| 平成８年度 委託研究ソフトウェアの 最終成果報告書 |
KILCをはじめとする従来の並行論理型言語の処理系では，ゴールの実行順序を 動的にスケジューリングする。その結果，たとえば細粒度プロセスが頻繁に交 信を行なうようなプログラムでは，スケジューリング・オーバヘッドのために 低い性能しか得られないことがしばしばあった。そこで我々は，コンパイル時 の解析とその結果に基づく実行時スケジューリングによって，このスケジュー リング・オーバヘッドを大幅に削減する方式を研究してきた。
まずコンパイラは，ゴール間のデータ依存関係を解析し，実行順序を静的に定 めることができるゴール群をまとめてスレッドとする。この解析は単にゴール 引数の入出力モードのみに基づくものではなく，ある変数の具体化が真に必要 なゴールや，その具体化のためにスケジュールされることが真に必要なゴール を見い出す。したがって，ある一組のゴール間に真の双方向データ依存がなけ れば，その両者の実行順序を静的に定めることができる。
この静的スケジューリングの結果，ランタイム・システムでのスケジューリン グ・オーバヘッドが軽減されるだけでなく，スタックを用いたスレッド内ゴー ル実行管理が可能となり，GCの実行頻度も大幅に軽減される。
一方，スレッドについては従来ゴール単位で行なっていたような動的スケジュー リングが必要である。このスレッド・スケジューリングを効率的に行なうため， 我々は reply-firstと呼ぶ新たな方式を考案した。この方式ではコンパイラが データ依存解析時に求めたスレッド間共有変数を具体化するゴールの情報を用 いて，共有変数が生成される際に具体化を行なうスレッドの情報を付加する。 ランタイム・システムでは，あるスレッドが共有変数の具体化待ちにより実行 中断した際に，変数に付加された情報を用いて，具体化を行なうスレッドに高 い優先度を与える。
この二つのスケジューリング方式，すなわちスレッド化と reply-first方式が， 性能向上のために相補的な役割を果たすことを評価によって示した。すなわち， スレッド化は一つのプロセッサでの実行速度を向上させ，reply-first方式は 一つのスレッドが長時間実行されることによるプロセッサ間通信の応答悪化を 防止する。
www-admin@icot.or.jp