FPGA開発日記

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

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

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

  • Advanced Computer Architecture

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

目次

Advanced Computer Architecture

2. メモリ階層の概要:続き

仮想メモリに関連する論理メカニズム

メインメモリ中に、ストレージをキャッシュするメカニズムが必要である。例えば、メインメモリのデータをキャッシュ中に保持しておく方法が必要だ。

  1. メインメモリへのリクエストで例外を発生させる(OSモードに遷移する)
    • いくつかの最小限のハードウェア支援が必要となる(完全にソフトウェアのみでの実現は不可能)
  2. OSモード中に、メモり中にソフトウェアでキャッシュを構築する。
    • ハードウェアキャッシュと全く同様に構築する場合(ケースAの場合)、いくつかの問題が発生する。例えば、タグのデータを読み込もうとするとキャッシュミスが発生する。
    • さらに、命令フェッチ中に例外が発生するとさらに例外を処理する必要がある。
  3. メインメモリをOS空間とユーザ空間に分ける。
    • テーブル中にタグのみを保存し、巨大なページを用意する(ケースBの場合)。
    • OSのコードはOS空間にすべて配置する。
      • OSのコード中でミスが発生しても例外は発生させず、単純にメインメモリから命令を読んでくればよい。
  4. コードリロケーションを行うと、メモリの使用効率が悪化してしまう。
    • アドレス変換を行う(ケースC)
    • プロセスの共有や保護のメカニズムにも自然に合致する。
  5. プログラム(データとコード)は仮想アドレスとして表現し、使用するときに物理アドレスに変換する。
    • OSに関しては変換は必要としない。
f:id:msyksphinz:20200313225817p:plain

仮想メモリ

仮想メモリのモチベーションとしては、

  • データをキャッシングする
  • リロケーションを行う。
  • 共有を行う。
  • 保護を行う。

などがある。

アドレス変換メカニズム

f:id:msyksphinz:20200313225831p:plain

キャッシュのエイリアシングについて

キャッシュのエイリアシングとは、

  • 2つの仮想アドレスが1つの物理ページを参照してしまい、競合が発生する。
  • 仮想アドレスを持つデータが1つの物理アドレスを参照するのに2つのキャッシュエントリを保持している。

  • 一般的な解決策:キャッシュ中に同じデータが共存するのを防ぐためにエイリアスを禁止する。

  • ダイレクトマップ形式におけるソフトウェア(OS)による解決方法

    • 共有ページの仮想アドレスはキャッシュのインデックスビットと一致させるようにする。これにより据えての仮想メモリアクセスは、すべて同じ物理アドレスのインデックスを参照するようになる。

キャッシュは仮想アドレスでは存するべきか、物理アドレスで保存するべきか?

仮想アドレスを使用すると、物理アドレスに変換するためにさらにメモリアクセスを必要としてしまう。このためメモリアクセス自体が非常に高価なものになる。これを防ぐために、ハードウェアでTranslation Lookaside Buffer(TLB)を使用してページテーブルの参照時に余計なメモリアクセスが発生しないような工夫が取られている。

f:id:msyksphinz:20200313225852p:plain

アドレス変換を高速化するためにTLBを追加する

f:id:msyksphinz:20200313225909p:plain

TLBを挿入することにより、メモリのアクセスフローは以下のように変化する。

f:id:msyksphinz:20200313225927p:plain

TLB内に当該ページのアドレス変換情報が存在していなかった場合、メモリアクセスを発行し当該ページテーブル情報を格納する。ページがメインメモリ中に存在しなかった場合、真のページフォルトのためディスクまでアクセスが発生する。

TLBミスは真のTLBページフォルトよりも発生土が十分に高い。

仮想アドレスを使用するキャッシュ

  • メリット:キャッシュのヒット・ミスをすぐに判定することができる。
  • デメリット:コンテキストスイッチが発生するとすぐにキャッシュをフラッシュする必要がある。
    • ASID(Address Space Identifiers)を持っていればフラッシュは不要。
  • デメリット:ページを共有することによるエイリアシングの問題が発生する。
f:id:msyksphinz:20200313225940p:plain

最適化6に立ち戻って:TLBとキャッシュへの同時アクセス

  • 仮想インデックス・物理タグ:仮想アドレスの一部を使ってTLBにアクセスし、仮想アドレスの一部を使ってキャッシュインデックスにアクセスする。TLBにより変換された物理アドレスとページオフセットを合わせて物理アドレスを作成し、キャッシュから取得した物理タグをTLBの物理タグと比較する。
f:id:msyksphinz:20200313225951p:plain

線形ページテーブル

  • ページテーブルエントリ(PTE):ページが存在しているかを示すビットが含まれている。
  • ページが存在するメモリの物理アドレスへのPPN(Physical Page Number)
  • ディスクに存在するページの番号:DPN(Disk Page Number)
  • ページ保護と属性に関するステータスビットも含まれる。
  • オペレーティングシステムは、プロセスが切り替わるとページテーブルベースレジスタの中身を変更する。
f:id:msyksphinz:20200313230004p:plain

ページテーブルのサイズは、32ビットアドレスであれば4kB+4バイトのPTE程度が良い。

2^{20} 個ののPTEが存在することになり、つまりユーザ当たり4MB程度がページテーブルの格納に使用される。全ての仮想アドレス空間をバックアップするのに4GB程度のスワップ領域が必要となる。

より大きなページを作成すると、今度はメモリ内でフラグメンテーションが大きくなり、ページフォルト時のペナルティが大きくなる。

階層的なページテーブル

仮想アドレスを複数の領域に分割し、何度もPTEをジャンプしながら最終的な物理アドレスに到達する。

f:id:msyksphinz:20200313230014p:plain