Adder, Subtracter, Comparator

김민욱·2025년 6월 14일

RISC-V computer architecture

컴퓨터구조 - Computer Architecture(RISC-V)

목록 보기

1/11

Digital Building Block

게이트, 멀티플렉서, 디코더, 레지스터, 연산회로, 카운터, 메모리 배열, 논리 배열 등 디지털 시스템 설계의 기본 구성요소를 말한다.

Adder

먼저 1-bit adder를 살펴보자

Half-Adder

1-bit 이진수 두개 $(A, B)$ 를 입력 받아 합 $(S)$ 과 자리 올림 $(C_{out})$ 을 출력하는 회로이다.

| A  B | C_out  S |
|------|----------|
| 0  0 |   0    0 |
| 0  1 |   0    1 |
| 1  0 |   0    1 |
| 1  1 |   1    0 |

Boolean equation :
$S = A \oplus B$
$C_{out} = AB$

carry-in 처리가 불가능하기 때문에 실제 연산회로에서는 잘 사용되지 않는다.

Full adder

1-bit 이진수 두개 $(A, B)$ 와 이전 연산의 올림 $(C_{in})$ 을 입력으로 받아 합 $(S)$ 과 자리 올림 $(C_{out})$ 을 출력하는 회로이다. 우리가 주로 사용할 adder의 형태다.

| C_in  A  B | C_out  S |
|------------|----------|
|   0   0  0 |   0    0 |
|   0   0  1 |   0    1 |
|   0   1  0 |   0    1 |
|   0   1  1 |   1    0 |
|   1   0  0 |   0    1 |
|   1   0  1 |   1    0 |
|   1   1  0 |   1    0 |
|   1   1  1 |   1    1 |

Boolean equation :
$S=A\oplus B\oplus C_{in}$ (세 비트 중 1이 홀수 개이면 1)
$C_{out}=AB+AC_{in}+BC_{in}$ (세 비트 중 최소 2개가 1이면 1)

이 것이 adder 설계의 기본 구조이다. 이제 이를 1-bit에서 multibit으로 확장시켜보자.

Multibit Adder

multibit adder는 carry의 처리 방식에 따라 타입이 나뉜다.
간략하게 살펴보면 다음과 같다.

Ripple-carry (느림)
Carry-lookahead (빠름)
Prefix (더 빠름)

블록이 커질 수록 carry-lookahead adder와 prefix adder가 더 빠르게 작동하지만 그만큼 더 많은 하드웨어를 요구한다.

multibit adder의 심볼은 다음과 같다.

Ripple-Carry Adder
1-bit adder들을 연결하여 구현한다.

carry가 전체 체인을 타고 나아가기 때문에 Ripple-Carry라고 부른다.
구현이 쉽지만 느리다는 단점이 존재한다.

Ripple-Carry adder의 딜레이는 다음과 같이 계산된다.

$t_{ripple}=Nt_{FA}$

$N$ : adder 개수
$t_{FA}$ : 1-bit full adder의 딜레이

Carry-Lookahead Adder
$C_{out}$ 을 generate(생성)와 propagate(전파) 신호를 이용해 계산한다.
쉽게 생각하면 우리가 종이에 연필을 가지고 하는 덧셈 계산 방식과 유사하게 작동한다.

4-bit 이진수 두 개를 가지고 합 연산을 한다고 가정하자.
각 자리 수를 열로 생각할 때, 각 열은 올림을 생성하거나 전파 받을 수 있다.

Generate
$i$ 번째 열의 계산은 $A_i$ 와 $B_i$ 가 모두 1일 때 반드시 $C_{out}$ 을 "생성"한다.
$G_i=A_iB_i$
$G$ 계산에 $C_{in}$ 은 고려하지 않는다.
Propagate
$A_i$ 와 $B_i$ 중 적어도 하나가 1일 경우 $C_{in}$ 을 통해 들어온 carry를 $C_{out}$ 으로 "전파"한다.
$P_i=A_i+B_i$
Carry out
따라서 column $i$ 의 $C_{out}$ 은 다음과 같이 계산된다.
$C_i=G_i+P_iC_{i-1}$

두 4-bit 이진수 $A_{3:0} = 1011$ , $B_{3:0} = 0110$ 를 예시로 보면

 1011
+0110
-----
 0001

$P_3,P_2,P_1,P_0$ = 1,1,1,1
$G_3,G_2,G_1,G_0$ = 0,0,1,0
$C_3,C_2,C_1,C_0$ = 1,1,1,0

이제 이 계산을 열 단위가 아닌 블록 단위로 확장한다.

블록 하나의 크기가 4-bit일 때 Block propagate signal은 다음과 같다.
$P_{3:0}=P_3P_2P_1P_0$
앞서 든 예시에서 $P_{3:0}=1$ 이다.

블록에서 캐리는
column 3에서 생성(G)되거나,
column 2에서 생성된 후 column 3에 전파(P)되거나,
column 1에서 생성된 후 column 2와 3에 전파되거나,
column 0에서 생성된 후 column 1, 2, 3에 전파될 경우 발생한다.

$G_{3:0}=G_3+G_2P_3+G_1P_2P_3+G_0P_1P_2P_3$ ,
즉, $G_{3:0} = G_3+P_3\{G_2+P_2(G_1+G_0P_1)\}$ 이다.
앞서 든 예시에서 $G_{3:0}=1$ 이다.

이에 따라서 캐리는

$C_3=G_{3:0}+P_{3:0}C_{-1}$ 이다.

4-bit adder block을 이용해 32-bit 구현된 32-bit carry-lookahead adder는 다음과 같다.

모든 열에 대해 $G_i$ 와 $P_i$ 를 계산한다.
k-bit 블록에 대한 $G$ 와 $P$ 를 계산한다.
합 계산을 수행하는 동안 $C_{in}$ 이 k-bit의 전파/생성 로직을 통해 전파된다.
most significant k-bit에 대한 합을 계산한다.

$k$ -bit block으로 구성된 $N$ -bit carry-lookahead adder의 딜레이는 다음과 같이 계산된다.

$t_{CLA}=t_{pg}+t_{pg\_block}+(\frac{N}{k}-1)t_{AND\_OR}+kt_{FA}$

$t_{pg}$ : 모든 $P_i,\ G_i$ 를 구하는데 걸리는 시간
$t_{pg\_block}$ : 모든 $P_{i:j},\ G_{i:j}$ 를 구하는데 걸리는 시간
$t_{AND\_OR}$ : $k$ -bit block에 있는 마지막 AND/OR 게이트를 통과하는데 걸리는 시간

Prefix Adder
각 열의 $C_{in}(=C_{i-1})$ 을 계산한 후 다음과 같이 sum 한다.

$S_i=(A_i\oplus B_i)\oplus C_{i-1}$

$C_{i-1}$ 은 다음 식으로 알아낼 수 있다.

$C_i=G_{i-1}$

예: 4-bit block일 경우)
$C_3=G_{3:0}+P_{3:0}C_{-1}$

$G_{3:0}=G_3+G_2P_3+G_1P_2P_3+G_0P_1P_2P_3$
$P_{3:0}=P_3P_2P_1P_0$

$C_3=G_3+G_2P_3+G_1P_2P_3+G_0P_1P_2P_3 +P_3P_2P_1P_0C_{-1}$

$C_{-1}=G_{-1}$ 이므로
$C_3=G_3+G_2P_3+G_1P_2P_3+G_0P_1P_2P_3 +G_{-1}P_3P_2P_1P_0$

$\therefore C_3=G_{3:-1}$

$\log_2N$ 개의 단계를 통해 sum을 구할 수 있다.

column -1은 $C_{in}$ 을 갖고 있다. 그러므로
$G_{-1}=C_{in}$ , $P_{-1}=\mathsf X$ (not used)

column $i$ 의 $C_{in}$ 은 column $i-1$ 의 $C_{out}$ 이다.
$C_{i-1}=G_{i-1:-1}$

그 결과로 sum을 실행한다.
$S_i=(A_i\oplus B_i)\oplus G_{i-1:-1}$

따라서 이 계산법의 목표는 모든 block의 generate $(G_{0:-1},G_{1:-1},G_{2:-1},... = C_0, C_1,C_2,...)$ 를 빠르게 계산하는 것이다.

block generate/propagate 시그널은 하위 block의 시그널로 표현할 수 있음을 기억하자.
$G_{i:j}=G_{i:k}+P_{i:k}G_{k-1:j}$
$P_{i:j}=P_{i:k}P_{k-1:j}$

즉, block $i:j$ 는 상위 부분 $(i:k)$ 에서 carry $(G_{i:k})$ 를 생성하거나, 하위 부분 $(k-1:j)$ 에서 carry $(G_{k-1:j})$ 를 생성하고 상위 부분에서 전파 $(P_{i:k})$ 될 경우 generate signal $(G_{i:j})$ 을 발생시킨다.

또한 상위 부분과 하위 부분 모두 전파될 경우 $(P_{i:k}\ AND\ P_{k-1:j})$ propagate signal $(P_{i:j})$ 을 발생시킨다.

<prefix adder 예시>
$A=1010_2$ , $B=0111_2$

 1010
+0111
------
10001

$G_3,G_2,G_1,G_0,G_{-1}=0,0,1,0,0$
$P_3,P_2,P_1,P_0,P_{-1}=1,1,1,1,\mathsf X$

$G_{2:-1}=G_{2:1}+P_{2:1}G_{0:-1}$
$G_{2:1}=G_{2}+P_2G_{1} = 0+1\cdot 1=1$

$\therefore G_{2:-1}=1$

$G_{1:-1}=G_{1:0}+P_{1:0}G_{-1}$
$G_{1:0}=G_1+P_1G_0 =1+1\cdot 0=1$

$\therefore G_{1:-1}=1$

$G_{0:-1}=G_{0}+P_0G_{-1}=0+1\cdot 0=0$

$S_3=(A_3\oplus B_3)\oplus G_{2:-1}=(1\oplus 0)\oplus 1 = 1\oplus 1 = 0$
$S_2 = (A_2\oplus B_2)\oplus G_{1:-1}=(0\oplus1)\oplus1=1\oplus 1=0$
$S_1=(A_1\oplus B_1)\oplus G_{0:-1}=(1\oplus 1)\oplus 0=0\oplus 0=0$
$S_0=(A_0\oplus B_0)\oplus G_{-1}=(0\oplus 1)\oplus 0=1\oplus 0=1$

$\therefore S = 0001_2$

16-bit prefix adder는 다음과 같이 구현된다.

컴퓨터 알고리즘 중 분할정복과 비슷한 원리로 이해할 수 있다.(이건 하드웨어지만)

딜레이는 다음과 같다.

$t_{PA}=t_{pg}+\log_2N(t_{pg\_prefix})+t_{XOR}$

$t_{pg}$ : $P_i$ , $G_i$ 계산에 걸리는 시간
$t_{pg\_prefix}$ : 위 회로도에서 검은색으로 표시된 prefix 셀의 딜레이

이쯤에서 정리를 한 번 해보자.

Adder summary

1-bit adder

	Half adder	Full-adder
입력	A, B	A, B, Carry-in
출력	Sum, Carry-out	Sum, Carry-out

Full-Adder 설계 기본 구조

$S_i=A_i\oplus B_i \oplus C_{in}$
multibit adder

타입	방식	딜레이
Ripple-Carry	1-bit full adder를 직렬로 연결하여 carry를 순차적으로 전파	$t_{ripple}=Nt_{FA}$
Carry-Lookahead	각 자리의 P와 G 신호를 미리 계산하여 carry를 병렬로 처리	$t_{CLA}=t_{pg}+t_{pg\_block}+(\frac{N}{k}-1)t_{AND\_OR}+kt_{FA}$
Prefix	각 자리의 Carry-in을 prefix 셀로 빠르게 계산	$t_{PA}=t_{pg}+\log_2N(t_{pg\_prefix})+t_{XOR}$

$C_{in}$ 을 어떻게 계산하느냐에 차이가 있다.

딜레이 계산 예제
32-bit ripple-carry, CLA, prefix adder의 딜레이를 비교하여라.
<조건>
CLA는 4-bit block들로 구성되었다.
2-input 게이트들의 딜레이는 $100ps$ ,
full adder의 딜레이는 $300ps$ 이다.

$t_{ripple}=Nt_{FA}=32\times 300\ (ps)=9.6ns$

$t_{CLA}\\=t_{pg}+t_{pg\_block}+(\frac{N}{k}-1)t_{AND\_OR}+kt_{FA}\\=100+100\times 6+(\frac{32}{4}-1)\times100\times 2+4\times300\\=100+600+1400+1200\ (ps)=3.3ns$