近年，情報化社会を反映して，アプリケーションソフトウエアはより多機能なものが開発され，より高速・高性能なアーキテクチャが求められている．そうした要求を満たす高速化技術の一つとして並列計算機に注目が集まっており,既に実用化の段階に入ってきている.その関連研究の一つとして,並列プログラミング言語がある.

　並列プログラミング言語は設計方針から二種類に分類される.一つは従来の逐次処理向けに設計された言語を基盤とし,並列計算機用に仕様の拡張と並列化を行なった言語であり,もう一つは最初から並列計算機での動作を考慮して,最初から設計,開発された言語である.

　現在,従来の言語との互換性などの点から前者が主流である.しかし,将来的にさらなる高並列計算機への要求が高まることは十分に考えられることであり,前者は元来逐次処理向けの言語であったために並列計算機向けに仕様拡張しても十分な並列度を抽出することが難しい.このことから後者の言語に対する研究の必要性は極めて高い.

　我々の研究室では,こうした必要性を考慮し,並列計算機に関するソフトウェアとハードウェア技術の研究を行なっている.その中で,ソフトウェア技術としては並列論理型言語Flengを開発し,実装,最適化に関する様々な研究が行なわれてきた.

　しかし,これらの多くの研究成果はFlengを高速実行する専用計算機であるPIE64上での評価が中心であった.前述のように,汎用的な並列分散農境が実用段階にある今日では,専用計算機ではなく,汎用型の共有メモリ型並列計算機上での評価がより現実的な研究として重要である.

　また,次のプロセッサとして注目されているCMPはハードウェアを一つのチップ上に集約化し,チップ間の遅延を削減することで高速化を実現するものであり,プロセッサクロック比で考えると,より細粒度な実行単位が要求されている．実際に,関連研究として,スレッド単位の実行といった細粒度実行の研究が活発であり,近い将来に細粒度実行が要求される時期が来る可能性が高い．このことから,細粒度実行の特長を明確化することが極めて重要である

　そこで,本研究では共有メモリ並列計算機上のFleng処理系を用い,その最適化と,その実行動作に関する定量的評価を行なうことにより細粒度な言語の特長について検討を行なった.

　まず,処理系の中でのコンパイラの最適化に着目をした.従来のコンパイラではゴール融合等の粒度最適化手法が実装されている.しかし,こうした最適化技術を複合的に適用することにより,従来は存在しなかった新たなオーバーヘッドが存在することを明確化した.さらに,オーバーヘッドの削減手法としてCommon Subexpression等の最適化手法の適用,評価を行なった.その結果,数十％のコード量削減と約十％の速度向上を実現した.

　次に,処理系の中でのランタイムシステムの高速化に着目した.従来のランタイムでは,ローカル優先のスケジューリング機構を用いているために並列動作による十分な速度向上が得られない問題点があった.そこで,プロセッサの稼働状態に応じたスケジューリング機構を提案した.また,提案手法ではプロセッサ間の排他制御によるオーバーヘッドが大きくなるため,従来の排他制御機構の改善を行なった.この結果,粒度の小さなプログラムでも並列動作による速度向上を達成するとともに,従来に比べ数十％の速度向上を実現した.

　また,こうした最適化においてはその最適化の方向をまとめることが不可欠である.しかし,こうした大規模なソフトウェアが並列実行される場合,オーバーヘッドは複合的な要因が多く,定量的評価は困難である.そこで,ランタイムとFlengプログラムの挙動を細分化するとともに,プロセッサの命令やキャッシュ等の細部に渡り,ランタイムの定量的評価を行なった.この評価から論理型言語Flengにおける利害得失について定量的評価をまとめ,細粒度実行の特長に関して検討を行なった.

　このように,本研究では共有メモリ型並列計算機上のFleng処理系に対し,最適化技術の提案,実装,評価と,ランタイムシステムの定量的評価を行なった．これにより従来に比べて,約2倍の速度向上を達成するとともに,汎用的な共有メモリ型並列計算機における並列論理型言語Flengの利害得失を定量的に評価し,細粒度実行の特長を明確化した.

本論文は、「共有メモリ型並列計算機における並列論理型言語Flengの処理系に関する研究」と題し、8章と付録からなる。情報化社会の発展は、計算機システムの限りない高速化を要求する。それを満たす重要な技術の一つはデバイス技術であり、もう一つは並列処理技術である。並列処理には、優れた並列プログラミング言語が重要であるが、その一つに並列論理型言語がある。本研究は、そのような言語の内、研究室で開発してきたFlengを対象として、共有メモリ型並列計算機向けの並列論理型言語処理系を開発し、その最適化技術とランタイムシステム技術を検討して、その処理系の評価を行い、特徴的な細粒度実行の特性について論じたものである。

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

第2章「Committed-Choice型言語Fleng」は、本研究の対象となるCommitted-Choice型言語Flengの言語仕様について述べたものである。

第3章「共有メモリ型並列計算機上のFleng処理系」は、研究室で従来までに開発されてきたFleng処理系の構成と実装についてまとめたものである。ソースプログラムは、記述性を高めるためにマクロ定義が可能となっているが、処理系は、まずそのマクロを展開し、次に実行効率向上のために、ゴール融合と強制インライン展開からなる粒度制御をソースレベルで行う。その出力をコンパイラでC言語に変換し、対象マシンの機械語に変換の後、マシンごとのランタイムシステムを用いて実行される。ランタイムシステムは、スケジュールを行うが、そのために仕事の単位であるゴールを蓄える二つのゴールスタックLGS、GGSを用いている。LGSは各スレッド毎に設けられたゴールスタックで、GGSは、全スレッドによって共有されるゴールスタックである。

第4章「ランタイムシステムの最適化」は、3章で述べたランタイムシステムを最適化する手法とその評価について述べたものである。まず、従来のランタイムシステムの問題点を明らかにするために測定をおこない、プログラムの並列度が低い場合は、GGSの排他制御のためのオーバヘッドがかなり大きく、それが実行速度を落としていること、並列度が高くなるとそれが隠れて並列処理が有効に機能することを明らかにしている。次にそれを改良するために負荷分散方式を工夫し、排他制御を行わないフラッグをLGSに設けたり、従来のpthreadを用いた排他制御の代りにビジーウエイトを用いたり、排他制御機構を細かく5つに分類しそれぞれの寄与を測定から調べることによって問題点を細かく分析し、それに基づいて新たなスケジューリング手法を提案している。それは、ビジーウエイト用に新たな排他制御変数を導入し、LGS、GGSの利用を細かく制御するものであって、その手法による実行時間の測定から、それが非常に効率の良い手法であって、システムタイムの大幅な削減と、台数効果による大きな速度向上を達成している。

第5章「コンパイラの最適化」は、処理系の内、マクロ展開、粒度制御、コンパイラのすべてに対して行った最適化手法について述べたものである。まず、従来の処理系の問題点を分析し、粒度制御の強制インライン展開処理は、定数伝播、共通部分式の削除、部分冗長性の除去などの手法が適用可能な文を多く生成するので、これらの最適化が必要であること、次にFlengコンパイラにより生成されたCプログラムを調べた結果、付けたタグをすぐまた外すような無用命令が発生すること、真偽値を用いた分岐判定に冗長性が発生することなどを明らかにしている。次に、ベンチマークプログラムを用いて、これらの最適化を施した場合の効果を調べ、Flengレベルの最適化によって、コードが20-30％減少し、Cプログラムレベルでの最適化によって、更に10％程度の削減が可能なこと、実行速度に関しても・ほぼ10％程度の速度向上が得られたことを示している。

第6章「共有メモリ型並列計算機上のFleng処理系の定量的評価」は、様々な要因が複雑にからみあう処理系に対する評価を検討したものである。Fleng言語とC言語の比較では、Flengプログラムに頻出する算術演算、分岐演算、リスト処理の3つに分けて考察した結果、実行命令は数倍から十数倍の差があり、実行サイクル数ではより大きな差異があること、その理由は・変数の単一化やタグの着脱処理により、ロード、ストア命令がCの数倍発行されるため、キャッシュ上データのミス率が増大すること、ライトアフタライトハザードのため、キャッシ遅延が生じるためであることを明らかにしている。次に、ランタイムの主要処理要素について、各処理のキャッシュ効率と並列実行の検討を行い、データキャッシュのミス率は、スレッド数が増えると減少すること、更に、性能とスレッド数、キャッシュミス、LGS/GGS内ゴール数との間の関係を詳細に分析している。

第7章は「考察」で、関連研究との比較を行うとともに、今後の課題をまとめている。

第8章は「結論」である。

以上、これを要するに本論文は、並列論理型プログラミング言語Flengの処理系について、コンパイラとランタイムシステムの最適化と、C言語で同じプログラムを作成した場合に比べての特徴、更にランタイムシステムの並列特性評価について考察したもので、論理型言語の細粒度並列処理の詳細な性質を明らかにしており、電子情報工学上貢献するところ少なくない。

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