Out-of-order execution — Tomasulo algorithm (conceptual): Visual walkthrough

We will trace exactly this program the whole way through:

I1: ADD.D  F2, F4, F6    ; F2 = F4 + F6
I2: MUL.D  F0, F2, F8    ; F0 = F2 * F8   (needs F2 from I1)

Two instructions. That's all we need to see every idea.

Step 1 — The board before anything runs

WHAT we drew: the empty board. WHY: every later picture is just this board with arrows and notes added. You must know the furniture before the play starts. PICTURE: below. Green boxes hold real numbers; grey boxes are empty; every sticky-note says ready because so far nobody is promising anything.

Figure — Out-of-order execution — Tomasulo algorithm (conceptual)

Step 2 — Issue I1: the adder claims the name "F2"

We process instructions in program order at issue time. So I1 goes first.

I1: ADD.D F2, F4, F6 reads F4 and F6, writes F2.

We ask, for each source register, the one question that decides everything:

Is a real value sitting in this register, or is someone about to write it?

The sticky-notes say F4 = ready and F6 = ready. So we copy the values straight into Add1.

Then the rename happens. I1's destination is F2, so we write on F2's sticky-note:

$Qi [F 2] = Add1$

Read that as: "F2's next value will be produced by station Add1." From this instant, anybody who wants F2 must listen for Add1, not read the register box.

WHAT: filled Add1 with two values; pointed F2's sticky-note at Add1. WHY: F4/F6 were ready, so no waiting is needed — grab the numbers. And by tagging F2, we've given F2's future a name, which is the whole trick that later kills false hazards. PICTURE: the burnt-orange arrows carry values into Add1; the plum sticky-note on F2 now reads Add1.

Step 3 — Issue I2: a tag, not a value, is captured

Still in program order: now I2: MUL.D F0, F2, F8. Sources are F2 and F8.

Ask the same question for each source:

F8? Sticky-note says ready → copy the value: $V_{k} = val (F 8)$ .
F2? Sticky-note says Add1 → not ready! So instead of a value, we copy the tag:

$tag slot for 1st operand Q_{j} = Add1$

$Q_{j}$ is the tag version of $V_{j}$ . A waiting room slot is either a filled value or a pending tag — never both. Here operand 1 is a pending tag (Add1), operand 2 is a value.

The firing rule is simply:

Finally rename I2's destination: $Qi [F 0] = Mult1$ .

WHAT: put a value for F8 but only a tag Add1 for F2 into Mult1; pointed F0 at Mult1. WHY: we genuinely don't have F2's number yet — so we record who owes it to us (a tag) instead of a number. This is the moment a promise gets stored. PICTURE: notice the teal tag arrow into Mult1's $Q_{j}$ slot — dashed, because it carries a name, not a number. Compare with the solid value arrow for F8.

Step 4 — Execute I1 (I2 is frozen)

Now look at the two waiting rooms:

Add1: both value slots full → it fires into the adder.
Mult1: $Q_{j} = Add1$ still pending → frozen, correctly.

The adder computes $val (F 4) + val (F 6)$ . Meanwhile Mult1 just sits, watching.

WHAT: the adder runs; the multiplier waits. WHY: this is exactly how a RAW (Read-After-Write) true dependency is respected — I2 cannot physically start, because operand 1's slot holds a tag, not a number. No number, no computation. The hardware enforces correctness by construction. PICTURE: Add1 glows (executing); Mult1 is dimmed with a little "waiting for Add1" note.

Step 5 — Write Result I1: the tag becomes a value on the CDB

Add1 finishes with a result — call it $r$ . Now the single most important event happens.

The broadcast rule — a snoop, done by every listener in parallel:

Two things happen this cycle, from one broadcast:

Mult1 sees $Q_{j} = Add1$ → it grabs $r$ into $V_{j}$ and sets $Q_{j} = 0$ . Now both its slots are values → next cycle it can fire.
Register F2 sees $Qi [F 2] = Add1$ → it stores $r$ and its sticky-note flips back to ready.

Notice what never happened: the value did not travel back into the register file and then out again to Mult1. It flowed directly producer → consumer over the bus. That direct hand-off is the speed win.

WHAT: Add1 broadcast (Add1, r); Mult1 and register F2 both caught it. WHY: one broadcast serves all waiters at once — one-to-many for free. And it's how a tag (a promise) finally "cashes in" to become a value. PICTURE: one thick teal CDB line leaving Add1, splitting to Mult1's $V_{j}$ and to register F2. The dashed tag arrow from Step 3 is now solid.

Step 6 — Execute + Write I2: the chain completes

Mult1 now has $V_{j} = r$ and $V_{k} = val (F 8)$ , both real numbers, $Q_{j} = Q_{k} = 0$ . So it fires, multiplies, and on finishing broadcasts $(Mult1, r \cdot val (F 8))$ . Register F0 (whose sticky-note read Mult1) catches it and flips to ready.

Both instructions are done. Final register state is exactly what strict in-order execution would have produced — but Mult1 never wasted a cycle before its data was ready, and the value skipped the register-file round trip.

WHAT: the multiplier ran and delivered F0. WHY: the dependency chain I1 → I2 was walked by following tags, not by re-reading registers. PICTURE: Mult1 executing then broadcasting to F0; the whole two-instruction dataflow drawn as one chain of arrows.

Step 7 — The edge cases (so no scenario surprises you)

Three quick "what if" boards, because a walkthrough that only shows the happy path is a trap.

WHAT: three corners — trivial-ready, many-listeners, bus-contention. WHY: rules 1–6 already contain these outcomes; drawing them means you'll never meet an unshown situation. PICTURE: three mini-boards side by side illustrating A, B, C.

The one-picture summary

This last figure compresses all six live steps into a single timeline: Issue → Execute → Write across cycles, with the tag Add1 drawn as a coloured token that moves from F2's sticky-note, into Mult1's $Q_{j}$ slot, and finally dissolves into a value on the CDB.

Recall Feynman: retell the whole walkthrough in plain words

Two order tickets come in. Ticket 1 (ADD) has both its ingredients on the counter, so we drop them into prep-station Add1 and write on the F2 shelf-tag: "F2 is coming from Add1." Ticket 2 (MUL) needs F2 — which isn't cooked yet — so instead of an ingredient we hand station Mult1 a note that says "Add1", plus the one ingredient it does have (F8). Mult1 can't start; it's holding a promise, not food. Add1 finishes and shouts once over the loudspeaker: "Add1's dish is ready — here it is!" Everybody holding an "Add1" note grabs the result at that instant: Mult1 swaps its note for the real food, and the F2 shelf gets stocked. Now Mult1 has everything, cooks, and shouts its own result to the F0 shelf. The tickets were taken in order; the food was cooked the moment ingredients existed; and the finished plates match the tickets exactly. That token that travelled from a shelf-tag, to a note, to real food — that's the tag becoming a value on the CDB, and it's the entire idea.

Related vault paths: Pipelining and Hazards · Scoreboarding · Superscalar Execution · Branch Prediction & Speculation · Cache Misses & Memory Latency · Parent topic.

Flashcards

At issue, when is a tag copied into a station instead of a value?

When the source register's status says another RS will still produce it (Qi[s] ≠ ready) — we don't have the number, so we record who owes it.

On the CDB broadcast, what does a station do when its Qj matches the broadcast tag?

It copies the broadcast value into Vj and clears Qj (sets it to 0); when both Q slots are 0 it may fire.

Why does the multiplier freeze in Step 4 even though the adder is running?

Its operand-1 slot holds the tag Add1, not a value — a RAW true dependency, so the hardware physically cannot start it.

In the "5 waiters" case, how many times does the producer write the register?

Once — a single CDB broadcast is snooped by all five waiting stations simultaneously.

What limits two finished results in the same cycle?

The CDB is a single shared wire, so only one (tag,value) pair rides per cycle; the other waits (arbitration).