外部発表論文
静的解析手法
昨年度提案した依存解析では、ゴールのスレッド化を行うためにゴール間の依 存関係を抽出していた。これを拡張し、各変数についてこれを具体化・参照す るゴールおよびスレッドを解析する。複数のスレッド間で具体化・参照される 変数は、スレッド間の共有変数とみなすことができ、これを追跡することによっ て、以下の最適化が可能になる。
あるループについて、
並列環境におけるスレッドスケジューリング
KL1のゴールスケジューリングとしてスレッド化手法を用いることで、並列実 行単位の粒度が大きくなる。これは、プログラムの並行性制御のオーバヘッド を小さくする反面、プログラムの持つ並列性を低下させてしまう問題がある。 とくに、他ノードからの返答を待って中断したスレッドが待たされることによ る動的な並列性の低下が性能に与える影響は、スレッド化を行うことで、従来 のものよりも大きなものになってしまう。
しかし、従来のゴール・スケジューリング方法では、要求データを生成するゴー ルが優先されるような機構がないため、要求メッセージに対する応答性は保証 されない。この問題はスケジューリング単位の大きいスレッド・スケジューリ ングでは深刻であり、要求データの生成に無関係かつ実行時間の長いスレッド がスケジューリングされてしまうと、N cの アイドル時間が非常に長くなる可能性がある。
そこで本研究では、中断スレッドに要求されたデータを返信するために必要な 具体化や同一化を行うスレッドを優先的にスケジューリングする reply first scheduling方式を提案する。本方式では、他ノードからデータ要求 メッセージが到着したり、自ノードでの実行スレッドが未具体化変数への参照 で中断したりした場合、該当データを具体化するスレッドをスケジューリング する。これにより、並列実行においてデータ要求への応答性が向上し、並列性 を引き出すことができる。
前記の静的解析により、スレッド間の共有変数Xについて、Xの 具体値を生成する可能性のあるゴールが得られる。よってスレッドT suspが未具体化変数Xによって中断した場合、 この解析情報によりXを具体化する可能性のあるスレッドT unifyを特定することが可能である。KL1では Xが具体化されるのは1度だが、実行パスによっては、Xを具体 化するスレッドが異なる可能性がある。このため、静的にはT unifyを一意に定めることはできない。そこで本手法 では、この静的解析情報を利用し、実行時に動的に決定される部分を追跡する 機構を生成コード中に組み込むことで、このスケジューリング方式を実現した。
本スケジューリング手法の有効性を簡単なプログラムを用いて評価した。その 結果、ゴール単位のものでは台数効果がでるがスレッド化では台数効果が出な いプログラムでも、ゴール単位と同等の台数効果が得られた。またゴール単位 のものでも台数効果がでないようなプログラムに対しても、reply first schedulingを適用することで、そのプログラムのもつ並列性を最大限に抽出す ることに成功し、2台で1.4倍の台数効果を得ることができた。
ソフトウェアとしての成果
ソフトウェア名称：ゴール・スケジューリング最適化KLIC
昨年度は逐次版のみ対応した試作版処理系を作成した。これは解析部とコード 生成部からなるコンパイラ部、ならびに実行系からなる。コンパイラ部のうち、 解析部は具体化ゴール情報を付加した型解析を行い、変数の型情報およびゴー ル間のデータ依存情報を抽出する。コード生成部は解析系が出力する解析情報 を受取り、プログラムをスレッド分割し、各スレッドの最適化コードを生成す る。実行系はKLICランタイム・システムの一部として組み込まれ、生成された 複数のスレッドの並行／並列実行および管理を行う。
本年度では、これを元に以下の拡張を行い、並列実行に対応した処理系を作成 した。
解析部ではゴールのスレッド化を行った後、再帰呼出しによるループ構造の識 別、およびスレッド間の共有変数の識別とその参照・具体化スレッドの解析を 行う。
コード生成部では、解析部が出力するモード情報を利用し、共有変数に対し、 自分を出力出現に持つスレッドへのポインタを保持させるためのコードを生成 する。一方、ある共有変数を出力にもつスレッドは実行時に変化するため、そ の変数が保持するポインタが常に自身を出力に持つスレッドへのものであるよ うに、動的に書き換えるためのコードも生成する。
また実行系ではreply first schedulingを行うための機構を追加し、プログラ ムの持つ並列性を最大限に抽出する。実装においては共有変数などの実現のた めに新しいデータ構造を生成したことや、同一化などにより共有変数を出力に もつスレッドが変化することなどから、同一化機構等を含む処理系核全般の変 更／拡張を行った。
残された課題
本年度の研究成果であるreply first schedulingについては、現在のところベ ンチマークによる性能評価しか得られていない。大規模なプログラムに適用し た場合の効果、あるいは副作用については、今後、評価を行う必要がある。
また、現在の実装は現行KLICの拡張という形で行っているため、KLIC自身の実 装に起因する原因により、我々の方式で期待される動作が完全に得られるわけ ではない。例えば、外部参照ポインタが単方向リンクになっていることにより、 ポインタを与えた側でのデータ要求に対するreply first schedulingは行われ ない。こうした問題点については、今後、KLICの基本部分も含めた実装方式の 見直しが必要である。
自己評価
スレッド化による逐次実行効率の改善については昨年度の研究で示されていた が、並列環境下では他ノードからの応答待ちによる並列性低下が懸念であった。 今回、静的解析情報を利用したreply first scheduling手法によりこの問題を 解決でき、逐次と同様に従来に対する性能向上が得られたのは、非常に意義の あることと考える。また、動的スレッド切替のタイミングにも解析情報を利用 することで、より性能向上を得ることができた。これらを実装した並列実行対 応の処理系が得られたことは、本研究の大きな成果である。