Tomasulo under pressure: structural squeezes and CDB fights

Two papers, one machine family

Both exercises use the machine family of every official paper: a few reservation stations per class (two, sometimes one), named functional units with a latency, a single Common Data Bus, all cache hits. The stage rules and the table conventions are the ones of lesson 12; here they are only applied. Two things change from paper to paper and decide everything: how many stations and units each class gets, and which class the instructions crowd into.

The February 2025 paper (notes, page 542) numbers its instructions I0 to I7; the notes print the registers of the older papers with a dollar sign ($F0, $R0), the June 2026 paper drops it, and so does this lesson.

I0: LD   F0, A(R0)
I1: LD   F2, B(R0)
I2: FADD F4, F0, F2
I3: FADD F6, F4, F4
I4: SD   F4, C(R0)
I5: SD   F6, D(R0)
I6: ADDI R0, R0, 4
I7: BNE  R0, R1, LOOP

Machine of the February paper: 2 reservation stations (RS1, RS2) with 2 load/store units (LDU1, LDU2), latency 6; 2 reservation stations (RS3, RS4) with 2 FP units (FPU1, FPU2), latency 2; one reservation station (RS5) with 1 INT_ALU/BR unit (ALU1), latency 1. The memory latency is long, the FP latency short, and the integer class has a single station.

The midterm of 5 May 2025 (notes, page 514) numbers its loop body I1 to I10, as printed. It is the software-pipelined body that lesson 21 schedules on a VLIW; here it runs on Tomasulo, a different machine with different latencies, so do not compare the two CPIs.

I1:  SD    F4, 0(R1)
I2:  SD    F6, 0(R2)
I3:  FADD  F4, F0, F0
I4:  FADD  F6, F2, F2
I5:  LD    F0, 16(R1)
I6:  LD    F2, 16(R2)
I7:  ADDUI R1, R1, 8
I8:  ADDUI R2, R2, 8
I9:  ADD   R3, R2, R1
I10: BNE   R3, R4, SP_LOOP

Machine of the midterm: 2 reservation stations (RS1, RS2) with 2 load/store units (LDU1, LDU2), latency 4; 2 reservation stations (RS3, RS4) with one FP unit (FPU1), latency 4; 2 reservation stations (RS5, RS6) with 2 INT_ALU/BR units (ALU1, ALU2), latency 2. Four memory instructions for two stations, two FP additions for one unit, and one bus for ten results.

The dependence tables, recomputed

Part 1 of the February exercise asks for every true, anti and output dependence of the fragment, "with I# for Fx". Read each instruction from its sources: a true dependence (RAW) is a source written by an earlier instruction; an anti-dependence (WAR) is a destination that an earlier instruction still reads; an output dependence (WAW) is a destination written twice. A store has no destination at all, so I4 and I5 can only be readers in such a table; and I3 reads F4 twice but owes it to I2 once.

Every destination (F0, F2, F4, F6, R0) is written exactly once, so there is no output dependence; the four anti-dependences sit on an integer register although the template says "$Fy" — write R0 anyway. The dependences that cross to the next iteration (the next I0 reads the R0 that I6 wrote) are not asked.

The midterm's body (notes, page 513) is the opposite picture. Software pipelining has moved the data chain out of the iteration: the stores read the F4 and F6 of the previous pass, the additions read the F0 and F2 loaded in the previous pass. What is left inside the body is name reuse, plus the control tail.

So the FP half of the midterm never waits for a value. Keep that in mind: every cycle it loses from here on is structural — a station, a unit or the bus was taken — and the exam's Hazards column must say so.

February: a closed door at cycle 5

Walk the February paper with the rules, a few cycles per step; the table after the steps is what they build.

1. Cycles 1–2. I0 issues into RS1 with its base register copied (Vk = R0) and starts on LDU1 at 2: six cycles, Write Result at 8. I1 issues into RS2 at 2.

2. Cycles 3–4. I1 starts on LDU2 (write at 9). I2 issues into RS3 with neither operand ready: its fields hold the tags Qj = RS1 and Qk = RS2, the names of the stations that will produce F0 and F2 — parked, not stalled. I3 issues into RS4 with Qj = Qk = RS3. Both FP stations are now full, both FP units idle: nobody has operands.

3. Cycle 5 is the cycle of the lesson. I4 is a store and needs a load/store station; RS1 holds I0 through its Write Result at 8, RS2 holds I1 through 9. No station, no issue: structural hazard, written STRUCTURAL in the Hazards column. And because issue is in order, the door is shut for everybody: I5 cannot issue, I6 cannot issue although R0 and the constant 4 are ready and ALU1 is idle, I7 cannot issue.

4. Cycles 6–8. Only countdowns, until I0 broadcasts F0 with the tag RS1 at 8: RS3 captures it, and RS1 is free from the next cycle.

5. Cycles 9–11. I1 broadcasts F2 at 9; RS3 has both operands; I4 at last issues into RS1, with Qj = RS3 for its store data and Vk = R0. At 10 I2 starts on FPU1 (write at 12) and I5 issues into RS2 with Qj = RS4. At 11 I6 issues into RS5 with both operands — six cycles late for a reason that has nothing to do with its own data.

6. Cycles 12–13. I2 writes F4: RS4 and RS1 capture it; I6 starts on ALU1. I7 wants the only integer station, RS5, busy with I6 through its write at 13: STRUCTURAL again. At 13 I3 starts on FPU2 (FPU1 would do as well: only the latency matters), I4 starts its six-cycle store on LDU1, and I6 writes the new R0 while I4 and I5, which read the old R0, have not finished — harmless, because each station holds its own copy.

7. Cycles 14–22. I7 issues at 14 with the new R0 and starts at 15. I3 writes F6 at 15 and RS2 captures it; I5 starts at 16, the cycle in which I7 resolves. Then only countdowns: I4 writes at 19, I5 at 22.

The eight Write Result cycles — 8, 9, 12, 13, 15, 16, 19, 22 — are all different, so the single bus never has to choose. That is why this paper is the clean one: its 22 cycles are made of the long memory latency and one structural hole.

What the hole did not change

Here is the first half of the puzzle. Give the February machine a third load/store station. I4 now issues at 5 (into RS3, with the FP stations renumbered RS4 and RS5), I5 at 9, I6 at 10 and I7 at 14; I6 even loses the bus at cycle 12 to the older I2 and writes at 13. The last Write Result is still 22, the CPI still 2.75. Look at the arrows of Fig. 2: I1 broadcasts at 9, I2 computes 10–11 and broadcasts at 12, I3 computes 13–14 and broadcasts at 15, I5 stores 16–21 and writes at 22. That chain is made of latencies and broadcasts only; no station count shortens it. What shortens it is a shorter latency: with FP latency 4 instead of 2 the same chain ends at 26 (CPI 3.25); with memory latency 4 instead of 6 it ends at 18 (CPI 2.25).

A missing station delays when instructions enter; a dependence chain of latencies decides when the last one leaves — and the table's last cycle belongs to the chain.

The midterm: when the bus is the bottleneck

Now the midterm, where the FP side owes nothing to anybody. Step through it; the table and the timeline below are the result.

1. Cycles 1–4. I1 issues into RS1 with its copy of F4 and starts the store at 2 (latency 4: write at 6), so RS1 is busy through 6. I2 issues at 2, starts at 3, writes at 7. I3 issues at 3 with F0 ready in both operand fields and starts on FPU1 at 4 (write at 8). I4 issues at 4 with F2 ready.

2. Cycle 5. I4 has its operands, but the only FP unit belongs to I3 through its Write Result at 8 — a structural wait at Start Exec, not at issue: Start Exec 9, Write Result 13. The single unit costs it four cycles (Start Exec 9 instead of 5). And I5, a load, finds RS1 busy until 6 and RS2 until 7: the door is shut again, this time for two cycles.

3. Cycles 6–11. I1 writes at 6, I2 at 7, I3 broadcasts F4 at 8 — nobody waits for it: I1 copied the old F4 at cycle 1, which is the anti-dependence being free. I5 issues at 7, the cycle after RS1's release, and starts at 8; I6 issues at 8, starts at 9; I7 issues at 9, starts on ALU1 at 10; I8 issues at 10, starts on ALU2 at 11 — each two cycles later than its ideal slot. At 11 I9 wants an integer station: RS5 and RS6 are both busy, so it waits, and I10 waits behind it.

4. Cycle 12 starts the fight. Two results are ready: I5 (started 8, latency 4) and I7 (started 10, latency 2). One bus, one result per cycle, oldest first: I5 writes F0, I7 waits and keeps RS5.

5. Cycles 13–16. At 13 four results are ready — I4 (9 + 4), I6 (9 + 4), I7, I8 (11 + 2). The oldest, I4, writes F6; then I6 writes F2 at 14, I7 writes R1 at 15 and I8 writes R2 at 16, in program order. I7's write slipped from 12 to 15, so RS5 is free only from 16.

6. Cycle 16. I9 issues into RS5, blocked since 11: three of its five lost cycles are the bus queue, two the two-cycle latency of the ADDUIs. R1 is in the register file and R2 is broadcast in this very cycle, so the station holds both values by the end of it.

7. Cycles 17–22. I9 starts on ALU1 at 17 and writes R3 at 19. I10 issues at 17 into RS6 with Qj = RS5 (the station of I9) and Vk = R4, captures R3 from the bus at 19, starts on ALU2 at 20 and writes at 22. Ten instructions, 22 cycles, CPI 2.2 — and the only true wait in the whole table is the two cycles I10 spends on R3; everything else was a station, a unit or the bus.

Count where the 22 cycles come from and you find three structural causes — two load/store stations too few at 5–6, one FP unit at 5–8, one bus at 12–16 — and a single true wait, the two cycles I10 spends on R3. The causes form one chain from the first cycle to the last: I1's write at 6 frees RS1 for I5 (issue 7, write 12); the bus queue pushes I7's write to 15, which frees RS5 for I9 (issue 16, write 19); I10 starts at 20 and writes at 22.

Tags, not registers

Cycle 17 shows the one idea of Tomasulo that the exam checks in the station snapshots. I10 issues although R3 does not exist yet: a station needs no values to be allocated, only a free slot. In the Qj field of RS6 it writes the tag of the producer — RS5, the station holding I9 — and from then on it listens to the bus. When I9 finishes on ALU1, the bus carries the pair <RS5, value>; RS6 compares the tag with its Qj, matches, copies the value into Vj and clears Qj. The register file does the same with its own tag field for R3. Nothing in this exchange names ALU1. A unit is not a producer: it serves one station after another (ALU1 runs I7, then I9; in the FP class RS3 and RS4 share the single FPU1), so "the result of ALU1" would not say which instruction's result it is. The tag is the station, because a station holds exactly one instruction from issue to Write Result.

One bus, one result per cycle, oldest first — and a result that waits for the bus keeps its station, so the bus can block the issue of instructions that never needed a bus at all.

Step it, then change the machine

The stepper runs both papers, and the official June 2025 paper as a contrast, with the conventions of this course. Every cycle lists its events and its refusals — a shut door, a busy unit, a lost bus — and the table and the timeline fill in as you go. The what-if controls change the machine relative to the paper: a second bus or unlimited buses, one more FP unit, one more load/store or integer station.

The what-if table

Every number below comes from the same rules as the two tables above; the stepper reproduces each line.

The official contrast: when the bus bites twice

The official paper of 10 June 2025 uses the same exercise family with two units in every class, latencies 4, 3 and 2. Its three loads fill the two load/store stations at once, so I2 issues only at 7; and twice two results are ready in the same cycle. Here is the model answer in this course's conventions (no official solution exists; the numbers are recomputed).

I0: FOR: LD    F2, A(R1)
I1:      LD    F4, B(R1)
I2:      LD    F6, C(R1)
I3:      FADD  F4, F2, F4
I4:      FADD  F6, F4, F6
I5:      SD    F6, A(R1)
I6:      ADDUI R1, R1, 8
I7:      BNE   R1, R2, FOR

Two things to say on the sheet. First, whether a branch takes a bus slot is not stated in the papers; this course lets it (it writes at 18), and an answer that writes 17 with the remark "the branch produces no register value" is defensible — the CPI is 22 / 8 = 2.75 either way, because the store I5 ends the table. Second, write the collision explicitly: "Structural (CDB at 12: I2 writes first)" is what turns a right number into a justified one.

The puzzle, answered

February: no station, no unit and no bus would change 22. Its last cycle is the chain F2 → F4 → F6 → memory, 6 + 2 + 2 + 6 cycles of latency plus the broadcasts between them; the shut door delayed four instructions by four cycles and cost not one cycle of the total. The only hardware that helps is faster hardware. The midterm: the bus. A second CDB takes the loop from 22 to 20 cycles, unlimited buses to 19, while a second FP unit buys one cycle and a third integer station none. Two ALUs sat idle for most of the 22 cycles; what they were waiting for was a slot on the bus and a free station behind it.

Reading and writing the Hazards column

The column is where the examiner sees whether you know why a number is what it is. Write one label per cause, in the order the causes happened to the row. None: nothing delayed the row — issue at the cycle after the previous instruction, start the cycle after issue, write at start plus latency. Structural (which stations, which cycles): the row issued late because every station of its class was busy; name the stations and the cycles, as in "RS1, RS2 busy, cycles 5–8". A row behind such a row issued late too: say "issue delayed behind I4". Structural (unit): the row started late because the unit was busy — "FPU1 busy with I3 until 8". Structural (CDB at c: I# first): the row wrote late because an older result took the bus. RAW with I# (Fx): the row started the cycle after that producer's Write Result; if the operand was already there at issue, say so, as the June table does. WAR / WAW with I# (Fx): renamed: optional, and worth a line, because it shows you know they cost nothing.

Two of these causes are present in every exam machine, whatever the code: the single bus and the non-pipelined units. The second widget isolates them on a small fragment with a mix of dependent and independent instructions. Machine: 2 load/store stations with LDU1 and LDU2 (latency 4), 3 FP stations with one FPU1 (latency 3), 2 integer stations with one ALU1 (latency 2).

I0: LD    F0, 0(R1)
I1: LD    F2, 8(R1)
I2: FMUL  F4, F0, F0
I3: FMUL  F6, F2, F2
I4: FADD  F8, F4, F6
I5: ADDUI R1, R1, 16
I6: SUBI  R2, R2, 1
I7: BNE   R2, R3, LOOP

Every exam table hides the same two taxes: a non-pipelined unit spreads results out, a single bus serialises the ones that still arrive together — and both are paid at Write Result, where the station is released.