MPI-aware compiler optimizations for improving communication-computation overlap

ABSTRACT

Several existing compiler transformations can help improve communication-computation overlap in MPI applications. However, traditional compilers treat calls to the MPI library as a black box with unknown side effects and thus miss potential optimizations. This paper's contributions enable the development of an MPI-aware optimizing compiler that can perform transformations exploiting knowledge of MPI call effects to increase communication-computa-tion overlap. We formulate a set of data flow equations and rules to describe the side effects of key MPI functions so an MPI-aware compiler can automatically assess the safety of transformations. After categorizing existing compiler transformations based on their effect on the application code, we present an optimization algorithm that specifies when and how to apply these optimizing transformations to achieve improved communication-computation overlap. By manually applying the optimization algorithm to kernels extracted from HYCOM and the NAS benchmarks, we show that even when transforming these highly optimized codes, execution time can be decreased by an average of over 30%.

REFERENCES

• 1: Open64. http://open64.sourceforge.net.
• 2: D. Bailey, T. Harris, W. Saphir, R. van der Wijngaart, A. Woo, and M. Yarrow. The NAS parallel benchmarks 2.0. Technical Report NAS-95-020, NASA Ames Research Center, December 1995.
• 3: C. Bell, D. Bonachea, R. Nishtala, and K. Yelick. Optimizing Bandwidth Limited Problems Using One-Sided Communication and Overlap. In 20th International Parallel & Distributed Processing Symposium (IPDPS), 2006.
• 4: Dan Bonachea, GASNet Specification, v1.1, University of California at Berkeley, Berkeley, CA, 2002
• 5: Zeki Bozkus , Alok N. Choudhary , Geoffrey Fox , Tomasz Haupt , Sanjay Ranka, A Compilation Approach for Fortran 90D/ HPF Compilers, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.200-215, August 12-14, 1993
• 6: E. P. Chassignet, L. T. Smith, G. R. Halliwell, and R. Bleck. North Atlantic simulation with the HYbrid Coordinate Ocean Model (HYCOM): Impact of the vertical coordinate choice, reference density, and thermobaricity. Journal of Physical Oceanography, 32:2504--2526, 2003.
• 7: Wei-Yu Chen , Dan Bonachea , Costin Iancu , Katherine Yelick, Automatic nonblocking communication for partitioned global address space programs, Proceedings of the 21st annual international conference on Supercomputing, June 17-21, 2007, Seattle, Washington [doi>10.1145/1274971.1274995]
• 8: Wei-Yu Chen , Costin Iancu , Katherine Yelick, Communication Optimizations for Fine-Grained UPC Applications, Proceedings of the 14th International Conference on Parallel Architectures and Compilation Techniques, p.267-278, September 17-21, 2005 [doi>10.1109/PACT.2005.13]
• 9: Dale Shires and Lori Pollock and Sara Sprenkle. Program Flow Graph Construction for Static Analysis of MPI Programs. In Parallel and Distributed Processing Techniques and Applications (PDPTA'99), pages 1847--1853, June 1999.
• 10: Anthony Danalis , Aaron Brown , Lori Pollock , Martin Swany , John Cavazos, Gravel: A Communication Library to Fast Path MPI, Proceedings of the 15th European PVM/MPI Users' Group Meeting on Recent Advances in Parallel Virtual Machine and Message Passing Interface, September 07-10, 2008, Dublin, Ireland [doi>10.1007/978-3-540-87475-1_19]
• 11: Anthony Danalis , Ki-Yong Kim , Lori Pollock , Martin Swany, Transformations to Parallel Codes for Communication-Computation Overlap, Proceedings of the 2005 ACM/IEEE conference on Supercomputing, p.58, November 12-18, 2005 [doi>10.1109/SC.2005.75]
• 12: A. Danalis, L. Pollock, and M. Swany. Automatic MPI application transformation with ASPhALT. In Workshop on Performance Optimization for High-Level Languages and Libraries (POHLL 2007), in conjunction with IPDPS 2007, 2007.
• 13: A. Danalis, L. Pollock, M. Swany, and J. Cavazos. Implementing an Open64-based Tool for Improving the Performance of MPI Programs. In The Open64 Workshop, in conjunction with IEEE/ACM International Symposium on Code Generation and Optimization (CGO) 2008, Apr 2008.
• 14: D. Das, M. Gupta, R. Ravindran, W. Shivani, P. Sivakeshava, and R. Uppal. Compiler-Controlled Extraction of Computation-Communication Overlap in MPI Applications. In HIPS-POHLL joint Workshop on High-Level Parallel Programming Models and Supportive Environments and Performance Optimization for High-Level Languages and Libraries held in conjunction with the 22nd IEEE International Parallel & Distributed Processing Symposium(IPDPS 2008), April 2008.
• 15: T. A. El-Ghazawi, W. W. Carlson, and J. M. Draper. UPC specification v. 1.1. http://upc.gwu.edu/documentation, 2003.
• 16: P. Feautrier, Array expansion, Proceedings of the 2nd international conference on Supercomputing, p.429-441, June 1988, St. Malo, France [doi>10.1145/55364.55406]
• 17: Manish Gupta , Sam Midkiff , Edith Schonberg , Ven Seshadri , David Shields , Ko-Yang Wang , Wai-Mee Ching , Ton Ngo, An HPF compiler for the IBM SP2, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.71-es, December 04-08, 1995, San Diego, California, United States [doi>10.1145/224170.224422]
• 18: High Performance Fortran Forum. High Performance Fortran language specification, version 1.0. CRPC-TR92225, Rice University, Houston, TX, 1993.
• 19: Paul N. Hilfinger , Dan Bonachea , David Gay , Susan Graham , Ben Liblit , Geoff Pike , Katherine Yelick, Titanium Language Reference Manual, University of California at Berkeley, Berkeley, CA, 2001
• 20: Seema Hiranandani , Ken Kennedy , Chau-Wen Tseng, Compiling Fortran D for MIMD distributed-memory machines, Multiprocessor performance measurement and evaluation, IEEE Computer Society Press, Los Alamitos, CA, 1995
• 21: Torsten Hoefler , Peter Gottschling , Andrew Lumsdaine, Leveraging non-blocking collective communication in high-performance applications, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany [doi>10.1145/1378533.1378554]
• 22: Torsten Hoefler , Andrew Lumsdaine , Wolfgang Rehm, Implementation and performance analysis of non-blocking collective operations for MPI, Proceedings of the 2007 ACM/IEEE conference on Supercomputing, November 10-16, 2007, Reno, Nevada [doi>10.1145/1362622.1362692]
• 23: C. Iancu, P. Husbands, and W. Chen. Message Strip Mining Heuristics for High Speed Networks. In VECPAR, 2004.
• 24: 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
• 25: K. Kennedy, B. Broom, K. Cooper, J. Dongarra, R. Fowler, D. Gannon, L. Johnsson, J. Mellor-Crummey, and L. Torczon. Telescoping Languages: A Strategy for Automatic Generation of Scientific Problem-Solving Systems from Annotated Libraries. Journal of Parallel and Distributed Computing, 61(12):1803--1826, 2001.
• 26: Michelle Mills Strout , Barbara Kreaseck , Paul D. Hovland, Data-Flow Analysis for MPI Programs, Proceedings of the 2006 International Conference on Parallel Processing, p.175-184, August 14-18, 2006 [doi>10.1109/ICPP.2006.32]
• 27: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 28: Jarek Nieplocha , Bryan Carpenter, ARMCI: A Portable Remote Memory Copy Libray for Ditributed Array Libraries and Compiler Run-Time Systems, Proceedings of the 11 IPPS/SPDP'99 Workshops Held in Conjunction with the 13th International Parallel Processing Symposium and 10th Symposium on Parallel and Distributed Processing, p.533-546, April 12-16, 1999
• 29: Robert W. Numrich , John Reid, Co-array Fortran for parallel programming, ACM SIGPLAN Fortran Forum, v.17 n.2, p.1-31, Aug. 1998 [doi>10.1145/289918.289920]
• 30: José Carlos Sancho , Kevin J. Barker , Darren J. Kerbyson , Kei Davis, Quantifying the potential benefit of overlapping communication and computation in large-scale scientific applications, Proceedings of the 2006 ACM/IEEE conference on Supercomputing, November 11-17, 2006, Tampa, Florida [doi>10.1145/1188455.1188585]
• 31: José Carlos Sancho , Darren J. Kerbyson, Improving the Performance of Multiple Conjugate Gradient Solvers by Exploiting Overlap, Proceedings of the 14th international Euro-Par conference on Parallel Processing, August 26-29, 2008, Las Palmas de Gran Canaria, Spain [doi>10.1007/978-3-540-85451-7_74]
• 32: Michelle Mills Strout , John Mellor-Crummey , Paul Hovland, Representation-independent program analysis, Proceedings of the 6th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, September 05-06, 2005, Lisbon, Portugal
• 33: Akiyoshi Wakatani , Michael Wolfe, A New Approach to Array Redistribution: Strip Mining Redistribution, Proceedings of the 6th International PARLE Conference on Parallel Architectures and Languages Europe, p.323-335, July 04-08, 1994

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS
      B.4.3 Interconnections (subsystems)
          Subjects: Parallel I/O

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

General Terms:
Algorithms, Theory

Keywords:
communication-computation overlap, data flow analysis, mpi-aware compiler optimizations