title: Out-of-Order 실행
date: 2025-06-26
category: arch
tags: [out-of-order, superscalar, reorder-buffer, register-renaming, Tomasulo]

Out-of-Order 실행 (Out-of-Order Execution)

개요

Out-of-Order 실행(Out-of-Order Execution, OoO)은 프로세서 아키텍처에서 명령어를 프로그램 순서와 다른 순서로 동적으로 실행하여 성능을 향상시키는 기술이다. 이 기술은 명령어 수준 병렬성(Instruction-Level Parallelism, ILP)을 극대화하여 파이프라인의 유휴 시간을 최소화하고, 데이터 의존성이 없는 명령어들이 기다리지 않고 바로 실행되도록 한다. Out-of-Order 실행은 현대 고성능 프로세서의 핵심 기술로, Intel, AMD, ARM, IBM 등의 프로세서에 광범위하게 채택되어 있다.

In-Order 실행에서는 명령어가 순서대로 실행되므로 앞선 명령어가 완료될 때까지 다음 명령어가 대기해야 한다. 반면 Out-of-Order 실행은 명령어 간 데이터 의존성을 분석하여 준비된 명령어를 먼저 실행하고, 나중에 결과를 프로그램 순서대로 재배치하여 커밋함으로써 프로그램의 정확성을 보장한다. 이를 통해 메모리 지연 시간이나 실행 유닛의 가용성에 따른 대기 시간을 효과적으로 숨길 수 있다.

핵심 개념

리네이밍 (Register Renaming)

리네이밍은 Out-of-Order 실행의 핵심 기술로, WAW(Write-After-Write)와 WAR(Write-After-Read) 의존성을 제거하기 위해 사용된다. 물리적 레지스터 파일(Physical Register File)을 사용하여 아키텍처 레지스터(architectural registers)를 동적으로 매핑함으로써 거짓 의존성(false dependency)을 제거한다.

동작 원리:
1. 명령어가 디코딩될 때 물리적 레지스터가 할당됨
2. 명령어 간 같은 아키텍처 레지스터를 사용하더라도 다른 물리적 레지스터에 매핑
3. 명령어가 완료될 때만 아키텍처 레지스터에 결과를 커밋

예시:

; 리네이밍 전 (WAW hazard)
ADD R1, R2, R3    ; R1 = R2 + R3
SUB R1, R4, R5    ; R1 = R4 - R5 (WAW 의존성)

; 리네이밍 후
ADD P1, P2, P3    ; P1 = P2 + P3 (물리적 레지스터 P1 사용)
SUB P4, P5, P6    ; P4 = P5 - P6 (물리적 레지스터 P4 사용)
; 나중에 P1의 값이 R1로 커밋됨

리오더 버퍼 (Reorder Buffer, ROB)

리오더 버퍼는 명령어를 실행 순서가 아닌 프로그램 순서대로 커밋하기 위해 사용되는 FIFO 큐이다. Out-of-Order 실행에서 발생하는 여러 문제를 해결한다:

• 정확한 예외 처리 (Precise Exceptions): 예외 발생 시 정확한 파이프라인 상태를 복원
• 분기 예측 실패 복구: 잘못된 분기 예측 후 파이프라인을 정확한 상태로 복원
• 결과 커밋: 명령어 결과를 아키텍처 상태에 프로그램 순서대로 반영

ROB 엔트리 구조:
| 필드 | 설명 |
|------|------|
| 명령어 상태 | 완료 대기, 실행 중, 완료, 커밋 |
| 결과 값 | 실행 결과 데이터 |
| 대상 레지스터 | 결과가 저장될 아키텍처 레지스터 |
| 예외 플래그 | 예외 발생 여부 |
| 분기 정보 | 분기 명령어인지 여부 |

리저버베이션 스테이션 (Reservation Station)

리저버베이션 스테이션은 실행 가능한 명령어를 대기시키는 큐이다. 각 실행 유닛에 연결되어 있으며, 명령어의 피연산자가 준비되면 즉시 실행을 시작한다.

동작 방식:
1. 디스패치된 명령어가 리저버베이션 스테이션에 배치됨
2. 피연산자 데이터가 준비될 때까지 대기
3. 모든 피연산자가 준비되면 실행 유닛으로 명령어를 전달
4. 다른 명령어가 먼저 실행되도록 허용 (Out-of-Order Issue)

로드/스토어 큐 (Load/Store Queue)

로드/스토어 큐는 메모리 접근 명령어를 관리하는 전용 큐이다. 특히 Out-of-Order 코어는 레지스터 의존성뿐 아니라 메모리 주소 의존성도 동적으로 추적해야 하므로, 로드/스토어 큐가 메모리 병렬성과 정확성 사이의 균형을 잡는 핵심 블록이 된다.

로드 큐 (Load Queue):
- 로드 명령어의 주소 계산 및 데이터 로드 관리
- 앞선 스토어와 충돌하지 않는 로드의 선행 실행 허용
- Store-Load 의존성 탐지

스토어 큐 (Store Queue):
- 스토어 명령어의 데이터를 캐시에 쓰기 전까지 보관
- 스토어 버퍼링 및 메모리 일관성 관리
- 스토어-스토어 순서 보장

메모리 의존성 예측이 공격적으로 동작하면 로드가 아직 주소가 확정되지 않은 스토어보다 먼저 실행될 수 있다. 이때 실제 주소 충돌이 발견되면 파이프라인 재실행(replay)이나 스쿼시(squash)가 필요하므로, 고성능 코어는 주소 비교기와 store-to-load forwarding 경로를 함께 둔다.

발행 폭과 윈도우 크기

Out-of-Order 성능은 단순히 실행 유닛 수만으로 결정되지 않는다. 한 사이클에 몇 개의 명령어를 rename, dispatch, issue, retire 할 수 있는지와, 동시에 추적 가능한 인플라이트(in-flight) 명령어 수가 함께 중요하다.

• Rename/Dispatch 폭: 프런트엔드가 백엔드에 공급할 수 있는 최대 명령어 수
• Issue 폭: 준비된 명령어를 실행 유닛으로 내보낼 수 있는 수
• Retire 폭: 프로그램 순서대로 상태를 확정할 수 있는 수
• 윈도우 크기: ROB, issue queue, load/store queue가 합쳐서 숨길 수 있는 지연 시간의 범위

즉, ROB가 크더라도 issue 폭이나 load queue가 좁으면 메모리 지연을 충분히 숨기지 못하고, 반대로 실행 유닛이 많더라도 rename 단계가 병목이면 백엔드가 비게 된다.

핵심 구성 요소 상세

Out-of-Order 실행의 핵심 구성 요소인 리오더 버퍼(ROB), 리저버베이션 스테이션, 로드/스토어 큐의 상세 구조와 동작 방식을 시각화한 다이어그램입니다.

실행 유닛과 비교 (Execution Units and Comparison)

Out-of-Order 프로세서는 여러 실행 유닛을 동시에 운영하여 명령어 수준 병렬성을 극대화한다:

비교/분석

In-Order vs Out-of-Order 실행 비교

In-Order 실행과 Out-of-Order 실행의 명령어 흐름과 성능 특성을 비교한 다이어그램입니다.

현대 프로세서의 Out-of-Order 구현 비교

하자(Hazard) 처리 비교

현대 구현에서는 위 표의 개념이 독립적으로 동작하지 않는다. 예를 들어 RAW 의존성은 forwarding으로 줄이되, 긴 지연의 LOAD는 ROB와 issue queue에 오래 머물며 뒤따르는 독립 명령어를 먼저 실행하게 만든다. 결국 리네이밍, wakeup/select, forwarding, load/store ordering이 함께 작동해야 OoO의 이점이 현실적인 IPC 향상으로 이어진다.

동작 원리

Out-of-Order 실행은 크게 8단계로 동작한다:

1단계: 페치 (Fetch)

명령어를 명령어 캐시(I-Cache)에서 읽어옴. 분기 예측기를 사용하여 다음에 실행할 명령어 블록을 예측하고, 예측된 주소에서 명령어를 페치함.

2단계: 디코딩 (Decode)

페치된 명령어를 해석하여 마이크로 연산(micro-operation, uop)으로 변환한다. 복잡한 CISC 명령어는 여러 개의 uop으로 분해되어 이후 단계에서 독립적으로 추적된다.

3단계: 리네이밍 및 할당 (Rename & Allocate)

• 물리적 레지스터 파일에서 물리적 레지스터를 할당
• 아키텍처 레지스터를 물리적 레지스터로 매핑 (Register Alias Table, RAT 사용)
• ROB 엔트리 할당
• 리저버베이션 스테이션 엔트리 할당

4단계: 디스패치 (Dispatch)

준비된 명령어를 리저버베이션 스테이션으로 전달. 명령어의 의존성 정보를 기록하고, 준비되면 실행될 수 있도록 준비함.

5단계: 실행 (Execute)

리저버베이션 스테이션에서 피연산자가 준비된 명령어를 선택하여 실행 유닛으로 전달. 여러 명령어가 동시에 다른 실행 유닛에서 실행될 수 있음.

6단계: 결과 전달 (Result Bypassing/Forwarding)

실행 결과를 다른 명령어의 피연산자로 즉시 전달. 결과가 레지스터 파일에 기록되기 전에 다른 명령어에서 사용할 수 있게 함.

7단계: 완료 (Complete)

실행 결과를 ROB에 기록. 명령어가 실행되었음을 표시하고, 결과 데이터를 저장함.

8단계: 커밋/졸업 (Commit/Retire)

ROB의 맨 앞에 있는 명령어가 실행을 완료했을 때, 프로그램 순서대로 아키텍처 레지스터 파일에 결과를 기록. 예외가 발생한 명령어는 적절한 복구 처리 후 예외를 처리함.

동작 흐름도

Out-of-Order 실행은 8단계로 동작하며, 핵심 구성 요소들이 함께 작동해 명령어를 비순차적으로 실행하고 프로그램 순서대로 커밋한다.

장단점

장점

1. 성능 향상: 파이프라인의 유휴 시간을 최소화하여 IPC(Instructions Per Cycle) 향상
2. 메모리 지연 시간 숨김: 메모리 접근 대기 시간 동안 다른 명령어를 실행하여 지연 효과 감소
3. 파이프라인 활용도 증가: 실행 유닛의 가용성을 높여 하드웨어 자원 효율적 활용
4. 분기 예측 실패 비용 감소: 잘못된 분기 예측 후에도 실행된 명령어들의 결과를 재사용 가능
5. 기존 코드 호환: 소프트웨어 변경 없이 하드웨어 수준에서 성능 향상

단점

1. 하드웨어 복잡도 증가: 리네이밍, ROB, 리저버베이션 스테이션 등 추가 하드웨어 필요
2. 전력 소모 증가: 복잡한 제어 로직과 추가 레지스터로 인한 전력 소모
3. 다이 면적 증가: 추가 하드웨어로 인한 칩 면적 확대
4. 설계 복잡도: 타이밍, 전력, 면적 간의 트레이드오프 복잡
5. 보안 취약점: Spectre, Meltdown과 같은 사이드 채널 공격에 취약

보안 고려사항

Out-of-Order 실행은 성능을 향상시키지만, 사이드 채널 공격에 취약할 수 있다:

• Spectre: 분기 예측과 스펙큘러티브 실행을 악용하여 메모리 데이터를 추출
• Meltdown: Out-of-Order 실행 중 권한 검사 전에 메모리 접근을 이용한 공격
• 대응책: Retpoline, IBRS, STIBP, 커널 페이지 테이블 격리(KPTI), speculation barrier 적용 등

관련 기술

참고 문헌 및 논문

1. Tomasulo, R.M. (1967). "An Efficient Algorithm for Exploiting Multiple Arithmetic Units." IBM Journal of Research and Development, 11(1), 25-33.
   - Tomasulo 알고리즘: Out-of-Order 실행의 기초가 된 최초의 알고리즘

2. Smith, J.E. & Pleszkun, A.R. (1985). "Implementation of Precise Interrupts in Pipelined Processors." 12th ISCA.
   - 정확한 예외 처리(Precise Exceptions) 구현에 대한 핵심 연구

3. Hennessy, J.L. & Patterson, D.A. (2017). Computer Architecture: A Quantitative Approach (6th ed.). Morgan Kaufmann.
   - 컴퓨터 아키텍처 교과서에서 Out-of-Order 실행에 대한 상세 설명

4. Mudge, T. (2004). "The Microarchitecture of Superscalar Processors." Proceedings of the IEEE.
   - 슈퍼스칼라 프로세서의 마이크로아키텍처 분석

관련 기술 문서

• CPU 마이크로아키텍처 기초: 파이프라인, 스테이지, IPC 등 기본 개념
• 분기 예측: Out-of-Order 실행과 함께 사용되는 분기 예측 기술
• 캐시 일관성 프로토콜: 멀티코어 환경에서의 캐시 일관성
• 메모리 일관성 모델: Out-of-Order 실행에서의 메모리 순서 보장 규칙을 정의하는 주제

관련 기술 분야

1. 스펙큘러티브 실행 (Speculative Execution): 분기 예측 결과를 미리 실행하는 기술
2. 레지스터 리네이밍 (Register Renaming): 물리적 레지스터를 사용한 거짓 의존성 제거
3. 데이터 전달 (Data Forwarding): 실행 결과를 바로 다음 명령어에 전달하는 기술
4. 메모리 탈출 회로 (Memory Disambiguation): 메모리 접근 의존성 분석 및 최적화
5. 슈퍼스칼라 아키텍처 (Superscalar Architecture): 여러 명령어를 동시에 실행하는 아키텍처

핵심 정리

1. Out-of-Order 실행은 명령어를 프로그램 순서가 아닌 데이터 준비 순서대로 실행하여 파이프라인 활용도를 극대화하는 기술이다.

2. 핵심 구성 요소인 리네이밍(Register Renaming), 리오더 버퍼(ROB), 리저버베이션 스테이션(Reservation Station)이 함께 작동하여 거짓 의존성을 제거하고 정확한 커밋을 보장한다.

3. 동작 원리는 페치 → 디코딩 → 리네이밍 → 디스패치 → 실행 → 완료 → 커밋의 8단계로 동작하며, ROB를 통해 프로그램 순서대로 결과를 아키텍처 상태에 반영한다.

4. 장점으로는 성능 향상, 메모리 지연 시간 숨김, 파이프라인 활용도 증가가 있으나, 하드웨어 복잡도, 전력 소모, 다이 면적 증가라는 단점이 있다.

5. 보안 고려사항으로 Spectre, Meltdown과 같은 사이드 채널 공격에 취약하며, 이를 방어하기 위한 다양한 기술이 개발되었다.