2. Adder

2장 Adder 개요

덧셈기(Adder) 는 모든 산술 연산의 기초이자 프로세서 datapath의 핵심이다. 본 노트에서는 Half Adder, Full Adder부터 시작해 Carry chain, Carry Lookahead, Carry Select 등 고속 덧셈기 구조들을 정리한다.

Half Adder (반가산기)

두 개의 1-bit 입력 A, B → sum S와 carry C:

• $S = A \oplus B$
• $C = A \cdot B$

Full Adder (전가산기)

세 개의 1-bit 입력 A, B, Cin → S, Cout:

• $S = A \oplus B \oplus C_{in}$
• $C_{out} = AB + (A \oplus B) \cdot C_{in} = AB + AC_{in} + BC_{in}$

Propagate & Generate

Carry Lookahead의 기반 개념:

• Generate: $G = A \cdot B$ (항상 carry 발생)
• Propagate: $P = A \oplus B$ (carry 통과)
• Cout = $G + P \cdot C_{in}$

Full Adder Design — Transistor Level

• Cout: $(A+B) \cdot C_{in} + A \cdot B$ → 5~6 Transistor 구조
• S: XOR 기반 → 10~12 Transistor
• Inverting logic: NAND/NOR만 사용해 면적·지연 최적화

Ripple Carry Adder (RCA)

n-bit Full Adder를 순차적으로 연결:

  A0,B0      A1,B1      A2,B2
    │          │          │
 [FA0]─C1→[FA1]─C2→[FA2]─C3→
    │          │          │
   S0         S1         S2

지연

• Carry propagation: $n$-bit 모두 통과 → O(n) 지연
• Worst case: $t = n \times t_{FA}$ → 32-bit에서는 매우 느림

Carry Lookahead Adder (CLA)

모든 bit의 carry를 병렬로 미리 계산:

$$C_{i+1} = G_i + P_i \cdot C_i$$

전개: $$C_4 = G_3 + P_3 G_2 + P_3 P_2 G_1 + P_3 P_2 P_1 G_0 + P_3 P_2 P_1 P_0 C_0$$

→ 각 carry를 O(log n) 지연에 계산 가능.

Block Carry Lookahead

CLA를 4-bit block 단위로 묶고, block 간 carry를 또 lookahead로 계산. Hierarchical CLA.

• 4-bit group → 16-bit CLA → 64-bit CLA 계층
• 각 level에서 log 시간 → 전체 $O(\log n)$

Manchester Carry Chain

CMOS pass transistor로 carry chain을 구현:

• Propagate는 pass transistor로 carry를 넘김
• Generate는 pull-down으로 직접 생성

Carry Skip Adder

RCA를 k-bit block으로 나누고, 블록 내 모든 bit가 propagate=1이면 block 전체를 carry가 skip (우회):

• Block 내: ripple
• Block 경계: MUX로 skip

성능: $O(\sqrt{n})$ 지연, 면적 효율적.

Carry Select Adder

각 블록을 Cin=0, Cin=1 두 가지 경우에 대해 동시에 계산 → 실제 Cin이 도착하면 MUX로 선택.

• 면적 ↑, but 지연 ↓
• 32-bit adder에서 자주 쓰임

Conditional Sum Adder

Carry Select의 재귀 버전. 상위 block도 재귀적으로 선택. 지연 $O(\log n)$.

Brent-Kung / Kogge-Stone Prefix Adder

Prefix tree를 이용해 모든 carry를 병렬로 계산. Parallel prefix adder.

• Brent-Kung: depth = 2log n, 면적 적음
• Kogge-Stone: depth = log n, 면적 큼, 가장 빠름
• Ladner-Fischer, Han-Carlson: 중간 tradeoff

CPU의 고성능 datapath adder는 대부분 Kogge-Stone 또는 변형.

Pipelined Adder

긴 n-bit adder를 여러 단계로 pipeline. Throughput ↑, latency ↑.

Subtraction (Two's Complement)

$A - B = A + \bar{B} + 1$ (두 번째 complement). Adder + XOR gate + Cin=1로 구현.

Multi-Operand Addition

3개 이상의 수 덧셈: CSA (Carry Save Adder) tree로 각 bit 위치의 partial sum을 reduce, 마지막에 CPA.

Saturation Arithmetic

오버플로 시 포화(saturate) — MAX 또는 MIN 값으로 클램프. DSP/Multimedia에서 중요.

Floating-Point Adder

• Align exponents (shift larger 값에 맞춤)
• Add mantissas
• Normalize 결과 (shift, adjust exponent)
• Round

단계별 복잡도가 높아 pipelined FP adder가 필수.

정리

프로세서의 datapath 성능은 adder의 지연이 결정한다. 현대 CPU의 ALU는 대부분 parallel prefix adder (Kogge-Stone 변형) + pipelining을 사용.