Visual walkthrough — Tomasulo's algorithm

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

Hum yeh exact program poora chalenge:

1. MUL  R1, R2, R3    # takes 5 cycles
2. ADD  R4, R1, R5    # takes 2 cycles, needs R1
3. SUB  R1, R6, R7    # takes 2 cycles, WRITES R1 again
4. DIV  R8, R1, R9    # takes 40 cycles, needs the NEW R1

Starting values: $R2=2,R3=3,R5=10,R6=20,R7=8,R9=2$.

Step 0 — Teen objects, ek baar draw kiye

KYA. Koi bhi instruction move karne se pehle, in pieces se milo. Ek register (jaise R1) ek labelled box hai jo ya to ek real number hold kar sakta hai ya ek sticky note jo kehti hai "koi aur meri value la raha hai." Ek reservation station (RS) ek waiting seat hai jo ek functional unit se judi hoti hai; iska naam hota hai jaise Mult1 ya Add2. Common data bus (CDB) ek single wire hai jise har box aur har seat sun sakti hai.

KYU sirf yahi teen aur kuch nahi? Kyunki Tomasulo ki poori trick yeh hai ki instructions ko register names pe ladhna band karke seats pe ladao. Iske liye hume chahiye (a) koi jagah baithe aur wait karo — the seat; (b) ek tarika yeh kehne ka "main seat X pe wait kar raha hoon" — the tag; aur (c) seat X ke liye ek tarika "done, yeh number hai!" chillane ka — the bus. Koi ek hata do aur trick gir jaati hai.

PICTURE. Legend ek baar padho; baad ke har figure mein yahi exact shapes aur colours reuse hote hain.

Yeh link poori padhai mein matter karta hai: renaming us naming problem ka hardware version hai jo data-hazards mein hai, aur Tomasulo out-of-order-execution ki classic form hai.

Step 1 — Cycle 1: MUL ne ek seat pakdi aur R1 pe ek tag lagaya

KYA. Hum MUL R1, R2, R3 issue karte hain. Ek free multiply seat hai, Mult1, toh MUL usme baith jata hai. Hum iske sources R2 aur R3 padhte hain — dono real numbers hold karte hain ($2$ aur $3$), toh hum unhe seedha seat mein copy karte hain: $V_j=2,V_k=3$. Phir hum crucial move karte hain: hum destination R1 pe ek sticky note lagate hain jo kehti hai "Mult1 mujhe fill karega."

KYU. Operands abhi padhna hi reason hai ki WAR hazards gayab ho jaate hain: MUL ne physically $2$ aur $3$ apni seat mein copy kar liye hain, toh baad mein R2 ya R3 ko overwrite karne wali koi bhi cheez use hurt nahi kar sakti. R1 ko tag karna hi reason hai ki R1 ke future readers jaanenge kaun wait karna hai — naam "R1" nahi, balki seat Mult1.

PICTURE. Sticky note (plum) R1 pe land karti hai; seat bhari hai aur ready hai.

$\text{Mult1}:\underset{\text{copied from }R2}{\underbrace{V_j=2}}\underset{\text{copied from }R3}{\underbrace{V_k=3}}\underset{\text{nothing to wait for}}{\underbrace{Q_j=\text{NULL}}}\underset{\text{nothing to wait for}}{\underbrace{Q_k=\text{NULL}}}$

$R1.\text{tag}\leftarrow \text{Mult1}(\text{"my value is coming from seat Mult1"})$

Dono tags NULL hain, toh MUL immediately compute karna shuru kar deta hai — yeh cycle $1+5=6$ pe finish hoga.

Step 2 — Cycle 2: ADD ko R1 chahiye, toh woh IOU copy karta hai

KYA. Hum seat Add1 mein ADD R4, R1, R5 issue karte hain. Ab hum iske sources padhte hain. R5 ek real number hold karta hai ($10$) → copy karo: $V_k=10$. Lekin R1 abhi ek number nahi hai — woh sticky note Mult1 pehne hua hai. Toh value ki jagah, ADD note copy karta hai: $Q_j=\text{Mult1}$. Aakhir mein, ADD ke apne destination ko tag karo: R4.tag ← Add1.

KYU. Yahi renaming ka dil hai. ADD ko R1 naam ka register jaanna zaroori nahi; use woh number chahiye jo MUL produce karne wala hai. $Q_j=\text{Mult1}$ store karke, ADD ne apne aap ko ek to-do likha hai: "mujhe tab jagao jab seat Mult1 chillaye." Yeh answer karta hai "mere liye value kaun produce karta hai?" na ki "kaun sa naam ise hold karta hai?"

PICTURE. Dekho Add1 ke $Q_j$ slot se seat Mult1 ki taraf teal arrow — woh arrow hi actual dependency hai, physical bana di gayi hai.

$\text{Add1}:\underset{\text{waiting on that seat}}{\underbrace{Q_j=\text{Mult1}}}\underset{\text{value not here yet}}{\underbrace{V_j=\varnothing }}\underset{R5\text{ was ready}}{\underbrace{Q_k=\text{NULL},V_k=10}}$

Add1 mein $Q_j\ne \text{NULL}$ hai, toh Step 0 ke rule se woh abhi execute nahi kar sakta. Woh wait karta hai.

Step 3 — Cycle 3: SUB ne R1 ka tag overwrite kiya — false dependency yahan khatam hoti hai

KYA. Hum seat Add2 mein SUB R1, R6, R7 issue karte hain. Iske sources R6, R7 dono real numbers hain ($20$ aur $8$) → $V_j=20,V_k=8$, dono tags NULL. Ab woh loaded moment: SUB R1 likhta hai, toh hum R1 pe sticky note overwrite karte hain. Pehle yeh kehti thi Mult1; ab kehti hai Add2.

KYU — yahi is page ka poora point hai. Program order mein MUL R1 ko pehle likhta hai, SUB se pehle. Ek naive machine SUB ko MUL ka wait karne ke liye force karti R1 ko clobbering se bachane ke liye (ek WAW hazard) — ek dependency jo sirf R1 ke shared naam ki wajah se exist karti hai, kisi real data ki wajah se nahi. Tomasulo refuse karta hai. Kyunki R1 sirf ek box hai jo ek note pehne hua hai, note overwrite karna free aur instant hai. Purana note Mult1 ab orphaned hai: kisi bhi box ki arrow ab usi point nahi karti (halanki Add1 use abhi bhi privately yaad karta hai — neeche dekho). Toh:

• Kyunki $Q_j=Q_k=\text{NULL}$ hai, SUB isi cycle execute karta hai, abhi bhi chal rahe MUL ke parallel mein.
• R1 pe naam ki collision do alag seat names Mult1 aur Add2 se resolve hoti hai. Yahi register renaming hai.

PICTURE. Dekho sticky note R1 pe cross out hoke replace hoti hai (plum → replaced plum). Orphaned tag Mult1 greyed out hai — Add1 ke andar abhi bhi yaad, R1 ke liye bhool gayi.

$R1.\text{tag}:\text{Mult1}\stackrel{\text{SUB issues}}{\mapsto }\text{Add2}$

Step 4 — Cycle 4: DIV automatically NEW R1 ka wait karta hai

KYA. Seat Mult2 mein DIV R8, R1, R9 issue karo. Sources padho: R9 ek number hai ($2$) → $V_k=2$. R1 pe abhi note Add2 hai (pichhle cycle mein SUB ne lagaya tha), toh DIV woh note copy karta hai: $Q_j=\text{Add2}$. Apna destination tag karo: R8.tag ← Mult2.

KYU. Dekho renaming ne free mein kya kiya: DIV chahta tha "woh R1 jo SUB produce karega," aur sirf R1 pe jo bhi note abhi hai usse padh ke, usne exactly Add2 pakad liya — kabhi Mult1 nahi. Humne is routing ke liye koi special logic nahi likha. Ek-sticky-note-per-register discipline guarantee karta hai ki har reader latest producer ko latch karta hai. Yahi disambiguation idea hai jo ek reorder-buffer aur scoreboarding ko bhi solve karni padti hai, lekin yahan yeh ek rule se nikal aata hai.

PICTURE. Mult2 ke $Q_j$ se teal dependency arrow Add2 pe point karta hai, Mult1 pe nahi.

$\text{Mult2}:\underset{\text{the NEW R1}}{\underbrace{Q_j=\text{Add2}}}\underset{R9\text{ ready}}{\underbrace{Q_k=\text{NULL},V_k=2}}R8.\text{tag}\leftarrow \text{Mult2}$

Mult2 mein $Q_j\ne \text{NULL}$ → woh Add2 finish hone ka wait karta hai.

Step 5 — Cycle 5: SUB CDB pe broadcast karta hai — do listeners alag-alag react karte hain

KYA. SUB cycle 3 pe shuru hua, 2 cycles leta hai, toh cycle 5 pe khatam hota hai aur CDB pe chillata hai: $⟨\text{Add2},20-8=12⟩$ Har seat aur har box ise sunta hai. Unme se do ko fark padta hai:

• Seat Mult2 mein $Q_j=\text{Add2}$ tha → woh $12$ ko $V_j$ mein grab karta hai aur tag clear karta hai: $Q_j\leftarrow \text{NULL}$.
• Box R1 ka note $=\text{Add2}$ tha → woh $12$ apni real value ke roop mein grab karta hai aur note ukhaad deta hai.

KYU sabko ek saath broadcast karo? Kyunki issue time pe kisi ko nahi pata tha kitne future instructions ko Add2 ka result chahiye hoga — zero ho sakta hai, paanch bhi ho sakta hai. Ek shared wire pe ek shout ek cycle mein unhe saari reach kar leta hai bina koi list maintain kiye. Yeh ek wire hi common-data-bus hai, aur yeh throughput bottleneck hai (sirf ek result per cycle chilla sakta hai).

PICTURE. Add2 se ek orange pulse nikalti hai; do teal arrows fan out karte hain — Mult2 ke slot mein aur box R1 mein.

$\text{After the shout: }\text{Mult2}.Q_j=\text{NULL},V_j=12R1=12(\text{note gone})$

Ab Mult2 ke dono operands NULL hain → DIV cycle 5 pe execute karna shuru karta hai, $5+40=45$ pe finish hoga.

Step 6 — Cycle 6: MUL broadcast karta hai — aur R1 sahi se ignore karta hai

KYA. MUL cycle 1 pe shuru hua, 5 cycles leta hai → cycle 6 pe khatam hota hai aur chillata hai: $⟨\text{Mult1},2\times 3=6⟩$ Kaun react karta hai?

• Seat Add1 mein $Q_j=\text{Mult1}$ tha (Step 2 se) → $6$ ko $V_j$ mein grab karta hai, tag clear karta hai. Add1 mein ab dono operands hain → ADD execute karna shuru karta hai.
• Box R1? Iska note ab Add2 kehta hai — actually note already gone hai (Step 5 mein ukhaad diya gaya). Either way $R1.\text{note}\ne \text{Mult1}$, toh R1 shout ignore karta hai.

KYU yeh payoff hai. Yeh exact moment hai jab WAW hazard harmless prove hota hai. MUL ka result 6 program terms mein R1 ki stale value thi; ise box mein jaane dena ek bug hota. Tag-match check (kya mera note us shouting seat ke barabar hai?) ise automatically filter kar deta hai. Isi beech legitimate consumer, ADD, abhi bhi 6 receive karta hai — kyunki usne IOU copy kiya tha, register name nahi. Data exactly wahan jaata hai jahan program ka real dataflow kehta hai, aur kahin nahi.

PICTURE. Mult1 se orange pulse; ek teal arrow Add1 mein land karti hai; ek red crossed-out arrow dikhata hai R1 value refuse kar raha hai.

$R1.\text{note}=\varnothing \ne \text{Mult1}\Rightarrow R1\text{ discards }6,\text{Add1}.V_j\leftarrow 6(\text{ADD may run})$

Baaki traffic bookkeeping hai: ADD cycle 8 pe finish hota hai aur R4=16 likhta hai; DIV cycle 45 pe finish hota hai aur R8 = 12/2 = 6 likhta hai. Har hazard already dissolve ho chuka hai.

Step 7 — Degenerate cases, taaki kuch surprise na kare

KYA. Teen corner situations jinhe walkthrough ne brush past kiya. Neeche wale summary figure mein har ek ka apna frame hai.

1. Koi free seat nahi (structural hazard). Agar Issue pe needed functional unit ki har seat busy hai, toh instruction slot nahi le sakta. Woh Issue pe stall karta hai — aage nahi jaata. Yeh woh akela stall hai jo Tomasulo rakhta hai.
2. Dono operands already ready. Agar koi bhi source note nahi pehne hua (jaise Step 3 mein SUB), toh issue pe dono $Q$ fields NULL hain → instruction same cycle mein execute kar sakta hai jis cycle mein issue hua. Koi waiting nahi.
3. Ek producer jise koi nahi sunta. Step 6 mein, seat Mult1 ne chillaya lekin iska result sirf Add1 (ek consumer) ko chahiya tha, aur iska destination box R1 aage badh gaya tha. Yeh normal aur safe hai: broadcasting unconditional hai, react karna tag-match se hota hai, toh ek unwanted result simply koi listener nahi paata.

KYU teeno dikhao? Kyunki ek reader jo sirf happy path dekha hoga woh pehli baar seat full hone pe, ya pehli baar broadcast "kahin nahi jaata" lagney pe panic karega. Yeh errors nahi hain — yeh designed behaviour hai.

PICTURE. Teen chhote panels: (a) ek full seat instructions ko reject karti hai; (b) ek instruction ek hi cycle mein issue aur run karti hai; (c) ek shout jiske koi listener nahi.

Ek-picture summary

KYA. Upar sab kuch, ek timeline mein compress kiya. Horizontal axis cycle number hai; har instruction ek coloured bar hai (issue → execute → write). Do events starred hain: cycle 3 pe R1 pe tag-overwrite (jahan false dependency marti hai) aur cycle 6 pe ignored broadcast (jahan WAW hazard harmless prove hota hai). Teal arrows real dataflow dikhate hain — Mult1 → Add1 aur Add2 → Mult2 — jo kabhi ek doosre ko touch nahi karte, yahi exact reason hai ki MUL+SUB+DIV time mein overlap karte hain.

Related depth: yeh decoupling hi hai jo instruction-level-parallelism badhata hai; same tag trick ka load/store version memory-disambiguation hai; aur ek Hinglish retelling 5.3.03 Tomasulo's algorithm (Hinglish) pe milti hai.