Parallel Dynamic Programming

In dynamic programming, a directed acyclic graph (digraph) of subproblems
is defined, and all of them are computed in topological order, i.e., if
there is an arc (arrow) from A to B, A must be visited (i.e., its subproblem
solved) before B.

There are commonly many topological orderings for a given digraph, and it does
not usually matter in which order they are visited.  If there is no directed
path from A to B or from B to A, we say that A and B are independent.

In parallel dynamic programming, independent subproblems can be computed
simultaneously, speeding up the computation if many processors are available.
We consider the following problems which yield to this technique:

1(a).  Finding the maximum or minimum item in an array.
1(b).  Finding the sum of items in an arry.

These two use the same digraph.

2(a).  Finding the prefix sum array of an array.
2(b).  Finding the sum of two binary numerals.  (The hard-wired algorithm
in some computers that I discussed on July 8.)

These two use almost the same digraph.