parallel

**Parallel Scan Prefix Sum Algorithm** is **a technique computing for each position the cumulative result of an associative operation (like addition) from element 0 to current position, executed efficiently across parallel processors** — fundamental building block for many parallel algorithms including sorting, compaction, and stream processing. Parallel scan enables data-dependent computations without explicit synchronization. **Inclusive and Exclusive Scan** where inclusive scan (iota) returns the cumulative result including current element, exclusive scan (prefix) returns cumulative without current element. Both forms are equivalent—exclusive scan of array 'a' equals inclusive scan of prepended zero, or shift inclusive scan left and append identity element. **Kogge-Stone Algorithm** uses parallel-prefix adder structure with O(log N) levels: level i adds elements distance 2^(i-1) apart. Thread k at level i computes result using values from thread (k - 2^(i-1)). All threads proceed synchronously, requiring shared memory on GPU or MPI synchronization on CPU clusters. Work complexity is O(N log N)—more work than sequential but enables efficient parallelization. **Blelloch Work-Efficient Algorithm** reduces work to O(N) through two phases: up-sweep phase (parallel reduction) combines pairs at increasing distances, down-sweep phase distributes results from top to leaves, restoring full prefix information. Up-sweep: level 0 combines (0,1), (2,3), etc., level 1 combines (0,2), (4,6), level log N combines (0, N/2). Down-sweep reverses this process, distributing accumulated values. **Segmented Scan** handles multiple independent scans within single array, useful for batch processing or hierarchical computations. Flags mark segment boundaries; scan operators need conditional logic (e.g., "(a, b) where flag determines whether to combine or reset"). **GPU Implementation** uses block-level shared memory for sub-block scans, inter-block synchronization for combining block results, and multiple kernel launches for hierarchical scans. NVIDIA provides __shfl_scan_inclusive/exclusive intrinsics for warp-level operations, essential for first stage. **Applications in Sorting** (prefix sums determine output positions), stream compaction (filtering elements), load balancing (scan determines work distribution), and dynamic programming (building up solutions from previous results). **Efficient parallel scan implementation requires understanding algorithm depth for latency hiding and work efficiency to minimize total computation** versus sequential baseline.