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
