# The Doubling Ladder

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

Half a million additions for a thousand-element scan is a lot. Here is the trick
that gets it down to ten thousand: run **log₂(n) passes**, and on pass
`d` have every cell add the value `2^d` places to its left. Stride 1,
then 2, then 4, 8, … After pass `d` every cell holds the sum of the
`2^(d+1)` elements ending at it, so ten passes over 1,024 cells leave each one
holding its whole prefix. This is the **Hillis-Steele** scan — the same
stride ladder the Reductions module climbs to collapse an array, run the other way:
doubling instead of halving, and keeping every partial answer instead of only the
last.

One kernel, called ten times from a plain JavaScript loop with the stride as an
*argument*. That multi-pass gather formulation is the point: gpu.js gives you no
atomics and no shared memory, so a pass boundary is the only synchronisation there is —
and it is the same shape as the barrier-separated steps a CUDA or WebGPU scan uses.

It also hands you something for free. An in-place scan has a famous race: cell 7 reads
cell 6 while cell 6 is busy overwriting itself, and back comes somebody's half-finished
answer. Real GPU code prevents that with a barrier or a second buffer
(*ping-pong* buffering). Here a kernel cannot write into the array it is reading —
each pass **returns a new array** and the next pass consumes it, so the race
is simply unavailable. As long as you really do feed each pass the previous pass's
result.

## Figures

- **1, 2, 4 — every pass reaches twice as far, and cell 7 collects the lot**

## Goal

**Goal:** write the one-pass kernel, drive ten passes from JavaScript
with the stride doubling each time, and log `scan[511]` and the grand total.

## Requirements

- The kernel takes `(data, stride)` and returns `data[x] + data[x − stride]`
- Threads below `stride` have no partner — they pass their own value through
- Drive the passes from JS: `stride` = 1, 2, 4, … while `stride < 1024`
- Each pass reads the array the *previous* pass returned

## Hint 1 — one pass

Every cell wants the value `stride` places to its left — but cells
`0 … stride − 1` have no such cell. They keep what they already have:

```js
if (this.thread.x >= stride) {
  return data[this.thread.x] + data[this.thread.x - stride];
}
return data[this.thread.x];
```

## Hint 2 — the driver

Ten passes, and the stride *doubles* — `1, 2, 4, 8, …`, not
`1, 2, 3`. The reassignment is what makes pass `d` read what
pass `d − 1` returned:

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

## Hint 3 — why Float32Array

gpu.js locks an argument's type on a kernel's first call, and every pass hands
back a `Float32Array`. Start the ladder from one —
`Float32Array.from(values)` — so pass 1 sees the same type as passes
2 … 10.

## Same idea elsewhere

This exact ladder is burned into GPU silicon at warp scale. Metal's
`simd_prefix_inclusive_sum`, WGSL's `subgroupInclusiveAdd` and the
CUDA idiom built from `__shfl_up_sync` are all Hillis-Steele over 32 or 64
lanes, with a lane-id comparison playing the part of your `if (x >= stride)`
guard. What you are writing by hand across kernel launches, the hardware does in five
instructions inside a warp.

## Starter code

```js
// One kernel, log2(1024) = 10 calls. The stride doubles every pass.
const gpu = new GPU({ mode });
const N = 1024;

const scanStep = gpu.createKernel(function (data, stride) {
  // TODO: add the value `stride` places to your left — if it exists.
  // Threads below `stride` have no partner and keep their own value.
  return data[this.thread.x];
}, { output: [N] });

// gpu.js locks an argument's type on the first call, so start from a
// Float32Array — the same type every pass hands back.
let v = Float32Array.from(values);

// TODO: ten passes, stride 1, 2, 4, ... 512. Each pass must read the
// array the PREVIOUS pass returned.
v = await scanStep(v, 1);

console.log('scan[511]:', v[511]);
console.log('grand total:', v[N - 1]);
```

---

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

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