並列の効果の測定
自作のN-Prologに分散並列の機能を追加しました。これを使うとどのような効果があるのか？Queens問題を解いてその性能を測定することとしました。
並列版のコード
１０Queensによることとしました。並列に分解するために１～10を先頭要素に持つようにコードを分解しました。[1,2...,10]のリストからN番目を取り除き、それについてQueens問題を解いたものにNを追加することで答えを得ています。比較のために逐次実行のコードも併記します。
% 10-queens program in parallel
%parallel 10queens
para :- dp_and([test1,test2]).
test1 :- queens1,queens2,queens3,queens4,queens5.
test2 :- queens6,queens7,queens8,queens9,queens10.
queens1 :- pqueen(1,[2,3,4,5,6,7,8,9,10],X),fail.
queens1.
queens2 :- pqueen(2,[1,3,4,5,6,7,8,9,10],X),fail.
queens2.
queens3 :- pqueen(3,[1,2,4,5,6,7,8,9,10],X),fail.
queens3.
queens4 :- pqueen(4,[1,2,3,5,6,7,8,9,10],X),fail.
queens4.
queens5 :- pqueen(5,[1,2,3,4,6,7,8,9,10],X),fail.
queens5.
queens6 :- pqueen(6,[1,2,3,4,5,7,8,9,10],X),fail.
queens6.
queens7 :- pqueen(7,[1,2,3,4,5,6,8,9,10],X),fail.
queens7.
queens8 :- pqueen(8,[1,2,3,4,5,6,7,9,10],X),fail.
queens8.
queens9 :- pqueen(9,[1,2,3,4,5,6,7,8,10],X),fail.
queens9.
queens10 :- pqueen(10,[1,2,3,4,5,6,7,8,9],X),fail.
queens10.
pqueen(N, Data, [N|Out]) :-
pqueen_2(N, Data, [N], Out).
pqueen_2(_, [], _, []).
pqueen_2(N, [H|T], History, [Q|M]) :-
qdelete(Q, H, T, L1),
nodiag(History, Q, 1),
pqueen_2(N, L1, [Q|History], M).
% sequential 10queens
seq :- queen([1,2,3,4,5,6,7,8,9,10],X),fail.
queen(Data, Out) :-
queen_2(Data, [], Out).
queen_2([], _, []).
queen_2([H|T], History, [Q|M]) :-
qdelete(Q, H, T, L1),
nodiag(History, Q, 1),
queen_2(L1, [Q|History], M).
qdelete(A, A, L, L).
qdelete(X, A, [H|T], [A|R]) :-
qdelete(X, H, T, R).
nodiag([], _, _).
nodiag([N|L], B, D) :-
D =\= N - B,
D =\= B - N,
D1 is D + 1,
nodiag(L, B, D1).
実行結果
3台のLinuxマシンを接続して実行しました。子機は1台は古いインテルi5、もう１台はAMD Ryzen、親機はインテルi7マシンです。
並列実行の方が若干高速になっていますが2倍までには至っていません。上述のように子機のうちの1台は古いマシンでありこれが足を引っ張っていると思われます。TCP/IP通信などのオーバーヘッドがあるにしても同程度の子機をそろえればおおむね2倍の計算速度が期待されます。
並列とProlog
Prologはバックトラックがあります。これと並列とを同居させることはかなりの困難を伴います。第五世代コンピューター計画においては専用の並列PrologマシンとGHCなどを開発しました。私はPrologのバックトラックを活かしつつ並列の良さを取り入れたいと思いました。分散並列であればそれぞれのマシンにおいてバックトラックが制約無く行えます。Prologが深さ優先探索であることを考えると分散したマシンで各それぞれが探索する方が向いているように思います。
ラズパイクラスタマシン
10台のラズパイをクラスタ接続したマシンを作ることを計画しています。これができると上述の10Queensはおおよそ10倍速で実行できるはずです。