FPGA開発日記

カテゴリ別記事インデックス https://msyksphinz.github.io/github_pages , English Version https://fpgadevdiary.hatenadiary.com/

UCBのAdvanced Computer Architectureの講義資料を読む(4. キャッシュ階層)

コンピュータアーキテクチャの論文を読んでいたのだが、どうもよく知らない項目がある。 よく考えてみたらコンピュータアーキテクチャの最新トレンドも含め最近勉強量が不足していたので、ここらへんでもう一度復習しておきたい。 せっかくなので海外の大学の講義資料を読んでみよう。

  • Advanced Computer Architecture

https://www.ece.ucsb.edu/~strukov/ece154BSpring2018/home.htm

目次

Advanced Computer Architecture

2. メモリ階層の概要

キャッシュの動機

キャッシュのモチベーションとして、プロセッサのDRAMのレイテンシのギャップが挙げられる。以下の図は年代毎のプロセッサとDRAMの速度向上の傾向を示している。

f:id:msyksphinz:20200312232225p:plain

この「メモリの壁」をどのように突破すればよいのか?以下のような方法がある。

  • メモリ階層の構築
  • アウトオブオーダの実行
  • マルチスレッディング
  • ベクトルプロセッサ

メモリの階層を設計する目的としては、メモリアクセスのサイクル数とプロセッサの性能のギャップを埋めるため。メモリは一般的に大きくなると生息になるため、このギャップを埋めるためにはメモリの階層化を行う。以下にメモリの階層を示す。

f:id:msyksphinz:20200312232243p:plain

なぜこのような複数の階層によるメモリの階層化を行う必要があるのか?それはプログラムの特性として、局所的なデータアクセスを行うことが多いため、メモリの階層化を行うことにより高速かつ大きなメモリを仮想的に実現することができる。

f:id:msyksphinz:20200312232259p:plain:w400
f:id:msyksphinz:20200312232318p:plain:w400

メモリ階層について纏めると、以下のようになる。

レベル 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

キャッシュの方式

ブロックの置き換え方式によってさまざまなキャッシュの方式がある。

f:id:msyksphinz:20200312232452p:plain

最も単純な方式:ダイレクトマップドキャッシュ

キャッシュのブロックのインデックスの計算方法は単純にアドレスを使用する。

  • ブロックインデックス = 「ブロックアドレス」 MOD 「キャッシュ内のブロック数」
f:id:msyksphinz:20200312232509p:plain

2ウェイセットアソシアティブキャッシュ

2種類のウェイのうちどちらかを使用してブロックを格納する。

  • セットのインデックス = 「ブロックアドレス」 MOD 「キャッシュ内のセット数」
f:id:msyksphinz:20200312232525p:plain

フルアソシアティブキャッシュ

ブロック中のどこにでも配置することができる。

f:id:msyksphinz:20200312232539p:plain

キャッシュの置き換えポリシ

アソシアティブなキャッシュでは、セットがいっぱいの時に、どのブロックを書きだすかを決定するアルゴリズムが問題になる。以下のようなアルゴリズムが存在する。

  • ランダム
  • Least Recently Used (LRU):LRUはアクセスの度にステートを更新する必要がある。真のLRU実装は2ウェイくらいが一般的。4-8ウェイでは疑似LRUが使用される。
  • First In, First Out (FIFO) (ラウンドロビン):アソシアティビティの高いキャッシュで使用される。

書き込みポリシについて

  • ライトスルー:キャッシュへの書き込みを行う場合、キャッシュ自身とその後ろにあるメインメモリへの書き込みを行う。
  • ライトバック:キャッシュへの書き込みを行う場合、キャッシュ自身にのみ書き込みを行う。

キャッシュ書き込み時のポリシ

  • ライトアロケート(フェッチオンライト):キャッシュミス時に、キャッシュ中にデータをフェッチしてから書き込む。
  • ライトアロケート無し:キャッシュミス時に、キャッシュ中にデータをフェッチせずにメインメモリにのみ書き込む。

キャッシュ内データのストア時にライトバッファを設けることで性能を向上させる

キャッシュのデータをメインメモリに戻すときに、キャッシュとメインメモリの間にライトバッファを設けることでメインメモリへの書き戻しの完了を待つことなく次のリクエストを受け付けることができるようになる。

キャッシュの性能

f:id:msyksphinz:20200312232554p:plain

キャッシュ最適化のための6つの方法

キャッシュ最適化を行うための6つの方法を紹介する。

  • ミス率を下げる
      1. ブロックサイズの増大
      1. キャッシュサイズの増大
      1. アソシアティビティを上げる
  • ミス時のペナルティを上げる
      1. 複数レベルキャッシュを導入する
      1. 読み込みのプライオリティを書き込みよりも上げる
  • ヒット時のキャッシュアクセス時間を削減する
      1. キャッシュインデックスのアクセス時にアドレス変換を行わない。

キャッシュの3つのCモデル

  • Compulsory : 初期参照。ブロックがキャッシュに乗っていないことによるキャッシュミス
  • Capacity : プログラム中のすべてのブロックをキャッシュ中に持つことはできない。
  • Conflict : 複数のメモリブロックが同じキャッシュ場所に配置されることにより衝突する。

最適化1. ブロックサイズを増大させてキャッシュミス率を下げる

  • メリット:キャッシュミス率が下がる。
  • デメリット:ミス時のペナルティが増大する。
  • デメリット:Conflictミス率が増大する。
f:id:msyksphinz:20200312232615p:plain

最適化2. キャッシュのサイズを大きくしてミス率を下げる

  • メリット:容量不足によるミスが削減される
  • デメリット:ヒット時の時間が増大する
  • デメリット:電力とコストが増大する。
f:id:msyksphinz:20200312232627p:plain

最適化3. アソシアティビティを向上させる

  • メリット:衝突率が削減する
  • デメリット:ヒット時のアクセスタイムが増大する
  • デメリット:電力が増大する
f:id:msyksphinz:20200312232641p:plain

最適化4. 複数階層のキャッシュを導入することでミスペナルティを削減する

  • メリット:ミスペナルティが削減される。
  • デメリット:複雑性が増大する
f:id:msyksphinz:20200312232703p:plain:w400
f:id:msyksphinz:20200312232759p:plain:w400

最適化5. 読み込みミスの優先度を書き込みミスよりも上げる

f:id:msyksphinz:20200312232813p:plain

ロード命令の優先度を上げ、キャッシュの書き出しのときにライトバッファにブロックをストアする。読み込み時にライトバッファを参照するようにする。

最適化6. ヒット時間を削減するために、キャッシュアクセス時に使用するインデックスにアドレス変換を使用しない