Worked examples — SIMT (single instruction multiple thread)

6.2.4 · D3 · Hardware › GPU Architecture › SIMT (single instruction multiple thread)

Yeh page parent SIMT note ki "number pe lao" companion hai. Wahan humne seekha tha ki warp kya hota hai aur divergence kyun hurt karta hai. Yahan hum har tarah ki situation ko grind karte hain jo SIMT model de sakta hai, taaki koi exam ya profiler output tumhe surprise na kar sake.

Shuru karne se pehle, kuch plain-word reminders taaki neeche har symbol samajh aaye:

---

Scenario matrix

Har SIMT problem jo tum miloge woh in cells mein se ek hogi. Neeche ke worked examples mein har ek (Cell A2) jaisi tag carry karta hai taaki tum dekh sako ki poora space cover ho raha hai.

#	Case class	Kya special hai	Covered by
A1	Clean divide	Thread count 32 ka exact multiple hai	Ex 1
A2	Ragged tail	Thread count 32 ka multiple NAHI hai → ek partial warp	Ex 2
A3	Degenerate: 1 thread	Sabse chhota possible launch	Ex 2 (tail)
B1	No divergence	Poora warp ek branch leta hai	Ex 3
B2	2-way divergence	Warp do paths mein split ho jaata hai	Ex 3
B3	Worst-case divergence	Saare 32 threads unique paths lete hain	Ex 4
B4	Nested divergence	Ek branch ke andar ek aur branch	Ex 5
C1	Coalesced memory	stride = element size	Ex 6
C2	Strided / broken	stride > element size	Ex 6
D1	Latency hiding	Stall cover karne ke liye enough warps	Ex 7
D2	Occupancy limit (registers)	Per-thread registers warps ko cap karte hain	Ex 8
D3	Occupancy limit (shared memory)	Per-block shared memory blocks ko cap karta hai	Ex 8
E1	Word problem	Image blur, real grid sizing	Ex 9
E2	Exam twist	Divergence ek for loop bound ke andar chhupa hua	Ex 10

Related deep material Warp Divergence, GPU Memory Coalescing, GPU Occupancy, aur CUDA Thread Hierarchy mein hai.

---

Setup figure: "one instruction, 32 lanes" kaisa dikhta hai

Figure dekho: ek instruction box left pe hai jo 32 lanes mein fan out karta hai. Jab ek lane coloured (lavender) hoti hai, uska thread active hai; jab grey hoti hai, woh thread masked hai. Neeche almost har example bas yahi hai — "kitni lanes coloured hain, aur kitne passes mein?"

---

Ex 1 — Clean divide (Cell A1)

Forecast: Warp count aur koi lane idle hai ya nahi — yeh guess karo aage padhne se pehle.

1. Warps count karo. Warps $=\lceil 256/32\rceil =8$.
   • Yeh step kyun? Hardware hamesha threads ko 32 ke groups mein pack karta hai; ceiling $\lceil \cdot \rceil$ (round up, upar defined) ka matlab hai "koi leftover bhi ek poora warp maangta hai".
2. Partial warp check karo. $256=8\times 32$ exactly, toh remainder $0$ hai.
   • Yeh step kyun? Remainder hi wasted lanes ka source hota hai; yahan koi nahi hai.
3. Warp utilization last warp ki $=32/32=1=100\%$.
   • Yeh step kyun? Utilization batata hai ki 32 lanes mein se kitni lanes ne actually useful work kiya.

Verify: $8\times 32=256$ threads — launch se match karta hai. Zero lanes wasted. ✓

---

Ex 2 — Ragged tail + 1-thread degenerate case (Cells A2, A3)

Forecast: Kya 100 threads ko 3 warps chahiye ya 4? Wasted-lane count guess karo.

1. 100 threads ke liye warps: $\lceil 100/32\rceil =\lceil 3.125\rceil =4$ (ceiling $3.125$ ko $4$ tak round karta hai).
   • Yeh step kyun? $3\times 32=96<100$, toh extra threads ko hold karne ke liye ek fourth warp force ho jaata hai.
2. Last warp mein threads: $100-3\times 32=100-96=4$.
   • Yeh step kyun? Pehle teen warps full hain; jo bhi bachta hai woh warp 3 mein jaata hai.
3. Last-warp utilization: $4/32=0.125=12.5\%$. Wasted lanes $=32-4=28$.
   • Yeh step kyun? Woh 28 lanes phir bhi hardware aur ek scheduling slot consume karti hain lekin kuch produce nahi karti — pure waste.
4. Degenerate 1-thread launch: $\lceil 1/32\rceil =1$ warp, utilization $1/32=3.125\%$.
   • Yeh step kyun? Yeh efficiency ka floor hai — ek thread bhi poora 32-lane warp book karta hai. Yeh dikhata hai ki "bas kuch" threads launch karna kitna terrible hai.

Verify: $3\times 32+4=100$ ✓. Figure mein, last warp 4 lavender lanes aur 28 grey dikhata hai — 12.5% se match karta hai. 1 thread ke liye: 1 lavender, 31 grey. ✓

---

Ex 3 — No divergence vs 2-way divergence (Cells B1, B2)

Forecast: Case (b) mein, kya do paths overlap karti hain ya add hoti hain? Cycle count guess karo.

Pehle, ek naam jo hum use karenge: $T_{\text{diverged}}$ woh total cycles hai jo ek warp spend karta hai jab usे ek se zyada path run karne ke liye force kiya jaata hai, aur $T_{\text{hot}}=10$, $T_{\text{cold}}=30$ har individual path ki cost hai. Yeh sirf statement mein diye numbers ke labels hain.

1. Case (a) — converged. Time $=\max$ over the ek path taken $=10$ cycles.
   • Yeh step kyun? Jab har thread same branch chahta hai, hardware ko kabhi kisi ko mask nahi karna padta — warp us path ko ek baar run karta hai.
2. Case (b) — mask splits. Warp physically ek saath do different instructions run nahi kar sakta, toh woh inhe serially run karta hai: $T_{\text{diverged}}=T_{\text{hot}}+T_{\text{cold}}=10+30=40\text{ cycles.}$
   • Yeh step kyun? Hot phase ke dauran 16 cold threads masked (idle) hain; cold phase ke dauran 16 hot threads masked hain. Idle lanes phir bhi cycles burn karti hain.
3. Lost work. Ek fully converged best case $\max (10,30)=30$ hota. Penalty $40-30=10$ extra cycles hai.
   • Yeh step kyun? $\max$ ke against compare karna us cost ko isolate karta hai jo divergence akele ne add ki.

Verify: Har phase mein sirf 16 of 32 lanes active hain → 50% utilization per phase, parent note se consistent. $10+30=40$ ✓. Dekho Warp Divergence ki mask register yeh kaise drive karta hai.

---

Ex 4 — Worst-case divergence: 32 unique paths (Cell B3)

Forecast: Multiplier guess karo — kya yeh 32× hai?

1. Required passes: ek pass per distinct path $=32$ passes.
   • Yeh step kyun? Do threads koi case share nahi karte, toh warp ko saare 32 serialize karne padte hain.
2. Total time: $32\times 5=160$ cycles.
3. Converged reference: agar sab ek case share karte, $5$ cycles.
4. Slowdown factor: $160/5=32$.
   • Yeh step kyun? Yeh ek 32-thread warp ke liye theoretical maximum divergence penalty hai — tum isse zyada bura nahi kar sakte.

Verify: Har pass mein exactly 1 of 32 lanes active hai → utilization $1/32=3.125\%$, Ex 2 ke 1-thread launch jaisa hi floor. $32\times 5=160$ ✓.

---

Ex 5 — Nested divergence (Cell B4)

Forecast: Kya inner branches outer ke upar add hote hain, ya usse replace karte hain?

1. Outer split cost. if(a) region aur else Z() region do different paths hain → serialize: outer body vs Z.
   • Yeh step kyun? Kyunki a-true threads aur a-false threads alag-alag instructions chahte hain, warp dono ek saath run nahi kar sakta; usе pehle pura a-true arm aur phir a-false arm execute karna padta hai, toh unki costs overlap nahi karti balki add hoti hain.
2. Inner split a-true arm ke andar. Iske andar, X aur Y phir diverge karte hain → serialize: $12+20=32$ cycles. 8-cycle shared test region add karo: $8+32=40$ cycles poore a-true arm ke liye.
   • Yeh step kyun? Nesting penalties stack karta hai — inner divergence inside ek already-diverged arm hoti hai.
3. a-false arm: bas $Z=6$ cycles.
4. Total: do outer arms serial hain: $40+6=46$ cycles.

Verify: Sanity — ek fully converged version roughly $8+\max (12,20)=28$ hota, toh nesting ne humein $46-28=18$ extra cycles cost kiye, jo smaller inner branch (12) plus outer alternative (6) ke barabar hai jo serialize ho gaya. $8+12+20+6=46$ ✓.

---

Ex 6 — Coalesced vs strided memory (Cells C1, C2)

Forecast: (b) ki efficiency guess karo — kya yeh 100% ke paas hai ya 3% ke paas?

1. Actually needed bytes dono taraf: $32\times 4=128$ bytes.
   • Yeh step kyun? Demand identical hai; sirf transfer cost access pattern ke saath change hoti hai.
2. (a) Coalesced. Saare 32 ints ek contiguous 128-byte block mein hain = exactly ek cache line.
   • Bytes transferred $=128$. Efficiency $=128/128=1=100\%$.
3. (b) Strided by 128. Consecutive threads 128 bytes apart land karte hain → har ek alag 128-byte cache line mein padta hai → 32 lines fetch hoti hain.
   • Bytes transferred $=32\times 128=4096$.
   • Efficiency $=128/4096=0.03125=3.125\%$.
   • Yeh step kyun? Efficiency $=\frac{\text{bytes requested}}{\text{bytes transferred}}$; denominator explode karta hai kyunki har useful 4 bytes ek poori wasted line saath kheenchti hai.

Verify: Figure mein coalesced pattern ek line ko fully paint karta hai; strided pattern 32 lines mein har ek mein ek lane touch karta hai. $128/4096=1/32=3.125\%$ ✓. Deep-dive: GPU Memory Coalescing.

---

Ex 7 — Latency hiding (Cell D1)

Forecast: Kya answer 400 ke paas hoga, ya bahut chhota?

Pehle, ek unit jo humein chahiye: ek instruction-slot "ek cycle mein issue ki gayi ek instruction ka kaam" hai. Throughput $T=1$ instruction/cycle pe, pipeline har cycle mein $1$ instruction-slot consume karti hai. Toh $L=400$ cycles ke dauran jab ek memory access in flight hai, pipeline ko busy rehne ke liye $L\cdot T$ instruction-slots ka dusra kaam chahiye — woh product instructions ki count hai, cycles nahi.

1. Raw rule: latency $L$ ko throughput $T$ pe hide karne ke liye, tumhe $W\ge L\cdot T=400\times 1=400$ instruction-slots ka kaam chahiye.
   • Yeh step kyun? Jab ek instruction 400 cycles ke liye in flight hai, idle pipe avoid karne ke liye tumhe 400 aur instruction-slots feed karne padte hain.
2. Lekin ek warp sirf har 4 cycles mein ek instruction supply karta hai, toh har warp un slots mein se 4 cover karta hai: 4 se divide karo. $W\ge \frac{L\cdot T}{4}=\frac{400}{4}=100\text{ warps.}$
   • Yeh step kyun? Hum "instruction-slots" ko "warps" mein convert karte hain har warp ki issue spacing use karke (har 4 cycles mein ek instruction = 4 slots covered per warp).
3. Reality check: ek SM typically ≤ 64 warps hold karta hai, toh $100>64$ → yeh kernel akele 400-cycle latency fully hide nahi kar sakta; tum bahut saare SMs aur higher occupancy pe rely karte ho.

Verify: $400/4=100$ ✓. Kyunki $100>64$, latency sirf partially hidden hai — parent note ke conclusion se match karta hai. Dekho GPU Occupancy.

---

Ex 8 — Occupancy registers se cap, phir shared memory se (Cells D2, D3)

Forecast: Part (b) mein, registers ya shared memory bottleneck hoga?

1. (a) Registers se allowed threads: $\frac{65536}{64}=1024$ threads $\Rightarrow 1024/32=32$ warps.
   • Yeh step kyun? Har resident thread ko apna register slice chahiye; registers ek hard budget hain.
2. (a) Thread-count cap se warps: bhi $1024/32=32$ warps. Active warps $=\min (32,32)=32$, toh occupancy $=32/32=100\%$.
   • Yeh step kyun? Occupancy saare limiters ke upar minimum hai — tumhe har ek check karna hoga.
3. (b) Shared memory se allowed blocks: $\lfloor \frac{49152}{32768}\rfloor =1$ block per SM.
   • Yeh step kyun? Shared memory ek per-block resource hai; agar ek block 48 KB pool mein se 32 KB le leta hai, ek doosra block (aur 32 KB ki zaroorat hai) fit nahi hoga.
4. (b) Shared memory se warps: $1\text{ block}\times \frac{256}{32}=8$ warps. Occupancy $=8/32=25\%$.
   • Yeh step kyun? Ab shared memory ($8$ warps) register/thread limits ($32$ warps) se bahut neeche hai, toh yeh binding constraint ban jaata hai — minimum wins.

Verify: Part (a): $65536/64/32=32$ warps, 100% ✓. Part (b): $\lfloor 49152/32768\rfloor =1$ block, $1\times 8=8$ warps, $8/32=25\%$ ✓. Dekho GPU Occupancy.

---

Ex 9 — Word problem: image blur ke liye grid size karna (Cell E1)

Forecast: Guess karo ki pixel count 256 se cleanly divide hoti hai ya nahi.

1. Total pixels (threads needed): $1920\times 1080=2073600$.
   • Yeh step kyun? Ek thread per pixel ka matlab hai threads = pixels.
2. Blocks: $\lceil 2073600/256\rceil$. Kyunki $2073600/256=8100$ exactly, blocks $=8100$.
   • Yeh step kyun? Ceiling ragged tail handle karta hai; yahan clean hai, toh koi partial block nahi.
3. Warps per block: $256/32=8$. Total warps: $8100\times 8=64800$.
4. Wasted padding threads: launched threads $=8100\times 256=2073600$, exactly pixel count → 0 wasted.
   • Yeh step kyun? Kyunki 2,073,600 ko 256 se divide kiya ja sakta hai, koi thread non-existent pixel compute nahi karta.

Verify: $8100\times 256=2073600=1920\times 1080$ ✓. Warps $8100\times 8=64800$ ✓. Units: threads↔pixels consistent. Dekho CUDA Thread Hierarchy.

---

Ex 10 — Exam twist: loop bound mein chhupa hua divergence (Cell E2)

Forecast: Kya warp 1 iteration mein khatam hota hai ya 10 mein? Trap dekho.

1. Hidden branch spot karo. Ek for loop actually ek repeated branch hai — "aage jaana hai?" — jo har thread har pass mein evaluate karta hai. Kyunki warp lockstep mein run karta hai, usе slowest thread khatam hone tak loop karte rehna padta hai: iterations $=\max (n)=\max (10,1)=10$.
   • Yeh step kyun? Ek bhi lamba thread ($n=10$) poore warp ko saath kheenchta hai; 31 short threads pass 1 ke baad khatam ho jaate hain lekin ja nahi sakte — woh loop continue hone ke dauran masked ho jaate hain.
2. Total cycles. 10 passes mein se har ek 2 cycles cost karta hai: $10\times 2=20$ cycles.
   • Yeh step kyun? Warp ka wall-clock time decide hota hai ki kitne passes physically execute karne hain, na ki har pass mein kitna useful work hai.
3. Actually done useful work. Saare threads ke across total real iterations $=\sum n=10+31\times 1=41$ lane-iterations.
   • Yeh step kyun? Yeh sirf woh iterations count karta hai jinse result mila, masked (idle) lanes ko ignore karta hai.
4. Capacity spent. Warp ne saare 10 passes ke liye 32 lanes open rakheen: $32\times 10=320$ lane-iterations of capacity.
   • Yeh step kyun? Utilization done kaam ko reserved capacity se compare karta hai.
5. Utilization. $\frac{41}{320}=0.128125=12.8125\%\approx 12.8\%$.
   • Yeh step kyun? Pass 1 ke baad, sirf 1 of 32 lanes 9 aur passes ke liye active rehti hai — near-total waste, exactly us tarah ka load imbalance jo profiler flag karega.

Verify: $\max n=10\Rightarrow$ cycles $=10\times 2=20$ ✓. Useful $=10+31=41$, capacity $=32\times 10=320$, utilization $=41/320=0.128125\approx 12.8\%$ ✓. Yeh dikhata hai ki loops ke andar load imbalance if/else divergence jaiti hi deadly hai — Warp Divergence.

---

Recall Quick self-test

100 threads → kitne warps aur last-warp utilization? ::: 4 warps, last warp $4/32=12.5\%$. Ek warp jahan saare 32 threads unique 5-cycle paths lete hain — total cycles? ::: $32\times 5=160$, ek 32× slowdown. Stride-128 access, 4-byte ints, 128-byte lines — coalescing efficiency? ::: $128/4096=3.125\%$. Registers = 65536, 128 regs/thread, 32 max warps — occupancy? ::: $16/32=50\%$. Ek 256-thread block jise 48 KB shared-memory pool mein se 32 KB chahiye — warps aur occupancy? ::: 1 block fit hota hai → 8 warps → $8/32=25\%$. Ek thread 10× loop karta hai, baaki 31 threads 1× loop karte hain, body 2 cycles — warp cycles? ::: $\max (n)\times 2=20$ cycles.