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

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