3.6 ループの変換

コンパイラは、プログラム中のループを並列に実行できるようにするために、ループ再構成のための変換を数回実行します。この変換のいくつかは、シングルプロセッサ上でのループの実行速度も向上させます。この節では、コンパイラによって実行される変換について説明します。

3.6.1 ループの分散

ループには多くの場合、並列で実行できないいくつかの文と、並列で実行できる多くの文が含まれます。ループの分散によって、これらの文を別のループに移動し、並列実行可能な文だけから成るループを作ります。このプロセスを次の例で説明します。

例 3-14 ループの候補

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-15 分散されたループ

/* 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 は元のループの並列実行できない部分を引き継いだままです。

ループの分散は、常に効果があって安全に実行できるとはかぎりません。コンパイラは、この効果と安全性を確認するための解析を実行します。

3.6.2 ループの融合

ループの粒度、つまりループで実行される作業が小さい場合は、分散からのパフォーマンスの利点がわずかである可能性があります。並列ループ起動のオーバーヘッドがループ作業負荷に比べて高すぎるためです。このような状況では、コンパイラはループの融合を使用して、いくつかのループを 1 つの並列ループに結合することで、ループの粒度を大きくします。同じ回数の繰り返しを行うループが隣接していると、ループの融合は簡単にしかも安全に行われます。次の例を考えてみましょう。

例 3-16 作業量の少ないループ

/* 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-17 融合された 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-18 安全でない融合の候補

/* 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.6.3 ループの交換

ループのネストでもっとも外側のループを並列化することは通常、発生するオーバーヘッドが小さいために、より多くの利点が得られます。ただし、もっとも外側のループを並列化することは、そのようなループによってもたらされる可能性のある依存性のために、常に安全とは限りません。次の例はこの状況を示しています。

例 3-19 並列化できない入れ子のループ

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-20 交換されたループ

for (j=0; j<n; j++) {
    for (i=0; i<n; i++) {
            a[j][i+1] = 2.0*a[j][i-1];
    }
}

結果のループが並列作業分散のオーバーヘッドを 1 回だけ発生するのに対して、以前はオーバーヘッドが n 回発生していました。コンパイラは、これまで説明したように、ループの交換をするかどうか決定するための解析を行い、安全性と有効性を確認します。