Accurate memory data flow modeling in statistical simulation

ABSTRACT

Microprocessor design is a very complex and time-consuming activity. One of the primary reasons is the huge design space that needs to be explored in order to identify the optimal design given a number of constraints. Simulations are usually used to explore these huge design spaces, however, they are fairly slow. Several hundreds of billions of instructions need to be simulated per benchmark; and this needs to be done for every design point of interest.Recently, statistical simulation was proposed to efficiently cull a huge design space. The basic idea of statistical simulation is to collect a number of important program characteristics and to generate a synthetic trace from it. Simulating this synthetic trace is extremely fast as it contains a million instructions only.This paper improves the statistical simulation methodology by proposing accurate memory data flow models. We model (i) load forwarding, (ii) delayed cache hits, and (iii) correlation between cache misses based on path info. Our experiments using the SPEC CPU2000 benchmarks show a substantial improvement upon current state-of-the-art statistical simulation methods. For example, for our baseline configuration we reduce the average IPC prediction error from 10.7% to 2.3%. In addition, we show that performance trends are predicted very accurately, making statistical simulation enhanced with accurate data flow models a useful tool for efficient and accurate microprocessor design space explorations.

REFERENCES

• 1: Robert H. Bell, Jr. , Lizy K. John, Improved automatic testcase synthesis for performance model validation, Proceedings of the 19th annual international conference on Supercomputing, June 20-22, 2005, Cambridge, Massachusetts [doi>10.1145/1088149.1088164]
• 2: David M. Brooks , Pradip Bose , Stanley E. Schuster , Hans Jacobson , Prabhakar N. Kudva , Alper Buyuktosunoglu , John-David Wellman , Victor Zyuban , Manish Gupta , Peter W. Cook, Power-Aware Microarchitecture: Design and Modeling Challenges for Next-Generation Microprocessors, IEEE Micro, v.20 n.6, p.26-44, November 2000 [doi>10.1109/40.888701]
• 3: David Brooks , Vivek Tiwari , Margaret Martonosi, Wattch: a framework for architectural-level power analysis and optimizations, Proceedings of the 27th annual international symposium on Computer architecture, p.83-94, June 2000, Vancouver, British Columbia, Canada
• 4: R. Carl and J. E. Smith. Modeling superscalar processors via statistical simulation. In Workshop on Performance Analysis and its Impact on Design (PAID-98), held in conjunction with ISCA-25, June 1998.
• 5: Thomas M. Conte , Mary Ann Hirsch , Kishore N. Menezes, Reducing State Loss For Effective Trace Sampling of Superscalar Processors, Proceedings of the 1996 International Conference on Computer Design, VLSI in Computers and Processors, p.468-477, October 07-09, 1996
• 6: Lieven Eeckhout , Robert H. Bell Jr. , Bastiaan Stougie , Koen De Bosschere , Lizy K. John, Control Flow Modeling in Statistical Simulation for Accurate and Efficient Processor Design Studies, Proceedings of the 31st annual international symposium on Computer architecture, p.350, June 19-23, 2004, München, Germany
• 7: 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
• 8: L. Eeckhout, S. Nussbaum, J. E. Smith, and K. De Bosschere. Statistical simulation: Adding efficiency to the computer designer's toolbox. IEEE Micro, 23(5):26--38, Sept/Oct 2003.
• 9: Stijn Eyerman , Lieven Eeckhout , Koen De Bosschere, Efficient design space exploration of high performance embedded out-of-order processors, Proceedings of the conference on Design, automation and test in Europe: Proceedings, March 06-10, 2006, Munich, Germany
• 10: K. I. Farkas , N. P. Jouppi, Complexity/performance tradeoffs with non-blocking loads, Proceedings of the 21ST annual international symposium on Computer architecture, p.211-222, April 18-21, 1994, Chicago, Illinois, United States
• 11: C. Hsieh and M. Pedram. Micro-processor power estimation using profile-driven program synthesis. IEEETCAD, 17(11):1080--1089, Nov. 1998.
• 12: V. S. Iyengar and L. H. Trevillyan. Evaluation and generation of reduced traces for benchmarks. Technical Report RC 20610, IBM Research Division, T. J. Watson Research Center, Oct. 1996.
• 13: Vijay S. Iyengar , Louise H. Trevillyan , Pradip Bose, Representative Traces for Processor Models with Infinite Cache, Proceedings of the 2nd IEEE Symposium on High-Performance Computer Architecture, p.62, February 03-07, 1996
• 14: M. Johnson. Superscalar Microprocessor Design. Prentice Hall, 1991.
• 15: 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
• 16: A. J. KleinOsowski and D. J. Lilja. MinneSPEC: A new SPEC benchmark workload for simulation-based computer architecture research. Computer Architecture Letters, 1(2):10--13, June 2002.
• 17: David Kroft, Lockup-free instruction fetch/prefetch cache organization, Proceedings of the 8th annual symposium on Computer Architecture, p.81-87, May 12-14, 1981, Minneapolis, Minnesota, United States
• 18: Shubhendu S. Mukherjee , Sarita V. Adve , Todd Austin , Joel Emer , Peter S. Magnusson, Performance Simulation Tools, Computer, v.35 n.2, p.38-39, February 2002 [doi>10.1109/2.982914]
• 19: 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
• 20: Sébastien Nussbaum , James E. Smith, Modeling Superscalar Processors via Statistical Simulation, Proceedings of the 2001 International Conference on Parallel Architectures and Compilation Techniques, p.15-24, September 08-12, 2001
• 21: Mark Oskin , Frederic T. Chong , Matthew Farrens, HLS: combining statistical and symbolic simulation to guide microprocessor designs, Proceedings of the 27th annual international symposium on Computer architecture, p.71-82, June 2000, Vancouver, British Columbia, Canada
• 22: Erez Perelman , Greg Hamerly , Brad Calder, Picking Statistically Valid and Early Simulation Points, Proceedings of the 12th International Conference on Parallel Architectures and Compilation Techniques, p.244, September 27-October 01, 2003
• 23: 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
• 24: Rabin A. Sugumar , Santosh G. Abraham, Efficient simulation of caches under optimal replacement with applications to miss characterization, Proceedings of the 1993 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.24-35, May 10-14, 1993, Santa Clara, California, United States
• 25: Roland E. Wunderlich , Thomas F. Wenisch , Babak Falsafi , James C. Hoe, SMARTS: accelerating microarchitecture simulation via rigorous statistical sampling, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California

INDEX TERMS

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

General Terms:
Experimentation, Measurement, Performance

Keywords:
memory data flow modeling, performance modeling, statistical simulation