ここ数日、キャッシュのカラーリング(Cache Colouring)について資料を読み漁っていたので、まとめておこうと思う。
ベースの資料としては、以下が参考になると思う。
キャッシュ・カラーリング、もしくはページ・カラーリングという技法を理解する為には、まずはキャッシュの構造について理解する必要がある。
CPUにおけるメモリアクセスの方法にはいくつかあるのだが、やらなければならないことは決まっていて：
この2つの項目は、どの順番でやっても何とかなる。しかし一般的には：
- アドレス変換を行ったのち、物理アドレスを使用してL1Dキャッシュにアクセスする
- 後述するPIPTという方法を使ってL1Dにアクセスする
- アドレス変換とL1Dキャッシュへのアクセスを同時に行う
- 後述するVIPTもしくはVIVTという方法を使ってL1Dにアクセスする
両者の違いは、L1Dキャッシュへのアクセスをどのように構成するか、というのが異なる。以下の3種類に分類されるだろう。
- PIPT (Physically Index, Physically Tag)
- VIPT (Virtually Index, Virtually Tag)
- L1Dのインデックスは仮想アドレスを使用する
- L1Dのタグチェックは物理アドレスを使用する
- アドレス変換とキャッシュアクセスを同時に行うことができるため、レイテンシを短くできる
- VIVT (Virtually Index, Virtually Tag)
- L1Dのインデックスは仮想アドレスを使用する
- L1Dのタグチェックは仮想アドレスを使用する
- 物理アドレスを使用しないので最もシンプルだが、いろいろ弊害がでる
使い分けというのは微妙なところだが、いろいろ文献を探っていると、L1Dキャッシュの場合はVIPT、L2キャッシュの場合はPIPT、L1IキャッシュはVIVTで作られることもある？という感じだ。
やはりL1Dキャッシュの場合はアクセスレイテンシが重要となるので、VIPTによりアドレス変換とL1Dアクセスを同時に行う、というのがセオリーのようだ。ただし、Armのドキュメントを読んでいるとARMv7ではL1DキャッシュをPIPTで作るという記述もあり、いろいろと手法は分かれているようだ。
PIPTとVIPTによるキャッシュ構成の違い
PIPT方式とVIPT方式でどのようにL1D構成が変わるのかということだが、まずはキャッシュにアクセスするためのインデックスの作り方が異なる。
PIPTの場合は、変換済みの物理アドレスの下位ビットの一部を用いて生成する。
- キャッシュサイズが32kB, キャッシュブロックが32Bの場合、全体で1024個のブロックが用意されていることになる
- さらに2-way Associativeの場合、キャッシュブロックの格納候補は2つある
したがって、キャッシュブロックを格納する場所は、 を必要とする。キャッシュブロックのサイズが32Bなので、物理アドレスの下位5-bitは使用せず、物理アドレスのビット位置
[13:5]をインデックスとしてキャッシュにアクセスすることになる。
一方、VIPTの場合は少し事情が異なる。VIPTの仮想アドレスを用いてアクセスする。同様に仮想アドレスの[13:5]を用いてアクセスすればよいと思うかもしれないが、そのようにすると問題が発生する。
例えば、仮想アドレス0x1000と0x2000が、同様に物理アドレス0xC000に変換される状況を考える。仮想アドレス0x1000は、[13:5]を取り出して0x8をキャッシュインデックスとして使用するが、仮想アドレス0x2000は0x10をキャッシュインデックスとして使用する。
しかし、この2つは結局同じ物理アドレスを参照していることになり、結果としてL1Dキャッシュに同一物理アドレスのキャッシュブロックが2つ存在してしまうことになる。
これは、例えば0x1000を用いてキャッシュのデータを更新するのと、0x2000を用いてキャッシュのデータを更新するのが別々に行われてしまうので、データの不整合が生じてしまい問題となる。
つまり、仮想アドレスと物理アドレスの間ではアドレスの12ビット目よりも上が異なる可能性があることが問題となる。VIPTにおいてページオフセットの部分(12ビット以下)を使うとこの問題は発生しないが、そうするとオフセットの領域のみ(12-bit → 4kB)のサイズしかキャッシュを作ることができず、キャッシュサイズを大きくすることができない。
これを解決するためにはいくつかの方法があるのだが、これは次に書くことにする。
