The Memory Hierarchy Upgrade Committee
A high school robotics team runs a simulation on 40 single-board computers. Each board has a 32 KB L 1 cache with a 1-cycle hit time, a unified L 2 cache with a 10-cycle hit time, and 100-cycle main memory. Profiling shows a 5% L 1 miss rate; of those misses, 20% also miss in L 2. A vendor offers two upgrades: (A) double L 1 to 64 KB, which measurements suggest would halve the L 1 miss rate but raise L 1 hit time to 1.5 cycles; or (B) keep L 1 unchanged and add a prefetcher that would cut the L 2 miss rate from 20% to 10%. The team has budget for only one upgrade and wants the larger reduction in average memory access time (AMAT).
1. Compute AMAT for the baseline, Upgrade A, and Upgrade B. Which upgrade should the team choose, and why does the larger reduction in miss rate not automatically win?
Read the worked answer
Use AMAT = L 1 hit time + L 1 miss rate x L 1 miss penalty, where the L 1 miss penalty is L 2 hit time + L 2 miss rate x memory latency.
- Baseline: penalty = 10 + 0.20(100) = 30 cycles. AMAT = 1 + 0.05(30) = 2.5 cycles.
- Upgrade A: penalty is still 30. AMAT = 1.5 + 0.025(30) = 2.25 cycles.
- Upgrade B: penalty = 10 + 0.10(100) = 20 cycles. AMAT = 1 + 0.05(20) = 2.0 cycles.
Upgrade B is better: it reduces AMAT by 20%, while A reduces it by only 10%. A halves the L 1 miss rate, but every access pays the higher 1.5-cycle hit time, including the 97.5% of accesses that hit. The miss-rate gain is diluted by the hit-time cost. The team should choose B, though it should verify that the prefetcher does not increase L 1 pressure or L 2 hit time.
2. The vendor for Upgrade A argues that it 'halves memory stalls,' so it must be the better choice. Is that claim numerically defensible, and why is it misleading for the team's decision?
Read the worked answer
The claim is defensible only in a narrow sense. Stall cycles per memory access equal miss rate x miss penalty. Baseline stalls are 0.05(30) = 1.5 cycles per access; with A they are 0.025(30) = 0.75 cycles per access, so A does halve the stall component.
It is misleading because AMAT also includes the hit time paid on every access. With A, total AMAT is 1.5 + 0.75 = 2.25 cycles, versus 1 + 1.0 = 2.0 cycles for B. Halving a component that is only part of the total cannot halve total time. The vendor is optimizing the wrong metric for the team's stated goal. A correct comparison reports AMAT or total execution time under the real workload, not stall cycles alone.
3. What measurement or workload change could reverse your recommendation? Name two and explain the mechanism.
Read the worked answer
Two plausible reversals:
- The prefetcher pollutes the caches. If it fetches lines that are never used, the L 1 miss rate could rise above 5%, or the L 2 hit time could rise. Then B's AMAT advantage could shrink or disappear. Measure the actual L 1 and L 2 miss rates with and without the prefetcher, not just the modeled improvement.
- The L 1 hit-time penalty is smaller than assumed. If doubling L 1 raises hit time only slightly, say to 1.1 cycles, A gives 1.1 + 0.025(30) = 1.85 cycles, beating B's 2.0. The recommendation is sensitive to the hit-time cost, so the team should benchmark it on the real board rather than trust the vendor's estimate.
A workload with many streaming accesses that the prefetcher handles well would also favor B; a pointer-chasing workload that defeats prefetching would favor A.