H.2 检测并增强循环级并行性

循环级并行性通常在源代码层面或接近源代码的层面分析；大部分 ILP 分析则在编译器已生成指令后进行。循环级分析需要确定：跨越同一循环的不同迭代时，操作数之间存在哪些依赖。

现在只考虑数据依赖，即某个操作数先被写入，随后又被读取。名称依赖也存在，可以用第 3 章讨论的重命名技术消除。

循环级并行性分析的重点是：后续迭代的数据访问，是否依赖更早迭代产生的数据值。这种依赖称为循环携带依赖（loop-carried dependence）。3.2 节的大多数例子没有这种依赖，因此具有循环级并行性。先看一个源代码层面的并行循环：

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

这里对 x[i] 的两次使用存在依赖，但都在同一次迭代内，因而不是循环携带的。不同迭代中对 i 的连续使用确实具有循环携带依赖，但它涉及归纳变量，容易识别和消除。3.2 节在展开循环时已展示如何消除归纳变量依赖，本节后面还有其他例子。

发现循环级并行性，需要识别循环、数组访问和归纳变量计算等结构。因此，相比机器代码层面，在源代码或接近源代码的层面进行分析，编译器会容易得多。下面看一个复杂些的例子。

例题

考虑如下循环：

for (i=1; 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，因此它是循环携带依赖，会迫使循环的连续迭代串行执行。

第二种依赖——S2 依赖 S1——发生在同一次迭代内，不由循环携带。如果只有这种依赖，只要保持每次迭代内两条语句的顺序，多次迭代就可以并行。3.2 节有这样的例子，循环展开能够暴露其并行性。

也可能存在不妨碍并行化的循环携带依赖，如下例所示。

例题

考虑如下循环：

for (i=1; 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. 第一次迭代中，S1 依赖的是循环开始之前就已计算好的 B[1]。

因此可将原循环替换为：

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

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

分析首先要找出所有循环携带依赖。但这种依赖信息并不精确：它通常只告诉我们依赖可能存在。考虑：

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

第二次访问 A 不必翻译成加载指令，因为该值刚由前一条语句计算并存储。可以直接引用保存计算结果的寄存器。进行这种优化，必须知道两次访问始终指向同一地址，且中间没有对该位置的其他访问。普通数据依赖分析只说明一次访问可能依赖另一次；要证明两次访问必定是完全相同的地址，需要更复杂的分析。这里，两次访问位于同一基本块，简单版本的分析就足够了。

循环携带依赖常表现为递推（recurrence）：

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

递推是指某个变量的定义依赖此前迭代中的变量值，通常就是上一次迭代，如上例。识别递推有两个重要原因：某些体系结构，特别是向量计算机，对递推执行有专门支持；某些递推也能提供相当数量的并行性。看下面的循环：

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

在迭代 i 中，循环访问元素 i-5，称其依赖距离为 5。许多有循环携带依赖的循环，其依赖距离为 1。距离越大，展开循环可获得的潜在并行性越多。展开第一个距离为 1 的循环，连续语句仍然相互依赖；单条机器指令之间虽还有一些并行性，但不多。展开距离为 5 的循环，则会得到五条互不依赖的语句，因此 ILP 多得多。虽然距离为 1 的情形很常见，较大距离也会出现，并可能提供足够并行性，使处理器持续忙碌。

寻找依赖

发现程序依赖，是做好三项工作的重要组成部分：有效调度代码、确定哪些循环具有并行性，以及消除名称依赖。困难来自 C、C++ 等语言中的数组和指针，以及 FORTRAN 的引用传参。标量变量显式引用名字，通常容易分析；但指针和引用参数引入的别名，会带来复杂性与不确定性。

编译器一般如何检测依赖？几乎所有依赖分析算法都假定数组下标是仿射的。最简单地说，如果一维数组下标可写为 $a i+b$，其中 $a,b$ 是常量、$i$ 是循环索引变量，就称其为仿射下标。多维数组如果每一维下标都是仿射的，整个下标也是仿射的。稀疏数组中常见的 x[y[i]] 是非仿射访问的主要例子之一。

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

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

一般不能在编译时确定依赖是否存在。例如，$a,b,c,d$ 的值可能未知，甚至来自其他数组；这时无法作出判断。另一些情形虽可在编译时判定，检测代价却很高，例如访问取决于多重嵌套循环的迭代索引。不过，许多程序主要使用简单下标，$a,b,c,d$ 都是常量，这时可以设计开销合理的编译时依赖测试。

一种能充分证明依赖不存在的简单方法是最大公约数测试（GCD test）。它依据这样一个事实：若存在循环携带依赖，$\gcd(c,a)$ 必须整除 $d-b$。所谓整数 $x$ 整除整数 $y$，就是 $y/x$ 的商为整数且无余数。

例题

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

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

循环之后，变量 X 已重命名为 X1；后续代码中，编译器可以直接把 X 替换为 X1。这里不必真的复制数据，通过名字替换或寄存器分配即可实现重命名。但另一些情况下，重命名确实需要复制操作。

依赖分析是开发并行性的关键技术。在指令层面，它提供调度时交换访存操作、判断循环展开收益所需的信息；在循环层面，它是检测并行性的基本工具。有效地把程序编译到向量计算机或多处理器，都极为依赖它。

主要局限是，数组依赖分析只适用于受限情况：访问须在同一个循环嵌套中，并使用仿射下标。许多情形下，它无法告诉我们想知道的信息，例如：

• 通过指针而不是数组下标访问对象，下文还将讨论。
• 通过另一个数组间接索引；许多稀疏数组表示都如此。
• 某些输入值可能造成依赖，但实际运行中的输入从不取这些值，因此实际没有依赖。
• 优化不仅要知道依赖是否可能存在，还要知道某次读取究竟依赖这个变量的哪一次写入。

处理指针程序需要另一类分析，通常称为指向分析（points-to analysis），参见 Wilson 与 Lam［1995］。其核心问题是：两个指针能否指向同一地址？对于复杂的动态数据结构，这极难回答。例如，要判断程序某一点上的两个指针是否可能指向同一链表节点，一般不可判定，实际也很难分析。但可能回答一个较简单的问题：两个指针能否指向同一条链表的节点，即便节点本身不同？这种较受限的分析，对于调度通过指针完成的访存仍很有用。

指向分析的基本方法依赖三类信息：

1. 类型信息： 限制指针可以指向什么。
2. 对象分配或取地址时的信息： 同样用来限制指向范围。例如，p 始终指向某一源代码行分配的对象，而 q 从不指向该对象，那么二者不可能指向同一对象。
3. 指针赋值信息： 例如，若 p 可能被赋为 q，那么 p 就可能指向 q 能指向的任何对象。

指针分析已在几类情形中成功应用，而且很有用：

• 用指针传递对象地址时，可以确定它可能引用的对象集合。一个重要用途是判断两个指针参数是否可能指向同一对象。
• 指针可能指向几种类型之一时，有时能在程序不同位置确定它所指数据对象的类型。
• 通常能够区分只可能指向局部对象的指针与可能指向全局对象的指针。

有两类限制影响大型程序的精确依赖分析。第一类来自算法适用范围。困难常常不是依赖分析本身不够精确，而是它不适用。例如，程序任意使用指针、对其进行算术运算时，指针依赖分析实际上就几乎无从进行。

第二类是必须跨越过程边界，才能取得准确行为信息。例如，一个过程接收两个指针参数，要判断它们的值是否可能相同，就需要跨过程分析。这称为过程间分析，远比单个过程内部的分析复杂。不同于单个循环嵌套内的数组下标分析，指向分析通常需要过程间分析。原因很简单：若分析某个程序片段时，不知道两个指针在入口处的任何信息，就只能保守假定最坏情况，即它们可能指向同一对象，但又不保证指向同一对象。这种不确定性很可能一路传播，使结果失去用途。

实际程序中，取得完全准确的过程间信息往往代价太高，因此编译器通常采用近似，所得信息又可能太不精确而无法利用。

Java 等强类型现代语言使依赖分析更容易；与此同时，大量使用过程和抽象数据类型组织程序，又增加了难度。不过，随着算法不断改进，以及指针依赖分析越来越重要，我们预期这一重要问题仍会持续取得进展。

消除相互依赖的计算

编译器可以降低相互依赖计算的影响，获得更多 ILP。关键技术是通过回代消除或减少依赖计算；这会增加并行性，有时也会增加计算量。它既可用于基本块内，也可用于循环，下面分别讨论。

在基本块内，可用表达式代数化简，以及消除值复制的复制传播（copy propagation），把以下序列：

DADDUI R1,R2,#4
DADDUI R1,R1,#4

简化成：

DADDUI R1,R2,#8

这里假定 R1 没有其他用途。3.2 节展开循环时合并多次数组索引递增，以及把递增操作移过访存操作，都是这种优化的例子。

上例实际消除了计算，但有时也会为了增加代码并行性而保留、甚至增加操作的数量。这类优化称为树高缩减（tree height reduction）：表示计算的树变得更宽、更矮。考虑：

ADD R1,R2,R3
ADD R4,R1,R6
ADD R8,R4,R7

每条指令都依赖紧邻的前一条，至少需三个执行周期。利用结合律，可以改写为：

ADD R1,R2,R3
ADD R4,R6,R7
ADD R8,R1,R4

该序列只需两个执行周期。展开循环时，这类优化机会经常出现。

无限范围、无限精度的算术满足结合律，但计算机算术不一定满足：整数范围有限，浮点数则范围与精度都有限。因此，这种重组有时会导致错误行为，虽然并不常见。出于这一原因，多数编译器要求显式启用依赖结合律的优化。

循环展开后，代数优化对于降低递推依赖的影响很重要。递推表达式在某次迭代中的值，由依赖此前迭代的函数给出。展开含递推的循环后，有时能通过代数优化，使每次展开后的迭代只需计算一次递推。常见形式来自显式语句，例如：

sum = sum + x;

假定把这个循环展开五次，五次迭代的 x 分别为 x1 到 x5，每组展开结束时可写为：

sum = sum + x1 + x2 + x3 + x4 + x5;

未经优化时，需要五次串行依赖的操作。但可改写为：

sum = ((sum + x1) + (x2 + x3)) + (x4 + x5);

这样，最长依赖链只需三个操作。

递推也来自隐式计算，例如数组索引：每个下标都要转换为根据循环索引计算的地址。通过展开与代数优化，同样可以尽量减少这些相互依赖的计算。

译注：本节代码中原书缺失的语句分号，以及重命名例子 for 首行缺失的右圆括号，已按完整语法补齐；变量、表达式和循环界限均未改变。