メモリ階層
速さ・大きさ・コストの違いからキャッシュの必要性を理解します。
この週でできるようになること
- 容量・速度・コストのトレードオフから階層が必要な理由を説明できる。
- 時間的局所性と空間的局所性を区別できる。
- キャッシュヒットとミスが性能へ与える影響を計算できる。
- レイテンシーと帯域幅を区別できる。
まず、具体的な場面から
時間的局所性。近くに置くと速い。
空間的局所性。近くの値をまとめて運べる。
キャッシュミスの待ち時間が増える。
見えてくること：よく使うもの・近くにあるものを速い小さな記憶へ置くと、平均の待ち時間を減らせます。
ここで初めて、見えてきた関係を言葉や記号でまとめます。
AMATは平均アクセス時間。hit timeはヒット時の基本時間、miss rateはミス割合、miss penaltyはミスで追加される待ち時間です。
なぜそうなる？
毎回かかるヒット時間に、ミスした割合だけ追加のペナルティがかかる、と期待値で平均します。たとえばミスが10回に1回なら、追加待ち時間の10分の1を平均へ足します。
講義ノートで詳しく読む
元のMarkdownにある仕組み・図・用語を、順番に確認します。
1. なぜ一種類のメモリだけではないか
理想は「レジスタ並みに速く、SSD並みに大きく、安いメモリ」ですが、現実には両立しません。そのため階層化します。
速い・小さい・高価/bit
レジスタ
L1キャッシュ
L2キャッシュ
L3キャッシュ
DRAM（主記憶）
SSD/HDD
遅い・大きい・安価/bit
上位に目的のデータがあれば速く、なければ下位からまとまりで持ってきます。
2. 局所性
時間的局所性
最近使ったデータを近いうちに再び使う傾向です。ループ変数、頻繁に呼ぶ命令、同じオブジェクトなどがあります。
空間的局所性
あるアドレスを使うと、その近くも使う傾向です。配列を先頭から順に読む場合が代表です。
キャッシュは一語だけでなくキャッシュライン単位で転送し、空間的局所性を利用します。
3. ヒットとミス
- ヒット：要求データがキャッシュにある。
- ミス：なくて下位階層から取得する。
- ヒット率：全アクセス中のヒット割合。
- ミスペナルティ：ミス時に増える待ち時間。
平均アクセス時間の単純モデル：
AMAT = hit time + miss rate × miss penalty
例：L1ヒット1 ns、ミス率5%、ミスペナルティ50 nsなら
AMAT = 1 + 0.05 × 50 = 3.5 ns
ミスは少なくても影響が大きいと分かります。
4. レイテンシーと帯域幅
- レイテンシー：最初の結果が届くまでの時間。
- 帯域幅：十分長い時間で1秒あたりに運べる量。
トラックは出発して到着するまで遅くても、一度に大量の荷物を運べます。これは高レイテンシー・高帯域の例です。CPUは一つの依存処理の待ち時間に敏感で、GPUは多数スレッドと大量転送で帯域を活用する設計です。
5. キャッシュの基本構造
メモリアドレスは概念的に次へ分けられます。
tag | index | block offset
- offset：キャッシュライン内の位置。
- index：候補となるキャッシュ集合。
- tag：目的のメモリブロックか照合する情報。
直接対応、セットアソシアティブ、完全連想などの方式があります。初学では「同じ場所を奪い合う競合ミスがある」と理解すれば十分です。
6. 仮想メモリ
プログラムが使う仮想アドレスを、OSとCPUのMMUが物理アドレスへ対応づけます。
- プロセスごとに独立したアドレス空間を提供。
- 保護と共有を制御。
- 物理メモリを柔軟に割り当てる。
変換結果のキャッシュがTLBです。仮想メモリは単に「RAM不足時にSSDを使う機能」だけではありません。
7. CPUとGPUのメモリ
CPUは大きなキャッシュと複雑な制御で、少数スレッドの待ち時間を減らします。GPUは高い帯域と多数の実行可能warpを持ち、あるwarpが待つ間に別のwarpを実行して待ち時間を隠します。
例題で確かめる
hit time 2 ns、miss rate 10%、miss penalty 40 nsならAMATは？
- 10%を0.10に直す。
- 追加時間は0.10 × 40 = 4 ns。
- 基本時間2 nsに足す。
答え：AMAT = 2 + 4 = 6 ns。
実習
次を実行します。
python ../exercises/performance_lab.py memory --size 1000000
またはプロジェクトルートから：
python exercises/performance_lab.py memory --size 1000000
連続アクセスと大きなstrideのアクセスを比較します。
記録項目：
- PythonバージョンとCPU名（分かる範囲）
- sizeとstride
- 各処理時間
- 1要素あたりの時間
- 予想と結果が一致したか
- Python処理系のオーバーヘッドが結果へ混ざる点
説明課題
「RAMが16 GBあるならキャッシュはいらない」という主張を、容量と速度の両面から訂正してください。
練習問題
元ノートの小テストです。まず自分で答えを考え、必要なら下の答えを開いてください。
最近使った値を再利用する性質を何というか。
答えと考え方を見る
時間的局所性。
配列を順番に読む処理が利用する主な局所性は何か。
答えと考え方を見る
空間的局所性。
hit time 2 ns、miss rate 10%、miss penalty 40 nsのAMATはいくつか。
答えと考え方を見る
2 + 0.10 × 40 = 6 ns。最初のデータが届くまでの時間を何というか。
答えと考え方を見る
レイテンシー。
仮想アドレスから物理アドレスへの変換結果を保持する代表的なキャッシュは何か。
答えと考え方を見る
TLB。