On maximally parallel schemata
- 1 October 1970
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 1 (02724847) , 32-50
- https://doi.org/10.1109/swat.1970.13
Abstract
A model for parallel computation called a schema is presented. This model is similar to that presented in the recent work of Karp and Miller2. Section 1 presents a description of the model, and some results on the characterization of computations within it. Section 2 summarizes some results on determinacy and equivalence. Section 3 presents a formalization of the property of maximal parallelism in schemata. Several alternate characterizations are shown to be equivalent for certain classes. Section 4 presents results on the complexity of a maximally parallel schema equivalent to a given schema.Keywords
This publication has 9 references indexed in Scilit:
- On formalised computer programsJournal of Computer and System Sciences, 1970
- Parallel program schemataJournal of Computer and System Sciences, 1969
- Properties of Programs and the First-Order Predicate CalculusJournal of the ACM, 1969
- Counter machines and counter languagesTheory of Computing Systems, 1968
- ANALYSIS OF IMPLEMENTATION ERRORS IN DIGITAL COMPUTING SYSTEMSPublished by Defense Technical Information Center (DTIC) ,1968
- Analysis of Programs for Parallel ProcessingIEEE Transactions on Electronic Computers, 1966
- Programming semantics for multiprogrammed computationsCommunications of the ACM, 1966
- A multiprocessor system designPublished by Association for Computing Machinery (ACM) ,1963
- Parallel ProgrammingThe Computer Journal, 1958