Task 2 of 6

Everyone Sums Their Own Prefix

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

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.

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.