Before RL can tune a compiler, someone has to design the RL
How to represent state, what reward to use, which algorithm: people used to try these one by one. SuperSonic leaves it to search, and against eight existing methods on four compiler tasks it usually comes out ahead.
Compilers are full of choices. How to schedule a Halide image pipeline, how to tile a convolution in TVM, what order to run LLVM’s optimization passes in. These are natural problems for reinforcement learning: make one decision at a time, then see how much faster or smaller the program got.
Anyone who has tried knows the hard part isn’t training. It is all the design before training. How do you represent the program’s state: Word2Vec, CodeBERT, the last few choices? What is the reward? PPO, DQN or Monte Carlo tree search? Which hyperparameters? The best combination differs from task to task, and a new task means starting over.
SuperSonic
SuperSonic, from our CC 2022 paper, is an open-source framework; the code is on GitHub. A developer writes a few lines of Python saying which actions are available and how to measure the result, and SuperSonic searches for the rest:
- The search space holds 23 RL algorithms and 10 program representations and models.
- Choosing a combination is treated as a multi-armed bandit, solved by an RL meta-optimizer: each candidate gets 50 steps and is scored by the area under its reward curve, over 100 rounds.
- The winning architecture’s hyperparameters are tuned with population-based training, and the result is saved and used directly on new programs.
Measuring a program is usually the slowest part, so measurement is split from search. Results go into a database, and measurement can run on many machines at once.
Results
> 11×speedup on some Halide benchmarks
1.74×best speedup on TVM convolution kernels
1.57×best code-size reduction beyond -Oz in LLVM
The four tasks were Halide scheduling, TVM neural-network operators, LLVM pass ordering for code size, and superoptimization with STOKE. We compared eight methods, including OpenTuner, Chameleon and the search strategies in CompilerGym.
On code size, SuperSonic was best on 90% of benchmarks and beat -Oz on all but two; where it wasn’t first, it was within 1% of the best. To match the strongest competitor it needed, on average, 31% to 40% of that competitor’s search time.
A small example: on a function called _Z3p23i it found a version using the popcnt instruction, 18 lines shorter than -O3 and 1.2 times faster.
What the search picked is interesting in itself. For code size it chose PPO. For Halide it chose Monte Carlo tree search, with a hash of the applied schedule as the state. No single RL setup was best everywhere, which is exactly why the choice belongs to a search.
Limitations
Measuring program performance often takes most of the search time. On some Halide tasks evolutionary search beat RL, and the two may be worth combining. When the space is large, 800 combinations for example, a budget of 100 rounds isn’t really enough.
This is one of our earlier papers. It also notes that once a model is deployed and meets programs unlike its training data, it stops working as well. PROM picks up from there.