本研究では、逐次実行が最適なゴール系列を一つのスレッドとみなし、プログ ラムを並行スレッドの集まりと考えて最適化を行う。これにより、スレッド内 については逐次実行効率を優先したコードを生成すると共に、スレッド間の動 的スケジューリングによって元プログラムの本質的な並行動作を実現し、デー タ依存関係を保つことができる。
最適化は、まずゴール間の依存解析を行った後、その結果を元にプログラムを スレッドに分割し、各スレッドについて最適化コードを生成するという方法を とる。
KL1での同一化は、対象となる変数について必ずしも具体値を必要としないた
め、変数間の論理的なデータの流れがすべて依存になるとは限らない。提案す
る手法では、ユーザ定義述語を「ガードで引数の一部を参照し、子供となるボ
ディゴールを生成して終了する」存在と捉える。組込述語については、「ラン
タイムが引数の一部を参照し、ボディゴールの呼び出しは行わずに引数の一部
を具体化して終了する」ものと考える。ここで参照、具体化される引数をそれ
ぞれ入力、出力とみなすと、あるゴール
が実行可能になるための条件は、入力引数の各々について、
それらを出力引数とするゴールの実行がすべて終了しており(データ依存)、
の親ゴールの実行も終了している
(制御依存)、ということである。したがって、これらの依存を解析した上で、
半順序の依存関係が成り立つゴールの集合を1スレッドとすればよい。
依存解析は後述するように具体化ゴール情報を付加した型解析を用い、データ
の生成ゴール・参照ゴール間の依存情報を抽出する。次に、この依存情報を利
用してプログラムをスレッドに分割する。あるスレッド
中のゴールpがボディゴール
を生成する場合を考えると、逐次化を
行うには、
の依存関係により両者
の実行順序を決定しなければならない。片方向の依存であれば実行順序を依存
順に、依存関係がなければ実行順序を任意に、それぞれ固定できる。相互依存
であれば、
の次の実行ゴールは
とし、
を新たなスレッド
の開始ゴールとする。これを繰り返して、プログラム中の全
ゴールをスレッドに分割すると同時に、スレッド内のゴールを静的スケジュー
リングする。各スレッド内のゴールから実行コードを生成する際には、逐次化
により不要になる動的な判定・操作を削減し、実行効率を向上させる。
実行時処理
従来のKLIC実行系では各ゴールがスケジューリング対象となるが、提案する手 法では、各スレッド内のゴールのスケジューリング順序を静的に固定している。 したがって、本手法の実行系ではスレッド単位のスケジューリングを行う。
実行系があるスレッドを選択すると、入力引数がそろっている限り、スレッド 内ゴールを逐次的に実行する。未具体化の入力引数が現れた場合にはゴールの 実行が中断するが、その変数を具体化するのは他のスレッド中のゴールである ので、実行中のスレッド自体が中断し、実行系は他のスレッドを選択して処理 を続ける。