コンパイラは、プログラム中のループを並列に実行できるようにするために、ループ再構成のための変換を数回実行します。この変換のいくつかは、シングルプロセッサ上でのループの実行速度も向上させます。コンパイラが実行する変換を次で説明します。
ループには、並列に実行できる文とできない文とが存在することがあります。通常、並列実行できない文はごく少数です。ループの分散によって、これらの文を別のループに移動し、並列実行可能な文だけから成るループを作ります。これを次の例で説明します。
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 個のループに分割すると次のようになります。
/* L1: 並列実行ループ */ for (i=0; i < n; i++) { x[i] = y[i] + z[i]*w[i]; /* S1 */ y[i] = z[i] - x[i]; /* S3 */ } /* L2: 順次実行ループ */ for (i=0; i < n; i++) { a[i+1] = (a[i-1] + a[i] + a[i+1]/3.0; /* S2 */ } |
この変換のあと、前述のループ L1 には並列実行を妨害する文が含まれていないので、これを並列実行できるようになります。ところが、2 番目のループ L2 は元のループの並列実行できない部分を引き継いだままです。
ループの分散は、常に効果があって安全に実行できるとはかぎりません。コンパイラは、この効果と安全性を確認するための解析を実行します。
ループが小さい、すなわちループでの作業量が少ないと、大幅にパフォーマンスを向上させることはできません。これは、ループでの作業量に比べて、並列ループを起動するときのオーバーヘッドが大きくなるためです。このような状況では、コンパイラはループの融合を使用して、いくつかのループを 1 つの並列ループに融合し、ループを大きくします。同じ回数の繰り返しを行うループが隣接していると、ループの融合は簡単にしかも安全に行われます。次の例について考えてみましょう。
/* L1: 小さな並列ループ */ for (i=0; i < 100; i++) { a[i] = a[i] + b[i]; /* S1 */ } /* L2: 別の小さな並列ループ */ for (i=0; i < 100; i++) { b[i] = a[i] * d[i]; /* S2 */ } |
この例では、2 個の小さなループが隣どうしに記述されていて、次のように安全に融合することができます。
/* L3: 大きな並列ループ */ for (i=0; i < 100; i++) { a[i] = a[i] + b[i]; /* S1 */ b[i] = a[i] * d[i]; /* S2 */ } |
これによって、並列ループの実行によるオーバーヘッドを半分にすることができます。ループの融合は、別の場合にも役に立ちます。たとえば、同じデータが 2 個のループで参照されている場合には、この 2 個のループを融合すると、参照を局所的なものにすることができます。
ただし、ループの融合は常に安全に実行できるとはかぎりません。ループの融合によって、元々存在していなかったデータの依存関係が生成されると、実行結果が正しくなくなることがあります。次の例について考えてみましょう。
/* L1: 小さな並列ループ */ for (i=0; i < 100; i++) { a[i] = a[i] + b[i]; /* S1 */ } /* L2: a データの依存性がある小さなループ */ for (i=0; i < 100; i++) { a[i+1] = a[i] * d[i]; /* S2 */ } |
「3.7.2 ループの融合」でループの融合が実行されると、文 S2 から S1 に対するデータの依存性が生成されます。実際に、文 S1 の右辺にある a[i] の値が、文 S2 で計算されるものになります。これはループが融合されないと起こりません。コンパイラは、ループの融合を実行すべきかどうかを判断するために解析を行い、安全性と有効性を確認します。場合によっては、任意の数のループを融合できることがあります。このような方法でループの作業量を多くすると、並列実行が十分に有効であるようなループを生成することができます。
入れ子になっているループのもっとも外側のループを並列化すると、発生するオーバーヘッドが小さいために、一般に大きな効果が期待できます。しかし、そのループに依存性がある場合は、並列化することは安全ではありません。次の例で説明します。
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 のループ) が今度は外側のループになります。
for (j=0; j<n; j++) { for (i=0; i<n; i++) { a[j][i+1] = 2.0*a[j][i-1]; } } |
この結果生成されたループでは並列作業の分散に対するオーバーヘッドが 1 回で済むのに対して、元のループでは、n 回必要でした。コンパイラは、これまで説明したように、ループの交換をするかどうか決定するための解析を行い、安全性と有効性を確認します。