Exercises — GPU memory bandwidth optimization

Addresses kitna span karte hain: thread $i$ reads $A+4i$, $i=0\dots 31$ ke liye. Lowest byte touched hai $A$, highest hai $A+4\cdot 31+3=A+127$. Toh poora warp bytes $A$ se lekar $A+127$ tak touch karta hai — exactly 128 bytes.

Transactions: $\lceil \frac{32\times 4}{128}\rceil =\lceil \frac{128}{128}\rceil ===1==$ transaction.

Efficiency: useful bytes $=32\times 4=128$; hauled bytes $=1\times 128=128$. $\eta =\frac{128}{128}===100\%==.$ Yeh ideal "fully coalesced" case hai — ek truck, ek full crate, kuch bhi waste nahi.

Pehle word size se kyun divide karein: banks word ke hisaab se assign hote hain, byte ke hisaab se nahi. Word index $=A/4=260/4=65$. Bank rule apply karo $\text{Bank}=(\text{word index})\mathrm{mod}N$: $\text{Bank}=65\mathrm{mod}32===1==.$ Word 65 = 32 banks ke 2 full sweeps (words 0–63) plus 1, jo bank 1 par land karta hai.

Span: thread 0 at $A$, thread 31 at $A+4\cdot 32\cdot 31=A+3968$; 4 bytes read add karo $\Rightarrow$ bytes $A$ … $A+3971$. Har thread ka float apne khud ke 128-byte crate mein hai (spacing $4\times 32=128$ B = exactly ek crate ka antar). Transactions: 32 threads mein se har ek ek alag crate force karta hai $\Rightarrow ==32==$ transactions. Efficiency: $\eta =\frac{32\times 4}{32\times 128}=\frac{128}{4096}===3.125\%==.$ Yeh parent note ka worst case hai: haule gaye 96.875% bytes phek diye jaate hain.

Chaahiye gaye bytes ka span: thread 0 offset 0 par, thread 31 offset $24\times 31=744$ par; +4 bytes $\Rightarrow$ 748 bytes ka span. Us span ko cover karne wale crates: $\lceil 748/128\rceil$. Parent ke count ke saath align karte hue, address range $32\times 24=768$ bytes of stride span karta hai: $\text{transactions}=\lceil \frac{768}{128}\rceil ===6==.$ Efficiency: useful $=128$ B; hauled $=6\times 128=768$ B. $\eta =\frac{128}{768}===16.67\%==.$ AoS partially coalesce karta hai — 6 trips, 32 nahi — lekin bandwidth ka 5/6 waste karta hai.

AoS: har field ko 6 transactions lagte hain (Ex 2.2) $\Rightarrow 6\text{ fields}\times 6===36==$ transactions. SoA: har field apna contiguous array hai, thread $i$ reads base + 4i $\Rightarrow$ 1 transaction/field (Ex 1.1) $\Rightarrow 6\times 1===6==$ transactions. Reduction: $\frac{36}{6}===6\times ==\text{ fewer transactions}.$

(a) Reduction factor. Naive: $2N$ global element-reads per output element. Tiled: har element shared memory mein ek baar per tile enter karta hai, aur $k$ ke saath $N/T$ tiles hain, jo $2N/T$ global reads per output element deta hai. $\text{reduction}=\frac{2N}{2N/T}=T===32\times ==.$ (b) Bytes moved (tiled). $N^2$ outputs $\times \frac{2N}{T}$ reads $\times 4$ bytes: $\text{Bytes}=\frac{8N^3}{T}=\frac{8N^3}{32}=\frac{N^3}{4}.$ (c) Arithmetic intensity. FLOPs $=2N^3$ (ek multiply + ek add per inner term). $I=\frac{2N^3}{8N^3/T}=\frac{T}{4}=\frac{32}{4}===8==\text{ FLOPs/byte}.$ Neeche di gayi picture mein dekho ki yeh point roofline par kahan baithta hai.

Machine balance — woh intensity jahan dono ceilings cross karti hain: $I^{\ast }=\frac{20\times 10^{12}\text{FLOP/s}}{1\times 10^{12}\text{byte/s}}===20==\text{ FLOPs/byte}.$ Rule: $I<I^{\ast }\Rightarrow$ bandwidth-bound (memory ceiling hai); $I>I^{\ast }\Rightarrow$ compute-bound.

• Naive $I=0.25<20$ → bandwidth-bound (heavily).
• Tiled $I=8<20$ → abhi bhi bandwidth-bound, lekin naive se 32× kam traffic ke saath.
• Register-blocked $I=25>20$ → compute-bound — memory ab bottleneck nahi hai. Full graph ke liye Roofline-Model dekho.

Roofline formula: attainable $=\min (\text{peak FLOP/s},B\times I)$. Tiled ($I=8$, bandwidth-bound): $B\times I=1\times 10^{12}\times 8===8\times 10^{12}===8\text{TFLOP/s}.$ Kyunki $8<20$, memory slope jeet jaata hai — 8 TFLOP/s, yaani peak ka 40%. Register-blocked ($I=25$): $B\times I=25\times 10^{12}$, lekin peak se cap hoga $\Rightarrow \min (20,25)\times 10^{12}===20\times 10^{12}===20$ TFLOP/s (full peak).

(a) tile[i][col] ka bank. [32][32] array mein linear word index $32i+\text{col}$ hai. $\text{Bank}=(32i+\text{col})\mathrm{mod}32=\text{col}\mathrm{mod}32.$ Har thread $i$ ek hi bank = $\text{col}\mathrm{mod}32$ hit karta hai, kyunki $32i$ term 32 ka multiple hai aur modulo ke under vanish ho jaata hai. (b) Cycles. 32 threads, ek bank, sab alag addresses (alag rows) $\Rightarrow$ full 32-way conflict $\Rightarrow ==32==$ cycles (1 ideal ke muqable). Yeh broadcast nahi hai: broadcast ke liye same address chahiye, yahan rows differ karti hain. (c) Fix — row ko pad karo. tile[32][33] declare karo. Ab linear index $33i+\text{col}$ hai: $\text{Bank}=(33i+\text{col})\mathrm{mod}32=(i+\text{col})\mathrm{mod}32,$ jo har $i$ ke liye distinct hai $\Rightarrow$ 32 alag banks $\Rightarrow ==1==$ cycle. Ek wasted padding column 32× serialization hata deta hai.

(a) Efficiencies combine karo (yeh multiply hoti hain, kyunki har ek independently usable bandwidth trim karti hai): ${\eta }_{total}=1\times 0.9\times 0.8=\mathrm{0.72.}$ $M=B\times {\eta }_{total}=2\times 10^{12}\times 0.72===1.44\times 10^{12}==\text{byte/s}=1.44\text{TB/s}.$ (b) Us memory feed se compute rate = $M\times I=1.44\times 10^{12}\times 5===7.2\times 10^{12}===7.2$ TFLOP/s. Peak 20 TFLOP/s se compare karo: $7.2<20\Rightarrow$ bandwidth-bound — memory feed, ALUs nahi, hame limit kar rahi hai.

32 floats ke fully coalesced warp ko kitne transactions chahiye? ::: 1 AoS 24-byte struct, ek field padhna, transactions per warp? ::: 6 (efficiency 16.67%) $T\times T$ tiling se global traffic mein reduction? ::: $T$ ka factor Tiled matmul ki arithmetic intensity, $T=32$, floats? ::: 8 FLOPs/byte 20 TFLOP/s aur 1 TB/s ke liye machine balance? ::: 20 FLOPs/byte 32-way shared-memory column conflict ka fix? ::: Tile row ko width 33 tak pad karo