(57)【要約】【課題】分散システムにおいて、処理サーバをより効率よく利用する技術を提供する。【解決手段】予測時間分布生成装置２０００は、リソース特徴量取得部２０２０、タスク処理時間取得部２０４０、及び予測時間分布生成部２０６０を有する。リソース特徴量取得部２０２０は、処理サーバがタスクを処理した時におけるその処理サーバのリソース特徴量を取得する。タスク処理時間取得部２０４０は、処理サーバがタスクの処理に要した時間である、タスク処理時間を取得する。予測時間分布生成部２０６０は、タスクに関するリソース特徴量及びタスク処理時間の組み合わせに基づき、複数のリソース特徴量それぞれについて予測時間分布を生成する。予測時間分布は、タスクの処理に要するタスク処理時間の予測値の確率分布である。【選択図】図１
2015108877.tif 000002
【特許請求の範囲】
【請求項１】
処理サーバがタスクを処理した時における前記処理サーバのリソース特徴量を取得するリソース特徴量取得手段と、
前記処理サーバが前記タスクの処理に要した時間であるタスク処理時間を取得するタスク処理時間取得手段と、
前記リソース特徴量及び前記タスク処理時間の組み合わせに基づき、複数のリソース特徴量それぞれについて、タスク処理時間の予測値の確率分布である予測時間分布を生成する予測時間分布生成手段と、
を有する予測時間分布生成装置。
【請求項２】
前記予測時間分布生成手段は、前記リソース特徴量に基づく回帰モデルを生成し、さらに前記回帰モデルを条件とする条件付き分布を生成し、その条件付き分布を前記予測時間分布とする請求項１に記載の予測時間分布生成装置。
【請求項３】
前記予測時間分布生成手段は、前記リソース特徴量の値空間を複数の部分空間に分割し、各部分空間に対応付けて、前記リソース特徴量がその部分空間内にある場合における前記予測時間分布を生成する請求項１又は２に記載の予測時間分布生成装置。
【請求項４】
前記予測時間分布生成手段は、所定数の前記タスクの実行が完了する度に、実行が完了した前記タスクに関する前記リソース特徴量及び前記タスク処理時間に基づいて前記予測時間分布を生成する請求項１乃至３いずれか一項に記載の予測時間分布生成装置。
【請求項５】
前記予測時間分布生成手段は、複数のタスク種別それぞれについて、そのタスク種別の前記タスクに関する前記リソース特徴量及び前記タスク処理時間の組み合わせに基づきリソース特徴量ごとの前記予測時間分布を算出する、
請求項１乃至４いずれか一項に記載の予測時間分布生成装置。
【請求項６】
予測時間分布生成装置として動作するコンピュータによって実行させる制御方法であって、
処理サーバがタスクを処理した時における前記処理サーバのリソース特徴量を取得するリソース特徴量取得ステップと、
前記処理サーバが前記タスクの処理に要した時間であるタスク処理時間を取得するタスク処理時間ステップと、
前記リソース特徴量及び前記タスク処理時間の組み合わせに基づき、複数のリソース特徴量それぞれについて、タスク処理時間の予測値の確率分布である予測時間分布を生成する予測時間分布生成ステップと、
を有する制御方法。
【請求項７】
前記予測時間分布生成ステップは、前記リソース特徴量に基づく回帰モデルを生成し、さらに前記回帰モデルを条件とする条件付き分布を生成し、その条件付き分布を前記予測時間分布とする請求項６に記載の制御方法。
【請求項８】
前記予測時間分布生成ステップは、前記リソース特徴量の値空間を複数の部分空間に分割し、各部分空間に対応付けて、前記リソース特徴量がその部分空間内にある場合における前記予測時間分布を生成する請求項６又は７に記載の制御方法。
【請求項９】
前記予測時間分布生成ステップは、所定数の前記タスクの実行が完了する度に、実行が完了した前記タスクに関する前記リソース特徴量及び前記タスク処理時間に基づいて前記予測時間分布を生成する請求項６乃至８いずれか一項に記載の制御方法。
【請求項１０】
前記予測時間分布生成ステップは、複数のタスク種別それぞれについて、そのタスク種別の前記タスクに関する前記リソース特徴量及び前記タスク処理時間の組み合わせに基づきリソース特徴量ごとの前記予測時間分布を算出する、
請求項６乃至９いずれか一項に記載の制御方法。
【請求項１１】
コンピュータに予測時間分布生成装置として動作する機能を持たせるプログラムであって、前記コンピュータに、
処理サーバがタスクを処理した時における前記処理サーバのリソース特徴量を取得するリソース特徴量取得機能と、
前記処理サーバが前記タスクの処理に要した時間であるタスク処理時間を取得するタスク処理時間機能と、
前記リソース特徴量及び前記タスク処理時間の組み合わせに基づき、複数のリソース特徴量それぞれについて、タスク処理時間の予測値の確率分布である予測時間分布を生成する予測時間分布生成機能と、
を持たせるプログラム。
【請求項１２】
前記予測時間分布生成機能は、前記リソース特徴量に基づく回帰モデルを生成し、さらに前記回帰モデルを条件とする条件付き分布を生成し、その条件付き分布を前記予測時間分布とする請求項１１に記載のプログラム。
【請求項１３】
前記予測時間分布生成機能は、前記リソース特徴量の値空間を複数の部分空間に分割し、各部分空間に対応付けて、前記リソース特徴量がその部分空間内にある場合における前記予測時間分布を生成する請求項１１又は１２に記載のプログラム。
【請求項１４】
前記予測時間分布生成機能は、所定数の前記タスクの実行が完了する度に、実行が完了した前記タスクに関する前記リソース特徴量及び前記タスク処理時間に基づいて前記予測時間分布を生成する請求項１１乃至１３いずれか一項に記載のプログラム。
【請求項１５】
前記予測時間分布生成機能は、複数のタスク種別それぞれについて、そのタスク種別の前記タスクに関する前記リソース特徴量及び前記タスク処理時間の組み合わせに基づきリソース特徴量ごとの前記予測時間分布を算出する、
請求項１１乃至１４いずれか一項に記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、予測時間分布生成装置、制御方法、及びプログラムに関する。
【背景技術】
【０００２】
ジョブを分割することで生成された複数のタスクを、複数の計算機（以下、処理サーバ）に分散して実行させる分散システムが開発されている。処理サーバは、タスクを実行できる状態になると、新たなタスクの割り当てを受ける。このような形態の分散システムでは、タスクが終了した処理サーバから順に新たなタスクが割り当てられるため、高速な処理サーバに対してより多くのタスクが割り当てられやすくなる。その結果、ジョブの実行効率が高くなる。
【０００３】
新しいタスクを割当てる処理サーバが複数存在する場合、他の処理サーバより短い時間でタスクを処理できるサーバを選択できれば、ジョブの完了時間をより短縮できる。短い処理時間で処理できるサーバを選択するためには、処理サーバごとにタスクの処理時間を予測する必要がある。
【０００４】
タスクの処理時間の予測又はそれに関連する技術を開示している先行技術文献として、非特許文献１及び特許文献１〜３がある。非特許文献１は、実行中のタスクの処理に要する時間を短くする技術を開示している。具体的には、まず、処理サーバ上で実行されているタスクの処理に要する時間を、１）そのままタスクの実行を続けた場合、及び２）タスクを再実行した場合の２つの場合について算出する。そして、再実行した場合の所要時間の方が短い場合、そのタスクを再実行する。
【０００５】
特許文献１は、負荷分散方法を開示している。この負荷分散方法は、負荷指標として、リソース使用時の待ち時間を除いた純処理時間に対する倍率となる伸長率を計算する。そして、この負荷分散方法は、予測した伸長率がより小さい処理サーバにタスクを割り当てる。
【０００６】
特許文献２は、負荷分散を行う情報処理装置を開示している。この情報処理装置は、タスクが多く消費するリソースを予測し、そのリソースを多く備える処理サーバにタスクを割り当てる。また、この情報処理装置は、既に記録された情報から、新しいタスクが必要とする計算量や消費時間の概算を予測し、この予測値と、各計算機の負荷状況を加味して、新しいタスクをどの計算機に割り振るかを決定する。
【０００７】
特許文献３は、分散システムの需要予測方法を開示している。この方法は、経時的な需要状況の変化の周期期間Ｔｓを定め、実績データから、周期期間Ｔｓにおける経時的な需要状況を表す需要近似簡易関数を求める。さらにこの方法は、周期期間Ｔｓを周期とする需要近似フーリエ級数関数を需要近似簡易関数から求め、需要近似フーリエ級数関数により需要予測をする。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２００１−１０９６３８号公報
【特許文献２】特開２００２−１４０３１３号公報
【特許文献３】特開２００２−２２９９６４号公報
【非特許文献】
【０００９】
【非特許文献１】Ganesh Ananthanarayanan、外６名、「Reining in the Outliers in Map-Reduce Clusters using Mantri」、Proceedings of the 9th USENIX Symposium on Operating Systems Design and Implementation (OSDI '10)、２０１０年１０月４日
【発明の概要】
【発明が解決しようとする課題】
【００１０】
本発明者は、分散システムにおいて、処理サーバをより効率よく利用する方法を検討した。その中で、本発明者は、処理サーバのリソース使用率が同一又は近い値である場合においても、タスクの処理時間にばらつきがあるということに着目した。例えば処理サーバのリソース使用率が高い場合、タスクの処理に長い時間を要する傾向はあるものの、短い時間でタスクの処理が完了することもある。つまり、処理サーバのリソース使用率が高いからといって、その処理サーバがタスクの処理に長い時間を要するとは限らない。前述した各先行技術文献に記載されている技術はいずれも、「リソース使用率が同一又は近い値である場合でもタスクの処理時間にばらつきがある」ということを考慮していない。
【００１１】
本発明は、以上の課題に鑑みてなされたものである。本発明の目的は、分散システムにおいて、処理サーバをより効率よく利用する技術を提供することである。
【課題を解決するための手段】
【００１２】
本発明が提供する予測時間分布生成装置は、処理サーバがタスクを処理した時における前記処理サーバのリソース特徴量を取得するリソース特徴量取得手段と、前記処理サーバが前記タスクの処理に要した時間であるタスク処理時間を取得するタスク処理時間取得手段と、前記リソース特徴量及び前記タスク処理時間の組み合わせに基づき、複数のリソース特徴量それぞれについて、タスク処理時間の予測値の確率分布である予測時間分布を生成する予測時間分布生成手段と、を有する。
【００１３】
本発明が提供する制御方法は、予測時間分布生成装置として動作するコンピュータによって実行させる。当該制御方法は、処理サーバがタスクを処理した時における前記処理サーバのリソース特徴量を取得するリソース特徴量取得ステップと、前記処理サーバが前記タスクの処理に要した時間であるタスク処理時間を取得するタスク処理時間ステップと、前記リソース特徴量及び前記タスク処理時間の組み合わせに基づき、複数のリソース特徴量それぞれについて、タスク処理時間の予測値の確率分布である予測時間分布を生成する予測時間分布生成ステップと、を有する。
【００１４】
本発明が提供するプログラムは、コンピュータに、本発明が提供する予測時間分布生成装置として動作する機能を持たせる。当該プログラムは、前記コンピュータに、本発明が提供する予測時間分布生成装置が有する各機能構成部の機能を持たせる。
【発明の効果】
【００１５】
本発明によれば、分散システムにおいて、処理サーバをより効率よく利用する技術が提供される。
【図面の簡単な説明】
【００１６】
【図１】実施形態１に係る予測時間分布生成装置の構成を例示するブロック図である。
【図２】タスクを実行した際のディスク I/O 使用率とタスク処理時間との関係を実測した結果を示すグラフである。
【図３】予測時間分布生成装置によって生成される予測時間分布を概念的に示す図である。
【図４】予測時間分布生成装置のハードウエア構成を例示するブロック図である。
【図５】実施形態１の予測時間分布生成装置が実行する処理の流れを例示するフローチャートである。
【図６】リソース特徴量算出部を有する予測時間分布生成装置の構成を例示する図である。
【図７】実施例１の想定環境を示す図である。
【図８】リソース情報格納部に格納されているリソース情報をテーブル形式で例示する図である。
【図９】タスク情報格納部に格納されているタスク情報をテーブル形式で例示する図である。
【図１０】x1、x2、及び x3 を順に入力することで算出された予測時間分布を表すグラフである。
【図１１】x1、x2、及び x3 を用いて生成した線形回帰モデルを示すグラフである。
【発明を実施するための形態】
【００１７】
以下、本発明の実施の形態について、図面を用いて説明する。尚、すべての図面において、同様な構成要素には同様の符号を付し、適宜説明を省略する。
【００１８】
［実施形態１］
図１は、実施形態１に係る予測時間分布生成装置２０００の構成を例示するブロック図である。図１において矢印は情報の流れを表す。また、図１において、各ブロックは、ハードウエア単位の構成ではなく、機能単位の構成を示している。
【００１９】
予測時間分布生成装置２０００は、リソース特徴量取得部２０２０、タスク処理時間取得部２０４０、及び予測時間分布生成部２０６０を有する。以下、それぞれの機能構成部について説明する。
【００２０】
＜リソース特徴量取得部２０２０＞
リソース特徴量取得部２０２０は、処理サーバがタスクを処理した時におけるその処理サーバのリソース特徴量を取得する。ここで、処理サーバは種々の計算機であり、例えば PC（Personal Computer）、サーバマシン、タブレット PC、又は携帯端末などである。リソース特徴量は、処理サーバによって使用されるリソースに関する特徴量である。処理サーバが使用するリソースは、例えば CPU、メモリ、ディスク帯域、又はネットワーク帯域などである。
【００２１】
＜タスク処理時間取得部２０４０＞
タスク処理時間取得部２０４０は、タスク処理時間を取得する。タスク処理時間は、処理サーバがタスクの処理に要した時間である。
【００２２】
＜予測時間分布生成部２０６０＞
予測時間分布生成部２０６０は、タスクに関するリソース特徴量及びタスク処理時間の組み合わせに基づき、複数のリソース特徴量それぞれについて予測時間分布を生成する。予測時間分布は、タスクの処理に要するタスク処理時間の予測値の確率分布である。ここで、「タスクに関するリソース特徴量」とは、そのタスクを処理した時における処理サーバのリソース特徴量を意味する。予測時間分布生成部２０６０が複数のリソース特徴量それぞれについて予測時間分布を生成するために用いるリソース特徴量及びタスク処理時間の組み合わせは、１つでもよいし、複数でもよい。また、１つのタスク処理時間に組み合わせるリソース特徴量は１つでも良いし、複数でも良い。
【００２３】
＜作用・効果＞
前述したように、処理サーバのリソース使用率等が同一又は近い値である場合でも、タスクの処理に要する時間が異なる場合がある。図２は、処理サーバにおいてタスクを実行した場合におけるディスク I/O 使用率とタスク処理時間との関係を実測した結果を示すグラフである。X 軸は、タスク実行時の平均ディスク I/O 使用率を示し、Y 軸は、そのタスクを実行した際のタスク処理時間を示す。各プロットは、実測されたディスク I/O 使用率とタスク処理時間との組み合わせを示す。
【００２４】
グラフ１０から４０はそれぞれ、ディスク I/O 使用率と、そのディスク I/O 使用率に対応するタスク処理時間の予測値（以下、予測時間）との関係を示す関数である。グラフ１０から４０は、実測されたディスク I/O 使用率とタスク処理時間との関係に基づき、それぞれ異なる方法で生成された関数である。グラフ１０は、全てのタスク処理時間の平均値を予測時間とするグラフである。グラフ２０は、全てのプロットを用いて線形回帰を行うことで生成された関数である。グラフ３０は、全てのプロットを M/M/1 待ち行列モデルに適用することで生成されたグラフである。グラフ４０は、全てのプロットを M/D/1 待ち行列モデルに適用することで生成されたグラフである。
【００２５】
ここで、図２の範囲８０に着目する。範囲８０には多くのプロットが含まれている。これは、ディスク I/O 使用率が高い場合（例：７０％）でも、タスクの処理に要する時間が短いことがある（例：２０秒）ことを示している。
【００２６】
しかし、グラフ２０から４０を用いてタスク処理時間を予測する場合には、範囲８０に含まれる予測時間よりも大きな値が算出される。ここで通常、新たなタスクは処理時間の予測値が小さい処理サーバに対して割り当てられる。そのため、図２の状況においてグラフ２０から４０を用いてタスク処理時間を予測すると、ディスク I/O 使用率が高い場合には、この処理サーバに対してタスクが割り当てられなくなる。その結果、この処理サーバは効率的に利用されない。また、グラフ１０を用いて予測時間を算出すると、リソース使用率が考慮されない。そのため、グラフ１０を用いた場合も、この処理サーバは効率的に利用されない。
【００２７】
これに対し、予測時間分布生成装置２０００は、複数のリソース特徴量それぞれについて予測時間分布を生成する。図３は、予測時間分布生成装置２０００によって生成される予測時間分布を概念的に示す図である。グラフ５０は、ディスク I/O 使用率が４０％の場合に対応する予測時間分布であり、グラフ６０は、ディスク I/O 使用率が６０％の場合に対応する予測時間分布であり、グラフ７０は、ディスク I/O 使用率が８０％の場合に対応する予測時間分布である。
【００２８】
予測時間分布生成装置２０００によって生成される予測時間分布を利用して予測時間を算出すると、予測時間を確率的に算出することができる。例えばグラフ７０に従って予測時間を算出すると、７０秒程度の予測時間が算出される確率が高いものの、３０秒程度の予測時間が算出される場合もありうる。このように、予測時間分布に従って予測時間を算出すれば、リソース使用率が同一又は近い場合においてもタスク処理時間にばらつきがあるということを考慮した予測時間が算出される。これにより、例えば、「予測時間が小さい処理サーバに対して優先的にタスクを割り当てる」という処理を行う際に、「リソース使用率が高いときでも処理時間が短いことがある」という処理サーバに対してタスクが割り当てられるようになる。よって、本実施形態の予測時間分布生成装置２０００によれば、処理サーバをより効率的に利用することができる。
【００２９】
なお、予測時間分布生成部２０６０があるタスクに関するリソース特徴量及びタスク処理時間に基づいて生成した予測時間分布は、そのタスクと同一のタスクを処理サーバ上で動作させる場合におけるタスク処理時間の予測に用いてもよいし、そのタスクとは異なるタスクを処理サーバ上で動作させる場合におけるタスク処理時間の予測に用いてもよい。ただし、予測時間の算出には、予測対象のタスクと同一又は同種別のタスクに関する情報を用いて生成された予測時間分布を用いることが好ましい。
【００３０】
また、予測時間分布生成部２０６０がある処理サーバ上でタスクを処理した際のリソース特徴量及びタスク処理時間に基づいて生成した予測時間分布は、同一の処理サーバ上でタスクを処理する場合におけるタスク処理時間の予測に用いてもよいし、異なる処理サーバ上でタスクを処理する場合におけるタスク処理時間の予測に用いてもよい。ただし、予測時間の算出には、予測対象のタスクを動作させようとしている処理サーバと同一又は構成が近い処理サーバ上でタスクを実行した際の情報を用いて生成された予測時間分布を用いることが好ましい。
【００３１】
＜ハードウエア構成＞
図４は、予測時間分布生成装置２０００のハードウエア構成を例示するブロック図である。図４において、予測時間分布生成装置２０００は、バス１０２０、プロセッサ１０４０、メモリ１０６０、ストレージ１０８０、及びネットワークアダプタ１１００を有する。
【００３２】
バス１０２０は、プロセッサ１０４０、メモリ１０６０、ストレージ１０８０及びネットワークアダプタ１１００が、相互にデータを送受信するためのデータ伝送路である。プロセッサ１０４０は、例えば CPU (Central Processing Unit) や GPU (Graphics Processing Unit) などの演算処理装置である。メモリ１０６０は、例えば RAM (Random Access Memory) や ROM (Read Only Memory) などのメモリである。ストレージ１０８０は、例えばハードディスク、SSD (Solid State Drive)、又はメモリカードなどの記憶装置である。また、ストレージ１０８０は、RAM や ROM 等のメモリであってもよい。ネットワークアダプタ１１００は、ネットワークに接続するためのインタフェースである。
【００３３】
リソース特徴量取得モジュール１２２０は、予測時間分布生成装置２０００に、リソース特徴量取得部２０２０の機能を持たせるためのプログラムである。プロセッサ１０４０は、リソース特徴量取得モジュール１２２０を実行することで、リソース特徴量取得部２０２０の機能を実現する。
【００３４】
タスク処理時間取得モジュール１２４０は、予測時間分布生成装置２０００に、タスク処理時間取得部２０４０の機能を持たせるためのプログラムである。プロセッサ１０４０は、タスク処理時間取得モジュール１２４０を実行することで、タスク処理時間取得部２０４０の機能を実現する。
【００３５】
予測時間分布生成モジュール１２６０は、予測時間分布生成装置２０００に、予測時間分布生成部２０６０の機能を持たせるためのプログラムである。プロセッサ１０４０は、予測時間分布生成モジュール１２６０を実行することで、予測時間分布生成部２０６０の機能を実現する。
【００３６】
例えばプロセッサ１０４０は、上記各モジュールをメモリ１０６０上に読み出して実行する。ただし、プロセッサ１０４０は、上記各モジュールを、メモリ１０６０上に読み出さずに実行してもよい。
【００３７】
ストレージ１０８０は、上記各モジュールを格納する。
【００３８】
予測時間分布生成装置２０００のハードウエア構成は、図４に示した構成に限定されない。例えば、各モジュールはメモリ１０６０に格納されてもよい。この場合、予測時間分布生成装置２０００は、ストレージ１０８０を備えていなくてもよい。
【００３９】
＜処理の流れ＞
図５は、実施形態１の予測時間分布生成装置２０００が実行する処理の流れを例示するフローチャートである。ステップＳ１０２において、リソース特徴量取得部２０２０は、リソース特徴量を取得する。ステップＳ１０４において、タスク処理時間取得部２０４０は、タスク処理時間を取得する。ステップＳ１０６において、予測時間分布生成部２０６０は、リソース特徴量及びタスク処理時間に基づき、複数のリソース特徴量それぞれについて予測時間分布を生成する。
【００４０】
以下、本実施形態の予測時間分布生成装置２０００について、さらに詳細に説明する。
【００４１】
＜リソース特徴量取得部２０２０の詳細＞
リソース特徴量取得部２０２０が取得するソース特徴量は、例えばタスクを処理した時にサーバが使用したリソースの使用量や使用率である。また、リソース特徴量は、リソースの待ち数であってもよい。リソースの待ち数とは、そのリソースの割り当てを待っているプロセスやリクエストなどの数である。例えば CPU の待ち数は、その CPU に割り当てるプロセスを管理するプロセススケジューラのランキューのキュー長などで表される。また、例えばディスクの待ち数は、そのディスクに対するリクエストを管理する I/O スケジューラのキュー長などで表される。
【００４２】
リソース特徴量取得部２０２０は、１種類又は複数種類のリソースについて、リソース特徴量を取得する。
【００４３】
リソース特徴量は、ある時点において測定されたリソース使用量、使用率、又は待ち数の値であってもよいし、複数の時点で測定されたこれらの値の統計値であってもよい。
【００４４】
また、リソース特徴量は、前述したリソース使用量などを用いて算出された値であってもよい。この場合、例えばリソース特徴量は、タスク処理時間と比例関係等にある値として算出される。以下、具体的に説明する。
【００４５】
待ち行列モデル M/M/1 を仮定すると、タスク処理時間とリソース使用率との間には、以下の数式（１）で示す関係が成り立つ。ここで、t はタスク処理時間、x はリソース使用率を表す。また、k は正の実数である。例えばリソース特徴量取得部２０２０は、数式（１）を用いて算出された 1/(1-x) をリソース特徴量として取得する。
【数１】
2015108877.tif 000003
【００４６】
また、待ち行列モデル M/M/1 を仮定すると、タスク処理時間とリソースの待ち数との間には、以下の数式（２）で示す関係が成り立つ。数式（２）における各記号の意味は、数式（１）における各記号の意味と同様である。例えばリソース特徴量取得部２０２０は、数式（２）を用いて算出された x+1 をリソース特徴量として取得する。
【数２】
2015108877.tif 000004
【００４７】
また、リソース特徴量取得部２０２０が取得するリソース特徴量は、複数種類のリソースそれぞれに関するリソース特徴量を用いて算出された１つの値であってもよい。複数のリソース特徴量から１つのリソース特徴量を算出する具体的な方法は、例えば以下の数式（３）を用いる方法である。ri は各リソースに関するリソース特徴量であり、R はこれら各リソース特徴量を用いて算出されるリソース特徴量である。例えばリソース特徴量取得部２０２０は、数式（３）を用いて算出された R をリソース特徴量として取得する。なお、複数種類のリソース特徴量を用いて１つのリソース特徴量を算出する方法は、数式（３）に示す方法に限定されない。例えば、各リソース特徴量 ri の和や重み付き平均を、１つのリソース特徴量 R として算出してもよい。
【数３】
2015108877.tif 000005
【００４８】
また、予測時間分布生成装置２０００は、上述した各数式などを用いてリソース特徴量を算出する機能を有してもよい。この機能を持つ機能構成部を、リソース特徴量算出部２０８０と表記する。図６は、リソース特徴量算出部２０８０を有する予測時間分布生成装置２０００の構成を例示する図である。
【００４９】
リソース特徴量算出部２０８０は、サーバのリソース使用状況を表す情報（以下、リソース情報）を取得し、そのリソース情報に基づいてリソース特徴量を算出する。リソース情報が示す値は、例えばリソース使用率、リソース使用量、又はリソースの待ち数などである。そして、リソース特徴量算出部２０８０は、リソース使用率等からリソース特徴量を算出する。例えばリソース特徴量算出部２０８０は、リソース使用率を取得し、数式（１）を用いてリソース特徴量を算出する。
【００５０】
例えばリソース特徴量算出部２０８０は、リソース情報が示す値の種類に応じて、リソース特徴量の算出方法を決定する。この場合、リソース情報は、値とその値の種類（例：リソース使用率や待ち数など）との組み合わせを示す。そして、リソース特徴量算出部２０８０は、リソース情報が示す値の種類に応じた方法を用いて、リソース特徴量を算出する。ただし、リソース特徴量算出部２０８０が取得する値の種類は、予め固定されていてもよい。この場合、リソース特徴量算出部２０８０は、予め固定されている値の種類に応じた算出方法でリソース特徴量を算出する。
【００５１】
リソース特徴量取得部２０２０がリソース特徴量を入手する方法は様々である。例えばリソース特徴量取得部２０２０は、外部の装置から入力されるリソース特徴量を取得する。その他にも例えば、リソース特徴量取得部２０２０は、手動で入力されるリソース特徴量を取得する。さらにリソース特徴量取得部２０２０は、外部の装置にアクセスして、リソース特徴量を取得してもよい。例えば、上記外部の装置は、処理サーバである。また、分散システムにおいて処理サーバを管理する管理サーバがある場合、リソース特徴量取得部２０２０は、この管理サーバからリソース特徴量を取得してもよい。
【００５２】
予測時間分布生成装置２０００がリソース特徴量算出部２０８０を有する場合、リソース特徴量算出部２０８０は、前述のリソース特徴量取得部２０２０がリソース特徴量を入手する方法と同様の方法でリソース情報を取得する。この場合、リソース特徴量取得部２０２０は、リソース特徴量算出部２０８０によって算出されたリソース特徴量を取得する。また、リソース特徴量取得部２０２０は、リソース特徴量算出部２０８０のよって算出されたリソース特徴量と、外部から提供されるリソース特徴量の双方を取得してもよい。
【００５３】
＜タスク処理時間取得部２０４０の詳細＞
タスク処理時間取得部２０４０がタスク処理時間を取得する方法は様々である。例えばタスク処理時間取得部２０４０は、外部の装置から入力されるタスク処理時間を取得する。その他にも例えば、タスク処理時間取得部２０４０は、手動で入力されるタスク処理時間を取得する。さらにタスク処理時間取得部２０４０は、外部の装置にアクセスして、タスク処理時間を取得してもよい。ここで、上記外部の装置は、例えば処理サーバである。また、分散システムにおいて処理サーバを管理する管理サーバがある場合、タスク処理時間取得部２０４０は、この管理サーバからタスク処理時間を取得してもよい。
【００５４】
＜予測時間分布生成部２０６０の詳細＞
前述したように、予測時間分布生成部２０６０は、リソース特徴量とタスク処理時間とを用いて、リソース特徴量ごとの予測時間分布を生成する。予測分布の確率モデルとしては、正規分布、スチューデントの t 分布、又は指数分布などの種々の確率モデルが利用できる。
【００５５】
例えば予測時間分布生成部２０６０は、リソース特徴量とタスク処理時間との関係を表す回帰モデルを生成する。そして、予測時間分布生成部２０６０は、この回帰モデルを条件とする条件付き分布を生成し、この条件付き分布を予測時間分布とする。リソース特徴量とタスク処理時間との関係を表す回帰モデルは、線形回帰モデルであってもよいし、非線形回帰モデルであってもよい。また、条件付き分布の確率モデルとしては、正規分布、スチューデントの t 分布、又は指数分布など、種々の確率モデルが利用できる。また、予測時間分布生成部２０６０が確率分布のモデルパラメータを算出する方法としては、統計的推定や機械学習アルゴリズムなどの種々の方法が利用できる。例えば予測時間分布生成部２０６０は、最尤推定法、ベイズ線形回帰、変分線形回帰、又は線形回帰の混合モデルなどを利用して、確率モデルのモデルパラメータを計算する。
【００５６】
予測時間分布生成部２０６０が予測時間分布を生成する契機は様々である。例えば予測時間分布生成部２０６０は、所定数のタスクについてリソース特徴量及びタスク処理時間を取得する度に、取得したリソース特徴量とタスク処理時間とを用いて予測時間分布を生成する。所定数は、１でもよいし、２以上でもよい。例えば、処理サーバにおいてタスクの実行が完了する度に、処理サーバ又は処理サーバを管理している管理サーバから、予測時間分布生成装置２０００に対して、実行が完了したタスクに関するリソース特徴量及びタスク処理時間を送信するようにする。このようにすると、予測時間分布生成装置２０００は、所定数のタスクの実行が完了する度に、実行が完了したタスクに関するリソース特徴量及びタスク処理時間を用いて、予測時間分布を生成する。
【００５７】
また例えば、予測時間分布生成部２０６０は、処理サーバを管理する管理サーバからの指示を受けたことを契機に、予測時間分布を生成してもよい。
【００５８】
予測時間分布生成部２０６０は、リソース特徴量ごとの予測時間分布を、タスクの種別ごとに生成する機能を有していてもよい。この場合、予測時間分布生成部２０６０は、取得したリソース特徴量とタスク処理時間を、対応するタスクの種別毎に分類する。そして、予測時間分布生成部２０６０は、同一の種別に分類されたリソース特徴量及びタスク処理時間のみを用いて、リソース特徴量ごとの予測時間分布を生成する。
【００５９】
タスク種別は、例えばジョブのＩＤで表される。例えば各タスクは、そのタスクの元となっているジョブのＩＤに対応付けられている。ただし、タスク種別は、ジョブのＩＤ以外でもよい。例えばその他のタスク種別は、ジョブのフェーズのＩＤや、ジョブのＩＤとフェーズのＩＤとの組み合わせなどである。
【００６０】
＜実施例１＞
実施形態１に係る予測時間分布生成装置２０００の具体的な動作例を、実施例１として説明する。実施例１の予測時間分布生成部２０６０は、リソース特徴量とタスク処理時間との組み合わせを入力としてベイズ線形回帰を行うことで、リソース特徴量ごとに予測時間分布を生成する。
【００６１】
＜＜想定環境＞＞
図７は実施例１の想定環境を示す図である。分散システム５０００は、マスタサーバ４０００及び複数の処理サーバ３０００を有する。マスタサーバ４０００は、処理サーバ３０００を管理するサーバである。
【００６２】
実施例１の予測時間分布生成装置２０００は、リソース特徴量取得部２０２０、タスク処理時間取得部２０４０、及び予測時間分布生成部２０６０に加え、リソース特徴量算出部２０８０及び予測時間算出部２１００を有する。リソース特徴量算出部２０８０については、前述した通りである。予測時間算出部２１００は、予測時間分布生成部２０６０によって生成された予測時間分布を用いて、処理サーバ３０００で実行されるタスクの処理時間の予測値を算出する。その具体的な方法については、後述の実施例２で説明する。
【００６３】
＜＜＜処理サーバ３０００＞＞＞
処理サーバ３０００は、タスク実行部３０２０、リソース情報格納部３０４０、及びタスク情報格納部３０６０を有する。タスク実行部３０２０は、１つ又は複数のタスクを実行する。例えばタスク実行部３０２０は、プロセス、スレッド、又は仮想マシンなどである。処理サーバ３０００は、複数のタスク実行部３０２０を有してもよい。
【００６４】
リソース情報格納部３０４０はリソース情報を格納する。前述した通り、リソース情報は、例えばリソース使用率など、サーバのリソース使用状況を直接的に表す情報である。なお、処理サーバ３０００において各リソースの使用量などを計測する方法は既知の技術である。そのため、その方法については説明を省略する。
【００６５】
図８は、リソース情報格納部３０４０に格納されているリソース情報をテーブル形式で例示する図である。図８が示すテーブルを、リソース情報テーブル１００と表記する。リソース情報テーブル１００は、サーバ識別子１０２及びリソース識別子１０４の組み合わせに対応付けて、記録時刻１０６、使用率１０８、使用時間１１０、及び待ち数１１２を示している。記録時刻１０６は、レコードが記録された時刻を示す。使用率１０８はリソース使用率を示し、使用時間１１０はリソース使用量を示し、待ち数１１２はリソースの待ち数を示す。
【００６６】
タスク情報格納部３０６０は、タスクに関する情報（タスク情報）を格納する。タスク情報格納部３０６０に格納されているタスク情報は、タスク実行部３０２０が実行しているタスク又はタスク実行部３０２０が過去に実行したタスクに関するタスク情報である。
【００６７】
図９は、タスク情報格納部３０６０に格納されているタスク情報をテーブル形式で例示する図である。図９が示すテーブルを、タスク情報テーブル２００と表記する。タスク情報テーブル２００は、タスク識別子２０２に対応付けて、サーバ識別子２０４、タスク種別２０６、ジョブ識別子２０８、開始時刻２１０、終了時刻２１２、及び処理時間２１４を示す。開始時刻２１０はタスクの実行を開始した時刻を示す。また、終了時刻２１２は、タスクの実行が完了した時刻を示す。タスクが実行中である場合、例えば終了時刻２１２は NULL を示す。処理時間２１４はタスクの実行に要した時間であり、終了時刻２１２と開始時刻２１０との差分に相当する。
【００６８】
タスク実行部３０２０は、タスクの実行を開始する際にタスク情報テーブル２００のレコードを生成する。そして、タスク実行部３０２０は、タスクの実行が完了したときに、そのタスクに関するレコードの終了時刻２１２及び処理時間２１４に情報を追加する。
【００６９】
＜＜＜マスタサーバ４０００＞＞＞
マスタサーバ４０００は、タスク実行管理部４０２０、リソース情報管理部４０４０、及びタスク情報管理部４０６０を有する。タスク実行管理部４０２０は、処理サーバ３０００に対してタスクを割り当てる処理や、処理サーバ３０００に対してタスクの開始又は中止を指示する処理などを行う。
【００７０】
リソース情報管理部４０４０は、各処理サーバ３０００のリソース情報格納部３０４０からリソース情報を収集して管理する。リソース特徴量算出部２０８０は、リソース情報管理部４０４０によって管理されているリソース情報を取得する。
【００７１】
タスク情報管理部４０６０は、各処理サーバ３０００のタスク情報格納部３０６０からタスク情報を収集して管理する。タスク処理時間取得部２０４０は、タスク情報管理部４０６０によって管理されているタスク情報を取得する。そして、タスク処理時間取得部２０４０は、タスク情報の中からタスク処理時間を取得する。
【００７２】
タスク実行管理部４０２０は、必要に応じて、予測時間算出部２１００によって算出された予測時間を取得する。例えばタスク実行管理部４０２０は、新たなタスクの割り当て先を複数の処理サーバ３０００の中から選択するために、各処理サーバ３０００についてタスク処理時間の予測時間を取得する。そして、各処理サーバ３０００に関する予測時間に基づいてタスクを割り当てる処理サーバ３０００を決定し、その処理サーバ３０００に対してタスクを割り当てる。
【００７３】
＜＜予測時間分布の生成方法＞＞
以下、実施例１の予測時間分布生成装置２０００が予測時間分布を生成する方法について説明する。前述したように、実施例１の予測時間分布生成部２０６０は、リソース特徴量を用いてベイズ線形回帰を行うことで、複数のリソース特徴量ごとに予測時間分布を生成する。
【００７４】
実施例１において、リソース特徴量算出部２０８０は、CPU のランキューのキュー長（以下、CPU キュー長）を示すリソース情報を取得する。そして、リソース特徴量算出部２０８０は、前述した数式（２）を用いて、CPU キュー長からリソース特徴量を算出する。リソース特徴量取得部２０２０は、リソース特徴量算出部２０８０によって算出されたリソース特徴量を取得する。
【００７５】
実施例１の予測時間分布生成部２０６０は、リソース特徴量 xi を入力として以下の数式（４）を用い、線形回帰モデル u(xi,w) を生成する。ここで、ベクトル w は重みベクトルである。また、ベクトルφ(x) は、リソース特徴量を含むベクトルである。以下、ベクトルφを特徴量ベクトルとも表記する。ここで、φ(x) の０番目の要素は定数１であり、φ(x) の１番目の要素はリソース特徴量を示す。
【数４】
2015108877.tif 000006
【００７６】
次に、予測時間分布生成部２０６０は、線形回帰モデル u(xi,w) を確率モデル化する。 具体的には、予測時間分布生成部２０６０は、線形回帰モデル u(xi,w) を、平均が u(xi,w)であり、かつ分散がβ^(-1) である正規分布のモデル p(ti|xi,w,β) を生成する。なお、β^(-1) は適宜設定するパラメタであり、例えば経験ベイズやエビデンス近似といった方法で決定される。本実施例では、β^(-1) = 10^9 とする。
【００７７】
そして、予測時間分布生成部２０６０は、確率モデル p(ti|xi,w,β) の未知の重み w の事前分布 d(i-1) から事後分布 di を算出する。事前分布と事後分布との関係は、以下の数式（５）で表される。
【数５】
2015108877.tif 000007
【００７８】
そして、予測時間分布生成部２０６０は、事後分布 di を用いて、以下の数式（６）に示すように予測時間分布 p(t|x,ti,xi,β,m(i-1),S(i-1)) を算出する。具体的には、予測時間分布生成部２０６０は、事後分布 di を特定する Si と mi とを用いて、ai と bi を算出する。そして、予測時間分布生成部２０６０は、平均が ai であり、かつ分散が bi である正規分布を、予測時間分布 p(t| x,ti,xi,β,m(i-1),S(i-1)) として算出する。
【数６】
2015108877.tif 000008
【００７９】
ここで、数式（６）は、a(i+1) と b(i+1) が、共にリソース特徴量 x の関数であることを示している。つまり、予測時間分布 p(t| x,ti,xi,β,m(i-1),S(i-1)) はリソース特徴量 x に応じて定まる正規分布である。したがって、数式（６）は、リソース特徴量 x の値ごとに予測時間分布が生成されていることを意味する。
【００８０】
以降、予測時間分布生成部２０６０は、取得したリソース特徴量を順次用いて、同様の処理を行う。ただし、予測時間分布生成部２０６０は、あるリソース特徴量を用いて予測時間分布を生成する際の事前分布として、その前に予測時間分布を生成した際に算出された事後分布を用いる。つまり、i 番目のリソース特徴量を用いて予測時間分布を生成する過程で算出された事後分布 di を、i+1 番目のリソース特徴量を用いて予測時間分布を生成する際の事前分布として用いる。こうすることで、それまでに入力された全てのリソース特徴量の値が加味された予測時間分布が生成される。
【００８１】
＜＜具体的な値に対する処理結果＞＞
図８のリソース情報テーブル１００が示す情報を用いて生成される予測時間分布について説明する。この例において、リソース特徴量算出部２０８０は、リソースの待ち数を用いてリソース特徴量を算出する。
【００８２】
まずリソース特徴量算出部２０８０は、リソース情報テーブル１００の１行目のレコードの待ち数１１２が示す値である 1 を取得する。この値を x1 とも表記する。リソース特徴量算出部２０８０は、数式（７）に示すように、特徴量ベクトルφ(x1) を算出する。そして、予測時間分布生成部２０６０は、数式（８）に示すように、特徴量ベクトルφ(x1) から線形回帰モデル u(x1) を算出する。
【数７】
2015108877.tif 000009
【数８】
2015108877.tif 000010
【００８３】
予測時間分布生成部２０６０は、重み w の事前分布 d0 から事後分布 d1 を算出する。ここで、予測時間分布生成部２０６０は、事前分布 d0 の平均 m0 と共分散 S0 として、以下の数式（９）に示すものを用いる。
【数９】
2015108877.tif 000011
【００８４】
その結果、事後分布 d1 は、以下の数式（１０）に示す m1 を平均とし、S1 を共分散とする正規分布となる。
【数１０】
2015108877.tif 000012
【００８５】
そして、予測時間分布生成部２０６０は、数式（６）に数式（１０）が示す S1 と m1 を適用して、予測時間分布 p(t|x,t1,x1,β,m0,S0) を算出する。
【００８６】
続いて予測時間分布生成部２０６０は、リソース情報テーブル１００の２行目のレコードが示す待ち数１１２を x2 として、同様の処理を行う。ただし、予測時間分布生成部２０６０は、重み w の事前分布として、上述の処理で算出した事後分布 d1 を用いる。
【００８７】
処理の結果、事後分布 d2 は、以下の数式（１１）に示す m2 と S2 で特定される正規分布となる。そして、予測時間分布生成部２０６０は、数式（６）に数式（１１）が示す S2 と m2 を適用して、予測時間分布 p(t|x,t2,x2,β,m1,S1) を算出する。
【数１１】
2015108877.tif 000013
【００８８】
続いて、予測時間分布生成部２０６０は、リソース情報テーブル１００の３行目のレコードが示す待ち数１１２を x3 として、同様の処理を行う。処理の結果、事後分布 d3 は、以下の数式（１２）に示す m3 と S3 で特定される正規分布となる。そして、予測時間分布生成部２０６０は、数式（６）に数式（１２）が示す S3 と m3 を適用して、予測時間分布 p(t|x,t3,x3,β,m2,S2) を算出する。
【数１２】
2015108877.tif 000014
【００８９】
図１０は、x1、x2、及び x3 を順に入力することで算出された予測時間分布を表すグラフである。この三次元のグラフをある x の値 xj で切った断面に表れる二次元のグラフは、リソース特徴量 xj に対応する予測時間分布を表す。なお、図１１は、x1、x2、及び x3 を用いて生成した線形回帰モデルを示すグラフである。図１０に示す予測時間分布は、図１１に示す線形回帰モデルをベイズ線形回帰で確率モデル化したものとなる。
【００９０】
[実施形態２]
実施形態２に係る予測時間分布生成装置２０００の構成は、実施形態１の予測時間分布生成装置２０００と同様に図１で表される。以下で説明する点を除き、実施形態２の予測時間分布生成装置２０００は、実施形態１の予測時間分布生成装置２０００と同様である。
【００９１】
実施形態２の予測時間分布生成部２０６０は、リソース特徴量の値空間を複数の部分空間に分割する。そして、各部分空間に対応付けて、リソース特徴量がその部分空間内に属する場合における予測時間分布を生成する。
【００９２】
例えばリソース特徴量がリソース使用率を表しているとする。この場合、予測時間分布生成部２０６０は、リソース使用率の値空間である [0, 1] を２等分し、[0,0.5) と [0.5,1] を生成する。そして、この２つの値空間それぞれに対して、予測分布を生成する。
【００９３】
また、リソース特徴量取得部２０２０が、複数種類のリソースそれぞれについてリソース特徴量を取得したとする。この場合、予測時間分布生成部２０６０は、複数種類のリソース特徴量によって定まる値空間を分割して、複数の部分空間を生成する。
【００９４】
例えば、リソース特徴量取得部２０２０が、n 種類のリソースそれぞれについてリソース特徴量を取得したとする。この場合、全種類のリソース特徴量の組み合わせで定まる値空間は n 次元空間となる。例えば予測時間分布生成部２０６０は、各種類のリソース特徴量の値空間を m 等分する。すると、全種類のリソース特徴量で定まる値空間は、m^n 個の部分空間に分割される。この場合、予測時間分布生成部２０６０は、m^n 個の部分空間それぞれについて、予測時間分布を生成する。
【００９５】
＜作用・効果＞
本実施形態の予測時間分布生成装置２０００によれば、リソース特徴量の値空間が複数の部分空間に分割され、部分空間ごとに予測時間分布が生成される。この方法は、例えば部分空間毎に予測時間分布の性質が異なる場合に有効である。これは、部分空間毎に予測時間分布を生成するため、例えば部分空間毎に異なる確率モデルを用いて予測時間分布を生成するといったことが可能であるためである。
【００９６】
＜実施例２＞
以下、実施形態２の予測時間分布生成装置２０００が行う具体的な動作の例を、実施例２として説明する。実施例２における想定環境は、実施例１における想定環境と同様である。
【００９７】
実施例２の予測時間分布生成装置２０００は、ディスク I/O 使用率 xk を示すリソース情報を６つ取得する。具体的には、リソース情報はそれぞれ、x1=0.667、x2=0.8、x3=0.9、x4=0.75、x5=0.875、x6=0.889 を示す。
【００９８】
リソース特徴量算出部２０８０は、以下の数式（１３）を用いて、ディスク I/O 使用率からリソース特徴量φ(xk) を算出する。
【数１３】
2015108877.tif 000015
【００９９】
リソース特徴量算出部２０８０は、取得した各ディスク I/O 使用率を数式（１３）に適用することで、φ(x1)=3、φ(x2)=5、φ(x3)=10、φ(x4)=4、φ(x5)=8、及びφ(x6)=9 をそれぞれ算出する。
【０１００】
タスク処理時間取得部２０４０は、ディスク I/O 使用率 xk に対応するタスク処理時間 tk を取得する。具体的には、タスク処理時間取得部２０４０は、t1=25,000、t2=70,000、t3=80,000、t4=55,000、t5=30,000、及び t6=130,000 を取得する。ここで、タスク処理時間の単位はミリ秒である。
【０１０１】
予測時間分布生成部２０６０は、リソース特徴量の値空間を２等分する。ここで、予測時間分布生成部２０６０は、リソース特徴量φ1(xk) の値空間（値域）を (0,10] と仮定する。その結果、予測時間分布生成部２０６０は、値空間 (0,10] を、部分空間 vd1=(0,5] と部分空間 vd2=(5,10] に分割する。
【０１０２】
予測時間分布生成部２０６０は、部分空間 vd1 と vd2 それぞれについて予測時間分布を算出する。以下に、その方法を説明する。まず予測時間分布生成部２０６０は、各φ(xk) を属する部分空間に基づいて分類する。具体的には、φ(x1)、φ(x2)、及びφ(x4) を vd1 に分類し、φ(x3)、φ(x5)、及びφ(x6) を vd2 に分類する。
【０１０３】
予測時間分布生成部２０６０は、同じ部分空間に属する各リソース特徴量に対応するタスク処理時間を用いて、その部分空間に対応する予測時間分布を算出する。具体的には、予測時間分布生成部２０６０は、タスク処理時間取得部２０４０が取得したタスク処理時間を標本として、母集団における平均及び標準偏差を推定する。そして、予測時間分布生成部２０６０は、推定した平均及び標準偏差で特定される正規分布を、その部分空間に対応する予測時間分布として生成する。
【０１０４】
以下、具体的な値を用いて説明する。まず予測時間分布生成部２０６０は、部分空間 vd1 に対応する予測時間分布を算出する。そのために、予測時間分布生成部２０６０は、vd1 に属する各リソース特徴量 φ(x1)、φ(x2)、及びφ(x4)に対応するタスク処理時間 t1、t2、及び t4 を用いる。具体的には、予測時間分布生成部２０６０は、数式（１４）が示すように平均μ1 と標準偏差σ1 を推定する。なお、数式（１４）において、予測時間分布生成部２０６０は、平均を標本平均とし、標準偏差を標本分散の平方根とする方法で推定を行っている。ただし、予測時間分布生成部２０６０が標本から母集団における平均と分散を推定する方法としては、他の様々な既知の推定方法を用いることができる。
【数１４】
2015108877.tif 000016
【０１０５】
上述の推定により、予測時間分布生成部２０６０は、部分空間 vd1 に対応する予測時間分布として、平均が 50,000 であり、標準偏差が 18,708 である正規分布を生成する。
【０１０６】
予測時間分布生成部２０６０は同様の方法により、部分空間 vd2 について平均μ2 = 80,000 及び標準偏差σ2 = 40,825 を推定する。その結果、予測時間分布生成部２０６０は、部分空間 vd2 に対応する予測時間分布として、平均が 80,000 であり、標準偏差が 40,825 である正規分布を生成する。
【０１０７】
＜＜予測時間の算出＞＞
予測時間算出部２１００が予測時間分布を用いて予測時間を算出する方法を説明する。ここで、タスク実行管理部４０２０が新たなタスクを処理サーバ３０００に対して割り当てようとしたとする。タスク実行管理部４０２０は、処理サーバ３０００のリソース情報格納部３０４０から、現在のリソース使用状況を表すリソース情報を取得する。ここで、このリソース情報は、ディスク I/O 使用率が 0.5 であることを示しているとする。
【０１０８】
タスク実行管理部４０２０は、予測時間算出部２１００に対して、ディスク I/O 使用率 0.5 を入力する。すると、予測時間算出部２１００は、予測時間分布生成部２０６０によって生成された予測時間分布の中から、ディスク I/O 使用率 0.5 に対応する予測時間分布を取得する。具体的には、以下の流れになる。
【０１０９】
まず、リソース特徴量算出部２０８０が、ディスク I/O 使用率 0.5 からリソース特徴量を算出する。算出結果は 2 となる。ここで、2 は部分空間 vd1 に属する。そこで、予測時間算出部２１００は、部分空間 vd1 に対応する予測時間分布を取得する。この予測時間分布は、数式（１４）に示す平均と標準偏差で特定される正規分布である。
【０１１０】
予測時間算出部２１００は、この予測時間分布から、タスク処理時間の予測時間を算出する。例えば予測時間算出部２１００は、直接法と呼ばれる方法を用いて予測時間を算出する。その方法は、以下に示す通りである。なお、予測時間算出部２１００が予測時間分布から予測時間を算出する方法は、この方法に限定されない。
【０１１１】
まず、予測時間算出部２１００は、一様乱数 y を生成する。そして、予測時間算出部２１００は、一様乱数 y が以下の数式（１５）を満たすように、数式（１５）における x の値を算出する。ここで数式（１５）における f(x) は、予測時間算出部２１００が取得した vd1 に対応する予測時間分布である。そして、予測時間算出部２１００は、算出した x を予測時間として出力する。
【数１５】
2015108877.tif 000017
【０１１２】
＜実施例３＞
実施形態２の予測時間分布生成装置２０００の別の動作例を、実施例３として説明する。実施例３の想定環境は、実施例２と同様である。
【０１１３】
実施例３の予測時間分布生成装置２０００は、複数種類のリソースそれぞれに関するリソース特徴量を用いる点が、実施例２の予測時間分布生成装置２０００と異なる。
【０１１４】
実施例３の予測時間分布生成装置２０００は、ディスク I/O 使用率と CPU のランキュー長（CPU の待ち数）という２種類の情報を示すリソース情報を取得する。具体的には、予測時間分布生成装置２０００は、(xk,yk)=(ディスク I/O 使用率、CPU ランキュー長）T として、(x1,y1)=(0.667,1)T、(x2,y2)=(0.8,3)T、(x3,y3)=(0.9,6)T、(x4,y4)=(0.75,8)T、(x5,y5)=(0.875,4)T、及び (x6,y6)=(0.889,2)T を取得する。
【０１１５】
そして、リソース特徴量算出部２０８０は、以下の数式（１６）を用いて、各 (xk,yk) に対応する特徴量ベクトルφk を求める。具体的には、各φk の値は、φ1=(3,2)T、φ2=(5,4)T、φ3=(10,7)T、φ4=(4,9)T、φ5=(8,5)T、φ6=(9,3)T となる。
【数１６】
2015108877.tif 000018
【０１１６】
タスク処理時間取得部２０４０は、各 (xk,yk) に対応するタスク処理時間 tk を取得する。ここで、tk は、t1=25,000、t2=70,000、t3=80,000、t4=55,000、t5=30,000、及び t6=130,000 であったとする。
【０１１７】
予測時間分布生成部２０６０は、リソース特徴量の値空間を複数の部分空間に分割する。ここで、xk と yk の値空間が共に (0,10] であると仮定する。予測時間分布生成部２０６０は、２つのリソース特徴量からなる２次元の値空間を、数式（１７）に示す４つの部分空間に分割する。
【数１７】
2015108877.tif 000019
【０１１８】
予測時間分布生成部２０６０は、各各φk を属する部分空間に分類する。具体的には、予測時間分布生成部２０６０は、φ1 及びφ2 を vd1 に分類し、φ4 を vd2 に分類し、φ5 及びφ6 を vd3 に分類し、φ3 を vd4 に分類する。
【０１１９】
実施例３の予測時間分布生成部２０６０は、vd1、vd2、vd3、及び vd4 それぞれに対応する予測時間分布を算出する。予測時間分布生成部２０６０は、vd1 に分類されたφ1 及びφ2 に対応する t1 及び t2 を用いて、vd1 に対応する予測時間分布を生成する。同様に、予測時間分布生成部２０６０は、t4 を用いて vd2 に対応する予測時間分布を生成し、t5 及び t6 を用いて vd3 に対応する予測時間分布を生成し、t3 を用いて vd4 に対応する予測時間分布を生成する。実施例３の予測時間分布生成部２０６０がタスク処理時間から予測時間分布を生成する方法は、実施例２の予測時間分布生成部２０６０が行う方法と同様である。
【０１２０】
＜＜予測時間の算出＞＞
実施例３の予測時間算出部２１００は、実施例２の予測時間算出部２１００と同様の方法で予測時間を算出する。例えば、タスク実行管理部４０２０がリソース情報格納部３０４０から現在のリソース使用状況を表すリソース情報を取得した際、リソース情報が「ディスク I/O 使用率 = 0.5、CPU ランキュー長 = 4」を示していたとする。
【０１２１】
タスク実行管理部４０２０は、予測時間算出部２１００に対して、(x,y)=(0.5,4) を入力する。すると、リソース特徴量算出部２０８０は、φ(x,y)=(2,5)T を算出する。このφ(x,y) は、vd1 に属する。よって、予測時間算出部２１００は、vd1 に対応する予測時間分布を用いて、予測時間を算出する。予測時間分布に基づいて予測時間を算出する方法は、実施例２で説明した方法と同様である。
【０１２２】
以上、図面を参照して本発明の実施形態について述べたが、これらは本発明の例示であり、上記以外の様々な構成を採用することもできる。
【符号の説明】
【０１２３】
１０、２０、３０、４０、５０、６０、７０ グラフ
８０ 範囲
１００ リソース情報テーブル
１０２ サーバ識別子
１０４ リソース識別子
１０６ 記録時刻
１０８ 使用率
１１０ 使用時間
１１２ 待ち数
２００ タスク情報テーブル
２０２ タスク識別子
２０４ サーバ識別子
２０６ タスク種別
２０８ ジョブ識別子
２１０ 開始時刻
２１２ 終了時刻
２１４ 処理時間
１０２０ バス
１０４０ プロセッサ
１０６０ メモリ
１０８０ ストレージ
１１００ ネットワークアダプタ
１２２０ リソース特徴量取得モジュール
１２４０ タスク処理時間取得モジュール
１２６０ 予測時間分布生成モジュール
２０００ 予測時間分布生成装置
２０２０ リソース特徴量取得部
２０４０ タスク処理時間取得部
２０６０ 予測時間分布生成部
２０８０ 特徴量算出部
２１００ 予測時間算出部
３０００ 処理サーバ
３０２０ タスク実行部
３０４０ リソース情報格納部
３０６０ タスク情報格納部
４０００ マスタサーバ
４０２０ タスク実行管理部
４０４０ リソース情報管理部
４０６０ タスク情報管理部
５０００ 分散システム
【図１】
2015108877.tif 000020
【図２】
2015108877.tif 000021
【図３】
2015108877.tif 000022
【図４】
2015108877.tif 000023
【図５】
2015108877.tif 000024
【図６】
2015108877.tif 000025
【図７】
2015108877.tif 000026
【図８】
2015108877.tif 000027
【図９】
2015108877.tif 000028
【図１０】
2015108877.tif 000029
【図１１】
2015108877.tif 000030