# The Anti-Diagonal Goes All At Once

*Task 2 of 6 · [Wavefronts: Aligning DNA on the Diagonal](https://gpu.rocks/learn/sequence-alignment-a85ca6d9.md) · GPU.js Learn*

Look at what cell `(i, j)` actually reads: `(i−1, j−1)`,
`(i−1, j)` and `(i, j−1)`. Add the coordinates up. The cell sits on
`i + j = d`; its three predecessors sit on `d − 2`, `d − 1`
and `d − 1`. **Nothing on diagonal `d` reads anything else on
diagonal `d`.**

So every cell along an *anti-diagonal* — the lines running from bottom-left to
top-right — is independent of every other cell on it, and the whole diagonal can be computed
in one shot. The matrix is not serial; it is serial *along the wrong axis*. Sweep it
as a **wavefront** instead: diagonal 2, then 3, then 4, all the way to
`|A| + |B|`. Sixteen launches here, and inside each one there is nothing left to
order. (Finding the set of updates that cannot see each other is the same permission slip
red-black colouring hands out in Iterative Linear Solvers. Seam Carving runs a wavefront
too, but an easier one — its cells read only the row *above*, never their own row,
so a launch per row is already enough and it never has to go looking for the diagonal.)

One launch per diagonal, and a launch writes the *whole* matrix — so a cell that
is not on this diagonal has exactly one job: hand back the value it already has.

## Figures

- **the matrix is not serial, it is serial along the wrong axis**

## Goal

**Goal:** add the diagonal test to the kernel, then drive it once per
anti-diagonal, `d = 2 … 17`, and log the best score in the finished matrix.

## Requirements

- A cell with `i + j !== d` returns `H[i][j]` unchanged
- A cell with `i + j === d` runs the recurrence from the last task
- Loop `d` from `2` to `|A| + |B|` = `17`, awaiting each launch and feeding its result to the next
- Scan the finished matrix in plain JavaScript and `console.log` the best score

## Hint 1 — the guard is one line

Before any arithmetic, and after the boundary guard:

```js
if (i + j !== d) return H[i][j];
```

Every thread still writes exactly one cell — its own. Cells off the diagonal are not
"skipped", they are copied forward, ready for the diagonal that is about to need them.

## Hint 2 — the driver

Sixteen launches, each reading what the one before it wrote:

```js
let H = empty;
for (let d = 2; d <= 17; d++) {
  H = await sweep(H, codesA, codesB, d);
}
```

The `await` is not optional and the loop cannot be a
`Promise.all`: diagonal `d` is defined in terms of diagonal
`d − 1`.

## Hint 3 — why 17 and not 16

The first interior cell is `(1, 1)`, so the first diagonal worth
launching is `d = 2`. The last interior cell is `(8, 9)`, so the
last is `d = 17`. That is `|A| + |B| − 1 = 16` launches — stop one
short and the bottom-right corner never gets computed.

## Same idea elsewhere

Wavefront scheduling is the standard answer whenever a dependency graph has levels:
CUDA implementations of Smith-Waterman (CUDASW++, SW#) launch one kernel per anti-diagonal
exactly like this before they get clever, Vulkan and WebGPU express the same thing as one
dispatch per level with a barrier between, and a task-graph runtime like TBB or Taskflow is
doing nothing else when it runs a "ready set". The trick is always to find the axis along
which the dependencies point the other way.

## Starter code

```js
// One launch per anti-diagonal. Cells off the diagonal ride along unchanged.
const gpu = new GPU({ mode });

const sweep = gpu.createKernel(function (H, a, b, d) {
  const i = this.thread.y;
  const j = this.thread.x;
  if (i === 0 || j === 0) return 0;
  // TODO 1: this launch owns anti-diagonal d. A cell whose i + j is
  //         anything else must return H[i][j], untouched.
  let s = this.constants.mismatch;
  if (a[i - 1] === b[j - 1]) s = this.constants.match;
  const diag = H[i - 1][j - 1] + s;
  const up = H[i - 1][j] - this.constants.gap;
  const left = H[i][j - 1] - this.constants.gap;
  return Math.max(0, Math.max(diag, Math.max(up, left)));
}, { output: [10, 9], constants: { match: 3, mismatch: -3, gap: 2 } });

const empty = [];
for (let i = 0; i <= 8; i++) empty.push(new Array(10).fill(0));

let H = empty;
// TODO 2: launch once per anti-diagonal, d = 2 … 17, feeding each
//         result into the next launch.

let best = 0;
for (let i = 0; i <= 8; i++) {
  for (let j = 0; j <= 9; j++) if (H[i][j] > best) best = H[i][j];
}
console.log('best score', best);
```

---

Interactive version: https://gpu.rocks/learn/sequence-alignment-a85ca6d9/2

[Previous task](https://gpu.rocks/learn/sequence-alignment-a85ca6d9/1.md) · [Next task](https://gpu.rocks/learn/sequence-alignment-a85ca6d9/3.md)