liveBook · Manning

Exclusive scan

As explained in Grokking GPU Programming

An exclusive scan computes each prefix result using only elements before the current position, beginning with the operation's identity element.

When several workers need different amounts of space in one output array, each needs to know how much space earlier workers will use. An exclusive scan computes those starting offsets: each result combines the elements before its position, leaving out the current element. section 7.15 section 6.1

Running totals before each element

For input [3, 1, 7, 0, 4, 1, 6, 3], the exclusive sum scan is [0, 3, 4, 11, 11, 15, 16, 22]. The first result is 0 because nothing comes before the first element; the result at index 3 is 3 + 1 + 7 = 11. An inclusive scan instead includes the current element. Unlike a reduction, either scan retains a result at every position. section 6.1

output[0] = 0
0 (nothing before me)
output[1] = 3
3
output[2] = 3 + 1
4
output[3] = 3 + 1 + 7
11
output[4] = 3 + 1 + 7 + 0
11
output[5] = 3 + 1 + 7 + 0 + 4
15
output[6] = 3 + 1 + 7 + 0 + 4 + 1
16
output[7] = 3 + 1 + 7 + 0 + 4 + 1 + 6
22

Follow the input terms included in each exclusive prefix sum. section 6.1

For addition, start a sequential scan with output[0] = 0, then compute output[i] = output[i−1] + input[i−1]. Using input[i] instead includes the current value and gives the wrong prefix. More generally, the first result is the operation’s identity: for multiplication it is 1. Parallel scan requires an associative operation so that regrouping does not change the result; floating-point addition can still differ slightly because of rounding. section 6.1

An inclusive result can be converted to exclusive by shifting it right and placing the identity first. For addition, convert exclusive to inclusive by adding each original input element to its matching result. If the scan overwrites its input, save the original values first. section 6.19 section 7.11

Parallel scans shorten the chain of dependent steps. Hillis–Steele produces an inclusive scan in O(log n) rounds but performs O(n log n) work. Blelloch produces an exclusive scan in O(log n) depth with O(n) work: an up-sweep builds partial sums, then the root is replaced with the identity and a down-sweep distributes the sums of preceding elements. Its two phases take more rounds than Hillis–Steele. section 6.19 section 7.21

In a CUDA implementation, threads must finish each round before the next reads its results. Missing a synchronization barrier can produce results that are correct on some runs and wrong on others. The illustrated single-block Blelloch kernel assumes a power-of-two size; other sizes can be padded with the identity. Save the root total before replacing it if it is needed later. section 6.18 section 7.8

Exclusive scans are useful whenever a position needs the total before it:

  • Stream compaction: mark kept elements with 1 and discarded elements with 0. Scanning the flags gives each keeper its zero-based output slot; the last scan value plus the last flag gives the output size. section 7.14
  • Variable-sized allocation: sizes [3, 1, 4, 2, 5] scan to starting offsets [0, 3, 4, 8, 10], giving each worker a consecutive, nonoverlapping range. section 7.15
  • Multi-block scan: exclusive-scan the block totals so each block receives the sum of all preceding blocks as its offset. section 7.12

How Grokking GPU Programming covers it

How deep it goes
Develops sequential and parallel scans through Blelloch’s synchronization and work bounds, while describing rather than implementing the multi-block strategy.
Examples
Traces an eight-element prefix sum, filtering positive values, and assigning offsets for five variable-sized allocations.
What you can do after
Builds a single-block CUDA exclusive scan from scratch and uses its results to reason about output positions.
How it connects
Connects exclusive scan to inclusive scan, reduction, stream compaction, and parallel memory allocation.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Grokking GPU Programming. The section links point to the parts of the book it draws on.