今日,並列計算機は実用段階に入り,商用の並列計算機も数多く発売されている.例えば,共有メモリ並列計算機なら数〜数十台程度の規模のものが,分散メモリ並列計算機なら千台以上の規模のものが,現実に稼働している.このため,ハードウェアの面からみれば,並列計算はもはや現実のものである.しかし,ソフトウェアの面からみれば必ずしもそうとはいえない.並列処理記述の負担が,プログラマにとって非常に重いためである.

　現在,プログラマは主にライブラリを用いて明示的に並列処理を記述している.このため,プログラマがバグのない並列プログラムを書くことは容易ではなく,並列計算機の普及にも関わらず,並列プログラムは一般的ではない.

　この困難を克服するため,これまでにさまざまな研究がなされてきた.それらは,大きく分けて,並列化コンパイラの研究と並列プログラミング言語の研究に分類される.

　並列化コンパイラは,逐次のプログラミング言語で記述したプログラムを,コンパイラが解析することにより,並列に実行できるようにするものである.ある意味理想的な手法であり,数値計算のような極めて定型的で単純なプログラムにおいては,すでにかなりの成功を収めている.しかし,より複雑なプログラム,例えばコンパイラやエディタのようなプログラムでは,解析が困難になるため,並列化の効果はまったく期待できない.

　並列プログラミング言語は,並列性を採り入れた新しい言語を定義し,それでプログラムを記述することで,並列プログラムの記述を容易にしようというものである.本論文の対象言語であるFlengもこの部類に入る.並列プログラミング言語には,並列関数型言語,並列論理型言語,並列オブジェクト指向型言語などがある.並列関数型言語,並列論理型言語は,関数型言語,論理型言語といった,理論的に扱いやすい言語をベースにすることで,プログラマに並列処理の複雑さを意識させることなく,容易に並列プログラムを記述できるようにしたものである.並列オブジェクト指向言語は,プログラムを並列に動作するオブジェクトとしてモデル化することにより,やはり容易な並列プログラムの作成を目指している.

　我々の研究室では,このような点を考慮に入れ,並列論理型言語Flengを設計,実装している.Flengは,複雑なプログラムにおいても容易に並列プログラムが記述でき,かつ大量の並列性を抽出可能であるという利点がある.現実に,Flengコンパイラ自身もFlengで記述され,並列に動作している.しかし,Flengを含め,これら並列プログラミング言語では,実行時のオーバーヘッドが大きく,実行効率を向上させるのが難しいという問題点がある.

　このオーバーヘッドは,大きく分けて2種類に分類できる.細粒度実行に由来するオーバーヘッドと配列処理に由来するオーバーヘッドである.本研究では,これらのオーバーヘッドを取り除く手法を提案し,高い性能を発揮するFlengの最適化コンパイラの実装を行なった.

　まず,細粒度実行に由来するオーバーヘッドについて説明する.Flengでは,すべてのゴール(Flengにおける実行の単位)を並列に実行する.決まっていない値を参照しなければ実行できないゴールは実行を中断(サスペンド)し,他のゴールによって値が決定されるまで待つ.値が決定された時点で,そのゴールは実行を再開(アクティベイト)する.このような機構を用いることで,複雑なプログラムからでも容易に大量の並列性を抽出することが可能になる.ただし,この機構を矛盾なく実現するため、変数は単一代入変数であり,書き換えることはできない.

　このような機構を用いると,並列性の抽出は容易に行なうことが可能になるが,並列実行の単位がゴール一つ一つといった,非常に細かなものになる.このため,ゴールの起動やサスペンド,アクティベイトといったそれぞれのゴール間での同期のコストが大きなものになってしまう.

　この問題点を解決するため,ゴール融合という手法と強制インライン展開という手法を提案した.

　ゴール融合は複数のゴールを一つにまとめることで,粒度の最適化を行なうものである.このことで,ゴールの起動や同期といったオーバーヘッドを削減することができる.しかし,これは一種のプログラムの逐次化に相当する.もともと並行に動作するものとして記述されたプログラムの逐次化を行なうため,デッドロックの危険性が存在する.したがって,デッドロックを防ぐため,プログラム全体に渡る大域的なデータフロー解析を行ない,安全にゴール融合を行なう手法を提案,実装した.

　次に,強制インライン展開は,同期の部分も含めてインライン展開を行なうことで粒度の最適化を行なうものである.通常のインライン展開では,サスペンドする可能性のあるゴールについては展開できなかった.これは,値を待つ必要があるゴールをインライン展開すると,本来待たなければならない値を待たずに実行することになるからである.強制インライン展開は,サスペンドする可能性のあるゴールについても,その同期部分を含めてインライン展開することで,任意のゴールについてインライン展開を可能にした.ただし,任意のゴールで展開が可能なため,過剰な展開によるコードの爆発を防ぐ必要がある.本研究では,高い性能を保ちながら,過剰な展開を防ぐ方法について提案,実装した.

　本研究では,これらゴール融合,強制インライン展開の手法について実装,評価を行ない,最大数倍以上の速度向上を達成した.

　二つ目の問題点は,配列処理に由来するオーバーヘッドである.先に述べたように,Flengでは,単一代入変数を用いている.このため,もとの配列から一部だけを変更した配列を得ようとした時,新しい配列を確保して,変更部分以外を元の配列からコピーする必要がある.これは,ハッシュやヒストグラム,あるいは数値計算的なプログラムにとっては,非常に大きな問題である.場合によっては,計算の複雑さのオーダーまで変えてしまう.

　この問題を解決するため,本研究では,配列更新時のコピー操作を除去する手法を提案した.この手法では,更新時にその配列を参照しているゴールが他になければ安全に破壊代入による更新が可能であることを利用する.コンパイル時に配列の参照と更新を逐次化してしまい,配列の更新時にはその配列を参照しているゴールが他にないことを保証する.ただし,ゴール融合の場合と同様,プログラムの逐次化はデッドロックの危険性を持つため,大域的なデータフロー解析を行ない,安全に逐次化を行なう.配列のコピー除去を行なうことで,最大数十倍の速度向上を達成することができた.

　また,配列処理を行なう際,並列化コンパイラなどで用いられているようなデータ並列的な並列性の抽出が行なわれていない.データ並列とは,配列の各要素に対し,独立に操作が可能な場合,それぞれを並列に実行する方法である.このため,データ並列機構を用いれば抽出可能な並列度を抽出することが出来ず,並列度が低下する場合があった.

　この問題を解決するために,Flengコンパイラでデータ並列性を抽出する手法を提案した.この手法では,配列のコピー除去を行ない,破壊代入による配列更新を行なう繰り返しにおいて,並列化コンパイラで提案されているような繰り返しを跨ぐデータ依存を解析し,安全にデータ並列性を抽出する.この手法を用いることにより,最大数倍程度の速度向上を達成した.

　このように,本研究ではFlengコンパイラにおいて新しい最適化手法を提案,実装,評価し,従来のコンパイラに比べて数〜数十倍の速度向上を達成した.

　本論文は、「並列論理型言語Flengの最適化コンパイラに関する研究」と題し、6章からなる。並列論理型言語は、その並列性記述の容易さと取り出し得る並列度の高さから特徴のあるプログラミング言語であるが、手続き型言語に比してその実行オーバヘッドが大きかった。本論文は、並列論理型言語の一つであるFlengを題材に、その実行オーバヘッドを改善する最適化コンパイラの作成手法を論じたものである。

　第1章「序論」は、本研究の背景と目的、並びに本論文の構成をまとめたものである。

　第2章「並列論理型言語Fleng」は、言語Flengの言語仕様の概要を述べ、次に、ソースコードレベルで低レベルな記述が行えるよう拡張した言語仕様を与えている。この拡張は、コンパイラの最適化部がソースレベルのトランスレータとなっていることから来る要請であり、プログラマの与えたソースコードは、この拡張された言語表現に変換される。次にこのコンパイラ作成時に用いた基本的なデータ構造を説明するとともに、コンパイラとランタイムシステムとからなる処理系の構成を述べている。

　第3章「粒度最適化」は、並列論理型言語の問題点の一つである処理粒度が細かいことに起因するオーバヘッドに対処する手法について述べたもので、ゴール融合と強制インライン展開の二つの手法を提案している。ゴール融合は、複数のゴールをまとめることでオーバヘッドを削減する手法であるが、不用意にそれをおこなうとデッドロックを引き起こす恐れがあるため、それが起こらないことを保証する必要がある。本論文では、そのための大規模なデータフロー解析のアルゴリズムを提案し、それを実装している。次に、別種の粒度制御手法として、強制インライン展開を提案している。これは、データフロー解析が不要なものであるが、通常のインライン展開と異なり、述語のヘッド部分に存在する同期処理のインライン展開も可能であって、それをボディ部に移動させてインライン展開を実現している。これらの手法を、並列推論エンジンPIE64の上で評価を行った結果、問題にもよるが、この最適化を行わない場合に比べて、2倍から4、5倍の性能向上が得られており、両方式を組み合わせることで更に大きな改善が見られることを示している。ゴール融合と類似の方式は、関数型言語に対してSeparate Constraint Partitioningと呼ぶ手法が提案されているが、本論文で提案している手法は、対象言語が論理型で異なっているということの他に、より一般化された手法となっており、性能的にも優れている他、強制インライン展開と組み合わせることで更に有効な粒度制御方式となっており、他に例を見ない。

　第4章「配列処理の最適化」は、並列論理型言語が単一代入変数を用いているため発生するオーバヘッドの中で特に問題となる配列処理に対するオーバヘッド削減策と、配列処理に対する自動並列化手法について述べたものである。前者は、配列の一部に新しい値を代入しようとすると、すべての配列のコピーが必要となる問題で、後者は、この言語がデータ並列性を抽出する機構を持たないことによる問題である。前者に対しては、配列の参照と更新を逐次化し、更新時には参照が終っていることを保証することによって破壊代入を許しコピーを不要とする手法を提案し、後者に対しては、ある制約条件を満たした場合、ゴールを複数に場合分けして並列に実行する手法を提案している。論文では、これらを一つのプログラムとして実装し評価した結果、対象プログラムにもよるが、数倍から数十倍に至る性能向上が得られたことを示している。オーバヘッド削減の手法それ自体は新しいものではないが、従来の研究は逐次型の関数型言語に対する検討が中心であり、並列型の関数型言語に対する検討は少ない。また、並列論理型言語KL1におけるMultiple Reference Bitを用いる手法との比較では、プログラマに与える負担という点で、本手法がより優れている。更に、Flengのような単一代入言語に自動データ並列化抽出を行った例はない。

　第5章「考察」では、Flengと他のプログラミングモデルとの比較を行ってFlengの有効性を主張するとともに、今後の課題について述べている。

　第6章は、「結論」である。

　以上、これを要するに本論文は、複雑な並列プログラムを作成する場合の書き易さと実行並列度の高さと言う点で優れた並列論理型プログラミング言語Flengに対して、その短所である実行オーバヘッドが大きいことに対処する最適化手法を検討してコンパイラを与え、この手法を導入することによって著しく高速な処理が可能であることを示したもので、情報工学上貢献する所少なくない。

　よって、本論文は、博士(工学)の学位請求論文として合格と認められる。