C コンパイラは、並列化しても安全であると判断したループに対して並列コードを生成します。通常、これらのループは、独立して実行可能な繰り返しを持っています。そのようなループでは、各繰り返しを実行する順番や、繰り返しを並列実行するかどうかは、問題ではありません。すべてではありませんが、ほとんどのベクトル処理用ループはこのような種類のループです。
C では別名が存在する可能性があるため、並列化の安全性を判断することは困難です。コンパイラに役立つように、Oracle Developer Studio C はプラグマおよび追加のポインタ修飾子を提供して、コンパイラが判定できない、プログラマには既知の別名情報を示します。詳細は、型に基づく別名解析を参照してください。
次の例は、C を並列化し、制御する方法を示しています。
% cc -fast -xO4 -xautopar example.c -o example
このコンパイラコマンドでは、通常の方法で実行できる example という実行可能ファイルが生成されます。マルチプロセッサ実行を活用する方法については、-xautoparを参照してください。
C コンパイラは、プログラム中のループの解析を実行することで、ループのさまざまな繰り返しを並列で実行することが安全であるかどうかを判断します。この解析の目的は、ループ中の任意の 2 個の繰り返しが、互いに干渉する可能性があるかどうかを調べることです。通常、この問題は、ループの一方の繰り返しが変数を読み取っている可能性があるときに、別の繰り返しがその同じ変数を書き込んでいる場合に発生します。次に示すプログラムの一部を考えてみましょう。
使用例 2 依存関係があるループfor (i=1; i < 1000; i++) {
sum = sum + a[i]; /* S1 */
}
この例では、2 つの連続する繰り返し、i および i+1 が、同じ変数 sum に対して書き込みと読み取りを実行します。したがって、このような 2 個の繰り返しを並列に実行するには、なんらかの方法で変数をロックすることが必要になります。そうしない場合、2 つの繰り返しを並列で実行するのを許可することは安全ではありません。
ところが、このロック機構を使用すると、オーバーヘッドが発生してプログラムの実行を遅くすることになります。C コンパイラは通常、前述の例のループを並列化しません。ループの 2 つの繰り返しの間にデータの依存関係があるからです。別の例を考えてみましょう。
使用例 3 依存関係を持たないループfor (i=1; i < 1000; i++) {
a[i] = 2 * a[i]; /* S1 */
}
この場合、ループの各繰り返しは、異なる配列要素を参照します。したがって、ループ中の繰り返しを実行する順番を守る必要がありません。また、異なる繰り返しでアクセスするデータが互いに干渉しないため、ロックを使用せずに並列実行することが可能になります。
ループの 2 つの異なる繰り返しが同じ変数を参照している可能性があるかどうかを判断するためにコンパイラが実行する解析はデータ依存性解析と呼ばれます。1 回でも変数に書き込みを実行している場合には、データ依存性によって並列化することができなくなります。コンパイラが実行する依存性解析の結果、次のいずれかの解答が得られます。
依存性があります。この場合、ループを並列で実行することは安全ではありません。
依存性がありません。この場合、任意の数のプロセッサを使用してループを並列で安全に実行する可能性があります。
依存性を確認できません。コンパイラは、安全のために、依存関係がループの並列実行を妨げる可能性があると仮定し、ループを並列化しません。
この例では、ループの 2 つの繰り返しが配列 a の同じ要素に書き込むかどうかは、配列 b が重複要素を含んでいるかどうかによって決まります。コンパイラは、この事実を判断できないかぎり、依存性が存在する可能性があると仮定し、ループを並列化しないようにする必要があります。
使用例 4 依存性を含んでいる可能性のあるループfor (i=1; i < 1000; i++) {
a[b[i]] = 2 * a[i];
}
データ依存性によっては、コンパイラがループを並列化できる場合があります。次の例を考えてみましょう。
使用例 5 並列化可能な依存性ありのループfor (i=1; i < 1000; i++) {
t = 2 * a[i]; /* S1 */
b[i] = t; /* S2 */
}
この例では、配列 a と b が重なりあっていないと仮定すると、2 回の繰り返しの間に、変数 t による明らかなデータ依存性が存在します。繰り返しの 1 回目と 2 回目に注目すると、次のような文が実行されることになります。
使用例 6 繰り返し 1 と 2t = 2*a[1]; /* 1 */ b[1] = t; /* 2 */ t = 2*a[2]; /* 3 */ b[2] = t; /* 4 */
文 1 および 3 によって変数 t が変更されるので、これらを並列実行することはできません。しかし、変数 t の値は常に同じ繰り返しの中で計算されて使用されるので、コンパイラは繰り返しごとに変数 t の別々のコピーを使用できます。この方法により、このような変数による異なる繰り返し間での干渉が回避されます。事実上、変数 t は次の例に示すように、繰り返しを実行するスレッドごとのスレッド固有変数として使用されます。
使用例 7 各スレッドに固有の変数としての変数 tfor (i=1; i < 1000; i++) {
pt[i] = 2 * a[i]; /* S1 */
b[i] = pt[i]; /* S2 */
}
この例では、各スカラー変数参照 t が、配列参照 pt で置き換えられています。各繰り返しが pt の異なる要素を使用するようになり、任意の 2 つの繰り返し間でのデータ依存性がなくなります。これの問題の 1 つは、さらに大きな配列になる可能性があることです。実際には、コンパイラによってスレッドごとに 1 個の変数だけが割り当てられ、その変数をループの実行で使用します。つまりこのような変数は、スレッドごとに固有であるといえます。
コンパイラは、配列変数を固有化してループを並列実行することもできます。次の例を考えてみましょう。
使用例 8 配列変数を使用した並列化可能なループfor (i=1; i < 1000; i++) {
for (j=1; j < 1000; j++) {
x[j] = 2 * a[i]; /* S1 */
b[i][j] = x[j]; /* S2 */
}
}
この例では、外側のループの異なる繰り返しが配列 x の同じ要素を変更するので、外側のループは並列化できません。しかし、外側のループの繰り返しを実行するそれぞれのスレッドに配列 x 全体のスレッド固有コピーがある場合は、外側ループの任意の 2 つの繰り返し間の干渉は発生しません。次の例はこの点を示しています。
使用例 9 スレッド固有化された配列を使用した並列化可能なループfor (i=1; i < 1000; i++) {
for (j=1; j < 1000; j++) {
px[i][j] = 2 * a[i]; /* S1 */
b[i][j] = px[i][j]; /* S2 */
}
}
スレッド固有スカラーの場合と同じく、システムで実行されるスレッドの数までしかこの配列を展開する必要はありません。この展開は、各スレッドのスレッド固有領域にオリジナル配列の 1 つのコピーを割り当てることで、コンパイラによって自動的に行われます。
変数のスレッド固有化は、プログラムの並列化を向上させる上で便利な方法です。しかし、プライベート変数がループの外側で参照される場合には、コンパイラが正しい値を持つことを確認する必要があります。次の例を考えてみましょう。
使用例 10 ストアバック変数を使用した並列化ループfor (i=1; i < 1000; i++) {
t = 2 * a[i]; /* S1 */
b[i] = t; /* S2 */
}
x = t; /* S3 */
この例では、文 S3 で参照されている t の値が、ループで計算される t の最終値です。変数 t がスレッド固有化され、ループの実行が終了したあと、t の正しい値をオリジナルの変数に戻すことが必要になります。このプロセスは「ストアバック」と呼ばれ、最後の繰り返しでの t の値を変数 t のコピーを元の場所に戻すことで実現されます。多くの場合、コンパイラはこれを自動的に行うことができますが、最後の値を容易に計算できない場合があります。
使用例 11 ストアバックを使用できないループfor (i=1; i < 1000; i++) {
if (c[i] > x[i] ) { /* C1 */
t = 2 * a[i]; /* S1 */
b[i] = t; /* S2 */
}
}
x = t*t; /* S3 */
正しい実行の場合、文 S3 の t の値は通常、ループの最後の繰り返しでの t の値ではありません。実際には、条件 C1 が真なのは、最後の繰り返しです。一般に、t の最終値の計算は困難である可能性があります。この例のような場合には、コンパイラはループを並列化しません。
ループの繰り返し間に実際の依存性が存在しており、依存性の原因となる変数をスレッド固有化するだけでは依存性を除去できない場合があります。たとえば、ある繰り返しから別の繰り返しへ値が累積される次のコードを見てみます。
使用例 12 並列化される可能性のあるループfor (i=1; i < 1000; i++) {
sum += a[i]*b[i]; /* S1 */
}
この例では、ループは 2 つの配列のベクトル積を計算して、sum と呼ばれる共通変数に入れます。このループを単純な方法で並列化することはできません。ここでは、文 S1 の計算式に結合の法則を適用し、各スレッドに対して psum[i]というスレッド固有変数を割り当てることができます。変数 psum[i] のコピーはそれぞれ 0 に初期化されます。各スレッドは、スレッド固有の変数 psum[i] に自分で計算した部分和を代入します。バリアに達したら、すべての部分和を合計してオリジナルの変数 sum に代入します。この例では、和の縮約をしているので、変数 sum を縮約変数といいます。しかし、スカラー変数を縮約変数にした場合には、丸め誤差が累積されて、sum の最終値に影響する可能性があることに注意してください。コンパイラは、ユーザーによる明確な指示がされた場合に、この操作を実行します。
コンパイラは、プログラム中のループを並列に実行できるようにするために、ループ再構成のための変換を数回実行します。この変換のいくつかは、シングルプロセッサ上でのループの実行速度も向上させます。このセクションでは、コンパイラによって実行される変換について説明します。
ループには多くの場合、並列で実行できないいくつかの文と、並列で実行できる多くの文が含まれます。ループの分散によって、これらの文を別のループに移動し、並列実行可能な文だけから成るループを作ります。このプロセスを次の例で説明します。
使用例 13 ループの候補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 つのループに分割または分散されたあとにループがどのようになるかを示しています。
使用例 14 分散されたループ/* 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 つの並列ループに結合することで、ループの粒度を大きくします。同じ回数の繰り返しを行うループが隣接していると、ループの融合は簡単にしかも安全に行われます。次の例を考えてみましょう。
使用例 15 作業量の少ないループ/* 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 個の小さなループが隣どうしに記述されていて、次のように安全に融合することができます。
使用例 16 融合された 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 個のループを融合すると、参照を局所的なものにすることができます。
ただし、ループの融合は常に安全に実行できるとはかぎりません。ループの融合が、それまで存在しなかったデータ依存性を作り出す場合は、融合によって間違った実行になることがあります。次の例を考えてみましょう。
使用例 17 安全でない融合の候補/* 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 で計算されます。ループが融合されない場合は、この依存性は発生しません。コンパイラは、ループの融合を実行すべきかどうかを判断するために、安全性と利点の解析を実行します。場合によっては、任意の数のループを融合できることがあります。このような方法でループの作業量を多くすると、並列実行が十分に有効であるようなループを生成することができます。
ループのネストでもっとも外側のループを並列化することは通常、発生するオーバーヘッドが小さいために、より多くの利点が得られます。ただし、もっとも外側のループを並列化することは、そのようなループによってもたらされる可能性のある依存性のために、常に安全とは限りません。次の例はこの状況を示しています。
使用例 18 並列化できない入れ子のループ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 のループ) が今度は外側のループになります。
使用例 19 交換されたループfor (j=0; j<n; j++) {
for (i=0; i<n; i++) {
a[j][i+1] = 2.0*a[j][i-1];
}
}
結果のループが並列作業分散のオーバーヘッドを 1 回だけ発生するのに対して、以前はオーバーヘッドが n 回発生していました。コンパイラは、これまで説明したように、ループの交換をするかどうか決定するための解析を行い、安全性と有効性を確認します。
ISO C の別名を使用すると、ループを並列化できなくなることがあります。別名とは、2 個の参照が記憶領域の同じ位置を参照する可能性のある場合に発生します。次の例を考えてみましょう。
使用例 20 同じメモリー位置への 2 つの参照を持つループvoid copy(float a[], float b[], int n) {
int i;
for (i=0; i < n; i++) {
a[i] = b[i]; /* S1 */
}
}
変数 a と b は引数であるため、a と b がメモリーの重なり合う領域を指している可能性があります。たとえば、copy が次のように呼び出された場合:
copy (x[10], x[11], 20);
呼び出されたルーチンでは、copy ループの後続の 2 回の繰り返しが、配列 x の同じ要素を読み書きしている可能性があります。しかし、ルーチン copy が次のように呼び出された場合には、ループの 20 回の繰り返しのいずれかで重なり合う可能性がなくなります。
copy (x[10], x[40], 20);
ルーチンの呼び出し方法に関する情報なしで、コンパイラはこの状況を正しく解析できません。ただし、Oracle Developer Studio C コンパイラには、この種の別名情報を伝えるための、標準 ISO C に対するキーワード拡張が用意されています。詳細については、制限付きポインタを参照してください。
別名の問題の一因は、配列参照とポインタ計算演算を定義できる C 言語の性質にあります。コンパイラが効率的にループを自動並列化できるようにするためには、配列として配置されているすべてのデータを、ポインタではなく C の配列参照の構文を使用して参照する必要があります。ポインタ構文が使用されると、コンパイラはループの異なる繰り返し間でのデータの関係を解析できなくなります。そのため、コンパイラは用心深くなり、ループを並列化しません。
コンパイラが効率的にループの並列化を実行するためには、特定の左辺値が記憶領域の別々の領域を指定しているかどうかを判断する必要があります。別名とは、記憶領域の決まった位置を示していない左辺値のことです。オブジェクトへの 2 個のポインタが別名であるかどうかを判断することは、困難で非常に時間がかかります。プログラム全体の解析が必要になることがあるためです。次の例の関数 vsq() を考えます。
使用例 21 2 つのポインタを持つループvoid vsq(int n, double * a, double * b) {
int i;
for (i=0; i<n; i++) {
b[i] = a[i] * a[i];
}
}
ポインタ a と b が異なるオブジェクトにアクセスしていると判断した場合、コンパイラはループの異なる繰り返しの実行を並列化できます。ポインタ a と b からアクセスされるオブジェクトで重なり合いがある場合は、コンパイラがループを並列で実行するのは安全ではありません。コンパイラはコンパイル時に、関数 vsq() を分析するだけでは、a と b からアクセスされるオブジェクトが重なり合っているかどうかを判断できません。コンパイラがこの情報を得るために、プログラム全体の解析が必要になることがあります。
別々のオブジェクトを指定するポインタを指定するために、制限付きポインタが使用されます。そうすることで、コンパイラはポインタ別名解析を実行できます。次の例に示す関数 vsq() は、関数パラメータが制限付きポインタとして宣言されています。
void vsq(int n, double * restrict a, double * restrict b)
ポインタ a および b が制限付きポインタとして宣言されているので、a および b で示された記憶領域が区別されていることがわかります。この別名情報によって、コンパイラはループの並列化を実行することができます。
キーワード restrict は volatile のような型修飾子であり、ポインタ型のみを修飾します。ソースコードを変更しない場合があります。その場合、次のコマンド行オプションを使用して、ポインタ型の値をとる関数の引数を restrict ポインタとして扱うように指定できます。
-xrestrict=[func1,…,funcn]
関数リストが指定されている場合、指定された関数内のポインタパラメータは制限付きとして扱われます。指定されていない場合は、C ファイル全体のすべてのポインタパラメータが制限付きとして扱われます。たとえば、-xrestrict=vsq を使用すると、前述の関数 vsq() についての最初の例では、ポインタ a および b がキーワード restrict によって修飾されます。
restrict を正しく使用することはとても重要です。区別できないオブジェクトを指しているポインタを制限付きポインタにしてしまうと、ループを正しく並列化することができなくなり、不定な動作をすることになります。たとえば、関数 vsq() のポインタ a および b が重なりあっているオブジェクトを指している場合には、b[i] と a[i+1] などが同じオブジェクトである可能性があります。このとき a および b が制限付きポインタとして宣言されていなければ、ループは順次実行されます。a および b が間違って制限付きであると宣言されていれば、コンパイラはループを並列実行するようになりますが、この場合 b[i+1] の結果は b[i] を計算したあとでなければ得られないので、安全に実行することはできません。