Noesis
4.1.22 · D4Computer Architecture (Deep)

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

2,768 words13 min read↑ Back to topic

Before we start, two pictures that every problem below leans on.

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

The figure above is the anatomy of one reservation station (RS). Read it left to right: a ticket (the instruction) arrives, and each of its two operands is either a value already in hand (stored in Vj/Vk) or a promissory note — a tag naming which other RS will later deliver that value (stored in Qj/Qk). The rule to remember: an instruction can only fire when both note-fields are empty (Qj == 0 and Qk == 0), i.e. every operand is a real value.

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

The second figure is the Common Data Bus (CDB) as a loudspeaker. One functional unit finishes, shouts a (tag, value) pair, and every RS and every register listening for that tag grabs the value in the same cycle. One shout, many listeners — but only one shout per cycle, because there is only one bus.

Throughout, "cycle" means one clock tick. We use the convention:

  • Issue takes 1 cycle.
  • Execute takes the functional unit's latency (given per problem).
  • Write Result (the CDB broadcast) takes 1 cycle.
  • The earliest an instruction can start Execute is the cycle after both operands are ready.

Level 1 — Recognition

Exercise 1.1

For each pair, name the hazard (RAW, WAR, or WAW) and say whether it is a true dependency or just name reuse.

(a) I1: F2 = F4 + F6      (b) I1: F2 = F4 + F6      (c) I1: F2 = F0 + F6
    I2: F8 = F2 + F10          I2: F2 = F8 + F10          I2: F0 = F8 + F10
Recall Solution 1.1
  • (a) I2 reads F2, which I1 wrote. Read-After-Write ⇒ RAW, a true dependency. I2 needs I1's actual result.
  • (b) Both write F2. Write-After-Write ⇒ WAW, name reuse only. Fixed by renaming.
  • (c) I1 reads F0, then I2 writes F0. Write-After-Read ⇒ WAR, name reuse only. Fixed by renaming.

Exercise 1.2

An instruction sits in an RS with Qj = Add1, Vk = 7.0, Qk = 0. Can it execute this cycle? What single event unblocks it?

Recall Solution 1.2

No. Execution requires Qj == 0 and Qk == 0. Here Qk == 0 (operand k is the value 7.0, ready) but Qj = Add1 ≠ 0 — operand j is still a promissory note waiting on RS Add1. The unblocking event is Add1 broadcasting on the CDB: when it shouts (Add1, value), this RS copies that value into Vj and sets Qj = 0. Now both are ready.

Level 2 — Application

Exercise 2.1

Show the RS/register-status contents right after issuing both instructions. Assume F4, F6, F8 already hold real values; F2 does not.

I1: ADD.D F2, F4, F6    -> RS "Add1"
I2: MUL.D F0, F2, F8    -> RS "Mult1"
Recall Solution 2.1

Issue I1: F4, F6 are ready values ⇒ copy them in. Mark that F2 is now owned by Add1.

  • Add1: Busy=yes, Op=ADD, Vj=val(F4), Vk=val(F6), Qj=0, Qk=0
  • Qi[F2] = Add1

Issue I2: source F2 → check Qi[F2] = Add1 ⇒ not a value yet, so store the tag. Source F8 is ready ⇒ store its value.

  • Mult1: Busy=yes, Op=MUL, Vj=—, Qj=Add1, Vk=val(F8), Qk=0
  • Qi[F0] = Mult1

Add1 can fire immediately (both Q's are 0). Mult1 must wait for the Add1 broadcast.

Exercise 2.2

Latencies: ADD.D = 2 cycles, MUL.D = 4 cycles. Issue = 1 cycle, Write = 1 cycle, one instruction issued per cycle, one CDB. Fill in the cycle numbers for Issue / start-Execute / end-Execute / Write for both instructions of Exercise 2.1. I1 issues in cycle 1.

Recall Solution 2.2

I1 (ADD, latency 2):

  • Issue: cycle 1
  • Execute: cycles 2–3 (starts the cycle after issue since operands ready; 2 cycles long)
  • Write (CDB): cycle 4

I2 (MUL, latency 4):

  • Issue: cycle 2 (one per cycle, in order)
  • Execute: cannot start until it has F2. F2 arrives on the CDB in cycle 4, so Mult1 clears Qj end of cycle 4 ⇒ Execute cycles 5–8.
  • Write (CDB): cycle 9.

So I2 finishes at cycle 9. The 2-cycle add plus the 4-cycle multiply, chained by one CDB hop, lands the final result at cycle 9.

Level 3 — Analysis

Exercise 3.1

Consider the WAW/WAR case. F0 already holds a value; F2, F4, F8, F10, F12 hold values.

I1: DIV.D F0, F2, F4    ; RS Div1, DIV latency = 10
I2: ADD.D F6, F0, F8    ; RS Add1, reads F0
I3: SUB.D F8, F10, F12  ; RS Sub1, WRITES F8 (WAR vs I2)

(a) Exactly which field of which RS makes the WAR between I3 and I2 harmless? (b) Can I3 execute before I1 or I2? Why is that safe?

Recall Solution 3.1

(a) At Issue of I2, source F8 is a ready value, so I2 copies it into Add1.Vk immediately — a private snapshot. The field is Add1.Vk holding val(F8) captured at issue. When I3 later writes a new F8, it lands in Sub1's destination; Add1.Vk is untouched. That captured copy is what defuses the WAR. (b) Yes. I3's operands F10, F12 are ready at issue, so Sub1 has Qj=0, Qk=0 and can execute in the very next cycle — long before the 10-cycle DIV (I1) finishes and before I2 (which waits on I1). This is safe because I3 writes its result to its own tag Sub1, and Qi[F8] = Sub1 now points the register file at the latest writer. Nobody who needed the old F8 was relying on the register name — they took a value copy at issue.

Exercise 3.2

Add a fourth instruction:

I4: MUL.D F6, F14, F16  ; RS Mult1, WRITES F6 (WAW vs I2 which also writes F6)

When I2 (Add1) eventually broadcasts (Add1, result), will register F6 be updated by it? Explain using Qi[F6].

Recall Solution 3.2

No. Sequence of Qi[F6]:

  1. Issue I2 ⇒ Qi[F6] = Add1.
  2. Issue I4 ⇒ Qi[F6] = Mult1 (overwrites Add1 — I4 is the later writer, so the register file must ultimately reflect I4).

When Add1 broadcasts, each register checks "does my Qi equal the broadcast tag?" For F6, Qi[F6] = Mult1 ≠ Add1, so F6 ignores Add1's result. The stale earlier write is silently discarded for the register (any RS that captured Add1 as an operand tag still grabs the value — those are real RAW consumers, not the WAW victim). WAW is thus solved with zero extra logic: last issuer wins the register name.

Level 4 — Synthesis

Exercise 4.1

You have 1 CDB, latencies ADD=2, MUL=4. Two multiplies I1, I2 both finish their Execute stage in the same cycle 8 and both want to broadcast. What happens, and what is the cost in cycles? Then argue what a second CDB would change.

Recall Solution 4.1

The CDB is a single shared bus: only one (tag, value) per cycle. Arbitration picks one — say I1 broadcasts in cycle 8, so I2 must stall its Write until cycle 9 (I2 sits in its RS holding its finished result, occupying the RS one extra cycle). Cost: +1 cycle of latency on I2, plus I2's RS stays Busy one cycle longer, which can cause a downstream structural stall if a new instruction needed that RS.

A second CDB lets both broadcast in cycle 8 (each on its own bus). Every RS/register now snoops two buses. This removes the +1 stall but costs hardware: wider comparators at every RS (each must match against 2 tags) and more wiring — the classic area-vs-throughput trade. This is why superscalar designs, which retire several instructions per cycle, often need multiple CDBs.

Exercise 4.2

The parent note says classic Tomasulo does not give precise interrupts. Design the minimal addition that fixes this, and state the one rule it enforces.

Recall Solution 4.2

Add a Reorder Buffer (ROB). Instructions still Execute and produce results out of order (kept in the ROB, tagged by ROB entry instead of / alongside RS tag), but a new final stage — Commit — retires ROB entries strictly in program order. The one rule: architectural state (register file, memory) is updated only at Commit, and Commit happens in issue order. So if instruction I raises an exception, every instruction before I has already committed and none after I has, giving a precise, restartable machine state. This also cleanly supports speculation: a mispredicted branch simply flushes the not-yet-committed tail of the ROB.

Level 5 — Mastery

Exercise 5.1

Full trace. Hardware: 2 Add RSs, 2 Mult RSs, 1 CDB. Latencies: ADD.D/SUB.D = 2, MUL.D = 4, DIV.D = 10. One issue per cycle; Execute starts the cycle after operands ready; Write takes 1 cycle; CDB one broadcast/cycle (lower-issue-order wins ties). All source registers initially hold values except those written by an earlier instruction below.

I1: MUL.D F0, F2, F4
I2: SUB.D F8, F0, F6   ; RAW on F0 from I1
I3: MUL.D F10, F8, F0  ; RAW on F8 (I2) and F0 (I1)

Give Issue / Execute-start / Execute-end / Write cycle for each. Assume I1 issues in cycle 1.

Recall Solution 5.1

I1 MUL (lat 4): Issue 1; operands ready ⇒ Execute 2–5; Write 6.

I2 SUB (lat 2): Issue 2. Needs F0 (tag from I1). F0 broadcast in cycle 6, so operands ready end of 6 ⇒ Execute 7–8; Write 9.

I3 MUL (lat 4): Issue 3 (a free Mult RS exists — 2 available). Needs F8 (from I2, broadcast cycle 9) and F0 (from I1, broadcast cycle 6). The later arrival gates it: F8 at cycle 9 ⇒ Execute 10–13; Write 14.

CDB check: broadcasts happen in cycles 6, 9, 14 — all distinct, so no CDB conflict and no arbitration stall. Final result (F10) is ready at cycle 14.

Exercise 5.2

Same program as 5.1 but change I3's source F0 to a fourth new instruction's result and stress the CDB:

I1: MUL.D F0, F2, F4    ; lat 4
I2: MUL.D F6, F2, F4    ; lat 4, independent of I1

If both issue in cycles 1 and 2 with 1 CDB, when does each Write? What is the throughput cost of the single bus here?

Recall Solution 5.2

I1: Issue 1, Execute 2–5, wants to Write 6. I2: Issue 2, Execute 3–6, finishes execute at cycle 6 and wants to Write cycle 7 naturally — wait, let's be exact: I2 execute is cycles 3–6, so its result is available to broadcast in cycle 7. I1 broadcasts cycle 6. No collision — they are one cycle apart.

Now the stress: if I2 had issued in cycle 1 as well (impossible with 1-issue/cycle, but imagine a 2-issue machine), both would execute 2–5 and both want cycle 6 → collision → I1 wins cycle 6, I2 forced to cycle 7 (+1 stall). Throughput cost: with one CDB the machine cannot retire more than one result per cycle, so a 2-wide execution engine is throttled to 1 write/cycle — the bus caps effective IPC at 1 regardless of how many functional units finish together. That cap is exactly why real superscalar cores widen the CDB.

Recall Self-test summary

Renaming target of a source register at issue ::: its producer's RS tag (into Qj/Qk), or the value if ready (into Vj/Vk) Cycle gate for a dependent instruction's Execute ::: the cycle after its producer's Write/CDB cycle Why WAW on a register is auto-solved ::: Qi[dest] points to the last issuer; earlier writers' broadcasts are ignored because their tag no longer matches Structural limit of a single CDB ::: at most one result broadcast (retire) per cycle Minimal add for precise interrupts ::: a Reorder Buffer (ROB) that commits in program order