Exercises — Prefetching strategies

Accuracy issued prefetches ke upar hai: $\frac{\text{used}}{\text{issued}}=\frac{300}{1000}=0.30$. Coverage original misses ke upar hai: $\frac{\text{misses killed}}{\text{original misses}}=\frac{240}{500}=0.48$. Alag denominators — yahi pura point hai. Dono $[0,1]$ mein aate hain jaise hona chahiye. Accuracy ::: 0.30 Coverage ::: 0.48

(a) Next-line — consecutive elements, ek line ke barabar stride; +1 rule ise pakad leta hai. (Stride bhi kaam karta hai, next-line sabse sasta option hai jo kaam kare.) (b) Stride — ek element se bada constant gap; next-line beech ke har element ko miss kar deta. (c) Correlation — agla address jo bhi pointer hold karta hai wahi hai; koi arithmetic pattern nahi, isliye sirf recorded miss-pairs (A→B) help karte hain. Spatial vs Temporal Locality se relate karta hai. (a) ::: next-line (b) ::: stride (c) ::: correlation

Har access $t_{hit}$ pay karta hai; sirf miss fraction penalty pay karta hai. $\text{AMAT}=t_{hit}+m\cdot t_{miss}=2+0.04\cdot 120=2+4.8=6.8\text{ cycles}.$ AMAT_base ::: 6.8 cycles

Step 1 — effective miss rate. $c$ kyun subtract karte hain? Socho 100 misses 100 tickets ki tarah lined up hain. Coverage $c=0.65$ matlab prefetcher ne physically 65 tickets CPU ke paunchne se pehle phaad diye — wo 65 accesses ab cache mein hit karte hain. Sirf bache hue $35$ tickets ($=100(1-c)$) abhi bhi miss karte hain. Yeh literally upar ki figure ka green-slice-removed picture hai: miss bar $m$ se $m(1-c)$ par aa jaata hai. $m_{eff}=m(1-c)+\Delta m=0.04(1-0.65)+0=0.04\cdot 0.35=\mathrm{0.014.}$ Yahan koi accuracy factor nahi hai — coverage pehle se hi correctness aur timeliness fold kar leta hai (yeh fraction actually eliminate hue hai). Step 2 — naya AMAT. Same formula, choti miss fraction: $\text{AMAT}=2+0.014\cdot 120=2+1.68=3.68\text{ cycles}.$ Step 3 — speedup. $\frac{6.8}{3.68}\approx 1.848\times$. m_eff ::: 0.014 AMAT_pf ::: 3.68 cycles speedup ::: about 1.85x

Confirmed stride $=2048-2000=48$ (aur $2096-2048=48$, $2144-2096=48$ — sab agree karte hain). Neeche ka address-line diagram exactly yahi trace karta hai: violet dots observed accesses hain, orange squares $2144$ ke baad issue hone wale teen prefetches hain. Latest address $2144$ se $k=1,2,3$ ke liye $\text{addr}+stride\cdot k$ prefetch karo:

• $k=1:2144+48=2192$
• $k=2:2144+96=2240$
• $k=3:2144+144=2288$

Sabse door wali aage ki distance $=stride\cdot D=48\cdot 3=144$ bytes. prefetched ::: 2192, 2240, 2288 farthest distance ::: 144 bytes

Figure ki two-slice picture use karo: remove hone wala green slice $m\cdot c=0.06\cdot 0.20=0.012$ hai, lekin add hone wala magenta pollution slice $\Delta m=0.025>0.012$ hai — pollution benefit se zyada hai, isliye compute karne se pehle hi loss expect karo. $m_{eff}=m(1-c)+\Delta m=0.06(0.80)+0.025=0.048+0.025=\mathrm{0.073.}$ ${\text{AMAT}}_{pf}=1+0.073\cdot 100=8.3\text{ cycles}.$ Baseline: ${\text{AMAT}}_{base}=1+0.06\cdot 100=7.0$ cycles. Yeh hurt karta hai $8.3-7.0=1.3$ cycles per access se. Kam accuracy ne coverage bhi shrink ki aur bekaar prefetches ne live lines evict kiye (dekho Cache Pollution and Replacement Policies). m_eff ::: 0.073 AMAT_pf ::: 8.3 cycles AMAT_base ::: 7.0 cycles net change ::: +1.3 cycles (worse)

Break-even woh moment hai jab magenta slice exactly green slice ke barabar ho — miss bar wapas original height par aa jaata hai. Formally $m_{eff}=m$: $m(1-c)+\Delta m=m\Rightarrow \Delta m=m-m(1-c)=m\cdot c.$ $\Delta m_{\max }=0.06\cdot 0.20=\mathrm{0.012.}$ $0.012$ se zyada koi bhi pollution net loss bana dega. Ex 3.1 mein $\Delta m=0.025>0.012$ — exactly isliye hurt kiya. Note karo $\Delta m_{\max }=m\cdot c\le m$ hamesha, stated domain ke consistent hai. break-even pollution ::: 0.012

Coverage "issued for" aur "succeeded" ka product hai: $c=p\cdot s=0.9\cdot 0.5=0.45$. $p$ aur $s$ dono $[0,1]$ mein hain, isliye unka product $c$ bhi — koi domain violation nahi. $m_{eff}=0.05(1-0.45)=0.05\cdot 0.55=\mathrm{0.0275.}$ $\text{AMAT}=1+0.0275\cdot 100=3.75\text{ cycles}.$ coverage ::: 0.45 m_eff ::: 0.0275 AMAT ::: 3.75 cycles

Fully hide karne ke liye time $=t_{miss}=120$ cycles. Har line $8$ cycles of compute "consume" karti hai. Isliye prefetch itna lead karna chahiye: $D=\lceil \frac{t_{miss}}{\text{cycles per line}}\rceil =\lceil \frac{120}{8}\rceil =15\text{ lines}.$ 15 lines se kam ahead chalna matlab prefetch late hai (partial miss). Bahut zyada aage chalna live data ko bahut jaldi evict karne ka risk rakhta hai. Yahi wajah hai ki degree/distance tuning matter karti hai — Memory-Level Parallelism (MLP) aur Out-of-Order Execution se connect karta hai. distance ahead ::: 15 lines

Blocking se pehle, access pattern rows ke across jump karta tha — irregular, isliye hardware stride prefetcher koi stride lock nahi kar sakta tha, aur software hint (ya correlation prefetcher) chahiye tha. Blocking ke baad, inner loop contiguous elements walk karta hai = unit stride. Ek simple hardware next-line / stride prefetcher yeh automatically detect kar leta hai zero instruction cost mein. Isliye explicit PREFETCHT0 redundant ho jaata hai: yeh sirf instruction bandwidth spend karega ek aise pattern ke liye jise hardware pehle se hi cover karta hai. Key insight: locality improve karna (blocking) expensive software prefetching unnecessary bana sakta hai — prefetch instructions add karne se pehle data restructure karo. sufficient mechanism ::: hardware next-line / stride prefetch

AMAT ko $c$ ka function likho (yaad rakho $0\le c\le 1$): $m_{eff}(c)=m(1-c)+0.05c=m-mc+0.05c=m+c(0.05-m).$ $m=0.08$ ke saath: $c$ ka coefficient $0.05-0.08=-0.03<0$ hai. Isliye $m_{eff}$ $c$ badhne par decrease karta hai — yahan zyada coverage hamesha help karta hai kyunki pollution penalty (coverage per unit $0.05$) benefit se chhoti hai (coverage per unit $m=0.08$). Yeh figure ka rule hai: green slice per unit $c$ hataaya ($=m$) magenta slice per unit $c$ add hue ($=0.05$) se zyada hai. Isliye optimum sabse bada achievable $c$ hai, yaani $c_{\text{opt}}=1$ (coverage ki domain ki top): $m_{eff}=0.08+1\cdot (0.05-0.08)=0.08-0.03=0.05,$ ${\text{AMAT}}_{\min }=1+0.05\cdot 150=1+7.5=8.5\text{ cycles}.$ Interpretation: jab bhi pollution-per-coverage $<m$ ho, coverage ko ceiling $c=1$ tak push karo; agar yeh $m$ se zyada ho, coefficient positive flip ho jaata hai aur best choice $c_{\text{opt}}=0$ hai (prefetcher band kar do). Break-even slope exactly $m$ hai. coefficient of c ::: -0.03 optimal coverage ::: 1 AMAT_min ::: 8.5 cycles

Coverage (issued × success): $c=p\cdot s=0.7\cdot 0.5=0.35$. (Note: accuracy $0.6$ ek bandwidth metric hai — yeh coverage mein enter NAHI karta.) Pollution unused prefetches se: $\Delta m=0.02\cdot (1-0.6)=0.02\cdot 0.4=0.008$ (positive, aur $\le m$, isliye domain ke andar). Effective miss rate: $m_{eff}=m(1-c)+\Delta m=0.05(0.65)+0.008=0.0325+0.008=0.0405$. AMAT: $1+0.0405\cdot 100=1+4.05=5.05$ cycles. Baseline: $1+0.05\cdot 100=6.0$ cycles. Net win $6.0-5.05=0.95$ cycles per access — kyunki green slice ($m\cdot c=0.0175$) hataaya gaya magenta pollution slice ($0.008$) add hue se zyada hai. coverage ::: 0.35 pollution ::: 0.008 m_eff ::: 0.0405 AMAT ::: 5.05 cycles net gain ::: 0.95 cycles

Formula for effective miss rate ::: m_eff = m(1-c) + delta_m Formula for AMAT ::: t_hit + m_eff * t_miss Coverage denominator ::: original misses Accuracy denominator ::: prefetches issued Break-even pollution ::: delta_m = m * c Coverage domain ::: 0 <= c <= 1 Pollution domain ::: delta_m >= 0 (typically <= m) Timely prefetch distance ::: ceil(t_miss / cycles_per_line) lines