Exercises — Branch target buffer (BTB)

Answer: (b) — the target address, the "where to jump".

• (a) is the branch predictor's job (direction).
• (c) is computed in the execute stage.
• (d) requires decode, which is exactly the step the BTB lets us skip. The BTB answers only: "If taken, where?"

The lookup happens in the fetch stage, using the current program counter (PC — the address of the instruction we are fetching now). It runs in parallel with the Instruction Cache (I-Cache) access. Both are indexed by the same PC at the same time, so the target arrives before decode — no waiting.

• $256=2^8$, so we need 8 index bits.
• Instructions are 4 bytes = $2^2$, so PC bits $[1:0]$ are always $00$ for aligned instructions — they carry no information to distinguish branches. We skip them and use bits $[9:2]$.

Fraction of instructions that are taken branches: $0.20\times 0.60=0.12$ Each pays 2 cycles: $0.12\times 2=\boxed{0.24\text{ cycles/instruction lost}}$

Probability a taken branch escapes = $h\times a=0.90\times 0.95=0.855$. Probability it pays = $1-0.855=0.145$. Taken-branch fraction of all instructions = $0.12$ (from 2.1). $\text{Lost}=0.12\times 0.145\times 2=\boxed{0.0348\text{ cycles/instruction}}$

$\frac{0.24-0.0348}{0.24}=\frac{0.2052}{0.24}=0.855=\boxed{85.5\%}$ Notice this equals $h\times a$ exactly — the escape probability. That's not a coincidence: the only thing that changed is that each taken branch now escapes with probability $ha$.

Index = PC$[7:2]$ = bits 7 down to 2.

• 0x1080 = ...0001 0000 1000 0000. Bits $[7:2]$ = 100000 = 0x20.
• 0x1880 = ...0001 1000 1000 0000. Bits $[7:2]$ = 100000 = 0x20. Same index → they share one BTB slot. Alternating execution:

1. 0x1080 writes tag 0x1080 into slot 0x20.
2. 0x1880 overwrites it with tag 0x1880.
3. Back to 0x1080: index hits slot 0x20, but tag 0x1880 ≠ 0x1080 → miss, full penalty. Then it overwrites again. Every iteration both branches miss: 100% miss rate despite each being perfectly predictable. Correctness is preserved (the tag check refuses the wrong target), but speed collapses. See figure below.

Make the BTB 2-way set-associative: each index now holds 2 entries (see Cache Organization). Both 0x1080 and 0x1880 map to set 0x20 but live in different ways, so neither evicts the other. Result: after warm-up both hit every iteration — thrashing gone, no size increase needed (though total entries double for the same number of sets).

$\frac{1\times 3+999\times 0}{1000}=\frac{3}{1000}=\boxed{0.003\text{ cycles/execution}}$ The cold miss is a one-time cost amortised over many hits. This is why BTBs shine in loops: the expensive learning happens once, then thousands of free reuses follow.

A plain BTB stores one target per branch PC. But a single ret instruction jumps back to whichever caller invoked the function — a different address each time. The BTB keeps only the last return address, so the next return from a different caller mispredicts. Fix: the Return Address Stack (RAS) — a small hardware stack. Each call pushes its return address; each ret pops it. Because calls/returns nest like matched parentheses, the RAS gives the correct target even when it changes every time — something a single-target BTB entry cannot.

Escape probability $=ha$. Marginal gain from improving each factor:

• Improving $h$ from 0.99: at most $+0.01$ possible → escape rises by $\le a\times 0.01=0.008$.
• Improving $a$ from 0.80: room up to $+0.20$ → escape rises by up to $h\times 0.20=0.198$. $a$ is the bottleneck — it's far from 1 while $h$ is nearly saturated. Spend on the predictor. General rule: invest in whichever factor is furthest below 1, because $ha$ is limited by its weaker term.

The delay slot hides one cycle of branch latency by always running the next sequential instruction — useful work regardless of direction. But if the branch target needs more than one cycle to become known (deep pipeline, decode + target calc = 2 cycles), a single delay slot cannot cover it. A BTB supplies the target in the fetch cycle, covering the remaining gap. So yes — the BTB still helps by removing the remaining penalty the fixed-size delay slot can't hide.

(a) Taken-branch fraction $=0.25\times 0.70=0.175$. (b) Escape $=ha=0.92\times 0.90=0.828$; pay $=1-0.828=0.172$. (c) Added CPI $=0.175\times 0.172\times 4=0.1204$. (d) Final CPI $=1.0+0.1204=\boxed{1.1204}$.

Added CPI $=0.175\times (1-ha)\times 4=0.05$. $0.7\times (1-0.92a)=0.05⟹1-0.92a=\frac{0.05}{0.7}=0.0714\dots$ $0.92a=0.9286⟹a=\frac{0.9286}{0.92}=\boxed{1.0093}$ Since $a>1$ is impossible, this target is unreachable with $h=0.92$ alone. To hit 0.05 you must also raise $h$ (or lower $P$). This is the mastery lesson: the product $ha$ caps how low the penalty can go, and no single knob past its ceiling of 1 can rescue an over-ambitious target.

(a) No BTB: added CPI $=0.175\times 1.0\times 4=0.70$. (b) With BTB (from 5.1c): added CPI $=0.1204$. Penalty CPI removed $=0.70-0.1204=0.5796$. Fraction removed $=0.5796/0.70=0.828=\boxed{82.8\%}$ — again exactly $ha$, the escape probability. The whole benefit of the BTB collapses to that one product.