キャッシュメモリの割付方式（cache mapping）

分類: テクノロジ系コンピュータ構成要素
出る試験: 基本情報応用情報
重要度: ★★★☆☆

主記憶のデータをキャッシュのどこに置くかを決める方式。置き場所の自由度で3種類に分かれる。

もう少し詳しい説明

キャッシュメモリ（よく使うデータをCPUの近くに置いておく、小さくて速い入れ物）は、主記憶（いま使うプログラムとデータを置いておく記憶装置）よりはるかに小さい入れ物です。主記憶が8Gバイトあってキャッシュが8Mバイトなら、1000分の1しか入りません。

ということは、主記憶のどのデータをキャッシュのどこに置くかを決めるルールが必要になります。それが割付方式（マッピング方式）です。

このルールの作り方には、置き場所の自由度という1本の軸があります。自由度が高いほど無駄なく使えますが、探すのが大変になります。この引き換えが、3つの方式の違いそのものです。

前提：ブロック単位で動く

キャッシュは1バイト（ビット（0か1のどちらかを入れる1けた）を8個まとめた単位）ずつではなく、ブロック（ライン）という決まった大きさのかたまりでやり取りします。主記憶（プログラムとデータを置いておく記憶装置）も同じ大きさで区切られていて、ブロック番号が付いています。

まとめて運ぶのは、近くのデータは続けて使われることが多いからです。 1バイトだけ取りに行っても、次に必要になるのはたいてい隣のバイトです。それなら、まとめて持ってきたほうが往復の回数が減ります。

また、キャッシュの各行にはタグという札が付いています。「いま入っているのは主記憶のどのブロックか」を記録しておくもので、探すときはこのタグを見ます。

ダイレクトマップ方式

置き場所を1か所に決めてしまう方式です。ブロック番号をキャッシュの行数で割った余りが、入る行になります。

キャッシュが4行のときの対応です。ブロック番号を4で割った余りが、入る行になります。色を付けた2つを見てください。ブロック0とブロック4は、どちらも行0しか使えません。

長所は、探すのが速いこと。 ブロック5を探したいなら「5 ÷ 4 の余りは1だから、1行目だけ見ればよい」で済みます。比較するタグは1つだけなので、回路も小さく、消費電力も少なくて済みます。

短所は、ぶつかること。 実際に主記憶とキャッシュを並べて、データがどこへ入るのかを見てください。

キャッシュは4行しかないので、ブロック番号を4で割った余りが入る行になります。ブロック0のデータ1は行0へ。ブロック4のデータ5も余りが0なので、行0にしか入れません。行1・2・3が空いていても使えないため、データ1とデータ5を交互に読むと毎回相手を追い出し合います。

ブロック0とブロック4は、どちらも0行目しか使えません。この2つを交互に読むと、毎回相手を追い出し合って、キャッシュがあるのに毎回ミスします。0行目以外が空っぽでも、そこは使えません。 置き場所が1か所に決まっている、というのはそういうことです。

机の引き出しが4段あって、「書類の番号を4で割った余りの段にしか入れてはいけない」という決まりがある状態です。探すのは楽ですが、同じ段を使う書類が2つあると、片方を出すたびにもう片方をしまうことになります。

フルアソシアティブ方式

どこへでも置ける方式です。空いている行があれば、そこに入れます。

長所は、無駄がないこと。 置き場所の制約でぶつかることがないので、キャッシュを使い切れます。

短所は、探すのが大変なこと。 「このブロックはどこにあるか」が分からないので、全部の行のタグを一度に比べる必要があります。行数が多いほど比較回路が大きくなり、消費電力も増えます。

そのため、行数の多いキャッシュでは現実的ではありません。小さな専用キャッシュなどに限られます。

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

上の2つの中間です。キャッシュの行をいくつかのセットにまとめ、

ブロック番号からどのセットに入れるかを一意に決める（ダイレクトマップのやり方）
そのセットの中ではどこに置いてもよい（フルアソシアティブのやり方）

という二段構えにします。1セットに何行入るかをウェイと呼び、2ウェイ・4ウェイ・8ウェイなどがあります。

4行のキャッシュを2ウェイにすると、セットは2つ（各2行）になります。ブロック0とブロック4は同じセットに入りますが、セットの中に2行あるので、両方同時に置けます。ダイレクトマップのぶつかり方が緩和されます。

探すときは、セットを1つに絞ってから、その中の2つ（2ウェイなら）のタグだけを比べます。全部を比べるフルアソシアティブより、回路がはるかに小さくて済みます。

実際のプロセッサは、ほとんどがこの方式です。 両方の欠点を現実的な範囲で削れるからです。

3つの比較

方式	置き場所	タグの比較	ぶつかりやすさ	回路
ダイレクトマップ	1か所に固定	1つだけ	ぶつかりやすい	小さい・速い
フルアソシアティブ	どこでもよい	全部	ぶつからない	大きい
セットアソシアティブ	セット内は自由	セット内だけ	少ない	中くらい

ダイレクトマップは1ウェイのセットアソシアティブ、フルアソシアティブは全行が1セットのセットアソシアティブとみなせます。つまり3つは別物ではなく、ウェイ数を1から全行まで動かした両端と中間です。この見方ができると、丸暗記せずに並びが出てきます。

追い出すものを選ぶ

置き場所が自由な方式（フルアソシアティブ、セットアソシアティブ）では、空きがないときにどれを追い出すかを決める必要があります。これを置換アルゴリズムと呼びます。

LRU（Least Recently Used。最後に使われたのがいちばん昔のもの）… 最後に使われてから一番長いものを追い出す。もっともよく使われる
FIFO（First In First Out。先に入れたものを先に出す）… 先に入ったものから追い出す
LFU（Least Frequently Used。使われた回数がいちばん少ないもの）… 使われた回数が一番少ないものを追い出す

LRUが選ばれるのは、「しばらく使っていないものは、この先も使われにくい」からです。 先に入れたかどうか（FIFO）より、最後に使った時期のほうが、次に使うかどうかの見当が付きます。

ダイレクトマップには置換の選択がありません。 置き場所が1か所しかないので、そこにあるものを追い出すしかないからです。ここも区別して覚えておくとよい点です。

試験ではこう出る

科目A（旧・午前）では、3方式の説明文を読んでどれかを選ばせる問題が定番です。手掛かりは次のとおりです。

「置き場所が一意に決まる」「余りで決まる」→ ダイレクトマップ
「どこにでも置ける」「すべてのタグを比較する」→ フルアソシアティブ
「セット内の任意の場所」「ウェイ」→ セットアソシアティブ

「全部のタグを比べる」が出てきたらフルアソシアティブ、と1つ覚えておくと、残り2つの区別も付けやすくなります。

計算問題としては、ブロック番号から入る行を求める形が出ます。行数で割った余りです。商と間違えやすいので注意してください。

応用情報では、ウェイ数を変えたときのぶつかりやすさや、置換アルゴリズム（とくにLRU）の動きまで問われます。

ミニクイズ

4行のキャッシュメモリを持つシステムで、ダイレクトマップ方式を用いている。主記憶のブロック番号13のデータは、キャッシュの何行目（0から数える）に割り付けられるか。

正解は 1番：1行目

ダイレクトマップ方式では、ブロック番号をキャッシュの行数で割った余りが置き場所になります。13 ÷ 4 ＝ 3 余り 1 なので、1行目です。3行目は余りではなく商を答えた値、13行目はブロック番号そのまま、0行目は割り切れると勘違いした値です。「行数で割った余り」と覚えてください。

間違えた用語の復習リストを見る →

この分野をまとめて解く → コンピュータ構成要素とハードウェアのミニテスト（全33問）

最終更新：2026-10-12