데이터패스 연산 유닛: 배럴 시프터, 비교기, 곱셈기 설계

3장 Datapath Functional Units 개요

프로세서의 Datapath를 구성하는 주요 기능 유닛(Functional Unit)들을 학습한다. Shifter, Comparator, Multiplier, Divider, Counter 등 ALU 내부의 핵심 구성 요소와 그 설계 기법을 다룬다.

Shifter (시프터)

Shift 연산은 곱셈·나눗셈의 빠른 근사와 비트 조작에 필수. 주요 종류:

• Logical shift (LSL, LSR): 0으로 채움
• Arithmetic shift (ASL, ASR): sign bit 유지 (signed division)
• Rotate (ROL, ROR): 순환
• Rotate through carry: carry bit 포함 순환

Barrel Shifter

n-bit 시프터를 1 cycle 내에 임의 shift 횟수로 처리. ARM의 특징적 유닛.

• MUX tree 구조: log n 단계
• 8-bit, 16-bit, 32-bit … 각 단계에서 shift 또는 통과
• Area: O(n log n), Delay: O(log n)

Comparator (비교기)

두 수 A, B를 비교해 A=B, A>B, A<B를 판정.

Equality Comparator

$A = B \iff \text{XNOR}(a_i, b_i) = 1 \text{ for all } i$

즉 각 bit XNOR → AND로 결합.

Magnitude Comparator

• Cascaded: 상위 bit부터 비교, 같으면 다음 bit로
• Parallel: 각 bit 쌍 비교 후 priority encoder

Multiplier (곱셈기)

Array Multiplier

각 partial product를 병렬로 생성 후 adder tree로 합산:

   A3 A2 A1 A0
×  B3 B2 B1 B0
───────────────
partial products 4개
   →  shift + add

지연 O(n), 면적 O(n²).

Booth Encoding

Signed 곱셈에서 연속된 1 bit를 묶어 partial product 수를 줄임.

• Booth-2 (radix-4): 3-bit씩 묶어 partial product가 절반
• Booth-4 (radix-8): 4-bit씩 묶어 partial product가 1/3

Wallace Tree Multiplier

Partial product들을 CSA (Carry Save Adder)로 줄이는 reduction tree:

• Depth = $O(\log n)$
• 최종 2개의 수를 CPA로 합산
• 현대 CPU의 정수 multiplier 표준

Dadda Tree

Wallace와 유사하지만 adder 개수가 약간 적음. 면적 더 효율적.

Divider (나눗셈기)

나눗셈은 곱셈보다 훨씬 복잡.

Restoring Division

• 뺄셈 후 결과가 음수면 원상 복구(restore)
• n-bit division: n cycle

Non-Restoring Division

• 원상 복구 없이 부호에 따라 다음 연산 결정
• 더 빠름, 현대 일반적 구현

SRT Division

• Redundant digit set (−2, −1, 0, +1, +2)
• Radix-4, Radix-8 SRT divider → cycle 수 감소
• Intel Pentium의 유명한 FDIV bug가 SRT lookup table 오류

Counter

• Binary counter: n-bit ripple counter
• Synchronous counter: 모든 flip-flop에 같은 clock → skew 적음, high freq 가능
• Johnson counter, Ring counter: 시프트 레지스터 기반

Multiplexer / Demultiplexer

• 2:1 MUX y </u></strong></mark> s·b + s̄·a (AOI gate)
• n:1 MUX는 log n 선택 신호
• 대규모 MUX는 tree 구조로 분해