Reservation stations: Visual walkthrough — Hardware deep dive

Before we start, three plain-English words we will earn:

Step 1 — Draw the problem: names that lie

WHAT. Look at these four instructions. R1 is written, then read, then written again, then read again.

1. MUL R1, R2, R3   ; R1 = R2 * R3   (writes R1)
2. ADD R4, R1, R5   ; R4 = R1 + R5   (reads R1)
3. SUB R1, R6, R7   ; R1 = R6 - R7   (writes R1 AGAIN)
4. ADD R8, R1, R9   ; R8 = R1 + R9   (reads the NEW R1)

WHY. The trouble is entirely in the name R1. Line 2 wants the first R1 (from line 1). Line 4 wants the second R1 (from line 3). If we run out of order, whose R1 is "the" R1? This ambiguity is exactly the family of pipeline hazards we must kill.

PICTURE. The figure shows the cup R1 being overwritten. The blue arrow is the read that wants the old juice; the red arrow is the read that wants the new juice. One cup cannot hold both — that is the bug.

Step 2 — Give each desk a nickname (the tag)

WHAT. We set up desks and give each a nickname: Mult1, Add1, Add2, Add3. We also make a small lookup table, the register status table, with one row per register name.

WHY. We need an answer to the question "if I read R1 right now, where is its newest value coming from?" The status table answers exactly that. Its rule:

PICTURE. Empty rows are drawn green (safe to read the cup). A row holding a tag is drawn orange (wait for that desk). Nothing has issued yet, so every row is green.

Each desk itself carries these slots (this is the desk's whole memory):

Step 3 — Issue MUL: mint the first tag

WHAT. Line 1 (MUL R1, R2, R3) grabs the free desk Mult1. Both inputs R2, R3 are ready in their cups, so we copy the numbers straight in.

$Mult1 : {O p = MUL, V_{j} = [R 2], V_{k} = [R 3], Q_{j} = 0, Q_{k} = 0}$

$V_{j} = [R 2]$ — the actual number from cup R2 copied in now.
$Q_{j} = 0, Q_{k} = 0$ — no promises pending; both inputs ready ⇒ this desk can compute immediately.

Then the crucial line:

$Status [R 1] \leftarrow Mult1$

WHY. This is the birth of a tag. We are announcing: "from now on, whoever reads R1 is really reading the eventual output of desk Mult1." The name R1 has been quietly renamed to Mult1.

PICTURE. Row R1 flips from green to orange and now stores the nickname Mult1. An arrow runs from the R1 row to the Mult1 desk — "your value lives here now."

Step 4 — Issue ADD (line 2): capture a promise, not a number

WHAT. Line 2 (ADD R4, R1, R5) takes desk Add1. Input R5 is ready (copy the value). But input R1? We look up $Status [R 1]$ and it says Mult1 — a promise, not a number.

$Add1 : {O p = ADD, V_{j} = ?, V_{k} = [R 5], Q_{j} = Mult1, Q_{k} = 0}$

$Q_{j} = Mult1$ — "my first input isn't here yet; it will arrive from desk Mult1." This is the promise being written down.
$V_{j} = ?$ — empty on purpose; we have no number for it yet.

And this instruction's own output register:

$Status [R 4] \leftarrow Add1$

WHY. This is the moment the RAW ("read-after-write") dependency on R1 gets encoded — not as a stall, but as a subscription. Add1 is now subscribed to whatever Mult1 will shout. Compare this with scoreboarding, where one central board polices all dependencies; here each desk minds only its own promises.

PICTURE. A dashed orange wire is drawn from Add1's $Q_{j}$ slot to the Mult1 desk. That dashed wire is the promise. When it turns solid, the value has arrived.

Step 5 — Issue SUB (line 3): the tag gets overwritten

WHAT. Line 3 (SUB R1, R6, R7) writes R1 again. It takes desk Add2; both inputs are ready. The decisive move:

$Status [R 1] \leftarrow Add2 (was Mult1, now Add2)$

WHY. This is the heart of the whole algorithm. R1 now has a new latest owner. The old binding to Mult1 is not deleted — Add1 already copied it in Step 4 — it is simply no longer the "current" R1. Two truths coexist:

Add1 still points at Mult1 (it froze that promise in the past).
The status table now points at Add2 (the present truth).

That coexistence is how a single name safely means two different values at once. It is what kills the WAW ("write-after-write") hazard: the later write silently becomes the newest binding.

PICTURE. The R1 row is redrawn: the nickname visibly changes from Mult1 to Add2. Add1's dashed wire still stubbornly points at Mult1 (drawn faded) — a snapshot of the past. A new arrow points R1 → Add2.

WHAT. Line 4 (ADD R8, R1, R9) takes desk Add3. It reads $Status [R 1]$ — which now says Add2.

$Add3 : {O p = ADD, V_{j} = ?, Q_{j} = Add2, V_{k} = [R 9], Q_{k} = 0}$

$Q_{j} = Add2$ — Add3 correctly waits for line 3's result, not line 1's.

WHY. This is the payoff of the overwrite in Step 5. Because the table was updated, line 4 automatically depends on the right producer. No special reasoning was needed — the table is the reasoning.

PICTURE. Two dashed wires now hang in the air: Add1 → Mult1 (old R1) and Add3 → Add2 (new R1). They point at different desks. The picture proves both readers are correct simultaneously.

Step 7 — The shout: Mult1 finishes and broadcasts

WHAT. Mult1 finishes computing. It puts its result on the Common Data Bus (CDB) — one shared wire everyone listens to — tagged with its own nickname Mult1.

Every desk runs this tiny check on both its inputs:

$if Q_{j} = (tag on CDB) \Rightarrow V_{j} \leftarrow (value on CDB), Q_{j} \leftarrow 0$

Reading term by term:

$Q_{j} = tag on CDB$ — "is my promise the one being paid right now?"
$V_{j} \leftarrow value$ — grab the number.
$Q_{j} \leftarrow 0$ — tear up the promise; this input is now a real value.

WHY broadcast at all? At the moment Mult1 issued, we did not know who would need its output (line 4 hadn't even issued). Point-to-point wiring would need every desk pre-connected to every other — that is $O (n^{2})$ wires. One shared bus lets any number of listeners subscribe for free.

PICTURE. The orange CDB wire lights up carrying (Mult1, 42). Add1's dashed wire turns solid green — it matched, captured 42, and cleared $Q_{j}$ . The status table row R1 does nothing: it holds Add2, not Mult1, so it ignores the shout (that value is now "dead" for the register file).

Step 8 — The second shout: Add2 finishes, register file updates

WHAT. Later, Add2 finishes and broadcasts (Add2, value). Now two listeners react:

Add3 matches ( $Q_{j} = Add2$ ): captures the value, clears its tag — Add3 can now run.
The register file checks $Status [R 1]$ ; it equals Add2, so it writes cup R1 for real and clears the row back to green.

$if Status [R 1] = (tag on CDB) \Rightarrow R 1 \leftarrow value, Status [R 1] \leftarrow \emptyset$

WHY. Only the latest binding is allowed to touch the architectural cup. Since Add2 was the latest owner of R1 (set in Step 5), this is the write that becomes visible to the outside world. The Mult1 value never reaches cup R1 — exactly right, because in the original program line 3 overwrote line 1.

PICTURE. The CDB carries (Add2, val). Add3's dashed wire goes solid; the R1 cup fills with the new juice and its status row flips back to green. Program order is honoured even though execution was scrambled.

The one-picture summary

WHAT. One frame showing the entire life of tag Mult1: minted at issue → frozen inside Add1 → superseded by Add2 in the status table → paid off on the CDB → captured by Add1 → ignored by the register file. Overlaid: the parallel life of tag Add2, which does reach cup R1.

WHY. Every hazard we started with is now visibly dead:

RAW → became a dashed wire (a subscription) that fills in when the value shouts.
WAW → became "overwrite the status row; latest owner wins."
WAR → the earlier reader already froze its own value, so a later write can't disturb it.

Recall Feynman retelling — say it like you're explaining to a friend

Registers are labelled cups, but a cup can be overwritten, so a name like R1 is a liar — it means different numbers at different times. Fix: whenever an instruction is going to write a register, we stop trusting the cup and instead write a nickname in a little table — "the fresh R1 is coming from desk Mult1." Any instruction that reads R1 right then copies down that nickname as a promise. When a second write to R1 comes, we just change the table's nickname to the new desk; anyone who already copied the old nickname keeps it (they froze the past), anyone reading now gets the new one. Desks compute the instant they have real numbers for both inputs — in any order. When a desk finishes, it shouts its result plus its nickname on one shared wire; every desk holding that nickname as a promise grabs the number and tears up the promise. The register cup only gets written by whichever desk the table currently points to — the latest writer — so the outside world sees exactly the program's final answer, even though everything inside ran out of order.

Connections

Parent: Reservation stations — the full mechanism this page draws step by step.
5.3.04-Scoreboarding — centralized dependency tracking; contrast with the distributed desks here.
5.3.07-Reorder-buffer — adds precise exceptions on top of this tag-passing.
5.2.03-Register-renaming — the "fresh cup per write" idea, formalized.
4.6.02-Pipeline-hazards — RAW/WAR/WAW, the enemies we killed.
5.3.09-Load-store-queues — the memory-side cousin of this trick.