Out-of-Order Execution

An in-order pipeline issues instructions strictly in the order the compiler produced them; if instruction i stalls, every instruction after it stalls too, even if instruction i+1 has all its operands ready. Out-of-order execution (OoOE) breaks this rigidity by separating instruction fetch and decode order from execution order from commit order. Instructions are fetched and decoded in program order, dispatched into a pool of waiting instructions, executed as soon as their operands become available (possibly in a completely different order than they were fetched), and finally committed — writing results into architectural state — strictly in program order again. Three structures make this possible. Register renaming replaces architectural register names with entries in a larger pool of physical registers, so that two instructions that happen to write the same architectural register (e.g., both writing `R1`) are given distinct physical registers and no longer create a false dependence. This eliminates WAR (write-after-read) and WAW (write-after-write) hazards — anti-dependences and output dependences — leaving only true RAW (read-after-write) data dependences, which are the only ones a correct execution must respect. Reservation stations (or, in modern designs, a unified scheduler/issue queue) hold decoded instructions with their renamed source operands, waiting until those operands are produced by other functional units; a common data bus (CDB) or broadcast network delivers each result to every waiting station simultaneously, "waking up" instructions whose last needed operand just arrived. The reorder buffer (ROB) is a circular queue, in program order, of all instructions currently in flight between dispatch and commit; each entry tracks whether the instruction has finished execution and holds its (renamed) destination and result, and the processor retires entries from the head of the ROB only when they are complete, in strict order. The result is a machine that behaves, from the outside, exactly like an in-order processor — same final register and memory state, same exceptions raised at the same points — while internally exploiting far more parallelism. This design pattern is often summarized as "dispatch and commit in order, execute out of order," and it is the defining feature of every modern superscalar core.

The classic realization of this idea is Tomasulo's algorithm, originally designed for the IBM 360/91's floating-point unit and now used, in spirit, in nearly all out-of-order cores. It has four logical phases per instruction, and a single global broadcast mechanism ties them together.

1. Dispatch (issue into the machine). The instruction is decoded, allocated an entry at the tail of the ROB, and allocated a reservation station at a compatible functional unit. Its architectural source registers are renamed: for each source, the register alias table (RAT) is consulted — if the architectural register has an outstanding rename (an in-flight producer), the reservation station records the producer's tag (typically its ROB or physical-register-file index) instead of a value; if there is no outstanding producer, the current committed value is read directly from the register file. The instruction's destination register is renamed to a fresh physical register / ROB entry, and the RAT is updated to point future readers of that architectural register to this new producer.

2. Wait / wakeup. The reservation station holds the instruction until all of its source operand tags have been resolved to actual values. Every cycle, the CDB broadcasts the tag and value of instructions that just finished executing; every reservation station compares (associatively, in parallel) its own pending source tags against the broadcast tag, and if a match occurs, it captures the value. This is the wakeup step. An instruction becomes ready to execute — is selected for dispatch to a functional unit — once all of its operands have arrived.

3. Execute. Once selected, the instruction is sent to its functional unit (ALU, multiplier, load/store unit, etc.) for however many cycles that operation requires. Structural hazards are resolved here: if more instructions are ready than there are functional-unit ports, an arbitration/select policy (e.g., oldest-first) picks a subset each cycle.

4. Write result / broadcast. When execution finishes, the result and its producer tag are broadcast on the CDB, simultaneously updating the ROB entry (marking it complete, storing the value) and waking up any reservation stations waiting on that tag. The reservation station is then freed for reuse.

5. Commit (retire). Independently of execution order, the processor inspects the head of the ROB every cycle. If the instruction at the head has completed (and did not fault, and — if it was a branch — was correctly predicted), its result is written from the ROB into the architectural register file (or, for a store, the memory system), the head pointer advances, and the corresponding rename in the RAT is retired if no younger instruction still refers to it. If the head instruction has not completed, commit stalls for that cycle — no younger instruction, however finished, can commit ahead of it. This in-order-commit rule is what makes the whole machine precise. ``` // One cycle of an out-of-order core, Tomasulo-style, informal pseudocode structure ROBEntry { valid, busy, done, dest_areg, value, exception, is_branch, mispredicted } structure RSEntry { busy, op, tag_src1, val_src1, ready1, tag_src2, val_src2, ready2, dest_tag } ROB : circular queue of ROBEntry, size N, head/tail pointers RAT : map from architectural register -> ROB tag (or "none" = use register file) RegFile : architectural register values (committed state only) RS : array of RSEntry per functional-unit class function DISPATCH(instr): if ROB is full or no free RS for instr's unit: stall tag = ROB.tail (v1, t1, ready1) = resolve(instr.src1) // read RegFile or RAT (v2, t2, ready2) = resolve(instr.src2) rs = allocate RSEntry(instr.op, t1, v1, ready1, t2, v2, ready2, dest_tag=tag) RAT[instr.dest] = tag ROB.push(ROBEntry(valid=true, busy=true, done=false, dest_areg=instr.dest)) RS.insert(rs) function resolve(areg): if RAT[areg] == none: return (RegFile[areg], -, ready=true) else: t = RAT[areg] if ROB[t].done: return (ROB[t].value, -, ready=true) else: return (-, t, ready=false) // wait for broadcast tag t function WAKEUP_AND_SELECT(): for rs in RS where rs.busy and not rs.ready1 or not rs.ready2: pass // handled by BROADCAST below ready_set = { rs in RS : rs.busy and rs.ready1 and rs.ready2 } chosen = arbitrate(ready_set) // e.g., oldest-first, per functional unit for rs in chosen: send rs to its functional unit; rs.busy = false (in flight) function EXECUTE_AND_BROADCAST(): for each functional unit finishing this cycle: (tag, value, exception) = result ROB[tag].done = true ROB[tag].value = value ROB[tag].exception = exception for rs in RS: // associative broadcast compare if rs.tag_src1 == tag: rs.val_src1 = value; rs.ready1 = true if rs.tag_src2 == tag: rs.val_src2 = value; rs.ready2 = true function COMMIT(): entry = ROB[ROB.head] if entry.valid and entry.done: if entry.exception: handle_exception(); flush_pipeline(); return if entry.is_branch and entry.mispredicted: flush_pipeline(); redirect_fetch(); return RegFile[entry.dest_areg] = entry.value if RAT[entry.dest_areg] == ROB.head: RAT[entry.dest_areg] = none ROB.pop() // else: stall commit this cycle ``` The crucial global invariant enforced by this pseudocode is: a physical result never overwrites architectural state until its ROB entry reaches the head and is proven exception-free and correctly speculated. Everything upstream of commit — dispatch, wakeup, execute, broadcast — can happen in any order the data dependences allow.

Hardware complexity per cycle. The wakeup broadcast compares the tag of every completing instruction against the pending source tags of every reservation station entry. If there are `W` reservation stations and the CDB delivers `B` results per cycle, wakeup costs `O(W·B)` comparators per cycle — an associative, fully parallel structure, not a search. Select/arbitration among ready instructions competing for a functional unit is a priority encoder over `O(W)` entries, typically `O(log W)` gate delay if implemented as a tree, though many designs use age-ordered matrices costing `O(W²)` bits of state to track relative age cheaply. The ROB is a simple circular buffer, `O(1)` per operation (push at tail, inspect/pop at head), but detecting when some entry has all its consumers retired, for reclaiming physical registers, again costs bookkeeping proportional to ROB size, `O(1)` amortized with a free-list of physical registers.

Why complexity is bounded, not unbounded. The number of reservation stations and ROB entries is fixed at design time (typically tens to a few hundred entries in real cores), so the instruction window — the set of in-flight instructions the hardware can reorder among — is bounded. This is a deliberate engineering tradeoff: a larger window exposes more ILP but the `O(W·B)` broadcast comparators and `O(W)`-wide select logic grow directly with window size, and associative CAM structures do not scale linearly in area or power. This is precisely why real designs use bounded structures (32–512 ROB entries typical in 2020s cores) rather than unbounded ones, and why increasing window size yields diminishing throughput returns per unit power past some point.

Correctness argument. The claim to prove is: the sequence of committed architectural states produced by the out-of-order machine is identical to the sequence produced by some in-order execution of the same instruction stream (respecting the actual control-flow path taken). The proof rests on three invariants maintained by the mechanism above. 1. Only true dependences constrain execution order. Register renaming assigns a distinct physical destination to every dynamic instruction that writes an architectural register. Hence two instructions can never collide over a physical register the way they might over an architectural one; WAR and WAW hazards, which are naming artifacts rather than real data flow, are eliminated by construction. What remains — an instruction cannot execute before the producer of a value it reads — is a RAW dependence, and the resolve/wakeup logic enforces exactly this: an operand is marked ready only once its producing tag has broadcast a value. So execution order always respects the true dependence DAG, and any topological order of that DAG (which out-of-order execution is free to choose) yields the same final values for each physical register, since each physical register is written exactly once (single static assignment property of renaming). 2. Commit order equals program order. The ROB is a FIFO indexed by dispatch (= program) order; the commit rule only ever advances the head, and only when the head entry is complete. Thus the sequence of writes into architectural registers and memory, as observed by anything outside the core (interrupts, other cores, I/O), is exactly the program order sequence — indistinguishable from in-order execution, satisfying the classical requirement of precise exceptions: at the moment any exception is recognized (at commit of the faulting instruction), every architecturally-prior instruction has already committed and every architecturally-later one has not touched architectural state. This is what allows a page-fault handler, debugger, or `signal` handler to see a clean, sequential machine state. 3. Speculative work is safely discardable. Instructions dispatched past a not-yet-resolved branch are speculative; they occupy ROB and RS entries and may execute and broadcast results, but none of that becomes architectural until commit. If the branch resolves as mispredicted, the ROB entries younger than the branch are simply invalidated/flushed (`ROB.pop` from the tail down to the branch, RAT restored to a checkpoint taken at dispatch of the branch) and fetch is redirected — no architectural state was ever touched by the wrong-path instructions, so no rollback of committed state is needed. This is exactly why speculation composes safely with renaming and the ROB: speculation touches only the "not yet real" side of the commit boundary.

Honest tradeoffs. Out-of-order hardware buys ILP at real cost: renaming tables, CAM-based reservation stations, and wide broadcast buses consume significant die area and dynamic power (CAM compares are notoriously power-hungry per bit compared to RAM reads). Deeper windows help hide longer-latency misses (e.g., last-level cache or DRAM) but with diminishing returns, since the rate of independent ready instructions available in typical code saturates; beyond a certain window size, extra hardware mostly buffers instructions that are still waiting on the same long-latency miss rather than genuinely independent work. Verification complexity also rises sharply — precise-exception and memory-ordering corner cases (load/store disambiguation, speculative loads bypassing stores) are a leading source of processor design bugs.

Consider this small sequence (register names are architectural; assume ADD/SUB take 1 cycle to execute, MUL takes 3, and all instructions are already fetched/decoded and ready to dispatch one per cycle): ``` I1: R1 = R2 + R3 I2: R4 = R1 * R5 // RAW on R1 from I1 I3: R1 = R6 - R7 // WAW on R1 with I1; also enables later readers I4: R8 = R1 + R4 // RAW on R1 from I3 (post-rename), RAW on R4 from I2 ``` Without renaming, `I3` would appear to have a WAW hazard on `R1` with `I1`, and a naive in-order-issue machine might even force `I3` to wait for `I1`'s value to be consumed before overwriting it. With renaming, `I1`'s destination becomes physical register `P10`, and `I3`'s destination becomes physical register `P11` — two entirely distinct storage locations, so `I3` can compute immediately, independent of `I1` and `I2`.

Two points this trace makes concrete. First, I3 executed in cycle 3, before I2 finished its 3-cycle multiply in cycle 6 — a clear case of out-of-order completion, made safe only because renaming gave `I3` its own physical destination `P12`, so it never had to wait for anything related to `I1`'s `R1`. Second, commit still proceeded strictly in program order (I1, then I2, then I3, then I4), even though I3 finished computing long before I2 did; the ROB simply stalled retirement at the I2 entry until I2's multiply completed, guaranteeing that any exception or observer sees state exactly as if the program executed sequentially I1→I2→I3→I4.

Every mainstream high-performance CPU core — Intel Core and Xeon, AMD Zen, Arm's Cortex-A and Neoverse lines, Apple's M-series and A-series — implements some variant of register renaming, reservation stations or unified issue queues, and a reorder buffer (sometimes called a "future file" or physical-register-file-based renaming with an ROB of tags rather than values). The technique is what lets these processors tolerate cache misses, long-latency floating-point and vector operations, and unpredictable memory-system delays without stalling the entire pipeline behind them. It is a prerequisite for effective branch speculation (mispredictions are cheap to recover from precisely because the ROB discards uncommitted work cleanly) and works hand-in-hand with superscalar issue width and multi-level cache hierarchies to determine overall single-thread performance. The same in-order-commit discipline that guarantees precise exceptions here is also what a processor's virtual memory subsystem and operating system rely on for correct page-fault handling and context switching. Looking forward, once a core can already track many independent in-flight instructions and physical registers per architectural thread, it is a comparatively small step to let two independent instruction streams share that same renaming and scheduling hardware — the idea behind Simultaneous Multithreading.

Ask the tutor: How does simultaneous multithreading share this out-of-order machinery — renaming tables, reservation stations, and the ROB — across multiple hardware threads at once?