pwq

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 国际许可协议进行许可。