Parallel Prefix Sum (Scan) is the fundamental parallel algorithm that computes all prefix sums of an input array — where element i of the output is the sum (or other associative operation) of all input elements from 0 to i — serving as a building block for dozens of parallel algorithms including stream compaction, radix sort, histogram, sparse matrix operations, and dynamic work allocation, making it one of the most important primitives in parallel computing.

Definition

• Input: [a₀, a₁, a₂, a₃, a₄, a₅, a₆, a₇]
• Inclusive scan (prefix sum): [a₀, a₀+a₁, a₀+a₁+a₂, ..., a₀+...+a₇]
• Exclusive scan: [0, a₀, a₀+a₁, a₀+a₁+a₂, ..., a₀+...+a₆]
• Works with any associative binary operator (sum, max, min, OR, AND, etc.).

Why Scan Is Nontrivial in Parallel

• Sequential: O(n) — trivial running sum.
• Parallel: Each output depends on ALL previous elements → inherently sequential dependency.
• Solution: Clever tree-based algorithms that break the dependency chain.

Blelloch Scan (Work-Efficient)

1. Up-sweep (Reduce): Build partial sums in a binary tree — O(n) work, O(log n) steps. 2. Down-sweep (Distribute): Propagate partial sums back down the tree — O(n) work, O(log n) steps. 3. Total: O(n) work, O(log n) span → work-efficient.

Up-sweep Example (n=8):

Level 0: [1, 2, 3, 4, 5, 6, 7, 8]
Level 1: [1, 3, 3, 7, 5, 11, 7, 15]
Level 2: [1, 3, 3, 10, 5, 11, 7, 26]
Level 3: [1, 3, 3, 10, 5, 11, 7, 36]  ← total sum at root

Down-sweep (propagation back to compute prefix sums):

Set root = 0, then propagate:
→ final: [0, 1, 3, 6, 10, 15, 21, 28]  ← exclusive scan

GPU Implementation (CUDA)

• For large arrays: Block-level scan + block sums scan + add block sums.
• CUB library provides optimized DeviceScan::InclusiveSum — production-ready.

Complexity Comparison

Applications of Parallel Scan

1. Stream compaction: Filter elements → scan to compute output positions → scatter. 2. Radix sort: Scan per-digit histograms to compute scatter positions. 3. Sparse matrix operations: Scan to compute row pointers for CSR format. 4. Dynamic allocation: Each thread requests N items → scan gives each thread its offset. 5. Polynomial evaluation: Parallel Horner's method via scan.

Parallel prefix sum is the "Hello World" of parallel algorithm design — its elegant tree-based structure transforms an apparently sequential computation into an efficient parallel one, and its role as a universal building block means that an efficient scan implementation directly accelerates dozens of higher-level parallel algorithms.