計算機の能力の向上に従って,我々が扱うべきデータは非常に巨大になっており,また増加し続けている。そのような巨大なデータを効率良く処理するために並列計算はその重要性を増している。近年,高速なネットワークによって接続されたPCクラスタやマルチコア・マルチCPUのように並列計算を行うためのハードウェアは比較的簡単に手に入れることができるようになってきている。一方で,効率良く並列計算を行うための並列プログラムを作成することはそれほど簡単でない。並列プログラミングにおいては,データの分散,プロセッサ間の通信・同期,処理のスケジューリングなど,逐次プログラムにはない事項を考えなければならないからである。

並列プログラミングに関して,これまで多数のプログラミングモデルが提案されてきた。Coleによって提案されたスケルトン並列プログラミング (Skeletal Parallelism) はそのようなモデルのひとつである。スケルトン並列プログラミングでは,並列スケルトンと呼ばれる並列計算に頻出する抽象的な計算パターンを組み合わせることで並列プログラムを作成する。データの分配やプロセッサ間通信などの並列性が並列スケルトンの中に隠蔽されることにより,ユーザは比較的簡単に並列プログラムを作成することができる。これまでに,リスト (配列) に対して多くの研究があり,様々な優れた結果が得られている。

本論文は,木構造の処理を抽象化した並列スケルトン (並列木スケルトン) を用いた並列プログラミングについて,その理論と実現に関する研究をまとめたものである。

木は構造を持ったデータを表現するのに良く利用される重要なデータ構造である。しかし一方で,木は不規則・不均等な構造を持つため,木上のデータを効率良く並列に処理することは困難であった。例えば,木を処理する多くの逐次アルゴリズムは分割統治法によって記述されるが,そのアルゴリズムをそのまま分割統治法による並列アルゴリズムにしただけでは入力の木が不均等な場合に性能が悪くなる。この問題を解決した,任意の形状の木に対して効率が保証できるtree contractionアルゴリズムと呼ばれる並列アルゴリズムがある。しかし,この並列アルゴリズムでは計算の順序が特殊であるため,もとの逐次プログラムを相当に変更しなければならないことが少なくない。また,この並列アルゴリズムを分散メモリ並列計算機上で効率良く実現することは簡単ではない。 これらの理由から,計算を抽象化した並列スケルトンによるスケルトン並列プログラミングは木に対する並列処理を簡易にするための魅力的なプログラミングモデルである。

本論文の貢献は,並列木スケルトンによるプログラミングの理論と実現の両面からなる。理論に関する研究では,構成的アルゴリズム論 (Constructive Algorithmics) に基づく並列木スケルトンの設計,および,それらの並列木スケルトンを用いた系統的なプログラミング手法を提案した。 実現に関する研究では,分散メモリ並列計算機においても効率の良い並列木スケルトンの実装を含む並列スケルトンライブラリ「助っ人」の実装,および,ふたつのクラスの自明でない実用的な問題に対するスケルトン並列プログラミングの適用を行った。以下に本論文における重要な4つの貢献をまとめる。

第一の貢献は,構成的アルゴリズム論に基づく並列木スケルトンの設計である。 構成的アルゴリズム論はデータの構成とその上のアルゴリズムの関係に着目した理論であり,逐次プログラムの設計・導出に関して多くの成果がある。並列木スケルトンはSkillicornによって最初に定式化されたが,本論文において二分木と一般の形状の木のそれぞれに対して並列木スケルトンを再設計した。 これらの並列木スケルトンは,再帰関数による逐次的なインターフェイスと様々な並列計算機環境における効率良い実現というふたつの側面を持つ。 一般には,任意の計算が並列に計算できるわけではないため,いくつかの並列木スケルトンは補助関数を要求する。 この補助関数を用いた定式化は本研究の新規性のひとつであり,これらの補助関数はプログラム導出や効率の良い並列実装において重要な役割を果たす。

第二の貢献は,系統的なスケルトン並列プログラミング手法の提案である。並列木スケルトンを利用することで多くの並列プログラムを作成することができるが,ユーザの視点に立つと,それらをどのように組み合わせるか,また,要求される補助関数をどうやって見つけるかを誘導することが必要である。まず,並列木スケルトンの組み合わせ方を導出するために分離定理 (Diffusion定理) を示した。この定理によって,逐次の再帰アルゴリズムがどのような並列スケルトンの組み合わせに分解できるかが示される。また,並列木スケルトンに要求される補助関数を導出するために計算の代数的な性質に着目した。本論文で示す3種類の代数的性質のいずれかが成り立つ場合には,系統的もしくは自動的に必要な補助関数を導出することができる。

第三の貢献は,並列スケルトンライブラリ「助っ人」の実現である。並列スケルトンライブラリ「助っ人」は汎用的なC++言語とMPIライブラリを用いて実装されており,分散メモリ環境の上でも効率の良く動作する並列スケルトンを提供する。特に,リストや行列を扱う並列スケルトンだけでなく,木を扱う並列木スケルトンが実装されていることは,他の並列スケルトンライブラリにはない「助っ人」の重要な特徴である。 「助っ人」のもうひとつの重要な特徴は,融合変換による最適化機構を持つことである。融合変換による最適化機構を利用することで,多数の並列スケルトンによるオーバーヘッドを取り除くことが可能である。並列木スケルトンの実装や最適化機構の効果について,実際のPCクラスタの上で実験を行い検証した。

第四の貢献は,自明でない実用的な問題に対するスケルトン並列プログラミングの適用である。本論文では,最大マーク付け問題 (最大重み和問題) とXPathクエリ処理とのふたつのクラスの問題が,スケルトン並列プログラミングによってそれぞれ統一的に並列化することができることを示した。最大マーク付け問題には動的計画法で解ける最適化問題が含まれており,リストや行列に対しては多数の研究がある。木における最大マーク付け問題の一般的な並列化を示したのは,本論文が初めてである。 これらの並列プログラムの導出においては,第二の貢献である系統的なスケルトン並列プログラミング手法が重要な役割を果たしている。

以上が本論文の要旨である。

並列計算は大量のデータを効率良く処理するための重要な計算手法であり、そのための並列プログラムの開発手法が求められている。また、木構造は多くの実用的な計算に現れる重要なデータ構造であるが、その不規則・不均等な構造のために効率の良い並列プログラムを作成することは難しいとされていおり、このようなデータを対象とした並列プログラミングの方法論の確立が期待されている。これまでにも、木構造を扱う効率の良い並列アルゴリズムの提案があるものの、実用的問題に対してそれを適用・実装することは非常に難しく、プログラムの開発も個別的になってしまっているのが現状である。このようなことから、規模の大きい木構造データを扱う並列プログラムを開発するにあたっては、明解なプログラムの仕様から効率の良い並列プログラムを得るための系統的なプログラミング手法、および、得られた並列プログラムを実行するためのライブラリの実現が望まれる。

本論文は、「Parallel Programming with Tree Skeletons (邦訳: 並列木スケルトンによる並列プログラミングの理論と実現に関する研究)」と題し、英文で書かれ、木構造の処理を対象とした並列スケルトン(並列木スケルトン) を用いた並列プログラミングの理論と実現に関して論じたものである。本論文の主な貢献は下記の4点である。

(a) 構成的アルゴリズム論に基づいた並列木スケルトンの設計。

(b) 系統的なスケルトン並列プログラミング手法の提案。

(c) C++とMPIによる並列スケルトンライブラリ「SkeTo」の実現。

(d) 木に対するスケルトン並列プログラミングの自明でない問題への適用。

本論文は下記に示す11章からなり、理論に関する貢献 (a),(b) は第2章から第5章に、実現に関する貢献 (c),(d) は第6章から第9章に示されている。

第1章 (Introduction) では、 本論文の背景、目的、貢献を要約するとともに、論文の構成を示している。

第2章 (Basis of Parallel Tree Computing on Binary Trees) では、まず二分木の上で定義される計算パターンである木上の準同型とtree contractionアルゴリズムを導入した後で、重要な基礎である二分木に対する並列木スケルトンの定義を示している。

第3章 (Tree Associativity and Ternary-Tree Representation) では、二分木上での並列計算およびその条件について、二分木の再帰的な分割を表現した三分木表現とその上で成立すべきある種の結合性 (tree associativity)を定式化している。 特に、ここで定義される結合性は、効率良く並列に計算できるために演算が持つべき必要十分な性質であることを主張している。

第4章 (Rose-Tree Skeletons) では、木の内部ノードが任意数の部分木を持つ一般の木構造 (rose tree; 薔薇木) に対する並列木スケルトンを扱っている。薔薇木に対する並列木スケルトンは、二分木に対するものの自然な拡張として定義されており、また、それらの効率良い並列実装は二分木に対する並列木スケルトンの実装を用いて実現できることを示している。

第5章 (Theorems for Deriving Skeletal Parallel Programs) では、明解な仕様から効率の良いスケルトン並列プログラムを得るための系統的な手法を提案している。本手法は、3ステップから構成されている。まず、ユーザは (並列性を意識しない) 初期プログラムを再帰関数として与え、次にこの再帰関数に対して、diffusion定理を適用して並列木スケルトンの組み合わせを得る。その際に、個々の並列木スケルトンを効率良く動作させるための条件の充足性を、それぞれの計算で使用される演算の代数的な性質から示すことになる。本章では、このような系統的手法が実用的な並列プログラミングに有効であると主張している。

第6章 (Implementation of Binary-Tree Skeletons) では、分散メモリ環境で並列二分木スケルトンを効率良く実装するためのアルゴリズムを与えている。計算の局所性を高めるためプロセッサに分散された各部分の計算をループとスタックを利用して実現し、データの局所性と負荷分散を両立させるための木を分割する際のパラメータの値について議論している。さらに実験により、これらの工夫による並列木スケルトン実現の効率を確認している。

第7章 (SkeTo: Parallel Skeleton Library) では、並列スケルトンをC++言語のライブラリとして提供するSkeToライブラリを説明している。ライブラリの概要の他、並列スケルトンを実現する上でのコーディングテクニック、融合変換による最適化機構、コード生成器などの詳細を示している。また、9種類の例題プログラムに対する実験結果も報告している。

第8章 (Parallelizing Maximum Marking Problems) では、動的計画法によって解くことのできる多くの最適化問題を含む「最大マーク付け問題 (Maximum Marking Problems)」に対し、並列木スケルトンを用いて効率良く並列に計算できることを示している。特に、すでに提案されている手法によって導出される逐次プログラムに対して、第5章で述べている手法を適用して、系統的に並列化できることを示している。

第9章 (Parallelizing XPath Queries) では、XML文書処理で良く利用されるXPathクエリを対象として、その並列化アルゴリズムを示している。そこでは、親子関係、兄弟関係、述語を含むXPathクエリを並列木スケルトンの組合せによって実現できることに着目し、その並列化を論じている。

第10章 (Related Work) では、本論文に関係の深い研究を5つの観点から取り上げ、本論文との関係・類似点・差異などを論じている。

第11章 (Conclusion) では、以上の内容を、木構造に対する並列プログラミングの理論と実現という2つの観点からまとめ、さらに、今後の展望を述べている。

以上を要するに、本論文は並列木スケルトンによる並列プログラミングに関してあらたな方法論を理論的に展開するとともに、実際のシステムを構築しその有効性を示したもので、計算機科学の発展に寄与するところが大きい。よって本論文は博士(情報理工学)の学位請求論文として合格と認められる。