Only about fifteen IBM System/360 Model 91s were built. The first went to NASA's Goddard Space Flight Center in October 1967, where at 16.6 MIPS it was the most powerful computer in user operation. It ran Tomasulo's algorithm — and it had imprecise exceptions and out-of-order memory stores, the two problems the reorder buffer later fixed. The hook's 512-entry buffer is the same algorithm with a window 64 times wider than the Model 91's eight instructions.
Guess now, pay later: speculation, precise exceptions and the reorder buffer
After this lesson you will fill a reorder-buffer entry and a rename table snapshot by snapshot, say which entries a mispredicted branch tears off, and explain why the register file is written only at commit.
Robert Tomasulo's 1967 paper describes hardware that looks ahead about eight instructions. Intel's Golden Cove core of 2021 keeps 512 in flight. Most of those 512 sit behind a branch nobody has evaluated yet — about one instruction in five is a branch — so the core guesses the outcome, runs ahead, and is wrong now and then. Yet it never leaves a wrong value in a register, and a divide by zero three instructions back never leaves a half-finished mess behind it.
The trick is a queue with two pointers that delays the one step which cannot be undone. In the notes' own example an instruction computes the value 10 in cycle 4, and the register F0 becomes 10 only in cycle 5. Keep that puzzle in mind: why would a machine built for speed wait a whole cycle to write a number it already has?
One more number before you start. In April 2026, 57 students took the professor's second self-assessment test — ILP, dynamic scheduling, reorder buffer — and averaged 5.9 out of 10. This lesson is where those points are.
Guess now: speculation, and the one step that cannot be undone
Take the loop of the notes' February 2025 reorder-buffer exercise (lesson 18 fills its table). Registers are written as the 2026 paper writes them, without the dollar sign; older papers write $F2.
LOOP: LD F2, 0(R1)
FADD F4, F2, F2
SD F4, 0(R1)
ADDUI R1, R1, 4
BNE R1, R2, LOOP ; pred. takenThe fetch unit reaches BNE at the end of the first iteration. It does not know whether R1 equals R2 — the ADDUI before it may not even have executed. A branch predictor (lesson 5) says "taken", and fetch continues at LOOP: the second iteration's LD, FADD and SD enter the machine while the first BNE is still a question mark. Figure 1 shows the stream: everything below the branch is a guess until the branch resolves.
On the classic Tomasulo machine of lesson 11 those guessed instructions would issue, execute and, at Write Result, put their results on the common data bus — which writes them straight into the register file. Suppose the guess was wrong and the loop was over. Now F2 and F4 hold values the program never asked for, and the SD may have written memory. Nobody kept the old values; there is nothing to roll back to. That is why a Tomasulo machine with a predictor may fetch down the predicted path but must not let those instructions change the state before the branch resolves — and waiting for every branch throws away most of the parallelism the predictor was supposed to buy.
Hardware-based speculation — executing instructions before it is known whether they are needed (they are control-dependent on an unresolved branch), with the ability to undo their effects if the prediction turns out wrong. Hennessy & Patterson make it three ideas: dynamic branch prediction to choose the path, speculation to execute along it before the branch resolves, and dynamic scheduling to overlap instructions from several basic blocks.
The problem it creates is in the notes' own words (p. 222): "how do we prevent side effects (e.g., register or memory updates) from mispredicted instructions?". The answer: defer the architectural state update until it is safe to commit. The architectural state is what the program can see — the register file and memory. Everything else, reservation stations, buses and the buffer below, is scaffolding that can be thrown away.
Reorder buffer (ROB) — a buffer that holds the results of instructions that have finished execution but are not yet committed. It lets results be written to the register file and memory in program order, and it lets the processor discard the results of a mispredicted path before they get there.
The notes list what the ROB is critical for (p. 222): decoupling execution completion from the state update, which they call commit; supporting precise exceptions, so the CPU can stop cleanly at the last correct instruction; and tracking which instructions are speculative and which are not. Hennessy & Patterson put it in one sentence: the bypassing of results among instructions, which speculative execution needs, must be separated from the actual completion of an instruction. Bypassing happens on the bus, as before. Completion — the write that counts — happens later, at a gate.
Completed is not committed: a result exists the moment the unit produces it; it becomes part of the program's state only when its instruction reaches the head of the reorder buffer.
Why go to this trouble? Here is the chain an examiner expects you to reproduce. Branches are frequent, so waiting for each one serialises the stream and wastes most of the available ILP. So predict and keep going. Some of that work is wrong. So it may compute, but it must not commit. So you need a place to park completed results and a rule to release them in order. The place is the ROB; the rule is in-order commit at the head. The cost sits next to the benefit: every misprediction wastes the work fetched down the wrong path (roughly the misprediction rate times the number of instructions behind the branch), recovery takes cycles, and the buffer is hardware — entries, ports, comparators and a copy of every result into the register file at commit.
Pay later: out of order, in order, and the fault that waits its turn
Out-of-order execution (lesson 8, lesson 9, lesson 11) exists because dependences and delays stop some instructions from executing now: a RAW hazard, a load that misses in the cache. Letting independent instructions bypass the stalled one keeps the functional units busy. The notes' example (p. 223): while an instruction waits for a memory load, an ALU operation behind it executes. The risk comes with it. Instructions complete in a different order from the program, which breaks the precise exception model; and the instructions behind a predicted branch may simply be wrong. The fix the notes state (p. 223): instructions must commit — retire — in order, exactly as they appear in the program. Execution out of order, commit in order, and the ROB bridges the two.
What the ROB does in each phase (pp. 223–224). At issue it allocates an entry, which marks the instruction's place in program order. During execution it stores the result as soon as the instruction finishes. At commit the instruction updates the architectural registers or memory only if three things hold:
- it is at the head of the ROB;
- its execution has completed;
- it is not speculative.
With these, the state is updated in program order only; speculative results stay in the buffer until validated; and a speculated instruction can be undone — its entry is simply dropped. The notes' summary (p. 224): the ROB lets the processor execute instructions as soon as their operands are ready, regardless of program order, while ensuring they commit their results in order.
Precise exceptions, by construction
Lesson 7 introduced the problem: once units complete out of order, a younger instruction may already have written its register when an older one faults — the exception is imprecise and the program cannot be restarted. The notes now define the goal (p. 224). An exception is precise if the processor can stop at a well-defined point corresponding to a specific instruction, all previous instructions are fully committed, and no subsequent instruction has modified the architectural state. Then the operating system or the handler can identify the error and resume the program.
The ROB delivers all three (p. 224): results go to the ROB, not to the register file or memory; only the head commits, in order; on an exception or a misprediction the entries after the faulting instruction are flushed and execution restarts from the faulting instruction or from the handler. The rollback is clean because the architectural state was never touched beyond the last committed instruction. One detail the notes leave out, from Hennessy & Patterson: the exception is recorded in the entry of the faulting instruction and is taken only when that instruction reaches the head. At that moment everything older is committed and everything younger is still in the buffer — the three conditions hold by construction. And an instruction on a mispredicted path that faults never reaches the head: it is flushed together with its entry, exception included. A speculative exception never happens.
The notes' Example 11 (p. 225) is the case to watch: four instructions, the third divides by zero, the fourth is independent and finishes early, writing R5. In the papers' mnemonics:
I1: LD F2, 0(R1)
I2: FADD F4, F2, F2
I3: FDIV F6, F4, F0 ; F0 = 0: fault
I4: ADDUI R5, R5, 8 ; independentA word about condition 3. In the course's tables an entry carries an explicit Speculative flag. In Hennessy & Patterson's model there is no flag: a branch commits only after it has resolved, so by the time an instruction reaches the head every older branch has committed and the instruction is no longer speculative by construction. The two views agree; the flag just makes the flush set visible on paper. Real processors do not even wait for the branch to reach the head: they recover as soon as it resolves, clearing the younger entries and restarting fetch — the notes' Example 13 does this silently.
The notes sum up the ROB's functional roles (p. 225): result buffering — results of instructions that have completed but not committed; speculative result propagation — results pass among instructions issued after a predicted branch, through the ROB and the bus, without touching the architectural registers; precise interrupt support — only committed instructions affect the state, and a flush rolls back a misprediction or an exception. The closing line is worth keeping: the ROB "is not merely a commit buffer, it is also a speculation-aware result forwarding structure, enabling safe communication among instructions that may never actually commit."
The machine: Figure 27 and the six fields of an entry
Figure 27 of the notes (p. 228) is Hennessy & Patterson's Figure 3.11: the floating-point unit of lesson 11 extended to handle speculation. Put the two side by side and three things have moved.
Before: classic Tomasulo
After: Tomasulo with a reorder buffer
Walk the components (pp. 228–230). The instruction queue holds fetched instructions and supplies each one to a reservation station and to the ROB in parallel. The reservation stations are temporary buffers between issue and execution — three for the adders, two for the multipliers in the figure — holding the instruction with operand values or ROB tags. The FP units receive an instruction when its operands are ready. The CDB broadcasts result values with their ROB tag; all waiting instructions and all ROB entries listen. The ROB is central: it takes over the tag namespace and the store buffers. The load buffers and the address unit stay: a load still gets a buffer at issue, the address unit computes base plus offset, and — step 3 of the notes' four — the load may access memory early only if no earlier store has an unresolved or equal address; otherwise it waits until memory disambiguation clears it. That is a RAW hazard through memory. A store, on the other hand, keeps its address and its data in its ROB entry and writes memory at commit, in order: WAW and WAR hazards through memory disappear, and since a store can never be undone it had to wait for commit anyway — which is why the store buffer could go. Finally the register file: not updated after execution, updated only when instructions commit through the ROB. In the figure the "Reg #" and "Data" arrows come from the buffer, and the CDB no longer reaches the registers.
The six fields of an entry
Each entry holds (p. 229): Busy — the entry is active or free; Instruction type — branch (no result), store (the destination is a memory address), load or ALU (the destination is a register); Destination — the register number, or the memory address for a store; Value — the result after execution, kept until commit; Ready — set when execution has completed and the result is valid; Speculative — whether the instruction was issued after an unresolved branch. The exam's table (February 2025) keeps the same information under its own headings and adds one column, Res. Alloc.: the reservation station or load buffer the instruction occupies. Figure 4 shows the mapping.
Conventions for the paper's columns, which lesson 18 drills: Res. Alloc. is Load1 … for loads, FP1 … for floating-point operations, Int1 … for integer operations and branches (a branch evaluates its condition on an integer unit), and "–" for a store — the ROB machine has no store buffer, the address and data live in the entry. A station is busy from issue to Write Result. Ready/Status is written "No, issued", "No, exec.(*)" for an instruction stuck in execution — the asterisk marks the cache miss the exercise announces — or "Yes". Dest. is the register, or "Mem" with the address for a store. A free entry is simply an empty row. Here is Example 12 in that format.
| ROB# | Instruction | Dest. | Res. Alloc. | Ready/Status | Value | Spec. |
|---|---|---|---|---|---|---|
| ROB0 | In: LD F0, 0(R1) | F0 | Load1 | No, exec. | – | No |
| ROB1 | – | – | – | – | – | – |
| ROB2 | – | – | – | – | – | – |
| ROB3 | – | – | – | – | – | – |
Two of the fields are control bits with a life of their own (p. 230). The Ready bit is set when the instruction finishes execution and the result is written into the ROB; it tells dependents that the value can be read — from the bus or directly from the entry — and it enables commit: no commit without Ready. The Speculative flag is set at issue when the instruction follows an unresolved branch and cleared when the branch resolves as predicted; its purpose is that speculative instructions never update the state, and that all of them can be flushed on a misprediction or an exception. The notes' summary of the design (p. 230): the ROB replaces the store buffers, so memory writes wait for commit; renaming moves from the reservation stations to the ROB; precise exceptions and speculation are both served by tracking and flushing; the CDB stays critical for forwarding and readiness detection.
"The ROB replaces the register renaming logic" (p. 229). Overstated: the register status table of lesson 11 still exists — it now holds ROB numbers, and the exam calls it the Rename Table. What the ROB replaces is the station-based tag namespace and the store buffers.
Two pointers and a ring: head, tail, the rename table, and the notes' Example 13
The ROB is a circular buffer — a circular FIFO queue — run by two pointers (p. 231). The head points to the oldest instruction, the next to commit; it advances at commit. The tail points to the next free entry, where the next issued instruction goes; it advances at issue. Why two pointers and a ring (pp. 231–232)? Insertion at the tail preserves program order at issue. Retirement from the head makes commit in order. When a pointer reaches the end of the buffer it wraps around to 0, so entries never move: no data shifting, less silicon. And full and empty are told apart with the two pointers and one busy bit:
Full: head = tail and the entry is busy — issue stalls
Empty: head = tail and the entry is free — nothing to commit
In symbols, with \(N\) entries, head \(h\), tail \(t\) and the busy bit \(b[h]\) of the entry at the head (the full / empty rule is the notes'; the modular arithmetic is background):
\[ \text{full} \iff h = t \wedge b[h] \]
\[ \text{empty} \iff h = t \wedge \neg b[h] \]
\[ \text{issue: } t \leftarrow (t + 1) \bmod N \]
\[ \text{commit: } h \leftarrow (h + 1) \bmod N \]
- \(h\), \(t\)
- head and tail pointers, as entry numbers
- \(b[h]\)
- busy bit of the entry the head points at
- \(N\)
- number of entries of the buffer
Full is the costly state. The head blocks everything behind it: if the oldest instruction waits on a cache miss, finished instructions behind it cannot commit, their entries do not free, and when the tail meets the head issue stops — the whole window is exhausted. Nothing commits out of order to make room, ever. That is the price of the design, and it is why the size of the buffer matters.
Why do modern cores need hundreds of entries?
Background, not in the notes. To sustain a throughput of IPC instructions per cycle while each instruction stays in the buffer for T cycles from issue to commit, the buffer must hold about IPC × T entries (Little's law). A cache miss of a hundred cycles at the head, on a core that issues four instructions per cycle, needs hundreds of entries behind it — or issue stalls long before the miss is served.
The rename table
The rename table (p. 232) is a small hardware table that records where the most recent value of each register will come from while its producer is still in flight: it maps F0, F2, … to the ROB entry producing their new value. It is lesson 11's register status table with ROB numbers instead of station names, and the exam calls it the Rename Table. A writer issues: its destination is mapped to its new ROB number. A reader issues: it checks the table — mapped, so read the value from the ROB, or take the tag if the entry is not ready; not mapped, so read the register file. Two rules the notes leave implicit. At commit the mapping is cleared only if it still points to the committing entry: a younger writer may have re-mapped the register, and that mapping must stay. At a flush every mapping that points to a flushed entry goes back to the older in-flight producer of that register, or to "–" if there is none; real cores keep a checkpoint of the table at each branch for exactly this.
The rename table holds names, never values: a ROB number or nothing. The values live in the entries and, after commit, in the register file.
Example 13, corrected: eight cycles, two commits, one flush
The notes' Example 13 (pp. 232–237) runs five instructions, In to In+4, through a four-entry ROB. Two things need fixing before it can be followed: there is no branch in the buffer although In+3 and In+4 are called speculative, and the rename table ends up holding values (both red pens are below). Here In+2 is the branch, and every instruction gets a mnemonic so that the paper's columns can be filled; the machine is the one of February 2025 — four load buffers, four FP reservation stations, two integer ones. The notes' numbers — 10, 20, the cycle of each event, the pointers — are unchanged. The notes count snapshots as cycles and issue two instructions in "cycle 1": read the cycles as snapshots, not as a timing table.
In: LD F0, 0(R1) ; Load1, value 10
In+1: FADD F2, F0, F0 ; FP1, RAW F0, 20
In+2: BNE R1, R2, NEXT ; Int1, pred. taken
In+3: FMUL F6, F2, F2 ; FP2, spec
In+4: FADD F8, F6, F2 ; FP3, specCycle 1. In and In+1 issue. Head ROB0, tail ROB2. F0 and F2 are renamed: whoever reads them now looks at ROB0 and ROB1, not at the register file. In+1 received the tag ROB0 for F0.
ROB# Instruction Dest. Res. Alloc. Ready/Status Value Spec. ROB0 In: LD F0, 0(R1) F0 Load1 No, exec. – No ROB1 In+1: FADD F2, F0, F0 F2 FP1 No, issued – No ROB2 – – – – – – ROB3 – – – – – – Reg # F0 F2 F4 F6 F8 ROB # ROB0 ROB1 – – – Cycle 2. The branch In+2 issues into ROB2 and takes Int1. It has no destination, so the rename table does not change; it is not speculative itself — it is the unresolved branch. Tail ROB3.
ROB# Instruction Dest. Res. Alloc. Ready/Status Value Spec. ROB0 In: LD F0, 0(R1) F0 Load1 No, exec. – No ROB1 In+1: FADD F2, F0, F0 F2 FP1 No, issued – No ROB2 In+2: BNE R1, R2, NEXT – Int1 No, issued – No ROB3 – – – – – – Reg # F0 F2 F4 F6 F8 ROB # ROB0 ROB1 – – – Cycle 3. In+3 issues into ROB3 with Spec = Yes: an older branch is unresolved. All four entries are busy, so the tail meets the head at ROB0 and the entry is busy — the ROB is full. Nothing more can issue until In commits.
ROB# Instruction Dest. Res. Alloc. Ready/Status Value Spec. ROB0 In: LD F0, 0(R1) F0 Load1 No, exec. – No ROB1 In+1: FADD F2, F0, F0 F2 FP1 No, issued – No ROB2 In+2: BNE R1, R2, NEXT – Int1 No, issued – No ROB3 In+3: FMUL F6, F2, F2 F6 FP2 No, issued – Yes Reg # F0 F2 F4 F6 F8 ROB # ROB0 ROB1 – ROB3 – Cycle 4. In completes: the CDB carries (ROB0, 10), ROB0 becomes Ready with Value 10, Load1 is freed, and In+1's station captures the 10. The register file still holds the old F0, and the rename table still says F0 → ROB0: the value is in the ROB, not in the register.
ROB# Instruction Dest. Res. Alloc. Ready/Status Value Spec. ROB0 In: LD F0, 0(R1) F0 – Yes 10 No ROB1 In+1: FADD F2, F0, F0 F2 FP1 No, exec. – No ROB2 In+2: BNE R1, R2, NEXT – Int1 No, issued – No ROB3 In+3: FMUL F6, F2, F2 F6 FP2 No, issued – Yes Reg # F0 F2 F4 F6 F8 ROB # ROB0 ROB1 – ROB3 – Cycle 5. In commits: it is at the head, Ready, not speculative. The register file gets F0 = 10, ROB0 is freed, the head moves to ROB1 and the tail finally finds a free entry at ROB0. The rename entry of F0 is cleared — it pointed to the committing entry — and reads "–", as the paper writes it.
ROB# Instruction Dest. Res. Alloc. Ready/Status Value Spec. ROB0 – – – – – – ROB1 In+1: FADD F2, F0, F0 F2 FP1 No, exec. – No ROB2 In+2: BNE R1, R2, NEXT – Int1 No, issued – No ROB3 In+3: FMUL F6, F2, F2 F6 FP2 No, issued – Yes Reg # F0 F2 F4 F6 F8 ROB # – ROB1 – ROB3 – Cycle 6. In+4 issues into the freed ROB0 — the ring has wrapped — with Spec = Yes and the station FP3 (FP1 is still busy until In+1 writes its result). In+1 completes with 20 = 10 + 10; In+3 and In+4 capture the 20 from the bus. Full again: head = tail = ROB1, busy.
ROB# Instruction Dest. Res. Alloc. Ready/Status Value Spec. ROB0 In+4: FADD F8, F6, F2 F8 FP3 No, issued – Yes ROB1 In+1: FADD F2, F0, F0 F2 – Yes 20 No ROB2 In+2: BNE R1, R2, NEXT – Int1 No, issued – No ROB3 In+3: FMUL F6, F2, F2 F6 FP2 No, exec. – Yes Reg # F0 F2 F4 F6 F8 ROB # – ROB1 – ROB3 ROB0 Cycle 7. In+1 commits: F2 = 20 in the register file, ROB1 freed, head ROB2, tail ROB1, F2 → "–". The head is now the branch. ROB0 and ROB3 are speculative and still executing; they can neither commit nor be trusted.
ROB# Instruction Dest. Res. Alloc. Ready/Status Value Spec. ROB0 In+4: FADD F8, F6, F2 F8 FP3 No, issued – Yes ROB1 – – – – – – ROB2 In+2: BNE R1, R2, NEXT – Int1 No, issued – No ROB3 In+3: FMUL F6, F2, F2 F6 FP2 No, exec. – Yes Reg # F0 F2 F4 F6 F8 ROB # – – – ROB3 ROB0 Cycle 8, before the flush. The branch executes: R1 equals R2 after all, the prediction "taken" was wrong. ROB2 becomes Ready (resolved) and the mispredict is detected. Everything issued after it — ROB3, then ROB0 — is on the wrong path.
ROB# Instruction Dest. Res. Alloc. Ready/Status Value Spec. ROB0 In+4: FADD F8, F6, F2 F8 FP3 No, issued – Yes ROB1 – – – – – – ROB2 In+2: BNE R1, R2, NEXT – – Yes (mispredicted) – No ROB3 In+3: FMUL F6, F2, F2 F6 FP2 No, exec. – Yes Reg # F0 F2 F4 F6 F8 ROB # – – – ROB3 ROB0 Cycle 8, after the flush. ROB3 and ROB0 are freed and FP2, FP3 released; the tail moves back to ROB3, the entry after the last surviving instruction; F6 and F8 lose their mappings — no older producer of F6 or F8 is in flight, so they read "–"; fetch restarts at the fall-through instruction. The register file was never touched: F0 = 10 and F2 = 20 are exactly the state after In+1.
ROB# Instruction Dest. Res. Alloc. Ready/Status Value Spec. ROB0 – – – – – – ROB1 – – – – – – ROB2 In+2: BNE R1, R2, NEXT – – Yes – No ROB3 – – – – – – Reg # F0 F2 F4 F6 F8 ROB # – – – – – Cycle 9, one step beyond the notes. The branch commits: a resolved branch retires with no change of state. Head ROB3, tail ROB3, entry not busy — the ROB is empty, and the next instruction of the correct path will issue into ROB3 with Spec = No.
ROB# Instruction Dest. Res. Alloc. Ready/Status Value Spec. ROB0 – – – – – – ROB1 – – – – – – ROB2 – – – – – – ROB3 – – – – – – Reg # F0 F2 F4 F6 F8 ROB # – – – – –
Now the warm-up puzzle. In computes 10 in cycle 4 and F0 becomes 10 in cycle 5. The machine does not wait because it doubts the value; it waits because every result goes through the same gate — the head, in program order. For In the gate costs one cycle and buys nothing visible. For In+3 the same gate is what makes cycle 8 possible: its entry is torn off and F6 never changed. For a faulting instruction it is what makes the exception precise. The price is a delay of the architectural write, never of execution — dependents got the 10 from the bus in cycle 4 — and what it buys is undo. That rule, not the ring or the flag, is the reorder buffer.
Exam-style questions
Explain the main concepts and benefits of each one of the following techniques used by modern superscalar processors (Tomasulo-style), in about five lines each: (2) dynamic branch prediction and speculative execution; (5) dynamic register renaming; (6) out-of-order execution; (7) reorder buffer.
Show model answer
Dynamic branch prediction and speculative execution. The outcome and target of a branch are predicted at fetch from run-time history (BHT, BTB). The instructions after the branch are fetched, issued and executed before the branch resolves; their results are forwarded among them through the CDB and the ROB but kept out of the architectural state until the branch is resolved and the instruction commits. On a misprediction the younger entries of the ROB are flushed and fetch restarts at the correct target. Benefit: branches no longer drain the pipeline, and the window of exploitable ILP spans several basic blocks. Cost: wasted work and recovery time on mispredictions, so accuracy matters.
Dynamic register renaming. Each issued instruction that writes a register gets a fresh name for its result — a reservation station in classic Tomasulo, a ROB entry in the speculative version; the rename table maps the architectural register to its newest producer, and a consumer issuing later takes that producer's value or its tag. Benefit: WAR and WAW (name) hazards disappear, so instructions and loop iterations can be overlapped freely and only true (RAW) dependences remain. Cost: a rename table to keep, to restore after a misprediction, and the copy of each value into the architectural register at commit.
Out-of-order execution. Instructions wait in reservation stations and start as soon as their own operands are ready, independently of program order; results are broadcast on the CDB. Issue and commit remain in order. Benefit: a stalled instruction — a cache miss, a long-latency FP operation — does not block independent later ones; functional units stay busy and CPI drops. It requires renaming against WAR/WAW hazards and in-order commit to keep exceptions precise.
Reorder buffer. A circular FIFO: an entry is allocated at issue in program order, written out of order at Write Result (value, ready bit) and drained in order at Commit from the head (head, ready, not speculative). It supplies operands between completion and commit, provides the names for renaming (the ROB number is the tag) and replaces the store buffers, keeping a store's address and data until commit. Benefits: precise exceptions, since nothing younger than a faulting instruction has touched the state; cheap misprediction recovery by discarding the entries after the branch; speculation made safe. Cost: a finite window — a stalled head stops issue when the buffer fills.
Four of the eight sub-points of the June 2026 open question. The examiner looks for the "what it buys" line in each one and for the pairing cost / benefit; "the ROB makes the processor faster" alone earns nothing — it makes speculation safe, and the speed comes from executing past unresolved branches.
What is a precise exception (give the three conditions)? Explain how the reorder buffer guarantees precise exceptions in an out-of-order processor, and what happens if an instruction on a mispredicted path raises an exception.
Show model answer
An exception is precise if (1) the processor can stop at a well-defined point corresponding to a specific instruction, (2) all previous instructions are fully committed, and (3) no subsequent instruction has modified the architectural state. With a reorder buffer, results are written to the ROB entry at Write Result, never directly to the register file or memory; only the head commits, in program order. An exception is recorded in the entry of the faulting instruction and taken when that instruction reaches the head: at that moment every older instruction has committed and every younger one is still in the buffer, so the younger entries are discarded and fetch restarts at the handler — the three conditions hold by construction. An exception raised on a mispredicted path never reaches the head: when the branch resolves, the entries after it are flushed together with the recorded exception, so it is never taken.
Give the three conditions as a list and then map each one to a property of the buffer (results parked, in-order commit at the head, flush of the younger entries). The last sentence — a speculative exception is simply discarded — is the part most answers miss.
(Single answer.) In the speculative Tomasulo algorithm, when is the architectural register file updated?
Show model answer
The third option: at Commit. The register file must reflect only instructions that are certainly part of the program's path; at Write Result the value goes to the ROB entry and to the waiting reservation stations.
Keep the contrast straight: in classic Tomasulo the register file is written at Write Result (Table 21's "commit on write-back"); with the ROB only at Commit. In neither design does the value wait inside the reservation station — the red pen on Table 21 above.
(Multiple answers.) Which of the following statements about the reorder buffer are true?
Show model answer
True: 1, 3, 5, 6. False: 2 (the station is freed at Write Result, the ROB entry at Commit) and 4 (the tail points to the next free entry).
The two false statements are the two confusions the lesson warns against most: which structure is freed when, and what the tail points to.
(Single answer.) In the Speculative Tomasulo Architecture, what type of hardware block is used to undo speculative instructions in case of a mispredicted branch? Motivate your answer by explaining what happens in the case of a mispredicted branch.
Show model answer
The Reorder Buffer. A speculative instruction's result is held only in its ROB entry (and in copies inside reservation stations), never in the register file or memory, and the entry is marked speculative. When the branch resolves as mispredicted: all ROB entries younger than the branch are invalidated and the tail is moved back to the entry after the branch; the reservation stations and load buffers working for them are squashed; the rename table is restored to the mapping valid at the branch, so that each register points to its older in-flight producer or to nothing; fetch is redirected to the correct target; the branch itself commits normally. Nothing has to be undone in the architectural state, because nothing speculative ever reached it.
The quiz of the February 2025 paper, as reproduced in the notes (p. 582). The motivation is worth the extra point: name the four actions (invalidate the younger entries, squash their stations, restore the rename table, redirect fetch) and the reason nothing in the registers needs undoing.
Consider the following instruction sequence executed on a speculative Tomasulo architecture with a 4-entry ROB, 4 load buffers (Load1–Load4), 4 FP reservation stations (FP1–FP4) and 2 integer reservation stations (Int1–Int2). The BNE is predicted taken. Complete the ROB table and the Rename Table (a) when the ROB becomes full, (b) after In has committed, (c) after the BNE has been found mispredicted and the ROB has been flushed.
In: LD F0, 0(R1)
In+1: FADD F2, F0, F0
In+2: BNE R1, R2, NEXT
In+3: FMUL F6, F2, F2
In+4: FADD F8, F6, F2Show model answer
(a) The ROB is full after four issues: head = tail = ROB0 and the entry is busy. In+3 is speculative because the BNE in ROB2 is unresolved; the BNE itself is not.
| ROB# | Instruction | Dest. | Res. Alloc. | Ready/Status | Spec. |
|---|---|---|---|---|---|
| ROB0 | In: LD F0, 0(R1) | F0 | Load1 | No, exec. | No |
| ROB1 | In+1: FADD F2, F0, F0 | F2 | FP1 | No, issued | No |
| ROB2 | In+2: BNE R1, R2, NEXT | – | Int1 | No, issued | No |
| ROB3 | In+3: FMUL F6, F2, F2 | F6 | FP2 | No, issued | Yes |
| Reg # | F0 | F2 | F4 | F6 | F8 |
|---|---|---|---|---|---|
| ROB # | ROB0 | ROB1 | – | ROB3 | – |
(b) In completes (Ready = Yes, value 10 in ROB0, Load1 released) and commits from the head: F0 = 10 in the register file, ROB0 freed, head ROB1, tail ROB0, and the mapping of F0 cleared. In+1 has captured F0 from the CDB and is executing.
| ROB# | Instruction | Dest. | Res. Alloc. | Ready/Status | Spec. |
|---|---|---|---|---|---|
| ROB0 | – | – | – | – | – |
| ROB1 | In+1: FADD F2, F0, F0 | F2 | FP1 | No, exec. | No |
| ROB2 | In+2: BNE R1, R2, NEXT | – | Int1 | No, issued | No |
| ROB3 | In+3: FMUL F6, F2, F2 | F6 | FP2 | No, issued | Yes |
| Reg # | F0 | F2 | F4 | F6 | F8 |
|---|---|---|---|---|---|
| ROB # | – | ROB1 | – | ROB3 | – |
(c) In+4 has meanwhile issued into ROB0 (FP3, speculative) and In+1 has committed (F2 = 20, head ROB2, tail ROB1). The BNE resolves as mispredicted: ROB3 and ROB0 are flushed, FP2 and FP3 released, the tail moves to ROB3, the mappings of F6 and F8 are cleared (no older producer is in flight), fetch restarts at the fall-through instruction. The branch is Ready at the head and commits next; the register file holds F0 = 10, F2 = 20 and was never touched by the flushed instructions.
| ROB# | Instruction | Dest. | Res. Alloc. | Ready/Status | Spec. |
|---|---|---|---|---|---|
| ROB0 | – | – | – | – | – |
| ROB1 | – | – | – | – | – |
| ROB2 | In+2: BNE R1, R2, NEXT | – | – | Yes | No |
| ROB3 | – | – | – | – | – |
| Reg # | F0 | F2 | F4 | F6 | F8 |
|---|---|---|---|---|---|
| ROB # | – | – | – | – | – |
The three snapshots are cycles 3, 5 and 8 of the corrected Example 13. Marks go to: the Spec column (Yes only behind the branch, No for the branch itself), the Res. Alloc. names and their release at Write Result, the head and tail positions in each snapshot, and the rename table — "–" after a commit, and after the flush "–" only because no older producer of F6 or F8 is still in flight.
Check yourself
In sits in ROB0 with Ready = Yes and Value = 10; the head is at ROB0, nothing has committed yet. In this cycle a new instruction that reads F0 issues. Where does it get F0 from?
You see head = tail = ROB5. Is the ROB full or empty?
Renaming registers to ROB entries removes which hazards?
Same answer as for classic Tomasulo — only the namespace of the tags changed.
The tail pointer of the reorder buffer points to…
F0 is mapped to ROB5, a speculative entry that is flushed; an older entry ROB0, which also writes F0, is still in flight. What should the rename table say for F0 after the recovery?
An instruction on a mispredicted path divides by zero before the branch resolves. What happens?
Which statements about freeing and writing are correct in the speculative Tomasulo algorithm?
The exam's Res. Alloc. column follows the first rule: a station name appears from issue to Write Result and then becomes free for the next instruction.
Key take-aways
- Speculation means predict, execute before the branch resolves, and undo if the guess was wrong; the undo is possible only because the architectural state — register file and memory — is not touched until commit.
- Execution is out of order, commit is in order: completed is not committed. An instruction commits only when it is at the head, its result is ready and it is not speculative.
- Precise exceptions come for free: an exception is recorded in the entry and taken at the head, when everything older is committed and everything younger is still in the buffer; an exception on a flushed path is discarded with it.
- The ROB number is the new tag: the rename table maps each register to the entry of its newest in-flight producer; an operand comes from the register file, from a ready entry, or as a tag to wait for on the CDB. WAR and WAW vanish, RAW is served by the bus, and reservation stations remain as staging areas.
- Figure 27 changes three things in Tomasulo's datapath: the CDB feeds the ROB, the ROB writes the register file and memory at commit, and the store buffer is gone because a store's address and data live in its entry.
- The ROB is a ring: issue at the tail, commit at the head, full and empty told apart by the busy bit; a blocked head stalls issue when the ring fills. A misprediction frees every entry younger than the branch, moves the tail back and restores the rename table — which holds names, never values.
What to watch and read
-
ROB Part 1 — Georgia Tech — HPCA: Part 3
Udacity (Milos Prvulovic)short clip
Watch it right after section 2: why Tomasulo alone cannot undo a mispredicted branch or give precise exceptions, and the before/after of "registers written at write-result" versus "at commit".
-
Handout 10: Out-of-Order Execution with ROB
MIT 6.823, 2005 (Arvind, Asanović, Emer)2 pages
The whole ROB machine on one sheet, with a filled-in snapshot of ROB, rename table and register file: open it next to the ring widget and match the fields. Mind its own notation (p1/src1, tags t1 … tn), not the notes' Vj Vk Qj Qk.
-
FREESS — free superscalar simulator (browser build)
Roberto Giorgi, University of Siena
A superscalar Tomasulo with an explicit ROB. Run the same small loop with a ROB of 4 and of 16 entries and watch how a small ring stalls issue — the cost named at the end of section 5.
-
Implementing Precise Interrupts in Pipelined Processors
James E. Smith and Andrew R. Pleszkun, IEEE Transactions on Computers, 198812 pages
Where the reorder buffer comes from. Read the definition of "precise" on the first pages and the comparison of the five solutions; the reorder buffer (with and without bypass) and the history buffer are the ones that survived.