近年、計算機に処理させたい問題の巨大化や、安価な並列計算機環境の普及に伴い、それら並列計算機を有効に活用するための並列プログラミングがプログラマにとって必須の仕事となってきている。しかしながら、並列プログラミングでは、これまでの逐次プログラミングには必要の無かった、計算対象のデータの複数計算機間での分散や、計算の仕事の分散と同期とを考慮する必要がある。そのため、並列プログラミングには、大きく以下の二点の難しい問題がある。ひとつは、問題を並列計算機で効率的に処理することが可能な並列アルゴリズムの開発が難しい。そして、もうひとつは、そのアルゴリズムを並列プログラムとして実装することが難しい。

これらの問題を解決するための枠組みのひとつとして、構造化並列プログラミング(スケルトン並列プログラミングとしても知られている)が提唱されている。この枠組みでは、スケルトンと呼ばれる並列計算の基本パタンを組み合わせる事で、プログラマは並列プログラミングを行うことができる。言い換えれば、並列プログラムをスケルトンで構造化することで、アルゴリズムの開発や実装の難しさの解決を図っている。並列処理の為に考慮すべき難しい並列性がスケルトンにより隠蔽されるため、この枠組みによる並列アルゴリズムの作成は、スケルトンの逐次的な組み合わせでアルゴリズムを設計する事にあたる。また、アルゴリズムの実装は、各スケルトンの並列実装を設計した組み合わせどおりに呼び出すだけとなり、容易である。

しかしながら、効率の良いアルゴリズムを系統的に作成できるような構造化並列プログラミングの枠組みを構築する事は、未だ大きな課題として残されている。スケルトンの組み合わせによるアルゴリズムの記述は容易であるが、一方で、愚直に組まれたアルゴリズムは組み合わせに含まれる無駄による非効率性の問題を持つ。例えば、連続するスケルトン間でやりとりされる中間データ構造がしばしば無駄である。そのため、組み合わせの無駄を省いて効率の良いアルゴリズムを合成できる枠組みが必要とされている。

本論文では、スケルトンの組み合わせの融合変換による最適化に注目して、効率の良いアルゴリズムを系統的に作成できるような構造化並列プログラミングの枠組みを提案する。我々の枠組みでは、融合の為の良い性質を持つ、凖同形と呼ばれる特定の形の計算パタンでスケルトンを構造化する。このスケルトンの構造化により、我々の枠組みでは、愚直なスケルトンの組み合わせで記述された並列アルゴリズムから、融合変換によって効率の良い並列アルゴリズムを得ることができる。本論文の主な貢献は以下のとおりである。

(a) 凖同型に基づく融合変換に適した並列スケルトンの設計。

(b) 設計されたスケルトンに関する融合規則による最適化の理論。

(c) 設計されたスケルトン及び最適化の実装による理論の効果の検証。

特に、二次元配列を操作対象とするスケルトンの設計、それらを用いたプログラミング、及び、それらの最適化は、大きな課題とされていた問題である。本論文の成果により、二次元配列を操作対象とした構造化並列プログラミングの議論が可能になった。また、他のデータ構造(一次元配列)に関しても、いつかの融合変換に基づく最適化を定理の形で与え、より幅広い問題を最適化可能になった。さらに、愚直なプログラム記述から効率的なアルゴリズムを得るための自動最適化の仕組みを提案し、実際のプログラミング言語上に高レベルな最適化を実装したライブラリを構築した。この仕組みを用いることにより、プログラマは最適化理論の成果を容易に利用可能となる。

本論文の構成は以下の通りである。

第一章では、本論文の背景、目的、貢献を要約し、本論文の構成を述べる。

第二章では、スケルトン設計の元となる、操作対象のデータ構造を表現する代数系とその準同形が導入される。データ構造を代数系として捉え、その上の準同形を計算の基本パタンとすることで、単純な計算の組合せによる複雑な計算の記述が容易になる。また、それらの代数系に並列性の為の自由度を持たせることにより、凖同形が並列スケルトンの基礎として利用できる。本章は、特に二次元配列に重点を置きつつ、一次元配列と木に関する代数系と準同形を導入する。

第三章では、前章で導入した準同形を基に、並列スケルトンが定義される。凖同形の性質を受け継ぐスケルトンは、自身は単純な計算パタンであるが、それらの組み合わせにより様々な計算を表現可能である。本章では、スケルトンで記述された様々な並列プログラムを通し、スケルトンの組み合わせによる記述力も示される。また、幾つかの行列の基本演算が定義されたスケルトンで記述可能であることが示される。

第四章では、本論文の提案するスケルトンの特徴である、融合変換による最適化の理論が構築される。まず、準同形の融合変換が導入され、それを基礎としてスケルトンの融合変換が構築される。また、それらの融合変換を用いて、愚直なスケルトンの組合せで記述されたアルゴリズムから、効率的なアルゴリズムを得ることができることが、具体的な問題例に関して示される。

第五章では、特定の問題クラスに特化した融合変換規則の構築や、効率的なアルゴリズムを与える最適化定理を構築する。これらは、準同形の融合変換の一般性から生じる変換の難しさを解決し、スケルトンプログラムの自動的な最適化を可能とする基盤を与える。本章で対象とする問題クラスは、入力の興味のある部分構造を生成し、それら部分構造の集まりを処理して結果を得るような計算問題である。例えば、二次元配列を入力とし、その中の矩形領域を考え、それらから最大の和を与えるものを探し出す、という問題(最大部分矩形和問題)が対象に含まれる。

第六章では、前章までに構築した理論を実際に実装し、本論文の提案する構造化並列プログラミングの枠組みで並列プログラムが現実に動かせることが示される。本章ではふたつのスケルトンの実装が示される。ひとつはC++上の関数としてスケルトンの実装を提供するライブラリである。もうひとつは新しいプログラミング言語Fortress上のライブラリである。後者の実装では、スケルトンの理論を基礎にしたより使いやすい表記法との融合や、スケルトンの組合せにマッピングされた並列プログラムの自動的な最適化の手法が示される。この実装により、ライブラリが並列アルゴリズムの動的な辞典として機能する。

第七章では、本論文の内容がまとめられ、さらに、今後の展望についての提案がなされる。

近年、計算機で処理する問題が巨大化し、また並列計算機環境の普及に伴い、並列プログラミングが科学技術計算にとって必須のものとなってきている。しかしながら、並列プログラミングでは、これまでの逐次プログラミングには必要なかったデータの配置や計算の分散・同期を考慮しなくてはならず、そのために、並列プログラミングには以下のような課題があるとされる。ひとつは、問題を並列計算機で効率的に処理するためのアルゴリズムの開発であり、もうひとつは、そのアルゴリズムを並列プログラムとして実装する方法である。これらの問題を解決するための枠組みのひとつとして、構造化並列プログラミング(スケルトン並列プログラミング)が提唱されている。この枠組みでは、スケルトンと呼ばれる並列計算の基本パタンを組み合わせて並列プログラムを構成する。そこでは、並列処理のために考慮すべき並列性をスケルトンによって隠蔽して、アルゴリズムの開発や実装の難しさの解決を図ろうとしている。しかしながら、スケルトンの組合せによるアルゴリズムの記述は比較的容易ではあるが、一方で、そのままのアルゴリズムは非効率であるということが問題となっている。本論文は、この課題の解決に向けた手法を論じたものである。

本論文は、Homomorphism-based Structured Parallel Programming(準同形に基づいた構造化並列プログラミングに関する研究)と題し、英文で書かれ7章からなる。本論文では上述のような課題に対して、スケルトンの組合せの融合変換による最適化に注目し、効率のよいアルゴリズムを系統的に作成できるような構造化並列プログラミングの枠組みを提案している。

第1章 Introductionでは、本論文の背景、目的、貢献、構成を述べている。並列アルゴリズムの開発と、そのアルゴリズムを並列プログラムとして実装する課題を解決する枠組みのひとつとして提唱されている構造化並列プログラミングを紹介し、そこに残されている課題を明示している。また、本章では、最大部分矩形和問題を例に、本論文の提案する準同形に基づいた構造化並列プログラミングの特徴を述べ、本論文で提案する手法を概観している。

第2章 Algebras and Homomorphisms for Data Structures では、操作対象のデータ構造を表現する代数系と準同形を導入し、その準同形を計算の基本パタン(スケルトン)とすることにより、単純な計算の組合せによって複雑な計算を記述する方法を述べている。また、それらの代数系に、並列性に内在する自由度を持たせることにより、準同形が並列スケルトンとして利用できることにも言及している。さらに、1次元配列(リスト)、2次元配列(行列)、および木に関する代数系と準同形を導入し、準同形の組合せによりさまざまな計算を記述できることを例示している。

第3章 Homomorphism-based Design of Parallel Skeletons では、前章で導入した準同形をもとに、並列計算の基本パタンとなる並列スケルトンを定義している。準同形の性質を受け継ぐスケルトンは、それ自体は単純な計算パタンであるが、それらの組合せによりさまざまな計算を表現できる。こうして、目的とする計算を並列スケルトンで記述すれば、愚直な並列プログラミングを終えたことになる。本章では、1次元配列、2次元配列、および木に関していくつかの並列スケルトンを導入している。また、さまざまな計算のスケルトンによる記述例を通して、スケルトンの組合せの記述力を示している。とくに、2次元配列上の並列スケルトンの設計と、そのスケルトンによるさまざまな並列計算の記述法を新たな貢献として主張している。

第4章 Fusion Optimizations of Parallel Skeletons では、本論文の提案するスケルトンの特徴である融合変換による最適化の基本理論を構築している。この融合変換による最適化により、愚直なアルゴリズムから効率的なアルゴリズムを得ることができると述べている。とくに、拡張された準同形の融合変換を用いることによって効率のよい並列アルゴリズムを系統的に導き出し、2次元配列上の準同形やスケルトンに関する融合最適化の構築と、それを用いた効率的な並列アルゴリズムの導出が本論文の貢献であるとしている。

第5章 Domain-specific Optimization for Skeleton Programs では、特定の問題クラスに特化した融合変換規則の構築と効率的なアルゴリズムを与える最適化定理の構築を示している。とくに、入力に関して興味のある部分構造の集まりを生成して、それらのうちから条件を満たすものを選ぶという生成子に基づく(generator-based)解法を対象とし、部分構造の生成の仕方に基づく問題の整理と最適化理論を構築している。具体的には、2次元配列上の各種の最適化定理と、条件による選別付きの1次元配列上の計算に関する最適化理論の構築とを新たな成果として示している。

第6章 Implementation of Skeletons and Optimizations では、前章までに構築した理論を実装し、本論文の提案する構造化並列プログラミングの枠組みでプログラムを効率よく動かすことを実験によって示している。ここでは、2種類のスケルトンの実装と、それらを用いた実験結果をあげている。ひとつはC++上の関数としてスケルトンの実装を提供するライブラリであり、もうひとつは新しいプログラミング言語Fortressの上にスケルトンの枠組みを実装したライブラリである。とくに2次元配列上の各種スケルトンの実装と部分構造の生成の仕方に基づく自動最適化の実装が実用的な成果であるとしている。

第7章 Conclusion では、本論文の内容をまとめるとともに今後の展望を述べている。

本論文の主な貢献は、準同形に基づく融合変換に適した並列スケルトンの設計、スケルトンに関する融合規則による最適化の理論、およびスケルトンと最適化の実装による理論の効果の検証の3点に集約される。とくに、2次元配列を操作対象とするスケルトンの設計とそれらを用いたプログラミング、およびそのようにして開発されたプログラムの最適化は、これまでには解決されていなかった課題への有効な方法を与えたものである。さらに、本論文では、他のデータ構造に関する融合変換に基づく最適化を定理の形で与えて、より幅広い問題の最適化を可能にしている。また、これらの理論的な成果をもとに、愚直なプログラムから効率的なプログラムを得るための自動最適化の仕組みを提案して、これを実装したライブラリを構築して有効性を実証している。

以上を要するに、本論文は構造化並列プログラミングに関して新たな方法論を理論的に展開するとともに、実用的なライブラリの構築によってその有効性を実証したもので、数理情報学、計算機科学の発展に寄与するところが大きい。よって本論文は博士(情報理工学)の学位請求論文として合格と認められる。