4.5 检测与增强循环级并行性

程序中的循环，是本章和第 5 章讨论的许多并行形式的源泉。本节介绍用于发现程序中可供向量和 SIMD 体系结构利用的并行性的编译技术，以及支持这些技术的硬件。前面已经说明，GPU 将这项优化交给程序员，而不是 CUDA 编译器。我们将精确定义：

什么情况下循环是并行的或可向量化的，依赖如何阻止循环并行，以及怎样消除某些依赖。发现和调整循环级并行性，对利用 DLP、TLP，以及附录 H 中更积极的静态 ILP 方法（例如 VLIW）都至关重要。

循环级并行性通常在源代码层面或接近源代码的层面分析，而多数 ILP 分析发生在编译器生成指令之后。循环级分析需要判断不同迭代之间的操作数有哪些依赖。这里暂时只考虑数据依赖：某个操作数先被写入，随后又被读取。名称依赖也存在，可以用第 3 章的重命名技术消除。

循环级并行性分析重点判断：后续迭代的数据访问是否依赖前面迭代产生的值，这种依赖称为循环携带依赖。第 2、3 章中的多数例子没有循环携带依赖，因此具有循环级并行性。先看下面的源代码：

for (i=999; i>=0; i=i-1)
    x[i] = x[i] + s;

两次使用 x[i] 之间存在依赖，但它局限于单次迭代，不是循环携带依赖。不同迭代中连续使用 i 之间确实存在循环携带依赖，不过 i 是归纳变量（induction variable），这种依赖容易识别和消除。原书第 2 章 2.2 节曾在循环展开中展示如何消除归纳变量依赖，本节稍后还会介绍其他例子。

寻找循环级并行性需要识别循环、数组引用和归纳变量计算等结构，因此与机器码层面相比，编译器更容易在源代码或接近源代码的层面分析。下面看一个更复杂的例子。

例题

考虑下面的循环：

for (i=0; i<100; i=i+1) {
    A[i+1] = A[i] + C[i];   /* S1 *
    B[i+1] = B[i] + A[i+1]; /* S2 */
}

假设 A、B、C 是彼此不同、互不重叠的数组。实际上，数组有时可能相同或重叠；而且它们可能作为参数传给包含本循环的过程，所以判断数组是否相同或重叠，往往需要复杂的过程间程序分析。循环中的 S1、S2 之间有哪些数据依赖？

解答

1. 存在两类依赖。第一类是 S1 使用较早一次迭代中 S1 计算的值：迭代 i 计算 A[i+1]，迭代 i+1 读取它。S2 对 B[i]、B[i+1] 也有同样的关系。
2. 第二类是 S2 使用同一次迭代中 S1 计算的 A[i+1]。

这两类依赖不同，影响也不同。为看清差别，假设一次只存在其中一类。S1 依赖之前迭代中的 S1，所以它是循环携带依赖，迫使相邻迭代串行执行。

译注： 原代码 S1 的注释终止符缺少斜线；它不影响作者讨论的数据依赖，但使代码不能直接作为完整 C 程序编译。

第二类依赖，即 S2 依赖 S1，只在一次迭代内部发生，并非循环携带。因此，如果只有这一依赖，只要每次迭代内的两个语句保持顺序，多次迭代就能并行执行。原书 2.2 节中用展开暴露并行性的例子曾出现这类依赖。这样的迭代内部依赖很常见，使用链接的向量指令序列恰好就具有这种依赖。

也可能存在不妨碍并行化的循环携带依赖，下面就是一例。

例题

for (i=0; i<100; i=i+1) {
    A[i] = A[i] + B[i];    /* S1 */
    B[i+1] = C[i] + D[i];  /* S2 */
}

S1 和 S2 之间有哪些依赖？这个循环是否并行？如果不是，说明怎样使它并行。

解答

S1 使用前一次迭代中 S2 赋的值，因此 S2 到 S1 存在循环携带依赖。尽管如此，这个循环仍能并行化。与前例不同，这个依赖关系没有环：两个语句都不依赖自身，而且虽然 S1 依赖 S2，S2 却不依赖 S1。如果一个循环可以写成依赖关系无环的形式，就可以并行化，因为无环意味着依赖关系只规定了语句之间的偏序。

原循环虽然没有依赖环，仍需变换以符合这一偏序、暴露并行性。两个观察至关重要：

1. 不存在从 S1 到 S2 的依赖。否则就会形成环，循环不能并行。正因为没有这一依赖，交换两个语句不会影响 S2 的执行。
2. 第一次迭代时，S2 依赖循环开始前计算好的 B[0]。

由此可以将原循环替换为：

A[0] = A[0] + B[0];
for (i=0; i<99; i=i+1) {
    B[i+1] = C[i] + D[i];
    A[i+1] = A[i+1] + B[i+1];
}
B[100] = C[99] + D[99];

译注： 第 2 点原文确为“S2 depends on … B[0]”。按题中代码，读取 B[0] 的是 S1，S2 读取的是 C、D。

两个语句之间的依赖已不再由循环携带，因此只要保持每次迭代内的语句顺序，各次迭代就可以重叠执行。

分析应从找出所有循环携带依赖开始。这样的依赖信息是不精确的：它说明依赖可能存在。考虑：

for (i=0; i<100; i=i+1) {
    A[i] = B[i] + C[i]
    D[i] = A[i] * E[i]
}

这里第二次引用 A 不必翻译成加载指令，因为前一语句已经计算并保存了该值。第二次引用可以直接使用计算 A 时的寄存器。执行这项优化，必须知道两次引用总是指向同一内存地址，且中间没有访问并改动同一位置。通常，数据依赖分析只说明一次引用可能依赖另一次引用；要证明二者必定指向完全相同的地址，需要更复杂的分析。本例两次引用位于同一基本块，所以简单分析就足够。

译注： 原页上述两条赋值语句均未印出分号，代码按原样保留。

循环携带依赖经常以递推（recurrence）形式出现：某变量的值基于前一次或更早一次迭代中的值定义，通常依赖紧邻的前一次迭代，例如：

for (i=1; i<100; i=i+1) {
    Y[i] = Y[i-1] + Y[i];
}

识别递推重要，有两个原因：一些体系结构，尤其是向量计算机，提供执行递推的特殊支持；在 ILP 场景中，也仍可能利用相当数量的并行性。

寻找依赖

发现程序依赖，对于判断哪些循环可能并行，以及消除名称依赖都很重要。依赖分析的复杂性还来自 C、C++ 的数组和指针，以及 Fortran 的引用传参。标量变量引用显式给出名称，通常比较容易分析；指针和引用参数导致的别名，会给这种分析带来一些复杂性和不确定性。

编译器一般怎样检测依赖？几乎所有依赖分析算法都假定数组下标为仿射形式。简单地说，如果一维数组下标能写成 $a\times i+b$，其中 a、b 是常量，i 是循环索引变量，它就是仿射的。多维数组只有在各维下标都为仿射形式时，才满足这一条件。稀疏数组访问通常形如 x[y[i]]，是非仿射访问的主要例子之一。

因此，判断循环中对同一数组的两次引用是否依赖，等价于判断两个仿射函数在循环界限内的不同索引处能否取相同值。例如，循环以 $a\times i+b$ 为下标存储，以 $c\times i+d$ 为下标加载，i 从 m 到 n。若以下两个条件成立，就存在依赖：

1. 存在两个循环索引 j、k，都在循环范围内，即 $m\leq j\leq n$、$m\leq k\leq n$。
2. 循环先写入下标 $a\times j+b$ 的元素，随后又通过下标 $c\times k+d$ 读取同一元素，即 $a\times j+b=c\times k+d$。

一般而言，编译时无法总是判断依赖是否存在。例如，a、b、c、d 的值可能未知，甚至来自其他数组，于是无法确定依赖。另一些情况下，依赖在编译时可判定，但测试代价很高，例如访问取决于多层嵌套循环的迭代索引。不过，许多程序主要使用简单下标，a、b、c、d 都是常量，这时可以设计成本合理的编译时测试。

一个简单且足以证明不存在依赖的测试，是最大公约数 GCD 测试。它基于这样的事实：若存在循环携带依赖，$\gcd(c,a)$ 必须整除 $d-b$。所谓整数 x 整除整数 y，是指 y/x 得到整数商且没有余数。

例题

用 GCD 测试判断下面的循环是否存在依赖：

for (i=0; i<100; i=i+1) {
    X[2*i+3] = X[2*i] * 5.0;
}

解答

$a=2,b=3,c=2,d=0$，因此 $\gcd(a,c)=2$，而 $d-b=-3$。2 不能整除 −3，所以不可能存在依赖。

GCD 测试能够充分保证依赖不存在；但即使满足其整除条件，也未必真的存在依赖，例如该测试没有考虑循环边界。

一般情况下，判断依赖是否真正存在是 NP 完全问题。不过，在实践中，许多常见情况可以低成本地精确分析。近年来，按通用性和成本逐层提高的一组精确测试，已经显示出准确而高效的效果。“精确”测试指能准确判定依赖是否存在；虽然一般情况是 NP 完全的，受限情形下仍有成本低得多的精确测试。

编译器除了检测依赖，还希望对依赖分类，以识别名称依赖，并在编译时通过重命名与复制消除。

例题

下面的循环包含多种依赖。找出所有真依赖、输出依赖和反依赖，并通过重命名消除输出依赖和反依赖。

for (i=0; i<100; i=i+1) {
    Y[i] = X[i] / c;  /* S1 */
    X[i] = X[i] + c;  /* S2 */
    Z[i] = Y[i] + c;  /* S3 */
    Y[i] = c - Y[i];  /* S4 */
}

解答

1. 四条语句之间，由 Y[i] 产生从 S1 到 S3、从 S1 到 S4 的真依赖。它们不是循环携带依赖，因此不妨碍循环并行，但要求 S3、S4 等待 S1 完成。
2. 由 X[i] 产生从 S1 到 S2 的反依赖。
3. 由 Y[i] 产生从 S3 到 S4 的反依赖。
4. 由 Y[i] 产生从 S1 到 S4 的输出依赖。

下列版本消除了这些假依赖：

for (i=0; i<100; i=i+1 {
    T[i] = X[i] / c;   /* 将 Y 重命名为 T，消除输出依赖 */
    X1[i] = X[i] + c;  /* 将 X 重命名为 X1，消除反依赖 */
    Z[i] = T[i] + c;   /* 将 Y 重命名为 T，消除反依赖 */
    Y[i] = c - T[i];
}

循环后，变量 X 已重命名为 X1。编译器可在后续代码中直接用 X1 替换 X，因此这里不需要真正的复制操作，通过名称替换或寄存器分配即可完成；其他情况下，重命名仍可能需要复制。

译注： 原页重命名后代码的 for 头缺少右括号，按原样保留。补上该右括号才是完整 C 语法；这不改变示例的依赖分析。

依赖分析既是利用并行性的关键技术，也是第 2 章分块等程序变换的基础。有效地为向量计算机、SIMD 计算机或多处理器编译程序，都高度依赖它。其主要局限是适用范围有限：通常只分析同一循环嵌套内、使用仿射下标函数的引用。因此，很多情形下，面向数组的依赖分析无法回答所需问题。例如，用指针而非数组下标访问时，分析会困难得多；这也是许多面向并行计算机的科学应用仍偏好 Fortran 而不是 C/C++ 的原因之一。跨过程调用分析引用也极为困难。因此，分析顺序语言代码固然重要，我们仍需要 OpenMP、CUDA 等显式编写并行循环的方法。

消除有依赖的计算

前面说过，递推是有依赖计算的重要形式，点积就是典型例子：

for (i=9999; i>=0; i=i-1)
    sum = sum + x[i] * y[i];

循环在变量 sum 上有循环携带依赖，所以不能并行。但可以把它变换为两个循环，一个完全并行，另一个部分并行。先执行完全并行的部分：

for (i=9999; i>=0; i=i-1)
    sum[i] = x[i] * y[i];

sum 从标量扩展成向量，这种变换称为标量扩展（scalar expansion），它使新循环完全并行。不过，随后还必须执行归约步骤，把向量各元素相加：

for (i=9999; i>=0; i=i-1)
    finalsum = finalsum + sum[i];

这个循环虽然不并行，却具有称为归约的特殊结构。归约在线性代数中很常见，也是第 6 章仓库级计算机所使用的主要并行原语 MapReduce 的关键部分。一般而言，任何函数都可以作为归约运算符，常见例子包括 max 和 min。

向量和 SIMD 体系结构有时用专门硬件处理归约，使其比标量方式快得多。

这些加速器采用的技术类似多处理器环境中的做法。一般变换适用于任意处理器数量；为简单起见，假设有 10 个处理器。求和归约的第一步中，每个处理器执行如下代码，p 为 0～9 的处理器编号：

for (i=999; i>=0; i=i-1)
    finalsum[p] = finalsum[p] + sum[i+1000*p];

10 个处理器各自累加 1000 个元素，这些工作完全并行；随后，一个简单的标量循环再把最后 10 个部分和相加。向量处理器和 SIMD 处理器采用类似方法。

需要注意，上述变换依赖加法结合律。无限范围、无限精度的算术满足结合律，计算机算术却未必满足：整数运算的范围有限，浮点运算的范围和精度都有限。因此，这些重组技术偶尔可能产生错误行为，尽管这种情况较少见。出于这一原因，多数编译器要求显式启用依赖结合律的优化。

译注： 本节引用“第 2 章 2.2 节”；但在本版中，循环展开的相应讨论属于第 3 章，而第 2 章讨论存储层次结构。