3.4 データの依存性と干渉

C コンパイラは、プログラム中のループを解析して、ループの各繰り返しを安全に並列実行できるかどうかを判断します。この解析の目的は、ループ中の任意の 2 個の繰り返しが、互いに干渉しないかどうかを調べることです。通常、干渉は、ある繰り返しが書き込みを行なっている変数に対して、別の繰り返しが読み込みを行うと発生します。次に示すプログラムの一部を考えてみましょう。

例 3-1 依存性を持つループ

for (i=1; i < 1000; i++) {
    sum = sum + a[i]; /* S1 */
}

「3.4 データの依存性と干渉」では、2 個の連続した繰り返しである i および i+1 が、同じ変数 sum に書き込みと読み込みを実行しています。したがって、このような 2 個の繰り返しを並列に実行するには、なんらかの方法で変数をロックすることが必要になります。ロックをしないと、2 個の連続した繰り返しを安全に並列実行することができなくなります。

ところが、このロック機構を使用すると、オーバーヘッドが発生してプログラムの実行を遅くすることになります。C コンパイラは「3.4 データの依存性と干渉」のループの並列化を行いません。「3.4 データの依存性と干渉」には、2 個の連続したループの繰り返しにデータの依存関係があるからです。別の例を考えてみましょう。

例 3-2 依存性を持たないループ

for (i=1; i < 1000; i++) {
    a[i] = 2 * a[i]; /* S1 */
}

この場合、ループ中の各繰り返しでは、異なる配列の要素が参照されています。したがって、ループ中の繰り返しを実行する順番を守る必要がありません。また、異なる繰り返しでアクセスするデータが互いに干渉しないため、ロックを使用せずに並列実行することが可能になります。

ループ内の 2 個の異なる繰り返しで、同じ変数を参照していないかどうかを判断するためにコンパイラが実行する解析を、「データ依存性解析」といいます。1 回でも変数に書き込みを実行している場合には、データ依存性によって並列化することができなくなります。コンパイラが実行する依存性解析の結果、次のいずれかの解答が得られます。

依存性があります。この場合には、ループを安全に並列実行できません。前述の「3.4 データの依存性と干渉」がこれに該当します。
ループ内に依存性がありません。ループを任意の数のプロセッサを使用して並列に実行することができます。前述の「3.4 データの依存性と干渉」がこれに該当します。
依存性を確認できません。コンパイラは、安全に実行することを重視して、ループに並列実行できないような依存関係が存在するものと仮定して、ループを並列化しません。

「3.4 データの依存性と干渉」ではループの 2 個の繰り返しで配列 a の同じ要素に書き込まれるかどうかは、配列 b に重複する要素が存在するかどうかによって決まります。コンパイラがこの事実を確認できないかぎり依存性があるものと判断され、ループは並列化されません。

例 3-3 依存性の有無を確認できないループ

for (i=1; i < 1000; i++) {
    a[b[i]] = 2 * a[i];
}

3.4.1 並列実行モデル

ループの並列実行は、Solaris スレッドによって実行されます。プログラムの初期実行を行うスレッドをマスタースレッドといいます。プログラムの起動時に、マスタースレッドによって複数のスレーブスレッドが生成されます (次の図を参照)。プログラムの終了時には、すべてのスレーブスレッドが終了されます。オーバーヘッドを最小限に抑えるために、スレーブスレッドの生成は 1 回だけ実行されます。

図 3-1 マスタースレッドとスレーブスレッド

起動後、マスタースレッドによってプログラムの実行が開始されますが、スレーブスレッドはアイドル状態で待機します。マスタースレッドが並列ループを検出すると、ループの異なる繰り返しがスレーブおよびマスタースレッドに割り当てられ、ループの実行が開始されます。それぞれのスレッドが実行を終了すると、残りのスレッドの終了と同期が取られます。この同期を取る点を「バリア」といいます。すべてのスレッドが分担した実行を終了してバリアに達するまで、マスタースレッドは残りのプログラムを実行することができません。スレーブスレッドは、バリアに達すると、ほかの並列化された部分が検出されるまで待ち状態になり、マスタースレッドがプログラムの実行を続行します。

この処理では、次に説明するオーバーヘッドが発生します。

同期と作業を分散するためのオーバーヘッド
バリア同期でのオーバーヘッド

一般的な並列ループの中には、並列化で得られるメリットよりオーバーヘッドの方が多くなってしまうものがあります。このようなループでは、実行速度が大きく低下することがあります。次の図ではループが並列化されていますが、水平の棒で示されたバリアは相当なオーバーヘッドを示しています。バリア間の作業は、図中に示すとおりに 1 つずつ実行される (順次実行) か、あるいは同時に実行 (並列実行) されます。ループの並列実行に必要な時間は、バリアの位置でマスタースレッドとスレーブスレッドの同期を取るために必要な時間よりはるかに短くてすみます。

図 3-2 ループの並列実行

3.4.2 固有スカラーと固有配列

データの依存性が存在してもコンパイラがループを並列化できる場合があります。次の例を考えてみましょう。

例 3-4 依存性があるが並列化可能なループ

for (i=1; i < 1000; i++) {
    t = 2 * a[i];           /* S1 */
    b[i] = t;               /* S2 */
}

この例では、配列 a と b が重なりあっていないと仮定すると、2 回の繰り返しの間に、変数 t による明らかなデータ依存性が存在します。繰り返しの 1 回目と 2 回目に注目すると、次のような文が実行されることになります。

例 3-5 繰り返し 1 と 2

t = 2*a[1];  /* 1 */
b[1] = t;    /* 2 */
t = 2*a[2];  /* 3 */
b[2] = t;    /* 4 */

文 1 および 3 によって変数 t が変更されるので、これらを並列実行することはできません。しかし、変数 t は常に同じ繰り返しの中で計算されて使用されるので、コンパイラは繰り返しごとに変数 t のコピーを使用することができます。したがって、このような変数による異なる繰り返し間での干渉を回避することができます。実際に変数 t は、繰り返しを実行する各スレッドに固有の変数として使用されます。これを説明した例を、次に示します。

例 3-6 各スレッドに固有の変数としての変数 t

for (i=1; i < 1000; i++) {
    pt[i] = 2 * a[i];       /* S1 */
    b[i] = pt[i];           /* S2 */
}

「3.4.2 固有スカラーと固有配列」は「3.4 データの依存性と干渉」と基本的に同じ例ですが、各スカラー変数参照 t が配列参照 pt に置き換えられています。各繰り返しでは、pt の異なる要素が使用されるので、任意の 2 個の繰り返し間でのデータ依存性がなくなります。ただし、この方法では、大きな配列を余分に生成することになります。実際には、コンパイラによってスレッドごとに 1 個の変数だけが割り当てられ、その変数をループの実行で使用します。つまりこのような変数は、スレッドごとに固有であるといえます。

コンパイラは、配列変数を固有化してループを並列実行することもできます。次の例を考えてみましょう。

例 3-7 配列変数を使用した並列化可能なループ

for (i=1; i < 1000; i++) {
    for (j=1; j < 1000; j++) {
            x[j] = 2 * a[i];        /* S1 */
            b[i][j] = x[j];         /* S2 */
    }
}

「3.4.2 固有スカラーと固有配列」では、外側のループの異なる繰り返しによって、配列 x の同じ要素が変更されるので、外側のループを並列化することはできません。しかし、外側のループを実行するそれぞれのスレッドに配列 x 全体のスレッド固有のコピーが存在すれば、外側の任意の 2 個のループ間で干渉が発生しません。これを説明した例を次に示します。

例 3-8 スレッド固有配列を使用した並列化可能なループ

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 */
    }
}

スレッド固有スカラー変数の場合と同様に、配列をすべての繰り返しに対して展開する必要はありません。システムで実行されるスレッドの数に対してのみ展開すればよいことになります。これはコンパイラによって自動的に行われ、各スレッドのスレッド固有領域にオリジナルの配列がコピーされます。

3.4.3 ストアバック変数の使用

変数のスレッド固有化は、プログラムの並列化を向上させる上で便利な方法です。しかし、スレッド固有変数がループの外側で参照される場合には、その値が正しいことを保証することが必要になります。次の例を考えてみましょう。

例 3-9 ストアバック変数を使用した並列ループ

for (i=1; i < 1000; i++) {
    t = 2 * a[i];           /* S1 */
    b[i] = t;               /* S2 */
}
x = t;                      /* S3 */

「3.4.3 ストアバック変数の使用」では、文 S3 で参照されている変数 t の値が、ループを終了したときの最終結果になります。変数 t がスレッド固有化され、ループの実行が終了したあと、t の正しい値をオリジナルの変数に戻すことが必要になります。この操作をストアバック (書き戻し) といいます。これは、繰り返しの最後における t の値をオリジナルの変数 t に書き込むことで実現できます。多くの場合、この操作はコンパイラによって自動的に行われます。しかし、最終値を簡単に計算できないこともあります。

例 3-10 ストアバック変数を使用できないループ

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 の値に等しくなります。すべての場合における t の最終値を計算することは、非常に困難です。このような場合には、コンパイラはループを並列化しません。

3.4.4 縮約変数の使用

ループの繰り返し間に本当の依存性が存在すると、依存性の原因となっている変数を簡単にスレッド固有化できない場合があります。このような状況は、たとえば、変数がある繰り返しから別の繰り返しで累積計算されているような場合に発生します。

例 3-11 並列化されるかどうか不明なループ

for (i=1; i < 1000; i++) {
    sum += a[i]*b[i]; /* S1 */
}

「3.4.4 縮約変数の使用」では、ループで 2 個の配列のベクトル積を計算して、共通変数 sum を求めています。このループを単純な方法で並列化することはできません。ここでは、文 S1 の計算式に結合の法則を適用し、各スレッドに対して psum[i]というスレッド固有変数を割り当てることができます。変数 psum[i]のコピーはそれぞれ 0 に初期化します。各スレッドは、スレッド固有の変数 psum[i] に自分で計算した部分和を代入します。バリアに達したら、すべての部分和を合計してオリジナルの変数 sum に代入します。この例では、和の縮約をしているので、変数 sum を縮約変数といいます。しかし、スカラー変数を縮約変数にした場合には、丸め誤差が累積されて、sum の最終値に影響する可能性があることに注意してください。コンパイラは、ユーザーによる明確な指示がされた場合に、この操作を実行します。

ナビゲーションリンクをスキップ
印刷ビューの終了
	Oracle Solaris Studio 12.2: C ユーザーガイド