Reservation stations: Worked examples — Hardware deep dive

This page is the exhaustive drill room for Reservation stations. The parent note taught you the machinery; here we run it against every kind of situation a reservation-station (RS) system can meet. Before we start, one promise: every symbol below was born in the parent note, but we re-anchor each one the moment we use it, so a reader who forgot can rebuild it from the picture.

The scenario matrix

Every reservation-station problem is really one of these cells. Our examples below cover all of them, and each example is labelled with the cell it hits.

#	Cell (case class)	What makes it tricky	Example
C1	Both operands already ready at issue	Degenerate: no waiting at all	Ex 1
C2	One operand pending (single RAW)	Must hold one IOU	Ex 2
C3	Both operands pending	Two IOUs, order of arrival	Ex 3
C4	Two consumers of the same result	One broadcast, many captures	Ex 4
C5	WAW (write-after-write) on same register	Status overwrite / "dead" value	Ex 5
C6	WAR (write-after-read) false dependency	Why renaming makes it vanish	Ex 6
C7	Structural hazard: RS full / two units finish same cycle	System stalls, limits	Ex 7
C8	Load/store address not ready (degenerate operand path)	Memory, two-phase execute	Ex 8
C9	Word problem (real-world sizing)	Count tag bits / RS sizing	Ex 9
C10	Exam twist: does OoO change the committed result?	Correctness vs. ordering	Ex 10

The figure below draws one station's anatomy — the Op, Vj/Qj, Vk/Qk, Busy fields — plus the CDB it snoops and the ready gate. Keep it in view: every example below is just this same picture with different numbers filled in. Notice the magenta "snoop" arrow running from the bus back into the station (that's Capture) and the violet ready gate at the bottom (Qj = 0 AND Qk = 0 → execute). The corner legend lists the ten cells C1–C10 so you can see which slot each example fills.

Example 1 — Cell C1: both operands ready (the degenerate case)

Worked example Statement

ADD R3, R1, R2   ; R3 = R1 + R2

At issue, Status[R1] and Status[R2] are both empty (values live in the register file). Let R1 = 5, R2 = 8. Trace the station and give the cycle it can start executing.

Forecast: guess before reading — does this instruction ever have to wait?

Issue. Allocate a free station, call it Add1. Since Status[R1] is empty, copy the value: Vj = 5, Qj = 0. Since Status[R2] is empty, Vk = 8, Qk = 0. Why this step? The status table is empty ⇒ no producer desk is pending ⇒ we grab the real numbers immediately, not IOUs.
Check readiness. Qj = 0 and Qk = 0 → the station is ready in the same cycle it issued. Why this step? Readiness is defined as both IOUs cleared. There is nothing to snoop for.
Execute. Compute 5 + 8 = 13. Then Write 13 on the CDB with tag Add1. Why this step? The whole point of RS is that a no-dependency instruction pays zero waiting cost — it behaves like a plain pipeline.

Verify: R3 = 5 + 8 = 13. Units: all are plain register values (dimensionless integers), sum is a value → consistent. No IOU was ever set, so the "degenerate" cell truly needs no CDB snoop.

Example 2 — Cell C2: one pending operand (single RAW)

Worked example Statement

MUL R1, R2, R3   ; (i)  R1 = R2 * R3, R2=4, R3=6
ADD R4, R1, R5   ; (ii) R4 = R1 + R5, R5=10

Instruction (ii) reads R1, which (i) is still computing. Trace (ii)'s station.

Forecast: which field of (ii) holds an IOU — Qj or Qk? And what number ends up in R4?

Issue (i). Station Mult1: Vj=4, Vk=6, Qj=0, Qk=0. Set Status[R1] = Mult1. Why? R1's next value now comes from desk Mult1; the phone book must say so.
Issue (ii). Its operand 1 is R1. Look up Status[R1] = Mult1 (not empty!) → store the IOU: Qj = Mult1. Operand 2 is R5, empty → Vk = 10, Qk = 0. Why? R1 isn't ready, so instead of a value we record who will produce it. This is renaming: (ii) now depends on the tag Mult1, not the name R1.
Mult1 finishes: 4 * 6 = 24, broadcasts (Mult1, 24) on the CDB. Why? One loudspeaker announcement; every desk snoops.
Add1 captures. Its Qj = Mult1 matches the shouted tag → set Vj = 24, Qj = 0. Now Qj=Qk=0 → execute 24 + 10 = 34. Why? Capture is the moment the IOU turns into a real ingredient.

Verify: R4 = (4*6) + 10 = 34. Sanity: (ii) waited exactly until (i) produced its value and not a cycle more — correct RAW behaviour.

Example 3 — Cell C3: both operands pending

Worked example Statement

MUL R1, R2, R3   ; (i)
SUB R4, R5, R6   ; (ii)
ADD R7, R1, R4   ; (iii) needs BOTH results

With R2=3,R3=3 (so R1=9) and R5=20,R6=5 (so R4=15). Suppose Mult1 finishes on cycle 8 and Sub1 on cycle 5. Trace (iii).

Forecast: does (iii) execute right after cycle 5, cycle 8, or somewhere in between?

Issue (iii). Status[R1]=Mult1, Status[R4]=Sub1. Both non-empty → two IOUs: Qj=Mult1, Qk=Sub1. No V yet. Why? Both sources are in flight; the station holds two IOUs simultaneously — that is perfectly legal.
Cycle 5: Sub1 broadcasts (Sub1, 15). (iii) snoops: Qk matches → Vk=15, Qk=0. But Qj=Mult1 still ≠ 0. Why? One IOU cleared, one remains ⇒ still not ready. Readiness needs both.
Cycle 8: Mult1 broadcasts (Mult1, 9). Qj matches → Vj=9, Qj=0. Now both zero → execute 9 + 15 = 24. Why? The station is gated by the last-arriving operand. The order of arrival didn't matter, only the max.

Verify: R7 = (3*3) + (20-5) = 9 + 15 = 24. Timing sanity: execution can begin at max(5, 8) = 8, controlled by the slower producer. ✔

Example 4 — Cell C4: two consumers of one result

Worked example Statement

MUL R1, R2, R3   ; (i)  R1 = 7*2 = 14
ADD R4, R1, R5   ; (ii) R5=1
SUB R6, R1, R7   ; (iii) R7=4

Both (ii) and (iii) read the same in-flight R1. How many CDB broadcasts are needed?

Forecast: does Mult1 shout once or twice?

Issue (ii): Qj = Mult1 (waiting on R1), Vk=1.
Issue (iii): looks up Status[R1]. It is still Mult1 (no one overwrote it) → Qj = Mult1, Vk=4. Why? Reading a register does not change its status entry. So both consumers legitimately hold the same IOU.
Mult1 broadcasts (Mult1, 14) — ONCE. Both Add1 and Sub1 snoop the same shout in the same cycle → both capture Vj=14, both clear Qj. Why broadcast, not point-to-point? At issue we didn't know how many desks would need R1. One announcement serves any number of listeners — this is the whole reason the CDB is a bus.

Verify: R4 = 14 + 1 = 15, R6 = 14 - 4 = 10. Both derived from a single broadcast — one shout, two captures. ✔

Example 5 — Cell C5: WAW hazard and the "dead" value

Worked example Statement

MUL R1, R2, R3   ; (i)   writes R1
ADD R1, R4, R5   ; (ii)  writes R1 AGAIN (WAW on R1)
SUB R6, R1, R7   ; (iii) reads R1  (must see (ii)'s R1)

With R2=2,R3=3 (→ (i) makes 6), R4=10,R5=20 (→ (ii) makes 30), and R7=8. Which value does R1 finally hold, what happens to (i)'s result, and what does R6 become?

Forecast: does (i)'s 6 ever land in R1?

Issue (i): Status[R1] = Mult1.
Issue (ii): it writes R1 too. Overwrite Status[R1] = Add1. The phone book now says "R1's newest producer is Add1." Why? This is the WAW fix: the latest writer wins the register-status entry. (i)'s claim on R1 is now invisible.
Issue (iii): reads Status[R1] = Add1 → Qj = Add1 (NOT Mult1), and R7 is ready so Vk = 8, Qk = 0. Why? (iii) comes after (ii) in program order, so it must see (ii)'s R1. The status table automatically gave it the right tag.
Mult1 finishes (6), broadcasts (Mult1, 6). The register file checks: is Status[R1] == Mult1? No, it's Add1. So the register file ignores it. Why? This is the "dead value." Nobody had Qj/Qk = Mult1, so it is simply dropped for R1. Correct — (i)'s write was overwritten.
Add1 finishes (30), broadcasts (Add1, 30). The register file checks: is Status[R1] == Add1? Yes. So it writes R1 = 30. In the same broadcast, (iii)'s station snoops, sees Qj = Add1 match, and captures Vj = 30, clearing Qj. Why this step? The register file writes only when the broadcasting tag matches the register's current status entry — that guarantees the register keeps the latest binding (Add1), not the stale one (Mult1). And (iii) captures on the same shout because its IOU named Add1; the one broadcast serves both the register file and every waiting consumer at once (same mechanism as Ex 4).

Verify: final R1 = 10 + 20 = 30 (kept); (i)'s value 2*3 = 6 is discarded; R6 = R1 - R7 = 30 - 8 = 22. ✔ (i)'s value never reaches R1.

Example 6 — Cell C6: WAR false dependency dissolves

Worked example Statement

ADD R3, R1, R2   ; (i)  reads R1
MUL R1, R4, R5   ; (ii) writes R1 (WAR: (ii) must not clobber R1 before (i) reads it)

R1 = 100 at start; R4=6,R5=7. In a naive in-order machine (ii) can't write R1 until (i) reads it. Show why RS make this constraint vanish.

Forecast: must (ii) wait for (i)?

Issue (i): R1 is ready → grab the value immediately: Vj = 100. (i) now owns the number 100 inside its own station. Why? Once captured, (i) no longer references the name R1 at all — it holds a private copy.
Issue (ii): writes R1 → Status[R1] = Mult1. This does not touch (i)'s copy of 100. Why? (i) already snapshotted its operand in step 1. (ii)'s new binding to R1 cannot corrupt a value that's already been copied out. The "false" WAR dependency is gone.
Execute (ii) freely, even before (i) executes: 6*7 = 42 → R1 = 42.

Verify: R3 = 100 + R2 (uses the old R1=100), while R1 later becomes 42. The order of the two executions no longer matters — that's the payoff of renaming. Let R2=1 → R3 = 101, R1 = 42. ✔

Example 7 — Cell C7: structural hazards (the limits!)

Forecast: in each, what must the machine do?

(a) — RS full. No free station ⇒ the third ADD cannot issue and the front end stalls for at least one cycle. Why this step? RS eliminate data hazards, never structural ones. If the buffer is physically full, issue blocks — this is the limiting/degenerate boundary of the whole scheme.
(b) — CDB contention. One bus = one broadcast per cycle. The arbiter picks one result (say Mult1); Add1 must hold its result and rebroadcast next cycle. Why? Classic Tomasulo has a single CDB. Two simultaneous producers is a structural hazard; one loses a cycle. (Modern designs add extra CDBs — at $O (n)$ wiring cost.)

Verify: counting check — with 2 stations and 2 busy, free stations = 2 - 2 = 0, so 0 < 1 needed ⇒ stall. With 1 CDB and 2 ready broadcasters, 2 > 1 ⇒ one deferred by exactly 2 - 1 = 1 cycle. ✔

Example 8 — Cell C8: load with address not yet ready

Worked example Statement

ADD  R2, R3, R4     ; (i)  computes base address, R3=1000, R4=24
LOAD R5, 0(R2)      ; (ii) load from address (R2 + 0)

The load's base register R2 is itself in flight. Trace the two-phase execute of the load.

Forecast: what does the load do before its address is known?

Issue (i). Allocate an integer-ALU station; call it Add1. Both R3 and R4 are ready → Vj = 1000, Vk = 24, Qj = Qk = 0. Set Status[R2] = Add1. Why this step? We must name the desk that will produce R2 so the load can point at it. Without showing (i)'s allocation, the tag Add1 would be a mystery.
Issue (ii). R2 pending → look up Status[R2] = Add1 → store the IOU: Qj = Add1. The address field A cannot be filled yet. Why? A load's first job is address computation; it needs the base value first, so it holds the base as an IOU like any operand.
Add1 finishes and broadcasts (Add1, 1024) (since 1000 + 24 = 1024). The load snoops, Qj = Add1 matches → captures the base value, Qj = 0. Why this step? The load cannot even begin address arithmetic until its base number exists; the CDB shout is exactly the moment that number becomes available, and Capture is how the load grabs it (same mechanism as every earlier example).
Execute phase 1 — address. A = base + offset = 1024 + 0 = 1024. Why split into phases? Memory access can't start until the address exists. Address calc is a distinct sub-step, unlike a pure ALU op.
Execute phase 2 — memory access, then broadcast. Read memory at address A = 1024, place the datum in the load's result, then broadcast (load-tag, datum) on the CDB. Why this step? Only now is the address known and safe to use; the memory read is the load's real work, and — like any producer — it must announce its result on the CDB so any consumer of R5 can capture it.

Verify: effective address = base + offset = (1000 + 24) + 0 = 1024. This is exactly where 5.3.09-Load-store-queues take over to check no earlier store aliases address 1024. ✔

Example 9 — Cell C9: word problem (sizing the hardware)

Forecast: guess the bit count before computing.

Total stations = 6 + 3 + 2 + 4 + 1 = 16. Why? A tag must uniquely identify any producing station across the whole machine (the CDB is global, so a shout could come from anywhere).
Bits needed = ⌈log₂(16)⌉ = 4 bits. Why the ceiling of a log? To label N distinct things you need ⌈log₂ N⌉ binary digits — the smallest number of on/off switches that gives at least N patterns. Here 2⁴ = 16 patterns exactly cover 16 stations.
Per-station tag storage. Each station holds two operand tags (Qj, Qk), each 4 bits → 2 × 4 = 8 bits of tag storage per station. Why? Each of j and k can independently be an IOU pointing at some station, so both need a full tag field.

Verify: 2⁴ = 16 ≥ 16 distinct stations ✔, while 2³ = 8 < 16 would be too few ⇒ 4 is the minimal bit-width. Per-station tag storage = 2 × 4 = 8 bits. ✔

Example 10 — Cell C10: exam twist — does out-of-order change the answer?

Worked example Statement

MUL R1, R2, R3   ; (i)   slow, R2=2,R3=5
ADD R4, R6, R7   ; (ii)  fast, R6=1,R7=1  (independent!)
SUB R8, R1, R4   ; (iii) needs both

(ii) finishes before (i) even though it's later in program order. Does the final architectural state differ from an in-order machine?

Forecast: true or false — OoO can produce a different value in R8?

Independence check. (ii) shares no register with (i) → no Q links them. It executes as soon as ready. Why? RS only serialize real data dependencies; unrelated instructions run whenever operands are present.
(iii) gates on both. Qj = Mult1, Qk = Add1. It waits for the later of the two finish times, regardless of which producer came first. Why? Correctness comes from tag capture, not from execution order. (iii) always uses (i)'s and (ii)'s actual results.
Result. R1 = 2*5 = 10, R4 = 1+1 = 2, R8 = 10 - 2 = 8. Why? Whatever order (i) and (ii) finish, (iii)'s two IOUs capture the true values before it executes, so it computes on 10 and 2.

Verify: an in-order machine computes the same R8 = (2*5) - (1+1) = 8. Out-of-order execution reorders timing, never values — that guarantee (plus the 5.3.07-Reorder-buffer for precise exceptions) is why the trick is safe. ✔

Recall Which cell does each example cover?

C1 ready/ready — Ex 1 ::: no wait, immediate execute C2 single RAW — Ex 2 ::: one IOU, capture once C3 both pending — Ex 3 ::: gated by last-arriving operand C4 two consumers — Ex 4 ::: one broadcast, many captures C5 WAW — Ex 5 ::: status overwrite, dead value dropped C6 WAR — Ex 6 ::: operand snapshotted, dependency vanishes C7 structural — Ex 7 ::: RS full stalls, one CDB defers C8 load address — Ex 8 ::: two-phase execute C9 sizing — Ex 9 ::: ⌈log₂ N⌉ tag bits C10 OoO safety — Ex 10 ::: reorders timing not values

Connections

Reservation stations — parent: the machinery these examples exercise.
5.3.06 Reservation stations (Hinglish) — same drills in Hinglish.
5.3.04-Scoreboarding — contrast: centralized tracking vs. our distributed Q/V desks.
5.3.07-Reorder-buffer — makes Ex 10's "timing-not-values" guarantee precise.
5.2.03-Register-renaming — the mechanism behind Ex 5 (WAW) and Ex 6 (WAR).
4.6.02-Pipeline-hazards — the hazard taxonomy the matrix is built on.
5.3.09-Load-store-queues — where Ex 8 continues for memory disambiguation.