data parallel pattern

**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.