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.