Automatic performance model construction for the fast software exploration of new hardware designs

ABSTRACT

Developing an optimizing compiler for a newly proposed architecture is extremely difficult when there is only a simulator of the machine available. Designing such a compiler requires running many experiments in order to understand how different optimizations interact. Given that simulators are orders of magnitude slower than real processors, such experiments are highly restricted. This paper develops a technique to automatically build a performance model for predicting the impact of program transformations on any architecture, based on a limited number of automatically selected runs. As a result, the time for evaluating the impact of any compiler optimization in early design stages can be drastically reduced such that all selected potential compiler optimizations can be evaluated. This is achieved by first evaluating a small set of sample compiler optimizations on a prior set of benchmarks in order to train a model, followed by a very small number of evaluations, or probes, of the target program.We show that by training on less than 0. 7% of all possible transformations (640 samples collected from 10 benchmarks out of 880000 possible samples, 88000 per training benchmark) and probing the new program on only 4 transformations, we can predict the performance of all program transformations with an error of just 7. 3% on average. As each prediction takes almost no time to generate, this scheme provides an accurate method of evaluating compiler performance, which is several orders of magnitude faster than current approaches.

REFERENCES

• 1: F. Agakov , E. Bonilla , J. Cavazos , B. Franke , G. Fursin , M. F. P. O'Boyle , J. Thomson , M. Toussaint , C. K. I. Williams, Using Machine Learning to Focus Iterative Optimization, Proceedings of the International Symposium on Code Generation and Optimization, p.295-305, March 26-29, 2006 [doi>10.1109/CGO.2006.37]
• 2: L. Almagor , Keith D. Cooper , Alexander Grosul , Timothy J. Harvey , Steven W. Reeves , Devika Subramanian , Linda Torczon , Todd Waterman, Finding effective compilation sequences, Proceedings of the 2004 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 11-13, 2004, Washington, DC, USA
• 3: L. R. Bachega , J. R. Brunheroto , L. DeRose , P. Mindlin , J. E. Moreira, The BlueGene/L pseudo cycle-accurate simulator, Proceedings of the 2004 IEEE International Symposium on Performance Analysis of Systems and Software, p.36-44, March 10-12, 2004
• 4: H. Berry, D. G. Prez, and O. Temam. Chaos in computer performance. Chaos, 16(1), Dec. 2005.
• 5: Christopher M. Bishop, Neural networks for pattern recognition, Oxford University Press, Oxford, 1996
• 6: L. Breiman, J. Friedman, R. Olshen, and C. Stone. Classification and Regression Trees. Chapman and Hall, 1984.
• 7: John Cavazos , J. Eliot , B. Moss, Inducing heuristics to decide whether to schedule, Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, June 09-11, 2004, Washington DC, USA
• 8: K. D. Cooper, A. Grosul, T. Harvey, S. Reeves, D. Subramanian, L. Torczon, , and T. Waterman. Searching for compilation sequences. Tech. report, Rice University, 2005.
• 9: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 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: A. Epshteyn, M. Garzaran, G. DeJong, D. Padua, G. Ren, X. Li, K. Yotov, and K. Pingali. Analytic models and empirical search: A hybrid approach to code optimization. In Proceedings of the International Workshop on Languages and Compilers for Parallel Computing (LCPC), Hawthorne, NY, USA, 2005.
• 12: Björn Franke , Michael O'Boyle , John Thomson , Grigori Fursin, Probabilistic source-level optimisation of embedded programs, Proceedings of the 2005 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 15-17, 2005, Chicago, Illinois, USA
• 13: M. Frigo and S. G. Johnson. FFTW: An adaptive software architecture for the FFT. In Proc. IEEE Intl. Conf. on Acoustics, Speech, and Signal Processing, volume 3, pages 1381--1384, Seattle, WA, May 1998.
• 14: Mary W. Hall , Jennifer M. Anderson , Saman P. Amarasinghe , Brian R. Murphy , Shih-Wei Liao , Edouard Bugnion , Monica S. Lam, Maximizing Multiprocessor Performance with the SUIF Compiler, Computer, v.29 n.12, p.84-89, December 1996 [doi>10.1109/2.546613]
• 15: 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
• 16: R. A. Jacobs, M. I. Jordan, S. J. Nowlan, and G. E. Hinton. Adaptive Mixtures of Local Experts. Neural Computation, 3, 1991.
• 17: 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
• 18: Prasad Kulkarni , Wankang Zhao , Hwashin Moon , Kyunghwan Cho , David Whalley , Jack Davidson , Mark Bailey , Yunheung Paek , Kyle Gallivan, Finding effective optimization phase sequences, Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool for embedded systems, June 11-13, 2003, San Diego, California, USA
• 19: C. Lee. Utdsp benchmark suite. In http://www. eecg. toronto. edu/~corinna/DSP/infrastructure/UTDSP. html, 1998.
• 20: Antoine Monsifrot , François Bodin , Rene Quiniou, A Machine Learning Approach to Automatic Production of Compiler Heuristics, Proceedings of the 10th International Conference on Artificial Intelligence: Methodology, Systems, and Applications, p.41-50, September 04-06, 2002
• 21: Zhelong Pan , Rudolf Eigenmann, Fast, automatic, procedure-level performance tuning, Proceedings of the 15th international conference on Parallel architectures and compilation techniques, September 16-20, 2006, Seattle, Washington, USA [doi>10.1145/1152154.1152182]
• 22: David Parello , Olivier Temam , Albert Cohen , Jean-Marie Verdun, Towards a Systematic, Pragmatic and Architecture-Aware Program Optimization Process for Complex Processors, Proceedings of the 2004 ACM/IEEE conference on Supercomputing, p.15, November 06-12, 2004 [doi>10.1109/SC.2004.61]
• 23: M. Püschel, J. M. F. Moura, J. Johnson, D. Padua, M. Veloso, B. W. Singer, J. Xiong, F. Franchetti, A. Gacić, Y. Voronenko, K. Chen, R. W. Johnson, and N. Rizzolo. SPIRAL: Code generation for DSP transforms. Proceedings of the IEEE, special issue on "Program Generation, Optimization, and Adaptation", 93(2):232--275, 2005.
• 24: M. Saghir, P. Chow, and C. Lee. A comparison of traditional and vliw dsp architecture for compiled dsp applications. In Proceedings of the International Workshop on Compiler and Architecture Support for Embedded Systems (CASES), Washington, DC, USA, 1998.
• 25: 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
• 26: Mark Stephenson , Saman Amarasinghe, Predicting Unroll Factors Using Supervised Classification, Proceedings of the international symposium on Code generation and optimization, p.123-134, March 20-23, 2005 [doi>10.1109/CGO.2005.29]
• 27: Mark Stephenson , Saman Amarasinghe , Martin Martin , Una-May O'Reilly, Meta optimization: improving compiler heuristics with machine learning, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 28: Spyridon Triantafyllis , Manish Vachharajani , Neil Vachharajani , David I. August, Compiler optimization-space exploration, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
• 29: Thomas F. Wenisch , Roland E. Wunderlich , Babak Falsafi , James C. Hoe, TurboSMARTS: accurate microarchitecture simulation sampling in minutes, Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 06-10, 2005, Banff, Alberta, Canada
• 30: R. Clint Whaley , Jack J. Dongarra, Automatically tuned linear algebra software, Proceedings of the 1998 ACM/IEEE conference on Supercomputing (CDROM), p.1-27, November 07-13, 1998, San Jose, CA
• 31: 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
• 32: Kamen Yotov , Xiaoming Li , Gang Ren , Michael Cibulskis , Gerald DeJong , Maria Garzaran , David Padua , Keshav Pingali , Paul Stodghill , Peng Wu, A comparison of empirical and model-driven optimization, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 33: Kamen Yotov , Keshav Pingali , Paul Stodghill, Think globally, search locally, Proceedings of the 19th annual international conference on Supercomputing, June 20-22, 2005, Cambridge, Massachusetts [doi>10.1145/1088149.1088168]
• 34: Min Zhao , Bruce R. Childers , Mary Lou Soffa, A Model-Based Framework: An Approach for Profit-Driven Optimization, Proceedings of the international symposium on Code generation and optimization, p.317-327, March 20-23, 2005 [doi>10.1109/CGO.2005.2]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Induction

General Terms:
Experimentation, Languages, Performance

Keywords:
architecture, artificial neural networks, compiler optimization, machine learning, performance modelling