Tomasulo cycle by cycle, and what it fixes compared with the scoreboard

The machine behind the tables, and the four rules

The example is the one Hennessy and Patterson use for Tomasulo's algorithm; the notes run it from page 163 to page 182, a fresh set of tables for every cycle in which something changes. It is also the program the scoreboard ran in lesson 10, with the same latencies, so the two runs compare like with like. Here it is in the papers' mnemonics (the notes write MULTD, SUBD, DIVD, ADDD and number the instructions 1 to 6; the papers count from I0, and so does this lesson):

I0: LD   F6, 34(R2)
I1: LD   F2, 45(R3)
I2: FMUL F0, F2, F4      ; RAW on F2 with I1
I3: FSUB F8, F6, F2      ; RAW on F6 with I0, on F2 with I1
I4: FDIV F10, F0, F6     ; RAW on F0 with I2, on F6 with I0
I5: FADD F6, F8, F2      ; RAW on F8 with I3, on F2 with I1
                         ; WAR on F6 with I3 and I4, WAW on F6 with I0

The notes never state the hardware; you have to read it off their tables, and you must, because one number of the run changes with it. Two load buffers, Load1 and Load2, feed one load unit with a latency of 2 cycles. Two stations ADD1 and ADD2 feed one adder, which does FADD and FSUB in 2 cycles. Two stations MUL1 and MUL2 feed one multiplier that also divides: 10 cycles for FMUL, 40 for FDIV. One common data bus. R2, R3 and F4 hold valid values from the start, so nothing in the window writes them. Fig. 1 is this machine; the fields of a station and the register-status row are the bookkeeping of lesson 11, the three stages are those of lesson 12.

If you want a picture to hang the rules on: issuing an instruction is handing in an order at a cloakroom with numbered tickets. For every input that is not ready you get a ticket number — the tag of the station that will produce it — instead of the value, and you hang your own number on the hook of your destination register: "F6 will be filled by ADD2". When a worker finishes, the number is called once over the loudspeaker, the common data bus: everybody holding that number copies the value, and the hook takes it only if it still shows that number. An older ticket called late is ignored; someone who already collected a value is not disturbed when the hook's label changes. Everything below is this picture with cycle numbers.

The rules that turn the picture into numbers are the stage conditions of lesson 12, read as arithmetic. They are also the conventions of the papers' solved exercises (the pre-filled row LD: 1 / 2 / 6 with latency 4 is these rules at work):

Start = the cycle after the last thing you were waiting for; write = start + latency; the bus serves one result per cycle, oldest first.

Fifty-nine cycles, and the six moments that matter

Before touching the stepper, derive the six rows with the rules alone. This is what you do on the paper: row by row, each row's three numbers depending only on the rows above it and on the units.

1. I0 LD F6, 34(R2) issues at 1 into Load1: R2 is ready, so Vj = v(R2) and A = 34; the register status says F6.Qi = Load1. Nothing to wait for, the load unit is free:

   \[ S_0 = 2, \qquad W_0 = 2 + 2 = 4 . \]

2. I1 LD F2, 45(R3) issues at 2 into Load2 (F2.Qi = Load2). Its operand is ready, but the one load unit is busy with I0 through I0's write cycle 4, so it waits in its buffer:

   \[ S_1 = \max(3,\ 5) = 5, \qquad W_1 = 7 . \]

   With a second load unit it would be \(S_1 = 3\), \(W_1 = 5\) — section 3.

3. I2 FMUL F0, F2, F4 issues at 3 into MUL1: F2 is pending, so Qj = Load2; F4 is ready, so Vk = v(F4); F0.Qi = MUL1. It waits for the tag Load2, which is called at 7:

   \[ S_2 = \max(4,\ 7 + 1) = 8 \] \[ W_2 = 8 + 10 = 18 . \]

4. I3 FSUB F8, F6, F2 issues at 4 into ADD1: F6 is pending from Load1 — but Load1 broadcasts in this very cycle, so by the end of cycle 4 the station holds v(F6) (the notes strike the tag out, page 169); F2 is pending, Qk = Load2; F8.Qi = ADD1:

   \[ S_3 = \max(5,\ 4 + 1,\ 7 + 1) = 8 \] \[ W_3 = 8 + 2 = 10 . \]

   It starts in the same cycle as I2: a different unit, so no conflict.

5. I4 FDIV F10, F0, F6 issues at 5 into MUL2: F0 is pending, Qj = MUL1; F6 has been in the register file since cycle 4, Vk = v(F6); F10.Qi = MUL2. It needs F0, written at 18, and the multiplier, busy with I2 through that same cycle:

   \[ S_4 = \max(6,\ 18 + 1,\ 19) = 19 \] \[ W_4 = 19 + 40 = 59 . \]

6. I5 FADD F6, F8, F2 issues at 6 into ADD2: F8 pending, Qj = ADD1; F2 pending, Qk = Load2; F6.Qi = ADD2 — the second rename of F6; the WAR with I3 and I4 and the WAW with I0 cost nothing. It needs F8 (written at 10), F2 (at 7) and the adder, busy with I3 through 10:

   \[ S_5 = \max(7,\ 11,\ 8,\ 11) = 11 \] \[ W_5 = 11 + 2 = 13 . \]

   Six instructions, last write at 59: \(\text{CPI} = 59 / 6 \approx 9.83\).

Read the three number columns top to bottom. Issue: 1, 2, 3, 4, 5, 6 — in order, without a gap. Start: 2, 5, 8, 8, 19, 11 — out of order, I5 before I4. Write: 4, 7, 18, 10, 59, 13 — out of order again: the instruction issued last finishes fourth, ahead of FMUL, and the one issued fifth finishes last. The bus is used at 4, 7, 10, 13, 18 and 59, never twice in one cycle, so the single CDB cost nothing in this run. And the hazards column holds nothing but RAW and one structural wait: every WAR and WAW of the code is in the last row with the words "solved by renaming".

Cycle 7 is the one to remember. LD F2 finishes and ⟨Load2, v(F2)⟩ goes on the bus once. Four listeners take it in the same cycle: the register file (Qi[F2] = Load2 matches, the value lands, the tag is cleared), MUL1 (Qj = Load2 becomes Vj = v(F2)), ADD1 and ADD2 (Qk becomes Vk). One write, four deliveries — that is what the word common in common data bus buys. It is also why FMUL and FSUB both start in cycle 8: each was waiting for exactly this tag, and they use different units. The bus is a bottleneck for writes, never for starts.

In-order issue, out-of-order execution and completion: issue 1 to 6; start 2, 5, 8, 8, 19, 11; write 4, 7, 18, 10, 59, 13.

Change one assumption, and every number on its chain moves

The notes' number for LD F2 is 5. The classic Berkeley CS252 table of the same example — Hennessy and Patterson's model; the slides are in the resources — says 3. Both are right, for different machines. The notes keep the load unit busy through the write cycle of its instruction and have only one of them; the textbook model lets a second load buffer proceed on its own, as if loads were pipelined through memory. Then LD F2 starts at 3 and writes at 5, and the two cycles travel unchanged down everything that waited for F2:

The finish moves from 59 to 57, and the CPI from 9.83 to 9.5. Nothing else changed: same code, same latencies, one sentence about the hardware. That is the lesson for the paper. The hardware sentence of Exercise 1 — "2 RESERVATION STATIONS with 2 LOAD/STORE units", "1 FP unit" — is not decoration; it decides numbers, and the June 2025 text even pre-fills a second load at 2 / 3 / 7 to make the two-unit convention explicit. When a text leaves an assumption open, write down the one you use next to the table.

From the notes' tables to the paper's table

The papers' Exercise 1 differs from the notes' tables in three ways. The hardware: two stations per class, LOAD/STORE units of latency 4, FP units of 3, an INT_ALU/BR unit of 2, named RS1 to RS6 and LDU1, FPU1, ALU1. The columns: Hazards Type, RSi and UNIT after the three cycle numbers, and "Calculate the CPI" below. The code: a loop body with a store, an ADDUI and a BNE, none of which the notes' example has. (One more difference is spelling only: the 2024 and 2025 texts prefix every register with a dollar sign, $F2; the 2026 text drops it, and so does this notebook.) Three rules cover the newcomers. A store issues to a LOAD/STORE station, starts when its base register and its data are available, and its WRITE RESULT is the end of the memory write — it never uses the CDB, so it never collides with anybody on it. ADDUI and BNE use the integer station and unit. When no station of the class is free, issue waits — and everything behind it waits too — and the paper's word for the hazard is "Structural". The June 2026 exercise filled in is lesson 12. Here is the notes' program on the papers' kind of machine, with latencies chosen so that every rule fires once:

Check the rows the way an examiner does. I2 starts at 8 = I1's write + 1. I4 starts at 15 = I2's write + 1, and FPU2 is free: I2 executed in 8 to 13 and wrote at 14. I5 starts at 12 = I3's write + 1, with FPU1 free since I3's write at 11. Note that I4 now has a second RAW, with I0 for F6: with a load latency of 4, F6 is still pending when I4 issues at 5, so it captures the tag RS1 instead of the value — the hazards column depends on the latencies too. The CDB is used at 6, 7, 11, 14, 15 and 27, all distinct. CPI = 27 / 6 = 4.5. Had I2 and I3 wanted the bus in the same cycle, the older I2 would have written first and I3 would have slipped by one, together with everything waiting for F8 — lesson 14 is made of such collisions.

Before and after: the scoreboard on the same six instructions

Lesson 10 ran this program on the scoreboard — one Integer unit for the loads, one adder, two multipliers and a divider, the same latencies — and the notes print the final table on page 139: LD F6 1-2-3-4, LD F2 5-6-7-8, FMUL 6-9-19-20, FSUB 7-9-11-12, FDIV 8-21-61-62, FADD 13-14-16-22 (issue, read operands, execution complete, write result). Put the two runs on one time axis and every row of the notes' Table 19 becomes a visible difference.

The numbers behind the words, three of them. Forwarding. A scoreboard consumer waits for the register-file write and then spends a cycle of its own reading — results go only to the register file, and no bus carries a tag that a waiting unit could match: LD F2 writes at 8, FMUL reads at 9 and executes from 10. Tomasulo's FMUL executes from 8, the cycle after the write at 7, because the value came down the bus into MUL1. One cycle saved per producer-consumer hop. Renaming. The scoreboard's FADD completed execution at 16 and waited until 21 for FDIV to read F6 — the WAR test at write result. In Tomasulo FDIV copied v(F6) into MUL2 at cycle 5, so FADD's write at 13 answers to nobody: 22 becomes 13. The course schedule's name for this is implicit register renaming: no extra registers, the station tags are the new names. Distributed control. The scoreboard issues only when a unit is free, so LD F2 waits at issue for the Integer unit in cycles 2 to 4 and FADD for the adder in 9 to 12, with everything behind them. Tomasulo issues into a station and lets the wait happen there: 13 cycles to issue become 6.

Now the puzzle of the hook. All of that, and the run is only three cycles shorter. The sum that explains it:

1. Every path through the program ends in FDIV, which needs F0 from FMUL, which needs F2 from LD F2. The chain LD F2 → FMUL → FDIV carries \(2 + 10 + 40 = 52\) cycles of pure latency. No scheduler, static or dynamic, can shorten it: the values do not exist earlier.

2. Tomasulo, one load unit: LD F2 starts at 5 (the unit is busy with LD F6 through cycle 4) and writes at 5 + 2 = 7. Then each link costs its latency plus one CDB hop:

   \[ 59 = (5 + 2) + (1 + 10) + (1 + 40) . \]

3. Scoreboard: LD F2 issues at 5 (the Integer unit is busy through cycle 4), reads at 6, executes at 7, writes at 8; FMUL reads at 9, executes 10 to 19, writes at 20; FDIV reads at 21, executes 22 to 61, writes at 62. Each link costs a read cycle and a write cycle around its latency:

   \[ \begin{aligned} 62 &= (5 + 1 + 1 + 1) \\ &+ (1 + 10 + 1) + (1 + 40 + 1) . \end{aligned} \]

4. \(62 - 59 = 3\): one read-operands cycle saved on each of the three links of the chain, nothing more. The seven cycles of issue stalls and the five cycles of WAR waiting that Tomasulo removed all happened in the shadow of the divide and never touched the finish line. With two load units the chain starts two cycles earlier and the finish is 57 — again the chain, not the scheduler.

So the answer to the hook: the savings went to the instructions off the critical path — FSUB and FADD finish at 10 and 13 instead of 12 and 22 — and to the issue stage, which was free for new work from cycle 7. A program that was one long dependence chain would show the same three cycles and nothing else; a loop whose iterations are independent of each other shows all of it, which is why the next lessons run loops. Dynamic scheduling removes waiting caused by names and by structure; waiting caused by values stays.

What the scoreboard keeps, in the notes' words (page 183): it is simpler to implement, historically foundational, and more hardware-economical for small-scale or embedded designs. Fair: one table and no bus is cheap, and every out-of-order machine since inherits its idea of issuing into a controller and letting the controller decide. But the verdict the notes give and the exam expects is the same — "for high-performance out-of-order execution, Tomasulo's model is the clear winner".

Forwarding saves the read-operands cycle after every producer; renaming removes every wait at write result; the dependence chain stays exactly as long as its latencies.

What Tomasulo breaks, and what fixed it

The notes close with four drawbacks (pages 184 and 185). Each one is a sentence of the open question — "main concepts and benefits" has a cost side too — and each one points at a later lesson.

1. Complex hardware. Stations with operand-tracking logic, a tag field for every register, a bus that broadcasts to every station, and comparators in every station to match the tag: area, control complexity, power. "Scaling the CDB becomes harder with many Functional Units and many RSs" (page 185) — every new listener is one more comparator on the bus.

2. The CDB bottleneck. One result per cycle. In this run the six writes never collided, so the bus cost nothing; the two past papers of lesson 14 are built so that they do, and every collision slips the younger instruction and everything waiting for it. The mitigations the notes name — several CDBs, local bypass networks, a reorder buffer with a central commit stage — are what the next lessons and modern cores use.

3. No precise exceptions. The notes' footnote 6 gives the definition to memorise: in precise exception handling, all instructions before the faulting one must complete, and none after it should affect the architectural state. Tomasulo breaks it twice over, as Fig. 3 shows: completion is out of order, and the register file is written in place at write result. Suppose FDIV, executing from 19 to 58, faults at cycle 30. FADD, which comes after it in the program, wrote F6 at cycle 13; F10 holds nothing new. The state is one no sequential machine could ever have had, and there is nothing to undo it with — "once a value is written to the register file via CDB, it's hard to 'undo' it".

4. Limited scalability. The original design issues one instruction per cycle and has one bus; a superscalar must issue and retire several per cycle, so the CDB and the tag matching must widen with it, and the stations grow with every extra unit. Modern cores keep the idea and change the parts: a register alias table for the renaming, a physical register file for the values, and reorder-buffer commit for the order — "these ideas evolved from Tomasulo" (page 185). Lesson 17 adds the reorder buffer to a Tomasulo machine and shows how a result like FADD's write at 13 is made to wait its turn before it reaches the register file.

Tomasulo's costs: comparators everywhere, one result per cycle on the bus, no precise exceptions, no easy way to go wide — and the reorder buffer is the answer to the third.