Prefetching strategies: Question bank — Hardware deep dive

First — every symbol this page uses, defined and pictured

Before any trap, lock down the vocabulary. If a symbol below is fuzzy, the questions won't make sense. Look at the figure while you read each line: it draws the whole latency-and-metrics story on one canvas.

Definition The symbols, in plain words with units

Block $b$ ::= one whole cache line — a fixed chunk of contiguous bytes (say 64 bytes). $b$ is a line index, so " $b + 1$ " means the next line in memory, not the next byte. Units of $b$ : lines.
Stride ::= the constant gap in bytes between successive addresses touched by one load instruction. for(i) A[i] on 4-byte ints has stride $4$ ; A[i*8] has stride $32$ . Units: bytes. A stride prefetcher's whole job is to learn this number.
Prefetch degree $D$ ::= how many extra lines the prefetcher pulls per trigger. Units: lines (a count). If stride $= 32$ bytes and $D = 4$ , the farthest prefetch is $s t r i d e \cdot D = 128$ bytes ahead — degree is a count, distance is bytes.
Hit time $t_{hi t}$ ::= cycles paid on every access just to probe the cache (data was already there or not). In the figure this is the short green bar.
Miss penalty $t_{mi ss}$ ::= the extra cycles paid when the block was absent and must come from slow memory — the long red bar in the figure.
$t_{a}$ ::= the time (measured from the moment the prefetch started) at which the CPU actually issues its demand access for that block. Small $t_{a}$ = CPU asked soon after the prefetch launched. Units: cycles. Marked as the dashed line in the figure.
$t_{u se}$ ::= the time (from when a prefetched line lands in cache) at which the CPU finally uses that line. The gap up to $t_{u se}$ is how long the line sits idle-but-occupying-space. Units: cycles.
Miss rate $m$ ::= fraction of accesses that miss with no prefetching (the baseline).
Effective miss rate $m_{e f f}$ ::= the miss rate after the prefetcher acts — what actually reaches slow memory.
Coverage $c$ ::= fraction of the original misses that the prefetcher truly turns into hits (correctness and timeliness already folded in). Denominator = original misses. Units: a fraction in $[0, 1]$ .
Accuracy $a$ ::= fraction of the prefetches you issued that get used before eviction. Denominator = issued prefetches. Units: a fraction in $[0, 1]$ . Low $a$ means wasted bandwidth and pollution — note it has a different denominator from coverage.
AMAT ::= Average Memory Access Time $= t_{hi t} + m_{e f f} \cdot t_{mi ss}$ : pay the probe always, pay the penalty only on surviving misses.

Where the pollution term $Δ m$ comes from

The trickiest formula on the parent page is $m_{e f f} = m (1 - c) + Δ m$ . Let's derive it, not just quote it. Follow the figure panel by panel.

Formula Building

$m_{e f f}$ one term at a time Start with the baseline: out of every access, a fraction $m$ misses (left bar in the figure).

Step 1 — subtract what coverage kills. Coverage $c$ (defined above) is the fraction of those original misses truly turned into hits. So the survivors are $m (1 - c)$ (middle bar shrinks). Why subtract exactly $c$ and not $a \cdot c$ ? Because $c$ already counts only the misses that were correctly and timely prefetched — accuracy is baked in.
Step 2 — add what pollution creates. Each useless prefetch had to make room, so it evicted a still-live block. When the CPU later touches that evicted block, it misses — a brand-new miss that did not exist in the baseline. Sum those new misses per access and call it $Δ m$ (the red slice added back on the right bar).
Result: $m_{e f f} = survivors m (1 - c) + pollution-induced new misses Δ m$ . How is $Δ m$ measured? Run the workload with and without the prefetcher; the extra demand misses caused purely by prefetch-driven evictions, divided by total accesses, is $Δ m$ .

Quantifying "too early" — the eviction window

The parent warns that arriving too early can hurt. Let's make that concrete with a picture instead of an assertion.

True or false — justify

Every answer must give a because. A bare "true" scores zero.

A next-line prefetcher always helps performance

False — if the program has poor spatial locality (random access), block

b + 1

is rarely used, so prefetches waste bandwidth and pollute the cache, possibly raising AMAT above baseline.

Coverage of 100% means the prefetcher is perfect

False — coverage only says all original misses became hits; it says nothing about the useless prefetches also fired, which cost bandwidth and can pollute. You also need high accuracy.

If accuracy is 100%, then coverage is also 100%

False — accuracy 100% means every prefetch you issued was used, but you may have issued prefetches for only 10% of the misses, leaving 90% still as misses (low coverage).

A prefetch that arrives after the CPU already requested the block is useless

False — it can still turn a full miss into a partial miss: the block is already in flight, so the CPU only waits the remaining fetch time

t_{mi ss} - t_{a}

instead of the full

t_{mi ss}

. It just isn't a complete win.

A prefetch that arrives too early is always fine

False — the longer it sits before use, the more intervening same-set accesses can evict it (timeliness failure), and if it evicted a live line to make room it also caused pollution. Both hurt.

Stride prefetching can handle a linked-list traversal

False — the next node's address is stored in the current node's pointer field, so it can be literally anywhere in memory; there is no constant byte-gap for the stride detector to confirm. You need a correlation/pointer prefetcher that remembers "node A was followed by node B."

Hardware prefetching requires recompiling the program

False — it is a dedicated engine watching the miss stream; it works on unmodified binaries. That's its main advantage over software prefetch.

Software prefetching costs no instruction bandwidth

False — each PREFETCHT0 is a real instruction occupying a slot and decode/issue resources; the trade is precision for that overhead.

Increasing prefetch degree

D

always increases coverage

False — beyond a point extra lines are unlikely to be used (accuracy drops), and they evict live data, so pollution (

Δ m

) can erase the gain. There's a sweet spot, not a monotone climb.

m_{e f f} = m (1 - c)

, replacing

c

with accuracy

a

gives the same number

False — coverage and accuracy have different denominators (misses vs issued prefetches). Accuracy does not multiply into

m_{e f f}

; it governs wasted bandwidth and pollution instead.

A correlation prefetcher needs the miss pattern to follow a formula

False — it needs the pattern to repeat, not to be arithmetic. It stores literal "after A comes B" pairs, so irregular-but-repeating traversals work fine.

Prefetching can never make the miss rate worse

False — pollution adds new misses (

Δ m

), so

m_{e f f} = m (1 - c) + Δ m

can exceed

m

when

Δ m > m \cdot c

Spot the error

Each item states a plausible-but-wrong claim. Find the flaw.

"Effective miss rate is

m (1 - a c)

where

a

is accuracy."

Wrong — coverage

c

already bakes in correctness and timeliness, so you subtract exactly

c

m_{e f f} = m (1 - c)

. Multiplying by accuracy double-counts.

"AMAT

= m_{e f f} \cdot t_{mi ss}

, because only misses cost time."

Wrong — every access pays

t_{hi t}

first (you always probe the cache), so

AMAT = t_{hi t} + m_{e f f} \cdot t_{mi ss}

. The hit time term is never zero.

"Since coverage is 0.6, effective miss rate is

0.6 \times m

Wrong — coverage is the fraction eliminated, so the survivors are

(1 - c)

m_{e f f} = m (1 - 0.6) = 0.4 m

, not

0.6 m

"Indexing the stride table by data address instead of PC is fine."

Wrong — two different load instructions touch different data streams; mixing them by data address corrupts each other's stride history. Index by PC (the instruction's address) so load A[i] and load B[j] stay separate.

"A useless prefetch is harmless because it's just extra fetched data."

Wrong — it consumes memory bandwidth (starving demand fetches) and can evict a live block, both of which degrade performance. Wrong prefetches are not free.

"With stride 32 and degree

D = 4

, the farthest prefetch is 32 bytes ahead."

Wrong — degree

D

is the count of lines; the farthest sits

s t r i d e \cdot D = 32 \cdot 4 = 128

bytes ahead. Distance and degree are different quantities.

"Prefetching and out-of-order execution do the same job, so you only need one."

Wrong — Out-of-Order Execution hides latency by finding independent work already in the instruction window; prefetching creates memory-level parallelism by launching fetches early. They are complementary, not redundant.

Why questions

Why is a wrong prefetch potentially worse than doing nothing?

Because it does negative work: it burns bandwidth that a real miss could have used and may evict a still-needed block, adding fresh misses (the

Δ m

term). Doing nothing costs neither.

Why do we track strides per instruction (by PC) rather than globally?

Because each load has its own access pattern; a single global stride would be corrupted whenever the program interleaves loads to different arrays. See Spatial vs Temporal Locality.

Why does stride prefetching fail on pointers but a correlation prefetcher succeeds?

A stride predictor assumes the next address equals current

+

a constant; pointer targets are stored data with no such arithmetic relation, so no constant is ever confirmed. A correlation prefetcher ignores arithmetic entirely and instead remembers the observed sequence of miss addresses — since you re-walk the same list the same way, that recorded "A then B" repeats and predicts correctly.

Why does next-line prefetching exploit spatial but not temporal locality?

Next-line assumes the neighbouring line

b + 1

is coming (spatial). Temporal locality is about revisiting the same address, which the cache handles by simply keeping the block resident — no prefetch needed. See Spatial vs Temporal Locality.

Why does prefetching help even a cache with a perfect replacement policy?

Replacement policy only decides what to keep once loaded; it cannot fetch data before it's demanded. Prefetching attacks the latency of the first touch — a different lever entirely. See Average Memory Access Time (AMAT).

Why does aggressive prefetching interact badly with limited memory bandwidth?

Prefetch requests and demand requests share the same memory bus; if the prefetcher floods it, real misses queue behind speculative ones and the CPU waits longer. This is the accuracy-vs-aggressiveness tension.

Why can prefetching raise the hit rate yet lower overall performance?

The extra bandwidth and pollution can slow the demand path and evict useful blocks; a nominally higher hit count doesn't offset the added stalls and new

Δ m

misses. Metrics must be measured end-to-end.

Why does prefetching pair naturally with out-of-order execution?

OoO exposes many in-flight loads at once (raising MLP); prefetching launches even more memory requests in parallel, so the two together keep the memory system busy while the core keeps computing. See Memory-Level Parallelism (MLP).

Why might a compiler's loop-blocking transformation reduce the need for prefetching?

Compiler Optimizations — Loop Blocking restructures loops so working sets fit in cache, cutting the miss stream itself — fewer misses means less latency to hide in the first place.

Edge cases

What does a stride prefetcher predict on the very first access to a new PC?

Nothing — with one address there is no gap to compute; it just records the address and waits for a second access to form a stride candidate.

What is the prefetcher's coverage on a purely random-access workload?

Near zero for stride/next-line — there is no exploitable pattern, so almost no miss is predicted correctly; accuracy is also low and pollution (

Δ m

) dominates.

If coverage

c = 0

and pollution

Δ m = 0

, what is

m_{e f f}

Exactly

m

— no misses eliminated and none added, so the prefetcher is a no-op for miss rate, though it may still have wasted bandwidth.

What if the prefetch degree

D = 0

No lines are fetched per trigger, so the prefetcher is effectively disabled and behaves like a plain demand-fetch cache.

For

m_{e f f}

to exceed baseline

m

, what must be true?

Pollution must outweigh the eliminated misses:

Δ m > m \cdot c

. That's the boundary where a prefetcher flips from helpful to harmful.

What does timeliness look like for a loop whose body is extremely short?

The CPU catches up fast, so prefetches must run several iterations ahead (larger distance

s t r i d e \cdot D

) or they arrive late; a too-small degree fails to hide latency.

What happens to a stride prefetcher when the stride is exactly one cache line?

It degenerates into next-line prefetching — a stride prefetcher is a strict generalization, and next-line is just the special case where the confirmed stride equals the size of one line, so the two behave identically.

First — every symbol this page uses, defined and pictured

Where the pollution term Δm comes from

Quantifying "too early" — the eviction window

True or false — justify

Spot the error

Why questions

Edge cases

Where the pollution term $Δ m$ comes from