WHAT is the goal? Convert a miss into a hit by having the block already present, or at least turn a full miss into a partial miss (data is "in flight" when requested, so you wait less).
WHY it works: programs have spatial locality — arrays, code streams, struct fields are laid out contiguously. If you touched byte 0 of a cache line, you'll very likely touch the next line soon.
HOW to derive the benefit. Let:
m = baseline miss rate (fraction of accesses that miss),
c = coverage = fraction of original misses that are successfully turned into hits by prefetching (this single number already accounts for correctness and timeliness),
thit = hit time, tmiss = miss penalty.
Coverage c directly tells us what fraction of misses disappear. So the effective miss rate is simply:
meff=m⋅(1−c)
Average memory access time (from first principles: time = hits × hit-cost + misses × miss-cost):
WHY track by PC? Different load instructions have different access patterns. Indexing the table by the instruction address separates the stream of "load A[i]" from "load B[j]", so their strides don't corrupt each other.
HOW/WHY: irregular data structures still get traversed the same way repeatedly (you walk the same list). The history of miss addresses repeats even if it isn't a formula.
Imagine you're reading a comic book. Instead of asking your friend for each page one at a time (slow!), your friend notices you always flip to the next page — so he already has page 5 ready before you finish page 4. That's next-line prefetching. If you skip 3 pages each time, he learns that gap (that's stride). If your comic jumps randomly but always the same way — page 2 then page 9 then page 4 — he memorizes that path (that's correlation). The danger: if he guesses wrong, he grabs pages you don't want and drops the ones you do — now you're slower. So he must guess often right, and just in time.
The huge gap between CPU speed and DRAM latency — it hides miss penalty by fetching data before it's demanded.
Coverage vs accuracy — what's the difference in denominator?
Coverage = fraction of original misses eliminated; Accuracy = fraction of issued prefetches actually used. Different denominators, different questions.
Why can prefetching make performance worse?
Inaccurate prefetches waste bandwidth and pollute the cache (evict useful blocks), adding new misses (pollution term Δm).
What does next-line prefetching do and why does it work?
Fetches block b+1 on access to b; works due to spatial locality (contiguous arrays/code).
Why is a stride prefetcher indexed by PC (instruction address)?
To separate different load instructions' access streams so their strides don't corrupt each other.
When does stride prefetching fail, and what replaces it?
On pointer-chasing/irregular structures (no constant stride); correlation/pointer prefetchers replace it.
Write the effective miss rate formula using coverage.
meff=m(1−c)+Δm where c=coverage (misses eliminated), Δm=pollution.
What is prefetch degree D, and what is distance ahead?
Degree D = number of lines fetched per trigger; distance ahead of the farthest = stride·D (bytes).
Software vs hardware prefetch: one advantage each.
Software knows program semantics/handles irregular access; hardware costs no instruction slots and adapts at runtime.
A prefetch was used but you still stalled — what went wrong?
Timeliness — it arrived too late (data still in flight when demanded).
Dekho, CPU bahut fast hai (~4 GHz) lekin DRAM se data lane me ~100 ns lagta hai — matlab ~400 cycles CPU bas wait karta rehta hai jab cache miss hota hai. Prefetching ka idea simple hai: data ko pehle se le aao, CPU ke maangne se pehle. Jab CPU actually maange, to woh already cache me ready ho — miss ko hit me convert kar diya!
Strategies ka progression aisa hai: Next-line (block b touch kiya to b+1 bhi le aao — spatial locality), phir Stride (loop fixed gap se chalta hai jaise A[i*8], gap seekh lo, PC ke hisaab se track karke), phir Correlation/pointer (linked list/tree me arithmetic pattern nahi hota, to "A ke baad B aata tha" yaad rakho). Yahan ek important cheez: degree D ka matlab hai kitni lines ek baar me prefetch karni hain (count), aur kitni door prefetch pahunchti hai woh hai stride⋅D bytes — degree count hai, distance bytes hai. Dono confuse mat karo.
Sabse zaroori: coverage aur accuracy alag cheezein hain, denominator alag hai. Coverage = original misses me se kitne actually khatam hue (yeh already batata hai kitne prefetch sahi the). Accuracy = jitne prefetch issue kiye unme se kitne kaam aaye (bandwidth waste ka metric). Isiliye formula hai meff=m(1−c)+Δm — sirf coverage subtract karo, accuracy ko dobara multiply mat karo (woh galti hai!). Agar prefetcher inaccurate hai to coverage kam ho jaati hai aur pollution Δm badhti hai, jis se AMAT ulta badh sakti hai. C.A.T. yaad rakho: Coverage, Accuracy, Timeliness.
