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

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

9-4-1.概要

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

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

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

9-4-2.述語説明

以下の表は、次に説明するソース提供された並列処理用の述語とは別にAZ-Prolog本体に実装されている組込述語の一覧です。一部の述語は並列処理支援機構実装時の必要性から追加で組み込まれたものです。


従来からある組込述語
 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)並列処理用述語の説明
詳細は、「mlt_parent.pl mlt_child.pl」を読んでください。子プロセスへのゴールの与え方と結果の受け取り方で目的の違う処理が構築できます。

複数の子プロセスの生成
 mlt_proc/2 
指定個数のprolog_c子プロセスを起動する。
第1引数: 生成するProlog子プロセスの個数
第2引数: 生成プロセス情報のリスト(出力)
  1プロセス当たりの情報は以下の通り。
[子プロセスID,入力FP,出力FP,実行プログラム,起動パラメタリスト]
例.
[1916,fp_f79090,fp_f79140,prolog_c,[-child]]
 mlt_proc/5 
指定個数の実行プログラムプロセスを指定引数で起動する。
第1引数: 生成する子プロセスの個数
第2引数: 実行プログラム(prolog_cが前提)
第3引数: 領域指定
第4引数: その他の起動パラメタ(-p以下に続く。読込みプログラム等)
*読込みプログラムはconsult/b_load/compile/assert/execの述語呼び出し形式の指定が可能です。
第5引数: 生成プロセス情報のリスト(出力)
プロセス情報は mlt_proc/2 と同じ
子プロセスにゴールを与える
 mlt_send/2 
各プロセスに実行すべきゴール情報を送信する。
第1引数: mlt_proc/[2または5]で生成されたプロセス情報リスト
第2引数: 各プロセスに実行させるゴール情報リスト
  ゴール情報の与え方には以下の3方式がある。受取結果については[子プロセスから結果を受け取る]を参照。
(a) ゴール
ゴールを実行するだけで戻り値を要求しない場合に用いる。
?-mlt_proc(3,P),mlt_send(P,[true,true,true]).
(b) [ゴール,戻り値]
ゴールが成功したとき返す戻り値を指定。
?-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_scan_each/2 を呼ぶ。
子プロセスから結果を受け取る
下記の述語の引数は述語のアリティに応じて以下の通り。
第1引数: mlt_proc/[2または5]で生成されたプロセス情報リスト(共通)
第2引数: ゴール実行の結果(出力)(アリティ2の場合)
スキャンインターバル(ミリ秒)(入力)(アリティ3の場合)
第3引数: ゴール実行の結果(出力)(アリティ3の場合のみ)
受け取る結果内容は mlt_send/2 に与えるゴールの方式に応じて、以下のいずれか(最速の結果のみの場合)、もしくはこれらから成るリスト(全ての結果を取得する場合)。
1)方式(a)の場合、および方式(b)(c)でエラー/failの場合
実行ステータス:「status(exe,Status)」という形式の項(Statusはsucc,failまたはエラー番号)
2)方式(b)(c)で正常終了した場合
送信したゴールを実行した結果の指定戻り値
但し、 mlt_scan2/3 では「プロセスID=戻り値」となっている。ソースが提供されているので、必要に応じて修正は可能。
 mlt_receive/2  を含む全ての結果を起動順に読み込む。
 mlt_receive/3  を含む全ての結果を到着順に読み込む。
 mlt_scan/3   を含む最速の結果のみを読み込む。
 mlt_scan2/3   を除く最速の結果を読み込む。
すべてなら述語そのものが失敗する。
 mlt_scan_each/2   を除く結果を早い順に受け取る。
バックトラックで次の結果を取れる。
子プロセスを強制終了する
 mlt_kill/1  引数はmlt_proc/[2,5]で生成されたプロセス情報リスト

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

サンプルプログラム(%AZ-Prolog%¥sample¥parallel下)を解説しながら、並列処理関連の述語の使い方を説明します。

(1)データ並列

異なるデータに同一の処理を並列で施し、結果を結合します。
Nqueen
4クイーンの場合、リスト[1,2,3,4]を条件(既に置いた駒の効き筋上に新たな駒を置かない事)を満たすように並べ替えて全解を取得しますが、リストの最初の要素(最初の列に置く駒の行位置)をそれぞれ1,2,3,4に固定して、それ以外の要素の並べ替え(残り3列への駒の配置)を行うようにデータを振り分けた4プロセスに並列化可能です。
サンプルファイルqueen.plでは、例えば1つ目の駒が最初の列の1行目に置かれた状態で残りの駒を配置する場合の解は、述語put/3を用いて、
?-put([2,3,4],[1],Ans).
で得られます。従って、全ての解を求めるには、
?- ( 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部分(セミコロンで区切られた各部)を各プロセスに割り当てて並列に解くプログラムは次のようになります。

:-['queen.pl'].
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) ).                                          % プロセスを消去

4通りのput/3呼び出しパターンを生成するためにNqueensを解く時と同じ述語 select/3 を呼び出しているので、queen.plを最初にコンサルトしています。
サンプルプログラムには、同様にデータ並列化可能な例題として、素数生成(prime.pl)、ペントミノパズル(pentomino.pl)を用意しています。

以下にpentomino.plのメニューで逐次処理(メニューの2番)/並列処理(メニューの5番)のそれぞれを実行した場合に各CPUの使用率がどのようになっているかを参考までに示します。Windows版で実行した際に、タスクマネージャーから起動できるリソースモニターに表示されたグラフです。ページの都合によりレイアウトは変更してあります。並列実行の場合に処理の負荷分散がうまくなされている様子が分かります。


1)逐次処理の場合

  逐次処理の場合


2)並列処理の場合

  並列処理の場合


(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)の結果を加算することを考えてみましょう。
サンプルファイルfibo_ack.plに両数値を計算するための述語fibo/2およびack/3は用意されています。いずれも定義通りです。
逐次計算するなら、
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)アルゴリズム並列
適用するアルゴリズムによって、データの散らばり方に依存して格段の処理速度の違いが生じる場合があります。
このような時、全てのアルゴリズムを同一データに対して並列で処理させ、最速結果のみを採用することが可能です。例として4種類のアルゴリズムで同一データのソートを考えてみましょう。これらのソート用述語はサンプルプログラムsort_pack.plで定義されていると仮定しています。次のようにすれば、最初に解が得られたアルゴリズムのタイムコストで済みます。
sort_pack.plは現在は提供されていません。http://nojiriko.asia/などにも色々なソートアルゴリズムが紹介されているので、課題としておきます。ソート対象を十分に大きくすると、アルゴリズムの効率の違いがよりはっきりします。
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). % 計算中のものも含め子プロセスを削除してしまう