近年、安価なネットワークやPCが普及してきたため、 マルチプロセッサマシンやPCクラスタなどの並列計算機環境が、 エンドユーザにも手が届くものになりつつある。 こうした資源を生かすには、従来の高性能な並列言語処理系だけでなく、 お手軽に並列処理を記述できるプログラミング言語と処理系が必要である。 逐次環境ではPerlなどのスクリプト言語がCなどの性能重視型言語を 補完するものとして普及しているが、 並列プログラミングにおいてはこのような言語はあまり存在しない。
そこでPerlをベースとする並列スクリプト言語(Perl)+の研究を行った。 (Perl)+はRPCによりPerlサブルーチンを並列タスクとして実行する機能を持つ。 RPCの返り値の評価は代入時点ではなく値の参照時点まで遅延されるため、 呼び出し側はRPCを行った後、自分も並行して別の処理を行い、 その後に先ほどの返り値を評価する、 といったスタイルのプログラミングが可能である。
また、タスク間の情報のやりとりはサブルーチンの引数・返り値を用いるほか、 通信ストリームを介したメッセージ通信も可能である。 ストリームはプログラム上、特殊なファイルとして扱われ、 同名のストリームをオープンしたタスク同士が、通信相手として結びつけられる。 ストリームに対するメッセージの送受信は、 ファイルと同じ入出力構文により行うことができる。
マルチエージェント型の並列モデルと宣言的な通信路を用いた、 並列言語Orgelの研究を行った。
Orgelのプログラムはストリームと呼ばれる抽象通信路で結合された エージェントの集まりとして記述する． エージェントは枠組として，非同期メッセージの受信・応答機構や 未到着メッセージの参照に対する中断・再開機構を備える． ユーザはこのエージェントが実行する逐次コードを記述し、 その中で明示的なメッセージ送信を行う。
Orgelでは、ストリームとエージェントの接続を、 操作ではなく宣言として行う。 KL1などでは並行プロセスやストリームを動的に生成し、 接続も操作的、つまり動的に行う。 これに対してOrgelでは、エージェントやストリームを変数として宣言し、 これらの間の接続関係も宣言文で記述する。 これにより、 一対一、一対多といったエージェント間の通信関係がコンパイル時に決定され、 通信処理の効率よい実装が可能になる。
第五世代計算機計画で開発された並列論理型言語は、 暗黙の通信・同期により並列記述が容易であり、 また論理型言語であることから非定型的な非数値処理に適している。 このため、 とくに記号処理・知識処理といった分野の並列プログラム記述に力を発揮する。
しかし、Cなどの手続き型言語に比べ、 KL1ではユーザが明示しないために処理系が解決すべき要素が多い。 たとえば通信・同期のタイミング、 並列・並行実行の最小単位であるゴールの実行順序(スケジューリング)などである。 これらの要素は一般に実行時まで決定できないため、 多くの処理系では実行時に動的な処理を行っており、 効率を低下させる要因となっている。 この結果、Cなどの処理系と比較して性能が劣るという欠点を生じている。
そこで、この動的処理の一部をコンパイル時に静的に解決することによって、 KL1処理系の実行効率向上を図った。 具体的には、KL1プログラムの静的解析を行って実行時の振舞いを予測し、 その結果を用いてプログラムを最適化する手法を開発した。
論理型言語の解析手法としては、従来よりさまざまな方法が提案されている。 我々の研究では、制約充足による型解析をベースとし、 型情報を拡張して依存ゴールや入出力方向といった情報を持たせることで、 プロセッサ間の通信パターン解析やゴール間の依存解析などに応用した。
論理型言語では、二つのゴールに同じ変数を引数として与えることで、 この変数が両ゴールの共有変数となる。 KL1ではこれらのゴールが違うプロセッサで実行される場合、 プロセッサ間の共有変数が生まれる。この変数へのアクセスが生じると、 ランタイムはプロセッサ間の単一化を実現するための物理通信を自動的に行う。
この機構により、KL1では他のプロセッサが生成した値をもらうためには、 単に共有変数を参照するだけで良く、明示的なsend/receiveを記述する負担がない。 しかし、どの値を送信すべきかはその値が参照されるまでわからないため、 値が参照されるたびに細粒度の通信が発生し、大きなオーバヘッドとなる。
この問題はとくにリストなどの構造型データにおいて大きな速度低下を引き起こす。 構造型データの場合、そのどの要素が必要になるかは各々が参照されるまで わからない。このため、リストの個々の要素をそれぞれ1メッセージとして転送 してしまう。これを改善するには構造型データを一度に転送すれば良いが、 この場合、結果的にデータの一部しか参照しなければ、 残りの転送は無駄になってしまう。
そこで我々の手法では、プログラムの静的解析により参照される部分を抽出し、 その部分だけをまとめ送りする送信コードを生成する。 本手法では、 リストの先頭n要素を参照するといった実行時の値で決まる部分は予測できない。 しかし、リストのリストに対し、 外側のリストは参照するがネストした内側のリストは参照しない、 といったパターンを抽出し、 外側のリスト要素のみまとめ送りするコードを生成することができる。
実行順序の決まっているPrologと異なり、 KL1では生成済みゴールからあるスケジューリング戦略に従って次実行ゴールを選ぶ。 このゴールが未具体化引数を参照していれば中断して他のゴールの実行に切り替え、 後に他のゴールによりこの未具体化引数が具体化されれば、 中断したゴールの実行を再開する。 このため、節内のゴールの記述順序に関わりなく、 依存関係に応じて自動的に正しく実行される。
しかし、このゴールの中断・再開機構のオーバヘッドのため、 単一プロセッサ上での逐次実行効率はCなどに比べると劣っている。 とくに、すべてのゴールについて中断可能にするため、 ゴールの環境はヒープ上に生成しており、 Cなど環境をスタックで管理する言語実装に比べると、 参照の局所性が低い、ヒープのGC時間だけ実行時間が増加する、といった問題がある。
そこで静的解析によりゴール間の依存解析を調べ、 ゴール間の相互依存がない部分についてはデータフロー順に並べ替え、 実行順序を静的に固定する。 この実行順を固定したゴール列をスレッドと呼ぶ。 スレッド間は従来のゴールと同様に、 データ依存による中断・再開によって動的スケジューリングを行うが、 スレッド内ゴールはスタック上に環境を生成し、固定順序で高速に実行できる。
最終更新: 2007年 3月 20日 火曜日 15:12:30 JST
御意見、御感想は ohno@arch.info.mie-u.ac.jp まで