キャッシュの編成とポリシー

キャッシュの編成は、キャッシュがメモリーブロックをストレージにどのようにマッピングするか（配置とアソシアティビティ）、および置換と書き込みを管理するポリシーに関係し、これらが連携してキャッシュヒットの頻度とメインメモリとの相互作用を決定します。

Definition

キャッシュの編成とポリシーは、キャッシュの構造的および管理上の選択であり、ブロックをどこに配置できるか、ミス時にどのブロックが追い出されるか、書き込みが下位レベルにどのように伝播されるかなどを決定し、そのヒット率と動作を管理します。

Scope

このトピックでは、単一キャッシュの内部設計について説明します。具体的には、ダイレクトマップ、セットアソシアティブ、フルアソシアティブの配置。LRUとその近似などの置換ポリシー。ライトポリシー（ライトスルー対ライトバック）とライトアロケーション。ブロックサイズ。そして、ミスを強制、容量、競合に分類することです。マルチキャッシュコヒーレンス（キャッシュコヒーレンスプロトコル）とアドレス変換（仮想メモリとページング）は除外します。

Core questions

• ダイレクトマップ、セットアソシアティブ、フルアソシアティブの配置は、コストと競合動作においてどのように異なりますか？
• ミス時にブロックを追い出すべき置換ポリシーは何ですか、またそれはどのように安価に近似されますか？
• ライトスルーとライトバックのポリシーは、トラフィックと複雑さにおいてどのように異なりますか？
• ミスはどのように分類され、どのような設計変更がそれぞれの種類を減らしますか？

Key concepts

• ダイレクトマップキャッシュ
• セットアソシアティブキャッシュ
• フルアソシアティブキャッシュ
• 最近最も使用されていない（LRU）置換
• ライトスルー対ライトバック
• ライトアロケート
• ブロック（ライン）サイズ
• 強制、容量、競合ミス

Key theories

スリーCミスモデル

キャッシュミスは、強制（最初のアクセス）、容量（ワーキングセットに対してキャッシュが小さすぎる）、競合（アソシアティビティが少なすぎる）に分類でき、このフレームワークは、各設計パラメータ（サイズ、ブロックサイズ、アソシアティビティ）をそれが削減するミスに結びつけます。

Mechanisms

メモリアドレスは、タグ、インデックス、オフセットのフィールドに分割されます。インデックスはセットを選択し、タグはその中のブロックを識別し、アソシアティビティは1つのセットを共有するブロックの数を設定します。ミスが発生すると、キャッシュはブロックをフェッチし、置換ポリシー（多くの場合、最近最も使用されていないものの近似）によって選択された別のブロックを追い出します。書き込みは、メインメモリを即座に更新するか（ライトスルー）、ブロックをダーティとマークして更新を延期します（ライトバック）。

Clinical relevance

ミスによるペナルティはヒットに比べて大きいため、キャッシュの編成は効果的なパフォーマンスを左右します。プログラマーは、データレイアウト、ブロッキング、および局所性を高めるアクセスパターンを通じてキャッシュの動作を改善し、アーキテクトは、ヒット率と面積、電力、帯域幅のバランスを取るために、アソシアティビティ、ブロックサイズ、およびライトポリシーを調整します。

History

ウィルクスは1965年にスレーブ（キャッシュ）メモリを提案し、キャッシュはすぐに商業的に採用されました。アラン・ジェイ・スミスによる1982年の調査では、配置、置換、およびライトポリシーに関する広範な測定が統合され、今日でも使用されている設計語彙が確立されました。その後、スリーCモデルは、ミスの原因と対策について推論するための構造化された方法を提供しました。

Key figures

• Maurice Wilkes
• Alan Jay Smith
• John L. Hennessy
• David A. Patterson

Seminal works

• smith1982cache
• hennessy2019

Frequently asked questions

ライトスルーキャッシュとライトバックキャッシュの違いは何ですか？

ライトスルーキャッシュは、すべての書き込み時にキャッシュとメインメモリの両方を更新し、メモリを最新の状態に保ちますが、より多くのトラフィックを生成します。ライトバックキャッシュは、キャッシュのみを更新し、ブロックをダーティとマークし、追い出されたときにのみメモリに書き込むため、追加の管理コストはかかりますが、トラフィックを削減します。

ダイレクトマップキャッシュの代わりにセットアソシアティブキャッシュを使用する理由は何ですか？

ダイレクトマップキャッシュは、各ブロックに正確に1つの場所しか許可しないため、同じスロットにマッピングされるブロックは競合します。セットアソシアティビティは、各ブロックにセット内でいくつかの可能な場所を与えることで、競合ミスを減らしますが、より多くの比較ハードウェアとわずかに遅いヒットのコストがかかります。