Cache Performance and the Three C's

Now that you can decode an address and simulate a cache, the engineering question is quantitative: how good is this cache, in nanoseconds? And when it is not good enough, why is it missing? This page gives you the two tools every architect reaches for — the AMAT equation to put a number on performance, and the three C's to diagnose the misses so you know which knob to turn.

AMAT: average memory access time

A cache costs you a fixed hit time on every access, plus a miss penalty on the fraction that miss:

\text{AMAT} = t_{\text{hit}} \;+\; (\text{miss rate}) \times t_{\text{penalty}}.

The lever with the most leverage is usually the penalty, because it is huge — hundreds of cycles to DRAM. That is why we build multiple levels: an L1 miss does not go straight to DRAM, it first tries L2, whose penalty is only tens of cycles. Recursively, the L1 miss penalty is itself an AMAT for the level below:

\text{AMAT} = t_{\text{L1}} + m_{\text{L1}}\big(t_{\text{L2}} + m_{\text{L2}}\,(t_{\text{L3}} + m_{\text{L3}}\,t_{\text{DRAM}})\big).

Here the miss rates are local (misses at that level ÷ accesses reaching that level). A second lever appears: the L2 only has to catch the m_{\text{L1}} fraction that L1 dropped, so even a mediocre L2 hit rate slashes the effective penalty. Run the calculator and feel how adding a level tames a brutal DRAM latency.

// Multi-level AMAT. Times in cycles; miss rates are LOCAL (per accesses reaching that level). function amat(tL1: number, mL1: number, tL2: number, mL2: number, tDram: number): number { const l2penalty = tL2 + mL2 * tDram; // cost of an L1 miss return tL1 + mL1 * l2penalty; } const tDram = 200; // cycles to DRAM console.log("no L2 (L1 misses go straight to DRAM):"); console.log(` AMAT = ${(4 + 0.05 * tDram).toFixed(2)} cycles`); console.log("with an L2 (12-cycle hit, catches 75% of L1 misses):"); // L1: 4-cyc hit, 5% miss. L2: 12-cyc hit, 25% LOCAL miss (so 75% of L1 misses hit in L2). console.log(` AMAT = ${amat(4, 0.05, 12, 0.25, tDram).toFixed(2)} cycles`);

The three C's: a taxonomy of misses

Every miss, no matter the cache, is one of exactly three kinds. Naming the kind tells you the cure.

Compulsory (cold) — the very first reference to a block. It has never been in the cache, so it must miss. Unavoidable except by fetching the block before you need it.
Capacity — the working set is simply bigger than the cache, so blocks you still want get evicted for lack of room. Present even in a fully-associative cache of that size.
Conflict (collision) — the block would have fit, but too many hot blocks map to the same set and evict each other. These vanish in a fully-associative cache; they are the "penalty" for limited associativity.

The classic way to measure them: run the trace on a fully-associative infinite cache (only compulsory misses remain), then a fully-associative finite cache of your size (adds capacity misses), then your real set-associative cache (adds conflict misses). Each step's extra misses name their C.

Which knob attacks which C

This is the payoff of the taxonomy: each design parameter fights a different C, and can make another worse.

Turn this up…	…and you attack	…but watch out
Cache size	capacity misses	slower hit time, more area & power
Associativity	conflict misses	slower hit time, more comparators
Block size	compulsory misses (spatial locality)	too big → fewer blocks, higher miss penalty, and more conflict/capacity misses

Block size is the treacherous one: enlarging blocks amortises the cold-miss cost over more useful bytes — until the blocks get so big that you are dragging in bytes you never use, evicting things you do, and paying a fatter penalty each time. Miss rate as a function of block size is U-shaped: it falls, bottoms out, then climbs again.

Diminishing returns of size

A famous rule of thumb: to halve the miss rate you must roughly quadruple the cache — miss rate falls like 1/\sqrt{\text{size}}. The curve below shows it. Drag the working-set factor (bigger, more cache-hungry workloads sit higher) and notice the shape never changes: a steep early drop where a little cache buys a lot, then a long flat tail where doubling the cache barely moves the needle. This is capacity misses being mopped up — and why L1 caches stay small (fast) while L2/L3 grow large to chase that shrinking tail.

Worked example: is the L2 worth it?

L1 hits in 4 cycles with a 5\% miss rate; DRAM is 200 cycles. Without an L2:

\text{AMAT} = 4 + 0.05 \times 200 = 14\ \text{cycles}.

Add an L2 that hits in 12 cycles and catches 75\% of L1 misses (so its local miss rate is 25\%):

\text{AMAT} = 4 + 0.05\big(12 + 0.25 \times 200\big) = 4 + 0.05 \times 62 = 7.1\ \text{cycles}.

The L2 nearly halved the average access time without touching L1's fast hit path — the whole point of a hierarchy. That 62-cycle effective L1 penalty (instead of 200) is the L2 earning its silicon.

In multiprocessors there is a fourth: the coherence miss. When another core writes a block you had cached, the coherence protocol must invalidate your copy, so your next access misses even though you never touched anything and the block still "fits". These are misses caused by sharing, not by your own access pattern, and they can dominate in heavily-shared parallel code (especially the nasty false sharing case, where two cores hammer different bytes of the same 64-byte block). We meet them properly when we reach cache coherence — for now, just know the classic taxonomy grows a "C" the moment more than one cache is in play.

For an L2, the local miss rate is L2 misses ÷ accesses that reached L2 (i.e. that already missed L1). The global miss rate is L2 misses ÷ all CPU accesses — which equals m_{\text{L1}} \times m_{\text{L2,local}}. They can look wildly different: an L2 with a scary-sounding 40\% local miss rate might have a 2\% global rate because L1 already filtered out 95\% of traffic. Always check which one a spec sheet or exam question means — plug the local rate into the nested AMAT formula, and use the global rate only when comparing whole-system traffic.

Where next

AMAT and the three C's are the diagnostic backbone of the rest of the module. The advanced optimizations page is organised precisely by which AMAT term each trick cuts, and prefetching is the direct assault on those "unavoidable" compulsory misses.