The speculative Tomasulo algorithm, stage by stage — and the ROB exam table

One paragraph of recall, one loop, four stages

Lesson 17 built the reorder buffer: a circular buffer with one entry per instruction in flight, allocated at the tail when the instruction issues and freed at the head when it commits. An entry holds Busy, the instruction and its type, the destination (a register; a memory address for a store; nothing for a branch), the Value once it exists, a Ready bit and the course's Speculative flag. Head and tail are two pointers; head = tail means full if that entry is busy and empty if it is not. Beside the buffer stands the rename table — register name → the entry that will produce its newest value — and the reservation stations stay where Tomasulo put them. That is all you need from lesson 17.

The algorithm has four stages, and the whole lesson walks them on one loop: the notes' Example 14 (pages 242–245), written here in the mnemonics of the exam papers. The notes write MULTD and #8; BNEZ (branch if not zero) stays, because the papers' BNE needs a second register the loop does not have; the registers are written without the dollar sign, as the 2026 paper does (older papers write $F0).

Loop: I0: LD   F0, 0(R1)
      I1: FMUL F4, F0, F2
      I2: SD   F4, 0(R1)
      I3: SUBI R1, R1, 8
      I4: BNEZ R1, Loop

Assumptions of the walk: one instruction issues per cycle, in program order, from cycle 1; the first LD misses in the cache and takes many cycles; FMUL takes several; SUBI takes one; BNEZ is predicted taken; the ROB has 8 entries. The notes do not say how many stations there are, so take two load buffers (Load1, Load2), two multiplier stations (Mult1, Mult2) and two integer stations (Int1, Int2) — enough for the iteration and a half the example covers.

The dependences, as the exam's dependence table would list them: I1 reads F0 from I0 (RAW), I2 reads F4 from I1 (RAW), I4 reads R1 from I3 (RAW); I3 writes R1 after I0 and I2 have read it (WAR); and across iterations the next LD writes F0 while this FMUL still needs it (WAR), while F0, F4 and R1 are written again (WAW). Renaming through ROB entries removes every WAR and WAW; the three RAWs are what the common data bus serves.

Read the picture once as a sentence per stage: issue allocates, execute computes, write result publishes to the buffer, commit publishes to the world. Now each stage in the detail the exam asks for.

Issue: a station and a ticket, or nothing

Issue takes the next instruction from the instruction queue and checks two things before it may enter: is a reservation station of its class free, and is a ROB entry free? Both must be. If either is missing the instruction stalls in the queue — and since issue is in order, everything behind it stalls too. This is a structural hazard, and the only thing "ROB full" closes is the entrance: the stations, the units and the CDB keep working.

When both are free, three things happen in the same cycle. First, the entry at the tail is taken: Busy = Yes, the instruction and its destination are written in, Ready = No, Value empty, and Spec = Yes if an older branch in the buffer is still unresolved; the tail advances. Second, the destination register is renamed: the rename table now says F4 → ROB1, whatever it said before. The newest producer always wins, even while an older writer of the same register is still in flight. A load also takes a load buffer; a branch takes an integer station and has no destination; a store, in the paper's table, takes none of the listed stations — its address and its data will live in its entry, which is why the speculative machine has no store buffer. Third, the ROB number goes to the station: it is the tag the result will carry on the CDB — "this ROB number replaces the register name during speculative execution", page 239.

The source operands are fetched by a rule with three cases, and the notes give only parts of it: page 239 says "Ready in the Register File → send it immediately to the Reservation Station; Pending in the ROB → send the ROB number (tag)", page 232 says "If an ROB entry is mapped: the instruction reads the pending value from the ROB". Both are right, and together they make the rule.

The middle case is the one the exam's scenario produces all the time. A head stuck on a cache miss means that everything behind it finishes without committing, so later instructions find their operands complete in the ROB and absent from the registers. The widget runs the rule on the loop.

Issue needs a free station and a free entry; it takes the entry at the tail, renames the destination to it, and gives each source a value (register file or ready entry) or a tag (entry not ready).

Execute and write result: the value goes to the entry, not to the register

Execution starts when every operand is in the station: "RAW hazards must already be solved to start execution", page 239. A station holding a tag listens to the CDB and captures the value the moment its tag is broadcast; nothing else is blocked meanwhile. Three special cases. A store needs only its base register to start: the effective address is computed, and the data "can still arrive later, closer to the commit phase" (page 240). A load computes its address and then waits until no earlier store in the buffer has an address still unknown or equal to its own — the memory disambiguation of lesson 17 — because a store writes memory only at commit, so the value a load needs may still be sitting in a store's entry. A branch computes its condition and compares it with the prediction: this is the moment the guess is checked, not commit.

When the unit finishes, write result puts ⟨ROB tag, value⟩ on the CDB. Two kinds of listener catch it: every reservation station waiting for that tag, and the entry itself — Value filled, Ready = Yes. The station that held the instruction is freed in the same cycle; the entry is not. And the register file is not touched: in the notes' Figure 27 (Fig. 3 of lesson 17) the CDB no longer reaches the registers at all. A store's data, if it was waiting as a tag, is captured here into the entry's Value, so that by commit the entry holds both address and data.

The consequence the exam likes: a dependent instruction never waits for the producer's commit. The FMUL of the loop gets F0 the cycle after the load's write result, whether or not the load has reached the head. The notes say otherwise at one point:

Write result publishes ⟨tag, value⟩ to the stations and to the entry, frees the station, and leaves the register file alone.

Commit: the head, and only the head

Commit is the only stage that touches the architectural state, and it looks at one entry: the head. Three conditions: the instruction is at the head; its Ready bit is set; and, in the course's table model, its Spec flag is No (Hennessy and Patterson need no flag: an instruction reaches the head only after every older branch has committed, so the two views agree — lesson 17 said so). Then one of three things happens, page 241:

• Normal commit (an arithmetic instruction or a load): the Value is written into the register file, the entry is freed, the head advances. The rename entry of the destination is cleared only if it still points to this entry — a younger writer may have re-mapped the register meanwhile.
• Store commit: the data is written into memory at the address kept in the entry, then the entry is freed. Memory sees stores in program order, which is what keeps memory updates precise too.
• Branch commit: predicted right — nothing special, the entry is freed. Mispredicted — every entry younger than the branch is flushed, the tail goes back to the entry after the branch, the stations and load buffers of the flushed instructions are squashed, the rename table is restored (each flushed mapping goes back to the older producer still in flight, or to "—" if that one has already committed), and fetch restarts on the correct path.

Real cores recover as soon as the branch resolves rather than when it reaches the head — Hennessy and Patterson say so, and the notes' Example 13 silently does the same — but the state after recovery is identical, and the exam's tables describe that state. An exception is handled like a misprediction: it is recorded in the entry and taken when the instruction reaches the head, so an exception raised on a mispredicted path is simply flushed with its entry and never happens.

The price of in-order commit is the one the puzzle is about. A head that waits — a load missing in the cache — stops every commit behind it, however finished; the entries stay busy; the tail catches up with the head; issue stops. Execution continues until the stations run dry, then the machine idles with a buffer full of results. This is why the size of the buffer matters so much: Tomasulo's 1967 paper had the hardware "looking ahead" about eight instructions; Intel's Golden Cove core of 2021 keeps 512 in its reorder buffer, so that a miss of a few hundred cycles at the head does not freeze the whole core. The exam's 8- and 10-entry buffers fill in eight and ten cycles of issue — which is exactly the moment the papers ask you to draw.

Only the head commits, only when Ready and not speculative; a stuck head freezes the buffer, and "ROB full" stalls issue, not execution.

Example 14: eight entries, a stuck head and a second iteration on credit

Now the notes' snapshots, pages 242–244, with the column the exam adds (Res. Alloc.) and the exam's status words: No, issued · No, exec. · Yes; the asterisk marks the cache miss, as the paper writes it. First snapshot: the five instructions of the first iteration have issued, one per cycle, each taking the entry at the tail.

Three details worth a mark each. The store's destination is a memory address and it takes none of the listed stations. The branch has no destination but does take an integer station, because its condition is computed on the integer unit. And R1 → ROB3 belongs in the rename table even though the notes' printed table has only F columns (the text on page 242 says "R1 to ROB3", the table forgets it); the paper's rename table lists F registers only, so write R1 beside it if the exercise mentions integer registers at all.

Second snapshot, "after some cycles": the load has completed and sits at the head, Ready — it will commit in the next cycle; the notes freeze the picture just before. Meanwhile the fetch unit, trusting the prediction, has issued the first three instructions of the second iteration behind the branch. They take ROB5–7 and the flag Spec = Yes, because BNEZ in ROB4 is, in the notes' timeline, still unresolved. The tail has caught up with the head: eight busy entries, the ROB is full, issue stops.

Look at the rename table: F0 → ROB5 while ROB0, the older writer of F0, is still in the buffer. That is renaming doing the work of loop unrolling at run time — "enables dynamic loop unrolling without conflicts", page 238 — and it is why the second FMUL (ROB6) waits for ROB5 and not for ROB0. One thing in the snapshot is not what the hardware would do:

Third snapshot, the first commit. ROB0 is at the head, Ready and not speculative: its value goes into F0, the entry is freed, the head moves to ROB1 and the tail finds ROB0 free. The rename table does not change: F0 still says ROB5, because the mapping no longer pointed to ROB0. The multiply, which has had F0 since the broadcast, is now executing.

The notes' fourth snapshot follows at once: the tail issues the second iteration's SUBI into the freed ROB0, speculative, and the buffer is full again — the "critical situation" of page 244. The whole run now rests on the prediction. If BNEZ resolves taken, the flags of ROB5, ROB6, ROB7 and the new ROB0 clear and the entries commit in their turn. If it resolves not taken, all four are flushed, the tail returns to ROB5, F4 goes back to ROB1 and R1 to ROB3 — but F0 goes to "—", not to ROB0, because ROB0 has committed and F0's value is in the register file now. Fig. 3 drew the two outcomes one snapshot earlier, with ROB0 still in flight: compare the rename tables and you have the restore rule.

Renaming to entries lets the next iteration issue behind an unresolved branch with fresh names; a stuck head keeps all of it in the buffer until the guess is checked.

The February 2025 exercise: ten rows and a rename table

The paper of 11 February 2025, Exercise 4 "Reorder Buffer", as transcribed in the notes (pages 567–568). Registers R1 and R2 are initialised at 0 and 40; the branch is predicted taken. The paper writes the registers with dollar signs and the H&P spellings ADDD $F4, $F2, $F2 and ADDI $R1, $R1, 4; here they are in the 2026 paper's form.

L0: LD   F2, 0(R1)
L1: FADD F4, F2, F2
L2: SD   F4, 0(R1)
L3: ADDI R1, R1, 4
L4: BNE  R1, R2, L0      ; branch predicted as taken

Three counting questions come first, then the unrolling, then the table. The counts are a four-line derivation.

1. Iterations: R1 goes 0, 4, 8, … and the loop exits when R1 equals R2 = 40. The index is updated before the compare, so the branch is taken 9 times and falls through once.

   \[ N = \frac{R2 - R1_0}{\Delta R1} = \frac{40 - 0}{4} = 10 . \]

2. Instructions per iteration: 5. Control versus datapath: the notes use the course's loop-overhead criterion — the index update and the branch "control the flow", the load, the add and the store "do actual data processing" — so 2 control, 3 datapath. State the criterion in your answer: under a strict ISA taxonomy ADDI is an integer ALU instruction.

3. Unrolling by 2 with register renaming: copy the body, give the second copy fresh registers (F6, F8) so that the two copies share no name, shift the second copy's offsets by one element (+4), keep one index update of twice the step and one branch.

   \[ N' = \frac{N}{2} = 5 \] \[ I_{\text{iter}} = 2 \cdot 3 + 2 = 8 \]

4. So the unrolled loop runs 5 iterations of 8 instructions: 2 control versus 6 datapath, the overhead down from 2/5 to 2/8, the dynamic instruction count from 50 to 40.

L0: LD   F2, 0(R1)
L1: FADD F4, F2, F2
L2: SD   F4, 0(R1)
L3: LD   F6, 4(R1)
L4: FADD F8, F6, F6
L5: SD   F8, 4(R1)
L6: ADDI R1, R1, 8
L7: BNE  R1, R2, L0      ; predicted taken

Then the machine: "the Speculative Tomasulo architecture with a 10-entry ROB and 4 Load Buffers (Load1, Load2, Load3, Load4); 4 FP Reservation Stations (FP1, FP2, FP3, FP4); 2 Integer Reservation Stations (Int1, Int2)", to be filled "until the ROB becomes full while the first instruction is still in execution due to a cache miss (*)". The paper gives the first two rows and a rename table with F0 already "–". From those rows you read the paper's snapshot convention: the head is "No, exec.(*)" and every entry behind it is "No, issued" — even the ADDI, which in a cycle-accurate run would have finished long ago; the snapshot records allocation, not progress. The remaining conventions: Res. Alloc. is the lowest free buffer or station of the instruction's class, the branch takes an integer station, a store takes "–"; Dest. is the register, "Mem" with the address for a store, "–" for the branch; Spec is Yes for every entry issued behind the unresolved BNE, and the branch itself is never speculative.

Fill the table yourself. The widget checks each row against the recomputed answer and keeps the pools, the pointers and the rename table in step.

Back to the puzzle. The complete table is in the exam section below; its shape is the answer. Ten busy entries with head = tail = ROB0: the buffer is full and issue has stopped, while inside it the second load, the adds and the stores are still free to execute. ROB8 and ROB9 are the two tickets of an iteration that exists only on the strength of a prediction, and they hold the names F2 and F4 — the rename table reads F2 → ROB8, F4 → ROB9 with ROB0 and ROB1 struck through but still in flight. If the guess is wrong, what is torn up is exactly that: two entries, a load buffer and a station, and two mappings that fall back to ROB0 and ROB1. Registers and memory never knew.

In the paper's snapshot: head "No, exec.(*)", everything else "No, issued", the lowest free station of the class, "–" for stores, Spec = Yes behind the branch, and the rename table pointing at the newest writer.