3.6 循环变换

编译器执行多个循环重构变换，帮助改进程序中循环的并行化。其中某些变换还可以提高循环的单处理器执行性能。此部分描述编译器执行的变换。

3.6.1 循环分布

循环通常包含少量无法并行执行的语句以及许多可以并行执行的语句。循环分布旨在将顺序语句移到单独一个循环中，并将可并行化的语句收集到另一个循环中。以下示例描述了此过程：

示例 3-14 循环分布举例

for (i=0; i < n; i++) {
    x[i] = y[i] + z[i]*w[i];               /* S1 */
    a[i+1] = (a[i-1] + a[i] + a[i+1]/3.0;  /* S2 */
    y[i] = z[i] - x[i];                    /* S3 */
}

假定数组 x、y、w、a 和 z 不重叠，则语句 S1 和 S3 可以并行化，但语句 S2 不能并行化。以下示例说明了循环在拆分或分配到两个不同的循环中之后的外在形式。

示例 3-15 分布式循环

/* L1: parallel loop */
for (i=0; i < n; i++) {
    x[i] = y[i] + z[i]*w[i];              /* S1 */
    y[i] = z[i] - x[i];                   /* S3 */
}
/* L2: sequential loop */
for (i=0; i < n; i++) {
    a[i+1] = (a[i-1] + a[i] + a[i+1]/3.0; /* S2 */
}

在此变换之后，循环 L1 不包含任何阻止循环并行化的语句，因此可并行执行。然而，循环 L2 仍包含来自初始循环的不可并行化的语句。

循环分布并非始终有益或安全。编译器会进行分析，以确定分布的安全性和有益性。

3.6.2 循环合并

如果循环的粒度（或循环执行的工作量）很小，则分布的效果可能并不明显，原因是相对于循环开销，并行循环启动的开销太大。在这种情况下，编译器使用循环合并将多个循环合并到单个并行循环中，增大了循环的粒度。当具有相同行程计数的循环彼此相邻时，循环合并很方便且很安全。请看以下示例：

示例 3-16 工作量小的循环

/* L1: short parallel loop */
for (i=0; i < 100; i++) {
    a[i] = a[i] + b[i];        /* S1 */
}
/* L2: another short parallel loop */
for (i=0; i < 100; i++) {
    b[i] = a[i] * d[i];        /* S2 */
}

这两个短并行循环彼此相邻，可以安全地合并，如下所示：

示例 3-17 合并的两个循环

/* L3: a larger parallel loop */
for (i=0; i < 100; i++) {
    a[i] = a[i] + b[i];       /* S1 */
    b[i] = a[i] * d[i];       /* S2 */
}

新循环产生的开销是并行循环执行产生的开销的一半。循环合并在其他方面也很有帮助。例如，如果在两个循环中引用同一数据，则合并这两个循环可以改善引用环境。

然而，循环合并并非始终安全。如果循环合并创建之前并不存在的数据依赖性，则合并可能会导致错误执行。请看以下示例：

示例 3-18 不安全合并举例

/* L1: short parallel loop */
for (i=0; i < 100; i++) {
    a[i] = a[i] + b[i];      /* S1 */
}
/* L2: a short loop with data dependence */
for (i=0; i < 100; i++) {
    a[i+1] = a[i] * d[i];    /* S2 */
}

如果合并此示例中的循环，会产生语句 S2 至 S1 的数据依赖性。实际上，语句 S1 右边 a[i] 的值是在语句 S2 中计算的。如果未合并循环，则不会产生此依赖性。编译器执行安全性和有益性分析，以确定是否应执行循环合并。通常，编译器可以合并任意多个循环。以这种方式增大粒度有时可以大大改善循环，使其足从并行化中获益。

3.6.3 循环交换

并行化循环嵌套的最外层循环通常更有益，因为发生的开销很小。然而，由于此类循环可能携带依赖性，并行化最外层循环并非始终安全。以下示例对此情况进行了说明。

示例 3-19 不能并行化的嵌套循环

for (i=0; i <n; i++) {
    for (j=0; j <n; j++) {
            a[j][i+1] = 2.0*a[j][i-1];
    }
}

在本例中，具有索引变量 i 的循环不能并行化，原因是循环的两次连续迭代之间存在依赖性。这两个循环可以交换，并行循环（j 循环）变为外部循环：

示例 3-20 循环交换

for (j=0; j<n; j++) {
    for (i=0; i<n; i++) {
            a[j][i+1] = 2.0*a[j][i-1];
    }
}

交换后的循环只发生一次并行工作分配开销，而先前发生 n 次开销。编译器执行安全性和有益性分析，以确定是否执行循环交换。