Meta optimization
Mark Stephenson, Saman P. Amarasinghe, Martín Martín et al. · ACM SIGPLAN Notices · 2003
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. This paper introduces Meta Optimization, a methodology for automatically fine-tuning compiler heuristics. Meta Optimization uses machine-learning techniques 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 machine-learning system uses 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 present in this paper, 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.
Cited by 248 works. doi:10.1145/780822.781141
Authors
References
- Genetic Programming: On the Programming of Computers by Means of Natural Selection
- MediaBench: A Tool for Evaluating and Synthesizing Multimedia and Communications Systems
- Genetic programming - An Introduction: On the Automatic Evolution of Computer Programs and Its Applications
- Effective compiler support for predicated execution using the hyperblock
- Iterative modulo scheduling
- The priority-based coloring approach to register allocation
- Efficient instruction scheduling for a pipelined architecture
- Tolerating latency through software-controlled data prefetching
- Efficient instruction scheduling for a pipelined architecture
- Optimizing for reduced code space using genetic algorithms