Detecting coarse-grain parallelism using an interprocedural parallelizing compiler

ABSTRACT

This paper presents an extensive empirical evaluation of an interprocedural parallelizing compiler, developed as part of the Stanford SUIF compiler system. The system incorporates a comprehensive and integrated collection of analyses, including privatization and reduction recognition for both array and scalar variables, and symbolic analysis of array subscripts. The interprocedural analysis framework is designed to provide analysis results nearly as precise as full inlining but without its associated costs. Experimentation with this system shows that it is capable of detecting coarser granularity of parallelism than previously possible. Specifically, it can parallelize loops that span numerous procedures and hundreds of lines of codes, frequently requiring modifications to array data structures such as privatization and reduction transformations. Measurements from several standard benchmark suites demonstrate that an integrated combination of interprocedural analyses can substantially advance the capability of automatic parallelization technology.

REFERENCES

• 1: Jennifer M. Anderson , Saman P. Amarasinghe , Monica S. Lam, Data and computation transformations for multiprocessors, Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.166-178, July 19-21, 1995, Santa Barbara, California, United States
• 2: William Blume , Rudolf Eigenmann , Keith Faigin , John Grout , Jay Hoeflinger , David A. Padua , Paul Petersen , William M. Pottenger , Lawrence Rauchwerger , Peng Tu , Stephen Weatherford, Polaris: Improving the Effectiveness of Parallelizing Compilers, Proceedings of the 7th International Workshop on Languages and Compilers for Parallel Computing, p.141-154, August 08-10, 1994
• 3: W. Blume , R. Eigenmann, Performance Analysis of Parallelizing Compilers on the Perfect Benchmarks Programs, IEEE Transactions on Parallel and Distributed Systems, v.3 n.6, p.643-656, November 1992 [doi>10.1109/71.180621]
• 4: William Blume , Rudolf Eigenmann, The range test: a dependence test for symbolic, non-linear expressions, Proceedings of the 1994 conference on Supercomputing, p.528-537, December 1994, Washington, D.C., United States
• 5: K. Cooper, M.W. Hall, and K. Kennedy. A methodology for procedure cloning. Computer Languages, 19(2), April 1993.
• 6: Béatrice Creusillet , François Irigoin, Interprocedural Array Region Analyses, Proceedings of the 8th International Workshop on Languages and Compilers for Parallel Computing, p.46-60, August 10-12, 1995
• 7: Gina Goff , Ken Kennedy , Chau-Wen Tseng, Practical dependence testing, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.15-29, June 24-28, 1991, Toronto, Ontario, Canada
• 8: Mohammad R. Haghighat , Constantine D. Polychronopoulos, Symbolic Analysis: A Basis for Parallelization, Optimization, and Scheduling of Programs, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.567-585, August 12-14, 1993
• 9: Mary W. Hall , Brian R. Murphy , Saman P. Amarasinghe , Shih-Wei Liao , Monica S. Lam, Interprocedural Analysis for Parallelization, Proceedings of the 8th International Workshop on Languages and Compilers for Parallel Computing, p.61-80, August 10-12, 1995
• 10: M. W. Hall, S. Amarasinghe, and B. Murphy. Interprocedural analysis for parallelization: Design and experience. In Proceedings of the Seventh SIAM Conference on Parallel Processing for Scientific Computing, pages 650-655, San Francisco, CA, February 1995.
• 11: Mary W. Hall , John M. Mellor-Crummey , Alan Carle , René G. Rodríguez, FIAT: A Framework for Interprocedural Analysis and Transfomation, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.522-545, August 12-14, 1993
• 12: Paul Howard Havlak , Ken Kennedy, Interprocedural symbolic analysis, 1995
• 13: P. Havlak , K. Kennedy, An Implementation of Interprocedural Bounded Regular Section Analysis, IEEE Transactions on Parallel and Distributed Systems, v.2 n.3, p.350-360, July 1991 [doi>10.1109/71.86110]
• 14: Michael Hind , Michael Burke , Paul Carini , Sam Midkiff, An empirical study of precise interprocedural array analysis, Scientific Programming, v.3 n.3, p.255-271, Fall 1994
• 15: F. Irigoin. Interprocedural analyses for programming environments. In NSF- CNRS Workshop on Evironments and Tools for Parallel Scientific Programming, September 1992.
• 16: François Irigoin , Pierre Jouvelot , Rémi Triolet, Semantical interprocedural parallelization: an overview of the PIPS project, Proceedings of the 5th international conference on Supercomputing, p.244-251, June 17-21, 1991, Cologne, West Germany [doi>10.1145/109025.109086]
• 17: William Landi , Barbara G. Ryder, A safe approximate algorithm for interprocedural aliasing, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.235-248, June 15-19, 1992, San Francisco, California, United States
• 18: Zhiyuan Li , Pen-Chung Yew, Efficient interprocedural analysis for program parallelization and restructuring, Proceedings of the ACM/SIGPLAN conference on Parallel programming: experience with applications, languages and systems, p.85-99, July 19-21, 1988, New Haven, Connecticut, United States
• 19: Vadim Maslov, Delinearization: an efficient way to break multiloop dependence equations, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.152-161, June 15-19, 1992, San Francisco, California, United States
• 20: Dror E. Maydan , John L. Hennessy , Monica S. Lam, Efficient and exact data dependence analysis, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.1-14, June 24-28, 1991, Toronto, Ontario, Canada
• 21: R. Metzger and P. Smith. The CONVEX application compiler. Fortran Journal, 3(1):8-10, 1991.
• 22: Eugene M. Myers, A precise inter-procedural data flow algorithm, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.219-230, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567556]
• 23: J. P. Singh and J. L. Hennessy. An empirical investigation of the effectiveness of and limitations of automatic parallelization. In Proceedings of the International Symposium on Shared Memory Multiprocessors, Tokyo, Japan, April 1991.
• 24: Rémi Triolet , Francois Irigoin , Paul Feautrier, Direct parallelization of call statements, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.176-185, June 25-27, 1986, Palo Alto, California, United States
• 25: Chau-Wen Tseng, Compiler optimizations for eliminating barrier synchronization, Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.144-155, July 19-21, 1995, Santa Barbara, California, United States
• 26: Peng Tu , David A. Padua, Automatic Array Privatization, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.500-521, August 12-14, 1993
• 27: Michael Edward Wolf, Improving locality and parallelism in nested loops, Stanford University, Stanford, CA, 1992

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Measurement techniques
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.1 Large and Medium ("Mainframe") Computers
          Subjects: Super (very large) computers

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

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

General Terms:
Design, Experimentation, Measurement, Performance

Keywords:
parallelizing compilers, shared memory multiprocessors, compiler optimizations, interprocedural data-flow analysis