收敛性和一致性¶
简介¶
在某些环境中，线程组并行执行相同的程序，其中使用称为收敛操作的特殊原语建立组内高效通信。收敛操作的结果对参与它的线程集敏感。
收敛的直观图景是围绕着“锁步”执行的线程构建的——一组线程被认为是收敛的，如果它们都在“一起执行相同的指令序列”。这些线程可能在发散分支处发散，并且它们可能稍后在某个公共程序点重新收敛。
在这个直观的图景中，当收敛的线程执行指令时，如果结果值在这些线程中是相同的，则称该结果值为一致的，否则为发散的。相应地，如果分支的条件是一致的，则称该分支为一致分支，否则为发散分支。
但是，锁步执行的假设对于描述收敛操作的通信不是必要的。它还通过过度指定线程在这种并行环境中如何执行来约束实现（编译器以及硬件）。为了消除这个假设
我们将收敛性定义为不同线程执行每条指令之间的关系，而不是线程本身之间的关系。这个定义对于已知目标是合理的，并且与 LLVM IR 中收敛操作的语义兼容。
我们还根据这种收敛性定义一致性。只有当指令的相应执行是收敛的时，才能跨多个线程检查指令的输出是否一致。
本文档描述了一种静态分析，用于确定函数中每条指令的收敛性。该分析扩展了先前关于发散分析的工作[DivergenceSPMD]，以涵盖不可归约的控制流。所描述的分析在 LLVM 中用于实现 UniformityAnalysis，该分析确定 LLVM IR 或 MIR 函数中每条指令计算的值的一致性。
Julian Rosemann、Simon Moll 和 Sebastian Hack。2021 年。可归约控制流图上 SPMD 发散的抽象解释。Proc. ACM Program。Lang. 5, POPL, Article 31 (2021 年 1 月), 35 页。 https://doi.org/10.1145/3434312
动机¶
发散分支约束了程序转换，例如更改 CFG 或将收敛操作移动到 CFG 的不同点。跨发散分支执行这些转换可能会更改收敛执行收敛操作的线程集。虽然这些约束不在本文档的范围之内，但一致性分析允许这些转换识别一致分支，在这些分支中这些约束不成立。
一致性本身在以共享执行资源（例如 waves、warps 或 subgroups）的组执行线程的目标上也很有用
一致的输出可能在共享资源上计算或存储。
这些目标必须“线性化”发散分支，以确保分支的每一侧都由同一组中的相应线程跟随。但是，在一致分支处线性化是不必要的，因为整个线程组要么遵循分支的一侧，要么遵循另一侧。
术语¶
线程和动态实例¶
程序源代码中指令的每次出现都称为静态实例。当线程执行程序时，静态实例的每次执行都会产生该指令的不同的动态实例。
每个线程产生唯一的动态实例序列
该序列是沿着分支决策和循环遍历生成的。
以“第一个”指令的动态实例开始。
继续执行连续的“下一个”指令的动态实例。
线程是独立的；一些目标可以选择以组的形式执行它们，以便在可能的情况下共享资源。
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|||
线程 1 |
Entry1 |
H1 |
B1 |
L1 |
H3 |
L3 |
Exit |
||||
线程 2 |
Entry1 |
H2 |
L2 |
H4 |
B2 |
L4 |
H5 |
B3 |
L5 |
Exit |
在上表中，每一行是一个不同的线程，从左到右列出该线程产生的动态实例。每个线程执行相同的程序，该程序以 Entry 节点开始，以 Exit 节点结束，但是不同的线程可能会采用不同的路径通过程序的控制流。列的编号仅为方便起见，空单元格没有特殊含义。同一列中列出的动态实例是收敛的。
收敛性¶
先收敛是动态实例上的严格偏序，定义为以下各项的传递闭包
如果动态实例
P在同一线程中严格在Q之前执行，则P先收敛于Q。如果动态实例
P在同一线程中严格在Q1之前执行，并且Q1与Q2收敛，则P先收敛于Q2。如果动态实例
P1与P2收敛，并且P2在同一线程中严格在Q之前执行，则P1先收敛于Q。
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
线程 1 |
Entry |
… |
S2 |
T |
… |
Exit |
|||
线程 2 |
Entry |
… |
Q2 |
R |
S1 |
… |
Exit |
||
线程 3 |
Entry |
… |
P |
Q1 |
… |
上表显示了来自不同线程的动态实例的部分序列。同一列中的动态实例被假定为收敛的（即，在收敛关系中彼此相关）。结果收敛顺序包括边 P -> Q2、Q1 -> R、P -> R、P -> T 等。
收敛是不同线程为同一静态实例产生的动态实例上的传递对称关系。
为收敛关系提供任何一个定义是不切实际的，因为不同的环境可能希望以不同的方式关联动态实例。先收敛是严格偏序这一事实是对收敛关系的约束。如果不同的动态实例永远不收敛，则可以轻松满足此条件。下面，我们提供一个称为最大收敛的关系，该关系满足先收敛，并且适用于已知目标。
注意
先收敛关系不是直接可观察的。程序转换通常可以自由更改指令的顺序，即使这显然会更改先收敛关系。
收敛的动态实例不需要同时执行，甚至不需要在同一资源上执行。收敛操作的收敛动态实例可能看起来是这样做的，但这只是实现细节。
P先收敛于Q这一事实并不自动意味着P在内存模型意义上先于Q发生。
最大收敛性¶
本节定义了一个约束，该约束可用于生成最大收敛关系，而不会违反严格的先收敛顺序。这种最大收敛关系对于实际目标是合理的，并且与收敛操作兼容。
最大收敛关系是根据循环头定义的，假设线程在循环的每次“迭代”中在循环头处收敛。非正式地，如果两个线程在进入循环后都先前执行了循环头相同次数，则它们执行循环的相同迭代。一般来说，这还需要考虑父循环的迭代。
最大收敛
由不同线程为同一静态实例
X产生的动态实例X1和X2在最大收敛关系中收敛，当且仅当
X不包含在任何循环中，或者，对于每个包含
X的、以H为头的循环C
在相应线程中先于
X1的H的每个动态实例H1都先收敛于X2，并且，在相应线程中先于
X2的H的每个动态实例H2都先收敛于X1，不假设
X1与X2收敛。
注意
如果 CFG 是不可归约的，则循环头对于给定的 CFG 可能不是唯一的。同一 CFG 的每个循环层次结构都会导致不同的最大收敛关系。
为了简洁起见，文档的其余部分将术语收敛限制为表示“在给定循环层次结构的最大收敛关系下相关”。
现在可以在前面的示例中演示最大收敛，如下所示
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|||
线程 1 |
Entry1 |
H1 |
B1 |
L1 |
H3 |
L3 |
Exit |
||||
线程 2 |
Entry2 |
H2 |
L2 |
H4 |
B2 |
L4 |
H5 |
B3 |
L5 |
Exit |
Entry1和Entry2是收敛的。H1和H2是收敛的。B1和B2由于H4而不收敛，H4不先收敛于B1。H3和H4是收敛的。H3由于H4而不与H5收敛，H4不先收敛于H3。L1和L2是收敛的。L3和L4是收敛的。L3由于H5而不与L5收敛，H5不先收敛于L3。
对循环头的依赖¶
先收敛中的矛盾仅可能发生在位于某些循环内的两个节点之间。此类节点的动态实例可能在同一线程中交错，并且这种交错对于不同的线程可能是不同的。循环头充当最大收敛关系中的隐式收敛点。当线程执行节点 X 一次，然后再次执行它时，它必须遵循 CFG 中包含 X 的闭合路径。这样的路径必须穿过至少一个循环的头——包含整个闭合路径的最小循环。在给定线程中，X 的两个动态实例要么被至少一个循环头的执行分隔，要么 X 本身就是循环头。
考虑嵌套循环 C1、C2、…、Ck 的序列，使得 C1 是最外层循环，Ck 是最内层循环，其头分别为 H1、H2、…、Hk。当线程进入循环 Ck 时，以下任何一种情况都可能发生
线程直接进入循环
Ck，而没有执行任何头H1到Hk。线程执行了一些或所有嵌套头一次或多次。
最大收敛关系捕获了关于循环的以下直觉
当两个线程进入顶层循环
C1时，它们执行作为C1的子节点的每个节点的收敛动态实例。当两个线程进入嵌套循环
Ck时，它们执行作为Ck的子节点的每个节点的收敛动态实例，直到任一线程退出Ck为止，当且仅当它们执行了它们任一线程遇到的最后一个嵌套头的收敛动态实例。请注意，当线程退出嵌套循环
Ck时，它必须遵循Ck外部的闭合路径才能重新进入它。这需要执行某个外部循环的头，如前所述。
考虑由线程 T1 和 T2 为作为嵌套循环 Ck 的子节点的节点 X 产生的两个动态实例 X1 和 X2。最大收敛按如下方式关联 X1 和 X2
如果两个线程都没有执行来自
H1到Hk的任何头，则X1和X2是收敛的。否则，如果没有任何来自
H1到Hk的任何头Q的收敛动态实例Q1和Q2（其中Q可能与X相同），使得Q1先于X1且Q2先于相应线程中的X2，则X1和X2不收敛。否则，考虑在相应线程中最近在
X1和X2之前发生的来自H1到Hk的头Q的收敛动态实例对Q1和Q2。然后，当且仅当在线程T1中的Q1和X1之间，或在线程T2中的Q2和X2之间，没有发生来自H1到Hk的任何头的动态实例时，X1和X2才收敛。换句话说，Q1和Q2表示最后的收敛点，在执行X之前没有执行其他头。
示例
上图显示了两个嵌套的不可归约循环，其头为 R 和 S。节点 Entry 和 Q 具有发散分支。下表显示了通过 CFG 中不同路径的三个线程之间的收敛性。同一列中列出的动态实例是收敛的。
1
2
3
4
5
6
7
8
10
线程1
Entry
P1
Q1
S1
P3
Q3
R1
S2
Exit
线程2
Entry
P2
Q2
R2
S3
Exit
线程3
Entry
R3
S4
Exit
P2和P3由于S1而不收敛Q2和Q3由于S1而不收敛S1和S3由于R2而不收敛S1和S4由于R3而不收敛
非正式地，T1 和 T2 执行内部循环的次数不同，而没有执行外部循环的头。当所有线程首次执行外部循环的头时，它们在外部循环中收敛。
一致性¶
当且仅当两个收敛的动态实例的输出对于这两个动态实例比较相等时，这两个动态实例的输出才是一致的。
静态实例
X的输出对于给定的线程集是一致的，当且仅当对于这些线程产生的X的每对收敛动态实例，它都是一致的。
非一致的值称为发散的。
对于线程集 S，静态实例的每个输出的一致性确定如下
指令的语义可能会指定输出是一致的。
否则，如果静态实例不是 m-收敛的，则输出是发散的。
否则，如果静态实例是 m-收敛的
如果是 PHI 节点，则当且仅当对于由
S中所有线程产生的每对收敛动态实例时，其输出才是一致的两个实例都从收敛的动态实例中选择相同的输出，并且，
该输出对于
S中的所有线程都是一致的。
否则，当且仅当输入操作数对于
S中的所有线程都是一致的时，输出才是一致的。
发散的循环出口¶
当发散分支发生在循环内部时，发散路径可能会继续到循环的出口。这称为发散循环出口。如果循环是不可归约的，则发散路径可能会重新进入并最终到达循环内的汇合点。应该检查这样的汇合点是否符合发散入口标准。
当两个线程在循环内收敛执行产生一致的值，但在执行循环头不同次数后（非正式地，在循环的不同迭代中）沿着相同的发散路径退出循环时，沿发散路径且位于循环外部的节点会经历时间发散。对于循环内的节点 N，两个线程的输出可能是一致的，但循环外的任何使用 U 都会接收来自 N 的非收敛动态实例的值。U 的输出可能是发散的，具体取决于指令的语义。
静态一致性分析¶
不可归约的控制流会导致不同的循环层次结构，具体取决于深度优先遍历期间头的选择。因此，静态分析并非总是可以确定不可归约循环中节点的收敛性，并且任何一致性分析都仅限于那些静态实例，这些静态实例的收敛性与循环层次结构无关
m-收敛静态实例
当且仅当其动态实例的最大收敛关系在可以为该 CFG 构建的每个循环层次结构中都相同时，给定 CFG 的静态实例
X才是m-收敛的。注意
换句话说，m-收敛静态实例
X的两个动态实例X1和X2在某个循环层次结构中收敛，当且仅当它们在同一 CFG 的每个其他循环层次结构中也收敛。如前所述，为了简洁起见，我们将术语收敛限制为表示“在给定循环层次结构的最大收敛关系下相关”。
如果给定 CFG 中的每个节点 X 满足以下必要条件，则报告该节点是 m-收敛的
注意
可归约循环轻松满足上述条件。特别是，如果整个 CFG 是可归约的，则 CFG 中的所有节点都是 m-收敛的。
使用先前描述的标准确定静态实例的每个输出的一致性。发散输出的发现可能会导致其用途（包括分支）也变得发散。分析传播这种发散，直到达到固定点。
使用这些标准推断出的收敛性是任何循环层次结构的最大收敛关系的安全子集。特别是，即使在检查某些其他循环层次结构 T' 时未检测到该事实，也足以确定静态实例对于给定循环层次结构 T 是否为 m-收敛的。
此属性允许编译器转换使用一致性分析，而不会受到底层循环分析中 DFS 选择的影响。当两个转换对同一个 CFG 使用不同的一致性分析实例时，一个分析实例中的“发散值”结果不会与另一个分析实例中的“一致值”结果相矛盾。
诸如 SimplifyCFG、CSE 和循环转换之类的通用转换通常会以更改最大收敛关系的方式更改程序。 这也意味着先前一致的值在这样的转换之后可能会变得发散。 在此类转换之后，必须重新计算一致性。
循环内的发散分支¶
上图显示了不可约循环区域内的发散分支 Q。当两个线程在 Q 处发散时，循环区域内动态实例的收敛取决于所选择的循环层次结构
在检测到以
P为头的单个循环C的实现中，循环内的收敛由P决定。在检测到以
R和S为头的两个嵌套循环的实现中，这些循环内的收敛由它们各自的头决定。
一种保守的方法是简单地将不可约循环内的所有节点报告为具有发散输出。但是，为了最大化一致性，期望识别 CFG 中的 m-收敛节点。本节描述了一种从此类闭合路径导出的节点模式，闭合路径是 CFG 的属性，不依赖于循环层次结构。
发散入口标准
仅当对于位于
P上的每个发散分支B及其汇合节点J，没有从B到J的发散路径上的P入口时，闭合路径P中所有节点的动态实例才是 m-收敛的。
考虑上图中的闭合路径 P -> Q -> R -> S。P 和 R 是 闭合路径的入口。Q 是发散分支，S 是该分支的汇合点，发散路径为 Q -> R -> S 和 Q -> S。
如果存在发散入口
R，则在某些循环层次结构中，R是包含闭合路径的最小循环C的头，并且在集合C - R中存在一个 子循环C'，其中包含分支Q和汇合点S。当线程在Q处发散时，一个子集M继续在循环C'内，而补集N退出C'并到达R。S的动态实例由集合M中的线程执行，由于R的存在，它们与集合N中执行的实例不收敛。通俗地说，在Q处发散的线程在外循环C的同一次迭代中重新收敛，但它们可能以不同的方式执行了内循环C'。1
2
3
4
5
6
7
8
9
10
11
线程1
Entry
P1
Q1
R1
S1
P3
…
Exit
线程2
Entry
P2
Q2
S2
P4
Q4
R2
S4
Exit
在上表中，由于
R1，S2与S1不收敛。
如果
R不存在，或者如果R以外的任何节点是C的头，则不会检测到这样的子循环C'。在Q处发散的线程执行S的收敛动态实例，因为它们在从Q到S的任何路径上都不会遇到循环头。通俗地说，在Q处发散的线程在C的同一次迭代中在S处重新收敛。1
2
3
4
5
6
7
8
9
10
线程1
Entry
P1
Q1
R1
S1
P3
Q3
R3
S3
Exit
线程2
Entry
P2
Q2
S2
P4
Q4
R2
S4
Exit
注意
一般来说，对于不同的头，上述语句中的循环
C预计不是同一个循环。循环及其头是紧密耦合的；对于同一个最外层循环中的不同头，检测到的子循环可能不同。与上述示例相关的属性是，对于每个闭合路径，都存在一个包含该路径且其头位于该路径上的循环C。
必须为每个通过发散分支 B 及其汇合点 J 的闭合路径检查发散入口标准。由于 每个闭合路径都通过某个循环的头，这相当于检查每个包含 B 和 J 的循环 C。当 C 的头支配汇合点 J 时，从头到 J 的任何路径都不可能有入口，其中包括从 B 到 J 的任何发散路径。对于通过包含 C 的外循环的头的任何闭合路径，情况也是如此。
因此，发散入口标准可以保守地简化如下
对于发散分支
B及其汇合节点J，包含B和J的循环C中的节点是 m-收敛的，仅当
B严格支配J，或者，
C的头H严格支配J，或者，递归地，在
C内部存在满足相同条件的循环C'。
当 J 与 H 或 B 相同时，平凡支配不足以对发散路径的入口做出任何陈述。
到达循环的发散路径¶
该图显示了两个循环层次结构，其中发散分支在 Entry 中而不是在 Q 中。对于分别在 P 和 R 处进入闭合路径 P -> Q -> R -> S 的两个线程，沿路径生成的动态实例的收敛取决于 P 还是 R 是头。
当
P是头时的收敛。1
2
3
4
5
6
7
8
9
10
11
12
13
线程1
Entry
P1
Q1
R1
S1
P3
Q3
S3
Exit
线程2
Entry
R2
S2
P2
Q2
S2
P4
Q4
R3
S4
Exit
当
R是头时的收敛。1
2
3
4
5
6
7
8
9
10
11
12
线程1
Entry
P1
Q1
R1
S1
P3
Q3
S3
Exit
线程2
Entry
R2
S2
P2
Q2
S2
P4
…
Exit
因此，当发散路径从循环外部到达不可约循环的不同入口时，静态分析保守地报告循环中的每个节点都不是 m-收敛的。
可约循环¶
如果 C 是以 H 为头的可约循环，则在任何 DFS 中，H 必须是包含 C 的某个循环 C' 的头。独立于 DFS，除了 H 本身之外，没有到子图 C 的入口。因此，我们有以下结论
对于发散分支及其汇合点，发散入口标准在子图
C内部是显然满足的。当发散路径从外部到达子图
C时，它们的收敛始终由同一个头H决定。
显然，这只能在循环层次结构 T 中确定，其中 C 被检测为可约循环。在不同的循环层次结构 T' 中无法得出这样的结论，在 T' 中，C 是具有相同头的更大循环 C' 的一部分，但这与 T 中的结论不矛盾。
受控收敛¶
收敛控制令牌 为确定哪些线程在程序中的给定点收敛提供了显式语义。 这的影响体现在动态实例的 受控最大收敛关系 和静态实例的 受控 m-收敛 属性中。 LLVM 中实现的 一致性分析 包含了对支持收敛控制令牌的目标的支持。