- 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 Amarasinghe
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}",
