GPUs and SIMD Execution

SIMD (Single Instruction, Multiple Data) is an architectural pattern in which one instruction specifies an operation — add, multiply, compare — that is applied simultaneously to multiple data elements packed into a wide register. A CPU vector unit with 256-bit registers holding eight 32-bit floats executes `vaddps` once and produces eight sums in one instruction issue. The parallelism is explicit at the instruction-set level: the compiler or programmer chooses the vector width, and the hardware replicates one ALU control signal across many datapaths.

SIMT (Single Instruction, Multiple Threads) is the GPU's variant of the same underlying idea, but expressed at the thread level rather than the register level. A programmer writes ordinary-looking scalar code — one thread computes one output pixel, one thread updates one array element — and the hardware groups threads into fixed-size groups called warps (NVIDIA terminology, 32 threads) or wavefronts (AMD, 64 threads). All threads in a warp share one instruction fetch/decode unit and execute the same instruction each cycle, but each thread carries its own registers and its own program counter conceptually, so control flow can diverge — handled by predication/masking rather than by refusing to compile. This is the crucial difference from pure SIMD: SIMT preserves a scalar programming model while the hardware underneath still executes in a SIMD-like lockstep across lanes. The other pillar of GPU throughput is latency hiding through massive multithreading, building directly on the register-file replication ideas from Hardware Multithreading and Simultaneous Multithreading. A GPU streaming multiprocessor (SM) holds the architectural state — registers, warp ID, program counter — for dozens of warps simultaneously (commonly 32–64 resident warps, i.e. 1024–2048 threads per SM). When one warp stalls on a memory load, the warp scheduler switches to another ready warp with zero-cycle overhead, because that warp's registers are already resident in a partition of a very large register file. This differs fundamentally from ILP techniques in Instruction-Level Parallelism and Dependences, which try to extract parallelism within one instruction stream via reordering and speculation; SIMT/GPU throughput comes from parallelism across thousands of independent instruction streams (threads), each individually simple and in-order.

Step 1 — Kernel launch and the thread hierarchy. A programmer writes a kernel: a function executed once per logical thread. Threads are organized into a hierarchy — threads within a block (CUDA) or workgroup (OpenCL), blocks within a grid. The hardware's job is to map this hierarchy onto physical lanes.

Step 2 — Warp formation. The runtime partitions each thread block into fixed-size warps (32 consecutive thread IDs on NVIDIA hardware). Warp formation is purely index-based: thread IDs 0–31 form warp 0, 32–63 form warp 1, and so on. This is a static, cheap operation — no dynamic load balancing at this stage.

Step 3 — Instruction issue across a warp. Each cycle (or over a few cycles depending on the SM's SIMD width relative to warp size), the warp scheduler picks one ready warp and issues its next instruction to all 32 lanes simultaneously. Each lane executes the instruction on its own registers and its own slice of memory addresses. This is functionally SIMD execution, but the "vector width" (32) is fixed by hardware and hidden behind the scalar-thread abstraction.

Step 4 — Divergence handling via masking. When threads in a warp take different branches (e.g., `if (x[i] > 0)`), the hardware cannot execute two instruction streams at once. Instead it uses an active mask: it executes the "taken" path with the mask disabling threads that shouldn't participate, then executes the "not-taken" path with the complementary mask, then reconverges. This means divergent branches cost the sum of both paths' latencies, not the max — the central throughput penalty of SIMT.

Step 5 — Memory access coalescing. When a warp executes a load/store, the memory system checks whether the 32 per-thread addresses fall into a small number of contiguous cache-line-sized segments. If thread `i` accesses address `base + i*4` (i.e., consecutive floats), the 32 requests coalesce into one or two wide memory transactions. If addresses are scattered (e.g., a strided or random-access pattern), the hardware must issue up to 32 separate transactions, collapsing throughput by an order of magnitude.

Step 6 — Latency hiding via warp scheduling. While a warp waits on a long-latency memory operation, the scheduler issues instructions from other resident warps. Because each SM holds many warps' worth of register state simultaneously (no swapping, no spilling — this is the direct generalization of the fine-grained/simultaneous multithreading register-duplication idea), the scheduler can fully hide memory latency as long as enough independent warps are resident and ready. ```pseudocode // ===== Software view: one thread per output element ===== kernel VectorAdd(A[], B[], C[], N): i = blockIdx * blockDim + threadIdx // global thread id if i < N: C[i] = A[i] + B[i] // ===== Hardware view: SIMT execution of one warp ===== // WARP_SIZE = 32 (fixed by hardware) function ExecuteWarp(warp, PC): activeMask = warp.mask // bit set = thread participates instr = Fetch(PC) if instr is BRANCH(cond): // evaluate cond per-lane -> two disjoint sub-masks takenMask = activeMask AND EvalPerLane(cond, true) notTakenMask = activeMask AND EvalPerLane(cond, false) if takenMask != 0: Push(divergenceStack, (reconvergePC, notTakenMask)) ExecutePath(takenPC, takenMask) if notTakenMask != 0 and takenMask == 0: ExecutePath(notTakenPC, notTakenMask) // reconvergence happens when execution reaches reconvergePC else: for lane in 0..31: if activeMask has bit(lane): RegisterFile[lane].apply(instr) // one ALU op per active lane AdvancePC(warp) // ===== Warp scheduler: picks a ready warp each cycle ===== function SchedulerCycle(residentWarps): ready = { w in residentWarps : w.notStalled() } if ready is empty: return IDLE // all warps waiting on memory/sync w = SelectByPolicy(ready) // e.g., greedy-then-oldest, round-robin IssueNextInstruction(w) ``` The `SelectByPolicy` step is where real hardware differs across vendors and generations — common policies include round-robin and "greedy-then-oldest," chosen to balance fairness against exploiting instruction-cache/data locality across consecutive issues from the same warp.

Throughput model. Let a GPU have $S$ streaming multiprocessors, each capable of issuing one warp instruction (32 lanes) per cycle at clock rate $f$. Peak throughput in operations per second is

This is a direct multiplicative gain over a scalar core: one instruction fetch/decode amortizes over 32 ALU operations, so the control overhead per useful operation drops by a factor of 32 relative to a scalar pipeline. This is the same amortization principle as SIMD vector units in CPUs, just realized at thread-group granularity.

Why masking is correct. The key invariant is: at every point in the divergence-and-reconvergence protocol, exactly one control-flow path is active per lane, and every lane executes precisely the sequence of instructions that its own scalar program order would dictate. Formally, if thread $t$'s serial execution trace is the sequence of instructions $I_1^t, I_2^t, \dots$, SIMT execution guarantees each $I_k^t$ is executed with thread $t$'s correct register state, in order, regardless of what other lanes in the warp are doing. The mask mechanism enforces this by having a lane execute an instruction only if its mask bit is set; masked-off lanes neither read nor write architectural state (registers, memory) for that instruction. Because divergent paths are executed serially (one full pass per distinct control path, not interleaved instruction-by-instruction), there is no possibility of one lane's speculative execution corrupting another's state — this is what makes SIMT semantically equivalent to independent scalar threads, at a real cost in time (the union of path lengths) but zero cost in correctness.

Cost of divergence. If a warp's 32 threads split into $k$ mutually exclusive groups with path lengths $\ell_1, \ldots, \ell_k$ (in instructions), the warp's total issue-cycle cost is $\sum_{j=1}^k \ell_j$, versus $\max_j \ell_j$ in an idealized world with independent per-thread control. In the worst case (all 32 threads on distinct paths, or two paths of nearly equal weight), throughput on that warp degrades toward $1/32$ of peak — the single biggest correctness-preserving inefficiency in the model.

Latency hiding — why it works and its limit. Suppose a memory operation has latency $L$ cycles and the SM issues one instruction per cycle when at least one warp is ready. If $W$ warps are resident and each warp's compute-to-memory ratio leaves it needing to wait $L$ cycles after issuing a memory request, the scheduler can fully hide that latency as long as

Occupancy — the fraction of the SM's maximum warp slots that are actually resident, limited by register file size, shared memory, and thread-block size — determines whether $W$ is large enough. This is the GPU generalization of the same latency-hiding argument used for fine-grained multithreading in Hardware Multithreading and Simultaneous Multithreading: more independent contexts convert stall cycles into useful issue cycles, up to the point where the hardware runs out of resident warps or the memory system itself saturates.

Space complexity. The register file must hold live state for every resident warp simultaneously — no spill-to-memory context switch exists in the fast path. For $W$ resident warps of 32 threads each using $r$ registers per thread, the SM needs $32 \cdot W \cdot r$ physical registers. This is why register usage per thread directly limits occupancy: a kernel using more registers per thread supports fewer resident warps, at a fixed register file size, trading per-thread performance against latency-hiding capacity — a genuine and unavoidable tradeoff, not a bug.

Consider a warp of 8 threads (shrunk from 32 for readability) executing: ``` i = threadIdx if (x[i] > 0): y[i] = sqrt(x[i]) // path A, 4 cycles else: y[i] = 0 // path B, 1 cycle z[i] = y[i] + 1 // reconverged instruction ``` Input data: `x = [4, -1, 9, -3, 0, 16, -2, 1]`

Execution trace:

Total: 6 cycles for the warp. An idealized machine with independent per-thread control (impossible in real SIMT hardware, but useful as a bound) would need only $\max(4,1) + 1 = 5$ cycles if the two groups could execute concurrently on separate hardware. The extra cycle is exactly the divergence penalty: $4 + 1$ (serial execution of both paths) instead of $\max(4,1)$. Now compare to the non-divergent case where all 8 threads have `x[i] > 0`: all take path A, mask is always full, and the warp finishes in $4 + 1 = 5$ cycles with zero wasted lane-cycles. The divergent case wastes $4 \times 4$ (path A idles 4 lanes for 4 cycles) $+ 1 \times 4$ (path B idles 4 lanes for 1 cycle) $= 20$ lane-cycles of masked-off, non-productive slots out of $8 \times 6 = 48$ total lane-cycles issued — a 42% utilization loss purely from this one branch, even though the final result is identical and correct in both cases.

GPUs evolved from fixed-function graphics pipelines into general-purpose SIMT parallel processors as vector-array-style supercomputer ideas were re-adapted to commodity silicon. The intellectual lineage runs from early vector supercomputers, whose designers first grappled with amortizing control overhead over wide data operations, through to the CUDA-era architects who formalized SIMT as a distinct execution model bridging vector hardware and scalar programmability.

Every major deep learning framework — training transformers, convolutional networks, diffusion models — depends on SIMT execution to turn matrix multiplications into thousands of parallel warp-scheduled threads; tensor cores extend the same lockstep idea to small fixed-size matrix tiles. Scientific computing (fluid dynamics, molecular dynamics, weather simulation) uses CUDA/OpenCL/SYCL kernels structured explicitly around avoiding divergence and maximizing coalesced access. Real-time graphics rendering, the GPU's original domain, still relies on SIMT to shade millions of pixels or vertices with identical shader programs per frame. Cryptocurrency mining, video encoding/decoding, and databases with GPU-accelerated joins and aggregations all exploit the same warp/lane model. Understanding this execution model is also the prerequisite for reasoning about whether a given kernel is arithmetic-bound or bandwidth-bound — the question answered systematically by The Roofline Model, and for understanding how GPU cores relate architecturally to the multithreaded CPU cores discussed in Hardware Multithreading and Simultaneous Multithreading.

Ask the tutor: How does warp scheduling policy (e.g., round-robin vs. greedy-then-oldest) change latency-hiding behavior under different occupancy levels?