Dijkstra 法がなぜ並列処理に向かないか?
※[2010/09/21 9:00] 用語を「並列」(parallel) に統一しました. まだ「並行」「並列」「分散」の使い分けがいまいち飲み込めてないので, 変だったらツッコミをいただけると幸いです.
さてここでは前のエントリで書いた Dijkstra アルゴリズム がなぜ Hadoop などの並列処理に向かないかを書いていきます.
玉入れとリレー
まずは比喩で話を進めていき, 並列処理に向いているアルゴリズムとそうでないアルゴリズムの区別を考えていきましょう.
運動会の種目から「玉入れ」と「リレー」という 2 つの競技を取り上げます. これらはどちらも団体でそれぞれ入れた玉の数やタイムを競うものです.
ただし, 同じ団体競技でもその性質は違います.
玉入れは競技人数を増やせば増やすほど得点の期待値は上がります. 例えば, 10 人で玉入れをしているチームと 20 人で玉入れをしているチームが競争すれば, 20 人のチームの方が断然有利でしょう. さらに 40 人, 80 人と増やしていけば, 落ちている玉を拾うコストがボトルネックになるまでスケールアウトできます.
極端なことを言えば, 玉入れの玉や籠を増やすという手段も採れます. こうしてしまえば際限無く得点の期待値を上げていくことができます.
逆に, リレーでは人数を増やしても玉入れほどには劇的にはタイムの期待値は上がりません. スタートとゴールがあらかじめ決められてしまっているため, 増えた人数の分だけ 1 人あたりの距離が短くなります. ある程度までは選手の疲労が少なくなる効果でタイムは伸びるでしょうが, すぐにバトンパスのコストがボトルネックになりタイムは落ちていくはずです.
そして, 玉入れの玉や籠を増やすようなボトルネックの解消手段がありません.
玉入れとリレーの違いは??
さて, なぜ玉入れとリレーでスケールアウトする/しないが分かれたのでしょうか?
それは処理の性質にありました.
玉入れでは玉が十分に転がっていれば玉を取り合うこともなく, 別の人の動作が自分の動作をじゃましません.
しかしリレーでは, バトンという 1 つしかないリソース (Singleton!) に対して各選手が処理を行っているため依存関係が生じ, どうしてもそれぞれの処理を並列で動かすことができません.
これを小難しく数式で書くとアムダールの法則とグスタフソンの法則になります. とは言ってもこの式は算数レベルの話なので, 覚えるほどの価値はありません. 式の字面を覚えるのではなく「並列処理基盤に載せても, 並列に処理できるとこしか処理時間の圧縮はできないよ」という式の意味の方を, 自分の言葉で噛み砕いて脳みそに染み込ませておきましょう. どうせ現実問題はこれより複雑で, とうてい計算なんぞできる代物ではないので.
余談ですが, 最近拾った面白い話にこんなのがありました.
秀吉とMapReduce : サルノオボエガキ
これも見事に部下の人数に対しスケールアウトするようにジョブを組んだ秀吉の頭脳の勝利と言えるでしょうか.
Dijkstra 法を復習
前置きがだいぶ長くなりましたが, 「処理の順序に依存関係があるかどうか?」という視点で Dijkstra 法を見ていきましょう.
Dijkstra 法では「スタートノードからの距離が最小のものから順に, 最短経路を確定していく」のでしたね. 忘れていたら前回のエントリで復習しておいてください.
以下のようなグラフに対して Dijkstra アルゴリズムを適用します.
まずスタートノードへの最短経路が決定します. 今回からは最短経路が決まったノードには色を付けていくことにします.
次に, 最短経路が決定したノードたちから 1 ステップで行けるノードのうち, スタートノードからの距離が最短のノードを探します.「い」ノードが選ばれ, 最短経路「S→い」, 最短距離 1 が確定します.
さらに同様に処理をしていくと,「は」への最短経路「S→は」と「S→い→は」, 最短距離 2 が確定,
「ろ」への最短経路「S→は→ろ」, 最短距離 3 が確定,
「に」への最短経路「S→は→に」, 最短距離 4 が確定,
「ほ」への最短経路「S→は→ろ→ほ」, 最短距離 5 が確定,
となり無事全てのノードの最短経路と最短距離が求まりました.
途中説明を省略したところはちょうど良い練習問題なので, どういったアルゴリズムで決定されていったか考えてみてください.
(というのが講義などでの便利な言い回しですよね〜.)
どこがボトルネックなのか?
さてここで問題ですが,「上の Dijkstra 法での解放では S, い, は, ろ, に, ほ, の順に最短経路が決まっていったが, この順序は前後することがあるか? もしくは前後させることができるか?」についてはどうでしょう?
つまり, Dijkstra 法は「玉入れ」なのか「リレー」なのか? という問いです.
答えは少し下に書くのでちょっと考えてみてください.
分かりましたか? 答えは「リレー」です.
その理由も答えられますか?
Dijkstra 法のポイントは, 『まだ最短経路が決定していないノードのうちスタートノードからの最短距離が「最短なもの」』を選んでいくことにあります. 最短という言葉がたくさん出てきましたが, 着目すべきは鉤括弧でくくった「最短なもの」です.
並列処理が得意な処理は, 小分けにできてそれぞれが独立している処理です. しかしこの Dijkstra 法では各ステップは「最短なもの」という 1 つしかないものを扱うことになります. 1 つのものはどうやったって小分けにはできません.
確かにどれが「最短なもの」かどうか調べるのに並列処理が使えますが, 最短かどうか比較するデータが全て出揃わないと「最短」が決定できません.
こういった他の処理の待ちが発生してしまってはせっかくの並列処理の恩恵が減ってしまいます.
ちょっと難しい言い方をすると,「ローカルな処理に還元するのが並列処理の特徴なのだが, グローバルなデータが必要になってしまってそのメリットを阻害している」となります.
(ちょっと自信が無いのですが, 「グローバルなデータ」の「グローバル」は CAP 定理 (仮説) で言うところの Consistency でしょうか?)
かと言って勝手に処理を進めてしまっては,「最短なもの」だと思って処理を進めていたが実は違った, という事態が発生し計算のやり直しになります.
どう解消したらいいのか?
上で述べた通り, そもそもアルゴリズムが並列処理に向いてないので, そのまま使うのは諦めます. (これこそ CAP 定理か?)
今欲しい並列処理のメリットは速度なので, そのために以下のデメリットを甘受します.
- 解の完全性を捨てる
- 対象とするグラフを絞る
1 番目の方法は, 最短経路が完全に決まる前に「これが最短なものだ」と仮定して, 次の探索を始めてしまう方法です. この方法ならそこそこ速く解が求まりますが, 再計算が必要になる可能性があるのが痛いところです.
2 番目の方法は, グラフの形をある程度規定してしまってアルゴリズムのチューニングをする方法です. 「解の完全性」と「求解のスピード」のトレードオフをチューニングする感じです.
ここから先はさらに個別の話になるので, また次の機会に記事を書こうと思います.
コメントでも Twitter でも感想もらえると嬉しいです! さらなる要望だともっと嬉しいです!!
つ【http://twitter.com/cocoatomo】
それではっ!
