| 平成８年度 委託研究ソフトウェアの提案 |
［研究の内容］
PIM ならびに KLIC の研究・開発を通じて，KL1 の逐次的なプログラムの実行
性能は，他の論理型言語や一般の記号処理向き言語のシステムと比べて，遜色
のない水準に達している［1］。しかし，本来 KL1 が対象とする並行／並列プロ
グラムの性能に関しては，必ずしも満足できるものとはなってはいない。例え
ば，並列オブジェクト指向言語におけるオブジェクト間通信に比べ，KL1 をは
じめとする並列論理型言語でのプロセス間通信は一般に低速である。
この理由の一つとして，プロセス間通信において受信プロセスが頻繁に 中断／ 再開を繰り返すことが挙げられる。例えば，プロセス p と q があって，p が q に要求を行ない，q がその結果を p に返答するという，典型的なプロセス 間通信を考える。従来の KL1 処理系で採用されているプロセス指向スケジュー リングでは，p が q への要求メッセージを生成した後で q からの返答を待っ て中断する。また q は p からの要求を処理して返答した後，p からの次の要 求を待って中断する。従って，p と q がメッセージを１回やりとりするたび に，p と q の各々が中断してしまう。また p や q の中で中断するゴールは １つであるとは限らず，メッセージの中身を間接的に必要とするゴールが多数 中断してしまうことがしばしばある。
この問題を解決する方法として，KLIC で採用されている resumption first scheduling や，メッセージ指向のスケジューリング［2］がある。これらの方法 では，前述の p が要求メッセージを生成した時点で直ちに q へ制御が移るた め，p の中で q からの応答を待つ中断は発生しない。しかし，p が生成する メッセージが複雑なものである場合，メッセージが完全なものとなる前に q に制御が移ってしまい，その結果 q が未生成の部分を発見して中断してしま うことがしばしばある。この不完全なメッセージによる中断は，一つのメッセー ジが通信される過程で何度も起こることがあり，かえって性能を悪化させてし まうことが多い。
以上のように，これまでに実装／提案されているゴール・スケジューリング手 法では，高頻度のプロセス間通信を行なう並行／並列プログラムの性能に大き な問題がある。この問題を整理すると，以下のようになる。
これらのうち，(a) の問題点はデータ依存性解析を行なって，中断するゴール にデータ依存するゴールをスケジュールしないようにすれば解決できる。しか し，データの依存関係は分岐や合流を持つグラフとなり，直線的な逐次スケジュー リングとは必ずしも整合しない。
そこで，中断するゴール自身がデータ依存「していない」ようなゴールは，ス ケジュールしなくてもデッドロックしないことを利用することが考えられる。 即ち，既定のスケジューリング順序と逆方向のデータ依存がないようなゴール 列に対しては，その中のあるゴールが中断すると後続のゴールを一切スケジュー リングしないという方法が考えられる。この方法は，データ依存関係を順方向 のみにできるようなプログラム断片をプロセスとし，プロセス内のゴールをス タックなどを用いて逐次的に実行し，中断したならばプロセス全体を中断させ るという，他のプログラム言語でしばしば用いられる方法で実現できる。
この方法の問題点の一つは，「依存関係が絶対に存在しない」ことを解析する 必要があることであり，これは一般に「依存関係が存在する」ことの解析より も困難である。従ってこの問題に関する良い解を得ることが，本研究の大きな 目標の一つとなる。この他，中断ゴールに依存しない後続ゴールを実行しない ことが，性能上の問題になることも考えられるが，これについては将来の課題 とする。
次に (b) の問題点は，他のプロセスのゴールを再開させるようなゴール（ユ ニフィケーション）の実行，あるいは他のプロセスへの制御移行を，自プロセ スがデッドロックしない範囲でできるだけ遅延することにより，多くの場合に は解決できると考えられる。従って，(a) と同様に依存関係が存在しないこと の解析が重要な役割を果たす。また我々が既に行なった，プロセッサ間通信の 最適化［3］とも密接に関連し，通信量の削減に応用できるものと考えられる。
平成7年度では，一つの節に含まれているゴール間の依存関係を解析し，双方 向の依存関係がないものをスレッドにまとめる解析系プロトタイプを作成した。 また，スレッドをスタックを用いて実行する逐次実行系プロトタイプも作成し て簡単な性能評価を行なったところ，1.5〜2倍の性能が得られることが明らか になった。
平成8年度は上記の結果に基づき，スレッドのスケジューリングの最適化，応 答性の低下防止や通信量削減を含む分散環境での実装，解析系／実行系の種々 の制約除去などを中心に研究を進める。
＜参考文献＞
［1］ Chikayama, T., et al. A Portable and Efficient Implementation of
KLIC. In Proc. Intl. Symp. on Programming Language Implementation
and Logic Programming, pp. 25-39, LNCS 844, Springer Verlag,
September, 1994.
［2］ Ueda, K. and Morita, M. Moded Flat GHC and Its Message-Oriented Implementation Technique. In New Generation Computing, Vol. 13, No. 1, pp. 3-43, November 1994.
［3］ 大野 和彦，他. 静的解析による並列論理型言語KL1の最適化手法. JSPP'95, pp.169--176, May, 1995.
ゴール・スケジューリング最適化 KLIC 改良版は，ゴール間のデータ依存解析 を行なってスケジューリング戦略を定める解析系と，解析系が求めた戦略にし たがってゴールのスケジューリングを行なう実行系に分かれる。
解析系はまず，モード解析に基づいて見かけ上のデータ依存関係を求め，さら に真の依存関係（実際のデータ生成／消費に基づく関係）を求める。この結果 に基づき，節内のゴールの起動順序を決定する。このスケジューリングに基づ き起動されるゴール列について，起動順序と逆方向のデータ依存関係がない部 分列を求め，それに対応する述語の集合をプロセスとする。またプロセス内／ プロセス間の制御移動について，各々に適合した処理コードを生成する。
実行系は解析系が生成した処理コードに基づき，プロセス内のゴールをスタッ クで管理する。またプロセス間制御移動に関するスケジューリング機構や，適 切なタイミングで制御移動するための管理機構などを持つ。
解析系／実行系ともに既存の KLIC に組み込まれ，解析の実施や解析結果に基 づく処理方式変更は，コンパイル・オプションにより指定する。従って KLIC ユーザはプログラムを一切変更することなく，ゴール・スケジューリングを最 適化した実行コードを得ることができる。
解析系は KLIC コンパイラの一部として組み込まれ，ゴール間のデータ依存解 析を主とする解析部と，解析結果に基づくコード生成部とに分かれる。既存の KLIC との連続性や，KLIC の今後の改良に対応するため，解析系は既存部分と は最大限に独立した形で実装する。またデータ依存解析はできるだけ汎用的に 行ない，他の用途への流用が容易に行なえるように設計する。
実行系は KLIC ラインタイム・システムの一部として組み込まれ，プロセス内 スケジューラとプロセス間スケジューラに分かれる。ユニフィケーション機構 など，既存のランタイム機構はほとんど影響を受けないので，ジェネリック・ オブジェクトなど既に作成されたユーザ定義モジュールを変更する必要は一切 ない。
本研究で作成するソフトウェアは，IFS の一つである KLIC システムを改良す る形で実装される。また，本研究の成果を組み込んだ改良版 KLIC システムは， ICOT フリーソフトウェアの一つとして提供する。
解析系は KL1 で，実行系は C で作成する。動作環境などは KLIC と全く同一 で良い。
KLIC の改良版として提供されるので，KL1 プログラムは勿論，ユーザ定義の ジェネリック・オブジェクトを変更する必要は一切ない。
また本研究での最適化は，ほとんど全てのプログラムに効果があると予想され るが，特にプロセスを指向したプログラミング・パラダイムを採用したプログ ラムについて，大きな効果を発揮するものと期待できる。また今後のプログラ ム開発において，従来のように処理系の性質を過度に考慮することなく，自然 なプログラミングで十分に高い性能を得ることができると期待される。
www-admin@icot.or.jp