Task 3 of 6

The Doubling Ladder

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.

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

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:

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:

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.

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.