第6回 記憶階層

情報システム基盤学基礎1
情報システム基盤学基礎1
コンピュータアーキテクチャ編 第6回
記憶階層
高性能コンピューティング学講座
三輪 忍
[email protected]
1
情報システム基盤学基礎1
本日の講義内容
• メモリテクノロジ
• キャッシュ
• 仮想記憶
2
情報システム基盤学基礎1
メモリテクノロジ
3
情報システム基盤学基礎1
4
コンピュータの記憶階層
• レジスタ
• 高速&小容量
• SRAM(Static Random Access Memory)
• メインメモリ
• 中速&中容量
• DRAM(Dynamic RAM)
• ディスク
• 低速&大容量
• SSD(Solid State Drive) や
HDD(Hard Disk Drive)
プロセッサ
小容量 高速
レジスタ
メモリ
ディスク
大容量 低速
情報システム基盤学基礎1
SRAM
• フリップフロップ(1ビットの
データを保持する論理回路)
によってデータを記録
• 読み出し速度は ~10ns 程
② WLを ① BL/BLに相補的な値をセット
アサート
0
1
1⇒0
5
① WLをアサート
1
④ WLを
ネゲート
② 電流が
流れる
③ 電流が
流れる
[ 書き込み時の動作 ]
1
0
③ BL/BLの電位差をセンス
アンプにより検出
[ 読み出し時の動作 ]
• 実装面積が大きい
• 1ビットの記録に最低 6T 必要
• 容量は数十B~数百MB
フリップフロップ
• 揮発性
• (電源が投入されている限り)
データは失われない
• 電源遮断するとデータを消失
[ SRAM アーキテクチャ ]
(http://www.eetimes.com/document.asp?doc_id=1279819 より)
情報システム基盤学基礎1
6
DRAM
• コンデンサに電荷を蓄えることに
よってデータを記録
• 読み出し速度は 30~100ns 程
• 実装面積が小さい
• 1ビットの記録を 1T1C で実現
• 容量は数MB~数十GB
• 揮発性
• 電源を投入していてもコンデンサに
蓄えられた電荷は失われる
• 定期的な内容の更新(リフレッシュ)
が必要
[ DRAM アーキテクチャ ]
(https://en.wikipedia.org/wiki/Dynamic_random-access_memory より)
情報システム基盤学基礎1
7
SSD
• フラッシュメモリを用いた記憶装置
• トランジスタの浮遊ゲートに電荷を
蓄えることによってデータを記録
• 注入する電荷の量を調整することで
1つのセルに複数ビット分の情報を
記録することも可能
• 複数セルの読み出し/書き込みを
一括して行う(NAND型の場合)
• 読み出し速度は数十~100μs 程
• 容量は ~数百GB
• 不揮発性
• 電源遮断してもデータが失われない
• 寿命が短い
• 書き換え回数に制限あり
[ (NAND)フラッシュメモリの構造(上)とセルの構造 ]
(https://en.wikipedia.org/wiki/Flash_memory より)
情報システム基盤学基礎1
8
HDD
• 円盤に塗布された磁性体の向きを
変えることによってデータを記録
• 読み出し速度は 数~数十ms 程
• 磁気ヘッドを移動⇒円盤を回転
⇒データ読み出し⇒データ転送
[ HDDの内部構造 ]
(https://en.wikipedia.org/wiki/Hard_disk_drive より)
• 容量は数百GB~数TB
• 不揮発性
[ プラッタの構造 ]
情報システム基盤学基礎1
9
その他の不揮発メモリ
• 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 程
情報システム基盤学基礎1
10
各メモリの諸元
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
代替
DRAM,
SSD
代替
不揮発性
用途
(2015年時点)
情報システム基盤学基礎1
11
メモリの信頼性
• メモリエラーは結構起きやすい
• 約3割のコンピュータで年1回は
メモリエラーが発生
• 約8%の DIMM で年1回はメモリ
エラーが発生
• メモリエラーはコンピュータに
とって致命的
• 例1: 命令フェッチしてみたら不正な
命令でプログラムが停止した
• 例2: データを読み出したら値が変化
していてプログラムが停止しな
くなった
(B. Schroeder, et al., “DRAM errors in the wild: a large-scale field study”,
ACM SIGMETRICS Performance Evaluation Review, Vol.37, Issue 1, 2009 より)
情報システム基盤学基礎1
12
メモリエラーの種類
• ソフトエラー
• 保持しているデータが一時的に変化した状態
• 主な原因: 宇宙線の衝突によってメモリセルに蓄えた電荷の乱れが発生
• ハードウェアは正常なため,データを更新すればメモリは正しく動作
• ほとんどのエラーはソフトエラー
• ハードエラー
• ハードウェアが物理的に壊れた状態
• ハードウェアの修理・交換が必要
• 修理・交換するまでは,メモリのデータが正しい保証はない
• めったに起こらない
情報システム基盤学基礎1
13
ECC(Error-Correcting Code)メモリ
• エラー検出・訂正を行うことができるメモリ
• ハミング符号を利用してエラー検出・訂正
• 一般には2ビットのエラー検出と1ビットのエラー訂正が可能
• この程度のエラー検出・訂正能力があれば普通は十分
情報システム基盤学基礎1
14
ハミング符号
• パリティ
• データ内の1の数の偶奇を1ビットで表したもの
• 偶数個 ⇒ 0,奇数個 ⇒ 1
データ
パリティビット
01001100
1
00010100
0
[ パリティの例 ]
• ハミング符号
• 左から右に向かって,符号語の各ビットに1から順に番号づけ
• 2m(mは整数)の位置のビット ⇒ パリティ,それ以外のビット ⇒ データ
• 2m の位置のパリティビットは,m+1 ビット目が1となる位置のデータをチェック
• 例: m=0 の時は 1 ビット目が1となる位置(1, 3, 5, 7)のデータのパリティを計算
位置
• ECCメモリ
• ハミング符号化したデータをメモリに格納
• データの読み出し時にパリティを計算
• パリティに1が現れなければデータは正常
• 1が現れた場合はP3P2P1の位置がエラー
P1
P2
P3
1
2
3
4
5
6
7
P1
P2
D1
P3
D2
D3
D4
X
X
X
X
X
X
X
X
X
X
X
X
[ ハミング符号におけるパリティビット(Pi)とデータ
ビット(Dj)およびパリティチェック対象の関係 ]
情報システム基盤学基礎1
キャッシュ
15
情報システム基盤学基礎1
16
メインメモリとプロセッサの速度差
• 両者の速度差は年々拡大
• 最近のプロセッサではメモリアクセスが性能上のボトルネック
情報システム基盤学基礎1
17
キャッシュ(キャッシュメモリ)
プロセッサ
• 高速&小容量のメモリ
• (一般に)SRAM によって構成
小容量 高速
レジスタ
1次キャッシュ
• メインメモリの機能を代替
• メモリ上のデータの一部を保持
• メモリの代わりに高速にデータ供給
• 複数の階層からなる
• プロセッサに近い方から1次,2次,…
(Level 1, Level 2, …)
• プロセッサに近い⇒上位,遠い⇒下位
2次キャッシュ
メモリ
ディスク
大容量 低速
情報システム基盤学基礎1
18
キャッシュヒットとキャッシュミス
プロセッサ
• キャッシュヒット
• アクセスしたデータがキャッシュに存在
• データ取得までの時間
= キャッシュのアクセスレイテンシ
①Aを
要求
② 10ns後
にデータ
キャッシュ
メモリ
A
A
アクセス時間:10ns
アクセス時間:100ns
[ キャッシュヒット ]
• キャッシュミス
• アクセスしたデータがキャッシュにない
• キャッシュミスペナルティが発生
• キャッシュのアクセス時間
+ 下位メモリのアクセス時間
• キャッシュを使用しない方が速い
プロセッサ
①Aを
要求
② 10ns後
にミス
判明
キャッシュ
③Aを
要求
④ 110ns後
にデータ
メモリ
A
アクセス時間:10ns
アクセス時間:100ns
[ キャッシュミス ]
情報システム基盤学基礎1
19
参照の局所性
• 時間的局所性
• 最近アクセスしたデータは再びアクセス
する可能性が高い
• 例: ループ変数(変数 i)へのアクセス
• 空間的局所性
• 最近アクセスしたデータの近傍のデータ
は近々アクセスする可能性が高い
• 例: 配列(配列 a, b)へのアクセス
for ( i = 0 ; i < 100 ; ++i )
s += a [ i ] * b [ i ];
[ 積和を計算するプログラム ]
情報システム基盤学基礎1
20
キャッシュが管理するデータの単位
• キャッシュブロック
• アドレスが連続するデータを1つのブロックとして管理
• 空間的局所性を利用するため
• ブロックの大きさは 32B 程度
• キャッシュはブロック単位で配置/消去を行う
データのアドレス:
“32”
“36”
“40”
“44”
“48”
“52”
“56”
“60”
A
B
C
D
E
F
G
H
データ(4B)
キャッシュブロック(32B)
情報システム基盤学基礎1
21
メモリとキャッシュ間のマッピング
• ダイレクトマップ方式
• 格納場所はブロックごとに1箇所
• 制御は簡単,ヒット率は低い
• セットアソシアティブ方式
• ブロックを格納できる場所は複数
の箇所(ウェイ)
• 制御はやや複雑,ヒット率は高め
• ほとんどのキャッシュはこの構成
メモリ
キャッシュ
メモリ
キャッシュ
メモリ
• フルアソシアティブ方式
• ブロックを任意の場所に格納
• ヒット率は最も高い,制御は複雑
キャッシュ
ブロック
情報システム基盤学基礎1
22
セットアソシアティブキャッシュの構成
19b
8b
3b
tag
index
offset
アドレス
way0
tag array
0
1
2
3
data array
way1
set
255
2b
tag array
0
1
2
3
255
=
=
選択回路
ヒット/ミス
ブロック
data array
情報システム基盤学基礎1
23
キャッシュの動作(ヒットする場合)
アドレス
19b
8b
3b
2b
00・・・00
00000001
010
00
tag array
0
1
2
3
00・・・00
tag array
data array
A
B
C
D
E
F
G
0
1
2
3
H
255
data array
00・・・01
I
=
不一致
J
255
=
一致
選択回路
ヒット
A
B
C
D
E
F
G
H
K
L
M N
O
P
情報システム基盤学基礎1
24
キャッシュの動作(ミスする場合)
アドレス
19b
8b
3b
2b
00・・・00
00000001
010
00
tag array
0
1
2
3
00・・・10
tag array
data array
Q
R
255
S
T
U
V W X
0
1
2
3
data array
00・・・01
I
=
不一致
J
255
=
不一致
選択回路
ミス
K
L
M N
O
P
情報システム基盤学基礎1
25
ブロックの置き換え方式
• LRU(Least Recently Used)方式
• 参照されてから最も時間が経過した
ブロックを置き換える
優先度
アクセス A B C D B C B E C D A B
ABCDBCBECDAB
キャッシュ
の状態
ABCDBCBECDA
ABCDDCBECD
AAAADDBEC
• LFU(Least Frequently Used)方式
• 参照回数が最少のブロックを置き換える
[ LRU方式 ]
アクセス A B C D B C B E C D A B
• ランダム方式
• ブロックをランダムで置き換える
低
高
ABCDBCBBCCCB
キャッシュ
の状態
ABCDBCCBBBC
ABCDDDDDDD
AAAAEEEAA
• その他にもさまざまな方式が存在
高
[ LFU方式 ]
低
情報システム基盤学基礎1
26
キャッシュへの書き込み方法
プロセッサ
• ライトスルー方式
• キャッシュと同時にメモリにも書き込み
• アクセスが完了するまでの時間が長い
• キャッシュとメモリの内容は常に一致
• ライトバック方式
• キャッシュのみに書き込み
• キャッシュからブロックが追い出される
時にメモリに書き込み
• アクセスが完了するまでの時間は短い
• キャッシュとメモリの内容が一致しない
A を上書き
キャッシュ
メモリ
A
A
[ ライトスルー方式 ]
プロセッサ
A を上書き
キャッシュ
A
メモリ
A
[ ライトバック方式 ]
情報システム基盤学基礎1
27
キャッシュミスの種類
• 初期参照ミス(compulsory miss)
• キャッシュに読み込んでいないブロックをアクセスした時に発生するミス
• 容量性ミス(capacity miss)
• 必要ブロック数がキャッシュサイズを超えることで発生するミス
• フルアソシアティブキャッシュでも発生
• 競合性ミス(conflict miss)
• 競合のためブロックが配置できないことによって発生するミス
• フルアソシアティブキャッシュでは発生しない
情報システム基盤学基礎1
28
キャッシュの効果
• 問1: メモリアクセス時間が100サイクル,キャッシュのアクセス
時間が2サイクル,ヒット率が80%の時の平均メモリアク
セス時間は?
• 0.8×2+0.2×100=21.6 サイクル
• 問2: 問1のキャッシュのアクセス時間を1サイクルに短縮した
場合の平均メモリアクセス時間は?
• 0.8×1+0.2×100=20.8 サイクル
• 問3: 問1のキャッシュのヒット率を90%に改善した場合の平均
メモリアクセス時間は?
• 0.9×1+0.1×100=10.9 サイクル
情報システム基盤学基礎1
仮想記憶
29
情報システム基盤学基礎1
30
仮想記憶が生まれた背景
• マルチタスクシステムの利便性向上
• メモリの管理コスト削減
• プログラマが各プロセスで使用する物理メモリを管理するのは大変
• 例: データを使用前にディスクから物理メモリに移動,
移動先の領域が他のプロセスに使用されていないか確認,など
• セキュリティの向上
• あるプロセスが同時に稼働する別のプロセスのデータを破壊するのを防ぐ
• 物理メモリ容量の限界の打破
• 当時(1940~50年代)は数MB程度の容量しかなく,プログラム全体を
格納できなかった
• プログラムが格納されたディスクと物理メモリ間のデータの入れ替えを
プログラム中で明示的に行っていたため,そのコストを削減したかった
• 物理メモリが大容量化されたため,現在はこのような状況はあまりない
情報システム基盤学基礎1
仮想記憶
プロセスAの
仮想メモリ
プロセスBの
仮想メモリ
0
1
• 仮想アドレス
• 仮想的なメモリのアドレス
• 「仮想的なメモリ > 物理メモリ」
31
0
1
物理メモリ
0
1
アドレス
空間
• プロセスごとに固有のアドレス空間
• 同じアドレスでもプロセスが違えば別データ
• 別プロセスのアドレス空間へのアクセスを制限
• プログラムから見えるアドレス
P-1
V-1
• コンパイル時に各命令,各データに割り当て
V-1
[ 仮想記憶 ]
• 物理アドレス
• 物理メモリのアドレス
• ハードウェアが実際のメモリアクセスに使用するアドレス
• 仮想アドレスと物理アドレスのマッピングはOSとHWが協力して行う
情報システム基盤学基礎1
32
仮想記憶とキャッシュ
プロセッサ
• ディスクとメモリの関係
• 容量: ディスク ≫ メモリ
• レイテンシ: メモリ ≫ ディスク
• 仮想記憶はメモリをディスクの
小容量 高速
レジスタ
(< 1ns)
1次キャッシュ
(< 1ns)
2次キャッシュ
(< 数十ns)
キャッシュとして利用
• 参照されやすいデータをディスク
からメモリに移動
• 参照されにくいデータをメモリから
ディスクへと追い出す
メモリ
(30~100ns)
ディスク
(数~数十ms)
大容量 低速
情報システム基盤学基礎1
33
ページング方式
ページ
ページテーブル
仮想メモリ
• ページング方式
• ページ: アドレスが連続した固定長
(4KB 程)のデータのまとまり
• ページ単位で仮想アドレスと物理アドレスを
マッピング
0
物理メモリ
0
4K
8K
• 仮想メモリ上のページ(仮想ページ)を物理メモリ
上のページ(物理ページ)に割り当て
• データの置き換えもページ単位で行う
• ページテーブル
• 仮想ページと物理ページの対応表
• プロセスごとにメモリ上に存在
16K
4M
4M+4K
アクセス
(ページ
フォールト)
20K
• ページフォールト
• 要求した仮想ページが物理メモリ上に
存在しない状態
• いわゆる「キャッシュミス」した状態
• OSに制御を移し,要求された仮想ページに
物理ページを割り当て
[ ページング方式 ]
情報システム基盤学基礎1
34
仮想アドレスの変換方法
仮想アドレス
20b
12b
仮想ページ番号
ページ内オフセット
ページテーブル
有効
ビット
物理ページ番号
0
1
2
3
1M-1
ページフォールト?
物理アドレス
物理ページ番号
ページ内オフセット
18b
12b
(物理メモリの容量が1GBの場合)
情報システム基盤学基礎1
35
アドレス変換(ページが有効な場合)
仮想アドレス
有効
ビット
0
1
2
3
1
20b
12b
00・・・001
000010000000
物理ページ番号
00・・・010
1M-1
有効
物理アドレス
00・・・010
18b
000010000000
12b
(物理メモリの容量が1GBの場合)
情報システム基盤学基礎1
36
アドレス変換(ページが無効な場合)
仮想アドレス
有効
ビット
0
1
2
3
20b
12b
00・・・001
000010000000
物理ページ番号
0
1M-1
無効(ページフォールト)
物理アドレス
18b
12b
(物理メモリの容量が1GBの場合)
情報システム基盤学基礎1
37
多段ページテーブル
10b
仮想アドレス
有効 2nd レベルページ
ビット テーブルの番号
仮想ページ番号(上位) 仮想ページ番号(下位)
1st レベル
ページテーブル
0
1
2
3
12b
10b
ページ内オフセット
2nd レベル
ページテーブル
有効
ビット
物理ページ番号
0
1
2
3
1023
1023
使用アドレスの拡大にともない,ページ
テーブルが使用するメモリ量が問題化
• ページテーブルを分割し,頻繁に使用
するテーブルのみをメモリに配置する
ことでメモリ使用量を抑制
ページフォールト?
物理アドレス
物理ページ番号
ページ内オフセット
18b
12b
(物理メモリの容量が1GBの場合)
情報システム基盤学基礎1
38
ページの管理方法
• 置き換えは LRU 方式
• 空き物理ページがなくなったら,参照されてから最も時間が経過した
ページを置き換え
• 書き込みはライトバック方式
• メモリへの書き込みは物理ページに対してのみ行う
• 物理ページが追い出される時に(必要があれば)ディスクに書き戻す
情報システム基盤学基礎1
39
TLB(Translation Lookaside Buffer)
• プロセッサ内に存在する高速かつ小容量のメモリ
• 最近アドレス変換した内容をキャッシュすることによって,
TLBにヒットした場合には高速なアドレス変換を実現
仮想ページ番号
12b
8b
tag
index
TLB
tag
物理ページ番号
0
1
2
3
63
=
TLB ヒット/ミス
物理ページ番号
情報システム基盤学基礎1
本日のまとめ
40
情報システム基盤学基礎1
まとめ
• メモリテクノロジ
• キャッシュ
• 仮想記憶
41
情報システム基盤学基礎1
次回
• 7/30(木) 9:00~
• 「マルチコア/マルチプロセッサ」について解説
42