Parallel Dynamic Programming

Parallel Dynamic Programming is the technique for extracting parallelism from dynamic programming algorithms that have data dependencies between subproblems — using wavefront (anti-diagonal) execution, dependency analysis, and pipeline parallelism to process independent subproblems simultaneously, achieving parallel speedups of P/dependencies on P processors for algorithms like sequence alignment (Smith-Waterman), shortest paths (Floyd-Warshall), and RNA structure prediction that appear inherently serial at first glance.

The DP Parallelism Challenge

Dynamic programming tables have dependencies: cell (i,j) depends on previously computed cells. In the classic Smith-Waterman alignment:

DP[i][j] = max(DP[i-1][j-1] + score, DP[i-1][j] + gap, DP[i][j-1] + gap, 0)

Cell (i,j) depends on (i-1,j-1), (i-1,j), and (i,j-1). Row i cannot start until row i-1 is complete. Column j cannot start until column j-1 is complete. But cells on the same anti-diagonal are independent.

Wavefront (Anti-Diagonal) Parallelism

The anti-diagonal d = i+j contains all cells where the sum of indices equals d. For a table of size M×N:
- Anti-diagonal d=0: cell (0,0) — 1 cell, no parallelism.
- Anti-diagonal d=k: cells (0,k), (1,k-1), ..., (k,0) — k+1 independent cells.
- Peak parallelism: min(M,N) cells at the middle anti-diagonals.

Execution proceeds anti-diagonal by anti-diagonal. Within each anti-diagonal, all cells can be computed in parallel. Total work: M×N. Span: M+N-1 steps. Speedup: M×N/(M+N-1) ≈ min(M,N)/2 for square tables.

GPU Implementation

For Smith-Waterman on GPU:
- Each anti-diagonal is processed by a kernel launch (or a single kernel with grid-level synchronization).
- Each thread computes one cell on the anti-diagonal.
- M+N-1 synchronization barriers (one per anti-diagonal).
- Optimization: tile the DP table into blocks. Within each block, compute the full anti-diagonal wavefront. Between blocks, pipeline the computation — block (1,0) can start its second anti-diagonal as soon as block (0,0) finishes its first row of outputs.

Other Parallel DP Patterns

• Floyd-Warshall (All-Pairs Shortest Paths): Phase k depends on phase k-1, but within phase k, all N² cell updates are independent. N phases × N² parallel work per phase = O(N³) total with O(N) span.
• Viterbi Algorithm (HMM Decoding): Each time step depends on the previous step, but all S states within a time step are independent. T sequential steps × S parallel states.
• CYK Parsing: Cells (i,j) depend on all split points (i,k) and (k+1,j). Anti-diagonal parallelism on the span (j-i) dimension.

Pipelining for Additional Parallelism

Tile the DP table into rectangular blocks. Block (r,c) depends on blocks (r-1,c), (r,c-1), and (r-1,c-1). These block-level dependencies form a coarser wavefront. Pipelining overlaps computation of block (r,c)'s interior with communication of block (r-1,c)'s boundary — increasing the effective parallelism beyond the anti-diagonal width.

Parallel Dynamic Programming is the art of finding and exploiting the independence hidden within apparently sequential recurrences — transforming algorithms that look inherently serial into wavefront-parallel computations that scale across hundreds of GPU cores or distributed processors.