Towards an Architecture-Independent Analysis of Parallel Algorithms
Lists
Only you see this
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.
BibTeX
@article{papadimitriou1990towards,
author = {Christos H. Papadimitriou and Mihalis Yannakakis},
title = {{Towards an Architecture-Independent Analysis of Parallel Algorithms}},
journal = {SIAM Journal on Computing},
year = {1990},
url = {https://openreview.net/forum?id=xN2FZfPNdl},
}Loading related content...