Understanding prediction-based partial redundant threading for low-overhead, high- coverage fault tolerance

ABSTRACT

Redundant threading architectures duplicate all instructions to detect and possibly recover from transient faults. Several lighter weight Partial Redundant Threading (PRT) architectures have been proposed recently. (i) Opportunistic Fault Tolerance duplicates instructions only during periods of poor single-thread performance. (ii) ReStore does not explicitly duplicate instructions and instead exploits mispredictions among highly confident branch predictions as symptoms of faults. (iii) Slipstream creates a reduced alternate thread by replacing many instructions with highly confident predictions. We explore PRT as a possible direction for achieving the fault tolerance of full duplication with the performance of single-thread execution. Opportunistic and ReStore yield partial coverage since they are restricted to using only partial duplication or only confident predictions, respectively. Previous analysis of Slipstream fault tolerance was cursory and concluded that only duplicated instructions are covered. In this paper, we attempt to better understand Slipstream's fault tolerance, conjecturing that the mixture of partial duplication and confident predictions actually closely approximates the coverage of full duplication. A thorough dissection of prediction scenarios confirms that faults in nearly 100% of instructions are detectable. Fewer than 0.1% of faulty instructions are not detectable due to coincident faults and mispredictions. Next we show that the current recovery implementation fails to leverage excellent detection capability, since recovery sometimes initiates belatedly, after already retiring a detected faulty instruction. We propose and evaluate a suite of simple microarchitectural alterations to recovery and checking. Using the best alterations, Slipstream can recover from faults in 99% of instructions, compared to only 78% of instructions without alterations. Both results are much higher than predicted by past research, which claims coverage for only duplicated instructions, or 65% of instructions. On an 8-issue SMT processor, Slipstream performs within 1.3% of single-thread execution whereas full duplication slows performance by 14%.A key byproduct of this paper is a novel analysis framework in which every dynamic instruction is considered to be hypothetically faulty, thus not requiring explicit fault injection. Fault coverage is measured in terms of the fraction of candidate faulty instructions that are directly or indirectly detectable before.

REFERENCES

• 1: 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
• 2: D. Burger, T.M. Austin, and S. Bennett. The Simplescalar Toolset, Version 2. Tech. Report CS-TR-1997-1342, CS Department, University of Wisconsin-Madison, July 1997.
• 3: 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
• 4: Mohamed A. Gomaa , T. N. Vijaykumar, Opportunistic Transient-Fault Detection, Proceedings of the 32nd Annual International Symposium on Computer Architecture, p.172-183, June 04-08, 2005
• 5: Jinson J. Koppanalil , Eric Rotenberg, A Simple Mechanism for Detecting Ineffectual Instructions in Slipstream Processors, IEEE Transactions on Computers, v.53 n.4, p.399-413, April 2004 [doi>10.1109/TC.2004.1268397]
• 6: S. Kumar and A. Aggarwal. Reducing resource redundancy for concurrent error detection techniques in high performance microprocessors. 12th International Symposium on High-Performance Computer Architecture, pp. 212--221, Feb. 2006.
• 7: Kevin M. Lepak , Mikko H. Lipasti, On the value locality of store instructions, Proceedings of the 27th annual international symposium on Computer architecture, p.182-191, June 2000, Vancouver, British Columbia, Canada
• 8: 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, p.99, May 25-29, 2002, Anchorage, Alaska
• 9: Shubhendu S. Mukherjee , Christopher Weaver , Joel Emer , Steven K. Reinhardt , Todd Austin, A Systematic Methodology to Compute the Architectural Vulnerability Factors for a High-Performance Microprocessor, Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.29, December 03-05, 2003
• 10: Angshuman Parashar , Sudhanva Gurumurthi , Anand Sivasubramaniam, A Complexity-Effective Approach to ALU Bandwidth Enhancement for Instruction-Level Temporal Redundancy, Proceedings of the 31st annual international symposium on Computer architecture, p.376, June 19-23, 2004, München, Germany
• 11: S. Parthasarathy. Improving transient fault tolerance of slipstream processors. M.S. Thesis, ECE Department, North Carolina State University, Dec. 2005.
• 12: Zachary Robert Purser , Eric Rotenberg, Slipstream processors, 2003
• 13: Zach Purser , Karthik Sundaramoorthy , Eric Rotenberg, A study of slipstream processors, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.269-280, December 2000, Monterey, California, United States [doi>10.1145/360128.360155]
• 14: Z. Purser, K. Sundaramoorthy, and E. Rotenberg. Slipstream memory hierarchies. Tech. Report CESR-TR-02-3, ECE Department, North Carolina State University, Feb. 2002.
• 15: Joydeep Ray , James C. Hoe , Babak Falsafi, Dual use of superscalar datapath for transient-fault detection and recovery, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
• 16: 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
• 17: George A. Reis , Jonathan Chang , Neil Vachharajani , Ram Rangan , David I. August, SWIFT: Software Implemented Fault Tolerance, Proceedings of the international symposium on Code generation and optimization, p.243-254, March 20-23, 2005 [doi>10.1109/CGO.2005.34]
• 18: George A. Reis , Jonathan Chang , Neil Vachharajani , Ram Rangan , David I. August , Shubhendu S. Mukherjee, Design and Evaluation of Hybrid Fault-Detection Systems, Proceedings of the 32nd Annual International Symposium on Computer Architecture, p.148-159, June 04-08, 2005
• 19: 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
• 20: E. Rotenberg. Exploiting large ineffectual instruction sequences. Technical Report, North Carolina State University, Nov. 1999.
• 21: James E. Smith , Andrew R. Pleszkun, Implementation of precise interrupts in pipelined processors, Proceedings of the 12th annual international symposium on Computer architecture, p.36-44, June 17-19, 1985, Boston, Massachusetts, United States
• 22: Jared C. Smolens , Jangwoo Kim , James C. Hoe , Babak Falsafi, Efficient Resource Sharing in Concurrent Error Detecting Superscalar Microarchitectures, Proceedings of the 37th annual IEEE/ACM International Symposium on Microarchitecture, p.257-268, December 04-08, 2004, Portland, Oregon [doi>10.1109/MICRO.2004.19]
• 23: 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
• 24: Dean M. Tullsen , Susan J. Eggers , Henry M. Levy, Simultaneous multithreading: maximizing on-chip parallelism, Proceedings of the 22nd annual international symposium on Computer architecture, p.392-403, June 22-24, 1995, S. Margherita Ligure, Italy
• 25: T. N. Vijaykumar , Irith Pomeranz , Karl Cheng, Transient-fault recovery using simultaneous multithreading, Proceedings of the 29th annual international symposium on Computer architecture, p.87, May 25-29, 2002, Anchorage, Alaska
• 26: ReStore: Symptom Based Soft Error Detection in Microprocessors, Proceedings of the 2005 International Conference on Dependable Systems and Networks (DSN'05), p.30-39, June 28-July 01, 2005 [doi>10.1109/DSN.2005.82]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.1 Reliability, Testing, and Fault-Tolerance

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.0 General
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Fault tolerance

General Terms:
Design, Performance, Reliability

Keywords:
branch prediction, chip multiprocessor (CMP), redundant multithreading, simultaneous multithreading (SMT), slipstream processor, time redundancy, transient faults, value prediction