Automatic generation and tuning of MPI collective communication routines

ABSTRACT

In order for collective communication routines to achieve high performance on different platforms, they must be able to adapt to the system architecture and use different algorithms for different situations. Current Message Passing Interface (MPI) implementations, such as MPICH and LAM/MPI, are not fully adaptable to the system architecture and are not able to achieve high performance on many platforms. In this paper, we present a system that produces efficient MPI collective communication routines. By automatically generating topology specific routines and using an empirical approach to select the best implementations, our system adapts to a given platform and constructs routines that are customized for the platform. The experimental results show that the tuned routines consistently achieve high performance on clusters with different network topologies.

REFERENCES

• 1: Jeff Bilmes , Krste Asanovic , Chee-Whye Chin , Jim Demmel, Optimizing matrix multiply using PHiPAC: a portable, high-performance, ANSI C coding methodology, Proceedings of the 11th international conference on Supercomputing, p.340-347, July 07-11, 1997, Vienna, Austria [doi>10.1145/263580.263662]
• 2: Jehoshua Bruck , Ching-Tien Ho , Eli Upfal , Shlomo Kipnis , Derrick Weathersby, Efficient Algorithms for All-to-All Communications in Multiport Message-Passing Systems, IEEE Transactions on Parallel and Distributed Systems, v.8 n.11, p.1143-1156, November 1997 [doi>10.1109/71.642949]
• 3: A. Faraj, P. Patarasuk, and X. Yuan. Bandwidth Efficient All-to-All Broadcast on Switched Clusters. Technical Report, Department of Computer Science, Florida State University, May 2005.
• 4: Ahmad Faraj , Xin Yuan, Message Scheduling for All-to-All Personalized Communication on Ethernet Switched Clusters, Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Papers, p.85.1, April 04-08, 2005 [doi>10.1109/IPDPS.2005.288]
• 5: NASA Parallel Benchmarks. Available at http://www.nas.nasa.gov/NAS/NPB.
• 6: M. Frigo and S. Johnson. FFTW: An Adaptive Software Architecture for the FFT. In Proceedings of the International Conference on Acoustics, Speech, and Signal Processing (ICASSP), volume 3, page 1381, 1998.
• 7: W. Gropp, E. Lusk, N. Doss, and A. Skjellum. A High-Performance, Portable Implementation of the MPI Message Passing Interface Standard. In MPI Developers Conference, 1995.
• 8: W. Gropp and E. Lusk. Reproducible Measurements of MPI Performance Characteristics. Technical Report ANL/MCS-P755-0699, Argonne National Labratory, Argonne, IL, June 1999.
• 9: LAM/MPI Parallel Computing. http://www.lam-mpi.org.
• 10: Mario Lauria , Andrew Chien, MPI-FM: high performance MPI on workstation clusters, Journal of Parallel and Distributed Computing, v.40 n.1, p.4-18, Jan. 10, 1997 [doi>10.1006/jpdc.1996.1264]
• 11: Laxmikant V. Kalé , Sameer Kumar , Krishnan Varadarajan, A Framework for Collective Personalized Communication, Proceedings of the 17th International Symposium on Parallel and Distributed Processing, p.69.1, April 22-26, 2003
• 12: Amit Karwande , Xin Yuan , David K. Lowenthal, CC--MPI: a compiled communication capable MPI prototype for ethernet switched clusters, Proceedings of the ninth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 11-13, 2003, San Diego, California, USA
• 13: Thilo Kielmann , Rutger F. H. Hofman , Henri E. Bal , Aske Plaat , Raoul A. F. Bhoedjang, MagPIe: MPI's collective communication operations for clustered wide area systems, Proceedings of the seventh ACM SIGPLAN symposium on Principles and practice of parallel programming, p.131-140, May 04-06, 1999, Atlanta, Georgia, United States
• 14: R. Rabenseifner. A new optimized MPI reduce and allreduce algorithms. Available at http://www.hlrs.de/organization/par/services/models/mpi/myreduce.html, 1997.
• 15: The MPI Forum. The MPI-2: Extensions to the Message Passing Interface, July 1997. Available at http://www.mpi-forum.org/docs/mpi-20-html/mpi2-report.html.
• 16: MPICH - A Portable Implementation of MPI. http://www.mcs.anl.gov/mpi/mpich.
• 17: Hirotaka Ogawa , Satoshi Matsuoka, OMPI: optimizing MPI programs using partial evaluation, Proceedings of the 1996 ACM/IEEE conference on Supercomputing (CDROM), p.37-es, January 01-01, 1996, Pittsburgh, Pennsylvania, United States [doi>10.1145/369028.369106]
• 18: I. Rosenblum, J. Adler, and S. Brandon. Multi-processor molecular dynamics using the Brenner potential: Parallelization of an implicit multi-body potential. International Journal of Modern Physics, C 10(1):189--203, Feb. 1999.
• 19: Steve Sistare , Rolf vandeVaart , Eugene Loh, Optimization of MPI collectives on clusters of large-scale SMP's, Proceedings of the 1999 ACM/IEEE conference on Supercomputing (CDROM), p.23-es, November 14-19, 1999, Portland, Oregon, United States [doi>10.1145/331532.331555]
• 20: Hong Tang , Kai Shen , Tao Yang, Program transformation and runtime support for threaded MPI execution on shared-memory machines, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.4, p.673-700, July 2000 [doi>10.1145/363911.363920]
• 21: R. Thakur, R. Rabenseifner, and W. Gropp. Optimizing of Collective Communication Operations in MPICH. ANL/MCS-P1140-0304, Mathematics and Computer Science Division, Argonne National Laboratory, March 2004.
• 22: Sathish S. Vadhiyar , Graham E. Fagg , Jack Dongarra, Automatically tuned collective communications, Proceedings of the 2000 ACM/IEEE conference on Supercomputing (CDROM), p.3-es, November 04-10, 2000, Dallas, Texas, United States
• 23: R. Clint Whaley , Jack J. Dongarra, Automatically tuned linear algebra software, Proceedings of the 1998 ACM/IEEE conference on Supercomputing (CDROM), p.1-27, November 07-13, 1998, San Jose, CA

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Distributed programming

General Terms:
Performance

Keywords:
MPI, cluster of workstations, empirical, tuning system