pvvq.github.io

Combined Elimination

原论文：Fast and effective orchestration of compiler optimizations for automatic performance tuning

编译器优化选项组合Optimization Orchestration指这样一个过程：从编译器提供的一系列优化选项中选出最佳的组合，从而使经过优化的程序执行时间是最快的。以GCC为例，其提供了大约140个优化选项，例如-fauto-inc-dec, -fbranch-count-reg。编译器通常提供将这些包装在-O1 -O2 -O3等优化等级中。但是如果想更精确的控制优化行为，就需要将自行将这些优化选项组合起来。Optimization Orchestration正是做了这么一件事情。

假如我们有140个优化选项，我们有2^140个可能的组合，如果一个程序运行时间为1s，那么如果要将这些组合都测试一遍，需要10^37天的时间。所以我们需要一种更高效的算法：本文介绍3种算法：Batch Elimination(BE), Iterative Elimination(IE) & Combined Elimination(CE)。

Batch Elimination(BE)：优化选项并不一定都会加速程序的运行，这3个算法都是通过选出有负面效果的优化选项来工作的。BE算法首先将所有选项都打开，这时的运行时间我们记为基线时间T_baseline，然后我们依次关闭每一个优化选项(一个时刻只有这一个关闭，其他均为打开)，测试得到一个运行时间T_i, 如果T_i < T_baseline说明此时编译器更好地优化了程序，即这个关闭的优化选项拖累了整体。我们去掉所有有负面效果的选项后就得到BE的结果。时间复杂度：O(n)。

Iterative Elimination(IE)：优化选项的负面效果可能与优化选项之间的影响有关，这是BE完全没有考虑的。IE试图考虑这些影响。我们得到了T_baseline之后，（如同BE一样）依次关闭每一个选项，得到一系列T_i，然后我们选出最小的T_i，即有最大的负面效应的优化选项，我们将这个选项从可选名单中剔除。这样我们保证我们去除的每一个选项都是局部最差的。然后我们重复这个过程，即每次重新测试一遍所有剩下的选项，但只去除有最大负面效应的选项，直到所有选项都具有正面的优化效果。时间复杂度O(N^2)。

Combined Elimination(CE)：CE试图将IE加速。CE的区别在于，在一轮循环中，去除最负面的选项后，我们不直接进入下一轮循环，而是将剩下的负面选项按照负面效应的大小降序排序，然后我们按该顺序依次关闭优化选项（同样仅关闭该单个选项），测试该优化选项在去掉了上一个更负面的优化之后，是否还具有负面效应，如果有则在测试下一个选项之前将它去除。通过此方式测试完所有在该轮循环中本来有负面效应的选项，这时我们再进入下一轮循环。时间复杂度为O(N^2)，但循环次数小于IE。

原论文对上述算法做了更具体严谨的描述。

参考文献

Pan Z, Eigenmann R. Fast and effective orchestration of compiler optimizations for automatic performance tuning[C]//International Symposium on Code Generation and Optimization (CGO’06). IEEE, 2006: 12 pp.-332.

本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。