# Everyone Sums Their Own Prefix

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

The way out of a dependency chain is to refuse to wait. Thread `i`
does not ask thread `i − 1` for its answer — it computes its own from scratch,
summing `values[0 … i]` itself. No thread needs anything but the original
input, so all 1,024 of them run at once. Correct, embarrassingly parallel, and a
**gather**: reads from anywhere, a write only to its own cell.

And wasteful. Thread 1,023 does 1,024 additions, thread 512 does 513, and the whole
thing costs about **n²/2 ≈ 524,000 additions** where the serial loop needed
1,023. That is the price of refusing to wait, and it is worth paying once: this is the
honest baseline every cleverer scan has to beat, and the one you can put a stopwatch
on.

One wrinkle. You cannot write `for (let j = 0; j <= this.thread.x; j++)` —
in gpu.js's WebGL backend a loop bound must be known when the shader is compiled, and
`this.thread.x` is not. So loop over the whole array and *mask*: every
thread walks all 1,024 elements and only counts the ones at or before its own index.

## Goal

**Goal:** return the inclusive prefix sum of `values` — one
thread per cell, each summing its own prefix — and log the grand total.

## Requirements

- Loop `for (let j = 0; j < this.constants.n; j++)` — a compile-time bound
- Add `data[j]` only while `j <= this.thread.x`
- The last cell already holds the grand total — `console.log` it

## Hint 1 — which elements are mine?

Thread 7 wants elements 0 through 7, its own included. Thread 0 wants only
element 0. So the test inside the loop is `j <= this.thread.x` — with
the equals sign, because the scan is *inclusive*.

## Hint 2 — the loop body

```js
let sum = 0;
for (let j = 0; j < this.constants.n; j++) {
  if (j <= this.thread.x) {
    sum += data[j];
  }
}
return sum;
```

## Same idea elsewhere

The brute-force scan is not only a straw man — it is what you actually want at
the very bottom of the hierarchy, where a handful of values already sit in registers and
a smarter algorithm's bookkeeping costs more than the redundant adds. Above that size it
loses badly, which is why CUB, rocPRIM and Thrust all switch strategy by scale instead of
shipping one scan.

## Starter code

```js
// 1024 threads, each summing its own prefix. Nobody waits for anybody.
const gpu = new GPU({ mode });

const prefix = gpu.createKernel(function (data) {
  // TODO: accumulate data[j] for every j at or before this thread's index.
  // The loop bound has to be a compile-time constant, so walk the whole
  // array and mask with an if.
  return data[this.thread.x];
}, {
  output: [1024],
  constants: { n: 1024 },
});

const scan = await prefix(values);
console.log('scan[0]:', scan[0], ' scan[1]:', scan[1], ' scan[2]:', scan[2]);
// TODO: the last cell is already the grand total — log it.
console.log('grand total:', 0);
```

---

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

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