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

States $10$ and $11$ predict Taken. States $00$ and $01$ predict Not-taken. Why the top bit: the counter counts confidence in "taken" from $0$ (never) up to $3$ (always). Written in binary, $2$ = 10 and $3$ = 11 — both have a leading $1$; $0$ = 00 and $1$ = 01 — both have a leading $0$. So the most significant (top) bit is exactly "is the count $\ge 2$?", which is exactly "do we lean Taken?". Reading one bit is free in hardware, which is the whole point.

(a) Taken. Backward jump = loop bottom returning to the top → taken almost every iteration. (b) Not-taken. Forward jump that skips code = usually an if/error path that doesn't fire → falling through is the right bet.

• Direction → the 2-bit saturating counter (the prediction bits).
• Target address in IF → the BTB (Branch Target Buffer). They are two different answers to two different questions; you need both for a taken branch to cost zero cycles.

Plug into $\text{CPI}=1+fpc$: $\text{CPI}=1+(0.2)(0.05)(3)=1+0.03=\boxed{1.03}$ What we did: multiplied the three independent quantities (how often a branch, how often wrong, cost each time), then added to the ideal $1$. Branches cost only $3\%$ overhead.

$\text{CPI}=1+(0.2)(0.45)(3)=1+0.27=\boxed{1.27}$ Slowdown vs $1.03$: $\frac{1.27-1.03}{1.03}=\frac{0.24}{1.03}\approx 0.233=\boxed{23.3\%}$ What we did: the only thing that changed is $p$ (accuracy). A worse predictor turned a $3\%$ tax into a $27\%$ tax — a $23.3\%$ real slowdown. This is the 80/20 payoff of good prediction.

BTFNT predicts the backward branch Taken every time. The branch is taken on iterations $1$ through $7$ (returning to the top) and not-taken once — the exit (iteration $8$).

• Correct on $7$ taken outcomes.
• Wrong on the $1$ exit. $\text{mispredictions}=\boxed{1}$ Why: the loop exit is the single event a static scheme can never anticipate — it's the irreducible cost.

A 1-bit predictor stores exactly one bit and simply copies the last outcome as its next prediction. We do not need to assume any particular starting value: after the loop's first pass the bit is guaranteed to be left in a definite state, so we analyse the steady state — how every pass behaves once the loop is already running repeatedly.

Why the steady-state entry bit is "Taken": each pass ends with the exit outcome Not-taken, which sets the bit to Not-taken; but then the exit is itself the last event before the next entry... so let us trace carefully. During a pass the outcomes are $N-1$ Takens followed by $1$ Not-taken. The final Taken (iteration $N-1$) sets the bit to Taken, and the exit (iteration $N$, Not-taken) then sets it to Not-taken. So at the moment the loop re-enters, the bit is Not-taken — carried in from the previous exit. Trace one steady-state pass with that carried-in bit:

• Re-entry, iteration $1$: outcome Taken, but bit says Not-taken (carried from last exit) → ✗ (miss #1). Bit flips to Taken.
• Iterations $2\dots N-1$: outcome Taken, bit says Taken → ✓. Bit stays Taken.
• Iteration $N$ (exit): outcome Not-taken, bit still says Taken → ✗ (miss #2). Bit flips to Not-taken, ready to poison the next re-entry.

The two misses are the re-entry and the exit, and this pattern repeats identically every pass — that is what "steady state" guarantees.

Figure description (for text-only readers): the figure shows eight branch executions in a row for a loop of length $4$ run twice: outcomes T, T, T, N (exit) then T, T, T, N (exit). Each dot is coloured green when the prediction was correct and red when it was a miss. Above each dot is the prediction the 1-bit bit made (pred T/pred N); below is OK or MISS. A dashed yellow line marks where the loop re-enters. The steady-state pattern shows two red dots per pass — one at the exit and one at the following re-entry — because the exit's Not-taken poisons the bit for the next entry.

Root cause: the 1-bit predictor changes its mind after one surprise, so the exit "poisons" its memory for the next entry. That is exactly the flaw the second bit fixes.

On Taken → increment (saturate at $11$). On Not-taken → decrement. Top bit is the prediction; recall $10$ and $11$ both predict Taken.

• Iterations $1\dots N-1$: Taken, state $11$, predict Taken → ✓. Stays $11$ (already saturated).
• Iteration $N$ (exit): Not-taken, state $11$ predicts Taken → ✗ (the one miss). State decrements $11\to 10$.
• Next entry, iteration $1$: Taken, state $10$ still predicts Taken → ✓. Increments $10\to 11$.

The only miss is the exit; re-entry is now correct because $10$ hasn't crossed below the top-bit threshold.

Figure description (for text-only readers): the figure plots the counter's numeric state (0=00, 1=01, 2=10, 3=11) across the same eight executions T, T, T, N, T, T, T, N. The upper band (states 10/11) is shaded green and labelled "predict TAKEN"; the lower band (00/01) is shaded red and labelled "predict NOT-taken", with a dotted threshold line between them. The counter sits at 11 through the three taken iterations, dips to 10 on the exit (the single red MISS), then climbs straight back to 11 — never crossing into the red "predict NOT-taken" band, so re-entry stays correct.

Conclusion: 2-bit halves the loop misprediction count ($2\to 1$) purely by requiring two surprises to flip.

1-bit: ${\text{CPI}}_1=1+(0.25)(0.10)(4)=1+0.10=1.10$. 2-bit: ${\text{CPI}}_2=1+(0.25)(0.05)(4)=1+0.05=1.05$. Speedup (time is proportional to CPI): $\text{speedup}=\frac{{\text{CPI}}_1}{{\text{CPI}}_2}=\frac{1.10}{1.05}\approx 1.0476=\boxed{4.76\%}$ What we did: only $p$ differs; a $2\times$ better accuracy shaved the branch tax roughly in half, giving ~$4.76\%$ more throughput.

Execution time $\propto \text{CPI}\times \text{cycle time}=\text{CPI}/\text{frequency}$. Convention: we normalize the shallow machine's clock to $1$ unit — i.e. set shallow frequency $=1$ so its cycle time is $1$ time-unit. The deep machine is then $1.4\times$ faster clock, so frequency $=1.4$ (its cycle time is $1/1.4$ time-units). All "time" numbers below are in these shallow-cycle time-units, so they are directly comparable.

• Shallow: $\text{CPI}=1+(0.2)(0.04)(2)=1+0.016=1.016$. Time $\propto 1.016/1=1.016$.
• Deep: $\text{CPI}=1+(0.2)(0.04)(5)=1+0.040=1.040$. Time $\propto 1.040/1.4\approx 0.7429$.

Speedup of deep over shallow: $\frac{1.016}{0.7429}\approx 1.368=\boxed{36.8\%\text{ faster}}$ What we did: deeper pipeline raises $c$ (more CPI) but the higher clock more than compensates given good prediction. The whole strategy only works because $p$ stayed low — connect this to why Pipeline Depth and CPI makes prediction accuracy critical.

We need deep time = shallow time (both in the same shallow-cycle time-units from 4.1): $\frac{1+f{p}^{\star }c}{1.4}=1.016$ Multiply both sides by $1.4$: $1+f{p}^{\star }c=1.016\times 1.4=1.4224$ Now substitute $f=0.2$ and $c=5$. Note the key simplification: the coefficient of $p^{\star }$ is $f\cdot c=(0.2)(5)=1$ exactly, so the whole penalty term collapses to just $p^{\star }$: $1+(0.2)(5)p^{\star }=1+1\cdot p^{\star }=1+p^{\star }=1.4224$ $p^{\star }=1.4224-1=0.4224$ $\boxed{p^{\star }\approx 0.4224(42.24\%)}$ Interpretation: the deep pipeline only loses if its predictor is worse than ~$42\%$ mispredictions — catastrophically bad. Any realistic predictor keeps the deep design ahead.

Step 0 — what is a "dynamic execution", and what will we weight by? A static branch is one line in the source code; the $70\%/30\%$ split counts these static lines. But CPI is charged every time a branch actually runs at runtime — a dynamic execution. A loop branch written once runs $10$ times per loop entry; a data branch runs once. So to average miss rates correctly we must weight each class by its dynamic-execution weight = (its share of static branches) × (how many times each runs). We call this weight a share unit: it is simply "expected number of dynamic branch executions contributed by this class, per unit of program", and it is what the misprediction penalty is actually charged against.

Step 1 — per-class miss rate. Per loop entry: $10$ dynamic branch executions, $1$ mispredict → loop miss rate $=1/10=0.10$. Data branches: miss rate $=0.50$.

Step 2 — dynamic-execution share units.

• loops: $0.70\times 10=7.0$ share units
• data: $0.30\times 1=0.30$ share units
• total $=7.0+0.30=7.30$ share units.

Step 3 — frequency-weighted overall miss rate. Weight each class's miss rate by its share units (total mispredictions ÷ total dynamic executions): $p=\frac{(\text{loop units}\times \text{loop rate})+(\text{data units}\times \text{data rate})}{\text{total units}}=\frac{7.0\times 0.10+0.30\times 0.50}{7.30}$ $p=\frac{0.70+0.15}{7.30}=\frac{0.85}{7.30}\approx 0.11644$ $\boxed{p\approx 0.1164(11.64\%)}$

Step 4 — CPI. Plug $p$ into the master formula with $f=0.15$, $c=4$: $\text{CPI}=1+f\cdot p\cdot c=1+(0.15)(0.11644)(4)=1+0.069863\approx \boxed{1.0699}$ What we did: the mastery move is realising loop branches execute more often than data branches, so they dominate the dynamic mix. A share-unit (frequency-weighted) average — not a simple $0.70/0.30$ average — is required.

No change — CPI stays $\approx 1.0699$. The formula $\text{CPI}=1+f\cdot p\cdot c$ already assumes correctly-predicted branches cost $0$; the only cost baked in is the misprediction penalty $c$. The BTB is precisely the hardware that delivers that "correct taken = 0 cycles" assumption by supplying the target during IF.

• BTB fixes: the bubble on a correctly predicted taken branch (turns it from $1$ cycle to $0$).
• BTB does NOT fix: mispredictions. Wrong direction still flushes $c$ instructions regardless of how fast the target was fetched.

So the BTB is baked into the baseline of this model; our $p$ and $c$ already reflect a world with it. Removing the BTB would add a per-taken-branch penalty term — a different, larger CPI. This ties into Speculative Execution: the BTB lets fetch keep running speculatively past a taken branch with no stall.