Task 2 of 6

The Anti-Diagonal Goes All At Once

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.

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

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:

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:

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.

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.