Branch Predictor or Bigger L1: Reading CPI and Clock Together
A five-stage in-order core (IF, ID, EX, MEM, WB) runs at 1 GHz with an ideal CPI of 1.0 and no structural hazards. Profiling the target workload gives: 20% of dynamic instructions are conditional branches, 30% of those are mispredicted, and each misprediction flushes three cycles; 25% of instructions are loads, 10% of which miss in the 32 KB L1 and cost a further 15 cycles when serviced from L2. Two changes are on the table. Change A is a better branch predictor that cuts the misprediction rate to 10% with no clock impact. Change B doubles L1 to 64 KB, dropping the load miss rate to 6%, but lengthens the clock period to 1.1 ns. The team must recommend a configuration for a 10^8-instruction benchmark, and the argument in the room is whether CPI or execution time should decide it. Nothing else in the pipeline changes, and both changes are independent of each other.
1. Compute the baseline CPI and the execution time of the 10^8-instruction benchmark. Show each stall component separately.
Read the worked answer
CPI = ideal CPI + stall cycles per instruction, with each stall term being (fraction of instructions causing it) x (penalty).
- Branch misprediction stalls: 0.20 branches x 0.30 mispredicted x 3 cycles = 0.18
- L1 miss stalls: 0.25 loads x 0.10 miss rate x 15 cycles = 0.375
- Base: 1.0
CPI = 1.0 + 0.18 + 0.375 = 1.555
Cycle time = 1 ns at 1 GHz, so time per instruction = 1.555 ns and total time = 10^8 x 1.555 ns = 1.555 x 10^8 ns = 0.1555 s.
The load stalls are already twice the branch stalls, which is worth noting before any proposal is evaluated: 0.375 of the 0.555 excess cycles comes from memory, 0.18 from control flow. Any intuition that branches dominate this workload is simply wrong at these numbers.
2. Evaluate Change A and Change B independently: give the new CPI, the new cycle time and the speedup over baseline for each. Which one should ship?
Read the worked answer
Change A (better predictor, misprediction 30% → 10%, clock unchanged): branch term = 0.20 x 0.10 x 3 = 0.06; CPI = 1 + 0.06 + 0.375 = 1.435; cycle time 1 ns → 1.435 ns/instruction; speedup = 1.555 / 1.435 = 1.084 (8.4%).
Change B (64 KB L1, miss 10% → 6%, clock period 1.1 ns): miss term = 0.25 x 0.06 x 15 = 0.225; CPI = 1 + 0.18 + 0.225 = 1.405; cycle time 1.1 ns → 1.405 x 1.1 = 1.5455 ns/instruction; speedup = 1.555 / 1.5455 = 1.006 (0.6%).
Ship A. The trap is that B has the better CPI (1.405 < 1.435) - it removes 0.15 cycles per instruction against A's 0.12 - but CPI is only half the performance equation. The 10% longer cycle multiplies away almost the entire gain: 1.405 x 1.1 is worse than 1.435 x 1.0. Comparing CPIs across machines with different clocks is meaningless; only instructions x CPI x cycle time, i.e. time, is comparable. B's CPI win would be real only if the cache could be enlarged without lengthening the clock.
3. A third option C pairs both changes and accepts the 1.1 ns clock. Compute its speedup and compare it with A alone and with a hypothetical B that has no clock penalty. What should the team conclude?
Read the worked answer
Option C (both changes, 1.1 ns clock): branch term 0.06, miss term 0.225, CPI = 1 + 0.06 + 0.225 = 1.285; time per instruction = 1.285 x 1.1 = 1.4135 ns; speedup = 1.555 / 1.4135 = 1.100 (10.0%).
Comparison:
| Configuration | CPI | ns/instruction | Speedup |
|---|---|---|---|
| Baseline | 1.555 | 1.5550 | 1.000 |
| A only | 1.435 | 1.4350 | 1.084 |
| B only | 1.405 | 1.5455 | 1.006 |
| B, if clock were free | 1.405 | 1.4050 | 1.107 |
| C (A + B, 1.1 ns) | 1.285 | 1.4135 | 1.100 |
Conclusions. (i) C is the fastest real option, but only by 1.5% over A alone - about 0.0215 ns per instruction, which is inside the noise of most benchmark measurements; if silicon area or verification cost matters, A alone is the defensible ship. (ii) The clock penalty belongs to the cache change only, so pairing it with the predictor does not double-count it: C's CPI is the product of both improvements while the frequency cost is paid once. (iii) If the cache could be doubled without slowing the clock, B alone would beat A (1.107 vs 1.084), which tells the team that the L1 miss path is the bigger underlying problem and that a cache redesign with a critical-path fix - pipelined L1 access, larger L2, or prefetching - is the higher-leverage project.