Tomasulo's algorithm: Foundations — Hinglish deep dive

5.3.3 · D1 · Hardware › Advanced Microarchitecture › Tomasulo's algorithm

Tomasulo's algorithm padhne se pehle, tumhe ideas ki ek chhoti si toolkit chahiye. Neeche har symbol, structure, aur word hai jis par parent note depend karta hai — bilkul zero se, ek aisi order mein jahan har ek cheez pichli cheez par tikti hai. Yahan kuch bhi assume nahi kiya gaya; agar parent ne use kiya, toh hum define karte hain.

1. Ek instruction actually hoti kya hai

Isko imagine karo ek chhoti si machine ke roop mein jisme do input wires hain aur ek output wire.

Topic ko yeh kyun chahiye: Tomasulo ke har rule ko "sources padho, destination produce karo" ke terms mein likha gaya hai. Agar tum nahi dekh sakte ki kaun sa register source hai aur kaun sa destination, toh hazard ki saari baatein samajh nahi aayengi.

2. Registers aur register file

Topic ko yeh kyun chahiye: instructions sirf registers se padhti aur registers mein likhti hain (is model mein). Ek register ka naam — locker par likha number — exactly wahi cheez hai jo Section 5 mein problem create karegi, isliye ab hum ise clearly define karte hain.

3. "Program order mein" vs "out of order"

Topic ko yeh kyun chahiye: out-of-order execution hi pura point hai. Lekin yeh tabhi safe hai jab hum woh answer kabhi na todein jo program expect karta tha — isliye ab hum dependencies padhte hain.

4. Cycles — CPU ki heartbeat

Topic ko yeh kyun chahiye: worked example ek cycle-by-cycle timeline hai. "Cycle 3", "40 cycles" is time unit ke bina meaningless hain.

5. Dependencies — jab ek instruction ko dusri ki sach mein zaroorat hoti hai

Do instructions related ho sakti hain kuch tareekon se. Inhe clearly samajhna hi sab kuch hai. Dekho data-hazards.

Topic ko yeh kyun chahiye: parent ke poore "What Problem Does Tomasulo Solve?" section mein WAR/WAW hazards ko khatam karne aur RAW ko respect karne ki baat hai. Tumhe real dependency aur fake dependency mein fark karna aana chahiye.

6. "Tag" ka idea — ek value ke liye temporary naam

Yeh sabse clever idea hai, isliye hum ise dheere-dheere build karte hain.

Topic ko yeh kyun chahiye: tags hi renaming hain. Jab R1.tag = Mult1 hai, register R1 ab ek number nahi hai — yeh ek note hai jo kehta hai "station Mult1 ka intezaar kar raha hun." Isi tarah se do R1s do alag cheezein ban jaati hain.

7. Reservation Stations (RS) — waiting rooms

Definition Reservation Station

Ek functional unit ke saamne ek chhota buffer jahan ek instruction tab tak wait karti hai jab tak uske operands ready na ho jaayein. Har station ka ek naam hota hai (uska apna tag) aur yeh fields hold karta hai:

Field	Meaning
`Op`	perform karna wala operation (`ADD`, `MUL`, …)
$V_{j}$	source 1 ki value (agar already hai)
$V_{k}$	source 2 ki value (agar already hai)
$Q_{j}$	source 1 ke liye jis tag ka intezaar hai (agar value abhi nahi hai)
$Q_{k}$	source 2 ke liye jis tag ka intezaar hai

Pairs ko aise padhein: har source ke liye tumhare paas ya toh value $V$ hai ya tag $Q$ — dono nahi, aur kuch nahi bhi nahi.

Topic ko yeh kyun chahiye: poora algorithm $V_{j}, V_{k}, Q_{j}, Q_{k}$ ke terms mein likha gaya hai. Agar woh chaar symbols blur hain, toh pseudocode padhna impossible hai. Unke naam bas yeh hain: V = Value, Q = "Queue tag jiska intezaar kar raha hun"; j = pehla source, k = doosra source.

8. Functional Units (FU)

Topic ko yeh kyun chahiye: ek reservation station ek FU se "attached" hoti hai. RS waiting instruction hold karta hai; FU kaam karta hai jab operands aa jaate hain.

9. Common Data Bus (CDB) — loudspeaker

Topic ko yeh kyun chahiye: poora "Write Result" stage aur "Execute" mein operand-capture CDB par hota hai. Symbol $⟨ tag, value ⟩$ baar baar aata hai.

10. NULL aur logical symbols

Topic ko yeh kyun chahiye: parent ka "Execute Condition" formula exactly yahi do symbols use karta hai.

Sab kuch kaise fit hota hai

Har arrow ka matlab hai "left wala idea samjhe bina right wala nahi samjhoge." Notice karo ki tag reservation stations aur CDB dono ko feed karta hai — yeh poore design ka glue hai.

Equipment checklist

Right side cover karo aur zor se jawaab do. Agar koi stumps kare, toh uska section upar se dobara padho.

ADD R4, R1, R5 mein kaun sa register destination hai?

R4 — sabse left wala; R1 aur R5 sources hain.

Numbered lockers ki ek row, jisme har ek ek number hold karta hai.

"Out-of-order execution" ka kya matlab hai?

Ek baad wali instruction ko pehle wali ke khatam hone se pehle run karna, jab uska data ready ho.

Clock cycle kya hoti hai?

CPU ki basic tick of time; ek MUL jo 5 cycles leta hai woh start hone ke 5 ticks baad ready hogi.

Kaun si dependency real hai aur hamesha wait karni padti hai?

RAW (read-after-write) — ek baad wali instruction woh value padhti hai jo ek pehle wali produce karti hai.

WAR aur WAW ko false dependencies kyun kehte hain?

Yeh sirf ek shared register naam ki wajah se clash karti hain, data ki wajah se nahi; renaming se yeh gayab ho jaati hain.

Tag kya hota hai?

Ek short label jo us station ka naam batata hai jo ek value produce karega, jaise Mult1.

Reservation station mein

V_{j}

aur

Q_{j}

mein kya fark hai?

V_{j}

actual value hai agar hamare paas hai;

Q_{j}

woh tag hai jiska intezaar kar rahe hain agar value abhi nahi hai.

Q_{j} = NULL

ka kya matlab hai?

Hamare paas source 1 ki value already hai (in

V_{j}

); hum kisi ka intezaar nahi kar rahe.

Execute condition

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

kya kehta hai?

Dono operands ready hain, toh instruction ab run kar sakti hai.

Common Data Bus par kya travel karta hai?

Ek pair

⟨ tag, value ⟩

— ek finished station ka naam aur uska result.

Result ko specific consumers ki jagah sabko broadcast kyun karo?

Kyunki issue ke time kisi ko nahi pata ki kitni baad wali instructions ko yeh chahiye hoga; ek baar broadcast karna zyada simple hai.

Jab upar ki har line easy lage, tab tum Tomasulo's algorithm ke liye ready ho — ya pehle isko Hinglish mein padho. Related deeper dives: reorder-buffer, scoreboarding, memory-disambiguation.