Speaker Name/Affiliation: Mark Stephenson/MIT

Talk Title: Automating the Construction of Compiler Heuristics Using M

achine Learning

Date/Time: June 23 2006 at 11:00 a.m.

Coffe

e: 10:30 a.m.

Location: ACES 2.402

Host: Kathryn McKinley<

br>
Talk Abstract:
Compiler writers are expected to create effective

and inexpensive
solutions to NP-hard problems such as instruction sched

uling
and register allocation. To make matters worse separate
opti

mization phases have strong interactions and competing
resource constra

ints. Compiler writers deal with system
complexity by dividing the prob

lem into multiple phases
and devising approximate heuristics for each p

hase. However
to achieve satisfactory performance developers are forc

ed
to manually tweak their heuristics with trial-and-error
experime

ntation.

In this talk I present meta optimization a methodology
for automatically constructing high quality compiler heuristics
using

machine learning techniques. I describe machine-learned
heuristics for

three important compiler optimizations: hyperblock
formation register

allocation and loop unrolling. The
machine-learned heuristics outperfo

rm their state-of-the-art
hand crafted counterparts (by as much as 3x i

n some cases).
By automatically collecting data and systematically anal

yzing
them my techniques discover subtle interactions that even
ex

perienced engineers would likely overlook. In addition
to improving per

formance my techniques can significantly
reduce the human effort invol

ved 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 work leads
to collaborative compilation an approach w

hich enables
ordinary users to transparently train compiler heuristics

by running their applications as they normally would. The
collabora

tive system automatically adapts itself to the
applications and systems
in which a community of users is interested.

Speaker Bio:
Mark r

ecently received his Ph.D. from MIT and is interviewing
for a Postdocto

ral Fellow position with Kathryn McKinley. You
can read more about Mark
at http://www.cag.lcs.mit.edu/%7Emstephen/.