年末年始プロジェクト N-Prolog マルチスレッド対応

分散並列Prologを達成したものの、さらにマルチコアを活かすためにマルチスレッド方式による単体並列機能を追加する計画を立てました。本業のお仕事の合間にすこしずつ改良を加えてきました。インタプリタ及びコンパイラにおいてスレッドセーフを達成できました。これで台数効果が得られるのか？など計算実験をしています。現状をご紹介します。

ホーアのクイックソート

クイックソートのアルゴリズムは完全に独立して並列動作可能です。まずはこれにより期待した並列動作をしているのかをテストしました。コードは下記のようです。

% multi-thread parallel example

:- mt_create(2).

para(X) :- list50(Y),psort(Y,X).

psort([Pivot|Rest], Sorted) :-
    partition(Pivot, Rest, Left, Right), 
    mt_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]).

インタプリタ及びコンパイラで期待どおりの答えが得られています。実行したPCはAMDのRyzenが搭載されたLinuxマシンです。pthreadを利用しています。マルチコアマシンではマルチスレッドで実行することにより台数効果が得られるはずです。

実行時間を計測すると大差ありません。おそらくこうした粒度の小さいコードではオーバーヘッドの方が大きいようです。それはともかくとして一応は期待した答えは得られるようになりました。

10queens問題

もっと粒度の大きな問題で並列機能をためしてみました。10Queens問題です。これを10個の部分計算に分割します。これを5個つづマルチスレッド並列で実行させます。コードは下記のとおりです。

% 10-queens program in parallel  

:- mt_create(2).
%parallel 10queens
para :- mt_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).

インタプリタによる実行結果は下記のとおりです。残念ながら並列の方が少し遅くなっています。

次にコンパイラでの結果を示します。

最初は並列の方が若干速い程度です。2回めからは並列の方がおおよそ2倍高速になっています。

私はCPUのL3キャッシュの影響ではないかと考えています。現在のメジャーなCPUはL1，L2，L3キャッシュを持っています。インタプリタのコードはL3キャッシュのヒット率が低いのだろうと思います。Prologの動作は複雑ですのでスレッドごとにコードがあちこちにジャンプします。インタプリタにおける変数のアルファ変換において競合防止のためにlockをかけてるのも影響があるかもしれません。

コンパイラの方は2回めの動作からはマルチコアが活きているように思えます。スレッドプーリングをしているのですが、初回はスレッド起動のオーバーヘッドが大きいように思えます。

いずれにしましてもマルチスレッドでPrologコードが動作するところまでは達成しました。さらなる考察と改良が必要です。

現在における並列Prolog

現在におけるPCはマルチコアが普通です。そしてとても安価になりました。ラズパイなら100ドル程度です。これらをクラスタ接続し分散並列としつつ、各PCにおいてマルチコアを活かすことができれば、安価にPrologの並列計算実験ができるというのが私のプロジェクトの狙いです。

1980年代における日本の第５世代コンピューター計画においてはコンピューターのダウンサイジングの波が到来していました。通産省による官製の計画だったため計画の変更は困難でした。当初計画どおりに大型の専用マシンを開発するという計画は変更できなかったと関係者から聞いています。

もしも、現在において再挑戦できるのであれば、普及価格のPCやラズパイが活用できます。豊富なハード資源により富豪的な並列計算をすれば、また、面白い結果が得られるのではないかと私は期待しています。Prologはとても興味深いです。私の興味は尽きることがありません。私なりの方法論で第５計画の続きをやってみたいと思っています。