Out-of-Order Execution (OoO)

1. Overview

비순차 실행(Out-of-Order Execution, OoO)은 코드에 적힌 순서를 그대로 기다리는 대신, 데이터 의존성이 풀린 명령어부터 먼저 실행해 파이프라인 정지 시간을 줄이는 CPU의 동적 스케줄링 하드웨어입니다.

학습자는 명령어 수준 병렬성(Instruction-Level Parallelism, ILP)을 실제로 끌어내기 위해 CPU가 어떻게 레지스터 르네이밍(Register Renaming), 예약 스테이션(Reservation Station), **재정렬 버퍼(Reorder Buffer, ROB)**를 조합하는지 분석합니다. 실행은 순서가 바뀔 수 있지만 커밋은 원래 프로그램 순서를 지켜야 한다는 제약까지 함께 다루며, 최신 CPU 백엔드가 성능과 정확성을 동시에 맞추는 구조를 익힙니다.

2. Scope & Boundaries

In-Scope

• 동적 스케줄링 (Dynamic Scheduling): 준비된 명령어를 먼저 실행하도록 발행(Issue) 순서를 조정하는 백엔드 제어.
• 레지스터 르네이밍 (Register Renaming): 논리 레지스터 이름 때문에 생기는 가짜 의존성을 물리 레지스터 매핑으로 제거하는 구조.
• 예약 스테이션과 CDB (Reservation Station & Common Data Bus): 피연산자 준비 상태를 태그로 추적하고 결과를 대기 중인 명령어에 전파하는 구조.
• ROB와 정확한 커밋 (Reorder Buffer & Precise Commit): 비순차로 끝난 결과를 프로그램 순서대로 확정하고 예외 상태를 정확하게 보존하는 메커니즘.

Out-of-Scope

• 분기 예측기 세부 알고리즘: BHT, BTB, 2비트 카운터, 전역/지역 히스토리 기반 예측 $\rightarrow$ 02-03-02. Speculative Execution & Branching 영역.
• 언어 수준 메모리 모델: C++/Java 메모리 모델, acquire/release, happens-before 규칙 $\rightarrow$ 02-02-03. Memory Barriers & Consistency 영역.

Boundaries

• OoO vs. Speculative Execution (02-03-02): 추측 실행은 제어 흐름이 어느 길로 갈지 예측해 먼저 실행하는 기술이고, OoO는 이미 가져온 명령어들 사이에서 데이터 의존성이 풀린 작업을 먼저 실행하는 백엔드 최적화입니다. 둘은 함께 쓰이는 경우가 많지만, 해결하는 병목은 각각 제어 흐름과 데이터 흐름으로 다릅니다.

3. Counterexample

• 소스 코드 순서 가정의 한계: load가 캐시 미스로 오래 걸리는 동안 뒤의 독립적인 add까지 같이 멈춰야 한다고 생각하는 오해입니다. OoO 백엔드는 add가 필요한 피연산자를 이미 가지고 있다면 먼저 실행해 실행 유닛의 빈 시간을 줄일 수 있습니다.
• 가짜 의존성으로 인한 병렬성 손실: 두 명령어가 같은 레지스터 이름을 쓴다는 이유만으로 실제 데이터 흐름과 무관한 WAR/WAW 의존성이 생기는 경우입니다. 레지스터 르네이밍을 쓰면 같은 논리 이름을 서로 다른 물리 레지스터에 매핑해 독립적인 작업을 분리할 수 있습니다.

4. Prerequisites

• 파이프라인 해저드와 분기 예측 (Basic): RAW/WAR/WAW 의존성, 구조적 해저드, 분기 예측 실패의 플러시 비용을 알고 있어야 OoO가 어떤 병목을 줄이고 어떤 병목은 그대로 남기는지 구분할 수 있습니다. (02-03-01 PHR, 02-03-02 SEB)

5. Learning Map

6. Learning Topics

Basic

Core Topic 01: 준비된 명령어 먼저 실행하기 (Dynamic Scheduling)

• Why to Learn: 메모리 로드나 나눗셈처럼 오래 걸리는 명령어 하나 때문에 뒤의 독립 명령어까지 모두 멈추면 실행 유닛이 비어 있게 됩니다. 동적 스케줄링은 데이터가 준비된 작업을 먼저 골라 실행해 이 빈 시간을 줄입니다.
• What to Learn:
  • Concepts: 비순차 실행(OoO), 동적 스케줄링(Dynamic Scheduling), 발행 큐(Issue Queue).
  • Skills: RAW/WAR/WAW 의존성 구분, 준비된 마이크로 연산 선택.
  • Tools: 간단한 명령어 의존성 그래프와 발행 큐 시뮬레이터.
  • Trade-offs: 순차 실행(In-order)은 구조가 단순하고 전력 예측이 쉽지만 긴 지연 하나에 전체 파이프라인이 막힙니다. OoO는 성능을 크게 높일 수 있으나 큐, 태그 비교기, 스케줄러가 커져 전력과 면적 비용이 증가합니다.
• How to Learn:
  • 1단계: load r1, [A]가 캐시 미스로 지연되는 동안, add r4, r2, r3처럼 r1에 의존하지 않는 명령어가 왜 먼저 실행될 수 있는지 의존성 그래프로 표시합니다.
  • 2단계: 프런트엔드는 프로그램 순서대로 디코드하지만, 백엔드의 발행 큐는 준비된 마이크로 연산을 선택한다는 분리를 살펴봅니다.
• Implement: 명령어의 소스/목적 레지스터를 파싱해 RAW 의존성이 없는 명령어 묶음을 매 사이클 발행 가능한 그룹으로 출력하는 작은 스케줄러 작성.

Recommended

Core Topic 02: 가짜 의존성 제거하기 (Register Renaming)

• Why to Learn: 명령어가 같은 레지스터 이름을 쓰더라도 실제 데이터 흐름이 독립적일 수 있습니다. 레지스터 르네이밍은 이런 WAR/WAW 가짜 의존성을 제거해 병렬 실행 여지를 넓힙니다.
• What to Learn:
  • Concepts: 논리 레지스터(Logical Register), 물리 레지스터(Physical Register), 르네임 테이블(Rename Table).
  • Skills: WAR/WAW 의존성 제거, free list 관리, 롤백을 위한 매핑 체크포인트 이해.
  • Tools: 르네임 테이블과 물리 레지스터 free list.
  • Trade-offs: 물리 레지스터를 많이 두면 더 넓은 OoO 윈도우를 활용할 수 있지만, 레지스터 파일과 포트 수가 커져 전력과 타이밍 부담이 커집니다.
• How to Learn:
  • 1단계: r1 = r2 + r3 뒤에 r1 = r4 + r5가 나올 때, 두 결과가 같은 논리 이름을 쓰지만 서로 다른 물리 레지스터에 저장될 수 있음을 표로 정리합니다.
  • 2단계: 분기 예측 실패나 예외가 발생했을 때 이전 르네임 테이블 체크포인트로 돌아가야 하는 이유를 ROB와 연결해 봅니다.
• Implement: 논리 레지스터를 물리 레지스터로 매핑하는 르네임 테이블과 free list를 만들고, 명령어 발행마다 새 목적 물리 레지스터를 할당하는 시뮬레이터 작성.

Practical

Core Topic 03: 대기와 결과 전파 구조 (Reservation Station & CDB)

• Why to Learn: OoO 백엔드는 명령어가 언제 실행 가능한지 계속 추적해야 합니다. 예약 스테이션은 필요한 값이 아직 없으면 태그를 들고 기다리고, 결과가 방송되면 즉시 실행 후보가 됩니다.
• What to Learn:
  • Concepts: 예약 스테이션(Reservation Station), 태그(Tag), 공통 데이터 버스(Common Data Bus, CDB).
  • Skills: 피연산자 준비 상태 추적, 결과 태그 매칭, 실행 유닛 포트 병목 분석.
  • Tools: Tomasulo 스타일 예약 스테이션 테이블.
  • Trade-offs: 결과를 넓게 방송하면 대기 중인 명령어를 빠르게 깨울 수 있지만, 태그 비교와 배선 비용이 커져 클럭 주파수와 전력에 부담을 줍니다.
• How to Learn:
  • 1단계: mul 결과를 기다리는 add가 실제 값 대신 생산자 태그를 들고 예약 스테이션에 머무르는 과정을 추적합니다.
  • 2단계: 결과가 CDB에 방송되면 같은 태그를 기다리던 여러 명령어가 동시에 깨어날 수 있지만, 실행 포트가 부족하면 다시 큐에서 경쟁해야 함을 확인합니다.
• Implement: op, vj, vk, qj, qk 필드를 가진 예약 스테이션 엔트리를 만들고, CDB 방송 이벤트가 들어오면 일치하는 태그를 값으로 갱신하는 시뮬레이터 작성.

Advanced

Core Topic 04: 순서대로 확정하기 (ROB & Precise Commit)

• Why to Learn: 명령어는 비순차로 끝날 수 있지만, 아키텍처 상태와 예외는 프로그램 순서를 지켜야 합니다. ROB는 완료된 결과를 임시로 보관하다가 앞선 명령어부터 차례로 커밋합니다.
• What to Learn:
  • Concepts: 재정렬 버퍼(Reorder Buffer, ROB), 커밋(Commit), 은퇴(Retirement), 정확한 예외(Precise Exception).
  • Skills: ROB head 커밋, 예외 보존, 분기 예측 실패 시 squash와 매핑 복원.
  • Tools: ROB 엔트리 테이블과 커밋 포인터.
  • Trade-offs: ROB가 크면 더 많은 명령어를 동시에 추적할 수 있지만, 회로 면적과 전력, 예외/롤백 제어 복잡도가 함께 증가합니다.
• How to Learn:
  • 1단계: 3번 명령어가 2번 명령어보다 먼저 완료되어도 ROB 안에서 기다리고, 2번 명령어가 먼저 커밋된 뒤에야 3번 결과가 아키텍처 상태에 반영되는 흐름을 추적합니다.
  • 2단계: 중간 명령어가 예외를 일으키거나 분기 예측이 틀렸을 때, ROB tail 쪽의 젊은 명령어를 취소하고 르네임 상태를 복원하는 과정을 연결합니다.
• Implement: id, dest, value, ready, exception 필드를 가진 ROB 엔트리를 만들고, head부터 ready인 항목만 커밋하는 간단한 ROB 시뮬레이터 작성.

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'의 주원인이 데이터 의존성 때문인지, 자원 부족 때문인지 리네이밍 통계를 통해 분석 가능한가?