Tomasulo's algorithm

Intuition The Core Idea

Imagine a restaurant kitchen where orders (instructions) arrive in sequence, but different stations (execution units) work at different speeds. The head chef doesn't force Station2 to wait for Station 1 to finish—instead, they track which ingredients (operands) each station needs and let them start cooking as soon as those ingredients arrive, even if earlier orders are still cooking. Tomasulo's algorithm is this kitchen management system for CPUs: it removes register name dependencies by tracking the actual data each instruction needs, letting the CPU execute instructions out-of-order while maintaining the illusion of sequential execution.

Why this matters: Without this, a slow division would stall every instruction behind it, even unrelated additions. Tomasulo extracts instruction-level parallelism (ILP) hidden in sequential code, boosting throughput 2-3× on typical workloads.

What Problem Does Tomasulo Solve?

The Register Name Problem (WAR/WAW hazards):

DIV  R1, R2, R3    # Slow: takes 40 cycles
ADD  R4, R1, R5    # Must wait for DIV (true dependency)
SUB  R1, R6, R7    # Overwrites R1 - WAW hazard with DIV!
MUL  R8, R1, R9    # Which R1? The DIV result or SUB result?

Without Tomasulo:

ADD waits (correct—needs DIV's result)
SUB waits even though it doesn't need DIV (false dependency on the name R1)
MUL is blocked by this pile-up

Tomasulo's solution: Register renaming in hardware. The algorithm tracks "who produces the value I need?" instead of "which register name holds it?"

How Tomasulo Works: The Three Key Structures

The Big Idea: Instructions don't fight over register names. They fight over reservation station slots. The RS name becomes a temporary register name.

The Algorithm: Three Stages

Stage 1: Issue (Dispatch)

What happens:

Fetch the next instruction from the queue
Check if the corresponding functional unit has a free reservation station
If yes: allocate the RS, read operands from registers or copy the producing RS's tag
Update the destination register's tag to point to this RS

Why this works:

DIV R1, R2, R3  # Issues to Mult1. R1.tag ← Mult1
SUB R1, R6, R7  # Issues to Add1.  R1.tag ← Add1 (overwrites!)

Now R1 points to Add1, not Mult1. Later instructions reading R1 will wait for Add1, not the old DIV. The DIV result will be broadcast on the CDB, but no one is listening for it anymore—WAW hazard eliminated.

Structural hazard: If no free RS, the instruction stalls at Issue. This prevents over-subscription.

Formula Issue Logic (Pseudocode)

if RS[FU].available:
    RS[FU].Op ← instruction.opcode
    # Source operand1
    if RegFile[src1].tag == NULL:
        RS[FU].Vj ← RegFile[src1].value
        RS[FU].Qj ← NULL
    else:
        RS[FU].Qj ← RegFile[src1].tag  # Wait for producer
    # Source operand 2 (similar)
    if RegFile[src2].tag == NULL:
        RS[FU].Vk ← RegFile[src2].value
        RS[FU].Qk ← NULL
    else:
        RS[FU].Qk ← RegFile[src2].tag
    
    # Mark destination
    RegFile[dest].tag ← RS[FU].name
    RS[FU].busy ← true
else:
    stall

Why copy the tag, not wait? Because the producer might not have finished yet. The tag is a "I'll tell you later" IOU.

Stage 2: Execute

What happens:

Monitor the CDB. When a needed operand arrives (Qj or Qk matches a broadcast tag), capture the value and clear the tag
When both operands are ready (Qj == NULL and Qk == NULL), send the instruction to the functional unit for execution
Execution may take multiple cycles (e.g., 40 for DIV, 5 for MUL)

Why monitor the CDB?

Add1 waits for Mult2 (Qj = Mult2, Vj = empty)
Mult2 finishes, broadcasts: <Mult2, 3.14>
Add1 sees "Mult2", grabs 3.14, clears Qj
Add1 now has both operands, starts execution

No scoreboard stalls: Unlike simple scoreboards, Tomasulo doesn't stall on WAR hazards. If SUB R1, R6, R7 issues while ADD R4, R1, R5 is executing, SUB gets a new RS tag (Add2). ADD still has the old R1 value or is waiting for its producer—it doesn't care that R1's tag changed.

Stage 3: Write Result (Broadcast)

What happens:

Functional unit finishes. It broadcasts <RS_name, result_value> on the CDB
All reservation stations and register file entries listening for RS_name latch the value
The producing RS is freed (dealocated)
The destination register's tag is cleared (if it still points to this RS)

Critical detail: "if it still points to this RS." If a later instruction overwrote the tag (WAW case), the register ignores this broadcast. Example:

Mult1 (R1 ← ..) finishes, broadcasts <Mult1, 7>
But R1.tag = Add1 (from a later SUB R1, ...)
R1 ignores the broadcast. Add1 will overwrite R1 later.

Formula CDB Broadcast Protocol

on FU_finish(RS[i], result):
    broadcast <RS[i].name, result> on CDB
    
    for each RS[j]:
        if RS[j].Qj == RS[i].name:
            RS[j].Vj ← result
            RS[j].Qj ← NULL
        if RS[j].Qk == RS[i].name:
            RS[j].Vk ← result
            RS[j].Qk ← NULL
    
    for each Register[k]:
        if Register[k].tag == RS[i].name:
            Register[k].value ← result
            Register[k].tag ← NULL
    
    RS[i].busy ← false

Why broadcast to everyone? Because we don't know at Issue time how many instructions will need this result. Could be zero, could be five. Broadcasting is simpler than tracking consumers.

Worked Example: The Full Dance

Code:

1. MUL  R1, R2, R3    # 5 cycles
2. ADD  R4, R1, R5    # 2 cycles (waits for R1)
3. SUB  R1, R6, R7    # 2 cycles
4. DIV  R8, R1, R9    # 40 cycles (waits for new R1 from SUB)

Initial state: R2=2, R3=3, R5=10, R6=20, R7=8, R9=2. All RS free. All tags NULL.

| Cycle | Event | RS State | Register Tags | |-------|-------|------------| | 1 | MUL issues to Mult1 | Mult1: MUL, Vj=2, Vk=3, Qj=NULL, Qk=NULL | R1.tag = Mult1 | | 2 | ADD issues to Add1 | Add1: ADD, Vj=NULL, Vk=10, Qj=Mult1, Qk=NULL | R4.tag = Add1 | | 3 | SUB issues to Add2 | Add2: SUB, Vj=20, Vk=8, Qj=NULL, Qk=NULL | R1.tag = Add2 (overwrites!) | | 3 | SUB executes immediately (operands ready) | | | 4 | DIV issues to Mult2 | Mult2: DIV, Vj=NULL, Vk=2, Qj=Add2, Qk=NULL | R8.tag = Mult2 | | 5 | SUB finishes, broadcasts <Add2, 12> | Mult2: Qj clears, Vj=12 | R1.tag = NULL, R1.value = 12 | | 5 | DIV starts executing (now has both operands) | | | | 6 | MUL finishes, broadcasts <Mult1, 6> | Add1: Qj clears, Vj=6 | R1 ignores (tag ≠ Mult1) | | 6 | ADD starts executing | | | 8 | ADD finishes, broadcasts <Add1, 16> | | R4.tag = NULL, R4.value = 16 | | 45 | DIV finishes, broadcasts <Mult2, 6> | | R8.tag = NULL, R8.value = 6 |

Key observations:

Cycle 3: SUB issues and immediately starts because R6/R7 are ready. It doesn't wait for MUL, even though MUL writes R1 first in program order (WA eliminated).
Cycle 5: DIV was waiting for Add2 (the new R1), not Mult1. Register renaming routed the dependency correctly.
Cycle 6: When MUL finishes, R1 ignores its result because R1.tag changed to Add2. No value is lost—ADD already captured it at Issue (Qj=Mult1).
Paralelism: MUL (cycles 1-6) and SUB (cycles 3-5) overlap. ADD starts at cycle 6, doesn't wait for SUB or DIV.

Why this step? Each time an operand arrives on the CDB, we're decoupling that producer from its consumers. The producer doesn't need to know who's waiting; consumers don't need to know when the producer finishes. The CDB is the "anonymous drop box."

Derivation: Why Does Register Renaming Work?

First principles:

True dependency (RAW): B needs A's result. This is unavoidable—B must wait.
Name dependency (WAR/WAW): B and A reuse the same register name, but B doesn't need A's value.

In Tomasulo:

Each instruction that writes gets a unique tag (RS name) at Issue time.
Readers capture the tag of the current writer.
If a new writer arrives, it gets a new tag. Old readers still point to the old tag.

Proof that WAW is eliminated:

Time t: MUL R1, ... issues. R1.tag ← Mult1.
Time t+1: SUB R1, ... issues. R1.tag ← Add2 (overwrites Mult1).

Any instruction issued after t+1 reading R1 will wait for Add2, not Mult1. MUL's result will broadcast, but R1 won't latch it (tag mismatch). This is equivalent to renaming: MUL R1_old, ..; SUB R1_new, .... The RS name is the physical register.

Proof that WAR is eliminated:

Time t: ADD R4, R1, ... issues. ADD.Qj ← (whatever R1.tag was, or grabs R1.value).
Time t+1: SUB R1, ... issues. R1.tag changes.

ADD doesn't re-check R1. It already has the value or tag it needs. SUB can overwrite R1 immediately without corrupting ADD.

Mathematical model: Let $W_i$ be the write time of instruction $i$ , $R_j$ be the operand-ready time of instruction $j$ . Without renaming: $R_j \geq \max(W_k : k < j \land k \text{ writes } \text{reg}(j))$ With renaming: $R_j \geq W_k \text{ only if } k \text{ is the most recent writer at } j\text{'s issue time}$ We decouple $R_j$ from stale writers, increasing paralelism.

Common Mistakes

Worked example Example 2: Loop with Dependencies

Code:

loop:
  LD   R1, 0(R10)    # Load from memory (3 cycles)
  MUL  R2, R1, R3    # 5 cycles
  ADD  R4, R4, R2    # 2 cycles (accumulator)
  ADI R10, R10, 4   # Increment pointer
  BNE  R10, R11, loop

Without Tomasulo: Each iteration waits for the previous ADD R4 to finish before starting the next ADD R4. Throughput: 3+5+2 = 10 cycles per iteration.

With Tomasulo (assuming 2 LD units, 2 MUL units, 3 ADD units):

Iteration 1: LD₁ → Mult₁ → Add₁
Iteration 2: LD₂ (starts cycle 1, finishes cycle 4) → Mult₂ (waits for LD₂, then for Add₁'s R4 if RS is smart) Wait, there's still a loop-carried dependency on R4! Each ADD R4, R4, R2 needs the previous iteration's R4. Tomasulo can't remove true dependencies.

But: Tomasulo overlaps the independent parts. While Mult₁ is running (cycles 4-8), LD₂ finishes (cycle 4) and Mult₂ can start (cycle 9). Without Tomasulo, LD₂ wouldn't even issue until Add₁ finishes (cycle 10). Speedup: ~1.3× (from pipelining the independentLD/MUL work). To get more, you'd need loop unrolling or vectorization—orthogonal techniques.

Why Tomasulo Beats Scoreboards

| Feature | Scoreboard (CDC 6600) | Tomasulo | |---------|----------------------| | WAW/WAR hazards | Stalls | Eliminated via renaming | | Operand fetch | From register file after RAW clears | From CDB (bypassing) | | Distributed control | Centralized functional unit table | Distributed in RSs | | Load/Store ordering | In-order | Can be out-of-order (with memory disambiguation) |

Key insight: Scoreboards detect hazards and stall. Tomasulo eliminates false hazards by renaming, so there's less to stall on.

Recall Explain to a12-Year-Old

Imagine you're doing homework, and you have 5 math problems. Problem 2 needs the answer from Problem 1, but Problem 3, 4, 5 are totally independent.

The dumb way: Do them in order. You sit there waiting for Problem 1 to finish before even reading Problem 3.

The Tomasulo way: You have sticky notes. When you start Problem 1, you stick a note on the answer line: "Problem 1 will put the answer here." Then you read Problem 3—it doesn't need Problem 1's answer, so you start solving it immediately. When Problem 1 finishes, you write the answer on the sticky note and announce "Problem 1 is done, the answer is 42!" Problem 2 hears this, grabs the 42, and starts solving. Meanwhile, you've already finished Problem 3 and 4.

The sticky note is the reservation station tag. The announcement is the CDB broadcast. Tomasulo is just a very organized homework system that never wastes time waiting unless it has to.

Connections

register-renaming: Tomasulo is the original hardware implementation
out-of-order-execution: Tomasulo enables dynamic OO without compiler help
reorder-buffer: Pairs with Tomasulo for precise exceptions (modern CPUs)
scoreboarding: Predecessor; Tomasulo improves on CDC 6600's scoreboard
instruction-level-parallelism: Tomasulo extracts ILP from sequential code
memory-disambiguation: Extends Tomasulo to loads/stores (e.g., load-store queue)
common-data-bus: The broadcast medium for results
data-hazards: RAW/WAR/WAW—Tomasulo eliminates WAR/WAW

#flashcards/hardware

What problem does Tomasulo's algorithm solve? :: Eliminates false dependencies (WAR/WAW hazards) caused by register name reuse, allowing out-of-order execution while maintaining the illusion of sequential execution.

What are the three key structures in Tomasulo?

Reservation Stations (RS), Register File Tags, and Common Data Bus (CDB).

What does a reservation station store?

The operation, source operand values or tags pointing to producers, and the destination tag (this RS's name).

What happens during the Issue stage?

Allocate an RS, copy operand values or producer tags from registers, update destination register's tag to this RS's name.

When does an instruction execute in Tomasulo?

When both its source operand tags are NULL (operands are ready), i.e.,

Q_j = \text{NULL} \land Q_k = \text{NULL}

What happens during Write Result?

The FU broadcasts <RS_name, result> on the CDB. All RSs and registers listening for that tag latch the value, and the RS is freed.

How does Tomasulo eliminate WAW hazards?

Later writes get new RS tags, overwriting the destination register's tag. Old writers broadcast, but the register ignores them (tag mismatch).

How does Tomasulo eliminate WAR hazards?

Readers capture tags at Issue time and don't re-check the register. Writers can overwrite registers without corrupting readers.

Why is the CDB a broadcast bus?

At Issue time, we don't know how many instructions will need a result. Broadcasting to everyone is simpler than tracking consumers.

What is the main limitation of Tomasulo (original)?

Imprecise exceptions—instructions complete out of order, so exceptions don't appear sequential. Solved by adding a reorder buffer (ROB).

What does the register tag field indicate?

If NULL, the register holds a valid value. If set to an RS name, the register is waiting for that RS to produce its value.

How does Tomasulo compare to scoreboarding?

Scoreboard detects hazards and stalls. Tomasulo eliminates false hazards (WAR/WAW) via register renaming, so there's less to stall on.

What happens if all reservation stations are full?

Issue stage stalls—structural hazard. The instruction waits until an RS is freed.

What is the role of the Qj and Qk fields in an RS?

They hold the RS tag (name) of the producer instruction. When that producer broadcasts, the RS captures the value and clears the Q field.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho yaar, Tomasulo ka core intuition ekdum simple hai—ek restaurant kitchen ki tarah socho. Orders (instructions) sequence mein aate hain, lekin different stations (execution units) alag-alag speed pe kaam karte hain. Head chef yeh nahi bolta ki Station 2 tab tak wait kare jab tak Station 1 khatam na ho jaye. Instead, woh track karta hai ki har station ko kaunse ingredients (operands) chahiye, aur jaise hi woh ingredient ready ho jaye, station cooking start kar deta hai—bhale hi purane orders abhi bhi pak rahe hon. CPU mein bhi yahi hota hai: Tomasulo instructions ko out-of-order execute karne deta hai, par bahar se aisa lagta hai jaise sab kuch sequence mein hi ho raha hai.

Ab yeh matter kyun karta hai? Socho ek slow DIV instruction hai jo 40 cycles leta hai. Agar Tomasulo na ho, toh uske peeche ki har instruction—even ek chhota sa unrelated ADD—stall ho jayega, bekaar mein wait karega. Asli problem yeh hai ki instructions register ke naam (jaise R1) pe fight karte hain, chahe unhe actual data ki zaroorat ho ya na ho. Yeh false dependency hai (WAR/WAW hazard). Tomasulo ismein register renaming karta hai hardware mein—yaani woh track karta hai "mujhe jo value chahiye woh kaun produce kar raha hai?" instead of "kaunse register naam mein woh value padi hai?"

Iske liye teen key structures use hote hain: Reservation Stations (jahan instructions apne operands ka wait karte hain), Register File Tags (jo batate hain ki register ready hai ya kisi station ka wait kar raha hai), aur Common Data Bus (jispe koi bhi unit apna result broadcast karta hai, aur jo bhi us value ka wait kar raha tha woh pakad leta hai). Bottom line yeh hai ki Tomasulo sequential code mein chhupi hui parallelism (ILP) ko nikal leta hai, aur typical workloads pe throughput 2-3× tak badha deta hai. Yeh modern CPUs ki performance ka ek foundation concept hai, isliye ise achhe se samajhna zaroori hai.

What Problem Does Tomasulo Solve?

How Tomasulo Works: The Three Key Structures

The Algorithm: Three Stages

Stage 1: Issue (Dispatch)

Stage 2: Execute

Stage 3: Write Result (Broadcast)

Worked Example: The Full Dance

Derivation: Why Does Register Renaming Work?

Common Mistakes

Why Tomasulo Beats Scoreboards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Advanced Microarchitecture

Connections