Models of parallel computation: A survey and synthesis

Published

Conference Paper

© 1995 IEEE. In the realm of sequential computing, the random access machine has successfully provided an underlying model of computation that has promoted consistency and coordination among algorithm developers, computer architects and language experts. In the realm of parallel computing, however, there has been no similar success. The need for such a unifying parallel model or set of models is heightened by the greater demand for performance and the greater diversity among machines. Yet the modeling of parallel computing still seems to be mired in controversy and chaos. This paper presents a broad range of models of parallel computation and the different roles they serve in algorithm, language and machine design. The objective is to better understand which model characteristics are important to each design community, in order to elucidate the requirements of a unifying paradigm. As an impetus for discussion, we conclude by suggesting a model of parallel computation which is consistent with a model design philosophy that balances simplicity and descriptivity with prescriptivity. Space constraints allow only the presentation of the survey of abstract computational models. It is our hope that the introduction provides insights into the rich array of relevant issues in other disciplines, inspiring the interested reader to examine the full paper.

Full Text

Duke Authors

Cited Authors

  • Maggs, BM; Matheson, LR; Tarjan, RE

Published Date

  • January 1, 1995

Published In

Volume / Issue

  • 2 /

Start / End Page

  • 61 - 70

International Standard Serial Number (ISSN)

  • 1530-1605

International Standard Book Number 10 (ISBN-10)

  • 0818669306

Digital Object Identifier (DOI)

  • 10.1109/HICSS.1995.375476

Citation Source

  • Scopus