Task 3 of 6

One Rung of the Ladder

Sixty-four partials finished in JavaScript is fine. A million wouldn't be. To stay parallel all the way down, GPUs fold an array onto itself: add each element in the top half to its partner in the bottom half, and 512 values become 256 in a single parallel step. That's one rung of the halving ladder — every reduction library on every platform is built from this move.

One kernel invocation = one rung. Each thread adds exactly one pair: data[x] + data[x + half]. And half comes for free — the fold distance is just the output length, this.output.x.

your partner lives one output-width away

Goal: write the rung kernel — fold 512 values into 256 pair sums, preserving the total.

Requirements

output: [256] — one thread per pair
Each thread adds its own element to its partner one output-width away
The fold preserves the total: the 256 outputs sum to the same value as the 512 inputs

Hint 1 — how far away is my partner?

With 512 inputs and 256 outputs, thread x pairs with element x + 256 — and 256 is exactly this.output.x, the width of the output.

Hint 2 — the one-liner

return data[this.thread.x] + data[this.thread.x + this.output.x];

Same idea elsewhere

The halving fold is the heart of every tree reduction: CUDA's classic shared-memory reduction halves its stride once per barrier, and WGSL subgroup ops or Metal's simd_sum are the same fold executed inside the hardware. One rung here equals one barrier-separated step there.

All tasks in Reductions

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