Wavefront Parallelism

Table of Contents

• Problem Formulation
• Building the Task Graph
• Applications

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

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:

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.

Building the Task Graph

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

#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;
}

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:

Applications

Wavefront parallelism appears across many domains:

• Dynamic 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.
• Video encoding: many video codecs process macroblocks in wavefront order to exploit intra-frame dependencies while maximising parallelism.
• Image processing: morphological operations, flood fill, and distance transforms on 2D grids follow a similar diagonal sweep.