ラズパイクラスタマシン
N-Prologの分散並列機能を利用してラズパイクラスタマシンで並列動作するPrologを動かしました。そのことについて書き記します。
題材
巡回騎士問題を題材としました。巡回騎士問題とはn*nの盤面がナイトの駒がすべて通過するような経路を求めるものです。５＊５の盤面でテストしました。
ナイトは8方向にジャンプすることができます。それを25か所について確認することになります。8^25通りの経路が考えられます。もっとも盤面の外になってしまうジャンプを除外しますからそれよりは小さくなります。それにしても膨大な試行錯誤をすることになります。
以下はし逐次処理の普通の巡回騎士問題を解くコードです。巡回騎士問題にはヒューリスティックな最適化の手法があるのですが、今回は敢えてそれを使わないことにします。
% tour start from (R,C), X is path
tour(R,C,X) :-
move(R,C,[[R,C]],X).
safe(R,C) :-
R >= 1,R =< 5,
C >= 1,C =< 5.
move(_,_,P,P) :-
length(P,25).
move(R,C,P,A) :-
R1 is R+2,
C1 is C+1,
safe(R1,C1),
not(member([R1,C1],P)),
move(R1,C1,[[R1,C1]|P],A).
move(R,C,P,A) :-
R1 is R+1,
C1 is C+2,
safe(R1,C1),
not(member([R1,C1],P)),
move(R1,C1,[[R1,C1]|P],A).
move(R,C,P,A) :-
R1 is R-2,
C1 is C-1,
safe(R1,C1),
not(member([R1,C1],P)),
move(R1,C1,[[R1,C1]|P],A).
move(R,C,P,A) :-
R1 is R-1,
C1 is C-2,
safe(R1,C1),
not(member([R1,C1],P)),
move(R1,C1,[[R1,C1]|P],A).
move(R,C,P,A) :-
R1 is R+2,
C1 is C-1,
safe(R1,C1),
not(member([R1,C1],P)),
move(R1,C1,[[R1,C1]|P],A).
move(R,C,P,A) :-
R1 is R+1,
C1 is C-2,
safe(R1,C1),
not(member([R1,C1],P)),
move(R1,C1,[[R1,C1]|P],A).
move(R,C,P,A) :-
R1 is R-2,
C1 is C+1,
safe(R1,C1),
not(member([R1,C1],P)),
move(R1,C1,[[R1,C1]|P],A).
move(R,C,P,A) :-
R1 is R-1,
C1 is C+2,
safe(R1,C1),
not(member([R1,C1],P)),
move(R1,C1,[[R1,C1]|P],A).
５＊５の場合には4隅に解があることがわかっています。左上の(1,,1）から経路を探索させてみます。
?- tour(1,1,X).
X = [[5,1],[4,3],[5,5],[3,4],[1,5],[2,3],[4,2],[2,1],[1,3],[2,5],[4,4],[5,2],[3,1],[1,2],[2,4],[4,5],[3,3],[5,4],[3,5],[1,4],[2,2],[4,1],[5,3],[3,2],[1,1]] .
yes
?-
?- measure(tour(1,1,X)).
Elapsed Time=1.538875 (second) 1939469(LIPS)
X = [[5,1],[4,3],[5,5],[3,4],[1,5],[2,3],[4,2],[2,1],[1,3],[2,5],[4,4],[5,2],[3,1],[1,2],[2,4],[4,5],[3,3],[5,4],[3,5],[1,4],[2,2],[4,1],[5,3],[3,2],[1,1]] .
yes
?-
デスクトップ機でおよそ1.5秒かかっています。Prolog世界の事実上のスタンダートであるSWI-Prologは高速です。
?- time(tour(1,1,X)).
% 2,564,759 inferences, 0.166 CPU in 0.166 seconds (100% CPU, 15459352 Lips)
X = [[5, 1], [4, 3], [5, 5], [3, 4], [1, 5], [2, 3], [4, 2], [2|...], [...|...]|...] .
?-
0.166秒と高速です。30年以上にわたり最適化を繰り返してきたSWIです。なかなかこの速度は出せません。
ラズパイクラスタマシンで挑戦
N-Prolog ver4.61で分散並列機能が安定してきました。これをつかってクラスタマシンをつくり、並列Prolog専用機としました。下記は分散並列の機能をつかって4台の子機で計算するコートです。
ptour4(R,C,X) :-
dp_or([pmove1(R,C,X),pmove2(R,C,X),pmove3(R,C,X),pmove4(R,C,X)]).
pmove1(R,C,X) :-
(R1 is R+2,C1 is C+1,move(R1,C1,[[R1,C1],[R,C]],X);
R1 is R+1,C1 is C+2,move(R1,C1,[[R1,C1],[R,C]],X)).
pmove2(R,C,X) :-
(R1 is R-2,C1 is C-1,move(R1,C1,[[R1,C1],[R,C]],X);
R1 is R-1,C1 is C-2,move(R1,C1,[[R1,C1],[R,C]],X)).
pmove3(R,C,X) :-
(R1 is R+2,C1 is C-1,move(R1,C1,[[R1,C1],[R,C]],X);
R1 is R+1,C1 is C-2,move(R1,C1,[[R1,C1],[R,C]],X)).
pmove4(R,C,X) :-
(R1 is R-2,C1 is C+1,move(R1,C1,[[R1,C1],[R,C]],X);
R1 is R-1,C1 is C+2,move(R1,C1,[[R1,C1],[R,C]],X)).
８方向を４つのグループに分けてdp_or/1で分担して計算しています。もっとも早くに答えを出してきた子機の答えをもって結果とします。計算途中の子機はその時点で強制停止させます。計算結果は下記の通りです。
?- dp_consult('./tests/knight').
yes
?- ptour4(1,1,X).
X = [[1,5],[2,3],[3,5],[5,4],[4,2],[2,1],[3,3],[4,5],[2,4],[1,2],[3,1],[5,2],[4,4],[2,5],[1,3],[3,4],[5,5],[4,3],[2,2],[4,1],[5,3],[3,2],[5,1],[3,0],[1,1]] .
yes
?- measure(ptour4(1,1,X)).
Elapsed Time=0.162186 (second) 151338(LIPS)
X = [[1,5],[2,3],[3,5],[5,4],[4,2],[2,1],[3,3],[4,5],[2,4],[1,2],[3,1],[5,2],[4,4],[2,5],[1,3],[3,4],[5,5],[4,3],[2,2],[4,1],[5,3],[3,2],[5,1],[3,0],[1,1]] .
yes
?-
ラズパイ4Bを使っています。ラズパイのCPU性能がデスクトップ機の1/10程度しかないことに留意してください。それにもかかわらずSWIと同程度のタイムを出しています。
分析
上記の場合だとpmobe3/2の場合が最も早くに答えがみつかります。それがさきほどの結果となっています。このように並列を使えばラズパイでもSWIに匹敵あるいは超える性能が出すことがわかりました。
弱点
とはいっても弱点もあるのです。(1,2)からスタートした場合には巡回騎士の答えはありません。この場合には全部を探索することになります。ラズパイはCPUパワーが1/10程度でありL3キャッシュをもっていません。こういう長大な計算になるとぐっと分が悪くなります。それでも分散しているのでいくらかは高速になります。
SWIは(1,2)からの巡回に答えがないことをわずかな時間で求めています。
?- time(tour(1,2,X)).
% 143,618,366 inferences, 9.138 CPU in 9.138 seconds (100% CPU, 15716620 Lips)
false.
?-
１５メガLIPSを出しています。キャッシュを活かしているのでしょう。すばらしい性能です。こうなるとラズパイではまったく歯が立ちません。
可能性
答えがある経路についてはSWIを上回る結果を出すことができました。このことが何かの役に立たないか、応用はないのかと考えています。
実験につかったN-PrologはOSSです。下記にて公開しています。よかったらラズパイで分散並列Prologをお試しください。