キャッシュ配置ポリシー

キャッシュ配置ポリシーは、特定のメモリブロックがCPUキャッシュに入るときに配置できる場所を決定するポリシーです。メモリブロックは必ずしもキャッシュ内の任意の場所に配置できるわけではなく、キャッシュの配置ポリシーによって特定のキャッシュラインまたはキャッシュラインのセット^[1]に制限される場合があります。 ^{[2] [3]}

キャッシュ内のメモリブロックの配置には、ダイレクトマップ、フルアソシエイティブ、セットアソシエイティブの 3 つの異なるポリシーがあります。もともと、このキャッシュ構成の空間は「合同マッピング」という用語を使用して説明されていました。^[4]

ダイレクトマップキャッシュ構造では、キャッシュは複数のセットに編成され^[1]、セットごとに1つのキャッシュラインがあります。メモリブロックのアドレスに基づいて、1つのキャッシュラインのみを占有できます。キャッシュはn ×1列のマトリックスとしてフレーム化できます。^[5]

• セットはメモリブロックのアドレスから導出されたインデックス^{[1]ビットによって決定されます。}
• メモリブロックは識別されたセット内に配置され、タグ^[1]はセットに関連付けられたタグフィールドに格納されます。
• キャッシュ ラインがすでに占有されている場合は、新しいデータによってキャッシュ内のメモリ ブロックが置き換えられます。

• セットはアドレスのインデックス ビットによって識別されます。
• メモリ ブロック アドレスから得られたタグ ビットは、セットに関連付けられたタグ ビットと比較されます。タグが一致すると、キャッシュヒットとなり、キャッシュ ブロックがプロセッサに返されます。そうでない場合は、キャッシュ ミスとなり、メモリ ブロックは下位メモリ (メイン メモリ、ディスク) から取得されます。

• この配置ポリシーは、すべてのキャッシュ ラインの検索を回避するため、電力効率に優れています。
• 配置ポリシーと交換ポリシーはシンプルです。
• 一度にチェックする必要があるタグは 1 つだけなので、シンプルで低コストのハードウェアを使用できます。

• セット内で使用できるキャッシュラインは1つだけなので、キャッシュヒット率は低くなります。同じセットに対して新しいメモリが参照されるたびに、キャッシュラインが置き換えられ、競合ミスが発生します。^[6]

4 バイトのブロックとして構成された 16 キロバイトのメイン メモリと、ブロック サイズが 4 バイトの 256 バイトの直接マップ キャッシュについて考えてみましょう。メイン メモリは 16 キロバイトなので、メモリ アドレスを一意に表すには最低 14 ビットが必要です。

各キャッシュ ブロックのサイズは 4 バイトなので、キャッシュ内のセットの合計数は 256/4、つまり 64 セットになります。

キャッシュへの受信アドレスは、オフセット、インデックス、タグのビットに分割されます。

• オフセットは、キャッシュ ラインからアクセスするバイトを決定するために使用されるビットに対応します。キャッシュ ラインは 4 バイトの長さなので、オフセット ビットは 2 つあります。
• インデックスは、キャッシュのセットを決定するために使用されるビットに対応します。キャッシュには 64 のセットがあり、2^6 = 64 なので、6 つのインデックス ビットがあります。
• タグは残りのビットに対応します。つまり、14 – (6+2) = 6 個のタグ ビットがあり、キャッシュ要求のアドレスと一致するようにタグ フィールドに格納されます。

以下はメモリ アドレスと、それがどのキャッシュ ラインにマップされるかの説明です。

1. アドレス0x0000(タグ - 0b00_0000、インデックス - 0b00_0000、オフセット - 0b00) はメモリのブロック 0 に対応し、キャッシュのセット 0 にマップされます。
2. アドレス0x0004(タグ - 0b00_0000、インデックス - 0b00_0001、オフセット - 0b00) はメモリのブロック 1 に対応し、キャッシュのセット 1 にマップされます。
3. アドレス0x00FF(タグ – 0b00_0000、インデックス – 0b11_1111、オフセット – 0b11) はメモリのブロック 63 に対応し、キャッシュのセット 63 にマップされます。
4. アドレス0x0100(タグ – 0b00_0001、インデックス – 0b00_0000、オフセット – 0b00) はメモリのブロック 64 に対応し、キャッシュのセット 0 にマップされます。

フルアソシエイティブキャッシュでは、キャッシュは複数のキャッシュラインを持つ単一のキャッシュセットに編成されます。メモリブロックは任意のキャッシュラインを占有できます。キャッシュ構成は1× m行のマトリックスとして構成できます。^[5]

• キャッシュラインは、それに関連付けられた有効ビット^[1]に基づいて選択されます。有効ビットが 0 の場合、新しいメモリ ブロックをそのキャッシュラインに配置できます。それ以外の場合は、有効ビットが 0 の別のキャッシュラインに配置する必要があります。
• キャッシュが完全に占有されている場合、ブロックは削除され、メモリ ブロックはそのキャッシュ ラインに配置されます。
• キャッシュからのメモリブロックの追い出しは置換ポリシーによって決定される。^[7]

• メモリ アドレスのタグ フィールドは、すべてのキャッシュ ラインに関連付けられたタグ ビットと比較されます。一致する場合、ブロックはキャッシュ内に存在し、キャッシュ ヒットとなります。一致しない場合は、キャッシュ ミスとなり、下位メモリからフェッチする必要があります。
• オフセットに基づいてバイトが選択され、プロセッサに返されます。

• 完全連想キャッシュ構造により、メモリ ブロックを任意のキャッシュ ラインに配置できる柔軟性が得られ、キャッシュを最大限に活用できます。
• 配置ポリシーにより、キャッシュヒット率が向上します。
• キャッシュミスが発生した場合に、さまざまな置換アルゴリズムを利用できる柔軟性を提供します。

• 配置ポリシーは、比較回路がブロックを見つけるためにキャッシュ全体を実行する必要があるため、電力を大量に消費します。
• 連想比較ハードウェアのコストが高いため、すべての方法の中で最も高価です。

4 バイトのブロックとして構成された 16 キロバイトのメイン メモリと、256 バイトの完全連想キャッシュ、および 4 バイトのブロック サイズで構成されているとします。メイン メモリは 16 キロバイトであるため、メモリ アドレスを一意に表すには最低 14 ビットが必要です。

キャッシュ内のセットの合計数は 1 で、キャッシュ ブロックのサイズが 4 バイトであるため、セットには 256/4 = 64 のキャッシュ ラインが含まれます。

キャッシュへの受信アドレスは、オフセットとタグのビットに分割されます。

• オフセットは、キャッシュラインからアクセスするバイトを決定するために使用されるビットに対応します。例では、2つのオフセットビットがあり、キャッシュラインの4バイトをアドレス指定するために使用されます。
• タグは残りのビットに対応します。つまり、14 – (2) = 12のタグビットがあり、キャッシュ要求のアドレスと一致するようにタグフィールドに格納されます。

任意のメモリ ブロックを任意のキャッシュ ラインにマップできるため、メモリ ブロックは置換ポリシーに基づいてキャッシュ ラインの 1 つを占有できます。

セットアソシエイティブ キャッシュは、ダイレクトマップ キャッシュと完全アソシエイティブ キャッシュの間のトレードオフです。

セット アソシアティブ キャッシュは、n × m のマトリックスとして考えることができます。キャッシュは 'n' セットに分割され、各セットには 'm' キャッシュ ラインが含まれます。メモリ ブロックは最初にセットにマップされ、次にセットの任意のキャッシュ ラインに配置されます。

ダイレクトマップ キャッシュからフル アソシエイティブ キャッシュまでの範囲は、セット アソシエイティブ レベルの連続体です。(ダイレクトマップ キャッシュは一方向セット アソシエイティブであり、mキャッシュ ラインを持つフル アソシエイティブ キャッシュはm方向セット アソシエイティブです。)

今日の設計における多くのプロセッサキャッシュは、ダイレクトマップ、2ウェイセットアソシエイティブ、または4ウェイセットアソシエイティブのいずれかです。^[5]

• セットは、メモリ ブロックのアドレスから導出されたインデックス ビットによって決定されます。
• メモリ ブロックは、識別されたセット内の使用可能なキャッシュ ラインに配置され、タグはそのラインに関連付けられたタグ フィールドに格納されます。セット内のすべてのキャッシュ ラインが使用されている場合は、置換ポリシーによって識別されたブロックが新しいデータに置き換えられます。

• セットは、メモリ ブロックのアドレスから導出されたインデックス ビットによって決定されます。
• タグ ビットは、選択されたセットに存在するすべてのキャッシュ ラインのタグと比較されます。タグがいずれかのキャッシュ ラインと一致する場合、キャッシュ ヒットとなり、適切なラインが返されます。タグがいずれのラインとも一致しない場合は、キャッシュ ミスとなり、メモリ階層の次のレベルからデータが要求されます。

• 配置ポリシーは、直接マップされたキャッシュと完全に連想されたキャッシュの間のトレードオフです。
• キャッシュ ミスが発生した場合に置換アルゴリズムを使用する柔軟性を提供します。

• 配置ポリシーでは、キャッシュ内の利用可能なすべてのキャッシュ ラインが効果的に使用されず、競合ミスが発生します。

4 バイトのブロックとして構成された 16 キロバイトのメイン メモリと、ブロック サイズが 4 バイトの 256 バイトの 2 ウェイ セット アソシエイティブ キャッシュについて考えてみましょう。メイン メモリは 16 キロバイトなので、メモリ アドレスを一意に表すには最低 14 ビットが必要です。

各キャッシュ ブロックのサイズは 4 バイトで、2 ウェイ セット アソシエイティブであるため、キャッシュ内のセットの合計数は 256/(4 * 2) となり、32 セットになります。

キャッシュへの受信アドレスは、オフセット、インデックス、タグのビットに分割されます。

• オフセットは、キャッシュ ラインからアクセスするバイトを決定するために使用されるビットに対応します。キャッシュ ラインは 4 バイトの長さなので、オフセット ビットは 2 つあります。
• インデックスは、キャッシュのセットを決定するために使用されるビットに対応します。キャッシュには 32 セットあり、2^5 = 32 なので、5 つのインデックス ビットがあります。
• タグは残りのビットに対応します。つまり、14 – (5+2) = 7 ビットが、キャッシュ要求のアドレスと一致するようにタグ フィールドに格納されます。

以下はメモリ アドレスと、どのセットのどのキャッシュ ラインにマップされるかの説明です。

1. アドレス0x0000(タグ - 0b000_0000、インデックス - 0b0_0000、オフセット - 0b00) はメモリのブロック 0 に対応し、キャッシュのセット 0 にマップされます。ブロックは、キャッシュの置換ポリシーによって決定されるセット 0 のキャッシュ ラインを占有します。
2. アドレス0x0004(タグ - 0b000_0000、インデックス - 0b0_0001、オフセット - 0b00) はメモリのブロック 1 に対応し、キャッシュのセット 1 にマップされます。ブロックは、キャッシュの置換ポリシーによって決定されるセット 1 のキャッシュ ラインを占有します。
3. アドレス0x00FF(タグ - 0b000_0001、インデックス - 0b1_1111、オフセット - 0b11) はメモリのブロック 63 に対応し、キャッシュのセット 31 にマップされます。ブロックは、キャッシュの置換ポリシーによって決定されるセット 31 のキャッシュ ラインを占有します。
4. アドレス0x0100(タグ - 0b000_0010、インデックス - 0b0_0000、オフセット - 0b00) はメモリのブロック 64 に対応し、キャッシュのセット 0 にマップされます。ブロックは、キャッシュの置換ポリシーによって決定されるセット 0 のキャッシュ ラインを占有します。

他にも、スキュード キャッシュ^[8]などの方式が提案されています。この方式では、ウェイ 0 のインデックスは上記のように直接ですが、ウェイ 1 のインデックスはハッシュ関数で形成されます。優れたハッシュ関数は、直接マッピングと競合するアドレスがハッシュ関数でマッピングされたときに競合しない傾向があるという特性があり、そのため、異常なアクセス パターンが原因でプログラムが予想外に多くの競合ミスに悩まされる可能性が低くなります。欠点は、ハッシュ関数の計算による余分な遅延です。^[9]さらに、新しいラインをロードして古いラインを追い出すときに、新しいラインが各ウェイの異なるインデックスのデータと競合するため、どの既存のラインが最も最近使用されていないかを判断するのが難しい場合があります。スキュードでないキャッシュのLRU追跡は通常、セットごとに行われます。それでも、スキュード アソシアティブ キャッシュは、従来のセット アソシアティブ キャッシュに比べて大きな利点があります。^[10]

真のセット連想キャッシュは、コンテンツ アドレス可能メモリのようなものを使い、すべての可能な方法を同時にテストします。疑似連想キャッシュは、可能な方法を 1 つずつテストします。ハッシュ再ハッシュ キャッシュと列連想キャッシュは、疑似連想キャッシュの例です。

最初にテストした方法でヒットを見つける一般的なケースでは、疑似連想キャッシュは直接マップされたキャッシュと同じくらい高速ですが、競合ミス率は直接マップされたキャッシュよりもはるかに低く、完全連想キャッシュのミス率に近くなります。^[9]

• 結合性
• キャッシュ置換ポリシー
• キャッシュ階層
• ポリシーの作成
• キャッシュの色分け