Prefetching strategies: Worked examples — Hinglish deep dive

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

Yeh parent topic ka practice deck hai. Parent ne tools banaye the: coverage $c$ , accuracy $a$ , effective miss rate $m_{e f f}$ , aur AMAT. Yahaan hum inhe har us case pe drill karte hain jo ek problem mein aa sakta hai — good cases, harmful cases, degenerate cases, aur woh exam trick jo logon ko pakad leti hai.

Neeche har cheez sirf un symbols se hai jo parent ne define ki. Ek quick reminder, simple words mein:

Definition Chaar numbers (plus ek), words mein

$m$ ::= miss rate = har access mein se, woh fraction jo miss hota hai (data cache mein nahi). 0 aur 1 ke beech ek pure number.
$c$ ::= coverage = original misses mein se, woh fraction jo prefetcher actually hits mein badal deta hai. Isme "kya yeh correct tha aur time pe tha?" bhi shaamil hai.
$a$ ::= accuracy = hamare issue kiye prefetches mein se, woh fraction jo eviction se pehle actually use hua. Wasted bandwidth measure karta hai — yeh $m_{e f f}$ mein enter nahi hota.
$Δ m$ ::= pollution = extra nayi misses jo isliye bani kyunki ek useless prefetch ne ek live block ko evict kar diya. Yeh add hoti hai, subtract nahi.
$D$ ::= prefetch degree = ek trigger par fetch ki gayi lines ki count (wohi matlab jo parent ne diya tha). Ise hum Ex 6 mein use karte hain yeh decide karne ke liye ki kitni lines aage rakhni hain.

Scenario matrix

Har prefetching problem in cells mein se kisi ek mein hoti hai. Baad ke examples mein har ek apna cell naam leta hai, isliye end tak koi bhi cell blank nahi rehti.

Cell	Kya khaas hai	Sign/limit stress point	Example
A. Clean win	acchi coverage, koi pollution nahi	$Δ m = 0$ , $c$ bada	Ex 1
B. Net loss	low coverage + pollution	$Δ m > 0$ , chhota $c$	Ex 2
C. Break-even	benefit exactly pollution cancel karta hai	tipping $Δ m$ ke liye solve karo	Ex 3
D. Degenerate: $c = 0$	prefetcher kuch nahi karta	$c \to 0$ limit	Ex 4
E. Degenerate: $c = 1$	prefetcher sab misses khatam karta hai	$c \to 1$ limit	Ex 5
F. Stride geometry	ek stride seekho, $D$ lines aage rakho	negative stride bhi shaamil	Ex 6
G. Accuracy trap	$a$ diya hai lekin multiply NAHI karna	$a$ ko $c$ se alag rakho	Ex 7
H. Real-world word problem	accuracy se bandwidth budget	wasted-fetch counting	Ex 8
I. Exam twist	irregular / pointer chase, koi stride nahi	stride prefetch = 0 coverage	Ex 9

Worked examples

Worked example Ex 1 — Cell A: the clean win

$t_{hi t} = 1$ , $t_{mi ss} = 200$ cycles, $m = 0.04$ . Ek next-line prefetcher coverage $c = 0.75$ paata hai bina kisi pollution ke ( $Δ m = 0$ ).

Forecast: aage padhne se pehle nayi AMAT guess karo. Bada $c$ → chhota $m_{e f f}$ → chhota AMAT. Kya yeh roughly half hoga?

$m_{e f f} = m (1 - c) + Δ m = 0.04 (1 - 0.75) + 0 = 0.04 \cdot 0.25 = 0.01$ . Yeh step kyun? Coverage defined hai as actually eliminate ki gayi misses, isliye exactly woh fraction subtract karo. Koi accuracy factor multiply nahi hota.
$AMAT_{ba se} = 1 + 0.04 \cdot 200 = 9$ cycles. Kyun? Baseline: koi prefetching nahi, full miss rate penalty pay karta hai.
$AMAT_{p f} = 1 + 0.01 \cdot 200 = 3$ cycles. Kyun? Same formula, chhota $m_{e f f}$ .

Verify: speedup $= 9/3 = 3 \times$ . Sanity: $m$ ek chauthai ho gaya, aur miss-cost term ( $0.04 \cdot 200 = 8$ ) $0.01 \cdot 200 = 2$ ho gayi. Fixed $t_{hi t} = 1$ ise full $4 \times$ nahi hone deta. ✅

Worked example Ex 3 — Cell C: break-even, tipping point ke liye solve karo

Same machine, coverage fixed at $c = 0.50$ . Question: kitna pollution $Δ m$ prefetching ko exactly break even karwata hai (AMAT equals baseline)?

Forecast: agar aadhi misses mar jaayein, toh hamare paas kuch pollution absorb karne ka "budget" hai. Crossover $Δ m$ guess karo.

Break-even ka matlab hai $m_{e f f} = m$ (same effective miss rate ⇒ same AMAT). Kyun? AMAT $m_{e f f}$ par sirf doosre term ke through depend karta hai; equal $m_{e f f}$ ⇒ equal AMAT.
$m (1 - c) + Δ m = m \Rightarrow Δ m = m - m (1 - c) = m \cdot c$ . Kyun? Algebra: jo benefit humne gain kiya woh exactly $m \cdot c$ hai; us amount tak pollution bas use cancel karta hai.
$Δ m = 0.04 \cdot 0.50 = 0.02$ . Yeh step kyun? Hum step 2 ke formula $Δ m = m \cdot c$ mein given numbers ( $m = 0.04$ , $c = 0.50$ ) substitute karte hain concrete tipping value paane ke liye.

Verify: $Δ m = 0.02$ ke saath: $m_{e f f} = 0.04 \cdot 0.5 + 0.02 = 0.02 + 0.02 = 0.04 = m$ . Baseline se identical. ✅ Rule of thumb: pollution $m \cdot c$ se neeche rehna chahiye warna tum lose karte ho.

Worked example Ex 6 — Cell F: stride geometry,

negative stride bhi shaamil hai PC 0x800 par ek load in addresses (bytes) ko touch karta hai: 2016, 1984, 1952, 1920. Cache line = 32 bytes. Prefetch degree $D = 3$ .

Alignment ke baare mein note: yahaan har address $32$ ka multiple hai ( $2016 = 63 \cdot 32$ , $1984 = 62 \cdot 32$ , …), isliye har ek already apne 32-byte cache line ke start par hai. Real hardware mein ek address jo ek line ke andar land karta hai use pehle line start par round down kiya jaata hai (low 5 bits drop karo, kyunki $32 = 2^{5}$ ) stride math se pehle; yahaan line-aligned addresses choose karne se hum extra rounding ke bina stride logic par focus kar sakte hain.

Forecast: addresses neeche ja rahe hain. Kya stride $+ 32$ hoga ya $- 32$ ? Prefetches kahan land hote hain?

Stride $= addr_{2} - addr_{1} = 1984 - 2016 = - 32$ . Yeh step kyun? Stride newest minus previous hota hai. Descending walk ek negative stride deta hai — arithmetic identical hai, sirf sign flip hota hai.
Confirm karo: $1952 - 1984 = - 32$ ✓, $1920 - 1952 = - 32$ ✓. Stride $- 32$ par confirmed. Kyun? Do matching gaps confidence kaafi raise karte hain prefetch karne ke liye (jaisa parent ke RPT mein tha).
Last address $1920$ se $k = 1, 2, 3$ ke liye $addr + stride \cdot k$ prefetch karo: $1920 + (- 32) \cdot k = 1888, 1856, 1824.$ Kyun? Same formula $a dd r + s t r i d e \cdot k$ ; negative stride prefetches ko backward bhejta hai. Har result phir se $32$ ka multiple hai, isliye har prefetched line line-aligned hai.

Figure — aise padho: cyan dots (top row) woh addresses hain jo CPU already touch kar chuka hai, leftward (address mein neeche) march karte hue. Amber squares (bottom row) woh teen prefetches hain jo engine loop se aage fire karta hai, aur white arrows har ek ko newest access

1920

se launch karte dikhate hain. Bracket

- 32

stride label karta hai; caption confirm karta hai ki sabse door prefetch

∣ stride ∣ \cdot D = 96

bytes ahead baith hai. Kya notice karna hai: amber squares sab cyan dots ke left mein hain — ek negative stride backward prefetch karta hai, exactly descending walk match karta hai. Sign flip karo aur poori picture right mein mirror ho jaati hai.

Verify: farthest prefetch distance $= ∣ stride ∣ \cdot D = 32 \cdot 3 = 96$ bytes loop ki direction mein aage. Lines $1888, 1856, 1824$ sab $1920$ ke neeche hain, descending walk match karta hai. ✅ (Positive strides upar land hote — same machinery, mirror image.)

Worked example Ex 7 — Cell G: the accuracy trap (

$a$ ko $m_{e f f}$ mein multiply mat karo) Ek prefetcher accuracy $a = 0.4$ aur coverage $c = 0.6$ report karta hai, machine $t_{hi t} = 1$ , $t_{mi ss} = 200$ , $m = 0.04$ , $Δ m = 0$ ke saath. Ek classmate likhta hai $m_{e f f} = m (1 - a c)$ . Sahi AMAT nikalo aur error expose karo.

Forecast: $m_{e f f}$ mein kaunsa number jaata hai — sirf $c$ , ya $a \cdot c$ ?

Sahi: $m_{e f f} = m (1 - c) = 0.04 (1 - 0.6) = 0.016$ . Yeh step kyun? Coverage already sirf actually eliminate ki gayi misses count karta hai. Accuracy ek alag denominator hai (issued prefetches par) aur wasted bandwidth measure karta hai, miss reduction nahi.
$AMAT_{cor r ec t} = 1 + 0.016 \cdot 200 = 4.2$ cycles.
Galat formula deta hai $m_{e f f} = 0.04 (1 - 0.4 \cdot 0.6) = 0.04 \cdot 0.76 = 0.0304$ , toh $AMAT_{w r o n g} = 1 + 0.0304 \cdot 200 = 7.08$ cycles. Yeh kyun dikhate hain? Yeh dekhne ke liye ki trap pessimistically double-counts karta hai: $a$ se dobara penalize karta hai jabki $c$ ne correctness already fold in kar li thi.

Verify: $4.2 \neq = 7.08$ . Dono $2.88$ cycles se disagree karte hain — proof ki $a$ ko $m_{e f f}$ se bahar rehna chahiye. Accuracy Ex 8 mein reappear karegi jahaan yeh belong karti hai: bandwidth. ✅

Worked example Ex 8 — Cell H: real-world bandwidth budget (accuracy ka sahi ghar)

Ek core ek run mein $P = 1, 000, 000$ prefetches issue karta hai, accuracy $a = 0.4$ ke saath. Har prefetch ek 64-byte line ko $B = 20 GB/s$ bandwidth wale bus par move karta hai. Kitne bytes waste hue, aur waste ne kitna bus time jalaya?

Forecast: $40%$ prefetches useful hain, isliye $60%$ waste hain. Wasted MB guess karo.

Useless prefetches $= P (1 - a) = 1, 000, 000 \cdot 0.6 = 600, 000$ . Yeh step kyun? Accuracy $a$ = used fraction; isliye $1 - a$ = wasted fraction. Yahaan $a$ legitimately appear karta hai — bandwidth mein, $m_{e f f}$ mein nahi.
Wasted bytes $= 600, 000 \cdot 64 = 38, 400, 000$ bytes $= 38.4 MB$ . Kyun? Har wasted prefetch phir bhi bus par ek poori 64-byte line kheeche laaya.
Wasted bus time $= \frac{38 , 400 , 000 bytes}{20 \times 1 0 ^{9} bytes/s} = 1.92 \times 1 0^{- 3} s = 1.92 ms$ . Kyun? time $=$ bytes $\div$ bandwidth; units: $bytes / (bytes/s) = s$ . ✅ units check.

Verify: $38.4 MB$ wasted aur $1.92 ms$ bus real traffic se chura liya. Yahi reason hai ki low accuracy hurt karta hai chahe coverage theek ho — yeh bandwidth churaata hai. ✅

Worked example Ex 9 — Cell I: the exam twist — irregular pointer chase

Ek program ek linked list walk karta hai; access order mein node addresses hain 5000, 8300, 1200, 9600 (bytes). Line = 64 B. (a) Stride prefetcher kya stride seekhta hai, aur usse kya coverage milti hai? (b) Kya structure ise fix karta hai?

Forecast: kya gaps constant hain? Agar nahi, toh stride prefetch helpless hai — coverage $\to 0$ .

Gaps: $8300 - 5000 = 3300$ ; $1200 - 8300 = - 7100$ ; $9600 - 1200 = 8400$ . Yeh step kyun? Successive strides exactly Ex 6 ki tarah compute karo.
Koi bhi do gaps match nahi karte ⇒ confidence kabhi confirm nahi hoti ⇒ stride coverage $c = 0$ . Kyun? Ek stride prefetcher sirf repeating gap par fire karta hai; random pointer targets mein koi nahi hota.
Fix: ek correlation prefetcher (parent ki Strategy 3) pair record karta hai "miss at 5000 → miss at 8300", "8300 → 1200", etc. Usi list ki agli traversal par, $5000$ dekhne par $8300$ prefetch karta hai. Kyun? Addresses ka koi formula nahi hai, lekin sequence repeat hoti hai jab tum list dobara walk karte ho — history, not arithmetic.

Verify: stride coverage yahaan $c = 0$ hai (koi matching gaps nahi hai yeh confirm karta hai), isliye ek stride engine se AMAT unchanged hai; sirf correlation (ya software pointer hints) help kar sakta hai. ✅

Recall Self-test: kaunsa cell?

Ek prefetcher ka $c = 0.5$ aur $Δ m = 0.03$ hai $m = 0.04$ par. Baseline se better hai ya worse? ::: Worse. Break-even $Δ m = m \cdot c = 0.02$ ; yahaan $0.03 > 0.02$ , isliye yeh Cell B (net loss) hai. $m_{e f f} = 0.04 \cdot 0.5 + 0.03 = 0.05 > 0.04$ . Hum kabhi $m_{e f f} = m (1 - a c)$ kyun nahi likhte? ::: Kyunki coverage $c$ already sirf actually eliminated misses count karta hai (correctness + timeliness baked in). Accuracy $a$ se multiply karna double-count karta hai. $a$ bandwidth math (Ex 8) mein belong karta hai, $m_{e f f}$ mein nahi. Ek descending address walk 2016,1984,1952 — stride ka sign? ::: Negative ( $- 32$ ). Prefetches backward jaate hain; aage ki distance $∣ stride ∣$ use karti hai.

Yeh bhi dekho: Cache Basics — Blocks and Locality, Spatial vs Temporal Locality, Cache Pollution and Replacement Policies, Out-of-Order Execution.