Tomasulo's algorithm: Visual walkthrough — Hardware deep dive

We will walk this exact program the whole way through:

1. MUL  R1, R2, R3    # takes 5 cycles
2. ADD  R4, R1, R5    # takes 2 cycles, needs R1
3. SUB  R1, R6, R7    # takes 2 cycles, WRITES R1 again
4. DIV  R8, R1, R9    # takes 40 cycles, needs the NEW R1

Starting values: $R 2 = 2, R 3 = 3, R 5 = 10, R 6 = 20, R 7 = 8, R 9 = 2$ .

Step 0 — The three objects, drawn once

WHAT. Before any instruction moves, meet the pieces. A register (like R1) is a labelled box that can hold either a real number or a sticky note that says "someone else is bringing my value." A reservation station (RS) is a waiting seat bolted to a functional unit; it has a name like Mult1 or Add2. The common data bus (CDB) is a single wire that every box and every seat can hear.

WHY these three and nothing else? Because the whole trick of Tomasulo is to stop instructions fighting over register names and instead make them fight over seats. To do that we need (a) somewhere to sit and wait — the seat; (b) a way to say "I'm waiting on seat X" — the tag; and (c) a way for seat X to shout "done, here's the number!" — the bus. Remove any one and the trick collapses.

PICTURE. Read the legend once; every later figure reuses these exact shapes and colours.

This link matters throughout: renaming is the hardware version of the naming problem in data-hazards, and Tomasulo is the classic form of out-of-order-execution.

Step 1 — Cycle 1: MUL grabs a seat and hangs a tag on R1

WHAT. We issue MUL R1, R2, R3. There is a free multiply seat, Mult1, so MUL sits in it. We read its sources R2 and R3 — both hold real numbers ( $2$ and $3$ ), so we copy them straight into the seat as $V_{j} = 2, V_{k} = 3$ . Then we do the crucial move: we hang a sticky note on the destination R1 that reads "Mult1 will fill me."

WHY. Reading operands now is why WAR hazards vanish: MUL has physically copied $2$ and $3$ into its own seat, so nothing that later overwrites R2 or R3 can hurt it. Tagging R1 is why future readers of R1 will know who to wait for — not the name "R1", but the seat Mult1.

PICTURE. The sticky note (plum) lands on R1; the seat is full and ready.

$Mult1 : copied from R 2 V_{j} = 2 copied from R 3 V_{k} = 3 nothing to wait for Q_{j} = NULL nothing to wait for Q_{k} = NULL$

$R 1. tag \leftarrow Mult1 (“my value is coming from seat Mult1”)$

Both tags are NULL, so MUL starts computing immediately — it will finish at cycle $1 + 5 = 6$ .

Step 2 — Cycle 2: ADD needs R1, so it copies the IOU

WHAT. We issue ADD R4, R1, R5 into seat Add1. Now we read its sources. R5 holds a real number ( $10$ ) → copy it: $V_{k} = 10$ . But R1 is not a number right now — it wears the sticky note Mult1. So instead of a value, ADD copies the note: $Q_{j} = Mult1$ . Finally, tag ADD's own destination: R4.tag ← Add1.

WHY. This is the heart of renaming. ADD does not need to know the register named R1; it needs the number MUL is going to produce. By storing $Q_{j} = Mult1$ , ADD has written itself a to-do: "wake me when seat Mult1 shouts." It answers "who produces the value I need?" instead of "which name holds it?"

PICTURE. Note the teal arrow from Add1's $Q_{j}$ slot pointing back at seat Mult1 — that arrow is the true dependency, made physical.

$Add1 : waiting on that seat Q_{j} = Mult1 value not here yet V_{j} = \emptyset R 5 was ready Q_{k} = NULL, V_{k} = 10$

Add1 has $Q_{j} \neq = NULL$ , so by the Step 0 rule it may not execute yet. It waits.

Step 3 — Cycle 3: SUB overwrites R1's tag — the false dependency dies here

WHAT. We issue SUB R1, R6, R7 into seat Add2. Its sources R6, R7 are both real numbers ( $20$ and $8$ ) → $V_{j} = 20, V_{k} = 8$ , both tags NULL. Now the loaded moment: SUB writes R1, so we overwrite the sticky note on R1. It used to say Mult1; now it says Add2.

WHY — this is the whole point of the page. In program order MUL writes R1 before SUB does. A naive machine would force SUB to wait for MUL to avoid clobbering R1 (a WAW hazard) — a dependency that exists only because of the shared name R1, not because of any real data. Tomasulo refuses. Because R1 is just a box wearing a note, overwriting the note is free and instant. The old note Mult1 is now orphaned: nobody's box points at it anymore (though Add1 still privately remembers it — see below). So:

Since $Q_{j} = Q_{k} = NULL$ , SUB executes this very cycle, in parallel with the still-running MUL.
The name collision on R1 is resolved by two different seat names, Mult1 and Add2. That is register renaming.

PICTURE. Watch the sticky note on R1 get crossed out and replaced (plum → replaced plum). The orphaned tag Mult1 is greyed — still remembered inside Add1, forgotten by R1.

$R 1. tag : Mult1 SUB issues Add2$

Step 4 — Cycle 4: DIV waits on the NEW R1, automatically

WHAT. Issue DIV R8, R1, R9 into seat Mult2. Read sources: R9 is a number ( $2$ ) → $V_{k} = 2$ . R1 currently wears the note Add2 (put there by SUB last cycle), so DIV copies that note: $Q_{j} = Add2$ . Tag its destination: R8.tag ← Mult2.

WHY. Look what renaming did for free: DIV wanted "the R1 that SUB produces," and by simply reading whatever note is currently on R1, it captured exactly Add2 — never Mult1. We did not write any special logic to route this. The single sticky-note-per-register discipline guarantees each reader latches onto the most recent producer. This is the same disambiguation idea a reorder-buffer and scoreboarding must also solve, but here it falls out of one rule.

PICTURE. The teal dependency arrow from Mult2's $Q_{j}$ points at Add2, not Mult1.

$Mult2 : the NEW R1 Q_{j} = Add2 R 9 ready Q_{k} = NULL, V_{k} = 2 R 8. tag \leftarrow Mult2$

Mult2 has $Q_{j} \neq = NULL$ → it waits for Add2 to finish.

Step 5 — Cycle 5: SUB broadcasts on the CDB — two listeners react differently

WHAT. SUB started at cycle 3, takes 2 cycles, so at cycle 5 it finishes and shouts on the CDB: $⟨ Add2, 20 - 8 = 12 ⟩$ Every seat and every box hears it. Two of them care:

Seat Mult2 had $Q_{j} = Add2$ → it grabs $12$ into $V_{j}$ and clears the tag: $Q_{j} \leftarrow NULL$ .
Box R1 had note $= Add2$ → it grabs $12$ as its real value and tears off the note.

WHY broadcast to everyone at once? Because at issue time nobody knew how many future instructions would need Add2's result — could be zero, could be five. A single shout on one shared wire reaches all of them in one cycle without maintaining a list. This one wire is the common-data-bus, and it is the throughput bottleneck (only one result can be shouted per cycle).

PICTURE. One orange pulse leaves Add2; two teal arrows fan out — into Mult2's slot and into box R1.

$After the shout: Mult2 . Q_{j} = NULL, V_{j} = 12 R 1 = 12 (note gone)$

Now Mult2 has both operands NULL → DIV starts executing at cycle 5, will finish at $5 + 40 = 45$ .

Step 6 — Cycle 6: MUL broadcasts — and R1 correctly ignores it

WHAT. MUL started at cycle 1, takes 5 cycles → finishes at cycle 6 and shouts: $⟨ Mult1, 2 \times 3 = 6 ⟩$ Who reacts?

Seat Add1 had $Q_{j} = Mult1$ (from Step 2) → grabs $6$ into $V_{j}$ , clears the tag. Add1 now has both operands → ADD starts executing.
Box R1? Its note now says Add2 — actually the note is already gone (torn off in Step 5). Either way R1 \ne \text{Mult1}$, so **R1` ignores the shout.**

WHY this is the payoff. This is the exact moment the WAW hazard is proven harmless. MUL's result 6 was the stale value of R1 in program terms; letting it into the box would be a bug. The tag-match check (does my note equal the shouting seat?) filters it out automatically. Meanwhile the legitimate consumer, ADD, still receives 6 — because it copied the IOU, not the register name. Data goes exactly where the program's real dataflow says it should, and nowhere else.

PICTURE. Orange pulse from Mult1; a teal arrow lands in Add1; a red crossed-out arrow shows R1 refusing the value.

$R 1. note = \emptyset \neq = Mult1 \Rightarrow R 1 discards 6, Add1 . V_{j} \leftarrow 6 (ADD may run)$

The remaining traffic is bookkeeping: ADD finishes at cycle 8 and writes R4=16; DIV finishes at cycle 45 and writes R8 = 12/2 = 6. Every hazard has already been dissolved.

Step 7 — The degenerate cases, so nothing surprises you

WHAT. Three corner situations the walkthrough brushed past. Each gets its own frame in the summary figure below.

No free seat (structural hazard). If, at Issue, every seat of the needed functional unit is busy, the instruction cannot get a slot. It stalls at Issue — it does not skip ahead. This is the only stall Tomasulo keeps.
Both operands already ready. If neither source wears a note (like SUB in Step 3), both $Q$ fields are NULL at issue → the instruction can execute the same cycle it issues. No waiting.
A producer that nobody listens to. In Step 6, seat Mult1 shouted but its result was needed only by Add1 (a consumer), and its destination box R1 had moved on. This is normal and safe: broadcasting is unconditional, reacting is by tag-match, so an unwanted result simply finds no listeners.

WHY show all three? Because a reader who only saw the happy path would panic the first time a seat is full, or the first time a broadcast seems to "go nowhere." These aren't errors — they're designed behaviour.

PICTURE. Three tiny panels: (a) a full seat block turns instructions away; (b) an instruction issuing and running in one cycle; (c) a shout with no listeners.

The one-picture summary

WHAT. Everything above, compressed into one timeline. The horizontal axis is cycle number; each instruction is a coloured bar (issue → execute → write). Two events are starred: the tag-overwrite on R1 at cycle 3 (where the false dependency dies) and the ignored broadcast at cycle 6 (where the WAW hazard is proven harmless). The teal arrows show the real dataflow — Mult1 → Add1 and Add2 → Mult2 — which never touch each other, which is exactly why MUL+SUB+DIV overlap in time.

Recall Feynman retelling — say it out loud in plain words

Imagine every register is a box that can hold either a number or a claim-ticket. When an instruction wants to write a result, it doesn't touch the box's number — it just staples a fresh claim-ticket onto the box saying "seat number so-and-so will bring your value." Any later instruction that reads that box copies the ticket, not the box's name, and then sits down and waits.

When a seat finishes, it doesn't hand its result to a specific register — it stands up and shouts its seat number and its number to the whole room. Everyone checks their ticket. If your ticket matches the shout, you take the value and throw the ticket away; otherwise you ignore it and keep waiting.

Now the magic: when two instructions both write the same register (our MUL and SUB on R1), the second one just staples a newer ticket over the old one. The old seat still finishes and still shouts — but the box's ticket has changed, so the box ignores the stale shout. Meanwhile the instructions that genuinely needed the old value already kept their own copy of the old ticket, so they still get served. Nobody fought over the name R1; they fought over seats, and there were plenty of seats. That is the entire algorithm.

Recall Self-test

Why does SUB start executing the same cycle it issues (cycle 3)? ::: Both its sources R6, R7 hold real numbers, so $Q_{j} = Q_{k} = NULL$ at issue — the execute condition is already met. At cycle 6 MUL shouts <Mult1, 6>. Why doesn't R1 update? ::: R1's tag was overwritten to Add2 at cycle 3; the shout's tag is Mult1, so the tag-match fails and R1 discards the value. Which false (name-based) dependency is eliminated when SUB overwrites R1's tag? ::: The WAW hazard between MUL and SUB — both write R1, but two different seat names (Mult1, Add2) keep their results separate. What is the one stall Tomasulo keeps? ::: A structural hazard — if no reservation station of the needed functional unit is free, the instruction stalls at Issue.

Related depth: this decoupling is what raises instruction-level-parallelism; the load/store version of the same tag trick is memory-disambiguation; and a Hinglish retelling lives at 5.3.03 Tomasulo's algorithm (Hinglish).