キャッシュ 頻繁にアクセスされるデータを入れておく小規模高速なメモリ 当たる(ヒット）、はずれる（ミスヒット） マッピング（割り付け） CacheであってCashではないので注意 元々はコンピュータの主記憶に対するものだが、IT装置の色々なところに使われるようになった ディスクキャッシュ、ページキャッシュ..etc.. 当たる(ヒット）、はずれる（ミスヒット） ミスヒットしたら、下のメモリ階層から取ってきて入れ替える(リプレイス） マッピング（割り付け） 主記憶とキャッシュのアドレスを高速に対応付ける Direct map　⇔　Full associative cache 書き込みポリシー ライトスルー、ライトバック リプレイス（追い出し）ポリシー LRU　(Least Recently Used)

アドレスマッピング（割り付け） ワード単位に割り付けるのは効率が悪い 順番に割り付けていって１周したら、元に戻る 一定の連続アドレスのブロック（ライン）を管理単位とする ブロックサイズは8byte-128byte程度 ここでは8word(16byte)を使う やや小さい 順番に割り付けていって１周したら、元に戻る キャッシュのブロック数（セット数）が2のn乗、ブロックサイズが2のm乗とすると、、、 残り n m タグ　（キー) インデックス ブロック内アドレス

… Direct Map のアドレス 割り付け 主記憶：1024ワード ブロックサイズ：8ワード キャッシュ：64ワード =8ブロック 0000000000 　　　　… 0000000111 0000010000 　　　　… 0000010111 0000100000 　　　　… 0000100111 0000110000 　　　　… 0000110111 0001000000 　　　　… 0001000111 0001010000 　　　　… 0001010111 1111111000 　　　　… 1111111111 0000001000 　　　　… 0000001111 0000011000 　　　　… 0000011111 0000101000 　　　　… 0000101111 0000111000 　　　　… 0000111111 0001001000 　　　　… 0001001111 1111110000 　　　　… 1111110111 … Direct Map のアドレス 割り付け 主記憶：1024ワード ブロックサイズ：8ワード キャッシュ：64ワード 　　　　　　　=8ブロック 000 001 010 011 100 101 110 111 Index Tag （Key) 0000101000 　　　　… 0000101111 ブロック内 アドレス

Direct Map From CPU 0011010 0011 010 100 … … 010 010 Main Memory (1KB=128Lines) Yes：Hit = Data 0011 Cache (64B=8Lines) Cache Directory (Tag Memory) 8 entries X (4bit ) ディレクトリは小さくて済む

Direct Map (Conflict Miss) From CPU 0000010 0000 010 100 … … 010 010 Main Memory No: Miss Hit = 0000 0011 Cache 010を共通するキャッシュラインは Conflict　Missを起こす Cache Directory (Tag Memory)

… 2-way set associative のアドレス 割り付け 00 01 10 11 Index Tag （Key) キャッシュ内 0000000000 　　　　… 0000000111 0000010000 　　　　… 0000010111 0000100000 　　　　… 0000100111 0000110000 　　　　… 0000110111 0001000000 　　　　… 0001000111 0001010000 　　　　… 0001010111 1111111000 　　　　… 1111111111 0000001000 　　　　… 0000001111 0000011000 　　　　… 0000011111 0000101000 　　　　… 0000101111 0000111000 　　　　… 0000111111 0001001000 　　　　… 0001001111 1111110000 　　　　… 1111110111 … 2-way set associative のアドレス 割り付け 00 01 10 11 Index Tag （Key) 0000101000 　　　　… 0000101111 キャッシュ内 アドレス

2-way set associative Map From CPU 0011010 00110 10 100 … … 10 Main Memory (1KB=128Lines) Yes: Hit = Data 00110 Cache (64B=8Lines) 10 No = 00000 Cache Directory (Tag Memory) 4 entries X 5bit X 2

2-way set associative Map From CPU 0000010 0011010 00000 10 100 … … 10 Main Memory (1KB=128Lines) No = 00110 Cache (64B=8Lines) 　　10 Data Yes: Hit = 00000 Cache Directory (Tag Memory) 4 entries X 5bit X 2 Conflict　Missが減る

4-way set associative Map From CPU 0000010 0011010 001101 100 … … Main Memory (1KB=128Lines) 001101 = Ｄａｔａ = = 000000 Cache (64B=8Lines) Cache Directory (Tag Memory) 2 entries X 6bit X 4 =

8-way set associative Map → Full Map From CPU 0000010 0011010 … … 0011010 100 Main Memory (1KB=128Lines) 0011010 = = = Ｄａｔａ = = = = 0000001 Cache (64B=8Lines) Cache Directory (Tag Memory) 7bit X 8 =

Way数のトレードオフ 大きくすると、、、 ヒット率が改善 遅延時間が大きくなる（マルチプレクサの遅延） 8くらいまでが多い Direct Map→2way set associative 32人で1つの椅子を争う　VS. 64人で2つの椅子を争う 　　偶然同じ時間に椅子を狙うライバルが居る場合は効果的 サイズを倍にするのと同じ程度の効果が見込まれる それ以上はどんどん効果が減る 4以上はあまり効果が上がらない 遅延時間が大きくなる（マルチプレクサの遅延） 8くらいまでが多い

書き込みポリシー Write Through Write Back 書き込み時に主記憶にもデータを書く Direct Write:ミス時は主記憶だけに書く Fetch-on-write:ミス時はリプレイスしてから書く 主記憶に合わせると性能ががた落ち（Verilogの設計はそうなっている）だが、Write bufferがあれば性能がさほど落ちることはない Write Back 書き込みはキャッシュのみ キャッシュと主記憶が一致：Clean、違う：Dirty Dirtyなキャッシュブロックは書き戻し（Write Back)をしてからリプレイス

Write Through （Hit） 0011010 … … From CPU Main Memory (1KB=128Lines) 100 主記憶も同時に更新 0011 Hit Cache (64B=8Lines) Write Data Cache Directory (Tag Memory) 8 entries X (4bit )

Write Through （Miss：Direct Write） 0000010 0011010 … … From CPU Main Memory (1KB=128Lines) 0000 010 100 主記憶のみ更新 0011 Miss Cache (64B=8Lines) Write Data Cache Directory (Tag Memory) 8 entries X (4bit )

Write Through （Miss：Fetch on Write） 0000010 0011010 … … From CPU Main Memory (1KB=128Lines) 0000 010 100 0011 0000 Miss Cache (64B=8Lines) Write Data Cache Directory (Tag Memory) 8 entries X (4bit )

Write Back （Hit） 0011010 … … From CPU Main Memory (1KB=128Lines) 0011 100 Dirty 0011 1 Hit Cache (64B=8Lines) Write Data Cache Directory (Tag Memory) 8 entries X (4bit+1bit )

Write Back （Replace） 0000010 0011010 … … From CPU Write Back Main Memory (1KB=128Lines) 0000 010 100 Dirty 0000 0011 1 Miss Cache (64B=8Lines) Cache Directory (Tag Memory) 8 entries X (4bit+1bit )

ライトスルーとライトバック 「ライトスルーは主記憶を待たなければならないので非効率」というのは嘘 ライトバック ちゃんとライトバッファを装備すれば性能的に悪くはならない しかし、シングルライトが必要→DRAMに合わない 常にデータの一致が取れるのがメリット、観測性が高い、I/Oで有利 ライトバック 常にデータ転送がブロック単位→DRAM、高速バスに適合 バスの利用率が下がる→マルチコアに適合 大体世の中はライトバックになりつつある

リプレイスポリシー リプレイスの際、どのWayを選ぶか？ LRU (Least Recently Used) Direct map以外のキャッシュで問題になる LRU (Least Recently Used) 最近もっとも使っていないwayを選ぶ 2-wayならば簡単→ Verilog記述参照 4-way以上は結構面倒→　擬似的なLRUでも大体OK 他にランダム、FIFOなどが考えられるが実際上あまり用いられない

キャッシュの性能 キャッシュオーバーヘッド付きCPI(Clock cycles Per Instruction)＝ 理想のCPI + 　　命令キャッシュのミス率×ミスペナルティ　＋ 　　データキャッシュの読み出しミス率×読み出し命令の生起確率×ミスペナルティ この式の問題点 ミスペナルティは書き戻しを伴うかどうかで違ってくる（Write Back) ライトバッファの容量、連続書き込み回数によっては書き込みミスでもストールする 書き込み直後に読み出しをするとキャッシュが対応できないでペナルティが増えることもある→ノンブロッキングキャッシュ 実際は階層化されているのでそれぞれの階層を考えないといけない プロセッサがOut-of-order実行可能ならば読み出し時にストールしないかもしれない（この話は後ほど、、、） ちゃんと評価するにはシミュレータを使うしかない、、、、

ミスの原因：３つのC Capacity Miss：容量ミス Conflict Miss:衝突ミス 絶対的な容量不足により起きる Conflict Miss:衝突ミス 容量に余裕があっても、indexが衝突することで、格納することができなくなる Compulsory Miss (Cold Start Miss) 初期化ミス スタート時、プロセス切り替え時に最初にキャッシュにブロックを持ってくるためのミス。避けることができない

キャッシュサイズと それぞれもミスの 割合 Hennessy & Patterson Computer Architectureより

ミスを減らす 容量を増やす Way数を増やす ブロックサイズを大きくする 〇容量ミスはもちろん減る。衝突ミスも減る。 ×コストが大きくなる。ヒット時間が増える。チップ（ボード）に載らない Way数を増やす 〇衝突ミスが減る キャッシュ容量が小さいと効果的、2Wayは、2倍の大きさのDirect Mapと同じ位のミス率になる キャッシュ容量が大きい場合、残った不運な衝突ミスを減らす効果がある ×コストが大きくなる。ヒット時間が増える。4以上はあまり効果がない。 ブロックサイズを大きくする 　〇局所性によりミスが減る。 　×ミスペナルテイが増える。（ブロックサイズに比例はしないが、、） 　　　キャッシュが小さいと衝突ミスが増える 容量に応じて適切なブロックサイズを選ぶ。32byte-128byte

ブロックサイズと ミスの割合 Hennessy & Patterson Computer Architectureより

演習 ｘとｙは互いにコンフリクトミスを起こす番地に配置されている。Direct Mapキャッシュで、以下のパターンで読み書きを行ったとき、Write Through（Direct Write)とWrite　Backキャッシュで（１）ヒットするかミスするか(2)リプレイスが起きるかライトバックが起きるかを示せ。なお最初のｘに対する読み出しはミスすると仮定する。 １．xから読み出し ２．yに書き込み ３．yを読み出し ４．xを読み出し ５．yに書き込み ６．xに書き込み