Out-of-Order Execution
CPU Pipeline & Microarchitecture · CPU Architectures track
6 min read
In this module
Breaking Program Order
In an in-order pipeline, instructions execute strictly in program order. If instruction 5 is sitting on a cache miss (about 100 cycles of nothing), instructions 6, 7, 8, ... all wait behind it, even when they're entirely independent. Out-of-order (OoO) execution breaks that logjam: instructions fire as soon as their inputs are ready, program order be damned.
The OoO Execution Pipeline
The pipeline of a modern out-of-order CPU looks roughly like this:
The front end — fetch, decode, rename — processes instructions in program order. The middle — dispatch, schedule, execute — fires them out of order whenever data is ready. The back end (complete, retire) commits results in program order again.
For contrast, here's the in-order pipeline from lesson 1 running a chain of dependent instructions. Untick Forwarding and count the bubbles. In an in-order core each one is a dead cycle. An out-of-order core would spend those cycles on later instructions that don't depend on the chain.
Instructions
| Cycle | F | D | E | M | W |
|---|---|---|---|---|---|
| 1 | ADD R1, R2, R3 | - | - | - | - |
| 2 | SUB R4, R1, R5 | ADD R1, R2, R3 | - | - | - |
| 3 | AND R6, R4, R7 | SUB R4, R1, R5 | ADD R1, R2, R3 | - | - |
| 4 | OR R8, R1, R6 | AND R6, R4, R7 | SUB R4, R1, R5 | ADD R1, R2, R3 | - |
| 5 | - | OR R8, R1, R6 | AND R6, R4, R7 | SUB R4, R1, R5 | ADD R1, R2, R3 |
| 6 | - | - | OR R8, R1, R6 | AND R6, R4, R7 | SUB R4, R1, R5 |
| 7 | - | - | - | OR R8, R1, R6 | AND R6, R4, R7 |
| 8 | - | - | - | - | OR R8, R1, R6 |
Reservation Stations
After renaming, instructions land in reservation stations — holding buffers where they wait for their operands. Some designs give each group of execution units its own; others, including many Intel cores, use one large unified scheduler that feeds every port. Each entry tracks the operation, the operand values (or tags pointing at future results to wait for), and the destination physical register.
An instruction parks in its reservation station until every operand is available. Once both are ready, the instruction is issued to the execution unit. Multiple instructions in different stations can become ready at the same instant and run in parallel.
The MUL can fire immediately — both operands ready. The ADD has to wait for pReg17, which a prior instruction is still producing.
The foundational algorithm for out-of-order execution came from Robert Tomasulo at IBM in 1967, designed for the System/360 Model 91 floating-point unit. His clever bit was combining register renaming with reservation stations. Instead of waiting for a value to be written to a register and then read back, instructions watch for the value to be broadcast on a "common data bus" and grab it on the fly. WAR and WAW hazards vanish, parallelism goes up. Modern CPUs are all variations on this theme.
The Reorder Buffer
The Reorder Buffer (ROB) is the trick that keeps up the illusion of in-order execution. Instructions enter the ROB in program order at decode. They execute out of order and stash their results there. Then they retire — commit to architectural state — from the head of the ROB, strictly in order.
MUL and SUB have already finished, but they're stuck — they can't retire until LOAD finishes and entry 1 clears the head. That ordering matters because if an exception hits (say, LOAD page-faults), the CPU can pinpoint exactly which instruction caused it and roll back everything after cleanly.
Register Renaming
x86-64 exposes 16 general-purpose architectural registers, but the physical register file holds 100-200+ entries. Register renaming maps each write to an architectural register onto a unique physical register, killing false dependencies in the process:
; Without renaming:add rax, rbx ; writes RAXmov rcx, rax ; reads RAX (true dependency on add)add rax, rdx ; writes RAX - WAW hazard with first add!mov rsi, rax ; reads RAX - must read second add's value
; With renaming (physical registers P1-P200):add P10, P2, P3 ; RAX renamed to P10mov P11, P10 ; reads P10 (correct dependency)add P12, P10, P4 ; RAX renamed to P12 (no WAW conflict!)mov P13, P12 ; reads P12 (correct dependency)Now both ADDs can fire as soon as their inputs are ready, with nothing blocking on the architectural name RAX. The rename table tracks the current architectural-to-physical mapping.
Memory Disambiguation
Memory operations need careful handling under OoO. A store to address X followed by a load from X has to come out the right way around — the load needs to see the stored value. Trouble is, addresses often aren't known until execution.
Memory disambiguation is the machinery that figures out whether a load depends on a prior store. The store buffer holds pending stores with their addresses and values. When a load executes, it cross-checks the store buffer for matching addresses; on a hit, the load grabs its value from the buffer (store-to-load forwarding) without ever going to cache.
If addresses are still unknown, the CPU may speculatively assume no conflict and let the load fly early. If a later-resolving store turns out to clash, the load and everything that depended on it gets replayed.
Performance Impact
Out-of-order execution is the single biggest performance lever in a modern CPU. It hides memory latency by running other instructions during cache misses, soaks up branch misprediction delays (useful work happened in the meantime), and squeezes out instruction-level parallelism that in-order execution would never see.
Without OoO, a modern core would lose a large share of its throughput on typical code, stalling on every cache miss and long-latency instruction; how much depends heavily on the workload. The hardware bill is steep — the ROB, reservation stations, rename tables, and scheduling logic eat real silicon and power. But the speedup is overwhelming, and that's why every flagship core ships it.
There's a security bill too. Everything the core does between a misprediction (or a faulting load) and the moment it notices is thrown away, and the architectural registers never see it. The cache does, though:
Those squashed, "never happened" instructions are called transient instructions, and they're the root of Spectre and Meltdown. Side-Channel Mitigations in Hardware picks the story up from here.