ループには、一般的な DO-END DO や DO 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 つの方法でループ構造を変更します。
データがアルゴリズムの異なるパスで再利用可能な場合、データキャッシュ中の一時的な空間が増加します。
各ベクトルの長さ、または SIMD 演算ごとに実行される演算の数により、ループの反復数は減ります。ストリーミング SIMD 拡張命令の場合、このベクトルまたはストリップの長さは 4 回 (1 つのストリーミング SIMD 拡張単精度浮動小数点 SIMD 演算が処理されるごとに 4 つの浮動小数点データ項目が) 減ります。
ベクトライザーに最初に導入される場合、このテクニックは指定されたベクトルマシンの最大ベクトル長以下のサイズで各ベクトル演算が完了したときに生成されるコードからなります。
コンパイラーは、自動的にループをストリップマイニングし、クリーンアップ・ループを生成します。例えば、コンパイラーが次のループをストリップマイニングしたと仮定します。
例 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 は逆の順序で参照されます (行優先順)。メモリー配置が列優先順であると仮定します。したがって、このコードの配列 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 となります。
例: ストライド-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 |
依存関係があるため、交換は常に可能であるとは限りません。依存関係によって異なる結果になる可能性があります。