A complexity theory of efficient parallel algorithms

Clyde P. Kruskal, Larry Rudolph, Marc Snir

Research output: Contribution to journalArticlepeer-review


This paper outlines a theory of parallel algorithms that emphasizes two crucial aspects of parallel computation: speedup the improvement in running time due to parallelism, and efficiency, the ratio of work done by a parallel algorithm to the work done by a sequential algorithm. We define six classes of algorithms in these terms; of particular interest is the class, EP, of algorithms that achieve a polynomial speedup with constant efficiency. The relations between these classes are examined. We investigate the robustness of these classes across various models of parallel computation. To do so, we examine simulations across models where the simulating machine may be smaller than the simulated machine. These simulations are analyzed with respect to their efficiency and to the reduction in the number of processors. We show that a large number of parallel computation models are related via efficient simulations, if a polynomial reduction of the number of processors is allowed. This implies that the classes EP is invariant across all these models. Many open problems motivated by our approch are listed.

Original languageEnglish (US)
Pages (from-to)95-132
Number of pages38
JournalTheoretical Computer Science
Issue number1
StatePublished - Mar 13 1990
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'A complexity theory of efficient parallel algorithms'. Together they form a unique fingerprint.

Cite this