Speculative execution: Visual walkthrough — Hinglish deep dive

5.3.11 · D2 · Hardware › Advanced Microarchitecture › Speculative execution

Parent: Speculative execution · Isse saath padhein Hinglish version.

Is page pe hum ek number bilkul zero se banayenge: woh average extra cost per branch jab CPU yeh guess karta hai ki code kis taraf jayega. Har cheez ko pehle draw karenge, phir use karenge. Akhir mein aap kisi bhi branch ke liye bata sakenge ki guessing ek achha bet hai ya nahi.

Yahaan pipelines ki koi prior knowledge nahi chahiye. Agar koi word naya lage, pehle draw karenge.

Step 1 — "Branch" actually hota kya hai

KYA. Ek program instructions ki ek list hoti hai jo CPU ek ke baad ek run karta hai. Zyaadatar waqt woh seedha list mein neeche chalte rehta hai. Lekin kabhi kabhi usse ek chauraha milta hai: ek if. Kya hum left jayein ya right? Woh chauraha hi branch kehlaata hai.

KYUN. CPU dono raaste ek saath nahi le sakta. Use ek road chunna padta hai. Lekin — aur yahi poori kahani hai — use abhi tak pata nahi kaunsa raasta sahi hai, kyunki jawab ek aisi value par depend karta hai jo abhi bhi compute ho rahi hai.

PICTURE. Figure dekhein. Blue line instructions ka stream hai jo neeche flow kar raha hai. Yellow diamond (branch) par woh split hoti hai. Ek road taken hai, ek not taken. Sirf baad mein, jab red clock ticking finish karta hai, CPU ko pata chalta hai kaunsa road sahi tha.

Step 2 — Pipeline: waiting itni costly kyun hai

KYA. Ek modern CPU ek time mein ek instruction nahi karta. Woh ek assembly line chalata hai: jab instruction 5 decode ho rahi hai, instruction 4 execute ho rahi hai, instruction 3 apna result likh rahi hai, aur aise hi aage. Line par har station ek pipeline stage hai. Stations ki sankhya pipeline depth hai, jise hum $D$ kehte hain.

$D$ kyun draw karein. Baad mein jo bhi symbols use karenge woh sab $D$ se bane hain. Toh ise abhi anchor karte hain: $D$ bas assembly line mein boxes ki count hai. Real CPUs mein $D \approx 15$ se $20$ hota hai.

PICTURE. Figure mein $D = 6$ boxes hain. Ek instruction left box mein enter karti hai aur har clock tick par ek box right ki taraf chalti hai. $D$ ticks lagte hain right end se bahar nikalne mein. Branch ka jawab sirf far right box (red) ke paas aata hai — kaafi ticks ke baad jab hum pehli baar left par branch se mile the.

Problem ab dikhti hai: Step 1 se jawab line ke end par aata hai, lekin Step 2 se hume road start par chunni thi. $D$ ticks ka gap hai. Agar hum poori assembly line freeze karke jawab ka wait karein, toh woh $D$ ticks beet jaate hain jab line se koi useful work nahi nikla. Woh khaali, kaam-ke-bina gap hi pipeline bubble hai.

Step 3 — Juaa: wait karne ki jagah guess karo

KYA. $D$ ticks freeze karne (Step 2 ka bubble) ki jagah, CPU guess karta hai ki branch kaunsa road leta hai aur guessed road se instructions assembly line mein turant march karna shuru kar deta hai.

KYUN yeh aur wait nahi. Agar hum wait karein, toh poora bubble khaayenge — $\approx D$ ticks har ek branch par. Agar hum guess karein aur zyaadatar sahi niklen, toh woh ticks sirf rare galat guess par lose karenge. Yahi poora bet hai Speculative execution ka.

PICTURE. Do timelines. Upar (green): "wait" — ek bada khaali gap $D$ bubble ticks ka kaam resume hone se pehle. Neeche (blue): "guess" — koi gap nahi, kaam seedha flow karta hai. Blue path chhota hai jab bhi guess sahi hota hai.

Lekin agar hum results compute karein pehle hi sure hue bina ki chahiye bhi hai ya nahi, toh hume un results ko park karne ki ek safe jagah chahiye — kahin jo abhi official count nahi hoti. Woh jagah hai Reorder buffer (ROB).

Step 4 — Ek galat guess ka cost (penalty $P$ )

KYA. Maano guess galat tha. Branch ke peeche road par bheje gaye har instruction ka kachra ban gaya. Hume sab ko bahar fekna padega — is act ko squashing kehte hain — aur pipeline ko sahi road se refill karna padega.

KYUN yeh do pieces. Cost mein exactly do parts hain, aur hum dono draw karte hain:

Pipeline depth $D$ tak galat kaam se bhari thi — poori line drain aur refill karni padegi: $\approx D$ ticks.
Memory/cache se pehli sahi instruction fetch karne mein thoda extra $R$ ticks lagte hain (refetch latency, usually $1$ – $3$ ).

PICTURE. Figure branch ko yellow mein front par mark karta hai, $D - 1$ red (galat) instructions ko peeche squash hote dikhata hai, phir thodi $R$ gap ke baad green correct instructions stream hoti hain.

$P$ wahi hai jo aap sirf galat hone par pay karte hain. Agar sahi ho, $0$ pay karte hain. Woh asymmetry yaad rakhein — yahi wajah hai ki juaa pay off kar sakta hai.

Step 5 — Average cost per branch (central result)

KYA. Ab hum "kitni baar galat hain" aur "galat hone ka kya cost hai" combine karenge. Galat guess ki chance ko $m$ kahein (misprediction rate). Yeh $0$ aur $1$ ke beech ka number hai: $m = 0.05$ matlab $5%$ time galat.

KYUN multiply. Hum kaafi branches mein average penalty chahte hain. Average = (bure event ki chance) × (bure event ka cost) + (achhe event ki chance) × ( $0$ ). Achha event kuch contribute nahi karta, toh sirf ek term bachta hai.

PICTURE. Ek tarazu. Galat-guess side par branches ka ek fraction $m$ hai, har ek full weight $P$ lekar. Sahi-guess side par fraction $1 - m$ hai, weightless. Balance point — average — $m \times P$ hai.

Parent ke numbers plug in karein. $m = 0.05$ , $P = 17$ : $\overset{ˉ}{C} = 0.05 \times 17 = 0.85 ticks per branch.$

Compare karein hamesha wait karne se, jisme poora $P \approx 17$ ticks har branch par cost hota hai. Speculation ne $17$ ko $0.85$ mein badal diya — $20 \times$ reduction. Yahi win hai, zero se derive ki gayi.

Step 6 — Break-even line: jab guessing jeetna BAND kar deti hai

KYA. Guessing hamesha achhi nahi hoti. Agar hum guess na karein toh hum ek chhota fixed wait pay karte, jise hum $W$ ticks kehte hain — stall cost, woh ticks jo lost hote hain agar hum simply freeze kar lein jab tak branch resolve ho (kuch ticks, kyunki resolving poore flush se faster hai). Guessing sirf tab jeet hai jab uska average cost $\overset{ˉ}{C}$ us stall cost se chhota ho: $miss rate m penalty P < stall cost if we wait instead W .$

KYUN equal set karein. Tipping point — break-even misprediction rate $m_{*}$ — woh hai jahan dono equal hain. Uske upar, waiting actually sasta hai. $m_{*} P = W ⟹ m_{*} = \frac{W}{P} .$

PICTURE. Poore range $m \in [0, 1]$ par ek graph (ek rate kuch bhi ho sakti hai kabhi-galat-nahi se hamesha-galat tak, toh sab draw karte hain). Blue rising line guessing ka cost $m P$ hai. Green flat line fixed stall cost $W$ hai. Woh $m_{*}$ par cross karte hain. Crossing ke left mein, blue neeche hai — guess. Right mein, green neeche hai — wait.

$W = 2$ , $P = 17$ ke saath: break-even $m_{*} = 2/17 \approx 0.12$ . Toh jab ek branch $\approx 12%$ se zyaada baar mispredicts kare, guessing band kar do.

Step 7 — Degenerate cases

KYA & KYUN. Koi bhi corner andikhaya nahi rehna chahiye. Jo kuch hum ne build kiya uske endpoints dekhein.

$m = 0$ (perfect prediction). $\overset{ˉ}{C} = 0 \times P = 0$ . Speculation free hai — woh ideal jiske paas ek loop pahunchti hai.
$m = 1$ (hamesha galat). $\overset{ˉ}{C} = P$ . Har branch full penalty deta hai; time mein kabhi-speculate-nahi karne jaisa hi, lekin neeche security leaks ke extra risk ke saath. Worst case.
$R \to 0$ (instant refetch, e.g. sahi instruction pehle se ek tiny front-end buffer mein hai). Toh $P = D + R \to D$ : penalty purely pipe drain karne se dominated hai, aur break-even $m_{*} = W / D$ .
$R \to \infty$ (sahi path cache mein nahi, lamba memory fetch). Toh $P \to \infty$ , toh koi bhi nonzero $m$ $\overset{ˉ}{C}$ ko huge bana deta hai aur break-even $m_{*} = W / P \to 0$ — jab refetch catastrophic ho toh guessing almost kabhi worth nahi.
$W \to 0$ (waiting free hai — branch instantly resolve ho jaata hai agar hum sirf stall karein). Toh break-even $m_{*} = W / P \to 0$ : guess karne se bachane ke liye kuch nahi, toh kabhi speculate nahi karna chahiye. (Real CPUs mein $W$ kabhi truly $0$ nahi hota kyunki resolving abhi bhi bubble cost karti hai; yeh limiting boundary hai.)
$D \to$ large (bahut deep pipe). $P = D + R$ badhta hai, toh $\overset{ˉ}{C} = m P$ badhta hai aur break-even $m_{*} = W / P$ ghatta hai. Deeper pipelines better predictors maangti hain — Superscalar architecture aur Instruction-level parallelism (ILP) mein ek real design tension.
Hidden leak. Ek squashed galat guess (Step 4) bhi memory touch kar sakta hai aur cache warm kar sakta hai. Woh trace program ke liye invisible hai lekin bahar se measurable hai — woh darwaza jisse Cache side-channel attacks guzarte hain. Hamara formula time count karta hai, safety nahi; safety cost alag hai.

PICTURE. Chhe mini-panels, ek per case ( $R \to 0$ , $R \to \infty$ , $W \to 0$ limits sameti), plus leak ke liye ek chhota cache icon.

Ek-picture summary

Is page par sab kuch ek chain hai: ek road guess karo → kaam Reorder buffer (ROB) mein rakho → check karo → squash karo aur $P = D + R$ pay karo sirf galat hone par → use $\overset{ˉ}{C} = m P$ se average karo → stall cost $W$ se compare karo. Final figure poori chain ko ek canvas par rakhta hai, break-even line verdict ke roop mein.

Recall Feynman retelling — ise zor se bolein

CPU ek lambi assembly line hai, $D$ boxes deep. Jab use ek if milta hai, jawab ready nahi hota, toh wait karne ke liye freeze karna ek $D$ -tick bubble chhodta hai — line chalti hai lekin kuch finish nahi karti. Use dodge karne ke liye, CPU ek road guess karta hai aur line ko full rakhta hai, unconfirmed results ROB mein park karta hai jahan woh abhi official nahi hain. Agar guess sahi tha, usne kuch nahi khoya. Agar galat, woh poori line squash karta hai — woh ROB slots aur pipeline work drop karta hai — aur refill karta hai, $P = D + R$ ticks ki cost lete hue. Kyunki woh sirf fraction $m$ time galat hota hai, typical cost per branch bas $m \times P$ hai. Ek normal branch ke liye woh bahut chhota hai (jaise $0.85$ ticks), $17$ ke liye freeze karne se kaafi better. Lekin agar ek branch basically coin flip hai ( $m = 0.5$ ), toh woh average $8.5$ ticks tak badh jaata hai — bas kuch ticks $W$ wait karne se bura — toh ek smart CPU break-even point $m_{*} = W / P$ se aage guessing band kar deta hai. Aur ek twist hai jo time-math nahi dekh sakta: ek feka hua guess bhi cache mein ek footprint chhodta hai, aur yahi tarah se Spectre-style attacks secrets padhte hain.

Recall

Misprediction penalty $P$ ke do ingredients kya hain? ::: Pipeline depth $D$ (drain aur refill) aur refetch latency $R$ . Pipeline bubble kya hota hai? ::: Ticks ki ek stretch jisme pipeline chalti hai lekin koi useful instruction finish nahi hoti — ek stall, $\approx D$ ticks per unhandled branch costing. Ek instruction ko squash karne ka kya matlab hai? ::: Use commit se pehle cancel karna — uska ROB slot free karo aur pipeline work discard karo taki woh kabhi official state ko touch na kare. Average wasted ticks per branch? ::: $\overset{ˉ}{C} = m \times P = m (D + R)$ . Sahi guesses average se kyun gayab ho jaate hain? ::: Unka cost $0$ ticks hai, toh $(1 - m)$ term kuch contribute nahi karta. Break-even misprediction rate? ::: $m_{*} = W / P$ , jahan $W$ sirf wait karne ki stall cost hai. Time formula kya CAPTURE nahi karta? ::: Security leak — squashed guesses abhi bhi cache warm karte hain (Spectre / side channels).