ループの独立性

独立したループは並列化が可能なため、ループの独立性を把握することは重要です。独立したループの並列化は、OpenMP* の粗粒度の並列処理から、ベクトル化およびソフトウェアのパイプライン化のような細粒度の命令レベルの並列処理 (ILP) まで、さまざまな方法で可能です。

反復 X の計算と無関係にループの反復 Y の計算を行うことができる場合、ループは独立していると考えられます。別の言い方をすれば、ループの反復 1 を計算し、同時に反復 1 の結果を使用しないで反復 2 を計算できる場合、ループは独立しています。

ループの出力の結果と、インデックス・カウンターを減らして記述された同じループからの結果を比較して、ループが独立しているかどうかを判断できます。

例えば、2 つめの例のコードが同じ結果を生成する場合、1 つめの例に示すループは独立しています。

subroutine loop_independent_A (a,b,MAX)

  implicit none

  integer :: j, MAX, a(MAX), b(MAX)

  do j=0, MAX

   a(j) = b(j)

  end do

end subroutine loop_independent_A

subroutine loop_independent_B (a,b,MAX)

  implicit none

  integer :: j, MAX, a(MAX), b(MAX)

  do j=MAX, 0, -1

   a(j) = b(j)

  end do

end subroutine loop_independent_B

ループが依存している (独立していない) 場合、ループのパフォーマンスを向上することはより困難になります。ループは、いくつかの一般的な方法に依存します。

以下のセクションでは、さまざまなループの依存性について説明します。

フロー依存性 - WRITE の後の READ

クロス反復のフロー依存は、次の例で示されているように、変数が読み取られた後、異なる反復で書き込まれたときに発生します。

subroutine flow_dependence (A,MAX)

  implicit none

  integer :: J,MAX

  real :: A(MAX)

  do j=1, MAX

   A(J)=A(J-1)

  end do

end subroutine flow_dependence

上記の例は、最初のいくつかの反復について、次の行に相当します。

反復のサンプル

A[1]=A[0];

A[2]=A[1];

再帰関係は、ある反復から次の反復に情報を次々に送ります。

subroutine time_stepping_loops (a,b,MAX)

  implicit none

  integer :: J,MAX

  real :: a(MAX), b(MAX)

  do j=1, MAX

   a(j) = a(j-1) + b(j)

  end do

end subroutine time_stepping_loops

ほとんどの再帰は完全には並列化できません。代わりに、並列化の外または中へのループを探します。アンロールを行うことでパフォーマンスを向上させることができます。

アンチ依存性 - READ の後の WRITE

クロス反復のアンチ依存は、次の例で示されているように、変数が書き込まれた後、異なる反復で読み取られたときに作成されます。

subroutine anti_dependence (A,MAX)

  implicit none

  integer :: J,MAX

  real :: a(MAX), b(MAX)

  do J=1, MAX

   A(J)=A(J+1)

  end do

end subroutine anti_dependence

上記の例は、最初のいくつかの反復について、次の行に相当します。

反復のサンプル

A[1]=A[2];

A[2]=A[3];

出力依存性 - WRITE の後の WRITE

クロス反復の出力依存は、変数が書き込まれた後、異なる反復で再度書き込まれたときに発生します。次に、出力依存性の例を示します。

subroutine output_dependence (A,B,C,MAX)

  implicit none

  integer :: J,MAX

  real :: a(MAX), b(MAX), c(MAX)

  do J=1, MAX

   A(J)=B(J)

   A(J+1)=C(J)

  end do

end subroutine output_dependence

上記の例は、最初のいくつかの反復について、次の行に相当します。

反復のサンプル

A[1]=B[1];

A[2]=C[1];

A[2]=B[2];

A[3]=C[2];

リダクション

インテル® コンパイラーは、乗算 (*)、加算 (+)、減算 (-)、および除算 (/) のような単純な算術演算子のリダクションを含む大部分のループをソフトウェアのパイプライン化 (SWP) またはベクトル化することができます。リダクションは、結合操作を使用して配列データをスカラーデータにします。

subroutine reduction (sum,c,MAX)

  implicit none

  integer :: j,MAX

  real :: sum, c(MAX)

  do J=0, MAX

   sum = sum + c(j)

  end do

end subroutine reduction

コンパイラーは、リダクションを誤認識してフロー、アンチ、出力依存性またはループ伝播のメモリー依存エッジを報告することがあります。このような場合、コンパイラーはループのベクトル化またはソフトウェアのパイプライン化を行いません。