Raced profiles: efficient selection of competing compiler optimizations

ABSTRACT

Many problems in embedded compilation require one set of optimizations to be selected over another based on run time performance. Self-tuned libraries, iterative compilation and machine learning techniques all compare multiple compiled program versions. In each, program versions are timed to determine which has the best performance.

The program needs to be run multiple times for each version because there is noise inherent in most performance measurements. The number of runs must be enough to compare different versions, despite the noise, but executing more than this will waste time and energy. The compiler writer must either risk taking too few runs, potentially getting incorrect results, or taking too many runs increasing the time for their experiments or reducing the number of program versions evaluated. Prior works choose constant size sampling plans where each compiled version is executed a fixed number of times without regard to the level of noise.

In this paper we develop a sequential sampling plan which can automatically adapt to the experiment so that the compiler writer can have both confidence in the results and also be sure that no more runs were taken than were needed. We show that our system is able to correctly determine the best optimization settings with between 76% and 87% fewer runs than needed by a brute force, constant sampling size approach. We also compare our approach to JavaSTATS(10); we needed 77% to 89% fewer runs than it needed.

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: Stephen M. Blackburn , Robin Garner , Chris Hoffmann , Asjad M. Khang , Kathryn S. McKinley , Rotem Bentzur , Amer Diwan , Daniel Feinberg , Daniel Frampton , Samuel Z. Guyer , Martin Hirzel , Antony Hosking , Maria Jump , Han Lee , J. Eliot B. Moss , B. Moss , Aashish Phansalkar , Darko Stefanović , Thomas VanDrunen , Daniel von Dincklage , Ben Wiedermann, The DaCapo benchmarks: java benchmarking development and analysis, Proceedings of the 21st annual ACM SIGPLAN conference on Object-oriented programming systems, languages, and applications, October 22-26, 2006, Portland, Oregon, USA
• 4: J Martin Bland and Douglas G Altman. Transforming data. BMJ (Clinical research ed.), 312, mar 1996.
• 5: B.L. Welch. The generalization of 'student's' problem when several different population varlances are involved. Biometrika, 34:28--35, 1947.
• 6: F. Bodin, T. Kisuk, P. M. W. Knijnenburg, M. F. P. O'Boyle, and E. Rohou. Iterative compilation in a non-linear optimisation space. In Workshop on Prole 14 and Feedback-Directed Compilation, in Conjunction with the International Conference on Parallel Architectures and Compilation Techniques (PACT), 10 1998.
• 7: G. E. P. Box and D. R. Cox. An analysis of transformations. Journal of the Royal Statistical Society. Series B (Methodological), 26(2):211--252, 1964.
• 8: E.C.Fieller. Some problems in interval estimation. Journal of the Royal Statistical Society, 16:175--185, 1954.
• 9: Grigori Fursin, Cupertino Miranda, Olivier Temam, Mircea Namolaru, Elad Yom-Tov, Ayal Zaks, Bilha Mendelson, Phil Barnard, Elton Ashton, Eric Courtois, Francois Bodin, Edwin Bonilla, John Thomson, Hugh Leather, Chris Williams, and Michael O'Boyle. Milepost gcc: machine learning based research compiler. In Proceedings of the GCC Developers'; Summit, June 2008.
• 10: Andy Georges , Dries Buytaert , Lieven Eeckhout, Statistically rigorous java performance evaluation, ACM SIGPLAN Notices, v.42 n.10, October 2007
• 11: Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13--30, March 1963.
• 12: Prasad Kulkarni , Wankang Zhao , Hwashin Moon , Kyunghwan Cho , David Whalley , Jack Davidson , Mark Bailey , Yunheung Paek , Kyle Gallivan, Finding effective optimization phase sequences, ACM SIGPLAN Notices, v.38 n.7, July 2003
• 13: M.A.Creasy. Confidence limits for the gradient in the linear functional relationship. Journal of the Royal Statistical Society, 18:64--69, 1956.
• 14: H. B. Mann and D. R. Whitney. On a test of whether one of two random variables is stochastically larger than the other. Annals of Mathematical Statistics, 18:50--60, 1947.
• 15: Oded Maron and Andrew W. Moore. Hoeffding races: Accelerating model selection search for classification and function approximation. In Advances in neural information processing systems 6, pages 59--66. Morgan Kaufmann, 1994.
• 16: Oden Maron , Andrew W. Moore, The Racing Algorithm: Model Selection for Lazy Learners, Artificial Intelligence Review, v.11 n.1-5, p.193-225, Feb. 1997 [doi>10.1023/A:1006556606079]
• 17: 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
• 18: Eliot Moss , Paul Utgoff , John Cavazos , Carla Brodley , David Scheeff , Doina Precup , Darko Stefanović, Learning to schedule straight-line code, Proceedings of the 1997 conference on Advances in neural information processing systems 10, p.929-935, July 1998, Denver, Colorado, United States
• 19: Todd Mytkowicz , Amer Diwan , Matthias Hauswirth , Peter F. Sweeney, Producing wrong data without doing anything obviously wrong!, Proceeding of the 14th international conference on Architectural support for programming languages and operating systems, March 07-11, 2009, Washington, DC, USA
• 20: Armitage P. and Healy M.J.R. Interpretation of Χ² tests. Biometrics, 13:113-115, 1957.
• 21: F. E. Satterthwaite. An approximate distribution of estimates of variance components. Biometrics Bulletin, 2:110--114, 1946.
• 22: 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]
• 23: Mark Stephenson , Saman Amarasinghe , Martin Martin , Una-May O'Reilly, Meta optimization: improving compiler heuristics with machine learning, ACM SIGPLAN Notices, v.38 n.5, May 2003
• 24: W.S.Gosset (Student). The probable error of a mean. Biometrika, 6:1--25, March 1908.
• 25: Abraham Wald. Sequential Analysis. 1947.
• 26: Stefan Wellek. Testing Statistical Hypotheses of Equivalence. CRC Press, 2003.
• 27: G.Barrie Wetherill and K.D. Glazebrook. Sequential methods in statistics. 3rd ed. London: Chapman and Hall, 1986.
• 28: John Whitehead. The Design and Analysis of Sequential Trials. Ellis Horwood, 1992.
• 29: W.J.Westlake. Use of confidence intervals in analysis of comparative bioavailability trials. Journal of Pharmaceutical Science, 61:1340--1341, 1972.

INDEX TERMS

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

General Terms:
Measurement, Performance

Keywords:
iterative compilation, statistics