Cache Coloring / Page Coloring について (2. VIPTにおけるキャッシュサイズを大きくするための手法)

では、VIPTにおいてキャッシュのサイズを大きくするためにはどうすればよいのか。

1つ目の方法は、キャッシュのWayサイズを増やしていくという方法だ。上記の構成において、2-way Associativeから8-way Associativeに変更すると、キャッシュインデックスのビット長を変えずに、ウェイサイズを4倍に大きくすることでキャッシュサイズを4倍にできる。この方法は、単純で分かりやすいが、ウェイサイズが増えるので実装の複雑性が増えてしまい、例えば理論上最大サイズである4kBの大きさから64kBまでサイズを増加するとウェイのサイズを16倍に大きくしなければならず、回路の複雑性が大きく増加してしまう。

2つ目の方法は、インデックスにおけるページオフセットよりも大きなビット位置を「カラービット」として扱うことだ。上記の構成ならば、[13:5]のうち、[13:12]をカラービットとして扱う。カラービットが2ビットなので、同一物理アドレスに割り当てられる可能性のある仮想アドレスは4種類あるということになる。[13:12]=0, [13:12]=1, [13:12]=2, [13:12]=3 の4つを用いて、キャッシュ内の4つの領域に割り当てられる可能性があるということだ。

キャッシュサイズをさらに倍にすると、カラービットは3ビットとなり、8つの領域に対して割り当てられる可能性がある。

とりあえずこのカラービットを用いれば、異なる仮想アドレスが同一の物理アドレスに割り当てられた場合でもなんとかなる。

L1DはVIPT、L2はPIPTで動作することを仮定すると

1. あるプロセスが、VA=0x1000 / PA=0xC000でアクセスする
   1. カラービットは上記のとおり’b01
   2. キャッシュミスが発生し、物理アドレス0xC000でL2にアクセスされる
   3. L2から取得したデータはカラービットを用いてL1Dのインデックス0x80へデータの書き込みを行う
2. 別のプロセスがVA=0x2000 / PA=0xC000でアクセスする
   1. カラービットは上記の通り’b10
   2. L1Dにアクセスするがキャッシュインデックスは0x100のため、L1Dミスが発生しL2に要求が伝達される
   3. ところがL2は当該物理アドレスのキャッシュがすでにL1Dに載っていることを知っているので、スヌープバスを用いて当該データをL1Dから抽出しようとする
   4. L2は最初の0xC000へのアクセスにおいて、カラービットが’b01であることを覚えており、したがってL1Dをスヌープするためのキャッシュインデックスは’b01とオフセットアドレスの情報を用いて生成する
   5. L2が呼び戻したキャッシュブロックは再びL1Dに書き込まれるが、この時はカラービット’b10を用いてキャッシュインデックス0x100に書き込まれる

とりあえずはこれで何とかなる。この場合、2つのプロセスが同じ物理アドレスに別のアドレスから交互に頻繁にアクセスすると、L2を介したスヌープで何度もキャッシュブロックが行き来することになり、全体的な性能の低下は避けられない。

ソフトウェアのページ割り当てに手を加えて、これを解決する、という方法もある。このカラービットを活用して、ソフトウェアを活用して割り当てる場所を制限するということになる。つまり、メモリアロケータは、仮想アドレスのカラービットの部分が、物理アドレスのカラーの位置に相当するビットが常に同一であるようにページを割り当てるということだ。

この手法についてはあまりよく分からなかったのだが、そもそも一度ページを割り当ててしまうと、別のプロセスの仮想アドレスが自由にキャッシュインデックスを作ってしまうとページアロケータはどうにもできなくなってしまうので、これを具体的にどうやるのかはよく分からない。もうちょっとソフトウェア側の詳細を調べてみる必要がありそうだ。