Worked examples — Out-of-order execution — Tomasulo algorithm (conceptual)

This page is a drill hall. The parent note taught you the machinery — three stages (Issue, Execute, Write), reservation stations (RS), tags, and the Common Data Bus. Here we run that machinery through every kind of situation it can meet, so you never hit a scenario cold in an exam.

Before we start, one plain-words refresher so no symbol is unearned:

Think of it exactly like the kitchen from the parent note: tickets taken in order, dishes cooked whenever their ingredients are ready, the loudspeaker shouting "soup from station 3 is done!" to all listeners simultaneously.

---

The scenario matrix

Every Tomasulo situation is really a combination of a few independent "axes". Here are the case classes this topic can throw at you:

Cell	Case class	The stress it tests	Covered by
C1	Pure RAW chain	Do tags carry a value forward without touching the register file?	Ex 1
C2	WAR (anti-dependence)	Does an early reader keep its value when a later instr overwrites the same reg?	Ex 2
C3	WAW (output-dependence)	Does "last issuer wins" the register, ignoring the stale earlier write?	Ex 3
C4	Independent instr hiding a slow load	Latency hiding — the whole point	Ex 4
C5	CDB structural conflict (two finish same cycle)	The single-bus bottleneck	Ex 5
C6	Structural stall (no free RS)	Issue blocked even though logic is fine	Ex 6
C7	Degenerate / zero case (fan-out to many listeners)	One broadcast → many snoopers	Ex 7
C8	Real-world word problem	Mapping a story to tags/stages	Ex 8
C9	Exam twist: speculation limit (precise exceptions)	What Tomasulo cannot do alone	Ex 9

Timing convention used on this page (fixed once, applied everywhere): a stage is a labelled phase, and the Execute phase is where all the arithmetic/memory latency lives — I fold the 1-cycle Write into the completion of Execute so the numbers stay clean. Concretely:

We now walk each cell.

---

Ex 1 — Pure RAW chain (Cell C1)

Forecast: guess before reading — does I2 read F2 from the register file, or straight off the bus?

1. Issue I1 (cycle 1). F4, F6 ready → Add1: Vj = val(F4), Vk = val(F6). Set Qi[F2] = Add1. Why this step? Issue is in-order and it renames: I1 now "owns" the name F2 under tag Add1. Anyone later wanting F2 must wait for Add1.
2. Issue I2 (cycle 2). Source F2 → Qi[F2] = Add1 (pending) → Mult1: Qj = Add1. F8 ready → Vk = val(F8). Set Qi[F0] = Mult1. Why this step? We don't have F2's value yet, so we store who will deliver it (the tag), not a number.
3. Execute I1 (cycles 3–4). Add1 has both values → fires. Result ready end of cycle 4. Why this step? Add1 has Qj = Qk = 0 (both operands are real values), so its firing condition is met and the adder can start — this is the Execute stage gate in action.
4. Write I1 (cycle 5). Broadcast (Add1, result) on CDB. Mult1 sees Qj == Add1, snaps the value into Vj, clears Qj = 0. Why this step? This is the punchline — the value flows bus → RS, never returning to the register file to be re-read.

Verify: Let $F4=3,F6=5,F8=2$. Then $F2=3+5=8$ and $F0=8\times 2=16$. I2 got $8$ off the CDB, not from the register file — correctness preserved. ✅

---

Ex 2 — WAR dissolved (Cell C2)

Forecast: will I2 end up using the old F8 or I3's new F8?

1. Issue I1. Qi[F0] = Div1. Div is slow — it will stall everyone naïvely. Why this step? I1 renames its destination F0 to tag Div1, so any later reader of F0 will wait on Div1 rather than the register — setting up the pending dependency the rest of the example turns on.
2. Issue I2. F0 pending → Add1: Qj = Div1. F8 ready now → Vk = val(F8) captured immediately. Set Qi[F6] = Add1. Why this step? The instant of issue, I2 grabs F8's value into Vk. It is now a private copy.
3. Issue I3. Writes F8 → Qi[F8] = Sub1. Operands F10, F12 ready → I3 can execute right away, long before slow I1/I2 finish. Why this step? I3's new F8 lives under tag Sub1; I2's captured copy in Vk is a different storage location entirely.

Verify: Let old $F8=7$, $F10=1,F12=4$ so new $F8=1-4=-3$. I2 uses its captured $F8=7$. When Div1 finally delivers $F0$ (say $F2=20,F4=5\Rightarrow F0=4$), I2 computes $F6=4+7=11$ — using the old F8, exactly as program order demands. WAR never bit. ✅

---

Ex 3 — WAW dissolved (Cell C3)

Forecast: after both finish, which value is in F6 — I1's sum or I2's product?

1. Issue I1. Qi[F6] = Add1. Why this step? At issue, I1 claims the destination name F6 under tag Add1 — this is the renaming stamp that marks I1 as F6's current pending writer.
2. Issue I2 (in order, so after I1). Overwrite Qi[F6] = Mult1. Why this step? The register-status table always points to the last issuer. So F6's official owner is now Mult1.
3. Write I1. Broadcasts (Add1, sum). But Qi[F6] == Mult1 ≠ Add1, so the register ignores this write. Any RS that captured Add1 still gets the value (that's a legit RAW consumer of I1), but the register stays owned by Mult1. Why this step? The register only accepts a broadcast whose tag matches its Qi entry; since I2 already reclaimed F6, I1's stale write is filtered out automatically — this is the mechanism that dissolves WAW without any explicit ordering logic.
4. Write I2. Broadcasts (Mult1, product). Now Qi[F6] == Mult1 → F6 stores the product, marked ready. Why this step? The tag now matches, so F6 accepts I2's value and clears its Qi, leaving the register holding exactly what program order (last writer wins) demands.

Verify: Let $F2=2,F4=3$ so I1 wants $5$; $F8=4,F10=6$ so I2 wants $24$. Program order says F6 must end as I2's value $=24$. Register ends with $24$, I1's $5$ discarded for the register. WAW solved by "last issuer wins." ✅

---

Ex 4 — Independent instruction hides a slow load (Cell C4)

Forecast: does I3 wait for the load, or run during the miss?

1. Issue I1 (cycle 1). Qi[F0] = Load1. The 2-cycle address/access-setup begins and the ~100-cycle memory access is launched (see Cache Misses & Memory Latency). I1's Execute spans cycles 2–103 (2 setup + 100 memory + the value is broadcast at cycle 104). Why this step? Issuing I1 renames F0 to Load1 and launches memory immediately, so later independent work has a 102-cycle shadow to hide inside.
2. Issue I2 (cycle 2). F0 pending → Mult1: Qj = Load1. It cannot fire — Qj ≠ 0. Why this step? I2 records the tag Load1 (not a value) because F0 is unavailable; its Qj ≠ 0 proves it is genuinely blocked by a true RAW dependency, so it is right that it waits.
3. Issue I3 (cycle 3). F10, F12 ready → Add1: Vj, Vk filled. Qj = Qk = 0. Execute cycles 4–5 (Add latency 2), broadcast cycle 6 — all during I1's still-running memory access. Why this step? Tomasulo does not check program order for execution — only operand readiness. I3 has its operands, so it runs.

The figure below plots all three instructions on a cycle timeline so you can see I3's short bar sitting entirely inside I1's long miss bar.

Verify: With the model above, I3 finishes broadcasting at cycle 6 while I1 finishes at cycle 104. Since $6<104$, I3's entire life is overlapped with the miss → the Add's 2 compute cycles are fully hidden, and in real code dozens of independent instructions pile into that 102-cycle shadow. Check: $6<104$ and hidden compute $=2$. ✅

---

Ex 5 — CDB structural conflict (Cell C5)

Forecast: two results ready at once, one bus — what gives?

1. Both execute on separate adder units, no data conflict. Why this step? There are two physical adders and the two instructions share no operand dependency, so execution has no conflict at all — the clash we are about to see is purely at the write stage, not here.
2. Write stage collides. The CDB carries one (tag, value) per cycle. Only one of Add1, Add2 broadcasts this cycle; the other must wait one cycle. Why this step? The bus is a shared physical wire — this is a structural hazard, not a data one. An arbiter picks a winner (commonly the oldest).
3. Loser broadcasts next cycle. Why this step? The bus is a serial resource: the loser's result is finished and just waiting for the wire, so as soon as the bus is free (next cycle) it broadcasts — the delay is exactly one cycle of serialization, nothing more.

Verify: If both finish computing at cycle 6, total Write cycles needed = 2 (one each), so completion cycles are 6 and 7 — a 1-cycle serialization penalty. With $n$ simultaneous finishers on one CDB, total extra write cycles $=n-1$. For $n=2$: $2-1=1$. ✅ (This is exactly the parent-note's "two instructions can broadcast in the same cycle" mistake, defused.)

---

Ex 6 — Structural stall: no free RS (Cell C6)

Forecast: does I3 issue, or does the whole pipeline choke?

1. Issue I1 → Mult1, Issue I2 → Mult2. Both busy, computing. Why this step? Each multiply needs a multiplier RS to hold it; I1 and I2 grab the only two available, so after this step the multiplier RS pool is completely full — that scarcity is what triggers the stall next.
2. Try to issue I3. No free multiplier RS → structural stall on Issue. Because Issue is strictly in program order, I3 and everything after it also stall, even independent later instructions. Why this step? Issue is the one in-order chokepoint. A full RS pool blocks the queue regardless of data readiness — this is a hardware-count limit, not a dependency.
3. When I1 finishes and frees Mult1, I3 can finally issue there. Why this step? An RS is released only when its instruction writes its result; freeing Mult1 is what removes the structural block, so I3 must wait precisely until that freeing event — this pins down when the stall ends.

Verify: I1 occupies Mult1 for its whole life: Issue(1) + Execute(6) + Write(1) = 8 cycles. Assuming no CDB contention, I3 cannot issue until cycle 9 at the earliest (the cycle after Mult1 frees at end of cycle 8). Delay imposed on I3 by the structural limit $=9-3=6$ cycles beyond its natural issue slot. ✅

---

Ex 7 — Degenerate fan-out: one producer, many listeners (Cell C7)

Forecast: four consumers — four writes, or one?

1. Issue I2–I5. Each captures Qj = Load1 (all waiting on the same tag). Why this step? At issue F0 is still pending under tag Load1, so every consumer records that same tag as its Qj — this is what makes them all snoop the identical broadcast later, giving free fan-out.
2. Write I1. One broadcast (Load1, value) on the CDB. Why this step? The CDB is one-to-many by nature. Every RS whose Qj (or Qk) equals Load1 snoops the same broadcast simultaneously and copies the value.

Verify: Number of CDB broadcasts by I1 $=1$, independent of the number of consumers ($4$ here). Broadcast is a fan-out for free — this kills the parent-note mistake "producer writes the register 5 times." Count check: consumers $=4$, writes $=1$. ✅

---

Ex 8 — Real-world word problem (Cell C8)

Forecast: does the black coffee get made before the latte?

1. Order A "issues" into slot 1 with Qj = Z (waiting for the espresso tag). It cannot start. Why this step? Unmet operand tag = Qj ≠ 0 = not fireable, exactly like a pending RAW.
2. Order B "issues" into slot 2 with Vj, Vk all present (Qj = Qk = 0). It fires now — out of program order. Why this step? Operand readiness, not ticket order, gates execution.
3. Z finishes, shouts on the PA → (Z, espresso). Slot 1 snoops it, clears Qj, and Order A can proceed. Why this step? The PA is the CDB: Z's single announcement is the one broadcast that all waiting slots snoop, so slot 1's Qj = Z matches, clears to 0, and Order A becomes fireable — the story's "loudspeaker" is exactly the write-then-wake mechanism.

Verify: Execution order = B then A, even though ticket order = A then B. This is the identical mechanism as Ex 4 (independent op runs during a stall). The story is faithful because: 1 barista = 1 unit, 3 slots = 3 RS, PA = CDB, tickets in order = in-order Issue. ✅ (One-to-one mapping, all four elements accounted for.)

---

Ex 9 — Exam twist: what Tomasulo canNOT do alone (Cell C9)

Forecast: when I1 faults, is machine state exactly "everything before I1 done, nothing after"?

1. I2 executes and writes F6 while the slow divide is still running. Why this step? Out-of-order Write is allowed for independent ops — that's the whole speedup.
2. I1 finally detects divide-by-zero. But F6 (a later instruction) has already modified architectural state. Why this problem exists? There is no in-order commit stage in classic Tomasulo — results become visible as soon as they broadcast. See Branch Prediction & Speculation for the same hazard with wrong-path instructions.
3. Fix (beyond classic Tomasulo): add a Reorder Buffer (ROB). Results wait in the ROB and are committed to the register file in strict program order; when I1 faults, every entry after it is still uncommitted, so the ROB simply discards them and no later write ever became visible → precise exceptions. Why this step? Separating "compute out of order" from "make visible in order" is the missing ingredient: the ROB adds the in-order commit gate that classic Tomasulo lacks, restoring the illusion that instructions finished one-by-one in program order.

Verify: With classic Tomasulo, count of later instructions that may have already updated state when I1 faults $\ge 1$ (here exactly $1$: I2). Therefore the exception is imprecise — precisely the parent-note Mistake 1 caveat. Adding a ROB reduces that count to $0$ at commit. Boolean check: is_precise_without_ROB = (leaked_writes == 0) where leaked_writes = 1 → False. ✅

---

Recall Which cell each example covered

Every matrix cell C1–C9 mapped one-to-one to Ex 1–9. Which example proves WAR never corrupts an early reader? ::: Ex 2 — F8's value is captured into Vk at issue. Which example shows the single-CDB structural bottleneck? ::: Ex 5. Which example shows a full RS pool stalling in-order Issue? ::: Ex 6. Which example shows why classic Tomasulo lacks precise exceptions? ::: Ex 9 (needs a ROB).

Related building blocks: Register Renaming, Scoreboarding, Superscalar Execution, Pipelining and Hazards.