最適化手法の適用

コンパイラーはループに対して、交換、アンロール、キャッシュ・ブロッキング、ループ分配、ループ融合、およびロードペアなどの最適化を適用します (適用されないこともあります)。以下のセクションでは、ループを手動で変換する方法およびプラグマまたは内部オプションを使用してループを制御する方法を含めて、これらの変換について説明します。

ループ交換

ループ交換は、2 つの入れ子しているループの実行順を単純に交換する、高レベルな最適化 (HLO) によって適用される入れ子ループの交換です。通常は、キャッシュの局所性を向上するために、ループ内部で使用される配列要素に、連続するユニット・ストライド・アクセスを提供することで行われます。-O3 (Linux* および Mac OS* X) または /O3 (Windows*) オプションを指定すると、コンパイラーはループ交換を適用できる可能性があるかどうかを調べます。

次に、ループ交換の例を示します。

#define NUM 1024

void loop_interchange(

       double a[][NUM], double b[][NUM],

       double c[][NUM] )

{

  int i,j,k;

  // Loop before Loop Interchange

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

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

      for(k=0;k<NUM;k++)

        c[i][j] =c[i][j] + a[i][k] * b[k][j];

  // Loop after Loop Interchange of k & j loops

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

    for(k=0;k<NUM;k++)

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

        c[i][j] =c[i][j] + a[i][k] * b[k][j];

}

詳細は、「非ユニット・ストライド・メモリー・アクセス」を参照してください。

アンロール

ループアンロールは、単一のループ反復中にできるだけ多くの関数ユニットで有用な作業を行いながら、命令レベルの並列処理 (ILP) の利点を活用できる、HLO によって一般的に使用されるループ変換です。ループアンロールでは、より少ないループの反復で、ループの内部により多くの作業を追加します。

アンロールの動作を制御する次のようなプラグマおよび内部オプションがあります。

プラグマ

説明

#pragma unroll

自身をアンロールして、コンパイラーがアンロール要素を判断できるようにします。

#pragma unroll(n)

-unrolln (Linux および Mac OS X) または /Qunroll:n (Windows) は、ループを n 回アンロールするようにコンパイラーに指示します。

#pragma nounroll

指定したループをアンロールしないようにコンパイラーに指示します。

通常は、ループはキャッシュ・ライン・サイズの要因でアンロールします。数を使用して試してください。次のループを考えてみます。

#define NUM 1025

void loop_unroll_before(

       double a[][NUM], double b[][NUM],

       double c[][NUM])

{

  int i,j;

  int N,M;

  N=NUM;

  M=5;

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

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

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

}

4 で "i" または外部ループをアンロールすると仮定した場合、4 では 1025 の N を平等に分割できないことがわかります。この場合、アンロールは困難です。このため、次のような場合は、「ポスト・コンディショニング」を使用します。

#define NUM 1025

void loop_unroll_after(

       double a[][NUM], double b[][NUM],

       double c[][NUM])

{

  int i,j,K;

  int N,M;

  N=NUM;

  M=5;

  K = N % 4;

  // Main part of loop.

  for(i=0;i<N-K; i+=4)

    for (j=0;j<M; j++) {

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

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

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

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

    }

  // Post conditioning part of loop.

  for(i= N-K+1;i<N; i+=4)

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

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

}

ポスト・コンディショニングは、データのアライメントを保存してメモリー・アライメント・アクセスのペナルティーを回避できるので、プリ・コンディショニングよりもポスト・コンディショニングを推奨します。

キャッシュ・ブロッキング

キャッシュ・ブロッキングは、L1 キャッシュまたは L2 キャッシュの一部にフィットしやすいように、構造データブロックを含みます。データキャッシュの局所性を制御することで、アプリケーションはメモリー・バス・アクセスによるパフォーマンスの遅延を最小限にすることができます。アプリケーションは、データがキャッシュにある間にスレッドがデータに繰り返してアクセスできるように、大きな配列をメモリーの小さなブロックに分割してこの動作を制御します。

例えば、イメージはイメージ全体のより小さな部分またはビデオフレームを使用して処理できるので、キャッシュ・ブロッキング・テクニックは、イメージ処理アプリケーションおよびビデオ・アプリケーションに適しています。コンパイラーは、L2 キャッシュから実行するように命令の関連ブロックをグループ化して、同じテクニックをよく使用します。

キャッシュ・ブロッキング・テクニックの有効性は、データブロックのサイズ、プロセッサーのキャッシュサイズ、およびデータが再利用される回数に依存します。キャッシュサイズはプロセッサーによって異なります。アプリケーションは、CPUID 命令を使用してデータキャッシュのサイズを検出し、パフォーマンスが最大限になるようにキャッシュ・ブロッキングのタイルサイズを動的に調整できます。一般的に、キャッシュブロックのサイズは、物理的なキャッシュサイズの 1/2 から 3/4 にするべきです。ハイパースレッディング・テクノロジー (HT テクノロジー) が有効なシステムでは、物理的なキャッシュサイズの 1/4 から 1/2 にしてください (その他のデザインに関する詳細は、「ハイパースレッディング・テクノロジーの設計」を参照してください)。

キャッシュ・ブロッキングは HLO に適用され、同時にすべての配列をキャッシュに入れることができない大きな配列で使用されます。この手法は、(小さな領域の) キャッシュにデータのサブセットを入れて、データがメモリーからの新しいデータに置換される前に、このキャッシュされたデータをできるだけ有効に使用する 1 つの方法です。

#define NUM 1024

void cache_blocking_before(

       double a[][NUM][NUM], double b[][NUM][NUM],

       double c[][NUM][NUM], int N )

{

  int i,j,k;

  N=1000;

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

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

      for (k=0;k < N; k++)

        a[i][j][k] = a[i][j][k] + b[i][j][k];

}

#define NUM 1024

void cache_blocking_after(

       double a[][NUM][NUM], double b[][NUM][NUM],

       double c[][NUM][NUM], int N )

{

  int i,j,k,u,v;

  N=1000;

  for (v=0; v<N; v+=20)

    for (u=0; u<N; u+=20)

      for (k=v; k<v+20; k++)

        for (j=u;j< u+20;j++)

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

            a[i][j][k] = a[i][j][k] + b[i][j][k];

}

キャッシュブロックのサイズは 20 に設定されます。目的は、キャッシュにあるデータのブロックを読み取って、可能なすべてのビットの計算を行った後、新しいデータのブロックをキャッシュにロードすることです。同時にキャッシュに A の 20 の要素と B の 20 の要素があり、次のキャッシュブロックに進む前に、このデータで可能な限りの作業を行います。

アーキテクチャーが異なると、ブロッキング系数も異なります。ブロッキング系数は経験的に判断します。例えば、単精度と倍精度では異なるブロッキング系数が必要です。通常、パフォーマンスに与える影響は非常に大きくなります。

ループ分配

ループ分配は、1 つの大きなループを 2 つの小さなループに分割する高レベルループ変換です。レジスターの使用率が高いためにソフトウェアのパイプライン化 (SWP) やベクトル化のような最適化を実行できない場合に役立ちます。ループをより小さなセグメントに分割することによって、より小さな各ループ、またはその少なくとも 1 つをソフトウェアのパイプライン化またはベクトル化できる可能性があります。次に例を示します。

#define NUM 1024

void loop_distribution_before(

       double a[NUM], double b[NUM], double c[NUM],

       double x[NUM], double y[NUM], double z[NUM] )

{

  int i;

  // Before distribution or splitting the loop.

  for (i=0; i< NUM; i++) {

    a[i] = a[i] + i;

    b[i] = b[i] + i;

    c[i] = c[i] + i;

    x[i] = x[i] + i;

    y[i] = y[i] + i;

    z[i] = z[i] + i;

  }

}

#define NUM 1024

void loop_distribution_after(

       double a[NUM], double b[NUM], double c[NUM],

       double x[NUM], double y[NUM], double z[NUM] )

{

  int i;

  // After distribution or splitting the loop.

  for (i=0; i< NUM; i++) {

    a[i] = a[i] +i;

    b[i] = b[i] +i;

    c[i] = c[i] +i;

  }

  for (i=0; i< NUM; i++) {

    x[i] = x[i] +i;

    y[i] = y[i] +i;

    z[i] = z[i] +i;

  }

}

次のように、コンパイラーにループの分配を推奨するプラグマがあります。

#pragma distribute point

プラグマがループの外部に配置されると、コンパイラーはその内部ヒューリスティックに基づいてループを分配しようとします。次に、ループの外部でプラグマを使用する例を示します。

#define NUM 1024

void loop_distribution_pragma1(

       double a[NUM], double b[NUM], double c[NUM],

       double x[NUM], double y[NUM], double z[NUM] )

{

  int i;

  // Before distribution or splitting the loop

  #pragma distribute point

  for (i=0; i< NUM; i++) {

    a[i] = a[i] + i;

    b[i] = b[i] + i;

    c[i] = c[i] + i;

    x[i] = x[i] + i;

    y[i] = y[i] + i;

    z[i] = z[i] + i;

  }

}

ループの内部に配置されると、コンパイラーはそのポイントでループを分配しようとします。ループ伝播の依存はすべて無視されます。次の例は、分割すべき場所を正確に示すためにループの内部でプラグマを使用しています。

#define NUM 1024

void loop_distribution_pragma2(

       double a[NUM], double b[NUM], double c[NUM],

       double x[NUM], double y[NUM], double z[NUM] )

{

  int i;

  // After distribution or splitting the loop.

  for (i=0; i< NUM; i++) {

    a[i] = a[i] +i;

    b[i] = b[i] +i;

    c[i] = c[i] +i;

    #pragma distribute point

    x[i] = x[i] +i;

    y[i] = y[i] +i;

    z[i] = z[i] +i;

  }

}

ループ融合

ループ融合は、ループ分配の逆です。ループ融合の目的は、ループのオーバーヘッドを減らすために、同じトリップカウントの 2 つのループを連結することです。-O3 (Linux) または /O3 (Windows) オプションを使用すると、機会があればループ融合が行われます。

ロードペア (IA-64 対応コンパイラー)

ロードペア (ldfp) は、1 回の転送でメモリーから 2 つの連続した単精度または倍精度値をロードする命令です。ロードペアは、パフォーマンスを大幅に向上させることができます。

手動ループ変換

手動ループ変換が使用可能な場合や、推奨される場合もあります。ただし、通常は、手動ではなく、コンパイラーでループ変換を行うようにすべきです。手動変換は最後の手段です。パフォーマンスの向上を試みている場合にのみ、この手法を使用してください。

手動ループ変換には、次のような多くの短所があります。

HLO レポートは、コンパイラーによって適用されたループ変換についての情報を知らせます。

手動でループを変換する場合に重要なのは経験です。コンパイラーが無視したループ変換を適用する場合もあります。また、コンパイラーが -O3 (Linux) または /O3 (Windows) を適用した後に手動ループ変換を適用すると良い場合もあります。