Critical Stride

カテゴリ:programming

CPU のキャッシュ構造

CPU のキャッシュは大抵,ラインとセットとで構成される. たとえば 2MByte のキャッシュ容量でラインのサイズが 64 Byte の CPU があるとする; このときこの CPU は

2M(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 の間隔でデータにアクセスすると,ごく少数のキャッシュしか使えない. そのためキャッシュミスが多発しパフォーマンスが低下する. これは巨大な構造体やメモリ内に散らばった関数の呼び出し時に問題になることがある.