liveBook · Manning

Swap-and-add

As explained in Grokking GPU Programming

Swap-and-add is a scan operation that passes a parent value to a child and adds the child’s prior value to the parent.

Swap-and-add moves prefix information down the tree during a Blelloch scan. Save the right child’s value, add the left child’s value to the right, then put the saved value in the left child. section 7.9

First down-sweep round

With stride 4, position 7 holds 0 and position 3 holds 11. After swap-and-add, position 7 holds 11 and position 3 holds 0. These values are not necessarily final; later rounds finish the prefixes. section 7.9

Figure 7.6 Seed step and Down-sweep Round 1 (stride = 4). After the seed sets position 7 to 0, only position 7 (with its left sibling at position 3) is active. The swap-and-add gives position 3 the seed value 0 and position 7 the seed plus position 3’s old value (0+11 = 11). Solid boxes mark swap-and-add computations.

The figure traces the seed and first swap-and-add round, showing how the zero moves to the left while the sum moves to the right. section 7.3

How Grokking GPU Programming covers it

How deep it goes
Explains the in-place pair update and its role in producing prefixes; assumes the up-sweep has already built subtree sums.
Examples
Traces positions 7 and 3 changing from 0 and 11 to 11 and 0.
What it assumes
Assumes an up-sweep has produced subtree sums; explains how the root seed propagates through later rounds.
What you can do after
Understand how swap-and-add propagates exclusive prefix sums through the scan tree.
How it connects
Connects to Blelloch scan, exclusive scan, and up-sweep partial sums.

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.