Tomasulo's algorithm: Exercises — Hardware deep dive

Before we start, four shared pieces of vocabulary the parent note gave us, restated here in the tightest form so every symbol in the exercises is earned before use.

Definition The reservation-station (RS) fields you will touch constantly

Every reservation station (RS) — the little waiting-room buffer in front of a functional unit (FU) — carries these fields:

Op — the operation this slot will perform (ADD, MUL, SUB, DIV, …). Just a label for "what to compute."
$V_{j}, V_{k}$ — the actual numeric values of the two source operands, once we have them.
$Q_{j}, Q_{k}$ — instead of a value, a tag: the name of the RS that will eventually produce that operand. This is the IOU defined above.
busy — a single true/false flag: is this slot occupied? Set true at Issue, cleared to false when the result is broadcast and the slot is freed.
A given source is either a value ( $Q = NULL$ , look in $V$ ) or an IOU ( $Q =$ a tag, $V$ is don't-care — meaningless until the tag resolves). Never both.

Definition The common data bus (CDB), its listeners, its clock convention, and its arbiter

The CDB (common data bus, common-data-bus) is the single shared wire where a finished FU broadcasts <its-RS-name, result>. Two groups of listeners compare every broadcast tag against their stored tag:

every RS's $Q_{j}$ and $Q_{k}$ fields, and
every register's .tag field.

Any listener whose stored tag matches the broadcast name latches the value and clears its tag — all in the same cycle.

Clock-phase convention used on this page (fix it now, once, for every problem). We adopt the standard textbook model:

First half of a cycle: any CDB broadcast happens; matching listeners latch, so updated $Q$ /.tag fields are visible within this same cycle.
Second half of a cycle: the "ready check" ( $Q_{j} = NULL \land Q_{k} = NULL$ ) reads those just-updated fields.
Therefore a station that receives its last operand on the CDB in cycle $c$ begins executing in cycle $c + 1$ (the next cycle), and an $n$ -cycle FU that starts execution in cycle $s$ finishes in cycle $s + n - 1$ and broadcasts its result in cycle $s + n$ if it wins the bus. This is the single timing rule every table below obeys.

One broadcast per cycle, and the arbitration policy. A basic Tomasulo machine has one CDB, so at most one FU may write its result per cycle. When two or more FUs finish and want the bus in the same cycle, the arbiter uses a fixed policy: oldest instruction in program order wins. The loser(s) stall their Write-Result stage (their RS stays busy, holding the finished value) and retry the next free cycle. Every latency count below assumes this oldest-first policy.

Level 1 — Recognition

Exercise 1.1 (L1)

For the register file entry R7.tag = Mult2, is R7 currently holding a valid value? What does this tag mean in plain English?

Recall Solution

No, R7.value is not trustworthy right now. A non-NULL .tag is the flag "I am waiting." Specifically R7.tag = Mult2 reads as: "The next value of R7 will come from reservation station Mult2. When Mult2 broadcasts on the CDB, R7 will latch that number into .value and clear .tag to NULL." Only a NULL tag means the register's .value field is trustworthy.

Exercise 1.2 (L1)

Name the three stages of Tomasulo in order, and give a one-line job for each.

Recall Solution

Issue — grab a free RS, copy operand values or their producer tags, and stamp the destination register's .tag with this RS's name.
Execute — watch the CDB until both $Q_{j}$ and $Q_{k}$ are NULL, then run the functional unit.
Write Result — win the CDB, broadcast <RS_name, result>; all listeners (RS $Q$ fields + register .tag fields) that named this RS grab the value; clear busy.

Exercise 1.3 (L1)

A reservation station has $Q_{j} = NULL$ , $V_{j} = 4$ , $Q_{k} = Add1$ (so $V_{k}$ is don't-care). Can this instruction begin executing right now? Which field is blocking it?

Recall Solution

No. The execute condition is $Q_{j} = NULL \land Q_{k} = NULL .$ Here $Q_{k} = Add1$ (not NULL), so the second operand is still an IOU and $V_{k}$ holds nothing meaningful yet. The instruction is blocked on $Q_{k}$ , waiting for Add1 to broadcast. $Q_{j}$ is fine.

Level 2 — Application

Exercise 2.1 (L2)

Registers: R2 holds value 5 (tag NULL). R3.tag = Mult1 (waiting). Show the exact Issue-stage field assignments for:

ADD R4, R2, R3   → issues to Add1

Recall Solution

Source 1 is R2: tag NULL ⇒ we have the value, copy it into $V_{j}$ . Source 2 is R3: tag Mult1 ⇒ we don't have the value, copy the tag into $Q_{k}$ (an IOU). Destination is R4: stamp its .tag with this RS's name so future R4 readers wait on Add1.

Resulting state after Issue:

Add1: O p = ADD, V_{j} = 5, Q_{j} = NULL, V_{k} = (don’t-care), Q_{k} = Mult1, busy = true

R4.tag = Add1

The only two "waiting" facts are $Q_{k} = Mult1$ (this operand is an outstanding IOU) and R4.tag = Add1 (R4 is now itself an IOU on Add1). Everything else is settled.

Exercise 2.2 (L2)

Continue Exercise 2.1. On a later cycle Mult1 broadcasts <Mult1, 9> on the CDB. Show what changes in Add1, and state whether Add1 can now execute — and in which cycle it starts, under this page's clock convention.

Recall Solution

Add1.Qk == Mult1 matches the broadcast tag, so on the CDB latch (first half of the broadcast cycle, call it cycle $c$ ):

Add1.Vk ← 9
Add1.Qk ← NULL

Now both $Q_{j} = NULL$ and $Q_{k} = NULL$ , so Add1 is ready, and it will compute $5 + 9 = 14$ .

Which cycle does it start? Under this page's fixed convention (see the CDB definition box): the operand is latched in the first half of cycle $c$ ; the ready-check reads it in the second half of cycle $c$ ; so execution begins in cycle $c + 1$ . The CDB forwarding means we do not have to write 9 into a register and read it back — that is what buys us starting as early as $c + 1$ instead of later.

Exercise 2.3 (L2)

MUL R1, R2, R3   → Mult1   (R2=2, R3=3, both ready)
SUB R1, R6, R7   → Add1    (R6=20, R7=8, both ready)

After both instructions have issued (before either finishes), what is R1.tag? When Mult1 later broadcasts <Mult1, 6>, does R1 update?

Recall Solution

MUL issues first: R1.tag ← Mult1. SUB issues second and also writes R1: R1.tag ← Add1 (overwrites Mult1). So the final R1.tag = Add1.

When Mult1 broadcasts <Mult1, 6>, the Write-Result rule checks "does R1.tag still name Mult1?" — it does not, it names Add1. So R1 ignores the broadcast. This is exactly the WAW hazard being dissolved: the earlier writer's result is silently dropped because a later writer already claimed the name. (SUB's 20 - 8 = 12 will land in R1 instead.)

Level 3 — Analysis

Exercise 3.1 (L3)

Given this program with all operands initially ready except through dependencies:

1. MUL R1, R2, R3    # 5 cycles
2. ADD R4, R1, R5    # 2 cycles
3. SUB R6, R1, R7    # 2 cycles

Both ADD and SUB need R1 (produced by MUL). When MUL broadcasts on the CDB, how many stations grab the value in a single broadcast? What property of the CDB makes this cheap?

Recall Solution

Both ADD (Add1) and SUB (Add2) have Qj = Mult1. A single broadcast <Mult1, result> is latched simultaneously by every RS listening for Mult1. So two stations grab it in one broadcast — and it would be the same one broadcast even if ten instructions were waiting.

The cheap property is that the CDB is a broadcast medium, not a point-to-point delivery. The producer does not track who needs its result (could be 0, could be 5). It shouts once; matching is done locally by each listener comparing its stored tag. This is why Tomasulo does not maintain a consumer list.

Exercise 3.2 (L3)

Same program as 3.1. Compare Tomasulo against a simple scoreboard on the WAR situation: suppose after issuing we add

4. ADD R5, R8, R9    # writes R5, which instruction 2 reads

Does Tomasulo stall instruction 4 to protect instruction 2's read of R5? Why / why not?

Recall Solution

Instruction 2 (ADD R4, R1, R5) reads R5. Instruction 4 writes R5. Program order says the read must see the old R5. A scoreboard, having no renaming, must stall instruction 4's write until instruction 2 has read R5 (a genuine WAR stall).

Tomasulo does not stall. At Issue time, instruction 2 already captured R5's old value into Add1.Vk (or copied its producer tag). Instruction 4 issues to a new RS and stamps R5.tag with its own name. Instruction 2 no longer looks at the register file for R5 at all — it holds its own private copy. Thus the WAR hazard never materializes; renaming gave each reader a snapshot. This is the headline advantage over scoreboarding: WAR and WAW are eliminated, not just detected.

Exercise 3.3 (L3)

In the parent note's worked example, DIV (Mult2) waits on Add2 (the new R1), not on Mult1 (the old R1). Trace why the dependency routed to Add2 and not Mult1, referencing the exact cycle events.

Recall Solution

Look at the timeline of R1's tag:

Cycle 1: MUL issues, R1.tag ← Mult1.
Cycle 3: SUB issues, R1.tag ← Add2 (overwrite).
Cycle 4: DIV R8, R1, R9 issues. It reads R1's tag at this moment, which is Add2. So Mult2.Qj ← Add2.

DIV therefore listens for Add2, correctly wanting the most recent R1 (SUB's result, 12), not the stale MUL result (6). At cycle 5 Add2 broadcasts <Add2, 12>, Mult2.Qj clears, and DIV starts. Register renaming captured program order automatically: whoever most recently owned R1's tag is whoever the later reader depends on.

Level 4 — Synthesis

Exercise 4.1 (L4)

Build the full issue/tag/timing trace for this program. Assume: MUL=5 cyc, ADD=2 cyc, SUB=2 cyc, DIV=40 cyc; the single CDB with oldest-first arbitration; the clock convention fixed in the CDB definition box (operand latched cycle $c$ ⇒ execute starts $c + 1$ ; $n$ -cycle op starting cycle $s$ finishes $s + n - 1$ , broadcasts $s + n$ if it wins the bus); one RS per unit as needed (Mult1, Mult2, Add1, Add2). One instruction issues per cycle, starting cycle 1. Initial: R2=6, R3=4, R5=1, R6=30, R7=10, R9=3.

1. MUL  R1, R2, R3
2. SUB  R1, R6, R7
3. ADD  R4, R1, R5
4. DIV  R8, R1, R9

Give: (a) which RS each instruction issues to, (b) each instruction's operand state at issue, (c) issue / execute-start / execute-finish / writeback cycle numbers with any CDB-arbitration stalls shown, (d) each numeric result, (e) whether MUL's broadcast is used by anyone.

Recall Solution

(a) RS assignment (in program order, one per free slot):

MUL → Mult1, SUB → Add1, ADD → Add2, DIV → Mult2.

(b) Operand state at issue:

MUL (Mult1): R2,R3 ready ⇒ Vj=6, Vk=4, Qj=NULL, Qk=NULL. Sets R1.tag = Mult1.
SUB (Add1): R6,R7 ready ⇒ Vj=30, Vk=10, Qj=NULL, Qk=NULL. Sets R1.tag = Add1 (overwrites Mult1).
ADD (Add2): reads R1 (tag now Add1) and R5 (ready) ⇒ Qj=Add1, Vk=1. Sets R4.tag = Add2.
DIV (Mult2): reads R1 (tag still Add1) and R9 (ready) ⇒ Qj=Add1, Vk=3. Sets R8.tag = Mult2.

(c) Cycle-by-cycle timing. Apply the fixed convention step by step:

MUL issues cycle 1, operands ready at issue ⇒ execute starts cycle 2, finishes $2 + 5 - 1 = 6$ , broadcasts cycle 7 (bus free) — <Mult1, 24>.
SUB issues cycle 2, operands ready at issue ⇒ execute starts cycle 3, finishes $3 + 2 - 1 = 4$ , broadcasts cycle 5 (bus free) — <Add1, 20>.
ADD issues cycle 3, but $Q_{j} = Add1$ (waiting). Add1's value arrives on the CDB at cycle 5 ⇒ ADD's ready-check passes cycle 5 ⇒ execute starts cycle 6, finishes $6 + 2 - 1 = 7$ , wants the bus cycle 8.
DIV issues cycle 4, also $Q_{j} = Add1$ . Same cycle-5 broadcast clears it ⇒ execute starts cycle 6, finishes $6 + 40 - 1 = 45$ , wants the bus cycle 46.

CDB-arbitration check. List the cycles each result wants the bus: cycle 5 (SUB), cycle 7 (MUL), cycle 8 (ADD), cycle 46 (DIV). All four are distinct, so oldest-first arbitration never has to break a tie here — no writeback is stalled.

Instr	RS	Issue	Exec start	Exec finish	Writeback (CDB)	Waited on
MUL	Mult1	1	2	6	7	—
SUB	Add1	2	3	4	5	—
ADD	Add2	3	6	7	8	Add1 (new R1)
DIV	Mult2	4	6	45	46	Add1 (new R1)

(d) Numeric results:

MUL $= 6 \times 4 = 24$ .
SUB $= 30 - 10 = 20$ ← this is the R1 everyone downstream uses.
ADD $= 20 + 1 = 21$ (uses SUB's 20).
DIV $= 20/3 = 6.6 \overline{6}$ (uses SUB's 20).

(e) Is MUL's broadcast used? No. When MUL broadcasts <Mult1, 24> at cycle 7, R1.tag is Add1 (not Mult1), and no RS has Qj/Qk = Mult1 (ADD and DIV both captured Add1, because SUB overwrote the tag before they issued). MUL's result is computed and thrown away — a dead value. That is the WAW hazard being resolved: the overwritten write's result harms nothing.

Exercise 4.2 (L4)

In Exercise 4.1, both ADD and DIV have Qj = Add1. When Add1 (SUB) broadcasts <Add1, 20> at cycle 5, how many latches fire, and into which fields? List them.

Recall Solution

The broadcast <Add1, 20> is compared against every stored tag. Matches:

Add2.Qj == Add1 → Add2.Vj ← 20, Add2.Qj ← NULL (ADD's operand).
Mult2.Qj == Add1 → Mult2.Vj ← 20, Mult2.Qj ← NULL (DIV's operand).
R1.tag == Add1 → R1.value ← 20, R1.tag ← NULL (register file update).

Three latches fire from one broadcast: two RS operands and one register file entry. All in the same cycle — the whole point of the shared CDB. And they fit in one CDB slot because it is one producer broadcasting; the one-per-cycle limit constrains producers, not listeners.

Level 5 — Mastery

Exercise 5.1 (L5)

A designer proposes removing the register-file .tag fields entirely, keeping only RS tags, to save area. Instructions would read operand values directly from the register file at Issue, and if a value is "not ready" they would... have no way to know. Explain precisely which hazard class breaks, and construct a 2-instruction counterexample producing a wrong result. Then state the minimal fix.

Recall Solution

Which hazard breaks: RAW (true data dependency), read-after-write. The register-file .tag field is the only mechanism that tells a consumer "the value you want isn't produced yet — here is the producer's name to wait on." Delete it and a consumer that issues before its producer finishes will read stale .value bits and treat them as valid.

Counterexample:

1. MUL R1, R2, R3    # R2=2, R3=3  → R1 should become 6, takes 5 cycles
2. ADD R4, R1, R5    # R5=10, issues at cycle 2, R1 not yet 6

With no register tags, at cycle 2 instruction 2 reads R1's old (stale) contents — say the pre-MUL value 99 — and computes R4 = 99 + 10 = 109. The correct answer is 6 + 10 = 16. Wrong result, silently.

Minimal fix: keep at least a .tag field on each register so a consumer at Issue can detect "not ready" and copy the producing RS's name into its $Q$ . This is irreducible — Tomasulo's renaming is the register tag mechanism; RS tags alone cannot bridge the register-file boundary. (See reorder-buffer for a related structure that also carries per-value producer info.)

Exercise 5.2 (L5)

Suppose the CDB can carry only one broadcast per cycle, but in some cycle two functional units finish simultaneously (Mult1 and Add1 both done). Using this page's oldest-first arbitration policy, describe the structural conflict, which unit wins, its effect on the ILP you can extract, and two realistic design responses.

Recall Solution

The conflict: there is one shared broadcast wire, so at most one FU may write per cycle. Two finishers competing for it is a structural hazard on the bus itself.

Who wins: by this page's fixed policy, the oldest instruction in program order broadcasts this cycle; the younger one stalls its Write-Result stage (its RS stays busy, holding the finished value) and retries the next free cycle. Concretely, if Mult1 holds the older instruction, Mult1 broadcasts now and Add1 waits one cycle.

Effect on ILP: every stalled writeback delays the moment dependent instructions receive their operands, which delays their execute start, rippling downstream. As issue width and FU count grow, a single CDB becomes the throughput bottleneck — you can compute in parallel but cannot publish results in parallel.

Two design responses:

Multiple CDBs (e.g., 2–4 buses). Each RS/register now snoops several buses; more comparators, more area, but concurrent broadcasts. This is what real superscalar Tomasulo machines do.
Arbitration + write buffering — keep the fixed oldest-first priority to choose a winner each cycle; losers queue in a small write buffer. Cheaper in wires, but caps writeback bandwidth at one per cycle, so it only helps when simultaneous finishes are rare.

Exercise 5.3 (L5)

Tomasulo as originally described (per the parent note) has no reorder buffer and thus commits results as soon as they are computed. Explain why this makes precise exceptions impossible, and how bolting on a ROB restores them — connecting back to why the same renaming machinery still works. Reference the figure.

Recall Solution

Why precise exceptions break: in plain Tomasulo, a later instruction (in program order) can finish and write its result into the register file first, out of order. Look at the figure: SUB finishes and updates R1 at cycle 5, while the earlier MUL is still running until cycle 6. If MUL now raises an exception (say overflow), the machine's visible register state has already been altered by a younger instruction (SUB's write, and possibly others). There is no clean point to say "the architectural state is exactly as if instructions 1..k completed and k+1 onward did not" — that is the definition of a precise exception, and it is impossible once younger writes have leaked out.

How the ROB fixes it: insert a reorder buffer — a FIFO queue in program order. Now Write-Result deposits the value into the instruction's ROB slot, not the register file. Instructions still execute out of order (throughput preserved), but they commit (write the architectural register file) strictly in program order, one from the head of the ROB per cycle. When MUL's exception is discovered, everything younger than MUL is still sitting uncommitted in the ROB and can simply be flushed — the architectural registers were never touched by them.

Why renaming still works: the tags $Q_{j} / Q_{k}$ now name ROB entries instead of RSs, and the CDB broadcasts <ROB_index, value>. The exact same IOU-and-broadcast mechanism runs; we only changed what the name refers to and added an in-order commit gate at the end. Out-of-order execution + in-order commit = full speed with precise state. (This is the standard modern out-of-order pipeline.)

Two figures below carry the visual intuition the tables only summarize — a broadcast fan-out and an out-of-order timeline.

The picture above is the answer to Exercise 4.2: one producer, one CDB slot, three simultaneous listener latches.

Recall Self-test cloze (do these last, from memory)

The execute condition requires ==both $Q_{j}$ = NULL and $Q_{k}$ = NULL==. A non-NULL register .tag means the register is waiting for the named RS to broadcast. Tomasulo eliminates WAR and WAW hazards via register renaming (RS/ROB tags). The CDB is a broadcast medium carrying one result per cycle, captured by all listeners whose stored tag matches. Precise exceptions require adding a reorder buffer so instructions commit in program order.

Execute condition in symbols?

Q_{j} = NULL \land Q_{k} = NULL

What does a register with .tag = Add2 hold right now?

No trustworthy value — it waits for Add2's CDB broadcast.

Why does an overwritten producer's result harm nothing?

No RS or register still names it; every downstream reader captured the newer tag.

One CDB, two finishers — which wins under this page's policy?

The oldest instruction in program order; the younger stalls its Write-Result stage.

Which two listener groups snoop the CDB?

Every RS's

Q_{j} / Q_{k}

fields and every register's .tag field.