情報システム基盤学基礎１ コンピュータアーキテクチャ編 第６回 記憶階層 情報システム基盤学基礎１ コンピュータアーキテクチャ編　第６回 記憶階層 高性能コンピューティング学講座 三輪　忍 miwa@is.uec.ac.jp

情報システム基盤学基礎１ 本日の講義内容 メモリテクノロジ キャッシュ 仮想記憶

情報システム基盤学基礎１ メモリテクノロジ

コンピュータの記憶階層 レジスタ メインメモリ ディスク 高速＆小容量 SRAM（Static Random Access Memory） 情報システム基盤学基礎１ コンピュータの記憶階層 レジスタ 高速＆小容量 SRAM（Static Random Access Memory） メインメモリ 中速＆中容量 DRAM（Dynamic RAM） ディスク 低速＆大容量 SSD（Solid State Drive） や HDD（Hard Disk Drive） プロセッサ 小容量 高速 レジスタ メモリ ディスク 大容量 低速

（http://www.eetimes.com/document.asp?doc_id=1279819 より） 情報システム基盤学基礎１ SRAM ② WLを 　アサート ① BL/BLに相補的な値をセット ① WLをアサート 1 1 ⇒ 0 1 ④ WLを 　ネゲート ② 電流が 　　流れる フリップフロップ（1ビットの データを保持する論理回路） によってデータを記録 読み出し速度は ～10ns 程 実装面積が大きい 1ビットの記録に最低 6T 必要 容量は数十B～数百MB 揮発性 （電源が投入されている限り） データは失われない 電源遮断するとデータを消失 ③ 電流が 　　流れる 1 ③ BL/BLの電位差をセンス 　　アンプにより検出 [ 書き込み時の動作 ] [ 読み出し時の動作 ] フリップフロップ [ SRAM アーキテクチャ ] （http://www.eetimes.com/document.asp?doc_id=1279819 より）

（https://en.wikipedia.org/wiki/Dynamic_random-access_memory より） 情報システム基盤学基礎１ DRAM コンデンサに電荷を蓄えることによってデータを記録 読み出し速度は 30～100ns 程 実装面積が小さい 1ビットの記録を 1T1C で実現 容量は数MB～数十GB 揮発性 電源を投入していてもコンデンサに蓄えられた電荷は失われる 定期的な内容の更新（リフレッシュ）が必要 [ DRAM アーキテクチャ ] （https://en.wikipedia.org/wiki/Dynamic_random-access_memory より）

SSD フラッシュメモリを用いた記憶装置 読み出し速度は数十～100μs 程 容量は ～数百GB 不揮発性 寿命が短い 情報システム基盤学基礎１ SSD フラッシュメモリを用いた記憶装置 トランジスタの浮遊ゲートに電荷を 蓄えることによってデータを記録 注入する電荷の量を調整することで 1つのセルに複数ビット分の情報を 記録することも可能 複数セルの読み出し/書き込みを 一括して行う（NAND型の場合） 読み出し速度は数十～100μs 程 容量は ～数百GB 不揮発性 電源遮断してもデータが失われない 寿命が短い 書き換え回数に制限あり [ （NAND）フラッシュメモリの構造（上）とセルの構造 ] （https://en.wikipedia.org/wiki/Flash_memory より）

（https://en.wikipedia.org/wiki/Hard_disk_drive より） 情報システム基盤学基礎１ HDD 円盤に塗布された磁性体の向きを変えることによってデータを記録 読み出し速度は 数～数十ms 程 磁気ヘッドを移動⇒円盤を回転 　⇒データ読み出し⇒データ転送 容量は数百GB～数TB 不揮発性 [ HDDの内部構造 ] （https://en.wikipedia.org/wiki/Hard_disk_drive より） [ プラッタの構造 ]

その他の不揮発メモリ MRAM（Magnetic RAM）/STT-RAM（Spin Transfer Torque RAM） 情報システム基盤学基礎１ その他の不揮発メモリ MRAM（Magnetic RAM）/STT-RAM（Spin Transfer Torque RAM） 磁気抵抗素子の抵抗値を変えることによってデータを記録 読み出し速度は 2～20 ns 程 FeRAM（Ferroelectric RAM） 強誘電体キャパシタの分極（電荷の偏り）方向を変えることによってデータを記録 読み出し速度は 20～80 ns 程 PRAM（Phase change RAM） 相変化膜の抵抗値（結晶構造）を変化させることによってデータを記録 読み出し速度は 20～50 ns 程 ReRAM（Resistive RAM） 絶縁体の抵抗値を変化させることによってデータを記録 読み出し速度は ～50 ns 程

各メモリの諸元 × ○ SRAM DRAM SSD HDD MRAM FeRAM PRAM ReRAM リード時間 ～10ns 情報システム基盤学基礎１ 各メモリの諸元 SRAM DRAM SSD HDD MRAM FeRAM PRAM ReRAM リード時間 ～10ns 30～100ns 数十～100μs 数～ 数十ms 2～20ns 20～80ns 20～50ns ～50ns 容量 数十B～数百MB 数MB～数十GB ～数百GB 数百GB～数TB ～数MB ～数百KB 研究 段階 不揮発性 × ○ 用途 レジスタなどのon-chip メモリ メイン メモリ ディスク SRAM 代替 DRAM 代替 DRAM, SSD 代替 (2015年時点）

メモリの信頼性 メモリエラーは結構起きやすい メモリエラーはコンピュータに とって致命的 約3割のコンピュータで年1回は メモリエラーが発生 情報システム基盤学基礎１ メモリの信頼性 メモリエラーは結構起きやすい 約3割のコンピュータで年1回は メモリエラーが発生 約8%の DIMM で年1回はメモリ エラーが発生 メモリエラーはコンピュータに とって致命的 例１： 命令フェッチしてみたら不正な 　　 命令でプログラムが停止した 例２： データを読み出したら値が変化 　　　 していてプログラムが停止しな 　　　 くなった （B. Schroeder, et al., “DRAM errors in the wild: a large-scale field study”, ACM SIGMETRICS Performance Evaluation Review, Vol.37, Issue 1, 2009 より）

メモリエラーの種類 ソフトエラー ハードエラー 保持しているデータが一時的に変化した状態 情報システム基盤学基礎１ メモリエラーの種類 ソフトエラー 保持しているデータが一時的に変化した状態 主な原因： 宇宙線の衝突によってメモリセルに蓄えた電荷の乱れが発生 ハードウェアは正常なため，データを更新すればメモリは正しく動作 ほとんどのエラーはソフトエラー ハードエラー ハードウェアが物理的に壊れた状態 ハードウェアの修理・交換が必要 修理・交換するまでは，メモリのデータが正しい保証はない めったに起こらない

ECC（Error-Correcting Code）メモリ 情報システム基盤学基礎１ ECC（Error-Correcting Code）メモリ エラー検出・訂正を行うことができるメモリ ハミング符号を利用してエラー検出・訂正 一般には2ビットのエラー検出と1ビットのエラー訂正が可能 この程度のエラー検出・訂正能力があれば普通は十分

ハミング符号 パリティ ハミング符号 ECCメモリ データ内の1の数の偶奇を1ビットで表したもの 偶数個 ⇒ 0，奇数個 ⇒ 1 情報システム基盤学基礎１ ハミング符号 パリティ データ内の1の数の偶奇を1ビットで表したもの 偶数個 ⇒ 0，奇数個 ⇒ 1 ハミング符号 左から右に向かって，符号語の各ビットに1から順に番号づけ 2m（mは整数）の位置のビット ⇒ パリティ，それ以外のビット ⇒ データ 2m の位置のパリティビットは，m+1 ビット目が1となる位置のデータをチェック 例： m=0 の時は 1 ビット目が1となる位置（1, 3, 5, 7）のデータのパリティを計算 ECCメモリ ハミング符号化したデータをメモリに格納 データの読み出し時にパリティを計算 パリティに1が現れなければデータは正常 1が現れた場合はP3P2P1の位置がエラー データ パリティビット 01001100 1 00010100 [ パリティの例 ] 位置 1 2 3 4 5 6 7 P1 P2 D1 P3 D2 D3 D4 X [ ハミング符号におけるパリティビット（Pi）とデータ 　ビット（Dj）およびパリティチェック対象の関係 ]

情報システム基盤学基礎１ キャッシュ

情報システム基盤学基礎１ メインメモリとプロセッサの速度差 両者の速度差は年々拡大 最近のプロセッサではメモリアクセスが性能上のボトルネック

キャッシュ（キャッシュメモリ） 高速＆小容量のメモリ メインメモリの機能を代替 複数の階層からなる （一般に）SRAM によって構成 情報システム基盤学基礎１ キャッシュ（キャッシュメモリ） プロセッサ 小容量 高速 高速＆小容量のメモリ （一般に）SRAM によって構成 メインメモリの機能を代替 メモリ上のデータの一部を保持 メモリの代わりに高速にデータ供給 複数の階層からなる プロセッサに近い方から1次，2次，… （Level 1, Level 2, …） プロセッサに近い⇒上位，遠い⇒下位 レジスタ 1次キャッシュ 2次キャッシュ メモリ ディスク 大容量 低速

キャッシュヒットとキャッシュミス キャッシュヒット キャッシュミス アクセスしたデータがキャッシュに存在 情報システム基盤学基礎１ キャッシュヒットとキャッシュミス プロセッサ キャッシュヒット アクセスしたデータがキャッシュに存在 データ取得までの時間 　＝ キャッシュのアクセスレイテンシ キャッシュミス アクセスしたデータがキャッシュにない キャッシュミスペナルティが発生 キャッシュのアクセス時間 　＋ 下位メモリのアクセス時間 キャッシュを使用しない方が速い ① A を 要求 ② 10ns後 にデータ キャッシュ メモリ A A アクセス時間：10ns アクセス時間：100ns [ キャッシュヒット ] プロセッサ ② 10ns後 　　にミス 　　判明 ① A を 要求 ③ A を 要求 ④ 110ns後 にデータ キャッシュ メモリ A アクセス時間：10ns アクセス時間：100ns [ キャッシュミス ]

参照の局所性 時間的局所性 空間的局所性 最近アクセスしたデータは再びアクセスする可能性が高い 例： ループ変数（変数 i）へのアクセス 情報システム基盤学基礎１ 参照の局所性 時間的局所性 最近アクセスしたデータは再びアクセスする可能性が高い 例： ループ変数（変数 i）へのアクセス 空間的局所性 最近アクセスしたデータの近傍のデータは近々アクセスする可能性が高い 例： 配列（配列 a, b）へのアクセス for ( i = 0 ; i < 100 ; ++i ) s += a [ i ] * b [ i ]; [ 積和を計算するプログラム ]

キャッシュが管理するデータの単位 キャッシュブロック アドレスが連続するデータを1つのブロックとして管理 情報システム基盤学基礎１ キャッシュが管理するデータの単位 キャッシュブロック アドレスが連続するデータを1つのブロックとして管理 空間的局所性を利用するため ブロックの大きさは 32B 程度 キャッシュはブロック単位で配置/消去を行う データのアドレス： “32” “36” “40” “44” “48” “52” “56” “60” A B C D E F G H データ（4B） キャッシュブロック（32B）

メモリとキャッシュ間のマッピング ダイレクトマップ方式 セットアソシアティブ方式 フルアソシアティブ方式 格納場所はブロックごとに1箇所 情報システム基盤学基礎１ メモリとキャッシュ間のマッピング メモリ キャッシュ ダイレクトマップ方式 格納場所はブロックごとに1箇所 制御は簡単，ヒット率は低い セットアソシアティブ方式 ブロックを格納できる場所は複数の箇所（ウェイ） 制御はやや複雑，ヒット率は高め ほとんどのキャッシュはこの構成 フルアソシアティブ方式 ブロックを任意の場所に格納 ヒット率は最も高い，制御は複雑 メモリ キャッシュ メモリ キャッシュ ブロック

セットアソシアティブキャッシュの構成 = = 選択回路 アドレス ヒット/ミス ブロック 情報システム基盤学基礎１ 19b 8b 3b 2b tag index offset way0 way1 tag array data array tag array data array 1 1 set 2 2 3 3 255 255 = = 選択回路 ヒット/ミス ブロック

キャッシュの動作（ヒットする場合） = = = 選択回路 選択回路 アドレス 一致 不一致 ヒット 情報システム基盤学基礎１ 19b 8b 00・・・00 00000001 010 00 tag array data array tag array data array 1 1 1 00・・・00 A B C D E F G H 00・・・01 I J K L M N O P 2 2 3 3 255 255 = = = 一致 不一致 選択回路 選択回路 ヒット A B C D E F G H

キャッシュの動作（ミスする場合） = = = 選択回路 アドレス 不一致 不一致 ミス 情報システム基盤学基礎１ 19b 8b 3b 2b 00・・・00 00000001 010 00 tag array data array tag array data array 1 1 1 00・・・10 Q R S T U V W X 00・・・01 I J K L M N O P 2 2 3 3 255 255 = = = 不一致 不一致 選択回路 ミス

ブロックの置き換え方式 LRU（Least Recently Used）方式 LFU（Least Frequently Used）方式 情報システム基盤学基礎１ ブロックの置き換え方式 優先度 LRU（Least Recently Used）方式 参照されてから最も時間が経過した ブロックを置き換える LFU（Least Frequently Used）方式 参照回数が最少のブロックを置き換える ランダム方式 ブロックをランダムで置き換える その他にもさまざまな方式が存在 アクセス A B C D E キャッシュの状態 高 低 [ LRU方式 ] アクセス A B C D E キャッシュの状態 高 低 [ LFU方式 ]

キャッシュへの書き込み方法 ライトスルー方式 ライトバック方式 キャッシュと同時にメモリにも書き込み アクセスが完了するまでの時間が長い 情報システム基盤学基礎１ キャッシュへの書き込み方法 プロセッサ ライトスルー方式 キャッシュと同時にメモリにも書き込み アクセスが完了するまでの時間が長い キャッシュとメモリの内容は常に一致 ライトバック方式 キャッシュのみに書き込み キャッシュからブロックが追い出される時にメモリに書き込み アクセスが完了するまでの時間は短い キャッシュとメモリの内容が一致しない A を上書き キャッシュ メモリ A A A A [ ライトスルー方式 ] プロセッサ A を上書き キャッシュ メモリ A A A A [ ライトバック方式 ]

キャッシュミスの種類 初期参照ミス（compulsory miss） 容量性ミス（capacity miss） 情報システム基盤学基礎１ キャッシュミスの種類 初期参照ミス（compulsory miss） キャッシュに読み込んでいないブロックをアクセスした時に発生するミス 容量性ミス（capacity miss） 必要ブロック数がキャッシュサイズを超えることで発生するミス フルアソシアティブキャッシュでも発生 競合性ミス（conflict miss） 競合のためブロックが配置できないことによって発生するミス フルアソシアティブキャッシュでは発生しない

情報システム基盤学基礎１ キャッシュの効果 問１： メモリアクセス時間が100サイクル，キャッシュのアクセス 　　　　時間が2サイクル，ヒット率が80%の時の平均メモリアク 　　　　セス時間は？ 0.8×2＋0.2×100＝21.6 サイクル 問２： 問１のキャッシュのアクセス時間を1サイクルに短縮した 　　　場合の平均メモリアクセス時間は？ 0.8×1＋0.2×100＝20.8 サイクル 問3： 問１のキャッシュのヒット率を90%に改善した場合の平均 　　　メモリアクセス時間は？ 0.9×1＋0.1×100＝10.9 サイクル

情報システム基盤学基礎１ 仮想記憶

仮想記憶が生まれた背景 マルチタスクシステムの利便性向上 物理メモリ容量の限界の打破 メモリの管理コスト削減 セキュリティの向上 情報システム基盤学基礎１ 仮想記憶が生まれた背景 マルチタスクシステムの利便性向上 メモリの管理コスト削減 プログラマが各プロセスで使用する物理メモリを管理するのは大変 例： データを使用前にディスクから物理メモリに移動， 　　　移動先の領域が他のプロセスに使用されていないか確認，など セキュリティの向上 あるプロセスが同時に稼働する別のプロセスのデータを破壊するのを防ぐ 物理メモリ容量の限界の打破 当時（1940～50年代）は数MB程度の容量しかなく，プログラム全体を格納できなかった プログラムが格納されたディスクと物理メモリ間のデータの入れ替えをプログラム中で明示的に行っていたため，そのコストを削減したかった 物理メモリが大容量化されたため，現在はこのような状況はあまりない

仮想記憶 仮想アドレス 物理アドレス 仮想アドレスと物理アドレスのマッピングはOSとHWが協力して行う 仮想的なメモリのアドレス 情報システム基盤学基礎１ 仮想記憶 プロセスAの 仮想メモリ プロセスBの 仮想メモリ 物理メモリ 1 1 仮想アドレス 仮想的なメモリのアドレス 「仮想的なメモリ ＞ 物理メモリ」 プロセスごとに固有のアドレス空間 同じアドレスでもプロセスが違えば別データ 別プロセスのアドレス空間へのアクセスを制限 プログラムから見えるアドレス コンパイル時に各命令，各データに割り当て 物理アドレス 物理メモリのアドレス ハードウェアが実際のメモリアクセスに使用するアドレス 仮想アドレスと物理アドレスのマッピングはOSとHWが協力して行う 1 アドレス 空間 P-1 V-1 V-1 [ 仮想記憶 ]

仮想記憶とキャッシュ ディスクとメモリの関係 仮想記憶はメモリをディスクのキャッシュとして利用 容量： ディスク ≫ メモリ 情報システム基盤学基礎１ 仮想記憶とキャッシュ プロセッサ 小容量 高速 ディスクとメモリの関係 容量： ディスク ≫ メモリ レイテンシ： メモリ ≫ ディスク 仮想記憶はメモリをディスクのキャッシュとして利用 参照されやすいデータをディスクからメモリに移動 参照されにくいデータをメモリからディスクへと追い出す レジスタ （< 1ns） 1次キャッシュ （< 1ns） 2次キャッシュ （< 数十ns） メモリ （30～100ns） ディスク （数～数十ms） 大容量 低速

ページング方式 ページング方式 ページテーブル ページフォールト ページ： アドレスが連続した固定長 （4KB 程）のデータのまとまり 情報システム基盤学基礎１ ページング方式 ページ 仮想メモリ ページテーブル ページング方式 ページ： アドレスが連続した固定長 　　　　　（4KB 程）のデータのまとまり ページ単位で仮想アドレスと物理アドレスをマッピング 仮想メモリ上のページ（仮想ページ）を物理メモリ上のページ（物理ページ）に割り当て データの置き換えもページ単位で行う ページテーブル 仮想ページと物理ページの対応表 プロセスごとにメモリ上に存在 ページフォールト 要求した仮想ページが物理メモリ上に 存在しない状態 いわゆる「キャッシュミス」した状態 OSに制御を移し，要求された仮想ページに 物理ページを割り当て 物理メモリ 4K 8K 4M 16K 4M+4K 20K アクセス （ページ フォールト） [ ページング方式 ]

仮想アドレスの変換方法 仮想アドレス ページフォールト？ 物理アドレス （物理メモリの容量が1GBの場合） 情報システム基盤学基礎１ 20b 仮想ページ番号 ページ内オフセット ページテーブル 有効 ビット 物理ページ番号 1 2 3 1M-1 ページフォールト？ 物理アドレス 物理ページ番号 ページ内オフセット 18b 12b （物理メモリの容量が1GBの場合）

アドレス変換（ページが有効な場合） 仮想アドレス 有効 物理アドレス （物理メモリの容量が1GBの場合） 情報システム基盤学基礎１ 20b 00・・・001 000010000000 有効 ビット 物理ページ番号 1 00・・・010 1 1 00・・・010 2 3 1M-1 有効 物理アドレス 00・・・010 000010000000 18b 12b （物理メモリの容量が1GBの場合）

アドレス変換（ページが無効な場合） 仮想アドレス 無効（ページフォールト） 物理アドレス （物理メモリの容量が1GBの場合） 情報システム基盤学基礎１ アドレス変換（ページが無効な場合） 20b 12b 仮想アドレス 00・・・001 000010000000 有効 ビット 物理ページ番号 1 1 2 3 1M-1 無効（ページフォールト） 物理アドレス 18b 12b （物理メモリの容量が1GBの場合）

多段ページテーブル 仮想アドレス 使用アドレスの拡大にともない，ページテーブルが使用するメモリ量が問題化 情報システム基盤学基礎１ 多段ページテーブル 10b 10b 12b 仮想アドレス 仮想ページ番号（上位） 仮想ページ番号（下位） ページ内オフセット 1st レベル ページテーブル 2nd レベル ページテーブル 有効 ビット 2nd レベルページテーブルの番号 有効 ビット 1 物理ページ番号 2 3 1 2 3 1023 1023 使用アドレスの拡大にともない，ページテーブルが使用するメモリ量が問題化 ページテーブルを分割し，頻繁に使用するテーブルのみをメモリに配置することでメモリ使用量を抑制 ページフォールト？ 物理アドレス 物理ページ番号 ページ内オフセット 18b 12b （物理メモリの容量が1GBの場合）

ページの管理方法 置き換えは LRU 方式 書き込みはライトバック方式 情報システム基盤学基礎１ ページの管理方法 置き換えは LRU 方式 空き物理ページがなくなったら，参照されてから最も時間が経過したページを置き換え 書き込みはライトバック方式 メモリへの書き込みは物理ページに対してのみ行う 物理ページが追い出される時に（必要があれば）ディスクに書き戻す

TLB（Translation Lookaside Buffer） 情報システム基盤学基礎１ TLB（Translation Lookaside Buffer） プロセッサ内に存在する高速かつ小容量のメモリ 最近アドレス変換した内容をキャッシュすることによって， TLBにヒットした場合には高速なアドレス変換を実現 12b 8b 仮想ページ番号 tag index TLB tag 物理ページ番号 1 2 3 63 = TLB ヒット/ミス 物理ページ番号

情報システム基盤学基礎１ 本日のまとめ

情報システム基盤学基礎１ まとめ メモリテクノロジ キャッシュ 仮想記憶

情報システム基盤学基礎１ 次回 7/30（木） 9:00～ 「マルチコア/マルチプロセッサ」について解説