このディレクトリの索引
http://pc12.2ch.net/test/read.cgi/tech/1269438098/256
#  [1] 授業単元: 並列プログラミング 
#  [2] 問題文(含コード&リンク): 配列をソートするために、クイックソートをMPIを用いて並列化せよ。 
#  

% Prolog 友人(AZ-Prologの開発者)に解答を依頼したところ掲載してよいからとメールがきました。
% AZ-Prologの並列機能を使っています。
% 同様に偶数のNプロセスでソートすることもできます。
% 方法1)
% 子プロセスのソート部分は従来のqsortそのままで、親がわであらかじめN個の
% PartitionでN個のリストを作ってから並列実行させる。
% 方法2)
% 深さ指定のパラメータをわたし、子側でさらに孫をつくるか、自分でソートするか
% 分岐をいれておく。
%
% 
% 2プロセスでソートする最も簡単な並列化です。
% ただし、データのプロセス間通信コストが発生するのであまりいい例ではありません。
% (このように単純なプログラムではシングルでソートしたほうが早い場合が多い!?)

/*
qsort.pl

    qsort を2プロセス並列で解を求める

      | ?- mlt_quick_sort([5,4,1,8,4,0,9],Ans).
      A = [0,1,4,4,5,8,9]
      yes

軽い説明:
      mlt_send(Prc,[[Goal,ReturnValue],[Goal2,ReturnValue2]...])   Procの個数分ゴールと戻し値を設定する
      mlt_receive(Proc,[ReturnValue,ReturnValue2....]) mlt_sendで起動した順、設定された戻し値がユニファイされ
る
*/

mlt_quick_sort([A|L],Ans):-
        mlt_proc(2,prolog_c,'',consult('qsort.pl'),Proc),          %  2つの子プロセスを立ち上げる
        partition(A,L,Ls,Lb),                                      %  元データを2つに分割する
        mlt_send(Proc,    [[qsort(Ls,X),X],[qsort(Lb,Y),Y]]),      %  2つのリストを2つのプロセスで並列ソート
        mlt_receive(Proc,[  Ans-[A|Else],        Else-[]  ]),      %  結果を起動順に受け取る(上のサブゴールの  X,Y  )
        mlt_kill(Proc).                                            %  子プロセスを削除する

%%%%%  Quick  Sort  %%%%%
quick_sort(List,Ans):-qsort(List,Ans-[]).

qsort([X|L],Ans-Tail):-
        !,partition(X,L,Lsmall,Lbig),  qsort(Lsmall,Ans-[X|Else]),  qsort(Lbig,Else-Tail).
qsort([],L-L).

partition(X,[A|L],Ls,[A|Lb]):-X @< A,!,partition(X,L,Ls,Lb).
partition(X,[A|L],[A|Ls],Lb):-!,partition(X,L,Ls,Lb).
partition(_,[],[],[]).