| 平成７年度 委託研究ソフトウェアの 提案 |
このプログラム開発容易性の観点から，並列プログラミングの発展に貢献する ことが期待されているのが，KL1 をはじめとする並行／並列型のプログラミン グ言語である。これらの言語は，プログラムの並行性／並列性の記述を言語の 基本的プリミティブとして備えているため，並列処理にともなうバグ混入を最 小化できるという特質を持つ。また，並行／並列プロセスのネットワークを自 然に記述できるため，所謂データ並列に留まらない多種多様な応用とプログラ ミング・パラダイムに対する高い包容力も有している。
しかしその一方で，並列処理の重要な側面である高速性の観点からは，これら の並行／並列型言語の処理システムが十分な性能を持っているとは言えない。 この性能上の問題点の大きな理由に，言語の本質である並行性制御にともなう オーバヘッドがある。KL1 はその端的な例の一つであり，各々のゴールが並行 実行の単位であるため，ゴール・スケジューリングの方式がプログラムの性質 に適合していないと，本来逐次的に実行するのが最適な部分を並行実行するな ど，無駄な処理によるオーバヘッドが著しく大きくなることがしばしばある。
このような問題点を解決し，並行／並列型言語を真に並列処理に適してものと する努力は急務であり，論理型言語だけではなく様々な種類の言語について研 究がなされている。
一般に並行／並列型プログラムのスケジューリングでは，逐次実行が最適であ るようなシーケンスを発見し，それを逐次的に実行する逐次化が重要である。 例えば KLIC などこれまでの 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 が未生成の部分を発見して中断してしま うことがしばしばある。この不完全なメッセージによる中断は，一つのメッセー ジが通信される過程で何度も起こることがあり，かえって性能を悪化させてし まうことが多い。
以上のように，これまでに実装／提案されているゴール・スケジューリング手 法では，高頻度のプロセス間通信を行なう並行／並列プログラムの性能に大き な問題がある。この問題を整理すると，以下のようになる。
そこで，中断するゴール自身がデータ依存「していない」ようなゴールは，ス ケジュールしなくてもデッドロックしないことを利用することが考えられる。 即ち，既定のスケジューリング順序と逆方向のデータ依存がないようなゴール 列に対しては，その中のあるゴールが中断すると後続のゴールを一切スケジュー リングしないという方法が考えられる。この方法は，データ依存関係を順方向 のみにできるようなプログラム断片をプロセスとし，プロセス内のゴールをス タックなどを用いて逐次的に実行し，中断したならばプロセス全体を中断させ るという，他のプログラム言語でしばしば用いられる方法で実現できる。
この方法の問題点の一つは，「依存関係が絶対に存在しない」ことを解析する 必要があることであり，これは一般に「依存関係が存在する」ことの解析より も困難である。従ってこの問題に関する良い解を得ることが，本研究の大きな 目標の一つとなる。この他，中断ゴールに依存しない後続ゴールを実行しない ことが，性能上の問題になることも考えられるが，これについては将来の課題 とする。
次に (b) の問題点は，他のプロセスのゴールを再開させるようなゴール（ユ ニフィケーション）の実行，あるいは他のプロセスへの制御移行を，自プロセ スがデッドロックしない範囲でできるだけ遅延することにより，多くの場合に は解決できると考えられる。従って，(a) と同様に依存関係が存在しないこと の解析が重要な役割を果たす。また我々が既に行なった，プロセッサ間通信の 最適化[3]とも密接に関連し，通信量の削減に応用できるものと考えられる。
| [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 ユーザはプログラムを一切変更することなく，ゴール・スケジューリングを最 適化した実行コードを得ることができる。
www-admin@icot.or.jp