Prefetching strategies: Visual walkthrough — Hinglish deep dive

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

Hum assume karte hain ki aapne pehle kabhi $m$ , $c$ , ya "AMAT" nahi dekha. Inme se har ek pehle ek picture hoga, tab ek symbol.

Step 1 — Ek single memory access mein actually kitna cost lagta hai

KYA. Socho CPU cache se ek piece of data maang raha hai. Do cheezein ho sakti hain. Ya toh data cache mein pehle se hi pada hai — woh ek hit hai — ya woh wahan nahi hai aur use slow main memory se kheench ke laana padega — woh ek miss hai.

WHY yahan se shuru karein. Average time ke baare mein har formula actually sirf in do outcomes ka weighted average hai. Agar hum yeh nail nahi karte ki har outcome mein kitna cost lagta hai, toh baad mein kuch bhi samajh nahi aayega.

PICTURE. CPU se nikalne wali do roads. Chhoti blue road (hit) fast hai. Lambi pink road (miss) seedha DRAM tak jaati hai aur wapas aati hai.

Step 2 — "Kabhi kabhi miss" ko ek number mein convert karna: miss rate $m$

KYA. CPU jo bhi accesses karta hai, unmein se kuch fraction misses hote hain. Us fraction ko $m$ (miss ke liye) kaho. Agar $m = 0.05$ hai, toh matlab har 100 accesses mein se 5 miss hote hain.

WHY fraction aur count nahi? Kyunki programs billions of accesses karte hain. Hum har ek ke baare mein reason nahi kar sakte. Lekin ek fraction hume "ek typical access" ke baare mein baat karne deta hai — aur averages exactly woh hain jo hume designs compare karne ke liye chahiye.

PICTURE. 100 chhote access-squares ki ek strip. Blue wale hits hain, pink wale misses hain. Pink wale total ke $m$ hain; blue wale $1 - m$ hain.

AMAT Average Memory Access Time (AMAT) ka short form hai — literally ek access mein average time kitna lagta hai.

Step 3 — Prefetching: CPU ke maangne se pehle ek pink square fetch karna

KYA. Ek prefetcher guess karta hai ki CPU aage kaun sa block chaahega aur use pehle se load karna shuru karta hai, jab CPU abhi bhi doosre kaam mein busy hai. Agar guess sahi hai aur woh time pe aa jaata hai, toh jab CPU finally maangta hai — block pehle se wahan hota hai. Ek square jo pink hota woh blue ho jaata hai.

WHY yeh kuch bhi help karta hai? Kyunki slow memory trip ab useful computation ki chhaya mein hoti hai, CPU ko stall karne ki jagah. Yeh overlap isliye kaam karta hai kyunki prefetching Memory-Level Parallelism (MLP) aur Out-of-Order Execution jaise ideas par rely karta hai — CPU kaam karta rehta hai jab fetch in-flight hoti hai.

PICTURE. Step 2 ki wahi strip, lekin ab kuch pink squares ek chhote "prefetch engine" dwara blue repaint ho rahe hain jo jis access ko service kar raha hai usse aage reach karta hai.

Step 4 — Coverage $c$ aur accuracy $a$ : do honest numbers

KYA. Prefetcher do alag-alag cheezein karta hai, isliye hume do fractions chahiye, har ek ka apna denominator:

WHY aise define karte hain. Coverage original misses — pink squares — ke upar measure hoti hai. Isme "kya guess sahi tha?" aur "kya woh time pe aa gaya?" dono fold ho jaate hain: prefetch sirf coverage ki taraf count hoti hai agar miss sach mein gayab ho gayi. Isliye coverage akele benefit drive karta hai.

PICTURE. Pink misses lo aur unhe do piles mein baanto: woh $c$ portion jo save ho gaye (blue repaint) aur woh $1 - c$ portion jo pink rehe kyunki prefetcher ne unhe miss kiya.

Step 5 — $m_{e f f}$ ko AMAT mein plug karo

KYA. Step 2 ka AMAT formula shape nahi badlata — hum bas isme chhota miss rate daal dete hain.

WHY. Hits ke baare mein ya miss ke cost ke baare mein kuch nahi badla. Sirf yeh badla ki kitne misses bachte hain. Isliye hum $m \to m_{e f f}$ swap karte hain aur baaki sab waise hi chodh dete hain.

PICTURE. Do bars side by side: baseline AMAT (lamba pink miss-portion) aur prefetched AMAT (chhota pink miss-portion). Blue $t_{hi t}$ base dono mein identical hai; sirf pink stack shrink hoti hai.

Yeh wahi locality-driven win hai jis par Cache Basics — Blocks and Locality aur Spatial vs Temporal Locality rely karte hain — prefetching bas us locality par pehle act karta hai.

Step 6 — $Δ m$ kahan se aata hai: accuracy se pollution ko model karna

KYA. Ek prefetch jo galat guess karta hai woh phir bhi ek cache line occupy karta hai. Jagah banane ke liye, woh ek live block ko evict kar sakta hai — jise CPU reuse karne wala tha. Woh eviction ek brand-new miss create karta hai jo hoti hi nahi agar prefetch na hota. Accesses ka woh fraction jo is tarah fresh misses mein convert ho jaata hai woh $Δ m$ hai, pollution term. Yeh koi magic constant nahi hai — hum model kar sakte hain ki yeh kahan se aata hai.

WHY iska apna step chahiye. Pehle ka har case cheez ko better ya neutral banata tha. Yeh woh case hai jahan prefetching cheez ko worse banata hai, aur reader ko kabhi bhi isse surprised nahi hona chahiye. Yahan Step 4 ka accuracy $a$ finally apna kaam karta hai.

PICTURE. Ek galat prefetch (pink-striped) ek full cache set mein ghus raha hai aur ek blue live block ko bahar nikal raha hai — woh ejected block ek naya pink square ban jaata hai jo pehle nahi tha.

Formula

$Δ m$ ka ek concrete model Maan lo prefetcher $p$ prefetches per access issue karta hai (uska issue rate). Accuracy $a$ ki definition se, $a$ fraction useful hain aur $(1 - a)$ fraction waste hain. Har wasted prefetch ek live block ko evict kar sakta hai; $ϕ$ woh fraction ho jo wasted prefetches ka actually ek jald-reused line displace karta hai (yeh cache associativity aur replacement policy par depend karta hai — Cache Pollution and Replacement Policies dekho). Tab $fresh misses per access Δ m = prefetches issued/access p \cdot fraction wasted (1 - a) \cdot fraction jo live line evict karte hain ϕ$

Dependencies seedhe padho: zyada aggressive prefetching (higher $p$ ) → zyada pollution; less accurate ( $a$ chhota) → zyada pollution; higher associativity ya smarter replacement policy (chhota $ϕ$ , kyunki victims ke live hone ka chance kam) → kam pollution. Ideal limits $a = 1$ (perfectly accurate) ya $ϕ = 0$ (kabhi live line evict nahi karta) mein $Δ m = 0$ milta hai.

Step 7 — Do boundary cases (sanity checks)

KYA. $c$ ko extreme tak push karo aur confirm karo ki formula theek behave karta hai.

WHY. Ek formula jis par aap trust karte ho use edges par obvious answer dena chahiye. Agar nahi deta, toh aapne galat banaya.

PICTURE. $c$ ke liye ek slider $0$ se $1$ tak, AMAT bar shrink karta hua jaise slider right slide karta hai.

Perfect prefetcher, $c = 1$ , $Δ m = 0$ : $m_{e f f} = m (1 - 1) = 0$ , isliye $AMAT = t_{hi t}$ . Har miss khatam → aap sirf probe cost pay karte ho. Sabse best possible outcome.
Useless prefetcher, $c = 0$ , $Δ m = 0$ : $m_{e f f} = m (1 - 0) = m$ , isliye $AMAT = t_{hi t} + m t_{mi ss}$ — exactly Step 2 ka baseline. Kuch nahi karna kuch nahi badalta. Achha: formula backward-compatible hai.
Actively harmful, $c = 0$ , $Δ m > 0$ : $m_{e f f} = m + Δ m > m$ → baseline se strictly worse, Step 6 se match karta hua.

Ek-picture summary

Figure har symbol ko ek visual element se map karta hai: full strip saare accesses hain; blue squares hits hain aur pink squares misses hain ( $m$ = pink fraction, $t_{mi ss}$ ko feed karta hai); coverage $c$ pink ka ek labelled slice blue repaint karta hai (benefit, arrow tagged $c$ ); pollution $Δ m = p (1 - a) ϕ$ kuch naaye striped-pink squares wapas smuggle karta hai (cost, arrow tagged $Δ m$ ); hamesha present blue base band $t_{hi t}$ hai. Jo bachta hai woh $m_{e f f} = m (1 - c) + Δ m$ hai, aur bottom line full AMAT spell karta hai.

Recall Feynman retelling — plain words mein bolo

Har baar jab CPU data chahta hai, woh ek door knock karne jaisa hai. Usually koi ghar pe hota hai (ek hit, sasta). Kabhi kabhi koi ghar pe nahi hota aur tumhe unhe fetch karne ke liye town cross karna padta hai (ek miss, mahenga). Miss rate $m$ bas yeh hai ki koi ghar pe nahi hota kitni baar.

Ek prefetcher ek helpful assistant hai jo guess karta hai ki tumhe aage kise chahiye aur unhe pehle se bula leta hai, taaki jab tum knock karo toh woh pehle se ghar pe hon. Coverage $c$ woh fraction hai ki "koi ghar pe nahi" situations mein se kitni assistant ne successfully fix kiin, isliye surviving misses $m$ se $m (1 - c)$ ho jaate hain. Accuracy $a$ ek alag score hai: un logon mein se jinhe assistant ne bulaya, kitne actually chahiye the — yeh tumhe directly help nahi karta, lekin low $a$ matlab bahut saare unwanted guests, aur unwanted guests un logon ko dhakka dete hain jinhe tumhe chahiye tha. Yeh pollution $Δ m$ hai, jo badhta hai kitni aggressively assistant bulata hai ( $p$ ), kitni baar galat hota hai ( $1 - a$ ), aur dhakka khaane waala kitna matter karta tha ( $ϕ$ , cache associativity aur replacement policy se set hota hai).

Isliye true surviving miss rate $m (1 - c) + Δ m$ hai, aur $AMAT = t_{hi t} + m_{e f f} t_{mi ss}$ . Ek last honesty note: $t_{mi ss}$ really fixed nahi hai — overlapping trips (MLP) ise chhota karte hain, jabki bahut zyada prefetches se bandwidth contention ise bada karta hai. Jab $c = 1$ tum heaven mein ho ( $AMAT = t_{hi t}$ ); jab $c = 0, Δ m = 0$ kuch nahi badla; jab assistant galat guess kare toh tum koi assistant na hone se bhi worse ho.

Recall Self-test

$t_{hi t}$ AMAT mein kaisa appear karta hai aur ise fraction se multiply kyun nahi kiya jaata? ::: Har access cache probe karta hai, isliye saare accesses $t_{hi t}$ pay karte hain; yeh ek flat additive cost hai, hit/miss par conditional nahi. Benefit term $m (1 - c)$ kyun hai aur $m (1 - a c)$ nahi? ::: Coverage $c$ original misses pe define ki gayi hai jo actually eliminate huin — correctness aur timeliness pehle se hi iske andar hain; accuracy $a$ cost side ( $Δ m$ ) par belong karta hai, benefit side par nahi. $Δ m$ ka model do aur bolo ki har factor kis par depend karta hai. ::: $Δ m = p (1 - a) ϕ$ : $p$ = issue rate (aggressiveness), $1 - a$ = wasted-prefetch fraction (accuracy), $ϕ$ = chance ki ek wasted prefetch ek live line evict kare (associativity + replacement policy). $t_{mi ss}$ sirf ek approximation kyun hai? ::: Overlapping misses/prefetches (MLP) felt per-miss penalty reduce karte hain, jabki bandwidth contention ise raise karta hai — yeh ek effective average hai, constant nahi. $c = 1, Δ m = 0$ par AMAT kya hai? ::: $t_{hi t}$ — har miss khatam ho jaati hai, isliye sirf probe cost bachti hai.

Yeh bhi dekho: Compiler Optimizations — Loop Blocking code ko restructure karne ke liye taaki prefetcher jo accesses dekhta hai woh pehli jagah predictable ho jaayein.