Over the past ten years, clusters have become the predominant architecture for performing parallel computation. By connecting multiple compute nodes by a Local Area Network (LAN), clusters make a large amount of processing power, memory and storage available for parallel computation. By connecting two or more of these clusters by a Wide Area Network (WAN), even more computational resources become available for parallel computation. Recently, the bandwidth of WANs has increased significantly,increasing the number of applications that can potentially take advantage of multi-cluster environments.

Unfortunately, multi-cluster environments are significantly more complex than single cluster environments.In particular, they introduce or magnify problems concerning connectivity, scalability, locality and adaptivity. As it is undesirable and unrealistic for each individual application to handle these problems separately, demands for wide-area communication libraries that handle these problems have increased.

Concerning connectivity, wide-area communication libraries need to be aware that connections between clusters are commonly blocked by firewalls or NAT. A simplistic scheme that assumes that all processes can connect to each other will encounter problems when deployed in WANs. Only some connections will be allowed, and messages must be routed between every pair of processes using those connections.

As for scalability, wide-area communication libraries need to avoid simplistic schemes that establish a large number of connections. While all connections consume resources, wide-area connections especially consume a lot of resources, causing various resource allocation problems. In addition to resource allocation problems, using a large number of wide-area connections in an uncoordinated fashion can result in low communication performance due to congestion.

The two previous requirements basically say that a wide-area communication library will establish connections between a subset of all process pairs. Then in order to maintain high communication performance,the process pairs that do establish connections should be selected in a locality-aware manner.In general, connections between nearby processes should be favored over connections between faraway processes, and connections between processes that communicate frequently should be favored over those that communicate infrequently.

Moreover, wide-area communication libraries should automatically satisfy the three previous requirements by adapting to environments and to applications. They should not rely on manual configuration,because it is tedious, it does not scale, and it is the cause of various errors.

Much previous research has focused on each of these requirements separately, but more work is necessary in order for wide-area communication libraries to meet all of these requirements. For example,research centered around message passing offers good locality but poor scalability and adaptivity and research centered around P2P overlay networks offers good scalability and adaptivity but poor locality.

This has motivated me to make two proposals concerning the design and implementation of scalable high-performance communication libraries for wide-area computing environments: a locality-aware connection management scheme and a locality-aware rank assignment scheme. Using the two proposed methods, I have implemented a wide-area MPI library called MC-MPI and a wide-area Sockets library called SSOCK.

My connection management scheme overcomes firewalls and NAT by constructing an overlay network, and achieves scalability by limiting the number of connections that each process establishes to O(log n)when the number of total processes is n. In order to achieve high performance with a limited number of connections, the connections that are established are selected in a locality-aware manner, based on latency and traffic information obtained from a short profiling run.

My rank assignment scheme for wide-area communication libraries. This scheme finds a low-overhead mapping between ranks (process IDs) and processes by formulating the rank assignment problem as a QAP. It uses latency and traffic information obtained from the profiling run as well as routing information obtained from the connection management scheme in order to adapt to environments and applications.

Using the proposed connection management and rank assignment schemes, I have implemented a wide-area MPI library called MC-MPI. I have evaluated its performance by running the NPB on 256 cores distributed equally across 4 real clusters. For the IS benchmark, MC-MPI performed up to 2.1 times better than when connections were established between all processes. For the other benchmarks,MC-MPI was able to limit the number of process pairs that established connections to just 10 percent without suffering a performance penalty. Moreover, MC-MPI was able to find rank assignments that performed up to 4.0 times better than locality-unaware assignments and up to 1.2 times better than host name-based assignments.

In order to support not just MPI applications but any parallel application, I have also used the proposed connection management scheme to implement a wide-area Sockets library called SSOCK. In one experiment, SSOCK was able to connect 1,262 processes with each other in a 13-cluster environment with firewalls and NAT, without any of the connectivity issues and resource allocation problems that were encountered when the Socket library was used. In another experiment in which 100 processes simultaneously tried to establish connections, SSOCK was able to establish connections between all pairs of processes in 1.2 seconds, while the Socket library suffered from a large number of packet losses and timed out after 189 seconds.

本論文は、「Design and Implementation of Scalable High-performance Communication Libraries for Wide-area Computing Environments」(広域計算環境における並列計算用のスケーラブルな高性能通信ライブラリの設計と実装)と題し、非均質な広域計算環境における並列計算をこれまでにない規模で効率良く実行できるようにすることを目的とし、高性能な通信を、環境に適応して自動的に達成する通信ライブラリの設計と実装を提案し、実証実験によりその有効性を論じたものであり、全体で7章から構成されている。論文は英語で書かれている。

第1章は「Introduction」(緒言)であり、Wide Area Network(WAN)のバンド幅の増加に伴って広域計算環境において並列計算を行う機会が増加したことについて述べ、広域計算環境における並列計算を支援する通信ライブラリが満たすべき接続性・スケーラビリティ・性能等に関する要件について説明している。そして、本研究で提案している通信ライブラリの構成技術である接続管理手法とランク割当て手法について述べている。また、それらを用いて実装したメッセージパッシングライブラリMulti-Cluster MPIとソケットライブラリScalable Socketsについて述べている。

第2章は「Related Work」(関連研究)と題し、本研究に関連する研究について述べている。まず、Virtual Private Network(VPN)やSOCKSなどについて述べ、それらが小規模な環境で接続性を確保するためには有用であるが、大規模な環境で任意のノードが互いに通信できるようにするためには多くの設定が必要であることを指摘している。次に、スケーラビリティを向上させるための手法としてPeer-to-Peer(P2P)オーバレイネットワークについて述べ、性能上の理由で並列計算には向かないことを指摘している。また、第6章の実験でScalable Socketsの比較相手として用いている広域計算環境用の通信ライブラリSmartSocketsについて述べている。

第3章は「Message Passing」(メッセージパッシング)と題し、メッセージパッシングモデル及びメッセージパッシングライブラリの構成法について説明している。まず、メッセージパッシングモデルの概要を述べ、メッセージパッシングのデファクトスタンダードApplication Programming Interface(API)であるMessage Passing Interface(MPI)について説明している。次に、広域計算環境においてメッセージパッシングを行う場合の局所性と接続性に関する課題について述べ、MPICH-G2やGridMPIなどの既存の広域計算環境用のMPIライブラリがそれらの課題にどのように対処しているかについて説明している。そして、スケーラビリティと通信性能を向上させるために確立する接続の数を制限する必要性について説明し、既存のMPIライブラリの用いている単純な接続管理は全対全通信を伴うようなアプリケーションではうまくいかないことを指摘している。最後に、MPIライブラリによるプロセスへのID割当て(ランク割当て)がMPIアプリケーションの性能に大きな影響を与えることを説明し、既存のランク割当て手法はアプリケーションや計算環境に十分に適応できないということを指摘している。

第4章は「Design and Implementation of MC-MPI」(MC-MPIの設計と実装)と題し、提案する接続管理手法とランク割当て手法について説明し、それらの手法を用いて実装されているMPIライブラリMulti-Cluster MPI(MC-MPI)について説明している。MC-MPIは、アプリケーションを短時間実行するプロファイリング実行によって遅延行列と通信行列を取得し、本実行でそれらの行列を用いて最適化された接続管理とランク割当てを行う。接続管理は、オーバレイネットワークを構築することによって接続性の問題を解決し、各プロセスが確立する接続の数をO(log n)に制限することによってスケーラビリティを向上させる。また、それらO(log n)個の接続を遅延行列と通信行列に基づいて選択することによって限られた数の接続で高い通信性能を出す。一方、ランク割当ては、遅延行列と通信行列を基に作成した二次割当て問題を解くことによって通信オーバヘッドの低い割当てを行う。二次割当て問題はNP困難であるが、ヒューリスティクスを用いる既存のライブラリを用いることによって良い近似解を得る。

第5章は「Performance Evaluation of MC-MPI」(MC-MPIの性能評価)と題し、4クラスタ256コアからなる実広域計算環境を用いてMC-MPIの性能を評価している。ベンチマークとしては、MPIライブラリの性能評価に広く用いられているNAS Parallel Benchmarks(NPB)とMPIで記述されたモデル検査ツールであるDistributed Verification Environment(DiVinE)を用いている。接続管理については、MC-MPIの性能と全対全で接続を確立した場合の性能・手動で中継プロセスを設定した場合の性能・ランダムに接続の数を制限した場合の性能を比較することによって、限られた数の接続で既存の手法に劣らない性能が出ることを示している。また、NPBのInteger Sort(IS)やDiVinEのように多数のプロセスが同時に通信するアプリケーションでは、接続の数を制限することによってコンジェスチョンが回避できて、多数の接続を用いるよりむしろ高い性能が出ることを示している。一方、ランク割当てについては、MC-MPIの性能とホスト名に基づく割当てを用いた場合の性能・ランダムな割当てを用いた場合の性能を比較することによって、自動的に行った割当てで既存の手法と同等もしくはそれ以上の性能が出ることを示している。

第6章は「Scalable Sockets」(スケーラブルソケッツ)と題し、Socket APIを提供することによってMC-MPIをより汎用的にしたライブラリScalable Sockets(SSOCK)について説明している。SSOCKは、MC-MPIの接続管理手法を用いて中継デーモンのオーバレイネットワークを構築し、そのオーバレイネットワークを用いてconnectやsendなどを実現する。13クラスタ338~1,264コアからなる実広域計算環境で行った評価実験では、SSOCKが既存の広域計算環境用の通信ライブラリよりスケーラビリティが高いことを示している。また、1対1通信性能は同等で、全対全通信性能はSSOCKの方が高いことを示している。

第7章「Conclusion and Future Work」(結論と今後の課題)では、本論文の主たる成果をまとめるとともに、今後の方向性について述べている。

以上を要するに、本論文は、非均質な広域計算環境における並列計算をこれまでにない規模で効率良く実行できるようにすることを目的とし、高性能な通信を、環境に適応して自動的に達成する通信ライブラリの設計と実装を提案し、実証実験によりその有効性を論じたものであり、電子情報学上貢献するところが少なくない。

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