Exercises — Occupancy and latency hiding

KYA: Occupancy active aur maximum warps ka ratio hai. KYUN: Yahi literally iska definition hai — yahan koi resource limits dhundhne ki zaroorat nahi, hume active-warp count seedha diya gaya hai. $\text{Occupancy}=\frac{48}{64}=0.75=75\%$ Jawab: $75\%$.

Step 1 — warps per block. Ek warp $32$ threads ka hota hai, toh $256/32=8$ warps per block. KYUN 32 se divide karein: hardware hamesha threads ko $32$ ki fixed lanes mein group karta hai; yahi scheduling ki sabse chhoti unit hai. Step 2 — total active warps. $6\text{ blocks}\times 8\text{ warps}=48$ warps. Step 3 — occupancy. $48/64=75\%$. Jawab: $8$ warps/block, $75\%$ occupancy.

Step 1 — registers per warp. Har warp mein $32$ threads hain, toh yeh $64\times 32=2048$ registers consume karta hai. KYUN 32 se multiply karein: $32$ lanes mein se har ek ko har register ki apni private copy chahiye; ek warp ki cost per-thread cost times $32$ hai. Step 2 — kitne aise warps fit honge. $W_{\text{regs}}=\lfloor \frac{65,536}{2048}\rfloor =32\text{ warps}$ KYUN floor $\lfloor \rfloor$: aap fractional warp host nahi kar sakte — jo leftover registers ek poore warp ko cover nahi kar sakte woh simply waste ho jaate hain. Step 3 — occupancy. Koi aur limit nahi, $\min (32,64)=32$. $\text{Occupancy}=\frac{32}{64}=50\%$ Jawab: $32$ warps, $50\%$.

Hume har resource check karna hoga aur minimum lena hoga. Register limit: $W_{\text{regs}}=\lfloor \frac{65,536}{32\times 32}\rfloor =\lfloor \frac{65,536}{1024}\rfloor =64\text{ warps}$ Shared-memory limit: $164$ KB mein kitne $48$ KB blocks fit honge? $\lfloor 164/48\rfloor =3\text{ blocks}\Rightarrow 3\times 8=24\text{ warps}$ Block-count limit: $3$ blocks $32$-block max se kaafi kam hai, toh yeh binding nahi hai. Step — minimum lo: $\min (64,24,64)=24$. $\text{Occupancy}=\frac{24}{64}=37.5\%$ Jawab: shared memory bottleneck hai; $37.5\%$.

KYUN yeh tool: Little's Law exactly yahi answer deta hai "ek latency aur rate diya gaya ho toh pipe full rakhne ke liye kitna in flight hona chahiye". Yahi bilkul hamara sawaal hai — hum latency kam nahi kar rahe, hum use overlap kar rahe hain. $\text{in flight}=L\times \text{throughput}=400\times 1=400\text{ warp-instructions}$ Jawab: $400$ (single-scheduler idealisation). Parent note explain karta hai kyun real SMs ko sirf $16$–$32$ warps chahiye: $4$ schedulers plus instruction-level parallelism SM-wide concurrency supply karte hain.

(a) $W_{\text{regs}}=\lfloor 65536/(128\times 32)\rfloor =\lfloor 65536/4096\rfloor =16$ warps $\Rightarrow 16/64=25\%$. (b) $W_{\text{regs}}=\lfloor 65536/(64\times 32)\rfloor =\lfloor 65536/2048\rfloor =32$ warps $\Rightarrow 32/64=50\%$. (c) KYUN 128 phir bhi jeet sakta hai: agar kernel memory-bound hai, toh $16$ warps shayad load latency hide karne ke liye kaafi hain (yaad karo SM-wide $16$–$32$ warps usually sufficient hain). Saath hi data registers mein rakhne se spills local memory mein avoid hote hain jo har baar hundreds of cycles cost karte hain. Toh bina spills ke $25\%$ spills ke saath $50\%$ ko beat kar sakta hai. Jawab: (a) $25\%$; (b) $50\%$; (c) memory-bound kernels jahan extra registers spilling prevent karte hain.

KYUN loads-per-warp se divide karein: har warp ab $2$ outstanding requests contribute karta hai, toh woh $400$-cycle gap fill karne mein $2$ ka kaam karta hai. $\text{warps}\gtrsim \frac{400}{2}=200\text{ (single-scheduler idealisation)}$ KYUN real number kaafi kam hai: A100 mein $4$ schedulers hain jo consecutive cycles mein alag-alag warps se issue karte hain, aur memory system bahut saare requests parallel mein service karta hai (memory-level parallelism). Idealised figure ko effective SM-wide issue width se divide karo aur aap empirical $16$–$32$ warp range mein pahunch jaoge. Jawab: $\approx 200$ idealised; practice mein $16$–$32$ warps kyunki $4$ schedulers + MLP.

KYA har ek ko limit karta hai: A ki ceiling registers hai; B ki ceiling shared memory. Binding constraint hi ek aise hai jise relax karna worth hai (barrel plank logic). Kernel A: register use kam karna $W_{\text{regs}}$ badhata hai, seedha minimum lift karta hai → occupancy badhti hai. Kernel B: zyada registers kuch nahi karte — shared memory abhi bhi sabse chhota plank hai; aap non-binding limit raise karoge. Jawab: Kernel A fayda uthata hai. B ke liye aapko shared-memory usage kam karni hogi (e.g. chhote tiles).

(a) Har limit check karo.

• Registers: $\lfloor 65536/(80\times 32)\rfloor =\lfloor 65536/2560\rfloor =25$ warps.
• Shared mem: $\lfloor 164/32\rfloor =5$ blocks $\Rightarrow 5\times 4=20$ warps.
• Blocks: $5$ blocks $\le 32$ max, toh blocks $5\times 4=20$ warps dete hain (extra-binding nahi).
• $\min (25,20,20,64)=20\Rightarrow 20/64=31.25\%$. Binding constraint: shared memory (20 warps). (b) Change: shared memory ko $16$ KB/block tak aadha karo. Tab $\lfloor 164/16\rfloor =10$ blocks $\Rightarrow 10\times 4=40$ warps smem ke liye; registers abhi bhi $25$ allow karte hain; block max $\min (10,32)\times 4=40$ allow karta hai. Naya minimum $=\min (25,40,40,64)=25$. $\text{Occupancy}=25/64=39.06\%$ KYUN 25 pe ruk jaata hai, 40 pe nahi: jab shared memory binding nahi rehti, registers naya sabse chhota plank ban jaate hain $25$ warps pe. Synthesis lesson: ek bottleneck fix karna agla expose karta hai. Jawab: (a) $31.25\%$, shared-memory bound. (b) $16$ KB smem → $\approx 39.06\%$, ab register bound.

KYUN roofline: yeh batata hai ek kernel apni intensity se kya ceiling reach kar sakta hai — ridge ke upar compute-bound, neeche memory-bound. Step — ridge-point intensity (jahan dono ceilings milti hain): $A{I}_{\text{ridge}}=\frac{19,500\text{ GFLOP/s}}{1555\text{ GB/s}}\approx 12.54\text{ FLOP/byte}$ Hamara $AI=0.5\ll 12.54$, toh hum ridge ke kaafi neeche hain → memory-bound. (b) Implication: performance data feed karne se set hoti hai, aur moderate occupancy ($\sim 50\%$, yani $16$–$32$ warps) already load latency hide kar leta hai. $100\%$ tak push karna diminishing returns deta hai; better hai coalescing improve karna taaki har transaction useful bytes move kare. Jawab: (a) memory-bound ($0.5\ll 12.54$); (b) ~50% occupancy kaafi hai — occupancy ki jagah coalescing fix karo.

(a) Occupancy.

• P: $\lfloor 65536/(96\times 32)\rfloor =\lfloor 65536/3072\rfloor =21$ warps $\Rightarrow 21/64=32.8\%$.
• S: $\lfloor 65536/(48\times 32)\rfloor =\lfloor 65536/1536\rfloor =42$ warps $\Rightarrow 42/64=65.6\%$. (b) Kaun jeetta hai. Version S occupancy double karta hai — tempting lagta hai. Lekin yeh $2\times 400=800$ cycles ki serial spill latency har thread ke critical path pe add karta hai, jabki P $50$ cycles bachata hai data resident rakh ke. Kyunki kernel memory-bound hai, P ke $21$ warps ($>16$) already SM-wide genuine load latency hide karne ke liye enough concurrency supply karte hain. S mein extra warps kuch naya hide nahi karte lekin spill tax pay karte hain. Decision: Version P faster hai. S mein occupancy badhi, lekin per-thread critical-path latency explode ho gayi — aur jab latency already hidden ho, zyada warps help nahi karte. Jawab: (a) P $\approx 32.8\%$, S $\approx 65.6\%$; (b) P jeetta hai — spills $800$ serial cycles add karte hain jo koi bhi occupancy yahan recover nahi kar sakti.

Warp scheduling view: ek scheduler har cycle mein ek ready warp pick karta hai. Ek stalled warp (apne load ka wait kar raha hai) ready nahi hota, toh agar wahi ek warp hai, scheduler ke paas issue karne ke liye kuch nahi → SM idle ho jaata hai. SM architecture view: bahut saare warps ka context (registers) on-chip simultaneously rehta hai, switch free banata hai — lekin sirf tab jab doosre warps switch karne ke liye exist karein. Ek warp = kuch nahi switch karne ke liye. Little's Law view: in-flight requests needed $=L\times \text{rate}$. Akela warp ek load issue karta hai phir wait karna padta hai; woh apne aap $400$ cycles ke worth independent requests outstanding nahi rakh sakta, kyunki uske baad ke instructions us load ke result pe depend karte hain. Rule of thumb: aapko multiple independent warps chahiye — empirically modern SMs pe $16$–$32$ — taaki $4$ schedulers ko fed rakha ja sake aur memory system busy rahe jab koi bhi warp wait kar raha ho. Jawab: latency hiding inherently ek between-warps mechanism hai; ILP ek warp ke andar dependencies se bounded hai, toh $\ge 16$–$32$ warps practical minimum hai.

Occupancy $=$ active warps divided by maximum warps per SM. Occupancy formula minimum of all resource limits leta hai. Registers per warp charge hote hain per-thread count times 32. Ek akela warp apni load latency hide nahi kar sakta kyunki latency hiding ek between-warps mechanism hai.