Automating the Construction of Compiler Heuristics Using Machine Learning

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

@PhdThesis{Stephenson:thesis,
  author =       "Mark W. Stephenson",
  title =        "Automating the Construction of Compiler Heuristics
                 Using Machine Learning",
  school =       "Department of Electrical Engineering and Computer
                 Science, Massachusetts Institute of Technology",
  year =         "2006",
  type =         "Doctor of Philosophy of Science in Computer Science
                 and Engineering",
  address =      "Cambridge, MA, USA",
  month =        may # " 23",
  keywords =     "genetic algorithms, genetic programming, SBSE, SVN,
                 regularisation, LOOCV, Priority Functions",
  URL =          "http://www.cag.csail.mit.edu/~mstephen/stephenson_phdthesis.pdf",
  size =         "162 pages",
  abstract =     "Compiler writers are expected to create effective and
                 inexpensive solutions to NP-hard problems such as
                 instruction scheduling and register allocation. To make
                 matters worse, separate optimisation phases have strong
                 interactions and competing resource constraints.
                 Compiler writers deal with system complexity by
                 dividing the problem into multiple phases and devising
                 approximate heuristics for each phase. However, to
                 achieve satisfactory performance, developers are forced
                 to manually tweak their heuristics with trial-and-error
                 experimentation.

                 In this dissertation I present meta optimization, a
                 methodology for automatically constructing high quality
                 compiler heuristics using machine learning techniques.
                 This thesis describes machine-learned heuristics for
                 three important compiler optimisations: hyperblock
                 formation, register allocation, and loop unrolling. The
                 machine-learned heuristics outperform (by as much as 3x
                 in some cases) their state-of-the-art hand-crafted
                 counterparts. By automatically collecting data and
                 systematically analysing them, my techniques discover
                 subtle interactions that even experienced engineers
                 would likely overlook. In addition to improving
                 performance, my techniques can significantly reduce the
                 human effort involved in compiler design. Machine
                 learning algorithms can design critical portions of
                 compiler heuristics, thereby freeing the human designer
                 to focus on compiler correctness.

                 The progression of experiments I conduct in this thesis
                 leads to collaborative compilation, an approach which
                 enables ordinary users to transparently train compiler
                 heuristics by running their applications as they
                 normally would. The collaborative system automatically
                 adapts itself to the applications in which a community
                 of users is interested.",
  notes =        "Thesis Supervisor: Saman Amarasing

                 p98 'policy search with genetic programming can find
                 effective priority functions with little human
                 intervention'

                 p150 My thesis describes a simple and effective
                 approach called policy search, that automatically
                 creates excellent priority functions. My genetic
                 programming-based implementation found better priority
                 functions -- sometimes much better -- than the best
                 human-constructed priority functions, and with
                 virtually no human intervention.

                 Also known as \cite{stephenson:phd-thesis:2006}",
}

Genetic Programming entries for Mark Stephenson