A compiler method for the parallel execution of irregular reductions in scalable shared memory multiprocessors

ABSTRACT

This paper presents a new parallelization method for reductions of arrays with subscripted subscripts on scalable shared memory multiprocessors. The mapping of computations is based on grouping reduction loop iterations into sets that are further assigned to the cooperating threads of computation. Iterations belonging to the same set are chosen in such a way that update different entries in the reduction array. That is, the loop distribution implies a conflict-free write distribution of the reduction array. The iteration sets are set up by building a loop-index prefetching data structure that allows to reorder properly the loop iterations. The proposed method is general, scalable, and easy to implement on a compiler. In addition it deals in a uniform way with one and multiple subscript arrays. In case of multiple indirection arrays, writes on the reduction array affecting different sets are solved by defining conflict-free supersets. A performance evaluation is presented. From the experimental results and performance analysis, the proposed method appears as a clear alternative to the array expansion and privatized buffer techniques, used on state-of-the-art parallelizing compilers, like Polaris or SUIF. The scalability problem that those techniques exhibit is missing in our method, as the memory overhead presented does not depend on the number of processors.

REFERENCES

• 1: R. Asenjo, E. Gutierrez, Y. Lin, D. Padua, B. Pottengerg, and E. Zapata. On the automatic parallelization of sparse and irregular Fortran codes. Technical Report TR-1512, University for Illinois at Urbana-Champalgn. Center for Supercomputing R&D, December 1996.
• 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: B. Brooks, K. Bruccoleri, B. Olafson, D. States, S. Swaminathan, and M. Karplus. Charmm: A program for macromolecular energy, minimization and dynamics calculations. J. Computational Chemistry, 4:217-183, 1983.
• 4: Chen Ding , Ken Kennedy, Improving cache performance in dynamic applications through data and computation reorganization at run time, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.229-241, May 01-04, 1999, Atlanta, Georgia, United States
• 5: I. Foster, R. Schreiber, and P. Havlak. HPF-2, scope of activities and motivating applications. Technical Report CRPC-TR94492, Center for Research on Parallel Computation, PAce University, November 1994.
• 6: Mary H. Hall , Saman P. Amarasinghe , Brian R. Murphy , Shih-Wei Liao , Monica S. Lam, Detecting coarse-grain parallelism using an interprocedural parallelizing compiler, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.49-es, December 04-08, 1995, San Diego, California, United States [doi>10.1145/224170.224337]
• 7: Mary W. Hall , Jennifer M. Anderson , Saman P. Amarasinghe , Brian R. Murphy , Shih-Wei Liao , Edouard Bugnion , Monica S. Lam, Maximizing Multiprocessor Performance with the SUIF Compiler, Computer, v.29 n.12, p.84-89, December 1996 [doi>10.1109/2.546613]
• 8: Hwansoo Han , Chau-Wen Tseng, Improving Compiler and Run-Time Support for Irregular Reductions Using Local Writes, Proceedings of the 11th International Workshop on Languages and Compilers for Parallel Computing, p.181-196, August 07-09, 1998
• 9: R. Hanxleden. Compiler support for machine independent parallelization of irregular problems. Technical Report CR.PC-TR.92301-S, Center for Research on Parallel Computation, Rice University, November 1992.
• 10: High Performance Fortran Forum. High Performance Fortran Language Specification, Version 2.0, 1996.
• 11: J. Ku. The design of an efficient and portable interface between a parallelizing compiler and its target machine. Technical report, Master's Thesis, Univ. of Illinois at Urbana-Champaign, Center for Supercomputing R&D, 1995.
• 12: 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
• 13: Nicholas Mitchell , Larry Carter , Jeanne Ferrante, Localizing Non-Affine Array References, Proceedings of the 1999 International Conference on Parallel Architectures and Compilation Techniques, p.192, October 12-16, 1999
• 14: J. Morales and S. Toxvaerd. The ceU-neighbour table method in moleimlar dynamics simulations. Computer Physics Communications, 71:71-76, 1992.
• 15: OpenMP Architecture Re,clew Board. OpenMP: A Proposed lndustry Standard API for Shared Memory Programming, 1997.
• 16: Ravi Ponnusamy , Joel Saltz , Alok Choudhary , Yuan-Shin Hwang , Geoffrey Fox, Runtime Support and Compilation Methods for User-Specified Irregular Data Distributions, IEEE Transactions on Parallel and Distributed Systems, v.6 n.8, p.815-831, August 1995 [doi>10.1109/71.406958]
• 17: Bill Pottenger , Rudolf Eigenmann, Idiom recognition in the Polaris parallelizing compiler, Proceedings of the 9th international conference on Supercomputing, p.444-448, July 03-07, 1995, Barcelona, Spain [doi>10.1145/224538.224655]
• 18: Silicon Graphics, Inc. MIPSpro Fortran77 Programmer's Guide, 1994.
• 19: Silicon Graphics, Inc. MIPSpro Automatic Parallelization, 1998.
• 20: S. Toxvacrd. Algorithms for canonical molecular dynamics simulations. Molecular Physics, 72(1):159-168, 1991.

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Shared memory

  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

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

General Terms:
Design, Languages, Measurement, Performance, Theory