분기 예측 — Branch Prediction

CPU는 if의 결과가 나오기도 전에 "찍는다" · 잘 찍으면 공짜, 틀리면 파이프라인을 통째로 비운다

1. CPU는 왜 미리 찍어야 하나

현대 CPU는 명령어를 한 줄씩 끝내지 않고 파이프라인에 여러 개를 겹쳐 흘려보낸다. 그런데 if (x > 0) goto A; else goto B; 같은 조건 분기를 만나면 문제가 생긴다. 조건식 x > 0의 결과는 파이프라인 뒤쪽(EX 단계)에서야 나오는데, 그 다음에 어떤 명령어를 가져와야 할지(A쪽? B쪽?)는 지금 당장 정해야 하기 때문이다.

그래서 CPU는 분기 예측기(branch predictor)로 "이 분기는 taken(점프함) / not-taken(안 함)" 을 미리 찍고, 예측한 쪽 명령어들을 파이프라인에 계속 채워 넣는다.

2. 2비트 포화 카운터 — 예측기의 심장

가장 고전적인 예측기는 분기마다 2비트짜리 상태를 하나씩 들고 있다(이 표를 BHT, Branch History Table이라 부른다). 상태는 4가지: 강한 Not-Taken → 약한 Not-Taken → 약한 Taken → 강한 Taken. 분기가 실제로 taken이면 카운터를 +1(오른쪽), not-taken이면 −1(왼쪽) 방향으로 밀되 양 끝에서 포화(saturate)한다.

핵심은 한 번 헛나가도 예측 방향이 바로 뒤집히지 않는다는 것. 예: 반복문이 100번 도는 동안 매번 taken인데 마지막 1번만 not-taken이다. 1비트 예측기는 이 한 번 때문에 예측을 뒤집었다가 다음 반복에서 또 틀린다(2번 실패). 2비트는 "약한 Taken"으로만 살짝 물러났다가 곧바로 회복한다(1번 실패).

3. 예측기 발전사

방식	동작	약점
정적 예측 Static	"뒤로 가는 분기(반복문)는 taken, 앞으로 가는 분기는 not-taken" 같은 고정 규칙. 컴파일러 힌트도 사용.	데이터에 따라 달라지는 분기는 못 맞힘
1비트	"지난번에 taken이었으면 이번에도 taken." 상태 1비트.	반복문 경계에서 매번 2번씩 틀림
2비트 포화	위 데모. 관성이 있어 가끔의 예외에 흔들리지 않음. 반복문 100회 → 실패 1회.	taken/not-taken이 번갈아 나오는 패턴엔 취약
2단계 / 상관 예측 Two-level	최근 분기들의 기록(global history)을 비트열로 저장하고, 그 패턴별로 2비트 카운터를 따로 둠. "A가 taken이었으면 B는 not-taken" 같은 상관관계 학습.	표가 커지고 워밍업 필요
토너먼트 / 신경망	여러 예측기를 두고 분기마다 어느 예측기를 믿을지까지 학습. 최신 CPU는 퍼셉트론 기반 예측기 사용.	하드웨어 복잡·전력

이와 별개로 BTB(Branch Target Buffer)는 "이 분기가 taken이면 어디로 점프하는지" 목적지 주소를 캐시해 둔다. 방향 예측(taken?)과 목적지 예측(어디로?)은 서로 다른 하드웨어다.

4. 실전: 정렬된 배열이 더 빠르다

Stack Overflow 역사상 가장 유명한 질문 중 하나 — "왜 정렬된 배열을 처리하는 게 더 빠른가?" 아래처럼 배열을 훑으며 임계값보다 큰 값만 더한다고 하자.

long sum = 0;
for (int i = 0; i < N; i++)
    if (data[i] >= 128)     // ← 이 분기의 예측 성공률이 관건
        sum += data[i];

데이터가 무작위면 data[i] >= 128은 동전 던지기라 예측기가 아무리 똑똑해도 적중률 ~50%. 데이터가 정렬돼 있으면 앞부분은 계속 not-taken, 뒷부분은 계속 taken — 딱 한 번 경계에서만 틀리고 나머지는 거의 100% 적중한다. 연산 결과는 똑같은데 실행 시간이 몇 배씩 차이 난다.

어떻게 고치나

• 분기를 없앤다(branchless). sum += (data[i] >= 128) * data[i]; 또는 조건부 이동(cmov) — 예측할 게 없으니 실패도 없다.
• 데이터를 정렬하거나 예측 잘 되는 순서로 정리한다(단, 정렬 비용과 비교).
• 컴파일러/프로파일(PGO)에 "이 분기는 거의 참"이라고 알려 준다([[likely]], __builtin_expect).

5. 예측 정확도 → 성능

분기가 전체 명령어의 20%, 예측 실패 페널티를 15사이클, 그 외 CPI를 1로 두면:

유효 CPI = 1 + 0.20 × (1 − 적중률) × 15

6. 한눈 정리

• 분기 예측은 파이프라인이 if 결과를 기다리지 않게 하는 투기적 실행(speculation)의 핵심이다.
• 2비트 포화 카운터는 관성 덕에 가끔의 예외에 흔들리지 않는다 — 1비트보다 반복문 경계에서 강하다.
• 같은 코드·같은 데이터라도 순서(예측 가능성)에 따라 속도가 몇 배 차이 난다.
• 예측이 불가능한 분기는 분기 자체를 없애는 것(branchless)이 정답일 때가 많다.
• 투기적 실행은 Spectre 같은 보안 취약점의 무대이기도 하다 — 예측이 틀려도 이미 흘러간 흔적이 캐시에 남는다.