论文分享：Adaptive-Auto-Tuning-Framework-for-Global-Exploration-of-Stencil-Optimization-on-GPUs

1 概述

GSTuner：自适应自动调优框架，可以高效地确定模板计算在GPU上的全局优化空间的最佳参数设置。

实现步骤如下：

• 程序生成 (Generation)：首先生成满足对称邻域访问模式的随机模板程序，为后续训练提供多样化的样本。
• 模型训练 (Training)：通过特征提取和数据预处理，统一不同优化组合（OC）的特征向量长度，训练用于预测性能的回归模型。
• 空间采样 (Sampling)：不再盲目搜索，而是利用预测模型指导采样。根据“配额奖励政策”动态调整不同优化组合的采样比例，优先探索潜力区域 。
• 演化搜索 (Search)：在缩小后的空间内，利用定制的遗传算法进行最终搜索。该算法以“子群相似度”作为终止条件，从而降低计算开销。

核心贡献：

全局探索能力：不同于以往仅针对特定优化组合（OC）的工具，GSTuner 分析了不同优化选择对性能的综合影响，并验证了参数设置对网格尺寸的自适应性 。

特征统一机制：提出模板转换机制，能够将复杂多变的模板访问模式转化为机器学习可处理的特征向量，并解决了 OC 之间特征长度不一致的难题 。

窄化搜索空间：设计了基于回归模型的搜索空间收缩机制。通过“配额奖励政策”（Quota-based reward policy），在保证搜索广度的同时，大幅提升了采样效率 。

高效终止策略：在遗传算法中引入“子群相似度”作为终止条件，这使得调优器能够在找到最优解后迅速停止，避免不必要的硬件测量开销。

2 相关背景及介绍

GPU的调优思路：

优化技术	核心原理	主要目标
流式处理 (Streaming)	采用 2.5-D 空间阻隔，将 2-D 切片沿一维流动。	提高数据复用，减少冗余计算。
合并计算 (Merging)	一个线程处理多个输出点，分为块合并（相邻点）和循环合并（固定距离）。	减少内核启动开销，消除重复访存。
预取 (Prefetching)	在当前迭代计算时，将下一迭代数据加载到寄存器中。	重叠计算与访存，隐藏同步屏障带来的延迟。
重定序 (Retiming)	将模板计算分解为子计算和累加过程，使访问均匀化。	平衡内存与寄存器资源，尤其适合高阶模板。
时间阻隔 (Temporal Blocking)	融合多个时间步，避免频繁访问全局内存。	利用隐藏的时间局部性，解决访存受限问题。

现有技术：

1. 集成于领域专用语言（DSL）的调优

   • Halide: 采用随机搜索来自动寻找优秀的流水线调度方案 。

   • Artemis: 采取分步策略，先调优影响力大的优化项，再筛选高性能候选方案 。

   • GoPipe: 专注于流水线盒型模板（如图像卷积）各阶段的任务粒度优化 。

2. 独立的自动调优框架

   • OpenTuner: 集合了多种搜索技术（如差分进化、爬山算法）来寻找最优解 。

   • Garvey: 依靠经验对参数分组，并在随机采样的基础上对每组参数进行穷举搜索 。

   • csTuner: 利用统计学和机器学习方法生成参数组和采样设置，并重新设计了带近似机制的遗传算法以缩短时间 。

局限性：

预设优化的局限: 现有的机制通常只针对预先指定的优化手段或组合进行参数搜索 。

局部最优陷阱: 这种做法将计算限制在局部最优点，而不同优化组合之间的性能差异可能非常巨大 。

解决方案：

支持向量机 (SVM): 通过内核配置和硬件计数器预测 GFLOPS 和执行时间 。

序数回归 (Ordinal Regression): 预测代码变体的性能排名，并使用肯德尔系数评估排名质量 。

卷积神经网络 (CNN): 如 StencilMART，将模板模式转化为二值张量，以此预测最佳的优化组合 。

2.1 优化组合（OC）的必要性

下图为最差OC和最佳OC之间的性能差异。通过调优获得了平均9倍的加速比。

下图为次优OC与最佳OC的性能差异，次优相对最佳OC达到了0.99的加速比

在一个网格尺寸下找到的最佳参数设置，是否在其他尺寸下依然有效的分析

首先在较小的网格（2-D 为 $2,048^2$，3-D 为 $128^3$）中筛选出性能前 100 的参数设置 。随后将这些设置应用于较大的网格（2-D 最高至 $8,192^2$，3-D 最高至 $512^3$）。

可以发现：

不同网格尺寸的加速比曲线非常相似 。

在 2-D 模板中，小尺寸下的最佳设置在大尺寸下依然能达到 1 倍的加速比（即依然是最优）。在 3-D 模板中，其表现也能达到最优值的 0.94 倍至 1 倍 。

3 研究内容

3.1 GSTuner概览

GSTuner的工作流程：

随机模板生成器 (Random Stencil Generator)：

功能：输出各种不同的模板程序，用于收集训练数据 。

地位：这是框架的起点，确保了模型能够学习到多样化的计算模式。

回归机制 (Regression Mechanisms)：输入特定的模板特征和优化参数，输出预测的执行时间 。

功能：在完成数据预处理后，预测每一个唯一参数设置下的性能表现 。

特性：这是 GSTuner 的新提议组件（用 ↑ 表示），旨在通过深度学习模型代替高昂的实际硬件测量 。

搜索空间采样 (Search Space Sampling)：

功能：设计了一种基于配额的奖励政策 (Quota-based Reward Policy)，从高性能的优化组合（OCs）中筛选参数设置 。

意义：该组件（↑）负责窄化搜索空间，确保后续搜索集中在最具潜力的区域 。

演化搜索 (Evolutionary Search)：

功能：通过带有终止条件的遗传算法，在采样后的空间中寻找最优参数设置 。

特性：基于作者之前工作（如 [11], [21]）扩展而来的组件（用 ↗ 表示） 。

通过引入“子群相似度”作为终止条件，用户不再需要根据经验手动设置迭代次数，极大地提高了自动调优的效率。

1.数据准备与特征提取阶段

• 随机模板生成器（Random Stencil Generator ）：根据输入的模板维度和最大阶数，生成多种具有对称访问模式的随机模板程序，用于收集训练数据集 。

• 特征提取（Feature Extraction ）：提取模板的邻域特征，例如非零元素的数量/密度，以及反映内存操作延迟的曼哈顿距离特征 。

• 数据预处理（Data Pre-processing ）：这是新提出的核心步骤，旨在解决不同优化组合（OC）之间特征向量长度不一致的问题 。

• 零填充（Zero-padding）：为所有可能的优化预留空间，缺失部分补零 。

• 变长序列（Varying-length）：将参数按优化手段分组并链成序列 。

2.模型训练与回归阶段

这一阶段构建了框架的“预测大脑”：

训练数据收集（Training Data Collection ）：通过随机参数搜索和皮尔逊相关系数分析，对生成的模板进行实际测量，建立“模板特征 + 优化组合 -> 执行时间”的数据集 。

回归机制（Regression Mechanisms ）：利用深度学习模型预测性能 ：

ZPNet (MLP)：适用于零填充格式的数据 。

VLNet (RNN)：利用 LSTM 处理变长序列数据 。

3.搜索空间采样阶段

利用预测模型来智能缩小搜索范围，避免无效的硬件实验：

搜索空间采样（Search Space Sampling ）：

配额奖惩策略（Quota-based reward policy）：根据回归模型的预测结果，动态调整采样比例 。

奖励机制：表现更好的优化组合（OC）会获得更高的采样配额，从而在保证探索广度的同时，将资源集中在高性能区域 。

4.演化搜索与产出阶段

在精选出的采样空间内进行最后的冲刺搜索：

演化搜索（Evolutionary Search ）：

多进程遗传算法：使用 MPI 通信在多个子种群之间进行个体迁移（Migration），加速收敛 。

MCR 终止条件（MCR termination condition）：根据子群中相同个体的比例（Maximum-count individuals Ratio）自动判断是否达到最优并停止搜索 。

最终输出：产出针对目标模板在特定 GPU 硬件上的最优参数设置（Optimal Parameter Setting） 。

3.2 随机模板生成

任何维度的模板访问模式都被表示为一个稀疏张量 。物理意义：张量中的索引代表了邻居点相对于中心点的偏移量 。

为了训练性能预测模型，需要大量的样本。GSTuner 放弃了简单的随机采样，转而设计了一种符合物理特性的生成算法：

该算法通过以下四个步骤确保生成的模板既具有随机性，又符合实际工业应用场景：

区域划分：将张量空间划分为具有重叠边界的局部区域，并选择其中一个进行采样 。

迭代采样：从低阶邻居开始，迭代地采样到高阶邻居 。在每次迭代中，随机采样上一轮选中点的更高阶邻居 。

对称映射：将采样的点对称地映射到张量空间的其他局部区域 。

去重处理：移除采样和映射过程中产生的重复邻居点 。

效果：

1.通过这种方式生成的模板能够覆盖所有流行的模板形状 。

2.生成的模板严格遵循对称邻域访问模式，这使得基于这些数据训练出来的回归模型在处理真实世界的 HPC 应用程序时具有极高的准确性 。

3.3 模板表示

GSTuner 采用了一种数学化的转换方式来捕捉计算特征：

空间转化：将访问的邻居点相对于中心点的偏移量（Offset）映射到张量的非零元素位置 。

分布捕捉：这种稀疏张量的表示法能够完整记录邻域访问的几何分布 。

3.3.1 核心创新：引入曼哈顿距离

权重的演进：StencilMART 仅生成二值张量（0 或 1），而 GSTuner 为每个非零位置分配了该点到中心点的曼哈顿距离 。

物理意义：曼哈顿距离在很大程度上决定了内存操作的延迟（Memory Latency），进而显著影响特定优化手段下的性能表现 。

3.3.2 回归预测

以往工作（如 StencilMART）使用卷积神经网络（CNN）直接预测最佳优化组合（OC），但这种“激进修剪”容易漏掉被低性能参数包围的全局最优解 。GSTuner 使用回归算法预测具体参数设置的执行时间，以此引导搜索空间的采样过程，确保了探索的深度和广度 。

为了提高回归模型的拟合效果，GSTuner 提取了一系列候选特征：

1.距离导向：与以往关注整体张量稀疏分布的研究不同，GSTuner 专注于邻居点与中心点之间的距离特征 。

2.特征维度：

包含每一阶邻居点的数量及比例。

Step-$m$ 特征：指曼哈顿距离为 $m$ 的具体位置信息，其中 $m$ 的范围取决于模板阶数和维度。

即输入特定的模板特征和优化参数，输出预测的执行时间 。

3.4 性能预测

1.输入特征的组成

• 模板候选特征集：反映模板本身的计算模式（如前文提到的曼哈顿距离、邻居分布等）

• 参数设置：包含三种类型的参数：

  • 数值型：如合并因子（merging factor），通常限制为 2 的幂 。为了训练稳定性，GSTuner 会对其进行 $log_2$ 运算 。

  • 布尔型：如是否使用共享内存，参数化为 $\{0, 1\}$ 。

  • 枚举型：如流维度（streaming dimension），从 1 开始以步长为 1 进行表示。

2.解决“向量不一致”的预处理方案

GSTuner 提出了两种统一格式 ：

零填充格式 (Zero-padding)：为全局所有可能的优化预留位置。如果某个 OC 不包含某项优化，则在该位置补零 。

变长格式 (Varying-length)：将参数按优化手段分组，并将各组链接成一个序列 。

3.两种回归机制：ZPNet 与 VLNet

• A. ZPNet (基于 MLP)

  • 数据适配：适用于零填充格式 。

  • 结构：由输入层、多个隐藏的多层感知器（MLP）层和输出层组成 。

  • 优势：可以通过调整层数和单元数来平衡预测精度与推理开销 。

• B. VLNet (基于 RNN)

  • 数据适配：适用于变长格式 。

  • 结构：包含掩码层（Masking layer）、长短期记忆网络（LSTM）层和多个全连接（FC）层 。

  • 逻辑：掩码层告诉 LSTM 跳过缺失的参数组 。模板特征和 LSTM 的输出会合并为联合特征，共同进入后续的 FC 层 。

3.5 搜索空间采样

用训练好的回归模型来智能地缩小搜索空间。

尽管回归模型可以预测执行时间，但直接取预测值最小的配置存在以下风险：

运行时失败：预测的最优设置可能因为资源溢出（如共享内存不足）而根本无法运行 。

预测误差：由于模型精度限制以及高性能配置之间极高的相似性，预测的最优解往往不是实际的最优解 。

成本控制：通过采样过滤掉大量低效配置，可以避免对海量模板实例进行实际硬件测量，从而极大降低调优成本 。

3.5.1 核心算法：配额奖惩策略

GSTuner 窄化搜索空间的核心算法（Algorithm 2），其基本原则是：哪个优化组合（OC）表现出更大的性能潜力，就增加该组合的采样比例（作为奖励） 。

A. 初始化与约束检查

比例初始化：最初根据每个优化组合（OC）中参数设置的数量占总数的比例来设定初始采样率（SR） 。

参数约束：在统计每个 OC 的设置数量时，会严格检查优化参数之间的显式约束（例如某些优化不能同时启用） 。

B. 迭代奖励机制

当前轮次筛选：在每一轮采样中，选出该轮次内预测性能最好的 OC 。

避免“早熟”：为了防止某个在初期表现较好的 OC 统治整个过程（Early promise），奖励仅基于当前轮次的表现，而不是历史累计表现。

配额重分配：

• 其他所有 OC 的采样率都会被扣除一个固定的“调整比例”（AR） 。
• 扣除出来的配额（剩余配额）将全部补偿给该轮次表现最佳的 OC 。

C. “逆袭”机制（Counterattack）

由于最优解往往隐藏在平均性能较差的区域，如果完全只采样表现好的 OC，可能会漏掉全局最优解 。

下限设定：为所有 OC 设定一个采样比例下限（LR） 。

作用：确保那些在之前迭代中表现不佳的 OC 始终保有一定的采样机会，从而有可能在后续采样中凭借某个极其出色的参数设置实现“逆袭” 。

3.6 进化搜索

3.6.1 多进程遗传算法架构

为了提升搜索效率，GSTuner 采用了多进程并行的架构：

个体与基因：一个“个体”由多个“基因”组成，代表一组特定的优化参数配置 。

种群划分：众多个体组成一个“种群”，种群被划分为多个“子种群”，每个子种群由一个独立的进程处理。

迁移机制：各子种群之间通过 MPI 通信 进行个体迁移。迁移遵循“单环拓扑”结构，每个子种群与其相邻的两个邻域交换个体。

3.6.2 个体繁殖与进化

新个体的产生（育种）经过三个标准步骤，以模拟生物进化：

父母选择：从四个邻域中选择父母，适应度（性能表现）越高的个体被选中的概率越大。

均匀交叉：新个体的每个基因随机从父母双方的对应基因中选取。

变异：基因以一定的概率发生随机改变，这是为了防止种群陷入局部最优解**。

3.6.3 非连续参数的重索引

这是一个关键的技术细节。由于采样后的搜索空间参数不再连续，直接进行基因编码会很困难 ：

问题：例如可选参数集为 $\{(0, 1), (4, 2), (3, 4)\}$，它们在数值空间上是跳跃的。

解决方案：GSTuner 对这些有效值进行升序重索引（如重新映射为 $\{0, 2, 1\}$）。

效果：将原本离散的参数空间映射为连续的索引范围（如 $[0, 2]$），使得遗传算法可以正常运行。

3.6.4 创新的终止条件：MCR

相比于作者之前的研究（csTuner）使用“前 $n$ 名适应度的变异系数”作为停止信号，GSTuner 引入了更高效的 MCR（最大计数个体比例） 机制 ：

核心挑战：计算 CV 需要通过 MPI 聚合所有子种群的数据，通信开销巨大，且阈值难以统一适配所有模板。

GSTuner 的做法：监控子种群的相似度。当任意子种群中出现频率最高的个体比例达到设定的阈值时，搜索即停止 。

• 优势：

  减少通信：不再需要大规模的数据聚合，降低了通信开销。

  更好的可扩展性：能够自动适应不同模板的特性，避免因过早停止而陷入次优解，或因停止过晚而增加搜索成本。

4 结论

GSTuner 的核心设计思想与实验表现：

自适应框架: 提出了一个能够高效识别 GPU 模板全局优化空间最优参数设置的框架 。

技术路径:

• 将模板模式表示为邻域特征，并统一不同优化组合（OC）的特征向量 。
• 利用配额奖惩策略和已训练模型指导全局空间的采样 。
• 采用考虑子群相似度的遗传算法进行参数搜索 。

成效: 实验证明 GSTuner 能准确预测 GPU 上模板实例的执行时间，并能比现有最先进工作在更短时间内找到高质量参数 。