細粒度高並列言語は、問題に内在するすべての並列度を抽出できるため、非定型的な問題を高並列計算機上で実行するためのプログラミング言語として有望である。しかし細粒度高並列言語には、データ/プロセスなどの負荷をいかに分散させるかという問題、プロセスをどのような順番で実行するかというスケジューリング問題、といった並列言語に共通の問題点に加え、コンテクスト切替のオーバーヘッドという細粒度言語特有の問題点がある。これらの問題を解決する高性能な処理系実装の手法を確立することが課題になっている。本研究では、並列推論エンジンPIE64上へのCommitted-Choice型言語flengの高性能な処理系実装を目的とし、上述の問題を解決した言語処理系方式の提案と実装を行なった。

　flengにおける負荷分散とは実行単位であるゴールを分配することである。PIE64がハードウェアで負荷平滑を支援しているため、均等に負荷を配分することは容易であるが、負荷を完全に均等に配分するとデータの参照の局所性は低下してしまう。これに対応するために、静的負荷分割を行なう必要がある。静的負荷分割は、局所性のあるデータとゴールをグループにまとめる作業である。負荷分散時にこのグループを単位に分散を行なうことで、負荷の分散を抑制しメモリ参照の局所性を高めることができる。

　ここでは特に視覚的な場面を文脈情報としてとりあげたが、場面以外の因果関係などの時間的関係など、文脈の種類の中のより抽象的関係を用いて曖昧性を解消する問題についてもそれぞれのサブゴールに応じて同様なアプローチをとることが可能であると思われる。また本研究は機械翻訳の意味選択に具体的応用例を設定しているが、その基本的手法および知識は機械翻訳のみに限らず自然言語処理が対象としている広範囲の分野において有効である。情報検索の分野においては、ユーザが話題としている事柄の焦点を見つけ、状況の脈絡を判断し、場面に応じて解の優先づけを行なう。一般に検索を依頼するユーザはできるだけ迅速に結果を必要とし、また検索結果を表示する範囲も限られていることが多い。この点、本手法のような優先づけを行なうシステムでは、望む結果から順番に結果が提示される為、有利である。対話やマルチメディアインタフェースシステムにおいては、機械と人間との自然な対話が求められるため、言語表現の簡潔化がより進んだ状態となり、言語外知識による曖昧性解消の問題がさらに深刻になる。また対話の実時間性は処理の効率化を要請する。文書校正支援や抄録を行なうシステムにおいては、冗長な部分を除く点で、情報を圧縮する処理を行なうが、まず文章の脈絡の検出などの理解を行ない、再構成するというアプローチの場合には、本研究で提案している手法が有意に応用できるという可能性がある。

図表図1:提案手法での自然言語処理の流れとアーキテクチャ / 図2:Scene identification algorithm / 表1:多義性解消率

図表図3:場面に登録されている実文中の単語114個の曖昧性解消率(左)と場面に登録されていない実文中の単語227個の曖昧性解消率(右)。(横軸はバックトラック数であり、table:単語-意味対を場面情報に持つ場合、item:シソーラスの細かい分類を意味として持つ場合、category:粗い分類を意味として持つ場合、random:場面情報を用いない場合) / 表2:場面同定率

　flengにおけるスケジューリングは、実行単位のゴールの実行順序の制御である。通常の言語では、プロセスの実行順序は何らかの方法で指定されているが、flengでは基本的にどのような順番で実行してもかまわない。これは、単一代入変数と呼ばれる構造メモリによって実行制御が行なわれ、値が入っていない変数の値を必要とするゴールはサスペンドと呼ばれる機構で自動的にスケジューリングから外されるからである。しかし、このサスペンドは非常に重い動作なので、極力避けなければならない。このためには、プログラム中のデータフローを解析し、データフローに沿って実行を行なう必要がある。これが静的スケジューリングである。

　コンテクストスイッチのオーバーヘッドが大きいのは、一つのゴールで行なわれる実行が小さいからである。これを大きくすることができれば、オーバーヘッドを低減できる。これが粒度制御である。粒度制御には動的な粒度制御と静的な粒度調整が考えられる。動的粒度制御は、ゴールの実行をスタックを用いて行なう方法である。これは、ゴール一つを扱うオーバーヘッドで複数のゴールを実行することで、相対的にオーバーヘッドを少なくする方法である。静的粒度調整は、プログラムを静的に構成し直して、1つのリダクションで行なわれる仕事量を大きくする方法である。ゴールそのものを大きくすることで、やはり相対的にオーバーヘッドを少なくする方法である。後者は前者よりも完全にコストを削減することができるが、前者より適用できる範囲が狭い。

　上記の3つの実行手法の問題点は負荷の不均衡を引き起こす可能性があることである。負荷の不均衡は高負荷時には特に間題にならないが、低負荷時にはプロセッサ稼働率の低下につながる。プロセッサ稼働率の低下は、プログラムの実行時間に大きな影響を与えるため、絶対に避けなければならない。このため実行時の負荷に応じた最適化が必要となる。しかし、非定型的なプログラムにおいては実行時の負荷を予測することは非常に困難なため、コンパイル時の最適化のみで実行時負荷に応じた最適化をすることはできない。

　本研究では、高負荷時と低負荷時のそれぞれの実行状態に最適化した実行コードを用意し、これらを実行時に動的に切替えることで、小さい動的制御のオーバーヘッドで、実行時負荷に応じた最適化を実現した。

　並列度が不足している状態すなわち低負荷時のコードでは、並列度を向上させるため得られる並列度をすべて用いなければならない。したがって、負荷分散に関しては、なるべく多くの並列性を抽出するため、積極的に分散を行なう。このとき、静的負荷分割で負荷分散を抑制しメモリ参照の局所性を維持する。同時に静的スケジュールもおこなう。粒度の調整は並列度を低下させない程度に抑える必要があり、静的な粒度調整のみを行なう。

　十分な並列度がある状態すなわち高負荷時のコードでは、余分な並列度があるため並列度を抑制する最適化が可能になる。負荷分散は行なわない。これによって、メモリ参照の局所性が維持できるだけでなくゴールの転送のオーバヘッドも低減できる。粒度制御は、動的粒度制御と静的粒度制御を併用する。また、動的粒度制御でスタックを用いたFIFOスケジュールがされるため、このスケジューリングを前提にして静的にコードを並べかえることで、静的スケジューリングを実現する。

　静的負荷分割は、データとゴールを局所性のあるグループに分割する。この分割はまずプログラムの入出力モードを解析し、データ依存グラフを作成し、このグラフを分割することで実現した。静的負荷分割と動的負荷分割の効果と、負荷量との相関を調べてみよう。ここでは、使用IU台数を変化させることで相対的に負荷を変動させている。台数が少ない場合には高負荷に、多い場合には低負荷に相当する。図2に動的負荷分割、静的負荷分割の双方とも行なわない場合に対するそれぞれの場合の速度向上率を示す。

図表図1:UNIREDストール時間 / 図2:速度向上率

　UNIREDのストール時間はプロセッサ間の通信量を反映している。静的負荷分割で通信量が低減されているのがわかる。静的負荷分割のみを行なったケースでは、高負荷部分で実行速度が行なわないものよりも遅くなっている。これは、静的負荷分割によって不必要にプロセスの分配を試みているためであると考えられる。動的負荷分割を併用すると高負荷時には負荷分散そのものを行なわないコードが走るため、この問題は生じない。

　コンテクストスイッチのオーバヘッドの低減のための静的粒度調整はflengプログラム上でのプログラム変換の一種である、展開(unfolding)によって行なう。flengプログラムの展開は同期の移動をともなうため、元のプログラムに含まれていないデッドロックを誘発する可能性がある。本研究では、これを避けるため、プログラムのデノーテーショナル・セマンテイクスを定義し、展開してもセマンティクスが変化しない状態を定義した。このような安全な状態においてのみ展開を行なうことによって、デッドロックを誘発する危険のない粒度制御が可能になる。図3に、低負荷バージョンと高負荷バージョンのコードのそれぞれの実行比率を示す。下から、高負荷時、低負荷時、アイドル時の比率を示している。負荷が減るにつれアイドル時間が増え、それにともなって低負荷時の状態が増えていくのがわかる。

　図4に静的/動的粒度調整を行なった場合の速度向上を示す。図の左側は、プロセッサ台数が少ないので相対的に高負荷状態に、右側は低負荷状態になっている。一番下のグラフが、粒度調整を全く行なわない場合を示している。静的粒度制御のみを行なった場合のグラフが下から2番目のグラフである。負荷状態に関わらず、一定の効果をあげている。動的粒度制御のみを行なった場合のグラフが下から3番目のグラフである。低負荷状態では高い効果をあげているが、負荷が低くなると効果が減少する。1番上の両方を行なった場合のグラフにも同様の傾向がみられるが、静的粒度制御の効果によって、低負荷状態でも比較的高い性能を示している。

図表図3:負荷モードの比率 / 図4:静的/動的粒度調整の効果

　以上のように、本研究では高負荷時と低負荷時のそれぞれの実行状態に対して静的に最適化したコードを、実行時ルーチンによって動的に切替えること手法を提案した。また、この手法を用いたコンパイラ系、実行時系を開発しこの手法によって、すべての負荷状態において安定した性能を得ることができることを確認した。

　本論文は、「細粒度高並列言語flengの高性能な処理系構築に関する研究」と題し、9章からなる。細かい実行単位で並列処理を記述できる細粒度高並列言語は、問題に内在する多くの並列性を抽出可能であるため、非定型的な問題を高並列に実行するためのプログラミング言語として有望である。しかしながら、この種類の言語には、それ特有の間題があり、その解決なしにはその優れた性質を享受できない。本論文は、これらの問題を解決することを目的として処理系方式の提案と実装を行なったものである。

　第1章「序論」では、本研究の背景と目的について述べ、さらに本論文の構成をまとめている。

　第2章[Committed-Choice型言語とその実装」は、細粒度な並列処理を記述可能な言語として注目されているCommitted-Choice型言語のサーベイと、その一つであり、この論文で研究対象としているfleng言語のまとめを行ない、更にこれらに対する従来の処理系実装法を検討して、利用者への負担や動的最適化の不足等、その問題点を明らかにしている。

　第3章「PIE64とPIE64上の実行時処理系」は、言語flengのターゲットマシンであるPIE64の概要を説明するとともに、PIE64の実行時システムとその制御下で実行されるflengプログラムの動きを概説している。

　第4章「flengの実行と問題点」は、flengの実行モデルを詳細に分析し、それを高速に実行するための用件をまとめている。すなわち、flengでは、各並列処理要素をゴールと呼んでいるが、その実行時の変数参照を出来るだけローカルに保つこと、ゴールの実行可能性チェックのオーパヘッドを減らす為にゴールのスケジュールを効率的に行なう必要があること、ゴール一つ一つはかなり小さいので、それをまとめて逐次化し適当な長さの実行単位にする必要があること等である。次に、これらに対処するために、静的負荷分割による負荷分散の抑制、静的スケジューリング、及び粒度制御、等の各手法が考えられるが、コンパイル時の最適化だけでは不十分で、実行時の状況を加味した動的制御が必要であることを述べている。しかし、その動的制御を一般的に実装するのはオーパヘッドが大きいことから現実的でなく、flengプログラムの動作を詳しく検討することによって、負荷の低い時と高い時の二つの状態を考慮する簡単な粒度制御を提案している。

　第5章「flengコンパイラシステム」は、前章までの考察に基づいて作成したflengコンパイラシステムについて述べている。まず、この全体構造を与えてコンパイラが、静的解析器、プリプロセッサ、コンパイラ、及びアセンブラの4つからなることを述べ、次にそれらを詳しく述べている。静的解析器はモード解析、データ依存解析、意味解析からなり、プリプロセッサは、静的解析器の出力するデータと与えられた最適化の方針に従ってプログラム変換とアノーテーションの付加を行なう。すなわち、プリプロセッサは、高負荷時用に最適化されたものと、低負荷時用に最適化されたものの二つが用意されており、コンパイラは、それらのアノーテーションを解釈して適切な最適化を施した2種類のアセンプラコードを出力する。アセンプラでは、これら2種類のコードを合成して一つのコードを生成する。コンパイラ自身は二つのフェーズからなり、最初のフェーズではターゲットマシンに依らない中間コードを生成し、次のフェーズでマシン依存のアセンプラコードを生成する。

　第6章「粒度制御とプログラム変換」は、逐次実行される各ゴールを繋ぎ合わせて、実行オーバヘッドの小さな長い実行単位に変換する手法について述べたもので、プログラムの入出力依存関係が変化しないことを保証しつつプログラムを展開する手法によってそれを実現しており、その為の理論的な準備としてプログラムの意味定義を行ない、それが変化しない範囲を与えでいる。

　第7章「fleng処理系の評価」は、fleng処理系でコンパイルされた応用プログラムを実際のPIE64マシンの上で走らせ、その負荷分割と粒度制御の機能について評価したものである。負荷分割の評価では、動的負荷分割の効果は並列性の高いときに非常に有効であるが、並列性が低いときは効果がないこと、静的負荷分割は並列性の多少に依らず効果があるが、特に低負荷時に効果が顕著であり、これらは相補的な関係にあること、等を示している。また、粒度制御については、これを行なうことによって、速度が1.5〜2倍早くなること、この効果は並列度には依存しないこと、またこの理由が、細かいゴールを繋ぎ合わせることによってオーパヘッドが2/3程度に減少したことによることを明らかにしている。

　第8章「考察」は、本研究の手法と従来の手法との比較を行なうとともに、幾つかの技術ポイントを考察している。

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

　以上、これを要するに本論文は、細かい単位での高並列処理の記述が可能な言語flengに対して、効率良い処理系作成法を与えることによって実際に並列性が効率良く引き出せることを示したもので、情報工学上貢献する所少なくない。

　よって、著者は、東京大学大学院工学系研究科情報工学専攻における博士の学位論文審査に合格したものと認める。