GPU computing

Graphics processing units accelerate computations that expose large numbers of relatively simple operations. A typical GPU programming model organizes threads into blocks or workgroups, then organizes those blocks into a grid or dispatch. Hardware executes groups of lanes together, often called warps on NVIDIA hardware, while assigning blocks to streaming multiprocessors or analogous units. A conceptual GPU hierarchy therefore has several levels: an application launches work; blocks share certain resources and synchronization scope; lanes execute instructions; and the machine schedules groups of blocks under resource constraints. The exact limits and scheduling policies are hardware-dependent, so code should query device properties rather than assume every GPU has an identical block size or register allocation.

Suppose a kernel transforms an array of 1,000,000 temperature readings. A block contains 256 threads, each responsible for one or more elements. The grid requires ceil(1,000,000/256)=3,907 blocks if each thread handles exactly one element; the final block includes inactive or bounds-checked lanes. The kernel must verify an element's global index before reading or writing. Omitting the bounds check may produce an out-of-bounds access on the final block. The number of launched threads is not the number of simultaneously resident hardware threads. Blocks are scheduled in waves, and residency depends on registers, shared memory, block size and device limits.

A GPU hides memory latency partly by switching among ready groups of threads. When one warp waits for data, another may issue useful instructions. This requires enough independent work and suitable resources; launching a huge number of threads is not a substitute for good memory access. A kernel that uses very many registers per thread can limit the number of resident warps. A kernel that reserves large shared-memory buffers can restrict block residency. An occupancy calculator estimates the share of a multiprocessor's supported active warps that can fit under these constraints, but high occupancy alone does not guarantee high throughput. Some compute-bound kernels perform best with fewer resident warps and more registers per thread, reducing spills to slow memory.

GPU blocks commonly coordinate only with threads in their own group using a barrier whose scope and semantics are defined by the API. A block barrier does not generally synchronize arbitrary blocks throughout a conventional kernel. Algorithms requiring global barriers may use multiple kernel launches, cooperative execution features where supported, or a different design. Assuming that block zero always runs before block one is unsafe: scheduling order is not a correctness guarantee. A producer block cannot normally write a flag and expect another arbitrary block to observe it safely without an appropriate device-wide protocol.

SIMT execution, single instruction multiple threads, expresses a common instruction stream over multiple lanes that may have different data. It resembles vectorization but also supports per-thread control flow. Divergent branches cause a group to execute distinct paths serially or under execution masks, depending on the hardware and compiler. Consider thirty-two lanes each evaluating whether its measurement exceeds a threshold. If all lanes follow the same branch, execution is regular. If half take an expensive branch and half skip it, the group may execute the branch body while masking inactive lanes, reducing utilization. Rearranging data by common behavior can sometimes improve coherence, but sorting records has a cost and may disrupt other locality advantages.

Device placement and transfer costs must be included in end-to-end performance. If a CPU sends 100 MB to a GPU, launches a 0.5-millisecond kernel and reads 100 MB back, the transfers can dominate the result. Optimizing only the kernel may offer little user-visible benefit. Keeping intermediate arrays on the GPU across several operations can amortize transfer overhead. Unified or managed memory can reduce programming complexity, but migration and page-fault behavior can still affect performance. The application should measure all allocation, transfer, synchronization and kernel phases with clearly described timing boundaries.

Multi-GPU systems add another level of hierarchy. Each GPU has its own memory, and moving data between devices may require a peer-to-peer link or a route through host memory. GPU-aware communication libraries may move data directly among devices when the environment supports it. Algorithms must still establish ownership and synchronization across these memories. Some workloads gain by partitioning independent batches across devices; others require costly cross-device reductions or halo exchanges. The number of GPUs alone says little about speedup without the communication graph and interconnect characteristics.

The practical approach is to map indices explicitly, establish bounds, estimate per-thread resources and explain every synchronization scope. Verify outputs against a simple CPU implementation on small arrays including sizes not divisible by block size. Then profile launch overhead, occupancy, memory traffic and divergence. GPU execution is most effective when the computational structure gives many independent, regular operations enough work to amortize transfers and scheduling.

A kernel is a device-executed function applied across a launch configuration. Writing a correct kernel is not merely translating a CPU loop into GPU syntax. The programmer must determine which thread computes each output, how input data are laid out, whether threads read overlapping locations and which intermediate results need communication. The easiest kernels use a one-to-one mapping between output elements and threads. More advanced kernels use each thread to process several elements, cooperate in shared-memory tiles, or pipeline memory transfers with arithmetic. Every such choice changes register pressure, memory traffic and the availability of independent work.

Consider elementwise affine transformation y_i=a x_i+b. A straightforward kernel obtains i from block and thread indices and writes y_i when i

Kernel launches impose overhead even when each thread does little work. If a device kernel performs ten microseconds of arithmetic but takes a comparable amount of time to enqueue and synchronize, fusing multiple compatible transformations into one kernel can improve throughput. Fusion saves temporary writes and repeated launches, but it may increase register pressure or complicate dependencies. For example, applying normalization followed by an independent nonlinear transform can often be fused. Combining two stages that require a global reduction between them may require separate kernels or a specialized cooperative strategy. Fusion is only correct when intermediate values and ordering constraints are preserved.

Parallel reductions illustrate cooperative kernels. Within a block, threads can load data, compute partial sums and combine them through a tree. Each phase may need a barrier before a thread reads a value produced by another. Across blocks, the program may emit partial sums to a global buffer and launch a second kernel to finish the reduction. Atomics can sometimes combine block results, but contention and nondeterministic floating-point order may make that method inferior. A strong implementation states how it handles non-power-of-two lengths, inactive lanes, overflow and the final partial block.

A GPU kernel is often memory-bound rather than arithmetic-bound. One device thread reading four bytes and writing four bytes for a single addition has only a small number of arithmetic operations per transferred byte. Increasing arithmetic throughput cannot overcome an already saturated memory interface. Reusing loaded tiles, working on several adjacent elements per thread or fusing operations can raise arithmetic intensity. However, transformations may reduce occupancy or increase redundant reads if chosen poorly. Count actual device-memory traffic when possible and use performance counters to test the model.

Kernel correctness includes floating-point behavior. CPUs and GPUs may use different instruction choices, fused multiply-add operations, rounding modes or reduction orders. Two valid implementations can disagree in a small number of least-significant bits without indicating a logical error. Verification should use justified absolute or relative tolerances for approximate floating-point results, while integer indexing and buffer bounds require exact correctness. A kernel that produces a visually plausible image can still be wrong at boundaries or for special values such as infinities and NaNs. Include small adversarial inputs with zeros, negative values, extreme magnitudes and ragged dimensions.

Streams and asynchronous execution can overlap copies and kernels when the device and dependencies permit. A pipeline may transfer batch k+1 while computing batch k and reading back batch k-1. Correctness requires that a kernel not consume data before its transfer finishes and that buffers are not reused while another operation still accesses them. Event dependencies or stream ordering can express those constraints. A timeline with transfer lanes and compute lanes makes overlap and idle gaps visible; measured overlap may be less than theoretical because copy engines, buses and memory controllers are finite resources.

Kernel optimization should proceed incrementally: establish a simple correct reference, profile bottlenecks, change one major mapping or memory strategy, and rerun correctness checks. Hand-tuned low-level tricks are valuable only when they outperform a known baseline on relevant hardware and input sizes. Performance that depends on a hidden warp-size assumption or undefined synchronization is not a reliable optimization.

GPU memory systems have several distinct storage levels. Device-global memory offers large capacity and bandwidth but higher access latency than registers or on-chip shared memory. Registers hold thread-local working values but are a scarce resource that can limit occupancy. Shared memory within a block can enable reuse and communication with controlled synchronization. Constant or read-only caches may accelerate suitable access patterns. The right choice depends on how frequently data are reused and which threads need them. Moving every value into shared memory is not necessarily a win: copying has a cost, and the shared-memory allocation may reduce the number of resident blocks.

Coalescing is a property of how a group of threads accesses memory. If neighboring lanes load neighboring contiguous elements, hardware can often service the accesses with relatively few memory transactions. If neighboring lanes load elements separated by a large stride, the same nominal payload can require many more transactions and waste transferred bytes. An example is a row-major matrix where consecutive threads read the same column from widely separated rows. The pattern has a stride equal to row length, so a transposed thread mapping or tiled approach may improve bandwidth. The details of transaction width, cache lines and alignment are device-specific, so analyze layout and confirm with profiling rather than asserting one constant penalty.

Tiling makes reuse explicit. Suppose multiplying matrices A and B to form C. A naive per-output thread repeatedly loads row elements of A and column elements of B, with reuse depending on cache behavior. A tiled kernel loads submatrices into shared memory, synchronizes threads, multiplies many combinations of the tile elements and accumulates partial outputs. Each loaded value is reused by multiple arithmetic operations. For tile width t, a block computes roughly t cubed multiply-add pairs while loading on the order of two t-squared input values per tile phase. This increases arithmetic per transferred byte, although register and shared-memory limits constrain t. The algorithm must handle partial tiles at matrix edges without reading invalid addresses.

Bank conflicts can arise in shared memory when several lanes address locations mapping to the same storage bank in a way that cannot be serviced efficiently. Padding a two-dimensional tile by one element per row is a classic remedy for certain transpose patterns. Yet this is a hardware and access-pattern issue: padding wastes some shared memory and might be unnecessary on architectures with different broadcast or bank behavior. The best explanation uses a concrete address mapping, identifies conflicting lanes and compares measured transactions or latency after the layout change.

Memory alignment and vector loads are further constraints. A compiler may generate efficient vectorized memory operations when pointers are aligned and sufficiently many adjacent elements are available. Misaligned boundaries may require separate handling. Using wider loads without checking length can overrun the final array. A good kernel states the alignment preconditions and includes a correct fallback path for ragged dimensions. For many real workloads, extra bounds checks cost far less than the engineering risk of assuming every input size is a multiple of a convenient block width.

Host-device transfers are part of the data-movement budget. Pinned host buffers and asynchronous copies can improve some pipelines, but pinned memory consumes system resources and should not be allocated without limits. Keeping data resident across several GPU stages often saves more than any individual coalescing trick because it eliminates round trips. A useful transfer model sums bytes across every boundary: disk to host, host to device, device memory to on-chip storage, and device to host. The slowest or most repeated boundary can dominate total latency even when the core arithmetic kernel runs quickly.

Irregular workloads resist perfect coalescing. Graph algorithms use neighbor lists with data-dependent addresses, and sparse matrices may have varying row lengths. Reordering vertices or grouping similar-degree rows can improve locality and load balance, but reordering incurs preprocessing cost and may complicate mapping results back to original identifiers. A sensible experiment compares end-to-end time across repeated iterations, accounting for amortization. If one expensive preprocessing pass saves a small amount on each of thousands of iterations, the investment may pay off; for a one-off query it may not.

The key design skill is to trace bytes, not source-code variables. Estimate compulsory data movement, identify reuse opportunities, inspect access regularity, and measure actual memory throughput. A kernel that executes many arithmetic operations can still be memory-bound; a kernel with simple arithmetic can be compute-bound when its data are repeatedly reused from registers. Only measurement plus a believable traffic model resolves the ambiguity.

Divergence occurs when threads that share an execution group follow different control-flow paths. In SIMT architectures, the hardware may execute paths under masks, so inactive lanes occupy execution resources without contributing useful work. The performance effect depends on path lengths, hardware reconvergence, compiler transformations and whether divergent groups are common. Divergence does not automatically make an algorithm incorrect, and avoiding every conditional statement is not always worthwhile. A uniform branch that every lane takes identically typically causes no lane-level divergence penalty in that group.

Consider a GPU image kernel that performs a cheap transform on ordinary pixels but runs a costly outlier reconstruction on extreme pixels. If outliers are randomly distributed, many execution groups contain both ordinary and extreme pixels. Those groups may execute the costly path with only a few active lanes, wasting lane capacity. If outliers cluster spatially, groups aligned with the clusters may execute mostly uniform branches, reducing the effect. Sorting pixels by category could make execution more coherent, but the sorting pass and reordering memory accesses may cost more than the branch penalty. The optimal approach depends on how often the workload is repeated and whether categorized indices are reused.

A common strategy is compaction: first generate a flag for items needing expensive work, then produce a compact list of their indices using a prefix sum, and launch a second kernel on only those items. The initial pass and scan impose extra memory traffic and launches. Compaction pays off when the expensive branch is sufficiently costly and sufficiently sparse. It can also enable separate kernels with different resource requirements, potentially improving occupancy. But it complicates output ordering and requires checking that the compact list is correct. A debugging test should compare the reconstructed output to a straightforward serial reference for every original index.

Divergence also arises from early exits and variable-length loops. In graph traversal, one thread may scan a vertex with two neighbors while another scans a vertex with thousands. Lanes assigned to short lists finish quickly but may remain inactive while the long list is processed. Load-balancing strategies can assign high-degree vertices to cooperative groups and low-degree vertices to individual threads. That mapping requires classification and potentially additional synchronization. Optimizing only divergence without considering memory locality can hurt performance because adjacency lists may no longer be processed in cache-friendly order.

Branch elimination is not always an optimization. Replacing a conditional with arithmetic selection might execute both sides of an expensive computation, increasing total work. It can also change numerical behavior, for example by evaluating a division that the original branch would have skipped when the denominator was zero. A predicate-based operation must preserve the domain and exception behavior of the original program. Measure whether the compiler already uses predication, and compare actual instruction counts and elapsed time rather than relying on source-code appearance.

Warp-level primitives can accelerate operations such as reductions and shuffles, but their semantics depend on the set of participating lanes. Using them under divergent control flow requires that participation masks and synchronization assumptions are valid. If an algorithm assumes all lanes are active and some exit early, results can be undefined or incorrect. An apparently successful run with a full block may conceal the bug that appears only in the final partial block. Testing ragged sizes is therefore central to validating divergence-sensitive kernels.

Profilers can report metrics such as eligible warps, branch efficiency, active lanes and instruction issue utilization. Each is a partial signal. High branch efficiency with terrible performance might mean memory accesses are scattered or the kernel performs unnecessary operations. Low branch efficiency might be acceptable if divergent branches are rare and arithmetic intensity is high. Evaluate overall throughput and isolate the dominant cause before changing code.

Divergence management is ultimately a problem of matching heterogeneous work to execution resources. Keep similar-length work together when possible, use separate kernels for genuinely different computational paths when amortization supports it, and preserve correctness under all participation patterns. A consistent test matrix includes uniform inputs, mixed inputs, all-exception inputs, and a final incomplete group. This gives far stronger evidence than an attractive benchmark on one regular dataset.