Slipstream processors: improving both performance and fault tolerance

ABSTRACT

Processors execute the full dynamic instruction stream to arrive at the final output of a program, yet there exist shorter instruction streams that produce the same overall effect. We propose creating a shorter but otherwise equivalent version of the original program by removing ineffectual computation and computation related to highly-predictable control flow. The shortened program is run concurrently with the full program on a chip multiprocessor or simultaneous multithreaded processor, with two key advantages:1) Improved single-program performance. The shorter program speculatively runs ahead of the full program and supplies the full program with control and data flow outcomes. The full program executes efficiently due to the communicated outcomes, at the same time validating the speculative, shorter program. The two programs combined run faster than the original program alone. Detailed simulations of an example implementation show an average improvement of 7% for the SPEC95 integer benchmarks.2) Fault tolerance. The shorter program is a subset of the full program and this partial-redundancy is transparently leveraged for detecting and recovering from transient hardware faults.

REFERENCES

• 1: Haitham Akkary , Michael A. Driscoll, A dynamic multithreading processor, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.226-236, November 1998, Dallas, Texas, United States
• 2: 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
• 3: D. Burger, T. Austin, and S. Bennett. Evaluating Future Microprocessors: The Simplescalar Toolset. Technical Report CS-TR-96-1308, Computer Sciences Department, University of Wisconsin - Madison, July 1996.
• 4: Doug Burger , Stefanos Kaxiras , James R. Goodman, DataScalar architectures, Proceedings of the 24th annual international symposium on Computer architecture, p.338-349, June 01-04, 1997, Denver, Colorado, United States
• 5: Robert S. Chappell , Jared Stark , Sangwook P. Kim , Steven K. Reinhardt , Yale N. Patt, Simultaneous subordinate microthreading (SSMT), Proceedings of the 26th annual international symposium on Computer architecture, p.186-195, May 01-04, 1999, Atlanta, Georgia, United States
• 6: Daniel A. Connors , Wen-mei W. Hwu, Compiler-directed dynamic computation reuse: rationale and initial results, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.158-169, November 16-18, 1999, Haifa, Israel
• 7: Pradeep K. Dubey , Kevin O'Brien , Kathryn M. O'Brien , Charles Barton, Single-program speculative multithreading (SPSM) architecture: compiler-assisted fine-grained multithreading, Proceedings of the IFIP WG10.3 working conference on Parallel architectures and compilation techniques, p.109-121, June 27-29, 1995, Limassol, Cyprus
• 8: Alexandre Farcy , Olivier Temam , Roger Espasa , Toni Juan, Dataflow analysis of branch mispredictions and its application to early resolution of branch outcomes, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.59-68, November 1998, Dallas, Texas, United States
• 9: Antonio Gonzalez , Jordi Tubella , Carlos Molina, Trace-Level Reuse, Proceedings of the 1999 International Conference on Parallel Processing, p.30, September 21-24, 1999
• 10: Jian Huang , David Lilja, Exploiting Basic Block Value Locality with Block Reuse, Proceedings of the 5th International Symposium on High Performance Computer Architecture, p.106, January 09-12, 1999
• 11: R. Iyer, A. Avizienis, D. Barron, D. Powell, H. Levendel, and J. Samson. Panel: Using COTS to Design Dependable Networked Systems. 29th Int'l Syrup. on Fault-Tolerant Computing, June 1999.
• 12: Erik Jacobsen , Eric Rotenberg , J. E. Smith, Assigning confidence to conditional branch predictions, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.142-152, December 02-04, 1996, Paris, France
• 13: Quinn Jacobson , Eric Rotenberg , James E. Smith, Path-based next trace prediction, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.14-23, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 14: Stephen Jourdan , Ronny Ronen , Michael Bekerman , Bishara Shomar , Adi Yoaz, A novel renaming scheme to exploit value temporal locality through physical register reuse and unification, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.216-225, November 1998, Dallas, Texas, United States
• 15: 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
• 16: Mikko H. Lipasti , Christopher B. Wilkerson , John Paul Shen, Value locality and load value prediction, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.138-147, October 01-04, 1996, Cambridge, Massachusetts, United States
• 17: Mikko Herman Lipasti, Value locality and speculative execution, Carnegie Mellon University, Pittsburgh, PA, 1998
• 18: Milo M. Martin , Amir Roth , Charles N. Fischer, Exploiting dead value information, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.125-135, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 19: Carlos Molina , Antonio González , Jordi Tubella, Reducing Memory Traffic Via Redundant Store Instructions, Proceedings of the 7th International Conference on High-Performance Computing and Networking, p.1246-1249, April 12-14, 1999
• 20: Kunle Olukotun , Basem A. Nayfeh , Lance Hammond , Ken Wilson , Kunyung Chang, The case for a single-chip multiprocessor, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.2-11, October 01-04, 1996, Cambridge, Massachusetts, United States
• 21: 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
• 22: 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
• 23: D. Ronfeldt. Social Science at 190 MPH on NASCAR's Biggest Superspeedways. First Monday Journal (on-line), Vol. 5 No. 2, Feb. 7, 2000.
• 24: 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
• 25: E. Rotenberg. Exploiting Large Ineffectual Instruction Sequences. Technical Report, Department of Electrical and Computer Engineering, North Carolina State University, Nov. 1999.
• 26: Amir Roth , Andreas Moshovos , Gurindar S. Sohi, Dependence based prefetching for linked data structures, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.115-126, October 02-07, 1998, San Jose, California, United States
• 27: A. Roth and G. Sohi. Speculative Data Driven Sequencing for Imperative Programs. Technical Report CS-TR-2000-1411, Computer Sciences Department, University of Wisconsin - Madison, Feb. 2000.
• 28: A. Roth and G. Sohi. Speculative Data-Driven Multithreading. Technical Report CS-TR-2000-1414, Computer Sciences Department, University of Wisconsin - Madison, April 2000.
• 29: Paul I. Rubinfeld, Managing Problems at High Speed, Computer, v.31 n.1, p.47-48, January 1998
• 30: Yiannakis Sazeides , James E. Smith, Modeling program predictability, Proceedings of the 25th annual international symposium on Computer architecture, p.73-84, June 27-July 02, 1998, Barcelona, Spain
• 31: Avinash Sodani , Gurindar S. Sohi, Dynamic instruction reuse, Proceedings of the 24th annual international symposium on Computer architecture, p.194-205, June 01-04, 1997, Denver, Colorado, United States
• 32: Avinash Sodani , Gurindar S. Sohi, An empirical analysis of instruction repetition, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.35-45, October 02-07, 1998, San Jose, California, United States
• 33: 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
• 34: 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
• 35: Jenn-Yuan Tsai , Pen-Chung Yew, The Superthreaded Architecture: Thread Pipelining with Run-Time Data Dependence Checking and Control Speculation, Proceedings of the 1996 Conference on Parallel Architectures and Compilation Techniques, p.35, October 20-23, 1996
• 36: 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
• 37: Dean M. Tullsen , Susan J. Eggers , Joel S. Emer , Henry M. Levy , Jack L. Lo , Rebecca L. Stamm, Exploiting choice: instruction fetch and issue on an implementable simultaneous multithreading processor, Proceedings of the 23rd annual international symposium on Computer architecture, p.191-202, May 22-24, 1996, Philadelphia, Pennsylvania, United States
• 38: Dean M. Tullsen , John S. Seng, Storageless value prediction using prior register values, Proceedings of the 26th annual international symposium on Computer architecture, p.270-279, May 01-04, 1999, Atlanta, Georgia, United States
• 39: Wayne Yamamoto , Mario Nemirovsky, Increasing superscalar performance through multistreaming, Proceedings of the IFIP WG10.3 working conference on Parallel architectures and compilation techniques, p.49-58, June 27-29, 1995, Limassol, Cyprus
• 40: Craig B. Zilles , Joel S. Emer , Gurindar S. Sohi, The use of multithreading for exception handling, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.219-229, November 16-18, 1999, Haifa, Israel
• 41: 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