%
\documentstyle[12pt,epsf]{book}

\def\ant{}

\headsep=1.2cm
\topmargin=0.0cm
\footskip=1.5cm
\oddsidemargin=0.416cm
\evensidemargin=0.416cm
\textheight=18.33cm
\textwidth=12.5cm
\parskip=\medskipamount
\parindent=0pt
\renewcommand{\footnoterule} {\kern-3pt \hrule width \textwidth \kern 2.6pt}

\pagestyle{headings}
\setcounter{tocdepth}{3}  % 3-subsubsection; 4-paragraph;
                          % 5-subparagraph; 2-subsection(default)

\title{TEMPUS: Activity 2 \\
       Parallel Algorithms \\
       Sorting}
\author{}

\begin{document}

\maketitle

%\chapter {Dynamic Programming}
%--------------------------------------------------------------------
\LARGE

\newpage\addcontentsline{toc}{section}{Sorting Generals}
\section* {Definitions of DP formulation}

\begin{itemize}
\item{\bf Dynamic programming:} consequent way how the problems can be treated
\item{\bf Applications:} discrete optimization problems such as scheduling, string-editing, packaging, and inventory management. 
\item{\bf Basic technique:} Divides it into a set of interdependent
subproblems, solves the subproblems and uses the results to solve larger subproblems until 
the entire problem is solved.
\item{\bf Example:} shortest path problem

\begin{figure}
\centerline{\epsfysize=6cm\epsffile{./figs/graph.eps}}
\caption{Example graph}
\label{graph}
\end{figure}

\item{\bf DP formulation:}recursive equations for $f(x)$:
 
 $$f(x)=\cases{0 & $x=0$\cr
               \min_{0 \leq j < x} \lbrace f(j)+c(j, x)\rbrace & 
               $1 \leq x\leq n-1$ \cr
              }$$

\begin{eqnarray*}
 f(x_6) &=& 0\cr
 f(x_5) &=& \min {\lbrace f(x_4)+c(5,4), c(5,6) \rbrace}\cr
 f(x_4) &=& c(4,6)\cr
 f(x_3) &=& \min {\lbrace f(x_4)+c(3,4), f(x_5) + c(3,5) \rbrace}\cr
 f(x_2) &=& \min {\lbrace f(x_3)+c(2,3), f(x_5) + c(2,5) \rbrace}\cr
 f(x_1) &=& \min {\lbrace f(x_3)+c(1,3), f(x_4) + c(1,4) \rbrace}\cr
 f(x_0) &=& \min {\lbrace f(x_1)+c(0,1), f(x_2) + c(0,2), f(x_3) + c(0, 3) \rbrace}\cr
\end{eqnarray*}

\item {\bf Generally}
If $r$ represents the cost of a solution composed
of subproblems $x_1,x_2,\dots,x_i$ then $r$ can be written as

$$r=g(f(x_1), f(x_2),\dots, f(x_l)).$$

\item{\bf Definitions:}
\begin{itemize}
\item{\it composition function}

DP represents the solution to an optimization problem as a recursive 
equation whose left side is an unknown quantity and whose right side is a
minimization (or maximization) expression. Such an equation is called a 
{\it functional equation} or an { \it optimization equation}.

In the previous equation the composition function $g$ is given by $f(j)+c(j, x)$. 
This function is additive, since it is sum of two terms. In a general 
DP formulation, the cost function need not be additive. 

A functional equation that contains a single
recursive term (for example, $f(j)$ yields a {\it monadic} DP
formulation. For an arbitrary DP formulation, the cost function 
may multiple recursive terms. DP formulations whose cost 
function contains multiple recursive terms are 
called {\it polyadic} formulations.

The dependencies between subproblems in a DP formulation can be represented by a
directed graph. Each node in the graph represents a subproblem. A directed edge 
from node $i$ to node $j$ indicates that the solution
to the subproblem represented by node $i$ is used to compute 
the solution to the subproblem represented by node $j$. If the graph is acyclic,
then the nodes of the graph can be organized into levels such that subproblems
at a particular level depend only on subproblems at previous levels. In this 
case, the DP formulation can be categorized as follows. If subproblems at 
all levels depend only on the results at the immediately preceding levels, 
the formulation is called {\it serial}, in the other, more complicated
cases we call it {\it nonserial} DP formulation.

\begin{figure}
\centerline{\epsfysize=8cm\epsffile{./figs/def1.eps}}
\caption{Serial, polyadic DP formulation }
\label{def1}
\end{figure}

Based on the preceding classification criteria, we define four classes
of DP formulations: 
{\it serial monadic, serial polyadic,  nonserial monadic}, 
and {\it nonserial polyadic}. 
These classes, however, are not exhaustive; 
some DP formulations cannot be classified into any of these categories.

In Fig.\ref{def1} we illustrated how DP defines the problems.
The solution to problem $x_{100}$ 
is the minimum of the three possible solutions having costs $r_1, r_2$, 
and $r_3$. The cost of the first solution is determined by composing solutions to 
subproblems $x_1$ and $x_2$, the second solution by composing solutions 
to subproblems $x_2$ and $x_3$, and the third solution by composing solutions 
to subproblems $x_3$, $x_4$ and $x_5$. However the solutions $x_{100}$
and $x_{101}$ can serve as subproblems solution to another bigger
problem, and cetera, till we found the solution of the main, original problem.

This example is serial DP formulation while 'levels' can be defined
and it recursively uses only the subproblems of the preceding levels.
On the other side it is polyadic, while in the composition function
more than one subproblems appear.


We can cover a wide variety of problems by DP approach, 
that is why it is difficult to find generic parallel algorithms for
them.
In the forthcoming sections we systematically go through the different
classes of DP and discuss parallel DP formulations for sample problems 
in each class.
 
\section* {Serial Monadic DP Formulations}
 
Two representative problems of serial monadic DP formulation is 
discussed in this chapter  section discusses the shortest-path problem
for a multistage graph and the 0/1 knapsack problem. 
The former is already treated in the Graph Algorithms chapter.
 
 \subsection {The Shortest-Path Problem}

A multistage graph of $r+1$ levels is a graph where the nodes are
arranged in levels, as shown in Fig.\ref{dyna1}. 
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$.

\begin{figure}
\centerline{\epsfysize=8cm\epsffile{./figs/dyna1.eps}}
\caption{}
\label{dyna1}
\end{figure}

The $i^{th}$ node at level $l$ in the graph is labeled $v^{l}_{i}$.
The cost of an edge connecting $v^{l}_{i}$ to node $v^{l+1}_{j}$ is labeled $c^{l}_{i,j}$.

The (minimal) cost of reaching the goal node $R$ from any node $v^{l}_{i}$ is 
represented by $C^{l}_{i}$. If there are $n$ nodes at level $l$, the vector 
${\lbrack C^{l}_{1},\dots ,C^{l}_{n-1}\rbrack}^T$ is referred to as
${\bf C}^l$.

The objective of this problem is to find the shortest path from $S$ to
$R$.
We can use one of the general algorithm explained in the Graph
Algorithms chapter, but we give here another formulation with DP which
extensively exploits the special structure (i.e. levels) of the graph.

Hence, the shortest-path problem reduces to computing ${\bf C}^0$. Since the graph 
has only one starting node, ${\bf C}^0=\lbrack{C^0_0}\rbrack $. The structure 
of the graph is such that any path from $v^l_i$ to $R$ includes a node 
 ${V^{l+1}_j} (0\leq j\leq n-1)$. 

Quite similarly to the example what we have seen in the first section,
the cost of any such path is the sum of the cost of the path between 
$v^l_i$ and $v^{l+1}_j$ and the cost of the shortest path between 
$v^{l+1}_j$ and $R$ (which is given by $C^{l+1}_j$). 

Thus, $C^l_i$, the cost of the shortest path between 
$v^l_i$ and $R$, is equal to the minimum cost over all paths through each 
node in level $l+1$. Therefore,
  
  $$C^l_i=\min \{ (c^l_{i,j}+C^{l+1}_j)\mid
                  j {\rm\ is\ a\ node\ at\ level\ } {l+1}\} .$$
  
In the special case when $ l=r-1$, all nodes $v^{r-1}_j$ 
have only one edge connecting them to the goal
node $R$ at level $r$, the cost $C^{r-1}_j$ is equal to $c^{r-1}_{j,R}$,
which implies
 
$${\bf C}^{r-1}=\lbrack c^{r-1}_{0,R}, c^{r-1}_{1,R},\dots ,c^{r-1}_{n-1,R}\rbrack .$$

The recursive equation 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

\begin{eqnarray*}
C^l_0     &=& \min\lbrace (c^l_{1,0}+C^{l+1}_0), (c^l_{0,1}+C^{l+1}_1),
               (c^l_{1,n-1}+C^{l+1}_{n-1})\rbrace,\\
C^l_1     &=& \min\lbrace (c^l_{1,0}+C^{l+1}_0), (c^l_{1,1}+C^{l+1}_1),
               (c^l_{1,n-1}+C^{l+1}_{m-1})\rbrace,\\
\vdots    &=& \vdots\\
C^l_{n-1} &=& \min\lbrace (c^l_{n-1,0}+C^{l+1}_0), (c^l_{n-1,1}+C^{l+1}_1),
               (c^l_{n-1,n-1}+C^{l+!}_{n-1})\rbrace.
\end{eqnarray*}


We can consider the operation of multiplying a matrix with a vector.
For that purpose we have to replace the addition operation by minimization and 
the multiplication operation by addition. The former set of equations
can be written as

$${\bf C}^l = M_{l,l+1}\times {\bf C}^{l+1},$$

\noindent
where ${\bf C}^l$ and ${\bf C}^{l+1}$ are $n\times 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\times 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

$$M_{l,l+1}=\left[\matrix{
                            c^l_{0.0}& c^l_{0,1}&\ldots& c^l_{0,n-1}\cr
                            c^l_{1.0}& c^l_{1,1}\ldots& c^l_{1,n-1}\cr
                            \vdots& \vdots& \vdots\cr
                            c^l_{n-1,0}& c^l_{n-1,1}& \ldots& c^l_{n-1,n-1}\cr
                         }
            \right]
$$

The shortest path problem has thus been reformulated as a sequence of matrix-
vector multiplications. 
In a sequential algorithm we compute first ${\bf C}^{r-1}$ while it is
obvious as we have seen it, and then recursively compute the
${\bf C}^{r-2}, {\bf C}^{r-3},\dots, {\bf C}^1$ by using the previous matrix equation. 
Finally, ${\bf C}^0$ is computed using our defining recursive equation.

Since there are $n$ nodes at each level, the cost of computing each vector
${\bf C}^l$ is $O (n^2)$.
The parallel algorithm for this problem can be derived using the parallel 
algorithms for the matrix-vector product discussed in the Numerical
Algorithms chapter.

For example, on a mesh, $O (n)$ processors can compute each vector
${\bf C}^l$ in $O (n)$ 
time and solve the entire problem in $O (rn)$ time.
 
This example can serve as a general template for many serial monadic DP
problems. The serial and monadic feature assures us to have a
dependency graph structure which yields to this matrix formulation.
However there are cases when this approach is not effective while, for
example the formulation produces a sparse matrix. In such cases other
parallel algorithmic methods (e.g. for sparse matrices) have to be applied.  
 
\subsection{The 0/1 Knapsack Problem}

\noindent
The well known one-dimensional 0/1 knapsack problem is a problem of a
tourist who wants to pack the most useful objects in his bag, but of
course the capacity of the bag is limited. To be more formal,
let be the capacity of the knapsack $c$ and a set of $n$ objects numbered 
$1, 2, \dots ,n$. Each object $i$ has weight $w_i$ and profit $p_i$. Object
profits and weights are integers. Let $v=\lbrack v_1, v_2, \dots , v_n\rbrack $
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
 
 $$\sum_{i=1}^{n} w_iv_i\leq c$$
 
 \noindent
 (that is, the object fit into the knapsack) and
 
 $$\sum_{i=1}^{n} p_iv_i$$
 
 \noindent
 is maximized (that is, the profit is maximized).
 
 The first idea could be to solve this problem is to consider all $2^n$
 possible subsets of the $n$ objects and choose the one that fits into the knapsack
 and maximizes the profit. It leads, of course, in practical cases to
 a non computable problem due to the huge number of combinatorial
 cases.

 Here we provide a DP formulation that is faster than
 the simple method when $c=O(2^n/n)$. Let $F\lbrack i, x\rbrack $ be the 
 maximum profit for a knapsack of capacity $x$ using only objects
 $\lbrace 1,2,\dots ,i\rbrace $. Then $F\lbrack n, c\rbrack $ 
 is the solution to the problem. The DP formulation for this problem 
 is as follows:
 
 $$F\lbrack i, x\rbrack =\cases{
                                 0 & $x\geq 0,i=0$\cr
                                 -\inf & $x<0,i=0$\cr
                                 \max_{1\leq i\leq n}\lbrace F\lbrack
                                   i-1,x\rbrack,(F\lbrack i-1,
                                   x-w_i\rbrack + P-i)\rbrace
                                   & $1\leq i\leq n$\cr
 }$$

This recursive equations 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:

\begin{itemize}
\item{} the object is not included, 
 knapsack capacity remains $x$, and profit is unchanged;
\item{} the object is included,
 knapsack capacity becomes $x-w_i$, and profit increases by $p_i$. 
\end{itemize}

The DP algorithm decides whether or not to include an object based 
on which choice leads to maximum profit.

\begin{figure}
\centerline{\epsfysize=8cm\epsffile{./figs/dyna2.eps}}
\caption{}
\label{dyna2}
\end{figure}

The sequential algorithm for this DP formulation maintains a table $F$ of size 
$n\times c$. (See Fig.\ref{dyna2}.)
The table contains all $F\lbrack i, j\rbrack$ value. We exploit here
that the possible weights are integers ranging from 0 1 to the
capacity $c$. The first (bottom) row belong to the case when only the
first object is selected.
The algorithm first determines the maximum profit by using the first object with 
knapsacks of different capacities. 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\lbrack i, j\rbrack $ requires $F\lbrack i-1, j\rbrack $
and $F\lbrack i-1, j-w_i\rbrack $. This is depicted in Fig.\ref{dyna2}.

Obviously, Computing each entry takes constant time (less than $c$
steps), so the sequential run time of this algorithm is $O (nc)$.
 
It is trivial, that this formulation is a serial,
while the subproblems $F\lbrack i, x\rbrack $ are organized 
into $n$ levels for $i=1, 2, \dots , n$.
Computation of problems in level $i$ depends only on the subproblems
at level $i-1$. The formulation
is monadic because each of the two alternate solutions of 
$F\lbrack i, x\rbrack $ depend on only one subproblem, namely the 
$F\lbrack i-1, x\rbrack$ function, where x is the variable of the
function. 

Let us use CREW PRAM model for the parallel formulation of this algorithm 
with processors labeled $P_0$ to $P_{c-1}$.

Processor $P_{r-1}$ 
computes the $r^{th}$ column of matrix $F$. When computing
$F\lbrack j, r\rbrack $ during iteration $j$, processor $P_{r-1}$
require the values $F\lbrack j-1, r\rbrack $ and $F\lbrack j-1, r-w_i\rbrack $.
Processor $P_{r-1}$ can read any element of matrix $F$ in constant time, 
so computing $F\lbrack j, r\rbrack $ also requires constant time. Therefore,
each iteration takes constant time. Since there are $n$ iteration, the parallel 
run time is $O (n)$. The formulation uses $c$ processors, hence, 
its processor-time product is $O (nc)$. Therefore, the algorithm is 
cost-optimal.

If we use a hypercube architecture the formulation is (generally) not
cost optimal.
Let us consider $c$-processor hypercube. Table $F$
is distributed among the processors so that each processor is responsible for one
column. We have depicted the the mapping on the Fig.\ref{dyna2}.

Each processor locally 
stores the weights and profits of all objects. In the $j^{th}$
iteration, for computing $F\lbrack j, r\rbrack $ at processor $P_{r-1},\ 
F\lbrack j-1, r\rbrack $ is available locally but $F\lbrack j-1, r-w_j\rbrack $
must be fetched from another processor. This circular $w_j$-shift
operation described
in the Fundamentals chapter. The time taken by a circular
shift operation on a hypercube with cut-through routing has an upper bound of 
$(t_s+t_w+t_h\log c)$ (since only one word is being shifted). If the sum and 
maximization operations take time $t_c$, then each iteration takes time
$t_c+t_s+t_w+t_h\log c$. Because 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 a $p$-processor hypercube, each processor computes $c/p$
elements of the table. In the $j^{th}$ iteration, processor $P_0$ 
computes the values of elements 
$F\lbrack j, 1\rbrack ,\dots , F\lbrack j, c/p\rbrack $, processor $P_1$ computes
values of elements $F\lbrack j, c/p+1, \dots , F\lbrack j, 2c/p\rbrack $, and so on.
Computing the value of $F\lbrack j, k\rbrack $, for any $k$, requires 
values $F\lbrack j-1, k\rbrack $ and $F\lbrack -1, k-w_j\rbrack $.
Required values of the $F$ table can be fetched from remote processors 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 processors. The time for this operation is at 
most $(2t_s+t_wc/p+2t_h\log p)$. Since each processor
computes $c/p$ such elements, the total time taken by a processor for each iteration
is $t_cc/p+2t_s+t_wc/p+2t_h\log p$. Therefore, the parallel run time of the algorithm
for $n$ iterations is $n(t_cc/p+2t_s+t_wc/p\log p)$. In asymptotic terms, this
algorithm's parallel run time is $O(nc/p+n\log p)$. Its processor-time product is
$O(nc+np\log p)$, which cost-optimal for $c=\Omega (p\log p)$.

There is an upper bound on the efficiency of this formulation. The reason
is that the amount of data that needs to be communicated is of the same order as the
amount of computation at each processor. This upper bound is determined by the values 
of $t_w$ and $t_c$. Mapping this parallel algorithm onto a mesh results
in a non-cost-optimal formulation.


\section* {Nonserial Monadic DP Formulations}

\noindent
The DP algorithm for determining the longest common subsequence of two given sequences
can be formulated as a nonserial monadic DP formulation.
 

\subsection{The Longest-Common-Subsequence Problem}

\noindent
Given  two sequence $A=\langle a_1, a_2, \dots , a_n\rangle $, 
and  $b=\langle a'_1, a'_2, \dots , a'_k\rangle $. We call $B$ a
subsequence of $A$
if we can produce $B$ by deleting entries from $A$.
The Fig\ref{subseq} shows an example:
$\langle a, b, z\rangle $ is a 
subsequence of $\langle c, a, d, b, r, z\rangle $, but $\langle a, c, z\rangle $ and
$\langle a, d, l\rangle $ are not. The {\it longest-common-subsequence}
(LCS) problem can be stated as follows. Given two sequences $A=\langle a_1, a_2,
\dots , a_n\rangle $ and $B=\langle b_1, b_2, \dots , b_m\rangle $,
find the longest sequence that is a subsequence of both $A$ and $B$. For 
example, if $A=\langle c, a, d, b, r, z\rangle $ and $B=\langle a, s, b, z\rangle $,
the longest common subsequence of $A$ and $B$ is $\langle a, b, z\rangle $.

\begin{figure}
\centerline{\epsfysize=8cm\epsffile{./figs/subseq.eps}}
\caption{Examples for subsequence, longest--common--subsequence}
\label{subseq}
\end{figure}


Let $F\lbrack i, j\rbrack $ 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\lbrack n, m\rbrack $. The DP formulation for 
this problem expresses $F\lbrack i, j\rbrack $ in terms of $F\lbrack i-1, j-1,
F\lbrack i, j-1\rbrack $, and $F\lbrack i-1, j\rbrack $ as follows:

$$F\lbrack i, j\rbrack =\cases{
0& if $i=0$ or $j=0$\cr
F\lbrack i-1, j-1\rbrack +1& if $i, j>0$ and $x_i=y_j$\cr
\max\lbrace F\lbrack i, j-1\rbrack, F\lbrack i-1, j\rbrack\rbrace & if $i, j>0$
and $x_i\neq y_j$\cr
}$$

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
$O (nm)$. This DP formulation is nonserial monadic, as illustrated in Fig.\ref{dyna3}
9.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 
in the recursive definition both $F\lbrack i  j-1\rbrack $ and $F\lbrack i-1\rbrack $ are 
possible solutions to $F\lbrack i, j\rbrack $, and the optimal  solution to 
$F\lbrack i, j\rbrack $ is the maximum of the two.) Fig.\ref{dyna3} shows that this
problem has a very regular structure.

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$ processors. Each processor $P_i$ computes the $i^{th}$ column of table $F$.
Table entries are computed on a diagonal sweep from the top-left to the bottom-right
corner. Since there are  $n$ processors, and each processor 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 $O (n)$ iterations. Thus, the parallel 
run time is $O (n)$. The algorithm is cost-optimal, since its $O 
(n^2)$ processor-time product equals the sequential complexity.


\begin{figure}
\centerline{\epsfysize=8.2cm\epsffile{./figs/dyna3.eps}}
\caption{}
\label{dyna3}
\end{figure}

This algorithm can be adapted to run on a linear array of $n$ processors by distributing
table $F$ among different processors. Processor 
$P_i$ stores the $(i+1)^{\ant st}$ column of the table. Entries in table $F$ are 
assigned to processors as illustrated in Fig.\ref{dyna33}. When computing the value of 
$F\lbrack i, j\rbrack $, processor $P_{j-1}$ may need either the value of 
$F\lbrack i-1, j-1\rbrack $ or the value of $F\lbrack i, j-1\rbrack $ from the
processor to its left. It takes time $t_s+t_w$ to communicate a single
word from a neighboring processor. To compute each entry in the table, 
a processor needs a single value from its immediate neighbor, followed by the actual
computation, which takes time $t_c$. Since each processor computes a single
entry on the diagonal, each iteration takes time $(t_s+t_w+t_c)$. 
The algorithm makes $(2m-1)$ diagonal sweeps (iterations) across the 
table; thus, the total parallel run time is 

$$T_p=(2n-1)(t_s+t_w+t_c).$$

\noindent
Since the sequential run time is $n^2t_c$, the efficiency of this algorithm is 

$$E={n^2t_c\over n(2n-1)(t_s+t_w+t_c)}.$$

\begin{figure}
\centerline{\epsfysize=8cm\epsffile{./figs/dyna33.eps}}
\caption{}
\label{dyna33}
\end{figure}

\noindent]
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 processors instantaneously; that is, $t_s=t_w=0$. In 
this case, the efficiency of the parallel algorithm is 


$$E_{\max }={1\over 2-1/n}.$$

\noindent
Thus, the efficiency is bounded above by 0.5. This upper bound holds even if 
multiple columns are mapped to a processor. Higher efficiencies are possible using 
alternate mappings. Parallel formulations for architectures such as the 
mesh and hypercube only require embedding the ring into the target architecture.

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 processors. In other words, the algorithm
exhibits locality of data access.

\section{Serial Polyadic DP Formulations}

\noindent
In the Graph Algorithms chapter we have investigated the Floyd's
algorithm for determining the shortest paths between  all pairs of nodes 
in a graph. To give an example to serial polyadic DP formulations we
reconsider the problem For basic notation and terminology we refer to
the Graph Algorithms chapter.

\subsection{DP formulation of the Floyd's All-Pairs Shortest-Paths Algorithm}

\noindent
Let $G$ a weighted graph, 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$. The cost of a path is the sum of the weights 
of the edge in the path (see Fig.\ref{floyd}).

\begin{figure}
\centerline{\epsffile{./figs/floyd.eps}}
\caption{All-pairs shortest path}
\label{dyna33}
\end{figure}


For DP formulation we use a several technique to define the recursive
equations like in the previous examples: we consider the 
$V^k =\{v_0, v_1,\dots,v_{k-1}\}$ subset of the node set $V$, and
we will stepwise add the next nodes till we reach the entire node set $V$.

Let $d^k_{i, j}$ be the minimum cost of a path from node $i$ to node $j$, using 
only nodes $V^k$. The functional equation of the DP formulation 
for this problem is 

$$d^k_{i, j}=\cases{
                     c_{i, j} & $k=0$\cr
                     \min\lbrace d^{k-1}_{i, j}, (d^{k-1}_{i, k},
                        +d^{k-1}_{k, j})\rbrace 
                        & $0\leq k\leq n-1$\cr
}$$

Since $d^n_{i, j}$ 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 $O (n^2)$ time.
Thus, the overall run time of the sequential algorithm is $O (n^3)$.

The equation above is a serial  polyadic formulation. Nodes $d^k_{i, j}$ can be partitioned
into $n$ levels, one for each value of $k$. Elements at level $k+1$ depend 
only on element at level $k$. Hence, the formulation is serial. The formulation is 
polyadic since one of the solution to $d_{i, j}^k$ requires a composition of solutions
to two subproblems $d^{k-1}_{i, k}$ and $d^{k-1}_{k, j}$ from 
the previous level. Furthermore, the dependencies between levels are 
sparse because the computation of each element in $d^{k+!}_{i, j}$ requires only
three results from the preceding level (out of $n^2$).

A simple CREW PRAM formulation of this algorithm uses $n^2$ processors. Processors 
are organized into a two-dimensional array in which processor $P_{i, j}$ computes the 
value of $d^k_{i, j}$ for $k=1, 2, \dots , n$. In each iteration $k$, processor 
$P_{i, j}$ requires the values $d^{k-1}_{i, j}, d^{k-1}_{i, k}$, and 
$d^{k-1}_{k, j}$. Given these values, it computes the value of $d^k_{i, j}$
in constant time. Therefore, the PRAM formulation has a parallel run time of 
$O (n)$. This formulation is cost-optimal because its processor-time product is 
the same as the sequential run time of $O (n^3)$. This algorithm 
can be adapted to practical architectures like the hypercube to yield efficient
parallel formulations.

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

\section{Nonserial Polyadic DP Formulations}

\noindent
In nonserial polyadic DP formulations, in addition to processing subproblems 
at a level in parallel, computation can also be pipelined to increase efficiency.
We illustrate this with the optimal matrix-parenthesization problem.

\subsection{The Optimal Matrix-Parenthesization Problem}

\noindent
Consider the problem of multiplying $n$ matrices, $A_1, A_2, \dots , A_n$, 
where each $A_i$ is a matrix with $r_{i-1}$ rows and $r_i$ columns.
(See Fig.\ref{matrix}.)
The order in which 
the matrices are multiplied has a significant impact on the total number of 
operations required to evaluate the product. For example, consider three matrices 
$A_1, A_2$, and $A_3$ of dimensions $10\times 20, 20\times 30$, and $30\times 40$,
respectively. The product of these matrices can be computed as $(A_1\times A_2)
\times A_3$ or as $A_1\times (A_2\times A_3)$. In $(A_1\times A_2)\times A_3$,
computing  $(A_1\times A_2)$ requires $10\times 20\times 30$
operations and yields a matrix of dimensions $10\times 30$. Multiplying this by $A_3$
requires $10\times 30\times 40$ additional operations. Therefore the total number of 
operations is $10\times 20\times 30+10\times 30\times 40=18, 000$. Similarly, computing
$A_1\times (A_2\times A_3)$ requires $20\times 30\times 40+10\times 20\times 40=32, 000$
operations. Clearly, the first parethesization is desirable. The objective of the
parenthesization problem is to determine a parenthesization that minimizes the number 
of operations. Enumerating all possible parenthesizations feasible since there are 
exponentially many of them.

\begin{figure}
\centerline{\epsfysize=10cm\epsffile{./figs/matrix.eps}}
\caption{Multiplying matrices}
\label{matrix}
\end{figure}


In order to formulise the recursive equation let we define $C[i,j]$ 
as the optimal cost of multiplying the matrices $A_i, \dots, A_j$. 
But that chain of matrices can be expressed as a product of 
two subchains i.e. $A_i, A_{i+1}, \dots, A_k$ and $A_{k+1}, \dots, A_j$.
If we multiply the matrices $A_i, \dots,A_k$ we got a matrix with
dimension $r_{i-1}\times r_k$, and multiplying the rest,
$A_{k+1},\dots, A_j$ it results a matrix of dimension $r_k\times r_j$.
Now, if we multiply the resultant matrices we have to perform 
$r_{i-1}\times r_k\times r_j$ operation.
This means if we parenthesize in the form 
$(A_i,\dots,A_k\)\(A_{k+1},\dots, A_j)$ then the corresponding cost
is $C[i,k]+C[k+1,j]+r_{i-1} r_k r_j$.
Considering the optimal parenthesization of the matrices $A_i, \dots,
A_j$ there exists a $k$ index which yield the optimal cost. In order
to find it we have to compute every costs where $i\leq k < j$.
Base on this we can set up the DP recurrence relation in the following
form:

$$C[i,j] =
 \cases { 0 & $j=i, 0 < i \leq n $\cr
          \min_{i\leq k < j} \{ C[i,k]+C[k+1,j]+r_{i-1}r_kr_j \} & $1 \leq i < j \leq n$ \cr
        }
$$


The problem is to find the $C[1,n]$. We set up a table containing the
$C[i, j]$ values. To fill the table we consider first the matrix
parenthetisation problem of length $1$ then length $2$ and so on.
Based on the already filled cells in the table we are able to fill new
cells by using the recirsive equation above. The table is depicted on
the Fig.\ref{dyna4}. Entries in the diagonal $l$ corresponds to the
cost of multiplying matrices of length $l+1$. Let we denote a
computation time of one term by $t_c$.

In computing the cost of the optimal parenthesization sequence the
algorithm computes $(n-1)$ chains of length 2. This takes $(n-1)t_c$
computation time. The next step is to compute the chains having length
3. This takes $(n-2) 3 t_c$ time. At last we have to compute a chain
of length $n$. As a result we set the followin formula:
$$ T_S = t_c ((n-1) + 2(n-2) + \dots + (n-1)1) =
\sum_i=1^{n-1}(n-i)it_c 
$$
which is approx. equal $(n^3/6)t_c$.


\begin{figure}
\centerline{\epsfysize=10cm\epsffile{./figs/dyna4.eps}}
\caption{}
\label{dyna4}
\end{figure}

\end{document}
