独立したループは並列化が可能なため、ループの独立性を把握することは重要です。独立したループの並列化は、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 |
ループが依存している (独立していない) 場合、ループのパフォーマンスを向上することはより困難になります。ループは、いくつかの一般的な方法に依存します。
以下のセクションでは、さまざまなループの依存性について説明します。
例 |
---|
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 |
ほとんどの再帰は完全には並列化できません。代わりに、並列化の外または中へのループを探します。アンロールを行うことでパフォーマンスを向上させることができます。
例 |
---|
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]; |
クロス反復の出力依存は、変数が書き込まれた後、異なる反復で再度書き込まれたときに発生します。次に、出力依存性の例を示します。
例 |
---|
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 |
コンパイラーは、リダクションを誤認識してフロー、アンチ、出力依存性またはループ伝播のメモリー依存エッジを報告することがあります。このような場合、コンパイラーはループのベクトル化またはソフトウェアのパイプライン化を行いません。