3.3 数据依赖性和干扰

C 编译器通过分析程序中的循环来确定并行执行循环的不同迭代是否安全。分析的目的是确定循环的两次迭代之间是否会相互干扰。通常，如果变量的一次迭代读取某个变量而另一次迭代正在写入该变量，会发生此问题。考虑以下程序片段：

示例 3-1 带依赖性的循环

for (i=1; i < 1000; i++) {
    sum = sum + a[i]; /* S1 */
}

在此示例中，任意两次连续迭代，第 i 次和第 i+1 次，将写入和读取同一变量 sum。因此，为了并行执行这两次迭代，需要以某种形式锁定该变量。否则，允许并行执行这两次迭代不安全。

然而，使用锁定会产生可能降低程序运行速度的开销。在上述示例中，C 编译器将不会如常并行化循环，原因是循环的两次迭代之间存在数据依赖性。考虑另一个示例：

示例 3-2 不带依赖性的循环

for (i=1; i < 1000; i++) {
    a[i] = 2 * a[i]; /* S1 */
}

在此情况下，循环的每次迭代均引用不同的数组元素。因此，循环的不同迭代可以按任意顺序执行。由于不同迭代的两个数据元素不可能相互干扰，因此它们可以并行执行而无需任何锁定。

编译器为确定一个循环的两次不同迭代是否引用相同变量而执行的分析称为数据依赖性分析。如果其中一个引用写入变量，数据依赖性阻止循环并行化。编译器执行的数据依赖性分析有三种结果：

• 在存在依赖性的情况下，并行执行循环是不安全的。

• 在不存在依赖性的情况下，可以使用任意数量的处理器安全地并行执行循环。

• 无法确定依赖性。为安全起见，编译器假定依赖性可能会阻止并行执行循环，并且不会并行化循环。

在以下示例中，循环的两次迭代是否写入数组 a 的同一元素取决于数组 b 是否包含重复元素。除非编译器可以确定实际情况，否则它必须假定可能存在依赖性并且不会并行化循环。

示例 3-3 可能包含依赖性的循环

for (i=1; i < 1000; i++) {
    a[b[i]] = 2 * a[i];
}

3.3.1 并行执行模型

循环的并行执行由 Solaris 线程完成。启动程序的初始执行的线程称为主线程。程序启动时，主线程创建多个从属线程，如下图所示。程序结束时，所有从属线程均终止。从属线程的创建只进行一次，以使开销减至最小。

图 3-1 主线程和从属线程

程序启动后，主线程开始执行程序，而从属线程保持空闲等待状态。当主线程遇到并行循环时，循环的不同迭代将会在启动循环执行的从属线程和主线程之间分布。在每个线程完成其块的执行之后，将与剩余线程保持同步。此同步点称为障碍。在所有线程完成其工作并到达障碍之前，主线程不能继续执行程序的剩余部分。从属线程在到达障碍之后进入等待状态，等待分配更多的并行工作，而主线程继续执行该程序。

在此期间，可发生多种开销：

• 同步和工作分配

• 边界同步

对于某些并行循环，执行的有用工作量不足以证明开销。对于此类循环，其运行速度会明显减慢。在下图中，循环是并行化的。然而，障碍（以水平条表示）带来大量开销。如图所示，障碍之间的工作串行或并行执行。并行执行循环所需的时间比主线程和从属线程在障碍处同步所需的时间少得多。

图 3-2 循环的并行执行

3.3.2 私有标量和私有数组

对于某些数据依赖性，编译器仍能够并行化循环。考虑以下示例。

示例 3-4 带依赖性的可并行化循环

for (i=1; i < 1000; i++) {
    t = 2 * a[i];           /* S1 */
    b[i] = t;               /* S2 */
}

在本例中，假定数组 a 和 b 为非重叠数组，而由于变量 t 的存在而使任意两次迭代之间存在数据依赖性。在第一次迭代和第二次迭代时执行以下语句。

示例 3-5 第一次迭代和第二次迭代

t = 2*a[1];  /* 1 */
b[1] = t;    /* 2 */
t = 2*a[2];  /* 3 */
b[2] = t;    /* 4 */

由于第一个语句和第三个语句会修改变量 t，因此编译器无法并行执行它们。不过，由于 t 的值始终在同一次迭代中计算并使用，因此编译器可以对每次迭代使用 t 的一个单独副本。此方法消除了不同迭代之间由于此类变量而产生的干扰。事实上，变量 t 用作执行迭代的每个线程的私有变量，如下例所示。

示例 3-6 变量 t 作为每个线程的私有变量

for (i=1; i < 1000; i++) {
    pt[i] = 2 * a[i];       /* S1 */
    b[i] = pt[i];           /* S2 */
}

在此示例中，每个标量变量引用 t 被数组引用 pt 替换。现在，每次迭代使用 pt 的不同元素，消除了任意两次迭代之间的所有数据依赖性。本示例产生的一个问题是可能导致数组非常大。在实际运用中，编译器为参与循环执行的每个线程只分配变量的一个副本。事实上，每个此类变量是线程的私有变量。

编译器还可以私有化数组变量，以便为循环的并行执行创造机会。请看以下示例：

示例 3-7 带数组变量的可并行化循环

for (i=1; i < 1000; i++) {
    for (j=1; j < 1000; j++) {
            x[j] = 2 * a[i];        /* S1 */
            b[i][j] = x[j];         /* S2 */
    }
}

在此示例中，外部循环的不同迭代修改数组 x 的相同元素，因此外部循环不能并行化。不过，如果执行外部循环迭代的每个线程均具有整个数组 x 的私有副本，那么外部循环的任意两次迭代之间不会发生干扰。以下示例对这一点进行了说明。

示例 3-8 使用私有化数组的可并行化循环

for (i=1; i < 1000; i++) {
    for (j=1; j < 1000; j++) {
            px[i][j] = 2 * a[i];    /* S1 */
            b[i][j] = px[i][j];     /* S2 */
    }
}

如私有标量的情形一样，只需将数组最多展开为系统中执行的线程数。此扩展由编译器自动完成，方式是在每个线程的私有空间中分配初始数组的一个副本。

3.3.3 返回存储

变量私有化对改进程序中的并行性十分有用。然而，如果在循环外部引用私有变量，则编译器需要确认私有变量具有正确的值。请看以下示例：

示例 3-9 使用返回存储的并行化循环

for (i=1; i < 1000; i++) {
    t = 2 * a[i];           /* S1 */
    b[i] = t;               /* S2 */
}
x = t;                      /* S3 */

在此示例中，在语句 S3 中引用的 t 值是循环计算的最终 t 值。在变量 t 私有化并且循环完成执行之后，需要重新将 t 的正确值存储到初始变量中。此过程称为返回存储，通过将最终迭代中 t 的值重新复制到变量 t 的原始位置实现。在许多情况下，编译器会自动执行此操作，但有时不容易计算最后一个值。

示例 3-10 不能使用返回存储的循环

for (i=1; i < 1000; i++) {
    if (c[i] > x[i] ) {         /* C1 */
            t = 2 * a[i];           /* S1 */
            b[i] = t;               /* S2 */
    }
}
x = t*t;                       /* S3 */

正确执行后，语句 S3 中的 t 值并不是循环最终迭代中的 t 值。事实上，它是条件 C1 为真时的最后一次迭代。通常，计算 t 的最终值会比较困难。在与此示例类似的情况下，编译器不会并行化循环。

3.3.4 约简变量

有时循环的迭代之间存在真正的依赖性，通过简单地私有化导致依赖性的变量并不能除去该依赖性。例如，查看以下从一次迭代到下一次迭代累计值的代码。

示例 3-11 可以并行化的循环

for (i=1; i < 1000; i++) {
    sum += a[i]*b[i]; /* S1 */
}

在此示例中，循环计算两个数组的向量乘积，并将结果赋给一个称为 sum 的公共变量。该循环不能以简单的方式并行化。编译器可以利用语句 S1 中计算的关联特性，并为每个线程分配一个称为 psum[i] 的私有变量。变量 psum[i] 的每个副本均初始化为 0。每个线程以自己的变量 psum[i] 副本计算自己的部分和。执行循环之前，所有部分和均加到初始变量 sum 上。在本示例中，变量 sum 称为约简变量，因为它计算和约简。然而，将标量变量提升为约简变量存在的危险是：累计舍入值的方式会更改 sum 的最终值。只有在您专门授权这样做时，编译器才执行该变换。