Speculative execution — Hinglish notes

5.3.11 · Hardware › Advanced Microarchitecture

Speculative Execution Kya Hai?

Speculative execution ek CPU optimization hai jisme instructions execute hoti hain pehle hi, jab processor ko abhi pata nahi ki unki zaroorat hai bhi ya nahi. CPU predictions karta hai:

Conditional jump kaunsa branch lega
Memory load kya value return karega (value prediction)
Branch liya bhi jaayega ya nahi

YEH KYU exist karta hai: Modern CPUs ke deep pipelines hote hain (15-20+ stages). Branch resolve hone ka wait karna ek pipeline bubble create karta hai—wasted cycles jisme execution units bekar baith te hain. Speculation karke, CPU saari units ko busy rakhta hai.

YEH KAISE kaam karta hai:

Branch predictor (saturating counters, perceptron predictors, etc.) use karke branch outcome Predict karo
Predicted path ki instructions Fetch aur execute karo
Speculation se pehle architectural state ka Checkpoint rakho
Branch resolve hone par prediction Verify karo
Sahi ho toh Commit karo, galat ho toh Rollback (squash) karo

Mechanics: Speculation Kaise Flow Karta Hai

1. Branch Prediction

Branch predictor (ek hardware table jo PC se indexed hoti hai) outcome guess karta hai. Modern predictors use karte hain:

2-bit saturating counters: History track karte hain (strongly taken, weakly taken, weakly not-taken, strongly not-taken)
Global history: Last N branches ka pattern jo PC ke saath XOR hota hai
Tournament predictors: Multiple algorithms compete karte hain, best wala select hota hai

2. Speculative Fetch & Execute

Predicted path ki instructions pipeline mein enter karti hain. Yeh:

Register Alias Table (RAT) se registers read karte hain (renaming false dependencies avoid karti hai)
Reservation stations mein execute hoti hain (out-of-order)
Results Reorder Buffer (ROB) mein store karte hain—ek circular queue jo program order mein ordered hai

Key point: Results calculate ho jaate hain lekin abhi architectural registers mein write NAHI hote.

3. Branch Resolution

Jab branch instruction finish hoti hai (condition evaluate ho jaati hai), CPU check karta hai: $Prediction Correct? = (Predicted Target == Actual Target)$

4. Commit ya Squash

Sahi prediction: ROB mein instructions architectural state mein commit ho jaati hain (registers, memory likhte hain). ROB entries free ho jaati hain.
Misprediction: Branch ke baad ki saari instructions squash ho jaati hain—ROB entries discard ho jaati hain, pipeline flush ho jaati hai, fetch correct target se restart hoti hai.

Worked Examples

Worked example Example 1: Simple Conditional Branch

if (x > 10) {
    y = x * 2;  // Path A
} else {
    y = x + 5;  // Path B
}
z = y + 3;

Prediction: CPU guess karta hai ki x > 10 TRUE hai (history ke basis par).

Step-by-step:

x > 10 comparison Fetch karo. Comparison calculate hote waqt Path A Speculate karo.
y = x * 2 speculatively Execute karo—result ROB mein jaata hai, architectural register y mein nahi.
Comparison resolve: Agar x = 15, prediction sahi!
- Yeh step kyun? Hum verify karte hain ki speculation program semantics violate nahi karta.
y = 30 architectural state mein Commit karo.
z = y + 3 = 33 Execute karo (jaldi start ho sakta hai kyunki y ROB mein hai). Agar galat (x = 8):
Comparison FALSE resolve hoti hai.
ROB se y = x * 2 Squash karo.
Branch ke baad ke pipeline stages Flush karo.
Path B Re-fetch karo, y = x + 5 = 13 execute karo.
Yeh step kyun? Architectural state sahi path reflect karna chahiye—speculation program ko invisible hai.

Worked example Example 2: Loop with Predictable Pattern

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

Branch: Har iteration ke end mein i < 100.

Prediction: 2-bit counter "weakly taken" se shuru hota hai. 2 iterations ke baad "strongly taken" ho jaata hai.

Iterations 0-98: Taken predict karo (sahi), koi penalty nahi.
Iteration 99: Taken predict karo, par ab i = 100 hai—misprediction!
Yeh step kyun? Predictors patterns par kaam karte hain. Yeh loop 99% predictable hai; exit hi akela miss hai.

Performance:

Speculation ke bina: 15 cycles stall × 100 iterations = 1500 cycles waste.
Speculation ke saath: 1 misprediction × 17 cycles = 17 cycles waste.
Speedup: $\frac{1500}{17} \approx 88 \times$ kam stall cycles.

Worked example Example 3: Unpredictable Branch (Random Data)

if (rand() % 2 == 0) {
    process_even();
} else {
    process_odd();
}

Prediction: Random 50/50 outcomes—predictor accuracy $\approx 50%$ .

Result: Aadhe time misprediction penalty pay karo.

Cost per branch: $0.5 \times 17 = 8.5$ cycles average.
Yeh step kyun? Yahan speculation nuksan karta hai! Stall karna better hai (maano, 2 cycles jab tak branch resolve ho) instead of average 8.5 cycles pay karne se.

Real CPUs: Kuch ke paas "confidence estimators" hote hain—agar predictor uncertain hai, toh woh speculate karne ki bajaye stall karte hain.

Common Mistakes

Common mistake Mistake 3: "Speculative execution sirf performance affect karta hai, correctness nahi"

Yeh sahi kyun lagta hai: CPU promise karta hai architectural state sahi maintain karne ka—speculation invisible hai.

Steel-man: Program ke perspective se, yeh 2018 se pehle sach tha.

Haqeeqat: Spectre attacks (2018) ne dikhaya ki speculative execution microarchitectural state (cache timings) mein traces chhodta hai. Ek malicious program:

Branch predictor ko mispredict karne ke liye train kar sakta hai.
Secret data (jaise kernel memory) speculatively access kar sakta hai.
Access squash ho jaata hai, par woh data cache mein pull kar deta hai.
Cache timing measure karke secret infer kar sakta hai.

Fix: Modern CPUs ke paas mitigations hain:

Speculation barriers (x86 par lfence) speculative memory access roke te hain.
Context switches par predictors flush karna.
Indirect branches ki jagah Retpolines lagate hain.

Security-sensitive code ke liye yeh ek correctness issue hai.

Doosre Concepts Se Connections

Branch prediction algorithms: Speculation ka "brain"—predictions kaise banti hain
Out-of-order execution: Speculation OO ko enable karta hai execute karne ke liye instructions de kar
Reorder buffer (ROB): Woh data structure jo speculation ko safe banata hai (results ka staging area)
Pipeline hazards: Speculation control hazards eliminate karta hai (branch stalls)
Cache side-channel attacks: Spectre/Meltdown speculative memory access exploit karte hain
Instruction-level parallelism (ILP): Speculation branches ke paar dekh ke zyada ILP expose karta hai
Superscalar architecture: Multiple execution units ko kaam chahiye—speculation unhe busy rakhta hai

Recall Ek 12-Saal Ke Bachhe Ko Explain Karo

Tum ek video game khel rahe ho jisme tum doors se guzarte ho. Har door ke peeche ya toh treasure room hai ya trap. Ek sign hota hai jo usually batata hai kaunsa hai, par sign padhne mein 5 second lagte hain.

Speculation ke bina: Tum ruko, sign padho, phir andar jao. Slow!

Speculation ke saath: Pichle 10 doors ke basis par guess karo (agar 9 treasure the, toh treasure guess karo). Sign load hone se pehle hi chalna shuru karo. Agar sahi nikla, 5 second bachh gaye! Agar galat, jaldi bahar aao (2 second lagte hain palat ne mein).

CPU yahi code ke saath karta hai. Wo guess karta hai tumhara if statement kaunsa raasta lega aur kaam jaldi shuru kar deta hai. Agar sahi guess kiya (95% time!), program faster chalta hai. Agar galat, turant galti undo karta hai aur doosra path try karta hai. Yeh bet pay off hota hai kyunki sahi hona galat hone se kahin zyada common hai.

Flashcards

#flashcards/hardware

Speculative execution kya hai? :: Ek CPU optimization jisme instructions execute hoti hain pehle hi, jab processor ko abhi pata nahi ki unki zaroorat hai, branch outcomes ke baare mein predictions ke basis par. Results reorder buffer mein jaate hain aur architectural state mein sirf tab commit hote hain jab prediction sahi ho.

Speculative execution kyun exist karta hai?

Pipeline bubbles se bachne ke liye jo branch stalls se aati hain. Modern CPUs ke deep pipelines hote hain (15-20 stages); har branch resolve hone ka wait karna execution units ko idle rakhega. Speculation unhe busy rakhta hai.

Architectural state aur microarchitectural state mein kya fark hai?

Architectural state (registers, memory, flags) software ko visible hai aur correctly maintain karni hi padti hai. Microarchitectural state (ROB, caches, branch predictors) internal implementation detail hai. Speculation microarchitectural state turant modify karta hai lekin architectural state mein sirf verification ke baad commit karta hai.

Jab branch mispredict hoti hai toh kya hota hai?

Galat path se fetch ki gayi saari instructions squash ho jaati hain (reorder buffer se discard), pipeline flush ho jaati hai, aur fetching correct target se restart hoti hai. Iska cost approximately pipeline_depth + refetch_latency cycles hoti hai.

15-stage pipeline mein 2-cycle refetch ke liye misprediction penalty calculate karo :: 15 (galat instructions flush karo) + 2 (correct path fetch karo) = 17 cycles

Unpredictable branches speculation ko performance ke liye kyun hurt kar sakte hain?

Agar branch 50/50 random hai, predictor ~50% time galat hoga. Misprediction penalty pay karna (jaise 17 cycles) aadhe time par average 8.5 cycles deta hai—yeh sirf branch resolve hone ka wait karne se worse hai (~2 cycles).

Reorder Buffer (ROB) kya hai aur speculation ke liye kyun chahiye?

Ek circular queue jo speculative instruction results program order mein hold karta hai. Isse CPU instructions out-of-order execute kar sakta hai lekin in-order commit kar sakta hai, jo correct architectural state ensure karta hai chahe speculations galat hon. Results ROB mein tab tak rehte hain jab tak instruction verify nahi ho jaati ki wo correct path par hai.

Spectre attacks speculative execution ko kaise exploit karte hain?

Woh branch predictor ko mispredict karne ke liye train karte hain, jisse CPU speculatively secret data access karta hai (jaise kernel memory). Halanki access squash ho jaata hai, cache timing mein traces rah jaate hain jinhein secret value infer karne ke liye measure kiya ja sakta hai.

Speculation barrier kya hai aur kab use hota hai?

Ek instruction (jaise x86 par lfence) jo us point ke aage speculative execution rok deti hai. Security-sensitive code mein use hoti hai ensure karne ke liye ki memory accesses speculatively execute nahi honge, Spectre-style attacks mitigate karne ke liye.

Speculation ek "bet" kyun hai jo usually pay off karti hai?

Modern branch predictors 95%+ accuracy achieve karte hain. 95% time sahi hona matlab hai 95% branches par pipeline_depth cycles bachana aur sirf 5% par misprediction_penalty pay karna—predictable code patterns ke liye net gain bahut bada hota hai.