HPC-Colony: services and interfaces for very large systems

ABSTRACT

Traditional full-featured operating systems are known to have properties that limit the scalability of distributed memory parallel programs, the most common programming paradigm utilized in high end computing. Furthermore, as processor counts increase with the most capable systems, the necessary activity to manage the system becomes more of a burden. To make a general purpose operating system scale to such levels, new technology is required for parallel resource management and global system management (including fault management). In this paper, we describe the shortcomings of full-featured operating systems and runtime systems and discuss an approach to scale such systems to one hundred thousand processors with both scalable parallel application performance and efficient system management.

REFERENCES

• 1: C. Huang, O. Lawlor, and L. V. Kalé, "Adaptive MPI," in Proceedings of the 16th International Workshop on Languages and Compilers for Parallel Computing (LCPC 2003), LNCS 2958, (College Station, Texas), pp. 306--322, October 2003.
• 2: James C. Phillips , Gengbin Zheng , Sameer Kumar , Laxmikant V. Kalé, NAMD: biomolecular simulation on thousands of processors, Proceedings of the 2002 ACM/IEEE conference on Supercomputing, p.1-18, November 16, 2002, Baltimore, Maryland
• 3: R. K. Brunner and L. V. Kalé, "Handling application-induced load imbalance using parallel objects," in Parallel and Distributed Computing for Symbolic and Irregular Applications, pp. 167--181, World Scientific Publishing, 2000.
• 4: G. Zheng, Achieving High Performance on Extremely Large Parallel Machines: Performance Prediction and Load Balancing. PhD thesis, Department of Computer Science, University of Illinois at Urbana-Champaign, 2005.
• 5: T. Agarwal, A. Sharma, and L. V. Kalé, "Topology-aware task mapping for reducing communication contention on large parallel machines," in Proceedings of IEEE International Parallel and Distributed Processing Symposium 2006, April 2006.
• 6: C. Huang, "System support for checkpoint and restart of charm++ and ampi applications," Master's thesis, Dept. of Computer Science, University of Illinois, 2004.
• 7: Gengbin Zheng , Lixia Shi , L. V. Kale, FTC-Charm++: an in-memory checkpoint-based fault tolerant runtime for Charm++ and MPI, Proceedings of the 2004 IEEE International Conference on Cluster Computing, p.93-103, September 20-23, 2004
• 8: S. Chakravorty and L. V. Kale, "A fault tolerant protocol for massively parallel machines," in FTPDS Workshop for IPDPS 2004, IEEE Press, 2004.
• 9: P. Apparao and G. Averill, "Firmware-based platform reliability." Intel white paper, October 2004.
• 10: R. K. Sahoo , A. J. Oliner , I. Rish , M. Gupta , J. E. Moreira , S. Ma , R. Vilalta , A. Sivasubramaniam, Critical event prediction for proactive management in large-scale computer clusters, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956799]
• 11: A. J. Oliner, R. K. Sahoo, J. E. Moreira, M. Gupta, and A. Sivasubramaniam, "Fault-aware job scheduling for BlueGene/L systems," Tech. Rep. RC23077, IBM Research, January (2004).
• 12: T. Jones, J. Fier, and L. Brenner, "Observed impacts of operating systems on the scalability of applications," Tech. Rep. UCRL-MI-202629, Lawrence Livermore National Laboratory, March 2003.
• 13: Paul Terry , Amar Shan , Pentti Huttunen, Improving application performance on HPC systems with process synchronization, Linux Journal, v.2004 n.127, p.3, November 2004
• 14: Terry Jones , Shawn Dawson , Rob Neely , William Tuel , Larry Brenner , Jeffrey Fier , Robert Blackmore , Patrick Caffrey , Brian Maskell , Paul Tomlinson , Mark Roberts, Improving the Scalability of Parallel Jobs by adding Parallel Awareness to the Operating System, Proceedings of the 2003 ACM/IEEE conference on Supercomputing, p.10, November 15-21, 2003
• 15: A. W. Cook and W. H. Cabot, "Large scale simulations with miranda on Blue Gene/L," Tech. Rep. UCRL-PRES-200327, Lawrence Livermore National Laboratory, 2003.
• 16: J. Moreira et al, "Blue Gene/L programming and operating environment," IBM Journal of Research and Development, vol. 49, no. 2/3, pp. 367--376, 2005.
• 17: Y.-C. Chow and W. H. Kohler, "Models for dynamic load balancing in homogeneous multiple processor systems," in IEEE Transactions on Computers, vol. c-36, pp. 667--679, May 1982.
• 18: L. M. Ni and K. Hwang, "Optimal Load Balancing in a Multiple Processor System with Many Job Classes," in IEEE Trans. on Software Eng., vol. SE-11, 1985.
• 19: Antonio Corradi , Letizia Leonardi , Franco Zambonelli, Diffusive Load-Balancing Policies for Dynamic Applications, IEEE Concurrency, v.7 n.1, p.22-31, January 1999 [doi>10.1109/4434.749133 ]
• 20: A. Ha'c and X. Jin, "Dynamic Load Balancing in Distributed System Using a Decentralized Algorithm," in Proc. of 7-th Intl. Conf. on Distributed Computing Systems, April 1987.
• 21: A. Sinha and L. Kalé, "A load balancing strategy for prioritized execution of tasks," in International Parallel Processing Symposium, (New Port Beach, CA.), pp. 230--237, April 1993.
• 22: M. H. Willebeek-LeMair , A. P. Reeves, Strategies for Dynamic Load Balancing on Highly Parallel Computers, IEEE Transactions on Parallel and Distributed Systems, v.4 n.9, p.979-993, September 1993 [doi>10.1109/71.243526 ]
• 23: A. Basermann, J. Clinckemaillie, T. Coupez, J. Fingberg, H. Digonnet, R. Ducloux, J.-M. Gratien, U. Hartmann, G. Lonsdale, B. Maerten, D. Roose, and C. Walshaw, "Dynamic load balancing of finite element applications with the DRAMA Library," in Applied Math. Modeling, vol. 25, pp. 83--98, 2000.
• 24: Karen D. Devine , Erik G. Boman , Robert T. Heaphy , Bruce A. Hendrickson , James D. Teresco , Jamal Faik , Joseph E. Flaherty , Luis G. Gervasio, New challanges in dynamic load balancing, Applied Numerical Mathematics, v.52 n.2-3, p.133-152, February 2005 [doi>10.1016/j.apnum.2004.08.028]
• 25: P. Colella, D. Graves, T. Ligocki, D. Martin, D. Modiano, D. Serafini, and B. Van Straalen, "Chombo Software Package for AMR Applications Design Document," 2003. http://seesar.lbl.gov/anag/chombo/ChomboDesign-1.4. pdf.
• 26: F. Ercal , J. Ramanujam , P. Sadayappan, Task allocation onto a hypercube by recursive mincut bipartitioning, Proceedings of the third conference on Hypercube concurrent computers and applications: Architecture, software, computer systems, and general issues, p.210-221, January 19-20, 1988, Pasadena, California, United States [doi>10.1145/62297.62323]
• 27: Jr,R. P. Bianchini , J. P. Shen, Interprocessing traffic scheduling algorithm for multiple-processor networks, IEEE Transactions on Computers, v.36 n.4, p.396-409, April 1987 [doi>10.1109/TC.1987.1676922]
• 28: Z. Fang , X. Li , L. M. Ni, On the Communication Complexity of Generalized 2-D Convolution on Array Processors, IEEE Transactions on Computers, v.38 n.2, p.184-194, February 1989 [doi>10.1109/12.16495 ]
• 29: Georg Stellner, CoCheck: Checkpointing and Process Migration for MPI, Proceedings of the 10th International Parallel Processing Symposium, p.526-531, April 15-19, 1996
• 30: Adnan Agbaria , Roy Friedman, Starfish: Fault-Tolerant Dynamic MPI Programs on Clusters of Workstations, Cluster Computing, v.6 n.3, p.227-236, July 2003 [doi>10.1023/A:1023540604208 ]
• 31: Yuqun Chen , James S. Plank , Kai Li, CLIP: a checkpointing tool for message-passing parallel programs, Proceedings of the 1997 ACM/IEEE conference on Supercomputing (CDROM), p.1-11, November 15-21, 1997, San Jose, CA [doi>10.1145/509593.509626]
• 32: Rob Strom , Shaula Yemini, Optimistic recovery in distributed systems, ACM Transactions on Computer Systems (TOCS), v.3 n.3, p.204-226, Aug. 1985 [doi>10.1145/3959.3962]
• 33: Graham E. Fagg , Jack J. Dongarra, Building and Using a Fault-Tolerant MPI Implementation, International Journal of High Performance Computing Applications, v.18 n.3, p.353-361, August 2004 [doi>10.1177/1094342004046052]
• 34: Rajanikanth Batchu , Anthony Skjellum , Zhenqian Cui , Murali Beddhu , Jothi P. Neelamegam , Yoginder Dandass , Manoj Apte, MPI/FTTM: Architecture and Taxonomies for Fault-Tolerant, Message-Passing Middleware for Performance-Portable Parallel Computing, Proceedings of the 1st International Symposium on Cluster Computing and the Grid, p.26, May 15-18, 2001
• 35: S. Louca, N. Neophytou, A. Lachanas, and P. Evripidou, "MPI-FT: Portable fault tolerance scheme for MPI," Parallel Processing Letters, vol. 10, no. 4, pp. 371--382, 2000.
• 36: Bouteiller Bouteiller , Franck Cappello , Thomas Herault , Krawezik Krawezik , Pierre Lemarinier , Magniette Magniette, MPICH-V2: a Fault Tolerant MPI for Volatile Nodes based on Pessimistic Sender Based Message Logging, Proceedings of the 2003 ACM/IEEE conference on Supercomputing, p.25, November 15-21, 2003
• 37: Elmootazbellah N. Elnozahy , Willy Zwaenepoel, Manetho: Transparent Roll Back-Recovery with Low Overhead, Limited Rollback, and Fast Output Commit, IEEE Transactions on Computers, v.41 n.5, p.526-531, May 1992 [doi>10.1109/12.142678 ]
• 38: S. Chakravorty, C. L. Mendes, and L. V. Kalé, "Proactive fault tolerance in MPI applications via task migration," 2006. Submitted to publication.
• 39: J. K. Ousterhout, "Scheduling techniques for concurrent systems," in Third International Conference on Distributed Computing Systems, pp. 22--30, May 1982.
• 40: P. G. Sobalvarro, S. Pakin, W. E. Weihl, and A. A. Chien, "Dynamic co-scheduling on workstation clusters," Tech. Rep. 1997-017, Digital Systems Research Center, March 1997.
• 41: Fabrizio Petrini , Darren J. Kerbyson , Scott Pakin, The Case of the Missing Supercomputer Performance: Achieving Optimal Performance on the 8,192 Processors of ASCI Q, Proceedings of the 2003 ACM/IEEE conference on Supercomputing, p.55, November 15-21, 2003
• 42: K. London, S. Moore, D. Terpstra, and J. Dongarra, "Support for simultaneous multiple substrate performance monitoring," October 2005. Poster Session at LACSI Symposium 2005.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.7 Organization and Design
          Subjects: Distributed systems

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Concurrency
      D.4.2 Storage Management
          Subjects: Distributed memories
      D.4.5 Reliability
          Subjects: Fault-tolerance

General Terms:
Design, Management, Performance, Reliability