4.1 優先度制御の利用目的

逐次型計算機では, 処理順序がプログラムに記述した順序で決まる. 一方 KL1 では, リダクションされたサブゴールの実行がプログラム中に 記述された順番に従って実行されるとは限らない. 順番に関係なく実行される ことは, 次のように言い換ることができる.

KL1 ではリダクションにより生成されたサブゴールを並列に 実行しても構わない.

前章までで述べてきたように, KL1 には暗黙の同期 機構があるので, 論理的には実行順序の制御を記述する 必要はない. しかし実際に KL1 プログラムを計算機上でより効率的に 動作させるには, 実行順序を制御する機構を利用した方が有効な場合が ある. そのために KL1 言語の 優先度制御を利用することになる.

優先度制御を利用する理由を挙げてみよう.

1. 領域計算量(計算に必要な記憶領域)を減らす効率化を図る
   例えば生産者-消費者問題のプログラムを作成した場合, 生産者側と 消費者側をどのような順序で実行すべきであろうか. 生産者側を 優先的に実行すれば, 生産者が一時的に巨大なデータを生成し, メモリ不足を引き起こす恐れがある. 消費者の優先度を上げることで, メモリ不足を防げる 可能性がある.
2. 時間計算量(ゴールリダクション数)を減らす効率化を図る
   例えば木探索問題において, 探索中の枝に評価値設定し, この評価値を そのまま優先度として利用すれば, 枝の探索順序を自然に決定できる. その結果としてプログラムが最良優先探索プログラムとなり, 計算量を減らせる 可能性がある.
3. メタプログラミングの代用処理をする
   非決定性プログラム, 例えば OR 型探索プログラムのある枝で解が みつかった場合, 他の枝に探索中止通知を他の処理より優先的に 送る必要があるし, その通知を優先的に受け取る必要がある. またマルチプロセッサ上で負荷分散処理を行う場合, 管理ゴールを優先的に 処理する場合にも利用する (本処理の説明は今回割愛する).