(57)【要約】【課題】ジョブ実行時のノード選択を高速化すること。【解決手段】記憶部１１は、複数のノードの接続関係を表すｎ（ｎは２以上の整数）次元の空間のうち、所定軸以外の他軸方向のサイズが２以上の所定の整数の冪である領域ごとに、当該領域に対応するノード群の空きノード情報４を記憶する。処理部１２は、ジョブの実行開始時および実行終了時に、空きノード情報４を生成し、空きノード情報４を記憶部１１に格納する。処理部１２は、各軸の指定サイズを含むジョブの実行要求を受け付けると、指定サイズに応じた空きノード情報４を選択し、選択した空きノード情報４に基づいて、要求されたジョブの割り当て先のノードを抽出する。【選択図】図１
2018092328.tif 000002
【特許請求の範囲】
【請求項１】
複数のノードがメッシュ結合またはトーラス結合で接続された並列処理システムで、前記複数のノードへのジョブの割り当てに用いられるジョブ割り当てプログラムであって、
前記ジョブの実行開始時および実行終了時に、前記複数のノードの接続関係を表すｎ（ｎは２以上の整数）次元の空間のうち、所定軸以外の他軸方向のサイズが２以上の所定の整数の冪である領域ごとに、前記領域に対応するノード群の空きノード情報を生成し、
各軸の指定サイズを含む前記ジョブの実行要求を受け付けると、前記指定サイズに応じた前記空きノード情報を選択し、選択した前記空きノード情報に基づいて、要求された前記ジョブの割り当て先のノードを抽出する、
処理をコンピュータに実行させることを特徴とするジョブ割り当てプログラム。
【請求項２】
前記空きノード情報は、前記所定軸の座標値に対応するビットを複数含むビット列であり、
前記空きノード情報の生成では、前記領域のうち前記所定軸の第１の座標値に対応する部分に属する全ノードに前記ジョブを割り当て可能な場合に、前記第１の座標値に対応する第１のビットを第１の値に設定し、前記部分に属する少なくとも１つのノードに前記ジョブを割り当て不可能な場合に、前記第１のビットを第２の値に設定する、
ことを特徴とする請求項１記載のジョブ割り当てプログラム。
【請求項３】
前記割り当て先のノードの抽出では、前記ビット列のうち、前記所定軸に対する前記指定サイズの数分、前記第１の値が連続するビット列部分があるか否かを判定し、前記ビット列部分がある場合、前記領域に対応する前記ノード群のうち、前記ビット列部分の前記座標値に対応するノードを、前記ジョブの前記割り当て先のノードと決定する、
ことを特徴とする請求項２記載のジョブ割り当てプログラム。
【請求項４】
前記空きノード情報の選択では、前記他軸方向のサイズが前記他軸方向の前記指定サイズよりも小さい前記領域に対応する第１の空きノード情報を複数選択し、
前記割り当て先のノードの抽出では、複数の前記第１の空きノード情報を組み合わせることで、前記他軸方向のサイズが前記指定サイズである前記領域に対応する第２の空きノード情報を生成し、前記第２の空きノード情報に基づいて、前記ジョブの前記割り当て先のノードを抽出する、
ことを特徴とする請求項１乃至３の何れか１項に記載のジョブ割り当てプログラム。
【請求項５】
前記割り当て先のノードの抽出では、複数の前記第１の空きノード情報のうちの一部の前記第１の空きノード情報を用いて、前記第２の空きノード情報に対応する前記領域に前記ジョブを割り当て可能であるか否かを判定し、割り当て可能でない場合、前記第２の空きノード情報の生成を省略する、
ことを特徴とする請求項４記載のジョブ割り当てプログラム。
【請求項６】
メッシュ結合またはトーラス結合で接続された複数のノードと、
前記複数のノードの接続関係を表すｎ（ｎは２以上の整数）次元の空間のうち、所定軸以外の他軸方向のサイズが２以上の所定の整数の冪である領域ごとに、前記領域に対応するノード群の空きノード情報を記憶する記憶部と、
ジョブの実行開始時および実行終了時に、前記空きノード情報を生成し、前記空きノード情報を前記記憶部に格納し、各軸の指定サイズを含む前記ジョブの実行要求を受け付けると、前記指定サイズに応じた前記空きノード情報を選択し、選択した前記空きノード情報に基づいて、要求された前記ジョブの割り当て先のノードを抽出する処理部と、
を有することを特徴とする並列処理装置。
【請求項７】
複数のノードがメッシュ結合またはトーラス結合で接続された並列処理システムで、前記複数のノードにジョブを割り当てるジョブ割り当て方法であって、コンピュータが、
前記ジョブの実行開始時および実行終了時に、前記複数のノードの接続関係を表すｎ（ｎは２以上の整数）次元の空間のうち、所定軸以外の他軸方向のサイズが２以上の所定の整数の冪である領域ごとに、前記領域に対応するノード群の空きノード情報を生成し、
各軸の指定サイズを含む前記ジョブの実行要求を受け付けると、前記指定サイズに応じた前記空きノード情報を選択し、選択した前記空きノード情報に基づいて、要求された前記ジョブの割り当て先のノードを抽出する、
ことを特徴とするジョブ割り当て方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はジョブ割り当てプログラム、並列処理装置およびジョブ割り当て方法に関する。
【背景技術】
【０００２】
現在、大規模な計算を行う並列処理装置が利用されている。例えば、並列処理装置では、計算を実行するノードを相互に複数接続して、複数のノードにより並列に計算を行い得る。並列処理装置のノード間のインタコネクトのトポロジの１つに格子状のネットワークが挙げられる。格子状のネットワークでは、あるノード対で通信してジョブを実行しつつ、別のノード対で通信して別のジョブを並列に実行できる。このとき、両方の通信が同じノード間リンクを使用すると演算性能が低下し得る。このため、実行中のジョブが別のジョブの実行に影響を及ぼすこともある。
【０００３】
そこで、全体の格子の一部のサブ格子を１つのジョブに専有させる提案がある。この提案では、ジョブ管理装置が、各ノードを１ビットに対応させたビット列を用意し、ビットの値を該当ノードに対するジョブの割り当て済／未割り当てに対応させることで、ノードへのジョブの割り当て状態を管理する。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】国際公開第２０１２／０２０４７４号
【特許文献２】特開２０１５−４１３０２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
並列処理装置では、ジョブを割り当てるノードの選択に伴う遅延が問題になる。当該遅延は、投入されたジョブが実行されるまでの待ち時間の増大や、並列計算機におけるノード全体の稼働率の低下の要因になる。
【０００６】
１つの側面では、本発明は、ジョブ実行時のノード選択の高速化を目的とする。
【課題を解決するための手段】
【０００７】
１つの態様では、複数のノードがメッシュ結合またはトーラス結合で接続された並列処理システムで、複数のノードへのジョブの割り当てに用いられるジョブ割り当てプログラムが提供される。ジョブ割り当てプログラムは、ジョブの実行開始時および実行終了時に、複数のノードの接続関係を表すｎ（ｎは２以上の整数）次元の空間のうち、所定軸以外の他軸方向のサイズが２以上の所定の整数の冪である領域ごとに、領域に対応するノード群の空きノード情報を生成し、各軸の指定サイズを含むジョブの実行要求を受け付けると、指定サイズに応じた空きノード情報を選択し、選択した空きノード情報に基づいて、要求されたジョブの割り当て先のノードを抽出する、処理をコンピュータに実行させる。
【発明の効果】
【０００８】
１つの側面では、ジョブ実行時のノード選択を高速化できる。
【図面の簡単な説明】
【０００９】
【図１】第１の実施の形態の並列処理装置を示す図である。
【図２】第２の実施の形態の並列処理システムの例を示す図である。
【図３】制御ノードのハードウェア例を示す図である。
【図４】計算ノードのハードウェア例を示す図である。
【図５】３次元メッシュネットワークで接続された計算ノードの例を示す図である。
【図６】トーラスネットワークで接続された計算ノードの例を示す図である。
【図７】制御ノードの機能例を示す図である。
【図８】計算ノードの空き状況を表すテーブルの例を示す図である。
【図９】空きノード情報生成の例を示すフローチャートである。
【図１０】ジョブ割り当ての例を示すフローチャートである。
【図１１】空きノードの探索例を示す図である。
【図１２】ビット列判定の例を示すフローチャートである。
【図１３】ビット列判定の具体例を示す図である。
【図１４】計算ノード数に対する所要ステップ数の例を示す図である。
【図１５】制御ノードの機能の比較例を示す図である。
【図１６】ジョブ割り当ての比較例（その１）を示すフローチャートである。
【図１７】比較例（その１）の割り当て判定を示すフローチャートである。
【図１８】比較例（その１）の基点座標更新判定を示すフローチャートである。
【図１９】ジョブ割り当ての比較例（その２）を示すフローチャートである。
【図２０】比較例（その２）の割り当て判定を示すフローチャートである。
【図２１】検索用マスクを用いた割り当て判定の例を示す図である。
【図２２】比較例（その２）の基点座標更新判定を示すフローチャートである。
【図２３】計算ノード数に対する所要ステップ数の比較例を示す図である。
【発明を実施するための形態】
【００１０】
以下、本実施の形態について図面を参照して説明する。
［第１の実施の形態］
図１は、第１の実施の形態の並列処理装置を示す図である。並列処理装置１は、制御ノード１０および計算ノード群２０を有する。制御ノード１０は、並列処理装置１の所定のネットワークを介して計算ノード群２０の各計算ノードと接続されている。制御ノード１０は、ジョブの入力を受け付ける。制御ノード１０は、計算ノード群２０に属する複数の計算ノードのうち、当該ジョブを割り当てる計算ノードを選択する。制御ノード１０は、選択された計算ノードに当該ジョブを実行させる。ジョブの実行に用いる計算ノードのサイズ（割り当てる計算ノードの数や形状）は、例えば、ジョブの受け付け時にユーザにより指定される。
【００１１】
計算ノード群２０は、計算ノード２１，２２，２３，２４，・・・を含む。計算ノード２１，２２，２３，２４，・・・は、それぞれがメモリおよびプロセッサを有する。計算ノード２１，２２，２３，２４，・・・は、制御ノード１０により割り当てられたジョブを実行する。計算ノード２１，２２，２３，２４，・・・は、相互に接続されてネットワーク２を形成する。計算ノード２１，２２，２３，２４，・・・は、ネットワーク２を介して相互に通信することで、ジョブを並列に実行する。
【００１２】
ネットワーク２は、ｎ（ｎは２以上の整数）次元の格子状のネットワークである。具体的には、ネットワーク２は、メッシュ結合またはトーラス結合と呼ばれる接続形態のネットワークである。図１におけるネットワーク２は、３次元（ｎ＝３）のメッシュ結合の接続形態を例示する。１つの格子点は１つの計算ノードに対応する。１つの格子点は空間における座標（０以上の整数の組）により表される。制御ノード１０は、全体の格子の一部分であるサブ格子（格子点のサブセット）を、ジョブに割り当てる。１つのジョブはサブ格子に属する計算ノードを専有する。制御ノード１０は、ある計算ノードに対してあるジョブを割り当て済のとき、他のジョブの割り当て先候補から当該計算ノードを除外する。
【００１３】
制御ノード１０は、１つの計算ノードを１つのビットに対応付け、ビットの値により、該当の計算ノードの空き状況（ジョブが割り当てられているか否か）を管理する。例えば、ビット値“１”はジョブ割り当て不可能（ジョブを割り当て済、または、故障中など）を示す。また、ビット値“０”はジョブ割り当て可能（ジョブを未割り当てである）を示す。制御ノード１０は、このような情報により表される計算ノードの空き状況に対して、ジョブを割り当てる計算ノードの選択を高速化する機能を提供する。
【００１４】
制御ノード１０は、記憶部１１および処理部１２を有する。記憶部１１は、ＲＡＭ（Random Access Memory）などの揮発性記憶装置でもよいし、ＨＤＤ（Hard Disk Drive）やフラッシュメモリなどの不揮発性記憶装置でもよい。処理部１２は、ＣＰＵ（Central Processing Unit）、ＤＳＰ（Digital Signal Processor）、ＡＳＩＣ（Application Specific Integrated Circuit）、ＦＰＧＡ（Field Programmable Gate Array）などを含み得る。処理部１２はプログラムを実行するプロセッサでもよい。「プロセッサ」は、複数のプロセッサの集合（マルチプロセッサ）も含み得る。
【００１５】
記憶部１１は、計算ノード２１，２２，２３，２４，・・・の接続関係を表すｎ次元の空間のうち、所定軸以外の他軸方向のサイズが２以上の所定の整数Ｍの冪である領域ごとに、当該領域に対応する計算ノード群の空きノード情報を記憶する。当該「領域」は線状の領域を含む。また、当該「領域」を「範囲」と称してもよい。また、整数Ｍの冪（累乗、あるいは、べき乗（冪乗）ということもある）は、底をＭ、指数をｋ（ｋ＝０，１，２，・・・）として、Ｍkで表される各値である。各軸方向のサイズは、各軸方向の計算ノードの数を示す。ｋの上限は、並列処理装置１が有する各軸方向の計算ノードの数に応じて定められる。
【００１６】
処理部１２は、ジョブの実行開始時および実行終了時に、空きノード情報４を生成し、生成した空きノード情報４を記憶部１１に格納する。
ここで、空きノード情報４は、該当の計算ノードまたは計算ノード群に対してジョブを割り当て済か否かを示すビット列である。
【００１７】
例えば、ネットワーク２が３次元メッシュ（ｎ＝３）のとき、互いに直交するｘ軸，ｙ軸，ｚ軸を考えることができる。並列処理装置１において、３次元メッシュのｘ軸方向の計算ノード数をＸ個、ｙ軸方向の計算ノード数をＹ個、ｚ軸方向の計算ノード数をＺ個とする。Ｘ，Ｙ，Ｚは、何れも正の整数であり、Ｘ≧Ｙ≧Ｚである。上記所定軸は、例えば、計算ノード数が最大の軸とする（下記に示すノード選択の演算を効率的に行うため）。この場合、上記所定軸はｘ軸である。また、ｘ軸以外の他軸はｙ軸およびｚ軸である。なお、１つ目の計算ノードの座標を（０，０，０）とする（当該座標に対する３次元メッシュの対角の座標は（Ｘ−１，Ｙ−１，Ｚ−１）となる）。
【００１８】
ジョブの割り当てについて、ｘ座標がｘ0以上ｘ0＋ｘ未満、ｙ座標がｙ0以上ｙ0＋ｙ未満、ｚ座標がｚ0以上ｚ0＋ｚ未満の計算ノード群にジョブが割り当てられるとき、（ｘ0，ｙ0，ｚ0）を基点と呼ぶ。ジョブの割り当て先の計算ノードを選ぶ段階では、（ｘ0，ｙ0，ｚ0）を基点候補と呼べる。
【００１９】
ここで、一例として、Ｍ＝２の場合を考える。２の冪は、２0，２1，２2，２3，・・・である。
処理部１２は、ジョブの割り当てに備えて、ジョブの割り当ての際に使用する情報（空きノード情報）を事前に計算しておく。具体的には、処理部１２は、基点候補の全座標に対し、ｘ軸以外の全ての軸方向のサイズが２の冪（１，２，４，８，・・・）となる全ての領域を特定し、各ｘ座標について、当該領域内の計算ノードが全て空きなら０、そうでなければ１であるビット列を生成する。
【００２０】
一例として（ｙ0，ｚ0）＝（０，０）であるＸ個の基点候補の座標を考える。処理部１２は、このＸ個の基点候補の座標に対して、複数のビット列（空きノード情報）を生成する。すなわち、処理部１２は、（ｙ軸方向のサイズ）×（ｚ軸方向のサイズ）＝２p×２qとなる領域に対して、Ｘ個のビットを含むビット列を生成する。ここで、ｐは、２p≦Ｙを満たす０以上の全ての整数をとる。また、ｑは、２q≦Ｚを満たす０以上の全ての整数をとる。また、ビット列のうち、最上位のビットがｘ＝０に、最下位のビットがｘ＝Ｘ−１に対応するものとする（以下の説明でも同様とする）。ｙ軸方向のサイズは、ｙ軸方向の計算ノード数を示す。ｚ軸方向のサイズは、ｚ軸方向の計算ノード数を示す。
【００２１】
より具体的には、処理部１２は、（ｙ軸方向のサイズ）×（ｚ軸方向のサイズ）＝２0×２0＝１となる領域に対して、Ｘ個のビットを含むビット列“０００・・・０”を生成する。
【００２２】
また、処理部１２は、（ｙ軸方向のサイズ）×（ｚ軸方向のサイズ）＝２0×２1＝２となる領域に対して、Ｘ個のビットを含むビット列“０１０・・・０”を生成する。
また、処理部１２は、（ｙ軸方向のサイズ）×（ｚ軸方向のサイズ）＝２1×２0＝２となる領域に対して、Ｘ個のビットを含むビット列“１１０・・・１”を生成する。
【００２３】
また、処理部１２は、（ｙ軸方向のサイズ）×（ｚ軸方向のサイズ）＝２1×２1＝４となる領域に対して、Ｘ個のビットを含むビット列“１１０・・・１”を生成する。
また、処理部１２は、（ｙ軸方向のサイズ）×（ｚ軸方向のサイズ）＝２2×２2＝１６となる領域に対して、Ｘ個のビットを含むビット列“１１０・・・１”を生成する。
【００２４】
処理部１２は、他のｐ，ｑの組み合わせに対応する領域に対しても同様にして空きノード情報を生成する。
こうして、処理部１２は、（ｙ0，ｚ0）＝（ｉ，ｊ）（ｉは０以上Ｙ未満の整数、ｊは０以上Ｚ未満の整数）および（ｐ，ｑ）の各組み合わせに対して、空きノード情報４を生成し、生成した空きノード情報４を記憶部１１に格納する。
【００２５】
処理部１２は、各軸の指定サイズを含むジョブ３の実行要求を受け付けると、記憶部１１を参照して指定サイズに応じた空きノード情報を選択する。処理部１２は、選択した空きノード情報に基づいて、要求されたジョブの割り当て先のノードを抽出する。
【００２６】
例えば、処理部１２は、ｘ軸，ｙ軸，ｚ軸に対する指定サイズｘ×ｙ×ｚのジョブ３の実行要求を受け付けると、空きノード情報４から、ｙ×ｚに応じたサイズに対応する空きノード情報を選択する。すなわち、処理部１２は、２p≦ｙとなる最大のｐ、および、２q≦ｚとなる最大のｑを計算し、計算した（ｐ，ｑ）の組み合わせに対応する空きノード情報を用いて、要求されたジョブの割り当て先のノードを抽出する。まず、処理部１２は、該当の空きノード情報に基づいて、ｙ×ｚのサイズ分だけ計算ノードが空いている箇所を抽出し、次に、当該座標からｘ軸方向に、ｘのサイズ分だけ連続して、ｙ×ｚのサイズの計算ノードが空いている領域を抽出する。処理部１２は、空きノード情報として取得したビット列を用いることで、当該抽出処理を高速に行える。そして、処理部１２は、当該領域に対応する計算ノード群に、要求されたジョブを割り当てる。
【００２７】
このように、処理部１２は、ジョブの実行開始時および実行終了時に、空きノード情報４を生成する。ジョブを割り当てるノードの選択時、処理部１２は、空きノード情報４によりＭの冪のサイズだけを判断すればよい。例えば、Ｍ＝２、Ｙ＝１００の場合、処理部１２は、ｙ軸については７通り（１，２，４，８，１６，３２，６４）のサイズに対する空きノード情報を判断すればよい。こうして、所定の軸以外の各軸について、任意の直方体形状（あるいは超直方体形状）の領域に対する空きノード情報４を用意しておくことで、ジョブ実行時のノード選択を高速化することができる。
【００２８】
また、ジョブ実行時のノード選択を高速化することで、ジョブの実行待ちの時間を減らし、並列処理装置１における各計算ノードの稼働率を向上できる。
なお、処理部１２は、ジョブの実行開始時や実行終了時に、空きノード情報４の全体を更新してもよいし、空きノード情報４のうち、使用状態が変化した計算ノードに対応する部分のみを更新してもよい。更新部分を限定することで、空きノード情報４の生成を一層高速化できる。また、処理部１２は、計算ノードの使用状態が変化しない限り、空きノード情報４を使い回して、計算ノードに対するジョブの割り当てを行える。
【００２９】
更に、上記の説明では、主に３次元メッシュネットワークを例示したが、ネットワーク２は、２次元または４次元以上のメッシュネットワークでもよいし、少なくとも１つの軸がトーラス軸である格子状ネットワークでもよい。
【００３０】
［第２の実施の形態］
図２は、第２の実施の形態の並列処理システムの例を示す図である。並列処理システム５０は、制御ノード１００および計算ノード２００，２００ａ，２００ｂ，２００ｃ，・・・を有する。制御ノード１００および計算ノード２００，２００ａ，２００ｂ，２００ｃ，・・・は、並列処理システム５０における管理用のネットワーク５１に接続されている。また、計算ノード２００，２００ａ，２００ｂ，２００ｃ，・・・は、格子状のネットワークにより相互に接続されている。
【００３１】
制御ノード１００は、ユーザによるジョブの入力を受け付け、計算ノード２００，２００ａ，２００ｂ，２００ｃ，・・・に対するジョブの割り当てを行う。また、制御ノード１００は、割り当て先の計算ノードに対するジョブの実行を指示する。
【００３２】
計算ノード２００，２００ａ，２００ｂ，２００ｃ，・・・それぞれは、プロセッサおよびメモリを有し、制御ノード１００により割り当てられたジョブを並列に実行する。
図３は、制御ノードのハードウェア例を示す図である。制御ノード１００は、プロセッサ１０１、ＲＡＭ１０２、ＨＤＤ１０３、画像信号処理部１０４、入力信号処理部１０５、媒体リーダ１０６および通信インタフェース１０７を有する。各ハードウェアは制御ノード１００のバスに接続されている。
【００３３】
プロセッサ１０１は、制御ノード１００の情報処理を制御するハードウェアである。プロセッサ１０１は、マルチプロセッサであってもよい。プロセッサ１０１は、例えばＣＰＵ、ＤＳＰ、ＡＳＩＣまたはＦＰＧＡなどである。プロセッサ１０１は、ＣＰＵ、ＤＳＰ、ＡＳＩＣ、ＦＰＧＡなどのうちの２以上の要素の組み合わせであってもよい。
【００３４】
ＲＡＭ１０２は、制御ノード１００の主記憶装置である。ＲＡＭ１０２は、プロセッサ１０１に実行させるＯＳ（Operating System）のプログラムやアプリケーションプログラムの少なくとも一部を一時的に記憶する。また、ＲＡＭ１０２は、プロセッサ１０１による処理に用いる各種データを記憶する。
【００３５】
ＨＤＤ１０３は、制御ノード１００の補助記憶装置である。ＨＤＤ１０３は、内蔵した磁気ディスクに対して、磁気的にデータの書き込みおよび読み出しを行う。ＨＤＤ１０３は、ＯＳのプログラム、アプリケーションプログラム、および各種データを記憶する。制御ノード１００は、フラッシュメモリやＳＳＤ（Solid State Drive）などの他の種類の補助記憶装置を備えてもよく、複数の補助記憶装置を備えてもよい。
【００３６】
画像信号処理部１０４は、プロセッサ１０１からの命令に従って、制御ノード１００に接続されたディスプレイ３１に画像を出力する。ディスプレイ３１として、ＣＲＴ（Cathode Ray Tube）ディスプレイや液晶ディスプレイなどを用いることができる。
【００３７】
入力信号処理部１０５は、制御ノード１００に接続された入力デバイス３２から入力信号を取得し、プロセッサ１０１に出力する。入力デバイス３２として、例えば、マウスやタッチパネルなどのポインティングデバイス、キーボードなどを用いることができる。
【００３８】
媒体リーダ１０６は、記録媒体３３に記録されたプログラムやデータを読み取る装置である。記録媒体３３として、例えば、フレキシブルディスク（ＦＤ：Flexible Disk）やＨＤＤなどの磁気ディスク、ＣＤ（Compact Disc）やＤＶＤ（Digital Versatile Disc）などの光ディスク、光磁気ディスク（ＭＯ：Magneto-Optical disk）を使用できる。また、記録媒体３３として、例えば、フラッシュメモリカードなどの不揮発性の半導体メモリを使用することもできる。媒体リーダ１０６は、例えば、プロセッサ１０１からの命令に従って、記録媒体３３から読み取ったプログラムやデータをＲＡＭ１０２またはＨＤＤ１０３に格納する。
【００３９】
通信インタフェース１０７は、ネットワーク５１に接続され、各計算ノードとの通信に用いられるインタフェースである。
図４は、計算ノードのハードウェア例を示す図である。計算ノード２００は、プロセッサ２０１、ＲＡＭ２０２および通信インタフェース２０３，２０４を有する。各ハードウェアは計算ノード２００のバスに接続されている。計算ノード２００ａ，２００ｂ，・・・も計算ノード２００と同様のハードウェアを用いて実現できる。
【００４０】
プロセッサ２０１は、計算ノード２００の情報処理を制御するハードウェアである。プロセッサ２０１は、マルチプロセッサであってもよい。プロセッサ２０１は、例えばＣＰＵ、ＤＳＰ、ＡＳＩＣまたはＦＰＧＡなどである。プロセッサ２０１は、ＣＰＵ、ＤＳＰ、ＡＳＩＣ、ＦＰＧＡなどのうちの２以上の要素の組み合わせであってもよい。
【００４１】
ＲＡＭ２０２は、計算ノード２００の主記憶装置である。ＲＡＭ２０２は、プロセッサ２０１に実行させるプログラムの少なくとも一部を一時的に記憶する。ＲＡＭ２０２は、プロセッサ２０１による処理に用いられる各種データを記憶する。
【００４２】
通信インタフェース２０３は、計算ノード２００ａ，２００ｂ，・・・それぞれと接続され、他の計算ノードとの通信に用いられるインタフェースである。
通信インタフェース２０４は、ネットワーク５１に接続され、制御ノード１００との通信に用いられるインタフェースである。
【００４３】
図５は、３次元メッシュネットワークで接続された計算ノードの例を示す図である。図５の例では、ｘ軸、ｙ軸およびｚ軸の各軸方向の計算ノード数（サイズ）は４である。１つの格子点が１つの計算ノードに相当する。３次元メッシュネットワークに対して、ジョブ形状は、直方体で表される。
【００４４】
図６は、トーラスネットワークで接続された計算ノードの例を示す図である。図６（Ａ）は、２次元トーラスネットワークで接続された計算ノードの例を示している。図６（Ｂ）は、３次元トーラスネットワークで接続された計算ノードの例を示している。図６（Ａ）の例では、ｘ軸およびｙ軸の２軸がトーラス軸である。また、図６（Ｂ）の例では、ｘ軸、ｙ軸およびｚ軸の３軸がトーラス軸である。ただし、空間を表す全ての軸のうちの一部の軸のみがトーラス軸であってもよい。
【００４５】
ここで、並列処理システム５０では、１つのジョブが格子全体に対する部分格子を専有する。このため、あるジョブを割り当て済である部分格子は、他のジョブの割り当て候補から除外される。
【００４６】
以下の説明では、主に、３次元の格子状ネットワーク（３次元メッシュネットワークや３次元トーラスネットワーク）を想定して、制御ノード１００の機能を説明する。ただし、３次元に限らず、他の次元でも制御ノード１００の機能を適用できる。
【００４７】
図７は、制御ノードの機能例を示す図である。制御ノード１００は、記憶部１１０、受付部１２０、出力部１３０、実行ノード選択部１４０、ノード情報管理部１５０および空きノード情報生成部１６０を有する。記憶部１１０は、ＲＡＭ１０２やＨＤＤ１０３の記憶領域を用いて実現される。受付部１２０、出力部１３０、実行ノード選択部１４０、ノード情報管理部１５０および空きノード情報生成部１６０は、ＲＡＭ１０２に記憶されたプログラムをプロセッサ１０１が実行することで実現される。
【００４８】
記憶部１１０は、計算ノードの空き状況を示すテーブルを記憶する。１つのテーブルは、１つのビット列に相当する。テーブルの具体的な内容は後述される。
受付部１２０は、ユーザによるジョブの実行要求を受け付ける。ジョブの実行要求は、ジョブの実行に要求される計算ノードの数およびジョブ形状（指定サイズ）の情報を含む。ジョブ形状は、３次元の場合、直方体となる（例えば、２次元では長方形である）。
【００４９】
出力部１３０は、ジョブの割り当て結果や、ジョブの実行結果を、ディスプレイ３１に表示させる。
実行ノード選択部１４０は、記憶部１１０に記憶されたテーブルに基づいて、ジョブを実行する計算ノード（実行ノード）を選択する（計算ノードに対するジョブの割り当てを行う）。実行ノード選択部１４０は、ノード情報管理部１５０を介して、割り当て先の計算ノードに、ジョブの実行を指示する。また、実行ノード選択部１４０は、計算ノードに対するジョブの割り当て結果やジョブの実行結果を出力部１３０に提供する。
【００５０】
ここで、ｘ座標がｘ0以上ｘ0＋ｘ未満、ｙ座標がｙ0以上ｙ0＋ｙ未満、ｚ座標がｚ0以上ｚ0＋ｚ未満の計算ノード群にジョブが割り当てられるとき、（ｘ0，ｙ0，ｚ0）を基点と呼ぶ。ジョブの割り当て先の計算ノードを決定する段階では、（ｘ0，ｙ0，ｚ0）を基点候補と呼べる。ただし、以下の説明では、基点候補についても基点と呼ぶことがある。
【００５１】
ノード情報管理部１５０は、計算ノード２００，２００ａ，・・・それぞれの使用状態を管理する。具体的には、ノード情報管理部１５０は、ジョブの実行に用いられていない未使用の計算ノード、ジョブの実行に使用中の計算ノード、および、未使用ではあるがジョブを割り当てられない故障中の計算ノードを示す割り当て情報を生成し、記憶部１１０に格納する。割り当て情報は、１つの計算ノードを１つのビットに対応付けたビットマップである。一例として、当該ビットマップでは、０は未使用（ジョブ割り当て可能）を示す。また、１は使用中または故障中（ジョブ割り当て不可能）を示す。ノード情報管理部１５０は、ジョブが計算ノードに割り当てられたタイミング（ジョブの実行が開始されたタイミング）やジョブが終了したタイミングを、空きノード情報生成部１６０に通知する。
【００５２】
空きノード情報生成部１６０は、記憶部１１０に記憶されたビットマップに基づいて、空きノード情報（上記のテーブル）を生成し、記憶部１１０に格納する。空きノード情報生成部１６０は、ジョブが計算ノードに割り当てられたタイミング、および、ジョブが終了したタイミング（すなわち、計算ノードの使用状態が変化したタイミング）で、テーブルの生成を行う。
【００５３】
図８は、計算ノードの空き状況を表すテーブルの例を示す図である。ここで、並列処理システム５０が有するｘ軸方向の計算ノードの数をＸ、ｙ軸方向の計算ノードの数をＹ、ｚ軸方向の計算ノードの数をＺとする（前述のように、Ｘ≧Ｙ≧Ｚである）。テーブルは、ビット列の情報であり、ビット列の各ビットはｘ座標に相当する。例えば、各軸方向のうち、計算ノードの数が最大となる軸をｘ軸とする。
【００５４】
１つのテーブルは、（ｐ，ｑ，ｙ0，ｚ0）の組によって識別される。図８（Ａ）は、ｔａｂｌｅ［ｐ］［ｑ］［ｙ0］［ｚ0］に対応する領域の例を示す。ｐは、２p≦Ｙを満たす０以上の整数である。また、ｑは、２q≦Ｚを満たす０以上の整数である。図８（Ａ）の例では、３次元の格子状ネットワークを表す直方体が、原点（０，０，０）を含む各軸が正である空間に配置されている。この場合、座標（０，ｙ0，ｚ0）は、ｔａｂｌｅ［ｐ］［ｑ］［ｙ0］［ｚ0］に対応する領域に属する全計算ノードにジョブを割り当てたと仮定した場合の基点の座標である。ｔａｂｌｅ［ｐ］［ｑ］［ｙ0］［ｚ0］に対応する領域の頂点の一例を示せば、同基点の対角に位置する座標は、（Ｘ−１，ｙ0＋２p−１，ｚ0＋２q−１）となる。同基点のｙｚ平面状の対角に位置する座標は、（０，ｙ0＋２p−１，ｚ0＋２q−１）となる。同基点からｘ軸の正方向に進んだ時の終端の座標は、（Ｘ−１，ｙ0，ｚ0）となる。
【００５５】
図８（Ｂ）は、ｔａｂｌｅ［ｐ］［ｑ］［ｙ0］［ｚ0］のビット列に含まれる各ビットの概念を示す。図８（Ｂ）は、Ｘ＝１２の場合の例である。例えば、ｔａｂｌｅ［ｐ］［ｑ］［ｙ0］［ｚ0］＝０１００１０００００００である。各ｘ座標について１ビットが対応している。この場合、最上位の桁のビットは、ｘ＝０に対応する。最下位の桁のビットは、ｘ＝Ｘ−１に対応する。ある１つのｘ座標について、ｙ座標がｙ0以上ｙ0＋２p未満、かつ、ｚ座標がｚ0以上ｚ0＋２q未満である全ての座標に対応する全ての計算ノードがジョブ割り当て可能であれば、当該ｘ座標に対応するビットは０である。そうでなければ（該当の各計算ノードのうちの１つでもジョブ割り当て不可能であれば）、当該ｘ座標に対応するビットは１である。なお、各テーブルに対応する領域のｙ軸方向のサイズおよびｚ軸方向のサイズは、２の冪に限らず、３以上の何れかの整数の冪でもよい。
【００５６】
このように、空きノード情報は、所定軸（例えば、ｘ軸）の座標値に対応するビットを複数含むビット列（テーブル）で表される。空きノード情報生成部１６０は、当該ビット列に対応する領域のうち所定軸の第１の座標値に対応する部分に属する全計算ノードにジョブを割り当て可能な場合に、第１の座標値に対応する第１のビットを、ジョブ割り当て可能を示す第１の値（例えば０）に設定する。また、空きノード情報生成部１６０は、当該部分に属する少なくとも１つの計算ノードにジョブを割り当て不可能な場合に、第１のビットを、ジョブ割り当て不可能を示す第２の値（例えば１）に設定する。
【００５７】
そして、実行ノード選択部１４０は、ジョブの割り当て先のノードを抽出する際、空きノード情報に相当するビット列のうち、所定軸方向の指定サイズの数分、第１の値が連続するビット列部分があるか否かを判定する。実行ノード選択部１４０は、当該ビット列部分がある場合、該当のビット列に相当する領域に対応する計算ノード群のうち、当該ビット列部分の座標値（座標値範囲）に対応する計算ノードを、ジョブの割り当て先のノードと決定する。
【００５８】
次に、制御ノード１００による処理の手順を説明する。まず、空きノード情報生成部１６０による処理の手順を説明する。
図９は、空きノード情報生成の例を示すフローチャートである。以下、図９に示す処理をステップ番号に沿って説明する。空きノード情報生成部１６０は、ジョブが計算ノードに割り当てられたことやジョブの実行が終了したことの通知をノード情報管理部１５０から受け付けると、下記の手順を開始する。
【００５９】
（Ｓ１）空きノード情報生成部１６０は、ｐに０を代入する。
（Ｓ２）空きノード情報生成部１６０は、ｑに０を代入する
（Ｓ３）空きノード情報生成部１６０は、ｐ＝０であるか否かを判定する。ｐ＝０である場合、処理をステップＳ４に進める。ｐ＝０でない場合、処理をステップＳ１１に進める。
【００６０】
（Ｓ４）空きノード情報生成部１６０は、ｑ＝０であるか否かを判定する。ｑ＝０である場合、処理をステップＳ５に進める。ｑ＝０でない場合、処理をステップＳ８に進める。
【００６１】
（Ｓ５）空きノード情報生成部１６０は、全ての整数ｙ0，ｚ0（０≦ｙ0＜Ｙ、０≦ｚ0＜Ｚ）について、ｙ座標と座標が（ｙ0，ｚ0）のノード群の割り当て情報を、記憶部１１０に格納されたｔａｂｌｅ［０］［０］［ｙ0］［ｚ0］に格納する。
【００６２】
（Ｓ６）空きノード情報生成部１６０は、ｑ＋１をｑに代入する。
（Ｓ７）空きノード情報生成部１６０は、２q≦Ｚであるか否かを判定する。２q≦Ｚである場合、処理をステップＳ３に進める。２q≦Ｚでない場合、処理をステップＳ９に進める。
【００６３】
（Ｓ８）空きノード情報生成部１６０は、全ての整数ｙ0，ｚ0（０≦ｙ0＜Ｙ、０≦ｚ0＜Ｚ）について、ｔａｂｌｅ［０］［ｑ］［ｙ0］［ｚ0］にｔａｂｌｅ［０］［ｑ−１］［ｙ0］［ｚ0］とｔａｂｌｅ［０］［ｑ−１］［ｙ0］［（ｚ0＋２q-1）％Ｚ］のＯＲ（ＯＲ演算の結果）を代入する。ここで、％記号は、剰余演算を表す。そして、処理をステップＳ６に進める。
【００６４】
（Ｓ９）空きノード情報生成部１６０は、ｐ＋１をｐに代入する。
（Ｓ１０）空きノード情報生成部１６０は、２p≦Ｙであるか否かを判定する。２p≦Ｙである場合、処理をステップＳ２に進める。２p≦Ｙでない場合、処理を終了する。
【００６５】
（Ｓ１１）空きノード情報生成部１６０は、全ての整数ｙ0，ｚ0（０≦ｙ0＜Ｙ、０≦ｚ0＜Ｚ）について、ｔａｂｌｅ［ｐ］［ｑ］［ｙ0］［ｚ0］にｔａｂｌｅ［ｐ−１］［ｑ］［ｙ0］［ｚ0］とｔａｂｌｅ［ｐ−１］［ｑ］［（ｙ0＋２p-1）％Ｙ］［ｚ0］のＯＲを代入する。そして、処理をステップＳ６に進める。
【００６６】
こうして、空きノード情報生成部１６０は、計算ノードの使用状態の変化を契機として、（ｐ，ｑ，ｙ0，ｚ0）の全ての組み合わせに対し、ｔａｂｌｅ［ｐ］［ｑ］［ｙ0］［ｚ0］を予め生成する。空きノード情報生成部１６０は、既存のテーブルを新たに生成されたテーブルに置き換える。なお、空きノード情報生成部１６０は、各テーブルのうち、使用状態が変化した計算ノードに関係するテーブルに限定して、生成し直してもよい。
【００６７】
次に、実行ノード選択部１４０による処理の手順を説明する。
図１０は、ジョブ割り当ての例を示すフローチャートである。以下、図１０に示す処理をステップ番号に沿って説明する。実行ノード選択部１４０は、ジョブの実行要求を受け付けると、下記の手順を開始する。
【００６８】
（Ｓ２１）実行ノード選択部１４０は、要求されたジョブの各軸方向のサイズ（ｘ，ｙ，ｚ）を取得する。
（Ｓ２２）実行ノード選択部１４０は、２p≦ｙとなる最大の自然数をｐに代入する。また、実行ノード選択部１４０は、２q≦ｚとなる最大の自然数をｑに代入する。
【００６９】
（Ｓ２３）実行ノード選択部１４０は、ｙ0に０を代入する。
（Ｓ２４）実行ノード選択部１４０は、ｚ0に０を代入する。
（Ｓ２５）実行ノード選択部１４０は、ビット列Ｅ（ｙ0，（ｚ0＋ｚ−２q）％Ｚ，ｙ，２q）を求める。Ｅ（ｙ0，（ｚ0＋ｚ−２q）％Ｚ，ｙ，２q）は、ｔａｂｌｅ［ｐ］［ｑ］［ｙ0］［（ｚ0＋ｚ−２q）％Ｚ］とｔａｂｌｅ［ｐ］［ｑ］［（ｙ0＋ｙ−２p）％Ｙ］［（ｚ0＋ｚ−２q）％Ｚ］のＯＲ（ＯＲ演算の結果）である。ここで、（ａ，ｂ）を起点とした各軸長さ（ｃ，ｄ）の空き状況をビット列Ｅ（ａ，ｂ，ｃ，ｄ）と表している。
【００７０】
（Ｓ２６）実行ノード選択部１４０は、Ｅ（ｙ0，（ｚ0＋ｚ−２q）％Ｚ，ｙ，２q）にｘビット連続する０があるか否かを判定する。ｘビット連続する０がある場合、処理をステップＳ２７に進める。ｘビット連続する０がない場合、処理をステップＳ３０に進める。
【００７１】
（Ｓ２７）実行ノード選択部１４０は、ビット列Ｅ（ｙ0，ｚ0，ｙ，ｚ）を求める。Ｅ（ｙ0，ｚ0，ｙ，ｚ）は、Ｅ（ｙ0，（ｚ0＋ｚ−２q）％Ｚ，ｙ，２q）とｔａｂｌｅ［ｐ］［ｑ］［ｙ0］［ｚ0］とｔａｂｌｅ［ｐ］［ｑ］［（ｙ0＋ｙ−２p）％Ｙ］［ｚ0］の三者のＯＲである。
【００７２】
（Ｓ２８）実行ノード選択部１４０は、Ｅ（ｙ0，ｚ0，ｙ，ｚ）にｘビット連続する０があるか否かを判定する。ｘビット連続する０がある場合、処理をステップＳ２９に進める。ｘビット連続する０がない場合、処理をステップＳ３１に進める。
【００７３】
（Ｓ２９）実行ノード選択部１４０は、ジョブの割り当て結果を出力部１３０に出力する。このとき、基点のｘ座標は、ステップＳ２８で判定されたｘビット連続する０の開始点の座標である。また、基点のｙ，ｚ座標は、（ｙ0，ｚ0）である。実行ノード選択部１４０は、ジョブの割り当て先の計算ノードに対して、ジョブの実行を指示してもよい。そして、実行ノード選択部１４０は、処理を終了する。
【００７４】
（Ｓ３０）実行ノード選択部１４０は、ｚ0＋ｚ−２qをｚ0に代入する。
（Ｓ３１）実行ノード選択部１４０は、ｚ0＋１をｚ0に代入する。
（Ｓ３２）実行ノード選択部１４０は、ｚ軸がトーラス軸であるか否かに応じて次の判定を行う。
【００７５】
（１）ｚ軸がトーラス軸である場合、実行ノード選択部１４０は、ｚ0＜Ｚであるか否かを判定する。ｚ0＜Ｚである場合、処理をステップＳ２５に進める。ｚ0＜Ｚでない場合、処理をステップＳ３３に進める。
【００７６】
（２）ｚ軸がトーラス軸でない場合、実行ノード選択部１４０は、ｚ0＜Ｚ−ｚ＋１であるか否かを判定する。ｚ0＜Ｚ−ｚ＋１である場合、処理をステップＳ２５に進める。ｚ0＜Ｚ−ｚ＋１でない場合、処理をステップＳ３３に進める。
【００７７】
（Ｓ３３）実行ノード選択部１４０は、ｙ0＋１をｙ0に代入する。
（Ｓ３４）実行ノード選択部１４０は、ｙ軸がトーラス軸であるか否かに応じて次の判定を行う。
【００７８】
（１）ｙ軸がトーラス軸である場合、実行ノード選択部１４０は、ｙ0＜Ｙであるか否かを判定する。ｙ0＜Ｙである場合、処理をステップＳ２４に進める。ｙ0＜Ｙでない場合、処理をステップＳ３５に進める。
【００７９】
（２）ｙ軸がトーラス軸でない場合、実行ノード選択部１４０は、ｙ0＜Ｙ−ｙ＋１であるか否かを判定する。ｙ0＜Ｙ−ｙ＋１である場合、処理をステップＳ２４に進める。ｙ0＜Ｙ−ｙ＋１でない場合、処理をステップＳ３５に進める。
【００８０】
（Ｓ３５）実行ノード選択部１４０は、ジョブの割り当て不可を出力部１３０に出力する。
図１１は、空きノードの探索例を示す図である。図１１（Ａ）では、（ｙ0，ｚ0）＝（１，１）を基点として、ｙ方向の長さ６、ｚ方向の長さ７の直方体内での割り当て可否を判定する例を示している。この場合、２p≦６となる最大のｐは、２である。また、２q≦７となる最大のｑは、２である。したがって、実行ノード選択部１４０は、（ｐ，ｑ）＝（２，２）である次のテーブル（２2×２2＝４×４領域のテーブル）を用いて、該当領域に対応する計算ノードの空き状況を判断する。
【００８１】
第１のテーブルは、ｔａｂｌｅ［２］［２］［１］［１］である。第２のテーブルは、ｔａｂｌｅ［２］［２］［３］［１］である。第３のテーブルは、ｔａｂｌｅ［２］［２］［１］［４］である。第４のテーブルは、ｔａｂｌｅ［２］［２］［３］［４］である。これら４つのテーブルのＯＲ演算結果は、（ｙ0，ｚ0）＝（１，１）を基点とした６×７領域の空きノード情報（ビット列）Ｅ（１，１，６，７）に相当する。
【００８２】
このように、実行ノード選択部１４０は、指定サイズに合致した領域に対応する空きノード情報がない場合、ｙ，ｚ軸方向のサイズがｙ，ｚ軸方向の指定サイズよりも小さい領域に対応する第１の空きノード情報を複数選択する。そして、実行ノード選択部１４０は、複数の第１の空きノード情報を組み合わせることで、ｙ，ｚ軸方向のサイズが指定サイズである領域に対応する第２の空きノード情報を生成し、第２の空きノード情報に基づいて、ジョブの割り当て先の計算ノードを抽出する。
【００８３】
図１１（Ｂ）は、図１０のステップＳ２６の判定により、探索の省略が可能となる理由を説明する図である。上記の４つのテーブルのうち、ｔａｂｌｅ［２］［２］［１］［４］とｔａｂｌｅ［２］［２］［３］［４］のＯＲ演算結果が割り当て不可を示せば、当該ＯＲ演算結果に対応する領域を包含する領域へのジョブ割り当ては不可である。したがって、この時点で、Ｅ（１，１，６，７）を計算しなくても、Ｅ（１，１，６，７）に対応する領域へのジョブの割り当ては不可であることが分かる。このとき、実行ノード選択部１４０は、（ｙ0，ｚ0）＝（１，４）に対して、ｚ方向の１つ先の基点（ｙ0，ｚ0）＝（１，５）から、空きの計算ノード群の探索を始めればよい（探索方向はｚ軸方向となる）。
【００８４】
このように、実行ノード選択部１４０は、割り当て先の計算ノードを抽出する際、複数の第１の空きノード情報のうちの一部の第１の空きノード情報を用いて、第２の空きノード情報に対応する領域にジョブを割り当て可能であるか否かを判定する。そして、割り当て可能でない場合、実行ノード選択部１４０は、第２の空きノード情報の生成を省略し、次の領域について計算ノード群の空き状況を確認する。こうして、判定における一部の試行を省略することで、計算ノードの選択を一層高速化できる。
【００８５】
なお、ステップＳ２６，Ｓ２８では、実行ノード選択部１４０は、ビット列にｘビット連続する０があるか否かを次の手順によって高速に行える。
図１２は、ビット列判定の例を示すフローチャートである。以下、図１２に示す処理をステップ番号に沿って説明する。以下に示す手順は、図１０のステップＳ２６またはステップＳ２８に相当する。
【００８６】
（Ｓ４１）実行ノード選択部１４０は、２Ｘ＜（ｘ＋１）ｌｏｇ2ｘであるか否かを判定する。２Ｘ＜（ｘ＋１）ｌｏｇ2ｘである場合、処理をステップＳ５０に進める。２Ｘ＜（ｘ＋１）ｌｏｇ2ｘでない場合、処理をステップＳ４２に進める。
【００８７】
（Ｓ４２）実行ノード選択部１４０は、入力ビット列をｔに代入する。ここで、入力ビット列は、ステップＳ２６の場合、ビット列Ｅ（ｙ0，（ｚ0＋ｚ−２q）％Ｚ，ｙ，２q）である。入力ビット列は、ステップＳ２８の場合、ビット列Ｅ（ｙ0，ｚ0，ｙ，ｚ）である。また、実行ノード選択部１４０は、ｓに１を代入する。
【００８８】
（Ｓ４３）実行ノード選択部１４０は、ｓ＋ｓ＜ｘであるか否かを判定する。ｓ＋ｓ＜ｘである場合、処理をステップＳ４４に進める。ｓ＋ｓ＜ｘでない場合、処理をステップＳ４６に進める。
【００８９】
（Ｓ４４）実行ノード選択部１４０は、ｔＯＲｔL1の演算結果をｔに代入する。ここで、ｔL1は、ｔをｓビット左ローテートしたビット列である。
（Ｓ４５）実行ノード選択部１４０は、ｓ＋ｓをｓに代入する。そして、実行ノード選択部１４０は、処理をステップＳ４３に進める。
【００９０】
（Ｓ４６）実行ノード選択部１４０は、ｔＯＲｔL2の演算結果をｔに代入する。ここで、ｔL2は、ｔをｘ−ｓビット左ローテートしたビット列である。
（Ｓ４７）実行ノード選択部１４０は、ｘ軸がトーラス軸であるか否かに応じて次の判定を行う。
【００９１】
（１）ｘ軸がトーラス軸である場合、実行ノード選択部１４０は、ｔの全ビットの中に０があるか否かを判定する。０がある場合、処理をステップＳ４８に進める。０がない場合、処理をステップＳ４９に進める。
【００９２】
（２）ｘ軸がトーラス軸でない場合、実行ノード選択部１４０は、ｔの右（最下位ビット）からｘ−１ビットを除いたビットの中に０があるか否かを判定する。当該ビットに０がある場合、処理をステップＳ４８に進める。当該ビットに０がない場合、処理をステップＳ４９に進める。
【００９３】
（Ｓ４８）実行ノード選択部１４０は、判定結果として、Ｙｅｓを返す。実行ノード選択部１４０は、０が見つかったビット位置を割り当て先のｘ座標（割り当てｘ座標）の基点とする。そして、処理を終了する。
【００９４】
（Ｓ４９）実行ノード選択部１４０は、判定結果として、Ｎｏを返す。そして、処理を終了する。
（Ｓ５０）実行ノード選択部１４０は、検索用マスクを初期化する。検索用マスクとは、Ｘビットのビット列からｘビットの連続する０を検索するための検索情報である。検索用マスクは、初期化された直後では、最上位ビット以下のｘビット分を１、それ以外のビットを０としたビット列である。
【００９５】
（Ｓ５１）実行ノード選択部１４０は、入力ビット列と、検索用マスクとのＡＮＤ結果が全ビット０であるか否かを判定する。全ビット０である場合、処理をステップＳ５３に進める。全ビット０でない場合、処理をステップＳ５２に進める。
【００９６】
（Ｓ５２）実行ノード選択部１４０は、検索用マスクをシフト（右シフト）可能であるか否かを判定する。シフト可能である場合、実行ノード選択部１４０は、検索用マスクをまとめて右シフトして、処理をステップＳ５１に進める。右シフトする量は、ステップＳ５１のＡＮＤ結果を最下位ビットからみて最初に１が出現する桁から、検索用マスクの連続する１の最上位の桁までカウントした数である。シフト可能でない場合、処理をステップＳ４９に進める。ここで、ｘ軸がトーラス軸のとき、検索用マスクの連続する１のうちの最も左の１が、検索用マスクの一番右の桁（最下位ビット）からあふれる場合にシフト不可であり、そうでない場合にシフト可能である。また、ｘ軸がトーラス軸でないとき、検索用マスクの連続する１のうちの一番右の１が、検索用マスクの一番右の桁からあふれる場合にシフト不可であり、そうでない場合にシフト可能である。
【００９７】
（Ｓ５３）実行ノード選択部１４０は、判定結果として、Ｙｅｓを返す。実行ノード選択部１４０は、検索用マスクの１が連続して並ぶ位置を、割り当てｘ座標とする。そして、処理を終了する。
【００９８】
ここで、ステップＳ４１の判定について、２Ｘ＜（ｘ＋１）ｌｏｇ2ｘである場合、ステップＳ４２以降を実行するより、ステップＳ５０以降を実行した方がステップ数が少なくて済む。一方、２Ｘ＜（ｘ＋１）ｌｏｇ2ｘでない場合、ステップＳ５０以降を実行するより、ステップＳ４２以降を実行した方がステップ数が少なくて済む。なぜなら、ステップＳ５０へ進む場合、演算のステップ数は、高々、２Ｘ／（ｘ＋１）程度であり、ステップＳ４２へ進む場合、演算のステップ数は、高々、ｌｏｇ2ｘ程度だからである。こうして、演算のステップ数の少ない手順を選択するために、実行ノード選択部１４０は、ステップＳ４１の判定を行う。
【００９９】
次に、ステップＳ４１でＮｏの場合（ステップＳ４２へ進む場合）の処理の具体例を説明する。
図１３は、ビット列判定の具体例を示す図である。ここでの例は、［ｌｏｇ2ｘ］回のＯＲ演算でｘビットの連続する０の有無と、その開始位置を求める具体例である。特に、ｘ＝５、Ｘ＝１２の場合を例示する。図１３では、入力ビット列６０の各ビットを、ａkと表す。ｋは、入力ビット列６０における桁に対応する０以上の整数である。ｋ＝０が入力ビット列６０の最上位桁である。ｋ＝１，２，３，・・・と順番に入力ビット列６０における桁が下がる。ｋ＝１１が入力ビット列６０の最下位桁である。また、ａk-lは、ａkからａlまでの全てのビットをＯＲした結果を示す。このとき、ビット列の両端は回り込んで考える。例えば、ａ0-3は、ａ0，ａ1，ａ2，ａ3のＯＲである。ａ9-1は、ａ9，ａ10，ａ11，ａ0，ａ1のＯＲである。
【０１００】
最初にステップＳ４４を実行する直前の段階では、ｔは入力ビット列６０であり、ｓ＝１である。このとき、ｔL1はビット列６１である。ｓ＝１なので、ビット列６１は、入力ビット列６０を１ビット左ローテートした結果である。実行ノード選択部１４０は、入力ビット列６０とビット列６１のＯＲ演算の結果であるビット列６２をｔに代入する（ステップＳ４４）。
【０１０１】
実行ノード選択部１４０は、ｓ＋ｓ＝１＋１＝２を、ｓに代入する（ステップＳ４５）。ｓ＋ｓ＝２＋２＝４＜５なので（ステップＳ４３  Ｙｅｓ）、実行ノード選択部１４０は、再びステップＳ４４を実行する。この段階では、ｔL1は、ビット列６３である。ｓ＝２なので、ビット列６３は、ビット列６２を２ビット左ローテートした結果である。実行ノード選択部１４０は、ビット列６２とビット列６３のＯＲ演算の結果であるビット列６３をｔに代入する（ステップＳ４４）。
【０１０２】
実行ノード選択部１４０は、ｓ＋ｓ＝２＋２＝４を、ｓに代入する（ステップＳ４５）。ｓ＋ｓ＝４＋４＝８＞５なので（ステップＳ４３  Ｎｏ）、実行ノード選択部１４０は、ステップＳ４６に進む。この段階では、ｔL2はビット列６５である。ｘ−ｓ＝５−４＝１なので、ビット列６５は、ビット列６４を１ビット左ローテートした結果である。実行ノード選択部１４０は、ビット列６４とビット列６５のＯＲ演算の結果であるビット列６６をｔに代入する（ステップＳ４６）。こうして得られたビット列６６のうち、０であるビットが存在すれば、入力ビット列６０において５ビット連続する０が存在することになる。また、０である桁に対応するｘ座標を基点として選択できることになる。
【０１０３】
なお、ビット列６６のうち、ａ8-0，ａ9-1，ａ10-2，ａ11-3のビットはｘ軸がトーラス軸の場合に有効であり、ｘ軸がトーラス軸でない場合には無効である。すなわち、ｘ軸がトーラス軸である場合には、ａ8-0，ａ9-1，ａ10-2，ａ11-3のビットに対応する座標は、基点の候補になり得る。一方、ｘ軸がトーラス軸でない場合には、ａ8-0，ａ9-1，ａ10-2，ａ11-3のビットに対応する座標は、基点の候補とはなり得ない。
【０１０４】
図１４は、計算ノード数に対する所要ステップ数の例を示す図である。図１４では、Ｘ，Ｙ，Ｚおよび全体の計算ノード数Ｎ（＝ＸＹＺ）に対して、前処理および割り当て可否判定の所要ステップ数と、両者の合計値とを示している。ここで、前処理の所要ステップ数は、図９のステップＳ５，Ｓ８，Ｓ１１を実行する回数に相当する。また、割り当て可否判定の所要ステップ数は、図１２のステップＳ４４，Ｓ４６，Ｓ５１を実行する回数に相当する。所要ステップ数は、以下に説明されるジョブ割り当ての比較例による所要ステップ数と比較される。
【０１０５】
次に、制御ノード１００とは異なる方法でジョブ割り当てを行う場合を例示し、制御ノード１００のジョブ割り当て方法と比較する。比較例の説明では、制御ノード１００に代えて、制御ノード５００を用いる。
【０１０６】
図１５は、制御ノードの機能の比較例を示す図である。制御ノード５００は、記憶部５１０、受付部５２０、出力部５３０、実行ノード選択部５４０およびノード情報管理部５５０を有する。
【０１０７】
受付部５２０は、受付部１２０と同様の機能を実現する。出力部５３０は、出力部１３０と同様の機能を実現する。ノード情報管理部５５０は、ノード情報管理部１５０と同様の機能を実現する。
【０１０８】
ただし、制御ノード５００は、空きノード情報生成部１６０に相当する機能を有していない。また、実行ノード選択部５４０は、実行ノード選択部１４０とは異なる方法により、ジョブ割り当てを行う。１つ目の比較例では、実行ノード選択部５４０は、１つのビットを１つの計算ノードの空き状況に対応付けたビットマップ（前述の割り当て情報）を参照して、ジョブ割り当てを行う。当該割り当て情報は、ノード情報管理部５５０により生成され、記憶部５１０に格納されている。１つ目の比較例の具体的な手順は、次の通りである。
【０１０９】
図１６は、ジョブ割り当ての比較例（その１）を示すフローチャートである。以下、図１６に示す処理をステップ番号に沿って説明する。
（Ｓ１０１）実行ノード選択部５４０は、ジョブの各軸方向のサイズ（ｘ，ｙ，ｚ）を取得する。
【０１１０】
（Ｓ１０２）実行ノード選択部５４０は、割り当て先の基点となる座標（ｘ0，ｙ0，ｚ0）を（０，０，０）に初期化する。
（Ｓ１０３）実行ノード選択部５４０は、基点座標から割り当て可能であるか否かを判定する。割り当て可能である場合、処理をステップＳ１０４に進める。割り当て不可である場合、処理をステップＳ１０５に進める。ここで、ステップＳ１０３の判定方法の詳細は後述される。
【０１１１】
（Ｓ１０４）実行ノード選択部５４０は、割り当て結果を出力部５３０に出力する。そして、処理を終了する。
（Ｓ１０５）実行ノード選択部５４０は、基点座標を更新可能であるか否かを判定する。更新可能である場合、実行ノード選択部５４０は、基点座標を更新して、処理をステップＳ１０３に進める。更新可能でない場合、処理をステップＳ１０６に進める。ここで、ステップＳ１０５の判定方法の詳細は後述される。
【０１１２】
（Ｓ１０６）実行ノード選択部５４０は、割り当て不可を出力部５３０に出力する。そして、処理を終了する。
図１７は、比較例（その１）の割り当て判定を示すフローチャートである。以下、図１７に示す処理をステップ番号に沿って説明する。以下に示す手順は、図１６のステップＳ１０３の判定処理に相当する。
【０１１３】
（Ｓ１１１）実行ノード選択部５４０は、ｋに０を代入する。
（Ｓ１１２）実行ノード選択部５４０は、ｊに０を代入する。
（Ｓ１１３）実行ノード選択部５４０は、ｉに０を代入する。
【０１１４】
（Ｓ１１４）実行ノード選択部５４０は、（ｘ0＋ｉ，ｙ0＋ｊ，ｚ0＋ｋ）の座標に対応する計算ノードを使用可能であるか否かを判定する。使用可能である場合、処理をステップＳ１１６に進める。使用可能でない場合、処理をステップＳ１１５に進める。
【０１１５】
（Ｓ１１５）実行ノード選択部５４０は、判定結果として、Ｎｏを返す。そして、処理を終了する。
（Ｓ１１６）実行ノード選択部５４０は、ｉ＋１をｉに代入する。
【０１１６】
（Ｓ１１７）実行ノード選択部５４０は、ｉ＜ｘであるか否かを判定する。ｉ＜ｘである場合、処理をステップＳ１１４に進める。ｉ＜ｘでない場合、処理をステップＳ１１８に進める。
【０１１７】
（Ｓ１１８）実行ノード選択部５４０は、ｊ＋１をｊに代入する。
（Ｓ１１９）実行ノード選択部５４０は、ｊ＜ｙであるか否かを判定する。ｊ＜ｙである場合、処理をステップＳ１１３に進める。ｊ＜ｙでない場合、処理をステップＳ１２０に進める。
【０１１８】
（Ｓ１２０）実行ノード選択部５４０は、ｋ＋１をｋに代入する。
（Ｓ１２１）実行ノード選択部５４０は、ｋ＜ｚであるか否かを判定する。ｋ＜ｚである場合、処理をステップＳ１１２に進める。ｋ＜ｚでない場合、処理をステップＳ１２２に進める。
【０１１９】
（Ｓ１２２）実行ノード選択部５４０は、判定結果として、Ｙｅｓを返す。そして、処理を終了する。
なお、ステップＳ１１４では、トーラス軸を考慮する場合、（（ｘ0＋ｉ）％Ｘ，（ｙ0＋ｊ）％Ｙ，（ｚ0＋ｋ）％Ｚ）に対応する計算ノードが使用可であるか否かを判定することが考えられる。
【０１２０】
図１８は、比較例（その１）の基点座標更新判定を示すフローチャートである。以下、図１８に示す処理をステップ番号に沿って説明する。以下に示す手順は、図１６のステップＳ１０５に相当する。
【０１２１】
（Ｓ１３１）実行ノード選択部５４０は、ｘ0＋１をｘ0に代入する。
（Ｓ１３２）実行ノード選択部５４０は、ｘ軸がトーラス軸であるか否かに応じて次の判定を行う。
【０１２２】
（１）ｘ軸がトーラス軸である場合、実行ノード選択部５４０は、ｘ0＜Ｘであるか否かを判定する。ｘ0＜Ｘである場合、処理をステップＳ１３８に進める。ｘ0＜Ｘでない場合、処理をステップＳ１３３に進める。
【０１２３】
（２）ｘ軸がトーラス軸でない場合、実行ノード選択部５４０は、ｘ0＜Ｘ−ｘ＋１であるか否かを判定する。ｘ0＜Ｘ−ｘ＋１である場合、処理をステップＳ１３８に進める。ｘ0＜Ｘ−ｘ＋１でない場合、処理をステップＳ１３３に進める。
【０１２４】
（Ｓ１３３）実行ノード選択部５４０は、ｙ0＋１をｙ0に代入する。実行ノード選択部５４０は、ｘ0に０を代入する。
（Ｓ１３４）実行ノード選択部５４０は、ｙ軸がトーラス軸であるか否かに応じて次の判定を行う。
【０１２５】
（１）ｙ軸がトーラス軸である場合、実行ノード選択部５４０は、ｙ0＜Ｙであるか否かを判定する。ｙ0＜Ｙである場合、処理をステップＳ１３８に進める。ｙ0＜Ｙでない場合、処理をステップＳ１３５に進める。
【０１２６】
（２）ｙ軸がトーラス軸でない場合、実行ノード選択部５４０は、ｙ0＜Ｙ−ｙ＋１であるか否かを判定する。ｙ0＜Ｙ−ｙ＋１である場合、処理をステップＳ１３８に進める。ｙ0＜Ｙ−ｙ＋１でない場合、処理をステップＳ１３５に進める。
【０１２７】
（Ｓ１３５）実行ノード選択部５４０は、ｚ0＋１をｚ0に代入する。実行ノード選択部５４０は、ｙ0に０を代入する。
（Ｓ１３６）実行ノード選択部５４０は、ｚ軸がトーラス軸であるか否かに応じて次の判定を行う。
【０１２８】
（１）ｚ軸がトーラス軸である場合、実行ノード選択部５４０は、ｚ0＜Ｚであるか否かを判定する。ｚ0＜Ｚである場合、処理をステップＳ１３８に進める。ｚ0＜Ｚでない場合、処理をステップＳ１３７に進める。
【０１２９】
（２）ｚ軸がトーラス軸でない場合、実行ノード選択部５４０は、ｚ0＜Ｚ−ｚ＋１であるか否かを判定する。ｚ0＜Ｚ−ｚ＋１である場合、処理をステップＳ１３８に進める。ｚ0＜Ｚ−ｚ＋１でない場合、処理をステップＳ１３７に進める。
【０１３０】
（Ｓ１３７）実行ノード選択部５４０は、判定結果として、Ｎｏを返す。そして、処理を終了する。
（Ｓ１３８）実行ノード選択部５４０は、判定結果として、Ｙｅｓを返す。なお、新たな基点は、この時点での（ｘ0，ｙ0，ｚ0）である。そして、処理を終了する。
【０１３１】
このように、ジョブ割り当ての１つの例として、実行ノード選択部５４０は、１つの計算ノードに対して、１つの計算ノードに対応するビットを、１つずつ確認しながら、ジョブを割り当て可能な部分格子を探索することが考えられる。
【０１３２】
この探索において、実行ノード選択部５４０は、前述の検索用マスクを用いてもよい。そこで、２つ目の比較例では、実行ノード選択部５４０が、１つのビットを１つの計算ノードの空き状況に対応付けたビットマップに対し、検索用マスクを用いてジョブ割り当てを行う例を説明する。
【０１３３】
図１９は、ジョブ割り当ての比較例（その２）を示すフローチャートである。以下、図１９に示す処理をステップ番号に沿って説明する。
（Ｓ１４１）実行ノード選択部５４０は、ジョブの各軸方向のサイズ（ｘ，ｙ，ｚ）を取得する。
【０１３４】
（Ｓ１４２）実行ノード選択部５４０は、割り当て先の基点となる座標（ｙ0，ｚ0）を（０，０）に初期化する。
（Ｓ１４３）実行ノード選択部５４０は、基点座標から割り当て可能であるか否かを判定する。割り当て可能である場合、処理をステップＳ１４４に進める。割り当て不可である場合、処理をステップＳ１４５に進める。ここで、ステップＳ１４３の判定方法の詳細は後述される。
【０１３５】
（Ｓ１４４）実行ノード選択部５４０は、割り当て結果を出力部５３０に出力する。そして、処理を終了する。
（Ｓ１４５）実行ノード選択部５４０は、基点座標を更新可能であるか否かを判定する。更新可能である場合、実行ノード選択部５４０は、基点座標を更新して、処理をステップＳ１４３に進める。更新可能でない場合、処理をステップＳ１４６に進める。ここで、ステップＳ１４５の判定方法の詳細は後述される。
【０１３６】
（Ｓ１４６）実行ノード選択部５４０は、割り当て不可を出力部５３０に出力する。そして、処理を終了する。
図２０は、比較例（その２）の割り当て判定を示すフローチャートである。以下、図２０に示す処理をステップ番号に沿って説明する。以下に示す手順は、図１９のステップＳ１４３の判定処理に相当する。
【０１３７】
（Ｓ１５１）実行ノード選択部５４０は、検索用マスクを初期化する。初期化の方法は、図１２のステップＳ５０と同様である。
（Ｓ１５２）実行ノード選択部５４０は、ｋに０を代入する。
【０１３８】
（Ｓ１５３）実行ノード選択部５４０は、ｊに０を代入する。
（Ｓ１５４）実行ノード選択部５４０は、ｙ座標とｚ座標が（ｙ0＋ｊ，ｚ0＋ｋ）のノード群（計算ノード群）の割り当て情報（ビット列）を取得する。
【０１３９】
（Ｓ１５５）実行ノード選択部５４０は、ステップＳ１５４で取得したビット列と検索用マスクとのＡＮＤ結果が全ビット０であるか否かを判定する。全ビット０である場合、処理をステップＳ１５６に進める。全ビット０でない場合、処理をステップＳ１６１に進める。
【０１４０】
（Ｓ１５６）実行ノード選択部５４０は、ｊ＋１をｊに代入する。
（Ｓ１５７）実行ノード選択部５４０は、ｊ＜ｙであるか否かを判定する。ｊ＜ｙである場合、処理をステップＳ１５４に進める。ｊ＜ｙでない場合、処理をステップＳ１５８に進める。
【０１４１】
（Ｓ１５８）実行ノード選択部５４０は、ｋ＋１をｋに代入する。
（Ｓ１５９）実行ノード選択部５４０は、ｋ＜ｚであるか否かを判定する。ｋ＜ｚである場合、処理をステップＳ１５３に進める。ｋ＜ｚでない場合、処理をステップＳ１６０に進める。
【０１４２】
（Ｓ１６０）実行ノード選択部５４０は、判定結果として、Ｙｅｓを返す。実行ノード選択部５４０は、検索用マスクの位置を割り当てｘ座標とする。そして、処理を終了する。
【０１４３】
（Ｓ１６１）実行ノード選択部５４０は、検索用マスクをシフト（右シフト）可能であるか否かを判定する。シフト可能である場合、実行ノード選択部５４０は、検索用マスクをまとめて右シフトして、処理をステップＳ１５２に進める。右シフトする量は、ステップＳ１５５のＡＮＤ結果を最下位ビットからみて最初に１が出現する桁から、検索用マスクの連続する１の最上位の桁までカウントした数である。シフト不可能である場合、処理をステップＳ１６２に進める。
【０１４４】
（Ｓ１６２）実行ノード選択部５４０は、判定結果として、Ｎｏを返す。そして、処理を終了する。
なお、ステップＳ１５４では、トーラス軸を考慮する場合、ｙ座標とｚ座標が（（ｙ0＋ｊ）％Ｙ，（ｚ0＋ｋ）％Ｚ）に対応する計算ノード群の割り当て情報を取得することが考えられる。
【０１４５】
図２１は、検索用マスクを用いた割り当て判定の例を示す図である。ここでは、ｘ＝４、Ｘ＝１２の場合を例示する。検索用マスクは、初期化直後では、１１１１００００００００である。また、（ｙ0＋ｊ，ｚ0＋ｋ）に対する割り当て情報に相当するビット列が、１１１０１１００１０００であるとする。ここで、当該ビット列の最上位ビットがｘ＝０に対応し、最下位ビットがｘ＝Ｘ−１に対応する。また、ノードの使用状態について、１が使用中であることを示し、０が使用中でないことを示す。
【０１４６】
検索用マスクと割り当て情報とをＡＮＤ処理した結果（ＡＮＤ結果）は、１１１０００００００００となる（同じ桁のビットが両方１のときＡＮＤ結果の該当桁も１、それ以外ではＡＮＤ結果の該当桁は０）。この場合、ＡＮＤ結果のビット列１１１０００００００００の下から見て最初に１が出現する位置まで割り当て不可なので、実行ノード選択部５４０は、検索用マスクを、まとめて（この場合、３ビット分）右シフトする。その結果、検索用マスクは、０００１１１１０００００となる。そして、実行ノード選択部５４０は、上記の手順を繰り返す。
【０１４７】
ここで、検索用マスクのシフトに関して、ｘ軸がトーラス軸のとき、一番左の１が検索用マスクの一番右の桁からあふれる場合にシフト不可であり、それ以外の場合にシフト可能である（トーラス軸の場合は右ローテートとなる）。また、ｘ軸がトーラス軸でないとき、一番右の１が検索用マスクの一番右の桁からあふれる場合にシフト不可であり、それ以外の場合にシフト可能である。
【０１４８】
なお、図２１の例は、図１２のステップＳ５０〜Ｓ５２の手順の例として捉えることもできる。図１２のステップＳ５０〜Ｓ５２の手順の例として捉える場合、上記の「割り当て情報」を、図１２の手順における「入力ビット列」と読み替えればよい。
【０１４９】
図２２は、比較例（その２）の基点座標更新判定を示すフローチャートである。以下、図２２に示す処理をステップ番号に沿って説明する。以下に示す手順は、図１９のステップＳ１４５に相当する。
【０１５０】
（Ｓ１７１）実行ノード選択部５４０は、ｙ0＋１をｙ0に代入する。
（Ｓ１７２）実行ノード選択部５４０は、ｙ軸がトーラス軸であるか否かに応じて次の判定を行う。
【０１５１】
（１）ｙ軸がトーラス軸である場合、実行ノード選択部５４０は、ｙ0＜Ｙであるか否かを判定する。ｙ0＜Ｙである場合、処理をステップＳ１７６に進める。ｙ0＜Ｙでない場合、処理をステップＳ１７３に進める。
【０１５２】
（２）ｙ軸がトーラス軸でない場合、実行ノード選択部５４０は、ｙ0＜Ｙ−ｙ＋１であるか否かを判定する。ｙ0＜Ｙ−ｙ＋１である場合、処理をステップＳ１７６に進める。ｙ0＜Ｙ−ｙ＋１でない場合、処理をステップＳ１７３に進める。
【０１５３】
（Ｓ１７３）実行ノード選択部５４０は、ｚ0＋１をｚ0に代入する。実行ノード選択部５４０は、ｙ0に０を代入する。
（Ｓ１７４）実行ノード選択部５４０は、ｚ軸がトーラス軸であるか否かに応じて次の判定を行う。
【０１５４】
（１）ｚ軸がトーラス軸である場合、実行ノード選択部５４０は、ｚ0＜Ｚであるか否かを判定する。ｚ0＜Ｚである場合、処理をステップＳ１７６に進める。ｚ0＜Ｚでない場合、処理をステップＳ１７５に進める。
【０１５５】
（２）ｚ軸がトーラス軸でない場合、実行ノード選択部５４０は、ｚ0＜Ｚ−ｚ＋１であるか否かを判定する。ｚ0＜Ｚ−ｚ＋１である場合、処理をステップＳ１７６に進める。ｚ0＜Ｚ−ｚ＋１でない場合、処理をステップＳ１７５に進める。
【０１５６】
（Ｓ１７５）実行ノード選択部５４０は、判定結果として、Ｎｏを返す。そして、処理を終了する。
（Ｓ１７６）実行ノード選択部５４０は、判定結果として、Ｙｅｓを返す。なお、新たな基点のｙ座標およびｚ座標は、この時点での（ｙ0，ｚ0）である。そして、処理を終了する。
【０１５７】
このように、実行ノード選択部５４０は、検索用マスクを用いることで、１つ目の比較例よりも演算のステップ数を削減し得る。しかし、２つの比較例の何れを用いても、並列処理システム５０の規模が大きくなるほど、計算ノード数の増加度合い以上に、計算ノードの選択にかかる時間が長くなってしまう。具体的には次の通りである。
【０１５８】
図２３は、計算ノード数に対する所要ステップ数の比較例を示す図である。図２３では、Ｘ，Ｙ，Ｚおよび全体の計算ノード数Ｎ（＝ＸＹＺ）に対して、比較例（その１）、比較例（その２）および第２の実施の形態によるジョブ割り当てに伴う所要ステップ数を示している。
【０１５９】
ここで、比較例（その１）の所要ステップ数は、比較例（その１）の手順のうち、図１７のステップＳ１１４が実行される回数に相当する。また、比較例（その２）の所要ステップ数は、比較例（その２）の手順のうち、図２０のステップＳ１５５が実行される回数に相当する。また、第２の実施の形態における所要ステップ数は、図１４で示した前処理と割り当て可否判定との所要ステップ数の合計である。
【０１６０】
図２３によれば、比較例（その１）および比較例（その２）の方法では、計算ノード数が増えるほど、所要ステップ数が著しく増えることが分かる。一方、第２の実施の形態の制御ノード１００によるジョブ割り当て方法によれば、計算ノード数の増加に対する所要ステップ数の増加は、２つの比較例に比べて緩やかである。また、制御ノード１００によるジョブ割り当て方法によれば、２つの比較例に比べて、所要ステップ数が少なくて済み、ジョブを割り当てる計算ノードの選択を高速に行える。特に、計算ノード数が多いほど、制御ノード１００によるジョブ割り当て方法は有用である。
【０１６１】
また、ジョブ実行時のノード選択を高速化することで、ジョブの実行待ちの時間を減らし、並列処理システム５０における各計算ノードの稼働率を向上できる。
なお、上記の例では、制御ノード１００は、主に、ｙ軸およびｚ軸方向のサイズが２の冪である領域ごとに、当該領域に対応する計算ノード群の空きノード情報を取得するものとした。一方、当該領域のｙ軸およびｚ軸方向のサイズは、３以上の整数の冪であってもよい。制御ノード１００は、計算ノードの数に応じて、当該サイズを２以上の何れの整数の冪とするかを決定してもよい。例えば、計算ノードの数が多いほど、大きな整数の冪とすることで、計算ノードの選択を高速化することも考えられる。
【０１６２】
また、上記の例では、主に、３次元の格子状のネットワークを例示して説明したが、前述のように、各計算ノードは２次元または４次元以上の格子状のネットワークにより接続されてもよい。
【０１６３】
更に、第１の実施の形態の情報処理は、処理部１２にプログラムを実行させることで実現できる。また、第２の実施の形態の情報処理は、プロセッサ１０１にプログラムを実行させることで実現できる。プログラムは、コンピュータ読み取り可能な記録媒体３３に記録できる。
【０１６４】
例えば、プログラムを記録した記録媒体３３を配布することで、プログラムを流通させることができる。また、プログラムを他のコンピュータに格納しておき、ネットワーク経由でプログラムを配布してもよい。コンピュータは、例えば、記録媒体３３に記録されたプログラムまたは他のコンピュータから受信したプログラムを、ＲＡＭ１０２やＨＤＤ１０３などの記憶装置に格納し（インストールし）、当該記憶装置からプログラムを読み込んで実行してもよい。
【符号の説明】
【０１６５】
１  並列処理装置
２  ネットワーク
３  ジョブ
４  空きノード情報
１０  制御ノード
１１  記憶部
１２  処理部
２０  計算ノード群
２１，２２，２３，２４  計算ノード
【図１】
2018092328.tif 000003
【図２】
2018092328.tif 000004
【図３】
2018092328.tif 000005
【図４】
2018092328.tif 000006
【図５】
2018092328.tif 000007
【図６】
2018092328.tif 000008
【図７】
2018092328.tif 000009
【図８】
2018092328.tif 000010
【図９】
2018092328.tif 000011
【図１０】
2018092328.tif 000012
【図１１】
2018092328.tif 000013
【図１２】
2018092328.tif 000014
【図１３】
2018092328.tif 000015
【図１４】
2018092328.tif 000016
【図１５】
2018092328.tif 000017
【図１６】
2018092328.tif 000018
【図１７】
2018092328.tif 000019
【図１８】
2018092328.tif 000020
【図１９】
2018092328.tif 000021
【図２０】
2018092328.tif 000022
【図２１】
2018092328.tif 000023
【図２２】
2018092328.tif 000024
【図２３】
2018092328.tif 000025