Robert Tomasulo's January 1967 paper on the IBM System/360 Model 91 sums up its floating-point unit in one line of the abstract: "a simple common data busing and register tagging scheme which permits simultaneous execution of independent instructions while preserving the essential precedences". Tagging is Issue, busing is Write Result, and the precedences are the true dependences that Execute still waits for.
Issue, execute, write result: the three stages and the exam table
After this lesson you will fill the ISSUE / START EXEC / WRITE RESULT / Hazards Type / RSi / UNIT table of an exam loop with the paper's own conventions, and point, for every cell, at the rule that fixed it.
The paper of 22 June 2026 hands you seven instructions — a loop body with two loads, two FP adds, a store, an increment of the index and a branch — and a machine built to run them out of order: two load/store units, one FP unit, one integer unit, one Common Data Bus, every cache access a hit. You will compute the answer in this lesson: the body takes 19 cycles, and the last instruction to finish is the fifth one, the store. The branch issued after it is resolved four cycles earlier.
Here is the puzzle. Issuing seven instructions takes seven cycles. Where do the other twelve go — and how many of them are the machine's fault? The store cannot even enter the machine before cycle 7; the branch loses a fight for the bus at cycle 14. Count those against the machine if you like. The answer at the end of the lesson is a single number, and it is smaller than you expect.
First the three stages, each walked on this loop; then the rules the papers use; then the table, cell by cell.
Three stages, and where the order is kept
Lesson 11 built the machine: reservation stations in front of every functional unit, a register file with a tag next to each value, and one Common Data Bus carrying every result to everybody. The table below is all you need to recall; this lesson is about what happens in time.
| Where | Field | Meaning |
|---|---|---|
| reservation station (RS) | Busy, Op | the station holds one issued instruction and its operation |
Vj, Vk | the values of the two source operands, when they were available at issue | |
Qj, Qk | otherwise the tags of the stations that will produce them; 0 = the value is in V | |
(A) | for a load or store: the offset, then the effective address | |
| register file | Qi | the tag of the station that will write this register next; 0 = the register holds a valid value |
| Common Data Bus (CDB) | ⟨tag, value⟩ | one result per cycle, seen at once by every station, every store buffer and the register file |
Everything here is walked on the loop of the June 2026 paper, written as the paper writes it (older papers write $F2 and $R1; the 2026 paper drops the dollar sign, and so does this notebook):
I0 FOR: LD F2, AA(R1)
I1 FADD F2, F2, F2
I2 LD F4, BB(R1)
I3 FADD F2, F2, F4
I4 SD F2, A(R1)
I5 ADDUI R1, R1, 8
I6 BNE R1, R2, FORThe machine of the paper: 2 reservation stations (RS1, RS2) with 2 load/store units (LDU1, LDU2) of latency 4; 2 reservation stations (RS3, RS4) with 1 FP unit (FPU1) of latency 3; 2 reservation stations (RS5, RS6) with 1 integer/branch unit (ALU1) of latency 2; all cache hits; a single Common Data Bus.
An instruction goes through three stages (notes, page 151). Issue, in program order: decode it and park it in a reservation station. Execute, out of order: wait in the station for the operands, then compute in the unit. Write Result, out of order: broadcast the result on the CDB to the stations and the register file. Unlike the scoreboard of lesson 9 there is no Read Operands stage: operands are read at issue when they exist, or delivered by the bus when they do not — which is exactly what removes the WAR stall, because nobody reads a register later.
I3 leaves the queue in program order into RS4, carrying the tags of its two producers. (2) At cycle 7, RS3 fires I1 into FPU1: its two tags have become values. (3) At cycle 10, I1's result goes on the bus as ⟨RS3, v(F2)⟩ to everybody at once — RS4 fills its Qj, and F2 is not written, because its tag already says RS4. Only the first arrow keeps program order.Issue: in order, one per cycle — or stall
Issue does four things to the instruction at the head of the queue (notes, page 151): decode it; find a free reservation station of its type (an FADD needs a station of the FP unit); for each source register, copy the value into Vj or Vk if the register is valid, otherwise its tag Qi into Qj or Qk; and rename the destination by writing this station's name into its Qi. Watch it on the first four cycles of the loop.
Cycle 1. I0 LD F2, AA(R1) goes into RS1. R1 is valid, so Vj = v(R1) and the offset AA waits in the address field. Then F2.Qi ← RS1: from now on, whoever needs F2 will wait for RS1, not for "F2".
Cycle 2. I1 FADD F2, F2, F2 goes into RS3. Both sources are F2 and F2.Qi says RS1, so Qj = RS1 and Qk = RS1. Then the destination is renamed again: F2.Qi ← RS3. The register file has forgotten RS1; only RS3 remembers it.
Cycle 3. I2 LD F4, BB(R1) goes into RS2, with Vj = v(R1) and F4.Qi ← RS2.
Cycle 4. I3 FADD F2, F2, F4 goes into RS4 with Qj = RS3 and Qk = RS2, and F2.Qi ← RS4 — the third name F2 has had in four cycles.
Before: after cycle 1
After: after cycle 4
The notes' Example 7 (page 152) does the same with ADD.D F6, F2, F4 and MUL.D F8, F6, F10 — the notes' spelling of FADD and FMUL, as in Hennessy and Patterson; this lesson writes its own code the papers' way. RS2, holding the multiply, "knows that it must listen for RS1's result on the Common Data Bus". The example stops one step short: the multiply also renames its destination, F8.Qi ← RS2.
What stalls the issue stage
Three things, and a RAW dependence is not one of them (page 152). First, no free reservation station of the needed type — a structural hazard, the stall the June 2025 and June 2026 papers both contain: in cycle 5 the store I4 needs a load/store station, RS1 holds I0 and RS2 holds I2 (a station stays busy from ISSUE through WRITE RESULT), so I4 issues only at 7, and the independent I5 and I6 wait behind it. (A type is a unit class: the notes' page 162 sends SUB.D to an ADD-type station and DIV.D to a MUL-type one; the papers have one FP class.)
Second, a full load/store queue — the same kind of stall for memory operations. Third, in the basic, non-speculative machine, an unresolved branch: the instructions after it must wait until it is resolved, and without a prediction the machine does not even know which instruction comes next. The speculative machine of lesson 17 removes that wait. A RAW dependence never stops an issue — the instruction takes a tag and waits in its own station, blocking nobody.
Why issue is kept in order
Renaming works only because every issue sees the register status table as the previous instruction left it: the destination's Qi must name the youngest writer, and a consumer must capture the tag of the last writer before it. Let I3 issue before I1 and all three go wrong: I3 captures RS1, the wrong producer of its F2; I1 then captures RS4, a younger instruction; and F2 ends up owned by I1 instead of I3. The second reason is memory order (the load/store queue takes the order of the stores from the issue sequence), the third simplicity. Precise exceptions are not on the list: results are still written out of order.
Issue copies a value or a tag, never a promise to read later — that is why a later writer can never hurt an earlier reader.
Execute: when Qj = Qk = 0 and the unit is free
A station fires its instruction into the unit when both tags are zero — the operands are in Vj and Vk — and the unit is free (page 154). Nothing else: not the program order, not a fixed cycle count. On the loop, I0 starts on LDU1 in cycle 2, the cycle after its issue, because R1 was ready, and I2 starts on LDU2 in cycle 4 — two loads overlap because there are two units. I1 sits in RS3 from cycle 2 to cycle 6 with Qj = Qk = RS1: a RAW wait, but one that blocks nobody. The notes call this dataflow execution: instructions run when their data are ready, not when the program says so.
When two stations of one unit are ready in the same cycle, the oldest goes first (page 155). Then the unit executes for its latency, with the convention every cell of the exam table depends on: a unit of latency L that starts in cycle s executes in cycles s … s + L − 1 and writes in cycle s + L — the paper's own pre-filled row, LD with latency 4 as ISSUE 1, START EXEC 2, WRITE RESULT 6. The papers do not say whether a unit is pipelined; the tables solved in the notes treat every unit as not pipelined, busy from its start through its write: FPU1 is busy with I1 from 7 through 10, and RS3 stays busy until that same write. In the three official papers the question never decides a cell — each second FADD depends on the first anyway.
Loads and stores
Memory is global, must stay precise and can raise exceptions, so loads and stores get special treatment (pages 155–156). A load waits for its base register (a tag in the load buffer if it is pending), computes the address and reads memory — both inside the exam's 4-cycle latency — then broadcasts the value like any result. A store needs two things, the address and the data, and either may arrive by tag: in the loop I4 waits in RS1 with Qk = RS4 until I3 broadcasts at 14, starts at 15 and writes memory at 19. Loads may pass other loads but never an earlier store to the same address; stores keep program order among themselves. And a store broadcasts nothing: it produces no register value, so nobody waits for its tag. The table still has a WRITE RESULT cell for the store; the solved tables fill it with the end of the memory write, START EXEC + 4, and that cycle takes no bus slot.
Fixed issue → execute. Data flow through registers. A RAW hazard stalls issue, and everything behind it. WAR and WAW are possible.
Execute waits dynamically for operands. Data flow through tags in the stations. A RAW wait happens inside one station only. WAR and WAW are eliminated by renaming.
Start = the cycle after issue, or the cycle after the last missing operand's broadcast, or the cycle after the unit's last write — whichever is latest; write = start + latency.
Write Result: one broadcast, every listener
When the unit finishes, the result goes on the CDB with the tag of the station that produced it (page 157): ⟨tag, value⟩, "anyone waiting for this, come get it". Three things follow in that same cycle. Every station compares the tag with its Qj and Qk; each match copies the value into Vj or Vk and clears the tag, which "allows many instructions to simultaneously wake up". The register file writes the register whose Qi matches, if there is one, and clears its Qi; a register whose Qi names another station is not written. The station is freed, and so is the unit.
The register write is for the instructions that have not issued yet: they will read the register file, and Qi = 0 tells them the value is there. Everybody already waiting got the value from the bus, before any register was written — the CDB is Tomasulo's forwarding path.
Cycle 6 of the loop is a complete example. I0 broadcasts ⟨RS1, v(F2)⟩ — v(F2) is the notes' way of writing "the value this instruction produces for F2"; the bus itself carries only the value and the producer's tag, never a register name. RS3 holds Qj = Qk = RS1: both of its operands come from this one broadcast. RS4 holds RS3 and RS2: no match. The register file finds F2.Qi = RS4, not RS1: the write is skipped. The load's F2 never reaches the register file — and nothing is lost, because the only instruction that needed it, I1, has it in RS3.
Example 8 done right
The notes justify the skipped write with A ADD.D F6, F2, F4 in RS1 and B MUL.D F6, F6, F8 in RS2 (page 158): after B issues, F6.Qi = RS2, so RS1's broadcast must not land in F6. True — but B reads F6, so RS2 holds Qj = RS1 and needs that broadcast: the value is anything but obsolete. And B cannot finish before A, so an early write by A would have changed nothing (as long as the tag RS2 stayed in place); the example cannot show the danger. The case the rule protects is the independent one. Below, F2 comes late from a load that missed, so I0 waits in RS1; I1 waits in RS2 with Qj = RS1; I2 has both operands and goes ahead (stations named as in the notes' example):
I0 FADD F6, F2, F4 ; RS1
I1 FMUL F8, F6, F10 ; RS2
I2 FSUB F6, F10, F12 ; RS3I2 finishes first and writes F6 — its tag matches — and clears Qi. Then the slow F2 arrives, I0 executes and broadcasts ⟨RS1, v(F6)⟩: RS2 fills its Vj, so I1 multiplies the old F6, as program order demands; and the register file finds F6.Qi = 0, not RS1, so F6 keeps I2's newer value, as program order demands. One broadcast, two correct outcomes: the WAR for I1 and the WAW for I2 both dissolved by a tag comparison.
One bus, one result per cycle
A single CDB carries one broadcast per cycle. When two units finish together, the older instruction writes first and the younger slips by one cycle — and again if the next cycle is taken too. In the loop, I3 and I6 are both ready at 14: I3 writes, I6 is resolved at 15 — if the branch, too, needs the bus, which no solved paper settles (convention C4 below). The other timing rule of the bus: a value broadcast in cycle w is usable from cycle w + 1, so I1 starts at 7, not at 6.
The tag on the bus is the producer's name: every station with that tag fills in, the register file writes only if its Qi still says that name.
Reading the dependences before the hardware does
Part 1 of the exercise asks, before any cycle is counted, for a table of "all types of true-data-dependences, anti-dependences and output dependences for each instruction". The rules are mechanical; what makes the table right is that nothing is missing. For each instruction look at every earlier instruction of the iteration: a true data dependence (RAW) on the nearest earlier writer of a register it reads; an anti-dependence (WAR) on every earlier reader of a register it writes; an output dependence (WAW) on every earlier writer of the same register. Every pair once per register, R registers included — R1 under the loads and the store counts.
| I# | Instruction | Analysis of dependences |
|---|---|---|
| I0 | LD F2, AA(R1) | None |
| I1 | FADD F2, F2, F2 | True data dependence with I0 for F2; output dependence with I0 for F2 |
| I2 | LD F4, BB(R1) | None |
| I3 | FADD F2, F2, F4 | True data dependence with I1 for F2 and with I2 for F4; anti-dependence with I1 for F2; output dependence with I0 and with I1 for F2 |
| I4 | SD F2, A(R1) | True data dependence with I3 for F2 |
| I5 | ADDUI R1, R1, 8 | Anti-dependence with I0, I2 and I4 for R1 |
| I6 | BNE R1, R2, FOR | True data dependence with I5 for R1 |
A dependence belongs to the program; a hazard belongs to a machine. The same twelve arcs exist on the 5-stage pipeline of lesson 2, on the scoreboard and on Tomasulo's machine; what changes is which of them cost cycles. Tomasulo keeps every true dependence as a wait in a station and turns the anti- and output dependences into non-hazards. In the Hazards Type column of Part 2 they cost nothing: write "WAR / WAW with I# solved by renaming" or leave them out — naming them shows that you saw them and knew they were harmless.
Why renaming makes them harmless, in two cases. Case A: the producer has already written when the consumer issues — the consumer copies the value into Vj, and no later writer of that register can touch its private copy. Case B: the producer is still pending — the consumer copies the producer's tag, and waits for that broadcast, not for "whatever the register ends up holding". The notes (pages 160–161) tell case B: DIV.D "still listening" for the first load while ADD.D renames F6 — which needs a slow load; in the run of lesson 13 that load has written before DIV.D issues, and DIV.D takes the value (case A). Both are safe; and because the register status table only ever names the youngest writer, an older writer's late broadcast is dropped at the register file (cycle 6 again).
A dependence belongs to the program, a hazard to the machine: Tomasulo pays for the true ones and names the others "solved by renaming".
The exam table: eight conventions and the June 2026 model
Part 2 of the exercise states the machine (the same sentence every year; only the number of FP and integer units changes), pre-fills the first row (LD: 1, 2, 6, None, RS1, LDU1) and asks you to complete the table and "Calculate the CPI". The notes' theory pages never state the timing rules, and no official solution is published. The two Tomasulo tables solved at the end of the notes (the 11 February 2025 paper and the 5 May 2025 midterm, lesson 14) apply the rules below; those solutions are the note author's, but the row 1 / 2 / 6 that every paper pre-fills agrees with them. Copy them onto your A4 sheet.
| # | Rule | Where you see it |
|---|---|---|
| C1 | Issue in program order, one per cycle from cycle 1, only into a free station of the class; a station is busy from ISSUE through WRITE RESULT and free again the next cycle. No station → the instruction and everything behind it wait (Hazards: Structural) | June 2026: I4 issues at 7; June 2025: the third load issues at 7 |
| C2 | Start exec = the latest of: ISSUE + 1; each producer's WRITE RESULT + 1; the cycle after the unit's last WRITE RESULT (the solved tables treat units as not pipelined, busy through their write cycle) | the pre-filled row 1 / 2 / 6; I1 starts at 7 after the load's write at 6 |
| C3 | Write result = START EXEC + latency, if the CDB is free | LD latency 4: 2 + 4 = 6 |
| C4 | One CDB: one write per cycle; on a tie the older instruction writes first and the younger slips to the next free cycle (Hazards: Structural on the CDB). Whether the branch takes a slot is not settled by any solved paper; this notebook gives it one and shows the other value | June 2026: I6 at 15, not 14; June 2025: I3 at 13, I7 at 18 |
| C5 | Stores start when address and data are both available (data by CDB: write + 1); WRITE RESULT = START EXEC + latency is the end of the memory write and uses no CDB slot | June 2026: I4 7 / 15 / 19 |
| C6 | Branch: an integer/branch instruction; starts when its registers are ready, WRITE RESULT = START EXEC + ALU latency; it closes the iteration | June 2026: I6 9 / 12 / 15 |
| C7 | Hazards Type: the dependences on earlier instructions — RAW with I# for the register; WAR / WAW "solved by renaming" (or left out: they never cost a cycle); Structural when a station, a unit or the CDB made the instruction wait; "issue delayed behind I#" when in-order issue held it behind a stalled instruction | every row below |
| C8 | CPI = the last WRITE RESULT cycle divided by the instructions of one iteration | 19 / 7 = 2.71; the notes' February 2025 paper (lesson 14): 22 / 8 = 2.75 |
Now the whole table, recomputed with these rules (no official solution exists; every cell was checked by the simulator of the widget below).
| INSTRUCTION | ISSUE | START EXEC | WRITE RESULT | Hazards Type | RSi | UNIT |
|---|---|---|---|---|---|---|
I0 LD F2, AA(R1) | 1 | 2 | 6 | None | RS1 | LDU1 |
I1 FADD F2, F2, F2 | 2 | 7 | 10 | RAW with I0 for F2; WAW with I0 for F2 (solved by renaming) | RS3 | FPU1 |
I2 LD F4, BB(R1) | 3 | 4 | 8 | None | RS2 | LDU2 |
I3 FADD F2, F2, F4 | 4 | 11 | 14 | RAW with I1 for F2, I2 for F4; WAR with I1, WAW with I0, I1 for F2 (solved by renaming) | RS4 | FPU1 |
I4 SD F2, A(R1) | 7 | 15 | 19 | RAW with I3 for F2; Structural: no free load/store RS at 5–6 | RS1 | LDU1 |
I5 ADDUI R1, R1, 8 | 8 | 9 | 11 | WAR with I0, I2, I4 for R1 (solved by renaming); issue delayed behind I4 | RS5 | ALU1 |
I6 BNE R1, R2, FOR | 9 | 12 | 15 | RAW with I5 for R1; issue delayed behind I4; Structural: CDB taken at 14 by I3 (14 if the branch takes no CDB slot) | RS6 | ALU1 |
CPI = 19 / 7 ≈ 2.71. The highlighted row is the hardest one of the paper; here it is one justified step at a time.
ISSUE.
I4followsI3(issued at 4), so the earliest cycle is 5. It needs a load/store station: RS1 holdsI0through its write at 6, RS2 holdsI2through its write at 8 (C1). First free cycle: 7, into RS1 — and LDU1 with it. Hazards: Structural, no free RS at 5–6.START EXEC. Address: R1 was valid at issue (the
ADDUIcomes later and renames R1 only for instructions issued after it), so Vj = v(R1). Data: F2.Qi = RS4 at cycle 7, so Qk = RS4;I3writes at 14, usable at 15 (C2, C5). Start = max(7 + 1, 14 + 1) = 15.WRITE RESULT. 15 + 4 = 19, the end of the memory write; no CDB slot is needed, so no tie is possible (C3, C5).
Hazards, RSi, UNIT. RAW with I3 for F2 (the data), Structural (the station); RS1, LDU1. The two cycles lost at issue cost nothing in the end: the store would have waited for F2 until 15 anyway.
CPI. The last write of the iteration is this one: CPI = 19 / 7 ≈ 2.71 (C8). The branch at 15 does not change it.
I2, is usable from cycle 9, two cycles before I3 starts, and costs nothing. Follow the F2 chain: 1 cycle of issue, then load 4 + 1, add 3 + 1, add 3 + 1, store 4 + 1 — exactly 19.Now the puzzle of the hook: how many of the twelve extra cycles are the machine's fault? None. Every one of the nineteen lies on the chain LD → FADD → FADD → SD through F2: one cycle to issue the load, then each link's latency plus its broadcast cycle — 1 + (4 + 1) + (3 + 1) + (3 + 1) + (4 + 1) = 19. Ten CDBs and a hundred stations could not shorten it, because each link needs the previous link's value. The hardware ran I2, I5 and I6 underneath the chain, and the two waits you could have blamed on it — the store's two cycles without a station, the branch's lost bus cycle — fall inside the chain and change nothing. That is the honest reading of CPI = 2.71: the program is serial, and dynamic scheduling hid what could be hidden.
Start = max(issue + 1, producers' writes + 1, unit free); write = start + latency; one CDB, oldest first; CPI = last write / instructions.
Exam-style questions
Explain the main concepts and benefits of each one of the following techniques used by modern superscalar processors (Tomasulo-style): 4. Reservation stations; 5. Dynamic register renaming; 6. Out-of-order execution. (Five lines each.)
Show model answer
Reservation stations. Buffers in front of each functional unit, each holding one issued instruction: its operation, its operand values (Vj, Vk) if they were available at issue, otherwise the tags (Qj, Qk) of the stations that will produce them, and a busy bit; the station's name is the tag under which its result will be broadcast. Benefits: the instruction leaves the in-order front end at once (a RAW dependence never stalls issue), waits locally and fires as soon as both operands arrive (data-driven execution); hazard detection is distributed, there is no central scoreboard; the stations give pending results more names than the ISA has registers. Cost: when all stations of a class are busy, issue stalls (structural hazard).
Dynamic register renaming. At issue the destination register's status field Qi is set to the station's tag, so the register always names its youngest writer; a consumer copies the value or the producer's tag at issue and never reads the register later. A result is broadcast with its tag, captured by every waiting station, and written into the register only if Qi still holds that tag. Benefits: WAR and WAW hazards (name dependences created by register reuse in loops and by the compiler's allocation) can neither stall nor corrupt — only true RAW dependences remain; the ISA's register count no longer limits scheduling; it is invisible to the program.
Out-of-order execution. An instruction starts in its unit as soon as Qj = Qk = 0 and the unit is free, independently of program order; results return out of order on the common data bus, one per cycle. Benefits: independent instructions proceed while a long-latency one (a load miss, a divide) waits, so stalls are hidden and throughput rises (lower CPI); latencies unknown at compile time are tolerated. Cost: completion out of order makes exceptions imprecise — a reorder buffer with in-order commit restores them.
The paper gives five blank lines per item: write short labelled statements, mechanism first, then "benefit:", then "cost:" where there is one. A complete answer names the fields of a station, the Qi tag and the "write only if the tag still matches" rule, and the exact firing condition of execution.
(Exercise 1, 15 July 2024; registers written without $.) Let's consider the following assembly code containing multiple types of intra-loop dependences. Complete the following table by inserting all types of true-data-dependences, anti-dependences and output dependences for each instruction (I0: None).
I0 FOR: LD F2, A(R1)
I1 FADD F2, F2, F2
I2 FADD F2, F2, F4
I3 SD F2, A(R1)
I4 ADDUI R1, R1, 8
I5 BNE R1, R2, FORLet's consider the previous assembly code to be executed on a CPU with dynamic scheduling based on TOMASULO algorithm with all cache HITS, a single Common Data Bus and: 2 RESERV. STATIONS (RS1, RS2) with 2 LOAD/STORE units (LDU1, LDU2) with latency 4; 2 RESERVATION STATION (RS3, RS4) with 1 FP unit (FPU1) with latency 3; 2 RESERVATION STATION (RS5, RS6) with 1 INT_ALU/BR unit (ALU1) with latency 2. Please complete the table INSTRUCTION | ISSUE | START EXEC | WRITE RESULT | Hazards Type | RSi | UNIT (row I0 given: 1, 2, 6, None, RS1, LDU1). Calculate the CPI.
Show model answer
Dependences: I1 true with I0 for F2, output with I0 for F2; I2 true with I1 for F2, anti with I1 for F2, output with I0 and I1 for F2; I3 true with I2 for F2; I4 anti with I0 and I3 for R1; I5 true with I4 for R1.
| INSTRUCTION | ISSUE | START EXEC | WRITE RESULT | Hazards Type | RSi | UNIT |
|---|---|---|---|---|---|---|
I0 LD F2, A(R1) | 1 | 2 | 6 | None | RS1 | LDU1 |
I1 FADD F2, F2, F2 | 2 | 7 | 10 | RAW with I0 for F2; WAW with I0 (renaming) | RS3 | FPU1 |
I2 FADD F2, F2, F4 | 3 | 11 | 14 | RAW with I1 for F2; WAR with I1, WAW with I0, I1 (renaming) | RS4 | FPU1 |
I3 SD F2, A(R1) | 4 | 15 | 19 | RAW with I2 for F2 | RS2 | LDU2 |
I4 ADDUI R1, R1, 8 | 5 | 6 | 8 | WAR with I0, I3 for R1 (renaming) | RS5 | ALU1 |
I5 BNE R1, R2, FOR | 6 | 9 | 11 | RAW with I4 for R1 | RS6 | ALU1 |
Writes on the CDB at 6, 8, 10, 11, 14 and the memory write at 19: no tie. CPI = 19 / 6 ≈ 3.17.
Every instruction issues one cycle after the previous one: with only one store the two load/store stations suffice. The whole loop is one RAW chain through F2, LD → FADD → FADD → SD; the integer tail runs underneath it. If you name a WAR or a WAW in the Hazards column, add "solved by renaming", so that it cannot be read as a stall.
(Exercise 1, 10 June 2025; registers written without $.) Let's consider the following assembly code containing multiple types of intra-loop dependences. Complete the following table by inserting all types of true-data-dependences, anti-dependences and output dependences for each instruction (I0, I1, I2: None).
I0 FOR: LD F2, A(R1)
I1 LD F4, B(R1)
I2 LD F6, C(R1)
I3 FADD F4, F2, F4
I4 FADD F6, F4, F6
I5 SD F6, A(R1)
I6 ADDUI R1, R1, 8
I7 BNE R1, R2, FORLet's consider the previous assembly code to be executed on a CPU with dynamic scheduling based on TOMASULO algorithm with all cache HITS, a single Common Data Bus and: 2 RESERV. STATIONS (RS1, RS2) with 2 LOAD/STORE units (LDU1, LDU2) with latency 4; 2 RESERVATION STATION (RS3, RS4) with 2 FP units (FPU1, FPU2) with latency 3; 2 RESERVATION STATION (RS5, RS6) with 2 INT_ALU/BR units (ALU1, ALU2) with latency 2. Please complete the table INSTRUCTION | ISSUE | START EXEC | WRITE RESULT | Hazards Type | RSi | UNIT (rows given: I0 = 1, 2, 6, None, RS1, LDU1; I1 = 2, 3, 7, None, RS2, LDU2). Calculate the CPI.
Show model answer
Dependences: I3 true with I0 for F2 and I1 for F4, output with I1 for F4; I4 true with I3 for F4 and I2 for F6, output with I2 for F6; I5 true with I4 for F6; I6 anti with I0, I1, I2 and I5 for R1; I7 true with I6 for R1.
| INSTRUCTION | ISSUE | START EXEC | WRITE RESULT | Hazards Type | RSi | UNIT |
|---|---|---|---|---|---|---|
I0 LD F2, A(R1) | 1 | 2 | 6 | None | RS1 | LDU1 |
I1 LD F4, B(R1) | 2 | 3 | 7 | None | RS2 | LDU2 |
I2 LD F6, C(R1) | 7 | 8 | 12 | Structural: no free load/store RS at 3–6 (RS1 busy until 6) | RS1 | LDU1 |
I3 FADD F4, F2, F4 | 8 | 9 | 13 | RAW with I0 for F2, I1 for F4 (satisfied at issue); WAW with I1 (renaming); issue delayed behind I2; Structural: CDB taken at 12 by I2 | RS3 | FPU1 |
I4 FADD F6, F4, F6 | 9 | 14 | 17 | RAW with I3 for F4, I2 for F6; WAW with I2 (renaming); issue delayed behind I2 | RS4 | FPU2 |
I5 SD F6, A(R1) | 10 | 18 | 22 | RAW with I4 for F6; issue delayed behind I2 | RS2 | LDU2 |
I6 ADDUI R1, R1, 8 | 11 | 12 | 14 | WAR with I0, I1, I2, I5 for R1 (renaming); issue delayed behind I2 | RS5 | ALU1 |
I7 BNE R1, R2, FOR | 12 | 15 | 18 | RAW with I6 for R1; issue delayed behind I2; Structural: CDB taken at 17 by I4 (17 if the branch takes no CDB slot) | RS6 | ALU2 |
CPI = 22 / 8 = 2.75.
Two traps. The third load finds both load/store stations busy at cycles 3–6 and issues only at 7, and in-order issue holds every later instruction behind it although the FP and integer units are idle — two stations per class cannot hold three loads at once. And the single CDB produces two ties, at 12 and at 17: the older instruction writes, the younger slips. The second FP unit changes nothing here, because I4 depends on I3 anyway.
Consider the loop of Exercise 1 of 22 June 2026 (this lesson's loop) on the same CPU, except that the LOAD/STORE class has 3 reservation stations instead of 2 (still 2 load/store units). Calculate the CPI of one iteration.
Show model answer
The store now finds a free station at cycle 5 (ISSUE 5 instead of 7), ADDUI issues at 6 (6 / 7 / 9) and BNE at 7 (7 / 10 / 12, no tie on the CDB any more). But the store still needs F2 from I3, written at 14: START EXEC 15, WRITE RESULT 15 + 4 = 19. CPI = 19 / 7 ≈ 2.71, unchanged.
The extra station removes the structural stall and the CDB tie, but neither was on the critical path LD → FADD → FADD → SD. The typical wrong answer moves the store's WRITE RESULT two cycles earlier together with its ISSUE (17 / 7 ≈ 2.43).
In Tomasulo's algorithm a reservation station is released: (single answer)
Show model answer
Answer 3: a station is busy from ISSUE through WRITE RESULT and reusable from the cycle after the write.
The notes' page 155 suggests answer 2 (the red pen in the section on Execute); every solved table is built on answer 3 (the June 2026 store issues at 7, not at 5).
Which of the following can stall the ISSUE stage of Tomasulo's algorithm? (multiple answers)
Show model answer
Answers 2, 4 and 5. Data hazards never stall issue: RAW waits in the station, WAW and WAR are dissolved by renaming.
The quiz checks that you separate the issue stall of the scoreboard (a WAW, or a busy unit) from Tomasulo's: a missing station or buffer entry and, without speculation, a pending branch — never a data hazard.
True or false: in Tomasulo's algorithm a store instruction writes its result on the Common Data Bus. Motivate your answer.
Show model answer
False. A store waits in its load/store station for the address and the data (the data may arrive by tag over the CDB), then writes memory; it broadcasts nothing because no later instruction reads a register from it. In the June 2026 table the store's WRITE RESULT = 15 + 4 = 19 is its memory write, and it never competes for the bus.
"Motivate your answer" carries its own point in the papers: name the mechanism (no register result, a memory write, no tag anyone waits for) and, if you can, the cycle from a table.
Check yourself
F6.Qi = RS2. RS1, an older writer of F6, now broadcasts ⟨RS1, value⟩, and RS3 holds Qj = RS1. What happens?
Which statements about the Issue stage are true?
Issue is where names are given out; waiting is what the stations do afterwards.
A producer writes its result on the CDB in cycle 10. The earliest cycle in which a consumer in a reservation station can start executing is …
Two instructions finish executing in the same cycle and both need the single CDB. Who writes in that cycle?
Why must issue stay in program order even though execution does not?
Which waits can appear in a Tomasulo exam table?
RAW and structural: everything the Hazards column can hold besides "solved by renaming".
Key take-aways
- Three stages: Issue in program order (decode, allocate a station or stall, copy values or tags, rename the destination through Qi); Execute out of order when Qj = Qk = 0 and the unit is free; Write Result out of order as one ⟨tag, value⟩ broadcast on the CDB.
- Issue stalls when a resource is missing (no free station, a full load/store queue) and, in the basic machine, behind an unresolved branch — never on a data hazard; it is kept in order so that the youngest writer owns each register, not for precise exceptions.
- A station is busy from ISSUE through WRITE RESULT; a unit is busy from START EXEC through WRITE RESULT; a result broadcast at w is usable at w + 1; one CDB carries one result per cycle, oldest first.
- At the broadcast every matching Qj / Qk fills in; the register is written only if its Qi still names the broadcaster — an older writer's value reaches the stations that wait for it and is dropped at the register file (Example 8 done right).
- Stores wait for address and data (the data may arrive on the CDB), keep program order, write memory and never broadcast on the CDB; their WRITE RESULT cell is the end of the memory write.
- Part 1 of the exercise: true = nearest earlier writer of a source, anti = every earlier reader of the destination, output = every earlier writer of it; every pair once per register, R1 included. A dependence belongs to the program, a hazard to the machine.
- June 2026: 19 cycles, CPI = 19 / 7 ≈ 2.71, and every cycle lies on the F2 chain; the hardware overlapped the rest.
What to watch and read
-
Tomasulo Timing Quiz Part 2
Georgia Tech HPCA, Udacityshort clip
A drill with the shape of Exercise 1: pause, fill issue / execute / write for each instruction, then watch the solution clip that follows it. Compare its conventions with the eight of this lesson before you trust a number.
-
Dynamic Scheduling with Tomasulo Algorithm — simulator
Virtual Labs, IIIT Hyderabad
Set the latencies, type the loop body of a paper, step. The reservation stations, the register alias table and the CDB are on screen; use it to check a table you filled by hand.
-
CS252 Lecture 7: Scoreboard, Tomasulo, Register Renaming
John Kubiatowicz, UC Berkeley25 pages
The three stages with their exact conditions on slides, in the same mnemonics and the same three-table layout as the notes — the second opinion when a sentence of the notes looks wrong.
-
Digital Design and Computer Architecture — Lecture 15: Out-of-Order Execution
Onur Mutlu, ETH Zürichfull lecture
Tomasulo as "restricted dataflow": a tag is a promise of a value, the station a waiting room, the bus a loudspeaker. Watch it once the table holds no surprises, for the words of the open question.
-
An Efficient Algorithm for Exploiting Multiple Arithmetic Units
R. M. Tomasulo, IBM Journal, 19679 pages
The abstract and the "common data bus" section: busy bits and tags under their original names, and the machine looking ahead "about eight instructions".