HPC
C/C++
Fortran
MIC

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

同カテゴリーの次の記事

メモリーレイアウト変換

この記事は、インテル® ソフトウェア・サイトに掲載されている「Cache Blocking Techniques」の日本語参考訳です。

はじめに

アルゴリズムの重要な変更の 1 つは、キャッシュに収まるようにデータ構造をブロッキングすることです。データのメモリーアクセスを調整し、キャッシュに大規模なデータのサブセット (ブロック) をロードして、そのデータブロックを使用して処理を行います。キャッシュのデータを利用/再利用することで、メモリーアクセス (つまり、メモリー帯域幅への負担) を減らすことができます。

トピック

ブロッキングは、多くのアプリケーションにおいてメモリー帯域幅のボトルネックを回避するのに役立つ一般的な最適化手法です。ブロッキングの目的は、複数回使用されるデータをキャッシュに保持することで、データ再利用の機会を活用することです。

ブロッキングは、1 次元、2 次元、または 3 次元の空間データ構造で行えます。一部の反復アプリケーションでは、複数の反復にわたってブロッキングを行うことで (一時ブロッキングと呼ばれる)、帯域幅のボトルネックをさらに減らすことができます。通常、ブロッキングに伴うコード変更として、ループ分割とループ変換があります。ほとんどのアプリケーション・コードでは、適切なコード変更とブロック要素のパラメーター化により、ブロッキングを行えます。

オリジナルのサンプルコード:

for (body1=0; body1 < NBODIES; body1++){
    for (body2=0; body2 < NBODIES; body2++) {
        OUT[body1] += compute(body1, body2);
    }
}

このサンプルコードでは、データ (body2) がメモリーから渡されます。NBODIES が大きい場合、キャッシュ内のデータを再利用することはできません。そのため、このアプリケーションはメモリー帯域幅により制限されます (アプリケーションは、メモリーから CPU への転送速度で実行されるため、最適なパフォーマンスが得られません)。

変更後のサンプルコード (1 次元のブロッキング):

for (body2=0; body2 < NBODIES; body2 += BLOCK) {
    for (body1=0; body1 < NBODIES; body1++) {
        for (body22=0; body22 < BLOCK; body22++) {
            OUT[body1] += compute(body1, body2 + body22);
        }
    }
}

この変更済みのコードでは、データ (body22) がキャッシュに保持され、再利用されるため、パフォーマンスが向上します。

上記のコードは NBody コードのブロッキング例です。2 つのループ (body1 と body2) はすべての body を反復します。オリジナルのコードは、内側のループですべての body を渡し、各反復で body2 の値をメモリーからロードする必要があります。ブロッキングしたコードでは、body2 ループが、BLOCK の倍数で body を反復する外側のループと、ブロック内の要素を反復する内側の body22 ループの 2 つに分割され、body1 ループと body2 ループが交互に配置されています。このコードでは、BLOCK にある body2 の値が、body1 ループの複数の反復で再利用されています。この値がキャッシュに収まるように BLOCK を選択すると、メモリー・トラフィックが 1/BLOCK に減ります。

以下は、NBody ベンチマークの OpenMP* バージョンのサンプルコードです (CHUNK_SIZE 倍でブロッキングされています)。このコードでは、アンロール-ジャム変換がプラグマで指定され、コンパイラーによって処理されます。コンパイラーが実際にループに対してアンロール-ジャムによる最適化を行ったかどうかは、-opt-report の出力で確認できます。

#define CHUNK_SIZE 8192

#pragma omp parallel private(body_start_index)
  for(body_start_index = 0; body_start_index < global_number_of_bodies; body_start_index += CHUNK_SIZE){
    int i;
    int body_end_index = body_start_index + CHUNK_SIZE;

    #pragma omp for private(i) schedule(guided)
    #pragma unroll_and_jam (4)
    for(i=starting_index; i < ending_index; i++){
      int j;
      TYPE acc_x_0 = 0, acc_y_0 = 0, acc_z_0 = 0;
      for(j=body_start_index; j < body_end_index; j+=1){
        TYPE delta_x_0 = Input_Position_X[(j+0)] - Input_Position_X[i];
        TYPE delta_y_0 = Input_Position_Y[(j+0)] - Input_Position_Y[i];
        TYPE delta_z_0 = Input_Position_Z[(j+0)] - Input_Position_Z[i];

        TYPE gamma_0 = delta_x_0*delta_x_0 + delta_y_0*delta_y_0 + delta_z_0*delta_z_0 + epsilon_sqr;
        TYPE s_0 = Mass[j+0]/(gamma_0 * SQRT(gamma_0));
        acc_x_0 += s_0*delta_x_0;
        acc_y_0 += s_0*delta_y_0;
        acc_z_0 += s_0*delta_z_0;
      }
      Output_Acceleration[3*(i+0)+0] += acc_x_0;
      Output_Acceleration[3*(i+0)+1] += acc_y_0;
      Output_Acceleration[3*(i+0)+2] += acc_z_0;
    }
  }

次に、行列乗算を行う Fortran のサンプルコードを示します。変更後のコードは、パフォーマンスを最適化するため、配列のローカルコピーを使用して、高度なブロック-アンロール-ジャム変換を行います。

オリジナルの Fortran のサンプルコード:

do j = 1, N
  do k = 1, N
    do i = 1, N
      c(i,j) = c(i,j) + a(i,k) * b(k,j)
    end do
  end do
end do

変更後の Fortran のサンプルコード:

     do JJ = 1, N, TJ
       do KK = 1, N, TK
         do jjj = 1, min(tj,N-jj+1)               ! BCOPY - no transpose
           do kkk = 1, min(tk,N-kk+1)
             p(kkk,jjj-1+1) = B(kk+kkk-1, jj+jjj-1)
           end do
         end do
         do II = 1, N, TI
           do iii = 1, min(ti,N-ii+1)               ! ACOPY - transpose
             do kkk = 1, min(tk,N-kk+1)
               Q(kkk,iii) = A(ii+iii-1, kk+kkk-1)
             end do
           end do
           do J = 1, min(tj,N-jj+1), 4
             do I = 1, min(ti,N-ii+1), 2
               t1 = 0 ; t2 = 0 ; t5 = 0 ; t6 = 0 ; t9 = 0 ; t10 = 0 ; t13 =0 ; t14 = 0
               !DIR$ vector aligned
               !DIR$ unroll(2)
               do K = 1, min(TK,N-kk+1)    ! Innermost loop, vectorized and unrolled by 2 after that
                 qi  = Q(K,I)           ;  qi1 = Q(K,I+1)
                 t1  = t1+ qi*P(K,J)    ;  t2  = t2+ qi1*P(K,J)
                 t5  = t5+ qi*P(K,J+1)  ;  t6  = t6+ qi1*P(K,J+1)
                 t9  = t9+ qi*P(K,J+2)  ;  t10 = t10+ qi1*P(K,J+2)
                 t13 = t13+ qi*P(K,J+3) ;  t14 = t14+ qi1*P(K,J+3)
               end do
               c(i+ii-1,j+jj-1)   = c(i+ii-1,j+jj-1) + t1    ; c(i+1+ii-1,j+jj-1)   = c(i+1+ii-1,j+jj-1) + t2
               c(i+ii-1,j+1+jj-1) = c(i+ii-1,j+1+jj-1) + t5  ; c(i+1+ii-1,j+1+jj-1) = c(i+1+ii-1,j+1+jj-1) + t6
               c(i+ii-1,j+2+jj-1) = c(i+ii-1,j+2+jj-1) + t9  ; c(i+1+ii-1,j+2+jj-1) = c(i+1+ii-1,j+2+jj-1) + t10
               c(i+ii-1,j+3+jj-1) = c(i+ii-1,j+3+jj-1) + t13 ; c(i+1+ii-1,j+3+jj-1) = c(i+1+ii-1,j+3+jj-1) + t14
             end do
           end do
         end do
       end do
     end do

まとめ

キャッシュ・ブロッキングは、データアクセスの再配置により、データのサブセット (ブロック) をキャッシュに読み込み、このブロックに対して操作を行うことで、メインメモリーから繰り返しデータをフェッチしなくても済むようにします。

上記の例のように、キャッシュを再利用するように手動でループのデータをブロッキングできます。パフォーマンス解析でメモリー帯域幅が制限されていることが判明し、-opt-report の出力からループが最適にブロッキングされていないことが明らかなパフォーマンス・クリティカルなループについては、データを効率良くブロッキングしてキャッシュの再利用を高めるため、手動によるループアンロールを検討してください。

次のステップ

この記事は、「Programming and Compiling for Intel® Many Integrated Core Architecture」(英語) の一部「Cache Blocking Techniques」の翻訳です。インテル® Xeon Phi™ コプロセッサー上にアプリケーションを移植し、チューニングを行うには、各リンクのトピックを参照してください。アプリケーションのパフォーマンスを最大限に引き出すために必要なステップを紹介しています。

インテル® MIC アーキテクチャーに対する準備に戻る

コンパイラーの最適化に関する詳細は、最適化に関する注意事項を参照してください。

関連記事