Memory hierarchy (global, shared, registers): Worked examples

6.2.7 · D3 · Hardware › GPU Architecture › Memory hierarchy (global, shared, registers)

Yeh page ek drill hai. Hum parent note ke teen storage levels — registers, shared memory, global memory — lete hain aur har tarah ke arithmetic questions attack karte hain jo exams mein aa sakte hain. Shuru karne se pehle, ek promise: yahan koi bhi symbol bina plain-word meaning ke nahi aayega. Vocabulary ek baar fix kar lete hain.

Scenario matrix

Har memory question in cells mein se ek hai. Neeche ke examples mein cell label lagaa hai.

Cell	Kya ise different banata hai	Example
A. Register limit	register budget bottleneck hai	Ex 1
B. Register tie / zero slack	division exact nikli, koi waste nahi	Ex 2
C. Register vs thread-cap	ek alag limit jeet jaati hai	Ex 3
D. Shared-memory limit	scratchpad bottleneck hai, registers nahi	Ex 4
E. Bank conflict — worst case	sab threads ek bank pe (serialize ×32)	Ex 5
F. Bank conflict — padding fix	ek number badlo, conflict khatam	Ex 6
G. Coalescing — best case	ek memory transaction	Ex 7
H. Coalescing — strided / worst case	32 transactions, degenerate access	Ex 7
I. Word problem	tiling se real speedup	Ex 8
J. Exam twist / limiting value	kaunsa resource occupancy cap karta hai? knob ko extreme pe push karo	Ex 9

Hum hamesha occupancy compute karenge: SM ke maximum threads ka woh fraction jo actually busy hai.

$Occupancy = \frac{N _{active}}{N _{max}}$

Kyun care karein? Ek idle SM global memory ke lambe wait ko hide nahi kar sakta. Zyada occupancy matlab zyada threads ready hain run karne ke liye jab doosre wait kar rahe hain. (Dekho Memory Latency Hiding.)

Figure — Memory hierarchy (global, shared, registers)

Upar ka bar chart har register/shared example ke liye mental picture hai: ek SM ke paas ek register pile aur ek scratchpad hota hai. Aap jo bhi block launch karte ho woh dono se ek bite leta hai. Jab kisi bhi bite se overflow ho jaye, aur blocks fit nahi honge.

Cell A — Register limit bottleneck hai

Worked example Ex 1 — registers block count cap karte hain

Ek SM ke paas $R_{total} = 65536$ registers aur thread cap $N_{m a x} = 2048$ hai. Ek kernel 512 threads/block launch karta hai aur 40 registers/thread use karta hai. Kitne blocks fit honge, aur occupancy kya hai?

Forecast: padhne se pehle guess karo — kya occupancy 100% hogi, ya kam?

Step 1. Ek block ko kitne registers chahiye. $R_{block} = 512 \times 40 = 20480$ Yeh step kyun? Ek block ke threads sab ek hi SM pe ek saath rehte hain, toh unki register demands add up hoti hain. Yahi woh bite hai jo block leta hai.

Step 2. Pile mein kitne complete blocks fit honge. $N_{blocks} = ⌊ \frac{65536}{20480} ⌋ = ⌊ 3.2 ⌋ = 3$ Yeh step kyun? Sirf whole blocks run hote hain, isliye hum floor lete hain. Bacha hua $65536 - 3 \times 20480 = 4096$ registers stranded hain — 4th block ke liye enough nahi.

Step 3. Active threads aur occupancy. $N_{active} = 3 \times 512 = 1536, Occupancy = \frac{1536}{2048} = 0.75 = 75%$

Verify: $3 \times 20480 = 61440 \leq 65536$ ✓ (fits) aur $4 \times 20480 = 81920 > 65536$ ✓ (4 overflow karta). Register limit ne decide kiya, thread cap ne nahi: $1536 < 2048$ .

Cell B — Exact division, zero slack

Worked example Ex 2 — division poori tarah exact nikli

Same SM ( $R_{total} = 65536$ , $N_{m a x} = 2048$ ). Kernel 256 threads/block aur 32 registers/thread use karta hai.

Forecast: is baar koi registers waste honge?

Step 1. Registers per block. $R_{block} = 256 \times 32 = 8192$ Yeh step kyun? Wahi reasoning jaise hamesha: ek block ke 256 threads SM pe saath baithte hain, isliye unki register demands add up karte hain taaki pata chale yeh block pile se kitna bada bite leta hai.

Step 2. Kitne blocks fit honge. $N_{blocks} = ⌊ \frac{65536}{8192} ⌋ = ⌊ 8.0 ⌋ = 8$ Yeh step kyun? Yahan $65536 = 8 \times 8192$ exactly hai — floor kuch nahi badalta. Yeh degenerate "no-waste" case hai: zero stranded registers.

Step 3. Threads aur occupancy. $N_{active} = 8 \times 256 = 2048, Occupancy = \frac{2048}{2048} = 100%$

Verify: $8 \times 8192 = 65536$ , bilkul budget ke barabar, remainder $0$ ✓. Aur $2048$ thread cap pe exactly hit karta hai — dono limits saath saturate hoti hain. Yahi woh sweet spot hai jise har tuning guide dhundta hai.

Cell C — Ek alag limit jeet jaati hai (thread cap)

Worked example Ex 3 — registers "aur" kehte hain, lekin thread cap "nahi" kehta

Same SM. Kernel 256 threads/block use karta hai lekin sirf 16 registers/thread (ek bahut light kernel).

Forecast: registers ab saste hain — kya occupancy 100% todega? (Trick: nahi tod sakta.)

Step 1. Register-limited block count. $R_{block} = 256 \times 16 = 4096, ⌊ \frac{65536}{4096} ⌋ = 16 blocks$ Yeh step kyun? Sirf registers ke hisaab se, 16 blocks fit hote hain.

Step 2. Thread-cap block count. $⌊ \frac{N _{m a x}}{threads/block} ⌋ = ⌊ \frac{2048}{256} ⌋ = 8 blocks$ Yeh step kyun? SM kabhi $2048$ se zyada live threads hold nahi kar sakta, chahe kitne bhi registers free hों. Yeh ek alag ceiling hai.

Step 3. Real answer chhoti limit hai. $N_{blocks} = min (16, 8) = 8, N_{active} = 2048, Occupancy = 100%$ Yeh step kyun? Dono ceilings ek saath hold karni chahiye — hardware har rule ek saath obey karta hai, isliye woh sirf utne blocks fit kar sakta hai jitne strictest rule permit karta hai. Yahi "minimum" ka matlab hai: tightest limit jeet jaati hai, aur koi bhi looser limit ke paas room bachta hai.

Verify: $8 \times 4096 = 32768 \leq 65536$ (registers spare hain) lekin $8 \times 256 = 2048 = N_{m a x}$ (thread cap full). Lesson: hamesha sab resource limits ka min lo. Spare registers extra threads nahi dilaate.

Cell D — Shared memory bottleneck hai

Worked example Ex 4 — scratchpad pehle khatam ho jaata hai

Ek SM ke paas 48 KB shared memory, $R_{total} = 65536$ registers, $N_{m a x} = 2048$ hai. Har block 256 threads launch karta hai, 32 registers/thread use karta hai, aur 20 KB shared memory allocate karta hai.

Forecast: ab teen limits hain — registers, threads, shared memory. Kaunsa pehle bite karta hai?

Step 1. Register limit (blocks). $256 \times 32 = 8192$ , toh $⌊ 65536/8192 ⌋ = 8$ blocks. Yeh step kyun? Teen alag ceilings mein se pehli — hum poochhte hain ki sirf register pile kitne blocks allow karti hai, bilkul Ex 1 ki tarah.

Step 2. Thread-cap limit. $⌊ 2048/256 ⌋ = 8$ blocks. Yeh step kyun? Doosri ceiling — SM ka live threads par hard cap, memory se independent, bilkul Ex 3 ki tarah.

Step 3. Shared-memory limit. $⌊ \frac{48 KB}{20 KB} ⌋ = ⌊ 2.4 ⌋ = 2 blocks$ Yeh step kyun? Har block scratchpad ka apna private 20 KB slice reserve karta hai — blocks ek doosre ki shared memory share nahi karte. Do blocks 40 KB use karte hain; teesra 60 KB maangta jo 48 KB se zyada hai.

Step 4. Min lo. $N_{blocks} = min (8, 8, 2) = 2, N_{active} = 512, Occupancy = \frac{512}{2048} = 25%$ Yeh step kyun? Ex 3 ki tarah, teeno ceilings simultaneously hold karni chahiye, toh true block count unka sabse chhota hai. Yahan shared memory sabse tight hai, toh wahi akela answer decide karta hai.

Verify: $2 \times 20 = 40 KB \leq 48$ ✓, $3 \times 20 = 60 > 48$ ✓. Registers aur threads ke paas bahut room tha, phir bhi shared memory ne occupancy $25%$ tak gira di. Isliye aap teeno resources budget karte ho.

Cell E — Bank conflict, worst case

Neeche ki figure bilkul yahi idea draw karti hai: upar 32 boxes ki row 32 bank-doors hain, orange arrows Ex 5 ka worst case dikhate hain (sab arrows ek door pe crash karte hue), aur teal arrows Ex 6 ka fixed case dikhate hain (ek arrow per door). Dono examples padhte waqt ise dekhte raho.

Worked example Ex 5 — ek 32×32 tile ka column read

Ek warp float tile[32][32] ka column 0 read karta hai: thread $t$ , tile[t][0] read karta hai, jiska byte address $a_{t} = t \times 32 \times 4 = 128 t$ hai. Figure mein, yeh orange arrows ka fan hai jo sab door 0 ki taraf point karte hain.

Forecast: kitne banks hit honge — 32 ya 1?

Step 1. Thread $t$ kaunsa bank hit karta hai? $bank (128 t) = (\frac{128 t}{4}) mod 32 = (32 t) mod 32 = 0.$ Yeh step kyun? Kyunki ek poori row 32 words wide hai, ek row neeche jaane se aap poore 32 words ka multiple move karte ho — wapas bank 0 pe. Har thread bank 0 pe land karta hai.

Step 2. Serialization factor. $S = 32 (sab 32 threads bank 0 pe)$ Yeh step kyun? Ek door, 32 knock → ek ek karke queue lagti hai.

Verify: effective latency $= 32 \times$ base. Ek square tile ka column read textbook worst case hai — 32-way conflict. Dekho CUDA Memory Types transpose kernels mein yeh kaise kaat ta hai.

Cell F — Ek number ka padding fix

Worked example Ex 6 — 33 columns tak pad karo

Same column read, lekin ab float tile[32][33] declare karo. Thread $t$ , tile[t][0] read karta hai, address $a_{t} = t \times 33 \times 4 = 132 t$ . Figure mein, yeh teal arrows ka set hai, har ek apne alag door mein jaata hai.

Forecast: kya ek unused column add karne se sach mein sab 32 threads untangle ho jaate hain?

Step 1. Thread $t$ ke liye naya bank. $bank (132 t) = (\frac{132 t}{4}) mod 32 = (33 t) mod 32 = (t) mod 32 = t .$ Yeh step kyun? $33 \equiv 1 (mod 32)$ , toh ek row aage jaana ab bank ko $0$ ki jagah exactly 1 advance karta hai. Threads $0..31$ banks $0..31$ mein spread ho jaate hain.

Step 2. Serialization factor. $S = 1 (har thread apne bank pe)$ Yeh step kyun? Hum $S$ compute karte hain — kisi ek door pe sabse badi crowd — taaki Step 1 ke bank map ko actual slowdown number mein badal sakein. Yahan har door par exactly ek visitor hai, toh worst crowd $1$ hai: koi queue nahi, ek single cycle mein full parallel service.

Verify: padding column kabhi read nahi hota (index 32 unused), toh correctness untouched rehti hai, phir bhi $S$ $32$ se $1$ ho gaya — us access par $32 \times$ speedup. Yahi parent ke transpose example ka tile[32][33] trick hai.

Cells G & H — Coalescing, best aur worst

Neeche ki figure neeche ke dono cases ki picture hai: upar ka teal band coalesced case hai (ek crate poore warp ko cover karta hai), aur neeche ke orange scattered boxes strided case hain (har thread apne crate mein alag hai). Ex 7 padhte waqt ise refer karo.

Worked example Ex 7 — same warp, best vs worst access pattern

32 threads ka ek warp float values (4 bytes each) read karta hai. Do patterns compare karo — figure mein teal band aur orange scatter.

Forecast: good aur bad pattern ke beech gap kitna bada hai?

Case G (coalesced). Thread $t$ address $a + 4 t$ read karta hai, toh addresses $a, a + 4, \dots, a + 124$ chalte hain.

Step 1. Total bytes span touched. $32 \times 4 = 128 bytes.$ Yeh step kyun? Agar ek warp ka poora footprint ek 128-byte crate hai (aur aligned hai), toh yeh ek single fetch mein fit ho jaata hai. $N_{transactions} = ⌈ \frac{128}{128} ⌉ = 1.$

Case H (strided, degenerate). Thread $t$ , $a + 256 t$ read karta hai — har 64 mein se ek float grab karta hai.

Step 2. Har thread alag crate mein land karta hai. $stride 256 bytes > 128 byte segment \Rightarrow N_{transactions} = 32.$ Yeh step kyun? Consecutive threads 256 bytes apart hain, ek crate se zyada wide, toh har ek ko apna crate chahiye. Hum 32 crates fetch karte hain lekin har ek se sirf 4 useful bytes use karte hain.

Step 3. Bandwidth ratio. $\frac{N _{worst}}{N _{best}} = \frac{32}{1} = 32.$

Verify: useful bytes dono cases mein $128$ hain, lekin bytes moved hain $128$ (coalesced) vs $32 \times 128 = 4096$ (strided). Efficiency $128/4096 = 1/32 \approx 3.1%$ . Ek $32 \times$ penalty — worst bank conflict jitna same factor, usi "ek lane, kai requests" logic se.

Cell I — Real-world word problem

Worked example Ex 8 — tiling se actually kitna save hota hai?

Do $1024 \times 1024$ matrices multiply karo $16 \times 16$ tiles (256 threads/block) ke saath. Naive version vs tiled version ke liye global reads compare karo. (Background: Matrix Multiplication Optimization.)

Forecast: speedup guess karo — 2×? 15×? 100×?

Step 1. Naive traffic. Har output element $C_{ij}$ ko $A$ ki poori row aur $B$ ka column chahiye: $2 \times 1024$ reads. Ek thread per output element, $102 4^{2}$ elements. $T_{naive} = 2 \times 1024 \times 102 4^{2} = 2, 147, 483, 648 \approx 2.15 billion reads.$ Yeh step kyun? Kuch reuse nahi hota; har multiply-add slow global memory se re-fetch karta hai.

Step 2. Tiled traffic. Matrix $1024/16 = 64$ tiles wide hai. Har block 64 tile-steps sweep karta hai, har step mein $A$ ka ek $16 \times 16$ tile aur $B$ ka ek load karta hai: $2 \times 256 = 512$ reads per step. Blocks: $(1024/16)^{2} = 6 4^{2} = 4096$ . $T_{tiled} = steps 64 \times reads/step 512 \times blocks 4096 = 134, 217, 728 \approx 134 million reads.$ Yeh step kyun? Har loaded value fast shared memory se 16 baar reuse hota hai discard hone se pehle, toh global traffic roughly tile width se drop karta hai.

Step 3. Speedup. $\frac{T _{naive}}{T _{tiled}} = \frac{2 , 147 , 483 , 648}{134 , 217 , 728} = 16.$ Yeh step kyun? Hum do traffic totals divide karte hain payoff dekhne ke liye. Ratio exactly $16$ pe land karna koi accident nahi: ek tile mein pull ki gayi har value $16$ baar use hoti hai (ek $16$ -wide tile ki row/column mein se har ek ke liye ek baar) shared memory chhodne se pehle, toh har global read ab $16$ naive reads ka kaam karta hai. Tile width aur speedup same number hain — yeh equality hamara built-in sanity check hai.

Verify: ratio tile width $16$ ke barabar hai — exactly reuse factor. (Parent ne "~15×" quote kiya tha; usne coarser per-block count use kiya tha. Clean per-value accounting exactly $16 \times$ deta hai.) Roofline intuition: humne ek memory-bound kernel ko compute-bound ki taraf move kiya. Dekho Roofline Model.

Cell J — Exam twist / limiting value

Worked example Ex 9 — register usage ko extreme tak push karo

Ek SM ke paas $R_{total} = 65536$ registers, $N_{m a x} = 2048$ threads, 128 threads ke blocks hain. Compiler report karta hai 255 registers/thread (hardware ceiling 256 ke paas). Occupancy kya hai? Phir: 100% reach karne ke liye kitne registers chahiye?

Forecast: registers max tak push karne par, kya ek bhi block fit hoga?

Step 1. Extreme par registers per block. $R_{block} = 128 \times 255 = 32640.$ Yeh step kyun? Har register example ki tarah wahi bite-adding rule: 128 threads jo 255 registers demand karte hain unhe saath resident rehna hai.

Step 2. Blocks by registers. $⌊ \frac{65536}{32640} ⌋ = ⌊ 2.007 ⌋ = 2 blocks.$ Yeh step kyun? Near-max register greed par bhi, 2 blocks muskil se squeeze karte hain. Teesre ko $97920 > 65536$ chahiye, toh floor $2.007$ ko $2$ tak kaata hai.

Step 3. Extreme par occupancy. $N_{active} = 2 \times 128 = 256, Occupancy = \frac{256}{2048} = 12.5%.$ Yeh step kyun? Yeh limiting behaviour hai: register knob ko uski ceiling ki taraf push karo aur occupancy apne floor ki taraf collapse karti hai — yahan SM ka ek-aathvan hissa reh jaata hai.

Step 4. Question reverse karo — 100% ke liye kitne registers chahiye? $2048$ threads fill karne ke liye hume $2048/128 = 16$ blocks chahiye. Allowed registers per block: $65536/16 = 4096$ . Per thread: $r_{m a x} = \frac{4096}{128} = 32 registers/thread.$ Yeh step kyun? Hum poora budget poore thread cap mein evenly divide karte hain — yeh back-solve karta hai sabse bada register count nikalne ke liye jो $2048$ thread slots mein se har ek fill hone deta hai.

Verify: $r = 32$ par: $128 \times 32 = 4096$ , $⌊ 65536/4096 ⌋ = 16$ blocks $\times 128 = 2048$ threads $= 100%$ ✓. $32$ se $255$ registers/thread jaane par occupancy $100%$ se $12.5%$ tak crush ho gayi — ek $8 \times$ fall. Yahi poori register-pressure story ek slide mein hai.

Recall Self-test — answers cover karo

Ex 1 occupancy ::: 75% (register-limited to 3 blocks) Ex 2 occupancy ::: 100% (exact division, 8 blocks, 2048 threads) Ex 3 winning limit ::: thread cap (min of 16 and 8 blocks = 8) Ex 4 occupancy ::: 25% (shared memory limits to 2 blocks) Ex 5 serialization factor ::: 32 (sab threads bank 0 hit karte hain) Ex 6 serialization factor after 33-padding ::: 1 (har thread apna bank) Ex 7 coalesced vs strided transaction ratio ::: 32× Ex 8 tiling speedup ::: 16× fewer global reads Ex 9 registers/thread for 100% occupancy ::: 32