Task 2 of 6

The Cheapest Path Down: One Launch per Row

A seam is a path: one pixel per row, and from row to row it may step at most one column left or right. The cheapest such path is a two-line dynamic program. Let M[y][x] be the price of the cheapest seam that ends at pixel (x, y):

M[0][x] = e[0][x]
M[y][x] = e[y][x] + min( M[y-1][x-1], M[y-1][x], M[y-1][x+1] )

Look at what that recurrence does and does not say. Cell [y][x] depends on row y - 1 and on nothing else in its own row — so every cell of a row is independent of every other cell of that row, while the rows themselves are strictly ordered. That is the whole trick: one kernel launch per row, 128 threads wide and 71 launches deep — row 0 is free, because nothing is above it. Parallel across, sequential down. (It is the same wavefront Wavefronts: Aligning DNA on the Diagonal finds along an anti-diagonal — there the independent set has to be dug out; here the rows hand it to you.)

One wrinkle worth knowing: each launch's output is the next launch's input, so the kernel must hand back a fresh buffer every call rather than recycling one. immutable: true is that promise, and every ping-ponging kernel in this course carries it.

a whole row at once, because nothing in it looks sideways — Two rows of a cumulative cost map. Three neighbouring cells in the finished row above are marked as the only cells the highlighted cell below can have come from. Every cell of the lower row is computed at the same time; the rows go one after another.

Goal: write step — one row of the recurrence — and drive it down the picture, one awaited launch per row.

Requirements

Cell x takes the smallest of prev[x - 1], prev[x] and prev[x + 1], skipping the ones that fall off the ends
Add this row's own energy: eRow[x] + best
Drive it in JavaScript: one await step(...) per row, in order — row y needs row y - 1's answer, so never fire them together
plot the finished bottom row so the cost across the picture is visible

Hint 1 — guarding the two ends

Column 0 has no x - 1 and the last column has no x + 1. Start from the cell directly above — which always exists — and only fold in the diagonals when they do:

let best = prev[x];
if (x > 0) best = Math.min(best, prev[x - 1]);
if (x + 1 < this.output.x) best = Math.min(best, prev[x + 1]);

Hint 2 — the driver

Row 0 is free: nothing is above it, so its cumulative cost is its energy. After that it is one launch per row:

for (let y = 1; y < energy.length; y++) {
  rows.push(await step(energy[y], rows[y - 1]));
}

Await each one before launching the next. Fire them all at once and every row after the first reads a promise instead of a row.

Same idea elsewhere

"Find the axis along which the cells are independent, then launch once per step along the other one" is the whole wavefront family: CUDA's dynamic-programming samples, the banded Smith–Waterman kernels in bioinformatics, and WebGPU compute passes separated by a barrier all look like this. The launch count is the depth of the dependency chain, and that is the number you optimise.

All tasks in Seam Carving: Content-Aware Resizing

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