Task 6 of 6

Watch the Wavefront, Then Read the Bill

Thirty-two bases against thirty-six, sharing a mutated stretch in the middle. Sixty-seven launches, and this time each one renders — so the console gives you a scrubber and you can watch the wavefront march from the top-left corner to the bottom-right, lighting the ridge where the two sequences agree.

Then the bill. Diagonal 2 has one cell. Diagonal 34 has thirty-two. Diagonal 68 has one again. Average occupancy across the sweep is around |A| / 2 threads, and the launches at either end are launches for a handful of work — which is why nobody ships this. Real aligners cut the matrix into tiles and run a wavefront over the tiles instead, so each launch has thousands of cells to chew on; or they abandon the wavefront entirely and align a whole database at once, one sequence per thread, which is embarrassingly parallel and needs no cleverness at all.

Both of those are engineering. The reframing — that a dynamic program nobody could parallelise turns out to be parallel along a diagonal — is the idea, and it survives every one of those refinements intact.

Goal: paint each frame of the sweep, and plot how much work each launch actually had against how many threads it started.

Requirements

Hint 1 — the paint kernel is a two-way branch

Read the score once, then decide which of the two colours this pixel gets:

const v = H[this.thread.y][this.thread.x] / this.constants.top;
if (this.thread.x + this.thread.y === d) {
  this.color(1, 0.6, 0.1, 1);
} else {
  this.color(v * 0.35, v * 0.95, v * 0.75, 1);
}
Hint 2 — how long is a diagonal?

The same clipping as before, one sequence length apiece:

const iStart = Math.max(1, d - 36);
const iEnd = Math.min(32, d - 1);
lengths.push(iEnd - iStart + 1);

Note the d - 1 and the 1: row 0 and column 0 are never computed, so they are not cells this algorithm has work for.

Hint 3 — reading the plot

The two series differ by two orders of magnitude at the ends, which is why the plot asks for a log axis. The flat line is what every launch costs; the triangle under it is what every launch is worth.

Same idea elsewhere

Occupancy — how much of the machine a launch actually keeps busy — is the number that decides whether a GPU port was worth it, and a triangular work profile is a classic way to lose. The standard answers are the ones real aligners use: tile the domain so every launch is full (CUDA's blocked wavefront, the same idea as cache blocking), or find a coarser axis of parallelism and use that instead. Modern tools like WFA go further and change the algorithm so the wavefront is short in the first place.

All tasks in Wavefronts: Aligning DNA on the Diagonal

  1. Three Ways Into a Cell
  2. The Anti-Diagonal Goes All At Once
  3. Which Cell Am I?
  4. Ride the Wavefront Down
  5. Traceback: What Did It Actually Align?
  6. Watch the Wavefront, Then Read the Bill

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