Meta optimization: improving compiler heuristics with machine learning

Created by W.Langdon from gp-bibliography.bib Revision:1.2031

@InProceedings{StephensonAMO03,
  author =       "Mark Stephenson and Saman Amarasinghe and 
                 Martin Martin and Una-May O'Reilly",
  title =        "Meta optimization: improving compiler heuristics with
                 machine learning",
  booktitle =    "Proceedings of the ACM SIGPLAN 2003 conference on
                 Programming Language Design and Implementation (PLDI
                 '03)",
  year =         "2003",
  pages =        "77--90",
  publisher =    "ACM",
  address =      "San Diego, California, USA",
  publisher_address = "New York, NY, USA",
  keywords =     "genetic algorithms, genetic programming, Programming
                 Techniques, Automatic Programming, Software
                 Engineering, Design Tools and Techniques, Artificial
                 Intelligence, Learning",
  bibsource =    "http://www.sebase.org/sbse/publications/repository.html",
  ISBN =         "1-58113-662-5",
  doi =          "doi:10.1145/781131.781141",
  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. 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 23percent (up to 73percent) 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 25percent on our training set, and 9percent 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.",
  notes =        "Also known as \cite{781141}",
}

Genetic Programming entries for Mark Stephenson Saman Amarasinghe Martin C Martin Una-May O'Reilly