对于某些数据依赖性,编译器仍能够并行化循环。考虑以下示例。
示例 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 */ } }
如私有标量的情形一样,只需将数组最多展开为系统中执行的线程数。此扩展由编译器自动完成,方式是在每个线程的私有空间中分配初始数组的一个副本。