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

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

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

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

例 1: ベクトル化前

i=0;

while(i<n)

{

  // Original loop code 

  a[i]=b[i]+c[i];

  ++i;

}

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

例 2: ベクトル化後

// The vectorizer generates the following two loops 

i=0;

while(i<(n-n%4))

{

  // Vector strip-mined loop

  // Subscript [i:i+3] denotes SIMD execution

  a[i:i+3]=b[i:i+3]+c[i:i+3];

  i=i+4;

}

while(i<n)

{

  // Scalar clean-up loop

  a[i]=b[i]+c[i];

  ++i;

}

ループ・ブロッキング

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

次の例について考えてみます。ループ・ブロッキングによって配列 A および B は小さな矩形のチャンクにブロック化され、2 つのブロック化されたチャンクの合計サイズはキャッシュサイズよりも小さくなります。この結果、データの再利用が改善されます。

例 3: 元のループ

#include <time.h>

#include <stdio.h>

#define MAX 7000

void add(int a[][MAX], int b[][MAX]);

int main()

{

int i, j;

int A[MAX][MAX];

int B[MAX][MAX];

time_t start, elaspe;

int sec;

//Initialize array

for(i=0;i<MAX;i++)

 {

  for(j=0;j<MAX; j++)

  {

    A[i][j]=j;

    B[i][j]=j;

  }

 }

 start= time(NULL);

 add(A, B);

 elaspe=time(NULL);

 sec = elaspe - start;

 printf("Time %d",sec); //List time taken to complete add function

}

void add(int a[][MAX], int b[][MAX])

{

 int i, j;

 for(i=0;i<MAX;i++)

  {

  for(j=0;j<MAX; j++)

   {

     a[i][j] = a[i][j] + b[j][i]; //Adds two matrices

   }

  }

}

次の例は、(前の例にある) ループ・ブロッキングの add 関数を示しています。この最適化による利点を得るには、キャッシュサイズを増やす必要があります。

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

#include <stdio.h>

#include <time.h>

#define MAX 7000

void add(int a[][MAX], int b[][MAX]);

int main()

{

#define BS 8  //Block size is selected as the loop-blocking factor.

int i, j;

int A[MAX][MAX];

int B[MAX][MAX];

time_t start, elaspe;

int sec;

//initialize array

for(i=0;i<MAX;i++)

 {

  for(j=0;j<MAX;j++)

  {

    A[i][j]=j;

    B[i][j]=j;

  }

 }

start= time(NULL);

add(A, B);

elaspe=time(NULL);

sec = elaspe - start;

printf("Time %d",sec); //Display time taken to complete loopBlocking function

}

void add(int a[][MAX], int b[][MAX])

{

int i, j, ii, jj;

for(i=0;i<MAX;i+=BS)

 {

 for(j=0; j<MAX;j+=BS)

  {

   for(ii=i; ii<i+BS; ii++)//outer loop

    {

     for(jj=j;jj<j+BS; jj++) //Array B experiences one cache miss

      {                      //for every iteration of outer loop

        a[ii][jj] = a[ii][jj] + b[jj][ii]; //Add the two arrays

      }

    }

  }

 }

}