분기 예측 (Branch Prediction)¶

개요¶

분기 예측은 조건 분기 명령어의 결과를 미리 예측하여 파이프라인 성능을 높이는 기술입니다. 현대 프로세서는 90% 이상의 예측 정확도를 달성합니다.

목차¶

제어 해저드와 분기 문제
정적 분기 예측
동적 분기 예측
분기 타겟 버퍼
투기적 실행
연습 문제

1. 제어 해저드와 분기 문제¶

분기로 인한 파이프라인 버블¶

beq $t0, $t1, target
add $s0, $s1, $s2     # 실행해야 하나?
sub $s3, $s4, $s5     # 실행해야 하나?
...
target:
or  $s6, $s7, $s8

시간:    1    2    3    4    5    6    7
beq:    IF   ID  [EX]  MEM  WB
                  ↑
             분기 결정
add:         IF   ID   ← flush 필요할 수도
sub:              IF   ← flush 필요할 수도

분기 페널티¶

분기 결정 시점에 따른 페널티:

┌──────────────────┬────────────────┬───────────┐
│   결정 시점      │   페널티       │   설명    │
├──────────────────┼────────────────┼───────────┤
│   ID 단계        │   1 사이클     │   초기 MIPS │
│   EX 단계        │   2 사이클     │   일반적   │
│   MEM 단계       │   3 사이클     │   복잡한 조건 │
└──────────────────┴────────────────┴───────────┘

현대 프로세서: 10-20 사이클 파이프라인
→ 분기 예측 필수!

분기 예측의 필요성¶

분기 빈도: 약 20% (5개 명령어당 1개)

예측 없이 항상 스톨:
CPI = 1 + 0.2 × 3 = 1.6  (3 사이클 페널티 가정)

90% 정확도 예측:
CPI = 1 + 0.2 × 0.1 × 3 = 1.06

성능 향상: 1.6/1.06 = 1.5배

2. 정적 분기 예측¶

2.1 항상 Not Taken¶

전략: 모든 분기가 일어나지 않는다고 예측

장점: 구현 간단
단점: 루프에서 성능 저하

for (i = 0; i < 100; i++)  // 99번 taken, 1번 not taken
                           // 예측 정확도: 1%

2.2 항상 Taken¶

전략: 모든 분기가 일어난다고 예측

장점: 루프에 유리
단점: 분기 타겟 주소 계산 필요

for (i = 0; i < 100; i++)  // 예측 정확도: 99%

2.3 BTFN (Backward Taken, Forward Not Taken)¶

전략:
- 뒤로 가는 분기 (루프): Taken 예측
- 앞으로 가는 분기 (if문): Not Taken 예측

┌─────────────────────────────────────────┐
│     분기 방향에 따른 예측                │
│                                         │
│  PC=100:  beq label    (label=80)       │
│           ↑                             │
│           뒤로 분기 → Taken 예측        │
│                                         │
│  PC=100:  beq label    (label=120)      │
│           ↑                             │
│           앞으로 분기 → Not Taken 예측   │
└─────────────────────────────────────────┘

루프의 끝에서 처음으로 돌아가는 것: 뒤로 분기
if문에서 else로 건너뛰는 것: 앞으로 분기

3. 동적 분기 예측¶

3.1 1비트 예측기¶

┌─────────────────────────────────────────┐
│           1-bit Predictor               │
├─────────────────────────────────────────┤
│  상태: Taken(1) 또는 Not Taken(0)       │
│                                         │
│  동작:                                  │
│  - 현재 상태로 예측                      │
│  - 틀리면 상태 반전                      │
└─────────────────────────────────────────┘

상태 전이:
     틀림         틀림
  ┌────────┐   ┌────────┐
  │        │   │        │
  ▼        │   ▼        │
┌────┐     │ ┌────┐     │
│ NT │◀────┴─│ T  │◀────┘
└────┘  맞음  └────┘  맞음

문제: 루프 시작과 끝에서 항상 2번 틀림

1비트 예측기의 한계¶

루프 100회 반복:
T T T ... T T N  (99번 T, 1번 N)
                 ↑ 루프 종료

예측:   T T T ... T T T N
실제:   T T T ... T T N ←
                      ↑ 틀림 (예측 T, 실제 N)

다음 루프 시작:
예측:   N ← 틀림 (예측 N, 실제 T)

100회 반복마다 2번 틀림 → 98% 정확도

3.2 2비트 예측기¶

┌─────────────────────────────────────────────────┐
│              2-bit Saturating Counter           │
├─────────────────────────────────────────────────┤
│  4가지 상태:                                    │
│  - 00: Strongly Not Taken                       │
│  - 01: Weakly Not Taken                         │
│  - 10: Weakly Taken                             │
│  - 11: Strongly Taken                           │
└─────────────────────────────────────────────────┘

상태 전이도:
        N              N              N
   ┌────────┐     ┌────────┐     ┌────────┐
   │        ▼     │        ▼     │        ▼
┌──┴──┐  ┌──┴──┐  ┌──┴──┐  ┌──┴──┐
│ SNT │  │ WNT │  │ WT  │  │ ST  │
│ 00  │  │ 01  │  │ 10  │  │ 11  │
└──┬──┘  └──┬──┘  └──┬──┘  └──┬──┘
   │        ▲     │        ▲     │        ▲
   └────────┘     └────────┘     └────────┘
        T              T              T

예측: 상위 비트가 1이면 Taken, 0이면 Not Taken

2비트 예측기 동작 예시¶

루프 100회:
실제:   T T T ... T T N T T T ... (다음 루프)

상태:  ST ST ST ... ST WT ST ST ST ...
예측:   T  T  T ...  T  T  T  T  T ...
정답:   ✓  ✓  ✓ ... ✓  ✗  ✓  ✓  ✓ ...

1번만 틀림! 루프당 1번 실패
99% 이상 정확도

3.3 분기 히스토리 테이블 (BHT)¶

┌─────────────────────────────────────────────────┐
│         Branch History Table (BHT)              │
├─────────────────────────────────────────────────┤
│                                                 │
│   PC[9:2] ───▶ ┌─────────┐                     │
│                │ Index   │                     │
│                │  256    │                     │
│                │ entries │                     │
│                └────┬────┘                     │
│                     │                          │
│                     ▼                          │
│              2-bit counter                     │
│                                                │
└─────────────────────────────────────────────────┘

PC의 일부 비트를 인덱스로 사용
- 각 엔트리에 2비트 카운터 저장
- 같은 인덱스에 여러 분기가 매핑될 수 있음 (aliasing)

3.4 상관 예측기 (Correlating Predictor)¶

아이디어: 다른 분기의 결과가 현재 분기에 영향

예시 코드:
if (a == 2)     // B1
    a = 0;
if (b == 2)     // B2
    b = 0;
if (a != b)     // B3: B1, B2 결과와 상관관계!
    ...

(m, n) 예측기:
- m: 최근 m개 분기의 결과를 기록 (Global History)
- n: n비트 카운터

┌──────────────────────────────────────────┐
│         (2, 2) Correlating Predictor     │
│                                          │
│  Global History: 2비트 (00, 01, 10, 11)  │
│  각 히스토리당: 2비트 카운터             │
│                                          │
│  총 4개의 2비트 카운터                    │
└──────────────────────────────────────────┘

3.5 토너먼트 예측기¶

┌────────────────────────────────────────────────┐
│           Tournament Predictor                  │
│                                                 │
│         ┌─────────────┐                        │
│  PC ───▶│  Selector   │ (2비트 카운터)         │
│         └──────┬──────┘                        │
│                │                               │
│         ┌──────┴──────┐                        │
│         ▼             ▼                        │
│  ┌────────────┐ ┌────────────┐                 │
│  │   Local    │ │   Global   │                 │
│  │ Predictor  │ │ Predictor  │                 │
│  └──────┬─────┘ └─────┬──────┘                 │
│         │             │                        │
│         └──────┬──────┘                        │
│                ▼                               │
│           MUX (선택)                           │
│                │                               │
│                ▼                               │
│            예측 결과                            │
└────────────────────────────────────────────────┘

- Local: 개별 분기의 히스토리 사용
- Global: 전체 분기 히스토리 사용
- Selector: 어느 예측기가 더 정확한지 학습

4. 분기 타겟 버퍼¶

BTB (Branch Target Buffer)¶

분기 명령어인지 + 타겟 주소를 미리 저장

┌─────────────────────────────────────────────────┐
│              Branch Target Buffer               │
├───────────┬──────────┬─────────────────────────┤
│    Tag    │  Target  │  Prediction (optional)  │
├───────────┼──────────┼─────────────────────────┤
│ 0x1000... │  0x2000  │        ST               │
│ 0x1100... │  0x1500  │        WT               │
│ 0x2000... │  0x1800  │        SNT              │
│    ...    │   ...    │        ...              │
└───────────┴──────────┴─────────────────────────┘

IF 단계에서 BTB 조회:
- Hit + Taken 예측: 타겟 주소로 즉시 점프
- Miss: 일반 실행, 나중에 BTB 업데이트

BTB 동작 흐름¶

┌─────────────────────────────────────────────────┐
│                IF 단계                          │
│                                                 │
│   PC ───▶ BTB 조회                             │
│              │                                  │
│              ▼                                  │
│         ┌────────┐                             │
│         │  Hit?  │                             │
│         └────┬───┘                             │
│              │                                  │
│      No      │      Yes                        │
│      ▼       │       ▼                         │
│   PC + 4     │   Taken 예측?                   │
│              │       │                          │
│              │   Yes │  No                     │
│              │    ▼  │   ▼                     │
│              │  Target  PC + 4                 │
│              │   주소                          │
└─────────────────────────────────────────────────┘

5. 투기적 실행¶

개념¶

분기 결과 확정 전에 예측된 경로의 명령어 실행

┌─────────────────────────────────────────────────┐
│           Speculative Execution                 │
│                                                 │
│   beq 예측: Taken                              │
│      │                                          │
│      ▼                                          │
│   타겟 명령어들을 미리 실행 (투기적)            │
│      │                                          │
│      ▼                                          │
│   분기 결과 확정                                │
│      │                                          │
│   ┌──┴──┐                                      │
│   │     │                                      │
│ 예측   예측                                     │
│ 성공   실패                                     │
│   │     │                                      │
│   ▼     ▼                                      │
│ 결과   결과 폐기                                │
│ 커밋   (flush)                                 │
└─────────────────────────────────────────────────┘

예측 실패 복구¶

예측 실패 시:
1. 파이프라인 플러시 (투기적 명령어 제거)
2. 레지스터 상태 복구
3. 올바른 경로로 재실행

복구 비용:
- 파이프라인 깊이에 비례
- 현대 프로세서: 10-20 사이클 페널티

Misprediction Rate의 영향¶

CPI = CPI_base + (분기 비율) × (예측 실패율) × (페널티)

예시:
- CPI_base = 1
- 분기 비율 = 20%
- 페널티 = 15 사이클

┌────────────────┬──────────────────┐
│ 예측 실패율    │      CPI         │
├────────────────┼──────────────────┤
│     10%        │ 1 + 0.2×0.1×15   │
│                │ = 1.30           │
├────────────────┼──────────────────┤
│      5%        │ 1 + 0.2×0.05×15  │
│                │ = 1.15           │
├────────────────┼──────────────────┤
│      2%        │ 1 + 0.2×0.02×15  │
│                │ = 1.06           │
├────────────────┼──────────────────┤
│      1%        │ 1 + 0.2×0.01×15  │
│                │ = 1.03           │
└────────────────┴──────────────────┘

6. 연습 문제¶

기초 문제¶

정적 분기 예측 3가지 방식은?
2비트 예측기의 4가지 상태는?
다음 시퀀스에서 1비트 예측기(초기 T)의 예측 결과: T T N T T N T T

분석 문제¶

아래 루프에서 2비트 예측기(초기 ST)의 동작:

for (int i = 0; i < 4; i++) {
    // 루프 본문
}

분기 비율 25%, 페널티 10 사이클, 예측 정확도 95%일 때 CPI는?

심화 문제¶

토너먼트 예측기가 단일 예측기보다 좋은 이유를 설명하시오.
BTB가 없을 때와 있을 때의 분기 처리 차이를 비교하시오.

정답

1. Always Not Taken, Always Taken, BTFN (Backward Taken, Forward Not Taken) 2. Strongly Not Taken (00), Weakly Not Taken (01), Weakly Taken (10), Strongly Taken (11) 3.

실제: T T N T T N T T
예측: T T T N T T N T
상태: T T N T T N T T
정답: ✓ ✓ ✗ ✗ ✓ ✗ ✗ ✓  (4/8 = 50%)

반복: T T T N (4회 반복)
상태: ST ST ST WT WT
예측: T  T  T  T  T
정답: ✓  ✓  ✓  ✗

4회 중 1회 실패 = 75% 정확도 5. CPI = 1 + 0.25 × 0.05 × 10 = 1.125 6. 토너먼트 예측기는 Local과 Global 예측기를 모두 사용하고, 각 분기에 대해 더 정확한 예측기를 선택적으로 사용. 어떤 분기는 지역적 패턴이 중요하고, 어떤 분기는 전역적 상관관계가 중요하기 때문. 7. - BTB 없음: ID 또는 EX 단계에서야 분기 여부와 타겟 파악, 페널티 발생 - BTB 있음: IF 단계에서 BTB hit 시 즉시 타겟으로 점프 가능, 페널티 최소화

다음 단계¶

13_Superscalar_Out_of_Order.md - ILP와 비순차 실행

참고 자료¶

Computer Architecture: A Quantitative Approach, Chapter 3 (Hennessy & Patterson)
Branch Prediction Competition
Agner Fog's Microarchitecture Guide