A bank statement shows a running balance after each transaction. A scan, also called a prefix sum when using addition, does the same for an ordered array: it produces one cumulative result for every position. Unlike a reduction, which returns only the final total, a scan keeps all the intermediate totals. section 6.0 section 6.1
Inclusive and exclusive scans
For [3, 1, 7, 0, 4, 1, 6, 3], an inclusive sum scan includes the current element and produces [3, 4, 11, 11, 15, 16, 22, 25]. An exclusive scan excludes the current element and produces [0, 3, 4, 11, 11, 15, 16, 22]. The initial 0 is addition’s identity: adding it changes nothing. You can obtain the exclusive result by shifting the inclusive result right and inserting 0 at the front. section 6.1 section 6.19
Scans also work with other associative operations, including multiplication, minimum, and maximum. Associativity means regrouping the operations does not change the result; subtraction does not satisfy this requirement. Floating-point addition can produce slightly different low-order bits when the grouping changes. section 6.1
A sequential sum scan adds each input to the previous running total. That creates a chain of dependencies. Parallel scan rearranges the work into rounds: positions work simultaneously within a round, but each round must wait for the previous one. section 6.1 section 6.18
Hillis-Steele builds an inclusive scan by doubling the distance between partners each round:
- Start with the input values. At stride 1, each position with a left neighbor adds that neighbor’s previous value; the first position copies its value. section 6.7
- Repeat at strides 2, 4, and so on. Positions without a partner at the current stride copy their previous value. After each round, the covered window doubles, until it reaches the start of the array. section 6.7
- Read from one buffer and write to another, swapping their roles between rounds. This prevents a thread from reading a value already overwritten in the same round. section 6.19
for r = 1 to ceil(log2(n)):
stride = 1 << (r - 1) // 2^(r-1)
for each position i in parallel:
if i >= stride:
buf[pout][i] = buf[pin][i] + buf[pin][i - stride]
else:
buf[pout][i] = buf[pin][i]
swap(pin, pout)Follow the stride and buffer updates for each parallel round. section 6.7
For eight values, Hillis-Steele takes three rounds but performs 17 additions, versus seven sequential additions. More generally, it uses O(n log n) work and O(log n) rounds. Blelloch uses an up-sweep and a down-sweep to produce an exclusive scan with O(n) work and O(log n) depth, though it takes more rounds. section 6.6 section 7.12 section 7.1
A common CUDA mistake is to omit the barrier between rounds. Results may be correct on some runs and wrong on others because a thread can read before another finishes writing. In a block-level Hillis-Steele kernel, use double buffering and place __syncthreads() at the end of each round. For arrays larger than one block, scan blocks locally, scan their block sums, then add the resulting offsets back to each block. section 6.18 section 6.19 section 7.21
Compacting selected values
To filter an array in parallel, mark each value to keep with a 1 and each other value with a 0. An exclusive scan of the flags gives each kept value its zero-based output slot: it counts how many keepers came before. Move each keeper to that slot to preserve its original order. section 7.14
Scan also supports memory allocation and radix sort. For an existing implementation, try NumPy’s np.cumsum() on the CPU or PyTorch’s torch.cumsum(); the latter runs on the GPU when its tensor is on a CUDA device. section 7.21
