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

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

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

コンパイラは、自動的にループをストリップ・マイニングし、クリーンアップ・ループを生成します。

ストリップ・マイニングとクリーンアップ・ループの例:

!ベクトル化前


i = 1
do while (i<=n)
a(i) = b(i) + c(i) !Original loop code
i = i + 1
end do


!ベクトル化後


!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 のアクセスのストライドは、それぞれ、1MAX になります。

B. の例では、 BS = block_size となり、MAXBS で割り切れる必要があります。

配列のループ・ブロッキングの例:

A. 元のループ
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
 

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


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