ループの構造

ループには、一般的な DO-END DODO WHILE、あるいは IF/GOTO やラベルを使用できます。 ループは、入口が 1 つだけでかつ出口が 1 つだけでなければ、ベクトル化できません。以下の例は、ベクトル化が可能なループ構造とベクトル化が不可能なループ構造を示しています。

例: ベクトル化が可能な構造

subroutine vec(a, b, c)

  dimension a(100), b(100), c(100)

  integer i

  i = 1

  do while (i .le. 100)

    a(i) = b(i) * c(i)

      if (a(i) .lt. 0.0) a(i) = 0.0

        i = i + 1

  enddo

end subroutine vec

次の例は、ループが途中で終了する可能性があるために、ベクトル化が不可能なループを示しています。

例: ベクトル化が不可能な構造

subroutine no_vec(a, b, c)

  dimension a(100), b(100), c(100)

  integer i

  i = 1

  do while (i .le. 100)

    a(i) = b(i) * c(i)

! The next statement allows early

!

exit from the loop and prevents

! vectorization of the loop.

    if (a(i) .lt. 0.0) go to 10

    i = i + 1

  enddo

  10 continue

end subroutine no_vecN

END

ループ出口条件

ループ出口条件とは、1 つのループ実行の反復回数を決める条件のことです。for ループの場合は、固定インデックスによって反復回数が決まっています。ループの反復回数は数えられるものでなければなりません。つまり、反復回数を指定するときは次のいずれかを使用しなければなりません。

ループ出口が計算に依存する場合、ループは可算ではありません。以下の例は、可算/不可算ループの構造を示しています。

例: 可算ループ

subroutine cnt1 (a, b, c, n, lb)

  dimension a(n), b(n), c(n)

  integer n, lb, i, count

! Number of iterations is "n - lb + 1"

  count = n

  do while (count .ge. lb)

    a(i) = b(i) * c(i)

    count = count - 1

    i = i + 1

  enddo ! lb is not defined within loop

end

次の例は、異なる可算ループ構造を示しています。

例: 可算ループ

! Number of iterations is (n-m+2)/2

subroutine cnt2 (a, b, c, m, n)

  dimension a(n), b(n), c(n)

  integer i, l, m, n

  i = 1;

  do l = m,n,2

    a(i) = b(i) * c(i)

    i = i + 1

  enddo

end

次の例は、カウント値が異なる依存性ループであるために不可算のループ構造を示しています。

例: 不可算ループ

! Number of iterations is dependent on a(i)

subroutine foo (a, b, c)

  dimension a(100),b(100),c(100)

  integer i

  i = 1

  do while (a(i) .gt. 0.0)

    a(i) = b(i) * c(i)

    i = i + 1

  enddo

end

ストリップマイニングとクリーンアップ

ループのセクション化として知られるストリップマイニングは、メモリーのパフォーマンスを改善する手段で、ループの SIMD エンコーディングを可能にするループ変換テクニックです。大きなループをより小さなセグメントやストリップに断片化することで、このテクニックは次の 2 つの方法でループ構造を変更します。

ベクトライザーに最初に導入される場合、このテクニックは指定されたベクトルマシンの最大ベクトル長以下のサイズで各ベクトル演算が完了したときに生成されるコードからなります。

コンパイラーは、自動的にループをストリップマイニングし、クリーンアップ・ループを生成します。例えば、コンパイラーが次のループをストリップマイニングしたと仮定します。

例 1: ベクトル化前

i = 1

do while (i<=n)

  a(i) = b(i) + c(i) ! Original loop code

  i = i + 1

end do

コンパイラーは、次の方法でループを再構築することにより、ストリップマイニングとループ・クリーニングを制御します。

例 2: ベクトル化後

!The vectorizer generates the following two loops

i = 1

do while (i < (n - mod(n,4)))

! Vector strip-mined loop.

  a(i:i+3) = b(i:i+3) + c(i:i+3)

  i = i + 4

end do

do while (i <= n)

  a(i) = b(i) + c(i)     !Scalar clean-up loop

  i = i + 1

end do

ループ・ブロッキング

ループ・ブロッキングを、2 次元またはそれ以上の次元におけるストリップマイニングとして処理することができます。ループ・ブロッキングは、メモリー・パフォーマンスの最適化に有用な手法です。その主な目的は、できるだけ多くのキャッシュミスを排除することです。メモリー領域全域をシーケンシャルにトラバースするのではなく、小さなチャンクに変換します。特定の計算用の全データがキャッシュに格納できるように、各チャンクのサイズは小さいことが条件になります。これにより、最大限のデータ再利用が可能になります。

次の例について考えてみます。2 次元配列 A は、まず j (列) 方向に、その後、i (行) 方向に参照されます (列優先順)。配列 B は逆の順序で参照されます (行優先順)。メモリー配置が列優先順であると仮定します。したがって、このコードの配列 AB のアクセスのストライドは、それぞれ、1 と MAX になります。BS = block_size となり、MAX は BS で割り切れる必要があります。

次のようなループの例を考えてみます。

例: 元のループ

REAL A(MAX,MAX), B(MAX,MAX)

DO I =1, MAX

  DO J = 1, MAX

    A(I,J) = A(I,J) + B(J,I)

  ENDDO

ENDDO

配列は小さなチャンクにブロック化され、2 つのブロック化されたチャンクの合計サイズはキャッシュサイズよりも小さくなります。この結果、データの再利用が改善されます。この処理を行う 1 つの方法を次に示します。

例: ブロッキングの後の変換されたループ

REAL A(MAX,MAX), B(MAX,MAX)

DO I =1, MAX, BS

  DO J = 1, MAX, BS

   DO II = I, I+MAX, BS-1

    DO J = J, J+MAX, BS-1

     A(II,JJ) = A(II,JJ) + B(JJ,II)

    ENDDO

   ENDDO

  ENDDO

ENDDO

ループ交換と添字: マトリクス乗算

ループ交換には、ベクトル化できるユニットストライド構造が必要です。一般に、マトリクス乗算 (行列積) は下の例のように記述します。

例: 一般的なマトリクス乗算

subroutine matmul_slow(a, b, c)

  integer :: i, j, k

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

  do i = 1, n

    do j = 1, n

      do k = 1, n

        c(i,j) = c(i,j) + a(i,k)*b(k,j);

      end do

    end do

  end do

end subroutine matmul_slow

B(K,J) を使用するのは、ストライド-1 での参照ではないため、通常はベクトル化できません。

しかし、ループを交換すると、次の例に示すように、すべての参照がストライド-1 となります。

例: ストライド-1 でのマトリクス積

subroutine matmul_fast(a, b, c)

  integer :: i, j, k

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

  do j = 1, n

    do k = 1, n

      do i = 1, n

        c(i,j) = c(i,j) + a(i,k)*b(k,j)

      enddo

    enddo

  enddo

end subroutine matmul_fast

依存関係があるため、交換は常に可能であるとは限りません。依存関係によって異なる結果になる可能性があります。