Models of parallel computation: A survey and synthesis

B. M. Maggs, L. R. Matheson, R. E. Tarjan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

53 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 28th Annual Hawaii International Conference on System Sciences, HICSS 1995
PublisherIEEE Computer Society
Pages61-70
Number of pages10
ISBN (Electronic)0818669306
DOIs
StatePublished - 1995
Event28th Annual Hawaii International Conference on System Sciences, HICSS 1995 - Wailea, United States
Duration: Jan 3 1995Jan 6 1995

Publication series

NameProceedings of the Annual Hawaii International Conference on System Sciences
Volume2
ISSN (Print)1530-1605

Conference

Conference28th Annual Hawaii International Conference on System Sciences, HICSS 1995
Country/TerritoryUnited States
CityWailea
Period1/3/951/6/95

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint

Dive into the research topics of 'Models of parallel computation: A survey and synthesis'. Together they form a unique fingerprint.

Cite this