メモリ階層とキャッシュ
メモリ階層は、レジスタ、キャッシュ、メインメモリ、バッキングストアといったレベルにストレージを編成し、小さく高速なレベルに最も使用される可能性の高いデータを保持することで、プログラムに対して大容量かつ高速なメモリという錯覚を与える。
Definition
メモリ階層とは、速度、コスト、容量が異なるストレージ技術を階層的に配置したものであり、平均アクセス時間を最小化するために、頻繁かつ最近アクセスされたデータがより高速で小容量のレベル（最も重要なのはキャッシュ）に配置されるように管理される。
Scope
この分野では、参照の局所性を利用してメモリが階層的に編成される理由と方法について扱う。これには、キャッシュ構造（配置、置換、書き込みポリシー）、マルチレベルキャッシュ、プロセッサ間のキャッシュコヒーレンス、仮想メモリとアドレス変換、および基盤となるDRAMと新興メモリ技術が含まれる。プロセッサの実行自体（プロセッサのマイクロアーキテクチャ）や大規模なファイルおよびデバイスストレージ（ストレージおよびI/Oシステム）は含まれないが、これら両方に隣接する。
Sub-topics
Core questions
- 参照の局所性が階層型メモリ階層を効果的にするのはなぜか？
- キャッシュは配置、アソシアティビティ、置換、書き込みポリシーに関してどのように組織されているか？
- 複数のキャッシュが同じメモリのコピーを保持している場合、一貫性（コヒーレンス）はどのように維持されるか？
- 仮想メモリはどのようにアドレスを変換し、保護と大容量メモリの錯覚を提供するのか？
- DRAMと新興メモリの特性はシステムパフォーマンスをどのように形成するか？
Key concepts
- 時間的局所性と空間的局所性
- キャッシュヒットとキャッシュミス
- アソシアティビティと置換ポリシー
- ライトスルーとライトバック
- マルチレベルキャッシュ
- キャッシュコヒーレンス
- 仮想メモリとページング
- トランスレーションルックアサイドバッファ
- DRAMとメモリ帯域幅
- 平均メモリアクセス時間
Key theories
- 参照の局所性
- プログラムは最近アクセスしたデータを再利用する傾向があり（時間的局所性）、近くのアドレスにアクセスする傾向がある（空間的局所性）。メモリ階層は、最近使用されたブロックをキャッシュし、隣接するデータをまとめてフェッチすることで、これら両方を活用する。
- キャッシュ設計のトレードオフ
- キャッシュの性能はミス率、ミス・ペナルティ、ヒット時間によって決定され、サイズ、ブロックサイズ、アソシアティビティ、置換および書き込みポリシーによって調整される。古典的な分析では、これらの選択の対象として、強制ミス、容量ミス、競合ミスが特定されている。
Mechanisms
プロセッサがデータを要求すると、まずキャッシュがチェックされる。ヒットした場合はデータが迅速に返され、ミスした場合は下位レベルからブロックがフェッチされ、置換ポリシーによって別のブロックが追い出される場合がある。書き込みはライトスルーまたはライトバック方式で伝播され、コヒーレンスプロトコルによって複数のキャッシュの一貫性が保たれる。仮想メモリは、ページテーブルとトランスレーションルックアサイドバッファを介した変換ステップを追加し、プログラムアドレスを物理DRAMにマッピングしながら保護を強制する。
Clinical relevance
メモリ階層は、実際のパフォーマンスを頻繁に支配する。プロセッサはメインメモリよりもはるかに高速であるため、キャッシュの動作と局所性は、生の命令速度よりも重要となることが多い。キャッシュを意識したデータレイアウト、ブロッキング、プリフェッチは、高性能コンピューティング、データベース、機械学習カーネルの中心であり、キャッシュタイミングはセキュリティサイドチャネルの発生源となっている。
History
モーリス・ウィルクスは1965年にキャッシュ（「スレーブメモリ」）を提案し、IBM System/360 Model 85などの商用マシンにキャッシュが導入された。仮想メモリは1960年代初頭のアトラスコンピュータで生まれ、デニングのワーキングセットモデルによって形式化された。アラン・ジェイ・スミスの1982年の調査はキャッシュ設計の知識を統合し、プロセッサとメモリの速度差が拡大するにつれて、マルチレベルキャッシュと洗練されたコヒーレンスプロトコルが標準となった。
Debates
- 局所性のハードウェア管理とソフトウェア管理
- 透過的なハードウェアキャッシュと明示的に管理されるメモリ（スクラッチパッド、ソフトウェア制御プリフェッチ）の間には継続的な緊張関係がある。ハードウェアキャッシュは汎用的でプログラミングが容易である一方、明示的な管理は特定のワークロードに対してより予測可能で効率的である場合がある。
Key figures
- Maurice Wilkes
- Alan Jay Smith
- Peter J. Denning
- John L. Hennessy
- David A. Patterson
Related topics
Seminal works
- hennessy2019
- smith1982cache
- patterson2020
Frequently asked questions
- キャッシュはメインメモリと比較して非常に小さいのに、なぜ効果的なのか？
- プログラムは局所性を示すためである。どの時点においても、プログラムは少数のワーキングセットのデータのみを繰り返し使用し、アクセスは近くのアドレスに集中する。したがって、そのワーキングセットを保持する小さなキャッシュが、要求の大部分を満たすことができる。
- キャッシュと仮想メモリの違いは何か？
- どちらも、より高速で小容量のレベルと、より低速で大容量のレベルの間でデータを移動させる。キャッシュ（ハードウェアで管理される）はメインメモリのブロックを保持する。仮想メモリ（オペレーティングシステムで管理される）は、プログラムアドレスを物理メモリにマッピングし、ディスクとの間でデータをページングするだけでなく、保護と物理RAMよりも大きなアドレス空間を提供する。