(57)【特許請求の範囲】
【請求項１】
並列計算を行う複数の計算ノードと、
ジョブを管理するジョブ管理ノードとを有し、
前記ジョブ管理ノードは、
前記複数の計算ノードのいずれかで実行されている複数のジョブから第１ジョブを選択し、
前記第１ジョブを実行している第１計算ノードが占有する第１領域に隣接すると共に、いずれのジョブも実行していない空き計算ノードが占有する第２領域を探索し、
前記第１領域と前記第２領域とを合わせた第３領域内の所定方向の端に接する位置に、前記第１領域と同じサイズの第４領域を決定し、
前記第３領域内の前記第４領域と重複しない範囲に、所定形状の第５領域を決定し、
前記第５領域に含まれる第３計算ノードで、新規に投入する第２ジョブを実行できるかどうかを判定し、
前記第２ジョブを実行できると判定した場合、前記第１計算ノードに対して、前記第４領域内の第２計算ノードへの前記第１ジョブのマイグレーションを指示すると共に、前記第３計算ノードに対し、前記第２ジョブの実行を指示する、
並列計算システム。
【請求項２】
前記ジョブ管理ノードは、前記探索時に、前記第１計算ノードに対して、前記第２領域の探索を指示し、
前記第１計算ノードは、隣接するノードへ、前記空き計算ノード探索用の第１データを送信し、
前記空き計算ノードは、前記第１データを受信すると、前記第１データ内の第１カウンタの値をカウントアップして、前記第１データを、前記第１計算ノードがある方向と反対側に隣接する計算ノードへ転送し、
前記複数の計算ノードのうちの、いずれかのジョブを実行している使用中ノードは、前記第１データを受信すると、前記第１データを前記第１計算ノードに送り返し、
前記第１計算ノードは、送り返された前記第１データ内の前記第１カウンタの値に基づいて前記第２領域の範囲を把握し、把握した前記第２領域の範囲を前記ジョブ管理ノードに送信する、
請求項１記載の並列計算システム。
【請求項３】
前記第１計算ノードは、前記第１データが送り返されると、前記第１データの転送経路上の中継空き計算ノードへ、別方向の空きノード探索用の第２データを送信し、
前記中継空き計算ノードは、前記第２データを受信すると、前記第２データを、前記第１計算ノードがある方向および該方向の反対側以外の方向に隣接する計算ノードへ転送し、
前記空き計算ノードは、前記第２データを受信すると、前記第２データ内の第２カウンタの値をカウントアップして、前記第２データを、前記中継空き計算ノードがある方向と反対側に隣接する計算ノードへ転送し、
前記使用中ノードは、前記第２データを受信すると、前記第２データを前記第１計算ノードに送り返し、
前記第１計算ノードは、送り返された前記第１データおよび前記第２データ内の前記第１カウンタおよび前記第２カウンタの値に基づいて前記第２領域の範囲を把握し、把握した前記第２領域の範囲を示す情報を前記ジョブ管理ノードに送信する、
請求項２記載の並列計算システム。
【請求項４】
前記ジョブ管理ノードは、前記第４領域の決定の際に、前記第３領域に隣接する計算ノードで実行されている周辺ジョブそれぞれについての、処理が終了するまでの時間を示す終了予定時間に基づいて、前記第４領域を決定する、
請求項１乃至３のいずれかに記載の並列計算システム。
【請求項５】
前記ジョブ管理ノードは、前記第４領域および前記第５領域の決定の際に、前記第１ジョブの終了予定時間と前記第２ジョブの終了予定時間とを比較し、比較結果と、前記周辺ジョブそれぞれについての終了予定時間とに基づいて、前記第４領域と前記第５領域とを決定する、
請求項４記載の並列計算システム。
【請求項６】
前記ジョブ管理ノードは、前記マイグレーションの指示の際に、前記第１計算ノードの性能と前記第２計算ノードの性能とを比較し、前記第２計算ノードの性能が、前記第１計算ノードの性能に所定値を乗算した値以上である場合に限り、前記マイグレーションの指示を行う、
請求項１乃至５のいずれかに記載の並列計算システム。
【請求項７】
複数の計算ノードを有する並列計算システム内の１ノードとして用いられるジョブ管理装置であって、
前記複数の計算ノードと通信する通信インタフェースと、
前記通信インタフェースを介して、前記複数の計算ノードにジョブのマイグレーションを指示する演算部とを有し、
前記演算部は、
前記複数の計算ノードのいずれかで実行されている複数のジョブから第１ジョブを選択し、
前記第１ジョブを実行している第１計算ノードが占有する第１領域に隣接すると共に、いずれのジョブも実行していない空き計算ノードが占有する第２領域を探索し、
前記第１領域と前記第２領域とを合わせた第３領域内の所定方向の端に接する位置に、前記第１領域と同じサイズの第４領域を決定し、
前記第３領域内の前記第４領域と重複しない範囲に、所定形状の第５領域を決定し、
前記第５領域に含まれる第３計算ノードで、新規に投入する第２ジョブを実行できるかどうかを判定し、
前記第２ジョブを実行できると判定した場合、前記第１計算ノードに対して、前記第４領域内の第２計算ノードへの前記第１ジョブのマイグレーションを指示すると共に、前記第３計算ノードに対し、前記第２ジョブの実行を指示する、
ジョブ管理装置。
【請求項８】
複数の計算ノードを有する並列計算システム内の１ノードとして用いられるコンピュータに、
前記複数の計算ノードのいずれかで実行されている複数のジョブから第１ジョブを選択し、
前記第１ジョブを実行している第１計算ノードが占有する第１領域に隣接すると共に、いずれのジョブも実行していない空き計算ノードが占有する第２領域を探索し、
前記第１領域と前記第２領域とを合わせた第３領域内の所定方向の端に接する位置に、前記第１領域と同じサイズの第４領域を決定し、
前記第３領域内の前記第４領域と重複しない範囲に、所定形状の第５領域を決定し、
前記第５領域に含まれる第３計算ノードで、新規に投入する第２ジョブを実行できるかどうかを判定し、
前記第２ジョブを実行できると判定した場合、前記第１計算ノードに対して、前記第４領域内の第２計算ノードへの前記第１ジョブのマイグレーションを指示すると共に、前記第３計算ノードに対し、前記第２ジョブの実行を指示する、
処理を実行させるジョブ管理プログラム。
【請求項９】
複数の計算ノードを有する並列計算システム内の１ノードとして用いられるコンピュータが、
前記複数の計算ノードのいずれかで実行されている複数のジョブから第１ジョブを選択し、
前記第１ジョブを実行している第１計算ノードが占有する第１領域に隣接すると共に、いずれのジョブも実行していない空き計算ノードが占有する第２領域を探索し、
前記第１領域と前記第２領域とを合わせた第３領域内の所定方向の端に接する位置に、前記第１領域と同じサイズの第４領域を決定し、
前記第３領域内の前記第４領域と重複しない範囲に、所定形状の第５領域を決定し、
前記第５領域に含まれる第３計算ノードで、新規に投入する第２ジョブを実行できるかどうかを判定し、
前記第２ジョブを実行できると判定した場合、前記第１計算ノードに対して、前記第４領域内の第２計算ノードへの前記第１ジョブのマイグレーションを指示すると共に、前記第３計算ノードに対し、前記第２ジョブの実行を指示する、
ジョブ管理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、並列計算システム、ジョブ管理装置、ジョブ管理プログラム、およびジョブ管理方法に関する。
【背景技術】
【０００２】
大規模なコンピュータシステムでは、システム全体を効率的に運用することが重要である。一般的には、ジョブスケジューラが時間的・空間的に考慮して、ジョブに、そのジョブを実行するノードを割り当てる。ジョブは、割り当てられたノードで実行される。なおジョブスケジューラとは、コンピュータシステムで実行させるジョブを管理するソフトウェアである。例えばジョブスケジューラは、ジョブへのノードの割り当て以外にも、複数のジョブ（プログラム、バッチ処理）の起動や終了を制御したり、ジョブの実行・終了状態の監視・報告をしたりする。
【０００３】
ジョブに複数のノードを割り当てる場合、ジョブを実行するノード間の通信が効率的に行えるように、できるだけ隣接したノードが割り当てられる。例えばシステムがメッシュまたはトーラス接続のネットワークである場合、ネットワーク内にサブメッシュ（２次元であれば長方形領域、３次元であれば直方体領域）が設定される。そして１つのジョブに対して、サブメッシュ内の空きノードが割り当てられる。空きノードとは、ジョブを実行していないノードである。
【０００４】
ただし、ネットワーク全体としてジョブの実行に用いるノード数分の空きノードがあっても、該当ノード数分のノードを包含するサブメッシュを確保できない場合がある。その要因の１つに、空きノードがフラグメンテーション状態となることがある。フラグメンテーション状態とは、使用中のノードと空きノードとが虫食い状態で配置されることである。例えば、時間の推移の中でジョブ実行完了時間の読み間違いなどでシステムのフラグメンテーション状態となる。フラグメンテーション状態になると、システムの使用効率が低下し、スループットが悪化する。
【０００５】
ジョブの使用効率を向上させる技術としては、例えば、計測データと解析データに基づいて、所定時間後のシステム稼働状況を予測し、その予測結果に基づいて最適ジョブ実行環境の設定を行う技術がある。また並列計算機システムにおいて、ジョブ実行に伴うスケジューリング誤差を削減し、計算機資源の利用効率を向上させる技術もある。さらに、応答時間の乱高下を抑止する技術も考えられている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開平７−２１９７８７号公報
【特許文献２】特開２００２−７３６４号公報
【特許文献３】特開２０１４−４９１１２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
空きノードがフラグメンテーション状態となっているために纏まった空きノード群が見つからない場合、例えばジョブマイグレーションによって、纏まった空きノード群を生成することが考えられる。ジョブマイグレーションは、あるノードで実行されているジョブを、他のノードに移動させる技術である。ジョブマイグレーションで纏まった空きノード群を生成するには、ジョブの移動先として、フラグメンテーションが解消できるような空きノードの探索が行われる。
【０００８】
しかし、大規模なシステムでは、ジョブの移動先をシステム全体から探すとなると、探索範囲が膨大となる。例えば、単純に全体の最適解を考えてどのジョブをどこへ移動させればよいかを探すと組合せ数が爆発し、計算時間が膨大となる。そのため、リアルタイムに処理できないという問題がある。
【０００９】
１つの側面では、本件は、纏まった空きノード群を迅速に作り出すことを目的とする。
【課題を解決するための手段】
【００１０】
１つの案では、並列計算を行う複数の計算ノードとジョブを管理するジョブ管理ノードとを有する並列計算システムが提供される。ジョブ管理ノードは、複数の計算ノードのいずれかで実行されている複数のジョブから第１ジョブを選択する。次にジョブ管理ノードは、第１ジョブを実行している第１計算ノードが占有する第１領域に隣接すると共に、いずれのジョブも実行していない空き計算ノードが占有する第２領域を探索する。次にジョブ管理ノードは、第１領域と第２領域とを合わせた第３領域内の所定方向の端に接する位置に、第１領域と同じサイズの第４領域を決定する。次にジョブ管理ノードは、第３領域内の第４領域と重複しない範囲に、所定形状の第５領域を決定する。次にジョブ管理ノードは、第５領域に含まれる第３計算ノードで、新規に投入する第２ジョブを実行できるかどうかを判定する。そしてジョブ管理ノードは、第２ジョブを実行できると判定した場合、第１計算ノードに対して、第４領域内の第２計算ノードへの第１ジョブのマイグレーションを指示すると共に、第３計算ノードに対し、第２ジョブの実行を指示する。
【発明の効果】
【００１１】
１態様によれば、纏まった空きノード群を迅速に作り出すことができる。
【図面の簡単な説明】
【００１２】
【図１】第１の実施の形態に係る並列計算システムの一例を示す図である。
【図２】並列計算システムの構成例を示す図である。
【図３】本実施の形態に用いる制御ノードのハードウェアの一構成例を示す図である。
【図４】各ノードが有する機能を示すブロック図である。
【図５】ジョブの再配置を伴うジョブ投入処理の手順の一例を示す図である。
【図６】空き領域把握処理の一例を示す図である。
【図７】転送データの一例を示す図である。
【図８】仮探索枠内の未探索領域の一例を示す図である。
【図９】未探索領域用転送データの一例を示す図である。
【図１０】移動可能領域の一例を示す図である。
【図１１】移動候補ジョブを移動後のジョブ投入可能領域の一例を示す図である。
【図１２】ジョブ再配置指示の処理手順の一例を示す図である。
【図１３】第３の実施形態におけるジョブマイグレーションの一例を示す図である。
【図１４】終了予定時間が最も長いジョブの位置に応じた移動先の例を示す図である。
【図１５】第３の実施の形態におけるジョブ移動処理手順の一例を示す図である。
【図１６】周辺ジョブ情報の一例を示す図である。
【図１７】新規ジョブと移動候補ジョブとの終了予定時間の比較結果のパターンを示す図である。
【図１８】第４の実施の形態におけるジョブ移動処理の一例を示す図である。
【図１９】第４の実施の形態におけるジョブ投入可能領域の一例を示す図である。
【図２０】ジョブ挿入可能領域の配置例を示す図である。
【図２１】「選択行動Ｉ」の処理手順の一例を示すフローチャートである。
【図２２】「選択行動ＩＩ」の処理手順の一例を示すフローチャートである。
【図２３】終了時間最大ジョブ選択処理の手順の一例を示すフローチャートである。
【図２４】移動ジョブ配置可能領域内の移動候補ジョブの配置例を示す図である。
【図２５】移動候補ジョブ移動処理の手順の一例を示すフローチャートである。
【発明を実施するための形態】
【００１３】
以下、本実施の形態について図面を参照して説明する。なお各実施の形態は、矛盾のない範囲で複数の実施の形態を組み合わせて実施することができる。
〔第１の実施の形態〕
図１は、第１の実施の形態に係る並列計算システムの一例を示す図である。第１の実施の形態に係る並列計算システムには、複数の計算ノード１とジョブ管理ノード１０とが含まれる。
【００１４】
複数の計算ノード１は、例えばメッシュまたはトーラス接続のネットワークを構成するコンピュータである。複数の計算ノード１間は、例えば高速のインターコネクトで接続されている。複数の計算ノード１内の各計算ノードがジョブを実行する。ジョブには、複数の計算ノードが連携して実行する並列ジョブが含まれる。並列ジョブを実行する場合、そのジョブに、ジョブを実行するための複数の計算ノードが割り当てられる。並列ジョブを実行する複数の計算ノードは、ジョブの実行過程で互いにデータを送受信する。並列ジョブを実行する計算ノード間の通信において、他のジョブを実行している計算ノードによる中継が行われると、他のジョブの影響により、並列ジョブの処理速度が低下する可能性がある。このような事態の発生を抑止するため、１つの並列ジョブに割り当てられる複数の計算ノードは、所定形状の纏まった１つの領域から選ばれる。例えばｎ次元（ｎは２以上の整数）のメッシュまたはトーラス接続のネットワークのとき、ｎ次の各軸方向の範囲の指定により領域が特定されるサブメッシュが生成され、並列ジョブに対しては、同じサブメッシュ内の計算ノードが割り当てられる。２次元に接続されたネットワークであれば、サブメッシュは長方形であり、３次元に接続されたネットワークであれば、サブメッシュは直方体である。
【００１５】
ジョブ管理ノード１０は、ジョブを管理する装置（ジョブ管理装置）であり、例えばコンピュータである。ジョブ管理ノード１０は、通信インタフェース１１と演算部１２とを有する。通信インタフェース１１は、複数の計算ノード１と通信する。演算部１２は、通信インタフェース１１を介して、複数の計算ノード１に実行させるジョブを管理する。
【００１６】
例えば演算部１２は、ジョブに対する計算ノードの割り当て、割り当てた計算ノードへのジョブの実行指示を行う。また演算部１２は、複数の計算ノード１に対して、ジョブのマイグレーションの指示も行う。例えば演算部１２は、ジョブを実行していない空き計算ノードを、１つの領域に纏めるため、ジョブのマイグレーションを指示する。例えば、新規に投入するジョブを実行するのに十分な計算ノードを含むサブメッシュをネットワーク内で生成できない場合がある。この場合、演算部１２は、ジョブをマイグレーションによって移動させ、十分なサイズのサブメッシュを生成できるような空き計算ノードの領域を生成する。具体的には、以下の通りである。
【００１７】
演算部１２は、まず、複数の計算ノード１のいずれかで実行されている複数のジョブから第１ジョブ（ＪｏｂＭＶ）を選択する（ステップＳ１）。次に演算部１２は、第１ジョブを実行している第１計算ノード１ａが占有する第１領域２に隣接すると共に、いずれのジョブも実行していない空き計算ノードが占有する第２領域３を探索する（ステップＳ２）。ここで、第１領域２と第２領域３とを合わせた領域を、第３領域４とする。
【００１８】
次に演算部１２は、第３領域４内の所定方向の端に接する位置に、第１領域２と同じサイズの第４領域５を決定する（ステップＳ３）。例えば演算部１２は、第１領域２を平行移動することで得られる領域を、第４領域５とする。この場合、第１領域２と第４領域５とは、サイズと形状とが同じ、すなわち合同である。
【００１９】
次に演算部１２は、第３領域４内の第４領域５と重複しない範囲に、所定形状の第５領域６を決定する（ステップＳ４）。第５領域６は、２次元であれば長方形、３次元であれば直方体のサブメッシュである。例えば演算部１２は、第３領域４内の第４領域５を除外した範囲に生成できる最大のサブメッシュを、第５領域６とする。
【００２０】
次に演算部１２は、第５領域６に含まれる第３計算ノード１ｃで、新規に投入する第２ジョブ（ＪｏｂＮＥＷ）を実行できるかどうかを判定する（ステップＳ５）。例えば演算部１２は、第５領域６に含まれる第３計算ノード１ｃの数が、第２ジョブの実行に使用する計算ノード数以上であれば、実行できると判定する。
【００２１】
第２ジョブを実行できると判定した場合、演算部１２は、第１計算ノード１ａに対して、第４領域５内の第２計算ノード１ｂへの第１ジョブのマイグレーションを指示する（ステップＳ６）。また演算部１２は、第３計算ノード１ｃに対し、第２ジョブの実行を指示する（ステップＳ７）。
【００２２】
なお、第５領域６に含まれる第３計算ノード１ｃで第２ジョブを実行できない場合、実行中の他のジョブが第１ジョブとして選択され、同様の処理が繰り返される。
これにより、第２ジョブを実行するのに十分なサイズの第５領域６が生成され、第２ジョブを実行させることができる。例えば図１の例では、第２ジョブの実行に、６台の計算ノードが用いられる。第１ジョブのマイグレーション前の状態では、６台以上の空き計算ノードが存在するものの、長方形の領域内に纏まっていない。そのため第１ジョブを移動させずに、第２ジョブを実行させることができない。図１の例では、第１ジョブを、Ｘ軸、Ｙ軸それぞれの負の方向の隅に設けた第４領域内の計算ノードに移動すれば、６台の計算ノードを含む長方形の第５領域６が生成可能となる。そこで第１ジョブが第４領域５内の計算ノードにマイグレーションで移動され、その結果として生じた第５領域６内の計算ノードで、第２ジョブが実行される。
【００２３】
このように、第１の実施の形態では、１つのジョブを周辺の空き計算ノードに移動させるだけで、新規に投入するジョブを実行するための十分な空き計算ノードを有する領域が生成できる。移動が１つのジョブに限定され、空き計算ノードの探索範囲が、そのジョブを実行している計算ノードの周囲に限定されるため、非常に高速に処理を行うことができる。例えば大規模なシステムにおいて、複数の計算ノード１全体に対するジョブの再配置を行って、纏まった空き領域を生成したのでは、非常に時間がかかる。それに対し、１つのジョブ周辺に限定した探索と、１つのジョブの移動だけであれば、非常に高速に行うことができる。
【００２４】
なお、演算部１２は、第１計算ノード１ａを利用して、第２領域３の探索を行うこともできる。例えば演算部１２は、第１計算ノード１ａに対して、第２領域３の探索を指示する。指示を受けた第１計算ノード１ａは、隣接するノードへ、空き計算ノード探索用の第１データを送信する。空き計算ノードは、第１データを受信すると、第１データ内の第１カウンタの値をカウントアップして、第１データを、第１計算ノードがある方向と反対側に隣接する計算ノードへ転送する。例えば空き計算ノードが、第１データをＸ軸の負の方向に隣接する計算ノードから取得した場合、第１カウンタの値が更新された第１データが、Ｘ軸の正の方向に隣接する計算ノードに転送される。複数の計算ノード１のうちの、いずれかのジョブを実行している使用中ノードは、第１データを受信すると、第１データを第１計算ノードに送り返す。第１計算ノード１ａは、送り返された第１データ内の第１カウンタの値に基づいて第２領域３の範囲を把握し、把握した第２領域３の範囲を示す情報をジョブ管理ノード１０に送信する。例えば送り返されたときの第１カウンタの値が「２」であれば、第１データを送信した方向に２台分の空き計算ノードが存在することが理解できる。
【００２５】
これにより、例えば第１領域２のＸ軸方向またはＹ軸方向の空間に空き計算ノードがどこまで続くかを把握できる。第１領域２をＸ軸方向またはＹ軸方向に平行移動させたときの位置を第４領域５とすれば、新規に投入する第２ジョブを実行可能となるのであれば、第２領域３の探索をこの段階でとどめてもよい。第１領域２をＸ軸方向およびＹ軸方向に平行移動させたときの位置を第４領域５とすることも考慮にいれるのであれば、さらに以下の探索を行うことができる。
【００２６】
第１計算ノード１ａは、第１データが送り返されると、第１データの転送経路上の中継空き計算ノードへ、別方向の空きノード探索用の第２データを送信する。中継空き計算ノードは、第２データを受信すると、第２データを、第１計算ノード１ａがある方向および該方向の反対側以外の方向に隣接する計算ノードへ転送する。例えば中継空き計算ノードが、第２データを、Ｘ軸の負の方向に隣接する計算ノードから取得した場合、第２データが、Ｙ軸の正の方向、負の方向それぞれに隣接する計算ノードの両方に転送される。空き計算ノードは、第２データを受信すると、第２データ内の第２カウンタの値をカウントアップして、第２データを、中継空き計算ノードがある方向と反対側に隣接する計算ノードへ転送する。例えば空き計算ノードが、第２データをＹ軸の負の方向に隣接する計算ノードから取得した場合、第２カウンタの値が更新された第２データが、Ｙ軸の正の方向に隣接する計算ノードに転送される。使用中ノードは、第２データを受信すると、第２データを第１計算ノード１ａに送り返す。第１計算ノード１ａは、送り返された第１データおよび第２データ内の第１カウンタおよび第２カウンタの値に基づいて第２領域３の範囲を把握し、把握した第２領域３の範囲をジョブ管理ノード１０に送信する。例えば送り返されたときの第１カウンタの値が「２」であれば、第１データを送信した方向（例えばＸ軸方向）に２台分の空き計算ノードが存在することが理解できる。そしてある空き計算ノードで中継された第２カウンタの値が「２」であれば、その空きノードから第２データを送信した方向（例えばＹ軸方向）に２台分の空き計算ノードが存在することが理解できる。
【００２７】
このように、第１計算ノード１ａに、第１データおよび第２データを送信させることで、第２領域３を探索し、探索処理を複数の計算ノードで分散して行うことができ、処理の効率化を図ることができる。
【００２８】
また演算部１２は、第４領域５の決定の際に、第３領域４に隣接する計算ノードで実行されている周辺ジョブそれぞれについての、処理が終了するまでの時間を示す終了予定時間に基づいて、第４領域５を決定することもできる。例えば、終了予定時間が最も長い周辺ジョブを実行している計算ノードに隣接する位置に、第４領域５が決定される。これにより、例えば終了予定時間が短いジョブを実行している計算ノードの周辺に空きノードとしておくことができ、そのジョブの実行が終了することで、広い範囲で空きノードの集合する領域を生成することができる。その結果、次に実行するジョブを投入しやすくなる。
【００２９】
さらに演算部１２は、第４領域５および第５領域６の決定の際に、第１ジョブの終了予定時間と第２ジョブの終了予定時間とを比較し、比較結果と、周辺ジョブそれぞれについての終了予定時間とに基づいて、第４領域５と第５領域６とを決定することもできる。例えば、第１ジョブの終了予定時間の方が第２ジョブの終了予定時間より長ければ、第１ジョブを実行する計算ノードを含む第４領域５が、周辺ジョブの中で最も終了予定時間が長いジョブを実行している計算ノードに隣接する位置に決定される。また、第２ジョブの終了予定時間の方が第１ジョブの終了予定時間より長ければ、第２ジョブを実行する計算ノードを含む第５領域６が、周辺ジョブの中で最も終了予定時間が長いジョブを実行している計算ノードに隣接する位置に決定される。これにより、例えば終了予定時間が短いジョブを実行している計算ノードの周辺に空きノードとしておくことができ、そのジョブの実行が終了することで、広い範囲で空きノードの集合する領域を生成することができる。
【００３０】
さらに演算部１２は、マイグレーションの指示の際に、第１計算ノード１ａの性能と第２計算ノード１ｂの性能とを比較し、第２計算ノード１ｂの性能が、第１計算ノード１ａの性能に所定値を乗算した値以上である場合に限り、マイグレーションの指示を行うようにすることもできる。例えば、所定値を「１」とすれば、第２計算ノード１ｂの性能が第１計算ノード１ａの性能以上の場合に限り、マイグレーションが行われることとなる。これにより、第１ジョブを移動させたことにより、第１ジョブのスループットが低下することを抑止できる。
【００３１】
なお、演算部１２は、例えばジョブ管理ノード１０が有するプロセッサにより実現することができる。また、図１に示した各要素間を接続する線は通信経路の一部を示すものであり、図示した通信経路以外の通信経路も設定可能である。
【００３２】
〔第２の実施の形態〕
次に第２の実施の形態について説明する。第２の実施の形態は、メッシュまたはトーラス接続された計算ノード群を用いた並列計算システムである。
【００３３】
図２は、並列計算システムの構成例を示す図である。制御ノード１００が、ネットワーク２０を介して計算ノード群２００内の計算ノード２１０−１，２１０−２，２１０−３，・・・に接続されている。制御ノード１００は、計算ノード群２００で構成されたＨＰＣ（High Performance Computing）システムを制御するコンピュータである。計算ノード群２００に含まれる各計算ノード２１０−１，２１０−２，２１０−３，・・・は、制御ノード１００からの指示に従ってジョブを実行するコンピュータである。計算ノード２１０−１，２１０−２，２１０−３，・・・には、計算のみを実行する単純計算ノードとＩＯ（Input/Output）処理と計算処理を担うＩＯノードとがある。一般的に全システム中のＩＯノードの数は、単純計算ノードに比べて少ない。
【００３４】
制御ノード１００は、計算ノード群２００内の１以上の計算ノードをジョブに割り当て、そのジョブの実行指示を、割り当てた計算ノードに送信する。また制御ノード１００は、ジョブの実行途中で、そのジョブを割り当てる計算ノードを変更できる。その場合、制御ノード１００は、ジョブを実行するタスクを、マイグレーションにより移動させる。ジョブのマイグレーションを行う場合、そのジョブのデータが、移行元の計算ノードから移行先の計算ノードに転送される。
【００３５】
計算ノード群２００内の各計算ノード２１０−１，２１０−２，２１０−３，・・・は、メッシュまたはトーラス接続でネットワークが組まれている。メッシュ接続の場合、計算ノード２１０−１，２１０−２，２１０−３，・・・が、ｎ次元（ｎは２以上の整数）の各軸方向に、並べられている。各計算ノード２１０−１，２１０−２，２１０−３，・・・は、各軸方向に隣接する他の計算ノードと高速のインターコネクトで接続されている。トーラス接続の場合、各軸方向の両端の計算ノード同士も、インターコネクトで接続されている。
【００３６】
図３は、本実施の形態に用いる制御ノードのハードウェアの一構成例を示す図である。制御ノード１００は、プロセッサ１０１によって装置全体が制御されている。プロセッサ１０１には、バス１０９を介してメモリ１０２と複数の周辺機器が接続されている。プロセッサ１０１は、マルチプロセッサであってもよい。プロセッサ１０１は、例えばＣＰＵ（Central Processing Unit）、ＭＰＵ（Micro Processing Unit）、またはＤＳＰ（Digital Signal Processor）である。プロセッサ１０１がプログラムを実行することで実現する機能の少なくとも一部を、ＡＳＩＣ（Application Specific Integrated Circuit）、ＰＬＤ（Programmable Logic Device）などの電子回路で実現してもよい。
【００３７】
メモリ１０２は、制御ノード１００の主記憶装置として使用される。メモリ１０２には、プロセッサ１０１に実行させるＯＳ（Operating System）のプログラムやアプリケーションプログラムの少なくとも一部が一時的に格納される。また、メモリ１０２には、プロセッサ１０１による処理に利用する各種データが格納される。メモリ１０２としては、例えばＲＡＭ（Random Access Memory）などの揮発性の半導体記憶装置が使用される。
【００３８】
バス１０９に接続されている周辺機器としては、ＨＤＤ（Hard Disk Drive）１０３、グラフィック処理装置１０４、入力インタフェース１０５、光学ドライブ装置１０６、機器接続インタフェース１０７およびネットワークインタフェース１０８がある。
【００３９】
ＨＤＤ１０３は、内蔵したディスクに対して、磁気的にデータの書き込みおよび読み出しを行う。ＨＤＤ１０３は、制御ノード１００の補助記憶装置として使用される。ＨＤＤ１０３には、ＯＳのプログラム、アプリケーションプログラム、および各種データが格納される。なお、補助記憶装置としては、フラッシュメモリなどの不揮発性の半導体記憶装置（ＳＳＤ：Solid State Drive）を使用することもできる。
【００４０】
グラフィック処理装置１０４には、モニタ２１が接続されている。グラフィック処理装置１０４は、プロセッサ１０１からの命令に従って、画像をモニタ２１の画面に表示させる。モニタ２１としては、ＣＲＴ（Cathode Ray Tube）を用いた表示装置や液晶表示装置などがある。
【００４１】
入力インタフェース１０５には、キーボード２２とマウス２３とが接続されている。入力インタフェース１０５は、キーボード２２やマウス２３から送られてくる信号をプロセッサ１０１に送信する。なお、マウス２３は、ポインティングデバイスの一例であり、他のポインティングデバイスを使用することもできる。他のポインティングデバイスとしては、タッチパネル、タブレット、タッチパッド、トラックボールなどがある。
【００４２】
光学ドライブ装置１０６は、レーザ光などを利用して、光ディスク２４に記録されたデータの読み取りを行う。光ディスク２４は、光の反射によって読み取り可能なようにデータが記録された可搬型の記録媒体である。光ディスク２４には、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）などがある。
【００４３】
機器接続インタフェース１０７は、制御ノード１００に周辺機器を接続するための通信インタフェースである。例えば機器接続インタフェース１０７には、メモリ装置２５やメモリリーダライタ２６を接続することができる。メモリ装置２５は、機器接続インタフェース１０７との通信機能を搭載した記録媒体である。メモリリーダライタ２６は、メモリカード２７へのデータの書き込み、またはメモリカード２７からのデータの読み出しを行う装置である。メモリカード２７は、カード型の記録媒体である。
【００４４】
ネットワークインタフェース１０８は、ネットワーク２０に接続されている。ネットワークインタフェース１０８は、ネットワーク２０を介して、他のコンピュータまたは通信機器との間でデータの送受信を行う。
【００４５】
以上のようなハードウェア構成によって、第２の実施の形態の処理機能を実現することができる。なお、第１の実施の形態に示したジョブ管理ノード１０や複数の計算ノード１も、図３に示した制御ノード１００と同様のハードウェアにより実現することができる。
【００４６】
制御ノード１００は、例えばコンピュータ読み取り可能な記録媒体に記録されたプログラムを実行することにより、第２の実施の形態の処理機能を実現する。制御ノード１００に実行させる処理内容を記述したプログラムは、様々な記録媒体に記録しておくことができる。例えば、制御ノード１００に実行させるプログラムをＨＤＤ１０３に格納しておくことができる。プロセッサ１０１は、ＨＤＤ１０３内のプログラムの少なくとも一部をメモリ１０２にロードし、プログラムを実行する。また制御ノード１００に実行させるプログラムを、光ディスク２４、メモリ装置２５、メモリカード２７などの可搬型記録媒体に記録しておくこともできる。可搬型記録媒体に格納されたプログラムは、例えばプロセッサ１０１からの制御により、ＨＤＤ１０３にインストールされた後、実行可能となる。またプロセッサ１０１が、可搬型記録媒体から直接プログラムを読み出して実行することもできる。
【００４７】
図４は、各ノードが有する機能を示すブロック図である。制御ノード１００はジョブマネージャ１１０を有している。ジョブマネージャ１１０は、計算ノードに実行させるジョブを管理する。例えばジョブマネージャ１１０はジョブスケジューラとして機能し、ジョブの実行スケジュールを作成し、そのスケジュールに従ってジョブを計算ノードに実行させる。一部の計算ノード２１０，２２０，２３０は、エージェント２１１，２２１，２３１を有している。エージェント２１１，２２１，２３１は、ジョブマネージャ１１０と連携し、担当範囲内の計算ノードにおけるジョブの実行を管理する。例えばエージェント２１１は、計算ノード２１０，２４０−１，２４０−２，２４０−３，・・・におけるジョブの実行を管理する。エージェント２２１は、計算ノード２２０，２５０−１，２５０−２，２５０−３，・・・におけるジョブの実行を管理する。エージェント２３１は、計算ノード２３０，２６０−１，２６０−２，２６０−３，・・・におけるジョブの実行を管理する。
【００４８】
エージェント２１１，２２１，２３１を有する計算ノード２１０，２２０，２３０以外の計算ノードは、デーモン２４１，２５１，２６１を有している。デーモン２４１，２５１，２６１は、エージェント２１１，２２１，２３１からの指示に従って、自身の周辺の空き計算ノードを探索する。
【００４９】
ジョブマネージャ１１０が並列ジョブに計算ノードを割り当てるとき、ネットワーク上の纏まった位置の複数の計算ノードを割り当てる。例えばジョブマネージャ１１０は、計算ノードの接続関係を示すメッシュまたはトーラス上に、空き計算ノードのみを含むサブメッシュを設定する。そしてジョブマネージャ１１０は、サブメッシュ内の複数の計算ノードを、ジョブに割り当てる。このとき、フラグメンテ−ションにより、ネットワーク内に十分な空き計算ノードが存在しても、空き計算ノードの位置が離散しており、ジョブの並列度に応じた数の計算ノードを含むサブメッシュを設定できない場合がある。この場合、例えば、ジョブマネージャ１１０は、実行されている複数のジョブの一部（例えば１つのジョブのみ）を移動することで、メッシュまたはトーラス接続のネットワーク上に所定のサイズの空き領域を作り出す。そしてジョブマネージャ１１０は、作り出した空き領域内の計算ノードをジョブに割り当て、その計算ノードにジョブを実行させる。
【００５０】
第２の実施の形態では、ジョブマイグレーションによるジョブの再配置、およびジョブの新規投入を、全ジョブのうち一部の再配置で実現することで、迅速な処理を可能とする。すなわち、リアルタイム性を重視するため、ジョブ配置の最適化が、あえて局所的に行われる。しかも再配置処理の効率化のため、ジョブの再配置は平行移動に限定される。また、ジョブの再配置によるジョブスループットの低下を抑止するため、再配置した場合にスループットが低下した場合は、再配置されたジョブは、元の配置に戻される。このようにしてフラグメンテーションによる運用効率の低下を抑止し、スループット向上（効率的運用）が図れる。
【００５１】
ジョブの再配置では、例えば、まず、１つの新規投入したいジョブ（投入候補ジョブ）と、着目する実行中のジョブ（移動候補ジョブ）が決められる。次に、移動候補ジョブの平行移動によって、それらの周辺に投入候補ジョブを実行可能な、所定の形状の空きノード群が確保できるかが判定される。投入候補ジョブの大きさ（割り当てる計算ノード数）や、移動候補ジョブの大きさと数は適当な閾値で制限してもよい。次に、投入候補ジョブに対し、移動候補ジョブを取り替えて、近くの空き計算ノード群が探索される。個々の探索は、例えば移動候補ジョブの近くの空きノード群それぞれのデーモンにより並列分散処理することができる。これにより探索に要する時間の短縮が可能となる。また投入候補ジョブが複数ある場合、１つの新規投入候補ジョブへの処理を繰り返すことで、投入候補ジョブそれぞれに、適切な数の計算ノード群を割り当てることができる。
【００５２】
以上の処理は、ジョブマネージャ１１０、エージェント２１１，２２１，２３１、および各計算ノードのデーモン２４１，２５１，２６１との連携処理により実現される。なお、制御ノード１００のジョブマネージャ１１０が一括で実行することも可能である。図１に示したジョブ管理ノード１０の機能は、例えばジョブマネージャ１１０とエージェント２１１，２２１，２３１とが連携動作することで実現できる。
【００５３】
また、図４に示した各要素間を接続する線は通信経路の一部を示すものであり、図示した通信経路以外の通信経路も設定可能である。また、図４に示した各要素の機能は、例えば、その要素に対応するプログラムモジュールをコンピュータに実行させることで実現することができる。
【００５４】
図５は、ジョブの再配置を伴うジョブ投入処理の手順の一例を示す図である。例えば、ジョブマネージャ１１０は、実行するジョブの並列度（ジョブの実行に使用する計算ノード数）分の空き計算ノードを包含するサブネットが見つからないとき、図５に示すジョブの再配置を伴うジョブ投入処理を開始する。
【００５５】
ジョブマネージャ１１０は、複数のエージェントそれぞれに対して、空き領域探索指示を出す（ステップＳ１０１）。なお、図５では、代表的にエージェント２１１との間の連携処理を示している。
【００５６】
空き領域探索指示を受信したエージェント２１１は、ジョブ並列サーチ処理を行う（ステップＳ１０２）。ジョブ並列サーチ処理では、例えばエージェント２１１は、自身が管理する範囲内の複数の計算ノードのうち、ジョブを実行している計算ノードのデーモンに対して、ジョブ周辺の空き領域把握指示を送信する。図５では、代表的にデーモン２４１との間の連携処理を示している。
【００５７】
空き領域把握指示を受信したデーモン２４１は、空き領域の把握処理を行う（ステップＳ１０３）。例えばデーモン２４１は、デーモン２４１自身が実装されている計算ノードの周囲の空き計算ノードに基づいて、デーモン２４１自身が実装されている計算ノードで実行しているジョブ（移動候補ジョブ）の移動可能領域を特定する。そしてデーモン２４１は、移動可能領域をエージェント２１１に通知する。
【００５８】
図６は、空き領域把握処理の一例を示す図である。図６では、計算ノードを矩形で示している。ジョブを実行している計算ノードを示す矩形内には、実行しているジョブの名称が示されている。ジョブを実行している計算ノードを示す矩形内には、「空」と示されている。
【００５９】
エージェント２１１は、例えばジョブを実行しているノードに対して、空き領域把握指示を行う。図６の例では、名称「ＪｏｂＭＶ」のジョブを実行している計算ノードに対して、空き領域把握指示が出されたものとする。この場合、名称「ＪｏｂＭＶ」のジョブが、移動候補ジョブ３１となる。移動候補ジョブ３１が実行されている計算ノードから、各軸方向に空き計算ノードが続く範囲が、空き領域の探索範囲となる。図６の例では、Ｘ軸の負の方向に１ノード分、正の方向に２ノード分が、Ｘ軸方向の探索範囲である。またＹ軸の負の方向に１ノード分、正の方向に１ノード分が、Ｙ軸方向の探索範囲である。
【００６０】
なお移動候補ジョブ３１は、エージェント２１１が無作為に選択してもよい。またジョブマネージャ１１０からジョブの優先度とジョブの使用ノード数との情報を取得したエージェント２１１が、優先度と使用ノード数とが基準以下のジョブを選択し、移動候補ジョブとすることもできる。使用ノード数についての基準は、例えば過去に実行させたジョブの使用ノード数の平均が適用される。この場合、平均以下の数の計算ノードで実行されているジョブの中から、移動候補ジョブが選択される。また、例えば、優先度の高いジョブが優先して実行される場合に、ジョブの優先度が５段階（１が最高の優先度、５が最小の優先度）に設定できるものとする。この場合、移行候補ジョブを選択する際の優先度の基準として、低い方の優先度「４」が用いられる。すなわち優先度が「４」または「５」のジョブの中から、移行対象ジョブが選択される。
【００６１】
以下、図６に示した２次元空間のネットワークの例で、空き領域把握処理を説明する。なお、３以上のｎ次元のメッシュまたはトーラス接続のネットワークであっても、基本的に同じ動作で空き領域の把握が可能である。
【００６２】
［手順１］デーモン２４１は、移動（再配置）の移動候補ジョブのＸ軸方向への、空き計算ノードの探索を行う。これにより、空き計算ノードが、Ｘ軸の正負の両方向にどこまで続くかが確認される。図６の例では、名称「ＪｏｂＭＶ」の移動候補ジョブ３１は４つの計算ノード２４０−１〜２４０−４を使用している。
【００６３】
［手順１−１］計算ノード２４０−１内のデーモンが、計算ノード２４０−１からＸ軸の負の方向の隣のノードへ転送データを送る。送信データを受信した計算ノードは、自ノードが空き計算ノードであれば、さらにＸ軸の負の方向に隣接する計算ノードに転送データを送る。送信データを受信した計算ノードは、自ノードがジョブを実行していれば、自身のアドレスを記載した転送データを、送信元に送り返す。
【００６４】
図７は、転送データの一例を示す図である。なお図７には、３次元のメッシュまたはトーラス接続のネットワークで実施する場合の転送データ４１の一例が示されている。転送データ４１には、受信した計算ノードのアドレス（Ｘ軸、Ｙ軸、Ｚ軸の座標値）、送信元の計算ノード２４０−１のアドレス（Ｘ軸、Ｙ軸、Ｚ軸の座標値）、ホップ数カウンタなどが含まれている。
【００６５】
［手順１−２］転送データ４１を受信した計算ノードでは、その計算ノード内のデーモンが、その計算ノードがジョブを実行しているかどうかを判断する。ジョブを実行していれば、デーモンは、転送データ４１内に自分の計算ノードのアドレスを設定し、転送データ４１を送信元である計算ノード２４０−１へ送信する。ジョブがない場合は、デーモンは、転送データ４１中のホップ数カウンタに１を加算して、転送データ４１を、自分のＸ軸の負の方向の１つ隣りの計算ノードへ送信する。
【００６６】
これにより、送信元の計算ノード２４０−１のデーモンは、送り返された転送データ４１の内容により、Ｘ軸の負の方向に何ホップ分の空き計算ノードが存在するのかを認識できる。計算ノード２４０−２は、同様の探索をＸ軸の正の方向に行う。これにより、送信元の計算ノード２４０−２のデーモンは、送り返された転送データ４１の内容により、Ｘ軸の正の方向に何ホップ分の空き計算ノードが存在するのかを認識できる。
【００６７】
［手順２］次にデーモン２４１は、移動（再配置）の移動候補ジョブのＹ軸方向への、空き計算ノードの探索を行う。
例えば計算ノード２４０−１内のデーモンが、計算ノード２４０−１からＹ軸の正の方向の隣のノードへ転送データ４１を送る。Ｙ軸方向の転送データ４１を受信した計算ノードでの処理は、Ｘ軸方向への転送データ４１に対する処理と同様である。これにより、送信元の計算ノード２４０−１のデーモンは、送り返された転送データ４１の内容により、Ｙ軸の負の方向に何ホップ分の空き計算ノードが存在するのかを認識できる。計算ノード２４０−３は、同様の探索をＹ軸の負の方向に行う。これにより、送信元の計算ノード２４０−３のデーモンは、送り返された転送データ４１の内容により、Ｙ軸の負の方向に何ホップ分の空き計算ノードが存在するのかを認識できる。
【００６８】
他の軸（例えばＺ軸）についても、転送データ４１を用いて、空き計算ノードの探索が行われる。これを実施すると、空き計算ノードが含まれる仮探索枠３２（図６参照）が認識できる。ただし、仮探索枠３２は、移動候補ジョブ３１から各軸方向に探索しただけなので、まだ仮探索枠３２内に、空き計算ノードかどうかが不明な計算ノードが残っている。
【００６９】
図８は、仮探索枠内の未探索領域の一例を示す図である。図８に示すように、移動候補ジョブ３１を実行している計算ノード２４０−１〜２４０−４からＸ軸方向およびＹ軸方向に空き計算ノードを探索した場合、仮探索枠３２の四隅に、未探索領域３３〜３６が残存する。未探索領域３３〜３６に存在する計算ノードは、空き計算ノードかどうかが、まだ不明である。
【００７０】
そこで、以下の手順３の処理が行われる。
［手順３］仮探索枠３２内の計算ノードが連携し、仮探索枠内の未探索領域３３〜３６を探索する。例えば、以下の手順で未探索領域３３〜３６の探索が行われる。
【００７１】
［手順３−１］移動候補ジョブ３１を実行する計算ノードは、Ｘ軸方向に並ぶ空きノードのうち、Ｘ軸の座標が最も大きい（最老番）計算ノード２４０−５のデーモンに、未探索領域用転送データを送る。
【００７２】
図９は、未探索領域用転送データの一例を示す図である。未探索領域用転送データ４２には、図７に示した転送データ４１と同様の情報に加え、未探索領域用転送データ４２を転送する空き計算ノードのアドレス（Ｘ軸、Ｙ軸、Ｚ軸の座標値）が設定される。
【００７３】
図９に示す未探索領域用転送データ４２は、例えば、仮探索枠３２内でかつ移動候補ジョブ３１を実行する計算ノード２４０−１のデーモンにより、Ｘ軸の正の方向の空き計算ノード２４０−５に送られる。このとき、計算ノード２４０−１のアドレスが送信元のアドレスとして記載される。送信された未探索領域用転送データ４２は、空き計算ノード２４０−６で一端受信され、計算ノード２４０−５に転送される。
【００７４】
［手順３−２］未探索領域用転送データ４２を受信した空き計算ノード２４０−５，２４０−６を、中継ノードとする。中継ノードのデーモンは、未探索領域用転送データ４２に、中継ノードのアドレス（Ｘ軸、Ｙ軸、Ｚ軸の座標値）として、自身のアドレスを記載する。
【００７５】
［手順３−３］中継ノード（計算ノード２４０−５，２４０−６）それぞれのデーモンは、Ｙ軸の正および負の方向それぞれの隣接する計算ノードへ、未探索領域用転送データ４２を転送する。未探索領域用転送データ４２を受信した計算ノードのデーモンは、自身の計算ノードでジョブを実行しているか否かを判断する。ジョブを実行していれば、デーモンは、未探索領域用転送データ４２にアドレス（Ｘ軸、Ｙ軸、Ｚ軸の座標値）を記載して、未探索領域用転送データ４２を送信元に送り返す。ジョブがない場合、デーモンは、未探索領域用転送データ４２中のホップ数値記載部分に１を加算して、自分のＹ軸方向（中継ノードから離れる方向）の１つ隣へ、未探索領域用転送データ４２を転送する。
【００７６】
このような処理を、移動候補ジョブ３１のＸ軸の負の方向にも行うことで、未探索領域用転送データ４２の送信元の計算ノード２４０−１において、未探索領域３３〜３６内の計算ノードが空き計算ノードか否かが認識される。仮探索枠３２内の各計算ノードが空き計算ノードか否かの情報は、例えば計算ノード２４０−１内のデーモン２４１から、エージェント２１１に通知される。
【００７７】
エージェント２１１は、仮探索枠３２内の各計算ノードが空き計算ノードか否かに基づいて、移動候補ジョブ３１の移動可能領域を決定する。
図１０は、移動可能領域の一例を示す図である。例えば、移動可能領域４３として、移動候補ジョブ３１を実行している計算ノードおよび空き計算ノードのみを含むサブメッシュが決定される。ネットワークが２次元のメッシュまたはトーラス接続であれば、移動可能領域４３の形状は、長方形となる。またネットワークが３次元のメッシュまたはトーラス接続であれば、移動可能領域４３の形状は、直方体となる。
【００７８】
例えばエージェント２１１は、仮探索枠３２内で生成可能な最も大きいサブメッシュを、移動可能領域４３とする。移動可能領域４３が長方形または直方体であることにより、移動候補ジョブ３１の移動時（再配置）や新規ジョブ投入時に複雑な計算処理が不要になり、迅速な処理が可能となる。すなわち、一部が凸型や凹型になると再配置や投入ができるかどうかの場合、判定が複雑になり、リアルタイム性が損なわれる。例えば図１０の例では、「ＪｏｂＷ」を実行している計算ノード２４０−７や「ＪｏｂＳ」を実行している計算ノード２４０−８のＹ軸方向に空き計算ノードがある。しかし、その空き計算ノードを移動可能領域４３に組み込むと、移動可能領域４３の形が複雑になり、結果的にその後のジョブ移動（再配置）やジョブ投入可能領域の計算に時間がかかる。そこで第２の実施の形態では、計算ノード２４０−７および計算ノード２４０−８それぞれのＹ軸方向の空き計算ノードを、あえて移動可能領域４３から除外することで、移動可能領域４３の形状を単純な長方形（直方体）とし、処理の高速化を図っている。
【００７９】
決定された移動可能領域４３内が、移動候補ジョブ３１を移動させる候補領域となる。移動候補ジョブ３１を移動可能領域４３内で移動させたとき、移動可能領域４３内の残りの領域内に、新規のジョブを投入可能な領域（ジョブ投入可能領域）が設定される。
【００８０】
図１１は、移動候補ジョブを移動後のジョブ投入可能領域の一例を示す図である。図１１の例は、移動可能領域４３内のＸ軸およびＹ軸の負の方向の端に、移動候補ジョブ３１を移動させた場合を示している。この場合、移動可能領域４３内に６つの計算ノードを含むジョブ投入可能領域４４が設定できる。ジョブ投入可能領域４４は、長方形または直方体の領域である。
【００８１】
以下、図５の説明に戻る。
移動可能領域を取得したエージェント２１１は、移動可能領域の情報をメモリに格納し、移動可能領域内で移動候補ジョブを移動させた場合の、移動前後での処理性能を比較する（ステップＳ１０４）。例えばエージェント２１１は、移動前の移動候補ジョブの性能（例えばスループット）を測定し、移動候補ジョブの移動先の計算ノードで実行させて性能（例えばスループット）を測定する。エージェント２１１は、移動後に明らかな処理性能低下がみられたときは、別の移動場所へ変更する。例えばエージェント２１１は、移動前の処理性能に対する移動後の処理性能が、所定値以下（例えば１／２以下）の場合、明らかな処理性能低下があると判断する。エージェント２１１は、明らかな処理性能低下があった場合は、移動候補ジョブを移動元へ戻し、処理性能が低下しない別の移動先を探索する。
【００８２】
なお処理性能測定は、様々な方法で可能であるが、例えば、メインループの１ループあたりの所要時間を比較する方法などがある。またＩＯやネットワークの通信を試すテストプログラムを走らせてみる方法もある。
【００８３】
処理性能の比較により、性能が低下しない移動先が見つかると、エージェント２１１は、そのときの移動候補ジョブ３１の移動先とジョブ投入可能領域４４とを示す情報を、ジョブマネージャ１１０に通知する。ジョブマネージャ１１０は、通知された移動候補ジョブ３１の移動先とジョブ投入可能領域４４とを示す情報をメモリに格納する。
【００８４】
次にジョブマネージャ１１０は、新たに計算ノードに実行させるジョブを選定する（ステップＳ１０５）。例えばジョブマネージャ１１０は、ジョブマネージャ１１０において待ち状態として登録されているジョブの中から、実行させるジョブを選定する。例えば実行させるジョブを、以下のように決めることができる。
【００８５】
ジョブマネージャ１１０は、実行させるジョブの候補（投入候補ジョブ）として、並列度（使用する計算ノード数）がジョブ投入可能領域４４内の計算ノード数以内のジョブを抽出する。ジョブマネージャ１１０は、投入候補ジョブが複数ある場合、次に以下の選択をかける。
【００８６】
ジョブマネージャ１１０は、スループットをあげるために、投入候補ジョブの中から、移動候補ジョブ３１の残り所要時間以内に終了するジョブを優先的に選択する。該当するジョブがない場合、ジョブマネージャ１１０は、できるだけノードが早く解放されることを考慮して、所要時間の少ないジョブを選択する。ジョブ選定処理の詳細は以下の通りである。
【００８７】
［手順１］移動可能領域４３内の計算ノード数から、１次判定用最大投入可能ノード数を算出する。１次判定用最大ジョブ投入可能ノード数とは、投入可能なジョブの使用ノード数の最大値である。算出方法は以下の式で表される。
１次判定用最大ジョブ投入可能ノード数＝移動可能領域内の計算ノード数−移動候補ジョブに割り当てられた計算ノード数
［手順２］投入ジョブの１次判定が行われる。以下の１次判定基準値を満たせば、次の手順へ処理が進められ、満たさなければ処理が打ち切られる。
１次判定基準値＝１次判定用最大ジョブ投入可能ノード数−投入ジョブの実行に使用する計算ノード数＞０
１次判定基準値が０より大きい場合、条件が満たされる。１次判定基準値が０以下の場合、条件が満たされない。
【００８８】
［手順３］ジョブマネージャ１１０は、最大投入ジョブ形状を計測する。詳細には以下の手順で計測が行われる。
［手順３−１］ジョブマネージャ１１０は、移動後の移動候補ジョブ３１について、移動可能領域４３中のＸ軸、Ｙ軸、Ｚ軸の負の方向（最若番側）へ寄せた場合の、移動候補ジョブ３１の位置を判断する。この時点では、実際のジョブ移動（再配置）は行わない。ジョブマネージャ１１０は、移動可能領域４３内の、移動後の移動候補ジョブ３１に割り当てられる計算ノードを除いた余剰部分（空き計算ノードが連続する範囲）内に、サブメッシュ（長方形または直方体）の領域を生成する。ジョブマネージャ１１０は、生成された領域を、ジョブ投入可能領域４４とする。図１１の例であれば、６個の計算ノードを含むジョブ投入可能領域４４が生成される。
【００８９】
［手順３−２］ジョブマネージャ１１０は、ジョブ投入可能領域４４に選択したジョブが投入可能か否かを確認する。例えばジョブ投入可能領域４４内の計算ノード数が、選択したジョブの実行に使用する計算ノード数以上であれば、投入可能であると判断される。
【００９０】
投入可能なら、ジョブマネージャ１１０は、ジョブの移動（再配置）をエージェント２１１に指示する（ステップＳ１０６）。ジョブマネージャ１１０からの指示を受けて、エージェント２１１が、移動候補ジョブ３１を、ジョブマイグレーションで移動させる（ステップＳ１０７）。例えばエージェント２１１は、移動候補ジョブ３１を、移動可能領域４３のうちのＸ軸、Ｙ軸、Ｚ軸の負の方向の端（最若番）へ移動させる。具体的にはエージェント２１１は、移動候補ジョブ３１を現在実行している計算ノードに対して、移動先の計算ノードへのジョブマイグレーションによる移動候補ジョブ３１の移動を指示する。すると、指示を受けた計算ノードがジョブマイグレーションを実行する。
【００９１】
次にエージェント２１１は、実測値により、移動候補ジョブ３１の移動前後の性能を比較する。例えば、エージェント２１１は、予め移動候補ジョブ３１の、移動前の計算ノードにおける性能（スループット）を測定しておく。そしてエージェント２１１は、移動候補ジョブ３１を移動後に、移動候補ジョブ３１を実行している計算ノードにおける処理の性能を単位時間（一例として５分間程度）だけ測定する。エージェント２１１は、移動前よりも移動後の処理性能が、所定値以上落ちていないことを確認する。例えばエージェント２１１は、移動後の性能を移動前の性能で除算した結果が所定値以上である場合、性能は落ちていないと判断する。もし、性能が落ちていた場合は、エージェント２１１は、移動を取り消す（ステップＳ１０９）。例えばエージェント２１１は、移動候補ジョブ３１を、マイグレーション前のジョブ配置位置へ、再度マイグレーションで戻す。そして処理を終了する。
【００９２】
移動したジョブの性能が落ちていない場合（性能維持または性能が向上した場合）は、エージェント２１１は、新規のジョブを投入する（ステップＳ１１０）。例えばエージェント２１１は、ジョブマネージャ１１０から、ステップＳ１０５で選定したジョブの情報を取得し、そのジョブをジョブ投入可能領域４４内の計算ノードに実行させる。
【００９３】
このようにして、空き計算ノードのフラグメンテーションを局所的に解消させることができる。その結果、実行待ちのジョブを早期に実行させることができ、システムの運用効率が向上する。しかも、フラグメンテーションの解消の範囲が局所的であるため、短時間で処理を完了することができる。また空き領域の把握などの処理を、複数のエージェントやデーモンで分散して実行するため、さらに短時間で処理を完了できる。
【００９４】
なお、ジョブマネージャ１１０から複数のエージェントに対して出した空き領域検索指示（図５のステップＳ１０１）に対して、２以上のエージェントが同一のジョブを移動候補ジョブとして選択する場合があり得る。また２以上のエージェントそれぞれが決定した移動可能領域の少なくとも一部が重複する場合もあり得る。そこで、ジョブマネージャ１１０は、ジョブ再配置指示（ステップＳ１０６）の際に、移動候補ジョブまたは移動可能領域が重複する場合の調停処理を行った上で、再配置指示を行う。
【００９５】
図１２は、ジョブ再配置指示の処理手順の一例を示す図である。
［ステップＳ１２１］ジョブマネージャ１１０は、各エージェントから、移動候補ジョブおよび移動可能領域を示す情報を受信する。例えばジョブマネージャ１１０は、各エージェントから、移動候補ジョブ３１のジョブＩＤと移動可能領域４３の範囲とを示す情報を受信する。
【００９６】
［ステップＳ１２２］ジョブマネージャ１１０は、複数のエージェントの中から、未選択のエージェントを１つ選択する。
［ステップＳ１２３］ジョブマネージャ１１０は、選択したエージェントが特定した移動候補ジョブまたは移動可能領域が、他のエージェントが特定した移動候補ジョブまたは移動可能領域と重複するか否かを判断する。例えばジョブマネージャ１１０は、選択したエージェントから取得した移動候補ジョブのジョブＩＤが、他のエージェントから取得した移動候補ジョブのジョブＩＤの少なくとも１つと一致する場合、移動候補ジョブが重複すると判断する。またジョブマネージャ１１０は、選択したエージェントから取得した移動可能領域の範囲が、他のエージェントから取得した移動可能領域の範囲の少なくとも１つと重複する場合、移動可能領域が重複すると判断する。重複がある場合、処理がステップＳ１２４に進められる。重複がない場合、処理がステップＳ１２５に進められる。
【００９７】
［ステップＳ１２４］ジョブマネージャ１１０は、同じジョブを移動候補ジョブとして特定したエージェントの中で、選択したエージェントのＩＤが最若番か否かを判断する。最若番であれば、処理がステップＳ１２５に進められる。最若番でなければ、処理がステップＳ１２６に進められる。
【００９８】
［ステップＳ１２５］ジョブマネージャ１１０は、選択したエージェントに対して、移動候補ジョブの再配置の実行を指示する。その後、処理がステップＳ１２７に進められる。
【００９９】
［ステップＳ１２６］ジョブマネージャ１１０は、選択したエージェントに対して、再配置の停止を指示する。
［ステップＳ１２７］ジョブマネージャ１１０は、すべてのエージェントに対して指示が完了したか否かがを判断する。指示をしていないエージェントがある場合、処理がステップＳ１２２に進められる。すべてのエージェントに対する指示が完了したら、ジョブ再配置指示の処理が終了する。
【０１００】
このようにして、複数のエージェントに並列で処理を実行させても、矛盾が生じないように再配置を指示することができる。その結果、複数のエージェントを利用した処理の信頼性が向上する。
【０１０１】
なお、第２の実施の形態では、移動可能領域４３を決定した後に、投入するジョブを選択しているが、先に投入するジョブを決定し、そのジョブを実行可能な移動可能領域４３を見つけ出すようにしてもよい。例えばジョブマネージャ１１０は、各エージェント２１１，２２１，２３１から取得した移動可能領域４３のうち、投入しようとするジョブを実行可能な移動可能領域４３を１つ選択する。そしてジョブマネージャ１１０は、選択した移動可能領域４３を通知したエージェントに対して、ジョブの投入を指示する。
【０１０２】
［第３の実施の形態］
次に第３の実施の形態について説明する。第３の実施の形態は、新規ジョブを投入しない場合において、各ジョブの終了予定時間に応じて、ジョブマイグレーションを行うものである。例えば、移動候補ジョブを実行している計算ノードの周辺の計算ノードで実行されているジョブの終了時間を鑑みて、終了予定時間が最も長いジョブに隣接するように、移動候補ジョブのジョブマイグレーションが行われる。終了時間が短いジョブを実行している計算ノード周辺の計算ノードを空き計算ノードにしておけば、終了時間が短いジョブが終了することで、空き計算ノードの範囲が広がる。その結果、次のジョブ追加時に、より広い領域を、ジョブ投入可能領域とすることが可能となる。
【０１０３】
図１３は、第３の実施形態におけるジョブマイグレーションの一例を示す図である。図１３の例では、移動可能領域５２内に、終了予定時間が２時間の移動候補ジョブ５１がある。移動可能領域５２の周囲の計算ノードでは、「ジョブＡ」〜「ジョブＧ」の各ジョブが実行されている。移動可能領域５２の周囲の計算ノードで実行されているジョブのうち、最も終了予定時間が長いのは「ジョブＥ」である。そこで、移動候補ジョブ５１は、ジョブＥを実行している計算ノードが占める領域５３に隣接する位置にジョブマイグレーションで移動される。
【０１０４】
図１４は、終了予定時間が最も長いジョブの位置に応じた移動先の例を示す図である。図１４（Ａ）は、終了予定時間が最も長いジョブを実行している計算ノードが占める領域５３の１つの辺の全体が、移動可能領域５２の１つの辺に接している場合である。図１４（Ａ）の例では、領域５３と移動可能領域５２とが、Ｙ軸に平行な辺で接している。この場合、領域５３のＹ軸方向の最低部（Ｙ軸の値の最若値）と、移動候補ジョブ５１の移動先の計算ノードが占める領域のＹ軸方向の最低部とが一致するように、移動候補ジョブ５１が移動される。
【０１０５】
図１４（Ｂ）は、終了予定時間が最も長いジョブを実行している計算ノードが占める領域５３の１つの辺の一部が、移動可能領域５２の１つの辺に接している場合である。図１４（Ｂ）の例では、領域５３のＹ軸方向の最低部が、移動可能領域５２のＹ軸方向の最低部より低くなっている。この場合、移動可能領域５２のＹ軸の範囲の最低部と移動候補ジョブ５１の移動先の計算ノードが占める領域の最低部とが一致するように、移動候補ジョブ５１が移動される。
【０１０６】
図１５は、第３の実施の形態におけるジョブ移動処理手順の一例を示す図である。
［ステップＳ２０１］エージェント２１１は、移動可能領域５２を示す情報をジョブマネージャ１１０に通知する。
【０１０７】
［ステップＳ２０２］ジョブマネージャ１１０から周辺ジョブ情報を取得する。周辺ジョブ情報には、例えば移動可能領域５２に隣接する位置の計算ノードが実行しているジョブ（周辺ジョブ）の終了予定時間（何時間後に終了するか）が示されている。
【０１０８】
図１６は、周辺ジョブ情報の一例を示す図である。例えばジョブマネージャ１１０からエージェント２１１へ、図１６に示す構造体の周辺ジョブ情報５４がリンクドリストの状態で通知される。周辺ジョブ情報５４には、ジョブＩＤ、ジョブ名、ジョブに割り当てられた計算ノードを含む領域に加え、次の周辺ジョブ情報へのリンクが含まれる。エージェント２１１は、周辺ジョブ情報５４のリンクを辿ることで、移動可能領域５２周辺の計算ノードの、ジョブへの割り当て状況を把握する。エージェント２１１は、周辺ジョブ情報５４で認識した各ジョブを指定して、ジョブマネージャ１１０から、該当ジョブの終了予定時間を取得する。これにより、エージェント２１１は、周辺ジョブの終了予定時間を把握できる。
【０１０９】
以下、図１５の説明に戻る。
［ステップＳ２０３］エージェント２１１は、周辺ジョブの中で、終了予定時間が最大となるジョブを検出する。
【０１１０】
［ステップＳ２０４］エージェント２１１は、終了予定時間が最大となるジョブが複数あるか否かを判断する。該当ジョブが複数ある場合、処理がステップＳ２０５に進められる。該当ジョブが１つしかなければ、そのジョブが選択され、処理がステップＳ２０６に進められる。
【０１１１】
［ステップＳ２０５］エージェント２１１は、終了予定時間が最大となるジョブのうち、ジョブＩＤが最若番のジョブを選択する。
［ステップＳ２０６］エージェント２１１は、ジョブマイグレーションにより、移動候補ジョブを、選択したジョブを実行している計算ノードに隣接する計算ノードへ移動する。
【０１１２】
以上のようにして、新規ジョブの投入時以外にも、空き計算ノードのフラグメンテ−ションの局所的な解消を行い、次のジョブ投入時までに、広いジョブ投入可能領域を用意することができる。その結果、システムの運用効率を向上させることができる。
【０１１３】
〔第４の実施の形態〕
次に第４の実施の形態について説明する。第４の実施の形態は、新規ジョブの投入時においても、移動可能領域の周辺ジョブの終了予定時間に基づいて、適切な位置に移動候補ジョブを移動させるものである。例えば第４の実施の形態では、新規ジョブの終了予定時間と移動候補ジョブの終了予定時間との比較結果に基づいて、どのような位置に移動候補ジョブを移動させるのかが決定される。
【０１１４】
図１７は、新規ジョブと移動候補ジョブとの終了予定時間の比較結果のパターンを示す図である。「パターン１」は、新規ジョブの終了予定時間が、移動候補ジョブの終了予定時間よりも長い場合である。この場合、「選択行動Ｉ」によって移動候補ジョブの移動先が選択される。「パターン２」は、新規ジョブの終了予定時間が、移動候補ジョブの終了予定時間よりも短い場合である。この場合、「選択行動ＩＩ」によって移動候補ジョブの移動先が選択される。「パターン３」は、新規ジョブの終了予定時間と移動候補ジョブの終了予定時間とが同じ場合である。例えば新規ジョブの終了予定時間と移動候補ジョブの終了予定時間との差が所定値以下であれば、同じと判断される。この場合、「選択行動Ｉ」によって移動候補ジョブの移動先が選択される。
【０１１５】
「選択行動Ｉ」は、先ジョブ投入可能領域を決め、次に、移動候補ジョブの移動先決定するものである。「選択行動ＩＩ」は、先に移動候補ジョブを移動させ、次に、ジョブ投入可能領域を決めるものである。
【０１１６】
図１８は、第４の実施の形態におけるジョブ移動処理の一例を示す図である。
［ステップＳ３０１］エージェント２１１は、ジョブ投入可能領域の形状を決定する。例えばエージェント２１１は、移動可能領域内で移動ジョブを所定の方向（例えば各軸の負の方向）に寄せた場合の、空き領域に生成できる最大の長方形または直方体の領域の形状を、ジョブ投入可能領域の形状として決定する。
【０１１７】
［ステップＳ３０２］エージェント２１１は、ジョブ投入可能領域に投入する新規ジョブの情報を、ジョブマネージャ１１０から取得する。
［ステップＳ３０３］エージェント２１１は、新規ジョブの終了予定時間が移動候補ジョブの終了予定時間以上か否かを判断する。新規ジョブの終了予定時間が移動候補ジョブの終了予定時間以上であれば、処理がステップＳ３０４に進められる。新規ジョブの終了予定時間が移動候補ジョブの終了予定時間未満であれば、処理がステップＳ３０５に進められる。
【０１１８】
［ステップＳ３０４］エージェント２１１は、「選択行動Ｉ」により、移動候補ジョブを移動させる。「選択行動Ｉ」による移動処理の詳細は、後述する（図２１参照）。その後、処理がステップＳ３０６に進められる。
【０１１９】
［ステップＳ３０５］エージェント２１１は、「選択行動ＩＩ」により、移動候補ジョブを移動させる。「選択行動ＩＩ」による移動処理の詳細は、後述する（図２２参照）。
［ステップＳ３０６］エージェント２１１は、ジョブ投入可能領域に新規ジョブを配置する。すなわちエージェント２１１は、ジョブ投入可能領域内の計算ノードに、新規ジョブを実行させる。
【０１２０】
図１９は、第４の実施の形態におけるジョブ投入可能領域の一例を示す図である。移動候補ジョブ６１が、移動可能領域内の各軸の負の方向に移動される。そして移動可能領域内の移動候補ジョブ６１が配置された領域以外の領域内で、最も大きな長方形または直方体の領域が、ジョブ投入可能領域６２となる。
【０１２１】
なお、ジョブ投入可能領域６２の配置は、移動候補ジョブ６１との関係によって決まる。
図２０は、ジョブ挿入可能領域の配置例を示す図である。図２０（Ａ）は、ジョブ投入可能領域６２をＹ軸の正の方向に寄せて配置した例である。図２０（Ｂ）は、移動候補ジョブ６１を、Ｙ軸の負の方向に寄せて配置した例である。
【０１２２】
ジョブ投入可能領域６２が決まると、移動可能領域内のジョブ投入可能領域６２以外の領域が、移動候補ジョブ６１を配置できる移動ジョブ配置可能領域６３となる。図２０の例では、移動候補ジョブ６１は、移動ジョブ配置可能領域６３内のＸ軸の負の方向に寄せて配置されている。
【０１２３】
移動ジョブ配置可能領域６３内のどこに移動候補ジョブ６１を配置するかは、周辺ジョブとの関係によって決められる。第４の実施の形態では、移動ジョブ配置可能領域６３の周辺のジョブのうちの終了予定時間が最大のジョブ（終了時間最大ジョブ）に隣接する位置に、移動候補ジョブ６１が配置される。
【０１２４】
次に、「選択行動Ｉ」の処理手順について説明する。
図２１は、「選択行動Ｉ」の処理手順の一例を示すフローチャートである。
［ステップＳ３１１］エージェント２１１は、移動可能領域５２を示す情報をジョブマネージャ１１０に通知する。
【０１２５】
［ステップＳ３１２］ジョブマネージャ１１０から周辺ジョブ情報を取得する。
［ステップＳ３１３］エージェント２１１は、周辺ジョブから終了時間最大ジョブ６４を選択する。この処理の詳細は後述する（図２３参照）。
【０１２６】
［ステップＳ３１４］エージェント２１１は、選択した終了時間最大ジョブ６４に隣接する位置に、ジョブ投入可能領域６２を設定する。
［ステップＳ３１５］エージェント２１１は、移動ジョブ配置可能領域６３に隣接する終了時間最大ジョブ６４を検出する。
【０１２７】
［ステップＳ３１６］エージェント２１１は、移動候補ジョブ６１を移動する。移動候補ジョブ移動処理の詳細は後述する（図２５）。
次に、「選択行動ＩＩ」の処理手順について説明する。
【０１２８】
図２２は、「選択行動ＩＩ」の処理手順の一例を示すフローチャートである。
［ステップＳ３２１］エージェント２１１は、移動可能領域５２を示す情報をジョブマネージャ１１０に通知する。
【０１２９】
［ステップＳ３２２］ジョブマネージャ１１０から周辺ジョブ情報を取得する。
［ステップＳ３２３］エージェント２１１は、周辺ジョブから終了時間最大ジョブ６４を選択する。この処理の詳細は後述する（図２３参照）。
【０１３０】
［ステップＳ３２４］エージェント２１１は、選択した終了時間最大ジョブ６４に隣接する位置に、移動ジョブ配置可能領域６３を設定する。
［ステップＳ３２５］エージェント２１１は、移動ジョブ配置可能領域６３に隣接する終了時間最大ジョブ６４を検出する。
【０１３１】
［ステップＳ３２６］エージェント２１１は、移動候補ジョブ６１を移動する。移動候補ジョブ移動処理の詳細は後述する（図２５）。
次に、終了時間最大ジョブ選択処理について詳細に説明する。
【０１３２】
図２３は、終了時間最大ジョブ選択処理の手順の一例を示すフローチャートである。
［ステップＳ３３１］エージェント２１１は、移動可能領域の周辺ジョブのうち、終了時間が最大のジョブ（終了時間最大ジョブ）が複数あるか否かを判断する。終了時間最大ジョブが複数ある場合、処理がステップＳ３３２に進められる。終了時間最大ジョブが１つだけであれば、そのジョブが選択され、終了時間最大ジョブ選択処理が終了する。
【０１３３】
［ステップＳ３３２］エージェント２１１は、終了時間最大ジョブのうち、使用する計算ノード数（並列度）が最大のジョブを特定する。
［ステップＳ３３３］エージェント２１１は、使用する計算ノード数が最大のジョブが複数あるか否かを判断する。該当ジョブが複数ある場合、処理がステップＳ３３４に進められる。該当ジョブが１つだけであれば、そのジョブを選択し、終了時間最大ジョブ選択処理が終了する。
【０１３４】
［ステップＳ３３４］エージェント２１１は、使用する計算ノード数が最大のジョブのうち、ジョブＩＤが最若番のジョブを選択する。
次に、移動ジョブ配置可能領域内の移動候補ジョブの配置について説明する。
【０１３５】
図２４は、移動ジョブ配置可能領域内の移動候補ジョブの配置例を示す図である。図２４（Ａ）は、移動可能な軸の負の方向に寄せる例である。移動ジョブ配置可能領域６３内のどこに配置しても、終了時間最大ジョブ６４に隣接する場合、移動候補ジョブ６１は、移動可能な軸（図２４の例ではＸ軸）の負の方向に寄せて配置される。
【０１３６】
図２４（Ｂ）は、終了時間最大ジョブのある方向に寄せる例である。例えば、終了時間最大ジョブ６４が、移動ジョブ配置可能領域６３内で移動候補ジョブ６１を移動可能な軸方向の一方の端に接している場合がある。この場合、移動候補ジョブ６１は、終了時間最大ジョブ６４が存在する方向に寄せて配置される。
【０１３７】
図２４（Ｃ）は、終了時間最大ジョブのうちのＩＤが若いジョブがある方向に寄せる例である。複数の終了時間最大ジョブ６４ａ，６４ｂが存在することがある。この場合、終了時間最大ジョブ６４ａ，６４ｂのジョブＩＤが比較され、ジョブＩＤの番号の若い方の終了時間最大ジョブ６４ａが特定される。そして移動候補ジョブ６１は、特定された終了時間最大ジョブ６４ａが存在する方向に寄せて配置される。
【０１３８】
このような配置を行うため、以下の手順で移動候補ジョブが移動される。
図２５は、移動候補ジョブ移動処理の手順の一例を示すフローチャートである。
［ステップＳ３４１］エージェント２１１は、移動ジョブ配置可能領域に対してＹ軸方向の上または下に、終了時間最大ジョブがあるか否かを判断する。Ｙ軸方向の上または下に終了時間最大ジョブがある場合、処理がステップＳ３４５に進められる。Ｙ軸方向の上または下に終了時間最大ジョブがない場合、処理がステップＳ３４２に進められる。
【０１３９】
［ステップＳ３４２］エージェント２１１は、移動ジョブ配置可能領域に対してＸ軸の負の方向に、終了時間最大ジョブがあるか否かを判断する。Ｘ軸方向の左に、終了時間最大ジョブがある場合、処理がステップＳ３４３に進められる。Ｘ軸方向の左に、終了時間最大ジョブがない場合、処理がステップＳ３４６に進められる。
【０１４０】
［ステップＳ３４３］エージェント２１１は、移動ジョブ配置可能領域に対してＸ軸方向の両側に、終了時間最大ジョブがあるか否かを判断する。Ｘ軸方向の両側に終了時間最大ジョブがある場合、処理がステップＳ３４４に進められる。Ｘ軸方向の一方にのみ終了時間最大ジョブがある場合、処理がステップＳ３４５に進められる。
【０１４１】
［ステップＳ３４４］エージェント２１１は、Ｘ軸方向両側の終了時間最大ジョブのうち、ジョブＩＤの値が小さい方（若番）の終了時間最大ジョブがあるのは、移動ジョブ配置可能領域に対してＸ軸の負の方向か否かを判断する。Ｘ軸の負の方向にある場合、処理がステップＳ３４５に進められる。Ｘ軸の正の方向にある場合、処理がステップＳ３４６に進められる。
【０１４２】
［ステップＳ３４５］エージェント２１１は、移動ジョブ配置可能領域の移動可能軸の負の方向に寄せて、移動候補ジョブを配置する。その後、移動候補ジョブ移動処理が終了する。
【０１４３】
［ステップＳ３４６］エージェント２１１は、移動ジョブ配置可能領域の移動可能軸の正の方向に寄せて、移動候補ジョブを配置する。その後、移動候補ジョブ移動処理が終了する。
【０１４４】
このように、新規ジョブの終了予定時間が移動候補ジョブの終了予定時間以上であれば、「選択行動Ｉ」により、終了時間最大ジョブに隣接する位置に新規ジョブが配置される。新規ジョブの終了予定時間が移動候補ジョブの終了予定時間未満であれば、「選択行動ＩＩ」により、終了時間最大ジョブに隣接する位置に移動ジョブが配置される。これにより、終了予定時間が長いジョブ同士を隣接させることができ、ジョブのフラグメンテーションの発生を抑止することができる。
【０１４５】
しかも移動ジョブ配置可能領域内で、移動候補ジョブを、終了時間最大ジョブに隣接するように寄せて配置するようにしたため、移動ジョブ配置可能領域内の終了時間最大ジョブが配置されない空き領域は、終了予定時間が比較的短いジョブに隣接する。その結果、終了予定時間が短いジョブが終了したときに、纏まった広い空き領域を確保することが可能となる。
【０１４６】
以上、実施の形態を例示したが、実施の形態で示した各部の構成は同様の機能を有する他のものに置換することができる。また、他の任意の構成物や工程が付加されてもよい。さらに、前述した実施の形態のうちの任意の２以上の構成（特徴）を組み合わせたものであってもよい。
【符号の説明】
【０１４７】
１  計算ノード
１ａ  第１計算ノード
１ｂ  第２計算ノード
１ｃ  第３計算ノード
２  第１領域
３  第２領域
４  第３領域
５  第４領域
６  第５領域
１０  ジョブ管理ノード
１１  通信インタフェース
１２  演算部
【図１】
0006428380.tif 000002
【図２】
0006428380.tif 000003
【図３】
0006428380.tif 000004
【図４】
0006428380.tif 000005
【図５】
0006428380.tif 000006
【図６】
0006428380.tif 000007
【図７】
0006428380.tif 000008
【図８】
0006428380.tif 000009
【図９】
0006428380.tif 000010
【図１０】
0006428380.tif 000011
【図１１】
0006428380.tif 000012
【図１２】
0006428380.tif 000013
【図１３】
0006428380.tif 000014
【図１４】
0006428380.tif 000015
【図１５】
0006428380.tif 000016
【図１６】
0006428380.tif 000017
【図１７】
0006428380.tif 000018
【図１８】
0006428380.tif 000019
【図１９】
0006428380.tif 000020
【図２０】
0006428380.tif 000021
【図２１】
0006428380.tif 000022
【図２２】
0006428380.tif 000023
【図２３】
0006428380.tif 000024
【図２４】
0006428380.tif 000025
【図２５】
0006428380.tif 000026