title: 분기 예측
date: 2025-06-26
category: arch
tags: [branch-prediction, pipeline, microarchitecture, BTB, TAGE, perceptron]

분기 예측 (Branch Prediction)

개요

분기 예측(Branch Prediction)은 현대 마이크로아키텍처에서 파이프라인 효율을 극대화하기 위한 핵심 기술이다. 조건 분기 명령어(conditional branch)의 결과가 결정되기 전에 분기의 방향(taken/not taken)을 미리 추측하여, 파이프라인에 불필요한 stall이 발생하는 것을 방지한다. 분기 예측이 없으면 프로세서는 분기 명령어의 결과가 확정될 때까지 다음 명령어의 인출을 지연시켜야 하며, 이는 깊은 파이프라인을 사용하는 현대 프로세서에서 심각한 성능 저하를 초래한다.

분기 미예측(misprediction) 시에는 이미 인출 및 실행된 명령어들을 폐기하고 파이프라인을 다시 채워야 하므로, 파이프라인 깊이만큼의 클럭 사이클이 손실된다. 현대 프로세서는 14~20단계의 파이프라인을 사용하므로, 미예측 시 10~20클럭의 패널티가 발생한다. 따라서 정확한 분기 예측은 프로세서 성능에 결정적인 영향을 미치며, 현대 프로세서는 95% 이상의 예측 정확도를 달성한다.

핵심 개념

분기 유형

분기 예측 메커니즘 구조

분기 예측기는 크게 세 가지 요소로 구성된다:

1. Branch Target Buffer (BTB): 분기 명령어의 주소를 키로 하여 목표 주소를 캐싱
2. Branch History: 과거 분기 결과를 기록 (global 또는 local)
3. Pattern History Table (PHT): 분기 패턴에 따라 최적의 예측을 제공하는 카운터 테이블

분기 예측 정확도와 성능

1%의 정확도 향상이 연간 수천만 클럭의 손실을 줄이므로, 분기 예측기 개선은 프로세서 설계에서 지속적인 연구 대상이다.

비교/분석

분기 예측기 유형 비교

글로벌 vs 로컬 분기 예측

현대 프로세서 분기 예측기 비교

동작 원리

2-bit Saturating Counter

가장 기초적인 동적 분기 예측기로, 4개의 상태를 갖는 유한 상태 머신(FSM)으로 동작한다:

• Strongly Not Taken (00): not taken을 강하게 예측
• Weakly Not Taken (01): not taken을 약하게 예측
• Weakly Taken (10): taken을 약하게 예측
• Strongly Taken (11): taken을 강하게 예측

분기 결과에 따라 상태가 업데이트되며, 예측은 현재 상태의 MSB(Most Significant Bit)를 사용한다. 1-bit 카운터와 달리 두 번 연속으로 예측이 틀려야지만 예측 방향이 바뀌므로, 반복적인 루프 분기에서 더 높은 정확도를 보인다.

Two-level Adaptive Predictor

이전 n개의 분기 결과를 기록한 Branch History Register(BHR)를 사용하여 PHT의 인덱스를 결정한다:

1. BHR에 최근 분기 결과를 저장 (taken=1, not taken=0)
2. BHR 값을 인덱스로 사용하여 PHT에서 2-bit counter를 선택
3. 선택된 counter의 MSB로 예측 수행
4. 분기 결과에 따라 counter를 업데이트

이 방식은 특정 분기 패턴(예: 3번마다 taken되는 패턴)을 학습할 수 있다. n=2인 경우 2²=4개의 counter가 필요하며, 일반적으로 n이 증가하면 예측 정확도가 향상되지만 테이블 크기가 기하급수적으로 증가한다.

Gshare Predictor

글로벌 히스토리와 분기 PC를 XOR 연산하여 PHT를 인덱싱하는 방식이다:

1. Global History Register(GHR)에 최근 N개 분기의 결과를 저장
2. GHR와 분기 명령어의 PC 상위 비트를 XOR
3. XOR 결과를 인덱스로 사용하여 PHT에서 counter 선택
4. 예측 수행 후 counter 업데이트

XOR 연산은 분기 PC와 히스토리 간의 충돌(aliasing)을 줄여, gselect(연결 방식)보다 더 높은 정확도를 보인다.

TAGE (Tagged Geometric History Length) 예측기

여러 길이의 히스토리를 동시에 활용하는 최신 예측기이다:

• 구조: 기본 bimodal 예측기 + 여러 개의 tagged 테이블 (히스토리 길이가 기하급수적으로 증가)
• 동작: 가장 긴 히스토리에서 매칭되는 엔트리를 우선으로 사용
• 장점: 짧은 히스토리 패턴과 긴 히스토리 패턴 모두 예측 가능
• 적용: Intel Haswell 이후, AMD Zen 이후 대부분의 현대 프로세서

Perceptron Predictor

신경망의 퍼셉트론을 활용한 분기 예측기이다:

• 수식: y = w₀ + Σ(wᵢ × hᵢ) (hᵢ는 i번째 히스토리 비트, wᵢ는 가중치)
• 예측: y ≥ 0이면 taken, y < 0이면 not taken
• 학습: 예측이 틀리면 가중치를 업데이트 (wᵢ = wᵢ + t × hᵢ, t는 실제 결과)
• 장점: 히스토리 길이에 비례하는 리소스로 긴 히스토리 활용 가능
• 단점: 덧셈 연산으로 인한 높은 레이턴시

Return Stack Buffer (RSB)

함수 반환 주소를 예측하기 위한 전용 예측기이다:

• 함수 호출 시 반환 주소를 스택에 푸시
• 반환 명령어 시 스택에서 주소를 팝하여 예측
• 일반적으로 4~16개의 엔트리를 가짐
• 재귀 함수, 중첩 호출에서 높은 정확도

장단점

장점

• 파이프라인 효율 극대화: 분기로 인한 stall을 최소화하여 CPI(Clock Per Instruction) 향상
• 심볼릭 실행 지원: Out-of-Order 실행과 함께 사용되어 명령어 수준 병렬성(ILP) 극대화
• 소프트웨어 투명성: 프로그래머의 개입 없이 하드웨어 수준에서 자동으로 최적화
• 지속적 발전: TAGE, perceptron 등의 최신 알고리즘으로 정확도 지속 향상

단점

• 하드웨어 비용: BTB, PHT, GHR 등 추가 하드웨어 소요
• 전력 소모: 복잡한 예측 로직이 전력 소모를 증가시킴
• 보안 취약점: Spectre 등 예측 실행을 악용한 사이드 채널 공격에 취약
• 미예측 패널티: 예측 실패 시 파이프라인 세척으로 심각한 성능 손실

보안 고려사항 (Spectre)

2018년 공개된 Spectre 취약점은 분기 예측기를 악용한 공격이다:

1. 공격자가 분기 예측기를 학습시켜 특정 분기를 taken으로 예측하게 유도
2. 미실행되어야 할 코드가 예측 실행되면서 메모리에 접근
3. 접근된 메모리의 캐시 상태를 측정하여 민감한 데이터 추출

이를 방어하기 위해 Intel, AMD는 분기 예측 제어 명령어(IBPB, STIBP, IBRS)를 도입하였다.

관련 기술

참고 문헌

• Hennessy, J. L., & Patterson, D. A. (2017). Computer Architecture: A Quantitative Approach (6th ed.). Morgan Kaufmann.
• Jimenez, D. A., & Lin, C. (2001). "Dynamic Branch Prediction with Perceptrons". Proceedings of the 7th International Symposium on High-Performance Computer Architecture (HPCA).
• Seznec, A. (2011). "A New Case for the TAGE Branch Predictor". Proceedings of the 44th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO).
• McFarling, S. (1993). "Combining Branch Predictors". Digital Western Research Lab Technical Report, TN-36.
• Fog, A. (2016). "The microarchitecture of Intel, AMD, and VIA CPUs". Technical University of Denmark.

관련 기술 문서

• CPU 마이크로아키텍처 기초
• CPU Cache Architecture
• Virtual Memory

핵심 정리

1. 분기 예측은 파이프라인 stall을 방지하기 위해 분기 결과를 미리 추측하는 핵심 기술로, 현대 프로세서의 성능에 결정적인 영향을 미친다.
2. 2-bit saturating counter에서 TAGE, perceptron까지 예측기의 복잡도와 정확도가 함께 증가하였으며, 현대 프로세서는 95% 이상의 정확도를 달성한다.
3. 글로벌 히스토리는 분기 간 상관관계를 활용하고, 로컬 히스토리는 개별 분기 패턴을 정밀하게 학습하는 장점이 있어, 현대 프로세서는 두 방식을 조합한 하이브리드 예측기를 사용한다.
4. 분기 미예측 시 파이프라인 깊이만큼의 클럭 사이클이 손실되므로, 예측 정확도 1% 향상은 수백만 클럭의 손실을 줄이는 의미 있는 성능 개선이다.
5. Spectre와 같은 보안 취약점으로 인해 분기 예측기는 성능뿐만 아니라 보안 측면에서도 중요한 설계 요소가 되었다.