並列分散環境におけるSPMD計算を対象にした,種々のオブジェクト指向クラス・ライブラリ・フレームワークが提案されている.これらのフレームワークは,実行環境に依存する処理をライブラリ内に隠蔽・実現することで,一様なアプリケーション・インターフェースを提供し,アプリケーション・プログラムの可搬性の向上を達成している.しかし,一方で,ライブラリ自身については,恣意的な方法で設計されていたり,または記述言語の改変を伴うものである等,その可搬性および拡張性は充分には達成されていない.本研究では,SPMD計算の代数的定式化を通して,可搬性と拡張性を備えたライブラリ・フーレムワークがクラス・カプセル化や継承機構等のオブジェクト指向計算の諸機能だけを用いて実現可能であることを実証する.

　まず,SPMD計算を「構造をもつデータ要素の集合に対する順序付けられた関数の適用」として規定し,更に,ライブラリ・フレームワークの機構を1)アルゴリズムからの並列性の抽出(アプリケーション・インターフェース部),2)プロセッサーへの分散(システム依存部),および3)両者の間の変換の3つに分解する.そして,1をデータ要素へのアクセス・パターン(順序付けられた要素集合上の横断)を定めるものとして捉え,これを横断子("traverser")と呼び,データ要素が定義される添字空間の上の関数として抽象化(クラス・カプセル化)する.更に,2を,データ要素の集合がもつ構造の再帰的階層化として捉え,これを階層的コレクション("hierarchical collection")と呼び,同様に添字空間上の変換として抽象化(クラス・カプセル化)する.これらの抽象化により,従来の研究では主として恣意的な実現が行なれていたフレームワーク中の3の部分を,1,2の分離(並列性と分散との分離)を図りつつ,添字空間を介して1,2の部分と統一的に実現することが可能になる.

　次に,横断子に対して,和と積の演算に関する代数系とその意味を与える.この代数系は,結合則,分配則等を満たすもので,これによりSPMD計算を代数的に定式化することが可能になる.例えば,ループ・ネストやループ変換を横断子の合成として代数演算により記述することが可能になる.更に,ある横断子と同じ計算結果を保証する横断子の全体がこれらの代数演算について閉じていることを示し,横断子の代数演算による宣言的な合成を可能にする.すなわち,並列性の抽出によって定められた横断子を,和・積演算による合成によって,分散に対応する階層的コレクションに適応した横断子に変換することが可能になる.

　この様な定式化の直接的な意義としては,まず第一にプログラムの宣言的記述による可読性の向上が挙げられる.更により本質的には,複数の異なる並列計算環境へのプログクムの移植に際して必要になる変更を横断子の(代数演算を用いた)再定義のみに限定できることから,保守の利便性の向上や,個別の計算環境に合わせたプログラムの最適化のコストの低減がはかられるというソフトウエア工学上の意義も認められる.また,並列性と分散との間の変換をアプリケーション・プログラムの中で記述する仕組により,ライブラリ設計の中の恣意性を除去し,高い可搬性と拡張性を備えたライブラリの実現が可能になる.実際,ライブラリの拡張は,横断子および階層的コレクションの,継承機構を用いた特殊化によって達成され,その結果はアプリケーション・プログラムにおいて直ちに利用可能になる.最後に,本定式化に基づく並列オブジェクト指向ライブラリを実際に構築し,実験を通じてその有効性を確認する.

　本論文は、9章からなり、第一章では研究の背景と概説、第二章は関連研究の整理、第3章と第4章は基礎概念としてのデータの分散とデータのトラバース、第5章は対象の代数的定式化、第6章は計算機上での実現、第7章は具体的な問題への応用を述べている。8章、9章は、それぞれ、結果についての議論と結論となっている。以下に、各章の概要を述べる。

　第1章は、並列分散環境におけるSPMD計算を対象にすでに提案されている種々のオブジェクト指向クラス・ライブラリ・フレームワークについて概観し、それらが恣意的な方法で設計されていたり,または記述言語の改変を伴うものである等,その可搬性および拡張性は充分には達成されていいるとはいえないことを指摘している。これに対して、本研究が、SPMD計算の代数的定式化を通して,可搬性と拡張性を備えたライブラリ・フーレムワークがクラス・カプセル化や継承機構等のオブジェクト指向計算の諸機能だけを用いて実現可能であることを実証していること、また、実際に実験的なクラス・ライブラリを構築し,いくつかの数値計算と二分木探索からなる性能評価を行なったことを述べている.

　第2章は、研究の背景と問題を詳述し,関連研究を比較分析した上で,本論文における議論の目標を設定し,以降の章の構成を示している。結論として、プログラム変換システムおよびタスク並列言語との比較から,オブジェクト指向クラス・ライブラリとしてのSPMD計算の記述系の利点を確認し,(1)-(3)を扱うための適切なSPMD計算の定式化を通したクラス・ライブラリの構築の仕組によってmaintainabilityが達成可能であることを主張している。

　第3章では、データの分散と並列性の抽出の分離の仕組の実現に焦点をあて、論文の基礎概念であるデータの分散について議論している。データの分散は,一般に,データ要素の集合がもつ構造の再帰的階層化として捉えられ,この階層的コレクションは"is-a"関係によって共通の性質を継承し,同時にコレクション階層間には"part-of"関係が定められる.これにより,単一の抽象的な構造を保存しながら,分散の詳細を階層として隠蔽する仕組が自然に実現可能になることを提案している。

　そして,元のコレクションに対する順序付けられた関数の適用は,この階層的コレクションに対する関数の再帰的な適用として再定義でき,その際の計算の等価性は,階層化による元の順序の保存性によって十分に保証できることを主張している.

　第4章では,論文の中心課題であるデータ分散,並列性の抽出,および並列性の分散への適応を統一的に記述するための代数的な定式化を詳述している.ここでは、まず,関数の適用順序を,データ要素へのアクセス・パターン(順序付けられた要素集合上の横断)を定めるものとして捉え,これを横断子(トラバーサ)と呼び,データ要素が定義される添字空間の上の変換として抽象化する.そして,横断子および前章で述べた階層的コレクションが,ともにデータの分布する添字空間の分解として統一的に記述可能であることを示している.この抽象化により,従来の研究では主として恣意的な実現が行なれていたフレームワーク中の「並列性の分散への適応」の部分を,「並列性と分散との分離」を図りつつ,添字空間を介して統一的に実現することが可能になるとする。次に,横断子に対して,和と積の演算に関する代数系とその意味を与え、この代数系が,結合則,分配則等を満たすもので,これによりSPMD計算を代数的に定式化することが可能になること、更に,ある横断子と同じ計算結果を保証する横断子の全体がこれらの代数演算について閉じていることを示すことで,横断子の代数演算による宣言的な合成が可能になることを示している。

　第5章では,これまでの議論にフォーマリズムを導入することを議論し、前章の結果をデータが分布する添字空間上で定義される変換として捉え直すことにより、この添字空間を生成元によって張られる自由生成系として抽象化することで議論の一般性が保たれること、また、同時に空間の分解を与える変換の性質が,和と積による代数系として形式化できることを示している.

　第6章では,本論文で提案するクラス・ライブラリが,既存のオブジェクト指向言語Eif-felを基にした「EPEEフレームワーク」の拡張として実現され,階層的コレクションおよび横断子に対応する抽象クラスが,各々EPEEにおけるコンテナ(container)およびプロバイダ(element provider)のサブクラスとして導入・実装される.また,並列分散環境における実行のための通信パッケージPOMを統合することで,ワークステーション・クラスタおよび超並列計算機等の種々の計算環境上での実行が可能になることを示している。

　第7章では,(1)行列積,(2)緩和法による偏微分方程式の求解,(3)行列の固有ベクトル,(4)RNA二次構造探索,の4つを具体的な例としてとりあげ,各々,ライブラリ・クラスおよびアプリケーション・プログラムの記述の簡便性を確認し,並列計算機上での実験を通して効率の低下が僅少であることを実験により検証している。実際,ほとんどのオーバーヘッドが静的解析を通して除去可能であることが示されている.

　第8章では,実現したクラス・ライブラリと,2章で概観・検討した既存の研究との比較を行ない,efficiencyとmaintainabilityの観点から得失を論じている。また,本論文での定式化が適用できない問題についても列挙し,適用可能領域の外延を明確にしている。

　第9章は結論とし、研究の新奇性および寄与について再述し,今後の課題と展望について総括している。具体的には、本研究における定式化に基づくクラス・ライブラリ・フレームワークが,ライブラリ設計者と利用者の双方に対して,"maintainability"の向上を齎す仕組を提供していること、また、定式化の意義としては,プログラムの宣言的記述による可読性の向上が得られることを述べ、より本質なこととして、複数の異なる並列計算環境へのプログラムの移植に際して必要になる変更を横断子の(代数演算を用いた)再定義のみに限定できることから,保守の利便性の向上や,個別の計算環境に合わせたプログラムの最適化のコストの低減がはかられるという意義を強調している.また,並列性と分散との間の変換をアプリケーション・プログラムの中で記述する仕組により,ライブラリ設計の中の恣意性を除去し,高い可搬性と拡張性を備えたライブラリの実現が可能になること、更に,「空間の分解/空間の横断」という抽象化は,並列計算の大局的な挙動を捉えるための仕組として大きな可能性を備えていると考えられ,SPMD型の並列計算以外についても適用を試みられるべきであるとしている。

　なお、6章は、Jean-Marc Jezequel博士、本学米澤教授との共同研究によって開発されたEPEEを拡張してものであるが、拡張の定式化は、論文提出者によるものであり、論文提出者の寄与が十分であると判断する。

　よって、博士(理学)の学位を授与できると認める。