# 4.5 检测与增强循环级并行性 程序中的循环，是本章和第 5 章讨论的许多并行形式的源泉。本节介绍用于发现程序中可供向量和 SIMD 体系结构利用的并行性的编译技术，以及支持这些技术的硬件。前面已经说明，GPU 将这项优化交给程序员，而不是 CUDA 编译器。我们将精确定义： 什么情况下循环是并行的或可向量化的，依赖如何阻止循环并行，以及怎样消除某些依赖。发现和调整循环级并行性，对利用 DLP、TLP，以及附录 H 中更积极的静态 ILP 方法（例如 VLIW）都至关重要。 循环级并行性通常在源代码层面或接近源代码的层面分析，而多数 ILP 分析发生在编译器生成指令之后。循环级分析需要判断不同迭代之间的操作数有哪些依赖。这里暂时只考虑**数据依赖**：某个操作数先被写入，随后又被读取。名称依赖也存在，可以用第 3 章的重命名技术消除。 循环级并行性分析重点判断：后续迭代的数据访问是否依赖前面迭代产生的值，这种依赖称为**循环携带依赖**。第 2、3 章中的多数例子没有循环携带依赖，因此具有循环级并行性。先看下面的源代码： ~~~c for (i=999; i>=0; i=i-1) x[i] = x[i] + s; ~~~ 两次使用 `x[i]` 之间存在依赖，但它局限于单次迭代，不是循环携带依赖。不同迭代中连续使用 i 之间确实存在循环携带依赖，不过 i 是**归纳变量**（induction variable），这种依赖容易识别和消除。原书第 2 章 2.2 节曾在循环展开中展示如何消除归纳变量依赖，本节稍后还会介绍其他例子。 寻找循环级并行性需要识别循环、数组引用和归纳变量计算等结构，因此与机器码层面相比，编译器更容易在源代码或接近源代码的层面分析。下面看一个更复杂的例子。 **例题** 考虑下面的循环： ~~~c 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 节中用展开暴露并行性的例子曾出现这类依赖。这样的迭代内部依赖很常见，使用链接的向量指令序列恰好就具有这种依赖。 也可能存在不妨碍并行化的循环携带依赖，下面就是一例。 **例题** ~~~c 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]`。 由此可以将原循环替换为： ~~~c 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。 两个语句之间的依赖已不再由循环携带，因此只要保持每次迭代内的语句顺序，各次迭代就可以重叠执行。 分析应从找出所有循环携带依赖开始。这样的依赖信息是**不精确**的：它说明依赖*可能*存在。考虑： ~~~c for (i=0; i<100; i=i+1) { A[i] = B[i] + C[i] D[i] = A[i] * E[i] } ~~~ 这里第二次引用 A 不必翻译成加载指令，因为前一语句已经计算并保存了该值。第二次引用可以直接使用计算 A 时的寄存器。执行这项优化，必须知道两次引用*总是*指向同一内存地址，且中间没有访问并改动同一位置。通常，数据依赖分析只说明一次引用*可能*依赖另一次引用；要证明二者*必定*指向完全相同的地址，需要更复杂的分析。本例两次引用位于同一基本块，所以简单分析就足够。 > **译注：** 原页上述两条赋值语句均未印出分号，代码按原样保留。 循环携带依赖经常以**递推**（recurrence）形式出现：某变量的值基于前一次或更早一次迭代中的值定义，通常依赖紧邻的前一次迭代，例如： ~~~c 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 测试判断下面的循环是否存在依赖： ~~~c 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 完全的，受限情形下仍有成本低得多的精确测试。 编译器除了检测依赖，还希望对依赖分类，以识别名称依赖，并在编译时通过重命名与复制消除。 **例题** 下面的循环包含多种依赖。找出所有真依赖、输出依赖和反依赖，并通过重命名消除输出依赖和反依赖。 ~~~c 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 的输出依赖。 下列版本消除了这些假依赖： ~~~c 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 等显式编写并行循环的方法。 ## 消除有依赖的计算 前面说过，递推是有依赖计算的重要形式，点积就是典型例子： ~~~c for (i=9999; i>=0; i=i-1) sum = sum + x[i] * y[i]; ~~~ 循环在变量 `sum` 上有循环携带依赖，所以不能并行。但可以把它变换为两个循环，一个完全并行，另一个部分并行。先执行完全并行的部分： ~~~c for (i=9999; i>=0; i=i-1) sum[i] = x[i] * y[i]; ~~~ `sum` 从标量扩展成向量，这种变换称为**标量扩展**（scalar expansion），它使新循环完全并行。不过，随后还必须执行**归约**步骤，把向量各元素相加： ~~~c for (i=9999; i>=0; i=i-1) finalsum = finalsum + sum[i]; ~~~ 这个循环虽然不并行，却具有称为归约的特殊结构。归约在线性代数中很常见，也是第 6 章仓库级计算机所使用的主要并行原语 MapReduce 的关键部分。一般而言，任何函数都可以作为归约运算符，常见例子包括 max 和 min。 向量和 SIMD 体系结构有时用专门硬件处理归约，使其比标量方式快得多。 这些加速器采用的技术类似多处理器环境中的做法。一般变换适用于任意处理器数量；为简单起见，假设有 10 个处理器。求和归约的第一步中，每个处理器执行如下代码，p 为 0～9 的处理器编号： ~~~c 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 章讨论存储层次结构。