Practical Aggregation of Semantical Program Properties for Machine Learning Based Compilation [abstract] (ACM DL)
Mircea Namolaru, Grigori Fursin, Albert Cohen, Ari Freund, and Ayal Zaks
Proceedings of the International Conference on Compilers and Synthesis for Embedded Systems (CASES), October 2010.
Iterative search combined with machine learning is a promising approach
to design optimizing compilers harnessing the complexity
of modern computing systems. While traversing a program optimization
space, we collect characteristic feature vectors of the
program, and use them to discover correlations across programs,
target architectures, data sets, and performance. Predictive models
can be derived from such correlations, effectively hiding the
time-consuming feedback-directed optimization process from the
application programmer.
One key task of this approach, naturally assigned to compiler experts,
is to design relevant features and implement scalable feature
extractors, including statistical models that filter the most relevant
information from millions of lines of code. This new task turns out
to be a very challenging and tedious one from a compiler construction
perspective. So far, only a limited set of ad-hoc, largely syntactical
features have been devised. Yet machine learning is only
able to discover correlations from information it is fed with: it is
critical to select topical program features for a given optimization
problem in order for this approach to succeed.
We propose a general method for systematically generating numerical
features from a program. This method puts no restrictions
on how to logically and algebraically aggregate semantical properties
into numerical features. We illustrate our method on the
difficult problem of selecting the best possible combination of 88
available optimizations in GCC. We achieve 74% of the potential
speedup obtained through iterative compilation on a wide range of
benchmarks and four different general-purpose and embedded architectures.
Our work is particularly relevant to embedded system
designers willing to quickly adapt the optimization heuristics
of a mainstream compiler to their custom ISA, microarchitecture,
benchmark suite and workload. Our method has been integrated
with the publicly released MILEPOST GCC [14].