Speculative execution: Exercises — Hinglish deep dive

5.3.11 · D4 · Hardware › Advanced Microarchitecture › Speculative execution

Yeh page ek self-test ladder hai. Har rung pehle se mushkil questions poochhti hai Speculative execution ke baare mein — "kya tum part ka naam jaante ho?" se lekar "kya tum mitigation design kar sakte ho?" tak. Solution cover karo, khud try karo, phir reveal karo.

Shuru karne se pehle, ek one-screen refresher un vocabulary words ka jo hum baar baar use karte rahenge. Agar koi word unfamiliar lage, toh yahi exercises usse drill karengi.

Hum sab kuch cycles mein measure karte hain (CPU clock ki ek tick) aur CPI mein = cycles per instruction. Jo numbers hum compute karte hain woh ===VERIFY=== mein check hote hain.

Building the penalty formula (read this first)

Neeche har exercise ek galat guess ko cycles mein price karta hai, isliye pehle hume samajhna hoga ki yeh price aata kahan se hai. Pipeline ko $N$ stages wale conveyor belt ki tarah socho; ek branch instruction belt ke door wale end ke paas ride karti hai, lekin woh instructions jo isko "gate" karti hain woh iske bilkul peeche fetch ho chuki hain aur belt pe stream kar rahi hain.

Formula Misprediction penalty — derived

$Penalty = PipelineDepth + RefetchLatency$

Exactly yeh do terms kyun? Wrong-path recovery ko step by step walk karo (neeche figure dekho):

Branch mispredicts. Belt par iske peeche $N - 1$ wrong-path instructions baithti hain (har remaining stage mein ek), aur branch khud ek aur slot occupy karti hai jab uski condition resolve ho rahi hai. Yeh $(N - 1) + 1 = N$ slots of work wrong path mein sunk hai — isliye depth term exactly $N$ hai, $N - 1$ nahi: branch ka apna resolve slot woh "+1" deta hai jo $N - 1$ ko ek poore $N = 15$ tak round karta hai.
Woh galat instructions invalidate (squash) ho jaati hain — saste flag flips, usi recovery mein fold ho jaate hain, isliye koi alag cycles nahi lagte.
Ab belt khaali hai aur hume ise sahi address se refill karna hai. Kuch useful tab tak commit nahi hota jab tak pehli sahi instruction travel in na kar le — yeh startup cost hai refetch latency, doosra term ( $2$ ).

Sunk wrong-path work ( $N = 15$ ) ko refill startup ( $2$ ) mein add karne par $Penalty = 15 + 2 = 17$ cycles milte hain.

Figure s01 — 15 rounded coral boxes ka ek conveyor belt dikhata hai wrong-path work ko har stage mein fill karte hue (depth term, 15 cycles); ek red arrow is block ko "PipelineDepth = 15" label karta hai. Daayein taraf do mint boxes, ek mint arrow se "RefetchLatency = 2 cycles" tag kiye hue, sahi kaam shuru hone se pehle refill startup dikhate hain. Neeche bold caption padhta hai "Penalty = 15 + 2 = 17 cycles". Ise left-to-right padho: pehle wrong work, phir chhota refill, penalty tak joda.

Definition Stall cost

$s$ — do alag events jo dono 2 cost karte hain Agar guess karne ke bajaye hum simply wait karein, pipeline tab tak pause hoti hai jab tak branch ki condition compute na ho jaaye aur sahi address na pata ho. Critically, koi wrong-path instructions kabhi fetch nahi hote, isliye squash karne ko kuch nahi aur garbage se bhara hua belt nahi — bada depth term $N$ kabhi appear nahi karta. Tum sirf short redirect pay karte ho: branch resolve hoti hai, fetcher ko (already-known-correct) agle address par point kiya jaata hai, aur pehli sahi instruction fetch hoti hai. Is machine par yeh redirect wait $s = 2$ cycles hai.

Yeh "resolve-and-redirect" wait numerically refetch latency ke barabar (bhi 2) kyun aata hai? Yeh conceptually alag events hain: refetch latency hai "galat guess ke baad corrected target ke liye instruction cache mein jao aur fetch karo", jabki stall redirect hai "fetcher ko us sahi target par point karo jiske baare mein hum kabhi galat nahi the aur use fetch karo". Lekin dono ka ant usi ek physical act mein hota hai — ek single instruction-cache access jo hit karti hai — aur is machine par ek I-cache hit plus uska result belt ke front ko feed karna $2$ cycles leta hai. Toh yeh match karte hain kyunki dono mein dominant cost ek hi I-cache-hit fetch hai, coincidence of definition se nahi. Agar I-cache miss karti, dono ek saath badhte.

Dono prices ko apne dimaag mein alag rakho chahe numbers tie hon: $s$ har branch par paid hoti hai agar tum stall karo (sasta redirect, koi wrong work nahi); $P$ sirf galat guesses par paid hoti hai agar tum speculate karo (poora belt wrong work se bhara, $N + 2$ ).

Ab hamare paas woh do quantities hain jo har exercise use karta hai: $P = Penalty = 17$ aur $s = stall cost = 2$ , $N = 15$ wali machine par.

Level 1 — Recognition

(Kya tum pieces ko naam de aur classify kar sakte ho?)

Exercise 1.1

Har item ko architectural ya microarchitectural state mein sort karo: (a) general-purpose register rax, (b) ROB, (c) L1 data cache, (d) main memory, (e) branch-predictor counter table.

Recall Solution

Test yeh hai: kya ek normal program ise directly read kar sakta hai?

Architectural (program dekh sakta hai): (a) rax, (d) main memory.
Microarchitectural (hidden helper): (b) ROB, (c) L1 cache, (e) predictor table.

Cache wala sneaky wala hai: ek program cache ko directly read nahi kar sakta, lekin woh memory accesses ko time kar sakta hai aur infer kar sakta hai ki kya cached hai. Woh timing leak har Spectre-style side-channel attack ka seed hai.

Exercise 1.2

Speculation ke har stage ko uske purpose se match karo:

Predict — 2. Checkpoint — 3. Execute — 4. Verify — 5. Commit/Squash. Purposes: (A) guessed path se instructions run karo; (B) branch outcome guess karo; (C) architectural state ko real banao ya undo karo; (D) state save karo taaki hum roll back kar sakein; (E) real branch result ko guess se compare karo.

Recall Solution

1→B, 2→D, 3→A, 4→E, 5→C. Order matters: tum execute se pehle checkpoint karte ho, kyunki tum us state par roll back nahi kar sakte jo tune kabhi save hi nahi ki.

Level 2 — Application

(Numbers ko machinery mein plug karo.)

Levels 2–3 ke liye upar ki derivation ki baseline machine use karo: pipeline depth $N = 15$ , penalty $P = 17$ cycles, stall cost $s = 2$ cycles.

Exercise 2.1

Ek program $1000$ branches run karta hai. Predictor $95%$ accurate hai. Mispredictions par kitne cycles waste hote hain?

Recall Solution

Mispredicted branches: $1000 \times (1 - 0.95) = 50$ . Har ek $17$ cycles cost karta hai → $50 \times 17 = 850$ cycles. Answer: $850$ cycles waste.

Exercise 2.2

Parent note ka loop:

for (int i = 0; i < 100; i++) sum += array[i];

i < 100 branch $99$ baar taken hoti hai aur ek baar not-taken (exit). Do alag design strategies aur unke apne stall costs consider karo:

(a) "in-order, drain-on-branch" — ek purane zamaane ka in-order core jo rename ya reorder nahi kar sakta, isliye har branch par isse re-steer karne se pehle poori pipeline drain karni padti hai. $N = 15$ -stage belt drain karna per branch full pipeline depth $= 15$ cycles cost karta hai. (Yeh hamari modern $s = 2$ se zyada strong stall hai: yeh machine useful work ke saath resolve bhi overlap nahi kar sakti.)
(b) speculation modern machine par — sirf single misprediction (loop exit) par $P = 17$ -cycle penalty pay karo.

(a) aur (b) ke liye total stall cycles compute karo, phir ratio (a)/(b) do.

Recall Solution

Yahan 15 kyun lekin baaki jagah $s = 2$ ? $s = 2$ redirect ek modern out-of-order front end assume karta hai jo sirf ek quick re-steer chahta hai. (a) machine deliberately ek alag, purani design hai jo har branch par sare 15 stages drain karti hai — uske paas koi sasta redirect nahi, isliye uska per-branch stall poori depth $N = 15$ ke barabar hai. Hum worst realistic non-speculative machine ko speculation ke against compare karte hain poora payoff dikhane ke liye. (a) $100 \times 15 = 1500$ stall cycles. (b) $1 \times 17 = 17$ stall cycles. Ratio $= 1500/17 \approx 88.2$ . Speculation yahan ~ $88 \times$ stall cost remove karta hai kyunki loop almost perfectly predictable hai.

Exercise 2.3

Random data par ek branch (rand() % 2 == 0) $50%$ time correctly predict hoti hai. Is branch ke execution par average penalty kya hai, aur yeh simply $s = 2$ cycles (upar define ki) stall karne se kaise compare hoti hai jab tak branch resolve na ho?

Recall Solution

Expected penalty $= 0.5 \times 17 = 8.5$ cycles per branch. Plain stall sirf $s = 2$ cycles cost karti hai. Yahan speculation $8.5 - 2 = 6.5$ cycles average par badtar hai. 50/50 branch ke liye, na speculate karna jeetta hai.

Level 3 — Analysis

(Trade-offs aur rates ke baare mein reason karo.)

Exercise 3.1

Ek branch-heavy program har $6$ instructions mein ek branch execute karta hai. Predictor accuracy $95%$ hai, penalty $17$ cycles. Mispredictions se add hone wala extra CPI (cycles per instruction) compute karo.

Recall Solution

Instructions ka fraction jo branches hain: $\frac{1}{6}$ . Un mein se $5%$ mispredict karte hain. Extra cycles per instruction: $branch freq \frac{1}{6} \times miss rate 0.05 \times penalty 17 = 0.1417 CPI .$ Toh roughly $0.14$ extra cycles per instruction — real, lekin har branch par stall karne se bahut sasta.

Exercise 3.2

Usi workload ke liye do predictor designs offer ki gayi hain (har $6$ instructions mein branch):

Design A: accuracy $92%$ , pipeline depth $12$ → penalty $12 + 2 = 14$ .
Design B: accuracy $97%$ , pipeline depth $20$ → penalty $20 + 2 = 22$ . Kaun sa per instruction kam misprediction overhead add karta hai?

Recall Solution

Extra CPI $= \frac{1}{6} \times (1 - acc) \times penalty$ .

A: $\frac{1}{6} \times 0.08 \times 14 = 0.18 \overline{6}$ CPI.
B: $\frac{1}{6} \times 0.03 \times 22 = 0.11$ CPI. Design B jeetta hai ( $0.11 < 0.187$ ). Deeper pipeline (bada penalty) bahut kam miss rate se more than offset hai. Deep pipelines tab hi pay off karte hain jab predictor itna acha ho.

Exercise 3.3

Parent note speculation ko ROB ke through out-of-order execution se link karta hai. 2–3 sentences mein explain karo kyun ROB woh cheez hai jo rollback ko possible banata hai, aur kya break hota agar speculative results seedha rax mein likhe jaate.

Recall Solution

ROB speculative results ko program order mein rakhta hai lekin abhi tak commit nahi kiye — ek staging area. Misprediction par, CPU galat ROB entries discard kar deta hai; architectural registers kabhi touch nahi hue, isliye undo karne ko kuch nahi. Agar results seedha rax mein likhe jaate, ek galat guess real value ko garbage se overwrite kar deta aur restore karne ke liye koi clean copy nahi hoti — speculation program corrupt kar deta. ROB woh checkpoint hai jo computed ko committed se alag karta hai.

Level 4 — Synthesis

(Ideas ko ek security/design argument mein combine karo.)

Exercise 4.1 — The Spectre gadget

Ek malicious program ek secret byte padhna chahta hai jise padhne ki permission nahi hai. Woh neeche wala sequence use karta hai. Har step ko architectural ya microarchitectural label karo, aur explain karo kyun secret tab bhi leak hota hai jab step 3 squash ho jaata hai.

Branch predictor ko "in-bounds" expect karne ki training do.
Ek out-of-bounds index pass karo taaki guard branch forbidden path mein mispredict kare.
Speculatively secret load karo, phir probe[secret * 256] load karo.
Branch resolve hoti hai → step 3 ka sab kuch squash ho jaata hai.
Attacker probe[0], probe[256], ... ke reads time karta hai dekhne ke liye kaun fast hai.

Recall Solution

Steps 1, 3, 5 microarchitectural state par operate karte hain (predictor + cache). Step 4 ka squash architectural state restore karta hai.
Leak survive karta hai kyunki squash sirf architectural effects undo karta hai (registers, memory). Woh cache line jo step 3 ne speculation ke dauran pull ki woh jaanbujh kar peeche chhodi jaati hai (yeh normal caching hai). probe[secret*256] cached rehta hai.
Step 5 mein attacker sare $256$ possible probe slots padhta hai; woh ek fast (cached) slot secret reveal karta hai. Neeche timing sketch dekho.

Figure s02 — aath probe slots (indices 0–7) ka ek bar chart jisme vertical axis par measured access time cycles mein hai. Saat bars lavender mein 120 cycles ke paas tall khade hain (evicted, slow); index 3 par ek bar mint mein approximately 42 cycles tak girta hai (still cached, fast). Ek dashed coral "cache-hit threshold" line 70 cycles par unhe separate karti hai, aur ek coral arrow short bar par point karta hai padhte hue "fast = cached ⇒ secret is 3". Ek single fast slot ka index leaked secret value hai.

Yahi cache side channels ka poora point hai: architectural rollback ek security boundary nahi hai kyunki woh cache undo karna bhool jaata hai.

Exercise 4.2 — Kaun sa fix, aur kyun

Har mitigation ko us exact step se match karo jise woh disrupt karta hai: (A) lfence speculation barrier — (B) context switch par predictor flush karna — (C) indirect branches ke liye retpoline. Steps: (i) ek privilege boundary ke across predictor train karna; (ii) speculatively secret-dependent load issue karna; (iii) ek indirect/call *reg branch ke through speculate karna.

Recall Solution

A → (ii): lfence execution ko speculatively iske past proceed karne se rokta hai, isliye secret-dependent load speculation ke under kabhi issue nahi hota.
B → (i): contexts ke beech predictor clear karna attacker ki training ko victim mein carry hone se rokta hai.
C → (iii): ek retpoline ek indirect jump ko ek controlled ret-based trampoline se replace karta hai jise predictor attacker target par steer nahi kar sakta. Har fix ek alag stage attack karta hai — isliye real CPUs kai ek saath deploy karte hain.

Level 5 — Mastery

(Ek poora decision design aur defend karo.)

Exercise 5.1 — Speculate-or-stall decision rule

Woh general condition derive karo jiske under speculation stall karne ke muqable worth it hai. Hamare do quantities reuse karte hue: $a$ = predictor accuracy, $P$ = misprediction penalty (cycles, $= 17$ yahan), $s$ = stall cost agar hum speculate nahi karte (cycles, $= 2$ yahan). Phir break-even accuracy $a^{*}$ nikalo, aur batao exactly us accuracy par kya hota hai.

Recall Solution

Speculate karne ki expected cost $= (1 - a) P$ (tum sirf tab penalty pay karte ho jab galat ho; sahi guesses cost $0$ ). Stall karne ki cost $= s$ (hamesha pay karna padta hai). Speculation tab jeetti hai jab $(1 - a) P < s ⟹ a > 1 - \frac{s}{P} .$ Break-even: $a^{*} = 1 - \frac{s}{P} = 1 - \frac{2}{17} \approx 0.882$ . Tie case $a = a^{*}$ : yahan $(1 - a) P = s$ exactly — speculate karna aur stall karna average par same cost karte hain, isliye koi bhi behtar nahi aur choice wash hai (real designs tab security exposure se bachne ke liye stall prefer karti hain). Strictly $a^{*}$ se upar, speculate karo; strictly neeche, stall karo.

Figure s03 — ek line plot jisme horizontal axis par predictor accuracy $a$ (0 se 1) aur vertical axis par expected cost in cycles per branch hai. Ek flat coral line constant stall cost $s = 2$ par baithti hai; ek sloped lavender line $(1 - a) P$ trace karti hai, $a = 0$ par $17$ se girti hui $a = 1$ par $0$ tak. Dono lines mint-dashed break-even $a^{*} \approx 0.882$ par milti hain, ek slate dot se mark ki hui. Crossing ke daayein mint-shaded region "speculate wins" label hai; baayein region "stalling wins" label hai.

Exercise 5.2 — Ek bura branch redesign karo

Tum ek hot branch profile karte ho: accuracy $55%$ , $1, 000, 000$ baar execute, $P = 17$ , aur stall karna $s = 2$ cost karta. (a) Speculation stall karne ke muqable kitne cycles waste karta hai? (b) Do software rewrites naam batao (parent note se) aur kaho kaun sa branch entirely remove karta hai.

Recall Solution

(a) Speculate karte hue: $(1 - 0.55) \times 17 = 7.65$ cycles/branch → $7.65 \times 1 0^{6} = 7, 650, 000$ cycles. Stall karte hue: $2 \times 1 0^{6} = 2, 000, 000$ cycles. Speculation $7.65 M - 2 M = 5, 650, 000$ extra cycles waste karta hai. (5.1 ke saath consistent: $0.55 < 0.882$ , isliye speculation harti hai.) (b) Data sort karo taaki branch biased/predictable ho, ya branchless code likho (cmov, bitwise select). Branchless rewrite branch entirely remove karta hai, isliye mispredict karne ko kuch bachta hi nahi — yahi sabse pakka fix hai.

Exercise 5.3 — Sab kuch jodo

Ek paragraph mein, Instruction-level parallelism (ILP), superscalar width, aur speculation ko connect karo: ek wider superscalar machine ko better speculation ki zaroorat kyun hoti hai?

Recall Solution

Ek superscalar core ILP exploit karne ke liye har cycle mein kai instructions issue karta hai — lekin branches har kuch instructions mein hoti hain, isliye ek wide machine almost har cycle mein ek branch hit karta hai. Accurate speculation ke bina woh constantly stall karta, aur uske extra issue slots idle baithte (wahi hazard jisko chhupaane ke liye speculation exist karta hai). Wider issue har stall ki cost badhata hai (zyada idle slots) aur branch encounter rate badhata hai, isliye predictor accuracy ke har 1% ka payoff width ke saath badhta hai. Wide + deep machines aur strong predictors isliye inseparable hain.