CPUキャッシュによるプログラム高速化の例

CPUのキャッシュメモリを使うで、プログラムの実行性能をあげることができます。このエントリでは、キャッシュメモリを活用することでどの程度性能が向上するのか見てみます。

動機

コンピュータの記憶領域は、レジスタ、キャッシュメモリ、メインメモリなどからなる階層構造になっています。レジスタやキャッシュメモリはメインメモリより容量が小さいものの、非常に高速です。

CPUが直接触れるのはレジスタのみです。レジスタとメインメモリでは、データアクセスの速度に約100倍の差があり、その差を埋める目的で、CPU内部にキャッシュメモリがあります。キャッシュメモリを活用できれば、プログラムの実装性能を大きく高めることができます。

ただし、基本的に、CPUがどのようにキャッシュメモリを使うのかをプログラマが直接指示することはできません。なので、キャッシュメモリを活用するには、CPUがどのようにメモリ上のデータを使うのかを考慮したプログラムを書くことで間接的にキャッシュメモリを使うことになります。

※理化学研究所の京で使われているSPARC64 VIIIfxにはセクタキャッシュという機構があり、プログラマがキャッシュを制御できます。セクタキャッシュを使うと、キャッシュメモリを２つの領域に分割し、データごとにキャッシュに使う領域をプログラマが指定できます。

このエントリでは、キャッシュメモリを活用することで、実際にどの程度性能が向上するのか、一例を見てみます。

サンプルコード

1000×1000行列の積を求めるプログラムについて、キャッシュブロック化によって実行性能を最適化します。

以下が、最適化前のCのコードです。(code1.c)

#include <stdio.h>
#include <stdlib.h>
 
#define N 1000
 
int main ()
{
  double A[N][N], B[N][N], C[N][N];
  int i, j, k;
  
  // initialize the matrices
  for ( i = 0; i < N; i++ )
    for ( j = 0; j < N; j++ )
      {
        A[i][j] = 1.0;
        B[i][j] = 1.0;
        C[i][j] = 0.0;
      }
  
  // matrix multiplication
  for ( i = 0; i < N; i++ )
    for ( j = 0; j < N; j++ )
      for (k = 0; k < N; k++ )
        C[i][j] += A[i][k] * B[k][j];
  
  printf ( "%f\n", C[0][0] );
  
  return 0;
}

これを、キャッシュブロック化によって以下のコードに書き換えます(code2.c)。もちろん、計算の結果そのものは変わりません。

$ cat code2.c
#include <stdio.h>
#include <stdlib.h>
 
#define N 1000
 
int main ()
{
  double A[N][N], B[N][N], C[N][N];
  int i, j, k;
  
  // initialize the matrices
  for ( i = 0; i < N; i++ )
    for ( j = 0; j < N; j++ )
      {
        A[i][j] = 1.0;
        B[i][j] = 1.0;
        C[i][j] = 0.0;
      }
  
  // matrix multiplication
  int ibl = 100;
  int ib, jb, kb;
  for (ib=0; ib<N; ib+=ibl)
    for (jb=0; jb<N; jb+=ibl)
      for (kb=0; kb<N; kb+=ibl)
        for (i=ib; i<ib+ibl; i++)
          for (j=jb; j<jb+ibl; j++)
            for (k=kb; k<kb+ibl; k++)
              C[i][j] += A[i][k] * B[k][j];
  
  printf ( "%f\n", C[0][0] );
  
  return 0;
}

実行

最適化前、最適化後それぞれについて、実行にかかる時間は以下のようになりました。

$ gcc -Wl,-stack_size,1000000000 -O2 -o code1 code1.c
$ time ./code1 > /dev/null

real    0m7.595s
user    0m7.494s
sys     0m0.035s

$ gcc -Wl,-stack_size,1000000000 -O2 -o code2 code2.c
$ time ./code2 > /dev/null

real    0m2.509s
user    0m2.462s
sys     0m0.030s

※大きな配列をスタック上に確保するために、ldにオプションを渡してスタックサイズを大きくしています

グラフにすると以下のようになります。



キャッシュブロック化によって、約３倍の性能向上が得られました。

ブロックサイズによる性能比較

次に、ブロック化のサイズによって性能がどのように変わるかを調べてみます。ブロック化のサイズを100、200、250、500に変えて、実行時間を計ると、以下のようになりました。

100 : 2.311s
200 : 2.390s
250 : 2.509s
500 : 6.588s

※ブロック化のサイズの単位は、配列の要素数です。バイト数に直すと、double型の配列なので8を掛けたものになります

グラフにすると、以下のようになります。


ブロック化のサイズが500になると、急激に性能が悪化しています。このことから、ブロック化のサイズが大きくなりキャッシュにデータが収まらなくなった様子が分かります。

500×500のブロックのデータ量が2MBなので、このプログラム以外が動いていることも勘案すると、使っている環境のCPUの持つキャッシュメモリサイズと一致した結果といえます。


--