1回限りの最適化の場合、必要な値はコンピューターの仕様で見つけることができますが、自動最適化が必要な場合（たとえば、プログラムのアセンブリおよびインストール中）、特別なテストスイートの結果によって特性を間接的に決定する必要があります。
Linuxの便利なテストプログラムは、 lmbenchテストスイートのlat_mem_rdです。 彼女の仕事は、メモリ内に配列を割り当て、与えられたステップでその要素を読み取り、繰り返し配列を繰り返し通過させることです。 次に、より大きな配列が割り当てられます。 ステップ値と配列サイズごとに、平均アクセス時間が計算されます。
実際のシステムでこのプログラムによって取得されたグラフの例：
キャッシュはブロック（行）に分割されることを思い出してください。各ブロックは分割できない単位として保存され、全体が次のメモリレベルから読み取られます。 アドレスの最下位ビットは、キャッシュブロック内の目的のバイトのオフセットを決定します。 通常、ブロックは2次元で構成されます。複数のセットから、アドレスの次の最下位ビットによって望ましいセットが選択されます。 そして、いくつかの方法から、LRUルールに従って、必要なものを任意に選択します。
各ブロックに対して、メインメモリのブロックに保存されているデータのアドレスを含むタグが保存されます。 メモリにアクセスすると、目的のセットのすべてのタグが目的のアドレスのタグと比較されます。 たとえば、4つのウィンドウに編成された32ブロックのキャッシュの場合：
セットがアドレスの最下位ビットによって選択されるという事実により、メモリ内の連続した配列はキャッシュ内に連続して配置されます。 たとえば、ブロックサイズが64バイトで、配列の最初のブロックがセット0にある場合：
配列がキャッシュ全体に配置されている場合、アクセス時にミスはありません。配列の後続の各ブロックは、次のフリーウェーブに分類されます。 それ以降の配列のパスでは、キャッシュから読み取られ、次のレベルのメモリへの新しいアクセスは必要ありません。
アレイのサイズがキャッシュのサイズを超える場合、LRUルールに従って、アレイの最初のブロックが最後のブロックに置き換えられます。 たとえば、配列が35個のブロックで構成されている場合、最初の3つのブロックは強制的に削除されます。
これで、アレイの2回目のパスで、最初の3セットが次のメモリレベルから新しい方法で書き込まれ、残りの5セットがキャッシュから直接読み取られます。 2番目のパスの最後に、最後の3つのブロックが配列の最初のブロックに再び置き換わります。
したがって、後続の各パスで、20ブロックがキャッシュから読み取られ、残りの15ブロックが次のメモリレベルから読み取られます。 配列のサイズがキャッシュ全体のサイズ（この例では8ブロック）を超えると、パス間のデータはキャッシュに保存されません。各呼び出しは失敗し、次のレベルのメモリから新しいブロックを読み取ります。
乾燥残留物には何が含まれていますか？
- 配列がキャッシュよりも小さい間、アクセス時間は一定です（0％ミス）
- 配列がキャッシュよりも1ウェーブ未満大きい場合、アクセス時間は「余剰」のサイズに依存します
- 配列がキャッシュよりも1ベイ以上大きい場合、その配列へのアクセス時間は一定です（100％ミス）
さらに、ステップの急峻さにより、キャッシュの結合性を判断できます。 キャッシュが非連想型（直接マッピング：1つのウェーブのみ）の場合、ファンのサイズはキャッシュのサイズに等しく、ミスの100％は2倍のサイズのキャッシュで始まります。 キャッシュが2レーンの場合、ファンのサイズはキャッシュのサイズの半分で、ステップの右端はキャッシュのサイズの1.5倍です。 など：キャッシュが完全に結合されている場合（1セットのみ）、ファンのサイズはブロックのサイズに等しく、ステップは垂直です：1ブロックでもキャッシュサイズを超えると、100％のミスが発生します。
グラフでは、最初のステップは明らかに垂直であり、2番目のステップはかなりぼやけています。 第1レベルのキャッシュはコードとデータで別々であるため、配列を通過するたびにキャッシュ内で同じイベントが発生すると結論付けることができます。 また、2次キャッシュは一般的であるため、テストプログラムのコード、OSのコードとデータも含まれています。 したがって、2番目のステップは、配列のサイズがキャッシュのサイズに達する前でも開始されます。 キャッシュサイズは、アレイへのアクセス時間の再現可能な線形増加が始まるアレイのサイズです。 チャートでは6MBであり、プロセッサの仕様でも確認されています。
配列のサイズに対するアクセス時間の依存性が分析されます。 ステップサイズはどうですか？ 最初の重要な事実：同じ配列サイズの場合、ステップサイズはミスの数に影響しません。 ステップがブロックサイズよりも大きい場合、アレイ全体がキャッシュに読み込まれるのではなく、個々のブロックが読み込まれます。 セットの一部は無料のままです。 いずれにせよ、配列がキャッシュより小さくなるまで0％のミスが発生し、配列がもう1つの方法であれば100％のミスが発生します。 たとえば、36ブロックの配列と128バイトのステップ（2ブロック）の場合：
各パスで、セット0と2でミスが発生し、新しい方法で10ブロックがメモリから読み取られます。 セット4と6（8ブロック）の内容はパス間で保存され、キャッシュから直接読み取られます。 10/18 = 56％のミスがあります。 ステップが256バイト（4ブロック）の場合：
各パスで、セット0でミスが発生し、5つのブロックが新しい方法でメモリから読み取られます。 セット4（4ブロック）の内容はパス間で保存され、キャッシュから直接読み取られます。 5/9 = 56％のミスがあります。
ステップサイズがファンのサイズを超えると、状況は多少変わります。この場合、「失われた」ファンは空いたままで、アレイ自体がキャッシュサイズよりも大きい場合でも、アレイのすべての読み取りブロックがキャッシュに配置されます。 たとえば、64ブロックの配列、およびキロバイト（16ブロック）のステップの場合、4ブロックのみが読み取られ、それらはすべて同じセットに分類されます。
ファンのサイズがブロックのサイズと一致する完全連想キャッシュでも同様の状況が常に発生します。 このようなパッセージの際立った特徴は、ステップサイズに応じてステップの左端がシフトすることです。2倍のステップは、2倍の「見かけの」キャッシュサイズに対応します。
最初のグラフでは、ステップの左端がすべてのステップサイズで一致しています。つまり、各キャッシュのサイズは試行したステップサイズの最大値よりも大きく、少なくとも4 KBです。 L1キャッシュの場合、垂直方向のステップが見られます。32KBの配列では0％のミス、36KBの配列では100％のミスです。 上で見たように、これは4KBのサプリメントがすべていっぱいになることを意味します。 したがって、ファンのサイズは正確に4KB、つまり L1キャッシュ8-8。
L2キャッシュの場合、約12MBまで直線的に増加します。 キャッシュの最大2倍のサイズ。これは非連想キャッシュに対応します。 ただし、プロセッサの仕様では、L2キャッシュは24ウェイ、つまり 256KBのサイズ。 キャッシュの実装が仕様を満たしていない（誰かがこれに注意を払っていただろうか？）、またはファンを選択するアルゴリズムがLRUと異なると結論付けることができます。 いずれにせよ、キャッシュが実際に24ウェイLRUである場合よりも、大きなアレイを循環するときのキャッシュへの実際のアクセス時間が優れている （平坦なステップ）ことは注目に値します。
そして、チャートで観察できるいくつかの興味深い現象。 1MBアレイから始めて、メモリへのアクセス時間はステップサイズに依存します-上記で見たように、これはキャッシュミスの発生によって説明できません。 ステップサイズがブロックサイズよりも小さい場合、同様の画像が観察されます。キャッシュオーバーフロー後、ミスの数は100％に達しませんが、ステップサイズに応じてより低いレベルになります。 ハーフブロックのステップでは、50％のミスが発生します（次のレベルのメモリからブロックを読み取るたびに、キャッシュから次の配列要素を読み取ります）。 1/4ブロックのステップでは、25％のミスが発生します（各ブロックがメモリから読み取られた後-キャッシュから3回読み取られます）など。 キャッシュに数キロバイトのブロックがあるのはどうしてですか？
ご想像のとおり、これはメモリのページング構成とDTLBオーバーフローです。 1MBは256の4キロバイトページです。 したがって、DTLBの容量は256レコードです。 配列が1 MBを超える場合、要素を読み取るたびに、配列の実際のデータを読み取ることに加えて、メモリからページテーブルエントリ（PTE）も読み取る必要があります。 512バイトのステップでは、PTEが読み取られるたびに、DTLBで7つのヒットが続き、ミスの12％がアレイへのアクセス時間をほとんど増加させません。 一方、4KBのステップでは、各PTE読み取りがメモリから実行され（DTLBで100％ミス）、アクセス時間が大幅に増加します。 DTLBのミスの100％はすぐには達成されませんが、サイズが1280KBの配列、つまり DTLBの容量の4分の1。 このことから、DTLBは4レーンであると結論付けました。
別の興味深い現象は、L2キャッシュのサイズを超える配列へのアクセス時間（つまり、各呼び出しが最後のレベルのメモリであるRAM）もステップサイズに依存し、その差はDTLBのミスで説明できるよりも大きいことです。 追加の違いは、SDRAMプロトコルによって説明されます。SDRAMプロトコルは、「メモリラインを開く」操作と「オープンラインから読み取る」操作を分離します。 同様に、DTLBのミスでは、小さいステップですでに開いている行から配列の次の要素を読み取ることができますが、大きいステップでは、呼び出しごとに新しい行を開く必要があります。 観測された遅延と回線を開く遅延との対応の数値検証は実行しませんでした。 使用されているメモリモジュールの仕様が見つかりませんでした。