システムLSIとアーキテクチャ技術　（part　II：オンチップ並列　　　　　　　　　　　アーキテクチャ）

Size: px

Start display at page:

Download "システムLSIとアーキテクチャ技術　（part　II：オンチップ並列　　　　　　　　　　　アーキテクチャ）"

さやとみもと
5 years ago
Views:

1 コンピュータ基礎記憶階層とキャッシュその2 テキスト第 10 章天野英晴

2 記憶システム膨大な容量を持ちアクセス時間 ( 読み出し書き込み ) が短いメモリが欲しい! しかし容量の大きい ( ビット単価が安い ) メモリは遅い高速なメモリは容量が小さいお金にモノを言わせて高速なメモリをたくさん揃えても大容量化の段階で遅くなってしまうそこでアクセスの局所性 (Locality) を利用時間的局所性 (Temporal Locality) 一度アクセスされたアドレスは近いうちにまたアクセスされる空間的局所性 (Special Locality) 一度アクセスされたアドレスに近い場所がまたアクセスされる

3 記憶の階層高速小容量の CPU の近くに置きよく使うデータを入れておくそこになければより遅い大容量メモリに取りに行く CPU L1 キャッシュ L2 キャッシュ L3 キャッシュ SRAM ソフトウェアからは透過 ( トランスペアレント ) チップ内メモリ ~64KB 1-2clock ~256KB 3-10clock 2M~4MB 10-20clock 主記憶 DRAM 4~16GB clock OS が管理補助記憶 (2 次記憶 ) μ-msec オーダー数百 GB

4 キャッシュ頻繁にアクセスされるデータを入れておく小規模高速なメモリ Cache であって Cash ではないので注意元々はコンピュータの主記憶に対するものだが IT 装置の色々なところに使われるようになったディスクキャッシュページキャッシュ..etc.. 当たる ( ヒット ) はずれる ( ミスヒット ) ミスヒットしたら下のメモリ階層から取ってきて入れ替える ( リプレイス ) マッピング ( 割り付け ) 主記憶とキャッシュのアドレスを高速に対応付ける Direct map Full associative cache 書き込みポリシー今日はここから! ライトスルーライトバックリプレイス ( 追い出し ) ポリシー LRU (Least Recently Used)

5 書き込みポリシー Write Through 書き込み時に主記憶にもデータを書く Direct Write: ミス時は主記憶だけに書く Fetch-on-write: ミス時はリプレイスしてから書く主記憶に合わせると性能ががた落ち (Verilog の設計はそうなっている ) だが Write buffer があれば性能がさほど落ちることはない Write Back 書き込みはキャッシュのみキャッシュと主記憶が一致 :Clean 違う :Dirty Dirty なキャッシュブロックは書き戻し (Write Back) をしてからリプレイス

6 ライトスルー (Hit) From CPU Main Memory (1KB=128Lines) 主記憶も同時に更新 0011 Hit Cache Directory (Tag Memory) 8 entries X (4bit ) Write Data Cache (64B=8Lines)

7 ライトスルー (Miss: ダイレクトライト ) From CPU Main Memory (1KB=128Lines) 主記憶のみ更新 0011 Miss Cache (64B=8Lines) Cache Directory (Tag Memory) 8 entries X (4bit ) Write Data

8 ライトスルー (Miss: フェッチオンライト ) From CPU Main Memory (1KB=128Lines) Miss Cache (64B=8Lines) Cache Directory (Tag Memory) 8 entries X (4bit ) Write Data

9 ライトバック (Hit) From CPU Dirty Main Memory (1KB=128Lines) Hit Cache (64B=8Lines) Cache Directory (Tag Memory) 8 entries X (4bit+1bit ) Write Data

10 ライトバック (Replace) From CPU Dirty Write Back Main Memory (1KB=128Lines) Miss Cache Directory (Tag Memory) 8 entries X (4bit+1bit ) Cache (64B=8Lines)

11 ライトスルーとライトバックライトスルーは主記憶を待たなければならないので非効率というのは嘘ちゃんとライトバッファを装備すれば性能的に悪くはならないしかしシングルライトが必要 DRAM に合わない常にデータの一致が取れるのがメリット観測性が高い I/O で有利ライトバック常にデータ転送がブロック単位 DRAM 高速バスに適合バスの利用率が下がるマルチコアに適合大体世の中はライトバックになりつつある

12 リプレイスポリシーリプレイスの際どの Way を選ぶか? Direct map 以外のキャッシュで問題になる LRU (Least Recently Used) 最近もっとも使っていない way を選ぶ 2-way ならば簡単 Verilog 記述参照 4-way 以上は結構面倒擬似的な LRU でも大体 OK 他にランダム FIFO などが考えられるが実際上あまり用いられない

13 演習 1 キャッシュブロック A とキャッシュブロック B は Conflict Miss を起こすアドレスである以下のアクセスを行った場合にライトスルーキャッシュ ( ダイレクトライト ) ライトバックキャッシュについてヒットするかミスするかを示しなさいライトバックの場合ブロックの状態を示しなさいまたリプレイスとライトバックが起きるかどうかも示しなさい 1. ブロック A から読み出し 2. ブロック A に書き込み 3. ブロック B から読み出し 4. ブロック A から読み出し 5. ブロック A に書き込み 6. ブロック B に書き込み 7. ブロック A から読み出し

14 キャッシュの性能キャッシュオーバーヘッド付き CPI(Clock cycles Per Instruction)= 理想の CPI + 命令キャッシュのミス率ミスペナルティ + データキャッシュの読み出しミス率読み出し命令の生起確率ミスペナルティこの式の問題点ミスペナルティは書き戻しを伴うかどうかで違ってくる (Write Back) ライトバッファの容量連続書き込み回数によっては書き込みミスでもストールする書き込み直後に読み出しをするとキャッシュが対応できないでペナルティが増えることもあるノンブロッキングキャッシュ実際は階層化されているのでそれぞれの階層を考えないといけないプロセッサが Out-of-order 実行可能ならば読み出し時にストールしないかもしれない ( この話は後ほど ) ちゃんと評価するにはシミュレータを使うしかない

15 ミスの原因 :3 つの C Capacity Miss: 容量ミス絶対的な容量不足により起きる Conflict Miss: 衝突ミス容量に余裕があっても index が衝突することで格納することができなくなる Compulsory Miss (Cold Start Miss) 初期化ミススタート時プロセス切り替え時に最初にキャッシュにブロックを持ってくるためのミス避けることができない

16 キャッシュサイズとそれぞれもミスの割合 Hennessy & Patterson Computer Architecture より

17 ミス率を減らす容量を増やす〇容量ミスはもちろん減る衝突ミスも減るコストが大きくなるヒット時間が増えるチップ ( ボード ) に載らない Way 数を増やす〇衝突ミスが減るキャッシュ容量が小さいと効果的 2Way は 2 倍の大きさの Direct Map と同じ位のミス率になるキャッシュ容量が大きい場合残った不運な衝突ミスを減らす効果があるコストが大きくなるヒット時間が増える 4 以上はあまり効果がないブロックサイズを大きくする〇局所性によりミスが減るミスペナルテイが増える ( ブロックサイズに比例はしないが ) キャッシュ容量が小さいと衝突ミスが増える容量に応じて適切なブロックサイズを選ぶ 32byte-128byte

18 Way 数のトレードオフ大きくするとヒット率が改善 Direct Map 2way set associative 32 人で 1 つの椅子を争う VS. 64 人で 2 つの椅子を争う偶然同じ時間に椅子を狙うライバルが居る場合は効果的サイズを倍にするのと同じ程度の効果が見込まれるそれ以上はどんどん効果が減る 4 以上はあまり効果が上がらない遅延時間が大きくなる ( マルチプレクサの遅延 ) 8 くらいまでが多い

19 ブロックサイズとミスの割合 Hennessy & Patterson Computer Architecture より

20 ブロックサイズと平均アクセス時間 Hennessy & Patterson Computer Architecture より

21 ミスペナルティを減らす階層キャッシュ CPU-Memory 間に複数のキャッシュを設けるノンブロッキングキャッシュミス処理の間にも次のアクセスを受け付ける Critical Word First と Early Restart CPU に対して可能な限り早くアクセスされたデータ ( 命令 ) を渡す

22 マルチレベルキャッシュ CPU L1 キャッシュ ~64KB 1-2clock CPU に近い方から L1,L2.. と番号を付ける L2 L3 キャッシュの局所ミス率は L1 キャッシュより高い L2 キャッシュ L3 キャッシュ主記憶 ~256KB 3-10clock 2M~4MB 10-20clock 4~16GB clock

23 マルチレベルキャッシュの制御 Multi-level Inclusion 上位階層のキャッシュが下位階層の内容を全て含む階層間のやり取りはキャッシューメモリ間と同じメモリシステム中にデータの重複が数多く存在 Multi-level Exclusion 上位階層のキャッシュと下位階層のキャッシュの内容が重なることはない階層間のやり取りはリプレースというよりはスワップ

24 ノンブロッキングキャッシュキャッシュが動作中にも次のアクセスを受け付けるキャッシュの操作をパイプライン化するメモリアクセスを強化しないとノンブロッキングキャッシュにはできない実際はミス中のヒットを 1 回許せば大体 OK CPU がアウトオブオーダ実行可能でないと効果が小さい来週

25 Critical Word First と Early Restart CPU キャッシュに転送する前に CPU にワードを渡す (Early Restart) キャッシュ主記憶アクセスしたワードを先に送る (Critical Word First)

26 プリフェッチアクセスする前にキャッシュに取って来る ( 問題点 ) 使うかどうか分からないデータ ( 命令 ) のために他のラインを追い出していいのか?? プリフェッチバッファを使う場合が多い本当にアクセスされたらキャッシュに入れるハードウェアプリフェッチ命令キャッシュで用いる一つ ( 二つ ) 先のブロックまで取って来る命令キャッシュは局所性が高いので効果的ソフトウェアプリフェッチプリフェッチ命令を使う : データキャッシュコンパイラが挿入命令実行のオーバーヘッドを伴う

27 コンパイラによる最適化ループ構造の最適化ループの入れ子を入れ替える 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]; ループをくっつけるブロック化キャッシュにうまく入るようにデータ構造を変更する科学技術計算には効果的

28 仮想記憶 (Virtual Memory) プロセッサから見たアドレス ( 論理アドレス ) と実際のメモリ上のアドレス ( 物理アドレス ) を分離する実メモリよりも大きいメモリを扱うことができる複数のプロセスを互いのアドレスを気にせずに並行実行可能管理単位で記憶の保護ページ : 固定サイズ (4K-16KB) vs. セグメント : 可変サイズページを用いる場合が多い概念はキャッシュに似ているが OS が管理用語も違うブロック ( ライン ):32-128B ページ :4KB リプレイススワップインライトバックスワップアウトページの割り付けは OS が管理リプレイスは LRU(Least Recently Used) 書き込み制御は当然ライトバック

29 仮想記憶のアドレス変換論理アドレス空間 (4GB) ページ番号 20bit ページ内アドレス 12bit 物理アドレス空間 (16MB) TLB 12bit 12bit 20bit 12bit の変換テーブルは巨大ソフトウェアで管理 TLB(Translation Lookaside Buffer) はこの変換テーブルに対するキャッシュ

30 TLB(Translation Lookaside Buffer) 論理アドレスページ番号ページ内アドレス = = = = = Dirty bit Priority bit = = = 物理アドレス

31 ページフォルト (Page Fault) の発生 TLB ミスページ自体は主記憶中に存在 TLB の入れ替えページ自体が主記憶中にないスワップイン + TLB の入れ替えヒットしたが Dirty bit が 0 のページに書き込みを行った Dirty bit のセットヒットしたが特権命令でないのに特権ページを扱ったいずれのケースも OS で処理する

32 TLB 変換時間の短縮仮想アドレスキャッシュキャッシュは仮想アドレスで参照するプロセスによってアドレスがダブる問題 ( シノニム問題 ) の解決が難しい仮想アドレスインデックス - 物理アドレスタグ方式 (Virtually indexed, Physically Tagged) 変換を行わないページ内アドレスをキャッシュのインデックスに使うタグ参照キャッシュ参照 TLB 変換が同時に可能 Direct Map だとキャッシュサイズが 4KB に制限される 2 way だと 8K 4 way だと 16K 8 way だと 32K 1 次キャッシュだけの話なので多少小さくてもいいか

33 仮想アドレスインデックス物理アドレスタグ方式ページ番号 20bit ページ内アドレス (12bit) index TLB Tag Mem. キャッシュ 12bit Tag = Hit CPU へ

34 演習 2 以下の条件でキャッシュのオーバーヘッドを含めた CPI はどのようになるか計算せよ理想の CPI: 1 キャッシュのミスペナルティ :10 クロック命令キャッシュのミス率 :1% データキャッシュのリード時のミス率 :3% LD 命令の確率 15%

システムLSIとアーキテクチャ技術　（part　II：オンチップ並列　　　　　　　　　　　アーキテクチャ）

システムLSIとアーキテクチャ技術　（part　II：オンチップ並列　　　　　　　　　　　アーキテクチャ）今回は前回の続きでキャッシュの書き込みポリシー性能の検討をやって仮想記憶を紹介します 1 ではメモリの基本がわかったところでキャッシュの話をしましょうキャッシュとは頻繁にアクセスされるデータ ( 命令もデータの一種と考える ) を入れておく小規模高速なメモリを指します小銭の Cash ではなく Cache( 貴重なものを入れておく小物入れ ) なのでご注意くださいこの言葉はコンピュータの世界で大変有名になったので

システムLSIとアーキテクチャ技術 （part II：オンチップ並列 アーキテクチャ）

システムLSIとアーキテクチャ技術　（part　II：オンチップ並列　　　　　　　　　　　アーキテクチャ）