作りながら学ぶコンピュータアーキテクチャ（改訂版）授業資料 テキスト141-152ページ対応 天野英晴 記憶の階層とキャッシュ 作りながら学ぶコンピュータアーキテクチャ（改訂版）授業資料　テキスト141-152ページ対応 天野英晴

記憶システムに要求される条件 高速、安価-大容量 アクセスの局所性 これらは互いに矛盾する要求 高速なものは小容量で高価 安価で大容量のものは低速 アクセスの局所性 時間的局所性(Temporal Locality):一度アクセスされたアドレスは近いうちにまたアクセスされる 空間的局所性(Special Locality):一度アクセスされた近くのアドレスは近いうちにまたアクセスされる 良く使われる命令・データを高速小容量のメモリに入れておき、ここに存在しなければ次のレベルに取りに行く →　記憶の階層

記憶の階層 CPUに近い 方から CPUと同一チップ内 CPU チップ内のRAMで作る L1キャッシュ ～64KB 1-2clock 2M～4MB 10-20clock オンボードキャッシュ SRAM（Static RAMで作る） ここまではソフトウェア からは見えない： 透過（トランスペアレント） 主記憶 4～16GB 50-100clock DRAM（Dynamic RAMで作る） OSが介在 補助記憶：ディスクが中心 １TB~　数ｍ秒かかる 最近はフラッシュメモリも台頭

メモリの基本構造 記憶要素により 性質が定まる RAM（Random Access Memory) 揮発性メモリ （電源を切ると データが消失） 　　vs. ROM(Read Only Memory) 不揮発性メモリ （電源を切っても データが残る） フラッシュROM Ｍｅｍｏｒｙ Ｃｅｌｌ Address Sense　Ａｍｐ Ｄａｔａ　Ｓｅｌｅｃｔｅｒ Ｉ／Ｏ　Ｂｕｆｆｅｒ

キャッシュメモリの実体 Static RAM 簡単なフリップフロップの形でデータを記憶 Word Bit Bit これは一例：6トランジスタ型

Multi-Core (Intel’s Nehalem-EX) CPU L3 Cache この例ではL3キャッシュ までオンチップに入って いる。 チップの容量の大きな 部分をキャッシュが占める ことに注意！ 8 CPU cores 24MB L3 cache 45nm CMOS 600 mm^2

主記憶の実体 DRAM（Dynamic RAM) 記憶はコンデンサ内の電荷によって行う リフレッシュ、プリチャージが必要 ２５６Mbit/Chipの大容量 連続転送は高速 SDRAM（Synchronous　DRAM）の普及 DDR-SDRAMの登場 DDR2 →　DDR3

DDR-ＳＤＲＡＭの読み出しタイミング CLK ～CLK Command ACT Read Address Row Column ＤＱＳ Data0 Data1 Data2 Data3

184pin DDR SDRAM Interface InfiniBand (X4,10Gbps) Connector Controller （FPGA） 　Virtex II Pro DDR SO-DIMM (256MB x 2) 184pin DDR SDRAM Interface

キャッシュ 基本的にトランスペアレント（透過） 頻繁にアクセスされるデータを入れておく小規模高速なメモリ 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、高速バスに適合 バスの利用率が下がる→マルチコアに適合 大体世の中はライトバックになりつつある

演習1 16Kワードの主記憶に２Kワードのキャッシュを設けたブロックサイズを8ワードとしたときに、以下の場合でタグメモリの構成はどのようになるかを示せ ダイレクトマップ 2-way set associative 4-way set associative

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

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