キャッシュ 頻繁にアクセスされるデータを入れておく小規模高速なメモリ CacheであってCashではないので注意 元々はコンピュータの主記憶に対するものだが、IT装置の色々なとこ ろに使われるようになった ディスクキャッシュ、ページキャッシュ..etc.. 当たる(ヒット）、はずれる（ミスヒット） ミスヒットしたら、下のメモリ階層から取ってきて入れ替える(リプレイ ス） マッピング（割り付け） 主記憶とキャッシュのアドレスを高速に対応付ける Direct map ⇔ Full associative cache 書き込みポリシー ライトスルー、ライトバック リプレイス（追い出し）ポリシー LRU (Least Recently Used) アドレスマッピング（割り付け） ワード単位に割り付けるのは効率が悪い 一定の連続アドレスのブロック（ライン）を管理単位と する ブロックサイズは8byte-128byte程度 ここでは8word(16byte)を使う やや小さい 順番に割り付けていって１周したら、元に戻る キャッシュのブロック数（セット数）が2のn乗、ブロック サイズが2のm乗とすると、、、 残り n タグ （キー) インデックス m ブロック内アドレス 0000000000 … 0000000111 0000010000 … 0000010111 0000001000 … 0000001111 0000100000 … 0000100111 0000011000 … 0000011111 0000110000 … 0000110111 0000101000 … 0000101111 0001000000 … 0001000111 0000111000 … 0000111111 0001010000 … 0001010111 0001001000 … 0001001111 1111111000 … 1111111111 1111110000 … 1111110111 … Direct Map のアドレス 割り付け 主記憶：1024ワード 000 001 010 011 100 101 110 111 Index ブロックサイズ：8ワード Tag 0000101000 キャッシュ：64ワード ブロック内 … （Key) =8ブロック 0000101111 アドレス Direct Map From CPU 0011010 0011 010 100 … … Main Memory (1KB=128Lines) 010 Yes：Hit = Data 010 0011 Cache (64B=8Lines) Cache Directory (Tag Memory) 8 entries X (4bit ) ディレクトリは小さくて済む Direct Map (Conflict Miss) From CPU 0000010 0000 010 100 … … Main Memory 010 No: Miss Hit = 010 0011 0000 Cache Cache Directory (Tag Memory) 010を共通するキャッシュラインは Conflict Missを起こす 0000000000 … 0000000111 0000010000 … 0000010111 0000001000 … 0000001111 0000100000 … 0000100111 0000011000 … 0000011111 0000110000 … 0000110111 0000101000 … 0000101111 0001000000 … 0001000111 0000111000 … 0000111111 0001010000 … 0001010111 0001001000 … 0001001111 1111111000 … 1111111111 1111110000 … 1111110111 … 2-way set associative のアドレス 割り付け 00 01 Tag （Key) 10 11 Index 0000101000 … 0000101111 キャッシュ内 アドレス 2-way set associative Map From CPU 0011010 00110 10 100 … … Main Memory (1KB=128Lines) Yes: Hit = Data 10 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 00000 10 100 0011010 … … Main Memory (1KB=128Lines) No = 10 00110 Cache (64B=8Lines) 10 Yes: Hit = 00000 Cache Directory (Tag Memory) 4 entries X 5bit X 2 Data Conflict Missが減る 4-way set associative Map From CPU 0000010 001101 0 100 0 001101 0011010 … … Main Memory (1KB=128Lines) = = Ｄａｔａ = Cache Directory (Tag Memory) 2 entries X 6bit X 4 000000 = Cache (64B=8Lines) 8-way set associative Map → Full Map 0000010 From CPU 0011010 … … 100 0011010 0011010 Main Memory (1KB=128Lines) = = = Ｄａｔａ = = = Cache Directory (Tag Memory) 7bit X 8 0000001 = = Cache (64B=8Lines) Way数のトレードオフ 大きくすると、、、 ヒット率が改善 Direct Map→2way set associative 32人で1つの椅子を争う VS. 64人で2つの椅子を争う 偶然同じ時間に椅子を狙うライバルが居る場合は効果的 サイズを倍にするのと同じ程度の効果が見込まれる それ以上はどんどん効果が減る 4以上はあまり効果が上がらない 遅延時間が大きくなる（マルチプレクサの遅延） 8くらいまでが多い 書き込みポリシー Write Through 書き込み時に主記憶にもデータを書く 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) 0011 010 100 主記憶も同時に更新 0011 Hit Cache (64B=8Lines) Cache Directory (Tag Memory) 8 entries X (4bit ) Write Data Write Through （Miss：Direct Write） 0000010 0011010 … … From CPU Main Memory (1KB=128Lines) 0000 010 100 主記憶のみ更新 0011 Miss Cache (64B=8Lines) Cache Directory (Tag Memory) 8 entries X (4bit ) Write Data Write Through （Miss：Fetch on Write） 0000010 0011010 … From CPU … Main Memory (1KB=128Lines) 0000 010 100 0011 0000 Miss Cache (64B=8Lines) Cache Directory (Tag Memory) 8 entries X (4bit ) Write Data Write Back （Hit） 0011010 … … From CPU Main Memory (1KB=128Lines) 0011 010 100 Dirty 0011 1 Hit Cache (64B=8Lines) Cache Directory (Tag Memory) 8 entries X (4bit+1bit ) Write Data Write Back （Replace） 0000010 0011010 … … From CPU Write Back 0000 010 100 Main Memory (1KB=128Lines) Dirty 0011 10 0000 Miss Cache (64B=8Lines) Cache Directory (Tag Memory) 8 entries X (4bit+1bit ) ライトスルーとライトバック 「ライトスルーは主記憶を待たなければならないので非 効率」というのは嘘 ちゃんとライトバッファを装備すれば性能的に悪くはならない しかし、シングルライトが必要→DRAMに合わない 常にデータの一致が取れるのがメリット、観測性が高い、I/Oで 有利 ライトバック 常にデータ転送がブロック単位→DRAM、高速バスに適合 バスの利用率が下がる→マルチコアに適合 大体世の中はライトバックになりつつある リプレイスポリシー リプレイスの際、どのWayを選ぶか？ LRU (Least Recently Used) Direct map以外のキャッシュで問題になる 最近もっとも使っていない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:衝突ミス 絶対的な容量不足により起きる 容量に余裕があっても、indexが衝突することで、格納 することができなくなる Compulsory Miss (Cold Start Miss) 初期化ミス スタート時、プロセス切り替え時に最初にキャッシュに ブロックを持ってくるためのミス。避けることができない キャッシュサイズと それぞれもミスの 割合 Hennessy & Patterson Computer Architectureより ミスを減らす 容量を増やす 〇容量ミスはもちろん減る。衝突ミスも減る。 ×コストが大きくなる。ヒット時間が増える。チップ（ボード）に載らない 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に書き込み
© Copyright 2024 ExpyDoc
