235. 분기 역사 표 (BHT)

핵심 인사이트 (3줄 요약)

1. 본질: 분기 역사 표 (BHT, Branch History Table)는 분기 명령어가 과거에 점프했는지 여부를 작은 상태값으로 기억해, 다음 분기 방향을 미리 추정하는 방향 예측용 메모리다.
2. 가치: 깊은 파이프라인에서는 분기 오예측 한 번이 10~20사이클 이상의 손실로 이어질 수 있으므로, BHT는 작은 하드웨어 비용으로 큰 성능 회복을 만드는 프론트엔드 핵심 장치다.
3. 판단 포인트: BHT는 단순할수록 빠르고 싸지만, 앨리어싱 (Aliasing)과 상관관계 미반영 한계가 있으므로 BTB (Branch Target Buffer), GHR (Global History Register), gshare 같은 기법과 함께 봐야 제대로 이해된다.

Ⅰ. 개요 및 필요성

BHT는 "이 분기는 지난번에 어디로 기울었는가" 를 기억하는 표다. CPU (Central Processing Unit)가 분기 명령어를 만날 때마다 결과를 끝까지 기다리면 파이프라인이 멈추므로, 먼저 방향을 예측하고 그 예측이 맞을 확률을 높여야 한다. 이때 BHT는 분기 주소를 단서로 삼아 과거의 Taken/Not Taken 경향을 짧게 저장한다.

이 장치가 필요한 이유는 제어 해저드 (Control Hazard)의 비용이 생각보다 크기 때문이다. 예를 들어 15단 파이프라인에서 분기 결과가 뒤늦게 확정되면 잘못 가져온 명령어들을 모두 비워야 하고, 이 손실이 루프마다 반복되면 산술 연산을 아무리 빨리 해도 전체 성능이 무너진다. 결국 BHT는 "분기 결과가 나오기 전까지도 파이프라인을 계속 전진시키기 위한 최소한의 기억 장치"로 등장했다.

특히 반복문은 거의 항상 같은 패턴을 보인다. 루프 본문 동안에는 계속 Taken이고 마지막 탈출 시점에만 Not Taken이 나오므로, 과거 이력을 조금만 잘 기억해도 높은 적중률을 얻을 수 있다. 그래서 BHT는 동적 분기 예측 (Dynamic Branch Prediction)의 출발점이자, 오늘날에도 여러 고급 예측기의 기반 구성요소로 남아 있다.

• 📢 섹션 요약 비유: BHT는 엘리베이터 문 앞 경비 기록장과 같다. 평소 8층으로 가던 사람이 오늘도 그럴 가능성이 높다고 보고 먼저 버튼을 준비해 두면, 문 앞에서 매번 다시 물어보느라 줄이 막히지 않는다.

Ⅱ. 아키텍처 및 핵심 원리

BHT의 기본 재료는 작은 SRAM (Static Random Access Memory) 배열과 2비트 포화 카운터 (2-bit Saturating Counter)다. CPU는 보통 PC (Program Counter)의 일부 비트를 인덱스로 사용해 BHT 엔트리를 읽고, 그 엔트리의 상위 의미를 Taken 또는 Not Taken으로 해석한다. 예측이 끝난 뒤 실제 실행 결과가 나오면 같은 엔트리를 갱신한다.

아래 그림은 BHT가 인출 단계에서 조회되고, 실행이 끝난 뒤 같은 항목이 갱신되는 흐름을 보여준다.

┌──────────────────────────────────────────────────────────────────────────┐
│                 BHT 조회와 갱신의 시간 흐름                              │
├──────────────────────────────────────────────────────────────────────────┤
│ IF (Instruction Fetch)                                                  │
│   PC ──▶ index 추출 ──▶ BHT[entry] 읽기 ──▶ 예측: Taken / Not Taken     │
│    │                                                                     │
│    └──────────────────────▶ BTB와 함께 다음 PC 선택                     │
│                                                                          │
│ EX / Resolve                                                             │
│   실제 분기 결과 확인 ──▶ 같은 entry 갱신 ──▶ 다음 예측에 반영           │
└──────────────────────────────────────────────────────────────────────────┘

2비트 포화 카운터를 쓰는 이유는 한 번의 예외에 바로 태도를 바꾸지 않기 위해서다. 1비트만 쓰면 루프 탈출 한 번에 상태가 즉시 뒤집혀 다음 루프 진입에서 또 틀리기 쉽다. 2비트는 약한 상태와 강한 상태를 분리해, 같은 방향의 반대 결과가 두 번쯤 누적되어야 예측 방향이 바뀌게 만든다.

이 표의 핵심은 "예측 비트"보다 "관성"에 있다. 예측기 입장에서는 맞히는 것만큼, 일시적 잡음 때문에 학습 내용을 쉽게 잊지 않는 것도 중요하다. 그래서 BHT는 작지만 사실상 유한 상태 머신 (FSM, Finite State Machine) 으로 동작하는 학습 회로라고 볼 수 있다.

• 📢 섹션 요약 비유: BHT의 2비트 카운터는 단골손님 메모와 같다. 단골이 하루 안 왔다고 바로 "이제 안 오네"라고 판단하지 않고, 몇 번 더 지켜본 뒤에야 주문 습관을 바꾸는 식이다.

Ⅲ. 비교 및 연결

BHT를 이해할 때 가장 먼저 비교해야 할 것은 1비트 예측기와 2비트 예측기다. 1비트는 구현이 매우 단순하지만 루프 종료처럼 드문 반전에도 쉽게 흔들린다. 반면 2비트 BHT는 루프형 코드에 특히 강하고, 작은 추가 비용으로 적중률을 크게 끌어올린다.

또한 BHT는 BTB와 역할이 다르다. BHT는 갈지 말지 를 판단하고, BTB는 간다면 어디로 갈지 를 알려준다. 즉 방향 정보와 목적지 정보가 분리되어 있어야 인출 단계에서 다음 PC를 빠르게 정할 수 있다.

한편 단순 BHT는 개별 분기의 로컬 경향만 잘 본다. 하지만 실제 프로그램에는 "앞 분기가 참일 때 뒤 분기도 참이 되기 쉬운" 상관관계가 많다. 그래서 현대 프로세서는 GHR과 PC를 XOR 하는 gshare, 여러 예측기를 경쟁시키는 tournament predictor 등으로 확장하여 BHT의 한계를 보완한다.

• 📢 섹션 요약 비유: BHT만 쓰는 것은 가게 사장님이 "이 손님은 보통 라면을 시켜" 정도만 기억하는 수준이다. BTB는 어느 자리로 가는지까지 기억하는 것이고, gshare는 앞선 손님들의 주문 흐름까지 같이 보고 오늘 메뉴를 더 정확히 맞히는 방식이다.

Ⅳ. 실무 적용 및 기술사 판단

실무에서 BHT는 단순히 "크게 만들면 좋은 표"가 아니다. 인출 단계는 매우 짧은 클럭 안에 끝나야 하므로, BHT는 충분히 빨라야 하고 동시에 적중률도 확보해야 한다. 결국 설계자는 성능, 면적, 전력의 균형 속에서 엔트리 수와 인덱싱 방식을 정한다.

설계 판단 포인트

1. 앨리어싱 (Aliasing) 관리: 서로 다른 분기 명령어가 같은 엔트리를 공유하면 예측 이력이 섞여 적중률이 떨어진다. 엔트리 수를 늘리거나, PC 비트를 더 영리하게 섞어 해시하는 이유가 여기에 있다.
2. 갱신 시점 선택: 실행 완료 후에만 갱신하면 안정적이지만 늦고, 투기적 갱신 (Speculative Update)을 쓰면 빠르지만 복구 로직이 필요하다. 깊은 파이프라인일수록 이 선택이 중요해진다.
3. BTB·프리디코더와의 협업: BHT가 Taken이라고 말해도 BTB 미스가 나면 즉시 목적지로 갈 수 없다. 따라서 방향 예측 정확도만 따로 높이는 것으로는 프론트엔드 병목이 완전히 해결되지 않는다.

안티패턴

• 무작위 분기 남발: 데이터가 완전히 랜덤한 분기는 아무리 좋은 BHT라도 학습하기 어렵다.
• 과소한 테이블 크기: 코드 규모에 비해 BHT가 너무 작으면 앨리어싱이 급증해, 예측기를 넣고도 체감 성능이 거의 안 난다.
• 정확도만 보고 조회 지연 무시: 적중률이 조금 올라가도 IF 단계가 느려지면 전체 클럭이 낮아져 오히려 손해일 수 있다.

기술사 답안에서는 "BHT는 적중률 장치이면서도 동시에 타이밍 제약 장치"라는 관점이 중요하다. 즉 많이 기억하는 것보다 제때 읽고, 제때 갱신하고, 충돌을 덜 일으키는 것이 더 본질적인 설계 포인트다.

• 📢 섹션 요약 비유: BHT 설계는 작은 동네 도서관 서가 배치와 같다. 책을 많이 꽂는 것도 중요하지만, 손님이 찾는 책이 자꾸 다른 책과 뒤섞이면 결국 서가가 커도 찾는 속도는 느려진다.

Ⅴ. 기대효과 및 결론

BHT의 가장 큰 효과는 제어 해저드 때문에 멈출 뻔한 파이프라인을 계속 흘려보낸다는 점이다. 적중률이 높아질수록 플러시 빈도가 줄고, 결과적으로 명령어 처리량(IPC, Instructions Per Cycle)이 안정된다. 특히 반복문과 조건 분기가 많은 일반 목적 코드에서 체감 이득이 크다.

다만 BHT만으로 모든 분기를 해결할 수는 없다. 간접 분기, 복잡한 상관 분기, 보안 이슈가 얽힌 투기 실행 환경에서는 더 정교한 예측기와 보호 기법이 필요하다. 따라서 BHT는 "완성형 해답"이라기보다 동적 분기 예측 체계의 가장 기본이면서도 여전히 필수적인 층으로 기억하는 것이 적절하다.

앞으로의 방향도 같은 맥락이다. 단순 카운터형 BHT는 여전히 빠르고 효율적이지만, 고성능 코어에서는 전역 이력, 하이브리드 예측, 신경망 기반 예측기까지 결합해 사용한다. 그럼에도 중심 원리는 변하지 않는다. 과거 분기 행동을 짧게 기억해 미래 정지 비용을 줄인다는 것이 BHT의 본질이다.

• 📢 섹션 요약 비유: BHT는 자동차의 자동변속기 학습 기능과 비슷하다. 운전 습관을 조금씩 기억해 다음 변속을 더 부드럽게 만들지만, 도로가 완전히 달라지면 내비게이션과 각종 센서의 도움이 함께 필요하다.

📌 관련 개념 맵

📈 관련 키워드 및 발전 흐름도

정적 분기 예측
    │
    ▼
1비트 분기 기록
    │
    ▼
BHT (Branch History Table)
    │
    ├──▶ BTB (Branch Target Buffer) 결합
    │
    └──▶ GHR (Global History Register) 결합
              │
              ▼
        gshare · tournament predictor
              │
              ▼
      하이브리드 · 신경망 기반 분기 예측기

이 흐름은 "단순 방향 추정 → 관성 부여 → 주소·상관관계 통합 → 하이브리드 고도화"로 진화하는 과정을 보여준다.

👶 어린이를 위한 3줄 비유 설명

1. BHT는 컴퓨터가 "이 갈림길에서는 보통 오른쪽으로 갔어" 하고 기억하는 작은 메모장이에요.
2. 한 번 실수했다고 바로 메모를 바꾸지 않고, 몇 번 더 보고 천천히 생각을 바꿔요.
3. 그래서 컴퓨터는 갈림길마다 오래 멈추지 않고, 미리 길을 짐작하며 더 빨리 달릴 수 있어요.