Memory hierarchy (global, shared, registers): Visual walkthrough

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

Parent note ne punchline bata di thi: hot data ko paas rakho, aur matrix multiply mein ~15× kam global traffic hogi. Yeh page us number ko zero se derive karta hai. Hum assume nahi karenge ki aap jaante hain "thread", "warp", ya "cycle" kya hota hai. Har symbol ko ek picture pe banate hain, step by step, aur memory trips khud count karte hain.

Step 0 — Words jo hum use kar sakte hain

Kisi bhi formula se pehle, teen plain-word ideas, har ek neeche di gayi picture se pinned.

Aur teen storage places, is hisaab se order ki gayi hain ki worker ko kitna door tak pahunchna padta hai:

Ek cycle sirf GPU ke clock ki ek tick hai — hamaari "kitna time lagega" ki unit. Yeh kehna ki global "400 cycles" hai matlab pantry tak ek walk ~400 arithmetic ticks jitna costly hai.

Figure — Memory hierarchy (global, shared, registers)

Kya / Kyun / Picture. Kya: humne workers aur shelves ke naam rakhe. Kyun: baad mein aane wala har symbol ( $N$ , $r$ , tiles, transactions) sirf inhi se bana hai. Picture: teen shelves distance ke hisaab se stack ki gayi hain — jitna upar chadhoge, utna lamba arrow (walk). Yeh distance-ladder hi poori wajah hai ki hierarchy exist karti hai.

Step 1 — Problem, pantry ki taraf arrows ki tarah draw ki gayi

Hamaara worked example: do $N \times N$ matrices multiply karo, $C = A \times B$ , jahan $N = 1024$ .

To ek thread pantry se $2 N = 2048$ numbers padhta hai — har loop trip mein ek $A$ aur ek $B$ . Algorithm khud dekhne ke liye Matrix Multiplication Optimization dekhein; yahan hum sirf walks count kar rahe hain.

Kya / Kyun / Picture. Kya: humne 2048 global reads per thread count ki. Kyun: yeh hamaara baseline "walk count" hai — baad mein sab kuch iske against measure hoga. Picture: ek thread 2048 lambe arrows door ke pantry mein fire kar raha hai. Arrows ki yeh wall hi problem hai.

Step 2 — Naïve total, honestly count kiya gaya

Har output cell ke liye ek thread hai, to $N^{2} = 102 4^{2} \approx 1, 048, 576$ threads hain (ise "1M" kaho).

Kya / Kyun / Picture. Kya: per-thread walks ko threads ki number se multiply kiya. Kyun: sahi traffic dekhne ke liye, aur waste expose karne ke liye. Picture: $A$ ki wohi row (coral mein highlight ki gayi) us row ke har thread dwara fetch ki jaati hai — bilkul same 1024 numbers, baar baar pantry tak le jaaye jaate hain. Yahi repetition hai jo hum aage plug karenge.

Step 3 — Idea: ek baar fetch karo, kaafi baar reuse karo (tiling)

Har matrix ko $T \times T$ size ke chhote square tiles mein split karo. Hum $T = 16$ use karte hain.

Kya / Kyun / Picture. Kya: shared memory mein parked ek $16 \times 16$ tile introduce ki. Kyun: shared memory global se ~10× closer hai, aur cooperative loading Step 2 ke duplicate walks hata deta hai. Picture: 256 threads (lavender box) har ek ek element pantry se lete hain (lambe arrows), use shared counter par daalte hain, phir compute ke dauran counter se short arrows draw karte hain — ek lambe arrow ke badle kaafi short arrows.

Step 4 — Tiled walks count karo, term by term

Tile ko $k$ -dimension ke paar slide karo. Ek row/column ke saath tiles ki number: $\frac{N}{T} = \frac{1024}{16} = 64 tiles.$

$N = 1024, T = 16$ ke saath: $\frac{2 \cdot 102 4 ^{3}}{16} = 134, 217, 728 \approx 134 million reads.$

Kya / Kyun / Picture. Kya: sharing ke saath total walks dobara count ki. Kyun: honest new number paane ke liye. Picture: ek loaded $A$ -tile row (mint) $T = 16$ alag output cells feed karti hai — ek walk, solah uses.

Step 5 — Speedup, aur $T$ kahan se aata hai

Parent ka "~15×" yahi number hai, practice mein edge/boundary tiles load karne se thoda smooth ho jaata hai. Clean law yeh hai: har fetched value ko $T$ times reuse karo → traffic $T$ se drop hoti hai. Yeh Roofline Model aur Memory Bandwidth Optimization ke peeche arithmetic-intensity lever hai.

Kya / Kyun / Picture. Kya: dono counts divide ki. Kyun: yeh isolate karne ke liye ki speedup kya cause karta hai — woh $T$ hai, aur kuch nahi. Picture: ek bar chart, 2.15B se 134M tak shrink ho raha hai, factor $T = 16$ se gap label kiya gaya hai.

Step 6 — Edge case: shared counter mein 32 lanes hain (bank conflicts)

Humne assume kiya tha ki shared memory uniformly fast hai. Isme ek catch hai. Shared memory banks mein split hoti hai: 32 lanes, har ek per cycle ek request serve karta hai.

Transpose case trap aur fix dikhata hai: ek $32 \times 32$ shared tile column access tile[i][i] ko har thread ke liye lane $i \cdot 32 mod 32 = 0$ par hit karta hai → $S = 32$ , ek 32× slowdown. $32 \times 33$ padding karne se har row ek lane shift ho jaati hai, to ek column saare 32 lanes mein spread ho jaata hai → $S = 1$ .

Kya / Kyun / Picture. Kya: shared memory ko 32 lanes ki tarah model kiya. Kyun: counter tab hi fast hota hai jab team ek lane mein crowd na kare. Picture: left, ek column lane 0 mein jam gaya (coral, serialized); right, [32][33] padding ke baad wohi column saare lanes mein fan out ho gaya (mint, parallel).

Step 7 — Degenerate cases: jab tiling kaam nahi karta

Common mistake Cases jahan

$T$ -law toot jaata hai ya gayab ho jaata hai

$T = 1$ (no tiling): factor $= 1$ . Aap kuch bhi reuse nahi kar rahe — aap wapas Step 2 ke 2.15B walks par aa jaate hain.
Tile shared memory ke liye bahut bada: $2 T^{2}$ floats ~48 KB mein fit hone chahiye. $T = 64$ ko $2 \cdot 6 4^{2} \cdot 4 = 32$ KB chahiye (theek hai); $T = 128$ ko 128 KB chahiye (fit nahi hoga) → occupancy collapse ho jaati hai (parent mein register/occupancy story dekhein).
Algorithm mein koi reuse nahi (jaise element-wise $C = A + B$ ): har value sirf ek baar padhi jaati hai; reuse karne ke liye kuch nahi hai, to shared memory kuch nahi khareedta. Tiling tab hi pay karta hai jab data kaafi baar touch hota hai.
Uncoalesced global loads: agar pantry walk khud scattered hai (parent ke coalescing rule ka Step 8), to walks ki reduced count bhi slow hai — har ek kaafi transactions mein badal jaata hai.

Kya / Kyun / Picture. Kya: $T$ ki boundary values aur no-reuse case sweep kiya. Kyun: contract kehta hai har case dikhana zaroori hai — including tab bhi jab trick fail ho. Picture: $T$ -vs-speedup curve, $T = 1$ par flat 1 se, upar jaata hai, phir shared-memory limit ke baad ek red "won't fit" wall.

Ek-picture summary

Ek thread ki 2048 far-pantry walks (Step 1) × 1M threads = 2.15 B walks (Step 2, duplicates se bhari). Shared counter par ek $T \times T$ tile park karo (Step 3), har fetched value ko $T$ baar reuse karo (Step 4), aur total walks $2 N^{3} / T$ tak gir jaati hain — ek clean $T$ × win (Step 5) — bas counter ki 32 lanes jam na hon (Step 6) aur tile fit ho real reuse ke saath exploit karne ke liye (Step 7).

Recall Feynman retelling — apne words mein wapas bolo

Ek chef ki imagine karo jo door ke pantry se laata hai. Naïvely, har dish chef ko usi onion ke liye baar baar pantry bhejtii hai — do billion trips, mostly repeats. Fix: ek runner ko bheho ki ingredients ki ek tray le aaye aur shared counter par rakh de; ab sab counter se cook karte hain, pantry mein ek baar per tray jaate hain ek baar per pinch ki jagah. 16 width ki tray ka matlab hai har ingredient ko har fetch mein 16 baar use kiya jaata hai, to trips 16-guna girte hain. Do cautions: counter mein 32 narrow slots hain, aur agar poori team ek slot se pakdti hai to queue mein lag jaate hain (fix: layout ko thoda nudge karo taaki spread ho); aur agar koi recipe har ingredient sirf ek baar use kare, to reuse karne ke liye kuch nahi — tray kisi ke kaam nahi aati.

Reveal-check:

N = 1024

ke liye total naïve reads

2 N^{3} = 2.15

billion

N = 1024, T = 16

ke liye total tiled reads

2 N^{3} / T = 134

million

Traffic-reduction factor barabar hota hai

tile width

T

[32][32] diagonal-column access ke liye bank-conflict serialization

S

Shared tile ko [32][33] pad kyun karte hain

taaki har row ek bank shift ho aur ek column saare 32 lanes mein spread ho (

S = 1

)

Related: Memory Latency Hiding · Cache Architecture · GPU Thread Hierarchy · CUDA Memory Types