インテル® C++ コンパイラー 18.0 デベロッパー・ガイドおよびリファレンス

ループの構造

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

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

 
void vec(float a[], float b[], float c[]) {
  int i = 0;
  while (i < 100) { 
// if 分岐はループ本体内
    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) 
// 次の文はループを途中で終了する 
// 第 2 出口
      break;
    ++i;
  } 
}

ループ出口条件

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

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

可算ループの例

 
void cnt1(float a[], float b[], float c[],
          int n, int lb) { 
// "N-1b+1" で指定された出口条件
  int cnt=n, i=0;
  while (cnt >= lb) { 
// lb はループ内で変更されない
    a[i] = b[i] * c[i];
    cnt--;
    i++;
  } 
}

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

可算ループの例

 
void cnt2(float a[], float b[], float c[],
          int m, int n) 
{ 
// 反復回数は "(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; 
// 反復回数は a[i] に依存
  while (a[i]>0.0) {
    a[i] = b[i] * c[i];
    i++;
  } 
}

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

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

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

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

ベクトル化前のコード例

 
i=0; 
while(i<n) {
  // オリジナルのループコード
  a[i]=b[i]+c[i];
  ++i; 
}

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

ベクトル化後のコード例

 
// ベクトル化により次の 2 つのループが生成される
i=0; 
while(i<(n-n%4)) {
  // ベクトル・ストリップ・マイニング・ループ
  // 添字 [i:i+3] は SIMD 実行を示す
  a[i:i+3]=b[i:i+3]+c[i:i+3];
  i=i+4; 
} 
while(i<n) {
  // スカラー・クリーンアップ・ループ
  a[i]=b[i]+c[i];
  ++i; 
}

ループ・ブロッキング

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

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

元のループの例

 
#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; 

// 配列の初期化
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); // add 関数の実行にかかる時間を表示する
} 

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]; // 2 つの行列の加算
    }
  } 
}

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

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

#include <stdio.h> #include <time.h> #define MAX 7000 void add(int a[][MAX], int b[][MAX]); int main() { #define BS 8 // ブロックサイズをループ・ブロッキング係数として選択 int i, j; int A[MAX][MAX]; int B[MAX][MAX]; time_t start, elaspe; int sec; // 配列の初期化 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); // loopBlocking 関数の実行にかかる時間を表示する } 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++) { // 外側のループ for(jj=j;jj<j+BS; jj++) { // 配列 B は外側のループの各反復で // キャッシュミスが発生する a[ii][jj] = a[ii][jj] + b[jj][ii]; // 2 つの配列の加算 } } } } }

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

ブロッキング後の変換されたループの例
#include <stdio.h> #include <time.h> #define MAX 7000 void add(int a[][MAX], int b[][MAX]); int main() { #define BS 8 // ブロックサイズをループ・ブロッキング係数として選択 int i, j; int A[MAX][MAX]; int B[MAX][MAX]; time_t start, elaspe; int sec; // 配列の初期化 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); // loopBlocking 関数の実行にかかる時間を表示する
} 

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++) {   // 外側のループ
       for(jj=j;jj<j+BS; jj++) {  // 配列 B は外側のループの各反復で
                                  // キャッシュミスが発生する
         a[ii][jj] = a[ii][jj] + b[jj][ii]; // 2 つの配列の加算
        }
      }
    }
  } 
}

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

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

一般的な行列乗算の例

 
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]; 
}

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

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