Reservation stations: Exercises — Hardware deep dive

Level 1 — Recognition

Exercise 1.1 (L1)

An instruction is issued and its reservation station ends up as: {Op=ADD, Vj=?, Vk=40, Qj=Mult1, Qk=0}. State, in plain words, exactly what this station is waiting for and what it already knows.

Recall Solution 1.1

Read the fields one at a time.

Qk=0 → the second operand is ready; its value is in Vk=40.
Qj=Mult1 → the first operand is not ready; the station Mult1 will produce it. We do not yet have a number, so Vj is blank (?).

In words: "I am an ADD. I already hold my second input (40). I am waiting for station Mult1 to broadcast the first input. The instant it does, I capture that value into Vj, set Qj=0, and both operands being ready (Qj=Qk=0) I fire into the ALU (the arithmetic logic unit)."

Exercise 1.2 (L1)

The register status table shows Status[R6] = empty and Status[R7] = Add2. Instruction SUB R8, R6, R7 is being issued. Fill in Vj, Vk, Qj, Qk.

Recall Solution 1.2

Match each source register against the status table.

Source 1 is R6. Status[R6] = empty → value is in the register file → copy it into Vj, set Qj = 0.
Source 2 is R7. Status[R7] = Add2 → value is pending, produced by Add2 → set Qk = Add2, leave Vk blank.

Result: {Op=SUB, Vj=R6_val, Vk=?, Qj=0, Qk=Add2}.

Level 2 — Application

Exercise 2.1 (L2)

Given a clean machine (all registers ready in the register file), issue this sequence and give the RS contents and status-table changes right after each issue:

1. MUL  R1, R2, R3
2. ADD  R4, R1, R5

Assume Mult1 is the free multiply station and Add1 the free add station.

Recall Solution 2.1

Issue MUL (cycle 1). R2 and R3 are both empty in the status table → both operands ready. Mult1: {Op=MUL, Vj=R2_val, Vk=R3_val, Qj=0, Qk=0}. Then set Status[R1] = Mult1 (R1's next value now comes from Mult1).

Issue ADD (cycle 2). Source R1: Status[R1] = Mult1 → pending → Qj = Mult1, Vj blank. Source R5: empty → ready → Vk = R5_val, Qk = 0. Add1: {Op=ADD, Vj=?, Vk=R5_val, Qj=Mult1, Qk=0}. Then set Status[R4] = Add1.

This is a pure RAW dependency (Add1 truly needs Mult1's answer), and the tag Mult1 captures it exactly.

Exercise 2.2 (L2)

Continue Exercise 2.1. On some later cycle Mult1 finishes and broadcasts its result = 12 on the Common Data Bus (CDB). Show what changes in Add1 and in the register file.

Recall Solution 2.2

Every station snoops the CDB (the shared broadcast wire) tag against its Qj and Qk.

Add1.Qj = Mult1 matches → capture: Vj ← 12, then Qj ← 0. Now Add1: {Op=ADD, Vj=12, Vk=R5_val, Qj=0, Qk=0} → both ready → eligible to execute next.
Register file: Status[R1] = Mult1 matches → write R1 ← 12, clear Status[R1] to empty.
Mult1 is freed (Busy=0).

Exercise 2.3 (L2)

A machine has 64 total reservation stations. How many bits does each operand tag field need? If a design later doubles to 128 stations, how many bits then?

Recall Solution 2.3

A tag must name one of the stations, so we need just enough bits to count them. The rule in words: tag bits = the smallest whole number of bits that can label every station — i.e. round the base-2 logarithm of the station count up to the next whole number.

64 stations: since $64 = 2 \times 2 \times 2 \times 2 \times 2 \times 2$ (six twos), exactly 6 bits label all 64.
128 stations: since $128 = 2 \times 64$ (seven twos), you need 7 bits.

So doubling the station count adds exactly one bit per tag — each extra bit doubles how many stations you can name.

Level 3 — Analysis

Exercise 3.1 (L3)

Run the full four-instruction sequence from the parent note and explain, at issue time, why instruction 4 depends on Add2 and not on Mult1:

1. MUL R1, R2, R3
2. ADD R4, R1, R5      ; RAW on R1
3. SUB R1, R6, R7      ; WAW on R1
4. ADD R8, R1, R9      ; RAW on new R1

Use the station-naming rule from the definitions: instruction 2 lands in the first free add station Add1, instruction 3 in the next free add station Add2, instruction 4 in the next Add3.

Recall Solution 3.1

Track Status[R1] as a moving pointer to "who produces R1's current value."

After inst 1 issues into Mult1: Status[R1] = Mult1.
Inst 2 issues into Add1, reads Status[R1] = Mult1, so Add1.Qj = Mult1. It snapshots the then-current producer.
Inst 3 (SUB R1,…) issues into Add2. Because it writes R1, we overwrite Status[R1] = Add2. This is the WAW resolution: the newest writer becomes R1's producer.
Inst 4 issues into Add3, reads Status[R1] = Add2 → Add3.Qj = Add2.

Why 4 depends on Add2, not Mult1: by the time inst 4 reads the status table, inst 3 had already overwritten the pointer. The status table always names the latest binding of a register, so inst 4 correctly waits for inst 3's result. Inst 2, which read the pointer earlier, still holds the old Mult1 tag — exactly the value it should get, because in program order inst 2 reads R1 before inst 3 rewrites it.

How to read the figure below. The two producers of "an R1 value" sit on the left: Mult1 (top, cyan) and Add2 (bottom, amber). The two consumers of R1 sit on the right: Add1 (inst 2, top) and Add3 (inst 4, bottom). Follow the cyan arrow across the top — it shows inst 2 snapshotting the early pointer value Mult1. Follow the amber arrow across the bottom — it shows inst 4 snapshotting the later pointer value Add2. The box in the middle is the single Status[R1] pointer; the cyan line is what it read as early, the amber line what it was overwritten to. Same register name, two different producers — decided purely by when each consumer read the pointer.

Exercise 3.2 (L3)

In Exercise 3.1, when Mult1 finally broadcasts, the register file ignores it. Prove this is correct — that R1 must not take Mult1's value.

Recall Solution 3.2

When Mult1 broadcasts, the register file checks Status[R1]. But inst 3 already set Status[R1] = Add2, so the tag Mult1 does not match → register file does nothing.

Why correct: program order says inst 3 (R1 = R6-R7) writes R1 after inst 1 (R1 = R2*R3). The architectural final value of R1 must be inst 3's result. If the register file accepted Mult1's late broadcast, it would clobber inst 3's value — a WAW violation. The mismatch is the mechanism that makes inst 1's write "dead" as far as the register file is concerned.

Meanwhile Add1.Qj = Mult1 did match, so inst 2 correctly still receives the old R1 — because inst 2 legitimately reads R1 before inst 3 overwrites it.

Level 4 — Synthesis

Exercise 4.1 (L4)

You are given a machine with one multiply station, one add station, and one CDB. Consider:

1. MUL R1, R2, R3
2. MUL R4, R5, R6

Both multiplies are independent. If a multiply takes 4 execute cycles and both are issued in back-to-back cycles, what limits throughput here, and what single design change fixes it?

Recall Solution 4.1

With only one multiply station, inst 2 cannot be issued until inst 1's station is free (freed only after write-result). Even though the two multiplies are independent, they serialize on the station, not on data.

This is a structural hazard on reservation stations (parent note, Mistake 1: "if RS full, must stall issue"). The fix: add a second multiply reservation station so inst 2 can be issued and begin waiting/executing in parallel. (A single pipelined multiply unit fed by two stations lets both be in flight; the CDB is still one bus but results here finish 4 cycles apart, so no CDB conflict.)

Exercise 4.2 (L4)

Design question: two functional units finish in the same cycle and both want the single CDB (Common Data Bus). Describe the conflict, then give one modern fix and its cost in wiring terms.

Recall Solution 4.2

Conflict: classic Tomasulo has one CDB → only one result may be broadcast per cycle. Two simultaneous completions are a structural hazard on the CDB; one unit must stall its write-result by a cycle (arbitration picks a winner).

Modern fix: add a second CDB (more generally $m$ buses). Now up to $m$ results broadcast per cycle.

Cost: every reservation-station operand field and the register file must snoop every bus. With $n$ snooping structures and $m$ buses that is $O (n \times m)$ comparators/wires — throughput bought with area and power. This is exactly the tradeoff the parent note flags.

Level 5 — Mastery

Exercise 5.1 (L5)

Corner case. What happens if an operand becomes available on the very cycle an instruction is being issued — i.e., the producing station is broadcasting on the CDB in the same cycle you read the status table? Show why a naive implementation could deadlock the consumer, and state the standard fix.

Recall Solution 5.1

The race. During issue you read Status[R1] = Mult1 and set Qj = Mult1. But this same cycle Mult1 is broadcasting on the CDB. If your capture logic only checks the CDB against stations that were already holding Qj = Mult1 at the start of the cycle, the just-issued station missed the broadcast. Its Qj stays Mult1 forever — Mult1 will never broadcast again (it's freed). The consumer waits for a tag that can never fire → deadlock (a lost wakeup).

Standard fix: at issue, also compare the operand's producing tag against the CDB tag being broadcast this cycle. If they match, capture the broadcast value directly into Vj and set Qj = 0 immediately (rather than storing the tag). Equivalently: the status-table read and the CDB snoop happen "together," so a same-cycle broadcast is either forwarded or the tag is captured and honored next cycle. Either way, no wakeup is lost.

Exercise 5.2 (L5)

Degenerate input. An instruction has the form ADD R5, R5, R5 (both sources are the same register, which is also the destination). Trace Vj, Vk, Qj, Qk and Status[R5] assuming Status[R5] = Mult1 on entry, and this ADD is issued into station Add1. Confirm no corruption occurs.

Recall Solution 5.2

Step 1 — issue, fill operands. Both sources are R5, and Status[R5] = Mult1 → pending. So we fill both operand slots from the same producer: Add1: {Op=ADD, Vj=?, Vk=?, Qj=Mult1, Qk=Mult1}.

Step 2 — issue, update destination. Because R5 is also the destination, overwrite Status[R5] = Add1 (this station's own tag). The read of the old binding (Mult1) has already been captured into Qj/Qk; the write creates a brand-new binding (Add1). These are two separate events, so they do not interfere.

Step 3 — Mult1 broadcasts value $v$ . The station snoops the CDB tag against both Qj and Qk. Both equal Mult1, so both match → capture $v$ into both Vj and Vk, clearing both Q fields: Add1: {Op=ADD, Vj=v, Vk=v, Qj=0, Qk=0} → both ready → eligible to execute. The register file checks Status[R5]: it now equals Add1, not Mult1, so it correctly does not write R5 from Mult1's broadcast (that would be the stale value).

Step 4 — Add1 executes and writes back. It computes $v + v = 2 v$ , broadcasts as tag Add1. Register file checks Status[R5] = Add1 → matches → write R5 ← 2v, clear the status entry. Add1 is freed.

Why no corruption: the read of R5 used the old binding tag (Mult1) captured at issue, while the write of R5 created a new binding (Add1). Even though one architectural register name appears three times (two sources and the destination), the rename cleanly separates "the value R5 held going in" ( $v$ , twice) from "the value R5 holds coming out" ( $2 v$ ). No slot is ever read after it was overwritten. This is exactly the guarantee dynamic renaming buys — see 5.2.03-Register-renaming.

Exercise 5.3 (L5)

Cost synthesis. A CPU has 40 integer RS + 24 floating-point (FP) RS. (a) What is the tag width? (b) If each RS entry stores two tags (Qj, Qk) plus one 32-bit value each (Vj, Vk) plus a 6-bit Op field and 1 Busy bit, how many bits does one RS entry hold? (c) What is the total storage across all 64 RS, in bits?

Recall Solution 5.3

(a) Tag width. Total RS $= 40 + 24 = 64$ . Since $64 = 2^{6}$ (six factors of two), the smallest whole number of bits that can label every one of the 64 stations is 6 bits.

(b) Bits per entry. Add up every slot:

Op: 6 bits
Qj, Qk: $2 \times 6 = 12$ bits (two tags, each 6 bits from part (a))
Vj, Vk: $2 \times 32 = 64$ bits (two 32-bit values)
Busy: 1 bit

Total per entry $= 6 + 12 + 64 + 1 = 83$ bits.

(c) Total storage. All 64 stations each hold one 83-bit entry: $64 \times 83 = 5312 bits \approx 664 bytes .$

Reading the result: the value fields (Vj, Vk) dominate — 64 of the 83 bits are just the two operand values. The tags and control bits are cheap by comparison. This is why widening the datapath (32 → 64-bit operands) costs far more RS area than adding a handful more stations.

Connections

5.3.6 (parent topic)
5.3.04-Scoreboarding — the centralized ancestor these distributed stations improve upon.
5.3.07-Reorder-buffer — where precise-exception handling gets bolted onto this machinery.
5.2.03-Register-renaming — the renaming that Exercise 5.2 leans on.
4.6.02-Pipeline-hazards — the hazard taxonomy behind every RAW/WAR/WAW mention.
5.3.09-Load-store-queues — the memory-side analogue not covered by RS alone.

Recall One-line self-test

Which single test decides whether the register file updates on a CDB broadcast? ::: Whether the broadcast tag equals the register's current Status[] entry — a status-table match, independent of which stations captured the value.