비순차적 명령어 처리 (Out-of-Order Execution)

비순차적 명령어 처리는 프로세서가 엄격하게 프로그램 순서대로가 아니라 피연산자가 준비되는 즉시 명령어를 실행하도록 하며, 레지스터 리네이밍(register renaming)과 버퍼링을 사용하여 병렬성을 노출하면서도 순차적인 결과를 생성합니다.

Definition

비순차적 명령어 처리는 프로세서가 동적으로 명령어 실행 순서를 재정렬하여 피연산자가 사용 가능해지는 즉시 독립적인 명령어를 실행하는 마이크로아키텍처 기술이며, 버퍼링과 리네이밍을 사용하여 순차적이고 순서대로 완료되는 것처럼 보이도록 유지합니다.

Scope

이 주제는 동적 스케줄링(dynamic scheduling)을 다룹니다: 예약 스테이션(reservation stations), 거짓 의존성(false dependencies) 제거를 위한 레지스터 리네이밍, 순차적 커밋(in-order commit)을 강제하는 재정렬 버퍼(reorder buffer), 그리고 추측 실행 복구(speculative execution recovery). 이는 토마술로 알고리즘(Tomasulo's algorithm)을 직접 기반으로 합니다. 분기 방향 예측(branch prediction)과 병렬성 존재 여부에 대한 더 넓은 개념(instruction-level parallelism)은 제외하며, 명령어 재정렬 메커니즘 자체에 초점을 맞춥니다.

Core questions

• 프로세서는 어떻게 프로그램 순서와 다르게 명령어를 실행하면서도 올바른 순차적 결과를 생성할 수 있는가?
• 레지스터 리네이밍은 쓰기-후-읽기(write-after-read) 및 쓰기-후-쓰기(write-after-write) 의존성을 어떻게 제거하는가?
• 예약 스테이션과 재정렬 버퍼는 무엇에 기여하는가?
• 비순차적 코어에서 예외 및 오예측은 어떻게 정확하게 복구되는가?

Key concepts

• 동적 스케줄링
• 예약 스테이션
• 레지스터 리네이밍
• 공통 데이터 버스
• 재정렬 버퍼
• 순차적 커밋
• 정확한 예외 처리
• 추측 실행 복구

Key theories

토마술로 알고리즘

토마술로 방식은 예약 스테이션과 공통 데이터 버스를 사용하여 레지스터를 리네이밍하고 피연산자가 사용 가능해지면 기능 장치로 명령어를 디스패치하여, 진정한 데이터 의존성만 존중하는 비순차적 명령어 처리를 허용합니다.

순차적 커밋을 통한 정확한 예외 처리

재정렬 버퍼는 비순차적 명령어의 결과를 보관하고 프로그램 순서대로 커밋하여, 실행이 엄격하게 순차적이었던 것처럼 예외 및 오예측을 정확하게 처리할 수 있도록 합니다.

Mechanisms

디코딩된 명령어는 물리적 레지스터로 리네이밍되고 예약 스테이션 또는 발행 큐(issue queue)에 배치되며, 여기서 결과 버스(result bus)를 통해 브로드캐스트되는 피연산자를 기다립니다. 준비되면 사용 가능한 기능 장치(functional units)에서 어떤 순서로든 실행됩니다. 재정렬 버퍼는 원래 프로그램 순서를 추적하고 결과를 순차적으로 커밋하며, 오예측(misprediction)이나 예외 발생 시 추측성 결과를 폐기하여 아키텍처 상태가 항상 정확하도록 합니다.

Clinical relevance

비순차적 명령어 처리는 고성능 CPU의 핵심 엔진으로, 독립적인 작업을 찾아 메모리 및 실행 지연 시간(latencies)을 숨깁니다. 또한 보안에도 영향을 미칩니다. 추측성, 비순차적 작업이 폐기되기 전에 일시적으로 데이터에 접근할 수 있기 때문에, 스펙터(Spectre) 및 멜트다운(Meltdown)과 같은 마이크로아키텍처 측면 채널 공격(side-channel attacks)을 가능하게 했습니다.

History

토마술로(Tomasulo)는 1967년 IBM System/360 Model 91에서 동적 스케줄링을 도입했습니다. 1980년대에 개발된 정확한 예외 처리를 위한 재정렬 버퍼와의 결합은 비순차적 명령어 처리를 범용 프로세서에 실용적으로 만들었으며, 1990년대 중반부터 고성능 설계의 표준이 되었습니다.

Debates

성능 대 복잡성, 전력, 보안

비순차적 명령어 처리는 강력한 단일 스레드 성능을 제공하지만, 하드웨어 복잡성과 전력 면에서 상당한 비용이 들고, 그 추측 실행은 악용될 수 있음이 입증되었습니다. 이는 얼마나 적극적으로 추측 실행을 할 것인지와 더 단순하고 효율적이거나 안전한 설계를 선호할 것인지에 대한 논쟁을 촉발합니다.

Key figures

• Robert Tomasulo
• Yale Patt
• James E. Smith
• John L. Hennessy

Seminal works

• tomasulo1967
• hennessy2019

Frequently asked questions

명령어가 순서와 다르게 실행된다면, 프로그램은 어떻게 여전히 올바른가?

프로세서는 실행 순서만 재정렬할 뿐, 결과는 재정렬하지 않습니다. 레지스터 리네이밍은 진정한 데이터 의존성을 존중하도록 보장하며, 재정렬 버퍼는 원래 프로그램 순서대로 결과를 커밋하므로, 가시적인 아키텍처 상태는 순차적 실행이 생성했을 결과와 정확히 동일합니다.

레지스터 리네이밍이란 무엇인가?

레지스터 리네이밍은 명령어에 명시된 아키텍처 레지스터를 더 큰 물리적 레지스터 풀에 매핑하는 것입니다. 이는 레지스터 이름 재사용으로 인해 발생하는 거짓 (이름) 의존성을 제거하여, 더 많은 독립적인 명령어가 레지스터 저장 공간에 대한 충돌 없이 병렬로 실행될 수 있도록 합니다.