Evaluating automatic parallelization for efficient execution on shared-memory multiprocessors

ABSTRACT

We present a parallel code generation algorithm for complete applications and a new experimental methodology that tests the efficacy of our approach. The algorithm optimizes for data locality and parallelism, reducing or eliminating false sharing. It also uses interprocedural analysis and transformations to improve the granularity of parallelism. Although the individual components of the algorithm have been published previously, their coordination is unique to this paper. For experimental validation, we do not attempt to parallelize “dusty deck” programs where many have tried and failed. Instead, we collect programs where the users tried to achieve excellent parallel performance. We apply our optimizations to sequential versions of these programs, i.e., the compiler was required to use its analysis and algorithms to parallelize the program and could not rely on user assertions that for example, a loop is parallel. With this metric, our algorithm improves or matches hand-coded parallel programs on shared-memory, bus-based parallel machines for eight of the nine programs in our test suite.

REFERENCES

• 1: r. Allen , D. Callahan , K. Kennedy, Automatic decomposition of scientific programs for parallel execution, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.63-76, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41631]
• 2: 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]
• 3: V. Balasundaram , K. Kennedy, A technique for summarizing data access and its use in parallelism enhancing transformations, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.41-53, June 19-23, 1989, Portland, Oregon, United States
• 4: Michael Burke , Ron Cytron, Interprocedural dependence analysis and parallelization, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.162-175, June 25-27, 1986, Palo Alto, California, United States
• 5: S. Carr, K. S. MCKinley, and C. Tseng. Compiler optimizations for improving data locality. Technical Report TR92-195, Dept. of Computer Science, Rice University, November 1992.
• 6: K. Cooper, M. W. Hall, R. T. Hood, K. Kennedy, K. S. McKinley, J. M. Mellor-Crummey, L. Torczon, and S. K. Warren. The ParaScope parallel programming environment. Proceedings of the IEEE, 81(2):244-263, February 1993.
• 7: Keith D. Cooper , Ken Kennedy , Linda Torczon, The impact of interprocedural analysis and optimization in the Rⁿ programming environment, ACM Transactions on Programming Languages and Systems (TOPLAS), v.8 n.4, p.491-523, Oct. 1986 [doi>10.1145/6465.6489]
• 8: R. Eigenmann, J. Hoeflinger, G. Jaxon, Z. Li, and D. Padua. Restructuring Fortran programs for Cedar. Concurrency: Practice & Experience, 5(7):553-574, October 1993.
• 9: Mary W. Hall , Ken Kennedy , Kathryn S. McKinley, Interprocedural transformations for parallel code generation, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.424-434, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.126055]
• 10: 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]
• 11: Ken Kennedy , Kathryn S. McKinley, Optimizing for parallelism and data locality, Proceedings of the 6th international conference on Supercomputing, p.323-334, July 19-24, 1992, Washington, D. C., United States [doi>10.1145/143369.143427]
• 12: Ken Kennedy , Kathryn S. McKinley, Maximizing Loop Parallelism and Improving Data Locality via Loop Fusion and Distribution, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.301-320, August 12-14, 1993
• 13: K. Kennedy and K. S. MCKinley. Typed fusion with applications to parallel and sequential code generation. Technical Report TR93-208, Dept. of Computer Science, Rice University, August 1993.
• 14: K. Kennedy, K. S. MCKinley, and C. Tseng. Analysis and transformation in an interactive parallel programming tool. Concurrency: Practice & Experience, 5(7):575--602, October 1993.
• 15: D. Kuck , E. Davidson , D. Lawrie , A. Sameh , C. Q. Zhu , A. Veidenbaum , J. Konicek , P. Yew , K. Gallivan , W. Jalby , H. Wijshoff , R. Bramley , U. M. Yang , P. Emrath , D. Padua , R. Eigenmann , J. Hoeflinger , G. Jaxon , Z. Li , T. Murphy , J. Andrews, The cedar system and an initial performance study, Proceedings of the 20th annual international symposium on Computer architecture, p.213-223, May 16-19, 1993, San Diego, California, United States
• 16: 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
• 17: K.S. McKinley. Dependence analysis of arrays subscripted by index arrays. Technical Report TR91-162, Dept. of Computer Science, Rice University, December 1990.
• 18: Kathryn Stuart McKinley, Automatic and interactive parallelization, Rice University, Houston, TX, 1992
• 19: Anita Osterhaug, Guide to parallel programming on Sequent computer systems: 2nd edition, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 20: J. Singh and J. 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.
• 21: Jaswinder Pal Singh , John L. Hennessy, Finding and exploiting parallelism in an ocean simulation program: experience, results, and implications, Journal of Parallel and Distributed Computing, v.15 n.1, p.27-48, May 1992 [doi>10.1016/0743-7315(92)90056-S]
• 22: Jaspal Singh Subhlok, Analysis of synchronization in a parallel programming environment, Rice University, Houston, TX, 1992
• 23: 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
• 24: Michael Edward Wolf, Improving locality and parallelism in nested loops, Stanford University, Stanford, CA, 1992
• 25: M. E. Wolf , M. S. Lam, A Loop Transformation Theory and an Algorithm to Maximize Parallelism, IEEE Transactions on Parallel and Distributed Systems, v.2 n.4, p.452-471, October 1991 [doi>10.1109/71.97902]

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

General Terms:
Algorithms, Experimentation, Measurement, Performance, Theory