# The Sum So Far

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

A **prefix sum** — a *scan* — is a running total. Give it
`[3, 1, 4, 1]` and it answers `[3, 4, 8, 9]`: cell `i`
holds everything from the start up to and including element `i`. A reduction
collapses an array to a single number; a scan keeps *every* partial answer along
the way, which turns out to be far more useful.

In JavaScript it is two lines, and the shape of those two lines is the whole
problem:

```js
out[0] = x[0];
out[i] = out[i - 1] + x[i];
```

Look at what cell `i` needs: not its neighbour's *input*, but its
neighbour's **answer**. Every thread on a GPU starts at the same instant, so
when thread 7 reaches for `out[6]` nobody has computed it yet — and nobody will,
because thread 6 is waiting on thread 5. That is a serial dependency chain as long as the
array, and it cannot be a kernel. Write it here in plain JavaScript first; the rest of
this module is five ways around it.

## Goal

**Goal:** fill `running` so that `running[i]` is
the total rainfall of days `0 … i`, then log the array and the season total.

## Requirements

- No kernel yet — plain JavaScript, so the dependency is impossible to miss
- `running[0]` is just `rainfall[0]`; every later cell adds that day to the cell before it
- `console.log` the whole `running` array, and the season total

## Hint 1 — seed the chain

Cell 0 has nothing before it, so it is the only cell that does not read
`running[i - 1]`. Set it first, then loop from `i = 1`.

## Hint 2 — the loop

```js
running[0] = rainfall[0];
for (let i = 1; i < rainfall.length; i++) {
  running[i] = running[i - 1] + rainfall[i];
}
```

The season total is the last cell — an inclusive scan ends with the
reduction already done.

## Same idea elsewhere

Every serious GPU platform ships a scan primitive precisely because you cannot
write one by accident: CUDA has `thrust::inclusive_scan` and CUB's
`DeviceScan`, ROCm has rocPRIM's `inclusive_scan`, Metal Shading
Language has `simd_prefix_inclusive_sum`, and WGSL's subgroup extension has
`subgroupInclusiveAdd`. All of them exist to break the chain you are about to
feel.

## Starter code

```js
// No kernel here. Plain JavaScript, so the dependency is unmissable.
const running = new Array(rainfall.length);

// TODO: running[i] should be the total of rainfall[0 ... i].
// Right now every cell is just that day's rain — nothing accumulates.
for (let i = 0; i < rainfall.length; i++) {
  running[i] = rainfall[i];
}

console.log('daily  :', rainfall);
console.log('running:', running);
console.log('season total:', running[running.length - 1]);
```

---

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

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