Towards an Architecture-Independent Analysis of Parallel Algorithms
- 1 April 1990
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 19 (2) , 322-328
- https://doi.org/10.1137/0219021
Abstract
A simple and efficient method for evaluating the performance of an algorithm, rendered as a directed acyclic graph, on any parallel computer is presented. The crucial ingredient is an efficient approximation algorithm for a particular scheduling problem. The only parameter of the parallel computer needed by our method is the message-to-instruction ratio $\tau$. Although the method used in this paper does not take into account the number of processors available, its application to several common algorithms shows that it is surprisingly accurate.
Keywords
This publication has 1 reference indexed in Scilit:
- A Communication-Time TradeoffSIAM Journal on Computing, 1987