# Work-Efficient: Upsweep, Downsweep

*Task 5 of 6 · [Prefix Sums (Scan)](https://gpu.rocks/learn/prefix-sum-351cfa41.md) · GPU.js Learn*

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.

## Figures

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

## Goal

**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

```js
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:

```js
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.

## Starter code

```js
// Two sweeps of a balanced tree. ~2n additions instead of n·log2(n).
const gpu = new GPU({ mode });
const N = 1024;

// UPSWEEP — build the reduction tree in place.
const upsweep = gpu.createKernel(function (data, stride) {
  const i = this.thread.x;
  // TODO: only the TOP cell of each 2*stride block works this pass — it
  // absorbs the subtotal `stride` places to its left. Everyone else
  // passes their value straight through.
  return data[i];
}, { output: [N] });

// DOWNSWEEP — walk the tree back down.
const downsweep = gpu.createKernel(function (data, stride) {
  const i = this.thread.x;
  // TODO: two kinds of active cell this pass, everyone else passes through:
  //   * the top of each 2*stride block keeps its own value PLUS its left
  //     partner's old subtotal;
  //   * that left partner takes over the block top's old value.
  return data[i];
}, { output: [N] });

// An exclusive scan starts from 0 at the root — prewired.
const clearLast = gpu.createKernel(function (data) {
  if (this.thread.x === this.constants.n - 1) {
    return 0;
  }
  return data[this.thread.x];
}, { output: [N], constants: { n: N } });

let v = Float32Array.from(values);

for (let stride = 1; stride < N; stride *= 2) {
  v = await upsweep(v, stride);
}

const total = v[N - 1]; // the upsweep already reduced the whole array
v = await clearLast(v);

for (let stride = N / 2; stride >= 1; stride /= 2) {
  v = await downsweep(v, stride);
}

console.log('exclusive[512]:', v[512]);
console.log('grand total:', total);
```

---

Interactive version: https://gpu.rocks/learn/prefix-sum-351cfa41/5

[Previous task](https://gpu.rocks/learn/prefix-sum-351cfa41/4.md) · [Next task](https://gpu.rocks/learn/prefix-sum-351cfa41/6.md)