Loading article…
キャッシュ配置ポリシーとは、特定のメモリブロックがCPUキャッシュに格納される際に、そのメモリブロックをどこに配置できるかを決定するポリシーです。メモリブロックは必ずしもキャッシュ内の任意の場所に配置できるわけではなく、キャッシュの配置ポリシーによって特定のキャッシュラインまたはキャッシュラインのセットに制限される場合があります[ 1 ] 。 [ 2 ] [ 3 ]
キャッシュ内のメモリブロックの配置には、ダイレクトマップ、フルアソシアティブ、セットアソシアティブの 3 つの異なるポリシーがあります。元々、このキャッシュ構成の空間は「コングルエンスマッピング」という用語を使用して説明されていました。[ 4 ]
ダイレクトマップキャッシュ構造では、キャッシュは複数のセット[ 1 ]に編成され、各セットに1つのキャッシュラインが割り当てられます。メモリブロックのアドレスに基づいて、1つのキャッシュラインしか占有できません。キャッシュはn ×1列行列として表現できます。[ 5 ]
16キロバイトのメインメモリ（4バイトのブロックで構成）と、256バイトのダイレクトマップキャッシュ（ブロックサイズ4バイト）を考えます。メインメモリが16kBなので、メモリアドレスを一意に表現するには最低14ビットが必要です。
各キャッシュブロックのサイズは4バイトなので、キャッシュ内のセットの総数は256÷4、つまり64セットになります。
キャッシュへの受信アドレスは、オフセット、インデックス、タグのビットに分割されます。
以下にメモリアドレスと、それらがどのキャッシュラインにマッピングされるかの説明を示します。
0x0000（タグ - 0b00_0000、インデックス - 0b00_0000、オフセット - 0b00）はメモリのブロック 0 に対応し、キャッシュのセット 0 にマッピングされます。0x0004（タグ - 0b00_0000、インデックス - 0b00_0001、オフセット - 0b00）はメモリのブロック 1 に対応し、キャッシュのセット 1 にマッピングされます。0x00FF（タグ – 0b00_0000、インデックス – 0b11_1111、オフセット – 0b11）はメモリのブロック 63 に対応し、キャッシュのセット 63 にマッピングされます。0x0100（タグ – 0b00_0001、インデックス – 0b00_0000、オフセット – 0b00）はメモリのブロック 64 に対応し、キャッシュのセット 0 にマッピングされます。完全連想キャッシュでは、キャッシュは複数のキャッシュラインを持つ単一のキャッシュセットに編成されます。メモリブロックはどのキャッシュラインにも配置できます。キャッシュ構成は1× m行行列として表現できます。[ 5 ]
16キロバイトのメインメモリ（4バイトのブロックで構成）と、256バイトの完全連想キャッシュ（ブロックサイズ4バイト）を考えてみましょう。メインメモリが16kBなので、メモリアドレスを一意に表現するには最低14ビットが必要です。
キャッシュ内のセットの総数は1であり、キャッシュブロックのサイズが4バイトであるため、セットには256/4=64のキャッシュラインが含まれます。
キャッシュへの入力アドレスは、オフセットとタグのビットに分割されます。
メモリのどのブロックもどのキャッシュラインにもマッピングできるため、メモリブロックは置換ポリシーに基づいていずれかのキャッシュラインを占有することができます。
セットアソシアティブキャッシュは、ダイレクトマップキャッシュとフルアソシアティブキャッシュの中間的な位置づけにある。
セットアソシアティブキャッシュは、n × m行列として考えることができます。キャッシュはn個のセットに分割され、各セットにはm個のキャッシュラインが含まれます。メモリブロックはまずセットにマッピングされ、その後、そのセット内の任意のキャッシュラインに配置されます。
ダイレクトマップ型からフルアソシアティブ型までのキャッシュの範囲は、セットアソシアティビティのレベルを示す連続体である。（ダイレクトマップ型キャッシュは一方向セットアソシアティブであり、m本のキャッシュラインを持つフルアソシアティブキャッシュはm 方向セットアソシアティブである。）
今日の設計における多くのプロセッサキャッシュは、ダイレクトマップ、2ウェイセットアソシアティブ、または4ウェイセットアソシアティブのいずれかである。[ 5 ]
16キロバイトのメインメモリ（4バイトのブロックで構成されている）と、256バイトの2ウェイセットアソシアティブキャッシュ（ブロックサイズは4バイト）を考えます。メインメモリが16kBなので、メモリアドレスを一意に表現するには最低14ビットが必要です。
各キャッシュブロックのサイズは4バイトで、2ウェイセットアソシアティブであるため、キャッシュ内のセットの総数は256/(4 * 2)となり、32セットになります。
キャッシュへの入力アドレスは、オフセット、インデックス、タグのビットに分割されます。
以下にメモリ アドレスと、それらがどのキャッシュ セットのどのキャッシュ ラインにマッピングされるかの説明を示します。
0x0000（タグ0b000_0000、インデックス0b0_0000、オフセット0b00）はメモリのブロック0に対応し、キャッシュのセット0にマッピングされます。ブロックは、キャッシュの置換ポリシーによって決定されるセット0内のキャッシュラインを占有します。0x0004（タグ0b000_0000、インデックス0b0_0001、オフセット0b00）はメモリのブロック1に対応し、キャッシュのセット1にマッピングされます。ブロックは、キャッシュの置換ポリシーによって決定されるセット1内のキャッシュラインを占有します。0x00FF（タグ – 0b000_0001、インデックス – 0b1_1111、オフセット – 0b11）はメモリのブロック63に対応し、キャッシュのセット31にマッピングされます。このブロックは、キャッシュの置換ポリシーによって決定される、セット31内のキャッシュラインを占有します。0x0100（タグ – 0b000_0010、インデックス – 0b0_0000、オフセット – 0b00）はメモリのブロック64に対応し、キャッシュのセット0にマッピングされます。ブロックは、キャッシュの置換ポリシーによって決定されるセット0内のキャッシュラインを占有します。スキューキャッシュ[ 8 ]などの他の方式も提案されている。スキューキャッシュでは、ウェイ0のインデックスは上記のように直接だが、ウェイ1のインデックスはハッシュ関数で生成される。優れたハッシュ関数は、直接マッピングと競合するアドレスがハッシュ関数でマッピングされたときに競合しないという特性を持ち、そのため、病的なアクセスパターンによってプログラムが予期せず多数の競合ミスに悩まされる可能性が低くなる。欠点は、ハッシュ関数の計算による余分なレイテンシである。[ 9 ]さらに、新しいラインをロードして古いラインを追い出すとき、新しいラインが各ウェイの異なるインデックスのデータと競合するため、どの既存のラインが最も最近使用されていないかを判断するのが難しい場合がある。非スキューキャッシュのLRUトラッキングは通常、セット単位で行われる。それでも、スキューアソシアティブキャッシュは、従来のセットアソシアティブキャッシュに比べて大きな利点がある。[ 10 ]
真のセットアソシアティブキャッシュは、コンテンツアドレス指定可能なメモリなどを用いて、考えられるすべての方法を同時にテストします。擬似アソシアティブキャッシュは、考えられる各方法を一度に1つずつテストします。ハッシュリハッシュキャッシュとカラムアソシアティブキャッシュは、擬似アソシアティブキャッシュの例です。
最初にテストした方法でヒットが見つかった一般的なケースでは、擬似連想キャッシュは直接マップキャッシュと同じくらい高速ですが、直接マップキャッシュよりも競合ミス率がはるかに低く、完全連想キャッシュのミス率に近くなります。[ 9 ]