Speculative Execution & Branching

1. Overview

투기적 실행 및 분기 예측(Speculative Execution & Branching, SEB)은 프로세서가 "모든 것이 확실해질 때까지 기다리는" 비효율을 깨고, 미래의 결과를 미리 짐작하여 도박처럼 연산을 미리 수행하는 하위 물리 계층의 초고속 전술입니다.

현대 CPU 파이프라인은 분기문의 결과가 나올 때까지 기다리기에는 너무나 깊고 빠릅니다. 학습자는 과거의 패턴을 기록하는 **분기 예측기(Branch Predictor)**의 구조와, 예측에 기반해 미리 연산한 뒤 틀리면 되돌리는 **투기적 실행(Speculative Execution)**의 물리적 비용을 배웁니다. 이는 단순한 하드웨어 동작 이해를 넘어, 왜 예측 실패가 시스템 성능의 낭떠러지가 되는지, 그리고 이러한 투기 과정이 메모리에 남기는 물리적 흔적이 어떻게 보안 위협(Spectre 등)으로 연결되는지 통찰하는 역량을 제공합니다.

2. Scope & Boundaries

In-Scope

• Branch Prediction Logic: 1-bit, 2-bit 카운터 및 상관 예측(Correlated Prediction) 물리
• Branch Target Buffer (BTB): 분기할 주소까지 미리 저장하여 Fetch 단계를 가속하는 구조
• Speculative Mechanics: 리오더 버퍼(ROB)를 통한 투기 결과의 가상 저장과 확정(Commit)
• Misprediction Penalty: 예측 실패 시 파이프라인을 비우고 상태를 복구하는 물리적 비용

Out-of-Scope

• 비순차 실행(OoO)의 스케줄링 및 리네이밍 상세 (02-03-03 OoO 영역으로 위임)
• 소프트웨어 단위의 분기문 최적화(If-conversion) 컴파일러 기술 (05. 영역으로 위임)

Boundaries

• SEB vs. Pipeline: 파이프라인이 '일을 겹쳐서 하는 구조'라면, SEB는 그 구조 안에서 '어느 일을 먼저 할지 도박하는 지능'에 집중합니다.

3. Counterexample

• 단순히 "빠르게 실행하려고 미리 해본다"는 직관은 SEB 학습이 아닙니다. 왜 분기문에서 80% 이상의 정확도를 가진 **2비트 포화 카운터(2-bit saturating counter)**가 1비트 방식보다 물리적으로 왜 안정적인지 수치로 입증할 수 있어야 하고, 예측이 실패했을 때 하드웨어가 레지스터 상태를 **롤백(Rollback)**하기 위해 어떤 물리적 백업 데이터를 유지하는지 설명하지 못한다면 SEB의 핵심을 놓치고 있는 것입니다.

4. Prerequisites

• Pipeline & Hazard Resolution (Basic): 제어 해저드와 파이프라인 플러시(Flush) 지식이 필수입니다. (02-03-01 PHR)
• Cache Design & Locality (Recommended): 예측 데이터 저장소의 접근 지연 시간 이해가 권장됩니다. (02-02-01 CDL)

5. Learning Map

1. Prediction Foundations: 분기가 일어났던 과거의 역사를 기록하는 하드웨어 장부를 구축합니다.
2. Execution Gambling: 확신이 없어도 한 쪽 길을 선택하여 명령어를 파이프라인에 밀어 넣습니다.
3. Commit or Squash: 결과가 판명된 후, 성공 시 기록을 확정하고 실패 시 모든 물리적 변화를 취소합니다.
4. Security Awareness: 이 '도박'의 과정에서 발생하는 부수적인 메모리 접근이 남기는 물리적 흔적(Side-channel)을 인지합니다.

6. Learning Topics

Basic

Core: 정적 및 동적 분기 예측 (Branch Prediction Basics)

• Why to Learn: 매번 파이프라인을 멈추는 대신, 높은 확률의 추측으로 흐름을 유지하기 위함입니다.
• What to Learn:
  • 정적 예측: 무조건 예측, 방향 기반(Backward Taken, Forward Not-taken) 물리
  • 동적 예측: 실행 중에 예측 정보를 업데이트하는 1-bit 예측기
  • 분기 페널티: 틀렸을 때 버려지는 클록 사이클의 정량적 계산
• How to Learn:
  • 특정 루프에서 1-bit 예측기가 처음과 끝에서 어떻게 틀리는지 단계별 추적 실습
  • $Penalty \times Miss\_Rate$ 공식을 통한 전체 CPI 저하 효과 계산 연습
• Implement: 입력된 분기 이력을 바탕으로 다음 분기 결과를 추측하는 기본 예측기 시뮬레이션

Recommended

Core: 2비트 카운터와 BTB (Advanced Predictors)

• Why to Learn: 한 번의 특이값(Exception)에 의해 예측 모델이 통째로 흔들리는 것을 방지하기 위해서입니다.
• What to Learn:
  • 2비트 포화 카운터(Saturating Counter): $Strongly \rightarrow Weakly$ 상태 전이 물리
  • Branch Target Buffer: "어디로 갈 것인가"를 Fetch 단계에서 즉각 결정하는 저장소
  • 전역 vs 지역 분기 정보의 상관관계 분석
• How to Learn:
  • if(a) if(b) 처럼 의존성이 있는 분기문에서 상관 예측기가 어떻게 정확도를 높이는지 시나리오 분석 실습
  • BTB 히트 시 명령 주소를 계산(Calculation)하지 않고 바로 점프하는 시간적 이득 정량화
• Implement: 2비트 상태 머신을 각 분기 주소별로 유지하며 정확도를 보고하는 BTB 시뮬레이터

Practical

Core: 투기적 실행과 롤백 메커니즘 (Speculative Operations)

• Why to Learn: 틀릴 수 있음에도 불구하고 연산을 미리 수행했을 때 하드웨어가 무결성을 유지하는 비결을 배우기 위해서입니다.
• What to Learn:
  • Reorder Buffer (ROB): 연산 결과를 실제 레지스터에 쓰기 전 보관하는 물리적 완충지대
  • Commit (확정): 예측이 성공했을 때만 영구적으로 상태를 반영하는 과정
  • 취소 및 복구: 실패 시 ROB를 비우고 PC를 올바른 곳으로 돌리는 물리적 리셋
• How to Learn:
  • 예측 경로 상에서 이미 메모리 로드(Load)를 수행했을 때, 예측 실패 시 해당 메모리 값을 어떻게 물리적으로 무효화하는지 분석
  • 'Shadow Register' 기술을 이용한 초고속 롤백 메커니즘 연습
• Implement: 명령 시퀀스를 실행하다가 특정 시점에 '예측 실패' 신호를 줄 때 시스템 상태를 복구하는 시뮬레이션

Advanced

Core: 보안상 미치는 영향 (Spectre & Meltdown Side-channels)

• Why to Learn: 투기적 실행이라는 성능 최적화가 현대 보안의 가장 큰 아킬레스건이 된 물리적 이유를 파악하기 위해서입니다.
• What to Learn:
  • 투기적 실행이 남기는 '부수적 흔적': 캐시는 비워지지 않는다(Cache footprint)
  • Spectre 공격 원리: 잘못된 경로를 투기적으로 실행하게 유도하여 비밀 정보를 캐시에 남기는 물리
  • 하드웨어적 완화책: 지연 시간 강제 추가, 캐시 격리 기술
• How to Learn:
  • 예측 실패 후 파이프라인은 취소되지만, 그 과정에서 당겨온 데이터가 왜 여전히 L1 캐시에 남아 있는지 물리적 경로 추적 실습
  • 성능과 보안 사이의 근본적인 하드웨어 설계 트레이드오프 토론
• Implement: 파이프라인 실행 중 캐시 상태를 관찰하여 투기적 실행으로 인한 정보 누설 가능성을 탐지하는 로직

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 사이즈 등)을 고려하여 분기 패턴을 재배치하는 전략을 수립할 수 있는 가?