liveBook · Manning

Multi-block scan

As explained in Grokking GPU Programming

A multi-block scan strategy computes a scan over data spanning multiple GPU thread blocks by combining block-level results.

A scan that fits in one GPU thread block can run locally. For larger arrays, compute each block’s local scan, scan the block totals to find offsets, then add each offset to its block. Separate kernel passes let each step safely read the previous step’s results. section 7.12

The three steps are:

  • Scan each block independently. section 7.12
  • Collect the block totals and exclusive-scan them. Each block’s offset is the sum of all earlier blocks, so the first block gets zero. section 7.12
  • Add each offset to every element in its block. If the block-sums array is still too large for one block, repeat the strategy on that array. section 7.12

Four blocks of four

For [1, 2, 3, 4 | 5, 6, 7, 8 | 9, 10, 11, 12 | 13, 14, 15, 16], local inclusive scans end in totals 10, 26, 42, and 58. Their exclusive scan gives offsets 0, 10, 36, and 78. Adding those offsets produces the same result as a sequential inclusive scan. section 7.12

For about a million elements with blocks of 256, the block sums need two more scan levels before they fit in one block. This classic scan-then-propagate approach handles arbitrary-sized arrays; production libraries such as CUB fuse the steps into a single pass. section 7.12 section 7.21

How Grokking GPU Programming covers it

How deep it goes
Details the three passes and recursive block-sum levels, but stops short of implementing the multi-block strategy.
Examples
Works through a 16-element array in four blocks and a million-element array requiring three scan levels.
What you can do after
Understand how local scans and block offsets combine to match a sequential scan over a larger array.
How it connects
Connects parallel scan with inclusive scan, exclusive scan, and GPU thread blocks.

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.