On the computation and communication tradeoffs and their impact on the performance of asynchronous multiprocessor systems
Vijay K. Naik, Merrell L. Patrick · 1988
A major issue in parallel processing is how to distribute the computational work of solving a problem while keeping the cost of communication small. Inherent in many algorithms, there is a close relationship between the extractable parallelism and the associated communication requirements. The topic of this dissertation is to systematically analyze a certain class of such algorithms for asynchronous multiprocessor systems. The data dependencies of an algorithm are represented by a directed acyclic graph (DAG). Three classes of uniform DAGs are considered. These are: a diamond DAG, a generic rectangular DAG, and three and higher dimensional cubes. Lower bounds on the computation time, t, and the associated data traffic, $\tau$, are given. For an $n$ x $n$ diamond DAG, $t\cdot\tau$ is shown to be $\Omega (n\sp3)$, independent of the number of processors used. This result is similar to that of Papadimitriou and Ullman (1987). The effects on the lower bound are discussed when a constant number of data dependencies are added at each vertex. For an $n\sb1$ x $n\sb2$ rectangular DAG, $n\sb1\leq n\sb2$, $t\cdot\tau$ is $\Omega(n\sbsp{1}{2}\cdot n\sb2$). For a $d$-dimensional cube $t\cdot\tau\sp{d-1}$ is shown to be $\Omega(n\sp{d\sp2-d+1})$. All of the lower bound results hold even if vertices the DAG are recomputed. The lower bounds given are the best possible in the sense that there are partitioning schemes that meet these bounds. As a consequence of these lower bounds, a tradeoff is shown to exist between the computation time and the associated data traffic. The effect of the tradeoffs on the overall performance is discussed. Partitioning schemes are discussed which compute the problem in the smallest total execution time using an optimum number of processors. The problems of factoring dense and sparse matrices are considered as examples of nonuniform DAGs. Lower bounds on the computation time and the data traffic are established. For factoring an $n$ x $n$ sparse matrix, the data traffic using $p$ processors is shown to be $\Omega(n\cdot\sqrt{p})$. A partitioning scheme with the minimum data traffic is given and analyzed. The computation time and data traffic tradeoff in two different scheduling schemes is discussed.