(57)【要約】      （修正有）【課題】故障によって通信経路が遮断された場合に迂回経路を確立しやすくした、並列計算機システム、並列計算機システム制御方法を提供する。【解決手段】通信経路を介して接続された複数のノードを備える並列計算機と、並列計算機内の所定数のノードにジョブを割り当てる制御装置とを有する。制御装置は，ジョブを割り当てた複数のノードを有するＮ次元ジョブノードの周囲領域に、ジョブが割り当てられていない空ノード、ジョブが割り当てられている０次元ジョブノード、ジョブが割り当てられているＭ（Ｍ＝＜Ｎ）次元ジョブノードの１ノード長の辺または面のノードのいずれかを割り当てるジョブ割り当て処理部と、Ｎ次元ジョブノード内に故障が発生した場合、周囲領域内のノードの少なくとも１つのノードを中継ノードに割り当て、中継ノードを経由する経路を迂回経路として選択、迂回経路を介してノード間通信を実行させる故障処理部と、を有する。【選択図】図１２
2016038649.tif 000002
【特許請求の範囲】
【請求項１】
計算をそれぞれ実行するとともに通信経路を介して接続される複数のノードを備える並列計算機と，
前記並列計算機内の所定数のノードにジョブを割り当てる制御装置とを有し，
前記制御装置は，
第１のジョブを割り当てた複数のノードを有する第１のＮ（Ｎは１以上）次元ジョブノードの周囲領域に，ジョブが割り当てられていない空ノードと，ジョブが割り当てられている０次元ジョブノードと，ジョブが割り当てられているＭ（Ｍ＝＜Ｎ）次元ジョブノードの１ノード長の辺または面のノードのいずれかを割り当てるジョブ割り当て処理部と，
前記第１のＮ次元ジョブノード内に故障が発生した場合，前記周囲領域内のノードの少なくとも１つのノードを中継ノードに割り当てるとともに，前記中継ノードを経由する経路を，前記故障により通信に支障が生じた通信経路に対する迂回経路として選択し，前記迂回経路を介して前記ノード間の通信を実行させる故障処理部とを有する並列計算機システム。
【請求項２】
前記ジョブ割り当て処理部は，前記第１のＮ次元ジョブノードを，第２のジョブを実行中の複数のノードを有する第２のＮ次元ジョブノードと，前記周囲領域を介して隣接するように割り当てる
請求項１に記載の並列計算機システム。
【請求項３】
前記通信経路は，ルーティングルールに従う始点ノードから経由ノードを経由し終点ノードに至る経路であり，
前記迂回経路は，前記始点ノードから経由ノードを経由し前記中継ノードに至る第１の迂回経路と，前記中継ノードから経由ノードを経由し前記終点ノードに至る第２の迂回経路とを有し，
前記始点ノードが送出したパケットは，前記ルーティングルールに従って前記第１の迂回経路を伝搬して前記中継ノードに到達し，
前記中継ノードが送出したパケットは，前記ルーティングルールに従って前記第２の迂回経路を伝搬して前記終点ノードに到達する
請求項１または２に記載の並列計算機システム。
【請求項４】
前記中継ノードは，受信したパケットをバッファリングし，前記パケットの始点座標と終点座標を書き換え，前記書き換えたパケットを前記第２の迂回経路に応じて送出し，
前記経由ノードは，前記パケットの始点座標と終点座標に基づいて，伝搬してきた前記パケットをルーティングする
請求項３に記載の並列計算機システム。
【請求項５】
前記Ｍ次元ジョブノード内のノード間のパケットのルーティング方向と，前記迂回経路を伝搬するパケットが前記Ｍ次元ジョブノードの１ノード長の辺のノードでのルーティング方向とが異なる
請求項３に記載の並列計算機システム。
【請求項６】
前記制御装置の故障処理部は，前記中継ノードを，前記周囲領域内の前記空きノードから選択する，
請求項１に記載の並列計算機システム。
【請求項７】
計算をそれぞれ実行するとともに通信経路を介して接続される複数のノードを備える並列計算機と，前記並列計算機内の所定数のノードにジョブを割り当てる制御装置とを有する並列計算機システムの制御方法において，
前記制御装置が、
第１のジョブを割り当てた複数のノードを有する第１のＮ（Ｎは１以上）次元ジョブノードの周囲領域に，ジョブが割り当てられていない空ノードと，ジョブが割り当てられている０次元ジョブノードと，ジョブが割り当てられているＭ（Ｍ＝＜Ｎ）次元ジョブノードの１ノード長の辺または面のノードのいずれかを割り当て，
前記第１のＮ次元ジョブノード内に故障が発生した場合，前記周囲領域内のノードの少なくとも１つのノードを中継ノードに割り当てるとともに，前記中継ノードを経由する経路を，前記故障により通信に支障が生じた通信経路に対する迂回経路として選択し，前記迂回経路を介して前記ノード間の通信を実行させる並列計算機システムの制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は，並列計算機システム及び並列計算機システムの制御方法に関する。
【背景技術】
【０００２】
高性能計算を行う計算機システムは，ノードと呼ばれる複数のプロセッサをリンクで接続したノード結合網を有し，計算処理などのジョブを割り当てられた複数のノードが互いに通信しながら並列に処理を行う。並列計算機システムは，プロセッサの数が増加するほど高性能になり，同時にシステム内のどこかで故障する可能性が高くなる。
【０００３】
多数のプロセッサをリンクで接続した並列計算機システム内の故障には，ノード内のプロセッサやメモリの故障，ノード内のルータの故障，ノード間を接続するリンクの断線などの故障がある。ジョブ実行中にどこかで故障が発生した場合，故障箇所を含む領域で実行中のジョブや，故障箇所を通過する通信経路を使用するジョブの実行に支障がでるので何らかの対処が必要になる。
【０００４】
以下の特許文献には，ノード故障が発生した場合，故障ノードを含む部分集合のジョブを停止し，新たにノードを割り付けて実行する処理が記載されている。また，プロセッサ間の通信経路が故障した場合に故障回避用のチャネルを確保する処理が記載されている。また，並列計算機システムのインターコネクトについて記載されている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特表２００７−５３３０３１号
【特許文献２】特開平０６−２６６６８４号公報
【非特許文献】
【０００６】
【非特許文献１】FUJITSU. 63, 3, P.260-264 「スーパーコンピュータ「京」のインターコネクトTofu」，05,2012
【発明の概要】
【発明が解決しようとする課題】
【０００７】
発生した故障がルータの故障やリンクの故障の場合は，ノード間の通信経路が遮断される。その場合，遮断された通信経路に代わる迂回経路を確立することができれば，故障が発生したにもかかわらず，ジョブを継続して実行することができる。
【０００８】
しかしながら，迂回経路を確立することは，ハードウエア的なルーティングの制限により不可能な場合がある。また，ジョブを割り当てるノードの数を増やしてノード群の領域サイズを増大することで，ジョブを別のノードに割り当ててジョブを再開することができる。しかし，メッシュ又はトーラスなどの直接網では，ジョブのノード群は矩形や直方体など稠密な形に割り当てられるのが一般的である。そのため，矩形や直方体の形を崩さずにサイズを大きくすると必要以上の数のノードを追加する必要があり，ノードの効率化に反する場合がある。
【０００９】
そこで，本発明の目的は，故障によって通信経路が遮断された場合に迂回経路を確立しやすくした並列計算機システム及び並列計算機システムの制御方法を提供することにある。
【課題を解決するための手段】
【００１０】
本実施の形態の第１の側面は，計算をそれぞれ実行するとともに通信経路を介して接続される複数のノードを備える並列計算機と，
前記並列計算機内の所定数のノードにジョブを割り当てる制御装置とを有し，
前記制御装置は，
第１のジョブを割り当てた複数のノードを有する第１のＮ（Ｎは１以上）次元ジョブノードの周囲領域に，ジョブが割り当てられていない空ノードと，ジョブが割り当てられている０次元ジョブノードと，ジョブが割り当てられているＭ（Ｍ＝＜Ｎ）次元ジョブノードの１ノード長の辺または面のノードのいずれかを割り当てるジョブ割り当て処理部と，
前記第１のＮ次元ジョブノード内に故障が発生した場合，前記周囲領域内のノードの少なくとも１つのノードを中継ノードに割り当てるとともに，前記中継ノードを経由する経路を，前記故障により通信に支障が生じた通信経路に対する迂回経路として選択し，前記迂回経路を介して前記ノード間の通信を実行させる故障処理部とを有する並列計算機システムである。
【発明の効果】
【００１１】
第１の側面によれば，故障によって通信経路が遮断された場合に迂回経路を確立しやすくなる。
【図面の簡単な説明】
【００１２】
【図１】並列計算機のメッセージ送信の第１のルーティング例を説明する図である。
【図２】並列計算機のメッセージ送信の第２のルーティング例を説明する図である。
【図３】並列計算機のメッセージ送信の第３のルーティング例を説明する図である。
【図４】複数ノード群の領域を拡張する場合を説明する図である。
【図５】本実施の形態における並列計算機システムとノードの構成を示す図である。
【図６】並列計算機内の入出力装置３３の構成図である。
【図７】並列計算機システムの制御装置の構成を示す図である。
【図８】制御装置５０の構成を示す図である。
【図９】本実施の形態における制御装置によるジョブ割り当て例を示す図である。
【図１０】本実施の形態における制御装置によるジョブ割り当て処理のフローチャート図である。
【図１１】ジョブ割り当て処理の途中の状態を示す図である。
【図１２】本実施の形態における第１の迂回経路の例を示す図である。
【図１３】本実施の形態における第２の迂回経路の例を示す図である。
【図１４】本実施の形態における第３の迂回経路の例を示す図である。
【図１５】本実施の形態における故障処理のフローチャート図である。
【図１６】図１５の通信経路の回復の処理Ｓ１８のフローチャート図である。
【図１７】図１６の処理Ｓ２８の周囲領域内での中継ノードの選択処理のフローチャート図である。
【図１８】中継ノードの構成を示す図である。
【図１９】中継ノードを経由する迂回経路のルーティングを説明する図である。
【図２０】３次元ジョブノードの周囲領域に配置するノードの例を示す図である。
【発明を実施するための形態】
【００１３】
図１は，並列計算機のメッセージ送信の第１のルーティング例を説明する図である。図１に示された並列計算機は，二次元メッシュのトポロジで構成され，計算を実行する複数のノードＮＤと，ノード間をそれぞれ接続する複数のリンクＬＮとを有する。各ノードＮＤは，プロセッサとメモリとルータとを有する。図示しない制御装置は，処理すべきジョブを所定数のノードに割り当てて，ジョブの実行を制御する。ジョブが割り当てられた複数のノードのプロセッサは，メッセージをお互いに交換しながらジョブを並列に処理する。
【００１４】
図１のルーティングは，一例として，次元オーダルーティングである。次元オーダルーティングによれば，始点ノードから終点ノードまでの最短経路は，最初にＸ軸方向に進み，次にＹ軸方向に進むというルールの制限下で決定される。このルールによれば，最初にＹ軸方向に進むと次にＸ軸方向に進むことはできない。なお，並列計算機が３次元メッシュで構成される場合は，次元オーダルーティングによる経路は，最初にＸ軸方向，次にＹ軸方向，最後にＺ軸方向に進むというルールの制限の下で決定される。
【００１５】
図１において，番号１のノードから番号１１のノードへの通信経路は，破線矢印１０で示すとおり，番号１のノードから番号３のノードへのＸ軸方向の経路と，番号３のノードから番号１１のノードへのＹ軸方向の経路とで構成される。しかし，番号７のノードのルータが故障した場合，番号３のノードから番号１１のノードへのＹ軸方向の通信経路が遮断される。この場合，実線矢印１１で示すような通信経路は，故障箇所Ｆ１を迂回する経路であるが，次元オーダルーティングに反するため利用できない。したがって，故障箇所Ｆ１を迂回して番号１のノードから番号１１のノードにメッセージパケットを送信することが不可能になり，実行中のジョブを中止し，別のノード群にジョブを割り当ててジョブを最初から再開しなければならず，計算資源の利用効率の低下を招く。
【００１６】
図２は，並列計算機のメッセージ送信の第２のルーティング例を説明する図である。図２に示された並列計算機は，２次元トーラスのトポロジで構成され，複数のノードＮＤとそれらを接続する複数のリンクＬＮで構成される。Ｘ軸方向のリンクは，右端のノードと左端のノードとを接続するトーラスのリンクＴＲを有する。Ｙ軸方向も同様にトーラスのリンクを有する。
【００１７】
図２のルーティングは，一例として，West-First-Turnルーティングである。この場合の始点ノードから終点ノードまでの最短経路が，西方向の経路は最初でなければならないというルールの制限下で決定される。ノードＮＤ１からノードＮＤ２への通信経路は，破線矢印１２に示したように最初に西方向の経路，次ぎに北方向の経路からなる。しかし，故障箇所Ｆ２，Ｆ４の２カ所のリンクで故障が発生し，故障箇所Ｆ３のノードのルータが故障した場合，ノードＮＤ１からノードＮＤ２への通信経路は遮断される。実線矢印１３で示した迂回経路は，北方向の経路の後に西方向の経路があるので，West-First-Turnルーティングのルールに反するからである。つまり，３つの故障箇所Ｆ２−Ｆ４の発生により，ノードＣからノードＢへの経路は遮断されないが，複数のノードＡからノードＢへの迂回経路は利用できないことになる。そのため，これらのノード間でメッセージ送信が不可能になり，実行中のジョブを中止し，別のノードにジョブを割り当ててジョブを再開しなければならなくなる。
【００１８】
図３は，並列計算機のメッセージ送信の第３のルーティング例を説明する図である。この並列計算機は，２次元メッシュのトポロジで構成され，West-First-Turnルーティングである。このトポロジはトーラスではないため，故障箇所Ｆ５のノードのルータが故障すると，ノードＮＤ３からノードＮＤ４への通信経路１４が遮断される。そして，実線矢印１５の迂回経路は，West-First-Turnルーティングに反するので利用できない。結局，故障箇所Ｆ５を経由する経路が遮断されると，複数のノードＡから複数のノードＢへの通信経路は利用できなくなる。その結果，実行中のジョブを中止し，他のノードにジョブを再度割り当ててジョブを最初から再開しなければならない。一般に，２次元メッシュの場合は，２次元トーラスよりも故障の発生により迂回経路を選択することがより困難になる。
【００１９】
図４は，複数ノード群の領域を拡張する場合を説明する図である。上記のとおり，故障の発生により故障を迂回する経路がなくなる場合は，ジョブを割り当てているノード群の領域を拡張し，拡張により追加したノードに中止したジョブを割り当てる必要がある。しかしながら，ジョブを複数のノードに割り当てる場合，ジョブ間の干渉を避けるため，割り当てられるジョブ群は矩形や直方体など稠密な形状が好ましい。
【００２０】
図４において，あるジョブが複数ノード領域２０に割り当てられている場合に，領域２１が相互通信不可能になると仮定する。この場合，領域２１のノードで実行されていたジョブは中止され，複数ノード領域２２に拡張される。拡張された複数ノード領域２２は元々の複数ノード領域２０の矩形を維持して拡張される。しかし，中止したジョブを割り当てるノード群２３は，拡張により増加したノード数よりも少ない場合がある。その結果，拡張により増加したノードの一部しか利用されなくなり，計算資源の効率化の低下を招く。
【００２１】
上記のように，ジョブが割り当てられているノード領域内で故障が発生しても，迂回経路を選択できる可能性を高くしつつ，計算資源の効率化の低下が生じないようにすることが望まれる。
【００２２】
［本実施の形態における並列計算機システム］
図５は，本実施の形態における並列計算機システムとノードの構成を示す図である。並列計算機システムは，計算を実行する複数のノードＮＤとノード間をそれぞれ接続する複数のリンクＬＮとを有する並列計算機３０と，並列計算機内のノードＮＤにジョブを割り当ててジョブの実行を制御する制御装置５０とを有する。並列計算機３０は，複数のノードＮＤとリンクＬＮとで形成されるノードの結合網３２と，ストーレージを有する入出力装置３３とを有する。
【００２３】
ノードＮＤは，プロセッサであるＣＰＵ４０と，主記憶装置４１と，ルータ４２とを有する。プロセッサ４０は，例えば複数のＣＰＵコアを有するマルチコアプロセッサである。ノードＮＤにはノードの故障状態を検知する故障検知装置４３が設けられている。したがって，ノードＮＤ内のプロセッサ４０にジョブが割り当てられ，ジョブが割り当てられたプロセッサ４０はジョブの演算処理を実行する。
【００２４】
また，プロセッサ４０は，他のノードのプロセッサとメッセージを交換しながら計算を実行しジョブを並列に処理する。ルータ４２は，ノードがメッセージ通信の始点ノードの場合は，メッセージをルーティングルールに基づいていずれかのリンクＬＮに送出する。ルータ４２は，メッセージが経由する経由ノードの場合は，あるリンクＬＮから伝搬してきたメッセージを，そのヘッダ内の終点座標とルーティングに必要な付加情報とを参照し，ルーティングルールに基づいて次のノードにルーティングする。
【００２５】
ノードのプロセッサ４０は，割り当てられたジョブを実行する。また，ノードのプロセッサ４０は，メッセージを送信する場合ヘッダに始点座標と終点座標を収納したメッセージパケットをメモリ内に生成し，ルータ４２は，ルーティングルールに基づいてメッセージパケットを送出する。プロセッサ４０は，メッセージパケットを受信した場合ヘッダ内の終点座標が自分の座標であればメッセージパケットをメモリ内にバッファリングし，必要な処理を実行する。さらに，ノードのルータ４２は，受信したメッセージパケットのヘッダ内の始点座標と終点座標を参照し，ルーティングルールに基づく転送先にそのパケットをルーティングする。
【００２６】
したがって，ノードが故障した場合でも，プロセッサ４０が故障した場合はノードによるジョブの実行処理は不能になり，始点ノードとしてメッセージパケットを送出することができなくなり，終点ノードとしてメッセージパケットを受信することができなくなる。ルータ４２が故障した場合は，パケットの送出と受信ができなくなり，パケットの転送もできなくなる。そして，リンクが切断するなどリンクが故障した場合，そのリンクを経由するパケットの送信ができなくなる。
【００２７】
図６は，並列計算機内の入出力装置３３の構成図である。入出力装置３３は複数のハードディスクＨＤＤ等の大容量記憶媒体を有する。入出力装置３３は，ノード結合網３２と接続されるホストチャネルアダプタＨＣＡと，スイッチ３４と，スイッチとＨＤＤとを接続するターゲットチャネルアダプタＴＣＡとを有する。ノード結合網３２内の複数のノードのプロセッサは，入出力装置３３内の大容量記憶媒体にアクセス可能になっている。
【００２８】
図７は，並列計算機システムの制御装置の構成を示す図である。制御装置５０は例えばサーバであり，並列計算機のノード結合網３２と同様に，複数のノードとそれらを結合するリンクで構成されてもよい。制御装置５０は，ネットワーク５１とスイッチ群とを介して並列計算機のノード網３２内の複数のノードＮＤと接続される。
【００２９】
図８は，制御装置５０の構成を示す図である。制御装置５０は前述のとおりサーバ装置である。制御装置５０は，プロセッサであるＣＰＵと，入出力装置Ｉ／Ｏと，メインメモリ５２と，ネットワーク５１とのインターフェースであるネットワークインターフェース５３とを有する。メインメモリ５２内には，ユーザから要求されたジョブを並列計算機のノードに割り当てるジョブ割り当てプログラム５２−１と，並列計算機内に故障が発生した場合に故障処理を行う故障処理プログラム５２−２が格納され，プロセッサＣＰＵにより実行される。また，メインメモリ５２内には，ユーザから要求されたジョブを格納するジョブキュー５２−３と，ジョブを実行中のノードを記録するジョブ実行ノード記憶テーブル５２−４と，故障箇所を記録する故障箇所記憶テーブル５２−５とが格納される。
【００３０】
ユーザによる入出力装置Ｉ／Ｏからのジョブの実行要求に応答して，制御装置５０は，ジョブキュー５２−３に要求されたジョブをエントリする。そして，プロセッサＣＰＵは，ジョブ割り当てプログラム５２−１を実行して，並列計算機の必要な数のノードにジョブを割り当てて，そのジョブの実行開始を制御する。それと共に，プロセッサＣＰＵは，ジョブ実行中のノードをジョブ実行ノード記憶テーブル５２−４に登録する。各ノードに設けられている故障検知装置４３から故障検知通知を受信すると，プロセッサＣＰＵは，故障処理プログラム５２−２を実行して，故障箇所記憶テーブル５２−５に故障箇所と故障内容を登録し，ジョブの停止，再開，迂回経路の探索など後述する故障処理を行う。
【００３１】
［ジョブ割り当て処理］
本実施の形態の並列計算機システムでは，発生した故障により通信経路に支障が生じている場合に迂回経路を確立できる可能性を高めるために，制御装置が，中断が許されないジョブ，つまり継続実行が要求されるような重要度が高いジョブを，次のようにノードに割り当てる。
【００３２】
図９は，本実施の形態における制御装置によるジョブ割り当て例を示す図である。この例は，並列計算機のノード結合網３２のトポロジが８×８の２次元メッシュであり，ルーティングはWest-First-Turnモデルである。但し，本実施の形態は，任意のＮ次元メッシュまたはＮ次元トーラスなどの種々のトポロジや，次元オーダルーティングなど他のルーティングモデルにも適用できる。
【００３３】
図９において，白丸のノードは，ジョブが割り当てられておらずプロセッサが計算を実行していないノードであり，待機ノードまたは空ノードＥ＿ＮＤと称する。右上がり斜線のノードは，１つのノード単独でジョブを割り当てられてそのジョブを実行中のノードであり，０次元ジョブノード０Ｄ＿ＪＮＤと称する。次に，左上がり斜線のノードは，ジョブが割り当てられてジョブ実行中の複数のノードであり，ある１次元方向に配置されたノードであり，１次元ジョブノード１Ｄ＿ＪＮＤと称する。さらに，黒丸のノードは，ジョブが割り当てられ２次元に配置されたノードであり，２次元ジョブノード２Ｄ＿ＪＮＤと称する。
【００３４】
図９の例は，簡単のために２次元メッシュにしている。したがって，２次元ジョブノードが最大の次元数になる。３次元メッシュの場合は，最大次元の３次元ジョブノードにジョブが割り当てられることがある。一般化すると，Ｋ次元メッシュの場合は，０次元〜Ｋ次元ジョブノードにジョブが割り当てられることが可能である。
【００３５】
空ノードＥ＿ＮＤは，プロセッサは動作停止中であるが，そのルータは伝搬するメッセージパケットをルーティングしている。０次元ジョブノード０Ｄ＿ＪＮＤは，単一のプロセッサによりジョブを実行しているので，他のノードのプロセッサとメッセージを送受信することはない。
【００３６】
一方，１次元ジョブノード１Ｄ＿ＪＮＤは，１次元方向に配置された複数のノードがジョブを並列に計算している。したがって，１次元ジョブノード内の複数のノードのプロセッサは，互いにメッセージを送受信しあっていて，ルータは１次元ジョブノード内のメッセージを一次元方向にルーティングすることに加えて，１次元ジョブノードの外のノード間のメッセージをルーティングする。
【００３７】
次に，本実施の形態における制御装置によるジョブ割り当て処理について説明する。制御装置５０は，ユーザから要求されたジョブを，ジョブの処理量に適した数のノードに割り当てる。ジョブが複数のノードに割り当てられる場合，他のジョブとの干渉を避けるために矩形や直方体など稠密な形状の領域のノードに割り当てられる。つまり，ジョブは外形が凸凹の領域には割り当てない。
【００３８】
また，図９の例は２次元メッシュであるので，ジョブが割り当てられるジョブノードの領域の形状は，０次元ジョブノード０Ｄ＿ＪＮＤと，１次元ジョブノード１Ｄ＿ＪＮＤと，２次元ジョブノード２Ｄ＿ＪＮＤの３種類になる。３次元メッシュであれば，３次元ジョブノードが追加され，Ｎ次元メッシュであればＮ次元ジョブノードまでジョブが割り当て可能である。
【００３９】
図９では，制御装置５０が，３つの２次元ジョブノード２Ｄ＿ＪＮＤ１〜３にそれぞれジョブを割り当てられている。このうち，２次元ジョブノード２Ｄ＿ＪＮＤ１には継続実行が要求されるなどの重要なジョブが割り当てられると仮定する。
【００４０】
制御装置５０は，まず，重要ジョブが割り当てられた２次元ジョブノード２Ｄ＿ＪＮＤ１の周囲領域，つまり一点鎖線６０と２次元ジョブノード２Ｄ＿ＪＮＤ１との間の周囲領域には，空ノードＥ＿ＮＤ，０次元ジョブノード０Ｄ＿ＪＮＤ，１次元ジョブノード１Ｄ＿ＪＮＤの一端のノードのいずれかを割り当てる。特に，１次元ジョブノード１Ｄ＿ＪＮＤの場合は，１次元形状の一端のノードだけが重要ジョブの２次元ジョブノード２Ｄ＿ＪＮＤ１に隣接するように割り当てる。つまり，制御装置は，１次元ジョブノード１Ｄ＿ＪＮＤの辺の長さが１ノードの辺が重要ジョブの２次元ジョブノード２Ｄ＿ＪＮＤ１のいずれかの辺に接するように割り当てる。
【００４１】
図９の例では，重要ジョブの２次元ジョブノード２Ｄ＿ＪＮＤ１の周囲領域には，５つの空ノードＥ＿ＮＤと，７つの０次元ジョブノード０Ｄ＿ＪＮＤと，２つの一次元ジョブノード１Ｄ＿ＪＮＤの一端の辺のノードとが割り当てられている。
【００４２】
また，制御装置５０は，重要ジョブの２次元ジョブノード２Ｄ＿ＪＮＤ１を，別のジョブを割り当てた２次元ジョブノード２Ｄ＿ＪＮＤ２，２ｄ＿ＪＮＤ３とは，一点鎖線６０と２次元ジョブノード２Ｄ＿ＪＮＤ１との間の領域（周囲領域）を介して隣接するように割り当てる。すなわち，制御装置は，重要ジョブの２次元ジョブノード２Ｄ＿ＪＮＤ１と別のジョブを割り当てた２次元ジョブノード２Ｄ＿ＪＮＤ２，２ｄ＿ＪＮＤ３とが直接隣接しないように配置する。
【００４３】
このように，重要ジョブの２次元ジョブノード２Ｄ＿ＪＮＤ１の周囲領域に上記のようなノードを配置することで，２次元ジョブノード２Ｄ＿ＪＮＤ１内に故障が発生した場合に，故障により遮断された通信経路に代わる迂回経路を周囲領域のノードを利用して確立する可能性を高くできる。とりわけ，空ノードＥ＿ＮＤに中継ノードを割り当てることで，メッセージ通信の始点ノードから中継ノードまでの第１の迂回経路と，中継ノードから終点ノードまでの第２の迂回経路を確立できる可能性が高くなる。
【００４４】
ここで，中継ノードは，中継ノードの座標からメッセージの終点座標までの通信経路を検出してメッセージパケットを生成し，そのメッセージパケットのルーティングを開始できる中継機能を有する。この中継ノードを利用することで，ルーティングの制限下でも故障箇所を回避して迂回経路を確立できる可能性を高めることができる。但し，０次元ジョブノードや１次元ジョブノードの一端のノードでも，そのノード内のプロセッサの一部のコアの稼働率がゼロまたは低い場合は，中継ノードに割り当てることができる。中継ノードと迂回経路については後で詳述する。
【００４５】
なお，上記の例では，重要ジョブは２次元ジョブノード２Ｄ＿ＪＮＤ１に割り当てているが，重要ジョブが１次元ジョブノードに割り当てられても良い。その場合でも，重要ジョブの１次元ジョブノードの周囲領域には，空ノードと，０次元ジョブノードと，１次元ジョブノードの１ノード長の辺のノードのいずれかが割り当てられる。この場合，１次元ジョブノードの１ノート長の辺が重要ジョブの１次元ジョブノードに接するように割り当てることが必要である。
【００４６】
図１０は，本実施の形態における制御装置によるジョブ割り当て処理のフローチャート図である。図１１は，ジョブ割り当て処理の途中の状態を示す図である。制御装置５０のプロセッサＣＰＵは，ジョブ割り当てプログラムを実行して，以下のジョブ割り当て処理を行う。
【００４７】
まず，制御装置５０は，ジョブキュー５２−３内に未実行ジョブがあるか否かチェックし（Ｓ１），未実行ジョブがある場合は（Ｓ１のＹＥＳ）次の処理を行う。未実行ジョブが０次元ジョブノードまたは１次元ジョブノードに割り当て可能でない場合（Ｓ２のＮＯ），未実行ジョブが継続実行を必要とする重要ジョブであり，その継続実行すべきジョブを割り当てることができるノードの空き領域があれば（Ｓ５のＹＥＳ），その継続実行すべきジョブを空き領域に割り当ててジョブ実行開始する（Ｓ６）。
【００４８】
図１１は，継続実行すべきジョブを空き領域６０内の２次元ジョブノード２Ｄ＿ＪＮＤ１の領域に割り当てた状態を示す。この例では，空き領域６０は２次元ジョブノード２Ｄ＿ＪＮＤ１の領域よりも左右上下に１ノード分の領域だけ広くなっている。つまり，２次元ジョブノード２Ｄ＿ＪＮＤ１の周囲領域が確保されている。
【００４９】
その後，制御装置５０は，未実行ジョブが０次元ジョブノードまたは１次元ジョブノードに割り当て可能な場合（Ｓ２のＹＥＳ），継続実行すべきジョブが実行中であれば（Ｓ３のＹＥＳ），未実行ジョブを２次元ジョブノード２Ｄ＿ＪＮＤ１の周囲領域内のノードに割り当てて実行開始させる（Ｓ４）。制御装置５０は，この周囲領域内のノードに未実行ジョブを割り当てる処理を，周囲領域内の空ノードＥ＿ＮＥが必要最小限の数に達するまで繰り返す。このように未実行ジョブの割り当てが繰り返され，２次元ジョブノード２Ｄ＿ＪＮＤ１の周囲領域には，空ノードＥ＿ＮＤと，０次元ジョブノード０Ｄ＿ＪＮＤと，１次元ジョブノード１Ｄ＿ＪＮＤの一端のノードのいずれかが割り当てられる。図９に示される通りである。そして，重要ジョブが割り当てられた２次元ジョブノード２Ｄ＿ＪＮＤ１は，他のジョブが割り当てられた２次元ジョブノード２Ｄ＿ＪＮＤ２，３と直接隣接することはなく，かならず上記の周囲領域を介して隣り合うことになる。
【００５０】
［故障処理］
本実施の形態の並列計算機システムでは，重要ジョブの２次元ジョブノード内に発生した故障により通信経路に支障が生じている場合に，制御装置５０が，その周囲領域のノードに中継ノードを割り当て，遮断した通信経路に対する迂回経路を確立する。ルーティングの制約を受けずに新たなパケットでルーティングを再開できる中継ノードを経由することで，故障により遮断した通信経路に対する迂回経路を確立できる可能性が高まる。
【００５１】
図１２は，本実施の形態における第１の迂回経路の例を示す図である。図１２のノード結合網のトポロジとルーティングルール及びノード結合網内のジョブの割り当ては，図９と同じである。図１２に示されるように，継続実行すべき重要ジョブが割り当てられた２次元ジョブノード２Ｄ＿ＪＮＤ１内の中央リンクに故障Ｆ６が発生した場合を想定する。この結果，２次元メッシュでWest-First-Turnのルーティングでは，ノードＮＤ６からノードＮＤ５への通信経路に対する迂回経路を２次元ジョブノード２Ｄ＿ＪＮ１内に確立することができない。図３の例と同様に，ノードＮＤ６からノードＮＤ５への経路には西方向の経路が必要だが，ノードＮＤ６から最初に西方向の経路を通過することは故障Ｆ６により不可能だからである。
【００５２】
そこで，制御装置５０は，故障処理において，２次元ジョブノード２Ｄ＿ＪＮＤ１の周囲領域内のノードに，望ましくは空ノードに中継ノードＲ＿ＮＤ（Relay Node）を割り当てる。そして，制御装置５０は，始点ノードＮＤ６から中継ノードＲ＿ＮＤまでの第１の迂回経路ＡＲ１１（Alternative Rout）と，中継ノードＲ＿ＮＤから終点ノードＮＤ５までの第２の迂回経路ＡＲ１２とからなる迂回経路を確立する。制御装置は，選択した中継ノードＲ＿ＮＤに中継プログラムをインストールし起動するので，中継ノードＲ＿ＮＤは，受信したパケットをバッファに格納し，新たなパケットして再度ルーティングを開始できる。その結果，中継ノードＲ＿ＮＤは，第２の迂回経路Ｒ１２で最初に西方向に進むルーティングを行うことができる。
【００５３】
また，第１の迂回経路ＡＲ１１は，始点ノードＮＤ６から中継ノードＲ＿ＮＤに至るまで，周囲領域内に割り当てられた１次元ジョブノード１Ｄ＿ＪＮＤの１ノードの辺の長さの辺（左端の辺）のノードと，０次元ジョブノード０Ｄ＿ＮＤを経由する。しかし，１次元ジョブノード１Ｄ＿ＪＮＤの左端のノードであり２次元ジョブノード２Ｄ＿ＪＮＤ１に接するノードは，１次元ジョブノード内のメッセージを右隣のノードとしか送受信しない。そのため，１次元ジョブノード１Ｄ＿ＪＮＤの左端のノードのルータは，右隣のノード方向以外のルーティングには余裕がある。したがって，第１の迂回経路ＡＲ１１内のメッセージが経由する経由ノードになっても，そのノードのルータが迂回経路ＡＲ１１のルーティング処理を行うことに支障はない。さらに，０次元ジョブノード０Ｄ＿ＪＮＤはメッセージの送信を行っていないので，ルータはルーティング処理に余裕がある。したがって，０次元ジョブノード０Ｄ＿ＪＮＤは第１の迂回経路ＡＲ１１内の経由ノードになってもそのルーティング処理を行う余裕を持っていて支障はない。
【００５４】
同様に，第２の迂回経路ＡＲ１２は，中継ノードＲ＿ＮＤから終点ノードＮＤ５に至るまで，周囲領域に割り当てられた２つの０次元ジョブノード０Ｄ＿ＪＮＤを経由する。この経由ノードも上記と同様の理由で，第２の迂回経路ＡＲ１２のルーティング処理を行う余裕がある。第２の迂回経路ＡＲ１２は，図１２と異なり，２次元ジョブノード２Ｄ＿ＪＮＤ１内のノードを経由しないで周囲領域のノードのみを経由して終点ノードＮＤ５に達するようにしてもよい。
【００５５】
図１３は，本実施の形態における第２の迂回経路の例を示す図である。図１３に示されるように，２次元ジョブノード２Ｄ＿ＪＮＤ１内の中央リンクに故障Ｆ６が発生した場合を想定する。この場合は，ノードＮＤ５からノードＮＤ６への通信経路に対する迂回経路を２次元ジョブノード２Ｄ＿ＪＮ１内に確立することは理論的には可能である。しかし，２次元ジョブノード２Ｄ＿ＪＮＤ１内にはメッセージのパケットが頻繁に伝搬しているので，新たに迂回経路を設定することはデッドロックが発生するなど望ましくない場合がある。
【００５６】
そこで，図１３の例では，制御装置５０が周囲領域内の空ノードを中継ノードＲ＿ＮＤに割り当てて，始点ノードＮＤ５から中継ノードＲ＿ＮＤに至る第１の迂回経路ＡＲ２１と，中継ノードＲ＿ＮＤから終点ノードＮＤ６に至る第２の迂回経路ＡＲ２２とを確立する。
【００５７】
図１４は，本実施の形態における第３の迂回経路の例を示す図である。図１４の例では，制御装置５０が周囲領域内の空ノードを中継ノードＲ＿ＮＤに割り当てて，始点ノードＮＤ５から中継ノードＲ＿ＮＤに至る第１の迂回経路ＡＲ３１と，中継ノードＲ＿ＮＤから終点ノードＮＤ６に至る第２の迂回経路ＡＲ３２とを確立する。
【００５８】
始点ノードＮＤ５から終点ノードＮＤ６に至る通信経路に対する迂回経路は，上記以外にもいくつかの経路が考えられる。周囲領域内に中継ノードを設定することで，始点座標から終点座標までのルーティングを複数に分割して行うことができるので，迂回経路を確立できる可能性が高くなる。
【００５９】
本実施の形態における迂回経路の設定によれば，迂回経路は，重要ジョブが割り当てられた２次元ジョブノード２Ｄ＿ＪＮＤ１の周囲領域を主に経由するので，２次元ジョブノード内のルータに余分の負担を強いることが少なくなり，故障箇所の影響を受けない迂回の必要がないパケットのルーティングに支障を来すことは少ない。
【００６０】
中継ノードＲ＿ＮＤは，空ノードＥ＿ＮＤに割り当てることが望ましい。しかし，０次元ジョブノードや１次元ジョブノードの１ノード辺長の辺のノードのプロセッサに空きコアがあれば，それらのノードに中継ノードを割り当てることもできる。
【００６１】
中継ノードＲ＿ＮＤは空ノードＥ＿ＮＤに割り当てることが望ましいので，周囲領域内の空ノードの数が必要最小限の数より多くなるようにジョブ割り当てを行うのが望ましい。したがって，制御装置５０は，例えば，重要ジョブの２次元ジョブノード２Ｄ＿ＪＮＤの故障箇所数に対して一定の割合の数の空ノードを割り当てるようにしても良い。この割合は，予めシミュレーションなどで目安となる基準値を見出すことができる。
【００６２】
図１５は，本実施の形態における故障処理のフローチャート図である。制御装置５０のプロセッサＣＰＵは，故障処理プログラム５２−２を実行して以下の故障処理を行う。制御装置５０は，各ノードに設けられている故障検知装置４３から故障検知通知を受信すると，その故障箇所と故障の内容を故障箇所記憶テーブル５２−５に登録する（Ｓ１０）。制御装置５０は，ジョブ実行ノード記憶テーブル５２−４を参照して，故障発生箇所で実行中のジョブがあるか否かチェックし（Ｓ１１），故障発生箇所で実行中のジョブがあり（Ｓ１１のＹＥＳ），そのジョブが継続実行が必要など重要ジョブの場合は（Ｓ１２のＹＥＳ），故障種別に応じて（Ｓ１４）それぞれ対応する故障処理を実行する。
【００６３】
故障箇所がノード内のプロセッサ４０や主記憶装置４１（プロセッサエレメントＰＥ）の場合は，制御装置５０は，そのプロセッサによるジョブの実行が中断したことを他のプロセスに通知する（Ｓ１５）。この場合は，ＵＬＦＭ（User-Level Failure Mitigation：ユーザレベル故障緩和）により，ユーザが故障に対応する。
【００６４】
故障箇所がノード内のルータの故障の場合は，制御装置５０は，故障箇所のプロセッサ上のプロセスを別のノードに移動させる（Ｓ１６）。この別のノードへの移動は，例えば，制御装置５０内のノード結合網とは別のネットワーク５１を経由して行うことが望ましい。また，故障箇所がリンクの故障の場合に，リンクの故障によりノードが孤立した場合は（Ｓ１７のＹＥＳ），そのノードによるプロセスの継続は不可能になるので，制御装置５０は，孤立したノードのプロセッサ上のプロセスを別のノードに移動させる（Ｓ１６）。
【００６５】
故障箇所がルータ故障またはリンク故障の場合は，ノード間のメッセージの送信経路に支障が生じる場合があるので，制御装置５０は，故障が発生した２次元ジョブノードの周囲領域内に中継ノードを設定し，中継ノードを用いて迂回経路を決定し，通信経路を回復させる（Ｓ１８）。そして，制御装置５０は，故障箇所を通過していたメッセージ通信が失敗したことを全プロセスに通知する（Ｓ１９）。これにより，故障箇所の情報も全プロセスに，つまりジョブ実行中のノードに通知される。
【００６６】
図１６は，図１５の通信経路の回復の処理Ｓ１８のフローチャート図である。制御装置５０は，故障処理において故障により遮断された通信経路に対する迂回経路を確立して通信経路を回復する。その場合，制御装置５０は，まず，重要ジョブの２次元ジョブノード内のノードから中継ノードとして適切なノードを探索し（Ｓ２１−Ｓ２７），適当なノードが見つからない場合は，２次元ジョブノードの周囲領域内のノードから中継ノードとして適切なノードを探索する（Ｓ２８）。
【００６７】
制御装置５０は，カウンタｉが上限値に達するまで（Ｓ２１，Ｓ２７），迂回経路の候補ノードを故障箇所の近傍から抽出し（Ｓ２２），候補のノードのリンク利用率が低い場合で（Ｓ２３のＹＥＳ），候補ノードのＣＰＵに空きコアがある場合は（Ｓ２４のＹＥＳ），その候補ノードを中継ノードに割り当てて，中継プログラムをインストールして起動する（Ｓ２５）。上限値を適切に設定することで，上記の処理により故障が発生した２次元ジョブノードの領域内のノードで中継ノードとして適切なノードを検出する。
【００６８】
制御装置５０は，故障が発生した２次元ジョブノードの領域内のノードに中継ノードとして適しているノードが見つからない場合は（Ｓ２７のＹＥＳ），２次元ジョブノードの周囲領域内のノードから中継ノードとして適切なノードを探索する（Ｓ２８）。この探索処理は，図１７で説明する。
【００６９】
制御装置５０は，いずれかのノードに中継ノードを割り当てると，選択された中継ノードの座標を，通信経路を遮断されたノードなど通知が必要なノードに通知する（Ｓ２９）。これにより，通知を受けたノードは，新たに設定された中継ノードを経由する迂回経路を利用してメッセージの送信を再開する。
【００７０】
図１７は，図１６の処理Ｓ２８の周囲領域内での中継ノードの選択処理のフローチャート図である。制御装置５０は，周囲領域内のノードを，空ノード，０次元ジョブノード，１次元ジョブノードの順にソートする（Ｓ３１）。制御装置５０は，ソートされた最初のノード（または２回目は次のノード）を中継ノード候補に選択し（Ｓ３２），迂回経路の中継経路として成立するか否かをチェックする（Ｓ３３）。この成立性のチェックは，例えば，予想される故障箇所に対して迂回経路を確立することができるか否かのチェックであり，成立する確率が一定値以上であれば，成立すると判定される。中継ノード候補で迂回経路の中継経路として成立する場合は（Ｓ３３のＹＥＳ），制御装置５０は，迂回経路の実効長を算出する（Ｓ３４）。迂回経路の実効長は，重要ジョブの２次元ジョブノード内の通過長さＬ１と，周囲領域の通過長さＬ２に対して，実効長は次の式により求めることができる。
迂回経路の実効長＝a*L1+b*L2
ここで，ａ，ｂは重み値でありａ＞ｂである。
【００７１】
つまり，迂回経路の実効長は，２次元ジョブノード内のノードを通過すると実効長はより長くなり，周囲領域を通過すると実効長はより短くなる。したがって，迂回経路が，できるだけ少ない通過ノード数を有し，できるだけ周囲領域を通過すれノードを含めば，実効長を短くできる。
【００７２】
制御装置５０は，上記の中継ノード候補への選択Ｓ３２と，中継経路としての成立性の判断Ｓ３３と，実効長の計算Ｓ３４とを，全ての候補に対して行い，最小実効長の候補を中継ノードに選択する。実効長が同じ場合は，空ノードが優先して中継ノードに選択される。
【００７３】
迂回経路の実効長の計算式において，候補ノードが空ノードであれば重み値ｂをより小さくし，０次元ジョブノード，１次元ジョブノードであれば順位重み値ｂを大きくするように設定してもよい。そのようにすることで，空ノードが中継ノードに選択されやすくすることができる。
【００７４】
［中継ノードを経由する迂回経路のルーティング］
図１８は，中継ノードの構成を示す図である。中継ノードは，図５で示した通常のノードと同様に，プロセッサ４０と，主記憶装置４１と，ルータ４２と，故障検知装置４３とを有する。主記憶装置４１内には，中継プログラム４１−１と，受信したパケットを一時的に格納する通信バッファ４１−２と，故障箇所情報４１−３とが格納される。但し，中継ノード情報４１−４は中継ノードのメモリには格納されない。
【００７５】
一方，通常のノードでは，主記憶装置４１内に，中継プログラムの代わりに通信プログラムが格納され，故障箇所情報４１−３に加えて中継ノード情報４１−４も格納される。
【００７６】
中継ノードＲ＿ＮＤのプロセッサ４０は，中継プログラム４１−１を実行して，始点ノードが送出したパケットを終点ノードとして受信し，通信バッファ４１−２内に格納する。受信したパケットのヘッダには，始点座標として始点ノードの座標が，終点座標として中継ノードの座標が格納されている。さらに，中継ノードのプロセッサ４０は，中継プログラムを実行して，受信パケットのヘッダ内の始点座標を中継ノードの座標に，終点座標を終点ノードの座標に変更し，再度パケットをルーティングする。後述するとおり，パケットのデータ領域には，始点座標，中継座標，終点座標の情報が含まれている。
【００７７】
図１９は，中継ノードを経由する迂回経路のルーティングを説明する図である。図１９中，破線矢印のように中継ノードを経由しないパケットは，ヘッダに始点座標と終点座標が格納されデータ領域にメッセージが格納される。そして，パケットが経由するノードのルータは，始点座標と伝搬してきたリンクと終点座標とに基づいて，ルーティングルールに基づき，パケットを次のノードに宛ててルーティングする。したがって，経由ノードのルータは，ハードウエアがパケットのヘッダ情報に基づいてルーティングの方向を判断することができる。
【００７８】
一方，図１９の迂回経路ＡＲ３１，ＡＲ３２は，図１４の例と同じである。この迂回経路は始点ノードＮＤ５から中継ノードＲ＿ＮＤまでの第１の迂回経路ＡＲ３１と，中継ノードＲ＿ＮＤから終点ノードＮＤ６までの第２の迂回経路ＡＲ３２とを有する。始点ノードＮＤ５のプロセッサは，中継ノードＲ＿ＮＤを経由して終点ノードＮＤ６に至る迂回経路を探索する。そして，始点ノードＮＤ５のプロセッサは，パケットのヘッダ領域に始点座標として始点ノードＮＤ５の座標を，終点座標として中継ノードＲ＿ＮＤの座標を格納し，パケットのデータ領域に始点座標と中継座標と終点座標の情報を格納して，パケットを送出する。送出されたパケットは，第１の迂回経路ＡＲ３１の途中の経由ノードのルータにより，ヘッダ内の始点座標と終点座標に基づく通常のハードウエアによるルーティング処理を行われ，中継ノードＲ＿ＮＤに届けられる。
【００７９】
中継ノードＲ＿ＮＤのプロセッサは，中継プログラムを実行し，受信したパケットを通信バッファ内に一時的に格納する。プロセッサは，中継プログラムを実行し，一時的に格納したパケットのデータ領域内の始点座標，中継座標及び終点座標を参照し，バッファリングしたパケットのヘッダ内の始点座標に中継ノードの座標を，終点座標に終点ノードの座標を書き込んで，そのヘッダ情報を変更したパケットを，第２の迂回経路に送出する。これにより，第２の迂回経路ＡＲ３２の途中の経由ノードのルータにより，ヘッダ内の始点座標と終点座標に基づくルーティング処理が行われ，パケットは終点ノードＮＤ６に届けられる。
【００８０】
上記のように，中継ノードＲ＿ＮＤは，中継プログラムをインストールされ起動されているので，ルータによる通常のルーティングではなく，始点ノードと同様に送信するパケットを生成して，生成したパケットを新たにルーティングする。したがって，ルーティングの制限下においても，中継ノードを経由することで，故障箇所を迂回する迂回経路を利用して故障により遮断された通信経路を回復することができる。
【００８１】
［３次元ジョブノードの周囲領域に配置するノードの例］
図２０は，３次元ジョブノードの周囲領域に配置するノードの例を示す図である。本実施の形態の制御装置は，ジョブ配置処理で，重要ジョブの３次元ジョブノード３Ｄ＿ＪＮＤのＹＺ平面に接する周囲領域には，空ノードＥ＿ＮＤや０次元ジョブノード０Ｄ＿ＪＮＤを配置する。更に，１次元ジョブノード１Ｄ＿ＪＮＤの長辺や，２次元ジョブノード２Ｄ＿ＪＮＤの長辺が，重要ジョブの３次元ジョブノード３Ｄ＿ＪＮＤのＹＺ面に接するように配置してもよい。
【００８２】
その理由は以下のとおりである。迂回経路ＡＲとして，３次元ジョブノード３Ｄ＿ＪＮＤ内部のノードからＹＺ面の周囲領域に配置された空ノードＥ＿ＮＤを中継ノードＲ＿ＮＤとし，その中継ノードから内部のノードに至る経路について考える。この迂回経路ＡＲは，中継ノードに設定された元空ノードＥ＿ＮＤからＺ軸方向に進み，途中でＹ軸方向に進みながら１次元ジョブノード１Ｄ＿ＪＮＤ２と２次元ジョブノード２Ｄ＿ＪＮＤ内のノードを経由し，次にＸ軸方向に進んで３次元ジョブノード２Ｄ＿ＪＮＤ内のノードに至る。
【００８３】
この場合，迂回経路ＡＲは１次元ジョブノード１Ｄ＿ＪＮＤ２内のノードをＹ軸方向に横切るのに対して，１次元ジョブノード１Ｄ＿ＪＮＤ２内のノードのルータは主にＺ軸方向のメッセージをルーティングする。したがって，１次元ジョブノード１Ｄ＿ＪＮＤ２内のノードのルータはＹ軸方向のルーティングについては余裕があるので，迂回経路ＡＲがＹ軸方向に横切り迂回経路上のメッセージが通過しても１次元ジョブノード１Ｄ＿ＪＮＤ２内のメッセージのルーティングに影響を与えることは少ない。
【００８４】
同様に，２次元ジョブノード２Ｄ＿ＪＮＤ内のノードは，内部のメッセージのルーティングはＺＸ面内に限定されている。したがって，迂回経路ＡＲがＹ軸方向に横切り迂回経路のメッセージが２次元ジョブノード２Ｄ＿ＪＮＤをＹ軸方向に通過しても内部のメッセージのルーティングに影響を与えることは少ない。
【００８５】
このように，３次元ジョブノード３Ｄ＿ＪＮＤのＹＺ面の周囲領域に配置される２次元ジョブノード２Ｄ＿ＪＮＤまたは１次元ジョブノード１Ｄ＿ＪＮＤは，１ノード長の辺または面のノードであれば良く，その１ノード長の辺または面の１ノード長方向に迂回経路を設けることができる。
【００８６】
以上説明したとおり，本実施の形態の並列計算機システムによれば，継続実行が要求されるなどの重要ジョブを実行するＮ次元ジョブノードの周囲領域に，ジョブが割り当てられていない空ノードと，ジョブが割り当てられている０次元ジョブノードと，ジョブが割り当てられているＭ（Ｍ＝＜Ｎ）次元ジョブノードの１ノード長の辺または面のノードのいずれかを割り当てるので，故障で遮断された通信経路を，周囲領域内の少なくとも一つのノードを中継ノードとして経由する迂回経路により復旧することができる。これにより，メッセージの通信不通によりジョブを中止して新たな領域にジョブを割り当ててジョブを再開することをできるだけ回避することができる。
【００８７】
以上の実施の形態をまとめると，次の付記のとおりである。
【００８８】
（付記１）
計算をそれぞれ実行するとともに通信経路を介して接続される複数のノードを備える並列計算機と，
前記並列計算機内の所定数のノードにジョブを割り当てる制御装置とを有し，
前記制御装置は，
第１のジョブを割り当てた複数のノードを有する第１のＮ（Ｎは１以上）次元ジョブノードの周囲領域に，ジョブが割り当てられていない空ノードと，ジョブが割り当てられている０次元ジョブノードと，ジョブが割り当てられているＭ（Ｍ＝＜Ｎ）次元ジョブノードの１ノード長の辺または面のノードのいずれかを割り当てるジョブ割り当て処理部と，
前記第１のＮ次元ジョブノード内に故障が発生した場合，前記周囲領域内のノードの少なくとも１つのノードを中継ノードに割り当てるとともに，前記中継ノードを経由する経路を，前記故障により通信に支障が生じた通信経路に対する迂回経路として選択し，前記迂回経路を介して前記ノード間の通信を実行させる故障処理部とを有する並列計算機システム。
【００８９】
（付記２）
前記ジョブ割り当て処理部は，前記第１のＮ次元ジョブノードを，第２のジョブを実行中の複数のノードを有する第２のＮ次元ジョブノードと，前記周囲領域を介して隣接するように割り当てる
付記１に記載の並列計算機システム。
【００９０】
（付記３）
前記通信経路は，ルーティングルールに従う始点ノードから経由ノードを経由し終点ノードに至る経路であり，
前記迂回経路は，前記始点ノードから経由ノードを経由し前記中継ノードに至る第１の迂回経路と，前記中継ノードから経由ノードを経由し前記終点ノードに至る第２の迂回経路とを有し，
前記始点ノードが送出したパケットは，前記ルーティングルールに従って前記第１の迂回経路を伝搬して前記中継ノードに到達し，
前記中継ノードが送出したパケットは，前記ルーティングルールに従って前記第２の迂回経路を伝搬して前記終点ノードに到達する
付記１または２に記載の並列計算機システム。
【００９１】
（付記４）
前記中継ノードは，受信したパケットをバッファリングし，前記パケットの始点座標と終点座標を書き換え，前記書き換えたパケットを前記第２の迂回経路に応じて送出し，
前記経由ノードは，前記パケットの始点座標と終点座標に基づいて，伝搬してきた前記パケットをルーティングする
付記３に記載の並列計算機システム。
【００９２】
（付記５）
前記Ｍ次元ジョブノード内のノード間のパケットのルーティング方向と，前記迂回経路を伝搬するパケットが前記Ｍ次元ジョブノードの１ノード長の辺のノードでのルーティング方向とが異なる
付記３に記載の並列計算機システム。
【００９３】
（付記６）
前記制御装置の故障処理部は，前記中継ノードを，前記周囲領域内の前記空きノードから選択する，
付記１に記載の並列計算機システム。
【００９４】
（付記７）
前記制御装置の故障処理部は，前記中継ノードを，前記周囲領域内の前記空きノードと，前記０次元ジョブノードと，前記Ｍ次元ジョブノードの１ノード長の辺のノードから，前記中継ノードを通る迂回経路の実効長が最小になるノードを選択する，
付記１に記載の並列計算機システム。
【００９５】
（付記８）
前記制御部のジョブ割り当て処理部は，前記周囲領域内の前記空きノードの数が最小値以上になるように，前記周囲領域内に前記０次元ジョブノードと，前記Ｍ次元ジョブノードの１ノード長の辺のノードのいずれかを割り当てる，
付記１に記載の並列計算機システム。
【００９６】
（付記９）
計算をそれぞれ実行するとともに通信経路を介して接続される複数のノードを備える並列計算機と，前記並列計算機内の所定数のノードにジョブを割り当てる制御装置とを有する並列計算機システムの制御方法において，
前記制御装置が、
第１のジョブを割り当てた複数のノードを有する第１のＮ（Ｎは１以上）次元ジョブノードの周囲領域に，ジョブが割り当てられていない空ノードと，ジョブが割り当てられている０次元ジョブノードと，ジョブが割り当てられているＭ（Ｍ＝＜Ｎ）次元ジョブノードの１ノード長の辺または面のノードのいずれかを割り当て，
前記第１のＮ次元ジョブノード内に故障が発生した場合，前記周囲領域内のノードの少なくとも１つのノードを中継ノードに割り当てるとともに，前記中継ノードを経由する経路を，前記故障により通信に支障が生じた通信経路に対する迂回経路として選択し，前記迂回経路を介して前記ノード間の通信を実行させる並列計算機システムの制御方法。
【符号の説明】
【００９７】
並列計算機システム
３０：並列計算機
３２：ノード結合網
３３：入出力装置
ＮＤ：ノード
ＬＮ：リンク
４０：プロセッサ，CPU
４１：メインメモリ
４２：ルータ
５０：制御装置
５０−１：ジョブ割り当てプログラム
５０−２：故障処理プログラム
５０−３：ジョブキュー
５０−４：ジョブ実行ノード記憶テーブル
５０−５：故障箇所記憶テーブル
Ｅ＿ＮＤ：空ノード
０Ｄ＿ＪＮＤ：０次元ジョブノード
１Ｄ＿ＪＮＤ：１次元ジョブノード
２Ｄ＿ＪＮＤ：２次元ジョブノード
Ｒ＿ＮＤ：中継ノード
４０−１：中継プログラム，中継デーモンプログラム
４１−２：通信バッファ
【図１】
2016038649.tif 000003
【図２】
2016038649.tif 000004
【図３】
2016038649.tif 000005
【図４】
2016038649.tif 000006
【図５】
2016038649.tif 000007
【図６】
2016038649.tif 000008
【図７】
2016038649.tif 000009
【図８】
2016038649.tif 000010
【図９】
2016038649.tif 000011
【図１０】
2016038649.tif 000012
【図１１】
2016038649.tif 000013
【図１２】
2016038649.tif 000014
【図１３】
2016038649.tif 000015
【図１４】
2016038649.tif 000016
【図１５】
2016038649.tif 000017
【図１６】
2016038649.tif 000018
【図１７】
2016038649.tif 000019
【図１８】
2016038649.tif 000020
【図１９】
2016038649.tif 000021
【図２０】
2016038649.tif 000022