キャッシュ
よく使うデータを CPU の近くに置いて、メモリの遅さを隠す。
主記憶は レジスタの 200 倍以上遅い。キャッシュが無ければ CPU は待ってばかりになる。
局所性#
キャッシュが機能するのは、プログラムに規則性があるから。
| 局所性 | 内容 |
|---|---|
| 時間的局所性 | 一度使ったものはまた使われる（ループ変数） |
| 空間的局所性 | 近いアドレスも使われる（配列の走査） |
空間的局所性を利用するため、 キャッシュは 64 バイト単位（キャッシュライン）で転送する。 1 バイト読むだけでも 64 バイト読み込む。
構造#
| 方式 | 内容 |
|---|---|
| ダイレクトマップ | アドレスから置き場所が一意に決まる。衝突しやすい |
| フルアソシアティブ | どこにでも置ける。検索が高価 |
| セットアソシアティブ | 中間。8〜16 way が一般的 |
性能への影響#
// 行優先で走査 — 空間的局所性が効く
for (i) for (j) sum += a[i][j];
// 列優先 — 毎回別のキャッシュラインを触る
for (j) for (i) sum += a[i][j];同じ計算量でも、10 倍以上の差がつくことがある。 行列積のブロック化（タイリング）が効くのも同じ理由で、 BLAS の高速化の中核にある。
偽共有#
異なるスレッドが同じキャッシュライン上の別々の変数を 書き換えると、ラインの所有権が行き来して激しく遅くなる。
論理的には競合していないのに性能が落ちるため、 原因が分かりにくい。 並列プログラムで注意を要する。
参考文献#
- Randal E. Bryant, David R. O’Hallaron. Computer Systems: A Programmer’s Perspective, 3rd ed. Pearson, 2016. https://csapp.cs.cmu.edu/
- John L. Hennessy, David A. Patterson. Computer Architecture: A Quantitative Approach, 6th ed. Morgan Kaufmann, 2017.
- Ulrich Drepper. What Every Programmer Should Know About Memory. 2007. https://people.freebsd.org/~lstewart/articles/cpumemory.pdf