GPU自动调优优化算法的基准测试：一项面向进化黑盒优化的综合实验与分析

本文旨在为中文研究社区介绍一篇发表于《IEEE Transactions on Evolutionary Computation》期刊上的学术研究论文。该论文题为“Benchmarking Optimization Algorithms for Auto-Tuning GPU Kernels”，由来自荷兰国家数学与计算机科学研究院（CWI）、荷兰eScience中心以及莱顿高级计算机科学研究所（LIACS）的研究团队完成，作者包括Richard Schoonhoven， Ben van Werkhoven， 和 K. Joost Batenburg。本研究属于高性能计算（HPC）、软件工程与进化计算交叉领域的研究，具体聚焦于图形处理器（GPU）内核的自动性能调优（Auto-tuning）问题。

学术背景与目标 近年来，图形处理器（GPU）因其强大的并行计算能力和相对低廉的成本，在科学计算、人工智能（AI）等诸多领域得到爆炸式应用。然而，编写一个计算高效的GPU程序（内核）极具挑战性。GPU内核的性能高度依赖于大量参数（如线程块大小、内存布局、循环展开因子等）的配置，而这些参数构成了一个离散、非凸的庞大搜索空间。通常，只有极少数特定的配置组合能带来显著的性能提升。手动或穷举搜索最优配置通常不现实，因为每个配置的评估都涉及耗时的重新编译和测试运行。此外，相同的GPU内核在面对不同的输入数据、硬件架构或代码修改时，往往需要重新调优。

自动性能调优技术旨在通过经验性反馈，自动优化内核参数以实现期望的性能指标（如最短运行时间）。这个过程可以被形式化为一个黑盒优化问题。然而，一个核心问题随之而来：哪种优化算法最适合为GPU内核寻找高效配置？如何配置这些算法以获得最佳效果？尽管存在多种通用自动调优框架（如OpenTuner， CLTune， Kernel Tuner等），但针对GPU内核调优这一特定问题，对各种优化算法进行系统性、大规模的比较与分析仍然缺乏。此外，如何量化不同内核调优问题的“难度”，并理解不同算法表现差异背后的原因，也是一个有待探索的课题。

本研究的主要贡献是双重的：第一，通过大规模实验，确定在不同调优时间预算下，哪些优化算法能够为GPU内核产生最快的配置。第二，引入一种基于“适应度流图”（Fitness Flow Graph， FFG）和PageRank中心性的新指标，用于量化和洞察GPU内核调优搜索空间的难度，并解释算法性能差异的原因。

详细工作流程 本研究的工作流程严谨且全面，主要包含以下几个步骤：

1. 实验平台与基准内核构建：研究团队选用了9款不同型号的NVIDIA和AMD GPU（涵盖了从2012年的Tesla K20到2020年的A100等多种架构），以及3个具有实际应用价值的基准GPU内核：卷积（Convolution）、通用密集矩阵乘法（GEMM）和点在多边形判定（PNPOLY）。这些内核的搜索空间经过精心设计，使得在充足计算资源下可以完整遍历，从而获得全局最优解和完整的搜索空间信息。研究团队公开了这26个（9 GPU × 3 内核，部分组合不适用）完整的搜索空间缓存文件，为后续算法基准测试和空间分析奠定了基础。

2. 优化算法选择与超参数调优：研究调查了16种进化与黑盒优化算法，并将其分为三类：离散算法（如随机搜索、多起点局部搜索（MLS）、迭代局部搜索（ILS）、禁忌搜索、模拟退火（SA）、遗传算法（GA）、遗传局部搜索（GLS））、连续算法（通过映射应用于离散空间，如盆地跳跃（Basin Hopping）、双重退火（Dual Annealing）、粒子群优化（PSO）、差分进化）以及专门用于随机优化的调参算法（如顺序模型算法配置（SMAC）、迭代竞赛（Irace））。为了公平比较，研究首先在部分GPU和内核上对每种算法的超参数（如邻域定义、种群大小、扰动强度等）进行了广泛的网格搜索，为不同函数评估预算（从25到1600次）选出了一组在多种条件下表现稳健的默认超参数。

3. 确定性性能基准测试：这是本研究核心的实验部分。对于每个内核-GPU组合，使用每种优化算法，在设定的函数评估预算（25， 50， 100， 200， 400， 800， 1600）下进行50次独立运行。内核的性能（适应度）被定义为32次运行的平均时间（确定性设置）。算法性能通过其找到的配置的运行时间与已知全局最优运行时间的比值（最优适应度分数）来评估。研究通过两样本独立t检验（α=0.05）统计比较了不同算法在低预算（≤200次评估）和中高预算（>200次评估）下的表现优劣。

4. 随机性性能基准测试：为了评估算法在处理具有噪声的适应度评估时的表现，研究进行了另一组实验。在此设置下，每次函数评估返回的是单次内核运行的时间（而非平均值）。这模拟了更真实的运行时波动环境。在此设置下，重点测试了SMAC、Irace以及之前在确定性测试中表现良好的算法（如双重退火、GA、firstILS）。

5. 搜索空间难度量化与分析：为了深入理解算法性能差异并量化调优难度，研究团队提出了创新性的分析方法。首先，他们构建了“适应度流图”（FFG）。FFG将搜索空间中的每个点表示为图节点，并在两个相邻点之间建立一条有向边，边的方向从适应度较差的点指向较好的点。这样，在FFG上的随机游走就模拟了随机“首次改进”局部搜索算法的行为。其次，他们借鉴网络分析中的PageRank算法，计算FFG中每个节点的中心性。对于局部最小点，其PageRank值代表了长随机游走最终到达该最小点的概率。最后，他们定义了一个“中心性比例”（Proportion of Centrality）指标：计算所有适应度在全局最优一定百分比（例如p%）范围内的“优质”局部最小点的PageRank值之和，除以所有局部最小点的PageRank值总和。这个比例越高，意味着随机局部搜索算法更容易“陷入”一个接近全局最优的局部最小点，从而预示着该搜索空间可能“更容易”调优。

主要结果 研究的实验结果丰富且具有启发性：

1. 算法性能排名：

   • 确定性设置，低预算（≤200次评估）：双重退火（Dual Annealing）算法表现最佳，在三个内核上 consistently 优于或与其他顶尖算法持平，尤其是在卷积和PNPOLY内核上优势明显。其次是模拟退火（SA）。值得注意的是，基于贝叶斯优化的SMAC在GEMM内核上表现甚至不如随机搜索，研究人员推测这可能与GEMM搜索空间中极高的编译失败率（约78%）有关，这干扰了代理模型的构建。
   • 确定性设置，中高预算（>200次评估）：局部搜索类算法脱颖而出。first-improvement版本的迭代局部搜索（firstILS）、多起点局部搜索（firstMLS）以及遗传局部搜索（GLS）和模拟退火（SA）成为表现最好的算法。相比之下，“最佳改进”版本的局部搜索算法（bestILS， bestMLS）由于需要评估所有邻域点，在有限预算下效率低下，表现较差。粒子群优化（PSO）整体表现不佳。
   • 随机性设置：总体而言，要达到与确定性实验相近的解质量，需要更多的函数评估预算。遗传算法（GA）和双重退火在低预算下表现良好，而firstILS在预算≥100时表现强劲。Irace在GEMM内核的大预算（≥800）下表现最好，但在其他内核上未能超越前述算法。SMAC在随机性设置下同样表现不佳。因此，研究建议将GPU内核调优视为确定性优化问题（使用平均运行时间）更为高效。

2. 超参数影响：研究为每种算法在不同预算下提供了经过调优的默认超参数集（详见表III），这为实践者使用这些算法进行GPU调优提供了宝贵的起点。例如，对于局部搜索算法，“首次改进”策略和“邻接”邻域定义（仅考虑参数值列表中相邻的值）通常更有效。

3. 搜索空间难度分析结果：

   • 研究首先检验了一个直观的简单指标——“局部最小点的最优适应度分数分布”，发现它无法解释实际观测到的调优难度差异。例如，对于卷积内核，A100 GPU的局部最小点中位数更接近最优值，但实际调优中算法在A100上找到接近最优解反而更困难。
   • 新提出的“中心性比例”指标则与实验结果高度吻合。以卷积内核为例，V100 GPU的“中心性比例”最高，意味着其优质局部最小点更容易被局部搜索到达，而实验也证实双重退火和firstILS在V100上能以更少的评估找到更优的解。相反，A100的“中心性比例”最低，对应了实际调优的更高难度。对于GEMM和PNPOLY内核，该指标同样成功区分了不同GPU型号上内核调优的难易程度。
   • 分析还揭示了一个有趣现象：调优难度并不与GPU的新旧程度直接相关。例如，最新的A100在卷积内核上调优反而比一些旧型号更困难，而在GEMM和PNPOLY上，新GPU的调优则相对更容易。

结论与价值 本研究得出以下主要结论： 1. 算法推荐：对于GPU内核自动调优，如果希望用极少的重编译和测试次数（低评估预算）快速获得良好配置，双重退火（Dual Annealing） 是最佳选择。如果可以承受更多的评估次数（中高预算），则首次改进的迭代局部搜索（firstILS） 等局部搜索算法能更可靠地找到接近最优的配置。 2. 问题性质：将GPU内核调优视为确定性优化问题（使用平均运行时间作为适应度）比视为随机优化问题更有效、更节省时间。 3. 难度度量：研究提出的基于适应度流图（FFG）和PageRank中心性比例的新指标，能够有效量化不同GPU-内核组合的调优难度，并解释算法表现的差异。这为理解GPU内核性能空间的复杂结构提供了新的分析工具。 4. 资源贡献：研究完整计算并公开了26个GPU内核搜索空间的数据集，为进化计算和黑盒优化领域的研究者提供了一个新的、真实的、可重复的基准测试平台。

本研究的科学价值在于首次对GPU内核自动调优这一特定问题进行了大规模、系统性的优化算法基准测试，并提供了经过实证检验的算法选择与超参数配置指南。其应用价值在于直接指导GPU程序员和HPC工程师高效地进行自动性能调优，节省大量手动尝试的时间。方法论上的价值在于引入了FFG和PageRank这一新颖的组合工具来分析离散优化问题的搜索空间特性，为后续研究开辟了新思路。

研究亮点 1. 大规模系统性基准测试：覆盖9款GPU、3个真实内核、16种算法、多个时间预算的全面实验，结论具有很高的代表性和实用性。 2. 实用的超参数配置指南：不仅比较算法，还为每种算法在不同使用场景下提供了经过优化的默认超参数，极大提升了研究的实用价值。 3. 创新性的难度量化指标：创造性地将网络科学的PageRank算法应用于优化搜索空间分析，提出的“适应度流图”和“中心性比例”概念，为理解和预测优化问题难度提供了新的理论视角和量化工具。 4. 开放数据集：公开完整的搜索空间缓存，促进了该领域研究的可重复性和进一步发展。

其他有价值内容 论文还详细介绍了其使用的软件工具：Kernel Tuner（一个支持多种优化算法的通用GPU内核调优框架）和Bloopy（作者开发的用于离散黑盒优化的Python包，实现了本研究所用的算法和FFG等分析工具）。这些工具的可用性为其他研究者复现和扩展本工作提供了便利。