Scalable, fault tolerant membership for MPI tasks on HPC systems

ABSTRACT

Reliability is increasingly becoming a challenge for high-performance computing (HPC) systems with thousands of nodes, such as IBM's Blue Gene/L. A shorter mean-time-to-failure can be addressed by adding fault tolerance to reconfigure working nodes to ensure that communication and computation can progress. However, existing approaches fall short in providing scalability and small recon guration overhead within the fault-tolerant layer.This paper contributes a scalable approach to recon gure the communication infrastructure after node failures. We propose a decentralized (peer-to-peer) protocol that maintains a consistent view of active nodes in the presence of faults. Our protocol shows response times in the order of hundreds of microseconds and single-digit milliseconds for recon guration using MPI over BlueGene/L and TCP over Gigabit, respectively. The protocol can be adapted to match the network topology to further increase performance. We also verify experimental results against a performance model, which demonstrates the scalability of the approach. Hence, the membership service is suitable for deployment in the communication layer of MPI runtime systems, and we have integrated an early version into LAM/MPI.

REFERENCES

• 1: http://www.intel.com/design/servers/ipmi/index.htm.
• 2: http://www.redbooks.ibm.com/redbooks/pdfs/sg246686.pdf.
• 3: The ASCI purple benchmarks. http://www.llnl.gov/asci/purple/benchmarks, 2002.
• 4: N. Adiga and et al. An overview of the BlueGene/L supercomputer. In Supercomputing, Nov. 2002.
• 5: Y. Amir , L. E. Moser , P. M. Melliar-Smith , D. A. Agarwal , P. Ciarfella, The Totem single-ring ordering and membership protocol, ACM Transactions on Computer Systems (TOCS), v.13 n.4, p.311-342, Nov. 1995 [doi>10.1145/210223.210224]
• 6: R. T. Aulwes, D. J. Daniel, N. N. Desai, R. L. Graham, L. D. Risinger, M. A. Taylor, T. S. Woodall, and M. W. Sukalski. Architecture of LA-MPI, a network-fault-tolerant MPI. In International Parallel and Distributed Processing Symposium, 2004.
• 7: B. Barrett, J. M. Squyres, A. Lumsdaine, R. L. Graham, and G. Bosilca. Analysis of the component architecture overhead in Open MPI. In Proceedings, 12th European PVM/MPI Users' Group Meeting, Sorrento, Italy, September 2005.
• 8: Nina T. Bhatti , Matti A. Hiltunen , Richard D. Schlichting , Wanda Chiu, Coyote: a system for constructing fine-grain configurable communication services, ACM Transactions on Computer Systems (TOCS), v.16 n.4, p.321-366, Nov. 1998 [doi>10.1145/292523.292524]
• 9: Kenneth P. Birman , Robert V. Renesse , Robbert Van Renesse, Reliable Distributed Computing with the ISIS Toolkit, IEEE Computer Society Press, Los Alamitos, CA, 1994
• 10: George Bosilca , Aurelien Bouteiller , Franck Cappello , Samir Djilali , Gilles Fedak , Cecile Germain , Thomas Herault , Pierre Lemarinier , Oleg Lodygensky , Frederic Magniette , Vincent Neri , Anton Selikhov, MPICH-V: toward a scalable fault tolerant MPI for volatile nodes, Proceedings of the 2002 ACM/IEEE conference on Supercomputing, p.1-18, November 16, 2002, Baltimore, Maryland
• 11: Greg Bronevetsky , Daniel Marques , Keshav Pingali , Paul Stodghill, Automated application-level checkpointing of MPI programs, Proceedings of the ninth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 11-13, 2003, San Diego, California, USA
• 12: Greg Bronevetsky , Daniel Marques , Keshav Pingali , Paul Stodghill, Collective operations in application-level fault-tolerant MPI, Proceedings of the 17th annual international conference on Supercomputing, June 23-26, 2003, San Francisco, CA, USA [doi>10.1145/782814.782847]
• 13: S. Chakravorty, C. Mendes, and L. Kale. Proactive fault tolerance in large systems. In HPCRI: 1st Workshop on High Performance Computing Reliability Issues, in Proceedings of the 11th International Symposium on High Performance Computer Architecture (HPCA-11). IEEE Computer Society, 2005.
• 14: G. V. Chockler, I. Keidar, and R. Vitenberg. Group communication speci cations: A comprehensive study, Apr. 23 2001.
• 15: F. Cristian. Reaching agreement on processor group membership in synchronous distributed systems, June 12 1991.
• 16: David E. Culler , Richard M. Karp , David Patterson , Abhijit Sahay , Eunice E. Santos , Klaus Erik Schauser , Ramesh Subramonian , Thorsten von Eicken, LogP: a practical model of parallel computation, Communications of the ACM, v.39 n.11, p.78-85, Nov. 1996 [doi>10.1145/240455.240477]
• 17: 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
• 18: Xavier Défago , André Schiper , Péter Urbán, Total order broadcast and multicast algorithms: Taxonomy and survey, ACM Computing Surveys (CSUR), v.36 n.4, p.372-421, December 2004 [doi>10.1145/1041680.1041682]
• 19: Nirmit Desai , Frank Mueller, A Log(n) Multi-Mode Locking Protocol for Distributed Systems, Proceedings of the 17th International Symposium on Parallel and Distributed Processing, p.4, April 22-26, 2003
• 20: Nirmit Desai , Frank Mueller, Scalable Distributed Concurrency Services for Hierarchical Locking, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.530, May 19-22, 2003
• 21: Nirmit Desai , Frank Mueller, Scalable hierarchical locking for distributed systems, Journal of Parallel and Distributed Computing, v.64 n.6, p.708-724, June 2004 [doi>10.1016/j.jpdc.2003.10.001]
• 22: J. Duell. The design and implementation of berkeley lab's linux checkpoint/restart. Tr, Lawrence Berkeley National Laboratory, 2000.
• 23: J. Duell, P. H. Hargrove, and E. S. Roman. Requirements for linux checkpoint/restart, May 20 2002.
• 24: C. Engelmann , Stephen Scott , G. A. Geist, II, Distributed Peer-to-Peer Control in Harness, Proceedings of the International Conference on Computational Science-Part II, p.720-728, April 21-24, 2002
• 25: Graham E. Fagg , Jack Dongarra, FT-MPI: Fault Tolerant MPI, Supporting Dynamic Applications in a Dynamic World, Proceedings of the 7th European PVM/MPI Users' Group Meeting on Recent Advances in Parallel Virtual Machine and Message Passing Interface, p.346-353, January 2000
• 26: R. Friedman and R. van Renesse. Strong and weak virtual synchrony in horus. Technical Report TR95--1537, Cornell University, Computer Science Department, Aug. 24, 1995.
• 27: E. Gabriel, G. E. Fagg, G. Bosilca, T. Angskun, J. J. Dongarra, J. M. Squyres, V. Sahay, P. Kambadur, B. Barrett, A. Lumsdaine, R. H. Castain, D. J. Daniel, R. L. Graham, and T. S. Woodall. Open MPI: Goals, concept, and design of a next generation MPI implementation. In Proceedings, 11th European PVM/MPI Users' Group Meeting, pages 97 (104, Budapest, Hungary, September 2004.
• 28: William Gropp , Ewing Lusk , Nathan Doss , Anthony Skjellum, A high-performance, portable implementation of the MPI message passing interface standard, Parallel Computing, v.22 n.6, p.789-828, Sept. 1996 [doi>10.1016/0167-8191(96)00024-5]
• 29: IBM T. J. Watson. Personal communications. July 2005.
• 30: I. Keidar. Group communication, June 12 2000.
• 31: Idit Keidar , Jeremy Sussman , Keith Marzullo , Danny Dolev, A Client-Server Oriented Algorithm for Virtually Synchronous Group Membership in WANs, Proceedings of the The 20th International Conference on Distributed Computing Systems ( ICDCS 2000), p.356, April 10-13, 2000
• 32: Roger I. Khazan, Group membership: a novel approach and the first single-round algorithm, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011819]
• 33: Roger I. Khazan , Roger Khazan , Sophia Yuditskaya, Using Leader-Based Communication to Improve the Scalability of Single-Round Group Membership Algorithms, Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Workshop 16, p.280.2, April 04-08, 2005 [doi>10.1109/IPDPS.2005.445]
• 34: D. Malki, D. Dolev, and R. Strong. A framework for partitionable membership service, Aug. 19 1995.
• 35: S. McCanne and S. Floyd. VINT Network Simulator - ns (version 2). http://www-mash.CS.Berkeley.EDU/ns/, Apr. 1999.
• 36: S. Mishra, L. L. Peterson, and R. D. Schlichting. Consul: a communication substrate for fault-tolerant distributed programs. Distributed Systems Engineering, 1(2):87 (103, Dec. 1993.
• 37: Frank Mueller, Fault-Tolerance for Token-based Synchronization Protocols, Proceedings of the 15th International Parallel & Distributed Processing Symposium, p.125, April 23-27, 2001
• 38: Philip C. Roth , Dorian C. Arnold , Barton P. Miller, MRNet: A Software-Based Multicast/Reduction Network for Scalable Tools, Proceedings of the 2003 ACM/IEEE conference on Supercomputing, p.21, November 15-21, 2003
• 39: S. Sankaran, J. M. Squyres, B. Barrett, A. Lumsdaine, J. Duell, P. Hargrove, and E. Roman. The LAM/MPI checkpoint/restart framework: System-initiated checkpointing. In Proceedings, LACSI Symposium, Sante Fe, New Mexico, USA, October 2003.
• 40: J. M. Squyres and A. Lumsdaine. A Component Architecture for LAM/MPI. In Proceedings, 10th European PVM/MPI Users' Group Meeting, number 2840 in Lecture Notes in Computer Science, pages 379 (387, Venice, Italy, September / October 2003. Springer-Verlag.
• 41: Georg Stellner, CoCheck: Checkpointing and Process Migration for MPI, Proceedings of the 10th International Parallel Processing Symposium, p.526-531, April 15-19, 1996
• 42: S. Toueg and T. D. Chandra. Unreliable failure detectors for reliable distributed systems, June 18 1996.
• 43: T. Woodall, R. Graham, R. Castain, D. Daniel, M. Sukalski, G. Fagg, E. Gabriel, G. Bosilca, T. Angskun, J. Dongarra, J. Squyres, V. Sahay, P. Kambadur, B. Barrett, and A. Lumsdaine. Open MPI's TEG point-to-point communications methodology: Comparison to existing implementations. In Proceedings, 11th European PVM/MPI Users' Group Meeting, pages 105 (111, Budapest, Hungary, September 2004.
• 44: T. Woodall, R. Graham, R. Castain, D. Daniel, M. Sukalski, G. Fagg, E. Gabriel, G. Bosilca, T. Angskun, J. Dongarra, J. Squyres, V. Sahay, P. Kambadur, B. Barrett, and A. Lumsdaine. TEG: A high-performance, scalable, multi-network point-to-point communications methodology. In Proceedings, 11th European PVM/MPI Users' Group Meeting, pages 303 (310, Budapest, Hungary, September 2004.
• 45: T. Yang, J. Zhou, and L. Chu. An ef cient topology-adaptive membership protocol for large-scale network services. Technical report, University of California, Santa Barbara, Computer Science, June 2004.
• 46: Jingyu Zhou , Lingkun Chu , Tao Yang, An Efficient Topology-Adaptive Membership Protocol for Large-Scale Cluster-Based Services, Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Papers, p.57.2, April 04-08, 2005 [doi>10.1109/IPDPS.2005.92]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.5 Reliability
          Subjects: Fault-tolerance

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Modeling and prediction; Measurements

General Terms:
Measurement, Performance, Reliability

Keywords:
group communication, high-performance computing, message passing, node failure, reliability, scalability