Tomasulo's algorithm: Worked examples — Hardware deep dive

This page is the "throw everything at it" companion to Tomasulo's algorithm. We already know the three stages (Issue, Execute, Write Result) and the three structures (reservation stations, register tags, the Common Data Bus). Here we grind through every kind of situation the algorithm can meet, one worked example per case, so you never hit a scenario you have not seen.

The symbols we use everywhere (restated in full)

This page is self-contained: every symbol below is defined here before we ever use it, so you never need to flip back to the parent note.

Definition Reservation-station fields (restated in situ)

A reservation station (RS) is a small waiting-slot in front of a functional unit where an instruction sits until its inputs are ready. Each RS entry holds these fields:

== $V_{j}$ , $V_{k}$ == ::: the actual numeric values of the two source operands, once we have them. "V" for value.
== $Q_{j}$ , $Q_{k}$ == ::: tags — the name of the RS that will produce a missing operand. "Q" for queue-position / who-owes-me. If $Q_{j} =$ NULL, then $V_{j}$ already holds a real value and we are not waiting on anyone.
Op ::: the operation (MUL, ADD, …). busy ::: whether the slot is occupied.
The RS's own name (e.g. Add1) is the tag it will broadcast when it finishes.

The execute condition (the one rule that starts execution). An instruction in a reservation station may begin executing exactly when both operands are present: $Q_{j} = NULL \land Q_{k} = NULL .$ Why both? You cannot compute $A ⋆ B$ while $B$ is still an IOU. The instant the last missing operand arrives on the CDB, this condition flips true and execution can be scheduled.

The timing model we use everywhere

Cycle counts are meaningless unless everyone agrees "when does a stage happen." So we fix one simple model and use it for every example below. Whenever you see a cycle number, it obeys these rules.

Definition Our fixed pipeline timing model

Issue takes 1 cycle. An instruction issued in cycle $c$ occupies its reservation station starting that cycle.
Execute begins the cycle after both operands are present ( $Q_{j} = Q_{k} =$ NULL). If an operand is captured off the CDB in cycle $c$ , execution's first cycle is $c + 1$ . An op with latency $L$ occupies the functional unit for cycles $c + 1, \dots, c + L$ .
Write Result takes its own 1 cycle, the cycle after the last execute cycle. An op that finishes executing in cycle $f$ broadcasts on the CDB in cycle $f + 1$ .
A value captured off the CDB in cycle $w$ can free a waiting instruction so that it starts executing in cycle $w + 1$ .
The CDB carries at most one result per cycle (one write port). If two want it, an arbiter picks by program order and the loser waits.

So the shortest possible life of an op is: Issue @ $c$ , Execute @ $c + 1 \dots c + L$ , Write @ $c + L + 1$ . Concretely: an op with latency $L$ issued in cycle $c$ executes cycles $c + 1, \dots, c + L$ and writes in cycle $c + L + 1$ .

The scenario matrix

Before defining anything new, let's recall three plain-word labels for the ways one instruction can clash with another. A hazard is just "a reason instruction B might get the wrong answer if we let it run too early."

Here is the full grid of cases we will cover. Each cell names the "corner of the space," and the example number that lands in it.

#	Case class	What is being stressed
E1	Pure RAW chain	The one hazard you cannot remove
E2	WAW clash	Two writes to one register; late write wins
E3	WAR "false" clash	Earlier read must survive a later write
E4	Zero dependency	Instruction with both operands ready — issues & runs instantly
E5	Degenerate broadcast	A result computed but ignored by every listener
E6	Limiting behaviour	Long chain vs. wide independent code — where ILP saturates
E7	Real-world word problem	Load/store + memory-disambiguation
E8	Exam twist	CDB structural conflict: two units finish same cycle
E9	Control hazard + commit	Branch misprediction and reorder-buffer commit

Cell coverage check: RAW → E1, E6, E8. WAR → E3. WAW → E2, E5. No-dependency/zero → E4. Degenerate/ignored value → E5. Limiting → E6. Word problem/memory → E7. Structural/exam → E8. Control + commit → E9. Every cell is hit.

E1 — Pure RAW chain (the hazard you cannot remove)

Worked example Statement

Assume MUL takes 4 cycles, ADD takes 2. Issue is 1 instruction/cycle.

1. MUL R1, R2, R3
2. ADD R4, R1, R5   # reads R1 — RAW on inst 1

With R2=6, R3=7, R5=1. On what cycle does ADD start executing, and what is R4?

Forecast: Guess now — does ADD start right after issue, or does it have to wait? For how many cycles?

Cycle 1 — MUL issues to Mult1. Both operands ready ( $V_{j} = 6, V_{k} = 7$ , $Q_{j} = Q_{k} =$ NULL). Set R1.tag = Mult1. Why this step? At Issue we snapshot whatever the register file currently holds; R1's tag now says "wait for Mult1."
Cycle 2 — ADD issues to Add1. R5 is ready ( $V_{k} = 1$ ), but R1's tag is Mult1, so ADD stores $Q_{j} = Mult1$ , $V_{j}$ empty. Why this step? ADD copies the tag, an IOU — it doesn't block, it just remembers who owes it a number.
Cycles 2–5 — MUL executes (issued @1, so execute is cycles $2$ through $5$ , latency 4). ADD cannot run: $Q_{j} \neq =$ NULL. Why this step? This is the one wait we can never skip — the data truly does not exist yet.
Cycle 6 (write) — MUL broadcasts $⟨ Mult1, 42 ⟩$ (execute finished @5, write @6, i.e. $1 + 4 + 1$ ). Add1 sees Mult1, sets $V_{j} = 42$ , clears $Q_{j}$ . Why this step? The CDB delivers the number the instant it is written; ADD captures it this same cycle.
Cycle 7 — ADD executes (starts the cycle after capture) with $42 + 1 = 43$ ; executes cycles 7–8; result $R 4 = 43$ broadcast at cycle 9 ( $6 + 1$ start, then $2 + 1$ ).

Verify: MUL: $6 \times 7 = 42$ , written cycle 6. ADD: $42 + 1 = 43$ , written cycle 9. RAW forced a real wait — ADD could not begin before MUL's result was broadcast. That is correct; the data physically had to arrive.

E2 — WAW clash (two writes to one register)

Worked example Statement

1. MUL R1, R2, R3   # 4 cycles, R1 ← 42
2. SUB R1, R6, R7   # 2 cycles, R1 ← 12  (WAW on inst 1!)

R2=6,R3=7,R6=20,R7=8. After both finish, what is R1, and does MUL's result reach R1?

Forecast: Both write R1. Which value survives — 42 or 12? Does MUL's broadcast overwrite SUB's answer?

Cycle 1 — MUL issues to Mult1. R1.tag = Mult1. Execute cycles 2–5, write @6. Why? R1 is now promised to Mult1.
Cycle 2 — SUB issues to Add1, operands ready. R1.tag = Add1 overwrites Mult1. Execute cycles 3–4, write @5. Why this step? The register file only remembers its latest producer. This overwrite is the renaming that dissolves WAW — R1 now points to the newer writer.
Cycle 5 — SUB writes, broadcasts $⟨ Add1, 12 ⟩$ . R1.tag is Add1, so R1 latches $12$ , tag → NULL. Why this step? A broadcast is latched by a register only if that register's tag still names the broadcasting RS. R1's tag is Add1 and this is Add1's broadcast, so the match holds and 12 lands in R1 — this is the write that should win.
Cycle 6 — MUL writes, broadcasts $⟨ Mult1, 42 ⟩$ . R1.tag is now NULL (≠ Mult1), so R1 ignores it. Why this step? Same match rule, now failing: the tag was overwritten, so the stale earlier write vanishes harmlessly — exactly the WAW guard.

Verify: Final $R 1 = 12$ (the last writer in program order). $42$ was computed but discarded — exactly what a correct in-order machine would produce. No stall was needed.

Figure s01 — E2's WAW guard. The mint arrow is SUB's broadcast at cycle 5: R1's tag is Add1, the tags match, so 12 is latched. The dashed coral arrow is MUL's later broadcast at cycle 6: R1's tag is already NULL, the tags mismatch, so 42 is dropped. Read the two "tag matches / tag ≠" labels — they are the entire WAW mechanism in one picture.

E3 — WAR clash (earlier read must survive a later write)

Worked example Statement

1. DIV R1, R2, R3   # 10 cycles (slow), reads R2,R3
2. ADD R2, R6, R7   # 2 cycles, WRITES R2 (WAR on inst 1's read of R2)

R2=100,R3=4,R6=5,R7=5. Does ADD overwriting R2 corrupt DIV's dividend?

Forecast: DIV reads R2=100 but is still crunching when ADD wants to write R2=10. Does DIV end up dividing 10 or 100?

Cycle 1 — DIV issues. R2 and R3 are ready now, so DIV copies the values $V_{j} = 100, V_{k} = 4$ into Mult1. R1.tag=Mult1. Why this step? This is the crucial line. Tomasulo reads operand values at Issue, not later. DIV owns a private copy of 100.
Cycle 2 — ADD issues to Add1, ready. R2.tag=Add1. ADD executes cycles 3–4, writes @5. Why? ADD does not touch DIV's copy; it only changes the register file's R2.
Cycle 5 — ADD writes, broadcasts $⟨ Add1, 10 ⟩$ ; R2 becomes 10 in the register file. Why this step? DIV's $V_{j}$ is a separate buffer — the register-file change cannot reach it.
Cycle 12 — DIV writes. DIV issued @1, so it executes cycles 2–11 (latency 10), and its Write Result is the following cycle: $1 + 10 + 1 = 12$ . It used its snapshot $100/4 = 25$ . Why this step? Applying the model exactly: last execute cycle is 11, and Write Result is its own cycle after that, so cycle 12.

Verify: $100/4 = 25$ (correct — used the old R2), written cycle 12 ( $1 + 10 + 1$ ). The register file's R2 is now $5 + 5 = 10$ . The WAR "false" hazard never blocked anything because reading values at Issue is the rename. This is Tomasulo's edge over scoreboarding, which would have stalled ADD.

E4 — Zero dependency (both operands ready = instant run)

Worked example Statement

1. ADD R4, R6, R7   # 2 cycles; R6,R7 both ready, nothing before it writes them

R6=20,R7=8. On what cycle does it execute, and on what cycle does it write?

Forecast: With zero dependencies, is there any wait between Issue and Execute? When does the result appear on the CDB?

Cycle 1 — issues to Add1, $V_{j} = 20, V_{k} = 8$ , both $Q$ =NULL. Why? No tag to copy — the register file holds real values, not IOUs.
Cycles 2–3 — executes (execute condition already true at issue, so execute starts the very next cycle). Why this step? This is the "zero input" case: with no producer to wait for, the only cost is the fixed stages themselves.
Cycle 4 — writes. Last execute cycle is 3, so Write Result is its own cycle after that: cycle $1 + 2 + 1 = 4$ . It broadcasts $⟨ Add1, 28 ⟩$ ; R4 latches 28, tag → NULL. Why this step? Even with no dependents to hear it, the Write stage still runs — every op must pass through Issue, Execute, and Write. This is the stage the other examples show and E4 must show too.

Verify: $20 + 8 = 28$ , written cycle 4. Latency = issue (1) + execute (2) + write (1) = 4 cycles total, with no dependency stall. This is the best case and the baseline the others are measured against.

E5 — Degenerate broadcast (a value computed then ignored)

Worked example Statement

1. MUL R1, R2, R3   # 4 cyc, R1 ← 42
2. SUB R1, R6, R7   # 2 cyc, R1 ← 12  (renames R1)
3. ADD R4, R1, R5   # reads the RENAMED R1

R2=6,R3=7,R6=20,R7=8,R5=1. Which R1 does ADD consume — 42 or 12? Does MUL's 42 ever get used?

Forecast: ADD reads R1. But R1 was rewritten. Whose 42/12 flows into ADD?

Cycle 1 — MUL issues to Mult1, R1.tag=Mult1. Execute 2–5, write @6. Why this step? MUL is the first writer of R1, so R1's tag is set to point at Mult1 at Issue.
Cycle 2 — SUB issues to Add1, operands ready, R1.tag=Add1 overwrites Mult1. Execute 3–4, write @5. Why this step? SUB is a later writer of R1; the register file always keeps the newest producer's tag, so any subsequent reader will bind to Add1, not Mult1.
Cycle 3 — ADD issues to Add2. It reads R1's current tag Add1, so $Q_{j} = Add1$ ; $V_{k} = 1$ from R5. Why this step? ADD binds to the newest producer of R1 — the renamed one (Add1) — never the stale MUL.
Cycle 5 — SUB writes, broadcasts $⟨ Add1, 12 ⟩$ : ADD's $Q_{j}$ clears, $V_{j} = 12$ . ADD now executes cycles 6–7, writes @8. Why this step? The CDB match on Add1 delivers the correct, renamed value straight into ADD's reservation station.
Cycle 6 — MUL writes, broadcasts $⟨ Mult1, 42 ⟩$ : no RS and no register is listening for Mult1. The 42 dies unused. Why this step? This is the degenerate corner — a perfectly valid result with zero consumers. Broadcasting-to-all handles "0 listeners" the same as "5 listeners," so nothing special is needed.

Verify: ADD computes $12 + 1 = 13$ . The MUL result 42 is computed but consumed by nobody — matching sequential semantics, where SUB's 12 shadows MUL's 42 before ADD ever reads R1.

E6 — Limiting behaviour (where parallelism saturates)

Worked example Statement

Compare two 4-instruction programs, each op = 2 cycles, 1 issue/cycle, 1 CDB write/cycle. Use the fixed timing model (Issue @ $c$ , Execute @ $c + 1 \dots$ , Write @ $c + 3$ for a 2-cycle op). (A) Dependent chain: each reads the previous result.

ADD R1,R2,R3 ; ADD R4,R1,R5 ; ADD R6,R4,R7 ; ADD R8,R6,R9

(B) Independent: no shared registers.

ADD R1,R2,R3 ; ADD R4,R5,R6 ; ADD R7,R8,R9 ; ADD R10,R11,R12

On what cycle does the last result get written in each?

Forecast: How much can out-of-order help chain (A)? Does (B) finish in a quarter of the time?

Chain (A): I1 issues @1, executes 2–3, writes @4 (frees Add1). I2 needs I1's value, captures @4, execute 5–6, write @7. I3 captures @7, execute 8–9, write @10. I4 captures @10, execute 11–12, write @13. Why this step? Each write is exactly the previous write + 3 (op latency 2 + 1 write cycle). RAW is irreducible — out-of-order-execution cannot beat a true data chain. This is the limit: latency grows linearly with chain length. At most one ADD is busy at a time here, so two slots is plenty.
Independent (B): I1 issues @1 (Add1), I2 @2 (Add2), I3 @3 (Add1 is already free? no — Add1 writes @4). Track slots: I1 uses Add1 (busy c1–4), I2 uses Add2 (busy c2–5), I3 must wait for a free slot — Add1 frees at c4, so I3 takes Add1, issues c4 (one-cycle issue slip), exec 5–6, write @7; I4 takes Add2 (frees c5), issues c5, exec 6–7, write @8. Last write @8. Why this step? Here the limit is structural: only two RS slots, so the third and fourth ADDs wait for a slot to free. With the fixed 2-slot hardware, independent code is capped by RS count, not by data.

Verify: Chain finishes at cycle 13; independent at cycle 8. Independent is faster but not 4× faster — the fixed 2 RS slots (and the 1-wide CDB) serialise the pipeline. Lesson: ILP is bounded by whichever is scarcer, true dependencies or hardware resources (RS slots, CDB).

Figure s02 — E6 timelines under our fixed model with exactly two RS slots. Top (lavender): the dependent chain — each box's write cycle is the previous +3, so the last write slides all the way to cycle 13. Bottom (mint): the independent code — only two slots exist, so I3/I4 wait for a slot to free and the last write lands at cycle 8. Compare the two rightmost "last=" labels: the gap (13 vs 8) is exactly the cost of a true data chain versus a fixed-resource limit.

E7 — Real-world word problem (loads, stores, memory ordering)

Worked example Statement

A graphics loop does:

1. L.D  F2, 0(R1)     # load pixel from address in R1 (say 4 cycles)
2. MUL  F4, F2, F0    # scale it (RAW on F2)
3. S.D  F4, 0(R1)     # store result back to SAME address

Can the store (3) be reordered before the load (1) or before it has F4?

Forecast: Store and load touch the same memory address. Is this a "hazard" the register tags can see?

Load issues to Load1, computes address [R1], executes; result F2 broadcast on CDB with tag Load1. Why? Loads behave like any producer: their tag Load1 renames F2.
MUL issues, $Q_{j} = Load1$ , waits, then executes $F 2 \times F 0$ . Why this step? Normal RAW through F2 — handled by tags, no memory involved.
Store issues: its data operand F4 gets tag Mult1; its address uses R1. The store must not commit before the load's address is known, because they may alias. Why this step? Register tags see register dependencies, not memory ones. Same-address load/store is a memory dependency invisible to $Q_{j} / Q_{k}$ . We need memory-disambiguation: hold the store until earlier load/store addresses are computed and compared.

Verify: Order must be Load → (address-compare) → Store. With R1=address of pixel, value 200 (F0=0.5): F2=200, F4=100, memory finally holds 100 at [R1]. If the store had bypassed the load, it would have read the old pixel or written garbage — a correctness bug tags alone cannot catch.

E8 — Exam twist (CDB structural conflict)

Worked example Statement

Two independent instructions both finish executing on the same cycle and both want the CDB:

1. ADD R1,R2,R3   # finishes execute at cycle 4
2. MUL R4,R5,R6   # ALSO finishes execute at cycle 4

R2=2,R3=3,R5=6,R6=5. There is exactly one CDB. What happens, and how does it change the timeline?

Forecast: Two winners, one bus. Does one result get lost? Delayed? How is the tie broken?

Both finish executing at cycle 4, so both request the Write-Result cycle (cycle 5 under our model, $f + 1$ ). But only one CDB slot exists. Why this step? Execution units are separate, but the broadcast is a shared, 1-per-cycle resource — a structural hazard on the CDB.
Cycle 5 — arbiter grants the CDB to the older instruction (program order: ADD, inst 1). ADD broadcasts $⟨ Add1, 5 ⟩$ . Why this step? A fixed priority (program order) guarantees a deterministic, deadlock-free choice — no result is ever dropped, one is merely deferred.
Cycle 6 — MUL broadcasts $⟨ Mult1, 30 ⟩$ , one cycle late. Its result sat in the multiply unit's output latch through cycle 5 waiting for the bus. Why this step? The unit holds its finished value in an output latch until the bus frees; nothing is recomputed or lost, only postponed.
Downstream effect: any instruction waiting on Mult1 captures 30 in cycle 6 instead of 5, so its execute start slips to cycle 7 — the one-cycle delay ripples exactly one step down the dependency chain, no further. Why this step? A single-cycle CDB stall propagates at most one cycle to each direct consumer; it does not compound, which is why one extra CDB usually suffices.

Verify: ADD $= 2 + 3 = 5$ , written cycle 5. MUL $= 6 \times 5 = 30$ , written cycle 6 (arbiter deferred it one cycle). Correctness intact; only timing slips by one cycle. Real machines add multiple CDBs precisely to reduce this bottleneck — echoing the E6 limit.

Figure s03 — E8 arbitration. Both ADD (mint) and MUL (lavender) finish at cycle 4 and reach for the single butter-coloured CDB. The solid mint arrow labelled "c5 (priority)" wins by program order; the dashed lavender arrow labelled "c6 (stalls 1)" is deferred exactly one cycle. Follow the arrow into "listeners": the one-cycle slip is passed on to whoever waits for Mult1, and stops there.

E9 — Control hazard and commit (branch + reorder buffer)

Plain-Tomasulo as described so far broadcasts results and lets them change registers immediately. That is a problem the moment a branch appears: we may have executed instructions from the wrong path. Real machines fix this by adding a reorder buffer (ROB) so results commit in program order and speculative work can be thrown away.

Worked example Statement

1. SUB R1, R6, R7    # 2 cyc -> R1
2. BEQZ R1, skip     # branch: taken if R1 == 0
3. ADD R4, R5, R8    # speculative (guessed not-taken)
skip:
4. MUL R9, R2, R3    # correct target if branch taken

R6=8,R7=8 (so R1=0, branch is taken), but the predictor guessed not-taken and ran inst 3. What happens to ADD, and what does the register file end up holding?

Forecast: ADD already executed on a wrong guess. Does R4 get corrupted?

SUB executes, R1 renamed via ROB; its value 0 will commit in order. Why? Every result now lands in the ROB first, not the register file — so it can be undone.
BEQZ predicted not-taken; ADD issues and executes speculatively, its result parked in an ROB entry (not written to R4 yet). Why this step? The ROB lets ADD compute without committing — speculation with a safety net.
Branch resolves: R1 = 0, so it IS taken → misprediction. Every ROB entry after the branch (ADD) is squashed; ADD's reservation station and any tag it set for R4 are flushed. Why this step? Squashing before commit means the wrong-path ADD never touches architectural state — the control hazard is erased.
Fetch redirects to skip; MUL runs and commits in order. Why this step? Only correct-path instructions ever reach commit, so program order and correctness are preserved.

Verify: $R 1 = 8 - 8 = 0$ ⇒ branch taken (predicted wrong). ADD's speculative result ( $5 + 8 = 13$ ) is discarded, so R4 is unchanged. MUL $= 2 \times 3 = 6$ commits to R9. Final architectural state matches the correct (taken) path exactly — the ROB commit stage is what makes Tomasulo safe under branches.

Recall Self-test

Which hazard forces a genuine wait? ::: RAW (Read-After-Write) — true data dependency. Under our timing model, when does an op with latency $L$ issued in cycle $c$ write its result? ::: In cycle $c + L + 1$ (Write-Result is its own cycle after the last execute cycle). Why does E2's MUL result get ignored? ::: R1's tag was overwritten to Add1; the "latch only if tag matches" rule drops the stale Mult1 broadcast. In E3, why isn't DIV corrupted by the later write to R2? ::: DIV copied R2's value at Issue into $V_{j}$ ; register-file changes can't reach that private copy. Its write lands at cycle 12 ( $1 + 10 + 1$ ). What limits speed in E6's independent code? ::: The fixed 2 RS slots (and the single CDB) — a structural, not data, limit. What hazard is invisible to register tags (E7)? ::: A memory (same-address load/store) dependency — needs memory-disambiguation. How does the reorder buffer undo a mispredicted branch (E9)? ::: It squashes every entry after the branch before commit, so speculative results never reach the architectural registers.

See also: Tomasulo's algorithm · reorder-buffer · common-data-bus · scoreboarding · instruction-level-parallelism.