A mechanistic performance model for superscalar out-of-order processors

ABSTRACT

A mechanistic model for out-of-order superscalar processors is developed and then applied to the study of microarchitecture resource scaling. The model divides execution time into intervals separated by disruptive miss events such as branch mispredictions and cache misses. Each type of miss event results in characterizable performance behavior for the execution time interval. By considering an interval's type and length (measured in instructions), execution time can be predicted for the interval. Overall execution time is then determined by aggregating the execution time over all intervals. The mechanistic model provides several advantages over prior modeling approaches, and, when estimating performance, it differs from detailed simulation of a 4-wide out-of-order processor by an average of 7%.

The mechanistic model is applied to the general problem of resource scaling in out-of-order superscalar processors. First, we use the model to determine size relationships among microarchitecture structures in a balanced processor design. Second, we use the mechanistic model to study scaling of both pipeline depth and width in balanced processor designs. We corroborate previous results in this area and provide new results. For example, we show that at optimal design points, the pipeline depth times the square root of the processor width is nearly constant. Finally, we consider the behavior of unbalanced, overprovisioned processor designs based on insight gained from the mechanistic model. We show that in certain situations an overprovisioned processor may lead to improved overall performance. Designs where a processor's dispatch width is wider than its issue width are of particular interest.

REFERENCES

• 1: Vikas Agarwal , M. S. Hrishikesh , Stephen W. Keckler , Doug Burger, Clock rate versus IPC: the end of the road for conventional microarchitectures, Proceedings of the 27th annual international symposium on Computer architecture, p.248-259, June 2000, Vancouver, British Columbia, Canada
• 2: Erik Berg , Erik Hagersten, Fast data-locality profiling of native execution, Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 06-10, 2005, Banff, Alberta, Canada
• 3: Brooks, D., Martonosi, M., and Bose, P. 2000. Abstraction via separable components: An empirical study of absolute and relative accuracy in processor performance modeling. Tech. rep. RC 21909, IBM Research Division, T. J. Watson Research Center. December.
• 4: Doug Burger , Todd M. Austin, The SimpleScalar tool set, version 2.0, ACM SIGARCH Computer Architecture News, v.25 n.3, p.13-25, June 1997 [doi>10.1145/268806.268810]
• 5: Yuan Chou , Brian Fahs , Santosh Abraham, Microarchitecture Optimizations for Exploiting Memory-Level Parallelism, Proceedings of the 31st annual international symposium on Computer architecture, p.76, June 19-23, 2004, München, Germany
• 6: Adrián Cristal , Oliverio J. Santana , Mateo Valero , José F. Martínez, Toward kilo-instruction processors, ACM Transactions on Architecture and Code Optimization (TACO), v.1 n.4, p.389-417, December 2004 [doi>10.1145/1044823.1044825]
• 7: P. K. Dubey , G. B. Adams, III , M. J. Flynn, Instruction Window Size Trade-Offs and Characterization of Program Parallelism, IEEE Transactions on Computers, v.43 n.4, p.431-442, April 1994 [doi>10.1109/12.278481]
• 8: Pradeep K. Dubey , Michael J. Flynn, Optimal pipelining, Journal of Parallel and Distributed Computing, v.8 n.1, p.10-19, Jan. 1990 [doi>10.1016/0743-7315(90)90064-V]
• 9: Lieven Eeckhout , Koenraad De Bosschere, Hybrid Analytical-Statistical Modeling for Efficiently Exploring Architecture and Workload Design Spaces, Proceedings of the 2001 International Conference on Parallel Architectures and Compilation Techniques, p.25, September 08-12, 2001
• 10: P. G. Emma, Understanding some simple processor-performance limits, IBM Journal of Research and Development, v.41 n.3, p.215-232, May 1997
• 11: P. G. Emma , E. S. Davidson, Characterization of branch and data dependencies on programs for evaluating pipeline performance, IEEE Transactions on Computers, v.36 n.7, p.859-875, July 1987 [doi>10.1109/TC.1987.1676981]
• 12: Stijn Eyerman , Lieven Eeckhout , Tejas Karkhanis , James E. Smith, A performance counter architecture for computing accurate CPI components, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
• 13: Stijn Eyerman , Lieven Eeckhout , Tejas Karkhanis , James E. Smith, A Top-Down Approach to Architecting CPI Component Performance Counters, IEEE Micro, v.27 n.1, p.84-93, January 2007 [doi>10.1109/MM.2007.3]
• 14: Eyerman, S., Smith, J. E., and Eeckhout, L. 2006b. Characterizing the branch misprediction penalty. In IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS), 48--58.
• 15: Brian A. Fields , Rastislav Bodik , Mark D. Hill , Chris J. Newburn, Interaction cost and shotgun profiling, ACM Transactions on Architecture and Code Optimization (TACO), v.1 n.3, p.272-304, September 2004 [doi>10.1145/1022969.1022971]
• 16: Glew, A. 1998. MLP yes! ILP no! In ASPLOS Wild and Crazy Idea Session.
• 17: Fei Guo , Yan Solihin, An analytical model for cache replacement policy performance, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 26-30, 2006, Saint Malo, France
• 18: A. Hartstein , Thomas R. Puzak, The optimum pipeline depth for a microprocessor, Proceedings of the 29th annual international symposium on Computer architecture, May 25-29, 2002, Anchorage, Alaska
• 19: A. Hartstein , Thomas R. Puzak, Optimum Power/Performance Pipeline Depth, Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.117, December 03-05, 2003
• 20: M. S. Hrishikesh , Doug Burger , Norman P. Jouppi , Stephen W. Keckler , Keith I. Farkas , Premkishore Shivakumar, The optimal logic depth per pipeline stage is 6 to 8 FO4 inverter delays, Proceedings of the 29th annual international symposium on Computer architecture, May 25-29, 2002, Anchorage, Alaska
• 21: Engin Ïpek , Sally A. McKee , Rich Caruana , Bronis R. de Supinski , Martin Schulz, Efficiently exploring architectural design spaces via predictive modeling, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
• 22: Joseph, P. J., Vaswani, K., and Thazhuthaveetil, M. J. 2006a. Construction and use of linear regression models for processor performance analysis. In Proceedings of the 12th International Symposium on High-Performance Computer Architecture (HPCA), 99--108.
• 23: P. J. Joseph , Kapil Vaswani , Matthew J. Thazhuthaveetil, A Predictive Performance Model for Superscalar Processors, Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.161-170, December 09-13, 2006 [doi>10.1109/MICRO.2006.6]
• 24: Karkhanis, T. and Smith, J. E. 2002. A day in the life of a data cache miss. In Proceedings of the 2nd Annual Workshop on Memory Performance Issues (WMPI) held in conjunction with ISCA.
• 25: Tejas S. Karkhanis , James E. Smith, Automated design of application specific superscalar processors: an analytical approach, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
• 26: Tejas S. Karkhanis , James E. Smith, A First-Order Superscalar Processor Model, Proceedings of the 31st annual international symposium on Computer architecture, p.338, June 19-23, 2004, München, Germany
• 27: S. R. Kunkel , J. E. Smith, Optimal pipelining in supercomputers, Proceedings of the 13th annual international symposium on Computer architecture, p.404-411, June 02-05, 1986, Tokyo, Japan
• 28: Benjamin C. Lee , David M. Brooks, Accurate and efficient regression modeling for microarchitectural performance and power prediction, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
• 29: Pierre Michaud , Andre Seznec , Stephan Jourdan, Exploring Instruction-Fetch Bandwidth Requirement in Wide-Issue Superscalar Processors, Proceedings of the 1999 International Conference on Parallel Architectures and Compilation Techniques, p.2, October 12-16, 1999
• 30: Pierre Michaud , André Seznec , Stéphan Jourdan, An exploration of instruction fetch requirement in out-of-order superscalar processors, International Journal of Parallel Programming, v.29 n.1, p.35-58, 2001 [doi>10.1023/A:1026431920605]
• 31: 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
• 32: Derek B. Noonburg , John P. Shen, Theoretical modeling of superscalar processor performance, Proceedings of the 27th annual international symposium on Microarchitecture, p.52-62, November 30-December 02, 1994, San Jose, California, United States [doi>10.1145/192724.192730]
• 33: Derek B. Noonburg , John Paul Shen, A Framework for Statistical Modeling of Superscalar Processor Performance, Proceedings of the 3rd IEEE Symposium on High-Performance Computer Architecture, p.298, February 01-05, 1997
• 34: E. M. Riseman , C. C. Foster, The Inhibition of Potential Parallelism by Conditional Jumps, IEEE Transactions on Computers, v.21 n.12, p.1405-1411, December 1972 [doi>10.1109/T-C.1972.223514]
• 35: 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
• 36: Daniel J. Sorin , Vijay S. Pai , Sarita V. Adve , Mary K. Vernon , David A. Wood, Analytic evaluation of shared-memory systems with ILP processors, Proceedings of the 25th annual international symposium on Computer architecture, p.380-391, June 27-July 02, 1998, Barcelona, Spain
• 37: Eric Sprangle , Doug Carmean, Increasing processor performance by implementing deeper pipelines, Proceedings of the 29th annual international symposium on Computer architecture, May 25-29, 2002, Anchorage, Alaska
• 38: 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
• 39: Viji Srinivasan , David Brooks , Michael Gschwind , Pradip Bose , Victor Zyuban , Philip N. Strenski , Philip G. Emma, Optimizing pipelines for power and performance, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
• 40: Tarek M. Taha , D. Scott Wills, An Instruction Throughput Model of Superscalar Processors, Proceedings of the 14th IEEE International Workshop on Rapid System Prototyping (RSP'03), p.156, June 09-11, 2003
• 41: Tarek M. Taha , Scott Wills, An Instruction Throughput Model of Superscalar Processors, IEEE Transactions on Computers, v.57 n.3, p.389-403, March 2008 [doi>10.1109/TC.2007.70817]
• 42: David W. Wall, Limits of instruction-level parallelism, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.176-188, April 08-11, 1991, Santa Clara, California, United States
• 43: Yutao Zhong , Steven G. Dropsho , Chen Ding, Miss Rate Prediction across All Program Inputs, Proceedings of the 12th International Conference on Parallel Architectures and Compilation Techniques, p.79, September 27-October 01, 2003

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

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

General Terms:
Performance

Keywords:
Superscalar out-of-order processor, analytical modeling, balanced processor design, mechanistic modeling, overprovisioned processor design, performance modeling, pipeline depth, pipeline width, resource scaling, wide front-end dispatch processors