未来のいつか/hyoshiokの日記 このページをアンテナに追加 RSSフィード Twitter

2006-04-22

萌えーー

やはり萌えである。未踏ソフトウェアの喜連川PMの採択者が集まって同窓会をした。最近IT研究開発といえば萌えである。データベース研究情報爆発というキーワードのもとGoogle的なアプローチに収斂しつつあるような印象を持つ。これもウェブ進化論の功罪なのかもしれないけどデータベース関連の研究費というのはほとんど情報検索とかGoogle的なものに集中している。喜連川先生研究室学生も未踏関連のプロジェクトメンバーも元気のいい研究者を根こそぎGoogle雇用している。(やっぱお金のあるところは強いよねという世界観

Web2.0というファンシーなキーワード学生が集中する。その時々の流行語に学生が集中するのはいたしかたないが一方でBinary2.0のような地味な研究も必要である。わたしみたいにデータベース管理システム(DBMS)がどうだこうだとか、キャッシュミスがどうだとかいう古典的な分野の古典的なテクニックをああだこうだするということの価値を大学先生は伝えないといけないとは思う。思うのだけどなかなかそうはいかないところに大学のジレンマがある。(教育の問題である)

キャッシュがどうだという話はたまたま喜連川先生趣味に合致したので未踏に採択されたがそうでなければ未踏にも採択されず今回のCache Pollution Aware Patchの開発も日の目を見なかった。

大学での最先端の研究と現場のプログラマの間には広くて深い谷がある。絶望的なほどの谷がある。

同窓会の前半は各自の近況報告なのであるが、わたしはhardmeterでの経験からoprofileを利用したカーネルチューニングの話をした。write cache missが非常にコストが高いので、それを回避するためにキャッシュをバイパスする命令を利用することによってキャッシュミスを劇的に減らしたという話(Cache Pollution Aware Patch)をした。

Cache Pollutionとか、キャッシュをバイパスするテクニックとかは昔から知られているテクニックで、私が世界で初めて発見したものではない。その意味で学術的な意義はない(新規性はないので論文にはならないのであろう)が、Linuxカーネルでの実装はなかったので実用的な価値は非常に高い。このギャップすなわち学術的な価値はないが実用的な価値はあるというもののギャップは広くて深い。

研究でのアイデアを実装するまでの距離の広さ深さを埋める必要は絶対あると思う。

CPUが増えるとキャッシュミスが増えるというグラフで、喜連川先生の質問が本質を突く。「なぜ、CPUが増えるとキャッシュミスが増えるのですか」

こんな単純な質問もわたしには答えられない。わたしは精密な回答を持たない。世界の誰かはこの質問に定量的に答えられるデータを持っているかもしれないがわたしはその回答を知らない。いくつかの仮説はあげられるがそれをバックアップするような定量的なデータを持たない。

キャッシュミスという観点からCPUスケーラビリティを議論した研究を言うのをわたしは知らない。(いやもちろんキャッシュコヒーレンシーがどうだという研究がいっぱいあるのはさすがに知っていますが…)CPUスケーラビリティとの関連の研究を私が知らないというだけの話であるが、仮にそのような研究があったとしてもそれはLinuxカーネルには適用されていない。研究と実装の間には深い谷がある。

未踏をやっていたときに喜連川先生から質問を受けた。「キャッシュミスを発見したとしてそれをどのように解決するのですか?」それに対する回答がCache Pollution Aware Patchである。それまではキャッシュミスを解決するためにはプリフェッチしかわたしは知らなかったわけではあるが、それ以外にも方法があるというのを今回学んだ。そして喜連川先生の3年前の質問に対して、「キャッシュをバイパスすることによって解決します」という回答を示せた。

ムーアの法則に従ってこの40数年間CPUの性能が向上してきた。これまでは性能向上の方向が周波数向上の方向であった。そのために、CPUの速度とメモリアクセスの速度差が年々広がってきたためにキャッシュアクセスを上手にすることが性能向上につながった。システムの性能向上にはキャッシュアクセスを上手にすることが非常に重要だったわけだ。(過去形か?)

ところが消費電力が増えすぎたためにこれ以上周波数を増やすことが経済的に難しくなってきた。その結果、周波数はそのままでコア数を増やすというマルチコア化が加速している。そのような状況下でシステムの性能向上を目指すためには、キャッシュミスをうんぬんするだけではなく、マルチコア(プロセッサ)でのロックの競合の問題が重要になってくる。(ロック萌え〜

CPUを増やしたときに性能をどのように上げるかという古典的な問題が現代的なコンテキストの元に再度重要になってきているのである。

CPUが増えたらなんでキャッシュミスが増えるのですか?それに回答することをカーネルハッカーは求められている。

性能萌え〜である。

mhiramatsumhiramatsu 2006/04/23 10:28 CPUが増えると他のCPUと共有するキャッシュラインが増え、そのキャッシュラインが他のCPUからinvalidateされやすくなる、ということではないでしょうか。

kosakikosaki 2006/04/23 15:29 その先生の事はまったく知らないのですが、もっと本質的な事を聞いているかもしれませんよ。
たとえばCPUが2つあったとして、それぞれ別のOSが動いているような組み込み的な使い方をしたらキャッシュミスは増えていきませんよね。
つまり複数のCPUからアクセスされうるようなデータ構造をなんでつくるのさ?と。
別のCPUを用途分割するのがいいんだ。といっているのではなく、例えば、スケジューラはper CPUなデータ構造つくってキャッシュミスを減らしていますよね。
スケーラビリティーを損なわない範囲で、データ構造をもっとper CPUなものに落とし込んでいくことがなぜ出来ないのか。
と聞かれているのではないかしら。

ひらひら 2006/04/23 15:57 CPUが増えたらキャッシュミスが増える、というのはちょっと違和感があります。キャッシュミスの増減は、CPUアーキテクチャ(対称型/非対称型など)やカーネルアーキテクチャ(リエントラント/プリエンプティブなど)に依存する話でCPUの数に依存する話ではないように思います。x86+Linuxに限定するとmhiramatsuの意見に同意です。

ひらひら 2006/04/23 16:03 ”さん”を付け忘れました。失礼しましたm(_ _)m >mhiramatsuさん

hyoshiokhyoshiok 2006/04/23 19:40 mhiramatsuさま、コメントありがとうございます。基本的にはその通りだと思うのですが、それを定量的に示すことと、それへの効果的な対応策は?という事が求められているような気がします。

hyoshiokhyoshiok 2006/04/23 19:43 kosakiさま、コメントありがとうございます。スケーラビリティをあげるようなデータ構造、ロック方式、キャッシュに優しいメモリアクセスなどなど

hyoshiokhyoshiok 2006/04/23 19:49 ひらさま、コメントありがとうございます。CPUの数が増えれば独立なプロセス、スレッドが増えるわけですからキャッシュミスは増えるような気がします。それをどう防止するか。

troubleantennatroubleantenna 2006/04/24 01:15 > 研究と実装の谷
現場の人が読んで興味を持てるような論文(新規性は全然なくても構わない)をそこそこリーズナブルなお値段で読める場があればいいんですが、なかなか。。。

hyoshiokhyoshiok 2006/04/24 06:54 troubleantennaさま、コメントありがとうございます。
現場の人向けには雑誌とかWebとかで情報発信なんでしょうね。研究の人と現場の人との交流がもっとあればいいと思うのですが…
データベース学会でやっているPostgreSQLの内部実装のセミナーなんかは両者が交流するいい機会かもしれません。
だけど、仮にPostgreSQLをチューニングしたとしても、学会レベルでは、それはPostgreSQLの実装がだめだったんでしょう、という事になってしまって全然受けない。

HenrichHenrich 2006/05/11 11:26 Cache Pollution Aware Patchのマージの進捗はどうなっているのでしょうか?

hyoshiokhyoshiok 2006/05/12 08:39 Henrichさま、コメントありがとうございます。Andrew Mortonのmm-treeにはマージされています。http://www.kernel.org/pub/linux/kernel/people/akpm/patches/2.6/2.6.17-rc3/2.6.17-rc3-mm1/broken-out/x86-cache-pollution-aware-__copy_from_user_ll.patch
Linus版にはマージされていません。
性能上の悪影響がないことを証明しないとマージしないとLinusさんは言っています。
誰か実用的なベンチマークをしてバックアップをしてほしいなあと他力本願モードがはいってます。

HenrichHenrich 2006/05/12 15:05 http://kerneltrap.org/node/6402 のコメントを見てパッチの状況を知りたく思ったのですが、「Pending a one-at-a-time re-review」のところが証明が必要という意味ですかね。
ベンチマークであればOSDLは何かテストケースを持っていたりはしないのでしょうか。どこか大手ハードベンダ(HP,IBM,NEC,Fujitsu,Hitachiあたり?)が動くようにけしかけてみるのが良いのではないかと思います(といっても私には伝手が無いのですが)。

hyoshiokhyoshiok 2006/06/12 17:33 Henrichさま、コメントありがとうございます。”Will merge-and-see-what-happens I guess.”ということで、とりあえづ入れてみっか、というスタンスみたいですね。さっき、Andrew Mortonがいたので拙い英語で聞いてみましたら、そのような事を言っていました。

hyoshiokhyoshiok 2006/06/27 07:29 Linusのtreeにマージされたようです。
http://kernel.org/git/?p=linux/kernel/git/torvalds/linux-2.6.git;a=commit;h=c22ce143d15eb288543fe9873e1c5ac1c01b69a1