# The Race

*Task 5 of 5 · [Iterative Linear Solvers](https://gpu.rocks/learn/iterative-solvers-e73b8e1f.md) · GPU.js Learn*

Everything is wired: the Jacobi sweep, both halves of the red-black sweep, and
the residual. Same plate, same starting guess of zero, same finish line — an RMS residual
below `0.0005`. Count sweeps.

"The same work per sweep" is the claim worth being careful about. One Jacobi sweep
updates all 900 interior cells once. One red-black sweep updates all 900 once too, in two
halves — the same averages, split across two kernel launches instead of one, with half the
threads in each launch copying themselves. Sweeps are what we are comparing; the extra
launch is what it costs. (A production kernel launches only the cells of one colour and
pays nothing for the copies.)

The residual is sampled every 5 sweeps rather than every sweep: the read-back is the
expensive part of this loop, and five sweeps barely move the number.

## Figures

- **same finish line, same work per sweep — 170 sweeps against 275**

## Goal

**Goal:** fill in the red-black loop, and read the two sweep counts off
the console — Jacobi should need about 275 sweeps and red-black about 170.

## Requirements

- Drive red-black with the same `sweepsToTolerance` helper the Jacobi baseline uses
- One red-black sweep is `black(red(u))` — both halves, in that order
- Count sweeps, not half-sweeps

## Hint 1 — the helper already does the counting

`sweepsToTolerance` takes one argument: a function that turns a grid
into the next grid. Because a kernel call is awaited, that function is
`async` — Jacobi's is `async u => await sweep(u)`, and the
helper awaits whatever it returns. Red-black's is one sweep — both halves — expressed
the same way.

## Hint 2 — the one-liner

```js
const redBlackSweeps = await sweepsToTolerance(
  async u => await black(await red(u))
);
```

Both halves inside one call, so the helper counts a full sweep each time it runs it. Both
`await`s matter: the outer one hands the helper a grid, and the inner one is
what makes the black half read the red half's output instead of a Promise.

## Same idea elsewhere

The shape of this measurement is the one that transfers, more than the numbers:
an iterative solver is judged on iterations-to-tolerance, and a GPU implementation is
judged on that *times* the cost of an iteration. Red-black buys fewer sweeps for one
extra dispatch, which is a trade you make on nearly every platform; the same ledger decides
whether SOR's relaxation factor, a Chebyshev acceleration or a full multigrid V-cycle is
worth its complexity. Multigrid is where this ends up — and its inner smoother is the
red-black sweep you just wrote.

## Starter code

```js
// Both solvers, one finish line. Jacobi's loop is done — write red-black's.
const gpu = new GPU({ mode });

const sweep = gpu.createKernel(function (u) {
  const x = this.thread.x;
  const y = this.thread.y;
  if (x === 0 || y === 0 || x === this.constants.size - 1 || y === this.constants.size - 1) {
    return u[y][x];
  }
  return (u[y][x - 1] + u[y][x + 1] + u[y - 1][x] + u[y + 1][x]) / 4;
}, { output: [32, 32], constants: { size: 32 } });

const red = gpu.createKernel(function (u) {
  const x = this.thread.x;
  const y = this.thread.y;
  if (x === 0 || y === 0 || x === this.constants.size - 1 || y === this.constants.size - 1) {
    return u[y][x];
  }
  // parity as a NUMBER — gpu.js cannot keep a boolean in a kernel variable
  const parity = (x + y) % 2;
  if (parity !== 0) return u[y][x];
  return (u[y][x - 1] + u[y][x + 1] + u[y - 1][x] + u[y + 1][x]) / 4;
}, { output: [32, 32], constants: { size: 32 } });

const black = gpu.createKernel(function (u) {
  const x = this.thread.x;
  const y = this.thread.y;
  if (x === 0 || y === 0 || x === this.constants.size - 1 || y === this.constants.size - 1) {
    return u[y][x];
  }
  // parity as a NUMBER — gpu.js cannot keep a boolean in a kernel variable
  const parity = (x + y) % 2;
  if (parity !== 1) return u[y][x];
  return (u[y][x - 1] + u[y][x + 1] + u[y - 1][x] + u[y + 1][x]) / 4;
}, { output: [32, 32], constants: { size: 32 } });

const residual = gpu.createKernel(function (u) {
  const x = this.thread.x;
  const y = this.thread.y;
  if (x === 0 || y === 0 || x === this.constants.size - 1 || y === this.constants.size - 1) {
    return 0;
  }
  return u[y][x - 1] + u[y][x + 1] + u[y - 1][x] + u[y + 1][x] - 4 * u[y][x];
}, { output: [32, 32], constants: { size: 32 } });

function rmsOf(grid) {
  let sum = 0;
  for (let y = 0; y < 32; y++) {
    for (let x = 0; x < 32; x++) sum += grid[y][x] * grid[y][x];
  }
  return Math.sqrt(sum / (32 * 32));
}

const TOL = 0.0005;
const CHECK_EVERY = 5;
const MAX_SWEEPS = 400;

// Sweeps until the RMS residual drops below TOL, checking every 5 sweeps.
// `step` turns one grid into the next.
async function sweepsToTolerance(step) {
  let u = plate;
  let sweeps = 0;
  while (sweeps < MAX_SWEEPS) {
    if (rmsOf(await residual(u)) < TOL) break;
    for (let i = 0; i < CHECK_EVERY; i++) {
      u = await step(u);
      sweeps++;
    }
  }
  return sweeps;
}

const jacobiSweeps = await sweepsToTolerance(async u => await sweep(u));
console.log('jacobi: converged in', jacobiSweeps, 'sweeps');

// TODO: one red-black sweep is the red half followed by the black half,
//       and the black half has to read what the red half just wrote.
//       Await both halves — an un-awaited call hands black a Promise.
const redBlackSweeps = await sweepsToTolerance(async u => u);
console.log('red-black: converged in', redBlackSweeps, 'sweeps');
```

---

Interactive version: https://gpu.rocks/learn/iterative-solvers-e73b8e1f/5

[Previous task](https://gpu.rocks/learn/iterative-solvers-e73b8e1f/4.md)