Prefetching strategies: Question bank — Hinglish deep dive

5.4.17 · D5 · Hardware › Memory Hierarchy & Caches › Prefetching strategies

Pehle — is page ke har symbol ki definition aur picture

Kisi bhi trap se pehle, vocabulary lock kar lo. Agar neeche koi symbol fuzzy lag raha hai, toh questions samajh nahi aayenge. Figure dekho jab bhi har line padho: ye poori latency-and-metrics story ek hi canvas par draw karta hai.

Definition Symbols, simple words mein units ke saath

Block $b$ ::= ek poora cache line — contiguous bytes ka ek fixed chunk (maan lo 64 bytes). $b$ ek line index hai, toh " $b + 1$ " matlab memory mein agla line hai, na ki agla byte. $b$ ki units: lines.
Stride ::= ek load instruction ke successive addresses ke beech constant gap in bytes. for(i) A[i] pe 4-byte ints ka stride $4$ hai; A[i*8] ka stride $32$ hai. Units: bytes. Stride prefetcher ka poora kaam yahi number seekhna hai.
Prefetch degree $D$ ::= prefetcher har trigger pe kitni extra lines pull karta hai. Units: lines (ek count). Agar stride $= 32$ bytes aur $D = 4$ hai, toh sabse door wala prefetch $s t r i d e \cdot D = 128$ bytes aage hai — degree ek count hai, distance bytes mein hai.
Hit time $t_{hi t}$ ::= cycles jo har access pe cache probe karne mein lagte hain (chahe data pehle se tha ya nahi). Figure mein ye short green bar hai.
Miss penalty $t_{mi ss}$ ::= extra cycles jo tab lagte hain jab block absent tha aur slow memory se laana pada — figure mein long red bar hai.
$t_{a}$ ::= wo time (prefetch shuru hone ke moment se measure kiya) jab CPU apna demand access us block ke liye issue karta hai. Chhota $t_{a}$ = CPU ne prefetch launch hone ke thodi der baad hi pooch liya. Units: cycles. Figure mein dashed line ke roop mein mark hai.
$t_{u se}$ ::= wo time (jab se prefetched line cache mein land hui) jab CPU finally us line ko use karta hai. $t_{u se}$ tak ka gap yahi hai kitni der line idle-but-occupying-space rahi. Units: cycles.
Miss rate $m$ ::= bina prefetching ke kitne fraction accesses miss karte hain (baseline).
Effective miss rate $m_{e f f}$ ::= prefetcher ke kaam karne ke baad miss rate — jo actually slow memory tak pahunchta hai.
Coverage $c$ ::= original misses ka wo fraction jo prefetcher ne sach mein hits mein badal diya (correctness aur timeliness pehle se fold in hain). Denominator = original misses. Units: $[0, 1]$ mein ek fraction.
Accuracy $a$ ::= aapke issue kiye prefetches ka wo fraction jo eviction se pehle use ho jaate hain. Denominator = issued prefetches. Units: $[0, 1]$ mein ek fraction. Kam $a$ matlab bandwidth waste aur pollution — dhyan do iska different denominator hai coverage se.
AMAT ::= Average Memory Access Time $= t_{hi t} + m_{e f f} \cdot t_{mi ss}$ : probe har baar pay karo, penalty sirf surviving misses pe pay karo.

Pollution term $Δ m$ kahan se aata hai

Parent page pe sabse tricky formula hai $m_{e f f} = m (1 - c) + Δ m$ . Isko sirf quote nahi karte, derive karte hain. Figure panel by panel follow karo.

Formula

$m_{e f f}$ ek term at a time banana Baseline se shuru karo: har access mein se ek fraction $m$ miss karta hai (figure mein left bar).

Step 1 — jo coverage kill karta hai woh subtract karo. Coverage $c$ (upar defined) un original misses ka fraction hai jo sach mein hits mein badal gayi. Toh survivors hain $m (1 - c)$ (middle bar shrink hoti hai). Exactly $c$ subtract kyon, $a \cdot c$ nahi? Kyunki $c$ sirf wahi misses count karta hai jo correctly aur timely prefetch hue — accuracy bake in hai.
Step 2 — jo pollution create karta hai woh add karo. Har useless prefetch ne jagah banane ke liye ek abhi-live block evict kiya. Jab CPU baad mein us evicted block ko touch karta hai, toh woh miss karta hai — ek brand-new miss jo baseline mein exist nahi karta tha. Un nayi misses per access ko jod ke $Δ m$ kaho (right bar pe wapas add ki gayi red slice).
Result: $m_{e f f} = survivors m (1 - c) + pollution-induced new misses Δ m$ . $Δ m$ measure kaise hota hai? Workload prefetcher ke saath aur bina chalao; sirf prefetch-driven evictions ki wajah se hue extra demand misses, total accesses se divide karo, wahi $Δ m$ hai.

"Too early" quantify karna — eviction window

Parent warn karta hai ki zyada jaldi aana hurt kar sakta hai. Ek assertion ki jagah ek picture se isko concrete banate hain.

True ya false — justify karo

Har answer mein because hona chahiye. Sirf "true" ka koi score nahi.

A next-line prefetcher always helps performance

False — agar program mein poor spatial locality hai (random access), toh block

b + 1

rarely use hoti hai, toh prefetches bandwidth waste karte hain aur cache pollute karte hain, possibly AMAT baseline se bhi upar le jaate hain.

Coverage of 100% means the prefetcher is perfect

False — coverage sirf yeh kehta hai ki saari original misses hits ban gayin; us baare mein kuch nahi keh raha jo useless prefetches bhi fire hue, jo bandwidth cost karte hain aur pollute kar sakte hain. High accuracy bhi chahiye.

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

False — accuracy 100% matlab har issued prefetch use hua, par aapne sirf 10% misses ke liye prefetches issue kiye hon to bhi hoga, baaki 90% abhi bhi misses hain (low coverage).

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

False — ye phir bhi full miss ko partial miss mein badal sakti hai: block pehle se in flight hai, toh CPU poore

t_{mi ss}

ki jagah sirf remaining fetch time

t_{mi ss} - t_{a}

wait karta hai. Ye sirf complete win nahi hai.

A prefetch that arrives too early is always fine

False — jitna zyada use se pehle baithti hai, utne zyada intervening same-set accesses use evict kar sakte hain (timeliness failure), aur agar usne jagah banane ke liye koi live line evict ki thi toh pollution bhi hua. Dono hurt karte hain.

Stride prefetching can handle a linked-list traversal

False — next node ka address current node ke pointer field mein stored hai, toh wo literally memory mein kahin bhi ho sakta hai; stride detector ko confirm karne ke liye koi constant byte-gap nahi hai. Aapko correlation/pointer prefetcher chahiye jo "node A ke baad node B aaya" remember karta ho.

Hardware prefetching requires recompiling the program

False — ye ek dedicated engine hai jo miss stream dekh raha hai; ye unmodified binaries pe kaam karta hai. Yahi software prefetch pe iska main advantage hai.

Software prefetching costs no instruction bandwidth

False — har PREFETCHT0 ek real instruction hai jo ek slot aur decode/issue resources occupy karta hai; trade-off precision ke liye woh overhead hai.

Increasing prefetch degree

D

always increases coverage

False — ek point ke baad extra lines use hone ki probability nahi hoti (accuracy girti hai), aur ye live data evict karte hain, toh pollution (

Δ m

) gain erase kar sakti hai. Ek sweet spot hai, monotone climb nahi.

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

, replacing

c

with accuracy

a

gives the same number

False — coverage aur accuracy ke different denominators hain (misses vs issued prefetches). Accuracy

m_{e f f}

mein multiply nahi hoti; ye wasted bandwidth aur pollution govern karta hai.

A correlation prefetcher needs the miss pattern to follow a formula

False — isse pattern ka repeat hona chahiye, arithmetic hona zaruri nahi. Ye literally "A ke baad B" pairs store karta hai, toh irregular-but-repeating traversals theek kaam karte hain.

Prefetching can never make the miss rate worse

False — pollution nayi misses add karta hai (

Δ m

), toh

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

m

se exceed kar sakta hai jab

Δ m > m \cdot c

ho.

Error dhundo

Har item ek plausible-but-wrong claim batata hai. Flaw dhundo.

"Effective miss rate is

m (1 - a c)

where

a

is accuracy."

Galat — coverage

c

pehle se correctness aur timeliness bake in karta hai, toh exactly

c

subtract karo:

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

. Accuracy se multiply karna double-counting hai.

"AMAT

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

, because only misses cost time."

Galat — har access pehle

t_{hi t}

pay karta hai (cache probe toh hamesha hoga), toh

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

. Hit time term kabhi zero nahi hota.

"Since coverage is 0.6, effective miss rate is

0.6 \times m

Galat — coverage wo fraction hai jo eliminate hua, toh survivors

(1 - c)

hain:

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

, na ki

0.6 m

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

Galat — do alag load instructions alag data streams touch karte hain; unhe data address se mix karna ek doosre ki stride history corrupt kar deta hai. PC (instruction ke address) se index karo taki load A[i] aur load B[j] alag rahen.

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

Galat — ye memory bandwidth consume karta hai (demand fetches starve ho jaate hain) aur live block evict kar sakta hai, dono performance degrade karte hain. Wrong prefetches free nahi hain.

"With stride 32 and degree

D = 4

, the farthest prefetch is 32 bytes ahead."

Galat — degree

D

lines ka count hai; sabse door wala

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

bytes aage hoga. Distance aur degree alag quantities hain.

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

Galat — Out-of-Order Execution latency hide karta hai instruction window mein pehle se independent kaam dhundh ke; prefetching memory-level parallelism create karta hai fetch jaldi launch karke. Ye complementary hain, redundant nahi.

Why questions

Why is a wrong prefetch potentially worse than doing nothing?

Kyunki ye negative kaam karta hai: wo bandwidth burn karta hai jo ek real miss use kar sakti thi aur shayad abhi-zaruri block evict kar deta hai, nayi misses add karta hai (

Δ m

term). Kuch na karne se koi bandwidth bhi nahi jati aur koi cost bhi nahi.

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

Kyunki har load ka apna access pattern hota hai; ek global stride tab corrupt ho jaata jab program alag arrays ke loads interleave kare. Dekho Spatial vs Temporal Locality.

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

Stride predictor assume karta hai agla address current

+

ek constant hai; pointer targets stored data hote hain jinka koi aisa arithmetic relation nahi, toh koi constant kabhi confirm nahi hota. Correlation prefetcher arithmetic bilkul ignore karta hai aur instead miss addresses ka observed sequence yaad rakhta hai — kyunki aap same list same tarike se phir chalte ho, recorded "A phir B" repeat hota hai aur sahi predict karta hai.

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

Next-line assume karta hai neighbouring line

b + 1

aa rahi hai (spatial). Temporal locality usi address ko dubara visit karne ke baare mein hai, jise cache simply block resident rakh ke handle karta hai — koi prefetch ki zarurat nahi. Dekho Spatial vs Temporal Locality.

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

Replacement policy sirf load hone ke baad kya rakhna hai decide karta hai; ye data demand se pehle fetch nahi kar sakta. Prefetching pehle touch ki latency attack karta hai — ye bilkul alag lever hai. Dekho Average Memory Access Time (AMAT).

Why does aggressive prefetching interact badly with limited memory bandwidth?

Prefetch requests aur demand requests same memory bus share karte hain; agar prefetcher use flood kar de, toh real misses speculative ones ke peeche queue mein lag jaate hain aur CPU zyada wait karta hai. Yahi accuracy-vs-aggressiveness tension hai.

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

Extra bandwidth aur pollution demand path slow kar sakti hai aur useful blocks evict kar sakti hai; nominally higher hit count added stalls aur nayi

Δ m

misses offset nahi karta. Metrics end-to-end measure honi chahiye.

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

OoO ek saath kaafi in-flight loads expose karta hai (MLP badhata hai); prefetching aur bhi memory requests parallel mein launch karta hai, toh dono milke memory system busy rakhte hain jabki core compute karta rehta hai. Dekho Memory-Level Parallelism (MLP).

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

Compiler Optimizations — Loop Blocking loops restructure karta hai taki working sets cache mein fit ho jaayein, miss stream khud hi cut ho jaata hai — kam misses matlab pehli jagah se chhupane ke liye kam latency.

Edge cases

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

Kuch nahi — ek address se koi gap compute nahi ho sakta; ye sirf address record karta hai aur stride candidate form karne ke liye doosre access ka wait karta hai.

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

Stride/next-line ke liye near zero — koi exploitable pattern nahi hai, toh almost koi miss sahi predict nahi hoti; accuracy bhi low hogi aur pollution (

Δ m

) dominate karega.

If coverage

c = 0

and pollution

Δ m = 0

, what is

m_{e f f}

Exactly

m

— na koi miss eliminate hua na koi add hua, toh prefetcher miss rate ke liye no-op hai, halanki wo phir bhi bandwidth waste kar sakta hai.

What if the prefetch degree

D = 0

Har trigger pe koi lines fetch nahi hoti, toh prefetcher effectively disabled ho jaata hai aur plain demand-fetch cache ki tarah behave karta hai.

For

m_{e f f}

to exceed baseline

m

, what must be true?

Pollution eliminate ki gayi misses se zyada honi chahiye:

Δ m > m \cdot c

. Yahi boundary hai jahan prefetcher helpful se harmful flip ho jaata hai.

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

CPU jaldi pakad leta hai, toh prefetches kaafi iterations aage run karni chahiye (bada distance

s t r i d e \cdot D

) warna late pahunchti hain; bahut chhota degree latency hide karne mein fail karta hai.

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

Ye next-line prefetching mein degenerate ho jaata hai — stride prefetcher ek strict generalization hai, aur next-line sirf woh special case hai jahan confirmed stride ek line ke size ke barabar hai, toh dono identically behave karte hain.