Advanced Cache Optimizations

By now you know the master equation, \text{AMAT} = t_{\text{hit}} + (\text{miss rate}) \times t_{\text{penalty}}, and the three C's that populate the miss rate. There are exactly three terms to shrink, and every advanced cache trick ever invented is an attack on one of them: reduce the hit time, reduce the miss rate, or reduce the miss penalty. Keep that lens and the zoo of optimizations organises itself.

The optimization menu, sorted by target

Optimization	Idea in one line	AMAT term it cuts
Way prediction	guess the matching way early so a set-associative cache acts like a direct-mapped one on a hit	hit time
Banking / multiported	split the cache into independent banks so several accesses proceed in parallel	hit time (bandwidth)
Victim cache	a tiny fully-associative buffer holds just-evicted lines, catching conflict misses	miss rate
Larger / more-associative	attack capacity and conflict misses directly	miss rate
Multi-level (L2/L3)	a mid-speed level catches L1 misses before DRAM	miss penalty
Critical-word-first / early restart	fetch the exact word the CPU stalled on first, restart, stream the rest behind it	miss penalty
Non-blocking (lockup-free)	keep serving hits (and other misses) while a miss is outstanding — hit-under-miss	miss penalty (overlaps it away)
Prefetching	fetch blocks before they are demanded, hiding compulsory misses	miss rate / penalty

Notice how the table splits neatly into three groups — that grouping is the mental model. Below we zoom in on the three most conceptually rich ones.

Victim caches — recycling the just-evicted

A direct-mapped cache is fast but suffers conflict misses: two hot blocks fighting over one set evict each other endlessly (ping-pong thrashing). A victim cache is a small fully-associative buffer (just 4–16 lines) that catches every block the main cache throws out. On a main miss, you check the victim cache first; a hit there swaps the block back in a cycle or two instead of a trip to L2. For a handful of lines it can eliminate a large share of a direct-mapped cache's conflict misses — the cheap fix that lets a fast simple cache pretend to be more associative.

// Victim cache killing conflict misses. Direct-mapped cache of 1 line (worst case), // plus a 2-entry fully-associative victim buffer. Two blocks (0 and 1) map to the same slot. let mainTag = -1; // the one direct-mapped line const victim: number[] = []; // recently evicted blocks (FA, size 2) function access(block: number): string { if (mainTag === block) return `block ${block}: HIT (main)`; const vi = victim.indexOf(block); if (vi !== -1) { // found in victim cache: swap it back, no L2 trip victim.splice(vi, 1); if (mainTag !== -1) victim.unshift(mainTag); mainTag = block; return `block ${block}: hit (victim) - conflict miss saved!`; } if (mainTag !== -1) { victim.unshift(mainTag); victim.length = Math.min(victim.length, 2); } mainTag = block; return `block ${block}: MISS (go to L2)`; } // Classic ping-pong: 0,1,0,1,0,1 — a direct-mapped cache misses EVERY time. for (const b of [0, 1, 0, 1, 0, 1]) console.log(access(b));

Non-blocking caches — don't freeze on a miss

A naive cache blocks: on a miss the whole cache stalls until the block returns, hundreds of cycles wasted. A non-blocking (lockup-free) cache instead keeps going — it serves later hits while the miss is in flight (hit-under-miss), and even launches further misses (miss-under-miss). Each outstanding miss is tracked by a Miss Status Handling Register (MSHR); with N MSHRs the cache can have N misses in flight at once, overlapping their latencies. This is what makes a cache worthy of an out-of-order core: the core generates many independent loads, and the cache pursues them all in parallel, folding hundreds of cycles of memory latency into each other rather than paying them end to end.

Critical-word-first — deliver the byte they're waiting for

A miss fetches a whole 64-byte block, but the CPU stalled on one word inside it. Why wait for all 64 bytes? Critical-word-first asks memory for the needed word first and forwards it to the CPU the instant it arrives (early restart); the rest of the block streams in behind while the pipeline is already running again. The effective miss penalty drops from "time for the whole block" to "time for the first word" — most of the block-transfer time is hidden. The trick is nearly free and appears in essentially every real cache.

Multi-level: inclusion vs exclusion

With three cache levels, a policy question appears: must a block in L1 also sit in L2 and L3?

Inclusive — every block in an inner level is guaranteed present in the outer level. Simplifies coherence (snoop only the outer level to know if any inner cache holds a block), but wastes capacity duplicating data, and an eviction from L3 must back-invalidate the copies in L1/L2.
Exclusive — a block lives in exactly one level; the levels partition the data, giving the most effective total capacity. AMD chips have long favoured this. Costs more traffic (blocks shuffle between levels on hits/misses).
Non-inclusive/NINE — neither guaranteed; the pragmatic middle ground many Intel chips use.

And banking ties it together at the bottom: dividing each cache (and DRAM) into independent banks lets multiple accesses proceed at once — more bandwidth for the many outstanding misses a non-blocking cache and an out-of-order core throw at it.

An n-way set-associative cache normally reads all n tags and all n data ways in parallel, then a late multiplexer picks the matching one — safe, but the data can't leave until the (slow) tag comparison finishes. Way prediction adds a tiny table that guesses which way will hit and reads only that one, speculatively, forwarding its data immediately. Guess right (usually >90% of the time thanks to locality) and you got direct-mapped hit speed with set-associative miss rates — the best of both. Guess wrong and you pay an extra cycle to check the others. It is speculation applied to the cache, the same gamble the branch predictor makes in the pipeline, and it pays for the same reason: programs are predictable.

A frequent muddle: "L2 caches reduce the miss rate." An L2 does not lower L1's miss rate at all — L1 misses exactly as often as before. What the L2 lowers is the penalty of each of those misses (62 cycles instead of 200, say). Victim caches and higher associativity attack the miss rate; extra levels, critical-word-first, and non-blocking attack the miss penalty; way prediction and banking attack the hit time. Naming the term a trick targets is the whole point of the taxonomy — conflate rate and penalty and you will "optimise" the wrong number and wonder why AMAT didn't move.

The next assault: prefetching

One row of the table deserves its own page. Prefetching is unique because it attacks the one C the others cannot touch — the compulsory miss — by fetching a block before the CPU ever asks. That is where we go next.