(57)【特許請求の範囲】
【請求項１】
計算機システムを管理するジョブ管理装置に、
前記計算機システムにおける計算資源を表す複数の頂点及び前記計算資源間のリンクを表す複数の辺を含むグラフにおいて、あるジョブが割り当てられた計算資源についての部分グラフに属する頂点の数に対する前記部分グラフに隣接するがジョブの割り当てがない計算資源についての頂点の数の割合と、前記部分グラフに属する頂点の数に対する前記部分グラフに属する複数の頂点に隣接するがジョブの割り当てがない計算資源についての頂点の数の割合と、前記部分グラフに属する頂点の数に対する前記部分グラフに隣接するがジョブの割り当てがない計算資源についての頂点と隣接し且つ前記部分グラフに属する頂点の数の割合と、前記部分グラフに属する頂点に対する、一方の頂点が前記部分グラフに属するが他方の頂点が前記部分グラフに隣接してさらにジョブの割り当てがない計算資源についての頂点である辺の数の割合と、前記部分グラフに属する頂点間の辺の数に対する一方の頂点が前記部分グラフに属するが他方の頂点が部分グラフに隣接してさらにジョブの割り当てがない計算資源についての頂点である辺の数の割合とのうち少なくともいずれかを取得させ、
取得された前記割合に基づき、前記部分グラフを基準に他のジョブを割り当てるべき計算資源を探索するのに要する負荷に関する指標値を算出させる
ジョブ管理プログラム。
【請求項２】
前記ジョブ管理プログラムはさらに、
前記ジョブ管理装置に、
前記指標値に基づき、前記部分グラフを基準に他のジョブを割り当てるべき計算資源を探索するための処理要素数を決定させる
請求項１記載のジョブ管理プログラム。
【請求項３】
前記ジョブ管理プログラムにおいて、
前記算出させる処理が、
取得された前記割合から前記部分グラフを基準に他のジョブを割り当てるべき計算資源の探索が成功する確率を、予め設定された第１のデータに基づき算出させ、
取得された前記割合と算出された前記確率とに基づき、予め設定された第２のデータに基づき前記指標値を算出させる
処理を含む請求項１又は２記載のジョブ管理プログラム。
【請求項４】
前記ジョブ管理プログラムはさらに、
前記ジョブ管理装置に、
前記取得させる処理と前記算出させる処理とを、複数の前記部分グラフについて実施させ、
前記決定させる処理は、
複数の前記部分グラフについて算出された複数の指標値に応じて、前記処理要素数を複数の前記部分グラフの各々について決定させる
処理を含む請求項２記載のジョブ管理プログラム。
【請求項５】
計算機システムを管理するジョブ管理装置が、
前記計算機システムにおける計算資源を表す複数の頂点及び前記計算資源間のリンクを表す複数の辺を含むグラフにおいて、あるジョブが割り当てられた計算資源についての部分グラフに属する頂点の数に対する前記部分グラフに隣接するがジョブの割り当てがない計算資源についての頂点の数の割合と、前記部分グラフに属する頂点の数に対する前記部分グラフに属する複数の頂点に隣接するがジョブの割り当てがない計算資源についての頂点の数の割合と、前記部分グラフに属する頂点の数に対する前記部分グラフに隣接するがジョブの割り当てがない計算資源についての頂点と隣接し且つ前記部分グラフに属する頂点の数の割合と、前記部分グラフに属する頂点に対する、一方の頂点が前記部分グラフに属するが他方の頂点が前記部分グラフに隣接してさらにジョブの割り当てがない計算資源についての頂点である辺の数の割合と、前記部分グラフに属する頂点間の辺の数に対する一方の頂点が前記部分グラフに属するが他方の頂点が部分グラフに隣接してさらにジョブの割り当てがない計算資源についての頂点である辺の数の割合とのうち少なくともいずれかを取得し、
取得された前記割合に基づき、前記部分グラフを基準に他のジョブを割り当てるべき計算資源を探索するのに要する負荷に関する指標値を算出する
ジョブ管理方法。
【請求項６】
計算機システムを管理するジョブ管理装置において、
前記計算機システムにおける計算資源を表す複数の頂点及び前記計算資源間のリンクを表す複数の辺を含むグラフにおいて、あるジョブが割り当てられた計算資源についての部分グラフに属する頂点の数に対する前記部分グラフに隣接するがジョブの割り当てがない計算資源についての頂点の数の割合と、前記部分グラフに属する頂点の数に対する前記部分グラフに属する複数の頂点に隣接するがジョブの割り当てがない計算資源についての頂点の数の割合と、前記部分グラフに属する頂点の数に対する前記部分グラフに隣接するがジョブの割り当てがない計算資源についての頂点と隣接し且つ前記部分グラフに属する頂点の数の割合と、前記部分グラフに属する頂点に対する、一方の頂点が前記部分グラフに属するが他方の頂点が前記部分グラフに隣接してさらにジョブの割り当てがない計算資源についての頂点である辺の数の割合と、前記部分グラフに属する頂点間の辺の数に対する一方の頂点が前記部分グラフに属するが他方の頂点が部分グラフに隣接してさらにジョブの割り当てがない計算資源についての頂点である辺の数の割合とのうち少なくともいずれかを取得する取得部と、
取得された前記割合に基づき、前記部分グラフを基準に他のジョブを割り当てるべき計算資源を探索するのに要する負荷に関する指標値を算出する算出部と、
を有するジョブ管理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ジョブ管理プログラム、ジョブ管理方法及びジョブ管理装置に関する。
【背景技術】
【０００２】
大規模な並列計算機システムでは、クロスバ結合のような「複数のプロセッサ間の通信性能がネットワーク上のプロセッサの配置にほとんど影響されない」形態のネットワークを採用することは、配線や中継装置の物量増加に伴うコストの問題により困難である。これは、そのような形態のネットワークでは、配線や中継装置の数がプロセッサ数の２乗に比例するためである。そこで、メッシュやトーラスなど、配線や中継装置の物量が演算処理装置としてのプロセッサの数に比例する程度に抑えられる接続形態（すなわちネットワークトポロジ）のネットワークが用いられることが多い。
【０００３】
なお、大規模なシステムのネットワークトポロジに関する技術は現在も進展中であり、メッシュやトーラスに限られてはいないが、基本的な特性について、物量がプロセッサ数に比例する程度に抑えられることが求められる点は同様である。
【０００４】
このような大規模なシステムでは、複数（最大ジョブ数は、システムの規模にも拠るが、数千単位乃至数万単位のオーダーであり、しばしば極めて多数）のジョブの各々に対し、プロセッサの集合、又はプロセッサの集合と使用可能時間帯との対を割り当てて、同時に実行するという運用形態が一般的である。その際、各ジョブに割り当てるプロセッサの集合を、他のジョブに割り当てられたプロセッサの他の集合との間で、通信トラフィックが全く又はほとんど干渉しないように、ネットワーク上に配置することが望ましい。例えば、ネットワークがメッシュやトーラスの場合、各ジョブに割り当てるプロセッサの集合を「ネットワーク全体よりは小さいメッシュ又はトーラス」（＝サブメッシュ又はサブトーラス）に割り当てる方法が、しばしば採用される。
【０００５】
各ジョブに割り当てるべきプロセッサの集合は、要素数やプロセッサ相互のネットワーク上での位置関係などの点において多様であり、ジョブの実行に要する時間も様々である。そのため、各ジョブに対する資源管理の処理は、空き資源と割り当て済み資源の位置関係や前後関係が複雑になりがちな大規模なシステムにおいて、スケジューリング処理のボトルネックになりやすい。その結果、ジョブスケジューラの性能低下によるシステムの利用率の低下、すなわちシステムとしてのスループット低下の原因にもなり得る。
【０００６】
スケジューリングの処理時間を短縮するため、ジョブを割り当て可能な資源の探索処理を並列化すること、例えば、割り当て可能なプロセッサの集合の探索範囲を複数のスレッドに分割することが考えられる。しかし、このような探索処理を並列化する際には、以下で述べるような問題が存在している。
【０００７】
すなわち、探索範囲の分担方法や探索の処理手順によっては、実際には割り当て可能な空き資源が検出されない恐れがある。例えば、メッシュやトーラスにおいて、空き資源と割り当て済み資源とをビットマップによって管理するタイプの従来技術では、探索すべき空き資源の形状パラメタ（すなわち各次元での大きさ）の間隔で探索位置をずらす方法と、常に各次元で１マス毎に探索位置をずらす方法が知られている。
【０００８】
このような２つの方法のうち前者の方法では、空き資源を見落とす可能性がある。一方、後者の方法では、探索時間が長くなるという問題がある。
【０００９】
また、並列処理の場合、並列処理を行うための処理要素（プロセッサ、プロセッサの集合、プロセッサのコア、プロセッサのコアの集合など）の間の分担範囲が不適切なことにより、割り当て可能な空き資源の探索に失敗する可能性も生ずる。
【００１０】
さらに、並列処理の場合、並列化できない処理の時間の割合が大きいと、並列化による処理時間の短縮効果が小さくなる（アムダールの法則）ため、並列化可能な処理が探索処理全体の時間に対して占める割合を高めることが好ましい。しかしながら、従来技術ではこのような工夫はなされていない。
【００１１】
さらに、並列処理の場合、個々の探索範囲によって探索処理の所要時間が大きく異なる場合があり得るため、最も長い処理時間によりスケジューリング性能が制約される恐れがある。
【００１２】
割り当て可能か不可能かの判定をも含む探索処理の時間は、「割り当て状況の複雑さ」、言い換えれば「資源領域のフラグメンテーション進行度」に依存すると考えられる。しかし、ジョブスケジューラが管理する資源についての「割り当て状況の複雑さ」又は「フラグメンテーション進行度」は、定量化の方法が確立されておらず、従来技術では解決できない。
【００１３】
例えば従来技術として知られている、メモリ領域やディスク領域でのフラグメンテーションの定量化では、「個々の割り当て済み領域（メモリセグメント又はファイル）又は空き領域のページ番号又はブロック番号が連続しているか否か」という単一のパラメタに着目している。そのため、フラグメンテーションの有無の判定は比較的単純であるが、ジョブスケジューラの管理対象資源は、「プロセッサのネットワーク内での接続関係」に関連する複数のパラメタが「フラグメンテーション進行度」に影響すると考えられる。従って、メモリやディスクと同じような方法を採用することはできない。
【先行技術文献】
【特許文献】
【００１４】
【特許文献１】特開２０１０−２０４８８０号公報
【特許文献２】特開２００９−７０２６４号公報
【特許文献３】国際公開第２００５／１１６８３２号パンフレット
【特許文献４】特開２００８−７１２９４号公報
【発明の概要】
【発明が解決しようとする課題】
【００１５】
従って、本発明の目的は、一側面として、複数の計算機を含む計算機システムを管理するジョブ管理装置が実行するジョブスケジューラにおける探索処理の並列化を効率化するための技術を提供することである。
【課題を解決するための手段】
【００１６】
本発明の第１の態様に係るジョブ管理装置によるジョブ管理方法は、（Ａ）計算機システムにおける計算資源を表す複数の頂点及び計算資源間のリンクを表す複数の辺を含むグラフにおける、１又は複数の第１のジョブが割り当てられた第１の計算資源についての第１の部分グラフ又は上記１又は複数の第１のジョブに対して、上記グラフにおいてジョブが割り当てられていない計算資源についての頂点を介して第１の部分グラフに接続され且つ第２のジョブが割り当てられた第２の計算資源についての第２の部分グラフ又は第２のジョブについてのデータを管理し、（Ｂ）上記データを用いて、第３のジョブを割り当てるべき第３の計算資源の有無を、第１の部分グラフから判断する処理を含む。
【００１７】
本発明の第２の態様に係るジョブ管理装置によるジョブ管理方法は、（Ａ）計算機システムにおける計算資源を表す複数の頂点及び計算資源間のリンクを表す複数の辺を含むグラフにおいて、（ａ１）あるジョブが割り当てられた計算資源についての部分グラフに属する頂点の数に対する部分グラフに隣接するがジョブの割り当てがない計算資源についての頂点の数の割合と、（ａ２）部分グラフに属する頂点の数に対する部分グラフに属する複数の頂点に隣接するがジョブの割り当てがない計算資源についての頂点の数の割合と、（ａ３）部分グラフに属する頂点の数に対する部分グラフに隣接するがジョブの割り当てがない計算資源についての頂点と隣接し且つ部分グラフに属する頂点の数の割合と、（ａ４）部分グラフに属する頂点に対する、一方の頂点が部分グラフに属するが他方の頂点が部分グラフに隣接してさらにジョブの割り当てがない計算資源についての頂点である辺の数の割合と、（ａ５）部分グラフに属する頂点間の辺の数に対する一方の頂点が部分グラフに属するが他方の頂点が部分グラフに隣接してさらにジョブの割り当てがない計算資源についての頂点である辺の数の割合とのうち少なくともいずれかを取得し、（Ｂ）取得された割合に基づき、部分グラフを基準に他のジョブを割り当てるべき計算資源を探索するのに要する負荷に関する指標値を算出する処理を含む。
【発明の効果】
【００１８】
一側面として、複数の計算機を含む計算機システムを管理するジョブ管理装置が実行するジョブスケジューラにおける探索処理の並列化を効率化できる。
【図面の簡単な説明】
【００１９】
【図１】図１は、グラフ表現された計算機システムの一例を示す図である。
【図２】図２は、時間帯を含む資源を表すグラフの一例を示す図である。
【図３】図３は、対岸を説明するための図である。
【図４】図４は、本実施の形態に係る計算機システムの一例を示す図である。
【図５】図５は、マスタスケジューラノードの機能構成例を示す図である。
【図６】図６は、スレーブスケジューラノードの機能構成例を示す図である。
【図７】図７は、ジョブを管理するためのデータの一例を示す図である。
【図８】図８は、連結成分を管理するためのデータの一例を示す図である。
【図９】図９は、スレーブスケジューラノードにおけるメインの処理フローを示す図である。
【図１０】図１０は、第１追加処理の処理フローを示す図である。
【図１１】図１１は、第２追加処理の処理フローを示す図である。
【図１２】図１２は、第３追加処理の処理フローを示す図である。
【図１３Ａ】図１３Ａは、削除処理の処理フローを示す図である。
【図１３Ｂ】図１３Ｂは、分解判定処理の処理フローを示す図である。
【図１４】図１４は、対岸リスト更新処理の処理フローを示す図である。
【図１５】図１５は、対岸リスト更新処理の処理フローを示す図である。
【図１６】図１６は、複雑度の定義を説明するための図である。
【図１７】図１７は、複雑度の定義を説明するための図である。
【図１８】図１８は、定義１の複雑度を算出するための処理の処理フローを示す図である。
【図１９】図１９は、定義２の複雑度を算出するための処理の処理フローを示す図である。
【図２０】図２０は、定義３の複雑度を算出するための処理の処理フローを示す図である。
【図２１】図２１は、定義４の複雑度を算出するための処理の処理フローを示す図である。
【図２２】図２２は、定義５の複雑度を算出するための処理の処理フローを示す図である。
【図２３】図２３は、マスタスケジューラノードにおけるメインの処理フローを示す図である。
【図２４】図２４は、処理時間の見積もり処理の処理フローの一例を示す図である。
【図２５】図２５は、探索処理の処理フローを示す図である。
【図２６】図２６は、探索処理の処理フローを示す図である。
【図２７】図２７は、探索処理の評価処理の処理フローを示す図である。
【図２８】図２８は、探索処理の評価処理の処理フローを示す図である。
【図２９】図２９は、処理時間の見積もり処理の処理フローの他の例を示す図である。
【図３０】図３０は、探索処理の評価処理の処理フローを示す図である。
【図３１】図３１は、実行待ちのジョブに関するデータの例を示す図である。
【図３２】図３２は、ジョブ制御表の一例を示す図である。
【図３３】図３３は、連結成分についての制御表の位置例を示す図である。
【図３４】図３４は、ジョブに対する対岸リストの１ブロックの例を示す図である。
【図３５】図３５は、連結成分に対する対岸リストの１ブロックの例を示す図である。
【図３６】図３６（ａ）乃至（ｃ）は、ハッシュテーブルを説明するための図である。
【発明を実施するための形態】
【００２０】
メッシュやトーラスといったネットワークトポロジだけではなく一般のネットワークトポロジのシステムを扱う場合、「ジョブに対する資源割り当て単位」である計算ノードに対応する「頂点」と、「ジョブに対する資源割り当て単位間のネットワークリンク」に対応する「辺」とを設定することで、システムをグラフ理論の意味での「グラフ」で表すことができる。
【００２１】
例えば、図１に示すように、計算機システムは、計算ノード（すなわち、資源）に対応する丸と、計算ノード間を繋ぐネットワークリンクとで表される。なお、図１においては、黒丸は、ジョブに対して割り当て済み資源に対応する頂点を表しており、白丸は、空き資源に対応する頂点を表している。また、実線の辺は、割り当て済み資源間を繋ぐネットワークリンクに対応する。点線の辺は、割り当て済み資源と空き資源との間を繋ぐネットワークリンクに対応し、且つ割り当て済み資源と空き資源との境界に対応するネットワークリンクに対応する。
【００２２】
本実施の形態でも、グラフを表現するために一般的に用いられる隣接行列と、接続行列とを用いる。隣接行列は、グラフの点集合が｛１，２，．．．，ｎ｝であるとき、ｉｊ成分が点ｉとｊを結ぶ辺数を表すｎ×ｎ行列である。同様に、接続行列は、辺に｛１，２，．．．，ｍ｝とラベル付けされているときに、そのｉｊ成分が１であるのは点ｉが辺ｊに接続されている場合であり、且つ接続していないときは０であるようなｎ×ｍ行列である。
【００２３】
本実施の形態で想定するような大規模なシステムにおけるネットワークトポロジに対するコスト的な制約により、大規模なシステムを表す「グラフ」の「隣接行列」と「接続行列」は、いずれも「疎行列（大半の成分が０の行列）」になる。
【００２４】
また、大規模なシステムにおけるジョブスケジューリングでは、単にプロセッサの集合をジョブに割り当てるだけでなく、そのプロセッサ集合の使用時間帯をも決めた上で割り当てる場合もある。そこで、以下ではジョブスケジューラがジョブに割り当てる「資源」とは、明示的に区別しない限り、「プロセッサの集合」と「プロセッサの集合と使用時間帯との対」とのどちらでもあり得るものとする。
【００２５】
「プロセッサの集合と使用時間帯との対」という意味での「資源」を扱う場合、使用時間帯を所定の単位時間により整数の時刻座標で表し、座標毎にシステムに対応するグラフのコピーを対応させる。
【００２６】
そして、ジョブに対する割り当て単位に対応する頂点が、直前及び直後の時刻において計算機システムの計算ノードに対応する頂点が結ばれているグラフを「資源」に対応させることとする。
【００２７】
以下、グラフに関する用語は、特に断らない限り「グラフ理論」における標準的な意味で使用する。
【００２８】
例えば、図２に示すように、使用可能時間帯１において１列に並ぶように接続された５つの頂点で表されるグラフは、使用可能時間帯２乃至４の各々についてコピーされ、各頂点について４つの使用可能時間帯を繋ぐ３つの辺（矢印）でも繋がれている。白丸と黒丸、実線と点線については、図１で説明したものと同様である。
【００２９】
例えば図１及び図２において黒丸と実線とで特定される資源群を、本実施の形態では、割り当て済み資源に対応する部分グラフである「割り当て済みグラフ」と呼ぶことにする。
【００３０】
本実施の形態では、割り当て済みグラフの連結部分集合に対して次のように定義する「近傍」及び「対岸」という概念を導入し、探索処理に先立ってこれらに関係するデータを用意することで、探索処理を高速化させる。但し、「近傍」はグラフ理論の一般的な用語というわけではない。
【００３１】
グラフΓ（Ｖ，Ｅ）における連結部分グラフＣ１、Ｃ２がＣ１∩Ｃ２＝φを満たすとき、Ｃ１とＣ２が「接する」とは、Ｃ１とＣ２が同じ連結成分に含まれることをいう。
【００３２】
以下ではグラフΓ（Ｖ，Ｅ）の頂点の集合Ｖが共通の頂点がない２つの部分集合に分かれているとする。
（Ｖ＝Ｘ∪Ｙ）∧（Ｘ∩Ｙ＝φ）
言い換えれば、ＸとＹは全体集合Ｖにおいて互いに他の補集合とする。
【００３３】
この前提の下で、辺の集合Ｅを、どの２つも共通部分が空集合になるような以下の３つの部分集合に分ける。
Ｅ１＝｛ｅ∈Ｅ｜両端の頂点ともにＸに属する｝
Ｅ２＝｛ｅ∈Ｅ｜両端の頂点ともにＹに属する｝
Ｅ３＝｛ｅ∈Ｅ｜両端の頂点のうち、一方がＸに属し、他方がＹに属する｝
【００３４】
すなわち、集合の記号と論理記号で書けば、以下のようになる。
Ｅ＝（Ｅ１∪Ｅ２∪Ｅ３）∧（Ｅ１∩Ｅ２＝φ）∧（Ｅ２∩Ｅ３＝φ）∧（Ｅ３∩Ｅ１＝φ）
【００３５】
これ以降では、表現を簡潔にするため、部分グラフΓ（Ｘ，Ｅ１）とＸを同一視してＸと表し、部分グラフΓ（Ｙ，Ｅ２）とＹも同一視してＹと表すものとする。
【００３６】
以下、ＳＰ（ｖ１，ｖ２）という記号で、２つの頂点ｖ１と頂点ｖ２の最短経路（すなわち、含まれる辺の数が最小の経路）の集合を表す。
ＳＰ（ｖ１，ｖ２）＝｛ｖ１とｖ２の最短経路｝
【００３７】
Ｘにおいて共通の頂点がない２つの連結部分グラフＣ１及びＣ２（すなわちＣ１⊂Ｘ，Ｃ２⊂Ｘ，Ｃ１∩Ｃ２＝φ）に対し、Ｃ１とＣ２が互いに他の「対岸である」ことを、次の条件で定義する。ここで、Ｘを陸地、Ｙを水域に見立てて「対岸」という用語を導入している。但し、ＸとＹは定義上は対称なので、Ｙの連結部分グラフについても、同様な定義は可能である。なお、∃は、直後に置かれる変数記号に対して「次の条件を満たすものが存在する」という意味を表す論理記号である。同様に∀は直後に置かれる変数記号に対し、「その全てが次の条件を満たす」という意味を表す論理記号である。以下では、表現を簡潔にするため、これらの論理記号を用いて、「対岸」の条件を表す。
∃ｖ１∈Ｃ１  ∃ｖ２∈Ｃ２  ∃ｐ∈ＳＰ（ｖ１，ｖ２）  ｐのｖ１及びｖ２以外の頂点が全てＹ（すなわちＸの補集合）に含まれる
【００３８】
一方、ｖ１及びｖ２が対岸でない場合は、「辺の数が最小のどのような経路」も、途中でＸの部分集合（すなわち陸地）を通過する。
【００３９】
Ｃ１とＣ２の間の「辺の数が最小の経路」は、一般のグラフでは「単一始点最小経路問題」の解であり、ダイクストラ法やベルマン−フォード法など、グラフ理論の既知のアルゴリズムで計算される。また、「全点対最小経路問題」の解を、Ｃ１及びＣ２の点を始点及び終点となる場合の一部とみなせば、Ｃ１とＣ２の間の「辺の数が最小の経路」は、ワーシャル−フロイド法など、グラフ理論の既知のアルゴリズムで計算される。
【００４０】
なお、メッシュやトーラスに対応するグラフに対しては、それらに対する比較的洗練された、グラフ理論のアルゴリズムを使うまでもなく他のシンプルな手法で求めることができ、探索処理の際に計算幾何における「最近傍領域探索」用のデータ構造（例えばＲ木、区間木など）を利用することもできる。
【００４１】
次に、正の整数ｎに対し、共にＸの部分グラフであり且つ共通部分がない２つの連結部分グラフＣ１及びＣ２が「互いに他方のｎ次近傍」であることを、次のように再帰的に定める。
（１）Ｃ１とＣ２が「対岸である」なら、Ｃ１とＣ２は互いに他の１次近傍である。
（２）Ｃ１とＣ２とのいずれの対岸でもない、Ｘ内の部分集合Ｃ３⊂Ｘであって、Ｃ１とＣ３がｎ1次近傍、Ｃ３とＣ２がｎ2次近傍として、ｎ1＋ｎ2の最小値がｎであるとき、Ｃ１とＣ２はｎ次近傍である。
【００４２】
すなわち、Ｃ１とＣ２がｎ次近傍であれば、Ｘにおいてｎ個の連結部分グラフの列Ｄ（１），Ｄ（２），．．．，Ｄ（ｎ）があって、Ｄ（１）＝Ｃ１，Ｄ（ｎ）＝Ｃ２，全てのｉ＝１，．．．，ｎに対して  Ｄ（ｉ）とＤ（ｉ＋１）が対岸である。
【００４３】
なお、本実施の形態では、連結部分グラフのこのような列に対し、「Ｃ１から見てＤ（ｉ）はＤ（ｉ＋１）の手前にある」又は「Ｃ１から見て、Ｄ（ｉ＋１）はＤ（ｉ）の向こう側にある」という表現を使う場合もあるものとする。同様に「Ｃ２から見て、Ｄ（ｉ＋１）はＤ（ｉ）の手前にある」又は「Ｄ（ｉ）はＤ（ｉ＋１）の向こう側にある」と表現する場合があるものとする。
【００４４】
さらに、本実施の形態では、連結集合Ｃを「Ｃ自体の０次近傍」と呼ぶ場合もあるものとする。
【００４５】
なお、異なる２つの連結成分の共通部分はない（＝空集合である）ことから、「対岸である」関係や「ｎ次近傍」は、連結成分に対しては、自然に定義される。
【００４６】
また、各ジョブに対して、「どの２つのジョブに割り当てる資源に対応する部分グラフも連結」且つ「異なるジョブに対応する資源は共通部分を持たない部分グラフに対応する」ように割り当てる場合、ジョブの間に「対岸である」関係と「ｎ次近傍」を定義することもできる。
【００４７】
さらに、メッシュやトーラスについては、連結部分グラフ間の経路を各次元の座標軸に平行な経路に制限することで「少なくとも１つの座標軸について対岸である」という用語も用いる場合があるものとする。「少なくとも１つの座標軸について対岸である」ならば「対岸である」が、逆は必ずしも成立しない。
【００４８】
すなわち、メッシュ又はトーラスの２つの連結部分グラフＣ１及びＣ２において全ての最短経路が「斜め」になる（∀ ｖ１∈Ｃ１  ∀ ｖ２∈Ｃ２  ｖ１とｖ２の座標は全ての座標軸の成分が異なる）場合、どの座標軸を選んでも「１つの座標軸について対岸である」とは言えない。
【００４９】
上で述べた定義の一部を、図３に示したメッシュの場合を用いて説明する。図３において、頂点は計算ノード（すなわち、資源）に対応し、頂点間の辺はネットワークリンクに対応する。図３において、斜線で囲まれた領域１０１乃至１１４は、それぞれ１つのジョブに割り当てられた頂点の集合を表している。領域１０１と領域１０２とは接しており、領域１０１と領域１０２との間における辺の領域１２１にジョブは割り当てられないので、領域１０１及び１０２と領域１２１とで、割り当て済みグラフ内における連結成分となる。同様に、領域１０４と領域１０３とは接しており、領域１０３と領域１０４との間における辺の領域１２２にジョブは割り当てられないので、領域１０３及び１０４と領域１２２とで、割り当て済みグラフ内における連結成分となる。
【００５０】
さらに、領域１１３と領域１１４とは接しており、領域１１３と領域１１４との間における辺の領域１２８にジョブは割り当てられないので、領域１１３及び１１４と領域１２８とで、割り当て済みグラフ内における連結成分となる。
【００５１】
さらに、領域１０６は、領域１０５と領域１０７とに接しており、領域１０６と領域１０５との間における辺の領域１２３にジョブは割り当てられず、且つ領域１０６領域１０７との間における辺の領域１２４にジョブは割り当てられないので、領域１０５乃至１０７と領域１２３及び１２４とで、割り当て済みグラフ内における連結成分となる。
【００５２】
さらに、領域１１２は、領域１０９と領域１０８とに接しており、さらに領域１１１にも接している。また、領域１１１は、領域１１０に接している。領域１１２と領域１０９及び１０８との間、並びに領域１０９と領域１０８との間における辺の領域１２５にはジョブは割り当てられておらず、また領域１１２と領域１１１との間における辺の領域１２６にはジョブは割り当てられない。さらに、領域１１１と領域１１０との間における辺の領域１２７にはジョブは割り当てられない。よって、領域１０８乃至１１２と領域１２５乃至１２７とで、割り当て済みグラフ内における連結成分となる。
【００５３】
図３において、割り当て済みグラフ内における連結成分間の「対岸である」関係は、両方向点線矢印１３１乃至１３８で表される。具体的には、領域１０１及び１０２と領域１２１とを含む連結成分の対岸は、領域１０３及び１０４と領域１２２とを含む連結成分と、領域１０８乃至１１２と領域１２５乃至１２７とを含む連結成分と、領域１１３及び１１４と領域１２８とを含む連結成分である。
【００５４】
領域１０３及び１０４と領域１２２とを含む連結成分の対岸は、領域１０１及び１０２と領域１２１とを含む連結成分と、領域１０８乃至１１２と領域１２５乃至１２７とを含む連結成分と、領域１０５乃至１０７と領域１２３及び１２４とを含む連結成分とである。
【００５５】
領域１０５乃至１０７と領域１２３及び１２４とを含む連結成分の対岸は、領域１０３及び１０４と領域１２２とを含む連結成分と、領域１０８乃至１１２と領域１２５乃至１２７とを含む連結成分と、領域１１３及び１１４と領域１２８とを含む連結成分である。
【００５６】
領域１０８乃至１１２と領域１２５乃至１２７とを含む連結成分の対岸は、その他の連結成分全てである。
【００５７】
領域１１３及び１１４と領域１２８とを含む連結成分の対岸は、領域１０５乃至１０７と領域１２３及び１２４とを含む連結成分と、領域１０８乃至１１２と領域１２５乃至１２７とを含む連結成分と、領域１０１及び１０２と領域１２１とを含む連結成分である。
【００５８】
本実施の形態では、個々のジョブに対応する割り当て済み資源を管理して、未割り当て資源は「システムの全資源から「割り当て済み資源」を除いたもの」として間接的に管理するものとする。
【００５９】
また、本実施の形態では、例えば、各連結成分について、当該連結成分の対岸となる連結成分等を探索範囲の限界点として予め把握しておくことで、当該連結成分から行われ且つ新規ジョブのための資源を確保できるか否かを判断する探索処理の高速化を図る。
【００６０】
さらに、本実施の形態では、探索範囲によって探索処理の所要時間が大きく異なる事態を避けるために、資源割り当て状況の複雑度（すなわち、フラグメンテーション進行度）を表す新たなパラメタを導入することで、所要時間をより正確に見積もることができるようにする。
【００６１】
以上のような技術的事項を実現するための構成を以下具体的に説明する。
【００６２】
図４に示すように、並列計算機システム１は、複数の計算ノード２００がネットワーク２０を介して相互に通信可能に接続され、これにより相互結合網が構成されている。また、ネットワーク２０には、１つのマスタスケジューラノード３００と、複数のスレーブスケジューラノード３１０とが接続されている。
【００６３】
ネットワーク２０は通信回線であり、例えば、ＬＡＮ（Local Area Network）や光通信路である。
【００６４】
計算ノード２００は情報処理装置であり、互いに同様の構成を有する。図４に示すように、各計算ノード２００は、それぞれ、ＣＰＵ（Central Processing Unit）２０１、メモリ２０２及びＮＩＣ（Network Interface Card）２０３を有する。
【００６５】
ＮＩＣ２０３は、計算ノード２００をネットワーク２０に接続する通信部であり、ネットワーク２０を介して、他の計算ノード２００、マスタスケジューラノード３００、例えばユーザが操作する他の情報処理装置等との間でデータ通信を行う。ＮＩＣ２０３は、例えば、ＬＡＮインタフェースカードである。
【００６６】
メモリ２０２は、ＲＯＭ（Read Only Memory）及びＲＡＭ（Random Access Memory）を含む記憶装置である。メモリ２０２のＲＯＭには、各種演算に係るプログラムやこのプログラム用のデータが書き込まれている。メモリ２０２上のプログラムは、ＣＰＵ２０１に適宜読み込まれて実行される。また、メモリ２０２のＲＡＭは、ＣＰＵ２０１に実行されるプログラム及び当該プログラムによって用いられるデータを格納する。
【００６７】
ＣＰＵ２０１は、各種制御及び演算を行う処理装置であり、メモリ２０２に格納されたＯＳ（Operating System）及びプログラムを実行することにより、各種機能を実現する。すなわち、ＣＰＵ２０１は、ＮＩＣ２０３及びネットワーク２０を介して受信したデータに対して演算処理を行う。また、ＣＰＵ２０１は、演算処理結果等のデータを他の計算ノード２００等へ送信する場合には、そのデータをＮＩＣ２０３及びネットワーク２０を介して出力する。
【００６８】
上でも述べたように、ジョブは、本並列計算機システム１において１又は複数の計算ノード２００に割り当てられる。
【００６９】
マスタスケジューラノード３００は、スレーブスケジューラノード３１０を制御すると共に、ジョブを割り当てるべき計算ノード２００を決定する処理等を行うジョブ管理装置である。
【００７０】
マスタスケジューラノード３００は、ジョブ管理装置としての情報処理装置であり、ＣＰＵ３０１、メモリ３０２及びＮＩＣ３０３を有する。
【００７１】
ＮＩＣ３０３は、マスタスケジューラノード３００をネットワーク２０に接続する通信部であり、ネットワーク２０を介して計算ノード２００、スレーブスケジューラノード３１０及びユーザが操作する他の情報処理装置等との間でデータ通信を行う。ＮＩＣ３０３は、例えば、ＬＡＮインタフェースカードである。
【００７２】
メモリ３０２は、ＲＯＭ及びＲＡＭを含む記憶装置である。メモリ３０２のＲＯＭには、スレーブスケジューラノード３１０の制御を含むジョブスケジューリングに係るプログラム及びこのプログラム用のデータが書き込まれている。メモリ３０２上のプログラムは、ＣＰＵ３０１に適宜読み込まれて実行される。また、メモリ３０２のＲＡＭは、ＣＰＵ３０１に実行されるプログラム及び当該プログラムによって用いられるデータを格納する。
【００７３】
ＣＰＵ３０１は、各種制御及び演算を行う処理装置であり、メモリ３０２に格納されたＯＳ及びプログラムを実行することにより、ジョブスケジューラを含む各種機能を実現する。
【００７４】
スレーブスケジューラノード３１０は、マスタスケジューラノード３００からの指示に応じて、ジョブを割り当てることができる計算ノード２００を探索する処理等を行う。
【００７５】
スレーブスケジューラノード３１０は、情報処理装置であり、ＣＰＵ３１１、メモリ３１２及びＮＩＣ３１３を有する。
【００７６】
ＮＩＣ３１３は、スレーブスケジューラノード３１０をネットワーク２０に接続する通信部であり、ネットワーク２０を介して計算ノード２００、マスタスケジューラノード３００及びユーザが操作する他の情報処理装置等との間でデータ通信を行う。ＮＩＣ３１３は、例えば、ＬＡＮインタフェースカードである。
【００７７】
メモリ３１２は、ＲＯＭ及びＲＡＭを含む記憶装置である。メモリ３１２のＲＯＭには、ジョブに割り当てられる計算ノード２００を探索する処理等を実行するためのプログラム及びこのプログラム用のデータが書き込まれている。メモリ３１２上のプログラムは、ＣＰＵ３１１に適宜読み込まれて実行される。また、メモリ３１２のＲＡＭは、ＣＰＵ３１１に実行されるプログラム及び当該プログラムによって用いられるデータを格納する。
【００７８】
ＣＰＵ３１１は、各種制御及び演算を行う処理装置であり、メモリ３１２に格納されたＯＳ及びプログラムを実行することにより、計算ノード２００の探索機能を含む各種機能を実現する。
【００７９】
なお、スレーブスケジューラノード３１０は、ジョブが割り当てられていない計算ノード２００である場合もある。
【００８０】
次に、マスタスケジューラノード３００に実現される機能構成例を、図５に示す。マスタスケジューラノード３００は、データ格納部３０１０と、探索制御部３０２０と、ジョブ配置処理部３０３０と、データ管理部３０４０とを有する。
【００８１】
探索制御部３０２０は、データ格納部３０１０に格納されているデータに基づき、スレーブスケジューラノード３１０に実行させる探索処理の前処理を行い、その処理結果に基づき、スレーブスケジューラノード３１０に探索処理を実行させる。
【００８２】
ジョブ配置処理部３０３０は、スレーブスケジューラノード３１０による探索処理の処理結果に基づき、ジョブの割当先となる計算ノード２００を決定する処理等を実行する。
【００８３】
データ管理部３０４０は、データ格納部３０１０に格納されるデータの更新処理を実行し、式推定部３０４１を有する。式推定部３０４１は、探索制御部３０２０に用いられる探索処理時間の推定式の推定処理を実行する。
【００８４】
また、スレーブスケジューラノード３１０に実現される機能構成例を、図６に示す。スレーブスケジューラノード３１０は、データ格納部３１１０と、探索処理部３１２０と、データ管理部３１３０とを有する。
【００８５】
探索処理部３１２０は、データ格納部３１１０に格納されているデータに基づき、新たなジョブに対して割り当てるべき計算ノードが、探索処理の分担範囲内に存在しているか否かを判断する処理等を実行する。
【００８６】
データ管理部３１３０は、データ格納部３１１０に格納されているデータを維持管理する処理を行い、追加処理部３１３１と、削除処理部３１３２と、パラメタ算出部３１３３とを有する。
【００８７】
追加処理部３１３１は、探索処理の分担範囲内にジョブが追加された場合の処理を実行する。削除処理部３１３２は、探索処理の分担範囲内におけるジョブが終了した場合の処理を実行する。パラメタ算出部３１３３は、式推定部３０４１で用いられ且つ本実施の形態で導入されるパラメタの値を算出する処理を実行する。
【００８８】
なお、マスタスケジューラノード３００は、スレーブスケジューラノード３１０の機能及びデータを併せて有する場合もある。
【００８９】
次に、スレーブスケジューラノード３１０の動作について、主に図７乃至図２２を用いて説明する。スレーブスケジューラノード３１０は、マスタスケジューラノード３００からの指示に応じて、新たなジョブを割り当てられる計算ノード群を探索する探索処理を実行する。この探索処理を効率的に行うため、探索処理より前且つ探索処理を行っていない間に、データ格納部３１１０に格納されているデータを更新しておく。
【００９０】
上でも述べたように、本実施の形態では、例えば、各連結成分について、当該連結成分から探索処理が行われ、新規ジョブのための資源を確保できるか否かを判断することになる。このためには、連結成分の対岸となる連結成分等についてのデータを保持しておき、ジョブに対する計算ノードの割り当てに変更があれば、当該データを更新することで、次なる探索処理に備えることになる。
【００９１】
データ格納部３１１０には、探索処理の分担範囲に含まれるジョブのリストが格納されている。さらに、データ格納部３１１０は、図７に示すように、このジョブのリストに含まれる各ジョブについて、ジョブＩＤ（識別子）、ジョブ要求元のユーザＩＤ、並列計算機システム１において使用する資源についてのデータ、当該ジョブに接するジョブ（隣接ジョブと呼ぶ）のリストについてのデータ、当該ジョブの対岸であるジョブのリストである対岸リストについてのデータ、当該ジョブが属する連結成分についてのデータなどを格納している。
【００９２】
また、データ格納部３１１０は、図８に示すように、連結成分毎に、連結成分ＩＤ、当該連結成分の構成データ（連結成分に含まれるジョブのリストを含む）、当該連結成分の対岸であるジョブのリスト（連結成分についての対岸リスト）についてのデータ等を含む。
【００９３】
さらに、データ格納部３１１０は、隣接行列及び接続行列を格納している。
【００９４】
次に、主に図９乃至図２２を用いて、スレーブスケジューラノード３１０の処理内容について説明する。
【００９５】
まず、図９を用いて、メインの処理フローを説明する。
【００９６】
スレーブスケジューラノード３１０のデータ管理部３１３０は、探索処理部３１２０が探索未実施中に所定のイベントの発生を待機して、発生すると当該イベントを検出する（ステップＳ１）。所定のイベントとは、自スレーブスケジューラノード３１０が担当する連結成分の付近においてジョブの追加割り当てが行われたという通知を受信したというイベント、又は自スレーブスケジューラノード３１０が担当する連結成分においてジョブが終了したことを検出するか又は付近において計算資源の解放が行われたという通知を受信したというイベントである。ジョブの追加割り当てについての通知には、割当先の計算ノードを特定するためのデータが含まれる。
【００９７】
ジョブの追加というイベントを検出した場合には（ステップＳ３：Ｙｅｓルート）、データ管理部３１３０の追加処理部３１３１は、第１追加処理を実行する（ステップＳ５）。さらに、追加処理部３１３１は、第２追加処理を実行する（ステップＳ７）。第１及び第２追加処理については、後に詳しく述べるが、追加されたジョブに応じて隣接リスト及び対岸リストを更新する。そして処理はステップＳ１１に移行する。
【００９８】
一方、ジョブの追加というイベントではない場合には（ステップＳ３：Ｎｏルート）、ジョブの削除ということになるので、削除処理部３１３２は、削除処理を実行する（ステップＳ９）。この削除処理については、後に詳しく述べるが、計算資源の解放に応じて隣接リスト及び対岸リストを更新する。そして処理はステップＳ１１に移行する。
【００９９】
そして、パラメタ算出部３１３３は、複雑度算出処理を実行する（ステップＳ１１）。後に述べる複雑度を更新するための処理を実行する。複雑度算出処理については、後に詳しく述べる。
【０１００】
そして、データ管理部３１３０は、処理終了であるか否かを判断する（ステップＳ１３）。処理終了ではない場合には、処理はステップＳ１に戻る。一方、例えば処理終了が指示されると、処理を終了する。
【０１０１】
なお、探索処理部３１２０は、典型的にはマスタスケジューラノード３００からの指示に応じて探索処理を実行する。すなわち、図９の処理の前又は後に、探索処理は実行される。この探索処理については、後にマスタスケジューラノード３００の処理との関係で説明する。
【０１０２】
次に、第１追加処理について、図１０を用いて説明する。
【０１０３】
データ管理部３１３０の追加処理部３１３１は、追加されたジョブＪが、既存ジョブＪ０に接するか否かを判断する（ステップＳ３１）。既存ジョブＪ０は、自スレーブスケジューラノード３１０の分担範囲に含まれるジョブである。
【０１０４】
追加されたジョブＪが既存ジョブＪ０に接する場合には、追加処理部３１３１は、追加されたジョブＪを既存ジョブＪ０の隣接リストに追加登録する（ステップＳ４９）。そして処理は呼び出し元の処理に戻る。
【０１０５】
一方、追加されたジョブＪが既存ジョブＪ０に接しない場合には、追加処理部３１３１は、空の集合Ｌに対して、既存ジョブＪ０の更新前の対岸リストに含まれるジョブを登録する（ステップＳ３３）。
【０１０６】
その後、追加処理部３１３１は、集合Ｌが空であるか否かを判断する（ステップＳ３５）。集合Ｌが空であれば、処理は呼び出し元の処理に戻る。
【０１０７】
一方、集合Ｌが空ではない場合には、追加処理部３１３１は、変数Ｊ１に対して、集合Ｌの先頭ジョブを設定する（ステップＳ３７）。また、追加処理部３１３１は、集合ＬからジョブＪ１を除去する（ステップＳ３９）。
【０１０８】
そして、追加処理部３１３１は、既存ジョブＪ０から見てジョブＪがジョブＪ１より手前であるか否かを判断する（ステップＳ４１）。すなわち、既存ジョブＪ０の対岸であるジョブＪ１が、新規ジョブＪが配置されたことによって対岸ではなくなったか否かを判断している。
【０１０９】
既存ジョブＪ０から見てジョブＪがジョブＪ１より手前ではない場合には、追加処理部３１３１は、既存ジョブＪ０から見てジョブＪ１がジョブＪより手前であるか否かを判断する（ステップＳ４３）。この条件を満たす場合には、対岸リストを更新しなくてもよい、ジョブＪ１とジョブＪとの位置関係であるから、処理は呼び出し元の処理に戻る。
【０１１０】
一方、ステップＳ４３の条件が満たされない場合には、ジョブＪ１とジョブＪとが対向するような位置関係にないので、処理はステップＳ３５に戻る。
【０１１１】
既存ジョブＪ０から見てジョブＪがジョブＪ１より手前である場合には、追加処理部３１３１は、ジョブＪを既存ジョブＪ０の対岸リストに追加すると共に（ステップＳ４５）、その対岸リストからジョブＪ１を除去する（ステップＳ４７）。そして、処理は呼び出し元の処理に戻る。
【０１１２】
このようにして対岸リストや隣接リストが更新される。
【０１１３】
次に、第２追加処理について図１１を用いて説明する。
【０１１４】
追加処理部３１３１は、空の集合Ｃ０に対して、基準連結成分の構成ジョブリストを登録する（ステップＳ５１）。例えば自スレーブスケジューラノード３１０の分担範囲における連結成分を基準連結成分とする。但し、複数の連結成分が分担範囲に含まれる場合には、例えば予め定められた連結成分を基準連結成分とする。
【０１１５】
そして、追加処理部３１３１は、新規ジョブＪは、集合Ｃ０のいずれかのジョブに接するか否かを判断する（ステップＳ５３）。この条件を満たさない場合には、処理はステップＳ５７に移行する。一方、ステップＳ５３の条件を満たす場合には、追加処理部３１３１は、新規ジョブＪを、集合Ｃ０に追加する（ステップＳ５５）。これによって、基準連結成分の構成ジョブリストが更新される。
【０１１６】
そして、追加処理部３１３１は、空の集合Ｌに対して、基準連結成分の対岸リストに含まれるジョブを登録する（ステップＳ５７）。そして、追加処理部３１３１は、集合Ｌが空であるか否かを判断する（ステップＳ５９）。
【０１１７】
集合Ｌが空ではない場合には、追加処理部３１３１は、変数Ｃ１に集合Ｌの先頭ジョブを設定する（ステップＳ６１）。さらに、追加処理部３１３１は、集合ＬからジョブＣ１を除去する（ステップＳ６３）。そして、追加処理部３１３１は、第３追加処理を実行する（ステップＳ６５）。第３追加処理については、図１２を用いて説明する。そして処理はステップＳ５９に戻る。
【０１１８】
集合Ｌが空である場合には、追加処理部３１３１は、新規ジョブＪが複数の連結成分に属するか否かを判断する（ステップＳ６７）。ここでは、新規ジョブＪが複数の連結成分に接するように追加された場合を確認するものである。この条件を満たさない場合には、処理は呼び出し元の処理に戻る。
【０１１９】
一方、新規ジョブＪが複数の連結成分に属する場合には、追加処理部３１３１は、新規ジョブＪが属する全連結成分を統合して構成ジョブリストを更新する（ステップＳ６９）。そして処理は呼び出し元に戻る。
【０１２０】
次に、第３追加処理について図１２を用いて説明する。
【０１２１】
追加処理部３１３１は、空の集合Ｌ２に、ジョブＣ１の連結成分の構成ジョブリストを設定する（ステップＳ７１）。そして、追加処理部３１３１は、集合Ｌ２が空であるか否かを判断する（ステップＳ７３）。集合Ｌ２が空である場合には、処理は呼び出し元の処理に戻る。
【０１２２】
一方、集合Ｌ２が空ではない場合には、追加処理部３１３１は、変数Ｊ１に、集合Ｌ２の先頭ジョブを設定する（ステップＳ７５）。また、追加処理部３１３１は、集合Ｌ２からジョブＪ１を除去する（ステップＳ７７）。
【０１２３】
そして、追加処理部３１３１は、新規ジョブＪは、ジョブＪ１に接するか否かを判断する（ステップＳ７９）。新規ジョブＪがジョブＪ１に接しない場合には、処理はステップＳ７３に戻る。
【０１２４】
一方、新規ジョブＪがジョブＪ１に接する場合には、追加処理部３１３１は、新規ジョブＪをジョブＣ１の連結成分の構成ジョブリストに追加済みであるか否かを判断する（ステップＳ８１）。この条件を満たさない場合には、追加処理部３１３１は、新規ジョブＪをジョブＣ１の連結成分の構成ジョブリストに追加する（ステップＳ８３）。一方、ステップＳ８１の条件が満たされる場合には、処理はステップＳ８５に移行する。
【０１２５】
そして、追加処理部３１３１は、ジョブＪ１の隣接リストに新規ジョブＪが追加されていない場合には新規ジョブＪを追加する（ステップＳ８５）。そして処理はステップＳ７３に戻る。
【０１２６】
以上のような処理を実行することで、連結成分についてのデータが更新される。
【０１２７】
次に、削除処理について、図１３Ａ乃至図１５を用いて説明する。
【０１２８】
削除処理部３１３２は、変数Ｊに処理が終了したジョブを設定する（図１３Ａ：ステップＳ９１）。また、削除処理部３１３２は、空の集合Ｃ０に、ジョブＪが属する連結成分のジョブ群を設定する（ステップＳ９３）。
【０１２９】
そして、削除処理部３１３２は、集合Ｃ０からジョブＪを除去すると空集合になるか否かを判断する（ステップＳ９４）。すなわち、ジョブＪが属する連結成分がジョブＪのみを含むのか否かを判断するものである。
【０１３０】
ステップＳ９４の条件を満たす場合には、削除処理部３１３２は、集合Ｃ０に対応する連結成分のデータを削除する（ステップＳ９５）。集合Ｃ０に１つしかジョブがない場合にはこれ以上の処理は行われないため、処理は呼び出し元の処理に戻る。
【０１３１】
一方、ステップＳ９４の条件を満たさない場合には、削除処理部３１３２は、分解判定処理を実行する（ステップＳ９６）。分解判定処理については、後に述べるが、連結成分からジョブを除いたときに、複数の連結成分への分解が発生するか否かを判断する処理である。そして、削除処理部３１３２は、集合Ｃ０からジョブＪを除去すると複数の連結成分に分解するか否かを、分解判定処理の判定結果から判断する（ステップＳ９７）。この条件を満たさない場合には、処理は呼び出し元の処理に戻る。
【０１３２】
一方、ステップＳ９７の条件を満たす場合には、削除処理部３１３２は、データ格納部３１１０において、増加分の連結成分のためのエントリを生成する（ステップＳ９８）。また、削除処理部３１３２は、ジョブＪ以外の集合Ｃ０に属するジョブを、各連結成分に対して配分する（ステップＳ９９）。その後、削除処理部３１３２は、対岸リスト生成処理を実行する（ステップＳ１００）。対岸リスト生成処理については、図１４及び図１５を用いて説明する。そして処理は呼び出し元の処理に戻る。
【０１３３】
なお、複数の連結成分に分解する場合には、追加された連結成分に対してスレーブスケジューラノード３１０等の処理要素を割り当て又は追加する処理を行う場合もある。これは、マスタスケジューラノード３００によって行われる場合もある。
【０１３４】
次に、図１３Ｂを用いて分解判定処理について説明する。まず、削除処理部３１３２は、集合Ｌに対して、集合Ｃ０内でジョブＪが接するジョブを設定する（図１３Ｂ：ステップＳ１０１）。そして、削除処理部３１３２は、変数Ｊ１に対して、集合Ｌ内の任意のジョブを設定し、集合ＬからジョブＪ１を除外する（ステップＳ１０２）。
この分解判定処理は、「Ｊを取り除く前の連結成分Ｃ０からＪを取り除いた残りのジョブ群が１つの連結成分に属するか否か」を判定するものである。この連結性の判定は、「Ｊを除去したことにより、除去する前は同じ連結成分に属していた２ジョブが、異なる連結成分に属するようになるか」を判定すればよい。もしＪに接していたジョブ群Ｌが、Ｊを除去した後でも１つの連結成分に属するならば、Ｊの有無は全体の連結性に影響を及ぼさないことになるので、「Ｃ０に属するＪ以外のジョブ全て」の連結性を調べる代わりに、「Ｊに接していたジョブ全て（すなわちＬ）」の連結性を調べることになる。すなわち、以下のステップについては、集合Ｌ内の各ジョブについて行うことになる。
また、削除処理部３１３２は、集合Ｍに対して、集合Ｃ０からジョブＪを除いたジョブ集合内におけるジョブＪ１の連結成分を設定する（ステップＳ１０３）。そして、削除処理部３１３２は、判定結果に「分解しない」を設定し（ステップＳ１０４）、集合Ｌ内に、集合Ｍに含まれないジョブが存在するか否かを判断する（ステップＳ１０５）。このような条件が満たされる場合には、複数の連結成分に分解するので、削除処理部３１３２は、判定結果を「分解する」に設定し直す（ステップＳ１０６）。そして処理は呼び出し元の処理に戻る。一方、ステップＳ１０５の条件が満たされない場合には、処理は呼び出し元の処理に戻る。
【０１３５】
次に、対岸リスト生成処理について図１４及び図１５を用いて説明する。
【０１３６】
まず、削除処理部３１３２は、空の集合ＣＸに対して、分裂前の連結成分を設定する（ステップＳ１１１）。さらに、削除処理部３１３２は、空の集合Ｌ１に対して、分裂後の連結成分を設定する（ステップＳ１１３）。
【０１３７】
そして、削除処理部３１３２は、集合Ｌ１が空であるか否かを判断する（ステップＳ１１５）。集合Ｌ１が空になれば、処理は呼び出し元の処理に戻る。
【０１３８】
一方、集合Ｌ１が空でなければ、削除処理部３１３２は、変数Ｃに対して集合Ｌ１の先頭ジョブを設定する（ステップＳ１１７）。また、削除処理部３１３２は、集合Ｌ１からジョブＣを除去する（ステップＳ１１９）。
【０１３９】
そして、削除処理部３１３２は、空の集合Ｌ２に対して分裂後の連結成分を設定する（ステップＳ１２１）。また、削除処理部３１３２は、集合Ｌ２からジョブＣを除去する（ステップＳ１２３）。さらに、削除処理部３１３２は、空の集合Ｌ３に対して集合Ｌ２を設定する（ステップＳ１２５）。また、削除処理部３１３２は、空の集合Ｌ５に対して、分裂前の連結成分の対岸リストを登録する（ステップＳ１２７）。そして処理は端子Ｘを介して図１５の処理に移行する。
【０１４０】
図１５の処理の説明に移行して、削除処理部３１３２は、集合Ｌ５は空であるか否かを判断する（ステップＳ１２９）。集合Ｌ５が空になると、削除処理部３１３２は、ジョブＣの対岸リストを集合Ｌ３に設定する（ステップＳ１３１）。さらに、削除処理部３１３２は、ジョブＣ１の対岸リストに対して、ＣＸを削除し、集合Ｌ６の要素を追加する（ステップＳ１３３）。そして処理は端子Ｙを介して図１４のステップＳ１１５に戻る。
【０１４１】
一方、集合Ｌ５が空ではない場合には、削除処理部３１３２は、変数Ｃ１に対して、集合Ｌ５の先頭ジョブを設定する（ステップＳ１３５）。また、削除処理部３１３２は、集合Ｌ５からジョブＣ１を除去する（ステップＳ１３７）。さらに、削除処理部３１３２は、集合Ｌ６に空リストを設定する（ステップＳ１３９）。また、削除処理部３１３２は、集合Ｌ４に対して集合Ｌ３を設定する（ステップＳ１４１）。
【０１４２】
そして、削除処理部３１３２は、集合Ｌ４が空か否かを判断する（ステップＳ１４３）。集合Ｌ４が空であれば、処理はステップＳ１２９に戻る。一方、集合Ｌ４が空でなければ、削除処理部３１３２は、変数Ｃ２に対して、集合Ｌ４の先頭ジョブを設定する（ステップＳ１４５）。さらに、削除処理部３１３２は、集合Ｌ４からジョブＣ２を除去する（ステップＳ１４７）。
【０１４３】
そして、削除処理部３１３２は、ジョブＣから見てジョブＣ２がジョブＣ１の手前にあるか否かを判断する（ステップＳ１４９）。この条件を満たす場合には、処理はステップＳ１４３に戻る。一方、ステップＳ１４９の条件が満たされない場合には、削除処理部３１３２は、ジョブＣ１を集合Ｌ３に追加する（ステップＳ１５１）。さらに、削除処理部３１３２は、ジョブＣ２を集合Ｌ２に追加する（ステップＳ１５３）。そして処理はステップＳ１４３に戻る。
【０１４４】
このような処理を実行することで、分裂した２つの連結成分について対岸リストが生成される。
【０１４５】
次に、データ管理部３１３０のパラメタ算出部３１３３により実行される、複雑度を算出する複雑度算出処理（ステップＳ１１）について説明する。まず、複雑度の定義について説明する。
【０１４６】
連結成分が多い時、及び連結成分の形状が複雑な場合、フラグメンテーテーションが進行しているため、その範囲内での空き資源の探索処理には、より多くの時間がかかると考えられる。
【０１４７】
連結成分Ｃ⊂Ｘの形状の複雑度は、Ｃに属する頂点とＸの補集合Ｙに属する頂点とが、どの程度多くのリンクを通して隣接しているかに基き定める。本実施の形態では、次の定義１乃至５のように定義する。
定義１：
「Ｃの頂点集合の要素数｜Ｃ｜」に対する「Ｃに属する頂点に隣接し、Ｘの補集合Ｙに属する頂点の数（すなわち下記の集合Ｓ１の要素数｜Ｓ１｜）」の割合
Ｓ１＝｛ｖ∈Ｙ ｜ ∃ｖ1∈Ｃ ｖはｖ1と隣接する｝
とすると定義１における複雑度＝｜Ｓ１｜／｜Ｃ｜
【０１４８】
定義２：
「Ｃの頂点集合の要素数｜Ｃ｜」に対する「Ｃに属する複数の頂点に隣接し且つＸの補集合Ｙに属する頂点の数（すなわち下記の集合Ｓ２の要素数｜Ｓ２｜）」の割合
Ｓ２＝｛ｖ∈Ｙ | ∃ｖ1∈Ｃ ∃ｖ2∈Ｃ ｖ1≠ ｖ2  ｖはｖ1及びｖ2に隣接する｝
とすると定義２における複雑度＝｜Ｓ２｜／｜Ｃ｜
【０１４９】
定義３：
「Ｃの頂点集合の要素数｜Ｃ｜」に対する「Ｃの頂点でＸの補集合Ｙに属する頂点と隣接するものの数（すなわち下記の集合Ｓ３の要素数｜Ｓ３｜）」の割合
Ｓ３＝｛ｖ∈Ｃ | ∃ｖ1∈Ｙ  ｖはｖ1と隣接する｝
とすると定義３における複雑度＝｜Ｓ３｜／｜Ｃ｜
【０１５０】
定義４：
「Ｃの頂点集合の要素数｜Ｃ｜」に対する「一方の頂点がＣの要素であり且つ他方の頂点がＹの要素である辺の数｜Ｓ４｜」の割合
Ｓ４＝｛ｅ∈Ｅ | ∃ｖ1∈Ｃ ∃ｖ2∈Ｙ  ｅはｖ1とｖ2を結ぶ辺｝
とすると定義４における複雑度＝｜Ｓ４｜／｜Ｃ｜
【０１５１】
定義５：
「両端がＣの頂点である辺の数｜Ｓ５｜」に対する「一方の頂点がＣの要素であり且つ他方の頂点がＹの要素であるような辺の数｜Ｓ４｜」の割合
Ｓ４＝｛ｅ∈Ｅ | ∃ｖ1∈Ｃ ∃ｖ2∈Ｙ  ｅはｖ1とｖ2を結ぶ辺｝
Ｓ５＝｛ｅ∈Ｅ | ∃ｖ1∈Ｃ ∃ｖ2∈Ｃ  ｅはｖ1とｖ2を結ぶ辺｝
とすると定義５における複雑度＝｜Ｓ４｜／｜Ｓ５｜
【０１５２】
例えば、並列計算機システムのネットワークトポロジがメッシュとなっており、図１６に示すように、ジョブが割り当てられた計算ノードを黒丸で表し、ジョブが割り当てられていない計算ノードを白丸で表すものとする。そうすると、上で述べた定義１乃至５の複雑度は以下のように計算される。
【０１５３】
定義１において｜Ｓ１｜は、黒丸に接続された白丸の数であるから、点線で囲まれた白丸の数となる。従って、｜Ｓ１｜＝２６となる。｜Ｃ｜は黒丸の数であるから、｜Ｃ｜＝３８となる。従って、定義１の複雑度は、｜Ｓ１｜／｜Ｃ｜＝２６／３８となる。
【０１５４】
定義２において｜Ｓ２｜は、複数の黒丸に接続された白丸の数であるから、実線で囲まれた白丸の数となる。従って、｜Ｓ２｜＝２となる。よって、定義２の複雑度は、｜Ｓ２｜／｜Ｃ｜＝２／３８となる。
【０１５５】
定義３において｜Ｓ３｜は、白丸に接続された黒丸の数であるから、一点鎖線で囲まれた黒丸の数となる。従って、定義３の複雑度は、｜Ｓ３｜／｜Ｃ｜＝２２／３８となる。
【０１５６】
定義４において｜Ｓ４｜は、白丸と黒丸とを結ぶ辺の数であるから、図１７の実線で囲まれた辺の数となる。従って、定義４の複雑度は、｜Ｓ４｜／｜Ｃ｜＝２８／３８となる。
【０１５７】
定義５において｜Ｓ５｜は、黒丸と黒丸とを結ぶ辺の数であるから、Ｓ４で包囲される範囲内の全辺の数となる。従って、定義５の複雑度は、｜Ｓ４｜／｜Ｓ５｜＝２８／６２となる。
【０１５８】
これらの複雑度及びＳ１乃至Ｓ５は、ジョブに対する資源の割り当て及び割り当てた資源の解放処理を契機に又は定期的に、一般にはグラフの隣接行列や接続行列に基いて次に述べるような処理にて計算する。
【０１５９】
まず、図１８を用いて、定義１の複雑度を算出するための処理について説明する。
【０１６０】
パラメタ算出部３１３３は、空の集合Ｌ１に、Ｃに属する頂点の番号（ジョブが割り当てられている計算ノードの番号）に対応する、隣接行列の行番号リストを登録する（ステップＳ２０１）。
【０１６１】
また、パラメタ算出部３１３３は、カウンタｉを０に初期化する（ステップＳ２０３）。
【０１６２】
さらに、パラメタ算出部３１３３は、集合Ｌ１が空であるか否かを判断する（ステップＳ２０５）。集合Ｌ１が空になると、パラメタ算出部３１３３は、複雑度をカウンタｉ／｜Ｃ｜によって算出する（ステップＳ２１９）。そして処理を終了する。
【０１６３】
一方、集合Ｌ１が空でない場合には、パラメタ算出部３１３３は、変数ｍに、集合Ｌ１の先頭要素を設定し、集合Ｌ１からｍを除去する（ステップＳ２０７）。
【０１６４】
また、パラメタ算出部３１３３は、空の集合Ｌ２に、Ｙに属する頂点の番号（ジョブが割り当てられていない計算ノードの番号）に対応する、隣接行列の列番号リストを登録する（ステップＳ２０９）。
【０１６５】
そして、パラメタ算出部３１３３は、集合Ｌ２が空であるか否かを判断する（ステップＳ２１１）。集合Ｌ２が空である場合には、処理はステップＳ２０５に戻る。
【０１６６】
一方、集合Ｌ２が空ではない場合には、パラメタ算出部３１３３は、変数ｎに、集合Ｌ２の先頭要素を設定し、集合Ｌ２からｎを除去する（ステップＳ２１３）。
【０１６７】
そして、パラメタ算出部３１３３は、隣接行列の（ｍ，ｎ）成分が０であるか否かを判断する（ステップＳ２１５）。隣接行列の（ｍ，ｎ）成分が０である場合には、処理はステップＳ２１１に移行する。
【０１６８】
一方、隣接行列の（ｍ，ｎ）成分が０ではない場合には、パラメタ算出部３１３３は、ｉを１インクリメントする（ステップＳ２１７）。そして処理はステップＳ２１１に移行する。
【０１６９】
このような処理にて定義１の複雑度が算出される。
【０１７０】
次に、図１９を用いて定義２の複雑度を算出するための処理について説明する。
【０１７１】
パラメタ算出部３１３３は、空の集合Ｌ１に、Ｃに属する頂点の番号（ジョブが割り当てられている計算ノードの番号）に対応する行が１である、接続行列の列番号リストを設定する（ステップＳ２２１）。
【０１７２】
また、パラメタ算出部３１３３は、カウンタｉを０に初期化する（ステップＳ２２３）。
【０１７３】
さらに、パラメタ算出部３１３３は、集合Ｌ１が空であるか否かを判断する（ステップＳ２２５）。集合Ｌ１が空になると、パラメタ算出部３１３３は、複雑度をカウンタｉ／｜Ｃ｜によって算出する（ステップＳ２３３）。そして処理を終了する。
【０１７４】
一方、集合Ｌ１が空でない場合には、パラメタ算出部３１３３は、変数ｋに、集合Ｌ１の先頭要素を設定し、集合Ｌ１からｋを除去する（ステップＳ２２７）。
【０１７５】
また、パラメタ算出部３１３３は、接続行列の第ｋ列において１である要素の一方がＣに属する頂点であり且つ他方がＹに属する頂点に対応するか否かを判断する（ステップＳ２２９）。この条件を満たさない場合には、処理はステップＳ２２５に戻る。一方、ステップＳ２２９の条件を満たす場合には、パラメタ算出部３１３３は、ステップＳ２２９で検出されたＹの頂点が、Ｃに属する複数の頂点と隣接しているか否かを判断する（ステップＳ２３１）。この条件を満たさない場合には、処理はステップＳ２２５に戻る。
【０１７６】
一方、ステップＳ２３１の条件を満たす場合には、パラメタ算出部３１３３は、ｉを１インクリメントする（ステップＳ２３２）。そして処理はステップＳ２２５に戻る。
【０１７７】
このような処理にて定義２の複雑度が算出される。
【０１７８】
次に、図２０を用いて定義３の複雑度を算出するための処理について説明する。
【０１７９】
パラメタ算出部３１３３は、空の集合Ｌ１に、Ｃに属する頂点の番号に対応する行が１である、接続行列の列番号リストを設定する（ステップＳ２５１）。また、パラメタ算出部３１３３は、カウンタｉを０に初期化する（ステップＳ２５３）。
【０１８０】
そして、パラメタ算出部３１３３は、集合Ｌ１が空であるか否かを判断する（ステップＳ２５５）。集合Ｌ１が空になると、パラメタ算出部３１３３は、複雑度をカウンタｉ／｜Ｃ｜によって算出する（ステップＳ２６３）。そして処理を終了する。
【０１８１】
一方、集合Ｌ１が空ではない場合には、パラメタ算出部３１３３は、変数ｋに、集合Ｌ１の先頭要素を設定し、集合Ｌ１からｋを除去する（ステップＳ２５７）。
【０１８２】
そして、パラメタ算出部３１３３は、接続行列の第ｋ列で１である要素の一方が、Ｃの頂点に対応し且つ他方がＹの頂点に対応するか否かを判断する（ステップＳ２５９）。この条件が満たされる場合には、パラメタ算出部３１３３は、ｉを１インクリメントする（ステップＳ２６１）。そして処理はステップＳ２５５に戻る。一方、ステップＳ２５９の条件が満たされない場合にも、処理はステップＳ２５５に戻る。
【０１８３】
このような処理にて定義３の複雑度が算出される。
【０１８４】
このように接続行列及び隣接行列を用いれば正確に複雑度を算出できる。しかしながら、一様乱数によるモンテカルロ法により、複雑度の近似計算をしてもよい。例えば、１以上｜Ｃ｜以下の正の整数を同じ確率でランダムに所定の回数発生させ、対応する頂点がＳ１、Ｓ２、Ｓ３等に属していた割合を、｜Ｓ１｜／｜Ｃ｜、｜Ｓ２｜／｜Ｃ｜、｜Ｓ３｜／｜Ｃ｜等の複雑度の近似値として用いるようにしても良い。
【０１８５】
ここで、定義４の複雑度を、乱数を用いて算出する処理の例を図２１を用いて説明する。まず、パラメタ算出部３１３３は、空の集合Ｌ１に、接続行列の列で頂点ｖ（例えばＣに属する頂点）に対応する要素が０でない列番号を等確率で所定個選択して設定する（ステップＳ２７１）。
【０１８６】
また、パラメタ算出部３１３３は、カウンタｓを０に初期化する（ステップＳ２７３）。
【０１８７】
さらに、パラメタ算出部３１３３は、Ｃの要素数に等しい長さで、全ての要素が０である配列ａ［］を生成する（ステップＳ２７５）。
【０１８８】
そして、パラメタ算出部３１３３は、集合Ｌ１が空であるか否かを判断する（ステップＳ２７７）。空でない場合には、パラメタ算出部３１３３は、ｅに集合Ｌ１の先頭要素を設定し、ｅを集合Ｌ１から除去する（ステップＳ２７９）。
【０１８９】
さらに、パラメタ算出部３１３３は、接続行列において、ｅの０でない成分の一方がＹの頂点であるか否かを判断する（ステップＳ２８１）。
【０１９０】
この条件を満たす場合には、パラメタ算出部３１３３は、ｓを１インクリメントする（ステップＳ２８３）。また、パラメタ算出部３１３３は、ｎに、接続行列においてｅの１である要素に対応する行番号を設定する（ステップＳ２８５）。そして、パラメタ算出部３１３３は、ａ［ｎ］＝１と設定する（ステップＳ２８７）。処理はステップＳ２７７に戻る。
【０１９１】
一方、ステップＳ２８１の条件が満たされない場合には、パラメタ算出部３１３３は、ｍ及びｎに、接続行列においてｅの１である要素に対応する行番号を設定する（ステップＳ２８９）。そして、パラメタ算出部３１３３は、ａ［ｎ］＝１及びａ［ｍ］＝１を設定する（ステップＳ２９１）。そして処理はステップＳ２７７に戻る。
【０１９２】
また、ステップＳ２７７で集合Ｌ１が空になったと判断された場合、パラメタ算出部３１３３は、変数ｋにａ［］において０でない要素の数を設定する（ステップＳ２９３）。そして、パラメタ算出部３１３３は、ｓ／ｋを｜Ｓ４｜／｜Ｃ｜の近似値として設定する（ステップＳ２９５）。
【０１９３】
このような処理にて定義４の複雑度の近似値が得られる。
【０１９４】
さらに、定義５の複雑度を、乱数を用いて算出する処理の例を図２２を用いて説明する。
【０１９５】
まず、パラメタ算出部３１３３は、空の集合Ｌ１に、接続行列の列で頂点ｖ（例えばＣに属する頂点）に対応する要素が０でない列番号を等確率で所定個選択して設定する（ステップＳ３０１）。
【０１９６】
また、パラメタ算出部３１３３は、カウンタｓを０に初期化する（ステップＳ３０３）。さらに、パラメタ算出部３１３３は、カウンタｔを０に初期化する（ステップＳ３０５）。
【０１９７】
そして、パラメタ算出部３１３３は、集合Ｌ１が空か否かを判断する（ステップＳ３０７）。空でない場合には、パラメタ算出部３１３３は、ｅに集合Ｌ１の先頭要素を設定し、ｅを集合Ｌ１から除去する（ステップＳ３０９）。
【０１９８】
そして、パラメタ算出部３１３３は、接続行列において、ｅの０でない成分の一方がＹの頂点であるか否かを判断する（ステップＳ３１１）。この条件が満たされる場合には、パラメタ算出部３１３３は、ｓを１インクリメントする（ステップＳ３１３）。そして処理はステップＳ３０７に移行する。一方、この条件が満たされない場合には、パラメタ算出部３１３３は、ｔを１インクリメントする（ステップＳ３１５）。そして処理はステップＳ３０７に戻る。
【０１９９】
ステップＳ３０７で集合Ｌ１が空であると判断されると、パラメタ算出部３１３３は、ｔ／ｓを、｜Ｓ４｜／｜Ｓ５｜の近似値として設定する（ステップＳ３１９）。
【０２００】
このような処理を行うことで、複雑度が算出される。
【０２０１】
このような複雑度は、連結成分ＩＤに対応付けて例えばスレーブスケジューラノード３１０からマスタスケジューラノード３００に送信され、マスタスケジューラノード３００は、連結成分ＩＤに対応付けて複雑度を、データ格納部３０１０に格納する。
【０２０２】
その後、後に述べる探索処理をスレーブスケジューラノード３１０が実行すると、探索の基準とした連結成分の連結成分ＩＤと対応付けて、連結成分の数、ジョブを割り当てられる計算ノード２００を検出できたか否かを表すデータ及び処理時間（負荷評価指標の一例）のデータも、スレーブスケジューラノード３１０からマスタスケジューラノード３００に送信される。マスタスケジューラノード３００は、連結成分ＩＤに対応付けて、連結成分の数、ジョブを割り当てられる計算ノード２００を検出できたか否かを表すデータ及び処理時間のデータを、データ格納部３０１０に格納する。探索処理を実行した処理要素の数を含めるようにしても良い。
【０２０３】
マスタスケジューラノード３００のデータ管理部３０４０における式推定部３０４１は、データ格納部３０１０に、スレーブスケジューラノード３１０から受信したデータがある程度蓄積されると、処理時間の推定式を生成する。
【０２０４】
第１の方法としては、一定範囲内におけるジョブが割り当て済みとなっている計算ノードの連結成分の数と、それらの連結成分の複雑度（５つの定義の少なくとも１つ）を説明変数とし、処理時間を非説明変数とする推定式を、例えば重回帰分析又はカルマンフィルタによって回帰式を生成する。例えば、一定範囲内に連結成分が３つあれば、複雑度としては３つの複雑度の和などを用いる。
【０２０５】
なお、説明変数は、連結成分の数及びそれらの連結成分の複雑度の代わりに、それらの任意の単調増加関数（指数関数、指数が正のべき乗関数、対数など）を用いても良い。さらに、連結成分の数及び複雑度に加えて、それらの少なくともいずれかの単調増加関数を採用するようにしても良い。
【０２０６】
なお、処理時間については、適切な性能モデルを用意して、シミュレーションによって得られた値を用いるようにしても良い。
【０２０７】
式推定部３０４１は、このように生成した推定式のデータについては、データ格納部３０１０に格納しておく。
【０２０８】
第２の方法としては、ジョブが割り当てられる計算ノード２００を検出できる確率である成功確率をも予想する。このように予測された成功確率が大きい分担範囲に対して、より多くの計算ノードを配分することが意味を有する場合があるためである。
【０２０９】
ここでは、このような成功確率の推定に対してベイズ推定を行う。そして、ベイズ推定の方法としては、例えば各説明変数が全て独立とみなして計算する手法を採用する。説明変数は、第１の方法で述べた説明変数を用いても良いが、具体的な形については第１の方法とは異なる場合もある。なお、ベイズ推定におけるパラメタ変換については、カーネル法など、さまざまな手法が知られているので、いずれかを用いる。このような成功確率を推定するためのデータは、データ格納部３０１０に格納される。場合によっては、重回帰分析を行うようにしても良い。
【０２１０】
さらに、第２の方法では、このように予測された成功確率も考慮して、カルマンフィルタに基づいて処理時間を推定するためのデータを生成し、データ格納部３０１０に格納しておく。
【０２１１】
次に、マスタスケジューラノード３００の主要な動作について説明する。
【０２１２】
図２３に、マスタスケジューラノード３００のメインの処理フローを示す。
【０２１３】
マスタスケジューラノード３００の探索制御部３０２０は、ネットワーク２０に接続された他の端末などからの新規ジョブを受け付ける（ステップＳ４０１）。新規ジョブのデータとしては、ジョブＩＤ、ユーザＩＤ、計算資源のサイズ（Ｎ（Ｎは整数）次元であれば各次元において使用する計算ノード２００の個数など。時間をも含む。）等のデータを含む。なお、新規ジョブのキューなどから、今回処理すべきジョブを読み出すようにしても良い。
【０２１４】
そうすると、探索制御部３０２０は、処理時間の見積もり処理を実行する（ステップＳ４０３）。この処理については、図２４を用いて説明する。但し、上で述べた処理時間の推定式などの、処理時間を推定するためのデータを用いて、予め定められた分担範囲毎（例えば、連結成分毎。但し、分担範囲には複数の連結成分を含む場合もある。）に処理時間を見積もる。
【０２１５】
その後、探索制御部３０２０は、見積もられた処理時間に応じて各分担範囲に対して、探索処理を行うための資源の配分を決定する（ステップＳ４０５）。例えば、見積もられた処理時間の比に応じて資源を配分する。より具体的には、４つの分担範囲があって、１０：５：３：１という処理時間の比が得られた場合には、第１の分担範囲には１０個の資源を割り当て、第２の分担範囲には５つの資源を割り当て、第３の分担範囲には３つの資源を割り当て、第４の分担範囲には１つの資源を割り当てる。基本的にスレーブスケジューラノード３１０を割り当てるが、ジョブが割り当てられていない計算ノード２００を割り当てても良い。
【０２１６】
そして、探索制御部３０２０は、資源配分の結果に基づきスレーブスケジューラノード３１０（場合によっては計算ノード２００を含む）に対して探索処理を実行させる（ステップＳ４０７）。探索処理については、図２５及び図２６を用いて説明する。例えば、各分担範囲について、例えば連結成分の基準点から当該連結成分の対岸となる連結成分までに、新規ジョブを割り当てられる計算ノード２００が存在するか否かを判断する。スレーブスケジューラノード３１０は、探索結果を、マスタスケジューラノード３００に送信する。探索結果は、新規ジョブを割り当てられる計算ノード２００が検出できた場合には、例えば、検出成功を表すデータと、処理時間と、新規ジョブを割り当てられる計算ノード２００を特定するためのデータとを含む。新規ジョブを割り当てられる計算ノード２００を検出できなかった場合には、探索結果は、例えば、検出失敗を表すデータと、処理時間とを含む。
【０２１７】
そして、ジョブ配置処理部３０３０は、探索結果の評価処理を実行する（ステップＳ４０９）。探索結果の評価処理については、図２７乃至図３０を用いて説明する。例えば、新規ジョブ配置のためのポリシーに応じた探索結果の評価によって、新規ジョブを割り当てられる計算ノード２００のうちいずれを採用するのかを決定するための処理が行われる。
【０２１８】
その後、ジョブ配置処理部３０３０は、評価結果に基づき、新規ジョブを計算ノード２００に配置するための処理を実行する（ステップＳ４１１）。具体的には、評価結果に基づき特定される計算ノード２００に対して新規ジョブの実行を指示する。
【０２１９】
なお、この後に、上で述べた複雑度の更新結果を受信すると、処理時間の推定式などの更新を行うようにしても良い。
【０２２０】
このような処理を行うことで、システム全体として並列的な探索処理が効率的に行われ、新規ジョブが適切な計算ノード２００に配置されるようになる。
【０２２１】
次に、処理時間の見積もり処理（ステップＳ４０３）の一例について図２４を用いて説明する。
【０２２２】
探索制御部３０２０は、空の集合Ｌに対して、分担範囲のリストを設定する（ステップＳ４２１）。そして、探索制御部３０２０は、集合Ｌが空であるか否かを判断する（ステップＳ４２３）。集合Ｌが空であれば、呼び出し元の処理に戻る。
【０２２３】
一方、集合Ｌが空でない場合には、探索制御部３０２０は、変数ａに、集合Ｌにおける先頭の分担範囲を設定する（ステップＳ４２５）。また、探索制御部３０２０は、集合Ｌから変数ａを除去する（ステップＳ４２７）。
【０２２４】
そして、探索制御部３０２０は、分担範囲ａにおける探索処理の所要時間（すなわち処理時間）を、例えばデータ格納部３０１０に格納されている推定式のデータ及び当該分担範囲ａのデータを用いて推定する（ステップＳ４２９）。より詳しくは、データ格納部３０１０には、分担範囲ａについての複雑度のデータ及び含まれる連結成分の数が格納されており、これらのデータを推定式に代入することで、処理時間を算出し、例えばデータ格納部３０１０に格納する。そして処理はステップＳ４２３に戻る。
【０２２５】
以上のような処理を実施すれば、各分担範囲について処理時間の見積もりが行われる。
【０２２６】
次に、スレーブスケジューラノード３１０によって実行される探索処理（ステップＳ４０７）の一例について図２５及び図２６を用いて説明する。なお、ここではＮ次元メッシュ又はトーラスといったグラフを想定した処理を示すが、これは対岸リストによって処理が高速化するという点を分かりやすくするためである。
【０２２７】
まず、探索処理部３１２０は、新規ジョブＪのデータを取得する（ステップＳ４４１）。上で述べたように、新規ジョブＪのデータは、ジョブＩＤ、ユーザＩＤ、計算資源のサイズ等を含み、マスタスケジューラノード３００から得られる。
【０２２８】
そして、探索処理部３１２０は、新規ジョブＪの各次元ｉのサイズを、変数ｓ（ｉ）（ｉは１以上Ｎ以下）に設定する（ステップＳ４４３）。さらに、探索処理部３１２０は、空の集合ＣＬに対して、自らの分担範囲に対して予め定められた探索基準点のリストを設定する（ステップＳ４４５）。探索基準点は、例えば、分担範囲に複数の連結成分が存在する場合には、各連結成分について少なくとも１つは設定される。
【０２２９】
そして、探索処理部３１２０は、集合ＣＬが空であるか否かを判断する（ステップＳ４４７）。集合ＣＬが空である場合には、探索処理部３１２０は、探索結果に対して検出失敗を設定し、探索結果をマスタスケジューラノード３００に送信する（ステップＳ４５５）。そして処理は呼び出し元の処理に戻る。なお、探索結果と共に処理時間を併せて送信するようにしても良い。
【０２３０】
一方、集合ＣＬが空ではない場合には、探索処理部３１２０は、集合ＣＬから、１つの探索基準点ｃを取り出し、ｃを集合ＣＬから除去する（ステップＳ４４９）。そして、探索処理部３１２０は、空の集合Ｊ１に対して、ｃに隣接するジョブを設定する（ステップＳ４５１）。例えば、ｃを含むジョブについて設定されている隣接ジョブのリストを集合Ｊ１に設定する。隣接ジョブは複数存在する可能性がある。なお、隣接ジョブが存在しない場合には、ｃについてのジョブを集合Ｊ１に設定する。
【０２３１】
そして、探索処理部３１２０は、集合Ｊ１が空か否かを判断する（ステップＳ４５２）。集合Ｊ１が空の場合には、処理はステップＳ４４７に戻る。一方、集合Ｊ１が空ではない場合には、探索処理部３１２０は、集合Ｊ１から、１つのジョブＪ２を取り出し、集合Ｊ１からジョブＪ２を除去する（ステップＳ４５３）。
【０２３２】
さらに、探索処理部３１２０は、集合ＳＬに対して、ジョブＪ２の各次元の対岸リストを設定する（ステップＳ４５４）。そして処理は端子Ａを介して図２６の処理に移行する。
【０２３３】
端子Ａを介して図２６の処理の説明に移行して、探索処理部３１２０は、集合ＳＬが空であるか否かを判断する（ステップＳ４５６）。集合ＳＬが空であれば、処理は端子Ｂを介してステップＳ４５２に戻る。
【０２３４】
一方、集合ＳＬが空ではない場合には、探索処理部３１２０は、集合ＳＬから、対岸リストに含まれる１つのジョブＳを取り出し、ジョブＳを集合ＳＬから除去する（ステップＳ４５７）。
【０２３５】
そして、探索処理部３１２０は、ジョブＳの対岸リストがジョブＪ２を含み、且つジョブＪ２はｃとジョブＳとで挟まれるか否かを判断する（ステップＳ４５９）。これは、探索基準点ｃに係るジョブを含む連結成分について対岸であるジョブＳから見て、探索基準点ｃと隣接ジョブＪ２とジョブＳとの位置関係が、隣接ジョブＪ２とジョブＳとの間の空き資源を探索するという観点において適切であるか否かを確認するものである。この条件を満たさない場合には、処理はステップＳ４５６に戻る。
【０２３６】
ステップＳ４５９の条件が満たされる場合には、探索処理部３１２０は、ｄ（ｉ）に、各次元ｉ（ｉは１以上Ｎ以下の整数）におけるジョブＪ２とジョブＳとの距離を設定する（ステップＳ４６１）。距離は、例えば間に存在する計算ノード２００の数である。
【０２３７】
そして、探索処理部３１２０は、いずれかのｉについてｓ（ｉ）≦ｄ（ｉ）となっているかを判断する（ステップＳ４６３）。全てのｉについてｓ（ｉ）≦ｄ（ｉ）となっているかを判断するようにしても良い。この条件が満たされない場合には、処理はステップＳ４５６に移行する。
【０２３８】
一方、ステップＳ４６３の条件が満たされた場合には、探索処理部３１２０は、探索結果を、例えばマスタスケジューラノード３００に送信する（ステップＳ４６５）。そして、処理は端子Ｃを介して呼び出し元の処理に戻る。なお、探索結果には、探索基準点ｃが含まれる場合もあれば、例えばジョブＪ２とジョブＳを特定するためのデータの場合もある。
【０２３９】
なお、この処理では、条件を満たす１つの空き資源が得られると処理を終了するが、より多くの空き資源を見つけるように処理内容を変更しても良い。例えば、ステップＳ４６５からステップＳ４５６に戻るようにして、ステップＳ４５５についても、それまでに検出された空き資源についてのデータを含む探索処理を、マスタスケジューラノード３００に送信しても良い。
【０２４０】
さらに、この探索処理では、探索基準点毎に、さらに処理を並列化させることで処理の高速化が図られる。すなわち、探索範囲に複数のスレーブスケジューラノード３１０（ジョブが割り当てられていない計算ノード２００である場合も含む）が割り当てられた場合には、探索基準点毎に処理を分担すればよい。
【０２４１】
次に、探索結果の評価処理（ステップＳ４０９）の一例について図２７乃至図３０を用いて説明する。
【０２４２】
まず、マスタスケジューラノード３００のジョブ配置処理部３０３０は、カウンタ変数ｃｏｕｎｔに０を設定する（ステップＳ５０１）。そして、ジョブ配置処理部３０３０は、カウンタ変数ｃｏｕｎｔの値が分担範囲数より小さいか否かを判断する（ステップＳ５０３）。
【０２４３】
カウンタ変数ｃｏｕｎｔの値が分担範囲数より小さい場合には（ステップＳ５０３：Ｎｏルート）、ジョブ配置処理部３０３０は、スレーブスケジューラノード３１０からの探索結果を待機し、探索結果のデータを受信すると、例えばデータ格納部３０１０に格納する（ステップＳ５０５）。
【０２４４】
そうすると、ジョブ配置処理部３０３０は、カウンタ変数ｃｏｕｎｔを１インクリメントし（ステップＳ５０７）、受信した探索結果が空き資源検出を示しているか否かを判断する（ステップＳ５０９）。受信した探索結果が空き資源検出を示していない場合には、処理はステップＳ５０３に戻る。
【０２４５】
一方、受信した探索結果が空き資源検出を示している場合には、ジョブ配置処理部３０３０は、検出した空き資源に新規ジョブを割り当てた場合における評価値を算出し、当該空き資源に対応付けてデータ格納部３０１０に格納する（ステップＳ５１１）。そして処理はステップＳ５０３に戻る。
【０２４６】
本処理フローでは、新規ジョブの要求に適合する空き資源が複数見つかった場合は、何らかの評価基準に基づき評価値を算出し、最も評価値が高い空き資源を選択する。これは、一般的にはベストフィットと呼ばれる割り当てポリシーであるが、用いられる評価基準は、必ずしもジョブを割り当てる資源の「形状」に関するもののみに限定されない。
【０２４７】
例えば、「評価基準」として「使用可能時間帯が早いほどよい」という条件を設定すると、結果的に時間軸に関する割り当てポリシーとして「先着優先」を実現することになる。さらに、「使用可能時間帯が同じ場合は、割り当て後のフラグメンテーションの進行度が小さいほどよい」という条件や、「ジョブが有する１又は複数の属性についての一致度が高いほどよい」という基準にしてもよい。
【０２４８】
一方、カウンタ変数ｃｏｕｎｔの値が分担範囲数以上となると（ステップＳ５０３：Ｙｅｓルート）、ジョブ配置処理部３０３０は、評価値が最良である空き資源（大きい方が良い場合には評価値最大の空き資源、小さい方が良い場合には評価値最小の空き資源）を選択する（ステップＳ５１３）。なお、評価値が算出された空き資源が存在しない場合もあるので、そのような場合には、本処理を終了して、以降の処理を停止する。
【０２４９】
そして、ジョブ配置処理部３０３０は、探索処理を行った処理要素（計算ノード２００を含む）を、選択された空き資源が含むか否かを判断する（ステップＳ５１５）。ジョブが割り当てられていない計算ノード２００をスレーブスケジューラノード３１０として用いている場合、その計算ノード２００に新規ジョブが割り当てられるようになるのか否かを確認するものである。
【０２５０】
探索処理を行った処理要素を、選択された空き資源が含む場合には、ジョブ配置処理部３０３０は、その処理要素による探索処理を停止させる（ステップＳ５１７）。そして処理は呼び出し元の処理に戻る。一方、探索処理を行った処理要素を、選択された空き資源が含まない場合にも、処理は呼び出し元の処理に戻る。
【０２５１】
なお、探索結果の評価処理（ステップＳ４０９）については図２８の処理を採用しても良い。
【０２５２】
まず、マスタスケジューラノード３００のジョブ配置処理部３０３０は、カウンタ変数ｃｏｕｎｔに０を設定する（ステップＳ５２１）。そして、ジョブ配置処理部３０３０は、カウンタ変数ｃｏｕｎｔの値が分担範囲数より小さいか否かを判断する（ステップＳ５２３）。
【０２５３】
カウンタ変数ｃｏｕｎｔの値が分担範囲数より小さい場合には（ステップＳ５２３：Ｙｅｓルート）、ジョブ配置処理部３０３０は、スレーブスケジューラノード３１０からの探索結果を待機し、探索結果のデータを受信すると、例えばデータ格納部３０１０に格納する（ステップＳ５２５）。
【０２５４】
そうすると、ジョブ配置処理部３０３０は、カウンタ変数ｃｏｕｎｔを１インクリメントし（ステップＳ５２７）、受信した探索結果が空き資源検出を示しているか否かを判断する（ステップＳ５２９）。受信した探索結果が空き資源検出を示していない場合には、処理はステップＳ５２３に戻る。
【０２５５】
一方、受信した探索結果が空き資源検出を示している場合には、ジョブ配置処理部３０３０は、検出した空き資源に新規ジョブを割り当てた場合における評価値を算出する（ステップＳ５３１）。評価基準については、上で述べた例と同様である。
【０２５６】
ここで、本実施の形態では、ジョブ配置処理部３０３０は、算出された評価値が閾値以上であれば（ステップＳ５３３：Ｎｏルート）、今回の探索結果についての空き資源を選択する（ステップＳ５３５）。そして処理は呼び出し元の処理に戻る。
【０２５７】
このように、評価値が閾値以上である空き資源を検出すれば直ぐに、その空き資源に新規ジョブを割り当てるものである。
【０２５８】
一方、算出された評価値が閾値未満である場合には（ステップＳ５３３：Ｎｏルート）、ジョブ配置処理部３０３０は、評価値を当該空き資源に対応付けてデータ格納部３０１０に格納する（ステップＳ５３７）。そして処理はステップＳ５２３に戻る。
【０２５９】
一方、カウンタ変数ｃｏｕｎｔの値が分担範囲数以上となると（ステップＳ５２３：Ｎｏルート）、ジョブ配置処理部３０３０は、新規ジョブを配置可能な空き資源が検出されたか否かをデータ格納部３０１０に格納されているデータから判断する（ステップＳ５３９）。一度もステップＳ５３１に処理が移行していない場合には、データ格納部３０１０に空き資源に対して評価値が格納されることがないので、空き資源に対応付けて評価値が格納されているか否かを判断する。
【０２６０】
新規ジョブを配置可能な空き資源が存在しない場合には、ジョブ配置処理部３０３０は、割り当て不能を設定する（ステップＳ５４３）。そして、呼び出し元の処理に戻るが、これ以降の処理は行われない。
【０２６１】
一方、新規ジョブを配置可能な空き資源が存在する場合には、ジョブ配置処理部３０３０は、評価値が最良である空き資源を選択する（ステップＳ５４１）。そして処理は呼び出し元の処理に戻る。
【０２６２】
次に、処理時間の見積もり処理の第２の例について図２９を用いて説明する。
【０２６３】
第２の例では、最初に見つかった空き資源を他の探索結果を考慮せずに割り当てる「ファーストフィット」と呼ばれる割り当てポリシーを採用する場合を想定する。
【０２６４】
このような割り当てポリシーでは、割り当ての成功確率も予想し、成功確率が大きい分担範囲に、より多くの処理要素を配分することが意味を有する場合がある。図２８のように、評価値が閾値以上である空き資源を検出すれば直ぐにその空き資源に新規ジョブを割り当てるようなポリシーを採用する場合も同様である。
【０２６５】
そこで、探索制御部３０２０は、空の集合Ｌに対して、分担範囲のリストを設定する（ステップＳ６０１）。そして、探索制御部３０２０は、集合Ｌが空であるか否かを判断する（ステップＳ６０３）。集合Ｌが空であれば、呼び出し元の処理に戻る。
【０２６６】
一方、集合Ｌが空でない場合には、探索制御部３０２０は、変数ａに、集合Ｌにおける先頭の分担範囲を設定する（ステップＳ６０５）。また、探索制御部３０２０は、集合Ｌから変数ａを除去する（ステップＳ６０７）。
【０２６７】
そして、探索制御部３０２０は、分担範囲ａにおける成功確率を、例えばデータ格納部３０１０に格納されている、成功確率を推定するためのデータ及び分担範囲ａのデータを用いて推定する（ステップＳ６０９）。ベイズ推定によって得られた、成功確率を推定するためのデータと、分担範囲ａについての複雑度のデータ及び連結成分の数などとから、成功確率を推定する。
【０２６８】
さらに、探索制御部３０２０は、分担範囲ａにおける探索処理の所要時間（すなわち処理時間）を、例えばデータ格納部３０１０に格納されている推定式のデータ及び当該分担範囲ａのデータに加えて、算出された成功確率を用いて推定する（ステップＳ６１１）。さらに、分担範囲ａについての複雑度のデータ及び含まれる連結成分の数と、成功確率とから、例えばカルマンフィルタによって処理時間を算出し、例えばデータ格納部３０１０に格納する。そして処理はステップＳ６０３に戻る。
【０２６９】
以上のような処理を実施すれば、各分担範囲について、成功確率をも加味した上で処理時間の見積もりが行われる。
【０２７０】
そして、評価処理（ステップＳ４０９）では、図３０に示すような処理が行われる。
【０２７１】
すなわち、マスタスケジューラノード３００のジョブ配置処理部３０３０は、カウンタ変数ｃｏｕｎｔに０を設定する（ステップＳ６２１）。そして、ジョブ配置処理部３０３０は、カウンタ変数ｃｏｕｎｔの値が分担範囲数より小さいか否かを判断する（ステップＳ６２３）。
【０２７２】
カウンタ変数ｃｏｕｎｔの値が分担範囲数より小さい場合には（ステップＳ６２３：Ｙｅｓルート）、ジョブ配置処理部３０３０は、スレーブスケジューラノード３１０からの探索結果を待機し、探索結果のデータを受信すると、例えばデータ格納部３０１０に格納する（ステップＳ６２５）。
【０２７３】
そうすると、ジョブ配置処理部３０３０は、カウンタ変数ｃｏｕｎｔを１インクリメントし（ステップＳ６２７）、受信した探索結果が空き資源検出を示しているか否かを判断する（ステップＳ６２９）。受信した探索結果が空き資源検出を示していない場合には、処理はステップＳ６２３に戻る。
【０２７４】
一方、受信した探索結果が空き資源検出を示している場合には、ジョブ配置処理部３０３０は、この探索結果についての空き資源を選択する（ステップＳ６３１）。そして処理は呼び出し元の処理に戻る。
【０２７５】
一方、カウンタ変数ｃｏｕｎｔの値が分担範囲数以上となると（ステップＳ６２３：Ｎｏルート）、ジョブ配置処理部３０３０は、割り当て不能を設定する（ステップＳ６３３）。そして処理は呼び出し元の処理に戻る。但し、この場合、以降の処理は停止する。
【０２７６】
［Ａｐｐｅｎｄｉｘ］
上では、ジョブを管理するための簡易的なデータ構造を示したが、以下、ｎ次元メッシュ又はトーラスである場合の具体例について説明する。
【０２７７】
図３１に、実行待ちのジョブに関するデータを示す。図３１に示すように、ジョブを特定するジョブＩＤ（識別子）に対して、利用者ＩＤ、ジョブ属性値及び各次元の大きさを関連付けている。各次元の大きさは、実行に要する計算ノードで占められる領域の各次元（第１乃至第Ｎ次元）の大きさである。
【０２７８】
図３２に、実行中のジョブに関するデータであるジョブ制御表を示す。
【０２７９】
本実施の形態に係るジョブ制御表は、ジョブＩＤに対して、利用者ＩＤ、開始予定時刻、終了予定時刻、各次元の最大値、各次元の最小値、及び関連データにアクセスするためのデータを含む。各次元の最大値と各次元の最小値は、実行中の各ジョブが使用しているノード座標の各次元の最大値と最小値である。
【０２８０】
関連データにアクセスするためのデータは、使用時間帯及び各次元についてのハッシュテーブル内次ジョブ、使用時間帯及び各次元についてのハッシュテーブル内前ジョブ、使用時間帯及び各次元についての隣接リスト内起点、使用時間帯及び各次元についての隣接リスト内終点、隣接リスト起点、隣接リスト終点、ジョブについての対岸リスト始点及び終点、及び連結成分制御表へのポインタを含む。
【０２８１】
ハッシュテーブル内次ジョブというのは、各次元での座標の最小値又は最大値をキーとするハッシュ表（図３６（ａ）乃至（ｃ））の「ハッシュバケツ」内の次ジョブへのポインタである。同様に、ハッシュテーブル内前ジョブというのは、各次元での座標の最小値又は最大値をキーとするハッシュ表（図３６（ａ）乃至（ｃ））の「ハッシュバケツ」内の前ジョブへのポインタである。なお、最後のジョブでは空ポインタとなる。
【０２８２】
使用時間帯及び各次元についての隣接リスト内起点は、使用時間帯及び各次元に関して、隣接リストの起点へのポインタである。使用時間帯及び各次元についての隣接リスト内終点は、使用時間帯及び各次元に関して、隣接リストにおける終点へのポインタである。
【０２８３】
また、本具体例では、ジョブについての全体の隣接リストも設けられており、隣接リスト起点については、全体の隣接リストにおける起点へのポインタである。同様に、隣接リスト終点については、全体の隣接リストにおける終点へのポインタである。
【０２８４】
対岸リスト起点及び終点は、ジョブについての対岸リストにおける起点及び終点へのポインタである。連結成分制御表へのポインタは、本ジョブが属する連結成分についての制御表へのポインタである。
【０２８５】
本実施の形態では、図３３に示すように連結成分についての制御表である連結成分制御表をも保持される。
【０２８６】
連結成分制御表は、連結成分ＩＤ、連結成分内の最早開始時間及び最遅終了時間（時間帯）、連結成分内における各次元の最小値及び最大値、使用時間帯及び各次元についての隣接リストにおける起点、使用時間帯及び各次元についての隣接リストにおける終点、隣接リスト起点及び終点、並びに対岸リスト起点及び対岸リスト終点を含む。この他に、連結成分の構成要素についてのジョブ構成リストへのポインタを有する場合もある。
【０２８７】
本具体例では、本連結成分についての全体の隣接リストも設けられており、隣接リスト起点及び終点は、全体の隣接リストにおける起点及び終点へのポインタである。
【０２８８】
対岸リスト起点及び終点は、連結成分についての対岸リストにおける起点及び終点へのポインタである。
【０２８９】
図３４に、ジョブについての対岸リストの１ブロックの一例を示す。対岸リストは、１又は複数のブロックを含む場合があり、対岸リストに含まれる各ジョブについてのジョブ制御表へのポインタ、次のブロックへのポインタ、及び前のブロックへのポインタを含む。このようにすれば対岸リストが大きくなった場合に、複数のブロックで管理できる。
【０２９０】
同様に、図３５に、連結成分についての対岸リストの１ブロックの一例を示す。連結成分についての対岸リストは、１又は複数のブロックを含む場合があり、対岸リストに含まれる各連結成分についての連結成分制御表へのポインタ、次のブロックへのポインタ、及び前のブロックへのポインタを含む。このようにすれば連結成分制御表についても対岸リストが大きくなった場合に、複数のブロックで管理できる。
【０２９１】
なお、ジョブ及び連結成分についての隣接リストについても、これらの構造と同様の構成を有する。
【０２９２】
次に、ハッシュテーブルについて説明する。ハッシュテーブルは、ノード座標空間に割り当てられている実行中ジョブの位置（ノード座標位置）を管理する実行中ジョブ位置情報である。このハッシュテーブルは、探索処理の鍵となる情報である。
【０２９３】
ハッシュテーブルは、ノード座標空間における、実行中ジョブの各次元のノード座標値をキーとする（Ｎ個の）ハッシュの情報である。
【０２９４】
図３６（ａ）、（ｂ）及び（ｃ）はハッシュテーブルを説明するための図である。図３６（ａ）はメッシュを例示する図であり、図３６（ｂ）は図３６（ａ）に示すメッシュの縦座標の次元に関する実行中ジョブのハッシュ表を示し、図３６（ｃ）は図３６（ａ）に示すメッシュの横座標の次元に関する実行中ジョブのハッシュ表を示す。
【０２９５】
ハッシュテーブルは、ノード座標空間に割り当てられている実行中ジョブの位置（ノード座標位置）を、ノード座標空間を構成する次元軸毎に対応させて管理する。
【０２９６】
例えば、図３６（ａ）に示すメッシュのノード座標空間は、横座標方向（横座標の次元）と縦座標方向（縦座標の次元）とを備える。このようなノード座標空間においては、ハッシュテーブルは、横座標の次元に関するハッシュテーブル（図３６（ｃ）参照）と縦座標の次元に関するハッシュテーブル（図３６（ｂ）参照）とを含む。
【０２９７】
そして、ハッシュテーブルには、各ジョブについて、各次元でのノード座標の最小値及び最大値に対応するエントリに、ジョブ制御表内で、そのジョブに対応するエントリへのポインタを格納する。
【０２９８】
図３６（ａ）に示すように、９（横軸）×７（縦軸）のメッシュ座標にjob1乃至job5で示される５つのジョブが割り当てられている。例えば、この図３６（ａ）において、job4の四隅（頂点）の座標（ノード座標）は（１，４），（４，４），（１，６），（４，６）である。従って、このjob4のノード座標の横軸側の最大値は４であり最小値は１である。
【０２９９】
この場合に、図３６（ｃ）に示すように、横座標の次元のハッシュテーブルにおいては、座標値１に対応するエントリと座標値４に対応するエントリとのそれぞれにjob4が関連付けられる。同様に、このjob4のノード座標の縦軸側の最大値は６であり最小値は４であるので、図３６（ｂ）に示すように、縦座標の次元のハッシュテーブルにおいては、座標値４に対応するエントリと座標値６に対応するエントリとのそれぞれにjob4が関連付けられる。
【０３００】
これらの関連付け、すなわちハッシュテーブルへの登録は、具体的には、座標の最小値および最大値をキーにして、対応するジョブのジョブ制御表（図３２）へのポインタが登録される。また、このジョブ制御表へのポインタの登録は、当該ジョブの実行開始時に登録される。
【０３０１】
なお、ハッシュ値の衝突は、「ハッシュバケツ法」で処理する。すなわち、同一キーに対応する構造体をポインタで連結する。キーの衝突はハッシュバケツ法、すなわち、ポインタ格納領域をキューイングする方法で処理する。
【０３０２】
また、上ではスレーブスケジューラノード３１０は、対岸リストを保持するようにしていたが、空き計算ノード２００を探索処理の処理要素として使用している場合、２次以上の近傍との情報共有（例えば、探索が終了した事の通知）により、処理効率が向上する場合もある。例えば「最も早く見つかった割り当て可能な空き資源を割り当てる」ポリシー（すなわちファーストフィット）の場合に「見つかったので他の処理要素での処理を打ち切る」ための通信を、実際に資源を割り当てるコンポーネントへの通知と同時に開始する場合などが該当する。
【０３０３】
以上本発明の実施の形態を説明したが、本発明はこれに限定されるものではない。例えば、上で述べた機能ブロック図は、プログラムモジュール構成とは一致しない場合もある。また、処理フローについても、処理結果が変わらない限り、処理の順番を入れ替えたり、複数ステップの順番を入れ替えても良い。
【０３０４】
また、上で述べたように、スレーブスケジューラノード３１０で実行される処理は、マスタスケジューラノード３００で実行される場合もある。データについても、スレーブスケジューラノード３１０が保持するデータを、マスタスケジューラノード３００においても保持する場合がある。
【０３０５】
また、上の説明では、ジョブについての処理においては、ジョブが特定されると当該ジョブに割り当てられた計算ノードが特定されるようにしているが、ジョブが割り当てられた計算ノード２００についての部分グラフに対応付けてジョブなどのデータが管理されるような場合もある。
【０３０６】
以上述べた本実施の形態をまとめると、以下のようになる。
【０３０７】
本実施の形態の第１の態様に係る情報処理方法は、（Ａ）計算機システムにおける計算資源を表す複数の頂点及び計算資源間のリンクを表す複数の辺を含むグラフにおける、１又は複数の第１のジョブが割り当てられた第１の計算資源についての第１の部分グラフ又は上記１又は複数の第１のジョブに対して、上記グラフにおいてジョブが割り当てられていない計算資源についての頂点を介して第１の部分グラフに接続され且つ第２のジョブが割り当てられた第２の計算資源についての第２の部分グラフ又は第２のジョブについてのデータを管理し、（Ｂ）上記データを用いて、第３のジョブを割り当てるべき第３の計算資源の有無を、第１の部分グラフから判断する処理を含む。
【０３０８】
このように前もって上記のようなデータを維持管理すれば、第３のジョブを割り当てるべき第３の計算資源の有無を判断する処理が高速化される。
【０３０９】
また、上で述べた管理する処理が、（ａ１）第４のジョブが新たに割り当てられた第４の計算資源についての第４の部分グラフについてのデータを受信する場合、又は第５のジョブについて割り当てられ且つ当該第５のジョブの終了によって解放された第５の計算資源についての第５の部分グラフについてのデータを受信する場合、上記データを更新する処理を含むようにしても良い。このような場合には、第２の部分グラフが変化する可能性があるためである。
【０３１０】
さらに、上で述べた更新する処理を、上で述べた判断する処理を行っていない時間帯に実行するようにしても良い。このようにすれば、第３のジョブを割り当てるべき第３の計算資源の有無を判断する処理に影響を与えることなく、上記データの更新を行うことができるようになる。
【０３１１】
本実施の形態の第２の態様に係る情報処理方法は、（Ａ）計算機システムにおける計算資源を表す複数の頂点及び計算資源間のリンクを表す複数の辺を含むグラフにおいて、（ａ１）あるジョブが割り当てられた計算資源についての部分グラフに属する頂点の数に対する部分グラフに隣接するがジョブの割り当てがない計算資源についての頂点の数の割合と、（ａ２）部分グラフに属する頂点の数に対する部分グラフに属する複数の頂点に隣接するがジョブの割り当てがない計算資源についての頂点の数の割合と、（ａ３）部分グラフに属する頂点の数に対する部分グラフに隣接するがジョブの割り当てがない計算資源についての頂点と隣接し且つ部分グラフに属する頂点の数の割合と、（ａ４）部分グラフに属する頂点に対する、一方の頂点が部分グラフに属するが他方の頂点が部分グラフに隣接してさらにジョブの割り当てがない計算資源についての頂点である辺の数の割合と、（ａ５）部分グラフに属する頂点間の辺の数に対する一方の頂点が部分グラフに属するが他方の頂点が部分グラフに隣接してさらにジョブの割り当てがない計算資源についての頂点である辺の数の割合とのうち少なくともいずれかを取得し、（Ｂ）取得された割合に基づき、部分グラフを基準に他のジョブを割り当てるべき計算資源を探索するのに要する負荷に関する指標値を算出する処理を含む。
【０３１２】
このように、計算機システムを表すグラフに対する新たなパラメタ（例えば実施の形態における複雑度）を導入することで、計算資源の探索に要する負荷に関する指標値を適切に算出することができるようになる。
【０３１３】
また、第２の態様に係る情報処理方法は、上記指標値に基づき、部分グラフを基準に他のジョブを割り当てるべき計算資源を探索するための処理要素数を決定する処理をさらに含むようにしても良い。このようにすれば、並列して探索処理を行わせても、処理時間に大きな偏りが生じないようにすることができるようになる。
【０３１４】
さらに、上で述べた算出する処理が、（ｂ１）取得された割合から部分グラフを基準に他のジョブを割り当てるべき計算資源の探索が成功する確率を、予め設定された第１のデータに基づき算出し、（ｂ２）取得された割合と算出された確率とに基づき、予め設定された第２のデータに基づき指標値を算出する処理を含むようにしても良い。例えば確率が高い部分グラフに対してより多くの処理要素を割り当てるようにしても良い。
【０３１５】
また、第２の態様に係る情報処理方法は、上で述べた取得する処理と上で述べた算出する処理とを、複数の部分グラフについて実施する処理をさらに含むようにしても良い。この場合、上で述べた決定する処理が、複数の部分グラフについて算出された複数の指標値に応じて、処理要素数を複数の部分グラフの各々について決定する処理を含むようにしても良い。
【０３１６】
なお、上で述べたような処理をプロセッサ又はコンピュータに実施させるためのプログラムを作成することができ、当該プログラムは、例えばフレキシブル・ディスク、ＣＤ−ＲＯＭなどの光ディスク、光磁気ディスク、半導体メモリ（例えばＲＯＭ）、ハードディスク等のコンピュータ読み取り可能な記憶媒体又は記憶装置に格納される。なお、処理途中のデータについては、ＲＡＭ等の記憶装置に一時保管される。
【０３１７】
以上の実施例を含む実施形態に関し、さらに以下の付記を開示する。
【０３１８】
（付記１）
計算機システムを管理するジョブ管理装置に、
前記計算機システムにおける計算資源を表す複数の頂点及び前記計算資源間のリンクを表す複数の辺を含むグラフにおける、１又は複数の第１のジョブが割り当てられた第１の計算資源についての第１の部分グラフ又は前記１又は複数の第１のジョブに対して、前記グラフにおいてジョブが割り当てられていない計算資源についての頂点を介して前記第１の部分グラフに接続され且つ第２のジョブが割り当てられた第２の計算資源についての第２の部分グラフ又は前記第２のジョブについてのデータを管理させ、
前記データを用いて、第３のジョブを割り当てるべき第３の計算資源の有無を、前記第１の部分グラフから判断させる、
ジョブ管理プログラム。
【０３１９】
（付記２）
前記ジョブ管理プログラムにおいて、
前記管理させる処理が、
第４のジョブが新たに割り当てられた第４の計算資源についての第４の部分グラフについてのデータを受信する場合、又は第５のジョブについて割り当てられ且つ当該第５のジョブの終了によって解放された第５の計算資源についての第５の部分グラフについてのデータを受信する場合、前記データを更新させる処理
を含む付記１記載のジョブ管理プログラム。
【０３２０】
（付記３）
前記ジョブ管理プログラムにおいて、
前記ジョブ管理装置に、
前記更新させる処理を、前記判断させる処理を行っていない時間帯に実行させる
付記２記載のジョブ管理プログラム。
【０３２１】
（付記４）
計算機システムを管理するジョブ管理装置に、
前記計算機システムにおける計算資源を表す複数の頂点及び前記計算資源間のリンクを表す複数の辺を含むグラフにおいて、あるジョブが割り当てられた計算資源についての部分グラフに属する頂点の数に対する前記部分グラフに隣接するがジョブの割り当てがない計算資源についての頂点の数の割合と、前記部分グラフに属する頂点の数に対する前記部分グラフに属する複数の頂点に隣接するがジョブの割り当てがない計算資源についての頂点の数の割合と、前記部分グラフに属する頂点の数に対する前記部分グラフに隣接するがジョブの割り当てがない計算資源についての頂点と隣接し且つ前記部分グラフに属する頂点の数の割合と、前記部分グラフに属する頂点に対する、一方の頂点が前記部分グラフに属するが他方の頂点が前記部分グラフに隣接してさらにジョブの割り当てがない計算資源についての頂点である辺の数の割合と、前記部分グラフに属する頂点間の辺の数に対する一方の頂点が前記部分グラフに属するが他方の頂点が部分グラフに隣接してさらにジョブの割り当てがない計算資源についての頂点である辺の数の割合とのうち少なくともいずれかを取得させ、
取得された前記割合に基づき、前記部分グラフを基準に他のジョブを割り当てるべき計算資源を探索するのに要する負荷に関する指標値を算出させる
ジョブ管理プログラム。
【０３２２】
（付記５）
前記ジョブ管理プログラムはさらに、
前記ジョブ管理装置に、
前記指標値に基づき、前記部分グラフを基準に他のジョブを割り当てるべき計算資源を探索するための処理要素数を決定させる
付記４記載のジョブ管理プログラム。
【０３２３】
（付記６）
前記ジョブ管理プログラムにおいて、
前記算出させる処理が、
取得された前記割合から前記部分グラフを基準に他のジョブを割り当てるべき計算資源の探索が成功する確率を、予め設定された第１のデータに基づき算出させ、
取得された前記割合と算出された前記確率とに基づき、予め設定された第２のデータに基づき前記指標値を算出させる
処理を含む付記４又は５記載のジョブ管理プログラム。
【０３２４】
（付記７）
前記ジョブ管理プログラムはさらに、
前記ジョブ管理装置に、
前記取得させる処理と前記算出させる処理とを、複数の前記部分グラフについて実施させ、
前記決定させる処理は、
複数の前記部分グラフについて算出された複数の指標値に応じて、前記処理要素数を複数の前記部分グラフの各々について決定させる
処理を含む付記５記載のジョブ管理プログラム。
【０３２５】
（付記８）
計算機システムを管理するジョブ管理装置が、
前記計算機システムにおける計算資源を表す複数の頂点及び前記計算資源間のリンクを表す複数の辺を含むグラフにおける、１又は複数の第１のジョブが割り当てられた第１の計算資源についての第１の部分グラフ又は前記１又は複数の第１のジョブに対して、前記グラフにおいてジョブが割り当てられていない計算資源についての頂点を介して前記第１の部分グラフに接続され且つ第２のジョブが割り当てられた第２の計算資源についての第２の部分グラフ又は前記第２のジョブについてのデータを管理し、
前記データを用いて、第３のジョブを割り当てるべき第３の計算資源の有無を、前記第１の部分グラフから判断する
ジョブ管理方法。
【０３２６】
（付記９）
計算機システムを管理するジョブ管理装置が、
前記計算機システムにおける計算資源を表す複数の頂点及び前記計算資源間のリンクを表す複数の辺を含むグラフにおいて、あるジョブが割り当てられた計算資源についての部分グラフに属する頂点の数に対する前記部分グラフに隣接するがジョブの割り当てがない計算資源についての頂点の数の割合と、前記部分グラフに属する頂点の数に対する前記部分グラフに属する複数の頂点に隣接するがジョブの割り当てがない計算資源についての頂点の数の割合と、前記部分グラフに属する頂点の数に対する前記部分グラフに隣接するがジョブの割り当てがない計算資源についての頂点と隣接し且つ前記部分グラフに属する頂点の数の割合と、前記部分グラフに属する頂点に対する、一方の頂点が前記部分グラフに属するが他方の頂点が前記部分グラフに隣接してさらにジョブの割り当てがない計算資源についての頂点である辺の数の割合と、前記部分グラフに属する頂点間の辺の数に対する一方の頂点が前記部分グラフに属するが他方の頂点が部分グラフに隣接してさらにジョブの割り当てがない計算資源についての頂点である辺の数の割合とのうち少なくともいずれかを取得し、
取得された前記割合に基づき、前記部分グラフを基準に他のジョブを割り当てるべき計算資源を探索するのに要する負荷に関する指標値を算出する
ジョブ管理方法。
【０３２７】
（付記１０）
計算機システムを管理するジョブ管理装置において、
前記計算機システムにおける計算資源を表す複数の頂点及び前記計算資源間のリンクを表す複数の辺を含むグラフにおける、１又は複数の第１のジョブが割り当てられた第１の計算資源についての第１の部分グラフ又は前記１又は複数の第１のジョブに対して、前記グラフにおいてジョブが割り当てられていない計算資源についての頂点を介して前記第１の部分グラフに接続され且つ第２のジョブが割り当てられた第２の計算資源についての第２の部分グラフ又は前記第２のジョブについてのデータを管理する管理部と、
前記データを用いて、第３のジョブを割り当てるべき第３の計算資源の有無を、前記第１の部分グラフから判断する判断部と、
を有するジョブ管理装置。
【０３２８】
（付記１１）
計算機システムを管理するジョブ管理装置において、
前記計算機システムにおける計算資源を表す複数の頂点及び前記計算資源間のリンクを表す複数の辺を含むグラフにおいて、あるジョブが割り当てられた計算資源についての部分グラフに属する頂点の数に対する前記部分グラフに隣接するがジョブの割り当てがない計算資源についての頂点の数の割合と、前記部分グラフに属する頂点の数に対する前記部分グラフに属する複数の頂点に隣接するがジョブの割り当てがない計算資源についての頂点の数の割合と、前記部分グラフに属する頂点の数に対する前記部分グラフに隣接するがジョブの割り当てがない計算資源についての頂点と隣接し且つ前記部分グラフに属する頂点の数の割合と、前記部分グラフに属する頂点に対する、一方の頂点が前記部分グラフに属するが他方の頂点が前記部分グラフに隣接してさらにジョブの割り当てがない計算資源についての頂点である辺の数の割合と、前記部分グラフに属する頂点間の辺の数に対する一方の頂点が前記部分グラフに属するが他方の頂点が部分グラフに隣接してさらにジョブの割り当てがない計算資源についての頂点である辺の数の割合とのうち少なくともいずれかを取得する取得部と、
取得された前記割合に基づき、前記部分グラフを基準に他のジョブを割り当てるべき計算資源を探索するのに要する負荷に関する指標値を算出する算出部と、
を有するジョブ管理装置。
【符号の説明】
【０３２９】
３００  マスタスケジューラノード
３０１０  データ格納部
３０２０  探索制御部
３０３０  ジョブ配置処理部
３０４０  データ管理部
３１０  スレーブスケジューラノード
３１１０  データ格納部
３１２０  探索処理部
３１３０  データ管理部
【図１】
0006413789.tif 000002
【図２】
0006413789.tif 000003
【図３】
0006413789.tif 000004
【図４】
0006413789.tif 000005
【図５】
0006413789.tif 000006
【図６】
0006413789.tif 000007
【図７】
0006413789.tif 000008
【図８】
0006413789.tif 000009
【図９】
0006413789.tif 000010
【図１０】
0006413789.tif 000011
【図１１】
0006413789.tif 000012
【図１２】
0006413789.tif 000013
【図１３Ａ】
0006413789.tif 000014
【図１３Ｂ】
0006413789.tif 000015
【図１４】
0006413789.tif 000016
【図１５】
0006413789.tif 000017
【図１６】
0006413789.tif 000018
【図１７】
0006413789.tif 000019
【図１８】
0006413789.tif 000020
【図１９】
0006413789.tif 000021
【図２０】
0006413789.tif 000022
【図２１】
0006413789.tif 000023
【図２２】
0006413789.tif 000024
【図２３】
0006413789.tif 000025
【図２４】
0006413789.tif 000026
【図２５】
0006413789.tif 000027
【図２６】
0006413789.tif 000028
【図２７】
0006413789.tif 000029
【図２８】
0006413789.tif 000030
【図２９】
0006413789.tif 000031
【図３０】
0006413789.tif 000032
【図３１】
0006413789.tif 000033
【図３２】
0006413789.tif 000034
【図３３】
0006413789.tif 000035
【図３４】
0006413789.tif 000036
【図３５】
0006413789.tif 000037
【図３６】
0006413789.tif 000038