研究上の成果
本手法の依存解析では、型解析 [2]を、
具体化ゴール情報を付加した形に拡張して用いる。KL1では構造型データとそ
の各引数について、具体化するゴールがそれぞれ異なる場合が多く、単純にゴー
ル引数間の依存を追跡しただけでは、構造型データを介した依存が判明しない。
そこで、型解析により各引数が取り得る型の集合を得ると同時に、その集合要
素となる各々の型について、どのゴールが具体化するかも調べる。この結果、
ゴール
がデータ依存するゴール
は、
の入力引数の型集合の各要
素を具体化するゴールという形で得られる。
このデータ依存解析は、データ生成ゴールと参照ゴールの間の関係が、プログ
ラムの制御構造中における両者の位置にかかわりなく得られる。しかし、ゴー
ルの静的スケジューリングでは、項の例のように、兄弟関
係にあるゴール
の実行順序を決
定する必要がある。この例では
の子孫
に
がデータ依存する場合、
を
より先に実
行しなければならない。しかし
は
に制御依存しているから、結
局
は
に依存していることになる。したがって、
が
に依存するかどうかは、
の子孫を含めたデータ依存から判定できる。
スレッド内の逐次最適化については、スケジューリングが静的になったことに より、動的スケジューリングのための処理を削減することができる。また、解 析結果を利用することで、より効果的なコード削減が可能である。具体的には、 型情報を利用することにより取り得る引数の型が限定できるため、実行時の型 判定コードを簡略化できる。また、他スレッド中のどのゴールからも依存のな い変数については、スレッドのフックが起こらないため、その変数の具体化操 作については、フック判定が不要になる。さらに本手法は、我々がすでに行っ たプロセッサ間通信の最適化手法 [2] と型解析部分がほぼ共通であるため、両者を併用する場合にも解析コストの増 加を押さえることができる。
実行時においては、各スレッド内のゴールが逐次実行されることで、スタック を用いた効率的な実装が可能になった。この結果、スレッド内のデータ操作の コストを小さくし、ゴールの実行効率を上げることができる。また、並行処理 の単位がゴールからスレッドに拡大したことにより、処理の粒度を大きくし、 切替のオーバヘッドを相対的に小さくすることができる。さらに、スレッドの スケジューリングにも解析情報を利用することで、より効率的なスケジューリ ングが期待できる。
ソフトウェアとしての成果
ソフトウェア名称：ゴール・スケジューリング最適化KLIC改良版
KLIC改良版は、解析部とコード生成部からなる解析系、ならびに実行系からな る(図-1)。実装は、既存のKLIC処理系 に対する拡張の形で行う。
解析系は、既存のKLICコンパイラの一部の形で組み込まれる。
解析部は前記したように具体化ゴール情報を付加した型解析を行い、変数の型 情報およびゴール間のデータ依存情報を抽出する。実装上はほとんど独立した モジュールとなり、既存KLICで前処理が終わったプログラムを受け取り、解析 情報を出力する。これは今後のKLICの改良に対応しやすくすると同時に、他の 最適化を併用する場合に、解析部の拡張を容易にするためである。現時点では、 前記のプロセッサ間通信最適化を併用するための拡張を検討している。
コード生成部は前処理後のプログラムおよび解析系が出力する解析情報を受取 り、プログラムをスレッド分割し、各スレッドの最適化コードを生成する。生 成するコードがスレッド単位の逐次コードという従来とは異なったものになる ため、この部分は既存KLICのコード生成部を置き換える形になる。しかし、 KL1節からCへの変換部分は従来のコードと基本的に同じであり、不要な操作の 生成を取り除くための変更を加えるだけであるので、実装は従来のものをベー スとして行う。
実行系はKLICランタイム・システムの一部として組み込まれ、生成された複数 のスレッドの並行実行および管理を行う。各スレッドは従来の処理系における ゴールと同様、対応するコードへのポインタなどを格納したレコードを用いて、 スケジューリングを行う。また、スレッド内の実行環境は、各スレッドにそれ ぞれ独立したスタックを持たせることで、中断の際の切替オーバヘッドを小さ くする。実装は、これら本手法で新たに必要なもののみを対象とし、同一化機 構など低レベル処理を行うランタイム機構は、既存のものをそのまま利用する。 このため、ジェネリック・オブジェクトなど既に作成されたユーザ定義モジュー ルを変更する必要は一切ない。
現在、単一プロセッサのプロトタイプ版について設計を進めている。
残された課題
96年度は、まず単一プロセッサ版プロトタイプ処理系の実装および性能評価を 行い、その結果を元に処理系の改良とマルチプロセッサ版の開発を行っていく 予定である。
解析系については現在単一プロセッサ上で動作する場合を対象としている。物 理的な並列プロセスの各々に本手法を適用することにより、プロセッサ間依存 の解析を拡張するだけで、容易にマルチプロセッサ環境に対応できると考えら れる。実行系についても、単一プロセッサ版のランタイム機構を個々のプロセッ サ上で動作させることで対応できる。ただし、本手法によるスレッド単位のゴー ル・スケジューリングが並列実行の効率に与える影響については、今後詳細な 検討を行う必要がある。
解析情報の利用に関して、従来のKLICの生成するコードに対する調査から、ス レッド内の逐次処理を最適化する際にいろいろと有用であるとの見通しを得て おり、詳細な最適化手法を確立することが、今後の課題となっている。また、 実行時のスレッド・スケジューリングにおいても、この情報を利用してより適 切な戦略がとれる可能性がある。これについても、今後詳しい検討を行ってい きたい。
最終的には、前記したプロセッサ間通信の最適化も併用し、プロセッサ内・プ ロセッサ間のオーバヘッドを共に最小化するような、効率のよい処理系の実現 を目指している。
自己評価
KL1プログラムのスレッド化に関する最大の課題である依存解析を、型解析を 応用した手法で実現できる見通しを得られたことは、極めて大きな成果である。 また、静的スケジューリングによって、従来のスケジューリングよりも効率の 良い処理系が得られることも明らかになり、今後の実装によってKL1の実行効 率改善に大きく役立つものと考えている。
