Intererence analysis tools for parallelizing programs with recursive data structures

ABSTRACT

Interference estimation is a useful tool in developing parallel programs and is a key aspect of automatically parallelizing sequential programs. Interference analysis and disambiguation mechanisms for programs with simple data types and arrays have become a standard part of parallelizing and vectorizing compilers. However, efficient and implementable techniques for interference analysis in the presence of dynamic data-structures have yet to be developed. In this paper we study the problem of estimating interference in an imperative language with dynamic data-structures. We focus on developing efficient and implementable methods for regular recursive data-structures. We illustrate the approach by presenting a method for analysing trees and DAGs. In particular, we develop a structural flow-analysis technique that allows us to estimate whether two statements affect disjoint sub-trees of a forest of dynamically-allocated trees and DAGs. The method is based on a regular-expression-like representation of the relationships between accessible nodes in the forest. We have implemented our analysis and have obtained some very promising preliminary results.

REFERENCES

• AK87: Randy Allen , Ken Kennedy, Automatic translation of FORTRAN programs to vector form, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.4, p.491-542, Oct. 1987 [doi>10.1145/29873.29875]
• Ban79a: Utpal Banerjee, Speedup of ordinary programs, 1979
• Ban79b: John P. Banning, An efficient way to find the side effects of procedure calls and the aliases of variables, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.29-41, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567756]
• Bar78: Jeffrey M. Barth, A practical interprocedural data flow analysis algorithm, Communications of the ACM, v.21 n.9, p.724-736, Sept. 1978 [doi>10.1145/359588.359596]
• BC86: Michael Burke , Ron Cytron, Interprocedural dependence analysis and parallelization, ACM SIGPLAN Notices, v.21 n.7, p.162-175, July 1986
• BN86: Gianfranco Bilardi , Alexandru Nicolau, Adaptive Bitonic Sorting: An Optimal Parallel Algorithm for Shared Memory Machines, Cornell University, Ithaca, NY, 1986
• DK85: Henry Dietz and David Klappholz. Refined C: A sequential language for parallel processing. I-n ICPP, pages 442-449, 1985.
• GL86: David K. Gifford , John M. Lucassen, Integrating functional and imperative programming, Proceedings of the 1986 ACM conference on LISP and functional programming, p.28-38, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319848]
• Gua88: Vincent A. Guarna Jr. A technique for analyzing pointer and structure references in parallel restructuring compilers, ht Proceedings of the International Conference on Parallel Processing, volume 2, pages 212-220, 1988.
• Har86: W. Ludwell Harrison III. Compiling Lisp for evaluation on a tightly coupled multiprocessor. Technical Report CSRD Rpt. No. 565, Center for Supercomputing Research and Development, University of Illinois at Urbanan-Champaign, March 1986.
• Har88: W. L. Harrison, The interprocedural analysis and automatic parallelization of scheme programs, University of Illinois, Department of Computer Science, Urbana, IL, 1990
• Hen88: Laurie J. Hendren, Recursive Data Structures and Parallelism Detection, Cornell University, Ithaca, NY, 1988
• HN89: Laurie J. Hendren and Alexandru Nicolau. P~rallelizing programs with recursive data structures. In Proceedings of the International Conference on Parallel Processing, 1989.
• Hud86: Paul Hudak, A semantic model of reference counting and its abstraction (detailed summary), Proceedings of the 1986 ACM conference on LISP and functional programming, p.351-363, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319876]
• JM81: Steven S. Muchnick , Neil D. Jones, Program Flow Analysis: Theory and Application, Prentice Hall Professional Technical Reference, 1981
• JM82: Neil D. Jones , Steven S. Muchnick, A flexible approach to interprocedural data flow analysis and programs with recursive data structures, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.66-74, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582161]
• LG88: J. M. Lucassen , D. K. Gifford, Polymorphic effect systems, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.47-57, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73564]
• LH88a: J. R. Larus , P. N. Hilfinger, Detecting conflicts between structure accesses, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.24-31, June 20-24, 1988, Atlanta, Georgia, United States
• LH88b: James R. Larus , Paul N. Hilfinger, Restructuring Lisp programs for concurrent execution, Proceedings of the ACM/SIGPLAN conference on Parallel programming: experience with applications, languages and systems, p.100-110, July 19-21, 1988, New Haven, Connecticut, United States
• Luc87: J. M. Lucassen. Types and Effects: Towards the Integration oJ Functional and Imperative Programming. PhD thesis, MIT, 1987.
• Nei88: Anne Denise Neirynck, Static analysis of aliases and side effects in higher-order languages, Cornell University, Ithaca, NY, 1988
• Nic84: Alexandru Nicolau, Parallelism, memory anti-aliasing and correctness for trace scheduling compilers (disambiguation, flow-analysis, compaction), 1984
• PW86: David A. Padua , Michael J. Wolfe, Advanced compiler optimizations for supercomputers, Communications of the ACM, v.29 n.12, p.1184-1201, Dec. 1986 [doi>10.1145/7902.7904]
• RM88: C. Ruggieri , T. P. Murtagh, Lifetime analysis of dynamically allocated objects, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.285-293, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73585]
• Wei80: William E. Weihl, Interprocedural data flow analysis in the presence of pointers, procedure variables, and label variables, Proceedings of the 7th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.83-94, January 28-30, 1980, Las Vegas, Nevada [doi>10.1145/567446.567455]
• Wol82: Michael Joseph Wolfe, Optimizing supercompilers for supercomputers, 1982

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Data types and structures
      D.3.4 Processors
          Subjects: Compilers

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.1 Specifying and Verifying and Reasoning about Programs
          Subjects: Specification techniques

General Terms:
Design, Theory