Compilation of data-driven programs for synchronous execution

ABSTRACT

We present algorithms that convert a class of parallel programs, called loop programs, from data-driven mode to synchronous mode. Such algorithms enable programmers to use a high-level, data-driven programming language without forfeiting the efficiency of a synchronous machine. We characterize loop programs for which conversion is possible in terms of sets of balancing equations and we present two conversion algorithms.

REFERENCES

• 1: E. Arjomandi, M. Fischer, and N. Lynch, A difference in efficiency between synchronous and asynchronous systems, Tech. Rep. #81-0301, University of Washington, 1981.
• 2: J. Cuny and L. Snyder, Conversion from dataflow to synchronous execution in loop programs, Tech. Rep. #CSD-TR-392, Purdue University, 1982.
• 3: J. Cuny and L. Snyder, "Testing coordination for 'homogeneous' parallel algorithms", Proceedings of the 1982 International Conference on Parallel Processing, pp. 265-267, August, 1982.
• 4: J. Cuny and L. Snyder, "A model for analyzing generalized interprocessor communication systems," In Algorithmically-Specialized Computers, D. Gannon, H. Seigel, L Seigel and L. Snyder (eds.), to appear.
• 5: D. Gannon, "Pipelining array computations for MIMD parallelism: A function specification," Proceedings of the 1982 Conference on Parallel Processing, pp. 284-286.
• 6: R. Karp and R. E. Miller, "Properties of a model for parallel computations: determinacy, termination, queuing", SIAM J. Appl. Math. 14, pp. 1390-1411 November, 1966.
• 7: H. T. Kung and C. E. Leiserson, Systolic arrays (for VLSI), Tech. Rep. CMU-CS-79-103, Carnegie-Mellon University, 1979.
• 8: R. J. Lipton, R. E. Miller, and L. Snyder, "Synchronization and computing capabilities of linear asynchronous structures", JCSS 14, pp. 49-72, February, 1977.
• 9: James L. Peterson, Petri Nets, ACM Computing Surveys (CSUR), v.9 n.3, p.223-252, Sept. 1977 [doi>10.1145/356698.356702]