# One Rung of the Ladder

*Task 3 of 6 · [Reductions](https://gpu.rocks/learn/reductions-3dadc130.md) · GPU.js Learn*

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

## Figures

- **your partner lives one output-width away**

## Goal

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

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

## Starter code

```js
// Fold the top half onto the bottom half: 512 values in, 256 out.
const gpu = new GPU({ mode });

const halve = gpu.createKernel(function (data) {
  // TODO: add this thread's element to its partner in the top half.
  // The fold distance is this.output.x.
  return data[this.thread.x];
}, {
  output: [256],
});

const folded = await halve(data);
console.log('folded length:', folded.length);
console.log('first pair sum:', folded[0]);
```

---

Interactive version: https://gpu.rocks/learn/reductions-3dadc130/3

[Previous task](https://gpu.rocks/learn/reductions-3dadc130/2.md) · [Next task](https://gpu.rocks/learn/reductions-3dadc130/4.md)