ループの構造

ループ出口条件

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

• 定数

• ループ不変項

• 最外ループ添字の線形関数

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

subroutine cnt1 (a, b, c, n, lb)
  dimension a(n), b(n), c(n)
  integer n, lb, i, count 
! 反復回数は "n - lb + 1"
  count = n
  do while (count .ge. lb)
    a(i) = b(i) * c(i)
    count = count - 1
    i = i + 1
  enddo ! lb はループ内で定義されていない
end

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

! 反復回数は (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

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

! 反復回数は 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 つの方法でループ構造を変更します。

• データがアルゴリズムの異なるパスで再利用可能な場合、データキャッシュ中の一時的な空間を増やします。

• 各ベクトルの長さ、または SIMD 演算ごとに実行される演算の数により、ループの反復数を減らします。インテル® SSE の場合、このベクトルまたはストリップの長さは 4 分の 1 に減ります (1 つの単精度浮動小数点 SIMD 演算につき 4 つの浮動小数点データ項目が処理されます)。

最初にベクトル化で導入されたこのテクニックは、指定されたベクトルマシンの最大ベクトル長以下のサイズで各ベクトル演算が行われる場合にコードを生成します。

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

i = 1 
do while (i<=n)
  a(i) = b(i) + c(i) ! オリジナルのループコード
  i = i + 1 
end do

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

! ベクトル化により次の 2 つのループが生成される
i = 1 
do while (i < (n - mod(n,4))) 
! ベクトル・ストリップ・マイニング・ループ
  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)     ! スカラー・クリーンアップ・ループ
  i = i + 1 
end do

ループ・ブロッキング

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

次の例について考えてみます。2 次元配列 A は、まず j (列) 方向に、その後、i (行) 方向に参照されます (列優先順)。配列 B は逆の順序で参照されます (行優先順)。メモリー配置が列優先順であると仮定します。したがって、このコードの配列 A と B のアクセスのストライドは、それぞれ、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 となります。

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

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