분기 예측으로 파이프라인 정체를 줄이는 프로세서 설계
분기 방향과 목적지 예측, BTB·RAS·추측 실행 복구가 프로세서 파이프라인 성능에 미치는 영향을 정리한다.
2026-08-14 · 최초 발행 2026-01-06
분기가 파이프라인을 멈추게 하는 지점
조건 분기는 다음에 가져올 명령어의 주소를 확정하기 전까지 인출 경로를 결정할 수 없게 만든다. 결과를 기다리는 동안 파이프라인은 끊기고, 분기마다 수 사이클의 지연이 생긴다. 전체 명령어에서 분기 명령어가 차지하는 비율은 15-25%이므로 이 지연은 누적된다. 예측이 틀리면 이미 진행한 파이프라인 전체를 무효화해야 한다.
파이프라인이 14 단계이고 분기 비율이 20%이며, 예측 실패 때 14 사이클을 잃는 상황을 생각해 볼 수 있다.
파이프라인 길이: 14 단계
분기 비율: 20%
예측 실패 시 손실: 14 사이클
예측 없이: 20% × 14 = 평균 2.8 사이클 손실/명령어
95% 정확도: 20% × 5% × 14 = 0.14 사이클 손실/명령어
→ 약 20배 성능 향상
분기 예측은 이 공백을 줄이기 위해 방향과 목적지를 미리 추정한다. 방향 예측은 분기가 taken인지 not-taken인지를, 목적지 예측은 taken일 때 어느 주소로 갈지를 담당한다.
정적 규칙과 실행 이력을 이용한 방향 예측
가장 단순한 정적 방식은 모든 분기를 taken으로 본다. 루프의 백워드 분기가 taken일 가능성이 높다는 점을 활용하며, 추가 회로 없이 60-70%의 정확도를 낼 수 있다. 정확도는 워크로드에 따라 달라진다.
BTFN(Backward Taken, Forward Not-taken)은 분기 방향을 기준으로 예측을 나눈다. 백워드 분기는 루프가 계속된다고 보고 taken으로, 포워드 분기는 조건이 실패한다고 보고 not-taken으로 처리한다. 이 방식의 정확도는 65-75%이며 판단 기준이 분기 방향으로 제한돼 단순하다.
프로파일 기반 예측은 프로그램 실행 프로파일을 수집한 뒤 컴파일러 통계를 명령어의 힌트 비트에 인코딩한다. 실행 패턴이 고정적인 경우에 효과가 있으며 정확도는 80-85%다.
동적 예측기는 이전 실행 결과를 저장해 다음 결과를 추정한다. 1비트 예측기는 taken과 not-taken 상태를 두고 마지막 실행 결과로 상태를 바꾼다. 하지만 루프의 진입과 탈출에서 연속으로 두 번 실패할 수 있다.
루프 반복 시 패턴: T T T T T N (taken 5회, not-taken 1회)
1비트 예측: 루프 마지막에서 N 예측 실패 → 다음 루프 시작에서 T 예측 실패
→ 정확도 4/6 = 66.7%
2비트 포화 카운터는 Strongly Taken, Weakly Taken, Weakly Not-taken, Strongly Not-taken 상태를 둔다. 반대 결과가 2번 연속 나타나야 예측 방향을 바꾸므로, 루프의 진입과 탈출에서 실패를 1번으로 제한한다. 정확도는 85-90%다.
상태 전이도:
11 (ST) <--> 10 (WT) <--> 01 (WN) <--> 00 (SN)
Taken Not-taken Taken
지역 분기 히스토리는 각 분기의 과거 결과를 PHT(Pattern History Table)에 기록한다. 히스토리 레지스터는 최근 N회 분기 결과를 비트 벡터로 보관하고, 분기 PC와 히스토리로 PHT에 접근한다. 정확도는 90-93%다.
전역 분기 히스토리는 모든 분기의 최근 결과를 GHR(Global History Register)에 담아 분기 간 상관성을 이용한다. gshare는 PC ⊕ GHR를 PHT 인덱스로 사용하며 92-95%의 정확도를 보인다.
서로 다른 예측기를 조합하는 방식
Tournament Predictor는 지역 예측기와 전역 예측기를 동시에 운용하고, 메타 예측기가 어느 쪽이 더 정확한지를 학습한다. 분기 패턴에 따라 선택을 바꾸며 95-97%의 정확도를 목표로 한다.
Alpha 21264 예측기는 지역·전역·선택기를 함께 둔 구성의 예다.
구성:
- 지역 예측기: 1024 엔트리 × 10비트 히스토리
- 전역 예측기: 4096 엔트리 × 12비트 GHR
- 선택기: 4096 엔트리 × 2비트 카운터
TAGE(TAgged GEometric history length)는 서로 다른 히스토리 길이를 가진 다층 테이블을 사용한다. 긴 히스토리가 태그와 매치되면 이를 우선하고, 분기마다 적합한 히스토리 길이를 자동으로 선택한다. 최신 기술로서 정확도는 97-98%다.
BTB와 RAS가 목적지 주소를 찾는 방법
BTB(Branch Target Buffer)는 분기 PC를 태그로 삼아 목적지 주소를 저장하는 캐시 유사 구조다. 명령어 인출 단계에서 즉시 조회하며, 엔트리는 [Valid | Tag | Target Address | Prediction]으로 구성된다. 용량은 512-4096 엔트리이고 연관도는 2-4다.
BTB 접근을 빠르게 하기 위해 연관 캐시의 way를 예측하는 Way Prediction, 교체된 엔트리를 작은 캐시에 보관하는 Victim Cache, 작은 L0 BTB와 큰 L1 BTB를 결합하는 Micro-BTB를 사용할 수 있다.
함수 반환은 RAS(Return Address Stack)가 처리한다. RAS는 LIFO 구조로 반환 주소를 저장하며, CALL 명령어는 주소를 Push하고 RETURN 명령어는 Pop한 주소를 목적지로 예측한다. 재귀 깊이 제한 안에서는 정확도가 거의 100%다.
RAS는 8-32 레벨의 함수 호출 깊이를 수용한다. 깊은 재귀에서는 오래된 엔트리가 덮어써질 수 있다. 잘못 예측한 경로에서도 Push와 Pop이 투기적으로 수행되므로, 예측 실패 때 RAS 상태를 복원하는 메커니즘이 필요하다.
간접 분기는 함수 포인터, 가상 함수, switch-case처럼 실행 중 목적지가 달라진다. 같은 PC가 여러 목적지를 가질 수 있어 단순 BTB만으로는 정확도가 낮다. 최근 목적지를 여러 개 저장하는 Target Cache, 히스토리를 쓰는 Two-Level 예측, 경로 히스토리로 목적지를 인덱싱하는 Tagged Target이 대응 방식이며 정확도는 직접 분기보다 낮은 80-90%다.
긴 상관관계를 다루는 예측기
Perceptron 예측기는 간단한 신경망 구조를 이용한다. 히스토리 비트마다 가중치를 둔 테이블을 사용하고 예측 실패 시 가중치를 조정한다. 복잡한 패턴을 학습할 수 있으며 정확도는 95-97%다.
Neural Branch Prediction은 다층 퍼셉트론이나 LSTM을 활용하는 방식이다. 하드웨어 구현에서는 지연과 전력 문제가 생기며 실제 프로세서 적용은 제한적이다. 이론상 99% 이상 정확도의 잠재력이 있다.
경로 기반 예측은 분기 결과뿐 아니라 최근 분기들의 PC 시퀀스도 기록한다. PPM(Prediction by Partial Matching) 같은 압축 알고리즘을 응용해 상관관계를 넓히며 정확도는 96-98%다.
추측 실행이 실패했을 때 되돌리는 과정
예측 결과를 바탕으로 분기 결과가 확정되기 전에 명령어를 실행하는 것이 투기적 실행이다. ROB(Reorder Buffer)는 순서와 다르게 완료된 결과를 임시로 보관하고, 분기가 확정된 뒤에야 결과를 아키텍처 상태에 반영한다.
예측이 틀리면 파이프라인 단계 수만큼 명령어를 폐기해야 한다. 투기 경로에서 갱신한 BTB와 RAS도 취소하고, 잘못된 경로가 데이터를 캐시에 채워 발생한 캐시 오염도 감수해야 한다. 무효화될 명령어를 실행하는 동안의 전력 역시 낭비된다.
프로세서 설계에서 보이는 구성
Intel Skylake는 TAGE와 Loop Detector로 방향을 예측하고, L1 4K 엔트리와 L2 16K 엔트리 BTB를 둔다. RAS는 32 엔트리이며 정확도는 약 97-98%다.
AMD Zen 3는 TAGE와 하이브리드한 Perceptron 기반 예측을 사용한다. BTB는 6.5K 엔트리이고, 간접 분기에는 고급 타겟 캐시를 사용하며 정확도는 약 96-97%다.
ARM Cortex-A76은 지역 예측기와 전역 예측기를 결합한 Dynamic Predictor를 사용한다. BTB는 6K 엔트리, 3-way 구성이고 RAS는 16 엔트리다. 정확도와 전력의 균형을 고려한 저전력 최적화가 특징이다.
성능·보안·이기종 환경의 설계 과제
온칩 NPU를 전용 신경망 가속기로 활용하거나, 애플리케이션 프로파일을 오프라인에서 미리 학습하고 실행 중 온라인 학습을 이어 가는 적응형 모델은 예측기 발전 방향이다.
추측 실행은 Spectre 공격처럼 정보 유출에 악용될 수 있다. 투기 실행을 제한하거나 캐시를 격리하는 완화 기법이 필요하지만, 보안 패치로 5-30%의 성능 저하가 발생할 수 있다.
GPU에서는 워프 내부의 분기 발산을 처리해야 하며, AI 가속기는 제어 흐름을 최소화하는 방향으로 설계된다. 이기종 컴퓨팅에서는 도메인 특화 커스텀 예측기도 고려 대상이 된다.
1990년대의 단순한 2비트 예측기에서 출발한 분기 예측은 오늘날 머신러닝 기법을 활용해 97% 이상의 정확도를 달성하고 있다. 방향과 목적지 예측을 결합해 높은 클럭 속도와 깊은 파이프라인의 처리 효율을 뒷받침하지만, 성능과 추측 실행 보안 사이의 균형은 계속되는 설계 과제다.