AutoPhase: Juggling HLS Phase Orderings in Random Forests with Deep Reinforcement Learning

Ameer Haj Ali

The performance of the code a compiler generates depends on the order in which it applies the optimization passes.
Choosing a good order--often referred to as the {\em phase-ordering} problem--is an NP-hard problem. As a result, existing solutions rely on a variety of heuristics. In this paper, we evaluate a new technique to address the phase-ordering problem: deep reinforcement learning. To this end, we implement a framework that takes a program and finds a sequence of passes that optimize the performance of the generated circuit. Without loss of generality, we instantiate this framework in the context of an LLVM compiler and target high-level synthesis programs. We use random forests to quantify the correlation between the effectiveness of a given pass and the program's features. This helps us reduce the search space by avoiding orderings that are unlikely to improve the performance of a given program. We compare the performance of deep reinforcement learning to state-of-the-art algorithms that address the phase-ordering problem. In our evaluation, we show that reinforcement learning improves circuit performance by 28\% when compared to using the -O3 compiler flag, and it achieves competitive results compared to the state-of-the-art solutions, while requiring fewer samples. More importantly, unlike existing state-of-the-art solutions, our reinforcement learning solution can generalize to more than 12,000 different programs after training on as few as a hundred programs for less than ten minutes.

Published On: March 2, 2020

Presented At/In: Proceedings of Machine Learning and Systems 2020 (MLSys 2020)

Link: https://proceedings.mlsys.org/static/paper_files/mlsys/2020/26-Paper.pdf

Authors: Ameer Haj Ali, Qijing Huang, William Moses, John Xiang, Krste Asanovic, John Wawrzynek, Ion Stoica