Branch prediction (static and dynamic)

The Branch Problem

In a pipelined processor, the fetch stage grabs the next instruction before the previous branch resolves. Consider:

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

By the time we decode the BEQ at cycle 2, we've already fetched instruction at108 (cycle 1). By the time we execute the compare and know the branch outcome (cycle 5), we've fetched 4-5 more instructions.

Static Branch Prediction

Static prediction uses a fixed rule decided at design time or compile time—no runtime learning.

Common Static Schemes

Predict Not-Taken (PNT)
- Always fetch the fall-through instruction (PC + 4).
- Why?: Simple hardware, no state needed.
- Works for: Forward branches (often not-taken, e.g., error checks if (rare_error) goto handler).
Predict Taken (PT)
- Always fetch the branch target.
- Works for: Backward branches (loops! for and while usually iterate multiple times, so the backwards jump is taken90%+ of the time).
Backwards Taken, Forward Not-Taken (BTFNT)
- Compiler hint: If branch target address< PC, predict taken. Else, not-taken.
- Accuracy: ~60-70% for typical code (loops dominate branches).

Formula Static Prediction Accuracy (Empirical)

For the BTFNT scheme: $\text{Accuracy} = \frac{N_{\text{correct predictions}}}{N_{\text{total branches}}}$ Derivation of expected accuracy:

Let $f_L =0.7$ be the fraction of branches that are loops (backward jumps), with loop average iteration count $n = 10$ . Loop branches are taken $\frac{n-1}{n} = 0.9$ of the time (last iteration not-taken).
Let $f_F = 0.3$ be forward branches, taken ~30% of the time (error checks, early returns). $P_{\text{correct}} = f_L \cdot 0.9 + f_F \cdot 0.7 = 0.7 \times 0.9 + 0.3 \times 0.7 = 0.63 + 0.21 = 0.84$

So we expect ~84% accuracy for BTFNT in loop-heavy code. But this is a fixed ceiling—no learning.

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. Correct 99/100 times (99% hit rate).
Break condition arr[i] < 0: Forward → Predict Not-Taken. Correct if array mostly positive. Why the backward branch works: The loop body executes 99 times, jumps back 99 times, falls through once. Static "always taken" is right 99%.

Why the forward branch can fail: If the array has many negatives, we mispredict every break, flushing the pipeline each time.

Dynamic Branch Prediction

Dynamic prediction uses runtime history to adapt. The CPU remembers "last time I saw this branch, it went taken/not-taken."

1-Bit Predictor (Branch History Table)

Structure: A table indexed by low-order bits of PC (branch address). Each entry is a 1-bit state:

0 = Predict Not-Taken
1 = Predict Taken

Update rule: After the branch resolves, set the bit to the actual outcome.

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: $\text{BHT index} = \text{PC}[n:2] \mod 2^k$ (Use $k$ bits of the PC, ignoring bottom 2 bits since instructions are 4-byte aligned.)

Worked example 1-Bit Predictor on a Loop

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

Execution trace (assume BHT initially all 0): | 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% (!). Why so bad? The predictor gets the first and last iterations wrong (cold start + loop exit).

Why this step matters: This shows the fundamentalaw of 1-bit predictors—they can't handle the natural pattern of loops (many T, one NT). They oscillate at loop boundaries.

2-Bit Saturating Counter (Bimodal Predictor)

To fix the 1-bit predictor's loop problem, use a 2-bit counter with hysteresis (require two mispredictions to change behavior).

States:

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

Prediction rule: Predict Taken if counter ≥ 10, else Not-Taken.

Update rule: Increment on taken (saturate at 11), decrement on not-taken (saturate at 00).

Formula 2-Bit Predictor State Diagram

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

Why hysteresis helps: A loop that goes T, T, T, .., T, NT starts at 00, climbs to 11 (strongly taken), then a single NT only drops it to 10 (still predicts taken). The next loop iteration immediately reinforces 11. We mispredict only the first and last iterations, not every loop exit.

Worked example 2-Bit Predictor on Same Loop

Loop: 3 iterations, then 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% (worse! But only because loop is too short).

Second iteration of the loop (we re-enter):

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%. Much better! The counter has "learned" the loop behavior.

For a100-iteration loop: Mispredict the first 1-2 iterations (cold start) and the exit (1 mispredict). Accuracy = 97/100 = 97%.

Correlating Predictors (Two-Level Adaptive)

Insight: A branch's outcome often depends on recent branch history, not just its own past.

Example:

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

If B1 is not-taken, B2 never executes. If B1 is taken, B2's outcome depends on b. A correlating predictor uses a global history register (GHR) to track the last $n$ branch outcomes, then indexes a table with (PC, GHR).

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 tracks last 2 branches: 00, 01, 10, 11 (not-taken=0, taken=1).

Scenario:

First time: B1 not-taken → GHR = ...00. Next B1 is index by GHR=00 table.
Fourth time: B1 taken → GHR = ...01. Now B2 uses GHR=01 table (different counter!).

Benefit: B2's predictor isn't polluted by the times B2 never executed (when B1 was not-taken). Accuracy improves from ~60% (bimodal, confused by path dependence) to ~85%.

Tournament Predictor (Hybrid)

Problem: No single predictor wins for all branches. Loops love bimodal (local history). Corelated code loves correlating predictors.

Solution: Tournament predictor runs multiple predictors in parallel (e.g., a local2-bit predictor + a global correlating predictor), then uses a meta-predictor (another 2-bit counter) to choose which predictor to trust for each branch.

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 hash to the same BHT entry, interfering with each other. Larger tables reduce this.

Common mistake Common Misconception: "Dynamic Predictors Always Win"

Wrong idea: "A 2-bit predictor is always better than static BTFNT."

Why it feels right: Dynamic predictors learn and adapt, so they should beat a fixed rule.

The truth: For very short loops (2-3 iterations) or first-time execution (cold start), a2-bit predictor is still training and may be wrong2-3 times. A static "predict taken for backward branches" is right immediately. Also, if the BHT is too small, aliasing causes different branches to fight over the same counter, destroying learned patterns—static schemes suffer no aliasing.

When static wins: Embedded systems with small branch counts, or compilers that can profile and insert hints (e.g., __builtin_expect in GCC tells the CPU "this branch is cold").

The fix: Use hybrid predictors that fall back to static hints when confidence is low, or use tagged predictors (store partial PC in the table to reduce aliasing).

Recall Feynman Explanation (age 12)

Imagine you're reading a choose-your-own-adventure book, but you're reading it really fast—you're on page 10, but you've already flipped ahead and started reading page 11,12, 13, all at once. Then page 10 says "If you chose the sword, turn to page 50. If you chose the shield, turn to page 60."

Uh-oh! You don't know which page you should've been reading. You've wasted time reading the wrong pages.

Branch prediction is the CPU's guess: "I bet they chose the sword (because last time they did), so I'll start reading page 50 right now." If the guess is right, you saved time. If wrong, you throw away pages11-13 and start over at page 60(that's the pipeline flush).

Static prediction: "I always guess sword" (a fixed rule). Dynamic prediction: "I remember the last 5 choices you made, and I guess based on that pattern."

The CPU gets really good at guessing (95%+ correct), so the book flies by!

Connections

Pipeline Hazards: Branch prediction solves control hazards (not knowing which instruction to fetch next).
Speculative Execution: Prediction enables speculation; mispredictions require rollback mechanisms.
Instruction-Level Parallelism (ILP): High ILP demands high prediction accuracy (more instructions flight = higher misprediction cost).
Cache Performance: Wrong-path instructions pollute the instruction cache; predictors with high accuracy reduce this.
Superscalar Processors: Multiple issue per cycle amplifies branch penalties; advanced predictors are critical.
Compiler Optimizations: Profile-guided optimization (PGO) can insert static hints or reorder code to help predictors.

#flashcards/hardware

What is the branch penalty in a pipelined CPU? :: The number of wasted cycles when a branch misprediction occurs, typically 5-10 cycles (the depth of the pipeline must be flushed and restarted from the correct path).

Why does static "backwards taken, forward not-taken" work well?

Loops (backward branches) iterate many times (taken 90%+), while forward branches (error checks) are usually not-taken. This heuristic exploits the natural behavior of typical code.

What is the difference between a 1-bit and 2-bit branch predictor?

A 1-bit predictor changes prediction on every misprediction (oscillates at loop exits). A 2-bit predictor requires two consecutive mispredictions to flip, providing hysteresis that stabilizes loop behavior.

How does a correlating (two-level) predictor improve on a bimodal predictor?

It uses a global history register (GHR) to track recent branch outcomes, allowing it to select different prediction tables based on the path taken. This captures branch correlation (e.g., nested ifs where one branch's outcome affects another).

What does a tournament predictor do?

It runs multiple predictors (e.g., local bimodal + global correlating) in parallel and uses a meta-predictor (selector) to choose which one to trust for each branch, learning which predictor works best for each branch pattern.

Why can't a 2-bit predictor eliminate all loop mispredictions?

The loop exit is always mispredicted once per loop invocation—the counter saturates at "strongly taken," so the not-taken exit mispredicts. This is 1 error per loop, which is ~1% for long loops but ~33% for short loops.

What is aliasing in branch prediction?

When multiple branches hash to the same entry in the BHT (due to limited table size), they interfere with each other's learned patterns, reducing accuracy. Larger tables or tagged entries reduce aliasing.

What is the formula for average CPI with branch mispredictions?

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

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, sabse pehle intuition samajh lo. Modern CPU ek assembly line ki tarah kaam karta hai jahan instructions execute hone se bahut pehle fetch ho jaate hain. Lekin problem tab aati hai jab ek if condition ya loop aata hai — jaise if (x > 5) — kyunki CPU ko abhi tak nahi pata ki kaunsa raasta lena hai. Condition ka result aane mein 10-20 cycles lag jaate hain, aur tab tak pipeline khali baithi rehti hai, kaam maang rahi hoti hai. Isliye CPU ek "educated guess" lagata hai — "shayad ye branch lena padega" — aur us guess ke basis pe instructions speculatively fetch kar leta hai. Agar guess sahi nikla to full speed maintain rehti hai, aur agar galat nikla to pipeline flush karni padti hai matlab kiya hua kaam bekaar chala jaata hai.

Ab ye kyun matter karta hai? Formula dekho: agar 20% instructions branches hain, 10% mispredict hoti hain, aur penalty 10 cycles ki hai, to CPI 1 se badhkar 1.2 ho jaata hai — yaani sirf branch galat guess karne se 20% performance loss! Yahi reason hai ki prediction accha hona bahut zaroori hai. Static prediction ek fixed rule use karta hai — jaise BTFNT (Backwards Taken, Forward Not-Taken). Iska logic simple hai: loops backward jump karte hain aur baar baar chalte hain (isliye "taken" maan lo), jabki forward branches jaise error checks aksar nahi chalte (isliye "not-taken" maan lo). Loop-heavy code mein ye scheme lagbhag 84% accuracy de deta hai.

Lekin static prediction ki ek badi limitation hai — ye seekhta nahi. Ek fixed ceiling pe atak jaata hai. Isliye dynamic branch prediction aata hai, jo runtime history dekh ke apne guesses ko adapt karta hai — matlab jaisa pehle hua tha uske basis pe agla guess better banata hai. Yahi real-world CPUs ki taakat hai: static rules se kaam chala lete hain simple cases mein, aur complex patterns ke liye dynamic prediction lagate hain jo actual program behaviour se seekh ke accuracy 95%+ tak le jaata hai. Iske bina modern deep pipelines efficient hi nahi ho paate.

The Branch Problem

Static Branch Prediction

Common Static Schemes

Dynamic Branch Prediction

1-Bit Predictor (Branch History Table)

2-Bit Saturating Counter (Bimodal Predictor)

Correlating Predictors (Two-Level Adaptive)

Tournament Predictor (Hybrid)

Comparison: Static vs Dynamic

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Advanced Microarchitecture

Connections