Cache pollution
今年の夏は朝から晩までLinux Kernelのチューニングをやっていた。端的に言うとLinux kernelでキャッシュミスが多発しているところを発見してそれを解消するパッチを作ったので、その評価をひたすらやっている今日この頃である。 http://marc.theaimsgroup.com/?l=linux-kernel&m=112489315002172&w=2
cache pollutionという話題は昔からよく知られている話題なのであるがOSのカーネルをそれを防止することによって性能向上を図るという話は、どうなんだろうか、わたしの不勉強かもしれないがあまりないような気がしている。
最近のプロセッサではMMX/SSEみたいなマルチメディアストリーミング対応の命令セットが実装されているが、それとの絡みでcache pollutionの話題が出てくるが、Linuxカーネルではその手の命令を使わないので時々誰かが話をふるが放置されるという感じらしい。
CPUのキャッシュというのはという話題はかつてふれたような気がするので自分のはてな日記を検索すると、http://d.hatena.ne.jp/hyoshiok/20040730でふれている。すっかり忘れていた。先日のYLUGカーネル読書会で今回の件を小ネタとして紹介したのだが、そのときもかつて塚本さんにお話してもらっていたことをすっかり忘れていた。
10.5.5 Cache Management Instructions *1
The non-temporal move instructions (MOVNTI, MOVNTQ, MOVNTDQ, MOVNTPS, and MOVNTPD) allow data to be moved from the processor’s registers directly into system memory without being also written into the L1, L2, and/or L3 caches. These instructions can be used to prevent cache pollution when operating on data that is going to be modified only once before being stored back into system memory. These instructions operate on data in the generalpurpose, MMX, and XMM registers.
このノンテンポラルMOVE命令というのがきもである。
cache pollution というのはメモリからデータをアクセスするとき通常はメモリからレジスタにデータを移送するだけでなくキャッシュという高速のメモリにデータを置いておく。そうすると次回同じアドレスにアクセスしたとき高速にアクセスできるので実行性能が向上する。同じアドレスにアクセスする場合はいいのだが、ストリーミングデータのようにシーケンシャルにアクセスするだけで同じところには再びアクセスしない場合、無駄にキャッシュを使うので本来キャッシュ上に残しておきたいデータまで追い出されてしまう。これをcache pollutionという。上記のnon-temporal move 命令は一次キャッシュ、二次キャッシュ、三次キャッシュなどにデータを書き込むことなくメモリにダイレクトに書き込むのでcache pollutionを起こさない。
でもって、今回ひたすらベンチマークをやってカーネルのボトルネックを探しているときにたまたまcache pollutionを発見したので、このノンテンポラルMOVE命令を利用してみたところキャッシュミスが激減して性能も向上した。まあ言ってしまえばそれだけのことである。
通常アプリケーションの性能向上をはかる場合、性能上のボトルネックを発見し、それに対応する対策をしてというのを繰り返すわけだが、対策も、１）アルゴリズムやデータ構造の変更により計算量を変えるアプローチ、２）アルゴリズムやデータ構造の変更ではなく局所的な変更による改良によるアプローチとがある。
前者は計算量が変わるので場合によっては劇的に性能向上がはかれたりするが、よいアルゴリズムを発見することはなかなか難しいし、改造量も大きくなりがちで実装の手間ヒマが非常にかかったりする。お手軽ではない。
一方で後者のアプローチはもっとちまちました改良を積み重ねるという地味な方式である。ロック競合が起きているところを発見してそれを改良したり、ループで時間がかかっていたらそのループを減らすことを考えたりとか、瑣末なことの積み重ねである。
OSのスケジューラのスケーラビリティがないのでそれを抜本的に改良したO(1)スケジューラの導入というのはまさに前者の例で計算量がO(n)からO(1)に変わってしまった。この手の大物の導入というのはそうそうあるものではない。
カーネルのチューニングの多くはもっとちまちましたものの積み重ねである。今回のパッチもそのようなものの一つである。
さてなぜキャッシュに注目したチューニングが重要か簡単に記しておく。
CPUは年率50%の割合で性能向上している。一方でメモリはせいぜい年率7%くらいの性能向上と言われている。その結果、CPUとメモリの性能は年々広がってきている。CPUからみるとメモリは相対的にどんどん遅くなってきているのである。（メモリの大規模化は性能向上には足かせになるのである。）この性能上のギャップを埋めるのがキャッシュと呼ばれるハードウェアである。Intel Pentium4やXeonの実装ではL1キャッシュ（一次キャッシュ）は8KBで2 clocksでアクセスできる。2GHzのマシンだと1ns（ナノセカンド、10億分の一秒）でアクセスできる。L1は速いが小さい。L2(２次キャッシュ）は512KBで10nsくらいでアクセスできる。L1に比べれば大きいけどメインメモリに比べれば非常に小さい。メインメモリは最近では4GB程度あるのも全然珍しくない。L2に比べて1000倍以上でかい。そのアクセススピードは200〜300 clocksくらいかかる。L1に比べれば100倍遅いのである。CPUが高速になればなるほどメモリアクセスは高価になってくるのである。メモリアクセスの間CPUはやることがなくなってぶらぶらすることをさけないといけない。性能向上をはかるには、いかにしてキャッシュミス（速度低下をもたらす）を下げるかが課題になる。
プログラマの視点からキャッシュミスを考えるというのは非常に難しい。というのはプログラムの字面を追っているだけではどこでキャッシュミスが起こるか起こらないかというのは全然見えてこないからだ。アルゴリズムを計算量で評価するのは比較的たやすい。入力に対して出力を得るまでどれだけの計算量が必要かというのはコンピュータサイエンスの基本中の基本である。しかし、コードの字面からキャッシュミスを特定することはほとんど無理である。そのような定番の教科書もないし、考えたこと（？）もないというのが実情だろう。（といってはいいすぎかな？）
今回作ったパッチの説明を書く前に紙面が尽きた（？）のでそれについては後日記す。（かもしれない）
