ジョブ管理システム及びジョブ管理方法
【課題】複数のノードを共有するクラスタシステムの使用率を向上させるジョブ管理方法等を提供する。
【解決手段】投入されたジョブを複数のノードから選択し、且つ、時間に応じて割り当てて管理するスケジューラマップから、アサイン対象ジョブが要求するリソースを満たす未使用空間を検索する段階と、検索した未使用空間に基づいて、ジョブを実行開始する時刻を決定する段階と、前記時刻にジョブを割り当て可能な少なくとも１以上の候補ノードから、該各候補ノードの前方ジョブの空き時間長、前方ジョブの使用ノード数、及び前方ジョブの最大ノード間距離の情報を備えるノードリストを作成する段階と、アサイン対象ジョブの実行予定ノードを選択するためのポリシーによって、ノードリストをアサイン対象ジョブの実行予定ノードを選択する優先度順にソートする段階と、を備えるジョブ管理方法。
【解決手段】投入されたジョブを複数のノードから選択し、且つ、時間に応じて割り当てて管理するスケジューラマップから、アサイン対象ジョブが要求するリソースを満たす未使用空間を検索する段階と、検索した未使用空間に基づいて、ジョブを実行開始する時刻を決定する段階と、前記時刻にジョブを割り当て可能な少なくとも１以上の候補ノードから、該各候補ノードの前方ジョブの空き時間長、前方ジョブの使用ノード数、及び前方ジョブの最大ノード間距離の情報を備えるノードリストを作成する段階と、アサイン対象ジョブの実行予定ノードを選択するためのポリシーによって、ノードリストをアサイン対象ジョブの実行予定ノードを選択する優先度順にソートする段階と、を備えるジョブ管理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ジョブ管理システム及びジョブ管理方法に関し、特に、バックフィルスケジューラを使用するジョブ管理システム及びそのジョブ管理方法に関する。
【背景技術】
【０００２】
従来、ＨＰＣ（Ｈｉｇｈ Ｐｅｒｆｏｒｍａｎｃｅ Ｃｏｍｐｕｔｉｎｇ）分野を中心に利用されるバッチ処理システムにおいて、多数のノードを接続したクラスタシステム、及びバックフィル型スケジューリングを用いるジョブスケジューラ（以降、「バックフィルスケジューラ」と称する）が利用されている。バックフィルスケジューラとは、クラスタシステムに接続されているノード等のリソースを現在から未来に渡って管理し、ジョブに対してリソースを占有して使用可能な時間枠を割り当てることを特徴とした、ジョブ管理システムのジョブスケジューリング機能である。
【０００３】
ここで、バックフィルスケジューラの特徴であるスケジューラマップについて、図１を参照して説明する。スケジューラマップとは、ジョブが使用するノードと実行する時刻についての情報とを保持するマップである。投入されたジョブは、図１（ａ）に示すように、まず、キューに繋がれ、優先度が設定される。バックフィルスケジューラは、図１（ｂ）に示すように、キュー内の優先順位の高いジョブからスケジューラマップ上の未使用空間にジョブを配置し（以降、「アサイン」と称する）、時間経過とともに予定されたジョブを実行する。
【０００４】
図１（ｂ）に示すスケジューラマップは、ジョブＡ〜Ｅがアサインされた状態を示す。この時の未使用空間は、Ｎｏｄｅ０の斜線部（１），（３）、及びＮｏｄｅ１の斜線部（２）である。バックフィルスケジューラは、ユーザが指定したジョブＦの使用ノード数や予定実行時間等の情報を元に、ジョブＦを実行するのに十分な空きがある未使用空間を探す。この場合は、未使用空間である、Ｎｏｄｅ０の斜線部（３）とＮｏｄｅ１の斜線部（２）にジョブＦをアサインする。
【０００５】
初期のクラスタシステムにおけるジョブ管理システムでは、ジョブを規模（使用ノード数）ごとにクラス分けし、クラスに対応するキューを設定し、それぞれのキューには、規模に応じて専用のノードを割り当てる。よって、利用者がジョブの規模にあったキューにジョブを投入すると、バックフィルスケジューラは、投入されたジョブをそのキューに割り当てられたクラス用のノードに配置して実行する。このような運用では、投入されるジョブの規模に偏りがあると、一部のキューに割り当てられたノードばかりが使用され、残りのノードは未使用となり、クラスタシステム全体の使用率が低くなってしまうという問題があった。また、キューごとにノード数が固定であるため、運用状況に応じてノードの割り当て数を変更することが困難であった。
【０００６】
そのため、上記の問題を解決するために、現在、全ノードを共有する方式が取られるようになった。この方式では、キューはジョブの規模（使用ノード数）ごとに設定されていても、ノードはキュー間で共有しているため、空いているノードを柔軟に選択できる。バックフィルスケジューラは、ジョブが要求するリソース条件に対して最適な未使用空間を必要ノード数選択し、ジョブをアサインする。ただし、クラスタシステムの使用率を高くするためには、なるべく未使用空間ができないようにスケジューリングすることが求められる。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００５−３１０１３９号公報
【特許文献２】特開２００９−０２６６３６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかし、全ノードを共有する方式では、下記課題を有している。
【０００９】
すなわち、一つ目の課題は、スケジューラマップ上の未使用空間の分断（断片化）である。従来の全ノードを共有する方式は、規模の不均一なジョブを、共有されたノードにアサインするため、リソースの空き状況のみを基準にして未使用空間を割り当てるものであり、この方式では未使用空間を分断するようなアサインをしてしまう可能性がある。例えば、ＨＰＣ分野では実行時間が長時間に及ぶジョブが多い傾向にあるため、時間が短い未使用空間は使われないまま残り、クラスタシステム全体の使用率低下を招く原因になる（図２参照）。
【００１０】
二つ目の課題は、先行ジョブの終了時刻不均一による後続ジョブの実行待ちである。ユーザが宣言するジョブの予定実行時間は長めに設定されていることが多く、ジョブが実行時間より早く終了することがある。このような時、通常は後続のジョブを予定実行開始時刻から早めて実行する。しかし、複数のノードで実行する場合、使用予定のノードが別のジョブによって使用されていると該当ノードが空くまで後続ジョブは実行を待たされることになる。そのため、ジョブが早期に終了したノードは、その間、アイドリング状態となる。ＨＰＣ分野では、多数のノードを使用するジョブが多いため、上記のような状態はクラスタシステム全体の使用率低下を招く原因になる（図３参照）。
【００１１】
従来技術を参照すると、例えば、特許文献１では、メッシュ構造に相互接続されたクラスタシステムにおいて、クラスタの接続状況を考慮してジョブにノードを割り当てる方法が開示されている。特許文献１に記載の発明は、ジョブ投入時点の未使用ノードのネットワーク接続状態等を考慮して、ジョブの規模に合うノード数を自動的に割り当てることを可能としている。しかし、ノード割り当ての基準は、ノード自体の性能（演算速度、信頼度等）であり、時系列でジョブ間の関係を考慮したものではないため、特許文献１に記載の発明では、前述した課題を解決することはできない。
【００１２】
また、特許文献２では、プログラム構造やＩ／Ｏによるジョブの実行待ち、ユーザの使用ＣＰＵ数の過大申告によるＣＰＵの遊休による無駄を解消するためのスケジューリング方法が開示されている。特許文献２に記載の発明は、スケジューラマップ上の先行ジョブが占有するＣＰＵを使っていない間に限り、後続ジョブが借りて実行することを可能としている。しかし、前述した課題は単一ノードの使用状況に限らず発生するため、特許文献２に記載の発明では、前述した課題を解決することはできない。
【００１３】
さらに、類似の技術として、時間と空間について制御を行うスケジューリング方式の「時空間分割スケジューリング」が知られている。これは、共有するノードの負荷状況を考慮して各ノードに複数のジョブを割当て、ラウンドロビンによる時分割でノードに割り当てたジョブを実行する方式である。しかし、バックフィルスケジューラとは設計思想がそもそも異なるため、クラスタシステムのジョブ管理には使用できない。
【００１４】
そこで、本発明は、かかる事情に鑑み、バックフィルスケジューラにおいて、未使用空間の分断と先行ジョブの予定終了時刻の不均一によるジョブの実行待ちを回避し、クラスタシステムの使用率を向上させることができる新しいジョブ管理システム及びジョブ管理方法を提供することを目的とする。
【課題を解決するための手段】
【００１５】
本発明によるジョブ管理システムは、多数のノードを共有するクラスタシステムにおいて、バックフィルスケジューラを使用するジョブ管理システムであって、投入されたジョブを前記多数のノードから選択し、且つ、時間に応じて割り当てて管理するスケジューラマップから、アサイン対象ジョブが要求するリソースを満たす未使用空間を検索する検索手段と、前記検索した未使用空間に基づいて、ジョブを実行開始する時刻を決定する決定手段と、前記時刻にジョブを割り当て可能な少なくとも１以上の候補ノードから、該各候補ノードの前方ジョブの空き時間長、前方ジョブの使用ノード数、及び前方ジョブの最大ノード間距離の情報を備えるノードリストを作成する作成手段と、前記アサイン対象ジョブの実行予定ノードを選択するためのポリシーによって、前記ノードリストを前記アサイン対象ジョブの実行予定ノードを選択する優先度順にソートするノード優先順位決定手段と、を備える。
【００１６】
本発明によるジョブ管理方法は、多数のノードを共有するクラスタシステムにおいて、バックフィルスケジューラを使用するジョブ管理方法であって、投入されたジョブを前記多数のノードから選択し、且つ、時間に応じて割り当てて管理するスケジューラマップから、アサイン対象ジョブが要求するリソースを満たす未使用空間を検索する段階と、前記検索した未使用空間に基づいて、ジョブを実行開始する時刻を決定する段階と、前記時刻にジョブを割り当て可能な少なくとも１以上の候補ノードから、該各候補ノードの前方ジョブの空き時間長、前方ジョブの使用ノード数、及び前方ジョブの最大ノード間距離の情報を備えるノードリストを作成する段階と、前記アサイン対象ジョブの実行予定ノードを選択するためのポリシーによって、前記ノードリストを前記アサイン対象ジョブの実行予定ノードを選択する優先度順にソートする段階と、を備える。
【発明の効果】
【００１７】
以上のように構成された本発明のジョブ管理システム等によれば、バックフィルスケジューラ上において小さな未使用空間が減少し、マルチノードジョブを含むより多くのジョブがアサインされやすくなるため、クラスタシステムの使用率を向上させることができる。
【図面の簡単な説明】
【００１８】
【図１】スケジューラマップについて説明するための図である。
【図２】従来のバックフィルスケジューラマップを示す図である。
【図３】従来のバックフィルスケジューラマップを示す図である。
【図４】本実施形態のジョブ管理システムの概略構成を示す図である。
【図５】本実施形態の前方検査ポリシーを適用した場合のスケジューラマップを示す図である。
【図６】本実施形態のジョブ管理方法の処理内容を示すフローチャートである。
【図７】本実施形態のジョブ管理方法の処理内容を示すフローチャートである。
【図８】本実施形態のジョブ管理方法を説明するためのノードリスト、スケジューラマップ、及びネットワーク構成を示す図である。
【図９】本実施形態のジョブ管理方法を用いた例を説明するためのノードリスト、スケジューラマップ、及びネットワーク構成を示す図である。
【発明を実施するための形態】
【００１９】
本発明は、バックフィルスケジューラにおいて、ジョブ投入時にジョブをアサインする空間を選択するためのポリシーを提供する。このポリシーにより、従来技術の課題である未使用空間の分断と先行ジョブの予定終了時刻の不均一によるノードの実行待ち（遊休時間発生）を回避し、クラスタシステムの使用率を向上させるものである。
【００２０】
以下、本発明を実施するための好適な実施形態を、図面を参照しながら説明する。図４は、本実施形態におけるジョブ管理を行うクラスタシステム（ジョブ管理システム）１の概略構成を示す。
【００２１】
ジョブ管理システム１は、多数のノードを共有するクラスタシステムにおける、バックフィルスケジューラを使用するものであり、図４に示すように、ジョブアサイン部１０と情報管理部２０とを含んで構成される。バックフィルスケジューラは、投入されたジョブ（以下、「アサイン対象ジョブ」と称する）が要求するリソースを満たす未使用空間をスケジューラマップ上から検索し、最も早く実行を開始できる空間を割り当てる機能を有する。この最も早く実行を開始できる時刻を、本実施形態では、予定実行開始時刻という。予定実行開始時刻からジョブを割り当てることができる未使用空間は、１通り以上のノードの組み合わせになる可能性があるため、候補の中から使用するノードを選択するために、後述するポリシーを適用する。なお、ジョブ管理システム１は、ハードウェアとして、例えば、ＣＰＵ、ＣＰＵにバス結合されたＲＯＭ、ＲＡＭ、記憶部、入力部、表示部、および入出力インタフェースなど、通常のコンピュータ装置と同様のハードウェアを備えることができる。また、物理的には、専用化したシステム、あるいは汎用の情報処理装置のいずれであってもよい。
【００２２】
ジョブアサイン部１０は、投入されたジョブを現在から未来に渡るノード空間にアサインするものであり、空き情報検索手段１１、予定実行開始時刻決定手段１２、及び実行予定ノード選択部１３を含み、実行予定ノード選択部１３は、更に、ノード優先順位決定手段１４及びノード選択手段１５を含む。
【００２３】
空き情報検索手段（検索手段）１１は、アサイン対象ジョブが実行可能なリソースを備える未使用空間を検索する機能を有する。
【００２４】
予定実行開始時刻決定手段（決定手段）１２は、検索によって得られた未使用空間情報に基づいて、アサイン対象ジョブを最も早く実行開始できる時刻を決定する機能を有する。
【００２５】
実行予定ノード選択部１３は、上記実行開始できる時刻にジョブを割り当て可能な少なくとも１以上の候補ノードから、該各候補ノードの前方ジョブの空き時間長、前方ジョブの使用ノード数、及び前方ジョブの最大ノード間距離の情報を備えるノードリストを作成する作成手段として機能する。また、実行予定ノード選択部１３は、ノード優先順位決定手段１４によってノードに優先順位をつけ、ノード選択手段１５によって優先順位に従い、使用するノードを決定する。
【００２６】
ノード優先順位決定手段１４は、１つ以上のポリシーを有しており、本実施形態の前方検査ポリシー１６は、そのうちの一つである。なお、前方検査ポリシー１６については、後述する。
【００２７】
情報管理部２０は、ジョブやクラスタシステムに関する情報を管理するものであり、情報更新手段２１、ジョブ情報（データベース）２２、及びノードの構成を保持するトポロジ情報（データベース）２３を含む。
【００２８】
情報更新手段２１は、アサインが確定したジョブの情報をジョブ情報２２に格納する。
【００２９】
ジョブ情報２２は、アサイン済みのジョブに関する情報を保持するものであり、トポロジ情報２３は、ノードの構成を保持するものである。ここで、本実施形態では、前方ジョブの最大ノード間距離のコストを「ルータを経由する回数」と定義する。すなわち、トポロジ情報２３は、コストを算出するため、ノードの構成が保持される。
【００３０】
ここで、本実施形態の前方検査ポリシー１６について説明する。前方検査ポリシー１６は、まず、前方空き時間長が昇順になるようにソートする。次に、同じ前方空き時間長を持つノードごとに、アサイン対象ジョブの使用ノード数を基準に、「前方ジョブの使用ノード数とノード数が同一」、「前方ジョブの使用ノード数がアサイン対象ジョブの使用ノード数よりも多く、数が近い」、「前方ジョブの使用ノード数がアサイン対象ジョブの使用ノード数よりも少なく、数が近い」という順に未使用空間情報をソートする。最後に、前方ジョブの使用ノード数が同じノードごとに、最大ノード間距離を昇順に未使用空間情報をソートする。このリストの上位から、アサイン対象ジョブが使用するノード数分、ノードを選択する。この操作により、前方ジョブとの空き時間が少なく、使用ノード数がアサイン対象ジョブと同じか、より多いジョブに割り当てられていて、ノード間の距離も近いノードを選ぶことが可能になる。すなわち、前方ジョブとの空き時間が少ないということは、長い未使用空間を中央で分断していないということであり、また、使用ノード数が同じということは前方ジョブが早期終了したときに後続ジョブの予定実行開始時刻を繰り上げて実行ができるということである。ノード間距離が近いノードを優先して選択することで、通信による待ち時間を減らし、より早くジョブの実行を終えることができる。
【００３１】
図２のスケジューラマップのジョブを、前方検査ポリシー１６を使用してアサインした場合のスケジューラマップを図５に示す。ジョブＣがジョブＡのノードにアサインされ、ジョブＧが未使用空間を分断しないなどの改善を得ることができる。その結果、図２に示す場合では（前方検査ポリシー不適用）、ジョブＨはジョブＦの後ろにアサインされていたが、図５に示す場合では（前方検査ポリシー適用）、ジョブＨはジョブＦの前にアサインすることが可能となる。
【００３２】
ここで、ノード障害時の対応としては、アサインをキャンセルされたジョブ（以下、「被障害ジョブ」と称する）を元々の予定実行開始時刻近くの未使用空間に再割り当てする運用方法がある。しかし、本実施形態の前方検査ポリシーを使用すれば、スケジューラマップの前方が隙間無く埋められているために、被障害ジョブを再割当てすることが難しくなる。そのため、なるべく早い時刻に再割り当て可能なように、ノード障害時用の優先度を設定することもできる。具体的には、被障害ジョブであることがわかるように識別子を用意し、被障害ジョブの優先度を新たに投入されたジョブよりも高くすることで、被障害ジョブを、未割り当てのジョブの中で最も早く実行開始できるようにしてもよい。
【００３３】
次に、図４，図６〜図８を参照して、本実施形態の動作処理について詳細に説明する。なお、以下では、図４に示すジョブアサイン部１０と情報管理部２０とがクラスタシステムに１つずつあり、該クラスタシステムのジョブ管理を行うものとする。
【００３４】
まず、ジョブアサイン部１０の動作処理を、図６に示すフローチャートを参照しながら説明する。
【００３５】
空き情報検索手段１１は、各ノードについて、ユーザが指定した予定実行時間以上の空きがあり、且つ、最も早く実行可能な未使用空間を検索する（ステップＳ１０１）。ユーザは、ジョブを投入する際に、使用するノード数やメモリ量、予定実行時間を指定する。
【００３６】
未使用空間があるか否かを判定し（ステップＳ１０２）、未使用空間がないと判定した場合（ステップＳ１０２：Ｎｏ）、処理を終了する。投入されたジョブは次回の未使用空間検索が行われるまで待ち状態になる。
【００３７】
一方、未使用空間があると判定した場合（ステップＳ１０２：Ｙｅｓ）、予定実行開始時刻決定手段１２は、使用するノード数や予定実行時間などの条件を満たし、且つ、最も早くジョブを実行開始できる時刻を予定実行開始時刻として決定する（ステップＳ１０３）。
【００３８】
実行予定ノード選択部１３は、予定実行開始時刻にジョブを割り当てることができるノードについて、ジョブ情報２２とトポロジ情報２３を参照して、「前方空き時間長、前方ジョブのノード数、前方ジョブの最大ノード間距離」等の情報を備えたノードリストを作成する（ステップＳ１０４）。
【００３９】
ノード優先順位決定手段１４は、ユーザが指定した使用ノード数以上に、該当するノードがあった場合、実行予定ノードを選択するためのポリシー適用と判定し（ステップＳ１０５：Ｙｅｓ）、使用するノードを選択するために１つ以上のポリシーを適用する（ステップＳ１０６）。
【００４０】
ノード選択手段１５は、適用したポリシーによって優先度順にソートされたノードリストを元に、ユーザによって指定された使用ノード数分を選択し、ジョブをアサインする（ステップＳ１０７）。
【００４１】
情報更新手段２１は、アサインしたジョブについて、情報管理部２０のジョブ情報２２を更新する（ステップＳ１０８）。
【００４２】
一方、ポリシー適用と判定しない場合（ステップＳ１０５：Ｎｏ）、ノード選択手段１５は、検索した空き情報に基づいて実行予定のノードを選択し（ステップＳ１０９）、情報更新手段２１は、実行予定時間と実行予定のノードを更新する（ステップＳ１０８）。
【００４３】
以上により、ジョブアサイン部１０の動作処理を終了する。
【００４４】
次に、図７及び図８を参照して、本実施形態における、２ノードを使用するジョブＸを割り当てるときの前方検査ポリシー１６の動作説明をする。なお、以下では、３台ずつのノードを接続したクラスタをさらに上位で接続した計６台からなる構成を想定する場合を例にとって説明する。
【００４５】
ここで、図８に示すネットワーク構成は、ノード間の接続関係を示し、現在時刻で処理しているジョブＡ，Ｂ，Ｃ，Ｄを示す。また、図８のスケジューラマップは、ジョブ管理システムのアサイン状況を示す。さらに、図８の表１〜表３は、ジョブアサイン部１０が作成したノードリストに対して、前方検査ポリシー１６を適用していく過程を示すものである。
【００４６】
図７に示すように、まず、前方検査ポリシー１６は、各ノードにおいて前方空き時間長の順序に従い、ノードリストをソートする（ステップＳ２０１）。図８に示す場合においては、ソートした結果、表１に示すノードリストから、表２に示すノードリストになる。
【００４７】
次に、前方検査ポリシー１６は、同じ前方空き時間長のノードごとに、前方のジョブが使用するノード数についてソートする（ステップＳ２０２）。具体的には、ソートの順番は、アサイン対象ジョブが使用するノード数を基準に、前方ジョブの使用ノード数が「ノード数が同一、より多いが数が近い、より少ないが数が近い」の順序である。図８に示す場合においては、前方空き時間長が「０」のノードを使用するジョブは全て２つのノードを使用するため、ソートした結果は変わらない。
【００４８】
次いで、前方検査ポリシー１６は、同じ前方空き時間長、使用ノード数を持つノードごとに、前方ジョブが使用するノード群の最大ノード間距離順になるようにソートする（ステップＳ２０３）。図８に示すように、想定するクラスタシステムにおいて、ジョブＢが使用するノードは、同じクラスタに接続されているため、最大ノード間距離は０、ジョブＡの最大ノード間距離は２となる。したがって、ソートした結果、表２に示すノードリストから、表３に示すノードリストになる。
【００４９】
ジョブアサイン部１０は、他に適用するポリシーが登録されていなければ、上記ソートした結果（図８に示す表３）に従い、ジョブＸがＮｏｄｅ３とＮｏｄｅ４に割り当てられる。
【００５０】
なお、アサイン後に使用予定のノードが障害のため停止した場合は、障害ノードにアサインされていたジョブをすべて解除し、再度ジョブアサインを行うことができる。また、解除時に、各ジョブ情報の被障害識別子に障害にあったことを記録することで、再アサイン時に障害発生後に投入されたジョブよりも優先的に未使用空間を割り当てることもできる。
【００５１】
以上のような本実施形態のバックフィルスケジューラを使用するジョブ管理方法では、以下の効果を奏する。
【００５２】
第１の効果は、クラスタシステムの使用率を向上させることである。その理由は、小さな未使用空間が減少し、マルチノードジョブを含む、より多くのジョブがアサインされやすくなるためであり、且つ、実行中ジョブが予定より早期に終了した場合に直後にアサインされているジョブが即時に実行され、システムのアイドリング時間を減少させることができるためである。
【００５３】
第２の効果は、ジョブのターンアラウンドタイム（ＴＡＴ）を短縮できることである。その理由は、大きい未使用空間にジョブがアサインされやすくなることでジョブが早期に実行されることや、ノード間距離が近いノードを使用することで通信時間を抑えることが、ＴＡＴの短縮に繋がるためである。
【００５４】
第３の効果は、ジョブの投入数が少ない場合にノードの省電力運転をしやすくなることである。その理由は、ノードの未使用時間を分断しないようにジョブをアサインするため、未使用時間が長時間になりやすく、その間、電源を切るなどの運用が可能になる。通常、起動・終了処理はその処理時間が長くかかるため、未使用時間が短く頻繁にジョブを実行するような場合には、電源を切ることは出来ないからである。
【００５５】
＜他の実施形態＞
【００５６】
以下、上述の本実施形態で示した前方検査ポリシー１６の処理において、前方ジョブが使用するノード群の最大ノード間距離を、ノードの電力供給経路に置き換えた場合を例にとって説明する。この場合、優先する電力供給の経路を使用するノードを使うことになるため、アサインされているジョブが少ない場合は、同じ電力供給の経路（配電盤等）を使うノードをまとめて電源を切ることが可能になり、省電力を優先する運用に使用できる。
【００５７】
図９は、ノード０〜２が繋がる経路（配電盤１）の優先度が高い場合のジョブ投入を示した図である。ノードリストを前方空き時間長、前方ジョブのノード数、電力供給経路の優先順でソートした結果、ジョブＸはＮｏｄｅ１，２にアサインされる。Ｎｏｄｅ３〜５は未使用になった区間であるため、電源を切ることができる。
【００５８】
＜変形例＞
以上のように本発明の好適な実施形態について説明したが、本発明は、以上の実施形態に限定されるべきものではなく、特許請求の範囲に表現された思想および範囲を逸脱することなく、種々の変形、追加、および省略が当業者によって可能である。
【００５９】
例えば、上記各実施形態では、ジョブアサイン部１０及び情報管理部２０において、それぞれの処理機能を有する各手段等が備えられている構成を説明したが、本発明はこれに限られず、例えば、各手段が通信可能に接続されたネットワーク上に又は他の装置に備えて構成することもできる。
【００６０】
さらに、上記各実施形態では、ジョブアサイン部１０及び情報管理部２０には、用途に応じた各手段がそれぞれ備えられているが、これら各手段は、そのいくつかを一纏めにして構成されていてもよいし、一つの部をさらに複数の部に分割して構成されていてもよい。
【００６１】
上記の実施形態の一部または全部は、以下の付記のようにも記載されうるが、以下には限られない。
【００６２】
（付記１）多数のノードを共有するクラスタシステムにおいて、バックフィルスケジューラを使用するジョブ管理方法であって、投入されたジョブを前記多数のノードから選択し、且つ、時間に応じて割り当てて管理するスケジューラマップから、アサイン対象ジョブが要求するリソースを満たす未使用空間を検索する段階と、前記検索した未使用空間に基づいて、ジョブを実行開始する時刻を決定する段階と、前記時刻にジョブを割り当て可能な少なくとも１以上の候補ノードから、該各候補ノードの前方ジョブの空き時間長、前方ジョブの使用ノード数、及び前方ジョブの最大ノード間距離の情報を備えるノードリストを作成する段階と、前記アサイン対象ジョブの実行予定ノードを選択するためのポリシーによって、前記ノードリストを前記アサイン対象ジョブの実行予定ノードを選択する優先度順にソートする段階と、を備えるジョブ管理方法。
【００６３】
（付記２）前記ポリシーは、前記候補ノードを前記前方空き時間長の昇順に前記ノードリストをソートし、前記前方空き時間長の昇順にソート後、前記候補ノードを、前記アサイン対象ジョブが使用するノード数を基準にして、前記前方ジョブの使用ノード数とノード数が同一、前記前方ジョブの使用ノード数がアサイン対象ジョブの使用ノード数よりも多く数が近い、及び前記前方ジョブの使用ノード数がアサイン対象ジョブの使用ノード数よりも少なく数が近い、順序に前記ノードリストをソートし、前記候補ノードを前記前方ジョブの最大ノード間距離の昇順に前記ノードリストをソートする、付記１に記載のジョブ管理方法。
【００６４】
（付記３）前記アサイン対象ジョブの実行予定ノードを選択する優先度順にソートされた前記ノードリストを元に、実行予定のノード数分を選択して前記アサイン対象ジョブをアサインする段階を更に備える、付記１又は付記２に記載のジョブ管理方法。
【００６５】
（付記４）多数のノードを共有するクラスタシステムにおいて、バックフィルスケジューラを使用するジョブ管理システムであって、投入されたジョブを前記多数のノードから選択し、且つ、時間に応じて割り当てて管理するスケジューラマップから、アサイン対象ジョブが要求するリソースを満たす未使用空間を検索する検索手段と、前記検索した未使用空間に基づいて、ジョブを実行開始する時刻を決定する決定手段と、前記時刻にジョブを割り当て可能な少なくとも１以上の候補ノードから、該各候補ノードの前方ジョブの空き時間長、前方ジョブの使用ノード数、及び前方ジョブの最大ノード間距離の情報を備えるノードリストを作成する作成手段と、前記アサイン対象ジョブの実行予定ノードを選択するためのポリシーによって、前記ノードリストを前記アサイン対象ジョブの実行予定ノードを選択する優先度順にソートするノード優先順位決定手段と、を備えるジョブ管理システム。
【産業上の利用可能性】
【００６６】
本発明は、多数のノードを共有し、バックフィルスケジューラによってジョブ管理を行うクラスタシステムにおいて、クラスタシステムの高使用率を実現するジョブのアサイン方法に適用できる。
【符号の説明】
【００６７】
１…ジョブ管理システム、１０…ジョブアサイン部、１１…空き情報検索手段、１２…予定実行開始時刻決定手段、１３…実行予定ノード選択部、１４…ノード優先順位決定手段、１５…ノード選択手段、１６…前方検査ポリシー。
【技術分野】
【０００１】
本発明は、ジョブ管理システム及びジョブ管理方法に関し、特に、バックフィルスケジューラを使用するジョブ管理システム及びそのジョブ管理方法に関する。
【背景技術】
【０００２】
従来、ＨＰＣ（Ｈｉｇｈ Ｐｅｒｆｏｒｍａｎｃｅ Ｃｏｍｐｕｔｉｎｇ）分野を中心に利用されるバッチ処理システムにおいて、多数のノードを接続したクラスタシステム、及びバックフィル型スケジューリングを用いるジョブスケジューラ（以降、「バックフィルスケジューラ」と称する）が利用されている。バックフィルスケジューラとは、クラスタシステムに接続されているノード等のリソースを現在から未来に渡って管理し、ジョブに対してリソースを占有して使用可能な時間枠を割り当てることを特徴とした、ジョブ管理システムのジョブスケジューリング機能である。
【０００３】
ここで、バックフィルスケジューラの特徴であるスケジューラマップについて、図１を参照して説明する。スケジューラマップとは、ジョブが使用するノードと実行する時刻についての情報とを保持するマップである。投入されたジョブは、図１（ａ）に示すように、まず、キューに繋がれ、優先度が設定される。バックフィルスケジューラは、図１（ｂ）に示すように、キュー内の優先順位の高いジョブからスケジューラマップ上の未使用空間にジョブを配置し（以降、「アサイン」と称する）、時間経過とともに予定されたジョブを実行する。
【０００４】
図１（ｂ）に示すスケジューラマップは、ジョブＡ〜Ｅがアサインされた状態を示す。この時の未使用空間は、Ｎｏｄｅ０の斜線部（１），（３）、及びＮｏｄｅ１の斜線部（２）である。バックフィルスケジューラは、ユーザが指定したジョブＦの使用ノード数や予定実行時間等の情報を元に、ジョブＦを実行するのに十分な空きがある未使用空間を探す。この場合は、未使用空間である、Ｎｏｄｅ０の斜線部（３）とＮｏｄｅ１の斜線部（２）にジョブＦをアサインする。
【０００５】
初期のクラスタシステムにおけるジョブ管理システムでは、ジョブを規模（使用ノード数）ごとにクラス分けし、クラスに対応するキューを設定し、それぞれのキューには、規模に応じて専用のノードを割り当てる。よって、利用者がジョブの規模にあったキューにジョブを投入すると、バックフィルスケジューラは、投入されたジョブをそのキューに割り当てられたクラス用のノードに配置して実行する。このような運用では、投入されるジョブの規模に偏りがあると、一部のキューに割り当てられたノードばかりが使用され、残りのノードは未使用となり、クラスタシステム全体の使用率が低くなってしまうという問題があった。また、キューごとにノード数が固定であるため、運用状況に応じてノードの割り当て数を変更することが困難であった。
【０００６】
そのため、上記の問題を解決するために、現在、全ノードを共有する方式が取られるようになった。この方式では、キューはジョブの規模（使用ノード数）ごとに設定されていても、ノードはキュー間で共有しているため、空いているノードを柔軟に選択できる。バックフィルスケジューラは、ジョブが要求するリソース条件に対して最適な未使用空間を必要ノード数選択し、ジョブをアサインする。ただし、クラスタシステムの使用率を高くするためには、なるべく未使用空間ができないようにスケジューリングすることが求められる。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００５−３１０１３９号公報
【特許文献２】特開２００９−０２６６３６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかし、全ノードを共有する方式では、下記課題を有している。
【０００９】
すなわち、一つ目の課題は、スケジューラマップ上の未使用空間の分断（断片化）である。従来の全ノードを共有する方式は、規模の不均一なジョブを、共有されたノードにアサインするため、リソースの空き状況のみを基準にして未使用空間を割り当てるものであり、この方式では未使用空間を分断するようなアサインをしてしまう可能性がある。例えば、ＨＰＣ分野では実行時間が長時間に及ぶジョブが多い傾向にあるため、時間が短い未使用空間は使われないまま残り、クラスタシステム全体の使用率低下を招く原因になる（図２参照）。
【００１０】
二つ目の課題は、先行ジョブの終了時刻不均一による後続ジョブの実行待ちである。ユーザが宣言するジョブの予定実行時間は長めに設定されていることが多く、ジョブが実行時間より早く終了することがある。このような時、通常は後続のジョブを予定実行開始時刻から早めて実行する。しかし、複数のノードで実行する場合、使用予定のノードが別のジョブによって使用されていると該当ノードが空くまで後続ジョブは実行を待たされることになる。そのため、ジョブが早期に終了したノードは、その間、アイドリング状態となる。ＨＰＣ分野では、多数のノードを使用するジョブが多いため、上記のような状態はクラスタシステム全体の使用率低下を招く原因になる（図３参照）。
【００１１】
従来技術を参照すると、例えば、特許文献１では、メッシュ構造に相互接続されたクラスタシステムにおいて、クラスタの接続状況を考慮してジョブにノードを割り当てる方法が開示されている。特許文献１に記載の発明は、ジョブ投入時点の未使用ノードのネットワーク接続状態等を考慮して、ジョブの規模に合うノード数を自動的に割り当てることを可能としている。しかし、ノード割り当ての基準は、ノード自体の性能（演算速度、信頼度等）であり、時系列でジョブ間の関係を考慮したものではないため、特許文献１に記載の発明では、前述した課題を解決することはできない。
【００１２】
また、特許文献２では、プログラム構造やＩ／Ｏによるジョブの実行待ち、ユーザの使用ＣＰＵ数の過大申告によるＣＰＵの遊休による無駄を解消するためのスケジューリング方法が開示されている。特許文献２に記載の発明は、スケジューラマップ上の先行ジョブが占有するＣＰＵを使っていない間に限り、後続ジョブが借りて実行することを可能としている。しかし、前述した課題は単一ノードの使用状況に限らず発生するため、特許文献２に記載の発明では、前述した課題を解決することはできない。
【００１３】
さらに、類似の技術として、時間と空間について制御を行うスケジューリング方式の「時空間分割スケジューリング」が知られている。これは、共有するノードの負荷状況を考慮して各ノードに複数のジョブを割当て、ラウンドロビンによる時分割でノードに割り当てたジョブを実行する方式である。しかし、バックフィルスケジューラとは設計思想がそもそも異なるため、クラスタシステムのジョブ管理には使用できない。
【００１４】
そこで、本発明は、かかる事情に鑑み、バックフィルスケジューラにおいて、未使用空間の分断と先行ジョブの予定終了時刻の不均一によるジョブの実行待ちを回避し、クラスタシステムの使用率を向上させることができる新しいジョブ管理システム及びジョブ管理方法を提供することを目的とする。
【課題を解決するための手段】
【００１５】
本発明によるジョブ管理システムは、多数のノードを共有するクラスタシステムにおいて、バックフィルスケジューラを使用するジョブ管理システムであって、投入されたジョブを前記多数のノードから選択し、且つ、時間に応じて割り当てて管理するスケジューラマップから、アサイン対象ジョブが要求するリソースを満たす未使用空間を検索する検索手段と、前記検索した未使用空間に基づいて、ジョブを実行開始する時刻を決定する決定手段と、前記時刻にジョブを割り当て可能な少なくとも１以上の候補ノードから、該各候補ノードの前方ジョブの空き時間長、前方ジョブの使用ノード数、及び前方ジョブの最大ノード間距離の情報を備えるノードリストを作成する作成手段と、前記アサイン対象ジョブの実行予定ノードを選択するためのポリシーによって、前記ノードリストを前記アサイン対象ジョブの実行予定ノードを選択する優先度順にソートするノード優先順位決定手段と、を備える。
【００１６】
本発明によるジョブ管理方法は、多数のノードを共有するクラスタシステムにおいて、バックフィルスケジューラを使用するジョブ管理方法であって、投入されたジョブを前記多数のノードから選択し、且つ、時間に応じて割り当てて管理するスケジューラマップから、アサイン対象ジョブが要求するリソースを満たす未使用空間を検索する段階と、前記検索した未使用空間に基づいて、ジョブを実行開始する時刻を決定する段階と、前記時刻にジョブを割り当て可能な少なくとも１以上の候補ノードから、該各候補ノードの前方ジョブの空き時間長、前方ジョブの使用ノード数、及び前方ジョブの最大ノード間距離の情報を備えるノードリストを作成する段階と、前記アサイン対象ジョブの実行予定ノードを選択するためのポリシーによって、前記ノードリストを前記アサイン対象ジョブの実行予定ノードを選択する優先度順にソートする段階と、を備える。
【発明の効果】
【００１７】
以上のように構成された本発明のジョブ管理システム等によれば、バックフィルスケジューラ上において小さな未使用空間が減少し、マルチノードジョブを含むより多くのジョブがアサインされやすくなるため、クラスタシステムの使用率を向上させることができる。
【図面の簡単な説明】
【００１８】
【図１】スケジューラマップについて説明するための図である。
【図２】従来のバックフィルスケジューラマップを示す図である。
【図３】従来のバックフィルスケジューラマップを示す図である。
【図４】本実施形態のジョブ管理システムの概略構成を示す図である。
【図５】本実施形態の前方検査ポリシーを適用した場合のスケジューラマップを示す図である。
【図６】本実施形態のジョブ管理方法の処理内容を示すフローチャートである。
【図７】本実施形態のジョブ管理方法の処理内容を示すフローチャートである。
【図８】本実施形態のジョブ管理方法を説明するためのノードリスト、スケジューラマップ、及びネットワーク構成を示す図である。
【図９】本実施形態のジョブ管理方法を用いた例を説明するためのノードリスト、スケジューラマップ、及びネットワーク構成を示す図である。
【発明を実施するための形態】
【００１９】
本発明は、バックフィルスケジューラにおいて、ジョブ投入時にジョブをアサインする空間を選択するためのポリシーを提供する。このポリシーにより、従来技術の課題である未使用空間の分断と先行ジョブの予定終了時刻の不均一によるノードの実行待ち（遊休時間発生）を回避し、クラスタシステムの使用率を向上させるものである。
【００２０】
以下、本発明を実施するための好適な実施形態を、図面を参照しながら説明する。図４は、本実施形態におけるジョブ管理を行うクラスタシステム（ジョブ管理システム）１の概略構成を示す。
【００２１】
ジョブ管理システム１は、多数のノードを共有するクラスタシステムにおける、バックフィルスケジューラを使用するものであり、図４に示すように、ジョブアサイン部１０と情報管理部２０とを含んで構成される。バックフィルスケジューラは、投入されたジョブ（以下、「アサイン対象ジョブ」と称する）が要求するリソースを満たす未使用空間をスケジューラマップ上から検索し、最も早く実行を開始できる空間を割り当てる機能を有する。この最も早く実行を開始できる時刻を、本実施形態では、予定実行開始時刻という。予定実行開始時刻からジョブを割り当てることができる未使用空間は、１通り以上のノードの組み合わせになる可能性があるため、候補の中から使用するノードを選択するために、後述するポリシーを適用する。なお、ジョブ管理システム１は、ハードウェアとして、例えば、ＣＰＵ、ＣＰＵにバス結合されたＲＯＭ、ＲＡＭ、記憶部、入力部、表示部、および入出力インタフェースなど、通常のコンピュータ装置と同様のハードウェアを備えることができる。また、物理的には、専用化したシステム、あるいは汎用の情報処理装置のいずれであってもよい。
【００２２】
ジョブアサイン部１０は、投入されたジョブを現在から未来に渡るノード空間にアサインするものであり、空き情報検索手段１１、予定実行開始時刻決定手段１２、及び実行予定ノード選択部１３を含み、実行予定ノード選択部１３は、更に、ノード優先順位決定手段１４及びノード選択手段１５を含む。
【００２３】
空き情報検索手段（検索手段）１１は、アサイン対象ジョブが実行可能なリソースを備える未使用空間を検索する機能を有する。
【００２４】
予定実行開始時刻決定手段（決定手段）１２は、検索によって得られた未使用空間情報に基づいて、アサイン対象ジョブを最も早く実行開始できる時刻を決定する機能を有する。
【００２５】
実行予定ノード選択部１３は、上記実行開始できる時刻にジョブを割り当て可能な少なくとも１以上の候補ノードから、該各候補ノードの前方ジョブの空き時間長、前方ジョブの使用ノード数、及び前方ジョブの最大ノード間距離の情報を備えるノードリストを作成する作成手段として機能する。また、実行予定ノード選択部１３は、ノード優先順位決定手段１４によってノードに優先順位をつけ、ノード選択手段１５によって優先順位に従い、使用するノードを決定する。
【００２６】
ノード優先順位決定手段１４は、１つ以上のポリシーを有しており、本実施形態の前方検査ポリシー１６は、そのうちの一つである。なお、前方検査ポリシー１６については、後述する。
【００２７】
情報管理部２０は、ジョブやクラスタシステムに関する情報を管理するものであり、情報更新手段２１、ジョブ情報（データベース）２２、及びノードの構成を保持するトポロジ情報（データベース）２３を含む。
【００２８】
情報更新手段２１は、アサインが確定したジョブの情報をジョブ情報２２に格納する。
【００２９】
ジョブ情報２２は、アサイン済みのジョブに関する情報を保持するものであり、トポロジ情報２３は、ノードの構成を保持するものである。ここで、本実施形態では、前方ジョブの最大ノード間距離のコストを「ルータを経由する回数」と定義する。すなわち、トポロジ情報２３は、コストを算出するため、ノードの構成が保持される。
【００３０】
ここで、本実施形態の前方検査ポリシー１６について説明する。前方検査ポリシー１６は、まず、前方空き時間長が昇順になるようにソートする。次に、同じ前方空き時間長を持つノードごとに、アサイン対象ジョブの使用ノード数を基準に、「前方ジョブの使用ノード数とノード数が同一」、「前方ジョブの使用ノード数がアサイン対象ジョブの使用ノード数よりも多く、数が近い」、「前方ジョブの使用ノード数がアサイン対象ジョブの使用ノード数よりも少なく、数が近い」という順に未使用空間情報をソートする。最後に、前方ジョブの使用ノード数が同じノードごとに、最大ノード間距離を昇順に未使用空間情報をソートする。このリストの上位から、アサイン対象ジョブが使用するノード数分、ノードを選択する。この操作により、前方ジョブとの空き時間が少なく、使用ノード数がアサイン対象ジョブと同じか、より多いジョブに割り当てられていて、ノード間の距離も近いノードを選ぶことが可能になる。すなわち、前方ジョブとの空き時間が少ないということは、長い未使用空間を中央で分断していないということであり、また、使用ノード数が同じということは前方ジョブが早期終了したときに後続ジョブの予定実行開始時刻を繰り上げて実行ができるということである。ノード間距離が近いノードを優先して選択することで、通信による待ち時間を減らし、より早くジョブの実行を終えることができる。
【００３１】
図２のスケジューラマップのジョブを、前方検査ポリシー１６を使用してアサインした場合のスケジューラマップを図５に示す。ジョブＣがジョブＡのノードにアサインされ、ジョブＧが未使用空間を分断しないなどの改善を得ることができる。その結果、図２に示す場合では（前方検査ポリシー不適用）、ジョブＨはジョブＦの後ろにアサインされていたが、図５に示す場合では（前方検査ポリシー適用）、ジョブＨはジョブＦの前にアサインすることが可能となる。
【００３２】
ここで、ノード障害時の対応としては、アサインをキャンセルされたジョブ（以下、「被障害ジョブ」と称する）を元々の予定実行開始時刻近くの未使用空間に再割り当てする運用方法がある。しかし、本実施形態の前方検査ポリシーを使用すれば、スケジューラマップの前方が隙間無く埋められているために、被障害ジョブを再割当てすることが難しくなる。そのため、なるべく早い時刻に再割り当て可能なように、ノード障害時用の優先度を設定することもできる。具体的には、被障害ジョブであることがわかるように識別子を用意し、被障害ジョブの優先度を新たに投入されたジョブよりも高くすることで、被障害ジョブを、未割り当てのジョブの中で最も早く実行開始できるようにしてもよい。
【００３３】
次に、図４，図６〜図８を参照して、本実施形態の動作処理について詳細に説明する。なお、以下では、図４に示すジョブアサイン部１０と情報管理部２０とがクラスタシステムに１つずつあり、該クラスタシステムのジョブ管理を行うものとする。
【００３４】
まず、ジョブアサイン部１０の動作処理を、図６に示すフローチャートを参照しながら説明する。
【００３５】
空き情報検索手段１１は、各ノードについて、ユーザが指定した予定実行時間以上の空きがあり、且つ、最も早く実行可能な未使用空間を検索する（ステップＳ１０１）。ユーザは、ジョブを投入する際に、使用するノード数やメモリ量、予定実行時間を指定する。
【００３６】
未使用空間があるか否かを判定し（ステップＳ１０２）、未使用空間がないと判定した場合（ステップＳ１０２：Ｎｏ）、処理を終了する。投入されたジョブは次回の未使用空間検索が行われるまで待ち状態になる。
【００３７】
一方、未使用空間があると判定した場合（ステップＳ１０２：Ｙｅｓ）、予定実行開始時刻決定手段１２は、使用するノード数や予定実行時間などの条件を満たし、且つ、最も早くジョブを実行開始できる時刻を予定実行開始時刻として決定する（ステップＳ１０３）。
【００３８】
実行予定ノード選択部１３は、予定実行開始時刻にジョブを割り当てることができるノードについて、ジョブ情報２２とトポロジ情報２３を参照して、「前方空き時間長、前方ジョブのノード数、前方ジョブの最大ノード間距離」等の情報を備えたノードリストを作成する（ステップＳ１０４）。
【００３９】
ノード優先順位決定手段１４は、ユーザが指定した使用ノード数以上に、該当するノードがあった場合、実行予定ノードを選択するためのポリシー適用と判定し（ステップＳ１０５：Ｙｅｓ）、使用するノードを選択するために１つ以上のポリシーを適用する（ステップＳ１０６）。
【００４０】
ノード選択手段１５は、適用したポリシーによって優先度順にソートされたノードリストを元に、ユーザによって指定された使用ノード数分を選択し、ジョブをアサインする（ステップＳ１０７）。
【００４１】
情報更新手段２１は、アサインしたジョブについて、情報管理部２０のジョブ情報２２を更新する（ステップＳ１０８）。
【００４２】
一方、ポリシー適用と判定しない場合（ステップＳ１０５：Ｎｏ）、ノード選択手段１５は、検索した空き情報に基づいて実行予定のノードを選択し（ステップＳ１０９）、情報更新手段２１は、実行予定時間と実行予定のノードを更新する（ステップＳ１０８）。
【００４３】
以上により、ジョブアサイン部１０の動作処理を終了する。
【００４４】
次に、図７及び図８を参照して、本実施形態における、２ノードを使用するジョブＸを割り当てるときの前方検査ポリシー１６の動作説明をする。なお、以下では、３台ずつのノードを接続したクラスタをさらに上位で接続した計６台からなる構成を想定する場合を例にとって説明する。
【００４５】
ここで、図８に示すネットワーク構成は、ノード間の接続関係を示し、現在時刻で処理しているジョブＡ，Ｂ，Ｃ，Ｄを示す。また、図８のスケジューラマップは、ジョブ管理システムのアサイン状況を示す。さらに、図８の表１〜表３は、ジョブアサイン部１０が作成したノードリストに対して、前方検査ポリシー１６を適用していく過程を示すものである。
【００４６】
図７に示すように、まず、前方検査ポリシー１６は、各ノードにおいて前方空き時間長の順序に従い、ノードリストをソートする（ステップＳ２０１）。図８に示す場合においては、ソートした結果、表１に示すノードリストから、表２に示すノードリストになる。
【００４７】
次に、前方検査ポリシー１６は、同じ前方空き時間長のノードごとに、前方のジョブが使用するノード数についてソートする（ステップＳ２０２）。具体的には、ソートの順番は、アサイン対象ジョブが使用するノード数を基準に、前方ジョブの使用ノード数が「ノード数が同一、より多いが数が近い、より少ないが数が近い」の順序である。図８に示す場合においては、前方空き時間長が「０」のノードを使用するジョブは全て２つのノードを使用するため、ソートした結果は変わらない。
【００４８】
次いで、前方検査ポリシー１６は、同じ前方空き時間長、使用ノード数を持つノードごとに、前方ジョブが使用するノード群の最大ノード間距離順になるようにソートする（ステップＳ２０３）。図８に示すように、想定するクラスタシステムにおいて、ジョブＢが使用するノードは、同じクラスタに接続されているため、最大ノード間距離は０、ジョブＡの最大ノード間距離は２となる。したがって、ソートした結果、表２に示すノードリストから、表３に示すノードリストになる。
【００４９】
ジョブアサイン部１０は、他に適用するポリシーが登録されていなければ、上記ソートした結果（図８に示す表３）に従い、ジョブＸがＮｏｄｅ３とＮｏｄｅ４に割り当てられる。
【００５０】
なお、アサイン後に使用予定のノードが障害のため停止した場合は、障害ノードにアサインされていたジョブをすべて解除し、再度ジョブアサインを行うことができる。また、解除時に、各ジョブ情報の被障害識別子に障害にあったことを記録することで、再アサイン時に障害発生後に投入されたジョブよりも優先的に未使用空間を割り当てることもできる。
【００５１】
以上のような本実施形態のバックフィルスケジューラを使用するジョブ管理方法では、以下の効果を奏する。
【００５２】
第１の効果は、クラスタシステムの使用率を向上させることである。その理由は、小さな未使用空間が減少し、マルチノードジョブを含む、より多くのジョブがアサインされやすくなるためであり、且つ、実行中ジョブが予定より早期に終了した場合に直後にアサインされているジョブが即時に実行され、システムのアイドリング時間を減少させることができるためである。
【００５３】
第２の効果は、ジョブのターンアラウンドタイム（ＴＡＴ）を短縮できることである。その理由は、大きい未使用空間にジョブがアサインされやすくなることでジョブが早期に実行されることや、ノード間距離が近いノードを使用することで通信時間を抑えることが、ＴＡＴの短縮に繋がるためである。
【００５４】
第３の効果は、ジョブの投入数が少ない場合にノードの省電力運転をしやすくなることである。その理由は、ノードの未使用時間を分断しないようにジョブをアサインするため、未使用時間が長時間になりやすく、その間、電源を切るなどの運用が可能になる。通常、起動・終了処理はその処理時間が長くかかるため、未使用時間が短く頻繁にジョブを実行するような場合には、電源を切ることは出来ないからである。
【００５５】
＜他の実施形態＞
【００５６】
以下、上述の本実施形態で示した前方検査ポリシー１６の処理において、前方ジョブが使用するノード群の最大ノード間距離を、ノードの電力供給経路に置き換えた場合を例にとって説明する。この場合、優先する電力供給の経路を使用するノードを使うことになるため、アサインされているジョブが少ない場合は、同じ電力供給の経路（配電盤等）を使うノードをまとめて電源を切ることが可能になり、省電力を優先する運用に使用できる。
【００５７】
図９は、ノード０〜２が繋がる経路（配電盤１）の優先度が高い場合のジョブ投入を示した図である。ノードリストを前方空き時間長、前方ジョブのノード数、電力供給経路の優先順でソートした結果、ジョブＸはＮｏｄｅ１，２にアサインされる。Ｎｏｄｅ３〜５は未使用になった区間であるため、電源を切ることができる。
【００５８】
＜変形例＞
以上のように本発明の好適な実施形態について説明したが、本発明は、以上の実施形態に限定されるべきものではなく、特許請求の範囲に表現された思想および範囲を逸脱することなく、種々の変形、追加、および省略が当業者によって可能である。
【００５９】
例えば、上記各実施形態では、ジョブアサイン部１０及び情報管理部２０において、それぞれの処理機能を有する各手段等が備えられている構成を説明したが、本発明はこれに限られず、例えば、各手段が通信可能に接続されたネットワーク上に又は他の装置に備えて構成することもできる。
【００６０】
さらに、上記各実施形態では、ジョブアサイン部１０及び情報管理部２０には、用途に応じた各手段がそれぞれ備えられているが、これら各手段は、そのいくつかを一纏めにして構成されていてもよいし、一つの部をさらに複数の部に分割して構成されていてもよい。
【００６１】
上記の実施形態の一部または全部は、以下の付記のようにも記載されうるが、以下には限られない。
【００６２】
（付記１）多数のノードを共有するクラスタシステムにおいて、バックフィルスケジューラを使用するジョブ管理方法であって、投入されたジョブを前記多数のノードから選択し、且つ、時間に応じて割り当てて管理するスケジューラマップから、アサイン対象ジョブが要求するリソースを満たす未使用空間を検索する段階と、前記検索した未使用空間に基づいて、ジョブを実行開始する時刻を決定する段階と、前記時刻にジョブを割り当て可能な少なくとも１以上の候補ノードから、該各候補ノードの前方ジョブの空き時間長、前方ジョブの使用ノード数、及び前方ジョブの最大ノード間距離の情報を備えるノードリストを作成する段階と、前記アサイン対象ジョブの実行予定ノードを選択するためのポリシーによって、前記ノードリストを前記アサイン対象ジョブの実行予定ノードを選択する優先度順にソートする段階と、を備えるジョブ管理方法。
【００６３】
（付記２）前記ポリシーは、前記候補ノードを前記前方空き時間長の昇順に前記ノードリストをソートし、前記前方空き時間長の昇順にソート後、前記候補ノードを、前記アサイン対象ジョブが使用するノード数を基準にして、前記前方ジョブの使用ノード数とノード数が同一、前記前方ジョブの使用ノード数がアサイン対象ジョブの使用ノード数よりも多く数が近い、及び前記前方ジョブの使用ノード数がアサイン対象ジョブの使用ノード数よりも少なく数が近い、順序に前記ノードリストをソートし、前記候補ノードを前記前方ジョブの最大ノード間距離の昇順に前記ノードリストをソートする、付記１に記載のジョブ管理方法。
【００６４】
（付記３）前記アサイン対象ジョブの実行予定ノードを選択する優先度順にソートされた前記ノードリストを元に、実行予定のノード数分を選択して前記アサイン対象ジョブをアサインする段階を更に備える、付記１又は付記２に記載のジョブ管理方法。
【００６５】
（付記４）多数のノードを共有するクラスタシステムにおいて、バックフィルスケジューラを使用するジョブ管理システムであって、投入されたジョブを前記多数のノードから選択し、且つ、時間に応じて割り当てて管理するスケジューラマップから、アサイン対象ジョブが要求するリソースを満たす未使用空間を検索する検索手段と、前記検索した未使用空間に基づいて、ジョブを実行開始する時刻を決定する決定手段と、前記時刻にジョブを割り当て可能な少なくとも１以上の候補ノードから、該各候補ノードの前方ジョブの空き時間長、前方ジョブの使用ノード数、及び前方ジョブの最大ノード間距離の情報を備えるノードリストを作成する作成手段と、前記アサイン対象ジョブの実行予定ノードを選択するためのポリシーによって、前記ノードリストを前記アサイン対象ジョブの実行予定ノードを選択する優先度順にソートするノード優先順位決定手段と、を備えるジョブ管理システム。
【産業上の利用可能性】
【００６６】
本発明は、多数のノードを共有し、バックフィルスケジューラによってジョブ管理を行うクラスタシステムにおいて、クラスタシステムの高使用率を実現するジョブのアサイン方法に適用できる。
【符号の説明】
【００６７】
１…ジョブ管理システム、１０…ジョブアサイン部、１１…空き情報検索手段、１２…予定実行開始時刻決定手段、１３…実行予定ノード選択部、１４…ノード優先順位決定手段、１５…ノード選択手段、１６…前方検査ポリシー。
【特許請求の範囲】
【請求項１】
多数のノードを共有するクラスタシステムにおいて、バックフィルスケジューラを使用するジョブ管理方法であって、
投入されたジョブを前記多数のノードから選択し且つ時間に応じて割り当てて管理するスケジューラマップから、アサイン対象ジョブが要求するリソースを満たす未使用空間を検索する段階と、
前記検索した未使用空間に基づいて、ジョブを実行開始する時刻を決定する段階と、
前記時刻にジョブを割り当て可能な少なくとも１以上の候補ノードから、該各候補ノードの前方ジョブの空き時間長、前方ジョブの使用ノード数、及び前方ジョブの最大ノード間距離の情報を備えるノードリストを作成する段階と、
前記アサイン対象ジョブの実行予定ノードを選択するためのポリシーによって、前記ノードリストを前記アサイン対象ジョブの実行予定ノードを選択する優先度順にソートする段階と、
を備えるジョブ管理方法。
【請求項２】
前記ポリシーは、
前記候補ノードを前記前方空き時間長の昇順に前記ノードリストをソートし、
前記前方空き時間長の昇順にソート後、前記候補ノードを、前記アサイン対象ジョブが使用するノード数を基準にして、前記前方ジョブの使用ノード数とノード数が同一、前記前方ジョブの使用ノード数がアサイン対象ジョブの使用ノード数よりも多く数が近い、及び前記前方ジョブの使用ノード数がアサイン対象ジョブの使用ノード数よりも少なく数が近い、順序に前記ノードリストをソートし、
前記候補ノードを前記前方ジョブの最大ノード間距離の昇順に前記ノードリストをソートする、請求項１に記載のジョブ管理方法。
【請求項３】
前記アサイン対象ジョブの実行予定ノードを選択する優先度順にソートされた前記ノードリストを元に、実行予定のノード数分を選択して前記アサイン対象ジョブをアサインする段階を更に備える、請求項１又は請求項２に記載のジョブ管理方法。
【請求項４】
多数のノードを共有するクラスタシステムにおいて、バックフィルスケジューラを使用するジョブ管理システムであって、
投入されたジョブを前記多数のノードから選択し且つ時間に応じて割り当てて管理するスケジューラマップから、アサイン対象ジョブが要求するリソースを満たす未使用空間を検索する検索手段と、
前記検索した未使用空間に基づいて、ジョブを実行開始する時刻を決定する決定手段と、
前記時刻にジョブを割り当て可能な少なくとも１以上の候補ノードから、該各候補ノードの前方ジョブの空き時間長、前方ジョブの使用ノード数、及び前方ジョブの最大ノード間距離の情報を備えるノードリストを作成する作成手段と、
前記アサイン対象ジョブの実行予定ノードを選択するためのポリシーによって、前記ノードリストを前記アサイン対象ジョブの実行予定ノードを選択する優先度順にソートするノード優先順位決定手段と、
を備えるジョブ管理システム。
【請求項１】
多数のノードを共有するクラスタシステムにおいて、バックフィルスケジューラを使用するジョブ管理方法であって、
投入されたジョブを前記多数のノードから選択し且つ時間に応じて割り当てて管理するスケジューラマップから、アサイン対象ジョブが要求するリソースを満たす未使用空間を検索する段階と、
前記検索した未使用空間に基づいて、ジョブを実行開始する時刻を決定する段階と、
前記時刻にジョブを割り当て可能な少なくとも１以上の候補ノードから、該各候補ノードの前方ジョブの空き時間長、前方ジョブの使用ノード数、及び前方ジョブの最大ノード間距離の情報を備えるノードリストを作成する段階と、
前記アサイン対象ジョブの実行予定ノードを選択するためのポリシーによって、前記ノードリストを前記アサイン対象ジョブの実行予定ノードを選択する優先度順にソートする段階と、
を備えるジョブ管理方法。
【請求項２】
前記ポリシーは、
前記候補ノードを前記前方空き時間長の昇順に前記ノードリストをソートし、
前記前方空き時間長の昇順にソート後、前記候補ノードを、前記アサイン対象ジョブが使用するノード数を基準にして、前記前方ジョブの使用ノード数とノード数が同一、前記前方ジョブの使用ノード数がアサイン対象ジョブの使用ノード数よりも多く数が近い、及び前記前方ジョブの使用ノード数がアサイン対象ジョブの使用ノード数よりも少なく数が近い、順序に前記ノードリストをソートし、
前記候補ノードを前記前方ジョブの最大ノード間距離の昇順に前記ノードリストをソートする、請求項１に記載のジョブ管理方法。
【請求項３】
前記アサイン対象ジョブの実行予定ノードを選択する優先度順にソートされた前記ノードリストを元に、実行予定のノード数分を選択して前記アサイン対象ジョブをアサインする段階を更に備える、請求項１又は請求項２に記載のジョブ管理方法。
【請求項４】
多数のノードを共有するクラスタシステムにおいて、バックフィルスケジューラを使用するジョブ管理システムであって、
投入されたジョブを前記多数のノードから選択し且つ時間に応じて割り当てて管理するスケジューラマップから、アサイン対象ジョブが要求するリソースを満たす未使用空間を検索する検索手段と、
前記検索した未使用空間に基づいて、ジョブを実行開始する時刻を決定する決定手段と、
前記時刻にジョブを割り当て可能な少なくとも１以上の候補ノードから、該各候補ノードの前方ジョブの空き時間長、前方ジョブの使用ノード数、及び前方ジョブの最大ノード間距離の情報を備えるノードリストを作成する作成手段と、
前記アサイン対象ジョブの実行予定ノードを選択するためのポリシーによって、前記ノードリストを前記アサイン対象ジョブの実行予定ノードを選択する優先度順にソートするノード優先順位決定手段と、
を備えるジョブ管理システム。
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図１】
【図８】
【図９】
【図３】
【図４】
【図５】
【図６】
【図７】
【図１】
【図８】
【図９】
【公開番号】特開２０１２−２１５９３３（Ｐ２０１２−２１５９３３Ａ）
【公開日】平成２４年１１月８日（２０１２．１１．８）
【国際特許分類】
【出願番号】特願２０１１−７８９３２（Ｐ２０１１−７８９３２）
【出願日】平成２３年３月３１日（２０１１．３．３１）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【出願人】（３９０００１３９５）ＮＥＣシステムテクノロジー株式会社 (438)
【公開日】平成２４年１１月８日（２０１２．１１．８）
【国際特許分類】
【出願日】平成２３年３月３１日（２０１１．３．３１）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【出願人】（３９０００１３９５）ＮＥＣシステムテクノロジー株式会社 (438)
[ Back to top ]