題名の通り、私がコンピュータの「キャッシュ」というものについてあまりにも知識不足なため、 ここらで基礎の基礎から調べ直してみて、その結果をまとめるつもりのものです。 たぶんこのテーマだと終わりはないような気がするので、気が向いたときに追加修正していくことになると思います。
https://en.oxforddictionaries.com/definition/cache から引用：
- NOUN
- 1.2 Computing An auxiliary memory from which high-speed retrieval is possible.
高速に検索することができる補助的なメモリ、とのこと。 （「検索」で適切かちょっと疑わしいですが、いいたいことはわかる気がするのでとりあえずこのまま）
広義に「キャッシュ」というとブラウザのキャッシュとか色々出てきそうですが、以降この文章で単に「キャッシュ」といったときには CPU のキャッシュメモリのことを指すものと定義します。
なぜキャッシュメモリが必要になったかは、Hisa Ando さんの「コンピュータアーキテクチャの話」というマイナビニュース内の連載がわかりやすかったのでこれを引用します。 https://news.mynavi.jp/article/architecture-135/ から引用：
メモリは1サイクルか2サイクルでアクセスができるという想定でパイプラインを考えてきたが、この想定がある程度成り立っていたのは30年以上も昔のことである。 それ以降の30年で、プロセサのクロックは1000倍程度速くなったが、メモリのアクセスタイムは10倍程度しか向上しておらず、結果として、現在のマイクロプロセサがDRAMで構成されたメモリをアクセスするには、100サイクル以上を必要とするようになってきている。
CPU が速くなりすぎて補助的でない方のいわゆる普通のメモリの速度が追いつかなくなってきた、ということのようです。 普通のメモリへのアクセスを『遠くの倉庫まで毎回必要な工具や材料を取りに行く』、キャッシュへのストアを『近くに小さな置き場を作り』『必要となりそうな材料はまとめて倉庫から持って』くる、という比喩で説明しています。なるほど。
で、これを実現するやり方は２つあると書かれていますが、そのうちの 1 つが
ハードウェアがどのデータが頻繁に使われるかを判断して、ローカルメモリに自動的にデータを出し入れする方式
https://news.mynavi.jp/article/architecture-136/ から引用：
プログラムで意識する必要のない後者のローカルメモリを、キャッシュ(Cache:秘密の小箱)と呼ぶ。
とされています。 ここから、キャッシュメモリは
- （プログラム＝ソフトウェアではなく）コンピュータ＝ハードウェアが
- 頻繁に使われると判断したデータを格納するための
- 通常のメモリよりも CPU からのアクセスが高速な（しかし小容量な）メモリ
と考えられます。
「コンピュータアーキテクチャの話」がわかりやすかったので、以降しばらくはこれを読んで、部分的に引用しつつ自分なりに解釈することで概観をつかんで行こうと思います。 （この項は「コンピュータアーキテクチャの話」の第137回を読んで解釈したものです。）
メモリ上のデータにはそのアドレスが存在するため、メモリへの読み書きをキャッシュで代替できるか確認するとき、実際に代替するとき、またキャッシュ上で書き換えられたデータをメモリに書き込むとき、元のアドレスがわかっていなければいけません。 この「元のアドレス情報」をタグまたはキャッシュタグと呼ぶそうです。タグとデータのペアはキャッシュラインと呼ぶそうです。
またタグはアドレス情報だけではなく、キャッシュラインが有効かどうかであるとか、データが上書きされた＝メモリを書き換える必要があるかどうかのような制御情報もあわせて書き込まれているようです。
Ruby でいうところの ruby_fl_type https://github.com/ruby/ruby/blob/v2_6_0_preview2/include/ruby/ruby.h#L815 のようなものだと考えるとわかりやすそうです。
タグは情報そのものの名前であって、タグが書き込まれるメモリは「タグアレイ」または「ディレクトリ」と呼ばれるらしいです。また、データが書き込まれるメモリは「データアレイ」と呼ぶそうです。 個人的には「タグ」というとその書かれた内容より荷札という物体そのものを連想してしまうので、使い分けに注意したいです。
ここまでをまとめると、以下のような形になるでしょうか。
- メモリにアクセスするときに、
- キャッシュの中の「タグアレイ」（または「ディレクトリ」）という場所に書かれた「タグ」を見て、
- もしアクセスしようとしたメモリに一致する情報が存在すれば、
- その「タグ」の「キャッシュライン」上でペアにあるデータをキャッシュの「データアレイ」から特定し、
- このデータへのアクセスで、元々のメモリアクセスを代替する。
タグアレイも広義のメモリですのでその読み書きはコストがかかりますし、キャッシュ内の記憶容量も使用します。 そこだけを考えると相対的なタグの容量を小さく、つまりキャッシュラインの容量を大きくしたくなります。
しかしキャッシュの容量が固定であれば、キャッシュラインを大きくすることはキャッシュラインの本数を減らすこととと同義であり、 そうすると今度はキャッシュでカバーするメモリが局所化してしまい、プログラムで扱うメモリをカバーしにくくなります。 そのため、キャッシュラインは大きすぎず小さすぎないサイズで設計されていることが重要になってきます。
（この項は「コンピュータアーキテクチャの話」の第138回から第140回を読んで解釈したものです。）
キャッシュはその性質上高速でなければならないので、前述の「アクセスしようとしたメモリに一致する情報が存在」するかどうかという条件の判定も、やはり高速に行わなければいけません。
すべてのタグのアドレス情報を比較・検索する方式を「フルアソシアティブ」と呼ぶそうです。 フルアソシアティブは理想的な動作が保証されますが、比較回路の面積や消費電力に問題がでやすいという欠点があるようです。
アクセス要求のアドレスを上位・中位・下位で三分割し、上位をアドレスタグ、中位の部分をキャッシュインデックス、つまり「キャッシュラインの何本目か」の添字として利用する方式を「ダイレクトマップキャッシュ」と呼ぶそうです。 ダイレクトマップキャッシュはフルアソシアティブに比べて回路の単純化が見込めますが、異なるアドレスタグでキャッシュインデックスが一致してしまうようなメモリアクセスをするとキャッシュミスとなり性能低下が起きます。
これらの方式のいわゆる「いいとこ取り」または「中間的な方式」として、「セットアソシアティブ」がよく利用されているそうです。 基本的なアイディアとしてアドレスを上位・中位・下位にわける方式はダイレクトマップキャッシュと同じなのですが、中位のインデックスに対して「way数」と呼ばれる個数分だけ対応するキャッシュラインが複数存在するようにしておきます。 ある中位アドレスに対応するキャッシュラインの組を「セット」と呼びます。
（この項は「コンピュータアーキテクチャの話」の第140回から第141回を読んで解釈したものです。）
メモリからキャッシュにデータを持ってこようとしたときにキャッシュに空きがない場合、古いキャッシュラインを上書きして利用することになります。 セットアソシアティブでは way 数の分だけ追い出しの候補があります。この判断基準として、「セット中で、直近の利用（アクセス）がもっとも古いキャッシュライン」を追い出し対象にする Least Recently Used 略して「LRU」という方式がよく使われます。
回路を簡単にするため、way 数が多い場合には「アクセスの新しい方は厳密に記憶するが、古い方はまとめて扱い厳密には記憶しない」というような、擬似的な LRU で実装されることがよくあるそうです。
（この項は「コンピュータアーキテクチャの話」の第142回を読んで解釈したものです。）
キャッシュに持ってきたデータを書き換えた場合、メモリにもその値を反映させる必要があります。 このとき大きく分けて方針は 2 つあります。
「ライトスルー」方式は、キャッシュの書き換えごとにメモリも書き換える方式です。確実で制御が簡単という利点があります。 「ライトバック」方式は、キャッシュの追い出しのときにデータが書き換わっていればメモリに反映させる方式です。メモリへのアクセスが少なくて済む利点があります。
通常よく利用されるのはライトバックのようです。
（この項は「コンピュータアーキテクチャの話」の第143回を読んで解釈したものです。）
キャッシュは大きければ大きいほどヒット率が上がりますが、しかし小さければ小さいほどアクセス速度が上がります。 このバランスを取るために、最近の CPU はほとんどが多階層のキャッシュを持っており、CPU に近い順から
CPU <-> L1 キャッシュ <-> L2 キャッシュ <-> ... <-> Ln キャッシュ <-> メモリ
のような構成を取ります。
「コンピュータアーキテクチャの話」の 2008/12/22 時点では『近年の高性能マイクロプロセサでは、ほぼ例外なく2階層のキャッシュが用いられており』ということでしたが、最近(2018/10 現在)だと個人用 PC でも L3 キャッシュは特に珍しくなくなっています。
（この項は「コンピュータアーキテクチャの話」の第145回から第146回を読んで解釈したものです。）
近年の OS 上で動くプログラムでは通常、メモリの実際のアドレス（物理アドレス）ではなくプログラム（プロセス）ごとに割り振られた仮想アドレスを使ってメモリにアクセスします。 （必要になった経緯のマルチタスクやセグメントの話や、それを行っている MMU や OS 上での扱いなどは、キャッシュの話からずれていくので調べていません） このときページという単位（x86 でいえば 4 KiB）でデータを扱い、プロセスごとに Address Space IDentifier 略して ASID という識別子で空間を区別して、ある ASID に対応する仮想アドレスの 1 ページめは物理アドレスのここからここまで、というように対応表を作ることになります。
この表をページテーブルといい、ページテーブルの高速化のためのキャッシュを Translation Lookaside Buffer 略して TLB というそうです。 また命令列つまりプログラムのために利用する部分を Instruction TLB 略して ITLB、データのために利用する部分を Data TLB 略して DTLB と分類します。 アドレス空間は（特に 64 ビット OS では）広大でページテーブル全体を確保するのは無駄なので、部分的に区切って確保するようになっています。