Automatic partitioning and virtual scheduling for efficient parallel execution

ABSTRACT

The research of this report gives a method for automatic determination and scheduling of parallel modules from an existing sequential computation.In compiling a sequential program for execution on a multiprocessor system, there are four major problems to be solved: [26]1. Analyzing the data dependences and control dependences in the program.2. Identifying parallelism in the program.3. Partitioning the program into grains of sequential tasks.4. Scheduling the tasks on processors.The work of this paper addresses the last three problems. The automatic dependence analysis, the phase that detects where parallelism is constrained, has been studied extensively, and there exist a number of tools (e.g. PAT[3], PTOOL[2], Parafrase[21], Faust[19] and PTRAN[1]) that create data flow and control flow graphs from sequential code. A directed graph is typically used to model the dependence relation. Usually, a node of the graph G = (N,E) represents an operation such as a statement or block of statements, and an edge (u,v) represents the dependence of v on u, forcing the execution of u before v. For both data and control dependence, the key is to represent only essential dependence constraints as edges. This paper assumes that a dependence graph exists and discusses a method for performing the last three tasks on the dependence graph. The technique decomposes the data flow graph into grains of the appropriate size for any underlying homogeneous multiprocessor architecture, determines which grains should be executed in parallel and which must be executed sequentially, and schedules those grains onto processors.

REFERENCES

• 1: F. Allen , M. Burke , P. Charles , R. Cytron , J. Ferrante, An overview of the PTRAN analysis system for multiprocessing, Proceedings of the 1st International Conference on Supercomputing, p.194-211, March 1988, Athens, Greece
• 2: Allen, R., Baumgartner, D., Kennedy, K., and Porterfield, A."PTOOL: A Semi-Autumatic Parallel Programming Assistant," Proceedings of the 1986 International Conference on Parallel Processing, pp. 721-727.
• 3: Appelbe, W. F. and Smith, K. "PAT: A Retargetable Parallelizing Tool for Fortran" Proceedings of the IEEE 1990 Conference on Software Maintenance. 1990.
• 4: Baxter, J., and Patel, J., "The LAST Algorithm: A Heuristic- Based Static Task Allocation Algorithm," Proceedings of the 1089 International Conference on Parallel Processing, pp. 217-222.
• 5: Berman, F., "Experience with and Automatic Solution to the Mapping Problem', in The Characteristics of Parallel Algorithms, edited by Leah H. Jamieson. Dennis B. Gannon" and Robert J. Doublar, MIT Press. Cambridge, 1987.
• 6: Bokari, S., "On the Mapping Problem". IEEE Transactions on Computers, March, 1981.
• 7: Bomans, L., and Roose, D., Hypercube and Distributed Computers, Elsevier Science Publishers, New York, 1989.
• 8: Carroll, J. M., Thomas J. C. and Malhotra, A.. 1980 "Presentation and Representation in Design Problem-Solving", British Journal of Psychology, 71 (1980). pp. 143-153.
• 9: Shi-Kuo Chang, Principles of visual programming systems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1990
• 10: Shi-Kuo K. Chang , Tadao Ichikawa , Panos A. Ligomenides, Visual Languages, Perseus Publishing, 1987
• 11: Coffman. E. "Computer and Job-Shop Scheduling theory". New York: John Wiley and Sons, 1976.
• 12: Dongarra, J. J. and Sorensen, D. C.,"SCHEDULE: Tools for Developing and Analyzing Parallel Fortran Programs," in The Characteristics of Parallel Algorithms, edited by Leah tl. Jamieson, Dennis B. Gannon, and Robert J. Doublas, MIT Press, Cambridge, 1987.
• 13: J. J. Dongarra , Orlie Brewer , James Arthur Kohl , Samuel Fineberg, A tool to aid in the design, implementation, and understanding of matrix algorithms for parallel processors, Journal of Parallel and Distributed Computing, v.9 n.2, p.185-202, June 1990 [doi>10.1016/0743-7315(90)90045-Q]
• 14: A. Ehrenfeucht , G. Rozenberg, Theory of 2-structures. Part I: clans, basic subclasses, and morphisms, Theoretical Computer Science, v.70 n.3, p.277-303, Feb. 1990 [doi>10.1016/0304-3975(90)90129-6]
• 15: A. Ehrenfeucht , G. Rozenberg, Primitivity is hereditary for 2-structures, Theoretical Computer Science, v.70 n.3, p.343-358, Feb. 1990 [doi>10.1016/0304-3975(90)90131-Z]
• 16: A. Ehrenfeucht , G. Rozenberg, Theory of 2-structures. Part II: representation through labeled tree families, Theoretical Computer Science, v.70 n.3, p.305-342, Feb. 1990 [doi>10.1016/0304-3975(90)90130-A]
• 17: Fortes, J. A. B. and Moldovan, D. I., "Parallelism Detection and Transformation Techniques Useful for VLSI Algorithms", Journal of Parallel and Distributed Computing, 2 (1985), pp. 277-301.
• 18: Gibbons, P., "A More Practical PRAM Model", International Computer Science Institute, Berkeley, CA. Technical Report TR-89-019,1989.
• 19: V. A. Guarna , D. Gannon, Jr. , Y. Gaur , D. Jablonowski, FAUST: an environment for programming parallel scientific applications, Proceedings of the 1988 ACM/IEEE conference on Supercomputing, p.3-10, November 12-17, 1988, Orlando, Florida, United States
• 20: Kim, S., and Browne, S., "A General Approach to Mapping of Parallel Computations Upon Multiprocesanr Architecture," Proceedings of the 1988 International Conference on Parallei Processing, pp. 1-8.
• 21: Kuck, D. H., Kuhn, R. H., Leasure, B. R., and Wolfe M. J., "The Structure of an Advanced Retargetable Vectorizer." In Supercomputers : Design and Applications Tutorial (Hwnng K., ed. ), IEEE Society Press, Silver Spring, MD, pp. 967-74.
• 22: Leirson, C., and Maggs, B., "Communication Efficient Parallel Graph Algorithms", International Conference on Parallel Procesing, 1986, pp. 861-868.
• 23: Carolyn McCreary, Parsing a graph-grammar, Proceedings of the 1988 ACM sixteenth annual conference on Computer science, p.249-255, February 1988, Atlanta, Georgia, United States [doi>10.1145/322609.322649]
• 24: Carolyn McCreary , Helen Gill, Automatic determination of grain size for efficient parallel processing, Communications of the ACM, v.32 n.9, p.1073-1078, Sept. 1989 [doi>10.1145/66451.66454]
• 25: McCreary, C. L. and Gill, D. H., "Efficient Exploitation of Cencurrency Using Graph Decomposition," Proceedings of the 1990 International Conference on Parallel Processing.
• 26: Vivek Sarkar, Partitioning and Scheduling Parallel Programs for Multiprocessors, MIT Press, Cambridge, MA, 1989
• 27: Bernd Stramm , Francine Berman, Communication-sensitive heuristics and algorithms for mapping compilers, Proceedings of the ACM/SIGPLAN conference on Parallel programming: experience with applications, languages and systems, p.222-243, July 19-21, 1988, New Haven, Connecticut, United States
• 28: Stratum, B., and Berman, F., "How Good Is Good?, Department of Computer Science and Engineering, University of California, San Diego, Technical Report CS90-169, 1990.
• 29: D. C. Stone, Using cumulative graphic traces in the visualization of sorting algorithms, ACM SIGCSE Bulletin, v.21 n.4, p.37-42, Dec. 1989 [doi>10.1145/74091.74100]
• 30: D Towsley, Allocating programs containing branches and loops within a multiple processor system, IEEE Transactions on Software Engineering, v.12 n.10, p.1018-1024, Oct. 1986
• 31: Michael Joseph Wolfe, Optimizing Supercompilers for Supercomputers, MIT Press, Cambridge, MA, 1990
• 32: Hans Zima , Barbara Chapman, Supercompilers for parallel and vector computers, ACM Press, New York, NY, 1990
• 33: Zima, H. P., Bast, H. J., and Gerudt, H. M. "SUPERB - A Tool for Semi- Automatic MIMD/SIMD Parailelization," Parallel Computing, 6 (1988), pp. 1-18.