Out-of-Order Execution (OoO)

1. Overview

비순차 실행(Out-of-Order Execution, OoO)은 프로그램이 작성된 '정적인 순서'라는 제약을 깨고, 실행 가능한 데이터가 준비된 명령어들을 하드웨어가 능동적으로 골라 먼저 처리하는 현대 고성능 프로세서의 '동적 효율화' 정수입니다.

한 명령어가 메모리 접근으로 인해 수백 클록을 멈춰야 할 때, 뒤따르는 독립적인 연산들까지 멈추는 것은 거대한 낭비입니다. 학습자는 **토마술로 알고리즘(Tomasulo's Algorithm)**과 같이 의존성을 실시간으로 확인하는 물리 로직을 배우고, 가짜 의존성을 제거하기 위한 레지스터 리네이밍(Register Renaming) 기술을 익힙니다. 이를 통해 CPU가 어떻게 내부적으로는 무질서하게(Out-of-order) 연산하면서도 유저에게는 질서정연하게(In-order) 결과를 확정(Commit)하여 시스템 무결성을 유지하는지 심층적으로 이해합니다.

2. Scope & Boundaries

In-Scope

• Dynamic Scheduling Physics: 토마술로 알고리즘, 예약 스테이션(Reservation Stations)
• Dependency Elimination: RAW(진성), WAR(반), WAW(출력) 의존성 분류 및 물리적 해결
• Register Renaming: 논리 레지스터를 물리 레지스터로 사상하여 자원 경합 해소
• Retirement Mechanics: Reorder Buffer(ROB)를 통한 순차적 상태 확정 물리

Out-of-Scope

• 단순한 5단 정적 파이프라인 로직 (02-03-01 PHR 영역으로 위임)
• 순수 소프트웨어 기반의 VLIW 스케줄링 기술

Boundaries

• OoO vs. Multi-threading: 멀티스레딩이 '여러 작업 흐름'을 다룬다면, OoO는 '단일 작업 흐름 내의 명령어들'을 하드웨어 수준에서 재배치하는 기술입니다.

3. Counterexample

• 단순히 "명령어를 빨리 하려고 순서를 바꾼다"는 직관은 OoO 학습이 아닙니다. 왜 레지스터의 이름($R1, R2$ 등)이 중복될 때 발생하는 WAR/WAW 의존성이 실제 데이터 흐름과는 무관한 '가짜 의존성'인지 물리적으로 입증할 수 있어야 하고, 실행이 완료된 명령어가 왜 즉각 레지스터에 쓰이지 못하고 **ROB(Reorder Buffer)**에서 자기 차례(In-order retirement)를 기다려야 하는지 예외 처리 관점에서 설명할 수 있어야 합니다.

4. Prerequisites

• Pipeline & Hazard Resolution (Basic): 데이터 해저드와 의존성 기초 지식이 필수입니다. (02-03-01 PHR)
• ALU & Data Path Design (Recommended): 연산 유닛 다중화(Multiple Issue) 환경 이해가 권장됩니다. (02-01-03 ADP)

5. Learning Map

1. Hazard Identification: 데이터가 준비되지 않아 파이프라인이 멈추는 지점을 동적으로 탐색합니다.
2. Resource Renaming: 같은 레지스터 이름을 쓰는 독립적 연산들의 물리적 공간을 분리합니다.
3. Execution Pool: 예약 스테이션에 가동 준비된 명령어들을 모아 ALU로 쏘아 올립니다(Dispatch).
4. Order Recovery: 제멋대로 끝난 결과들을 원래 순서대로 모아 시스템 상태를 안전하게 갱신합니다.

6. Learning Topics

Basic

Core: 동적 스케줄링과 토마술로 알고리즘 (Tomasulo Foundations)

• Why to Learn: 프로그램 실행 중에 하드웨어가 스스로 코드를 최적화하여 멈춤 없는 연산을 수행하게 하기 위함입니다.
• What to Learn:
  • 예약 스테이션(Reservation Station): 연산 대기 주소와 데이터 태그 관리 물리
  • CDB (Common Data Bus): 계산 결과가 모든 대기자에게 동시에 전파되는 방송 체계
  • 데이터 주도 실행(Data-driven Execution)의 원리
• How to Learn:
  • 세 개의 연산 명령이 서로 다른 의존성을 가질 때, 예약 스테이션의 'Busy' 비트와 'Tag'가 어떻게 물리적으로 변하는지 추적 실습
  • 정적 스케줄링(Scoreboarding) 대비 토마술로 방식의 물리적 우위 분석
• Implement: 특정 명령어 시퀀스에 대해 예약 스테이지와 연산 유닛의 상태 변화를 출력하는 시뮬레이터

Recommended

Core: 레지스터 리네이밍과 의존성 제거 (Register Renaming)

• Why to Learn: 한정된 레지스터 이름 때문에 발생하는 인위적인 병목을 하드웨어 확장을 통해 돌파하기 위해서입니다.
• What to Learn:
  • 논리 레지스터(Architecture Registers) vs 물리 레지스터(Physical Pool)
  • RAT (Register Alias Table): 이름과 실제 물리 위치의 사상 물리
  • WAR/WAW 해저드가 리네이밍을 통해 어떻게 '자원 경합' 문제로 치환되어 해결되는지 이해
• How to Learn:
  • 동일한 $R1$ 레지스터를 서로 다른 용도로 쓰는 코드 서너 줄을 설계하고, 물리 레지스터 할당 과정을 단계별 작도 실습
  • 리네이밍 풀(Pool) 크기가 작을 때 발생하는 파이프라인 스톨 현상 분석
• Implement: RAT 테이블을 유지하며 주소 지정 방식을 변환해주는 리네이밍 로직 모듈

Practical

Core: 리오더 버퍼와 상태 확정 (The Reorder Buffer)

• Why to Learn: 비순차 실행 중 예외(Exception)나 인터럽트가 발생했을 때, 시스템을 정교하게 '과거의 질서 있는 상태'로 되돌리기 위해서입니다.
• What to Learn:
  • ROB의 구조: 순환 큐(Circular Queue) 형태의 결과 저장소 물리
  • Retirement (Commit): 연산 결과가 실제 아키텍처 레지스터에 영구히 반영되는 시점
  • Precise Exceptions: 예외 발생 지점 이전은 모두 반영하고 이후는 폐기하는 물리적 무결성
• How to Learn:
  • 뒤쪽 명령어는 끝났는데 앞쪽 명령어에서 '0으로 나누기' 예외가 발생했을 때, 어떻게 전체 상태를 롤백하는지 시나리오 분석
  • ROB의 깊이가 전체 프로세서의 '투기 윈도우(Speculation Window)' 크기를 결정하는 수리적 관계 분석
• Implement: 실행 완료 순서와 상관없이 ROB 인덱스 순서대로 데이터를 확정하는 큐 관리 로직

Advanced

Core: 다중 이슈와 슈퍼스칼라 (Superscalar Physics)

• Why to Learn: 한 클록에 여러 개의 명령어를 동시에 뽑아내고(Fetch) 쏘아 올리는(Issue) 극한의 병렬 구조를 이해하기 위해서입니다.
• What to Learn:
  • 다중 명령어 배정(Multi-issue)의 하드웨어적 병목
  • 정적 슈퍼스칼라 vs 동적 슈퍼스칼라의 물리적 효율 차이
  • IPC (Instructions Per Cycle)의 한계와 데이터 의존도(ILP)의 수학적 상관관계
• How to Learn:
  • 4-way 슈퍼스칼라 CPU에서 명령 주소 계산과 정렬(Alignment)이 왜 물리적으로 어려운 고난도 작업인지 분석 실습
  • 실제 Intel/AMD 아키텍처의 프론트엔드와 백엔드 구조를 보고 OoO 로직의 비중 확인
• Implement: 병렬 실행 가능한 명령어 수를 계산하고 최적의 연산 유닛 배정 순서를 제안하는 스케줄러 알고리즘

7. Terminology

8. References

Primary

• [P1] CS2023 - AR/Instruction-Level Parallelism — Core requirements.
• [P2] SWEBOK v4.0 - Computing Foundations / Pipeline and Parallelism — Structural standards.

Secondary

• [Modern Processor Design: Fundamentals of Superscalar Processors] Shen & Lipasti — The "Orange Book" for OoO.
• [Computer Architecture: A Quantitative Approach] Hennessy & Patterson — Detailed Tomasulo analysis.

Industry

• [Intel Core Microarchitecture: Out-of-Order Executive] — Real-world silicon details.
• [The Apple M1/M2 Architecture: Large OoO Window analysis] — Industry leading implementation.

9. Final Checklist

Primary

• 토마술로 알고리즘에서 'CDB(Common Data Bus)'를 통한 데이터 전파가 왜 레지스터에 기록하는 물리적 지연을 우회할 수 있게 하는지 설명 가능한가? (P1)
• 'Register Renaming'이 없을 때, 동일한 레지스터 이름을 쓰는 두 명령어가 가져오는 '가짜 의존성(Output Dependency)'의 전형적인 사례를 입증할 수 있는 가? (P1)

Secondary

• 예측 실패(Misprediction) 시, 'ROB'의 포인터를 되돌리는 것만으로 어떻게 시스템의 모든 투기적 변화를 한꺼번에 리셋할 수 있는지 물리적 과정을 소통 가능한가?
• 'Reservation Station'의 개수가 프로세서의 처리량 임계치를 어떻게 수리적으로 제한하는지 병목 인자를 찾아낼 수 있는 가?

Industry

• 클라우드 서버 CPU 선택 시, 윈도우 사이즈(OoO Window)가 큰 최신 아키텍처가 특정 워크로드(예: DB 쿼리)에서 왜 압도적인지 하드웨어 사상 근거로 제안할 수 있는 가? (SFIA)
• CPU의 실시간 모니터링 태스크 중 'Pipeline Stall'의 주원인이 데이터 의존성 때문인지, 자원 부족 때문인지 리네이밍 통계를 통해 분석 가능한가?