5.4.17
Intuition Ek-line ka ideaJab bhi cache ko slow memory se data laana padta hai, CPU ruk jaata hai. Prefetching ek trick hai jisme ==aap guess karte ho ki aage kya data chahiye hoga aur use pehle se fetch kar lete ho, taaki jab CPU actually maange tab woh pehle se cache mein baith chuka ho==.
Modern CPUs ~4 GHz pe chalte hain (≈0.25 ns per cycle), lekin DRAM miss ki cost hoti hai ~100 ns ≈ 400 cycles . Agar aapka program har kuch instructions pe nayi memory touch karta hai, toh CPU apni zyaadatar zindagi wait karte hua guzaarta hai.
Ek plain demand-fetch cache sirf react karta hai: woh ek block miss ke baad load karta hai. Matlab aap har baar poori miss penalty bhugte ho. Prefetching ek reactive cache ko proactive bana deta hai — woh memory latency ko useful computation ke saath overlap karta hai.
GOAL kya hai? Ek miss ko hit mein convert karo — block pehle se present ho — ya kam se kam poori miss ko partial miss banao (data "in flight" hota hai jab request aati hai, toh wait kam hota hai).
Intuition Do alag denominators — inhe mix mat karo!Coverage original misses par measure hoti hai (kitni miss khatam ki?). Accuracy issue ki gayi prefetches par measure hoti hai (kitni issue karne layak thin?). Ye dono alag sawaalon ke jawab dete hain. Ek prefetcher ki high coverage lekin low accuracy ho sakti hai (zyaadatar misses khatam karta hai lekin bahut saari bekar prefetches bhi fire karta hai), ya ulta bhi ho sakta hai.
Intuition Accuracy itni important kyun haiEk galat prefetch free nahi hoti! Woh memory bandwidth waste karti hai aur cache pollute kar sakti hai — kisi useful block ko bahar nikal ke. Toh ek aggressive lekin inaccurate prefetcher performance ko worse bana sakta hai. Yahi central tension hai.
Definition Next-line prefetchBlock b == b + 1 == b + 2 , … prefetch degree D count ).
Kaam kyun karta hai: programs mein spatial locality hoti hai — arrays, code streams, struct fields contiguous layout mein hote hain. Agar aapne ek cache line ka byte 0 touch kiya, toh bahut zyaada chances hain ki aap jaldi next line bhi touch karoge.
Benefit kaise derive karein. Maano:
m c coverage = original misses ka woh fraction jo prefetching se successfully hits mein badal jaata hai (yeh ek number hi correctness aur timeliness dono account karta hai),t hi t t mi ss
Coverage c effective miss rate simply hai:
m e f f = m ⋅ ( 1 − c )
Average memory access time (first principles se: time = hits × hit-cost + misses × miss-cost):
AMAT = t hi t + m e f f ⋅ t mi ss
Real loops sirf 1 se nahi chalte. for(i) A[i*8] ek fixed stride se chalta hai. Ek stride prefetcher woh constant gap seekhta hai.
Definition Stride prefetcher — aur "degree" ka matlab yahanHar load instruction ke liye (PC se track kiya jaata hai ek Reference Prediction Table mein), store karo: last address, last stride, aur ek confidence state. Jab stride confirm ho jaaye, tab D == a dd r + s t r i d e ⋅ k == , k = 1 , 2 , … , D D prefetch degree = har trigger pe fetch ki jaane wali lines ki count (bilkul next-line jaisa matlab). Sabse door prefetch ki distance ahead hai s t r i d e ⋅ D lines ki count , aur "distance" = kitna door bytes mein ; multiplier k 1.. D
PC se track kyun karein? Alag load instructions ke alag access patterns hote hain. Table ko instruction address se index karne par "load A[i]" ka stream "load B[j]" se alag ho jaata hai, taaki unke strides ek doosre ko corrupt na karein.
Intuition Jab koi stride nahi hotaLinked lists, trees, hash tables: agle node ka address ka koi arithmetic pattern nahi hota — woh jo bhi pointer kahe. Stride prefetching bilkul fail ho jaata hai.
Definition Correlation prefetcherPairs record karo: "A miss ke baad, B miss hone ka pattern tha." Inhe ek table mein store karo. Agli baar jab A pe miss ho, B prefetch karo. Yeh irregular lekin repeating miss sequences capture karta hai.
Kaise/Kyun: irregular data structures phir bhi usi tarah traverse hote hain baar baar (aap usi list pe chalta hai). Miss addresses ki history repeat hoti hai, chahe woh koi formula na ho.
Definition Software prefetchCompiler/programmer ek explicit instruction insert karta hai (jaise x86 PREFETCHT0 [addr]) jo hint deta hai "ise cache mein lao." Ek instruction slot ki cost lagti hai lekin kaafi targeted hota hai.
Definition Hardware prefetchEk dedicated engine miss stream watch karta hai aur automatically prefetch karta hai — koi code changes nahi, lekin woh sirf wahi patterns detect kar sakta hai jinke liye design kiya gaya hai.
Software
Hardware
Program semantics jaanta hai
✅
❌
Instruction bandwidth kharach karta hai
✅ (haan)
❌ (nahi)
Runtime pe adapt karta hai
❌
✅
Irregular pointers handle karta hai
✅ (manually)
sirf correlation prefetchers
Worked example Example 1 — Next-line se AMAT improvementBaseline: t hi t = 1 t mi ss = 100 m = 0.05 coverage c = 0.6 achieve karta hai (60% misses sach mein hits mein badal jaate hain) negligible pollution ke saath.
Step 1: m e f f = m ( 1 − c ) = 0.05 ( 1 − 0.6 ) = 0.02 Yeh step kyun? Coverage define ki gayi hai actually eliminate hue misses ke roop mein, toh hum exactly woh fraction subtract karte hain — koi extra accuracy factor yahan nahi chahiye.
Step 2: AMAT ba se = 1 + 0.05 ⋅ 100 = 6 Step 3: AMAT p f = 1 + 0.02 ⋅ 100 = 3 Kyun? Wohi formula, chhhota effective miss rate.
Result: memory access pe speedup = 6/3 = 2 ×
Worked example Example 2 — Jab prefetching HURT karta hai (accuracy vs coverage split)Ab prefetcher bahut saari misses ke liye prefetch issue karta hai, lekin sirf coverage c = 0.18 misses actually eliminate hoti hain (issued prefetches pe poor accuracy matlab zyaadatar bekar fire hoti hain). Aur bura, har useless prefetch ek live line evict karta hai, pollution Δ m = 0.03 .
m e f f = m ( 1 − c ) + Δ m = 0.05 ( 1 − 0.18 ) + 0.03 = 0.05 ⋅ 0.82 + 0.03 = 0.041 + 0.03 = 0.071 Yeh step kyun? Sirf truly-eliminated fraction (c inaccurate prefetches help nahi karti lekin karti hain pollution ke zariye fresh misses add.
AMAT = 1 + 0.071 ⋅ 100 = 8.1 bura !
Lesson: low accuracy coverage ko shrink karta hai aur pollution add karta hai — net loss.
Worked example Example 3 — Stride detection trace (degree = number of lines)PC = 0x400 par load instruction access karti hai: 1000, 1032, 1064, 1096.
Access 1000 → koi history nahi, record karo.
1032 → stride candidate = 32. Confidence low.
1064 → 1064 − 1032 = 32
1096 → phir confirm hua.
Degree D = 4 ke saath (har trigger pe 4 lines fetch karo), 1096 access ke baad hum 1096 + 32 ⋅ k k = 1 , 2 , 3 , 4 1128 , 1160 , 1192 , 1224 Degree kyun matter karta hai: D lines ki count hai; sabse door prefetch s t r i d e ⋅ D = 32 ⋅ 4 = 128
Common mistake "Coverage aur accuracy ek hi cheez hain (yam e f f Kyun sahi lagta hai: dono "prefetcher kitna achha hai" jaisa sunai deta hai, toh lagta hai m e f f = m ( 1 − a ⋅ c ) Kyun galat hai: inke different denominators hain. Coverage original misses pe hai (pehle se sirf successful wale count karta hai); accuracy issued prefetches pe hai (bandwidth/waste metric). Coverage akela deta hai m e f f = m ( 1 − c ) Fix: pehle apni definition decide karo, phir double-count mat karo.
Common mistake "Zyaada prefetching hamesha better hai."Kyun sahi lagta hai: zyaada prefetches → zyaada hits, intuitively. Kyun galat hai: har prefetch bandwidth consume karti hai aur live data evict kar sakti hai (pollution). Ek point ke baad, extra prefetches prevent karne se zyaada misses cause karti hain (dekho Example 2). Fix: degree tune karo aur throttle karne ke liye confidence/accuracy feedback use karo.
Common mistake "Jo prefetch use hui = ek achhi prefetch."Kyun sahi lagta hai: use hui, toh help ki! Kyun incomplete hai: agar woh late pahunchi (data requested hone par abhi bhi in flight tha) toh aap phir bhi stall hue — timeliness matter karti hai. Agar bahut jaldi pahunchi toh shayad evict ho gayi aur phir re-fetch hui. Fix: sirf accuracy nahi, timeliness bhi measure karo.
Common mistake "Stride prefetchers linked lists handle karte hain."Kyun sahi lagta hai: yeh modern fancy prefetcher hain. Kyun galat hai: pointer-chasing addresses ka koi constant stride nahi hota. Fix: irregular structures ke liye correlation / pointer-content prefetchers use karo.
Recall Kisi 12-saal ke bachche ko samjhaoSocho tum ek comic book padh rahe ho. Har page ek-ek karke apne dost se maangne ke bajaay (kitna slow!), tera dost notice karta hai ki tu hamesha agle page pe jaata hai — toh woh page 5 pehle se ready kar leta hai, tab tak jab tu page 4 khatam karta hai. Yeh hai next-line prefetching . Agar tu har baar 3 pages skip karta hai, woh woh gap seekh leta hai (yeh hai stride ). Agar teri comic randomly jump karti hai lekin hamesha usi tarah — page 2 phir page 9 phir page 4 — toh woh woh path yaad kar leta hai (yeh hai correlation ). Khatre ki baat: agar woh galat guess kare, toh woh woh pages utha leta hai jo tu nahi chaahta aur jo tu chaahta tha unhe drop kar deta hai — ab tu aur slow ho gaya. Toh use zyaadatar sahi guess karna chahiye, aur bilkul sahi time pe .
Mnemonic Strategies yaad rakho:"Nice Students Chase Pointers"
N ext-line → S tride → C orrelation → P ointer/software. Simple → complex, regular → irregular. Aur inhe judge karo C.A.T. se = C overage (of misses), A ccuracy (of prefetches), T imeliness.
Prefetching kaun si problem solve karta hai? CPU speed aur DRAM latency ke beech ka bada gap — miss penalty hide karta hai data ko demand se pehle fetch karke.
Coverage vs accuracy — denominator mein kya fark hai? Coverage = original misses ka fraction jo eliminate hua; Accuracy = issued prefetches ka fraction jo actually use hua. Alag denominators, alag sawaal.
Prefetching performance worse kyun bana sakta hai? Inaccurate prefetches bandwidth waste karti hain aur cache pollute karti hain (useful blocks evict karti hain), nayi misses add karti hain (pollution term Δm).
Next-line prefetching kya karta hai aur kaam kyun karta hai? Block b ko access karne par block b+1 fetch karta hai; spatial locality ki wajah se kaam karta hai (contiguous arrays/code).
Stride prefetcher ko PC (instruction address) se index kyun kiya jaata hai? Alag load instructions ke access streams ko alag karne ke liye taaki unke strides ek doosre ko corrupt na karein.
Stride prefetching fail kab karta hai, aur uski jagah kya aata hai? Pointer-chasing/irregular structures pe (koi constant stride nahi); correlation/pointer prefetchers uski jagah aate hain.
Coverage se effective miss rate formula likho. m e f f = m ( 1 − c ) + Δ m
Prefetch degree D kya hai, aur distance ahead kya hai? Degree D = har trigger pe fetch ki jaane wali lines ki count; sabse door ki distance ahead = stride·D (bytes mein).
Software vs hardware prefetch: ek-ek advantage. Software program semantics jaanta hai/irregular access handle karta hai; hardware koi instruction slots consume nahi karta aur runtime pe adapt karta hai.
Ek prefetch use hui lekin phir bhi stall hua — kya galat hua? Timeliness — woh bahut late pahunchi (data demand karne par abhi bhi in flight tha).
Slow DRAM miss ~400 cycles
Demand-fetch cache reactive
Wastes bandwidth and pollutes cache
