SafetyNet: improving the availability of shared memory multiprocessors with global checkpoint/recovery

ABSTRACT

We develop an availability solution, called SafetyNet, that uses a unified, lightweight checkpoint/recovery mechanism to support multiple long-latency fault detection schemes. At an abstract level, SafetyNet logically maintains multiple, globally consistent checkpoints of the state of a shared memory multiprocessor (i.e., processors, memory, and coherence permissions), and it recovers to a pre-fault checkpoint of the system and re-executes if a fault is detected. SafetyNet efficiently coordinates checkpoints across the system in logical time and uses "logically atomic" coherence transactions to free checkpoints of transient coherence state. SafetyNet minimizes performance overhead by pipelining checkpoint validation with subsequent parallel execution.We illustrate SafetyNet avoiding system crashes due to either dropped coherence messages or the loss of an interconnection network switch (and its buffered messages). Using full-system simulation of a 16-way multiprocessor running commercial workloads, we find that SafetyNet (a) adds statistically insignificant runtime overhead in the common-case of fault-free execution, and (b) avoids a crash when tolerated faults occur.

REFERENCES

• 1: R. E. Ahmed, R. C. Frazier, and P. N. Marinos. Cache-Aided Rollback Error Recovery (CARER) Algorithms for Shared-Memory Multiprocessor Systems. In Proceedings of the 20th International Symposium on Fault-Tolerant Computing Systems, pages 82-88, June 1990.
• 2: A. R. Alameldeen, C. J. Mauer, M. Xu, P. J. Harper, M. M. Martin, D. J. Sorin, M. D. Hill, and D. A. Wood. Evaluating Non-deterministic Multi-threaded Commercial Workloads. In Proceedings of the Fifth Workshop on Computer Architecture Evaluation Using Commercial Workloads, pages 30-38, Feb. 2002.
• 3: R. Anglada and A. Rubio. An Approach to Crosstalk Effect Analyses and Avoidance Techniques in Digital CMOS VLSI Circuits. International Journal of Electronics, 6(5):9-17, 1988.
• 4: Todd M. Austin, DIVA: a reliable substrate for deep submicron microarchitecture design, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.196-207, November 16-18, 1999, Haifa, Israel
• 5: Michel Banâtre , Alain Gefflaut , Philippe Joubert , Christine Morin , Peter A. Lee, An Architecture for Tolerating Processor Failures in Shared-Memory Multiprocessors, IEEE Transactions on Computers, v.45 n.10, p.1101-1115, October 1996 [doi>10.1109/12.543705]
• 6: Paul Barford , Mark Crovella, Generating representative Web workloads for network and server performance evaluation, Proceedings of the 1998 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.151-160, June 22-26, 1998, Madison, Wisconsin, United States
• 7: Philip A. Bernstein, Sequoia: A Fault-Tolerant Tightly Coupled Multiprocessor for Transaction Processing, Computer, v.21 n.2, p.37-45, February 1988 [doi>10.1109/2.17]
• 8: M. Bohr. Interconnect Scaling - The Real Limiter to High Performance. In Proceedings of the International Electron Devices Meeting, pages 241-244, Dec. 1995.
• 9: J. F. Cantin, M. H. Lipasti, and J. E. Smith. Dynamic Verification of Cache Coherence Protocols. In Workshop on Memory Performance Issues, June 2001. In conjunction with ISCA.
• 10: Alan Charlesworth, Starfire: Extending the SMP Envelope, IEEE Micro, v.18 n.1, p.39-49, January 1998 [doi>10.1109/40.653032]
• 11: Marcelo Cintra , José F. Martínez , Josep Torrellas, Architectural support for scalable speculative parallelization in shared-memory multiprocessors, Proceedings of the 27th annual international symposium on Computer architecture, p.13-24, June 2000, Vancouver, British Columbia, Canada
• 12: W. J. Dally, L. R. Dennison, D. Harris, K. Kan, and T. Xanthopoulos. Architecture and Implementation of Reliable Router. In Proceedings of 2nd Hot Interconnects Symposium, Aug. 1994.
• 13: T. J. Dell. A White Paper on the Benefits of Chipkill-Correct ECC for PC Server Main Memory. IBM Microelectronics Division Whitepaper, Nov. 1997.
• 14: Jose Duato , Sudhakar Yalamanchili , Lionel Ni, Interconnection Networks: An Engineering Approach, IEEE Computer Society Press, Los Alamitos, CA, 1997
• 15: E. Elnozahy, D. Johnson, and Y. Wang. A Survey Rollback-Recovery Protocols in Message-Passing Systems. Technical Report CMU-CS-96-181, Department of Computer Science, Carnegie Mellon University, Sept. 1996
• 16: 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]
• 17: S. J. Frank. Tightly Coupled Multiprocessor System Speeds Memory-access Times. Electronics, 57(1):164-169, Jan 1984.
• 18: Mike Galles, Spider: A High-Speed Network Interconnect, IEEE Micro, v.17 n.1, p.34-39, January 1997 [doi>10.1109/40.566196]
• 19: Chris Gniady , Babak Falsafi , T. N. Vijaykumar, Is SC + ILP = RC?, Proceedings of the 26th annual international symposium on Computer architecture, p.162-171, May 01-04, 1999, Atlanta, Georgia, United States
• 20: S. Gopal , T. Vijaykumar , J. Smith , G. Sohi, Speculative Versioning Cache, Proceedings of the 4th International Symposium on High-Performance Computer Architecture, p.195, January 31-February 04, 1998
• 21: Greg Grohoski, Reining in Complexity, Computer, v.31 n.1, p.41-42, January 1998
• 22: Rajiv Gupta, The fuzzy barrier: a mechanism for high speed synchronization of processors, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.54-63, April 03-06, 1989, Boston, Massachusetts, United States
• 23: R. Gustafson and F. Sparacio. IBM 3081 Processor Unit: Design Considerations and Design Process. IBM Journal of Research and Development, 26:12-21, Jan. 1982.
• 24: D. Hunt and P. Marinos. A General Purpose Cache-Aided Rollback Error Recovery (CARER) Technique. In Proceedings of the 17th International Symposium on Fault-Tolerant Computing Systems, pages 170-175, 1987.
• 25: IEEE Computer Society. IEEE Standard for Scalable Coherent Interface (SCI), Aug. 1993.
• 26: D. Jewett. Integrity S2: A Fault-Tolerant UNIX Platform. In Proceedings of the 21st International Symposium on Fault Tolerant Computing Systems, pages 512-519, June 1991.
• 27: D. Johnson. The Intel 432: A VLSI Architecture for Fault-Tolerant Computing. IEEE Computer, pages 40-48, Aug 1984.
• 28: T. Juhnke and H. Klar. Calculation of the Soft Error Rate of Submicron CMOS Logic Circuits. IEEE Journal of Solid-State Circuits, 30(7):830-834, July 1995.
• 29: Peter S. Magnusson , Magnus Christensson , Jesper Eskilson , Daniel Forsgren , Gustav Hållberg , Johan Högberg , Fredrik Larsson , Andreas Moestedt , Bengt Werner, Simics: A Full System Simulation Platform, Computer, v.35 n.2, p.50-58, February 2002 [doi>10.1109/2.982916]
• 30: Jeffrey Oplinger , David Heine , Shih Liao , Basem A. Nayfeh , Monica S. Lam , Kunle Olukotun, Software and Hardware for Exploiting Speculative Parallelism with a Multiprocessor, Stanford University, Stanford, CA, 1997
• 31: David A. Patterson , Garth Gibson , Randy H. Katz, A case for redundant arrays of inexpensive disks (RAID), Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.109-116, June 01-03, 1988, Chicago, Illinois, United States
• 32: James S. Plank , Kai Li , Michael A. Puening, Diskless Checkpointing, IEEE Transactions on Parallel and Distributed Systems, v.9 n.10, p.972-986, October 1998 [doi>10.1109/71.730527]
• 33: Dhiraj K. Pradhan, Fault-tolerant computer system design, Prentice-Hall, Inc., Upper Saddle River, NJ, 1996
• 34: Parthasarathy Ranganathan , Vijay S. Pai , Sarita V. Adve, Using speculative retirement and larger instruction windows to narrow the performance gap between memory consistency models, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.199-210, June 23-25, 1997, Newport, Rhode Island, United States [doi>10.1145/258492.258512]
• 35: Steven K. Reinhardt , Shubhendu S. Mukherjee, Transient fault detection via simultaneous multithreading, Proceedings of the 27th annual international symposium on Computer architecture, p.25-36, June 2000, Vancouver, British Columbia, Canada
• 36: J. Robertson. Alpha Particles Worry IC Makers as Device Features Keep Shrinking. Semiconductor Business News, October 21, 1998.
• 37: Eric Rotenberg, AR-SMT: A Microarchitectural Approach to Fault Tolerance in Microprocessors, Proceedings of the Twenty-Ninth Annual International Symposium on Fault-Tolerant Computing, p.84, June 15-18, 1999
• 38: O. Serlin. Fault-Tolerant Systems in Commercial Applications. IEEE Computer, pages 19-30, Aug. 1984.
• 39: K. Seshan, T. Maloney, and K. Wu. The Quality and Reliability of Intel's Quarter Micron Process. Intel Technology Journal, Sept. 1998.
• 40: L. Spainhower and T. A. Gregg. IBM S/390 Parallel Enterprise Server G5 Fault Tolerance: A Historical Perspective. IBM Journal of Research and Development, 43(5/6), September/November 1999.
• 41: J. Steffan , T Mowry, The Potential for Using Thread-Level Data Speculation to Facilitate Automatic Parallelization, Proceedings of the 4th International Symposium on High-Performance Computer Architecture, p.2, January 31-February 04, 1998
• 42: Karthik Sundaramoorthy , Zach Purser , Eric Rotenburg, Slipstream processors: improving both performance and fault tolerance, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.257-268, November 2000, Cambridge, Massachusetts, United States
• 43: Marc Tremblay, Increasing Work, Pushing the Clock, Computer, v.31 n.1, p.40-41, January 1998
• 44: Yi-Min Wang , Yennun Huang , Kiem-Phong Vo , Pe-Yu Chung , C. Kintala, Checkpointing and Its Applications, Proceedings of the Twenty-Fifth International Symposium on Fault-Tolerant Computing, p.22, June 27-30, 1995
• 45: D. Wilson, The STRATUS computer system, Resilient computing systems: vol. 1, John Wiley & Sons, Inc., New York, NY, 1986
• 46: Steven Cameron Woo , Moriyoshi Ohara , Evan Torrie , Jaswinder Pal Singh , Anoop Gupta, The SPLASH-2 programs: characterization and methodological considerations, Proceedings of the 22nd annual international symposium on Computer architecture, p.24-36, June 22-24, 1995, S. Margherita Ligure, Italy
• 47: David A. Wood , Garth A. Gibson , Randy H. Katz, Verifying a Multiprocessor Cache Controller Using Random Test Generation, IEEE Design & Test, v.7 n.4, p.13-25, July 1990 [doi>10.1109/54.57906]
• 48: K. L. Wu , W. K. Fuchs , J. H. Patel, Error Recovery in Shared Memory Multiprocessors Using Private Caches, IEEE Transactions on Parallel and Distributed Systems, v.1 n.2, p.231-240, April 1990 [doi>10.1109/71.80134]
• 49: J. F. Ziegler , H. W. Curtis , H. P. Muhlfeld , C. J. Montrose , B. Chin, IBM experiments in soft fails in computer electronics (1978–1994), IBM Journal of Research and Development, v.40 n.1, p.3-18, Jan. 1996

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Multiple-instruction-stream, multiple-data-stream processors (MIMD)

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Shared memory
  B.8 Performance and Reliability
      B.8.1 Reliability, Testing, and Fault-Tolerance

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.5 Reliability
          Subjects: Checkpoint/restart

General Terms:
Design, Performance, Reliability, Theory

Keywords:
availability, shared memory, multiprocessor