浅读 GroupTuner: Efficient Group-Aware Compiler Auto-tuning
简体中文 (current) | English
前言
笔者作为CSIS专业的学生，FYP项目为Compiler Flag Optimisation using Machine Learning, 是个机器学习与计算机科学的交叉领域。根据基本的时间线，会在秋季学期做大量的准备工作，包括阅读论文，知识积累，开题报告等等。
在此记录整个FYP的一些进展，供自己将来参考，也能对知识进行一些总结提高。
目前Read List里有十篇论文，笔者决定先从这篇开始，也是导师指定的一篇。
Background
基于机器学习的编译器标志优化，并不是一个新兴的领域。2018年的论文A Survey on Compiler Autotuning using Machine Learning指出了过往编译器优化的一些方法，从那时到现在，已经提出诸多寻找最佳参数组合的方法，例如贝叶斯分类器，更现代的还有基于LLM的优化。这些方法无一例外的是想从数百个flags里找到一些最小化执行时间的组合，因此也有共同的缺点。想要全部遍历可能的参数组，所用的时间会超过宇宙中原子的总数，即它们的可迭代次数是有限的。由此引发的问题是所有得到的数据都是稀疏的，充满噪声，导致最终陷入局部最优解。
这篇论文提出的方法是，将编译器中所有功能分为多个组，相关连功能的参数放入同个组。这个过程实际要复杂的多，通过分析GCC的源代码，把那些在
同一个编译过程 (Pass) 中被调用或功能上紧密耦合的选项划分到一组。例如，所有与代码对齐相关的选项（-falign-loops, -falign-jumps, -falign-functions）被分到一组，它们在功能上都服务于“对齐”这个共同目标。
Option Grouping
这里进行的是静态分组——因为并非所有的参数组合都有意义，动态分组只会增加复杂度，同时可以保证粒度在接受范围内。
具体来说，有三个步骤：
- 标志-过程映射 (Flag-pass mapping): 作者使用一个名为 CodeQL 的静态分析工具来分析 GCC 的源代码 。他们以此找出每个编译器选项（flag）具体是在哪个编译优化过程（pass）中被使用的，从而建立起选项和 Pass 之间的关联 。属于同一个 Pass 的所有选项被初步聚为一组 。
- 合并重叠组 (Merge overlapping groups): 在初步分组后，作者发现有些选项会影响多个 Pass，导致不同组之间有重叠 。为了确保关联紧密的选项被放在一起，他们将所有存在重叠选项的组合并成一个更大的组 。
- 分配剩余项 (Assign leftover options): 合并之后，仍有一些选项属于独立的、无重叠的 Pass 。为了避免分组粒度过细，作者根据这些 Pass 在 GCC 编译流程中的执行顺序，将这些“剩余”的选项分配给最邻近的现有组 。
原文中”nearest existing group”有些抽象，根据笔者的理解，应该说的是编译过程中流程相近的Pass, gcc/passes.def定义了所有优化过程的执行顺序，假设我们已经基于 pass_A 和 pass_D 创建了两个“选项组”。现在有一个“剩余选项”，它属于 pass_C，那么，在执行顺序上，pass_C 离 pass_D 比离 pass_A 更“近”。因此，这个属于 pass_C 的剩余选项就会被分配到 pass_D 所在的那个组里。
通过这个纯粹基于 GCC 内部结构分析的静态过程，作者将206个优化选项划分成了15个功能上内聚的组。
Group-Aware Mutation Search
Initialization
作者以-O3优化为起点，对其进行分组级别的随机变异，生成n个初始候选组合，并把它们放入一个“候选列表” (candidate_list) 中 。
注意，此处与平时使用的编译选项有些差别。为了进行严谨的、自动化的科学研究，必须明确指定某个选项的开关，而非由编译器决定默认值，正因如此，GroupTuner 实际上是一个状态向量模型，是基于内部状态表示，笔者在这里思考了许久。
对候选列表的所有序列进行性能测试，选出一个得分最高的序列作为最佳序列。
History-Based Search
从候选列表中随机选取一个序列作为基础序列，然后随机选择一个组，对组内选项进行随机开关，其他所有组保持不变。然后使用基于模拟退火的方法评估新序列的性能，具体来说，如果新序列比候选列表中最差的那个还要好，就直接替换掉最差的。如果新组合比最差的还要差，算法会以一个特定的概率接受它，这个概率随着“温度”的降低而减小 。这能帮助算法跳出局部最优。
通过不断迭代，最终得出的最佳序列就是最佳的选项组合。
论文接下来谈的是性能和执行时间上均优于其他方法，在此不展开讨论。笔者考虑的是，对FYP有什么启发。
该项目要求使用GA/RL方法来预测编译选项的Cbench分数，笔者有以下几点猜想，待具体要求下发后再验证：
- 也许可以尝试不让模型直接学习206个独立选项的影响，而是学习这15个“特征组”的影响。可能会极大地降低模型的学习难度。
- 如果使用GA, 标准的变异是随机翻转染色体上的任意一个基因（flag），而新算子可以改为：随机选择一个“基因组”（即一个选项组）或 只在这个组内进行基因翻转，可能会使进化过程更具方向性。
参考
B. Gao, M. Yao, Z. Wang, D. Liu, D. Li, X. Chen, and Y. Guo, “Grouptuner: Efficient Group-Aware Compiler Auto-tuning,” in
Proceedings of the 26th ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, and Tools for Embedded Systems (LCTES ‘25), Seoul, Republic of Korea, 2025, doi: 10.1145/3735452.3735530.