Prefetching

Every trick in the last lesson left one enemy standing: the compulsory miss. The first time a program touches a block, it must miss — the data has never been in the cache, so no amount of size or associativity can help. Unless… you fetch the block before the program asks for it. That is prefetching: predicting future accesses and pulling those blocks in early, so that when the demand finally comes, the data is already sitting in the cache. Done well, a compulsory miss silently becomes a hit.

The catch is in that word predicting. Prefetch too late and you still stall; too early and the block gets evicted before use; wrong entirely and you have wasted precious memory bandwidth and maybe polluted the cache, evicting something useful. Prefetching is a bet, and its whole art is being right, and being on time.

Hardware prefetchers: patterns in the address stream

The memory hardware watches the addresses flowing past and guesses what's next, purely from the pattern — no help from the program:

Prefetcher	What it detects	What it fetches
Next-line	any access	the sequentially following block (block + 1) — dead simple, great for code & scans
Stride	a constant address stride (e.g. +512 bytes each step)	the block a few strides ahead — catches array/matrix walks
Stream	several concurrent sequential streams	runs ahead in each stream, into dedicated stream buffers

A stride prefetcher is the workhorse. It records, per instruction, the last address and the last stride; when the same stride repeats it grows confident and launches a prefetch several strides ahead of the demand stream. Loops over arrays and matrices — the beating heart of scientific and ML code — are exactly constant-stride, so this pays enormously.

// A minimal stride prefetcher: learn the stride, then prefetch DISTANCE blocks ahead. const DISTANCE = 4; // how far ahead to run let last = -1, stride = 0, confident = false; const prefetched = new Set<number>(); let demandMisses = 0, savedByPrefetch = 0; function demand(block: number) { if (prefetched.has(block)) { savedByPrefetch++; prefetched.delete(block); } else demandMisses++; // a real (compulsory) miss if (last !== -1) { const s = block - last; if (s === stride && s !== 0) confident = true; else confident = false; stride = s; } last = block; if (confident) prefetched.add(block + stride * DISTANCE); // fetch ahead } // Walk an array with stride +2: blocks 0,2,4,6,8,10,12,14. for (let b = 0; b <= 14; b += 2) demand(b); console.log(`demand misses: ${demandMisses}`); console.log(`accesses served by prefetch: ${savedByPrefetch}`);

Software prefetching: the compiler asks nicely

Sometimes the program knows its future better than any hardware pattern-matcher — chasing a linked list, or a hash table, where addresses look random to the hardware but the code knows the next node pointer. ISAs expose a prefetch instruction (x86 \texttt{PREFETCHT0}, ARM \texttt{PRFM}) — a non-binding hint that says "please start bringing this address toward the cache; I'll need it in about 20 iterations". The compiler (or a careful programmer) inserts it far enough ahead of the use to hide the latency. It faults on nothing and returns no value; a wrong guess just wastes a little bandwidth. The skill is picking the prefetch distance: insert it k iterations early where k \approx (memory latency) ÷ (work per iteration).

// Software prefetch distance: how many iterations ahead to prefetch. // Rule of thumb: k = ceil(memoryLatency / workPerIterationCycles). function prefetchDistance(memLatency: number, workPerIter: number): number { return Math.ceil(memLatency / workPerIter); } const memLatency = 200; // cycles to bring a block from DRAM for (const work of [10, 20, 40, 100]) { const k = prefetchDistance(memLatency, work); console.log(`work/iter = ${work} cyc -> prefetch ${k} iterations ahead`); }

Timeliness: the Goldilocks distance

Prefetching has a sweet spot. Fetch too close to the use and the block hasn't arrived yet — you still eat much of the latency (a late prefetch). Fetch too far ahead and the block sits in the cache so long it gets evicted before use (or evicts something you needed — pollution). The benefit curve therefore rises then falls with prefetch distance. Slide the memory-latency knob: as memory gets slower, the whole curve's peak shifts to larger distances — you must prefetch earlier to hide a longer latency.

Three numbers that judge a prefetcher

Coverage — the fraction of original misses that prefetching eliminated. High coverage = it caught most of the misses.
Accuracy — the fraction of prefetches that were actually used. Low accuracy = wasted bandwidth and cache pollution.
Timeliness — did the block arrive before it was demanded? Early enough to hide latency, late enough to survive eviction.

A good prefetcher wants all three high at once, and they fight: crank up aggressiveness for coverage and accuracy usually falls (more speculative, more wrong guesses). On a bandwidth-limited machine an inaccurate prefetcher is worse than none — it steals the very bandwidth demand misses need.

Absolutely, and it's a real hazard. A prefetcher with low accuracy floods the memory system with blocks no one wanted. On a machine already starved for DRAM bandwidth, those useless fetches queue ahead of the demand misses the CPU is truly waiting on, and evict useful lines to make room. Coverage looks fine in isolation, but end-to-end the program slows down. This is why aggressive prefetchers are throttled dynamically — hardware watches accuracy and bandwidth pressure and dials the prefetcher back when it starts doing harm. More speculation is not always better; a prefetch you don't use is pure cost.

A common overstatement: "prefetching fixes cache misses." It specifically targets compulsory (and some capacity/conflict) misses by moving them earlier in time — the block still occupies the cache, it just arrives before you stall. It does not make your working set fit; if your data genuinely exceeds the cache, prefetching can even hurt by accelerating the eviction of things you still need. And a prefetch that arrives and is evicted before use bought you nothing but bandwidth cost. Think of prefetching as latency hiding, not capacity creation — it reshapes when misses happen, not whether the data fits.