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