Worked examples — GPU memory bandwidth optimization

6.2.14 · D3 · Hardware › GPU Architecture › GPU memory bandwidth optimization

Yeh parent topic ka worked-examples companion hai. Parent ne tools diye the: coalescing, transactions, efficiency $\eta$, bank conflicts, aur arithmetic intensity $I$. Yahan hum har case ko hit karte hain jo woh tools produce kar sakte hain — perfect access, worst access, degenerate one-thread cases, AoS scattering case, aur roofline boundary — numbers ke saath jo bottom mein check hain.

Shuru karne se pehle, ek plain-words refresher taaki koi symbol unearned na ho:

$\eta =\frac{w\cdot b}{\text{(transactions)}\times T_{tx}},\text{transactions}=\lceil \frac{\text{address span}}{T_{tx}}\rceil$

Yahan $b$ woh bytes hain jo har thread chahta hai (ek float mein $b=4$ hai). Symbol $\lceil \rceil$ ka matlab hai round up — tum aadha fetch nahi kar sakte; ek bhi leftover byte pura extra transaction force kar deta hai.

---

The scenario matrix

Is topic ka har memory-access problem in cells mein se ek mein fit hota hai. Neeche ke worked examples us cell ke saath labelled hain jo woh cover karte hain, aur saath milke poori table fill karte hain.

Cell	Access pattern	Kya special hai isme	Example
A	Consecutive (stride 1)	Best case, $\eta =100\%$	Ex 1
B	Strided (stride $s>1$)	Wasted bandwidth $s$ ke saath badhta hai	Ex 2
C	Extreme stride ($s\ge 32$)	Full serialization, $\eta$ floor	Ex 2b (Ex 2 ke andar)
D	Degenerate: 1 active thread	31 threads masked off wala warp	Ex 3
E	Broadcast: sab same address	Zero-stride, special hardware path	Ex 4
F	AoS scatter (struct span $S$)	Partial coalescing	Ex 5
G	Shared-memory bank conflict	$k$-way conflict → $k$ cycles	Ex 6
H	Word problem (real workload)	Layout choose karo, speedup predict karo	Ex 7
I	Roofline boundary (limiting case)	Bandwidth- vs compute-bound crossover	Ex 8
J	Exam twist (misaligned base)	Alignment offset extra transaction force karta hai	Ex 9

Prerequisites jo click karne layak hain agar koi step fast lage: GPU-Warp-Scheduling, Cache-Hierarchy, CUDA-Shared-Memory, Roofline-Model.

Upar ki figure poori matrix pictures mein hai — har colored strip ek warp ki 32 requests hai, aur black boxes woh 128-byte fetches hain jo actually haul hoti hain. Isko baar baar dekhte rehna.

---

Ex 1 — Cell A: perfectly consecutive

Forecast: aage padhne se pehle transaction count guess karo. (Ek? Baatees?)

1. Address span dhundo. Thread 0 offset $0$ par hai, thread 31 offset $4\times 31=124$ par. Span $=124-0+4=128$ bytes (yeh $+4$ isliye kyunki thread 31 apne 4 bytes chahta hai). Yeh step kyun? Transactions sirf is par depend karte hain ki pehli aur aakhri bytes kitni door hain, threads ki sankhya par nahi — fetch ek contiguous block carry karta hai.
2. Transactions mein round up karo. $\lceil 128/128\rceil =1$. Yeh step kyun? Ek 128-byte block poora span exactly cover karta hai.
3. Efficiency compute karo. Useful bytes $=32\times 4=128$. Hauled $=1\times 128=128$. $\eta =\frac{128}{128}=1=100\%.$

Verify: Figure mein strip A dekho — colored requests single black box ko bina gaps aur bina overflow ke tile karte hain. Units: bytes/bytes = dimensionless, efficiency ke liye sahi. ✓

---

Ex 2 — Cells B & C: strided access

Forecast: kaun sa 3.125% floor tak completely collapse kar deta hai?

Part (a), $s=2$:

1. Span. Last thread offset $4\cdot 2\cdot 31=248$ par; span $=248+4=252$ bytes. Kyun? Stride double karne se address spread double ho jaata hai.
2. Transactions. $\lceil 252/128\rceil =\lceil 1.97\rceil =2$. Yahan round up kyun matter karta hai: 252 bytes ko block $[0,127]$ plus block $[128,255]$ chahiye — data byte 251 par khatam hota hai, abhi bhi doosre block ke andar, isliye do transactions isko cover karte hain (teen nahi).
3. Efficiency. $\eta =\frac{128}{2\times 128}=\frac{1}{2}=50\%$.

Part (b), $s=32$:

1. Span. Last thread ka offset $=4\cdot 32\cdot 31=3968$; span $=3968+4=3972$ bytes.
2. Transactions. $\lceil 3972/128\rceil =\lceil 31.03\rceil =32$. Exactly 32 kyun? Stride $\ge 32$ floats ke saath, har thread apne khud ke 128-byte block mein land karta hai — do koi fetch share nahi karte. Yeh hai worst case = Cell C.
3. Efficiency. $\eta =\frac{128}{32\times 128}=\frac{1}{32}=3.125\%$.

Verify: parent note ke worst-case $3.125\%$ se match karta hai. Figure mein, strip C ki requests ek-per-box scatter hoti hain — 32 boxes, 31/32 har ek ka wasted. Sanity: $\eta$ monotonically drop hua jaise $s$ badha (100% → 50% → 3.1%), jo ki "zyada spread = zyada waste" demand karta hai. ✓

---

Ex 3 — Cell D: degenerate, ek active thread

Forecast: kya ek akela thread abhi bhi poore 128-byte fetch ke liye pay karta hai?

1. Span. Sirf ek active address hai, toh span $=4$ bytes. Yeh step kyun? Masked threads koi request issue nahi karte; span sirf live wale ka hai.
2. Transactions. $\lceil 4/128\rceil =1$. Zero kyun nahi ho sakta: block 128 bytes par quantized hai — tum isse kam fetch nahi kar sakte.
3. Efficiency. Useful $=4$, hauled $=128$: $\eta =4/128=3.125\%$.

Verify: Strided worst case jaisa hi 3.125% floor — lekin opposite reason se. Cell C waste karta hai kyunki addresses spread out hain; Cell D waste karta hai kyunki warp almost empty hai. Isliye warps full rakhna matter karta hai: ek under-populated warp bandwidth utni hi jalata hai jitni ek scattered wali. ✓

---

Ex 4 — Cell E: broadcast (zero stride)

Forecast: naively tum soch sakte ho 32 threads ek word ke liye lad rahe hain — kya yeh conflict hai?

1. Global-memory span. Sab threads offset 0 par, span $=4$ bytes → $\lceil 4/128\rceil =1$ transaction. Kyun? Har request same address hai, toh address span sirf ek word hai.
2. General formula se efficiency. DRAM ko sirf 4 distinct useful bytes deliver karne the (ek word), ek 128-byte block ke andar hauled: ${\eta }_{\text{DRAM}}=\frac{\text{distinct useful bytes}}{\text{transactions}\times T_{tx}}=\frac{4}{1\times 128}=3.125\%.$ "Distinct" yahan kyun? $\eta$ DRAM traffic waste measure karta hai, aur DRAM ne sirf ek word move kiya chahe kitne bhi threads ne use consume kiya. Toh fetch trips par sasta hai (1 transaction) chahe uski DRAM efficiency floor par ho — yeh do facts conflict mein nahi hain.
3. Shared-memory case. Parent ka broadcasting exception fire karta hai: identical address → hardware 1 cycle mein broadcast karta hai, koi bank conflict nahi. Kyun? Conflict ke liye different addresses chahiye same bank mein. Same address ek aisa exception hai.

Verify: 1 transaction, ${\eta }_{\text{DRAM}}=3.125\%$ (global), aur 1 cycle (shared, broadcast). Ex 6 se contrast karo jahan ek bank mein different addresses bahut mehenga padta hai. ✓

---

Ex 5 — Cell F: Array-of-Structures scatter

Forecast: yeh full worst case nahi hai — 1 aur 32 ke beech guess karo.

1. Span. Thread $i$ ka x offset $24i$ par hai. Last thread $=24\times 31=744$; span $=744+4=748$ bytes. Kyun? Wanted fields har 24 bytes par hain — scattered, lekin stride-32 jitna door nahi.
2. Transactions. $\lceil 748/128\rceil =\lceil 5.84\rceil =6$. 6 kyun aur 32 kyun nahi? Chhe neighbouring blocks 748-byte spread cover karte hain, isliye AoS partially coalesces karta hai.
3. Efficiency. $\eta =\frac{128}{6\times 128}=\frac{1}{6}\approx 16.7\%$.

Ab fix — Structure of Arrays — x[i] ko consecutive banata hai, Cell A par wapas (1 transaction, 100%).

4. Whole-struct speedup. Sab 6 fields: AoS $=6\times 6=36$ transactions; SoA $=6\times 1=6$. $\text{Reduction}=36/6=6\times .$

Verify: parent ke AoS-vs-SoA numbers se match karta hai ($16.7\%$, $6\times$). Figure mein strip F mein 6 boxes hain jisme har ek mein sirf ek useful sliver hai. SoA pehle se choose karne ke liye Parallel-Algorithm-Design dekho. ✓

---

Ex 6 — Cell G: shared-memory bank conflict

Forecast: kya column read karna best ya worst cheez hai?

1. Har address ka bank. Bank $=\left(\frac{A}{4}\right)\mathrm{mod}32$. Element tile[i][0] word index $32i$ par hai (row-major, 32 columns per row). Word index $32i$ kyun? Row $i$ row $i-1$ se $32$ words aage se shuru hoti hai.
2. Mod 32 reduce karo. $32i\mathrm{mod}32=0$ har i ke liye. Yeh disaster kyun hai: sab 32 threads bank 0 par map karte hain, different addresses → ek 32-way conflict.
3. Cycle cost. $k$-way conflict $=k$ cycles: yahan $k=32$, toh 32 cycles 1 ki jagah.

Padding fix: float tile[32][33] declare karo (ek dummy column). Ab tile[i][0] word index $33i$ par hai, aur $33i\mathrm{mod}32=i$ — sab distinct banks → 1 cycle. $+1$ kyun kaam karta hai: $33\equiv 1(\mathrm{mod}32)$, toh successive rows exactly ek bank se shift hoti hain, column ko sab 32 mein spread kar deti hain.

Verify: Conflict-free result $33i\mathrm{mod}32=i$ banks $\mathrm{0..31}$ ko ek ek baar hit karta hai. Speedup $32\to 1$ cycles $=32\times$. Padding idiom ke liye CUDA-Shared-Memory dekho. ✓

---

Ex 7 — Cell H: word problem, layout choose karo

Forecast: kaun sa ek red-channel warp ko coalesce karne deta hai?

1. Interleaved red access. Pixel $i$ ka red byte $12i$ par hai. 32 threads ke liye span $=12\times 31+4=376$; transactions $=\lceil 376/128\rceil =3$. Kyun? Reds 12 bytes apart hain — Ex 5 jaisa scatter idea, bas $S=12$.
2. Planar red access. Reds contiguous hain, 4 bytes apart. Span $=128$; transactions $=1$. Kyun? Planar sab reds ko ek run mein rakhta hai → Cell A.
3. Ratio. $3/1=3\times$ fewer transactions red pass ke liye; green aur blue passes ke liye bhi same.

Answer: channel-parallel work ke liye planar (SoA) choose karo. Verify: interleaved deta hai $\eta =128/(3\cdot 128)=33.3\%$, planar $100\%$; ratio $3\times$ step 3 se match karta hai. Units: transactions dimensionless counts hain. ✓

---

Ex 8 — Cell I: the roofline boundary

Forecast: kya $T_{\text{tile}}=32$ tiling memory wall se nikalne ke liye kaafi hogi?

1. Work count karo. Ek full multiply $N^3$ multiply-adds karta hai, har ek 2 FLOPs count karta hai, toh total FLOPs $=2N^3$. Yeh step kyun? Arithmetic intensity $I$ = FLOPs ÷ bytes, toh pehle FLOP numerator chahiye. $N^2$ output entries mein se har ek length $N$ ka dot product hai → $N^3$ products.
2. Tiling ke saath DRAM bytes count karo — build it up.
   • Sub-step 2a — reads per output element, un-tiled: har output entry ko $A$ ki ek full row aur $B$ ka ek full column chahiye, yani DRAM se $2N$ element reads.
   • Sub-step 2b — tiling yeh kaise divide karta hai: hum shared dimension ko $T_{\text{tile}}$ ke chunks mein sweep karte hain, $N/T_{\text{tile}}$ tile-steps dete hain. Har step ke andar ek tile DRAM se ek baar fetch hoti hai aur phir block ke har thread se fast shared memory se reuse hoti hai. Toh DRAM reads per output element $2N$ se $2N/T_{\text{tile}}$ par drop ho jaate hain. Yeh step kyun? Reuse tiling ka poora point hai: ek DRAM fetch $T_{\text{tile}}$ worth of arithmetic feed karta hai, toh DRAM traffic $T_{\text{tile}}$ factor se shrink hoti hai.
   • Sub-step 2c — bytes mein convert karo aur sab outputs mein multiply karo: $N^2$ output elements hain, har ek read par 4-byte float: $\text{DRAM bytes}=\underset{\text{outputs}}{\underbrace{N^2}}\times \underset{\text{reads each}}{\underbrace{\frac{2N}{T_{\text{tile}}}}}\times \underset{\text{bytes/float}}{\underbrace{4}}=\frac{8N^3}{T_{\text{tile}}}\text{ bytes}.$ Yeh step kyun? Ab numerator (FLOPs) aur denominator (bytes) dono haath mein hain, toh $I$ directly follow karta hai.
3. Arithmetic intensity. $I=\frac{2N^3}{8N^3/T_{\text{tile}}}=\frac{T_{\text{tile}}}{4}\text{FLOPs/byte}.$ $N^3$ cancel ho jaata hai — intensity sirf tile size par depend karti hai, matrix size par nahi. $T_{\text{tile}}=32$ ke liye: $I=32/4=8$ FLOPs/byte.
4. Machine balance. $I_{\star }=\frac{20\times 10^{12}}{1\times 10^{12}}=20$ FLOPs/byte. Yeh number kyun? Yeh woh FLOPs hain jo tumhe har byte par karne padenge taaki compute units bandwidth ki pace par exactly fed rahein. Isse neeche → memory se starved.
5. Compare karo. $8<20$ → bandwidth-bound, lekin naive $T_{\text{tile}}=1$ case ($I=0.25$) se $32\times$ kam traffic. Limiting behaviour: compute-bound mein cross karne ke liye $T_{\text{tile}}/4\ge 20\Rightarrow T_{\text{tile}}\ge 80$ chahiye (register blocking se reach hota hai, kyunki 80×80 shared tiles fit nahi honge).

Verify: $I_{\star }=20$, tiled $I=8$ (<20 → bandwidth), naive $I=0.25$ (≪20). Crossover $T_{\text{tile}}=80$. Sab Roofline-Model se consistent. ✓

---

Ex 9 — Cell J: the exam twist (misaligned base)

Forecast: Ex 1 ne 1 transaction diya — kya shifted start sach mein cost karta hai?

1. Touched byte range. Thread 0 byte 64 par, thread 31 byte $64+124=188$ par. Range $[64,191]$. 191 include kyun karte hain? Thread 31 bytes 188–191 chahta hai.
2. Kaun se 128-blocks? Block 0 $[0,127]$ cover karta hai, block 1 $[128,255]$ cover karta hai. Hamara range $[64,191]$ 128 par boundary straddle karta hai. Yeh kyun matter karta hai: transactions 128-byte block boundaries par aligned hain, tumhare data par nahi.
3. Transactions count karo. Range block 0 (bytes 64–127) aur block 1 (bytes 128–191) touch karta hai, toh 2 transactions chahiye — chahe data sirf 128 bytes wide ho. 2 kyun aur 1 kyun nahi? Ek single fetch sirf ek aligned 128-byte block ho sakta hai; hamara data seam ke across spill karta hai, toh koi single aligned block sab contain nahi kar sakta.
4. Efficiency. Useful $=32\times 4=128$ bytes; hauled $=2\times 128=256$ bytes. $\eta =\frac{128}{2\times 128}=\frac{1}{2}=50\%.$

Verify: Alignment yahan efficiency half kar deta hai — ek classic trap. Lesson: allocations pad karo taaki base 128 ka multiple ho. Ex 1 jaisi hi 128 useful bytes, lekin $2\times$ fetches kyunki hum seam cross kar gaye. Figure mein strip J dekho — colored run black gridline ke astriding baith hai. ✓

---

Recall Quick self-test

Stride-2 float read: kitne transactions aur kya efficiency? ::: 2 transactions, 50% (span 252 → ⌈252/128⌉ = 2) Stride-32 float read: kitne transactions? ::: 32 (har thread ka apna 128-byte block) Sirf thread 0 active wala ek warp 1 float read karta hai — efficiency? ::: 3.125% (4 useful / 128 hauled) Sab 32 threads same shared word read karte hain — kitne cycles? ::: 1 (broadcast exception) AoS 24-byte struct ke saath, ek field per thread — transactions? ::: 6 (span 748 → ⌈748/128⌉) Consecutive reads lekin base=64 — transactions? ::: 2 (range 128-byte boundary straddle karta hai) Tiled matmul T_tile=32 ek 20:1 machine par — kis se bound? ::: bandwidth (I=8 < I* = 20)