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

4.1.22 · Coding › Computer Architecture (Deep)

YEH EXIST KYU KARTA HAI?

Intuition Woh problem jise yeh solve karta hai

Consider karo:

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?!

Strict in-order execution mein, I3 I2 ke peeche stuck hai jo slow load I1 ke peeche stuck hai. Yeh hardware ki barbaadi hai. Tomasulo I3 ko abhi execute karne deta hai, I1 ki latency ko hide karta hua.

Reordering ke blockers hazards hain:

Hazard	Meaning	Example	Real dependency?
RAW (true)	Read After Write	`I2` reads F0 jo `I1` ne write kiya	✅ Haan — respect karna padega
WAR (anti)	Write After Read	`I3` ek aisa reg write karta hai jo earlier instr abhi bhi read kar rahi hai	❌ False — sirf name reuse
WAW (output)	Write After Write	do instrs same reg likhti hain	❌ False — sirf name reuse

PIECES KYA HAIN?

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

YEH KAISE CHALTA HAI? Teen stages

Formula Tomasulo pipeline (per instruction)

1. Issue (program order mein):

Op ke liye ek free RS lo. Agar koi free nahi → structural stall.
Har source register s ke liye: agar Qi[s] kehta hai koi RS ise produce karega → woh tag Qj/Qk mein copy karo. Warna value Vj/Vk mein copy karo.
Qi[dest] = thisRS set karo → yeh RS ab destination name ko "own" karta hai. (Yahi renaming step hai.)

2. Execute (out of order):

Tab tak wait karo jab tak Qj == 0 && Qk == 0 (operands ready), phir functional unit ko bhejo.
RAW hazards se bachata hai: tum literally tab tak start nahi kar sakte jab tak real value nahi aati.

3. Write Result (out of order):

(thisRS_tag, result) CDB par broadcast karo.
Har RS jisme Qj == tag hai woh value Vj mein le leta hai (aur Qj clear karta hai). Qk ke liye bhi same. Har register jisme Qi == tag hai woh value store karta hai aur ready mark karta hai.
RS free karo.

Worked Example 1 — RAW tags ke zariye handle hota hai

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. Yeh step kyun? I1 ab F2 naam ka owner hai; jisko bhi F2 chahiye woh tag Add1 ka wait kare.

Issue I2: source F2 → check Qi[F2]=Add1 (ready nahi). Toh Mult1: Qj=Add1, F8 ready → Vk=val(F8). Set Qi[F0]=Mult1. Yeh step kyun? Hum tag Add1 store karte hain, value nahi — humare paas F2 ki value abhi nahi hai, toh hum record karte hain kaun ise deliver karega.

Execute + Write I1: Add1 compute karta hai, CDB par (Add1, result) broadcast karta hai. Yeh step kyun? Mult1 dekhta hai Qj==Add1, value Vj mein capture karta hai, Qj clear karta hai. Ab Mult1 ready hai → execute kar sakta hai. Data register file se wapas gaye bina flow kar gaya.

Worked Example 2 — WAR/WAW dissolve ho jaate hain

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 (F0 ka wait karta hai), Vk=val(F8) abhi captured. Set Qi[F6]=Add1. Yeh step kyun? I2 ne F8 ki value issue time par grab kar li. Toh chahe I3 baad mein F8 change kare, I2 ke paas uski copy already hai — WAR bite nahi kar sakta.

Issue I3: F8 write karta hai → set Qi[F8]=Sub1. I3 immediately execute kar sakta hai (operands ready) chahe I2 na kar sake. Yeh step kyun? I3 ka naya F8 Sub1 ke tag mein rehta hai; I2 ki captured value untouched hai.

Issue I4: F6 write karta hai → set Qi[F6]=Mult1 (Add1 ko overwrite karta hai). Yeh step kyun? Register file ab F6 → Mult1 (latest writer) ki taraf point karti hai. Jab I2 (Add1) finish karta hai toh (Add1, ...) broadcast karta hai, lekin Qi[F6]≠Add1 ab, toh register ke liye stale write ignore ho jaata hai. WAW automatically solved.

Common mistake Common errors ko steel-man karna

Mistake 1: "Out-of-order execution ka matlab hai results out of order commit hote hain, program semantics tod ke." Kyun sahi lagta hai: agar instructions kisi bhi order mein chalein, toh visible state zaroor scrambled hogi. Fix: Tomasulo RAW dependencies ko exactly respect karta hai, aur Issue in-order hota hai toh renaming "last writer wins" preserve karta hai. (Precise exceptions ke liye aap Reorder Buffer add karte hain — yeh classic Tomasulo ke baad ka step hai, jo akele precise interrupts nahi deta.)

Mistake 2: "Do instructions ek hi cycle mein CDB par broadcast kar sakte hain." Kyun sahi lagta hai: bahut saare units ek saath finish hote hain. Fix: CDB ek single shared bus hai — sirf ek result per cycle. Yeh ek real structural bottleneck hai aur arbitrate / aur CDBs add karne ki wajah hai.

Mistake 3: "Reservation stations sirf source register numbers store karte hain." Kyun sahi lagta hai: operands registers se aate hain. Fix: Woh ya toh value store karte hain (agar ready hai) ya producing RS ka tag — issue ke baad kabhi architectural register number nahi. Woh tag hi renamed name hai.

Mistake 4: "Agar same value 5 instructions ko chahiye, toh producer register 5 baar write karta hai." Fix: Ek CDB broadcast; sabhi 5 waiting RS entries simultaneously snoop karte hain. Broadcast = one-to-many for free.

Recall Feynman: ek 12-saal ke bachhe ko explain karo

Socho ek kitchen mein ek chef hai lekin kaafi saare prep stations hain. Orders tickets par aate hain. Agar kisi dish ko ek ingredient chahiye jo abhi bhi pak raha hai, chef freeze nahi hota — woh doosri dish shuru karta hai jiske saare ingredients ready hain. Har prep station ek chhoti si note hold karta hai: "Mujhe Station 3 se soup ka wait hai." Jis waqt Station 3 loudspeaker par chillata hai "soup done!" (woh CDB hai), sabhi jo us soup ka wait kar rahe the woh ek saath use grab karte hain. Chef order tickets order mein leta hai, lekin jo bhi ready hai pehle cook karta hai — aur khana phir bhi utaarta hai waise jaisa har ticket ne manga tha.

Flashcards

Tomasulo's algorithm kaun si problem solve karta hai?

Yeh independent instructions ko out of order execute karne deta hai taaki CPU ek slow instruction ke peeche stall na kare, jabki program correctness preserve hoti hai.

Kaun sa hazard type TRUE dependency hai jise Tomasulo ko respect karna padta hai?

RAW (Read After Write).

Tomasulo WAR aur WAW hazards kaise eliminate karta hai?

Reservation station tags ke zariye implicit register renaming — har result ko ek fresh name milta hai, toh name-reuse hazards gayab ho jaate hain.

Tomasulo ke teen stages kya hain?

Issue (in order), Execute (jab operands ready hon), Write Result (CDB par broadcast).

Ek reservation station ek aisa operand ke liye kya hold karta hai jo ready nahi hai?

Us reservation station ka tag (Qj/Qk) jo woh operand produce karega, value ki jagah.

Common Data Bus (CDB) kya hai?

Ek single broadcast bus jo (tag, value) carry karta hai; sabhi RS aur registers ek cycle mein results capture karne ke liye ise snoop karte hain.

Issue program order mein kyun hota hai?

Taaki register status table hamesha har register ka LAST writer record kare, jo correct WAW resolution deta hai.

Kya do functional units same cycle mein CDB par write kar sakte hain?

Nahi — yeh ek shared bus hai, ek cycle mein ek result (ek structural bottleneck).

Qi[dest] = thisRS set karna kya accomplish karta hai?

Kya classic Tomasulo precise exceptions provide karta hai?

Nahi — aapko precise interrupts/exceptions ke liye upar Reorder Buffer (ROB) add karna padta hai.

Reservation station mein ek instruction Execute kab shuru kar sakta hai?

Sirf jab dono Qj0 aur Qk0 hon (dono operands ki values present hain).

Agar kisi register ka Qi tag overwrite ho gaya, toh purane producer ke CDB broadcast ka kya hoga?

Register use ignore karta hai (tag mismatch); sirf woh RS entries jo abhi bhi us tag se tagged hain value capture karti hain.

Connections

Pipelining and Hazards — RAW/WAR/WAW yahan se originate hote hain
Register Renaming — woh general technique jo Tomasulo embody karta hai
Reorder Buffer (ROB) — precise exceptions + in-order commit add karta hai
Scoreboarding — Tomasulo ka predecessor (CDC 6600); koi renaming nahi, WAR/WAW par stalls
Branch Prediction & Speculation — jo out-of-order engine ko feed karta hai
Superscalar Execution — ek cycle mein multiple instructions issue karna
Cache Misses & Memory Latency — woh latency jo Tomasulo hide karta hai