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.