The Reorder Buffer (ROB)

Tomasulo’s algorithm in Chapter 50 executes instructions in dataflow order and updates the architectural register file as results land on the common data bus. The register file updates happen in the order results arrive, which is generally out of program order. This causes two problems that the original 1967 design did not solve.

First, exceptions are not precise. When a long-running divide takes a divide-by-zero exception, the architectural register file may already reflect the writes of younger instructions that complete before the divide finishes. The exception handler sees a state that no sequential execution would have produced, making the handler unable to clean up correctly.

Second, branch mispredictions cannot be fully recovered. Tomasulo’s tagging eliminates WAR and WAW, but it does not provide a mechanism to undo the architectural register file updates that mispredicted instructions performed on their speculative path.

The reorder buffer is the structure that fixes both problems. It is an in-order FIFO that holds every in-flight instruction, and it gates the architectural state update behind in-order retirement. An instruction may execute and complete in any order, but its result becomes architectural only when the instruction reaches the ROB’s head, every older instruction has already retired, and no exception has been detected at or before this instruction.

This chapter develops the ROB from first principles. A later section explains the separation between speculative state and architectural state. A later section describes the ROB entry layout and the head/tail pointers. A later section walks through the retirement process. A later section develops precise exception handling. A later section covers branch misprediction recovery. A later section discusses ROB sizing tradeoffs and the IPC versus power curve.

01.Why Separate Speculative from Architectural State

The out-of-order machine has two distinct notions of state. The architectural state is what the program nominally produces, as if every instruction ran in strict program order. The speculative state is what the hardware has actually computed, with instructions reordered for dataflow efficiency. The two must agree at every observable boundary: exception delivery, system-call boundary, debugger snapshot, inter-processor synchronization.

Without the ROB, the machine’s only state is the architectural register file plus memory. Tomasulo updates the architectural register file in the order results arrive. A divide-by-zero exception in I5 of the chapter-50 trace example would deliver the exception at cycle 17, by which time I6 had already updated f6 at cycle 11. The handler sees f6 as updated, but the program expected to see f6’s old value (since I5 supposedly took the exception before I6 ran in program order).

The fix is to delay architectural state updates until retirement. The ROB provides the staging area. When I6 completes at cycle 11, its result lands in its physical register, and the ROB entry for I6 marks it complete. The architectural state is not yet updated. I6 sits in the ROB waiting for I3, I4, I5 to retire first. When I5 takes the divide-by-zero at cycle 17, its ROB entry is marked exception, and at retirement the pipeline detects the exception, flushes I6 and everything past I5, and the architectural state is exactly what the program expects.

The same principle handles branch mispredictions. When the branch resolves and disagrees with the prediction, the pipeline knows that every instruction past the branch’s ROB entry is on the wrong path. The ROB lets the pipeline identify those entries cleanly (every entry with a sequence number younger than the branch) and discard them as a group. The architectural state is untouched because none of the discarded instructions had retired.

02.ROB Entry Layout

Each ROB entry holds the bookkeeping needed to determine whether retirement can proceed and, if so, what update to apply to the architectural state. The table below lists the typical fields.

The ArchDst and PhysDst fields capture the renaming decision so retirement can update the retirement RAT. The PrevPhys field is the previous physical register that backed ArchDst before this instruction renamed it. PrevPhys is what returns to the free list at retirement. The PC field is needed to deliver precise exceptions: the handler is given the PC of the excepting instruction.

The ROB is implemented as a circular buffer in SRAM. The head pointer and tail pointer wrap modulo the buffer size. Figure 1 shows the layout.

The ROB is filled by the rename stage and drained by the retirement stage. The fill rate is the rename width and the drain rate is the retirement width, with retirement usually provisioned at least as wide as rename. When the fill rate exceeds the drain rate (the common case during a long-latency stall), the ROB fills up until it is full. When the ROB is full, the rename stage stalls, propagating back-pressure to fetch.

03.Retirement

Retirement is the act of moving an instruction from speculative state to architectural state. The retirement logic examines the entries at the head of the ROB and proceeds as follows.

1. Check the head entry. If Valid is zero, the ROB is empty, so no retirement happens this cycle.

2. If Valid is one, check Complete. If Complete is zero, the instruction has not yet finished execution, so retirement stalls this cycle.

3. If Complete is one, check Exception. If Exception is one, divert into the exception handler (a later section).

4. If no exception, perform the architectural update. The retirement RAT entry for ArchDst is updated to PhysDst. The previous physical PrevPhys is returned to the free list. For stores, the store buffer entry indexed by StoreId is committed to memory (allowed to drain to the cache). For branches, any prediction-tracking metadata is updated.

5. Advance the head pointer. The retired entry’s Valid is cleared.

6. If the design supports multi-instruction retirement (typically at least as wide as rename), repeat steps 1 through 5 for the next entry up to the retirement width. Multi-instruction retirement requires that all retired entries in the cycle be complete and exception-free.

The retirement width is typically equal to the rename width or up to 50 percent wider. Modern designs use widths of 4 to 8. The Intel Golden Cove core retires 6 instructions per cycle. The Apple M1 Firestorm retires 8 per cycle. The AMD Zen 4 retires 8 per cycle. The IPC limit of the pipeline is bounded above by the retirement width.

04.Precise Exceptions in Out-of-Order

A precise exception is one in which the architectural state at exception delivery is exactly what the program expects: every instruction before the excepting instruction has completed and updated state, and no instruction at or after the excepting instruction has updated state. The ISA requires precise exceptions for most user-visible faults (page faults, divide by zero, illegal instruction). The out-of-order machine must deliver them despite executing instructions out of program order.

Detection

Exceptions can be detected at several points along the pipeline. Illegal instructions are detected at decode. Page faults on loads and stores are detected at the TLB lookup, which happens during execute. Divide-by-zero is detected when the divider sees a zero divisor at the start of its multi-cycle execution. Floating-point overflows are detected at the end of the FP unit’s multi-cycle execution.

When an exception is detected, the functional unit broadcasts the result completion with the exception bit set. The ROB entry is updated: Complete is set to one, Exception is set to one, and ExcCode is set to the appropriate cause code. The physical register destination is still written (with whatever the unit produced, often zero or undefined), but its value will never be read by anything because retirement discards everything past the exception.

Delivery

Exception delivery happens at retirement. The retirement logic, when it encounters a ROB entry with Exception set to one, performs the following.

1. Flush every entry in the ROB newer than this entry. The flush includes the issue queue, the in-flight functional units, the store buffer entries for younger stores, and the load queue entries.

2. Return all physical registers allocated to flushed instructions to the free list. The previous physical mappings are restored to the RAT (using the PrevPhys field of each flushed ROB entry to walk back through the renames).

3. Compute the exception vector address from ExcCode and the privilege-level configuration.

4. Save the excepting PC, the cause code, and any fault-specific information (the faulting address for a page fault) into the privileged state registers as required by the ISA.

5. Redirect fetch to the exception vector.

6. Resume execution at the handler.

The state at handler entry is exactly the state that a sequential execution would have produced just before the excepting instruction. The handler can roll forward (by fixing the fault and retrying) or roll back (by treating the excepting instruction as the boundary) without any ambiguity. The hardware has made the architectural state match the program’s view.

05.Branch Misprediction Recovery

Branch misprediction recovery uses the same machinery as exception delivery, with two differences. First, the mispredicted branch itself is not discarded, only the instructions past it are. Second, the redirect target is the correct branch target rather than an exception vector.

The branch unit, on resolving a branch, compares the resolved outcome (taken or not taken, and if taken the target address) against the prediction recorded for that branch when it was issued. If the comparison agrees, the branch retires normally. If the comparison disagrees, the branch unit signals a misprediction to the ROB.

The ROB initiates recovery by performing the following.

1. Mark the mispredicted branch’s ROB entry as complete with a misprediction flag.

2. Flush every entry past the branch. This is identical to the exception flush except that the branch itself remains.

3. Restore the RAT either from a per-branch checkpoint (a later section) or by walking the ROB back from the misprediction point using the PrevPhys fields of each flushed entry.

4. Return the physical registers allocated to flushed instructions to the free list.

5. Redirect fetch to the correct branch target.

6. Resume.

The branch itself eventually retires from the head of the ROB once it becomes the oldest entry. The recovery does not have to wait for retirement to happen. The flush and redirect happen as soon as the misprediction is detected. The branch entry sits at its place in the ROB until older instructions retire ahead of it.

06.ROB Sizing and the IPC-Power Curve

The ROB’s capacity is one of the most consequential parameters of an out-of-order design. Larger ROBs allow more in-flight instructions, which means more memory latency tolerance and more dataflow parallelism. Smaller ROBs save power, reduce area, and shorten the critical paths through the rename and retirement stages.

IPC as a Function of ROB Capacity

Empirically, IPC grows sub-linearly with ROB capacity. Going from 32 to 64 entries typically buys 30 to 40 percent IPC improvement on SPEC integer. Going from 64 to 128 buys another 15 to 25 percent. Going from 128 to 256 buys 10 to 15 percent. Going from 256 to 512 buys roughly 6 percent on typical SPEC integer.

The diminishing return is a consequence of the memory-latency distribution. Most cache misses resolve from the L2 or L3 within 30 to 100 cycles, and a ROB of 100 to 150 entries can absorb those at the issue width. Beyond that, only the rare DRAM misses (300 to 500 cycles) benefit from deeper windows. Those misses are infrequent enough that the marginal IPC gain from a larger window shrinks.

The table below sketches the relationship on a typical 4-wide out-of-order core running SPEC integer.

The marginal IPC per entry drops by an order of magnitude across the table. The architect’s task is to find the point at which the marginal IPC gain no longer justifies the marginal area and power cost.

Power Scaling

The ROB’s static power scales linearly with the entry count, because each entry is an SRAM cell with leakage. The ROB’s dynamic power scales with the read and write activity, which scales with the rename and retirement width but not directly with the entry count.

The auxiliary structures, however, scale with ROB capacity in problematic ways. The physical register file must grow to feed the ROB ($P \geq A + \text{ROB capacity}$). The issue queue must grow proportionally to keep the average issue queue depth at a useful fraction. The load and store queues must grow proportionally. The branch checkpoint buffer must grow to cover the in-flight branches.

A ROB doubling thus doubles the physical register file, doubles the issue queue, doubles the load and store queues, and increases the checkpoint buffer. The aggregate power roughly doubles per doubling of ROB capacity, while the IPC gain decreases. The IPC per watt curve peaks at a finite ROB capacity.

Critical-Path Concerns

The ROB has two critical paths that limit clock frequency. The fill path writes new entries at the tail. Widening the rename increases the write-port count. The drain path reads and updates entries at the head. Widening retirement increases the read-port count and the exception-detection fan-out.

For deep ROBs (more than 200 entries), the entry-search path during recovery becomes significant. Walking the ROB to restore the RAT entry by entry can take dozens of cycles. Modern designs avoid this by using per-branch checkpoints (Chapter 51) so that the common-case recovery is one cycle.

07.Worked Examples

08.Exercises