Towards an Architecture-Independent Analysis of Parallel Algorithms
Christos H. Papadimitriou, Mihalis Yannakakis · SIAM Journal on Computing · 1990
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.