Practical exhaustive optimization phase order exploration and evaluation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

Practical exhaustive optimization phase order exploration and evaluation

Full text

Pdf (935 KB)

Source

ACM Transactions on Architecture and Code Optimization (TACO) archive
Volume 6 , Issue 1 (March 2009) table of contents

Article No.: 1

Year of Publication: 2009

ISSN:1544-3566

Authors

Prasad A. Kulkarni	University of Kansas, Lawrence, Kansas
David B. Whalley	Florida State University, Tallahassee, Florida
Gary S. Tyson	Florida State University, Tallahassee, Florida
Jack W. Davidson	University of Virginia, Charlottesville, Virginia

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 191, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1509864.1509865 What is a DOI?

ABSTRACT

Choosing the most appropriate optimization phase ordering has been a long-standing problem in compiler optimizations. Exhaustive evaluation of all possible orderings of optimization phases for each function is generally dismissed as infeasible for production-quality compilers targeting accepted benchmarks. In this article, we show that it is possible to exhaustively evaluate the optimization phase order space for each function in a reasonable amount of time for most of the functions in our benchmark suite. To achieve this goal, we used various techniques to significantly prune the optimization phase order search space so that it can be inexpensively enumerated in most cases and reduce the number of program simulations required to evaluate program performance for each distinct phase ordering. The techniques described are applicable to other compilers in which it is desirable to find the best phase ordering for most functions in a reasonable amount of time. We also describe some interesting properties of the optimization phase order space, which will prove useful for further studies of related problems in compilers.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked 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	Michael Barr , Anthony Massa, Programming Embedded Systems: With C and GNU Development Tools, O'Reilly Media, Inc., 2006
	4	M. E. Benitez , J. W. Davidson, A portable global optimizer and linker, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.329-338, June 20-24, 1988, Atlanta, Georgia, United States
	5	Bodin, F., Kisuki, T., Knijnenburg, P., O'Boyle, M., and Rohou, E. 1998. Iterative compilation in a non-linear optimisation space. In Proceedings of the Workshop on Profile and Feedback Directed Compilation.
	6	Doug Burger , Todd M. Austin, The SimpleScalar tool set, version 2.0, ACM SIGARCH Computer Architecture News, v.25 n.3, p.13-25, June 1997 [doi>10.1145/268806.268810]
	7	John Cavazos , Michael F. P. O'Boyle, Method-specific dynamic compilation using logistic regression, Proceedings of the 21st annual ACM SIGPLAN conference on Object-oriented programming systems, languages, and applications, October 22-26, 2006, Portland, Oregon, USA
	8	Keith D. Cooper , Alexander Grosul , Timothy J. Harvey , Steven Reeves , Devika Subramanian , Linda Torczon , Todd Waterman, ACME: adaptive compilation made efficient, Proceedings of the 2005 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 15-17, 2005, Chicago, Illinois, USA
	9	Keith D. Cooper , Philip J. Schielke , Devika Subramanian, Optimizing for reduced code space using genetic algorithms, Proceedings of the ACM SIGPLAN 1999 workshop on Languages, compilers, and tools for embedded systems, p.1-9, May 05-05, 1999, Atlanta, Georgia, United States
	10	Davidson, J. W. and Whalley, D. B. 1991. A design environment for addressing architecture and compiler interactions. Microproces. Microsyst. 15, 9, 459--472.
	11	Engblom, J. 2007. Using simulation tools for embedded systems software development. http://www.embedded.com/columns/technicalinsights/199501500?_requestid=111267.
	12	M. R. Guthaus , J. S. Ringenberg , D. Ernst , T. M. Austin , T. Mudge , R. B. Brown, MiBench: A free, commercially representative embedded benchmark suite, Proceedings of the Workload Characterization, 2001. WWC-4. 2001 IEEE International Workshop, p.3-14, December 02-02, 2001 [doi>10.1109/WWC.2001.15]
	13	Hewlett-Packard. 2000. Parallel programming guide for hp-ux systems. http://docs.hp.com/en/B3909-90003/B3909-90003.pdf (page 74).
	14	Kenneth Hoste , Lieven Ee khout, Cole: compiler optimization level exploration, Proceedings of the sixth annual IEEE/ACM international symposium on Code generation and optimization, April 05-09, 2008, Boston, MA, USA [doi>10.1145/1356058.1356080]
	15	T. Kisuki , P. M. W. Knijnenburg , M. F. P. O'Boyle, Combined Selection of Tile Sizes and Unroll Factors Using Iterative Compilation, Proceedings of the 2000 International Conference on Parallel Architectures and Compilation Techniques, p.237, October 15-19, 2000
	16	Toru Kisuki , Peter M. W. Knijnenburg , Michael F. P. O'Boyle , François Bodin , Harry A. G. Wijshoff, A Feasibility Study in Iterative Compilation, Proceedings of the Second International Symposium on High Performance Computing, p.121-132, May 26-28, 1999
	17	Knijnenburg, P., Kisuki, T., Gallivan, K., and O'Boyle, M. 2000. The effect of cache models on iterative compilation for combined tiling and unrolling. In Proceedings of 3rd ACM Workshop on Feedback-Directed and Dynamic Optimization. ACM, New York, 31--40.
	18	Prasad Kulkarni , Stephen Hines , Jason Hiser , David Whalley , Jack Davidson , Douglas Jones, Fast searches for effective optimization phase sequences, Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, June 09-11, 2004, Washington DC, USA
	19	Prasad A. Kulkarni , David B. Whalley , Gary S. Tyson , Jack W. Davidson, Exhaustive Optimization Phase Order Space Exploration, Proceedings of the International Symposium on Code Generation and Optimization, p.306-318, March 26-29, 2006 [doi>10.1109/CGO.2006.15]
	20	Prasad A. Kulkarni , David B. Whalley , Gary S. Tyson , Jack W. Davidson, In search of near-optimal optimization phase orderings, Proceedings of the 2006 ACM SIGPLAN/SIGBED conference on Language, compilers, and tool support for embedded systems, June 14-16, 2006, Ottawa, Ontario, Canada
	21	Prasad A. Kulkarni , David B. Whalley , Gary S. Tyson, Evaluating Heuristic Optimization Phase Order Search Algorithms, Proceedings of the International Symposium on Code Generation and Optimization, p.157-169, March 11-14, 2007 [doi>10.1109/CGO.2007.9]
	22	Prasad Kulkarni , Wankang Zhao , Hwashin Moon , Kyunghwan Cho , David Whalley , Jack Davidson , Mark Bailey , Yunheung Paek , Kyle Gallivan, Finding effective optimization phase sequences, Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool for embedded systems, June 11-13, 2003, San Diego, California, USA
	23	Prasad A. Kulkarni , Stephen R. Hines , David B. Whalley , Jason D. Hiser , Jack W. Davidson , Douglas L. Jones, Fast and efficient searches for effective optimization-phase sequences, ACM Transactions on Architecture and Code Optimization (TACO), v.2 n.2, p.165-198, June 2005 [doi>10.1145/1071604.1071607]
	24	Peterson, W. and Brown, D. 1961. Cyclic codes for error detection. In Proceedings of the Institute of Radio Engineers. 49, 228--235.
	25	Redhat. 2004. Gnupro 04r1 tools for embedded systems development. http://www.redhat.com/f/pdf/GNUPro-04r1-Embedded-AnnouncementLetter.pdf.
	26	Sid-Ahmed-Ali Touati , Denis Barthou, On the decidability of phase ordering problem in optimizing compilation, Proceedings of the 3rd conference on Computing frontiers, May 03-05, 2006, Ischia, Italy [doi>10.1145/1128022.1128042]
	27	Spyridon Triantafyllis , Manish Vachharajani , Neil Vachharajani , David I. August, Compiler optimization-space exploration, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
	28	Steven R. Vegdahl, Phase coupling and constant generation in an optimizing microcode compiler, Proceedings of the 15th annual workshop on Microprogramming, p.125-133, October 05-07, 1982, Palo Alto, California, United States
	29	Virtutech. 2008. Virtualized software development white paper. http://www.virtutech.com/files/whitepapers/wp_simics.pdf.
	30	Tim A. Wagner , Vance Maverick , Susan L. Graham , Michael A. Harrison, Accurate static estimators for program optimization, ACM SIGPLAN Notices, v.29 n.6, p.85-96, June 1994
	31	Weisstein, E. W. 2006. Correlation coefficient. from MathWorld—A Wolfram Web Resource. http://mathworld.wolfram.com/CorrelationCoefficient.html.
	32	D. Whitfield , M. L. Soffa, An approach to ordering optimizing transformations, Proceedings of the second ACM SIGPLAN symposium on Principles & practice of parallel programming, p.137-146, March 14-16, 1990, Seattle, Washington, United States
	33	Deborah L. Whitfield , Mary Lou Soffa, An approach for exploring code improving transformations, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.6, p.1053-1084, Nov. 1997 [doi>10.1145/267959.267960]
	34	Min Zhao , Bruce Childers , Mary Lou Soffa, Predicting the impact of optimizations for embedded systems, Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool for embedded systems, June 11-13, 2003, San Diego, California, USA
	35	Min Zhao , Bruce R. Childers , Mary Lou Soffa, A Model-Based Framework: An Approach for Profit-Driven Optimization, Proceedings of the international symposium on Code generation and optimization, p.317-327, March 20-23, 2005 [doi>10.1109/CGO.2005.2]