More Web Proxy on the site http://driver.im/

Article

Fast and Effective Orchestration of Compiler Optimizations for Automatic Performance Tuning

Authors:

Rudolf EigenmannAuthors Info & Claims

CGO '06: Proceedings of the International Symposium on Code Generation and Optimization

Pages 319 - 332

https://doi.org/10.1109/CGO.2006.38

Published: 26 March 2006 Publication History

Abstract

Although compile-time optimizations generally improve program performance, degradations caused by individual techniques are to be expected. One promising research direction to overcome this problem is the development of dynamic, feedback-directed optimization orchestration algorithms, which automatically search for the combination of optimization techniques that achieves the best program performance. The challenge is to develop an orchestration algorithm that finds, in an exponential search space, a solution that is close to the best, in acceptable time. In this paper, we build such a fast and effective algorithm, called Combined Elimination (CE). The key advance of CE over existing techniques is that it takes the least tuning time (57% of the closest alternative), while achieving the same program performance. We conduct the experiments on both a Pentium IV machine and a SPARC II machine, by measuring performance of SPEC CPU2000 benchmarks under a large set of 38 GCC compiler options. Furthermore, through orchestrating a small set of optimizations causing the most degradation, we show that the performance achieved by CE is close to the upper bound obtained by an exhaustive search algorithm. The gap is less than 0.2% on average.

References

[1]

{1} Forte C 6 /Sun WorkShop 6 Compilers C User's Guide. http://docs.sun.com/app/docs/doc/806-3567.

[2]

{2} GCC online documentation. http://gcc.gnu.org/onlinedocs/.

[3]

{3} L. Almagor, K. D. Cooper, A. Grosul, T. J. Harvey, S. W. Reeves, D. Subramanian, L. Torczon and T. Waterman. Finding effective compilation sequences. In LCTES '04: Proceedings of the 2004 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems , pages 231-239, New York, NY, USA, 2004. ACM Press.

Digital Library

[4]

{4} G. E. P. Box, W. G. Hunter and J. S. Hunter. Statistics for experimenters : an introduction to design, data analysis, and model building. John Wiley and Sons, 1978.

[5]

{5} K. Chow and Y. Wu. Feedback-directed selection and characterization of compiler optimizations. In Second Workshop on Feedback Directed Optimizations, Israel, November 1999.

[6]

{6} K. D. Cooper, D. Subramanian and L. Torczon. Adaptive optimizing compilers for the 21st century. The Journal of Supercomputing, 23(1):7-22, 2002.

Digital Library

[7]

{7} E. D. Granston and A. Holler. Automatic recommendation of compiler options. In 4th Workshop on Feedback-Directed and Dynamic Optimization (FDDO-4), December 2001.

[8]

{8} M. Haneda, P. Knijnenburg and H. Wijshoff. Generating new general compiler optimization settings. In Proceedings of the 19th ACM International Conference on Supercomputing , pages 161-168, June 2005.

Digital Library

[9]

{9} A. Hedayat, N. Sloane and J. Stufken. Orthogonal Arrays: Theory and Applications. Springer, 1999.

[10]

{10} T. Kisuki, P. M. W. Knijnenburg and M. F. P. O'Boyle. Combined selection of tile sizes and unroll factors using iterative compilation. In IEEE PACT, pages 237-248, 2000.

Digital Library

[11]

{11} T. Kisuki, P. M. W. Knijnenburg, M. F. P. O'Boyle, F. Bodin, and H. A. G. Wijshoff. A feasibility study in iterative compilation. In International Symposium on High Performance Computing (ISHPC'99), pages 121-132, 1999.

Digital Library

[12]

{12} P. Kulkarni, S. Hines, J. Hiser, D. Whalley, J. Davidson and D. Jones. Fast searches for effective optimization phase sequences. In PLDI '04: Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation , pages 171-182, New York, NY, USA, 2004. ACM Press.

Digital Library

[13]

{13} Z. Pan and R. Eigenmann. Compiler optimization orchestration for peak performance. Technical Report TR-ECE-04- 01, School of Electrical and Computer Engineering, Purdue University, 2004.

[14]

{14} Z. Pan and R. Eigenmann. Rating compiler optimizations for automatic performance tuning. In SC2004: High Performance Computing, Networking and Storage Conference, page (10 pages), November 2004.

Digital Library

[15]

{15} R. P. J. Pinkers, P. M. W. Knijnenburg, M. Haneda and H. A. G. Wijshoff. Statistical selection of compiler options. In The IEEE Computer Societys 12th Annual International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunications Systems (MASCOTS' 04), pages 494-501, Volendam, The Netherlands, October 2004.

Digital Library

[16]

{16} N. J. A. Sloane. A Library of Orthogonal Arrays. http://www.research.att.com/njas/oadir/.

[17]

{17} M. Stephenson, S. Amarasinghe, M. Martin and U.-M. O'Reilly. Meta optimization: improving compiler heuristics with machine learning. In Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, pages 77-90. ACM Press, 2003.

Digital Library

[18]

{18} S. Triantafyllis, M. Vachharajani, N. Vachharajani and D. I. August. Compiler optimization-space exploration. In Proceedings of the international symposium on Code generation and optimization, pages 204-215, 2003.

Digital Library

[19]

{19} M. J. Voss and R. Eigenmann. High-level adaptive program optimization with ADAPT. In Proceedings of the eighth ACM SIGPLAN symposium on principles and practices of parallel programming, pages 93-102. ACM Press, 2001.

Digital Library

[20]

{20} R. C. Whaley and J. Dongarra. Automatically tuned linear algebra software. In SuperComputing 1998: High Performance Networking and Computing, 1998.

Digital Library

Cited By

Sachan ASrivastav PGhoshal B(2022)Learning based application driven energy aware compilation for GPUMicroprocessors & Microsystems10.1016/j.micpro.2022.10466494:COnline publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1016/j.micpro.2022.104664
Sachan AGhoshal B(2021)Learning based compilation of embedded applications targeting minimal energy consumption▪Journal of Systems Architecture: the EUROMICRO Journal10.1016/j.sysarc.2021.102116116:COnline publication date: 1-Jun-2021
https://dl.acm.org/doi/10.1016/j.sysarc.2021.102116
Zanella Ada Silva AQuintão FCavalcante EDantas FBatista T(2020)YACOSProceedings of the 24th Brazilian Symposium on Context-Oriented Programming and Advanced Modularity10.1145/3427081.3427089(56-63)Online publication date: 19-Oct-2020
https://dl.acm.org/doi/10.1145/3427081.3427089
Show More Cited By

Index Terms

Fast and Effective Orchestration of Compiler Optimizations for Automatic Performance Tuning
1. Computing methodologies
  1. Machine learning
2. Software and its engineering
  1. Software notations and tools
    1. Compilers

Recommendations

Tuning Compiler Optimizations for Simultaneous Multithreading
Special issue on the 30th annual ACM/IEEE international symposium on microarchitecture, part II

Simultaneous Multithreading (SMT) is a processor architectural technique that promises to significantly improve the utilization and performance of modern wide-issue superscalar processors. An SM T processor is capable of issuing multiple instructions ...
Tuning compiler optimizations for simultaneous multithreading
MICRO 30: Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture

Compiler optimizations are often driven by specific assumptions about the underlying architecture and implementation of the target machine. For example, when targeting shared-memory multiprocessors, parallel programs are compiled to minimize sharing, in ...
PEAK—a fast and effective performance tuning system via compiler optimization orchestration

Compile-time optimizations generally improve program performance. Nevertheless, degradations caused by individual compiler optimization techniques are to be expected. Feedback-directed optimization orchestration systems generate optimized code versions ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CGO '06: Proceedings of the International Symposium on Code Generation and Optimization

March 2006

347 pages

ISBN:0769524990

Sponsors

Publisher

IEEE Computer Society

United States

Publication History

Published: 26 March 2006

Check for updates

Qualifiers

Article

Conference

CGO06

Sponsor:

CGO06: 4th Annual IEEE / ACM International Symposium on Code Generation and Optimization

March 26 - 29, 2006

Acceptance Rates

CGO '06 Paper Acceptance Rate 29 of 80 submissions, 36%;

Overall Acceptance Rate 312 of 1,061 submissions, 29%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

43
Total Citations
View Citations
441
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)1

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Sachan ASrivastav PGhoshal B(2022)Learning based application driven energy aware compilation for GPUMicroprocessors & Microsystems10.1016/j.micpro.2022.10466494:COnline publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1016/j.micpro.2022.104664
Sachan AGhoshal B(2021)Learning based compilation of embedded applications targeting minimal energy consumption▪Journal of Systems Architecture: the EUROMICRO Journal10.1016/j.sysarc.2021.102116116:COnline publication date: 1-Jun-2021
https://dl.acm.org/doi/10.1016/j.sysarc.2021.102116
Zanella Ada Silva AQuintão FCavalcante EDantas FBatista T(2020)YACOSProceedings of the 24th Brazilian Symposium on Context-Oriented Programming and Advanced Modularity10.1145/3427081.3427089(56-63)Online publication date: 19-Oct-2020
https://dl.acm.org/doi/10.1145/3427081.3427089
Wang TJain NBoehme DBeckingsale DMueller FGamblin TAyguadé EHwu WBadia RHofstee H(2020)CodeSeerProceedings of the 34th ACM International Conference on Supercomputing10.1145/3392717.3392741(1-11)Online publication date: 29-Jun-2020
https://dl.acm.org/doi/10.1145/3392717.3392741
Ou PDemsky B(2018)Towards understanding the costs of avoiding out-of-thin-air resultsProceedings of the ACM on Programming Languages10.1145/32765062:OOPSLA(1-29)Online publication date: 24-Oct-2018
https://dl.acm.org/doi/10.1145/3276506
Ashouri AKillian WCavazos JPalermo GSilvano C(2018)A Survey on Compiler Autotuning using Machine LearningACM Computing Surveys10.1145/319797851:5(1-42)Online publication date: 18-Sep-2018
https://dl.acm.org/doi/10.1145/3197978
Filipovič JPetrovič FBenkner S(2017)Autotuning of OpenCL Kernels with Global OptimizationsProceedings of the 1st Workshop on AutotuniNg and aDaptivity AppRoaches for Energy efficient HPC Systems10.1145/3152821.3152877(1-6)Online publication date: 9-Sep-2017
https://dl.acm.org/doi/10.1145/3152821.3152877
Boussaa MBarais OBaudry BSunyé G(2016)Automatic non-functional testing of code generators familiesACM SIGPLAN Notices10.1145/3093335.299325652:3(202-212)Online publication date: 20-Oct-2016
https://dl.acm.org/doi/10.1145/3093335.2993256
Boussaa MBarais OBaudry BSunyé GFischer BSchaefer I(2016)Automatic non-functional testing of code generators familiesProceedings of the 2016 ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences10.1145/2993236.2993256(202-212)Online publication date: 20-Oct-2016
https://dl.acm.org/doi/10.1145/2993236.2993256
Sikora ACésar EComprés IGerndt MKumar ASarkar SGerndt M(2016)Autotuning of MPI Applications Using PTFProceedings of the ACM Workshop on Software Engineering Methods for Parallel and High Performance Applications10.1145/2916026.2916028(31-38)Online publication date: 31-May-2016
https://dl.acm.org/doi/10.1145/2916026.2916028
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents