JP6799258B2 - ノード間通信プログラム、並列処理装置およびノード間通信方法 - Google Patents

Description

本発明はノード間通信プログラム、並列処理装置およびノード間通信方法に関する。

計算量の大きな問題を複数の小さな問題に分割し、ネットワークに接続された複数のコンピュータ（「計算ノード」や単に「ノード」と言うことがある）を並列に動作させて計算する並列処理装置が利用されている。並列処理装置を利用する場合、計算途中においてノード間で通信が発生することがある。そこで、並列処理装置用のアプリケーションプログラムを作成する際に、ＭＰＩ（Message Passing Interface）ライブラリなどの通信ライブラリが利用されることがある。通信ライブラリを利用することで、ユーザはノード間の通信手順の詳細をアプリケーションプログラム中に記述しなくてよい。

なお、各ノードが自分以外の全てのノードにデータを送信する分散メモリ型の並列計算システムが提案されている。提案の並列計算システムは、複数のノードが２ⁿ個のフェーズで相互に通信できるようにする。各ノードは、自分に割り当てられた識別番号とフェーズ番号との排他的論理和を算出し、算出した排他的論理和を識別番号としてもつ他のノードを当該フェーズにおける通信相手として選択する。

特開平１１−１１０３６２号公報

ところで、あるノードが複数の他のノードと通信する可能性がある場合、ノード間通信の効率を向上させるため、当該あるノードのメモリ上には他のノードそれぞれに対応させて個別の受信バッファを確保しておくことが多い。しかし、他のノードの全てに対して個別の受信バッファを用意すると、メモリ使用量が多くなってしまうという問題がある。

１つの側面では、本発明は、ノード間の通信に用いる受信バッファを削減できるノード間通信プログラム、並列処理装置およびノード間通信方法を提供することを目的とする。

１つの態様では、複数のノードのうちの第１のノードとして用いられるコンピュータに以下の処理を実行させるノード間通信プログラムが提供される。複数のノードのうち第１のノードと同じ第１のグループに属する１以上の第２のノードを決定し、１以上の第２のノードそれぞれに対して第１のノードが有するメモリ上に第１の受信バッファを確保する。複数のノードのうち第２のグループに属する第３のノードおよび１以上の第４のノードを決定し、第３のノードに対してメモリ上に第２の受信バッファを確保すると共に１以上の第４のノードに対してはメモリ上の受信バッファを省略する。１以上の第２のノードのうちの１つの第２のノードと通信する場合、１つの第２のノードに対応する第１の受信バッファをメッセージの受信に使用させ、第３のノードと通信する場合、第２の受信バッファをメッセージの受信に使用させ、１以上の第４のノードのうちの１つの第４のノードと通信する場合、第１の受信バッファまたは第２の受信バッファをメッセージの受信に使用させる。

また、１つの態様では、メモリおよびプロセッサを有する第１のノードと、第１のノードとネットワークで接続された複数の他のノードとを有する並列処理装置が提供される。また、１つの態様では、複数のノードを有する並列処理装置が実行するノード間通信方法が提供される。

１つの側面では、ノード間の通信に用いる受信バッファを削減できる。

第１の実施の形態の並列処理装置の例を示す図である。 第２の実施の形態の並列処理装置の例を示す図である。 ノードのハードウェア例を示すブロック図である。 直接ｅａｇｅｒ通信の例を示す図である。 直接ｒｅｎｄｅｚｖｏｕｓ通信の例を示す図である。 第１のバッファ配置例を示す図である。 グループＩＤとグループ内ＩＤの算出例を示す図である。 通信経路の例を示す図である。 第２のバッファ配置例を示す図である。 通信経路の他の例を示す図である。 間接ｅａｇｅｒ通信の例を示す図である。 第１の間接ｒｅｎｄｅｚｖｏｕｓ通信の例を示す図である。 第２の間接ｒｅｎｄｅｚｖｏｕｓ通信の例を示す図である。 メッセージフォーマット例を示す第１の図である。 メッセージフォーマット例を示す第２の図である。 メッセージフォーマット例を示す第３の図である。 ノードの機能例を示すブロック図である。 初期化の手順例を示すフローチャートである。 ｅａｇｅｒ通信の手順例を示すフローチャートである。 ｒｅｎｄｅｚｖｏｕｓ通信の手順例を示す第１のフローチャートである。 ｒｅｎｄｅｚｖｏｕｓ通信の手順例を示す第２のフローチャートである。 ｒｅｎｄｅｚｖｏｕｓ通信の手順例を示す第３のフローチャートである。 ｒｅｎｄｅｚｖｏｕｓ通信の手順例を示す第４のフローチャートである。

以下、本実施の形態を図面を参照して説明する。
［第１の実施の形態］
第１の実施の形態を説明する。

図１は、第１の実施の形態の並列処理装置の例を示す図である。
第１の実施の形態の並列処理装置１０は、ノード１１，１１−１，１１−２，１１−３を含む複数のノードを有する。ノード１１，１１−１，１１−２，１１−３は、例えば、サーバコンピュータなどの物理マシンである。ノード１１，１１−１，１１−２，１１−３はネットワークで接続されている。並列処理装置１０は、ノード１１，１１−１，１１−２，１１−３に並列に情報処理を実行させることができる。情報処理を実行している間、ノード１１，１１−１，１１−２，１１−３は相互にメッセージを送信することがある。メッセージの送信は、例えば、ＭＰＩなどの通信ライブラリによって実装される。

ノード１１は、メモリ１２およびプロセッサ１３を有する。ノード１１−１，１１−２，１１−３は、メモリやプロセッサを有してもよく、以下に説明するノード１１の通信方法と同様の通信方法を実行してもよい。メモリ１２は、いわゆる主記憶装置であり、例えば、ＲＡＭ（Random Access Memory）などの揮発性の半導体記憶装置である。

プロセッサ１３は、例えば、ＣＰＵ（Central Processing Unit）やＤＳＰ（Digital Signal Processor）である。ただし、プロセッサ１３は、ＡＳＩＣ（Application Specific Integrated Circuit）やＦＰＧＡ（Field Programmable Gate Array）などの特定用途の電子回路を含んでもよい。プロセッサ１３は、例えば、メモリ１２などの記憶装置に記憶されたプログラムを実行する。プログラムには、ノード１１−１，１１−２，１１−３との通信を制御するノード間通信プログラムが含まれる。なお、複数のプロセッサの集合を「マルチプロセッサ」または単に「プロセッサ」と言うことがある。

メモリ１２には、他のノードからメッセージを受信するための１以上の受信バッファが確保され得る。プロセッサ１３は、情報処理の開始時（例えば、通信ライブラリの初期化時）に、メモリ１２に１以上の受信バッファを確保する。このとき、プロセッサ１３は、ノード１１が参加する並列処理に利用されるノード群を特定し、ノード群を複数のグループに分割する。並列処理に利用されるノード群は、例えば、ノード１１，１１−１，１１−２，１１−３の間の相互通信によって特定される。プロセッサ１３は、以下のようにして、グループ分けに基づいてメモリ１２に１以上の受信バッファを確保する。

プロセッサ１３は、並列処理に利用されるノード群のうち、ノード１１（第１のノード）と同じグループ１５（第１のグループ）に属する１以上の他のノード（第２のノード）を決定する。第２のノードは、例えば、ノード１１，１１−１，１１−２，１１−３それぞれに付与された識別子に基づいて決定される。識別子はいわゆる「ランク」などの識別番号でもよい。例えば、プロセッサ１３は、各ノードの識別子からグループ識別子とグループ内識別子の組を算出する。プロセッサ１３は、グループ識別子がノード１１と同じでありグループ内識別子がノード１１と異なるノードを第２のノードとして決定する。ここでは、ノード１１−１が第２のノードであると決定される。

プロセッサ１３は、決定した第２のノードそれぞれに対応させて、メモリ１２上に個別の受信バッファ（第１の受信バッファ）を確保する。ここでは、ノード１１−１に対応させてメモリ１２上に受信バッファ１４ａが確保される。

また、プロセッサ１３は、並列処理に利用されるノード群のうち、グループ１５と異なるグループ１５−１（第２のグループ）に属する１つの他のノード（第３のノード）および１以上の他のノード（第４のノード）を決定する。第３のノードは、例えば、グループ１５−１に属するノードのうちノード１１に対応するノード（パートナーノード）である。第４のノードは、例えば、グループ１５−１に属するノードのうち第２のノードのパートナーノードである。第３のノードおよび第４のノードは、例えば、各ノードに付与された識別子に基づいて決定される。例えば、プロセッサ１３は、グループ識別子がノード１１と異なりグループ内識別子がノード１１と同じノードを第３のノードとして決定する。また、プロセッサ１３は、グループ識別子とグループ内識別子の何れもノード１１と異なるノードを第４のノードとして決定する。ここでは、ノード１１−２が第３のノードであると決定され、ノード１１−３が第４のノードであると決定される。

プロセッサ１３は、決定した第３のノードに対応させて、メモリ１２上に受信バッファ（第２の受信バッファ）を確保する。ここでは、ノード１１−２に対応させてメモリ１２上に受信バッファ１４ｂが確保される。一方、プロセッサ１３は、決定した第４のノードに対応する受信バッファはメモリ１２上に確保せず、受信バッファを省略する。

プロセッサ１３は、ノード１１−１と通信する場合に、ノード１１−１に対応する受信バッファ１４ａがメッセージの受信に使用されるよう制御する。例えば、プロセッサ１３は、ノード１１−１がノード１１にメッセージを送信するときに受信バッファ１４ａにメッセージを書き込ませることで、ノード１１−１がノード１１と直接通信できるようにする。また、プロセッサ１３は、ノード１１−２と通信する場合に、受信バッファ１４ｂがメッセージの受信に使用されるよう制御する。例えば、プロセッサ１３は、ノード１１−２がノード１１にメッセージを送信するときに受信バッファ１４ｂにメッセージを書き込ませることで、ノード１１−２がノード１１と直接通信できるようにする。

これに対し、ノード１１−３に対応する個別の受信バッファはメモリ１２上に確保されていない。そこで、プロセッサ１３は、ノード１１−３と通信する場合に、受信バッファ１４ａまたは受信バッファ１４ｂがメッセージの受信に使用されるよう制御する。

ノード１１−３からノード１１にメッセージを送信する場合、送信元ノードのパートナーノードであるノード１１−１を経由してメッセージを送信するようにしてもよい。その場合、例えば、ノード１１−３は、ノード１１−１が有するノード１１−３用の受信バッファにメッセージを書き込む。ノード１１−１はノード１１−３のパートナーノードであるため、ノード１１−１にはノード１１−３用の受信バッファが確保され得る。ノード１１−１は、受信したメッセージを受信バッファ１４ａに転送する。

また、ノード１１−３からノード１１にメッセージを送信する場合、宛先ノードのパートナーノードであるノード１１−２を経由してメッセージを送信するようにしてもよい。その場合、例えば、ノード１１−３は、ノード１１−２が有するノード１１−３用の受信バッファにメッセージを書き込む。ノード１１−２はノード１１−３と同じグループに属するため、ノード１１−２にはノード１１−３用の受信バッファが確保され得る。ノード１１−２は、受信したメッセージを受信バッファ１４ｂに転送する。

第１の実施の形態の並列処理装置１０によれば、ノード１１と同じグループ１５に属するノード１１−１に対して、メモリ１２上に受信バッファ１４ａが確保される。また、グループ１５−１に属するノードのうちノード１１に対応するノード１１−２に対して、メモリ１２上に受信バッファ１４ｂが確保される。一方、グループ１５−１に属するノードのうちノード１１に対応しないノード１１−３については受信バッファが省略される。そして、ノード１１とノード１１−３とが通信する場合、受信バッファ１４ａまたは受信バッファ１４ｂがメッセージの受信に使用される。例えば、ノード１１−３が生成したメッセージはノード１１−１またはノード１１−２を経由してノード１１に送信される。

これにより、ノード１１のメモリ１２上に他の全てのノード用の受信バッファを確保する場合よりも、受信バッファの数を減らすことができメモリ使用量を削減できる。
［第２の実施の形態］
次に、第２の実施の形態を説明する。

図２は、第２の実施の形態の並列処理装置の例を示す図である。
第２の実施の形態の並列処理装置は、少なくとも３６個のノード（ノード１００，１００−１，１００−２，…，１００−３５）を含む。ノード１００，１００−１，１００−２，…，１００−３５はネットワーク３０に接続されている。

第２の実施の形態の並列処理装置は、複数のノードに同一種類のユーザプログラムを配置し、これら複数のノードに並列にユーザプログラムを実行させることで並列処理を実現することができる。並列処理が行われている間、複数のノードは相互に通信することがある。通信頻度や通信するノードの組はユーザプログラムに依存する。

ユーザプログラムを作成するにあたり、ノード間の通信を記述するためにＭＰＩライブラリが使用されることがある。ＭＰＩライブラリを使用することで、ユーザプログラム中に通信手順の詳細を記述しなくてよく、ユーザプログラムの作成が容易となる。ＭＰＩライブラリを参照するユーザプログラムを実行する場合、各ノードは並列処理の開始時にＭＰＩライブラリの初期化を行い、他ノードと通信可能な状態にする。ＭＰＩライブラリの初期化には、ＭＰＩライブラリをＲＡＭにロードしてユーザプログラムから呼び出し可能にすることや、他ノードから受信したメッセージを一時的に格納するための受信バッファをＲＡＭに確保することが含まれる。メッセージの送信や受信などの実際のノード間通信は、ユーザプログラムがＭＰＩライブラリを呼び出すことで適宜実行される。

並列処理では複数の「プロセス」が並列に実行される。各ノードは１以上のプロセスを実行する。第２の実施の形態では説明を簡単にするため、１つのノードが１つのプロセスを実行することを想定する。ただし、１つのノードが複数のプロセスを実行することも可能である。例えば、複数のプロセッサを有するノードは、１つのプロセッサにつき１つのプロセスを実行することがある。また、複数のプロセッサコアを有するノードは、１つのプロセッサコアにつき１つのプロセスを実行することがある。

ユーザプログラムがＭＰＩライブラリを使用している場合、複数のプロセスそれぞれに対して「ランク」と呼ばれる識別番号が割り当てられる。ランクは「０」から始まる連続する非負整数であり、ランクの最大値はプロセス数より１だけ小さい値である。ランクは、例えば、ＭＰＩライブラリに従って複数のノードが通信することで決定される。

図３は、ノードのハードウェア例を示すブロック図である。
ノード１００は、ＣＰＵ１０１、ＲＡＭ１０２、ＨＤＤ（Hard Disk Drive）１０３、画像信号処理部１０４、入力信号処理部１０５、媒体リーダ１０６および通信インタフェース１０７を有する。上記ユニットはバスに接続される。

ＣＰＵ１０１は、プログラムの命令を実行する演算回路を含むプロセッサである。ＣＰＵ１０１は、ＨＤＤ１０３に記憶されたプログラムやデータの少なくとも一部をＲＡＭ１０２にロードし、プログラムを実行する。なお、ＣＰＵ１０１は複数のプロセッサコアを備えてもよく、ノード１００は複数のプロセッサを備えてもよく、以下で説明する処理を複数のプロセッサまたはプロセッサコアを用いて並列に実行してもよい。また、複数のプロセッサの集合を「マルチプロセッサ」または単に「プロセッサ」と言うことがある。

ＲＡＭ１０２は、ＣＰＵ１０１が実行するプログラムやＣＰＵ１０１が演算に用いるデータを一時的に記憶する揮発性の半導体メモリである。なお、ノード１００は、ＲＡＭ以外の種類のメモリを備えてもよく、複数個のメモリを備えてもよい。

ＨＤＤ１０３は、ＯＳ（Operating System）やミドルウェアやアプリケーションソフトウェアなどのソフトウェアのプログラム、および、データを記憶する不揮発性の記憶装置である。プログラムにはノード間通信プログラムが含まれる。なお、ノード１００は、フラッシュメモリやＳＳＤ（Solid State Drive）などの他の種類の記憶装置を備えてもよく、複数の不揮発性の記憶装置を備えてもよい。

画像信号処理部１０４は、ＣＰＵ１０１からの命令に従って、ノード１００に接続されたディスプレイ１０４ａに画像を出力する。ディスプレイ１０４ａとしては、ＣＲＴ（Cathode Ray Tube）ディスプレイ、液晶ディスプレイ（ＬＣＤ：Liquid Crystal Display）、プラズマディスプレイ、有機ＥＬ（ＯＥＬ：Organic Electro-Luminescence）ディスプレイなどを用いることができる。

入力信号処理部１０５は、ノード１００に接続された入力デバイス１０５ａから入力信号を取得し、ＣＰＵ１０１に出力する。入力デバイス１０５ａとしては、マウスやタッチパネルやタッチパッドやトラックボールなどのポインティングデバイス、キーボード、リモートコントローラ、ボタンスイッチなどを用いることができる。また、ノード１００に複数の種類の入力デバイスが接続されていてもよい。

媒体リーダ１０６は、記録媒体１０６ａに記録されたプログラムやデータを読み取る読み取り装置である。記録媒体１０６ａとして、例えば、磁気ディスク、光ディスク、光磁気ディスク（ＭＯ：Magneto-Optical disk）、半導体メモリなどを使用できる。磁気ディスクには、フレキシブルディスク（ＦＤ：Flexible Disk）やＨＤＤが含まれる。光ディスクには、ＣＤ（Compact Disc）やＤＶＤ（Digital Versatile Disc）が含まれる。

媒体リーダ１０６は、例えば、記録媒体１０６ａから読み取ったプログラムやデータを、ＲＡＭ１０２やＨＤＤ１０３などの他の記録媒体にコピーする。読み取られたプログラムは、例えば、ＣＰＵ１０１によって実行される。なお、記録媒体１０６ａは可搬型記録媒体であってもよく、プログラムやデータの配布に用いられることがある。また、記録媒体１０６ａやＨＤＤ１０３を、コンピュータ読み取り可能な記録媒体と言うことがある。

通信インタフェース１０７は、ネットワーク３０に接続され、ネットワーク３０を介して他のノードと通信を行うインタフェースである。通信インタフェース１０７は、例えば、スイッチなどの通信装置とケーブルで接続される有線通信インタフェースである。ただし、基地局と無線リンクで接続される無線通信インタフェースでもよい。

次に、ＭＰＩライブラリを用いたノード間通信の基本的方法について説明する。第２の実施の形態の並列処理装置は、以下に説明するｅａｇｅｒ（イーガー）通信とｒｅｎｄｅｚｖｏｕｓ（ランデブー）通信という２種類の通信を行うことができる。ｅａｇｅｒ通信は少量のデータ本文（データペイロード）を送信するのに好適な通信方法であり、ｒｅｎｄｅｚｖｏｕｓ通信は多量のデータペイロードを送信するのに好適な通信方法である。

図４は、直接ｅａｇｅｒ通信の例を示す図である。
ここでは、ノード１００−２にランク＃２のプロセス１１１ａが配置されており、ノード１００−２６にランク＃２６のプロセス１１１ｂが配置されているとする。そして、プロセス１１１ａがプロセス１１１ｂに対してデータペイロードを送信することを考える。

ノード１００−２のＲＡＭには、プロセス１１１ａによって動的にユーザバッファ１１２ａが確保される。プロセス１１１ａは、送信しようとするデータペイロードをユーザバッファ１１２ａに書き込み、ＭＰＩライブラリを呼び出す。ノード１００−２のＲＡＭには、ＭＰＩライブラリの初期化時に送信バッファ１１３ａが確保されている。呼び出されたＭＰＩライブラリは、ユーザバッファ１１２ａに格納されたデータペイロードにＭＰＩ通信用のヘッダを付加してデータメッセージを生成し、データメッセージを送信バッファ１１３ａに書き込む。ＭＰＩライブラリは、送信バッファ１１３ａに格納されたデータメッセージを、ノード１００−２６の受信バッファ１１４ａ宛てに送信する。

ノード１００−２６のＲＡＭには、プロセス１１１ｂによって動的にユーザバッファ１１２ｂが確保される。プロセス１１１ｂは、プロセス１１１ａからのデータペイロードの受信を待つためにＭＰＩライブラリを呼び出す。ノード１００−２６のＲＡＭには、ＭＰＩライブラリの初期化時に受信バッファ１１４ａが確保されている。受信バッファ１１４ａは、プロセス１１１ａからメッセージを受信するための受信バッファ、すなわち、ランク＃２用の受信バッファである。ノード１００−２は、ＭＰＩライブラリの初期化時に行われるノード間通信などを通じて受信バッファ１１４ａのアドレスを知っている。

ノード１００−２６のＭＰＩライブラリは、受信バッファ１１４ａにメッセージが到着しているか監視する。受信バッファ１１４ａにデータメッセージが到着すると、ＭＰＩライブラリは、到着したデータメッセージからヘッダを削除してデータペイロードを抽出し、データペイロードをユーザバッファ１１２ｂに書き込む。ユーザバッファ１１２ｂに書き込まれたデータペイロードは、プロセス１１１ｂから参照可能となる。

図５は、直接ｒｅｎｄｅｚｖｏｕｓ通信の例を示す図である。
ここでは、図４のｅａｇｅｒ通信と同様に、ノード１００−２に配置されたランク＃２のプロセス１１１ａが、ノード１００−２６に配置されたランク＃２６のプロセス１１１ｂに対してデータペイロードを送信することを考える。

ノード１００−２のＲＡＭには、プロセス１１１ａによって動的にユーザバッファ１１２ａが確保される。プロセス１１１ａは、送信しようとするデータペイロードをユーザバッファ１１２ａに書き込み、ＭＰＩライブラリを呼び出す。ノード１００−２のＲＡＭには、ＭＰＩライブラリの初期化時に送信バッファ１１３ａが確保されている。呼び出されたＭＰＩライブラリは、ｒｅｎｄｅｚｖｏｕｓ通信の開始を要求する制御メッセージ（要求制御メッセージ）を生成し、要求制御メッセージを送信バッファ１１３ａに書き込む。ＭＰＩライブラリは、送信バッファ１１３ａに格納された要求制御メッセージを、ノード１００−２６の受信バッファ１１４ａ宛てに送信する。例えば、ＭＰＩライブラリは、受信バッファ１１４ａのアドレスを指定して要求制御メッセージを送信する。

ノード１００−２６のＲＡＭには、プロセス１１１ｂによって動的にユーザバッファ１１２ｂが確保される。プロセス１１１ｂは、プロセス１１１ａからのデータペイロードの受信を待つためにＭＰＩライブラリを呼び出す。ノード１００−２６のＲＡＭには、ＭＰＩライブラリの初期化時に受信バッファ１１４ａが確保されている。受信バッファ１１４ａはランク＃２用の受信バッファであり、ノード１００−２はそのアドレスを予め知っている。ノード１００−２６のＭＰＩライブラリは、受信バッファ１１４ａに要求制御メッセージが到着すると、要求制御メッセージに対する応答を示す制御メッセージ（応答制御メッセージ）を生成し、応答制御メッセージを送信バッファ１１３ｂに書き込む。

応答制御メッセージには、ユーザバッファ１１２ｂのアドレスが含まれる。ＭＰＩライブラリは、送信バッファ１１３ｂに格納された応答制御メッセージを、ノード１００−２の受信バッファ１１４ｂ宛てに送信する。ノード１００−２のＲＡＭには、ＭＰＩライブラリの初期化時に受信バッファ１１４ｂが確保されている。受信バッファ１１４ｂは、プロセス１１１ｂからメッセージを受信するための受信バッファ、すなわち、ランク＃２６用の受信バッファである。ノード１００−２６は、ＭＰＩライブラリの初期化時に行われるノード間通信などを通じて受信バッファ１１４ｂのアドレスを知っている。

ノード１００−２のＭＰＩライブラリは、受信バッファ１１４ｂに応答制御メッセージが到着すると、ユーザバッファ１１２ａに格納されたデータペイロードを、応答制御メッセージで指定されたユーザバッファ１１２ｂ宛てに送信する。このとき、ＭＰＩライブラリは、送信バッファ１１３ａや受信バッファ１１４ａを経由せずに、データペイロードをユーザバッファ１１２ｂに直接送信することができる。また、ＭＰＩライブラリは、ｒｅｎｄｅｚｖｏｕｓ通信の完了を示す制御メッセージ（完了制御メッセージ）を生成し、完了制御メッセージを送信バッファ１１３ａに書き込む。ＭＰＩライブラリは、送信バッファ１１３ａに格納された完了制御メッセージを受信バッファ１１４ａ宛てに送信する。

ノード１００−２６のＭＰＩライブラリは、受信バッファ１１４ａに応答制御メッセージが到着したことによって、ｒｅｎｄｅｚｖｏｕｓ通信が完了したと判断する。例えば、ＭＰＩライブラリがプロセス１１１ｂにデータペイロードの到着を通知する。ユーザバッファ１１２ｂに格納されたデータペイロードは、ｒｅｎｄｅｚｖｏｕｓ通信が完了したと判断された後、プロセス１１１ｂから参照可能となる。

このように、ｅａｇｅｒ通信は、予め確保された受信バッファを利用して送信元ノードから宛先ノードに一方的にデータペイロードを送信する通信方法である。よって、データペイロードのサイズが受信バッファのサイズよりも十分小さい場合には、ｅａｇｅｒ通信の方がデータペイロードを効率的に送信することができる。一方、ｒｅｎｄｅｚｖｏｕｓ通信は、制御メッセージによって宛先ノードから送信元ノードに書き込み先バッファをその都度指定することで、予め確保された受信バッファを経由しないでデータペイロードを送信する通信方法である。よって、データペイロードのサイズが大きい場合には、ｒｅｎｄｅｚｖｏｕｓ通信の方がデータペイロードを効率的に送信することができる。

ここで、任意の２つのノードの間で図４，５のように直接メッセージを送信できるようにすると、各ノードはＲＡＭ上に多数の受信バッファを予め確保しておくことになるという問題がある。次に、バッファ配置の問題について説明する。

図６は、第１のバッファ配置例を示す図である。
ノード１００にはランク＃０のプロセス１１１ｃが配置されている。このバッファ配置方法では、ノード１００は、ＭＰＩライブラリの初期化時に送信バッファ１１３ｄを確保する。また、ノード１００は、ＭＰＩライブラリの初期化時に、ノード１００以外のノードに配置されたランク＃１〜＃３５のプロセスに対応する３５個の受信バッファを確保する。受信バッファ１１５ａはランク＃１に対応し、受信バッファ１１５ｂはランク＃２に対応し、受信バッファ１１５ｃはランク＃３５に対応する。

ノード１００−１にはランク＃１のプロセス１１１ｄが配置されている。ノード１００−１は、ＭＰＩライブラリの初期化時に送信バッファ１１３ｅを確保する。また、ノード１００−１は、ＭＰＩライブラリの初期化時に、ノード１００−１以外のノードに配置されたランク＃０，＃２〜＃３５のプロセスに対応する３５個の受信バッファを確保する。受信バッファ１１５ｄはランク＃０に対応し、受信バッファ１１５ｅはランク＃２に対応し、受信バッファ１１５ｆはランク＃３５に対応する。

ノード１００−３５にはランク＃３５のプロセス１１１ｅが配置されている。ノード１００−３５は、ＭＰＩライブラリの初期化時に送信バッファ１１３ｆを確保する。また、ノード１００−３５は、ＭＰＩライブラリの初期化時に、ノード１００−３５以外のノードに配置されたランク＃０〜＃３４のプロセスに対応する３５個の受信バッファを確保する。受信バッファ１１５ｇはランク＃０に対応し、受信バッファ１１５ｈはランク＃１に対応し、受信バッファ１１５ｉはランク＃３４に対応する。

並列処理の間に何れのプロセス間でメッセージが送信されるかは、ＭＰＩライブラリの初期化時には不明である。よって、任意のプロセス間で図４，５のように直接メッセージを送信することを許容すると、各ノードは図６のようにＲＡＭ上に多数の受信バッファを確保することになる。例えば、１つの受信バッファのサイズが２キロバイト（ｋＢ）でありプロセス数が１００万であるとすると、各ノードは受信バッファだけで約２ギガバイト（ＧＢ）のメモリ領域を使用することになる。そこで、第２の実施の形態の並列処理装置は、並列処理で使用する複数のノードをグループ分けし、メッセージを送信する経路を制限することでＲＡＭ上の受信バッファを削減する。

図７は、グループＩＤとグループ内ＩＤの算出例を示す図である。
並列処理装置は、各プロセスのランクｒａｎｋからグループ識別子ｇｒｐ＿ｉｄとグループ内識別子ｉｄを算出する。ｇｒｐ＿ｉｄ＝ｒａｎｋ／Ｎ_ppgであり、ｉｄ＝ｍｏｄ（ｒａｎｋ，Ｎ_ppg）である。すなわち、ｇｒｐ＿ｉｄはｒａｎｋをＮ_ppgで割った商（小数点以下を切り捨てた整数）であり、ｉｄはｒａｎｋをＮ_ppgで割ったときの余りである。Ｎ_ppgはグループ１つ当たりのプロセス数である。第２の実施の形態では１ノードに１プロセスが配置されるため、Ｎ_ppgはグループ１つ当たりのノード数でもある。Ｎ_ppgは、例えば、ＭＰＩライブラリの中で固定値として設定されている。ただし、環境変数または実行コマンドのオプションとして、ユーザがＮ_ppgを指定できるようにしてもよい。

同じグループ識別子ｇｒｐ＿ｉｄをもつプロセスは同じグループに属している。第２の実施の形態では１ノードに１プロセスが配置されるため、同じグループ識別子ｇｒｐ＿ｉｄをもつプロセスが配置されたノードは同じグループに属していると言うことができる。また、あるプロセスにとって、グループ識別子ｇｒｐ＿ｉｄは異なるもののグループ内識別子ｉｄが同じである他のプロセスは「パートナープロセス」である。第２の実施の形態では１ノードに１プロセスが配置されるため、あるプロセスが配置されたノードにとって、グループ識別子ｇｒｐ＿ｉｄは異なるもののグループ内識別子ｉｄが同じである他のプロセスが配置された他のノードは「パートナーノード」であると言うことができる。

ここでは、Ｎ_ppg＝９であり、ノード１００，１００−１，…，１００−３５に配置されたランク＃０〜＃３５のプロセスが４つのグループに分割される場合を考える。グループ４１（＃０）は、ｇｒｐ＿ｉｄ＝０をもつプロセス、すなわち、ノード１００，１００−１，…，１００−８に配置されたランク＃０〜＃８のプロセスの集合である。グループ４２（＃１）は、ｇｒｐ＿ｉｄ＝１をもつプロセス、すなわち、ノード１００−９，…，１００−１７に配置されたランク＃９〜＃１７のプロセスの集合である。グループ４３（＃２）は、ｇｒｐ＿ｉｄ＝２をもつプロセス、すなわち、ノード１００−１８，…，１００−２６に配置されたランク＃１８〜＃２６のプロセスの集合である。グループ４４（＃３）は、ｇｒｐ＿ｉｄ＝３をもつプロセス、すなわち、ノード１００−２７，…，１００−３５に配置されたランク＃２７〜＃３５のプロセスの集合である。

図８は、通信経路の例を示す図である。
並列処理装置は、あるプロセスが直接メッセージを送信できる宛先プロセスを、同一グループ内のプロセス（グループ識別子が同じプロセス）と他グループ内のパートナープロセス（グループ内識別子が同じプロセス）に限定する。他グループ内のパートナープロセス以外のプロセス（グループ識別子もグループ内識別子も異なるプロセス）には、パートナープロセス経由でメッセージを送信することになる。

例えば、ランク＃２のプロセス１１１ａをもつノード１００−２は、宛先が同一グループに属するため、ランク＃４のプロセスをもつノード１００−４に対して直接メッセージを送信できる。また、ノード１００−２は、宛先がパートナープロセスであるため、ランク＃１１のプロセスをもつノード１００−１１に対して直接メッセージを送信できる。

一方、ノード１００−２は、宛先が同一グループに属しておらずパートナープロセスでもないため、ランク＃２６のプロセス１１１ｂをもつノード１００−２６に対しては直接メッセージを送信しない。この場合、ノード１００−２は、宛先プロセスと同じグループに属するパートナープロセスであるランク＃２０のプロセスを特定し、ランク＃２０のプロセスをもつノード１００−２０に対してメッセージを送信する。ノード１００−２０は、ノード１００−２から受信したメッセージをノード１００−２６に転送する。

このように、メッセージの送信経路を限定することで受信バッファを削減できる。
図９は、第２のバッファ配置例を示す図である。
ノード１００にはランク＃０のプロセス１１１ｃが配置されている。ノード１００は、ＭＰＩライブラリの初期化時に送信バッファ１１３ｄを確保する。また、ノード１００は、ＭＰＩライブラリの初期化時に、同一グループに属するランク＃１〜＃８のプロセスに対応する８個の受信バッファを確保する。更に、ノード１００は、他グループのパートナープロセスであるランク＃９，＃１８，＃２７のプロセスに対応する３個の受信バッファを確保する。受信バッファ１１５ｊはランク＃８に対応し、受信バッファ１１５ｋはランク＃９に対応し、受信バッファ１１５ｌはランク＃１８に対応し、受信バッファ１１５ｍはランク＃２７に対応する。

ノード１００−１にはランク＃１のプロセス１１１ｄが配置されている。ノード１００−１は、ＭＰＩライブラリの初期化時に送信バッファ１１３ｅを確保する。また、ノード１００−１は、ＭＰＩライブラリの初期化時に、同一グループに属するランク＃０，＃２〜＃８のプロセスに対応する８個の受信バッファを確保する。更に、ノード１００−１は、他グループのパートナープロセスであるランク＃１０，＃１９，＃２８のプロセスに対応する３個の受信バッファを確保する。受信バッファ１１５ｎはランク＃８に対応し、受信バッファ１１５ｏはランク＃１０に対応し、受信バッファ１１５ｐはランク＃１９に対応し、受信バッファ１１５ｑはランク＃２８に対応する。

ノード１００−３５にはランク＃３５のプロセス１１１ｅが配置されている。ノード１００−３５は、ＭＰＩライブラリの初期化時に送信バッファ１１３ｆを確保する。また、ノード１００−３５は、ＭＰＩライブラリの初期化時に、同一グループに属するランク＃２７〜＃３４のプロセスに対応する８個の受信バッファを確保する。更に、ノード１００−３５は、他グループのパートナープロセスであるランク＃８，＃１７，＃２６のプロセスに対応する３個の受信バッファを確保する。受信バッファ１１５ｒはランク＃２７に対応し、受信バッファ１１５ｓはランク＃８に対応し、受信バッファ１１５ｔはランク＃１７に対応し、受信バッファ１１５ｕはランク＃２６に対応する。

このように、各ノードに確保される受信バッファの数は、他ノードに配置されたプロセスのうち同一グループに属するプロセスの数と他グループの数とを合計したものとなる。図９の例では、他ノードに配置されたプロセスのうち同一グループに属するプロセスの数はＮ_ppg−１＝８であり他グループの数は３であるため、ノード１００，１００−１，…，１００−３５それぞれに確保される受信バッファの数は１１になる。よって、図６の場合よりも各ノードに確保される受信バッファが少なくなる。

なお、図７，８ではプロセス総数がＮ_ppgで割り切れる例を示したが、プロセス総数がＮ_ppgで割り切れない場合にもメッセージの送信経路を制限することができる。
図１０は、通信経路の他の例を示す図である。

ここでは、１７個のノード（ノード１００，１００−１，…，１００−１６）にランク＃０〜＃１６のプロセスが配置されており、Ｎ_ppg＝６である場合を考える。ランク＃０〜＃５のプロセスがグループ＃０に属し、ランク＃６〜＃１１のプロセスがグループ＃１に属し、ランク＃１２〜＃１６のプロセスがグループ＃２に属する。プロセス総数がＮ_ppgで割り切れないため、グループ＃２に属するプロセスの数はＮ_ppg−１＝５である。

ここで、ランク＃５のプロセスがランク＃１４のプロセスにメッセージを送信しようとするとき、図８と同様の方法でメッセージを送信しようとしても、グループ＃２にはランク＃５のプロセスに対応するパートナープロセスが存在しない。すなわち、グループ＃２には、ランク＃５のプロセスと同じグループ内識別子＝５をもつプロセスが存在しない。

そこで、パートナープロセスが存在しない場合、並列処理装置は、送信元プロセスと同じグループに属するプロセスのうち宛先プロセスに対応するパートナープロセスを中継プロセスとして指定することとする。ここでは、ランク＃５のプロセスをもつノード１００−５は、グループ＃０に属するプロセスの中から宛先プロセスに対応するパートナープロセスであるランク＃２のプロセスを特定し、ランク＃２のプロセスをもつノード１００−２に対してメッセージを送信する。ノード１００−２は、ノード１００−５から受信したメッセージを、ランク＃１４のプロセスをもつノード１００−１４に転送する。

次に、中継プロセスが存在する場合における間接的なｅａｇｅｒ通信と間接的なｒｅｎｄｅｚｖｏｕｓ通信について説明する。なお、第２の実施の形態の並列処理装置は、ｒｅｎｄｅｚｖｏｕｓ通信として後述する２種類の方法の何れか一方を選択できる。

図１１は、間接ｅａｇｅｒ通信の例を示す図である。
ここでは、ノード１００−２がノード１００−２０を経由してノード１００−２６に対して、ｅａｇｅｒ通信によりデータペイロードを送信する場合を考える。

ノード１００−２のＲＡＭには、ＭＰＩライブラリの初期化時に送信バッファ１１３ａが確保される。また、ノード１００−２のＲＡＭには、動的にユーザバッファ１１２ａが確保される。ユーザバッファ１１２ａには、プロセス１１１ａによってデータペイロードが書き込まれる。ノード１００−２は、ユーザバッファ１１２ａに格納されたデータペイロードにヘッダを付加してデータメッセージを生成し、データメッセージを送信バッファ１１３ａに書き込む。ノード１００−２は、送信バッファ１１３ａに格納されたデータメッセージを、ノード１００−２０の受信バッファ１１４ｃに送信する。

ノード１００−２０のＲＡＭには、ＭＰＩライブラリの初期化時に送信バッファ１１３ｃやランク＃２用の受信バッファ１１４ｃが確保される。受信バッファ１１４ｃにデータメッセージが到着すると、ノード１００−２０は、到着したデータメッセージのヘッダを適切に書き換え、ヘッダを書き換えたデータメッセージを送信バッファ１１３ｃに書き込む。ノード１００−２０は、送信バッファ１１３ｃに格納されたデータメッセージを、ノード１００−２６の受信バッファ１１４ｄに送信する。

ノード１００−２６のＲＡＭには、ＭＰＩライブラリの初期化時にランク＃２０用の受信バッファ１１４ｄが確保される。また、ノード１００−２６のＲＡＭには、動的にユーザバッファ１１２ｂが確保される。受信バッファ１１４ｄにデータメッセージが到着すると、ノード１００−２６は、到着したデータメッセージからデータペイロードを抽出し、抽出したデータペイロードをユーザバッファ１１２ｂに書き込む。プロセス１１１ｂは、ユーザバッファ１１２ｂからデータペイロードを読み出す。

図１２は、第１の間接ｒｅｎｄｅｚｖｏｕｓ通信の例を示す図である。
ここでは、ノード１００−２がノード１００−２０を経由してノード１００−２６に対して、ｒｅｎｄｅｚｖｏｕｓ通信によりデータペイロードを送信する場合を考える。

ノード１００−２のＲＡＭには、ＭＰＩライブラリの初期化時に送信バッファ１１３ａやランク＃２０用の受信バッファ１１４ｅが確保される。また、ノード１００−２のＲＡＭには、動的にユーザバッファ１１２ａが確保される。ユーザバッファ１１２ａには、プロセス１１１ａによってデータペイロードが書き込まれる。すると、ノード１００−２は、ｒｅｎｄｅｚｖｏｕｓ通信の開始を示す要求制御メッセージを生成して送信バッファ１１３ａに書き込む。ノード１００−２は、送信バッファ１１３ａに格納された要求制御メッセージを、ノード１００−２０の受信バッファ１１４ｃに送信する。

ノード１００−２０のＲＡＭには、ＭＰＩライブラリの初期化時に送信バッファ１１３ｃ、ランク＃２用の受信バッファ１１４ｃおよびランク＃２６用の受信バッファ１１４ｆが確保される。受信バッファ１１４ｃに要求制御メッセージが到着すると、ノード１００−２０は、ＲＡＭに一時バッファ１１２ｃを確保する。一時バッファ１１２ｃは、受信バッファ１１４ｃよりサイズが大きいものの、ユーザプログラムから認識されなくてよい。ノード１００−２０は、要求制御メッセージに対する応答を示す応答制御メッセージを生成して送信バッファ１１３ｃに書き込む。応答制御メッセージには一時バッファ１１２ｃのアドレスが含まれる。ノード１００−２０は、送信バッファ１１３ｃに格納された応答制御メッセージを、ノード１００−２の受信バッファ１１４ｅに送信する。

受信バッファ１１４ｅに応答制御メッセージが到着すると、ノード１００−２は、ユーザバッファ１１２ａに格納されたデータペイロードを、応答制御メッセージによって指定された一時バッファ１１２ｃに送信する。データペイロードの送信が完了すると、ノード１００−２は、送信完了を示す完了制御メッセージを生成して送信バッファ１１３ａに書き込む。ノード１００−２は、送信バッファ１１３ａに格納された完了制御メッセージを、ノード１００−２０の受信バッファ１１４ｃに送信する。

受信バッファ１１４ｃに完了制御メッセージが到着すると、ノード１００−２０は、ｒｅｎｄｅｚｖｏｕｓ通信の開始を示す要求制御メッセージを生成して送信バッファ１１３ｃに書き込む。ノード１００−２０は、送信バッファ１１３ｃに格納された要求制御メッセージを、ノード１００−２６の受信バッファ１１４ｄに送信する。

ノード１００−２６のＲＡＭには、ＭＰＩライブラリの初期化時に送信バッファ１１３ｂやランク＃２０用の受信バッファ１１４ｄが確保される。また、ノード１００−２６のＲＡＭには、プロセス１１１ｂがデータペイロードを取得するために動的にユーザバッファ１１２ｂが確保される。受信バッファ１１４ｄに要求制御メッセージが到着すると、ノード１００−２６は、要求制御メッセージに対する応答を示す応答制御メッセージを生成して送信バッファ１１３ｂに書き込む。応答制御メッセージにはユーザバッファ１１２ｂのアドレスが含まれる。ノード１００−２６は、送信バッファ１１３ｂに格納された応答制御メッセージを、ノード１００−２０の受信バッファ１１４ｆに送信する。

受信バッファ１１４ｆに応答制御メッセージが到着すると、ノード１００−２０は、一時バッファ１１２ｃに格納されたデータペイロードを、応答制御メッセージによって指定されたユーザバッファ１１２ｂに送信する。データペイロードの送信が完了すると、ノード１００−２０は、送信完了を示す完了制御メッセージを生成して送信バッファ１１３ｃに書き込む。ノード１００−２０は、送信バッファ１１３ｃに格納された完了制御メッセージを、ノード１００−２６の受信バッファ１１４ｄに送信する。プロセス１１１ｂは、ユーザバッファ１１２ｂからデータペイロードを読み出す。

次に、別のｒｅｎｄｅｚｖｏｕｓ通信の方法を説明する。
図１３は、第２の間接ｒｅｎｄｅｚｖｏｕｓ通信の例を示す図である。
前述の第１のｒｅｎｄｅｚｖｏｕｓ通信方法では、最初の送信元ノード（始点ノード）と最終的な宛先ノード（終点ノード）との間で中継ノードがデータペイロードを転送している。これに対し、第２のｒｅｎｄｅｚｖｏｕｓ通信方法では、中継ノードは要求制御メッセージのみ転送し、それ以降の応答制御メッセージとデータペイロードと完了制御メッセージは始点ノードと終点ノードとの間で直接送信するようにする。

ノード１００−２のＲＡＭには、ＭＰＩライブラリの初期化時に送信バッファ１１３ａが確保される。また、ノード１００−２のＲＡＭには、動的にユーザバッファ１１２ａが確保される。ユーザバッファ１１２ａには、プロセス１１１ａによってデータペイロードが書き込まれる。すると、ノード１００−２は、ＲＡＭに一時的な受信バッファ１１４ｇを確保する。ノード１００−２は、ｒｅｎｄｅｚｖｏｕｓ通信の開始を示す要求制御メッセージを生成して送信バッファ１１３ａに書き込む。要求制御メッセージには受信バッファ１１４ｇのアドレスが含まれる。ノード１００−２は、送信バッファ１１３ａに格納された要求制御メッセージを、ノード１００−２０の受信バッファ１１４ｃに送信する。

ノード１００−２０のＲＡＭには、ＭＰＩライブラリの初期化時に送信バッファ１１３ｃやランク＃２用の受信バッファ１１４ｃが確保される。受信バッファ１１４ｃに要求制御メッセージが到着すると、ノード１００−２０は、到着した要求制御メッセージの一部内容を適切に書き換え、書き換えた要求制御メッセージを送信バッファ１１３ｃに書き込む。ノード１００−２０は、送信バッファ１１３ｃに格納された要求制御メッセージを、ノード１００−２６の受信バッファ１１４ｄに送信する。

ノード１００−２６のＲＡＭには、ＭＰＩライブラリの初期化時に送信バッファ１１３ｂやランク＃２０用の受信バッファ１１４ｄが確保される。また、ノード１００−２６のＲＡＭには、プロセス１１１ｂがデータペイロードを取得するために動的にユーザバッファ１１２ｂが確保される。受信バッファ１１４ｄに要求制御メッセージが到着すると、ノード１００−２６は、ＲＡＭに一時的な受信バッファ１１４ｈを確保する。ノード１００−２６は、要求制御メッセージに対する応答を示す応答制御メッセージを生成して送信バッファ１１３ｂに書き込む。応答制御メッセージには、ユーザバッファ１１２ｂのアドレスと受信バッファ１１４ｈのアドレスが含まれる。ノード１００−２６は、送信バッファ１１３ｂに格納された応答制御メッセージを、要求制御メッセージによって指定されたノード１００−２の受信バッファ１１４ｇに送信する。

受信バッファ１１４ｇに応答制御メッセージが到着すると、ノード１００−２は、ユーザバッファ１１２ａに格納されたデータペイロードを、応答制御メッセージによって指定されたユーザバッファ１１２ｂに送信する。データペイロードの送信が完了すると、ノード１００−２は、送信完了を示す完了制御メッセージを生成して送信バッファ１１３ａに書き込む。ノード１００−２は、送信バッファ１１３ａに格納された完了制御メッセージを、応答制御メッセージによって指定された受信バッファ１１４ｈに送信する。プロセス１１１ｂは、ユーザバッファ１１２ｂからデータペイロードを読み出す。

次に、メッセージのフォーマットについて説明する。
図１４は、メッセージフォーマット例を示す第１の図である。
始点ノードであるノード１００−２から中継ノードであるノード１００−２０には、データメッセージ１２１が送信される。データメッセージ１２１は、メッセージ種別、送信元ランク、ユーザ指定タグ、始点ランク、終点ランクおよびデータペイロードを含む。

メッセージ種別は、メッセージの種別がデータメッセージであることを示す。送信元ランクは、データメッセージ１２１の直接の送信元を示すランクであり、この例ではランク＃２である。ユーザ指定タグは、複数のメッセージを区別するためにユーザプログラムが任意に設定できるタグである。始点ランクは、ｅａｇｅｒ通信の最初の送信元を示すランクであり、この例ではランク＃２である。終点ランクは、ｅａｇｅｒ通信の最終的な宛先を示すランクであり、この例ではランク＃２６である。

中継ノードであるノード１００−２０から終点ノードであるノード１００−２６には、データメッセージ１２１と同様のデータメッセージが送信される。このデータメッセージの送信元ランクは、ランク＃２からランク＃２０に書き換えられる。一方、このデータメッセージの始点ランクおよび終点ランクは、データメッセージ１２１と同じである。すなわち、ノード１００−２０によってｅａｇｅｒ通信が中継されても、始点ランクはランク＃２のままであり、終点ランクはランク＃２６のままである。

図１５は、メッセージフォーマット例を示す第２の図である。
第１のｒｅｎｄｅｚｖｏｕｓ通信方法では、始点ノードであるノード１００−２から中継ノードであるノード１００−２０に要求制御メッセージ１２２が送信される。要求制御メッセージ１２２は、メッセージ種別、送信元ランク、ユーザ指定タグ、データサイズ、送信側リクエスト識別子、始点ランクおよび終点ランクを含む。

メッセージ種別は、メッセージの種別が要求制御メッセージであることを示す。送信元ランクは、要求制御メッセージ１２２の直接の送信元を示すランクであり、この例ではランク＃２である。ユーザ指定タグは、複数のメッセージを区別するためにユーザプログラムが任意に設定できるタグである。データサイズは、ｒｅｎｄｅｚｖｏｕｓ通信においてノード１００−２が送信しようとするデータペイロードのサイズである。送信側リクエスト識別子は、ｒｅｎｄｅｚｖｏｕｓ通信を識別するためにノード１００−２が付与する識別子である。始点ランクは、ｒｅｎｄｅｚｖｏｕｓ通信の最初の送信元を示すランクであり、この例ではランク＃２である。終点ランクは、ｒｅｎｄｅｚｖｏｕｓ通信の最終的な宛先を示すランクであり、この例ではランク＃２６である。

中継ノードであるノード１００−２０から始点ノードであるノード１００−２には応答制御メッセージ１２３が送信される。応答制御メッセージ１２３は、メッセージ種別、ユーザバッファアドレス、送信側リクエスト識別子および受信側リクエスト識別子を含む。

メッセージ種別は、メッセージの種別が応答制御メッセージであることを示す。ユーザバッファアドレスは、ノード１００−２０がデータペイロードを受信するためのバッファのアドレスである。ただし、ここではノード１００−２０は中継ノードであるため、データペイロードを受信するためのバッファは、ノード１００−２０に一時的に確保された一時バッファ１１２ｃである。送信側リクエスト識別子は、要求制御メッセージ１２２に含まれていた識別子である。受信側リクエスト識別子は、ｒｅｎｄｅｚｖｏｕｓ通信を識別するためにノード１００−２０が付与する識別子である。

始点ノードであるノード１００−２から中継ノードであるノード１００−２０には完了制御メッセージ１２４が送信される。完了制御メッセージ１２４は、メッセージ種別および受信側リクエスト識別子を含む。

メッセージ種別は、メッセージの種別が完了制御メッセージであることを示す。受信側リクエスト識別子は、応答制御メッセージ１２３に含まれていた識別子である。
中継ノードであるノード１００−２０から終点ノードであるノード１００−２６には、要求制御メッセージ１２２と同様の要求制御メッセージが送信される。また、終点ノードであるノード１００−２６から中継ノードであるノード１００−２０には、応答制御メッセージ１２３と同様の応答制御メッセージが送信される。また、中継ノードであるノード１００−２０から終点ノードであるノード１００−２６には、完了制御メッセージ１２４と同様の完了制御メッセージが送信される。これらの制御メッセージに含まれる送信元ランク、送信側リクエスト識別子、受信側リクエスト識別子およびユーザバッファアドレスは、ノード１００−２０，１００−２６により適切に設定される。

図１６は、メッセージフォーマット例を示す第３の図である。
第２のｒｅｎｄｅｚｖｏｕｓ通信方法では、始点ノードであるノード１００−２から中継ノードであるノード１００−２０に要求制御メッセージ１２５が送信される。要求制御メッセージ１２５は、メッセージ種別、送信元ランク、ユーザ指定タグ、データサイズ、送信側リクエスト識別子、始点ランク、終点ランクおよび送信側一時バッファアドレスを含む。メッセージ種別、送信元ランク、ユーザ指定タグ、データサイズ、送信側リクエスト識別子、始点ランクおよび終点ランクは、要求制御メッセージ１２２と同様である。送信側一時バッファアドレスは、応答制御メッセージを受信するためにノード１００−２に一時的に確保された受信バッファ１１４ｇのアドレスである。

中継ノードであるノード１００−２０から終点ノードであるノード１００−２６には、要求制御メッセージ１２５と同様の要求制御メッセージが送信される。原則として、要求制御メッセージ１２５の内容がノード１００−２６に転送される。ただし、この要求制御メッセージの送信元ランクは、ランク＃２からランク＃２０に書き換えられる。

終点ノードであるノード１００−２６から始点ノードであるノード１００−２には、ノード１００−２０を経由せずに応答制御メッセージ１２６が送信される。応答制御メッセージ１２６は、メッセージ種別、ユーザバッファアドレス、送信側リクエスト識別子、受信側リクエスト識別子および受信側一時バッファアドレスを含む。

メッセージ種別は、応答制御メッセージ１２３と同様である。ユーザバッファアドレスは、データペイロードを受信するためにノード１００−２６に確保されたユーザバッファ１１２ｂのアドレスである。送信側リクエスト識別子は、要求制御メッセージ１２５に含まれていた識別子であり、ノード１００−２が付与した識別子である。受信側リクエスト識別子は、ｒｅｎｄｅｚｖｏｕｓ通信を識別するためにノード１００−２６が付与する識別子である。受信側一時バッファアドレスは、完了制御メッセージを受信するためにノード１００−２６に一時的に確保された受信バッファ１１４ｈのアドレスである。

始点ノードであるノード１００−２から終点ノードであるノード１００−２６には、ノード１００−２０を経由せずに完了制御メッセージ１２７が送信される。完了制御メッセージ１２７は、メッセージ種別および受信側リクエスト識別子を含む。メッセージ種別および受信側リクエスト識別子は、完了制御メッセージ１２４と同様である。

次に、各ノードの機能について説明する。
図１７は、ノードの機能例を示すブロック図である。
ノード１００は、通信バッファ領域１３１、ユーザバッファ領域１３２、初期化部１３３、送信処理部１３４、受信処理部１３５および中継制御部１３６を有する。通信バッファ領域１３１およびユーザバッファ領域１３２は、ＲＡＭ１０２上の記憶領域を用いて実装される。初期化部１３３、送信処理部１３４、受信処理部１３５および中継制御部１３６は、例えば、ＣＰＵ１０１が実行するプログラムモジュールを用いて実装される。他のノードも、ノード１００と同様のモジュール構成を有する。

通信バッファ領域１３１には、ノード間通信に使用されユーザプログラムからは認識されないバッファが確保される。通信バッファ領域１３１は、ノード１００に配置されたプロセス１つにつき、送信するメッセージを一時的に格納する１つの送信バッファと、受信したメッセージを一時的に格納する複数の受信バッファとを含む。通信バッファ領域１３１には、ｒｅｎｄｅｚｖｏｕｓ通信においてデータペイロードを中継するための一時バッファが確保されることがある。ユーザバッファ領域１３２には、ユーザプログラムから認識されるバッファが確保される。ユーザバッファ領域１３２は、送信するデータペイロードまたは受信したデータペイロードを格納するユーザバッファを含む。

初期化部１３３は、並列処理の開始時にＭＰＩライブラリの初期化を行う。初期化部１３３は、通信バッファ領域１３１に送信バッファを確保する。また、初期化部１３３は、並列処理に参加するプロセスを特定し、各プロセスのランクに基づいて同一グループ内のプロセスおよび他グループ内のパートナープロセスを判定する。初期化部１３３は、判定した同一グループ内のプロセスおよび他グループ内のパートナープロセスそれぞれに対して、個別の受信バッファを通信バッファ領域１３１に確保する。それ以外のプロセスに対応する受信バッファは、通信バッファ領域１３１に確保しなくてよい。

送信処理部１３４は、メッセージやデータペイロードの送信を行う。送信処理部１３４は、ノード１００に配置されたプロセスからのｅａｇｅｒ通信の要求に応じて、ユーザバッファ領域１３２の中の指定されたユーザバッファからデータペイロードを読み出し、データメッセージを生成する。また、送信処理部１３４は、中継制御部１３６からのｅａｇｅｒ通信の要求に応じて、到着したデータメッセージを取得してヘッダを書き換える。送信処理部１３４は、生成したデータメッセージを通信バッファ領域１３１の中の送信バッファに書き込み、送信バッファに格納されたメッセージを順に送信する。

また、送信処理部１３４は、ノード１００に配置されたプロセスまたは中継制御部１３６からのｒｅｎｄｅｚｖｏｕｓ通信の要求に応じて、各種の制御メッセージを生成する。送信処理部１３４は、生成した制御メッセージを通信バッファ領域１３１の中の送信バッファに書き込み、送信バッファに格納されたメッセージを順に送信する。また、送信処理部１３４は、ノード１００に配置されたプロセスからの要求に応じて、ユーザバッファ領域１３２の中の指定されたユーザバッファからデータペイロードを読み出し、データペイロードを送信する。また、送信処理部１３４は、中継制御部１３６からのｒｅｎｄｅｚｖｏｕｓ通信の要求に応じて、通信バッファ領域１３１の中の指定された一時バッファからデータペイロードを読み出し、データペイロードを送信することがある。

受信処理部１３５は、メッセージやデータペイロードの受信を行う。受信処理部１３５は、通信バッファ領域１３１の中の受信バッファを監視し、データメッセージが到着すると受信バッファからデータメッセージを読み出す。受信処理部１３５は、終点ランクがノード１００に配置されたプロセスのランクである場合、データメッセージに含まれるデータペイロードをユーザバッファ領域１３２の中のユーザバッファに書き込む。一方、受信処理部１３５は、終点ランクがノード１００に配置されたプロセスのランクでない場合、データメッセージの内容を中継制御部１３６に通知する。

また、受信処理部１３５は、通信バッファ領域１３１の中の受信バッファを監視し、制御メッセージが到着すると受信バッファから制御メッセージを読み出す。受信処理部１３５は、制御メッセージの内容を送信処理部１３４または中継制御部１３６に通知する。

中継制御部１３６は、メッセージやデータペイロードの中継を制御する。中継制御部１３６は、ノード１００が中継ノードとなるｅａｇｅｒ通信を検出すると、終点ランクのプロセスを判定し、終点ランクに対するデータメッセージの送信を送信処理部１３４に指示する。また、中継制御部１３６は、ノード１００が中継ノードとなるｒｅｎｄｅｚｖｏｕｓ通信を検出すると、終点ランクのプロセスを判定し、終点ランクに対する制御メッセージの送信を送信処理部１３４に指示する。また、第１のｒｅｎｄｅｚｖｏｕｓ通信方法では、中継制御部１３６は、データペイロードの転送を送信処理部１３４に指示する。

次に、各ノードの処理手順について説明する。以下では代表してノード１００の処理手順を説明するが、他のノードもノード１００と同様の処理を行う。
図１８は、初期化の手順例を示すフローチャートである。

（Ｓ１０）初期化部１３３は、並列処理に参加するプロセスの総数（ランク総数）と、ノード１００に配置されたプロセス１１１ｃのランク（自ランク）を取得する。ランク総数と自ランクは、ユーザプログラムの記述やノード間通信などを通じて決定される。

（Ｓ１１）初期化部１３３は、ステップＳ１０で取得した自ランクから、プロセス１１１ｃのグループ識別子（自グループＩＤ）とプロセス１１１ｃのグループ内識別子（自グループ内ＩＤ）とを算出する。前述のように、自グループＩＤは自ランクをＮ_ppgで割った商であり、自グループ内ＩＤは自ランクをＮ_ppgで割った余りである。

（Ｓ１２）初期化部１３３は、並列処理に参加する他プロセスのランク（他ランク）の中から１つ他ランクを選択する。選択可能な他ランクは、０以上かつランク総数−１以下の整数のうち自ランクと異なるものである。

（Ｓ１３）初期化部１３３は、ステップＳ１２で選択した他ランクから、他プロセスのグループ識別子（他ランクグループＩＤ）と他プロセスのグループ内識別子（他ランクグループ内ＩＤ）とを算出する。前述のように、他ランクグループＩＤは他ランクをＮ_ppgで割った商であり、他ランクグループ内ＩＤは他ランクをＮ_ppgで割った余りである。

（Ｓ１４）初期化部１３３は、ステップＳ１１の自グループＩＤとステップＳ１３の他ランクグループＩＤとを比較すると共に、ステップＳ１１の自グループ内ＩＤとステップＳ１３の他ランクグループ内ＩＤとを比較する。そして、初期化部１３３は、自グループＩＤと他ランクグループＩＤが同じか、または、自グループ内ＩＤと他ランクグループ内ＩＤとが同じであるか判断する。この条件を満たす場合、ステップＳ１５に処理が進む。この条件を満たさない場合、すなわち、自グループＩＤと他ランクグループＩＤが異なり、かつ、自グループ内ＩＤと他ランクグループ内ＩＤとが異なる場合、ステップＳ１６に処理が進む。

（Ｓ１５）初期化部１３３は、ステップＳ１２で選択した他ランク用の受信バッファを、通信バッファ領域１３１の中に確保する。
（Ｓ１６）初期化部１３３は、ステップＳ１２において全ての他ランクを選択したか判断する。全ての他ランクを選択した場合は初期化が終了し、未選択の他ランクがある場合はステップＳ１２に処理が進む。

図１９は、ｅａｇｅｒ通信の手順例を示すフローチャートである。
（Ｓ２０）送信処理部１３４は、プロセス１１１ｃからｅａｇｅｒ通信によるデータペイロードの送信要求を受け付けたか判断する。送信要求を受け付けた場合はステップＳ２１に処理が進み、それ以外の場合はステップＳ２４に処理が進む。

（Ｓ２１）送信処理部１３４は、プロセス１１１ｃの自ランクから、自グループＩＤと自グループ内ＩＤを算出する。また、送信処理部１３４は、プロセス１１１ｃによって指定された宛先ランクから、宛先グループＩＤと宛先グループ内ＩＤを算出する。宛先グループＩＤの算出方法は前述の他ランクグループＩＤと同様であり、宛先グループ内ＩＤの算出方法は前述の他ランクグループ内ＩＤと同様である。

（Ｓ２２）送信処理部１３４は、ステップＳ２１の自グループＩＤと宛先グループＩＤが同じか、または、ステップＳ２１の自グループ内ＩＤと宛先グループ内ＩＤとが同じであるか判断する。この条件を満たす場合、ステップＳ２８に処理が進む。この条件を満たさない場合、すなわち、自グループＩＤと宛先グループＩＤが異なり、かつ、自グループ内ＩＤと宛先グループ内ＩＤとが異なる場合、ステップＳ２３に処理が進む。

（Ｓ２３）送信処理部１３４は、宛先グループＩＤと自グループ内ＩＤとに基づいて中継プロセスのランクを決定する。中継プロセスは、宛先プロセスと同じグループに属するプロセスのうち、プロセス１１１ｃと同じグループ内ＩＤをもつパートナープロセスである。中継プロセスのランク＝宛先グループＩＤ×Ｎ_ppg＋自グループ内ＩＤと算出できる。ただし、上記の条件を満たすパートナープロセスが存在しない場合、送信処理部１３４は、プロセス１１１ｃが属するグループの中から、宛先プロセスと同じグループ内ＩＤをもつプロセスを中継プロセスとして選択する。送信処理部１３４は、決定した中継プロセスのランクを宛先ランクとする。また、送信処理部１３４は、プロセス１１１ｃから指定された宛先ランクを終点ランクとする。そして、ステップＳ２８に処理が進む。

（Ｓ２４）受信処理部１３５は、何れかの受信バッファにデータメッセージが到着したか判断する。データメッセージが到着した場合はステップＳ２５に処理が進み、データメッセージが到着していない場合は処理が終了する。

（Ｓ２５）受信処理部１３５は、到着したデータメッセージに含まれる終点ランクが自ランクであるか判断する。終点ランクが自ランクである場合はステップＳ２７に処理が進み、終点ランクが自ランクでない場合はステップＳ２６に処理が進む。

（Ｓ２６）中継制御部１３６は、終点ランクを新たな宛先ランクに決定し、データメッセージの転送を送信処理部１３４に指示する。そして、ステップＳ２８に処理が進む。
（Ｓ２７）受信処理部１３５は、到着したデータメッセージに含まれるデータペイロードをユーザバッファに書き込む。このとき、受信処理部１３５はプロセス１１１ｃからｅａｇｅｒ通信によるデータペイロードの受信要求を受け付けており、この受信要求によってユーザバッファが指定されている。そして、処理が終了する。

（Ｓ２８）送信処理部１３４は、データペイロードにヘッダを付したデータメッセージを、送信バッファ１１３ｄに書き込む。プロセス１１１ｃからの要求に応じてデータメッセージを送信する場合、送信処理部１３４は、プロセス１１１ｃによって指定されたユーザバッファからデータペイロードを読み出してヘッダを付加する。このとき、ヘッダの送信元ランクおよび始点ランクは自ランクであり、終点ランクはプロセス１１１ｃによって指定された宛先ランクである。データメッセージを転送する場合、送信処理部１３４はヘッダを書き換える。このとき、ヘッダの送信元ランクは自ランクであり、始点ランクおよび終点ランクは元のデータメッセージのままである。

（Ｓ２９）送信処理部１３４は、送信バッファ１１３ｄに格納されたデータメッセージを、宛先ランクに対応するノード（宛先ノード）が有する受信バッファのうち自ランク用の受信バッファ宛てに送信する。送信処理部１３４は、データメッセージの送信時に、宛先となる受信バッファのアドレスを指定する。自ランク用の受信バッファのアドレスは、ＭＰＩライブラリの初期化時のノード間通信を通じて予め知っている。自ランクが始点ランクであり中継プロセスが存在しない場合、宛先ランクは終点ランクと一致する。自ランクが始点ランクであり中継プロセスが存在する場合、宛先ランクは中継プロセスのランクである。自ランクが始点ランクでない場合、宛先ランクは終点ランクである。

図２０は、ｒｅｎｄｅｚｖｏｕｓ通信の手順例を示す第１のフローチャートである。
ここでは、第１のｒｅｎｄｅｚｖｏｕｓ通信方法を説明する。
（Ｓ３０）送信処理部１３４は、プロセス１１１ｃからｒｅｎｄｅｚｖｏｕｓ通信によるデータペイロードの送信要求を受け付けたか判断する。送信要求を受け付けた場合はステップＳ３１に処理が進み、それ以外の場合はステップＳ４０に処理が進む。

（Ｓ３１）送信処理部１３４は、プロセス１１１ｃの自ランクから、自グループＩＤと自グループ内ＩＤを算出する。また、送信処理部１３４は、プロセス１１１ｃによって指定された宛先ランクから、宛先グループＩＤと宛先グループ内ＩＤを算出する。

（Ｓ３２）送信処理部１３４は、ステップＳ３１の自グループＩＤと宛先グループＩＤが同じか、または、ステップＳ３１の自グループ内ＩＤと宛先グループ内ＩＤとが同じであるか判断する。この条件を満たす場合、ステップＳ３４に処理が進む。この条件を満たさない場合、すなわち、自グループＩＤと宛先グループＩＤが異なり、かつ、自グループ内ＩＤと宛先グループ内ＩＤとが異なる場合、ステップＳ３３処理が進む。

（Ｓ３３）送信処理部１３４は、宛先グループＩＤと自グループ内ＩＤとに基づいて中継プロセスのランクを決定する。中継プロセスのランク＝宛先グループＩＤ×Ｎ_ppg＋自グループ内ＩＤと算出できる。ただし、上記の条件を満たす中継プロセスが存在しない場合、送信処理部１３４は、プロセス１１１ｃが属するグループの中から、宛先プロセスと同じグループ内ＩＤをもつプロセスを中継プロセスとして選択する。送信処理部１３４は、決定した中継プロセスのランクを宛先ランクとする。また、送信処理部１３４は、プロセス１１１ｃから指定された宛先ランクを終点ランクとする。

（Ｓ３４）送信処理部１３４は、要求制御メッセージを生成して送信バッファ１１３ｄに書き込む。要求制御メッセージの送信元ランクは自ランクであり、送信側リクエスト識別子は送信処理部１３４が指定した識別子である。プロセス１１１ｃの要求に応じてデータペイロードを送信する場合、始点ランクは自ランクであり、終点ランクはプロセス１１１ｃによって指定された宛先ランクである。データペイロードを転送する場合、始点ランクおよび終点ランクは元の要求制御メッセージと同じである。

（Ｓ３５）送信処理部１３４は、送信バッファ１１３ｄに格納された要求制御メッセージを、宛先ランクに対応する宛先ノードが有する受信バッファのうち自ランク用の受信バッファ宛てに送信する。このとき、自ランクが始点ランクであり中継プロセスが存在しない場合、宛先ランクは終点ランクと一致する。自ランクが始点ランクであり中継プロセスが存在する場合、宛先ランクは中継プロセスのランクである。自ランクが始点ランクでない場合、宛先ランクは終点ランクである。

（Ｓ３６）受信処理部１３５は、ステップＳ３５の宛先ランク用の受信バッファに応答制御メッセージが到着したことを検出する。
（Ｓ３７）送信処理部１３４は、送信するデータペイロードを読み出す。自ランクが始点ランクである場合、送信処理部１３４は、プロセス１１１ｃによって指定されたユーザバッファからデータペイロードを読み出す。自ランクが始点ランクでない場合、送信処理部１３４は、一時バッファから転送すべきデータペイロードを読み出す。そして、送信処理部１３４は、ステップＳ３６の応答制御メッセージによって指定されたバッファ宛てにデータペイロードを送信する。宛先ランクが終点ランクである場合、応答制御メッセージによって指定されるバッファはユーザバッファである。宛先ランクが終点ランクでない場合、応答制御メッセージによって指定されるバッファは一時バッファである。

（Ｓ３８）送信処理部１３４は、完了制御メッセージを生成して送信バッファ１１３ｄに書き込む。完了制御メッセージの受信側リクエスト識別子は、ステップＳ３６の応答制御メッセージに含まれている受信側リクエスト識別子と同じである。

（Ｓ３９）送信処理部１３４は、送信バッファ１１３ｄに格納された完了制御メッセージを、ステップＳ３５と同じ受信バッファ宛てに送信する。そして、処理が終了する。
図２１は、ｒｅｎｄｅｚｖｏｕｓ通信の手順例を示す第２のフローチャートである。

（Ｓ４０）受信処理部１３５は、何れかの受信バッファに要求制御メッセージが到着したか判断する。要求制御メッセージが到着した場合はステップＳ４１に処理が進み、要求制御メッセージが到着していない場合は処理が終了する。

（Ｓ４１）受信処理部１３５は、到着した要求制御メッセージに含まれる終点ランクが自ランクであるか判断する。終点ランクが自ランクである場合はステップＳ４３に処理が進み、終点ランクが自ランクでない場合はステップＳ４２に処理が進む。

（Ｓ４２）受信処理部１３５は、データペイロード用の一時バッファを確保する。
（Ｓ４３）送信処理部１３４は、応答制御メッセージを生成して送信バッファ１１３ｄに書き込む。応答制御メッセージの送信側リクエスト識別子は、ステップＳ４０の要求制御メッセージに含まれている送信側リクエスト識別子と同じである。受信側リクエスト識別子は、受信処理部１３５が指定した識別子である。終点ランクが自ランクである場合、ユーザバッファアドレスは、プロセス１１１ｃによって指定されたユーザバッファのアドレスである。このとき、受信処理部１３５はプロセス１１１ｃからｒｅｎｄｅｚｖｏｕｓ通信によるデータペイロードの受信要求を受け付けており、この受信要求によってユーザバッファが指定されている。終点ランクが自ランクでない場合、ユーザバッファアドレスはステップＳ４２で確保した一時バッファのアドレスである。

（Ｓ４４）送信処理部１３４は、送信バッファ１１３ｄに格納された応答制御メッセージを、要求制御メッセージに含まれている送信元ランクに対応するノード（送信元ノード）が有する受信バッファのうち自ランク用の受信バッファ宛てに送信する。

（Ｓ４５）受信処理部１３５は、ステップＳ４４の送信元ランク用の受信バッファ（ステップＳ４０と同じ受信バッファ）に完了制御メッセージが到着したことを検出する。
（Ｓ４６）受信処理部１３５は、ステップＳ４０の要求制御メッセージに含まれる終点ランクが自ランクであるか判断する。終点ランクが自ランクである場合はｒｅｎｄｅｚｖｏｕｓ通信が終了し、終点ランクが自ランクでない場合はステップＳ４７に処理が進む。

（Ｓ４７）中継制御部１３６は、終点ランクを新たな宛先ランクに決定し、データペイロードの転送を送信処理部１３４に指示する。そして、ステップＳ３４に処理が進む。
図２２は、ｒｅｎｄｅｚｖｏｕｓ通信の手順例を示す第３のフローチャートである。

ここでは、第２のｒｅｎｄｅｚｖｏｕｓ通信方法を説明する。
（Ｓ５０）送信処理部１３４は、プロセス１１１ｃからｒｅｎｄｅｚｖｏｕｓ通信によるデータペイロードの送信要求を受け付けたか判断する。送信要求を受け付けた場合はステップＳ５１に処理が進み、それ以外の場合はステップＳ６２に処理が進む。

（Ｓ５１）受信処理部１３５は、受信バッファを一時的に確保する。
（Ｓ５２）送信処理部１３４は、プロセス１１１ｃの自ランクから、自グループＩＤと自グループ内ＩＤを算出する。また、送信処理部１３４は、プロセス１１１ｃによって指定された宛先ランクから、宛先グループＩＤと宛先グループ内ＩＤを算出する。

（Ｓ５３）送信処理部１３４は、ステップＳ５２の自グループＩＤと宛先グループＩＤが同じか、または、ステップＳ５２の自グループ内ＩＤと宛先グループ内ＩＤとが同じであるか判断する。この条件を満たす場合、ステップＳ５５に処理が進む。この条件を満たさない場合、すなわち、自グループＩＤと宛先グループＩＤが異なり、かつ、自グループ内ＩＤと宛先グループ内ＩＤとが異なる場合、ステップＳ５４に処理が進む。

（Ｓ５４）送信処理部１３４は、宛先グループＩＤと自グループ内ＩＤとに基づいて中継プロセスのランクを決定する。中継プロセスのランク＝宛先グループＩＤ×Ｎ_ppg＋自グループ内ＩＤと算出できる。ただし、上記の条件を満たす中継プロセスが存在しない場合、送信処理部１３４は、プロセス１１１ｃが属するグループの中から、宛先プロセスと同じグループ内ＩＤをもつプロセスを中継プロセスとして選択する。送信処理部１３４は、決定した中継プロセスのランクを宛先ランクとする。また、送信処理部１３４は、プロセス１１１ｃから指定された宛先ランクを終点ランクとする。

（Ｓ５５）送信処理部１３４は、要求制御メッセージを生成して送信バッファ１１３ｄに書き込む。要求制御メッセージの送信元ランクおよび始点ランクは自ランクであり、送信側リクエスト識別子は送信処理部１３４が指定した識別子であり、終点ランクはプロセス１１１ｃによって指定された宛先ランクである。送信側一時バッファアドレスは、ステップＳ５１で確保した受信バッファのアドレスである。

（Ｓ５６）送信処理部１３４は、送信バッファ１１３ｄに格納された要求制御メッセージを、宛先ランクに対応する宛先ノードが有する受信バッファのうち自ランク用の受信バッファ宛てに送信する。中継プロセスが存在しない場合、宛先ランクは終点ランクと一致する。中継プロセスが存在する場合、宛先ランクは中継プロセスのランクである。

（Ｓ５７）受信処理部１３５は、ステップＳ５１で確保した受信バッファに応答制御メッセージが到着したことを検出する。
（Ｓ５８）送信処理部１３４は、プロセス１１１ｃによって指定されたユーザバッファからデータペイロードを読み出し、ステップＳ５７の応答制御メッセージによって指定されたユーザバッファ宛てにデータペイロードを送信する。

（Ｓ５９）送信処理部１３４は、完了制御メッセージを生成して送信バッファ１１３ｄに書き込む。完了制御メッセージの受信側リクエスト識別子は、ステップＳ５７の応答制御メッセージに含まれている受信側リクエスト識別子と同じである。

（Ｓ６０）送信処理部１３４は、送信バッファ１１３ｄに格納された完了制御メッセージを、応答制御メッセージによって指定された受信バッファ宛てに送信する。
（Ｓ６１）受信処理部１３５は、ステップＳ５１の受信バッファを解放する。そして、処理が終了する。

図２３は、ｒｅｎｄｅｚｖｏｕｓ通信の手順例を示す第４のフローチャートである。
（Ｓ６２）受信処理部１３５は、何れかの受信バッファに要求制御メッセージが到着したか判断する。要求制御メッセージが到着した場合はステップＳ６３に処理が進み、要求制御メッセージが到着していない場合は処理が終了する。

（Ｓ６３）受信処理部１３５は、到着した要求制御メッセージに含まれる終点ランクが自ランクであるか判断する。終点ランクが自ランクである場合はステップＳ６７に処理が進み、終点ランクが自ランクでない場合はステップＳ６４に処理が進む。

（Ｓ６４）中継制御部１３６は、終点ランクを新たな宛先ランクに決定し、データペイロードの転送を送信処理部１３４に指示する。
（Ｓ６５）送信処理部１３４は、要求制御メッセージを送信バッファ１１３ｄに書き込む。要求制御メッセージの送信元ランクは自ランクである。送信側リクエスト識別子、始点ランク、終点ランクおよび送信側一時バッファアドレスは、元の要求制御メッセージと同じである。すなわち、実質的に元の要求制御メッセージの内容が転送される。

（Ｓ６６）送信処理部１３４は、送信バッファ１１３ｄに格納された要求制御メッセージを、宛先ランクに対応する宛先ノードが有する受信バッファのうち自ランク用の受信バッファ宛てに送信する。そして、処理が終了する。

（Ｓ６７）受信処理部１３５は、受信バッファを一時的に確保する。
（Ｓ６８）送信処理部１３４は、応答制御メッセージを生成して送信バッファ１１３ｄに書き込む。応答制御メッセージの送信側リクエスト識別子は、ステップＳ６２の要求制御メッセージに含まれている送信側リクエスト識別子と同じである。受信側リクエスト識別子は、受信処理部１３５が指定した識別子である。ユーザバッファアドレスは、プロセス１１１ｃによって指定されたユーザバッファのアドレスである。受信側一時バッファアドレスは、ステップＳ６７で確保した受信バッファのアドレスである。

（Ｓ６９）送信処理部１３４は、送信バッファ１１３ｄに格納された応答制御メッセージを、要求制御メッセージに含まれている送信側一時バッファアドレスが示す受信バッファ宛てに送信する。この受信バッファは、要求制御メッセージに含まれている始点ランクに対応するノード（始点ノード）が有する受信バッファである。

（Ｓ７０）受信処理部１３５は、ステップＳ６７で確保した受信バッファに完了制御メッセージが到着したことを検出する。
（Ｓ７１）受信処理部１３５は、ステップＳ６７の受信バッファを解放する。

第２の実施の形態の並列処理装置によれば、各ノードには同一グループに属するプロセス用の受信バッファおよび他グループのパートナープロセス用の受信バッファをＲＡＭに確保すればよく、それ以外の受信バッファを恒常的に確保しておかなくてよい。よって、受信バッファの数を削減することができ、ＲＡＭ領域の使用量を削減できる。また、各プロセスのランクからグループ識別子とグループ内識別子が算出され、グループ識別子とグループ内識別子に基づいて何れのプロセス用の受信バッファを確保すればよいか判定される。よって、各ノードが独立に確保すべき受信バッファを判定できる。

また、原則として、送信元プロセスと同じグループ内識別子をもつパートナープロセスが中継プロセスとして選択される。よって、メッセージを転送するノードを分散させることができ、特定のノードにメッセージが集中することを抑制できる。その結果、特定のノードがボトルネックとなって並列処理装置の性能が低下することを抑制できる。また、第２のｒｅｎｄｅｚｖｏｕｓ通信方法によれば、中継プロセスをもつノードは要求制御メッセージのみを転送すればよく、他の制御メッセージおよびデータペイロードは始点ノードと終点ノードの間で直接送信される。よって、メッセージの送信回数を削減できる。

１０ 並列処理装置
１１，１１−１，１１−２，１１−３ ノード
１２ メモリ
１３ プロセッサ
１４ａ，１４ｂ 受信バッファ
１５，１５−１ グループ

Claims (7)

1. 複数のノードのうちの第１のノードとして用いられるコンピュータに、
   前記複数のノードのうち前記第１のノードと同じ第１のグループに属する１以上の第２のノードを決定し、前記１以上の第２のノードそれぞれに対して前記第１のノードが有するメモリ上に第１の受信バッファを確保し、
   前記複数のノードのうち第２のグループに属する第３のノードおよび１以上の第４のノードを決定し、前記第３のノードに対して前記メモリ上に第２の受信バッファを確保すると共に前記１以上の第４のノードに対しては前記メモリ上の受信バッファを省略し、
   前記１以上の第２のノードのうちの１つの第２のノードと通信する場合、前記１つの第２のノードに対応する前記第１の受信バッファをメッセージの受信に使用させ、前記第３のノードと通信する場合、前記第２の受信バッファをメッセージの受信に使用させ、前記１以上の第４のノードのうちの１つの第４のノードと通信する場合、前記第１の受信バッファまたは前記第２の受信バッファをメッセージの受信に使用させる、
   処理を実行させるノード間通信プログラム。
2. 前記複数のノードそれぞれに識別子が割り当てられ、
   前記第３のノードは、前記第１のノードの前記識別子および前記第２のグループに属する各ノードの前記識別子に基づいて前記第２のグループの中から選択される、
   請求項１記載のノード間通信プログラム。
3. 前記コンピュータに更に、前記複数のノードそれぞれに対してグループ識別子およびグループ内識別子を算出する処理を実行させ、
   前記１以上の第２のノードは前記グループ識別子が前記第１のノードと同じノードであり、前記第３のノードは前記グループ識別子が前記第１のノードと異なり前記グループ内識別子が前記第１のノードと同じノードであり、前記１以上の第４のノードは前記グループ識別子および前記グループ内識別子が前記第１のノードと異なるノードである、
   請求項１記載のノード間通信プログラム。
4. 前記コンピュータに更に、前記１つの第２のノードとは直接通信し、前記第３のノードとは直接通信し、前記１つの第４のノードとは前記１つの第２のノードまたは前記第３のノードを経由して通信するよう制御する処理を実行させる、
   請求項１記載のノード間通信プログラム。
5. 前記コンピュータに更に、
   前記１つの第４のノードによって生成された第１のメッセージが前記１つの第２のノードを経由して前記第１の受信バッファに到着するか、または、前記第１のメッセージが前記第３のノードを経由して前記第２の受信バッファに到着した場合、前記１つの第４のノードに対して前記メモリ上に第３の受信バッファを一時的に確保し、
   前記第１のメッセージに関連する第２のメッセージを、前記第３の受信バッファを用いて前記１つの第４のノードから直接受信することを許容する、
   処理を実行させる請求項１記載のノード間通信プログラム。
6. メモリおよびプロセッサを有する第１のノードと、
   前記第１のノードとネットワークで接続された複数の他のノードとを有し、
   前記プロセッサは、
   前記複数の他のノードのうち前記第１のノードと同じ第１のグループに属する１以上の第２のノードを決定し、前記１以上の第２のノードそれぞれに対して前記メモリ上に第１の受信バッファを確保し、
   前記複数の他のノードのうち第２のグループに属する第３のノードおよび１以上の第４のノードを決定し、前記第３のノードに対して前記メモリ上に第２の受信バッファを確保すると共に前記１以上の第４のノードに対しては前記メモリ上の受信バッファを省略し、
   前記１以上の第２のノードのうちの１つの第２のノードと通信する場合、前記１つの第２のノードに対応する前記第１の受信バッファをメッセージの受信に使用させ、前記第３のノードと通信する場合、前記第２の受信バッファをメッセージの受信に使用させ、前記１以上の第４のノードのうちの１つの第４のノードと通信する場合、前記第１の受信バッファまたは前記第２の受信バッファをメッセージの受信に使用させる、
   並列処理装置。
7. 並列処理装置が有する複数のノードのうちの第１のノードが、
   前記複数のノードのうち前記第１のノードと同じ第１のグループに属する１以上の第２のノードを決定し、前記１以上の第２のノードそれぞれに対して前記第１のノードが有するメモリ上に第１の受信バッファを確保し、
   前記複数のノードのうち第２のグループに属する第３のノードおよび１以上の第４のノードを決定し、前記第３のノードに対して前記メモリ上に第２の受信バッファを確保すると共に前記１以上の第４のノードに対しては前記メモリ上の受信バッファを省略し、
   前記１以上の第２のノードのうちの１つの第２のノードと通信する場合、前記１つの第２のノードに対応する前記第１の受信バッファをメッセージの受信に使用し、前記第３のノードと通信する場合、前記第２の受信バッファをメッセージの受信に使用し、前記１以上の第４のノードのうちの１つの第４のノードと通信する場合、前記第１の受信バッファまたは前記第２の受信バッファをメッセージの受信に使用する、
   ノード間通信方法。

Images