| 平成９年度 委託研究ソフトウェアの提案 |
| 研究代表者： | 中島 浩 教授 |
| 豊橋技術科学大学 情報工学系 |
PIM ならびに KLIC の研究・開発を通じて，KL1 の逐次的なプログラムの実行 性能は，他の論理型言語や一般の記号処理向き言語のシステムと比べて，遜色 のない水準に達している[1]。しかし，手続型やオブジェクト指向言語と比べ ると，その実行性能は必ずしも満足できるものとはいえない。
この主な原因として，我々はプロセッサ間およびプロセッサ内での並列／並行 実行のメカニズムが過度に一般化された動的なものであることに着目した。即 ち，モード解析[2]などの静的解析技術を用いることによって，並列／並行実 行のオーバヘッドを大きく削減できるのではないかと考えた。
このような研究方針に基づき，我々は既にプロセッサ間通信の最適化技法[3] と，ゴール・スケジューリングの最適化技法[4,5]を確立し，それぞれ大幅な 性能向上が得られることを示してきた。これらはいずれも変数のタイプ解析に 基づくものであり，一つの解析技術を様々な局面で応用できることを示したも のでもある。そこで，これまでに得られた成果に基づいて，静的解析を利用し た高速化手法をさらに追求することで，より優れた KL1 の処理系を得ること が本研究の基本的な方針である。
KL1 の高速実行のための有力な方法として，我々は静的解析に基づくゴール・ スケジューリングの最適化方式に関する研究を平成７〜８年度に行なった [4,5]。
この方法では，まず静的解析によってゴール間のデータ依存関係を調べ，同一 クローズから起動される二つのゴール p, q が特定の順序で（例えば p->q の 順序）逐次実行可能か否かを判定する。その結果，逐次実行可能と判定されれ ば p, q は一つの「スレッド」に属するゴールとして，逐次的に実行される。 従って p の実行が中断しても q はスケジューリングされず，従来のスケジュー リング方式の欠点である無駄な中断が除去される。またスレッド内の実行が完 全に逐次的であることを利用し，ゴールの実行環境をスタックで管理すること によって，ガベージ・コレクションの起動回数を削減することもできた。この 他，動的なスケジューリング単位がスレッドとなったために生じる並列実行時 の応答性能の劣化を補償するために，スレッドのスケジューリング優先度を動 的に定める reply first scheduling を考案して実装した。
以上のスレッド化技法を用いることにより，KL1 の実行速度が 1.3〜2.9 倍に 向上することが確かめられた。しかしスレッド化技法には，さらなる性能向上 のための改善の余地が数多くある。例えばスレッド内の実行環境を管理するス タックには，オリジナルの KLIC のゴール・レコードとほとんど同じものが格 納されており，ガベージ・コレクション以外での性能向上への寄与はほとんど ない。また，スレッドごとのスタック割付けアルゴリズムも単純であるため， スタックの伸縮が頻繁に生じるプログラムでは，割付けのためのオーバヘッド が小さくない。
またスレッド長をできるだけ大きくするようなスレッド化を行なっているため， 極めて粒度が大きなスレッドが生成されることが多い。例えばゴール p, q に 相互の依存関係がなく，逐次／並行のどちらでも実行可能な場合，現状ではス レッド長を大きくするために必ず逐次実行（例えば p->q の順序）が行なわれ る。その結果，q による具体化を必要とするようなゴールが別のプロセッサで 実行されている場合，p の実行によって応答性能が悪化することがある。
本研究の目的は，上記のようなスレッド化技法の問題点を解決することにある。 即ち；
の２点が本研究の目的である。
現状のスレッド内実行方式の問題点を細かく見ると，以下のようになる。
一方，クローズ環境法では q の完了時に制御が q->p->r と移動するのに 対し，ゴール環境法では q->r と移動するため制御移行オーバヘッドは小 さい。したがって，ゴール引数生成と制御移行のどちらのオーバヘッドが 大きいかを評価／勘案し，スレッドの実行方式を見直す必要がある。なお 現状では q が一定の条件を満たせば q->r の分岐を直接分岐とする最適 化を行なっているが，この方法や gcc のラベル変数利用などはどちらの 環境管理方式にも適用できる。
また現状では実装を簡単にするために，上記の X をヒープに割付け，s に対しても reference pointer を渡しているが，これを s のゴール・レ コード中に割付けるようにするのは容易である。その際に生じる所謂ロー カル変数の安全性問題については，スレッド化のための依存解析によって， ほとんどの場合はコンパイル時に解決できる。
そこでスタック・ページ割付について；
などの改良が考えられる。
また，現状のスレッド生成方式では，あるスレッド t に属するゴール p, q について，静的に定められた実行順序が p->q であることは，必ずしも q が p に依存することを意味しない。即ち p が q に依存しないこと，つまり p の中断時に q をスケジューリングしなくてもデッドロックが生じないことが 確かめられれば，実行順序を固定する。この方法は，例えば quick sort の二 つの再帰ゴールのように，相互依存関係が存在しないゴール群に対して不要な スレッド生成を行なわないようにするというメリットがある。
しかし，上記の q が他のスレッド s が参照する変数を具体化するようなもの であるとき，以下のような問題が生じる可能性がある。
これらを解消するためには，q を t とは別のスレッドとする必要があるが， そのためには以下のような項目について深く検討しなければならない。
<2> q の分離を静的に行なうか，動的に行なうか。静的に行なう場合，分離戦 略のプログラムへの適合性が性能に強く影響することが予想されるが，適 切に戦略を定めるのは困難が予想される。したがって，コンパイル時には 分離可能（あるいは「分離希望」）であることを指示し，実行時に判断す る方法が考えられる。
<3> 動的分離の場合の分離タイミング。p, q が属するクローズの実行時に分 離するのは容易であるが，分離判定に使用できる情報が不十分であること が予想される。例えば，クローズ実行時に他のスレッドからの具体化要求 がなければ分離しないとすると，上記の(b1), (b2)の問題が解消できない ことが多くなると予想される。逆に p の実行開始後でも分離できるよう にすると，q を分離可能にするためのオーバヘッドが大きくなることが予 想される。
<4> 動的分離の場合の条件。他のスレッドからの具体化要求以外に，存在する （あるいはアクティブな）スレッド数などを勘案することも考えられ，特 に分離タイミングをクローズ実行時にする場合には必須であろう。その場 合，分離条件に関わるパラメータ（例えばスレッド数の上限）の設定をど のように行なうかが課題となる。
以上のように検討が必要な課題が数多くあるが，いずれも研究的価値が高い課 題であると考える。
| 氏 名 | 所 属 | |
| 研究代表者 | 中島 浩 | 豊橋技術科学大学 *1 |
| 研究協力者 | 貴島 寿郎 | 豊橋技術科学大学 *1 |
| 研究協力者 | 大野 和彦 | 京都大学(博３) *2 |
| 研究協力者 | 杉山奈美代 | 豊橋技術科学大学(修１)*1 |
*1 情報工学系／情報工学専攻
*2 工学研究科 情報工学専攻
解析系には，これまでのデータ依存関係に基づくスレッド化機能に，従来はス レッドに属していたゴールを別スレッドとして分離する，あるいは動的に分離 可能とする機能が加えられる。このため，ゴール間あるいはスレッド間のデー タ依存関係に関して，従来版よりも詳細な解析を行なう。またスレッド内のゴー ル呼び出しについても，実行系の改良に伴う生成コードの修正を行なう。
実行系については，まずスタックを利用したスレッド実行環境の管理が大幅に 修正される。また動的スレッド分離を行なう場合には，従来の reply first scheduling の改良や新たな機能の導入により，解析系の指示に基づくスレッ ドの分離機能を追加する。
実行系も KLIC ラインタイム・システムの一部として組み込まれる。ユニフィ ケーション機構など，既存のランタイム機構はほとんど影響を受けないので， ジェネリック・オブジェクトなど既に作成されたユーザ定義モジュールを変更 する必要は一切ない。
また本研究での最適化は，ほとんど全てのプログラムに効果があると予想され るが，特にプロセスを指向したプログラミング・パラダイムを採用したプログ ラムについて，大きな効果を発揮するものと期待できる。また今後のプログラ ム開発において，従来のように処理系の性質を過度に考慮することなく，自然 なプログラミングで十分に高い性能を得ることができると期待される。
www-admin@icot.or.jp