parallel prefix sum scan

**Parallel Prefix Sum (Scan)** is **a fundamental parallel primitive that computes all prefix sums (running totals) of an array in O(n/P + log n) parallel time, transforming an apparently sequential computation into a highly parallel one** — scan is arguably the most important building block in parallel algorithms, appearing in sorting, stream compaction, histogram computation, and memory allocation. **Scan Definitions:** - **Exclusive Scan**: output[i] = sum(input[0..i-1]), with output[0] = identity element (0 for addition) — the output at position i excludes the input at position i - **Inclusive Scan**: output[i] = sum(input[0..i]), including the input at position i — equivalent to exclusive scan shifted left by one position with the total sum appended - **Generalization**: scan works with any associative binary operator (addition, multiplication, max, min, bitwise OR/AND) — the operator doesn't need to be commutative, just associative - **Sequential Complexity**: O(n) trivially computed with a single loop — the challenge is computing it in O(log n) parallel steps while keeping total work close to O(n) **Hillis-Steele Algorithm (Inclusive Scan):** - **Algorithm**: in step d (d = 0, 1, ..., log₂(n)-1), each element i computes x[i] = x[i] + x[i - 2^d] if i ≥ 2^d — after log₂(n) steps, all prefix sums are computed - **Work**: O(n log n) total operations — not work-efficient (performs more operations than sequential O(n) scan) - **Span**: O(log n) parallel steps — good for hardware implementations where excess work doesn't matter (e.g., fixed-function circuits) - **GPU Implementation**: simple to implement with alternating buffers — each step requires a full array pass, making it straightforward but wasteful for large arrays **Blelloch Algorithm (Work-Efficient Scan):** - **Up-Sweep (Reduce)**: builds a binary tree of partial sums bottom-up in log₂(n) steps — step d computes x[k×2^(d+1) - 1] += x[k×2^(d+1) - 2^d - 1] for all valid k - **Down-Sweep (Distribute)**: traverses the tree top-down in log₂(n) steps — replaces each node with the prefix sum up to that point using saved intermediate values - **Work**: O(n) total operations — matches sequential scan, making it work-efficient - **Span**: O(log n) parallel steps — same depth as Hillis-Steele but with O(n) work instead of O(n log n) **GPU Implementation (CUDA):** - **Block-Level Scan**: each thread block scans a tile of data (typically 1024-2048 elements) in shared memory using Blelloch's algorithm — shared memory enables fast intra-block communication - **Block-Level Reduction**: the last element of each block's scan (the block total) is written to an auxiliary array — this array is itself scanned to compute inter-block offsets - **Block-Level Update**: each block adds its inter-block offset to all elements — this three-phase approach (scan, scan of block sums, update) achieves O(n/P + log n) time - **Performance**: CUB and Thrust library implementations achieve 80-90% of peak memory bandwidth on modern GPUs — for 100M elements, scan completes in <1 ms on an A100 **Scan Applications:** - **Stream Compaction**: given a predicate, pack matching elements into a contiguous array — compute a scan of the predicate flags, use scan results as scatter indices - **Radix Sort**: each pass of radix sort uses scan to compute output positions — scan of per-digit histograms determines where each element should be placed - **Sparse Matrix Operations**: scan converts CSR (Compressed Sparse Row) row pointer arrays to/from per-element row indices — enables efficient parallel SpMV (Sparse Matrix-Vector multiply) - **Memory Allocation**: parallel dynamic memory allocation uses scan to compute per-thread allocation offsets — each thread declares its allocation size, scan produces non-overlapping offsets - **Run-Length Encoding**: scan of segment flags computes output positions for compressed representation — enables parallel compression of repetitive data **Multi-GPU and Distributed Scan:** - **Hierarchical Approach**: each GPU scans its local partition, exchanges partition totals, scans the totals, and adds offsets to local results — two-phase approach with one inter-GPU communication step - **Communication Cost**: only P values (one per GPU) are exchanged — for thousands of GPUs scanning billions of elements, communication overhead is negligible - **MPI_Scan/MPI_Exscan**: MPI provides built-in prefix scan operations — each process receives the scan of all preceding processes' contributions **Parallel prefix sum demonstrates a profound principle in parallel algorithm design — transforming sequential dependencies into tree-structured computations that expose logarithmic parallelism, enabling what appears to be an inherently sequential operation to execute with near-linear speedup across thousands of processors.**