Foundations — Branch prediction (static and dynamic)

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

Pehle se Branch Prediction ke parent note ko padhne se pehle, tumhe har symbol ko sachchi tarah se apna banana hoga jo wo tumhare samne phenkta hai. Yeh page har ek ko kuch bhi nahi se build karta hai — pehle plain words mein, phir ek picture, phir woh reason ki topic ko yeh kyun chahiye.

1. "Pipeline" asal mein kya hoti hai

Ek classic 5-stage pipeline mein yeh stages hoti hain, order mein:

1. Fetch (F) — instruction ko memory se grab karo.
2. Decode (D) — pata lagao yeh kya hai.
3. Execute (E) — arithmetic / compare karo.
4. Memory (M) — data memory read ya write karo.
5. Writeback (W) — result ko register mein store karo.

Picture dekho. Har row ek instruction hai; har column ek clock cycle hai (ek "tick"). Cycle 5 par poori line bhar jaati hai: paanch alag instructions ek saath kaam mein hain. Isliye CPUs fast hote hain — lekin yahi exactly woh reason bhi hai ki branches kyun hurt karti hain, jaise hum dekhenge.

2. Program Counter — PC

Parent note ke example mein, addresses 100, 104, 108, ... jaate hain. Yeh 4 se jump karte hain kyunki har instruction 4 bytes wide hoti hai.

3. "Branch" kya hoti hai

Ek conditional branch ke do possible outcomes hote hain:

• Taken — condition true thi, isliye hum ek naye address par jump karte hain jise target kehte hain.
• Not-Taken — condition false thi, isliye hum bas PC+4 par fall through karte hain.

Red arrow taken path hai (target par jump). Black arrow not-taken fall-through hai. CPU dono par nahi chal sakta — use ek pick karna padta hai fetch ke liye pehle compare khatam ho usse. Woh pick hi prediction hai.

4. Cycles, stalls, aur "penalty"

Picture mein, CPU ne galat path predict kiya aur teen instructions fetch kar li (grey). Jab branch Execute par resolve hoti hai, woh teen flush ho jaati hain (red mein cross out) — barbaad kaam. Waste hue cycles ki sankhya branch penalty hai.

5. Probability — $P_{\text{something}}$ padhna

Parent note $P_{\text{branch}}$ aur $P_{\text{mispredict}}$ jaisi cheezein likhta hai. Letter $P$ bas matlab hai "yeh kitni baar hota hai uska fraction," 0 aur 1 ke beech ki ek number.

6. CPI — woh score jo hum kam karna chahte hain

7. Accuracy — ek predictor ko measure karna

8. Bits, binary, aur modulo mod

Dynamic predictors ek table ko PC ke bits use karke index karte hain. Teen choti ideas isse readable banati hain.

9. State machines — parent ke diagrams mein arrows

1-bit predictor ke 2 states hain (0=predict Not-Taken, 1=predict Taken). 2-bit predictor ke 4 states hain (00→11). T / NT se label arrows kehte hain kahan jaana hai jab branch Taken ya Not-Taken nikle.

Red arrow hysteresis highlight karta hai: Strongly-Taken (11) se, ek akela Not-Taken sirf ek step peeche Weakly-Taken (10) par jaata hai — woh abhi bhi Taken predict karta hai. Yeh "zidd" hi wajah hai ki 2-bit counter loop ke ek-time exit se bachi rehti hai bina apni poori opinion flip kiye.

Prerequisite map

Baayein taraf har foundation parent topic mein feed karta hai daayein taraf: tum kyun prediction payoff karti hai nahi samajh sakte (CPI equation) pipelines aur penalties ke bina, aur tum dynamic predictors kaise yaad karte hain nahi samajh sakte bits aur state machines ke bina.

Yeh foundations baahri connections rakhte hain Speculative Execution se (kisi guess par act karna), Instruction-Level Parallelism (ILP) aur Superscalar Processors se (kyun deep pipelines branches ko costly banate hain), Cache Performance se (galat path se fetch karna caches bhi pollute karta hai), aur Compiler Optimizations se (jahan BTFNT hints insert ki jaati hain).

Equipment checklist

Daayein side cover karo aur khud ko test karo.