A light-weight cache-based fault detection and checkpointing scheme for MPSoCs enabling relaxed execution synchronization

ABSTRACT

While technology advances have made MPSoCs a standard architecture for embedded systems, their applicability is increasingly being challenged by dramatic increases in the amount of device failures that may occur during execution. Conventional fault tolerance techniques employ a duplication-and-comparison strategy to detect arbitrary execution faults, as well as a checkpointing-and-rollback strategy to recover from the faulty state. Comparison and checkpointing are performed either at task level, thus imposing a large amount of overhead in verifying and backing up memory pages, or at instruction level, thus necessitating a lock-step execution model which significantly limits the attainable performance. To overcome the shortcomings of both strategies, in this paper we propose a cache-based fault tolerance scheme wherein the comparison and checkpointing process is performed at the cache-memory interface. By allowing two processors that execute duplicated tasks to share a single data cache, the proposed scheme is able to verify execution results before writing them back into memory, thus protecting the memory from being polluted by execution faults. This in turn significantly reduces the checkpointing overhead. Meanwhile, since only the data written into memory are compared, the strict instruction-by-instruction synchronization model used in multithreading processors can be relaxed. The simulation results confirm that the proposed scheme only imposes a performance overhead ranging from 1.4% to 10.4%, while both fault detection and execution checkpointing can be effectively attained.

REFERENCES

• 1: Wayne Wolf, The future of multiprocessor systems-on-chips, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996753]
• 2: International Technology Roadmap for Semiconductors (ITRS), 2007 Edition. "Process integration, devices, and structures".
• 3: Premkishore Shivakumar , Michael Kistler , Stephen W. Keckler , Doug Burger , Lorenzo Alvisi, Modeling the Effect of Technology Trends on the Soft Error Rate of Combinational Logic, Proceedings of the 2002 International Conference on Dependable Systems and Networks, p.389-398, June 23-26, 2002
• 4: Kent D. Wilken , Timothy Kong, Concurrent Detection of Software and Hardware Data-Access Faults, IEEE Transactions on Computers, v.46 n.4, p.412-424, April 1997 [doi>10.1109/12.588046]
• 5: 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
• 6: Shubhendu S. Mukherjee , Michael Kontz , Steven K. Reinhardt, Detailed design and evaluation of redundant multithreading alternatives, Proceedings of the 29th annual international symposium on Computer architecture, May 25-29, 2002, Anchorage, Alaska
• 7: T. N. Vijaykumar , Irith Pomeranz , Karl Cheng, Transient-fault recovery using simultaneous multithreading, Proceedings of the 29th annual international symposium on Computer architecture, May 25-29, 2002, Anchorage, Alaska
• 8: Mohamed Gomaa , Chad Scarbrough , T. N. Vijaykumar , Irith Pomeranz, Transient-fault recovery for chip multiprocessors, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 9: A. Wood, "Data integrity concepts, features, and technology," White paper, Tandem divison, Compaq Computer Corporation.
• 10: Nicholas S. Bowen , Dhiraj K. Pradhan, Virtual Checkpoints: Architecture and Performance, IEEE Transactions on Computers, v.41 n.5, p.516-525, May 1992 [doi>10.1109/12.142677]
• 11: P. A. Lee , N. Ghani , K. Heron, A Recovery Cache for the PDP-11, IEEE Transactions on Computers, v.29 n.6, p.546-549, June 1980 [doi>10.1109/TC.1980.1675618]
• 12: Ying Zhang , Krishnendu Chakrabarty, Energy-Aware Adaptive Checkpointing in Embedded Real-Time Systems, Proceedings of the conference on Design, Automation and Test in Europe, p.10918, March 03-07, 2003
• 13: D. B. Hunt and P. N. Marinos, "A general purpose cache-aided rollback error recovery (CARER) technique," In Proc. FTCS-17, pp. 170--175, 1987.
• 14: 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]
• 15: Chunho Lee , Miodrag Potkonjak , William H. Mangione-Smith, MediaBench: a tool for evaluating and synthesizing multimedia and communicatons systems, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.330-335, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 16: Todd Austin , Eric Larson , Dan Ernst, SimpleScalar: An Infrastructure for Computer System Modeling, Computer, v.35 n.2, p.59-67, February 2002 [doi>10.1109/2.982917]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Fault tolerance

General Terms:
Design, Performance, Reliability

Keywords:
checkpointing, fault detection, fault recovery