Parallel Prefix Sum Scan

Parallel Prefix Sum (Scan) is a fundamental parallel primitive that computes all partial reductions of an input array — transforming [a₀, a₁, a₂, ...] into [a₀, a₀⊕a₁, a₀⊕a₁⊕a₂, ...] for any associative operator ⊕ — serving as a building block for stream compaction, radix sort, sparse matrix operations, and dozens of other parallel algorithms.

Scan Variants:
- Exclusive Scan: output[i] = sum of elements [0, i) — output[0] = identity element; useful for computing output positions (e.g., scatter addresses) where each element doesn't include itself
- Inclusive Scan: output[i] = sum of elements [0, i] — output[0] = input[0]; useful when each element should include its own contribution (e.g., running totals)
- Segmented Scan: scan restarts at segment boundaries defined by a flag array — enables independent prefix sums on variable-length segments packed in a single array (used in sparse matrix operations)
- Generalized Scan: works with any associative binary operator (addition, multiplication, max, min, boolean OR/AND) — not restricted to arithmetic sum

Algorithms:
- Hillis-Steele (Inclusive): O(N log N) work, O(log N) steps — each element adds the value from 2^d positions left at step d; simple but work-inefficient (2× more operations than sequential)
- Blelloch (Work-Efficient): O(N) work, O(log N) steps — two phases: up-sweep (reduce) builds partial sums in tree, down-sweep distributes prefix sums; matches sequential work complexity
- Hybrid GPU Scan: partition array into tiles, scan each tile in shared memory using work-efficient algorithm, collect tile sums into a small array, scan tile sums, add tile prefix to each tile — three-phase approach handles arrays of arbitrary size

GPU Implementation:
- Warp-Level Scan: __shfl_up_sync enables scan within a warp without shared memory — each thread reads from the thread d positions below and adds, doubling d each step for O(log 32) = 5 steps
- Block-Level Scan: shared memory scan across all threads in a block — warp-level scans of each warp, followed by scan of per-warp totals, then add warp prefix to each lane
- Multi-Block Scan: global memory used to communicate between blocks — either atomic-based decoupled lookback (fastest) or three-kernel approach (tile scan → prefix scan → propagate)
- Decoupled Lookback: each block publishes its local sum incrementally and looks back at predecessor blocks — achieves single-pass scan without coordination kernel, optimal for modern GPUs

Parallel scan is often called the 'parallel computing equivalent of the for-loop' — mastering scan-based algorithm design is essential for efficient GPU programming because it transforms inherently sequential accumulation patterns into massively parallel operations.