namespace tf {

/** @page wavefront Wavefront Parallelism

We study @em wavefront @em parallelism, a pattern that arises in dynamic
programming whenever computation propagates diagonally across a grid of
dependent cells.

@tableofcontents

@section WavefrontComputingFormulation Problem Formulation

Wavefront computation starts at a single corner of a data grid and
propagates its effect diagonally toward the opposite corner.
Each cell depends on the cell directly above it and the cell directly to
its left, so all cells along the same anti-diagonal are independent of one
another and can execute in parallel.

The following figure shows this propagation on a 9×9 grid partitioned into
a 3×3 arrangement of blocks:

@image html images/wavefront_1.png width=70%

The wavefront sweeps from the top-left block to the bottom-right block.
Each block is assigned one task.
Because a block only depends on its upper neighbour and its left neighbour,
all blocks on the same anti-diagonal can run simultaneously.

@section WavefrontTaskGraph Building the Task Graph

We express the wavefront as a two-level nested loop over block indices.
Since each block's dependency edges point @em inward from the blocks above
and to the left, we pre-allocate all tasks using tf::Taskflow::placeholder
before wiring any edges:

@code{.cpp}
#include <taskflow/taskflow.hpp>

int main() {

  tf::Executor executor;
  tf::Taskflow taskflow;

  const int num_blocks = 3;

  // pre-allocate a 2D grid of placeholder tasks
  std::vector<std::vector<tf::Task>> node(
    num_blocks, std::vector<tf::Task>(num_blocks)
  );
  for(int i = 0; i < num_blocks; i++) {
    for(int j = 0; j < num_blocks; j++) {
      node[i][j] = taskflow.placeholder();
    }
  }

  // assign work and wire wavefront dependencies in reverse order
  // so that each task's successors already exist when we call precede
  for(int i = num_blocks - 1; i >= 0; i--) {
    for(int j = num_blocks - 1; j >= 0; j--) {
      node[i][j].work([=]() {
        printf("compute block (%d, %d)\n", i, j);
      });
      if(j + 1 < num_blocks) node[i][j].precede(node[i][j+1]);  // right
      if(i + 1 < num_blocks) node[i][j].precede(node[i+1][j]);  // below
    }
  }

  executor.run(taskflow).wait();
  taskflow.dump(std::cout);

  return 0;
}
@endcode

The resulting task graph for a 3×3 wavefront is shown below.
Tasks along each anti-diagonal have no mutual dependencies and execute
in parallel; tasks on later diagonals wait for their upper and left
neighbours:

@dotfile images/wavefront_2.dot

@section WavefrontApplications Applications

Wavefront parallelism appears across many domains:

- @b Dynamic @b programming: longest common subsequence, edit distance, and
  biological sequence alignment (e.g., Smith-Waterman) all exhibit diagonal
  dependency patterns that map directly to this model.
- @b Video @b encoding: many video codecs process macroblocks in wavefront
  order to exploit intra-frame dependencies while maximising parallelism.
- @b Image @b processing: morphological operations, flood fill, and
  distance transforms on 2D grids follow a similar diagonal sweep.

*/

}
