Models of parallel computation: A survey and synthesis

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.