Putting a number on the cache: AMAT
By now you can take a 32-bit address, chop it into tag, index, and offset, and walk the lookup that ends in a hit or a miss. But 'mostly hits' is a feeling, not a measurement. To compare two caches, or to decide whether a change is worth its silicon, we need a single honest number for how long an average memory access really takes. That number is the average memory access time, or AMAT, and it ties together everything from the earlier guides into one formula.
The idea is simple. Every access pays the hit time — the time to probe the cache itself — because you always have to look. Then, only when you miss, you additionally pay the miss penalty: the extra time to fetch the line from the next level down. So AMAT = hit time + miss rate x miss penalty. The miss rate is just the fraction of accesses that miss; it is the only term locality controls, and it is why the whole hierarchy works. Notice the shape: a small hit time you pay always, plus a large miss penalty you pay rarely.
AMAT = hit_time + miss_rate x miss_penalty
Example: hit_time = 1 cycle
miss_penalty = 100 cycles (go to DRAM)
miss_rate = 10% -> AMAT = 1 + 0.10 x 100 = 11 cycles
miss_rate = 3% -> AMAT = 1 + 0.03 x 100 = 4 cycles
miss_rate = 1% -> AMAT = 1 + 0.01 x 100 = 2 cycles
Going from 10% to 1% misses: same hits, but ~5x faster average.Stare at that table for a moment, because it carries the whole moral of caching. The hit time barely changed; the miss penalty never changed; yet the average swung by 5x. When the penalty for a miss dwarfs the cost of a hit — and going to DRAM really is roughly a hundred cycles against one — the average is dominated by the rare misses, not the common hits. That is why architects obsess over the last percentage point of miss rate, and why the rest of this guide is about understanding and lowering it.
The three C's: every miss has a reason
Lowering the miss rate starts with knowing why you missed. A wonderfully clarifying classification, the three C's of misses, says every miss is one of exactly three kinds. A compulsory (or cold) miss is the very first touch of a line — the data has simply never been in the cache, so no cache of any size could have helped. A capacity miss happens because the cache is too small to hold the program's whole working set, so a line you needed was evicted to make room. A conflict miss is the painful one: the line was thrown out not because the cache was full, but because too many lines mapped to the same set and crowded each other out.
The value of this split is that each C has its own cure, and the cures pull in different directions. Compulsory misses fall if you fetch more per miss — a bigger block, or prefetching the next line before it is asked for. Capacity misses fall if you make the cache bigger. Conflict misses fall if you raise associativity, because a more associative set has more slots to absorb lines that collide; a set-associative cache suffers far fewer conflicts than a direct-mapped one, and a fully associative cache has no conflict misses at all, by definition.
When the program writes: two policies
So far every access was a read — the cache hands back a copy and the original in memory is untouched. Writes raise a genuinely awkward question: the cache holds a copy of memory, so when the program changes that copy, when does the real memory in DRAM find out? Think of the cache as photocopies on your desk and memory as the master file in the cabinet. If you scribble on a photocopy, you eventually have to reconcile it with the master — the only question is when, and there are two honest answers.
Write-through updates both at once: every write goes to the cache and straight on to memory. It is simple and the master is always current, but it floods the path to memory with traffic, since even a variable you scribble on a thousand times sends a thousand writes downstream. Write-back is lazier and far more common: a write updates only the cached line and sets a single dirty bit to mark 'this copy has changed'. Memory stays stale until that line is evicted, at which point the dirty line is written back in one go. A counter racing through a loop is touched once at the end instead of a thousand times in the middle.
A second small choice rides along: on a write that misses, do you first pull the line into the cache (write-allocate) or just push the write to memory and skip the cache (no-write-allocate)? Write-back caches almost always pair with write-allocate, because once the line is in the cache, all the following writes to it become cheap hits. The everyday combination you will meet in nearly every modern CPU is therefore write-back plus write-allocate, with a dirty bit per line — lazy, traffic-light, and a beautiful fit for the temporal locality you already know writes tend to have.
Multilevel caches: don't pick small OR big — have both
Look back at the AMAT formula and you can feel a tension. To keep the hit time tiny, you want a small cache close to the core. To keep the miss rate low, you want a big cache. You cannot have one cache that is both small and big — so modern chips simply build more than one. A multilevel cache stacks a fast little L1 right next to the pipeline, a larger, slower L2 behind it, and often a big shared L3 behind that, with DRAM at the bottom. Each level is a desk; L1 is the few books at your elbow, L2 the shelf across the room, L3 the closet down the hall, and memory the library across town.
The trick that makes this pay is that the miss penalty of one level becomes the AMAT of the next. When L1 misses, it does not jump straight to the hundred-cycle DRAM; it asks L2, which is maybe ten cycles and usually hits. So the formula nests: AMAT = L1 hit time + L1 miss rate x (L2 hit time + L2 miss rate x L2 miss penalty). The rare L1 miss is now mostly absorbed by a fast L2, and only the rarer-still miss that escapes both pays the full DRAM price. Each level shaves the effective penalty of the one above it.
Put numbers on it to feel the win. With a single level, a 5% miss rate against a 100-cycle DRAM penalty gives AMAT = 1 + 0.05 x 100 = 6.0 cycles. Now slot an L2 between L1 and memory: L1 still misses 5% of the time, but its penalty is no longer 100 — it is L2's AMAT. If L2 hits in 10 cycles and only 20% of L1's misses escape it to the 100-cycle DRAM, then AMAT = 1 + 0.05 x (10 + 0.20 x 100) = 1 + 0.05 x 30 = 2.5 cycles. Same 5% L1 miss rate, yet the average more than halved, because L2 catches most of what L1 dropped.
Two numbers help you read multilevel caches honestly. The local miss rate of a level is misses divided by the accesses reaching that level — L2's local rate looks high because L1 already skimmed off all the easy hits. The global miss rate is misses at a level divided by all the CPU's accesses, and only the global rate of the last level tells you how often you truly fall all the way to memory. Confusing the two makes a perfectly good L2 look terrible, so architects quote both.
What this buys, and where we go next
Step back and the cache stops being a mysterious box and becomes a set of dials you can reason about. AMAT turns 'is this cache good?' into arithmetic. The three C's tell you which dial to turn — block size for compulsory, capacity for capacity, associativity for conflict. Write-back with a dirty bit keeps write traffic off the bus until eviction. And multilevel caching dissolves the small-versus-big dilemma by stacking levels so each catches what the one above it missed.
- Measure the cache with AMAT = hit time + miss rate x miss penalty; remember the rare miss, not the common hit, dominates.
- Diagnose each miss as compulsory, capacity, or conflict — the label points straight at the cure.
- Pick write-back plus write-allocate for everyday CPUs; keep a dirty bit and reconcile with memory only on eviction.
- Stack L1/L2/L3 so each level's miss penalty becomes the next level's much smaller AMAT.
Here is the most important thing to carry forward: every dial we turned was hardware, but the miss rate it feeds on is set by your code. The cache only rewards access patterns rich in temporal and spatial locality, and a cache-hostile loop produces exactly the same answer many times slower. The next and final guide in this rung crosses that line — from the architect's side to yours — and shows how loop order and cache-friendly tricks like tiling can quietly make a program run several times faster on the very same chip.