記憶の階層とキャッシュ 天野英晴

記憶システム 膨大な容量を持ち、アクセス時間（読み出し、書き込み）が短いメモリが欲しい！ しかし 容量の大きい（ビット単価が安い）メモリは遅い 高速なメモリは容量が小さい お金にモノを言わせて高速なメモリをたくさん揃えても大容量化の段階で遅くなってしまう そこでアクセスの局所性(Locality)を利用 時間的局所性(Temporal Locality) 一度アクセスされたアドレスは近いうちにまたアクセスされる 空間的局所性(Special Locality) 一度アクセスされたアドレスに近い場所がまたアクセスされる

記憶の階層 ソフトウェアから は透過 CPU （トランスペアレント） チップ内メモリ L1キャッシュ ～64KB 1-2clock 高速小容量の CPUの近くに置き よく使うデータを入れておく そこになければより遅い 大容量メモリに取りに行く チップ内メモリ L1キャッシュ ～64KB　1-2clock L2キャッシュ ～256KB 3-10clock L3キャッシュ SRAM 2M～4MB 10-20clock 主記憶 DRAM 4～16GB 50-100clock OSが管理 補助記憶　（2次記憶） μ-msecオーダー 数百GB

半導体メモリの分類 RAM （RWM)： 揮発性メモリ ROM(Read Only Memory)：不揮発性メモリ 電源を切ると内容が消滅 SRAM(Static　RAM) DRAM(Dynamic　RAM) ROM(Read Only Memory)：不揮発性メモリ 電源を切っても内容が保持 Mask ROM 書き換え不能 PROM(Programmable ROM)　プログラム可 One Time PROM　一回のみ書き込める Erasable PROM　消去、再書き込み可能 UV EPROM　（紫外線消去型） EEPROM （電気的消去可能型）　フラッシュメモリ

ＲＡＭの容量 アドレス 本数 容量 省略した言い方 ８ ２５６ 10 1024 1K 12 4096 4K 16 65536 64K 18 262144 256K 20 1048576 1M 24 16777216 16M 28 26835456 256M 30 1073741824 1G 32 4204067296 4G 深さ×幅 右の表に幅を掛ければ全体の容量が出る 省略した言い方でも十分（端数を覚えている人は少ない）

SRAM (Static RAM) 非同期式SRAM 古典的なＳＲＡＭ クロックを用いない 現在も低電力SRAMシリーズなどで用いられる 連続転送機能を強化したSSRAM　(Synchronous　SRAM）が登場、高速大容量転送に用いられる 8Mbit/Chip-６４Mbit/Chip程度 TSOP (Thin Small Outline Package)やBGA(Ball Grid Array)を利用

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

DDR-SDRAMカードの例 下は１GBでやや小さい。今は４GB－８GBのカードが良く使われる

SDR (Single Data Rate) ＳＤＲＡＭ：同期式ＤＲＡＭ １００ＭＨｚ－１３３ＭＨｚの高速クロックに同期した読み・書きを行う CS,RAS,CAS,WEなどの制御線の組み合わせでコマンドを構成 コマンドにより、同期式に読み、書き、リフレッシュ等を制御 バンクの切り替えにより連続読み・書きが高速に可能

SDR-ＳＤＲＡＭの読み出しタイミング CLK Command ACT Read Address Row Column Data0

DDR (Double Data Rate) ＳＤＲＡＭ：同期式ＤＲＡＭ SDR SDRAM同様の高速周波数（１００ＭＨｚ－１３３ＭＨｚ）のクロックの両エッジで転送を行うことにより、倍のデータ転送レートを実現 差動クロックを利用 データストローブ信号によりタイミング調整 より豊富なコマンド

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

DRAMのまとめ SRAMの4倍程度集積度が大 使い難いが、連続アクセスは高速 転送はますますパケット化する傾向にある SDR-SDRAM→　DDR-SDRAM→DDR2-SDRAM DDR2: 800Mbps (400MHz両エッヂ）　2Gbit /Chip DDR3: 1600Mbps (800MHz両エッヂ）　4Gbit /Chip パッケージ：FBGA(Fine pitch Ball Grid Array)の利用 SO-DIMM(Small outline Dual dual in-line memory module)の形で供給される：　8GByte/DIMM 現在PC用にはDDR3が標準となる プリフェッチ機能→　連続転送可能 １．５V電源、電気的特性の改善 DDR-4が準備中 制御は複雑、高速なため取り扱いもたいへん →　IP( Intellectual Property)の利用が進む

フラッシュメモリ EEPROM型の発展：小型化のために選択ゲートを用いず、ブロック単位で消去を行う. NOR型、NAND型、DINOR型、AND型等様々な構成法がある. オンチップ用：高速消去可能NOR型　1Gbit程度まで 単独読み出しが可能、消去が高速 ファイルストレージ用：大容量のNAND型　1Gbit- 128Gbit/チップ 連続読み出し、消去はミリ秒オーダー掛かる SDメモリカード・SDHCメモリカードなど、8GB-32GBが使われる 書き換え回数に制限がある

ストレージシステム：ディスク装置 トラック：同心円状のアクセスの単位 １万-５万ある シリンダ：ヘッドの下にある すべてのトラックのこと 磁性体の塗布された円板に データを格納 可動式のヘッドを使って読み書き 不揮発性 セクタ：512B程度に分割したアクセスの単位 100-500　セクタ番号、誤り訂正符号付きのデータを含む

容量と動作速度 2.5インチー3.5インチ ヘッド数：2-4 容量： １００GB-1TB 平均ディスクアクセス時間＝ 　　平均シーク時間（ヘッドを動かす時間）＋ 　　平均回転待ち時間＋転送時間→数msec インタフェース ATA(Advanced Technology Attachment) SCSI(Small Computer Systems 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 =

タグメモリの設計法 キャッシュ内に何ブロック入るかを計算する。 ２のn乗である時 インデックスはnbitとなる メモリ内に何ブロック入るかを計算する。 ２のh乗である時 タグはh-n=mbitとなる ダイレクトマップでは幅m,深さ2のn乗のタグメモリが必要 2-way set associativeは、インデックスが1bit減り深さが半分となり、タグが1bitを増える。しかしこれがダブルで必要 way数が倍になる度にインデックスが1bit減り、深さが半分になり、タグが1bit増え、タグ自体が倍になる。

書き込みポリシー 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より

ブロックサイズと 平均アクセス時間 Hennessy & Patterson Computer Architectureより

ミスペナルティを減らす 階層キャッシュ ノンブロッキングキャッシュ Critical Word FirstとEarly Restart CPU－Memory間に複数のキャッシュを設ける ノンブロッキングキャッシュ ミス処理の間にも次のアクセスを受け付ける Critical Word FirstとEarly Restart CPUに対して可能な限り早くアクセスされたデータ（命令）を渡す

マルチレベル キャッシュ CPUに近い 方からL1,L2.. と番号を付ける L2・L3キャッシュの 局所ミス率は L1キャッシュより 高い ～64KB　1-2clock L2キャッシュ ～256KB 3-10clock L3キャッシュ 2M～4MB 10-20clock 主記憶 4～16GB 50-100clock

マルチレベルキャッシュの制御 Multi-level Inclusion Multi-level Exclusion 上位階層のキャッシュが下位階層の内容を全て含む 階層間のやり取りは、キャッシューメモリ間と同じ メモリシステム中にデータの重複が数多く存在 Multi-level Exclusion 上位階層のキャッシュと下位階層のキャッシュの内容が重なることはない 階層間のやり取りは、リプレースというよりはスワップ

ノンブロッキングキャッシュ キャッシュが動作中にも次のアクセスを受け付ける CPUがアウトオブオーダ実行可能でないと効果が小さい→来年 キャッシュの操作をパイプライン化する メモリアクセスを強化しないとノンブロッキングキャッシュにはできない 実際はミス中のヒットを1回許せば大体OK CPUがアウトオブオーダ実行可能でないと効果が小さい→来年

Critical Word FirstとEarly Restart CPU キャッシュに転送する前に CPUにワードを渡す （Early Restart) キャッシュ アクセスした ワードを先に 送る （Critical Word Firsｔ） 主記憶

プリフェッチ アクセスする前にキャッシュに取って来る ハードウェアプリフェッチ ソフトウェアプリフェッチ (問題点)　使うかどうか分からないデータ（命令）のために他のラインを追い出していいのか？？ →プリフェッチバッファを使う場合が多い 本当にアクセスされたらキャッシュに入れる ハードウェアプリフェッチ 命令キャッシュで用いる。一つ（二つ）先のブロックまで取って来る 命令キャッシュは局所性が高いので効果的 ソフトウェアプリフェッチ プリフェッチ命令を使う：データキャッシュ コンパイラが挿入 命令実行のオーバーヘッドを伴う

コンパイラによる最適化 ループ構造の最適化 ブロック化 科学技術計算には効果的 ループの入れ子を入れ替える ループをくっつける キャッシュにうまく入るようにデータ構造を変更する 科学技術計算には効果的 for(j=0; j<100; j=j+1) for(i=0; i<5000; i=i+1) x[i][j] = a * x[i][j]; for(i=0; i<5000; i=i+1) for(j=0; j<100; j=j+1) x[i][j] = a * x[i][j];

仮想記憶（Virtual Memory) プロセッサから見たアドレス（論理アドレス）と実際のメモリ上のアドレス（物理アドレス）を分離する 実メモリよりも大きいメモリを扱うことができる 複数のプロセスを互いのアドレスを気にせずに並行実行可能 管理単位で記憶の保護 ページ：固定サイズ(4K-16KB)　 vs. セグメント：可変サイズ→ページを用いる場合が多い 概念はキャッシュに似ているがOSが管理、用語も違う ブロック(ライン)：32-128B　⇔　ページ:4KB リプレイス　　スワップイン ライトバック　⇔　スワップアウト ページの割り付けはOSが管理 リプレイスはLRU(Least Recently Used) 書き込み制御は当然ライトバック

仮想記憶のアドレス変換 論理アドレス空間（４GB) ページ番号 ページ内 アドレス 物理アドレス空間（16MB) 20bit 12bit TLB 12bit 12bit 20bit→12bitの変換テーブルは巨大 ソフトウェアで管理 TLB(Translation Lookaside Buffer)はこの変換テーブルに 対するキャッシュ

TLB(Translation Lookaside Buffer) 論理アドレス ページ番号 ページ内アドレス 00110101011100000010 001011001100 Dirty bit Priority bit = = 00110101011100000010 = 111011001110 = = = = 物理アドレス = 111011001110 001011001100

ページフォルト（Page Fault)の発生 3年のコンピュータアーキテクチャ、OSの授業で学ぶ例外処理の一つ TLBミス ページ自体は主記憶中に存在→TLBの入れ替え ページ自体が主記憶中にない→スワップイン＋TLBの入れ替え ヒットしたがDirty bitが0のページに書き込みを行った Dirty bitのセット ヒットしたが特権命令でないのに特権ページを扱った いずれのケースもOSで処理する

TLB変換時間の短縮 仮想アドレスキャッシュ 仮想アドレスインデックス-物理アドレスタグ方式 キャッシュは仮想アドレスで参照する プロセスによってアドレスがダブる問題（シノニム問題）の解決が難しい 仮想アドレスインデックス-物理アドレスタグ方式 　　(Virtually indexed, Physically Tagged) 変換を行わないページ内アドレスをキャッシュのインデックスに使う タグ参照、キャッシュ参照、TLB変換が同時に可能 Direct Mapだとキャッシュサイズが4KBに制限される 2 way だと8K、4 wayだと16K、8 wayだと32K １次キャッシュだけの話なので、多少小さくてもいいか。。。。

仮想アドレスインデックス・物理アドレスタグ方式 ページ番号 ページ内アドレス(12bit) 20bit index Tag Mem. キャッシュ TLB = 12bit Tag Hit CPUへ

演習1 0x00番地からサイズ8の配列A[i]が、0x40番地から同じくサイズ8の配列B[i]が割り付けられている。 enshu.asmは以下を計算するプログラムである int i,dsum; dsum =0; for(i=0; i<8;i++) dsum += B[i]-A[i]; これをダイレクトマップのキャッシュ（direct)で実行したときと２ウェイセットアソシアティブ（2way)で実行したときで、両者のミスの回数と、演算結果が出るまでのクロック数（pcがｃ番地になったら終了と考えよう）をシミュレーションして求めよ。

演習2 64kワードの主記憶に対して4kワードのキャッシュを設ける ブロックサイズは16ワードとする ダイレクトマップ、2way set associative、4way set associativeキャッシュのタグメモリ構成をそれぞれ示せ ヒント：タグメモリの設計法のページを参照！

演習３ あるキャッシュのブロックにマップされた互いに衝突するアドレスA,Bに対して以下のアクセスを順に行う。 Aから読み出し Bから読み出し ダイレクトライト型のライトスルーキャッシュ、ライトバックキャッシュについて、それぞれのアクセスがミスするかヒットするかを示せ。また、各アクセスによってメモリに対してどのような操作（リプレイスR、ライトバックWB、ライトスルーの書き込みWTH）が必要か？ライトバックについてはブロックはC、Dのうちどちらの状態になるか？