Static single assignment for explicitly parallel programs

ABSTRACT

We describe and prove algorithms to convert programs which use the Parallel Computing Forum Parallel Sections construct into Static Single Assignment (SSA) form. This proces allows compilers to apply classical scalar optimization algorithms to explicitly parallel programs. To do so, we must define what the concept of dominator and dominance frontier mean in parallel programs. We also describe how we extend SSA form to handle parallel updates and still preserve the SSA properties.

REFERENCES

• 1: Frances Allen , Michael Burke , Philippe Charles , Ron Cytron , Jeanne Ferreant, An overview for the PTRAN analysis system for multiprocessing, Journal of Parallel and Distributed Computing, v.5 n.5, p.617-640, October 1988 [doi>10.1016/0743-7315(88)90015-9]
• 2: B. Alpern , M. N. Wegman , F. K. Zadeck, Detecting equality of variables in programs, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-11, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73561]
• 3: Per Brinch Hansen. Operating Systems Principles. Automatic Computation. Prentice-Hall, 1973.
• 4: Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , F. Kenneth Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.451-490, Oct. 1991 [doi>10.1145/115372.115320]
• 5: Samuel P. Midkiff and David A. Padua. Issues in the optimization of parallel programs. In Proc. 1990 International Conf. on Parallel Processing, volume II, pages 105-113, St. Charles, IL, August 1990. Penn State Press.
• 6: Samuel P. Midkiff , David A. Padua , Ron Cytron, Compiling programs with user parallelism, Selected papers of the second workshop on Languages and compilers for parallel computing, p.402-422, May 1990, Urbana, Illinois, United States
• 7: CORPORATE The Parallel Computing Forum, PCF parallel Fortran extensions, ACM SIGPLAN Fortran Forum, v.10 n.3, p.1-57, Sept. 1991 [doi>10.1145/122391.122392]
• 8: Conf. Record 15~h Annual A CM Syrup. Principles of Programming Languages, San Diego, CA, January 1988.
• 9: B. K. Rosen , M. N. Wegman , F. K. Zadeck, Global value numbers and redundant computations, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.12-27, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73562]
• 10: Harini Srinivasan. Analyzing programs with explicit parallelism. M.S. thesis 91-TH-006, Oregon Graduate Institute, Dept. of Computer Science and Engineering, July 1991.
• 11: Harini Srinivasan , Michael Wolfe, Analyzing Programs with Explicit Parallelism, Proceedings of the Fourth International Workshop on Languages and Compilers for Parallel Computing, p.405-419, August 07-09, 1991
• 12: Mark N. Wegman , F. Kenneth Zadeck, Constant propagation with conditional branches, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.2, p.181-210, April 1991 [doi>10.1145/103135.103136]
• 13: Michael Wolfe, Beyond induction variables, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.162-174, June 15-19, 1992, San Francisco, California, United States
• 14: Michael Wolfe , Harini Srinivasan, Data Structures for Optimizing Programs with Explicit Parallelism, Proceedings of the First International ACPC Conference on Parallel Computation, p.139-156, September 30-October 02, 1991

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Control primitives

General Terms:
Algorithms, Performance