Searching for Priority Functions
Abstract Compiler writers have crafted many heuristics over the years to approximately solve NP-hard problems efficiently.  Finding a heuristic that performs well on a broad range of applications is a tedious and difficult process.  In this work we use genetic programming (GP) to automatically search the space of compiler heuristics. Our techniques reduce compiler design complexity by relieving compiler writers of the tedium of heuristic tuning.  Our system uses GP, an evolutionary algorithm, to automatically find effective compiler heuristics. We present promising experimental results.  In one mode of operation Meta Optimization creates application-specific heuristics which often result in impressive speedups.  For hyperblock formation, one optimization we researched, we obtain an average speedup of 23% (up to 73%) for the applications in our suite. Furthermore, by evolving a compiler's heuristic over several benchmarks, we can create effective, general-purpose heuristics.  The best general-purpose heuristic our system found for hyperblock formation improved performance by an average of 25% on our training set, and 9% on a completely unrelated test set. We demonstrate the efficacy of our techniques on three different optimizations in this paper: hyperblock formation, register allocation, and data prefetching. Papers and Presentations M. Stephenson, M. Martin, U. O'Reilly, and S. Amarasinghe. Meta Optimization: Improving Compiler Heuristics with Machine Learning. In Proceedings of the SIGPLAN '03 Conference on Programming Language Design and Implementation, San Diego, CA, June 2003. (ps, pdf, ppt). M. Stephenson, U. O'Reilly, M. Martin, and S. Amarasinghe. Genetic Programming Applied to Compiler Heuristic Optimization. In Proceedings of the 6th European Conference on Genetic Programming, Essex, UK, April 14, 2003. (ps, pdf, ppt). M. Stephenson, U. O'Reilly, M. Martin, and S. Amarasinghe, Presentation of Meta Optimization.  Presented at the Boston Area Architecture Workshop.  January 30, 2003. (ppt). M. Stephenson, S. Amarasinghe, M. Martin, and U. O'Reilly. Meta Optimization: Improving Compiler Heuristics with Machine Learning. MIT-TM-634.  November 2002. (ps, pdf). Software The GP toolkit that we used to perform this research can be downloaded here. Latest release: 5/05/2004 User's Guide Previous release: 12/01/2003 Preliminary release: 6/9/2003 People Mark Stephenson Una-May O'Reilly Martin C. Martin Saman Amarasinghe Related Papers and Links D. Puppin, M. Stephenson, S. Amarasinghe, U. O'Reilly, M. Martin. Adapting Convergent Scheduling Using Machine Learning. In Proceedings of the 16th International Workshop on Languages and Compilers for Parallel Computing, College Station, TX, October 2003. (pdf, ppt). D. Puppin, M. Stephenson, W. Lee, S. Amarasinghe. Convergent Scheduling. In Journal of Instruction-Level Parallelism. Volume 6, September 2004. (pdf). Keith Cooper and his students use genetic algorithms to find effective compiler phase orders.  Check out their work. Eliot Moss and John Cavazos at the University of Massachusetts are working on applying supervised learning to compilation. Fast Searches for Effective Optimization Phase Sequences. Prasad Kulkarni, Stephen Hines (Florida State University), Jason Hiser (University of Virginia), David Whalley (Florida State University), Jack Davidson (University of Virginia), and Douglas Jones (University of Illinois), PLDI 2004, Washington D.C., USA.
Last updated by Mark Stephenson on March 25, 2005