A Comparison of Some Theoretical Models of Parallel Computation
- 1 August 1973
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-22 (8) , 710-717
- https://doi.org/10.1109/tc.1973.5009149
Abstract
In this paper we briefly describe and compare a number of theoretical models for parallel computation; namely, Petri nets, computation graphs, and parallel program schemata. We discuss various problems and properties of parallel computation that can be studied within these formulations and indicate the ties between these properties and the more practical aspects of parallel computation. We show how marked graphs, a particular type of Petri net, are a restricted type of computation graph and indicate how some results of marked graphs can be obtained from known results of computation graphs. Also, for schemata we discuss the decidability versus undecidability of various properties and several techniques of schemata composition.Keywords
This publication has 47 references indexed in Scilit:
- Marked directed graphsJournal of Computer and System Sciences, 1971
- The impact of future developments in computer technologyComputers & Structures, 1971
- Legality and Other Properties of Graph Models of ComputationsJournal of the ACM, 1970
- Scheduling Parallel ComputationsJournal of the ACM, 1968
- The Organization of Computations for Uniform Recurrence EquationsJournal of the ACM, 1967
- Models of Computations and Systems—Evaluation of Vertex Probabilities in Graph Models of ComputationsJournal of the ACM, 1967
- Additional comments on a problem in concurrent programming controlCommunications of the ACM, 1966
- Large Parallel ComputersJournal of the ACM, 1966
- Solution of a problem in concurrent programming controlCommunications of the ACM, 1965
- Parallel ProgrammingThe Computer Journal, 1958