The Reorder Buffer: In-Order Retirement After Out-of-Order Execution

What It Is and the Problem It Solves

Out-of-order execution wins performance by running each instruction as soon as its inputs are ready, ignoring program order. But this breaks two guarantees the ISA promises. First, precise exceptions: when instruction i faults, the architectural state must reflect all instructions before i completed and none after — even though a later instruction may have already computed its result. Second, misspeculation recovery: a mispredicted branch or bad load must be undone without corrupting registers or memory.

The reorder buffer solves both by adding a layer of indirection between completion (an execution unit produces a result) and retirement (that result updates architectural state). Every decoded instruction gets a ROB entry allocated in program order at the tail. Results flow in whenever they finish, out of order. Retirement drains the head of the buffer strictly in order, so architectural state only ever advances along the true sequential path. If the head instruction faulted, the machine flushes everything younger and reports a precise state — the exact point Smith and Pleszkun targeted in 1985.

How It Works, Step by Step

Each ROB entry holds: instruction type, destination register (or memory tag), the computed result or a pointer to its physical register, a done bit, and an exception field. A pipeline cycles through four phases:

1. Dispatch/allocate: after decode and rename, allocate a ROB entry at the tail in program order. If the ROB is full, dispatch stalls — this is a structural hazard.
2. Execute: reservation stations / the scheduler issue the instruction when operands are ready; functional units run in any order.
3. Writeback/complete: the result is broadcast on the common data bus, tags match waiting consumers, and the entry's done bit is set.
4. Retire/commit: each cycle, inspect the head. If done and no exception, copy its result to the architectural register file (or free the old physical register in a rename scheme), advance head, and free the entry. If it carries an exception, flush all younger entries, restore the rename map, and redirect fetch.

The core invariant: the ROB retires entries in exactly the order they were allocated, so architectural state mirrors sequential execution at every commit boundary.

Complexity and a Worked Step Trace

Let N be the ROB size. Allocation and retirement are O(1) amortized per instruction: advance a pointer, mark bits. The buffer uses O(N) space. Wide cores retire up to W (e.g. 6-8) contiguous done entries per cycle, still O(W) work. Head/tail arithmetic is modulo-N. The busy-waiting hazard is when the head is a not-yet-done long-latency op (e.g. an L3 miss): younger done instructions pile up and the ROB fills, stalling dispatch even if unrelated work exists.

Program:  I1: LOAD  R1,[X]   ; slow, cache miss
          I2: ADD   R2,R3,R4 ; fast
          I3: MUL   R5,R2,R6 ; needs I2

cycle  ROB (head..tail)         event
  1    [I1*]                    allocate I1
  2    [I1*][I2*]               allocate I2
  3    [I1*][I2 done][I3*]      I2 completes OOO; I1 still pending
  4    [I1*][I2 done][I3 done]  I3 completes; head I1 NOT done -> no retire
  ...  (stall: head blocks)
 20    [I1 done][I2 done][I3 done]  I1 returns
 21    retire I1, then I2, then I3   in program order

Note I2 and I3 finished at cycle 3-4 but could not update architectural state until I1 retired — that ordering is exactly what preserves precise state.

Real-System Usage

Every mainstream out-of-order CPU ships a ROB. Intel's Pentium Pro (1995) popularized it in x86 with a 40-entry buffer that also served as the rename storage (result-in-ROB style). Modern designs separate the ROB from a physical register file (PRF): the ROB tracks ordering and status while renamed results live in the PRF, freed at retirement. Sizes have ballooned — Skylake 224, Golden Cove 512, Apple's Firestorm around 630 entries — because a bigger ROB tolerates more memory latency by keeping more instructions in flight.

Arm Cortex-X, AMD Zen, IBM POWER, and RISC-V cores like SiFive's and Ventana's all use ROBs. The concept generalizes: the ROB is where register reclamation, store buffer commit (stores become visible to memory only at retirement), branch misprediction rollback, and precise floating-point/page-fault exceptions are all sequenced. It is effectively the commit point that defines a core's architectural timeline.

How It Compares to the Alternatives

Smith and Pleszkun evaluated several schemes. The in-order completion approach forbids out-of-order finishing entirely — trivially precise, but it throws away the ILP that makes OoO worthwhile. A history buffer lets instructions write architectural registers immediately but logs old values so an exception can roll them back; it commits fast but pays on the recovery path and complicates the register file. A future file keeps a speculative register file plus an architectural one reconciled by a ROB.

The reorder buffer's tradeoff is the winner in practice: it centralizes ordering in one FIFO, makes the common case (no exception) cheap, and makes recovery a clean flush. Versus pure Tomasulo's algorithm (1967), which achieves OoO execution and renaming via reservation stations but has no mechanism for precise state, the ROB is the missing piece — modern cores combine Tomasulo-style dynamic scheduling with a ROB. The cost is chip area and the head-of-line blocking hazard, which motivates research into checkpoint-based and out-of-order retirement schemes.

Pitfalls and Significance

The dominant pitfall is head-of-line blocking: a long-latency miss at the ROB head stalls retirement, the buffer fills, dispatch halts, and the whole window drains of useful throughput. This is why ROB capacity, load/store queue sizes, and MSHRs must scale together — an oversized ROB with a tiny store queue just stalls elsewhere. A second subtlety is memory ordering: stores must not become globally visible before retirement, or a squashed speculative store would corrupt shared memory; the store buffer commits only on retire. Speculative loads that were mis-ordered relative to an older store trigger a memory-order machine clear — an expensive full flush.

The ROB's significance is foundational: it is the mechanism that lets a processor lie convincingly. Software sees a simple sequential machine with precise faults and clean rollback, while underneath hundreds of instructions reorder freely. It also underpins security-relevant behavior — speculative work that never retires is architecturally invisible, yet its microarchitectural side effects enabled the Spectre and Meltdown class of attacks, making the completion-versus-retirement boundary a security frontier, not just a performance one.

ROB capacity in representative out-of-order CPU cores

Microarchitecture	ROB entries	Notes
Intel Pentium Pro (1995)	40	First mainstream ROB-based x86 core
Intel Skylake (2015)	224	Unified scheduler, separate PRF
Intel Golden Cove (2021)	512	Alder Lake P-core
Apple Firestorm (2020, A14/M1)	~630	Very wide 8-wide decode design
AMD Zen 4 (2022)	320	Retire up to ~8-wide per cycle