235. 분기 역사 표 (BHT)

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

본질: 분기 역사 표 (Branch History Table, BHT)는 특정 분기 명령어의 과거 점프 여부(Taken/Not Taken)를 2비트 포화 카운터(Saturating Counter)로 기록하여 미래를 예측하는 초소형 SRAM 배열이다.

가치: 2비트 상태 머신을 통해 "두 번은 틀려야 태도를 바꾸는" 인간적인 고집(Hysteresis)을 구현함으로써, 루프의 종료와 같은 일시적인 예외 상황 때문에 공들여 쌓은 예측 패턴이 깨지는 것을 방지한다.

판단 포인트: 단순 주소 맵핑의 한계를 극복하기 위해 전역 이력(GHR)과 XOR 연산으로 결합된 gshare 방식 등으로 진화하며, 현대에는 퍼셉트론(Perceptron) 기반 하드웨어 AI가 BHT의 역할을 대체하고 있다.

Ⅰ. 개요 및 필요성

BHT는 동적 분기 예측기의 "기억력"이다. 정적 예측이 무지성으로 찍는 것이라면, BHT는 분기 명령어 주소(PC)를 인덱스로 삼아 최근 수십 번의 행적을 꼼꼼히 기록해두는 비밀 수첩과 같다.

이 기술이 필요한 이유는 1비트 예측의 변덕 방지다. 100번 도는 루프에서 100번째에 탈출할 때 예측이 한 번 틀리는 건 당연하지만, 1비트 방식은 이때 즉시 상태를 '점프 안 함'으로 바꿔버려 다음 루프 진입 시 또 틀리는 이중 패널티를 유발한다. BHT는 2비트 완충 지대를 두어 이런 단기 기억 상실을 치료하고, 90% 이상의 안정적인 적중률을 사수하는 현대 CPU 프론트엔드의 핵심 지능으로 군림한다.

📢 섹션 요약 비유: 식당 주인이 손님을 평가하는 '신용 등급'과 같습니다. VIP 손님(11, Strongly)이 바빠서 하루 결석했다고 바로 일반 손님으로 강등시키지 않고 한 번은 봐줍니다(10, Weakly). 이틀 연속으로 결석해야 비로소 등급을 내리는 신중함입니다.

Ⅱ. 아키텍처 및 핵심 원리

BHT의 핵심은 4가지 상태를 가진 2비트 포화 카운터(Saturating Counter)의 유한 상태 머신(FSM)이다.

상태 (Bit)	명칭 (State Name)	예측 방향	실제 결과가 T일 때	실제 결과가 NT일 때
11	Strongly Taken	점프함	11 유지	10으로 하락
10	Weakly Taken	점프함	11로 상승	01로 하락 (예측 변경)
01	Weakly Not Taken	안 함	10으로 상승 (예측 변경)	00으로 하락
00	Strongly Not Taken	안 함	01로 상승	00 유지

┌─────────────────────────────────────────────────────────────────────────────┐
│              BHT의 동작 메커니즘 (인출 단계 조회 및 사후 갱신)              │
├─────────────────────────────────────────────────────────────────────────────┤
│  [ 현재 PC (예: 0x1000) ]                                                   │
│        │                                                                    │
│        ▼ (하위 10비트 추출 -> 1024개 엔트리)                                │
│  [ BHT (SRAM 배열) ]                                                        │
│  Index 0: [ 11 ]                                                            │
│  Index 1: [ 00 ]                                                            │
│  ...                                                                        │
│  Index 42: [ 10 ] (Weakly Taken) ◀── (현재 PC와 매칭됨)                    │
│                                                                             │
│ * 과정: 1. BHT의 '10'을 보고 "점프함" 예측                                  │
│         2. 나중에 실행 결과가 "진짜 점프"면 인덱스 42를 '11'로 강화         │
│         3. "진짜 안 점프"면 인덱스 42를 '01'로 약화 (반성 및 갱신)          │
└─────────────────────────────────────────────────────────────────────────────┘

이 구조는 물리적으로 매우 단순한 비트 연산만으로도 고도의 통계적 추론을 가능케 하며, 칩 설계에서 가장 적은 비용으로 가장 큰 성능 이득을 얻는 구간 중 하나다.

📢 섹션 요약 비유: 2비트 카운터는 '두 번은 참는 보살님'과 같습니다. 평소 매일 아침 오던 손님이 하루 안 왔다고 해서 내일 재료를 안 준비하는 게 아니라, 내일 한 번만 더 믿어보고 안 오면 그때 비로소 재료를 치우는 인내심입니다.

Ⅲ. 비교 및 연결

BHT는 정보의 깊이에 따라 로컬(Local)에서 글로벌(Global)로 진화했다.

비교 항목	1-bit BHT (단순 기억)	2-bit BHT (표준)	gshare (글로벌 상관관계)
상태 수	2개 (T, NT)	4개 (완충 지대 존재)	수만 개 (패턴 기반)
루프 탈출 시	다음 진입 시 무조건 오답	다음 진입 시 정답 사수	중첩 루프까지 완벽 추적
결정적 단점	변덕스러운 예측 (Stall 빈번)	앞 분기와의 상관관계 모름	거대한 해시 테이블 필요
적중률	80% 근방	85~90%	95% 이상

최근의 고성능 CPU는 단순 BHT의 인덱스로 PC 주소만 쓰지 않는다. 최근 10번의 분기 결과 전체를 묶은 **GHR (Global History Register)**과 PC 주소를 XOR 연산하여 BHT를 뒤지는 gshare 방식을 쓴다. 이를 통해 "A 분기가 성공했을 때 B 분기가 실패하더라"는 소름 돋는 상관관계를 칩이 스스로 파악해낸다.

📢 섹션 요약 비유: 단순 BHT가 "오늘 비 오니 내일도 오겠지"라고 날씨만 보는 것이라면, gshare는 "오늘 비 왔고 바람도 습하게 부니 소나기가 오겠군" 하고 주변 환경(상관관계)까지 섞어서 맞추는 기상청 시스템입니다.

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

실무 아키텍트에게 BHT 설계는 **'앨리어싱 (Aliasing)'**과의 전쟁이다.

설계 및 실무 판단 포인트

해시 충돌 방지: BHT 주소로 PC의 하위 비트만 쓰면, 서로 다른 두 분기가 같은 BHT 방을 쓰며 이력을 덮어씌우는 '파괴적 간섭'이 일어난다. 실무에서는 이를 막기 위해 PC 주소 비트를 영리하게 섞는 해시 튜닝에 수백만 번의 시뮬레이션을 쏟아붓는다.
Speculative Update: 파이프라인이 너무 깊으면 실제 연산 결과가 나올 때까지 기다렸다가 BHT를 갱신하면 늦는다. 뒷 명령어가 옛날 수첩을 보고 계속 틀리기 때문이다. 실무에서는 예측한 즉시 BHT를 일단 갱신해두고, 나중에 틀리면 복구하는 '투기적 갱신' 기법을 필수로 쓴다.
PPA와 용량: BHT가 크면 잘 맞추지만 IF 단계가 늦어진다. 1024~4096 엔트리 사이에서 전력과 속도의 황금비를 찾는 것이 아키텍트의 실력이다.

안티패턴

BHT를 무력화하는 무작위 분기 코드: if (rand() % 2) 같은 코드는 BHT 수첩을 갈기갈기 찢어버린다. 이런 코드는 분기문 없는 수학적/비트 연산으로 대체하여 BHT를 보호해야 한다.
📢 섹션 요약 비유: 장부가 아직 어제 매출로 안 적혀 있는데, 아침 알바생이 옛날 장부를 보고 잘못된 재고 주문을 수십 번 연달아 넣어버리는 치명적인 정보 불일치 사고(Delayed Update)를 막아야 합니다.

Ⅴ. 기대효과 및 결론

BHT는 하드웨어가 소프트웨어의 **'심리'**를 읽어내는 통계적 거버넌스다.

결론적으로 현대 아키텍처는 단순한 2비트 카운터의 한계를 절감하고, 수만 개의 가중치 테이블을 가진 퍼셉트론 (Perceptron) 하드웨어 AI로 BHT를 대체하며 적중률 99%의 벽을 넘보고 있다. 미래에는 칩 내부의 온도와 전압에 따라 BHT의 민감도를 조절하는 자가 적응형 이력 관리 기술이 발전하며, 전력 효율과 성능의 극한을 동시에 달성할 것이다.

📢 섹션 요약 비유: BHT는 과거의 실패를 적어두는 낡은 일기장에서 출발하여, 이제는 수만 가지 변수를 분석해 정답을 외치는 기적의 마법 수정구슬로 진화하며 현대 CPU의 제왕 자리를 지키고 있습니다.

📌 관련 개념 맵

개념	연결 포인트
2-bit Counter	한 번의 실수에 흔들리지 않는 BHT의 핵심 논리
gshare	GHR과 PC를 XOR하여 상관관계를 읽어내는 진화된 BHT
앨리어싱 (Aliasing)	서로 다른 명령어가 같은 BHT 칸을 써서 발생하는 정보 오염
퍼셉트론 예측기	BHT 카운터를 대체하는 차세대 하드웨어 AI 예측 기술

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

선생님이 내는 퀴즈(분기문)를 맞추려고, 똑똑한 반장이 "선생님은 어제도 그제도 답을 4번으로 하셨어!" 하고 수첩(BHT)에 적어둬요.
이 수첩은 선생님이 한 번 답을 바꿨다고 바로 속지 않고, 두 번 연속으로 바꿔야만 비로소 "아, 이제 바뀌었구나" 하고 깨닫는 아주 신중한 수첩이에요.
이 신중한 수첩 덕분에 반 친구들은 미리 정답을 예상하고 공부해서 시험 문제를 빛의 속도로 풀 수 있답니다!