Out-of-Order Execution and the Reorder Buffer

Tomasulo's algorithm lets instructions execute in whatever order their operands become ready. Wonderful for speed — but it creates a crisis of accountability. Suppose a late instruction has already written its result when an earlier instruction suddenly raises an exception (a page fault, a divide-by-zero). The machine's architectural state is now a mess: a younger instruction's effects are visible, but the older one never finished. How do you deliver a precise exception — one where everything before the faulting instruction is done and everything after it looks untouched — when instructions have been finishing out of order all along?

The answer, from the late 1980s, is one of the most important structures in a modern CPU: the reorder buffer (ROB). The slogan is "execute out of order, but commit in order." Instructions may compute in any order they like, but their results are held in a waiting room and made architecturally official strictly in program order. The messy, speculative, out-of-order world is hidden inside the machine; the outside sees a tidy in-order sequence.

Two kinds of state

The trick is to separate speculative results from committed ones. When an instruction finishes executing, its result is not written straight into the architectural registers or memory. It goes into that instruction's ROB entry, where later instructions may still read it (via the same tag-forwarding as Tomasulo), but where it is officially "not real yet." Only when the instruction reaches the head of the ROB — meaning every older instruction has already committed — is its result written into the true architectural state. That final step is called commit or retire.

The ROB is a circular buffer

Physically the ROB is a ring of slots with two pointers. Newly issued instructions are appended at the tail (in program order); completed instructions are removed from the head (also in program order). Between the two pointers sit in-flight instructions in every state: some still executing, some finished-but-not-yet-committed. Because it's a ring, the pointers wrap around modulo the buffer size — no data ever moves, only the pointers advance. Each slot below is coloured by its state.

A circular buffer, in code

The ROB's mechanism is exactly the classic ring buffer: a fixed array with a head index, a tail index, and a count, all advancing modulo the capacity. Issue pushes at the tail; commit pops from the head. Run it and watch the indices wrap:

// A reorder buffer is a circular FIFO. Issue = enqueue at tail; commit = dequeue at head. class ReorderBuffer { private slots: (string | null)[]; private head = 0; // next to commit (in order) private tail = 0; // next free slot to issue into private count = 0; constructor(private capacity: number) { this.slots = new Array(capacity).fill(null); } issue(name: string): boolean { if (this.count === this.capacity) { console.log(` [stall] ROB full, cannot issue ${name}`); return false; } this.slots[this.tail] = name; this.tail = (this.tail + 1) % this.capacity; this.count++; console.log(` issue ${name} -> tail now ${this.tail}, count ${this.count}`); return true; } commit(): void { if (this.count === 0) { console.log(" [nothing to commit]"); return; } const name = this.slots[this.head]; this.slots[this.head] = null; this.head = (this.head + 1) % this.capacity; this.count--; console.log(` commit ${name} -> head now ${this.head}, count ${this.count}`); } } const rob = new ReorderBuffer(4); rob.issue("I1"); rob.issue("I2"); rob.issue("I3"); rob.commit(); // I1 retires in order rob.issue("I4"); rob.issue("I5"); // I5 wraps the tail around to slot 0 rob.commit(); rob.commit(); // I2, I3 retire — always in program order

How the ROB delivers precise exceptions

Now the payoff. Say instructions issue in order I_1, I_2, I_3, I_4, and I_4 (a fast add) finishes first while I_2 (a slow load) is still in flight. I_4's result sits in its ROB entry — visible to dependents via forwarding, but not committed. If I_2 now faults, the machine simply:

  1. lets everything older than I_2 (here I_1) commit normally;
  2. flushes every ROB entry from I_2 onward — I_3 and the already-computed I_4 are thrown away, because they never committed and so never touched architectural state;
  3. takes the exception at I_2 with a perfectly clean architectural state.

The out-of-order execution is completely invisible to the exception handler. This same flush machinery is exactly what makes branch speculation recoverable: a mispredicted branch is just "discard everything younger than the branch," the identical operation.

In the original ROB design, an instruction's result lives in its ROB entry while speculative and is copied into the architectural register file at commit — so a value can be read from two places depending on its age, and the commit step does real data movement. Modern high-end cores (Intel P6 onward, and every big core since) merged the two ideas with a physical register file: renaming already gave every result a physical register, so commit doesn't copy anything — it just updates a table saying "this physical register is now the architectural one," and frees the register the old value used. The ROB then holds only bookkeeping (which physical reg, is it done, did it fault), not the data itself. Same guarantee — in-order commit, precise state — with less copying.

Students sometimes fear that forcing in-order commit re-serialises everything and throws the speed away. It doesn't. The slow part — executing, waiting on memory and dependences — still happens fully out of order and overlapped. Commit is cheap: it just advances the head pointer and makes already-computed results official, several per cycle. As long as the oldest instruction eventually finishes, the whole train behind it retires in a quick burst. In-order commit costs you almost nothing in throughput and buys you precise exceptions and clean recovery — one of the great bargains in architecture.

Why every big core has one

The reorder buffer is the piece that makes aggressive out-of-order execution safe. It reconciles two things that seem incompatible: run instructions in any order for speed, yet present a strictly ordered, recoverable architectural state to the software. Its size is a headline design number — a big modern core keeps hundreds of instructions in flight in its ROB (Apple's cores famously have very large ROBs), because the more instructions you can hold, the further ahead you can look for independent work. And its flush-younger-entries mechanism is the universal "undo" button behind both exceptions and speculation.