Page 215 - 《软件学报》2026年第6期

2534 软件学报 2026 年第 37 卷第 6 期

∑ ∑
W v 2 W v 2
其中, (t i − ˆ t i ) 为所有样本实测值与预测值之间的残差平方和 (residual sum of squares, RSS), (t i − ¯ t) 为所
i=1 i=1
2
有样本的总离差平方和 (total sum of squares, TSS). 当 R 的值接近 1 时, 表示预测值与实测值非常接近, 模型拟合
效果很好. 当 R 的值接近 0 时, 表示模型的解释能力较弱, 无法准确表示编译选项组合与程序性能之间的复杂非
2
线性关系.
当模型的预测精度达到一定水平后, 就可以在后续的搜索过程中对程序性能进行预测, 从而替代实际执行以
降低功耗开销. 由于模型的泛化程度有限, 而程序的执行也存在一定的动态性, 因此预测的结果可能存在误差, 从
而导致错过最优解的情况出现. SWTuner 通过执行阈值 (execution threshold, ET) 对模型的预测结果进行筛选, 并
且对具有优化潜力的选项组合进行实际执行验证. 执行阈值的定义如下所示:

∑
t i
ET = (x i ,t i )∈S t ∪S v (6)
2
(W t +W v )·max(R ,0.1)
对于编译调优任务, 假设每个编译选项对程序性能的影响均为独立随机事件, 并且使用完全随机的搜索策略,
根据中心极限定理 [32] , 性能模型的预测结果应符合正态分布. 由于正态分布属于对称分布, 其概率密度曲线下均
值左右两侧的面积相等, 假设程序在单位执行时间内的功耗为固定值, 则在理想情况下, 使用 ET 筛选后的功耗节
2
省比例约为 50%. 考虑到模型预测结果的可信度与训练过程的质量密切相关, 本文将 R 引入 ET 的计算过程. 在
2
2
一些极端情况下, 模型过拟合或者数据中存在异常值可能导致 R 的结果为负值, 因此公式 (6) 使用 max(R , 0.1)
2
作为分母. 当模型的预测结果较为准确时, ET 值接近历史实测结果的平均值, 而当模型的解释能力减弱时, R 值减
小, 从而导致预测执行逐步退化为实际执行.
2.3 基于 SHAP 的选项分析及筛选
编程语言和编译技术的不断发展推动了编译器种类及编译选项数量的迅速增长. 可配置编译选项数量的增多导
致所有可能的选项组合数量以指数形式增长. 因此, 尝试通过遍历整个搜索空间来寻找最优配置的方法, 在实际应用
中往往是不可行的. 目前主流的编译调优框架通常采用启发式或近似算法来解决这一问题, 以便在合理的时间内找
到接近最优解的解决方案. 然而, 这些方法仍然需要面对庞大的搜索空间, 在优化质量和搜索效率之间做出权衡. 如
何在保证优化效果的前提下探索更加高效和适应性强的搜索空间优化策略, 是当前编译调优领域的重要研究方向.
不同的编译选项对程序性能的影响存在显著差异. 例如, 某些选项能够大幅提升程序的运行速度, 但可能会增
加二进制文件的大小; 而其他选项可能减少内存使用量, 但以牺牲执行效率为代价; 还有一些编译选项则主要用于
调试, 对程序性能几乎不产生直接影响. 上述差异性提示我们在选择编译选项进行优化时, 必须仔细考量应用程序
的具体需求以及目标硬件的特性, 并将重点放在那些对调优目标有显著影响的选项上.
Shapley 值 [33] 是合作博弈论中的重要概念, 用于公平地计算每个玩家对联盟总收益的贡献. 在可解释机器学习
领域, 通过计算 Shapley 值, 可以了解每个特征对模型预测值的贡献程度, 从而帮助理解模型的行为 [34] . SWTuner
使用 Shapley 值来评估每个编译选项对程序性能的影响程度. 具体地, 对于编译选项组合 x=(o 1 , o 2 ,…, o n ), 编译选
项 o i 的 Shapley 值的计算方式如下所示:
∑ |S |!(n−|S |−1)!
ϕ i = ( f x (S ∪{o i })− f x (S )) (7)
n!
S ⊆O\{o i }
其中, O={o 1 , o 2 ,…, o n }是 x 中包含的所有编译选项的集合, n 为选项的个数, S⊆O\{o i }为不包含 o i 的选项集合的子
集, f x (S) 为随机森林模型对选项子集 S 的预测. |S|!(n–|S|–1)!/n!为子集 S 的权重, 其中分母 n!表示 n 个选项在任意
排序情况下的组合数量, 分子|S|!(n–|S|–1)!表示在确定子集 S 后, n 个选项在特定排序的情况下的组合数量.
尽管 Shapley 值具有令人信服的理论优势, 但是其精确计算过程具有指数复杂度. SHAP 框架 [35] 针对树形模
2
M
型推导了一种优化算法, 将计算精确 Shapley 值的复杂度从 O(TL2 ) 降低至 O(TLD ). 其中, T 是决策树的数量, L
是所有树中的最大节点数量, M 是特征数量, D 是所有树的最大深度. 这种复杂度的指数级降低使得应用 Shapley
值评估编译选项的重要程度成为可能.
在编译优化过程中, 多个编译选项可能同时作用于一个优化遍. 例如, 对于第 2.2 节中包含 5 个选项的编译调