# Ride the Wavefront Down

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

Sixteen launches, resized one at a time, each writing its diagonal back into a plain
JavaScript matrix so the next launch can read it. That is the whole algorithm — and the
driving loop looks a lot like the halving ladder in Reductions, except the kernel grows and
then shrinks instead of only shrinking.

The best score is picked up on the way past. Smith-Waterman's answer is the largest value
*anywhere* in the matrix, not the bottom-right corner — that corner is
Needleman-Wunsch's answer to a different question ("align these end to end"). Track the
maximum and where it sat, because the next task walks backwards from exactly that cell.

Count the threads while you are here. The diagonals run
`1, 2, 3, … 8, 8, … 3, 2, 1` — 72 in total, one per cell, against the 1,440 the
previous task launched for the same answer. Twenty times fewer threads, and exactly the same
sixteen launches. Which is the honest headline: the launches, not the threads, are what this
algorithm actually pays for.

## Goal

**Goal:** drive the compact kernel across every anti-diagonal, stitch each
result back into `H`, and log `best score S at row I, column J`.

## Requirements

- For each `d` from 2 to 17: `setOutput([len])`, then `await` the launch
- Write value `t` back to `H[iStart + t][d - iStart - t]`
- Track the largest value seen and the cell it came from
- Log it in exactly this shape: `best score 13 at row 6, column 7`

## Hint 1 — the loop skeleton

```js
for (let d = 2; d <= 17; d++) {
  const range = diagonalRange(d);
  diagonal.setOutput([range.len]);
  const values =
    await diagonal(H, codesA, codesB, d, range.iStart);
  // … write values back into H, and watch for a new best …
}
```

## Hint 2 — stitching a diagonal back in

Thread `t` owned row `iStart + t`, and its column is
whatever makes the sum come to `d`:

```js
for (let t = 0; t < range.len; t++) {
  const i = range.iStart + t;
  H[i][d - i] = values[t];
}
```

## Hint 3 — the log line

The tests read this line, so keep the wording:

```js
console.log(
  'best score ' + best + ' at row ' + bi + ', column ' + bj
);
```

## Same idea elsewhere

Sixteen launches to fill 72 cells is a launch-bound program, and every platform has
machinery for exactly that complaint: CUDA graphs exist to replay a fixed sequence of tiny
kernels without paying per-launch driver cost, WebGPU lets you record many dispatches into
one command buffer, and Metal's indirect command buffers do the same job. When the work per
launch is small, the schedule is the program.

## Starter code

```js
// The whole fill: one resized launch per anti-diagonal.
const gpu = new GPU({ mode });

const diagonal = gpu.createKernel(function (H, a, b, d, iStart) {
  const i = iStart + this.thread.x;
  const j = d - i;
  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)));
}, { dynamicOutput: true, constants: { match: 3, mismatch: -3, gap: 2 } });

// Anti-diagonal d covers rows i = iStart … iStart + len - 1, and j = d - i.
// Clipped at both ends: i never passes 8 (= |A|), and j never passes 9 (= |B|).
function diagonalRange(d) {
  const iStart = Math.max(1, d - 9);
  const iEnd = Math.min(8, d - 1);
  return { iStart, len: iEnd - iStart + 1 };
}

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

let best = 0;
let bi = 0;
let bj = 0;

// TODO: for each d from 2 to 17 — resize the kernel to the diagonal,
//       await the launch, write the values back into H, and keep the
//       largest score you have seen along with its row and column.

console.log('best score ' + best + ' at row ' + bi + ', column ' + bj);
console.log('threads launched:', 72, 'vs', 16 * 9 * 10, 'for the full-matrix sweep');
```

---

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

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