(5) KL1 のゴール・スケジューリング最適化

［中間報告］

1. 研究進捗状況

本研究では；

1. あるゴールが中断した時に，スケジューリングすべきゴールをできるだけ 限定し，中断したゴールにデータ依存するようなゴールのスケジューリン グを回避する。
   
2. あるゴールが再開可能になった時，その再開をできるだけ遅延させ，再開 されるゴールの中断を回避する。

ような最適化ゴール・スケジューリング方式を得ることにある。これらはいず れも，ゴール間のデータ依存関係が「存在しない」ことを解析できれば実現可 能である。しかしそのような解析は，依存関係が「存在する」ことを見い出す よりもはるかに困難である。そこで，まず (a) に的を絞り，同じクローズに 属する二つのゴールについて，双方向の依存関係が存在しえないことの解析方 法を検討中である。

2. 現在までの主な成果

クローズ；

    p(X,Z):- true | q(X,Y), r(Y,Z).

について，p, q, r の入出力モードが p(+X,-Z), q(+X,-Y), r(+Y,-Z) である とする。この時 r が q にデータ依存することは明らかであるが，q が r に データ依存しないことは自明ではない。即ち p を呼び出したゴールが，Z->X のデータ・フローを生成している可能性があり，その場合 q あるいはそのサ ブゴールの中断時に r のスケジューリングを行なわないと，デッドロックす る可能性がある。

そこで，q あるいはそのサブゴールが中断した時，r をスケジューリングして も Z が全く具体化されないならば，r をスケジューリングしなくてよい，と いう規則を見い出した。この場合，Z->X のデータ・フローが存在しなければ， 勿論 r をスケジューリングする必要はない。また Z->X のデータ・フローが 存在すれば，r をスケジューリングしてもしなくても，同じ結果（デッドロッ ク）となる。

3. 今後の研究概要

前述のクローズ内スケジューリング規則が適用できるための条件を，静的解析 によって求める解析系の設計を行なう。また，スケジューリング規則に基づく 実行系プロトタイプの設計を行なう。

4. 今年度目標成果

前述のクローズ内スケジューリング規則に基づく，解析系／実行系のプロトタ イプ。