(57)【要約】【課題】ノード間通信経路を決定する中継ノードを、通過コストを考慮しつつ、時間をかけずに決定すること。【解決手段】中継制御ノード１００は、第１ノードから、第２ノードとのノード間通信を行うリクエストを受信する。中継制御ノード１００は、ジョブ管理部から現在のジョブ実行情報を受信する。中継制御ノード１００は、第１ノードの情報、第２ノードの情報、ジョブ実行情報および予め記憶したノード構造のトポロジー情報を基にして、連結成分グラフ情報を生成する。中継制御ノード１００は、連結成分グラフ情報を基にして、第１ノードおよび第２ノード間のノード間通信時に経由するノード群経由情報を複数生成する。中継制御ノード１００は、最も通過コストが低いノード群経由情報を選択する。中継制御ノード１００は、選択したノード群経由情報のノード群間の位置情報を基にして、各ノード群から中継ノードを抽出する。【選択図】図３
2019021127.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータに、
第１ノードから、第２ノードとのノード間通信を行うリクエストを受信し、
ジョブ管理部から現在のジョブ実行情報を受信し、
前記第１ノードの情報、前記第２ノードの情報、前記ジョブ実行情報および予め記憶したノード構造のトポロジー情報を基にして、連結成分グラフ情報を生成し、
前記連結成分グラフ情報を基にして、前記第１ノードおよび前記第２ノード間のノード間通信時に経由するノード群経由情報を複数生成し、
最も通過コストが低いノード群経由情報を選択し、
選択したノード群経由情報のノード群間の位置情報を基にして、各ノード群から中継ノードを抽出する
処理を実行させることを特徴とする中継ノード決定プログラム。
【請求項２】
前記連結成分グラフ情報を生成する処理は、前記第１ノード、前記第２ノード、複数の第３ノードのうち、アクティブノードを頂点とし、かつ、各頂点が連結する部分グラフと、アクティブノード以外の他のノードを頂点とし、かつ、各頂点が連結する部分グラフとを生成し、複数の部分グラフを、前記トポロジー情報を基にして接続することで、前記連結成分グラフを生成することを特徴とする請求項１に記載の中継ノード決定プログラム。
【請求項３】
前記ノード群経由情報を生成する処理は、前記連結成分グラフ情報を基にして、前記第１ノードを含む部分グラフから、他の部分グラフを経由して、前記第２ノードを含む部分ブラフに至る経路を、前記ノード群経由情報として複数生成することを特徴とする請求項２に記載の中継ノード決定プログラム。
【請求項４】
コンピュータが実行する中継ノード決定方法であって、
第１ノードから、第２ノードとのノード間通信を行うリクエストを受信し、
ジョブ管理部から現在のジョブ実行情報を受信し、
前記第１ノードの情報、前記第２ノードの情報、前記ジョブ実行情報および予め記憶したノード構造のトポロジー情報を基にして、連結成分グラフ情報を生成し、
前記連結成分グラフ情報を基にして、前記第１ノードおよび前記第２ノード間のノード間通信時に経由するノード群経由情報を複数生成し、
最も通過コストが低いノード群経由情報を選択し、
選択したノード群経由情報のノード群間の位置情報を基にして、各ノード群から中継ノードを抽出する
処理を実行することを特徴とする中継ノード決定方法。
【請求項５】
第１ノードから、第２ノードとのノード間通信を行うリクエストを受信し、ジョブ管理部から現在のジョブ実行情報を受信する受信部と、
前記第１ノードの情報、前記第２ノードの情報、前記ジョブ実行情報および予め記憶したノード構造のトポロジー情報を基にして、連結成分グラフ情報を生成し、前記連結成分グラフ情報を基にして、前記第１ノードおよび前記第２ノード間のノード間通信時に経由するノード群経由情報を複数生成し、最も通過コストが低いノード群経由情報を選択し、選択したノード群経由情報のノード群間の位置情報を基にして、各ノード群から中継ノードを抽出する中継制御部と
を有することを特徴とする並列処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、中継ノード決定プログラム等に関する。
【背景技術】
【０００２】
ひとつの並列ジョブが行うノード間通信は、他の並列ジョブが行うノード間通信との間の重複をできるだけ小さくすることが、性能の観点から望ましい。
【０００３】
たとえば、大規模並列計算システムのネットワークトポロジーには、メッシュあるいはトーラスと呼ばれるネットワークトポロジーがある。このシステムでは、各ジョブに割り当てたノード間通信の通信経路が単一のサブメッシュないしサブトーラスに閉じるようにして、ジョブ間の通信の干渉を回避する場合がある。しかし、１つのジョブに割り当てるノードを単一のサブメッシュやサブトーラス内に限定することは、ノードの割り当て効率に関しては不利となる。
【０００４】
ノードの稼働率を上げるため、１つのジョブが使用するノードを複数のサブメッシュないしサブトーラスにする場合も有る。この場合は、ジョブ間通信の干渉が発生する。
【０００５】
ネットワークトポロジーがメッシュあるいはトーラスであるネットワークにおいて、ハードウェア自体が通信の始点と終点とを指定されて行う転送での通信経路は、次元順ルーティングと呼ばれる方式で決定される場合が多い。次元順ルーティングは、静的ルーティングの一種であり、使用される経路は、通信の始点と終点とを指定した時点で固定される。
【０００６】
図２３は、２次元での次元順ルーティングの一例を示す図である。図２３において、横方向をＸ軸方向、縦方向をＹ軸方向とする。ノード（Ａ）からノード（Ｂ）への通信パケットは、まず、ノード（Ａ）の座標からＸ軸方向に進み、Ｘ座標がノード（Ｂ）の座標と等しくなった時に、Ｙ軸方向に進む。
【０００７】
ハードウェアによる自動経路選択では、図２３で説明した経路以外の経路は使用されない。このため、次元順ルーティングが使われるシステムでは、ハードウェアが自動選択する経路と異なる経路を使用して、通信の干渉を減らす場合には、次のような処理をソフトウェアが行う。すなわち、ソフトウェアが通信の始点と終点以外のノードに、中継点となるノードを設定し、かつ、明示的に、中継点のノードを経由する通信を行う。以下の説明では、中継点のノードを、中継ノードと表記する。
【０００８】
図２４は、中継ノード設定による迂回経路の一例を示す図である。経路決定を行うソフトウェアは、中継ノード（Ｃ）を設定する。また、ソフトウェアは、中継ノード（Ｃ）上で中継処理機能を起動するか、中継ノード（Ｃ）上でハードウェアによる自動転送機能用のコマンド列をセットアップしておく。たとえば、自動転送機能は、InfiniBandのCORE-Directや、Tofuのsession-modeの機能に対応する。
【０００９】
ノード（Ａ）からノード（Ｂ）への通信を行う際には、ノード（Ａ）は、通信パケットのヘッダに「ノード（Ｂ）への転送指示情報」を加えて、ノード（Ｃ）に向けて通信パケットを送信する。これにより、通信パケットは、迂回経路（Ａ）、（Ｃ）、（Ｂ）により、ノード（Ｂ）に到達する。
【００１０】
一般に、ｍ次元のメッシュないしトーラスのネットワークでは、各ノードのネットワークアドレスは、ｍ個の整数の組で（ｘ１，...，ｘｍ）のように表され、各次元の上限、下限の整数が、ａ１≦ｘ１≦ｂ１，ａ２≦ｘ２≦ｂ１，...，ａｍ≦ｘｍ≦ｂｍのように定まる。
【００１１】
ここで、ネットワークの各次元の大きさ(ホップ数)は（ｂｉ−ａｉ＋１）＝Ｌｉ（ｉ＝１，２，...，ｍ）である。各次元の座標が１だけ違う２つのノードの間には物理的なネットワークリンク（以下、単にリンク）が存在する。ただし、トーラスの場合は、第ｉ次元の座標がａ１とｂ１のノード間にもリンクが存在するが、トーラスでは第ｉ次元の座標の差をｍｏｄ（ｂｉ×ａｉ＋１）で計算すれば、メッシュとトーラスの座標の取扱いは、ほぼ同じになる。
【先行技術文献】
【特許文献】
【００１２】
【特許文献１】特表２０１１−５１６９４５号公報
【発明の概要】
【発明が解決しようとする課題】
【００１３】
しかしながら、上述した従来技術では、ノード間通信経路を決定する中継ノードを、通過コストを考慮しつつ、時間をかけずに決定することができないという問題がある。
【００１４】
たとえば、下記の前提１，２で通信経路を判定すると、経路の数は、中継ノードの位置に関する組み合わせに依存する。
前提１：ハードウェアの機能として次元順ルーティングが使用されるネットワークである。
前提２：ソフトウェアで明示的に中継ノードを定めて通信する。
【００１５】
以下の説明では、あるジョブが使用しているノードからファイルサーバノードへの通信、あるいは、同じジョブが使用しているノード間の通信を「自ジョブの通信」と表記する。
【００１６】
自ジョブの通信が、できるだけ他のジョブ通信と干渉しないように、中継ノードの組み合わせを選択することが好ましい。
【００１７】
原理的には、中継ノードの候補となる空きノードの組み合わせ全てについて、各組み合わせでの通信の干渉コストを何らかの基準で比較して、干渉コストが最小となる組み合わせを選択することが考えられる。たとえば、「他ジョブが使用している経路と重複するリンクの数」を基準とする。
【００１８】
干渉コストが最小となる組み合わせを選択する場合には、次のように「グラフ理論」での「最小費用流用問題」の用語を使用することで、干渉コストが最小となる組み合わせを選択する処理を、簡素に表現することができる。
【００１９】
物理ネットワークのノードを「頂点」、リンクを「辺」とする「グラフ」を以下では「物理ネットワークブラフ」と呼ぶ。また、「物理ネットワークグラフ」をΓｐ（Ｖ，Ｅ）と表記する。Ｖは、システム内の全ノードに対応する管理構造体であり、リストで扱う。Ｅは、システムのネットワークの中の全ての物理的なリンクに対応する構造体であり、各頂点の隣接リストを全て合わせたものとして取り扱う。
【００２０】
たとえば、ソフトウェアは、次の条件１、２によるΓｐ（Ｖ，Ｅ）を用いて、他のジョブの通信と干渉するコストを算出する。
【００２１】
条件１：通信経路の一方の端点が自ジョブのノードかつ他方の端点がファイルサーバノードであるか、通信経路の両端が自ジョブのノード。
条件２：グラフΓｐ（Ｖ，Ｅ）の「辺（Ｅの要素）」通過コストは、少なくとも一方の他のジョブが使用中のノードである場合、全て「１」とする。リンクの両端が、下記のいずれか（ａ）、（ｂ）、（ｃ）のノードである場合、「辺（Ｅの要素）」通過コストを「０」とする。
（ａ）：どのジョブも使用していないノード。
（ｂ）：自ジョブのサブメッシュを構成するノード。
（ｃ）：自ジョブがサービスを要求するサーバノード（たとえば、あるファイルサーバへのＩＯでの通信の場合、そのファイルサーバ）。
【００２２】
ここで、上記条件１、２によるΓｐ（Ｖ，Ｅ）を用いて、他のジョブの通信と干渉するコストを算出する場合、大規模やシステムにおいては、ノードやリンクの数が増加する。これにより、ノードやリンクの組み合わせの数は急激に増大し、単純に組み合わせを調べることは、計算量の観点から困難である。
【００２３】
たとえば、２次元のｎ×ｎメッシュネットワーク（ノードの数がｎ２）の場合、このメッシュネットワークのグラフを表す隣接行列はｎ２×ｎ２成分、隣接リストは、ｎ２×４要素、接続行列はｎ２×（（ｎ＋２）（ｎ−１））成分である。
【００２４】
図２５は、メッシュネットワークの一例を示す図である。図２５に示すように、１６ノードである場合には、隣接行列は、１６×１６＝２５６成分、接続行列は、１６×１８＝２８８成分である。しかし、１０００ノードである場合には、隣接行列は１０８成分、隣接行列は、更に多くの成分を持つことになる。
【００２５】
すなわち、大規模システムでは、上記のΓｐ（Ｖ，Ｅ）を用いて、他のジョブの通信と干渉するコストを算出する場合、計算時間が増加するため、現実的な時間内で、ジョブ間の干渉を抑えた中継ノードを選択することが困難である。
【００２６】
１つの側面では、本発明は、ノード間通信経路を決定する中継ノードを、通過コストを考慮しつつ、時間をかけずに決定することができる中継ノード決定プログラム、中継ノード決定方法および並列処理装置を提供することを目的とする。
【課題を解決するための手段】
【００２７】
第１の案では、コンピュータに次の処理を実行させる。コンピュータは、第１ノードから、第２ノードとのノード間通信を行うリクエストを受信する。コンピュータは、ジョブ管理部から現在のジョブ実行情報を受信する。コンピュータは、第１ノードの情報、第２ノードの情報、ジョブ実行情報および予め記憶したノード構造のトポロジー情報を基にして、連結成分グラフ情報を生成する。コンピュータは、連結成分グラフ情報を基にして、第１ノードおよび第２ノード間のノード間通信時に経由するノード群経由情報を複数生成する。コンピュータは、最も通過コストが低いノード群経由情報を選択する。コンピュータは、選択したノード群経由データのノード群間の位置情報を基にして、各ノード群から中継ノードを抽出する。
【発明の効果】
【００２８】
ノード間通信経路を決定する中継ノードを、通過コストを考慮しつつ、時間をかけずに決定することができる。
【図面の簡単な説明】
【００２９】
【図１】図１は、本実施例に係る中継制御ノードの処理の一例を説明する図である。
【図２】図２は、連結成分グラフの一例を示す図である。
【図３】図３は、本実施例に係るシステムの構成を示す機能ブロック図である。
【図４】図４は、本発明が前提とする通信の中継を説明するための図である。
【図５】図５は、中継ノードを複数設定した場合の通信の中継を説明するための図である。
【図６】図６は、ノードの中継制御エージェントが設定、参照するメッセージのデータ構造の一例を示す図である。
【図７】図７は、ノードの通信ハードウェアにとってのメッセージのデータ構造の一例を示す図である。
【図８】図８は、始点ノードの中継制御エージェントとアプリケーションとの通信で用いられるメッセージのデータ構造の一例を示す図である。
【図９】図９は、本実施例に係るノードの構成を示す機能ブロック図である。
【図１０】図１０は、経路表情報のデータ構造の一例を示す図である。
【図１１】図１１は、経路割り当て情報のデータ構造の一例を示す図である。
【図１２】図１２は、中継制御エージェントが実行する中継処理を示すフローチャートである。
【図１３】図１３は、中継終了処理を示すフローチャートである。
【図１４】図１４は、物理的なネットワークのトポロジーがメッシュである場合の隣接リストを説明する図である。
【図１５】図１５は、物理的なネットワークのトポロジーがトーラスである場合の隣接リストを説明する図である。
【図１６】図１６は、本実施例に係る中継制御ノードの構成を示す機能ブロック図である。
【図１７】図１７は、中継制御マネージャが中継ノードを特定する処理手順を示すフローチャートである。
【図１８】図１８は、連結成分グラフの辺と、通過コストを算出する処理手順を示すフローチャートである。
【図１９】図１９は、物理ネットワークへの引き戻しを説明するための図である。
【図２０】図２０は、本実施例に係る中継制御ノードの処理手順を示すフローチャートである。
【図２１】図２１は、バウンディングボックスによる連結成分グラフの辺の数の削減を説明するための図である。
【図２２】図２２は、中継制御ノードと同様の機能を実現するコンピュータのハードウェア構成の一例を示す図である。
【図２３】図２３は、２次元での次元順ルーティングの一例を示す図である。
【図２４】図２４は、中継ノード設定による迂回経路の一例を示す図である。
【図２５】図２５は、メッシュネットワークの一例を示す図である。
【発明を実施するための形態】
【００３０】
以下に、本願の開示する中継ノード決定プログラム、中継ノード決定方法および並列処理装置の実施例を図面に基づいて詳細に説明する。なお、この実施例によりこの発明が限定されるものではない。
【実施例】
【００３１】
本実施例では、通信端末のノードと、「中継点として使用可能な全てのノード」とを合わせて、「アクティブノード」という同じ種類のノードであると定義する。通信端点のノードは、通信の始点のノードと、終点のノードとを示す。通信端点ノードを占有するジョブを「自ジョブ」と表記する。
【００３２】
たとえば、以下の１ａ〜３ａを「アクティブノード」とする。アクティブノードで閉じた通信は、他ジョブとの干渉をなしとする。
１ａ：どのジョブも使用していないノード。
２ａ：自ジョブのサブメッシュを構成するノード。
３ａ：自ジョブがサービスを要求するサーバノード。
【００３３】
また、以下の１ｂ〜３ｂを「アクティブノード」としてもよい。
１ｂ：どのジョブも使用していないノード。
２ｂ：自ジョブと利用者が共通のジョブのサブメッシュを構成するノード。
３ｂ：自ジョブがサービスを要求するサーバノード。
【００３４】
アクティブノードの定め方は１ａ〜３ａ、１ｂ〜３ｂに限定されるものではない。たとえば、通信の干渉を許容可能なジョブが使用中のノードをアクティブノードとしてもよい。以下の説明では、単に、通信端末のノードを含む、所定の複数のノード（群）として説明を行うものとする。
【００３５】
続いて、本実施例に係る中継制御ノードの処理の一例について説明する。中継制御ノードは、並列処理装置の一例である。中継制御ノードは、次元順ルーティングおよび中継ノードを設定よることによる迂回経路の使用を前提として、ジョブ間の干渉をできるだけ抑えた通信経路（ジョブ間の干渉をできるだけ抑えた通信経路に含まれる各中継ノード）を求める。
【００３６】
中継制御ノードは、ジョブ間の干渉をできるだけ抑えた通信経路を求めるにあたり、物理ネットワークに対応した物理ネットワークグラフを生成し、物理ネットワークグラフに対する最小費用流問題を階層化し、準最小費用流を求める。たとえば、中継制御ノードは、次の処理１ｃ、２ｃを実行することで、「アクティブノードの頂点だけを含む部分グラフの連結成分」を頂点とする「連結成分グラフ」を生成する。
【００３７】
１ｃ：中継制御ノードは、物理ネットワークグラフにおいて、頂点として「アクティブノード」の頂点だけを含む部分グラフΓ０（Ｖ０，Ｅ０）を生成する。
２ｃ：中継制御ノードは、部分グラフΓ０（Ｖ０，Ｅ０）の「連結成分」を求める。連結成分の集合をＶＣ＝Ｃ１，Ｃ２，...，Ｃｎとする。中継制御ノードは、連結成分の集合全てから要素の組「Ｓ＝（Ｃｉ，Ｃｊ）｜Ｃｉ，Ｃｊ∈ＶＣ，ｉ≠ｋ」を生成する。中継制御ノードは、要素の組Ｓの一部なし全部をＴ⊂Ｓとして、ＥＣ＝Ｔとおき、「ｅｉｊ＝（Ｃｉ，Ｃｊ）が、頂点Ｃｉと頂点Ｃｉとの間の辺であるグラフ」ΓＣ（ＶＣ，ＥＣ）を生成する。以下、ΓＣ（ＶＣ，ＥＣ）を「連結成分グラフ」と表記する。
【００３８】
以下の説明では、Ｃ１が自ジョブの通信の始点ノードｇ０を含み、Ｃｔが自ジョブの通信の終点ノードｆｔを含むものとする。
【００３９】
大規模ネットワークに対して、単純に最小費用流問題を使用すると、計算量が大きくなる。このため、中継制御ノードは、比較的計算量の小さい次の処理１ｄ、２ｄを実行することで、中継ノードを特定するまでの時間を短縮するものである。
１ｄ：中継制御ノードは、連結成分の間の最短距離を与えるノードの対を求める。
２ｄ：中継制御ノードは、連結成分の間の最短距離での通過コストを、連結成分間の通過コストに置き換えた連結成分グラフに基づいて、通過コストの低い通信経路を特定する。
【００４０】
上記の処理１ｄ、２ｄの解の合成手順をグラフ理論の用語を使用して述べると、次の１ｅ〜３ｅに示すものとなる。
１ｅ：中継制御ノードは、辺ｅｉｊ＝（Ｃｉ，Ｃｊ）の通過コストを、ＣｉとＣｊとの間の最小費用の経路とする。中継制御ノードは、最小費用の経路を与えるＣｉのノードとＣｊのノードとの対を（ｆｉｊ，ｇｉｊ）として記憶する。
２ｅ：中継制御ノードは、ΓＣ（ＶＣ，ＥＣ）について、最小費用流問題の解を算出することで、通過コストが最小となる経路（Ｅ１，...，Ｅｋ）を求める。連結成分に符号を振り直して、Ｅ１＝（Ｃ１，Ｃ２）、Ｅ１＝（Ｃ２，Ｃ３），...，Ｋｋ＝（Ｃｋ，Ｃｔ）とする。
３ｅ：中継ノードは、連結成分グラフでの最小費用流を与える経路の各辺Ｅ１，...，Ｅｐ，...，Ｅｋ、各辺の通過コストを定めたノードの対を、１≦ｐ≦ｋに対し、Ｅｐ＝（ｆｐ，ｇｐ）とするとき、（ｆ０，ｇ１，ｆ１，ｇ２，...，ｆｋ，ｇｋ，ｆｔ）とする。
【００４１】
図１は、本実施例に係る中継制御ノードの処理の一例を説明する図である。図１では、４×４メッシュネットワークを示す。図１のメッシュネットワークにおいて、ノード（ｅ）は空きノードである。ノード（ｉ）は、ＩＯノードである。ノード（ｊ）は、ＩＯノードと通信しようとするジョブのノードである。ノード（ｌ）およびノード（ｋ）は、ノード（ｊ）とは異なるジョブのノードである。ノード（ｅ）、ノード（ｉ）、ノード（ｊ）がアクティブノードである。
【００４２】
図１に示す例では、４つの連結成分（Ｊ＋Ｅ）、（Ｉ＋Ｊ）、（Ｋ）、（Ｌ）がある。中継制御ノードは、ノード（ｊ）のジョブの通信経路を選択する場合には、まず、ノード（ｊ）の連結成分だけを頂点とする「連結成分グラフ」を生成する。
【００４３】
図２は、連結成分グラフの一例を示す図である。図１に示す連結成分グラフは、頂点（Ｊ＋Ｅ）と、頂点（Ｉ＋Ｊ）とを有する。頂点（Ｊ＋Ｅ）は、図１の連結成分（Ｊ＋Ｅ）に対応する。頂点（Ｉ＋Ｊ）は、図１の連結成分（Ｉ＋Ｊ）に対応する。頂点（Ｊ＋Ｅ）は、経路１０（Ｋ）および経路１０（Ｌ）を介して、頂点（Ｉ＋Ｊ）に接続される。経路１０（Ｋ）は、図１の連結成分（Ｋ）を通過する経路である。経路１０（Ｌ）は、図１の連結成分（Ｌ）を通過する経路である。
【００４４】
中継制御ノードは、図２に示す連結成分グラフについて、通過コストが最小となる経路を判定する。たとえば、始点ノードを含む頂点を頂点（Ｊ＋Ｅ）とし、始点ノードを含む頂点を頂点（Ｊ＋Ｉ）とする場合、通過コストが最小となる経路は、経路１０（Ｋ）と経路１０（Ｌ）のうち、いずれか一方の経路となる。すなわち、通過コストの比較対象が削減されるので、計算量を抑止することが可能となる。
【００４５】
たとえば、経路１０（Ｌ）の通過コストが、経路１０（Ｋ）のの通過コストよりも少ないとすれば、中継制御ノードは、通信経路を、経路１０（Ｌ）を経由する通信経路として特定する。たとえば、中継装置は、通信経路の各連結成分に含まれる端のノードを、中継ノードとして特定する。連結成分に含まれる端のノードが複数存在する場合には、中継ノードとして選択するノードを予め設定しておいても良い。
【００４６】
一般に、大規模な並列システムでは、大規模システムでした実行できない「多数のノードを動じ使用するジョブ」が実行されるので、「連結成分グラフ」は、元の物理ネットワークに対応するグラフと比べて頂点数が少ない。たとえば、平均的なジョブが１００ノードを同時に使用するシステムの場合、頂点数が１／１００のグラフで、通過コストが少ない経路を計算すればよい。
【００４７】
なお、連結成分グラフを用いて、通過コストの少ない通信経路を特定する処理は、連結成分を求める処理や、引き戻しの処理（後述する）を伴うが、元のグラフで通信コストの通信経路を求める処理の計算量よりオーダーが少ない。
【００４８】
これにより、本実施例の中継制御ノードによれば、大規模システムでも現実的な計算時間で、他ジョブとの干渉が小さい通信経路を使用した迂回通信を効率的に実行することができる。
【００４９】
続いて、上記の中継制御ノードを有するシステムの構成について説明する。図３は、本実施例に係るシステムの構成を示す機能ブロック図である。図３に示すように、このシステムは、複数のノード２０と、複数のＩＯノード２５と、中継制御ノード１００と、ファイルサーバ２００とを有する。図示を省略するが、このシステムは、他のノード、ＩＯノードを有していても良い。
【００５０】
大規模な並列計算機においては、計算を行うノード２０に直接大容量の２次元記憶装置を接続するのではなく、分散ファイルシステムをサポートするファイルサーバ２００を設置する。ノード２０は、ＩＯノード２５を介して、ファイルサーバ２００との間でｉＯ処理を行う。
【００５１】
図３に示すシステムでは、多数のノード２０から通信が一時にファイルサーバ２００に集中して、ＣＰＵ負荷やメモリ使用量、あるいは通信バンド幅のボルトネックになることを避けるために、ノード２０全体の集合をいくつかの部分集合に分割する。各部分集合内のノードに対して「ステージング」と呼ばれる処理を担当する「ネットワーク上で近い」小規模なファイルサーバに相当するＩＯノード２５を設置する。
【００５２】
ここで、「ネットワーク上で近い」とは、たとえば、ノード２０間の通信に使用される、通信バンド幅が大きく通信レイテンシも小さい「インタコネクト」と呼ばれるネットワークに接続されているという構成を示す。
【００５３】
以下の説明において、通信の始点となるノード２０またはＩＯノード２５を、始点ノードと表記する。通信の終点となるノード２０またはＩＯノード２５を、終点ノードと表記する。通信の中継点となるノード２０またはＩＯノード２５を、中継ノードと表記する。
【００５４】
続いて、図３に示したシステムで動作するソフトウェアの構成について説明する。たとえば、本発明は、並列システムにおける通信ライブラリ関数および、通信ライブラリ関数の実行管理部を合わせたものとして実現される。「通信ライブラリ関数」は、他ノード上のプロセスと通信するアプリケーションにリンクされ、アプリケーションのメモリ空間内の実行コンテキストで動作する。
【００５５】
通信ライブラリ関数の実行管理部は、通信ライブラリがリンクするアプリケーションとは独立のメモリ空間で動作する場合もある。また、通信ライブラリ関数の実行管理部は、アプリケーションが動作するノードとは別のノードで動作する部分を含む。
【００５６】
たとえば、「通信ライブラリ関数の実行管理部」は、「メッセージ送信経路の管理を行う部分」と、「各メッセージの中継制御を行う部分」を含む。「メッセージ送信経路の管理を行う部分」と、「各メッセージの中継制御を行う部分」とが動作するメモリ空間、動作するノードは、一般的には異なる。
【００５７】
続いて、本発明が前提とする通信の中継について説明する。図４は、本発明が前提とする通信の中継を説明するための図である。図４に示すように、始点ノードは、メッセージを中継ノードに送信する（ステップＳ１０）。中継ノードは、始点ノードからメッセージを受信する（ステップＳ１１）。中継ノードは、メッセージを終点ノードに送信する（ステップＳ１２）。終点ノードは、中継ノードからメッセージを受信する（ステップＳ１３）。
【００５８】
ここで、ノードの通信ハードウェアによるメッセージ受信とは、ネットワーク経由で他ノードから転送されてくるデータを所定のメモリアドレスに格納することである。ノードの通信ハードウェアによるメッセージ送信とは、所定のメモリアドレスに格納されているデータをネットワーク経由で他のノードに転送することである。中継ノードにおける中継処理は、メッセージ受信により所定のアドレスに格納されたデータへのメッセージ送信で実現される。
【００５９】
なお、中継ノードを複数設定することも可能であり、中継ノードを複数設定した場合の、処理手順は図５に示すものとなる。図５は、中継ノードを複数設定した場合の通信の中継を説明するための図である。
【００６０】
図５に示すように、始点ノードは、メッセージを中継ノードに送信する（ステップＳ２０）。中継ノードａは、始点ノードからメッセージを受信する（ステップＳ２１）。中継ノードａは、メッセージを中継ノードｂに送信する（ステップＳ２２）。中継ノードｂは、中継ノードａからメッセージを受信する（ステップＳ２３）。
【００６１】
中継ノードｂは、メッセージを中継ノードｃに送信する（ステップＳ２４）。中継ノードｃは、中継ノードｂからメッセージを受信する（ステップＳ２５）。中継ノードｃは、メッセージを終点ノードに送信する（ステップＳ２６）。終点ノードは、中継ノードｃからメッセージを受信する（ステップＳ２７）。
【００６２】
一般に、中継ノード上での中継制御方法には、大別して方法１ｆ、方法２ｆがある。
方法１ｆ：ノード間通信の主体となるジョブのノードが、転送経路の指示全てをメッセージヘッダに格納する。転送経路の指示には、メッセージが経由する中継ノードのアドレスが含まれる。方法１ｆは、ソースルーティングと呼ばれる。方法１ｆでは、送信元で中継ノードを選択するか、使用すべき中継ノードを送信前に通知されている必要がある。
方法２ｆ：各中継ノードに「経路表（ルーティングテーブル）」を設定しておく。経路表とは、受信したメッセージの次の転送先を定めた表である。
【００６３】
本実施例では一例として、中継制御ノード１００が、方法２ｆに従い、通信の開始に先立って、経路表の情報を中継ノードに通知しておくものとするが、本発明では、方法１ｆによって、中継制御を行う場合にも適用可能である。
【００６４】
続いて、中継ノードが、各メッセージを中継する処理について説明する。中継ノードがメッセージを中継する処理は、大別して下記の方法１ｇ、２ｇがある。
方法１ｇ：中継ノードの中継ソフトウェアが、メッセージを受信後、受信したメッセージを次の転送先に送信する。
方法２ｇ：中継ノードが、受信メッセージの自動転送機能を持つハードウェアに対し、メッセージの内容別に、自動転送先を設定しておく。
【００６５】
受信メッセージの自動転送機能を持つハードウェアとして、たとえば、InfiniBandやTofuがある。Tofuにあるメッセージの自動転送機能は、CORE-Directと呼ばれる。
【００６６】
本実施例では、中継ノード上での中継処理をソフトウェアである中継制御エージェントが実行する。なお、中継ノードは、上記の自動転送機能を持つハードウェアを用いて、中継処理を実行してもよい。
【００６７】
異なるノード２０で動作する２つのコンポーネント間のインターフェースは、メッセージの送受信である。同一ノード１０で動作する２つのコンポーネント間のインターフェースは、たとえば、同一の仮想空間で動作している場合には、関数呼び出しがインターフェースであり、その際は、所定のデータを格納済みのメモリアドレスを通知することで、メモリ内容のコピーを行わない場合が多い。
【００６８】
ノード２０間のメッセージ通信は、同一のアプリケーションの異なるノード２０上の動作単位の間で実行される通信と、ＩＯサーバ上の分散ファイルシステムと、ノード２０上のアプリケーションの間で実行される通信とに大別する。また、次のような定義１ｈ、２ｈを行う。
定義１ｈ：ノード２０は、異なるプログラム間で通信を行う場合は、各プログラム間で共通のアプリケーションＩＤを取得しておくものとする。
定義２ｈ：ノード２０は、ＩＯサーバ上の分散ファイルシステムと通信を行う場合は、アプリケーションＩＤとして、特定の数値を割り当てておくものとする。たとえば、特定の数値を０とする。
【００６９】
なお、中継制御ノード１００は、物理ネットワーク内の経路設定依頼に対応して、経路ＩＤを付与し、経路構成管理表のエントリを追加しておく。
【００７０】
続いて、ノード２０等のコンポーネント間のメッセージ送受信に使用されるメッセージのデータ構造の一例について説明する。
【００７１】
図６は、ノードの中継制御エージェントが設定、参照するメッセージのデータ構造の一例を示す図である。図６に示すように、ノード２０の中継制御エージェントが設定、参照するメッセージ３０は、メッセージヘッダ３１ａと、ペイロード３１ｂとを有する。
【００７２】
図７は、ノードの通信ハードウェアにとってのメッセージのデータ構造の一例を示す図である。図７に示すように、ノード２０の通信ハードウェアにとってのメッセージ３０は、メッセージヘッダ３１ａと、中継ヘッダ３２ａと、本来のペイロード３２ｂとを有する。中継ヘッダ３２ａは、経路ＩＤ３３ａと、終点ノード座標３３ｂとを有する。このうち、経路ＩＤ３３ａは、通信経路を一意に示す情報を格納する。終点ノード座標３３ｂは、終点ノードの位置を示す情報を格納する。
【００７３】
図８は、始点ノードの中継制御エージェントとアプリケーションとの通信で用いられるメッセージのデータ構造の一例を示す図である。図８に示すように、このメッセージ３５は、経路ＩＤ３５ａと、終点ノード座標３５ｂと、アプリケーションＩＤ３５ｃと、ペイロード３５ｄとを有する。このうち、経路ＩＤ３５ａは、通信経路を一意に示す情報を格納する。終点ノード座標３５ｂは、終点ノードの位置を示す情報を格納する。アプリケーションＩＤ３５ｃは、アプリケーションを一意に識別する情報を格納する。ペイロード３５ｄは、各種のユーザデータを格納する。
【００７４】
図９は、本実施例に係るノードの構成を示す機能ブロック図である。図９に示すように、このノード２０は、通信ハードウェア２１と、記憶部２２と、制御部２３とを有する。通信ハードウェアは、メッセージを、メッセージの転送先となるノード２０に送信する装置である。
【００７５】
記憶部２２は、経路表情報２２ａと、経路割り当て情報２２ｂと、自ノード座標情報２２ｃとを有する。記憶部２２は、ＲＡＭ（Random  Access  Memory）、ＲＯＭ（Read  Only  Memory）、フラッシュメモリ（Flash  Memory）などの半導体メモリ素子や、ＨＤＤ（Hard  Disk  Drive）などの記憶装置に対応する。
【００７６】
図１０は、経路表情報のデータ構造の一例を示す図である。図１０に示すように、この経路表情報２２ａは、経路ＩＤと、終点ノード座標と、次の転送先ノード座標とを対応づける。経路ＩＤは、通信経路を一意に示す情報を格納する。終点ノード座標は、物理ネットワーク上の終点ノードの位置（座標）を示す情報を格納する。次の転送先ノード座標は、該当する経路ＩＤ、終点ノード座標の終点ノードにパケットを送信する場合の転送先となる隣接のノードの座標の情報を格納する。
【００７７】
経路表情報２２ａは、中継制御ノード１００から、経路設定依頼の応答として通知される。
【００７８】
図１１は、経路割り当て情報のデータ構造の一例を示す図である。図１１に示すように、この経路割り当て情報２２ｂは、経路ＩＤと、アプリケーションＩＤとを対応づける。経路ＩＤは、通信経路を一意に示す情報を格納する。アプリケーションＩＤは、アプリケーションを一意に示す情報である。たとえば、同一のノード２０であっても、複数のアプリケーションが動作し、各アプリケーションに異なる通信経路が割り当てられる場合がある。
【００７９】
自ノード座標情報２２ｃは、自ノード２０の座標に関する情報である。
【００８０】
制御部２３は、中継制御エージェント２３ａと、アプリケーション２３ｂとを有する。制御部２３は、ＣＰＵ（Central  Processing  Unit）やＭＰＵ（Micro  Processing  Unit）などによって実現できる。また、制御部２３は、ＡＳＩＣ（Application  Specific  Integrated  Circuit）やＦＰＧＡ（Field  Programmable  Gate  Array）などのハードワイヤードロジックによっても実現できる。
【００８１】
中継制御エージェント２３ａは、メッセージの中継処理を実行する処理部である。たとえば、中継制御エージェント２３ａは、メッセージを受信し、受信したメッセージが自ノード２０宛のメッセージである場合には、中継終了処理を実行する。中継制御エージェント２３ａは、受信したメッセージが自ノード２０宛のメッセージでない場合には、メッセージを次の転送先のノードに送信する。
【００８２】
図１２は、中継制御エージェントが実行する中継処理を示すフローチャートである。図１２に示すように、ノード２０の中継制御エージェント２３ａは、メッセージを受信する（ステップＳ１０１）。中継制御エージェント２３ａは、メッセージの中継ヘッダをキーに経路表情報２２ａのエントリを検索する（ステップＳ１０２）。
【００８３】
中継制御エージェント２３ａは、マッチするエントリが有るか否かを判定する（ステップＳ１０３）。中継処理エージェント２３ａは、マッチするエントリが有る場合には（ステップＳ１０３，Ｙｅｓ）、次の転送先に受信したメッセージと同じメッセージを送信する（ステップＳ１０４）。
【００８４】
中継処理エージェント２３ａは、マッチするエントリがない場合には（ステップＳ１０３，Ｎｏ）、中継終了処理を実行する（ステップＳ１０５）。
【００８５】
図１２のステップＳ１０５に示した中継終了処理について説明する。図１３は、中継終了処理を示すフローチャートである。図１３に示すように、中継処理エージェント２３ａは、経路ＩＤをキーに経路割り当て情報２２ｂを検索する（ステップＳ２０１）。中継処理エージェント２３ａは、マッチするエントリがない場合には（ステップＳ２０２，Ｎｏ）、処理を終了する。中継処理エージェント２３ａは、マッチするエントリがある場合には（ステップＳ２０２，Ｙｅｓ）、ステップＳ２０３に移行する。
【００８６】
中継処理エージェント２３ａは、マッチするエントリのアプリケーションＩＤでアプリケーションを特定する（ステップＳ２０３）。中継処理エージェント２３ａは、メッセージに格納された終点ノード座標と、自ノード座標とが等しいか否かを判定する（ステップＳ２０４）。
【００８７】
中継処理エージェント２３ａは、メッセージに格納された終点ノード座標と、自ノード座標とが等しい場合には（ステップＳ２０４，Ｙｅｓ）、アプリケーション２３ｂにペイロード格納領域を通知する（ステップＳ２０５）。
【００８８】
一方、中継処理エージェント２３ａは、メッセージに格納された終点ノード座標と、自ノード座標とが等しくない場合には（ステップＳ２０４，Ｎｏ）、終点ノード座標にメッセージを送信する（ステップＳ２０６）。
【００８９】
アプリケーション２３ｂは、たとえば、分散ファイルシステムに対応する。アプリケーション２３ｂは、複数のアプリケーションを含む。以下の説明では、適宜、アプリケーション２３ｂに含まれる複数のアプリケーションのうち、一つのアプリケーションを単にアプリケーションと表記する。
【００９０】
アプリケーションは、通信ハードウェア２１、中継制御エージェント２３ａを介して、対となる始点ノードまたは終点ノードのアプリケーションとメッセージを送受信する処理部である。たとえば、アプリケーションは、上記の中継処理エージェント２３ａから、ペイロード格納領域の通知を受け付け、データを取得する。
【００９１】
また、アプリケーションは、終点ノードに対してメッセージの送信を行う場合に、経路設定依頼を、中継制御ノード１００に送信する。これにより、中継制御ノード１００から、経路設定依頼の応答として、経路表情報２２ａを受信する。また、アプリケーションが、経路設定依頼を行う場合に、経路ＩＤと、アプリケーションＩＤとを対応づけたエントリが、経路割り当て情報２２ｂに格納される。
【００９２】
続いて、図３に示した中継制御ノード１００に関する処理を行う。以下の実施例では、メッセージ送信経路の管理は、中継制御ノード１００上で動作するソフトウェアである中継制御マネージャが実行する。各メッセージの中継制御は、各ノード２０のソフトウェアである中継制御エージェント２３ａが実行する。
【００９３】
中継制御ノード１００は、少なくともシステム全体で一つ設置される。なお、中継制御ノード１００の処理を、複数のノード２０が代わりに実行してもよい。たとえば、ＩＯノード２５との通信に際しての中継ノードの決定を、ＩＯノード２５毎に独立の中継制御マネージャによって実行してもよい。この場合には、中継制御ノード１００の数は、ＩＯノード２５の数と一致する。
【００９４】
本実施例では、ある１つのジョブＪが使用しているノード２０の集合Ｓと、ある１つのＩＯノードＩ（ジョブＩが使用するＩＯノード２０）との通信において、他のジョブ内のプロセス間通信との干渉を最小にする通信経路を、中継制御マネージャが特定する場合の処理を例示する。ただし、ジョブＪとＩＯノードＩとの間の通信と、他のジョブ内のプロセス間通信との干渉コストは、共通に使用されるリンクの数とする。
【００９５】
物理ネットワークでのリンクを辺、ノード２０を頂点とする物理ネットワークグラフΓｐを隣接リストで表現すると、図１４、図１５に示すものとなる。
【００９６】
図１４は、物理的なネットワークのトポロジーがメッシュである場合の隣接リストを説明する図である。図１４に示すように、たとえば、物理的なネットワークのトポロジーがメッシュである場合の隣接リストは、隣接リスト４０ａとなる。たとえば、頂点のノード「１」の隣接ノードは、ノード「２、４」となる。
【００９７】
図１５は、物理的なネットワークのトポロジーがトーラスである場合の隣接リストを説明する図である。図１５に示すように、たとえば、物理的なネットワークのトポロジーがトーラスである場合の隣接リストは、隣接リスト４０ｂとなる。たとえば、頂点のノード「１」の隣接ノードは、ノード「２，３，４，７」となる。
【００９８】
本実施例では、物理的なネットワークのトポロジーをメッシュあるいはトーラスとしているので、物理ネットワークグラフΓｐを隣接リストで表現すると、データ量が比較的小さくなる。たとえば、物理ネットワークグラフΓｐに対応する物理ネットワークがＮ次トーラスの場合には、各頂点の隣接リストは、２Ｎ個の頂点を要素に持つ。
【００９９】
本実施例に係る中継制御装置１００は、物理ネットワークグラフΓｐで他ジョブとの通信干渉を最小にする経路を求める処理を、次の２つの処理１ｉ、２ｉに分割して行う。
処理１ｉ：連結したアクティブノードをまとめた各連結成分を頂点とした連結成分グラフΓＣにおいて、通過コストが最小となる経路を求める。
処理２ｉ：処理１ｉで求めた経路の連結成分に含まれる各ノード２０を頂点とするグラフΓ１において、通過コストが最小となる経路を求める。
【０１００】
ここで、グラフΓ１における各連結成分内の経路は、他のジョブ内の経路の通信とは干渉しない。他のジョブとの通信との干渉の最小化は、連結成分グラフΓＣという物理ネットワークグラフΓｐより小さなグラフに置き換えることで、計算時間を抑止することができる。
【０１０１】
図１６は、本実施例に係る中継制御ノードの構成を示す機能ブロック図である。図１６に示すように、この中継制御ノード１００は、通信バードウェア１１０と、記憶部１２０と、制御部１３０とを有する。
【０１０２】
通信ハードウェア１１０は、ノード２０、ＩＯノード２５、ファイルサーバ２００との間でデータ通信を実行する通信装置である。たとえば、通信ハードウェア１１０は、依頼元のノード２０から、経路設定依頼を受信して、制御部１３０に出力する。たとえば、経路設定依頼メッセージには、後述する通信パラメタが含まれる。また、通信ハードウェア１１０は、制御部１３０から出力される経路設定依頼メッセージへの応答メッセージを、依頼元のノード２０に送信する。たとえば、応答メッセージには、後述する出力データ１２０ｃが含まれる。
【０１０３】
記憶部１２０は、入力データ１２０ａ、中間データ１２０ｂ、出力データ１２０ｃを有する。記憶部１２０は、ＲＡＭ、ＲＯＭ、フラッシュメモリなどの半導体メモリ素子や、ＨＤＤなどの記憶装置に対応する。
【０１０４】
たとえば、入力データ１２０ａは、「物理ネットワークグラフΓｐ（Ｖ，Ｅ）」と、「全ジョブの属性リスト」と、「通信パラメタ」とを含む。
【０１０５】
「物理ネットワークグラフΓｐ（Ｖ，Ｅ）」は、図３で示した物理ネットワークのトポロジーを連携リストでグラフ表現した情報である。物理ネットワークグラフΓｐ（Ｖ，Ｅ）の頂点Ｖは、ネットワーク内の全ノードのリストである。物理ネットワークグラフΓｐ（Ｖ，Ｅ）の辺Ｅは、システムのネットワークの中の全ての物理的なリンクに対応する構造体であり、各頂点Ｖの隣接リストを全て合わせたものとして取り扱う。
【０１０６】
また、各ノードには、ノード属性データが設定される。ノード属性データは、ノードＩＤ、ノードのネットワーク座標、ノード毎の隣接リスト、ノードの利用状況、ジョブＩＤを有する。
【０１０７】
ノードＩＤは、ノード２０（またはＩＯノード２５、以下同様）を一意に識別する情報である。ノードのネットワーク座標は、物理ネットワーク上のノード２０の座標（ｘ１，ｘ２，...，ｘ３）を示すものである。ノード毎の隣接リストは、ノードが持つ物理リンクの先に接続されたノード管理構造体へのポインタのリストである。ノードの利用状況は、ノードが、ノード２０（計算ノード）であるか、ＩＯノード２５であるかを識別する情報である。ジョブＩＤは、ノード２０を占有するジョブを一意に識別する情報である。たとえば、空きノードや、ＩＯノードに対応するジョブＩＤは、ＩＤとして無効な値「０」が設定される。
【０１０８】
「全ジョブの属性リスト」は、ジョブＩＤ、ジョブの状態、利用者ＩＤ、ジョブが占有するノード群のサブメッシュ領域のリスト、実行開始時刻（または実行開始予定時刻）、終了予定時刻、アクティブノード情報を有する。全ジョブの属性リストは、ジョブスケジューラから、割り当て状況の変化に応じて随時渡される（受信部１３０ａが、ジョブスケジューラから、全ジョブの属性リストを受信する）。たとえば、ジャブスケジューラーは、中継制御ノード１００で動作しても良いし、図示しないジョブ管理装置上で動作してもよい。ジョブスケジューラは、ジョブ管理部の一例である。
【０１０９】
ジョブＩＤは、ジョブを一意に識別する情報である。ジョブの状態は、ジョブが実行待ちであるか、実行中であるか、スワップアウト中であるかを示す情報である。利用者ＩＤは、ジョブを実行する利用者を一意に識別する情報である。
【０１１０】
ジョブが占有するノード群のサブメッシュ領域のリストは、ネットワーク座標の各次元での最小値（ｓ１，ｓ２，...，ｓｍ）と、ネットワーク座標の各次元での最大値（ｔ１，ｔ２，...，ｔｍ）を有する。
【０１１１】
実行開始時刻は、ジョブが処理を開始する時刻を示す。実行終了予定時刻は、ジョブが処理を終了する時刻を示す。
【０１１２】
アクティブノード情報は、空きノード全てのリスト、ＩＯノード全てのリスト、通信干渉を許容する全てのリスト、通信干渉を許容するジョブが使用しているノード全てのリストを有する。
【０１１３】
「通信パラメタ」は、通信するジョブの経路設定依頼メッセージに含まれる情報である。たとえば、通信パラメタは、通信するジョブのジョブＩＤ、通信の始点ノードのノードＩＤ、通信の終点ノードのノードＩＤ、アクティブノードの範囲指定を含む。
【０１１４】
アクティブノードの範囲指定には、同じジョブで動作するノードをアクティブノードにするか否かを指定、同じユーザＩＤのジョブで動作するノードをアクティブノードにするか否かの指定を含む。またアクティブノードの範囲指定には、干渉を許容するジョブを指定する情報が含まれる。干渉を許容するジョブで動作するノード２０は、始点ノードと終点ノードのジョブと異なっている場合でも、アクティブノードとなる。
【０１１５】
図１６の説明に戻る。中間データは、後述する中継制御マネージャ１３０ｂにより生成される情報である。中間データ１２０ｂは、アクティブノード全てのリスト、アクティブノード部分グラフ、アクティブノード部分グラフの連結成分リスト、アクティブノード部分グラフの連結成分の対のリスト、連結成分リストの情報を含む。また、中間データ１２０ｂは、アクティブノード部分グラフの連結成分間の最短経路、連結成分グラフの各辺の通信コスト、連結成分グラフでの最小費用流を与える経路の情報を含む。
【０１１６】
出力データ１２０ｃは、中継ノードリストと、各通信端点ノードに固有の付随情報と、各中継ノードに固有の付随情報を含む。たとえば、中継ノードリストは、通過コストが最小となる経路に含まれる各中継ノードのノードＩＤおよび各中継ノードのネットワーク座標を含む。
【０１１７】
制御部１３０は、受信部１３０ａと、中継制御マネージャ１３０ｂと、送信部１３０ｃとを有する。制御部１３０は、ＣＰＵやＭＰＵなどによって実現できる。また、制御部１３０は、ＡＳＩＣやＦＰＧＡなどのハードワイヤードロジックによっても実現できる。
【０１１８】
受信部１３０ａは、通信ハードウェア１１０を介して、入力データ１２０ａに含まれる各種情報を受信する。受信部１３０ａは、受信した情報を、入力データ１２０ａに格納する。
【０１１９】
中継制御マネージャ１３０ｂは、入力データ１２０ａを基にして、適宜、通過コストが最小となる経路を算出するための、中間データ１２０ｂを生成しつつ、最終的に出力データ１２０ｃを生成する処理部である。中継制御マネージャ１３０ｂは、中継制御部の一例である。
【０１２０】
送信部１３０ｃは、中継制御マネージャ１３０ｂにより生成された出力データを基にして、経路設定依頼メッセージへの応答メッセージを生成する。送信部１３０ｃは、通信ハードウェア１１０を介して、応答メッセージを、始点ノード２０に送信する。
【０１２１】
続いて、中継制御マネージャ１３０ｂの処理手順の一例について説明する。図１７は、中継制御マネージャが中継ノードを特定する処理手順を示すフローチャートである。図１７に示すように、中継制御マネージャ１３０ｂは、アクティブノードのリストを算出する（ステップＳ３０１）。中継制御マネージャ１３０ｂは、アクティブノード部分グラフを算出する（ステップＳ３０２）。
【０１２２】
中継制御マネージャ１３０ｂは、アクティブノード部分グラフの連結成分リストを算出する（ステップＳ３０３）。中継制御マネージャ１３０ｂは、連結成分グラフを算出する（ステップＳ３０４）。
【０１２３】
中継制御マネージャ１３０ｂは、連結成分グラフの辺と、通過コストを算出する（ステップＳ３０５）。中継制御マネージャ１３０ｂは、連結成分グラフでの最小費用流を算出する（ステップＳ３０６）。中継制御マネージャ１３０ｂは、連結成分グラフでの経路を、物理ネットワークへ引き戻し（ステップＳ３０７）、中継ノードを特定する（ステップＳ３０８）。
【０１２４】
図１７のステップＳ３０１に示したアクティブノードのリストを算出する処理について説明する。中継制御マネージャ１３０ｂは、入力データ１２０ａから、通信パラメタと、アクティブノード情報を取得する。中継制御マネージャ１３０ｂは、通信パラメタの指定に従って、アクティブノード情報に含まれる各種のノードのリストを合併することで、アクティブノードのリストを算出する。
【０１２５】
図１７のステップＳ３０２に示したアクティブノード部分グラフを算出する処理について説明する。中継制御マネージャ１３０ｂが、アクティブノード全てのリストを求めることで、アクティブノード部分グラフが求まったことになる。ここで、アクティブノード部分グラフの辺の情報は、各アクティブノードの隣接リストとなる。たとえば、Γｐの全ての空きのノード２０をＥとし、Ｅ∪Ｓ∪Ｉを含むΓｐの部分グラフをΓ１とする。
【０１２６】
図１７のステップＳ３０３に示したアクティブノード部分グラフの連結成分リストを算出する処理について説明する。中継制御マネージャ１３０ｂは、グラフ理論に基づいて、アクティブノード部分グラフの連結成分を求める。たとえば、図１で説明した例では、アクティブノード部分グラフの連結成分は、連結成分（Ｊ＋Ｅ）、（Ｉ＋Ｊ）、（Ｋ）、（Ｌ）となる。中継制御マネージャ１３０ｂは、各連結成分を、連結成分リストに登録する。
【０１２７】
図１７のステップＳ３０４に示した連結成分グラフを算出する処理について説明する。中継制御マネージャ１３０ｂは、アクティブノード部分グラフの連結成分リストから、２つの要素の対を全て取り出して、アクティブノード部分グラフの連結成分の対のリストに登録する。中継制御マネージャ１３０ｂは、アクティブノード部分グラフの連結成分の対のリストないし、全部を「辺」として、「連結成分グラフ」を生成する。
【０１２８】
たとえば、図１において、始点ノードが連結成分（Ｊ＋Ｅ）に含まれ、終点ノードが、連結成分（Ｉ＋Ｊ）に含まれる場合には、中継制御マネージャ１３０ｂは、連結成分の「対」を、連結成分（Ｊ＋Ｅ）と、連結成分（Ｉ＋Ｊ）との対とする。また、中継制御マネージャ１３０ｂは、連結成分（Ｌ）、（Ｋ）は、連結成分グラフの「辺」とする。
【０１２９】
図１７のステップＳ３０５に示した連結成分グラフの辺と、通過コストを算出する処理について説明する。中継制御マネージャ１３０ｂは、アクティブノード部分グラフの連結成分の対のリストである「連結成分リスト」の「辺」の各要素に対し、最短経路を求める。最短経路は、始点と終点とを含む。
【０１３０】
ここで、始点ノードと終点ノードとの通信は双方向に対称とする。すなわち、始点ノードと終点ノードとは通信方向を変えた場合に、始点ノードと終点ノードは、役割が入れ替わるが、上記の最短距離は、交換前と変わらない。
【０１３１】
中継制御マネージャ１３０ｂは、２つの連結成分（始点ノードを含む連結成分、終点ノードを含む連結成分）に対し、「マンハッタン距離」を算出する。たとえば、中継制御マネージャ１３０ｂは、マンハッタン距離を算出する場合には、最近傍点探索を実行すればよい。最短経路の両端点ノード（始点ノードおよび終点ノード）は、それぞれ異なる連結成分に含まれている。このとき、これらの端点ノードをこの連結成分の対についての、各連結成分の代表ノードと呼ぶ。
【０１３２】
図１８は、連結成分グラフの辺と、通過コストを算出する処理手順を示すフローチャートである。図１８に示すように、中継制御マネージャ１３０ｂは、直積集合Ｐの要素を全て含むリストＬを生成する（ステップＳ４０１）。
【０１３３】
中継制御マネージャ１３０ｂは、重みを格納する変数ｗを０で初期化する（ステップＳ４０２）。中継制御マネージャ１３０ｂは、ｐ＝（ｘ，ｙ）をリストＬの先頭要素とする（ステップＳ４０３）。
【０１３４】
中継制御マネージャ１３０ｂは、ｘからｙまでの次元順ルーティングでの経路が、Ｃｉ、Ｃｊ以外の連結成分と交差しない場合には（ステップＳ４０４，Ｎｏ）、ステップＳ４０５に移行する。一方、中継制御マネージャ１３０ｂは、ｘからｙまでの次元順ルーティングでの経路が、Ｃｉ、Ｃｊ以外の連結成分と交差する場合には（ステップＳ４０４，Ｙｅｓ）、ステップＳ４０９に移行する。
【０１３５】
中継制御マネージャ１３０ｂは、ｘからｙまでの経路のホップ数がｗより大きい場合には（ステップＳ４０５，Ｙｅｓ）、ステップＳ４０６に移行する。一方、中継制御マネージャ１３０ｂは、ｘからｙまでの経路のホップ数がｗより大きくない場合には（ステップＳ４０５，Ｎｏ）、ステップＳ４０９に移行する。
【０１３６】
中継制御マネージャ１３０ｂは、ｘからｙまでのホップ数を、ｗに格納する（ステップＳ４０６）。中継制御マネージャ１３０ｂは、連結成分の間の代表経路Ｅ（ｉ，ｊ）を暫定的にｐとする（ステップＳ４０７）。
【０１３７】
中継制御マネージャ１３０ｂは、リストＬからｐを取り除く（ステップＳ４０８）。中継制御マネージャ１３０ｂは、リストが空リストである場合には（ステップＳ４０９，Ｙｅｓ）、処理を終了する。中継制御マネージャ１３０ｂは、リストが空リストでない場合には（ステップＳ４０９，Ｎｏ）、ステップＳ４０３に移行する。
【０１３８】
ここで、図１８に示した処理における復帰値（重みｗ）の値が正の数となる場合には、Ｃｉに対するΓＣの頂点ｖｉと、Ｃｊに対するΓＣの頂点ｖｊとを結ぶ辺ｅｉｊが存在することを示す。この場合には、中継制御マネージャ１３０ｂは、ｅｉｊに対応する重みをｗｉｊとする。中継制御マネージャ１３０ｂが、図１８に示した処理を実行した後、Ｅ（ｉ，ｊ）の内容である、ノードの対（ｘ，ｙ）が、ΓＣの経路ｅｉｊに対応する経路成分ＣｉとＣｊ各々の代表ノードの対になる。
【０１３９】
中継制御マネージャ１３０ｂは、連結成分グラフの各辺の通過コストを、各辺の両端である連結成分において、上記の最短経路の始点ないし終点となるノード間の通信コスト（たとえば、マンハッタン距離）とする。
【０１４０】
なお、Γ１の連結成分で、Ｓを含むものをＣ１、Ｉを含むものをＣ２とする。たとえば、Ｓ⊂Ｃ１、Ｉ∈Ｃ２とする。Ｃ１＝Ｃ２のとき、Γ１の連結成分Ｃ１＝Ｃ２＝Ｃに含まれる頂点（ノード）と辺（リンク）だけを通る、ＳからＩへの通信経路が存在する。Ｃに含まれる通信経路を使用する通信は、他のジョブの通信と干渉しない。中継制御マネージャ１３０ｂは、Ｃ１≠Ｃ２のとき、連結成分グラフΓＣでの最小費用流を求めてから、後述する物理ネットワークΓＰへの経路に引き戻す。
【０１４１】
連結成分グラフΓＣでの辺の設定、および各辺の重みの計算は、ＣｉとＣｊにおいて「各連結成分に含まれない隣接ノードを持つノード」を、それぞれＤｉ＝∂Ｃｉ、Ｄｊ＝∂Ｃｊとするとき、次のように表現する。Ｄｉ，Ｄｊの「直積集合Ｐ＝Ｄｉ×Ｄｊ」とする。すなわち、（ｘ，ｙ）∈Ｐのとき、ｘ∈Ｄｉ，ｘ∈Ｄｊとする。
【０１４２】
図１７のステップＳ３０６に示した連結成分グラフでの最小費用流を算出する処理について説明する。中継制御マネージャ１３０ｂは、連結成分グラフΓＣにおいて、物理ネットワークでの通信の始点を含む連結成分を始点、物理ネットワークでの通信の終点を含む連結成分を終点として、最小費用流を与える経路を求める。ここでも、通信は双方向に対称として、始点と終点の役割を交換しても、最小費用流を与える経路であるとする。中心の始点をＳ、通信の終点をＩ（ＩＯノード２５）とする。
【０１４３】
中継制御マネージャ１３０ｂは、連結成分グラフΓＣの辺の重みｗを通過コストとし、ｖ１を始点、ｖ２を終点として、通過コストが最小となる経路Ｒ＝（ｖ１，ｘ１，ｘ２，...，ｘｍ，ｖ２）を求める。たとえば、図１に示した連結成分グラフにおいて、始点ノードを含む連結成分を連結成分（Ｊ＋Ｅ）、終点ノードを含む連結成分を連結成分（Ｉ＋Ｊ）とし、経路１０（Ｌ）の通過コストが、経路１０（Ｋ）の通過コストよりも大きい場合には、経路は、連結成分（Ｊ＋Ｅ）、経路１０（Ｋ）、連結成分（Ｉ＋Ｊ）となる。
【０１４４】
図１７のステップＳ３０６に示した連結成分グラフでの経路を物理ネットワークに引き戻す処理について説明する。中継制御マネージャ１３０ｂは、連結成分グラフΓＣで、通過経路が最小となる経路を、物理ネットワークでの経路に対応づけて、準最適な経路を特定する。
【０１４５】
ここで、「ｘ１，ｘ２，...，ｘｍ」に対応するグラフΓ１の連結成分を、Ｘ１，...，Ｘｍとする。中継制御マネージャ１３０ｂは、連結成分Ｃ１と連結成分Ｘ１の各代表ノードの対を（ｆ１，ｇ１）、連結成分Ｘ１と連結成分Ｘ２の各代表ノードの対を（ｆ２，ｇ２）...のように、順次、（ｆｍ−１，ｇｍ−１）まで、連結成分の各代表ノードの対を定める。
【０１４６】
連結成分ｍと連結成分Ｃ１の各代表ノードとの対を（ｆｍ，ｇｍ）とする。通信の始点ノードを、連結成分Ｃ１内のノードｇ０とする。通信の終点ノードを、連結成分Ｃ２内のノードｆｍ＋２とする。このとき、中継制御マネージャ１３０ｂは、ｇｊからｆｊ＋１までの、各連結成分の中のノードだけを通過する経路を求める。中継制御マネージャ１３０ｂは、求めた経路とｆｉからｇｉへの経路を結んだ、物理ネットワークグラフΓｐにおける経路ｒ＝（ｇ０，ｆ１，ｇ１，...，ｆｍ，ｇｍ，ｆｍ＋１）を、連結成分グラフΓＣから物理ネットワークグラフΓｐへの引き戻しとする。
【０１４７】
図１９は、物理ネットワークへの引き戻しを説明するための図である。図１９では簡単のため、ｍ＝１とする。
【０１４８】
図１９に示すように、連結成分グラフΓＣを、連結成分Ｃ１、連結成分Ｘ１、連結成分Ｃ２から構成される連結成分グラフとする。連結成分グラフΓＣにおいて、始点ｖ１から終点ｖ２までの経路（引き戻す前の経路）を、経路Ｒ（ｖ１，ｘ１，ｖ２）とする。連結成分Ｃ１と連結成分Ｘ１との辺に対する代表点を、それぞれｆ１、ｇ１とする。連結成分Ｃ１と連結成分Ｘ２との辺に対する代表点を、それぞれｆ２、ｇ２とする。
【０１４９】
中継制御マネージャ１３０ｂが、上記のような条件で、連結成分グラフΓＣを物理ネットワークに対応するグラフΓ０に対して、経路Ｒを引き戻すと、引き戻した経路ｒは、経路ｒ＝（ｇ０，ｆ１，ｇ１，ｆ２，ｇ２，ｆ３）となる。たとえば、連結成分毎に、代表点となるノード２０は、予め設定されているものとする。
【０１５０】
中継制御マネージャ１３０ｂは、経路ｒに経路ＩＤを付与し、経路構成管理表のエントリを追加する。メッシュないしトーラスネットワーク内部の経路は、ネットワーク座標の空間において、常に直角に曲がる線として表現される。このため、中継制御マネージャ１３０ｂは、経路の折れ線を構成する各線分の端点に対応する各ノードを、それぞれ中継ノードとして特定する。たとえば、図１９に示す例では、ノード２０Ａ、２０Ｂ、２０Ｃが、中継ノードとして特定される。
【０１５１】
中継制御マネージャ１３０ｂは、各中継ノードに対して、始点ノードから終点ノードへ至る時に通る順に「次の転送先ノード」を特定する。中継制御マネージャ１３０ｂは、各中継ノードに対して、経路ＩＤと、終点ノードの座標と、次の転送先ノードとを対応づけた経路表エントリを通知する。
【０１５２】
次に、中継制御ノード１００の処理手順について説明する。図２０は、本実施例に係る中継制御ノードの処理手順を示すフローチャートである。図２０に示すように、中継制御ノード１００の受信部１３０ａは、依頼元のノード２０から経路設定依頼メッセージを受信する（ステップＳ５０１）。
【０１５３】
中継制御ノード１００の中継制御マネージャ１３０ｂは、始点ノードから終点ノードに至る経路のうち、通過コストが最小となる経路における各中継ノードを特定する（ステップＳ５０２）。ステップＳ５０２の処理は、たとえば、図１７で示した処理に対応する。
【０１５４】
中継制御マネージャ１３０ｂは、各中継ノードに経路表エントリを通知する（ステップＳ５０３）。中継制御マネージャ１３０ｂは、始点ノードと終点ノードに経路ＩＤを通知する（ステップＳ５０４）。中継制御ノード１００の送信部１３０ｃは、依頼元のノードに、応答メッセージを送信する（ステップＳ５０５）。
【０１５５】
次に、本実施例に係る中継制御ノード１００の効果について説明する。中継制御ノード１００は、アクティブノードからなる連結成分と、他のノードから成る連結成分とを含む連結成分グラフを基にして、連結成分単位で通過コストの低い経路を求め、求めた経路を、実際の物理ネットワークに引き戻しを行うことで、各中継ノードを特定する。これにより、物理ネットワークのノード２０の数が多くても、ノード間通信経路を決定する中継ノードを、通過コストを考慮しつつ、時間をかけずに決定することができる。
【０１５６】
一般に、大規模な並列システムでは、大規模システムでした実行できない「多数のノードを動じ使用するジョブ」が実行されるので、「連結成分グラフ」は、元の物理ネットワークに対応するグラフと比べて頂点数が少ない。たとえば、平均的なジョブが１００ノードを同時に使用するシステムの場合、頂点数が１／１００のグラフで、通過コストが少ない経路を計算すればよく、計算コストを抑止できる。
【０１５７】
ところで、物理ネットワークにおいて「アクティブノードを頂点とする部分グラフの連結成分の対」全てから連結成分グラフの辺を生成すると、辺の数が連結成分の数の二乗のオーダーとなる。このため、中継制御マネージャ１３０ｂは、連結成分の対の一部だけを、連結成分グラフの辺として、辺の数を減少させても良い。
【０１５８】
上記のように、連結成分グラフの辺の数を減少させることで、辺の通過コストの計算時間が減少する利点、連結成分グラフにおける経路の計算時間を減少する利点がある。
【０１５９】
しかし、最短経路を与える可能性のある辺を排除しないようにすることが望ましい。たとえば、３つの連結成分Ｃ１、Ｃ２、Ｃ３について、連結成分Ｃ２が、連結成分Ｃ１、Ｃ３の中間の位置にある連結成分とする。この場合には、中継制御マネージャ１３０ｂは、連結成分Ｃ１、Ｃ２の間の辺と、連結成分Ｃ１、Ｃ３の間の辺を残し、連結成分Ｃ１、Ｃ３を直接結ぶ辺を排除する。
【０１６０】
中継制御マネージャ１３０ｂは、３つの連結成分Ｃ１、Ｃ２、Ｃ３について、連結成分Ｃ２が、連結成分Ｃ１、Ｃ３の中間の位置にある連結成分であることをどのように判定してもよい。たとえば、中継制御マネージャ１３０ｂは、ある連結成分に含まれる全ノードの各次元の座標の最小値と最大値とから、連結成分を含むサブメッシュを示すバウンティングボックスを作成する。
【０１６１】
ｍ次元のメッシュないしトーラスネットワークにおいて、各バウンディングボックスは、連結成分に含まれるノード数には関係無く、２ｍ個という一定の頂点がある。３つの連結成分Ｃ１、Ｃ２、Ｃ３のバウンティングボックスを、バウンティングボックスＢ１、Ｂ２、Ｂ３とする。バウンティングボックス頂点のネットワークアドレスを、ｍ次元ユークリッド空間の座標とする。中継制御マネージャ１３０ｂは、Ｂ１の頂点の１つと、Ｂ３の頂点の１つとを結ぶ直線が、Ｂ２の内部を通過するか否かを、定数個の頂点の組あわせの計算により判定する。
【０１６２】
図２１は、バウンディングボックスによる連結成分グラフの辺の数の削減を説明するための図である。たとえば、図２１に示すように、バウンティングボックスＢ１は、頂点（Ａ）、（Ｂ）、（Ｃ）、（Ｄ）を含む。バウンティングボックスＢ２は、頂点（０）、（１）、（２）、（３）を含む。バウンティングボックスＢ３は、頂点（ａ）、（ｂ）、（ｃ）、（ｄ）を含む。たとえば、中継制御マネージャ１３０ｂは、頂点（Ａ）と、頂点（ａ）とを結ぶ直線が、頂点（０）、（１）、（２）、（３）のうち隣接する２点を結ぶ辺との交点を持つ場合には、連結成分Ｃ２が、連結成分Ｃ１、Ｃ３の中間の位置にある連結成分であると判定する。
【０１６３】
次に、上記実施例に示した中継制御ノード１００と同様の機能を実現するコンピュータのハードウェア構成の一例について説明する。図２２は、中継制御ノードと同様の機能を実現するコンピュータのハードウェア構成の一例を示す図である。
【０１６４】
図２２に示すように、コンピュータ３００は、各種演算処理を実行するＣＰＵ３０１と、ユーザからのデータの入力を受け付ける入力装置３０２と、ディスプレイ３０３とを有する。また、コンピュータ３００は、記憶媒体からプログラム等を読み取る読み取り装置３０４と、外部装置との間でデータの授受を行うインターフェース装置３０５とを有する。また、コンピュータ３００は、各種情報を一時記憶するＲＡＭ３０６と、ハードディスク装置３０７とを有する。そして、各装置３０１〜３０７は、バス３０８に接続される。
【０１６５】
ハードディスク装置３０７は、受信プログラム３０７ａ、中継制御プログラム３０７ｂ、送信プログラム３０７ｃを有する。ＣＰＵ３０１は、受信プログラム３０７ａ、中継制御プログラム３０７ｂ、送信プログラム３０７ｃを読み出してＲＡＭ３０６に展開する。
【０１６６】
受信プログラム３０７ａは、受信プロセス３０６ａとして機能する。中継制御プログラム３０７ｂは、中継制御プロセス３０６ｂとして機能する。送信プログラム３０７ｃは、送信プロセス３０６ｃとして機能する。
【０１６７】
受信プロセス３０６ａの処理は、受信部１３０ａの処理に対応する。中継制御プロセス３０６ｂの処理は、中継制御マネージャ１３０ｂの処理に対応する。送信プロセス３０６ｃの処理は、送信部１３０ｃの処理に対応する。
【０１６８】
なお、各プログラム３０７ａ〜３０７ｃについては、必ずしも最初からハードディスク装置３０７に記憶させておかなくても良い。例えば、コンピュータ３００に挿入されるフレキシブルディスク（ＦＤ）、ＣＤ−ＲＯＭ、ＤＶＤディスク、光磁気ディスク、ＩＣカードなどの「可搬用の物理媒体」に各プログラムを記憶させておく。そして、コンピュータ２００が各プログラム３０７ａ〜３０７ｃを読み出して実行するようにしても良い。
【０１６９】
以上の各実施例を含む実施形態に関し、さらに以下の付記を開示する。
【０１７０】
（付記１）コンピュータに、
第１ノードから、第２ノードとのノード間通信を行うリクエストを受信し、
ジョブ管理部から現在のジョブ実行情報を受信し、
前記第１ノードの情報、前記第２ノードの情報、前記ジョブ実行情報および予め記憶したノード構造のトポロジー情報を基にして、連結成分グラフ情報を生成し、
前記連結成分グラフ情報を基にして、前記第１ノードおよび前記第２ノード間のノード間通信時に経由するノード群経由情報を複数生成し、
最も通過コストが低いノード群経由情報を選択し、
選択したノード群経由データのノード群間の位置情報を基にして、各ノード群から中継ノードを抽出する
処理を実行させることを特徴とする中継ノード決定プログラム。
【０１７１】
（付記２）前記連結成分グラフ情報を生成する処理は、前記第１ノード、前記第２ノード、複数の第３ノードのうち、アクティブノードを頂点とし、かつ、各頂点が連結する部分グラフと、アクティブノード以外の他のノードを頂点とし、かつ、各頂点が連結する部分グラフとを生成し、複数の部分グラフを、前記トポロジー情報を基にして接続することで、前記連結成分グラフを生成することを特徴とする付記１に記載の中継ノード決定プログラム。
【０１７２】
（付記３）前記ノード群経由情報を生成する処理は、前記連結成分グラフ情報を基にして、前記第１ノードを含む部分グラフから、他の部分グラフを経由して、前記第２ノードを含む部分ブラフに至る経路を複数生成し、生成した複数の経路のうち、最も通過コストの低い経路を、部分グラフ単位で特定し、特定した経路を基にして、前記ノード群経由情報を複数生成することを特徴とする付記２に記載の中継ノード決定プログラム。
【０１７３】
（付記４）コンピュータが実行する中継ノード決定方法であって、
第１ノードから、第２ノードとのノード間通信を行うリクエストを受信し、
ジョブ管理部から現在のジョブ実行情報を受信し、
前記第１ノードの情報、前記第２ノードの情報、前記ジョブ実行情報および予め記憶したノード構造のトポロジー情報を基にして、連結成分グラフ情報を生成し、
前記連結成分グラフ情報を基にして、前記第１ノードおよび前記第２ノード間のノード間通信時に経由するノード群経由情報を複数生成し、
最も通過コストが低いノード群経由情報を選択し、
選択したノード群経由情報のノード群間の位置情報を基にして、各ノード群から中継ノードを抽出する
処理を実行することを特徴とする中継ノード決定方法。
【０１７４】
（付記５）前記連結成分グラフ情報を生成する処理は、前記第１ノード、前記第２ノード、複数の第３ノードのうち、アクティブノードを頂点とし、かつ、各頂点が連結する部分グラフと、アクティブノード以外の他のノードを頂点とし、かつ、各頂点が連結する部分グラフとを生成し、複数の部分グラフを、前記トポロジー情報を基にして接続することで、前記連結成分グラフを生成することを特徴とする付記４に記載の中継ノード決定方法。
【０１７５】
（付記６）前記ノード群経由情報を生成する処理は、前記連結成分グラフ情報を基にして、前記第１ノードを含む部分グラフから、他の部分グラフを経由して、前記第２ノードを含む部分ブラフに至る経路を複数生成し、生成した複数の経路のうち、最も通過コストの低い経路を、部分グラフ単位で特定し、特定した経路を基にして、前記ノード群経由情報を複数生成することを特徴とする付記５に記載の中継ノード決定方法。
【０１７６】
（付記７）第１ノードから、第２ノードとのノード間通信を行うリクエストを受信し、ジョブ管理部から現在のジョブ実行情報を受信する受信部と、
前記第１ノードの情報、前記第２ノードの情報、前記ジョブ実行情報および予め記憶したノード構造のトポロジー情報を基にして、連結成分グラフ情報を生成し、前記連結成分グラフ情報を基にして、前記第１ノードおよび前記第２ノード間のノード間通信時に経由するノード群経由情報を複数生成し、最も通過コストが低いノード群経由情報を選択し、選択したノード群経由情報のノード群間の位置情報を基にして、各ノード群から中継ノードを抽出する中継制御部と
を有することを特徴とする並列処理装置。
【０１７７】
（付記８）前記中継制御部は、前記第１ノード、前記第２ノード、複数の第３ノードのうち、アクティブノードを頂点とし、かつ、各頂点が連結する部分グラフと、アクティブノード以外の他のノードを頂点とし、かつ、各頂点が連結する部分グラフとを生成し、複数の部分グラフを、前記トポロジー情報を基にして接続することで、前記連結成分グラフを生成することを特徴とする付記７に記載の並列処理装置。
【０１７８】
（付記９）前記中継制御部は、前記連結成分グラフ情報を基にして、前記第１ノードを含む部分グラフから、他の部分グラフを経由して、前記第２ノードを含む部分ブラフに至る経路を、前記ノード経由情報として複数生成することを特徴とする付記８に記載の並列処理装置。
【符号の説明】
【０１７９】
２０  ノード
２５  ＩＯノード
１００  中継制御ノード
２００  ファイルサーバ
【図１】
2019021127.tif 000003
【図２】
2019021127.tif 000004
【図３】
2019021127.tif 000005
【図４】
2019021127.tif 000006
【図５】
2019021127.tif 000007
【図６】
2019021127.tif 000008
【図７】
2019021127.tif 000009
【図８】
2019021127.tif 000010
【図９】
2019021127.tif 000011
【図１０】
2019021127.tif 000012
【図１１】
2019021127.tif 000013
【図１２】
2019021127.tif 000014
【図１３】
2019021127.tif 000015
【図１４】
2019021127.tif 000016
【図１５】
2019021127.tif 000017
【図１６】
2019021127.tif 000018
【図１７】
2019021127.tif 000019
【図１８】
2019021127.tif 000020
【図１９】
2019021127.tif 000021
【図２０】
2019021127.tif 000022
【図２１】
2019021127.tif 000023
【図２２】
2019021127.tif 000024
【図２３】
2019021127.tif 000025
【図２４】
2019021127.tif 000026
【図２５】
2019021127.tif 000027