SIMT (single instruction multiple thread): Exercises

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

Yeh page ek self-test ladder hai. Har problem clearly state ki gayi hai, phir ek hidden solution har step walkthrough karta hai. Pehle khud solve karo, tab reveal karo.

Yahan sab kuch directly parent SIMT note par build karta hai. Shuru karne se pehle, hum har symbol ko re-anchor karte hain taaki kuch bhi assumed na ho.

Definition Woh symbols jo tumhe chahiye (sab yahan define hain)

Thread — sabse chhota worker. Ek thread scalar code ko ek baar, apne data ke slice par run karta hai.
tid (thread ID) — ek single integer jo ek thread ko label karta hai. 1-D launch ke liye yeh compute hota hai $tid = blockIdx \times blockDim + threadIdx$ ke roop mein: block ka number times threads per block, plus thread ki position apne block ke andar. Issi se har thread decide karta hai ki kaunsa data element (data[tid]) use karna hai.
Warp — 32 threads ka ek fixed bundle jo hardware lockstep mein drive karta hai. Ek instruction ek saath saare 32 ko broadcast hoti hai. Dekho Warp Divergence.
Lane — warp ke andar 32 slots mein se ek. Thread number $mod 32$ tumhe lane batata hai.
Block — programmer-chosen group of threads (32 se 1024 tak) jo ek SM par saath run karta hai aur memory share kar sakta hai. Threads, block ke andar warps ban jaate hain. Dekho CUDA Thread Hierarchy.
Grid — ek kernel call se launch hone wali blocks ki poori army. Grid blocks se bani hai; block warps se bana hai; warp 32 threads se bana hai.
SM (Streaming Multiprocessor) — physical engine jo warps hold karta hai aur unhe run karta hai. Dekho Streaming Multiprocessor.
Occupancy — ek SM kitna full hai: active warps divided by maximum jo woh hold kar sakta hai. Dekho GPU Occupancy.

Figure — SIMT (single instruction multiple thread)

Figure s01 — Ek single 32-lane warp ko squares ki 16-by-2 grid ke roop mein draw kiya gaya hai. Pehle 4 squares red se filled hain (lit = active threads), baaki 28 white hain (dark = masked / wasted lanes). Yeh 100-thread launch ka warp 3 hai; sirf 4 lanes real work carry kar rahi hain.

Level 1 — Recognition

Exercise 1.1

Ek kernel 100 threads ke saath launch hoti hai. Warps threads ko order mein 32 ke groups mein kaatke banaye jaate hain. Kitne warps create hote hain, aur last warp ki warp utilization kya hai?

Recall Solution

KYA karte hain: 32 ke groups count karo, phir leftover dekho. KYU: hardware sirf poore warps schedule kar sakta hai; woh hamesha ek full 32-lane warp allocate karta hai chahe kuch lanes ke paas koi thread na ho.

Number of warps $= ⌈ \frac{100}{32} ⌉ = ⌈ 3.125 ⌉ = 4$ warps.

Warps 0, 1, 2 mein se har ek mein 32 threads hain. Isse $3 \times 32 = 96$ threads use hote hain. Last warp (warp 3) mein $100 - 96 = 4$ threads hain.

Last warp ki utilization: $Utilization = \frac{N _{active}}{32} = \frac{4}{32} = 0.125 = 12.5%$

KAISA DIKHTA HAI: light-bulb picture mein, warp 3 ke 4 bulbs jale hain aur 28 dark hain — figure mein red group dekho. Woh 28 dark lanes phir bhi hardware slots lete hain; woh wasted hain.

Exercise 1.2

Kaun sa execution model threads ko different branches lene deta hai: SIMD ya SIMT? Ek word.

Recall Solution

SIMT. SIMD mein (jaise AVX) har lane ko same operation execute karne ki force hoti hai — divergence impossible hai. SIMT mein har thread ka apna logical program counter hota hai, isliye branches allowed hain (serialization ki cost ke saath). Dekho SIMD vs SIMT Comparison.

Level 2 — Application

Exercise 2.1

Ek block mein 256 threads hain. (a) Woh kitne warps hain? (b) Ek grid 1000 aise blocks launch karta hai — total kitne warps?

Recall Solution

KYA karte hain (a): block ke threads ko 32 se divide karo aur round up karo. KYU: ek block ko SM ke andar 32 ke warps mein dice kiya jaata hai jahan woh run karta hai; hardware scheduling unit warp hai, kabhi loose thread nahi, isliye block ke threads ko poore warps mein package karna padta hai. 256 exactly 32 ka multiple hai, isliye koi lane wasted nahi. $⌈ \frac{256}{32} ⌉ = 8 warps per block.$

KYA karte hain (b): warps-per-block ko blocks ki number se multiply karo. KYU: ek grid sirf independent blocks ka collection hai, aur har block same 8 warps contribute karta hai; total work isliye per-block warp count ko saare blocks mein sum karna hai, jo ek simple multiplication hai. $1000 \times 8 = 8000 warps total.$ Dekho CUDA Thread Hierarchy.

Exercise 2.2

Ek warp is branch se guzarta hai, 50/50 split ke saath — 16 threads hot path lete hain, 16 cold path lete hain. Yahan tid thread ID hai jo upar define kiya gaya ( $tid = blockIdx \times blockDim + threadIdx$ ), isliye data[tid] is thread ka apna element hai:

if (data[tid] > threshold)   // tid = blockIdx*blockDim + threadIdx
    hot();   // 10 cycles
else
    cold();  // 30 cycles

Yeh warp kitne cycles spend karta hai, aur effective utilization kya hai?

Recall Solution

KYA karte hain: kyunki dono groups different paths lete hain, warp unhe serially run karta hai — pehle ek branch doosron ko masked karke, phir doosra. KYU: ek single warp sirf EK instruction address par ho sakta hai ek cycle mein. Toh woh branch A fully execute karta hai (16 lanes lit, 16 dark), phir branch B fully (mask flip ho jaata hai).

$T_{diverged} = T_{hot} + T_{cold} = 10 + 30 = 40 cycles$

Hot phase ke dauran, 32 mein se 16 lanes lit hain → 50% utilization. Cold phase ke liye bhi same. Average lit-lane utilization = 50%.

KAISA DIKHTA HAI: bulb row ke do passes; har pass mein exactly aadhe bulbs dark hain (figure s02).

Figure s02 — Same 32-lane warp do baar dikhaya gaya hai, do passes ke roop mein stack karke. "Pass 1: hot() (10 cycles)" mein pehle 16 lanes red hain aur last 16 white hain. "Pass 2: cold() (30 cycles)" mein mask flip ho jaata hai: pehle 16 white hain aur last 16 red. Kyunki dono passes ek ke baad ek run hote hain, total 10 + 30 = 40 cycles hai, aur har pass mein aadhi lanes dark rehti hain (50% utilization).

Level 3 — Analysis

Exercise 3.1

32 threads ka ek warp woh code run karta hai jahan har thread ek unique path leta hai ek 32-way switch ke through, aur har path 10 cycles cost karta hai. Is time ko ek fully-converged warp se compare karo (saare 32 same 10-cycle path par). Slowdown factor kya hai?

Recall Solution

KYA karte hain: count karo kitne serial passes force hote hain. KYU: har distinct path ek alag serialized phase hai; 32 unique paths = 32 phases, har ek mein sirf 1 lane lit.

$T_{diverged} = \sum_{i = 1}^{32} 10 = 32 \times 10 = 320 cycles$ $T_{converged} = max_{i} (10) = 10 cycles$ $Slowdown = \frac{320}{10} = 32 \times$

Yeh SIMT ka worst case hai: $32 \times$ penalty, ek pass mein ek lane lit. Dekho Warp Divergence.

Exercise 3.2

32 threads global memory se read karte hain. Thread $i$ ka address hai $addr_{i} = base + i \cdot stride, each element = 4 bytes .$ (a) stride = 4 bytes aur (b) stride = 128 bytes ke liye coalescing efficiency compute karo. Ek memory transaction ek 128-byte cache line move karta hai. Maano base 128-byte aligned hai (misaligned case ko hum alag note mein treat karte hain neeche).

Recall Solution

Coalescing efficiency $= \frac{bytes actually needed}{bytes physically transferred}$ . Dekho GPU Memory Coalescing.

Warp ko hamesha $32 \times 4 = 128$ bytes of useful data chahiye.

(a) stride = 4 bytes. 32 addresses hain $base, base + 4, \dots, base + 124$ — ek contiguous 128-byte span. Kyunki base ek 128-byte boundary par aligned hai, woh span ek single line ke andar aata hai, isliye yeh ek 128-byte transaction mein fit ho jaata hai. $η_{a} = \frac{128}{128} = 100%$

(b) stride = 128 bytes. Ab consecutive threads ek poori cache line apart hain, isliye 32 mein se har thread ek alag 128-byte line mein jaata hai → 32 transactions, $32 \times 128 = 4096$ bytes move hote hain. $η_{b} = \frac{128}{4096} = 0.03125 = 3.125%$

KAISA DIKHTA HAI: case (a) accesses ka ek tight red bar hai; case (b) 32 scattered red ticks hain, har ek apni poori line drag kar raha hai (figure s03).

Figure s03 — Top row: ek single 128-byte cache line (black rectangle) jiske andar 32 red tick marks packed hain — coalesced, aligned case, ek transaction, 100% efficiency. Bottom row: strided case ka cartoon — chhe labelled cache-line rectangles har ek mein ek red tick ke saath, aur "(showing 6 of 32 lines)" likha hua, saari 32 alag lines represent karte hue. Reality mein 32 aisi rectangles hain; sirf 6 draw ki gayi hain page mein fit karne ke liye. Kyunki 32 mein se har thread apni poori line drag karta hai, woh 32 transactions hain aur sirf 128/4096 = 3.125% efficiency hai.

Level 4 — Synthesis

Exercise 4.1

Tumhe $L = 400$ cycles ki memory latency hide karni hai. SM ko busy rehne ke liye throughput $T = 1$ instruction per cycle chahiye, aur har warp average par sirf har 4 cycles mein ek instruction issue kar sakta hai (baaki time woh wait kar raha hota hai). SM mein kitne warps resident rehne chahiye? Agar SM maximum 64 warps support karta hai, toh kya ek single SM enough hai?

Recall Solution

KYA karte hain: latency-hiding rule use karo aur phir per-warp issue gap ke liye adjust karo. KYU: jab ek warp wait karta hai, doosron ko work supply karni chahiye. Kabhi stall na ho, iske liye warp pool itna bada hona chahiye ki har cycle mein kam se kam ek ready ho.

Latency hide karne ki base requirement: $W \geq L \cdot T = 400 \times 1 = 400 warp-instructions.$

Lekin har warp sirf har 4 cycles mein issue karta hai, isliye ek single warp us kaam ke 4 cycles cover karta hai: $W \geq \frac{400}{4} = 100 warps.$

SM 64 warps par cap karta hai, aur $64 < 100$ . Isliye ek SM enough nahi hai — yahi wajah hai ki GPUs ek deep pipeline ki jagah bahut saare SMs parallel mein use karte hain, aur isliye kernels high occupancy chase karte hain. Dekho bhi GPU vs CPU Architecture.

Exercise 4.2

Exercise 2.1 jaisi hi launch (total 8000 warps). GPU mein 80 SMs hain, har ek 16 warps concurrently run karta hai. Kitne "waves" chahiye, aur total time kya hai agar ek wave $T_{wave}$ cost kare?

Recall Solution

KYA karte hain: pata karo kitne warps ek saath run hote hain, phir total ko ussse divide karo aur round up karo. KYU divide karein: GPU ke paas fixed number of warp slots hain jo kisi bhi instant mein resident hain — 80 SMs har ek mein 16 warps. Ek "wave" har slot ka ek full filling hai; sirf utne warps physically ek saath in-flight ho sakte hain, isliye total work ko us size ke batches mein machine se pour karna padta hai.

Poore GPU mein concurrent warps: $80 \times 16 = 1280 warps at once.$

8000 warps drain karne ke liye waves chahiye: $⌈ \frac{8000}{1280} ⌉ = ⌈ 6.25 ⌉ = 7 waves.$

KYU round up: 6 full waves ke baad, $6 \times 1280 = 7680$ warps done ho jaate hain, $8000 - 7680 = 320$ warps abhi bhi unexecuted rehte hain. Woh 320 warps ko ek poori extra scheduling pass ke liye real slots occupy karne padte hain — hardware "0.25 of a wave" run nahi kar sakta, woh unhe finish karne ke liye ek fresh wave (mostly under-filled) start karta hai. Isliye leftover work hamesha ek aur complete wave force karta hai.

Total time (waves ke beech overlap ignore karke): $T_{total} \approx 7 \cdot T_{wave} .$

Level 5 — Mastery

Exercise 5.1

Ek Ampere-style SM ke paas hai:

65536 registers total,
1024 threads maximum per SM,
64 warps per SM ki hard cap,
65536 bytes (64 KB) shared memory total.

Tumhara kernel 64 registers per thread use karta hai, 256 threads (= 8 warps per block) ke blocks mein run karta hai, aur har block 16384 bytes (16 KB) shared memory request karta hai. Occupancy find karo: kitne warps actually run kar sakte hain, aur woh 64-warp maximum ka kitna fraction hai?

Recall Solution

KYA karte hain: har resource se warp limit compute karo — registers, threads, hardware cap, aur shared memory — phir sabse chhota lo (binding constraint). KYU: ek SM ke paas kai finite resource pools hain, aur unhe sab simultaneously fit karna padta hai. Ek warp tabhi resident ho sakta hai jab har pool jisse woh draw karta hai abhi bhi room ho; isliye SM warps add karna tab rok deta hai jab pehla pool khatam ho jaaye. Isliye occupancy ek $min$ hai independent limits ke upar, koi product ya sum nahi.

Register limit. Ek warp 32 threads ka hai, isliye registers per warp $= 64 \times 32 = 2048$ . $W_{reg} = ⌊ \frac{65536}{2048} ⌋ = 32 warps.$

Thread limit. $\frac{1024}{32} = 32$ warps.

Hardware cap. 64 warps.

Shared-memory limit. Har block ko 16 KB chahiye, aur SM ke paas 64 KB hai, isliye zyada se zyada $⌊ 65536/16384 ⌋ = 4$ blocks fit hote hain. Har block 8 warps ka hai, isliye shared memory $4 \times 8 = 32$ warps allow karta hai.

Binding constraint sabse chhoti hai: $min (32, 32, 64, 32) = 32$ warps.

$Occupancy = \frac{32}{64} = 0.5 = 50%$

Yahan teen alag limits (registers, threads, shared memory) sab humein 32 warps par pin karte hain. Occupancy aur upar push karne ke liye tumhe sab binding ones ko ek saath relieve karna hoga — jaise registers ko 32/thread aur shared memory ko 8 KB/block tak cut karo. Yeh classic GPU Occupancy trade-off hai, Instruction-Level Parallelism se tied.

Exercise 5.2 (Capstone)

Sab kuch combine karo. Ek warp Exercise 2.2 wala branch run karta hai (40 cycles, 50/50 split, hot=10 / cold=30). Maano tum data sort karte ho taaki warp ab fully converged ho jaaye cold path par. (a) Us warp ke liye new time kya hai? (b) Sorting ne diverged 40 cycles ke muqaable mein kya speedup diya?

Recall Solution

KYA karte hain: ek baar fully converge hone par warp ka cost re-evaluate karo, phir old cost ko new se divide karo. KYU (a): jab saare 32 lanes same branch lete hain, toh koi second serialized pass nahi hota — warp poore time ek instruction address par hota hai, isliye iska cost sirf us single branch ka time hai, sum nahi. Yeh exactly Exercise 2.2 ka opposite hai, jahan do different addresses ne do passes force kiye. KYU (b): speedup define hota hai old-time over new-time kyunki yeh measure karta hai ki kaam ab kitni baar tezi se khatam hota hai; extra serial pass ko remove karna precisely wahi hai jo ratio capture karta hai.

(a) Fully converged ka matlab hai saare 32 lanes same branch lete hain, isliye time sirf wahi ek branch hai: $T_{converged} = max (T) = 30 cycles (all cold).$ Koi serialization nahi — ek pass, saare bulbs lit.

(b) Speedup: $\frac{T _{diverged}}{T _{converged}} = \frac{40}{30} \approx 1.33 \times$

Sorting ne second serial pass remove kar diya. Gain yahan modest lagta hai kyunki hot (10) sasta tha; agar dono branches equal-cost hote toh diverged case $2 \times$ slow hota aur sorting throughput double kar deta. Isliye "sort/group by branch outcome" ek top-tier SIMT optimization hai. Dekho Warp Divergence.

Recall Quick self-check (reveal the answers)

Threads ko whole warps tak round up karo? ::: Haan — hamesha $⌈ N /32 ⌉$ . Diverged branch cost sum hai ya max? ::: Sum ( $T_{A} + T_{B}$ ); sirf converged warps $max$ cost karte hain. 32-thread warp ke liye worst-case divergence slowdown? ::: $32 \times$ (har thread unique path). Stride = ek full cache line ke liye coalescing efficiency? ::: $128/4096 = 3.125%$ . Kya cheez ideal 1-transaction coalesced case ko todti hai chahe accesses contiguous hon? ::: Ek misaligned base — 128-byte span do lines straddle karta hai, 2 transactions cost karta hai (50%). Multiple resource limits se occupancy? ::: Minimum limit (registers, threads, cap, shared memory), sum nahi.