JP5429382B2 - ジョブ管理装置及びジョブ管理方法 - Google Patents

Description

本発明は、ジョブ管理装置及びジョブ管理方法に関する。

並列処理を実行するコンピュータシステムである並列コンピュータシステムにおいて、計算ノード群である複数のコンピュータの間は、ネットワークにより接続される。計算ノードのネットワークによる接続の形態としては、完全結合、Fat−Tree結合、メッシュ結合、トーラス結合等が知られている。これらの中で、メッシュ結合及びトーラス結合は、近傍の計算ノードを相互に接続するので、数千個以上の計算ノードを低コストで接続することができる。このため、数千個以上の計算ノードを含む並列コンピュータシステムにおいては、２次元トーラス結合や３次元メッシュ結合が使用されることが多い。

なお、格子型コンピュータシステムにおいて、親ノードのスーパースケジューラが、格子型コンピュータシステムにおける複数のノードとノード間接続装置の接続形態にしたがって論理ノードからなる格子モデルを作成する機能と、格子型コンピュータシステムに与えられる複数タスクからなるサービス要求を分析する機能と、サービス要求の分析結果にしたがって、サービス要求毎に必要となるノード数を格子モデル内に確保するための基点となる子ノードの数を決定する機能と、決定された数の子ノードを格子モデル内に分散して配置する機能と、を有することが、提案されている。

また、例えば、メモリ中に引き継ぎ情報ファイルを管理する空きレコード管理エリアを設けてディスクの有効利用を図り、管理エリアをファイルの各レコードが使用中であれば“１”、未使用であれば“０”というように対応する１ビットで使用状況を表現することが、提案されている。

特開２００７−２０６９８６号公報 特開平６−０８９２６２号公報

並列コンピュータシステムにおいて、計算ノード群である複数のコンピュータにおけるジョブの実行時間は、概略、計算ノードにおける実際の計算時間と、計算ノードの間における通信時間とに大別される。従って、計算ノードの間における通信時間の増加は、ジョブの実行時間を増加させる原因となる。

そこで、メッシュ結合又はトーラス結合された並列コンピュータシステムにおいて、隣接するノードの間における通信路が広帯域とされ、かつ、複数の単位ジョブを連続した長方形状又は直方体形状の計算ノード群に割り当てる。単位ジョブは、ユーザが投入した１個のジョブを分割したものである。複数の単位ジョブを連続した長方形状又は直方体形状の計算ノード群に割り当てることにより、ジョブの実行時間の増加を回避することができる。

複数の単位ジョブを連続した長方形状又は直方体形状の計算ノード群へ割り当てる割り当て処理は、ジョブ管理装置により実行される。ジョブ管理装置は、空きノードを検索して、単位ジョブに空きノードを割り当てる。空きノードは、新たに単位ジョブを割り当てることが可能な計算ノードである。空きノードを検索する時間が長いと、ユーザからは、ジョブの実行待ち時間が長く見える。また、空きノードを検索する時間が長いと、並列コンピュータシステムの稼働率が低下する。

本発明は、並列処理を実行するコンピュータシステムにおいて、空きノードを効率良く検索することができるジョブ管理装置を提供することを目的とする。

開示されるジョブ管理装置は、ｎ（ｎは２以上の整数）次元メッシュ結合又はｎ次元トーラス結合されたコンピュータネットワークにおける計算ノードであって、ジョブの割り当てが可能な空きノードを検索する。ジョブ管理装置は、１次元検索用情報生成部と、検索情報生成部と、空きノード検索部とを含む。１次元検索用情報生成部は、ｎ次元の中の１つの次元についての検索用情報であって、複数のビットを含み、ｎ次元の中の１つの次元に属する複数の計算ノードの各々について、ジョブの割り当てが可能か否かを１ビットの情報で示す１次元検索用情報を生成する。検索情報生成部は、複数のビットに対応するビット数の検索用マスクパターンであって、ｎ次元の中の１つの次元についてジョブが要求するサイズに対応する連続ビットを予め定められた値に設定された検索用マスクパターンを生成する。空きノード検索部は、ｎ次元の中の１つの次元について、１次元検索用情報と検索用マスクパターンとを用いて予め定められた論理演算を実行することにより、空きノードを検索する。

開示されるジョブ管理装置によれば、並列処理を実行するコンピュータシステムにおいて、複数の単位ジョブを連続した長方形状又は直方体形状を割り当てる計算ノードである空きノードを、効率良く検索することができる。

ジョブ管理装置の構成を示す図である。 ジョブ管理装置の構成を示す図である。 ジョブ管理処理の説明図である。 ジョブ管理処理の一例を示す図である。 ジョブ管理処理の一例を示す図である。 ジョブ管理処理の一例を示す図である。 ジョブ管理処理の一例を示す図である。 ジョブ管理処理の一例を示す図である。 ジョブ管理処理の一例を示す図である。 ジョブ管理処理フローである。 ジョブ管理処理の説明図である。 ジョブ管理処理の他の一例を示す図である。 ジョブ管理処理の他の一例を示す図である。 他のジョブ管理処理フローである。 本発明の検討したジョブ管理処理の説明図である。 本発明の検討したジョブ管理処理フローである。

本発明者は、並列コンピュータシステムにおける、空きノードの検索処理について検討した。

ユーザが投入したジョブは、ジョブ管理装置によって受け付けられ、複数の単位ジョブに分割される。複数の単位ジョブは、ジョブ管理装置によって実行する計算ノードに割り当てられ、割り当てられた計算ノードによって実行される。ジョブ管理装置は、ジョブを計算ノードに割り当てるため、空きノードを検索する。

例えば、図１５に示すように、計算ノード群５３０が、３次元メッシュネットワークにより接続されているとする。この場合、ジョブ管理装置は、図１６に示すように、空きノード５３１の検索処理を実行する。

ジョブ管理装置は、ジョブ割り当て情報リストのループを開始する（ステップＳ５０１）。具体的には、ジョブ管理装置は、予め定められた順に従って、１つのジョブ割り当て情報リストを選択する。

この後、ジョブ管理装置は、選択されたジョブ割り当て情報リストに定義されたジョブ、換言すれば、計算ジョブを割り当てるための６重ループ処理を開始する。

最初に、ジョブ管理装置は、計算ノード群５３０におけるｚ方向のループ、換言すれば、システムのｚ方向のループを開始する（ステップＳ５０２）。具体的には、ジョブ管理装置は、予め定められた順に従って、計算ノード群５３０におけるｚ方向の座標を選択する。計算ノード群５３０におけるｚ方向のループのループ範囲は、「１」から、「システムサイズ−ジョブサイズ＋１」までである。

次に、ジョブ管理装置は、計算ノード群５３０におけるｙ方向のループ、換言すれば、システムのｙ方向のループを開始する（ステップＳ５０３）。具体的には、ジョブ管理装置は、予め定められた順に従って、計算ノード群５３０におけるｙ方向の座標を選択する。計算ノード群５３０におけるｙ方向のループのループ範囲は、「１」から、「システムサイズ−ジョブサイズ＋１」までである。

次に、ジョブ管理装置は、計算ノード群５３０におけるｘ方向のループ、換言すれば、システムのｘ方向のループを開始する（ステップＳ５０４）。具体的には、ジョブ管理装置は、予め定められた順に従って、計算ノード群５３０におけるｘ方向の座標を選択する。計算ノード群５３０におけるｘ方向のループのループ範囲は、「１」から、「システムサイズ−ジョブサイズ＋１」までである。

ステップＳ５０２〜Ｓ５０４により、計算ノード群５３０におけるジョブ割り当ての開始点、換言すれば、開始ノード５３１が選択される。

次に、ジョブ管理装置は、ステップＳ５０１において選択したジョブ割り当て情報リストにおけるジョブサイズのｚ方向のループを開始する（ステップＳ５０５）。具体的には、ジョブ管理装置は、予め定められた順に従って、ジョブ割り当て情報リストにおけるジョブサイズのｚ方向における位置を選択する。ジョブサイズのｚ方向のループのループ範囲は、「１」から、「ジョブサイズ」までである。

次に、ジョブ管理装置は、ジョブ割り当て情報リストにおけるジョブサイズのｙ方向のループを開始する（ステップＳ５０６）。具体的には、ジョブ管理装置は、予め定められた順に従って、ジョブ割り当て情報リストにおけるジョブサイズのｙ方向における位置を選択する。ジョブサイズのｙ方向のループのループ範囲は、「１」から、「（ジョブサイズ）」までである。

次に、ジョブ管理装置は、ジョブ割り当て情報リストにおけるジョブサイズのｘ方向のループを開始する（ステップＳ５０７）。具体的には、ジョブ管理装置は、予め定められた順に従って、ジョブ割り当て情報リストにおけるジョブサイズのｘ方向における位置を選択する。ジョブサイズのｘ方向のループのループ範囲は、「１」から、「（ジョブサイズ）」までである。

ステップＳ５０５〜Ｓ５０７により、前述の開始点を基準として、ジョブ割り当て情報リストにおけるある位置に対応する計算ノード５３１が選択される。

次に、ジョブ管理装置は、選択した計算ノード５３１が空きノードであるか否かを判断する（ステップＳ５０８）。選択した計算ノード５３１が空きノードでない場合、換言すれば、選択した計算ノード５３１が割り当て済みノードである場合、ジョブ管理装置は、ステップＳ５０９〜Ｓ５１２を省略して、ステップＳ５１３を実行する。

選択した計算ノード５３１が空きノードである場合、ジョブ管理装置は、ジョブ割り当て情報リストにおけるジョブサイズのｘ方向のループを終了する（ステップＳ５０９）。具体的には、ジョブ管理装置は、ジョブサイズのｘ方向についての前述のループ範囲の実行が終了しない場合にはステップＳ５０７を繰り返し、ジョブサイズのｘ方向についての前述のループ範囲の実行が終了した場合にはステップＳ５１０を実行する。

次に、ジョブ管理装置は、ジョブ割り当て情報リストにおけるジョブサイズのｙ方向のループを終了する（ステップＳ５１０）。具体的には、ジョブ管理装置は、ジョブサイズのｙ方向についての前述のループ範囲の実行が終了しない場合にはステップＳ５０６を繰り返し、ジョブサイズのｙ方向についての前述のループ範囲の実行が終了した場合にはステップＳ５１１を実行する。

次に、ジョブ管理装置は、ジョブ割り当て情報リストにおけるジョブサイズのｚ方向のループを終了する（ステップＳ５１１）。具体的には、ジョブ管理装置は、ジョブサイズのｚ方向についての前述のループ範囲の実行が終了しない場合にはステップＳ５０５を繰り返し、ジョブサイズのｚ方向についての前述のループ範囲の実行が終了した場合にはステップＳ５１２を実行する。

次に、ジョブ管理装置は、以上の処理の結果、ジョブが計算ノード群５３０に割り当て可能であるか否かを判断する（ステップＳ５１２）。ジョブが計算ノード群５３０に割り当て可能である場合、ジョブ管理装置は、ステップＳ５１６を実行する。ジョブが計算ノード群５３０に割り当て可能でない場合、ジョブ管理装置は、ステップＳ５１３を実行する。

次に、ジョブ管理装置は、計算ノード群５３０におけるｘ方向のループを終了する（ステップＳ５１３）。具体的には、ジョブ管理装置は、計算ノード群５３０におけるｘ方向についての前述のループ範囲の実行が終了しない場合にはステップＳ５０４を繰り返す。計算ノード群５３０におけるｘ方向についての前述のループ範囲の実行が終了した場合には、ジョブ管理装置は、ステップＳ５１４を実行する。

次に、ジョブ管理装置は、計算ノード群５３０におけるｙ方向のループを終了する（ステップＳ５１４）。具体的には、ジョブ管理装置は、計算ノード群５３０におけるｙ方向についての前述のループ範囲の実行が終了しない場合にはステップＳ５０３を繰り返す。計算ノード群５３０におけるｙ方向についての前述のループ範囲の実行が終了した場合には、ジョブ管理装置は、ステップＳ５１５を実行する。

次に、ジョブ管理装置は、計算ノード群５３０におけるｚ方向のループを終了する（ステップＳ５１５）。具体的には、ジョブ管理装置は、計算ノード群５３０におけるｚ方向についての前述のループ範囲の実行が終了しない場合にはステップＳ５０２を繰り返す。計算ノード群５３０におけるｚ方向の前述のループ範囲の実行が終了した場合には、ジョブ管理装置は、ステップＳ５１６を実行する。

次に、ジョブ管理装置は、ジョブ割り当て情報リストのループを終了する（ステップＳ５１６）。具体的には、ジョブ管理装置は、現在のジョブ割り当て情報リストが最後か否かを調べ、最後でない場合にはステップＳ５０１を繰り返し、最後である場合には処理を終了する。

以上によれば、ジョブの開始点を定めるためには、計算ノード群５３０におけるｚ方向のループ、ｙ方向のループ、ｘ方向のループの３重のループの実行が必要になる。従って、合計で６重のループの実行が必要になる。また、ジョブを連続した直方体形状に割り当てるためには、ジョブ割り当て情報リストにおけるジョブサイズのｚ方向のループ、ｙ方向のループ、ｘ方向のループの３重のループの実行が必要になる。従って、６重のループの実行により、計算ノード群５３０へジョブが割り当てられる。

このため、計算ノード群５３０の規模が大きくなると、空きノード検索の６重ループの処理時間が大きくなる。これは、投入されたジョブの実行待ち時間が長くなる原因となり、また、計算ノード群５３０の稼動率が悪化する原因となる。

開示のジョブ管理装置及びジョブ管理方法は、並列処理を実行するコンピュータシステムにおいて、複数の単位ジョブを連続した長方形状又は直方体形状を割り当てる計算ノードである空きノードを、効率良く検索する。

（第１の実施態様）
図１及び図２は、ジョブ管理装置の構成を示す図である。図３は、ジョブ管理処理の説明図である。

並列コンピュータシステムは、図１に示すように、ジョブ管理装置１、利用者端末２、計算ノード群３を含む。ジョブ管理装置１は、利用者端末２と第１のネットワーク４を介して接続され、計算ノード群３と第２のネットワーク５を介して接続される。第１のネットワーク４と第２のネットワーク５とは、同一のネットワークであっても良い。

計算ノード群３は、図２（Ａ）のように接続された複数の計算ノード３１を含む。図２（Ａ）に示す計算ノード群３は、３次元メッシュ結合されたコンピュータネットワーク、換言すれば、３次元メッシュネットワークである。従って、図１の例において、計算ノード群３は、３次元メッシュネットワークである。３次元メッシュネットワークは、隣接する計算ノード３１のみが接続される結合である。

なお、計算ノード群３は、図２（Ｂ）に示すように、２次元トーラス結合されたコンピュータネットワーク、換言すれば、２次元トーラスネットワークであっても良い。２次元トーラスネットワークも、隣接する計算ノード３１のみが接続される結合である。なお、両端の計算ノード３１は、隣接すると考えてよい。また、計算ノード群３は、ｎ次元のコンピュータネットワークであって良い。ここで、ｎは２以上の整数である。

ジョブ管理装置１は、空きノード３１を検索して、検索結果に基づいて計算ノード３１にジョブを割り当てる。計算ノード群３におけるジョブの割り当てが可能な計算ノード３１を、空きノード３１ということとする。このために、ジョブ管理装置１は、ジョブ受付処理部１１、ジョブ実行制御部１２、記憶部１３、ジョブ割り当て処理部１４、計算ノード情報記憶部１５を含む。ジョブ受付処理部１１は割り当て情報生成部１１１を含む。記憶部１３は、Ｘ軸検索用情報記憶部１３１、ジョブ割り当て情報記憶部１３２、検索情報記憶部１３３を含む。ジョブ割り当て処理部１４は、空きノード検索部１４１、計算ノード管理部１４２を含む。計算ノード情報記憶部１５は３次元システム情報記憶部１５１を含む。

記憶部１３は、ジョブ受付処理部１１、ジョブ実行制御部１２、ジョブ割り当て処理部１４が使用するメモリである。計算ノード情報記憶部１５は計算ノード管理部１４２が使用するメモリである。ジョブ受付処理部１１、ジョブ実行制御部１２、ジョブ割り当て処理部１４は、処理プログラムにより実現される。

計算ノード管理部１４２は、計算ノード群３について、３次元システム情報１５１’を生成する。例えば、計算ノード管理部１４２は、構造情報と空き情報とに基づいて、図３（Ａ）に示す３次元システム情報１５１’を生成する。構造情報と空き情報は、計算ノード管理部１４２に入力され情報記憶部１５に保持される。生成された３次元システム情報１５１’は、計算ノード情報記憶部１５の３次元システム情報記憶部１５１に格納される。３次元システム情報１５１’については後述する。

構造情報は、計算ノード群３における各々の計算ノード３１の位置を示す。空き情報は、各々の計算ノード３１が「空き」であるか「使用中」であるかを示す。計算ノード群３における位置は、計算ノード群３のｘ方向の位置を示すｘ座標、ｙ方向の位置を示すｙ座標、ｚ方向の位置を示すｚ座標により表される。３次元システム情報において、空きノードは論理「１」で表され、使用中ノードは論理「０」で表される。

ジョブ受付処理部１１は、利用者端末２から送信されたジョブ投入コマンドを受信して実行する。換言すれば、ジョブ受付処理部１１は、受信したジョブ投入コマンドを受け付けて、ジョブ割り当て処理部１４に送る。

また、ジョブ受付処理部１１の割り当て情報生成部１１１は、ジョブ投入コマンドに基づいて、図３（Ｃ）に示すジョブ割り当て情報１３２’を生成して、ジョブ割り当て処理部１４に送信する。この時点でのジョブ割り当て情報１３２’は、後述するように、初期値を格納するのみである。ジョブ割り当て処理部１４は、受信したジョブ割り当て情報１３２’を、記憶部１３のジョブ割り当て情報記憶部１３２に格納する。ジョブ割り当て情報１３２’については後述する。

ジョブ割り当て処理部１４の空きノード検索部１４１は、計算ノード群３にジョブを割り当てる。具体的には、空きノード検索部１４１は、３次元システム情報１５１’に基づいて、図３（Ｂ）に示すｘ軸検索用情報１３１’を生成する。生成されたｘ軸検索用情報１３１’は、記憶部１３のｘ軸検索用情報記憶部１３１に格納される。ｘ軸検索用情報１３１’については後述する。

空きノード検索部１４１は、ジョブ割り当て情報１３２’に基づいて、図３（Ｄ）に示す検索情報１３３’を生成する。生成された検索情報１３３’は、記憶部１３の検索情報記憶部１３３に格納される。ジョブ割り当て情報１３２’については後述する。

検索情報１３３’は、後述するように、検索用マスクパターンを含む。検索用マスクパターンは、空きノード３１の検索に用いられる。

空きノード検索部１４１は、ｘ軸検索用情報１３１’と検索情報１３３’とを用いて、計算ノード群３における空きノード３１を検索する。この時、実際には、空きノード検索部１４１は、主として、ｘ軸検索用情報１３１’と検索用マスクパターンとを用いた論理演算を実行することにより、空きノード３１を検索する。空きノード検索部１４１は、空きノード３１の検索結果に基づいて、ジョブを空きノード３１に割り当てる。換言すれば、空きノード検索部１４１は、ジョブ割り当て情報１３２’を完成させて、ジョブ実行制御部１２に送信する。

ジョブ実行制御部１２は、受信したジョブ割り当て情報１３２’に基づいて、ジョブの実行を制御する。換言すれば、ジョブ実行制御部１２は、ジョブを割り当てられた計算ノード３１にジョブを実行させる。

以下、並列コンピュータシステムにおけるジョブ割り当て処理について、図４〜図９を参照して具体的に説明する。

図４は、３次元システム情報の一例を示す。

計算ノード管理部１４２は、図４に示すように、計算ノード群３の計算ノード３１の各々について、３次元システム情報１５１’を生成する。３次元システム情報１５１’は、実際には、３次元の配列により計算ノード群３の構造を表したものである。

図３（Ａ）の３次元システム情報１５１’において、［ｓｙｓｔｅｍＸ］は計算ノード群３のｘ方向の範囲となる値を取り、［ｓｙｓｔｅｍＹ］は計算ノード群３のｙ方向の範囲となる値を取り、［ｓｙｓｔｅｍＺ］は計算ノード群３のｚ方向の範囲となる値を取る。このために、計算ノード管理部１４２は、構造情報に基づいて、複数の計算ノード３１のｘ座標の中の最小値〜最大値を［ｓｙｓｔｅｍＸ］とし、複数の計算ノード３１のｙ座標の中の最小値〜最大値を［ｓｙｓｔｅｍＹ］とし、複数の計算ノード３１のｚ座標の中の最小値〜最大値を［ｓｙｓｔｅｍＺ］とする。これにより、図４に示すように、計算ノード群３を直方体の形状として表すことができる。

例えば、図４において、ｘ座標は０〜７であり、ｙ座標は０〜７であり、ｚ座標は０〜７である。従って、［ｓｙｓｔｅｍＸ］の最大値が８、［ｓｙｓｔｅｍＹ］の最大値が８、［ｓｙｓｔｅｍＺ］の最大値が８である。この場合、計算ノード群３の構成は、８×８×８となる。［ｓｙｓｔｅｍＸ］、［ｓｙｓｔｅｍＹ］、［ｓｙｓｔｅｍＺ］の範囲は、相互に異なっていても良い。

また、３次元システム情報１５１’は、計算ノード群３に含まれる各々の計算ノード３１についての空きノード情報を含む。空きノード情報は、当該計算ノード３１が空きノードであることを示す論理「１」、又は、当該計算ノード３１が使用中ノードであることを示す論理「０」のいずれか一方である。

図５は、ｘ軸検索用情報の一例を示す。

空きノード検索部１４１は、図５に示すように、３次元システム情報１５１’に基づいて、ｘ軸検索用情報１３１’を生成する。ｘ軸検索用情報１３１’は、３次元の中の１つの次元についての検索用情報である。換言すれば、ｘ軸検索用情報１３１’は１次元検索用情報である。１次元検索用情報は、複数のビットを含む。ｘ軸検索用情報１３１’は、３次元の中の１つの次元であるｘ軸に属する複数の計算ノードの各々について、ジョブの割り当てが可能か否かを１ビットの情報で示す。換言すれば、ｘ軸検索用情報１３１’は、３次元システム情報１５１’における配列ｘの複数の要素の各々を1ビットで表現し、かつ、配列ｘの複数の要素を１つの変数で格納するものである。

なお、ｘ軸検索用情報１３１’に代えて、ｙ軸検索用情報又はｚ軸検索用情報を生成するようにしても良い。

図３（Ｂ）のｘ軸検索用情報１３１’において、ｘは、計算ノード群３のｘ方向の全ての値である。一方、［ｓｙｓｔｅｍＹ］は計算ノード群３のｙ方向の範囲となる値を取り、［ｓｙｓｔｅｍＺ］は計算ノード群３のｚ方向の範囲となる値を取る。従って、ｘ軸検索用情報１３１’は、複数のｘ軸検索用情報１３１Ａ、１３１Ｂ、・・・を含む。換言すれば、ｘ軸検索用情報１３１’は、ｘ座標が異なりかつ共通の座標（ｙ，ｚ）を有する計算ノード３１毎に生成される。また、ｘ軸検索用情報１３１’の数は、［ｓｙｓｔｅｍＹ］×［ｓｙｓｔｅｍＺ］である。

例えば、ｘ軸検索用情報１３１Ａは、共通の座標（ｙ，ｚ）＝（０，０）を有する計算ノード３１についての情報である。ｘ軸検索用情報１３１Ａは、図５に示すように、座標（ｘ，ｙ，ｚ）＝（０，０，０）から座標（ｘ，ｙ，ｚ）＝（７，０，０）までの複数の計算ノード３１についての、空きノード情報を含む。例えば、座標（０，０，０）の計算ノード３１が空きノードである場合、ｘ軸検索用情報１３１Ａのｂｉｔ７は「１」とされる。ｂｉｔ６〜ｂｉｔ０も、空きノード情報に従って定まる。ｘ軸検索用情報１３１Ａのビットの数は、［ｓｙｓｔｅｍＸ］、換言すれば、計算ノード群３のｘ方向の範囲に一致し、図５においては８ビットである。

ｘ軸検索用情報１３１’を用いることにより、計算ノード群３は、図５に示す計算ノード群３’として表される。計算ノード群３’は、個々の要素が８ビットのデータ列である、ｙ方向及びｚ方向の２次元の配列により、３次元の計算ノード群３を置換したものである。

図６は、検索用マスクパターンの一例を示す。

空きノード検索部１４１は、図６に示すように、検索用マスクパターン１３４を生成する。検索用マスクパターン１３４は、ｘ軸検索用情報１３１Ａにおける複数のビットに対応するビット数を含む。換言すれば、検索用マスクパターン１３４のビットの数は、ｘ軸検索用情報１３１Ａのビットの数と同一とされる。検索用マスクパターン１３４は、３次元の中の１つの次元についてジョブが要求するサイズに対応する連続ビットを予め定められた値に設定されたものである。換言すれば、検索用マスクパターン１３４は、ｘ軸検索用情報１３１Ａと同一の座標軸について生成される。従って、図６の検索用マスクパターン１３４は、ｘ軸の検索用である。

なお、ｘ軸検索用情報１３１’に代えてｙ軸検索用情報又はｚ軸検索用情報が生成された場合には、検索用マスクパターン１３４に代えてｙ軸の検索用のマスクパターン又はｚ軸の検索用のマスクパターンが生成される。

前述したように、検索用マスクパターン１３４は検索情報１３３’に含まれ、検索情報１３３’はジョブ割り当て情報１３２’に基づいて生成される。そこで、まず、図３（Ｃ）に示すジョブ割り当て情報１３２’について説明する。

図３（Ｃ）のジョブ割り当て情報１３２’において、ジョブの開始座標（ｘ）は図３（Ａ）の［ｓｙｓｔｅｍＸ］の最小値であり、ジョブの開始座標（ｙ）は図３（Ａ）の［ｓｙｓｔｅｍＹ］の最小値であり、ジョブの開始座標（ｚ）は図３（Ａ）の［ｓｙｓｔｅｍＺ］の最小値である。なお、［ｓｙｓｔｅｍＸ］の最小値、［ｓｙｓｔｅｍＹ］の最小値、［ｓｙｓｔｅｍＺ］の最小値は、いずれも「０」とされる。換言すれば、ジョブの割り当ては、（０，０，０）の座標を有する計算ノード３１から順に判断される。

また、図３（Ｃ）のジョブ割り当て情報１３２’において、ジョブの形状（ｘ）はジョブのｘ方向のサイズであり、ジョブの形状（ｙ）はジョブのｙ方向のサイズであり、ジョブの形状（ｚ）はジョブのｚ方向のサイズである。ジョブの形状（ｘ）、ジョブの形状（ｙ）及びジョブの形状（ｚ）は、利用者端末２から入力されたジョブ投入コマンドにおいて指示される。

ジョブの全体の要求形状６は、ジョブの形状（ｘ）、ジョブの形状（ｙ）及びジョブの形状（ｚ）に基づいて定まる。例えば、ジョブの形状（ｘ）が「４」であり、ジョブの形状（ｙ）が「４」であり、ジョブの形状（ｚ）が「４」である場合、ジョブの全体の要求形状６は、図６に示すように定まる。この時、ジョブの全体の要求形状６を「ジョブの形状（ｘ）×ジョブの形状（ｙ）×ジョブの形状（ｚ）」と表すとすると、この場合のジョブの全体の要求形状６は、「４×４×４」である。換言すれば、ジョブの全体の要求形状６は、「４×４×４」のジョブの要求の要素６１を含む。各々のジョブの要求の要素６１は、各々の計算ノード３１に対応し、かつ、割り当てられる。

また、図３（Ｃ）のジョブ割り当て情報１３２’において、割り当て可能フラグは、当該ジョブが計算ノード群３に割り当て可能である場合には「１」とされ、割り当て不可能である場合には「０」とされる。この時点では、割り当て可能フラグは、割り当て可能か否かが不明であるので、「０」とされる。

ここで、ジョブが要求する計算ノード３１の数、換言すれば、ジョブを分割した単位ジョブの数が、例えば「６４」であるとする。この場合、「６４」を満足するジョブの全体の形状６の組合せは、複数存在し得る。具体的には、ジョブの全体の要求形状６は、「４×４×４」、「２×８×４」、「２×２×１６」のいずれであっても良い。

そこで、割り当て情報生成部１１１は、実際には、ジョブ割り当て情報１３２’として、複数のジョブ割り当て情報リストを生成する。生成されるジョブ割り当て情報リストの数は、ジョブの全体の形状６の組合せの数である。

複数のジョブ割り当て情報リストにおいては、ジョブの形状（ｘ）、ジョブの形状（ｙ）及びジョブの形状（ｚ）のみが相互に異なる。例えば、第１のジョブ割り当て情報リストにおいては、ジョブの形状（ｘ）が「４」、ジョブの形状（ｙ）が「４」、ジョブの形状（ｚ）が「４」とされ、第２のジョブ割り当て情報リストにおいては、ジョブの形状（ｘ）が「２」、ジョブの形状（ｙ）が「８」、ジョブの形状（ｚ）が「４」とされ、第３のジョブ割り当て情報リストにおいては、ジョブの形状（ｘ）が「２」、ジョブの形状（ｙ）が「２」、ジョブの形状（ｚ）が「１６」とされる。複数のジョブ割り当て情報リストの各々について、検索情報１３３’が生成され、ジョブの割り当てが可能か否かが検索される。

次に、図３（Ｄ）の検索情報１３３’において、ジョブの開始座標（ｘ）はジョブ割り当て情報１３２’におけるジョブの開始座標（ｘ）から得られ、ジョブの開始座標（ｙ）はジョブ割り当て情報１３２’におけるジョブの開始座標（ｙ）から得られ、ジョブの開始座標（ｚ）はジョブ割り当て情報１３２’におけるジョブの開始座標（ｚ）から得られる。ジョブの開始座標（ｙ）は並列コンピュータシステムにおけるｙ方向のループの初期値として用いられ、ジョブの開始座標（ｚ）は並列コンピュータシステムにおけるｚ方向のループの初期値として用いられる。

また、図３（Ｄ）の検索情報１３３’において、ジョブの形状（ｘ）はジョブ割り当て情報１３２’におけるジョブの形状（ｘ）から得られ、ジョブの形状（ｙ）はジョブ割り当て情報１３２’におけるジョブの形状（ｙ）から得られ、ジョブの形状（ｚ）はジョブ割り当て情報１３２’におけるジョブの形状（ｚ）から得られる。ジョブの形状（ｘ）、ジョブの形状（ｙ）及びジョブの形状（ｚ）は、固定である。

また、図３（Ｄ）の検索情報１３３’において、検索用マスクパターンは、図６に示す検索用マスクパターン１３４として得られる。前述したように、検索用マスクパターン１３４のビットの数は、ｘ軸検索用情報１３１Ａのビットの数と同一とされる。従って、図４及び図５の計算ノード群３を検索するための検索用マスクパターン１３４のビットの数は「８」である。

一方、ジョブの全体の要求形状６において、例えば、図６に示すように、ジョブの形状（ｘ）が「４」であり、ジョブの形状（ｙ）が「４」であり、ジョブの形状（ｚ）が「４」であるとする。従って、前述したように、検索用マスクパターン１３４は、ｘ軸について、ジョブが要求するサイズ「４」に対応する連続ビットｂｉｔ７〜ｂｉｔ４を、予め定められた値「０」に設定することにより得られる。この時、検索用マスクパターン１３４において、先頭のビットｂｉｔ７から連続する４ビットが「０」とされる。これにより、ｘ軸の方向において、連続した空きノード３１を検出することができる。また、この時、ジョブが割り当て要求するサイズ以外のサイズ、換言すれば、ジョブの割り当ての範囲外の計算ノード３１に対応するビットであるｂｉｔ３〜ｂｉｔ０を「１」とする。ジョブの割り当ての範囲外の計算ノード３１は、ジョブの割り当て処理において無視される範囲である。なお、ｘ軸についてジョブが要求するサイズ「４」が、ジョブの全体の要求形状６における、ジョブの部分形状６２に対応する。

図７は、空きノードの検索の一例を示す。

空きノード検索部１４１は、ｘ軸について、ｘ軸検索用情報１３１’と検索用マスクパターン１３４とを用いて予め定められた論理演算を実行することにより、空きノード３１を検索する。このために、前述したように、ｘ軸検索用情報１３１’において、使用中ノードを「０」で表し、空きノードを「１」で表す。また、検索用マスクパターン１３４において、割り当て要求する計算ノードを「０」で表し、割り当て範囲外のノードを「１」で表す。

従って、図７に示すように、使用中である計算ノード３１について割り当て要求を無視して良い場合、換言すれば、ビットの値が「０」である計算ノード３１について検索用マスクパターン１３４のビットの値が「１」である場合には、どのように判定しても良いので、割り当てが可能であると判定することとする。

ここで、割り当てが可能である場合を「１」で表し、割り当てが不可能である場合を「０」で表すこととする。このように表す場合、使用中を示す「０」と無視を示す「１」との論理和（ＯＲ演算）により求められる演算結果「１」を用いて、割り当てが可能であると判定することができる。

なお、割り当てが可能であるかの演算は、論理和に限られない。従って、図７に示す判定の論理の設定に応じて、種々の論理演算を用いることができる。

また、使用中である計算ノード３１について割り当て要求がある場合、換言すれば、ビットの値が「０」である計算ノード３１について検索用マスクパターン１３４のビットの値が「０」である場合には、割り当てが不可能であると判定する。これは、本来の割り当てが不可能な場合である。この場合、使用中を示す「０」と割り当て要求を示す「０」との論理和により求められる演算結果「０」を用いて、割り当てが不可能であると判定することができる。

また、空きである計算ノード３１について割り当て要求を無視して良い場合、換言すれば、ビットの値が「１」である計算ノード３１について検索用マスクパターン１３４のビットの値が「１」である場合には、どのように判定しても良いので、割り当てが可能であると判定することとする。この場合、空きを示す「１」と無視を示す「１」との論理和により求められる演算結果「１」を用いて、割り当てが可能であると判定することができる。

また、空きである計算ノード３１について割り当て要求がある場合、換言すれば、ビットの値が「１」である計算ノード３１について検索用マスクパターン１３４のビットの値が「０」である場合には、割り当てが可能であると判定する。これは、本来の割り当てが可能な場合である。この場合、空きを示す「１」と割り当て要求を示す「０」との論理和により求められる演算結果「１」を用いて、割り当てが可能であると判定することができる。

図８及び図９は、ジョブの割り当てについての判定の一例を示す。なお、図８及び図９に示す例は、検索用マスクパターン１３４におけるシフト処理の説明の便宜のために、図４〜図６に示す例とは異なる。

空きノード検索部１４１は、以上に述べた論理和の演算結果が「０」である場合、検索用マスクパターン１３４におけるシフト処理を実行する。ここで、論理和の演算結果が「０」である場合とは、ｘ軸検索用情報１３１’と検索用マスクパターン１３４との論理和が、ｘ軸について、ジョブの割り当てが不可能であることを示す場合である。検索用マスクパターン１３４におけるシフト処理とは、例えば、ジョブが要求するサイズ「４」に対応する連続ビットｂｉｔ７〜ｂｉｔ４を、予め定められた方向に１ビットだけシフトすることである。予め定められた方向とは、ｘ軸方向の座標値が増す方向、換言すれば、ｂｉｔ０に向かう方向である。

例えば、ｘ軸検索用情報１３１Ｃにおいて、図８（Ａ）に示すように、ｂｉｔ７〜ｂｉｔ５が「０」であり、ｂｉｔ４〜ｂｉｔ２が「１」であり、ｂｉｔ１〜ｂｉｔ０が「０」であるとする。この状態は、ｂｉｔ７〜ｂｉｔ５に対応する計算ノード３１が使用中であり、ｂｉｔ４〜ｂｉｔ２に対応する計算ノード３１が空きであり、ｂｉｔ１〜ｂｉｔ０に対応する計算ノード３１が使用中である状態である。

また、例えば、検索用マスクパターン１３４Ｂにおいて、図８（Ｂ）に示すように、ｂｉｔ７〜ｂｉｔ５が「０」であり、ｂｉｔ４〜ｂｉｔ０が「１」であるとする。この状態は、ｂｉｔ７〜ｂｉｔ５に対応する計算ノード３１が割り当て要求の対象であり、ｂｉｔ４〜ｂｉｔ０に対応する計算ノード３１が割り当てに無関係であり無視して良い状態である。

空きノード検索部１４１は、図８（Ａ）のｘ軸検索用情報１３１Ｃと、図８（Ｂ）の検索用マスクパターン１３４Ｂとの論理和を求める。この論理和の演算結果は、図８（Ｃ）に示すように、ｂｉｔ７〜ｂｉｔ５が「０」となり、ｂｉｔ４〜ｂｉｔ０が「１」となる。従って、ｂｉｔ７〜ｂｉｔ５が割り当て不可能であり、ｂｉｔ４〜ｂｉｔ０が割り当て可能であることが求められる。

ここで、前述したように、ｂｉｔ７〜ｂｉｔ５に対応する計算ノード３１が割り当て要求の対象であり、ｂｉｔ４〜ｂｉｔ０に対応する計算ノード３１は割り当てに無関係である。従って、割り当て要求の対象であるｂｉｔ７〜ｂｉｔ５に対応する計算ノード３１について、ジョブを割り当てることができない。

そこで、空きノード検索部１４１は、図８（Ｂ）の検索用マスクパターン１３４Ｂにおける、ジョブが要求するサイズ「３」に対応する連続ビットｂｉｔ７〜ｂｉｔ５を、ｂｉｔ０の方向に１ビットだけシフトする。これにより、図８（Ｄ）の検索用マスクパターン１３４Ｃが得られる。

検索用マスクパターン１３４Ｂにおけるシフト処理の後、空きノード検索部１４１は、ｘ軸検索用情報１３１’とシフトされた検索用マスクパターン１３４Ｃとを用いて論理和を求めることにより、再度、空きノードを検索する。

図８（Ａ）のｘ軸検索用情報１３１Ｃと、図８（Ｄ）の検索用マスクパターン１３４Ｃとの論理和の演算結果は、図８（Ｅ）に示すように、ｂｉｔ７が「１」となり、ｂｉｔ６〜ｂｉｔ５が「０」となり、ｂｉｔ４〜ｂｉｔ０が「１」となる。従って、ｂｉｔ７が割り当て可能であり、ｂｉｔ６〜ｂｉｔ５が割り当て不可能であり、ｂｉｔ４〜ｂｉｔ０が割り当て可能であることが求められる。

ここで、前述したように、ｂｉｔ７〜ｂｉｔ５に対応する計算ノード３１が割り当て要求の対象であり、ｂｉｔ４〜ｂｉｔ０に対応する計算ノード３１は割り当てに無関係である。従って、割り当て要求の対象であるｂｉｔ７〜ｂｉｔ５に対応する計算ノード３１について、ジョブを割り当てることができない。

そこで、空きノード検索部１４１は、図８（Ｄ）の検索用マスクパターン１３４Ｃにおける、ジョブが要求するサイズ「３」に対応する連続ビットｂｉｔ６〜ｂｉｔ４を、ｂｉｔ０の方向に１ビットだけシフトする。これにより、図９（Ａ）の検索用マスクパターン１３４Ｄが得られる。

検索用マスクパターン１３４Ｃにおけるシフト処理の後、空きノード検索部１４１は、ｘ軸検索用情報１３１’とシフトされた検索用マスクパターン１３４Ｄとを用いて論理和を求めることにより、再度、空きノードを検索する。

図８（Ａ）のｘ軸検索用情報１３１Ｃと、図９（Ａ）の検索用マスクパターン１３４Ｄとの論理和の演算結果は、図９（Ｂ）に示すように、ｂｉｔ７〜ｂｉｔ６が「１」となり、ｂｉｔ５が「０」となり、ｂｉｔ４〜ｂｉｔ０が「１」となる。従って、ｂｉｔ７〜ｂｉｔ６が割り当て可能であり、ｂｉｔ５が割り当て不可能であり、ｂｉｔ４〜ｂｉｔ０が割り当て可能であることが求められる。

ここで、前述したように、ｂｉｔ７〜ｂｉｔ５に対応する計算ノード３１が割り当て要求の対象であり、ｂｉｔ４〜ｂｉｔ０に対応する計算ノード３１は割り当てに無関係である。従って、割り当て要求の対象であるｂｉｔ７〜ｂｉｔ５に対応する計算ノード３１について、ジョブを割り当てることができない。

そこで、空きノード検索部１４１は、図９（Ａ）の検索用マスクパターン１３４Ｄにおける、ジョブが要求するサイズ「３」に対応する連続ビットｂｉｔ５〜ｂｉｔ３を、ｂｉｔ０の方向に１ビットだけシフトする。これにより、図９（Ｃ）の検索用マスクパターン１３４Ｅが得られる。

検索用マスクパターン１３４Ｄにおけるシフト処理の後、空きノード検索部１４１は、ｘ軸検索用情報１３１’とシフトされた検索用マスクパターン１３４Ｅとを用いて論理和を求めることにより、再度、空きノードを検索する。

図８（Ａ）のｘ軸検索用情報１３１Ｃと、図９（Ｃ）の検索用マスクパターン１３４Ｅとの論理和の演算結果は、図９（Ｄ）に示すように、ｂｉｔ７〜ｂｉｔ０が「１」となる。従って、ｂｉｔ７〜ｂｉｔ０が割り当て可能であることが求められる。

ここで、前述したように、ｂｉｔ７〜ｂｉｔ５に対応する計算ノード３１が割り当て要求の対象であり、ｂｉｔ４〜ｂｉｔ０に対応する計算ノード３１は割り当てに無関係である。従って、割り当て要求の対象であるｂｉｔ７〜ｂｉｔ５に対応する計算ノード３１について、ジョブを割り当てることができる。

以上は、ｘ軸についての検索情報である。空きノード検索部１４１は、ｘ軸以外の残りのｙ軸及びｚ軸について、空きノード３１か否かの判定処理を、開始点から予め定められた順に繰り返すことにより、空きノード３１を検索する。

これにより、ジョブの開始点を定めるための処理を、並列コンピュータシステムにおけるｚ方向のループとｙ方向のループのみとして、ｘ方向のループを省略することができる。また、ジョブを連続した直方体形状に割り当てるための処理を、ジョブサイズのｚ方向のループとｙ方向のループのみとして、ｘ方向のループを省略することができる。従って、６重のループではなく、４重のループの実行により、並列コンピュータシステムへジョブが割り当てられる。従って、投入されたジョブの実行待ち時間を短縮することができ、また、並列コンピュータシステムの稼動率を向上することができる。

図１０は、ジョブ管理処理フローである。

空きノード検索部１４１は、初期化処理を実行して、３次元システム情報１５１’に基づいて、ｘ軸検索用情報１３１’を生成する（ステップＳ１０）。

次に、空きノード検索部１４１は、ジョブ割り当て情報リストのループを開始する（ステップＳ１１）。ジョブ割り当て情報リストのループは、ジョブ割り当て情報１３２’に含まれる複数のジョブ割り当てリストの数分のループ制御を行う処理である。具体的には、空きノード検索部１４１は、予め定められた順に従って、ジョブ割り当て情報１３２’の中から１つのジョブ割り当て情報リストを選択する。この時点では、ジョブ割り当て情報１３２’であるジョブ割り当て情報リストにおいて、割り当て可能フラグは、不可能（ｆａｌｓｅ）が設定されている。

この後、空きノード検索部１４１は、選択されたジョブ割り当て情報リストに定義されたジョブ、換言すれば、計算ジョブを割り当てるための４重ループ処理を開始する。

最初に、空きノード検索部１４１は、計算ノード群３、換言すれば、並列コンピュータシステムにおけるｚ方向のループを開始する（ステップＳ１２）。具体的には、空きノード検索部１４１は、予め定められた順に従って、計算ノード群３におけるｚ方向の座標を選択する。なお、計算ノード群３におけるｚ方向のループを「システムのｚループ」と言うこととする。システムのｚループは、検索の開始点をｚ方向に制御するループである。システムのｚループのループ範囲は、「１」から、「システムサイズ−ジョブサイズ＋１」までである。

次に、空きノード検索部１４１は、計算ノード群３、換言すれば、並列コンピュータシステムにおけるｙ方向のループを開始する（ステップＳ１３）。具体的には、空きノード検索部１４１は、予め定められた順に従って、計算ノード群３におけるｙ方向の座標を選択する。これにより、１個のｘ軸検索用情報１３１’が選択される。なお、計算ノード群３におけるｙ方向のループを「システムのｙループ」と言うこととする。システムのｙループは、検索の開始点をｙ方向に制御するループである。システムのｙループのループ範囲は、「１」から、「システムサイズ−ジョブサイズ＋１」までである。

ステップＳ１２〜Ｓ１３により、計算ノード群３におけるジョブ割り当ての開始点、換言すれば、開始点についてのｘ軸検索用情報１３１’が選択される。

次に、空きノード検索部１４１は、選択されたｘ軸検索用情報１３１’において、空きノード３１の数が、ジョブが要求する計算ノード３１の数未満であるか否かを判断する（ステップＳ１４）。具体的には、空きノード検索部１４１は、ｘ軸検索用情報１３１’における「１」の数をカウントし、カウント値とｘ方向のジョブサイズとを比較する。空きノード３１の数がジョブサイズ未満の場合、空きノード３１の検索処理が無駄になることを回避して、処理時間を短縮することができる。

空きノード３１の数がジョブが要求する計算ノード３１の数未満である場合（ステップＳ１４ Ｙｅｓ）、空きノード検索部１４１は、ステップＳ１１５を実行する。

空きノード３１の数がジョブが要求する計算ノード３１の数未満でない場合（ステップＳ１４ Ｎｏ）、空きノード検索部１４１は、検索情報１３３’を初期化する（ステップＳ１５）。

具体的には、空きノード検索部１４１は、検索情報１３３’において、ジョブの開始座標（ｘ）、ジョブの開始座標（ｙ）及びジョブの開始座標（ｚ）に「０」を設定する。また、空きノード検索部１４１は、検索情報１３３’において、ジョブの形状（ｘ）にジョブ割り当て情報１３２’におけるジョブの形状（ｘ）を設定し、ジョブの形状（ｙ）にジョブ割り当て情報１３２’におけるジョブの形状（ｙ）を設定し、ジョブの形状（ｚ）にジョブ割り当て情報１３２’におけるジョブの形状（ｚ）を設定する。更に、空きノード検索部１４１は、検索情報１３３’において、検索用マスクパターン１３４を生成する。検索用マスクパターン１３４は、最左端のｂｉｔ７から順にジョブの形状（ｘ）の数の分の「０」を設定し、残りのｂｉｔに「１」を設定する。これにより、例えば図６に示す検索用マスクパターン１３４が得られる。更に、空きノード検索部１４１は、検索情報１３３’において、シフト総数に「０」を設定し、シフト数に「０」を設定する。

次に、空きノード検索部１４１は、検索用マスクパターン１３４において、ジョブの形状（ｘ）の数の分の「０」を、検索情報１３３’におけるシフト数だけ、ｂｉｔ０の方向へシフトする、換言すれば、右シフトする（ステップＳ１６）。シフト数が「０」である場合には、シフト処理は実行されない。従って、シフト数が初期値である場合、シフト処理は実行されない。空きノード検索部１４１は、検索情報１３３’において、シフト総数にシフト数を加算する。

なお、計算ノード群３が図２（Ｂ）に示すトーラス結合されたコンピュータネットワークである場合において、シフト総数とｘ方向のジョブサイズとの合計がｘ軸検索用情報１３１’又は検索用マスクパターン１３４のサイズ以上になった場合、図１３を参照して後述するように処理される。

次に、空きノード検索部１４１は、ｘ軸検索用情報１３１’と検索用マスクパターン１３４とを用いた論理和演算を実行することにより、ジョブが割り当て可能か否かを判断する（ステップＳ１７）。

ジョブの割り当てが可能でない場合（ステップＳ１７ Ｎｏ）、空きノード検索部１４１は、シフト数に＋１を加算した後に、ジョブの形状（ｘ）の数の分の「０」についての次回のシフトが、右シフトの上限か否かを判断する（ステップＳ１８）。次回のシフトが右シフトの上限である場合（ステップＳ１８ Ｙｅｓ）、空きノード検索部１４１は、ステップＳ１１５を実行する。次回のシフトが右シフトの上限でない場合（ステップＳ１８ Ｎｏ）、空きノード検索部１４１は、ステップＳ１６を実行する。

ここで、右シフトの上限とは、計算ノード群３が図２（Ａ）のメッシュ結合である場合、シフト総数とｘ方向のジョブサイズとの合計がｘ軸検索用情報１３１’又は検索用マスクパターン１３４のサイズ以上となった場合である。換言すれば、シフト総数とｘ方向のジョブサイズとの合計がｘ軸検索用情報１３１’又は検索用マスクパターン１３４のサイズ未満の場合は、右シフトの上限ではない。

例えば、図６の検索用マスクパターン１３４において、ｘ方向のジョブサイズが「４」であり、検索用マスクパターン１３４のサイズが「８」である。従って、シフト総数が「３」以下であれば右シフトの上限とならず、シフト総数が「４」以上であれば右シフトの上限となる。

また、計算ノード群３が図２（Ｂ）のトーラス結合である場合において、シフト総数がｘ軸検索用情報１３１’又は検索用マスクパターン１３４のサイズ未満の場合には、右シフトの上限ではないので、ステップＳ１６が実行される。シフト総数がｘ軸検索用情報１３１’又は検索用マスクパターン１３４のサイズ以上の場合には、右シフトの上限であり、ステップＳ１１５が実行される。

ステップＳ１７において、ジョブの割り当てが可能である場合（ステップＳ１７ Ｙｅｓ）、空きノード検索部１４１は、ステップＳ１１において選択したジョブ割り当て情報リストにおけるジョブサイズのｚ方向のループを開始する（ステップＳ１９）。具体的には、空きノード検索部１４１は、予め定められた順に従って、ジョブ割り当て情報リストにおけるジョブサイズのｚ方向における位置を選択する。なお、ジョブ割り当て情報リストにおけるｚ方向のループを「ジョブサイズのｚループ」と言うこととする。ジョブサイズのｚループは、検索マスクパターン１３４による空きノードの検索をｚ方向に制御するループである。ジョブサイズのｚループのループ範囲は、「１」から、「ジョブサイズ」までである。

次に、空きノード検索部１４１は、ジョブ割り当て情報リストにおけるジョブサイズのｙ方向のループを開始する（ステップＳ１１０）。具体的には、空きノード検索部１４１は、予め定められた順に従って、ジョブ割り当て情報リストにおけるジョブサイズのｙ方向における位置を選択する。なお、ジョブ割り当て情報リストにおけるｙ方向のループを「ジョブサイズのｙループ」と言うこととする。ジョブサイズのｙループは、検索マスクパターン１３４による空きノードの検索をｙ方向に制御するループである。ジョブサイズのｙループのループ範囲は、「１」から、「ジョブサイズ」までである。ステップＳ１９〜Ｓ１１０により、前述の開始点を基準として、ジョブ割り当て情報リストにおけるある位置に対応するｘ軸検索用情報１３１’が選択される。

次に、空きノード検索部１４１は、ｘ軸検索用情報１３１’と検索用マスクパターン１３４とを用いた論理和演算を実行することにより、ジョブが割り当て可能か否かを判断する（ステップＳ１１１）。

ジョブの割り当てが可能でない場合（ステップＳ１１１ Ｎｏ）、空きノード検索部１４１は、シフト数に＋１を加算した後に、ジョブの形状（ｘ）の数の分の「０」についての次回のシフトが、右シフトの上限か否かを判断する（ステップＳ１１８）。次回のシフトが右シフトの上限である場合（ステップＳ１１８ Ｙｅｓ）、空きノード検索部１４１は、ステップＳ１１５を実行する。次回のシフトが右シフトの上限でない場合（ステップＳ１１８ Ｎｏ）、空きノード検索部１４１は、ステップＳ１６を実行する。右シフトの上限については前述した通りである。

ステップＳ１１１において、ジョブの割り当てが可能である場合（ステップＳ１１１ Ｙｅｓ）、次に、空きノード検索部１４１は、ジョブ割り当て情報リストにおけるジョブサイズのｙ方向のループを終了する（ステップＳ１１２）。具体的には、空きノード検索部１４１は、ジョブサイズのｙ方向についての前述のループ範囲の実行が終了しない場合にはステップＳ１１０を繰り返し、ジョブサイズのｙ方向についての前述のループ範囲の実行が終了した場合にはステップＳ１１３を実行する。

次に、空きノード検索部１４１は、ジョブ割り当て情報リストにおけるジョブサイズのｚ方向のループを終了する（ステップＳ１１３）。具体的には、空きノード検索部１４１は、ジョブサイズのｚ方向についての前述のループ範囲の実行が終了しない場合にはステップＳ１９を繰り返し、ジョブサイズのｚ方向についての前述のループ範囲の実行が終了した場合にはステップＳ１１４を実行する。

次に、空きノード検索部１４１は、図６のジョブの要求形状６の全体が割り当て可能か否かを判断する（ステップＳ１１４）。図６のジョブの要求形状６の全体の割り当てが可能である場合、空きノード検索部１４１は、ステップＳ１１７を実行する。

図６のジョブの要求形状６の全体の割り当てが可能でない場合、空きノード検索部１４１は、計算ノード群３におけるｙ方向のループを終了する（ステップＳ１１５）。具体的には、空きノード検索部１４１は、計算ノード群３におけるｙ方向についての前述のループ範囲の実行が終了しない場合にはステップＳ１３を繰り返す。計算ノード群３におけるｙ方向についての前述のループ範囲の実行が終了した場合には、空きノード検索部１４１は、ステップＳ１１６を実行する。

次に、空きノード検索部１４１は、計算ノード群３におけるｚ方向のループを終了する（ステップＳ１１６）。具体的には、空きノード検索部１４１は、計算ノード群３におけるｚ方向についての前述のループ範囲の実行が終了しない場合にはステップＳ１２を繰り返す。計算ノード群３におけるｚ方向の前述のループ範囲の実行が終了した場合には、空きノード検索部１４１は、ステップＳ１１７を実行する。

次に、空きノード検索部１４１は、ジョブ割り当て情報リストのループを終了する（ステップＳ１１７）。具体的には、空きノード検索部１４１は、現在のジョブ割り当て情報リストが最後か否かを調べ、最後でない場合にはステップＳ１１を繰り返し、最後である場合には処理を終了する。この時、空きノード検索部１４１は、ジョブ割り当て情報１３２’のジョブ割り当て情報の形状（ｘ）に検索情報１３３’のジョブの形状（ｘ）を設定し、ジョブ割り当て情報１３２’のジョブ割り当て情報の形状（ｙ）に検索情報１３３’のジョブの形状（ｙ）を設定し、ジョブ割り当て情報１３２’のジョブ割り当て情報の形状（ｚ）に検索情報１３３’のジョブの形状（ｚ）を設定する。また、空きノード検索部１４１は、ジョブ割り当て情報１３２’の割り当て可能フラグに「可能（ｔｒｕｅ）」を設定する。

図１１は、ループ数の削減効果の一例を示す。

図１１において、計算ノード群３におけるｚ方向のサイズが「ｓｙｓｔｅｍＺ」であり、ｙ方向のサイズが「ｓｙｓｔｅｍＹ」であり、ｘ方向のサイズが「ｓｙｓｔｅｍＸ」であるものとする。また、ｚ方向のジョブサイズが「ｊｏｂＺ」であり、ｙ方向のジョブサイズが「ｊｏｂＹ」であり、ｘ方向のジョブサイズが「ｊｏｂＸ」であるものとする。

この場合、図１６に示す処理によれば、計算ノード群３におけるｚ方向のループの回数は「ｓｙｓｔｅｍＺ−ｊｏｂＺ＋１」となり、ｙ方向のループの回数は「ｓｙｓｔｅｍＹ−ｊｏｂＹ＋１」となり、ｘ方向のループの回数は「ｓｙｓｔｅｍＸ−ｊｏｂＸ＋１」となる。また、ジョブサイズのｚ方向のループの回数は「ｊｏｂＺ」となり、ジョブサイズのｙ方向のループの回数は「ｊｏｂＹ」となり、ジョブサイズのｘ方向のループの回数は「ｊｏｂＸ」となる。

これに対して、図１０に示す処理によれば、計算ノード群３におけるｚ方向のループの回数は「ｓｙｓｔｅｍＺ−ｊｏｂＺ＋１」となり、ｙ方向のループの回数は「ｓｙｓｔｅｍＹ−ｊｏｂＹ＋１」となるが、ｘ方向のループの回数は「１」となる。また、ジョブサイズのｚ方向のループの回数は「ｊｏｂＺ」となり、ジョブサイズのｙ方向のループの回数は「ｊｏｂＹ」となるが、ジョブサイズのｘ方向のループの回数は「１」となる。

ここで、図２（Ａ）の３次元メッシュ結合が立方体であり、図６のジョブサイズも立方体であるとする。この場合、「ｓｙｓｔｅｍＺ＝ｓｙｓｔｅｍＹ＝ｓｙｓｔｅｍＸ」が成立するので、これらの値を「ｓｙｓｔｅｍ」と表すこととする。また、「ｊｏｂＺ＝ｊｏｂＹ＝ｊｏｂＸ」が成立するので、これらの値を「ｊｏｂ」と表すこととする。これにより、下記の式に示すように、ループ回数を削減することができる。

（第２の実施態様）
第１の実施態様においては、検索用マスクパターン１３４のシフト処理が１ビットずつ実行される。ここで、図８及び図９に着目すると、ジョブが要求している計算ノード３１の数に足りない計算ノード３１の数は、空きノード３１を検出するまでのシフトのビット数に一致する。換言すれば、演算結果が「０」のビットの数は、空きノード３１を検出するために必要な最小のシフト量に一致する。

そこで、この例では、空きノード検索部１４１は、ｘ軸について、ｘ軸検索用情報１３１’と検索用マスクパターン１３４とを用いた論理和演算に基づいて、演算結果が「０」のビットの数を算出する。演算結果が「０」のビットの数は、ジョブの割り当てが不可能であることを示すビットの数である。更に、空きノード検索部１４１は、検索用マスクパターン１３４における値「０」に設定された連続ビットを、ｂｉｔ０の方向に、演算結果が「０」のビットの数の分だけシフトする。

この結果、シフトされた検索用マスクパターン１３４が得られる。この後、空きノード検索部１４１は、ｘ軸検索用情報１３１’とシフトされた検索用マスクパターン１３４とを用いた論理和演算を実行することにより、再度、空きノード３１を検索する。これにより、演算結果が「０」のビットについてのシフト処理を１回で実行する、換言すれば、スキップして、更に、演算処理の回数を削減することができる。

図１２及び図１３は、ジョブの割り当てについての判定の他の一例を示す。

例えば、ｘ軸検索用情報１３１Ｄにおいて、図１２（Ａ）に示すように、ｂｉｔ７〜ｂｉｔ５が「０」であり、ｂｉｔ４〜ｂｉｔ２が「１」であり、ｂｉｔ１〜ｂｉｔ０が「０」であるとする。この状態は、ｂｉｔ７〜ｂｉｔ５に対応する計算ノード３１が使用中であり、ｂｉｔ４〜ｂｉｔ２に対応する計算ノード３１が空きであり、ｂｉｔ１〜ｂｉｔ０に対応する計算ノード３１が使用中である状態である。

また、例えば、検索用マスクパターン１３４Ｆにおいて、図１２（Ｂ）に示すように、ｂｉｔ７〜ｂｉｔ５が「０」であり、ｂｉｔ４〜ｂｉｔ０が「１」であるとする。この状態は、ｂｉｔ７〜ｂｉｔ５に対応する計算ノード３１が割り当て要求の対象であり、ｂｉｔ４〜ｂｉｔ０に対応する計算ノード３１が割り当てに無関係であり無視して良い状態である。

空きノード検索部１４１は、図１２（Ａ）のｘ軸検索用情報１３１Ｄと、図１２（Ｂ）の検索用マスクパターン１３４Ｆとの論理和を求める。この論理和の演算結果は、図１２（Ｃ）に示すように、ｂｉｔ７〜ｂｉｔ５が「０」となり、ｂｉｔ４〜ｂｉｔ０が「１」となる。従って、ｂｉｔ７〜ｂｉｔ５が割り当て不可能であり、ｂｉｔ４〜ｂｉｔ０が割り当て可能であることが求められる。

ここで、前述したように、ｂｉｔ７〜ｂｉｔ５に対応する計算ノード３１が割り当て要求の対象であり、ｂｉｔ４〜ｂｉｔ０に対応する計算ノード３１は割り当てに無関係である。従って、割り当て要求の対象であるｂｉｔ７〜ｂｉｔ５に対応する計算ノード３１について、ジョブを割り当てることができない。

そこで、空きノード検索部１４１は、図１２（Ａ）のｘ軸検索用情報１３１Ｄと、図１２（Ｂ）の検索用マスクパターン１３４Ｆとの論理和の演算結果における「０」のビットの数を算出する。演算結果が「０」のビットの数は、図１２（Ｃ）に示すように、「３」である。演算結果が「０」のビットの数は、「シフト総数」である。算出されたシフト総数は、図３（Ｄ）の検索情報１３３’におけるシフト総数に設定される。

シフト総数は、以下のようにして算出される。例えば、ｘ軸検索用情報１３１Ｄと検索用マスクパターン１３４Ｆとの論理和の演算結果において、最左端のｂｉｔ７の方向に向かって「０」が始めて出現する位置は、「ｂｉｔ５」である。換言すれば、「ｂｉｔ５」は「０」の出現位置の最右端である。この場合において、シフト総数は、「計算ノード群３のサイズ−「０」の出現位置の最右端」により求めることができる。従って、シフト総数は、８−５＝３により、「３」となる。

この算出の結果に基づいて、空きノード検索部１４１は、図１２（Ｂ）の検索用マスクパターン１３４Ｆにおける、ジョブが要求するサイズ「３」に対応する連続ビットｂｉｔ７〜ｂｉｔ５を、ｂｉｔ０の方向に、１ビットではなく、３ビットだけシフトする。これにより、図１２（Ｄ）の検索用マスクパターン１３４Ｇが得られる。

検索用マスクパターン１３４Ｆにおける３ビットのシフト処理の後、空きノード検索部１４１は、ｘ軸検索用情報１３１’とシフトされた検索用マスクパターン１３４Ｇとを用いて論理和を求めることにより、再度、空きノード３１を検索する。

図１２（Ａ）のｘ軸検索用情報１３１Ｄと、図１２（Ｄ）の検索用マスクパターン１３４Ｇとの論理和の演算結果は、図１２（Ｅ）に示すように、ｂｉｔ７〜ｂｉｔ０が「１」となる。従って、ｂｉｔ７〜ｂｉｔ０が割り当て可能であることが求められる。

ここで、前述したように、ｂｉｔ７〜ｂｉｔ５に対応する計算ノード３１が割り当て要求の対象であり、ｂｉｔ４〜ｂｉｔ０に対応する計算ノード３１は割り当てに無関係である。従って、割り当て要求の対象であるｂｉｔ７〜ｂｉｔ５に対応する計算ノード３１について、ジョブを割り当てることができる。

これにより、ジョブを連続した直方体形状に割り当てるための処理において、検索用マスクパターン１３４におけるシフト処理の回数及び論理和演算の回数をより少なくすることができる。従って、投入されたジョブの実行待ち時間を短縮することができ、また、計算ノード群３の稼動率を向上することができる。

なお、計算ノード群３が、図２（Ｂ）に示すトーラス結合されたコンピュータネットワークである場合がある。この場合において、図１３（Ａ）に示すように、検索用マスクパターン１３４Ｈにおいて、ｂｉｔ７〜ｂｉｔ３が「１」であり、ｂｉｔ２〜ｂｉｔ０が「０」であり、かつ、演算結果が「０」のビットの数が「３」である場合がある。換言すれば、シフト総数とジョブが要求するｘ軸方向のジョブサイズとの合計が、計算ノード３におけるｘ軸方向のサイズ以上になる場合がある。

この場合、ジョブが要求するサイズ「３」に対応する連続ビットｂｉｔ２〜ｂｉｔ０を、ｂｉｔ０の方向に、３ビットだけシフトする。この時、空きノード検索部１４１は、図１３（Ｂ）に示すように、ｂｉｔ０に隣接してｂｉｔ７が存在するので、ｂｉｔ０の「０」をｂｉｔ７に移動する。これにより、演算結果が「０」のビットをシフトさせることができる。

なお、他の実施態様においても、計算ノード群３が、図２（Ｂ）に示すトーラス結合されたコンピュータネットワークである場合には、図１３に示すようにして、演算結果が「０」のビットがシフトされる。

図１４は、他のジョブ管理処理フローである。

空きノード検索部１４１は、図１４に示すように、基本的には、図１０に示す処理と同様の処理を実行するが、図１０に示す処理に加えてステップＳ２８及びステップＳ２１９を実行する。

以下、図１４に示す処理における、図１０に示す処理との相違点について説明する。

空きノード検索部１４１は、図１０のステップＳ１０〜Ｓ１７と同様に、ステップＳ２０〜Ｓ２７を実行する。

この後、空きノード検索部１４１は、ステップＳ２７において、ジョブの割り当てが可能でない場合（ステップＳ２７ Ｎｏ）、ジョブの割り当てが不可能な位置に基づいてシフト数を算出する（ステップＳ２８）。具体的には、空きノード検索部１４１は、演算結果が「０」のビットの数を算出する。

この後、空きノード検索部１４１は、演算結果が「０」のビットの数と、ｘ軸検索用情報１３１’又は検索用マスクパターン１３４のビットの数とに基づいて、演算結果が「０」のビットの数の分のシフトが、右シフトの上限か否かを判断する（ステップＳ２９）。換言すれば、ジョブが要求するサイズ「３」に対応する連続ビットが、演算結果が「０」のビットの数だけシフトすることができるか否かが判断される。

演算結果が「０」のビットの数の分のシフトが右シフトの上限でない場合（ステップＳ２９ Ｎｏ）、空きノード検索部１４１は、ステップＳ２６を実行する。これにより、ジョブが要求するサイズ「３」に対応する連続ビットが、演算結果が「０」のビットの数だけシフトされる。

演算結果が「０」のビットの数の分のシフトが右シフトの上限である場合（ステップＳ２９ Ｙｅｓ）、空きノード検索部１４１は、ステップＳ２１６を実行する。

一方、ステップＳ２７において、ジョブの割り当てが可能である場合（ステップＳ２７ Ｙｅｓ）、空きノード検索部１４１は、ステップＳ２１０〜Ｓ２１２を実行する。

この後、空きノード検索部１４１は、ステップＳ２１２において、ジョブの割り当てが可能でない場合（ステップＳ２１２ Ｎｏ）、ジョブの割り当てが不可能な位置に基づいてシフト数を算出する（ステップＳ２１９）。具体的には、空きノード検索部１４１は、演算結果が「０」のビットの数を算出する。

この後、空きノード検索部１４１は、演算結果が「０」のビットの数と、ｘ軸検索用情報１３１’又は検索用マスクパターン１３４のビットの数とに基づいて、演算結果が「０」のビットの数の分のシフトが、右シフトの上限か否かを判断する（ステップＳ２２０）。換言すれば、ジョブが要求するサイズ「３」に対応する連続ビットが、演算結果が「０」のビットの数だけシフトすることができるか否かが判断される。

演算結果が「０」のビットの数の分のシフトが右シフトの上限でない場合（ステップＳ２２０ Ｎｏ）、空きノード検索部１４１は、ステップＳ２６を実行する。これにより、ジョブが要求するサイズ「３」に対応する連続ビットが、演算結果が「０」のビットの数だけシフトされる。

演算結果が「０」のビットの数の分のシフトが右シフトの上限である場合（ステップＳ２２０ Ｙｅｓ）、空きノード検索部１４１は、ステップＳ２１６を実行する。

（第３の実施態様）
第１〜第２の実施態様においては、ｘ軸検索用情報１３１’が生成され、ｘ軸に関する２重のループが削減される。これに対して、例えば、計算ノード群３のサイズが小さい場合には、検索用マスクパターン１３４のシフト処理回数が少なくなる。この場合には、ｘ軸検索用情報１３１’の生成処理、ｘ軸検索用情報１３１’と検索用マスクパターン１３４との論理和演算処理、検索用マスクパターン１３４のシフト処理のオーバーヘッドが大きくなる可能性がある。

そこで、この例では、空きノード検索部１４１は、計算ノード群３のｘ軸のサイズ、換言すれば、［ｓｙｓｔｅｍＸ］の最大値が予め定められた第１の値以上である場合には、前述したように、論理演算の結果に基づいて検索用マスクパターン１３４における連続ビットのシフト処理を行う。計算ノード群３のｘ軸のサイズは、［ｓｙｓｔｅｍＸ］の最大値である。第１の値は経験的に予め定められる。ｙ軸検索用情報又はｚ軸検索用情報が生成される場合には、ｙ軸のサイズ又はｚ軸のサイズが予め定められた値以上である場合には、論理演算の結果に基づいて検索用マスクパターン１３４における連続ビットのシフト処理を行う。

一方、空きノード検索部１４１は、計算ノード群３のｘ軸のサイズが予め定められた第１の値より小さい場合には、ｘ軸についても、空きノード３１か否かの判定処理を開始点から予め定められた順に繰り返すことにより、空きノード３１を検索する。換言すれば、空きノード検索部１４１は、計算ノード群３のｘ軸のサイズが予め定められた第１の値より小さい場合には、計算ノード群３におけるｘ方向のループを実行する。これにより、検索用マスクパターン１３４のシフト処理のオーバーヘッドが大きくなることを回避することができる。

なお、空きノード検索部１４１が、ジョブが要求するｘ軸方向のサイズが予め定められた第２の値以上である場合に、論理演算の結果に基づいて検索用マスクパターン１３４における連続ビットのシフトを行うようにしても良い。ジョブが要求するｘ軸方向のサイズは、［ｊｏｂＸ］の最大値である。第２の値は経験的に予め定められる。また、ｙ軸検索用情報又はｚ軸検索用情報が生成される場合には、ジョブが要求するｙ軸のサイズ又はジョブが要求するｚ軸のサイズが予め定められた値以上である場合には、論理演算の結果に基づいて検索用マスクパターン１３４における連続ビットのシフト処理を行うようにしても良い。

また、空きノード検索部１４１が、計算ノード群３のｘ軸のサイズとジョブが要求するサイズとの差分が予め定められた第３の値以上である場合に、論理演算の結果に基づいて検索用マスクパターン１３４における連続ビットのシフトを行うようにしても良い。第３の値は経験的に予め定められる。また、ｙ軸検索用情報又はｚ軸検索用情報が生成される場合には、ｙ軸方向における前記差分又はｚ軸方向における前記差分が予め定められた値以上である場合には、論理演算の結果に基づいて検索用マスクパターン１３４における連続ビットのシフト処理を行うようにしても良い。

（第４の実施態様）
第１〜第３の実施態様においては、３次元の中の１つの次元としてｘ軸が選択され、ｘ軸検索用情報１３１’が生成され、ｘ軸に関する２重のループが削減される。これに対して、計算ノード群３の形状が直方体である場合には、削減されるループをできるだけサイズの大きな軸方向に適用すると、ループの削減による処理時間の短縮の効果が大きい。また、ジョブの要求形状が直方体である場合にも、削減されるループをできるだけサイズの大きな軸方向に適用すると、ループの削減による処理時間の短縮の効果が大きい。

そこで、この例では、計算ノード管理部１４２が、図２（Ａ）の計算ノード群３における最も長辺である次元を、ｎ次元の中の１つの次元として選択し、当該選択された軸の検索用情報を生成する。ここで、最も長辺とは、［ｓｙｓｔｅｍＸ］の最大値、［ｓｙｓｔｅｍＹ］の最大値、及び、［ｓｙｓｔｅｍＺ］の最大値の中で、最も大きい値を持つ座標軸である。換言すれば、計算ノード管理部１４２は、図２（Ａ）において、座標軸はそのままにして、計算ノード群３における最も長辺である次元がｘ軸となるように、計算ノード群３を回転する。

この状態で、空きノード検索部１４２は、計算ノード群３にジョブを割り当てる。この後、計算ノード管理部１４２が、図２（Ａ）において、座標軸はそのままにして、計算ノード群３における最も長辺である次元がｘ軸から元の座標軸となるように、計算ノード群３を逆方向に回転する。この後、ジョブ実行制御部１２が、本来の座標軸に戻された計算ノード群３にジョブを割り当てて実行させる。これにより、ジョブの割り当て処理の時間を一層短縮することができる。

また、計算ノード管理部１４２が、図６のジョブの要求形状６における最も長辺である次元を、ｎ次元の中の１つの次元として選択し、当該選択された軸の検索用情報を生成するようにしても良い。ここで、最も長辺とは、［ｊｏｂＸ］の最大値、［ｊｏｂＹ］の最大値、及び、［ｊｏｂＺ］の最大値の中で、最も大きい値を持つ座標軸である。換言すれば、計算ノード管理部１４２は、図２（Ａ）において、座標軸はそのままにして、図６のジョブの要求形状６における最も長辺である次元がｘ軸となるように、計算ノード群３を回転する。

この状態で、空きノード検索部１４２は、計算ノード群３にジョブを割り当てる。この後、計算ノード管理部１４２が、図２（Ａ）において、座標軸はそのままにして、図６のジョブの要求形状６における最も長辺である次元がｘ軸からもとの座標軸となるように、計算ノード群３を逆方向に回転する。この後、ジョブ実行制御部１２が、本来の座標軸に戻された計算ノード群３にジョブを割り当てて実行させる。これにより、ジョブの割り当て処理の時間を一層短縮することができる。

１ ジョブ管理装置
２ 利用者端末
３ 計算ノード群
３１ 計算ノード
１１ ジョブ受付処理部
１２ ジョブ実行制御部
１３ 記憶部
１４ ジョブ割り当て処理部
１５ 計算ノード情報記憶部
１１１ 割り当て情報生成部
１３１ Ｘ軸検索用情報記憶部
１３２ ジョブ割り当て情報記憶部
１３３ 検索情報記憶部
１４１ 空きノード検索部
１４２ 計算ノード管理部
１５１ ３次元システム情報記憶部

Claims (8)

1. ｎ（ｎは２以上の整数）次元メッシュ結合又はｎ次元トーラス結合されたコンピュータネットワークにおける計算ノードであって、ジョブの割り当てが可能な空きノードを検索するジョブ管理装置であって、
   前記ｎ次元の中の１つの次元についての検索用情報であって、複数のビットを含み、前記ｎ次元の中の１つの次元に属する複数の計算ノードの各々について、前記ジョブの割り当てが可能か否かを１ビットの情報で示す１次元検索用情報を生成する１次元検索用情報生成部と、
   前記複数のビットに対応するビット数の検索用マスクパターンであって、前記ｎ次元の中の１つの次元について前記ジョブが要求するサイズに対応する連続ビットを予め定められた値に設定された検索用マスクパターンを生成する検索情報生成部と、
   前記ｎ次元の中の１つの次元について、前記１次元検索用情報と前記検索用マスクパターンとを用いて予め定められた論理演算を実行することにより、前記空きノードを検索する空きノード検索部とを含む
   ことを特徴とするジョブ管理装置。
2. 前記空きノード検索部が、前記ｎ次元の中の前記１つの次元以外の残りの（ｎ−１）次元について、前記空きノードか否かの判定処理を開始点から予め定められた順に繰り返すことにより、前記空きノードを検索する
   ことを特徴とする請求項１に記載のジョブ管理装置。
3. 前記空きノード検索部が、前記ｎ次元の中の１つの次元についての前記論理演算の結果が前記ｎ次元の中の１つの次元について前記ジョブの割り当てが不可能であることを示す場合、前記検索用マスクパターンにおける前記予め定められた値に設定された前記連続ビットを、予め定められた方向に１ビットだけシフトし、前記１次元検索用情報とシフトされた前記検索用マスクパターンとを用いて前記予め定められた論理演算を実行することにより、前記空きノードを検索する
   ことを特徴とする請求項１に記載のジョブ管理装置。
4. 前記空きノード検索部が、前記ｎ次元の中の１つの次元についての前記論理演算に基づいて、前記ジョブの割り当てが不可能であることを示すビットの数を算出し、前記検索用マスクパターンにおける前記予め定められた値に設定された前記連続ビットを、前記予め定められた方向に前記ジョブの割り当てが不可能であることを示すビットの数の分だけシフトし、前記１次元検索用情報とシフトされた前記検索用マスクパターンとを用いて前記予め定められた論理演算を実行することにより、前記空きノードを検索する
   ことを特徴とする請求項３に記載のジョブ管理装置。
5. 前記空きノード検索部が、前記ｎ次元メッシュ結合又はｎ次元トーラス結合されたコンピュータネットワークのサイズが予め定められた第１の値以上である場合、前記ジョブが要求するサイズが予め定められた第２の値以上である場合、又は、前記コンピュータネットワークのサイズと前記ジョブが要求するサイズとの差分が予め定められた第３の値以上である場合に、前記論理演算の結果に基づいて、前記検索用マスクパターンにおける前記連続ビットのシフトを行う
   ことを特徴とする請求項３に記載のジョブ管理装置。
6. 前記ジョブ管理装置が、更に、
   前記ｎ次元メッシュ結合又はｎ次元トーラス結合されたコンピュータネットワークにおける計算ノードの各々について、前記空きノードか否かを示すｎ次元システム情報を生成する計算ノード管理部を含み、
   前記空きノード検索部が、前記ｎ次元システム情報に基づいて、前記１次元検索用情報を生成する
   ことを特徴とする請求項１に記載のジョブ管理装置。
7. 前記ジョブ管理装置が、更に、
   前記ｎ次元メッシュ結合又はｎ次元トーラス結合されたコンピュータネットワークにおける最も長辺である次元を、前記ｎ次元の中の１つの次元として選択する計算ノード管理部を含む
   ことを特徴とする請求項１に記載のジョブ管理装置。
8. ｎ（ｎは２以上の整数）次元メッシュ結合又はｎ次元トーラス結合されたコンピュータネットワークにおける計算ノードであって、ジョブの割り当てが可能な空きノードを検索するジョブ管理方法であって、
   １次元検索用情報生成部が、前記ｎ次元の中の１つの次元についての検索用情報であって、複数のビットを含み、前記１つの次元に属する複数の計算ノードの各々について、前記ジョブの割り当てが可能か否かを１ビットの情報で示す１次元検索用情報を生成するステップと、
   検索情報生成部が、前記複数のビットに対応するビット数の検索用マスクパターンであって、前記ｎ次元の中の１つの次元について前記ジョブが要求するサイズに対応する連続ビットを予め定められた値に設定された検索用マスクパターンを生成するステップと、
   空きノード検索部が、前記ｎ次元の中の１つの次元について、前記１次元検索用情報と前記検索用マスクパターンとを用いて予め定められた論理演算を実行することにより、前記空きノードを検索するステップとを含む
   ことを特徴とするジョブ管理方法。

Images