Tomasulo's algorithm — Hinglish notes

5.3.3 · Hardware › Advanced Microarchitecture

Intuition Core Idea

Ek restaurant kitchen imagine karo jahan orders (instructions) sequence mein aate hain, lekin alag-alag stations (execution units) alag-alag speed se kaam karte hain. Head chef Station 2 ko force nahi karta ki Station 1 khatam hone tak wait kare—balki woh track karta hai ki kaunse ingredients (operands) har station ko chahiye, aur unhe tab hi cooking shuru karne deta hai jab woh ingredients aa jaate hain, chahe pehle wale orders abhi bhi cook ho rahe hon. Tomasulo's algorithm CPUs ke liye yahi kitchen management system hai: yeh register name dependencies ko remove karta hai actual data ko track karke jo har instruction ko chahiye, aur CPU ko instructions out-of-order execute karne deta hai jabki sequential execution ka illusion maintain karta hai.

Yeh kyun important hai: Iske bina, ek slow division har instruction ko rok deta jo uske peeche ho, chahe woh unrelated additions hi kyun na hon. Tomasulo sequential code mein chupi instruction-level parallelism (ILP) extract karta hai, aur typical workloads pe throughput 2-3× badh jaati hai.

Tomasulo Kya Problem Solve Karta Hai?

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?

Tomasulo ke bina:

ADD wait karta hai (sahi—DIV ka result chahiye)
SUB wait karta hai chahe use DIV ki zaroorat nahi (name R1 pe false dependency hai)
MUL is pile-up se block hai

Tomasulo ka solution: Hardware mein Register renaming. Algorithm track karta hai "woh kaun produce karega jo mujhe chahiye?" instead of "kaunse register name mein woh hai?"

Tomasulo Kaise Kaam Karta Hai: Teen Key Structures

Definition Core Components

Reservation Stations (RS): Har functional unit (FU) se attached buffers jahan instructions operands ke liye wait karti hain. Har RS entry store karti hai:
- Operation (ADD, MUL, etc.)
- Source operand values ya tags jo us RS ki taraf point karte hain jo unhe produce karega
- Destination tag (is RS ka naam, jaise Add1, Mult2)
Register File Tags: Har architectural register (R1, R2, ..) ka ek tag field hota hai. Agar tag empty hai, toh register ek valid value hold karta hai. Agar tag Mult2 hai, toh register Reservation Station Mult2 ka wait kar raha hai ki woh apni value produce kare.
Common Data Bus (CDB): Ek broadcast bus jahan functional units completed results announce karte hain. Har RS aur register sunta hai. Jab Mult2 finish karta hai, woh CDB pe <Mult2, 42> broadcast karta hai—jo bhi Mult2 ka wait kar raha tha woh value 42 le leta hai.

Badi Baat: Instructions register names pe nahi ladte. Woh reservation station slots pe ladte hain. RS ka naam ek temporary register naam ban jaata hai.

Algorithm: Teen Stages

Stage 1: Issue (Dispatch)

Kya hota hai:

Queue se agla instruction fetch karo
Check karo ki corresponding functional unit mein free reservation station hai ya nahi
Agar haan: RS allocate karo, operands registers se padho ya producing RS ka tag copy karo
Destination register ka tag update karo is RS ki taraf point karne ke liye

Yeh kyun kaam karta hai:

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

Ab R1 Add1 ki taraf point karta hai, Mult1 ki taraf nahi. Baad mein R1 padhne wali instructions Add1 ka wait karengi, purane DIV ka nahi. DIV ka result CDB pe broadcast hoga, lekin ab koi sun nahi raha—WAW hazard eliminate ho gaya.

Structural hazard: Agar koi free RS nahi, toh instruction Issue pe stall karti hai. Yeh over-subscription ko rokta hai.

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

Tag copy kyun karte hain, wait kyun nahi? Kyunki producer ne abhi finish nahi kiya hoga. Tag ek "baad mein bataunga" wala IOU hai.

Stage 2: Execute

Kya hota hai:

CDB monitor karo. Jab koi needed operand aata hai (Qj ya Qk kisi broadcast tag se match kare), value capture karo aur tag clear karo
Jab dono operands ready hon (Qj == NULL aur Qk == NULL), instruction ko functional unit pe execution ke liye bhejo
Execution multiple cycles le sakti hai (jaise DIV ke liye 40, MUL ke liye 5)

CDB monitor kyun karte hain?

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

Scoreboard stalls nahi: Simple scoreboards ke unlike, Tomasulo WAR hazards pe stall nahi karta. Agar SUB R1, R6, R7 issue hota hai jab ADD R4, R1, R5 execute ho raha hai, toh SUB ko ek naya RS tag milta hai (Add2). ADD ke paas abhi bhi purana R1 value hai ya apne producer ka wait kar raha hai—use koi farq nahi padhta ki R1 ka tag badal gaya.

Stage 3: Write Result (Broadcast)

Kya hota hai:

Functional unit finish karta hai. Woh CDB pe <RS_name, result_value> broadcast karta hai
Sab reservation stations aur register file entries jo RS_name sun rahi hain woh value latch karti hain
Producing RS free ho jaata hai (deallocate)
Destination register ka tag clear ho jaata hai (agar woh abhi bhi is RS ki taraf point kar raha hai)

Critical detail: "agar woh abhi bhi is RS ki taraf point kar raha hai." Agar kisi baad ki instruction ne tag overwrite kar diya (WAW case), toh register is broadcast ko ignore kar deta hai. 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

Sabko broadcast kyun karte hain? Kyunki Issue time pe hum nahi jaante kitni instructions ko yeh result chahiye hoga. Zero bhi ho sakti hain, paanch bhi. Broadcasting consumers ko track karne se zyada simple hai.

Worked Example: Poora 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. Sab RS free. Sab 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 immediately execute hoti hai (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 execute shuru (ab dono operands hain)
6	MUL finishes, broadcasts `<Mult1, 6>`	Add1: Qj clears, Vj=6	R1 ignore karta hai (tag ≠ Mult1)
6	ADD execute shuru
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 issue hoti hai aur immediately start karti hai kyunki R6/R7 ready hain. Woh MUL ka wait nahi karti, chahe MUL program order mein pehle R1 likhta hai (WAR eliminate ho gaya).
Cycle 5: DIV Add2 (naye R1) ka wait kar raha tha, Mult1 ka nahi. Register renaming ne dependency sahi route kiya.
Cycle 6: Jab MUL finish karta hai, R1 uska result ignore karta hai kyunki R1.tag Add2 ho gaya tha. Koi value nahi jaati—ADD ne use Issue pe hi capture kar liya tha (Qj=Mult1).
Parallelism: MUL (cycles 1-6) aur SUB (cycles 3-5) overlap karte hain. ADD cycle 6 pe start hoti hai, SUB ya DIV ka wait nahi karta.

Yeh step kyun? Har baar jab CDB pe ek operand aata hai, hum us producer ko uske consumers se decouple kar rahe hain. Producer ko nahi pata kaun wait kar raha hai; consumers ko nahi pata producer kab finish karega. CDB ek "anonymous drop box" hai.

Derivation: Register Renaming Kyun Kaam Karta Hai?

First principles:

True dependency (RAW): B ko A ka result chahiye. Yeh unavoidable hai—B ko wait karna hi padega.
Name dependency (WAR/WAW): B aur A same register naam reuse karte hain, lekin B ko A ki value nahi chahiye.

Tomasulo mein:

Har instruction jo write karti hai use Issue time pe ek unique tag (RS name) milta hai.
Readers current writer ka tag capture karte hain.
Agar naya writer aata hai, use naya tag milta hai. Purane readers abhi bhi purane tag ki taraf point karte hain.

Proof ki WAW eliminate ho gaya:

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

t+1 ke baad issue hone wali koi bhi instruction jo R1 padhe woh Add2 ka wait karegi, Mult1 ka nahi. MUL ka result broadcast hoga, lekin R1 use latch nahi karega (tag mismatch). Yeh renaming ke equivalent hai: MUL R1_old, ..; SUB R1_new, .... RS naam hi physical register hai.

Proof ki WAR eliminate ho gaya:

Time t: ADD R4, R1, ... issues. ADD.Qj ← (jo bhi R1.tag tha, ya R1.value le leta hai).
Time t+1: SUB R1, ... issues. R1.tag badal jaata hai.

ADD R1 re-check nahi karta. Uske paas pehle se woh value ya tag hai jo use chahiye. SUB bina ADD ko corrupt kiye R1 overwrite kar sakta hai.

Mathematical model: Maano $W_{i}$ instruction $i$ ka write time hai, $R_{j}$ instruction $j$ ka operand-ready time hai. Renaming ke bina: $R_{j} \geq max (W_{k} : k < j \land k writes reg (j))$ Renaming ke saath: $R_{j} \geq W_{k} only if k is the most recent writer at j ’s issue time$ Hum $R_{j}$ ko stale writers se decouple karte hain, parallelism badhti hai.

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

Tomasulo ke bina: Har iteration agla ADD R4 start karne se pehle pichle ADD R4 ke finish hone ka wait karta hai. Throughput: 3+5+2 = 10 cycles per iteration.

Tomasulo ke saath (2 LD units, 2 MUL units, 3 ADD units assume karo):

Iteration 1: LD₁ → Mult₁ → Add₁
Iteration 2: LD₂ (cycle 1 start, cycle 4 finish) → Mult₂ (LD₂ ka wait karta hai, phir Add₁ ke R4 ka agar RS smart hai) Ruko, R4 pe abhi bhi loop-carried dependency hai! Har ADD R4, R4, R2 ko pichli iteration ke R4 ki zaroorat hai. Tomasulo true dependencies nahi hata sakta.

Lekin: Tomasulo independent parts ko overlap karta hai. Jab Mult₁ run ho raha hai (cycles 4-8), LD₂ finish ho jaati hai (cycle 4) aur Mult₂ start ho sakta hai (cycle 9). Tomasulo ke bina, LD₂ tab tak issue bhi nahi hoti jab tak Add₁ finish na ho (cycle 10). Speedup: ~1.3× (independent LD/MUL kaam ko pipeline karne se). Zyada ke liye loop unrolling ya vectorization chahiye—yeh orthogonal techniques hain.

Tomasulo Scoreboards Se Better Kyun Hai

Feature	Scoreboard (CDC 6600)	Tomasulo
WAW/WAR hazards	Stalls	Renaming se eliminate
Operand fetch	Register file se RAW clear hone ke baad	CDB se (bypassing)
Distributed control	Centralized functional unit table	RSs mein distributed
Load/Store ordering	In-order	Out-of-order ho sakta hai (memory disambiguation ke saath)

Key insight: Scoreboards hazards detect karke stall karte hain. Tomasulo renaming se false hazards eliminate karta hai, toh stall karne ki zaroorat kam hoti hai.

Recall 12-Saal Ke Bachche Ko Samjhao

Socho tum homework kar rahe ho, aur tumhare paas 5 math problems hain. Problem 2 ko Problem 1 ka answer chahiye, lekin Problem 3, 4, 5 bilkul independent hain.

Bewaqoofi wala tarika: Order mein karo. Tum wahan baithke Problem 1 ke khatam hone ka wait karte ho, Problem 3 padhne se pehle bhi.

Tomasulo wala tarika: Tumhare paas sticky notes hain. Jab tum Problem 1 shuru karte ho, answer line pe ek note chipkate ho: "Problem 1 yahan answer likhega." Phir tum Problem 3 padhte ho—use Problem 1 ka answer nahi chahiye, toh tum use immediately solve karna shuru kar do. Jab Problem 1 finish hoti hai, tum sticky note pe answer likhte ho aur announce karte ho "Problem 1 done hai, answer 42 hai!" Problem 2 yeh sunta hai, 42 le leta hai, aur solve karna shuru kar deta hai. Itne mein tum Problem 3 aur 4 bhi finish kar chuke ho.

Sticky note reservation station tag hai. Announcement CDB broadcast hai. Tomasulo ek bahut organized homework system hai jo kabhi time waste nahi karta wait karne mein jab tak zaroorat na ho.

Connections

register-renaming: Tomasulo original hardware implementation hai
out-of-order-execution: Tomasulo compiler ki help ke bina dynamic OO enable karta hai
reorder-buffer: Tomasulo ke saath pair hota hai precise exceptions ke liye (modern CPUs)
scoreboarding: Predecessor; Tomasulo CDC 6600 ke scoreboard ko improve karta hai
instruction-level-parallelism: Tomasulo sequential code se ILP extract karta hai
memory-disambiguation: Tomasulo ko loads/stores tak extend karta hai (jaise load-store queue)
common-data-bus: Results ke liye broadcast medium
data-hazards: RAW/WAR/WAW—Tomasulo WAR/WAW eliminate karta hai

#flashcards/hardware

Tomasulo's algorithm kya problem solve karta hai? :: False dependencies (WAR/WAW hazards) jo register name reuse se hoti hain unhe eliminate karta hai, out-of-order execution allow karta hai jabki sequential execution ka illusion maintain hota hai.

Tomasulo mein teen key structures kya hain?

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

Ek reservation station kya store karta hai?

Operation, source operand values ya producers ki taraf point karne wale tags, aur destination tag (is RS ka naam).

Issue stage mein kya hota hai?

Ek RS allocate karo, registers se operand values ya producer tags copy karo, destination register ka tag is RS ke naam pe update karo.

Tomasulo mein instruction kab execute hoti hai?

Jab uske dono source operand tags NULL hon (operands ready hain), yaani

Q_{j} = NULL \land Q_{k} = NULL

Write Result mein kya hota hai?

FU CDB pe <RS_name, result> broadcast karta hai. Us tag ko sun rahi sab RSs aur registers value latch karti hain, aur RS free ho jaata hai.

Tomasulo WAW hazards kaise eliminate karta hai?

Baad ki writes ko naye RS tags milte hain, destination register ka tag overwrite ho jaata hai. Purane writers broadcast karte hain lekin register unhe ignore karta hai (tag mismatch).

Tomasulo WAR hazards kaise eliminate karta hai?

Readers Issue time pe tags capture karte hain aur register re-check nahi karte. Writers registers overwrite kar sakte hain readers ko corrupt kiye bina.

CDB broadcast bus kyun hai?

Issue time pe hum nahi jaante kitni instructions ko result chahiye hoga. Sabko broadcast karna consumers ko track karne se zyada simple hai.

Tomasulo (original) ki main limitation kya hai?

Imprecise exceptions—instructions out-of-order complete hoti hain, toh exceptions sequential nahi lagte. Reorder buffer (ROB) add karke solve hota hai.

Agar NULL hai, register valid value hold karta hai. Agar RS naam set hai, toh register us RS ka wait kar raha hai ki woh apni value produce kare.

Tomasulo aur scoreboarding mein comparison?

Scoreboard hazards detect karke stall karta hai. Tomasulo register renaming se false hazards (WAR/WAW) eliminate karta hai, toh stall karne ki zaroorat kam hoti hai.

Agar sab reservation stations full hain toh kya hota hai?

Issue stage stall karta hai—structural hazard. Instruction tab tak wait karti hai jab tak koi RS free na ho.

RS mein Qj aur Qk fields ka kya role hai?

Woh producer instruction ka RS tag (naam) hold karte hain. Jab woh producer broadcast karta hai, RS value capture karta hai aur Q field clear karta hai.