Program schemas with concurrency: execution time and hangups

ABSTRACT

A class of program schemas with concurrency is defined as a natural extension of the standard notion of sequential flow-chart-like schemas. The question is considered as to whether such a program schema may reach a premature termination (or "hangup") for some interpretation. It is shown that in general this question is undecidable; however, it is shown to be decidable for the class of free program schemas. And an algorithm for testing this property is presented with an upper time bound that grows linearly with the size of the schema.Several structural properties are shown to be equivalent to the hangup-free conditon for free schemas. And we give a method for computing the expected execution time of a program schema if the expected frequencies of choices at the branch points are known.

REFERENCES

• 1: Robert M. Keller, Parallel Program Schemata and Maximal Parallelism II: Construction of Closures, Journal of the ACM (JACM), v.20 n.4, p.696-710, Oct. 1973 [doi>10.1145/321784.321795]
• 2: H. S. Stone, Problems of parallel computation. Complexity of Sequential and Parallel Numerical Algorithms. Ed. J. F. Traub, Academic Press, New York, 1973.
• 3: H. S. Stone, Parallel processing with perfect shuffle. IEEE Transactions on Computers, Vol. C-20, No. 2, pp 153-161 (February 1971).
• 4: D. C. Luckham, D. M. R. Park, M. S. Paterson, On formalized computation programs. Journal of Computer and System Sciences: 4, pp 220-249 (1970).
• 5: Z. Manna, Program schemas. Currents in the Theory of Computing, Ed. A. V. Aho, Prentice-Hall, Englewood Cliffs, N.J., pp 90-142 (1973).
• 6: M. E. Conway, A multiprocessor system design. Proceedings of AFIPS Conference 24, pp 139-146 (1963).
• 7: R. M. Karp and R. E. Miller, Parallel program schemata. Journal of Computer and System Sciences: 3 pp 147-195, (May 1969).
• 8: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 9: Narsingh Deo, Graph Theory with Applications to Engineering and Computer Science (Prentice Hall Series in Automatic Computation), Prentice-Hall, Inc., Upper Saddle River, NJ, 1974
• 10: B. P. Lester, The Balance Property of Parallel Computations, Ph.D. Thesis, Project MAC, Dept. of Electrical Engineering, Massachusetts Institute of Technology, Cambridge, Mass. (February 1974).
• 11: M. Hack, ANALYSIS OF PRODUCTION SCHEMATA BY PETRI NETS, Massachusetts Institute of Technology, Cambridge, MA, 1972
• 12: M. Paterson, Equivalence Problems in a Model of Computation, Ph.D. Thesis, Cambridge University (1967).
• 13: Marvin Schaefer, A mathematical theory of global program optimization (Prentice-Hall series in automatic computation), Prentice-Hall, Inc., Upper Saddle River, NJ, 1973
• 14: D. E. Martin and G. Estrin, Models of computational systems - cyclic to acylic graph transformations, IEEE Transactions on Electronic Computers, Vol. EC-16, No. 1, pp 70-79 (February 1967).