コンピュータアーキテクチャの論文を読んでいたのだが、どうもよく知らない項目がある。 よく考えてみたらコンピュータアーキテクチャの最新トレンドも含め最近勉強量が不足していたので、ここらへんでもう一度復習しておきたい。 せっかくなので海外の大学の講義資料を読んでみよう。
- Advanced Computer Architecture
https://www.ece.ucsb.edu/~strukov/ece154BSpring2018/home.htm
目次
- 1. 半導体のトレンドと背景
- 2.半導体の性能向上
- 3.半導体の性能向上
- 4. キャッシュ階層
- 5. キャッシュ階層
- 6. 高度なキャッシュ最適化
- 7. ILPの向上テクニック
- 8. ILPの向上テクニック, Tomasuloのアルゴリズム
- 9. 分岐予測
- 10. 複数命令発行の技術
Advanced Computer Architecture
2. メモリ階層の概要
キャッシュの動機
キャッシュのモチベーションとして、プロセッサのDRAMのレイテンシのギャップが挙げられる。以下の図は年代毎のプロセッサとDRAMの速度向上の傾向を示している。
この「メモリの壁」をどのように突破すればよいのか？以下のような方法がある。
- メモリ階層の構築
- アウトオブオーダの実行
- マルチスレッディング
- ベクトルプロセッサ
メモリの階層を設計する目的としては、メモリアクセスのサイクル数とプロセッサの性能のギャップを埋めるため。メモリは一般的に大きくなると生息になるため、このギャップを埋めるためにはメモリの階層化を行う。以下にメモリの階層を示す。
なぜこのような複数の階層によるメモリの階層化を行う必要があるのか？それはプログラムの特性として、局所的なデータアクセスを行うことが多いため、メモリの階層化を行うことにより高速かつ大きなメモリを仮想的に実現することができる。
メモリ階層について纏めると、以下のようになる。
| レベル | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 名前 | レジスタ | キャッシュ | メインメモリ | ディスクストレージ |
| 典型的なサイズ | < 1KB | 32KB - 8MB | < 512GB | > 1TB |
| 実装テクノロジ | CMOSマルチポートカスタムメモリ | CMOS オンチップSRAM | CMOS DRAM | 磁気ディスク |
| アクセスタイム(ns) | 0.15 - 0.30 | 0.5 - 15 | 30 - 200 | 5,000,000 |
| バンド幅 (MB/sec) | 100,000 - 1,000,000 | 10,000 - 40,000 | 5000 - 20,000 | 50 - 500 |
| 管理 | コンパイラ | ハードウェア | オペレーティングシステム | オペレーティングシステム・オペレータ |
| バックアップ | キャッシュ | メインメモリ | ディスク | 他のディスク・DVD |
キャッシュの方式
ブロックの置き換え方式によってさまざまなキャッシュの方式がある。
最も単純な方式：ダイレクトマップドキャッシュ
キャッシュのブロックのインデックスの計算方法は単純にアドレスを使用する。
- ブロックインデックス = 「ブロックアドレス」 MOD 「キャッシュ内のブロック数」
2ウェイセットアソシアティブキャッシュ
2種類のウェイのうちどちらかを使用してブロックを格納する。
- セットのインデックス = 「ブロックアドレス」 MOD 「キャッシュ内のセット数」
フルアソシアティブキャッシュ
ブロック中のどこにでも配置することができる。
キャッシュの置き換えポリシ
アソシアティブなキャッシュでは、セットがいっぱいの時に、どのブロックを書きだすかを決定するアルゴリズムが問題になる。以下のようなアルゴリズムが存在する。
- ランダム
- Least Recently Used (LRU)：LRUはアクセスの度にステートを更新する必要がある。真のLRU実装は2ウェイくらいが一般的。4-8ウェイでは疑似LRUが使用される。
- First In, First Out (FIFO) (ラウンドロビン)：アソシアティビティの高いキャッシュで使用される。
書き込みポリシについて
- ライトスルー：キャッシュへの書き込みを行う場合、キャッシュ自身とその後ろにあるメインメモリへの書き込みを行う。
- ライトバック：キャッシュへの書き込みを行う場合、キャッシュ自身にのみ書き込みを行う。
キャッシュ書き込み時のポリシ
- ライトアロケート（フェッチオンライト）：キャッシュミス時に、キャッシュ中にデータをフェッチしてから書き込む。
- ライトアロケート無し：キャッシュミス時に、キャッシュ中にデータをフェッチせずにメインメモリにのみ書き込む。
キャッシュ内データのストア時にライトバッファを設けることで性能を向上させる
キャッシュのデータをメインメモリに戻すときに、キャッシュとメインメモリの間にライトバッファを設けることでメインメモリへの書き戻しの完了を待つことなく次のリクエストを受け付けることができるようになる。
キャッシュの性能
キャッシュ最適化のための6つの方法
キャッシュ最適化を行うための6つの方法を紹介する。
- ミス率を下げる
- ブロックサイズの増大
- キャッシュサイズの増大
- アソシアティビティを上げる
- ミス時のペナルティを上げる
- 複数レベルキャッシュを導入する
- 読み込みのプライオリティを書き込みよりも上げる
- ヒット時のキャッシュアクセス時間を削減する
- キャッシュインデックスのアクセス時にアドレス変換を行わない。
キャッシュの3つのCモデル
- Compulsory : 初期参照。ブロックがキャッシュに乗っていないことによるキャッシュミス
- Capacity : プログラム中のすべてのブロックをキャッシュ中に持つことはできない。
- Conflict : 複数のメモリブロックが同じキャッシュ場所に配置されることにより衝突する。
最適化1. ブロックサイズを増大させてキャッシュミス率を下げる
- メリット：キャッシュミス率が下がる。
- デメリット：ミス時のペナルティが増大する。
- デメリット：Conflictミス率が増大する。
最適化2. キャッシュのサイズを大きくしてミス率を下げる
- メリット：容量不足によるミスが削減される
- デメリット：ヒット時の時間が増大する
- デメリット：電力とコストが増大する。
最適化3. アソシアティビティを向上させる
- メリット：衝突率が削減する
- デメリット：ヒット時のアクセスタイムが増大する
- デメリット：電力が増大する
最適化4. 複数階層のキャッシュを導入することでミスペナルティを削減する
- メリット：ミスペナルティが削減される。
- デメリット：複雑性が増大する
最適化5. 読み込みミスの優先度を書き込みミスよりも上げる
ロード命令の優先度を上げ、キャッシュの書き出しのときにライトバッファにブロックをストアする。読み込み時にライトバッファを参照するようにする。
