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

WHY does branch prediction exist at all?

Imagine a classic 5-stage pipeline: IF → ID → EX → MEM → WB.

The branch resolves in EX. So between fetching the branch (IF) and resolving it (EX) there are 2 instructions already in flight. If we guessed wrong, those must be squashed.

Formula Branch misprediction penalty — derived

Let:

$p$ = probability a branch is mispredicted
$f$ = fraction of instructions that are branches
$c$ = misprediction penalty in cycles (number of pipeline slots flushed)

Ideal CPI (cycles per instruction) of a pipeline is $1$ . Every mispredicted branch wastes $c$ extra cycles. The expected extra cycles per instruction is: $\text{extra CPI} = f \cdot p \cdot c$ Why? Multiply the three independent quantities: how often you meet a branch ( $f$ ), how often you're wrong given a branch ( $p$ ), and the cost each time you're wrong ( $c$ ). $\boxed{\text{CPI} = 1 + f \cdot p \cdot c}$ The penalty $c$ equals the number of stages between fetch and branch resolution — i.e. how many wrongly-fetched instructions must die. Deeper pipelines → bigger $c$ → prediction matters more.

Static prediction — guess without history

Common static schemes (in order of cleverness):

Predict not-taken — keep fetching sequentially. Cheap; right whenever the branch falls through.
Predict taken — assume the branch jumps. Needs the target early, so harder for forward branches.
BTFNT (Backward-Taken, Forward-Not-taken) — backward branches are predicted taken, forward branches predicted not-taken.

Worked example Static BTFNT on a loop

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

A loop of $N$ iterations is taken $N-1$ times and not-taken once. BTFNT predicts taken every time → only 1 misprediction (the final exit) per loop entry. Why this step? The single wrong guess is the loop exit, which BTFNT can never see coming statically — and that's the irreducible cost.

Dynamic prediction — learn from history

Static can't adapt. Dynamic predictors keep a small table of runtime history indexed by the branch's address.

1-bit predictor (the warm-up)

2-bit saturating counter (the workhorse)

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

Worked example Trace a 2-bit counter through a loop of length 4, run twice

Start state $11$ (Strongly Taken). Outcomes for one loop: T,T,T,N (exit), then loop re-runs: 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

Why this step? The exit decrements $11\to10$ but 10 still predicts Taken, so re-entry is correct. Net: 1 miss per loop instead of 2. For a 1-bit predictor you'd see 2 misses each pass.

BTB — Branch Target Buffer

Recall Feynman: explain it to a 12-year-old

You're walking down a hallway with lots of doors. At each door, you have to decide before you reach it whether you'll go straight or turn. If you guess wrong, you have to walk all the way back — that wastes time. So you keep a little notebook: "Last few times at this door I turned right." After being surprised once you don't immediately change your mind — you wait for two surprises, because one weird day doesn't mean the pattern changed. That notebook of confident guesses is the 2-bit predictor. And next to each door's note you also scribble where it led last time, so you can sprint there instantly — that's the BTB.

Flashcards

What is a control hazard?

A pipeline stall caused because a branch's outcome and target are resolved late (in EX) while fetch needs the next address now (in IF).

Branch misprediction penalty formula and meaning of each term?

\text{CPI}=1+f\cdot p\cdot c

;

f

=fraction of branches,

p

=misprediction probability,

c

=cycles flushed (≈ stages between fetch and resolution).

What is BTFNT static prediction?

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

Why does a 1-bit predictor mispredict a tight loop twice per execution?

Once on the loop exit (flips bit to not-taken), then again on re-entry (bit now wrongly says not-taken).

What are the four states of a 2-bit saturating counter?

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

How does a 2-bit predictor update?

On Taken increment (saturate at 11), on Not-taken decrement (saturate at 00); top bit is the prediction.

Why are 2 bits better than 1 for loops?

They add hysteresis — one surprise (loop exit) only weakens confidence, doesn't flip the prediction, so re-entry is still correct → 1 miss/loop instead of 2.

What is a BTB and what does it store?

Branch Target Buffer: a PC-indexed cache holding (branch PC tag, predicted target address, prediction bits) so the target is known in IF.

Why is the BTB needed in addition to the direction predictor?

The 2-bit counter only gives Taken/Not-taken; the BTB supplies WHERE to jump, available in IF, removing the bubble on correctly-predicted taken branches.

A correctly predicted taken branch with a BTB hit costs how many cycles?

0 cycles (target fetched immediately from the BTB in IF).

Connections

Pipelining and Hazards — branch prediction solves the control hazard.
Pipeline Depth and CPI — deeper pipelines raise $c$ , making prediction more critical.
Speculative Execution — executing predicted-path instructions before resolution.
Caches and Locality — BTB is itself a small cache exploiting locality of branches.
Out-of-Order Execution — relies on accurate prediction to keep the window full.
Loop Unrolling — compiler trick that reduces branch frequency $f$ .

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, modern CPU pipeline hota hai — instructions ek line mein assembly line ki tarah process hote hain. Problem yeh hai ki jab ek branch (if/loop wala jump) aata hai, to CPU ko abhi (fetch stage mein) decide karna padta hai ki agla instruction kahan se uthaun, lekin branch ka asli answer to baad mein (EX stage mein) pata chalta hai. Agar guess galat nikla, to jo instructions galti se andar aaye the unhe flush (phenk dena) karna padta hai — yeh time waste hai. Isi waste ko bachane ke liye branch prediction karte hain.

Static prediction simple hai: compile time pe hi fix guess. Best trick hai BTFNT — backward jump (loop ke bottom) ko "taken" maano, forward jump (if/skip) ko "not-taken" maano. Kyun? Kyunki loops baar-baar taken hote hain, aur if-conditions aksar skip ho jaate hain. Zero runtime cost mein achha accuracy.

Dynamic prediction runtime se seekhta hai. 1-bit predictor "last time jaisa" guess karta hai, par loop mein do baar galti karta hai (exit pe, aur dobara entry pe). Isi liye 2-bit saturating counter use karte hain: prediction badalne ke liye do consecutive surprises chahiye. Ek anomaly (loop exit) sirf confidence kam karta hai, prediction nahi palatta — to loop mein sirf ek hi galti. Aur BTB (Branch Target Buffer) ek chhota cache hai jo yaad rakhta hai ki branch kahan jump karega, taaki taken branch ka cost zero ho jaye. Formula yaad rakho: $CPI = 1 + f\cdot p\cdot c$ — branches kam ho, misprediction kam ho, ya penalty kam ho to CPU fast.

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

WHY does branch prediction exist at all?

Static prediction — guess without history

Dynamic prediction — learn from history

1-bit predictor (the warm-up)

2-bit saturating counter (the workhorse)

BTB — Branch Target Buffer

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Computer Architecture (Deep)

Connections