parallel prefix sum scan

**Parallel Prefix Sum (Scan) Algorithms** — The parallel prefix sum, or scan, computes all partial reductions of a sequence in parallel, serving as a fundamental building block for countless parallel algorithms including stream compaction, radix sort, and histogram computation. **Scan Operation Definitions** — Two variants define the output semantics: - **Inclusive Scan** — element i of the output contains the reduction of all input elements from index 0 through i, so the last output element equals the total reduction - **Exclusive Scan** — element i of the output contains the reduction of all input elements from index 0 through i-1, with the first output element being the identity value - **Generalized Scan** — the operation works with any associative binary operator, not just addition, enabling parallel prefix computations for multiplication, maximum, logical operations, and custom reductions - **Segmented Scan** — extends the scan operation to work on segments of the input independently, enabling parallel processing of variable-length sequences within a single array **Hillis-Steele Algorithm** — A simple but work-inefficient approach: - **Algorithm Structure** — in each of log(n) steps, every element adds the value from a position 2^d elements to its left, where d is the current step number - **Step Complexity** — completes in O(log n) parallel steps, achieving optimal span for the scan operation - **Work Complexity** — performs O(n log n) total operations, which is not work-efficient compared to the O(n) sequential algorithm - **Implementation Simplicity** — the regular access pattern and absence of a down-sweep phase make this algorithm straightforward to implement on SIMD and GPU architectures **Blelloch Work-Efficient Algorithm** — A two-phase approach achieving optimal work: - **Up-Sweep (Reduce) Phase** — builds a balanced binary tree of partial sums from the leaves to the root in log(n) steps, computing the total reduction at the root - **Down-Sweep Phase** — traverses the tree from root to leaves, distributing partial prefix sums using the identity element at the root and combining with saved values at each level - **Work Efficiency** — performs O(n) total operations across both phases, matching the sequential algorithm's work while achieving O(log n) parallel depth - **Bank Conflict Avoidance** — GPU implementations add padding to shared memory arrays to prevent bank conflicts that would serialize memory accesses within a warp **Large-Scale Scan Implementation** — Handling arrays larger than a single thread block: - **Block-Level Scan** — each thread block performs a local scan on its portion of the input, producing per-block partial results and block-level totals - **Block Total Scan** — the array of block totals is itself scanned, either recursively or using a single block if the number of blocks is small enough - **Final Adjustment** — each block adds its corresponding scanned block total to all its local results, producing the globally correct prefix sum - **Decoupled Lookback** — modern GPU implementations use a decoupled lookback strategy where blocks publish partial results and propagate prefix sums through a chain of lookback operations, avoiding the multi-pass overhead **Parallel prefix sum is arguably the most important primitive in parallel algorithm design, enabling efficient parallelization of problems that appear inherently sequential by transforming them into scan-based formulations.**