Prefix scans and compaction
Compute inclusive and exclusive scans and use an exclusive scan to assign stable output positions
Before you begin
Follow a linked prerequisite when you cannot explain it from memory. Background skills without links are stated as abilities rather than hidden terminology.
- Hierarchical reduction
- Arrays, indexing, and associative operations
A GPU program filters one million token records and must write every accepted record into a dense output array. The program cannot use one ordinary shared counter safely because thousands of threads would race to claim the next position. A common implementation first writes one keep flag per record, such as [1, 0, 1, 1], then runs a library operation such as CUB DeviceScan. Inspecting the intermediate arrays shows offsets [0, 1, 1, 2], which give unique destinations to the three accepted records.
The array of running offsets is called a prefix scan. A profiler usually shows a small sequence of GPU kernels or a specialized single-pass scan kernel, plus reads and writes of the flag and offset arrays. Comparing the input flags with the output offsets gives the learner direct evidence of what the operation computed before any tree algorithm is introduced.
A prefix scan transforms values x into outputs y where each y contains the reduction of all earlier values. Prefix scans appear in cumulative sums, stream compaction, radix sorting, token offsets, and allocator bookkeeping. Unlike a simple reduction, the intermediate prefixes are outputs, so the algorithm cannot discard most of its tree.
A hierarchical scan separates local prefix calculation from block-offset distribution. A block computes local prefixes and one block total. A higher-level scan computes prefixes of the block totals. Each block then adds its assigned offset to its local results. The decomposition creates local parallel work plus a smaller scan over block totals.
A scan is easier to learn on eight values than on a million. Write the inclusive and exclusive results for the same input, then trace which partial sums an upsweep creates. The algorithm becomes practical only after the output definition and the temporary tree values are clearly distinguished.
Inclusive and exclusive scan
For input [3, 1, 4, 2], an inclusive sum scan is [3, 4, 8, 10]. Output i includes input i. The exclusive result is [0, 3, 4, 8]. Output i contains only inputs before i, and output 0 is the additive identity zero. For multiplication the identity would be one. For a maximum over integers it could be the lowest representable value.
The one-position difference controls how an application uses the result. Exclusive scan is convenient for allocation and placement because the output at i counts how much space earlier items require. Inclusive scan is convenient for cumulative totals. Converting between them is possible, but the first output and total-size calculation must remain explicit.
Work-efficient tree scan
A Hillis–Steele scan lets every element add a value at distances 1, 2, 4, and so on. The algorithm has logarithmic parallel depth, but it performs O(N log N) additions. A serial scan performs O(N) additions. The extra factor matters for large inputs even though each round is parallel.
A Blelloch-style scan uses an upsweep and a downsweep. The upsweep forms subtree totals exactly as a reduction tree does. For an exclusive scan, the root is replaced by the identity. During the downsweep, each node sends the incoming prefix to its left child and sends that prefix combined with the left-subtree total to its right child. Each tree edge participates in bounded work, so total additions remain O(N). A simple array implementation pads a non-power-of-two input to the next complete tree with identity values, or predicates the absent nodes. The tree is a schedule over shared-memory locations; it is not a separately allocated pointer structure.
Warp, block, and grid composition
A practical block scan usually begins with warp scans. Each warp produces local prefixes and one warp total. One warp scans the totals. The prefix assigned to an earlier warp is then added to every value in the next warp. Warp-and-block composition avoids a block-wide barrier at every logical tree level.
For an input larger than one block, the first kernel scans each block and writes its total. A second stage scans the block totals. A third stage adds the resulting block offset to every local output. Libraries may fuse or replace these passes with a single-pass method such as decoupled look-back. Decoupled look-back allows a block to obtain prefixes from earlier blocks through global state, but correctness depends on memory ordering and progress guarantees that are harder to implement than the three-stage design.
Scan as an index generator
Stable compaction first maps each input to a keep flag. The exclusive scan of those flags gives the destination index for every retained element. If flags are [1, 0, 1, 1], their exclusive scan is [0, 1, 1, 2]. The retained inputs at positions 0, 2, and 3 write to output positions 0, 1, and 2. No two retained elements receive the same destination, and their original order is preserved.
The same pattern converts variable record lengths into offsets. If record lengths are [4, 0, 3], an exclusive scan gives starting offsets [0, 4, 4] and the total allocation size is seven. Radix sort, sparse tensor construction, and token packing use variations of this idea. The scan supplies deterministic addresses; the application supplies the values written at those addresses.
Worked example: Stable stream compaction
Given one million records and a predicate, write passing records densely while preserving their original order.
- Evaluate the predicate into 0 or 1 for each record. Use an exclusive scan so the prefix before record i equals the number of passing records earlier than i.
- Trace a four-record example first. For keep flags [1, 0, 1, 1], verify that the exclusive result [0, 1, 1, 2] gives unique destinations only where the flag is one.
- If predicate[i] is one, write record i to output[prefix[i]]. Unique prefixes prevent races and preserve order.
- Obtain output length from the final prefix plus the last predicate. Avoid copying the entire prefix array if a fused or library primitive can produce positions and writes efficiently.
- Benchmark predicate distributions, including none, all, clustered, and random. Branch divergence and output traffic change even when scan work is similar.
- Compare a staged implementation that materializes flags and prefixes with a library or fused implementation. Attribute the difference to the extra full-array reads and writes.
Conclusion: Scan converts a data-dependent placement problem into deterministic indices. The primitive provides structure on which irregular algorithms can build dense memory access.
Common errors
- Confusing inclusive and exclusive semantics. The off-by-one difference changes placement and often fails only at boundaries.
- Comparing algorithms by span alone. Extra work, synchronization rounds, bank behavior, and global passes determine GPU performance.
- Ignoring the cost of materializing predicates or prefixes. Fusion can be more important than the scan kernel in isolation.
- Applying an in-place round update without preserving values from the previous round. Inter-warp execution order can then change results.
Reference summary
A scan returns every prefix reduction rather than only the final value. Exclusive sum turns boolean keep-flags into compacted output positions, builds offsets from variable lengths, and underlies radix sort and sparse formats. Work-efficient tree scans use an upsweep to form partial sums and a downsweep to distribute prefixes, composed hierarchically across warps and blocks.
exclusive_scan([a,b,c]) = [identity, a, a⊕b]flags = [1, 0, 1, 1]
offsets = [0, 1, 1, 2]
write input[i] to output[offsets[i]] when flags[i] == 1- Warp scans can use shuffle operations.
- Block scans combine warp results through a small shared-memory array.
- Grid scans require multiple phases, decoupled look-back, or library primitives.
- Use CUB or a framework primitive unless the surrounding operator creates a fusion opportunity.
Knowledge check
Describe how a boolean predicate, exclusive scan, and scatter implement stable stream compaction.
Show the answer guide
- The boolean predicate produces one flag per input: 1 when the element must be kept and 0 when it must be removed.
- An exclusive scan of the flags gives each input the number of retained elements that occur before it. The prefix count is the input's output index when its flag is 1.
- The scatter writes only flagged elements to their scanned offsets. Because different retained elements have different prefix counts, the writes do not contend for the same destination.
- The scan counts retained elements in original input order, so the scatter preserves that order and the compaction is stable. The final output length is the total flag sum, available from the last scan value plus the last flag.
Expose every array in stable stream compaction
Implement stable compaction for the declared input [7, 2, 9, 4, 5, 8, 1, 6] with the predicate keep values greater than or equal to 5. Materialize the predicate flags, exclusive offsets, compacted output, and output length. Then run the implementation on random arrays of lengths 0, 1, 31, 32, 33, 1024, and 1,000,003 and compare it with a stable CPU filter.
Evidence to keep: Submit code, the four intermediate arrays for the declared eight-element input, correctness tests that verify values and order for every edge shape, and a short causal explanation of why no two retained elements receive the same offset.
Compaction removes contention by assigning unique destinations. Histograms study the harder case where many inputs intentionally target the same small set of counters.
Sources and further reading
The lesson explanations synthesize primary papers and official references. Follow the originals for proofs, exact APIs, architecture details, and version-sensitive behavior.
- CUDA C++ Programming Guide↗
- CUDA C++ Best Practices Guide↗
- Nsight Compute Profiling Guide↗
- NVIDIA Nsight Systems User Guide↗
Official reference for capturing and reading CPU, CUDA API, GPU workload, and communication timelines.
- NVIDIA CUTLASS↗