Superscalar and Out-of-Order Execution

A simple pipeline caps out at one instruction per cycle. Modern cores go well past that by combining two mechanisms that are often treated as one thing but are genuinely separate.

Superscalar means width. The core has multiple copies of the fetch, decode, and execution hardware, so several instructions can be handled in the same cycle. Intel's Golden Cove core, per Intel's public description, decodes up to 6 instructions per cycle, up from 4 in the previous design, and has 12 execution ports, up from 10.

Out-of-order means reordering. The core executes an instruction as soon as its inputs are ready, rather than in program order.

Each helps alone. Together they compound, and the reason is straightforward: a wide machine only pays off if it can find enough independent work to fill its width each cycle, and strict program order almost never supplies that.

Consider a load that misses cache and takes a couple of hundred cycles, followed by work that does not depend on it:

ld   r1, 0(r2)      ; misses, ~200+ cycles
add  r3, r1, r4     ; depends on r1, must wait
mul  r5, r6, r7     ; independent
sub  r8, r9, r10    ; independent

In strict program order the entire machine stops at the add for the full duration of the miss, while a 6-wide core sits idle. The mul and sub need nothing from the load and could have run immediately.

Out-of-order execution lets exactly that happen: the add waits, and the independent instructions proceed past it. The core is looking for instruction-level parallelism, and the practical question is how far ahead it is allowed to look. That distance is the instruction window, and it is why the next few structures exist.

Reordering runs into a subtlety. Not every dependency is real.

add  r1, r2, r3     ; writes r1
sub  r4, r1, r5     ; TRUE dependency: needs r1
mul  r1, r6, r7     ; reuses r1 for something unrelated

The second instruction genuinely needs the first one's result. That is a true dependency and no hardware can remove it. But the third instruction merely reuses the name r1. It does not need the old value at all. If it were allowed to write r1 before the sub reads it, the sub would get the wrong value.

This is a false dependency, an artefact of the architecture having a small fixed set of register names. x86-64 exposes 16 general-purpose integer registers, so compilers recycle names constantly, and each reuse creates a false ordering constraint that would otherwise serialise unrelated work.

The fix is to separate the register names the program uses from the physical storage the core actually has. A core keeps a much larger pool of physical registers and, at rename time, assigns each write a fresh physical register.

program (architectural)        after renaming (physical)
add  r1, r2, r3                add  p31, p12, p13
sub  r4, r1, r5                sub  p32, p31, p15
mul  r1, r6, r7                mul  p33, p16, p17

The two writes to r1 now land in different physical registers, p31 and p33. The false dependency is gone, and the mul can execute whenever it likes, including before the sub. The true dependency, sub on p31, survives renaming intact, exactly as it must.

This is the single most important trick in the whole design. Everything else out-of-order execution does is bookkeeping to make renaming safe in the presence of branches and exceptions.

The shape that matters: the two ends are in order and only the middle is not. Instructions enter in program order and retire in program order, so the architectural state the programmer can observe only ever advances sequentially. Execution in between happens whenever operands are ready. This is what lets the core reorder aggressively while remaining, from the outside, a machine that runs your program one instruction at a time.

If instructions finish out of order, how does the machine handle an exception or a mispredicted branch, where everything after a certain point must be undone?

The reorder buffer, or ROB, is the answer. Every instruction gets a ROB entry at rename, in program order. When it finishes executing, its result is marked ready but is not yet architecturally visible. Instructions retire from the head of the ROB strictly in order, and only at retirement does a result become official.

This gives precise exceptions. If instruction 40 faults, instructions 41 onwards have possibly already executed, but none of them has retired, so their effects can be discarded wholesale. The machine can present a clean architectural state at exactly instruction 40 as though nothing after it had ever started.

The same machinery handles branch mispredictions, which is why the misprediction penalty from the previous lesson is a pipeline refill rather than a correctness problem.

The ROB size sets the instruction window: the maximum number of instructions that can be in flight between issue and retirement. It is the concrete answer to "how far past a stalled instruction can the core keep working?"

Intel's published figures for Golden Cove put the reorder buffer at 512 entries, increased from 352 in the previous Sunny Cove core, with 192 load and 114 store queue entries, up from 128 and 72.

Those numbers are worth holding next to the memory latencies from the next lesson, because they set a hard ceiling. If a cache miss costs on the order of two hundred cycles and the core can hold roughly 512 instructions in flight, then a single miss is survivable, provided there is enough independent work nearby to fill the window. If the code hits a dependent chain of misses, where each load's address comes from the previous load, no window size helps: there is nothing independent to run. That case is pointer chasing, and it is the worst thing you can do to a modern core.

Branch prediction is the famous case, but a modern core speculates in several ways, all following the same pattern: guess, proceed, verify, undo if wrong.

• Branch direction and target. Covered in the previous lesson.
• Memory disambiguation. A load following a store to an unknown address might or might not alias it. Waiting for every prior store address would serialise memory access, so the core predicts that the load does not alias, executes it early, and squashes if it turns out it did.
• Value and address prediction appear in some designs, predicting a load's address from a stride pattern so the access can begin earlier.

The common structure is worth naming, because it explains a whole class of security research: the core does real work on unverified assumptions and relies on being able to erase the result. Erasing architectural state turned out to be easier than erasing every microarchitectural trace, which is the root of the speculative execution vulnerabilities. That is a large topic and this lesson does not attempt it.

If wider is better, why did decode width take roughly fifteen years to move from 4 to 6? Three limits bind.

• Available parallelism. Typical integer code simply does not contain six independent instructions at every point. Studies of instruction-level parallelism have long found that realistic code, with realistic branch prediction, yields a modest sustained IPC regardless of machine width.
• Scheduler cost. The wake-up and select logic that matches ready operands to free units grows roughly quadratically with the number of entries it must compare each cycle. It is also on the critical path, so making it bigger tends to lower the clock.
• Rename and retire bandwidth. Every extra instruction per cycle needs another rename port, another ROB write port, and another retire slot. These are expensive in both area and power.

The result is a design that is wide enough to exploit the parallelism that exists, and no wider. Further gains had to come from somewhere else, which in practice meant more cores, wider vectors, and above all better caches. That is where the next lesson goes.