Exercises — Prefetching strategies

Accuracy is over issued prefetches: $\frac{\text{used}}{\text{issued}}=\frac{300}{1000}=0.30$. Coverage is over original misses: $\frac{\text{misses killed}}{\text{original misses}}=\frac{240}{500}=0.48$. Different denominators — that is the whole point. Both land in $[0,1]$ as they must. Accuracy ::: 0.30 Coverage ::: 0.48

(a) Next-line — consecutive elements, stride of one line's worth; the +1 rule catches it. (Stride also works, next-line is the cheapest that suffices.) (b) Stride — a constant gap larger than one element; next-line would miss every element in between. (c) Correlation — the next address is whatever the pointer holds; no arithmetic pattern exists, so only recorded miss-pairs (A→B) help. Relates to Spatial vs Temporal Locality. (a) ::: next-line (b) ::: stride (c) ::: correlation

Every access pays $t_{hit}$; only the miss fraction pays the penalty. $\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. Why subtract $c$? Imagine 100 misses lined up as 100 tickets. Coverage $c=0.65$ means the prefetcher physically tore up 65 of those tickets before the CPU reached them — those 65 accesses now hit in cache. Only the surviving $35$ tickets ($=100(1-c)$) still cost a miss. That is literally the green-slice-removed picture in the figure at the top: the miss bar drops from $m$ to $m(1-c)$. $m_{eff}=m(1-c)+\Delta m=0.04(1-0.65)+0=0.04\cdot 0.35=\mathrm{0.014.}$ There is no accuracy factor here — coverage already counts only tickets actually torn up. Step 2 — new AMAT. Same formula, smaller 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$ (and $2096-2048=48$, $2144-2096=48$ — all agree). The address-line diagram below traces exactly this: violet dots are the observed accesses, orange squares are the three prefetches issued after $2144$. Prefetch $\text{addr}+stride\cdot k$ for $k=1,2,3$ from the latest address $2144$:

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

Farthest distance ahead $=stride\cdot D=48\cdot 3=144$ bytes. prefetched ::: 2192, 2240, 2288 farthest distance ::: 144 bytes

Use the figure's two-slice picture: the green slice removed is $m\cdot c=0.06\cdot 0.20=0.012$, but the magenta pollution slice added is $\Delta m=0.025>0.012$ — pollution out-stacks the benefit, so we expect a loss even before computing. $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. It hurts by $8.3-7.0=1.3$ cycles per access. Low accuracy shrank coverage and the useless prefetches evicted live lines (see 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 is the moment the magenta slice exactly equals the green slice — the miss bar returns to its original height. 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.}$ Any pollution above $0.012$ makes it a net loss. In Ex 3.1, $\Delta m=0.025>0.012$ — which is exactly why it hurt. Note $\Delta m_{\max }=m\cdot c\le m$ always, consistent with the stated domain. break-even pollution ::: 0.012

Coverage is the product of "issued for" and "succeeded": $c=p\cdot s=0.9\cdot 0.5=0.45$. Both $p$ and $s$ live in $[0,1]$, so their product $c$ does too — no domain violation. $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

Time to fully hide $=t_{miss}=120$ cycles. Each line "consumes" $8$ cycles of compute. So the prefetch must lead by: $D=\lceil \frac{t_{miss}}{\text{cycles per line}}\rceil =\lceil \frac{120}{8}\rceil =15\text{ lines}.$ Running fewer than 15 lines ahead means the prefetch is late (partial miss). Running far more risks evicting live data too early. This lead is why degree/distance tuning matters — connects to Memory-Level Parallelism (MLP) and Out-of-Order Execution. distance ahead ::: 15 lines

Before blocking, the access pattern jumped across rows — irregular, so a hardware stride prefetcher could not lock a stride, and a software hint (or correlation prefetcher) was needed. After blocking, the inner loop walks contiguous elements = unit stride. A plain hardware next-line / stride prefetcher detects this automatically at zero instruction cost. Therefore the explicit PREFETCHT0 becomes redundant: it would only spend instruction bandwidth for a pattern the hardware already covers. Key insight: improving locality (blocking) can make expensive software prefetching unnecessary — restructure data before adding prefetch instructions. sufficient mechanism ::: hardware next-line / stride prefetch

Write AMAT as a function of $c$ (recall $0\le c\le 1$): $m_{eff}(c)=m(1-c)+0.05c=m-mc+0.05c=m+c(0.05-m).$ With $m=0.08$: coefficient of $c$ is $0.05-0.08=-0.03<0$. So $m_{eff}$ decreases as $c$ grows — more coverage always helps here because the pollution penalty ($0.05$ per unit coverage) is smaller than the benefit ($m=0.08$ per unit coverage). This is the figure's rule: green slice removed per unit $c$ ($=m$) exceeds magenta slice added per unit $c$ ($=0.05$). Thus the optimum is the largest achievable $c$, i.e. $c_{\text{opt}}=1$ (the top of coverage's domain): $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: whenever pollution-per-coverage $<m$, push coverage to its ceiling $c=1$; if it exceeded $m$, the coefficient flips positive and the best choice is $c_{\text{opt}}=0$ (turn the prefetcher off). The break-even slope is exactly $m$. 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$ is a bandwidth metric — it does NOT enter coverage.) Pollution from unused prefetches: $\Delta m=0.02\cdot (1-0.6)=0.02\cdot 0.4=0.008$ (positive, and $\le m$, so within domain). 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 of $6.0-5.05=0.95$ cycles per access — because the green slice ($m\cdot c=0.0175$) removed outweighs the magenta pollution slice ($0.008$) added. 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