가산기(Carry-lookahead Adder) 구조

가산기

CPU의 연산처리과정을 익혀보던 중 그 흔한 덧셈을 과연 어떻게 최적화를 시켰을까 궁금해서 찾아보게 되었다.

가산기는 간단히 말하면 두 수의 덧셈을 연산하는 논리회로이다. 반가산기(half adder), 전가산기(full adder), RCA(ripple carry adder)는 익숙하지 않은 사람이 회로만 봐도 이해가 가능할 정도로 상당히 간결하다.

반가산기	전가산기	RCA

출처 : wikipedia

 

간단히 정리하면 반가산기는 입력으로 두 개의 bit가 주어질 때 S(sum)과 C(carry) bit를 구한다.

전가산기는 반가산기에 carry bit까지 입력으로 들어올 때를 구현했고, RCA는 이런 전가산기를 여러 bit에서 연산 가능하도록 조합한 형태이다.

 

Ripple carry adder로 가산기를 만들었다고 치고 32bit 덧셈을 하는데 몇 개의 논리게이트를 통과하는지 생각해보자.

 

1bit의 Full Adder를 연산하는데 2단의 논리게이트를 통과하고, 자리올림을 확인하기 위해 첫째 자리부터 순차적으로 계산한다고 하면 32x2 = 64개의 게이트를 통과해야 한다. 게다가 마지막 자리의 carry가 있을 경우 추가 게이트가 필요하므로 적어도 65개 이상의 게이트를 통과한다고 볼 수 있다.

 

1차원적으로만 생각해보면 자리올림(carry)이 이전 자릿수의 결괏값에 의존적이기 때문에 병목지점이고, 이 자리올림 문제를 효율적으로 처리해야겠다는 생각까지 도달할 수 있다. 곧 생각의 흐름이 자리올림을 예측(CLA, Carry-lookahead adder)하는 방향으로 나아가야 한다는 것을 알 수 있다.

 

CLA, Carry-lookahead adder

자리올림을 예측해보기 위해 다음과 같이 Generate와 Propagate라는 함수를 정의한다.

 

$ G(A,B) = A ∧ B (AND) $

-> 이전의 결괏값과 상관없이 자리올림이 발생하는지 여부

$ P(A,B) = A ⊻ B (XOR) $

-> 이전의 결괏값에 따라 자리올림이 발생할 가능성이 있는지 여부

 

그럼 이제 $S$(sum)과 $C$(carry)를 구해보자.

$$ S_{i} = P_{i} ⊻ C_{i} \\
C_{i+1} = G_{i} ∨ (P_{i} ∧ C_{i})$$

위 식에서 볼 수 있듯이 이전 결괏값을 기다리던 $C_{i}$의 식을 재귀적으로 풀면 $G$와 $P$에 관한 식으로 나타낼 수 있다.

$G$와 $P$는 식에서 알 수 있듯이 각 bit에 독립적이기 때문에 한 번에 연산이 가능하다. $C_{i}$를 이전 결괏값에 의존적이지 않게 구할 수 있다는 것 까지는 이제 납득이 간다.

 

하지만 재귀적으로 Ci를 풀어보면 G와 P로 이루어진 꽤나 긴 식이 나오는데 이게 더 오래 걸리는 게 아닐까?

여기서 BIT(Binary Indexed Tree)의 개념을 가져오면 빠르게 구할 수 있다.

 

$i$를 $2^{x}$라고 할 때,

$$ G_{i,i+2x} = G_{i+x,i+2x} ∨ (G_{i,i+x} ∧ P_{i+x,i+2x}) \\
P_{i,i+2x} = P_{i+x,i+2x} ∧ P_{i,i+x} $$

위와 같이 구간을 확대해 나가면서 $G$, $P$값을 구하면 32bit 기준으로 $O(log_{2}32)$ 깊이의 논리게이트를 사용해서 모든 $G$와 $P$를 구할 수 있다. (마지막 자리 연산 등의 이유로 몇 개가 더 필요하긴 하다) 이로써 덧셈에 필요한 모든 값들을 구했고 원하는 결괏값인 $S_{i}$를 구할 수 있다!

 

마무리

CLA는 기존의 RCA보다 논리게이트는 더 많이 필요하지만 $i+1$번째를 구하기 위해 $i$번째 결과를 기다리는 짓은 안 해도 된다. 32bit의 덧셈의 경우에도 문제의 $C$를 구하는데 20개 내외의 논리게이트를 사용하므로 CPU의 cycle time을 단축시킬 수 있다.

 

회로도까지 깊숙이 내려가서 생각할 일은 별로 없지만 이전 결괏값에 의존적인 n-bit연산을 빠르게 구하는 방법에 대한 포인트는 인상적이다.

1. 자리올림을 위해 이전 결괏값을 기다리지 않도록 식을 세운다.
2. 그 식을 빠르게 구한다.