liveBook · Manning

Scan

As explained in Grokking GPU Programming

The scan pattern computes cumulative results for the prefixes of an ordered sequence.

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

How Grokking GPU Programming covers it

How deep it goes
Develops inclusive and exclusive scans through Hillis-Steele and Blelloch, including correctness, synchronization, work, depth, and multi-block scaling.
Examples
Traces an eight-element prefix sum and uses scanned flags to place retained values in a compacted array.
What it assumes
Introduces running totals and scan variants with examples while drawing on reduction, identity elements, and thread synchronization.
What you can do after
Builds CUDA scan kernels and applies scan through NumPy or PyTorch.
How it connects
Connects scan to reduction, associativity, stream compaction, memory allocation, and radix sort.

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.