データ格納構造
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/11/05 14:09 UTC 版)
キャッシュメモリはデータをライン(ブロック)と呼ぶある程度まとまった単位で管理する(例えばIntel Pentium4の8kByte L1キャッシュはラインサイズ64Byte)が、データのアクセス要求があった時にそのデータがキャッシュに存在しているか、あるならどのラインかなどを瞬時(多くの場合1サイクルのスループット)に検索する必要がある。そのためデータ格納アドレスの一部、具体的にはライン単位アドレスの下位数ビット(エントリアドレス)によりある程度の格納位置を限定することで検索速度を高める。各ラインにはライン単位アドレスの上位ビット、即ちフレームアドレスを格納しておき、キャッシュ検索時には検索アドレスのフレームアドレス部と、キャッシュ内に格納されている検索エントリアドレス位置（エントリアドレス部をデコードしラインが1つ選択される）に対応したフレームアドレスとを比較することでキャッシュのヒットを検出する。このフレームアドレス格納バッファが（図中）タグである。複数セットのタグを持てば同じエントリアドレスでも複数データの格納を行うことが可能となる。このタグのセット数(ウエイ)を連想度と呼ぶ。データ格納構造の相違は連想度の相違でもある。 ダイレクトマップ方式 (Direct Mapped) 1組のタグにより構成（連想度1）されるデータ格納構造。アドレスにより一意に配置が決まるため、タグの構造が非常に単純。だが、同一エントリに異なるフレームアドレスが転送されると必ずラインの入れ替えが発生する。ラインの入れ替えが頻発しスループットが落ちることをキャッシュスラッシングというが、この状態が起こりやすくヒット率は他の方式に比べ高くない。 セットアソシアティブ方式 (Set Associative) 複数のタグにより構成(連想度2以上)されるデータ格納構造。同一エントリに異なるフレームアドレスのデータを複数格納することができる。連想度が上がるほどキャッシュヒット率は上昇するが製造は困難になっていくため、システムによりバランスのよい実装が異なる。n個のタグにより構成された場合、nウエイセットアソシアティブ方式と呼ぶ。最近はCAM (連想メモリ：Content Addressable Memory)がタグとして使われ出し、32など非常に高い連想度を実装できるようになってきた。ダイレクトマップ方式や下記のフルアソシアティブ方式はこの方式の特殊な場合である。 フルアソシアティブ方式 (Fully Associative) エントリアドレスによる振り分けはなく、全てのラインが検索対象となる構造。従って連想度はライン数分となる。キャッシュスラッシングは起こり難くヒット率は最も優れているが、実装コストや複雑度の面から通常用いられることはない。
※この「データ格納構造」の解説は、「キャッシュメモリ」の解説の一部です。
「データ格納構造」を含む「キャッシュメモリ」の記事については、「キャッシュメモリ」の概要を参照ください。
- データ格納構造のページへのリンク
