パワポ資料:cache

Report
記憶の階層とキャッシュ
天野英晴
記憶システム
膨大な容量を持ち、アクセス時間(読み出し、書き込み)
が短いメモリが欲しい!
しかし



容量の大きい(ビット単価が安い)メモリは遅い
高速なメモリは容量が小さい
お金にモノを言わせて高速なメモリをたくさん揃えても大容量化の段
階で遅くなってしまう

そこでアクセスの局所性(Locality)を利用

時間的局所性(Temporal Locality)


一度アクセスされたアドレスは近いうちにまたアクセスされる
空間的局所性(Special Locality)

一度アクセスされたアドレスに近い場所がまたアクセスされる
CPU
記憶の階層
高速小容量の
CPUの近くに置き
よく使うデータを入れておく
L1キャッシュ
ソフトウェアから
は透過
(トランスペアレント)
チップ内メモリ
~64KB 1-2clock
L2キャッシュ
~256KB 3-10clock
L3キャッシュ
SRAM
2M~4MB 10-20clock
そこになければより遅い
大容量メモリに取りに行く
主記憶
DRAM
OSが管理
4~16GB 50-100clock
補助記憶 (2次記憶)
μ-msecオーダー
数百GB
半導体メモリの分類

RAM (RWM): 揮発性メモリ




電源を切ると内容が消滅
SRAM(Static RAM)
DRAM(Dynamic RAM)
ROM(Read Only Memory):不揮発性メモリ



電源を切っても内容が保持
Mask ROM 書き換え不能
PROM(Programmable ROM) プログラム可
 One Time PROM 一回のみ書き込める
 Erasable PROM 消去、再書き込み可能


UV EPROM (紫外線消去型)
EEPROM (電気的消去可能型) フラッシュメモリ
容量



深さ×幅
右の表に幅を掛
ければ全体の
容量が出る
省略した言い方
でも十分(端数
を覚えている人
は少ない)
アドレス
本数
8
10
12
16
18
20
24
28
容量
省略した言
い方
256
1024
4096
65536
256
1K
4K
64K
256K
1M
16M
256M
30
32
1073741824
262144
1048576
16777216
26835456
4204067296
1G
4G
SRAM (Static RAM)

非同期式SRAM




古典的なSRAM
クロックを用いない
現在も低電力SRAMシリーズなどで用いられる
連続転送機能を強化したSSRAM (Synchronous
SRAM)が登場、高速大容量転送に用いられる


8Mbit/Chip-64Mbit/Chip程度
TSOP (Thin Small Outline Package)やBGA(Ball Grid
Array)を利用
DRAM(Dynamic RAM)






記憶はコンデンサ内の電荷によって行う
リフレッシュ、プリチャージが必要
256Mbit/Chipの大容量
連続転送は高速
SDRAM(Synchronous DRAM)の普及
DDR-SDRAMの登場


DDR2 → DDR3
DDR4、HMC(Hybrid Memory Cube)が準備中
DDR-SDRAMカードの例

下は1GBでやや小さい。今は4GB-8GBの
カードが良く使われる
SDR (Single Data Rate)
SDRAM:同期式DRAM




100MHz-133MHzの高速クロックに同期し
た読み・書きを行う
CS,RAS,CAS,WEなどの制御線の組み合わせ
でコマンドを構成
コマンドにより、同期式に読み、書き、リフレッ
シュ等を制御
バンクの切り替えにより連続読み・書きが高速に
可能
SDR-SDRAMの読み出しタイミング
CLK
Command
ACT
Read
Row
Column
Address
Data0
Data1
Data2
Data3
DDR (Double Data Rate)
SDRAM:同期式DRAM




SDR SDRAM同様の高速周波数(100MHz-
133MHz)のクロックの両エッジで転送を行うこ
とにより、倍のデータ転送レートを実現
差動クロックを利用
データストローブ信号によりタイミング調整
より豊富なコマンド
DDR-SDRAMの読み出しタイミン
グ
CLK
~CLK
Command
ACT
Read
Row
Column
Address
DQS
Data0Data1Data2Data3
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が標準となる


DDR-4が準備中
制御は複雑、高速なため取り扱いもたいへん
→ IP( Intellectual Property)の利用が進む


プリフェッチ機能→ 連続転送可能
1.5V電源、電気的特性の改善
フラッシュメモリ


EEPROM型の発展:小型化のために選択ゲートを用いず、ブロック
単位で消去を行う.
NOR型、NAND型、DINOR型、AND型等様々な構成法がある.
 オンチップ用:高速消去可能NOR型 1Gbit程度まで


単独読み出しが可能、消去が高速
ファイルストレージ用:大容量のNAND型 1Gbit- 128Gbit/チップ



連続読み出し、消去はミリ秒オーダー掛かる
SDメモリカード・SDHCメモリカードなど、8GB-32GBが使われる
書き換え回数に制限がある
ストレージシステム:ディスク装置
トラック:同心円状のアクセスの単位
1万-5万ある
シリンダ:ヘッドの下にある
すべてのトラックのこと
ヘッド
セクタ:512B程度に分割したアクセスの単位
100-500 セクタ番号、誤り訂正符号付きのデータを含む
磁性体の塗布された円板に
データを格納
可動式のヘッドを使って読み書き
不揮発性
容量と動作速度





2.5インチー3.5インチ
ヘッド数:2-4
容量: 100GB-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)を使う


やや小さい
順番に割り付けていって1周したら、元に戻る

キャッシュのブロック数(セット数)が2のn乗、ブロック
サイズが2のm乗とすると、、、
残り
n
タグ (キー) インデックス
m
ブロック内アドレス
0000000000
…
0000000111
0000010000
…
0000010111
0000001000
…
0000001111
0000100000
…
0000100111
0000011000
…
0000011111
0000110000
…
0000110111
0000101000
…
0000101111
0001000000
…
0001000111
0000111000
…
0000111111
0001010000
…
0001010111
0001001000
…
0001001111
1111111000
…
1111111111
1111110000
…
1111110111
…
Direct Map
のアドレス
割り付け
主記憶:1024ワード 000 001 010 011 100 101 110 111
Index
ブロックサイズ:8ワード
Tag
0000101000
キャッシュ:64ワード
ブロック内
…
(Key)
=8ブロック
0000101111
アドレス
Direct Map
From CPU
0011010
0011 010 100
…
…
Main Memory
(1KB=128Lines)
010
Yes:Hit
=
Data
010
0011
Cache
(64B=8Lines)
Cache Directory
(Tag Memory)
8 entries X (4bit )
ディレクトリは小さくて済む
Direct Map (Conflict Miss)
From CPU
0000010
0000 010 100
…
…
Main Memory
010
No: Miss Hit
=
010
0011
0000
Cache
Cache Directory
(Tag Memory)
010を共通するキャッシュラインは
Conflict Missを起こす
0000000000
…
0000000111
0000010000
…
0000010111
0000001000
…
0000001111
0000100000
…
0000100111
0000011000
…
0000011111
0000110000
…
0000110111
0000101000
…
0000101111
0001000000
…
0001000111
0000111000
…
0000111111
0001010000
…
0001010111
0001001000
…
0001001111
1111111000
…
1111111111
1111110000
…
1111110111
…
2-way set associative
のアドレス
割り付け
00
01
Tag
(Key)
10
11
Index
0000101000
…
0000101111
キャッシュ内
アドレス
2-way set associative Map
From CPU
0011010
00110 10 100
…
…
Main Memory
(1KB=128Lines)
Yes: Hit
=
Data
10
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
00000 10 100
0011010
…
…
Main Memory
(1KB=128Lines)
No
=
10
00110
Cache
(64B=8Lines)
10
Yes: Hit
=
00000
Cache Directory
(Tag Memory)
4 entries X 5bit X 2
Data
Conflict Missが減る
4-way set associative Map
From CPU
0000010
001101 0 100
0
001101
0011010
…
…
Main Memory
(1KB=128Lines)
=
=
Data
=
Cache Directory
(Tag Memory)
2 entries X 6bit X 4
000000
=
Cache
(64B=8Lines)
8-way set associative Map → Full Map
0000010
From CPU
0011010
…
…
100
0011010
0011010
Main Memory
(1KB=128Lines)
=
=
=
Data
=
=
=
Cache Directory
(Tag Memory)
7bit X 8
0000001
=
=
Cache
(64B=8Lines)
タグメモリの設計法




キャッシュ内に何ブロック入るかを計算する。
 2のn乗である時
 インデックスはnbitとなる
メモリ内に何ブロック入るかを計算する。
 2のh乗である時
 タグはh-n=mbitとなる
ダイレクトマップでは幅m,深さ2のn乗のタグメモリが必要
2-way set associativeは、インデックスが1bit減り深さが半
分となり、タグが1bitを増える。しかしこれがダブルで必要
 way数が倍になる度にインデックスが1bit減り、深さが半
分になり、タグが1bit増え、タグ自体が倍になる。
書き込みポリシー

Write Through





書き込み時に主記憶にもデータを書く
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)
0011 010 100
主記憶も同時に更新
0011
Hit
Cache
(64B=8Lines)
Cache Directory
(Tag Memory)
8 entries X (4bit )
Write Data
Write Through (Miss:Direct Write)
0000010
0011010
…
…
From CPU
Main Memory
(1KB=128Lines)
0000 010 100
主記憶のみ更新
0011
Miss
Cache
(64B=8Lines)
Cache Directory
(Tag Memory)
8 entries X (4bit )
Write Data
Write Through (Miss:Fetch on Write)
0000010
0011010
…
From CPU
…
Main Memory
(1KB=128Lines)
0000 010 100
0011
0000
Miss
Cache
(64B=8Lines)
Cache Directory
(Tag Memory)
8 entries X (4bit )
Write Data
Write Back (Hit)
0011010
…
…
From CPU
Main Memory
(1KB=128Lines)
0011 010 100
Dirty
0011 1
Hit
Cache
(64B=8Lines)
Cache Directory
(Tag Memory)
8 entries X (4bit+1bit )
Write Data
Write Back (Replace)
0000010
0011010
…
…
From CPU
Write
Back
0000 010 100
Main Memory
(1KB=128Lines)
Dirty
0011 10
0000
Miss
Cache
(64B=8Lines)
Cache Directory
(Tag Memory)
8 entries X (4bit+1bit )
ライトスルーとライトバック

「ライトスルーは主記憶を待たなければならないので非
効率」というのは嘘




ちゃんとライトバッファを装備すれば性能的に悪くはならない
しかし、シングルライトが必要→DRAMに合わない
常にデータの一致が取れるのがメリット、観測性が高い、I/Oで
有利
ライトバック


常にデータ転送がブロック単位→DRAM、高速バスに適合
バスの利用率が下がる→マルチコアに適合
大体世の中はライトバックになりつつある
リプレイスポリシー

リプレイスの際、どのWayを選ぶか?


LRU (Least Recently Used)




Direct map以外のキャッシュで問題になる
最近もっとも使っていないwayを選ぶ
2-wayならば簡単→ Verilog記述参照
4-way以上は結構面倒→ 擬似的なLRUでも大体
OK
他にランダム、FIFOなどが考えられるが実際上
あまり用いられない
キャッシュの性能
キャッシュオーバーヘッド付き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)の発生


3年のコンピュータアーキテクチャ、OSの授業で
学ぶ例外処理の一つ
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
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)で実行したとき
と2ウェイセットアソシアティブ(2way)で実行したときで、
両者のミスの回数と、演算結果が出るまでのクロック数
(pcがc番地になったら終了と考えよう)をシミュレーショ
ンして求めよ。

演習2




64kワードの主記憶に対して4kワードのキャッ
シュを設ける
ブロックサイズは16ワードとする
ダイレクトマップ、2way set associative、4way
set associativeキャッシュのタグメモリ構成をそ
れぞれ示せ
ヒント:タグメモリの設計法のページを参照!
演習3


あるキャッシュのブロックにマップされた互いに衝突するアドレ
スA,Bに対して以下のアクセスを順に行う。
1.
Aから読み出し
2.
Bから読み出し
3.
Aに書き込み
4.
Aから読み出し
5.
Bに書き込み
6.
Aから読み出し
7.
Aに書き込み
ダイレクトライト型のライトスルーキャッシュ、ライトバックキャッシュについ
て、それぞれのアクセスがミスするかヒットするかを示せ。また、各アクセ
スによってメモリに対してどのような操作(リプレイスR、ライトバックWB、ラ
イトスルーの書き込みWTH)が必要か?ライトバックについてはブロックは
C、Dのうちどちらの状態になるか?

similar documents