Milind M. Chabbi
John M. Mellor-Crummey
Keith D. Cooper
ABSTRACT
Most compilers apply optimizations in a fixed order regardless of input programs. However, it is well known that optimizations can have enabling, and disabling interactions or equivalent effects. The effects of interference are program specific and hence no single sequence is universally appropriate for all input programs. In this paper we explore the problem of searching for optimal sequences of compiler optimizations to apply for a given program and describe novel strategies that bring us a step closer to searching this problem space efficiently. We also construct models for accurately predicting the runtime performance of a program when a sequence of optimizations is applied to it. The early results of the models on a small set of input programs are encouraging and suggest that the approaches we describe are worthy of further consideration.
- http://users.ece.gatech.edu/mrichard/ExascaleComputingStudyReports/exascale_final_report_100208.pdf.Google Scholar
- Almagor, L., Cooper, K. D., Grosul, A., Harvey, T. J., Reeves, S. W., Subramanian, D., Torczon, L., and Waterman, T. Finding effective compilation sequences. In Proceedings of the 2004 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems (2004), LCTES '04, ACM, pp. 231--239. Google ScholarDigital Library
- Baer, R. M. Nonlinear regression and the solution of simultaneous equations. Comm. ACM 5 (1962), 397--398. Google ScholarDigital Library
- Cavazos, J., Fursin, G., Agakov, F., Bonilla, E., O'Boyle, M. F. P., and Temam, O. Rapidly selecting good compiler optimizations using performance counters. In Proceedings of the International Symposium on Code Generation and Optimization (Washington, DC, USA, 2007), CGO '07, IEEE Computer Society, pp. 185--197. Google ScholarDigital Library
- Charikar, Makarychev, and Makarychev. On the advantage over random for maximum acyclic subgraph. In FOCS: IEEE Symposium on Foundations of Computer Science (FOCS) (2007). Google ScholarDigital Library
- Cohen, D. M., Dalal, S. R., Fredman, M. L., and Patton, G. C. The aetg system: An approach to testing based on combinatorial design. IEEE Trans. Softw. Eng. 23 (July 1997), 437--444. Google ScholarDigital Library
- Cooper, K. D., Grosul, A., Harvey, T. J., Reeves, S., Subramanian, D., Torczon, L., and Waterman, T. Exploring the structure of the space of compilation sequences using randomized search algorithms. The Journal of Supercomputing 36, 2 (May 2006), 135--151. Google ScholarDigital Library
- Cooper, K. D., Schielke, P. J., and Subramanian, D. Optimizing for reduced code space using genetic algorithms, 1999.Google Scholar
- Cooper, K. D., Subramanian, D., and Torczon, L. Adaptive optimizing compilers for the 21st century. Journal of Supercomputing 23 (2001), 2002. Google ScholarDigital Library
- Epshteyn, A., Garzaran, M., Dejong, G., Padua, D., Ren, G., Li, X., Yotov, K., and Pingali, K. Analytic models and empirical search: A hybrid approach to code optimization. In In Proceedings of the International Workshop on Languages and Compilers for Parallel Computing (LCPC (2005). Google ScholarDigital Library
- Forsythe, G., Malcolm, M., and Moler, C. Computer methods for mathematical computations. Prentice Hall, Englewood Cliffs, 1977. Google ScholarDigital Library
- Grindal, M., Offutt, J., and Andler, S. F. Combination testing strategies: a survey. Softw. Test, Verif. Reliab 15, 3 (2005), 167--199.Google ScholarCross Ref
- Hassin, R., and Rubinstein, S. Approximations for the maximum acyclic subgraph problem. Information Processing Letters 51 (1997), 133--140. Google ScholarDigital Library
- Hooke, R., and Jeeves, T. A. "Direct search" solution of numerical and statistical problems. Journal of the Association for Computing Machinery 8, 2 (1961), 212--229. Google ScholarDigital Library
- Hutter, M. Bayesian regression of piecewise constant functions, June 13 2006. Comment: 27 pages, 18 figures, 1 table, 3 algorithms.Google Scholar
- Kolda, Lewis, and Torczon. Optimization by direct search: New perspectives on some classical and modern methods. SIREV: SIAM Review 45 (2003).Google Scholar
- Kulkarni, P., Hines, S., Hiser, J., Whalley, D., Davidson, J., and Jones, D. Fast searches for effective optimization phase sequences. SIGPLAN Not. 39 (June 2004), 171--182. Google ScholarDigital Library
- Kulkarni, P. A., Whalley, D. B., Tyson, G. S., and Davidson, J. W. Exhaustive optimization phase order space exploration. In Proceedings of the International Symposium on Code Generation and Optimization (2006), CGO '06, pp. 306--318. Google ScholarDigital Library
- Lei, Y., and Tai, K.-C. In-parameter-order: A test generation strategy for pairwise testing. In The 3rd IEEE International Symposium on High-Assurance Systems Engineering (Washington, DC, USA, 1998), HASE '98, IEEE Computer Society, pp. 254--261. Google ScholarDigital Library
- Mandl, R. Orthogonal latin squares: an application of experiment design to compiler testing. Commun. ACM 28 (October 1985), 1054--1058. Google ScholarDigital Library
- Marcus, M. Matrices and MATLAB: a tutorial. The MATLAB curriculum series. Prentice-Hall, pub-PH:adr, 1992.Google Scholar
- Milojičić, D., Lazara, B., Stankovic, J., Preikschat, W. S., Iftode, L., Lea, R., and Rau, B. Trend wars: Embedded systems. IEEE Concurrency 8, 4 (Oct./Dec. 2000), 80--90. Google ScholarDigital Library
- Milojicic, D. S. Trend wars: Mobile agent applications. IEEE Concurrency 7, 3 (1999), 80--90. Google ScholarDigital Library
- Newman, A. Approximating the maximum acyclic subgraph. Master's thesis, Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2000.Google Scholar
- Olukotun, K., and Hammond, L. The future of microprocessors. Queue 3 (September 2005), 26--29. Google ScholarDigital Library
- Pan, Z., and Eigenmann, R. Fast and effective orchestration of compiler optimizations for automatic performance tuning. In Proceedings of the International Symposium on Code Generation and Optimization (Washington, DC, USA, 2006), CGO '06, IEEE Computer Society, pp. 319--332. Google ScholarDigital Library
- Qasem, A., Kennedy, K., and Mellor-crummey, J. Automatic tuning of whole applications using direct search and a performance-based transformation system. In In Proceedings of the Los Alamos Computer Science Institute Second Annual Symposium (2004), pp. 183--196.Google Scholar
- Schlett, M. Trends in embedded-microprocessor design. Computer 31 (August 1998), 44--49. Google ScholarDigital Library
- SPEC. Benchmark suite release 1.0, 1989.Google Scholar
- Tatsumi, K. Test case design support system. In Proceedings of the International Conference on Quality Control (ICQC), 3 (1987), 615--620.Google Scholar
- Vuduc, R., Demmel, J. W., and Bilmes, J. Bilmes. statistical models for empirical search-based performance tuning. International Journal of High Performance Computing Applications 18 (2004), 65--94. Google ScholarDigital Library
- Zhao, M., Childers, B. R., and Soffa, M. L. A framework for exploring optimization properties. In Proceedings of the 18th International Conference on Compiler Construction, ETAPS 2009 (Berlin, Heidelberg, 2009), CC '09, Springer-Verlag, pp. 32--47. Google ScholarDigital Library
Index Terms
- Efficiently exploring compiler optimization sequences with pairwise pruning
Recommendations
A Survey on Compiler Autotuning using Machine Learning
Since the mid-1990s, researchers have been trying to use machine-learning-based approaches to solve a number of different compiler optimization problems. These techniques primarily enhance the quality of the obtained results and, more importantly, make ...
Mitigating the compiler optimization phase-ordering problem using machine learning
OOPSLA '12: Proceedings of the ACM international conference on Object oriented programming systems languages and applicationsToday's compilers have a plethora of optimizations to choose from, and the correct choice of optimizations can have a significant impact on the performance of the code being optimized. Furthermore, choosing the correct order in which to apply those ...
Mitigating the compiler optimization phase-ordering problem using machine learning
OOPSLA '12Today's compilers have a plethora of optimizations to choose from, and the correct choice of optimizations can have a significant impact on the performance of the code being optimized. Furthermore, choosing the correct order in which to apply those ...
Comments