Efficient architectural design space exploration via predictive modeling

ABSTRACT

Efficiently exploring exponential-size architectural design spaces with many interacting parameters remains an open problem: the sheer number of experiments required renders detailed simulation intractable. We attack this via an automated approach that builds accurate predictive models. We simulate sampled points, using results to teach our models the function describing relationships among design parameters. The models can be queried and are very fast, enabling efficient design tradeoff discovery. We validate our approach via two uniprocessor sensitivity studies, predicting IPC with only 1--2% error. In an experimental study using the approach, training on 1% of a 250-K-point CMP design space allows our models to predict performance with only 4--5% error. Our predictive modeling combines well with techniques that reduce the time taken by each simulation experiment, achieving net time savings of three-four orders of magnitude.

REFERENCES

• 1: Bigus, J. 1994a. Applying neural networks to computer system performance tuning. In Proc. IEEE International Conference on Neural Networks.
• 2: Bigus, J. 1994b. Computer system performance modeling using neural networks. In Proc. International Neural Network Society Conference. 510--515.
• 3: Borkar, S., Dubey, P., Kahn, K., Kuck, D., Mulder, H., Pawlowski, S., and Rattner, J. 2006. Platform 2015: Intel processsor and platform evolution for the next decade. White Paper, Intel Corporation.
• 4: Cai, G., Chow, K., Nakanishi, T., Hall, J., and Barany, M. 1998. Multivariate power/performance analysis for high performance mobile microprocessor design. In Power Driven Microarchitecture Workshop.
• 5: Caruana, R., Lawrence, S., and Giles, C. 2000. Overfitting in neural nets: Backpropagation, conjugate gradient, and early stopping. In Proc. Neural Information Processing Systems Conference.
• 6: Chow, K. and Ding, J. 1997. Multivariate analysis of Pentium Pro processor. In Intel Software Developers Conference. 84--91.
• 7: 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
• 8: 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]
• 9: Eeckhout, L., Nussbaum, S., Smith, J., and De Bosschere, K. 2003b. Statistical simulation: Adding efficiency to the computer designer's toolbox. IEEE Micro 23, 5, 26--38.
• 10: 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
• 11: 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]
• 12: Eeckhout, L., Vandierendonck, H., and De Bosschere, K. 2003a. Quantifying the impact of input data sets on program behavior and its applications. Journal of Instruction Level Parallelism 5, http://www.jilp.org/vol5.
• 13: 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
• 14: 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]
• 15: 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
• 16: 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
• 17: Hastie, T., Tibshirani, R., and Friedman, J. 2001. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer Verlag, New York.
• 18: Ipek, E., de Supinski, B., Schulz, M., and McKee, S. 2005. An approach to performance prediction for parallel applications. In Proc. ACM/IEEE Euro-Par International European Conference on Parallel Computing. 196--205.
• 19: 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
• 20: 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
• 21: 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]
• 22: 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]
• 23: Joseph, P., Vaswani, K., and Thazhuthaveetil, M. 2006b. Use of linear regression models for processor performance analysis. In Proc. 12th IEEE Symposium on High Performance Computer Architecture. 99--108.
• 24: 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
• 25: 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 2002 [doi>10.1109/L-CA.2002.8]
• 26: Poonacha Kongetira , Kathirgamar Aingaran , Kunle Olukotun, Niagara: A 32-Way Multithreaded Sparc Processor, IEEE Micro, v.25 n.2, p.21-29, March 2005 [doi>10.1109/MM.2005.35]
• 27: B. Kumar , E. S. Davidson, Computer system design using a hierarchical approach to performance evaluation, Communications of the ACM, v.23 n.9, p.511-521, Sept. 1980 [doi>10.1145/359007.359012]
• 28: 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
• 29: Kunkel, S., Eickemeyer, R., Lipasti, M., Mullins, T., O'Krafka, B., Rosenberg, H., VanderWiel, S., Vitale, P., and Whitley, L. 2000. A performance methodology for commercial servers. IBM Journal of Research and Development 44, 6, 851--872.
• 30: 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
• 31: Li, Y., Lee, B., Brooks, D., Hu, Z., and Skadron, K. 2006. CMP design space exploration subject to physical constraints. In Proc. 12th IEEE Symposium on High Performance Computer Architecture. 15--26.
• 32: Martonosi, M. and Skadron, K. 2001. NSF computer performance evaluation workshop: Summary and action items. http://www.princeton.edu/~mrm/nsf_sim_final.pdf.
• 33: Marzban, C. 2000. A neural network for tornado diagnosis. Neural Computing and Applications 9, 2, 133--141.
• 34: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 35: 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]
• 36: 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, Anaheim, California, USA [doi>10.1145/1065579.1065590]
• 37: 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]
• 38: 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
• 39: A. Phansalkar , A. Joshi , L. Eeckhout , L. K. John, Measuring Program Similarity: Experiments with SPEC CPU Benchmark Suites, Proceedings of the IEEE International Symposium on Performance Analysis of Systems and Software, 2005, p.10-20, March 20-22, 2005 [doi>10.1109/ISPASS.2005.1430555]
• 40: Pomerleau, D. 1993. Knowledge-based training of artificial neural networks for autonomous robot driving. In Robot Learning, J. Connell and S. Mahadevan, Eds. Kluwer Academic Publ., Boston, MA. 19--43.
• 41: Ramanathan, R. 2006. Intel multi-core processors: Making the move to quad-core and beyond. White Paper, Intel Corporation.
• 42: 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
• 43: Renau, J. 2002. SESC. http://sesc.sourceforge.net/index.html.
• 44: Saar-Tsechansky, M. and Provost, F. 2001. Active learning for class probability estimation and ranking. In Proc. 17th International Joint Conference on Artificial Intelligence. 911--920.
• 45: 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
• 46: 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]
• 47: Van Biesbrouck, M., Eeckhout, L., and Calder, B. 2005. Efficient sampling startup for sampled processor simulation. In Proc. 1st International Conference on High Performance Embedded Architectures and Compilers. 47--67.
• 48: 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
• 49: Wilton, S. and Jouppi, N. 1996. CACTI: An enhanced cache access and cycle time model. IEEE Journal of Solid-State Circuits 31, 5 (May), 677--688.
• 50: 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
• 51: Yuan Xie , Gabriel H. Loh , Bryan Black , Kerry Bernstein, Design space exploration for 3D architectures, ACM Journal on Emerging Technologies in Computing Systems (JETC), v.2 n.2, p.65-103, April 2006 [doi>10.1145/1148015.1148016]
• 52: 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
• 53: Yoo, R., Lee, H., Chow, K., and Lee, H. 2006. Constructing a non-linear model with neural networks for workload characterization. In Proc. IEEE International Symposium on Workload Characterization. 150--159.
• 54: Shengke Yu , Marianne Winslett , Jonghyun Lee , Xiaosong Ma, Automatic and portable performance modeling for parallel I/O: a machine-learning approach, ACM SIGMETRICS Performance Evaluation Review, v.30 n.3, December 2002 [doi>10.1145/605521.605524]

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