Suppose each item in an array needs to know the sum of all the items before it. A sequential loop can carry a running total from left to right, but each step depends on the previous one. The Blelloch algorithm uses a tree to compute these exclusive prefix sums in parallel, with O(n) total work and O(log n) depth. section 7.0 section 7.1
The algorithm works in two phases, using an array as an implicit binary tree:
- Up-sweep: starting with stride 1, add each left sibling’s value into its right sibling. Double the stride each round until the last position holds the total. section 7.1
- Seed: replace the total at the root with 0, because nothing comes before the whole array. section 7.4
- Down-sweep: halve the stride each round. Give the left child its parent’s prefix; give the right child that prefix plus the left subtree’s total. The leaves become the exclusive scan. section 7.4
Scanning eight values
For [3, 1, 7, 0, 4, 1, 6, 3], the up-sweep combines positions 1, 3, 5, and 7 at stride 1; positions 3 and 7 at stride 2; and position 7 at stride 4. After the root is cleared and the down-sweep distributes prefixes, the result is [0, 3, 4, 11, 11, 15, 16, 22]. Each result excludes its own input value. section 7.1 section 7.11
Figure 7.1 The Blelloch scan in two phases. The up-sweep builds an implicit reduction tree across 3 rounds; the seed step replaces the root with 0; the down-sweep distributes prefix sums back down across 3 rounds. Dotted boxes are unchanged, dashed boxes are computed by add, and solid boxes are computed by swap-and-add.

Follow the reduction tree, root seed, and prefix distribution across all three rounds of each phase. section 7.1
In a CUDA implementation, threads load the input into one shared-memory buffer and synchronize between rounds. A single buffer is safe because, within a round, one thread’s writes do not overlap positions read by other threads. The active index for thread tid is (tid + 1) × stride × 2 − 1 in both phases. section 7.1 section 7.21
The shown kernel assumes a power-of-two size and fits within one block of at most 256 elements. For another size, pad to the next power of two with zeros, pass the padded size to the kernel, and ignore padded results. Larger arrays need a multi-block strategy: scan each block, scan the block sums, then add the resulting offsets to each block. section 7.12 section 7.21
Blelloch uses fewer total additions than Hillis-Steele but takes twice as many tree rounds. Actual performance also depends on memory traffic, synchronization, and hardware utilization. To obtain an inclusive scan, add each original input value to its exclusive result; save the input first if the scan overwrites it. section 7.12 section 7.11 section 7.21
