SIMT (single instruction multiple thread): Exercises

This page is a self-test ladder. Each problem is stated cleanly, then a hidden solution walks every step. Work it yourself first, then reveal.

Everything here builds directly on the parent SIMT note. Before we start, we re-anchor every symbol so nothing is assumed.

Definition The symbols you need (all defined here)

Thread — the smallest worker. One thread runs the scalar code once, on its own slice of data.
tid (thread ID) — a single integer that labels a thread. For a 1-D launch it is computed as $tid = blockIdx \times blockDim + threadIdx$ : the block's number times how many threads per block, plus the thread's position inside its block. It is how each thread picks which data element (data[tid]) to work on.
Warp — a fixed bundle of 32 threads that the hardware drives in lockstep. One instruction is broadcast to all 32 at once. See Warp Divergence.
Lane — one of the 32 slots inside a warp. Thread number $mod 32$ tells you the lane.
Block — a programmer-chosen group of threads (32 to 1024) that runs together on one SM and can share memory. Threads become warps inside a block. See CUDA Thread Hierarchy.
Grid — the whole army of blocks launched by one kernel call. A grid is made of blocks; a block is made of warps; a warp is made of 32 threads.
SM (Streaming Multiprocessor) — the physical engine that holds warps and runs them. See Streaming Multiprocessor.
Occupancy — how full an SM is: active warps divided by the maximum it can hold. See GPU Occupancy.

Figure — SIMT (single instruction multiple thread)

Figure s01 — A single 32-lane warp drawn as a 16-by-2 grid of squares. The first 4 squares are filled red (lit = active threads), the remaining 28 are white (dark = masked / wasted lanes). This is warp 3 of a 100-thread launch; only 4 of its 32 lanes carry real work.

Level 1 — Recognition

Exercise 1.1

A kernel is launched with 100 threads. Warps are formed by cutting the threads into groups of 32 in order. How many warps are created, and what is the warp utilization of the last warp?

Recall Solution

WHAT we do: count groups of 32, then look at the leftover. WHY: the hardware can only schedule whole warps; it always allocates a full 32-lane warp even if some lanes have no thread.

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

Warps 0, 1, 2 each hold 32 threads. That uses $3 \times 32 = 96$ threads. The last warp (warp 3) holds $100 - 96 = 4$ threads.

Utilization of the last warp: $Utilization = \frac{N _{active}}{32} = \frac{4}{32} = 0.125 = 12.5%$

WHAT IT LOOKS LIKE: in the light-bulb picture, warp 3 has 4 bulbs lit and 28 dark — see the red group in the figure. Those 28 dark lanes still cost hardware slots; they are wasted.

Exercise 1.2

Which execution model allows threads to take different branches: SIMD or SIMT? One word.

Recall Solution

SIMT. In SIMD (e.g. AVX) every lane is forced to execute the same operation — divergence is impossible. In SIMT each thread has its own logical program counter, so branches are allowed (paid for with serialization). See SIMD vs SIMT Comparison.

Level 2 — Application

Exercise 2.1

A block has 256 threads. (a) How many warps is that? (b) A grid launches 1000 such blocks — how many warps total?

Recall Solution

WHAT we do (a): divide the block's threads by 32 and round up. WHY: a block is diced into warps of 32 inside the SM it runs on; the hardware scheduling unit is the warp, never the loose thread, so the block's threads must be packaged into whole warps. 256 is an exact multiple of 32, so no lane is wasted. $⌈ \frac{256}{32} ⌉ = 8 warps per block.$

WHAT we do (b): multiply warps-per-block by the number of blocks. WHY: a grid is just a collection of independent blocks, and each block contributes the same 8 warps; total work is therefore the per-block warp count summed across all blocks, which is a plain multiplication. $1000 \times 8 = 8000 warps total.$ See CUDA Thread Hierarchy.

Exercise 2.2

A warp hits this branch, with a 50/50 split — 16 threads take the hot path, 16 take the cold path. Here tid is the thread ID defined at the top ( $tid = blockIdx \times blockDim + threadIdx$ ), so data[tid] is this thread's own element:

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

How many cycles does this warp spend, and what is the effective utilization?

Recall Solution

WHAT we do: because the two groups take different paths, the warp runs them serially — first one branch with the others masked, then the other. WHY: a single warp can only be at ONE instruction address per cycle. So it executes branch A fully (16 lanes lit, 16 dark), then branch B fully (the mask flips).

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

During the hot phase, 16 of 32 lanes are lit → 50% utilization. Same for the cold phase. Average lit-lane utilization = 50%.

WHAT IT LOOKS LIKE: two passes of the bulb row; each pass has exactly half the bulbs dark (figure s02).

Figure s02 — The same 32-lane warp shown twice, stacked as two passes. In "Pass 1: hot() (10 cycles)" the first 16 lanes are red and the last 16 are white. In "Pass 2: cold() (30 cycles)" the mask flips: the first 16 are white and the last 16 red. Because the two passes run one after the other, the total is 10 + 30 = 40 cycles, and each pass leaves half the lanes dark (50% utilization).

Level 3 — Analysis

Exercise 3.1

A warp of 32 threads runs code where every thread takes a unique path through a 32-way switch, and each path costs 10 cycles. Compare the time against a fully-converged warp (all 32 on the same 10-cycle path). What is the slowdown factor?

Recall Solution

WHAT we do: count how many serial passes are forced. WHY: each distinct path is a separate serialized phase; 32 unique paths = 32 phases, each with only 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$

This is the worst case of SIMT: a $32 \times$ penalty, one lane lit per pass. See Warp Divergence.

Exercise 3.2

32 threads read from global memory. The address of thread $i$ is $addr_{i} = base + i \cdot stride, each element = 4 bytes .$ Compute the coalescing efficiency for (a) stride = 4 bytes and (b) stride = 128 bytes. A memory transaction moves one 128-byte cache line. Assume base is 128-byte aligned (we treat the misaligned case separately in the note below).

Recall Solution

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

The warp always needs $32 \times 4 = 128$ bytes of useful data.

(a) stride = 4 bytes. The 32 addresses are $base, base + 4, \dots, base + 124$ — a contiguous 128-byte span. Because base is aligned to a 128-byte boundary, that span lands inside a single line, so it fits in one 128-byte transaction. $η_{a} = \frac{128}{128} = 100%$

(b) stride = 128 bytes. Now consecutive threads are one full cache line apart, so each of the 32 threads lands in a different 128-byte line → 32 transactions, moving $32 \times 128 = 4096$ bytes. $η_{b} = \frac{128}{4096} = 0.03125 = 3.125%$

WHAT IT LOOKS LIKE: case (a) is one tight red bar of accesses; case (b) is 32 scattered red ticks, each dragging a whole line (figure s03).

Figure s03 — Top row: a single 128-byte cache line (black rectangle) with 32 red tick marks packed inside it — the coalesced, aligned case, one transaction, 100% efficiency. Bottom row: a cartoon of the strided case — six labelled cache-line rectangles each holding one red tick, with "(showing 6 of 32 lines)" written beside them, standing in for all 32 separate lines. In reality there are 32 such rectangles; only 6 are drawn to fit the page. Because each of the 32 threads drags its own whole line, that is 32 transactions and only 128/4096 = 3.125% efficiency.

Level 4 — Synthesis

Exercise 4.1

You must hide a memory latency of $L = 400$ cycles. The SM needs throughput $T = 1$ instruction per cycle to stay busy, and each warp can issue an instruction only once every 4 cycles on average (the rest of the time it is waiting). How many warps must the SM keep resident? If the SM supports at most 64 warps, is a single SM enough?

Recall Solution

WHAT we do: use the latency-hiding rule and then adjust for the per-warp issue gap. WHY: while one warp waits, others must supply work. To never stall, the pool of warps must be large enough that at every cycle at least one is ready.

Base requirement to hide latency: $W \geq L \cdot T = 400 \times 1 = 400 warp-instructions.$

But each warp issues only every 4 cycles, so a single warp covers 4 of those cycles of work: $W \geq \frac{400}{4} = 100 warps.$

The SM caps at 64 warps, and $64 < 100$ . So one SM is not enough — this is exactly why GPUs use many SMs in parallel rather than one deep pipeline, and why kernels chase high occupancy. See also GPU vs CPU Architecture.

Exercise 4.2

Same launch as Exercise 2.1 (8000 warps total). The GPU has 80 SMs, each running 16 warps concurrently. How many "waves" are needed, and what is the total time if one wave costs $T_{wave}$ ?

Recall Solution

WHAT we do: find how many warps run at once, then divide the total by it and round up. WHY divide: the GPU has a fixed number of warp slots resident at any instant — 80 SMs each holding 16 warps. A "wave" is one full filling of every slot; only that many warps can physically be in flight together, so the total work must be poured through the machine in batches of that size.

Concurrent warps across the whole GPU: $80 \times 16 = 1280 warps at once.$

Waves needed to drain 8000 warps: $⌈ \frac{8000}{1280} ⌉ = ⌈ 6.25 ⌉ = 7 waves.$

WHY round up: after 6 full waves, $6 \times 1280 = 7680$ warps are done, leaving $8000 - 7680 = 320$ warps still unexecuted. Those 320 warps must occupy real slots for a whole extra scheduling pass — the hardware cannot run "0.25 of a wave", it lights up a fresh wave (mostly under-filled) to finish them. Leftover work therefore always forces one more complete wave.

Total time (ignoring overlap between waves): $T_{total} \approx 7 \cdot T_{wave} .$

Level 5 — Mastery

Exercise 5.1

An Ampere-style SM has:

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

Your kernel uses 64 registers per thread, runs in blocks of 256 threads (= 8 warps per block), and each block requests 16384 bytes (16 KB) of shared memory. Find the occupancy: how many warps can actually run, and what fraction of the 64-warp maximum is that?

Recall Solution

WHAT we do: compute the warp limit from each resource — registers, threads, hardware cap, and shared memory — then take the smallest (the binding constraint). WHY: an SM has several finite resource pools, and all of them must fit simultaneously. A warp can only be resident if every pool it draws from still has room; therefore the SM stops adding warps the moment the first pool runs dry. That is why occupancy is a $min$ over independent limits, not a product or a sum.

Register limit. A warp is 32 threads, so 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. Each block needs 16 KB, and the SM has 64 KB, so at most $⌊ 65536/16384 ⌋ = 4$ blocks fit. Each block is 8 warps, so shared memory allows $4 \times 8 = 32$ warps.

The binding constraint is the smallest: $min (32, 32, 64, 32) = 32$ warps.

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

Here three separate limits (registers, threads, shared memory) all pin us at 32 warps. To push occupancy higher you would need to relieve all of the binding ones at once — e.g. cut registers to 32/thread and shared memory to 8 KB/block. This is the classic GPU Occupancy trade-off, tied to Instruction-Level Parallelism.

Exercise 5.2 (Capstone)

Combine everything. A warp runs the branch from Exercise 2.2 (40 cycles, 50/50 split, hot=10 / cold=30). Suppose you sort the data so that a warp is now fully converged onto the cold path. (a) What is the new time for that warp? (b) What speedup did sorting buy versus the diverged 40 cycles?

Recall Solution

WHAT we do: re-evaluate the warp's cost once it is fully converged, then divide the old cost by the new. WHY (a): when all 32 lanes take the same branch, there is no second serialized pass — the warp is at one instruction address the whole time, so its cost is just that single branch's time, not a sum. This is the exact opposite of Exercise 2.2, where two different addresses forced two passes. WHY (b): speedup is defined as old-time over new-time because it measures how many times faster the work now finishes; removing the extra serial pass is precisely what the ratio captures.

(a) Fully converged means all 32 lanes take the same branch, so time is just that one branch: $T_{converged} = max (T) = 30 cycles (all cold).$ No serialization — one pass, all bulbs lit.

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

Sorting removed the second serial pass. The gain looks modest here because hot (10) was cheap; if both branches were equal-cost the diverged case would be $2 \times$ slower and sorting would double throughput. This is why "sort/group by branch outcome" is a top-tier SIMT optimization. See Warp Divergence.

Recall Quick self-check (reveal the answers)

Round threads up to whole warps? ::: Yes — always $⌈ N /32 ⌉$ . Diverged branch cost is sum or max? ::: Sum ( $T_{A} + T_{B}$ ); only converged warps cost $max$ . Worst-case divergence slowdown for a 32-thread warp? ::: $32 \times$ (every thread unique path). Coalescing efficiency for stride = one full cache line? ::: $128/4096 = 3.125%$ . What breaks the ideal 1-transaction coalesced case even when accesses are contiguous? ::: A misaligned base — the 128-byte span straddles two lines, costing 2 transactions (50%). Occupancy from multiple resource limits? ::: The minimum limit (registers, threads, cap, shared memory), not the sum.