dskjal
広告
広告

Critical Stride

カテゴリ:others

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

外部リンク

2のべき乗サイズの配列は危ないという話 via 行列積


広告
広告

カテゴリ