たとえば、512KB の 64 ビット double 型の LUT を想定します。一般的に言えば、CPU はどのようにして構造を L1 または L2 にキャッシュしますか?
例: 中央の要素にアクセスします。LUT 全体をキャッシュしようとしますか、それともその一部だけをキャッシュしようとしますか?たとえば、中央の要素とそれに続く n 個の要素をキャッシュしますか?
CPU は、L2 キャッシュに何を保持するかを決定するためにどのようなアルゴリズムを使用しますか? それが従う特定の先読み戦略はありますか
注: 私は x86 を想定していますが、他のアーキテクチャーが POWER、SPARC などでどのように機能するかを知りたいと思っています.
LUT（ルックアップテーブル？）に使用するデータ構造に依存します
キャッシュは、散在するのではなく、連続して配置されたもの (配列や std::vector など) がメモリ内にある場合に最適です。
簡単に言えば、メモリの場所にアクセスすると、RAM のブロック (「キャッシュ ライン」に相当する -- x86 では 64 バイト) がキャッシュに読み込まれ、以前にキャッシュされたデータが削除される可能性があります。
通常、いくつかのレベルのキャッシュがあり、階層を形成しています。各レベルで、アクセス時間は増加しますが、容量も増加します。
はい、先読みがありますが、かなり単純なアルゴリズムとページ境界を越えることができないという制限があります (x86 では通常、メモリ ページのサイズは 4KB です)。
What Every Programmer Should Know About Memoryを読むことをお勧めします。それは主題に関する多くの素晴らしい情報を持っています.
キャッシュは通常、キャッシュ ラインの集合として形成されます。各キャッシュ ラインの粒度はキャッシュ ラインのサイズに合わせて調整されます。たとえば、128 バイトのキャッシュ ラインを持つキャッシュでは、データをキャッシュするアドレスが 128 バイトに調整されます。
CPU キャッシュは通常、LRU エビクション メカニズム (キャッシュ ミスで最も古いキャッシュ ラインをエビクトするなど、最も使用頻度の低いメカニズム) を使用し、メモリ アドレスから特定のキャッシュ ライン セットへのマッピングも行います。(これは、4k または 16M 境界に配置された複数のアドレスから読み取ろうとすると、x86 で多くの誤った共有エラーの 1 つになります。)
そのため、キャッシュ ミスが発生した場合、CPU は、ミスしたアドレス範囲を含むメモリのキャッシュ ラインを読み取ります。たまたまキャッシュ ラインの境界を越えて読み取る場合は、2 つのキャッシュ ラインを読み取ることになります。