(4) ＫＬ１のゴール・スケジューリング最適化

［研究テーマ］	ＫＬ１のゴール・スケジューリング最適化
［研究代表者］	京都大学・工学研究科・助教授 中島 浩（現・豊橋技術科学大学　情 報工学系教授）

1. 研究進捗状況

本研究の目的は、解析情報により中断・切替のオーバヘッドが少なくなるよう な、最適化ゴール・スケジューリング方式を得ることにある。

昨年度の研究では、ゴール間のデータ依存関係について、実行時にデッドロッ クが生じないことを保証する条件を求めた。これを利用し、静的スケジューリ ングされたゴール列であるスレッドを生成し、これを動的スケジューリング対 象とすることにより、実行時オーバヘッドの削減された逐次処理系を実現した。

本年度の目的は、このスレッドのスケジューリングにおいて、最適な実行方式 を得ることである。最終的に並列処理系を実装するため、この実行方式は並列 実行においても最適なスケジューリングを行う必要がある。

2. 現在までの主な成果

従来の KLIC では、具体化により再開可能となったゴールを優先する resumption first 方式が用いられている。昨年度は、これのスケジューリン グ単位をスレッドに変更した方式を用いていた。

しかしこの場合、中断したスレッドは原因変数が具体化されしだい再開される が、その変数を具体化するスレッド自体が優先的にスケジューリングされるわ けではない。そのため、他の無関係なスレッドが長期にわたってスケジューリ ングされる事態が生じうる。この結果、並列実行においては、他ノードからの データ要求通信に対する応答時間が長くなり、並列性低下の大きな要因となる 可能性がある。

本年度の研究では、producer first スケジューリング方式を考案し、現在、 詳細設計および実装を進めている。本方式は、あるスレッド Si が中断した場 合に、原因変数を具体化するスレッド Sj (または Sj を生成する先祖のスレッ ド)をスケジューリングすることで、先の問題を解決する。

具体的には解析系においてスレッド間の変数共有を解析し、共有変数の具体化 スレッドを求める。実行時には、共有変数は常に具体化スレッドへのポインタ を保持し、スケジューラが利用できるようにする。また、このポインタをデー タ要求メッセージに付加してやれば、ノード間での producer first スケジュー リング方式が可能になり、並列性の向上が期待できる。

3. 今後の研究概要

producer first スケジューリングに必要な解析情報を求めるよう、昨年度に 実装した解析系を拡張する。また、本スケジューリング方式を用いた並列版処 理系の設計・実装を行う。

4. 今年度目標成果

ゴールのスレッド化および前述の producer first スケジューリング方式を採 用した、並列実行対応版の解析系／実行系を実装する。この最適化実装により， 広い範囲の KL1 プログラムが高速化されると期待できる。