Task 5 of 6

Work-Efficient: Upsweep, Downsweep

Hillis-Steele is fast but greedy: ten passes over 1,024 cells is about n·log₂n ≈ 10,000 additions where the serial loop needed 1,023. The Blelloch scan gets that down to roughly 2n, in two halves of one balanced tree.

Upsweep is a plain tree reduction — the one the Reductions module builds — done in place: at stride 1 every odd cell absorbs its left neighbour, at stride 2 every fourth cell absorbs the subtotal two places left, and so on. After log₂n passes the last cell holds the grand total and each "block top" holds its own block's subtotal — a whole tree of partial sums, stored in the array it came from. Downsweep then walks that tree back down: put 0 in the last cell, and at each level a node hands its value down to its left partner while keeping its own value plus that partner's old subtotal. What falls out is the exclusive scan.

Be honest about the payoff. Blelloch does a fraction of the arithmetic — 2n against n·log₂n — but needs twice the kernel launches (21 here against 10), and near the root of the tree almost every thread is idle. At n = 1,024 the simpler ladder usually wins on the clock; work-efficiency only starts paying once the array is big enough that arithmetic, not launch overhead, is the bill. Press Benchmark and watch the better algorithm lose.

up the tree to build subtotals, down it again to hand them out

Goal: write the two sweep kernels. The prewired driver runs upsweep up the tree, clears the last cell, and runs downsweep back down — producing the exclusive scan of values.

Requirements

Upsweep: only the top cell of each 2·stride block changes, to data[i] + data[i − stride]
Downsweep: the block top becomes data[i] + data[i − stride], and its left partner takes over the block top's old value
Every other cell in both kernels passes its value straight through
Log exclusive[512] and the grand total

Hint 1 — which cells are active?

At stride s the blocks are 2s wide, so their tops sit at indexes 2s − 1, 4s − 1, 6s − 1, … — exactly the cells where (i + 1) % (2 * stride) === 0. The top's left partner is stride places earlier, so the partner's own test is (i + 1 + stride) % (2 * stride) === 0.

Hint 2 — the upsweep body

const i = this.thread.x;
if ((i + 1) % (2 * stride) === 0) {
  return data[i] + data[i - stride];
}
return data[i];

At stride 1 that is cells 1, 3, 5, …; at stride 2 it is cells 3, 7, 11, … — half as many workers each pass, which is where the n·log n turns into 2n.

Hint 3 — the downsweep body

Two active cases, and everybody else passes through:

const i = this.thread.x;
const block = 2 * stride;
if ((i + 1) % block === 0) {
  return data[i] + data[i - stride];
}
if ((i + 1 + stride) % block === 0) {
  return data[i + stride];
}
return data[i];

The second case is the left partner taking over the block top's old value — which is why both swaps have to happen in the same pass, reading the same snapshot.

Same idea elsewhere

Blelloch's two sweeps are the textbook work-efficient scan, and they are what every GPU course draws on the board. Production libraries have moved past them: CUB's DeviceScan uses a single-pass decoupled look-back, where each block scans locally and then waits on its predecessors' aggregates, because on modern hardware the bill is memory traffic rather than additions — and two full sweeps means reading the array twice. Knowing why the elegant answer lost is the real lesson.

All tasks in Prefix Sums (Scan)

This page is an interactive exercise — the editor, the GPU runner and your saved progress need JavaScript. The text above is the full brief.