Branch target buffer (BTB)

Overview

The Branch Target Buffer (BTB) is a specialized cache that stores the predicted target addresses of recently executed branch instructions. It works alongside branch predictors to eliminate the need to decode a branch instruction before predicting its target, enabling same-cycle prediction for taken branches.

Why it matters: Without a BTB, even if we predict a branch will be taken, we still need to wait until the decode stage to know where to jump. This creates a 1-2 cycle penalty. The BTB lets us fetch from the predicted target immediately.

Core Intuition

What the BTB Stores

Why this structure?

Tag matching ensures we have the right branch (not an alias)
Target address is the key payload - the "where to jump"
Metadata helps integrate with the branch predictor (some architectures combine them)

What the BTB Does NOT Store

The BTB does NOT store whether the branch will be taken - that's the branch predictor's job. The BTB only answers: "If taken, where do we go?"

How BTB Operation Works

Fetch Stage Integration

Formula BTB Lookup Process

Step 1: At instruction fetch, use current PC to index BTB $\text{BTB Index} = \text{PC}[n:m] \quad \text{(typically bits 2-10, skipping alignment bits)}$

Step 2: Compare tag $\text{Hit} = (\text{BTB.tag} == \text{PC}[\text{upper bits}])$ Step 3: On hit + predicted taken: $\text{Next PC} = \text{BTB.target}$

Why these steps?

Index extraction: Fast lookup, no full tag comparison needed initially
Tag comparison: Verify it's actually the right branch (handles aliasing)
Target selection: Bypass normal PC+4 increment, jump directly to target

The Decision Tree

PC arrives at fetch stage
    ↓
BTB lookup (parallel with I-cache)
    ↓
    ├─ BTB Miss → Use default next PC (PC+4)
    │             (Not a branch, or never seen before)
    │
    └─ BTB Hit → Have target address
                ↓
                 Branch Predictor: Taken?
                    ├─ Predicted NOT taken → PC+4
                    └─ Predicted TAKEN → Use BTB target

Critical insight: The BTB lookup and branch prediction happen in parallel during the same cycle. The processor doesn't wait for decode.

Derivation: Why BTB Reduces Branch Penalty

Let's derive the cycle savings from first principles.

Why this matters quantitatively: If 20% of instructions are branches, and 60% of branches are taken:

Without BTB: $0.20 \times 0.60 \times 2 = 0.24$ cycles/instruction lost
With BTB (95% accuracy): $0.20 \times 0.60 \times 0.05 \times 5 = 0.03$ cycles/instruction lost
IPC improvement: ~24% faster execution

Worked Examples

Worked example Example 1: BTB Hit on Conditional Branch

Code:

0x1000: cmp r1, r2
0x1004: beq 0x2000    ; Branch if equal
0x1008: add r3, r4, r5
...
0x2000: mul r6, r7, r8  ; Target

First execution (BTB miss):

PC=0x1004: Fetch beq, BTB miss
PC=0x1008: Fetch add (default PC+4)
Decode stage: Discover beq, compute target 0x2000
Flush pipeline, refetch from 0x2000
Update BTB: Store PC=0x1004 → Target=0x2000

Second execution (BTB hit):

PC=0x1004: Fetch beq, BTB hit (tag matches)
Branch predictor: "Taken" (from history)
Same cycle: Use BTB target → PC=0x2000
Next cycle: Fetch from 0x2000 (no flush!) Why each step?

First time: No cached information, must decode
Update: Store the computed target for reuse
Second time: BTB provides target before decode, avoiding penalty

Worked example Example 2: BTB Miss vs. Not-a-Branch

Scenario A - Instruction is a branch:

0x3000: jmp 0x4000  ; First time seeing this

BTB miss → Fetch from 0x3004(wrong!)
Decode discovers jump → Flush, fetch from 0x4000
Penalty: 2-3 cycles
Update BTB for next time

Scenario B - Instruction is NOT a branch:

0x3000: add r1, r2, r3  ; Regular instruction

BTB miss → Fetch from 0x3004 (correct!)
No penalty Why the difference?
BTB miss assumes "not a branch" → continues sequentially
If wrong, decode corrects it (with penalty)
If right (most instructions aren't branches), no harm done
Design philosophy: Optimize for the common case (non-branches)

Worked example Example 3: BTB Aliasing

Setup: BTB has 64 entries, indexed by PC[7:2]

0x1080: beq target_A  ; Index = 0b1000 = 0x20
0x1880: beq target_B  ; Index = 0b1000 = 0x20 (same!)

What happens:

Execute 0x1080 → BTB[0x20] = {tag: 0x1080, target: target_A}
Execute 0x1880 → BTB[0x20] = {tag: 0x1880, target: target_B} (overwrites!)
Re-execute 0x1080:
- Index 0x20 → Entry found
- Tag comparison: 0x1880 ≠ 0x1080 → Miss!
- Treated as first encounter →2-cycle penalty Why this happens:

Limited BTB size means collisions
Tag check prevents wrong target (correctness preserved)
But we lose the speed benefit (performance degradation)
Mitigation: Larger BTBs, better hash functions, set-associative BTBs

Common Mistakes

Integration with Other Components

BTB + Branch Predictor Cooperation

Formula Combined Prediction Decision

if (BTB_hit AND predictor_says_taken):
    next_PC = BTB.target
elif (BTB_hit AND predictor_says_not_taken):
    next_PC = PC + 4
else:  // BTB miss
    next_PC = PC + 4  // Assume not a branch or not taken

Modern optimization: Some designs embed simple predictors inside BTB entries (e.g., 2-bit counter per entry) to avoid a separate lookup.

Return Address Stack (RAS) vs. BTB

Function calls/returns are special:

Call: Target is in the instruction (BTB works great)
Return: Target changes every call (BTB would alias constantly)

Solution: Dedicated Return Address Stack (RAS) for returns, BTB for other branches. Many designs detect ret instructions and query the RAS instead of BTB.

Advanced: Set-Associative BTB

Active Recall Practice

Recall Feynman Technique: Explain to a 12-year-old

Imagine you're playing a video game where you keep jumping to different levels. Your character runs forward automatically, and when you hit a "jump portal," you teleport to a new level.

The problem: Your character is running so fast that by the time your brain sees the portal and decides where to jump, you've already run past it! You have to backup and try again (slow!).

The BTB is like a cheat sheet you write as you play: "Red portal → Level 5, Blue portal → Level 12." Now when you approach a portal, you can jump immediately because you already know where it goes from last time. No need to slow down and read the sign!

Sometimes your cheat sheet is wrong (the portal changed, or you wrote down the wrong level), and you jump to the wrong place. Then you have to go back, fix your notes, and try again. But most of the time, your cheat sheet is right, and you zoom through the game super fast!

Connections Branch Prediction Schemes: BTB provides the "where," predictors provide the "whether"

Pipeline Hazards: BTB mitigates control hazards
Instruction Cache (I-Cache): BTB lookup happens in parallel with I-cache access
Return Address Stack (RAS): Specialized BTB for function returns
Speculative Execution: BTB enables aggressive speculation on branch targets
Cache Organization: BTB uses similar set-associative structures
Branch Delay Slots: Older alternative to BTB (expose delay to software)

#flashcards/hardware

What does the Branch Target Buffer (BTB) store? :: The predicted target addresses of recently executed branch instructions (NOT whether the branch is taken - that's the predictor's job).

Why can't we just wait for the decode stage to get branch targets?

Decode happens1-2 cycles after fetch. Waiting creates a guaranteed penalty for every taken branch, even if perfectly predicted. BTB eliminates this wait.

How is a BTB indexed and accessed?

Indexed by lower bits of PC (e.g., bits [9:2] for 256entries). Tag compared with upper PC bits to verify correct branch. Target address returned on hit.

What happens on a BTB miss?

Processor assumes it's not a branch and fetches PC+4 (sequential). If it turns out to be a branch, the pipeline flushes after decode and the BTB is updated.

What is BTB aliasing and why does it occur?

When two different branches map to the same BTB index. Occurs because BTB has limited size and uses only some PC bits for indexing. Tag comparison detects aliasing (causing a miss), but performance degrades.

BTB hit + branch predictor says "not taken" → what happens?

Fetch from PC+4 (sequential). BTB target is ignored. Both conditions must be true: BTB hit AND predicted taken, to use the target.

How does a BTB reduce branch penalty from 2 cycles to 0?

BTB provides target address during the fetch stage (before decode), allowing immediate fetch from target when branch is predicted taken. No decode wait needed.

Why don't BTBs work well for function returns?

Returns have variable targets (depends on call site). Different calls push different return addresses, causing massive aliasing. Use dedicated Return Address Stack (RAS) instead.

What is a 2-way set-associative BTB?

Each BTB index has2 entries instead of 1. Allows 2 different branches with the same index to coexist. Reduces aliasing at the cost of 2 parallel tag comparisons.

Typical BTB size in modern processors?

512-2048 entries for L1 BTB (1-cycle access). Some have larger L2 BTB (4K-8K entries, 2+ cycles). Trade-off between hit rate and access latency.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

BTB ka basic idea samajhte hain. Jab processor instructions fetch karta hai, usko pata nahi hota ki yeh instruction ek branch hai ya nahi, aur agar branch hai to kahaan jump karna hai. Normally, yeh information decode stage mein milti hai, jo fetch ke1-2 cycles bad ati hai. Iska matlab hai ki har taken branch pe 2 cycles ka penalty lag jata hai, even if branch predictor sahi bhi predict kar le ki "haan, yeh branch lega."

BTB yeh problem solve karta hai ek simple chez se - yeh ek chhota cache hai jo recently executed branches ke target addresses store karta hai. Jab PC (program counter) ek instruction fetch karne jata hai, toh simultaneously BTB bhi check hota hai: "Kya is address pehle kabhi koi branch thi? Agar thi, toh uska target kya tha?" Agar BTB mein entry mil gayi (BTB hit), aur branch predictor bhi kehta hai "taken", toh processor turant us target se instructions fetch karne lag jaata hai - decode ka wait kiye bina. Yeh 0-cycle prediction deta hai for taken branches.

Lekin BTB perfect nahi hai. Agar naya branch hai (pehli baar execute ho raha), toh BTB miss hoga aur normal penalty lagega. Iske alawa, BTB mein limited entries hoti hain (512-2048 typically), toh agar bahut sare branches hain, toh aliasing problem ati hai - do alag branches same BTB entry use karenge aur ek dusre ko overwrite kar denge. Tab bhi performance thodi degrade hoti hai. But overall, modern processors mein BTB kafi effective hai - 20-30% IPC (instructions per cycle) improvement kar sakta hai branch-heavy code mein.

Samjhne ke liye yad rakho: BTB sirf "kahaan jana hai" bata hai, "jana hai ya nahi" yeh branch predictor decide karta hai. Dono sath mein kaam karte hain fetch stage mein hi, jisse pipeline smooth chalti hai aur stalls kam hote hain.