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
