Adaptive reduction parallelization techniques

ABSTRACT

In this paper, we propose to adapt parallelizing transformations, more specifically, reduction parallelizations, to the actual reference pattern executed by a loop, i.e., to the particular input data and dynamic phase of a program. More precisely we will show how, after validating a reduction at run-time (when this is not possible at compile time) we can dynamically characterize its reference pattern and choose the most appropriate method for parallelizing it. For this purpose, we develop a library of parallel reduction algorithms, including both previously known and novel schemes, which includes algorithms specialized for different classes of access behavior. In particular, each algorithm in our library has identified strengths related to specific reference pattern characteristics, which are matched, at run-time, with measured characteristics of the actual reference pattern. The matching of algorithm to reference pattern is performed using a decision-tree based selection scheme. The contribution of this work consists in new optimizations for reduction parallelization and in the introduction of a new approach to the optimization of irregular applications: Characteristic based customization.

REFERENCES

• 1: Charmm: A program for macromolecular energy, minimization, and dynamics calculations. Journal of Computational Chemistry, ,4(6), 1983.
• 2: William Blume , Ramon Doallo , Rudolf Eigenmann , John Grout , Jay Hoeflinger , Thomas Lawrence , Jaejin Lee , David Padua , Yunheung Paek , Bill Pottenger , Lawrence Rauchwerger , Peng Tu, Parallel Programming with Polaris, Computer, v.29 n.12, p.78-82, December 1996 [doi>10.1109/2.546612]
• 3: Rudolf Eigenmann , Jay Hoeflinger , Z. Li , David A. Padua, Experience in the Automatic Parallelization of Four Perfect-Benchmark Programs, Proceedings of the Fourth International Workshop on Languages and Compilers for Parallel Computing, p.65-83, August 07-09, 1991
• 4: H. Han , C.-W. Tseng, Improving Compiler and Run-Time Support for Adaptive Irregular Codes, Proceedings of the 1998 International Conference on Parallel Architectures and Compilation Techniques, p.393, October 12-18, 1998
• 5: C. Kruskal. Efficient parallel algorithms for graph problems. In Proceedings of the 1986 International Conference on Parallel Processing, pages 869--876, August 1986.
• 6: F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
• 7: M.J. Frisch, et. al. Gaussian 94, Revision B.1. Gaussian, Inc., Pittsburgh PA, 1995.
• 8: Laurence NageL SPICE2: A Computer Program to Simulate Semiconductor Circuits. PhD thesis, University of California, May 1975.
• 9: Devang Patel , Lawrence Rauchwerger, Principles of Speculative Run-Time Parallelization, Proceedings of the 11th International Workshop on Languages and Compilers for Parallel Computing, p.323-337, August 07-09, 1998
• 10: Lawrence Rauchwerger , David A. Padua, The LRPD Test: Speculative Run-Time Parallelization of Loops with Privatization and Reduction Parallelization, IEEE Transactions on Parallel and Distributed Systems, v.10 n.2, p.160-180, February 1999 [doi>10.1109/71.752782]
• 11: Sandhya Dwarkadas , Alan L. Cox , Willy Zwaenepoel, An integrated compile-time/run-time software distributed shared memory system, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.186-197, October 01-04, 1996, Cambridge, Massachusetts, United States
• 12: Robert G. Whirley and Bruce Engelmann. DYNA3D: A Nonlinear, Explicit, Three-Dimensional Finite Element Code For Solid and Structural Mechanics. Lawrence Livermore National Laboratory, Ngvember, 1993.
• 13: J. Wu, J. Saltz, S. Hiranandani, and H. Berryman. Runtime compilation methods for multicomputers. In Dr. H.D. Schwetman, editor, Proceedings of the 1991 International Conference on Parallel Processing, pages 26--30. CRC Press, Inc., 1991. Vol. II - Software,
• 14: Hao Yu and L. Rauchwerger. Run-time parallelization overhead reduction techniques. In Proc. of the 9th International Conference on Compiler Construction (CC2000), Berlin, Germany. Lecture Notes in Computer Selene, Springer-Vedag, 2000.
• 15: Hans Zima , Barbara Chapman, Supercompilers for parallel and vector computers, ACM Press, New York, NY, 1990
• 16: William Morton Pottenger, Theory, techniques, and experiments in solving recurrences in computer programs, University of Illinois at Urbana-Champaign, Champaign, IL, 1997
• 17: Yuan Lin , David A. Padua, On the Automatic Parallelization of Sparse and Irregular Fortran Programs, Selected Papers from the 4th International Workshop on Languages, Compilers, and Run-Time Systems for Scalable Computers, p.41-56, May 28-30, 1998

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.2.4 Software/Program Verification
          Subjects: Model checking

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.2 Automatic Programming
          Subjects: Program transformation

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