Speculative Execution & Branching

1. Overview

추측 실행과 분기 예측(Speculative Execution & Branching, SEB)은 파이프라인이 길어질수록 분기(Branch) 예측 실패 한 번으로 큰 플러시(Flush) 비용이 생기는 문제를 줄이기 위해, CPU가 가능성이 높은 경로를 미리 실행하는 성능 최적화 기법입니다.

학습자는 분기문(if, for)이 어느 방향으로 갈지 과거 실행 패턴을 바탕으로 예측하는 동적 분기 예측(Dynamic Branch Prediction) 하드웨어를 살펴보고, 분기 타겟 버퍼(BTB)와 2비트 포화 카운터(Saturating Counter)의 동작을 분석합니다. 이어 예측이 맞는 동안 뒤의 명령어를 미리 실행하고, 틀렸을 때는 임시 결과를 취소하는 **추측 실행(Speculative Execution)**의 복구 절차를 이해합니다.

2. Scope & Boundaries

In-Scope

• 정적 vs 동적 예측 (Static vs Dynamic Prediction): 고정 휴리스틱과 과거 실행 이력을 이용한 예측의 차이.
• 분기 예측기 하드웨어 (Branch Predictor Hardware): 1비트/2비트 상태 머신, BHT(Branch History Table), 히스토리 기반 예측.
• 분기 타겟 버퍼 (Branch Target Buffer, BTB): 분기 목적지 주소(Target Address)를 저장해 Fetch 단계의 다음 PC 결정을 앞당기는 구조.
• 추측 실행 물리 (Speculative Execution): 예측 경로의 명령어를 임시로 실행하고, 예측 실패 시 취소(Squash/Flush)하는 절차.

Out-of-Scope

• 추측 실행 보안 취약점 심화: 스펙터(Spectre)와 멜트다운(Meltdown) 공격 코드 수준의 데이터 탈취 원리 $\rightarrow$ 02-04-01. Microarchitectural Attacks 영역.
• 비순차 실행(OoO) 커밋 역학: 레지스터 르네이밍(Renaming), 예약 스테이션, ROB 구조의 상세 동작 $\rightarrow$ 02-03-03. Out-of-Order Execution 영역.

Boundaries

• SEB vs. Pipeline Hazards (02-03-01): 파이프라인 해저드는 분기 때문에 발생하는 빈칸(Bubble)과 플러시 비용을 다루고, SEB는 그 비용을 줄이기 위해 분기 방향과 목적지를 미리 예측한 뒤 명령어를 앞당겨 실행하는 전략을 다룹니다.

3. Counterexample

• 정렬되지 않은 배열의 if문 병목 (Unsorted Array Branch Thrashing): C/C++에서 배열을 순회하며 if (arr[i] > 128) 조건에 맞는 값만 더할 때, 배열이 무작위로 섞여 있으면 분기 예측기가 일관된 패턴을 배우기 어렵습니다. 예측 실패가 반복되면 플러시 비용이 누적되고, 배열을 정렬했을 때보다 실행 시간이 크게 늘 수 있습니다.
• 추측 실행의 캐시 오염 (Speculative Cache Pollution): 예측이 틀리면 레지스터 상태는 롤백할 수 있지만, 추측 경로에서 이미 가져온 캐시 라인은 흔적을 남길 수 있습니다. 이 특성은 성능 저하뿐 아니라 Spectre 계열 사이드채널 취약점의 배경이 됩니다.

4. Prerequisites

• 파이프라인 제어 해저드 (Basic): 분기 예측이 틀렸을 때 발생하는 플러시 페널티와 제어 해저드의 기본 구조를 알고 있어야, 분기 예측과 추측 실행이 왜 필요한지 이해할 수 있습니다. (02-03-01 PHR)

5. Learning Map

6. Learning Topics

Basic

Core Topic 01: 분기 페널티와 예측 필요성 (Branch Prediction Need)

• Why to Learn: 현대 CPU의 파이프라인은 깊고, 분기 결과가 늦게 확정될수록 잘못 가져온 명령어를 버리는 비용이 커집니다. 분기 예측은 이 대기 시간을 줄이기 위한 기본 장치입니다.
• What to Learn:
  • Concepts: 정적 분기 예측(Static Branch Prediction), 파이프라인 깊이(Pipeline Depth), 분기 페널티(Branch Penalty).
  • Skills: 루프 분기와 조건 분기의 통계적 패턴 구분.
  • Tools: CPI 비용 계산과 제어 해저드 시나리오.
  • Trade-offs: 정적 예측은 회로 비용이 낮지만 패턴 변화에 둔감하고, 동적 예측은 정확도를 높이는 대신 예측 테이블과 갱신 로직 비용을 요구합니다.
• How to Learn:
  • 1단계: 깊은 파이프라인에서 분기 결과가 EX 단계 이후에 확정될 때, 예측 실패로 버려야 하는 명령어 수를 계산합니다.
  • 2단계: "뒤로 가는 분기는 루프일 가능성이 높다" 같은 정적 휴리스틱이 언제 유용하고 언제 실패하는지 예제로 비교합니다.
• Implement: 20단 파이프라인에서 분기 비율과 예측 정확도를 입력받아 CPI 증가분을 계산하는 간단한 비용 계산기 작성.

Recommended

Core Topic 02: 동적 예측기와 2비트 포화 카운터 (Dynamic Predictors & 2-bit Counter)

• Why to Learn: 프로그램의 분기 패턴은 반복되는 경우가 많습니다. 동적 예측기는 과거 실행 이력을 저장해 같은 분기가 다음에 어떤 방향으로 갈지 더 안정적으로 예측합니다.
• What to Learn:
  • Concepts: 동적 분기 예측(Dynamic Prediction), BHT(Branch History Table), 2비트 포화 카운터(Saturating Counter).
  • Skills: 1비트 예측기의 루프 진입/탈출 실패 분석, 2비트 상태 전이 해석.
  • Tools: 강한 Taken/약한 Taken/약한 Not Taken/강한 Not Taken FSM 다이어그램.
  • Trade-offs: 1비트 예측기는 작고 빠르지만 일시적인 예외에 바로 흔들립니다. 2비트 예측기는 상태를 한 번 더 확인해 안정성을 높이지만 저장 공간이 늘어납니다.
• How to Learn:
  • 1단계: 분기 명령어 주소(PC)의 일부를 인덱스로 써서 BHT 엔트리를 찾고, 해당 엔트리가 방향 예측 상태를 저장하는 흐름을 그립니다.
  • 2단계: $T, T, T, T, N$ 패턴에서 1비트 예측기와 2비트 예측기가 각각 몇 번 틀리는지 상태 전이로 비교합니다.
• Implement: 분기 결과 배열을 입력받아 1비트 예측기와 2비트 포화 카운터의 예측 적중률을 비교 출력하는 시뮬레이터 작성.

Practical

Core Topic 03: 분기 목적지 버퍼와 Fetch 지연 단축 (Branch Target Buffer, BTB)

• Why to Learn: 방향 예측이 맞더라도 목적지 주소를 늦게 계산하면 Fetch 단계가 기다려야 합니다. BTB는 과거에 계산한 분기 목적지를 저장해 다음 PC 결정을 앞당깁니다.
• What to Learn:
  • Concepts: 분기 타겟 버퍼(BTB), PC 태그 매칭, Fetch 단계 예측.
  • Skills: 현재 PC와 저장된 타겟 주소 매핑, BTB hit/miss 해석.
  • Tools: 해시 테이블형 하드웨어 캐시 모델.
  • Trade-offs: BTB가 크면 더 많은 분기 목적지를 기억할 수 있지만, 면적과 전력 비용이 커지고 잘못된 엔트리 충돌 가능성도 관리해야 합니다.
• How to Learn:
  • 1단계: BTB 엔트리가 현재 분기 명령어 주소를 태그로, 이전에 계산된 목적지 주소를 값으로 저장하는 구조를 표로 정리합니다.
  • 2단계: BHT가 Taken을 예측하고 BTB도 hit인 경우, Fetch 단계에서 다음 PC가 곧바로 타겟 주소로 바뀌는 흐름을 추적합니다.
• Implement: 현재 PC가 BTB_Dict에 있고 방향 예측이 Taken이면, 추가 목적지 계산 없이 PC를 BTB_Dict[PC]로 갱신하는 분기 Fetch 시뮬레이터 작성.

Advanced

Core Topic 04: 추측 실행과 취소 절차 (Speculative Execution & Squash)

• Why to Learn: 분기 결과가 확정될 때까지 기다리면 성능이 떨어집니다. 추측 실행은 예측 경로의 명령어를 먼저 실행하되, 확정 전 결과를 임시 상태로 관리해 실패 시 되돌릴 수 있게 합니다.
• What to Learn:
  • Concepts: 추측 실행(Speculative Execution), 롤백(Rollback), 취소(Squash/Flush), 커밋 전 임시 상태.
  • Skills: 추측 윈도우(Speculation Window) 추적, 예측 실패 시 임시 결과 폐기.
  • Tools: ROB와 커밋 단계의 승인 모델.
  • Trade-offs: 예측이 맞으면 대기 시간을 줄여 성능을 높일 수 있지만, 틀리면 실행한 작업을 버려야 하고 캐시/전력 비용도 발생합니다.
• How to Learn:
  • 1단계: 추측 상태의 연산 결과가 곧바로 아키텍처 레지스터에 쓰이지 않고, 커밋 전까지 임시 버퍼에 머무르는 이유를 확인합니다.
  • 2단계: 예측 실패(Misprediction)가 확인되면 젊은 명령어의 valid_bit를 끄고, PC와 임시 상태를 올바른 경로로 복원하는 흐름을 추적합니다.
• Implement: 추측 플래그를 가진 가상 CPU에서 분기 이후 명령어의 결과를 shadow_regs에만 기록하고, 예측 실패 시 shadow_regs를 비워 원래 regs가 오염되지 않았음을 확인하는 롤백 매니저 작성.

7. Terminology

8. References

Primary

• [P1] CS2023 - AR/Pipelining and Instruction-Level Parallelism — Branch/Spec standards.
• [P3] CyBOK v1.1 - Hardware Security / Microarchitectural Attacks — Speculation risks.

Secondary

• [Computer Architecture: A Quantitative Approach] Hennessy & Patterson — The source for prediction algorithms.
• [Modern Processor Design] John Paul Shen — Implementation details of spec-ex.

Industry

• [Intel 64 and IA-32 Architectures Optimization Reference Manual] — Real-world prediction behaviors.
• [Google Project Zero: Reading privileged memory with a side-channel] — The Spectre research.

9. Final Checklist

Primary

• 2비트 분기 예측기가 루프 내의 '단 한 번의 이례적인 분기 실패'에 대해 왜 1비트보다 물리적으로 안정적인지 상태 전이로 설명 가능한가? (P1)
• '분기 페널티'가 15클록인 CPU에서 예측 정확도가 10% 떨어졌을 때, 시스템 전체 CPI에 미치는 물리적 영향을 수치로 도출할 수 있는가? (P1)

Secondary

• 'BTB'가 단순히 방향만 알려주는 것을 넘어, 어떻게 '타겟 명령어'를 미리 가져오는 시간을 수리적으로 단축하는지 소통 가능한가?
• 예측이 틀렸을 때 하드웨어가 수행하는 'Flush' 작업이 왜 전력 소모 측면에서 비용이 큰지 물리적으로 입증할 수 있는가?

Industry

• 고성능 서버 아키텍처 설계 시, Spectre 취약점을 방지하기 위해 'Speculative Barrier' 명령어를 어느 지점에 삽입해야 하는지 제안할 수 있는가? (SFIA)
• 컴파일러 최적화 시, 하드웨어 분기 예측기의 특성(BTB 사이즈 등)을 고려하여 분기 패턴을 재배치하는 전략을 수립할 수 있는가?