10.1.3 データ依存性の問題

すべてのループが並列化できるわけではありません。複数のプロセッサ上でループを並列実行すると、実行している反復の順序が変わる可能性があります。さらに、ループを並列実行する複数のプロセッサがお互いに干渉する可能性もあります。 このような状況が発生するのは、ループ中にデータ依存性がある場合です。

データ依存性の問題が発生する場合は、再帰、縮約、間接アドレス指定、データに依存するループが繰り返されています。

10.1.3.1 データに依存したループ

ループを書き直して、並列化することで、データへの依存をなくすことができます。しかし、拡張再構成が必要な場合があります。

次は、いくつかの一般的な規則です。

• すべての繰り返しが個々のメモリー位置に書き込む場合のみ、ループはデータから独立しています。

• いずれの繰り返しも同じ位置に書き込まないかぎり、繰り返しはその位置から読み取る場合があります。

これらは並列化の一般的な条件です。ループを並列化するかどうか決める際に、コンパイラの自動並列化解析により、追加の条件が検討されます。しかし、抑制により誤った結果を出すループも含め、ループを明示的に並列化する指令を使用することができます。

10.1.3.2 再帰

ループのある反復で設定され、後続の反復で使用される変数は、反復間依存性、つまり再帰の原因となります。ループ中で再帰を行う場合は、反復が適切な順序で実行される必要があります。たとえば、次のようにします。

   DO I=2,N
      A(I) = A(I-1)*B(I)+C(I)
   END DO

たとえば、前述のコードでは、以前の反復中で A(I) 用に計算された値が、現在の反復中で (A(I-1) として) 使用されなければいけません。各反復を並列実行して、1 つのプロセッサで実行したときと同じ結果を生成するためには、反復 I は、反復 I+1 が実行できる前に完了している必要があります。

10.1.3.3 縮約

縮約操作は、配列の要素を 1 つの値に縮約します。たとえば、配列の要素の合計を 1 つの変数にまとめる場合、その変数は反復ごとに更新されます。

   DO K = 1,N
     SUM = SUM + A(I)*B(I)
   END DO

このループを並列実行する各プロセッサが反復のサブセットを取る場合、SUM の値を上書きしようとして、各プロセッサはお互いに干渉します。うまく処理するためには、各プロセッサが 1 度に 1 回ずつ合計を実行する必要があります。しかし、順序は問題になりません。

ある共通の縮約操作は、コンパイラによって、特別なケースであると認識され、処理されます。

10.1.3.4 間接アドレス指定

ループ依存性は、値が未知である添字によってループの中の添字付けられた配列への格納から発生する可能性があります。たとえば、添字付の配列中に繰り返される値がある場合、間接アドレス指定は順序に依存することがあります。

   DO L = 1,NW
     A(ID(L)) = A(L) + B(L)
   END DO

前述の例中、ID 中で繰り返される値は、 A の要素を上書きする原因となります。逐次処理の場合、最後の格納が最終値です。並列処理の場合、順序は決定されていません。使用される A(L) の値 (古い値か更新された値) は、順序に依存します。