« LingrTickr - 誰でもニコニコメソッドプレゼン | メイン | 倉庫番solverをちょっと Erlangっぽく »

Erlang で分散してみたくて倉庫番solver

Erlang の「軽量プロセス間の非同期 tuple メッセージのやりとりによる分散」というのが今やっていることの色々参考になるんじゃないかという気がして、少し勉強ということで "Programming Erlang" をせっせと読んでみました。

#Erlang のメッセージは別に tuple じゃなくてもなんでも送れます。一応念のため。

いきなり余談。"Programming Erlang" の書籍版はまだ出てないんですが、直販で $45.95、amazon.com だと $36.95 なのに、amazon.co.jp だと ¥7264 もするのはなぜ!? まあ、PDF版 ( $22.50 ) を買ったので関係ないんですが。 (5/18 追記:Amazon に Programming Erlang をリコメンドされたのでふと見てみたら¥4,118 になってました。これなら書籍でも良かったかな~)
ちなみに、PDF 版を購入すると特典として「全ページ」に自分の名前を入れてくれます(笑)。買ってからダウンロードできるまでにえらい時間かかるなあと思ったらそんな事してたのね。

閑話休題。中谷は何か作ってみないとわからない人なので、分散に向いている何か題材は……という頃合いに こんな記事 を見かけてしまうわけです。
あー大昔に作ったなあ。あの頃は X68000 だったのでメモリがなく、深さ優先で作るしかなかったんだけど、200~300歩クラスの問題なら解けるところまではなんとかたどり着いたなあ(しみじみ)。

というわけで、「分散対応 倉庫番 solver for Erlang」です。
まあ Erlang の勉強の題材としてということなので、単純幅優先&枝切り無しという solver としてはおもちゃなレベルなんですが、荷物3、4個の問題ならだいたい十数秒クラスで解けます。
注目を浴びている理由の 対C10K なネタじゃなくてすいません(笑)。

ソース: solver2.erl

関数型言語でまともにコードを書くのは初めてなので(XSLT除く)、おいおいなんだこりゃというところがぽこぽこあるでしょうが、生暖かくスルーするか添削してもらえると嬉しいです……

まずはシングルプロセスでの実行方法。
# カレントに solver2.erl を置いて、erlang を起動
$ erl

% モジュール読み込み
> c(solver2).

% 組み込まれているテスト用問題の解法を実行
% ######
% #@  .#
% # +++#
% # . .#
% ######"
> solver2:test4().
solution: 22 steps ([{5,3,"v"},{4,3,"^"},{4,2,">"},{3,3,"v"}]), goal (3, 3)
solution: 22 steps ([{5,3,"v"},{4,3,"^"},{3,3,"v"},{4,2,">"}]), goal (4, 2)
finish.

% 自分で問題を指定して解法を実行
% ##########
% #@.. #   #
% # +++    #
% ##.  #####
% ######    
% ・制限歩数 50
% ・自ノードで1プロセス実行
% 解法は複数出力されます。最短解法のみコピペ。
> solver2:start( [{self,1}], 
>  ["##########","#@.. #   #","# +++    #","##.  #####","######    "], 
>  50).
solution: 35 steps ([{4,3,"v"},
                     {5,3,">"},
                     {3,3,">"},
                     {4,4,"<"},
                     {4,3,"^"},
                     {6,3,">"},
                     {7,3,">"},
                     {8,3,"<"},
                     {7,3,"<"},
                     {6,3,"<"},
                     {5,3,"<"},
                     {4,2,"<"},
                     {4,3,"^"}]), goal (4, 3)
問題は下記のように記述します。ちなみに上記問題は自作w
プレイヤー初期位置がゴール上な場合が記述できないですが、まあいいや。
 # : 壁
 @ : プレイヤー初期位置
 + : 荷物
 . : ゴール
 * : ゴール上にある荷物
解法結果は(歩数、解法履歴、最終のプレイヤー位置)が出力されます(最終のプレイヤー位置は意味なかったなあ……)。
解法履歴は荷物の座標と、その荷物をどの方向に動かすかで表示されています。座標は左上を(1,1)としています。


では、続いて分散実行の方法。
# マシン2にてノード名とクッキーを指定して erlang 起動
# 以降、マシン2は手を触れる必要はありません。
# マシン2台無ければ同じマシンでも可
$ erl -name sokoban2@192.168.0.2 -setcookie solver

# マシン1にてノード名とクッキーを指定して erlang 起動
# setcookie には上と同じ値を指定
$ erl -name sokoban1@192.168.0.1 -setcookie solver

% マシン1にてモジュール読み込み
> c(solver2).

% マシン1にて分散解法実行
> solver2:start( [{self,1}, {'sokoban2@192.168.0.2',1}], 
>    ["##########","#@.. #   #","# +++    #","##.  #####","######    "], 
>    50).
start() の第1引数で {ノード名, プロセス数} を列挙することで、指定されたノードにて分散解法が開始されます。モジュールは自動的にマシン1からマシン2に渡されて読み込まれるようになっているので、マシン2は本当に erlang を起動しておくだけでOKです。
手元の環境では上記問題は1台実行で11秒、2台実行で7秒だったので、確かに分散の効果ありありって感じです(笑)。

というわけで、ここからはプログラムの説明。


分散ノードを指定して実行した場合、プロセスの構成は以下のようになっています。
manager
 ├server1(self: 'sokoban1@192.168.0.1')
 │ ├ solver1
 │ ├ solver2
 │ └ solver3
 └server2('sokoban2@192.168.0.2')
    ├ solver4
    └ solver5
solver は実際の解法処理を行うプロセスで、start() の第1引数にて指定したプロセス数の分だけ立ち上がります。

solver はまず直上の server に request メッセージを送って問題(枝)を要求、server は手持ちの問題があれば solver に solve メッセージで返し、無ければ manager に request を送って要求します。
manager は request を受け取ったら、別の server に手持ちの問題がないか request を送り、add メッセージで返ってくればそれを要求側に返し( add )、無ければ(タイムアウトしたら)また別の server に問い合わせます。

solver は問題を受け取ったら( solve )、押せる荷物のリストを作成、それぞれの荷物を移動させたものを新しい問題として server に返し( add )、また新しい問題を server に要求します( request )。

主要なメッセージを図示するとこんな感じ。実際には他にも解けた場合のメッセージや、終了する場合のメッセージなどがあります。
solver_message.png

solver が受け取るメッセージは solve しかなく、メッセージループが短くてちょうどいいので、簡単に見てみます。
solver_loop(Server, TIMEOUT, COUNT) ->
  receive
    {solve, PRE_BRANCH, Maxsteps, Parcels} ->                   % server から solve 受け取り
      BRANCHES = solve(Server, PRE_BRANCH, Maxsteps, Parcels),  % 解法 -> 新しい枝リスト
      if length(BRANCHES)>0 -> Server ! {add, BRANCHES};        % 新しい枝を server に返す
        true -> pass end,
      Server ! {request, self()},                               % 次の枝を要求
      solver_loop(Server, 1000, COUNT+1)

    after TIMEOUT ->
      erlang:monitor(process, Server),
      receive
        {'DOWN',_,_,_,_} -> exit(self())
      after 500 -> ok
      end,
      Server ! {request, self()},
      solver_loop(Server, TIMEOUT+1000, COUNT)
  end.
solver_loop() の引数は(親 server の Pid、タイムアウト、処理した枝数)となっています。
これらは process dictionary に積んだ方がいいのかなあと思いつつ、Erlang にはステートが無かったんと違ったん? 的疑問から逃れられなくて、引数で持ち回るようにしてしまいました。

receive {solve, PRE_BRANCH, Maxsteps, Parcels} -> で server からの solve メッセージを受け取ります。
PRE_BRANCH の中にマップの現在の状態、プレイヤーの位置、歩数、履歴などが格納されているので、これを solve() にて解かせます。
solve() 関数は解法処理そのものですが、分散まわりとは関係ないので説明省略(笑)。新しい枝のリスト BRANCHES が返ってきますので、これを Server ! {add, BRANCHES} としてサーバに送りつつ、Server ! {request, self()} で新たな問題を request しています。

とても簡単な構造で分散が実現できているのがわかるんじゃないでしょうか。

ちなみに、after は solver がひまひましててタイムアウトした場合の処理です。
主にまだ枝数が少なくて回っていない序盤や、解き終わって処理する枝が残っていない終盤にあたりに仕事が回ってこない可能性があるので、そこら辺を意識した処理が書かれています。


親 server は solver と同じ node 内にありますが、server と manager は別々のノードにあることもあります。
でもこの場合でも相手の Pid さえ持っていれば、メッセージ送信は同じノードか別のノードかを全く意識することなく、 Pid ! message で送ることが出来るので、とてもプログラムしやすかったです(違いはプロセスを起こすときの spawn にノードを指定する引数を付けるか付けないかだけ)。

逆に、困ったのがメッセージの送信そのものは成功・失敗を拾えないところ。エラーハンドリングは対象となるプロセスを別途監視することで行う(監視方法は色々用意されている)のですが、間接的になるため、いろいろなケースを考えると複雑にならざるを得ず。まあ、メッセージ送信そのものについてもハンドリングするとなると、そのIDが必要となり……と今のシンプルなメッセージングがスポイルされてしまう可能性も高いので、難しいところではあります。
でも、同期メッセージとかもあると、やっぱりちょっと嬉しかったかも。

トラックバック

このエントリーのトラックバックURL:
http://labs.cybozu.co.jp/cgi-bin/mt-admin/mt-tbp.cgi/1263

この一覧は、次のエントリーを参照しています: Erlang で分散してみたくて倉庫番solver:

» 倉庫番とそのソルバーの情報まとめ 送信元 神は細部に宿り給う
第8回 倉庫番を解くアルゴリズム:ITpro  これをきっã... [詳しくはこちら]

コメントを投稿