(57)【要約】  計算資源管理装置１０は、複数のタスクを実行するクラスタシステム２０を管理するための装置である。計算資源管理装置１０は、クラスタシステム２０の計算資源と計算時間との関係、タスク間の依存関係、及び各タスクの実行期限を特定する、条件特定部１１と、特定された計算資源と計算時間との関係、存関係に基づいて、タスク毎に、実行期限が守られるように、実行順序、及びクラスタシステム２０の計算資源のうちの割当てるべき計算資源を決定する、スケジューリング部１２と、を備えている。
2018198745.tif 000002
【特許請求の範囲】
【請求項１】
複数のタスクを実行するクラスタシステムを管理するための装置であって、
前記クラスタシステムの計算資源と計算時間との関係、前記複数のタスクそれぞれ間の依存関係、及び前記複数のタスクそれぞれの実行期限を特定する、条件特定部と、
特定された前記関係、前記依存関係に基づいて、前記複数のタスクそれぞれ毎に、前記実行期限が守られるように、実行順序、及び前記クラスタシステムの計算資源のうちの割当てるべき計算資源を決定する、スケジューリング部と、
を備えている、
ことを特徴とする計算資源管理装置。
【請求項２】
前記スケジューリング部が、
前記依存関係及び前記実行期限に基づいた、前記複数のタスクそれぞれの実行順序の決定処理と、決定された前記実行順序の元での、前記複数のタスクそれぞれへの任意の計算資源の割当て処理とを、一連の処理として複数回行なって、
前記複数のタスクそれぞれ毎に、実行順序、及び前記クラスタシステムの計算資源のうちの割当てるべき計算資源を決定する、
請求項１に記載の計算資源管理装置。
【請求項３】
前記スケジューリング部が、
前記複数のタスクそれぞれが前記実行期限内に完了している前記一連の処理のうち、前記複数のタスクそれぞれの実行終了時刻が設定条件を満たす一連の処理を選択し、
選択した一連の処理における前記決定処理及び前記割当て処理の結果を用いて、前記複数のタスクそれぞれ毎に、実行順序、及び前記クラスタシステムの計算資源のうちの割当てるべき計算資源を決定する、
請求項２に記載の計算資源管理装置。
【請求項４】
前記関係が、前記複数のタスクそれぞれ毎のコア数と計算時間との関係である、
請求項１〜３のいずれかに記載の計算資源管理装置。
【請求項５】
複数のタスクを実行するクラスタシステムを管理するための方法であって、
（ａ）前記クラスタシステムの計算資源と計算時間との関係、前記複数のタスクそれぞれ間の依存関係、及び前記複数のタスクそれぞれの実行期限を特定する、ステップと、
（ｂ）前記（ａ）のステップで特定された前記関係、前記依存関係に基づいて、前記複数のタスクそれぞれ毎に、前記実行期限が守られるように、実行順序、及び前記クラスタシステムの計算資源のうちの割当てるべき計算資源を決定する、ステップと、
を有する、
ことを特徴とする計算資源管理方法。
【請求項６】
前記（ｂ）のステップにおいて、
前記依存関係及び前記実行期限に基づいた、前記複数のタスクそれぞれの実行順序の決定処理と、決定された前記実行順序の元での、前記複数のタスクそれぞれへの任意の計算資源の割当て処理とを、一連の処理として複数回行なって、
前記複数のタスクそれぞれ毎に、実行順序、及び前記クラスタシステムの計算資源のうちの割当てるべき計算資源を決定する、
請求項５に記載の計算資源管理方法。
【請求項７】
前記（ｂ）のステップにおいて、
前記複数のタスクそれぞれが前記実行期限内に完了している前記一連の処理のうち、前記複数のタスクそれぞれの実行終了時刻が設定条件を満たす一連の処理を選択し、
選択した一連の処理における前記決定処理及び前記割当て処理の結果を用いて、前記複数のタスクそれぞれ毎に、実行順序、及び前記クラスタシステムの計算資源のうちの割当てるべき計算資源を決定する、
請求項６に記載の計算資源管理方法。
【請求項８】
前記関係が、前記複数のタスクそれぞれ毎のコア数と計算時間との関係である、
請求項５〜７のいずれかに記載の計算資源管理方法。
【請求項９】
コンピュータによって、複数のタスクを実行するクラスタシステムを管理するためのプログラムを記録したコンピュータ読み取り可能な記録媒体であって、
前記コンピュータに、
（ａ）前記クラスタシステムの計算資源と計算時間との関係、前記複数のタスクそれぞれ間の依存関係、及び前記複数のタスクそれぞれの実行期限を特定する、ステップと、
（ｂ）前記（ａ）のステップで特定された前記関係、前記依存関係に基づいて、前記複数のタスクそれぞれ毎に、前記実行期限が守られるように、実行順序、及び前記クラスタシステムの計算資源のうちの割当てるべき計算資源を決定する、ステップと、
を実行させる命令を含む、プログラムを記録しているコンピュータ読み取り可能な記録媒体。
【請求項１０】
前記（ｂ）のステップにおいて、
前記依存関係及び前記実行期限に基づいた、前記複数のタスクそれぞれの実行順序の決定処理と、決定された前記実行順序の元での、前記複数のタスクそれぞれへの任意の計算資源の割当て処理とを、一連の処理として複数回行なって、
前記複数のタスクそれぞれ毎に、実行順序、及び前記クラスタシステムの計算資源のうちの割当てるべき計算資源を決定する、
請求項９に記載のコンピュータ読み取り可能な記録媒体。
【請求項１１】
前記（ｂ）のステップにおいて、
前記複数のタスクそれぞれが前記実行期限内に完了している前記一連の処理のうち、前記複数のタスクそれぞれの実行終了時刻が設定条件を満たす一連の処理を選択し、
選択した一連の処理における前記決定処理及び前記割当て処理の結果を用いて、前記複数のタスクそれぞれ毎に、実行順序、及び前記クラスタシステムの計算資源のうちの割当てるべき計算資源を決定する、
請求項１０に記載のコンピュータ読み取り可能な記録媒体。
【請求項１２】
前記関係が、前記複数のタスクそれぞれ毎のコア数と計算時間との関係である、
請求項９〜１１のいずれかに記載のコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のタスクを実行するクラスタリングシステムにおいて、各タスクへの計算資源の割当を最適化するための、計算資源管理装置、及び計算資源管理方法に関し、更には、これらを実現するためのコンピュータ読み取り可能な記録媒体に関する。
【背景技術】
【０００２】
近年、大量のデータを分析して、所定の条件における最適解、例えば、プラントにおける材料の投入量、操作機器における操作量、又は商品の設定価格等を利用者に提供する分析システムが提案されている。また、このような分析システムは、利用者が、最終的な選択を行うための情報、例えば、判断指標等を提供することもできる。【０００３】
そして、分析対象となるデータ量は年々著しく増加していることから、分析システムとしては、クラスタシステムが用いられている。クラスタシステムは、タスクを、分散して、且つ並列に実行する。【０００４】
ここで、例えば、プラントにおける材料の投入量、操作機器における操作量、又は商品の設定価格等を、過去のデータをもとに最適化をするというタスクを考える。通常、こういった最適化処理は、毎日又は毎週という単位で実行する必要がある。これは、元になるデータが日々更新されるからである。また、最適化処理は、事業者による意思決定の前までに実行されて、最適解が導出されている必要がある。例えば、事業者が商品の価格を設定する前に、最適化された設定価格が決まっていなければ、事業は商品を販売できないことになる。従って、分析システムにおいては、タスクを締切りまでに完了させることは重要である。【０００５】
そして、タスクを締め切りまでに完了させるためには、分析システムが備える計算資源を効率良く使用する必要がある。このため、例えば、特許文献１は、効率良くタスクを実行するためのコア数を求めることができるシステムを開示している。特許文献１に開示されたシステムは、並列して実行されるタスク毎に、並列処理を実行可能なコア数の範囲内で、タスクの実行時間を最小化するコア数を計算し、計算したコア数で各タスクを実行する。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２０１５−０２２５７４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
ところで、例えば、上述した商品の設定価格を最適化するタスクは、実際は、過去データからの特徴量の抽出タスク、需要の予測タスク、設定価格の最適化タスクといった、依存関係のある複数のタスクによって構成されている。また、これらのタスクは、別の種類のデータに対して別個に実行される場合もある。典型的には、入力データが異なる２つの特徴量抽出タスクが別々に行なわれる。【０００８】
そして、このような場合、２つの特徴量抽出タスクは並列に実行できるが、需要の予測タスクと設定価格の最適化タスクとは、その後に実行される必要がある。つまり、通常、タスクには、依存関係がワークフローとして与えられているため、このような依存関係を考慮して、タスクに割当てる計算資源を最適化する必要がある。【０００９】
しかしながら、上記特許文献１に開示されたシステムでは、タスク間の依存関係は考慮されておらず、単にタスク毎に実行時間を最小化するコア数が計算されているだけである。このため、上記特許文献１に開示されたシステムでは、依存関係がある複数のタスクに対して最適な計算資源を割当てることは困難である。【００１０】
本発明の目的の一例は、上記問題を解消し、依存関係のある複数のタスクを実行する場合に、依存関係を踏まえて各タスクに割当てる計算資源を最適化し得る、計算資源管理装置、計算資源管理方法、及びコンピュータ読み取り可能な記録媒体を提供することにある。
【課題を解決するための手段】
【００１１】
上記目的を達成するため、本発明の一側面における計算資源管理装置は、複数のタスクを実行するクラスタシステムを管理するための装置であって、
前記クラスタシステムの計算資源と計算時間との関係、前記複数のタスクそれぞれ間の依存関係、及び前記複数のタスクそれぞれの実行期限を特定する、条件特定部と、
特定された前記関係、前記依存関係に基づいて、前記複数のタスクそれぞれ毎に、前記実行期限が守られるように、実行順序、及び前記クラスタシステムの計算資源のうちの割当てるべき計算資源を決定する、スケジューリング部と、
を備えている、ことを特徴とする。【００１２】
また、上記目的を達成するため、本発明の一側面における計算資源管理方法は、複数のタスクを実行するクラスタシステムを管理するための方法であって、
（ａ）前記クラスタシステムの計算資源と計算時間との関係、前記複数のタスクそれぞれ間の依存関係、及び前記複数のタスクそれぞれの実行期限を特定する、ステップと、
（ｂ）前記（ａ）のステップで特定された前記関係、前記依存関係に基づいて、前記複数のタスクそれぞれ毎に、前記実行期限が守られるように、実行順序、及び前記クラスタシステムの計算資源のうちの割当てるべき計算資源を決定する、ステップと、
を有する、
ことを特徴とする。【００１３】
更に、上記目的を達成するため、本発明の一側面におけるコンピュータ読み取り可能な記録媒体は、コンピュータによって、複数のタスクを実行するクラスタシステムを管理するためのプログラムを記録したコンピュータ読み取り可能な記録媒体であって、
前記コンピュータに、
（ａ）前記クラスタシステムの計算資源と計算時間との関係、前記複数のタスクそれぞれ間の依存関係、及び前記複数のタスクそれぞれの実行期限を特定する、ステップと、
（ｂ）前記（ａ）のステップで特定された前記関係、前記依存関係に基づいて、前記複数のタスクそれぞれ毎に、前記実行期限が守られるように、実行順序、及び前記クラスタシステムの計算資源のうちの割当てるべき計算資源を決定する、ステップと、
を実行させる命令を含む、プログラムを記録していることを特徴とする。
【発明の効果】
【００１４】
以上のように本発明によれば、依存関係のある複数のタスクを実行する場合に、依存関係を踏まえて各タスクに割当てる計算資源を最適化することができる。
【図面の簡単な説明】
【００１５】
【図１】図１は、依存関係のある複数のタスクの一例を示す図である。
【図２】図２は、計算資源と計算時間との関係の一例を示す図である。
【図３】図３は、コアの割当ての第１の例を示す図である。
【図４】図４は、コアの割当ての第２の例を示す図である。
【図５】図５は、コアの割当ての第３の例を示す図である。
【図６】図６は、コアの割当ての第４の例を示す図である。
【図７】図７は、本発明の実施の形態における計算資源管理装置の概略構成を示すブロック図である。
【図８】図８は、本発明の実施の形態における計算資源管理装置の具体的構成を示すブロック図である。
【図９】図９は、本発明の実施の形態における計算資源管理装置の動作を示すフロー図である。
【図１０】図１０は、本発明の実施の形態における具体例で用いられる計算資源と計算時間との関係を示す図である。
【図１１】図１１は、本発明の実施の形態における計算資源管理装置を実現するコンピュータの一例を示すブロック図である。
【発明を実施するための形態】
【００１６】
（発明の概要）
一般に、タスクの実行にかかる時間とそれに割当てられる計算資源との間には、一定の関係があり、１つのタスクに計算資源を多く割り当てたからといって、処理が速く終わるわけではない。つまり、計算資源としてコア数を想定すると、タスクにコア数を多く割り当てた場合、計算が並列化されることにより、並列化可能なタスクの計算時間は短くなるが、並列化不可能なタスクの計算時間はコア数を増やしても短くなることはない。これは、並列化により、コア間で通信の必要が発生し、その分計算時間がかかる、という現象が起こったことによる。このことは、単位コアあたりの計算効率は、割り当てるコア数を増やすごとに減少することを意味している。
【００１７】
一方で、タスク間に依存関係があり、あるタスクの実行終了時刻が全体のボトルネックとなる場合、あるタスクの実行期限が迫っているため、多少の計算効率を犠牲にしても、そのタスクの実行を終了させたい場合等がある。このような場合においては、計算効率を犠牲にしても、ネックとなるタスクに多くのコア数を割り当てる必要がある。但し、計算効率を軽視すると、全体のワークフローの終了が遅れ、全体の締切りに間に合わないということが起こりうる。
【００１８】
従って、複数のタスクを効率良く分散して実行するためには、計算効率と一部のタスクの早期終了とのトレードオフを取りながら、各タスクに適切な計算資源を割り当てる必要がある。つまり、依存関係のある複数のタスクがワークフローとして与えられたときは、タスクに割当てるコア数が少ない方が計算効率は高く、タスクに割当てるコア数が多い方が実行終了時刻は早くなることを鑑みつつ、各タスクへ計算資源を割り当て、その実行順序を決定する必要がある。
【００１９】
ここで、具体例を挙げて説明する。図１は、依存関係のある複数のタスクの一例を示す図である。図１に示すように、複数のタスクとタスク間の依存関係が、ワークフローの形で与えられている。ワークフローは、タスクの集合Ｗ＝｛１，２，・・・，ｎ｝と、集合Ｗの各要素ｗとに対する、タスク間の依存関係を表すＷの部分集合Ｐｗによって表現される。
【００２０】
図１の例では、集合Ｗ＝｛１，２，３，４｝であり、部分集合Ｐ１＝｛｝、Ｐ２＝｛１｝、Ｐ３＝｛１｝、Ｐ４＝｛２｝である。これは、タスク２はタスク１が終わるまで計算を開始できず、タスク４はタスク２の計算が終了するまで計算が開始できない、ということを表している。
【００２１】
例えば、需要予測のワークフローにおいて、タスクｗ１は予測に用いる特徴量抽出タスク、タスクｗ２は翌日の需要予測タスク、タスクｗ３は本日の需要予測タスク、タスクｗ４は翌日の需要予測に基づく価格戦略最適化タスクに相当するとする。
【００２２】
そして、各タスクｗに対して、デッドライン時刻（実行期限）ｄｗが与えられているとする。なお、実行期限が指定されていない場合には、ｄｗとしては、十分に大きな数∞が与えられる。図１の例において、タスク３と４の実行期限が１０[min]、１５[min]と与えられているとすると、ｄ１＝ｄ２＝∞、ｄ３＝１０、ｄ４＝１５というように定められる。
【００２３】
各タスクに対して、計算資源x_wを与えられたときの計算時間f(x_w)が与えられているとする。なお、以下においては、説明のため、計算資源x_wはＣＰＵ（Central Processing Unit）のコア数のみとするが、本発明において、計算資源はコア数のみに限定されることはない。
【００２４】
また、コア数と計算時間との関係は、例えば図２に示す通りとなる。図２は、計算資源と計算時間との関係の一例を示す図である。図２の例では、あるタスクの計算時間は、コア数の違いにより、ｆ（４）＝５０、ｆ（８）＝４８となる。これは、このタスクに４コアを用いた場合の計算時間が５０秒で、８コアを用いた場合の計算時間が４８秒であることを意味している。また、図２に示された計算時間は、過去のデータに基づいて推定される。この計算時間の推定について、更に説明する。
【００２５】
例えば、クラスタシステムが毎週同じ計算を実行しているが、計算の中身が違うという場合には、過去にかかった計算時間に基づいて、最新の計算時間を推定することができる。また、機械学習エンジンを用いて、毎週、異なるデータに基づいて推定処理が行なわれる場合を想定する。通常、機械学習エンジンが用いられる場合は、データの詳細な内容ではなく、データ量に依存して計算時間が決定される。よって、データ量とコア数との様々な組合せを想定して、機械学習エンジンを予め動かしておくことで、コア数に応じた計算時間を推定することができる。なお、このような推定には、十分な時間が使える状況にあることが必要となる。
【００２６】
ここで、図３〜図６を用いて、図１に示した各タスクへの最適なコアの割当てと最適な各タスクの実行開始時刻について説明する。また、図３〜図６の例において、使用可能なコア数の合計は４コアであるとする。図３は、コアの割当ての第１の例を示す図である。図４は、コアの割当ての第２の例を示す図である。図５は、コアの割当ての第３の例を示す図である。図６は、コアの割当ての第４の例を示す図である。なお、各図において、上段には、タスクの実行順序を示すグラフが表示されている。
【００２７】
図３の例では、タスクｗ１、ｗ３、ｗ２、ｗ４の順に、各タスクに４コア全てが用いられて計算が行なわれている。これに対して、図４の例では、まずタスクｗ１が４コアで計算され、次に、タスクｗ２及びｗ３をそれぞれが２コアで計算され、タスクｗ２の計算の終了後に、タスクｗ４が２コアで計算されている。
【００２８】
図３及び図４から分かるよう、一般に、コア数が１の時に比べて、コア数をｘとした時に、計算時間が１／ｘのオーダーで短縮されるわけではない。これは、複数のコアでタスクを実行する場合には、並列化できない逐次処理及びデータ通信等を行なう必要があるからである。従って、１コア当りの計算効率は、一般に少ないコア数でタスクを計算した方が良い結果となる。このことから、図５に示すように、１コアを最小単位とした場合は、１コア当りの計算効率は最も良くなり、逆に図３の例では、１コア当りの計算効率は最も悪くなる。
【００２９】
一方で、既に確保されている計算資源を余らせるのは無駄である。更に、図５の例では、タスクに設定されている実行期限が満たされない事態となっている。従って、計算効率と実行期限の遵守との両方の点からは、図４又は図６に示すように各タスクにコアを割当てるのが理想的である。図４の例では、最終終了時刻（タスク４の終了時刻）が最速であり、図６の例では、最終終了時刻は最速とはならないが、高い計算効率を維持しつつ、最終終了時刻までのマージンを十分に確保できる。本発明においては、このようなスケジュールを求めることができる。
【００３０】
（実施の形態）
以下、本発明の実施の形態における、計算資源管理装置、計算資源管理方法及びコンピュータ読み取り可能な記録媒体について、図７〜図１１を参照しながら説明する。
【００３１】
［装置構成］
最初に、本実施の形態における計算資源管理装置の構成について図７を用いて説明する。図７は、本発明の実施の形態における計算資源管理装置の概略構成を示すブロック図である。
【００３２】
図７に示す本実施の形態における計算資源管理装置１０は、複数のタスクを実行するクラスタシステム２０を管理するための装置である。図１に示すように、計算資源管理装置１０は、条件特定部１１と、スケジューリング部１２とを備えている。
【００３３】
条件特定部１１は、クラスタシステム２０の計算資源と計算時間との関係、複数のタスクそれぞれ間の依存関係、及び複数のタスクそれぞれの実行期限を特定する。スケジューリング部１２は、特定された計算資源と計算時間との関係、タスク間の依存関係に基づいて、タスク毎に、実行期限が守られるように、実行順序、及びクラスタシステム２０の計算資源のうちの割当てるべき計算資源を決定する。
【００３４】
このように、計算資源管理装置１０は、計算資源と計算時間との関係、タスク間の依存関係、及び各タスクの実行期限に基づいて、タスクのスケジューリングを行なう。このため、本実施の形態では、依存関係のある複数のタスクを実行する場合に、依存関係を踏まえて各タスクに割当てる計算資源を最適化することができる。
【００３５】
続いて、図８を用いて、計算資源管理装置１０の構成を更に具体的に説明する。図８は、本発明の実施の形態における計算資源管理装置の具体的構成を示すブロック図である。
【００３６】
図８に示すように、本実施の形態において、条件特定部１１は、外部から、クラスタシステム２０の計算資源と計算時間との関係、タスク間の依存関係、及び各タスクの実行期限を取得する。具体的には、これらの情報が、外部の端末装置から送信されてくる場合は、条件特定部１１は、送信されてきた情報を取得する。また、これらの情報が、キーボード等の入力機器によって入力される場合は、入力された情報を取得する。また、条件特定部１１は、取得した情報をスケジューリング部１２に渡す。
【００３７】
スケジューリング部１２は、本実施の形態では、実行順序決定部１３と、割当部１４と、判定部１５とを備えている。
【００３８】
実行順序決定部１３は、タスク間の依存関係及びタスク毎の実行期限に基づいて、各タスクの実行順序を決定する。割当部１４は、実行順序決定部１３が決定した実行順序の元で、各タスクへの任意の計算資源の割当てを実行する。
【００３９】
また、スケジューリング部１２において、実行順序決定部１３による決定処理と、割当部１４による割当て処理とは、一連の処理として複数回行なわれる。その後、判定部１５は、一連の処理の結果に基づき、タスク毎に、実行順序、及び割当てるべき計算資源を決定する。
【００４０】
具体的には、スケジューリング部１２において、実行順序決定部１３が、まず、各タスクについて初期の実行順序を決定し、その上で、割当部１４が、各タスクにコアを割当てる。続いて、実行順序決定部１３は、各タスクの実行順序を変更する。また、割当部１４は、変更後の実行順序を踏まえて、コア数を変更する。つまり、スケジューリング部１２において、複数回、スケジューリングが実行される。
【００４１】
判定部１５は、一連の処理が実行されると、その度に、各タスクが実行期限内に完了するかどうかを判定し、この判定結果に基づいて、最終的な各タスクの実行順序と割当てるコア数とを決定する。更に、判定部１５は、各タスクが実行期限内に完了していると判定された一連の処理のうち、各タスクの実行終了時刻が設定条件を満たす一連の処理を選択することができる。
【００４２】
また、本実施の形態では、計算資源管理装置１０は、上述した条件特定部１１とスケジューリング部１２とに加えて、出力部１６も備えている。出力部１６は、スケジューリングの結果を可視化するためのデータを作成し、作成したデータを、外部の端末装置に送信する。また、出力部１６は、スケジューリングの結果を、表示装置の画面上で可視化することもできる。
【００４３】
また、本実施の形態では、クラスタシステム２０の計算資源と計算時間との関係としては、例えば、タスク毎のコア数と計算時間との関係が挙げられる。コア数と計算時間との関係の具体例については図１０を用いて後述する。
【００４４】
［装置動作］
次に、本発明の実施の形態における計算資源管理装置１０の動作について図９を用いて説明する。図９は、本発明の実施の形態における計算資源管理装置の動作を示すフロー図である。以下の説明においては、適宜図７及び図８を参酌する。また、本実施の形態では、計算資源管理装置を動作させることによって、計算資源管理方法が実施される。よって、本実施の形態における計算資源管理方法の説明は、以下の計算資源管理装置１０の動作説明に代える。
【００４５】
図９に示すように、最初に、条件特定部１１が、外部から、クラスタシステム２０の計算資源と計算時間との関係、タスク間の依存関係、及び各タスクの実行期限を取得し、これらを特定する（ステップＡ１）。具体的には、条件特定部１１は、図２に示した計算資源と計算時間との関係、図１に示したタスク間の依存関係、図１に示した実行期限（ｄ１＝ｄ２＝∞、ｄ３＝１０、ｄ４＝１５）を特定する。
【００４６】
ここで、計算資源としてコア数が用いられ、総コア数をＣとし、ｘｗをタスクｗに割り当てるコア数とする。また、タスクｗが終了する計算時間をｔｗとする。σを置換とし、σ（ｗ）がｗの計算が終わる順序を表し、このとき、σの定義から下記の数１が成立するとする。置換とは、１，２、、、、ｎの並び替えをあらわす。とくに、ここでは、σ（ｗ）＝iだった場合に、タスクｗはi番目に計算が終了することを意味する。
【００４７】
【数１】
2018198745.tif 000003
【００４８】
但し、上記数１において、ｔ０は便宜上の、計算開始時刻である。また、π（ｗ）によって、タスクｗを計算し始める直前のタスクを表す。このとき、下記の数２が定義から成立する。これは、タスクｗの計算終了順序σ（ｗ）は、直前のタスクπ（ｗ）の計算終了順序σ（π（ｗ））より大きいことを意味する。
【００４９】
【数２】
2018198745.tif 000004
【００５０】
また、タスクの依存関係に関する制約から、すべてのタスクｗとＰｗの要素ｐに対して、下記の数３が成立する。
【００５１】
【数３】
2018198745.tif 000005
【００５２】
上記数３は、タスクｗの計算が実行される直前のタスクπ（ｗ）の計算終了順序は、いかなる先行タスクｐの計算終了の順序以上でなくてはならないという性質を示している。
【００５３】
次に、スケジューリング部１２において、実行順序決定部１３が、まず、各タスクについて実行順序を決定する（ステップＡ２）。
【００５４】
具体的には、ステップＡ２では、スケジューリング部１２は、既に処理が行なわれている場合は、初期の実行順序として、前回の処理で決定されたσとπとを用いる。一方、未だ処理が何も行なわれていない状態においては、スケジューリング部１２は、以下のように、初期の実行順序としてσとπを計算する。
【００５５】
まず、実行順序決定部１３は、最も実行期限が早いタスクｗ１（図１参照）を選び、ｗ１の実行開始時刻より前に計算が終了していなければならないタスクを、依存関係を満たすようにｗ１１、ｗ１２、、、、ｗ１ｎ１、ｗ１として並べる。
【００５６】
同様に、実行順序決定部１３は、まだ選ばれていないタスクの中でもっとも実行期限が早いタスクをｗ２として、それよりも前に計算が終了していなければならないタスクを、依存関係を満たすように、ｗ２１、、、、ｗ２ｎ２、ｗ２、として並べる。
【００５７】
以上の結果、実行順序決定部１３は、タスクの優先順位の列ｗ１１、、、、ｗ１ｎ１、ｗ１、ｗ２１、、、、ｗ２、ｗ３１、、、、ｗ３、、、、を得る。そして、実行順序決定部１３は、この順に、優先順位を割り振り、σ（ｗ１１）＝１、σ（ｗ１２）＝２、、、、と設定する。また、実行順序決定部１３は、πを一つ前のタスクに割り当てる。これにより、σとπの初期値が得られる。
【００５８】
次に、スケジューリング部１２において、割当部１４が、ステップＡ２で決定された実行順序に基づいて、各タスクにコアを割当てる（ステップＡ３）。次に、スケジューリング部１２は、繰り返し処理の終了条件が満たされているかどうかを判定し、満たされていない場合は、再度ステップＡ２を実行し、満たされている場合は、ステップＡ５を実行する。なお、終了条件としては、ステップＡ２及びＡ３が予め設定された回数行なわれたこと、全てのタスクが実行期限内に完了したこと、等が挙げられる。
【００５９】
ここで、ステップＡ３について具体的に説明する。まず、実行順序が決定されると、コア数とタスク間の依存関係とには、以下の数４の線形不等式によって表される制約が存在する。
【００６０】
【数４】
2018198745.tif 000006
【００６１】
上記数４において、Ｗ（ｗ，σ、π）は同時に計算されるワークフローの集合であり、swは各タスクｗに対応する新たな変数である。これらの制約の元では、下記の数５に示す最終終了時間、及び後述するマージンｓを最適化する問題は、線形整数計画問題として定式化される。
【００６２】
【数５】
2018198745.tif 000007
【００６３】
そして、割当部１４は、ステップＡ２で決定された実行順序と、上記数４に示した制約の下で、タスク毎に、割当てるコア数と、計算時間とを算出する。このとき、ワークフローＷにおいて、タスクｗの終了時刻と、タスクπ（ｗ）の終了時刻が一致するとする。つまり、下記の数６又は数７が成立するとする。
【００６４】
【数６】
2018198745.tif 000008
【００６５】
【数７】
2018198745.tif 000009
【００６６】
この場合においては、i番目に終了するタスクとｉ＋１番目に終了するタスクとは終了時刻が等しく、本当は、ｉ＋１番目のタスクの計算は最早くに終了できるが、順序の制約を満たすために、ｉ＋１番目のタスクの計算を待機させている、ということが成立する。
【００６７】
従って、このようなワークフローＷにおいて、タスクπ（ｗ）を、このタスクπ（ｗ）より終了時刻が早いタスクに入れ替える、つまりσ−１(σ（π（ｗ））−１)にする、またはσ−１(ｉ)とσ−１(ｉ＋１)とを入れ替えることで、解が改善されることが期待される。このため、次のステップＡ２では、実行順序決定部１３は、タスクの入れ替えを行って、各タスクの実行順序を決定する。
【００６８】
また、再度のステップＡ２において、入れ替え対象となるタスクの選び方は、特に限定されるものではない。例えば、実行順序決定部１３は、コア効率、つまりｆｗ（ｘｗ）／ｆｗ（１）が、最も低いタスクｗを選択し、選択したタスクｗのσ又はπを上述した方法で変更する。
【００６９】
ステップＡ５では、判定部１５は、最終的な各タスクの実行順序と割当てるコア数とを決定する。具体的には、判定部１５は、ステップＡ２及びＡ３が実行される度に、各タスクが実行期限内に完了するかどうかを判定する。そして、判定部１５は、得られた各判定結果に基づいて、最終的な各タスクの実行順序と割当てるコア数とを決定する。
【００７０】
その後、出力部１６が、ステップＡ１〜Ａ５までの処理で得られたスケジューリングの結果を外部に出力する（ステップＡ６）。以上により、計算資源管理装置１０における処理は終了する。
【００７１】
［具体例］
続いて、本実施の形態における具体例について説明する。まず、図９に示したステップＡ１において、図１に示したタスク間の依存関係と、図１に示した実行期限（ｄ１＝ｄ２＝∞、ｄ３＝１０、ｄ４＝１３）とが与えられているとする。
【００７２】
また、クラスタシステムの全コア数は４コアであり、タスク毎の計算資源（コア）と計算時間との関係として、図１０に示すテーブルが与えられているとする。図１０は、本発明の実施の形態における具体例で用いられる計算資源と計算時間との関係を示す図である。図１０の例では、各タスクに割当てられたコア数が、１、２、３、４である場合の計算時間が示されている。
【００７３】
次に、ステップＡ２において、実行順序決定部１３が、例えば、タスク１、３、２、４の順に、各タスクの初期の実行順序を決定する。この場合、σ（１）＝１、σ（３）＝２、σ（２）＝３、σ（４）＝４となる。これに対し、π（１）＝０、π（３）＝１、π（２）＝３、π（４）＝２となる。これらの初期値は、図５の上段のグラフに対応する。
【００７４】
また、この場合において、コア数を最終の終了時刻に対して最適化すると、全てのタスクに４コアを割り当てるのが最適となることから、割当部１４は、図５の下段に示すように各タスクにコアを割当てる。各タスクの開始時をゼロとした終了時間を、ｔ１、ｔ２、ｔ３、ｔ４とすると、ｔ１＝４秒、ｔ２＝１１秒、ｔ３＝９秒、ｔ４＝１４秒となる。なお、この場合、タスク４の実行期限が満たされていない結果となる。
【００７５】
ここで、タスク１、３、４に関しては、σ及びπの値を、制約を崩すことなく変更することはできないため、タスク２について検討する。すると、タスク２のπの値のみ変更可能であることから、実行順序決定部１３は、π（２）＝１、つまり、タスク２の直前のタスクを３から１に変更する。この変更により、各タスクの実行順序は、図６の上段に示した通りとなる。
【００７６】
この変更の後に、割当部１４が、各タスクに割当てるコアの数を最適化すると、図６の下段に示す通りとなる。この場合、ｔ１＝４秒、ｔ２＝９秒、ｔ３＝９秒、ｔ４＝１２秒となる。
【００７７】
この場合、タスク２とタスク３についてｔ２＝ｔ３が成立する。但し、タスク２の実際の計算時間（ｆ２（１））は４秒（図１０参照）であるのに対して、図６において、タスク２の計算時間は５秒となっている。これは、各タスクの実行順序による制約（図６の上段）から、タスク２はタスク３より後に終了する必要があるからである。従って、実行順序決定部１３は、この制約を排除し、σ（２）とσ（３）とを入れ替える。
【００７８】
この入れ替えの後、各タスクの実行順序は、図４の上段に示した通りとなる。また、各タスクに割当てるコアの数を最適化すると、図４の下段に示した通りとなる。図４の下段の例では、最終の終了時刻が最短となり、ｔ１＝４秒、ｔ２＝７秒、ｔ３＝１０秒、ｔ４＝１１秒となる。
【００７９】
また、判定部１５は、各タスクが実行期限内に完了していると判定された一連の処理のうち、各タスクの実行終了時刻が設定条件を満たす一連の処理を選択する。例えば、最終の終了時刻からのマージンを最大化したい場合は、図６の下段の例が最適解となるので、判定部１５は、図６の下段の例に示された実行順序及び計算資源に決定する。
【００８０】
以上のように、本実施の形態では、計算資源管理装置１０は、最適化の目的変数を変更し、そして、反復処理の中から最良の結果を選択する。このため、依存関係のある複数のタスクを実行する場合に、依存関係を踏まえて各タスクに割当てる計算資源を最適化することができる。
【００８１】
［プログラム］
本実施の形態におけるプログラムは、コンピュータに、図９に示すステップＡ１〜Ａ６を実行させるプログラムであれば良い。このプログラムをコンピュータにインストールし、実行することによって、本実施の形態における計算資源管理装置１０と計算資源管理方法とを実現することができる。この場合、コンピュータのＣＰＵ（Central Processing Unit）は、条件特定部１１、スケジューリング部１２、及び出力部１６として機能し、処理を行なう。
【００８２】
また、本実施の形態におけるプログラムは、複数のコンピュータによって構築されたコンピュータシステムによって実行されても良い。この場合は、例えば、各コンピュータが、それぞれ、条件特定部１１、スケジューリング部１２、及び出力部１６のいずれかとして機能しても良い。
【００８３】
ここで、本実施の形態におけるプログラムを実行することによって、計算資源管理装置１０を実現するコンピュータについて図１１を用いて説明する。図１１は、本発明の実施の形態における計算資源管理装置を実現するコンピュータの一例を示すブロック図である。
【００８４】
図１１に示すように、コンピュータ１１０は、ＣＰＵ１１１と、メインメモリ１１２と、記憶装置１１３と、入力インターフェイス１１４と、表示コントローラ１１５と、データリーダ／ライタ１１６と、通信インターフェイス１１７とを備える。これらの各部は、バス１２１を介して、互いにデータ通信可能に接続される。
【００８５】
ＣＰＵ１１１は、記憶装置１１３に格納された、本実施の形態におけるプログラム（コード）をメインメモリ１１２に展開し、これらを所定順序で実行することにより、各種の演算を実施する。メインメモリ１１２は、典型的には、ＤＲＡＭ（Dynamic Random Access Memory）等の揮発性の記憶装置である。また、本実施の形態におけるプログラムは、コンピュータ読み取り可能な記録媒体１２０に格納された状態で提供される。なお、本実施の形態におけるプログラムは、通信インターフェイス１１７を介して接続されたインターネット上で流通するものであっても良い。
【００８６】
また、記憶装置１１３の具体例としては、ハードディスクドライブの他、フラッシュメモリ等の半導体記憶装置が挙げられる。入力インターフェイス１１４は、ＣＰＵ１１１と、キーボード及びマウスといった入力機器１１８との間のデータ伝送を仲介する。表示コントローラ１１５は、ディスプレイ装置１１９と接続され、ディスプレイ装置１１９での表示を制御する。
【００８７】
データリーダ／ライタ１１６は、ＣＰＵ１１１と記録媒体１２０との間のデータ伝送を仲介し、記録媒体１２０からのプログラムの読み出し、及びコンピュータ１１０における処理結果の記録媒体１２０への書き込みを実行する。通信インターフェイス１１７は、ＣＰＵ１１１と、他のコンピュータとの間のデータ伝送を仲介する。
【００８８】
また、記録媒体１２０の具体例としては、ＣＦ（Compact Flash（登録商標））及びＳＤ（Secure Digital）等の汎用的な半導体記憶デバイス、フレキシブルディスク（Flexible Disk）等の磁気記録媒体、又はＣＤ−ＲＯＭ（Compact Disk Read Only Memory）などの光学記録媒体が挙げられる。
【００８９】
なお、本実施の形態における計算資源管理装置１０は、プログラムがインストールされたコンピュータではなく、各部に対応したハードウェアを用いることによっても実現可能である。更に、計算資源管理装置１０は、一部がプログラムで実現され、残りの部分がハードウェアで実現されていてもよい。
【００９０】
上述した実施の形態の一部又は全部は、以下に記載する（付記１）〜（付記１２）によって表現することができるが、以下の記載に限定されるものではない。
【００９１】
（付記１）
複数のタスクを実行するクラスタシステムを管理するための装置であって、
前記クラスタシステムの計算資源と計算時間との関係、前記複数のタスクそれぞれ間の依存関係、及び前記複数のタスクそれぞれの実行期限を特定する、条件特定部と、
特定された前記関係、前記依存関係に基づいて、前記複数のタスクそれぞれ毎に、前記実行期限が守られるように、実行順序、及び前記クラスタシステムの計算資源のうちの割当てるべき計算資源を決定する、スケジューリング部と、
を備えている、
ことを特徴とする計算資源管理装置。
【００９２】
（付記２）
前記スケジューリング部が、
前記依存関係及び前記実行期限に基づいた、前記複数のタスクそれぞれの実行順序の決定処理と、決定された前記実行順序の元での、前記複数のタスクそれぞれへの任意の計算資源の割当て処理とを、一連の処理として複数回行なって、
前記複数のタスクそれぞれ毎に、実行順序、及び前記クラスタシステムの計算資源のうちの割当てるべき計算資源を決定する、
付記１に記載の計算資源管理装置。
【００９３】
（付記３）
前記スケジューリング部が、
前記複数のタスクそれぞれが前記実行期限内に完了している前記一連の処理のうち、前記複数のタスクそれぞれの実行終了時刻が設定条件を満たす一連の処理を選択し、
選択した一連の処理における前記決定処理及び前記割当て処理の結果を用いて、前記複数のタスクそれぞれ毎に、実行順序、及び前記クラスタシステムの計算資源のうちの割当てるべき計算資源を決定する、
付記２に記載の計算資源管理装置。
【００９４】
（付記４）
前記関係が、前記複数のタスクそれぞれ毎のコア数と計算時間との関係である、
付記１〜３のいずれかに記載の計算資源管理装置。
【００９５】
（付記５）
複数のタスクを実行するクラスタシステムを管理するための方法であって、
（ａ）前記クラスタシステムの計算資源と計算時間との関係、前記複数のタスクそれぞれ間の依存関係、及び前記複数のタスクそれぞれの実行期限を特定する、ステップと、
（ｂ）前記（ａ）のステップで特定された前記関係、前記依存関係に基づいて、前記複数のタスクそれぞれ毎に、前記実行期限が守られるように、実行順序、及び前記クラスタシステムの計算資源のうちの割当てるべき計算資源を決定する、ステップと、
を有する、
ことを特徴とする計算資源管理方法。
【００９６】
（付記６）
前記（ｂ）のステップにおいて、
前記依存関係及び前記実行期限に基づいた、前記複数のタスクそれぞれの実行順序の決定処理と、決定された前記実行順序の元での、前記複数のタスクそれぞれへの任意の計算資源の割当て処理とを、一連の処理として複数回行なって、
前記複数のタスクそれぞれ毎に、実行順序、及び前記クラスタシステムの計算資源のうちの割当てるべき計算資源を決定する、
付記５に記載の計算資源管理方法。
【００９７】
（付記７）
前記（ｂ）のステップにおいて、
前記複数のタスクそれぞれが前記実行期限内に完了している前記一連の処理のうち、前記複数のタスクそれぞれの実行終了時刻が設定条件を満たす一連の処理を選択し、
選択した一連の処理における前記決定処理及び前記割当て処理の結果を用いて、前記複数のタスクそれぞれ毎に、実行順序、及び前記クラスタシステムの計算資源のうちの割当てるべき計算資源を決定する、
付記６に記載の計算資源管理方法。
【００９８】
（付記８）
前記関係が、前記複数のタスクそれぞれ毎のコア数と計算時間との関係である、
付記５〜７のいずれかに記載の計算資源管理方法。
【００９９】
（付記９）
コンピュータによって、複数のタスクを実行するクラスタシステムを管理するためのプログラムを記録したコンピュータ読み取り可能な記録媒体であって、
前記コンピュータに、
（ａ）前記クラスタシステムの計算資源と計算時間との関係、前記複数のタスクそれぞれ間の依存関係、及び前記複数のタスクそれぞれの実行期限を特定する、ステップと、
（ｂ）前記（ａ）のステップで特定された前記関係、前記依存関係に基づいて、前記複数のタスクそれぞれ毎に、前記実行期限が守られるように、実行順序、及び前記クラスタシステムの計算資源のうちの割当てるべき計算資源を決定する、ステップと、
を実行させる命令を含む、プログラムを記録しているコンピュータ読み取り可能な記録媒体。
【０１００】
（付記１０）
前記（ｂ）のステップにおいて、
前記依存関係及び前記実行期限に基づいた、前記複数のタスクそれぞれの実行順序の決定処理と、決定された前記実行順序の元での、前記複数のタスクそれぞれへの任意の計算資源の割当て処理とを、一連の処理として複数回行なって、
前記複数のタスクそれぞれ毎に、実行順序、及び前記クラスタシステムの計算資源のうちの割当てるべき計算資源を決定する、
付記９に記載のコンピュータ読み取り可能な記録媒体。
【０１０１】
（付記１１）
前記（ｂ）のステップにおいて、
前記複数のタスクそれぞれが前記実行期限内に完了している前記一連の処理のうち、前記複数のタスクそれぞれの実行終了時刻が設定条件を満たす一連の処理を選択し、
選択した一連の処理における前記決定処理及び前記割当て処理の結果を用いて、前記複数のタスクそれぞれ毎に、実行順序、及び前記クラスタシステムの計算資源のうちの割当てるべき計算資源を決定する、
付記１０に記載のコンピュータ読み取り可能な記録媒体。
【０１０２】
（付記１２）
前記関係が、前記複数のタスクそれぞれ毎のコア数と計算時間との関係である、
付記９〜１１のいずれかに記載のコンピュータ読み取り可能な記録媒体。
【０１０３】
以上、実施の形態を参照して本願発明を説明したが、本願発明は上記実施の形態に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【０１０４】
この出願は、２０１７年４月２７日に出願された米国出願６２／４９０８９５を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【産業上の利用可能性】
【０１０５】
以上のように本発明によれば、依存関係のある複数のタスクを実行する場合に、依存関係を踏まえて各タスクに割当てる計算資源を最適化することができる。本発明は、例えば、クラスタシステムに有用である。
【符号の説明】
【０１０６】
１０  計算資源管理装置
１１  条件特定部
１２  スケジューリング部
１３  実行順序決定部
１４  割当部
１５  判定部
１６  出力部
２０  クラスタシステム
１１０  コンピュータ
１１１  ＣＰＵ
１１２  メインメモリ
１１３  記憶装置
１１４  入力インターフェイス
１１５  表示コントローラ
１１６  データリーダ／ライタ
１１７  通信インターフェイス
１１８  入力機器
１１９  ディスプレイ装置
１２０  記録媒体
１２１  バス
【図１】
2018198745.tif 000010
【図２】
2018198745.tif 000011
【図３】
2018198745.tif 000012
【図４】
2018198745.tif 000013
【図５】
2018198745.tif 000014
【図６】
2018198745.tif 000015
【図７】
2018198745.tif 000016
【図８】
2018198745.tif 000017
【図９】
2018198745.tif 000018
【図１０】
2018198745.tif 000019
【図１１】
2018198745.tif 000020
【手続補正書】
【提出日】令和1年10月24日(2019.10.24)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数のタスクを実行するクラスタシステムを管理するための装置であって、
前記クラスタシステムの計算資源と計算時間との関係、前記複数のタスクそれぞれ間の依存関係、及び前記複数のタスクそれぞれの実行期限を特定する、条件特定部と、
特定された前記関係、前記依存関係に基づいて、前記複数のタスクそれぞれ毎に、前記実行期限が守られるように、実行順序、及び前記クラスタシステムの計算資源のうちの割当てるべき計算資源を決定する、スケジューリング部と、
を備えている、
ことを特徴とする計算資源管理装置。
【請求項２】
前記スケジューリング部が、
前記依存関係及び前記実行期限に基づいた、前記複数のタスクそれぞれの実行順序の決定処理と、決定された前記実行順序の元での、前記複数のタスクそれぞれへの任意の計算資源の割当て処理とを、一連の処理として複数回行なって、
前記複数のタスクそれぞれ毎に、実行順序、及び前記クラスタシステムの計算資源のうちの割当てるべき計算資源を決定する、
請求項１に記載の計算資源管理装置。
【請求項３】
前記スケジューリング部が、
前記複数のタスクそれぞれが前記実行期限内に完了している前記一連の処理のうち、前記複数のタスクそれぞれの実行終了時刻が設定条件を満たす一連の処理を選択し、
選択した一連の処理における前記決定処理及び前記割当て処理の結果を用いて、前記複数のタスクそれぞれ毎に、実行順序、及び前記クラスタシステムの計算資源のうちの割当てるべき計算資源を決定する、
請求項２に記載の計算資源管理装置。
【請求項４】
前記関係が、前記複数のタスクそれぞれ毎のコア数と計算時間との関係である、
請求項１〜３のいずれかに記載の計算資源管理装置。
【請求項５】
複数のタスクを実行するクラスタシステムを管理するための方法であって、
（ａ）前記クラスタシステムの計算資源と計算時間との関係、前記複数のタスクそれぞれ間の依存関係、及び前記複数のタスクそれぞれの実行期限を特定する、ステップと、
（ｂ）前記（ａ）のステップで特定された前記関係、前記依存関係に基づいて、前記複数のタスクそれぞれ毎に、前記実行期限が守られるように、実行順序、及び前記クラスタシステムの計算資源のうちの割当てるべき計算資源を決定する、ステップと、
を有する、
ことを特徴とする計算資源管理方法。
【請求項６】
前記（ｂ）のステップにおいて、
前記依存関係及び前記実行期限に基づいた、前記複数のタスクそれぞれの実行順序の決定処理と、決定された前記実行順序の元での、前記複数のタスクそれぞれへの任意の計算資源の割当て処理とを、一連の処理として複数回行なって、
前記複数のタスクそれぞれ毎に、実行順序、及び前記クラスタシステムの計算資源のうちの割当てるべき計算資源を決定する、
請求項５に記載の計算資源管理方法。
【請求項７】
前記（ｂ）のステップにおいて、
前記複数のタスクそれぞれが前記実行期限内に完了している前記一連の処理のうち、前記複数のタスクそれぞれの実行終了時刻が設定条件を満たす一連の処理を選択し、
選択した一連の処理における前記決定処理及び前記割当て処理の結果を用いて、前記複数のタスクそれぞれ毎に、実行順序、及び前記クラスタシステムの計算資源のうちの割当てるべき計算資源を決定する、
請求項６に記載の計算資源管理方法。
【請求項８】
前記関係が、前記複数のタスクそれぞれ毎のコア数と計算時間との関係である、
請求項５〜７のいずれかに記載の計算資源管理方法。
【請求項９】
コンピュータによって、複数のタスクを実行するクラスタシステムを管理するためのプログラムであって、
前記コンピュータに、
（ａ）前記クラスタシステムの計算資源と計算時間との関係、前記複数のタスクそれぞれ間の依存関係、及び前記複数のタスクそれぞれの実行期限を特定する、ステップと、
（ｂ）前記（ａ）のステップで特定された前記関係、前記依存関係に基づいて、前記複数のタスクそれぞれ毎に、前記実行期限が守られるように、実行順序、及び前記クラスタシステムの計算資源のうちの割当てるべき計算資源を決定する、ステップと、
を実行させる命令を含むプログラム。
【請求項１０】
前記（ｂ）のステップにおいて、
前記依存関係及び前記実行期限に基づいた、前記複数のタスクそれぞれの実行順序の決定処理と、決定された前記実行順序の元での、前記複数のタスクそれぞれへの任意の計算資源の割当て処理とを、一連の処理として複数回行なって、
前記複数のタスクそれぞれ毎に、実行順序、及び前記クラスタシステムの計算資源のうちの割当てるべき計算資源を決定する、
請求項９に記載のプログラム。
【請求項１１】
前記（ｂ）のステップにおいて、
前記複数のタスクそれぞれが前記実行期限内に完了している前記一連の処理のうち、前記複数のタスクそれぞれの実行終了時刻が設定条件を満たす一連の処理を選択し、
選択した一連の処理における前記決定処理及び前記割当て処理の結果を用いて、前記複数のタスクそれぞれ毎に、実行順序、及び前記クラスタシステムの計算資源のうちの割当てるべき計算資源を決定する、
請求項１０に記載のプログラム。
【請求項１２】
前記関係が、前記複数のタスクそれぞれ毎のコア数と計算時間との関係である、
請求項９〜１１のいずれかに記載のプログラム。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０００１
【補正方法】変更
【補正の内容】
【０００１】
本発明は、複数のタスクを実行するクラスタリングシステムにおいて、各タスクへの計算資源の割当を最適化するための、計算資源管理装置、及び計算資源管理方法に関し、更には、これらを実現するためのプログラムに関する。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００１０
【補正方法】変更
【補正の内容】
【００１０】
本発明の目的の一例は、上記問題を解消し、依存関係のある複数のタスクを実行する場合に、依存関係を踏まえて各タスクに割当てる計算資源を最適化し得る、計算資源管理装置、計算資源管理方法、及びプログラムを提供することにある。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００１３
【補正方法】変更
【補正の内容】
【００１３】
更に、上記目的を達成するため、本発明の一側面におけるコンピュータ読み取り可能な記録媒体は、コンピュータによって、複数のタスクを実行するクラスタシステムを管理するためのプログラムであって、
前記コンピュータに、
（ａ）前記クラスタシステムの計算資源と計算時間との関係、前記複数のタスクそれぞれ間の依存関係、及び前記複数のタスクそれぞれの実行期限を特定する、ステップと、
（ｂ）前記（ａ）のステップで特定された前記関係、前記依存関係に基づいて、前記複数のタスクそれぞれ毎に、前記実行期限が守られるように、実行順序、及び前記クラスタシステムの計算資源のうちの割当てるべき計算資源を決定する、ステップと、
を実行させることを特徴とする。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００２２
【補正方法】変更
【補正の内容】
【００２２】
そして、各タスクｗに対して、デッドライン時刻（実行期限）ｄｗが与えられているとする。なお、実行期限が指定されていない場合には、ｄｗとしては、十分に大きな数∞が与えられる。図１の例において、タスク３と４の実行期限が１０[min]、１３[min]と与えられているとすると、ｄ１＝ｄ２＝∞、ｄ３＝１０、ｄ４＝１３というように定められる。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００５５
【補正方法】変更
【補正の内容】
【００５５】
まず、実行順序決定部１３は、最も実行期限が早いタスクｗ１（図１参照）を選び、ｗ１の実行開始時刻より前に計算が終了していなければならないタスクを、依存関係を満たすようにｗ１１、ｗ１２、、、、ｗ１ｎ１、ｗ１として並べる。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】００９９
【補正方法】変更
【補正の内容】
【００９９】
（付記９）
コンピュータによって、複数のタスクを実行するクラスタシステムを管理するためのプログラムであって、
前記コンピュータに、
（ａ）前記クラスタシステムの計算資源と計算時間との関係、前記複数のタスクそれぞれ間の依存関係、及び前記複数のタスクそれぞれの実行期限を特定する、ステップと、
（ｂ）前記（ａ）のステップで特定された前記関係、前記依存関係に基づいて、前記複数のタスクそれぞれ毎に、前記実行期限が守られるように、実行順序、及び前記クラスタシステムの計算資源のうちの割当てるべき計算資源を決定する、ステップと、
を実行させる命令を含むプログラム。
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】０１００
【補正方法】変更
【補正の内容】
【０１００】
（付記１０）
前記（ｂ）のステップにおいて、
前記依存関係及び前記実行期限に基づいた、前記複数のタスクそれぞれの実行順序の決定処理と、決定された前記実行順序の元での、前記複数のタスクそれぞれへの任意の計算資源の割当て処理とを、一連の処理として複数回行なって、
前記複数のタスクそれぞれ毎に、実行順序、及び前記クラスタシステムの計算資源のうちの割当てるべき計算資源を決定する、
付記９に記載のプログラム。
【手続補正１０】
【補正対象書類名】明細書
【補正対象項目名】０１０１
【補正方法】変更
【補正の内容】
【０１０１】
（付記１１）
前記（ｂ）のステップにおいて、
前記複数のタスクそれぞれが前記実行期限内に完了している前記一連の処理のうち、前記複数のタスクそれぞれの実行終了時刻が設定条件を満たす一連の処理を選択し、
選択した一連の処理における前記決定処理及び前記割当て処理の結果を用いて、前記複数のタスクそれぞれ毎に、実行順序、及び前記クラスタシステムの計算資源のうちの割当てるべき計算資源を決定する、
付記１０に記載のプログラム。
【手続補正１１】
【補正対象書類名】明細書
【補正対象項目名】０１０２
【補正方法】変更
【補正の内容】
【０１０２】
（付記１２）
前記関係が、前記複数のタスクそれぞれ毎のコア数と計算時間との関係である、
付記９〜１１のいずれかに記載のプログラム。
【手続補正１２】
【補正対象書類名】図面
【補正対象項目名】図７
【補正方法】変更
【補正の内容】
【図７】
2018198745.tif 000021
【国際調査報告】
2018198745.tif 000022
2018198745.tif 000023
2018198745.tif 000024
2018198745.tif 000025