ユメのチカラ: Linux Kernel 2.6.18とCache Pollution Aware Patch

日	月	火	水	木	金	土
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30	31

9月20日に最新のLinuxカーネルが公開された。最近ではだいたい3ヶ月程度で新バージョンが公開されているというペースである。

2.6.12 2005/06/17
2.6.13 2005/08/29
2.6.14 2006/10/28
2.6.15 2006/01/03
2.6.16 2006/03/20
2.6.17 2006/06/18
2.6.18 2006/09/20

実はこのバージョンには、わたしが書いた cache pollution aware patch というのが入っている。パッチそのものは昨年の今頃に書いたもので、すぐにAndrew Mortonのmmツリーと呼ばれるものにはマージされたのであるが、Linus Torvaldsの本家のツリーにはなかなかマージされていなかった。

Cache Pollution Aware Patchというのは、一言で言うと、コンピュータの中央処理装置(CPU)にはキャッシュというメモリアクセスを高速化するハードウェアが付いているが、ちょっとしたトリックを使って、その処理をさらに高速化するというものである。

コンピュータはムーアの法則によって約18ヶ月で半導体の集積度を倍に向上させてきた。CPUの処理速度もそれに比例して年々向上してきた。メモリの速度はCPUの処理速度の向上に比べ遅いペースで向上してきているので結果としてCPUから見てメモリアクセスというのは遅い処理に見えてくるようになった。

最近のプロセッサだとメモリへのアクセスは200〜300クロック程度かかる。CPUクロックが2GHzのマシンだと1クロックあたり0.5nsec(ナノ秒=10億分の1秒)なので、100nsec〜150nsecかかる。それでも随分速いように思えるが、レジスタへのアクセスが2クロック程度なので100倍程度遅いことになる。

そこで、遅いメモリとレジスタの間にキャッシュと呼ばれる容量は小さいけど高速のメモリを置き、メモリアクセスを高速化する。1次キャッシュ(L1と呼ぶ)はインテルのPentium 4だと8KB(キロバイト)で202クロック程度でアクセスできる。キャッシュにデータが載っていればメインメモリにアクセスするより10100倍程度速くアクセスできる。

キャッシュのサイズは小さいので、どのようなデータをキャッシュに載せ、どのようなデータをキャッシュに載せないのかが性能を左右することになる。必要なデータがキャッシュにある時、それをキャッシュにヒットしたとよび、キャッシュにない時、キャッシュミスしたとよぶ。

性能を向上させるためには、いかにしてキャッシュミスを減らすか(キャッシュヒットを増やすか)というのが重要になってくる。

どのようにキャッシュにデータを載せるかというアルゴリズムは広く研究されている。通常はCPUがメモリにアクセスする時、まづキャッシュに当該データが載っていないか調べ、載っていればキャッシュからデータをとってきて(速い)、載っていなければ、メモリにアクセスし(とても遅い)、キャッシュに載せる。わざわざキャッシュに載せるのは、一度アクセスされたデータは近い将来またアクセスされるかもしれないので、それを期待してとりあえづキャッシュに載せておくのである。これを時間的局所性があると言うが、これは思いのほか上手くいく戦略である。

またメモリからキャッシュにデータを載せる時、アクセスするメモリの周辺のデータも一緒に持ってくる。Pentium 4の場合、64バイトないし128バイトをキャッシュに載せる。これはあるデータにアクセスしたらその近傍のデータにもアクセスする可能性が高いと仮定していて、そのような性質を空間的局所性があると言うが、これも思いのほか上手くいく戦略である。

メモリアクセスのスピードとCPUの性能向上のギャップは年々拡大傾向にあるので上手にキャッシュを利用するアルゴリズムは益々重要になってきている。

さてCache Pollution Aware Patchなのであるが、キャッシュポルージョン(cache pollution)というのは、キャッシュにデータを載せる時、キャッシュのサイズは限られているのでキャッシュ上のデータを捨てないといけないが、その時、すぐに利用される有効なデータを追い出してしまい、結果としてすぐにキャッシュミスを発生させるような状況をさす。

時間的な局所性がない(すぐに再度アクセスされない)データをキャッシュに載せるのはキャッシュポルージョンを発生させるのでよろしくない。

時間的な局所性があるのかないのかというのは通常はなかなかよくわからないのであるが、今回のパッチの作成にあたっては、oprofileというカーネルプロファイリングツールを利用して、カーネルのどこでキャッシュポルージョンが発生しているかを特定した。厳密に部位を特定できたのでパッチの作成そのものはそれほど困難ではなかった。

インテルのPentium4/Xeonプロセッサはデータをアクセスする時にキャッシュをバイパスする命令がある。今回のパッチではカーネル中のキャッシュポルージョンを発生している部分でキャッシュをバイパスする命令を利用しキャッシュポルージョンを効果的に削減した。

iozoneというベンチマークを利用した性能評価ではwrite()システムコールにおいて約10%の性能向上が確認できた。

Linux Kernel 2.6.18
http://www.kernel.org/pub/linux/kernel/v2.6/linux-2.6.18.tar.bz2
http://www.kernel.org/pub/linux/kernel/v2.6/ChangeLog-2.6.18

Cache Pollution Aware Patch (わたしが作ったパッチ)
http://kernel.org/git/?p=linux/kernel/git/torvalds/linux-2.6.git;a=commit;h=c22ce143d15eb288543fe9873e1c5ac1c01b69a1

未来のいつか/hyoshiokの日記
cache pollutionに関する記述がいくつかある。
http://d.hatena.ne.jp/hyoshiok/searchdiary?word=cache%20pollution

2005年度オープンソースソフトウェア活用基盤整備事業
「OSS性能・信頼性評価／障害解析ツール開発」
OS層
〜CPUスケーラビリティ評価編〜
http://www.ipa.go.jp/software/open/forum/development/download/051115/OS-cpu.pdf