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

WHY does this exist?

Intuition The problem it solves

Consider:

I1: F0 = MEM[100]      ; slow load (cache miss, 100 cycles)
I2: F4 = F0 * F2       ; needs F0 — must wait
I3: F8 = F10 + F12     ; INDEPENDENT — why should it wait?!

In strict in-order execution, I3 is stuck behind I2 which is stuck behind the slow load I1. That's wasted hardware. Tomasulo lets I3 execute now, hiding the latency of I1.

The blockers to reordering are hazards:

Hazard	Meaning	Example	Real dependency?
RAW (true)	Read After Write	`I2` reads F0 written by `I1`	✅ Yes — must respect
WAR (anti)	Write After Read	`I3` writes a reg an earlier instr still reads	❌ False — just name reuse
WAW (output)	Write After Write	two instrs write same reg	❌ False — just name reuse

HOW does it run? The three stages

Worked Example 1 — RAW handled via tags

I1: ADD.D F2, F4, F6     ; F2 = F4 + F6   (RS = Add1)
I2: MUL.D F0, F2, F8     ; needs F2 from I1

Issue I1: F4, F6 ready → Add1: Vj=val(F4), Vk=val(F6). Set Qi[F2]=Add1. Why this step? I1 now owns the name F2; anyone wanting F2 should wait for tag Add1.

Issue I2: source F2 → check Qi[F2]=Add1 (not ready). So Mult1: Qj=Add1, F8 ready → Vk=val(F8). Set Qi[F0]=Mult1. Why this step? We store the tag Add1, not a value — we don't have F2's value yet, so we record who will deliver it.

Execute + Write I1: Add1 computes, broadcasts (Add1, result) on CDB. Why this step? Mult1 sees Qj==Add1, captures the value into Vj, clears Qj. Now Mult1 is ready → it can execute. The data flowed without ever going back through the register file.

Worked Example 2 — WAR/WAW dissolved

I1: DIV.D F0, F2, F4   ; slow divide  (RS = Div1)
I2: ADD.D F6, F0, F8   ; reads F0
I3: SUB.D F8, F10, F12 ; WRITES F8 — WAR vs I2's read of F8
I4: MUL.D F6, F14, F16 ; WRITES F6 — WAW vs I2's write of F6

Issue I2: Qj=Div1 (waits for F0), Vk=val(F8) captured now. Set Qi[F6]=Add1. Why this step? I2 grabbed F8's value at issue time. So even if I3 changes F8 later, I2 already has its copy — WAR can't bite.

Issue I3: writes F8 → set Qi[F8]=Sub1. I3 can execute immediately (operands ready) even though I2 hasn't. Why this step? I3's new F8 lives in Sub1's tag; I2's captured value is untouched.

Issue I4: writes F6 → set Qi[F6]=Mult1 (overwrites Add1). Why this step? The register file now points F6 → Mult1 (the latest writer). When I2 (Add1) finishes it broadcasts (Add1, ...), but Qi[F6]≠Add1 anymore, so the stale write is ignored for the register. WAW solved automatically.

Common mistake Steel-manning the common errors

Mistake 1: "Out-of-order execution means results commit out of order, breaking program semantics." Why it feels right: if instructions run in any order, surely the visible state is scrambled. Fix: Tomasulo respects RAW dependencies exactly, and Issue is in-order so renaming preserves "last writer wins." (For precise exceptions you add a Reorder Buffer — that's the next step beyond classic Tomasulo, which by itself does NOT give precise interrupts.)

Mistake 2: "Two instructions can broadcast on the CDB in the same cycle." Why it feels right: lots of units finish together. Fix: The CDB is a single shared bus — only one result per cycle. This is a real structural bottleneck and a reason to arbitrate / add more CDBs.

Mistake 3: "Reservation stations just store the source register numbers." Why it feels right: operands come from registers. Fix: They store either the value (if ready) or the producing RS's tag — never the architectural register number after issue. That tag IS the renamed name.

Mistake 4: "If the same value is needed by 5 instructions, the producer writes the register 5 times." Fix: One CDB broadcast; all 5 waiting RS entries snoop it simultaneously. Broadcast = one-to-many for free.

Recall Feynman: explain it to a 12-year-old

Imagine a kitchen with one chef but several prep stations. Orders come in on tickets. If one dish needs an ingredient that's still cooking, the chef doesn't freeze — he starts another dish that has all its ingredients ready. Each prep station holds a little note: "I'm waiting for the soup from Station 3." The moment Station 3 shouts "soup's done!" over the loudspeaker (the CDB), everybody waiting for that soup grabs it at once. The chef takes order tickets in order, but cooks whatever is ready first — and the food still comes out matching what each ticket asked for.

Flashcards

What problem does Tomasulo's algorithm solve?

It lets independent instructions execute out of order so the CPU doesn't stall behind one slow instruction, while preserving program correctness.

Which hazard type is a TRUE dependency that Tomasulo must respect?

RAW (Read After Write).

How does Tomasulo eliminate WAR and WAW hazards?

Implicit register renaming via reservation station tags — each result gets a fresh name, so name-reuse hazards disappear.

What are the three stages of Tomasulo?

Issue (in order), Execute (when operands ready), Write Result (broadcast on CDB).

What does a reservation station hold for an operand that isn't ready yet?

The tag (Qj/Qk) of the reservation station that will produce that operand, instead of a value.

What is the Common Data Bus (CDB)?

A single broadcast bus carrying (tag, value); all RS and registers snoop it to capture results in one cycle.

Why is Issue done in program order?

So the register status table always records the LAST writer of each register, giving correct WAW resolution.

Can two functional units write the CDB in the same cycle?

No — it's one shared bus, one result per cycle (a structural bottleneck).

What does setting Qi[dest] = thisRS accomplish?

Does classic Tomasulo provide precise exceptions?

No — you need a Reorder Buffer (ROB) added on top for precise interrupts/exceptions.

When can an instruction in a reservation station begin Execute?

Only when both Qj0 and Qk0 (both operands' values present).

If a register's Qi tag was overwritten, what happens to the old producer's CDB broadcast?

The register ignores it (tag mismatch); only RS entries still tagged with it capture the value.

Connections

Pipelining and Hazards — RAW/WAR/WAW originate here
Register Renaming — the general technique Tomasulo embodies
Reorder Buffer (ROB) — adds precise exceptions + in-order commit
Scoreboarding — Tomasulo's predecessor (CDC 6600); no renaming, stalls on WAR/WAW
Branch Prediction & Speculation — what feeds the out-of-order engine
Superscalar Execution — issuing multiple instructions per cycle
Cache Misses & Memory Latency — the latency Tomasulo hides

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Socho CPU ke paas ek slow instruction hai — jaise ek load jo cache miss ki wajah se 100 cycle leta hai. Agar CPU strictly program order mein chale, toh uske peeche wali saari independent instructions bhi bekaar mein wait karengi. Tomasulo ka algorithm bolta hai: "jiska data ready hai, woh abhi chalega" — chahe woh program mein baad mein ho. Isko bolte hain out-of-order execution, lekin result aise aate hain jaise sab in-order chala ho.

Asli trick hai register renaming. WAR aur WAW hazards real nahi hote — yeh sirf isliye aate hain kyunki register ke naam (F0, F2...) limited hain aur reuse hote hain. Tomasulo har result ko ek fresh naam (tag) deta hai, jo reservation station se aata hai. Jab instruction issue hoti hai, agar uska operand abhi tak ready nahi hai, toh woh us operand ki value nahi, balki uss producer RS ka tag store kar leti hai — matlab "main station Add1 ke result ka wait kar rahi hoon".

Jab koi functional unit kaam khatam karta hai, woh apna (tag, value) Common Data Bus (CDB) par broadcast karta hai. Saari reservation stations aur registers ek saath sunte hain — jiska Qj ya Qk us tag se match karta hai, woh value pakad leta hai. Ek hi broadcast mein 5 waiting instructions ek saath operand le sakti hain. Yaad rakho: CDB ek hi shared bus hai, toh ek cycle mein sirf ek result jaa sakta hai.

Teen stage yaad rakho: Issue (in order, rename karo), Execute (jab dono operand ready ho), Write (CDB par broadcast). Sirf RAW real dependency hai jise respect karna padta hai. Precise exceptions ke liye classic Tomasulo enough nahi — uske upar Reorder Buffer lagta hai. Bas yahi core idea hai jo modern superscalar CPUs ki neenv hai.

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

WHY does this exist?

WHAT are the pieces?

HOW does it run? The three stages

Worked Example 1 — RAW handled via tags

Worked Example 2 — WAR/WAW dissolved

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Computer Architecture (Deep)

Connections