面向GPU平台的通用Stencil自动调优框架

孙庆骁; 杨海龙

doi:10.7544/issn1000-1239.202440612

面向GPU平台的通用Stencil自动调优框架

孙庆骁^1,,
杨海龙²

1.
中国石油大学（北京）人工智能学院　北京　102249
2.
北京航空航天大学计算机学院　北京　100191

详细信息

作者简介:
孙庆骁: 1996年生. 博士，副教授. CCF会员. 主要研究方向为异构运行时系统、性能优化

杨海龙: 1985年生. 博士，教授. CCF杰出会员. 主要研究方向为高性能计算、智能计算系统

中图分类号: TP319
计量
- 文章访问数: 54
- HTML全文浏览量: 6
- PDF下载量: 9
出版历程
- 收稿日期: 2024-07-14
- 录用日期: 2025-01-25
- 网络出版日期: 2025-01-25

Generalized Stencil Auto-Tuning Framework on GPU Platform

Sun Qingxiao^1,,
Yang Hailong²

1.
College of Artificial Intelligence, China University of Petroleum-Beijing, Beijing 102249
2.
School of Computer Science and Engineering, Beihang University, Beijing 100191

More Information

Author Bio:
Sun Qingxiao: born in 1996. PhD, associate professor. Member of CCF. His main research interests include heterogeneous runtime system and performance optimization

Yang Hailong: born in 1985. PhD, professor. Distinguished member of CCF. His main research interests include high performance computing and intelligent computing system

摘要

摘要:
Stencil计算在科学应用中得到了广泛采用. 许多高性能计算平台利用GPU的高计算能力来加速Stencil计算. 近年来，Stencil计算在阶数、内存访问和计算模式等方面变得更加复杂. 为了使Stencil计算适配GPU架构，学术界提出了各种基于流处理和分块的优化技术. 由于Stencil计算模式和GPU架构的多样性，没有单一的优化技术适合所有Stencil实例. 因此，研究人员提出了Stencil自动调优机制来对给定优化技术组合进行参数搜索. 然而，现有机制引入了庞大的离线分析成本和在线预测开销，并且无法灵活地推广到任意Stencil模式. 为了解决上述问题，提出了通用Stencil自动调优框架GeST，其在GPU平台上实现Stencil计算的极致性能优化. 具体来说，GeST通过零填充格式构建全局搜索空间，利用变异系数量化参数相关性并生成参数组. 之后，GeST迭代地从参数组选取参数值，根据奖励策略调整采样比例并通过哈希编码避免冗余执行. 实验结果表明，与其他先进的自动调优工作相比，GeST能够在短时间内识别出性能更优的参数设置.
- Stencil计算 /
- GPU /
- 自动调优 /
- 性能优化 /
- 参数搜索
Abstract:
Stencil computations are widely adopted in scientific applications. Many HPC platforms utilize the high computation capability of GPUs to accelerate stencil computations. In recent years, stencils have become more complex in terms of stencil order, memory accesses, and computation patterns. To adapt stencil computations to GPU architectures, the academic community has proposed a variety of optimization techniques based on streaming and tiling. Due to the diversity of stencil computational patterns and GPU architectures, no single optimization technique fits all stencil instances. Therefore, researchers have proposed stencil auto-tuning mechanisms to conduct parameter searches for a given combination of optimization techniques. However, existing mechanisms introduce huge offline profiling costs and online prediction overhead, unable to be flexible to arbitrary stencil patterns. To address the above problems, this paper proposes a generalized stencil auto-tuning framework GeST, which achieves the ultimate performance optimization of stencil computations on GPU platforms. Specifically, GeST constructs the global search space through the zero-padding format, quantifying parameter correlations via the coefficient of variation to generate parameter groups. After that, GeST iteratively selects parameter values from the parameter groups, adjusting the sampling ratio according to the reward policy and avoiding redundant execution through hash coding. The experimental results show that GeST can identify better-performing parameter settings in a short time compared to other state-of-the-art auto-tuning works.
- stencil computation /
- GPU /
- auto-tuning /
- performance optimization /
- parameter search

HTML全文

Stencil计算是科学应用最常采用的计算模式之一，出现在图像处理^[1]、物理仿真^[2]和元胞自动机^[3]等领域. Stencil计算扫描计算网格并处理每个点周围的固定邻居来更新其值，其中邻居沿每个维度的范围称为阶（order）. 例如，盒型Stencil用于在图像处理中执行平滑和其他基于邻居像素的计算^[4].

近年来，Stencil计算在阶数、数据访问和计算模式等方面趋向于多样化^[5]. Stencil计算往往具有丰富的并行性，这使得其很适合部署在GPU上进行性能加速. 然而，程序员必须确保内存合并、重叠计算和数据访问、减少同步和消除线程分歧，以及在并行性和资源利用之间进行权衡^[6]. 为了适应GPU架构的高计算能力和有限内存带宽，研究工作提出了许多基于流处理和分块的优化技术^[7]. 由于计算模式的多样性，单一的优化技术无法适用于所有Stencil实例.

Stencil领域特定语言（domain-specific language，DSL）集成各种优化技术来探索自动代码生成^[8]. 尽管DSL可有效加速Stencil计算，各个优化技术的性能影响仍难以评估. 此外，指定优化组合下能否生成高性能代码取决于Stencil计算模式和GPU硬件架构. 为了充分提升性能，Stencil DSL通常采用基于穷尽参数搜索的性能调优策略^[9]. 然而，这些策略在适应更多优化选项时扩展性较差，并且在大型优化空间中的搜索过程非常耗时. 另一方面，Stencil自动调优框架被提出以确定指定优化组合下的最佳参数设置^[10]. 尽管这些框架能够缩小参数空间，但它们严重依赖于专家知识. 而且，当优化组合不适用于特定的Stencil计算模式时，其性能提升也十分有限.

最新工作基于机器学习选取高性能优化组合，并根据预测性能来指导搜索空间采样，从而避免陷入性能不佳的局部优化空间^[11]. 然而，优越设置的相似性会导致不可避免的预测误差，因此仅通过性能预测来确定最优参数设置是不可行的. 另一方面，机器学习方法需要构建庞大的训练集，并引入显著的训练成本，且最终效果因Stencil计算模式而异. 即便仅考虑在线开销，对于所含模式较少而无法批量预测的应用来说，前向推理的启动时间也是不可接受的.

为了应对上述挑战，本文提出通用Stencil自动调优框架GeST，其能够高效地识别GPU上全局优化空间的高性能参数设置. GeST首先将Stencil优化技术和GPU优化选项进行参数化，并基于零填充构建全局搜索空间. 之后，GeST对全局搜索空间进行随机采样，通过统计学指标量化参数相关性并生成参数组. 最后，GeST迭代地从参数组中采样参数值并将参数设置的哈希编码存储于字典以避免冗余执行. 本文开展了大量的实验来评估GeST框架，以验证其在Stencil性能自动调优方面的有效性.

本文的主要贡献包括4个方面：

1）详尽分析了Stencil计算在GPU上的优化技术及其组合的参数范围和性能影响. 此外，设计了检查优化约束的规则，从而仅执行有效的参数设置；

2）提出了参数分组策略，对特定Stencil计算模式进行少量的随机采样执行，基于统计学指标量化成对参数的相关性，生成参数组以缩小搜索范围；

3）提出了搜索空间采样机制，迭代地从参数组选取参数值，执行选到的参数设置并根据性能反馈调整采样比例，通过哈希编码存储以避免重复执行；

4）实现了通用Stencil自动调优框架GeST，其对GPU上的全局优化空间进行高效搜索. 实验结果表明，GeST取得了更高的调优效率和最终性能.

1. 背　　景

1.1 GPU架构和执行模型

GPU由数十到百余个流多处理器（streaming multiprocessor，SM）组成. 如图1所示，每个SM包含数百个计算核心和其他存储资源（寄存器、共享内存和L1高速缓存）. 在GPU上执行的代码被称为内核. CPU主机端启动内核后，GPU上会创建大量线程，每32个线程分到一个Warp中. 多个Warp组成一个线程块（thread block，TB），TB的大小由内核配置决定. TB调度器根据轮询策略将TB调度给SM，并在计算资源和硬件限制下最大化GPU利用率.

图 1 GPU基础硬件架构

Figure 1. Basic hardware architecture of GPU

下载: 全尺寸图片幻灯片

由于SM中的计算资源有限^[12]，GPU任务必须进行微调以实现系统利用率和性能加速比之间的权衡. 某些优化策略（如循环展开）增加寄存器级别的数据重用以提高性能^[13]. 然而，生成的代码受到寄存器压力的高度约束，甚至可能导致寄存器溢出. 此外，需要仔细确定参数设置才能获得更好的性能. 例如，适当的TB大小可以在硬件限制下最大化线程级并行（thread-level parallelism，TLB）. 但是，过高的TLB可能会导致缓存抖动，特别是对于诸如Stencil计算的内存密集任务^[14]. 因此，仅通过分析建模来进行GPU任务的性能调优是不够的^[9].

1.2 Stencil性能优化技术

在具有高计算能力的GPU上加速Stencil计算已经引起学术界的广泛关注^[15-16]. 下面将简要讨论面向GPU架构的Stencil性能优化技术，如表1所示.

表 1 面向GPU平台的Stencil性能优化技术

Table 1. Stencil Performance Optimizations Technology on GPU Platforms

优化技术	简称	约束
流处理（streaming）	ST	—
块合并（block merging）	BM	启用CM时无效
循环合并（cyclic merging）	CM	启用BM时无效
重定时（retiming）	RT	仅在启用ST时有效
预取（prefetching）	PR	仅在启用ST时有效
时间分块（temporal blocking）	TL	—
“—”表示没有约束.

下载: 导出CSV

| 显示表格

1）流处理（streaming）：流处理技术是一种常见的优化，可以改进数据重用并减少流维度上的计算冗余. 针对3D输入网格，流处理技术的有效实现是采用2.5D空间分块. 具体来说，2D块的计算在一个维度上流式传输，每个块的数据被重用以更新下一个块. 然而，如果问题规模很大，流处理技术会增大计算粒度从而限制并行性. 为了取得更好的性能，并发流处理技术^[6]将流维度划分为块，其中TB以块粒度并行遍历流维度. 与此同时，流处理技术可以结合循环展开来增加寄存器级别的数据重用.

2）块/循环合并（block/cyclic merging）：一般来说，每个GPU线程负责单个输出点. 合并多个输出点的计算能够降低内核启动开销并消除冗余内存访问. 研究人员提出了2种技术来合并计算，包括块合并和循环合并. 块合并技术合并多个相邻的输出点，而循环合并技术则将具有固定距离的每个点合并. 然而，这2种技术都可能增大寄存器压力并降低驻留在每个SM上的线程数量. 此外，全局网格最内层的块合并会破坏内存合并^[17]. 合并技术的选择以及要合并点的数量会显著影响Stencil计算的性能.

3）预取（prefetching）：在当前迭代更新输出网格后，流处理会移动位于共享内存中的数据来继续下一次迭代的计算. 由于海量线程的并发执行，相邻迭代之间必须进行同步以保证结果的正确性. 同步会导致内核之间的串行处理而损失性能. 预取技术通过重叠计算和数据加载来隐藏同步延迟^[6]. 具体来说，在处理当前迭代计算的同时，用于下一次迭代的数据被加载到寄存器中. 然而，预取技术可能会耗尽GPU上非常有限的寄存器.

4）重定时（retiming）：重定时技术将Stencil计算分解为一组子计算，再累积结果来改进数据重用^[18]. 重定时通过同质化Stencil访问来平衡内存和寄存器之间的资源使用. 由于寄存器的有效重用，高阶Stencil可以受益于重定时优化. 然而，重定时技术对于具有低寄存器压力的Stencil计算几乎无效.

5）时间分块（temporal blocking）：尽管Stencil计算具有跨时间步的数据依赖，但每个点的依赖范围受到Stencil邻接访问模式和自该点上次更新以来经过的时间步数的限制^[9]. 时间分块技术合并时间步并避免全局内存访问以利用隐藏的时间局部性，再通过相邻块的冗余加载来解决沿时间维度的数据依赖. 然而，时间分块技术可能会导致受寄存器约束的Stencil计算的性能下降.

Stencil优化技术的有效性取决于多种因素，例如GPU架构和Stencil计算模式. 在某些约束（见表1）下，可以组合优化技术以进一步改进性能. 另外，参数设置选择不当会导致性能欠佳. 以上驱动了针对Stencil计算的优化和参数联合搜索机制的实现.

1.3 Stencil自动调优机制

由于Stencil模式的多样性，任何优化都必须进行微调以最大化性能. Stencil框架将与性能相关的参数暴露给集成在其框架中的参数调优机制来实现此目的. Halide^[8]应用随机搜索来自动找到良好的流水线规划. Halide还限制了每个函数的域调度操作数以防止生成代码爆炸. Artemis^[6]通过分层参数调优来裁剪搜索空间. Artemis首先调整对计算性能影响较大的优化技术，然后选择高性能候选参数. GoPipe^[19]为盒状Stencil（如卷积）的每个阶段找到最佳任务粒度和调度机制. AN5D^[9]根据性能模型获得Top-5的参数集，并基于实际执行选择其中最高性能的参数集. 以上自动调优机制是专为Stencil框架定制的，因此它们在评估更多优化技术时的可扩展性较差.

为了克服上述限制，其他工作专注于加快Stencil计算的参数调优进程. FAST^[20]训练回归模型来预测最佳解空间的相似度，并建立参数特征和优化解之间的映射. OpenTuner^[21]实现一系列搜索技术（如差分进化和爬山器）来寻找最优解决方案. Garvey等人^[17]根据先验知识对优化参数进行分组，并在启用随机采样的情况下详尽地搜索每组的参数设置. csTuner^[10]采用统计学和机器学习方法生成参数组和采样设置，随后设计考虑近似性的遗传算法以减少搜索时间. Trümper等人^[22]对循环嵌套的动静态性能特征进行编码，并将优化参数存储在数据库中以实现迁移调优. 以上自动调优框架通常对预先指定的优化或其组合执行参数搜索，这很容易陷入局部优化空间.

除了参数自动调优之外，研究人员还利用性能预测来研究优化技术对Stencil计算的影响. Martínez等人^[23]将内核配置和硬件计数器提供给支持向量机来预测GFLOPS和执行时间. Cosenza等人^[24]利用序数回归来预测代码变体的性能排名，排名质量通过Kendall系数进行评估. Nesterenko等人^[25]对优化组合和领域级属性之间的相互作用进行性能建模. StencilMART^[14]通过张量赋值将Stencil模式表示为二元张量，再利用卷积神经网络来预测最佳优化组合. 上述工作没有实现性能预测与自动调优的有效融合，且对于不可避免的预测误差也缺乏良好的容错能力. GSTuner^[11]基于零填充统一不同优化组合的特征向量，并根据预测性能来指导全局搜索空间采样和遗传进化搜索. 然而，基于机器学习的性能预测方法都需要预先收集海量性能数据来构成Stencil数据集，并且引入了显著的离线训练和在线推理成本，这对于轻量级的Stencil计算来说通常是难以接受的.

2. 方法设计与实现

2.1 设计概要

本文提出通用Stencil自动调优框架GeST来高效地确定全局优化空间的高性能参数设置，如图2所示. GeST由2个重要组件组成，包括参数分组和搜索空间采样. 参数分组组件通过统计学指标和分组算法聚合强相关的参数，其中Stencil数据集来自随机采样过程. 搜索空间采样组件利用奖励策略来选取参数值设置并基于执行反馈来调整采样比例，其中初始参数设置和初始采样比例分别基于Stencil数据集和参数组来生成. 与先前方法不同，GeST不会引入任何离线开销，即使是Stencil数据集的收集过程也是通过随机采样在线完成，并且计入整体调优时间内.

图 2 GeST框架的设计概要

Figure 2. The design overview of GeST framework

下载: 全尺寸图片幻灯片

图2展示了GeST框架的设计概要. GeST将Stencil优化技术和GPU特定选项参数化为搜索空间，其中每个参数设置都被预处理为零填充格式以统一各种优化组合. GeST对参数搜索空间进行随机采样以获取Stencil数据集，其用于指导参数分组以及生成后续采样过程的初始参数设置. GeST将参数对的量化相关性指标存储在双端队列中，并通过分组算法聚合参数以降低搜索工作量. GeST从参数组中迭代地采样参数设置，其中每组的采样比例根据基于配额的奖励策略进行调整. GeST将选取到的设置通过哈希编码存储在字典中以避免冗余的重新执行.

由于GeST无需离线性能分析和模型训练，其可以被轻易地推广到任意Stencil计算模式和输入网格大小，以及集成更多参数来捕获未来的Stencil优化技术. 另一方面，GeST由于其组件的通用性还可以支持其他通用GPU算法的性能自动调优.

2.2 优化空间参数化

首先，本文需要对后续自动调优流水线的优化技术组合进行参数化. 表2以3D Stencil计算为例展示了参数优化空间，其中M_n为输入网格第n维的长度. GeST从1开始，以单位步长表示布尔类型参数（如useShared）和枚举类型参（SD）. 这种处理方式确保了计算变异系数时涉及到的除法操作的合法性. 与现有工作一致^[17]，GeST将数值参数的值限制为2的幂. 注意对参数进行分组时，GeST对数值操作执行lb运算以便计算变异系数的输入是连续的. 这保证了不同参数对的相关性的公平比较.

表 2 面向GPU平台的Stencil参数优化空间

Table 2. Parameterized Optimization Space of Stencil on GPU Platform

优化技术	参数	范围
线程块维度	TB_x, TB_y, TB_z	[1,1 024], [1,2 024], [1,64]
共享内存	useShared	{1,2}
固定内存	useConstant	{1,2}
流处理	useStreaming	{1,2}
流处理维度	SD	{1,2,3}
并发流处理	SB	[1,M_SD]
循环展开	UF_x, UF_y, UF_z	[1,M₁], [1,M₂], [1,M₃]
循环合并	CM_x, CM_y, CM_z	[1,M₁], [1,M₂], [1,M₃]
块合并	BM_x, BM_y, BM_z	[1,M₁], [1,M₂], [1,M₃]
重定时	useRetiming	{1,2}
预取	usePrefetching	{1,2}
时间分块	useTB	{1,2}

下载: 导出CSV

| 显示表格

除了表2中所示的参数范围外，优化参数之间还有一些显式约束. 例如，线程块大小（即TB_x×TB_y×TB_z）必须小于或等于1 024；TB和SB参数仅在启用流处理优化时有效；启用并发流时，流维度中的循环展开因子必须不大于SB. 即便考虑这些显式约束，总搜索空间仍包含超过1亿个参数设置. 此外，GPU的有限存储资源也带来了隐式约束. 例如，块合并和循环展开的参数设置受寄存器数量和共享内存大小的限制. GeST在生成搜索代码之前检查上述约束，以便在性能调优期间仅执行有效的参数设置.

2.3 参数分组

参数分组的原则是将强相关的参数置于同一组以方便后续的搜索空间采样过程. 如图3所示，考虑到Stencil计算的特性，GeST预先生成2个参数组（PG₀和PG₁），其中PG₀包含线程块维度，而PG₁包含循环合并和块合并的相关参数. 对于其他单独参数，GeST需要量化成对参数之间的相关性.

图 3 参数分组的工作流程

Figure 3. The workflow of parameter grouping

下载: 全尺寸图片幻灯片

$CV = \dfrac{\sigma }{\mu } = \dfrac{{\sqrt {\dfrac{1}{n}\displaystyle\sum\limits_{i = 1}^n {{{({x_i} - \bar x)}^2}} } }}{{\bar x}} .$

(1)

假设有N个单独参数，GeST每次在固定剩余N－2个参数时更改2个参数的设置. 以P₂和P₃为例，其取值范围分别为R₂和R₃. GeST从R₂中选择P₂的设置，最终得到在P₂固定下达到最佳性能的P₃设置列表（VS₂₃）. 需要注意的是，如果R₂中的某个设置不在Stencil数据集内，则应跳过该设置. 接下来，GeST计算VS₂₃的变异系数CV₂₃，如式（1）所示.

变异系数CV定义为标准差 $\sigma$ 与平均值 $\mu$ 的比值，在统计领域用于反映数据的离散程度，图3中较高的CV意味着较低的参数相关性. 通过重复上述过程，最终得到代表参数相关性的CV序列. 随后，GeST根据CV的升序将参数对推入双端队列Deque. GeST通过算法1来实现参数分组，其中输入是参数列表paraList、初始参数组initGroup、CV升序双端队列Deque和目标参数组数numGroups.

算法1. 基于双端队列的参数分组过程.

输入：参数列表 $paraList$ ，初始参数组 $initGroup$ ， $CV$ 升序双端队列 $Deque$ ，目标参数组数 $numGroups$ ；

输出：最终参数组 $paraGroup$ .

① $paraGroup,gCount \leftarrow initGroup,initGroup.size$ ;

② while $Deque.size > 0$ do

③ 　 $ftPara,bkPara = Deque.popright()$ ; /*右侧弹出*/

④ 　if $gCount < numGroups$ then

⑤ 　　if $ftPara$ in $paraGroup$ then

⑥ 　　　 $paraGroup.append([ftPara])$ ;

⑦ 　　　 $gCount \leftarrow gCount + 1$ ;

⑧ 　　end if

⑨ 　　if $bkPara$ in $paraGroup$ then

⑩ 　　　 $paraGroup.append([bkPara])$ ;

⑪ 　　　 $gCount \leftarrow gCount + 1$ ;

⑫ 　　end if

⑬ 　end if

⑭ 　if $gCount = = numGroups$ then

⑮ 　　 $break$ ;

⑯ 　end if

⑰ 　while $Deque.size > 0$ do

⑱ 　 $ftPara,bkPara = Deque.popleft()$ ; /*左侧弹出*/

⑲ 　if $ftPara$ in $paraGroup$ then

⑳ 　　if $bkPara$ not in $paraGroup$ then

㉑　　　 $paraGroup[ftIn].append(bkPara)$ ;

㉒　　end if

㉓　end if

㉔　if $bkPara$ in $paraGroup$ then

㉕　　if $ftPara$ not in $paraGroup$ then

㉖　　　 $paraGroup[bkIn].append(ftPara)$ ;

㉗　　end if

㉘　end if

㉙ end while

㉚ /*将剩余单独参数附加到最小规模的参数组*/

㉛ while $paraList.any()$ not in $paraGroup$ do

㉜　 $paraGroup[mSize].append(paraList[notIn])$ ;

㉝ end while

如算法1所示，GeST首先从Deque的右侧弹出参数对（第3行）. 如果某个参数不在已有的参数组中，则创建新的参数组存储该参数（第4~13行）. 当已有参数组数等于目标参数组数时，跳出该循环（第14~16行）. 接下来，GeST从Deque的左侧弹出参数对（第18行）. 如果仅有1个参数不在已有的参数组中，则将该参数合并到已有的参数组中（第19~28行）. 最后，GeST检查是否还有剩余的单独参数，并将这些参数附加到最小规模的参数组中（第31~33行），以保证参数组的规模平衡. 通过上述过程，GeST获得了针对特定Stencil计算的最终参数组.

2.4 搜索空间采样

GeST采用了一种简明但高效的搜索空间采样机制，无需大量离线分析来训练性能模型，这得益于其基于配额的奖励策略，如图4所示. 经过参数分组后，Stencil计算的搜索空间已大幅缩小，此时不适合使用遗传算法或模拟退化法等方法来解决优化问题. 例如，遗传算法需要庞大的种群来进行交叉和迁移，这意味着每次迭代都要测试大量的参数设置，对于小搜索空间而言代价过高，几轮迭代几乎等同于穷尽搜索. 若选择较小的种群规模，则会因个体数量过少而陷入局部最优. 因此，GeST在每次迭代中遍历参数组，并根据执行性能反馈动态调整采样比例，从而确保搜索过程沿着更优参数设置的方向进行.

图 4 基于配额的奖励策略

Figure 4. Quota-based reward policy

下载: 全尺寸图片幻灯片

算法2说明了基于奖励策略的搜索空间采样过程，其原则是增加能够带来性能提升的参数组的采样比例，以奖励它们的性能潜力. 首先，GeST根据每个参数组包含的组合数量来初始化每个参数组的采样比例. 在计算参数组的组合数量时，GeST会检查优化参数之间的显式约束. 接下来，GeST迭代地从参数组中采样设置，直到达到预定义的最大采样数量mSMP（第2行）. 具体来说，GeST在每次迭代之前重置奖励参数组列表upList和总采样比例totSR（第3行）. GeST遍历参数组，并从每个参数组的有效设置validSET中执行不放回的随机采样（第5~7行）. 有效设置是指满足约束条件且不与已采样设置重复的设置. 为了实现不放回的随机采样，GeST将每个参数设置编码为唯一的哈希值并存储在字典中，以便快速查找不重复的设置. 如果某个参数组采样到的设置表现优于当前最佳设置，则更新最佳设置，并将该参数组添加到upList中（第8~10行）.

算法2. 基于奖励策略的搜索空间采样过程.

输入：总参数设置 $totSET$ ，最佳参数设置 $optSET$ ，参数组 $paraGroup$ ，最大采样数量 $mSMP$ ，迭代采样数量 $iSMP$ ，采样比例 $SR$ ，调整比例 $AR$ ，最低比例 $LR$ ；

输出：采样参数设置字典 $sampledDict$ .

① $numGroups,numSMP \leftarrow paraGroup.size,0$ ;

② while $numSMP < = mSMP$ do

③ 　 $upList,totSR \leftarrow [],0$ ; /*重置奖励参数组列表*/

④ 　for $id$ in range $[1,numGroups]$ do

⑤ 　　/*从有效设置中执行不放回的随机采样*/

⑥ 　　 $validSET \leftarrow totSET(optSET[paraGrou{p_{id}}])$ ;

⑦ 　　 $iSET \leftarrow validSET.sample(iSMP \times S{R_{id}})$ ;

⑧ 　　if $iSET.isUpdate = =$ True then

⑨ 　　　 $upList.append(id)$ ;

⑩ 　　　 $optSET.update()$ ; /*更新最佳参数设置*/

⑪ 　　end if

⑫ 　　 $sampledDict.append(iSET)$ ; /*字典存储*/

⑬ 　　 $numSMP \leftarrow numSMP + iSET.size$ ;

⑭ 　end for

⑮ 　for $id$ in range $[1,numGroups]$ do

⑯ 　　if $id$ in $upList$ then

⑰ 　　　 $continue$ ; /*跳到下一个参数组*/

⑱ 　　end if

⑲ 　　if $S{R_{id}} > = LR + AR$ then

⑳ 　　　 $S{R_{id}} \leftarrow S{R_{id}} - AR$ ; /*降低采样比例*/

㉑　　　 $totSR \leftarrow totSR + S{R_{id}}$ ;

㉒　　end if

㉓　end for

㉔　for $id$ in $upList$ do

㉕　　/*将剩余的比例配额均分给奖励参数组*/

㉖　　 $S{R_{id}} \leftarrow (1 - totSR)/upList.size()$ ;

㉗　end for

㉘ end while

GeST将奖励参数组的设置限制在单次迭代内，而不是在整个循环内进行管理，以避免某个参数组由于在早期表现突出而主导采样过程. GeST根据奖励结果调整每个参数组的采样比例. 具体来说，将其他参数组的采样比例减去固定的调整比例AR，然后将剩余的采样比例配额均分给奖励参数组（第15~27行）. 由于最优参数设置往往被较差的设置包围^[26]，最优参数设置也可能由平均表现平庸的参数组所决定. 为此，GeST为每个参数组的采样比例设置了下限（LR），以确保在之前迭代中没有突出表现的参数组仍有机会获得奖励，从而进行“反击”. 基于配额的奖励策略实现了对Stencil优化空间的全局探索，在保证搜索广度的同时提高了采样质量.

3. 实验与结果分析

3.1 实验设置

1）硬件平台和Stencil程序：如表3所示，本文在1台配备Intel Xeon E5-2680 v4 CPU和2块NVIDIA Tesla V100 GPU的服务器上进行评测. 实验运行在Ubuntu 16.04操作系统上，使用的编译器为GCC v7.5和NVCC v10.1. 本文选取了21个典型Stencil程序用于实验测试，这些程序涵盖了不同的阶数、维度和形状. 本文将2D和3D Stencil程序的输入网格大小分别设置为8 192²和512³.

表 3 硬件规格

Table 3. Hardware Specifications

	CPU	GPU
型号	Intel Xeon E5-2680 v4	NVIDIA Tesla V100
频率/GHz	2.4	1.5
核心	28	13 440 (80 SMs)
缓存	32 KB L1, 256KB L2, 35 MB L3	6 MB L2
内存	378 GB DDR4	32 GB HBM2
带宽/GBps	76.8	900

下载: 导出CSV

| 显示表格

2）搜索方法和实现细节：本文将GeST与5种流行的参数调优方法进行比较，包括GSTuner^[11]，AN5D^[9]，Artemis^[6]，OpenTuner^[21]，RandSearch. RandSearch在参数搜索空间中进行不放回随机采样，并在每次采样后更新最佳参数设置. GSTuner通过训练后的回归模型指导搜索空间采样，采样比例设置为10%. 对于GeST和GSTuner，AR和LR均设置为0.1. 为了支持全局优化探索，本文将AN5D，Artemis，OpenTuner的参数设置预处理为零填充格式. GSTuner和OpenTuner均采用遗传算法，其具有2个子种群，每个子种群包含16个个体；交叉率和突变率分别设置为0.8和0.005.

3）对比指标：衡量参数调优有效性的关键指标是找到最佳设置所需的时间. 因此，本文将GeST与上述方法进行等时搜索质量的比较，即所有方法都在固定的时间（100 s）内运行. 等时比较能够充分验证调优过程的收敛性. 为了降低随机性的影响，本文将每种方法运行10次并给出平均结果.

3.2 自动调优性能

图5显示了不同参数调优方法在典型Stencil计算模式的等时比较，其中横轴表示搜索时间，纵轴表示Stencil计算的最短执行时间. 需要注意的是，对于GeST，图5中已包含获取Stencil数据集所需的时间. 如图5所示，GeST的收敛速度相对较快，能够在短时间内找到高性能的参数设置. 这表明GeST的奖励策略确保了参数组中采样设置的高质量. 尽管Artemis的固定参数组同样显著降低了搜索空间，但其激进的分组策略使其难以捕捉到高性能的设置. 相比之下，OpenTuner和RandSearch缺乏降低搜索空间的机制，因此在短时间内无法实现收敛.

图 5 V100 GPU上典型Stencil模式的调优效率对比

Figure 5. Auto-tuning efficiency comparison of typical Stencil patterns on V100 GPU

下载: 全尺寸图片幻灯片

图6显示了几种参数调优方法相对于RandSearch的归一化等时性能. 从图6中可以看出，GeST在大多数Stencil计算模式下表现最佳，其最佳比例达到71.4%. 在等时评估中，GeST相对于GSTuner，AN5D，Artemis，OpenTuner，RandSearch的平均加速比分别为1.1倍、3.3倍、1.6倍、1.5倍、1.8倍. 这证明GeST采用的参数分组策略和搜索空间采样机制能够有效地推广到各种Stencil计算模式. 相比之下，AN5D和Artemis的性能不稳定；这是因为AN5D的激进参数范围缩减和Artemis的基于经验的分层调优都难以全面覆盖高性能设置. 例如，在box3d2r下，Artemis的最终执行时间甚至是GeST的2.9倍. OpenTuner由于种群规模较小，容易陷入局部最优. 选择较小的种群规模是为了充分利用遗传算法，否则在短时间内迭代次数太少则更接近于随机搜索. RandSearch具有很强的随机性，缺乏沿执行时间降低方向的指导性搜索，平均结果未能体现出良好的性能表现. 尽管GSTuner的性能接近GeST，但其需要训练回归模型来指导采样过程，而收集训练数据的离线分析成本较高. 总之，与其他参数调优方法相比，GeST能够以更快的速度识别到更优的参数设置.

图 6 V100 GPU上的参数调优性能对比

Figure 6. Auto-tuning performance comparison of parameter on V100 GPU

下载: 全尺寸图片幻灯片

3.3 其他硬件架构

为了证明GeST方法的通用性，本文在配备2块NVIDIA Tesla A100 GPU的平台上进行实验评估. 具体来说，本文在新的硬件架构上重新采用几种参数调优方法来搜索高性能配置. 图7显示了在A100 GPU上归一化为RandSearch的等时性能. 结果表明，对于大多数Stencil，GeST的表现优于其他参数调优方法. GeST在61.9%的情况下表现最佳，而GSTuner和Artemis的最佳表现比例为28.6%和9.5%. 此外，GeST相对于GSTuner，AN5D，Artemis，OpenTuner，RandSearch分别实现了1.0倍、3.3倍、2.2倍、1.3倍、1.5倍的加速比. GSTuner和GeST在平均性能上接近，但在某些情况（如box2d2r和cross3d1r）下存在较大差异，可根据不同场景灵活选择使用. GeST在box2d3r下分别比AN5D和Artemis快了6.9倍和6.7倍，这是因为激进的搜索空间剪枝导致性能不稳定. OpenTuner由于优化空间较大，往往陷入局部最优. RandSearch在极少数情况（如box3d2r）下与GeST性能相当，但在其他情况下明显不如GeST. 需要注意的是，参数分组算法和基于奖励的采样策略无需离线性能分析和模型训练，因此GeST能够灵活应用于各种硬件平台并且保持稳定的参数调优质量.

图 7 A100 GPU上的参数调优性能对比

Figure 7. Auto-tuning performance comparison of parameter on A100 GPU

下载: 全尺寸图片幻灯片

3.4 其他网格大小

考虑到不同场景下Stencil计算的网格大小可能会有所区别，本文探讨了GeST参数调优组件在其他网格大小下的适配性. 本文随机选取了6个Stencil计算模式，其中2D网格大小设置为2 048²和4 096²，3D网格大小设置为128³和256³. 图8显示了不同网格大小下的参数调优性能对比，纵轴表示归一化为RandSearch的时间. 从图8中可以看出，GeST在大多数Stencil下表现优于其他参数调优方法. 具体来说，对于2 048²和128³的输入网格，GeST相比GSTuner，AN5D，Artemis，OpenTuner，RandSearch分别取得了1.3倍、2.7倍、1.4倍、1.6倍、1.8倍的加速比. 而对于4 096²和256³的输入网格，GeST的加速比分别为1.1倍、2.9倍、1.6倍、1.6倍、1.9倍. 结果表明，无论网格大小如何变化，GeST都能够很好地适应不同的搜索空间范围，并体现卓越的参数调优性能，而无需对框架组件进行额外调整.

图 8 其他网格大小下的参数调优性能对比

Figure 8. Auto-tuning performance comparison of parameter under other grid sizes

下载: 全尺寸图片幻灯片

3.5 参数敏感性分析

1）Stencil数据集规模：图9显示了不同Stencil数据集规模的参数调优性能对比，纵轴表示归一化为RandSearch的时间. sd_X指代Stencil数据集共有X个实例. 如图9所示，GeST在所有情况下的表现均优于RandSearch. 值得注意的是，GeST在收集Stencil数据集时，其过程实际上是随机搜索，因此这样的结果充分证明了基于配额的奖励策略能够使GeST快速地向性能更优的设置收敛. 整体来看，sd_10在超过半数情况（52.4%）下表现最差. 这表明GeST需要一定规模的Stencil数据集才能实现合理的参数分组. 另一方面，sd_15的表现相对sd_20更为稳定，在42.9%的情况下表现最佳. 因此，应将Stencil数据集规模控制在合理范围（如15~20个实例），以便在限定时间内迭代更多搜索步骤以提升最终性能.

图 9 不同Stencil数据集规模的参数调优性能对比

Figure 9. Auto-tuning performance comparison of parameter with different stencil dataset sizes

下载: 全尺寸图片幻灯片

2）参数组数量：图10显示了不同参数组数量的参数调优性能对比，其中pg_X指代GeST设置了X个参数组. 如图10所示，GeST在大多数情况下的表现优于RandSearch. 整体来看，pg_3在52.4%的情况下表现最差. 这是因为足够多的参数组才能进行细粒度的采样比例调整，以充分挖掘每个参数的性能潜力. pg_6的性能极其不稳定，在box2d1r下甚至比RandSearch更差. 原因在于，当设置的参数组过多时，性能影响相近的参数可能会被置于不同组，无法发挥参数联合调优的快速性能提升优势. pg_4和pg_5的性能表现相对稳定，但pg_5的表现更为出色，在47.6%的情况下取得最佳表现. 鉴于参数组数量是影响调优效率的关键因素，针对未来Stencil计算中可能涉及到的更多优化参数，可以根据实际需求灵活调整参数组数量，从而平衡搜索范围和搜索速度.

图 10 不同参数组数量的自动调优性能对比

Figure 10. Auto-tuning performance comparison with different numbers of parameter groups

下载: 全尺寸图片幻灯片

3.6 开销分析

GeST的处理开销可划分为参数分组和搜索空间采样2部分. 参数分组开销主要包括基于变异系数计算的相关性量化和基于双端队列结构的分组算法. 搜索空间采样开销则涉及基于奖励策略的参数设置选择和基于哈希编码与字典结构的设置去重存储. 需要注意的是，GeST的处理开销已纳入固定时间的实验评估中. 图11显示了处理开销在整个参数调优流水线时间中的归一化结果. 如图11所示，处理开销几乎可以忽略不计，平均只占参数调优流水线的0.97‱. 这意味着参数调优的大部分时间都花在启动和执行Stencil计算上. 由于GeST的轻量级和通用特性，它能够高效地对大规模Stencil应用中的多样化计算进行批量调优，从而提升整个应用的性能.

图 11 处理开销的时间分解

Figure 11. Time breakdown of processing overhead

下载: 全尺寸图片幻灯片

4. 相关工作

4.1 Stencil领域特定语言

基于Stencil计算的常规模式，研究工作将优化技术集成到DSL中来实现自动代码转换. PATUS^[27]允许用户通过类C的语法定义Stencil并选择预定义和自定义的优化策略. Physis^[28]将用户编写的Stencil代码转换为GPU集群的可扩展实现. Forma^[4]提出DSL专用于具有Stencil操作的图像处理应用. Grosser等人将^[7]六边形分块和wavefront分块在GPU上相结合以实现混合分块方法. Hagedorn等人^[5]使用LIFT原语来实现Stencil代码和优化技术. Rawat等人^[29]使用有向无环图进行阻塞、流式传输和资源管理来优化性能. StencilFlow^[30]提供从高级程序描述到分布式硬件的端到端分析和映射. 曹杭等人^[31]以“自然块”的新概念标识不同形状的特征并针对星型Stencil设计2层密铺方案. Bisbas等人^[32]实现由MLIR方言组成的编译组件以用于在分布式Stencil计算中进行信息传递. 上述工作普遍缺乏对性能自动调优的有效支持，而GeST能够集成到DSL中以确定目标优化组合的最佳设置，且无需引入离线成本.

4.2 GPU性能自动调优

由于识别最佳内核变体对于程序员或代码生成器来说极具挑战性，大量研究致力于通过自动调优技术来最大化GPU程序的性能. 孙相征等人^[33]设计对角线稀疏存储格式并根据应用矩阵的特点进行自适应SpMV性能优化. Li等人^[34]预先计算临界点并选择全局最优来解决并发性和寄存器使用之间的冲突. Pfaffe等人^[35]将分层在线自动调优与多面体并行化相结合以降低搜索复杂度并提高收敛速度. Ansor^[36]对优化组合进行采样并利用进化搜索和成本模型来精调张量程序. LLAMA^[37]通过动态运行基于成本的优化器并配置单独的操作调用来遍历空间. GTuner^[38]通过图注意网络共同学习结构和统计特征以找到最佳的代码实现. 曹坤等人^[39]提取OpenCL应用的特性并基于改进交叉熵策略的调度技术以提高设计点寻优效率. PARALiA^[40]通过硬件抽象来优化通信并利用自动调优和性能建模来提高BLAS例程的性能. PrecTuner^[41]整合混合精度代码生成器和自动调优器以预测定义参数的最佳性能值. Li等人^[42]提出基于分析特征的机器学习预测模型和动态梯度下降搜索策略来降低自动调优时间. 上述工作能够用于优化Stencil计算，而GeST因其轻量级的全局搜索机制也可灵活扩展到其他目标程序.

5. 结束语

本文提出了一种面向通用Stencil计算的性能自动调优框架GeST. 首先，GeST通过随机搜索获取Stencil数据集，基于变异系数指标量化参数之间的相关性，从双端队列弹出参数对来生成参数组. 之后，GeST利用基于配额的奖励策略来指导参数组的迭代搜索，并通过哈希编码和字典存储来避免冗余设置采样. 实验结果表明，与当前最先进的方案相比，GeST能够在更短时间内识别到高质量的参数设置.

未来的工作包括以下3个方面：1）将GeST应用于Stencil计算的其他硬件环境，例如分布式异构系统和边缘计算设备；2）将GeST扩展到拥有更大搜索空间的应用领域，例如深度学习中的张量优化；3）针对GPU上的Stencil计算，建立分析模型以指导性能优化并明确性能上界. 为了实现上述目标，需要对GeST的方法和框架进行充分解耦并形成插件化的设计，使其能够快速嵌入目标场景，实现非侵入式的参数自动调优. 在此基础上，构建Roofline模型以深入分析性能瓶颈，并评估不同优化策略在各种Stencil模式下所能达到的性能极限.

作者贡献声明：孙庆骁提出了算法思路和实验方案；完成实验方案并撰写论文；杨海龙提出了指导意见并修改论文.

图 1 GPU基础硬件架构

Figure 1. Basic hardware architecture of GPU

下载: 全尺寸图片幻灯片

图 2 GeST框架的设计概要

Figure 2. The design overview of GeST framework

下载: 全尺寸图片幻灯片

图 3 参数分组的工作流程

Figure 3. The workflow of parameter grouping

下载: 全尺寸图片幻灯片

图 4 基于配额的奖励策略

Figure 4. Quota-based reward policy

下载: 全尺寸图片幻灯片

图 5 V100 GPU上典型Stencil模式的调优效率对比

Figure 5. Auto-tuning efficiency comparison of typical Stencil patterns on V100 GPU

下载: 全尺寸图片幻灯片

图 6 V100 GPU上的参数调优性能对比

Figure 6. Auto-tuning performance comparison of parameter on V100 GPU

下载: 全尺寸图片幻灯片

图 7 A100 GPU上的参数调优性能对比

Figure 7. Auto-tuning performance comparison of parameter on A100 GPU

下载: 全尺寸图片幻灯片

图 8 其他网格大小下的参数调优性能对比

Figure 8. Auto-tuning performance comparison of parameter under other grid sizes

下载: 全尺寸图片幻灯片

图 9 不同Stencil数据集规模的参数调优性能对比

Figure 9. Auto-tuning performance comparison of parameter with different stencil dataset sizes

下载: 全尺寸图片幻灯片

图 10 不同参数组数量的自动调优性能对比

Figure 10. Auto-tuning performance comparison with different numbers of parameter groups

下载: 全尺寸图片幻灯片

图 11 处理开销的时间分解

Figure 11. Time breakdown of processing overhead

下载: 全尺寸图片幻灯片

表 1 面向GPU平台的Stencil性能优化技术

Table 1 Stencil Performance Optimizations Technology on GPU Platforms

优化技术	简称	约束
流处理（streaming）	ST	—
块合并（block merging）	BM	启用CM时无效
循环合并（cyclic merging）	CM	启用BM时无效
重定时（retiming）	RT	仅在启用ST时有效
预取（prefetching）	PR	仅在启用ST时有效
时间分块（temporal blocking）	TL	—
“—”表示没有约束.

下载: 导出CSV

表 2 面向GPU平台的Stencil参数优化空间

Table 2 Parameterized Optimization Space of Stencil on GPU Platform

优化技术	参数	范围
线程块维度	TB_x, TB_y, TB_z	[1,1 024], [1,2 024], [1,64]
共享内存	useShared	{1,2}
固定内存	useConstant	{1,2}
流处理	useStreaming	{1,2}
流处理维度	SD	{1,2,3}
并发流处理	SB	[1,M_SD]
循环展开	UF_x, UF_y, UF_z	[1,M₁], [1,M₂], [1,M₃]
循环合并	CM_x, CM_y, CM_z	[1,M₁], [1,M₂], [1,M₃]
块合并	BM_x, BM_y, BM_z	[1,M₁], [1,M₂], [1,M₃]
重定时	useRetiming	{1,2}
预取	usePrefetching	{1,2}
时间分块	useTB	{1,2}

下载: 导出CSV

表 3 硬件规格

Table 3 Hardware Specifications

	CPU	GPU
型号	Intel Xeon E5-2680 v4	NVIDIA Tesla V100
频率/GHz	2.4	1.5
核心	28	13 440 (80 SMs)
缓存	32 KB L1, 256KB L2, 35 MB L3	6 MB L2
内存	378 GB DDR4	32 GB HBM2
带宽/GBps	76.8	900

下载: 导出CSV

参考文献(42)

[1]	Mullapudi R T, Vasista V, Bondhugula U. PolyMage: Automatic optimization for image processing pipelines [C] //Proc of the 20th Int Conf on Architectural Support for Programming Languages and Operating Systems. New York: ACM, 2015: 429−443
[2]	Gamell M, Teranishi K, Heroux M A, et al. Local recovery and failure masking for stencil-based applications at extreme scales [C/OL] //Proc of the 27th Int Conf for High Performance Computing, Networking, Storage and Analysis. New York: ACM, 2015 [2024-07-15]. https://dl.acm.org/doi/abs/10.1145/2807591.2807672
[3]	Sano K, Hatsuda Y, Yamamoto S. Multi-FPGA accelerator for scalable stencil computation with constant memory bandwidth[J]. IEEE Transactions on Parallel and Distributed Systems, 2013, 25(3): 695−705
[4]	Ravishankar M, Holewinski J, Grover V. Forma: A DSL for image processing applications to target GPUs and multi-core CPUs [C] //Proc of the 8th Workshop on General Purpose Processing using GPUs. New York: ACM, 2015: 109−120
[5]	Hagedorn B, Stoltzfus L, Steuwer M, et al. High performance stencil code generation with LIFT [C] //Proc of the 16th ACM/IEEE Int Symp on Code Generation and Optimization. New York: ACM, 2018: 100−112
[6]	Rawat P S, Vaidya M, Sukumaran-Rajam A, et al. On optimizing complex stencils on GPUs [C] //Proc of the 33rd IEEE Int Parallel and Distributed Processing Symp. Piscataway, NJ: IEEE, 2019: 641–652
[7]	Grosser T, Cohen A, Holewinski J, et al. Hybrid hexagonal/classical tiling for GPUs [C] //Proc of the 12th ACM/IEEE Int Symp on Code Generation and Optimization. New York: ACM, 2014: 66−75
[8]	Ragan-Kelley J, Barnes C, Adams A, et al. Halide: A language and compiler for optimizing parallelism, locality, and recomputation in image processing pipelines[J]. ACM SIGPLAN Notices, 2013, 48(6): 519−530 doi: 10.1145/2499370.2462176
[9]	Matsumura K, Zohouri H R, Wahib M, et al. AN5D: Automated stencil framework for high-degree temporal blocking on GPUs [C] //Proc of the 18th ACM/IEEE Int Symp on Code Generation and Optimization. New York: ACM, 2020: 199–211
[10]	Sun Qingxiao, Liu Yi, Yang Hailong, et al. csTuner: Scalable auto-tuning framework for complex stencil computation on GPUs [C] //Proc of the 23rd IEEE Int Conf on Cluster Computing. Piscataway, NJ: IEEE, 2021: 192−203
[11]	Sun Qingxiao, Liu Yi, Yang Hailong, et al. Adaptive auto-tuning framework for global exploration of stencil optimization on GPUs[J]. IEEE Transactions on Parallel and Distributed Systems, 2024, 35(1): 20−33 doi: 10.1109/TPDS.2023.3325630
[12]	Sun Qingxiao, Liu Yi, Yang Hailong, et al. QoS-aware dynamic resource allocation with improved utilization and energy efficiency on GPU[J]. Parallel Computing, 2022, 113: 102958 doi: 10.1016/j.parco.2022.102958
[13]	Rawat P S, Rastello F, Sukumaran-Rajam A, et al. Register optimizations for stencils on GPUs [C] //Proc of the 23rd ACM SIGPLAN Symp on Principles and Practice of Parallel Programming. New York: ACM, 2018: 168−182
[14]	Sun Qingxiao, Liu Yi, Yang Hailong, et al. StencilMART: Predicting optimization selection for stencil computations across GPUs [C] //Proc of the 36th IEEE Int Parallel and Distributed Processing Symp. Piscataway, NJ: IEEE, 2022: 875–885
[15]	Yuan Liang, Cao Hang, Zhang Yunquan, et al. Temporal vectorization for stencils [C/OL] //Proc of the 33rd Int Conf for High Performance Computing, Networking, Storage and Analysis. New York: ACM, 2021 [2024-07-15]. https://dl.acm.org/doi/abs/10.1145/3458817.3476149
[16]	Li Kun, Yuan Liang, Zhang Yunquan, et al. Reducing redundancy in data organization and arithmetic calculation for stencil computations [C/OL] //Proc of the 33rd Int Conf for High Performance Computing, Networking, Storage and Analysis. New York: ACM, 2021 [2024-07-15]. https://dl.acm.org/doi/abs/10.1145/3458817.3476154
[17]	Garvey J D, Abdelrahman T S. Automatic performance tuning of stencil computations on GPUs [C] //Proc of the 44th Int Conf on Parallel Processing. Piscataway, NJ: IEEE, 2015: 300−309
[18]	Stock K, Kong M, Grosser T, et al. A framework for enhancing data reuse via associative reordering [C] //Proc of the 35th ACM SIGPLAN Conf on Programming Language Design and Implementation. New York: ACM, 2014: 65−76
[19]	Oh C, Zheng Zhen, Shen Xipeng, et al. GoPipe: A granularity-oblivious programming framework for pipelined stencil executions on GPU [C] //Proc of the 29th Int Conf on Parallel Architectures and Compilation Techniques. New York: ACM, 2020: 43−54
[20]	Luo Yulong, Tan Guangming, Mo Zeyao, et al. FAST: A fast stencil autotuning framework based on an optimal solution space model [C] //Proc of the 29th Int Conf on Supercomputing. New York: ACM, 2015: 187−196
[21]	Ansel J, Kamil S, Veeramachaneni K, J. Ragan-Kelley, et al. OpenTuner: An extensible framework for program autotuning [C] //Proc of the 23rd Int Conf on Parallel Architectures and Compilation Techniques. New York: ACM, 2014: 303−316
[22]	Trümper L, Ben-Nun T, Schaad P, et al. Performance embeddings: A similarity-based transfer tuning approach to performance optimization [C] //Proc of the 37th Int Conf on Supercomputing. New York: ACM, 2023: 50−62
[23]	Martínez V, Dupros F, Castro M, et al. Performance improvement of stencil computations for multi-core architectures based on machine learning[J]. Procedia Computer Science, 2017, 108: 305−314 doi: 10.1016/j.procs.2017.05.164
[24]	Cosenza B, Durillo J J, Ermon S, et al. Autotuning stencil computations with structural ordinal regression learning [C] //Proc of the 31st IEEE Int Parallel and Distributed Processing Symp. Piscataway, NJ: IEEE, 2017: 287−296
[25]	Nesterenko B, Yi Qing, Lin Pei-Hung, et al. Modeling optimization of stencil computations via domain-level properties [C] //Proc of the 13th Int Workshop on Programming Models and Applications for Multicores and Manycores. New York: ACM, 2022: 35−44
[26]	Roy R B, Patel T, Gadepally V, et al. BLISS: Auto-tuning complex applications using a pool of diverse lightweight learning models [C] //Proc of the 42nd ACM SIGPLAN Int Conf on Programming Language Design and Implementation. New York: ACM, 2021: 1280−1295
[27]	Christen M, Schenk O, Burkhart H. PATUS: A code generation and autotuning framework for parallel iterative stencil computations on modern microarchitectures [C] //Proc of the 25th IEEE Int Parallel and Distributed Processing Symp. Piscataway, NJ: IEEE, 2011: 676−687
[28]	Maruyama N, Nomura T, Sato K, et al. Physis: An implicitly parallel programming model for stencil computations on large-scale GPU-accelerated supercomputers [C/OL] //Proc of the 23rd Int Conf for High Performance Computing, Networking, Storage and Analysis. New York: ACM, 2011 [2024-07-15]. https://dl.acm.org/doi/abs/10.1145/2063384.2063398
[29]	Rawat P S, Vaidya M, Sukumaran-Rajam A, et al. Domain-specific optimization and generation of high-performance GPU code for stencil computations[J]. Proceedings of the IEEE, 2018, 106(11): 1902−1920 doi: 10.1109/JPROC.2018.2862896
[30]	de Fine Licht J, Kuster A, De Matteis T, et al. StencilFlow: Mapping large stencil programs to distributed spatial computing systems [C] //Proc of the 19th IEEE/ACM Int Symp on Code Generation and Optimization. Piscataway, NJ: IEEE, 2021: 315−326
[31]	曹杭,袁良,黄珊,等. 一种基于空间密铺的星型Stencil并行算法[J]. 计算机研究与发展,2020,57(12):2621−2634 doi: 10.7544/issn1000-1239.2020.20190734 Cao Hang, Yuan Liang, Huang Shan, et al. A parallel star stencil algorithm based on tessellating[J]. Journal of Computer Research and Development, 2020, 57(12): 2621−2634 (in Chinese) doi: 10.7544/issn1000-1239.2020.20190734
[32]	Bisbas G, Lydike A, Bauer E, et al. A shared compilation stack for distributed-memory parallelism in stencil DSLs [C] //Proc of the 29th ACM Int Conf on Architectural Support for Programming Languages and Operating Systems. New York: ACM, 2024: 38−56
[33]	孙相征,张云泉,王婷,等. 对角线稀疏矩阵的SpMV自适应性能优化[J]. 计算机研究与发展,2013,50(3):648−656 doi: 10.7544/issn1000-1239.2013.20110104 Sun Xiangzheng, Zhang Yunquan, Wang Ting, et al. Auto-tuning of SpMV for diagonal sparse matrices[J]. Journal of Computer Research and Development, 2013, 50(3): 648−656 (in Chinese) doi: 10.7544/issn1000-1239.2013.20110104
[34]	Li Ang, Song S L, Kumar A, et al. Critical points based register-concurrency autotuning for GPUs [C] //Proc of the 53rd Design, Automation & Test in Europe Conf & Exhibition. Piscataway, NJ: IEEE, 2016: 1273−1278
[35]	Pfaffe P, Grosser T, Tillmann M. Efficient hierarchical online-autotuning: A case study on polyhedral accelerator mapping [C] //Proc of the 33rd Int Conf on Supercomputing. New York: ACM, 2019: 354−366
[36]	Zheng Lianmin, Jia Chengfan, Sun Minmin, et al. Ansor: Generating high-performance tensor programs for deep learning [C] //Proc of the 14th USENIX Symp on Operating Systems Design and Implementation. Berkeley, CA: USENIX Association, 2020: 863−879
[37]	Romero F, Zhao M, Yadwadkar N J, et al. LLAMA: A heterogeneous & serverless framework for auto-tuning video analytics pipelines [C/OL] //Proc of the 12th ACM Symp on Cloud Computing. New York: ACM, 2021 [2024-07-15]. https://dl.acm.org/doi/abs/10.1145/3472883.3486972
[38]	Sun Qi, Zhang Xinyun, Geng Hao, et al. GTuner: Tuning DNN computations on GPU via graph attention network [C] //Proc of the 59th ACM/IEEE Design Automation Conf. New York: ACM, 2022: 1045−1050
[39]	曹坤,龙赛琴,李哲涛. CPU-GPU MPSoC中使用寿命驱动的OpenCL应用调度方法[J]. 计算机研究与发展,2023,60(5):976−991 doi: 10.7544/issn1000-1239.202220700 Cao Kun, Long Saiqin, Li Zhetao. Lifetime-driven OpenCL application scheduling on CPU-GPU MPSoC[J]. Journal of Computer Research and Development, 2023, 60(5): 976−991 (in Chinese) doi: 10.7544/issn1000-1239.202220700
[40]	Anastasiadis P, Papadopoulou N, Goumas G, et al. PARALiA: A performance aware runtime for auto-tuning linear algebra on heterogeneous systems[J]. ACM Transactions on Architecture and Code Optimization, 2023, 20(4): 1−25
[41]	Xu Jinchen, Song Guanghui, Zhou Bei, et al. A holistic approach to automatic mixed-precision code generation and tuning for affine programs [C] //Proc of the 29th ACM SIGPLAN Annual Symp on Principles and Practice of Parallel Programming. New York: ACM, 2024: 55−67
[42]	Li Chendi, Xu Yufan, Saravani S M, et al. Accelerated auto-tuning of GPU kernels for tensor computations [C] //Proc of the 38th ACM Int Conf on Supercomputing. New York: ACM, 2024: 549−561