data parallel patterns
**Data Parallel Patterns** are the **fundamental computational building blocks — map, reduce, scan, gather, scatter, stencil, and histogram — that express common parallel operations on collections of data**, providing composable, portable, and optimizable primitives that underpin virtually all parallel applications from scientific computing to machine learning.
Rather than reasoning about individual threads and synchronization, data parallel patterns express operations on entire arrays or collections. The runtime or compiler maps these high-level patterns onto the hardware's parallel resources, enabling both programmer productivity and performance portability.
**Core Patterns**:
| Pattern | Operation | Complexity | Example |
|---------|----------|-----------|----------|
| **Map** | Apply f(x) to each element independently | O(n/p) | Vector scaling, activation function |
| **Reduce** | Combine all elements with associative op | O(n/p + log p) | Sum, max, dot product |
| **Scan (prefix sum)** | Cumulative reduction producing array | O(n/p + log p) | Running total, radix sort |
| **Gather** | Read from scattered source locations | O(n/p) | Sparse matrix access |
| **Scatter** | Write to scattered destination locations | O(n/p) | Histogram, sparse update |
| **Stencil** | Compute from fixed neighborhood | O(n/p) | Convolution, PDE solver |
| **Sort** | Order elements by key | O(n log n / p) | Database operations, rendering |
**Map**: The most embarrassingly parallel pattern — each output element depends only on the corresponding input element(s). GPU implementations achieve near-peak bandwidth because there are no inter-thread dependencies. Fusion of multiple maps (kernel fusion) eliminates intermediate memory traffic: instead of writing map1 results to memory and reading for map2, fuse both into a single kernel that keeps intermediate values in registers.
**Reduce**: Tree-based parallel reduction: each step combines pairs of values, requiring log2(n) steps for n elements. GPU implementation: each warp performs warp-level reduction using shuffle instructions (no shared memory needed), then block-level reduction in shared memory, then grid-level reduction via atomic operations or multi-kernel launch. CUB and Thrust libraries provide optimized implementations achieving >95% of peak bandwidth.
**Scan (Prefix Sum)**: Deceptively powerful — scan enables parallel implementation of algorithms that appear inherently sequential. Applications: **radix sort** (scan to compute scatter offsets), **stream compaction** (scan to generate output indices for selected elements), **sparse matrix operations** (segmented scan for per-row/per-column operations), and **parallel allocation** (scan to assign dynamic buffer positions). Blelloch's work-efficient scan requires 2n operations and log(n) steps.
**Stencil**: Each output element computed from a fixed geometric neighborhood of input elements. Critical for scientific computing (finite differences, CFD, molecular dynamics) and deep learning (convolution). Optimization: load shared memory tiles that include halo regions (ghost zones), compute from shared memory, write results to global memory. Tiling reduces global memory traffic by the ratio of compute-to-halo size.
**Composability**: Complex algorithms are composed from primitive patterns: sorting = scan + scatter; sparse matrix-vector multiply = segmented reduce; histogram = scatter with atomic addition; radix sort = repeated scan + scatter per digit. Libraries like CUB, Thrust, and Kokkos provide optimized pattern implementations for multiple backends.
**Data parallel patterns are the vocabulary of parallel programming — they replace low-level thread management with high-level operations on data, enabling programmers to express parallelism naturally while giving runtime systems the freedom to optimize execution for the target hardware.**