JP5532849B2 - コンピュータ、プロセス間通信プログラム、およびプロセス間通信方法 - Google Patents

Description

本発明はネットワークを介したプロセス間の通信を行うコンピュータ、プロセス間通信プログラム、およびプロセス間通信方法に関する。

近年、ＨＰＣ（High Performance Computing）システムとして、小規模のコンピュータを多数接続して並列処理を実行するクラスタシステムがある。特にＩＡ（インテル・アーキテクチャ）サーバを高速ネットワークで接続したクラスタシステムは、ＰＣ（Personal Computer）クラスタシステムと呼ばれ、幅広く使われている。

クラスタシステムで並列プログラムを実行する場合、並列プログラムの実行により起動されるプロセスは、複数のサーバに分散して実行される。そのため、プロセス間でデータ交換が必要なときは、サーバ間通信が必要になる。従い、クラスタシステムの処理性能向上に、サーバ間通信性能の向上が重要である。サーバ間通信で高性能を実現するには、InfiniBand・Myrinetなどの高性能なネットワークに加え、高性能な通信ライブラリを用意することも重要である。クラスタシステムでは、ＭＰＩ（Message Passing Interface）という通信ＡＰＩ（Application Program Interface）で記述された並列プログラムが実行されることが多く、様々なＭＰＩ通信ライブラリが実装・提供されている。

並列プログラムにおけるプロセス間の通信パターンはプログラム次第であり多種多様であるが、その中でも特に重要視される通信パターンの１つに、全対全通信がある。全対全通信は、その名の通り、すべてのプロセスがすべてのプロセスとデータ送受する通信パターンである。ＭＰＩでは関数”MPI＿Alltoall()”に全対全通信機能が実装されている。

全対全通信を実現する通信アルゴリズムは様々なものがある。その中で、比較的データサイズが大きく、ネットワークバンド幅で性能が制限を受けるケースでは、Ringアルゴリズムが使われることが多い。

特表２００９−５１９５０４号公報

ところで、ＩＡプロセッサなどのプロセッサのマルチコア化が進展した結果、クラスタシステムを構成するサーバはマルチコアプロセッサを搭載することが一般的となった。マルチコアプロセッサでは、プロセッサコアごとにプロセスが実行されることが多い。例えば、４コアＣＰＵを２個（総コア数８個）搭載したサーバで構成されるクラスタシステムでは、並列プログラム実行時に１サーバ当たり８個のプロセスが実行されることも珍しくない。以下、サーバ１台当たりのプロセス数を、ローカルプロセス数と呼ぶこととする。

しかし、Ringアルゴリズムなど、現在の通信アルゴリズムの多くは１サーバ当たり１プロセスを前提として発案・実装されており、マルチコアプロセッサが実装されたサーバによるクラスタシステムに適用するには不適切である。実際、サーバ数１６で、ローカルプロセス数を１，２，４，８と変え、Ringアルゴリズムで全対全通信を行ったときの実効ネットワークバンド幅を測定すると、ローカルプロセス数が多いときには実効ネットワークバンド幅が低下することが分かる。実効ネットワークバンド幅が低下するのは、ローカルプロセス数が２以上の場合にRingアルゴリズムで全対全通信を行うと、ネットワークスイッチ内でＨＯＬ（Head-Of-Line）ブロッキングと呼ばれる競合が発生するためである。ＨＯＬブロッキングとは、複数の入力ポートから同一の出力ポートへ同時にパケット転送するときに発生するものであり、出力ポートのバッファが競合するためにパケット転送が遅延される現象である。

このように従来の全対全のプロセス間通信アルゴリズムは、複数のプロセスが実行されるサーバによるクラスタシステムにとって適切なアルゴリズムではない。その結果、そのようなクラスタシステムで既存のアルゴリズムを用いてプロセス間通信を行うと、システム全体の性能を十分に発揮させることができなかった。

本発明はこのような点に鑑みてなされたものであり、複数のプロセスが実行されるサーバによるクラスタシステムにおける効率的な全対全のプロセス間通信が可能なコンピュータ、プロセス間通信プログラム、およびプロセス間通信方法を提供することを目的とする。

上記課題を解決するために、以下の機能を有するコンピュータが提供される。
コンピュータは、クラスタシステムを構成する複数のサーバのうちの１つとして機能し、複数のサーバそれぞれで実行されるプロセス間の通信を行う。そのために、コンピュータは、送信先サーバ決定手段、送信先プロセス決定手段、およびデータ送信手段を有する。

送信先サーバ決定手段は、全対全のプロセス間通信時に複数のサーバそれぞれで繰り返し行われる送信先サーバ決定における同一回の送信先サーバ決定において、複数のサーバが互いに異なるサーバを送信先サーバとして決定するような送信先サーバ決定手順が予め定義されており、コンピュータで実行される自プロセスからの全対全のプロセス間通信要求に応答し、送信先サーバ決定手順に従って送信先サーバを繰り返し決定する。送信先プロセス決定手段は、送信先サーバが決定されるごとに、決定された送信先サーバで動作しているプロセスを順番に送信先プロセスとして決定する。データ送信手段は、送信先プロセスが決定されるごとに、自プロセスの実行により送信用のデータが格納された送信用バッファから送信先プロセスに対する送信データを取得し、送信先サーバ内の決定された送信先プロセスの実行時に送信データを読み取り可能とするように、送信先サーバに対して取得した送信データを送信する。

複数のプロセスが実行されるサーバによるクラスタシステムにおいて、効率的な全対全のサーバ間通信が可能となる。

第１の実施の形態の機能を示すブロック図である。 本実施の形態のシステム構成例を示す図である。 本実施の形態に用いるコンピュータのハードウェア構成例を示す図である。 全対全通信の動作イメージを示す図である。 ネットワークスイッチ内の通信経路を示す図である。 ネットワークスイッチによるパケットの受信状況を示す図である。 ネットワークスイッチにおけるＨＯＬブロッキング発生状態を示す図である。 サーバの機能を示すブロック図である。 プロセス間通信制御部の全対全通信機能を示すブロック図である。 全対全通信処理の手順を示すフローチャートである。 第２の実施の形態における2-Level Ringアルゴリズムによるプロセス決定を行う処理記述例を示す図である。 Ringアルゴリズムによるプロセス間通信の状態遷移を示す第１の図である。 Ringアルゴリズムによるプロセス間通信の状態遷移を示す第２の図である。 ４番目のステップ（Ｓｔｅｐ＝３）における競合の発生状況を示す図である。 Ringアルゴリズムの各通信ステップの実行時間を示す図である。 2-Level Ringアルゴリズムによるプロセス間通信の状態遷移を示す第１の図である。 2-Level Ringアルゴリズムによるプロセス間通信の状態遷移を示す第２の図である。 2-Level RingアルゴリズムとRingアルゴリズムとの実効ネットワークバンド幅の測定結果を示す図である。 第３の実施の形態におけるサーバの機能を示すブロック図である。 プロセスＩＤ管理テーブル記憶部のデータ構造例を示す図である。 第３の実施の形態における2-Level Ringアルゴリズムによるプロセス決定を行う処理記述例を示す図である。

以下、本実施の形態について図面を参照して説明する。
〔第１の実施の形態〕
図１は、第１の実施の形態の機能を示すブロック図である。コンピュータＡは、クラスタシステムを構成する複数のサーバのうちの１つとして機能する。すなわち、複数のサーバ６−１，６−２，・・・とコンピュータＡとがネットワークスイッチ５で接続され、クラスタシステムとして動作する。コンピュータＡおよび複数のサーバ６−１，６−２，・・・は、それぞれで実行されるプロセス間の通信を行う。

コンピュータＡは、複数のプロセス１−１，１−２，１−３，・・・が動作している。同様に、サーバ６−１，６−２，・・・でも複数のプロセスが動作している。サーバ６−１，６−２，・・・内に複数のプロセッサ６ａ−１，６ａ−２，６ｂ−１，６ｂ−２に実装されている。各プロセッサ６ａ−１，６ａ−２，６ｂ−１，６ｂ−２は、複数のプロセッサコアを有し、プロセッサコアそれぞれがプロセスを実行している。図１の例では、サーバ６−１，６−２，・・・内のプロセスを円形で示している。

このようにコンピュータＡおよび複数のサーバ６−１，６−２，・・・では、複数のプロセスが動作し、各プロセスが、クラスタシステムで実行すべき計算処理を実行する。各プロセスは、所定の計算処理が終了すると、プロセス間通信によりデータの送受信を行う。このプロセス間通信の１つに全対全通信がある。

コンピュータＡのプロセス１−１，１−２，１−３，・・・は、送信用バッファ２−１，２−２，２−３，・・・と受信用バッファ３−１，３−２，３−３，・・・を介して、データの受け渡しを行う。送信用バッファ２−１，２−２，２−３，・・・と受信用バッファ３−１，３−２，３−３，・・・とは、例えばコンピュータＡの主記憶装置内の記憶領域の一部である。

全対全通信を実行するタイミングになると、プロセス１−１，１−２，１−３，・・・の実行により、送信するデータが送信用バッファ２−１，２−２，２−３，・・・に格納される（計算処理中に使用していたバッファをそのまま送信用バッファとすることもある）。その後、プロセス１−１，１−２，１−３，・・・から全対全のプロセス間通信要求が出される。

プロセス１−１，１−２，１−３，・・・のそれぞれから全対全のプロセス間通信要求が出力されると、プロセス１−１，１−２，１−３，・・・それぞれに対応する全対全通信手段４−１，４−２，４−３，・・・が起動される。全対全通信手段４−１，４−２，４−３，・・・は、対応するプロセス１−１，１−２，１−３，・・・から出力されたデータを他のプロセスに送信し、他のプロセスから受信したデータをプロセス１−１，１−２，１−３，・・・に渡す。なお、全対全通信手段４−１，４−２，４−３，・・・は同じ機能を有する。そこで、以下、代表的に全対全通信手段４−１の機能について詳細に説明する。

全対全通信手段４−１は、送信先サーバ決定手段４ａ、送信先プロセス決定手段４ｂ、データ送信手段４ｃ、受信元サーバ決定手段４ｄ、受信元プロセス決定手段４ｅ、およびデータ受信手段４ｆを有する。

送信先サーバ決定手段４ａは、コンピュータＡで実行される自プロセス（プロセス１−１）からの全対全のプロセス間通信要求に応答し、予め定義された送信先サーバ決定手順に従って送信先サーバを繰り返し決定する。送信先サーバ決定手順には、全対全のプロセス間通信時に複数のサーバそれぞれで繰り返し行われる送信先サーバ決定における同一回の送信先サーバ決定において、複数のサーバが互いに異なるサーバを送信先サーバとして決定するように定義されている。

例えば、送信先サーバ決定手順としては、複数のサーバそれぞれに付与されたサーバ番号を所定の配列で並べ、コンピュータＡに付与されたサーバ番号と他のサーバ番号との配列上の相対的位置関係に基づいて送信先サーバを決定するように定義される。このような送信先サーバ決定手順であれば、コンピュータＡおよび各サーバ６−１，６−２，・・・が共通の送信先サーバ決定手順で送信先サーバを決定しても、同一回の送信先サーバ決定において、互いに異なるサーバを送信先サーバとして決定できる。すなわち、コンピュータＡおよび各サーバ６−１，６−２，・・・は、それぞれ異なるサーバ番号を有している。そのため、自己のサーバ番号を基準とした配列上の相対的位置関係を特定した場合、それぞれ異なるサーバ番号の位置が特定される。その結果、コンピュータＡおよび各サーバ６−１，６−２，・・・において、互いに異なるサーバを送信先サーバとして決定できる。なお、自己のサーバ番号を基準とした送信先サーバ決定手順を用いた場合、１つのコンピュータＡ内の各全対全通信手段４−１，４−２，４−３，・・・は、同一回の送信先サーバ決定において共通のサーバを送信先サーバとして決定することとなる。

コンピュータＡに付与されたサーバ番号と他のサーバ番号との配列上の相対的位置関係に基づいて送信先サーバを決定するような送信先サーバ決定手順として、例えばサーバ番号を環状に配置するものがある。具体的には、複数のサーバそれぞれに付与されたサーバ番号を昇順で並べると共に、サーバ番号の最大値の次順をサーバ番号の最小値とする配列とする。送信先サーバ決定手順には、コンピュータＡに付与されたサーバ番号から配列の並びに沿って一定方向にサーバ番号を順次決定し、決定したサーバ番号で示されるサーバを送信先サーバとすることが定義される。

送信先プロセス決定手段４ｂは、送信先サーバが決定されるごとに、送信先サーバで動作しているプロセスを順番に送信先プロセスとして決定する。例えば、送信先プロセス決定手段４ｂは、予め定義された送信先プロセス決定手順に従って、全対全のプロセス間通信要求を出力した自プロセス（プロセス１−１）に対する送信先サーバを繰り返し決定する。送信先プロセス決定手順では、複数のプロセス１−１，１−２，１−３，・・・それぞれに対する送信先プロセス決定が繰り返し行われる。そして送信先サーバ決定手順では、同一回の送信先プロセス決定において、複数のプロセスプロセス１−１，１−２，１−３，・・・それぞれに対して、送信先サーバ内の互いに異なるプロセスを送信先プロセスとして決定するように定義されている。なお、複数のプロセス１−１，１−２，１−３，・・・それぞれに対する送信先プロセス決定は、複数のプロセス１−１，１−２，１−３，・・・それぞれから出力される全対全のプロセス間通信要求に応じて行われる。

例えば、送信先プロセス決定手順では、複数のプロセスそれぞれに付与されたプロセス番号を所定の配列で並べることが定義される。さらに送信先プロセス決定手順では、全対全のプロセス間通信要求を出力した自プロセス（プロセス１−１）に付与されたプロセス番号と他のプロセスのプロセス番号との配列上の相対的位置関係に基づき送信先プロセスを決定するように定義される。このような送信先プロセス決定手順であれば、全対全通信手段４−１，４−２，４−３，・・・が共通の送信先プロセス決定手順で送信先プロセスを決定しても、同一回の送信先プロセス決定において、互いに異なるプロセスを送信先プロセスとして決定できる。すなわち、全対全通信手段４−１，４−２，４−３，・・・は、それぞれ異なる自プロセスのプロセス番号を有しているため、そのプロセス番号を基準とした配列上の相対的位置関係を特定した場合、それぞれ異なるプロセス番号の位置が特定される。その結果、全対全通信手段４−１，４−２，４−３，・・・において、互いに異なるプロセスを送信先プロセスとして決定できる。

自プロセスのプロセス番号と他のプロセス番号との配列上の相対的位置関係に基づいて送信先プロセスを決定するような送信先プロセス決定手順として、例えばプロセス番号を環状に配置するものがある。具体的には、送信先サーバ内の複数のプロセスそれぞれに付与された送信先サーバ内でプロセスを一意に識別するローカルプロセス番号を昇順で並べると共に、ローカルプロセス番号の最大値の次順をプロセス番号の最小値とする配列とする。送信先プロセス決定手順には、自プロセスに付与されたプロセス番号から配列の並びに沿って一定方向にプロセス番号を順次決定し、決定したプロセス番号で示される送信先サーバ内のプロセスを送信先プロセスとすることが定義される。

データ送信手段４ｃは、送信先プロセスが決定されるごとに、自プロセスにより送信用のデータが格納された送信用バッファ２−１から送信先プロセスに対する送信データを取得する。そしてデータ送信手段４ｃは、送信先サーバ内の決定された送信先プロセスの実行時に送信データを読み取り可能とするように、送信先サーバに対して取得した送信データを送信する。

受信元サーバ決定手段４ｄは、コンピュータＡで実行される自プロセス（プロセス１−１）からの全対全のプロセス間通信要求に応答し、予め定義された受信元サーバ決定手順に従って受信元サーバを繰り返し決定する。受信元サーバ決定手順には、全対全のプロセス間通信時に複数のサーバそれぞれで繰り返し行われる受信元サーバ決定における同一回の受信元サーバ決定において、複数のサーバが互いに異なるサーバを受信元サーバとして決定するように定義されている。

受信元プロセス決定手段４ｅは、受信元サーバが決定されるごとに、受信元サーバで動作しているプロセスを順番に受信元プロセスとして決定する。
データ受信手段４ｆは、受信元プロセスが決定されるごとに、受信元サーバ内の決定された受信元プロセスから送信される受信データを取得し、取得した受信データを受信用バッファ３−１に格納する。

このような全対全通信手段４−１，４−２，４−３，・・・と同様の通信手段が、他のサーバ６−１，６−２，・・・にも設けられている。すると、クラスタシステム内の各プロセスが全対全のプロセス間通信を開始すると、それぞれのプロセスに関する同一回の送信先サーバ決定では、異なるサーバ内のプロセスに対しては互いに異なるサーバが送信先サーバとして決定される。次に、各プロセスのデータの送信先となる送信先プロセスとして、送信先サーバ内のプロセスが決定される。そして、各プロセスの出力したデータが、そのプロセスに対して決定された送信先プロセスに対して送信される。

このように、異なるサーバで実行される各プロセスに関する同一回の送信先サーバ決定では、異なるサーバが送信先サーバに決定されるため、送信したデータのネットワークスイッチ５での転送において出力ポートの競合が抑制される。出力ポートの競合が発生しなければ、ＨＯＬブロッキングの発生も抑制され、全対全のプロセス間通信の処理効率が向上する。

ここで、全対全通信手段４−１，４−２，４−３，・・・において送信先プロセスのみではなく受信元プロセスの決定も行っているのは、受信元プロセスからのデータを即座に受け取れるように、データ受信手段４ｆ内のバッファを用意しておくためである。すなわちデータ受信手段４ｆは、受信元プロセスが決定されると、その受信元プロセスから送られるデータを優先的に取得するためのバッファを確保する。これにより、コンピュータ間の他の通信が発生し、他のデータの受信があったとしても、受信元プロセスから送られたデータを即座に受信し、プロセス用に設けられた受信用バッファに格納できる。その結果、全対全のプロセス間通信の処理効率を向上させることができる。

〔第２の実施の形態〕
次に、第２の形態の詳細を説明する。第２の実施の形態は、各プロセスのプロセス番号を、そのプロセスが実行されるサーバのサーバ番号と、そのプロセスのサーバ内でのローカルプロセス番号から算出できるようにすることで、受信元・送信先プロセスの決定を容易にしたものである。なお、第２の実施の形態では、サーバ番号をサーバＩＤとよび、プロセス番号をプロセスＩＤと呼ぶこととする。

図２は、本実施の形態のシステム構成例を示す図である。本実施の形態に係るクラスタシステムでは、ネットワークスイッチ５００を介して複数のサーバ１００，２００，３００，４００が接続されている。

各サーバ１００，２００，３００，４００は、それぞれプロセッサ１１０，２１０，３１０，４１０と通信インタフェース１２０，２２０，３２０，４２０とを有している。プロセッサ１１０は複数のプロセッサコア１１１，１１２を有する。同様にプロセッサ２１０は複数のプロセッサコア２１１，２１２を有し、プロセッサ３１０は複数のプロセッサコア３１１，３１２を有し、プロセッサ４１０は複数のプロセッサコア４１１，４１２を有する。

各サーバ１００，２００，３００，４００には、サーバＩＤが割り振られている。サーバ１００のサーバＩＤは「０」、サーバ２００のサーバＩＤは「１」、サーバ３００のサーバＩＤは「２」、サーバ４００のサーバＩＤは「３」である。

また各サーバ１００，２００，３００，４００内のプロセッサに含まれるプロセッサコアで実行されるプロセスには、サーバ内でのローカルプロセスＩＤが割り振られる。図２では、プロセッサコアを示す円の中に、そのプロセッサコアで実行されるプロセスのローカルプロセスＩＤが示されている。

各プロセスには、クラスタシステム内でプロセスを一意に識別するためのプロセスＩＤも定義される。第２の実施の形態では、プロセスが実行されるサーバのサーバＩＤにローカルプロセス数（サーバ当たりのプロセス数）を乗算し、乗算結果にプロセスのローカルプロセスＩＤの値を加算した結果が、プロセスＩＤとなる。

次にサーバ１００，２００，３００，４００のハードウェア構成について説明する。
図３は、本実施の形態に用いるコンピュータのハードウェア構成例を示す図である。サーバ１００は、複数のプロセッサコア１１１，１１２を有するプロセッサ１１０によって装置全体が制御されている。プロセッサ１１０には、バス１０８を介してＲＡＭ（Random Access Memory）１０２と複数の周辺機器が接続されている。

ＲＡＭ１０２は、サーバ１００の主記憶装置として使用される。ＲＡＭ１０２には、プロセッサ１１０に実行させるＯＳ（Operating System）のプログラムやアプリケーションプログラムの少なくとも一部が一時的に格納される。また、ＲＡＭ１０２には、プロセッサ１１０による処理に必要な各種データが格納される。

バス１０８に接続されている周辺機器としては、ハードディスクドライブ（ＨＤＤ:Hard Disk Drive）１０３、グラフィック処理装置１０４、入力インタフェース１０５、光学ドライブ装置１０６、および通信インタフェース１２０がある。

ＨＤＤ１０３は、内蔵したディスクに対して、磁気的にデータの書き込みおよび読み出しを行う。ＨＤＤ１０３は、サーバ１００の二次記憶装置として使用される。ＨＤＤ１０３には、ＯＳのプログラム、アプリケーションプログラム、および各種データが格納される。なお、二次記憶装置としては、フラッシュメモリなどの半導体記憶装置を使用することもできる。

グラフィック処理装置１０４には、モニタ１１が接続されている。グラフィック処理装置１０４は、プロセッサ１１０からの命令に従って、画像をモニタ１１の画面に表示させる。モニタ１１としては、ＣＲＴ（Cathode Ray Tube）を用いた表示装置や液晶表示装置などがある。

入力インタフェース１０５には、キーボード１２とマウス１３とが接続されている。入力インタフェース１０５は、キーボード１２やマウス１３から送られてくる信号をプロセッサ１１０に送信する。なお、マウス１３は、ポインティングデバイスの一例であり、他のポインティングデバイスを使用することもできる。他のポインティングデバイスとしては、タッチパネル、タブレット、タッチパッド、トラックボールなどがある。

光学ドライブ装置１０６は、レーザ光などを利用して、光ディスク１４に記録されたデータの読み取りを行う。光ディスク１４は、光の反射によって読み取り可能なようにデータが記録された可搬型の記録媒体である。光ディスク１４には、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）などがある。

通信インタフェース１２０は、ネットワークスイッチ５００に接続されている。通信インタフェース１２０は、ネットワークスイッチ５００を介して、他のサーバ２００，３００，４００との間でデータの送受信を行う。

以上のようなハードウェア構成によって、本実施の形態の処理機能を実現することができる。なお図３にはサーバ１００のハードウェア構成を示したが、他のサーバ２００，３００，４００も同様のハードウェアで実現できる。

このような構成のサーバ１００，２００，３００，４００では、プロセッサコアごとのプロセスが生成される。各プロセスを生成したプロセッサコアが演算処理を実行する。大規模な演算を行う場合、演算処理が分割され、分割された個々の処理が各プロセスに振り分けられる。各プロセスを実行するプロセッサコアにより、振り分けられた演算処理が並列に実行される。各プロセスを実行するプロセッサコアは互いに通信し、演算結果を他のプロセスを実行するプロセッサコアと交換する。このようなデータ交換の中で、全対全通信が行われることがある。全対全通信では、各プロセスを実行するプロセッサコアが、他のすべてのプロセスを実行するプロセッサコアとの間で通信を行う。

図４は、全対全通信の動作イメージを示す図である。図４の例では、Ｎ個（Ｎは１以上の自然数）のプロセス間で全対全通信を行う場合における、時間経過に伴う各プロセスの処理内容の変遷を示している。各プロセスの白抜きの部分は、計算処理を実行している時間帯を示している。また各プロセスの網掛の部分は、通信処理を実行している時間帯を示している。

各プロセスを実行するプロセッサコアは、所定の計算部分に関する計算処理が終了すると、他のプロセスとの間の全対全通信に対応する関数を呼び出す。例えば、全対全通信用のＭＰＩ関数が読み出される。

全対全のプロセス間通信のうち、異なるサーバに属するプロセス間通信は、ネットワークスイッチ５００を経由して実行される。ネットワークスイッチ５００では、１つの通信ポートから出力するデータが、別の複数の通信ポートに同時に入力されると、ＨＯＬブロッキングが発生する。以下、図５〜図７を参照して、ＨＯＬブロッキングの発生状況について説明する。

図５は、ネットワークスイッチ内の通信経路を示す図である。図５には、ネットワークスイッチ５００における４台のサーバ１００，２００，３００，４００それぞれに接続された通信ポート５１０，５２０，５３０，５４０間の通信経路が示されている。通信ポート５１０にはサーバ１００が接続され、通信ポート５２０にはサーバ２００が接続され、通信ポート５３０にはサーバ３００が接続され、通信ポート５４０にはサーバ４００が接続されているものとする。

ネットワークスイッチ５００の各通信ポート５１０，５２０，５３０，５４０は、入力ポート５１１，５２１，５３１，５４１と出力ポート５１２，５２２，５３２，５４２とを有する。入力ポート５１１，５２１，５３１，５４１には、接続されたサーバから他のサーバに送信するパケットが入力される。出力ポート５１２，５２２，５３２，５４２からは、接続されたサーバに対して他のサーバから送信されたパケットが出力される。入力ポート５１１，５２１，５３１，５４１にはバッファが設けられている。入力ポート５１１，５２１，５３１，５４１内のバッファには、入力されたパケットを一次的に蓄えることができる。同様に、出力ポート５１２，５２２，５３２，５４２にはバッファが設けられている。出力ポート５１２，５２２，５３２，５４２内のバッファには、出力するパケットを一次的に蓄えることができる。

通信ポート５１０の入力ポート５１１からは、他の通信ポート５２０，５３０，５４０の出力ポート５２２，５３２，５４２への通信経路が設けられている。通信ポート５２０の入力ポート５２１からは、他の通信ポート５１０，５３０，５４０の出力ポート５１２，５３２，５４２への伝送路が設けられている。通信ポート５３０の入力ポート５３１からは、他の通信ポート５１０，５２０，５４０の出力ポート５１２，５２２，５４２への伝送路が設けられている。通信ポート５４０の入力ポート５４１からは、他の通信ポート５１０，５２０，５３０の出力ポート５１２，５２２，５３２への伝送路が設けられている。

クラスタシステムのプロセスを実行する全プロセッサコアが全対全通信を開始すると、ネットワークスイッチ５００を介した通信が発生する。ここで、サーバ１００，３００から同時に、サーバ２００宛のパケット２１，２２が送信された場合を想定する。２台のサーバ１００，３００から送信されたパケット２１，２２は、それぞれネットワークスイッチ５００の入力ポート５１１，５３１に入力される。

図６は、ネットワークスイッチによるパケットの受信状況を示す図である。サーバ１００から送信されたパケット２１は、ネットワークスイッチ５００の入力ポート５１１のバッファに格納される。また、サーバ３００から送信されたパケット２２は、ネットワークスイッチ５００の入力ポート５３１のバッファに格納される。ネットワークスイッチ５００は、パケットの宛先に基づいて、入力されたパケットを送出するポートを判断する。図６の例では、２つのパケット２１，２２共にサーバ２００宛である。そのためネットワークスイッチ５００では、パケット２１，２２を送出するポートとして、サーバ２００が接続された通信ポート５２０が選択される。この場合、１つの入力ポートが出力ポート５２２の使用権を獲得する。そして、ネットワークスイッチ５００は、使用権を獲得した入力ポートのバッファに格納されたパケットを、出力ポート５２２に転送する。

図７は、ネットワークスイッチにおけるＨＯＬブロッキング発生状態を示す図である。図７の例では、入力ポート５１１が使用権を獲得し、パケット２１が出力ポート５２２に転送されている。出力ポート５２２が空くまでは入力ポート５３１からのパケット２２の転送はできない。そこで、入力ポート５３１に格納されているパケット２２は、ネットワークスイッチ５００によってブロックされる。このように、出力ポートの競合によってパケットの転送がブロックされる現象が、ＨＯＬブロッキングである。

このようなＨＯＬブロッキングの発生を抑制するには、出力ポートの競合の発生を抑制することが重要である。そこで第２の実施の形態では、出力ポートの競合の発生が抑制されるアルゴリズムによって、各サーバ１００，２００，３００，４００における全対全のプロセス間通信を実行する際のデータの送受信相手を順次決定する。以下、第２の実施の形態におけるデータの送受信相手の決定アルゴリズムを、「2-Level Ringアルゴリズム」と称する。

以下、2-Level Ringアルゴリズムを実現するための各サーバ１００，２００，３００，４００の機能について説明する。
図８は、サーバの機能を示すブロック図である。サーバ１００は、プロセス１３１，１３２、プロセス１３１，１３２ごとの送信用バッファ１４１，１５１、プロセス１３１，１３２ごとの受信用バッファ１４２，１５２、およびプロセス間通信制御部１６０を有する。

プロセス１３１，１３２は、クラスタシステムにおける並列演算用にプロセッサコア１１１，１１２で実行される。プロセス１３１，１３２は、計算処理実行用に設けられたプログラムをプロセッサコア１１１，１１２が実行することで、サーバ１００内に生成される。

プロセス１３１には、送信用バッファ１４１と受信用バッファ１４２とが関連付けられている。送信用バッファ１４１は、プロセス１３１が、次の演算ステップに引き渡すデータの格納用の記憶機能である。例えばＲＡＭ１０２の記憶領域の一部が、送信用バッファ１４１として使用される。送信用バッファ１４１には、プロセス１３１自身が次の演算ステップで使用するデータと、他のプロセスが次の演算ステップで使用するデータとが含まれる。

受信用バッファ１４２は、プロセス１３１による次の演算ステップの実行に使用するデータの格納用の記憶領域である。例えばＲＡＭ１０２の記憶領域の一部が、受信用バッファ１４２として使用される。受信用バッファ１４２には、プロセス１３１自身の演算により生成されたデータと、他のプロセスの演算により生成されたデータとが含まれる。

プロセス１３１と同様に、プロセス１３２にも送信用バッファ１５１と受信用バッファ１５２とが関連付けられている。送信用バッファ１５１の機能は、送信用バッファ１４１と同じである。受信用バッファ１５２の機能は、受信用バッファ１４２と同じである。

プロセス間通信制御部１６０は、プロセス間で受け渡されるデータの転送を制御する。具体的には、プロセス間通信制御部１６０は、送信用バッファ１４１，１５１内のデータを、サーバ１００，２００，３００，４００内のいずれかのプロセス宛に転送する。他のサーバ２００，３００，４００上で実行されるプロセス宛にデータを送信する場合、プロセス間通信制御部１６０は、送信対象のデータを含むパケットを生成し、ネットワークスイッチ５００経由でパケットを送信する。

また、プロセス間通信制御部１６０は、サーバ１００，２００，３００，４００内のいずれかのプロセスの実行により送信されたデータを、受信用バッファ１４２，１５２に格納する。なおプロセス間通信制御部１６０は、他のサーバ２００，３００，４００内のプロセスの実行により送信されたデータは、ネットワークスイッチ５００経由で入力されたパケットから取得する。

このような機能のサーバ１００において、例えばプロセス１３１が全対全通信を実行する場合、プロセス１３１を実行するプロセッサコア１１１によりプロセス間通信制御部１６０に対して、全対全通信要求が出力される。全対全通信要求の出力は、例えばＭＰＩでは関数”MPI＿Alltoall()”の呼び出し処理である。プロセス間通信制御部１６０では、全対全通信要求に応答して、「2-Level Ringアルゴリズム」によるプロセス１３１と他のプロセスとの間のデータ通信を実行する。

図９は、プロセス間通信制御部の全対全通信機能を示すブロック図である。プロセス間通信制御部１６０は、全対全通信要求に応答して、全対全通信要求を出力したプロセス用の全対全通信部１６０ａ，１６０ｂを起動する。以下、プロセス１３１の実行により出力された全対全通信要求に応じた全対全通信について、詳細に説明する。

なお、プロセス１３１を実行するプロセッサコア１１１は、全対全通信要求を出力する前に、予め送信データを送信用バッファ１４１に格納しておく。具体的には、送信用バッファ１４１は、クラスタシステムで計算処理を実行している各プロセスのプロセスＩＤに対応する記憶領域が設けられている。プロセス１３１を実行するプロセッサコア１１１は、各プロセスに引き渡すデータを、データの送信相手のプロセスＩＤに対応する記憶領域に格納する。なお、プロセス１３１を実行するプロセッサコア１１１は、プロセス１３１自身が次の演算ステップで使用するデータについても、自己のプロセスＩＤに対応する記憶領域に格納する。プロセス１３１を実行するプロセッサコア１１１は、送信用バッファ１４１への各プロセス宛のデータの格納が完了した後、プロセス間通信制御部１６０に対して全対全通信要求を出力する（計算処理中に使用していたバッファをそのまま送信用バッファとすることもある）。

プロセス間通信制御部１６０は、全対全通信要求に応じて、全対全通信部１６０ａを起動する。例えば全対全通信部１６０ａは、プロセス１３１を実行しているプロセッサコア１１１が全対全通信用のプログラムを実行することで実現される。

全対全通信部１６０ａは、全対全通信用のアルゴリズム（2-Level Ringアルゴリズム）に基づくデータ通信を実行する。そのために全対全通信部１６０ａは、受信元・送信先サーバ決定部１６１、受信元・送信先プロセス決定部１６２、データ送信部１６３、およびデータ受信部１６４を有する。

受信元・送信先サーバ決定部１６１は、全対全通信要求が出されると、データの受信元となるサーバ（受信元サーバ）とデータの送信先となるサーバ（送信先サーバ）との組を順次決定する。受信元・送信先サーバ決定部１６１は、決定した受信元サーバと送信先サーバとの組を、受信元・送信先プロセス決定部１６２に通知する。例えば受信元・送信先サーバ決定部１６１は、受信元サーバと送信先サーバとを示す各変数に、決定した受信元サーバと送信先サーバとのサーバＩＤを設定する。受信元サーバと送信先サーバとを示す各変数の内容を受信元・送信先プロセス決定部１６２が読み取ることで、決定した受信元サーバと送信先サーバとの組が受信元・送信先プロセス決定部１６２に通知される。

受信元・送信先サーバ決定部１６１は、決定した受信元サーバと送信先サーバとの間のデータの送受信の完了通知を受信元・送信先プロセス決定部１６２から受け取ると、次の受信元サーバと送信先サーバとの組を決定する。受信元サーバと送信先サーバとの組の決定は、送信用バッファ１４１内のすべてのデータの送信および受信用バッファ１４２へのすべてのプロセスからのデータの受信が完了するまで繰り返される。受信元・送信先サーバ決定部１６１は、送信用バッファ１４１内のすべてのデータの送信および受信用バッファ１４２へのすべてのプロセスに関するデータの受信が完了すると、全対全通信の完了がプロセス１３１を実行するプロセッサコア１１１に通知される。

受信元サーバと送信先サーバとの組の決定順は、クラスタシステムで計算処理を行うすべてのプロセスの全対全通信が発生した場合に、１台のサーバを送信先サーバとするプロセスが、異なるサーバ上に存在しないように決定される。例えば受信元・送信先サーバ決定部１６１は、2-Level Ringアルゴリズムに従って受信元サーバと送信先サーバとを順番に決定する。

2-Level Ringアルゴリズムにおけるサーバ決定部分では、受信元・送信先サーバ決定部１６１は、１回目の決定では、受信元サーバおよび送信先サーバとして、自己のサーバ１００のサーバＩＤを決定する。受信元・送信先サーバ決定部１６１は、２回目以降の決定では、直前に決定した受信元サーバのサーバＩＤから「１」を減算した値をサーバＩＤとするサーバを、次の受信元サーバとして決定する。ただし受信元・送信先サーバ決定部１６１は、直前に決定した受信元サーバのサーバＩＤが「０」であれば、サーバＩＤが最大値のサーバを、次の受信元サーバとして決定する。また、受信元・送信先サーバ決定部１６１は、直前に決定した送信先サーバのサーバＩＤに「１」を加算した値をサーバＩＤとするサーバを、次の送信先サーバとして決定する。ただし受信元・送信先サーバ決定部１６１は、直前に決定した送信先サーバのサーバＩＤがサーバＩＤの最大値であれば、サーバＩＤが「０」のサーバを、次の送信先サーバとして決定する。

受信元・送信先プロセス決定部１６２は、受信元・送信先サーバ決定部１６１で決定された受信元サーバと送信先サーバとの組に基づいて、データの受信元となるプロセス（受信元プロセス）とデータの送信先となるプロセス（受信先プロセス）との組を決定する。このとき受信元プロセスは、受信元サーバ内のプロセスから決定される。また送信先プロセスは、送信先サーバ内のプロセスから決定される。受信元・送信先プロセス決定部１６２は、決定した受信元プロセスをデータ受信部１６４に通知する。また受信元・送信先プロセス決定部１６２は、決定した送信先プロセスをデータ送信部１６３に通知する。例えば受信元・送信先プロセス決定部１６２は、受信元プロセスと送信先プロセスとを示す各変数に、決定した受信元プロセスと送信先プロセスとのプロセスＩＤを設定する。受信元プロセスを示す変数の内容をデータ受信部１６４が読み取ることで、決定した受信元プロセスがデータ受信部１６４に通知される。また送信先プロセスを示す変数の内容をデータ送信部１６３が読み取ることで、決定した送信先プロセスがデータ送信部１６３に通知される。

受信元・送信先プロセス決定部１６２は、決定した受信元プロセスと送信先プロセスとの間のデータの送受信の完了通知をデータ送信部１６３およびデータ受信部１６４から受け取ると、次の受信元プロセスと送信先プロセスとの組を決定する。受信元プロセスと送信先プロセスとの組の決定は、受信元・送信先プロセス決定部１６２で決定された受信元サーバ内の各プロセスからのデータ受信と、送信先サーバ内の各プロセスへのデータ送信が完了するまで繰り返される。受信元・送信先プロセス決定部１６２は、決定された受信元サーバ内の各プロセスからのデータ受信と、決定された送信先サーバ内の各プロセスへのデータ送信が完了すると、完了したことを受信元・送信先サーバ決定部１６１に通知する。

受信元プロセスの決定順は、サーバ１００内の複数のプロセスの全対全通信が発生した場合に、サーバ１００内の複数のプロセスが、１つのプロセスを同時に受信元としないように決定される。また送信先プロセスの決定順は、サーバ１００内の複数のプロセスから１つのプロセスを同時に送信先としないように決定される。例えば受信元・送信先プロセス決定部１６２は、2-Level Ringアルゴリズムに従って受信元プロセスと送信先プロセスとを順番に決定する。

2-Level Ringアルゴリズムにおける１回目のプロセス決定では、受信元・送信先プロセス決定部１６２は、受信元・送信先プロセスとして、全対全通信要求を出力したプロセス１３１とローカルプロセスＩＤが同じプロセスを決定する。受信元・送信先プロセス決定部１６２は、２回目以降の決定では、直前に決定した受信元プロセスのプロセスＩＤから「１」を減算した値をプロセスＩＤとするプロセスを、次の受信元プロセスとして決定する。ただし受信元・送信先プロセス決定部１６２は、直前に決定した受信元プロセスのプロセスＩＤが「０」であれば、プロセスＩＤが最大値のプロセスを、次の受信元プロセスとして決定する。また、受信元・送信先プロセス決定部１６２は、直前に決定した送信先プロセスのプロセスＩＤに「１」を加算した値をプロセスＩＤとするプロセスを、次の送信先プロセスとして決定する。ただし受信元・送信先プロセス決定部１６２は、直前に決定した送信先プロセスのプロセスＩＤがプロセスＩＤの最大値であれば、プロセスＩＤが「０」のプロセスを、次の送信先プロセスとして決定する。

データ送信部１６３は、受信元・送信先プロセス決定部１６２で決定された送信先プロセスを実行するプロセッサコアに対してデータを送信する。具体的には、データ送信部１６３は、決定された送信先プロセスのプロセスＩＤに対応するデータを、送信用バッファ１４１から読み出す。次に、データ送信部１６３は、送信先プロセスのプロセスＩＤに基づいて、送信先プロセスが動作しているサーバを判断する。第２の実施の形態では、プロセスＩＤをローカルプロセス数で除算した商が、そのプロセスＩＤで示されるプロセスが動作しているサーバのサーバＩＤとなる。

データ送信部１６３は、送信先プロセスが他のサーバで動作していれば、送信先プロセスが実行されるサーバを宛先としたメッセージを生成する。データ送信部１６３は、ネットワークの伝送プロトコルに従って、生成したメッセージを伝送するパケットを生成する。生成されたパケットには、送信先プロセスに送信すべきデータが含まれる。データ送信部１６３は、生成したパケットを、ネットワークスイッチ５００に対して出力する。すると、ネットワークスイッチ５００により、宛先となるサーバへパケットが転送される。

また送信先プロセスが、データを送信するプロセス１３１自身であれば、データ送信部１６３は、データ受信部１６４にデータを渡す。さらに送信先プロセスがサーバ１００内の別のプロセス１３２であれば、データ送信部１６３は、プロセス１３２用の全対全通信部１６０ｂにデータを渡す。

データ送信部１６３は、送信先プロセスに対応するデータの送信が完了すると、送信完了を受信元・送信先プロセス決定部１６２に通知する。
データ受信部１６４は、受信元・送信先プロセス決定部１６２で決定された受信元プロセスから出力されたデータを受信する。具体的には、データ受信部１６４は、受信元プロセスのプロセスＩＤに基づいて、受信元プロセスが動作しているサーバを判断する。そしてデータ受信部１６４は、受信元プロセスが動作しているサーバから、受信元プロセスが送信したデータが入力されるのを待つ。データが入力されると、データ受信部１６４は入力されたデータを、受信用バッファ１４２内の受信元プロセスのプロセスＩＤに対応する記憶領域に格納する。

データ受信部１６４は、受信元プロセスが他のサーバで動作していれば、受信元プロセスが実行されるサーバから、受信元プロセスが出力したデータを含むパケットを受信する。この際、データ受信部１６４は、ネットワークを経由して受信するメッセージを一時的に蓄えるメッセージバッファ領域内に、受信元プロセスから出力されたデータを含むメッセージを格納する領域を確保しておく。受信元プロセスから送信されたデータを含むパケットが送信元サーバから入力されると、データ受信部１６４は、パケットを解析してメッセージを生成し、そのメッセージを予め確保しておいたメッセージバッファ領域に格納する。そしてデータ受信部１６４は、メッセージバッファ領域に格納したメッセージからデータ抽出し、受信用バッファ１４２内の受信元プロセスのプロセスＩＤに対応する記憶領域に格納する。

また受信元プロセスが、データを受信するプロセス１３１自身であれば、データ受信部１６４は、データ送信部１６３からデータを取得する。さらに受信元プロセスがサーバ１００内の別のプロセス１３２であれば、データ受信部１６４は、プロセス１３２用の全対全通信部１６０ｂからデータを取得する。

なお、プロセス１３２用の全対全通信部１６０ｂについても、全対全通信部１６０ａと同様の機能を有している。
また、図１に示した第１の実施の形態の機能のうち、全対全通信手段４−１，４−２，４−３，・・・の機能は、図９に示した第２の実施の形態に係るサーバ１００では、全対全通信部１６０ａで実現されている。具体的には、送信先サーバ決定手段４ａと受信元サーバ決定手段４ｄの機能は、受信元・送信先サーバ決定部１６１で実現されている。送信先プロセス決定手段４ｂと受信元プロセス決定手段４ｅの機能は、受信元・送信先プロセス決定部１６２で実現されている。データ送信手段４ｃの機能は、データ送信部１６３で実現されている。データ受信手段４ｆの機能は、データ受信部１６４で実現されている。

次に、プロセス間通信制御部１６０によって実行される全対全通信処理の手順を説明する。
図１０は、全対全通信処理の手順を示すフローチャートである。以下、図１０に示す処理をステップ番号に沿って説明する。

〔ステップＳ１１〕プロセス間通信制御部１６０は、プロセス１３１，１３２を実行するプロセッサコア１１１，１１２から全対全通信要求が出力されたか否かを判断する。全対全通信要求が出力された場合、処理がステップＳ１２に進められる。全対全通信要求が出力されていなければ、ステップＳ１１の処理が繰り返され、全対全通信要求が出力されるのを待つ。

〔ステップＳ１２〕プロセス間通信制御部１６０は、全対全通信要求を出力したプロセスの全対全通信を行う全対全通信部を起動する。ここでは、プロセス１３１から全対全通信要求が出力されたものとする。この場合、全対全通信部１６０ａが起動される。起動された全対全通信部１６０ａでは、受信元・送信先サーバ決定部１６１が、受信元サーバと送信先サーバとの組を、2-Level Ringアルゴリズムに従って順次決定する。受信元・送信先サーバ決定部１６１は、受信元サーバと送信先サーバとの組を決定するごとに、決定結果を受信元・送信先プロセス決定部１６２に通知する。

〔ステップＳ１３〕受信元・送信先プロセス決定部１６２は、受信元・送信先サーバ決定部１６１で決定された受信元サーバと送信先サーバとの組を受け取ると、受信元プロセスと送信先プロセスとの組を、2-Level Ringアルゴリズムに従って順次決定する。このとき決定される受信元プロセスは、受信元サーバ内のプロセスである。受信元・送信先プロセス決定部１６２は、決定した送信先プロセスのプロセスＩＤを、データ送信部１６３に通知する。また受信元・送信先プロセス決定部１６２は、決定した受信元プロセスのプロセスＩＤを、データ受信部１６４に通知する。

〔ステップＳ１４〕データ送信部１６３とデータ受信部１６４とがプロセス間通信を実行する。すなわちデータ送信部１６３は、決定された送信先プロセスのプロセスＩＤに対応するデータを送信用バッファ１４１から取得し、決定された送信先プロセスに対して送信する。データ送信部１６３は、データの送信が完了すると、送信が完了したことを受信元・送信先プロセス決定部１６２に通知する。またデータ受信部１６４は、決定された受信元プロセスのデータを受信し、決定された受信元プロセスのプロセスＩＤに対応する受信用バッファ１４２内の記憶領域に、受信したデータを格納する。データ受信部１６４は、データの受信が完了すると、受信が完了したことを受信元・送信先プロセス決定部１６２に通知する。

〔ステップＳ１５〕受信元・送信先プロセス決定部１６２は、データ送信部１６３とデータ受信部１６４とによる通信が完了したか否かを判断する。具体的には、受信元・送信先プロセス決定部１６２は、データ送信部１６３から送信完了の通知を受け取り、かつデータ受信部１６４から受信完了の通知を受け取った場合に、通信完了と判断する。通信が完了すると、処理がステップＳ１６に進められる。通信が完了していなければステップＳ１５の処理が繰り返される。

〔ステップＳ１６〕受信元・送信先プロセス決定部１６２は、決定した受信元プロセスと送信先プロセスとの間の通信が完了すると、決定されている受信元サーバと送信先サーバのすべてのプロセスとの間での通信が完了したか否かを判断する。具体的には、受信元サーバ内の各プロセスからのデータの受信が完了し、送信先サーバ内の各プロセスに対するデータの送信が完了している場合に、受信元・送信先サーバの全プロセスとの通信完了と判断される。受信元・送信先サーバの全プロセスとの通信が完了すると、処理がステップＳ１７に進められる。受信元・送信先サーバのプロセスのうち通信を行っていないプロセスがあれば処理がステップＳ１３に進められ、未通信のプロセスが受信元・送信先プロセスとして決定される。

〔ステップＳ１７〕受信元・送信先サーバの全プロセスとの通信が完了すると、受信元・送信先サーバ決定部１６１は、クラスタシステムを構成するすべてのサーバとの通信が完了したか否かを判断する。すべてのサーバとの間で、データの送信および受信それぞれの通信が完了していれば、全対全通信処理が終了する。未通信のサーバがあれば、処理がステップＳ１２に進められ、未通信のサーバが受信元・送信先サーバとして決定される。

このような手順で2-Level Ringアルゴリズムによる全対全通信が実行される。全対全通信は、例えば関数”MPI＿Alltoall()”によって呼び出すことができる。この場合、2-Level Ringアルゴリズムにより受信元・送信先プロセスを決定する処理記述を呼び出す関数が予め定義される。その場合、全対全通信要求として関数の呼び出しが行われる。関数が呼び出されると、関数に対応する処理記述に基づく処理が実行される。

図１１は、第２の実施の形態における2-Level Ringアルゴリズムによるプロセス決定を行う処理記述例を示す図である。図１１に示すように、2-Level Ringアルゴリズムは、例えばfor文で処理を記述することができる。ここで、図１１中の各変数には、以下の情報が設定される（”：”の左が変数名、”：”の右が設定される内容）。
Ｎｓ：サーバ数
Ｎｌ：ローカルプロセス数（サーバ１台当たりのプロセス数）
Ｎｐ：総プロセス数（Ｎｐ＝Ｎｓ×Ｎｌ）
Ｉｓ：自サーバＩＤ（０≦Ｉｓ＜Ｎｓ）
Ｉｌ：自ローカルプロセスＩＤ（０≦Ｉｌ＜Ｎｌ）
Ｉｐ：自プロセスＩＤ（Ｉｐ＝Ｉｓ×Ｎｌ＋Ｉｌ）
Ｉｓ＿ｓｒｃ：受信元サーバＩＤ
Ｉｓ＿ｄｓｔ：送信先サーバＩＤ
Ｉｐ＿ｓｒｃ：受信元プロセスＩＤ
Ｉｐ＿ｄｓｔ：送信先プロセスＩＤ
処理記述の１行目から３行目には、受信元サーバと送信先サーバとを決定する手順が記述されている。

１行目には、for文による繰り返し処理が定義されている。変数ｓには初期値として「０」が設定される。変数ｓは、for文内の処理が１回繰り返されるごとに、インクリメントされる（Ｓ＋＋）。そして、変数ｓの値がサーバ数（Ｎｓ）未満の間、２行目から７行目の処理が繰り返される。

２行目には、受信元サーバを決定する式が定義されている。自サーバＩＤ（Ｉｓ）に対し、変数ｓの値を減算されると共にサーバ数（Ｎｓ）が加算される。その加減算の結果をサーバ数（Ｎｓ）で除算した余りが、受信元サーバＩＤ（Ｉｓ＿ｓｒｃ）に設定される。

３行目には、送信先サーバを決定する式が定義されている。自サーバＩＤ（Ｉｓ）に対し、変数ｓの値とサーバ数（Ｎｓ）とを加算する。その加算の結果をサーバ数（Ｎｓ）で除算した余りが、送信先サーバＩＤ（Ｉｓ＿ｄｓｔ）に設定される。

処理記述の４行目から６行目には、受信元プロセスと送信先プロセスとを決定する手順が記述されている。なお、４行目から６行目の処理は、１行目のfor文内の処理の一部である。

４行目には、for文による繰り返し処理が定義されている。変数ｌには初期値として「０」が設定される。変数ｌは、for文内の処理が１回繰り返されるごとに、インクリメントされる（ｌ＋＋）。そして、変数ｌの値がローカルプロセス数（Ｎｌ）未満の間、５行目〜７行目の処理が繰り返される。

５行目には、受信元プロセスを決定する式が定義されている。５行目に定義された式では、受信元サーバＩＤ（Ｉｓ＿ｓｒｃ）にローカルプロセス数（Ｎｌ）が乗算される。また、自ローカルプロセスＩＤ（Ｉｌ）に対し、変数ｌの値が減算されると共にローカルプロセス数（Ｎｌ）が加算され、加減算の結果がローカルプロセス数（Ｎｌ）で除算される。除算の余りを先の乗算結果に加算した値が、受信元プロセスＩＤ（Ｉｐ＿ｓｒｃ）に設定される。

６行目には、送信先プロセスを決定する式が定義されている。６行目に定義された式では、送信先サーバＩＤ（Ｉｓ＿ｄｓｔ）にローカルプロセス数（Ｎｌ）が乗算される。また、自ローカルプロセスＩＤ（Ｉｌ）に対し、変数ｌの値とローカルプロセス数（Ｎｌ）とが加算され、加算の結果がローカルプロセス数（Ｎｌ）で除算される。除算の余りを先の乗算結果に加算した値が、送信先プロセスＩＤ（Ｉｓ＿ｄｓｔ）に設定される。

７行目には、通信処理を実行する関数呼び出しが定義されている。通信処理の関数呼び出しでは、データの受信元として受信元プロセスＩＤ（Ｉｐ＿ｓｒｃ）が指定され、データの送信先として送信先プロセスＩＤ（Ｉｓ＿ｄｓｔ）が指定される。

このような処理記述に従って処理が実行されることで、2-Level Ringアルゴリズムによるプロセスを行った全対全通信が実行される。2-Level Ringアルゴリズムを用いる全対全通信を行うことで、ＨＯＬブロッキングの発生が抑制される。以下、Ringアルゴリズムと比較して、2-Level Ringアルゴリズムの優位性について説明する。

まず、図１２、図１３を参照して、Ringアルゴリズムによる全対全通信を行った場合のプロセス間通信の状態遷移について示す図である。
図１２は、Ringアルゴリズムによるプロセス間通信の状態遷移を示す第１の図である。なお図１２では、サーバ１００，２００，３００，４００を矩形で表し、各サーバ１００，２００，３００，４００内で実行されるプロセスを円形で表している。各プロセスを示す円形内には、プロセスＩＤが示されている。

Ringアルゴリズムでは、データの送信先とするプロセスのプロセスＩＤが環状に並べられる。例えばプロセスＩＤが昇順で並べられ、値が最大のプロセスＩＤ「７」の次は、値が最小のプロセスＩＤ「０」であるものと定義される。図１２の例では、プロセスが、プロセスＩＤの順に時計回りに配置されている。そこで、以下の説明では、受信元プロセスおよび送信先プロセスを、全対全通信要求を出力したプロセスからの図１２上での相対位置によって示す。

図１２に示すように８つのプロセスそれぞれに対応するプロセスＩＤが環状に並べられているものとし、Ringアルゴリズムによる全対全通信を行うと、すべての通信を完了するのに８ステップ要する。図１２には、ステップ番号０〜３のステップの通信状態が示されている。

ステップ番号０のステップ（Ｓｔｅｐ＝０）では、全対全通信要求を出力したプロセス自身が、受信元プロセスおよび送信先プロセスとなる。
ステップ番号１のステップ（Ｓｔｅｐ＝１）では、全対全通信要求を出力したプロセスのプロセスＩＤから反時計回りに１個ずれた位置のプロセスＩＤに対応するプロセスが、受信元プロセスとされる。また、全対全通信要求を出力したプロセスのプロセスＩＤから時計回りに１個ずれた位置のプロセスＩＤに対応するプロセスが、送信先プロセスとされる。

ステップ番号２のステップ（Ｓｔｅｐ＝２）では、全対全通信要求を出力したプロセスから反時計回りに２個ずれた位置のプロセスが、受信元プロセスとされる。また、全対全通信要求を出力したプロセスから時計回りに２個ずれた位置のプロセスが、送信先プロセスとされる。

ステップ番号３のステップ（Ｓｔｅｐ＝３）では、全対全通信要求を出力したプロセスから反時計回りに３個ずれた位置のプロセスが、受信元プロセスとされる。また、全対全通信要求を出力したプロセスから時計回りに３個ずれた位置のプロセスが、送信先プロセスとされる。

図１３は、Ringアルゴリズムによるプロセス間通信の状態遷移を示す第２の図である。図１３には、ステップ番号４〜７のステップの通信状態が示されている。
ステップ番号４のステップ（Ｓｔｅｐ＝４）では、全対全通信要求を出力したプロセスから反時計回りに４個ずれた位置のプロセスが、受信元プロセスとされる。また、全対全通信要求を出力したプロセスから時計回りに４個ずれた位置のプロセスが、送信先プロセスとされる。

ステップ番号５のステップ（Ｓｔｅｐ＝５）では、全対全通信要求を出力したプロセスから反時計回りに５個ずれた位置のプロセスが、受信元プロセスとされる。また、全対全通信要求を出力したプロセスから時計回りに５個ずれた位置のプロセスが、送信先プロセスとされる。

ステップ番号６のステップ（Ｓｔｅｐ＝６）では、全対全通信要求を出力したプロセスから反時計回りに６個ずれた位置のプロセスが、受信元プロセスとされる。また、全対全通信要求を出力したプロセスから時計回りに６個ずれた位置のプロセスが、送信先プロセスとされる。

ステップ番号７のステップ（Ｓｔｅｐ＝７）では、全対全通信要求を出力したプロセスから反時計回りに７個ずれた位置のプロセスが、受信元プロセスとされる。また、全対全通信要求を出力したプロセスから時計回りに７個ずれた位置のプロセスが、送信先プロセスとされる。

図１２、図１３に示した例では、サーバ１台当たりのプロセス数は２である。このように、１台のサーバで複数のプロセスが動作している状況でRingアルゴリズムによる全対全通信を行うと、４番目のステップ（Ｓｔｅｐ＝３）と６番目のステップ（Ｓｔｅｐ＝５）とのそれぞれの通信において、出力ポート使用の競合が発生する。なお図１２、図１３の４番目のステップ（Ｓｔｅｐ＝３）と６番目のステップ（Ｓｔｅｐ＝５）とでは、競合する通信同士を同じ線種（実線、破線、点線、一点鎖線）で表している。

図１４は、４番目のステップ（Ｓｔｅｐ＝３）における競合の発生状況を示す図である。図１４では、プロセス間で受け渡すデータを送信するプロセスと受信するプロセスへのデータの転送経路を線で示している。競合する通信の転送経路は、互いに同じ線種（実線、破線、点線、一点鎖線）で表されている。

ネットワークスイッチ５００内では、各出力ポート５１２，５２２，５３２，５４２に対して、異なる入力ポートからパケットが同時に転送される場合、出力ポートにおいて競合が発生する。例えば、サーバ１００内のプロセスＩＤ「１」のプロセスを実行するプロセッサコアから、サーバ３００内のプロセスＩＤ「４」のプロセスへデータ転送が行われている。またサーバ２００内のプロセスＩＤ「２」のプロセスを実行するプロセッサコアから、サーバ３００内のプロセスＩＤ「４」のプロセスへデータ転送が行われている。この２つのデータ転送は、サーバ３００に接続された通信ポート５３０の出力ポート５３２を経由する。このとき、データの受信元となるプロセスが異なるサーバ上に存在する。そのため出力ポート５３２の使用権を獲得の競合が発生する可能性がある。

図１４の例では、すべての出力ポート５１２，５２２，５３２，５４２で競合が発生する可能性がある。競合が発生すると、同じ出力ポートへパケットを転送しようとする入力ポートの一方のみが先に出力ポートの使用権を獲得する。使用権を獲得できなかった入力ポートではＨＯＬブロッキングが発生する。

図１２〜図１４に示した例では、理解しやすくするために総プロセス数を８としているが、実際のクラスタシステムでは、プロセス数はもっと多数であることが多い。実際に、総プロセス数１２８のクラスタシステム上にて、Ringアルゴリズムの各通信ステップの実行時間を測定した。

図１５は、Ringアルゴリズムの各通信ステップの実行時間を示す図である。図１５には、総プロセス数１２８（サーバ数１６×ローカルプロセス数８）のクラスタシステム上にて、Ringアルゴリズムの各通信ステップの通信の実行時間を測定した結果が示されている。サーバには、８コアのＩＡサーバを使用した。通信には、ＤＤＲ（Double Data Rate）のInfiniBandに準拠した機器を使用した。プロセス間送受信のデータサイズは、１ＭＢとした。

図１５中の横軸には、通信のステップ番号が示されている。縦軸には、通信ステップ番号が８の倍数（ステップ番号「０」を除く）のときの通信の実行時間で正規化した、通信の通信時間が示されている。すなわち、通信ステップ番号が８の倍数のときの通信の実行時間を単位時間（１．０）とし、他のステップの通信の実行時間が、単位時間の何倍になるのかが示されている。

通信ステップ番号が８の倍数のときの通信の実行時間を基準としているのは、通信ステップ番号がローカルプロセス数８の倍数のときには、出力ポート使用の競合およびＨＯＬブロッキングが発生しないと考えられるためである。すなわち、通信ステップ番号がローカルプロセス数８の倍数のときは、各サーバ内の各プロセスが共通のサーバに対してデータが送信される。そうすると、各サーバから送信されるパケットの送信先となるサーバが異なるため、出力ポート使用の競合およびＨＯＬブロッキングが発生しない。例えば、図１２、図１３に示した例では、ローカルプロセス数が「２」である。ステップ番号が２の倍数となる２，４，６の各ステップでは、出力ポート使用の競合およびＨＯＬブロッキングは発生していない。

図１５を参照すると分かるように、通信ステップ番号がローカルプロセス数の倍数でないときには、実行時間が長くなっている。これはネットワークスイッチ５００内で出力ポート使用の競合によりＨＯＬブロッキングが発生しているためであると考えられる。すなわち、ＨＯＬブロッキングの発生により、通信効率が低下しているのが分かる。

なお図１５の例において、ステップ番号が７以下、１２１以上の通信の実行時間は、通信ステップ番号が８の倍数のときの通信の実行時間よりも短い。これはステップ番号が７以下、１２１以上の通信では、同じサーバ内でのプロセス間の通信が存在し、ネットワークスイッチを経由したプロセス間通信が他のステップよりも少ないためである。

このように、Ringアルゴリズムによる全対全通信は、マルチコアのプロセッサを実装したサーバで構成されるクラスタシステムにとって適切なアルゴリズムではない。
次に、図１６、図１７を参照して、2-Level Ringアルゴリズムによるプロセス間通信状況の遷移を説明する。

図１６は、2-Level Ringアルゴリズムによるプロセス間通信の状態遷移を示す第１の図である。なお図１６では、サーバ１００，２００，３００，４００を矩形で表し、各サーバ１００，２００，３００，４００内で実行されるプロセスを円形で表している。各プロセスを示す円形内には、そのプロセスのプロセスＩＤが示されている。また、各プロセスを示す円形の左上に、そのプロセスのローカルプロセスＩＤが示されている。

2-Level Ringアルゴリズムでは、各サーバのサーバＩＤが環状に並べられる。例えばサーバＩＤが昇順で並べられ、値が最大のサーバＩＤ「３」の次は、値が最小のサーバＩＤ「０」であるものと定義される。図１６の例では、サーバが、サーバＩＤの順に時計回りに配置されている。そこで、以下の説明では、受信元サーバおよび送信先サーバを、全対全通信要求を出力したプロセスが実行されているサーバからの図１６上での相対位置によって示す。

また、2-Level Ringアルゴリズムでは、データの送信先とするプロセスのローカルプロセスＩＤが、サーバごとに環状に並べられる。例えばローカルプロセスＩＤが昇順で並べられ、値が最大のローカルプロセスＩＤ「１」の次は、値が最小のローカルプロセスＩＤ「０」であるものと定義される。

図１６に示すように４つのサーバおよび８つのプロセスが環状に並べられているものとし、2-Level Ringアルゴリズムによる全対全通信を行うと、すべての通信を完了するのに８ステップ要する。図１２には、ステップ番号０〜３のステップの通信状態が示されている。

ステップ番号０のステップ（Ｓｔｅｐ＝０）では、全対全通信要求を出力したプロセス自身が、受信元プロセスおよび送信先プロセスとなる。
ステップ番号１のステップ（Ｓｔｅｐ＝１）では、全対全通信要求を出力したプロセスが動作しているサーバ内の他のプロセスが、受信元プロセスおよび送信先プロセスとされる。

ステップ番号２のステップ（Ｓｔｅｐ＝２）では、全対全通信要求を出力したプロセスが動作しているサーバから反時計回りに１個ずれた位置のサーバが、受信元サーバとなる。また全対全通信要求を出力したプロセスが動作しているサーバから時計回りに１個ずれた位置のサーバが、送信先サーバとなる。さらに全対全通信要求を出力したプロセスと同じローカルプロセスＩＤを有する受信元サーバ内のプロセスが、受信元プロセスとなる。そして、全対全通信要求を出力したプロセスと同じローカルプロセスＩＤを有する送信先サーバ内のプロセスが、送信先プロセスとなる。

ステップ番号３のステップ（Ｓｔｅｐ＝３）では、受信元サーバと送信先サーバとは、ステップ番号２のステップと同じである。また全対全通信要求を出力したプロセスと同じローカルプロセスＩＤを有する受信元サーバ内のプロセスの次の順のプロセスが、受信元プロセスとなる。そして、全対全通信要求を出力したプロセスと同じローカルプロセスＩＤを有する送信先サーバ内のプロセスの次の順のプロセスが、送信先プロセスとなる。

図１７は、2-Level Ringアルゴリズムによるプロセス間通信の状態遷移を示す第２の図である。図１７には、ステップ番号４〜７のステップの通信状態が示されている。
ステップ番号４のステップ（Ｓｔｅｐ＝４）では、全対全通信要求を出力したプロセスが動作しているサーバから反時計回りに２個ずれた位置のサーバが、受信元サーバとなる。また全対全通信要求を出力したプロセスが動作しているサーバから時計回りに２個ずれた位置のサーバが、送信先サーバとなる。さらに全対全通信要求を出力したプロセスのローカルプロセスＩＤと同じローカルプロセスＩＤの受信元サーバ内のプロセスが、受信元プロセスとなる。そして、全対全通信要求を出力したプロセスのローカルプロセスＩＤと同じローカルプロセスＩＤの送信先サーバ内のプロセスが、送信先プロセスとなる。

ステップ番号５のステップ（Ｓｔｅｐ＝５）では、受信元サーバと送信先サーバとは、ステップ番号４のステップと同じである。また全対全通信要求を出力したプロセスと同じローカルプロセスＩＤを有する受信元サーバ内のプロセスの次の順のプロセスが、受信元プロセスとなる。そして、全対全通信要求を出力したプロセスと同じローカルプロセスＩＤを有する送信先サーバ内のプロセスの次の順のプロセスが、送信先プロセスとなる。

ステップ番号６のステップ（Ｓｔｅｐ＝６）では、全対全通信要求を出力したプロセスが動作しているサーバから反時計回りに３個ずれた位置のサーバが、受信元サーバとなる。また全対全通信要求を出力したプロセスが動作しているサーバから時計回りに３個ずれた位置のサーバが、送信先サーバとなる。さらに全対全通信要求を出力したプロセスのローカルプロセスＩＤと同じローカルプロセスＩＤの受信元サーバ内のプロセスが、受信元プロセスとなる。そして、全対全通信要求を出力したプロセスのローカルプロセスＩＤと同じローカルプロセスＩＤの送信先サーバ内のプロセスが、送信先プロセスとなる。

ステップ番号７のステップ（Ｓｔｅｐ＝７）では、受信元サーバと送信先サーバとは、ステップ番号６のステップと同じである。また全対全通信要求を出力したプロセスと同じローカルプロセスＩＤを有する受信元サーバ内のプロセスの次の順のプロセスが、受信元プロセスとなる。そして、全対全通信要求を出力したプロセスと同じローカルプロセスＩＤを有する送信先サーバ内のプロセスの次の順のプロセスが、送信先プロセスとなる。

このように2-Level Ringアルゴリズムにより全対全通信を行えば、異なるサーバで実行される複数のプロセスが、同時に１つのサーバにデータ転送を行うことが抑制され、出力ポートの使用の競合の発生が抑制される。その結果、ＨＯＬブロッキングの発生も抑制され、通信の実行時間も短縮される。

図１８は、2-Level RingアルゴリズムとRingアルゴリズムとの実効ネットワークバンド幅の測定結果を示す図である。図１８の例では、サーバには、８コアのＩＡサーバを使用した。通信には、ＤＤＲ（Double Data Rate）のInfiniBandに準拠した機器を使用した。サーバ数は１６とした。プロセス間送受信のデータサイズは、１ＭＢとした。このようなハードウェア構成で、ローカルプロセス数を、１，２，４，８とした場合の全対全通信時の実効ネットワークバンド幅を測定した。実効ネットワークバンド幅の単位は、「ギガバイト（ＧＢ）／秒（ｓ）」である。なおローカルプロセス数を１，２，４とする場合、サーバ内のプロセッサコアの一部だけが計算処理用のプロセスを実行している。

ローカルプロセス数が１の場合、2-Level RingアルゴリズムとRingアルゴリズムとの間に、実効ネットワークバンド幅の有意な差異は見られない。ローカルプロセス数が複数になると、2-Level Ringアルゴリズムの方がRingアルゴリズムよりも実効ネットワークバンド幅が明らかに高くなる。ローカルプロセス数が増えるに従って、2-Level RingアルゴリズムとRingアルゴリズムとの実効ネットワークバンド幅の差が増加する。

図１８では、Ringアルゴリズムによる全対全通信から2-Level Ringアルゴリズムによる全対全通信に通信アルゴリズムを変更した場合の性能向上率を示している。性能向上率は、Ringアルゴリズムの実効ネットワークバンド幅から2-Level Ringアルゴリズムの実効ネットワークバンド幅への増加量を、Ringアルゴリズムの実効ネットワークバンド幅に対する割合（パーセンテージ）で示したものである。図１８に示すように、ローカルプロセス数が増加する程、性能向上率が向上している。

ローカルプロセス数が多いときにRingアルゴリズムにおける実効ネットワークバンド幅が低下するのは、ネットワークスイッチ内でＨＯＬブロッキングが発生するためであるものと考えられる。図１５で示したように、ステップ番号がローカルプロセス数の倍数のときにはＨＯＬブロッキングは発生しないが、それ以外のステップ番号ではＨＯＬブロッキングが発生する可能性がある。実際に、サーバ数が１６、ローカルプロセス数が８、総プロセス数が１２８の場合にRingアルゴリズムの各ステップの実行時間を測定したところ、ステップ番号がローカルプロセス数の倍数でないときには実際に実行時間が長くなっていることが分かる。Ringアルゴリズムは、１台のサーバで複数のプロセスを実行するクラスタシステムにとって適切なアルゴリズムではない。

それに対し、2-Level Ringアルゴリズムでは、全対全通信におけるＨＯＬブロッキングの発生を抑止できる。その結果、図１８に示すように、ローカルプロセス数が増加しても、ネットワークバンド幅の低下を最小限に抑えることが可能となる。

以上説明したように、従来のアルゴリズムは各プロセスがどのサーバのプロセスであるかを考慮しないため、ある通信ステップにおいてネットワークスイッチ内で競合が発生する可能性があった。それに対して、2-Level Ringアルゴリズムは各プロセスがどのサーバのプロセスであるかを考慮したアルゴリズムであり、どの通信ステップにおいても、あるサーバの各プロセスは、同じサーバのプロセスからデータを受信する。その結果、ネットワークスイッチ５００内で出力ポート使用の競合が発生せず、本来の通信性能を得ることができる。総プロセス数１２８（サーバ数１６× ローカルプロセス数８）のクラスタシステムにあれば、2-Level Ringアルゴリズムは、Ringアルゴリズムに対して実効ネットワークバンド幅が２２．５％向上することが確認されている（図１８参照）。

しかも2-Level Ringアルゴリズムでは、送信先プロセスの決定において、複数のプロセスが１つのプロセスを重複して送信先プロセスとしないようにしている。１つのサーバ内でデータを受信するプロセスに偏りがあると、サーバの処理効率が低下する。すなわち、データを受信するプロセスに偏りがあると、データを受信しないプロセスが発生し、そのプロセスを実行しているプロセッサコアの処理能力に余裕が生まれる。処理能力を使い切っていないプロセッサコアが発生するということは、サーバ全対の処理効率の低下を意味する。2-Level Ringアルゴリズムによれば、全対全通信時のサーバ内のプロセッサコア間の処理の均等化が図られるため、サーバの処理効率の低下が防止される。

さらに、第２の実施の形態では、受信元プロセスを決定しておき、受信元プロセスから送られるデータを優先的に受信できるようにしている。すなわち、受信元プロセスから送られるデータを含むメッセージを格納するバッファが用意されるため、受信側のバッファ不足によるそのメッセージの転送の待ちの発生が抑止される。その結果、全対全のプロセス間通信を優先的に効率よく実行可能となる。

〔第３の実施の形態〕
次に第３の実施の形態について説明する。第３の実施の形態は、各サーバのプロセスに対するプロセスＩＤの割当がマッピングテーブルで管理されている場合の2-Level Ringアルゴリズムの例である。

第２の実施の形態では、各プロセスのプロセスＩＤが、そのプロセスが動作しているサーバのサーバＩＤにローカルプロセス数を乗算し、乗算結果にそのプロセスのローカルプロセスＩＤを加算して得られる値である。第２の実施の形態では、このようにプロセスＩＤがサーバＩＤとローカルプロセスＩＤとから規則的に求められることを前提としている。しかし、プロセスＩＤの割当に特別な規則性を持たせず、マッピングテーブルで管理することも可能である。そのような場合、マッピングテーブルを参照して、受信元プロセスおよび送信先プロセスを決定する。

図１９は、第３の実施の形態におけるサーバの機能を示すブロック図である。第３の実施の形態における第２の実施の形態と相違する要素は、受信元・送信先プロセス決定部１６２ａとプロセスＩＤ管理テーブル記憶部１６５である。そこで受信元・送信先プロセス決定部１６２ａとプロセスＩＤ管理テーブル記憶部１６５以外の要素は、図８に示した第２の実施の形態のブロック図と同じ符号を付し、説明を省略する。

第３の実施の形態における受信元・送信先プロセス決定部１６２ａは、受信元プロセスと送信先プロセスとのプロセスＩＤとを決定する処理の詳細が、第２の実施の形態における受信元・送信先プロセス決定部１６２と異なる。受信元・送信先プロセス決定部１６２ａが実行する他の要素との間の各種情報の受け渡し処理については、第２の実施の形態における受信元・送信先プロセス決定部１６２と同様である。

受信元・送信先プロセス決定部１６２ａは、受信元プロセスを決定する際に、まず受信元サーバ内の受信元プロセスとするプロセスのローカルプロセスＩＤを決定する。そして、受信元・送信先プロセス決定部１６２ａは、決定したローカルプロセスＩＤに対応するプロセスＩＤを、プロセスＩＤ管理テーブル記憶部１６５から取得する。受信元・送信先プロセス決定部１６２ａは、取得したプロセスＩＤに対応するプロセスを、受信元プロセスとする。

また、受信元・送信先プロセス決定部１６２ａは、送信先プロセスを決定する際に、まず送信先サーバ内の送信先プロセスとするプロセスのローカルプロセスＩＤを決定する。そして、受信元・送信先プロセス決定部１６２ａは、決定したローカルプロセスＩＤに対応するプロセスＩＤを、プロセスＩＤ管理テーブル記憶部１６５から取得する。受信元・送信先プロセス決定部１６２ａは、取得したプロセスＩＤに対応するプロセスを、送信先プロセスとする。

プロセスＩＤ管理テーブル記憶部１６５は、プロセスＩＤに対応付けて、そのプロセスＩＤが割り振られたプロセスが実行されているサーバのサーバＩＤ、およびそのプロセスのローカルプロセスＩＤを記憶する記憶機能である。例えば、ＲＡＭはＨＤＤの記憶領域の一部が、プロセスＩＤ管理テーブル記憶部１６５として使用される。

図２０は、プロセスＩＤ管理テーブル記憶部のデータ構造例を示す図である。プロセスＩＤ管理テーブル記憶部１６５には、プロセスＩＤ管理テーブル１６５ａが格納されている。プロセスＩＤ管理テーブル１６５ａには、プロセスＩＤ、サーバＩＤ、およびローカルプロセスＩＤの欄が設けられている。

プロセスＩＤの欄には、クラスタシステム内の各プロセスを識別するためのプロセスＩＤが設定される。サーバＩＤの欄には、プロセスＩＤが割り当てられたプロセスが動作しているサーバのサーバＩＤが設定される。ローカルプロセスＩＤの欄には、プロセスＩＤが割り当てられたプロセスのサーバ内のローカルプロセスＩＤが設定される。

図２１は、第３の実施の形態における2-Level Ringアルゴリズムによるプロセス決定を行う処理記述例を示す図である。図２１に示すように、第３の実施の形態における2-Level Ringアルゴリズムは、例えばfor文で処理を記述することができる。ここで、図２１中の各変数のうち、Ｉｐ、Ｉｌ＿ｓｒｃ、Ｉｌ＿ｄｓｔ以外の変数に設定される内容は第２の実施の形態と同様である。第３の実施の形態では、Ｉｐに自プロセスＩＤが設定されるが、その値は０以上、Ｎｐ未満の任意の値である。Ｉｌ＿ｓｒｃには、受信元プロセスのローカルプロセスＩＤ（受信元ローカルプロセスＩＤ）が設定される。Ｉｌ＿ｄｓｔには、送信先プロセスのローカルプロセスＩＤ（送信先ローカルプロセスＩＤ）が設定される。

処理記述の１行目から３行目には、受信元サーバと送信先サーバとを決定する手順が記述されている。１行目から３行目の内容は、図１１に示した第２の実施の形態の処理と同様である。

４行目には、for文による繰り返し処理が定義されている。変数ｌには初期値として「０」が設定される。変数ｌは、for文内の処理が１回繰り返されるごとに、インクリメントされる（ｌ＋＋）。そして、変数ｌの値がローカルプロセス数（Ｎｌ）未満の間、５行目〜９行目の処理が繰り返される。

５行目には、受信元ローカルプロセスＩＤを決定する式が定義されている。５行目に定義された式では、自ローカルプロセスＩＤ（Ｉｌ）に対し、変数ｌの値が減算されると共にローカルプロセス数（Ｎｌ）が加算され、加減算の結果がローカルプロセス数（Ｎｌ）で除算される。除算の余りが、受信元ローカルプロセスＩＤ（Ｉｌ＿ｓｒｃ）に設定される。

６行目には、送信先ローカルプロセスＩＤを決定する式が定義されている。６行目に定義された式では、自ローカルプロセスＩＤ（Ｉｌ）に対し、変数ｌの値とローカルプロセス数（Ｎｌ）とが加算され、加算の結果がローカルプロセス数（Ｎｌ）で除算される。除算の余りが、送信先ローカルプロセスＩＤ（Ｉｌ＿ｄｓｔ）に設定される。

７行目には、受信元プロセスを決定する式が定義されている。５行目に定義された式では、受信元サーバＩＤ（Ｉｓ＿ｓｒｃ）と受信元ローカルプロセスＩＤ（Ｉｌ＿ｓｒｃ）とをパラメータで指定した関数Get＿Ip()の呼び出しを行っている。関数Get＿Ip()は、プロセスＩＤ管理テーブルを参照し、サーバＩＤとローカルプロセスＩＤからプロセスＩＤを決定する処理である。関数Get＿Ip()の処理結果が、受信元プロセスＩＤ（Ｉｐ＿ｓｒｃ）に設定される。

８行目には、送信先プロセスを決定する式が定義されている。８行目に定義された式では、送信先サーバＩＤ（Ｉｓ＿ｄｓｔ）と送信先ローカルプロセスＩＤ（Ｉｌ＿ｄｓｔ）とをパラメータで指定した関数Get＿Ip()の呼び出しを行っている。関数Get＿Ip()の処理結果が、受信元プロセスＩＤ（Ｉｐ＿ｓｒｃ）に設定される。

９行目には、通信処理を実行する関数呼び出しが定義されている。通信処理の関数呼び出しでは、データの受信元として受信元プロセスＩＤ（Ｉｐ＿ｓｒｃ）が指定され、データの送信先として送信先プロセスＩＤ（Ｉｓ＿ｄｓｔ）が指定される。

このようにして、プロセスＩＤをテーブルで管理している場合においても、2-Level Ringアルゴリズムによる適切なプロセスを送信先として決定できる。
〔その他の応用例〕
第２の実施の形態では１台のサーバに、２つのコアを有するプロセッサが１つ搭載されている場合の例を示したが、サーバには４コアなどの多数のコアを有するプロセッサを搭載可能である。また各サーバに、マルチコアプロセッサを複数搭載することもできる。例えば、サーバに４コアのプロセッサを２個搭載することもできる。この場合、総コア数は８となり、並列プログラム実行時にサーバ１台当たり８個のプロセスが実行される。このように１台当たりのプロセス数が多数であっても、第２の実施の形態と同様のアルゴリズム（2-LEVEL Ring アルゴリズム）で全対全通信を行えば、ネットワークスイッチでのＨＯＬブロッキングの発生を抑止できる。

さらに、１台のサーバにシングルコアのプロセッサが複数搭載されている場合も、１台のサーバで複数のプロセスが実行される。このような場合も2-Level Ringアルゴリズムによる全対全のプロセス間通信により、通信効率を向上させることができる。

なお、上記の処理機能は、コンピュータによって実現することができる。その場合、サーバが有すべき機能の処理内容を記述したプログラムが提供される。そのプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、磁気記憶装置、光ディスク、光磁気記録媒体、半導体メモリなどがある。磁気記憶装置には、ハードディスク装置（ＨＤＤ）、フレキシブルディスク（ＦＤ）、磁気テープなどがある。光ディスクには、ＤＶＤ、ＤＶＤ−ＲＡＭ、ＣＤ−ＲＯＭ／ＲＷなどがある。光磁気記録媒体には、ＭＯ（Magneto-Optical disc）などがある。

プログラムを流通させる場合には、例えば、そのプログラムが記録されたＤＶＤ、ＣＤ−ＲＯＭなどの可搬型記録媒体が販売される。また、プログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することもできる。

プログラムを実行するコンピュータは、例えば、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、自己の記憶装置に格納する。そして、コンピュータは、自己の記憶装置からプログラムを読み取り、プログラムに従った処理を実行する。なお、コンピュータは、可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することもできる。また、コンピュータは、サーバコンピュータからプログラムが転送されるごとに、逐次、受け取ったプログラムに従った処理を実行することもできる。

また、上記の処理機能の少なくとも一部を、ＤＳＰ（Digital Signal Processor）、ＡＳＩＣ（Application Specific Integrated Circuit）、ＰＬＤ（Programmable Logic Device）などの電子回路で実現することもできる。

以上、実施の形態を例示したが、実施の形態で示した各部の構成は同様の機能を有する他のものに置換することができる。また、他の任意の構成物や工程が付加されてもよい。さらに、前述した実施の形態のうちの任意の２以上の構成（特徴）を組み合わせたものであってもよい。

以上説明した実施の形態の主な技術的特徴は、以下の付記の通りである。
（付記１） クラスタシステムを構成する複数のサーバのうちの１つとして機能し、複数のサーバそれぞれで実行されるプロセス間の通信を行うコンピュータにおいて、
全対全のプロセス間通信時に複数のサーバそれぞれで繰り返し行われる送信先サーバ決定における同一回の送信先サーバ決定において、複数のサーバが互いに異なるサーバを送信先サーバとして決定するような送信先サーバ決定手順が予め定義されており、前記コンピュータで実行される自プロセスからの全対全のプロセス間通信要求に応答し、前記送信先サーバ決定手順に従って送信先サーバを繰り返し決定する送信先サーバ決定手段と、
送信先サーバが決定されるごとに、決定された送信先サーバで動作しているプロセスを順番に送信先プロセスとして決定する送信先プロセス決定手段と、
送信先プロセスが決定されるごとに、前記自プロセスの実行により送信用のデータが格納された送信用バッファから送信先プロセスに対する送信データを取得し、送信先サーバ内の決定された送信先プロセスの実行時に送信データを読み取り可能とするように、送信先サーバに対して取得した送信データを送信するデータ送信手段と、
を有するコンピュータ。

（付記２） 前記送信先プロセス決定手段は、前記コンピュータで実行される複数のプロセスそれぞれの実行により出力される全対全のプロセス間通信要求に応じて、複数のプロセスそれぞれに対して繰り返し行われる送信先プロセス決定における同一回の送信先プロセス決定において、複数のプロセスそれぞれに対して、送信先サーバ内の互いに異なるプロセスを送信先プロセスとして決定するような送信先プロセス決定手順が予め定義されており、前記送信先サーバ決定手順に従って、前記全対全のプロセス間通信要求を出力した前記自プロセスに対する送信先サーバを繰り返し決定することを特徴とする付記１記載のコンピュータ。

（付記３） 前記送信先サーバ決定手段は、前記送信先サーバ決定手順に従って、複数のサーバそれぞれに付与されたサーバ番号を所定の配列で並べ、前記コンピュータに付与されたサーバ番号と他のサーバ番号との前記配列上の相対的位置関係に基づいて送信先サーバを決定することを特徴とする付記１または２記載のコンピュータ。

（付記４） 前記送信先サーバ決定手段は、前記送信先サーバ決定手順に従って、複数のサーバそれぞれに付与されたサーバ番号を昇順で並べると共に、サーバ番号の最大値の次順をサーバ番号の最小値とする配列とし、前記コンピュータに付与されたサーバ番号から前記配列の並びに沿って一定方向にサーバ番号を順次決定し、決定したサーバ番号で示されるサーバを送信先サーバとすることを特徴とする付記３記載のコンピュータ。

（付記５） 前記送信先プロセス決定手段は、前記送信先プロセス決定手順に従って、複数のプロセスそれぞれに付与されたプロセス番号を所定の配列で並べ、前記全対全のプロセス間通信要求を出力した前記自プロセスに付与されたプロセス番号と他のプロセスのプロセス番号との前記配列上の相対的位置関係に基づき送信先プロセスを決定することを特徴とする付記２または３記載のコンピュータ。

（付記６） 前記送信先プロセス決定手段は、前記送信先プロセス決定手順に従って、送信先サーバ内の複数のプロセスそれぞれに付与された送信先サーバ内でプロセスを一意に識別するローカルプロセス番号を昇順で並べると共に、ローカルプロセス番号の最大値の次順をローカルプロセス番号の最小値とする配列とし、全対全のプロセス間通信要求を出力した前記自プロセスに付与されたプロセス番号から前記配列の並びに沿って一定方向にプロセス番号を順次決定し、決定したプロセス番号で示される送信先サーバ内のプロセスを送信先プロセスとすることを特徴とする付記５記載のコンピュータ。

（付記７） 全対全のプロセス間通信時に複数のサーバそれぞれで繰り返し行われる受信元サーバ決定における同一回の受信元サーバ決定において、複数のサーバが互いに異なるサーバを受信元サーバとして決定するような受信元サーバ決定手順が予め定義されており、前記コンピュータで実行される自プロセスからの全対全のプロセス間通信要求に応答し、前記受信元サーバ決定手順に従って受信元サーバを繰り返し決定する受信元サーバ決定手段と、
受信元サーバが決定されるごとに、受信元サーバで動作しているプロセスを順番に受信元プロセスとして決定する受信元プロセス決定手段と、
受信元プロセスが決定されるごとに、受信元サーバ内の決定された受信元プロセスから送信される受信データを取得し、取得した受信データを受信用バッファに格納するデータ受信手段と、
をさらに有することを特徴とする付記１記載のコンピュータ。

（付記８） クラスタシステムを構成する複数のサーバのうちの１つとして機能するコンピュータに対し、複数のサーバそれぞれで実行されるプロセス間の通信を実行させるプロセス間通信プログラムにおいて、
前記コンピュータに、
全対全のプロセス間通信時に複数のサーバそれぞれで繰り返し行われる送信先サーバ決定における同一回の送信先サーバ決定において、複数のサーバが互いに異なるサーバを送信先サーバとして決定するような送信先サーバ決定手順が予め定義されており、前記コンピュータで実行される自プロセスからの全対全のプロセス間通信要求に応答し、前記送信先サーバ決定手順に従って送信先サーバを繰り返し決定し、
送信先サーバが決定されるごとに、決定された送信先サーバで動作しているプロセスを順番に送信先プロセスとして決定し、
送信先プロセスが決定されるごとに、前記自プロセスの実行により送信用のデータが格納された送信用バッファから送信先プロセスに対する送信データを取得し、送信先サーバ内の決定された送信先プロセスの実行時に送信データを読み取り可能とするように、送信先サーバに対して取得した送信データを送信する、
処理を実行させるプロセス間通信プログラム。

（付記９） クラスタシステムを構成する複数のサーバのうちの１つとして機能するコンピュータで、複数のサーバそれぞれで実行されるプロセス間の通信を実行するプロセス間通信方法において、
前記コンピュータが、
全対全のプロセス間通信時に複数のサーバそれぞれで繰り返し行われる送信先サーバ決定における同一回の送信先サーバ決定において、複数のサーバが互いに異なるサーバを送信先サーバとして決定するような送信先サーバ決定手順が予め定義されており、前記コンピュータで実行される自プロセスからの全対全のプロセス間通信要求に応答し、前記送信先サーバ決定手順に従って送信先サーバを繰り返し決定し、
送信先サーバが決定されるごとに、決定された送信先サーバで動作しているプロセスを順番に送信先プロセスとして決定し、
送信先プロセスが決定されるごとに、前記自プロセスの実行により送信用のデータが格納された送信用バッファから送信先プロセスに対する送信データを取得し、送信先サーバ内の決定された送信先プロセスの実行時に送信データを読み取り可能とするように、送信先サーバに対して取得した送信データを送信する、
ことを特徴とするプロセス間通信方法。

１−１，１−２，１−３，・・・ プロセス
２−１，２−２，２−３，・・・ 送信用バッファ
３−１，３−２，３−３，・・・ 受信用バッファ
４−１，４−２，４−３，・・・ 全対全通信手段
４ａ 送信先サーバ決定手段
４ｂ 送信先プロセス決定手段
４ｃ データ送信手段
４ｄ 受信元サーバ決定手段
４ｅ 受信元プロセス決定手段
４ｆ データ受信手段
５ ネットワークスイッチ
６−１，６−２，・・・ サーバ
６ａ−１，６ｂ−１，６ａ−２，６ｂ−２ プロセッサ
Ａ コンピュータ

Claims (6)

1. クラスタシステムを構成する複数のサーバのうちの１つとして機能し、複数のサーバそれぞれで実行されるプロセス間の通信を行うコンピュータにおいて、
   全対全のプロセス間通信時に複数のサーバそれぞれで繰り返し行われる送信先サーバ決定における同一回の送信先サーバ決定において、複数のサーバが互いに異なるサーバを送信先サーバとして決定するような送信先サーバ決定手順が予め定義されており、前記コンピュータで実行される複数のプロセスのうちの自プロセスからの全対全のプロセス間通信要求に応答し、前記送信先サーバ決定手順に従って送信先サーバを繰り返し決定する送信先サーバ決定手段と、
   前記複数のプロセスそれぞれに対して繰り返し行われる送信先プロセス決定における同一回の送信先プロセス決定において、前記複数のプロセスそれぞれに対して、送信先サーバ内の互いに異なるプロセスを送信先プロセスとして決定するような送信先プロセス決定手順が予め定義されており、送信先サーバが決定されるごとに、前記送信先サーバ決定手順に従って、前記全対全のプロセス間通信要求を出力した前記自プロセスに対する該送信先サーバ内の送信先プロセスを繰り返し決定する送信先プロセス決定手段と、
   送信先サーバ内の送信先プロセスが決定されるごとに、前記自プロセスの実行により送信用のデータが格納された送信用バッファから該送信先プロセスに対する送信データを取得し、該送信先プロセスの実行時に該送信先サーバにおいて該送信データを読み取り可能とするように、該送信先サーバに対して該送信データを送信するデータ送信手段と、
   を有するコンピュータ。
2. 前記送信先サーバ決定手段は、前記送信先サーバ決定手順に従って、複数のサーバそれぞれに付与されたサーバ番号を所定の配列で並べ、前記コンピュータに付与されたサーバ番号と他のサーバ番号との前記配列上の相対的位置関係に基づいて送信先サーバを決定することを特徴とする請求項１記載のコンピュータ。
3. 前記送信先プロセス決定手段は、前記送信先プロセス決定手順に従って、複数のプロセスそれぞれに付与されたプロセス番号を所定の配列で並べ、前記全対全のプロセス間通信要求を出力した前記自プロセスに付与されたプロセス番号と他のプロセスのプロセス番号との前記配列上の相対的位置関係に基づき送信先プロセスを決定することを特徴とする請求項１または２記載のコンピュータ。
4. 全対全のプロセス間通信時に複数のサーバそれぞれで繰り返し行われる受信データの送信元サーバ決定における同一回の送信元サーバ決定において、複数のサーバが互いに異なるサーバを送信元サーバとして決定するような送信元サーバ決定手順が予め定義されており、前記コンピュータで実行される自プロセスからの全対全のプロセス間通信要求に応答し、前記送信元サーバ決定手順に従って送信元サーバを繰り返し決定する送信元サーバ決定手段と、
   送信元サーバが決定されるごとに、送信元サーバで動作しているプロセスを順番に送信元プロセスとして決定する送信元プロセス決定手段と、
   送信元プロセスが決定されるごとに、送信元サーバ内の決定された送信元プロセスから送信される受信データを取得し、取得した受信データを受信用バッファに格納するデータ受信手段と、
   をさらに有することを特徴とする請求項１乃至３のいずれかに記載のコンピュータ。
   
5. クラスタシステムを構成する複数のサーバのうちの１つとして機能するコンピュータに対し、複数のサーバそれぞれで実行されるプロセス間の通信を実行させるプロセス間通信プログラムにおいて、
   前記コンピュータに、
   全対全のプロセス間通信時に複数のサーバそれぞれで繰り返し行われる送信先サーバ決定における同一回の送信先サーバ決定において、複数のサーバが互いに異なるサーバを送信先サーバとして決定するような送信先サーバ決定手順が予め定義されており、前記コンピュータで実行される複数のプロセスのうちの自プロセスからの全対全のプロセス間通信要求に応答し、前記送信先サーバ決定手順に従って送信先サーバを繰り返し決定し、
   前記複数のプロセスそれぞれに対して繰り返し行われる送信先プロセス決定における同一回の送信先プロセス決定において、前記複数のプロセスそれぞれに対して、送信先サーバ内の互いに異なるプロセスを送信先プロセスとして決定するような送信先プロセス決定手順が予め定義されており、送信先サーバが決定されるごとに、前記送信先サーバ決定手順に従って、前記全対全のプロセス間通信要求を出力した前記自プロセスに対する該送信先サーバ内の送信先プロセスを繰り返し決定し、
   送信先サーバ内の送信先プロセスが決定されるごとに、前記自プロセスの実行により送信用のデータが格納された送信用バッファから該送信先プロセスに対する送信データを取得し、該送信先プロセスの実行時に該送信先サーバにおいて該送信データを読み取り可能とするように、該送信先サーバに対して該送信データを送信する、
   処理を実行させるプロセス間通信プログラム。
6. クラスタシステムを構成する複数のサーバのうちの１つとして機能するコンピュータで、複数のサーバそれぞれで実行されるプロセス間の通信を実行するプロセス間通信方法において、
   前記コンピュータが、
   全対全のプロセス間通信時に複数のサーバそれぞれで繰り返し行われる送信先サーバ決定における同一回の送信先サーバ決定において、複数のサーバが互いに異なるサーバを送信先サーバとして決定するような送信先サーバ決定手順が予め定義されており、前記コンピュータで実行される複数のプロセスのうちの自プロセスからの全対全のプロセス間通信要求に応答し、前記送信先サーバ決定手順に従って送信先サーバを繰り返し決定し、
   前記複数のプロセスそれぞれに対して繰り返し行われる送信先プロセス決定における同一回の送信先プロセス決定において、前記複数のプロセスそれぞれに対して、送信先サーバ内の互いに異なるプロセスを送信先プロセスとして決定するような送信先プロセス決定手順が予め定義されており、送信先サーバが決定されるごとに、前記送信先サーバ決定手順に従って、前記全対全のプロセス間通信要求を出力した前記自プロセスに対する該送信先サーバ内の送信先プロセスを繰り返し決定し、
   送信先サーバ内の送信先プロセスが決定されるごとに、前記自プロセスの実行により送信用のデータが格納された送信用バッファから該送信先プロセスに対する送信データを取得し、該送信先プロセスの実行時に該送信先サーバにおいて該送信データを読み取り可能とするように、該送信先サーバに対して該送信データを送信する、
   ことを特徴とするプロセス間通信方法。
   

Images