C 编译器为那些它确定可以安全进行并行化的循环生成并行代码。通常,这些循环具有彼此独立的迭代。对于此类循环,迭代以什么顺序执行或者是否并行执行并不重要。虽然不是全部,但是许多向量循环都属于此种类。
由于 C 中使用别名的方式,难以确定并行化的安全。为帮助编译器,Oracle Developer Studio C 提供了 pragma 和附加指针限定,以提供程序员知道、但编译器无法确定的别名信息。有关更多信息,请参见基于类型的别名分析。
以下示例说明了如何启用和控制并行化 C:
% cc -fast -xO4 -xautopar example.c -o example
此编译器命令将生成一个称为 example 的可正常执行的可执行程序。要了解如何利用多处理器执行,请参见-xautopar。
C 编译器通过分析程序中的循环来确定并行执行循环的不同迭代是否安全。分析的目的是确定循环的两次迭代之间是否会相互干扰。通常,如果循环的一次迭代读取某个变量而另一次迭代正在写入该变量,会发生此问题。考虑以下程序片段:
示例 2 带依赖性的循环for (i=1; i < 1000; i++) { sum = sum + a[i]; /* S1 */ }
在此示例中,任意两次连续迭代,第 i 次和第 i+1 次,将写入和读取同一变量 sum。因此,为了并行执行这两次迭代,需要以某种形式锁定该变量。否则,允许并行执行这两次迭代不安全。
然而,使用锁定会产生可能降低程序运行速度的开销。在上述示例中,C 编译器将不会如常并行化循环,原因是循环的两次迭代之间存在数据依赖性。考虑另一个示例:
示例 3 不带依赖性的循环for (i=1; i < 1000; i++) { a[i] = 2 * a[i]; /* S1 */ }
在此情况下,循环的每次迭代均引用不同的数组元素。因此,循环的不同迭代可以按任意顺序执行。由于不同迭代的两个数据元素不可能相互干扰,因此它们可以并行执行而无需任何锁定。
编译器为确定一个循环的两次不同迭代是否引用相同变量而执行的分析称为数据依赖性分析。如果其中一个引用写入变量,数据依赖性阻止循环并行化。编译器执行的数据依赖性分析有三种结果:
在存在依赖性的情况下,并行执行循环是不安全的。
在不存在依赖性的情况下,可以使用任意数量的处理器安全地并行执行循环。
无法确定依赖性。为安全起见,编译器假定依赖性可能会阻止并行执行循环,并且不会并行化循环。
在以下示例中,循环的两次迭代是否写入数组 a 的同一元素取决于数组 b 是否包含重复元素。除非编译器可以确定实际情况,否则它必须假定可能存在依赖性并且不会并行化循环。
示例 4 可能包含依赖性的循环for (i=1; i < 1000; i++) { a[b[i]] = 2 * a[i]; }
对于某些数据依赖性,编译器仍能够并行化循环。考虑以下示例。
示例 5 带依赖性的可并行化循环for (i=1; i < 1000; i++) { t = 2 * a[i]; /* S1 */ b[i] = t; /* S2 */ }
在本例中,假定数组 a 和 b 为非重叠数组,而由于变量 t 的存在而使任意两次迭代之间存在数据依赖性。在第一次迭代和第二次迭代时执行以下语句。
示例 6 第一次迭代和第二次迭代t = 2*a[1]; /* 1 */ b[1] = t; /* 2 */ t = 2*a[2]; /* 3 */ b[2] = t; /* 4 */
由于第一个语句和第三个语句会修改变量 t,因此编译器无法并行执行它们。不过,由于 t 的值始终在同一次迭代中计算并使用,因此编译器可以对每次迭代使用 t 的一个单独副本。此方法消除了不同迭代之间由于此类变量而产生的干扰。事实上,变量 t 用作执行迭代的每个线程的私有变量,如下例所示。
示例 7 变量 t 作为每个线程的私有变量for (i=1; i < 1000; i++) { pt[i] = 2 * a[i]; /* S1 */ b[i] = pt[i]; /* S2 */ }
在此示例中,每个标量变量引用 t 被数组引用 pt 替换。现在,每次迭代使用 pt 的不同元素,消除了任意两次迭代之间的所有数据依赖性。本示例产生的一个问题是可能导致数组非常大。在实际运用中,编译器为参与循环执行的每个线程只分配变量的一个副本。事实上,每个此类变量是线程的私有变量。
编译器还可以私有化数组变量,以便为循环的并行执行创造机会。请看以下示例:
示例 8 带数组变量的可并行化循环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 的私有副本,那么外部循环的任意两次迭代之间不会发生干扰。以下示例对这一点进行了说明。
示例 9 使用私有化数组的可并行化循环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 */ } }
如私有标量的情形一样,只需将数组最多展开为系统中执行的线程数。此扩展由编译器自动完成,方式是在每个线程的私有空间中分配初始数组的一个副本。
变量私有化对改进程序中的并行性十分有用。然而,如果在循环外部引用私有变量,则编译器需要确认私有变量具有正确的值。请看以下示例:
示例 10 使用返回存储的并行化循环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 的原始位置实现。在许多情况下,编译器会自动执行此操作,但有时不容易计算最后一个值。
示例 11 不能使用返回存储的循环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 的最终值会比较困难。在与此示例类似的情况下,编译器不会并行化循环。
有时循环的迭代之间存在真正的依赖性,通过简单地私有化导致依赖性的变量并不能除去该依赖性。例如,查看以下从一次迭代到下一次迭代累计值的代码。
示例 12 可以并行化的循环for (i=1; i < 1000; i++) { sum += a[i]*b[i]; /* S1 */ }
在此示例中,循环计算两个数组的向量乘积,并将结果赋给一个称为 sum 的公共变量。该循环不能以简单的方式并行化。编译器可以利用语句 S1 中计算的关联特性,并为每个线程分配一个称为 psum[i] 的私有变量。变量 psum[i] 的每个副本均初始化为 0。每个线程以自己的变量 psum[i] 副本计算自己的部分和。执行循环之前,所有部分和均加到初始变量 sum 上。在本示例中,变量 sum 称为约简变量,因为它计算和约简。然而,将标量变量提升为约简变量存在的危险是:累计舍入值的方式会更改 sum 的最终值。只有在您专门授权这样做时,编译器才执行该变换。
编译器执行多个循环重构变换,帮助改进程序中循环的并行化。其中某些变换还可以提高循环的单处理器执行性能。此部分描述编译器执行的变换。
循环通常包含少量无法并行执行的语句以及许多可以并行执行的语句。循环分布旨在将顺序语句移到单独一个循环中,并将可并行化的语句收集到另一个循环中。以下示例描述了此过程:
示例 13 循环分布举例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 不能并行化。以下示例说明了循环在拆分或分配到两个不同的循环中之后的外在形式。
示例 14 分布式循环/* 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 仍包含来自初始循环的不可并行化的语句。
循环分布并非始终有益或安全。编译器会进行分析,以确定分布的安全性和有益性。
如果循环的粒度(或循环执行的工作量)很小,则分布的效果可能并不明显,原因是相对于循环开销,并行循环启动的开销太大。在这种情况下,编译器使用循环合并将多个循环合并到单个并行循环中,增大了循环的粒度。当具有相同行程计数的循环彼此相邻时,循环合并很方便且很安全。请看以下示例:
示例 15 工作量小的循环/* 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 */ }
这两个短并行循环彼此相邻,可以安全地合并,如下所示:
示例 16 合并的两个循环/* 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 */ }
新循环产生的开销是并行循环执行产生的开销的一半。循环合并在其他方面也很有帮助。例如,如果在两个循环中引用同一数据,则合并这两个循环可以改善引用环境。
然而,循环合并并非始终安全。如果循环合并创建之前并不存在的数据依赖性,则合并可能会导致错误执行。请看以下示例:
示例 17 不安全合并举例/* 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 中计算的。如果未合并循环,则不会产生此依赖性。编译器执行安全性和有益性分析,以确定是否应执行循环合并。通常,编译器可以合并任意多个循环。以这种方式增大粒度有时可以大大改善循环,使其足从并行化中获益。
并行化循环嵌套的最外层循环通常更有益,因为发生的开销很小。然而,由于此类循环可能携带依赖性,并行化最外层循环并非始终安全。以下示例对此情况进行了说明。
示例 18 不能并行化的嵌套循环for (i=0; i <n; i++) { for (j=0; j <n; j++) { a[j][i+1] = 2.0*a[j][i-1]; } }
在本例中,具有索引变量 i 的循环不能并行化,原因是循环的两次连续迭代之间存在依赖性。这两个循环可以交换,并行循环(j 循环)变为外部循环:
示例 19 循环交换for (j=0; j<n; j++) { for (i=0; i<n; i++) { a[j][i+1] = 2.0*a[j][i-1]; } }
交换后的循环只发生一次并行工作分配开销,而先前发生 n 次开销。编译器执行安全性和有益性分析,以确定是否执行循环交换。
ISO C 别名通常可防止循环并行化。存在两个对同一存储单元的可能引用时,将产生别名。请看以下示例:
示例 20 具有对同一存储单元的两个引用的循环void copy(float a[], float b[], int n) { int i; for (i=0; i < n; i++) { a[i] = b[i]; /* S1 */ } }
由于变量 a 和 b 为参数,因此 a 和 b 可能指向重叠的内存区域,例如,如果 copy 的调用如下:
copy (x[10], x[11], 20);
在调用的例程中,copy 循环的两次连续迭代可能读/写数组 x 的同一元素。然而,如果例程 copy 的调用如下,则循环的 20 次迭代中不可能出现重叠:
copy (x[10], x[40], 20);
如果未提供有关如何调用例程的信息,编译器不可能正确地分析此情况。但是,Oracle Developer Studio C 编译器提供标准 ISO C 的关键字扩展,以传达此类别名信息。有关更多信息,请参见受限指针。
别名问题的部分原因是:C 语言可以通过指针运算来定义数组引用及定义。为使编译器有效地自动并行化循环,所有采用数组布局的数据均必须使用 C 数组引用语法而不是指针进行引用。如果使用指针语法,编译器将无法确定循环的不同迭代之间的关系。因此,编译器将保守而不会并行化循环。
为使编译器有效地执行循环的并行执行任务,需要确定特定左值是否指定不同的存储区域。别名是其存储区域相同的左值。由于需要分析整个程序,因此确定对象的两个指针是否为别名是一个困难而费时的过程。考虑以下示例中的函数 vsq():
示例 21 带两个指针的循环void vsq(int n, double * a, double * b) { int i; for (i=0; i<n; i++) { b[i] = a[i] * a[i]; } }
如果编译器已确定指针 a 和 b 访问不同的对象,则可以并行化循环的不同迭代的执行。如果通过指针 a 和 b 访问的对象存在重叠,则编译器以并行方式执行循环将会不安全。在编译时,编译器无法通过简单地分析函数 vsq() 来确定 a 和 b 访问的对象是否重叠。编译器可能需要分析整个程序才能获取此信息。
限定指针用来指定那些指定不同对象的指针,以便编译器可以执行指针别名分析。以下示例说明了函数参数声明为限定指针的函数 vsq():
void vsq(int n, double * restrict a, double * restrict b)
指针 a 和 b 声明为限定指针,因此编译器知道 a 和 b 指向不同的存储区域。有了此别名信息,编译器就能够并行化循环。
关键字 restrict 是一个类型限定符,与 volatile 类似,但它仅限定指针类型。 在某些情况下,您可能不希望更改源代码。可以使用以下命令行选项指定将返回赋值指针函数参数视为限定指针:
-xrestrict=[func1,…,funcn]
如果指定函数列表,则指定的函数中的指针参数将被视为限定的;否则,整个 C 文件中的所有指针参数均被视为限定的。例如,-xrestrict=vsq 限定前一个有关键字 restrict 的函数 vsq() 示例中给定的指针 a 和 b。
正确使用 restrict 至关重要。如果指针被限定为限定指针而指向不同的对象,编译器会错误地并行化循环而导致不确定的行为。例如,假定函数 vsq() 的指针 a 和 b 指向的对象重叠,使 b[i] 和 a[i+1] 是同一对象。如果 a 和 b 未声明为限定指针,循环将以串行方式执行。如果 a 和 b 被错误地限定为限定指针,编译器会并行化循环的执行,但这是不安全的,因为 b[i+1] 应在 b[i] 之后进行计算。