Data Parallel Patterns are the recurring algorithmic structures — map, reduce, scan, stencil, gather/scatter — that capture the fundamental ways data-parallel computations are expressed, providing reusable templates that map efficiently to GPUs, SIMD units, and distributed systems while abstracting away hardware-specific details.

Why Patterns Matter

Instead of programming each parallel algorithm from scratch, recognizing which pattern applies allows the programmer to use optimized library implementations (CUB, Thrust, TBB, MapReduce) that embody years of hardware-specific optimization. The pattern provides the structure; the library provides the performance.

Core Patterns

• Map: Apply an independent function to each element. f(x₁), f(x₂), ..., f(xₙ). Each computation is independent → embarrassingly parallel. Examples: pixel-wise image processing, element-wise tensor operations, Monte Carlo sampling. GPU: one thread per element.

• Reduce: Combine all elements into a single value using an associative operator. sum(x₁, x₂, ..., xₙ). Requires O(log N) steps using a parallel tree. Examples: global sum, max, dot product, histogram counting. GPU: tree reduction within blocks, then across blocks.

• Scan (Prefix Sum): Compute running aggregates. [x₁, x₁+x₂, x₁+x₂+x₃, ...]. The "parallel allocation" primitive. Examples: stream compaction, radix sort scatter, CSR construction. GPU: Blelloch work-efficient scan.

• Stencil: Each element is updated based on its neighbors in a regular pattern. output[i] = f(input[i-1], input[i], input[i+1]). Examples: finite difference PDE solvers, image convolution, cellular automata. GPU: shared memory tiling with halo exchange.

• Gather/Scatter: Gather reads from irregular source positions into regular destinations. Scatter writes regular source data to irregular destination positions. Examples: sparse matrix operations, histogram bin accumulation, texture sampling. GPU: atomic operations for scatter conflicts.

• Transpose: Rearrange data layout (e.g., AoS↔SoA, matrix transpose). Converts inefficient access patterns into efficient ones. GPU: shared memory transpose to avoid uncoalesced global memory access.

Composition

Real algorithms combine multiple patterns. Radix sort = map (extract digit) + scan (compute positions) + scatter (redistribute). K-nearest neighbors = map (compute distances) + reduce (find top-K). Recognizing the component patterns is the key to parallelizing complex algorithms.

Embarrassingly Parallel

The special case where the entire computation is a pure map with no inter-element dependencies. Each work unit is completely independent. Examples: ray tracing (independent per pixel), Monte Carlo simulation (independent per sample), parameter sweep. Linear speedup with processor count — the best-case scenario for parallelism.

Data Parallel Patterns are the periodic table of parallel computing — a small set of fundamental elements that combine to form every parallel algorithm, each with known performance characteristics and optimized implementations for every major hardware platform.