Cache Pollution
延々とcacheネタですまぬぅ〜（ぺこり）The IA-32 Intel(R) Architecture Software Developer's Manual, Volume 3: System Programming Guide *1 の10章がメモリキャッシュコントロールの章である。その図10-1を見るとBus Interface Unit というのにキャッシュやらStore Bufferやらがくっついていて、システムバス経由で物理メモリに接続されている。L1キャッシュの下にL2があってそのまた下にL3があるというのではなく、Bus Interface Unitに直接それぞれがくっついているという感じである。
今回作ったcache pollution aware patch がなぜ有効かという話をする前に準備としていろいろ理解しておかないといけない。
CPUがデータをキャッシュ可能なメモリに書くとき、最初にそのメモリのキャッシュが存在しているかチェックする。もし有効なキャッシュが存在していれば（現在の書き込みポリシーに依存するのだが）、CPUはシステムメモリではなく、キャッシュにデータを書き込む。これをwrite hitと呼ぶ。もし書き込みがキャッシュをミスしたら（有効なメモリのキャッシュが存在しない）、CPUはcache line fill, write allocationする。cache line fillというのはメモリから適当なキャッシュへキャッシュライン分読み込むことである。Pentium 4だと64バイト一気にキャッシュに読む。そしてデータをキャッシュに書き込む。そしてそれをメモリへ書き出す。もしデータがメモリへ書き出されるとしたら、最初にstore bufferに書き出され、その後store bufferから、システムバスが利用できるようになった時、メモリへ書き出される。*2
キャッシュにのったデータがすぐに利用されれば（読み込まれれば）、メインメモリまでアクセスしにいかないので性能向上につながる。これを時間的局所性があるという。時間的局所性がない場合は性能向上にはつながらないことに注意しよう。例えば、あるデータを足したり引いたりして、その結果を同じアドレスに戻す場合を考えると、データを読むときにはキャッシュミスをするかもしれないが、すぐに書きだせばライトヒットする。別のアドレスに書き出す場合はライトミスをするかもしれない。
さてデータをコピーすることを考える。通常、データのコピー元のアドレスとコピー先のアドレスは異なる。（当り前だ）コピー先のアドレスは多くの場合、ライトミスをする。このコピー先のデータがすぐに利用されなければ、（すなわち時間的局所性がなければ）、有効なキャッシュを追い出すことになる。これがcache pollution（キャッシュを無効なデータで汚染してしまう）である。コピー先のデータがすぐに利用されるかされないかはそのプログラムを書いた人にしかわからないが、時間的局所性がないとわかっているのなら、このcache pollution を避けるのは簡単である。データをコピーして書き込む時、キャッシュをバイパスすればいいのである。そうすれば、キャッシュには有効なデータが残る。
さて、ライトミスなのだが、これは結構コストが高い。
- 犠牲となるキャッシュラインを選ぶ。
- もしダーティなキャッシュラインならメモリへ書き出す。
- キャッシュラインフィルするためにメモリを読む。
- キャッシュへ書き込む。
犠牲となったキャッシュラインがすぐさま利用されるとしたら目も当てられない位性能に悪影響がでる。これがcache pollutionなのである。
さて、ここでキャッシュをバイパスするとどうなるか？上記のライトミスがまったく発生しないだけではなく、cache pollutionもなくなる。ただ犠牲となったキャッシュのうちどれだけがすぐに利用されるデータであったかは簡単にはわからない。いっぱい、すぐに利用されるかもしれないし、利用されないかもしれない。後者の場合はキャッシュの汚染はなかったということである。
oprofileを利用するとその汚染度が簡単にわかる。手順としては、
- L3キャッシュミスの回数を測定する。
そうするとキャッシュミスを多発しているルーチンがわかる。copy_from_user_ll()という、ユーザー空間からカーネル空間へデータをコピーするルーチンだ。copy_from_user_ll()はほとんどライトミスである。
- 改良版のL3キャッシュミスの回数を測定する。
copy_from_user_ll_nocache()が改良版のルーチンだ。そのキャッシュミスの回数はほぼ0。最初のキャッシュミスの総数をAとして当該ルーチンのキャッシュミスの回数B、改良版のキャッシュミスの総数をCとすると、
A = B + C + cache pollutionの回数
ゆえにcache pollutionの回数は A - B - Cとなる。そーやって、もとめてみると、
CPU 1 CPU 2 CPU 4
copy_from...() 37142 37314 37125
cache miss 5050 14740 17583
cache pollution 5012 3028 3758
みたいな感じになった。CPUの数を1、2、4と変化させると、通常のキャッシュミスが増えて、相対的にcache pollutionの影響は減少していく。さらにスケーラビリティを向上させるためには、このキャッシュミスの内容を詳細に分析しないといけない。次ぎなる課題というわけである。
*1:http://developer.intel.com/design/pentium4/manuals/253668.htm
*2:10.2 Caching Terminology
