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