현대 CPU에 사용되는 슈퍼스칼라 구조와 Out-of-Order (OoO) 실행에 대해 알아보겠습니다.

인스트럭션 수준 병렬화

지금까지 본 내용에선, CPU는 명령어를 직렬적으로 실행했습니다. 파이프라이닝이 한 사이클에 여러 명령어를 처리할 수 있게 해주지만, 동시에 여러 명령어가 한 번에 실행되지는 않았습니다. 하나씩 입력되고, 하나씩 실행됐죠.

이를 개선하기 위한 방법이 인스트럭션 수준 병렬화(Instruction-Level Parallelism, ILP) 입니다. ILP는 프로그램 안에서 동시에 실행할 수 있는 명령어를 찾아내어 병렬로 처리하는 것을 말합니다. 프로그래머가 보기에는 명령어가 한 줄씩 실행되지만, CPU 내부적으로는 서로 의존성이 없는 명령어들을 동시에 처리해서 성능을 높입니다.

병렬화에는 ILP 외에도 다른 층위가 있습니다. 여러 스레드를 동시에 실행하는 스레드 수준 병렬화(Thread-Level Parallelism, TLP) 는 멀티코어나 SMT가 활용하며, 같은 연산을 여러 데이터에 동시에 적용하는 데이터 수준 병렬화(Data-Level Parallelism, DLP) 는 SIMD나 GPU가 대표적입니다. TLP와 DLP가 프로그래머의 명시적인 코드 작성을 요구하는 것과 달리, ILP는 하드웨어와 컴파일러가 자동으로 추출하기 때문에 프로그래머에게 거의 투명하다는 점이 특징입니다.

Processing Element와 Average ILP

ILP가 실제로 얼마나 가능한지 이야기하려면 두 가지 개념이 필요합니다.

먼저 Processing Element(PE) 는 실제로 연산을 수행하는 최소 단위 하드웨어를 말합니다. ILP의 맥락에서는 ALU나 FPU 같은 functional unit 하나라고 보면 됩니다. 한 사이클에 동시에 처리할 수 있는 명령어의 수는 결국 PE의 개수에 묶이게 됩니다.

다음으로 Average ILP 는 자원이 무한하다고 가정했을 때, 데이터 의존성만으로 프로그램을 가장 빨리 실행했을 경우 사이클당 평균 몇 개의 명령어가 동시에 실행되는지를 나타내는 값입니다.

$$ \text{Average ILP} = \frac{\text{전체 명령어 수}}{\text{critical path 길이(사이클)}} $$

이 값은 자원 제약을 고려하지 않은 이상적인 상한으로, 프로그램이 본질적으로 가지고 있는 병렬성을 의미합니다. 실제 머신에서 측정되는 IPC와는 다른 개념입니다.

간단한 예시로 다음 다섯 개의 명령어를 봅시다.

I1: r1 = a + b
I2: r2 = c + d
I3: r3 = r1 * r2     ; I1, I2에 의존
I4: r4 = e + f
I5: r5 = r3 + r4     ; I3, I4에 의존

데이터 의존성 그래프를 따라 자원이 무한하다고 가정하고 스케줄링하면 다음과 같이 정리됩니다.

전체 명령어 수는 5개이고, critical path는 I1 → I3 → I5로 3 사이클입니다. 따라서 이 코드 조각의 Average ILP는 $5 / 3 \approx 1.67$ 이 됩니다. 즉 이상적으로도 사이클당 평균 1.67개의 명령어밖에 뽑아낼 수 없는 코드라는 뜻입니다.

만약 PE가 하나뿐인 머신에서 이 코드를 돌리면 5 사이클이 그대로 걸려 ILP를 전혀 활용하지 못하고, 반대로 PE가 3개 이상이면 의존성이 허용하는 한계인 3 사이클까지 단축됩니다. PE의 수가 ILP를 얼마나 끌어낼 수 있는지의 천장이 되는 셈입니다.

슈퍼스칼라

슈퍼스칼라(Superscalar) 는 한 사이클에 여러 개의 명령어를 동시에 발행(issue) 하고 실행할 수 있도록 만든 CPU 구조입니다. 앞 절에서 본 것처럼 ILP를 실제로 끌어내려면 PE가 여러 개 있어야 하는데, 슈퍼스칼라 CPU는 ALU·FPU·로드/스토어 유닛 같은 functional unit을 여러 벌 두고, 매 사이클마다 의존성이 없는 명령어 여러 개를 골라 각 PE에 분배합니다.

이때 한 사이클에 발행할 수 있는 명령어의 최대 개수를 issue width 라고 하며, issue width가 $N$인 머신을 보통 "$N$-way 슈퍼스칼라"라고 부릅니다. 예를 들어 4-way 슈퍼스칼라는 매 사이클마다 최대 4개의 명령어를 동시에 발행할 수 있습니다.

슈퍼파이프라인과의 비교

처리량을 늘리는 또 다른 접근으로 슈퍼파이프라인(Superpipelined) 머신이 있습니다. 슈퍼파이프라인은 파이프라인의 각 스테이지를 더 작은 단위로 잘게 쪼개서 단계 수를 늘리고, 그만큼 클럭 주파수를 높이는 방식입니다. 한 사이클에 발행하는 명령어 수는 여전히 1개라서 Average ILP 자체를 끌어올리지는 못하지만, 사이클이 짧아진 덕분에 단위 시간당 더 많은 명령어를 처리할 수 있게 됩니다.

두 방식의 차이를 정리하면 다음과 같습니다.

같은 8개의 명령어를 세 종류의 머신에서 실행한다고 가정해봅시다. 명령어들 사이에 의존성이 전혀 없다고 하고, 기본 파이프라인은 5 스테이지(IF, ID, EX, MEM, WB)라고 하겠습니다.

I1, I2, I3, I4, I5, I6, I7, I8   ; 모두 독립

(1) 일반 스칼라 파이프라인 — 한 사이클에 한 명령어만 발행. 첫 명령어가 5 사이클 후에 끝나고, 이후 매 사이클마다 한 개씩 완료됩니다. 8개 명령어를 모두 끝내는 데 $5 + (8 - 1) = 12$ 사이클이 걸립니다. IPC는 $8/12 \approx 0.67$.

(2) 슈퍼파이프라인 (스테이지 10개, 클럭 2배) — 스테이지를 두 배로 잘게 쪼개 클럭이 2배가 됩니다. 한 사이클에 한 명령어만 발행하지만 사이클 자체가 짧아진 것이죠. 첫 명령어가 10 (짧은) 사이클 후 완료되고, 이후 매 짧은 사이클마다 한 개씩 완료되어 $10 + (8 - 1) = 17$ 짧은 사이클이 걸립니다. 원래 사이클 기준으로 환산하면 $17 / 2 = 8.5$ 사이클로, 스칼라 파이프라인보다 약 1.4배 빠릅니다.

(3) 2-way 슈퍼스칼라 (5 스테이지, PE 2벌) — 한 사이클에 명령어 두 개를 동시에 발행합니다. 사이클 1에 I1·I2가 IF에 들어가고, 사이클 2에 I3·I4가 들어가는 식이죠. 첫 두 명령어가 5 사이클 후에 함께 끝나고, 이후 매 사이클마다 두 개씩 완료되어 총 $5 + (8/2 - 1) = 8$ 사이클이 걸립니다. IPC는 $8/8 = 1.0$이며, 2-way의 이상적인 한계인 2.0에는 워밍업 때문에 못 미치지만 충분히 큰 명령어 흐름에서는 2에 근접하게 됩니다.

여기서 두 가지를 관찰할 수 있습니다. 첫째, 슈퍼파이프라인은 클럭을 끌어올려서 시간 축에서 처리량을 늘리는 반면, 슈퍼스칼라는 PE를 늘려서 공간 축에서 처리량을 늘립니다. 둘째, 두 방식은 서로 배타적이지 않아서 실제 현대 CPU는 깊은 파이프라인 위에 넓은 슈퍼스칼라 발행을 결합해 둘의 이점을 동시에 취합니다.

In-Order 파이프라인의 한계

다만 위 예시는 명령어들 사이에 의존성이 전혀 없다는 가정 하의 이야기였습니다. 실제 코드에는 데이터 의존성과 분기, 메모리 접근 지연이 섞여 있고, 이때 명령어를 프로그램 순서대로 발행하는 in-order 파이프라인은 두 가지 큰 문제에 부딪힙니다.

1. 머신 병렬성을 키울수록 활용률이 급격히 떨어진다

In-order 파이프라인은 명령어를 프로그램 순서대로만 발행할 수 있기 때문에, 앞쪽 명령어가 멈추면 그 뒤의 명령어들은 의존성과 무관하게 함께 멈춰야 합니다. issue width를 키울수록 이 "한 명령어의 stall이 한 사이클 전체를 비우는" 손해는 점점 커집니다.

다음 코드를 봅시다.

I1: r1 = load [r10]   ; 캐시 미스, 데이터가 4 사이클 후에 도착
I2: r2 = r1 + 1       ; I1에 의존
I3: r3 = r5 + r6      ; 독립
I4: r4 = r7 + r8      ; 독립
I5: r5 = r9 + r11     ; 독립
I6: r6 = r12 + r13    ; 독립

이 코드를 2-way in-order 슈퍼스칼라에서 실행하면 다음과 같이 진행됩니다.

총 7 사이클에 6개 명령어, 동시에 처리할 수 있었던 슬롯은 $7 \times 2 = 14$개인데 실제로 채워진 건 6개입니다. 활용률 약 43%. 사이클 2~4의 stall 동안 I3·I4·I5는 이미 준비가 끝났는데도 in-order 규칙 때문에 들어가지 못한 것이죠.

이번엔 같은 코드를 4-way in-order 슈퍼스칼라에 올려봅시다.

총 6 사이클, 슬롯은 $6 \times 4 = 24$개인데 채워진 건 6개로 활용률 25%. issue width를 2배로 늘렸지만 전체 시간은 7 → 6 사이클로 한 사이클밖에 줄지 않았고, 대부분의 슬롯이 비어버렸습니다. 머신 병렬성을 키우면 키울수록 stall로 인한 손해는 width에 비례해서 커지므로, 일정 지점을 넘어가면 추가된 PE가 거의 일을 못 하는 것이 in-order 구조의 본질적 한계입니다.

2. Forwarding으로는 이 문제를 해결할 수 없다

이전에 본 파이프라인 해저드는 포워딩(forwarding) 으로 상당 부분 해결할 수 있었습니다. EX 단계에서 계산된 결과를 WB까지 기다리지 않고 바로 다음 명령어의 EX 입력으로 흘려주는 방식이죠. 하지만 포워딩이 통하는 건 결과가 이미 계산되어 있는 경우에 한합니다.

위 예시의 I1 → I2 의존성을 보면, I1의 결과는 캐시 미스 때문에 4 사이클 뒤에야 메모리에서 도착합니다. 포워딩 경로가 아무리 잘 깔려 있어도 존재하지 않는 데이터를 앞당겨 흘려줄 수는 없습니다. 즉 포워딩은 "결과 생성 → 사용" 사이의 파이프라인 지연은 줄여주지만, "데이터가 아직 없음"으로 인한 본질적인 대기 시간 자체는 줄여주지 못합니다. 캐시 미스, 부동소수점 나눗셈, 긴 곱셈 같은 다중 사이클 연산 뒤에 의존 명령어가 오면 in-order 파이프라인은 그저 기다릴 수밖에 없습니다.

Out-of-Order Execution

결국 in-order 구조에서 issue width를 늘리는 것은 수확체감에 빠르게 부딪히고, 포워딩 같은 기존 기법으로는 막을 수 없다는 결론에 이릅니다. 그렇다면, 앞쪽 명령어가 stall되어 있는 동안, 뒤쪽 명령어를 먼저 실행하면 어떨까요? 이 발상에서 출발한 것이 바로 비순차 실행(Out-of-Order Execution, OoO) 입니다.

OoO는 이름 그대로, 명령어를 프로그램에 적힌 순서대로 실행하지 않고 준비된 것부터 먼저 실행하는 방식입니다. 핵심 원칙은 다음과 같이 요약할 수 있습니다.

• In-order fetch / decode: 명령어를 가져와 해석하는 단계는 여전히 프로그램 순서를 따릅니다. 분기 예측이나 의존성 추적을 위해서는 원래 순서를 알고 있어야 하기 때문이죠.
• Out-of-order execute: 디코드된 명령어들은 일종의 대기실에 쌓여 있다가, 자신이 필요로 하는 입력 값(피연산자)이 모두 준비된 명령어부터 사용 가능한 PE에 발행됩니다. 프로그램 순서는 무시됩니다.
• In-order commit: 실행이 끝났더라도 결과를 곧바로 아키텍처 상태(레지스터 파일, 메모리)에 반영하지 않고, 원래 프로그램 순서대로 차례로 커밋합니다. 이렇게 해야 분기 예측 실패나 예외(exception)가 발생했을 때 마치 in-order로 실행한 것처럼 깔끔하게 되돌릴 수 있습니다.

이 "in-order로 들여와 OoO로 실행하고 다시 in-order로 마무리한다"는 구조 덕분에, 프로그래머는 여전히 명령어가 한 줄씩 순서대로 실행되는 것처럼 볼 수 있으면서도 CPU 내부에서는 ILP를 최대한 끌어낼 수 있습니다.

이런 OoO를 실제로 구현하려면 풀어야 할 문제가 몇 가지 있습니다.

1. 같은 레지스터 이름을 재사용해서 생긴 가짜 의존성이 명령어 순서를 묶어 놓는데, 이걸 어떻게 풀어낼 것인가? → Register Renaming
2. 어떤 명령어의 피연산자가 준비되었는지 추적하고, 준비된 명령어를 적절한 PE에 배분하는 메커니즘은 어떻게 만들 것인가? → Reservation Station / Issue Queue
3. 순서가 뒤죽박죽으로 실행된 결과를, 원래 프로그램 순서대로 다시 정렬해서 커밋하려면 무엇이 필요한가? → Reorder Buffer (ROB)

이제 이 세 가지를 차례대로 살펴봅시다.

Register Renaming

명령어의 순서를 바꾸려고 하면 데이터 의존성이 발목을 잡습니다. 의존성에는 세 종류가 있습니다.

• RAW (Read After Write, true dependency): 파이프라이닝에서도 알아본 의존성입니다. 앞 명령어가 쓴 값을 뒤 명령어가 읽음. 이는 진짜 데이터 흐름에서 비롯된 의존성이라 어떤 방법으로도 없앨 수 없습니다.
• WAR (Write After Read, anti-dependency): 앞 명령어가 읽는 레지스터를 뒤 명령어가 덮어씀. 순서가 바뀌면 앞 명령어가 잘못된 값을 읽게 됩니다.
• WAW (Write After Write, output dependency): 두 명령어가 같은 레지스터에 순서대로 씀. 순서가 바뀌면 최종 값이 달라집니다.

WAR와 WAW는 사실 이름이 같은 레지스터를 재사용해서 생긴 가짜 의존성입니다. 실제로 데이터가 흐르는 게 아니라, 단지 컴파일러가 가용한 아키텍처 레지스터(x86의 RAX, RISC-V의 x1~x31 등) 개수가 한정되어 있어서 같은 이름을 돌려쓴 결과일 뿐이죠. 만약 이름만 다르게 붙여줄 수 있다면, 이 가짜 의존성은 사라집니다.

Register Renaming은 바로 이 작업을 합니다. CPU 내부에 아키텍처 레지스터보다 훨씬 많은 물리 레지스터(physical register) 를 두고, 명령어가 어떤 아키텍처 레지스터에 쓸 때마다 비어 있는 물리 레지스터 하나를 새로 할당합니다. 그리고 그 후의 명령어가 같은 아키텍처 레지스터를 읽으면, 가장 최근에 매핑된 물리 레지스터에서 값을 읽어옵니다. 결과적으로 같은 이름을 쓰는 명령어들이 서로 다른 물리 레지스터를 보게 되어, WAR·WAW가 사라지고 RAW만 남습니다.

다음 코드를 봅시다.

I1: r1 = r2 + r3
I2: r4 = r1 * 2       ; I1에 RAW 의존
I3: r1 = r5 + r6      ; I1과 WAW, I2와 WAR
I4: r7 = r1 - r8      ; I3에 RAW 의존

I3은 I1·I2와 데이터 흐름상 아무 관계가 없습니다. 그저 우연히 r1이라는 이름을 재사용한 것뿐이죠. 그런데 in-order로 보면 I3은 I1·I2가 끝날 때까지 기다려야 합니다. I1이 캐시 미스 같은 이유로 stall되면 I3·I4까지 같이 묶여 멈춥니다.

이제 물리 레지스터 p10, p11, p12, ...를 할당하면서 리네이밍을 적용해봅시다. 초기 매핑이 r1→p1, r2→p2, ..., r8→p8이라고 하면:

리네이밍 후 의존성 그래프를 다시 그려봅시다.

• I1(p10) ← I2(p11은 p10을 읽음): RAW
• I3(p12) ← I4(p13은 p12를 읽음): RAW
• I1과 I3은 더 이상 같은 레지스터에 쓰지 않음 → WAW 사라짐
• I2와 I3 사이의 가짜 WAR도 사라짐

즉 명령어 흐름이 두 개의 독립적인 사슬 (I1 → I2) 와 (I3 → I4) 로 깔끔하게 나뉩니다. I1이 stall에 빠져도 I3·I4는 자유롭게 먼저 실행될 수 있고, 2-way 슈퍼스칼라라면 두 사슬을 동시에 진행해서 I1의 지연을 가릴 수도 있습니다.

리네이밍 전후의 critical path 길이를 비교하면 효과가 명확합니다. 원본은 I1 → I2 → I3 → I4로 묶여 4 사이클이 필요하지만(가짜 의존성 때문), 리네이밍 후에는 I1 → I2와 I3 → I4가 병렬이므로 2 사이클이면 충분합니다. Average ILP가 4/4 = 1.0에서 4/2 = 2.0으로 두 배가 된 것이죠. 가짜 의존성을 걷어내자 프로그램 안에 숨어 있던 ILP가 드러난 셈입니다.

Reservation Station (Issue Queue)

리네이밍으로 가짜 의존성은 걷어냈지만, RAW 의존성은 여전히 남아 있습니다. 어떤 명령어는 자기 입력 값이 아직 계산되지 않아서 당장 실행할 수 없고, 어떤 명령어는 바로 실행할 수 있습니다. 매 사이클마다 "누가 지금 실행 가능한가" 를 추적하고, 가능한 명령어를 비어 있는 PE에 골라 보내주는 메커니즘이 필요합니다. 이 역할을 맡는 구조가 Reservation Station (RS), 또는 Issue Queue 입니다.

리네이밍을 거친 명령어는 곧장 PE로 가지 않고 일단 RS의 한 칸(엔트리)에 들어가 대기합니다. 각 엔트리는 대략 다음과 같은 정보를 가집니다.

리네이밍 직후, 이미 레지스터 파일에 값이 있는 피연산자는 ready=1로 채워지고, 아직 누군가가 계산 중인 피연산자는 ready=0인 채로 들어옵니다. 그리고 매 사이클 RS는 두 가지 동작을 동시에 합니다.

1. Wakeup: 어떤 PE가 결과를 다 계산하면, 그 결과는 CDB(Common Data Bus) 라는 공용 버스를 통해 RS의 모든 엔트리에 동시에 방송됩니다. 자기가 기다리던 물리 레지스터 번호와 일치하는 엔트리들은 해당 피연산자를 받아 채우고 ready를 1로 바꿉니다.
2. Select: 두 피연산자가 모두 준비된(ready1 = ready2 = 1) 엔트리들 중에서, 사용 가능한 PE 수만큼을 골라 발행합니다. 골라진 엔트리는 RS에서 빠져나갑니다.

이 두 동작이 매 사이클 반복되면서, 명령어들은 프로그램 순서와 무관하게 준비되는 대로 실행됩니다.

Reorder Buffer (ROB)

RS 덕분에 명령어들이 뒤죽박죽 순서로 실행될 수 있게 되었습니다. 그런데 이대로 결과를 곧장 레지스터 파일과 메모리에 써버리면 큰 문제가 생깁니다.

• 분기 예측 실패: 분기 예측이 틀리면 그 뒤로 투기적으로 실행한 명령어들의 결과를 모조리 취소해야 하는데, 이미 레지스터 파일에 써버렸다면 되돌릴 수 없습니다.
• 예외(Exception): 어떤 명령어가 페이지 폴트나 0 나누기 같은 예외를 일으켰을 때, 프로그래머가 보는 시점에서 그 명령어 이전의 모든 명령어는 반영되어 있고, 이후의 모든 명령어는 반영되지 않은 상태여야 합니다. 이전 글에서 설명했듯이, 이를 precise exception 이라고 합니다.

이 두 요구사항을 만족시키려면, 비록 실행은 OoO로 했더라도 결과를 아키텍처 상태에 반영하는 단계만큼은 다시 프로그램 순서대로 해야 합니다. 이 역할을 맡는 구조가 Reorder Buffer (ROB) 입니다.

ROB는 이름 그대로 원형 큐(circular queue) 형태의 버퍼로, 디스패치 단계에서 명령어들이 프로그램 순서대로 한 칸씩 자리를 잡습니다. 각 엔트리는 대략 다음을 담습니다.

명령어의 일생은 다음과 같이 흘러갑니다.

1. Dispatch (in-order): 디코드 후 ROB 꼬리에 자리를 잡고, 동시에 RS에도 엔트리를 만듭니다.
2. Execute (out-of-order): RS가 준비된 명령어를 PE로 보내 실행합니다.
3. Writeback: 실행이 끝나면 결과를 물리 레지스터에 쓰고, 해당 ROB 엔트리의 done을 1로 표시합니다.
4. Commit / Retire (in-order): ROB의 머리(head) 에 있는 엔트리가 done = 1이 되면, 그 명령어를 "공식적으로 완료"시킵니다. 즉 논리 레지스터 매핑을 갱신해 외부에서도 그 결과가 보이게 만들고, store라면 메모리에 실제로 값을 기록합니다. 그리고 ROB 머리가 다음 칸으로 전진합니다.

만약 4번 단계에서 어떤 엔트리에 예외 표시가 되어 있다면, ROB는 그 엔트리부터 뒤쪽의 모든 엔트리를 통째로 폐기하고 RS도 비웁니다. 분기 예측 실패도 같은 방식으로 처리됩니다. 아직 commit되지 않은 명령어들은 아키텍처 상태에 아무 영향도 주지 않았으므로, 이렇게 버려도 안전하죠.

OoO로 메모리 지연 숨기기

지금까지 본 OoO의 효과는 주로 ALU 명령어 사이의 짧은 stall을 가리는 데 초점이 있었지만, 사실 OoO가 실제 CPU에서 얻는 가장 큰 이득은 메모리 접근 지연을 숨기는 것입니다.

현대 CPU의 클럭은 빠른데 DRAM은 그만큼 빨라지지 못해서, 캐시 미스 한 번의 비용은 끔찍하게 큽니다.

OoO는 이 시간을 그냥 흘려보내지 않습니다. load가 메모리 응답을 기다리는 동안, ROB와 RS에 들어와 있는 뒤쪽 명령어들 중 그 load에 의존하지 않는 것들을 먼저 실행해버립니다. load의 결과가 도착할 때쯤이면, 독립적인 명령어들은 이미 상당 부분 처리되어 있는 거죠.

Load-Store Queue (LSQ)

메모리 접근 명령어(load, store) 를 실행할때는 한 가지 까다로운 점이 있습니다. 레지스터는 리네이밍으로 가짜 의존성을 없앨 수 있었지만, 메모리 주소는 리네이밍할 수 없습니다. 같은 주소에 쓰는 두 store, 같은 주소를 읽는 load와 store 사이에는 진짜 데이터 의존성이 존재하고, 게다가 그 주소는 명령어가 EX 단계에서 베이스 레지스터·오프셋을 더해보기 전까지는 알 수도 없습니다.

이 문제를 다루기 위한 전용 구조가 Load-Store Queue (LSQ) 입니다. 보통 두 부분으로 나뉩니다.

• Store Queue (SQ): dispatch 시점에 store 명령어가 자리를 잡습니다. 주소와 쓸 값이 계산되면 해당 엔트리에 채워지지만, 실제 메모리에는 ROB가 commit해줄 때까지 쓰지 않습니다. 분기 예측 실패나 예외로 squash되면 그냥 SQ에서 빼내면 되므로 안전하죠.
• Load Queue (LQ): load 명령어가 dispatch될 때 자리를 잡습니다. load는 보통 OoO로 일찍 실행해야 메모리 지연을 숨길 수 있으므로, ROB commit을 기다리지 않고 데이터를 가져옵니다.

LSQ가 풀어야 할 두 가지 핵심 문제가 있습니다.

1. Store-to-load forwarding — load가 메모리에서 데이터를 가져오기 전에, 자기보다 앞선(older) store들 중 같은 주소에 쓴 것이 SQ에 남아 있는지 먼저 확인해야 합니다. 만약 있다면 그 store가 아직 메모리에 반영되지 않았더라도 SQ에서 직접 값을 받아옵니다. 이것이 store-to-load forwarding 입니다. 이게 없다면 load는 캐시에 있는 낡은 값을 읽어버리겠죠.

I1: store [r10], r1     ; r10 주소에 r1을 씀
I2: load  r2, [r10]     ; 같은 주소에서 읽음

I1이 아직 commit되지 않아 메모리에 반영되지 않았더라도, I2는 SQ에서 I1의 값을 직접 받아 r2에 넣을 수 있습니다.

2. Memory disambiguation — load는 자기보다 앞선 store의 주소를 다 알기 전엔 원칙적으로 실행할 수 없습니다. 어떤 store가 자기랑 같은 주소를 쓸지 모르니까요. 하지만 그렇게 보수적으로 굴면 OoO의 이점이 거의 사라집니다. 그래서 현대 CPU는 load도 투기적으로 실행합니다. "앞선 store들이 나랑 다른 주소일 거야" 라고 가정하고 일찍 메모리에서 값을 가져오는 거죠.

나중에 그 앞선 store가 실제로 주소를 알게 되었을 때, 이미 일찍 실행된 load들이 LQ에 남아 있는지 검사합니다. 만약 같은 주소를 미리 읽어버린 load가 있다면 그 load는 잘못된 값을 가져온 것이므로, 그 load와 그 뒤의 모든 명령어를 ROB squash와 동일한 방식으로 폐기하고 다시 실행합니다. 이를 memory ordering violation 이라고 부릅니다.

OoO의 제어 추측

여기까지 설명에는 한 가지 큰 가정이 숨어 있었습니다. ROB와 RS에 뒤쪽 명령어가 충분히 들어와 있다는 것이죠. ALU 명령어들이 죽 늘어선 직선 코드라면 별 문제가 안 되지만, 실제 코드에는 5~6 명령어마다 한 번씩 분기(branch) 가 끼어 있습니다. 분기를 만나면 다음에 어느 명령어를 가져와야 할지 결정되어야 비로소 fetch를 계속할 수 있는데, 그 결정은 보통 분기 명령어가 EX 단계에서 실제로 실행될 때까지 알 수 없습니다.

만약 CPU가 정직하게 "분기가 풀릴 때까지 기다리자"고 한다면 어떻게 될까요? 큰 ROB도, 넓은 issue width도 모두 무용지물이 됩니다. 분기가 풀리는 그 수십 사이클 동안 ROB는 텅 비어 있게 되고, 앞 절에서 본 메모리 지연 숨기기 효과도 사라져버립니다. 따라서 OoO가 의미 있게 동작하려면 분기를 기다리지 않고 넘어서야 합니다.

이를 위해 도입되는 것이 제어 추측(Control Speculation) 입니다. 분기의 결과를 예측해서, 그 예측이 맞다고 가정하고 일단 다음 명령어들을 계속 fetch하고 ROB에 집어넣어 실행해버리는 것이죠. 예측이 맞으면 그 명령어들은 정상적으로 commit되고, 틀리면 모두 폐기하고 올바른 경로에서 다시 시작합니다.

분기 예측 자체는 이전 글에서 다뤘으므로, 여기서는 "예측기가 어떤 식으로든 taken/not-taken과 목적지 주소를 알려준다"는 정도로 넘어가겠습니다. 중요한 건 예측이 틀렸을 때 어떻게 깨끗이 되돌리느냐, 그리고 한 사이클에 여러 명령어를 fetch할 때 분기를 어떻게 다루느냐 입니다.

슈퍼스칼라 fetch와 분기

슈퍼스칼라 CPU는 매 사이클 한 개가 아니라 여러 개의 명령어를 한꺼번에 fetch합니다. 4-way라면 한 사이클에 4 명령어, 8-way라면 8 명령어가 동시에 들어오죠. 그런데 이 fetch 그룹 안에 분기가 끼어 있다면 다음 사이클의 nextPC (nPC)를 어떻게 정해야 할까요?

2-way fetch를 예로 들어 세 가지 경우를 봅시다.

Case 1: 두 명령어 모두 분기가 아니거나, 둘 다 not-taken으로 예측됨

가장 평범한 경우입니다. 그냥 다음 두 명령어로 이어가면 되므로

$$ nPC = PC + 8 $$

이 됩니다 (한 명령어 4바이트 가정). 명령어 fetch는 끊김 없이 진행됩니다.

Case 2: 둘 중 하나가 taken으로 예측된 분기

이 경우 nPC는 그 분기의 예측된 목적지 주소 가 됩니다.

$$ nPC = \text{predicted target} $$

만약 taken 분기가 fetch 그룹의 두 번째 위치라면 첫 번째 명령어는 정상적으로 파이프라인에 흘려보내고, 다음 사이클부터 target에서 fetch를 이어가면 됩니다.

Case 3: 두 명령어 모두 분기

이게 가장 까다롭습니다. 첫 번째 분기의 예측 결과를 먼저 봐야 합니다.

• 첫 번째 분기가 not-taken으로 예측되면, 두 번째 분기까지 그대로 살리고 두 번째 분기의 예측에 따라 nPC를 결정합니다.
• 첫 번째 분기가 taken으로 예측되면, 두 번째 분기는 이미 같은 사이클에 fetch되어 버린 상태입니다. 하지만 첫 번째 분기가 taken이라면 두 번째 분기는 실제로는 실행되어선 안 되는 명령어이므로, fetch는 됐지만 파이프라인에서 흘려보내야 합니다. nPC는 첫 번째 분기의 예측 target이 됩니다.

이 마지막 시나리오는 슈퍼스칼라 fetch의 본질적인 비효율을 보여줍니다. issue width가 클수록 한 fetch 그룹 안에 분기가 둘 이상 들어올 확률이 높아지고, 그만큼 fetch 슬롯이 버려지는 일이 잦아집니다. 이 손실을 줄이기 위해 현대 CPU는 한 사이클에 분기 예측을 여러 개 동시에 수행할 수 있는 멀티포트 BTB와 예측기를 두기도 하지만, 본질적으로 "한 사이클에 여러 분기를 다루는 것"은 fetch 단계의 복잡도를 크게 높이는 부분입니다.

잘못된 예측에서의 복구 (Recovery)

분기 예측이 틀렸다는 사실은 그 분기 명령어가 EX에서 실제로 실행되어야 알 수 있습니다. 그런데 그 시점에는 이미 ROB·RS에 분기 뒤쪽 명령어들이 잔뜩 들어와 있고, 일부는 실행이 끝나 물리 레지스터에 결과까지 써놨을 수 있습니다. 이 모든 것을 마치 처음부터 없었던 것처럼 되돌려야 합니다.

다행히 앞서 본 ROB의 in-order commit 원칙 덕분에, 잘못된 예측 경로의 명령어들은 아직 commit되지 않았습니다. 즉 아키텍처 레지스터 파일과 메모리에는 영향을 주지 않은 상태죠. 따라서 복구는 다음 단계로 이루어집니다.

1. Squash: ROB에서 잘못 예측한 분기 이후의 모든 엔트리를 폐기합니다. RS 안의 해당 명령어들도 함께 비웁니다. 폐기된 명령어가 점유하던 물리 레지스터는 free list로 반납됩니다.
2. RAT 복원: Register Renaming은 "어떤 아키텍처 레지스터가 지금 어떤 물리 레지스터에 매핑되어 있는가"를 Register Alias Table (RAT) 로 추적합니다. 분기 예측 시점의 RAT 상태를 미리 저장(snapshot)해두었다가, 예측이 틀렸을 때 그 스냅샷으로 되돌립니다. 이렇게 해야 "마치 이 분기 직후부터 실행하는 것처럼" 리네이밍을 다시 시작할 수 있습니다.
3. Fetch 재시작: PC를 분기의 올바른 목적지로 바꾸고, 거기서부터 새로 fetch를 시작합니다.

이 모든 작업은 보통 한두 사이클 안에 끝나도록 하드웨어가 설계되어 있습니다. 하지만 그 후 ROB가 다시 채워지고, 새 명령어들이 EX 단계까지 도달해서 다시 백엔드가 풀가동되기까지는 추가로 수십 사이클이 들어갑니다. 이 전체 비용을 branch misprediction penalty 라고 부르며, 깊은 파이프라인의 현대 CPU에서는 보통 15~20 사이클 정도입니다. 이래서 분기 예측 정확도가 1%만 떨어져도 성능에 크게 영향을 주는 거죠.

다음 코드를 봅시다.

I1: cmp r1, 0
I2: beq L1            ; 분기, taken 예측
I3: r2 = r3 + r4      ; (예측된 경로의 명령어)
I4: r5 = r2 * r6
I5: store [r7], r5
L1: ...

OoO + 분기 예측 머신에서:

• Cycle 1: I1, I2가 dispatch. 예측기가 "I2는 taken" 이라고 알려주므로 fetch는 L1 쪽으로 점프하고, 이때의 RAT를 스냅샷으로 저장합니다.
• Cycle 2~: L1 이후 명령어들이 계속 dispatch되어 ROB에 들어오고, 일부는 RS 에서 실행을 시작합니다.
• Cycle 5: I2가 EX에서 실제로 실행되어 보니, 사실은 not-taken 이었음이 드러납니다. 예측이 틀렸습니다.
• Cycle 6: ROB에서 I2 이후의 모든 엔트리(L1 이후 명령어들)를 squash합니다. RS도 비웁니다. RAT는 Cycle 1에 저장해둔 스냅샷으로 복원됩니다.
• Cycle 7~: PC를 I3로 돌리고 fetch를 재시작합니다. I3, I4, I5가 새로 dispatch되기 시작합니다.

만약 squash가 없었다면 L1 쪽 명령어들이 그대로 commit되어 잘못된 결과가 프로그래머에게 보이게 됩니다. ROB의 in-order commit 원칙과 RAT 스냅샷 덕분에, 잘못된 예측이 겉으로 드러나지 않고 조용히 흡수될 수 있는 것입니다.

P6 스타일 vs R10K 스타일

지금까지 설명한 OoO 구조는 추상적인 모델이었지만, 실제 CPU들은 두 가지 큰 흐름으로 나뉩니다. 중요한 차이는 "명령어의 결과 값을 어디에 저장하느냐" 입니다.

P6 스타일 (Pentium Pro, AMD K8/Opteron Core)

1995년 Intel Pentium Pro에서 처음 등장한 방식입니다. 이름이 "P6 마이크로아키텍처" 라서 P6 스타일이라 부릅니다. AMD의 K8(Opteron, Athlon 64) 코어도 같은 계열에 속합니다.

이 방식의 핵심은 ROB가 두 가지 일을 동시에 한다는 것입니다.

1. 원래 ROB 역할: 명령어를 in-order로 줄 세워 commit 순서를 보장
2. 추가 역할: 아직 commit되지 않은 명령어들의 결과 값을 직접 들고 있음

즉, P6 스타일에서 명령어가 실행을 끝내면 결과 값이 자기 ROB 엔트리의 한 필드에 기록됩니다. 별도의 물리 레지스터 파일은 없습니다. 그리고 commit 시점이 되면, ROB 엔트리에 들어 있던 값이 별도로 존재하는 아키텍처 레지스터 파일(ARF) 로 복사되고 ROB 엔트리는 비워집니다.

ROB 엔트리는 대략 이렇게 생겼습니다.

이 설계에서 RS의 명령어가 피연산자를 읽으려면 두 군데를 봐야 합니다. 이미 commit된 값이라면 ARF에서, 아직 commit 안 된 in-flight 값이라면 ROB 엔트리 에서 가져옵니다. RAT는 "이 아키텍처 레지스터의 최신 값이 ARF에 있는지, 아니면 어느 ROB 엔트리에 있는지"를 가리키는 포인터 역할을 합니다.

장점:

• 구조가 직관적이고 RAT의 복원이 비교적 단순합니다. 분기 예측 실패 시 squash된 ROB 엔트리들을 그냥 버리면 되고, ARF는 손댈 필요 없으니까요.
• Precise exception 보장이 깔끔합니다. ARF에 들어 있는 값들은 정의상 commit된 것뿐이라, ARF 자체가 곧 "아키텍처 상태" 입니다.

단점:

• 같은 값이 ROB와 ARF에 두 번 존재할 수 있어 저장 공간이 낭비됩니다.
• Commit 때마다 ROB → ARF로 값을 물리적으로 복사해야 합니다. issue width가 넓어지면 commit 포트도 함께 늘려야 해 비용이 큽니다.
• ROB 엔트리에 값까지 들어가니 엔트리 크기가 커지고, 큰 ROB를 만들기 부담스러워집니다.

AMD Opteron(K8) 코어도 이 계열입니다. K8은 정수 ROB와 부동소수점 ROB를 분리 하는 등 변형을 가했지만, "결과 값이 ROB 안에 산다"는 본질은 동일합니다. K8의 경우 정수 코어는 통합 reservation station 대신 명령어 종류별로 작은 RS를 두는 distributed scheduler 를 채택했고, 정수 RS는 dispatch 시점에 피연산자 값을 직접 복사해 들고 있는 형태로 만들어졌습니다.

R10K 스타일 (MIPS R10000)

1996년 MIPS R10000에서 정립된 방식이고, Alpha 21264, IBM Power, 그리고 Intel도 Sandy Bridge(2011) 이후로 이 스타일로 옮겨갔습니다. 오늘날 거의 모든 고성능 OoO CPU가 R10K 스타일입니다.

핵심 아이디어는 별도의 ARF를 없애고 모든 레지스터 값을 단일 물리 레지스터 파일(PRF)에 모은다는 것입니다. PRF는 아키텍처 레지스터 개수보다 훨씬 많은 엔트리를 가지며(예: MIPS R10000은 32개의 아키텍처 정수 레지스터에 대해 64개의 물리 정수 레지스터), in-flight인 값과 commit된 값이 모두 이 한 곳에 함께 살게 됩니다.

여기서 ROB는 값을 들고 있지 않습니다. 대신 "이 명령어가 어느 물리 레지스터에 쓰기로 되어 있다" 라는 매핑 정보만 보관합니다.

명령어가 dispatch될 때 free list에서 빈 물리 레지스터 하나를 받아 dst (물리)에 넣고, 그 직전까지 같은 논리 레지스터를 가리키던 물리 레지스터 번호를 prev dst에 기록해둡니다. 이 정보가 squash·commit 시 free list 관리의 핵심이 됩니다.

명령어가 EX에서 실행을 끝내면 결과 값을 곧장 PRF의 dst (물리) 슬롯에 씁니다. 이게 끝입니다. 더 이상 commit 시점에 데이터를 옮길 필요가 없습니다. RS의 다른 명령어들도 처음부터 PRF만 바라보고 있기 때문에, 이 값이 쓰이는 순간부터 바로 forwarding이 가능합니다.

그렇다면 commit은 무엇을 할까요? 대단한 일을 하는 건 아니고, 두 가지입니다.

1. RAT (architectural map) 갱신: "이 논리 레지스터의 공식 매핑은 이제 새 물리 레지스터다" 라고 표시. 이 표는 squash 시 RAT 복원에 쓰입니다.
2. prev dst에 적힌 옛 물리 레지스터를 free list로 반납. 이전 매핑은 더 이상 누구도 안 보니까요.

반대로 squash 때는: 폐기되는 ROB 엔트리들의 dst (물리)를 free list로 돌려 보내고, RAT를 분기 예측 시점의 스냅샷으로 복원합니다.

장점:

• Commit이 매우 가볍습니다. 데이터 복사가 없고 포인터 갱신만 있으니까요.
• 결과 값이 PRF에 한 곳에만 존재해 저장 공간이 낭비되지 않습니다.
• ROB 엔트리가 작아져서 같은 면적에 더 큰 ROB를 만들 수 있습니다 — 이게 결국 앞 절에서 본 메모리 지연 숨기기의 윈도우 크기를 키워줍니다.
• PRF 포트 수를 잘 설계하면 wakeup·forwarding 회로가 단순해집니다.

단점:

• Free list, RAT, ROB가 더 복잡한 방식으로 맞물려야 합니다. squash 시 free list 복원이 까다로워서 별도의 history buffer나 walk 메커니즘이 필요 합니다.
• PRF 자체가 매우 큰 멀티포트 SRAM이 되어 면적·전력 부담이 큽니다. 4-way 머신 이라면 issue 단계에서만 8개 read 포트가 필요할 수 있습니다.

MIPS R10000과 AMD Opteron Core 비교

두 CPU는 거의 같은 시대(1996년경)에 등장했지만 정반대의 설계 철학을 보여 줍니다.

R10000은 학술적·이론적으로 가장 깔끔한 OoO 설계로 평가받습니다. 통합 PRF, 명확한 RAT/free list 관리, 명령어 종류별 RS 분리 — 거의 모든 후속 OoO CPU의 청사진이 되었죠. 다만 물리 레지스터 64개와 ROB 32개로 윈도우가 좁아 메모리 지연 숨기기 능력은 오늘날 기준으로 제한적이었습니다.

Opteron K8은 x86이라는 복잡한 ISA를 OoO로 돌리기 위해 P6 스타일을 택했습니다. x86 명령어를 내부 매크로 op로 디코드한 뒤, 각 매크로 op가 ROB·RS·LSQ를 거쳐 실행되는 식이죠. P6 스타일 덕분에 Intel/AMD가 이미 가지고 있던 Pentium Pro 계통의 노하우를 그대로 활용할 수 있었고, K8은 이를 기반으로 큰 ROB(72)와 넓은 LSQ(44)를 두어 당시 Pentium 4를 능가하는 메모리 성능을 보였습니다.

흥미롭게도 Intel 자신도 Pentium 4까지 P6 스타일을 유지하다가, Sandy Bridge (2011) 부터 R10K 스타일의 통합 PRF로 전환했습니다. 이유는 단순합니다 — ROB를 계속 키우려면 결국 R10K 스타일이 필요했기 때문입니다. 오늘날 Apple M 시리즈, ARM Cortex-X 시리즈, AMD Zen, Intel Golden Cove 모두 R10K 스타일이며, ROB 크기는 200~600 엔트리에 이릅니다. 메모리 장벽 시대를 견디기 위한 거대한 명령어 윈도우가 R10K 스타일 위에서 비로소 가능해진 것이죠.

칩 멀티프로세서

지금까지는 한 코어 안에서 ILP를 최대한 끌어내는 이야기를 했지만, 2000년대 중반부터 이 방향에는 분명한 한계가 보이기 시작했습니다. issue width를 더 넓히고 ROB를 더 키워도 추가되는 트랜지스터 대비 성능 향상이 점점 작아졌고, 무엇보다 클럭을 더 올리지 못하는 전력·열 문제(power wall) 가 결정타였습니다. Pentium 4가 4GHz 벽에 부딪힌 사건이 상징적이죠.

이때 등장한 대안이 칩 멀티프로세서(Chip-Multiprocessor, CMP), 흔히 멀티코어 라고 부르는 구조입니다. 한 코어를 더 크고 빠르게 만드는 대신, 적당한 크기의 코어 여러 개를 한 다이(die)에 올려놓는 발상이죠. 2005년 AMD Athlon 64 X2와 Intel Pentium D를 시작으로, 이후 모든 주류 CPU는 멀티코어가 되었습니다.

CMP는 트랜지스터 예산을 ILP가 아니라 TLP(Thread-Level Parallelism)에 투자합니다. 각 코어가 별개의 스레드를 독립적으로 실행하므로, ILP를 짜낼 때처럼 의존성·분기·캐시 미스에 시달리지 않고 거의 코어 수에 비례해 처리량을 늘릴 수 있습니다. 글 첫머리에서 본 ILP/TLP/DLP 분류로 돌아가자면, 슈퍼스칼라·OoO가 ILP를 위한 하드웨어였다면 CMP는 TLP를 위한 하드웨어인 셈입니다.

물론 공짜는 아닙니다. 여러 코어가 같은 메모리를 공유하므로 캐시 일관성(cache coherence) 프로토콜이 필요하고, 프로그래머 입장에서는 명시적인 멀티스레드 프로그래밍 을 해야 비로소 멀티코어의 이점을 누릴 수 있습니다. 단일 스레드만 돌리는 프로그램은 코어가 아무리 많아도 한 코어 위에서만 돌죠. 이 때문에 CMP의 도입은 "하드웨어가 알아서 빨라지는 시대"가 끝나고 "소프트웨어가 병렬성을 명시적으로 다뤄야 하는 시대"로 넘어가는 분기점이 되었습니다.