Compile-time analysis of parallel programs that share memory

ABSTRACT

Traditional optimization techniques for sequential programs are not directly applicable to parallel programs where concurrent activities may interfere with each other through shared variables. New compiler techniques must be developed to accommodate features found in parallel languages. In this paper, we use abstract interpretation to obtain useful properties of programs, e.g., side effects, data dependences, object lifetime and concurrent expressions, for a language that supports first-class functions, pointers, dynamic allocations and explicit parallelism through cobegin. These analyses may facilitate many applications, such as program optimization, parallelization, restructuring, memory management, and detecting access anomalies. Our semantics is based on a labeled transition system and is instrumented with procedure strings to record the procedural/concurrency movement along the program interpretation. We develop analyses in both concrete domains and abstract domains, and prove the correctness and termination of the abstract interpretation.

REFERENCES

• BHA86: G. L. Burn , C. L. Hankin , S. Abramsky, The theory of strictness analysis for higher order functions, on Programs as data objects, p.42-62, April 1986, Copenhagen, Denmark
• Bur87: G. L. Burn. Abstract Interpretation and the Parallel Evaluation of Functional Languages. PhD thesis, University of London, 1987.
• CC77: 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]
• Cyt86: Ron Cytron. On the implications of Parallel Languages for Compilers. Technical Report RC- 11723, IBM T.J. Watson Research Center, April 1986.
• Deu90: Alan Deutsch, On determining lifetime and aliasing of dynamically allocated data in higher-order functional specifications, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.157-168, December 1989, San Francisco, California, United States [doi>10.1145/96709.96725]
• HA89: W. L. Harrison, III , Z. Ammarguellat, The design of automatic parallelizers for symbolic and numeric programs, Proceedings of the US/Japan workshop on Parallel Lisp on Parallel Lisp: languages and systems, p.235-253, June 1990, Sendai, Japan
• Har89: Williams Ludwell Harrison IIi. The Interprocodural Analysis and Automatic Parallelization of Scheme Programs. Lisp and Symbolic Computation: an International Journal, 2(3/4):179-396, 1989.
• Har91: Williams Ludwell Harrison III. Semantic Analysis of Symbolic Programs for Automatic Parallelization. book in preparation, 1991.
• HPR89: S. Horwitz , P. Pfeiffer , T. Reps, Dependence analysis for pointer variables, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.28-40, June 19-23, 1989, Portland, Oregon, United States
• Hud87: Paul Hudak. A Semantic Model of Reference Counting and its Abstraction. In S. Abramsky and C. Hankin, editors, Abstract Interpretation of Declarative Languages. Ellis Horwood Limited, 1987.
• McD89: 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]
• Mer91: Nicolas Mercouroff, An Algorithm for Analyzing Communicating Processes, Proceedings of the 7th International Conference on Mathematical Foundations of Programming Semantics, p.312-325, March 25-28, 1991
• MH89: Charles E. McDowell , David P. Helmbold, Debugging concurrent programs, ACM Computing Surveys (CSUR), v.21 n.4, p.593-622, Dec. 1989 [doi>10.1145/76894.76897]
• MP90: S.P. Midkiff and D.A. Padua. Issues in the Optimization of Parallel Programs. In International Conference on Parallel Processing. Vol H Software, pages 105-113, 1990.
• MPC90: 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
• Nie87: F. Nielson, Strictness analysis and denotational abstract interpretation, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.120-131, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41636]
• NPD87: A. Neirynck , A. J. Demers, Computation of aliases and support sets, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.274-283, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41650]
• Rat90: C. Rattray, editor. Specification and Verification of Concurrent Systems, Workshops in Computing. Springer-Voting, 1990.
• Ros89: Mads Rosendahl, Automatic complexity analysis, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.144-156, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99381]
• RS90: John H. Reif , Scott A. Smolka, Data flow analysis of distributed communicating processes, International Journal of Parallel Programming, v.19 n.1, p.1-30, Feb. 1990 [doi>10.1007/BF01407862]
• SS88: 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]
• Tay83: Richard N. Taylor, A general-purpose algorithm for analyzing concurrent programs, Communications of the ACM, v.26 n.5, p.361-376, May 1983 [doi>10.1145/69586.69587]
• Val89: Antti Valmari, Eliminating Redundant Interleavings During Concurrent Program Verification, Proceedings of the Parallel Architectures and Languages Europe, Volume II: Parallel Languages, p.89-103, June 12-16, 1989

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Concurrent, distributed, and parallel languages

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Operational semantics

General Terms:
Design, Languages