Meta optimization

Publisher Website
Google Scholar
Abstract
Compiler writers have crafted many heuristics over the years to approximately solve NP-hard problems ecien tly. Find- ing a heuristic that performs well on a broad range of ap- plications is a tedious and dicult process. This paper in- troduces Meta Optimization, a methodology for automat- ically ne-tuning compiler heuristics. Meta Optimization uses machine-learning techniques to automatically search the space of compiler heuristics. Our techniques reduce com- piler design complexity by relieving compiler writers of the tedium of heuristic tuning. Our machine-learning system uses an evolutionary algorithm to automatically nd eec- tive compiler heuristics. We present promising experimental results. In one mode of operation Meta Optimization creates application-specic heuristics which often result in impres- sive speedups. For hyperblock formation, one optimization we present in this paper, we obtain an average speedup of 23% (up to 73%) for the applications in our suite. Further- more, by evolving a compiler's heuristic over several bench- marks, we can create eectiv e, general-purpose heuristics. The best general-purpose heuristic our system found for hy- perblock formation improved performance by an average of 25% on our training set, and 9% on a completely unrelated test set. We demonstrate the ecacy of our techniques on three dieren t optimizations in this paper: hyperblock for- mation, register allocation, and data prefetching.

This publication has 8 references indexed in Scilit: