Parallelism for free: efficient and optimal bitvector analyses for parallel programs

ABSTRACT

We consider parallel programs with shared memory and interleaving semantics, for which we show how to construct for unidirectional bitvector problems optimal analysis algorithms that are as efficient as their purely sequential counterparts and that can easily be implemented. Whereas the complexity result is rather obvious, our optimality result is a consequence of a new Kam/Ullman-style Coincidence Theorem. Thus using our method, the standard algorithms for sequential programs computing liveness, availability, very busyness, reaching definitions, definition-use chains, or the analyses for performing code motion, assignment motion, partial dead-code elimination or strength reduction, can straightforward be transferred to the parallel setting at almost no cost.

REFERENCES

• 1: David Callahan , Jaspal Sublok, Static analysis of low-level synchronization, Proceedings of the 1988 ACM SIGPLAN and SIGOPS workshop on Parallel and distributed debugging, p.100-111, May 05-06, 1988, Madison, Wisconsin, United States
• 2: 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]
• 3: CHOW, J.-H. AND HARRISON, W. L. 1994. State space reduction in abstract interpretation of parallel programs. In Proceedings of the International Conference on Computer Languages (ICCL'9g). Toulouse, France, 277- 288.
• 4: 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]
• 5: COUSOT, P. AND COUSOT, R. 1984. Invariance proof methods and analysis techniques for parallel programs. In Automatic Program Construction Techniques, A. W. Biermann, G. Guiho, and Y. Kodratoff, Eds. Macmillan Publishing Company, Chapter 12, 243 - 271.
• 6: DHAMDHERE, D. M. 1989. A new algorithm for composite hoisting and strength reduction optimisation (+ corrigendum). International Journal of Computer Mathematics 27, 1- 14 (+ 31 32)
• 7: Dhananjay M. Dhamdhere , Barry K. Rosen , F. Kenneth Zadeck, How to analyze large programs efficiently and informatively, ACM SIGPLAN Notices, v.27 n.7, p.212-223, July 1992
• 8: Karl-Heinz Drechsler , Manfred P. Stadel, A variation of Knoop, Rüthing, and Steffen's Lazy Code Motion, ACM SIGPLAN Notices, v.28 n.5, p.29-38, May 1993 [doi>10.1145/152819.152823]
• 9: S. Duri , U. Buy , R. Devarapalli , S. M. Shatz, Using state space reduction methods for deadlock analysis in Ada tasking, ACM SIGSOFT Software Engineering Notes, v.18 n.3, p.51-60, July 1993
• 10: 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
• 11: Patrice Godefroid , Pierre Wolper, Using Partial Orders for the Efficient Verification of Deadlock Freedom and Safety Properties, Proceedings of the 3rd International Workshop on Computer Aided Verification, p.332-342, July 01-04, 1991
• 12: Dirk Grunwald , Harini Srinivasan, Data flow equations for explicitly parallel programs, ACM SIGPLAN Notices, v.28 n.7, p.159-168, July 1993
• 13: Dirk Grunwald , Harini Srinivasan, Efficient Computation of Precedence Information in Parallel Programs, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.602-616, August 12-14, 1993
• 14: Matthew S. Hecht, Flow Analysis of Computer Programs, Elsevier Science Inc., New York, NY, 1977
• 15: JOSHI, S. M. AND DHAMDHERE, D. M. 1982a. A composite hoisting-strength reduction transformation for global program optimization - part I. International Journal of Computer Mathematics 11, 21 - 41.
• 16: JOSHI, S. M. AND DHAMDHERE, D. M. 1982b. A composite hoisting-strength reduction transformation for global program optimization - part II. International Journal of Computer Mathematics 11, 111- 126.
• 17: KAM, J. B. AND ULLMAN, J. D. 1977. Monotone data flow analysis frameworks. Acta Informatica 7, 309 - 317.
• 18: Gary Arlen Kildall, Global expression optimization during compilation, 1972
• 19: Gary A. Kildall, A unified approach to global program optimization, Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.194-206, October 01-03, 1973, Boston, Massachusetts [doi>10.1145/512927.512945]
• 20: Jens Knoop , Oliver Rüthing , Bernhard Steffen, Lazy code motion, ACM SIGPLAN Notices, v.27 n.7, p.224-234, July 1992
• 21: KNOOP, J., RUTHING, O., AND STEFFEN, B. 1993. Lazy strength reduction. Journal of Programruing Languages 1, 1, 71-91.
• 22: 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]
• 23: 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
• 24: KNOOP, J., RUTHING, O., AND STEFFEN, B. 1994c. A tool kit for constructing optimal interprocedural data flow analyses. Tech. Rep. MIP-9413, FakultSot fiir Mathematik und Informatik, UniversitS~t Passau, Germany. 26 pages.
• 25: Jens Knoop , Oliver Rüthing , Bernhard Steffen, The power of assignment motion, ACM SIGPLAN Notices, v.30 n.6, p.233-245, June 1995
• 26: Jens Knoop , Bernhard Steffen, The Interprocedural Coincidence Theorem, Proceedings of the 4th International Conference on Compiler Construction, p.125-140, October 05-07, 1992
• 27: KNOOP, J. AND STEFFEN, B. 1993. Efficient and optimal bit-vector data flow analyses: A uniform interprocedural framework. Tech. Rep. 9309, Institut fiir Informatik und Praktische Mathematik, Christian-Albrechts-UniversitSot Kiel, Germany. 22 pages.
• 28: Jens Knoop , Bernhard Steffen , Jürgen Vollmer, Parallelism for Free: Bitvector Analyses -> No State Explosion!, Proceedings of the First International Workshop on Tools and Algorithms for Construction and Analysis of Systems, p.264-289, May 19-20, 1995
• 29: KNOOP, J., STEFFEN, B., AND VOLLMER, J. 1995b. Parallelism for free: Efficient and optimal bitvector analyses for parallel programs. In Preliminary Proceedings of the ist International Workshop on Tools and Algorithms for the Construction and Analysis of Systems (TACAS'95). BRICS Notes Series NS-95-2. Aarhus, Denmark, 319 - 333.
• 30: 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]
• 31: Kim Marriott, Frameworks for abstract interpretation, Acta Informatica, v.30 n.2, p.103-129, March 1993 [doi>10.1007/BF01178576]
• 32: Charles E. McDowell, A practical algorithm for static analysis of parallel programs, Journal of Parallel and Distributed Computing, v.6 n.3, p.515-536, June 1989 [doi>10.1016/0743-7315(89)90004-X]
• 33: MIDKIFF, S. P. AND PADUA, D. A. 1990. Issues in the optimization of parallel programs. In Proceedings of the International Conference on Parallel Processing (ICPP'90). Vol. II. St. Charles, Illinois, 105 - 113.
• 34: E Morel, Data flow analysis and global optimization, Methods and tools for compiler construction, Cambridge University Press, New York, NY, 1984
• 35: E. Morel , C. Renvoise, Global optimization by suppression of partial redundancies, Communications of the ACM, v.22 n.2, p.96-103, Feb. 1979 [doi>10.1145/359060.359069]
• 36: MOREL, E. AND RENVOISE, C. 1981. InterprocedurM elimination of partial redundancies. In Program Flow Analysis: Theory and Applications, S. S. Muchnick and N. D. Jones, Eds. Prentice Hall, Englewood Cliffs, New Jersey, Chapter 6, 160- 188.
• 37: Steven S. Muchnick , Neil D. Jones, Program Flow Analysis: Theory and Application, Prentice Hall Professional Technical Reference, 1981
• 38: SHARIR, M. AND PNUELI, t. 1981. Two approaches to interprocedurM data flow analysis. In Program Flow Analysis: Theory and Applications, S. S. Muchnick and N. D. Jones, Eds. Prentice Hall, Englewood Cliffs, New Jersey, Chapter 7, 189 - 233.
• 39: 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]
• 40: 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
• 41: Bernhard Steffen , Andreas Claßen , Marion Klein , Jens Knoop , Tiziana Margaria, The Fixpoint-Analysis Machine, Proceedings of the 6th International Conference on Concurrency Theory, p.72-87, August 21-24, 1995
• 42: Antti Valmari, A Stubborn Attack On State Explosion, Proceedings of the 2nd International Workshop on Computer Aided Verification, p.156-165, June 18-21, 1990
• 43: VOLLMER, J. 1994. Data flow equations for parallel programs that share memory. Tech. Rep. 2.11.1 of the ESPRIT Project COMPARE number 5933, FakultSot fiir Informatik, UniversitS~t Karlsruhe, Germany.
• 44: Jürgen Vollmer, Data flow analysis of parallel programs, Proceedings of the IFIP WG10.3 working conference on Parallel architectures and compilation techniques, p.168-177, June 27-29, 1995, Limassol, Cyprus
• 45: 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:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Concurrent, distributed, and parallel languages
      D.3.4 Processors
          Subjects: Optimization
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Synchronization

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

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
assignment motion, bitvector problems, code motion, data flow analysis, definition-use chains, interleaving semantics, parallelism, partial dead-code elimination, program optimization, shared memory, strength reduction, synchronization