Worked examples — SIMT (single instruction multiple thread)

This page is the "put a number on it" companion to the parent SIMT note. There we learned what a warp is and why divergence hurts. Here we grind through every kind of situation the SIMT model can hand you, so no exam or profiler output can surprise you.

Before we start, some plain-word reminders so every symbol below is earned:

---

The scenario matrix

Every SIMT problem you will meet is one of these cells. The worked examples below each carry a tag like (Cell A2) so you can see the whole space getting covered.

#	Case class	What makes it special	Covered by
A1	Clean divide	Thread count is an exact multiple of 32	Ex 1
A2	Ragged tail	Thread count NOT a multiple of 32 → a partial warp	Ex 2
A3	Degenerate: 1 thread	The smallest possible launch	Ex 2 (tail)
B1	No divergence	Whole warp takes one branch	Ex 3
B2	2-way divergence	Warp splits into two paths	Ex 3
B3	Worst-case divergence	All 32 threads take unique paths	Ex 4
B4	Nested divergence	A branch inside a branch	Ex 5
C1	Coalesced memory	stride = element size	Ex 6
C2	Strided / broken	stride > element size	Ex 6
D1	Latency hiding	Enough warps to cover a stall	Ex 7
D2	Occupancy limit (registers)	Per-thread registers cap the warps	Ex 8
D3	Occupancy limit (shared memory)	Per-block shared memory caps the blocks	Ex 8
E1	Word problem	Image blur, real grid sizing	Ex 9
E2	Exam twist	Divergence hidden inside a for loop bound	Ex 10

Related deep material lives in Warp Divergence, GPU Memory Coalescing, GPU Occupancy, and CUDA Thread Hierarchy.

---

Setup figure: what "one instruction, 32 lanes" looks like

Look at the figure: one instruction box on the left fans out to 32 lanes. When a lane is coloured (lavender), its thread is active; when it is grey, that thread is masked. Almost every example below is just "how many lanes are coloured, and for how many passes?"

---

Ex 1 — Clean divide (Cell A1)

Forecast: Guess the warp count and whether any lane is idle before reading on.

1. Count warps. Warps $=\lceil 256/32\rceil =8$.
   • Why this step? The hardware always packs threads into groups of 32; the ceiling $\lceil \cdot \rceil$ (round up, defined above) means "even a leftover needs a whole warp".
2. Check for a partial warp. $256=8\times 32$ exactly, so remainder is $0$.
   • Why this step? A remainder is the only source of wasted lanes; here there is none.
3. Warp utilization of the last warp $=32/32=1=100\%$.
   • Why this step? Utilization tells us how many of the 32 lanes actually did useful work.

Verify: $8\times 32=256$ threads — matches the launch. Zero lanes wasted. ✓

---

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

Forecast: Will 100 threads need 3 warps or 4? Guess the wasted-lane count.

1. Warps for 100 threads: $\lceil 100/32\rceil =\lceil 3.125\rceil =4$ (the ceiling rounds $3.125$ up to $4$).
   • Why this step? $3\times 32=96<100$, so a fourth warp is forced just to hold the extra threads.
2. Threads in the last warp: $100-3\times 32=100-96=4$.
   • Why this step? The first three warps are full; whatever remains lives in warp 3.
3. Last-warp utilization: $4/32=0.125=12.5\%$. Wasted lanes $=32-4=28$.
   • Why this step? Those 28 lanes still consume hardware and a scheduling slot but produce nothing — pure waste.
4. Degenerate 1-thread launch: $\lceil 1/32\rceil =1$ warp, utilization $1/32=3.125\%$.
   • Why this step? This is the floor of efficiency — one thread still books a whole 32-lane warp. It shows why launching "just a few" threads is terrible.

Verify: $3\times 32+4=100$ ✓. In the figure, the last warp shows 4 lavender lanes and 28 grey — matching 12.5%. For 1 thread: 1 lavender, 31 grey. ✓

---

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

Forecast: In case (b), do the two paths overlap or add? Guess the cycle count.

First, a name we will use: let $T_{\text{diverged}}$ stand for the total cycles a warp spends when it is forced to run more than one path, and $T_{\text{hot}}=10$, $T_{\text{cold}}=30$ be the cost of each individual path. These are just labels for the numbers in the statement.

1. Case (a) — converged. Time $=\max$ over the one path taken $=10$ cycles.
   • Why this step? When every thread wants the same branch, the hardware never has to mask anyone — the warp runs that path once.
2. Case (b) — the mask splits. The warp physically cannot run two different instructions at once, so it runs them serially: $T_{\text{diverged}}=T_{\text{hot}}+T_{\text{cold}}=10+30=40\text{ cycles.}$
   • Why this step? During the hot phase the 16 cold threads are masked (idle); during the cold phase the 16 hot threads are masked. Idle lanes still burn the cycles.
3. Lost work. A fully converged best case would be $\max (10,30)=30$. The penalty is $40-30=10$ extra cycles.
   • Why this step? Comparing against $\max$ isolates the cost that divergence alone added.

Verify: During each phase only 16 of 32 lanes are active → 50% utilization per phase, consistent with the parent note. $10+30=40$ ✓. See Warp Divergence for how the mask register drives this.

---

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

Forecast: Guess the multiplier — is it 32×?

1. Passes required: one pass per distinct path $=32$ passes.
   • Why this step? No two threads share a case, so the warp must serialize all 32.
2. Total time: $32\times 5=160$ cycles.
3. Converged reference: if all shared one case, $5$ cycles.
4. Slowdown factor: $160/5=32$.
   • Why this step? This is the theoretical maximum divergence penalty for a 32-thread warp — you can never do worse than 32×.

Verify: In every pass exactly 1 of 32 lanes is active → utilization $1/32=3.125\%$, the same floor as the 1-thread launch in Ex 2. $32\times 5=160$ ✓.

---

Ex 5 — Nested divergence (Cell B4)

Forecast: Do the inner branches add on top of the outer, or replace it?

1. Outer split cost. The if(a) region and the else Z() region are two different paths → serialize: outer body vs Z.
   • Why this step? Because a-true threads and a-false threads want different instructions, the warp cannot run both at once; it must execute the whole a-true arm first and the a-false arm afterwards, so their costs add rather than overlap.
2. Inner split inside the a-true arm. Within it, X and Y diverge again → serialize: $12+20=32$ cycles. Add the 8-cycle shared test region: $8+32=40$ cycles for the whole a-true arm.
   • Why this step? Nesting stacks penalties — the inner divergence happens inside an already-diverged arm.
3. a-false arm: just $Z=6$ cycles.
4. Total: the two outer arms are serial: $40+6=46$ cycles.

Verify: Sanity — a fully converged version would be roughly $8+\max (12,20)=28$, so nesting cost us $46-28=18$ extra cycles, which equals the smaller inner branch (12) plus the outer alternative (6) that got serialized. $8+12+20+6=46$ ✓.

---

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

Forecast: Guess (b)'s efficiency — is it near 100% or near 3%?

1. Bytes actually needed either way: $32\times 4=128$ bytes.
   • Why this step? The demand is identical; only the transfer cost changes with the access pattern.
2. (a) Coalesced. All 32 ints sit in one contiguous 128-byte block = exactly one cache line.
   • Bytes transferred $=128$. Efficiency $=128/128=1=100\%$.
3. (b) Strided by 128. Consecutive threads land 128 bytes apart → each falls in a different 128-byte cache line → 32 lines fetched.
   • Bytes transferred $=32\times 128=4096$.
   • Efficiency $=128/4096=0.03125=3.125\%$.
   • Why this step? Efficiency $=\frac{\text{bytes requested}}{\text{bytes transferred}}$; the denominator explodes because each useful 4 bytes drags a whole wasted line along.

Verify: In the figure the coalesced pattern paints one line fully; the strided pattern touches one lane per line across 32 lines. $128/4096=1/32=3.125\%$ ✓. Deep-dive: GPU Memory Coalescing.

---

Ex 7 — Latency hiding (Cell D1)

Forecast: Will the answer be near 400, or much smaller?

First, a unit we need: an instruction-slot is "one instruction's worth of work issued in one cycle." At throughput $T=1$ instruction/cycle, the pipeline consumes $1$ instruction-slot every cycle. So over the $L=400$ cycles that one memory access is in flight, the pipeline needs $L\cdot T$ instruction-slots of other work to stay busy — that product is a count of instructions, not cycles.

1. Raw rule: to hide latency $L$ at throughput $T$, you need $W\ge L\cdot T=400\times 1=400$ instruction-slots worth of work.
   • Why this step? While one instruction is in flight for 400 cycles, you must feed 400 other instruction-slots to avoid an idle pipe.
2. But one warp supplies an instruction only every 4 cycles, so each warp covers 4 of those slots: divide by 4. $W\ge \frac{L\cdot T}{4}=\frac{400}{4}=100\text{ warps.}$
   • Why this step? We convert "instruction-slots" into "warps" using each warp's issue spacing (one instruction per 4 cycles = 4 slots covered per warp).
3. Reality check: an SM typically holds ≤ 64 warps, so $100>64$ → this kernel cannot fully hide 400-cycle latency alone; you rely on many SMs and higher occupancy.

Verify: $400/4=100$ ✓. Since $100>64$, latency is only partially hidden — matches the parent note's conclusion. See GPU Occupancy.

---

Ex 8 — Occupancy capped by registers, then by shared memory (Cells D2, D3)

Forecast: In part (b), will registers or shared memory be the bottleneck?

1. (a) Threads allowed by registers: $\frac{65536}{64}=1024$ threads $\Rightarrow 1024/32=32$ warps.
   • Why this step? Every resident thread needs its own register slice; registers are a hard budget.
2. (a) Warps from the thread-count cap: also $1024/32=32$ warps. Active warps $=\min (32,32)=32$, so occupancy $=32/32=100\%$.
   • Why this step? Occupancy is the minimum over all limiters — you must check each.
3. (b) Blocks allowed by shared memory: $\lfloor \frac{49152}{32768}\rfloor =1$ block per SM.
   • Why this step? Shared memory is a per-block resource; if one block eats 32 KB of a 48 KB pool, a second block (needing another 32 KB) won't fit.
4. (b) Warps from shared memory: $1\text{ block}\times \frac{256}{32}=8$ warps. Occupancy $=8/32=25\%$.
   • Why this step? Now shared memory ($8$ warps) is far below the register/thread limits ($32$ warps), so it becomes the binding constraint — the 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\%$ ✓. See GPU Occupancy.

---

Ex 9 — Word problem: sizing a grid for an image blur (Cell E1)

Forecast: Guess whether the pixel count divides cleanly by 256.

1. Total pixels (threads needed): $1920\times 1080=2073600$.
   • Why this step? One thread per pixel means threads = pixels.
2. Blocks: $\lceil 2073600/256\rceil$. Since $2073600/256=8100$ exactly, blocks $=8100$.
   • Why this step? Ceiling handles a ragged tail; here it's clean, so no partial block.
3. Warps per block: $256/32=8$. Total warps: $8100\times 8=64800$.
4. Wasted padding threads: launched threads $=8100\times 256=2073600$, exactly the pixel count → 0 wasted.
   • Why this step? Because 2,073,600 is divisible by 256, no thread computes a non-existent pixel.

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

---

Ex 10 — Exam twist: divergence hidden in a loop bound (Cell E2)

Forecast: Does the warp finish in 1 iteration or 10? Watch the trap.

1. Spot the hidden branch. A for loop is really a repeated branch — "keep going?" — evaluated by every thread each pass. Because the warp runs in lockstep, it must keep looping until the slowest thread is done: iterations $=\max (n)=\max (10,1)=10$.
   • Why this step? Even a single long thread ($n=10$) drags the entire warp along; the 31 short threads finish after pass 1 but cannot leave — they get masked while the loop continues.
2. Total cycles. Each of the 10 passes costs 2 cycles: $10\times 2=20$ cycles.
   • Why this step? The warp's wall-clock time is set by how many passes it must physically execute, not by how much useful work each pass contains.
3. Useful work actually done. Total real iterations across all threads $=\sum n=10+31\times 1=41$ lane-iterations.
   • Why this step? This counts only the iterations that produced a result, ignoring masked (idle) lanes.
4. Capacity spent. The warp held 32 lanes open for all 10 passes: $32\times 10=320$ lane-iterations of capacity.
   • Why this step? Utilization compares work done to capacity reserved.
5. Utilization. $\frac{41}{320}=0.128125=12.8125\%\approx 12.8\%$.
   • Why this step? After pass 1, only 1 of 32 lanes stays active for 9 more passes — a near-total waste, exactly the kind of load imbalance the profiler will flag.

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\%$ ✓. This shows load imbalance inside loops is as deadly as if/else divergence — Warp Divergence.

---

Recall Quick self-test

100 threads → how many warps and last-warp utilization? ::: 4 warps, last warp $4/32=12.5\%$. A warp where all 32 threads take unique 5-cycle paths — total cycles? ::: $32\times 5=160$, a 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\%$. A 256-thread block needing 32 KB of a 48 KB shared-memory pool — warps and occupancy? ::: 1 block fits → 8 warps → $8/32=25\%$. One thread loops 10×, other 31 loop 1×, body 2 cycles — warp cycles? ::: $\max (n)\times 2=20$ cycles.