Branch target buffer (BTB): Visual walkthrough — Hardware deep dive

This page rebuilds the parent result — why a Branch Target Buffer turns a 1–2 cycle branch penalty into a 0 cycle penalty — from the ground up, one picture per step. We assume you know nothing about pipelines yet. Every word is earned before it is used.

New here? Start at the Branch target buffer (BTB) parent note, or read it in Hinglish.

Step 1 — What is a "PC" and why do instructions come in a line?

WHAT. A processor runs a program: a long list of tiny commands called instructions, stored in memory. Each instruction sits at a numbered slot called an address. The processor keeps one number that says "which instruction am I fetching right now" — that number is the Program Counter (PC).

WHY. Everything about branches is a question of "what number do I put in the PC next?" So before we can talk about jumping, we must picture the PC crawling forward.

PICTURE. Look at the figure. Instructions live at addresses 0x1000, 0x1004, 0x1008, … — four apart because each instruction is 4 bytes wide. The default move is:

$PC_{next} = where I am now PC + one instruction wide 4$

$PC$ — current address being fetched.
$+ 4$ — step to the very next instruction in line (the "boring" case).

Step 2 — A branch is an instruction that changes the PC to somewhere far away

WHAT. A branch is a special instruction that says "instead of PC+4, jump to some target address." A conditional branch like beq 0x2000 ("branch if equal") jumps to 0x2000 only if a condition holds; otherwise it falls through to PC+4.

WHY. This is the whole problem. The next-PC is no longer obvious — it depends on (a) is this even a branch? and (b) is it taken? and (c) where does it go? Three unknowns, and the processor wants the answer now.

PICTURE. The red arrow is the "taken" path leaping from 0x1004 to 0x2000. The grey arrow is the "not taken" fall-through to 0x1008.

$PC_{next} = {target PC + 4 if branch taken if not taken$

$target$ — the far-away address the branch jumps to (e.g. 0x2000).
The cases brace — "pick one line depending on the condition."

Step 3 — The pipeline: the processor works on several instructions at once

WHAT. A modern CPU is a pipeline — an assembly line. While one instruction is being executed, the next is being decoded, and the one after is being fetched. Call these stages Fetch → Decode → Execute.

WHY. This is exactly why branches hurt. The PC must produce the next address in the Fetch stage — but the fact that "this is a branch and here is its target" is only discovered later, in Decode. There is a gap in time between wanting the answer and knowing it.

PICTURE. Three coloured lanes moving left to right. Fetch is stage 0, Decode is one cycle later, Execute two cycles later. The "I want the target" moment (Fetch) and the "I computed the target" moment (Decode) are separated by a wall.

$cycle 0 Fetch \to cycle 1 : target known here Decode \to cycle 2 Execute$

See Pipeline Hazards for why this gap is a "control hazard."

Step 4 — Without a BTB: the wasted cycles (the penalty)

WHAT. Follow a taken branch through the pipeline with no BTB. In cycle 0 we fetch the branch, but the PC has no idea it's a branch, so it fetches PC+4 next (the wrong instruction). Only in Decode do we learn the target. We must flush (throw away) the wrongly-fetched instructions and re-fetch from the target.

WHY. Those thrown-away cycles are pure waste — the branch penalty. This is the number the BTB will attack. Counting them from the picture is the derivation.

PICTURE. Cycle 0 fetches the branch; cycle 1 fetched the wrong PC+4 (crossed out); at cycle 1 Decode reveals the target; cycle 2 finally fetches the correct target. Count the crossed-out slots.

$Penalty_{no BTB} = time to learn "it’s a branch" decode latency + compute where target calc = 1 - 2 cycles$

Each term is one wasted pipeline slot.
With deeper pipelines this grows — but 1–2 is the classic number.

Step 5 — The BTB: a notebook that remembers "last time, this PC jumped to here"

WHAT. A Branch Target Buffer is a small cache keyed by the branch's PC. Each entry stores a tag (upper PC bits, to prove it's the right branch) and a target (where that branch went last time).

WHY. If we already saw this branch once and recorded its target, then next time we can look it up in the Fetch stage — no waiting for Decode. That's the trick: replace a computation (slow, in Decode) with a memory lookup (fast, in Fetch).

PICTURE. A table. We split the PC into two coloured slices: the low bits pick the row (index), the high bits are checked against the stored tag. If the tag matches, the stored target is served instantly.

$index = PC [n : m], hit = (BTB.tag == PC [upper]), PC_{next} = BTB.target$

$PC [n : m]$ — the middle bits of the PC; small enough to name a row quickly.
$tag$ — the high bits; the proof of identity so we don't confuse two branches.
$==$ — "are these bit-strings identical?"
$BTB.target$ — the remembered destination, served in the same cycle.

Step 6 — With a BTB: the penalty collapses to zero

WHAT. Replay the taken branch, now with a BTB hit and a correct "taken" prediction. In cycle 0 we fetch the branch and the BTB hands us the target in parallel. So cycle 1 already fetches the target — no wrong PC+4, nothing to flush.

WHY. Compare directly to Step 4. The wasted slots vanish because the target arrived early. That difference is the saving.

PICTURE. Same pipeline as Step 4, but the crossed-out slot is gone; the target flows in cycle 1. Set the two pictures side by side in your head.

$Penalty_{with BTB} = 0 (if BTB hits and prediction correct)$

$Δ = Penalty_{no BTB} - Penalty_{with BTB} = (1 - 2) - 0 = 1 - 2 cycles saved$

$Δ$ — cycles rescued per correctly-predicted taken branch.

Solve

A BTB hit + correct "taken" prediction gives a 0-cycle penalty; the saving is the 1–2 cycles you would have wasted without it.

Step 7 — Edge case: the cold miss (first time we ever see this branch)

WHAT. The very first time a branch runs, the BTB has never recorded it. Lookup misses. So the CPU assumes "not a branch, use PC+4," fetches straight ahead, and only Decode reveals the truth — full penalty, then the BTB is updated for next time.

WHY. You cannot remember what you have never seen. This case must exist; ignoring it would be a lie. Crucially, a miss defaults to "keep going straight," which is free for the huge majority of instructions that are not branches (Example 2 in the parent).

PICTURE. Two lanes. Top lane: a real branch missing → wrong fetch → flush → BTB gets written (magenta write-arrow). Bottom lane: an ordinary add missing → PC+4 was right all along → zero cost.

$P (first visit) : penalty = 1 - 2 cycles, then BTB [index] \leftarrow {tag, target}$

$\leftarrow$ — "store into"; the CPU writes the just-computed target for reuse.

Step 8 — Edge case: aliasing (two branches fight over one row)

WHAT. The BTB has limited rows, chosen by the low PC bits only. Two different branches whose low bits match land on the same row. The second one overwrites the first. When the first returns, the row is occupied by a stranger — the tag check fails → miss → penalty again.

WHY. This shows the tag isn't decoration: it guarantees correctness (we never jump to the wrong target), while accepting a performance loss. Every real BTB lives with this trade-off.

PICTURE. Two branches 0x1080 and 0x1880 both index to row 0x20. Watch the row's contents get overwritten (violet), then the tag mismatch (red X) on re-entry.

$index (0 x 1080) = index (0 x 1880) = 0 x 20 \Rightarrow collision; tag (0 x 1880) \neq = tag (0 x 1080) \Rightarrow miss$

The one-picture summary

The whole story is: the answer is born in Decode, but needed in Fetch — the BTB remembers it so it arrives early. This last figure lays the no-BTB timeline over the with-BTB timeline and marks the rescued cycles in bright orange.

Recall Feynman retelling — say it back in plain words

Imagine reading a choose-your-own-adventure book. A normal predictor tells you "yes, you'll make a choice on this page," but you still have to read the page to find the page number to flip to — that reading is the Decode delay, and flipping late means you already started the wrong page and must tear it out (the flush penalty). The BTB is a sticky note in the margin: "last time, this choice sent you to page 47." Because the note is right there where your eyes land (the Fetch stage), you flip immediately — no reading, no torn pages. That saves the 1–2 wasted turns. Two honest catches: the first time on a page there's no note yet (cold miss — you pay full price and then write the note). And if two different pages share the same margin spot (aliasing), the newer note erases the older one; the tag ("is this really page 12's note?") stops you jumping somewhere wrong, but you lose the shortcut. The margin note never decides whether you turn — that's the predictor. It only ever whispers where.

Prerequisites and neighbours: Pipeline Hazards · Instruction Cache (I-Cache) · Cache Organization · Speculative Execution · Return Address Stack (RAS) · Branch Delay Slots · parent Branch target buffer (BTB).