Foundations — Prefetching strategies

This page assumes nothing. Before you read the parent note, you must be fluent in every letter, ratio, and picture it throws at you. We build each one from the ground up, in an order where every symbol is earned before it is used.

0. The stage everything sits on: a cache

Look at the picture below: the CPU never talks to slow memory directly if it can help it — it looks in the fast cache first.

WHY the topic needs this: prefetching's entire job is turning misses into hits. If you don't have the words "block", "hit", "miss" as pictures in your head, the metrics later are meaningless. This is the ground floor — see Cache Basics — Blocks and Locality.

1. Time measured in cycles, and why memory is so slow

WHY the topic needs this: the entire motivation for prefetching is that a stall is enormous. Every formula later is really asking "how many of these 400-cycle freezes can we avoid?"

2. Two kinds of "you'll want it soon" — locality

WHY the topic needs this: locality is the reason a guess can succeed at all. Next-line prefetching lives on spatial locality; correlation prefetching lives on repeated (temporal) patterns of misses. No locality → no predictable future → prefetching is pure luck. Full detail in Spatial vs Temporal Locality.

3. Address, block number, and stride — the arithmetic of "where"

Let's make "stride" a picture — a ruler with evenly spaced ticks:

WHY the topic needs this: next-line prefetch is the special case stride $=1$ block (one box forward). Stride prefetch is the general case, usually expressed in bytes. The parent's formula $addr+stride\cdot k$ is nothing but "start here, take $k$ equal steps of size stride" — with $addr$ and $stride$ in the same unit (bytes).

4. Degree $D$ and the multiplier $k$ — how far ahead to run

WHY the topic needs this: the parent uses $D$ and $k$ in both next-line and stride strategies. If you read $addr+stride\cdot k$ without knowing $k$ just counts $\mathrm{1..}D$, the formula looks mysterious. It isn't — it's just "take $D$ evenly spaced steps forward."

5. Fractions that grade a prefetcher — $m$, $c$, $a$

Everything the parent measures is a fraction: a number between $0$ and $1$ meaning "this portion of a whole."

The two pie charts below make the "different wholes" point visual. Look at what each pie is a slice of: the left pie is cut from the set of original misses — its green wedge ($c=0.6$) is the portion of those misses we killed. The right pie is cut from a completely different set, the prefetches we issued — its green wedge ($a=0.35$) is the portion that got used, and the red "wasted / pollution" slice is bandwidth thrown away. The two greens are not comparable numbers: they answer different questions because they are slices of different circles. That is exactly why you must never multiply $a$ into a coverage formula.

WHY the topic needs this: the parent's central formula $m_{eff}=m(1-c)$ only makes sense once you see that $c$ is already "the misses actually eliminated". The related metrics feed Cache Pollution and Replacement Policies (bad accuracy → pollution) and are the vocabulary of the whole page.

6. Reading $m_{eff}=m(1-c)$ before the parent does

We now have every piece. Read the formula in plain words:

If $c=0$ (prefetcher does nothing), $m_{eff}=m$. If $c=1$ (kills every miss), $m_{eff}=0$. Every value in between is a straight line — no hidden accuracy factor, because $c$ already counts only the ones that worked. See Average Memory Access Time (AMAT) for where $m_{eff}$ plugs in.

7. Symbols you'll meet later (so they're not new when you get there)

Prerequisite map

Equipment checklist

Test yourself — reveal only after answering out loud.