キャッシュの高速化手法と
仮想記憶
天野英晴
キャッシュの性能
キャッシュオーバーヘッド付きCPI(Clock cycles Per Instruction)=
理想のCPI +
命令キャッシュのミス率×ミスペナルティ +
データキャッシュの読み出しミス率×読み出し命令の生起確率×ミス
ペナルティ
 この式の問題点
 ミスペナルティは書き戻しを伴うかどうかで違ってくる(Write Back)
 ライトバッファの容量、連続書き込み回数によっては書き込みミスでも
ストールする
 書き込み直後に読み出しをするとキャッシュが対応できないでペナル
ティが増えることもある→ノンブロッキングキャッシュ
 実際は階層化されているのでそれぞれの階層を考えないといけない
 プロセッサがOut-of-order実行可能ならば読み出し時にストールしな
いかもしれない(この話は後ほど、、、)
 ちゃんと評価するにはシミュレータを使うしかない、、、、
ミスの原因:3つのC

Capacity Miss:容量ミス


Conflict Miss:衝突ミス


絶対的な容量不足により起きる
容量に余裕があっても、indexが衝突することで、格納
することができなくなる
Compulsory Miss (Cold Start Miss) 初期化ミス

スタート時、プロセス切り替え時に最初にキャッシュに
ブロックを持ってくるためのミス。避けることができない
キャッシュサイズと
それぞれもミスの
割合
Hennessy &
Patterson
Computer
Architectureより
ミス率を減らす


容量を増やす
〇容量ミスはもちろん減る。衝突ミスも減る。
×コストが大きくなる。ヒット時間が増える。チップ(ボード)に載らない
Way数を増やす
〇衝突ミスが減る
キャッシュ容量が小さいと効果的、2Wayは、2倍の大きさのDirect Mapと同じ
位のミス率になる
キャッシュ容量が大きい場合、残った不運な衝突ミスを減らす効果がある

×コストが大きくなる。ヒット時間が増える。4以上はあまり効果がない。
ブロックサイズを大きくする
〇局所性によりミスが減る。
×ミスペナルテイが増える。(ブロックサイズに比例はしないが、、)
キャッシュ容量が小さいと衝突ミスが増える
容量に応じて適切なブロックサイズを選ぶ。32byte-128byte
ブロックサイズと
ミスの割合
Hennessy &
Patterson
Computer
Architectureより
ブロックサイズと
平均アクセス時間
Hennessy &
Patterson
Computer
Architectureより
ミスペナルティを減らす

階層キャッシュ


ノンブロッキングキャッシュ


CPU-Memory間に複数のキャッシュを設ける
ミス処理の間にも次のアクセスを受け付ける
Critical Word FirstとEarly Restart

CPUに対して可能な限り早くアクセスされたデータ
(命令)を渡す
CPU
マルチレベル
キャッシュ
CPUに近い
方からL1,L2..
と番号を付ける
L2・L3キャッシュの
局所ミス率は
L1キャッシュより
高い
L1キャッシュ
L2キャッシュ
L3キャッシュ
主記憶
~64KB 1-2clock
~256KB 3-10clock
2M~4MB 10-20clock
4~16GB 50-100clock
マルチレベルキャッシュの制御

Multi-level Inclusion




上位階層のキャッシュが下位階層の内容を全て含む
階層間のやり取りは、キャッシューメモリ間と同じ
メモリシステム中にデータの重複が数多く存在
Multi-level Exclusion


上位階層のキャッシュと下位階層のキャッシュの内容
が重なることはない
階層間のやり取りは、リプレースというよりはスワップ
ノンブロッキングキャッシュ

キャッシュが動作中にも次のアクセスを受け付
ける




キャッシュの操作をパイプライン化する
メモリアクセスを強化しないとノンブロッキングキャッ
シュにはできない
実際はミス中のヒットを1回許せば大体OK
CPUがアウトオブオーダ実行可能でないと効果
が小さい→来週
Critical Word FirstとEarly Restart
CPU
キャッシュに転送する前に
CPUにワードを渡す
(Early Restart)
キャッシュ
主記憶
アクセスした
ワードを先に
送る
(Critical Word
First)
プリフェッチ

アクセスする前にキャッシュに取って来る
(問題点) 使うかどうか分からないデータ(命令)のために他の
ラインを追い出していいのか??
→プリフェッチバッファを使う場合が多い
 本当にアクセスされたらキャッシュに入れる


ハードウェアプリフェッチ

命令キャッシュで用いる。一つ(二つ)先のブロックまで取って来
る


命令キャッシュは局所性が高いので効果的
ソフトウェアプリフェッチ



プリフェッチ命令を使う:データキャッシュ
コンパイラが挿入
命令実行のオーバーヘッドを伴う
コンパイラによる最適化

ループ構造の最適化

ループの入れ子を入れ替える
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)
書き込み制御は当然ライトバック
仮想記憶のアドレス変換
論理アドレス空間(4GB)
ページ番号
20bit
ページ内
アドレス
12bit
物理アドレス空間(16MB)
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)の発生

TLBミス



ヒットしたがDirty bitが0のページに書き込みを
行った



ページ自体は主記憶中に存在→TLBの入れ替え
ページ自体が主記憶中にない→スワップイン+TLB
の入れ替え
Dirty bitのセット
ヒットしたが特権命令でないのに特権ページを
扱った
いずれのケースもOSで処理する
TLB変換時間の短縮

仮想アドレスキャッシュ



キャッシュは仮想アドレスで参照する
プロセスによってアドレスがダブる問題(シノニム問題)の解決
が難しい
仮想アドレスインデックス-物理アドレスタグ方式
(Virtually indexed, Physically Tagged)



変換を行わないページ内アドレスをキャッシュのインデックスに
使う
タグ参照、キャッシュ参照、TLB変換が同時に可能
Direct Mapだとキャッシュサイズが4KBに制限される


2 way だと8K、4 wayだと16K、8 wayだと32K
1次キャッシュだけの話なので、多少小さくてもいいか。。。。
仮想アドレスインデックス・物理アドレス
タグ方式
ページ番号
20bit
ページ内アドレス(12bit)
index
Tag
Mem.
TLB
12bit Tag
キャッシュ
=
Hit
CPUへ
ストレージシステム:ディスク装置
トラック:同心円状のアクセスの単位
1万-5万ある
シリンダ:ヘッドの下にある
すべてのトラックのこと
ヘッド
セクタ:512B程度に分割したアクセスの単位
100-500 セクタ番号、誤り訂正符号付きのデータを含む
磁性体の塗布された円板に
データを格納
可動式のヘッドを使って読み書き
不揮発性
容量と動作速度





2.5インチー3.5インチ
ヘッド数:2-4
容量: 100GB-1TB
平均ディスクアクセス時間=
平均シーク時間(ヘッドを動かす時間)+
平均回転待ち時間+転送時間→数msec
インタフェース




ATA(Advanced Technology Attachment)
SCSI(Small Computer Systems Interface)
ディスク内にマイクロプロセッサを装備し、アクセス時間
を最適化
ディスクキャッシュの利用
ディペンダビリティ
サービス仕様を満足
2. サービス中断
障害:1→2 復旧:2→1
信頼性(reliability): 1の連続遂行可能時間
1.
MTTF(Mean Time To Failure)
可用性(availability): 1の状態で居られる割合
MTTF/(MTTF+MTTR)
MTBF(Mean Time Between Failure)=MTTF+MTTR
ディペンダビリティを上げる→冗長性
RAID (Redundant Arrays of Inexpensive
Disks)

複数の安価なディスクを同時にアクセス




RAID 0: 冗長性なし、複数ディスクに対するアクセスの
分散(ストライピング)のみ
RAID 1: ミラーリング



アクセス速度の改善
信頼性を改善
2つ用意して同じ内容を書く
コストが高い
RAID 2: ハミングコードによるデータ修復

効率が悪く実際には使われていない
ストライピングとミラーリングの組み合わせ
RAID0+1 (RAID01)
RAID1+0 (RAID10)
RAID1
RAID0
D0
D2
D4
D6
D8
…



RAID0
RAID0
D1
D3
D5
D7
D9
…
D0
D2
D4
D6
D8
…
D1
D3
D5
D7
D9
…
RAID1
D0
D2
D4
D6
D8
…
RAID1
D0
D2
D4
D6
D8
…
ディスクドライブに対する故障耐性はRAID1+0が有利
コントローラに対する故障耐性はRAID0+1が有利
RAID1+0の方が多く使われる
D1
D3
D5
D7
D9
…
D1
D3
D5
D7
D9
…
RAID 3
A0
A4
B0
B4
C0
C4



A1
A5
B1
B5
C1
C5
A2
A6
B2
B6
C2
C6
A3
A7
B3
B7
C3
C7
P
P
P
P
P
P
データ単位に分散させ、各行に対応するParityディスクを
設ける
一つのディスクが故障しても、Parityにより復旧が可能
連続データに対してアクセスが分散されるので、ストリー
ム処理(画像データ)や科学技術計算で有利
RAID4


AI
AII
AIII
AIV
P
BI
BII
BIII
BIV
P
CI
CII
CIII
CIV
P
DI
DII
DIII
DIV
P
独立した小さな読み出し(保護グループ内に入る
読み出し)に対応するためにブロック単位でスト
ライピング
それぞれのブロックに対してパリティを設ける
RAID4とRAID3の書き込み時の動作
書き込みデータ
D0
A0
A1
A2
A3
P
書き込みデータ
D0
AI
AII
AIII
AIV
P
+
+
A0’


A1
A2
+
A3
P’
AI’
AII
AIII
AIV
P’
小さな書き込みに対して、RAID4は読み出しが1台で済む
書き込み時にParityディスクがボトルネックになる
RAID 5





AI
AII
AIII
AIV
P
BI
BII
BIII
P
BIV
CI
CII
P
CIII
CIV
DI
P
DII
DIII
DIV
Parityブロックを分散することでParityの書き込みを分散
障害時の回復は面倒
2重のデータ故障への対応→Parityを二重化(RAID6)
アクセス並列化の強化→RAID 5+0
耐故障性の強化→RAID 1+5
演習

以下の条件でキャッシュのオーバーヘッドを含めたCPIはどのように
なるか計算せよ
 理想のCPI: 1.1
 1次キャッシュのミスペナルティ:10クロック
 2次キャッシュ(統合キャッシュ)のミスペナルティ:50クロック→2次
キャッシュミス時に1次キャッシュのペナルティを加える必要はない
(Critical word First + Early restart)
 1次命令キャッシュのミス率:1%
 1次データキャッシュのリード時のミス率:3%
 2次キャッシュのローカルミス率:10%
 データ読み出し命令の生起確率:15%
 プロセッサはインオーダ実行(命令の追い越しはない)
 キャッシュはパイプライン化されており、十分なライトバッファを持って
いる
ダウンロード

パワポ資料