Out-of-order execution: Visual walkthrough — Hinglish deep dive

5.3.2 · D2 · Hardware › Advanced Microarchitecture › Out-of-order execution

Neeche sab kuch ek honest sawaal se start hota hai: ek computer kabhi idle kyun baithta hai?

Step 1 — "In program order" ka matlab kya hai

KYA HAI. Ek program choti-choti commands ki ek list hota hai. Har command kuch boxes read karti hai, compute karti hai, aur ek box likhti hai. Har ek box ko hum register kehte hain — socho ek labeled cubby-hole jo ek number hold karta hai. R1, R2, ... register names hain.

Hum ek command aisi likhte hain:

$destination cubby R 1 = first input R 2 + second input R 3$

Left se right padho: "cubby R2 mein jo number hai use lo, cubby R3 mein jo number hai use add karo, jawab cubby R1 mein daal do."

YE YAHAN SE KYU SHURU HO RAHA HAI. Baad ka har idea — dependencies, renaming, reordering — bas yeh statement hai ki kaunsi command ko kaunsa cubby chahiye. Agar hum pehle cubbies fix nahi karte, baaki kuch bhi meaningful nahi hai.

PICTURE. Figure mein char cubbies aur ek instruction dikhti hai jo unme se do ko access kar rahi hai (red = woh destination jo likhi ja rahi hai).

Step 2 — Stall: ek naive CPU time kyun waste karta hai

KYA HAI. Alag-alag instructions alag-alag time lete hain. Ek register add 1 cycle mein khatam ho jaata hai (clock ki ek tick). Ek LOAD — dur ke memory se number fetch karna — 3 ya zyada cycles le sakta hai. Ek cycle bas processor ki ek heartbeat hai.

Ek CPU jo instructions ko bilkul likhne ke order mein chalata hai, usse instruction $k$ finish hona chahiye $k + 1$ start hone se pehle. Isliye ek slow LOAD sab ko peeche rok deta hai — unhe bhi jo uska result nahi maangta. Yeh ruk jaana hi stall hai.

YE KYU MATTER KARTA HAI. Out-of-order execution ka poora point in unnecessary stalls ko khatam karna hai. Dushman ko dekhna zaroori hai usse fight karne se pehle.

PICTURE. Ek timeline (cycles left→right). Red block ek 3-cycle LOAD hai; uske peeche wale black adds idle baithe hain haalaanki woh run kar sakte the.

Step 3 — Dependency graph: kya actually reorder kiya ja sakta hai

KYA HAI. Hum instructions ko tabhi early run karne ki ijazat hai jab aisa karne se jawab nahi badlega. Jo rule reordering forbid karta hai woh hai true dependency:

Parent ke chaar instructions lo aur ek arrow $A \to B$ khiincho jab bhi $B$ woh padhta hai jo $A$ ne likha:

I1: R1 = LOAD [addr1]
I2: R2 = R3 + R4
I3: R5 = R1 + R2      (reads R1 from I1, R2 from I2)
I4: R6 = R7 * R8

$I 3$ R1 (jo I1 ne likha) aur R2 (jo I2 ne likha) read karta hai, isliye $I 1 \to I 3$ aur $I 2 \to I 3$ . I2 ya I4 ki taraf koi arrow nahi — woh free hain.

KYU. Yeh graph, likhne ka order nahi, asli law hai. Jo bhi arrow se connected nahi hai woh kisi bhi order mein run ho sakta hai. In-order execution graph ko ignore karke list ki baat maanta hai; yahi iska ek-maatra kasoor hai.

PICTURE. Chaar instructions nodes ke roop mein; red arrows do true dependencies hain. Dekho I4 akela float kar raha hai.

Yeh hai instruction-level parallelism: independent nodes ek saath execute ho sakte hain.

Step 4 — False dependencies (WAW aur WAR), aur renaming unhe kaise mitaata hai

KYA HAI. Kabhi-kabhi do instructions sirf isliye clash karti hain kyunki woh same cubby name reuse karti hain, na ki isliye ki woh ek value exchange karti hain. Is jhoothe clash ke do flavors hain.

Flavor 1 — Write-After-Write (WAW). Do instructions same name likhti hain:

A1: R1 = R2 + R3
A2: R1 = R6 - R7     (writes R1 again — but a NEW value)

Dono R1 likhti hain. Agar woh out of order finish karti, galat wali R1 mein reh jaati. Phir bhi doosra R1 pehle se bilkul alag number hai — clash sirf isliye hai kyunki naam khatam ho gaye.

Flavor 2 — Write-After-Read (WAR). Ek baad ki instruction ek aisa naam likhti hai jo ek pehle wali instruction abhi read karne wali hai:

B1: R4 = R1 + R5     (reads R1 — the OLD value)
B2: R1 = R6 - R7     (overwrites R1)

B2 ko R1 clobber nahi karna chahiye B1 ke read karne se pehle. Ek baar phir, B1 se B2 koi value flow nahi ho rahi; arrow sirf isliye hai kyunki dono R1 naam ko touch karti hain.

WAW aur WAR dono false dependencies hain: pure naam-reuse, koi real data flow nahi.

FIX. CPU ko extra cubbies (physical registers, ~168) ka ek bada secret pool do, jo programmer ke dekhe architectural registers (~16–32) se kaafi zyada hain. Ek lookup table — Register Alias Table — har ek write ko ek fresh physical cubby se remap karta hai. Baad mein aane wale instruction tags ke saath in cubbies ko confuse karne se bachne ke liye, hum physical registers ko $ϕ_{47}$ (Greek "phi", "physical") likhte hain:

$name programmer wrote R 1 ⟼ fresh physical cubby, chosen now ϕ_{47}$

$physical registers ≫ architectural registers$

Term by term: left symbol woh naam hai jo code use karta hai; $⟼$ ka matlab hai "is waqt mapped hai"; $ϕ_{47}$ ek private cubby hai jise programmer kabhi naam nahi deta. WAW mein, do writes ab alag physical cubbies mein jaati hain. WAR mein, B2 ki write ek fresh cubby mein jaati hai, isliye B1 abhi bhi purani wali read karta hai untouched. Dono false arrows gaayab ho jaate hain.

KYU. False dependencies delete karne se sirf true arrows bachte hain — Step 3 ka pure data-flow graph. Ab CPU maximally schedule kar sakta hai.

PICTURE. Top row: ek false WAW arrow (R1 par do writes). Bottom row: ek false WAR arrow (R1 read, phir R1 write). Right side: renaming ke baad, har write ko apna red physical cubby $ϕ$ milta hai — dono arrows gone.

Puri machinery ke liye dekho Register renaming.

Step 5 — Ready condition: ek instruction kab fire kar sakti hai?

KYA HAI. Har waiting instruction ek chote holding pen mein baithti hai jise reservation station kehte hain. Yeh instruction aur uske do inputs, $src_{1}$ aur $src_{2}$ , ke liye slots hold karta hai. Har slot do states mein se ek mein hota hai:

Ready — actual number slot mein baitha hai.
Waiting — slot ki jagah ek tag hold kar raha hai: producer instruction ka naam (hum producer tags ko $P_{j}$ likhte hain, ek Producer instruction, Step 4 ke physical cubbies $ϕ$ se alag) jo value supply karega.

Instruction tabhi execute kar sakti hai jab dono inputs ready hon:

$Ready (I) = Ready (src_{1}) \land Ready (src_{2})$

Term by term: $Ready (I)$ poori instruction ka yes/no hai; $\land$ logical AND hai (sirf tabhi true jab dono sides true hon); har $Ready (src_{i})$ ek input slot ka yes/no hai. Ek bhi waiting slot matlab poori cheez wait karti hai.

AND KYU, OR KYU NAHI? Ek add ko dono numbers chahiye add karne ke liye. Koi bhi missing karega toh result garbage hoga. Isliye gate sabse strict wala hai: AND.

PICTURE. Ek reservation station box: src1 filled (black number, ready), src2 abhi bhi ek red producer tag $P_{j}$ hold kar raha hai (waiting). Instruction abhi fire nahi kar sakti.

Step 6 — Wakeup: Common Data Bus broadcast karta hai

KYA HAI. Jab ek producer $P_{j}$ finish ho jaata hai, woh apna result sabko ek saath ek shared wire par shout karta hai, Common Data Bus (CDB). Yeh shout ek pair hai:

$(kaun hoon main tag : P_{j}, wo number jo main ne banaya value : V)$

Har reservation station CDB ko snoop (sun'ta) karta hai. Pehle hume logic notation ke do chote pieces chahiye, har ek use se pehle earn kiya gaya:

Un do words ke saath, wakeup rule aisa padhta hai:

$\forall I : trigger: yeh slot P_{j} ka wait kar raha hai (src_{i} = P_{j}) \Rightarrow consequence: value swallow karo, Ready flip karo (src_{i} \leftarrow V, Ready (src_{i}) \leftarrow true)$

Term by term, left se right: $\forall I$ = "har station mein har instruction ke liye, yeh check karo"; trigger $src_{i} = P_{j}$ poochta hai "kya yeh slot producer $P_{j}$ ka wait kar raha hai?"; $\Rightarrow$ kehta hai "agar haan, toh yeh karo"; arrow $\leftarrow$ matlab hai "assign hota hai"; toh slot value $V$ swallow karta hai aur khud ko Ready flip kar leta hai.

SABKO BROADCAST KYU, EK-EK KO KYU NAHI? Kai instructions same result ka wait kar rahi hoti hain. Ek parallel shout unhe sab ko ek cycle mein jagaata hai; list walkthrough karna har waiter ke liye cycles cost karega — isliye rule $\forall$ se start hota hai (ek saath har waiter), "agle waiter" se nahi.

PICTURE. Ek producer red CDB wire drive karta hai; teen stations snoop karte hain; do matching tags light up hote hain aur fill ho jaate hain.

Step 7 — Structural limits: utni hi buses aur ports hain

KYA HAI. Steps 5–6 ne assume kiya tha ki koi bhi ready instruction fire kar sakti hai aur koi bhi finished wali broadcast kar sakti hai. Real hardware finite hai. Do structural hazards aate hain:

Execution ports. CPU ke paas fixed number of execution units (ports) hote hain. Agar zyada instructions ready hain ports se, toh sirf utni hi is cycle mein fire hoti hain; baaki ek aur cycle wait karti hain. Scheduler age/priority se chunti hai.
CDB bandwidth. Common Data Bus ek cycle mein sirf fixed number of results carry kar sakta hai (aksar ek ya do). Agar do instructions same cycle mein finish hoti hain lekin sirf ek bus slot hai, toh ek broadcast ek cycle delay ho jaata hai — aur uske waiters ek cycle baad jagenge.

Ek structural hazard ek stall hai jo kafi machine nahi hai ki wajah se hua, data arrow ki wajah se nahi.

YE KYU MATTER KARTA HAI. Yeh humara pehle wala bound change karta hai. Zero dependencies ke saath bhi, throughput execution width (kitne ports) aur result-bus width se capped hai. Yahi parent ke IPC bound mein "Execution width" term hai.

PICTURE. Chaar ready instructions, sirf do ports: do ab fire hote hain (red), do agle cycle ke liye hold hote hain. Ek doosra panel do finishers ko ek single CDB slot ke liye compete karte dikhata hai.

Step 8 — Sab kuch jodna: out-of-order timeline

KYA HAI. Ab Step 3 ki chaar instructions ko run hote dekho. Latencies: LOAD = 3 cycles, baki sab = 1 cycle. Ek instruction us cycle ke baad fire hoti hai jab uska last input ready hota hai. Assumption clearly stated: is machine mein do execution ports hain aur CDB itna wide hai ki is chhote example mein koi do results collide nahi karte — toh koi structural hazard yahan nahi aata.

Har instruction ki start cycle trace karo:

I1 (LOAD) ki koi dependency nahi → cycle 1 mein fire hoti hai, busy cycles 1–3, result cycle 3 ke end mein ready.
I2 (add) free hai → cycle 1 mein doosre port par fire hoti hai, result cycle 1 ke end mein ready.
I4 (multiply) free hai lekin dono ports cycle 1 mein busy hain (I1, I2), isliye cycle 2 mein fire hoti hai, cycle 2 ke end mein ready.
I3 ko R1 chahiye (end of 3 par ready) aur R2 (end of 1 par ready). Uska last input cycle 3 ke end mein aata hai, isliye I3 cycle 4 mein fire hoti hai, cycle 4 ke end mein ready.

Last kaam cycle 4 ke end mein khatam hota hai, isliye out-of-order span 4 cycles hai.

In-order machine ke liye, instructions ko likhne ke order mein same do ports par run karna hoga, aur har ek program order mein jagah banne ka wait karega: I1 cycles 1–3, I2 cycle 4, I3 cycle 5, I4 cycle 6 → span 6 cycles.

$speedup = \frac{in-order span}{out-of-order span} = \frac{6}{4} = 1.5 \times$

Term by term: numerator 6 = in-order cycles; denominator 4 = out-of-order cycles; ratio batata hai reordered machine kitni baar faster finish karti hai.

1.5× HI KYU, ZYADA KYU NAHI? Kyunki true chain $I 1 \to I 3$ genuine hai aur chhoti nahi ki ja sakti — yeh critical path hai, graph mein sabse lamba arrow-path. I3 kabhi bhi cycle 3 ke end se pehle start nahi ho sakti chahe machine kitni bhi clever ho, isliye kam se kam 4 cycles unavoidable hain. OoOE wasted stalls delete karta hai (I2, I4 ab load ke peeche queue nahi karti), lekin real dependencies ko kabhi nahi. Zyada free instructions aur lambi chains wale bade programs mein 2–3× milta hai.

PICTURE. Do stacked timelines, in-order (upar, 6 cycles) vs out-of-order (neeche, 4 cycles). Red bars un do cycles ko highlight karte hain jo OoOE save karta hai.

Step 9 — Memory operations: sabse tricky out-of-order case

KYA HAI. Registers easy hain — unke naam instruction mein visible hote hain, isliye CPU ko decode karte hi har register dependency pata chal jaati hai. Memory alag hai. Ek STORE [addr] memory location likhta hai aur LOAD [addr2] ek read karta hai, lekin machine aksar actual addresses tab tak nahi jaanti jab tak woh instructions unhe compute na kar lein. Isliye woh pehle se nahi bata sakti ki ek load aur ek pehle wala store same location ko touch karte hain ya nahi. Yahi unknown hai memory disambiguation problem.

Pending memory operations manage karne ke liye hum ek nayi structure introduce karte hain, use se pehle define karke:

Teen ordering rules jo machine kabhi nahi todregi:

Memory RAW (true): ek LOAD ko same address pe sabse recent earlier STORE ki value return karni chahiye. Yeh memory ke through genuine value flow hai — unbreakable, bilkul register RAW jaisi.
Memory WAW (false): same address par do STOREs ko memory mein baad wale ki value chhodni chahiye. Writes ka order matter karta hai, lekin unke beech koi value flow nahi.
Memory WAR (false): ek STORE ko woh location overwrite nahi karni chahiye jo ek earlier LOAD ko abhi bhi read karni hai.

Load ek value lene se pehle, LSQ har earlier store ka address scan karta hai:

$load may bypass earlier stores ⟺ every earlier store S has addr (S) \neq = addr(load)$

Term by term: $⟺$ = "exactly when / if and only if"; right side kehta hai har earlier store ka address load ke address se alag hai. Agar sab alag hain, toh load aage skip kar sakta hai aur memory read kar sakta hai. Agar koi ek match karta hai, toh load ko us store ki value directly leni hogi — yeh hai store-to-load forwarding (value seedha store buffer se do, memory skip karo) — ya wait karo agar us store ki value abhi ready nahi.

False memory hazards (WAW / WAR) handle karna. Register WAW/WAR ke unlike, memory locations ko ek huge pool mein rename nahi kiya jaata — address space hi address space hai. Iska bajaye CPU stores ko LSQ mein program order mein rakhta hai aur store ko real memory tabhi likhne deta hai jab woh commit kare (retire kare). Loads memory se race karne ki bajaye LSQ se read karte hain (forwarding ke through). Isliye memory WAW resolve hota hai stores ko order mein commit karke, aur memory WAR isliye resolve hota hai kyunki younger store ki value LSQ mein bottled rehti hai jab tak har older load pehle se old value read na kar le. False memory arrows is tarah ordered commit se neutralize hote hain, renaming se nahi.

Degenerate case — galat guess (memory speculation). Aggressive CPUs ek load ko jaldi jaane dete hain, guess karte hue ki koi earlier store alias nahi karega, yeh jaane bina ki sab earlier store addresses kya hain. Agar baad mein compute hua ek store address match karta hai, toh woh ek memory-ordering violation tha: speculatively-executed load — aur jo bhi uski value use kar raha tha — squash aur re-execute hota hai correct forwarded value ke saath. Yahi flush-and-restart machinery hai jo exceptions aur mispredicted branches ke liye use hoti hai.

ITne care KYU? Ordered memory ke bina, out-of-order execution silently data corrupt karta: ek load stale bytes read karta, ya ek store ek value clobber karta jo abhi bhi ek earlier read ki deni thi. LSQ memory ko usi true/false dependency logic ke saath follow karata hai jo humne registers ke liye banaya — true RAW respected, false WAW/WAR in-order store commit se neutralize. Yahi ordering discipline cache coherence aur memory consistency models ko bhi support karti hai jab kai cores memory share karte hain.

PICTURE. Ek LSQ column program order mein; ek young load do stores se peeche reach karta hua; red store uska address share karta hai, plain memory read ki jagah store-to-load forwarding force karta hai.

Step 10 — Degenerate case: ise in-order jaisa dikhana (ROB)

KYA HAI. Early execute karne se ek khatara paida hota hai: results scrambled order mein finish hote hain. Lekin agar koi instruction fault kare (jaise divide-by-zero, bad memory), toh duniya ko exactly waise dikhna chahiye jaise program cleanly us instruction par ruka — usse pehle sab committed, uske baad sab erased. Yeh clean picture hai precise exception.

Fix hai reorder buffer (ROB): ek queue jo har in-flight instruction ko program order mein hold karta hai. Instructions execute out of order hoti hain lekin retire (permanent ho jaati hain, yaani woh architectural state likhti hain jo programmer dekhta hai) sirf head se hoti hain, strictly program order mein. Yeh ordered retirement woh mechanism hai jo precise exceptions guarantee karta hai:

Head instruction $I_{h}$ tabhi retire ho sakti hai jab:

$Can_Commit (I_{h}) = Complete (I_{h}) \land \neg Exception (I_{h})$

Term by term: $I_{h}$ queue ke head par instruction hai; $Complete$ = woh execute finish kar chuki; $\land$ = AND (Step 5 se); $\neg$ = logical NOT (true ko false karta hai); $Exception$ = woh fault hua. Isliye woh tabhi retire hoti hai agar finished aur fault-free ho.

Fault case dikhane ke liye hum apne running program mein do aur instructions add karte hain, I5 aur I6, I3 ke baad fetch hue aur speculatively execute hue (early, yeh jaane bina ki woh safe hain):

I5: R9  = R1 + 1     (fetched after I3, executed early)
I6: R10 = R9 * 2     (fetched after I5, executed early)

Maano I3 fault karta hai. Toh: I3 ke peeche sab kuch flush karo (including I5, I6), un speculatively-computed results ko throw away karo, architectural state ko I2 ke just baad restore karo, aur OS ko control do.

KYU. Yeh poori scheme ki degenerate boundary hai: chahe execution maximum scrambled ho, in-order retirement guarantee karta hai ki outside world (memory, interrupts, ek debugger) ek clean sequential story dekhe. Andar fast, bahar order — aur yeh bilkul isliye possible hai kyunki stores program order mein commit karte hain (Step 9) aur results yahan program order mein retire karte hain, isliye mid-program fault ko precise dikhaya ja sakta hai.

PICTURE. ROB ek queue ke roop mein. I1,I2 retired (left, done); I3 head par faulted (red); I5,I6 finished lekin peeche baithe hain, flush hone wale hain.

Yeh clean rollback exactly wahi hai jo speculative execution aur branch prediction ko safe banata hai — galat guesses simply kabhi retire nahi hoti.

Ek-picture summary

KYA HAI. Is page ka har idea ek single flow mein compress: instructions in order enter karti hain, rename hoti hain (false WAW/WAR arrows khatam), reservation stations mein wait karti hain jab tak CDB unhe jagaaye, finite ports ke liye compete karti hain, LSQ ke through memory ordering respect karti hain, out of order execute hoti hain, ROB mein land karti hain, aur in order jaati hain taaki exceptions precise rehein.

Recall Feynman retelling — saral shabdon mein kaho

Ek to-do list imagine karo. Ek bewakoof worker items ko strictly upar se neeche karta hai, isliye ek slow item (delivery ka wait) poori list freeze kar deta hai chahe baad wali items ko kuch bhi na chahiye. Ek smart worker pehle arrows kheenchta hai: "item C ko item A ka result chahiye." Sirf woh arrows real rules hain. Agar do items sirf isliye clash karti hain kyunki woh same sticky-note par scribble karti — ya toh dono likhte hain, ya ek likhta hai jabki doosra abhi bhi padhne wala hai — smart worker har ek ko apna fresh note deta hai (renaming), aur dono fake clashes gaayab. Ab har item ek waiting-tray mein baithti hai apne inputs ke saath; jaise hi ek finished item poore room mein apna jawab shout karta hai (the bus), koi bhi tray jo woh jawab miss kar rahi thi use grab karta hai aur runnable ho jaata hai. Lekin utne hi haath hain (ports) aur ek loudspeaker (the bus), isliye agar ek saath bahut zyada items ready hain, kuch ek turn wait karte hain — yeh ek structural jam hai, real dependency nahi. Memory items extra sneaky hain: do ek hi shelf touch kar sakte hain bina worker ko pata chale jab tak der na ho jaaye, isliye ek special ledger (the LSQ) shelf numbers check karta hai kisi bhi read ko aage skip karne dene se pehle, aur stores tabhi actually shelf par likhte hain jab woh finally file hote hain. Finally, finished work sirf ek in-order stack ke top se filed hota hai (the reorder buffer); agar koi item disaster nikle, us ke baad filed sab kuch shred ho jaata hai aur desk aisa dikhta hai jaise us item ne sab kuch cleanly rok diya. Andar fast, bahar tidy.

Recall Quick self-test

Renaming se kaunsi dependency types delete hoti hain? ::: False wali — WAW aur WAR (naam-reuse), true RAW kabhi nahi. $ϕ_{47}$ aur $P_{j}$ mein kya fark hai? ::: $ϕ_{47}$ ek physical register hai (ek storage cubby jo number hold karta hai); $P_{j}$ ek producer tag hai (us instruction ka naam jo value banayegi). CDB wakeup rule mein $\forall$ aur $\Rightarrow$ ka kya matlab hai? ::: $\forall$ = "har ek ke liye" (har waiting slot check karo); $\Rightarrow$ = "leads to" (agar tag match kare, toh value swallow karo aur Ready flip karo). Instruction ko DONO operands ka wait kyun karna padta hai (AND, OR nahi)? ::: Ek operation ko correct result produce karne ke liye har input chahiye; missing input matlab garbage. CPU hamesha LOAD ko STORE se pehle kyun reorder nahi kar sakta? ::: Unke addresses alias kar sakte hain (same location); LSQ confirm kare ki koi earlier store woh address hit nahi karta, warna store ki value forward karta hai ya load re-execute karta hai. False memory WAW/WAR hazards kaise neutralize hote hain? ::: Renaming se nahi — stores program order mein memory mein commit karte hain aur tab tak LSQ mein bottled rehte hain, isliye writes kabhi un reads se reorder nahi hoti jo abhi bhi old value ki zaroorat rakhte hain. Execution out-of-order hone ke bawajood retirement program order mein kyun hoti hai? ::: Precise exceptions ke liye — reorder buffer apne head se order mein retire karta hai, isliye outside world hamesha ek clean "exactly yahan ruka" boundary dekhta hai. Step 8 ke example mein out-of-order span aur speedup kya hai? ::: 4 cycles out-of-order vs 6 in-order, 6/4 = 1.5× speedup, true I1→I3 critical path se limited.