Selective eager execution on the PolyPath architecture

ABSTRACT

Control-flow misprediction penalties are a major impediment to high performance in wide-issue superscalar processors. In this paper we present Selective Eager Execution (SEE), an execution model to overcome mis-speculation penalties by executing both paths after diffident branches. We present the micro-architecture of the PolyPath processor, which is an extension of an aggressive superscalar, out-of-order architecture. The PolyPath architecture uses a novel instruction tagging and register renaming mechanism to execute instructions from multiple paths simultaneously in the same processor pipeline, while retaining maximum resource availability for single-path code sequences.Results of our execution-driven, pipeline-level simulations show that SEE can improve performance by as much as 36% for the go benchmark, and an average of 14% on SPECint95, when compared to a normal superscalar, out-of-order, speculative execution, monopath processor. Moreover, our architectural model is both elegant and practical to implement, using a small amount of additional state and control logic.

REFERENCES

• 1: James O. Bondi , Ashwini K. Nanda , Simonjit Dutta, Integrating a misprediction recovery cache (MRC) into a superscalar pipeline, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.14-23, December 02-04, 1996, Paris, France
• 2: T-F Chen, Supporting Highly-Speculative Execution via Adaptive Branch Trees, Proceedings of the 4th International Symposium on High-Performance Computer Architecture, p.185, January 31-February 04, 1998
• 3: John H. Edmondson , Paul I. Rubinfeld , Peter J. Bannon , Bradley J. Benschneider , Debra Bernstein , Ruben W. Castelino , Elizabeth M. Cooper , Daniel E. Dever , Dale R. Donchin , Timothy C. Fischer , Anil K. Jain , Shekhar Mehta , Jeanne E. Meyer , Ronald P. Preston , Vidya Rajagopalan , Chandrasekhara Somanathan , Scott A. Taylor , Gilbert M. Wolrich, Internal organization of the Alpha 21164, a 300-MHz 64-bit quad-issue CMOS RISC microprocessor, Digital Technical Journal, v.7 n.1, p.119-135, Jan. 1995
• 4: 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
• 5: Timothy Heil and James Smith. Selective Dual Path Execution. Technical report, University of Wisconsin-Madison, November 1996. http://w ww.ece, wi sc.edu/j es/papers/sdpe, ps.
• 6: 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
• 7: Quinn Jacobson , Steve Bennett , Nikhil Sharma , James E. Smith, Control Flow Speculation in Multiscalar Processors, Proceedings of the 3rd IEEE Symposium on High-Performance Computer Architecture, p.218, February 01-05, 1997
• 8: Michael J. Knieser , Christos A. Papachristou, Y-Pipe: a conditional branching scheme without pipeline delays, Proceedings of the 25th annual international symposium on Microarchitecture, p.125-128, December 01-04, 1992, Portland, Oregon, United States
• 9: Chih-Chieh Lee , I-Cheng K. Chen , Trevor N. Mudge, The bi-mode branch predictor, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.4-13, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 10: Kelsey Lick. Limited Dual Path Execution. Master's thesis, University of California, Riverside, 1996.
• 11: Mikko Herman Lipasti, Value locality and speculative execution, Carnegie Mellon University, Pittsburgh, PA, 1998
• 12: Scott McFarling. Combining Branch Predictors. TN 36, DEC-WRL, June 1993.
• 13: Abhijit Paithankar. AINT: A Tool for Simulation of Shared- Memory Multiprocessors. Master's thesis, University of Colorado at Boulder, 1996.
• 14: Eric Rotenberg , Quinn Jacobson , Yiannakis Sazeides , Jim Smith, Trace processors, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.138-148, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 15: Digital Semiconductor. Alpha AXP-21164 Processor Hardware Reference Manual, September 1997.
• 16: André Seznec , Stéphan Jourdan , Pascal Sainrat , Pierre Michaud, Multiple-block ahead branch predictors, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.116-127, October 01-04, 1996, Cambridge, Massachusetts, United States
• 17: James E. Smith , Andrew R. Pleszkun, Implementing Precise Interrupts in Pipelined Processors, IEEE Transactions on Computers, v.37 n.5, p.562-573, May 1988 [doi>10.1109/12.4607]
• 18: Eric Sprangle , Robert S. Chappell , Mitch Alsup , Yale N. Patt, The agree predictor: a mechanism for reducing negative branch history interference, Proceedings of the 24th annual international symposium on Computer architecture, p.284-291, June 01-04, 1997, Denver, Colorado, United States
• 19: M. Tremblay , B. Joy , K. Shin, A three dimensional register file for superscalar processors, Proceedings of the 28th Hawaii International Conference on System Sciences (HICSS'95), p.191, January 04-07, 1995
• 20: Gary Tyson, Kelsey Lick, and Matthew Farrens. Limited Dual Path Execution. CSE-TR 346-97, University of Michigan, 1997.
• 21: Augustus K. Uht , Vijay Sindagi , Kelley Hall, Disjoint eager execution: an optimal form of speculative execution, Proceedings of the 28th annual international symposium on Microarchitecture, p.313-325, November 29-December 01, 1995, Ann Arbor, Michigan, United States
• 22: Kenneth C. Yeager, The MIPS R10000 Superscalar Microprocessor, IEEE Micro, v.16 n.2, p.28-40, April 1996 [doi>10.1109/40.491460]
• 23: Tse-Yu Yeh , Yale N. Patt, A comparison of dynamic branch predictors that use two levels of branch history, Proceedings of the 20th annual international symposium on Computer architecture, p.257-266, May 16-19, 1993, San Diego, California, United States

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.3 Other Architecture Styles
          Subjects: Pipeline processors

Additional Classification:
  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: Modeling of computer architecture