簡単な探索問題

ゴールの優先度を勉強した際に用いた簡単な探索問題プログラムに, 今度は更 に負荷分散制御を応用してみよう. プログラムは先に用いたものを拡張し, 負荷分散アルゴリズムはサイクリック割り付けを用いる.

また, 負荷分散は探索木が別れる部分で行なう. ただし, あまり細かく分散 すると負荷分散のためのオーバヘッドが増大するので, 探索がある程度のレベ ル(この例の場合は2)に達するまでは同じノードで実行し, レベルに達したと ころでサイクリックにノード割り付けを行なって負荷分散する. この探索木 は2分木なので, 探索レベル3のところ兄弟の数は個になり, 8台のノー ドに負荷分散する事になる.

なお, 負荷分散した先ではそれ以上の負荷分散は行なわず, 優先度制御のみを 行なう. この例では, 先に用いた search_pri モジュール ( ページ参照) のゴールを ただ呼び出しているだけである. また, ノードの番号を得るためのサーバプ ロセスを設け, 負荷分散を行なう前にはこのプロセスに対してノード番号を問 い合わせるものとする.

では, まず図4.19に各ノードのプロセスがどのノー ドで実行されるかを示す. また, 各ノード内での優先度も示す. 図中, 各ノー ド及びリーフの右肩或いは左肩の数字は優先度を表わす. また, 右或いは左 の数字は実行されるノードを表わす. 続けてプログラムをみてみよう.

  
図 4.19: 探索木の各ノードプロセスの実行されるノードと優先度

:- module search_load_balancing.

        search(Tree,Output):- true |                    %(1)
                current_node(PE,PEs),                   %(2)
                control(Results,Output,Cont),           %(3)
                fork(Tree,Results,0,PeServer,Cont)
                             @priority(4000),           %(4)
                next_pe(PeServer,PE,PEs).               %(5)
        fork(_,R,_,Next,stop):- true | R=[], Next=[].   %(6)
        alternatively.                                  %(7)
        fork(H,R,_,Next,_):- integer(H) |               %(8)
                R=[], Next=[].                          %(9)
        fork(H,R,_,Next,Cont):- atom(H) |               %(10)
                R=[H], Next=[].                         %(11)
        fork([TL,TR],R,Level,Next,Cont):-               %(12)
                Level =< 1 |                            %(13)
                L1 := Level+1,                          %(14)
                merge:in(R0,R1,R),                      %(15)
                merge:in(Next0,Next1,Next),             %(16)
                fork(TL,R0,L1,Next0,Cont),              %(17)
                fork(TR,R1,L1,Next1,Cont).              %(18)
        fork([TL,TR],R,Level,Next,Cont):-               %(19)
                Level =:= 2 |                           %(20)
                Next=[get(PE0),get(PE1)],               %(21)
                merge:in(R0,R1,R),                      %(22)
                search_pri:fork(TL,R0,Cont)@node(PE0),  %(23)
                search_pri:fork(TR,R1,Cont)@node(PE1).  %(24)

        control([H|_],Output,Cont):- wait(H) |          %(25)
                Output=[H], Cont=stop.                  %(26)
        control([],Output,Cont):- true | Output=[].     %(27)
        
        next_pe([],_,_):- true | true .                 %(28)
        next_pe([get(PeNo)|Next],PE,PEs):-true |        %(29)
                PE1 := PE+1,                            %(30)
                PeNo := PE mod PEs,                     %(31)
                next_pe(Next,PE1,PEs).                  %(32)

search このプログラムを呼び出すトップレベルの述語である. 引数は先の例と全く同じである. ボディゴールでは, まず組込み述語で自分 のノード番号と全体のノード数を計算している(2). (3), (4)では探索を行な うプロセスを生成している. (5)ではノード番号を得るサーパプロセスを生成 している.

fork クローズ(12) 探索のレベルが1以下の時には同じノードで 実行する. なお, ここで (17), (18) の優先度を変えていないが, これは負 荷分散作業を最優先で実行するためである. 即ち, 優先度を下げると探索作 業と負荷分散作業が並行して行なわれ, ノードに投げる処理が遅れるからであ る.

負荷分散が完了するまでは, 負荷分散作業を行なうゴールのプライオリティは 他のゴールのプライオリティよりも低くならないようにするように注意しなけ ればならない.

fork クローズ(19) 探索のレベルが 2 に達した時, 左右の探索を別ノードで実行させるようゴールを投げている (23), (24). い ずれのゴールも, 実行する優先度の範囲はトップレベルのゴール呼び出しで与 えられた引数をそのまま渡している.
ここで search_pri: の後にゴールを記述しているが, これは別モジュールのゴールを呼び出すため の表記である. 優先度制御は, このモジュール の中で行なわれる. なお, (21) の部分で動作させるべきノード番号を得ている.

next_pe ノード番号をサイクリックに得るためのサーバである.