Tomasulo meets a loop: eighteen cycles of renaming in action

The loop, the machine and the four tables

The loop is the one lesson 15 unrolled by hand: it multiplies every element of an array by the scalar in F2, walking down from the address in R1. This time nobody touches the code. In the papers' mnemonics:

I0  LOOP: LD    F0, 0(R1)      ; F0 ← M[R1]
I1        FMUL  F4, F0, F2     ; F4 ← F0 × F2
I2        SD    F4, 0(R1)      ; M[R1] ← F4
I3        SUBI  R1, R1, 8      ; next element, 8 bytes down
I4        BNE   R1, R2, LOOP   ; predicted taken

The assumptions are on page 194: the first LD misses in the cache and takes 8 clock cycles, the second hits and takes 1 (so does the third, in the tables), FMUL takes 4, and the branch is predicted taken, so issue carries on with the next iteration. SUBI and BNE run on the integer side and are not tabulated. R1 starts at 80, so the iterations touch the addresses 80, 72 and 64. The question behind the example: memory is slow and floating point moderately slow — can the machine keep working while the first load is stuck in memory?

The notes never draw the machine; you read it off their tables. Three load buffers, Load1 to Load3; three store buffers, Store1 to Store3; two multiply stations, Mult1 and Mult2 (the add stations stay empty). One common data bus, the CDB. One memory unit that serves one load at a time, so a hit cannot overtake a miss. And a multiplier that works on two FMULs at once: in cycles 12 to 14 both stations count down together. Fields and stages are those of lesson 11 and lesson 12.

Two kinds of field do the renaming. Addr, Vj and Vk are copies: what exists at issue is copied into the entry, so a later write to R1 or F2 cannot disturb it — a WAR hazard dies there. Qj, Qk and a store's FU hold a tag, the name of the buffer or station that will produce the missing value: a reader is tied to its producer, not to a register name. And the register status names only the youngest writer of each register, so an older result can never land on top of a younger one — a WAW hazard dies there.

The timing rules are lesson 12's stages turned into arithmetic, as in lesson 13. Issue goes in program order, one instruction per cycle, into a free entry of the right class; a missing operand never delays issue — it becomes a tag. Execution starts the cycle after the last operand arrives. The CDB carries one result per cycle, oldest first: every entry holding the tag copies it, the register file only if the register's status still names that tag. An entry stays busy until its result has been broadcast; a store executes the cycle after its data arrives and writes memory in the next.

Issue copies what exists — a value, an address — and writes a tag for what does not; after that, no entry cares what its registers are called.

Cycles 1–8: issue runs ahead of the data

Fig. 1 is the end of cycle 3: LD₁ entered Load1 at cycle 1, FMUL₁ entered Mult1 at cycle 2 — copying the value of F2 (Vk = R(F2)) and recording the tag of F0 (Qj = Load1) — and SD₁ entered Store1 at cycle 3 with FU = Mult1. Nothing has been computed, yet the iteration's data-flow graph already exists in hardware, written in tags.

Cycles 4 and 5 belong to the integer side: SUBI₁ and BNE₁ issue, R1 reads 72 from cycle 5, the branch is predicted taken. Cycles 6 to 8 are the reason the example exists: iteration 2 issues while iteration 1 still waits for memory — LD₂ into Load2 with Addr = 72, FMUL₂ into Mult2 with Qj = Load2, SD₂ into Store2 with FU = Mult2. The register status is simply overwritten, F0 from Load1 to Load2 and F4 from Mult1 to Mult2, while Mult1 keeps Qj = Load1 and Store1 keeps FU = Mult1.

At the end of cycle 8, six instructions from two iterations are in flight, all spelled with F0 and F4, and nothing conflicts: every waiting field holds a tag, and the tags all differ. The notes call it the dynamic loop unrolling effect (page 193): two copies of the body side by side, although nobody copied the code.

One thing looks odd: LD₂, a hit issued at cycle 6, executes only at cycle 10. The notes' reason (page 202) is wrong.

In order in, out of order through: issue goes 1, 2, 3, 6, 7, 8, while LD₂ finishes executing at cycle 10 — before FMUL₁ has even started.

Cycle 10: one broadcast, two answers

At cycle 9 Load1 completes its eighth memory cycle and SUBI₂ issues. Cycle 10 is the moment of the puzzle. Load1 puts ⟨Load1, M[80]⟩ on the CDB, and every entry compares the tag with its fields. Mult1 holds Qj = Load1: it copies the value into Vj, and its Time field starts at 4, for the execution cycles 11 to 14. The register file compares the tag with F0's status, which since cycle 6 says Load2: no match, F0 does not change. Load1 is freed, and Load2 finally gets the memory unit.

Ignoring the value loses nothing: the only instruction that needed M[80] was FMUL₁, and it took it from the bus. F0 must end up holding what the youngest load put in it, so it listens for that load's tag only; taking M[80] would overwrite a claim that belongs to a younger instruction. This is WAW protection, and it costs no stall at all.

What did the tags buy? Draw both iterations as a dependence graph, as lesson 15 did: a chain of true dependences inside each iteration, LD → FMUL → SD, and four name dependences between them — two WAW, because F0 and F4 are written twice, and two WAR, because FMUL₁ reads F0 before LD₂ writes it and SD₁ reads F4 before FMUL₂ writes it. A machine that tracks registers by name must respect all of them; one that renames keeps only the true ones.

A value goes to whoever holds its tag; the register file is one more listener, and it listens only for its youngest writer.

Cycles 11–18: countdowns, a full house and two stores

Cycle 11 repeats cycle 10 for the second iteration: Load2 broadcasts M[72] and Mult2 takes it. In the same cycle LD₃ is issued into Load3 (Addr = 64) and F0's status becomes Load3. Issued, not started — the notes say otherwise.

From cycle 11 the two multiplies count down side by side, Mult1 from 3 to 0 and Mult2 from 4 to 1. At cycle 12 the machine hits its first wall. FMUL₃ is next in program order and its operand will be ready at cycle 13, but both multiply stations are busy — and a station stays busy until its result has been broadcast, at 15 and 16. No free station, no issue: a structural hazard on the reservation stations, not a data hazard. Because issue is in order, SD₃ waits behind it although Store3 is free. At cycle 13 Load3 broadcasts M[64]; no younger load has claimed F0, so the register file takes it — the only loaded value F0 keeps in the whole run.

At cycle 15 Mult1 broadcasts M[80]×F2: Store1, which has held FU = Mult1 since cycle 3, takes it, and F4, whose status names Mult2, ignores it. Mult1 is freed and, in the notes, refilled in the same cycle with FMUL₃, which reads F0 = M[64] from the register file. At cycle 16 Mult2's product goes to Store2, and F4 ignores this one too: its status now names Mult1. Cycles 17 and 18 belong to the stores, and the notes narrate them with two slips.

The result of the exercise is the notes' last instruction-status table (page 221), here in the paper's headings plus the notes' Exec Comp:

Four causes account for every cycle of the chart. The miss: nothing floating-point executes from cycle 2 to 9, yet issue goes on, and by cycle 8 six instructions wait in buffers and stations. Stations held until write result: Mult1 is occupied from cycle 2 to 15 — fourteen cycles for four of multiplying — and that keeps FMUL₃ out for three cycles. In-order issue: SD₃ queues behind FMUL₃. The memory unit: one access at a time, so LD₂ waits behind the miss. What costs nothing: the CDB (results at 10, 11, 13, 15 and 16, never two in a cycle; on the papers' machine they collide, lesson 14) and the register names.

Change one assumption at a time and the chain moves (same rules as the notes' run):

Two rows deserve a sentence. With a non-blocking cache, LD₂ writes F0 at cycle 8 and LD₁'s older value arrives at 10 — the classic WAW hazard, a stale write after a fresh one — and the register file ignores it, because F0's status no longer names Load1. With every load a hit, the loop settles into one iteration every 5 cycles, CPI = 1, the single-issue limit: each FMUL holds its station 7 or 8 cycles while a new one arrives every 5, so on average 1.5 stations are busy (a count not in the notes). The miss alone stretched Mult1's stay to fourteen cycles.

The time goes to the miss, to stations held until write result, to in-order issue and to the single memory unit — never to the register names.

The paper's version: one iteration, one table

The exam never asks for the four tables: Exercise 1 of every paper from 2024 to 2026 gives one iteration on a fixed machine, a dependence table and then one timing table, filled with the eight conventions of lesson 12. The formats differ in more than layout:

Here is the loop on the machine of July 2024 and June 2026: a single CDB; RS1 and RS2 with load/store units LDU1 and LDU2, latency 4; RS3 and RS4 with FPU1, latency 3; RS5 and RS6 with ALU1, latency 2. The first row is the one every paper pre-fills.

1. I0, given. Issue 1 into RS1; R1 is valid, so it starts at 2, occupies LDU1 for 4 cycles (2 to 5) and writes F0 on the CDB at 6. From cycle 1, F0's tag is RS1.

2. I1 FMUL. Issue 2 into RS3: F2 is copied, F0 is recorded as the tag RS1 — a RAW with I0. The value arrives on the CDB at 6, so START EXEC = 6 + 1 = 7 and WRITE RESULT = 7 + 3 = 10.

3. I2 SD. Issue 3 into RS2, since RS1 is busy until 6. The address uses R1, valid now; the data is the tag RS3, a RAW with I1 for F4. START EXEC = 10 + 1 = 11; WRITE RESULT = 11 + 4 = 15, the end of the memory write — a store takes no CDB slot.

4. I3 SUBI. Issue 4 into RS5; R1 is valid, so it starts at 5 and writes at 5 + 2 = 7, the bus being free. It overwrites R1 while I2 still has to use its address (from cycle 11): a WAR with I0 and I2 for R1, harmless because both copied R1 at issue.

5. I4 BNE. Issue 5 into RS6. R1 comes from I3 at 7 and ALU1 is free after I3's write, so START EXEC = 8 and the result would be ready for 8 + 2 = 10. At 10 the bus belongs to I1, the older instruction: BNE writes at 11 — Structural on the CDB. The papers never say whether a branch uses the CDB; if you assume it does not, write 10 and say so — the CPI does not change.

6. CPI. The last WRITE RESULT of the iteration is the store's: CPI = 15 / 5 = 3.0.

Two cells deserve a second look. FMUL waits in RS3 from cycle 3 to 6 while FPU1 is idle — a RAW wait inside a station, not a stall at issue. SUBI writes R1 at 7 while SD still needs its address at 11 to 15: harmless, because the address was copied at issue ("solved by renaming"). A second FP unit or ALU, as on the June 2025 machine, changes nothing here: every wait is a RAW or the bus.

The theory part asks for the same mechanism in words; the first exam-style question below answers four items of the June 2026 question on this loop.

One assumption the walkthrough never questions: the branch. BNE₁ and BNE₂ are predicted taken, and the next iteration issues before either is resolved. The rule of lesson 4 forbids updating registers or memory before the branch outcome is known, and plain Tomasulo cannot take a write back: a broadcast goes straight into the register file, a store straight into memory. So, as lesson 15 said when it struck out the notes' word "speculatively" (page 193), it may issue past a predicted branch, but nothing behind the branch may execute until the branch is resolved. Here that costs nothing: a BNE needs only R1, which the integer side has ready, so BNE₂ (issued at 10) is resolved by cycle 11, before LD₃ executes at 12. Make the branch wait for a slow result, a load that misses, and everything behind it sits in its station: the overlap is gone. Executing past the branch and undoing a wrong guess is the reorder buffer's job.

Back to the puzzle. F0 and F4 ignored those values because each register listens only for the tag of its youngest writer; the values went where their tags pointed — M[80] to Mult1, the two products to Store1 and Store2 and on to memory at 80 and 72. The one word is tag: in Tomasulo's machine a value is addressed to the instructions that wait for it, not to a register.

On the paper: one iteration, START EXEC = the producer's WRITE RESULT + 1, a station free the cycle after its write, CPI = 15 / 5 = 3.0 for this loop.