prefix adder: 마지막 carry를 한 비트씩 기다리지 않는 방법

32비트 덧셈의 답은 한 줄로 쓸 수 있지만, 마지막 비트가 답을 알기까지는 앞쪽에서 만들어진 carry를 기다려야 한다. 모든 자릿수를 같은 방식으로 연결하면 그 기다림도 길어진다. prefix adder가 바꾸는 것은 덧셈의 규칙이 아니라 앞쪽 여러 비트가 carry에 미치는 영향을 묶어서 계산하는 순서다.

carry는 현재 자리의 합이 다음 자리로 넘기는 값이다. ripple 구조는 낮은 자리의 carry를 다음 자리에 차례로 전달한다. 병렬 prefix 구조는 구간별 정보를 트리처럼 합쳐, 먼 자리까지의 영향을 여러 단계로 계산한다.

한 자리의 정보를 두 비트로 요약하기

입력 비트 a_i와 b_i에 대해 generate와 propagate를 정의하자.

g_i = a_i AND b_i

p_i = a_i XOR b_i

둘 다 1이면 입력 carry와 무관하게 다음 자리 carry를 만든다. 둘 중 하나만 1이면 들어온 carry를 다음 자리로 전달한다. 둘 다 0이면 carry를 막는다. 그래서 다음 carry는 c_(i+1) = g_i OR (p_i AND c_i)로 표현된다.

예를 들어 4비트 unsigned 값 7과 9를 더하면 a=0111, b=1001이다. bit0는 두 입력이 모두 1이므로 carry를 만들고, bit1부터 bit3까지는 그 carry를 전달한다. 결과는 carry-out=1, 아래 4비트=0000이다. 가장 높은 자리의 결과가 낮은 자리의 사건과 연결되는 예다.

구간끼리 합치면 같은 규칙이 반복된다

높은 구간 H와 낮은 구간 L의 요약을 각각 (G_H,P_H), (G_L,P_L)로 적자. 전체 구간은 다음처럼 합쳐진다.

G = G_H OR (P_H AND G_L)

P = P_H AND P_L

높은 구간이 스스로 carry를 만들거나, 높은 구간이 낮은 구간의 carry를 통과시키면 전체도 carry를 만든다. 전체가 들어온 carry를 끝까지 통과시키려면 두 구간 모두 통과시켜야 한다. 이 합성은 구간을 어떻게 괄호로 묶어도 같은 결과를 내므로 트리 구조로 계산할 수 있다.

8비트를 생각하면 각 자리의 요약을 먼저 만들고, 길이 2의 구간, 길이 4의 구간, 길이 8의 구간 정보를 병렬로 묶을 수 있다. 구간 크기가 두 배씩 늘어나는 것이 직렬 전달과의 차이다. 다만 모든 자리의 prefix를 만드는 전체 네트워크의 단계 수는 선택한 topology에 따라 달라진다. 이 세 번의 구간 확대를 특정 8비트 adder 전체의 물리 지연으로 읽으면 안 된다.

Yosys의 공개 기술 매핑 코드는 $lcu를 Brent–Kung 형태의 prefix 네트워크로 낮추는 사례를 보여 준다. 원문의 main tree와 inverse tree에서 구간 propagate·generate를 합치고, 각 위치의 carry를 만든다. 회로 이름보다 이 구간 합성 관계를 보면 병렬화 대상이 분명해진다.

적은 논리 단계가 곧 가장 짧은 배선은 아니다

prefix 방식은 긴 carry 의존을 줄이는 대신 여러 비트 사이의 연결을 늘린다. topology에 따라 노드 수, fan-out, 긴 배선의 수와 논리 깊이가 달라진다. 어떤 구조는 더 많은 prefix 정보를 빨리 만들지만 배선 부하와 혼잡을 지불한다. 다른 구조는 노드를 줄이면서 일부 위치의 계산 단계를 더 거친다.

그래서 같은 폭에서도 배치·배선 이후의 승자는 달라질 수 있다. 게이트 지연만 더한 비교와 실제 배선 부하를 포함한 비교가 서로 다른 답을 낼 수 있다. 입력 도착 시간도 중요하다. 상위 비트가 늦게 도착하는 조건에서 균일 입력 도착을 가정한 최적 topology가 그대로 유리하다고 보장할 수 없다.

출력 전체가 필요한지도 확인해야 한다. 낮은 일부 비트만 쓰는 회로라면 높은 carry를 빠르게 만드는 데 지불한 비용이 필요 없을 수 있다. carry-out이 버려지는 덧셈과 전체 확장 합을 구하는 덧셈은 기능 요구부터 다르다.

코드가 prefix 구조를 약속하지는 않는다

RTL의 sum = a + b는 산술 의미를 표현한다. 합성 도구가 어떤 구조로 구현하는지는 목표 기술, 제약과 최적화에 달려 있다. 일반 매핑에서 prefix 네트워크를 사용하더라도 FPGA의 전용 carry 자원이 더 적합할 수 있다. 직접 prefix 논리를 쓰면 의도한 구조가 보존되는지, 도구의 산술 인식에 어떤 영향을 주는지도 살펴야 한다.

비교할 때는 같은 폭·부호·결과 비트와 같은 입력·출력 timing을 두고 기능 동치를 확인한다. 이후 배치·배선된 임계 경로, 면적과 소비 전력을 함께 본다. 넓은 덧셈에서 prefix가 왜 유력한 선택인지는 논리로 설명할 수 있지만, 특정 라이브러리에서 얼마나 빠른지는 구현 결과가 필요하다.

덧셈기의 마지막 비트가 기다리는 이유는 carry의 의미 때문이다. prefix adder는 그 의미를 구간의 요약으로 옮겨 직렬 기다림을 줄인다. 좋은 prefix 구조의 기준은 가장 유명한 이름이 아니라, 필요한 carry를 어떤 깊이와 연결 비용으로 만들었는가다. 이 관점으로 보면 덧셈 RTL의 한 줄 뒤에서 실제로 비교해야 할 회로가 드러난다.