Chapter 11

덧셈기

프로세서가 하는 일의 대부분은 결국 덧셈이다. 주소 계산, 분기 목표, 비교, 곱셈의 부분곱 합치기까지 모두 덧셈기를 지난다. 그런데 64비트 덧셈은 64개의 1비트 덧셈을 나란히 하는 일이 아니다. 맨 아래 비트에서 생긴 캐리 하나가 맨 위 비트까지 번질 수 있기 때문이다. 이 장에서는 전가산기 하나에서 출발해 캐리가 비트를 따라 번지는 모습을 직접 보고, 그 사슬을 끊어 지연을 $N$에서 $\sqrt{N}$, 다시 $\log_2 N$으로 줄이는 구조들을 하나씩 만져 본다. 덧셈기 설계는 결국 "캐리를 얼마나 빨리, 얼마나 싸게 알아내는가"의 문제다.

반가산기·전가산기의 진리표와 게이트 회로를 만들고, 생성·전파·소멸 신호로 캐리 식 $c_{i+1} = g_i + p_i c_i$를 쓴다.
리플 캐리 덧셈기의 지연이 $N$에 비례하는 이유와 최악 입력을 설명한다.
캐리 예측·캐리 건너뛰기·캐리 선택 구조의 지연을 식으로 세우고 최적 블록 크기를 구한다.
(G,P) 결합 연산자 ∘로 병렬 접두사 덧셈기를 이해하고, Kogge–Stone·Brent–Kung·Sklansky·Han–Carlson의 단 수·면적·팬아웃·배선을 비교한다.

반가산기와 전가산기

초등학교에서 배운 세로 덧셈을 이진수로 하면 각 자리에서 하는 일은 같다. 그 자리의 두 비트와 아랫자리에서 올라온 올림수를 더해, 그 자리의 합 한 비트와 윗자리로 보낼 올림수 한 비트를 낸다. 올림수를 캐리(Carry)라 부른다.

두 비트만 더하는 회로가 반가산기(Half adder)다. 합은 두 비트가 다를 때 1이므로 XOR, 캐리는 둘 다 1일 때만 생기므로 AND다. 아랫자리 캐리까지 세 비트를 더하는 회로가 전가산기(Full adder, FA)다. 세 비트를 더한 결과는 0~3이고, 이를 두 비트 $(C_{out}, S)$로 쓴다. 반가산기 두 개와 OR 하나면 된다.

그림 11-1. 해 보기왼쪽 입력 원을 누르거나 아래 버튼, 진리표의 행을 눌러 입력을 바꾼다. 선의 색은 논리값이다(1 초록, 0 회색). 첫 XOR의 출력 $P = A \oplus B$와 첫 AND의 출력 $G = A\cdot B$가 이 장 전체의 주인공이다. 전가산기의 캐리는 "$G$가 1이거나, $P$가 1이고 아래 캐리가 1일 때" 1이 된다.

식으로 쓰면 다음과 같다. 캐리 출력은 세 입력 중 두 개 이상이 1이면 1이므로 다수결 함수(Majority, MAJ)이기도 하다.

$$ S = A \oplus B \oplus C_{in}, \qquad C_{out} = AB + C_{in}(A \oplus B) = AB + AC_{in} + BC_{in} = \mathrm{MAJ}(A,B,C_{in}) $$

$A, B$: 이 자리의 두 비트, $C_{in}$: 아랫자리에서 온 캐리, $S$: 합, $C_{out}$: 윗자리로 보내는 캐리. 두 번째 꼴($AB + C_{in}(A\oplus B)$)과 세 번째 꼴(다수결)은 같은 함수다. $A\oplus B$ 대신 $A + B$를 써도 캐리 식은 같다.

트랜지스터 수준에서는 게이트를 그대로 이어 붙이지 않는다. 정적 CMOS XOR는 비싸고(인버터 포함 약 12개), 그림처럼 XOR 2개·AND 2개·OR 1개로 지으면 40개가 넘는다. 실제 표준 셀 라이브러리의 전가산기는 다수결 함수를 한 번에 계산하는 복합 게이트로 $\overline{C_{out}}$을 먼저 만들고, 그것을 다시 써서 합을 만든다. 이것이 Weste & Harris가 소개하는 미러 가산기(Mirror adder)로, 트랜지스터 28개다.

구현	트랜지스터 수(대략)	특징
XOR 2 + AND 2 + OR 1 (정적 CMOS 게이트 조합)	약 42	그림 11-1 그대로. 교재용, 느리고 크다
NAND 9개	36	범용 게이트만으로 짓기(2장)
미러 가산기	28	풀업·풀다운이 거울 대칭, 캐리 경로는 2단 반전
전송 게이트(TG) 가산기	약 24	XOR를 전송 게이트로, 출력 구동력이 약해 버퍼 필요(7장)

미러 가산기의 두 가지 요령

첫째, 캐리 회로의 풀업과 풀다운이 같은 모양이다. $\overline{C_{out}} = \overline{AB + C_{in}(A+B)}$는 자기 쌍대 함수라서 pMOS 쪽을 nMOS 쪽과 똑같이(직렬·병렬을 뒤집지 않고) 배치해도 맞는 함수가 나온다. 그래서 "거울"이다. 둘째, 캐리 경로에 반전을 허용한다. 출력 $\overline{C_{out}}$을 그대로 다음 비트로 보내고, 홀수 비트에서는 입력도 반전해 받으면 비트마다 인버터 하나를 아낄 수 있다((Inverting adder)). 리플 캐리에서는 캐리 경로의 게이트 하나가 곧 비트당 지연이므로 이 차이가 크다. 또 캐리 게이트의 $C_{in}$ 트랜지스터를 출력에 가장 가깝게 두어 늦게 도착하는 신호의 기생 커패시턴스를 줄인다(5장의 입력 순서).

생성·전파·소멸

전가산기의 캐리 출력을 다르게 읽어 보자. 아래 캐리 $c_i$가 아직 도착하지 않았을 때, 이 자리의 두 비트만 보고도 미리 알 수 있는 것이 있다.

두 비트가 모두 1이면 아래 캐리와 상관없이 캐리가 생긴다. 생성(Generate) $g_i = a_i b_i$.
두 비트가 모두 0이면 아래 캐리와 상관없이 캐리가 사라진다. 소멸(Kill) $k_i = \overline{a_i}\,\overline{b_i}$.
둘 중 하나만 1이면 아래 캐리를 그대로 위로 넘긴다. 전파(Propagate) $p_i = a_i \oplus b_i$.

세 경우는 서로 배타적이고 빠짐없다. 즉 모든 자리는 G·P·K 셋 중 하나다. 캐리가 오래 기다려야 하는 곳은 P 자리뿐이다. G와 K는 입력이 들어오자마자 답이 정해진다.

$$ c_{i+1} = g_i + p_i\, c_i, \qquad s_i = p_i \oplus c_i $$

$g_i = a_i b_i$: 생성, $p_i = a_i \oplus b_i$: 전파, $c_i$: 비트 $i$로 들어오는 캐리($c_0 = C_{in}$), $s_i$: 합 비트. 캐리 식만 쓸 때는 $p_i = a_i + b_i$(OR, "전달 가능")로 써도 결과가 같지만, 합 비트를 만들려면 XOR 꼴이 필요하다.

A + B + Cin—

G · P · K 개수—

가장 긴 전파 사슬—

그림 11-2. 해 보기A·B 행의 비트를 눌러 바꾸고, 오른쪽 끝 원을 눌러 $C_{in}$을 바꾼다. 가운데 줄은 자리마다 G(주황)·P(파랑)·K(회색)를 표시한다. 캐리가 1인 경로 중 P 자리를 연달아 지나는 부분은 주황 띠로 이었다. 캐리는 G(또는 $C_{in}$)에서 태어나 P를 지나고, 첫 K에서 죽는다. 가장 긴 띠가 이 입력에서 캐리가 가장 오래 기다리는 길이다.

G·P·K는 "아직 모르는 캐리"의 함수 표현이다

자리 $i$를 "들어온 캐리 → 나가는 캐리" 함수로 보면 가능한 1비트 함수는 셋뿐이다. 상수 1(G), 상수 0(K), 항등(P). 이 관점이 4절의 캐리 예측과 6절의 병렬 접두사 덧셈기의 출발점이다. 여러 자리를 이어 붙인 블록도 결국 상수 1, 상수 0, 항등 중 하나의 함수가 되기 때문이다.

리플 캐리 덧셈기

전가산기 $N$개를 캐리 선으로 줄줄이 이으면 $N$비트 덧셈기가 된다. 각 FA는 아래 캐리가 도착해야 자기 캐리를 확정할 수 있으므로 캐리가 물결처럼 아래에서 위로 번진다. 그래서 리플 캐리 덧셈기(Ripple-carry adder, RCA)다. 가장 작고 단순하지만 가장 느리다.

SIMULATOR

캐리가 번지는 리플 캐리 덧셈기

비트 폭 N 재생 속도

입력

시간

현재 시각—

A + B + Cin—

가장 긴 전파 사슬—

이 입력의 완료 시각—

최악 지연 (N비트)—

A·B의 비트를 눌러 바꾸면 시각 0에서 다시 시작한다. 입력이 바뀐 직후 캐리와 합은 아직 확정되지 않았으므로 X(빨간 빗금)로 표시한다. 교육용 모델: 캐리 한 단 지연 $t_c$ = 1, 합 XOR = 1. G·K 자리의 캐리는 시각 1에 확정되고, P 자리는 아래 캐리가 확정된 뒤 1만큼 지나서 확정된다. 아래 막대는 각 합 비트가 확정되는 시각이다. DG-7에서 $t_c$는 약 1 FO4 ≈ 7.5 ps로 잡았다.

시뮬레이터에서 최악 입력을 눌러 보자. $A = 0111\ldots1$, $B = 0\ldots01$이면 비트 0이 G, 비트 1부터 $N-2$까지가 모두 P라서 캐리가 맨 아래에서 맨 위까지 한 칸씩 걸어 올라간다. 정적 타이밍 분석(10장)은 입력 값을 모르므로 언제나 이 최악 경로를 기준으로 클럭을 정한다.

$$ t_{\text{ripple}} \approx t_{pg} + (N-1)\,t_{c} + t_{\text{xor}} \;\propto\; N $$

$t_{pg}$: $g_i, p_i$를 만드는 시간, $t_c$: 캐리 한 단(AND-OR 또는 미러 가산기의 캐리 게이트) 지연, $t_{\text{xor}}$: 마지막 합 XOR. 64비트라면 캐리 63단, DG-7 기준 대략 60 FO4 ≈ 450 ps다. 5 GHz 클럭 한 주기(200 ps)의 두 배가 넘는다.

무작위 입력이면 캐리 사슬은 얼마나 길까?

64비트 두 수를 무작위로 골랐을 때 가장 긴 전파 사슬의 길이는 대략 얼마일까? 64에 가까울까, 훨씬 짧을까? 시뮬레이터의 무작위를 여러 번 눌러 16비트에서 먼저 감을 잡아 보자.

답 보기

훨씬 짧다. 각 자리가 P일 확률은 1/2이므로 P가 $m$개 연속할 확률은 $2^{-m}$이다. $N$비트에서 가장 긴 연속은 평균 약 $\log_2 N$, 64비트면 약 5~6비트다(Burks–Goldstine–von Neumann, 1946). 그래서 "캐리가 끝났는지 감지해 일찍 끝내는" 비동기 덧셈기도 연구되었다. 그러나 동기식 칩은 최악의 경우에 맞춰 클럭을 정해야 하므로 평균이 짧다는 사실을 쓸 수 없다. 아래의 모든 구조는 최악 지연을 줄이는 방법이다.

캐리 예측 덧셈기

캐리 식 $c_{i+1} = g_i + p_i c_i$를 자기 자신에 계속 대입하면 모든 캐리를 $c_0$와 $g, p$만으로 쓸 수 있다. 캐리가 도착하기를 기다리지 않고 "미리 내다보는" 셈이다. 이것이 캐리 예측(Carry-lookahead, CLA)이다.

$$ \begin{aligned} c_1 &= g_0 + p_0 c_0 \\ c_2 &= g_1 + p_1 g_0 + p_1 p_0 c_0 \\ c_3 &= g_2 + p_2 g_1 + p_2 p_1 g_0 + p_2 p_1 p_0 c_0 \\ c_4 &= \underbrace{g_3 + p_3 g_2 + p_3 p_2 g_1 + p_3 p_2 p_1 g_0}_{G_{3:0}} + \underbrace{p_3 p_2 p_1 p_0}_{P_{3:0}}\, c_0 \end{aligned} $$

$G_{3:0}$: 4비트 블록 안에서 캐리가 생겨 밖으로 나가는가(블록 생성), $P_{3:0}$: 블록에 들어온 캐리가 그대로 빠져나가는가(블록 전파). 블록 전체도 $c_4 = G_{3:0} + P_{3:0}\,c_0$로 1비트 자리와 똑같은 꼴이 된다.

블록 생성 G_3:0—

블록 전파 P_3:0—

c₄ 를 정한 항—

그림 11-3. 해 보기위쪽 A·B 비트와 $c_0$ 원을 눌러 바꾼다. 아래는 4비트 블록의 캐리 식을 펼친 것이다. 1이 된 곱항이 주황으로 켜진다. 각 캐리는 OR 안의 곱항 중 하나만 켜져도 1이다. $c_4$의 마지막 항은 곱 다섯 개(팬인 5)이고 OR는 입력이 다섯이다. 블록을 4비트보다 크게 만들기 어려운 이유가 보인다.

4비트 블록이 $G_{3:0}, P_{3:0}$를 내면 블록을 다시 1비트 자리처럼 다룰 수 있다. 블록 4개의 $(G,P)$를 2단 CLA 유닛에 넣으면 16비트의 블록 캐리 $c_4, c_8, c_{12}, c_{16}$이 같은 식으로 나오고, 다시 4개를 묶으면 64비트가 된다. 단 수는 $\log_4 N$에 비례한다. 신호는 트리를 올라가며 $(G,P)$를 모으고, 내려오며 블록 캐리를 나눠 준다.

그림 11-4. 16비트 2단 CLA. 4비트 블록마다 블록 (G,P)를 올려 보내고(주황), 2단 유닛이 블록 캐리를 계산해 내려 준다(파랑 점선). 각 블록은 받은 캐리로 내부 캐리와 합을 만든다. 64비트는 이것을 한 단 더 쌓는다.

"예측"에도 공짜는 없다

펼친 식은 비트 수가 늘수록 항의 수가 제곱으로, 곱항의 팬인이 선형으로 늘어난다. 5장에서 본 것처럼 직렬 nMOS가 4~5개를 넘으면 게이트가 급격히 느려지고, 6장의 논리적 노력도 팬인에 비례해 커진다. 그래서 실제 CLA는 4비트(때로 3비트) 블록을 트리로 쌓는다. 이 "트리로 쌓기"를 가장 일반적인 형태로 정리한 것이 6절의 병렬 접두사 덧셈기다.

캐리 건너뛰기와 캐리 선택

CLA처럼 큰 논리를 쓰지 않고도 리플 캐리를 빠르게 하는 값싼 방법이 둘 있다. 둘 다 $N$비트를 $k$비트짜리 블록으로 자른다.

캐리 건너뛰기(Carry-skip, Carry-bypass)는 블록 안 모든 자리가 P이면($P_{\text{blk}} = p_{k-1}\cdots p_0 = 1$) 들어온 캐리를 MUX 하나로 블록 끝까지 곧장 보낸다. 블록 안에서 캐리가 생기는 경우는 블록 안의 리플로 처리된다. 최악 경로는 첫 블록에서 생긴 캐리가 리플로 빠져나와, 가운데 블록들을 MUX로 건너뛰고, 마지막 블록에서 다시 리플하는 길이다.

캐리 선택(Carry-select)은 더 대담하다. 각 블록을 두 벌 만들어 하나는 "들어올 캐리가 0", 다른 하나는 "1"이라고 가정하고 미리 계산한다. 진짜 캐리가 도착하면 MUX로 둘 중 하나를 고르기만 한다. 면적은 거의 두 배지만 블록마다 MUX 한 단만 지나면 된다.

$$ t_{\text{skip}} \approx t_{pg} + 2(k-1)\,t_c + \left(\tfrac{N}{k}-1\right) t_{\text{mux}} + t_{\text{xor}}, \qquad t_{\text{select}} \approx t_{pg} + k\,t_c + \left(\tfrac{N}{k}-1\right) t_{\text{mux}} + t_{\text{xor}} $$

$k$: 블록 크기(비트), $N/k$: 블록 수, $t_{\text{mux}}$: 건너뛰기·선택 MUX 한 단. 모든 단위 지연을 1로 두면 $t_{\text{skip}} \approx 2k + N/k - 1$은 $k = \sqrt{N/2}$에서, $t_{\text{select}} \approx k + N/k + 1$은 $k=\sqrt{N}$에서 가장 작다. 두 경우 모두 최적 지연은 $\propto \sqrt{N}$이다.

비트 폭 N 블록 크기 k

리플 캐리—

건너뛰기 (이 k)—

선택 (이 k)—

최적 k (건너뛰기 / 선택)—

그림 11-5. 해 보기블록 크기 $k$를 바꿔 보자. 위 띠는 $N$비트를 $k$비트 블록으로 자른 모습과 최악 경로(주황)다. 아래 그래프는 $k$에 따른 최악 지연(단위 $t_c$)이다. $k$가 너무 작으면 블록 수 $N/k$만큼 MUX를 지나고, 너무 크면 블록 안 리플이 길어진다. 그 사이에 최적점이 있다.

블록 크기를 모두 같게 해야 할까?

캐리 건너뛰기에서 최악 경로는 첫 블록과 마지막 블록에서만 리플한다. 블록 크기를 자리마다 다르게 하면 더 빨라질 수 있을까? 어떤 모양이 좋을까?

답 보기

그렇다. 가운데 블록은 건너뛰기만 당하므로 크게, 양 끝 블록은 리플을 해야 하므로 작게 만들면 된다. 예를 들어 2, 3, 4, …, 4, 3, 2처럼 가운데가 불룩한 가변 블록이 균일 블록보다 빠르다. 캐리 선택도 같은 생각으로 블록 크기를 1비트씩 늘려($k, k+1, k+2,\ldots$) 앞 블록의 MUX 출력과 다음 블록의 계산이 동시에 끝나게 맞추면 지연이 약 $\sqrt{2N}$으로 준다. 어느 쪽이든 규모는 여전히 $\sqrt{N}$이다.

병렬 접두사 덧셈기

2절의 관점으로 돌아가자. 자리 $i$부터 $j$까지($i \ge j$)의 연속된 비트 구간은 들어온 캐리를 상수 1로 만들거나(블록 생성 $G_{i:j}=1$), 그대로 넘기거나(블록 전파 $P_{i:j}=1$), 상수 0으로 만든다. 두 인접 구간을 이어 붙인 구간의 $(G,P)$는 다음 연산자 $\circ$로 구한다.

$$ (G,P)_{i:k} = (G,P)_{i:j} \circ (G,P)_{j-1:k} = \bigl(\,G_{i:j} + P_{i:j}\,G_{j-1:k},\;\; P_{i:j}\,P_{j-1:k}\,\bigr), \qquad c_{i+1} = G_{i:0} $$

위쪽 구간 $i:j$가 생성하면 그대로 생성, 전파하면 아래쪽 구간의 결과를 물려받는다. $C_{in}$은 비트 −1의 생성 신호 $g_{-1}=C_{in}$로 넣으면 되므로 아래에서는 $C_{in}=0$으로 둔다. 결국 $N$개의 캐리는 $(g_i,p_i)$ 수열의 모든 접두사 $G_{i:0}$이다. 합은 $s_i = p_i \oplus G_{i-1:0}$.

$\circ$의 핵심 성질은 결합 법칙이다. $(x\circ y)\circ z = x\circ(y\circ z)$. 순서(교환 법칙)는 바꿀 수 없지만, 괄호는 아무렇게나 쳐도 된다. 괄호를 왼쪽부터 차례로 치면 리플 캐리($N-1$단), 균형 잡힌 트리로 치면 $\log_2 N$단이다. 덧셈의 고속화는 "모든 접두사를 얕은 트리로 동시에 계산하는" 병렬 접두사(Parallel prefix) 문제가 된다.

결과 (G,P)_3:0—

세 묶음 결과가 같은가—

∘ 단 수 (깊이)—

그림 11-6. 해 보기맨 위 네 칸(비트 3~0)을 누르면 K → P → G 순으로 바뀐다. 괄호 묶음을 바꿔도 맨 아래 결과는 언제나 같다. 바뀌는 것은 트리의 깊이, 즉 지연이다. 비트 3이 G이면 아래가 무엇이든 결과는 G, 비트 3이 K이면 결과는 K다. P인 위쪽 비트는 아래쪽 결과를 그대로 물려받는다.

병렬 접두사 덧셈기는 세 부분으로 된다. ① 자리마다 $g_i, p_i$를 만든다. ② 접두사 네트워크가 모든 $G_{i:0}$을 계산한다. ③ $s_i = p_i \oplus G_{i-1:0}$. 구조의 차이는 모두 ②에 있다. 네트워크는 점(∘ 셀)과 선(배선)으로 그린 그래프이고, 설계자가 맞바꾸는 것은 네 가지다. 단 수(지연), 셀 수(면적·전력), 팬아웃(한 셀이 구동하는 부하), 배선(가로로 길게 뻗는 선의 수와 길이).

SIMULATOR

접두사 네트워크 탐험기

G 생성P 전파K 소멸아직 계산 안 됨선: 위 노드 → ∘ 셀

비트 폭

구조

A (16진) B (16진)

입력

단계 진행

∘ 단 수—

∘ 셀 수—

최대 팬아웃—

배선 (최장 / 총, 비트 피치)—

합 S (16진)—

가리킨 노드노드 위에 올려 보자

맨 위 줄은 비트별 $(g_i,p_i)$, 그 아래 각 줄이 접두사 네트워크의 한 단이다. 점은 ∘ 셀(위쪽 같은 비트의 노드와 대각선으로 이어진 아래쪽 비트 노드를 결합), 점 없이 내려가는 세로선은 값을 그대로 넘기는 배선이다. 맨 아래 줄은 합 비트 $s_i$(논리값 색). "다음 단"으로 한 단씩 계산하고, 노드 위에 포인터를 올리면(모바일은 누르면) 그 노드의 값을 만드는 입력 원뿔이 강조된다. MSB가 왼쪽이다. $C_{in}=0$.

네 가지 고전 구조의 성격을 정리하면 다음과 같다($N$비트, 접두사 네트워크만).

구조	단 수	∘ 셀 수	최대 팬아웃	64비트 (단 / 셀 / 팬아웃 / 총 배선)	성격
직렬(리플)	$N-1$	$N-1$	2	63 / 63 / 2 / 63	가장 작고 가장 느림
Sklansky (1960)	$\log_2 N$	$\tfrac{N}{2}\log_2 N$	$\tfrac{N}{2}+1$	6 / 192 / 33 / 1104	분할 정복. 단 수 최소지만 팬아웃이 크다
Kogge–Stone (1973)	$\log_2 N$	$N\log_2 N - N + 1$	2	6 / 321 / 2 / 2667	단 수·팬아웃 최소, 셀과 배선이 가장 많다
Brent–Kung (1982)	$2\log_2 N - 1$	$2N - 2 - \log_2 N$	2	11 / 120 / 2 / 321	올라갔다 내려오는 트리. 작지만 단이 두 배
Han–Carlson (1987)	$\log_2 N + 1$	$\tfrac{N}{2}\log_2 N$	2	7 / 192 / 2 / 1365	홀수 비트만 Kogge–Stone, 마지막에 짝수 비트 한 단

Kogge–Stone은 왜 "가장 빠르다"고만 말하기 어려울까?

64비트에서 Kogge–Stone과 Sklansky는 둘 다 6단이다. 그런데 Kogge–Stone의 셀은 321개, Sklansky는 192개다. 시뮬레이터에서 두 구조를 64비트로 번갈아 보며, Kogge–Stone이 단 수 말고 무엇을 얻으려고 셀을 더 쓰는지, 그 대가로 무엇이 늘어나는지 찾아보자.

답 보기

Kogge–Stone은 모든 셀의 팬아웃을 2로 묶는다. Sklansky는 마지막 단에서 노드 하나가 32개 셀을 구동해야(팬아웃 33) 하므로 6장의 논리적 노력으로 보면 그 단이 크게 느려지거나 버퍼를 넣어야 한다. 대신 Kogge–Stone은 단마다 $N$개 가까운 선이 $2^l$비트씩 가로로 뻗어 총 배선이 2667 비트 피치로 Sklansky의 두 배가 넘고, 마지막 단에는 32비트를 가로지르는 선이 32개 나란히 지나간다. 배선 트랙과 배선 커패시턴스(14장), 전력이 대가다. Han–Carlson은 한 단을 더 쓰고 이 배선을 절반으로 줄인 절충이다.

접두사 구조의 지도: Knowles와 Harris의 분류

Knowles(1999)는 Kogge–Stone과 Sklansky 사이를 잇는 구조군을 팬아웃 매개 변수로 정리했고, Harris(2003)는 모든 고전 구조를 세 축, 즉 단 수 $\log_2 N + l$, 팬아웃 $2^f + 1$, 배선 트랙 $2^t$로 나타낼 수 있으며 $l + f + t = \log_2 N - 1$이라는 관계를 보였다. Brent–Kung은 $l$을, Sklansky는 $f$를, Kogge–Stone은 $t$를 최대로 쓴 꼭짓점이고 Han–Carlson은 그 사이다. 실제 고성능 덧셈기는 이 공간에서 공정과 배선 여유에 맞는 점을 고른다. 4비트마다 하나의 캐리만 계산하고 나머지는 캐리 선택으로 마무리하는 희소 트리(Sparse tree), 첫 단을 한 단 줄이는 Ling 덧셈기도 널리 쓰인다.

"단 수"는 지연의 일부일 뿐이다

표의 단 수는 모든 ∘ 셀이 같은 시간이 걸린다고 가정한다. 실제로는 팬아웃이 큰 셀이 느리고, 긴 배선은 RC 지연을 더하며, 셀 수가 많으면 전체가 커져 배선이 더 길어진다. 다음 절의 비교 시뮬레이터는 이 효과를 간단한 모델로 넣어 본다.

덧셈기 비교: 지연 대 면적

지금까지 본 구조를 한자리에 놓아 보자. 가로축은 지연, 세로축은 면적이다. 왼쪽 아래로 갈수록 좋다. 어느 구조도 두 축에서 동시에 최고는 아니다. 좋은 구조들은 파레토 경계(Pareto frontier) 위에 늘어서고, 설계자는 목표 클럭과 면적 예산에 맞춰 그 경계 위의 한 점을 고른다.

SIMULATOR

덧셈기 구조 비교

비트 폭 N (산점도)

지연 모델

강조할 구조

가장 빠른 구조—

가장 작은 구조—

파레토 경계 위—

FO4 환산 (가장 빠른 것)—

교육용 근사 모델. 지연 단위는 ∘ 셀(또는 캐리 한 단) 하나 = 1. "단 수만": 접두사 구조는 $2 + $단 수($g,p$ 생성과 합 XOR 포함), 건너뛰기·선택은 최적 블록 크기에서 위 절의 식, CLA는 4비트 블록 트리로 각 단 1.5. "팬아웃·배선 반영": 각 단 지연을 $1 + 0.25\log_2(\text{팬아웃}) + 0.02\times$(그 단 최장 배선, 비트 피치)로 늘리고 나머지 구조는 1.25배. 면적은 ∘ 셀 등가(접두사는 셀 수, RCA $N-1$, 건너뛰기 $N-1+1.5N/k$, 선택 약 $2.5N$, CLA 약 $2N$). FO4 환산은 단위 지연 × 0.8.

두 그래프에서 읽을 것은 세 가지다. 첫째, 리플 캐리는 $N$, 건너뛰기·선택은 $\sqrt N$, CLA와 접두사 구조는 $\log N$으로 자란다. 오른쪽 그래프의 기울기가 그 차수다. 둘째, $N$이 16 이하로 작으면 차이가 크지 않아 작은 구조가 합리적이다. 셋째, 64비트 이상에서는 $\log N$ 구조가 아니면 한 사이클에 넣기 어렵다. 고성능 CPU의 정수 덧셈기가 거의 모두 접두사 구조의 변형인 이유다.

뺄셈과 오버플로

덧셈기가 있으면 뺄셈기는 거의 공짜다. 2의 보수(Two's complement)에서 $-B = \overline{B} + 1$이므로, B의 모든 비트를 반전(XOR 게이트에 "빼기" 신호를 넣으면 된다)하고 캐리 입력에 1을 넣으면 된다.

$$ A - B = A + \overline{B} + 1, \qquad V = c_N \oplus c_{N-1} $$

$\overline{B}$: B의 비트별 반전, $+1$: $C_{in}=1$로 넣는다. $V$: 부호 있는 오버플로. 최상위 비트(부호 비트)로 들어가는 캐리 $c_{N-1}$과 나오는 캐리 $c_N$이 다르면 결과가 $N$비트 부호 있는 범위 $[-2^{N-1}, 2^{N-1}-1]$를 벗어났다는 뜻이다. 부호 없는 오버플로는 따로, 덧셈에서는 $c_N = 1$, 뺄셈에서는 $c_N = 0$(빌림)이다.

A B

수학적 결과—

8비트 결과 (부호 있는)—

V = c₈ ⊕ c₇—

캐리 c₈ (부호 없는 해석)—

그림 11-7. 해 보기8비트 부호 있는 정수 두 개를 고른다. 맨 위 줄은 각 자리로 들어가는 캐리, 왼쪽 끝 열은 부호 비트(비트 7)다. 100 + 50처럼 양수끼리 더해 127을 넘기면 부호 비트로 캐리가 들어가지만($c_7=1$) 나오지는 않아($c_8=0$) $V=1$이 된다. 뺄셈으로 바꾸면 B 줄이 $\overline{B}$로 바뀌고 오른쪽 끝에 $C_{in}=1$이 들어간다.

오버플로 규칙을 말로 하면 단순하다. 부호가 같은 두 수를 더했는데 결과의 부호가 다르면 오버플로다. 부호가 다른 두 수의 덧셈은 절대 넘치지 않는다. $c_N \oplus c_{N-1}$은 이 규칙을 게이트 하나로 계산한 것이다. 같은 덧셈기 출력을 부호 없는 수로 읽을지, 부호 있는 수로 읽을지는 회로가 아니라 명령어가 정한다. 그래서 ALU는 두 종류의 플래그 $C$(캐리)와 $V$(오버플로)를 함께 낸다. 비교 명령은 뺄셈을 하고 결과는 버린 채 이 플래그와 영(Z), 부호(N) 플래그만 남긴다(12장).

포화 산술

신호 처리나 신경망 가속기에서는 오버플로가 났을 때 값을 감아 돌리지(wrap) 않고 최댓값·최솟값에 붙잡는 포화(Saturation) 산술을 자주 쓴다. 100 + 50이 −106이 되는 대신 127로 멈추면 소리가 "딱" 하고 튀지 않는다. 회로는 $V$와 부호 비트로 MUX를 하나 더 두면 된다.

실제 수치: 덧셈 한 번은 한 사이클

최신 CPU에서 정수 덧셈은 1사이클 명령이고, 결과는 다음 사이클의 명령이 바로 쓴다(바이패스). 그러니 덧셈기 하나에 바이패스 MUX와 배선까지 더한 루프가 한 클럭 주기 안에 들어와야 한다. 이 "ALU + 바이패스 루프"는 고성능 코어의 대표적인 임계 루프다.

항목	대략값	비고
64비트 고속 덧셈기 지연	약 7~10 FO4	병렬 접두사(희소 트리, Ling 등), 동적 논리면 더 짧다
같은 덧셈기, DG-7 환산	약 50~75 ps	FO4 ≈ 7.5 ps
64비트 리플 캐리 덧셈기	약 60 FO4 이상	DG-7에서 약 450 ps 이상, 2 GHz 주기에도 못 들어간다
5 GHz 클럭 한 주기	200 ps ≈ DG-7 약 27 FO4	2020년대 데스크톱 CPU는 약 5~6 GHz(부스트)
고성능 코어 한 사이클의 논리 깊이	약 15~25 FO4	2000년대 중반 이후. 플립플롭 오버헤드 약 2~4 FO4 포함
Pentium 4 (약 2000년)	코어 클럭 2배로 도는 ALU	16비트씩 나눠 반 사이클마다 계산하는 "double-pumped" ALU

클럭 주파수

클럭 주기—

덧셈기—

여유—

판정—

그림 11-8. 해 보기클럭을 올리면서 덧셈 루프가 한 주기(점선 상자)에 들어가는지 보자. 막대는 플립플롭 오버헤드(clk→Q + setup, 약 3 FO4), 덧셈기(비교 시뮬레이터의 팬아웃 모델을 FO4로 환산), 바이패스 MUX·배선(약 3 FO4), 클럭 스큐·지터 여유(약 1.5 FO4)를 차례로 쌓은 것이다. DG-7 기준 FO4 = 7.5 ps. 넘치면 덧셈을 두 사이클로 나누거나 파이프라인 단을 하나 더 넣어야 한다.

덧셈기 너머: 캐리를 아예 미루기

여러 수를 연달아 더할 때는 매번 캐리를 끝까지 전파할 필요가 없다. 캐리를 따로 한 줄로 저장해 두는 캐리 저장(Carry-save) 표현을 쓰면 전가산기 한 단(3입력 → 2출력)만으로 세 수를 두 수로 줄일 수 있고, 마지막에 한 번만 빠른 덧셈기를 쓴다. 곱셈기의 월리스 트리가 이 원리다. 다음 장 곱셈기·시프터·ALU에서 이어진다.

핵심 정리

전가산기는 $S = A\oplus B\oplus C_{in}$, $C_{out} = \mathrm{MAJ}(A,B,C_{in})$이다. 실제 셀은 28트랜지스터 미러 가산기처럼 캐리 경로를 짧게 만든다.
자리마다 생성 $g=ab$, 전파 $p=a\oplus b$, 소멸 중 하나이고 $c_{i+1} = g_i + p_i c_i$다. 캐리가 기다리는 곳은 P 자리뿐이다.
리플 캐리 덧셈기는 가장 작지만 최악 입력(0111…1 + 1)에서 지연이 $N$에 비례한다. 동기 회로는 평균이 아니라 최악에 맞춘다.
캐리 예측은 블록 $(G,P)$를 미리 계산해 트리로 쌓는다. 캐리 건너뛰기·선택은 블록 크기 $\sqrt N$ 근처에서 지연 $\propto\sqrt N$을 얻는다.
(G,P) 결합 연산자 ∘는 결합 법칙을 따르므로 모든 캐리를 $\log_2 N$단 트리로 동시에 구할 수 있다. 이것이 병렬 접두사 덧셈기다.
Kogge–Stone(단·팬아웃 최소, 배선 최대), Sklansky(팬아웃 큼), Brent–Kung(셀 최소, 단 2배), Han–Carlson(절충)은 단 수·팬아웃·배선의 맞바꿈이다.
뺄셈은 $A+\overline B+1$, 부호 있는 오버플로는 $c_N\oplus c_{N-1}$이다. 64비트 고속 덧셈기는 약 7~10 FO4로 한 사이클 안에 든다.

확인 퀴즈

Q1. 전가산기의 캐리 출력 $C_{out}$과 같은 식은?

세 입력 중 두 개 이상이 1이면 캐리가 나는 다수결 함수다. $AB + C_{in}(A\oplus B)$와 같은 함수다. 첫 번째 보기는 합 $S$다.

Q2. 16비트 리플 캐리 덧셈기에서 합의 최상위 비트가 가장 늦게 확정되는 입력은?

0x7FFF + 0x0001에서 비트 0은 G, 비트 1~14는 P라서 캐리가 비트 0에서 비트 15까지 한 칸씩 전파된다. 0xFFFF + 0xFFFF는 모든 자리가 G라서 캐리가 즉시 확정되고, 0x5555 + 0x5555도 모든 자리가 G 또는 K다.

Q3. 64비트 Kogge–Stone 덧셈기의 접두사 네트워크는 몇 단인가?

Kogge–Stone은 단마다 결합 거리를 1, 2, 4, …로 두 배씩 늘리므로 $\log_2 64 = 6$단이다. 11단은 Brent–Kung($2\log_2N-1$), 63단은 직렬 리플이다.

Q4. 모든 단위 지연을 같게 둘 때, 균일 블록 캐리 선택 덧셈기의 지연을 최소로 하는 블록 크기 $k$는 대략?

$t \approx k + N/k + 1$은 $k=\sqrt N$에서 최소이고 그때 지연은 약 $2\sqrt N$이다. 캐리 건너뛰기는 블록 안 리플이 두 번이라 $k=\sqrt{N/2}$다.

Q5. 8비트 부호 있는 덧셈 100 + 50의 결과에 대한 설명으로 옳은 것은?

150은 8비트 부호 있는 범위(−128~127)를 넘는다. 비트 7로 캐리가 들어가지만 나오지 않으므로 $V = c_8\oplus c_7 = 1$이고, 비트 패턴 10010110은 −106이다. $c_8$만으로는 부호 있는 오버플로를 알 수 없다.

Q6. Brent–Kung 구조를 Kogge–Stone과 비교한 설명으로 옳은 것은?

Brent–Kung은 트리를 올라갔다 내려오며 $2N-2-\log_2N$개 셀만 쓰지만 $2\log_2N-1$단이다. 팬아웃이 큰 것은 Sklansky다. 어느 구조든 ∘의 결합 법칙 덕분에 결과는 같다.

구조	단 수	∘ 셀 수	최대 팬아웃	64비트 (단 / 셀 / 팬아웃 / 총 배선)	성격
직렬(리플)	\(N-1\)	\(N-1\)	2	63 / 63 / 2 / 63	가장 작고 가장 느림
Sklansky (1960)	\(\log_2 N\)	\(\tfrac{N}{2}\log_2 N\)	\(\tfrac{N}{2}+1\)	6 / 192 / 33 / 1104	분할 정복. 단 수 최소지만 팬아웃이 크다
Kogge–Stone (1973)	\(\log_2 N\)	\(N\log_2 N - N + 1\)	2	6 / 321 / 2 / 2667	단 수·팬아웃 최소, 셀과 배선이 가장 많다
Brent–Kung (1982)	\(2\log_2 N - 1\)	\(2N - 2 - \log_2 N\)	2	11 / 120 / 2 / 321	올라갔다 내려오는 트리. 작지만 단이 두 배
Han–Carlson (1987)	\(\log_2 N + 1\)	\(\tfrac{N}{2}\log_2 N\)	2	7 / 192 / 2 / 1365	홀수 비트만 Kogge–Stone, 마지막에 짝수 비트 한 단