【超分かりやすい】ダイレクトマッピング/フルアソシアティブ/セットアソシアティブ【新感覚Sutdy/応用情報】

2024.06.15 2024.06.14

はじめに

IT分野の技術者を目指す皆さん、こんにちは。今日は、コンピュータの高速化に欠かせない「キャッシュメモリ」の割付方式について詳しく解説していきます。キャッシュメモリは、CPUの処理速度を最大限に活かすための重要な要素であり、その割付方式を理解することは、応用情報技術者試験の合格にも直結します。この記事では、ダイレクトマッピング方式、フルアソシアティブ方式、セットアソシアティブ方式の3つの方式について、具体例を交えながらわかりやすく説明します。難解な用語も多いこの分野ですが、この記事を読み終える頃には、キャッシュメモリの割付方式がすっきりと理解できることでしょう。それでは、さっそく始めましょう。

【ここで扱う疑問】

キャッシュメモリってなに？

では、まずはキャッシュメモリってそもそもなんなのかを理解していきましょう！

キャッシュメモリは、CPUと主記憶装置（RAM）の間に位置する小容量・高速のメモリです。主記憶装置へのアクセス時間を短縮するために、よく使用されるデータや指令をキャッシュメモリに一時的に保存します。これにより、CPUの処理効率が向上し、システム全体のパフォーマンスが改善されます。

では、以下にキャッシュメモリがデータをどのように保存し、検索するかを示す方法（マッピング方式）を色々と紹介していきます！

ダイレクトマッピング方式ってなに？

ダイレクトマッピング方式（Direct Mapping）は、キャッシュメモリにデータを保存する方法の一つです。具体的には、メインメモリのデータがキャッシュの特定の位置にのみ保存されるようにする方法です。

メインメモリ

メインメモリ（Main Memory）とは、コンピュータシステムの中で、データやプログラムを一時的に保存するための高速な記憶装置です。一般的には、RAM（Random Access Memory、ランダムアクセスメモリ）と呼ばれています。

ブロック

コンピュータのメモリは大量のデータを管理していますが、これを効率よく扱うために、データを小さな単位に分けています。これを「ブロック」と呼びます。

メインメモリのデータがキャッシュメモリにコピーされるとき、そのデータは一つのブロック単位でキャッシュメモリに格納されます。

仕組みの説明

メモリアドレス: メインメモリの各データには固有のアドレス（番号）が付いています。このアドレスを使ってデータがどこにあるかを特定します。
アドレスの分割: メインメモリのアドレスをいくつかの部分に分けます。
- タグ（Tag）: どのデータなのかを示します。
- インデックス（Index）: キャッシュのどこにデータを置くかを決めます。
- オフセット（Offset）: データのブロック内の具体的な位置を示します。

例を使って説明します：

メインメモリが1024個のデータブロックに分かれているとします。
キャッシュメモリには16個のブロックがあります。

メインメモリのアドレスを10ビットで表します（1024 = 2^10なので10ビットが必要）。キャッシュメモリのインデックスは4ビットです（16 = 2^4なので4ビット）。

例えば、メインメモリのアドレスが「1010110010」だとします。

インデックス部分（真ん中の4ビット）は「1100」（つまり、12番目のキャッシュブロック）。
残りのビットはタグ部分で、データが何なのかを示します。

データの格納と取り出し

格納: 新しいデータをキャッシュに入れるとき、メインメモリのアドレスからインデックス(キャッシュのどこにデータを置くか)を取り出し、その位置にデータを保存します。
取り出し: データが必要になったとき、CPUはメインメモリのアドレスからインデックスを使ってキャッシュメモリの位置を特定します。そして、タグを使ってその位置に正しいデータがあるか確認します。

メリットとデメリット

メリット:
- 実装が簡単で、高速に動作します。
- メモリアドレスの一部だけを使ってアクセスするので、検索が速いです。
デメリット:
- 衝突（異なるメモリブロックが同じキャッシュブロックを使う）が発生しやすいです。例えば、メインメモリのアドレス「0000」と「0010」が両方ともキャッシュの同じ場所に保存される可能性があります。
- 衝突が多いと、キャッシュの効果が低下します。

衝突が発生したらどうなるの？

ダイレクトマッピング方式では、メインメモリの異なるアドレスが同じキャッシュブロックにマップされることがあります。これを「衝突（コンフリクト）」といいます。衝突が発生すると、新しいデータが既存のデータを上書きする必要があります。以下で詳しく説明します。

以下で、衝突が発生した時の対応方法を紹介していきます。

1. 上書き（書き換え）

ダイレクトマッピング方式では、衝突が発生した場合、基本的には新しいデータが既存のデータを上書きします。つまり、同じキャッシュブロックにマップされるメモリアドレスがアクセスされたとき、キャッシュブロックの内容は新しいデータに置き換えられます。

例を挙げて説明します：

メインメモリのアドレス「0000」と「1000」がキャッシュの同じブロックにマップされるとします。
まず、アドレス「0000」にアクセスし、そのデータがキャッシュに保存されます。
次に、アドレス「1000」にアクセスすると、キャッシュの同じブロックに新しいデータが保存されます。このとき、アドレス「0000」のデータは上書きされます。

2. キャッシュの一貫性

上書きが発生するとき、キャッシュメモリとメインメモリのデータの一貫性を保つために以下の方法が使われます：

ライトスルー方式: キャッシュに書き込まれたデータを同時にメインメモリにも書き込みます。これにより、キャッシュとメインメモリのデータの一貫性が保たれますが、メモリ書き込みの速度が遅くなることがあります。
ライトバック方式: キャッシュに書き込まれたデータをすぐにはメインメモリに書き込まず、キャッシュブロックが上書きされるときにだけメインメモリに書き込みます。これにより、メモリ書き込みの速度が向上しますが、キャッシュとメインメモリのデータの一貫性を保つのが少し複雑になります。

まとめ

ダイレクトマッピング方式では、衝突が発生した場合、新しいデータが既存のデータを上書きすることで対応します。このとき、キャッシュとメインメモリの一貫性を保つために、ライトスルー方式またはライトバック方式が使われます。ダイレクトマッピングは実装が簡単で高速ですが、衝突が発生しやすいため、効率を最大化するためには他のマッピング方式（例えば、セットアソシアティブ）も考慮する必要があります。

まとめ

ダイレクトマッピング方式は、キャッシュメモリの実装簡単にし、データのアクセスを高速化しますが、データの衝突が起こりやすいという問題もあります。この仕組みを理解することは、コンピュータがどのようにして効率的にデータを処理するかを理解する助けになります。

フルアソシアティブ方式ってなに？

フルアソシアティブ方式（Fully Associative Mapping）は、キャッシュメモリの中で最も柔軟なデータ配置方法です。キャッシュメモリ内のどの場所にもメインメモリの任意のデータを配置することができます。この方式では、キャッシュ内のどのブロックでも使用可能であるため、競合の問題が発生しません。

具体的な説明

データの配置:
- メインメモリのどのブロック（データの塊）でもキャッシュメモリのどのブロックにも保存できます。つまり、キャッシュメモリの全てのブロックが自由に使えます。
データの検索:
- データを探すとき、キャッシュの全てのブロックをチェックします。どのブロックにもデータが置かれている可能性があるからです。

例で理解する

キャッシュメモリが4ブロックあるとします。

メインメモリのアドレス「A」のデータをキャッシュメモリに置くとき、キャッシュのどのブロックに置いても構いません。
次にメインメモリのアドレス「B」のデータをキャッシュメモリに置くときも、空いているどのブロックにでも置けます。

これにより、データの配置に関して非常に柔軟になります。

メモリの構成とタグ

フルアソシアティブ方式では、メモリアドレスは以下のように構成されます：

タグ（Tag）: メモリのデータを一意に識別するための部分。キャッシュ内の各ブロックにデータがどこから来たのかを示します。
オフセット（Offset）: ブロック内の具体的な位置を示します（キャッシュブロックが大きい場合に使います）。

メリットとデメリット

メリット

柔軟性: データをキャッシュのどこにでも配置できるので、ダイレクトマッピング方式のような衝突が起きません。
キャッシュヒット率が高い: データの配置が自由なので、キャッシュメモリの利用効率が高くなり、キャッシュヒット率が向上します。

キャッシュヒット率

キャッシュヒット率は、CPUがアクセスしたデータがキャッシュメモリ内に存在する割合です。

フルアソシアティブ方式では、ダイレクトマッピングやセットアソシアティブ方式のような固定された配置規則がないため、衝突が起きにくい傾向があります。つまり、同じキャッシュブロックを競合して利用しようとするメモリアドレスが少ないです。

デメリット

検索の複雑さ: データを探すときにキャッシュの全てのブロックをチェックする必要があるため、検索が遅くなることがあります。
ハードウェアの複雑さ: 各ブロックを調べるためのハードウェアが複雑で高価です。

まとめ

フルアソシアティブ方式は、キャッシュメモリのどのブロックにもメインメモリのどのデータでも配置できる方法です。この方式は、データの配置に関して非常に柔軟で、キャッシュヒット率を高めることができますが、検索が複雑でハードウェアが高価になります。柔軟性と効率性を重視する場面で使われることが多いです。

セットアソシアティブ方式ってなに？

セットアソシアティブ方式（Set Associative Mapping）は、ダイレクトマッピング方式とフルアソシアティブ方式の中間的な方式です。この方式では、キャッシュメモリをいくつかのセットに分割し、それぞれのセットに複数のブロック（エントリ）を持たせます。そして、メモリアドレスを特定のセットにマッピングすることで、データの置き場所を決定します。

具体的な例で説明

例えば、キャッシュメモリが8セット、各セットに2つのブロックがあるとします。

セットの分割: キャッシュメモリを8つのセットに分けます。
ブロックの配置: 各セットに2つのブロックを配置します。

メモリアドレスとの関係

メモリアドレスは通常、以下の3つの部分から構成されます：タグ、セットインデックス、オフセット。

タグ: メモリブロックを一意に識別するための部分。
セットインデックス: メモリブロックがどのセットに属するかを示す部分。
オフセット: メモリブロック内の特定のデータの位置を示す部分。

セットアソシアティブの動作

データの配置: メモリアドレスがキャッシュにアクセスされると、そのメモリアドレスのセットインデックスを見て、対応するセットにデータを配置します。
データの検索: メモリアドレスに対応するデータを探すとき、まず対応するセット内のブロックを検索します。
- セット内の複数のブロック（エントリ）の中から、タグを比較して該当するデータを見つけます。