3.3 データの依存性と干渉

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

例 3-1 依存性があるループ

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

この例では、2 つの連続する繰り返し、i および i+1 が、同じ変数 sum に対して書き込みと読み込みを実行します。したがって、このような 2 個の繰り返しを並列に実行するには、なんらかの方法で変数をロックすることが必要になります。そうしない場合、2 つの繰り返しを並列で実行するのを許可することは安全ではありません。

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

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

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

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

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

• 依存性があります。この場合、ループを並列で実行することは安全ではありません。

• 依存性がありません。この場合、任意の数のプロセッサを使用してループを並列で安全に実行する可能性があります。

• 依存性を確認できません。コンパイラは、安全のために、依存関係がループの並列実行を妨げる可能性があると仮定し、ループを並列化しません。

この例では、ループの 2 つの繰り返しが配列 a の同じ要素に書き込むかどうかは、配列 b が重複要素を含んでいるかどうかによって決まります。コンパイラは、この事実を判断できないかぎり、依存性が存在する可能性があると仮定し、ループを並列化しないようにする必要があります。

例 3-3 依存性を含んでいる可能性のあるループ

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

3.3.1 並列実行モデル

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

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

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

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

• 同期と作業の分散

• バリアー同期

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

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

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

この例では、各スカラー変数参照 t が、配列参照 pt で置き換えられています。各繰り返しが pt の異なる要素を使用するようになり、任意の 2 つの繰り返し間でのデータ依存性がなくなります。これの問題の 1 つは、さらに大きな配列になる可能性があることです。実際には、コンパイラによってスレッドごとに 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 */
    }
}

この例では、外側のループの異なる繰り返しが配列 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 */
    }
}

スレッド固有スカラーの場合と同じく、システムで実行されるスレッドの数までしかこの配列を展開する必要はありません。この展開は、各スレッドのスレッド固有領域にオリジナル配列の 1 つのコピーを割り当てることで、コンパイラによって自動的に行われます。

3.3.3 ストアバック

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

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

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 のコピーを元の場所に戻すことで実現されます。多くの場合、コンパイラはこれを自動的に行うことができますが、最後の値を容易に計算できない場合があります。

例 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 の最終値の計算は困難である可能性があります。この例のような場合には、コンパイラはループを並列化しません。

3.3.4 縮約変数

ループの繰り返し間に実際の依存性が存在しており、依存性の原因となる変数をスレッド固有化するだけでは依存性を除去できない場合があります。たとえば、ある繰り返しから別の繰り返しへ値が累積される次のコードを見てみます。

例 3-11 並列化される可能性のあるループ

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 の最終値に影響する可能性があることに注意してください。コンパイラは、ユーザーによる明確な指示がされた場合に、この操作を実行します。