Towards automatic translation of OpenMP to MPI

ABSTRACT

We present compiler techniques for translating OpenMP shared-memory parallel applications into MPI message-passing programs for execution on distributed memory systems. This translation aims to extend the ease of creating parallel applications with OpenMP to a wider variety of platforms, such as commodity cluster systems. We present key concepts and describe techniques to analyze and efficiently handle both regular and irregular accesses to shared data.We evaluate the performance achieved by our translation scheme on seven representative OpenMP applications, two from SPEC OMPM2001 and five from the NAS Parallel Benchmarks suite, on two different platforms. The average scalability (execution time relative to the serial version) achieved is within 12% of that achieved by corresponding hand-tuned MPI applications. We also compare our programs with versions deployed for a Software Distributed Shared Memory (SDSM) system and find that the direct translation to MPI achieves up to 30% higher scalability. A comparison with High Performance Fortran (HPF) versions of two NAS benchmarks indicates that our translated OpenMP versions achieve 12% to 89% better performance than the HPF versions.

REFERENCES

• 1: Tarek S. Abdelrahman , Thomas N. Wong, Compiler Support for Array Distribution onNUMA Shared Memory Multiprocessors, The Journal of Supercomputing, v.12 n.4, p.349-371, October 1998 [doi>10.1023/A:1008035807599 ]
• 2: Cristiana Amza , Alan L. Cox , Sandhya Dwarkadas , Pete Keleher , Honghui Lu , Ramakrishnan Rajamony , Weimin Yu , Willy Zwaenepoel, TreadMarks: Shared Memory Computing on Networks of Workstations, Computer, v.29 n.2, p.18-28, February 1996 [doi>10.1109/2.485843 ]
• 3: Vishal Aslot , Max J. Domeika , Rudolf Eigenmann , Greg Gaertner , Wesley B. Jones , Bodo Parady, SPEComp: A New Benchmark Suite for Measuring Parallel Computer Performance, Proceedings of the International Workshop on OpenMP Applications and Tools: OpenMP Shared Memory Parallel Programming, p.1-10, July 30-31, 2001
• 4: D. H. Bailey, E. Barszcz, J. T. Barton, D. S. Browning, R. L. Carter, D. Dagum, R. A. Fatoohi, P. O. Frederickson, T. A. Lasinski, R. S. Schreiber, H. D. Simon, V. Venkatakrishnan, and S. K. Weeratunga. The NAS Parallel Benchmarks. The International Journal of Supercomputer Applications, 5(3):63--73, Fall 1991.
• 5: P. Banerjee, J. A. Chandy, M. Gupta, J. G. Holm, A. Lain, D. J. Palermo, S. Ramaswamy, and E. Su. The PARADIGM Compiler for Distributed-Memory Message Passing Multicomputers. In The First International Workshop on Parallel Processing, pages 322--330, Bangalore, India, Dec. 1994.
• 6: John Bircsak , Peter Craig , RaeLyn Crowell , Zarka Cvetanovic , Jonathan Harris , C. Alexander Nelson , Carl D. Offner, Extending OpenMP for NUMA machines, Proceedings of the 2000 ACM/IEEE conference on Supercomputing (CDROM), p.48-es, November 04-10, 2000, Dallas, Texas, United States
• 7: William Blume , Rudolf Eigenmann, The range test: a dependence test for symbolic, non-linear expressions, Proceedings of the 1994 conference on Supercomputing, p.528-537, December 1994, Washington, D.C., United States
• 8: Zeki Bozkus , Larry Meadows , Steven Nakamoto , Vincent Schuster , Mark Young, PGHPF—an optimizing High Performance Fortran compiler for distributed memory machines, Scientific Programming, v.6 n.1, p.29-40, Spring 1997
• 9: David Callahan , Ken Kennedy, Analysis of interprocedural side effects in a parallel programming environment, Journal of Parallel and Distributed Computing, v.5 n.5, p.517-550, October 1988 [doi>10.1016/0743-7315(88)90011-1]
• 10: B. Chapman, P. Mehrotra, and H. Zima. Enhancing OpenMP with features for Locality Control. Technical Report TR99-02, Inst. for Software Technology and Parallel Systems, U. Vienna, www.par.univie.ac.at., 1999.
• 11: A. Krishnamurthy , D. E. Culler , A. Dusseau , S. C. Goldstein , S. Lumetta , T. von Eicken , K. Yelick, Parallel programming in Split-C, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.262-273, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169724]
• 12: F. Darema, D. A. George, V. A. Norton, and G. F. Pfister. A single-program-multiple-data computational model for epex/fortran. Parallel Computing, 7(1):11--24, 1988.
• 13: Raja Das , Mustafa Uysal , Joel Saltz , Yuan-Shin Hwang, Communication optimizations for irregular scientific computations on distributed memory architectures, Journal of Parallel and Distributed Computing, v.22 n.3, p.462-478, Sept. 1994 [doi>10.1006/jpdc.1994.1104 ]
• 14: Tarek El-Ghazawi , Francois Cantonnet, UPC performance and potential: a NPB experimental study, Proceedings of the 2002 ACM/IEEE conference on Supercomputing, p.1-26, November 16, 2002, Baltimore, Maryland
• 15: T. El-Ghazawi, W. Carlson, and J. Draper. UPC Language Specifications V1.0, Feb. 2001.
• 16: Message P Forum, MPI: A Message-Passing Interface Standard, University of Tennessee, Knoxville, TN, 1994
• 17: M. Frumkin, H. Jin, and J. Yan. Implementation of NAS Parallel Benchmarks in High Performance Fortran. Technical Report NAS-98-009.
• 18: Manish Gupta , Edith Schonberg , Harini Srinivasan, A Unified Framework for Optimizing Communication in Data-Parallel Programs, IEEE Transactions on Parallel and Distributed Systems, v.7 n.7, p.689-704, July 1996 [doi>10.1109/71.508249 ]
• 19: 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 ]
• 20: High Performance Fortran Forum. High Performance Fortran language specification, version 1.0. Technical Report CRP-CTR92225, Houston, Tex., 1993.
• 21: Y. Charlie Hu , Honghui Lu , Alan L. Cox , Willy Zwaenepoel, OpenMP for networks of SMPs, Journal of Parallel and Distributed Computing, v.60 n.12, p.1512-1530, Dec. 2000 [doi>10.1006/jpdc.2000.1658 ]
• 22: H. Jin, M. Frumkin, and J. Yan. The OpenMP Implementation of NAS Parallel Benchmarks and Its Performance. Technical Report NAS-99-011.
• 23: Ken Kennedy , Nenad Nedeljkovic, Combining dependence and data-flow analyses to optimize communication, Proceedings of the 9th International Symposium on Parallel Processing, p.340-346, April 25-28, 1995
• 24: Charles H. Koelbel , David B. Loveman , Robert S. Schreiber , Guy L. Steele, Jr. , Mary E. Zosel, The high performance Fortran handbook, MIT Press, Cambridge, MA, 1994
• 25: U. Kremer. Automatic data layout for distributed memory machines. Technical Report TR96-261, 14, 1996.
• 26: S.-I. Lee, T. A. Johnson, and R. Eigenmann. Cetus - An Extensible Compiler Infrastructure for Source-to-Source Transformation. In Proc. of the Workshop on Languages and Compilers for Parallel Computing(LCPC'03), pages 539--553. (Springer-Verlag Lecture Notes in Computer Science), Oct. 2003.
• 27: Jingke Li , Marina Chen, Generating explicit communication from shared-memory program references, Proceedings of the 1990 ACM/IEEE conference on Supercomputing, p.865-876, November 12-16, 1990, New York, New York
• 28: J. Li , M. Chen, Compiling Communication-Efficient Programs for Massively Parallel Machines, IEEE Transactions on Parallel and Distributed Systems, v.2 n.3, p.361-376, July 1991 [doi>10.1109/71.86111 ]
• 29: Yuan Lin , David Padua, Compiler analysis of irregular memory accesses, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.157-168, June 18-21, 2000, Vancouver, British Columbia, Canada
• 30: Honghui Lu , Sandhya Dwarkadas , Alan L. Cox , Willy Zwaenepoel, Quantifying the performance differences between PVM and TreadMarks, Journal of Parallel and Distributed Computing, v.43 n.2, p.65-78, June 15, 1997 [doi>10.1006/jpdc.1997.1332 ]
• 31: Seung-Jai Min , Ayon Basumallik , Rudolf Eigenmann, Optimizing OpenMP programs on software distributed shared memory systems, International Journal of Parallel Programming, v.31 n.3, p.225-249, June 2003 [doi>10.1023/A:1023090719310]
• 32: S.-J. Min, A. Basumallik, and R. Eigenmann. Supporting realistic OpenMP applications on a commodity cluster of workstations. In OpenMP Shared Memory Parallel Programming: International Workshop on OpenMP Applications and Tools, WOMPAT 2003, Toronto, Canada, June 26--27, 2003. Proceedings Editors: M. J. Voss (Ed.), pages 170--179, 2003.
• 33: OpenMP Forum. OpenMP: A Proposed Industry Standard API for Shared Memory Programming. Technical report, October 1997.
• 34: Yunheung Paek , Jay Hoeflinger , David Padua, Efficient and precise array access analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.24 n.1, p.65-109, January 2002 [doi>10.1145/509705.509708]
• 35: 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]
• 36: V. Schuster and D. Miles. Distributed OpenMP, Extensions to OpenMP for SMP Clusters. In Proc. of the Workshop on OpenMP Applications and Tools (WOMPAT2000), July 2000.
• 37: Reinhard von Hanxleden , Ken Kennedy , Charles Koelbel , Raja Das , Joel H. Saltz, Compiler Analysis for Irregular Problems in Fortran D, Proceedings of the 5th International Workshop on Languages and Compilers for Parallel Computing, p.97-111, August 03-05, 1992
• 38: J. Zhu and J. Hoeflinger. Compiling for a Hybrid Programming Model Using the LMAD Representation. In Proc. of the 14th annual workshop on Languages and Compilers for Parallel Computing (LCPC2001), August 2001.

INDEX TERMS

Keywords:
MPI, OpenMP, commodity clusters, compiler techniques, performance