Efficiently exploring architectural design spaces via predictive modeling

ABSTRACT

Architects use cycle-by-cycle simulation to evaluate design choices and understand tradeoffs and interactions among design parameters. Efficiently exploring exponential-size design spaces with many interacting parameters remains an open problem: the sheer number of experiments renders detailed simulation intractable. We attack this problem via an automated approach that builds accurate, confident predictive design-space models. We simulate sampled points, using the results to teach our models the function describing relationships among design parameters. The models produce highly accurate performance estimates for other points in the space, can be queried to predict performance impacts of architectural changes, and are very fast compared to simulation, enabling efficient discovery of tradeoffs among parameters in different regions. We validate our approach via sensitivity studies on memory hierarchy and CPU design spaces: our models generally predict IPC with only 1-2% error and reduce required simulation by two orders of magnitude. We also show the efficacy of our technique for exploring chip multiprocessor (CMP) design spaces: when trained on a 1% sample drawn from a CMP design space with 250K points and up to 55x performance swings among different system configurations, our models predict performance with only 4-5% error on average. Our approach combines with techniques to reduce time per simulation, achieving net time savings of three-four orders of magnitude.

REFERENCES

• 1: G. Cai, K. Chow, T. Nakanishi, J. Hall, and M. Barany. Multivariate power/performance analysis for high performance mobile microprocessor design. In Power Driven Microarchitecture Workshop, June 1998.
• 2: R. Caruana, S. Lawrence, and C. Giles. Overfitting in neural nets: Backpropagation, conjugate gradient, and early stopping. In Proc. Neural Information Processing Systems Conference, pages 402--408, Nov. 2000.
• 3: K. Chow and J. Ding. Multivariate analysis of Pentium Pro processor. In Intel Software Developers Conference, pages 84--91, Oct. 1997.
• 4: 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
• 5: John D. Davis , James Laudon , Kunle Olukotun, Maximizing CMP Throughput with Mediocre Cores, Proceedings of the 14th International Conference on Parallel Architectures and Compilation Techniques, p.51-62, September 17-21, 2005 [doi>10.1109/PACT.2005.42]
• 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 , Yue Luo , Koen De Bosschere , Lizy K. John, BLRL: Accurate and Efficient Warmup for Sampled Processor Simulation, The Computer Journal, v.48 n.4, p.451-459, July 2005 [doi>10.1093/comjnl/bxh103]
• 8: L. Eeckhout, S. Nussbaum, J. Smith, and K. De Bosschere. Statistical simulation: Adding efficiency to the computer designer's toolbox. IEEE Micro, 23(5):26--38, 2003.
• 9: L. Eeckhout, H. Vandierendonck, and K. De Bosschere. Quantifying the impact of input data sets on program behavior and its applications. Journal of Instruction Level Parallelism, 5:http://www.jilp.org/vol5, Feb. 2003.
• 10: S. Eyerman, L. Eeckhout, and K.D. Bosschere. The shape of the processor design space and its implications for early stage explorations. In Proc. 7th WSEAS International Conference on Automatic Control, Modeling and Simulation, pages 395--400, Mar. 2005.
• 11: 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]
• 12: Minimal Subset Evaluation: Rapid Warm-Up for Simulated Hardware State, Proceedings of the International Conference on Computer Design: VLSI in Computers & Processors, p.32, September 23-26, 2001
• 13: R. S. Burugula , K. Skadron, Memory reference reuse latency: Accelerated warmup for sampled microarchitecture simulation, Proceedings of the 2003 IEEE International Symposium on Performance Analysis of Systems and Software, p.195-203, March 06-08, 2003
• 14: T. Hastie, R. Tibshirani, and J. Friedman. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer Verlag, 2001.
• 15: 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
• 16: Bruce Jacob, A Case for Studying DRAM Issues at the System Level, IEEE Micro, v.23 n.4, p.44-56, July 2003 [doi>10.1109/MM.2003.1225969]
• 17: P. Joseph, K. Vaswani, and M. Thazhuthaveetil. Use of linear regression models for processor performance analysis. In Proc. 12th IEEE Symposium on High Performance Computer Architecture, pages 99--108, Feb. 2006.
• 18: 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
• 19: A J KleinOsowski , David J. Lilja, MinneSPEC: A New SPEC Benchmark Workload for Simulation-Based Computer Architecture Research, IEEE Computer Architecture Letters, v.1 n.1, p.7, January 2006 [doi>10.1109/L-CA.2002.8]
• 20: Rakesh Kumar , Victor Zyuban , Dean M. Tullsen, Interconnections in Multi-Core Architectures: Understanding Mechanisms, Overheads and Scaling, Proceedings of the 32nd Annual International Symposium on Computer Architecture, p.408-419, June 04-08, 2005
• 21: 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
• 22: M. Martonosi and K. Skadron. NSF computer performance evaluation workshop http://www.princeton.edu/~mrm/nsf sim final.pdf, Dec. 2001.
• 23: C. Marzban. A neural network for tornado diagnosis. Neural Computing and Applications, 9(2):133--141, 2000.
• 24: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 25: Anish Muttreja , Anand Raghunathan , Srivaths Ravi , Niraj K. Jha, Automated energy/performance macromodeling of embedded software, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996599]
• 26: Anish Muttreja , Anand Raghunathan , Srivaths Ravi , Niraj K. Jha, Hybrid simulation for embedded software energy estimation, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA [doi>10.1145/1065579.1065590]
• 27: 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]
• 28: 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
• 29: A. Phansalkar, A. Joshi, L. Eeckhout, and L. John. Measuring program similarity: Experiments with SPEC CPU benchmark suites. In Proc. IEEE International Symposium on Performance Analysis of Systems and Software, pages 10--20, Mar. 2005.
• 30: D. Pomerleau. Knowledge-based training of artificial neural networks for autonomous robot driving. In J. Connell and S. Mahadevan, editors, Robot Learning, pages 19--43. Kluwer Academic Press, Boston, 1993.
• 31: Venkata Syam P. Rapaka , Diana Marculescu, Pre-Characterization Free, Efficient Power/Performance Analysis of Embedded and General Purpose Software Applications, Proceedings of the conference on Design, Automation and Test in Europe, p.10504, March 03-07, 2003
• 32: J. Renau. SESC. http://sesc.sourceforge.net/index.html.
• 33: M. Saar-Tsechansky and F. Provost. Active learning for class probability estimation and ranking. In Proc. 17th International Joint Conference on Artificial Intelligence, pages 911--920, Aug. 2001.
• 34: 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
• 35: Standard Performance Evaluation Corporation. SPEC CPU benchmark suite. http://www.specbench.org/osg/cpu2000/, 2000.
• 36: Gerald Tesauro, Temporal difference learning and TD-Gammon, Communications of the ACM, v.38 n.3, p.58-68, March 1995 [doi>10.1145/203330.203343]
• 37: M. Van Biesbrouck, L. Eeckhout, and B. Calder. Efficient sampling startup for sampled processor simulation. In Proc. 1st International Conference on High Performance Embedded Architectures and Compilers, pages 47--67, Nov. 2005.
• 38: Thomas F. Wenisch , Roland E. Wunderlich , Babak Falsafi , James C. Hoe, TurboSMARTS: accurate microarchitecture simulation sampling in minutes, ACM SIGMETRICS Performance Evaluation Review, v.33 n.1, June 2005
• 39: S.Wilton and N. Jouppi. CACTI: An enhanced cache access and cycle time model. IEEE Journal of Solid-State Circuits, 31(5):677--688, May 1996.
• 40: 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
• 41: Joshua J. Yi , David J. Lilja , Douglas M. Hawkins, A Statistically Rigorous Approach for Improving Simulation Methodology, Proceedings of the 9th International Symposium on High-Performance Computer Architecture, p.281, February 08-12, 2003

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

General Terms:
Design, Experimentation, Measurement

Keywords:
artificial neural networks, design space exploration, performance prediction, sensitivity studies