Conversion from data-driven to synchronous execution in loop programs

ABSTRACT

Conversion algorithms are presented that would enable programmers to write programs in a high-level, data flow language and then run those programs on a synchronous machine. A model of interprocess communication systems is developed in which both data-driven and synchronous execution modes are represented. Balancing equations are used to characterize a subclass of parallel programs, called loop programs, for which conversions are possible. We show that all loop programs having the finite buffer property can be converted into synchronous mode. Finally two algorithms for the conversion of loop programs are presented and discussed.

REFERENCES

• 1: BAILEY, D. A., CUNY, J. E., AND MACLEOo, B.B. Coordination in the Poker Parallel Programming Environment: A parallel code optimization. Tech. Rep. 85-21, University of Massachusetts, Amherst, Aug. 1985.
• 2: CUNY, J. E., AND SNYDER, L. Testing the coordination predicate. IEEE Trans. Comput. 33, 3 (Mar. 1984), 201-208.
• 3: GANNON, D., SNYDER, L., AND VAN ROSENDALE, J. Programming substructure computations for elliptic problems on the CHiP computer. In Impact o{ New Computing Systems on Computational Mechanics, A. K. Noor (Ed.), American Society of Mechanical Engineers, 1983.
• 4: KARP, R., AND MILLER, R.E. Parallel program schemata. J. Comput. Syst. Sci. 3 (May 1969), 147-195.
• 5: James L. Peterson, Petri Nets, ACM Computing Surveys (CSUR), v.9 n.3, p.223-252, Sept. 1977 [doi>10.1145/356698.356702]
• 6: CUNY, g. E., AND SNYDER, L. A model for analyzing generalized interprocessor communication system. In AlgorithmicaUy-specialized Computers, L. Snyder, L. Jamieson, H. Siegel, and D. Gannon (Eds.), 1985, pp. 7-16.
• 7: KARP, R. M., AND MILLER, R.E. Properties of a model for parallel computations: Determinacy, termination and queuing. SIAMJ. Appl. Math. 14 (Nov. 1966), 1390-1411.
• 8: KuNa, H. T., ANO LEISERSON, C.E. Systolic arrays (for VLSI). Tech. Rep. CS-79-103, Carnegie- Mellon University, Pittsburgh, Pa., 1979.
• 9: LEISERSON, C. E., ANO SAXE, J.B. Optimizing synchronous system. In Proceedings o{ the 22nd Symposium on the Foundations of Computer Science. IEEE, New York (1981), pp. 23-36.
• 10: Janice E. Cuny , Lawrence Snyder, Compilation of data-driven programs for synchronous execution, Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.197-202, January 24-26, 1983, Austin, Texas [doi>10.1145/567067.567087]
• 11: DENNIS, J. B., AND RONO, G.G. Maximum pipelining of array operations on static data flow machine. In Proceedings of the 1983 International Conference on Parallel Processing. IEEE, New York, 1983, pp. 331-334.
• 12: RON(~, G.G. Pipelined mapping of homogeneous data flow programs. In Proceedings of the 1984 International Conference on Parallel Processing. IEEE, New York, 1984, pp. 532-534.
• 13: SNYDER, L. Parallel programming and the Poker Programming Environment. Computer 17, 7 (1984), 27-37.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Multiple-instruction-stream, multiple-data-stream processors (MIMD)

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Parallel processors**
      C.1.3 Other Architecture Styles
          Subjects: Data-flow architectures; Adaptable architectures

  D. Software
  D.3 PROGRAMMING LANGUAGES
  D.4 OPERATING SYSTEMS

General Terms:
Algorithms, Languages, Performance