ループの構造

ループは、一般的な for や while 構造で構成することができます。 ループは、入口が 1 つだけでかつ出口が 1 つだけでなければ、ベクトル化できません。以下の例は、ベクトル化が可能なループ構造とベクトル化が不可能なループ構造を示しています。

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

 
void vec(float a[], float b[], float c[])
{
  int i = 0;
  while (i < 100) {
// The if branch is inside body of loop.
    a[i] = b[i] * c[i];
    if (a[i] < 0.0)
        a[i] = 0.0;
        i++;
  }
}

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

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

 
void no_vec(float a[], float b[], float c[])
{
  int i = 0;
  while (i < 100) {
    if (a[i] < 50)
// The next statement is a second exit
// that allows an early exit from the loop.
      break;
    ++i;
  }
}

ループ出口条件

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

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

例: 可算ループ

 
void cnt1(float a[], float b[], float c[],
          int n, int lb)
{
// Exit condition specified by "N-1b+1"
  int cnt=n, i=0;
  while (cnt >= lb) {
// lb is not affected within loop.
    a[i] = b[i] * c[i];
    cnt--;
    i++;
  }
}

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

例: 可算ループ

 
void cnt2(float a[], float b[], float c[],
          int m, int n)
{
// Number of iterations is "(n-m+2)/2".
  int i=0, l;
  for (l=m; l<n; l+=2) {
    a[i] = b[i] * c[i];
    i++;
  }
}

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

例: 不可算ループ

 
void no_cnt(float a[], float b[], float c[])
{
  int i=0;
// Iterations dependent on a[i].
  while (a[i]>0.0) {
    a[i] = b[i] * c[i];
    i++;
  }
}

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

ループのセクション化として知られるストリップマイニングは、メモリーのパフォーマンスを改善する手段で、ループの 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
      }
    }
  }
 }
}

ループ交換と添字: 行列乗算

ループ交換はメモリー・アクセス・パターンを向上するためによく使用されます。一般に、行列乗算は下の例のように記述します。

例: 一般的な行列乗算

 
void matmul_slow(float *a[], float *b[], float *c[])
{
  int N = 100;
  for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
      for (int k = 0; k < N; k++)
        c[i][j] = c[i][j] + a[i][k] * b[k][j];
}

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

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

例: ストライド-1 での行列積

 
void matmul_fast(float *a[], float *b[], float *c[])
{
  int N = 100;
  for (int i = 0; i < N; i++)
    for (int k = 0; k < N; k++)
      for (int j = 0; j < N; j++)
        c[i][j] = c[i][j] + a[i][k] * b[k][j];
}

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

親トピック: 自動ベクトル化

このヘルプトピックについてのフィードバックを送信

© 1996-2010 Intel Corporation. 無断での引用、転載を禁じます。