# The Cheapest Path Down: One Launch per Row

*Task 2 of 6 · [Seam Carving: Content-Aware Resizing](https://gpu.rocks/learn/seam-carving-a23a0d9b.md) · GPU.js Learn*

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

```js
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.

## Figures

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

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

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

```js
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.

## Starter code

```js
// One launch per row. Across a row, nothing depends on anything.
const gpu = new GPU({ mode });

const step = gpu.createKernel(function (eRow, prev) {
  const x = this.thread.x;
  // TODO 1: the cheapest of the three cells above — prev[x - 1], prev[x],
  //         prev[x + 1] — with the two edge columns guarded.
  let best = prev[x];
  // TODO 2: add this row's own energy, eRow[x], and return it.
  return best;
}, {
  output: [128],
  immutable: true,        // each call's output is the next call's input
  dynamicOutput: true,
  dynamicArguments: true,
});

// Row 0 has nothing above it, so its cumulative cost is its energy. Start
// from a Float32Array: gpu.js locks an argument's type on the first call,
// and that is what every launch hands back.
const rows = [Float32Array.from(energy[0])];

// TODO 3: one awaited launch per remaining row.
// for (let y = 1; y < energy.length; y++) { … }

const bottom = rows[rows.length - 1];
console.log('cheapest seam costs', Math.min(...bottom), '· dearest', Math.max(...bottom));
plot(bottom, { title: 'cumulative cost of the bottom row', xLabel: 'column' });
```

---

Interactive version: https://gpu.rocks/learn/seam-carving-a23a0d9b/2

[Previous task](https://gpu.rocks/learn/seam-carving-a23a0d9b/1.md) · [Next task](https://gpu.rocks/learn/seam-carving-a23a0d9b/3.md)