なぜL3キャッシュは共有ブロックのみを保持できるのですか？

Question

最近のCACM記事[1]で、著者は共有およびコヒーレントのキャッシュのスケーラビリティを改善する方法を提示します。コア成分は、キャッシュがあると仮定しています 包括的, 、つまり、高レベルのキャッシュ（L3、1つのグローバルキャッシュなど）には、子孫の下位レベルのキャッシュに保存されているすべてのブロック（L1、コアごとに1つのキャッシュ）が含まれています。

通常、高レベルのキャッシュは、それぞれの子孫キャッシュよりも大きくなります。たとえば、4つのコアを備えたIntel Core I7シリーズの一部のモデルには、8MB共有キャッシュ（L3）と256kbのプライベートキャッシュ（L2）があります。つまり、共有キャッシュは、合計でプライベートキャッシュの8倍のブロックを保持できます。

これは、共有キャッシュが（新しいブロックをロードするために）ブロックを排除する必要があるときはいつでも、プライベートキャシュ²（ピジョンホール原理）と共有されていないブロックを見つけることができることを示唆しているようです。ただし、著者は次のように書いています。

私たち]は、すべてのリコールを潜在的に排除することができますが、それは関連性、または特定のブロックがキャッシュされる可能性のある場所の数の場合にのみ、共有キャッシュがプライベートキャッシュの骨材の関連性を超えています。十分な関連性により、[共有キャッシュ]は非シャレッドブロック[...]を見つけることが保証されています。この最悪の関連性がなければ、ミスの病理学的クラスターは、共有キャッシュのセット内のすべてのブロックが本当に共有される状況につながる可能性があります。

これはどのように可能ですか、つまり、たとえば、1MBが8MBをカバーすることができますか？明らかに、このようなキャッシュ階層がどのように機能するかについての詳細が見逃しています。ここでは「関連性」とはどういう意味ですか？ 「特定のブロックがキャッシュされる可能性のある場所の数」は明確ではありません。各キャッシュにブロックを複数回保存できるという解釈しか考えられませんが、それはまったく意味がありません。そのような「ミスの病理学的クラスター」はどのように見えるでしょうか？

---

1. オンチップキャッシュコヒーレンスがここにある理由 MMK Martin、MD Hill、DJ Sorin（2012）
2. 共有キャッシュがどのブロックが共有されているかを知っていると仮定する。これは、明示的な立ち退き通知と追跡ビットによって達成できます。これは[1]でも説明されています。

Answer 1

おそらく、私は関連性に光を当てることができます。これらのキャッシュは、メモリの開いたブロックだけではないので、それらをある種の一般的なコンテナとは考えないでください。メモリの各ブロックには実際のアドレスがあります（これが物理的であろうと仮想であろうと、固定アドレスであると仮定します）。キャッシュの各レベルで、このメモリは、キャッシュ内の非常に特定の場所でのみキャッシュできます。

たとえば、メモリアドレスXは、位置Y0のL1キャッシュに保存できます。これは直接マッピングです。ただし、Y1の場所に保存できると仮定し、2方向の連想（これはかなり一般的です）です。 n-locationsに保存可能になると、n-way連想が得られます。チップがキャッシュの位置を選択すると、これらのNの場所のみをチェックします。キャッシュ全体をスキャンしません（遅すぎる/複雑になります）。

これは、共有キャッシュには低いキャッシュよりも高い関連性が高いと言うことによって、彼らが意味することを明確にするはずです。したがって、L1が2方向である場合、L2は4ウェイで、4つのプロセッサがあり、共有キャッシュは24方向の連想を共有する必要があります（記事はありませんが、これは意味のように聞こえます）。これに続きますが、これらの共有された場所の少なくとも1つは、プライベートキャッシュのいずれでもキャッシュされてはなりません。

私は彼らの「病理学的」ケースが何であるかを確実に言うことはできませんが、私は共通のケース、つまりバイナリ検索のようなものに影響を与える可能性のあるものを説明することができます。 L1キャッシュは1方向の連想、サイズが4kbであるとします。メモリを保存できる場所は、おそらくアドレスの単純なmod（x mod 4k）です。次に、2（一般的です）のパワーであるデータの大きなブロックがあるとします。バイナリ検索では、常にサイズを半分に刻むため、256Kブロックで検索すると、128K、64K、32K、16K、8K、4K、および4K、および低いアドレスを確認する必要があります。しかし、ここで問題が発生するはずです。これらの最初の6つのアドレスはすべて、まったく同じキャッシュの場所にマップします。したがって、各アクセスには、ごくわずかなメモリのみにアクセスしているにもかかわらず、各アクセスには立ち退きと負荷が必要です。