Tomasulo's algorithm: Worked examples — Hinglish deep dive

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

Yeh page Tomasulo's algorithm ka "sab kuch daal do" companion hai. Hum teen stages (Issue, Execute, Write Result) aur teen structures (reservation stations, register tags, Common Data Bus) already jaante hain. Yahan hum har tarah ki situation ke through grind karte hain jo algorithm face kar sakta hai — ek worked example per case, taaki koi bhi scenario tumhare liye naya na ho.

Symbols jo hum har jagah use karte hain (poori tarah se restated)

Yeh page self-contained hai: neeche har symbol use se pehle define kiya gaya hai, taaki tumhe kabhi parent note pe waapis jaana na pade.

Definition Reservation-station fields (restated in situ)

Ek reservation station (RS) ek functional unit ke saamne ek chhota waiting-slot hota hai jahan ek instruction tab tak baith ti hai jab tak uske inputs ready nahi ho jaate. Har RS entry in fields ko hold karta hai:

== $V_{j}$ , $V_{k}$ == ::: do source operands ki actual numeric values, jab hum unhe paate hain. "V" matlab value.
== $Q_{j}$ , $Q_{k}$ == ::: tags — us RS ka naam jo ek missing operand produce karega. "Q" matlab queue-position / who-owes-me. Agar $Q_{j} =$ NULL hai, toh $V_{j}$ already ek real value rakhta hai aur hum kisi ka wait nahi kar rahe.
Op ::: operation (MUL, ADD, …). busy ::: kya slot occupied hai.
RS ka apna naam (e.g. Add1) woh tag hai jo woh finish hone par broadcast karega.

Execute condition (ek rule jo execution start karta hai). Ek reservation station mein ek instruction tab exactly execute karna shuru kar sakta hai jab dono operands present hon: $Q_{j} = NULL \land Q_{k} = NULL .$ Kyun dono? Tum $A ⋆ B$ compute nahi kar sakte jab $B$ abhi bhi ek IOU hai. Jaise hi last missing operand CDB par aata hai, yeh condition true flip ho jaati hai aur execution schedule ho sakti hai.

Timing model jo hum har jagah use karte hain

Cycle counts meaningless hain jab tak sab log agree na karein ki "kab ek stage hota hai." Isliye hum ek simple model fix karte hain aur ise har example ke liye use karte hain neeche. Jab bhi tum ek cycle number dekhte ho, woh in rules ka paalan karta hai.

Definition Hamaara fixed pipeline timing model

Issue 1 cycle leta hai. Cycle $c$ mein issued ek instruction usi cycle se apna reservation station occupy karta hai.
Execute cycle baad shuru hota hai jab dono operands present hon ( $Q_{j} = Q_{k} =$ NULL). Agar ek operand cycle $c$ mein CDB se capture hota hai, toh execution ka pehla cycle $c + 1$ hai. Latency $L$ wala ek op functional unit ko cycles $c + 1, \dots, c + L$ ke liye occupy karta hai.
Write Result apna khud ka 1 cycle leta hai, last execute cycle ke baad wala cycle. Ek op jo cycle $f$ mein execute karna khatam karta hai woh cycle $f + 1$ mein CDB par broadcast karta hai.
Cycle $w$ mein CDB se captured ek value waiting instruction ko free kar sakti hai taaki woh cycle $w + 1$ mein execute karna shuru kar sake.
CDB ek cycle mein zyada se zyada ek result carry karta hai (ek write port). Agar do chahte hain, ek arbiter program order se chunata hai aur haarne waala wait karta hai.

Toh ek op ki sabse chhoti possible life hai: Issue @ $c$ , Execute @ $c + 1 \dots c + L$ , Write @ $c + L + 1$ . Concretely: latency $L$ wala op cycle $c$ mein issued hota hai, cycles $c + 1, \dots, c + L$ mein execute hota hai aur cycle $c + L + 1$ mein write karta hai.

Scenario matrix

Kuch naya define karne se pehle, teen plain-word labels yaad karte hain un ways ke liye jismein ek instruction doosre se clash kar sakta hai. Ek hazard bas "ek wajah hai jis se instruction B galat answer de sakta hai agar hum ise bahut jaldi run hone dein."

Definition Teen hazards (plain words)

RAW (Read-After-Write, ek true dependency): B ek register read karta hai jo A write karta hai. B ko genuinely A ka number chahiye. Tum ise cheat nahi kar sakte — data actually flow karna chahiye.
WAR (Write-After-Read): B ek register write karta hai jo ek earlier A ko abhi read karna hai. Yeh ek false dependency hai — yeh sirf isliye exist karta hai kyunki woh ek naam share karte hain, ek value nahi.
WAW (Write-After-Write): dono A aur B ek hi register write karte hain. Sirf aakhri write survive karni chahiye. Phir se false — ek naming clash, data need nahi.

Full taxonomy ke liye data-hazards dekho. Tomasulo ka poora trick yeh hai ki woh RAW (real) ko respect karna chaahiye lekin WAR aur WAW (fake) ko renaming via tags use karke dissolve kar deta hai.

Yeh un cases ka full grid hai jo hum cover karenge. Har cell "space ka corner" name karta hai, aur woh example number jo usme fit hota hai.

#	Case class	Kya stress ho raha hai
E1	Pure RAW chain	Ek hazard jo tum remove nahi kar sakte
E2	WAW clash	Ek register pe do writes; late write jeet ta hai
E3	WAR "false" clash	Earlier read ko later write se bachna hai
E4	Zero dependency	Instruction jiske dono operands ready hain — issue aur run instantly
E5	Degenerate broadcast	Ek result compute hua lekin har listener ne ignore kiya
E6	Limiting behaviour	Long chain vs. wide independent code — ILP kahan saturate hoti hai
E7	Real-world word problem	Load/store + memory-disambiguation
E8	Exam twist	CDB structural conflict: do units same cycle mein finish
E9	Control hazard + commit	Branch misprediction aur reorder-buffer commit

Cell coverage check: RAW → E1, E6, E8. WAR → E3. WAW → E2, E5. No-dependency/zero → E4. Degenerate/ignored value → E5. Limiting → E6. Word problem/memory → E7. Structural/exam → E8. Control + commit → E9. Har cell hit ho gaya.

E1 — Pure RAW chain (woh hazard jo tum remove nahi kar sakte)

Worked example Statement

Maano MUL 4 cycles leta hai, ADD 2. Issue 1 instruction/cycle hai.

1. MUL R1, R2, R3
2. ADD R4, R1, R5   # reads R1 — RAW on inst 1

R2=6, R3=7, R5=1 ke saath. Kis cycle mein ADD execute karna shuru karta hai, aur R4 kya hai?

Forecast: Abhi andaza lagao — kya ADD issue ke right baad start hota hai, ya use wait karna padta hai? Kitne cycles ke liye?

Cycle 1 — MUL Mult1 ko issue hota hai. Dono operands ready ( $V_{j} = 6, V_{k} = 7$ , $Q_{j} = Q_{k} =$ NULL). R1.tag = Mult1 set karo. Yeh step kyun? Issue par hum register file mein jo bhi hai snapshot lete hain; R1 ka tag ab kehta hai "Mult1 ka wait karo."
Cycle 2 — ADD Add1 ko issue hota hai. R5 ready hai ( $V_{k} = 1$ ), lekin R1 ka tag Mult1 hai, toh ADD $Q_{j} = Mult1$ store karta hai, $V_{j}$ empty. Yeh step kyun? ADD tag copy karta hai, ek IOU — yeh block nahi karta, bas yaad rakhta hai ki kise uska number dena hai.
Cycles 2–5 — MUL execute karta hai (issued @1, toh execute hai cycles $2$ se $5$ , latency 4). ADD run nahi kar sakta: $Q_{j} \neq =$ NULL. Yeh step kyun? Yeh woh ek wait hai jo hum kabhi skip nahi kar sakte — data genuinely abhi exist nahi karta.
Cycle 6 (write) — MUL broadcast karta hai $⟨ Mult1, 42 ⟩$ (execute @5 khatam hua, write @6, yani $1 + 4 + 1$ ). Add1 Mult1 dekhta hai, $V_{j} = 42$ set karta hai, $Q_{j}$ clear karta hai. Yeh step kyun? CDB number deliver karta hai jaise hi woh written hota hai; ADD isi cycle mein capture karta hai.
Cycle 7 — ADD execute karta hai (capture ke baad wala cycle) $42 + 1 = 43$ ke saath; cycles 7–8 execute karta hai; result $R 4 = 43$ cycle 9 par broadcast ( $6 + 1$ start, phir $2 + 1$ ).

Verify: MUL: $6 \times 7 = 42$ , cycle 6 mein written. ADD: $42 + 1 = 43$ , cycle 9 mein written. RAW ne ek real wait force kiya — ADD MUL ke result broadcast hone se pehle shuru nahi ho sakta tha. Yeh correct hai; data physically arrive karna tha.

E2 — WAW clash (do writes ek register ko)

Worked example Statement

1. MUL R1, R2, R3   # 4 cycles, R1 ← 42
2. SUB R1, R6, R7   # 2 cycles, R1 ← 12  (WAW on inst 1!)

R2=6,R3=7,R6=20,R7=8. Dono finish hone ke baad, R1 kya hai, aur kya MUL ka result R1 tak pahuncha?

Forecast: Dono R1 write karte hain. Kaun si value survive karti hai — 42 ya 12? Kya MUL ka broadcast SUB ke answer ko overwrite karta hai?

Cycle 1 — MUL issue hota hai Mult1 ko. R1.tag = Mult1. Execute cycles 2–5, write @6. Kyun? R1 ab Mult1 ko promise ki gayi hai.
Cycle 2 — SUB Add1 ko issue hota hai, operands ready. R1.tag = Add1 overwrites Mult1. Execute cycles 3–4, write @5. Yeh step kyun? Register file sirf apna latest producer yaad rakhta hai. Yeh overwrite woh renaming hai jo WAW ko dissolve karti hai — R1 ab newer writer ko point karta hai.
Cycle 5 — SUB writes, $⟨ Add1, 12 ⟩$ broadcast karta hai. R1.tag Add1 hai, toh R1 $12$ latch karta hai, tag → NULL. Yeh step kyun? Ek broadcast ek register tab latch karta hai jab us register ka tag broadcasting RS ka naam rakhe. R1 ka tag Add1 hai aur yeh Add1 ka broadcast hai, toh match hold hoti hai aur 12, R1 mein land karta hai — yeh woh write hai jo jeetnee chahiye.
Cycle 6 — MUL writes, $⟨ Mult1, 42 ⟩$ broadcast karta hai. R1.tag ab NULL hai (≠ Mult1), toh R1 ise ignore karta hai. Yeh step kyun? Same match rule, ab fail ho rahi: tag overwrite ho gayi, toh stale earlier write harmlessly vanish ho jaati hai — exactly WAW guard.

Verify: Final $R 1 = 12$ (program order mein last writer). $42$ compute hua lekin discard hua — exactly wahi jo ek correct in-order machine produce karta. Koi stall zarurat nahi thi.

Figure s01 — E2 ka WAW guard. Mint arrow SUB ka cycle 5 mein broadcast hai: R1 ka tag Add1 hai, tags match karte hain, toh 12 latch ho jaata hai. Dashed coral arrow MUL ka baad wala cycle 6 mein broadcast hai: R1 ka tag already NULL hai, tags mismatch hote hain, toh 42 drop ho jaata hai. Do "tag matches / tag ≠" labels padho — yeh ek tasveer mein poora WAW mechanism hai.

E3 — WAR clash (earlier read ko later write se bachna hai)

Worked example Statement

1. DIV R1, R2, R3   # 10 cycles (slow), reads R2,R3
2. ADD R2, R6, R7   # 2 cycles, WRITES R2 (WAR on inst 1's read of R2)

R2=100,R3=4,R6=5,R7=5. Kya ADD ka R2 overwrite karna DIV ke dividend ko corrupt karta hai?

Forecast: DIV R2=100 read karta hai lekin abhi bhi crunching kar raha hai jab ADD R2=10 write karna chahta hai. Kya DIV aakhir mein 10 divide karta hai ya 100?

Cycle 1 — DIV issue hota hai. R2 aur R3 abhi ready hain, toh DIV values copy karta hai $V_{j} = 100, V_{k} = 4$ Mult1 mein. R1.tag=Mult1. Yeh step kyun? Yeh crucial line hai. Tomasulo operand values Issue par read karta hai, baad mein nahi. DIV ke paas 100 ki private copy hai.
Cycle 2 — ADD Add1 ko issue hota hai, ready. R2.tag=Add1. ADD cycles 3–4 execute karta hai, @5 write karta hai. Kyun? ADD DIV ki copy ko touch nahi karta; yeh sirf register file ka R2 change karta hai.
Cycle 5 — ADD writes, $⟨ Add1, 10 ⟩$ broadcast karta hai; R2 register file mein 10 ban jaata hai. Yeh step kyun? DIV ka $V_{j}$ ek alag buffer hai — register-file change use reach nahi kar sakta.
Cycle 12 — DIV writes. DIV @1 issued hua, toh cycles 2–11 execute karta hai (latency 10), aur uska Write Result agle cycle mein hai: $1 + 10 + 1 = 12$ . Usne apna snapshot $100/4 = 25$ use kiya. Yeh step kyun? Model exactly apply karna: last execute cycle 11 hai, aur Write Result uske baad apna cycle hai, toh cycle 12.

Verify: $100/4 = 25$ (correct — purana R2 use kiya), cycle 12 mein written ( $1 + 10 + 1$ ). Register file ka R2 ab $5 + 5 = 10$ hai. WAR "false" hazard ne kuch nahi rokaa kyunki Issue par values padhna hi rename hai. Yeh scoreboarding pe Tomasulo ka edge hai, jo ADD ko stall kar deta.

E4 — Zero dependency (dono operands ready = instant run)

Worked example Statement

1. ADD R4, R6, R7   # 2 cycles; R6,R7 dono ready hain, kuch bhi inhe pehle write nahi karta

R6=20,R7=8. Kis cycle mein execute hota hai, aur kis cycle mein write karta hai?

Forecast: Zero dependencies ke saath, kya Issue aur Execute ke beech koi wait hai? CDB par result kab appear hota hai?

Cycle 1 — Add1 ko issue hota hai, $V_{j} = 20, V_{k} = 8$ , dono $Q$ =NULL. Kyun? Copy karne ke liye koi tag nahi — register file real values rakhta hai, IOUs nahi.
Cycles 2–3 — execute karta hai (issue par execute condition already true hai, toh execute bilkul agle cycle mein start hota hai). Yeh step kyun? Yeh "zero input" case hai: koi producer ka wait nahi, toh sirf fixed stages ka cost hai.
Cycle 4 — writes. Last execute cycle 3 hai, toh Write Result uske baad apna cycle hai: cycle $1 + 2 + 1 = 4$ . $⟨ Add1, 28 ⟩$ broadcast karta hai; R4 28 latch karta hai, tag → NULL. Yeh step kyun? Chahe koi dependents sun nahi rahe, Write stage phir bhi chalti hai — har op ko Issue, Execute, aur Write se guzarna padta hai. Yeh woh stage hai jo doosre examples mein bhi dikhti hai aur E4 mein bhi dikhaana zaroori hai.

Verify: $20 + 8 = 28$ , cycle 4 mein written. Latency = issue (1) + execute (2) + write (1) = total 4 cycles, koi dependency stall nahi. Yeh best case hai aur woh baseline hai jiske against baaki measure hote hain.

E5 — Degenerate broadcast (ek value compute hui phir ignore hui)

Worked example Statement

1. MUL R1, R2, R3   # 4 cyc, R1 ← 42
2. SUB R1, R6, R7   # 2 cyc, R1 ← 12  (R1 ko rename karta hai)
3. ADD R4, R1, R5   # RENAMED R1 read karta hai

R2=6,R3=7,R6=20,R7=8,R5=1. ADD kaun sa R1 consume karta hai — 42 ya 12? Kya MUL ka 42 kabhi use hota hai?

Forecast: ADD R1 read karta hai. Lekin R1 rewrite ho gaya. Kiska 42/12 ADD mein flow karta hai?

Cycle 1 — MUL issues Mult1 ko, R1.tag=Mult1. Execute 2–5, write @6. Yeh step kyun? MUL R1 ka pehla writer hai, toh R1 ka tag Issue par Mult1 ko point karne ke liye set hota hai.
Cycle 2 — SUB Add1 ko issues hota hai, operands ready, R1.tag=Add1 overwrites Mult1. Execute 3–4, write @5. Yeh step kyun? SUB R1 ka baad wala writer hai; register file hamesha newest producer ka tag rakhta hai, toh koi bhi baad wala reader Add1 se bind karega, Mult1 se nahi.
Cycle 3 — ADD Add2 ko issues hota hai. Woh R1 ka current tag Add1 read karta hai, toh $Q_{j} = Add1$ ; $V_{k} = 1$ R5 se. Yeh step kyun? ADD R1 ke newest producer se bind karta hai — renamed wale (Add1) se — stale MUL se kabhi nahi.
Cycle 5 — SUB writes, $⟨ Add1, 12 ⟩$ broadcast karta hai: ADD ka $Q_{j}$ clear hota hai, $V_{j} = 12$ . ADD ab cycles 6–7 execute karta hai, @8 writes. Yeh step kyun? Add1 par CDB match correct, renamed value seedha ADD ke reservation station mein deliver karta hai.
Cycle 6 — MUL writes, $⟨ Mult1, 42 ⟩$ broadcast karta hai: koi bhi RS aur koi register Mult1 ke liye sun nahi raha. 42 unused mar jaata hai. Yeh step kyun? Yeh degenerate corner hai — ek perfectly valid result jiske zero consumers hain. Broadcast-to-all "0 listeners" ko "5 listeners" ki tarah handle karta hai, toh kuch special nahi chahiye.

Verify: ADD $12 + 1 = 13$ compute karta hai. MUL result 42 compute hua lekin koi nahi consume kiya — sequential semantics match karta hai, jahan SUB ka 12, MUL ke 42 ko shadow karta hai ADD ke R1 read karne se pehle.

E6 — Limiting behaviour (jahan parallelism saturate hoti hai)

Worked example Statement

Do 4-instruction programs compare karo, har op = 2 cycles, 1 issue/cycle, 1 CDB write/cycle. Fixed timing model use karo (Issue @ $c$ , Execute @ $c + 1 \dots$ , Write @ $c + 3$ 2-cycle op ke liye). (A) Dependent chain: har ek pichla result read karta hai.

ADD R1,R2,R3 ; ADD R4,R1,R5 ; ADD R6,R4,R7 ; ADD R8,R6,R9

(B) Independent: koi shared registers nahi.

ADD R1,R2,R3 ; ADD R4,R5,R6 ; ADD R7,R8,R9 ; ADD R10,R11,R12

Har ek mein last result kis cycle mein written hota hai?

Forecast: Out-of-order chain (A) ki kitni help kar sakta hai? Kya (B) quarter time mein finish karta hai?

Chain (A): I1 @1 issue hoti hai, 2–3 execute, @4 writes (Add1 free). I2 ko I1 ki value chahiye, @4 capture karta hai, execute 5–6, write @7. I3 @7 capture, execute 8–9, write @10. I4 @10 capture, execute 11–12, write @13. Yeh step kyun? Har write exactly pichli write + 3 hai (op latency 2 + 1 write cycle). RAW irreducible hai — out-of-order-execution ek true data chain ko beat nahi kar sakta. Yeh limit hai: latency chain length ke saath linearly badhti hai. Yahan ek saath zyada se zyada ek ADD busy hai, toh do slots kaafi hain.
Independent (B): I1 @1 issue hoti hai (Add1), I2 @2 (Add2), I3 @3 (kya Add1 already free hai? nahi — Add1 @4 write karta hai). Slots track karo: I1 Add1 use karta hai (busy c1–4), I2 Add2 use karta hai (busy c2–5), I3 ko ek free slot chahiye — Add1 c4 par free hota hai, toh I3 Add1 leta hai, c4 issue karta hai (ek-cycle issue slip), exec 5–6, write @7; I4 Add2 leta hai (c5 free hota hai), c5 issue karta hai, exec 6–7, write @8. Last write @8. Yeh step kyun? Yahan limit structural hai: sirf do RS slots, toh teesra aur chautha ADD slot free hone ka wait karte hain. Fixed 2-slot hardware ke saath, independent code RS count se cap hoti hai, data se nahi.

Verify: Chain cycle 13 par finish hoti hai; independent cycle 8 par. Independent faster hai lekin 4× faster nahi — fixed 2 RS slots (aur single CDB) pipeline ko serialise karte hain. Lesson: ILP isse bounded hai jo scarcer ho, true dependencies ya hardware resources (RS slots, CDB).

Figure s02 — E6 timelines hamaare fixed model ke under exactly do RS slots ke saath. Top (lavender): dependent chain — har box ka write cycle pichla +3 hai, toh last write cycle 13 tak slide karta hai. Bottom (mint): independent code — sirf do slots exist karte hain, toh I3/I4 slot free hone ka wait karte hain aur last write cycle 8 par land karta hai. Do sabse right "last=" labels compare karo: gap (13 vs 8) exactly ek true data chain ka cost hai versus ek fixed-resource limit.

E7 — Real-world word problem (loads, stores, memory ordering)

Worked example Statement

Ek graphics loop karta hai:

1. L.D  F2, 0(R1)     # R1 mein address se pixel load karo (maano 4 cycles)
2. MUL  F4, F2, F0    # ise scale karo (RAW on F2)
3. S.D  F4, 0(R1)     # result SAME address par store karo

Kya store (3) ko load (1) se pehle ya F4 hone se pehle reorder kiya ja sakta hai?

Forecast: Store aur load same memory address touch karte hain. Kya yeh ek "hazard" hai jo register tags dekh sakte hain?

Load issue hota hai Load1 ko, address [R1] compute karta hai, execute karta hai; result F2 CDB par tag Load1 ke saath broadcast hota hai. Kyun? Loads kisi bhi producer ki tarah behave karte hain: unka tag Load1 F2 ko rename karta hai.
MUL issues, $Q_{j} = Load1$ , wait karta hai, phir $F 2 \times F 0$ execute karta hai. Yeh step kyun? Normal RAW through F2 — tags se handle hota hai, koi memory involved nahi.
Store issue hota hai: uska data operand F4 tag Mult1 paata hai; uska address R1 use karta hai. Store ko load ke address pata hone se pehle commit nahi karna chahiye, kyunki woh alias ho sakte hain. Yeh step kyun? Register tags register dependencies dekhte hain, memory wale nahi. Same-address load/store ek memory dependency hai jo $Q_{j} / Q_{k}$ se invisible hai. Hume memory-disambiguation chahiye: store ko tab tak hold karo jab tak earlier load/store addresses compute aur compare na ho jaayein.

Verify: Order Load → (address-compare) → Store hona chahiye. R1=pixel ka address, value 200 (F0=0.5): F2=200, F4=100, memory finally [R1] par 100 rakhta hai. Agar store load ko bypass kar deta, toh woh purana pixel read karta ya garbage write karta — ek correctness bug jo akele tags catch nahi kar sakte.

E8 — Exam twist (CDB structural conflict)

Worked example Statement

Do independent instructions dono same cycle mein execute finish karti hain aur dono CDB chahti hain:

1. ADD R1,R2,R3   # cycle 4 par execute finish karta hai
2. MUL R4,R5,R6   # BHAI cycle 4 par execute finish karta hai

R2=2,R3=3,R5=6,R6=5. Exactly ek CDB hai. Kya hota hai, aur yeh timeline ko kaise change karta hai?

Forecast: Do winners, ek bus. Kya ek result kho jaata hai? Delay hota hai? Tie kaise toot ta hai?

Dono cycle 4 par execute finish karte hain, toh dono Write-Result cycle request karte hain (hamaare model mein cycle 5, $f + 1$ ). Lekin sirf ek CDB slot exist karta hai. Yeh step kyun? Execution units alag hain, lekin broadcast ek shared, 1-per-cycle resource hai — CDB par ek structural hazard.
Cycle 5 — arbiter CDB grant karta hai older instruction ko (program order: ADD, inst 1). ADD $⟨ Add1, 5 ⟩$ broadcast karta hai. Yeh step kyun? Ek fixed priority (program order) ek deterministic, deadlock-free choice guarantee karta hai — koi result kabhi drop nahi hota, ek sirf defer hota hai.
Cycle 6 — MUL broadcasts $⟨ Mult1, 30 ⟩$ , ek cycle late. Uska result multiply unit ke output latch mein cycle 5 mein bus free hone ka wait karte hua baitha raha. Yeh step kyun? Unit apni finished value ek output latch mein tab tak rakhti hai jab tak bus free na ho; kuch recompute ya lost nahi hota, sirf postponed hota hai.
Downstream effect: Mult1 ka wait kar rahi koi bhi instruction cycle 6 mein 30 capture karta hai cycle 5 ki jagah, toh uska execute start cycle 7 par slip karta hai — ek-cycle delay exactly ek step dependency chain mein neeche ripple karta hai, aage nahi. Yeh step kyun? Ek single-cycle CDB stall zyada se zyada ek cycle propagate karta hai har direct consumer ko; yeh compound nahi karta, isliye ek extra CDB usually kaafi hota hai.

Verify: ADD $= 2 + 3 = 5$ , cycle 5 mein written. MUL $= 6 \times 5 = 30$ , cycle 6 mein written (arbiter ne ise ek cycle defer kiya). Correctness intact; sirf timing ek cycle slip karta hai. Real machines precisely is bottleneck ko reduce karne ke liye multiple CDBs add karte hain — E6 limit ko echo karte hue.

Figure s03 — E8 arbitration. Dono ADD (mint) aur MUL (lavender) cycle 4 par finish hote hain aur single butter-coloured CDB ke liye reach karte hain. Solid mint arrow labelled "c5 (priority)" program order se jeet ta hai; dashed lavender arrow labelled "c6 (stalls 1)" exactly ek cycle defer hota hai. Arrow "listeners" mein follow karo: ek-cycle slip jo bhi Mult1 ka wait karta hai use pass on hoti hai, aur wahan ruk jaati hai.

E9 — Control hazard aur commit (branch + reorder buffer)

Plain-Tomasulo jaisa abhi tak describe hua hai results broadcast karta hai aur unhe registers immediately change karne deta hai. Yeh problem hai jaise hi ek branch appear hota hai: hum galat path se instructions execute kar chuke ho sakte hain. Real machines ise reorder buffer (ROB) add karke fix karti hain taaki results program order mein commit karein aur speculative kaam pheka ja sake.

Definition Commit (chautha stage) aur control hazards

Ek control hazard agle instruction ke baare mein uncertainty hai, ek branch ki wajah se jiska direction abhi tak pata nahi. CPU predict karta hai aur guessed path mein speculatively run karta hai.
Reorder buffer ek queue hai jo har in-flight instruction ka result rakhti hai aससे pehle ki use architectural register file touch karne ki permission mile. Commit final stage hai: ROB apne oldest completed entry ka result real register/memory mein program order mein write karta hai.
Misprediction par, branch ke baad har ROB entry squash ho jaati hai (delete); unke tags aur reservation stations flush ho jaate hain. Kyunki kuch bhi speculative real register file tak nahi pahuncha, machine exactly aisa lagti hai jaise sirf correct path chali.

Worked example Statement

1. SUB R1, R6, R7    # 2 cyc -> R1
2. BEQZ R1, skip     # branch: taken if R1 == 0
3. ADD R4, R5, R8    # speculative (not-taken guess)
skip:
4. MUL R9, R2, R3    # correct target if branch taken

R6=8,R7=8 (toh R1=0, branch is taken), lekin predictor ne not-taken guess kiya aur inst 3 run kiya. ADD ka kya hota hai, aur register file mein aakhir mein kya hota hai?

Forecast: ADD pehle se ek galat guess par execute ho gayi. Kya R4 corrupt hoga?

SUB execute karta hai, R1 ROB ke through rename hota hai; uski value 0 order mein commit karegi. Kyun? Har result ab pehle ROB mein land karta hai, register file mein nahi — taaki ise undo kiya ja sake.
BEQZ not-taken predict kiya; ADD issue hoti hai aur speculatively execute karti hai, uska result ek ROB entry mein parked hai (abhi R4 mein nahi likha). Yeh step kyun? ROB ADD ko compute karne deta hai commit kiye bina — speculation with a safety net.
Branch resolve hota hai: R1 = 0, toh IS taken hai → misprediction. Branch ke baad har ROB entry (ADD) squash hoti hai; ADD ka reservation station aur jo bhi tag usne R4 ke liye set kiya woh flush ho jaata hai. Yeh step kyun? Commit se pehle squash karna matlab hai ki wrong-path ADD ne architectural state kabhi touch nahi kiya — control hazard erase ho jaata hai.
Fetch skip par redirect hoti hai; MUL run karta hai aur order mein commit karta hai. Yeh step kyun? Sirf correct-path instructions kabhi commit tak pahunchti hain, toh program order aur correctness preserve hoti hai.

Verify: $R 1 = 8 - 8 = 0$ ⇒ branch taken (galat predict kiya). ADD ka speculative result ( $5 + 8 = 13$ ) discard ho jaata hai, toh R4 unchanged rehta hai. MUL $= 2 \times 3 = 6$ , R9 mein commit karta hai. Final architectural state exactly correct (taken) path se match karta hai — ROB commit stage woh hai jo Tomasulo ko branches ke under safe banata hai.

Recall Self-test

Kaun sa hazard genuine wait force karta hai? ::: RAW (Read-After-Write) — true data dependency. Hamaare timing model ke under, latency $L$ wala op jo cycle $c$ mein issued hua apna result kab write karta hai? ::: Cycle $c + L + 1$ mein (Write-Result last execute cycle ke baad apna cycle hai). E2 mein MUL ka result kyun ignore hota hai? ::: R1 ka tag Add1 pe overwrite ho gaya tha; "sirf tab latch karo jab tag match hو" rule stale Mult1 broadcast ko drop karta hai. E3 mein DIV, R2 par baad wali write se kyun corrupt nahi hota? ::: DIV ne R2 ki value Issue par $V_{j}$ mein copy ki thi; register-file changes us private copy tak nahi pahunch sakte. Uska write cycle 12 par land karta hai ( $1 + 10 + 1$ ). E6 ki independent code mein speed kya limit karta hai? ::: Fixed 2 RS slots (aur single CDB) — ek structural, data nahi, limit. Kaun sa hazard register tags ko invisible hai (E7)? ::: Ek memory (same-address load/store) dependency — memory-disambiguation chahiye. Reorder buffer ek mispredicted branch ko kaise undo karta hai (E9)? ::: Woh branch ke baad har entry ko commit se pehle squash karta hai, toh speculative results kabhi architectural registers tak nahi pahunchte.

Yeh bhi dekho: Tomasulo's algorithm · reorder-buffer · common-data-bus · scoreboarding · instruction-level-parallelism.