SlicK: slice-based locality exploitation for efficient redundant multithreading

ABSTRACT

Transient faults are expected a be a major design consideration in future microprocessors. Recent proposals for transient fault detection in processor cores have revolved around the idea of redundant threading, which involves redundant execution of a program across multiple execution contexts. This paper presents a new approach to redundant threading by bringing together the concepts of slice-level execution and value and control-flow locality into a novel partial redundant threading mechanism called SlicK.The purpose of redundant execution is to check the integrity of the outputs propagating out of the core (typically through stores). SlicK implements redundancy at the granularity of backward-slices of these output instructions and exploits value and control-flow locality to avoid redundantly executing slices that lead to predictable outputs, thereby avoiding redundant execution of a significant fraction of instructions while maintaining extremely low vulnerabilities for critical processor structures.We propose the microarchitecture of a backward-slice extractor called SliceEM that is able to identify backward slices without interrupting the instruction flow, and show how this extractor and a set of predictors can be integrated into a redundant threading mechanism to form SlicK. Detailed simulations with SPEC CPU2000 benchmarks show that SlicK can provide around 10.2% performance improvement over a well known redundant threading mechanism, buying back over 50% of the loss suffered due to redundant execution. SlicK can keep the Architectural Vulnerability Factors of processor structures to typically 0%-2%. More importantly, SlicK's slice-based mechanisms provide future opportunities for exploring interesting points in the performance-reliability design space based on market segment needs.

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: Mary D. Brown , Jared Stark , Yale N. Patt, Select-free instruction scheduling logic, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
• 3: D. Burger and T. Austin. The SimpleScalar Toolset, Version 3.0. http://www.simplescalar.com.
• 4: Martin Burtscher, An improved index function for (D)FCM predictors, ACM SIGARCH Computer Architecture News, v.30 n.3, June 2002 [doi>10.1145/571666.571677]
• 5: Jamison D. Collins , Dean M. Tullsen , Hong Wang , John P. Shen, Dynamic speculative precomputation, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
• 6: Evelyn Duesterwald , Rajiv Gupta , Mary Lou Soffa, Distributed Slicing and Partial Re-execution for Distributed Programs, Proceedings of the 5th International Workshop on Languages and Compilers for Parallel Computing, p.497-511, August 03-05, 1992
• 7: 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
• 8: Dirk Grunwald , Artur Klauser , Srilatha Manne , Andrew Pleszkun, Confidence estimation for speculation control, Proceedings of the 25th annual international symposium on Computer architecture, p.122-131, June 27-July 02, 1998, Barcelona, Spain
• 9: S. Gurumurthi, A. Parashar, and A. Sivasubramaniam. SOS: Using Speculation for Memory Error Detection. In Proceedings of the Workshop on High Performance Computing Reliability Issues (held in conjunction with HPCA), February 2005.
• 10: HP NonStop Himalaya. http://nonstop.compaq.com/.
• 11: 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]
• 12: Kevin M. Lepak , Gordon B. Bell , Mikko H. Lipasti, Silent Stores and Store Value Locality, IEEE Transactions on Computers, v.50 n.11, p.1174-1190, November 2001 [doi>10.1109/12.966493]
• 13: SoftArch: An Architecture Level Tool for Modeling and Analyzing Soft Errors, Proceedings of the 2005 International Conference on Dependable Systems and Networks (DSN'05), p.496-505, June 28-July 01, 2005 [doi>10.1109/DSN.2005.88]
• 14: Enric Morancho , José María Llabería , Àngel Olivé, Recovery Mechanism for Latency Misprediction, Proceedings of the 2001 International Conference on Parallel Architectures and Compilation Techniques, p.118, September 08-12, 2001
• 15: Andreas Moshovos , Dionisios N. Pnevmatikatos , Amirali Baniasadi, Slice-processors: an implementation of operation-based prediction, Proceedings of the 15th international conference on Supercomputing, p.321-334, June 2001, Sorrento, Italy [doi>10.1145/377792.377856]
• 16: 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
• 17: 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
• 18: 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
• 19: Microarchitecture-Based Introspection: A Technique for Transient-Fault Tolerance in Microprocessors, Proceedings of the 2005 International Conference on Dependable Systems and Networks (DSN'05), p.434-443, June 28-July 01, 2005 [doi>10.1109/DSN.2005.62]
• 20: 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
• 21: Smruti R. Sarangi , Wei Liu, Josep Torrellas , Yuanyuan Zhou, ReSlice: Selective Re-Execution of Long-Retired Misspeculated Instructions Using Forward Slicing, Proceedings of the 38th annual IEEE/ACM International Symposium on Microarchitecture, p.257-270, November 12-16, 2005, Barcelona, Spain [doi>10.1109/MICRO.2005.28]
• 22: Timothy Sherwood , Erez Perelman , Greg Hamerly , Brad Calder, Automatically characterizing large scale program behavior, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 23: 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
• 24: Timothy J. Slegel , Robert M. Averill III , Mark A. Check , Bruce C. Giamei , Barry W. Krumm , Christopher A. Krygowski , Wen H. Li , John S. Liptay , John D. MacDougall , Thomas J. McPherson , Jennifer A. Navarro , Eric M. Schwarz , Kevin Shum , Charles F. Webb, IBM's S/390 G5 Microprocessor Design, IEEE Micro, v.19 n.2, p.12-23, March 1999 [doi>10.1109/40.755464]
• 25: Jared C. Smolens , Brian T. Gold , Jangwoo Kim , Babak Falsafi , James C. Hoe , Andreas G. Nowatzyk, Fingerprinting: bounding soft-error detection latency and bandwidth, Proceedings of the 11th international conference on Architectural support for programming languages and operating systems, October 07-13, 2004, Boston, MA, USA
• 26: 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]
• 27: 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
• 28: 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
• 29: 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
• 30: 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]
• 31: Tse-Yu Yeh , Yale N. Patt, Alternative implementations of two-level adaptive branch prediction, Proceedings of the 19th annual international symposium on Computer architecture, p.124-134, May 19-21, 1992, Queensland, Australia
• 32: Craig B. Zilles , Gurindar S. Sohi, Understanding the backward slices of performance degrading instructions, Proceedings of the 27th annual international symposium on Computer architecture, p.172-181, June 2000, Vancouver, British Columbia, Canada

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.0 General

General Terms:
Performance, Reliability

Keywords:
backward slice extraction, microarchitecture, redundant threading, transient faults