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

research-article

Evaluating iterative optimization across 1000 datasets

Authors:

Lieven Eeckhout,

Grigori Fursin,

Chengyong WuAuthors Info & Claims

PLDI '10: Proceedings of the 31st ACM SIGPLAN Conference on Programming Language Design and Implementation

Pages 448 - 459

https://doi.org/10.1145/1806596.1806647

Published: 05 June 2010 Publication History

Abstract

While iterative optimization has become a popular compiler optimization approach, it is based on a premise which has never been truly evaluated: that it is possible to learn the best compiler optimizations across data sets. Up to now, most iterative optimization studies find the best optimizations through repeated runs on the same data set. Only a handful of studies have attempted to exercise iterative optimization on a few tens of data sets.

In this paper, we truly put iterative compilation to the test for the first time by evaluating its effectiveness across a large number of data sets. We therefore compose KDataSets, a data set suite with 1000 data sets for 32 programs, which we release to the public. We characterize the diversity of KDataSets, and subsequently use it to evaluate iterative optimization.We demonstrate that it is possible to derive a robust iterative optimization strategy across data sets: for all 32 programs, we find that there exists at least one combination of compiler optimizations that achieves 86% or more of the best possible speedup across all data sets using Intel's ICC (83% for GNU's GCC). This optimal combination is program-specific and yields speedups up to 1.71 on ICC and 2.23 on GCC over the highest optimization level (-fast and -O3, respectively). This finding makes the task of optimizing programs across data sets much easier than previously anticipated, and it paves the way for the practical and reliable usage of iterative optimization. Finally, we derive pre-shipping and post-shipping optimization strategies for software vendors.

References

[1]

EEMBC: The Embedded Microprocessor Benchmark Consortium. http://www.eembc.org.

[2]

cBench: Collective Benchmarks. http://www.ctuning.org/ cbench.

[3]

PAPI: A Portable Interface to Hardware Performance Counters. http: //icl.cs.utk.edu/papi.

[4]

F. Agakov, E. Bonilla, J. Cavazos, B. Franke, G. Fursin, M. F. P. O'Boyle, J. Thomson, M. Toussaint, and C. K. I. Williams. Using machine learning to focus iterative optimization. In Proceedings of the International Symposium on Code Generation and Optimization (CGO), pages 295--305, March 2006.

Digital Library

[5]

M. Arnold, A. Welc, and V.T.Rajan. Improving virtual machine performance using a cross-run profile repository. In Proceedings of the ACM Conference on Object-Oriented Programming, Systems, Languages and Applications (OOPSLA), pages 297--311, October 2005.

Digital Library

[6]

P. Berube and J. Amaral. Aestimo: a feedback-directed optimization evaluation tool. In Proceedings of the IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS), pages 251--260, March 2006.

[7]

C. Bienia, S. Kumar, J. P. Singh, and K. Li. The PARSEC benchmark suite: characterization and architectural implications. In Proceedings of the 17th International Conference on Parallel Architectures and Compilation Techniques (PACT), pages 72--81, October 2008.

Digital Library

[8]

J. Cavazos, G. Fursin, F. Agakov, E. Bonilla, M. F. P. O'Boyle, and O. Temam. Rapidly selecting good compiler optimizations using performance counters. In Proceedings of the International Symposium on Code Generation and Optimization (CGO), pages 185--197, March 2007.

Digital Library

[9]

K. Cooper, P. Schielke, and D. Subramanian. Optimizing for reduced code space using genetic algorithms. In Proceedings of the Conference on Languages, Compilers, and Tools for Embedded Systems (LCTES), pages 1--9, July 1999.

Digital Library

[10]

K. D. Cooper, A. Grosul, T. J. Harvey, S. Reeves, D. Subramanian, L. Torczon, and T. Waterman. ACME: adaptive compilation made efficient. In Proceedings of the ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems (LCTES), pages 69--77, July 2005.

Digital Library

[11]

L. Eeckhout, H. Vandierendonck, and K. De Bosschere. Quantifying the impact of input data sets on program behavior and its applications. Journal of Instruction-Level Parallelism, 5:1--33, February 2003.

[12]

B. Franke, M. O'Boyle, J. Thomson, and G. Fursin. Probabilistic source-level optimisation of embedded programs. In Proceedings of the ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems (LCTES), pages 78--86, July 2005.

Digital Library

[13]

G. Fursin and O. Temam. Collective optimization. In Proceedings of the International Conference on High Performance Embedded Architectures & Compilers (HiPEAC), pages 34--49, January 2009.

Digital Library

[14]

G. Fursin, J. Cavazos, M. O'Boyle, and O. Temam. Midatasets: Creating the conditions for a more realistic evaluation of iterative optimization. In Proceedings of the International Conference on High Performance Embedded Architectures & Compilers (HiPEAC), pages 245--260, January 2007.

Digital Library

[15]

M. Guthaus, J. Ringenberg, D. Ernst, T. Austin, T. Mudge, and R. Brown. Mibench: A free, commercially representative embedded benchmark suite. In Proceedings of the IEEE Fourth Annual International Workshop on Workload Characterization (WWC), pages 3--14, December 2001.

Digital Library

[16]

M. Haneda, P. Knijnenburg, and H. Wijshoff. On the impact of data input sets on statistical compiler tuning. In Proceedings of the 20th IEEE International Parallel and Distributed Processing Symposium (IPDPS), April 2006.

Digital Library

[17]

K. Hoste and L. Eeckhout. Cole: compiler optimization level exploration. In Proceedings of the Sixth Annual IEEE/ACM International Symposium on Code Generation and Optimization (CGO), pages 165--174, April 2008.

Digital Library

[18]

K. Hoste and L. Eeckhout. Comparing benchmarks using key microarchitecture-independent characteristics. In Proceedings of the IEEE International Symposium on Workload Characterization (IISWC), pages 83--92, October 2006.

[19]

K. Hoste, A. Georges, and L. Eeckhout. Automated just-in-time compiler tuning. In Proceedings of the Eighth Annual IEEE/ACM International Symposium on Code Generation and Optimization (CGO), April 2010.

Digital Library

[20]

W. C. Hsu, H. Chen, P. C. Yew, and D.-Y. Chen. On the predictability of program behavior using different input data sets. In Proceedings of the Sixth Annual Workshop on Interaction between Compilers and Computer Architectures (INTERACT), pages 45--53, February 2002.

Digital Library

[21]

Y. Jiang, E. Z. Zhang, K. Tian, F. Mao, M. Gethers, X. Shen, and Y. Gao. Exploiting statistical correlations for proactive prediction of program behaviors. In Proceedings of the International Symposium on Code Generation and Optimization (CGO), April 2010.

Digital Library

[22]

P. Kulkarni, S. Hines, J. Hiser, D. Whalley, J. Davidson, and D. Jones. Fast searches for effective optimization phase sequences. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pages 171--182, June 2004.

Digital Library

[23]

G. Magklis, M. L. Scott, G. Semeraro, D. H. Albonesi, and S. Dropsho. Profile-based dynamic voltage and frequency scaling for a multiple clock domain microprocessor. In Proceedings of the 30th Annual International Symposium on Computer Architecture (ISCA), pages 14-- 27, June 2003.

Digital Library

[24]

F. Mao, E. Z. Zhang, and X. Shen. Influence of program inputs on the selection of garbage collectors. In Proceedings of the ACM SIGPLAN/ SIGOPS International Conference on Virtual Execution Environments (VEE), pages 91--100, March 2009.

Digital Library

[25]

F. Matteo and S. Johnson. FFTW: An adaptive software architecture for the FFT. In Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), volume 3, pages 1381--1384, May 1998.

[26]

T. Mytkowicz, A. Diwan, M. Hauswirth, and P. F. Sweeney. Producing wrong data without doing anything obviously wrong! In Proceeding of the 14th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), pages 265--276, February 2009.

Digital Library

[27]

Z. Pan and R. Eigenmann. Fast and effective orchestration of compiler optimizations for automatic performance tuning. In Proceedings of the International Symposium on Code Generation and Optimization (CGO), pages 319--332, March 2006.

Digital Library

[28]

K. Sankaranarayanan and K. Skadron. Profile-based adaptation for cache decay. ACM Transactions on Architecture and Code Optimization (TACO), 1:305--322, September 2004.

Digital Library

[29]

M. Stephenson, M. Martin, and U. O'Reilly. Meta optimization: Improving compiler heuristics with machine learning. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pages 77--90, June 2003.

Digital Library

[30]

M. W. Stephenson. Automating the Construction of Compiler Heuristics Using Machine Learning. PhD thesis, MIT, USA, January 2006.

Digital Library

[31]

R. C. Whaley, A. Petitet, and J. Dongarra. Automated empirical optimization of software and the atlas project. In Parallel Computing, March 2001.

[32]

Y. Zhong, X. Shen, and C. Ding. Program locality analysis using reuse distance. Transactions on Programming Languages and Systems (TOPLAS), 31(6):1--39, Aug. 2009.

Digital Library

Cited By

Scravaglieri LPopov MLima Pilla LGuermouche AAumage OSaillard E(2023)Optimizing performance and energy across problem sizes through a search space exploration and machine learningJournal of Parallel and Distributed Computing10.1016/j.jpdc.2023.104720180(104720)Online publication date: Oct-2023
https://doi.org/10.1016/j.jpdc.2023.104720
Hollenbeck CO'Boyle MSteuwer MPolikarpova N(2022)Investigating magic numbers: improving the inlining heuristic in the Glasgow Haskell CompilerProceedings of the 15th ACM SIGPLAN International Haskell Symposium10.1145/3546189.3549918(81-94)Online publication date: 6-Sep-2022
https://dl.acm.org/doi/10.1145/3546189.3549918
Li ZMa PWang HWang STang QNie SWu SDwyer MDamian DZeller A(2022)Unleashing the power of compiler intermediate representation to enhance neural program embeddingsProceedings of the 44th International Conference on Software Engineering10.1145/3510003.3510217(2253-2265)Online publication date: 21-May-2022
https://dl.acm.org/doi/10.1145/3510003.3510217
Show More Cited By

Index Terms

Evaluating iterative optimization across 1000 datasets
1. Software and its engineering
  1. Software notations and tools
    1. Compilers

Recommendations

Deconstructing iterative optimization

Iterative optimization is a popular compiler optimization approach that has been studied extensively over the past decade. In this article, we deconstruct iterative optimization by evaluating whether it works across datasets and by analyzing why it ...
Evaluating iterative optimization across 1000 datasets
PLDI '10

While iterative optimization has become a popular compiler optimization approach, it is based on a premise which has never been truly evaluated: that it is possible to learn the best compiler optimizations across data sets. Up to now, most iterative ...
Iterative optimization for the data center
ASPLOS '12

Iterative optimization is a simple but powerful approach that searches for the best possible combination of compiler optimizations for a given workload. However, each program, if not each data set, potentially favors a different combination. As a result,...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PLDI '10: Proceedings of the 31st ACM SIGPLAN Conference on Programming Language Design and Implementation

June 2010

514 pages

ISBN:9781450300193

DOI:10.1145/1806596

General Chair:
Ben Zorn
Microsoft Research
,
Program Chair:
Alex Aiken
Stanford University

ACM SIGPLAN Notices Volume 45, Issue 6
PLDI '10
June 2010
496 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/1809028
Issue’s Table of Contents

Copyright © 2010 ACM.

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]

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 June 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

PLDI '10

Sponsor:

SIGPLAN

PLDI '10: ACM SIGPLAN Conference on Programming Language Design and Implementation

June 5 - 10, 2010

Ontario, Toronto, Canada

Acceptance Rates

Overall Acceptance Rate 406 of 2,067 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

53
Total Citations
View Citations
759
Total Downloads

Downloads (Last 12 months)40
Downloads (Last 6 weeks)2

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Scravaglieri LPopov MLima Pilla LGuermouche AAumage OSaillard E(2023)Optimizing performance and energy across problem sizes through a search space exploration and machine learningJournal of Parallel and Distributed Computing10.1016/j.jpdc.2023.104720180(104720)Online publication date: Oct-2023
https://doi.org/10.1016/j.jpdc.2023.104720
Hollenbeck CO'Boyle MSteuwer MPolikarpova N(2022)Investigating magic numbers: improving the inlining heuristic in the Glasgow Haskell CompilerProceedings of the 15th ACM SIGPLAN International Haskell Symposium10.1145/3546189.3549918(81-94)Online publication date: 6-Sep-2022
https://dl.acm.org/doi/10.1145/3546189.3549918
Li ZMa PWang HWang STang QNie SWu SDwyer MDamian DZeller A(2022)Unleashing the power of compiler intermediate representation to enhance neural program embeddingsProceedings of the 44th International Conference on Software Engineering10.1145/3510003.3510217(2253-2265)Online publication date: 21-May-2022
https://dl.acm.org/doi/10.1145/3510003.3510217
Cummins CWasti BGuo JCui BAnsel JGomez SJain SLiu JTeytaud OSteiner BTian YLeather HLee J(2022)CompilerGymProceedings of the 20th IEEE/ACM International Symposium on Code Generation and Optimization10.1109/CGO53902.2022.9741258(92-105)Online publication date: 2-Apr-2022
https://dl.acm.org/doi/10.1109/CGO53902.2022.9741258
Liu HLuo JLi YWu Z(2021)Iterative Compilation Optimization Based on Metric Learning and Collaborative FilteringACM Transactions on Architecture and Code Optimization10.1145/348025019:1(1-25)Online publication date: 6-Dec-2021
https://dl.acm.org/doi/10.1145/3480250
Ren XHo MMing JLei YLi LFreund SYahav E(2021)Unleashing the hidden power of compiler optimization on binary code difference: an empirical studyProceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3453483.3454035(142-157)Online publication date: 19-Jun-2021
https://dl.acm.org/doi/10.1145/3453483.3454035
Costa DBezemer CLeitner PAndrzejak A(2021)What's Wrong with My Benchmark Results? Studying Bad Practices in JMH BenchmarksIEEE Transactions on Software Engineering10.1109/TSE.2019.292534547:7(1452-1467)Online publication date: 1-Jul-2021
https://doi.org/10.1109/TSE.2019.2925345
Tagtekin BHoke BSezer MOzturk M(2021)FOGA: Flag Optimization with Genetic Algorithm2021 International Conference on INnovations in Intelligent SysTems and Applications (INISTA)10.1109/INISTA52262.2021.9548573(1-6)Online publication date: 25-Aug-2021
https://doi.org/10.1109/INISTA52262.2021.9548573
Munksgaard PBreddam SHenriksen TGieseke FOancea C(2021)Dataset Sensitive Autotuning of Multi-versioned Code Based on Monotonic PropertiesTrends in Functional Programming10.1007/978-3-030-83978-9_1(3-23)Online publication date: 23-Aug-2021
https://doi.org/10.1007/978-3-030-83978-9_1
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
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