Visual walkthrough — Branch prediction (static and dynamic)

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

Step 1 — "Pipeline" actually hota kya hai (instructions ke liye ek car wash)

KYA HAI. Ek processor ek instruction ko start-to-finish khatam karne ke baad hi agli instruction ko nahi pakadta. Woh kaam ko stages mein tod deta hai, bilkul car wash ki tarah: soap → rinse → wax → dry. Jab car #1 wax ho rahi hai, car #2 pehle se rinse ho rahi hai, aur car #3 soap ho rahi hai. Koi bhi apni baari ka wait nahi karta — sab overlap karte hain.

KYUN. Agar har stage ek clock ki tick mein hoti hai (us tick ko hum cycle kehte hain), to overlap ka matlab hai ki ek finished instruction har cycle mein bahar aati hai, har 5 cycles mein nahin. Yahi pipeline ka poora point hai: throughput.

PICTURE. Figure mein, paanch instructions (rows) paanch stages (columns) mein diagonally chalti hain. Ek column ko upar se neeche padho to pata chalega "abhi kaun kahan hai."

Step 2 — Branch car wash ko kahan se todta hai

KYA HAI. Ek branch ek aisi instruction hai jo poochhti hai "kya mujhe kahin aur jump karna chahiye, ya seedha chalte rehna chahiye?" — if ka machine version. Catch yeh hai: jawab sirf Execute stage mein pata chalta hai, lekin Fetch ko jawab abhi chahiye taaki woh jaane ki agli instruction kaun si pakdni hai.

KYUN. Fetch cycle 1 mein hoti hai. Execute cycle 3 mein hoti hai. Yeh ek cycles ka gap hai jahan Fetch andheri hai: branch ne abhi reveal bhi nahi kiya ki woh kaunsi taraf gayi, aur tab tak 2 instructions pehle se pakad li gayi hain. Figure mein amber gap dekho — woh instructions bharose pe fetch ki gayi hain.

PICTURE. Branch row 1 mein hai. Uska result uske E box (cycle 3) tak pata nahi chalta. Lekin rows 2 aur 3 pehle se fetch ho chuki hain (cyan) us se pehle. Agar branch actually kahin aur jump karti hai, to woh cyan boxes galat instructions thi.

Step 3 — React karne ke do tarike, aur prediction kyun jeetती hai

KYA HAI. Jab Fetch andheri hai to uske paas bilkul do options hain:

1. Stall — Fetch ko freeze karo jab tak branch resolve na ho jaaye. Safe hai, kabhi galat nahi, lekin guaranteed hai ki woh gap cycles har ek branch par waste honge.
2. Predict — ek direction guess karo, usi taraf fetch karo, aur pipeline full rakho. Sahi hone par free; galat hone par sirf flush ka kharcha aata hai.

KYUN. Guessing ek bet hai. Maan lo galat guess karne ki probability $P_{\text{mispredict}}$ hai. Phir expected wasted cycles per branch ek weighted average hai:

$\underset{\text{sahi ka fraction}}{\underbrace{(1-P_{\text{mispredict}})}}\times \underset{\text{sahi hone par kharcha}}{\underbrace{0}}+\underset{\text{galat ka fraction}}{\underbrace{P_{\text{mispredict}}}}\times \underset{\text{galat hone par kharcha}}{\underbrace{\text{Penalty}}}$

Pehla term khatam ho jaata hai (sahi guesses par kuch kharcha nahi), aur bacha rehta hai $P_{\text{mispredict}}\times \text{Penalty}$. Yahi reason hai ki prediction stalling se behtar hai: jab tak tum kaafi baar sahi ho, average cost always-stall cost se kaafi neeche chali jaati hai.

PICTURE. Do side-by-side timelines: "always stall" (har branch par ek fixed grey gap) vs. "predict" (zyaatar koi gap nahi, kabhi-kabhi ek amber flush).

Step 4 — "Wasted cycles" ko CPI mein convert karna

KYA HAI. Hume poore program ki speed measure karne ke liye ek single number chahiye. Woh number hai CPI = Cycles Per Instruction — average mein, har instruction par kitne clock ticks lagte hain?

KYUN. Ek perfect pipeline mein, ek instruction har cycle mein retire hoti hai, to $\text{CPI}=1$. Yeh humara baseline hai. Har branch misprediction extra cycles add karta hai jinhein koi instruction "productively use" nahi karti — isliye yeh CPI ko 1 se upar inflate karti hai. CPI sahi tool hai (na ki "total time") kyunki yeh per-instruction damage ko isolate karta hai, program ki length se independent.

PICTURE. Height 1 se shuru hota ek bar (ideal), upar ek amber block stack hua hai jo average penalty cycles ko represent karta hai jo andar aa rahi hain.

$\text{CPI}=\underset{\text{ideal: har cycle mein ek instruction}}{\underbrace{1}}+\underset{\text{woh damage jo hum ab calculate karenge}}{\underbrace{(\text{branches se extra cycles per instruction})}}$

Step 5 — Sirf kuch instructions branches hain

KYA HAI. Har instruction branch nahi hoti — zyaatar adds, loads, stores hoti hain. Maan lo $P_{\text{branch}}$ un sabhi instructions ka fraction hai jo branches hain (jaise 20%, yaani $0.20$).

KYUN. Step 3 mein penalty "per branch" thi. Lekin CPI sabhi instructions par average hota hai. Isliye hume per-branch damage ko scale down karna hoga — kitna, yeh depend karta hai ki branches kitni baar aati hain. Agar 5 mein se sirf 1 instruction branch hai, to branch damage baaki 4 par dilute ho jaata hai.

PICTURE. 10 instruction boxes ki ek strip; 2 amber highlight hain (branches), 8 cyan hain (non-branches). Sirf amber wale kabhi bhi flush cause kar sakte hain.

$\text{extra cycles per instruction}=\underset{\begin{array}{c}\text{ek instruction kitni baar}\\ \text{branch hoti hai}\end{array}}{\underbrace{P_{\text{branch}}}}\times \underset{\begin{array}{c}\text{ek branch kitni baar}\\ \text{galat guess hoti hai}\end{array}}{\underbrace{P_{\text{mispredict}}}}\times \underset{\begin{array}{c}\text{ek galat guess}\\ \text{ka kharcha}\end{array}}{\underbrace{\text{Penalty}}}$

Step 6 — Poora formula assemble karo aur numbers plug in karo

KYA HAI. Step 5 ko Step 4 mein substitute karo:

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

KYUN. Har factor ek sawaal ka jawab deta hai, aur unhe multiply karna sawaalon ko chain karta hai: yeh branch kitni baar hoti hai? → unमें se, kitni baar galat? → ek galat kitna mehenga hai? Teeno probabilities aur cost ko multiply karo aur tum paate ho average extra cycles per instruction, ideal 1 ke upar baithe hue.

PICTURE. Teeno multiplied factors teen shrinking funnels ki tarah: 100% instructions → 20% branches → unमें se 10% mispredict → har ek par 10 cycles ka kharcha.

Step 7 — Degenerate cases (koi bhi scenario unseen mat chhodo)

KYA HAI. Formula ko sanity-check karne ke liye har factor ko uski extreme par le jaao.

KYUN. Yeh extremes dikhati hain ki formula sahi behave karta hai: yeh exactly ideal 1.0 par collapse ho jaata hai jab punish karne ke liye kuch nahi hota, aur jab misprediction rate aur penalty dono bade hote hain to yeh blow up ho jaata hai. Isliye modern deep-pipeline CPUs $P_{\text{mispredict}}$ par itna dhyan dete hain — Penalty multiplier unforgiving hota hai jab pipelines lambi hoti hain.

PICTURE. Teen cases ke liye teen bars (perfect, moderate, coin-flip-deep) taaki tum CPI ko 1.0 se 3.0 tak dekhte raho.

Ek-picture summary

Yeh single diagram poori kahani chain karta hai: ideal 1 CPI → branches thode-thode time par aati hain → kuch fraction mispredict hota hai → har misprediction Penalty cycles flush karta hai → woh cycles us 1 ke upar stack hoti hain, final CPI deti hain. Beech wale funnel ko chhota karna ($P_{\text{mispredict}}$, parent note mein har predictor ka kaam) ek aisa lever hai jise designer runtime par poori tarah control kar sakta hai.

Yeh bhi dekho: Superscalar Processors (har cycle mein kai instructions har flush ka kharcha multiply karte hain), Cache Performance (extra cycles ka ek aur source ussi CPI baseline par stack hota hai), Compiler Optimizations (compiler $P_{\text{branch}}$ reduce kar sakta hai aur static prediction improve kar sakta hai).