Names, not values: Tomasulo’s architecture

Three instructions, one name: why rename at all

Lesson 7 sorted the ways two instructions can collide into three kinds. Only one of them, RAW, is about a value: the second instruction needs what the first one computes. The other two are about a name. In a WAR hazard a later instruction writes a register that an earlier one still has to read; in a WAW hazard two instructions write the same register and the second write could land first. The notes call them false dependences (page 142): the instructions “appear to depend on each other because they use the same register name, but there is no true data dependency between them”. Different values are fighting over one name.

The whole lesson runs on the fragment the notes use, written in the mnemonics of the exam papers. The notes spell it DIV.D, ADD.D, S.D, MUL.D (page 142), the spelling of Hennessy and Patterson; the papers write FDIV, FADD, SD, FMUL, and so does this notebook. Older papers write $F6; the 2026 paper drops the dollar sign.

I0: FDIV F0, F2, F4
I1: FADD F6, F0, F8      ; RAW on F0 with I0
I2: SD   F6, 0(R1)       ; RAW on F6 with I1
I3: FMUL F6, F10, F8     ; WAW on F6 with I1, WAR on F6 with I2

Read the last line twice. I3 must not deliver its product into F6 before I1 has delivered its sum (WAW), and not before I2 has read that sum (WAR). Neither rule asks I3 to wait for a value: F10 and F8 are ready. Both ask it to wait for the name F6 to become free. On the scoreboard the WAW check happens at Issue, so I3 waits there — and because issue is in order, everything behind it waits too.

Static renaming: let the compiler pick another name

The oldest cure is a second name. If the compiler has a spare register S, it can send the sum there and let the store read it; the multiply keeps F6, and the two name conflicts are gone while the RAW chain is untouched:

I0: FDIV F0, F2, F4
I1: FADD S,  F0, F8      ; RAW on F0, as before
I2: SD   S,  0(R1)       ; now reads S
I3: FMUL F6, F10, F8     ; nobody else uses F6 any more

The notes name the two limits (page 142). The compiler must know every hazard in advance, which means knowing the whole execution path — hard with branches, loops and inputs that change. And every spare name costs an architectural register, a number that has to fit in the register field of the instruction; the ISA may not have one to spare. The machine of the hook is the extreme case: the System/360 had only four floating-point registers, so the compiler had nothing to rename into.

Implicit renaming: let the hardware invent names it never shows

Tomasulo’s answer is to give the result a name that exists only inside the machine. The buffer in front of a functional unit that holds a waiting instruction — the reservation station — becomes the temporary name, the tag, of the result it will produce. The notes picture it as a rewrite of the code (page 143), with the sum sent to “RS1” and the store reading “from RS1”:

I0: FDIV F0, F2, F4
I1: FADD RS1, F0, F8     ; the sum will be known as RS1
I2: SD   RS1, 0(R1)      ; the store waits for RS1, not for F6
I3: FMUL F6, F10, F8     ; its own write to F6 collides with nobody

Take the listing as a picture, not as a mechanism: no instruction text is rewritten. The renaming lives in two kinds of fields, one in the station and one in the register file, and the next section fills them in. The before/after pair shows what changes.

RAW is about a value and stays; WAR and WAW are about a name and disappear the moment every result gets a name of its own.

A station holds a value or a name

Page 144 of the notes calls the reservation stations “Tomasulo’s brain”, and the reason is where they sit. The scoreboard kept one central table and asked it before every move. Tomasulo puts the control next to each functional unit: the adder has its own small buffers, the multiplier has its own, the memory unit has its own. Each buffer holds one issued instruction together with everything it needs to decide, alone, when to go. The fields of one station are few, and the exam expects you to know them by name.

For each operand exactly one of the pair is meaningful at any moment: either Vj holds the value, or Qj names who will deliver it. A station whose two Q fields are 0 is ready; a station with a non-zero Q field is waiting — not for a register, but for a tag to come down the bus. The notes’ slogan on page 144 says it in one line: “We no longer wait for registers, we wait for values, and when they’re ready, we go.”

The register file gets a matching field. Each register Fi now carries its value Vi and a tag Qi (page 147): the name of the station that will produce the next value of the register. Qi = 0 means the value is valid, use it; Qi = RS4 means “F2 will come from RS4”. The tag is written at issue, by the instruction whose destination the register is, and it is overwritten by every later instruction that writes the same register. So the register remembers only its newest writer: older claims are simply forgotten. That single rule is the renaming.

The bus that shouts a name

Now the third piece, the one that ties the fields together. When a functional unit finishes, the result does not go to its destination register first. It is put on the common data bus (CDB) together with the tag of the station that produced it — the pair <tag, value> — and three things happen at once (page 145): every station whose Qj or Qk equals the tag copies the value into Vj or Vk and clears the tag; the register file writes the value into every register whose Qi equals the tag and clears that Qi; and the producing station becomes free. The notes call this “a kind of hardware-level forwarding, operands are handed off before they hit the register file” — the forwarding path of lesson 2, generalised to every unit at once.

Two consequences are the heart of the exam questions on this topic. First, the tag on the bus is the name of the producer, never of the destination register. A normal data bus says “this value goes to F2”; the CDB says “this value comes from RS1”, and every consumer decides for itself whether it was waiting for RS1. (This “come-from” reading is standard lecture material on Tomasulo’s algorithm; the notes do not use the word.) Second, the register is written only if its Qi still matches: if a later instruction has renamed the register to its own station, the register ignores the broadcast — the value still reaches every station that was waiting for it, so nobody loses anything, and the register keeps its promise to the newest writer. That is how a WAW hazard dies without a single stall.

Try it on the loop body of the 15 July 2024 paper, the first exercise of that exam. Imagine all six instructions issued and no result written yet. The loads and the store share stations RS1 and RS2 in front of the two load/store units, the two FADD share RS3 and RS4 in front of the FP unit, the integer instructions RS5 and RS6 in front of the ALU — the exam’s standard machine.

I0: LD    F2, A(R1)
I1: FADD  F2, F2, F2      ; RAW on F2 with I0, WAW with I0
I2: FADD  F2, F2, F4      ; RAW on F2 with I1, WAR and WAW with I1
I3: SD    F2, A(R1)       ; RAW on F2 with I2
I4: ADDUI R1, R1, 8       ; WAR on R1 with I0 and I3
I5: BNE   R1, R2, FOR     ; RAW on R1 with I4

Read the tables as sentences before you touch the widget. RS3 says: “I add two copies of whatever RS1 delivers.” RS2 says: “I store at address 100 whatever RS4 delivers” — and notice that it already holds R1 = 100, copied at issue, so the ADDUI in RS5 can change R1 whenever it likes. The register status says: “F2 will come from RS4, R1 from RS5.” F2 has been promised three times, by I0, I1 and I2; only the newest promise is kept.

A tag is the name of a producer: one broadcast fills every field that carries it, and a register takes it only if its Qi still says so.

The whole machine: Figure 26 end to end

The notes’ Figure 26 (page 149) is Hennessy and Patterson’s drawing of the floating-point unit of a RISC-V processor built this way — in the 5th edition the same figure is drawn for MIPS. Figure 2 redraws it. Follow one floating-point instruction and one load through it; every block has a job you now know.

An FADD leaves the queue in program order, travels on the operation bus to a free adder station, and fills it: values from the FP registers over the operand buses where Qi = 0, tags where it is not. Its destination register gets the station’s name as Qi. The station then watches the CDB until both Q fields are 0, sends the operation into an adder when one is free, and finally puts <tag, value> on the bus. A load takes the other path: the address unit adds the base register and the offset, the load buffer waits for the memory unit, and the loaded value goes on the same bus with the load buffer’s tag — a load is a producer like any other.

Loads and stores: the buffer that listens but never speaks

Memory operations need two steps instead of one, and the notes separate them (page 147). A load buffer first computes the effective address, base register plus offset, then waits for the memory unit and reads. A store buffer needs two things before it can act — the address and the data — and either may be a tag, so store buffers monitor the CDB like any reservation station. When both are present it writes memory. What it never does is put anything on the bus: a store has no destination register, so no station and no Qi can be waiting for its tag. That missing arrow is the whole difference between the two panels of Figure 3, and the exam quizzes it directly.

One bus, one result per cycle

Look at Figure 2 once more and count how many things hang on the CDB: every reservation station, every store buffer, every register. That is why one broadcast can wake everybody at once — and it is also the price. A bus can carry one <tag, value> per cycle, so one CDB means one result per cycle, however many units finish together; the exam’s “single Common Data Bus” is exactly this rule, and the older instruction gets the bus first (lesson 12). Behind the rule sits hardware the notes do not mention: every station and every register compares its tag with the bus every cycle — associative compares at full speed — and the bus fans out to every unit, so it is long, loaded and slow to drive. More buses mean more comparators everywhere. (Standard lecture material on Tomasulo’s drawbacks; the notes list only the benefits.)

Page 148 sums up why the design works, and the four reasons are the four blocks you have just seen: issue is decoupled from operand readiness, so out-of-order execution is natural; several stations per unit let several instructions of one type be in flight; the register file need not remember everything, because the stations hold the values and the dependences; and the broadcast hands every waiting unit what it needs without any central control. The notes’ word for the result is dataflow-like (page 145): an instruction runs when its operands are ready, not when a global scheduler says so.

Issue, execute, write result: the flow in three steps

Page 150 ends with the execution flow, and it is shorter than the scoreboard’s: three steps, not four. There is no Read Operands stage, because reading happens at issue (the values that exist) or on the bus (the ones that do not). Each step has one condition that lets an instruction through; the stepper states it and says why it is the right one. The exact rules for the exam table — what “the cycle after” means, ties on the bus, when a station is reusable — are lesson 12; the full cycle-by-cycle run of the notes’ six-instruction example is lesson 13.

1. Issue (instruction queue → station), in program order. Condition: a station of the right type is free. Copy the instruction in; for each source register copy the value into Vj/Vk if Qi = 0, otherwise copy the register’s Qi into Qj/Qk; then set the destination register’s Qi to this station’s tag. Why in order: the renaming must see the instructions in program order, so that Qi always names the latest writer and every later reader captures the right producer. If no station is free the instruction waits — a structural hazard — and so does everything behind it.

2. Execute (station → functional unit), out of order. Condition: Qj = Qk = 0 and the unit is free. The station sends the operation into the unit, which computes for its latency. Why operands and not order: a RAW dependence is the only thing the hardware still has to honour, and “both tags cleared” is exactly “both producers have broadcast”. The station stays Busy while the unit works — it still has to deliver the result.

3. Write result (unit → CDB), out of order. Condition: the CDB is free. Put <tag, value> on the bus; every station with a matching Qj/Qk fills the field and clears the tag; every register with a matching Qi is written and its Qi cleared; the station becomes free. Why the register is written at all when the consumers already have the value: instructions issued later will read the register file, and Qi = 0 tells them the value there is good.

Issue needs a free station; execute needs both tags at 0 and a free unit; write result needs the bus.

Scoreboard versus Tomasulo, and the answer to the puzzle

The notes compare the two machines twice, in Table 16 (page 141) and Table 17 (page 145). Merged, with the vocabulary of lesson 9 on the left:

Every row of the table is one consequence of renaming, and the widget below shows the first two on the fragment of the hook. The two timelines run on the same machine — one station per unit, FDIV 7 cycles, FADD and FMUL 3, the store 4, operands usable the cycle after their producer writes, one CDB — and the switch changes one thing only: whether a second writer of a register must wait for the name (the scoreboard’s two rules: WAW at issue, WAR at write result) or gets a tag of its own.

The answer to the puzzle

What Tomasulo’s machine changed is the meaning of “F6”. On the scoreboard F6 is a place: one cell, and whoever wants to write it must wait until the previous writer has written and the previous reader has read. In Tomasulo’s machine F6 is a promise: the cell records the name of the station that will write it last, and nothing else. The sum of I1 is called RS-whatever-the-adder’s-station-is from the moment it is issued; the store asks for that name, not for F6; the multiply, issued two cycles later, writes its own name into F6.Qi and runs. When the sum finally arrives on the bus it goes to the store, which was waiting for it, and is ignored by F6, which has promised itself to the multiply. No stall, no wrong value — and no change to the code, because the compiler never sees a station name.

State the cost next to the benefit, as the open question of the exam expects. The benefit: WAR and WAW can never stall or corrupt, only true dependences remain, and the machine runs code compiled for other implementations because the renaming is invisible to the ISA — the ISA’s register count no longer limits what can be in flight. The cost: every station and every register is an associative comparator on the bus, the bus itself is the throughput limit, and results are still written out of order, so an exception leaves the registers in a state no sequential program would have produced — the problem that the reorder buffer of lesson 17 fixes.