Coalesced memory access: Visual walkthrough — Hinglish deep dive

6.2.8 · D2 · Hardware › GPU Architecture › Coalesced memory access

Step 1 — Ek thread ek number maangta hai

KYA HAI. GPU ki main memory (jise global memory kehte hain, woh bada off-chip DRAM) ko bytes ka ek bahut lamba ruler samjho. Ek byte ek storage slot hai jisme 8 bits hote hain. Har slot ka ek address hota hai — ruler par uska position number. Hum addresses hexadecimal (base-16, 0x se mark kiya) mein likhte hain, lekin tum unhe "slot 0, slot 4, slot 8…" ki tarah padh sakte ho. Ek float (ek decimal number) 4 bytes leta hai, isliye data[0] address 0x000 par hota hai, data[1] 0x004 par, aur aage bhi aise hi.

HEXADECIMAL KYO / BYTES KYO. Hardware kabhi "elements" mein count nahi karta — woh bytes mein count karta hai, kyunki byte sabse chhoti cheez hai jise memory address kar sakti hai. Yeh predict karne ke liye ki hardware kya karta hai, hume uske units mein sochna hoga, apne units mein nahi. Yahi wajah hai ki coalescing subtle hai: hum "array index" sochte hain, woh "byte address" sochta hai.

PICTURE. Neeche ka ruler ek thread (ise thread 0 kaho, tera code execute karne wala ek single worker) ko dikhata hai jo address 0x000 par 4-byte float tak pahunch raha hai.

Step 2 — Hardware kabhi ek byte fetch nahi karta: transaction

KYA HAI. Jab thread 0 apne 4 bytes maangta hai, memory controller sirf woh 4 bytes wapas nahi karta. Woh ek pura fixed-size chunk — ek transaction — uthata hai jo requested address ko contain karta hai. Hum uski size $T$ kehte hain. Hamare model architecture (Volta-style GPU) mein ek transaction ek 32-byte sector hota hai: ek aligned block $[0 x 000, 0 x 01 F]$ , phir $[0 x 020, 0 x 03 F]$ , aur aage bhi aise. "Aligned" matlab har sector ek aise address par shuru hota hai jo $T$ ka poora multiple ho — sector boundaries $0, 32, 64, \dots$ par hain aur beech mein kabhi nahi.

FIXED CHUNK KYO AUR EXACTLY 4 BYTES KYO NAHI. DRAM ek grid of rows ki tarah bana hota hai. Ek row kholna mahenga hissa hai; ek baar khul gaya, toh 32 bytes stream karna almost utna hi cost karta hai jitna 4 bytes karna. Isliye controller hamesha burst deliver karne ke liye designed hota hai. Yeh ek hardware fact baaki sab cheez ka seed hai: tum per transaction pay karte ho, per byte nahi. Cost ke baare mein reason karne ke liye tool isliye transactions count karna hai, bytes count karna nahi — yahi is poori derivation ka "why this tool" hai.

PICTURE. Thread 0 ko 4 orange bytes chahiye; hardware poora 32-byte teal sector unke around return karta hai. Baaki 28 bytes saath mein aa gaye — useful sirf tab jab kisi aur thread ko unki zaroorat hoti.

Step 3 — Threads packs mein chalte hain: warp

KYA HAI. GPUs kabhi akele ek thread nahi chalate. Woh threads ko warps ke fixed groups mein chalate hain jisme $W = 32$ threads hote hain, aur — yeh key rule hai — 32 sab ek hi instruction ek hi waqt execute karte hain (yeh SIMT model hai 6.2.01-GPU-execution-model se). Toh jab instruction "load a float" hai, hardware ke paas ek hi waqt 32 addresses aate hain.

YEH KYO MATTER KARTA HAI. Kyunki 32 requests saath mein aati hain, controller smart ho sakta hai: woh sab 32 addresses dekha, phir kam se kam transactions issue karta hai jo unhe cover kare. Agar 32 addresses tightly cluster hain, kuch transactions kaafi hain. Agar scatter ho jaate hain, zyada chahiye. Coalescing exactly yahi "kitne transactions is warp ke 32 addresses cover karte hain?" wala sawaal hai.

PICTURE. Warp scheduler 32 address-arrows ikattha karta hai pehle decide karne se ki kitne teal buckets fill karne hain.

Step 4 — Best case: consecutive addresses

KYA HAI. Maano thread $i$ data[i] read karta hai. Tab:

$address (i) = i \times E = i \times 4 bytes$

$i$ ::: thread ka index, $0, 1, 2, \dots, 31$ .
$E = 4$ ::: bytes per float — toh consecutive threads exactly $4$ bytes apart land karte hain.

Thread 0 → 0x000, thread 1 → 0x004, … thread 31 → 0x07C. Saath mein woh $32 \times 4 = 128$ bytes span karte hain, block $[0 x 000, 0 x 07 F]$ — perfectly packed, koi gap nahi.

YEH OPTIMAL KYO HAI. 128 useful bytes exactly wahi hai jo warp chahta hai. 32-byte sectors mein divide karo, toh $128/32 = 4$ transactions — aur har fetched byte use hoti hai. 128 useful bytes ko 4 se kam sector-transactions mein nahi padh sakte, toh yeh floor hai. Yahi "coalesced" ka matlab hai: minimum transactions, zero waste. (Yeh clean count secretly assume karta hai ki array sector boundary par shuru hota hai — hum yeh assumption Step 8 mein cash karte hain.)

PICTURE. 32 arrows 4 back-to-back teal sectors tile karte hain bina kisi wasted slot ke.

$N_{coalesced} = \frac{W \times E}{T} = \frac{32 \times 4}{32} = 4 transactions$

$W \times E$ ::: warp request kiye total useful bytes ( $= 128$ ).
$T$ se divide karo ::: wo $T$ -byte buckets kitne hain jin mein woh bytes fit hoti hain.

Step 5 — Worst case: bada stride warp scatter kar deta hai

KYA HAI. Ab thread $i$ ko data[i * S] read karne do, jahan $S$ stride hai — neighbouring threads kya uthate hain unke beech elements mein gap. Itna bada stride lo ki byte gap $S \times E$ kam se kam $T$ ho:

$address (i) = i \times S \times E$

Agar $S \times E \geq T$ , toh har thread ka address ek alag sector mein land karta hai. $S = 8$ floats ke saath: gap $= 8 \times 4 = 32 = T$ bytes — thread 0 sector 0 mein, thread 1 sector 1 mein, … thread 31 sector 31 mein.

YEH COLLAPSE KYO KARTA HAI. Koi do threads ek sector share nahi karte, toh controller ko ek transaction per thread issue karna padta hai: $N = 32$ . Har transaction phir bhi poora 32-byte sector laata hai, lekin sirf $4$ bytes use hote hain. Toh warp $32 \times 32 = 1024$ bytes touch karta hai sirf $32 \times 4 = 128$ use karne ke liye.

PICTURE. 32 arrows, har ek alag teal sector mein ghusta hai; plum shading har sector ke 28 wasted bytes mark karta hai.

$N_{strided} = W = 32 transactions (jab S \cdot E \geq T)$

Step 6 — Transaction-count ko time mein convert karna

KYA HAI. Har transaction ek latency $L$ carry karta hai — data aane se pehle fixed wait — lagbhag $L = 300$ ns. Scattered accesses ke liye yeh per transaction pay karna padta hai. Toh:

$t \approx N \times L$

$N$ ::: transactions ki sankhya jo warp ko chahiye.
$L$ ::: latency per transaction (scattered loads ke liye dominant cost).

Coalesced: 4 back-to-back transactions overlap karte hain aur ek effective wait ki tarah behave karte hain, $t_{coalesced} \approx 300$ ns. Strided: $t_{strided} = 32 \times 300 = 9600$ ns.

4 BURSTS KI COST SIRF EK WAIT KYO HAI? Latency $L$ mostly ek DRAM row kholne ki cost hai — memory array ke poore ek page ko ek fast row buffer mein activate karna. 4 coalesced sectors 128 adjacent bytes hain, toh woh same open row mein hain. Tum row-open cost ek baar pay karte ho; doosra, teesra aur chaautha 32-byte burst seedha pehle se khule row buffer se streaming speed par padha jaata hai (woh near-zero $0.14$ ns transfer). 32 strided sectors, iske ulta, 32 far-apart rows mein hain — har ek apna row-open force karta hai, isliye uska $L$ hide nahi ho sakta. Yeh "same row = one latency" exactly woh row-buffer locality hai jo 5.1.05-Cache-coherence-protocols ke neeche bhi hai.

PICTURE. Ek timeline: ek short coalesced wait ke saath 32 stacked strided waits.

$Speedup = \frac{t _{strided}}{t _{coalesced}} = \frac{9600}{300} = 32 \times$

Step 7 — Stride ka poora spectrum, odd wale bhi

KYA HAI. Real code rarely "perfect" ya "worst" hota hai. Kisi bhi stride $S$ ke liye jahan byte gap kam se kam ek element ho lekin ek sector se kam, threads ek fixed number ek sector mein pack karte hain. Generally, $T$ bytes ka ek sector hold karta hai

$threads per sector = \frac{T}{S \times E} (jab S \cdot E \leq T),$

toh warp ko jo transactions chahiye unki sankhya hai

$N (S) = ⌈ \frac{W}{⌊ T / ( S \cdot E )⌋} ⌉ (aligned, S \cdot E \leq T), N (S) = W (S \cdot E \geq T) .$

$⌊ T / (S \cdot E)⌋$ ::: ek $T$ -byte sector ke andar kitne threads' addresses fit hote hain (floor, kyunki partial thread sector share nahi kar sakta).
$⌈ W / \dots ⌉$ ::: upar ki taraf round karo — threads ka ek leftover handful phir bhi ek pura extra transaction maangta hai.

Worked odd case, $S = 3$ (power of two nahi): byte gap $= 3 \times 4 = 12$ ; threads per sector $= ⌊ 32/12 ⌋ = 2$ ; toh $N = ⌈ 32/2 ⌉ = 16$ transactions, efficiency $128/ (16 \times 32) = 25%$ .

Stride $S$ (floats)	Byte gap $S \cdot E$	Threads/sector	$N$	Efficiency
$S = 1$	4 B	8	4 (minimum)	100%
$S = 2$	8 B	4	8	50%
$S = 3$	12 B	2	16	25%
$S = 4$	16 B	2	16	25%
$S = 8$	32 B $= T$	1	32 (worst)	12.5%
$S > 8$	$> T$	—	32	$< 12.5%$
$S = 0$	0 B	sab 32	1 (broadcast)	broadcast

$S = 2$ row aise padho: har 32-byte sector mein $T / (S \cdot E) = 32/8 = 4$ float-slots hain jinhein do threads (8 used bytes) actually touch karte hain, toh $32/4 = 8$ sectors warp cover karte hain — aadhe fetched bytes waste hain, isliye 50%.

DO ENDS KYO FLAT HOTE HAIN. Jab $S \cdot E \geq T$ ho jaata hai, tum pehle hi ek transaction per thread hit kar chuke ho — bade strides $N$ ko 32 se zyada nahi kar sakte, woh sirf har sector ke andar zyada waste karte hain. Aur degenerate case $S = 0$ (har thread same address read karta hai) 32 addresses ek sector mein collapse kar deta hai, toh hardware ek single broadcast karta hai — 1 transaction, sabse sasta. (Agar instead har thread us ek address par write karta hai toh race hoti hai; tools ko 6.2.04-Shared-memory-and-synchronization mein guard karo.)

PICTURE. Stride ke against efficiency plotted: ek staircase 100% se 12.5% tak girta hai, phir flat, $S = 0$ par lone broadcast dot ke saath.

Step 8 — Alignment wrinkle: agar array boundary par shuru na ho toh?

KYA HAI. Upar sab kuch quietly assume karta tha ki array ka base address $T$ ka multiple hai (address $0 mod 32$ ), toh 128 coalesced bytes exactly 4 aligned sectors mein land karte hain. Kya agar data address 0x004 par shuru ho — ek misaligned base? Tab thread $i$ byte $[4 + 4 i, 4 + 4 i + 3]$ read karta hai, aur 128-byte span ban jaata hai $[0 x 004, 0 x 083]$ : yeh 5 sectors mein ghusta hai — sector 0 ka ek sliver, sectors 1–3 sab, aur sector 4 ka ek sliver.

EK EXTRA TRANSACTION KYO COST KARTA HAI. Controller sirf whole aligned sectors fetch kar sakta hai. Ek span jo dono ends par sector boundary cross karta hai worst case mein $⌈ span / T ⌉ + 1$ sectors touch karta hai: yahan $N = 5$ ki jagah $4$ , aur efficiency $128/ (5 \times 32) = 80%$ ho jaati hai. Kuch bhi scatter nahi hua — pattern phir bhi perfectly consecutive hai — tumne sirf off-grid start karne ka "boundary tax" pay kiya.

PICTURE. Consecutive 128-byte span 4 bytes right shift hua, ab 5 teal sectors overlap kar raha hai, dono end-slivers plum mein waste mark hain.

Ek-picture summary

Yeh single figure dono extremes stack karta hai: coalesced (upar) 4 sectors bina waste ke tile karta hai aur ek effective latency pay karta hai; strided (neeche) 32 sectors mein ghusta hai, jo kheencha uska 87.5% waste karta hai, aur 32 latencies pay karta hai. Dono timelines ka ratio headline $32 \times$ hai.

Recall Feynman retelling — seedhe shabdon mein kaho

Memory numbered slots ka ek ruler hai. Jab ek worker koi number maangta hai, machine sirf woh number nahi uthati — woh uske around ek pura fixed-size crate (transaction, yahan 32 bytes) uthati hai, kyunki drawer kholna slow part hai, contents scoop karna nahi. Workers 32 ki gangs mein aate hain (warp) jo bilkul ek hi waqt maangte hain. Machine sab 32 requests dekhti hai aur kam se kam crates kholti hai jo cover kare. Agar 32 numbers side by side hain, chaar crates sab kuch hold kar lete hain aur kuch waste nahi hota — aur kyunki woh chaar crates ek hi DRAM "row" mein hain, slow row-open sirf ek baar pay karte ho. Agar 32 numbers bahut door scatter hain (bada stride), har ek apna crate apni row mein maangta hai: 32 slow row-opens, aur har 32 bytes mein 28 phek diye jaate hain — yahi poori $32 \times$ story hai. In-between strides ke liye, count karo kitne workers ek crate mein fit hote hain aur divide karo. Do wrinkles: agar tera array exactly crate edge par shuru na ho (misaligned), tab bhi side-by-side numbers ek extra crate mein spill ho jaate hain; aur agar 128 bytes do rows mein straddle ho jaayein, toh ek ki jagah do row-opens pay karte ho. Special case: agar sab log same number maangein, ek crate sab ko broadcast kar deta hai — sabse sasta.

Links: Coalesced memory access · 6.2.01-GPU-execution-model · 6.2.04-Shared-memory-and-synchronization · 6.2.09-Memory-hierarchy · 6.3.02-Roofline-model · 5.1.05-Cache-coherence-protocols · 6.2.08 Coalesced memory access (Hinglish)