GPU memory bandwidth optimization: Visual walkthrough

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

Yeh page EK central idea ko zero se build karti hai: kyun threads ko is tarah arrange karna ki woh neighbouring addresses read karein, ek slow GPU kernel ko fast bana deta hai. Hum woh efficiency formula derive karte hain jo parent note mein bataya gaya hai, lekin pictures ki sequence ke roop mein. Akhir tak aap koi bhi access pattern dekh kar predict kar sakenge ki woh kitna bandwidth waste karta hai.

Hum assume karte hain ki aapne kabhi "warp", "transaction", ya ceiling symbol $⌈ ⌉$ nahi dekha. Har cheez step by step earn hogi.

Step 1 — Memory kya hai, aur "thread" kya hota hai?

KYA HAI. GPU memory (jise DRAM kehte hain) ko ek bahut lambi shelf ke roop mein imagine karein jisme tiny boxes hain. Har box kuch bytes store karta hai. Ek byte sirf 8 bits hota hai — ise data ka ek chota parcel samjhein. Ek float (ek decimal number jiske saath GPU kaam karta hai) exactly 4 bytes leta hai, isliye woh row mein 4 boxes occupy karta hai.

Har box ka ek address hota hai — shelf par uski position number. Box 0, box 1, box 2, ... Address bas "shelf par kitni door hai" yeh batata hai.

Ek thread ek worker hai. GPU hazaaron chalata hai, lekin hardware unhe 32 ke fixed groups mein, jise warp kehte hain, bundle kar deta hai. Warp important hai kyunki usme saare 32 threads lockstep mein chaalte hain: jab warp memory read karta hai, saare 32 ek hi ek moment mein read karte hain.

YEH PEHLE KYUN BATAYA. Coalescing poori tarah is baat par depend karti hai ki warp ke 32 threads us shared moment mein shelf par kahan pahunchte hain. Isliye pehle shelf aur 32 haath ussme daakhil hote hue dekhna zaroori hai.

PICTURE. Addressed boxes ki shelf, uske upar 32 threads ka ek warp, har thread ek arrow ki tarah us box ki taraf point karta hua jisko woh chahta hai.

Figure — GPU memory bandwidth optimization

Step 2 — Hardware data ko fixed chunks mein kyun move karta hai

KYA HAI. Memory system aapko akela 4-byte box khud se nahi de sakta. Woh data sirf fixed-size blocks mein move karta hai. Is block size ko $T$ bytes kehte hain — ek transaction. Real GPUs par $T$ usually 128 bytes hota hai, yaani 32 floats ki width.

Agar aap ek 128-byte block ke andar sirf ek byte maangein, poora 128-byte block bus se neeche aata hai.

YEH TOOL KYUN. Aap pooch sakte hain: sirf requested bytes hi fetch kyun nahi karte? Kyunki wires (the "bus") aur memory chips ek wide block per request burst karne ke liye bane hain — hardware ke liye ek mota block move karna 32 patli blocks se bahut sasta hai. Yahi woh ek fact hai jis wajah se coalescing exist karti hai.

PICTURE. Shelf ab stripes mein paint ki gayi hai, har stripe ek 128-byte transaction hai. Ek stripe mein koi bhi box touch karo → poori stripe move ho jaati hai.

Step 3 — Best case: consecutive addresses (fully coalesced)

KYA HAI. Maanlo thread $i$ address $A + 4 i$ par float read karta hai. Toh:

thread 0 → address $A$
thread 1 → address $A + 4$
thread 2 → address $A + 8$
... thread 31 → address $A + 124$

32 requested floats exactly $32 \times 4 = 128$ bytes fill karte hain — ek single transaction.

KYUN MATTER KARTA HAI. Truck jo bhi bytes carry karta hai, koi na koi thread unhe chahta hai. Kuch bhi waste nahi hota. Yahi woh target hai jiske taraf hum optimise karte hain.

PICTURE. Saare 32 arrows ek hi stripe ke andar land karte hain; stripe "100% useful" light up hoti hai.

Formally count karte hain. $w$ threads ke ek warp ke liye jisme har thread $b$ bytes request karta hai, size $T$ ke transactions mein fit hone wale address span mein phailay hue:

$Transactions = ⌈ \frac{w \cdot b}{T} ⌉$

$w = 32$ — warp mein threads ki sankhya (kitne haath andar jaate hain).
$b = 4$ — bytes jo har thread chahta hai (ek float).
$w \cdot b = 128$ — total useful bytes jo warp chahta hai.
$T = 128$ — bytes jo ek transaction move karta hai.
$⌈ ⌉$ — ceiling: agli poori sankhya tak upar round karo, kyunki aadha truck order nahi kar sakte.

$⌈ \frac{32 \cdot 4}{128} ⌉ = ⌈ 1 ⌉ = 1 transaction$

$η$ (Greek letter "eta") hamaara score hai 0 se 1 tak: delivered pallet ka kitna fraction actually chahiye tha.

Step 4 — Worst case: strided access

KYA HAI. Ab maanlo thread $i$ address $A + 128 i$ read karta hai — har thread ek poora transaction aage jump karta hai (32 floats ka stride). Thread 0 stripe 0 mein hai, thread 1 stripe 1 mein, ..., thread 31 stripe 31 mein.

Har thread ek alag stripe mein land karta hai. Har stripe ek alag truck hai. Isliye 32 threads serve karne ke liye hume 32 transactions chahiye.

YEH KYUN DIKHAYA. Yahi woh disaster case hai jo kernels ko 32× slow karta hai. Exactly kyun — ek thread per stripe — yeh dekhna hi aapko code mein ise pehchanne deta hai (transaction width ke barabar ek stride).

PICTURE. 32 arrows, har ek apni stripe mein, har pallet ka 31/32 "wasted" ke roop mein grey out.

Count karte hain: yahan useful bytes abhi bhi $w \cdot b = 128$ hain, lekin address span bahut bada hai, isliye:

$Transactions = 32, η = \frac{128}{32 \times 128} = \frac{128}{4096} = 0.03125 = 3.125%$

Numerator $128$ — abhi bhi sirf 128 useful bytes (hum ne 32 floats maange).
Denominator $4096$ — 32 pallets $\times$ 128 bytes each jo actually bus se aaye.

Toh hum ne 4096 bytes ke liye pay kiya aur sirf 128 use kiye. Yeh ek $32 \times$ waste hai.

Step 5 — In-between case: ek struct stride (partial coalescing)

KYA HAI. Real code aksar best aur worst ke beech land karta hai. Maanlo har element ek 24-byte struct hai (Array-of-Structures), aur har thread apne struct ka pehla float read karta hai: thread $i$ → address $A + 24 i$ .

32 requested floats ab $32 \times 24 = 768$ bytes span karte hain. Itne bytes kai stripes cross karte hain:

$Transactions = ⌈ \frac{768}{128} ⌉ = ⌈ 6 ⌉ = 6$

$768$ — address span jo warp touch karta hai (useful bytes nahi!).
$128$ — transaction size.
Result 6 — chhe pallets travel karte hain.

Useful bytes abhi bhi $32 \times 4 = 128$ hain:

$η = \frac{128}{6 \times 128} = \frac{1}{6} \approx 16.7%$

YEH CASE KYUN MATTER KARTA HAI. Yeh myth ko disprove karta hai ki access ya "perfect" hoti hai ya "fully serial". 1 aur 32 floats ke beech strides ek graded penalty dete hain. Structure-of-Arrays par switch karna (thread $i$ → $A + 4 i$ ) ise Step 3 par wapas le jaata hai: 1 transaction, 100%.

PICTURE. Arrows har 24 bytes par land karte hue, ~6 stripes across sweep karte hue, har stripe sirf partly used.

Step 6 — Degenerate cases: saare threads EK address hit karein, aur misalignment

KYA HAI — broadcast case. Maanlo har thread wahi same address $A$ read karta hai. Naively yeh ek box ke liye 32 requests hain. Lekin hardware ise specially handle karta hai: woh box ek baar fetch karta hai aur value saare 32 threads ko broadcast karta hai — 1 transaction, $η$ us datum ke liye full count hoti hai. Koi penalty nahi.

KYA HAI — misalignment case. Maanlo access perfectly consecutive hai (Step 3, stride 4) lekin stripe boundary ki bajay address $A + 4$ se shuru hoti hai. 128 useful bytes ab do stripes mein split ho jaate hain: bytes $4..128$ stripe 0 mein aur bytes $128..131$ stripe 1 mein. Isliye:

$Transactions = 2, η = \frac{128}{2 \times 128} = 50%$

Bilkul consecutive reads bhi aadha bandwidth waste karte hain agar woh 128-byte boundary par shuru na hon. Apne arrays ko align karna ise fix karta hai.

YEH KYUN COVER KIYA. Yeh woh traps hain jo logon ko surprise karti hain: identical addresses free hain (good news), lekin ek one-float misalignment bandwidth half kar deta hai (bad news). Woh reader jo sirf Steps 3–5 dekha ho, dono ko wrongly predict karta.

PICTURE. Left panel: 32 arrows ek box mein → single broadcast. Right panel: consecutive block boundary se off ho gaya, doosri stripe mein spill ho gaya.

Recall

Saare 32 threads ke liye same address kitne transactions leta hai? ::: Ek — hardware broadcast karta hai. 128-byte boundary se ek float off consecutive floats — efficiency? ::: 50%, kyunki woh do transactions mein straddle karte hain.

Step 7 — Efficiency se bandwidth tak (the payoff)

KYA HAI. Physical bandwidth $B$ woh hai ki bus kitne bytes per second move kar sakta hai (ek A100 ~2 TB/s hai). Lekin aapka kernel sirf useful progress iss rate par karta hai:

$M = B \times η$

$B$ — peak bytes/second jo wires deliver karte hain (hardware se fixed).
$η$ — woh efficiency jo hum ne abhi derive ki (aapke access pattern se fixed).
$M$ — woh useful bytes/second jo aapka program actually paata hai.

YEH POORA POINT KYUN HAI. Aap zyada $B$ nahi khareed sakte; lekin aap apna data re-lay karke $η$ ko 3% se 100% tak raise kar sakte hain — ek potential 32× speedup bina koi naya hardware liye. Isliye memory coalescing woh pehla optimisation hai jiske liye koi bhi GPU programmer pahunchta hai. (Jab compute, memory nahi, limit ban jaata hai, tab aap Roofline-Model par graduate karte hain.)

PICTURE. Full bandwidth $B$ ki ek bar, jisme $η$ hamare charo cases mein se har ek ke liye useful portion slice karta hai.

Ek-picture summary

Har access pattern span vs useful bytes ki ek kahani hai. 32 threads hamesha wahi 128 useful bytes chahte hain; jo badalta hai woh yeh hai ki woh bytes kitne 128-byte pallets mein phailey hain. Kam pallets = zyada $η$ = aapka zyada real bandwidth $B$ .

Recall Feynman retelling — plain words mein poori walkthrough

GPU apne workers ko ek baar mein 32 (ek warp) march karta hai. Memory sirf full 128-byte truckloads mein aati hai. Agar 32 workers 32 neighbouring floats ke liye reach karein, saare 32 ek truck par fit ho jaate hain — ek trip, kuch waste nahi, 100% efficient. Agar instead har worker ek poore truckload aage reach kare, toh 32 floats ke liye 32 trucks chahiye aur jo aaya uska 97% throw away ho jaata hai. Beech mein — maanlo ek 24-byte struct stride — wanted floats 6 trucks mein phail jaate hain aur sirf 1/6 milta hai. Do special cases: agar saare 32 workers ek hi box chahein toh truck ek baar deliver karta hai aur sabko copy karta hai (free); lekin agar aapka neat consecutive block ek float off a truck boundary se start ho toh woh doosre truck mein spill kar jaata hai aur aap aadha kho dete hain. Aapki useful speed bas truck capacity times trucks kitne full the hai: $M = B η$ . Data re-lay karna (Structure-of-Arrays, alignment) hi woh tarika hai jisse trucks full rehte hain.

Related: CUDA-Shared-Memory · Memory-Latency-Hiding · GPU-Warp-Scheduling · Cache-Hierarchy · Parallel-Algorithm-Design · 6.2.14 GPU memory bandwidth optimization (Hinglish)