--
初期ミス、容量ミス、競合ミス
--
キャッシュミスの分類
・初期ミス(C)
あるブロックがキャッシュに最初に入るためのミス率
・容量ミス(S)
キャッシュが理想的なフルアソシアティブ・キャッシュのときに発生する
ミス率をFとすると、S = F - C
・競合ミス(P)
連想性が原因で、キャッシュからはみ出す
P = M - C - S
分類はメモリアドレスのトレースから得ることができる
Full Associativeの場合の置換ポリシーはLRUとする
--
キャッシュのブロック図は試験に出る
--
キャッシュサイズとミス率の表
これが重要
Compulsory: 初期ミス
Capacity: 容量ミス
Conflict: 競合ミス
8KB 1-way 0.046 0.002 4% 0.023 51% 0.021 45%
8KB 2-way 0.038 0.002 5% 0.023 61% 0.013 34%
8KB 4-way 0.035 0.002 5% 0.023 66% 0.010 28%
8KB 8-way 0.029 0.002 6% 0.023 79% 0.004 15%
キャッシュサイズとミス率
--
キャッシュミスは必ず起こる
いかに減らすか
--
平均アクセス時間 = (1 - ミス率) キャッシュアクセス時間 + ミス率 * ミス処理時間
--
ミス率の減少方式(1)
ブロックサイズを適切な大きさにする
時間的局所性、空間的局所性のいずれに関連するか
大きいブロックサイズ
・空間的局所性の利用
・ミスペナルティの増大(転送時間の増大)
・ブロック数の減少(時間的局所性が利用困難)
・通常、32 ~ 64 byte
小さいキャッシュではブロックサイズが小さい方が、
大きいキャッシュではブロックサイズが大きい方がよい
--
ミス率の減少方法(2)
高い連想性の利用
ダイレクトマップ-> セットアソシアティブ
競合ミスの減少と、キャッシュアドレス時間のトレードオフ
1way 1
2way 1.1
4way 1.12
8way 1.14
--
ミス率の減少方法(3)
Victim Cache
ダイレクトマップでの競合ミスを、最近追い出されたブロックを保持する小さなfull associativeキャッシュで回避
4エントリから7エントリで十分有効。
--
ミス率の減少方法(4)
・疑似セットアソシアティブ
各wayは独立したメモリではなく、同一メモリの異なる領域としておく
どのwayをアクセスするか、アクセス順でブロック内容を交換
ヒット時間が直接ヒットする場合と、疑似ヒットする場合に分かれる
様々な方式
--
ミス率の減少方式(5) ☆
・ハードウェアによるプリフェッチ
予測する
- プリフェッチ CPUからの実際のアクセスに先立って、block in
- 命令 シーケンシャル実行時に、次のブロックをプ利府ぇっ値
- データ 連続アドレスアクセスで、次のブロックをプ利府ぇっ値
- アドレス予測表を用いて、一定ストライドのアクセスを検出する方式
- プリフェッチは、予想が外れた場合のメモリバンド幅の浪費が問題
高度なプリフェッチ
- Hidden Markov プリフェッチ
実はそれほど当たらない
- Global History Buffer プリフェッチ
過去アドレスをリストに格納して解析
- AMPM (Access Map Pattern Match)
過去にアクセスしたアドレスをビットテーブルで保持
並列パターン解析ハードウェアで次を推定
現在、一番精度の高いハードウェアプリフェッチャー
--
ミス率の減少方式(6)
・ソフトウェアによるプリフェッチ
コンパイラがプリフェッチ命令を挿入
プリフェッチ命令 non-blockingなキャッシュアクセス命令
コンパイラが、命令・データのアクセスパタンを解析
連続アクセス、一定ストライドアクセスなd
問題点
・プリフェッチ命令のオーバーヘッド
・競合ミスによる無駄なプリフェッチ
--
ミス率の減少方式(7)
最適化コンパイラによる、キャッシュを意識した変換・スケジューリング
すごく性能があがる
キャッシュはマシンごとに異なるので、
ライブラリがキャッシュを調べて行うとか(dynamic tuning)
--
ミス率の減少方式(8)
・キャッシュ置換方式の改善
LRUがなぜよいのか?
スタックモデルを使ってプログラミングをしているから
(function callでスタックを積み上げているから)
多くのプログラムにとり、LRUは最適戦略ではない
最大の問題はDeal block をいかに減らすか
新た恣意ブロックをキャッシュにいれるとき、LRUでもMRUでもない中間地点に挿入
時間的局所性だけをつかっているとわかれば、LRU側にいれる
空間的 .. MRU ..
--
ミス時ペナルティの減少(1)
・Read時のミスをWrite時のミスより優先
- Write Bufferによる書き込みの一時的保持
- Write Buffer
・主にWrite Through
・ミス時にWritter buffer をフラッシュするか、アドレス比較
・Combining Write Buffer バイト書き込み列を合併
--
ミス時ペナルティ削減(2)
サブブロック
ブロックをさらに小分割
--
ミス時ペナルティ削減(3)
・Early Restart
ミスを再開したデータを受け取った時点で、CPU実行を再開
・Critical Word First
ミスを発生したデータを最初に転送する
現在では常識
--
ミス時のペナルティ削減(4)
ノンブロックキングキャッシュ
- プリフェッチ命令と疑似機構
--
ミス時のペナルティ再現(5)
マルチレベルキャッシュ
2次キャッシュメモリ
--
ペナルティ削減(6)
マルチコアプロセッサにおけるCache Only Memory Architecture (COMA)
--
ヒット時アクセスの高速化(1)
論理アドレスキャッシュ
キャッシュ・ディレクトリのアドレス
・物理アドレス
・論理アドレスでアクセス
・論理インデクス、物理タグ
page aliasing
一つの物理アドレスに複数のエントリ
ページ共用で一貫性が失われる
対策
・way数を増やすことにより、ページアドレスにキャッシュインデクスが入らないようにする
・OSがAliasingを発生する共用を許可しない
・キャッシュタグに検出機構をつける