« 日本語は英語より速く読める? | Main | 生物内での量子もつれ »

現実のアプリケーションはこれからも勝手に疎結合になっていく ---そしてmap-reduceこそが並列処理の王道

まあ以下の文章をダシにする必要は無い内容になっちゃったけど:

さてHadoop関連の某セミナーへの参加者が900人を越えたそうです。個人的にはHadoopを必要としている人、またはHadoopに関わる人というのはそれほど多くないと思うのですがね。HadoopのもととなったMapReduceは良くも悪くも、きわめて癖が強い分散処理手法。それをベースにしたHadoopも当然、汎用的なシステムではなく、データ特性や処理内容を選びます。どちらかというと既存のデータ処理に問題を抱えている方で、その中で問題解決にHadoopがたまたま向いている方になると思うのですがね。

それとHadoopを使うと分散システムは様々な難しい問題を解決すると思っている方が多いのも気になります。分散システムのは難しい問題のほとんどは、元を辿れば通信遅延に起因します。つまりコンピュータ間で情報共有する場合、他のコンピュータに関しては恒に過去の情報しか知り得ないということです。これは光が有限速度で進むのと同じで、物理的制約なので根本的に解決することはできず、その通信遅延の影響を見えないようにするのが限界です。

佐藤一郎:web日記(9/13)

「MapReduceが極めて癖が強い」と言うのは適用できるデータや処理内容の範囲がせまいという意味なのだろうけど、それは違うと思う。map-reduceで処理できる範囲と言うのは、実はかなり大きいのではないか。(ここで、正確に言うと私はmapReduceの中身まで知っているわけではないので、ここではmapとreduceで解ける並列的な問題という意味でmap-reduceと言う。)

大きな計算量を必要とする問題は三つに分類できると思う。効率のよいアルゴリズムが存在しそれを上手に並列に分解する方法が分かっている問題、効率のよいアルゴリズムが存在するけど上手に並列化できない問題、効率のよいアルゴリズムが存在せず総当たりせざるをえない問題。
上手に並列化できる問題とは、つまり問題を疎結合にすることに成功した問題であり、疎結合の極限がmapだ。少し工夫すれば極限でなくともある程度mapにできるだろう。また反対に上手なアルゴリズムが見つかっていない問題と言うのは総当たりで解かざるをえない問題だが、総当たりもmap-reduceに適している。つまり両方の極端が適している。

さて、振り返ってみれば、昔80年代だって並列マシン特に万単位のマイクロプロセッサからなる並列マシンは構想されていた。で、その時はとても実用にならないとして捨てられていた。

しかしいま、まさに実用になっている。で、それは何か並列処理の理論にブレークスルーがあったか?No. ブレークスルーなどない。ハードウェアの進歩のせいか?No. CPUのクロックに対する通信レイテンシやband widthの比はむしろ悪化している。ではなぜ?

単にプロセッサの能力が上がって問題の規模が上がったために問題の方が疎結合になったからだ。現実世界の問題は大きくなる程、疎結合になる傾向があるからだ。昔のアプリケーションは皆問題が小さかった、だから密結合だったのだ。

例えば単純に3次元空間の中で時間発展する流体力学のような問題を考える。CPUの能力が16倍になると、メッシュを時間空間方向に2倍にすることができる。CPUは3次元空間と同じトポロジで隣のCPUとやり取りすれば良い。すると通信量は、表面積4倍時間2倍で、8倍になる。すると通信量/計算量の比は減少していることになる。

LINPACKベンチマークとして使われる行列演算でさえ同じように行列が大きくなると疎結合になりマルチプロセッサに分解しやすくなる傾向がある。

こんな感じで問題の疎結合性は年とともに勝手に上がっている。またデータマイニングなどの近年新しく登場したアプリケーションなども疎結合の傾向がある。

どうも現実世界の問題と言うのは計算量が巨大になる程、疎結合になって並列な問題に分解しやすくなるのは一般的な傾向であるようだ。

それは生物にさえ言える。たとえば、ネズミの脳と人間の脳をくらべてみる。人間が17cmくらいかな、ラットの脳は1.2cmくらい。人間の脳の体積は2000倍くらいある。ここで皮質の面積は長さの2乗で効く、そして体積は長さの3乗で効くのが基本だ。表面には皮質が、内部の体積には白質つまり配線がある。従って神経細胞に対して繊維の量が1.5乗で増えることになる。実際には、ラットにはしわがないのに対して、人間のにはしわがあるので、さらに落ちる。知らないけど多分1.3乗とかそんな感じ。
で、繊維が脳の全体に対して投射しているとすると、繊維の長さは脳全体の長さに比例するから、繊維の本数は(繊維の体積/繊維の長さ)でなんと0.3乗に比例することになってしまう。神経細胞が演算、繊維が通信に対応するとすると、やはり通信/演算は 0.3 - 2 乗以下だということになる。これは恐ろしいほど疎結合だ。実際には一つのニューロンが受けるシナプスの数はむしろわずかに増えていることから長距離の投射はなくて、近距離の投射が人間では増えていることを示している。
これはなおさら、人脳が疎結合化されサブシステムに分解された問題を解いていることを意味している。実際、ネズミの脳に比べて領野の分割がはっきりとし、領野の数が増えていることが疎結合型のdivide and conquer型のアーキテクチャであることを証明している。

(現実の世界の問題は巨大であると同時に疎結合だ。ごく最近CPUがGHzになって初めてコンピュータは現実の世界の巨大な問題を解く事ができるようになった。だから疎結合でよい。それ以前のコンピュータは能力が低すぎて現実の問題を解く事はできず、マルチタスキングがどうのテキスト処理はどうのというコンピュータの為に作られた(離散記号からなる)問題を解くのに使われていた。現実でなかったから主要な問題が疎結合でなかったのだ。)

というわけで、コンピュータに要求される現実の問題は今後ますます勝手に疎結合になっていく。そして疎結合の程度が非常に高まったものはmapとreduceで始末することが可能になる。

このようにして将来に向かってさらにmapとreduceみたいなもので解ける問題のclassは増大していく。

だからmap-reduceは特殊な狭いものとは言えない。




もっとも同じ佐藤氏の記述(3月2日)

ただそれ以外の分散処理もなんとかMapReduce/Hadoopに集約する方向にいく可能性はあります。

とあるのは、佐藤氏もmap-reduceが主流になる可能性を考えているのかも。

|

« 日本語は英語より速く読める? | Main | 生物内での量子もつれ »

Comments

納得できない私は無能なのかも

Posted by: やさわ | October 17, 2011 at 11:53 PM

The comments to this entry are closed.

TrackBack

TrackBack URL for this entry:
http://app.cocolog-nifty.com/t/trackback/31362/52971186

Listed below are links to weblogs that reference 現実のアプリケーションはこれからも勝手に疎結合になっていく ---そしてmap-reduceこそが並列処理の王道:

« 日本語は英語より速く読める? | Main | 生物内での量子もつれ »