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.