Achieving Non-Inclusive Cache Performance with Inclusive Caches 本多・近藤研究室 金東賢 2013年5月27日

Achieving Non-Inclusive Cache Performance with Inclusive Cache 論文について タイトル Achieving Non-Inclusive Cache Performance with Inclusive Cache 著者 Aamer Jaleel, Eric Borch, Malini Bhandaru, Simon C. Steely Jr., and Joel Emer 出典 MICRO '43: Proceedings of the 2010 43rd Annual IEEE/ACM International Symposium on Microarchitecture,pp.151-162, 2010.

キャッシュ階層構造の種類 CPU CPU CPU L1 a b a b a b LLC a e b o b m e g r m j k (a)Inclusive Hierarchy LLCはL1のラインを 保持 (b)Non-Inclusive Hierarchy LLCはL1のラインを 一部保持 (c)Exclusive Hierarchy LLCはL1のラインを 保持しない インクルーシブキャッシュの利点 コヒーレンシ維持コストが低い

インクルーシブキャッシュの課題 CPU LLCが使える容量 a b L1 LLC t m k k a b bを追い出す 課題

3種類の階層構造の比較 目的 L1,LLCの容量比を1:2～1:16に変えて比較 他の階層構造に比べ、低い結果… インクルーシブキャッシュを 1とする 他の階層構造に比べ、低い結果… 目的 インクルーシブキャッシュの長所を損なわず、L1から時間的局所性の高いラインの追い出しを防ぐ。

キャッシュマネジメントのモデル化 … a, d, a, e, a, f, a … L1 LLC MRU:最近使用したラインを格納 □：エントリ　　　　　　左：MRU(Most Recently Used) →：追い出しの優先度　　右：LRU(Least Recently Used) 次のアクセスパターンを用いて手法を考察 … a, d, a, e, a, f, a …

キャッシュマネジメントのモデル化 … a, d, a, e, a, f, a … L1 LLC LRU:次追い出されるラインを格納 □：エントリ　　　　　　左：MRU(Most Recently Used) →：追い出しの優先度　　右：LRU(Least Recently Used) 次のアクセスパターンを用いて手法を考察 … a, d, a, e, a, f, a …

Baseline Inclusive Cache キャッシュミス時 　L1,LLC共に 　ラインを記憶 LLCのラインが 取り除かれる場合、 L1からも取り除かれてしまう L1にラインを保持する際、LLCもライン保持を行う。 LLCからラインの追い出しがある場合L1からも追い出す

Baseline Inclusive Cache アクセスパターン … a, d, a, e, a, f, a … aに アクセス CPU ヒット c a c b a 初期状態

Baseline Inclusive Cache アクセスパターン … a, d, a, e, a, f, a … aに アクセス CPU aをMRUへ更新 LLCに反映されない ヒット c a c a c b a L1でヒット aをMRUへ書き換え

Baseline Inclusive Cache アクセスパターン … a, d, a, e, a, f, a … dに アクセス CPU ミス a c ミス c b a L1,LLCでキャッシュミス L1,LLCでdをMRUへ書き換え

Baseline Inclusive Cache アクセスパターン … a, d, a, e, a, f, a … CPU cを追い出す dをMRUへ更新 d a c dをMRUへ更新 d c b a L1,LLCでキャッシュミス L1,LLCでdをMRUへ書き換え

Baseline Inclusive Cache アクセスパターン … a, d, a, e, a, f, a … aに アクセス CPU ヒット d a d c b a L1でaがヒット L1でaをMRUへ置き換え

Baseline Inclusive Cache アクセスパターン … a, d, a, e, a, f, a … CPU aをMRUへ更新 a d d a d c b a L1でaがヒット L1でaをMRUへ置き換え

Baseline Inclusive Cache アクセスパターン … a, d, a, e, a, f, a … eに アクセス CPU ミス a d ミス d c b a L1,LLCでキャッシュミス L1,LLCでeをMRUへ書き換え

Baseline Inclusive Cache アクセスパターン … a, d, a, e, a, f, a … CPU LLCに同期しaを追い出す eをMRUへ更新 aを追い出す e a d d eをMRUへ更新 e d c b a 問題点 L1,LLCでキャッシュミス L1,LLCでeをMRUへ書き換え 時間的局所性の高いラインの追い出し

1.Temporal Locality Hints (TLH) L1とLLCを同期 L1でヒットした場合に動作 L1のアクセス情報をLLCへ伝える ヒット毎に同期し、時間的局所性の高いラインを保護

1.Temporal Locality Hints (TLH) アクセスパターン … a, d, a, e, a, f, a … aに アクセス CPU ヒット c a c a b 初期状態 L1でヒット aをMRUへ書き換え

1.Temporal Locality Hints (TLH) アクセスパターン … a, d, a, e, a, f, a … CPU aをMRUへ更新 LLCに反映される a c a c 優先度をL1と同期 c a a c b L1でヒット aをMRUへ書き換え

1.Temporal Locality Hints (TLH) アクセスパターン … a, d, a, e, a, f, a … dに アクセス CPU ミス a c ミス a c b L1,LLCでキャッシュミス L1,LLCでdをMRUへ書き換え

1.Temporal Locality Hints (TLH) アクセスパターン … a, d, a, e, a, f, a … CPU cを追い出す dをMRUへ更新 d a c 優先度をL1と同期 d a c b 時間的局所性のあることがLLCに伝わる。 ヒット毎に同期を行うため、プロセッサ間通信が増える。 L1,LLCでキャッシュミス L1,LLCでdをMRUへ書き換え

2.Early Core Invalidation (ECI) LLC:ラインの追い出し Next VictimをL1で無効化 LLCでキャッシュ追い出し時に動作。 ライン追い出し時にNext VictimをL1で無効にする。 再度アクセスがあればLLCにアクセスされ、優先度が更新される。 L1ではキャッシュミスとなる。 LLCでヒットさせ、キャッシュ全体から 取り除かれないようにする次善策。

2.Early Core Invalidation (ECI) アクセスパターン … a, d, a, e, a, f, a … aに アクセス CPU ヒット c a c b a L1でヒット aをMRUへ書き換え 初期状態

2.Early Core Invalidation (ECI) アクセスパターン … a, d, a, e, a, f, a … CPU aをMRUへ更新 c a a c c b a L1でヒット aをMRUへ書き換え

2.Early Core Invalidation (ECI) アクセスパターン … a, d, a, e, a, f, a … dに アクセス CPU ミス a c ミス c b a L1,LLCでキャッシュミス L1,LLCでdをMRUへ書き換え

2.Early Core Invalidation (ECI) アクセスパターン … a, d, a, e, a, f, a … CPU cを追い出す dをMRUへ更新 L1に同じラインがあれば無効化 d a a c ※LLCには何もしない dをMRUへ更新 d c b a L1,LLCでキャッシュミス L1,LLCでdをMRUへ書き換え

2.Early Core Invalidation (ECI) アクセスパターン … a, d, a, e, a, f, a … aに アクセス CPU ミス d ヒット d c b a LLCでaがヒット L1,LLCでaをMRUへ置き換え

2.Early Core Invalidation (ECI) アクセスパターン … a, d, a, e, a, f, a … CPU aをMRUへ更新 a d LLCにアクセスさせ 追い出しを防ぐ aをMRUへ更新 a d c b a LLCでaがヒット L1,LLCでaをMRUへ置き換え

2.Early Core Invalidation (ECI) アクセスパターン … a, d, a, e, a, f, a … eに アクセス CPU ミス a d ミス a d c b L1,LLCでキャッシュミス L1,LLCでeをMRUへ書き換え

2.Early Core Invalidation (ECI) アクセスパターン … a, d, a, e, a, f, a … CPU dを追い出す eをMRUへ更新 e a d L1に無いのでそのまま bを追い出す eをMRUへ更新 e d d c b ラインの追い出し毎の動作のため、通信量が少ない。 短期間でにアクセスが無いと追い出されてしまう欠点がある。 L1,LLCでキャッシュミス L1,LLCでeをMRUへ書き換え

3.Query Based Selection (QBS) L1に無いラインをLLCから追い出す LLCのキャッシュ追い出し時に動作 LRUのラインがL1に存在するか調べる。 　　存在する→LRUの次のラインを調べる 　　存在しない→LRUにあるラインを取り除く 質問を行い、L1にあるラインを 追い出させない

3.Query Based Selection (QBS) アクセスパターン … a, d, a, e, a, f, a … aに アクセス CPU ヒット c a c b a L1でヒット aをMRUへ書き換え 初期状態

3.Query Based Selection (QBS) アクセスパターン … a, d, a, e, a, f, a … CPU aをMRUへ更新 c a a c c b a L1でヒット aをMRUへ書き換え

3.Query Based Selection (QBS) アクセスパターン … a, d, a, e, a, f, a … dに アクセス CPU ミス a c ミス c b a L1,LLCでキャッシュミス L1,LLCでdをMRUへ書き換え

3.Query Based Selection (QBS) アクセスパターン … a, d, a, e, a, f, a … CPU Cを追い出す dをMRUへ更新 d a c dをMRUへ更新 d c b a L1,LLCでキャッシュミス L1,LLCでdをMRUへ書き換え

3.Query Based Selection (QBS) アクセスパターン … a, d, a, e, a, f, a … aに アクセス CPU aをMRUへ更新 ヒット d a d a d c b a L1でヒット aをMRUへ置き換え

3.Query Based Selection (QBS) アクセスパターン … a, d, a, e, a, f, a … eに アクセス CPU ミス a d ミス d c b a L1,LLCでキャッシュミス L1,LLCでeをMRUへ書き換え

3.Query Based Selection (QBS) アクセスパターン … a, d, a, e, a, f, a … CPU No! 追い出すかどうか質問 a d d a c b a MRUへ L1,LLCでキャッシュミス L1,LLCでeをMRUへ書き換え

3.Query Based Selection (QBS) アクセスパターン … a, d, a, e, a, f, a … CPU ok! 追い出すかどうか質問 a d a d c b 犠牲になる L1,LLCでキャッシュミス L1,LLCでeをMRUへ書き換え

3.Query Based Selection (QBS) アクセスパターン … a, d, a, e, a, f, a … CPU dは追い出し eをMRUへ更新 e a d L1にあるラインは追い出さない eをMRUへ更新 e a d c 動作は複雑だがメモリストール中に行うためオーバーヘッドを小さく抑えられる L1,LLCでキャッシュミス L1,LLCでeをMRUへ書き換え

実験環境 X86シュミレータ(CMP$im)を使用 CPU0 CPU1 1 32kB 32kB L1 10 256kB 256kB L2 Core i7をモデルとしたキャッシュ階層構造・サイクル数 CPU0 CPU1 サイクル数 1 32kB 32kB L1 10 256kB 256kB L2 24 LLC 2MB 150 メインメモリ

実験環境 SPEC CPU2006 を使用 15種類から2つ組み合わせ全105パターンでベンチマーク。 各階層でのキャッシュミスから3種類に分類。 ※MPKI:命令1000回あたりのキャッシュミス回数 ワーキングセット ・L1に収まる:CCF(Core Cache Fitting), dea, h26, per, pov, sje ・LLCに収まる:LLCF(Last Level Cache Fittng), ast, bzi, cal, hmm, xal ・LLCより大きい:LLCT(Last Level Cache Thrashing), gob, lib, mcf, sph, wrf

実験結果 1 TLH-L1,L2,ECI,QBSは平均してそれぞれ 5,2%,2.7%,3.3%6.5%のパフォーマンス向上。 実験結果 1　　 TLH-L1 L1のヒットで動作 TLH-L2 L2のヒットで動作 インクルーシブキャッシュを1 TLH-L1,L2,ECI,QBSは平均してそれぞれ 5,2%,2.7%,3.3%6.5%のパフォーマンス向上。 通常の方式でL1から時間的局所性の高いラインの 追い出しがあったアプリケーションに有効

実験結果 2　　 L1とLLCの比を変えた場合の実験結果 QBSはノンインクルーシブキャッシュと同等の結果 インクルーシブキャッシュの欠点を改善

まとめ インクルーシブキャッシュの長所を損なわず、 L1から時間的局所性の高いラインの追い出しを防ぐ。 解決手法 まとめ　　 インクルーシブキャッシュの長所を損なわず、 L1から時間的局所性の高いラインの追い出しを防ぐ。 解決手法 ・Temporal Locality Hints (TLH) 　　プロセッサ間通信が多くなることが欠点 ・Early Core Invalidation (ECI) 　　ある一定時間内にアクセスがない場合有効でない ・Query Based Selection (QBS) 　　25パターンのベンチマークで10～33%のパフォーマンス向上 　　ノンインクルーシブキャッシュと同様の結果 提案手法はハードウェアを追加すること無く実現可能 マルチコアに有用な手法を提案