Prefetching strategies: Worked examples — Hardware deep dive

This is the practice deck for the parent topic. The parent built the tools: coverage $c$ , accuracy $a$ , effective miss rate $m_{e f f}$ , and AMAT. Here we drill them across every case a problem can throw at you — good cases, harmful cases, degenerate cases, and the exam trick that catches people.

Everything below only uses symbols the parent defined. Quick reminder, in plain words:

The scenario matrix

Every prefetching problem lives in one of these cells. The examples afterwards each name the cell they cover, so by the end no cell is left blank.

Cell	What makes it special	Sign/limit stress point	Example
A. Clean win	good coverage, no pollution	$Δ m = 0$ , $c$ large	Ex 1
B. Net loss	low coverage + pollution	$Δ m > 0$ , small $c$	Ex 2
C. Break-even	benefit exactly cancels pollution	solve for the tipping $Δ m$	Ex 3
D. Degenerate: $c = 0$	prefetcher does nothing	$c \to 0$ limit	Ex 4
E. Degenerate: $c = 1$	prefetcher kills all misses	$c \to 1$ limit	Ex 5
F. Stride geometry	learn a stride, place $D$ lines ahead	negative stride included	Ex 6
G. Accuracy trap	$a$ given but must NOT be multiplied in	separate $a$ from $c$	Ex 7
H. Real-world word problem	bandwidth budget from accuracy	wasted-fetch counting	Ex 8
I. Exam twist	irregular / pointer chase, no stride	stride prefetch = 0 coverage	Ex 9

Worked examples

Worked example Ex 1 — Cell A: the clean win

$t_{hi t} = 1$ , $t_{mi ss} = 200$ cycles, $m = 0.04$ . A next-line prefetcher gets coverage $c = 0.75$ with no pollution ( $Δ m = 0$ ).

Forecast: guess the new AMAT before reading on. Bigger $c$ → smaller $m_{e f f}$ → smaller AMAT. Will it roughly halve?

$m_{e f f} = m (1 - c) + Δ m = 0.04 (1 - 0.75) + 0 = 0.04 \cdot 0.25 = 0.01$ . Why this step? Coverage is defined as misses actually eliminated, so subtract exactly that fraction. No accuracy factor multiplies in.
$AMAT_{ba se} = 1 + 0.04 \cdot 200 = 9$ cycles. Why? Baseline: no prefetching, full miss rate pays the penalty.
$AMAT_{p f} = 1 + 0.01 \cdot 200 = 3$ cycles. Why? Same formula, smaller $m_{e f f}$ .

Verify: speedup $= 9/3 = 3 \times$ . Sanity: $m$ dropped to a quarter, and the miss-cost term ( $0.04 \cdot 200 = 8$ ) dropped to $0.01 \cdot 200 = 2$ . The fixed $t_{hi t} = 1$ stops it being a full $4 \times$ . ✅

Worked example Ex 3 — Cell C: break-even, solve for the tipping point

Same machine, coverage fixed at $c = 0.50$ . Question: how much pollution $Δ m$ makes prefetching exactly break even (AMAT equals baseline)?

Forecast: if half the misses die, we have "budget" to absorb some pollution. Guess the crossover $Δ m$ .

Break-even means $m_{e f f} = m$ (same effective miss rate ⇒ same AMAT). Why? AMAT depends on $m_{e f f}$ only through the second term; equal $m_{e f f}$ ⇒ equal AMAT.
$m (1 - c) + Δ m = m \Rightarrow Δ m = m - m (1 - c) = m \cdot c$ . Why? Algebra: the benefit we gained is exactly $m \cdot c$ ; pollution up to that amount just cancels it.
$Δ m = 0.04 \cdot 0.50 = 0.02$ . Why this step? We just substitute the given numbers ( $m = 0.04$ , $c = 0.50$ ) into the formula $Δ m = m \cdot c$ from step 2 to get the concrete tipping value.

Verify: with $Δ m = 0.02$ : $m_{e f f} = 0.04 \cdot 0.5 + 0.02 = 0.02 + 0.02 = 0.04 = m$ . Identical to baseline. ✅ Rule of thumb: pollution must stay below $m \cdot c$ or you lose.

Worked example Ex 6 — Cell F: stride geometry, including a

negative stride A load at PC 0x800 touches addresses (bytes): 2016, 1984, 1952, 1920. Cache line = 32 bytes. Prefetch degree $D = 3$ .

Note on alignment: each address here is a multiple of $32$ ( $2016 = 63 \cdot 32$ , $1984 = 62 \cdot 32$ , …), so each already sits at the start of its 32-byte cache line. In real hardware an address that lands inside a line is first rounded down to its line start (drop the low 5 bits, since $32 = 2^{5}$ ) before the stride math; picking line-aligned addresses here lets us focus on the stride logic without that extra rounding.

Forecast: the addresses go down. Will the stride be $+ 32$ or $- 32$ ? Where do the prefetches land?

Stride $= addr_{2} - addr_{1} = 1984 - 2016 = - 32$ . Why this step? Stride is newest minus previous. A descending walk gives a negative stride — the arithmetic is identical, only the sign flips.
Confirm: $1952 - 1984 = - 32$ ✓, $1920 - 1952 = - 32$ ✓. Stride confirmed at $- 32$ . Why? Two matching gaps raise confidence enough to prefetch (as in the parent's RPT).
Prefetch $addr + stride \cdot k$ for $k = 1, 2, 3$ from the last address $1920$ : $1920 + (- 32) \cdot k = 1888, 1856, 1824.$ Why? Same formula $a dd r + s t r i d e \cdot k$ ; the negative stride sends prefetches backward. Each result is again a multiple of $32$ , so every prefetched line is line-aligned.

Figure — read it like this: the cyan dots (top row) are the addresses the CPU already touched, marching leftward (down in address). The amber squares (bottom row) are the three prefetches the engine fires ahead of the loop, and the white arrows show each one launching from the newest access

1920

. The bracket labels the

- 32

stride; the caption confirms the farthest prefetch sits

∣ stride ∣ \cdot D = 96

bytes ahead. What to notice: the amber squares all lie to the left of the cyan dots — a negative stride prefetches backward, exactly matching the descending walk. Flip the sign and the whole picture mirrors to the right.

Verify: farthest prefetch distance $= ∣ stride ∣ \cdot D = 32 \cdot 3 = 96$ bytes ahead of the loop's direction. Lines $1888, 1856, 1824$ all lie below $1920$ , matching the descending walk. ✅ (Positive strides would land above — same machinery, mirror image.)

Worked example Ex 7 — Cell G: the accuracy trap (do NOT multiply

$a$ into $m_{e f f}$ ) A prefetcher reports accuracy $a = 0.4$ and coverage $c = 0.6$ , on the machine $t_{hi t} = 1$ , $t_{mi ss} = 200$ , $m = 0.04$ , with $Δ m = 0$ . A classmate writes $m_{e f f} = m (1 - a c)$ . Find the correct AMAT and expose the error.

Forecast: which number goes into $m_{e f f}$ — $c$ alone, or $a \cdot c$ ?

Correct: $m_{e f f} = m (1 - c) = 0.04 (1 - 0.6) = 0.016$ . Why this step? Coverage already counts only the misses truly eliminated. Accuracy is a different denominator (over issued prefetches) and measures wasted bandwidth, not miss reduction.
$AMAT_{cor r ec t} = 1 + 0.016 \cdot 200 = 4.2$ cycles.
The wrong formula gives $m_{e f f} = 0.04 (1 - 0.4 \cdot 0.6) = 0.04 \cdot 0.76 = 0.0304$ , so $AMAT_{w r o n g} = 1 + 0.0304 \cdot 200 = 7.08$ cycles. Why show it? To see the trap pessimistically double-counts: it re-penalizes with $a$ even though $c$ already folded correctness in.

Verify: $4.2 \neq = 7.08$ . The two disagree by $2.88$ cycles — proof that $a$ must stay out of $m_{e f f}$ . Accuracy will reappear in Ex 8 where it belongs: bandwidth. ✅

Worked example Ex 8 — Cell H: real-world bandwidth budget (accuracy's true home)

A core issues $P = 1, 000, 000$ prefetches over a run, with accuracy $a = 0.4$ . Each prefetch moves one 64-byte line over a bus with $B = 20 GB/s$ of bandwidth. How many bytes are wasted, and how much bus time does the waste burn?

Forecast: $40%$ of prefetches are useful, so $60%$ are wasted. Guess the wasted MB.

Useless prefetches $= P (1 - a) = 1, 000, 000 \cdot 0.6 = 600, 000$ . Why this step? Accuracy $a$ = fraction used; so $1 - a$ = fraction wasted. This is where $a$ legitimately appears — bandwidth, not $m_{e f f}$ .
Wasted bytes $= 600, 000 \cdot 64 = 38, 400, 000$ bytes $= 38.4 MB$ . Why? Each wasted prefetch still dragged a full 64-byte line across the bus.
Wasted bus time $= \frac{38 , 400 , 000 bytes}{20 \times 1 0 ^{9} bytes/s} = 1.92 \times 1 0^{- 3} s = 1.92 ms$ . Why? time $=$ bytes $\div$ bandwidth; units: $bytes / (bytes/s) = s$ . ✅ units check.

Verify: $38.4 MB$ wasted and $1.92 ms$ of bus stolen from real traffic. This is exactly why low accuracy hurts even when coverage is fine — it steals bandwidth. ✅

Worked example Ex 9 — Cell I: the exam twist — irregular pointer chase

A program walks a linked list; node addresses in access order are 5000, 8300, 1200, 9600 (bytes). Line = 64 B. (a) What stride does a stride prefetcher learn, and what coverage does it get? (b) What structure fixes it?

Forecast: are the gaps constant? If not, stride prefetch is helpless — coverage $\to 0$ .

Gaps: $8300 - 5000 = 3300$ ; $1200 - 8300 = - 7100$ ; $9600 - 1200 = 8400$ . Why this step? Compute successive strides exactly as in Ex 6.
No two gaps match ⇒ confidence never confirms ⇒ stride coverage $c = 0$ . Why? A stride prefetcher only fires on a repeating gap; random pointer targets have none.
Fix: a correlation prefetcher (parent's Strategy 3) records the pair "miss at 5000 → miss at 8300", "8300 → 1200", etc. On the next traversal of the same list, seeing $5000$ prefetches $8300$ . Why? The addresses have no formula, but the sequence repeats when you re-walk the list — history, not arithmetic.

Verify: stride coverage is $c = 0$ here (no matching gaps confirms it), so AMAT is unchanged by a stride engine; only correlation (or software pointer hints) can help. ✅

Recall Self-test: which cell?

A prefetcher has $c = 0.5$ and $Δ m = 0.03$ on $m = 0.04$ . Better or worse than baseline? ::: Worse. Break-even $Δ m = m \cdot c = 0.02$ ; here $0.03 > 0.02$ , so it's Cell B (net loss). $m_{e f f} = 0.04 \cdot 0.5 + 0.03 = 0.05 > 0.04$ . Why don't we ever write $m_{e f f} = m (1 - a c)$ ? ::: Because coverage $c$ already counts only misses actually eliminated (correctness + timeliness baked in). Multiplying by accuracy $a$ double-counts. $a$ belongs to bandwidth math (Ex 8), not $m_{e f f}$ . A descending address walk 2016,1984,1952 — sign of stride? ::: Negative ( $- 32$ ). Prefetches go backward; distance ahead uses $∣ stride ∣$ .

See also: Cache Basics — Blocks and Locality, Spatial vs Temporal Locality, Cache Pollution and Replacement Policies, Out-of-Order Execution.