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

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

代的元搜索空间构建.
上述 3 个模块相互配合, 形成了一个完整且高效的自动化编译调优流程. 下面, 本文分别对每个模块中采用的
关键技术进行详细介绍.
2.1 基于 AUC-Bandit 的分布式元搜索
为了动态地分配计算资源给不同的搜索技术, 同时平衡探索与利用以避免陷入局部最优, SWTuner 将搜索过
程抽象为赌博机 (bandit) 问题, 并采用曲线下面积指导具体搜索技术的选择. AUC-Bandit 元搜索策略的核心在于
使用 AUC 值来评估每个搜索技术的表现, 并基于评估结果决定哪些技术应该获得更多的测试机会 [27] . 具体而言,
AUC t 值反映了搜索技术 t 在滑动窗口中产生新的全局最佳结果的能力, 其计算方式如下所示:

∑
|V t |
2 iV t [i]
AUC t = i=1 (1)
|V t |(|V t |+1)
其中, V t 是一个 Bool 类型的数组, 其元素 V t [i] 用于记录滑动窗口中第 i 次使用搜索技术 t 时是否获得全局最优结
果 (是为 1, 否则为 0). 滑动窗口通过限制历史数据的观察范围来动态调整搜索技术的资源分配, 窗口长度在
∑ |V t |
SWTuner 中通过参数 window 进行配置. iV t [i] 表示 V t 中各元素的加权和, 其权重是该技术在滑动窗口中的
i=1
位置 (从 1 开始计数).
为了更好地理解 AUC 的含义, 本文将其直观地表示为图 2 所示的笛卡尔坐标系中的红色线条. 其中, 横坐标
∑
|V t |
表示技术 t 在滑动窗口中的使用次数, 纵坐标表示 V t 中每个元素的加权值, 而 iV t [i] 则等价于曲线与横轴所
i=1
包围区域的面积. 如果技术 t 在第 i 次使用中产生了新的全局最佳结果, 则曲线在 i 处向上跳跃, 否则保持不变. 通
过将 AUC 值归一化到 [0, 1] 之间, 元搜索策略能够直接比较不同搜索技术之间的优劣程度.

5 5

4 4
AUC 0 =0.67 AUC 1 =0.60
iV t [i] 3 iV t [i] 3

2 2

1 1
0 0
1 2 3 4 5 i 1 2 3 4 5 i
(a) 搜索策略P 0 (b) 搜索策略 P 1
图 2 曲线下面积的图形化表示

在 SWTuner 元搜索驱动的初始化阶段, 所有搜索技术均被赋予相同的信用值. 而随着搜索过程的推进, 搜索
技术被选择的概率将与它的得分成正比. 技术 t 的得分 Score t 的计算方式如下所示:

(2)
Score t = AUC t + EXP t
公式 (2) 中除了 AUC t 外, 还包括一个探索项:

√
2lnH
EXP t = C (3)
|V t |
其中, C 是控制探索与平衡的常数, H 是滑动窗口的长度. 探索项 EXP t 的存在是为了确保即使某种搜索技术当前
表现不佳, 也会有一定的概率被再次尝试, 以避免陷入局部最优.
SWTuner 的 AUC-Bandit 元搜索驱动支持多种不同的搜索方法, 包括均匀贪婪变异 (uniform greedy mutation,
UGM)、正态贪婪变异 (normal greedy mutation, NGM)、差分进化变异 (differential evolution mutation, DEM) 以及
随机单纯形法 (random Nelder-Mead, RNM) 等. 其中, 均匀贪婪变异通过在参数空间中均匀选择变异方向, 结合贪