C 编译器通过分析程序中的循环来确定并行执行循环的不同迭代是否安全。分析的目的是确定循环的两次迭代之间是否会相互干扰。通常,如果循环的一次迭代读取某个变量而另一次迭代正在写入该变量,会发生此问题。考虑以下程序片段:
示例 3-1 带依赖性的循环for (i=1; i < 1000; i++) { sum = sum + a[i]; /* S1 */ }
在此示例中,任意两次连续迭代,第 i 次和第 i+1 次,将写入和读取同一变量 sum。因此,为了并行执行这两次迭代,需要以某种形式锁定该变量。否则,允许并行执行这两次迭代不安全。
然而,使用锁定会产生可能降低程序运行速度的开销。在上述示例中,C 编译器将不会如常并行化循环,原因是循环的两次迭代之间存在数据依赖性。考虑另一个示例:
示例 3-2 不带依赖性的循环for (i=1; i < 1000; i++) { a[i] = 2 * a[i]; /* S1 */ }
在此情况下,循环的每次迭代均引用不同的数组元素。因此,循环的不同迭代可以按任意顺序执行。由于不同迭代的两个数据元素不可能相互干扰,因此它们可以并行执行而无需任何锁定。
编译器为确定一个循环的两次不同迭代是否引用相同变量而执行的分析称为数据依赖性分析。如果其中一个引用写入变量,数据依赖性阻止循环并行化。编译器执行的数据依赖性分析有三种结果:
在存在依赖性的情况下,并行执行循环是不安全的。
在不存在依赖性的情况下,可以使用任意数量的处理器安全地并行执行循环。
无法确定依赖性。为安全起见,编译器假定依赖性可能会阻止并行执行循环,并且不会并行化循环。
在以下示例中,循环的两次迭代是否写入数组 a 的同一元素取决于数组 b 是否包含重复元素。除非编译器可以确定实际情况,否则它必须假定可能存在依赖性并且不会并行化循环。
示例 3-3 可能包含依赖性的循环for (i=1; i < 1000; i++) { a[b[i]] = 2 * a[i]; }