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