OProfile

OProfile http://sourceforge.net/projects/oprofile/ を利用するとキャッシュミスの場所を特定してくれる。非常に簡単に特定してくれるのでそれをヒントにいろいろ性能向上をはかれる。もちろんOProfileの限界もいろいろある。OProfileはキャッシュミスのイベントの「どこ」を特定するが「なぜ」は教えてくれない。それは自分で考えないといけない。write cache missかread cache missかも教えてくれない。（IA-32のイベントマスクをちゃんと設定すると教えてくれるかもしれないと、この日記を書いていて思いついたが、あとで調べることにする）
キャッシュミスの時間的局所性についても教えてくれない。あるデータへのアクセスがキャッシュミスをしてその結果そのデータがキャッシュにのったとして、そのデータへのアクセスがキャッシュにのっているとき再度発生すれば時間的局所性があったといい、キャッシュにのっているときに一度もアクセスが発生しなかったら時間的局所性がないと言う。でもって、あるデータがキャッシュミスをしたときにそいつに時間的局所性があるのかないのかというのはOProfileは教えてくれない。誰も教えてくれない。
理想的なメモリトレーサなるものがあったとして、すべてのメモリアクセスを記録していたとする。そうするといつの時点でキャッシュミスがおこりそのキャッシュミスが時間的局所性を持つか持たないかは分かる。時系列ですべてのメモリアクセスを記録しているのだから、どのキャッシュミスはなんでおこったかも分かる。しかしそのようなツールはシミュレータ以外ない。メモリトレーサの実行コストは非実用的なくらい高いからである。
時間的局所性があるというのがあらかじめ分かっているのならprefetchでもしてlatencyを隠蔽すればいいし、時間的局所性がないならキャッシュにのせないという作戦をとれる。(cache pollution aware patchは時間的非局所性を利用した初めて（？）のカーネルパッチである）
時間的非局所性もまったく二度とアクセスしないという絶対的な時間的非局所性から、何度かアクセスするのだけどアクセスする頻度がキャッシュのサイズを超えていてキャッシュからあふれるという非局所性まで様々である。後者の場合はアクセスの距離（一度アクセスしてから次にアクセスされるまでの時間）を減らす方法はいろいろ考えられる。まあいづれにせよ理想的なメモリトレーサがなければそのようなことは簡単にはわからない。
今回OProfileの枠組みでできる可能な限り（？）のことをいろいろ試したがread cache missとwrite cache missの区別ができたのは実に簡単なことでmovslというメモリからメモリへのMOVE命令をmov src, eaxみたいな、メモリからレジスタへの命令(readにあたる)と、movnti eax, dstというレジスタからメモリへの命令(writeにあたる)へ分解したからである。
時間的局所性があるかないかというのはOProfileの結果からは分からないのでひたすらソースコードを分析するしかない。（直感的に）
いままでキャッシュミスといえばprefetch位の方法しか提案されていなかったのは、キャッシュミスの場所がわかればとりあえづprefetchでもしてlatencyを隠すかぐらいしかできなかったからである。現実問題としてツールで測定できるのはキャッシュミスくらいしかなかったからと言っても過言ではない。アクセス（キャッシュミス）の距離をはかるメモリトレーサがあるかは知らないが（あったら教えてほしい）、Intelとかは当然詳細なイベントトレーサは持っているだろうがそのようなツールは門外不出だし素人が使いこなせるものでもないのでOProfile程度のツールを利用してあれやこれや試みるのが精一杯である。