ループのセクション化として知られるストリップマイニングは、メモリーのパフォーマンスを改善する手段で、ループの SIMD エンコーディングを可能にするループ変換テクニックです。大きなループをより小さなセグメントやストリップに断片化することで、このテクニックは次の 2 つの方法でループ構造を変更します。
データがアルゴリズムの異なるパスで再利用可能な場合、データキャッシュ中の一時的な空間が増加します。
各ベクトルの長さ、または SIMD 演算ごとに実行される演算の数により、ループの反復数は減ります。ストリーミング SIMD 拡張命令の場合、このベクトルまたはストリップの長さは 4 回 (1 つのストリーミング SIMD 拡張単精度浮動小数点 SIMD 演算が処理されるごとに 4 つの浮動小数点データ項目が) 減ります。
ベクトライザーに最初に導入される場合、このテクニックは指定されたベクトルマシンの最大ベクトル長以下のサイズで各ベクトル演算が完了したときに生成されるコードからなります。
コンパイラーは、自動的にループをストリップマイニングし、クリーンアップ・ループを生成します。例えば、コンパイラーが次のループをストリップマイニングしたと仮定します。
例 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 } } } } } |