作りながら学ぶコンピュータアーキテクチャ（改訂版）授業資料 テキスト ページ対応 天野英晴

Presentation on theme: "作りながら学ぶコンピュータアーキテクチャ（改訂版）授業資料 テキスト ページ対応 天野英晴"— Presentation transcript:

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

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

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

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

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

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

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

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

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

10 キャッシュ 基本的にトランスペアレント（透過） 頻繁にアクセスされるデータを入れておく小規模高速なメモリ
CacheであってCashではないので注意 元々はコンピュータの主記憶に対するものだが、IT装置の色々なところに使われるようになった ディスクキャッシュ、ページキャッシュ..etc.. 当たる(ヒット）、はずれる（ミスヒット） ミスヒットしたら、下のメモリ階層から取ってきて入れ替える(リプレイス） 基本的にトランスペアレント（透過） ソフトウェアからはヒットしたかミスしたかは分からない ヒットすれば早くなり、ミスすれば遅い 全てをハードウェアが管理する必要がある→もちろんキャッシュを意識すればソフトウェアで高速化は可能（プリフェッチ命令、データの配置） マッピング（割り付け） 主記憶とキャッシュのアドレスを高速に対応付ける Direct map　⇔　Full associative cache 書き込みポリシー ライトスルー、ライトバック リプレイス（追い出し）ポリシー LRU　(Least Recently Used)

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

12 … Direct Map のアドレス 割り付け 主記憶：1024ワード ブロックサイズ：8ワード キャッシュ：64ワード =8ブロック
　　　　… 　　　　… 　　　　… 　　　　… 　　　　… 　　　　… 　　　　… 　　　　… 　　　　… 　　　　… 　　　　… 　　　　… 　　　　… … Direct Map のアドレス 割り付け 主記憶：1024ワード ブロックサイズ：8ワード キャッシュ：64ワード 　　　　　　　=8ブロック 000 001 010 011 100 101 110 111 Index Tag （Key) 　　　　… ブロック内 アドレス

13 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 ) ディレクトリは小さくて済む

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

15 … 2-way set associative のアドレス 割り付け 00 01 10 11 Index Tag （Key) キャッシュ内
　　　　… 　　　　… 　　　　… 　　　　… 　　　　… 　　　　… 　　　　… 　　　　… 　　　　… 　　　　… 　　　　… 　　　　… 　　　　… … 2-way set associative のアドレス 割り付け 00 01 10 11 Index Tag （Key) 　　　　… キャッシュ内 アドレス

16 2-way set associative Map
From CPU 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

17 2-way set associative Map
From CPU 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が減る

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

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

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

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

22 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 )

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

24 Write Through （Miss：Fetch on Write）
… … 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 )

25 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 )

26 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 )

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

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

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

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