Mapping fundamental algorithms onto multiprocessor architectures
Chris J. Scheiman · 1994
This dissertation presents two performance measures for algorithms: processor-time-minimality and period-processor-time-minimality. These measures quantify the parallelism of an algorithm. Processor-time-minimality indicates the minimum number of processors that are sufficient to extract the dag's maximum parallelism. Using this measure, tight bounds are proved for a number of fundamental algorithms, represented as directed acyclic graphs (dags): a matrix multiplication algorithm (represented as a rectilinear mesh), a Tensor product algorithm (represented as a 4D cubical mesh), a Gaussian elimination algorithm, and a transitive closure algorithm. Period-processor-time-minimality measures the maximum throughput obtainable when using the minimum number of processing elements that are sufficient to extract the dag's maximum parallelism. Using this measure, tight bounds are proved for a square matrix multiplication algorithm (represented as a cubical mesh).