Dyn-MPI: Supporting MPI on Non Dedicated Clusters

ABSTRACT

Distributing data is a fundamental problem in implementing efficient distributed-memory parallel programs. The problem becomes more difficult in environments where the participating nodes are not dedicated to a parallel application. We are investigating the data distribution problem in non dedicated environments in the context of explicit message-passing programs. To address this problem, we have designed and implemented an extension to MPI called Dynamic MPI (Dyn-MPI). The key component of Dyn-MPI is its run-time system, which efficiently and automatically redistributes data on the fly when there are changes in the application or the underlying environment. Dyn-MPI supports efficient memory allocation, precise measurement of system load and computation time, and node removal. Performance results show that programs that use Dyn-MPI execute efficiently in non dedicated environments, including up to almost a three-fold improvement compared to programs that do not redistribute data and a 25% improvement over standard adaptive load balancing techniques.

REFERENCES

• 1: [1] Message Passing Interface Forum MPIF. MPI-2: Extensions to the Message-Passing Interface. Technical Report, University of Tennessee, Knoxville, 1996.
• 2: Umit Rencuzogullari , Sandhya Dwardadas, Dynamic adaptation to available resources for parallel computing in an autonomous network of workstations, Proceedings of the eighth ACM SIGPLAN symposium on Principles and practices of parallel programming, p.72-81, June 2001, Snowbird, Utah, United States
• 3: [3] Saman P. Amarasinghe, Jennifer M. Anderson, Monica S. Lam, and Chau-Wen Tseng. The SUIF compiler for scalable parallel machines. In Proceedings of the Seventh SIAM Conference on Parallel Processing for Scientific Computing, February 1995.
• 4: [4] High Performance Fortran language specification. November 1994.
• 5: 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]
• 6: Donald G. Morris , David K. Lowenthal, Accurate data redistribution cost estimation in software distributed shared memory systems, Proceedings of the eighth ACM SIGPLAN symposium on Principles and practices of parallel programming, p.62-71, June 2001, Snowbird, Utah, United States
• 7: 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
• 8: 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]
• 9: Seema Hiranandani , Ken Kennedy , Chau-Wen Tseng, Compiling Fortran D for MIMD distributed-memory machines, Communications of the ACM, v.35 n.8, p.66-80, Aug. 1992 [doi>10.1145/135226.135230]
• 10: Vasanth Balasundaram , Geoffrey Fox , Ken Kennedy , Ulrich Kremer, A static performance estimator to guide data partitioning decisions, Proceedings of the third ACM SIGPLAN symposium on Principles and practice of parallel programming, p.213-223, April 21-24, 1991, Williamsburg, Virginia, United States
• 11: Manish Gupta , Prithviraj Banerjee, PARADIGM: a compiler for automatic data distribution on multicomputers, Proceedings of the 7th international conference on Supercomputing, p.87-96, July 19-23, 1993, Tokyo, Japan [doi>10.1145/165939.165959]
• 12: Jennifer M. Anderson , Monica S. Lam, Global optimizations for parallelism and locality on scalable parallel machines, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.112-125, June 21-25, 1993, Albuquerque, New Mexico, United States
• 13: Ken Kennedy , Ulrich Kremer, Automatic data layout for distributed-memory machines, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.4, p.869-916, July 1998 [doi>10.1145/291891.291901]
• 14: Daniel J. Palermo , Prithviraj Banerjee, Automatic Selection of Dynamic Data Partitioning Schemes for Distributed-Memory Multicomputers, Proceedings of the 8th International Workshop on Languages and Compilers for Parallel Computing, p.392-406, August 10-12, 1995
• 15: Jordi Garcia , Eduard Ayguade , Jesus Labarta, Dynamic data distribution with control flow analysis, Proceedings of the 1996 ACM/IEEE conference on Supercomputing (CDROM), p.11-es, January 01-01, 1996, Pittsburgh, Pennsylvania, United States [doi>10.1145/369028.369048]
• 16: [16] Gary Shao, Rich Wolski, and Fran Berman. Modeling the cost of redistribution in scheduling. In Eighth SIAM Conference on Parallel Processing for Scientific Computation, March 1997.
• 17: [17] Guy Edjlali, Gagan Agrawal, Alan Sussman, Jim Humphries, and Joel Saltz. Runtime and compiler support for programming in adaptive parallel environments. Scientific Programming, 6(2):215-227, 1997.
• 18: Rich Wolski , Neil Spring , Jim Hayes, Predicting the CPU Availability of Time-Shared Unix Systems on the Computational Grid, Proceedings of the 8th IEEE International Symposium on High Performance Distributed Computing, p.12, August 03-06, 1999
• 19: Alex Scherer , Honghui Lu , Thomas Gross , Willy Zwaenepoel, Transparent adaptive parallelism on NOWs using OpenMP, Proceedings of the seventh ACM SIGPLAN symposium on Principles and practice of parallel programming, p.96-106, May 04-06, 1999, Atlanta, Georgia, United States
• 20: [20] Bongki Moon and Joel Saltz. Adaptive runtime support for direct simulation monte carlo methods on distributed memory architectures. In Scalable High Performance Computing Conference, pages 176-183, May 1994.
• 21: Kai Li , Paul Hudak, Memory coherence in shared virtual memory systems, ACM Transactions on Computer Systems (TOCS), v.7 n.4, p.321-359, Nov. 1989 [doi>10.1145/75104.75105]
• 22: Milind A. Bhandarkar , Laxmikant V. Kalé , Eric de Sturler , Jay Hoeflinger, Adaptive Load Balancing for MPI Programs, Proceedings of the International Conference on Computational Science-Part II, p.108-117, May 28-30, 2001
• 23: [23] Orion Lawlor, Milind Bhandarkar, and L. V. Kale. Adaptive MPI. TR 02-05, University of Illinois, 2002.
• 24: Laxmikant V. Kale , Sanjeev Krishnan, CHARM++: a portable concurrent object oriented system based on C++, Proceedings of the eighth annual conference on Object-oriented programming systems, languages, and applications, p.91-108, September 26-October 01, 1993, Washington, D.C., United States
• 25: [25] Jian Ke and Evan Speight. Tern: Migrating threads in an MPI runtime environment. Technical Report CSL-TR-2001-1016, Cornell, November 2001.
• 26: Gregory W. Price , David K. Lowenthal, A comparative analysis of fine-grain threads packages, Journal of Parallel and Distributed Computing, v.63 n.11, p.1050-1063, November 2003 [doi>10.1016/j.jpdc.2003.06.001]
• 27: [27] D. Brent Weatherly, David K. Lowenthal, and Franklin Lowenthal. Dyn-MPI: Supporting MPI on non dedicated clusters (extended version). Technical Report 03-003, University of Georgia, January 2003.
• 28: [28] D. Bailey, J. Barton, T. Lasinski, and H. Simon. The NAS parallel benchmarks. RNR-91-002, NASA Ames Research Center, August 1991.
• 29: Jaswinder Pal Singh , John L. Hennessy , Anoop Gupta, Scaling Parallel Programs for Multiprocessors: Methodology and Examples, Computer, v.26 n.7, p.42-50, July 1993 [doi>10.1109/MC.1993.274941]
• 30: Jaswinder P Singh , Wolf Weber , Anoop Gupta, SPLASH: Stanford parallel applications for shared-memory, Stanford University, Stanford, CA, 1991