liveBook · Manning

Up-sweep

As explained in Grokking GPU Programming

The up-sweep is the bottom-up phase of the Blelloch scan that combines values into subtree totals.

The up-sweep is the first phase of the Blelloch scan. Like building a reduction tree from the leaves upward, it combines neighboring values into larger subtree totals. The final active position holds the total of the array; the down-sweep later uses the tree to produce prefix sums. section 7.1 section 7.4

For [3, 1, 7, 0, 4, 1, 6, 3], the stride doubles each round, while the active positions become fewer:

  • At stride 1, positions 1, 3, 5, and 7 absorb their left neighbors, forming sums of pairs. section 7.2
  • At stride 2, positions 3 and 7 combine those pair sums into totals for four elements: 11 and 14. section 7.2
  • At stride 4, position 7 combines the two halves and holds the array total, 25. section 7.2

In a CUDA kernel, index = (tid + 1) × stride × 2 − 1 selects each thread’s target; that position adds the value stride places to its left. Every thread must reach the synchronization barrier after each round, including threads whose target is outside the array. section 7.7 section 7.7

Figure 7.3 Up-sweep Round 1 (stride = 1). The four right-sibling positions absorb their left neighbors: position 1 = 1+3 = 4 (sum of data[0..1]), position 3 = 0+7 = 7 (data[2..3]), position 5 = 1+4 = 5 (data[4..5]), position 7 = 3+6 = 9 (data[6..7]). Dashed boxes are positions just computed by add; dotted boxes are unchanged. Solid boxes, for swap-and-add, do not appear until the down-sweep.

Shows the first round’s active positions and pair sums for the example array. section 7.2

How Grokking GPU Programming covers it

How deep it goes
Traces stride updates, active indices, subtree-sum invariants, and CUDA synchronization, then leaves prefix propagation to the down-sweep.
Examples
Works through an eight-element array, showing active positions and partial sums at strides 1, 2, and 4.
What you can do after
Understand how stride and active indices combine array values into subtree totals in parallel.
How it connects
Connects Blelloch scan with reduction trees, down-sweep, shared memory, and Hillis-Steele scan.

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.