An efficient MPI_allgather for grids

ABSTRACT

Allgather is an important MPI collective communication. Most of the algorithms for allgather have been designed for homogeneous and tightly coupled systems. The existing algorithms for allgather on Gridsystems do not efficiently utilize the bandwidths available on slow wide-area links of the grid. In this paper, we present an algorithm for allgather on grids that efficiently utilizes wide-area bandwidths and is also wide-area optimal. Our algorithm is also adaptive to gridload dynamics since it considers transient network characteristics for dividing the nodes into clusters. Our experiments on a real-grid setup consisting of 3 sites show that our algorithm gives an average performance improvement of 52% over existing strategies.

REFERENCES

• 1: L. B.-Estefanel and G. Mounie. Identifying Logical Homogeneous Clusters for Efficient Wide-Area Communication. In In Proceedings of the Euro PVM/MPI 2004, volume LNCS Vol. 3241, pages 319--326, 2004.
• 2: O. Beaumont, V. Boudet, and Y. Robert. A Realistic Model and an Efficient Heuristic for Scheduling with Heterogenous Processors. In Proceedings of 11th Heterogeneous Computing Workshop, 2002.
• 3: G. Benson, C.-W. Chu, Q. Huang, and S. Caglar. A Comparison of MPICH Allgather Algorithms on Switched Networks, volume 2840/2003 of Lecture Notes in Computer Science, pages 335--343. Springer Berlin / Heidelberg, September 2003. Recent Advances in Parallel Virtual Machine and Message Passing Interface, 10th European PVM/MPI Users' Group Meeting.
• 4: 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]
• 5: H. Casanova. Network Modeling Issues for Grid Application Scheduling. International Journal of Foundations of Computer Science (IJFCS), 16(2):145--162, 2005.
• 6: Ernie Chan , Robert van de Geijn , William Gropp , Rajeev Thakur, Collective communication on architectures that support simultaneous communication over multiple links, Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming, March 29-31, 2006, New York, New York, USA [doi>10.1145/1122971.1122975]
• 7: David Culler , Richard Karp , David Patterson , Abhijit Sahay , Klaus Erik Schauser , Eunice Santos , Ramesh Subramonian , Thorsten von Eicken, LogP: towards a realistic model of parallel computation, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.1-12, May 19-22, 1993, San Diego, California, United States
• 8: Ahmad Faraj , Xin Yuan, Automatic generation and tuning of MPI collective communication routines, Proceedings of the 19th annual international conference on Supercomputing, June 20-22, 2005, Cambridge, Massachusetts [doi>10.1145/1088149.1088202]
• 9: R. Gupta and S. Vadhiyar. Application-Oriented Adaptive MPI_Bcast for Grids. In Proceedings of International Parallel and Distributed Processing Symposium (IPDPS'06), Rhodes Island, Greece, 2006.
• 10: L. Hollermann, T.-S. Hsu, D. Lopez, and K. Vertanen.Scheduling Problems in a Practial Allocation Model. Journal of Combinatorial Optimization, 1(2):129--149, 1997.
• 11: Exploiting Hierarchy in Parallel Computer Networks to Optimize Collective Operation Performance, Proceedings of the 14th International Symposium on Parallel and Distributed Processing, p.377, May 01-05, 2000
• 12: Thilo Kielmann , Henri E. Bal , Sergei Gorlatch , Kees Verstoep , Rutger F.H. Hofman, Network performance-aware collective communication for clustered wide-area systems, Parallel Computing, v.27 n.11, p.1431-1456, October 2001 [doi>10.1016/S0167-8191(01)00098-9]
• 13: Thilo Kielmann , Henri E. Bal , Kees Verstoep, Fast Measurement of LogP Parameters for Message Passing Platforms, Proceedings of the 15 IPDPS 2000 Workshops on Parallel and Distributed Processing, p.1176-1183, May 01-05, 2000
• 14: 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
• 15: Bruce Lowekamp , Thomas Gross , David O'Hallaron, Discovery and application of network information, Carnegie Mellon University, Pittsburgh, PA, 2000
• 16: Gabriel Mateescu, A Method for MPI Broadcast in Computational Grids, Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Workshop 13, p.251.2, April 04-08, 2005 [doi>10.1109/IPDPS.2005.45]
• 17: Mpich2 home page. http://www-unix.mcs.anl.gov/mpi/mpich2.
• 18: MPICH-G2. http://www3.niu.edu/mpi.
• 19: K. Park, H. Lee, Y. Lee, O. Kwon, S. Park, and S. K. H. W. Park. An Efficient Collective Communication Method for Grid Scale Networks. In Proceedings of the International Conference on Computational Science, pages 819--828, Melbourne, Australia and St. Petersburg, Russia, June 2003.
• 20: H. Saito , K. Taura , T. Chikayama, Collective Operations for Wide-Area Message Passing Systems Using Adaptive Spanning Trees, Proceedings of the 6th IEEE/ACM International Workshop on Grid Computing, p.40-48, November 13-14, 2005 [doi>10.1109/GRID.2005.1542722]
• 21: Martin Swany , Rich Wolski, Building Performance Topologies for Computational Grids, International Journal of High Performance Computing Applications, v.18 n.2, p.255-265, May 2004 [doi>10.1177/1094342004038957]
• 22: R. Thakur, R. Rabenseifner, and W. Gropp. Optimization of Collective Communication Operations in MPICH. International Journal of High Performance Computing Applications, 19(1):49--66, Spring 2005.

INDEX TERMS

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

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

General Terms:
Algorithms, Design, Performance

Keywords:
MPI_Allgather, grids