Branch prediction — static, dynamic (2-bit predictor, BTB)

4.1.21 · Coding › Computer Architecture (Deep)

Branch prediction exist kyun karta hai?

Socho ek classic 5-stage pipeline: IF → ID → EX → MEM → WB.

Branch EX mein resolve hoti hai. Toh branch fetch karne (IF) aur resolve karne (EX) ke beech 2 instructions already in flight hote hain. Agar guess galat hua, toh unhe squash karna padega.

Static prediction — history ke bina guess karo

Common static schemes (cleverness ke order mein):

Predict not-taken — sequentially fetch karte raho. Sasta; jab branch fall-through kare tab sahi.
Predict taken — assume karo ki branch jump kari. Target pehle chahiye, toh forward branches ke liye mushkil.
BTFNT (Backward-Taken, Forward-Not-taken) — backward branches ko taken predict karo, forward branches ko not-taken predict karo.

Worked example Loop par Static BTFNT

top:  ...           ; loop body
      i++           
      cmp i, N
      blt top       ; backward branch -> predict TAKEN

$N$ iterations wala loop $N - 1$ baar taken hota hai aur ek baar not-taken. BTFNT har baar taken predict karta hai → poore loop mein sirf 1 misprediction (final exit par). Ye step kyun? Ek galat guess loop exit hai, jise BTFNT statically kabhi nahi dekh sakta — aur ye irreducible cost hai.

Dynamic prediction — history se seekho

Static adapt nahi kar sakta. Dynamic predictors ek chhoti si runtime history ki table maintain karte hain jo branch ke address se indexed hoti hai.

1-bit predictor (warm-up)

2-bit saturating counter (workhorse)

Figure — Branch prediction — static, dynamic (2-bit predictor, BTB)

Worked example 4 length ke loop ko do baar run karne par 2-bit counter trace karo

Start state $11$ (Strongly Taken). Ek loop ke outcomes: T,T,T,N (exit), phir loop re-run: T,T,T,N.

Outcome	State before	Predict	Correct?	State after
T	11	T	✓	11
T	11	T	✓	11
T	11	T	✓	11
N (exit)	11	T	✗	10
T (re-enter)	10	T	✓	11
T	11	T	✓	11
T	11	T	✓	11
N (exit)	11	T	✗	10

Ye step kyun? Exit $11 \to 10$ decrement karta hai lekin 10 still Taken predict karta hai, toh re-entry correct hai. Net: 1 miss per loop 2 ki jagah. 1-bit predictor mein har pass mein 2 misses dikhte.

BTB — Branch Target Buffer

Recall Feynman: 12-saal ke bachche ko samjhao

Tum ek hallway mein chal rahe ho jisme bahut saare doors hain. Har door par, tumhe pahunchne se pehle decide karna hota hai ki straight jaoge ya turn loge. Galat guess hua toh poora wapas jaana padega — time waste. Toh tum ek chhoti notebook rakhte ho: "Is door par pichli kuch baar main right muda tha." Ek baar surprise hone ke baad tum turant apna mind nahi badalte — do surprises ka wait karte ho, kyunki ek ajeeb din ka matlab pattern badal gaya nahi hai. Yahi confident guesses ki notebook 2-bit predictor hai. Aur har door ke note ke paas tum wahan bhi likhte ho jahan wo pichli baar gaya tha, taaki tum wahan turant sprint kar sako — yahi BTB hai.

Flashcards

Control hazard kya hota hai?

Ek pipeline stall jo is wajah se hoti hai ki branch ka outcome aur target late resolve hota hai (EX mein) jabki fetch ko next address abhi chahiye (IF mein).

Branch misprediction penalty formula aur har term ka matlab?

CPI = 1 + f \cdot p \cdot c

;

f

=branches ka fraction,

p

=misprediction probability,

c

=cycles flush hue (≈ fetch aur resolution ke beech stages).

BTFNT static prediction kya hoti hai?

Backward branches Taken predict hote hain (loops), forward branches Not-taken predict hote hain (if/skip code).

Tight loop mein 1-bit predictor har execution mein do baar mispredict kyun karta hai?

Loop exit par ek baar (bit not-taken par flip hoti hai), phir re-entry par dobara (bit ab galat not-taken kehti hai).

2-bit saturating counter ke chaar states kya hain?

11 Strongly Taken, 10 Weakly Taken (dono Taken predict karte hain); 01 Weakly Not-taken, 00 Strongly Not-taken (dono Not-taken predict karte hain).

2-bit predictor update kaise hota hai?

Taken par increment karo (saturate at 11), Not-taken par decrement karo (saturate at 00); top bit prediction hai.

Loops ke liye 2 bits, 1 bit se better kyun hain?

Ye hysteresis add karte hain — ek surprise (loop exit) sirf confidence ko weaken karta hai, prediction flip nahi karta, toh re-entry still correct hoti hai → 1 miss/loop instead of 2.

BTB kya hai aur ye kya store karta hai?

Branch Target Buffer: ek PC-indexed cache jo (branch PC tag, predicted target address, prediction bits) store karta hai taaki IF mein hi target pata ho.

Direction predictor ke saath BTB kyun zaroori hai?

2-bit counter sirf Taken/Not-taken deta hai; BTB KAHAN jaana hai ye supply karta hai, IF mein available, correctly-predicted taken branches par bubble remove karta hai.

BTB hit ke saath correctly predicted taken branch kitne cycles cost karta hai?

0 cycles (target IF mein BTB se immediately fetch hota hai).

Connections

Pipelining and Hazards — branch prediction control hazard solve karta hai.
Pipeline Depth and CPI — deeper pipelines $c$ badhate hain, prediction zyada critical ho jaati hai.
Speculative Execution — resolution se pehle predicted-path instructions execute karna.
Caches and Locality — BTB khud ek chhota cache hai jo branches ki locality exploit karta hai.
Out-of-Order Execution — accurate prediction pe rely karta hai window full rakhne ke liye.
Loop Unrolling — compiler trick jo branch frequency $f$ reduce karta hai.