2.3.3 部分木は直接通信させない

部分問題を解く計算を通して得られたデータを, 別の部分問題を解くところで も活用したくなる場合は少なくない. このような場合も, サブネットワーク すなわち部分木どうしが直接通信するようにプログラムすると, プログラムの全体の木構造が崩れて, 構造が把握しにくくなる.

プログラム全体は木構造のままで, 部分木間でデータを共有したい場合は, 共 有データのためのサーバプロセスを置き, ここを経由して通信するようにする と, 構造を把握しやすくなる. すなわち, 図 2.3の左のようなプロセス・ネットワークでなく, 右の ようなプロセス・ネットワークを構成するのである。 プログラムは以下のようになるだろう.

        p(I, O) :-
            decompose(I, I1, ..., In),
            merge({S1, ..., Sn}, S),
            shared_data_server(S),
            p1(I1, S1, O1),
            ...,
            pn(In, Sn, On),
            compose(O1, ..., On, O).

  
図 2.3: サーバプロセスを通した通信へ

決してとるべきでない通信形態は `部分木のうち最初に解を見つけたものが他 の部分木の計算をやめさせる' というような方法である. このような形態を とると複数の部分木がほぼ同時に解を見つけた場合に, いつでも正しく動作さ せるようにするのが難しくなる. 解が見つかった, という事実は共有データ である. 解を見つけた部分木は共有データのサーバに連絡し, このサーバが 他の部分木を終了させるようにするのが良い. 一般に, 競争条件は原則とし てストリームのマージ機構に一元化すべきである.