Exercises — Branch prediction (static and dynamic)

1 → (a): PNT always takes the fall-through, the next sequential instruction PC+4. 2 → (b): PT always takes the target address. 3 → (c): BTFNT predicts taken when the target is behind the branch (backward = a loop), not-taken otherwise. 4 → (d): the 1-bit Branch History Table simply remembers the last outcome of that branch. 5 → (e): the 2-bit counter has hysteresis — one wrong guess only nudges it, it takes two to change the prediction.

Target 0x0040 is less than the branch address 0x00A0, so the jump is backward. BTFNT rule: backward ⇒ Predict Taken. This is the loop case — the branch jumps back to the top of a loop.

Plug straight into the master formula: $\text{CPI}=1+\underset{P_{\text{branch}}}{\underbrace{0.20}}\times \underset{P_{\text{mispredict}}}{\underbrace{0.08}}\times \underset{\text{Penalty}}{\underbrace{12}}$ Multiply left to right: $0.20\times 0.08=0.016$, then $0.016\times 12=0.192$. $\text{CPI}=1+0.192=1.192$ Interpretation: mispredictions add 19.2% overhead on top of the ideal 1 CPI.

New CPI: ${\text{CPI}}_{\text{new}}=1+0.20\times 0.03\times 12=1+0.072=1.072$ Execution time is proportional to CPI (same instruction count, same clock). Speed-up ratio: $\frac{{\text{CPI}}_{\text{old}}}{{\text{CPI}}_{\text{new}}}=\frac{1.192}{1.072}\approx 1.1119$ Time saved = $1-\frac{1.072}{1.192}=1-0.8993=0.1007$, about a 10.1% reduction in runtime.

Rule reminder: predict what the bit says; then set the bit to the actual outcome.

Correct = 3 out of 5 ⇒ accuracy = 60%. Wrong on the first (cold start) and last (exit) events — the two boundaries.

Encoding: 00=SNT, 01=WNT, 10=WT, 11=ST. Predict Taken iff counter $\ge$ 10. Increment on T (cap 11), decrement on NT (floor 00).

Correct = 2 of 5 ⇒ 40% on this cold pass — worse than the 1-bit's 60% here! The reason: the 2-bit counter needs two taken events just to start predicting taken, so it wastes an extra warm-up event.

Second entry starts at 10 (WT), left over from the exit:

Correct = 4 of 5 ⇒ 80%. The hysteresis has now "learned" the loop: only the exit misses. See the state figure below.

Once warmed up, the counter sits at 11 (ST) throughout the 100 taken iterations — all correct. The single exit NT mispredicts (predicted T at 11), dropping the counter to 10. On re-entry the very first taken event pushes it back to 11, so no cold-start penalty on subsequent passes.

Mispredictions per pass = 1 (the exit only). $\text{Accuracy}=\frac{100}{101}\approx 0.9901=99.0\%$ This is the classic "2-bit predictors nail long loops" result: the longer the loop, the more the single exit miss gets amortised.

Predictor A: ${\text{CPI}}_A=1.00+0.25\times 0.06\times 10=1.00+0.15=1.15$ Predictor B: the base cost is now 1.05, not 1.00: ${\text{CPI}}_B=1.05+0.25\times 0.025\times 10=1.05+0.0625=1.1125$ Compare: $1.1125<1.15$. Predictor B wins despite its higher base cost, because the misprediction savings ($0.15\to 0.0625$, a drop of $0.0875$) outweigh the $0.05$ base penalty. Net advantage $=1.15-1.1125=0.0375$ CPI.

Set the two CPIs equal: $1.05+0.25\times m\times 10=1.15$ $2.5m=1.15-1.05=0.10$ $m=\frac{0.10}{2.5}=0.04=4\%$ So B must keep its mispredict rate below 4% to justify its 0.05-CPI overhead. At exactly 4% they tie; at the given 2.5% B is comfortably ahead.

B2 only executes on the 500 runs where B1 was taken. Of those, it is taken 90%.

Bimodal on B2: it sees only the 500 executed instances (B2 is skipped otherwise, so no update). Best fixed bias = predict Taken (the majority). Accuracy on executed instances: $\frac{450}{500}=0.90=90\%$ Here bimodal already does fine on B2 alone, because B2's own history is a clean 90%-taken stream.

Where correlation actually pays is a different, aliasing-driven case. Suppose instead B2's outcome were perfectly determined by B1: whenever B1 taken ⇒ B2 taken, whenever (hypothetically) B1 not-taken but B2 still reached ⇒ B2 not-taken. Then the correlating predictor, keyed on the 1-bit global history of B1, reaches: $\frac{500}{500}=1.00=100\%$ while bimodal, forced to blend the two sub-streams into one counter, sits at the majority mix. The gap = the mutual information between B1 and B2. When a branch's outcome is predictable from recent branches, only a history-indexed (correlating) predictor can exploit it; a per-address bimodal counter throws that context away.

(a) Table has $2^h$ entries, each 2 bits: storage $=2\times 2^h=2^{h+1}$ bits. For $h=8$: $2^9=512$ bits (64 bytes). For $h=9$: $2^{10}=1024$ bits (128 bytes).

(b) CPI contribution from mispredicts $=P_{\text{branch}}\times m\times \text{Penalty}=0.25\times m\times 14=3.5m$.

• At $h=8$: $3.5\times 0.030=0.105$ added CPI.
• At $h=9$: $3.5\times 0.027=0.0945$ added CPI.

Savings $=0.105-0.0945=0.0105$ CPI for doubling the table (64 → 128 bytes). Whether that is "worth it" is a policy call, but the marginal gain is real and cheap in storage; the classic diminishing-returns curve means the next doubling (h=9→10) will save even less. Relate this to Cache Performance — same "double the table, shrink the benefit" shape.

The three factors multiplied in the CPI penalty term are ==$P_{\text{branch}}$, $P_{\text{mispredict}}$, and Penalty. Hysteresis in a 2-bit counter costs you accuracy on a cold, short loop but wins on a long, warm loop. Correlating predictors only beat bimodal when a branch correlates with recent branch history==.