对于某些数据依赖性,编译器仍能够并行化循环。考虑以下示例。
for (i=1; i < 1000; i++) { t = 2 * a[i]; /* S1 */ b[i] = t; /* S2 */ } |
在本例中,假定数组 a 和 b 为非重叠数组,而由于变量 t 的存在而使任意两次迭代之间存在数据依赖性。在第一次迭代和第二次迭代时执行以下语句。
t = 2*a[1]; /* 1 */ b[1] = t; /* 2 */ t = 2*a[2]; /* 3 */ b[2] = t; /* 4 */ |
由于第一个语句和第三个语句会修改变量 t,因此编译器无法并行执行它们。不过,t 的值始终在同一次迭代中计算并使用,因此编译器可以对每次迭代使用 t 的一个单独副本。这消除了不同迭代之间由于此类变量而产生的干扰。事实上,我们已使变量 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 的不同元素,因此消除了任意两次迭代之间的所有数据依赖性。当然,本示例产生的一个问题是可能导致数组非常大。在实际运用中,编译器为参与循环执行的每个线程只分配变量的一个副本。事实上,每个此类变量是线程的私有变量。
编译器还可以私有化数组变量,以便为循环的并行执行创造机会。请看以下示例:
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 的私有副本,那么外部循环的任意两次迭代之间不存在干扰。这种情形说明如下:
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 */ } } |
如私有标量的情形一样,不必要为所有迭代展开数组,而只需要达到系统中执行的线程数。这由编译器自动完成,方式是在每个线程的私有空间中分配初始数组的一个副本。