Branch prediction (static and dynamic): Question bank

5.3.7 · D5 · Hardware › Advanced Microarchitecture › Branch prediction (static and dynamic)

True or false — justify

Sirf "true/false" kehna yahan bekar hai — judge toh reasoning hai.

Predict-Not-Taken hardware ko koi state nahi chahiye, isliye woh kabhi galat nahi ho sakta.

False. Use koi state nahi chahiye, lekin woh galat zaroor hota hai jab bhi koi branch actually taken hoti hai (jaise loops), toh woh simple hai, accurate nahi.

Ek 2-bit saturating counter hamesha 1-bit predictor se kam-se-kam utna hi accurate hota hai.

False. Ek chhote loop (3 iterations) mein, 2-bit counter pehle pass mein worse score kar sakta hai kyunki uski hysteresis use "taken" trust karne mein slow banati hai; woh sirf kai repetitions ke baad hi jeet-ta hai.

Static prediction program run hone se pehle hoti hai; dynamic prediction chalte waqt hoti hai.

True. Static ek aisi rule use karta hai jo design/compile time par fix hoti hai; dynamic branch ke actual runtime outcomes se ek hardware table update karta hai.

Backwards-Taken-Forward-Not-Taken (BTFNT) isliye kaam karta hai kyunki loops backward jump karti hain aur usually iterate karti hain.

True. Loop ki back-edge ek lower address ki taraf point karti hai (target < PC) aur har iteration mein taken hoti hai, toh "backward ⇒ taken" 90%+ time sahi hoti hai.

Ek correct branch prediction mein zero penalty cycles lagti hain.

True. Sahi guess par speculatively fetch ki gayi instructions sahi wali thi, toh pipeline kabhi stall ya flush nahi hoti — predict karne ka poora point yahi hai.

1-bit predictor ek long loop mein sirf ek baar mispredict karta hai.

False. Woh loop entry-to-exit mein do baar mispredict karta hai: pehli iteration mein (cold start) aur exit par — kyunki ek single not-taken uski bit flip kar deta hai, toh re-entry galat se shuru hoti hai.

Branch penalty badhana (deeper pipeline) prediction accuracy ko aur zyada important bana deta hai.

True.

CPI = 1 + P_{branch} \times P_{mispredict} \times Penalty

mein, bada Penalty har galti ko multiply karta hai, toh wahi mispredict rate zyada cycles cost karti hai.

Ek correlating predictor ek bimodal predictor se better perform kar sakta hai tab bhi jab har branch akela random lagta hai.

True. Ek branch individually unpredictable ho sakti hai lekin recent branches ke saath correlated ho sakti hai; global history register woh pattern capture karta hai jo per-address counter nahi dekh sakta.

Agar ek branch hamesha taken hoti hai, toh 1-bit predictor pehli baar ke baad 100% accuracy achieve kar leta hai.

True. Koi exit event nahi hoti jo bit ko wapas flip kare, toh pehli (cold) miss ke baad bit 1 par rehti hai aur hamesha sahi rehti hai.

Spot the error

Neeche diye gaye har statement mein ek galat claim chupi hui hai. Use dhundho aur theek karo.

"Prediction ke saath, mispredictions free hain kyunki CPU pehle hi guess kar chuka hai."

Galat — miss wala case expensive hota hai: speculatively fetch ki gayi instructions flush ho jaati hain aur pipeline restart hoti hai, poora ~5–10 cycle penalty lagta hai. Sirf correct guesses free hoti hain.

"2-bit counter Taken predict karta hai jab counter 01 (Weakly Not-Taken) hota hai."

Galat — rule yeh hai ki Taken sirf tab predict karo jab counter

\geq 10

ho. 01 abhi bhi Not-Taken half mein hai, toh woh Not-Taken predict karta hai.

"Hum Branch History Table ko full PC se index karte hain, neeche ke 2 bits bhi include karke."

Galat — neeche ke 2 bits drop kar diye jaate hain kyunki instructions 4-byte aligned hain aur woh hamesha 00 honge; hum

PC [n : 2] mod 2^{k}

use karte hain, taaki koi index bits waste na hon.

"Static BTFNT time ke saath seekhta hai aur program chalte waqt improve hota rehta hai."

Galat — static schemes mein koi learning nahi hoti; BTFNT ki ~84% ek fixed ceiling hai jo target-address rule se set hoti hai, run to run nahi badlti.

"Ek loop jo 100 baar chalta hai woh 1-bit predictor ko ~100% accuracy deta hai kyunki woh almost sab taken hai."

Galat — woh oscillate karta hai: exit bit ko Not-Taken mein flip kar deta hai, toh agli entry phir se mispredict karti hai. Woh ~98% tak pahunchta hai, aur woh har re-entry par entry cycle dobara khota hai, unlike 2-bit counter jo "Strongly Taken" hold karta hai.

"Correlating predictors ko sirf current branch ka address chahiye kaam karne ke liye."

Galat — unhein global history register bhi chahiye (recent outcomes of other branches); sirf address use karna use ek plain bimodal predictor bana deta hai.

"Predict-Taken forward branches jaise error checks ke liye best hai."

Galat — forward branches (error checks, early returns) usually not taken hoti hain, toh Predict-Not-Taken unhe suit karta hai; Predict-Taken backward loop branches ke liye sahi hai.

Why questions

Kyun 2-bit counter sirf last outcome track karne ki jagah hysteresis add karta hai?

Taaki ek alag anomalous outcome (jaise loop ka ek exit) prediction flip na kar sake — switch karne ke liye do consecutive misses lagti hain, jo predictor ko dominant behaviour par sahi rehne deta hai.

Kyun 1-bit predictor ek 3-iteration loop par sirf 50% score karta hai?

Loop itni chhoti hai ki apni do guaranteed misses (cold start + exit) ko thodi iterations mein amortise nahi kar sakti — 4 branch events mein se 2 galat exactly 50% hai.

Kyun hum branch resolve hone ka wait karne ki jagah speculatively fetch karte hain?

Kyunki branch outcome ~10–20 cycles tak pata nahi hoti, aur stalling pipeline ko starve kar deta hai — ek educated guess use full rakhta hai aur sirf kabhi-kabhi kaam barbaad karta hai, jo average par kaafi faster hai. Yeh Speculative Execution aur Instruction-Level Parallelism (ILP) ko underpin karta hai.

Kyun deeper pipelining (zyada stages) good branch prediction ko aur urgent bana deta hai?

Zyada stages matlab miss par flush karne ke liye zyada in-flight instructions, toh misprediction penalty badh jaati hai — buri guess ki cost pipeline depth ke saath scale karti hai.

Kyun ek compiler static prediction mein help kar sakta hai?

Compiler code arrange kar sakta hai aur branch hints (likely/unlikely) emit kar sakta hai loop structure aur profiling ke knowledge ka use karke, jo fixed hardware rule ko feed karta hai. Dekho Compiler Optimizations.

Kyun ek correlating predictor nested if statements mein help karta hai?

Inner branch sirf tab execute ho sakti hai (ya ek certain tarike se resolve ho sakti hai) kyunki outer branch ek specific way se gayi; global history "outer was taken" encode karta hai, jo inner prediction ko us par condition karne deta hai.

Kyun branch misprediction indirectly cache performance ko hurt karta hai?

Galat guess galat path se instructions aur data fetch karta hai, cache ko useless lines se pollute karta hai jo program kabhi use nahi karta aur possibly useful ones ko evict kar deta hai — yeh Cache Performance se connect hota hai.

Kyun Superscalar Processors scalar ones se bhi zyada prediction ki parwah karte hain?

Woh har cycle mein kai instructions issue karte hain, toh ek flush poori pipeline width mein kai instructions ka kaam ek baar mein barbaad karta hai — penalty issue width se multiply ho jaati hai.

Edge cases

Boundaries woh jagah hain jahan predictors apna asli character dikhate hain.

Kisi bhi branch ko pehli baar dekhne par kya hota hai (cold start)?

BHT entry apni initial state (00 / Not-Taken) mein hoti hai, toh pehli prediction essentially ek blind guess hai aur aksar galat hoti hai, chahe predictor kitna bhi accha kyun na ho.

2-bit counter boundary state 10 (Weakly Taken) par kya predict karta hai?

Taken — rule hai

\geq 10 \Rightarrow

Taken, toh 10 Taken predict karta hai lekin ek single not-taken use 01 par le jaata hai aur prediction flip kar deta hai.

Kya hota hai jab do alag branches same BHT index par map ho jaati hain (aliasing)?

Woh ek counter share karti hain aur interfere karti hain ("destructive aliasing"), toh ek branch ke outcomes dusri ki prediction corrupt kar dete hain — accuracy drop ho jaati hai chahe har branch akele predictable kyun na ho.

Kisi bhi predictor ki accuracy truly random branch (50/50, koi pattern nahi) par kya hoti hai?

Lagbhag 50% — koi bhi history ya rule fair coin ko beat nahi kar sakti, toh yeh theoretical worst case hai jahan prediction sirf cost (flushes) add karta hai bina koi benefit ke.

2-bit predictor alternating T, NT, T, NT, ... branch par kaise behave karta hai?

Bura — woh kabhi saturate nahi karta, weak states ke around hovering karta rehta hai aur baar baar mispredict karta hai, kyunki pattern hysteresis ke settle hone se pehle flip ho jaata hai. Yahi woh case hai jiske liye correlating predictors banaye gaye hain.

BTFNT ki accuracy limit chahe code kitna bhi "nice" kyun na ho kya hai?

Woh target-address rule se fix hai (~84% typical), toh perfectly loop-heavy code bhi ise aur upar nahi push kar sakta — kyunki woh per-branch behaviour seekh nahi sakta.

Loop exit par, kyun even ek strongly taken 2-bit counter ek baar mispredict karta hai?

Exit genuinely not-taken hoti hai jabki counter Strongly Taken kehta hai, toh woh ek branch prediction ke against resolve hoti hai — lekin counter sirf 10 tak drop hota hai, toh re-entry phir bhi sahi hoti hai. Woh ek unavoidable exit miss "one per loop" cost hai.