liveBook · Manning

Down-sweep

As explained in Grokking GPU Programming

The down-sweep is the phase of the Blelloch scan that propagates accumulated results through the scan tree to produce prefix results.

The down-sweep carries prefix sums from the root of the Blelloch scan tree toward its leaves. Set the root to 0—the sum of nothing before the whole array—then visit strides from n/2 down to 1. section 7.3 section 7.9

At each active pair, save the right position’s value, add the left position’s value to the right, then put the saved value in the left. The left receives the prefix before its subtree; the right receives that prefix plus the left subtree’s total. This swap-and-add repeats until every position holds its exclusive prefix sum. section 7.9 section 7.4

Trace the final result

For [3, 1, 7, 0, 4, 1, 6, 3], the down-sweep produces [0, 3, 4, 11, 11, 15, 16, 22]. Each output is the sum of the input elements before that position, excluding the element at that position. section 7.3

Figure 7.8 Down-sweep Round 3 (stride = 1). Four pairs reach every position. After this final round, each cell holds its exclusive prefix sum: [0, 3, 4, 11, 11, 15, 16, 22].

Shows the final stride-1 round and the completed exclusive prefix sums. section 7.3

How Grokking GPU Programming covers it

How deep it goes
Traces the zero seed, reverse strides, swap-and-add operation, and prefix invariant through completion.
Examples
Works through an eight-element array and traces its final exclusive prefix sums.
What it assumes
Assumes the up-sweep has built subtree sums and explains how a zero root seed propagates prefixes.
What you can do after
Understand how the seed and subtree totals propagate to produce each exclusive prefix.
How it connects
Pairs with the up-sweep to produce an exclusive scan, using shared memory for in-place updates.

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.