-By Hugh Leather - University of Edinburgh Edinburgh,
Chris Cummins - Facebook AI Research
Abstract
Writing optimising compilers is difficult. The range of programs that may be presented to the compiler is huge and the systems on which they run are complex, heterogeneous, non-deterministic, and constantly changing. The space of possible optimisations is also vast, making it very hard for compiler writers to design heuristics that take all of these considerations into account. As a result, many compiler optimisations are out of date or poorly tuned.
A retrospective of machine learning in compiler optimisation from its earliest inception, through some of the works that set themselves apart, to today’s deep learning, finishing with our vision of the field’s future.
Developers have known since they first used optimising compilers that the compiler does not always choose the best options. They would try different compiler command lines, either in an ad hoc fashion or more rigorously by searching. Even simple techniques, like exhaustively searching for the best tiling factors for matrix multiplication, could yield considerable benefits.
The idea is straightforward: define a space of optimisation strategies, such as unrolling factors, tilings, or complete command lines, then use a search technique to find the best one. The search evaluates each strategy by compiling the program and running it with representative inputs enough times to estimate the measure of interest (typically performance). This process is shown in Figure 1. Unlike many compiler heuristics, iterative compilation is blind to the platform, easily adapts to changes, and is based on evidence, not belief. The potential gains are huge, found speedups of up to 2.23× over many data sets.
There have been many iterative compilation works. Each targets some different heuristic or applies a different search technique. The use of genetic algorithms is common, but random search and greedy approaches feature also. Optimisation targets include phase ordering, code size, compiler flags, and many others. Libraries, such as ATLAS and SPIRAL, auto tune on installation. PetaBricks and LIFT are among some of the works that expand the search space to include algorithmic choices. The high cost of iterative compilation has been addressed by statistical techniques.
Machine Learning - Supervised
Although iterative compilation can improve program performance to a remarkable degree, the search, which must be repeated for every new program and might require thousands of compilations and executions, is so timeconsuming as to be impractical for all but a few specialised use cases. Early pioneers began to look to supervised machine learning to get the same benefits as iterative compilation but in a single compilation.
Feature vectors are designed by compiler experts who decide what information will be most helpful when deciding the best value for the target heuristic.
The predictive model replaces a human constructed heuristic. Features are calculated for a new program and the predicts the best heuristic value.
The examples previously cited learn the heuristic directly. Often this is predicting some best category, such as loop unroll factor or whether to inline a function. Not all problems fit so neatly, and when it is not clear how to represent the heuristic values as a category then they instead require more careful consideration for how to fit them into a machine learning paradigm.
Genetic programming was used to search for features. A grammar described a programming language of features. A genetic program evolved individuals from the feature language, searching to improve the accuracy of a machine learning model for the target heuristic.
Deep Learning
The advent of deep learning has begun to pervade every discipline and compilers are no exception. Deep learning means using very large neural networks with many, or ‘deep’, layers. Previously, these large networks were infeasible to train, but processing power is now up to the task. What has changed by these advances is that large, deep neural nets can scale up to much larger training data sizes and produce much more detailed models that can learn functions with an ease that might previously have seemed magical. But, the game-changer is that whereas before the choice of features was so crucial, it is now possible to feed in raw data and the deep learner will make sense of it.
They made use of an existing technology that had had great success in natural language processing called long short term memory networks (LSTM). These nets are able to process streams of inputs and remember events from arbitrarily far in the past. This enables them to somewhat understand the structure of the program, such as whether a variable has been declared in the past. The results improved over prior, hand-built features.
Reinforcement learning - Future
Recently, reinforcement learning techniques have begun to make inroads in compiler optimization. Reinforcement learning concerns the process of iterative decision making of an agent within an environment. The environment provides a state, a set of actions, and a reward signal. The goal of an agent is to select the sequence of actions, one at a time, that will maximise cumulative reward.
vision: A reinforcement learning system to control all aspects of the compiler.
Conclusion:
Over last fifteen years3 i field . In that time we have seen it move from a niche academic discipline, struggling for acceptance, to one which industry is now scrambling to adopt. So, where is this field going? What do we need to do in the coming years? Optimisation is hard and it is only going to get harder still. We need to remove humans from all the heuristics in the compiler, and this will require a coordinated, inter-disciplinary effort. We need compiler writers to build modular compilers that support iterative compilation and machine learning from the ground up. We need machine learning researchers to invent models that are suited to the recurrent, flow-based nature of programs. And we need efficient learning strategies that can cope with the huge number of choices, distant rewards, and slow evaluations that apply to compiler optimisation.
Comments