同じ回数の足し算でも、データを読む順番で実行時間が変わることがあります。CPUが計算する速さと、大容量のメモリから値を運ぶ速さには差があるためです。キャッシュは、よく使うデータの一部をCPUに近い場所へ置き、この差を埋めます。
小さく速い場所を段階的に置く
一般的なCPUでは、レジスタ、L1・L2・L3などのキャッシュ、主記憶という階層を使います。容量、アクセス時間、共有範囲は機種によって違います。レジスタの値をどれにするかはコンパイラや命令が指定し、CPUキャッシュは通常ハードウェアが管理します。アプリが普段指定する配列のアドレスと、何段目にコピーがあるかは別の話です。
キャッシュが効く根拠は局所性です。同じ値を短い間隔で再び使う性質を時間的局所性、近いアドレスの値を続けて使う性質を空間的局所性と呼びます。ループの集計変数は前者、配列の順番の走査は後者を利用しやすい例です。
1要素でなくラインごと運ぶ
仮にキャッシュラインが64バイトで、整数が4バイトなら、連続した16要素が1ラインに入ります。先頭要素でミスしてラインを取り込めば、続く要素は同じラインから読める可能性があります。以下はアクセス順の違いだけを見るための例です。実測では最適化、プリフェッチ、配列の大きさなども影響します。
/* 連続した領域を読む */
for (size_t i = 0; i < n; ++i)
sum += a[i];
/* 16要素ごとに飛ぶ。総読取り数も異なる */
for (size_t i = 0; i < n; i += 16)
sum += a[i];後半は、各ラインから1要素だけ使って次へ進む例です。二つのコードは読取り数が違うので、そのまま時間だけを比べて優劣を決められません。1要素あたりの時間やキャッシュミス数を測ると、「運んだ64バイトのうち何バイトを利用したか」が見えます。
ヒット率の少しの差が待ちを増やす
目的のデータがあればヒット、なければミスです。単純な1段のモデルでは、平均アクセス時間＝ヒット時間＋ミス率×追加のミスペナルティと計算します。ヒット時間1ns、ミス率5％、追加待ち100nsなら6nsです。ミス率を1％に下げれば2nsになります。少数の遅いアクセスが平均を押し上げます。
実際のCPUは、複数のミスを並行して処理したり、計算と読取りを重ねたりします。この式をそのままプログラム全体の実行時間にはできません。何が待ち時間を決めているかを整理するモデルとして使います。
空きがあっても衝突する
キャッシュ全体の空きだけでは、データを置けるとは限りません。ダイレクトマップでは、各メモリブロックの置き場所が一つに決まります。違うブロックが同じ場所へ対応すると、交互に追い出し合うことがあります。セット連想方式では、同じセットの複数の場所から選べます。例えば4ウェイなら、そのセットに4ラインを置けます。
セットの全候補が埋まったときは、どれを捨てるかを置換方針で決めます。最も長く使われていないものを選ぶLRUや、その近似などがあります。連想度を上げると衝突を減らせる一方、比較回路などの費用が増えます。キャッシュ容量を増やす方法と、連想度を増やす方法は同じではありません。
書いた値はいつ下の階層へ届くか
ライトスルーは、キャッシュへの変更を下位階層にも伝えます。ライトバックは、変更したラインに印を付け、追い出すときなどにまとめて下位へ書き戻します。後者では、主記憶の内容が一時的に古くても、CPUから見える値はキャッシュ側の新しいものになります。
書込みミスのときにラインを取り込むかどうかは、書込みをいつ伝えるかとは別の方針です。また、CPUキャッシュの書戻しと、ファイルをSSDへ永続化する処理も別です。「メモリに書いた」ことだけで、電源を落としても値が残るとは言えません。
確かめてみよう
問1：同じ要素を何度も使うのは、どちらの局所性でしょうか。時間的局所性です。次の隣接要素を使うなら、空間的局所性です。
問2：ヒット時間2ns、ミス率2％、追加待ち80nsの平均アクセス時間はいくらでしょうか。2＋0.02×80＝3.6nsです。
複数コアやデバイスが同じメモリを使う場合は、割込み・I/O・DMA・マルチコアで扱います。