複数の有効なスロットがアドレスに一致する場合、同じアドレスの以前の検索が実行されたときに、アドレスに一致するはずの有効なスロットが使用されなかったことを意味します (おそらく最初にチェックされていないため)。または、キャッシュにまったくない行を格納するために複数の無効なスロットが使用されました。
間違いなく、これはバグと見なされるべきです。
しかし、バグを修正しないことに決めた場合 (より良い実装のために多くのハードウェアをコミットしたくないかもしれません)、最も明白なオプションは、スロットの 1 つを選択して無効にすることです。その後、他のキャッシュ ラインで使用できるようになります。
無効にするものを選択する方法については、重複する行の 1 つがクリーンな場合、ダーティなキャッシュ ラインよりも優先してその 1 つを無効にします。複数のキャッシュ ラインがダーティで、それらが同意しない場合は、さらに大きなバグを修正する必要があります。
編集：これを行うためにハードウェアを実装する方法は次のとおりです。
まず、重複の仮定から始めるのはあまり意味がありません。後で適切な時期にそれを回避します。新しい行をキャッシュするときに何が起こるかについて、いくつかの可能性があります。
- ラインはすでにキャッシュにあるため、アクションは必要ありません
- ラインはキャッシュにありませんが、使用可能な無効なスロットがあります: 新しいラインを使用可能なスロットの 1 つに配置します
- ラインはキャッシュにありませんが、使用可能な無効なスロットはありません。別の有効な行を削除する必要があり、新しい行が代わりに使用されます。
- エビクション候補を選択すると、パフォーマンスに影響があります。クリーンなキャッシュ ラインは無料で削除できますが、選択を誤ると、近い将来に別のキャッシュ ミスが発生する可能性があります。1 つを除くすべてのキャッシュ ラインがダーティであるかどうかを検討します。クリーンなキャッシュ ラインのみが削除された場合、2 つのアドレス間で交互に行われる多数の順次読み取りにより、すべての読み取りでキャッシュ ミスが発生します。キャッシュの無効化は、Comp Sci の 2 つの難しい問題 (もう 1 つは「名前付け」) の 1 つであり、この正確な質問の範囲外です。
おそらく、これらのそれぞれに対して動作する正しいスロットをチェックする検索を実装します。次に、別のブロックがそのリストから最初のものを選択し、それに基づいて動作します。
さて、質問に戻ります。重複がキャッシュに入る可能性がある条件は何ですか。メモリアクセスが厳密に順序付けられていて、(上記のように) 実装が正しい場合、重複はまったく可能ではないと思います。したがって、それらをチェックする必要はありません。
ここで、1 つのキャッシュが 2 つの CPU コアで共有されている、より信じられないケースを考えてみましょう。機能する最も単純な方法を実行し、各コアのキャッシュ メモリ自体を除くすべてを複製します。したがって、スロット検索ハードウェアは共有されません。これをサポートするために、スロットごとに余分なビットがミューテックスとして使用されます。検索ハードウェアは、他のコアによってロックされているスロットを使用できません。具体的には、
- アドレスがキャッシュにある場合は、スロットをロックしてそのスロットを返すようにしてください。スロットがすでにロックされている場合は、解放されるまでストールします。
- アドレスがキャッシュにない場合は、無効または有効だが削除可能な、ロックされていないスロットを見つけます。
この場合、実際には 2 つのスロットが同じアドレスを共有する位置になる可能性があります。両方のコアがキャッシュにないアドレスに書き込もうとすると、最終的に異なるスロットが取得され、重複した行が発生します。まず、何が起こるかを考えてみましょう。
- どちらの行もメイン メモリから読み取られました。それらは同じ値になり、両方ともクリーンになります。どちらかを追い出すのが正しいです。
- どちらの行も書き込みでした。どちらも汚れていますが、おそらく同じではありません。これは競合状態であり、メモリ フェンスまたはその他のメモリ順序付け命令を発行することによって、アプリケーションによって解決されているはずです。どちらを使用すべきかは推測できません。キャッシュがないと、競合状態が RAM に残ります。どちらかを追い出すのが正しいです。
- 1 行は読み取りで、1 行は書き込みでした。書き込みはダーティですが、読み取りはクリーンです。この場合も、キャッシュが介在していなければ、この競合状態は RAM に保持されますが、リーダーは別の値を見ることができます。きれいな行を追い出すことはRAMによって正しく、また常に読み取りと書き込みの順序を優先するという副作用もあります。
これで、何をすべきかはわかりましたが、このロジックはどこに属するのでしょうか。まず、何もしなければどうなるかを考えてみましょう。いずれかのコアの同じアドレスに対する後続のキャッシュ アクセスは、いずれかのラインを返す可能性があります。どちらのコアも書き込みを発行していない場合でも、読み取りは 2 つの値を交互に繰り返し、異なる結果を出し続ける可能性があります。これは、メモリの順序付けに関する考えられるすべてのアイデアを壊します。
1 つの解決策は、ダーティ ラインは 1 つのコアのみに属し、そのラインはダーティではなく、ダーティであり、別のコアによって所有されているとだけ言うことです。
- 2 つの同時読み取りの場合、両方のラインは同一であり、ロックが解除されており、交換可能です。後続の操作でコアがどの行を取得するかは問題ではありません。
- 同時書き込みの場合、両方の行は同期していませんが、相互に見えません。これによって生じる競合状態は残念ですが、破棄された行で発生するすべての操作が、消去された行で発生する操作の前に発生したかのように、妥当なメモリ順序付けが行われます。
- 読み取りと書き込みが同時に発生した場合、ダーティ ラインは読み取りコアからは見えません。ただし、きれいな行は両方のコアに表示され、ライターのメモリ順序が崩れる原因となります。将来の書き込みにより、両方がロックされる可能性さえあります (両方がダーティになるため)。
最後のケースは、汚れた行がきれいな行よりも好まれるということをかなり悪化させます。これにより、少なくともいくつかの余分なハードウェアが最初にダーティ ラインを検索し、ダーティ ラインが見つからない場合にのみラインをクリーニングするように強制されます。これで、新しい並行キャッシュの実装ができました。
- アドレスがキャッシュにあり、ダーティであり、要求元のコアによって所有されている場合は、そのスロットを使用します
- アドレスがキャッシュにあるがクリーンな場合
- 読み取りには、そのスロットを使用するだけです
- 書き込みの場合、スロットをダーティとしてマークし、そのスロットを使用します
- アドレスがキャッシュになく、無効なスロットがある場合は、無効なスロットを使用します
- 無効なスロットがない場合は、行を削除してそのスロットを使用します。
実装にまだ穴があります。両方のコアが同時にではなく同じアドレスにアクセスするとどうなるでしょうか。最も単純なことは、汚れた行は他のコアからは見えないということです。In cache but dirty は、キャッシュにまったく存在しないことと同じです。
あとは、アプリケーションが同期するためのツールを実際に提供することだけを考えなければなりません。行が汚れている場合は、行を明示的にフラッシュするツールをおそらく実行します。これは、エビクション中に使用されるのと同じハードウェアを呼び出すだけですが、ラインを無効ではなくクリーンとしてマークします。
長い投稿を簡潔にするために、重複を削除するのではなく、メモリの順序付けの問題がさらに発生しないようにし、重複排除の作業をアプリケーションまたは最終的な排除に任せることで、重複を処理するという考え方です。