近年、並列計算環境はクラスタ・グリッドをはじめとしてより身近になりつつあるが、それを構成する計算機の計算性能・通信性能・ネットワークトポロジーは様々である。このため並列計算環境でよりよい性能を出すには、これら並列計算機の不規則性、不均一性の問題に向き合わなければならない。また、並列化を行った際には、計算の分割が可能な単位においても、要素ごとに必要な計算量や通信量が大きく異なってくるため、計算の割り当て負荷分散には、これらを十分考慮しなくてはならない。

この論文では、このような科学技術計算の持つ共通の課題について、生体分子のシミュレーションを分散メモリ型並列計算機上で行う分子動力学法を対象に研究を行った。周期境界条件を用いない分子動力学法や、真空中もしくは、溶媒の連続体近似を行うシミュレーションの場合には、領域により計算量の大きな偏りがあり、粒子の分布も一定ではない。従来の分子動力学法では、このような不規則性を持った問題の負荷分散はほとんど考慮されて来なかった。この研究では、そのような不規則性を持った問題を扱う。

分子動力学法は反復計算を行い、各ステップ内では粒子への力の計算を行った後、位置もしくは力の情報を通信を行うが、各々の力の計算の順序に依存関係はない。このときの並列化手法としては、全プロセスが全粒子の位置情報の複製を持つ手法と、分割して持つ手法に大別される。2つの手法にはそれぞれ長所と短所があり、どちらが優れていると一概にいうことはできない。そこでこれら2つの並列化手法について、通信時間の削減のために、それぞれ異なるアプローチを提案する。一つは全プロセスが複製を持つ手法で用いられる集団通信の最適化、もうひとつは、小セルによる空間分割法を用いた場合のデータ割り当てによる隣接通信の最適化である。

まず、第1部では、集団通信の最適化について扱う。前述の不規則性へ対処するために従来手法の多くは、プロセス全てに全原子のデータの複製を持たせている。この方法では、粒子とプロセッサ数の増加とともに通信時間が大きくなるが、系が小さい場合や、データの局所性が少ない場合、空間分割法よりも計算負荷を細かく制御でき、通信の効率も近くなるため、全体の効率が良くなる。まずここでは、集団通信のひとつであるBroadcast通信をpoint-to-pointの通信を用いてネットワークに適したスケジューリングを得る手法の研究を行った。集団通信の通信時間はそのスケジューリングに大きく左右され、分子動力学法のように大きなメッセージを通信する場合には、特にネットワーク構造が重要である。一般的にネットワークは多様な性質の回線から構成されており、ヘテロなネットワーク環境で効率的なスケジュールを得る事は難しい。しかし、そのような非均一性が増えつつある今、適切なスケジューリングを得る事が非常に重要になってくる。また、現在の汎用のMPIの実装においてBroadcast内の個々の通信はブロッキング通信で行われているため、複数のノードへの同時送信や受信と送信をオーバーラップすることができていないため、ネットワーク構造を考慮する事によって大きなデータの通信をより高速に行える機会を逸している。しかし、これを効率的に行うには、通信の競合を避ける事が重要である。この研究では、木構造型のネットワークにおけるBroadcastのスケジューリングを扱う。木構造型ネットワークでは、多くのノード間で共通の通信路を使うため、競合する可能性が大きい。このためスケジューリングによる通信時間削減の効果が大きい。ここでは、木構造の対称性から由来する冗長なスケジューリングの探索を削減する手法を提案し、分枝限定法による探索を行う。この手法では、通信ペアの削減により探索を高速化するため、通信のモデルに依らず枝刈りが可能となる。実験によりこのアルゴリズムの効率性を示し、また得られたスケジューリングによるBroadcastを組み込みのBroadcastと比較し、データサイズが大きい場合、大幅に通信時間が減る事を示す。また、このネットワーク構造に最適化されたBroadcastは、全プロセスが粒子の複製情報を持つ、粒子分割法や力計算の分割法による分子動力学法に用いられる集団通信Allgatherや、Allreduceの高速化に貢献することを実験により示し、ネットワークのヘテロ性を考慮する事の重要性を示す。

第2部では、分子動力学法などにおいて空間分割を行う際の新しい分割手法の研究を行った。空間分割法は系の空間が十分大きい場合、データの局所性が高くなり通信量が少ないため高い並列性能を示す。しかし、従来の空間分割法では、粒子の分布する空間が直方体領域をとるなど仮定が大きく、領域の割当もカットオフ半径の大きさの立方体領域単位で行うため粗く、負荷の均衡が難しい。そのため、全プロセスがデータの複製を持つ手法の方が好まれていたようである。一方で、グラフ分割手法は、科学技術計算においてデータの局所性を活かし、並列性を出す手法として貢献してきた。この手法ではデータ依存関係をグラフ表現し、頂点集合を同じ重みのパーティションに分割し、枝カット、つまりは通信コストを最小化する。グラフにより任意のデータ依存関係が表現でき、カットオフ半径よりも細かい領域の分割も容易に扱う事が可能となる。しかし、グラフ分割により通信量の削減は期待できるが、分割データの計算ノードへの割り当てを適切に行わなければ、通信に局所的な偏りが起きるなど期待した並列性能が得られない可能性がある。そこで本研究では、計算とそれに必要な通信をグラフとして表現した計算グラフを定義し、これをもとにプロセッサの処理能力に応じてデータを分割し、ネットワーク構造を考慮した割り当てを行う手法を開発した。提案手法では、グラフデータを並列計算機のネットワーク構造を考慮しながら、再帰的にマルチレベルな二分割を行うことにより、プロセッサへ割当てる。提案手法は、従来手法の以下の点を改善する。まず、従来の研究で用いられる枝カットは、通信量を正しく反映したものではない。そこで、並列計算のモデルとして計算グラフを定義した。次に、枝カットの最小化によって全体の通信量が削減されたとしても、個々のプロセッサの通信量が減らなければ、通信時間は削減されない。この研究では、このような個々の通信時間を反映するような目的関数を提案した。そして、従来は、ネットワーク構造は考慮されないか、考慮されても非常に単純なものになっている。そこで、MDのような通信の多いアプリケーションではバンド幅が通信時間を最も左右するパラメータと考え、ネットワークモデルを構築した。この3点の改良を元に、再帰的な二分割手法を拡張し実装した。この手法を分子動力学法のデータ分割に適用した実験において、負荷の均衡を保ちつつ、通信時間が大きく短縮される事を示した。特に、ヘテロな環境では、直接通信を行った場合で10-20%、中継を用いた通信で20-60%通信時間が削減された。

この研究により、特に、分子動力学法のような通信量の多いアプリケーションでは、ヘテロなネットワークで結ばれたクラスタ環境では、通信時間が大きく、並列効果を上げることが難しかったが、2つのアプローチによる提案手法によりそのような環境での通信時間を大きく抑える事が可能となった。

並列計算環境は比較的安価に構築可能なクラスタ・グリッドをはじめとしてより身近になりつつあるが、それを構成する計算機の計算性能・通信性能・ネットワークトポロジーは多様化している。このため、このようなヘテロな並列計算環境でよりよい性能を出すには、これら計算機の不規則性、不均一性からくる問題に対処しなければならない。本論文では、このような並列計算の持つ課題について、メッセージ通信による並列化を行った分子動力学法を対象に研究を行っている。また、不規則な粒子の分布をもったシミュレーションでは、領域ごとに計算負荷が大きく異なり、従来の分子動力学法では、このような不均一性、不規則性を含んだ問題の負荷分散はほとんど考慮されて来なかった。これに対し、本論文では、そのような不規則な問題に対しても高い並列性を保つ研究を行っている。

分子動力学法は反復計算を行い、各反復では粒子への力の計算を行った後、更新された粒子の位置もしくは力の情報を通信するが、各々の力の計算の順序に依存関係はない。このような場合の並列化手法としては、全プロセスが全粒子の位置情報の複製を持つ粒子分割法などの手法と、データを分割して持つ空間分割法などの手法に大別される。本論文では、この2つの並列化手法について、通信時間の削減のためにそれぞれ異なるアプローチの手法の研究を行っている。一つは全プロセスが複製を持つ手法で用いられる集団通信の最適化、もう一つは、小セルによる空間分割法を用いた場合のデータ割り当てによる隣接通信の最適化である。

本論文は、全8章で構成されており、2章、3章、4章は粒子分割法における通信の最適化手法について述べられ、5章、6章、7章で空間分割法における通信の最適化手法について述べられている。

まず1章では、並列分子動力学法の研究の背景と動機について述べ、分子動力学法において通信が並列化効率を下げる要因となっていることを説明している。2章では、ヘテロなネットワーク環境における集団通信の研究の背景と既存研究の問題点について述べられ、提案手法との比較を行っている。3章では、木構造型ネットワークのモデル化を行い、ネットワークの対称性を考慮し、効率的にpoint-to-pointの通信によるBroadcastの最適スケジュールを探索するアルゴリズムを提案している。このモデルでは、単純なstore and forwardモデルとは違い、ルータやハブのような中継ノードが考慮されている点、通信のパイプライン化を通信の競合を避けて行える点で従来のスケジューリング手法から大きく改善されている。4章では、提案アルゴリズムにより最適化されたブロードキャストを実際のヘテロな並列計算機環境上で実験を行い、モデルと提案手法の有効性を確認している。また、分子動力学法において集団通信の一部に用いた場合など、メッセージサイズが大きい場合に特にその有効性が示されている。5章では、空間分割法の研究の背景と従来のマッピング手法の問題点について述べられており改善すべき点を挙げている。6章では、通信量の見積りを正確に行うために並列計算のデータ依存関係を計算グラフとして定義し、ネットワークの不均一な性能を考慮したグラフマッピング手法を提案し、詳細を説明している。また、分子動力学法データのマッピングを計算する実験により、既存手法からの優位性を示している。7章では、実機上で提案するマッピング手法と既存の手法を比較し最大60%程度の通信時間の削減が可能であることを示し、提案したモデルとアルゴリズムの有効性を示している。また、粒子分割法、空間分割法による局所性の違う問題に対する通信所要時間の特性の違いについて論じ、両手法の有効なデータ、不得手なデータについて定性的に論じている。8章では、研究の総括をし、通信が不均一なネットワークにおいて、ネットワークを適切に考慮した通信が大きく通信性能を改善可能であることについて論じている。

以上、本論文は、ヘテロなネットワークで結ばれたクラスタ環境において、従来、通信時間が大きく並列効果を上げることが困難であった分子動力学法などの応用に対し、それらの性能を大幅に改善する手法を提案したものである。

よって本論文は博士（情報理工学）の学位請求論文として合格と認められる。