循环通常包含少量无法并行执行的语句以及许多可以并行执行的语句。循环分布旨在将顺序语句移到单独一个循环中,并将可并行化的语句收集到另一个循环中。这一点在以下示例中描述:
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 不能并行化。以下是循环被分割或分布为两个不同循环后的情形:
/* 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 仍包含来自初始循环的不可并行化的语句。
循环分布并非始终有益或安全。编译器会进行分析,以确定分布的安全性和有益性。