3.2.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 つのコピーを割り当てることで、コンパイラによって自動的に行われます。