캐리 예측 가산기: 리플 캐리보다 빠른 이유

캐리 예측 가산기는 전파 및 생성 신호로 캐리 생성을 재구성합니다. 4비트 CLA를 유도하고 실제 설계가 계층 구조를 쓰는 이유를 알아보세요.

Denny

2026년 5월 7일약 7분 소요

Chalkboard feature illustration for “캐리 예측 가산기: 리플 캐리보다 빠른 이유”

요약: 캐리 예측은 직렬 점화식 $C_{i+1}=G_i+P_iC_i$ 를 비트별 및 그룹별 생성/전파 신호로 다시 씁니다. 작은 평면 CLA는 피연산자에서 여러 캐리를 직접 표현할 수 있습니다. 계층형 및 병렬 접두사 방식은 추가 셀, 팬아웃, 배선이라는 대가로 캐리 깊이를 선형에서 로그 방향으로 줄입니다.

4비트 리플 캐리 가산기는 간단합니다. 전가산기 네 개를 연결하고 각 $C_{out}$ 을 다음 $C_{in}$ 으로 보냅니다. 최악 조건의 캐리 의존성은 워드 폭에 따라 커집니다. 그 경로가 타이밍을 만족하는지는 기술, 목표 클록, 셀 설계, 주변 데이터패스에 달려 있으므로 폭만으로 설계가 ‘받아들일 수 없다’고 할 수는 없습니다.

캐리 예측 가산기(CLA)는 피연산자에서 바로 얻을 수 있는 중간 신호로 캐리 식을 유도해 이 직렬 의존성을 해결합니다.

리플 캐리가 느린 이유

전가산기 식을 다시 보겠습니다.

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

합 $S_i$ 는 $C_i$ 에 의존합니다. 캐리 $C_{i+1}$ 도 $C_i$ 에 의존합니다. 따라서 의존성 사슬은 $C_0 \to C_1 \to C_2 \to \dots \to C_n$ 입니다. 캐리 단계 하나에 $t_c$ 시간이 걸리면 최악 조건의 전체 덧셈 시간은 대략 다음과 같습니다.

$T_{ripple} \approx n \cdot t_c + t_{sum}$

1차 의존성은 워드 폭에 대해 선형입니다. 절대 나노초 값에는 특정 구현이 필요하므로, 여기서 게이트 지연 수는 토폴로지를 비교하는 데만 유용합니다. 이는 더 빠른 캐리 네트워크를 만들게 하는 전파 지연 한계입니다.

생성과 전파

캐리 식을 다시 살펴봅시다.

$C_{i+1} = A_i B_i + (A_i \oplus B_i) C_i$

첫 항 $A_i B_i$ 는 두 피연산자 비트가 모두 1일 때 정확히 참입니다. 이때 단계 $i$ 는 $C_i$ 에 무엇이 들어오든 캐리 출력을 무조건 만듭니다. 다음과 같이 정의합니다.

$G_i = A_i \cdot B_i$

이는 생성(generate) 신호입니다. 단계 $i$ 가 스스로 캐리를 생성합니다.

둘째 항 $(A_i \oplus B_i) C_i$ 는 피연산자 비트 중 정확히 하나가 1이면 $C_i$ 에 도착한 값이 그대로 통과한다는 뜻입니다. 다음과 같이 정의합니다.

$P_i = A_i \oplus B_i$

이는 전파(propagate) 신호입니다. 단계 $i$ 가 들어오는 모든 캐리를 출력으로 전달합니다.

캐리 식은 다음으로 간결해집니다.

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

이는 이미 알고 있는 AND 게이트와 OR 게이트가 진리표에 따른 일을 정확히 수행하는 것입니다. 다만 이제는 평탄화할 수 있는 점화식으로 결합되어 있습니다.

캐리 점화식 평탄화하기

점화식을 그 자체에 대입합니다. 알려진 $C_0$ 에서 시작하면 다음과 같습니다.

$C_1 = G_0 + P_0 C_0$

$C_2 = G_1 + P_1 C_1 = G_1 + P_1(G_0 + P_0 C_0) = G_1 + P_1 G_0 + P_1 P_0 C_0$

$C_3 = G_2 + P_2 C_2 = G_2 + P_2 G_1 + P_2 P_1 G_0 + P_2 P_1 P_0 C_0$

$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$

패턴은 명확합니다. 각 캐리 $C_{i+1}$ 은 단계 0부터 $i$ 까지의 생성 및 전파 신호에 대한 곱의 합입니다. 논리적으로 모든 식은 앞선 전가산기의 물리 전이가 완료되는 것 대신 $G$ , $P$ , $C_0$ 에만 의존합니다. 물리적으로는 넓은 곱 항과 배선에도 유한한 게이트, 버퍼, 배선이 필요합니다.

4비트 계산 예제

$C_0=0$ 에서 $A=1011_2$ (11)과 $B=0110_2$ (6)을 더합니다. 비트는 최하위부터 씁니다.

비트 $i$	$A_i$	$B_i$	$P_i=A_i\oplus B_i$	$G_i=A_iB_i$	$C_i$	$S_i=P_i\oplus C_i$
0	1	0	1	0	0	1
1	1	1	0	1	0	0
2	0	1	1	0	1	0
3	1	0	1	0	1	0

캐리 식은 $C_1=0$ , $C_2=1$ , $C_3=1$ , $C_4=1$ 을 줍니다. $C_4S_3S_2S_1S_0$ 를 읽으면 예상대로 $10001_2=17$ 입니다. 산술은 리플 캐리와 같으며, 달라지는 것은 캐리 네트워크의 토폴로지뿐입니다.

그룹 생성과 전파

비트 $i$ 부터 $j$ 까지의 그룹에 대해 그룹 전파와 그룹 생성을 정의합니다.

$P_{j:i}=P_jP_{j-1}\cdots P_i$

$G_{j:i}=G_j+P_jG_{j-1}+\cdots+P_jP_{j-1}\cdots P_{i+1}G_i$

그러면 그룹을 나가는 캐리는 다음과 같습니다.

$C_{j+1}=G_{j:i}+P_{j:i}C_i$

인접한 두 그룹은 같은 연산으로 결합할 수 있습니다.

(G_H,P_H)\circ(G_L,P_L) = (G_H+P_HG_L,\;P_HP_L)

이 결합 법칙이 계층형 및 병렬 접두사 가산기의 핵심입니다. 쌍을 결합하고 다시 쌍의 쌍을 결합하여 직렬 사슬 대신 트리를 만듭니다.

4비트 CLA 아키텍처

부울 수준에서 평면 4비트 CLA에는 세 가지 기능이 있습니다.

생성/전파 계층. $n$ 개의 AND 게이트가 한 지연에 $G_i = A_i B_i$ 를 만들고, $n$ 개의 XOR 게이트가 한 지연에 $P_i = A_i \oplus B_i$ 를 만듭니다. 이들은 병렬로 동작합니다.
캐리 네트워크. AND-OR 논리가 전개된 식에서 $C_1$ 부터 $C_4$ 를 계산합니다. 가상의 무제한 팬인 게이트라면 두 논리 단계처럼 보이지만, 실제 라이브러리는 넓은 항을 분해하므로 폭에 따라 깊이와 부하가 늘어납니다.
합 계층. $n$ 개의 XOR 게이트가 한 지연에 $S_i = P_i \oplus C_i$ 를 만듭니다. ( $P_i$ 가 계산된 뒤에는 $S_i = A_i \oplus B_i \oplus C_i = P_i \oplus C_i$ 입니다.)

4비트에서는 전가산기 셀 사슬보다 캐리 경로를 짧게 할 수 있습니다. 평면 식을 끝없이 확장하는 일은 실용적이지 않으므로 더 큰 CLA는 그룹을 도입합니다.

4비트 CLA의 블록 다이어그램

A0,B0 ─┬── XOR ── P0 ──┐                           ┌── XOR ── S0
       └── AND ── G0 ──┤                           │
                       │   ┌─── 캐리 네트워크 ───┐ │
A1,B1 ─┬── XOR ── P1 ──┤   │                     │ ├── XOR ── S1
       └── AND ── G1 ──┤   │   다음을 계산       │ │
                       ├──>│   C1, C2, C3, C4    │─┤
A2,B2 ─┬── XOR ── P2 ──┤   │   전개된 식에서     │ ├── XOR ── S2
       └── AND ── G2 ──┤   │                     │ │
                       │   │   캐리 식           │ │
                       │   └─────────────────────┘ │
A3,B3 ─┬── XOR ── P3 ──┤                           ├── XOR ── S3
       └── AND ── G3 ──┘                           │
                                                   └────────── C4
C0 ──────────────────────>┘

팬인, 배선, 숨은 비용

$C_4$ 에서 가장 긴 평면 식은 $C_0$ 를 포함하면 5입력 곱 항입니다. $C_{16}$ 에서는 대응하는 항이 17입력을 가집니다. 표준 셀 라이브러리는 제한된 팬인만 제공하고, 긴 배선과 큰 부하도 지연을 더합니다. 따라서 문자 그대로의 평면 CLA는 부울식이 얕아 보여도 우아하게 확장되지 않습니다.

일반적인 해결책은 계층 구조입니다. 비트를 보통 4비트 블록으로 묶어 그룹 $G$ 와 $P$ 를 계산하고, 다른 단계에서 이 그룹들을 결합합니다. 16비트 설계는 네 개의 4비트 그룹과 두 번째 예측 단계를 쓸 수 있습니다. 병렬 접두사 가산기는 결합적인 그룹 연산을 트리 전체에 적용합니다.

트레이드오프는 하나의 보편적인 게이트 수 표로 포착되지 않습니다.

아키텍처	캐리 의존성	일반적 장점	일반적 비용
리플 캐리	선형	작은 면적, 단순한 배선	긴 최악 조건 캐리 경로
블록 캐리 예측	계층형	중간 수준의 속도/면적 절충	더 넓은 국부 논리와 그룹 배선
캐리 선택	두 캐리 경우를 미리 계산	더 짧은 결정 경로	중복 합 하드웨어
병렬 접두사	트리형	낮은 논리 깊이	더 많은 접두사 셀, 배선, 때로는 큰 팬아웃

실제 지연, 면적, 에너지는 매핑 및 물리 구현 뒤에 측정해야 합니다. 추상적 게이트 단계에서 이기는 토폴로지도 혼잡, 버퍼링, 부하를 포함하면 질 수 있습니다.

CLA를 넘어: 병렬 접두사 가산기

캐리 예측이라는 발상은 일반화됩니다. 점화식 $C_{i+1} = G_i + P_i C_i$ 는 맞춤 연산자 아래 결합적입니다. 인접한 위치를 쌍으로 묶고, 다시 쌍의 쌍을 트리로 묶을 수 있습니다. 이것이 병렬 접두사 계열입니다.

Kogge–Stone — 낮은 접두사 깊이와 제한된 논리 팬아웃이 장점이지만, 배선이 밀집하고 접두사 노드가 많습니다.
Brent–Kung — 접두사 노드와 배선이 적은 대신 깊이가 더 큽니다.
Han-Carlson, Ladner-Fischer, Sklansky — 팬아웃, 배선 복잡도, 깊이를 서로 다르게 절충합니다.

상용 가산기는 접두사 구조를 섞거나, 희소성을 사용하거나, 선택한 그룹 주변에 캐리 선택 논리를 둘 수도 있습니다. 선택은 특정 타이밍, 면적, 전력, 배선 예산에 맞춰 이루어집니다. 프로세서의 클록 주파수만으로 가산기 토폴로지를 알 수는 없습니다.

DigiSim에서 CLA 구현하기

4비트 CLA는 기본 소자로 만들 수 있습니다. 생성을 위한 AND 게이트 네 개, 전파를 위한 XOR 게이트 네 개, 위의 캐리 식, 합을 위한 최종 XOR 게이트 네 개입니다. 상위 수준의 가산기와 8비트 가산기 구성 요소는 동작상 편의를 제공하는 것이므로, 구성 요소 문서가 명시하지 않는 한 내부 아키텍처를 추론하지 마세요.

토폴로지를 비교하려면 전가산기 네 개를 리플 캐리로 연결하고 별도의 4비트 CLA를 만드세요. 먼저 모든 피연산자 조합에서 기능적 동등성을 확인합니다. 그 다음 시뮬레이터가 게이트별 지연을 모델링한다면 입력 변화 뒤 가장 늦은 안정화 시간을 비교합니다. 게이트가 이상적이라면 의존 논리 단계를 세세요. 이상적인 파형은 실리콘 타이밍을 예측할 수 없습니다.

흔한 함정

$P_i$ 가 OR가 아니라 XOR이라는 점을 잊는 일. $P_i = A_i + B_i$ 또는 $P_i = A_i \oplus B_i$ 두 정의 모두 올바른 캐리를 만듭니다. $A_i = B_i = 1$ 인 경우는 이미 $G_i$ 가 담당하기 때문입니다. XOR을 선호하는 이유는 같은 선을 합 단계에 공급할 수 있기 때문입니다. 즉 $S_i = P_i \oplus C_i$ 입니다. OR로 정의한 $P_i$ 에서는 이 재사용이 성립하지 않아 합을 위한 별도 XOR이 필요합니다.
팬인 확장을 과소평가하는 일. 평면 16비트 전개에는 $C_0$ 를 포함할 때 17리터럴 항이 있습니다. 실용적인 넓은 설계는 논리를 분해하거나 그룹화합니다.
CLA가 항상 더 빠르다고 가정하는 일. 좁은 폭에서는 리플 구현이 면적에서 이길 수 있고 타이밍도 넉넉히 만족할 수 있습니다. 아키텍처와 무관한 교차 폭은 없습니다.
합과 캐리 임계 경로를 혼동하는 일. 캐리 네트워크 깊이가 전체 지연을 지배하지만 마지막 합 XOR이 게이트 지연 하나를 더합니다. 지연을 ‘캐리 네트워크 깊이’로만 명시하는 것은 흔한 오류입니다.

다음 단계

ALU의 작동 원리: 게이트로 만드는 산술 논리 장치를 계속 읽은 뒤, 다른 산술 최적화인 Booth 곱셈기 설명을 살펴보세요.

두 가산기 아키텍처를 직접 비교하려면 캐리를 포함한 전가산기 템플릿을 열어 인스턴스 네 개를 리플 캐리 가산기로 연결하고, 논리 분석기에서 비트별 캐리 전파를 관찰하세요. 이어서 이 글의 식으로 동등한 4비트 CLA를 만들고 두 회로의 시간을 재 보세요. 그 차이야말로 고속 ALU가 존재하는 이유입니다.