Prefetching strategies: Visual walkthrough — Hardware deep dive

We assume you have never seen the letters $m$ , $c$ , or "AMAT" before. Every one of them will be a picture before it is a symbol.

Step 1 — What a single memory access actually costs

WHAT. Imagine the CPU asks the cache for one piece of data. Two things can happen. Either the data is already sitting in the cache — that is a hit — or it is not there and must be dragged in from slow main memory — that is a miss.

WHY start here. Every formula about average time is really just a weighted average over these two outcomes. If we don't nail what each outcome costs, nothing later makes sense.

PICTURE. Two roads leaving the CPU. The short blue road (a hit) is fast. The long pink road (a miss) detours all the way out to DRAM and back.

Step 2 — Turning "sometimes a miss" into a number: the miss rate $m$

WHAT. Out of every access the CPU makes, some fraction are misses. Call that fraction $m$ (for miss). If $m = 0.05$ , that means 5 out of every 100 accesses miss.

WHY a fraction and not a count? Because programs make billions of accesses. We can't reason about each one. But a fraction lets us talk about "a typical access" — and averages are exactly what we need to compare designs.

PICTURE. A strip of 100 little access-squares. The blue ones are hits, the pink ones are misses. The pink ones are $m$ of the total; the blue ones are $1 - m$ .

AMAT is short for Average Memory Access Time (AMAT) — literally the average time one access takes.

Step 3 — Prefetching: fetching a pink square before the CPU asks

WHAT. A prefetcher guesses which block the CPU will want next and starts loading it early, while the CPU is still busy with other work. If the guess is right and it arrives in time, then when the CPU finally asks — the block is already there. A square that would have been pink turns blue.

WHY does this help at all? Because the slow memory trip now happens in the shadow of useful computation instead of stalling the CPU. This overlap is why prefetching leans on ideas like Memory-Level Parallelism (MLP) and Out-of-Order Execution — the CPU keeps working while the fetch is in flight.

PICTURE. The same strip from Step 2, but now some of the pink squares are being repainted blue by a little "prefetch engine" reaching ahead of the access it's currently servicing.

Step 4 — Coverage $c$ and accuracy $a$ : the two honest numbers

WHAT. The prefetcher does two separable things, so we need two fractions, each with its own denominator:

WHY define it this way. Coverage is measured over the original misses — the pink squares. It already folds in "was the guess correct?" and "did it arrive in time?": a prefetch only counts toward coverage if the miss really vanished. That is why coverage alone drives the benefit.

PICTURE. Take the pink misses and split them into two piles: the $c$ portion that got saved (repainted blue) and the $1 - c$ portion that stayed pink because the prefetcher missed them.

Step 5 — Plug $m_{e f f}$ back into AMAT

WHAT. The AMAT formula from Step 2 doesn't change shape — we just feed it the smaller miss rate.

WHY. Nothing about hits or the cost of a miss changed. The only thing prefetching changed is how many misses survive. So we swap $m \to m_{e f f}$ and leave everything else alone.

PICTURE. Two bars side by side: the baseline AMAT (a tall pink miss-portion) and the prefetched AMAT (a short pink miss-portion). The blue $t_{hi t}$ base is identical in both; only the pink stack shrinks.

This is the same locality-driven win that Cache Basics — Blocks and Locality and Spatial vs Temporal Locality rely on — prefetching just acts on that locality early.

Step 6 — Where $Δ m$ comes from: modelling pollution from accuracy

WHAT. A prefetch that guesses wrong still occupies a cache line. To make room, it may evict a live block — one the CPU was about to reuse. That eviction creates a brand-new miss that would not have existed. The fraction of accesses turned into fresh misses this way is $Δ m$ , the pollution term. It is not a magic constant — we can model where it comes from.

WHY it needs its own step. Every earlier case made things better or neutral. This is the case where prefetching makes things worse, and the reader must never be surprised by it. This is where accuracy $a$ from Step 4 finally does its job.

PICTURE. A wrong prefetch (pink-striped) barging into a full cache set and kicking a blue live block out — that ejected block becomes a new pink square that wasn't there before.

Formula A concrete model for

$Δ m$ Suppose the prefetcher issues $p$ prefetches per access (its issue rate). By the definition of accuracy $a$ , a fraction $a$ of them are useful and a fraction $(1 - a)$ are wasted. Each wasted prefetch might evict a live block; let $ϕ$ be the fraction of wasted prefetches that actually displace a soon-reused line (this depends on cache associativity and replacement policy — see Cache Pollution and Replacement Policies). Then $fresh misses per access Δ m = prefetches issued/access p \cdot fraction wasted (1 - a) \cdot fraction that evict a live line ϕ$

Read the dependencies straight off: more aggressive prefetching (higher $p$ ) → more pollution; less accurate ( $a$ small) → more pollution; higher associativity or a smarter replacement policy (smaller $ϕ$ , since victims are less likely to be live) → less pollution. In the ideal limits $a = 1$ (perfectly accurate) or $ϕ = 0$ (never evicts a live line) give $Δ m = 0$ .

Step 7 — The two boundary cases (sanity checks)

WHAT. Push $c$ to its extremes and confirm the formula behaves.

WHY. A formula you trust must give the obvious answer at the edges. If it doesn't, you built it wrong.

PICTURE. A slider for $c$ running from $0$ to $1$ , with the AMAT bar shrinking as the slider slides right.

Perfect prefetcher, $c = 1$ , $Δ m = 0$ : $m_{e f f} = m (1 - 1) = 0$ , so $AMAT = t_{hi t}$ . Every miss killed → you only ever pay the probe cost. The best possible outcome.
Useless prefetcher, $c = 0$ , $Δ m = 0$ : $m_{e f f} = m (1 - 0) = m$ , so $AMAT = t_{hi t} + m t_{mi ss}$ — exactly the baseline of Step 2. Doing nothing changes nothing. Good: the formula is backward-compatible.
Actively harmful, $c = 0$ , $Δ m > 0$ : $m_{e f f} = m + Δ m > m$ → strictly worse than baseline, matching Step 6.

The one-picture summary

The figure maps every symbol to a visual element: the full strip is all accesses; blue squares are hits and pink squares are misses ( $m$ = pink fraction, feeding $t_{mi ss}$ ); coverage $c$ repaints a labelled slice of pink to blue (the benefit, arrow tagged $c$ ); pollution $Δ m = p (1 - a) ϕ$ sneaks a few new striped-pink squares back in (the cost, arrow tagged $Δ m$ ); the always-present blue base band is $t_{hi t}$ . What survives is $m_{e f f} = m (1 - c) + Δ m$ , and the bottom line spells the full AMAT.

Recall Feynman retelling — say it in plain words

Every time the CPU wants data, it's like knocking on a door. Usually someone's home (a hit, cheap). Sometimes nobody's home and you must drive across town to fetch them (a miss, expensive). The miss rate $m$ is just how often nobody's home.

A prefetcher is a helpful assistant who guesses who you'll want next and calls them over early, so they're already home when you knock. Coverage $c$ is the fraction of the "nobody home" situations the assistant successfully fixed, so surviving misses shrink from $m$ to $m (1 - c)$ . Accuracy $a$ is a different score: of all the people the assistant called, how many were actually wanted — it doesn't help you directly, but a low $a$ means lots of unwanted guests, and unwanted guests shove out people you needed. That's pollution $Δ m$ , which grows with how eagerly the assistant calls ( $p$ ), how often it's wrong ( $1 - a$ ), and how likely the shoved-out person mattered ( $ϕ$ , set by cache associativity and replacement policy).

So the true surviving miss rate is $m (1 - c) + Δ m$ , and $AMAT = t_{hi t} + m_{e f f} t_{mi ss}$ . One last honesty note: $t_{mi ss}$ isn't really fixed — overlapping trips (MLP) make it smaller, while bandwidth contention from too many prefetches makes it larger. When $c = 1$ you're in heaven ( $AMAT = t_{hi t}$ ); when $c = 0, Δ m = 0$ nothing changed; when the assistant guesses badly you're worse off than having no assistant at all.

Recall Self-test

What does $t_{hi t}$ appear as in AMAT and why is it never multiplied by a fraction? ::: Every access probes the cache, so all accesses pay $t_{hi t}$ ; it's a flat additive cost, not conditional on a hit/miss. Why is the benefit term $m (1 - c)$ and not $m (1 - a c)$ ? ::: Coverage $c$ is defined over original misses as the ones actually eliminated — correctness and timeliness are already inside it; accuracy $a$ belongs on the cost side ( $Δ m$ ), not the benefit side. Give the model for $Δ m$ and name what each factor depends on. ::: $Δ m = p (1 - a) ϕ$ : $p$ = issue rate (aggressiveness), $1 - a$ = wasted-prefetch fraction (accuracy), $ϕ$ = chance a wasted prefetch evicts a live line (associativity + replacement policy). Why is $t_{mi ss}$ only an approximation? ::: Overlapping misses/prefetches (MLP) reduce the felt per-miss penalty, while bandwidth contention raises it — it is an effective average, not a constant. At $c = 1, Δ m = 0$ , what is AMAT? ::: $t_{hi t}$ — every miss is killed, so only the probe cost remains.

See also: Compiler Optimizations — Loop Blocking for restructuring code so the accesses a prefetcher sees become predictable in the first place.