Task 4 of 6

Ride the Wavefront Down

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

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:

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:

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.

All tasks in Wavefronts: Aligning DNA on the Diagonal

This page is an interactive exercise — the editor, the GPU runner and your saved progress need JavaScript. The text above is the full brief.