분기 예측(Branch Prediction)은 CPU 파이프라인이 조건 분기(if/else, 루프)의 결과를 미리 예측해 파이프라인 스톨(Stall)을 방지하는 기법이다. 현대 CPU는 95% 이상의 예측 정확도를 달성한다.
파이프라인 스톨 문제
5단계 파이프라인: IF → ID → EX → MEM → WB
조건 분기 명령어 도달:
분기 결과를 EX 단계에서야 알 수 있음
→ IF/ID 2단계가 낭비됨 (Bubble)
예측 틀렸을 때 패널티: ~15~20 사이클 (현대 CPU)
예측 전략
1. 정적 예측:
- 항상 taken/not-taken 예측
- 후방 분기(루프)는 taken 예측 → 적중률 높음
2. 동적 예측 (2-bit 포화 카운터):
11(강하게 taken) → 10(약하게 taken)
01(약하게 not-taken) → 00(강하게 not-taken)
최근 2번의 이력으로 예측
3. 토너먼트 예측기:
여러 예측기 중 가장 정확한 것 선택
4. TAGE (현대 CPU):
다양한 길이의 히스토리 기반 예측
Spectre 취약점
분기 예측 + 비순서 실행 = Spectre 취약점
→ 예측 실행 중 캐시 사이드 채널로 비밀 정보 유출
→ Spectre Mitigations: IBRS, retpoline 등
코드 최적화
c
// 예측 힌트 제공 (GCC)
if (__builtin_expect(error_condition, 0)) { // 거의 false로 예측
handle_error();
}
// C++20 [[likely]], [[unlikely]]
if (x > 0) [[likely]] {
fast_path();
}
관련 개념
