Branch target buffer (BTB): Worked examples — Hardware deep dive

This page is a drill. The parent note explained what a BTB is; here we throw every kind of situation at one and work it out by hand. Before we start, one reminder in plain words so nothing later is a surprise.

Definition Index and tag — how a PC is split

A BTB is a small cache, so it splits every PC into two pieces of bits. Suppose the BTB has $64$ entries and instructions are $4$ bytes wide (so the lowest $2$ bits of any PC are always $0$ ).

The index picks which slot to look in. With $64$ slots we need $lo g_{2} 64 = 6$ index bits, taken just above the 2 alignment bits: bits [7:2] of the PC.
The tag is the rest of the PC's bits above the index — bits [31:8] here, i.e. $32 - 8 = 24$ tag bits. It is stored inside the slot so we can later confirm "yes, this slot really belongs to my branch, not a different one that happened to land in the same slot."

In one line: $PC = [tag ∣ index ∣ 2 alignment bits]$ . A hit requires both the slot to be occupied and its stored tag to equal the tag of the current PC. We use this split concretely in Example 5.

We also lean on prerequisite ideas: Pipeline Hazards (why a wrong PC costs cycles), the Instruction Cache (I-Cache) (fetched in parallel with the BTB), the Return Address Stack (RAS) and Speculative Execution (which the BTB feeds), and Cache Organization (why aliasing happens). Hinglish version: 5.3.09 Branch target buffer (BTB) (Hinglish).

The scenario matrix

A BTB is a tiny yes/where machine. Only a few dimensions decide the outcome, so we can enumerate every case class. Each row is a cell we must cover with at least one worked example.

Cell	Is it a branch?	In BTB? (hit/miss)	Predictor says	Prediction correct?	Outcome we must show
A	yes	miss (cold, first ever)	—	—	full penalty, then BTB updated
B	yes	hit	taken	correct	0-cycle, the happy path
C	yes	hit	not taken	correct	fall through to $PC + 4$ , 0 penalty
D	yes	hit	taken	wrong (branch not taken)	mispredict flush
E	yes	hit, wrong tag (aliasing)	—	—	forced miss → penalty
F	no (plain add)	miss	—	—	$PC + 4$ correct, no harm
G	yes, indirect (target changes)	hit but stale target	taken	target wrong	correct direction, wrong address
H	zero/degenerate: branch to self ( $PC + 0$ ) / empty BTB	—	—	—	limiting behaviour
W	real-world word problem	mix	mix	mix	compute average penalty
X	exam twist	hit	taken	correct but BTB late by 1 cycle	"bubble" even on a hit

The eight lettered cells are the logic cases; W is the throughput problem; X is the gotcha. The examples below hit all of them.

Example 1 — Cell A: cold miss, first sighting of a branch

Worked example A branch nobody has met yet

0x1004: beq 0x2000    ; taken this time
0x1008: add r3,r4,r5
0x2000: mul r6,r7,r8  ; target

The BTB is empty. Trace what happens the first time.

Forecast: guess the penalty in cycles before reading on. (Hint: the machine does not yet know beq is a branch.)

Cycle 0 — PC = 0x1004, fetch beq. BTB lookup runs in parallel → miss.
- Why this step? On a miss the BTB's default answer is "not a branch," so it lets fetch continue sequentially.
Cycle 1 — PC = 0x1008, fetch add (the $PC + 4$ guess). Meanwhile beq reaches decode and reveals: branch, target 0x2000.
- Why this step? Decode is the earliest moment the hardware can compute a target for an unseen branch.
Cycle 1 (end) — the add we fetched is on the wrong path. Flush it.
- Why this step? We speculatively fetched down $PC + 4$ ; since the branch is taken, that work is void — a control hazard.
Cycle 2 — fetch from 0x2000. Write the BTB: entry for 0x1004 → 0x2000.
- Why this step? Storing the target now buys a 0-cycle jump next time.

Penalty = 2 cycles (the wasted fetch at step 2 + the redirect). See the timeline.

What to see in the figure: read it left-to-right by cycle. The blue boxes on the top row are useful fetches; the orange box at cycle 1 is the add we fetched on the wrong guess; the red arrow shows that orange box being flushed. The gap between the blue beq fetch (cycle 0) and the green target fetch (cycle 2) is exactly the 2-cycle hole the miss punched into the pipeline.

Verify: cycles from fetching the branch to fetching the correct target = cycle 2 − cycle 0 = 2. A same-cycle machine would have redirected in cycle 0, so the delta = 2 cycles. ✓ (checked in VERIFY)

Example 2 — Cell B: the happy path (0-cycle taken branch)

Worked example Second time around — BTB hit, predicted taken, correct

Same beq 0x2000, now already in the BTB, and the predictor's history says taken.

Forecast: how many stall cycles? Compare to Example 1.

Cycle 0 — PC = 0x1004, fetch beq. BTB lookup → hit, tag matches, target 0x2000 returned this same cycle.
- Why this step? The BTB read finishes inside the fetch cycle (it is a small cache, read in parallel with the Instruction Cache (I-Cache)).
Cycle 0 — predictor (a separate 2-bit counter, Speculative Execution) says taken. So Next PC ← 0x2000, not 0x1008.
- Why this step? The BTB supplies where, the predictor supplies whether. Both answers arrive before decode.
Cycle 1 — fetch 0x2000. No add was ever fetched; nothing to flush.
- Why this step? Because the redirect happened during cycle 0, the very next fetch is already correct.

Penalty = 0 cycles. This is the entire payoff of the BTB.

Verify: cycle(correct target fetched) − cycle(branch fetched) = 1 − 0 = 1, which is the normal pipeline spacing (one fetch per cycle), i.e. no extra bubble. Savings vs. Example 1 = 2 − 0 = 2 cycles. ✓

Example 3 — Cell C: hit but predictor says not taken

Example 4 — Cell D: hit, predicted taken, but branch is not taken

Worked example Wrong direction — a real misprediction

Same setup as Example 2 (predictor says taken) but the actual data makes the branch fall through.

Forecast: where is the mistake discovered, and how many cycles lost?

First fix the pipeline geometry so the timing is unambiguous. Say the front-end has exactly three stages the branch passes through in order: fetch (stage 1), decode (stage 2), execute (stage 3). A branch's direction (taken or not) is only known when it executes. So the number of speculative fetches we make before the truth is known equals the number of stages between fetch and execute.

Cycle 0 — BTB hit, predictor "taken" → Next PC ← 0x2000 speculatively.
Cycle 1 — fetch the instruction at 0x2000 speculatively. This is the first wrong-path fetch.
- Why this step? Speculative Execution presses ahead on the predicted path; it cannot yet know the guess is wrong.
Cycle 2 — the beq reaches execute, compares r1,r2, finds not equal → branch not taken. Everything fetched from 0x2000 was wrong.
- Why this step? Direction is only verified at execute (stage 3); the predictor was a guess.
Cycle 2 (end) — flush the wrong-path fetches, restart fetch at 0x1008.

Penalty = number of stages between fetch and execute − 0 useful = 2 cycles. Concretely: from the branch fetch at cycle 0 to the corrected fetch, the pipeline discards the work done in cycles 1 and 2 → 2 cycles of squashed front-end work.

Note: the BTB was not at fault here — its stored target 0x2000 was correct as a target. The predictor guessed the wrong direction. BTB good, predictor bad.

Verify: the misprediction penalty = (execute stage index) − (fetch stage index) = 3 − 1 = 2 cycles of front-end work discarded. ✓

Example 5 — Cell E: aliasing (right index, wrong tag)

Worked example Two branches collide in the same BTB slot

BTB has 64 entries, so (from the index/tag definition above) the index is PC bits [7:2] and the tag is bits [31:8]. Two branches:

0x1080: beq target_A
0x1880: beq target_B

Forecast: will re-executing 0x1080 after 0x1880 be a hit or a miss?

Compute the index of each. The index is "which of the 64 slots," so we need PC bits [7:2]. There is a clean arithmetic recipe for "grab bits [7:2]":
- First drop the low 2 alignment bits by integer-dividing the address by $4$ . "Integer division" means divide and throw away any remainder — written $⌊ x /4 ⌋$ , where the notation $⌊ \cdot ⌋$ (called floor) means "round down to the nearest whole number." We do this because those 2 bits are always $0$ and carry no information.
- Then keep only the lowest $6$ bits of the result, because $2^{6} = 64$ and there are only $64$ slots. "Keep the lowest 6 bits" is exactly "the remainder after dividing by $64$ ," written $(\dots) mod 64$ . The symbol $mod$ (modulo) means "the remainder left over" — e.g. $70 mod 64 = 6$ . We use it because a slot number must wrap around from $63$ back to $0$ . $index = ⌊ \frac{PC}{4} ⌋ mod 64$
- For 0x1080: $⌊ 0x1080 /4 ⌋ = 0x420 = 1056$ , and $1056 mod 64 = 32$ .
- For 0x1880: $⌊ 0x1880 /4 ⌋ = 0x620 = 1568$ , and $1568 mod 64 = 32$ .
- Why this step? Same index ⇒ same physical slot ⇒ the two branches fight over one entry.
Run 0x1080: slot 32 ← {tag = bits[31:8] of 0x1080, target A}.
Run 0x1880: slot 32 ← {tag of 0x1880, target B}. Overwrites A (its tag differs, but the slot is the same).
Re-run 0x1080: index 32 → entry present, but stored tag(0x1880) ≠ tag(0x1080) → miss.
- Why this step? The tag check protects correctness (we never jump to B's target for A) at the cost of a lost hit.

Result: a forced miss → back to the 2-cycle cold-miss penalty of Example 1. Mitigation: bigger BTB or set-associativity.

What to see in the figure: both PCs (blue 0x1080, orange 0x1880) have arrows that funnel into the same box — BTB slot 32 — which is the whole point: the index collapses them together. The box shows the survivor (tag=0x1880, target B). The red arrow is the later re-run of 0x1080 bouncing off that box because the tags do not match: correctness saved, speed lost.

Verify: both indices equal 32, and tags differ ⇒ conflict. ✓

Example 6 — Cell F: not a branch at all (the common case wins)

Worked example Plain arithmetic, BTB miss, zero harm

0x3000: add r1,r2,r3   ; not a branch, never in BTB

Forecast: does a BTB miss ever hurt a non-branch?

Cycle 0 — fetch add, BTB miss. Default next PC ← 0x3000 + 4 = 0x3004.
- Why this step? Miss means "assume sequential," which is exactly right for non-branches.
Cycle 1 — fetch 0x3004, the true next instruction.
Decode confirms add is not a branch. No correction needed.

Penalty = 0. Most instructions are not branches, so the miss default is tuned to be free here.

Verify: used next-PC 0x3004 equals the natural sequential PC. Match ⇒ 0 penalty. ✓

Example 7 — Cell G: indirect branch with a stale target

Worked example Right direction, wrong address (the indirect trap)

An indirect branch computes its target from a register at runtime:

0x5000: jmp [r9]     ; last time r9 = 0x6000, this time r9 = 0x7000

The BTB stored 0x5000 → 0x6000 from last time. r9 now holds 0x7000.

Forecast: BTB hits and predictor says "always taken." Is the fetched target correct?

Cycle 0 — BTB hit, target 0x6000 returned; jump is unconditional so direction is trivially "taken."
Cycle 1.. — speculatively fetch from 0x6000.
Execute — the real target [r9] = 0x7000 is computed. 0x7000 ≠ 0x6000 → target misprediction.
- Why this step? The BTB caches a past target; an indirect branch may pick a different one each time. Direction was right, address was stale.
Flush, refetch 0x7000, and update BTB 0x5000 → 0x7000.

Penalty = redirect depth (≈ 2 cycles) every time the target changes. This is why real cores add indirect-target predictors on top of the BTB; a plain BTB thrashes here. (Function returns dodge this by using the Return Address Stack (RAS) instead.)

Verify: stored target 0x6000 ≠ actual 0x7000 ⇒ mispredict. ✓

Example 8 — Cell H: degenerate / limiting inputs

Worked example Branch to itself, and the empty BTB

Two edge cases.

(H1) Self-branch: 0x8000: jmp 0x8000 (an infinite loop / spin).

First run: cold miss, decode finds target 0x8000, BTB ← 0x8000 → 0x8000.
Every later run: BTB hit, Next PC ← 0x8000 in the same cycle ⇒ the loop spins at 1 fetch/cycle with 0 penalty.
- Why this matters? The "target" equals the branch PC itself — a valid, non-pathological entry. Displacement = target − (PC+4) = 0x8000 − 0x8004 = −4, a backward branch, exactly what loops look like.

(H2) Empty / just-flushed BTB (cold start): every branch is a miss until it has executed once. So the first pass of any program pays cold-miss penalties on all its branches; steady state is much cheaper. This is the warm-up cost.

Verify: self-branch displacement = 0x8000 − 0x8004 = −4 (backward). And a self-branch's used next-PC equals its own PC. ✓

Example 9 — Cell W: real-world throughput problem

Worked example Average cycles lost per instruction

A program: 20% of instructions are branches; 60% of branches are taken; the BTB delivers a correct target on 90% of branch fetches (so 10% miss/alias/mispredict); each failure costs 2 penalty cycles.

Forecast: guess the cycles-per-instruction (CPI) penalty before computing.

Fraction of instructions that are taken branches: $0.20 \times 0.60 = 0.12$
- Why? Only taken branches need the BTB's redirect; not-taken ones fall through for free (Cell C).
Of those, the fraction that fail (miss/alias/mispredict): $0.10$ . $0.12 \times 0.10 = 0.012$
Multiply by penalty cycles: $CPI penalty = 0.012 \times 2 = 0.024 cycles/instruction$

Compare with no BTB (every taken branch pays the 2-cycle decode wait): $0.12 \times 1.0 \times 2 = 0.24 cycles/instruction .$

Verify: with-BTB penalty $= 0.024$ ; without $= 0.24$ ; the BTB removes $0.24 - 0.024 = 0.216$ CPI, a 10× reduction of branch penalty. ✓

Example 10 — Cell X: the exam twist (a bubble even on a hit)

Worked example "0-cycle" is only true if the BTB read finishes in time

Some designs cannot read the BTB and redirect fetch within a single cycle — the BTB result arrives one cycle late (a 2-cycle BTB access). In this example everything is a correct, predicted-taken hit; the only villain is BTB latency.

0x1004: beq 0x2000, in the BTB, predictor correctly says taken.

Forecast: if a perfect prediction still can't turn fetch in one cycle, what is the penalty?

Cycle 0 — fetch beq at 0x1004. The BTB lookup starts but its answer is not ready this cycle. With nothing to redirect fetch, the front-end takes the default → Next PC ← 0x1008.
- Why this step? A 2-cycle BTB cannot influence the very next fetch; fetch must guess something, and the default is sequential.
Cycle 1 — fetch 0x1008 (wrong path). Meanwhile the BTB answer lands: target 0x2000, predicted taken.
- Why this step? The stored, correct answer arrives exactly one cycle after the branch fetch — one fetch too late.
Cycle 1 (end) — the 0x1008 fetch is on the wrong path. Flush that single fetch, redirect fetch to 0x2000.
- Why this step? The prediction was right, so as soon as the late target appears we correct course — but one wasted fetch has already happened.
Cycle 2 — fetch 0x2000, the true target.

Penalty = 1 cycle — a single "bubble," even though the prediction was perfect. Compare the cells: a single-cycle BTB (Example 2) gives $latency - 1 = 1 - 1 = 0$ ; this two-cycle BTB gives $2 - 1 = 1$ . Moral for the exam: BTB latency, not just accuracy, sets the best-case penalty.

Verify: penalty = BTB-latency − 1 = 2 − 1 = 1 cycle; and a single-cycle BTB gives 1 − 1 = 0, matching Example 2. ✓

Recall Quick self-test

Cell B best-case penalty with a single-cycle BTB ::: 0 cycles A BTB hit with predictor "not taken" uses which next PC ::: $PC + 4$ (target ignored) Two branches share a BTB slot but differ in tag — hit or miss ::: miss (aliasing) Indirect branch, correct direction, stale target — whose fault ::: the BTB's cached target is stale (needs an indirect predictor) With 20% branches, 60% taken, 10% failure, 2-cycle penalty, CPI cost ::: 0.024 cycles/instruction A 2-cycle-latency BTB, perfectly correct hit — penalty ::: 1 cycle (latency − 1)