srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

CPUキャッシュの最適化について

Non-blocking Cache

キャッシュメモリの構成法の一つであり, キャッシュミスが起こり, それが処理されている最中でも, cache アクセスを可能にする. さらにメモリレベルの並列性(Memory-level parallelism) を使用することで, 同時に複数のキャッシュミスを処理することできる.
Non-blocking Cacheが必要な理由を説明する. 現在のCPUは Out of Order で実行されているため, ある命令によりキャッシュミスが発生しても, 次の命令を実行することができる. その命令がメモリアクセスが必要ならば, キャシュにアクセスする必要があるが, Blocking Cache であればそこで命令の実行が止まってしまう. しかし, Non-blocking Cache であれば命令を完了することができたり, Cacheでデータがヒットしなかった場合でも, 前のキャッシュミスと並列にミスを処理することを可能にするため, メモリアクセスのレイテンシを小さくすることができる.

https://www.fujitsu.com/jp/Images/nonblockingcache01_tcm102-1951020.gif

Miss-Status Holding Registers (MSHR)

miss bufferと呼ばれており, 未処理のキャッシュミスを追跡するためのハードウェアである. キャッシュミスが起きたとき, MSHRはその要求されたキャッシュラインがすでにメモリからキャッシュへフェッチしようとしている最中かどうかを判断するのに使われる. (Non-blocking Cacheであればキャッシュミスの処理最中に後続の命令で同じメモリアドレスを要求してくることがあり得る.) もしすでに同じアドレスのミスを処理中であれば, この要求がMSHRのおなじエントリに併合され, 新しい要求を生成しないようにする. (する必要がない.) そうでなければ, 新しいMSHRのエントリをアロケートして, キャッシュラインの要求が予約される. 空きのMSHRがない場合は, ストールする.

https://www.cse.iitk.ac.in/users/biswap/CS422/L18-CO.pdf

Victim Cache

従来のものは, コアからのメモリアクセス要求に対しては, 1, 2, 3次と順にキャッシュをチェックし, それでもミスした場合は, メモリからデータを読み込む. メモリから読み込まれたデータは 3, 2, 1次キャッシュと順に格納され, コアにデータが送られることになる. これに対して, 1,2,3次と順にチェックするが, データを3,2次に書き込まずに, 直接1次にデータを書き込み, 書き込みによって追い出されるデータを2次に書き込む方式を victim cache という.

https://news.mynavi.jp/article/architecture-177/images/011.jpg

従来のキャッシュであれば, L1のデータはL2に存在し, L2のデータはL3に存在するという包含関係が存在した. これを Inclusion Cache という. 一方で, Victim Cache の場合そのような包含関係は存在しないので, Non Inclusion Cache という.

https://news.mynavi.jp/article/architecture-177/images/012.jpg

コンピュータアーキテクチャの話(177) ビクティムキャッシュとインクルージョンキャッシュ | マイナビニュース