Out-of-order execution, register renaming and speculation

An in-order pipeline stops at the first instruction that isn't ready. If a load takes four cycles, everything behind it waits, even instructions that have nothing to do with it. The pipeline's other units sit idle while there's useful work a few instructions further down.

An out-of-order core doesn't wait. It looks ahead into the program, picks whichever instructions have their inputs ready, and runs them, so a slow instruction no longer blocks unrelated ones. To the program, nothing has changed: results are still committed as if every instruction ran one after the other, in order.

The idea is old. The CDC 6600 (1964) used a scoreboard to track which registers were still being computed and let independent instructions proceed. The IBM System/360 Model 91 (1967) introduced Tomasulo's algorithm, with register renaming and results broadcast to waiting instructions. It became mainstream in desktop CPUs with the Pentium Pro in 1995.

One slow chain shouldn't block the others

The demos in this chapter run a program on the emulator, then schedule the instructions it executed on two cores with the same resources: 2 instructions per cycle, loads 4 cycles (an L1 hit), multiplies 3, divides 20, everything else 1. One core starts instructions in program order; the other doesn't.

Each row is one instruction: D when it enters the core, · while it waits, L for a load, E for execution, R when it retires. On the in order core, the program takes 26 cycles. The load of ebx can't start until the eax chain in front of it has started its last multiply, and the ecx chain waits in turn. The three chains run one after another, even though they don't share a single value.

Switch to out of order: 15 cycles. The three loads start almost together, and the multiplies of each chain follow as soon as their own inputs arrive. The only order left is the one the data imposes.

How an out-of-order core is organized

The core is split into an in-order part, an out-of-order part, and an in-order part again:

1. Front end, in order. Fetch, predict branches, decode into µops, rename registers (see below), and dispatch each µop into the reorder buffer (ROB) and a scheduler (also called reservation stations).
2. Execution, out of order. Every cycle, the scheduler picks µops whose operands are ready and sends them to free execution units. When a µop finishes, it broadcasts its result to the µops waiting for it.
3. Retirement, in order. The ROB lists µops in program order. The oldest one retires — its result becomes official — only once it's finished and everything before it has retired.

The ROB is the instruction window: how far ahead of the oldest unfinished instruction the core can look for work. Current cores have large ones: 512 entries in Intel's Golden Cove, 320 in AMD's Zen 4.

Why retirement stays in order

Tanenbaum's out-of-order example also lets instructions complete out of order, to keep it simple. Real cores don't, because of precise exceptions. When an instruction faults — a page fault, a division by zero — the operating system must see a clean state: every instruction before it done, none after it. That's what makes it possible to handle the fault and resume.

In-order retirement gives this for free. A faulting instruction is only marked in the ROB. When it reaches the head, everything older has retired and nothing younger has, so the core discards the younger work and raises the exception exactly there. Interrupts are handled the same way.

False dependences and register renaming

Only a read after write (RAW) is a true dependence: the second instruction needs the value the first one produces. Two other orderings exist only because the program happens to reuse a register name:

• Write after read (WAR): an instruction wants to overwrite a register that an older instruction hasn't read yet.
• Write after write (WAW): two instructions write the same register, and the later value must be the one that remains.

Here are two unrelated computations that both use eax, as compiled code does all the time with only 16 registers:

With renaming off, the second load has to wait: it would overwrite eax before the first chain is done with it. The program takes 17 cycles, in order or not.

Turn renaming on: 11 cycles out of order. The in-order core stays at 17. Register renaming gives every result its own physical register. The 16 names of the ISA — rax, rbx, … — are just entries in a register alias table that says which physical register currently holds each name. A core has a couple of hundred physical registers behind those 16 names. When the second mov eax, … is renamed, eax simply points to a fresh physical register, and both chains run side by side. WAR and WAW vanish; only true dependences remain.

The flags are renamed too. In the first demo, switch renaming off: the three chains slow down to 24 cycles, because every imul also writes the flags register, so the chains collide on it even though their data registers are different.

Renaming also allows some instructions to finish without executing at all. xor eax, eax is recognized as "set to zero, no dependence on the old value", and on many cores a register-to-register mov just copies an entry in the alias table.

Looking further ahead: the window

The bigger the window, the further ahead the core can find independent work — especially loads, which can take hundreds of cycles if they miss the caches. Starting several of them at once is called memory-level parallelism.

add eax, [m] is split into two µops: the load, which only needs the address, and the addition, which needs the loaded value and eax. With a window of 4, the core holds just one iteration and the loop takes 115 cycles. Raise it to 32: 52 cycles. The loads of the next iterations start while earlier ones are still in flight, and only the one-cycle additions form a chain. Set width to 4 as well: 29 cycles, more than two instructions per cycle. The in-order core needs 100 to 116 cycles in all three settings.

Loads and stores need extra care, because their addresses aren't known until they execute. The load/store queues track all memory µops in flight. A load that reads an address an older, not-yet-retired store is writing gets the value straight from the store queue (store-to-load forwarding). A load is also allowed to run before older stores whose address isn't known yet, betting that they don't overlap; if they do, it is replayed.

Speculation

The window doesn't stop at branches. With branch prediction, the front end keeps dispatching down the predicted path, so a large part of the window is usually speculative: instructions that may turn out to be on the wrong path. That's safe because of in-order retirement. When a branch resolves as mispredicted, every µop younger than it is flushed from the ROB, the alias table is restored to its state at the branch, and fetch restarts at the right address. None of the wrong-path results were ever retired.

Tanenbaum also describes speculation done by the compiler: hoisting a load above a branch, with special instructions and poison bits so that a speculative load that faults only raises the error if its value is actually used. The Itanium's NaT bit worked this way. Modern out-of-order cores do the same thing in hardware, dynamically, on ordinary code.

When speculation leaks: Spectre and Meltdown

Flushing the wrong path undoes its effect on registers and memory, but not on the caches. A speculative load still brings its line into the cache, and the caches chapter showed how different a hit and a miss are in time. In 2018, researchers turned this into attacks:

• Spectre (variant 1, bounds-check bypass): the attacker trains a branch like if (i < size) to be predicted taken, then calls it with an out-of-bounds i. The core speculatively reads the secret byte at array[i] and uses it as an index into another array, loading one line that depends on the secret. The results are flushed, but by timing which line is now cached, the attacker recovers the byte.
• Meltdown: on many Intel cores of that time, a load from kernel memory in user mode was only blocked when it retired. Speculatively, it returned the data and could leak it the same way.

The fixes span every level: kernel page-table isolation (KPTI), which keeps kernel memory unmapped while user code runs; speculation barriers like lfence and index masking inserted by compilers; microcode updates; and new silicon. These are transient-execution attacks: they read what the machine did on a path that officially never happened.

The limits

Out-of-order execution finds parallelism that's already in the program; it can't create it. A single chain of dependent operations — like the running sum eax above — runs at the speed of that chain, however big the window. Bigger windows, more physical registers and wider schedulers also cost area and power, and they have to be searched every cycle. That's one reason core designs grew slowly wider and deeper, and why the next step was more cores — the subject of the multicore chapters.

Takeaways

• An out-of-order core executes µops as soon as their operands are ready, not in program order, but still retires them in order.
• The reorder buffer is the instruction window, and in-order retirement gives precise exceptions.
• Only RAW dependences are real. Register renaming onto physical registers removes WAR and WAW, including on the flags.
• A large window provides memory-level parallelism. Load/store queues handle memory ordering, with store-to-load forwarding.
• Everything past a predicted branch is speculative and flushed on a misprediction. Its cache side effects are what Spectre and Meltdown exploit.