このページではJavaScriptを使用しています。

9-3.並列処理支援機構

9-3-1.概要

AZ-Prolog.v6の並列処理支援の仕組みは、GHCのような言語に内包された機能ではなく、Prologのシンタックスそのままで、プログラム上で明示的に複数のプロセスに分散して粒度が粗い並列処理を行うものです。
プログラマは処理の切り分けと並列化をプログラミングしなければなりません。MPI(Message Passing Interface )と同様なものであるとお考えください。

AZ-PrologはVersion3(1995年リリース)のころから、子プロセスを立ち上げプロセス間通信をおこなう述語(s_child/5)が用意されていました。この述語は、DIRなどのOSコマンドをコマンドプロセッサ(cmd.exe)に送信し、結果を受け取ってPrologプログラム側で処理をおこなうことや、並列に多数のネットワークノードに「Telnet」「Snmp」をおこない、同時刻での情報を得る目的で使われてきました。
これまでのCPUはシングルコアであり、複数の処理を並列におこなって結果を結合しても上記のような目的以外ではかえって処理時間がかかってしまい、あまり意味をなさないものでありました。

しかしながら、昨今のCPUはマルチ/メニー・コアの流れが加速されており、この資源を生かすことでコア数倍の高速化が図れるようになっています。
手軽に並列化するごく簡単な手段で高速に結果を得ることが可能となったのです。

9-3-2.述語説明

従来からある組込述語
s_child/5 子プロセスを立ち上げる.
s_child(+実行形式プログラム,+[パラメータ並びリスト],-InStream,-OutStream,-ProcessID)
s_kill/2 子プロセスを削除する.
s_kill(+ProcessID,0).
s_sleep/1 指定ミリ秒スリープする
追加組込述語
s_flush/0 標準出力バッファの強制フラッシュ。対向(親)プロセス側で読み込めるようにする。
s_can_read/1 OutStreamから読み込み可能な場合(子プロセス側で標準出力に戻値出力)にのみ成功。
s_can_read/2 OutStreamから読み込み可能な場合に成功し、読み込み可能バイト数を返す。

(1)並列処理支援Prologソース 

(AZ-Prologインストールディレクトリ「¥system¥PL」にあります)
mlt_parent.pl親プロセス側の並列処理用述語(子プロセスも孫を生成することがあるので利用する)
mlt_child.pl¥子プロセス側の並列処理用述語

提供インタプリタはほぼ次のようにコンパイルされていますので子プロセス用Prologインタプリタとしてprolog_c.exe を使うことができます。
C:¥>azpc -p setof.pl utility.pl mlt_child.pl mlt_parent.pl /i /dcurses /e prolog_c
C:¥>azpc -p setof.pl utility.pl mlt_parent.pl /i /e prolog
もちろん、mlt_child.pl mlt_parent.plを含めてコンパイルされたユーザー作成の実行プログラムでもかまいません。

(2)並列処理支援Prolog述語説明
詳細は、「mlt_parent.pl mlt_child.pl」を読んでください。子プロセスへのゴールの与え方と結果の受け取り方で目的の違う処理が構築できます。

複数の子プロセスの生成
mlt_proc/2 必要なPrologプロセスの個数を指定。
生成された一覧リストを第二引数にユニファイする。
L = [[1916,fp_f79090,fp_f79140,prolog_c,[, -child ]],…..]
mlt_proc/5 プロセスの個数、EXEファイル、引数1(領域設定)、引数2(読込みPG)を
指定してプロセスを生成
子プロセスにゴールを与える
mlt_send/2 第一引数はmlt_proc/[2または5]で生成されたプロセス一覧リスト。
第二引数は各プロセスに与えるゴール(下記の3方式がある)のリスト。
(a) ゴール
後述の結果受け取りでは、 status(exe,Status) という形式の項が返る。
Statusはsucc,failまたはエラー番号である。
?-mlt_proc(3,P),mlt_send(P,[true,true,true]).
(b) [ゴール,戻し値]
ゴールが成功したとき返す戻し値を指定。エラー・failでは(a)と同じ
?-mlt_proc(2,P),mlt_send(P,[[put(4,L),L],[put(5,M),M]]).
(c){ゴール,戻し値}
(b)と同じだが、戻したあと強制バックトラックされ、別解が取れる
?-mlt_proc(2,P),mlt_send(P,[{put(4,L),L},{put(5,M),M}]).
子プロセスから結果を受け取る

以下の述語はすべて、第一引数はmlt_proc/[2または5]で生成されたプロセス一覧リスト。
最終引数(2ないし3):結果をリストでユニファイ
3引数のものは第2引数でスキャンインターバル(ミリ秒)を指定する。

mlt_receive/2 <fail,error>を含む全ての結果を起動順に読み込む。
mlt_receive/3 <fail,error>を含む全ての結果を到着順に読み込む。
mlt_scan/3 <fail,error>を含む最速の結果のみを読み込む。
mlt_scan2/3 <fail,error>を除く最速の結果を読み込む。
すべて<err,fail>なら述語そのものが失敗する。
mlt_scan_each/2 <fail,error>を除く結果を早い順に受け取る。
バックトラックで次の結果を取れる。
子プロセスを強制終了する
mlt_kill/1 引数はmlt_proc/[2,5]で生成されたプロセス一覧リスト

9-3-3.プログラムの書き方

サンプルプログラム(%AZ-Prolog%¥sample¥parallel下)を解説しながら、使い方を説明します。


(1)データ並列

異なるデータに同一の処理を並列で施し、結果を結合します。

Nqueen
4クイーンの場合、リスト[1,2,3,4]を条件を満たす並べ替えで全解を取得しますが、並べ替・条件チェックをおこなうデータは、リストの先頭がそれぞれ1,2,3,4であると固定してそれ以外の要素の並べ替えの4プロセスに並列化可能です。
?- ( put([2,3,4],[1],Ans); put([1,3,4],[2],Ans); put([1,2,4],[3],Ans); put([1,2,3],[4],Ans) ).
このOR部分をプロセスに割り当て、並列に解くプログラムは次のようになります。

queens:-
    List = [1,2,3,4],
length(List,Ln),
    bagof({put(Else,[F],Ans),Ans},select(List,F,Else),Pattern),  % 一列目におくQueenの位置全とおりを生成
    mlt_proc(Ln,prolog_c,'',compile('queen.pl'),Proc),           % List長数のプロセスを生成
    mlt_send(Proc,Pattern),                                      % おのおののプロセスにパターンを割り振る
    ( mlt_scan_each(Proc,X),write(X),nl,fail;                    % 全プロセスから全結果を取得
      mlt_kill(Proc) ).                                          % プロセスを消去
 

サンプルプログラムには同様のデータ並列例題として、素数生成、ペントミノパズルを用意しています。


(2)処理並列
依存しない複数のサブゴールが並列で処理できれば最長部分のみの処理時間で済みます。

逐次:
a(A,AA),b(B,BB),c(C,CC),  d(AA,BB,CC,Ans),....
 3秒  + 20秒  + 10秒      =33秒 
逐次に処理すると33秒

並列: ┌─ a(A,AA) ─┐ ─┼─ b(B,BB) ┼─ d(AA,BB,CC,Ans), └─ c(C,CC) ─┘ 並列だと20秒で処理できる

計算コストが大きいことで知られるアッカーマン関数(3,10)結果とフィボナッチ数列(35)の結果を加算することを考えてみましょう。
seq_ack_fibo:- fibo(35,X),ack(3,10,Y),Ans is X+Y,write(ans=Ans).
このfibo(35,X)とack(3,10,Y)を並列で計算するプログラムは次のようになります。
ack_fibo:-
mlt_proc(2,prolog_c,'',compile('fibo_ack.pl'),Proc), % fibo.pl を起動時に読込むプロセスを生成
mlt_send(Proc,[[fibo(35,X),X],[ack(3,10,Y),Y]]), % 各プロセスに異なる[ゴール,返し値]を送信
mlt_receive(Proc,[X,Y]), % 出力ストリームから計算結果を受け取る
Ans is X+Y, write(ans=Ans), % 両方の計算結果を加算する
mlt_kill(Proc).

(3)アルゴリズム並列
適用するアルゴリズムによって、データの散らばり方に依存して格段の処理速度の違いが生じる場合があります。
このようなとき、全てのアルゴリズムを同一データに対して並列で処理させ、最速結果のみを採用することが可能
です。ソートで考えてみましょう。次のようにすれば、最初に帰ってきた解のタイムコストとなります。
mlt_sort(L,Ans):-
mlt_proc(4,prolog_c, '',compile('sort_pack.pl'),Proc),
mlt_send(Proc,[[qsort(L,A),A],[msort(L,A),A],[bsort(L,A),A],[binsort(L,A),A]]),
mlt_scan2(Proc,0,Ans), % fail,errorでない最速で解を返したものを採用
mlt_kill(Proc). % 計算中のものも含め子プロセスを削除してしまう