Consider a weighted multistage graph of r + 1 levels, as shown in Figure 12.3. Each node at level i is connected to every node at level i + 1. Levels zero and r contain only one node, and every other level contains n nodes. We refer to the node at level zero as the starting node S and the node at level r as the terminating node R. The objective of this problem is to find the shortest path from S to R. The i^th node at level l in the graph is labeled . The cost of an edge connecting to node is labeled . The cost of reaching the goal node R from any node is represented by . If there are n nodes at level l, the vector is referred to as C^l. The shortest-path problem reduces to computing C⁰. Since the graph has only one starting node, . The structure of the graph is such that any path from to R includes a node (0 ≤ j ≤ n − 1). The cost of any such path is the sum of the cost of the edge between and and the cost of the shortest path between and R (which is given by ). Thus, , the cost of the shortest path between and R, is equal to the minimum cost over all paths through each node in level l + 1. Therefore,

Equation 12.2. 

Figure 12.3. An example of a serial monadic DP formulation for finding the shortest path in a graph whose nodes can be organized into levels.

Since all nodes have only one edge connecting them to the goal node R at level r, the cost is equal to . Hence,

Equation 12.3. 

Because Equation 12.2 contains only one recursive term in its right-hand side, it is a monadic formulation. Note that the solution to a subproblem requires solutions to subproblems only at the immediately preceding level. Consequently, this is a serial monadic formulation.

Using this recursive formulation of the shortest-path problem, the cost of reaching the goal node R from any node at level l (0 < l < r − 1) is

Now consider the operation of multiplying a matrix with a vector. In the matrix-vector product, if the addition operation is replaced by minimization and the multiplication operation is replaced by addition, the preceding set of equations is equivalent to

Equation 12.4. 

where C^l and C^l+1 are n × 1 vectors representing the cost of reaching the goal node from each node at levels l and l + 1, and M_l,l+1 is an n × n matrix in which entry (i, j) stores the cost of the edge connecting node i at level l to node j at level l + 1. This matrix is

The shortest-path problem has thus been reformulated as a sequence of matrix-vector multiplications. On a sequential computer, the DP formulation starts by computing C^{r −1} from Equation 12.3, and then computes C^{r −k−1} for k = 1, 2, ..., r −2 using Equation 12.4. Finally, C⁰ is computed using Equation 12.2.

Since there are n nodes at each level, the cost of computing each vector C^l is Θ(n²). The parallel algorithm for this problem can be derived using the parallel algorithms for the matrix-vector product discussed in Section 8.1. For example, Θ(n) processing elements can compute each vector C^l in time Θ(n) and solve the entire problem in time Θ(rn). Recall that r is the number of levels in the graph.

Many serial monadic DP formulations with dependency graphs identical to the one considered here can be parallelized using a similar parallel algorithm. For certain dependency graphs, however, this formulation is unsuitable. Consider a graph in which each node at a level can be reached from only a small fraction of nodes at the previous level. Then matrix M_l,l+1 contains many elements with value ∞. In this case, matrix M is considered to be a sparse matrix for the minimization and addition operations. This is because, for all x, x + ∞ = ∞, and min{x, ∞} = x. Therefore, the addition and minimization operations need not be performed for entries whose value is ∞. If we use a regular dense matrix-vector multiplication algorithm, the computational complexity of each matrix-vector multiplication becomes significantly higher than that of the corresponding sparse matrix-vector multiplication. Consequently, we must use a sparse matrix-vector multiplication algorithm to compute each vector.

A one-dimensional 0/1 knapsack problem is defined as follows. We are given a knapsack of capacity c and a set of n objects numbered 1, 2, ..., n. Each object i has weight w_i and profit p_i. Object profits and weights are integers. Let v = [v₁, v₂, ..., v_n] be a solution vector in which v_i = 0 if object i is not in the knapsack, and v_i = 1 if it is in the knapsack. The goal is to find a subset of objects to put into the knapsack so that

(that is, the objects fit into the knapsack) and

is maximized (that is, the profit is maximized).

A straightforward method to solve this problem is to consider all 2ⁿ possible subsets of the n objects and choose the one that fits into the knapsack and maximizes the profit. Here we provide a DP formulation that is faster than the simple method when c = O (2ⁿ /n). Let F [i, x] be the maximum profit for a knapsack of capacity x using only objects {1, 2, ..., i}. Then F [n, c] is the solution to the problem. The DP formulation for this problem is as follows:

This recursive equation yields a knapsack of maximum profit. When the current capacity of the knapsack is x, the decision to include object i can lead to one of two situations: (i) the object is not included, knapsack capacity remains x , and profit is unchanged; (ii) the object is included, knapsack capacity becomes x − w_i, and profit increases by p_i. The DP algorithm decides whether or not to include an object based on which choice leads to maximum profit.

The sequential algorithm for this DP formulation maintains a table F of size n × c. The table is constructed in row-major order. The algorithm first determines the maximum profit by using only the first object with knapsacks of different capacities. This corresponds to filling the first row of the table. Filling entries in subsequent rows requires two entries from the previous row: one from the same column and one from the column offset by the weight of the object. Thus, the computation of an arbitrary entry F [i, j] requires F [i − 1, j] and F [i − 1, j − w_i]. This is illustrated in Figure 12.4. Computing each entry takes constant time; the sequential run time of this algorithm is Θ(nc).

Figure 12.4. Computing entries of table F for the 0/1 knapsack problem. The computation of entry F[i, j] requires communication with processing elements containing entries F[i − 1, j] and F[i − 1, j − w_i].

This formulation is a serial monadic formulation. The subproblems F [i, x] are organized into n levels for i = 1, 2, ..., n. Computation of problems in level i depends only on the subproblems at level i − 1. Hence the formulation is serial. The formulation is monadic because each of the two alternate solutions of F [i, x] depends on only one subproblem. Furthermore, dependencies between levels are sparse because a problem at one level depends only on two subproblems from previous level.

Consider a parallel formulation of this algorithm on a CREW PRAM with c processing elements labeled P₀ to P_c−1. Processing element P_{r −1} computes the r^th column of matrix F. When computing F [j, r] during iteration j, processing element P_{r −1} requires the values F [j − 1, r] and F [j − 1, r − wj]. Processing element P_{r −1} can read any element of matrix F in constant time, so computing F [j, r] also requires constant time. Therefore, each iteration takes constant time. Since there are n iterations, the parallel run time is Θ(n). The formulation uses c processing elements, hence its processor-time product is Θ(nc). Therefore, the algorithm is cost-optimal.

Let us now consider its formulation on a distributed memory machine with c-processing elements. Table F is distributed among the processing elements so that each processing element is responsible for one column. This is illustrated in Figure 12.4. Each processing element locally stores the weights and profits of all objects. In the j^th iteration, for computing F [j, r] at processing element P_{r −1}, F [j − 1, r] is available locally but F [j − 1, r − w_j] must be fetched from another processing element. This corresponds to the circular w_j -shift operation described in Section 4.6. The time taken by this circular shift operation on p processing elements is bounded by (t_s + t_wm) log p for a message of size m on a network with adequate bandwidth. Since the size of the message is one word and we have p = c, this time is given by (t_s + t_w) log c. If the sum and maximization operations take time t_c, then each iteration takes time t_c + (t_s + t_w) log c. Since there are n such iterations, the total time is given by O (n log c). The processor-time product for this formulation is O (nc log c); therefore, the algorithm is not cost-optimal.

Let us see what happens to this formulation as we increase the number of elements per processor. Using p-processing elements, each processing element computes c/p elements of the table in each iteration. In the j^th iteration, processing element P₀ computes the values of elements F [j, 1], ..., F [j, c/p], processing element P₁ computes values of elements F [j, c/p + 1], ..., F [j, 2c/p], and so on. Computing the value of F [j, k], for any k, requires values F [j − 1, k] and F [j − 1, k − wj]. Required values of the F table can be fetched from remote processing elements by performing a circular shift. Depending on the values of w_j and p, the required nonlocal values may be available from one or two processing elements. Note that the total number of words communicated via these messages is c/p irrespective of whether they come from one or two processing elements. The time for this operation is at most (2t_s + t_wc/p) assuming that c/p is large and the network has enough bandwidth (Section 4.6). Since each processing element computes c/p such elements, the total time for each iteration is t_cc/p + 2t_s + t_wc/p. Therefore, the parallel run time of the algorithm for n iterations is n(t_cc/p + 2t_s + t_wc/p). In asymptotic terms, this algorithm’s parallel run time is O (nc/p). Its processor-time product is O (nc), which is cost-optimal.

There is an upper bound on the efficiency of this formulation because the amount of data that needs to be communicated is of the same order as the amount of computation. This upper bound is determined by the values of t_w and t_c (Problem 12.1).

Given a sequence A = <a_1, a_2, ..., a_n>, a subsequence of A can be formed by deleting some entries from A. For example, <a, b, z> is a subsequence of <c, a, d, b, r, z>, but <a, c, z> and <a, d, l> are not. The longest-common-subsequence (LCS) problem can be stated as follows. Given two sequences A = <a_1, a_2, ..., a_n> and B = <b₁, b₂, ..., b_m>, find the longest sequence that is a subsequence of both A and B. For example, if A = <c, a, d, b, r, z> and B = <a, s, b, z>, the longest common subsequence of A and B is <a, b, z>.

Let F [i, j] denote the length of the longest common subsequence of the first i elements of A and the first j elements of B. The objective of the LCS problem is to determine F [n, m]. The DP formulation for this problem expresses F [i, j] in terms of F [i − 1, j − 1], F [i, j − 1], and F [i − 1, j] as follows:

Given sequences A and B , consider two pointers pointing to the start of the sequences. If the entries pointed to by the two pointers are identical, then they form components of the longest common subsequence. Therefore, both pointers can be advanced to the next entry of the respective sequences and the length of the longest common subsequence can be incremented by one. If the entries are not identical then two situations arise: the longest common subsequence may be obtained from the longest subsequence of A and the sequence obtained by advancing the pointer to the next entry of B; or the longest subsequence may be obtained from the longest subsequence of B and the sequence obtained by advancing the pointer to the next entry of A. Since we want to determine the longest subsequence, the maximum of these two must be selected.

The sequential implementation of this DP formulation computes the values in table F in row-major order. Since there is a constant amount of computation at each entry in the table, the overall complexity of this algorithm is Θ(nm). This DP formulation is nonserial monadic, as illustrated in Figure 12.5(a). Treating nodes along a diagonal as belonging to one level, each node depends on two subproblems at the preceding level and one subproblem two levels earlier. The formulation is monadic because a solution to any subproblem at a level is a function of only one of the solutions at preceding levels. (Note that, for the third case in Equation 12.5, both F [i, j − 1] and F [i − 1, j] are possible solutions to F [i, j], and the optimal solution to F [i, j] is the maximum of the two.) Figure 12.5 shows that this problem has a very regular structure.

Figure 12.5. (a) Computing entries of table F for the longest-common-subsequence problem. Computation proceeds along the dotted diagonal lines. (b) Mapping elements of the table to processing elements.

Example 12.2 Computing LCS of two amino-acid sequences

Let us consider the LCS of two amino-acid sequences H E A G A W G H E E and P A W H E A E. For the interested reader, the names of the corresponding amino-acids are A: Alanine, E: Glutamic acid, G: Glycine, H: Histidine, P: Proline, and W: Tryptophan. The table of F entries for these two sequences is shown in Figure 12.6. The LCS of the two sequences, as determined by tracing back from the maximum score and enumerating all the matches, is A W H E E. ▪

Figure 12.6. The F table for computing the LCS of sequences H E A G A W G H E E and P A W H E A E.

To simplify the discussion, we discuss parallel formulation only for the case in which n = m. Consider a parallel formulation of this algorithm on a CREW PRAM with n processing elements. Each processing element P_i computes the i^th column of table F. Table entries are computed in a diagonal sweep from the top-left to the bottom-right corner. Since there are n processing elements, and each processing element can access any entry in table F, the elements of each diagonal are computed in constant time (the diagonal can contain at most n elements). Since there are 2n − 1 such diagonals, the algorithm requires Θ(n) iterations. Thus, the parallel run time is Θ(n). The algorithm is cost-optimal, since its Θ(n²) processor-time product equals the sequential complexity.

This algorithm can be adapted to run on a logical linear array of n processing elements by distributing table F among different processing elements. Note that this logical topology can be mapped to a variety of physical architectures using embedding techniques in Section 2.7.1. Processing element P_i stores the (i + 1)th column of the table. Entries in table F are assigned to processing elements as illustrated in Figure 12.5(b). When computing the value of F [i, j], processing element P_{j −1} may need either the value of F [i − 1, j − 1] or the value of F [i, j − 1] from the processing element to its left. It takes time t_s + t_w to communicate a single word from a neighboring processing element. To compute each entry in the table, a processing element needs a single value from its immediate neighbor, followed by the actual computation, which takes time t_c. Since each processing element computes a single entry on the diagonal, each iteration takes time (t_s + t_w + t_c). The algorithm makes (2n − 1) diagonal sweeps (iterations) across the table; thus, the total parallel run time is

Since the sequential run time is n²t_c, the efficiency of this algorithm is

A careful examination of this expression reveals that it is not possible to obtain efficiencies above a certain threshold. To compute this threshold, assume it is possible to communicate values between processing elements instantaneously; that is, t_s = t_w = 0. In this case, the efficiency of the parallel algorithm is

Equation 12.5. 

Thus, the efficiency is bounded above by 0.5. This upper bound holds even if multiple columns are mapped to a processing element. Higher efficiencies are possible using alternate mappings (Problem 12.3).

Note that the basic characteristic that allows efficient parallel formulations of this algorithm is that table F can be partitioned so computing each element requires data only from neighboring processing elements. In other words, the algorithm exhibits locality of data access.

Consider a weighted graph G, which consists of a set of nodes V and a set of edges E. An edge from node i to node j in E has a weight c_{i, j}. Floyd’s algorithm determines the cost d_{i, j} of the shortest path between each pair of nodes (i, j) in V (Section 10.4.2). The cost of a path is the sum of the weights of the edges in the path.

Let be the minimum cost of a path from node i to node j, using only nodes v₀, v₁, ..., v_k−1. The functional equation of the DP formulation for this problem is

Equation 12.6. 

Since is the shortest path from node i to node j using all n nodes, it is also the cost of the overall shortest path between nodes i and j . The sequential formulation of this algorithm requires n iterations, and each iteration requires time Θ(n²). Thus, the overall run time of the sequential algorithm is Θ(n³).

Equation 12.6 is a serial polyadic formulation. Nodes can be partitioned into n levels, one for each value of k. Elements at level k + 1 depend only on elements at level k. Hence, the formulation is serial. The formulation is polyadic since one of the solutions to requires a composition of solutions to two subproblems and from the previous level. Furthermore, the dependencies between levels are sparse because the computation of each element in requires only three results from the preceding level (out of n²).

A simple CREW PRAM formulation of this algorithm uses n² processing elements. Processing elements are organized into a logical two-dimensional array in which processing element P_i,j computes the value of for k = 1, 2, ..., n. In each iteration k, processing element P_i,j requires the values , , and . Given these values, it computes the value of in constant time. Therefore, the PRAM formulation has a parallel run time of Θ(n). This formulation is cost-optimal because its processor-time product is the same as the sequential run time of Θ(n³). This algorithm can be adapted to various practical architectures to yield efficient parallel formulations (Section 10.4.2).

As with serial monadic formulations, data locality is of prime importance in serial polyadic formulations since many such formulations have sparse connectivity between levels.

Consider the problem of multiplying n matrices, A₁, A₂, ..., A_n, where each A_i is a matrix with r_{i −1} rows and r_i columns. The order in which the matrices are multiplied has a significant impact on the total number of operations required to evaluate the product.

The objective of the parenthesization problem is to determine a parenthesization that minimizes the number of operations. Enumerating all possible parenthesizations is not feasible since there are exponentially many of them.

Let C [i, j] be the optimal cost of multiplying the matrices A_i ,..., A_j. This chain of matrices can be expressed as a product of two smaller chains, A_i, A_i +1,..., A_k and A_k+1 ,..., A_j. The chain A_i, A_{i +1} ,..., A_k results in a matrix of dimensions r_{i −1} × r_k, and the chain A_k+1 ,..., A_j results in a matrix of dimensions r_k × r_j. The cost of multiplying these two matrices is r_{i −1}r_k r_j. Hence, the cost of the parenthesization (A_i, A_i +1 ,..., A_k)( A_k+1 ,..., A_j) is given by C [i, k] + C [k + 1, j] + r_{i −1}r_k r_j. This gives rise to the following recurrence relation for the parenthesization problem:

Equation 12.7. 

Given Equation 12.7, the problem reduces to finding the value of C [1, n]. The composition of costs of matrix chains is shown in Figure 12.7. Equation 12.7 can be solved if we use a bottom-up approach for constructing the table C that stores the values C [i, j]. The algorithm fills table C in an order corresponding to solving the parenthesization problem on matrix chains of increasing length. Visualize this by thinking of filling in the table diagonally (Figure 12.8). Entries in diagonal l corresponds to the cost of multiplying matrix chains of length l + 1. From Equation 12.7, we can see that the value of C [i, j] is computed as min{C [i, k]+C [k +1, j]+r_{i −1}r_k r_j}, where k can take values from i to j −1. Therefore, computing C [i, j] requires that we evaluate (j − i) terms and select their minimum. The computation of each term takes time t_c, and the computation of C [i, j] takes time (j − i)t_c. Thus, each entry in diagonal l can be computed in time lt_c.

Figure 12.7. A nonserial polyadic DP formulation for finding an optimal matrix parenthesization for a chain of four matrices. A square node represents the optimal cost of multiplying a matrix chain. A circle node represents a possible parenthesization.

Figure 12.8. The diagonal order of computation for the optimal matrix-parenthesization problem.

In computing the cost of the optimal parenthesization sequence, the algorithm computes (n − 1) chains of length two. This takes time (n − 1)t_c. Similarly, computing (n − 2) chains of length three takes time (n − 2)2t_c. In the final step, the algorithm computes one chain of length n. This takes time (n − 1)t_c. Thus, the sequential run time of this algorithm is

Equation 12.8. 

The sequential complexity of the algorithm is Θ(n³).

Consider the parallel formulation of this algorithm on a logical ring of n processing elements. In step l, each processing element computes a single element belonging to the l^th diagonal. Processing element P_i computes the (i + 1)th column of Table C. Figure 12.8 illustrates the partitioning of the table among different processing elements. After computing the assigned value of the element in table C, each processing element sends its value to all other processing elements using an all-to-all broadcast (Section 4.2). Therefore, the assigned value in the next iteration can be computed locally. Computing an entry in table C during iteration l takes time lt_c because it corresponds to the cost of multiplying a chain of length l + 1. An all-to-all broadcast of a single word on n processing elements takes time t_s log n + t_w(n − 1) (Section 4.2). The total time required to compute the entries along diagonal l is lt_c + t_s log n + t_w(n − 1). The parallel run time is the sum of the time taken over computation of n − 1 diagonals.

The parallel run time of this algorithm is Θ(n²). Since the processor-time product is Θ(n³), which is the same as the sequential complexity, this algorithm is cost-optimal.

When using p processing elements (1 ≤ p ≤ n) organized in a logical ring, if there are n nodes in a diagonal, each processing element stores n/p nodes. Each processing element computes the cost C [i, j] of the entries assigned to it. After computation, an all-to-all broadcast sends the solution costs of the subproblems for the most recently computed diagonal to all the other processing elements. Because each processing element has complete information about subproblem costs at preceding diagonals, no other communication is required. The time taken for all-to-all broadcast of n/p words is t_s log p + t_wn(p − 1)/p ≈ t_s log p + t_wn. The time to compute n/p entries of the table in the l^th diagonal is lt_cn/p. The parallel run time is

In order terms, T_P = Θ(n³/p) + Θ(n²). Here, Θ(n³/p) is the computation time, and Θ(n²) the communication time. If n is sufficiently large with respect to p, communication time can be made an arbitrarily small fraction of computation time, yielding linear speedup.

This formulation can use at most Θ(n) processing elements to accomplish the task in time Θ(n²). This time can be improved by pipelining the computation of the cost C [i, j] on n(n + 1)/2 processing elements. Each processing element computes a single entry c(i, j) of matrix C. Pipelining works due to the nonserial nature of the problem. Computation of an entry on a diagonal t does not depend only on the entries on diagonal t − 1 but also on all the earlier diagonals. Hence work on diagonal t can start even before work on diagonal t − 1 is completed.