cache conflict - 未来のいつか/hyoshiokの日記

id:hyoshiok:20050825 の続き。アプリケーションレベルでハードウェアキャッシュを意識することはまあそうそうないが（それよりも計算量の少ないアルゴリズムを考えろつーことだ）OSだとその手のことをいろいろ考えないといけない場合が多くなってきた。spinlockなんかはメインメモリに必ずアクセスしに行くのでコストの高いオペレーションだということがよく知られているし、ロック競合を減らすためにもspinlockをいかにして減らすかということがカーネルプログラマの興味の中心（？）だったりもする。
とはいうものの、多くのプログラマはハードウェアキャッシュのことを意識していない。例えば、メモリに対するアクセスコストは等価だと仮定してプログラミングするが、（多くの場合はそれで十分なのだけど）、ハードウェアキャッシュとメインメモリへのアクセスは100倍以上コストが違う。メモリアクセスは非常に遅いのである。
プログラムの字面ではほとんど同じものが、一方はキャッシュにのって非常に高速で、一方はキャッシュにのらないために低速であるということがあるのだが、それを発見することはなかなか直感的には難しい。そこでoprofileのようなツールが必要になってくるのだが、まだまだその利用は一般的とは言えない。
http://www.labs.fujitsu.com/jp/techinfo/linux/usenix2002/での富士通の研究はキャッシュミスが多発している場所を専用ハードウェアを利用して発見したものだ。http://lc.linux.or.jp/lc2002/papers/yamamura0919h.pdfにLinux Conferenceでの発表資料が公開されている。キャッシュミスを発見しそれをカラーリングと呼ばれる手法で解決している。メインメモリへのアクセスはキャッシュに保存されるわけであるがその場所はメインメモリのアドレスによって決定される。例えば2次キャッシュが512KBで8 way associativeだとすると、512/8=64KBごとに同じキャッシュラインに乗ることになる。1次キャッシュは8KBで4 wayだとすると2KBごとに同じキャッシュラインにのる。ということは、あるアドレスが2Kで割ったあまりが同じであれば同じキャッシュにのる。例えば

        for (j = 0; j < SIZE; j++) {
          dst[j] = src[j];
        }

というコードは仮にsrcとdstが2KB離れているとキャッシュ的には非常にたちの悪い性質をもったりする。一つの解決策は、dst[]の先頭アドレスをキャッシュラインのサイズだけずらすというのがある。

int src[SIZE];
char pad[LINE_SIZE];
int dst[SIZE];

この手のテクニックによってキャッシュミスが劇的に減る場合があるのである。これを応用したのがカラーリングとして知られるテクニックである。
先の富士通の研究はLinux カーネルのスケジューラにキャッシュコンフリクトを発見し、それをカラーリングによって削減するというもので、2.4カーネルでは非常に効果があったのだが2.6カーネルではO(1)スケジューラになったため、そのようなボトルネック（キャッシュコンフリクト）がそもそも発生しなくなった。そのため、彼らの作ったパッチは本家にはマージされていない。キャッシュミスが多発した場合、それがこのようなキャッシュコンフリクトが原因であるのか、キャッシュポルーション(cache pollution)すなわちキャッシュにのせなくてもいいものをせっせとキャッシュにのせているために発生しているのかを見極めることは簡単ではない。彼らはバスを監視する専用ハードウェアを作ってそれを可能にした。
カラーリングで防げるキャッシュコンフリクトをoprofileで指摘することは実は難しい。というのはoprofileではキャッシュミスを多発している場所を指摘はできるが、その時どのアドレスにアクセスしているかのデータは取得できない。つまり、あるアドレスパターンが同じなので同じキャッシュラインに乗ってしまってキャッシュコンフリクトが発生しているかどうかを厳密に判定することができないのである。（残念）oprofileではキャッシュミスを多発しているEIP(命令ポインタが示すアドレス）をサンプリングするが、その時点のEAX/EBX/ECX/EDX/ESI/EDI等々を取得できないので、どこのデータにアクセスしているかは簡単にはわからないのである。とはいうもののキャッシュミスが多発している場所を発見できればそれの界隈のソースコードをじっくり読んで原因を追究することは簡単ではないけど不可能ではない。キャッシュミスのパターンを理解すればカラーリングでいけるのかノンテンポラルなMOVE命令を利用することでいけるのかはおのずと見えてくると思う。
未踏で開発したhardmeter http://hardmeter.sourceforge.jp というツールはキャッシュコンフリクトも発見できるのだが、その当時、Linux Kernelでこれほど簡単にcache pollutionが発見できかつ簡単に解決できるとは思い至らなかった。修行が足りなかったのである。http://hardmeter.sourceforge.jp/prosym.pdfにその当時の理解が記してあるので参考にしてほしい。私自身はまだまだ進化中である。
またまた今回作ったパッチのお話にたどり着く前に紙面が尽きてしまった。そのうち書きます。