キャッシュの高速化手法と仮想記憶作りながら学ぶコンピュータアーキテクチャ（改訂版）授業資料テキスト152-15７ページ対応天野英晴キャッシュの性能キャッシュオーバーヘッド付きCPI(Clock cycles Per Instruction)＝理想のCPI + 命令キャッシュのミス率×ミスペナルティ＋データキャッシュの読み出しミス率×読み出し命令の生起確率×ミスペナルティ  この式の問題点  ミスペナルティは書き戻しを伴うかどうかで違ってくる（Write Back)  ライトバッファの容量、連続書き込み回数によっては書き込みミスでもストールする  書き込み直後に読み出しをするとキャッシュが対応できないでペナルティが増えることもある→ノンブロッキングキャッシュ  実際は階層化されているのでそれぞれの階層を考えないといけない  プロセッサがOut-of-order実行可能ならば読み出し時にストールしないかもしれない（この話は後ほど、、、）  ちゃんと評価するにはシミュレータを使うしかない、、、、ミスの原因：３つの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 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) ページ番号 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 １次キャッシュだけの話なので、多少小さくてもいいか。。。。仮想アドレスインデックス・物理アドレスタグ方式ページ番号 20bit ページ内アドレス(12bit) 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) ディスク内にマイクロプロセッサを装備し、アクセス時間を最適化ディスクキャッシュの利用ディペンダビリティサービス仕様を満足 2. サービス中断障害：1→２復旧：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%  プロセッサはインオーダ実行（命令の追い越しはない）  キャッシュはパイプライン化されており、十分なライトバッファを持っている