【応用情報技術者試験】キャッシュメモリ格納方式

キャッシュメモリの格納方式は、主記憶のブロックをキャッシュ内のどこに置けるかを決める仕組みです。直接マッピングは「1か所」、フルアソシアティブは「全体のどこでも」、セットアソシアティブは「決まったセットの中」と整理しましょう。

この記事では3方式の違いを、同じ4ラインのキャッシュを使って比較します。配置を理解した後は、末尾のnote教材でヒット率・実効アクセス時間の計算へ進めます。

3つの格納方式を比較

方式	置ける場所	確認するタグの範囲
直接マッピング	ブロック番号から決まる1ライン	その1ライン
フルアソシアティブ	キャッシュ内の全ラインが候補	全ライン
セットアソシアティブ	ブロック番号から決まるセット内の各ライン	そのセット内

主記憶とキャッシュの間では、まとまった単位でデータを扱います。ここでは主記憶側の単位を「ブロック」、キャッシュ内の格納枠を「ライン」と呼びます。タグは、そのラインにどの主記憶ブロックが入っているかを識別する情報です。

直接マッピング：格納先は1か所

標準的な例では、ライン番号＝主記憶のブロック番号 mod ライン数で格納先を求めます。modは割り算の余りです。キャッシュが4ラインなら、ブロック0・4・8はいずれもライン0に対応します。

ブロック0と4を交互に読むと、ほかのラインが空いていてもライン0で追い出し合います。このように配置制約が原因で起きるミスをコンフリクトミスと呼びます。格納先とタグの比較対象を絞れるため、回路を比較的単純にできる点が特徴です。

フルアソシアティブ：全ラインが候補

ブロック0も4も、4ラインのどこにでも置けます。直接マッピングのような格納先の衝突によるミスを避けられますが、容量不足による追い出しまでなくなるわけではありません。初めて読むブロックでもミスは起きます。

検索時には全ラインのタグが比較対象になります。これは「空き場所を順番に探すから必ず遅い」という意味ではありません。並列比較もできますが、比較回路の規模や消費電力などの負担が増えやすくなります。ヒット率やアクセス時間は、アクセス列・容量・置換方式・実装にも依存します。

セットアソシアティブ：決まったセットの中で選ぶ

4ラインを2セットに分け、各セットに2ラインを持たせたものが2ウェイ・セットアソシアティブです。標準的な例では、セット番号＝ブロック番号 mod セット数で決めます。

主記憶ブロック	直接マッピング（4ライン）	フルアソシアティブ（4ライン）	2ウェイ（2セット×2ライン）
0	ライン0	全4ラインから選択	セット0の2ラインから選択
4	ライン0	全4ラインから選択	セット0の2ラインから選択
1	ライン1	全4ラインから選択	セット1の2ラインから選択

ブロック0と4は同じセット0ですが、2ラインあるので同時に保持できます。さらにブロック8も必要になりセット0が満杯なら、そのセット内から追い出す対象を選びます。セット1が空いていても、ブロック8をそちらに置くことはできません。

配置・置換・書込みは別の話

観点	決めること	例
配置方式	どこに置けるか	直接／フル／セットアソシアティブ
置換方式	候補が満杯のとき、何を追い出すか	LRU、FIFOなど
書込み方式	更新を主記憶にいつ反映するか	ライトスルー、ライトバック

直接マッピングでは格納先が1ラインなので、同じ格納先の別ブロックを入れるときに追い出す候補を選ぶ余地はありません。セットアソシアティブではセット内、フルアソシアティブでは全体から置換対象を選びます。

確認問題：ブロック8はどこに入る？

4ラインのキャッシュを、2セット×2ラインの2ウェイ構成にします。セット番号はブロック番号 mod 2です。ブロック8を新たに読み、セット0は満杯、セット1は空いています。どのように格納しますか？

解答・解説を見る

セット0のラインを1つ置き換えます。8 mod 2＝0なので、格納できるのはセット0の中だけです。セット1の空きは利用できません。置換対象は採用している置換方式に従って選びます。

次はヒット率・実効アクセス時間の計算へ

配置方式を理解したら、「必要なデータがキャッシュにある確率」と「平均でどれだけ時間がかかるか」を学びましょう。こちらのnoteでは、キャッシュの役割からヒット率・ミス率、実効アクセス時間の計算、よくある間違いへと進めます。3方式の配置例は本記事で確認し、計算の学習にnoteを使うと整理しやすくなります。

キャッシュメモリのヒット率・実効アクセス時間をnoteで学ぶ

教材の公開範囲・価格はnoteの表示をご確認ください。ほかの分野も探す場合は、IT資格攻略chのnote一覧をご覧ください。

まとめ

直接マッピングは1ライン、フルアソシアティブは全ライン、セットアソシアティブは指定セット内が候補です。「どこに置くか」「何を追い出すか」「いつ主記憶に書くか」を分けて考えると、用語を取り違えにくくなります。

参考：Cornell University：Caches（英語）。本記事の4ラインの例と確認問題は学習用のオリジナルです。