skip to main content
10.1145/2000417.2000421acmotherconferencesArticle/Chapter ViewAbstractPublication PagesexadaptConference Proceedingsconference-collections
research-article

Efficiently exploring compiler optimization sequences with pairwise pruning

Published: 05 June 2011 Publication History

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.

References

[1]
http://users.ece.gatech.edu/mrichard/ExascaleComputingStudyReports/exascale_final_report_100208.pdf.
[2]
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.
[3]
Baer, R. M. Nonlinear regression and the solution of simultaneous equations. Comm. ACM 5 (1962), 397--398.
[4]
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.
[5]
Charikar, Makarychev, and Makarychev. On the advantage over random for maximum acyclic subgraph. In FOCS: IEEE Symposium on Foundations of Computer Science (FOCS) (2007).
[6]
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.
[7]
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.
[8]
Cooper, K. D., Schielke, P. J., and Subramanian, D. Optimizing for reduced code space using genetic algorithms, 1999.
[9]
Cooper, K. D., Subramanian, D., and Torczon, L. Adaptive optimizing compilers for the 21st century. Journal of Supercomputing 23 (2001), 2002.
[10]
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).
[11]
Forsythe, G., Malcolm, M., and Moler, C. Computer methods for mathematical computations. Prentice Hall, Englewood Cliffs, 1977.
[12]
Grindal, M., Offutt, J., and Andler, S. F. Combination testing strategies: a survey. Softw. Test, Verif. Reliab 15, 3 (2005), 167--199.
[13]
Hassin, R., and Rubinstein, S. Approximations for the maximum acyclic subgraph problem. Information Processing Letters 51 (1997), 133--140.
[14]
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.
[15]
Hutter, M. Bayesian regression of piecewise constant functions, June 13 2006. Comment: 27 pages, 18 figures, 1 table, 3 algorithms.
[16]
Kolda, Lewis, and Torczon. Optimization by direct search: New perspectives on some classical and modern methods. SIREV: SIAM Review 45 (2003).
[17]
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.
[18]
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.
[19]
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.
[20]
Mandl, R. Orthogonal latin squares: an application of experiment design to compiler testing. Commun. ACM 28 (October 1985), 1054--1058.
[21]
Marcus, M. Matrices and MATLAB: a tutorial. The MATLAB curriculum series. Prentice-Hall, pub-PH:adr, 1992.
[22]
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.
[23]
Milojicic, D. S. Trend wars: Mobile agent applications. IEEE Concurrency 7, 3 (1999), 80--90.
[24]
Newman, A. Approximating the maximum acyclic subgraph. Master's thesis, Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2000.
[25]
Olukotun, K., and Hammond, L. The future of microprocessors. Queue 3 (September 2005), 26--29.
[26]
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.
[27]
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.
[28]
Schlett, M. Trends in embedded-microprocessor design. Computer 31 (August 1998), 44--49.
[29]
SPEC. Benchmark suite release 1.0, 1989.
[30]
Tatsumi, K. Test case design support system. In Proceedings of the International Conference on Quality Control (ICQC), 3 (1987), 615--620.
[31]
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.
[32]
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.

Cited By

View all
  • (2021)CTFS: A Configurable Tuning Framework on SHENWEI SystemProceedings of the 5th International Conference on High Performance Compilation, Computing and Communications10.1145/3471274.3471282(44-49)Online publication date: 18-Jun-2021
  • (2021)An experience with code-size optimization for production iOS mobile applicationsProceedings of the 2021 IEEE/ACM International Symposium on Code Generation and Optimization10.1109/CGO51591.2021.9370306(363-366)Online publication date: 27-Feb-2021
  • (2018)An Evaluation of Vectorization and Cache Reuse Tradeoffs on Modern CPUsProceedings of the 9th International Workshop on Programming Models and Applications for Multicores and Manycores10.1145/3178442.3178445(21-30)Online publication date: 24-Feb-2018
  • Show More Cited By

Index Terms

  1. Efficiently exploring compiler optimization sequences with pairwise pruning

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Other conferences
    EXADAPT '11: Proceedings of the 1st International Workshop on Adaptive Self-Tuning Computing Systems for the Exaflop Era
    June 2011
    73 pages
    ISBN:9781450307086
    DOI:10.1145/2000417
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 05 June 2011

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. compiler optimization
    2. optimization sequence
    3. phase ordering

    Qualifiers

    • Research-article

    Funding Sources

    Conference

    EXADAPT '11

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)1
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 14 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2021)CTFS: A Configurable Tuning Framework on SHENWEI SystemProceedings of the 5th International Conference on High Performance Compilation, Computing and Communications10.1145/3471274.3471282(44-49)Online publication date: 18-Jun-2021
    • (2021)An experience with code-size optimization for production iOS mobile applicationsProceedings of the 2021 IEEE/ACM International Symposium on Code Generation and Optimization10.1109/CGO51591.2021.9370306(363-366)Online publication date: 27-Feb-2021
    • (2018)An Evaluation of Vectorization and Cache Reuse Tradeoffs on Modern CPUsProceedings of the 9th International Workshop on Programming Models and Applications for Multicores and Manycores10.1145/3178442.3178445(21-30)Online publication date: 24-Feb-2018
    • (2013)A Study on the Impact of Compiler Optimizations on High-Level SynthesisLanguages and Compilers for Parallel Computing10.1007/978-3-642-37658-0_10(143-157)Online publication date: 2013
    • (2012)An embedded cross-assembler optimization method2012 International Conference on Computer Science and Information Processing (CSIP)10.1109/CSIP.2012.6308935(641-644)Online publication date: Aug-2012

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media