parallel prefix sum
**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)**
| Phase | Threads Used | Memory Pattern | Steps |
|-------|-------------|---------------|-------|
| Up-sweep | n/2 → n/4 → ... → 1 | Strided access | log₂(n) |
| Down-sweep | 1 → 2 → ... → n/2 | Strided access | log₂(n) |
| Total | — | Shared memory | 2·log₂(n) |
- For large arrays: Block-level scan + block sums scan + add block sums.
- CUB library provides optimized `DeviceScan::InclusiveSum` — production-ready.
**Complexity Comparison**
| Algorithm | Work | Span (Parallel Steps) |
|-----------|------|-----------------------|
| Sequential | O(n) | O(n) |
| Hillis-Steele (naive parallel) | O(n log n) | O(log n) |
| Blelloch (work-efficient) | O(n) | O(log n) |
**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.