Parallel Program Schemata and Maximal Parallelism I. Fundamental Results

ABSTRACT

The phenomenon of maximal parallelism is investigated in the framework of a class of parallel program schemata. Part I presents the basic properties of this model. Two types of equivalence relation on computations are presented, to each of which there corresponds a concept of determinacy and equivalence for schemata. The correspondence between these relations is shown and related to other properties of schemata. Then the concept of maximal parallelism using one of the relations as a basis is investigated. A partial order on schemata is defined which relates their inherent parallelism. The results presented are especially concerned with schemata which are maximal with respect to this order, i.e. maximally parallel schemata. Several other properties are presented and shown to be equivalent to the property of maximal parallelism. It is then shown that for any schema of a certain class, there exists a unique equivalent schema which is maximally parallel. We call such a schema the “closure” of the original schema.

REFERENCES

• 1: DAvls, M Computability and Unsolvabihty. McGraw-Hall, New York, 1958.
• 2: Jack B. Dennis , Earl C. Van Horn, Programming semantics for multiprogrammed computations, Communications of the ACM, v.9 n.3, p.143-155, March 1966 [doi>10.1145/365230.365252]
• 3: BARRmON, M. Introduction to Switching and Automata Theory. McGraw-Hall, New York, 1965.
• 4: I~ARP, R. M, AND MILLER, R.E. Parallel program schemata J. Comput. Syst. Se~. 8, 2 (May 1969), 147-195.
• 5: I~ELLER, R. M. On maximally parallel schemata. Proc. Eleventh Annual IEEE Symp. on Switching and Automata Theory, Oct 1970, pp. 32-50
• 6: tiELLER, R.M. Closures of parallel program schemata. Ph D. Dlss., Dep. of Elec. Eng. and Comput Sciences, U. of California, Berkeley, Dec. 1970
• 7: KONIG, D. Theorie der Endhchen und Unendhchen Graphen. Akademische Verlagsgesellschaft, Leipzig, 1936.
• 8: LUCKHAM, D. C., PARK, D. M. R., AND PATERSON, M. S. On formalised computer programs. J. Comput. Syst Sci. ~ (June 1970), 220-249.
• 9: LucoNI, F. L. Asynchronous computational structures. Rep. MAC-TR-49 (Thesis), MIT Project MAC, 1968.
• 10: SLUTZ, D. R. The flow graph schemata model of parallel computation. Rep. MAC-TRy53 (Thesis), MIT Project MAC, 1968.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES

General Terms:
Measurement, Performance, Theory, Verification