Chapter 12

곱셈기·시프터·ALU

덧셈기(11장)가 데이터패스의 심장이라면, 곱셈기는 그 심장을 수십 개 겹쳐 놓은 근육이다. 64비트 곱셈 하나에는 부분곱 비트가 4096개 생기고, 이것을 한 클럭 남짓 안에 하나의 수로 합쳐야 한다. 비결은 의외로 단순하다. 캐리를 기다리지 않는 것이다. 이 장에서는 손 곱셈의 모양에서 출발해 부분곱을 나무처럼 줄이는 월리스·다다 트리, 부분곱 수를 절반으로 줄이는 부스 부호화를 만지고, 이어서 시프터와 ALU, 비교기, 그리고 AI 가속기가 즐겨 쓰는 BF16·FP8까지 이르는 부동소수점 회로를 차례로 짓는다.

부분곱이 AND 행렬임을 알고, 배열 곱셈기와 트리 곱셈기의 지연이 $O(N)$과 $O(\log N)$으로 갈리는 이유를 설명한다.
캐리 저장 덧셈(3:2 압축기)으로 월리스·다다 트리를 짓고, 단계 수·전가산기 수·최종 CPA 폭을 계산한다.
radix-4 부스 부호화로 부호 있는 곱셈의 부분곱을 절반으로 줄이는 원리를 익힌다.
로그 시프터, 플래그(Z·N·C·V)를 내는 ALU, 비교기·LZC를 짓고, IEEE 754 부동소수점의 형식과 덧셈기 구조를 이해한다.

곱셈은 덧셈의 묶음: 부분곱

초등학교에서 배운 손 곱셈을 떠올려 보자. 13 × 11을 할 때 승수의 자리마다 피승수에 그 자리 숫자를 곱해 한 칸씩 밀어 적고, 마지막에 세로로 더한다. 각 줄을 부분곱(Partial product)이라 한다. 10진수에서는 줄마다 구구단이 필요하지만, 2진수에서는 승수의 자리가 0 아니면 1이다. 그래서 부분곱은 피승수 그대로이거나 0이고, 한 비트로 보면 그냥 AND 게이트다.

$$P = A \times B = \sum_{j=0}^{N-1} \left(A \cdot b_j\right) 2^{j} = \sum_{j=0}^{N-1}\sum_{i=0}^{N-1} \underbrace{(a_i \wedge b_j)}_{\text{부분곱 비트}}\; 2^{\,i+j}$$

$a_i, b_j$: 피승수 A와 승수 B의 i, j번째 비트. N비트 × N비트 곱은 부분곱 비트 $N^2$개(= AND 게이트 $N^2$개)를 만들고, 결과는 2N비트다.

아래 그림에서 A와 B의 비트를 눌러 보자. 승수 비트 $b_j$가 1인 줄에는 A가 그대로 복사되고, 0인 줄은 통째로 0이 된다. 각 점은 AND 게이트 하나의 출력이며, 같은 세로줄(같은 자리값 $2^{i+j}$)의 점끼리 더해야 곱이 된다. 이 "점을 세로로 더하는 문제"가 곱셈기 설계의 전부다.

피승수 A 승수 B

곱 A×B—

0이 아닌 부분곱 줄—

AND 게이트16개

그림 12-1. 해 보기A, B의 비트 칸을 누르거나 슬라이더를 움직이면 부분곱 행렬이 한 줄씩 채워진다. 초록 점은 1, 회색 점은 0이다. 넓은 화면에서는 오른쪽에 같은 곱셈을 10진수 손 곱셈으로 나란히 보여 준다. 2진수의 줄은 "A 아니면 0"뿐이라는 점을 확인하자.

부분곱 행렬은 평행사변형 모양이다. 가운데 자리(자리값 $2^{N-1}$)에 점이 가장 많아 N개가 쌓이고, 양 끝으로 갈수록 줄어든다. 점을 만드는 데는 AND 게이트 한 단(약 5 ps)이면 충분하다. 비용은 점을 더하는 데서 생긴다.

시프트-덧셈 곱셈기: 시간으로 면적을 산다

가장 작은 곱셈기는 덧셈기 하나와 레지스터로 만든다. 매 클럭 B의 한 비트를 보고 A를 더할지 말지 정한 뒤 누산기를 한 칸 민다. N비트 곱에 N 클럭이 걸리지만 면적은 덧셈기 하나다. 작은 마이크로컨트롤러나 암호 가속기의 큰 정수 곱셈에서 지금도 쓰인다. 반대로 고성능 CPU는 N² 개의 점을 한꺼번에 더하는 병렬 곱셈기를 쓰고, 그 방법이 이 장의 나머지 절반이다.

배열 곱셈기: 가산기 격자

점을 더하는 가장 직접적인 방법은 부분곱 줄을 하나씩 차례로 더하는 것이다. 덧셈기 N−1개를 위아래로 쌓으면 손 곱셈과 똑같이 생긴 격자가 된다. 이것이 배열 곱셈기(Array multiplier)다. 각 줄을 리플 캐리 덧셈기로 만들면 캐리가 옆으로도 흘러 경로가 길어지므로, 보통은 캐리를 옆이 아니라 아래 줄로 넘긴다. 줄마다 전가산기 출력이 합(sum)과 캐리(carry) 두 벡터로 남고, 맨 아래에서 한 번만 캐리를 전파하는 덧셈기로 마무리한다.

아래 격자에서 시간을 흘려 보자. 각 칸은 반가산기(HA) 또는 전가산기(FA)이고, 색이 칠해지는 순간이 그 칸의 출력이 확정되는 시각이다. 대각선으로 내려가는 선은 합, 수직선은 캐리다. 신호가 격자를 사선으로 훑으며 내려가고, 마지막 줄의 리플 덧셈에서 다시 옆으로 흐른다.

비트 폭 N 시간

애니메이션

셀 수—

임계 경로—

FO4 환산—

그림 12-2. 해 보기재생을 누르거나 시간 슬라이더를 끌어 확정되는 칸을 보자. 주황 테두리가 임계 경로다. N을 4에서 8로 늘리면 임계 경로가 거의 2배가 된다. 교육용 지연: AND 5 ps, FA 합 15 ps·캐리 10 ps, HA 합 10 ps·캐리 6 ps(DG-7, FO4 = 7.5 ps).

$$t_{\text{array}} \approx t_{AND} + (N-1)\,t_{FA} + (N-1)\,t_{carry} \;=\; O(N)$$

위 줄 N−1개를 사선으로 지나고($t_{FA}$), 맨 아래 리플 덧셈의 N−1자리를 옆으로 지난다($t_{carry}$). 셀 수는 약 $N^2$개로 규칙적이라 레이아웃은 쉽지만, 지연이 비트 폭에 비례한다.

배열 곱셈기의 장점은 규칙성이다. 같은 셀을 바둑판처럼 깔면 되고 배선이 이웃끼리만 이어진다. 단점은 64비트라면 줄 63개를 지나야 한다는 것이다. DG-7에서 대략 63×15 + 63×10 ≈ 1.6 ns, 4 GHz 클럭 여섯 주기가 넘는다. 줄을 차례로 더하지 말고 한꺼번에 여러 줄씩 줄여야 한다.

부분곱 줄이기: 캐리 저장 덧셈과 트리

열쇠는 전가산기를 다시 보는 것이다. 전가산기는 같은 자리의 세 비트를 받아 합 비트(같은 자리)와 캐리 비트(한 자리 위)를 낸다. 즉 세 개의 비트를 두 개로 줄이는 장치, 3:2 압축기(3:2 compressor)다. 전가산기를 자리마다 하나씩 나란히 놓고 캐리를 옆 칸에 넘기지 않으면, 세 개의 수가 합 벡터 S와 캐리 벡터 C 두 개로 줄어든다. 이것이 캐리 저장 덧셈기(Carry-save adder, CSA)다.

$$X + Y + Z \;=\; S + 2C, \qquad s_i = x_i \oplus y_i \oplus z_i,\quad c_{i} = \mathrm{MAJ}(x_i, y_i, z_i)$$

캐리 $c_i$는 자리값이 두 배이므로 한 칸 왼쪽($2C$)에 놓인다. 자리끼리 서로 기다리지 않으므로 CSA의 지연은 비트 폭과 무관하게 전가산기 하나(약 15 ps)다.

입력

X + Y + Z—

S + 2C—

CSA 지연1 FA ≈ 15 ps

그림 12-3. 해 보기X, Y, Z의 비트를 눌러 바꿔 보자. 세로줄 하나마다 전가산기 하나가 있고, 그 캐리는 아래 C 줄에서 한 칸 왼쪽으로 내려앉는다. 어느 열을 바꿔도 이웃 열의 S는 변하지 않는다. 마우스를 열 위에 올리면 그 열의 전가산기가 강조된다.

CSA를 나무처럼 엮으면 N개의 부분곱 줄을 $N \to \tfrac{2}{3}N \to \tfrac{4}{9}N \to \cdots \to 2$로 줄일 수 있다. 두 줄이 남으면 그때 단 한 번, 빠른 캐리 전파 덧셈기(Carry-propagate adder, CPA)(11장의 프리픽스 덧셈기)로 더한다. 1964년 월리스 트리(Wallace tree)는 매 단계 가능한 한 많은 비트를 3개씩 묶어 줄였다. 1965년 다다(Luigi Dadda)는 반대로 필요한 만큼만 줄이는 방법을 제안했다. 높이 목표를 $2, 3, 4, 6, 9, 13, 19, \ldots$(앞 값의 1.5배 내림)으로 정하고, 각 단계에서 열 높이가 다음 목표를 넘지 않을 만큼만 전가산기·반가산기를 쓴다. 단계 수는 같지만 반가산기가 훨씬 적다. 이것이 다다 트리(Dadda tree)다.

비트 폭을 4배로 늘리면 트리의 단계 수는?

4×4 곱셈기의 다다 트리는 2단계로 부분곱을 두 줄로 줄인다. 16×16 곱셈기는 몇 단계가 필요할까? 8단계(2배), 6단계, 16단계 중 무엇일까? 아래 시뮬레이터로 확인하기 전에 예측해 보자.

답 보기

6단계다. 다다 목표 수열 2, 3, 4, 6, 9, 13, 19에서 16을 넘지 않는 가장 큰 값은 13이고, 16 → 13 → 9 → 6 → 4 → 3 → 2로 6번 줄인다. 한 단계마다 높이를 약 2/3로 줄이므로 단계 수는 $\log_{1.5}(N/2)$에 비례한다. 폭이 4배가 되어도 단계는 3배밖에 늘지 않고, 64비트에서도 10단계면 된다.

SIMULATOR

점 다이어그램으로 보는 부분곱 축소

부분곱 비트합(sum)캐리(carry)전가산기 FA (3→2)반가산기 HA (2→2)

비트 폭 N

축소 방식

단계

축소 단계 수—

전가산기 / 반가산기—

최종 CPA 폭—

추정 지연—

열 최대 높이—

위쪽은 현재 단계의 점 배열과 이번 단계에서 쓰는 FA(파란 상자, 같은 열의 점 3개 → 합 1개 + 왼쪽 열 캐리 1개)와 HA(노란 점선, 2개 → 2개), 아래쪽은 그 결과다. 오른쪽 끝이 자리값 $2^0$이다. 배열 방식은 한 단계에 부분곱 한 줄씩만 받아들인다(흐린 점은 아직 기다리는 줄). 지연 추정(DG-7 교육용): AND 5 ps + 단계당 FA 15 ps + CPA(트리는 프리픽스 덧셈기 $(\lceil\log_2 w\rceil+1)\times 7.5$ ps, 배열은 리플 캐리 $w\times 10$ ps).

세 방식을 비교해 보면 성격이 뚜렷하다. 배열은 단계가 N−2개로 길지만 매 단계 이웃끼리만 연결된다. 월리스는 처음부터 공격적으로 줄여 최종 CPA가 짧아지는 대신 반가산기를 많이 쓴다. 다다는 전가산기 수가 같으면서 반가산기를 최소로 쓰고 대신 최종 CPA가 조금 넓다. 실제 설계에서 셀 수만큼 중요한 것은 배선이다. 트리는 서로 멀리 떨어진 열과 단계를 엮어 배선이 불규칙하고 길어지므로, 레이아웃을 정돈하기 쉬운 4:2 압축기 기반 트리나 단계를 열 단위로 재배치하는 방법이 쓰인다.

$$\text{단계 수} \approx \left\lceil \log_{3/2}\frac{N}{2} \right\rceil, \qquad t_{\text{tree}} \approx t_{AND} + \text{단계 수}\cdot t_{FA} + t_{CPA}(2N) \;=\; O(\log N)$$

한 단계에서 높이가 약 2/3로 줄어든다. 16비트 6단계, 32비트 8단계, 64비트 10단계. $t_{CPA}$도 프리픽스 덧셈기라면 $O(\log N)$이다.

4:2 압축기와 단계당 전가산기 두 개

전가산기 두 개를 엮으면 같은 열의 비트 4개(+옆 열에서 오는 캐리 1개)를 2개로 줄이는 4:2 압축기가 된다. 옆 열로 나가는 캐리가 들어오는 캐리에 의존하지 않도록 짜면 지연이 FA 두 개가 아니라 XOR 약 3단(≈ 1.5 FA)으로 줄고, 무엇보다 트리가 이진 트리 모양이 되어 배선이 규칙적이다. 64비트 곱셈기의 부분곱 32줄(부스 부호화 후)은 4:2 압축기 4단(32→16→8→4→2)으로 줄일 수 있다. 많은 상용 곱셈기가 이 구조를 쓴다.

부스 부호화: 부분곱을 절반으로

트리의 크기와 깊이는 부분곱 줄 수가 정한다. 줄 수 자체를 줄일 수는 없을까? 승수를 2비트씩 묶어 4진수로 보면 각 자리는 0, 1, 2, 3이다. 0·1·2배는 쉽다(2배는 한 칸 시프트). 문제는 3배다. 3A = 2A + A는 그 자체로 덧셈이 필요한 "어려운 배수"다. 부스 부호화(Booth encoding)는 3을 4 − 1로 바꿔 쓴다. 다음 자리에 1을 올리고 이 자리에서는 −1을 쓰면, 모든 자리가 $\{-2, -1, 0, +1, +2\}$ 안에 들어온다.

회로로는 더 깔끔하다. 승수 비트를 겹치는 3비트 창 $(b_{2i+1}, b_{2i}, b_{2i-1})$으로 훑고($b_{-1} = 0$), 각 창에서 바로 자리 숫자를 읽는다.

$$d_i = -2\,b_{2i+1} + b_{2i} + b_{2i-1}, \qquad B = \sum_{i=0}^{N/2-1} d_i\,4^{i}, \qquad A\times B = \sum_{i} \left(d_i A\right) 4^{i}$$

$d_i \in \{-2,-1,0,+1,+2\}$. 맨 위 비트 $b_{N-1}$에 $-2$의 가중치가 붙으므로 2의 보수(부호 있는 수)가 그대로 맞는다. N비트 승수에 부분곱이 N/2줄이다.

$b_{2i+1}$	$b_{2i}$	$b_{2i-1}$	자리 숫자 $d_i$	부분곱	회로 동작
0	0	0	0	0	0 선택
0	0	1	+1	+A	A 선택
0	1	0	+1	+A	A 선택
0	1	1	+2	+2A	A를 한 칸 시프트
1	0	0	−2	−2A	2A 반전 + 1
1	0	1	−1	−A	A 반전 + 1
1	1	0	−1	−A	A 반전 + 1
1	1	1	0	0	0 선택

피승수 A 승수 B 처리한 창 수

자리 숫자 d₃d₂d₁d₀—

누적 합—

정답 A×B—

그림 12-4. 해 보기8비트 부호 있는 승수 B를 3비트 창(주황 괄호) 네 개가 두 칸씩 겹치며 훑는다. "처리한 창 수"를 1부터 4까지 올리며 부분곱이 한 줄씩 쌓이는 것을 보자. 8줄이 아니라 4줄이다. 흐린 비트는 시프트로 생긴 0과 부호 확장 비트다. B = −1(11111111)이나 B = −128을 넣어 보면 음수 승수도 보정 없이 맞는다.

부스 부호화의 대가는 부분곱 생성기다. 각 줄에서 0, ±A, ±2A 중 하나를 고르는 5:1 MUX와 반전 회로가 필요하고, 음수 부분곱의 "+1"은 다음 줄의 빈자리에 끼워 넣는다. 그래도 트리의 전가산기가 거의 절반으로 줄고 단계도 하나 이상 줄어 이득이 크다. 64비트 곱셈기는 거의 모두 radix-4 부스를 쓴다. radix-8(4비트 창)은 줄을 1/3로 줄이지만 3A라는 어려운 배수를 미리 덧셈으로 만들어 두어야 해서, 지연보다 면적·전력이 중요한 곳에서만 쓰인다.

부호 확장이 트리를 망친다

음수 부분곱은 2의 보수라서 맨 위 비트를 결과 폭(2N)까지 복사해야 한다. 그림의 흐린 비트들이다. 그대로 두면 왼쪽 열이 부호 비트로 가득 차 트리가 커진다. 실제 곱셈기는 각 줄의 부호 비트 s를 반전해 $\bar{s}$로 두고 앞에 상수 1을 몇 개 붙이는 기법(sign-extension prevention)으로, 모든 줄의 부호 확장을 미리 계산한 상수 하나로 바꾼다. 같은 원리가 부호 있는 배열 곱셈기의 Baugh–Wooley 방식에도 쓰인다.

시프터: 한 번에 여러 칸 밀기

시프트는 곱셈·나눗셈의 2의 거듭제곱 버전이자, 부동소수점의 정렬과 정규화, 비트 필드 추출에 쓰인다. 조합 회로로 0~N−1칸을 한 번에 미는 방법은 두 가지다. 배럴 시프터(Barrel shifter)는 출력 비트마다 N:1 MUX를 두어 시프트 양을 디코드한 신호로 한 번에 고른다. 지연은 전송 게이트 하나 수준으로 짧지만 MUX 입력이 $N^2$개이고 배선이 격자로 교차한다. 로그 시프터(Logarithmic shifter)는 시프트 양을 2진수로 보고, 비트 $k_j$가 1이면 $2^j$칸 미는 2:1 MUX 단을 $\log_2 N$개 잇는다.

$$\text{로그 시프터: } N\log_2 N \text{개의 2:1 MUX},\; \log_2 N \text{단}, \qquad \text{배럴 시프터: } N^2 \text{개의 스위치},\; 1\text{단(+ 디코더)}$$

64비트에서 로그 시프터는 MUX 384개·6단, 배럴 시프터는 스위치 4096개다. 비트 폭이 크면 로그 시프터가 면적과 배선에서 압도적으로 유리하다.

연산

시프트 양 k

입력—

출력—

켜진 단—

그림 12-5. 해 보기8비트 로그 시프터. 맨 윗줄 입력 비트를 눌러 바꾸고 k를 움직여 보자. k = 5 = 101₂이면 1칸 단과 4칸 단만 켜지고(사선) 2칸 단은 그대로 통과한다(수직선). 산술 오른쪽 시프트는 빈자리를 부호 비트로 채우고(주황), 회전은 밀려난 비트를 반대편으로 되돌린다.

한 회로로 네 연산을 다 하는 것도 어렵지 않다. 오른쪽 시프트는 입력과 출력의 비트 순서를 뒤집은 왼쪽 시프트이고, 회전은 빈자리에 0 대신 밀려난 비트를 넣는 것이며, 산술 시프트는 부호 비트를 넣는 것이다. 각 MUX 단의 "빈자리 채움" 입력만 고르면 된다. 고성능 코어의 시프터는 1클럭 안에 들어가며(64비트 6단 MUX ≈ 6~8 FO4), 부동소수점 덧셈기의 정렬·정규화 시프터도 같은 구조다.

ALU: 덧셈기 + 논리 + MUX, 그리고 플래그

산술 논리 장치(Arithmetic logic unit, ALU)는 새로운 회로가 아니다. 덧셈기 하나, 비트별 논리 게이트 묶음, 시프터를 나란히 놓고 결과 MUX로 하나를 고른다. 뺄셈은 따로 만들지 않는다. $A - B = A + \bar{B} + 1$이므로 B 앞에 XOR(조건부 반전)를 두고 캐리 입력에 1을 넣으면 같은 덧셈기가 뺄셈기가 된다.

결과 옆에는 네 개의 상태 플래그(Status flags)가 나온다. 분기 명령은 이 플래그만 보고 판단한다.

$$Z = \overline{r_{N-1} \lor \cdots \lor r_0},\quad N = r_{N-1},\quad C = c_{N},\quad V = c_{N} \oplus c_{N-1} = \left(a_{N-1} \odot b'_{N-1}\right) \wedge \left(r_{N-1} \oplus a_{N-1}\right)$$

Z(zero): 결과가 0. N(negative): 결과의 부호 비트. C(carry): 맨 위 자리의 캐리 출력 — 부호 없는 수의 넘침, 뺄셈에서는 "빌림이 없었다(A ≥ B)". V(overflow): 부호 있는 수의 넘침 — 같은 부호끼리 더했는데 결과 부호가 다를 때. $b'$는 반전을 거친 B, $\odot$는 XNOR.

SIMULATOR

플래그를 내는 ALU

비트 폭

연산

A B

결과—

부호 없는 / 부호 있는 해석—

플래그 Z N C V—

해설—

교육용 ALU. 데이터 경로에서 이번 연산이 쓰는 블록과 선이 파랗게 밝아진다. A, B 비트 칸을 눌러 비트를 직접 바꿀 수 있다. SHL·SAR은 A를 B의 아래 3비트(4비트 폭이면 2비트)만큼 민다. SLT는 내부에서 A − B를 계산해 $N \oplus V$(부호 있는 A < B)를 0/1로 내보내며, 이때 플래그는 내부 뺄셈의 것이다. 논리 연산은 C = V = 0으로 둔다.

0x70 + 0x50은 넘쳤을까?

8비트에서 112 + 80 = 192 = 0xC0이다. 부호 없는 수로는 255 이하이니 문제없다. 그렇다면 플래그 C와 V는 각각 무엇일까? 부호 있는 수로 읽으면 결과는 몇인가?

답 보기

C = 0, V = 1이다. 맨 위 자리에서 캐리가 나가지 않았으므로 부호 없는 덧셈은 정상(192)이다. 그러나 양수(+112) + 양수(+80)인데 결과의 부호 비트가 1이라 부호 있는 수로는 −64가 되었다. 같은 비트 패턴, 같은 덧셈기인데 어떤 플래그를 볼지는 프로그램이 수를 어떻게 해석하는지에 달려 있다. 그래서 C 언어의 unsigned 비교와 signed 비교는 서로 다른 분기 명령(예: ARM의 BHI와 BGT)으로 번역된다.

비교 (A − B 후)	부호 없는 수	부호 있는 수
A = B	Z = 1
A < B	C = 0 (빌림 발생)	N ⊕ V = 1
A ≥ B	C = 1	N ⊕ V = 0
A > B	C = 1 그리고 Z = 0	Z = 0 그리고 N = V

ALU 지연의 대부분은 덧셈기다

논리 연산은 게이트 한두 단, 결과 MUX도 두세 단이다. ALU의 임계 경로는 거의 항상 B 반전 XOR → 덧셈기의 캐리 체인 → 결과 MUX → Z 플래그의 OR 트리로 이어진다. 그래서 고성능 코어는 64비트 덧셈기를 프리픽스 구조로 짓고, Z 플래그는 결과가 나오기를 기다리지 않고 A, B에서 직접 "A + B = 0인가"를 계산하는 회로로 앞당기기도 한다. 이 경로가 1클럭(약 15~20 FO4 이내)에 들어가야 연속된 덧셈 명령이 매 클럭 결과를 넘겨받을 수 있다. 데이터패스가 파이프라인과 바이패스 안에서 어떻게 쓰이는지는 SoCBook의 CPU 장에 있다.

비교기, 제로 검출, 선행 0 세기

크기 비교는 ALU의 뺄셈으로 할 수 있지만, 비교만 필요할 때는 더 싼 회로가 있다. 같음 비교는 비트마다 XNOR를 하고 전부 AND하면 된다. 크기 비교는 맨 위 비트부터 보다가 처음으로 다른 비트에서 결정된다. 그 자리에서 A가 1이면 A가 크다. 이 "처음 다른 자리 찾기"는 덧셈기의 캐리 전파와 같은 모양이라 프리픽스 트리로 $O(\log N)$에 끝난다.

제로 검출(Zero detection)은 N비트를 모두 OR한 뒤 반전하는 것, 즉 OR 트리다. 선행 0 개수(Leading zero count, LZC)는 맨 위에서부터 처음 1이 나오기 전까지 0이 몇 개인지 센다. 부동소수점 덧셈 후 결과를 정규화할 때 "왼쪽으로 몇 칸 밀어야 하는가"가 바로 LZC다. LZC도 트리로 짓는다. 두 반쪽의 (모두 0인가, LZC)를 합치는 규칙이 단순해서 16비트는 4단이면 된다.

회로

입력

결과—

——

그림 12-6. 해 보기비트 칸을 눌러 바꿔 보자. 제로 검출·LZC 모드에서는 16비트 OR 트리(4단)의 각 노드 값과 선행 1의 위치가 보인다. 크기 비교 모드에서는 맨 위부터 비트를 비교하다가 처음 다른 자리(주황)에서 결과가 정해진다. 그 아래 자리들은 아무리 바꿔도 결과에 영향이 없다.

부호 있는 비교는 맨 위 비트만 뒤집는다

2의 보수에서 부호 비트는 $-2^{N-1}$의 가중치를 가진다. 그래서 부호 있는 비교기는 두 수의 맨 위 비트를 반전한 뒤 부호 없는 비교기에 넣으면 된다(−128~127 범위가 0~255로 순서를 유지하며 옮겨진다). 같은 원리로 IEEE 754 부동소수점도 부호 비트만 따로 처리하면 나머지 비트를 정수처럼 비교해 크기 순서를 알 수 있다. 지수가 가수보다 위에 있도록 형식을 설계한 이유 중 하나다.

고정소수점과 부동소수점

정수 회로로 실수를 다루는 가장 간단한 방법은 소수점을 한 자리에 고정해 두는 고정소수점(Fixed point)이다. Q1.15 형식이라면 16비트 정수를 $2^{15}$으로 나눈 값으로 읽는다. 덧셈·곱셈 회로는 정수와 똑같고 곱한 뒤 시프트만 하면 되므로, DSP와 저전력 신호 처리에서 널리 쓰인다. 단점은 범위다. 아주 큰 수와 아주 작은 수를 같은 형식에 담을 수 없다.

부동소수점(Floating point)은 과학 표기법(1.23 × 10⁵)의 2진 버전이다. IEEE 754 형식은 비트를 부호 s, 지수 e, 가수 f 세 칸으로 나눈다. 지수는 바이어스를 더해 부호 없는 정수로 저장하고, 정규화된 수의 맨 앞 1은 항상 1이므로 저장하지 않는다(숨은 비트).

$$x = (-1)^{s} \times 2^{\,e - \text{bias}} \times \left(1 + \frac{f}{2^{M}}\right) \quad (0 < e < e_{\max}), \qquad x = (-1)^{s} \times 2^{\,1-\text{bias}} \times \frac{f}{2^{M}} \quad (e = 0)$$

M: 가수 비트 수, bias = $2^{E-1}-1$(E: 지수 비트 수). e = 0은 0과 비정규 수(Subnormal), e가 모두 1이면 ∞(f = 0)와 NaN(f ≠ 0). FP32는 E8·M23(bias 127), FP16은 E5·M10(bias 15), BF16은 E8·M7, FP8 E4M3은 E4·M3(bias 7, ∞ 없음).

형식

값 넣기 (반올림해 저장)

특별한 수

값—

해석—

종류 · 다음 수까지 간격—

반올림 오차—

그림 12-7. 해 보기비트 칸을 눌러 부호(주황 띠)·지수(파란 띠)·가수(초록 띠)를 바꾸면 값이 바로 해석된다. 0.1을 FP16과 BF16에 넣어 오차를 비교하고, "최대" 버튼으로 두 형식의 범위를 비교해 보자. 아래 막대는 이 형식이 담을 수 있는 크기의 범위(로그 눈금, 노란 부분은 비정규 수)와 현재 값의 위치다.

같은 16비트라도 FP16과 BF16은 성격이 정반대다. FP16은 가수가 10비트라 정밀하지만 최대가 65504에 불과해, 신경망 학습 중 기울기가 쉽게 넘치거나 0으로 사라진다. Google이 TPU에 도입한 BF16(Brain floating point)은 FP32의 지수 8비트를 그대로 두고 가수를 7비트로 잘랐다. 범위는 FP32와 같고 정밀도는 낮다. 신경망은 정밀도보다 범위에 민감해서, BF16은 FP32 학습을 거의 그대로 흉내 내며 곱셈기 면적은 가수 폭의 제곱에 비례하므로(8×8 대 24×24) 약 1/9로 줄어든다.

AI 가속기의 FP8과 블록 스케일링

2022년 이후 GPU·NPU는 8비트 부동소수점을 지원한다. E4M3(정밀도 우선, 최대 448)는 추론과 순전파에, E5M2(범위 우선, FP16과 같은 지수)는 역전파 기울기에 쓰는 식이다. 더 나아가 MX(microscaling) 형식은 32개 원소가 지수 하나를 공유하게 해 4~6비트 원소로도 정확도를 지킨다. 형식이 작아질수록 MAC 하나의 면적과 에너지가 빠르게 줄어 같은 칩에 더 많은 곱셈기를 넣을 수 있다. 이런 저정밀 형식을 쓰는 NPU의 MAC 배열과 데이터 흐름은 SoCBook의 NPU 장에서 다룬다.

부동소수점 덧셈기: 정렬, 덧셈, 정규화, 반올림

부동소수점 곱셈은 의외로 쉽다. 가수끼리 곱하고(정수 곱셈기) 지수끼리 더하면 된다. 어려운 쪽은 덧셈이다. 지수가 다른 두 수는 자리를 맞춰야 더할 수 있다. 덧셈기는 네 단계로 일한다. ① 지수를 비교해 작은 수의 가수를 차이 Δe만큼 오른쪽으로 민다(정렬 시프터). 밀려 나가는 비트는 버리지 않고 가드(G)·라운드(R)·스티키(S) 비트로 요약한다. ② 가수를 더하거나 뺀다. ③ 결과의 맨 앞 1이 제자리에 오도록 민다(캐리가 나면 오른쪽 1칸, 상쇄되어 앞이 0이면 LZC만큼 왼쪽). ④ G·R·S를 보고 가장 가까운 짝수로 반올림(Round to nearest, ties to even)한다.

A B

예제

지수 차 Δe · 연산—

정규화 · 반올림—

FP16 결과—

정확한 합과 비교—

그림 12-8. 해 보기FP16 덧셈기의 내부 가수 경로. 각 줄은 숨은 비트를 포함한 가수 11비트와 G·R·S 3비트이며, 세로 점선이 2진 소수점이다. B를 아주 작게 하면 정렬 단계에서 B가 통째로 스티키 비트로 사라지고, "상쇄" 예제에서는 정규화 시프터가 LZC만큼 왼쪽으로 크게 민다. 슬라이더 값은 가장 가까운 FP16 값으로 반올림되어 들어간다.

FP16에서 2048 + 1은?

FP16의 가수는 숨은 비트까지 11비트다. 2048 = 2¹¹에 1을 더하면 2049가 될까? 2048 + 3은?

답 보기

2048 + 1 = 2048이다. 2048 근처에서 FP16의 간격(ulp)은 2라서 2049는 2048과 2050의 정확히 한가운데이고, 짝수 쪽(가수 끝 비트가 0인 2048)으로 반올림된다. 2048 + 3 = 2051도 한가운데지만 이번에는 2052가 짝수 쪽이라 2052가 된다. 반올림 방향이 매번 같으면 오차가 한쪽으로 쌓이므로, IEEE 754는 "짝수로"를 기본으로 정해 평균 오차를 0으로 만든다. 큰 수에 작은 수를 계속 더하는 누산이 저정밀 형식에서 위험한 이유이기도 하다. 그래서 MAC은 곱은 FP8·BF16으로 하더라도 누산은 FP32로 하는 경우가 많다.

현대 프로세서는 곱셈과 덧셈을 따로 하지 않고 $A\times B + C$를 반올림 한 번으로 계산하는 융합 곱셈-덧셈(Fused multiply-add, FMA)을 기본 연산으로 쓴다. 곱셈기 트리의 마지막 두 줄에 정렬된 C를 세 번째 줄로 넣어 3:2 압축을 한 번 더 하면 되므로, 곱셈 뒤 덧셈을 따로 하는 것보다 빠르고 정확하다. 행렬 곱셈, 즉 AI 연산의 기본 단위인 MAC이 바로 이것이다.

실제 수치: 지연과 에너지

지금까지의 구조가 실제 칩에서 어느 정도 비용인지 대략값으로 보자. 먼저 연산 지연이다. 64비트 정수 곱셈은 부스 부호화 + 압축기 트리 + 128비트 CPA로, 4~5 GHz 코어에서 파이프라인 3~4단(약 0.7~0.9 ns)에 나뉘어 들어간다. 그래도 매 클럭 새 곱셈을 시작할 수 있다(처리량 1/클럭).

연산 (64비트 범용 코어)	지연 (클럭, 약)	처리량 (약)	비고
정수 덧셈·논리·시프트	1	클럭당 4개 내외	ALU 여러 개, 바이패스로 다음 명령이 바로 사용
정수 곱셈 (64×64 → 64)	3~4	클럭당 1개	x86 서버·데스크톱 코어 약 3 (2015~), ARM 고성능 코어 약 2~4
부동소수점 곱셈·FMA (FP64)	4~5	클럭당 2개	FMA 유닛 두 개가 흔하다 (2015~)
정수 나눗셈 (64비트)	약 15~90	수십 클럭당 1개	반복형(SRT 등)이라 값에 따라 다름. 최근 코어일수록 짧다

다음은 에너지다. Horowitz가 2014년 ISSCC 기조 강연에서 정리한 45 nm 공정 수치는 지금도 "연산은 싸고 데이터 이동은 비싸다"를 설명할 때 가장 많이 인용된다. 곱셈 에너지가 비트 폭의 제곱에 가깝게 늘고, 부동소수점이 정수보다 비싸며, 그보다 메모리 접근이 수십~수백 배 비싸다는 것을 보자.

연산 (45 nm, 0.9 V)	에너지 (약)	면적 (약)
8비트 정수 덧셈	0.03 pJ	36 µm²
32비트 정수 덧셈	0.1 pJ	137 µm²
8비트 정수 곱셈	0.2 pJ	282 µm²
32비트 정수 곱셈	3.1 pJ	3495 µm²
16비트 부동소수점 덧셈	0.4 pJ	1360 µm²
16비트 부동소수점 곱셈	1.1 pJ	1640 µm²
32비트 부동소수점 덧셈	0.9 pJ	4184 µm²
32비트 부동소수점 곱셈	3.7 pJ	7700 µm²
64비트 캐시(SRAM 8 KB) 읽기	10 pJ	—
64비트 DRAM 읽기	1300~2600 pJ	—

출처: M. Horowitz, "Computing's Energy Problem (and what we can do about it)," ISSCC 2014 기조 강연의 45 nm 추정치. 7 nm급(DG-7 수준) 공정에서는 연산 에너지가 대략 3~5배 줄었지만 상대적인 순서는 그대로다. 8비트 곱셈이 32비트 FP 곱셈보다 약 18배 싸다는 사실이 AI 가속기가 INT8·FP8로 내려가는 이유다.

곱셈기를 키우기 전에 데이터를 옮기는 비용을 보라

32비트 FP 곱셈 하나(3.7 pJ)보다 그 피연산자를 8 KB짜리 작은 캐시에서 64비트를 읽는 데 더 많은 에너지(약 10 pJ)가 들고, DRAM에서 가져오면 수백 배가 든다. 그래서 MAC 배열은 같은 데이터를 여러 번 재사용하도록(시스톨릭 배열, 가중치 고정 등) 짜고, 곱셈기 하나를 아끼는 것보다 레지스터·SRAM 접근을 줄이는 것이 전력에 더 크게 듣는다. 메모리 회로는 13장, 전력은 15장에서 다룬다.

핵심 정리

2진 곱셈의 부분곱은 AND 행렬이다. N×N 곱은 부분곱 비트 $N^2$개를 만들고, 곱셈기 설계는 이 점들을 세로로 더하는 문제다.
배열 곱셈기는 규칙적이지만 지연이 $O(N)$이다. 전가산기를 3:2 압축기로 쓰는 캐리 저장 덧셈은 캐리를 기다리지 않아 폭과 무관하게 FA 하나의 지연이다.
월리스·다다 트리는 높이를 단계마다 약 2/3로 줄여 $O(\log N)$ 단계(16비트 6단, 64비트 10단) 뒤 최종 CPA 한 번으로 끝낸다. 다다는 반가산기를 최소로 쓴다.
radix-4 부스 부호화는 겹치는 3비트 창으로 자리 숫자 $\{-2,\dots,+2\}$를 만들어 부분곱을 N/2줄로 줄이고, 부호 있는 곱셈을 보정 없이 처리한다.
로그 시프터는 $\log_2 N$단의 2:1 MUX로 모든 시프트·회전을 한다. ALU는 덧셈기 + 논리 + 시프터 + MUX이며, 플래그 Z·N·C·V로 부호 없는/있는 비교를 모두 판단한다.
비교·제로 검출·LZC는 모두 트리로 $O(\log N)$에 끝나며, LZC는 부동소수점 정규화의 시프트 양이다.
IEEE 754는 부호·지수·가수로 범위와 정밀도를 나누고, FP 덧셈은 정렬·덧셈·정규화·반올림(짝수로)을 거친다. BF16·FP8은 범위나 면적을 위해 가수를 줄인 형식이며, 메모리 접근이 연산보다 훨씬 비싸다.

확인 퀴즈

Q1. 부호 없는 8비트 × 8비트 병렬 곱셈기(부스 부호화 없음)가 만드는 부분곱 비트는 몇 개이고, 곱의 폭은?

$a_i \wedge b_j$가 i, j = 0..7 모두에 대해 생기므로 $8^2 = 64$개의 AND 게이트 출력이다. 두 8비트 수의 곱은 최대 255² = 65025 < 2¹⁶이므로 16비트다.

Q2. 캐리 저장 덧셈기(CSA)의 지연이 비트 폭과 무관한 이유는?

CSA는 세 수를 합 벡터 S와 캐리 벡터 C로 바꿀 뿐 캐리를 전파하지 않는다. 그래서 FA 하나의 지연으로 끝나고, 전파는 맨 마지막 CPA 한 번에 몰아서 한다.

Q3. 열 최대 높이가 9인 점 배열을 다다 방식으로 2줄까지 줄이려면 몇 단계가 필요한가?

다다 목표 수열 2, 3, 4, 6, 9에서 9 → 6 → 4 → 3 → 2로 네 번 줄인다. 배열 방식이라면 9 − 2 = 7단계가 걸린다.

Q4. radix-4 부스 부호화에서 창 $(b_{2i+1}, b_{2i}, b_{2i-1}) = (1, 1, 0)$이 고르는 부분곱은?

$d_i = -2\cdot1 + 1 + 0 = -1$이므로 −A다. 회로에서는 A를 반전하고 그 줄의 맨 아래에 1을 더한다.

Q5. 8비트 ALU에서 0x90 + 0x90을 계산했다. 플래그 C와 V는?

144 + 144 = 288 = 0x120이므로 결과는 0x20이고 맨 위 캐리가 나가 C = 1이다. 부호 있는 수로는 (−112) + (−112) = −224로 범위를 벗어났고, 음수 + 음수에서 결과 부호가 0(양수)이 되었으므로 V = 1이다.

Q6. BF16이 FP16보다 신경망 학습에 유리한 가장 큰 이유는?

BF16은 E8·M7로, FP16(E5·M10)보다 정밀도는 낮지만 최대값이 약 3.4×10³⁸로 FP32와 같다. 기울기가 넘치거나 사라지는 문제가 줄어 FP32 학습을 거의 그대로 흉내 낼 수 있다.