LoginSignup
9
9

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@SamN

キャッシュライン衝突するかどうか試してみた

Last updated at Posted at 2021-05-29

はじめに

2のべき乗サイズの配列を使った計算をすると「キャッシュライン衝突」というものが発生して処理速度に大きな影響を及ぼす場合がある、ということを以下の記事で知りました。

qlazyという量子計算のシミュレータを趣味で作っていますが、もしそういうことが裏で発生しているのだとすると大変です。量子計算においては2のべき乗サイズの配列は頻繁に扱います。というか、そういう配列しか扱わない、といっても過言ではありません。実装の工夫でこの問題を何とか回避できるのであれば、qlazyでもそうしておきたいところです。他にも世の中には沢山の量子計算を行うシミュレータがありますが、実は内部でバキバキとキャッシュライン衝突していて、本来のパフォーマンスが得られていない可能性があるのでは、、という疑念がふつふつと湧き上がってきます。

で、「キャッシュライン衝突」でぐぐってみると、

というような講義資料がヒットして、中身を見ると計算機科学に関するややこしい話がやさしく解説されています。キャッシュライン衝突が発生した場合の対策についても、以下のようにいくつか紹介されています。

  • パティング法：配列に（2冪でない）余分な領域を確保し確保配列の一部領域を使う。
  • データ圧縮法：計算に必要なデータのみキャシュライン衝突しないようにデータを確保し、かつ、必要なデータをコピーする。
  • 予測計算法：キャッシュライン衝突が起こる回数を予測するルーチンを埋め込み、そのルーチンを配列確保時に呼ぶ。

おっしゃわかった！（ホントはわかってないけど、、）じゃあ早速そのような対策を実装すっべ！！パティング法が簡単そうだな、ふむふむ、、とか言う前に、ちょっと待ってください。まずは、「2のべき乗サイズの配列は危ない...」で示されているようなことが、果たして本当に発生するのかを試してみてからでしょ、、ということで、実際に自分の環境でやってみました。

実施内容

今回実行してみたC言語のソースコードを示します。

cache_line_test.c
# include <stdio.h>
# include <stdlib.h>
# include <time.h>

double matrix_product(int N)
{
  /* 時間計測関連の変数 */
  int			sec, nsec;
  double		d_sec;
  struct timespec	start_time, end_time;

  /* メモリ確保 */
  int**   A = (int**)malloc(sizeof(int*) * N);
  int**   B = (int**)malloc(sizeof(int*) * N);
  int**   C = (int**)malloc(sizeof(int*) * N);

  int* arr_A = (int*)malloc(sizeof(int) * N * N);
  int* arr_B = (int*)malloc(sizeof(int) * N * N);
  int* arr_C = (int*)malloc(sizeof(int) * N * N);

  for (int i=0; i<N; i++) {
    A[i] = arr_A + i * N;
    B[i] = arr_B + i * N;
    C[i] = arr_C + i * N;
  }

  /* ランダム値(0-9)をセット */
  for (int i=0; i<N; i++) {
    for (int j=0; j<N; j++) {
      A[i][j] = rand() % 10;
      B[i][j] = rand() % 10;
      C[i][j] = 0;
    }
  }

  /* 時間計測（開始） */
  clock_gettime(CLOCK_REALTIME, &start_time);

  /* 行列積の計算実行 */
  for (int i=0; i<N; i++) {
    for (int j=0; j<N; j++) {
      for (int k=0; k<N; k++) {
        C[i][j] += A[i][k] * B[k][j];
      }
    }
  }

  /* 時間計測（修了） */
  clock_gettime(CLOCK_REALTIME, &end_time);

  /* 処理時間の計算 */
  sec	= end_time.tv_sec - start_time.tv_sec;
  nsec	= end_time.tv_nsec - start_time.tv_nsec;
  d_sec = (double)sec + (double)nsec / (1000 * 1000 * 1000);

  /* メモリ解放 */
  free(arr_A); free(arr_B); free(arr_C);
  free(A); free(B); free(C);

  return d_sec;
}

int main(void)
{
  int N_start = 1023;
  int N_end   = 1025;
  
  for (int N=N_start; N<=N_end; N++) {
    printf("N = %d, time = %f sec\n", N, matrix_product(N));
  }

  return 0;
}

2次元のメモリをmallocで確保して1、ランダム値を代入して、"C = AB"という行列積の計算を実行し、時間を計測しているだけです2。計測しているのは、前後の処理を除いた行列積計算の部分のみです。

上のコードを、

$ gcc cache_line_test.c
$ ./a.out

のようにgccでコンパイルして実行すると、

N = 1023, time = 11.907090 sec
N = 1024, time = 23.112193 sec
N = 1025, time = 12.297025 sec

という結果が得られました（おー、ほんとに遅くなってる！）。確かに、N=1024で3倍まではいかないですが、2倍程度遅くなっています。きっとキャッシュライン衝突しているのでしょう。何度やってもだいたい同じような結果でした。

次に、コンパイラの最適化オプションを使ってみます。gccでコンパイルする場合、大抵-O2とかの最適化オプションはつけますよね。で、やってみます。

$ gcc -O2 cache_line_test.c
$ ./a.out

とすると、結果は、

N = 1023, time = 9.100057 sec
N = 1024, time = 9.451575 sec
N = 1025, time = 9.207177 sec

となり、全体的に速くなるのはこれは最適化の効果です が、注目ポイントは、N=1024が他と比べて全く遅くなってないという事実です（なんと！） 。N=1024については2倍を超えるような遅さではないですが、少し遅くなっているようです。こちらも何度やっても同じような結果でした。

N=2047,2048,2049でも試しました。結果は、

$ gcc -O2 cache_line_test.c
$ ./a.out
N = 2047, time = 78.629614 sec
N = 2048, time = 88.006342 sec
N = 2049, time = 79.079479 sec

となり、 N=2048で処理時間が目立って大きくなるということはありませんでした（若干大きいですが、2倍とか3倍とかいうレベルではない）。 N=1024の場合と同様、N=2048で少し遅くなっています（N=1024の場合よりも遅さが目立つ）。何度も実行してきちんと検定すれば、はっきりした結果がわかると思います。

つまり、どういうことかというと、gccの最適化オプションを使うとキャッシュライン衝突が起きない、または緩和されるみたいです。上で引用させていただいた第1回 プログラム高速化の基礎の「パティング法」の説明の箇所にも、実は処方箋のひとつとして「コンパイラのオプションを使う」という方法が書いてあります。gccの場合は最適化の-O2オプションを使えば良いということなのだと思います（たぶん）。

ということで、遅くなってはいるものの2倍を超えるような派手な遅さではないため、コンパイラの最適化でキャッシュライン衝突が解消されると思ってしまいましたが、どうもそんな簡単な話ではなさそうです。コメント欄でご指摘いただいているように（@fujitanozomuさん、@tenmyoさん、ありがとうございます！）、ハードウェアのスペックによって計算時間が速くなる場合、ならない場合があります。また、キャッシュプロファイラ（cachegrind）で調査した結果、キャッシュミスがO2最適で特に削減されているわけではないようです。たまたま、私の環境ではO2最適化を使うと、2のべき乗サイズでの遅さが解消されたので、単純にキャッシュライン衝突が緩和されていると思ってしまいました。

動作環境

ちなみに、今回、どんな環境で試したかを一応記載しておきます。

  • PC: ThinkPad X230 3
  • CPU: Intel Core i5-3320M CPU @ 2.60GHz
  • Memory: 16GB
  • Storage(SSD): 256GB
  • OS: Linux - Ubuntu 20.04

その他、特にキャッシュ系の環境がどうなっているかが気になります。getconfコマンドでそのあたりの情報が見れるみたいなのでやってみます。ズラズラ表示されますがキャッシュっぽいところだけ抜き出してみると、

$ getconf -a
...
GNU_LIBC_VERSION                   glibc 2.31
GNU_LIBPTHREAD_VERSION             NPTL 2.31
POSIX2_SYMLINKS                    1
LEVEL1_ICACHE_SIZE                 32768
LEVEL1_ICACHE_ASSOC                8
LEVEL1_ICACHE_LINESIZE             64
LEVEL1_DCACHE_SIZE                 32768
LEVEL1_DCACHE_ASSOC                8
LEVEL1_DCACHE_LINESIZE             64
LEVEL2_CACHE_SIZE                  262144
LEVEL2_CACHE_ASSOC                 8
LEVEL2_CACHE_LINESIZE              64
LEVEL3_CACHE_SIZE                  3145728
LEVEL3_CACHE_ASSOC                 12
LEVEL3_CACHE_LINESIZE              64
LEVEL4_CACHE_SIZE                  0
LEVEL4_CACHE_ASSOC                 0
LEVEL4_CACHE_LINESIZE              0
...

となっていました。

gccのバージョンは、

$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

です。

おわりに

結局、コンパイラの最適化オプションを使えば、キャシュライン衝突をうまい具合に回避してくれるみたいです。ただ、本当にパティング法のような対策がコンパイラ内部でなされているのかどうかは全くわかりません。gccのドキュメントを精読すれば、もしかしたらわかるのかもしれませんが、、。

ということで、2のべき乗の配列を使わないようにする対応を自作プログラムでやるかどうかについては、 とりあえずやめておきます。引き続きコンパイラの最適化オプションのお世話になります。 もう少し良く考えてみる必要がありそうです。というのが今回の結論です。

以上、もしかするとトンデモナイ勘違いをしている可能性もあるので、何かお気づきの点があれば、コメントいただけるとありがたいです。

訂正（2021.05.31）

ソースコードの3重ループの中身がC[i][j]=A[i][k]*B[k][j]となっており行列積計算になっていませんでした（お恥ずかしいミス）。Cの要素をすべて0に明示的に初期化した上で3重ループの中身をC[i][j]+=A[i][k]*B[k][j]に変更し、併せて処理時間の結果も修正しました。

訂正（2021.06.05）

gccのO2最適化によって単純にキャッシュライン衝突が回避・緩和されたわけではない、という記述に修正しました。

訂正（2021.06.08）

O2最適化の結果を示した箇所で、2のべき乗サイズで処理時間が全く遅くなっていないという記載が言い過ぎだったため、2倍を超える遅さではないものの少し遅くなっている、という記載に変更。

  1. なにやら難しそうなことをやっている感じかもしれませんが、連続したメモリ領域に行列要素を格納するためにサイズN*Nのarr_A,arr_B,arr_Cという1次元配列を確保しています。 ↩

  2. ナノ秒単位での計算時間を取得するため、clock_gettime関数を使いました。【C言語】時間計測に用いるtime関数とclock関数の違いは？を参考にさせていただきました。 ↩

  3. 中古で入手した往年の名機ThinPad X230にメモリとストレージとバッテリーを換装して現代風に蘇った？マシンを開発用に使っています。 ↩

9
9
10

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
9
9

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?