(57)【要約】【課題】バリア同期にかかる時間を短縮した情報処理システム及び情報処理システムの制御方法を提供する。【解決手段】ノード１０は、他のノード１２へ信号を送信する送信部１０１と、他のノード１１から信号を受信する受信部１０２と、送信部１０１が信号を他のノード１１へ送信した場合、ノード１１との間で同期が確立したと判定し、受信部１０２が他のノード１２から信号を受信した場合、ノード１２との間で同期が確立したと判定し、さらに、同期が確立したと判定したノード１１及び１２との間で既に同期が確立したノードがある場合、当該ノードとの間でも同期が確立したと判定する判定部１０４と、判定部１０４により同期が確立したと判定されていない情報処理装置を信号の送信先のノード１１として選択する選択部１０３とを有する。【選択図】図３
2015036943.tif 000002
【特許請求の範囲】
【請求項１】
複数の情報処理装置を有する情報処理システムであって、
前記情報処理装置は、
他の情報処理装置へ信号を送信する送信部と、
他の情報処理装置から信号を受信する受信部と、
前記送信部が信号を他の情報処理装置へ送信した場合、送信先の情報処理装置との間で同期が確立したと判定し、前記受信部が他の情報処理装置から信号を受信した場合、送信元の情報処理装置との間で同期が確立したと判定し、さらに、同期が確立したと判定した情報処理装置との間で既に同期が確立した情報処理装置がある場合、当該情報処理装置との間でも同期が確立したと判定する判定部と、
前記判定部により同期が確立したと判定されていない情報処理装置を信号の送信先の情報処理装置として選択する選択部と
を備えたことを特徴とする情報処理システム。
【請求項２】
前記送信部は、前記送信先の情報処理装置から受信準備が完了した情報を受信すると、前記送信先の情報処理装置へ信号を送信することを特徴とする請求項１に記載の情報処理システム。
【請求項３】
前記選択部は、前記判定部により同期が確立したと判定されていない情報処理装置であり、且つ自装置と同期が確立していない情報処理装置との間で同期を確立した情報処理装置を信号の送信先の情報処理装置として選択することを特徴とする請求項１又は請求項２に記載の情報処理システム。
【請求項４】
複数の前記情報処理装置は、０から連番の識別番号が振られており、
前記選択部は、前記送信先の情報処理装置の選択を実行した回数で３をべき乗した数に、自装置の識別番号に加算した値を、情報処理装置の総数で割った剰余を識別番号として有する情報処理装置を送信先の情報処理装置とする
ことを特徴とする請求項１〜３のいずれか一つに記載の情報処理システム。
【請求項５】
複数の前記情報処理装置は、０から連番の識別番号が振られており、
前記選択部は、前記送信先の情報処理装置の選択を実行した回数で３をべき乗した数を、自装置の識別番号から減算した値を、前記情報処理装置の総数で割った剰余を識別番号として有する情報処理装置を送信先の情報処理装置とする
ことを特徴とする請求項１〜３のいずれか一つに記載の情報処理システム。
【請求項６】
複数の前記情報処理装置は、自装置を含む３つのノードが属するグループをそれぞれ形成し、
前記選択部は、自装置が属するグループである自グループにおける他の情報処理装置の一方へ信号を送信し、且つ他方から信号を受信するように前記送信先の情報処理装置を選択し、自グループ内での同期終了後、自装置と同期が確立していない情報処理装置が属する未選択グループの中から２つのグループを選択し、選択した各グループに属する情報処理装置と自グループの各情報処理装置とが１対１になるように、各グループから１つずつ情報処理装置を選択し、選択した情報処理装置の片方へ信号を送信し、且つ、他方のノードから信号を受信するように前記送信先の情報処理装置を選択する
ことを特徴とする請求項１〜３のいずれか一つに記載の情報処理システム。
【請求項７】
複数の情報処理装置を有する情報処理システムの制御方法であって、
前記情報処理装置に、
同期が確立していない情報処理装置を信号の送信先の情報処理装置として選択させ、
前記送信先の情報処理装置に信号を送信させ、
送信先の情報処理装置から信号を受信させ、
自装置を送信先の情報処理装置として選択した情報処理装置から信号を受信させ、
前記送信先の情報処理装置へ信号を送信した場合、送信先の情報処理装置との間で同期が確立したと判定させ、
自装置を送信先の情報処理装置として選択した情報処理装置から信号を受信した場合、送信元の情報処理装置との間で同期が確立したと判定させ、
さらに、同期が確立したと判定した情報処理装置との間で既に同期が確立した情報処理装置がある場合、当該情報処理装置との間でも同期が確立したと判定させ、
複数の前記ノードの全てとの間で同期が確立するまで、前記信号の送受信及び同期確立の判定を繰り返させる
ことを特徴とする情報処理システムの制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理システム及び情報処理システムの制御方法に関する。
【背景技術】
【０００２】
情報処理システムである並列計算機システムにおいて、複数のノード間で並列処理されている複数のプロセス間の同期をとる方法として、バリア同期が知られている。バリア同期では同期をとる同期ポイントがプロセスの処理の進行段階に応じて設定される。バリア同期を行なうプロセスは、同期ポイントにプロセスの処理が到達した場合、プロセスの処理を一時的に停止することにより他のノードにおけるプロセスの処理の進行を待ち合わせる。バリア同期を行うプロセスは、並列処理されているバリア同期を行うプロセスの全てが同期ポイントに到着した時点で、待ち合わせ状態を終了して停止した処理を再開する。これにより、複数のノード間で並列処理されている複数のプロセス間で、並列処理の同期をとることができる。
【０００３】
バリア同期装置においては、例えば、２つのノードが組になりメッセージを交換することを繰り返し、全ノードが同期ポイントに到達したことを確認する従来技術がある。例えば、２つのノード毎にグルーピングして同一グループの相手ノードとの間でデータ送受信が行えた場合に、グループピングされたノード同士が同期ポイントに達したと判定する。そして、各グループの特定のノードが次のグループの特定のノードとの間でデータ送受信が行えた場合、相手グループとの間で同期ポイントに達したと判定する。そして、全てのノードが同期ポイントに達するまでこの工程を繰り返す。
【０００４】
このようにバリア同期を行った場合、ノード数をＮとすると、バリア同期にかかる時間はｌｏｇ２Ｎに比例する。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開平０７−１５２７１２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、２つのノードを組として同期を繰り返す従来技術では、ノード数が大きくなるほど、バリア同期の時間が処理全体の実行時間に占める割合が大きくなり、バリア同期が処理のボトルネックとなる。特に、最近のスーパーコンピュータなどにおいては、ノード数が数千〜数万というものもあり、さらにノード数は増加傾向にあるため、バリア同期にかかる時間は増加の一途をたどっている。
【０００７】
開示の技術は、上記に鑑みてなされたものであって、バリア同期にかかる時間を短縮した情報処理システム及び情報処理システムの制御方法を提供することを目的とする。
【課題を解決するための手段】
【０００８】
本願の開示する情報処理システム及び情報処理システムの制御方法は、一つの態様において、複数の情報処理装置を有する。そして、前記情報処理装置は以下の各部を有する。送信部は、他の情報処理装置へ信号を送信する。受信部は、他の情報処理装置から信号を受信する。判定部は、前記送信部が信号を他の情報処理装置へ送信した場合、送信先の情報処理装置との間で同期が確立したと判定し、前記受信部が他の情報処理装置から信号を受信した場合、送信元の情報処理装置との間で同期が確立したと判定し、さらに、同期が確立したと判定した情報処理装置との間で既に同期が確立した情報処理装置がある場合、当該情報処理装置との間でも同期が確立したと判定する。選択部は、前記判定部により同期が確立したと判定されていない情報処理装置を信号の送信先の情報処理装置として選択する。
【発明の効果】
【０００９】
本願の開示する情報処理システム及び情報処理システムの制御方法の一つの態様によれば、バリア同期にかかる時間を短縮することができるという効果を奏する。
【図面の簡単な説明】
【００１０】
【図１】図１は、実施例１に係る情報処理システムの構成図である。
【図２】図２は、バリア同期処理を含むプログラム実行の処理の概要を説明するための図である。
【図３】図３は、実施例１に係るノードの詳細を表すブロック図である。
【図４】図４は、同期用の信号の送信について説明するための図である。
【図５】図５は、実施例１に係る情報処理システムによる送信先ノードの選択の一例を表す図である。
【図６】図６は、実施例１に係る情報処理システムによるバリア同期処理のフローチャートである。
【図７Ａ】図７Ａは、実施例２に係る情報処理システムにおけるＮ＝９の場合の１ステップ目の同期用の信号の送信状態を表す図である。
【図７Ｂ】図７Ｂは、実施例２に係る情報処理システムにおけるＮ＝９の場合の２ステップ目の同期用の信号の送信状態を表す図である。
【図８】図８は、ノードの構成の他の例を示す図である。
【発明を実施するための形態】
【００１１】
以下に、本願の開示する情報処理システム及び情報処理システムの制御方法の実施例を図面に基づいて詳細に説明する。なお、以下の実施例により本願の開示する情報処理システム及び情報処理システムの制御方法が限定されるものではない。
【実施例１】
【００１２】
図１は、実施例１に係る情報処理システムの構成図である。図１に示すように、情報処理システム１は、複数のノード１０を有する。そして、各ノード１０は、ネットワーク２で相互に接続されている。情報処理システム１は、例えば、並列計算機システムである。そして、ノード１０は、情報処理装置の一例である。
【００１３】
ノード１０は、１つのOperating  System（ＯＳ）が動作する情報処理部としてのCentral  Processing  Unit（ＣＰＵ）や記憶部としてのメモリを含む情報処理装置である。ノード１０は、少なくともメインメモリと１つ以上のＣＰＵを有する。
【００１４】
本実施例では、ノード１０は、メモリ１１２及び１１５、ＣＰＵ１１３及び１１４、並びに、ネットワークインタフェースカード（Network  Inter  Face  Card：ＮＩＣ）１１１を有する。
【００１５】
ＣＰＵ１１３とＣＰＵ１１４とは相互に接続されており、データの送受信が可能である。また、メモリ１１２は、ＣＰＵ１１３に接続されている。また、メモリ１１５は、ＣＰＵ１１４に接続されている。さらに、ネットワークインタフェースカード１１１は、ＣＰＵ１１３に接続されている。本実施例では、ＣＰＵ１１４は、ＣＰＵ１１３を介して、ネットワークインタフェースカード１１１と通信を行う。
【００１６】
ネットワークインタフェースカード１１１は、ネットワーク２に接続する。本実施例に係るネットワークインタフェースカード１１１は、InfiniBandを用いて通信を行う。InfiniBandのようなインターコネクトでは、データの送信前に、データの送信先の受信準備ができているか否かの情報の授受をハードウェアレベルで行っている。例えば、ネットワークインタフェースカード１１１は、送信先の受信バッファに空きができたという情報が送信先のネットワークインタフェースカード１１１から届くまでパケットの送信を行わない。
【００１７】
ここで、本実施例では、ネットワークインタフェースカード１１１は、InfiniBandを用いて通信を行うが、これに限らない。すなわち、ネットワークインタフェースカード１１１は、ノード間ネットワークのインタフェースとして、データの送信先の受信準備ができているかをデータの送信前に確認できる通信インタフェースを有していればよい。言い換えれば、ネットワークインタフェースカード１１１は、クレジットベースのフロー制御を採用したインタフェースをノード間ネットワークに用いるものであればよい。
【００１８】
ここで、InfiniBandを用いて通信について説明する。InfiniBandを用いた通信には、Send/ReceiveとRemote  Direct  Memory  Access(RDMA)writeという２つの方式がある。Send/Receiveでは、受信側のノード１０がReceiveをしていないと、送信完了できない。受信側のノード１０がReceiveしない場合、Nackが送信側のノード１０へ送信されて、送信側のノード１０が再送信を行う。この場合、例えば、４Ｂ送信時のレイテンシは、４．８μｓｅｃである。また、RDMAwiteでは、相手側の準備の有無に関らず送信側のノード１０はデータを送信できる。この場合、例えば、４Ｂ送信時のレイテンシは、３．８μｓｅｃである。情報処理システム１においてSend/ReceiveとRDMAwriteのどちらを用いるかは、設計者が選択することができる。
【００１９】
そして、各ノード１０は、ネットワークインタフェースカード１１１及びネットワーク２を介して、データの送受信が可能である。
【００２０】
また、各ノード１０には、識別情報（Identification：ＩＤ）が振られる。具体的には、最初に各ノード１０のＣＰＵ１１３及び１１４がプログラムを実行するにあたり、各ノードＩＤにどのプロセスが割当てられているかの情報がすべてのノード１０に送られる。そして、各ＣＰＵ１１３及び１１４が実行するプロセスは、このノードＩＤとプロセスとの対応の情報を参照することで、どのノードに何のＩＤが振られているかを取得することができる。
【００２１】
図２は、バリア同期処理を含むプログラム実行の処理の概要を説明するための図である。図２の縦軸上に配置されたブロックは、それぞれ異なるノード１０が行う処理を表す。また、縦軸は下に行くにしたがって、時間の経過を表す。
【００２２】
各ノード１０はプログラムを実行する。全てのノード１０は協働してプログラムを実行する。そして、各ノード１０は、ステップＳ１０１〜Ｓ１０４に示すように、プログラムのコード中の同期ポイントに到達する。ここで、各ノード１０は異なる処理を実行することなどにより、ステップＳ１０１〜Ｓ１０４に示すように、同期ポイントに到達するタイミングが異なる場合がある。
【００２３】
そして、各ノード１０は、同期ポイントに到達すると、バリア同期処理を行い、全てのノード１０の間で同期をとる。ここで、上述したように、各ノード１０において同期ポイントへの到達タイミングが異なる場合があるので、全てのノード１０の間で同期をとるためには、早く同期ポイントに到達したノード１０は、後から同期ポイントに到達したノード１０との同期まで待機することになる。
【００２４】
そして、全てのノード１０の間で同期が取れると、バリア同期処理が終了し、タイミング２００でバリア同期が取られた各ノード１０においてプログラムの実行が継続される。
【００２５】
このように、ノード１０は、バリア同期処理が完了するまで待機する。そのため、バリア同期処理の時間を短縮することができ、情報処理システム１における処理時間の短縮に大きく寄与する。そこで、次に、バリア同期処理を行うノード１０の詳細について説明する。
【００２６】
図３は、実施例１に係るノードの詳細を表すブロック図である。図３に示すように、ノード１０は、送信部１０１、受信部１０２、選択部１０３及び判定部１０４を有する。送信部１０１及び受信部１０２は、ネットワークインタフェースカード１１１によりその機能が実現される。また、選択部１０３及び判定部１０４は、ＣＰＵ１１３及び１１４、並びに、メモリ１１２及び１１５によりその機能が実現される。
【００２７】
また、ここでは、ノード１０が同期用の信号を送信する送信先ノードをノード１１とする。また、ノード１０が同期用の信号を受信する送信元ノードをノード１２とする。
【００２８】
送信部１０１は、選択部１０３により送信先ノードとして選択されたノード１１の識別情報を選択部１０３から受信する。
【００２９】
送信部１０１は、同期ポイントに到達したことを既に確認済みの他のノードのＩＤを判定部１０４から取得する。そして、送信部１０１は、同期ポイントに到達したことを既に確認済みの他のノードのＩＤを含む同期用の信号を生成する。
【００３０】
その後、送信部１０１は、受信したＩＤを有するノード１１から受信準備が完了した旨の通知を受信するまで待機する。そして、ノード１１から受信準備が完了した旨の通知を受信すると、送信部１０１は、ノード１１に対して、同期用の信号を送信する。さらに、送信部１０１は、同期用の信号を送信先のノード１１のＩＤを判定部１０４へ通知する。
【００３１】
送信部１０１は、全てのノード１０が同期ポイントに到達し、選択部１０３によるノード１０の選択が終了するまで、選択部１０３により選択されたノード１０に対する同期信号の送信を繰り返す。
【００３２】
受信部１０２は、同期ポイントに到達すると受信準備を開始する。そして、受信準備が完了すると、受信準備完了の通知をノード１２へ送信する。その後、受信部１０２は、同期用の信号をノード１２から受信する。そして、受信部１０２は、受信した同期用の信号を判定部１０４へ出力する。
【００３３】
受信部１０２は、全てのノード１０が同期ポイントに到達するまで、同期信号の受信を繰り返す。
【００３４】
ここで、図４を参照して、同期用の信号の送信について詳細に説明する。図４は、同期用の信号の送信について説明するための図である。ここでは、ノード１０及び１１を例に説明する。受信準備が完了した旨の通知はハードウェアレベルで送信されるので、ここでは、送信部１０１及び受信部１０２の機能を実現するネットワークインタフェースカード１１１Ａ及び１１１Ｂなどのハードウェアを用いて動作を説明する。
【００３５】
ノード１０は、ネットワークインタフェースカード１１１Ａを有する。ノード１１のネットワークインタフェースカード１１１Ｂは受信バッファ１１６Ｂを有する。実際には、ネットワークインタフェースカード１１１Ａも受信バッファを有するが、ここでは説明の便宜上省略する。
【００３６】
ネットワークインタフェースカード１１１Ｂは、同期ポイントに到達すると、受信準備を開始する。そして、ネットワークインタフェースカード１１１Ｂは、受信準備が完了するまで、受信バッファ１１６Ｂを空きが無い状態にしておく。そして、受信準備が完了すると、ネットワークインタフェースカード１１１Ｂは、受信バッファ１１６Ｂを空にして、受信バッファ１１６Ｂの空情報を通知する信号３０１をネットワークインタフェースカード１１１Ａへ送信する。
【００３７】
ネットワークインタフェースカード１１１Ａは、信号３０１を受信すると、同期用の信号３０２をネットワークインタフェースカード１１１Ｂに送信する。
【００３８】
ネットワークインタフェースカード１１１Ｂは、既に受信準備が完了済みなことから、信号３０１を受信することができる。
【００３９】
このように、同期用の信号の送信側のノード１０のネットワークインタフェースカード１１１Ａは、送信先のノード１１の受信準備が完了したことを表す情報として受信バッファ１１６Ｂの空情報を通知する信号３０１を受け取る。これにより、ノード１０は、同期用の信号をノード１１に送ることで、ノード１１が同期ポイントに到達したとみなすことができる。
【００４０】
判定部１０４は、同期用の信号を送信した送信先のノード１１のＩＤを送信部１０１から取得する。さらに、判定部１０４は、同期ポイントに到達したことを送信元のノード１２が確認済みのノードのＩＤを取得する。ここで、例えば、予め決められたアルゴリズムに従って同期用の信号を送信することで、判定部１０４は、既に同期ポイントに到達したことを送信先のノード１２が確認済みのノードのＩＤを推定し取得することができる。
【００４１】
また、判定部１０４は、受信部１０２が受信した同期用の信号を受信部１０２から取得する。そして、判定部１０４は、受信部１０２から取得した同期用の信号から、その信号の送信元のノード１２のＩＤを取得する。また、判定部１０４は、取得した同期用の信号から、同期ポイントへの到達をその信号の送信元のノード１２が確認済みの他のノードのＩＤを取得する。そして、判定部１０４は、同期用の信号の送信先のノード１１及び、同期用の信号の送信元のノード１２及び同期ポイントへの到達をノード１２が確認済みのノードが同期ポイントに到達したと判定する。
【００４２】
その後、判定部１０４は、同期ポイントへの到達判定の処理の完了のステップを１ステップインクリメントし、完了したステップ数を選択部１０３へ通知する。
【００４３】
また、判定部１０４は、情報処理システム１に含まれるノード１０の全てについて同期ポイントへの到達が確認できた場合、バリア同期処理の終了を選択部１０３へ通知する。ここで、例えば、情報処理システム１に含まれるノード１０の総数を「Ｎ」とすると、判定が完了したステップ数がｌｏｇ３Ｎ以上になった場合に、判定部１０４は、全ノード１０が同期ポイントへ到達したと判定できる。
【００４４】
選択部１０３は、以下の条件を満たす送信先のノード１１を選択する。すなわち、選択部１０３は、同期ポイントへの到達を確認していないノードであり、且つ、同期ポイントへの到達をそのノードが確認済みのノードの中に、自ノード１０において同期ポイントへの到達が確認が完了していないノードをなるべく多く含むノードを選択する。
【００４５】
ここで、同期ポイントへの到達を送信先のノード１１が確認済みのノードの数が同じであれば、その中に、自ノード１０において同期ポイントへの到達を確認済みのノードがなるべく少ないほうが選択の効率がよいといえる。そこで、選択部１０３による送信先のノード１１の選択の高効率のアルゴリズムの一例について説明する。
【００４６】
ここでは、情報処理システム１に属するノード１０の総数を「Ｎ」とする。また、各ノード１０には、０から連番となるＩＤが振られている。また、実行する同期ポイントへの到達判定のステップのステップ数を「Ｓ：Ｓ＝１，２，３・・・」とする。また、自ノード１０のＩＤを「Ａ」とする。
【００４７】
選択部１０３は、判定部１０１から受信した同期ポイントへの到達判定が完了したステップ数に１を加算することでＳを求める。
【００４８】
そして、選択部１０３は、送信先のノード１１のＩＤを（Ａ＋３Ｓ−１）ｍｏｄＮとして求める。ここで、「ｍｏｄ」は剰余を表す計算符合である。ただし、剰余は正の整数とする。例えば、送信先のノード１１のＩＤが７ｍｏｄ５で求まる場合、選択部１０３は、７を５で割ると１余り２であるので、送信先のノード１１のＩＤとして「２」を選択する。
【００４９】
また、ＩＤの選択方法の他の例として、選択部１０３は、送信先のノード１１のＩＤを（Ａ−３Ｓ−１）ｍｏｄＮとして求めてもよい。この場合、例えば、送信先のノード１１のＩＤが−１ｍｏｄ５で求まる場合、選択部１０３は、−１を５で割ると−１余り４であるので、送信先のノード１１のＩＤとして「４」を選択する。
【００５０】
さらに、図５を参照して、具体的な、送信先のノードの選択について説明する。図５は、実施例１に係る情報処理システムによる送信先ノードの選択の一例を表す図である。図５では、ノード数Ｎが９の場合を表す。また、図５では、各ノード１０をノード＃０〜＃８として表しており、以下の説明でも、ノード＃０〜＃８を用いて説明する。ここで、＃以下の番号は各ノード１０のＩＤを表す。ここでは、選択部１０３は、送信先のノード１１のＩＤを（Ａ＋３Ｓ−１）ｍｏｄＮとして求める場合を例に説明する。
【００５１】
１ステップ目では、各ノード＃０〜＃８は、図５の同期用の信号３１１で表されるように同期用の信号を送信する。ノード＃０は、（０＋３０）ｍｏｄ９＝１をＩＤとするノードを送信先のノードとして選択する。すなわち、ノード＃０は、ノード＃１に同期用の信号を送信する。また、ノード＃１は、（１＋３０）ｍｏｄ９＝２をＩＤとするノードを送信先のノードとして選択する。すなわち、ノード＃１は、ノード＃２に同期用の信号を送信する。このようにして、同期用の信号３１１で表されるように、各ノード＃１〜＃７は自ノードのＩＤに１を加えたＩＤを有するノードを送信先のノードとし、ノード＃８はノード＃１を送信先のノードとする。
【００５２】
次に、２ステップ目では、各ノード＃０〜＃８は、同期用の信号３１２で表されるように同期用の信号を送信する。ノード＃０は、（０＋３１）ｍｏｄ９＝３をＩＤとするノードを送信先のノードとして選択する。すなわち、ノード＃０は、ノード＃３に同期用の信号を送信する。また、ノード＃１は、（１＋３１）ｍｏｄ９＝４をＩＤとするノードを送信先のノードとして選択する。すなわち、ノード＃１は、ノード＃４に同期用の信号を送信する。
【００５３】
このようにして、同期用の信号３１１で表されるように、各ノード＃１〜＃５は自ノードのＩＤに３を加えたＩＤを有するノードを送信先のノードとし、ノード＃６〜８は自ノードのＩＤに３を加えたＩＤから総ノード数を減算したＩＤを有するノードを送信先のノードとする。
【００５４】
ここで、同期ポイントに到達したノードの把握について、ノード＃５を例に説明する。１ステップ目で、ノード＃５は、ノード＃４及び＃６が同期ポイントに到達したことを把握する。
【００５５】
２ステップ目で、ノード＃５は、ノード＃２から送信された同期用の信号により、ノード＃１〜＃３が同期ポイントに到達したことを把握する。また、ノード＃５は、１ステップ目でノード＃７及び＃０が同期ポイントに到達したことを把握したノード＃８に同期用の信号が送信できたので、ノード＃０，＃７及び＃８が同期ポイントに到達したことを把握する。
【００５６】
この時点でノード＃５は、自分以外の全てのノードであるノード＃０〜＃４及び＃６〜＃８が同期ポイントに到達したことを把握する。このようにして、ノード＃０〜＃８の全てが、全ノードが同期ポイントに到達したことを把握する。
【００５７】
また、判定部１０４による終了判定について説明する。１ステップ目では、ステップ数である１はｌｏｇ３９より小さいので、判定部１０４は、各ノード＃０〜＃８が、他の全てのノードの同期ポイントへの到達の把握を完了していないと判定する。２ステップ目では、ステップ数である２はｌｏｇ３９と同じであるので、判定部１０４は、各ノード＃０〜＃８が、全ノードが同期ポイントに到達したことを把握したと判定し、バリア同期処理を終了する。
【００５８】
次に、図６を参照して、本実施例に係る情報処理システムによるバリア同期処理の流れについて説明する。図６は、実施例１に係る情報処理システムによるバリア同期処理のフローチャートである。
【００５９】
判定部１０４は、判定処理が完了したステップ数を０とする（ステップＳ１）。そして、判定部１０４は、判定処理が完了したステップ数を選択部１０３へ通知する。
【００６０】
次に、選択部１０３は、判定処理が完了したステップ数を判定部１０４から受ける。そして、選択部１０３は、ステップ数を１つインクリメントする（ステップＳ２）。
【００６１】
選択部１０３は、（Ａ＋３Ｓ−１）ｍｏｄＮ，（Ａ：自ノードのＩＤ、Ｓ：ステップ数、Ｎ：ノード総数）をＩＤとするノードを同期用の信号の送信先のノード１１として選択する（ステップＳ３）。
【００６２】
受信部１０２は、受信準備を行う（ステップＳ４）。受信部１０２は、受信準備を行っている間、受信バッファに空きが無い状態にしておく。そして、受信部１０２は、受信準備が完了したか否かを判定する（ステップＳ５）。受信準備が完了していない場合（ステップＳ５：否定）、受信部１０２は、ステップＳ４に戻る。
【００６３】
これに対して、受信準備が完了した場合（ステップＳ５：肯定）、受信部１０２は、受信バッファの空情報を同期用の信号の送信元のノード１２へ送り、受信準備完了を通知する（ステップＳ６）。このステップＳ６の処理は、具体的には、ネットワークインタフェースカード１１１によってハードウェアレベルで実行させる。
【００６４】
送信部１０１は、（Ａ＋３Ｓ−１）ｍｏｄＮをＩＤとする送信先のノードからの受信バッファの空情報の通知の有無により、送信先のノード１１の受信準備が完了したか否かを判定する（ステップＳ７）。送信先のノードの受信準備が完了していない場合（ステップＳ７：否定）、送信部１０１は、送信先のノード１１の受信準備が完了するまで待機する。
【００６５】
これに対して、送信先のノードの受信準備が完了した場合（ステップＳ７：肯定）、送信部１０１は、（Ａ＋３Ｓ−１）ｍｏｄＮをＩＤとする送信先のノードへ同期用の信号を送信する（ステップＳ８）。送信部１０１は、（Ａ＋３Ｓ−１）ｍｏｄＮをＩＤとする送信先のノード１０への同期用の信号の送信を判定部１０４へ通知する。
【００６６】
受信部１０２は、同期用の信号を送信元のノード１２から受信したか否かを判定する（ステップＳ９）。同期用の信号を受信していない場合（ステップＳ９：否定）、受信部１０２は、同期用の信号を受信するまで待機する。
【００６７】
これに対して、同期用の信号を受信した場合（ステップＳ９：肯定）、受信部１０２は、受信した同期用の信号を判定部１０４へ送信する。判定部１０４は、受信した同期用の信号及び送信部１０１が同期用の信号を送信した送信先のノード１１のＩＤから、同期ポイントに到達したノードのＩＤを取得する（ステップＳ１０）。
【００６８】
その後、判定部１０４は、実行する処理のステップ数がｌｏｇ３Ｎ以上か否かを判定する（ステップＳ１１）。ステップ数がｌｏｇ３Ｎより小さい場合（ステップＳ１１：否定）、判定部１０４は、ステップＳ２へ戻る。
【００６９】
これに対して、ステップ数がｌｏｇ３Ｎ以上の場合（ステップＳ１１：肯定）、判定部１０４は、バリア同期処理を終了する。
【００７０】
ここで、情報処理システム１においては、１つのノード内に含まれるＣＰＵ間でのノード内通信と、異なるノード間でのノード間通信とがある。そこで、これらの通信におけるバリア同期について説明する。
【００７１】
同じノード１０が有するＣＰＵ１１３とＣＰＵ１１４（図１参照）との間で行われるノード内通信について説明する。ノード内通信では、ＣＰＵ１１３及び１１４は、共有メモリにアクセスすることが可能である。そこで、ＣＰＵ１１３とＣＰＵ１１４との間のバリア同期は共有メモリを介して通信を行うことで実現できる。
【００７２】
例えば、メモリ１１２が共有メモリの場合、ＣＰＵ１１３がメモリ１１２にデータを書き込み、ＣＰＵ１１４が書き込まれたデータを読み出すことで、ＣＰＵ１１４はＣＰＵ１１３の同期ポイントへの到達を把握することができる。そのため、ノード内通信では、同期用の信号の送受信による同期ポイントへの到達の通知は行わなくてもよい。
【００７３】
これに対して、ノードが異なる場合、共有するメモリが存在しない。そのため、ノード間通信では、同期用の信号を送受信することで同期ポイントへの到達の通知が行われる。したがって、同期用の信号の送受信を用いた以上に説明したバリア同期の処理はノード間通信に対して用いることが好ましい。
【００７４】
以上に説明したように、本実施例に係る情報処理システムは、同期用の信号の送信により送信先のノード及びそのノードにより同期ポイントへ到達を確認済みのノードの同期ポイントへの到達を自ノードで把握する。また、本実施例に係る情報処理システムは、同期用の信号の受信により送信元のノード及びそのノードにより同期ポイントへ到達を確認済みのノードの同期ポイントへの到達を自ノードで把握する。これにより、ノード間でのデータの送受信を行わなくても相手ノードの同期ポイントへの到達を把握することができ、バリア同期処理の時間を短縮することができる。
【００７５】
さらに、本実施例に係る情報処理システムでは、ノードのＩＤを０からの連番として、（Ａ＋３Ｓ−１）ｍｏｄＮ，（Ａ：自ノードのＩＤ、Ｓ：ステップ数、Ｎ：ノード総数）をＩＤとするノードを同期用の信号の送信先のノードとする。これにより、より迅速に全ノードの同期ポイントへの到達を確認することができる。
【００７６】
例えば、（Ａ＋３Ｓ−１）ｍｏｄＮをＩＤとするノードを同期用の信号の送信先のノードとした場合、全てのノードの同期ポイントへの到達が把握できるまでのステップ数は、ｌｏｇ３Ｎである。これに対して、従来のように２つのノードの組におけるデータの送受信により同期ポイントへの到達を把握する場合、全てのノードの同期ポイントへの到達が把握できるまでのステップ数は、ｌｏｇ２Ｎである。つまり、本実施例に係る情報処理システムを用いることで、従来の方式に比べて、ステップ数を約２／３にすることができる。
【００７７】
例えば、ノード数Ｎが２０００の場合、従来手法であれば１５ステップであるが、本実施形態に係る情報処理システムでは１０ステップですむ。このように、本実施例に係る情報処理システムは、従来手法に比べてバリア同期の処理にかかる時間を短縮することができる。
【００７８】
さらに、本実施例に係る情報処理装置が従来技術に比べてバリア同期処理が早い理由を説明する。アプリケーションレベルでのデータの送受信は、ハードウェアレベルの通信より性能が悪いことが一般的である。本実施例では、各ノードは、受信準備が完了したことをハードウェアレベルの通信を用いて行い、それを受けて、アプリケーションレベルの通信により同期用の信号を送信する。これに対して、従来技術では、各ノードは、アプリケーションレベルの通信により同期用の信号を送信し、信号を受信するとアプリケーションレベルの通信を用いて受信したことを応答として返す。すなわち、本実施例に係る情報処理装置では、アプリケーションレベルの通信の回数を削減し、それに変えてハードウェアレベルでの通信を用いている。これにより、本実施例に係る情報処理装置は、従来技術に比べて高速なバリア同期を実現することができる。
【実施例２】
【００７９】
次に、実施例２について説明する。本実施例に係る情報処理システムは、送信先のノードの選択方法が実施例１と異なるものである。本実施例に係る情報処理システムに含まれるノードも図１で表される。以下の説明では、実施例１と同様の機能を有する各部については説明を省略する。
【００８０】
まず、選択部１０３は、自ノードであるノード１０及び他の２つのノード１０を含むグループを形成する。以下では自ノードが属するグループを「自グループ」という。そして、選択部１０３は、自グループに属する他の２つのノード１０のうち、一方を送信先のノード１１として選択する。ここで、選択部１０３は、グループ内のノード間で送信先が重複しないように選択する。例えば、選択部１０３は、予め決められたアルゴリズムにしたがって送信先のＩＤを選択することで、送信先の重複を避ける。
【００８１】
次に、選択部１０３は、同期ポイントへの到達の判定の１ステップ目の終了を判定部１０４から受信すると、自グループに属する他のノード１０の全てが同期ポイントに到達したことを把握する。そして、選択部１０３は、自グループ以外のグループを２つ選択して、自グループを含む３つのグループでグループ群を形成する。この時、選択部１０３は、自グループの他のノード１０の選択部１０３も同じグループでグループ群を形成するように選択を行う。例えば、選択部１０３は、予め決められたアルゴリズムにしたがってグループ群を形成することで、自グループの他のノード１０の選択部１０３も同じグループでグループ群を形成するようにできる。
【００８２】
そして、選択部１０３は、形成したグループ群のうち自グループ以外のグループの一方を送信先のグループとして選択する。ここで、選択部１０３は、同じグループ群に属するグループの間で送信先のグループが重複しないようにグループを選択する。また、同じグループに属するノード１０の選択部１０３は、同じグループを送信先のグループとして選択する。例えば、選択部１０３は、予め決められたアルゴリズムにしたがって送信先のグループを選択することで、グループ間での送信先の重複を避け、且つグループ内での同一のグループの選択が実現できる。
【００８３】
次に、選択部１０３は、送信先のグループから送信先のノード１０を選択する。ここで、同じグループに含まれるノード１０の選択部１０３は、それぞれの送信先のノード１０が重複しないように選択する。例えば、選択部１０３は、予め決められたアルゴリズムにしたがって送信先のＩＤを選択することで、送信先の重複を避ける。
【００８４】
そして、選択部１０３は、選択した送信先のノード１１のＩＤを送信部１０１へ通知する。
【００８５】
選択部１０３は、判定部１０４からバリア同期処理の終了の通知を受けるまで、送信先のノード１１の選択及び送信部１０１への通知を繰り返す。
【００８６】
例えば、情報処理システム１に属するノード１０の数が９の場合を例に、各ノード１０の同期用の信号の送信について、図７Ａ及び７Ｂを参照して説明する。図７Ａは、実施例２に係る情報処理システムにおけるＮ＝９の場合の１ステップ目の同期用の信号の送信状態を表す図である。また、図７Ｂは、実施例２に係る情報処理システムにおけるＮ＝９の場合の２ステップ目の同期用の信号の送信状態を表す図である。図７Ａ及び７Ｂでは、各ノードをノード＃０〜＃８として表しており、以下の説明でも、ノード＃０〜＃８を用いて説明する。ここで、＃以下の番号は各ノード１０のＩＤを表す。
【００８７】
ノード＃０〜＃８は、ノード＃０〜＃２が属するグループ、ノード＃３〜＃５が属するグループ及びノード＃６〜＃８が属するグループの３グループに分かれている。
【００８８】
１ステップ目では、図７Ａに示すように、グループ内で同期用の信号の送信先が重複しないように、各ノードが送信先を選択する。例えば、ノード＃０は、ノード＃１を送信先とし、ノード＃１は、ノード＃２を送信先とし、ノード＃２は、ノード＃０を送信先とする。
【００８９】
１ステップ目で、例えば、ノード＃５は、ノード＃３及び＃４が同期ポイントに到達したことを把握する。
【００９０】
次に、２ステップ目では、ノード＃０〜＃２が属するグループは、ノード＃３〜＃５が属するグループを送信先のグループとして選択する。ノード＃３〜＃５が属するグループは、ノード＃６〜＃８が属するグループを送信先のグループとして選択する。ノード＃６〜＃８が属するグループは、ノード＃０〜＃２が属するグループを送信先のグループとして選択する。
【００９１】
さらに、各グループに属するノードは、送信先のグループから重複しないように送信先のノードを選択する。例えば、ノード＃０は、ノード＃３を送信先とし、ノード＃１は、ノード＃４を送信先とし、ノード＃２は、ノード＃５を送信先とする。ここで、送信先のグループのいずれのノードも、そのグループ内の全てのノードの同期ポイントへの到達を確認済みなことから、どのノードを選択しても差は無い。
【００９２】
２ステップ目で、例えば、ノード＃５は、ノード＃２から送信された同期用の信号により、ノード＃０〜＃２が同期ポイントに到達したことを把握する。また、ノード＃５は、１ステップ目でノード＃６及び＃７が同期ポイントに到達したことを把握したノード＃８に同期用の信号が送信できたので、ノード＃６〜＃８が同期ポイントに到達したことを把握する。すなわち、この時点でノード＃５は、自分以外の全てのノードであるノード＃０〜＃４及び＃６〜＃８が同期ポイントに到達したことを把握する。このようにして、ノード＃０〜＃８の全てが、全ノードが同期ポイントに到達したことを把握する。
【００９３】
ここで、ノード数がさらに多い場合、次のステップで同期ポイントに到達したことを把握したノードが属するグループをまとめてグループ群として、各グループに属するノードは、同期ポイントに到達していないノードを含むグループ群を選択し、その中から重複しないように送信先のノードを選択する。
【００９４】
ここで、以上では、説明の便宜上、３つのノードが属するグループに分け、その後、同期ポイントへの到達が確認できたノードが属するグループをグループ群として扱ったが。しかし、実際には、予め決められたアルゴリズムに従い送信先のノードを選択することで、上記の送信先の選択処理が実現できる。
【００９５】
例えば、ノードの総数が３のべき乗であり、ノードのＩＤを０から連番で振り、自ノードのＩＤを「Ａ」とし、ステップ数を「Ｓ」とする場合を考える。この場合、各ノードは、各ステップにおいて「（Ａ＋３ｓ−１）ｍｏｄ（３Ｓ）＋Ａ」をＩＤとするノードを送信先のノードとして選択していくことで、上述の送信先のノード１１の選択処理が実現できる。
【００９６】
すなわち、選択部１０３は、ステップ毎に、例えば、（Ａ＋３ｓ−１）ｍｏｄ（３Ｓ）＋Ａのような予め決められたアルゴリズムに従い送信先のノード１１を選択し、選択したノード１１のＩＤを送信部１０１へ通知するという処理を行っているともいえる。
【００９７】
以上に説明したように、本実施例に係る情報処理システムでは、３つのノードを含むグループ毎に分けて、そのグループを用いて同期用の信号の送信先のノードを決定する。このように、実施例１で説明した方法以外にも、同期用の信号の送信先のノードの選択方法は様々な方法が考えられ、それらの方法を用いても、バリア同期処理に係る時間を軽減することができる。
【００９８】
ここで、以上の実施例では、ＣＰＵを２つ有し、メモリを２つ有するノードを例に説明したが、ノードのハードウェア構成はこれに限らない。例えば、図８は、ノードの構成の他の例を示す図である。図８で示すように、ネットワークインタフェースカード１２１、メモリ１２２及びＣＰＵ１２３を有するノード１０を用いても同様の効果を得ることができる。
【符号の説明】
【００９９】
１  情報処理システム
２  ネットワーク
１０，１１，１２  ノード
１０１  送信部
１０２  受信部
１０３  選択部
１０４  判定部
１１１，１１１Ａ，１１１Ｂ  ネットワークインタフェースカード
１１２，１１５  メモリ
１１３，１１４  ＣＰＵ
１１６Ｂ  受信バッファ
【図１】
2015036943.tif 000003
【図２】
2015036943.tif 000004
【図３】
2015036943.tif 000005
【図４】
2015036943.tif 000006
【図５】
2015036943.tif 000007
【図６】
2015036943.tif 000008
【図７Ａ】
2015036943.tif 000009
【図７Ｂ】
2015036943.tif 000010
【図８】
2015036943.tif 000011