ダイレクトマップ・セットアソシアティブ・フルアソシアティブの違い：キャッシュの方式を比較
キャッシュは、メモリの各ブロックをどこに置いてよいかを決めなければなりません。ダイレクトマップのキャッシュでは、各ブロックを置けるラインが1つだけで、単純で速いのですが、2つのブロックが同じラインを取り合うと競合が起きます。フルアソシアティブのキャッシュでは、ブロックをどこにでも置けて競合はなくなりますが、すべてのラインとの比較が必要です。セットアソシアティブは、その折衷で、1つのセットの中のいくつかのウェイのどれかに置けます。ほとんどのCPUのキャッシュは、セットアソシアティブです。
| 項目 | ダイレクトマップ | セットアソシアティブ | フルアソシアティブ |
|---|---|---|---|
| ブロックを置ける場所 | インデックスのビットで決まる1つのライン | 1つのセットの中のウェイ(たとえば4つや8つ)のどれか | キャッシュ内のどのライン |
| 1回のアクセスでのタグ比較 | 1回 | ウェイごとに1回(たとえば8回) | すべてのラインを並列に |
| ヒット時間 | 最も速い | やや遅い | 最も遅い |
| ハードウェアのコストと電力 | 最も小さい | 中程度 | 最も大きい。ラインごとに比較器が必要 |
| 競合ミス | 最も多い | ウェイ数が増えると減る | なし。残るのは初期ミスと容量ミスだけ |
| 置き換えの方針 | 不要。選択肢が1つ | セットの中で選ぶ(LRUやその近似) | すべてのラインの中から選ぶ |
| 主な用途 | 小さく単純なキャッシュ、一部のマイコン | ほとんどのCPUのL1、L2、L3キャッシュ。多くは4〜16ウェイ | TLBやビクティムキャッシュなど、小さな構造 |
数値は代表的な目安で、世代や製品によって異なります。