Skewed redundancy

ABSTRACT

Technology scaling in integrated circuits has consistently provided dramatic performance improvements in modern microprocessors. However, increasing device counts and decreasing on-chip voltage levels have made transient errors a first-order design constraint that can no longer be ignored. Several proposals have provided fault detection and tolerance through redundantly executing a program on an additional hardware thread or core. While such techniques can provide high fault coverage, they at best provide equivalent performance to the original execution and at worst incur a slowdown due to error checking, contention for shared resources, and synchronization overheads. This work achieves a similar goal of detecting transient errors by redundantly executing a program on an additional processor core, however it speeds up (rather than slows down) program execution compared to the unprotected baseline case. It makes the observation that a small number of instructions are detrimental to overall performance, and selectively skipping them enables one core to advance far ahead of the other to obtain prefetching and large instruction window benefits. We highlight the modest incremental hardware required to support skewed redundancy and demonstrate a speedup of 6%/54% for a collection of integer/floating point benchmarks while still providing 100% error detection coverage within our sphere of replication. Additionally, we show that a third core can further improve performance while adding error recovery capabilities.

REFERENCES

• 1: Nidhi Aggarwal , Parthasarathy Ranganathan , Norman P. Jouppi , James E. Smith, Configurable isolation: building high availability systems with commodity multi-core processors, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
• 2: Ronald D. Barnes , Erik M. Nystrom , John W. Sias , Sanjay J. Patel , Nacho Navarro , Wen-mei W. Hwu, Beating in-order stalls with "flea-flicker" two-pass pipelining, Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.387, December 03-05, 2003
• 3: G. B. Bell , M. H. Lipasti, Deconstructing commit, Proceedings of the 2004 IEEE International Symposium on Performance Analysis of Systems and Software, p.68-77, March 10-12, 2004
• 4: Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
• 5: Harold W. Cain, III , Mikko H. Lipasti, Detecting and exploiting causal relationships in hardware shared-memory multiprocessors, University of Wisconsin at Madison, Madison, WI, 2004
• 6: H. Cain, K. Lepak, B. Schwarz, and M. Lipasti. Precise and accurate processor simulation. In CAECW, Feb. 2002.
• 7: A. Cristal et al. Large virtual ROBs by processor checkpointing. Tech. Rep. UPC-DAC-2002-39, Univ. UPC, July 2002.
• 8: Adrian Cristal , Daniel Ortega , Josep Llosa , Mateo Valero, Out-of-Order Commit Processors, Proceedings of the 10th International Symposium on High Performance Computer Architecture, p.48, February 14-18, 2004 [doi>10.1109/HPCA.2004.10008]
• 9: James David Dundas , Trevor Mudge, Improving processor performance by dynamically pre-processing the instruction stream, University of Michigan, Ann Arbor, MI, 1998
• 10: Ilya Ganusov , Martin Burtscher, Future Execution: A Hardware Prefetching Technique for Chip Multiprocessors, Proceedings of the 14th International Conference on Parallel Architectures and Compilation Techniques, p.350-360, September 17-21, 2005 [doi>10.1109/PACT.2005.23]
• 11: 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
• 12: Lance Hammond , Mark Willey , Kunle Olukotun, Data speculation support for a chip multiprocessor, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.58-69, October 02-07, 1998, San Jose, California, United States
• 13: P. Jordan, B. Konigsburg, H. Le, and S. White. US patent #5805849: Data processing system and method for using an unique identifier to maintain an age relationship between executing instructions, 1997.
• 14: T. Karkhanis and J. Smith. A day in the life of a data cache miss, In Workshop on Memory Performance Issues, 2002.
• 15: Ilhyun Kim , Mikko H. Lipasti, Understanding Scheduling Replay Schemes, Proceedings of the 10th International Symposium on High Performance Computer Architecture, p.198, February 14-18, 2004 [doi>10.1109/HPCA.2004.10011]
• 16: Venkata Krishnan , Josep Torrellas, A Chip-Multiprocessor Architecture with Speculative Multithreading, IEEE Transactions on Computers, v.48 n.9, p.866-880, September 1999 [doi>10.1109/12.795218]
• 17: Alvin R. Lebeck , Jinson Koppanalil , Tong Li , Jaidev Patwardhan , Eric Rotenberg, A large, fast instruction window for tolerating cache misses, Proceedings of the 29th annual international symposium on Computer architecture, May 25-29, 2002, Anchorage, Alaska
• 18: Y. Ma, H. Gao, M. Dimitrov, and H. Zhou. Optimizing dual-core execution for power efficiency and transient-fault recovery. IEEE TPDS, 18(8):1080--1093, 2007.
• 19: José F. Martínez , Jose Renau , Michael C. Huang , Milos Prvulovic , Josep Torrellas, Cherry: checkpointed early resource recycling in out-of-order microprocessors, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
• 20: 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
• 21: Onur Mutlu , Jared Stark , Chris Wilkerson , Yale N. Patt, Runahead Execution: An Alternative to Very Large Instruction Windows for Out-of-Order Processors, Proceedings of the 9th International Symposium on High-Performance Computer Architecture, p.129, February 08-12, 2003
• 22: 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
• 23: Vimal K. Reddy , Eric Rotenberg , Sailashri Parthasarathy, Understanding prediction-based partial redundant threading for low-overhead, high- coverage fault tolerance, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
• 24: 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
• 25: 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
• 26: Simha Sethumadhavan , Rajagopalan Desikan , Doug Burger , Charles R. Moore , Stephen W. Keckler, Scalable Hardware Memory Disambiguation for High-ILP Processors, IEEE Micro, v.24 n.6, p.118-127, November 2004 [doi>10.1109/MM.2004.87]
• 27: Jared C. Smolens , Brian T. Gold , Babak Falsafi , James C. Hoe, Reunion: Complexity-Effective Multicore Redundancy, Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.223-234, December 09-13, 2006 [doi>10.1109/MICRO.2006.42]
• 28: 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]
• 29: Gurindar S. Sohi , Scott E. Breach , T. N. Vijaykumar, Multiscalar processors, Proceedings of the 22nd annual international symposium on Computer architecture, p.414-425, June 22-24, 1995, S. Margherita Ligure, Italy
• 30: Srikanth T. Srinivasan , Ravi Rajwar , Haitham Akkary , Amit Gandhi , Mike Upton, Continual flow pipelines, Proceedings of the 11th international conference on Architectural support for programming languages and operating systems, October 07-13, 2004, Boston, MA, USA
• 31: 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
• 32: 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
• 33: Huiyang Zhou, Dual-Core Execution: Building a Highly Scalable Single-Thread Instruction Window, Proceedings of the 14th International Conference on Parallel Architectures and Compilation Techniques, p.231-242, September 17-21, 2005 [doi>10.1109/PACT.2005.18]

INDEX TERMS

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

General Terms:
Design, Performance, Reliability

Keywords:
distributed processing, error tolerance, memory-level parallelism