コンパイラは、プログラム中のループを並列に実行できるようにするために、ループ再構成のための変換を数回実行します。この変換のいくつかは、シングルプロセッサ上でのループの実行速度も向上させます。このセクションでは、コンパイラによって実行される変換について説明します。
ループには多くの場合、並列で実行できないいくつかの文と、並列で実行できる多くの文が含まれます。ループの分散によって、これらの文を別のループに移動し、並列実行可能な文だけから成るループを作ります。このプロセスを次の例で説明します。
使用例 3-12 ループの候補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 はできません。次の例は、異なる 2 つのループに分割または分散されたあとにループがどのようになるかを示しています。
使用例 3-13 分散されたループ/* 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 には並列実行を妨害する文が含まれていないので、これを並列実行できるようになります。ところが、2 番目のループ L2 は元のループの並列実行できない部分を引き継いだままです。
ループの分散は、常に効果があって安全に実行できるとはかぎりません。コンパイラは、この効果と安全性を確認するための解析を実行します。
ループの粒度、つまりループで実行される作業が小さい場合は、分散からのパフォーマンスの利点がわずかである可能性があります。並列ループ起動のオーバーヘッドがループ作業負荷に比べて高すぎるためです。このような状況では、コンパイラはループの融合を使用して、いくつかのループを 1 つの並列ループに結合することで、ループの粒度を大きくします。同じ回数の繰り返しを行うループが隣接していると、ループの融合は簡単にしかも安全に行われます。次の例を考えてみましょう。
使用例 3-14 作業量の少ないループ/* 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 */
}
この例では、2 個の小さなループが隣どうしに記述されていて、次のように安全に融合することができます。
使用例 3-15 融合された 2 つのループ/* 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 */
}
これによって、並列ループの実行によるオーバーヘッドを半分にすることができます。ループの融合は、別の場合にも役に立ちます。たとえば、同じデータが 2 個のループで参照されている場合には、この 2 個のループを融合すると、参照を局所的なものにすることができます。
ただし、ループの融合は常に安全に実行できるとはかぎりません。ループの融合が、それまで存在しなかったデータ依存性を作り出す場合は、融合によって間違った実行になることがあります。次の例を考えてみましょう。
使用例 3-16 安全でない融合の候補/* 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 で計算されます。ループが融合されない場合は、この依存性は発生しません。コンパイラは、ループの融合を実行すべきかどうかを判断するために、安全性と利点の解析を実行します。場合によっては、任意の数のループを融合できることがあります。このような方法でループの作業量を多くすると、並列実行が十分に有効であるようなループを生成することができます。
ループのネストでもっとも外側のループを並列化することは通常、発生するオーバーヘッドが小さいために、より多くの利点が得られます。ただし、もっとも外側のループを並列化することは、そのようなループによってもたらされる可能性のある依存性のために、常に安全とは限りません。次の例はこの状況を示しています。
使用例 3-17 並列化できない入れ子のループfor (i=0; i <n; i++) {
for (j=0; j <n; j++) {
a[j][i+1] = 2.0*a[j][i-1];
}
}
この例では、添字変数 i を持つループは、ループの後続の 2 回の繰り返しの間に依存性のために、並列化できません。ただし、2 つのループを交換することができるため、交換すると並列ループ (j のループ) が今度は外側のループになります。
使用例 3-18 交換されたループfor (j=0; j<n; j++) {
for (i=0; i<n; i++) {
a[j][i+1] = 2.0*a[j][i-1];
}
}
結果のループが並列作業分散のオーバーヘッドを 1 回だけ発生するのに対して、以前はオーバーヘッドが n 回発生していました。コンパイラは、これまで説明したように、ループの交換をするかどうか決定するための解析を行い、安全性と有効性を確認します。