シンプルイズベスト
N-Prologの拡張として取り組んでいた分散並列機能が動き出しました。ご紹介します。Prologの並列と言えばParlogやGHC、KL1などが有名です。これらは節の本体部をAND並列、あるいはOR並列をすることで実現していました。しかし、これはかなり大変です。私もGHCを実装しようと頑張ってみたのですがそのあまりの複雑さにめげてしまいました。今回、私が取り組んでいるのは極めてシンプルなものです。コード中の並列実行可能な部分を人間が取り出してコード化するという手法です。エジンバラPrologの仕様の範囲内で慣れ親しんだPrologで分散並列をやろうというものです。
例コード
まずはこのコードをご覧ください。
para(X) :- list50(Y),psort(Y,X).
psort([Pivot|Rest], Sorted) :-
partition(Pivot, Rest, Left, Right),
dp_and([qsort(Left, SortedLeft), qsort(Right, SortedRight)]),
append(SortedLeft, [Pivot|SortedRight], Sorted).
seq(X) :- list50(Y),qsort(Y,X).
qsort([], []).
qsort([Pivot|Rest], Sorted) :-
partition(Pivot, Rest, Left, Right),
qsort(Left, SortedLeft),
qsort(Right, SortedRight),
append(SortedLeft, [Pivot|SortedRight], Sorted).
partition(_, [], [], []).
partition(Pivot, [H|T], [H|Left], Right) :-
H =< Pivot,
partition(Pivot, T, Left, Right).
partition(Pivot, [H|T], Left, [H|Right]) :-
H > Pivot,
partition(Pivot, T, Left, Right).
% List of 50 elements for another test
list50([27, 74, 17, 33, 94, 18, 46, 83, 65, 2, 32, 53, 28, 85, 99, 47, 28, 82, 6, 11,
55, 29, 39, 81, 90, 37, 10, 0, 66, 51, 7, 21, 85, 27, 31, 63, 75, 4, 95, 99, 11, 28, 61,
74, 18, 92, 40, 55, 59, 8]).
psortというのが分散並列版のクイックソートです。qsortは逐次処理版です。ご注目いただきたいのはdp_and/1 という述語です。これはリスト中の述語を複数の子機にTCP/IPで渡して並列計算します。そして結果をTCP/IPで受け取って変数をunifyするというものです。
結果をご覧ください。
予め子機2台をネットワークモードで起動しておきます。そして親機からdp_create/1を使ってIPアドレスにより子機との通信を確立します。その後、子機も含めて全機でコンパイルして、全機にconsultします。
para/1は並列実行した結果です。seq/1は逐次実行の結果です。同じソート結果が得られています。
オーバーヘッド
このような粒度の小さいコードの実行ですとオーバーヘッドがバカになりません。並列分散の方が遅くなってしまうのは仕方のないことです。
しかし、粒度の大きな問題ですと威力を発揮するはずです。例えばボードゲームの先読みです。あるいは数学の群論、位相の問題で手間のかかるものです。9Queensを９つに分解して並列実行すると台数効果が得られるはずです。
だんだんと面白くなってきました。ご興味ありましたらご自分でも動作させてみてください。複数のLinuxマシンがあれば再現できます。ラズパイでも動作可能です。さあ、いよいよ並列の時代です。Prologの復活はあるかな？