Branch prediction (static and dynamic) — Hinglish notes

5.3.7 · Hardware › Advanced Microarchitecture

Branch Ki Problem

Ek pipelined processor mein, fetch stage next instruction ko pehle grab kar leti hai jab se pichla branch resolve ho. Consider karo:

100: CMP R1, #5
104: BEQ target    ; branch if equal
108: ADD R2, R3    ; fall-through path
...
200: SUB R4, R5    ; target path

Jab tak hum cycle 2 mein BEQ ko decode karte hain, hum 108 ki instruction already fetch kar chuke hain (cycle 1). Jab tak hum compare execute karte hain aur branch outcome pata chalta hai (cycle 5), hum 4-5 aur instructions fetch kar chuke hote hain.

Static Branch Prediction

Static prediction ek fixed rule use karta hai jo design time ya compile time par decide hoti hai—koi runtime learning nahi hoti.

Common Static Schemes

Predict Not-Taken (PNT)
- Hamesha fall-through instruction (PC + 4) fetch karo.
- Kyun?: Simple hardware, koi state ki zaroorat nahi.
- Kahan kaam karta hai: Forward branches ke liye (aksar not-taken, jaise error checks if (rare_error) goto handler).
Predict Taken (PT)
- Hamesha branch target fetch karo.
- Kahan kaam karta hai: Backward branches ke liye (loops! for aur while zyada tar kai baar iterate karte hain, toh backwards jump 90%+ baar liya jaata hai).
Backwards Taken, Forward Not-Taken (BTFNT)
- Compiler hint: Agar branch target address < PC hai, toh predict taken. Warna, not-taken.
- Accuracy: Typical code ke liye ~60-70% (loops mein branches dominant hote hain).

Worked example Static Prediction in Action

for (int i = 0; i < 100; i++) {  // backward branch
   if (arr[i] < 0) break;       // forward branch
   sum += arr[i];
}

BTFNT predictions:

Loop condition i < 100: Backward → Predict Taken. 99/100 baar sahi (99% hit rate).
Break condition arr[i] < 0: Forward → Predict Not-Taken. Sahi hoga agar array mostly positive ho. Backward branch kyun kaam karta hai: Loop body 99 baar execute hoti hai, 99 baar peeche jump karta hai, ek baar fall through hota hai. Static "always taken" 99% sahi hota hai.

Forward branch kyun fail ho sakta hai: Agar array mein kaafi negatives hain, toh har break par mispredict hoga, aur har baar pipeline flush hogi.

Dynamic Branch Prediction

Dynamic prediction adapt karne ke liye runtime history use karta hai. CPU ko yaad rehta hai "pichli baar jab maine yeh branch dekha, yeh taken/not-taken gaya tha."

1-Bit Predictor (Branch History Table)

Structure: Ek table jo PC ke low-order bits (branch address) se index hoti hai. Har entry ek 1-bit state hai:

0 = Predict Not-Taken
1 = Predict Taken

Update rule: Branch resolve hone ke baad, bit ko actual outcome par set karo.

Formula 1-Bit Predictor State Machine

State 0 (Predict NT) --[branch taken]--> State 1 (Predict T)
State 1 (Predict T)  --[branch not taken]--> State 0 (Predict NT)

Index function: $BHT index = PC [n : 2] mod 2^{k}$ (PC ke $k$ bits use karo, neeche ke 2 bits ignore karo kyunki instructions 4-byte aligned hoti hain.)

Worked example 1-Bit Predictor on a Loop

for (int i = 0; i < 3; i++) {  // branch at PC=0x1004
   work();
}

Execution trace (maano BHT initially sab 0 hai): | Iteration | Actual Outcome | BHT State (before) | Prediction | Correct? | BHT State (after) | |-----------|----------------|------------------|----------|----------------| | 0 | Taken | 0 (NT) | Not-Taken | ❌ | 1 (T) | | 1 | Taken | 1 (T) | Taken | ✅ | 1 (T) | | 2 | Taken | 1 (T) | Taken | ✅ | 1 (T) | | Exit | Not-Taken | 1 (T) | Taken | ❌ | 0 (NT) |

Accuracy: 2/4 = 50% (!). Itna bura kyun? Predictor pehli aur aakhri iterations galat karta hai (cold start + loop exit).

Yeh step kyun important hai: Yeh 1-bit predictors ki fundamental flaw dikhata hai—yeh loops ke natural pattern (kaafi T, ek NT) handle nahi kar sakte. Yeh loop boundaries par oscillate karte hain.

2-Bit Saturating Counter (Bimodal Predictor)

1-bit predictor ki loop problem fix karne ke liye, hysteresis ke saath 2-bit counter use karo (behavior badalne ke liye do mispredictions chahiye).

States:

00 = Strongly Not-Taken (SNT)
01 = Weakly Not-Taken (WNT)
10 = Weakly Taken (WT)
11 = Strongly Taken (ST)

Prediction rule: Agar counter ≥ 10 ho toh Taken predict karo, warna Not-Taken.

Update rule: Taken par increment karo (11 par saturate), not-taken par decrement karo (00 par saturate).

Formula 2-Bit Predictor State Diagram

00 (SNT) --T--> 01 (WNT) --T--> 10 (WT) --T--> 11 (ST)
  ^--NT--^        ^--NT--^       |
          \--------------------------------NT---/

Hysteresis kyun help karta hai: Ek loop jo T, T, T, .., T, NT jaata hai, 00 se shuru hota hai, 11 tak climb karta hai (strongly taken), phir ek NT sirf 10 par drop karta hai (abhi bhi taken predict karta hai). Agla loop iteration turant 11 reinforce kar deta hai. Hum sirf pehli aur aakhri iterations mispredict karte hain, har loop exit par nahi.

Worked example 2-Bit Predictor on Same Loop

Loop: 3 iterations, phir exit.

Iteration	Actual	Counter (before)	Prediction	Correct?	Counter (after)
0	T	00 (SNT)	NT	❌	01 (WNT)
1	T	01 (WNT)	NT	❌	10 (WT)
2	T	10 (WT)	T	✅	11 (ST)
Exit	NT	11 (ST)	T	❌	10 (WT)

Accuracy: 1/4 = 25% (bura! Lekin sirf isliye kyunki loop bahut chhota hai).

Loop ka doosra run (hum phir se enter karte hain):

Iteration	Actual	Counter (before)	Prediction	Correct?	Counter (after)
0	T	10 (WT)	T	✅	11 (ST)
1	T	11 (ST)	T	✅	11 (ST)
2	T	11 (ST)	T	✅	11 (ST)
Exit	NT	11 (ST)	T	❌	10 (WT)

Accuracy: 3/4 = 75%. Bahut better! Counter ne loop behavior "seekh liya" hai.

Ek 100-iteration loop ke liye: Pehli 1-2 iterations (cold start) aur exit (1 mispredict) galat hogi. Accuracy = 97/100 = 97%.

Correlating Predictors (Two-Level Adaptive)

Insight: Ek branch ka outcome aksar recent branch history par depend karta hai, sirf apne khud ke past par nahi.

Example:

if (a > 0) {        // Branch B1
    if (b > 0) {    // Branch B2
        ...
    }
}

Agar B1 not-taken hai, toh B2 kabhi execute nahi hoga. Agar B1 taken hai, toh B2 ka outcome b par depend karta hai. Ek correlating predictor ek global history register (GHR) use karta hai jo last $n$ branch outcomes track karta hai, phir (PC, GHR) se ek table index karta hai.

Worked example (2,2) Correlating Predictor

if (x % 4 == 0) {  // B1, taken every 4th time
   if (y > 0) {   // B2, taken 50% when B1 taken
       ...
   }
}

GHR last 2 branches track karta hai: 00, 01, 10, 11 (not-taken=0, taken=1).

Scenario:

Pehli baar: B1 not-taken → GHR = ...00. Agla B1 GHR=00 table se index hota hai.
Chauthi baar: B1 taken → GHR = ...01. Ab B2 GHR=01 table use karta hai (alag counter!).

Faida: B2 ka predictor un times se pollute nahi hota jab B2 kabhi execute nahi hua (jab B1 not-taken tha). Accuracy ~60% (bimodal, path dependence se confused) se ~85% tak improve hoti hai.

Tournament Predictor (Hybrid)

Problem: Koi ek predictor sabhi branches ke liye nahi jeetta. Loops bimodal ko pasand karte hain (local history). Correlated code correlating predictors ko pasand karta hai.

Solution: Tournament predictor multiple predictors parallel mein chalata hai (jaise ek local 2-bit predictor + ek global correlating predictor), phir ek meta-predictor (ek aur 2-bit counter) use karta hai jo choose karta hai ki har branch ke liye kaun sa predictor trust karna hai.

Comparison: Static vs Dynamic

Scheme	Accuracy (typical)	Hardware Cost	Cold Start	Aliasing
Static BTFNT	60-70%	Zero (just decode)	N/A	N/A
1-bit BHT	70-80%	Small (1-bit/entry)	Bad	Yes
2-bit Bimodal	85-90%	Small (2-bit/entry)	OK	Yes
(2,2) Correlating	90-93%	Medium (4× bimodal)	OK	Yes
Tournament (Alpha 21264)	95-97%	Large (3 tables)	Good	Reduced

Aliasing: Multiple branches ek hi BHT entry par hash ho jaate hain, ek doosre mein interfere karte hain. Bade tables isse reduce karte hain.

Common mistake Common Misconception: "Dynamic Predictors Hamesha Jeette Hain"

Galat soch: "Ek 2-bit predictor hamesha static BTFNT se better hota hai."

Kyun sahi lagta hai: Dynamic predictors seekhte aur adapt karte hain, toh unhe ek fixed rule ko chahiye beat karna.

Sach yeh hai: Bahut chhote loops (2-3 iterations) ya pehli baar execution (cold start) ke liye, ek 2-bit predictor abhi bhi training mein hota hai aur 2-3 baar galat ho sakta hai. Ek static "backward branches ke liye predict taken" turant sahi hota hai. Aur agar BHT bahut chhota hai, toh aliasing kaafi branches ko ek hi counter ke liye lad'vaati hai, jo seekhe hue patterns barbad kar deti hai—static schemes mein aliasing nahi hoti.

Jab static jeetta hai: Chhote branch count wale embedded systems, ya compilers jo profile kar sakte hain aur hints insert kar sakte hain (jaise GCC mein __builtin_expect CPU ko batata hai "yeh branch cold hai").

Fix: Hybrid predictors use karo jo low confidence par static hints par fall back karte hain, ya tagged predictors use karo (aliasing reduce karne ke liye table mein partial PC store karo).

Recall Feynman Explanation (age 12)

Socho tum ek choose-your-own-adventure book padh rahe ho, lekin bahut tezi se—tum page 10 par ho, lekin tumne pehle se page 11, 12, 13 sab ek saath padh liye hain. Phir page 10 kehta hai "Agar tumne talwar chuni, toh page 50 par jao. Agar tumne dhaal chuni, toh page 60 par jao."

Oh no! Tumhe nahi pata ki tumhe kaun sa page padhna chahiye tha. Tumne galat pages padhne mein waqt barbaad kar diya.

Branch prediction CPU ka guess hai: "Mujhe lagta hai unhone talwar chuni (kyunki pichli baar unhone ki thi), toh main abhi page 50 padhna shuru karta hoon." Agar guess sahi hua, toh waqt bacha. Agar galat hua, toh pages 11-13 phenk do aur page 60 se naya shuru karo (yahi pipeline flush hai).

Static prediction: "Main hamesha talwar guess karta hoon" (ek fixed rule). Dynamic prediction: "Mujhe tumhare pichle 5 choices yaad hain, aur main uss pattern se guess karta hoon."

CPU guessing mein bahut acha ho jaata hai (95%+ sahi), toh book bahut tezi se aage chalti hai!

Connections

Pipeline Hazards: Branch prediction control hazards solve karta hai (yeh nahi pata ki agla instruction kahan se fetch karein).
Speculative Execution: Prediction speculation enable karti hai; mispredictions ke liye rollback mechanisms chahiye.
Instruction-Level Parallelism (ILP): High ILP ke liye high prediction accuracy chahiye (zyada instructions in-flight = misprediction ka zyada cost).
Cache Performance: Wrong-path instructions instruction cache pollute karte hain; high accuracy predictors isse reduce karte hain.
Superscalar Processors: Ek cycle mein multiple issue branch penalties amplify karta hai; advanced predictors critical hain.
Compiler Optimizations: Profile-guided optimization (PGO) static hints insert kar sakta hai ya code reorder kar sakta hai predictors ki madad ke liye.

#flashcards/hardware

Pipelined CPU mein branch penalty kya hota hai? :: Jab branch misprediction hoti hai tab ke wasted cycles ki sankhya, usually 5-10 cycles (pipeline ki depth flush karni padti hai aur sahi path se restart karna padta hai).

Static "backwards taken, forward not-taken" kyun achha kaam karta hai?

Loops (backward branches) kai baar iterate karte hain (90%+ baar taken), jabki forward branches (error checks) zyada tar not-taken hote hain. Yeh heuristic typical code ke natural behavior ko exploit karta hai.

1-bit aur 2-bit branch predictor mein kya fark hai?

1-bit predictor har misprediction par prediction badal deta hai (loop exits par oscillate karta hai). 2-bit predictor ke liye do consecutive mispredictions chahiye flip karne ke liye, jo hysteresis provide karta hai aur loop behavior stable karta hai.

Correlating (two-level) predictor bimodal predictor se kaise better hai?

Yeh recent branch outcomes track karne ke liye ek global history register (GHR) use karta hai, jisse yeh liye gaye path ke basis par alag prediction tables select kar sakta hai. Yeh branch correlation capture karta hai (jaise nested ifs jahan ek branch ka outcome doosre ko affect karta hai).

Tournament predictor kya karta hai?

Yeh multiple predictors (jaise local bimodal + global correlating) parallel mein chalata hai aur ek meta-predictor (selector) use karta hai jo choose karta hai ki har branch ke liye kaun sa trust karna hai, yeh seekhte hue ki har branch pattern ke liye kaun sa predictor best kaam karta hai.

Ek 2-bit predictor sabhi loop mispredictions kyun eliminate nahi kar sakta?

Loop exit har loop invocation mein ek baar hamesha mispredict hoti hai—counter "strongly taken" par saturate ho jaata hai, toh not-taken exit mispredict hoti hai. Yeh 1 error per loop hai, jo lambe loops ke liye ~1% hai lekin chhote loops ke liye ~33% hai.

Branch prediction mein aliasing kya hota hai?

Jab multiple branches limited table size ki wajah se ek hi BHT entry par hash ho jaate hain, toh yeh ek doosre ke seekhe hue patterns mein interfere karte hain, accuracy reduce karte hain. Bade tables ya tagged entries aliasing reduce karte hain.

Branch mispredictions ke saath average CPI ka formula kya hai?

CPI = 1 + P_branch × P_mispredict × Penalty. Example: 20% branches, 10% mispredict rate, 10-cycle penalty → CPI = 1.2 (20% slowdown).