test

Sun Studio 12：C 用户指南

3.4 数据依赖性和干扰

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

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


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

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

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

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


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

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

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

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

示例 3–3 可能包含也可能不包含依赖性的循环


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

3.4.1 并行执行模型

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

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

显示派生从属线程的主线程的图。

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

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

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

图 3–2 循环的并行执行

显示并行执行循环的图。

3.4.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 */
}

3.4.2 私有标量和私有数组中的示例与3.4 数据依赖性和干扰中的示例基本相同，但是每个标量变量引用 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 */
    }
}

在3.4.2 私有标量和私有数组中，外部循环的不同迭代修改数组 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.4.3 返回存储

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

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


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

在3.4.3 返回存储中，在语句 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.4.4 约简变量

有时循环的迭代之间存在真正的依赖性，而导致依赖性的变量并不能简单地私有化。例如，从一次迭代到下一次迭代累计值时，会出现这种情况。

示例 3–11 可以或不可以并行化的循环


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

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