Code motion for explicitly parallel programs

ABSTRACT

In comparison to automatic parallelization, which is thoroughly studied in the literature [31, 33], classical analyses and optimizations of explicitly parallel programs were more or less neglected. This may be due to the fact that naive adaptations of the sequential techniques fail [24], and their straightforward correct ones have unacceptable costs caused by the interleavings, which manifest the possible executions of a parallel program. Recently, however, we showed that unidirectional bitvector analyses can be performed for parallel programs as easily and as efficiently as for sequential ones [17], a necessary condition for the successful transfer of the classical optimizations to the parallel setting.In this article we focus on possible subsequent code motion transformations, which turn out to require much more care than originally conjectured [17]. Essentially, this is due to the fact that interleaving semantics, although being adequate for correctness considerations, fails when it comes to reasoning about efficiency of parallel programs. This deficiency, however, can be overcome by strengthening the specific treatment of synchronization points.

REFERENCES

• 1: Jyh-Herng Chow , William Ludwell Harrison, III, Compile-time analysis of parallel programs that share memory, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.130-141, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143194]
• 2: Patrick Cousot , Radhia Cousot, Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.238-252, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512973]
• 3: P. Cousot and R. Cousot. Abstract interpretation frameworks. J. Logic and Computation, 2(4):511- 547', 1992.
• 4: D. M. Dhamdhere, Practical adaption of the global optimization algorithm of Morel and Renvoise, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.2, p.291-294, April 1991 [doi>10.1145/103135.214520]
• 5: Matthew B. Dwyer , Lori A. Clarke, Data flow analysis for verifying properties of concurrent programs, ACM SIGSOFT Software Engineering Notes, v.19 n.5, p.62-75, Dec. 1994
• 6: Dirk Grunwald , Harini Srinivasan, Data flow equations for explicitly parallel programs, ACM SIGPLAN Notices, v.28 n.7, p.159-168, July 1993
• 7: Matthew S. Hecht, Flow Analysis of Computer Programs, Elsevier Science Inc., New York, NY, 1977
• 8: J. B. Kam and J. D. Ullman. Monotone data flow analysis frameworks. Acta Informatica, 7:305 - 317, 1977.
• 9: J. Knoop. Optimal Interprocedural Program Optimization: A new Framework and its Application. PhD thesis, Univ. of Kiel, Germany, 1993. LNCS Tutorial 1428, Springer-V., 1998.
• 10: Jens Knoop, Eliminating partially dead code in explicitly parallel programs, Theoretical Computer Science, v.196 n.1-2, p.365-393, April 6, 1998 [doi>10.1016/S0304-3975(97)00208-9]
• 11: Jens Knoop, Parallel Constant Propagation, Proceedings of the 4th International Euro-Par Conference on Parallel Processing, p.445-455, September 01-04, 1998
• 12: Jens Knoop , Oliver Rüthing , Bernhard Steffen, Lazy code motion, ACM SIGPLAN Notices, v.27 n.7, p.224-234, July 1992
• 13: J. Knoop, O. Riithing, and B. Steffen. Lazy strength reduction. J. Prog. Lang., 1(1):71-91, 1993.
• 14: Jens Knoop , Oliver Rüthing , Bernhard Steffen, Optimal code motion: theory and practice, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.4, p.1117-1155, July 1994 [doi>10.1145/183432.183443]
• 15: Jens Knoop , Oliver Rüthing , Bernhard Steffen, Partial dead code elimination, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.147-158, June 20-24, 1994, Orlando, Florida, United States
• 16: Jens Knoop , Oliver Rüthing , Bernhard Steffen, The power of assignment motion, ACM SIGPLAN Notices, v.30 n.6, p.233-245, June 1995
• 17: Jens Knoop , Bernhard Steffen , Jürgen Vollmer, Parallelism for free: efficient and optimal bitvector analyses for parallel programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.3, p.268-299, May 1996 [doi>10.1145/229542.229545]
• 18: Arvind Krishnamurthy , Katherine A. Yelick, Optimizing Parallel SPMD Programs, Proceedings of the 7th International Workshop on Languages and Compilers for Parallel Computing, p.331-345, August 08-10, 1994
• 19: Arvind Krishnamurthy , Katherine Yelick, Optimizing parallel programs with explicit synchronization, ACM SIGPLAN Notices, v.30 n.6, p.196-204, June 1995
• 20: L. Lamport. How to make a multiprocessor computer that correctly executes multiprocess programs. IEEE Trans. Comput., 28(9):690- 691, 1979.
• 21: Jaejin Lee , Samuel P. Midkiff , David A. Padua, Concurrent Static Single Assignment Form and Constant Propagation for Explicitly Parallel Programs, Proceedings of the 10th International Workshop on Languages and Compilers for Parallel Computing, p.114-130, August 07-09, 1997
• 22: Douglas Long , Lori A. Clarke, Data flow analysis of concurrent systems that use the rendezvous model of synchronization, Proceedings of the symposium on Testing, analysis, and verification, p.21-35, October 08-10, 1991, Victoria, British Columbia, Canada [doi>10.1145/120807.120810]
• 23: Kim Marriott, Frameworks for abstract interpretation, Acta Informatica, v.30 n.2, p.103-129, March 1993 [doi>10.1007/BF01178576]
• 24: S. P. Midkiff and D. A. Padua. Issues in the optimization of parallel programs, in Proc. Int. Conf. on Parallel Processing, Vol. II, pages 105- 113, 1990.
• 25: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 26: Steven S. Muchnick , Neil D. Jones, Program Flow Analysis: Theory and Application, Prentice Hall Professional Technical Reference, 1981
• 27: Steven S. Muchnick , Neil D. Jones, Program Flow Analysis: Theory and Application, Prentice Hall Professional Technical Reference, 1981
• 28: Dennis Shasha , Marc Snir, Efficient and correct execution of parallel programs that share memory, ACM Transactions on Programming Languages and Systems (TOPLAS), v.10 n.2, p.282-312, April 1988 [doi>10.1145/42190.42277]
• 29: Harini Srinivasan , James Hook , Michael Wolfe, Static single assignment for explicitly parallel programs, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.260-272, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158644]
• 30: 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
• 31: Michael Joseph Wolfe , Carter Shanklin , Leda Ortega, High Performance Compilers for Parallel Computing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 32: 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
• 33: Hans Zima , Barbara Chapman, Supercompilers for parallel and vector computers, ACM Press, New York, NY, 1990

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS

General Terms:
Algorithms, Design

Keywords:
bitvector problems, code motion (partial redundancy elimination), code optimization, data-flow analysis, interleaving semantics, shared memory, synchronization