キャッシュの高速化手法と仮想記憶 天野英晴

キャッシュの性能 キャッシュオーバーヘッド付き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)の発生 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へ

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

容量と動作速度 2.5インチー3.5インチ ヘッド数：2-4 容量： １００GB-1TB 平均ディスクアクセス時間＝ 　　平均シーク時間（ヘッドを動かす時間）＋ 　　平均回転待ち時間＋転送時間→数msec インタフェース ATA(Advanced Technology Attachment) SCSI(Small Computer Systems Interface) ディスク内にマイクロプロセッサを装備し、アクセス時間を最適化 ディスクキャッシュの利用

ディペンダビリティ サービス仕様を満足 サービス中断 障害：1→２ 復旧：2→1 信頼性（reliability): 1の連続遂行可能時間 障害：1→２　　復旧：2→1 信頼性（reliability): 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 RAID0 RAID0 RAID1 RAID1 D0 D1 D0 D1 D0 D0 D1 D1 D2 D3 D2 D3 D2 D2 D3 D3 D4 D5 D4 D5 D4 D4 D5 D5 D6 D7 D6 D7 D6 D6 D7 D7 D8 D9 D8 D9 D8 D8 D9 D9 … … … … … … … … ディスクドライブに対する故障耐性はRAID1+0が有利 コントローラに対する故障耐性はRAID0+1が有利 RAID1+0の方が多く使われる

RAID 3 データ単位に分散させ、各行に対応するParityディスクを設ける 一つのディスクが故障しても、Parityにより復旧が可能 B0 B1 B2 B3 P B4 B5 B6 B7 P C0 C1 C2 C3 P C4 C5 C6 C7 P データ単位に分散させ、各行に対応するParityディスクを設ける 一つのディスクが故障しても、Parityにより復旧が可能 連続データに対してアクセスが分散されるので、ストリーム処理（画像データ）や科学技術計算で有利

RAID4 独立した小さな読み出し（保護グループ内に入る読み出し）に対応するためにブロック単位でストライピング AII AIII AIV P BI BII BIII BIV P CI CII CIII CIV P DI DII DIII DIV P 独立した小さな読み出し（保護グループ内に入る読み出し）に対応するためにブロック単位でストライピング それぞれのブロックに対してパリティを設ける

RAID4とRAID3の書き込み時の動作 小さな書き込みに対して、RAID4は読み出しが1台で済む P AI AII AIII AIV P ＋ ＋ ＋ A0’ A1 A2 A3 P’ AI’ AII AIII AIV P’ 小さな書き込みに対して、RAID4は読み出しが1台で済む 書き込み時にParityディスクがボトルネックになる

RAID 5 Parityブロックを分散することでParityの書き込みを分散 障害時の回復は面倒 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% プロセッサはインオーダ実行（命令の追い越しはない） キャッシュはパイプライン化されており、十分なライトバッファを持っている