キャッシュはCPU近くの小さく高速な記憶です。インデックスで集合、タグでブロック、オフセットでバイトを選びます。
配置とヒット・ミスのシミュレータ
1. 方式とアクセス列（4枠、4バイト、8ビット）
アクセス順
同じ入力で方式を比べてください。衝突する2アドレスは直接マップで、5ブロック循環は4枠のLRUでもミスを繰り返します。
オフセットブロック内の位置
インデックス集合を選択
タグブロックを識別
平均アクセス時間ヒット時間＋ミス率×ペナルティ
アドレスを3つに分ける
4バイトなら下位2ビットがオフセットです。その上の一部が集合インデックス、残りがタグです。総枠数一定でウェイ数を増やすとインデックスが減り、タグが増えます。
3つの配置方式
直接マップは各ブロックの置き場所が1か所です。同じ場所を使うブロックは互いに追い出します。 全相連はどの枠でも使えますが、タグ比較の回路が増えます。多くのCPUは中間の 集合相連方式を使います。
局所性とコード
最近使った値を再利用する時間的局所性と、近いアドレスを使う空間的局所性が重要です。行優先の配列を a[i][j] 順に走査すると連続アクセスになり、 a[j][i] 順では離れた場所へ飛びます。配列が連結構造よりキャッシュに有利な理由の1つです。