Hatena::ブログ(Diary)

cocoatomo衝動日記

2010-09-20 SSSP と並列処理

[][][] Dijkstra 法がなぜ並列処理に向かないか? 08:11  Dijkstra 法がなぜ並列処理に向かないか? - cocoatomo衝動日記 を含むブックマーク

※[2010/09/21 9:00] 用語を「並列」(parallel) に統一しました. まだ「並行」「並列」「分散」の使い分けがいまいち飲み込めてないので, 変だったらツッコミをいただけると幸いです.

さてここでは前のエントリで書いた Dijkstra アルゴリズム がなぜ Hadoop などの並列処理に向かないかを書いていきます.

玉入れとリレー

まずは比喩で話を進めていき, 並列処理に向いているアルゴリズムとそうでないアルゴリズムの区別を考えていきましょう.

運動会の種目から「玉入れ」と「リレー」という 2 つの競技を取り上げます. これらはどちらも団体でそれぞれ入れた玉の数やタイムを競うものです.


ただし, 同じ団体競技でもその性質は違います.

f:id:cocoatomo:20100920231401j:image

玉入れは競技人数を増やせば増やすほど得点の期待値は上がります. 例えば, 10 人で玉入れをしているチームと 20 人で玉入れをしているチームが競争すれば, 20 人のチームの方が断然有利でしょう. さらに 40 人, 80 人と増やしていけば, 落ちている玉を拾うコストがボトルネックになるまでスケールアウトできます.

極端なことを言えば, 玉入れの玉や籠を増やすという手段も採れます. こうしてしまえば際限無く得点の期待値を上げていくことができます.

f:id:cocoatomo:20100920231546j:image

逆に, リレーでは人数を増やしても玉入れほどには劇的にはタイムの期待値は上がりません. スタートとゴールがあらかじめ決められてしまっているため, 増えた人数の分だけ 1 人あたりの距離が短くなります. ある程度までは選手の疲労が少なくなる効果でタイムは伸びるでしょうが, すぐにバトンパスのコストがボトルネックになりタイムは落ちていくはずです.

そして, 玉入れの玉や籠を増やすようなボトルネックの解消手段がありません.

玉入れとリレーの違いは??

さて, なぜ玉入れとリレーでスケールアウトする/しないが分かれたのでしょうか?


それは処理の性質にありました.

玉入れでは玉が十分に転がっていれば玉を取り合うこともなく, 別の人の動作が自分の動作をじゃましません.

しかしリレーでは, バトンという 1 つしかないリソース (Singleton!) に対して各選手が処理を行っているため依存関係が生じ, どうしてもそれぞれの処理を並列で動かすことができません.


これを小難しく数式で書くとアムダールの法則とグスタフソンの法則になります. とは言ってもこの式は算数レベルの話なので, 覚えるほどの価値はありません. 式の字面を覚えるのではなく「並列処理基盤に載せても, 並列に処理できるとこしか処理時間の圧縮はできないよ」という式の意味の方を, 自分の言葉で噛み砕いて脳みそに染み込ませておきましょう. どうせ現実問題はこれより複雑で, とうてい計算なんぞできる代物ではないので.


余談ですが, 最近拾った面白い話にこんなのがありました.

秀吉とMapReduce : サルノオボエガキ

これも見事に部下の人数に対しスケールアウトするようにジョブを組んだ秀吉の頭脳の勝利と言えるでしょうか.


Dijkstra 法を復習

前置きがだいぶ長くなりましたが, 「処理の順序に依存関係があるかどうか?」という視点で Dijkstra 法を見ていきましょう.

Dijkstra 法では「スタートノードからの距離が最小のものから順に, 最短経路を確定していく」のでしたね. 忘れていたら前回のエントリで復習しておいてください.


以下のようなグラフに対して Dijkstra アルゴリズムを適用します.

f:id:cocoatomo:20100920232446j:image


まずスタートノードへの最短経路が決定します. 今回からは最短経路が決まったノードには色を付けていくことにします.

f:id:cocoatomo:20100920232506j:image

次に, 最短経路が決定したノードたちから 1 ステップで行けるノードのうち, スタートノードからの距離が最短のノードを探します.「い」ノードが選ばれ, 最短経路「S→い」, 最短距離 1 が確定します.

f:id:cocoatomo:20100920233425j:image

さらに同様に処理をしていくと,「は」への最短経路「S→は」と「S→い→は」, 最短距離 2 が確定,

f:id:cocoatomo:20100920232521j:image

「ろ」への最短経路「S→は→ろ」, 最短距離 3 が確定,

f:id:cocoatomo:20100920233548j:image

「に」への最短経路「S→は→に」, 最短距離 4 が確定,

f:id:cocoatomo:20100920232545j:image

「ほ」への最短経路「S→は→ろ→ほ」, 最短距離 5 が確定,

f:id:cocoatomo:20100920232559j:image

となり無事全てのノードの最短経路と最短距離が求まりました.

途中説明を省略したところはちょうど良い練習問題なので, どういったアルゴリズムで決定されていったか考えてみてください.

(というのが講義などでの便利な言い回しですよね〜.)

どこがボトルネックなのか?

さてここで問題ですが,「上の Dijkstra 法での解放では S, い, は, ろ, に, ほ, の順に最短経路が決まっていったが, この順序は前後することがあるか? もしくは前後させることができるか?」についてはどうでしょう?

つまり, Dijkstra 法は「玉入れ」なのか「リレー」なのか? という問いです.

答えは少し下に書くのでちょっと考えてみてください.















分かりましたか? 答えは「リレー」です.

その理由も答えられますか?


Dijkstra 法のポイントは, 『まだ最短経路が決定していないノードのうちスタートノードからの最短距離が「最短なもの」』を選んでいくことにあります. 最短という言葉がたくさん出てきましたが, 着目すべきは鉤括弧でくくった「最短なもの」です.

並列処理が得意な処理は, 小分けにできてそれぞれが独立している処理です. しかしこの Dijkstra 法では各ステップは「最短なもの」という 1 つしかないものを扱うことになります. 1 つのものはどうやったって小分けにはできません.

確かにどれが「最短なもの」かどうか調べるのに並列処理が使えますが, 最短かどうか比較するデータが全て出揃わないと「最短」が決定できません.

こういった他の処理の待ちが発生してしまってはせっかくの並列処理の恩恵が減ってしまいます.

ちょっと難しい言い方をすると,「ローカルな処理に還元するのが並列処理の特徴なのだが, グローバルなデータが必要になってしまってそのメリットを阻害している」となります.

(ちょっと自信が無いのですが, 「グローバルなデータ」の「グローバル」は CAP 定理 (仮説) で言うところの Consistency でしょうか?)

かと言って勝手に処理を進めてしまっては,「最短なもの」だと思って処理を進めていたが実は違った, という事態が発生し計算のやり直しになります.

どう解消したらいいのか?

上で述べた通り, そもそもアルゴリズムが並列処理に向いてないので, そのまま使うのは諦めます. (これこそ CAP 定理か?)

今欲しい並列処理のメリットは速度なので, そのために以下のデメリットを甘受します.

  1. 解の完全性を捨てる
  2. 対象とするグラフを絞る

1 番目の方法は, 最短経路が完全に決まる前に「これが最短なものだ」と仮定して, 次の探索を始めてしまう方法です. この方法ならそこそこ速く解が求まりますが, 再計算が必要になる可能性があるのが痛いところです.

2 番目の方法は, グラフの形をある程度規定してしまってアルゴリズムチューニングをする方法です. 「解の完全性」と「求解のスピード」のトレードオフチューニングする感じです.


ここから先はさらに個別の話になるので, また次の機会に記事を書こうと思います.

コメントでも Twitter でも感想もらえると嬉しいです! さらなる要望だともっと嬉しいです!!

つ【http://twitter.com/cocoatomo

それではっ!

2010-09-17 SSSP と並列処理

[][][] Dijkstra 法がなぜ並列処理に向かないか? 08:11  Dijkstra 法がなぜ並列処理に向かないか? - cocoatomo衝動日記 を含むブックマーク

玉入れとリレー

2010-09-16 需要を感じたので……

[][] 文系 Hadooper でも分かる Dijkstra アルゴリズム 00:30  文系 Hadooper でも分かる Dijkstra アルゴリズム - cocoatomo衝動日記 を含むブックマーク

今日の Hadoop ソースコードリーディングDijkstra アルゴリズムの知名度が低かったので, 解説を書いてみたぜ.

このアルゴリズムを一言で説明すると?

グラフ上のある始点からあるノードへの最短経路とその距離を求めるアルゴリズム.

用語が分かんないんだけど...

グラフというと y = 2x とかを思い浮かべるかもしれないが, この場合の「グラフ」というのは「いくつかの丸 (= ノード, 節) を線 (= エッジ, 辺) でつないだもの」で, 状態遷移図もグラフの一種. 状態遷移図は「有向グラフ」と呼ばる. 丸と丸とをただの線ではなく矢印でつなぐので「有向」=「向きが付いている」と言う.

"DAG" は "Directed Acyclic Graph" の略で「非循環有向グラフ」と訳される. "Directed" と "Acyclic" の順序が逆になってるのは気にせんでくれい.

このアルゴリズムの目的って?

概要で書いた通り, このアルゴリズムの目的はある地点への最短経路を求めること.

特徴としては, 探索が終わったときには全ノードへの最短経路が求まっている. つまり, あるゴールへの最短経路だけを求めたい場合には無駄な処理をしている可能性がある.

では, すっごく単純な例から.

f:id:cocoatomo:20100917002539j:image

上の図ではノードが 2 つで, 左のノードが始点 (スタートノード) だ.

Dijkstra 法ではまず始点から 1 ステップで到達できるノードを調べるぞ. 今回は調べる対象が右のノード 1 つしかないので, 1 回の探索で終了だ. もちろん, 右のノードへの最短経路は唯一あるエッジでその距離は 1 だ.

ちょっとだけ複雑に.

f:id:cocoatomo:20100917003600j:image

「って, どこが複雑やねん!? バカにしんといて!!」という声が聞こえますが, あーあー聞こえない(-"-;

今回はノードが 3 つで, スタートノードの他にノード「い」とノード「ろ」がある. Dijkstra 法では始点から 1 ステップで到達できるノードが複数あるときは, 始点に最も近いノードをまず選ぶ.

「選んでどうするんだ?」と思ったかな? 実はその選んだノードは最短経路が確定するんだ. 今回の例で言えば, 始点から「い」へは距離 3, 「ろ」へは距離 2 なので,「ろ」への最短経路「S → ろ」が確定してその距離は 2 だ.

次は, 最短経路が確定している「S」と「ろ」から 1 ステップで到達できるノードを調べる. (「S」への最短経路は「動かないこと」で距離は 0 ね.) この例では「S」から「い」へ到達できる経路しかないので, これが選ばれる.

選ぶ基準はちょっと複雑で「スタートノードからの最短距離が最短なもの」となる. これについては後の例で解説する.

「ろ」への最短経路「S → ろ」が確定し, 全てのノードへの最短経路が確定したので Dijkstra 法終了!

ほら, この例だけでもステップは複雑になったでしょ? この例の手順を理解すると後が楽だよ.

さらに複雑に. 経路が複数ある!

f:id:cocoatomo:20100917005823j:image

今回は前回の例に 1 本エッジを足してみた例だ.

これまで解説した部分は今後はさらっと流すことにする.

まず「ろ」の最短経路「S → ろ」が確定し, 最短距離が 2 と分かる. 次に「い」への最短経路を調べるのだが, 最短距離が確定しているノードから「い」へ到達する道が 2 つある. 「S → い」と「ろ → い」だ.

「そんなん『S → い』を選ぶに決まっとるやん!」というツッコミはスルーして, 丁寧に選択しよう.

ここで 2 つの経路を選ぶ基準は「スタートノードからの最短距離が最短なもの」だった. この例では「S → い」が距離 3, 「S → ろ → い」が 4. 「S → い」の方が短いので, こっちが最短経路として確定する. これで Dijkstra 法は終了.

この丁寧な選択は問題が複雑になってきたときに非常に効くし, ここが Dijkstra 法のキモだと言っていい.

さらっと次の例に. 本格的な例.

f:id:cocoatomo:20100917010706j:image

ノードが 1 つ増え, エッジが 3 つ増えたな. この例が分かれば, 一般のグラフの場合を理解できるはず.

では手順の解説. まず「S」から最も近い「ろ」への経路が決定する.

次が複雑だ! 重要だ!

最短経路が求まっているノードは「S」と「ろ」. するとそれらから 1 ステップで行けるノードは「い」と「は」. まずはスタートノードからそれぞれへの最短距離を求める.「い」は「S → い」の距離 3. 「は」は「S → は」が距離 4,「S → ろ → は」が距離 3 なので, 「S → い」と「S → ろ → は」の経路がそれぞれ「い」と「は」への最短経路だと確定する.

『「は」へ到達するルートは「S → い → は」も残ってるじゃないか!?』というツッコミに対してちょっと解説すると, Dijkstra 法の探索は始点からの距離が短い順に行っている. だから常に「最短距離が確定したノードへの距離」は「最短経路が確定していないノードへの距離」より短いのだ. これを保っているルールがさっきの「スタートノードからの最短距離が最短なもの」を選んでいくというやつだ.

それで計算する間でもなく「S → ろ → は」が「は」への最短経路だと分かる.

そろそろ Dijkstra 法の感覚が掴めてきたかな??


これでアルゴリズム初心者向けの解説は終了. アルゴリズムの実装は http://www.deqnotes.net/acmicpc/dijkstra/ とかを見てくれれば良いはず.

最後に

自分は数学を専攻していたのだが, こういう専門知識を分かりやすく解説するという仕事も自分の責務だと思っている. それが大学, 大学院という穀潰し生活をさせてくれたことへの恩返しだなぁと最近は感じている.

なので, 「ここが変だ」「ここが分からん」「この話題も解説せい」等のツッコミ・要望は大歓迎. コメントに書くのが気が引ける場合は Twitter でどうぞ.

つ【http://twitter.com/cocoatomo

yutuki-mnyutuki-mn 2010/09/17 12:27 手書きの図がw

cocoatomococoatomo 2010/09/18 12:00 > id:yutuki-mn

はてダの新機能でブログでお絵描きができるようになったみたいです.
図を書くには手書きが一番速いですよ.

yutuki-mnyutuki-mn 2010/09/18 12:06 お絵かき機能とIDコールという二つの新機能をしりますた

liquidfuncliquidfunc 2010/09/21 02:06 "ダイクストラ法(最短経路問題)"という文字列含んでおいたほうが、初心者へのアプローチとして易しい(題名読むだけでどんなアルゴリズムか把握できますよね)し、SEO的にも有効だと思いました。あと本質と逸れますが、半角の句読点ははてダだと(プロポーショナルフォントになるからかな)見にくくなってしまいますね。わざわざIME設定変えるの面倒でしょうけど

名無し名無し 2010/11/21 02:50 とてもわかりやすかったです。助かりました。