parallel prefix scan
**Parallel Prefix Scan (Parallel Scan)** is a **fundamental parallel algorithm that computes prefix operations on an array** — where each output element is the cumulative operation (sum, max, AND, etc.) of all preceding elements, achievable in O(log N) parallel steps.
**Definition**
- **Inclusive Scan**: $out[i] = in[0] \ \oplus\ in[1] \ \oplus\ ... \ \oplus\ in[i]$
- **Exclusive Scan**: $out[i] = in[0] \ \oplus\ in[1] \ \oplus\ ... \ \oplus\ in[i-1]$ (excludes element i)
- Operation $\oplus$: Addition, multiplication, max, min, XOR, AND, OR.
**Sequential vs. Parallel**
- Sequential: O(N) operations, inherently serial — each step depends on previous.
- Parallel (work-efficient): O(N) work, O(log N) depth — runs in log₂(N) parallel steps.
**Blelloch Two-Phase Algorithm**
**Up-sweep (Reduce) phase**:
- Build reduction tree: N/2, N/4, N/8 ... 1 parallel additions.
- Depth: log₂(N) steps, total work: N-1 operations.
**Down-sweep phase**:
- Traverse back down the tree inserting prefix values.
- Depth: log₂(N) steps, total work: N-1 operations.
**GPU Implementation (CUDA)**
- Shared memory scan within a block: 1024 elements per block.
- Multi-block scan: Scan within blocks → scan partial sums → add back.
- Warp-level scan: `__shfl_up_sync` — fastest, uses warp shuffle.
**Applications**
- **Memory allocation**: Compute offsets for variable-length structures.
- **Stream compaction**: Remove elements from array (filter) — output addresses from scan.
- **Radix sort**: Prefix scan on histogram bins for scatter step.
- **Sparse matrix computation**: Row offset computation in CSR format.
- **Graph BFS**: Frontier expansion — scan for output positions.
The parallel prefix scan is **one of the most versatile parallel primitives** — it appears as a subroutine in radix sort, compaction, and BFS, and mastering it is essential for efficient GPU programming.