用强化学习调编译器,先得决定怎么用强化学习
状态怎么表示、奖励怎么给、用哪个算法,以前要人一个个试。SuperSonic 把这件事交给搜索,在四类编译优化任务上和 8 种已有方法比,大多数时候都更好。
编译器里有很多要做选择的地方:Halide 的图像流水线怎么调度,TVM 里一个卷积怎么切块,LLVM 的优化 pass 按什么顺序跑。这些问题天生适合强化学习:一步一步做决定,最后看程序快了多少、小了多少。
真动手的人会发现,难的不是训练,是训练之前那一堆设计。程序的状态用什么表示,Word2Vec、CodeBERT,还是最近几次的选择?奖励怎么算?用 PPO、DQN 还是蒙特卡洛树搜索?超参数怎么定?每个任务的最佳组合都不一样,换个任务就得从头试。
SuperSonic
SuperSonic 是我们发表在 CC 2022 的开源框架,代码在 GitHub。开发者用几行 Python 写清楚能做哪些动作、怎么衡量好坏,剩下的由它来搜:
- 搜索空间里有 23 个强化学习算法,10 种程序表示和模型。
- 挑组合被当成一个多臂老虎机问题,由一个强化学习的「元优化器」来选:每个候选先试 50 步,按奖励曲线下的面积打分,一共 100 轮。
- 选出来的结构再用基于种群的训练调超参数,存下来,直接用在新程序上。
衡量程序的好坏通常最花时间,所以测量和搜索是拆开的,结果写进一个数据库,可以在多台机器上并行跑。
结果
> 11×部分 Halide 基准上的加速
1.74×TVM 卷积核,最高加速
1.57×LLVM 代码体积比 -Oz 再小,最高
四类任务分别是 Halide 调度、TVM 神经网络算子、LLVM pass 排序(优化代码体积)和用 STOKE 做超优化,一共和 8 种方法比,包括 OpenTuner、Chameleon 和 CompilerGym 里的搜索策略。
代码体积这一项,SuperSonic 在 90% 的基准上最好,除了两个程序,都比 -Oz 更小;没拿第一的那些,和最好的结果也只差 1% 以内。要追上最强的对手,它平均只需要对方 31% 到 40% 的搜索时间。
有个小例子:在一个叫 _Z3p23i 的函数上,它找到了用 popcnt 指令的写法,代码比 -O3 少 18 行,快 1.2 倍。
搜出来的配置也很有意思。代码体积任务它选了 PPO;Halide 调度选的却是蒙特卡洛树搜索,状态用的是已应用调度的哈希值。没有哪一种强化学习配置在所有任务上都最好,这正是把选择交给搜索的理由。
局限
测量程序性能往往占掉大部分搜索时间。在一些 Halide 任务上,演化搜索比强化学习更好,两者也许应该结合。搜索空间很大时,比如 800 种组合,100 轮的预算就不太够。
这是我们比较早的一篇工作。论文里也提到,模型一旦部署,遇到的程序和训练时不一样,效果就会变。后来的 PROM,就是从这个问题接着做下去的。