liveBook · Manning

Blelloch algorithm

As explained in Grokking GPU Programming

The Blelloch algorithm is a work-efficient parallel algorithm for computing a scan.

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

How Grokking GPU Programming covers it

How deep it goes
Explains both tree phases and their invariants, then gives a complete single-block CUDA kernel and outlines multi-block scaling.
Examples
Walks through an eight-element array and computes its exclusive prefix sums with a CUDA kernel.
What it assumes
Builds on reduction-tree knowledge while recapping inclusive and exclusive scans.
What you can do after
Build an in-place CUDA exclusive scan and adapt its result to an inclusive scan.
How it connects
Connects exclusive scan with reduction trees, inclusive scan, Hillis-Steele scan, stream compaction, 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.