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];
}