Towards an Architecture-Independent Analysis of Parallel Algorithms

Christos H. Papadimitriou, Mihalis YannakakisSIAM Journal on Computing 1990 · OpenReview

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...

Figure