# Colour the Board

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

Jacobi throws information away. Halfway through a sweep plenty of neighbours
already have better values, and Jacobi ignores every one of them because it reads only the
old grid. **Gauss-Seidel** is the fix a human would reach for: walk the cells
in order and always use the newest value available. It converges about twice as fast — and
it is *sequential by construction*. Cell 500 cannot start until cell 499 has
finished. There is no thread ordering on a GPU and no way to make one thread wait for
another, so the textbook algorithm is simply not on the menu.

The fix is a chessboard. The 5-point stencil only ever reads the four direct
neighbours, and on a chessboard every direct neighbour of a red square is black. So call a
cell **red** when `(x + y)` is even and **black** when
it is odd, and update all the reds at once: no red cell reads another red cell, so there is
nothing left to order. Then update all the blacks, reading the reds that were just
written — which is exactly the "use the newest value" that made Gauss-Seidel fast. One
sequential pass becomes two data-parallel half-sweeps.

This task is the red half. Every thread still writes only its own cell, so black cells
are not "skipped" — they gather *themselves*, unchanged, ready for the half-sweep
that is about to need them exactly as they are.

## Figures

- **a red cell's four neighbours are all black, so no red waits on a red**

## Goal

**Goal:** write the red half-sweep — cells with `(x + y) % 2 === 0`
take their neighbours' average, and every other cell (black cells and the whole boundary)
comes through untouched.

## Requirements

- Boundary cells return `u[y][x]`
- Keep the parity in a *number*: `const parity = (x + y) % 2;` — a boolean in a kernel variable does not compile on WebGL
- Cells with parity `1` (black) return `u[y][x]` unchanged
- Cells with parity `0` (red) return `(left + right + up + down) / 4`

## Hint 1 — the trap this task is built around

The natural spelling is a boolean, and it is the one thing gpu.js cannot do:

```js
const isRed = (x + y) % 2 === 0;   // throws on WebGL
```

The GL backend has no way to store a `bool` in a kernel variable, so it fails
at shader-compile time with *cannot convert from 'bool' to 'lowp float'* — and
the CPU backend runs it happily, which is how this reaches production. Keep the number:

```js
const parity = (x + y) % 2;        // 0 or 1
if (parity !== 0) return u[y][x];
```

## Hint 2 — three exits, one average

The kernel is a stack of guards: boundary first, then the wrong colour, then
the arithmetic. Whichever way a thread leaves, it writes exactly one cell — its own.

## Hint 3 — the whole body

```js
if (x === 0 || y === 0 || x === this.constants.size - 1
    || y === this.constants.size - 1) {
  return u[y][x];
}
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;
```

## Same idea elsewhere

Red-black ordering — and its multi-colour generalisation — is the standard way to
put a Gauss-Seidel or SOR smoother on a GPU: CUDA and WGSL do exactly this, one dispatch
per colour, and unstructured meshes get their colours from a graph-colouring pass first.
The idea generalises past solvers: a colour is simply a set of updates guaranteed not to
depend on each other, which is the same permission slip a wavefront or a task-graph level
hands out.

## Starter code

```js
// The red half-sweep: update the cells where (x + y) is even,
// and pass everything else through untouched.
const gpu = new GPU({ mode });

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];
  }
  // TODO 1: compute the parity as a NUMBER — const parity = (x + y) % 2;
  //         (a boolean in a kernel variable will not compile on WebGL)
  // TODO 2: parity 1 is black — return u[y][x] unchanged.
  // TODO 3: parity 0 is red — return the four neighbours' average.
  return u[y][x];
}, { output: [32, 32], constants: { size: 32 } });

const afterRed = await red(guess);
console.log('a red cell [16][16]:', guess[16][16], '→', afterRed[16][16]);
console.log('a black cell [16][17]:', guess[16][17], '→', afterRed[16][17]);
```

---

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

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