セットアソシアティブ方式（set associative）

📌

セットアソシアティブ方式とは

セットアソシアティブ方式とは、キャッシュをいくつかのセット（組）に分け、アドレスからセットだけを1つに決め、そのセットの中なら任意の位置（ウェイ）に置けるキャッシュ配置方式のことです。1セットに置き場所がN個あるとき「N-way（Nウェイ）セットアソシアティブ」と呼びます。

ダイレクトマップが「1つの行に固定」だったのに対し、セットアソシアティブは「1つのセットに固定、ただしセット内は自由」です。これにより、同じセットに割り当てられたブロックでも、ウェイ数の分だけ共存できるようになります。上のツールで▶ボタンを押すと、同じセットに2つのブロックがぶつからずに共存する様子を確認できます。

身近な例で言うと、学年ごとに区切られた駐輪場のようなものです。「1年生はこのエリア（セット）」と区画は決まっていますが、そのエリアの中なら空いている好きな枠に停められます。1人専用の枠（ダイレクトマップ）より融通が利き、ぶつかりにくくなります。

🗂️

セットの考え方

位置決めは2段階で進みます。まずアドレスのインデックス部でセットを1つに絞り、つぎにそのセットの中で空きウェイを探す、という流れです。

動作の手順を整理すると次のとおりです。
・セットを選ぶ：アドレスのインデックス部でセットを1つに決める
・セット内を検索：そのセットのウェイすべてのタグを並べて比較する
・ヒット/ミス判定：一致するタグがあればヒット、なければミス
・格納：ミスなら、空きウェイに入れる（空きがなければ後述の置換で1つ追い出す）

例: 2セット × 2-way（合計4行）
─────────────────────
アドレス 001000 → セット0 のウェイ0 へ
アドレス 011000 → セット0 のウェイ1 へ（共存）
→ 同じセットでも2ブロック保持できる

検索はセット内のウェイだけが対象なので、2-wayなら2つ、4-wayなら4つを比較するだけで済みます。フルアソシアティブのように全行を探す必要がないため、検索コストを抑えつつ衝突を減らせる、バランスのよい方式です。ウェイ数を増やすほど衝突に強くなりますが、その分検索の手間が増えます。

セットが満杯のときは、どのウェイを追い出すかを決める置換アルゴリズム（LRU など、最も長く使われていないものを追い出す方式）が必要になります。ダイレクトマップは行が1つなので追い出す相手に迷いませんが、セットアソシアティブでは複数ウェイから1つを選ぶ判断が加わります。

⚖️

他方式との比較

セットアソシアティブは、ダイレクトマップとフルアソシアティブのちょうど中間に位置づけられます。両端の方式と並べると性質がよく分かります。

実は、セットアソシアティブは両端の方式を含む一般形と見ることができます。
・1-way セットアソシアティブ＝各セットにウェイが1つ＝ダイレクトマップと同じ
・1セットだけ（全体が1つのセット）＝どこにでも置ける＝フルアソシアティブと同じ

そのため、実際の CPU では 2-way や 4-way、8-way といったセットアソシアティブが広く使われています。衝突の少なさと検索コストのバランスが取りやすく、ダイレクトマップの速さとフルアソシアティブの柔軟さのいいとこ取りができるためです。

📌

なぜセットアソシアティブがバランスよいのか

結論：「検索対象を絞れる（速い）」と「衝突しにくい（柔軟）」の両方を、同時に実現できるからです。ダイレクトマップは速いけれど衝突しやすく、フルアソシアティブ（＝全キャッシュ行のどこにでも置ける方式）は衝突しにくいけれど回路が複雑で高コストになります。

セットアソシアティブがこの中間に来る理由を整理すると次のとおりです。
・検索を絞れる（ダイレクトマップの速さを引き継ぐ）：セットを1つに絞るので、全行を探す必要がない。2-wayなら2つだけ比較すれば済む
・同じセット内に複数置ける（フルアソシアティブの柔軟さを引き継ぐ）：インデックスが同じブロックでも、ウェイ数の分だけ共存でき、衝突の頻度が大幅に減る

身近な例で言うと、「1年生はA棟・2年生はB棟」と建物は決まっているが、建物の中は好きな席に座れる学校のようなものです。全校で好きな席（フルアソシアティブ）は自由だけど席を探すのに全校を歩き回る必要があります。1人専用の机（ダイレクトマップ）は探しやすいけれど被ると困ります。棟で絞ってから中で選ぶ（セットアソシアティブ）が、探しやすさと自由さを両立しています。

📌

3つの方式の違いをひとことで整理する

3つのキャッシュ配置方式（＝キャッシュのどこに置くかを決めるルール）をひとことで区別すると次のようになります。
・ダイレクトマップ：「この番地のブロックはこの行に入れる」と1対1で固定。速いが衝突しやすい
・セットアソシアティブ：「この番地はこのセット（組）の中なら自由」。速さと衝突しにくさを両立
・フルアソシアティブ：「キャッシュのどの行にでも入れてよい」。最も衝突しにくいが回路が複雑で高コスト

なぜ実際のCPUではセットアソシアティブが主流なのか。フルアソシアティブは「全行から空き行を探す」ための回路が大きくなりすぎ、チップに収めるのが難しく消費電力も大きくなります。ダイレクトマップは回路は小さくても、特定のアクセスパターンでヒット率が大幅に落ちることがあります。2-way や 4-way のセットアソシアティブは、現実的なコストで衝突を大幅に減らせるため、スマートフォンからパソコンまで幅広いCPUで採用されています。

整理すると、3方式は「置ける自由度」を軸に並んでいます。自由度が増すほど衝突は減るが、その分だけ「どこにあるか」を探す手間も増えるというトレードオフです。セットアソシアティブはこのトレードオフをウェイ数で調整できるため、用途に合わせて柔軟に設計できる方式です。