DARM: Control-Flow Melding for SIMT Thread Divergence Reduction

文章标题：DARM: 用于减少SIMT线程分歧的控制流融合技术
作者/机构：Charitha Saumya, Kirshanthan Sundararajah, and Milind Kulkarni, 普渡大学电子与计算机工程学院

A1 主要贡献

本文旨在解决通用图形处理器（GPGPU）中因单指令多线程（SIMT）执行模型导致的控制流分歧性能下降问题。

核心问题：在GPGPU中，一组线程（warp或wavefront）以锁步方式执行指令。当遇到分支指令时，如果warp内的线程走向不同路径，就会发生控制流分歧。这导致分支的两条路径必须串行执行，从而降低了SIMD单元的利用率和程序性能。
研究目标：提出一种纯软件的编译器方法，通过利用分歧路径中控制流结构和指令序列的相似性，来减少控制流分歧。这种方法被称为“控制流融合”（control-flow melding）。
创新点与主要贡献：
1. 提出DARM (Divergence-Aware-Region-Melder)：一个实现了控制流融合思想的编译器分析与转换框架。DARM能够识别分歧的if-then-else区域中具有融合价值的机会，并利用分层序列对齐方法，将这些区域进行融合以减少控制流分歧。与现有技术（如尾部合并和分支融合）相比，DARM能够处理更复杂的控制流结构，而不仅限于简单的菱形结构（见表I）。
2. 在LLVM中实现DARM：该实现可应用于以HIP或CUDA编写的GPGPU程序，并且代码已公开发布。
3. 全面的评估：通过在一系列合成GPU程序和真实世界的GPU应用上进行评估，证明了DARM在减少控制流分歧性能下降方面的有效性。

A3 背景知识

GPGPU架构与编程模型

现代GPGPU架构：现代GPGPU包含多个处理核心，每个核心内有多个并行通道（SIMD单元）、一个向量寄存器文件和一块共享内存。执行的基本单位是warp（或wavefront），它是一组在SIMD单元上锁步执行的线程。共享内存由在同一核心上执行的warp共享。分支单元通过维护一个SIMT栈来处理控制流分歧，强制执行基于立即后支配节点（IPDOM）的重收敛。

编程模型与SIMT执行：像CUDA【索引8，CUDA C++ Programming Guide，https://docs.nvidia.com/cuda/cuda-c-programming-guide/index.html】或HIP【索引7 ，HIP Programming Guide v4.1，https://rocmdocs.amd.com/en/latest/】这样的GPGPU编程抽象，为开发者提供了数据并行与独立线程的编程假象。然而，在实际执行中，一组程序实例（即线程）被映射到一个warp中并以锁步方式执行。因此，SPMD（单程序多数据）程序中的控制流分歧由于SIMT执行的限制，对性能是有害的。

LLVM SSA形式与GPU分歧分析

LLVM与LLVM-IR：LLVM【索引6，Llvm: a compilation framework for lifelong program analysis transformation，2004，International Symposium on Code Generation and Optimization】是一个用于构建编译器、优化和代码生成器的通用框架。大多数广泛采用的GPGPU编译器都建立在LLVM基础设施之上。LLVM使用一种与目标无关的中间表示（LLVM-IR），这使得实现可移植的编译器优化成为可能。LLVM-IR采用静态单赋值（SSA）形式【索引11，Efficiently computing static single assignment form and the control dependence graph，1991，ACM Trans. Program. Lang. Syst.，https://doi.org/10.1145/115372.115320】，要求每个程序变量只被赋值一次，并在使用前被定义。SSA形式使用φ节点来解决存在分支时的数据流问题，选择在不同路径的汇合点应使用哪个定义。

分歧分析：在GPGPU编译器中，识别分歧控制流区域的关键步骤是执行编译器分析以识别分歧变量（或分支）【索引5，Divergence analysis and optimizations，2011，International Conference on Parallel Architectures and Compilation Techniques】【索引12，Improving performance of opencl on cpus，2012，Compiler Construction】。如果分支条件对于一个warp中的不同线程计算出非一致的值，则该分支是分歧的。如果分支条件是分歧的，warp中的线程将不得不在该点上走不同的控制流路径。LLVM的分歧分析将一个分支标记为分歧，如果其分支条件依赖于一个分歧变量（如线程ID）的数据或同步【索引12，Improving performance of opencl on cpus，2012，Compiler Construction】，尽管已有更复杂的分歧分析方法被提出【索引13，An abstract interpretation for spmd divergence on reducible control flow graphs，2021，Proc. ACM Program. Lang.】。

A3 关键Observation与设计原则

激励示例：Bitonic Sort

Bitonic Sort内核分析：Bitonic sort是许多并行排序算法中使用的核心组件，例如bitonic merge sort和Cederman的快速排序【索引14，Sorting networks and their applications，1968，spring joint computer conference】【索引15，Gpu-quicksort: A practical quicksort algorithm for graphics processors，2010，ACM J. Exp. Algorithmics】。图1展示了一个CUDA实现的bitonic sort，该内核是本文描述DARM控制流融合算法的运行示例。

_global__ static void bitonicSort(int *values) {   
2 // copy data from global memory to shared memor   
3 _syncthreads();   
4 for (unsigned int k = 2; k <= NUM; k *= 2) {   
5 for (unsigned int j = k / 2; j > 0; j /= 2) {   
6 unsigned int ixj = tid ^ j;   
7 if (ixj > tid) {   
8 if ((tid & k) == 0) {   
9 if (shared[ixj] < shared[tid])   
10 swap(shared[tid], shared[ixj]);   
11 }   
12 else {   
13 if ( shared[ixj] > shared[tid])   
14 swap(shared[tid], shared[ixj]);   
15 }   
16 }   
17 _syncthreads();   
18 }   
19 } // write data back to global memory   
20 }

图1. Bitonic Sort的CUDA实现

分歧点与融合机会：在该内核中，第8行的分支条件依赖于线程ID，因此是分歧的。由于该分歧分支位于循环内部，分支两侧的执行需要多次序列化，导致严重的控制流分歧。然而，该分歧分支的if部分（第9-10行）和else部分（第13-14行）的代码在两方面是相似的：首先，两个代码段具有相同的控制流结构（即一个if-then分支）；其次，两条路径上的指令也很相似，都是比较共享数组中的两个元素并执行交换操作。因此，if和else部分的内容可以被融合以减少控制流分歧。两个代码段都包含共享内存的加载和存储操作，在未融合的代码中，这些操作由于线程分歧必须序列化执行。然而，如果这两个部分被融合，线程可以在同一个周期内发出内存指令，从而提高性能。

现有技术的局限性：现有的编译器优化如尾部合并（tail merging）和分支融合（branch fusion）无法应用于此案例。尾部合并仅适用于两个基本块有共同目标且尾部有相同指令序列的情况，但bitonic sort中的if和then部分包含多个基本块，编译器无法应用尾部合并。同样，分支融合要求菱形的控制流，并且如果分支的if和else部分包含复杂的控制流结构，则不起作用。

DARM的解决思路

DARM的两阶段方法：DARM通过两个阶段解决这个问题。
1. 分析阶段（第IV-C节）：DARM分析由分歧分支支配的控制流区域，以找到位于该分歧分支的真假路径中的同构子区域。这些同构子区域对根据它们的融合收益（melding profitability）使用序列对齐策略进行对齐。融合收益是编译时对通过融合两个控制流区域可节省的线程周期百分比的近似。接下来，DARM在对齐中选择有收益的子区域对（使用一个阈值），并为两个区域中对应的基本块计算指令对齐。
2. 代码生成阶段（第IV-D节）：DARM使用这个指令对齐来融合子区域对中对应的基本块。这个融合过程会迭代应用，直到没有更多有收益的融合可以进行。DARM的融合转换是在SSA形式下完成的，因此生成的CFG可以被其他编译器优化进一步优化（第IV-E和IV-F节）。

A2 方法细节

本节描述DARM用于融合相似控制流子图的算法。首先定义算法中使用的术语。

预备知识与定义

术语定义：
* 定义 1. 简单区域 (Simple Region): 程序CFG的一个子图，它与CFG的其余部分仅通过两条边连接：一条入口边和一条出口边。
* 定义 2. 区域 (Region): CFG中的一个区域由两个基本块（入口和出口）来表征。区域内的所有基本块都受其入口支配，并受其出口后支配。入口为E、出口为X的区域表示为元组(E, X)。LLVM中的区域定义与此类似【索引16，llvm::RegionBase Class Template Reference，https://llvm.org/doxygen/classllvm_1_1RegionBase.html】【索引17 ，The program structure tree: Computing control regions in linear time，1994，SIGPLAN Not.】。
* 定义 3. 单入口单出口子图 (Single Entry Single Exit Subgraph): SESE子图既可以是一个简单区域，也可以是只有一个前驱和一个后继的单个基本块。
* 区域到简单区域的转换：一个入口为E、出口为X的区域可以通过引入新的入口块E_new和出口块X_new来转换为一个简单区域。E的所有后继都移至E_new，并将E_new设为E的唯一后继。类似地，X的所有前驱都移至X_new，并从X_new到X添加一条唯一的出口边。
* 定义 4. 简化区域 (Simplified Region): 一个区域，其所有子区域都已转换为简单区域，称为简化区域。

接下来，我们将介绍DARM编译器遍（pass）为减少控制分歧代码所采取的步骤。

检测可融合的分歧区域

检测分歧分支与区域：首先，DARM需要检测CFG中的分歧分支。我们使用LLVM内置的分歧分析来判断一个分支是否是分歧的（第II节）。包围一个分歧分支的最小CFG区域被称为该分支对应的分歧区域。融合转换仅应用于CFG的分歧区域。下一步是判断一个分歧区域是否包含可以被安全融合的控制流子图（定义3）。

可融合分歧区域的定义：
* 定义 5. 可融合的分歧区域 (Meldable Divergent Region): 一个入口为E、出口为X的简化区域R，如果满足以下条件，则称其为可融合且分歧的：
1. R的入口块有一个分歧分支。
2. 设B_T和B_F是E的后继块。B_T不后支配B_F，且B_F也不后支配B_T。

定义解释：根据定义5，一个可融合的分歧区域在其入口处有一个分歧分支（条件1），这确保了我们的融合变换只应用于分歧区域，而控制流的非分歧部分保持不变。条件2确保了路径B_T → X（即真路径）和B_F → X（即假路径）至少包含一个SESE子图，并且来自这两条路径的这些子图有可能被融合以减少控制流分歧。

应用于示例：以图1中的运行示例为例，当使用ROCm HIPCC GPU编译器【索引7，HIP Programming Guide v4.1，https://rocmdocs.amd.com/en/latest/】以-O3优化级别编译成LLVM-IR时，我们得到图4a所示的CFG。编译器会积极展开内核中的两个循环（第4行和第5行），最终的CFG包含内层循环体（第6-17行）的多个重复片段。图4a中仅显示了一个展开的循环体实例。如第III节所述，该内核包含一个分歧分支，位于基本块%B的末尾。同时，%B的两个后继%C和%D互不后支配。因此，区域(%B, %G)是一个可融合的分歧区域。

图 4. DARM 融合算法应用于 bitonic sort (图 1) (a) 原始控制流图, (b) 区域简化, (c) DARM 子图融合, (d) 非谓词化, (e) 最终优化后的控制流图

计算融合收益

可融合SESE子图的条件：定义5仅帮助我们检测可能包含可融合控制流子图的区域，但并未说明融合它们是否合法或是否能提升性能。首先，我们需要定义两个SESE子图可融合需要满足的条件。

定义 6. 可融合的SESE子图 (Meldable SESE Subgraphs)：SESE子图S1和S2，其中S1属于真路径，S2属于假路径，如果满足以下任一条件，则它们是可融合的：
1. S1和S2都包含多个基本块，并且它们结构相似，即同构。
2. S1是一个简单区域，而S2由单个基本块组成，反之亦然。
3. S1和S2都由单个基本块组成。

合法性保证：定义6确保满足任一条件的两个SESE子图可以被融合，而不会给控制流引入额外的分歧。我们不考虑包含warp级别内建函数（warp-level intrinsics）【索引18，Using cuda warp-level primitives，https://developer.nvidia.com/blog/using-cuda-warp-level-primitives/】的子图进行融合，因为融合这类子图可能导致死锁。

三种融合情况：图2展示了上述三种条件适用的例子。假设在每个例子中，子图L和M都位于一个分歧区域(E, X)内，并且从E到X的任何程序路径只会执行其中一个子图（即，一个warp中执行E的线程必须经过L或M，但不能同时经过两者）。
* 区域到区域的融合 (Case 1)：两个SESE子图L和M是同构的，因此它们可以被融合成一个具有相同控制流结构的子图N。在融合后的子图N中，基本块%C_P和%D_R保证后支配E，线程可以在这些点重收敛，从而减少控制流分歧。结构相似性确保了我们不会在融合后的子图中引入额外的分支。
* 基本块到区域的融合 (Case 2)：基本块%A（在子图L中）可能与CFG M中的任何基本块融合。假设基本块%A和%E具有最高的融合收益。首先，我们复制M的控制流结构来创建一个新的CFG L'。然后，我们将%A放置在L'中，使得%A和%E在L'和M两个CFG中的位置相似。我们通过具体化L'中的分支条件以始终执行%A，并在%A的支配边界上创建φ节点来确保程序正确性。在这个例子中，基本块%R1末尾的分支将总是走%R1-%A的边，并在%R2中添加φ节点。现在，子图L'和M是同构的，可以像情况1一样进行融合。这个过程称为区域复制 (Region Replication)。区域复制的主要好处是允许我们将%A与子图M中任何有收益的基本块融合，并且最终的子图N分歧更少，因为线程可以在融合后的子图N中的基本块%R1_C和%R2_D处重收敛。
* 基本块到基本块的融合 (Case 3)：这是最简单的情况，两个SESE基本块被融合。

子图对齐策略：一个可融合的分歧区域可能在其真假路径中包含多个SESE子图，因此需要一个策略来决定融合哪些子图对。我们将此问题形式化为序列对齐问题。首先，我们获得分歧区域真假路径中子图的有序序列，子图根据其入口和出口块的后支配关系进行排序。

定义 7. 子图对齐 (Subgraph Alignment)：假设一个分歧区域(E, X)在其真路径中有有序的SESE子图{ST1, ST2, ..., STm}，在假路径中有有序的子图{SF1, SF2, ..., SFn}。一个子图对齐是一个有序的元组序列 A = {(STi0, SFj0), (STi1, SFj1), ..., (STik, SFjk)}，其中：
1. 如果 (STp, SFq) ∈ A，那么STp和SFq是可融合的子图。
2. 如果 (STp1, SFq1) ≺ (STp2, SFq2)，那么 STp1 ≺ STp2 且 STq1 ≺ STq2。
这个定义确保只有可融合的子图才能被对齐，并且融合后不会破坏原始的支配和后支配关系。

对齐评分函数：给定一个合适的对齐评分函数F和空位罚分函数W，我们可以使用像Smith-Waterman算法【索引19，Identification of common molecular subsequences，1981，Journal of Molecular Biology】这样的序列对齐方法来找到一个最优的子图对齐。评分函数F衡量融合两个可融合子图S1和S2的收益。我们使用类似于函数合并【索引20，Function merging by sequence alignment，2019，IEEE/ACM International Symposium on Code Generation and Optimization (CGO)】【索引21，Effective function merging in the ssa form，2020，Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation】中采用的方法来定义子图融合收益。首先，我们定义两个基本块b1和b2的融合收益如下：

$$MP_B(b1,b2) = \frac{\sum_{i \in Q} min(freq(i,b1), freq(i,b2)) \times w_i}{lat(b1) + lat(b2)}$$

这里的Q是指令集中所有可能的指令类型集合（即LLVM-IR操作码）。lat(b)是基本块的静态延迟，可以通过对b中所有指令的延迟求和来计算。$w_i$是指令类型i的延迟。这个想法是，在最佳情况下（即b1和b2中所有公共指令都被融合，不考虑它们的顺序），近似计算通过融合b1和b2中的指令可以节省的指令周期百分比。例如，两个具有相同操作码频率分布的基本块将具有0.5的收益值。

子图融合收益：因为可融合的子图是同构的，所以它们的基本块之间存在一一对应的关系。例如，在图2的情况1中，CFG L和M的基本块映射为{(%C, %P), (%E, %Q), (%D, %R)}。假设S1和S2中基本块的映射由O表示。子图S1和S2的融合收益MPS根据它们对应基本块的融合收益来定义。

$$MP_S(S1, S2) = \frac{\sum_{(b1,b2)\in O} MP_B(b1,b2) \times (lat(b1) + lat(b2))}{\sum_{(b1,b2)\in O} lat(b1) + lat(b2)}$$

与MPB类似，MPS衡量通过融合两个SESE子图节省的指令周期百分比。这个度量是一个过高估计，但它提供了一种快速衡量两个子图融合收益的方法，在实践中效果很好。我们使用MPS作为子图对齐的评分函数。

DARM 代码生成

指令对齐：我们的子图融合收益度量（MPS）优先考虑那些在对应基本块中有许多相似指令的子图对。因此，在融合两个对应的基本块时，我们必须确保最大数量的相似指令被融合在一起。这需要计算两个指令序列的对齐，使得如果使用该对齐进行融合，节省的指令周期数将是最大的。我们采用分支融合【索引5，Divergence analysis and optimizations，2011，International Conference on Parallel Architectures and Compilation Techniques】中使用的方法来计算两个指令序列的最优对齐。在这种方法中，兼容的指令被对齐在一起，并且延迟较高的指令优先于延迟较低的指令被对齐。两条指令的融合兼容性取决于多种条件，如具有相同的操作码和操作数的类型兼容。我们使用Rocha等人【索引21，Effective function merging in the ssa form，22020，Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation】描述的标准来确定这种兼容性。这个指令对齐模型对未对齐的指令使用空位罚分，因为需要生成额外的分支来有条件地执行这些未对齐的指令。我们的融合算法不依赖于用于指令对齐计算的序列对齐算法。我们使用Smith-Waterman算法【索引19，Identification of common molecular subsequences，1981，Journal of Molecular Biology】来计算指令对齐，因为先前的工作【索引5，Divergence analysis and optimizations，2011，International Conference on Parallel Architectures and Compilation Techniques】已经证明了其有效性。图3a显示了为两个基本块A和B计算的指令对齐。

DARM融合流程：DARM的控制流融合过程如算法1所示。该算法输入一个SPMD函数F，并迭代F中的所有基本块，检查该基本块是否是可融合分歧区域（R）的入口（根据定义5的条件）。我们使用SimplifyRegion将R内的所有子区域转换为简单区域。我们为R的真假路径中的两个子图序列计算最优子图对齐。如果融合收益大于某个阈值，我们就融合对齐中的每个子图对。子图融合会改变F的控制流。因此，我们首先简化控制流（使用LLVM的simplifycfg），然后重新计算融合遍所需的控制流分析（如支配树、后支配树和区域树）。我们再次在F上应用融合过程，直到没有更多有收益的融合可以进行。

SESE子图融合算法：算法2展示了融合两个子图ST和SF的过程。C是包含ST和SF的可融合分歧区域的分支条件。首先，两个子图按前序遍历线性化，形成一个对应的基本块对列表。按前序处理基本块确保了支配定义在其使用之前被融合。对于列表中的每个基本块对，我们计算一个最优的指令对齐。对齐中的每个对都属于两类：I-I和I-G。I-I是两条指令的正确对齐，I-G是一条指令与一个空位的对齐。我们的对齐确保匹配中的两条指令总是可以融合成一条指令（例如，加载指令不允许与存储指令对齐）。首先，我们遍历对齐对列表并克隆对齐的指令。对于I-I对，我们克隆一条指令，因为它们可以被融合。在克隆期间，我们还更新operandMap，它维护了对齐的LLVM值和融合后的LLVM值之间的映射。我们对指令对齐进行第二次遍历以设置克隆指令的操作数（SetOperands）。假设我们正在处理一个I-I对，其指令为IT、IF，克隆的指令为I_melded。对于I_melded的每个操作数，我们从IT和IF中查找相应的操作数，因为操作数可能是一个已经融合的指令。如果从IT和IF得到的两个操作数相同，我们就直接使用该值作为操作数。如果它们不同，我们生成一个select指令，根据条件C选择正确的操作数。对于I-G对，操作数首先在operandMap中查找，结果被复制到I_melded。

操作数设置示例：参考图3a中的指令对齐，图3b展示了为对齐的指令对a、b和c生成的代码。
* 在情况a中，需要两个select指令，因为两个操作数都映射到不同的值（%0, %4 和 %1, %5）。
* 在情况b中，第一个操作数（%2）对于两条指令是相同的，因此只需要一个select。
* 在情况c中，两条指令的第一和第二个操作数都不同。然而，第二个操作数都映射到同一个融合后的指令%7，所以也只需要一个select。
注意，%cmp是分歧区域的分支条件，我们用它来选择操作数。

图 3. (a) 两个基本块A和B的指令对齐结果, (b) DARM为图3a中的对齐指令a, b和c生成的代码, (c) 对图3a中基本块B的未对齐指令应用非谓词化

融合出口块的分支指令：为子图出口块中的分支指令设置操作数与其他指令稍有不同。设B_ET和B_EF是ST和SF的出口块。B_ET和B_EF的后继可能包含φ节点。因此，我们需要确保B_E的后继可以区分真路径或假路径中产生的值。为了解决这个问题，我们将B_ET和B_EF的分支条件移动到新创建的块B'_T和B'_F中。现在我们可以根据C有条件地跳转到B'_T和B'_F。例如，在图4c中，当融合图4b中的%X1和%X2的出口分支时，创建了基本块%M和%N。%G中的任何φ节点（图4c）都可以使用%M和%N来区分真假路径中产生的值。

融合φ节点：在LLVM SSA形式中，φ节点总是位于基本块的开头。即使指令对齐结果包含两个对齐的φ节点，我们也无法将它们融合成一个单一的φ节点，因为select指令不能在它们之前插入。因此，我们将所有φ节点复制到融合后的基本块中，并使用operandMap为它们设置操作数。这可能会引入冗余的φ节点，我们会在后处理中移除它们。

非谓词化 (Unpredication)

非谓词化的动机与实现：在我们的代码生成过程中，未对齐的指令被插入到同一个融合的基本块中，无论它们是来自真路径还是假路径（即完全谓词化）。这可能由于几个原因引入开销。如果分支条件C偏向于真路径或假路径，可能导致冗余指令执行。此外，对未对齐的存储指令进行完全谓词化需要添加额外的加载指令，以确保正确的值被写回内存。非谓词化在空位边界处分割融合的基本块，并将未对齐的指令移动到新的块中。图3c展示了对图3a中基本块B的未对齐指令应用非谓词化。原始基本块被分割成两部分（%M和%M.tail），未对齐的指令（%8和%9）被移动到一个新的基本块%M.split中。φ节点（%10和%11）被添加到%M.tail中，以确保未对齐的指令支配其使用者。%8和%9在真路径中永远不会执行，因此来自块%M的φ节点的传入值是未定义的（LLVM undef）。注意，在区域复制（第IV-C节）中，我们仅对融合的基本块应用非谓词化。融合块之外的存储指令通过插入额外的加载来进行完全谓词化。

前处理和后处理步骤

前处理：维护SSA支配属性：在SSA形式中，任何定义都必须支配其所有使用者。然而，DARM的子图融合可能会破坏这个属性。考虑图5A中的两个可融合子图ST和SF。在融合前，定义%a支配其使用%x。然而，如果ST和SF被简单地融合，%a将不再支配%x。为了解决这个问题，我们添加一个带有φ节点%m的新基本块%P。%a的所有使用都被替换为%m（图5B）。注意，值%m在真路径执行中永远不会被使用，因此它在真路径中是未定义的（undef）。我们在融合之前应用这个预处理步骤（算法2中的PreProcess）。

后处理：移除冗余：子图融合可能会引入具有相同后继的分支、具有相同操作数的φ节点以及冗余的φ节点。算法2中的RunPostOptimizations会移除这些冗余。

整体流程

Bitonic Sort 示例的完整转换流程：图4展示了子图融合流程的每个阶段如何转换bitonicSort内核的CFG。
1. 原始CFG：图4a显示了原始CFG。区域(%B, %G)是一个可融合的分歧区域。
2. 区域简化：图4b显示了区域简化后的CFG。根据我们的分析，子图(%C, %X1)和(%D, %X2)进行融合是有益的。
3. 子图融合：图4c显示了子图融合后的CFG。
4. 非谓词化：应用非谓词化后的结果显示在图4d中。注意，非谓词化将基本块%C_D（在图4c中）分割成5个基本块（在图4d中用蓝色虚线框放大显示）。基本块%P.S.1和%P.S.2是未对齐的指令组，它们被有条件地执行。
5. 最终优化：图4e显示了应用后优化后的最终优化CFG。注意，ROCm HIPCC编译器积极地应用了if-conversion，因此在这种情况下，非谓词化步骤的效果被抵消了。

指令级融合示例：图6解释了为运行示例生成融合指令的过程。图6a显示了运行示例中可融合分歧区域（图4b中的(%B, %G)）的LLVM-IR。在DARM代码生成期间，子图(%C, %X1)和(%D, %X2)中的基本块被线性化以计算指令对齐。对应的基本块对是[%C, %D]、[%E, %F]和[%X1, %X2]。在这个例子中，除了基本块%D和%C中的比较指令（%34和%31）之外，所有指令都完美对齐。这些比较指令因为比较类型不同（大于 vs 小于）而无法对齐。

图6b显示了应用子图融合和非谓词化后的LLVM-IR（类似于图4d）。由于指令%34和%31未对齐，非谓词化步骤引入了基本块%P.S.1和%P.S.2，以根据分歧条件%16有条件地执行它们。插入了额外的φ指令%phi.1和%phi.2，以确保在非谓词化步骤中def-use链不被破坏。在所有对齐的指令中，只有基本块%C和%D末尾的分支指令在指令融合期间需要select指令。例如，基本块%E、%F中的存储指令使用匹配的操作数，因此可以不添加selects而进行融合。另一方面，条件分支指令使用值%34和%31，并插入select指令%37（图6b）来有条件地选择分支条件。注意，值%34和%31将分别通过φ节点%phi.1和%phi.2流向它们的使用者。因此，select指令（即%37）使用这些φ节点作为其操作数。

图 6. 应用 DARM 转换前后我们运行示例的 LLVM-IR (a) 可融合的分支区域 (b) 子图融合和非谓词化后生成的 LLVM-IR

实现细节

LLVM Pass 实现：我们在ROCM HIPCC GPU编译器【索引10，ROCm Compiler SDK，https://rocmdocs.amd.com/en/latest/ROCm_Compiler_SDK/ROCm-Compiler-SDK.html】之上，将第IV节中描述的DARM算法实现为一个LLVM-IR分析和转换遍（pass）。分析和转换都是在GPGPU函数上操作的函数遍。分析遍首先使用LLVM的分歧分析检测可融合的分歧区域，然后找到所有可以融合的有益子图对。我们使用默认的融合收益阈值0.2（算法1），并在第VI-E节中对此阈值进行了敏感性分析。我们使用修改版的LLVM成本模型【索引22 ，CostModel.cpp File Reference，https://llvm.org/doxygen/CostModel_8cpp.html】来获取指令延迟，用于融合收益和指令对齐计算。

转换与编译流程：转换遍使用分析的输出来执行DARM的代码生成过程（第IV-D节），同时还执行第IV-E和IV-F节中描述的非谓词化、前处理和后处理步骤。LLVM遍用大约2500行C++代码实现。为了使用我们的遍生成程序二进制文件，我们必须将我们的遍包含在ROCM HIPCC编译流程中。大多数GPGPU编译器（例如，CUDA nvcc，ROCm HIPCC）对GPU设备和CPU主机代码使用分开编译。最终的可执行文件将设备二进制文件嵌入在主机二进制文件中。在修改后的工作流程中，我们首先将设备代码编译成LLVM-IR，然后在其上运行DARM以生成转换后的IR模块。我们的遍只在设备函数上运行，避免对主机代码进行任何修改。之后，我们使用LLVM静态编译器（llc）【索引23，llc - LLVM static compiler，https://llvm.org/docs/CommandGuide/llc.html】为转换后的设备代码生成一个目标文件。编译流程的其余部分与未作任何修改时相同。

A4 实验环境

硬件配置:
- GPU: AMD Radeon Pro Vega 20，拥有16GB全局内存，64kB共享内存（LDS），最大时钟频率1700 MHz。
- CPU: AMD Ryzen Threadripper 3990X 64核处理器，最大时钟频率2900 MHz。
软件配置:
- 编译器: 基于ROCM HIPCC的修改版编译器，集成了DARM作为LLVM Pass。
- 基线编译选项: -O3。
数据集/基准测试:
- 合成程序: 创建了多个具有不同复杂度控制分歧的合成程序，用于评估DARM的通用性。
- 真实世界基准测试: 选择了7个用HIP编写的高度优化的真实程序，这些程序包含DARM可以利用的if-then-else分歧区域。
  1. Bitonic Sort (BIT): 运行示例，输入2^26个元素，改变块大小。
  2. Partition and Concurrent Merge (PCM): 基于Batcher奇偶合并排序的并行排序算法，输入2^28个元素。
  3. Mergesort (MS): 并行自底向上归并排序，输入2^20个元素。
  4. LU-Decomposition (LUD): 来自Rodinia基准套件，专注于lud_perimeter内核，输入16384x16384矩阵。
  5. N-Queens (NQU): 来自GPGPU-sim基准套件的N皇后问题求解器，N=15。
  6. Speckle Reducing Anisotropic Diffusion (SRAD): 来自Rodinia的图像去噪应用，输入4096x4906图像。
  7. DCT Quantization (DCT): 离散余弦变换平面的量化，输入2^15x2^15的DCT平面。
对比方法:
- 基线 (Baseline): 使用-O3编译的高度优化的原始内核。
- 分支融合 (Branch Fusion): 通过修改DARM以仅处理简单的菱形控制流（if-then-else）来实现。
评估变量:
- 块大小 (Block Size): 对于每个内核，在不同的块大小下进行评估，因为最佳块大小可能依赖于多种因素。本文旨在评估，对于给定块大小的内核，应用DARM会产生什么效果。

A4 实验结果

性能

实验内容: 评估DARM相对于基线和分支融合（BF）在不同块大小下的性能加速比。
实验结果: 如图7所示，DARM在大多数情况下都提升了性能，所有基准测试的几何平均加速比为1.15倍，在每个基准测试的最佳基线配置上的几何平均加速比为1.16倍。BIT和PCM在所有块大小下性能提升最显著，因为它们具有复杂的控制流和共享内存指令。LUD的性能提升仅在块大小为16、32、64时可见，因为其分歧与块大小相关。对于NQU，DARM通过区域复制成功移除了分歧。唯一的例外是SRAD，在某些配置下性能下降。
分析结论: DARM能有效融合复杂控制流，特别是在包含共享内存指令的分歧区域。对于SRAD，DARM融合了所有三个分支路径，而实际执行偏向其中两条，导致引入了额外开销。这表明融合顺序的优先级（未在本文中考虑）可能对性能有影响。有趣的是，对于4/7的基准测试，使基线性能最佳的块大小也为DARM带来了最佳的绝对性能和相对加速比。

ALU利用率

实验内容: 使用rocprof工具收集ALU利用率，以解释性能提升的原因。
实验结果: 如图8所示，DARM显著提高了大多数基准测试的ALU利用率。BIT是一个例外，虽然DARM对不同的比较操作进行了非谓词化，但后续的优化遍又将它们完全谓词化，导致ALU利用率较低。
分析结论: DARM的融合转换使得分歧路径中的ALU指令可以在同一周期内发出，从而有效提高了SIMD资源利用率。

内存指令的融合

实验内容: 收集全局和共享内存指令的计数，分析内存指令融合对性能的影响。
实验结果: 如图9所示，在BIT和PCM中，共享内存指令数量显著减少，这与性能增益相关。在LUD中，虽然分歧路径中有许多共享内存指令，但由于内存对齐不同无法融合，导致指令数增加；但全局内存指令数减少了。DCT在分歧区域没有内存指令。
分析结论: 融合共享内存指令比融合ALU指令更有益，因为共享内存指令的延迟高于多数ALU指令。融合共享内存指令可以带来接近2倍的周期节约。相比之下，融合全局内存指令并不总能提升性能，因为不同线程请求的数据可能位于不同的缓存行，即使在同一周期发出，内存控制器也会串行化这些请求。

融合收益阈值敏感性

实验内容: 在真实世界基准测试的最佳性能块大小配置下，评估不同融合收益阈值对DARM性能的影响。
实验结果: 如图10所示，随着阈值的增加，DARM的加速比因错失优化机会而降低。当阈值降低时，性能提升的增量在0.2之后变得不显著。
分析结论: 阈值不能降为零，否则所有可能的对都会被融合，导致后续的CFG简化遍进行不必要的非谓词化，甚至可能使DARM不收敛。默认阈值0.2是一个合理的选择。

编译时间

实验内容: 测量基线和DARM的设备代码编译时间。
实验结果: 如表II所示，DARM引入的编译时间开销可以忽略不计。DARM的分析和指令对齐在基本块级别进行，而不是在更高层级（如函数或区域），因此开销很小。LUD的轻微开销是由于循环展开后的大基本块上的序列对齐开销。
分析结论: DARM的编译时间取决于被融合的基本块大小和程序结构。对于大多数程序，DARM的编译开销是总编译时间的一小部分。

A7 补充细节

讨论与未来工作

DARM的适用性与局限性：大多数GPGPU基准测试都经过专家开发人员的大量手工优化，这通常包括类似DARM的转换来消除控制流分歧【索引5，Divergence analysis and optimizations，2011，International Conference on Parallel Architectures and Compilation Techniques】。我们在有限的一组真实世界基准上评估DARM，主要原因就在于此。然而，我们强调手工进行类似DARM的转换是耗时且容易出错的。例如，作者花费了数小时才手动将控制流融合应用于LUD内核。因此，将这项工作交给编译器可以节省大量的开发人员精力。

DARM的潜在应用：DARM的好处不仅限于减少GPGPU程序中的控制流分歧。
* 它可以用于减少任何采用SIMT执行的硬件后端和编程模型（例如，带有ISPC的Intel/AMD处理器【索引45，ispc: A spmd compiler for high-performance cpu programming，2012，Innovative Parallel Computing (InPar)】）中的控制流分歧。
* DARM可以用来减少程序中的分支，这一特性可被利用来加速软件测试技术，如符号执行【索引46，Targeted program transformations for symbolic execution，2015，Proceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering】。
* DARM可以提取出程序if-then-else区域内的公共代码段，因此也可以用作函数内的代码大小缩减优化。
这些应用表明DARM作为一种通用的编译器优化技术非常有用。我们计划在未来的工作中探索其中一些应用。

A5 结论

GPGPU程序中的分歧控制流由于序列化而导致性能下降。本文介绍了DARM，一个在LLVM上实现的、用于GPGPU程序的新的编译器分析和转换框架，它能够检测并融合分歧路径中相似的控制流区域，以减少控制流的分歧。DARM推广并包含了先前减少分歧的努力，如尾部合并和分支融合。我们证明了DARM通过提高ALU利用率和促进跨多个真实世界基准的合并共享内存访问来提高性能。

方法细节中的引用汇总

[1] ng, warp formation and scheduling for efficient gpu control flow, 2007, 40th Annual IEEE/ACM International Symposium on Microarchitecture: 在第七节（相关工作）中引用，作为一种通过动态Warp形成来减少分歧的架构级技术。
[2] W. W. L. Fung and T. M. Aamodt, “Thread block compaction for efficient simt control flow,” in 2011 IEEE 17th International Symposium on High Performance Computer Architecture, 2011: 在第一节（引言）中提到，作为一种解决分歧的硬件级方法。
[3] M. Rhu and M. Erez, “The dual-path execution model for efficient gpu control flow,” in 2013 IEEE 19th International Symposium on High Performance Computer Architecture (HPCA), 2013: 在第一节（引言）中提到，作为一种解决分歧的硬件级方法。在第七节（相关工作）中再次引用，作为独立线程调度的例子。
[4] W.-K. Chen, B. Li, and R. Gupta, “Code compaction of matching singleentry multiple-exit regions,” in Proceedings of the 10th International Conference on Static Analysis, 2003: 在第一节（引言）和第七节（相关工作）中引用，作为一种早期的、受限制的减少分歧的技术（尾部合并）。
[5] B. Coutinho, D. Sampaio, F. M. Q. Pereira, and W. Meira Jr., “Divergence analysis and optimizations,” in 2011 International Conference on Parallel Architectures and Compilation Techniques, 2011: 在第一节（引言）、第二节（背景）、第四节（方法）和第七、八节（相关工作、讨论）中多次引用。作为分支融合技术的代表，是DARM的主要对比和扩展对象。引用其在分歧分析、指令对齐方法等方面的贡献。
[6] C. Lattner and V. Adve, “Llvm: a compilation framework for lifelong program analysis transformation,” in International Symposium on Code Generation and Optimization, 2004: 在第一节（引言）和第二节（背景）中引用，说明DARM是基于LLVM框架实现的。
[7] “HIP Programming Guide v4.1”: 在第一节（引言）、第二节（背景）和第六节（评估）中引用，作为GPGPU编程模型之一，DARM可以处理用其编写的程序。
[8] “CUDA C++ Programming Guide”: 在第一节（引言）和第二节（背景）中引用，作为GPGPU编程模型之一，DARM可以处理用其编写的程序。
[10] “ROCm Compiler SDK”: 在第二节（背景）和第五节（实现）中引用，说明DARM是基于ROCm HIPCC编译器实现的。
[11] R. Cytron, et al., “Efficiently computing static single assignment form and the control dependence graph,” ACM Trans. Program. Lang. Syst., 1991: 在第二节（背景）和第四节（方法）中引用，作为LLVM IR中SSA形式和φ节点的基础。
[12] R. Karrenberg and S. Hack, “Improving performance of opencl on cpus,” in Compiler Construction, 2012: 在第二节（背景）和第七节（相关工作）中引用，作为LLVM中分歧分析的基础。
[13] J. Rosemann, S. Moll, and S. Hack, “An abstract interpretation for spmd divergence on reducible control flow graphs,” Proc. ACM Program. Lang., 2021: 在第二节（背景）和第七节（相关工作）中引用，作为一种更精确的分歧分析方法，可以为DARM提供更多机会。
[14] K. E. Batcher, “Sorting networks and their applications,” in Proceedings of the April 30–May 2, 1968, spring joint computer conference, 1968: 在第三节（激励示例）中引用，作为Bitonic Sort算法的来源。
[15] D. Cederman and P. Tsigas, “Gpu-quicksort: A practical quicksort algorithm for graphics processors,” ACM J. Exp. Algorithmics, 2010: 在第三节（激励示例）中引用，作为Bitonic Sort在GPU算法中应用的例子。
[16] “llvm::RegionBase Class Template Reference”: 在第四节（方法）中引用，用于定义“区域”这一术语，说明其与LLVM中的定义类似。
[17] R. Johnson, D. Pearson, and K. Pingali, “The program structure tree: Computing control regions in linear time,” SIGPLAN Not., 1994: 在第四节（方法）中引用，用于定义“区域”这一术语。
[18] “Using cuda warp-level primitives”: 在第四节（方法）中引用，说明DARM不处理包含warp级内建函数的子图，以避免死锁。
[19] T. Smith and M. Waterman, “Identification of common molecular subsequences,” Journal of Molecular Biology, 1981: 在第四节（方法）中引用，作为DARM中用于子图和指令对齐的Smith-Waterman算法的来源。
[20] R. C. O. Rocha, et al., “Function merging by sequence alignment,” in 2019 IEEE/ACM International Symposium on Code Generation and Optimization (CGO), 2019: 在第四节（方法）和第七节（相关工作）中引用，说明DARM的收益计算方法借鉴了函数合并技术。
[21] R. C. O. Rocha, et al., “Effective function merging in the ssa form,” in Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation, 2020: 在第四节（方法）和第七节（相关工作）中引用，说明DARM的收益计算和指令兼容性判断借鉴了函数合并技术。
[22] “CostModel.cpp File Reference”: 在第五节（实现）中引用，说明DARM使用LLVM的成本模型来获取指令延迟。
[23] “llc - LLVM static compiler”: 在第五节（实现）中引用，作为DARM编译流程的一部分。
[35] J. Anantpur and G. R., “Taming control divergence in gpus through control flow linearization,” in Compiler Construction, 2014: 在第七节（相关工作）中引用，作为一种通过谓词化减少分歧的技术。
[36] J. Fukuhara and M. Takimoto, “Branch divergence reduction based on code motion,” Journal of Information Processing, 2020: 在第七节（相关工作）中引用，作为一种与DARM正交的分歧减少技术。
[37] F. Khorasani, et al., “Efficient warp execution in presence of divergence with collaborative context collection,” in Proceedings of the 48th International Symposium on Microarchitecture, 2015: 在第七节（相关工作）中引用，作为一种分歧减少技术。
[38] T. D. Han and T. S. Abdelrahman, “Reducing branch divergence in gpu programs,” in Proceedings of the Fourth Workshop on General Purpose Processing on Graphics Processing Units, 2011: 在第七节（相关工作）中引用，作为一种与DARM互补的分歧减少技术。
[40] S. Damani and V. Sarkar, “Common subexpression convergence: A new code optimization for simt processors,” in Languages and Compilers for Parallel Computing, 2021: 在第七节（相关工作）中引用，作为一种与DARM对比的分歧减少技术，说明DARM更通用。
[41] W. W. L. Fung and T. M. Aamodt, “Thread block compaction for efficient simt control flow,” in 2011 IEEE 17th International Symposium on High Performance Computer Architecture, 2011: 在第七节（相关工作）中引用，作为一种架构级技术。
[42] T. G. Rogers, et al., “A variable warp size architecture,” in Proceedings of the 42nd Annual International Symposium on Computer Architecture, 2015: 在第七节（相关工作）中引用，作为一种架构级技术。
[43] J. Meng, D. Tarjan, and K. Skadron, “Dynamic warp subdivision for integrated branch and memory divergence tolerance,” SIGARCH Comput. Archit. News, 2010: 在第七节（相关工作）中引用，作为一种架构级技术。
[44] A. ElTantawy, et al., “A scalable multi-path microarchitecture for efficient gpu control flow,” in 2014 IEEE 20th International Symposium on High Performance Computer Architecture (HPCA), 2014: 在第七节（相关工作）中引用，作为独立线程调度的例子。
[45] M. Pharr and W. R. Mark, “ispc: A spmd compiler for high-performance cpu programming,” in 2012 Innovative Parallel Computing (InPar), 2012: 在第八节（讨论）中引用，作为DARM可以应用的另一个SIMT编程模型。
[46] C. Cadar, “Targeted program transformations for symbolic execution,” in Proceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering, 2015: 在第八节（讨论）中引用，作为DARM减少分支特性的一个潜在应用。