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

周文浩 等: SWTuner: 基于机器学习方法的分布式编译调优框架 2535

优任务示例, 同时启用 o 1 和 o 4 选项优化程序后的性能均优于单独使用 o 1 或 o 4 的性能, 即说明 o 1 和 o 4 选项存在
相关性. 在这种情况下, 如果仅考虑单个选项的 Shapley 值, 则可能在筛选阶段遗漏对程序性能有潜在重要影响的
编译选项. Shapley 交互值 [36] 是一个基于 Shapley 值理论的扩展概念. 在机器学习领域, Shapley 交互值能够揭示特
征之间的相互依赖性, 并且衡量特征之间的相互作用对模型预测结果的影响 [34] . 具体的, 对于编译选项组合 x=(o 1 ,
o 2 ,…, o n ), 编译选项 o i 和 o j 的 Shapley 交互值的计算方式如下所示:

∑ |S |!(n−|S |−2)!
ϕ i,j = δ i,j (S ), when i , j, and δ i,j (S ) = f x (S ∪{o i ,o j })− f x (S ∪{o i })− f x (S ∪{o j })+ f x (S ) (8)
2(n−1)!
S ⊆O\{o i ,o j }
公式 (8) 中各符号的含义与 Shapley 值的计算公式基本一致, 这里不做赘述. 对于一个具体的编译调优任务,
如果两个编译选项的 Shapley 交互值很高, 那么这两个选项可能具有很强的相互作用. SHAP 框架针对树形模型同
2
样设计了一种优化算法, 能够将计算所有特征对之间 Shapley 交互值的复杂度降低至 O(TMLD ).
基于 SHAP 的选项重要性分析及筛选流程如算法 1 所示. 算法 1 首先计算验证样本集合 S v 中每个特征 o i 的
平均 Shapley 值 ¯ ϕ i , 并根据 ¯ ϕ i 对原始选项集合 O 中的选项进行排序, 筛选出排名前 50% 的选项构成新的选项集
合 O', 其余选项则使用缺省配置. 这一步通过将原始选项集合 O 中对性能影响较小的选项淘汰, 从而降低了搜索
空间的维度. 然后, 对于验证样本集合 S v , 算法计算在当前模型下, 选项 o i ∈O'相对于其余特征 o j ∈O 的平均 Shapley
¯ ϕ i,j . 虽然 框架针对树形模型实现了高效的求解算法, 但是当验证样本和编译选项数量较多时, 其计
交互值 SHAP
算开销仍无法忽视. 针对上述问题, 本文一方面能够使用 SHAP 框架自带的 sample 函数对验证样本集合 S v 进行
随机采样, 以减少样本个数, 另一方面, 充分挖掘模块之间的潜在并行性, 在使用随机森林模型进行性能预测的同
时执行基于 SHAP 的选项重要性分析和筛选, 以实现 SHAP 计算开销的隐藏, 具体实现方式如图 5 所示.

算法 1. 基于 SHAP 的选项重要性分析及筛选算法.

输入: 验证样本集合 S v ={(x k , t k ): k=1, 2,…, W v }, 筛选前的选项集合 O;
输出: 筛选后的选项集合 O'.

1. FOR o i ∈O DO
2. FOR (x k , t k )∈S v DO
3. Compute ϕ (k)
i
4. END FOR
(∑ )
W v
(k)
5. Compute ¯ ϕ i = |ϕ | /W v
k=1 i
6. END FOR
7. Sort o i ∈O by ¯ ϕ i
8. Reserve the top 50% elements of O as O', other elements use default value
9. FOR o i ∈O' DO
10. FOR o i ∈O and i≠j DO
11. FOR (x k , t k )∈S v DO
12. Compute ϕ (k)
i,j
13. END FOR
14. END FOR
)
(∑
W v
(k)
15. Compute ¯ ϕ i,j = |ϕ | /W v
i,j
k=1
16. Use the quartile method to find potential outliers of ¯ ϕ i,j , forming Φ
{ }
′
′
17. Compute O = O ∪ o j ∈ O| ¯ ϕ i,j ∈ Φ
18. END FOR