Critical Stride
CPU のキャッシュ構造
CPU のキャッシュは大抵、ラインとセットとで構成される。たとえば 2MiB のキャッシュ容量でラインのサイズが 64 B の CPU があるとする。このときこの CPU は
2MiB(2,097,152) / 64 = 32768
のラインをもつ。それらが8つごとに way を構成すると、セットの数は
32768 ライン / 8 way = 4096
になる。
CPU はこれらの任意の場所にデータをロードできるわけではない。ロードするデータのアドレスによってセットが選択され、そのセットのどのラインが使われるかは CPU 依存である。あるメモリアドレスのロード先のセットは以下の式で計算できる。
ロード先のセット番号 = (メモリアドレス / ラインサイズ) % セット数
読み込みたいメモリアドレスが 0x10000 だとすると、ロードされるセット番号は
(0x10000 / 0x40) % 0x1000 = 0x400
つまりメモリアドレス 0x10000 はセット番号 1024(0x400) のラインのどれかにロードされる。
Critical Stride
この例ではメモリアドレス 0x50000, 0x90000, 0xD0000, …も 0x10000 と同じセットにロードされる。この同じセットにロードされるメモリ間隔を Critical Stride と呼ぶ。Critical Stride は以下の式で計算できる。
Critical Stride = セット数 * ラインサイズ = キャッシュ全体のサイズ / way 数
Critical Stride の間隔でデータにアクセスすると、ごく少数のキャッシュしか使えない。そのためキャッシュミスが多発しパフォーマンスが低下する。これは巨大な構造体やメモリ内に散らばった関数の呼び出し時に問題になることがある。