JP6237170B2 - 割当判定装置、制御方法、及びプログラム - Google Patents

Description

本発明は、割当判定装置、制御方法、及びプログラムに関する。

ジョブを分割することで生成された複数のタスクを、複数の計算機（以下、処理サーバ）に分散して実行させる分散システムが開発されている。処理サーバは、タスクを実行できる状態になると、新たなタスクの割り当てを受ける。このような形態の分散システムでは、タスクが終了した処理サーバから順に新たなタスクが割り当てられるため、高速な処理サーバに対してより多くのタスクが割り当てられやすくなる。その結果、ジョブの実行効率が高くなる。

新しいタスクを割当てる処理サーバが複数存在する場合、他の処理サーバより短い時間でタスクを処理できるサーバを選択できれば、ジョブの完了時間をより短縮できる。短い処理時間で処理できるサーバを選択するためには、処理サーバごとにタスクの処理時間を予測する必要がある。

タスクの処理時間の予測又はそれに関連する技術を開示している先行技術文献として、非特許文献１及び特許文献１から６がある。非特許文献１は、実行中のタスクの処理に要する時間を短くする技術を開示している。具体的には、まず、処理サーバ上で実行されているタスクの処理に要する時間を、１）そのままタスクの実行を続けた場合、及び２）タスクを再実行した場合の２つの場合について算出する。そして、再実行した場合の所要時間の方が短い場合、そのタスクを再実行する。

特許文献１及び２は、予め計測しておいたタスクの負荷指標と処理サーバの性能指標を元に、タスクの割当計画を静的に算出する技術を開示する。

特許文献３は、ジョブの進捗状況から完了時間を推定し、ジョブの要求完了時間を満たさない場合はジョブを複数のタスクに分割し、分割したタスクを複数の処理サーバに割り当てることで、並列処理を実現する技術を開示する。

特許文献４は、処理サーバの構成に基づいて算出された静的な性能指標値に基づき、高性能な処理サーバに対してタスクを割り当てる技術を開示する。

特許文献５は、リソースが確保された時間内に処理が完了するかを予測し、時間内に完了しない場合、処理を中断する技術を開示する。

特許文献６は、複数の記憶装置で構成されたファイルシステムにおいてデータのセグメントの読み出し時間を推定し、どの記憶装置が最も短いかの推定に基づいて、読み出す記憶装置を選択する技術を開示する。

特開２００８−２４３２１６号公報 特開２０１０−２７７６０４号公報 特開２００８−１２３２０５号公報 特開２００７−３１７０３８号公報 特開２０１０−１５２７３８号公報 特開２００９−５９３５７号公報

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 使用率とタスク処理時間との関係を実測した結果を示すグラフである。 予測時間分布取得部によって取得される予測時間分布を概念的に示す図である。 割当判定装置のハードウエア構成を例示するブロック図である。 実施形態１の割当判定装置が実行する処理の流れを例示するフローチャートである。 リソース特徴量算出部を有する割当判定装置の構成を例示する図である。 実施形態２に係る割当判定装置を例示するブロック図である。 実施形態２の割当判定装置によって実行される処理の流れを例示するフローチャートである。 予測時間分布の 5 パーセンタイル値、50パーセンタイル値、及び 95 パーセンタイル値を用いてタスクの割り当てを判定する方法を概念的に示す図である。 実施例１の想定環境を示すブロック図である。 実施例１の分散システムに含まれる処理サーバを示す図である。 予測時間分布格納部に格納されている予測時間分布をテーブル形式で例示する図である。 予測時間分布取得部によって取得される予測時間分布の１つを示すグラフである。 予測時間分布取得部によって取得される予測時間分布の１つを示すグラフである。 予測時間分布取得部によって取得される予測時間分布の１つを示すグラフである。 実施例２の想定環境を示すブロック図である。 実施例２の分散システムに含まれる処理サーバを示す図である。 リソース特徴量取得部に入力されるリソース情報をテーブル形式で例示する図である。

以下、本発明の実施の形態について、図面を用いて説明する。尚、すべての図面において、同様な構成要素には同様の符号を付し、適宜説明を省略する。

［実施形態１］
図１は、実施形態１に係る割当判定装置２０００をその使用環境と共に例示するブロック図である。図１において、矢印は情報の流れを表している。さらに、図１において、各ブロックは、ハードウエア単位の構成ではなく、機能単位の構成を表している。

分散システム５０００は、複数の処理サーバ３０００を有する。各処理サーバ３０００には、タスクが割り当てられる。処理サーバ３０００は、サーバマシン、PC（Personal Computer）、タブレット端末など、種々の計算機である。処理サーバ３０００は、割り当てられたタスクを実行する。割当判定装置２０００は、処理サーバ３０００に対するタスクの割り当てを判定する。割当判定装置２０００は、処理サーバ３０００同様、種々の計算機である。なお、処理サーバ３０００上で実行するタスクは１つであってもよいし、複数であってもよい。

処理サーバ３０００と割当判定装置２０００は、ネットワークを介して接続されている。このネットワークは、有線回線で構成されるネットワークでもよいし、無線回線で構成されるネットワークでもよいし、有線回線と無線回線が混在するネットワークでもよい。

図２は、実施形態１の割当判定装置２０００の構成を例示するブロック図である。図２において、矢印は情報の流れを表している。さらに、図２において、各ブロックは、ハードウエア単位の構成ではなく、機能単位の構成を表している。割当判定装置２０００は、リソース特徴量取得部２０２０、予測時間分布取得部２０４０、統計量算出部２０６０、及び割当判定部２０８０を有する。以下、それぞれの機能構成部について説明する。

＜リソース特徴量取得部２０２０＞
リソース特徴量取得部２０２０は、候補処理サーバに関するリソース特徴量を取得する。候補処理サーバは、タスクを割り当てる処理サーバ３０００の候補である。リソース特徴量は、候補処理サーバによって使用されるリソースに関する特徴量である。候補処理サーバが使用するリソースは、例えば CPU、メモリ、ディスク帯域、又はネットワーク帯域などである。

＜予測時間分布取得部２０４０＞
予測時間分布取得部２０４０は、リソース特徴量取得部２０２０によって取得されたリソース特徴量に対応する予測時間分布を取得する。予測時間分布は、タスク処理時間の予測値の確率分布である。

＜統計量算出部２０６０＞
統計量算出部２０６０は、予測時間分布取得部２０４０によって取得された予測時間分布の統計量を算出する。

＜割当判定部２０８０＞
割当判定部２０８０は、統計量算出部２０６０によって算出された統計量に基づき、候補処理サーバに対するタスクの割り当てについて判定を行う。

＜作用・効果＞
前述したように、処理サーバのリソース使用率等が同一又は近い値である場合でも、タスクの処理に要する時間が異なる場合がある。図３は、処理サーバにおいてタスクを実行した場合におけるディスク I/O 使用率とタスク処理時間との関係を実測した結果を示すグラフである。ここで、タスク処理時間とは、処理サーバ３０００がタスクを処理するために要した時間を意味する。X 軸は、タスク実行時の平均ディスク I/O 使用率を示し、Y 軸は、そのタスクを実行した際のタスク処理時間を示す。各プロットは、実測されたディスク I/O 使用率とタスク処理時間との組み合わせを示す。

グラフ１０から４０はそれぞれ、ディスク I/O 使用率と、そのディスク I/O 使用率に対応するタスク処理時間の予測値（以下、予測時間）との関係を示す関数である。グラフ１０から４０は、実測されたディスク I/O 使用率とタスク処理時間との関係に基づき、それぞれ異なる方法で生成された関数である。グラフ１０は、全てのタスク処理時間の平均値を予測時間とするグラフである。グラフ２０は、全てのプロットを用いて線形回帰を行うことで生成された関数である。グラフ３０は、全てのプロットを M/M1 待ち行列モデルに適用することで生成されたグラフである。グラフ４０は、全てのプロットを M/D/1 待ち行列モデルに適用することで生成されたグラフである。

ここで、図３の範囲８０に着目する。範囲８０には多くのプロットが含まれている。これは、ディスク I/O 使用率が高い場合（例：７０％）でも、タスクの処理に要する時間が短いことがある（例：２０秒）ことを示している。

しかし、グラフ２０から４０を用いてタスク処理時間を予測する場合には、範囲８０に含まれる予測時間よりも大きな値が算出される。ここで通常、新たなタスクは処理時間の予測値が小さい処理サーバに対して割り当てられる。そのため、図３の状況においてグラフ２０から４０を用いてタスク処理時間を予測すると、ディスク I/O 使用率が高い場合には、この処理サーバに対してタスクが割り当てられなくなる。その結果、この処理サーバは効率的に利用されない。また、グラフ１０を用いて予測時間を算出すると、リソース使用率が考慮されない。そのため、グラフ１０を用いた場合も、この処理サーバは効率的に利用されない。

これに対し、割当判定装置２０００は、候補処理サーバに関するリソース特徴量に対応する予測時間分布を取得する。図４は、複数のリソース特徴量それぞれに対応する予測時間分布を概念的に示す図である。グラフ５０は、ディスク I/O 使用率が４０％の場合に対応する予測時間分布であり、グラフ６０は、ディスク I/O 使用率が６０％の場合に対応する予測時間分布であり、グラフ７０は、ディスク I/O 使用率が８０％の場合に対応する予測時間分布である。

予測時間分布取得部２０４０によって取得される予測時間分布の統計量を算出すると、その統計量には、リソース特徴量が同一の値又は近い値である場合における予測時間のばらつきが反映されるようになる。例えば、予測時間分布取得部２０４０が、グラフ７０で表される予測時間分布を取得したとする。グラフ７０は、ディスク I/O 使用率が 80% であるという条件下において、予測時間にばらつきがあることを示している。具体的には、グラフ７０は、「予測時間が７０秒程度になる確率が高いものの、予測時間が３０秒以下になることもある」ということを示している。そして、グラフ７０で表される予測時間分布の統計量を算出すると、その統計量には、このような予測時間のばらつきが反映される。

本実施形態の割当判定装置２０００によれば、リソース特徴量に応じた予測時間分布が表す予測時間のばらつきを反映する統計量に基づいて、候補処理サーバに対してタスクの割り当てについて判定が行われる。このようにすることで、「リソース特徴量が同一の値又は近い値である場合における予測時間のばらつき」を考慮して、タスクの割り当てに関する判定が行われる。その結果、例えば、「リソース使用率が高いときでも処理時間が短いことがある」という処理サーバに対してもタスクを割り当ててよいと判定される。よって、本実施形態の割当判定装置２０００によれば、処理サーバをより効率的に利用することができる。

＜ハードウエア構成＞
図５は、割当判定装置２０００のハードウエア構成を例示するブロック図である。図５において、割当判定装置２０００は、バス１０２０、プロセッサ１０４０、メモリ１０６０、ストレージ１０８０、及びネットワークアダプタ１１００を有する。

バス１０２０は、プロセッサ１０４０、メモリ１０６０、ストレージ１０８０及びネットワークアダプタ１１００が、相互にデータを送受信するためのデータ伝送路である。プロセッサ１０４０は、例えば 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) をリソース特徴量として取得する。

また、待ち行列モデル M/M/1 を仮定すると、タスク処理時間とリソースの待ち数との間には、以下の数式（２）で示す関係が成り立つ。数式（２）における各記号の意味は、数式（１）における各記号の意味と同様である。例えばリソース特徴量取得部２０２０は、数式（２）を用いて算出された x+1 をリソース特徴量として取得する。

また、リソース特徴量取得部２０２０が取得するリソース特徴量は、複数種類のリソースそれぞれに関するリソース特徴量を用いて算出された１つの値であってもよい。複数のリソース特徴量から１つのリソース特徴量を算出する具体的な方法は、例えば以下の数式（３）を用いる方法である。ri は各リソースに関するリソース特徴量であり、R はこれら各リソース特徴量を用いて算出されるリソース特徴量である。例えばリソース特徴量取得部２０２０は、数式（３）を用いて算出された R をリソース特徴量として取得する。

また、割当判定装置２０００は、上述した各数式などを用いてリソース特徴量を算出する機能を有してもよい。この機能を持つ機能構成部を、リソース特徴量算出部２１００と表記する。図７は、リソース特徴量算出部２１００を有する割当判定装置２０００の構成を例示する図である。

リソース特徴量算出部２１００は、サーバのリソース使用状況を表す情報（以下、リソース情報）を取得し、そのリソース情報に基づいてリソース特徴量を算出する。リソース情報が示す値は、例えばリソース使用率、リソース使用量、又はリソースの待ち数などである。そして、リソース特徴量算出部２１００は、リソース使用率等からリソース特徴量を算出する。例えばリソース特徴量算出部２１００は、リソース使用率を取得し、数式（１）を用いてリソース特徴量を算出する。

例えばリソース特徴量算出部２１００は、リソース情報が示す値の種類に応じて、リソース特徴量の算出方法を決定する。この場合、リソース情報は、値とその値の種類（例：リソース使用率や待ち数など）との組み合わせを示す。そして、リソース特徴量算出部２１００は、リソース情報が示す値の種類に応じた方法を用いて、リソース特徴量を算出する。ただし、リソース特徴量算出部２１００が取得する値の種類は、予め固定されていてもよい。この場合、リソース特徴量算出部２１００は、予め固定されている値の種類に応じた算出方法でリソース特徴量を算出する。

リソース特徴量取得部２０２０がリソース特徴量を入手する方法は様々である。例えばリソース特徴量取得部２０２０は、外部の装置から入力されるリソース特徴量を取得する。その他にも例えば、リソース特徴量取得部２０２０は、手動で入力されるリソース特徴量を取得する。さらにリソース特徴量取得部２０２０は、外部の装置にアクセスして、リソース特徴量を取得してもよい。例えば、上記外部の装置は、処理サーバである。また、分散システムにおいて処理サーバを管理する管理サーバがある場合、リソース特徴量取得部２０２０は、この管理サーバからリソース特徴量を取得してもよい。

割当判定装置２０００がリソース特徴量算出部２１００を有する場合、リソース特徴量算出部２１００は、前述のリソース特徴量取得部２０２０がリソース特徴量を入手する方法と同様の方法でリソース情報を取得する。この場合、リソース特徴量取得部２０２０は、リソース特徴量算出部２１００によって算出されたリソース特徴量を取得する。また、リソース特徴量取得部２０２０は、リソース特徴量算出部２１００のよって算出されたリソース特徴量と、外部から提供されるリソース特徴量の双方を取得してもよい。

＜予測時間分布取得部２０４０の詳細＞
予測時間分布取得部２０４０は、リソース特徴量に応じた予測時間分布を取得する。例えば、図４で示す例において、リソース特徴量取得部２０２０が「ディスク I/O 使用率が 80% である」というリソース特徴量を取得したとする。この場合、予測時間分布取得部２０４０は、グラフ７０によって表される予測時間分布を取得する。同様の例において、リソース特徴量取得部２０２０が「ディスク I/O 使用率が 40% である」というリソース特徴量を取得したとする。この場合、予測時間分布取得部２０４０は、グラフ５０によって表される予測時間分布を取得する。

また例えば、予測時間分布取得部２０４０は、リソース特徴量を条件とする予測時間の条件付き分布を取得する。そして、予測時間分布取得部２０４０は、取得した条件付き分布に、リソース特徴量取得部２０２０によって取得されたリソース特徴量を適用することで、リソース特徴量に対応する予測時間分布を取得する。

予測時間分布は、処理サーバ３０００ごとに用意されていてもよいし、複数の処理サーバ３０００に共通して用意されていてもよい。また、予測時間分布は、構成が類似する処理サーバ３０００のグループごとに用意されてもよい。予測時間分布が処理サーバ３０００ごとや処理サーバ３０００のグループごとに用意されている場合、例えば予測時間分布取得部２０４０は、リソース特徴量と、候補処理サーバの ID 又は候補処理サーバが属するグループの ID とに対応する予測時間分布を取得する。

予測時間分布取得部２０４０が予測時間分布を取得する方法は様々である。例えば予測時間分布取得部２０４０は、リソース特徴量と対応付けて予測時間分布を格納している予測時間分布格納部から、リソース特徴量に対応する予測時間分布を取得する。予測時間分布格納部は、割当判定装置２０００の内部に設けられてもよいし、割当判定装置２０００の外部に設けられてもよい。また例えば、割当判定装置２０００は、予測時間分布を生成する装置（以下、予測時間分布生成装置）に対してリソース特徴量を入力し、予測時間分布生成装置によって出力された予測時間分布を取得してもよい。

＜割当判定部２０８０の詳細＞
割当判定部２０８０が行う、「候補処理サーバに対するタスクの割り当てに関する判定」は様々である。例えば割当判定部２０８０は、候補処理サーバに対してタスクを割り当てるという判定、又は候補処理サーバに対してタスクを割り当てないという判定を行う。また例えば、割当判定部２０８０は、候補処理サーバに対して「タスクを割り当ててもよい」という判定を行ってもよい。「タスクを割り当ててもよい」と判定された候補処理サーバは、例えばその他の条件を満した場合に、タスクが割り当てられる。「その他の条件」としては、任意の条件を設定することが可能である。

＜候補処理サーバの決定＞
割当判定装置２０００が複数の処理サーバ３０００の中から候補処理サーバを選択する方法は様々である。例えば割当判定装置２０００は、処理サーバ３０００からタスク割り当ての要求を受信し、その要求を送信した処理サーバ３０００を候補処理サーバとして選択する。その他にも例えば、割当判定装置２０００は、分散システム５０００に含まれる処理サーバ３０００の中から、候補処理サーバとする処理サーバ３０００を順次選択したり、ランダムに選択したりする。また例えば、割当判定装置２０００は、外部の装置や人手による処理サーバ３０００の指定を受け付けてもよい。また例えば、割当判定装置２０００は、外部の装置にアクセスして処理サーバ３０００を候補処理サーバとするかを示す情報を取得してもよい。

ここで、割当判定装置２０００は、割当判定部２０８０によって「タスクを割り当てない」と判定された処理サーバ３０００を、所定期間が経過するまで候補処理サーバとして選択しないようにしてもよい。こうすることで、割当判定装置２０００が判定対象とする処理サーバ３０００を絞り込むことができるため、割当判定装置２０００にかかる負荷が小さくなる。

[実施形態２]
図８は、実施形態２に係る割当判定装置２０００を例示するブロック図である。図８において、矢印は情報の流れを表している。さらに、図８において、各ブロックは、ハードウエア単位の構成ではなく、機能単位の構成を表している。

実施形態２の割当判定装置２０００は、タスク種別取得部２１２０を有する。タスク種別取得部２１２０は、候補処理サーバに割り当てるタスクの種別（タスク種別）を取得する。さらに、実施形態２の予測時間分布取得部２０４０は、リソース特徴量取得部２０２０によって取得されたリソース特徴量及びタスク種別取得部２１２０によって取得されたタスク種別に対応する予測時間分布を取得する。

タスクのタスク種別は、例えばそのタスクが属するジョブのＩＤで表される。また例えば、タスク種別は、ジョブのフェーズのＩＤや、ジョブのＩＤとフェーズのＩＤとの組み合わせなどで表されてもよい。

＜処理の流れ＞
図９は、実施形態２の割当判定装置２０００によって実行される処理の流れを例示するフローチャートである。図９において、図６と同符号のステップでは、図６の場合と同様の処理が行われる。

ステップＳ２０２において、タスク種別取得部２１２０は、候補処理サーバに割り当てようとしているタスクのタスク種別を取得する。ステップＳ２０４において、予測時間分布取得部２０４０は、リソース特徴量及びタスク種別に対応する予測時間分布を取得する。

＜作用・効果＞
本実施形態によれば、タスク種別及びリソース特徴量に対応する予測時間分布を用いて、タスクの割り当てが行われる。ここで、同一のタスク種別に含まれるタスクは、通常、処理速度の分布が類似していることが多いと考えられる。そこで、割当判定装置２０００が利用する予測時間分布を、タスク種別ごとに生成しておくようにする。こうすることで、予測時間分布によって表される予測時間の分布が、候補処理サーバに割り当てようとしているタスクの処理に要する時間の予測値の分布をより高い精度で表すようになるため、より効率的に処理サーバ３０００を利用できるようになる。

[実施形態３]
実施形態３に係る割当判定装置２０００の構成は、実施形態１の割当判定装置２０００と同様に図２で表される。以下で説明する点を除き、実施形態３の割当判定装置２０００は、実施形態１又は２の割当判定装置２０００と同様である。

＜統計量算出部２０６０＞
実施形態３の統計量算出部２０６０は、予測時間分布の統計量として、予測時間分布の代表値を算出する。統計量算出部２０６０が算出する代表値は様々である。例えば統計量算出部２０６０が算出する代表値は、予測時間分布が示す予測時間の最大値、最小値、平均値、X パーセンタイル値（0<X<100）、又は四分位点などである。

その他にも例えば、統計量算出部２０６０は、直接法と呼ばれる方法を用いて予測時間分布の代表値を算出する。具体的には、まず統計量算出部２０６０は、一様乱数 y を生成する。そして、統計量算出部２０６０は、一様乱数 y が以下の数式（４）を満たすように、数式（４）における x の値を算出する。ここで数式（４）における f(x) は、予測時間分布取得部２０４０が取得した予測時間分布である。そして、統計量算出部２０６０は、算出した x を予測時間分布の代表値とする。

＜割当判定部２０８０＞
割当判定部２０８０は、統計量算出部２０６０によって算出された代表値を用いて、候補処理サーバに対するタスクの割り当てについて判定を行う。例えば割当判定部２０８０は、代表値が所定値を超える場合、候補処理サーバにタスクを割り当てないと判定する。

また例えば、割当判定部２０８０は、複数の候補処理サーバそれぞれについて算出された代表値を比較することで、候補処理サーバに対するタスク割り当てについて判定してもよい。この場合、リソース特徴量取得部２０２０は、複数の候補処理サーバそれぞれについてリソース特徴量を取得する。また、予測時間分布取得部２０４０は、各候補処理サーバについて、その候補処理サーバのリソース特徴量に対応する予測時間分布を取得する。そして、統計量算出部２０６０は、複数の候補処理サーバそれぞれについて取得された予測時間分布について、それぞれ代表値を算出する。

複数の候補処理サーバについて算出された代表値を比較する方法は様々である。例えば割当判定部２０８０は、代表値が最も小さい候補処理サーバに対してタスクを割り当てると判定する。また例えば、割当判定部２０８０は、代表値が小さい順に候補処理サーバを並べた場合における上位 N 個の候補処理サーバに対し、タスクを割り当ててもよいと判定する。また例えば、割当判定部２０８０は、各代表値を用いて、代表値の確率分布を生成する。そして、割当判定部２０８０は、代表値がこの確率分布の所定範囲に含まれる候補処理サーバについてのみ、タスクを割り当ててよいと判定する。上記所定範囲は、例えば、確率分布の平均値をμ、標準偏差をσとした場合において、[μ−σ、μ＋σ] で表される。

＜＜タスクを割り当ててもよい候補処理サーバが複数ある場合について＞＞
タスクを割り当ててもよいと判定された候補処理サーバが複数ある場合に、割当判定部２０８０がタスクを割り当てる候補処理サーバを決定する方法は様々である。例えば割当判定部２０８０は、タスクを割り当ててもよいと判定された候補処理サーバのうち、負荷（リソース使用率やリソース使用量）が最も高い候補処理サーバに対してタスクを割り当てる。これにより、負荷が高い処理サーバ３０００がより積極的に利用されるようになる。逆に、割当判定部２０８０は、タスクを割り当ててもよいと判定された候補処理サーバのうち、負荷が最も低い候補処理サーバに対してタスクを割り当ててもよい。

また例えば、割当判定部２０８０は、各候補処理サーバに対して既に割り当てられているタスクの数を比較し、割り当てられるタスクの数ができる限り均等になるように、タスクを割り当てる候補処理サーバを決定する。

＜作用・効果＞
実施形態３の統計量算出部２０６０は、予測時間分布の統計量として、予測時間分布の代表値を算出する。予測時間分布の統計量として予測時間分布の代表値を用いることで、確率分布の形状の特徴をより反映したタスク割当判定を、簡便な方法で実現することができる。例えば、代表値に 95 パーセンタイル値を用いると、処理時間が 95% の確率でこの代表値以下になることが示される。したがって、例えば「代表値が閾値以下であったらタスクを割り当てる」と判定する場合、判定結果が 95% の確率で正しくなることが示される。これにより、タスク割り当ての判定精度がより高くなる蓋然性が高まる。

また例えば、代表値に直接法を用いた予測処理時間を用いると、確率分布に従った予測処理時間を直接求めることができる。したがって、この代表値からタスク割り当てを判定した場合、よりきめ細やかにタスクの割り当てを行うことができるようになる。これにより、タスクの処理時間が短くなる蓋然性が高まる。

[実施形態４]
実施形態４に係る割当判定装置２０００の構成は、実施形態１の割当判定装置２０００と同様に図２で表される。以下で説明する点を除き、実施形態４の割当判定装置２０００は、実施形態１又は２の割当判定装置２０００と同様である。

＜統計量算出部２０６０＞
実施形態４の統計量算出部２０６０は、予測時間分布の統計量として、予測時間分布の散布度を算出する。統計量算出部２０６０が算出する散布度は様々である。例えば統計量算出部２０６０が算出する散布度は、予測時間分布が示す予測時間の標準偏差、分散、又は X パーセンタイル値と Y パーセンタイル値の差（0<X<100、0<Y<100）などである。X パーセンタイル値と Y パーセンタイル値の差としては、例えば 95 パーセンタイル値と 5 パーセンタイル値の差を用いる。

＜割当判定部２０８０＞
例えば割当判定部２０８０は、統計量算出部２０６０によって算出された散布度を用いて、候補処理サーバに対するタスクの割り当てについて判定する。例えば割当判定部２０８０は、散布度が所定値を超える場合、候補処理サーバにタスクを割り当てない。散布度が大きいと、処理時間が長くなるリスクが大きいと考えられるためである。

また例えば割当判定部２０８０は、予測時間分布の分布が小さい値に偏っている場合に、タスクを割り当ててよいと判定する。予測時間分布が小さい値に偏っていると、処理時間が短くなる蓋然性が高いと考えられるためである。具体的には、次の方法で処理を行う。まず、統計量算出部２０６０は、予測時間分布の（50-X）パーセンタイル値、50パーセンタイル値、及び（50+X）パーセンタイル値をそれぞれ算出する。ここで、X は 0<x<50 を満たす実数である。例えば X の値として 45 を用いる。この場合、5 パーセンタイル値、50 パーセンタイル値、及び 95 パーセンタイル値を用いることになる。

そして、統計量算出部２０６０は、（50+X）パーセンタイル値と 50 パーセンタイル値との差分を第１散布度として算出する。また、統計量算出部２０６０は、50 パーセンタイル値と（50-X）パーセンタイル値との差分を第２散布度として算出する。

割当判定部２０８０は、第１散布度と第２散布度とを比較する。そして、第１散布度が第２散布度より小さい場合のみ、候補処理サーバに対してタスクを割り当てると判定する。

図１０は、予測時間分布の 5 パーセンタイル値、50パーセンタイル値、及び 95 パーセンタイル値を用いてタスクの割り当てを判定する方法を概念的に示す図である。図１０において、5 パーセンタイル値は 10 であり、50 パーセンタイル値は 35 であり、95 パーセンタイル値は 90 である。したがって、第１散布度は 25 であり、第２散布度は 65 である。そのため、図１０のグラフは、予測時間が小さい方に偏ったグラフとなっている。

また例えば、割当判定部２０８０は、複数の候補処理サーバそれぞれについて算出された散布度を比較することで、タスク割り当てに関する判定を行ってもよい。この場合、リソース特徴量取得部２０２０は、複数の候補処理サーバそれぞれについてリソース特徴量を取得する。また、予測時間分布取得部２０４０は、各候補処理サーバについて、その候補処理サーバのリソース特徴量に対応する予測時間分布を取得する。そして、統計量算出部２０６０は、複数の候補処理サーバそれぞれについて取得された予測時間分布について、それぞれ散布度を算出する。

複数の候補処理サーバについて算出された散布度を比較する方法は様々である。例えば割当判定部２０８０は、散布度が最も大きい候補処理サーバに対してはタスクを割り当てないと判定する。また例えば、割当判定部２０８０は、散布度が大きい順に候補処理サーバを並べた場合における上位 N 個の候補処理サーバに対しては、タスクを割り当てないと判定する。また例えば、割当判定部２０８０は、各散布度を用いて、散布度の確率分布を生成する。そして、割当判定部２０８０は、散布度がこの確率分布の所定範囲に含まれる候補処理サーバについてのみ、タスクを割り当ててよいと判定する。例えば散布度の所定範囲は、実施形態３で説明した代表値の所定範囲と同様である。

＜＜タスクを割り当ててもよい候補処理サーバが複数ある場合について＞＞
実施形態４の割当判定部２０８０が、タスクを割り当ててもよいと判定された候補処理サーバが複数ある場合にタスクを割り当てる候補処理サーバを決定する方法は、実施形態３の割当判定部２０８０が行う方法と同様である。

＜作用・効果＞
実施形態４の統計量算出部２０６０は、予測時間分布の統計量として、予測時間分布の散布度を算出する。予測時間分布の統計量として予測時間分布の散布度を用いることで、処理時間の散らばり度合をより反映したタスク割り当て判定を、簡便な方法で実現することが可能になる。例えば、散布度に歪度を用いると、歪度の絶対値や正負の符号を検査することで、ある負荷での予測処理時間の分布が小さくなりやすいのか大きくなりやすいのかを判定することが可能になる。これにより、タスクを割り当てた際に処理時間が短くなる蓋然性が高まる。

[実施例１]
＜想定環境＞
実施形態１に係る割当判定装置２０００の具体的な動作例を、実施例１として説明する。図１１は実施例１の想定環境を示す図である。図１１において、矢印は情報の流れを表している。さらに、図１１において、各ブロックは、ハードウエア単位の構成ではなく、機能単位の構成を表している。

＜＜割当判定装置２０００＞＞
実施例１の割当判定装置２０００は、実施形態２の割当判定装置２０００と同様の構成を有する。また、実施例１の統計量算出部２０６０は、予測時間分布の統計量として、予測時間分布の代表値を算出する。ここで、統計量算出部２０６０は、前述した直接法を用いて予測時間分布の代表値を算出する。実施例１の割当判定部２０８０は、候補処理サーバのリソース特徴量及びタスク種別の組み合わせについて取得した予測時間分布の代表値が90 秒を超える場合、そのタスク種別のタスクについては、その候補処理サーバに対して割り当てないと判定する。

＜＜分散システム５０００＞＞
分散システム５０００は、マスタサーバ４０００及び複数の処理サーバ３０００を有する。マスタサーバ４０００は、処理サーバ３０００を管理するサーバである。

＜＜処理サーバ３０００＞＞
処理サーバ３０００は、タスク実行部３０２０、リソース情報格納部３０４０、及びタスク情報格納部３０６０を有する。タスク実行部３０２０は、１つ又は複数のタスクを実行する。例えばタスク実行部３０２０は、プロセス、スレッド、又は仮想マシンなどである。処理サーバ３０００は、複数のタスク実行部３０２０を有してもよい。

リソース情報格納部３０４０はリソース情報を格納する。前述した通り、リソース情報は、例えばリソース使用率など、サーバのリソース使用状況を表す情報である。なお、処理サーバ３０００において各リソースの使用量などを計測する方法は既知の技術である。そのため、その方法については説明を省略する。

タスク情報格納部３０６０は、タスクに関する情報（タスク情報）を格納する。タスク情報格納部３０６０に格納されているタスク情報は、タスク実行部３０２０が実行しているタスク又はタスク実行部３０２０が過去に実行したタスクに関するタスク情報である。

＜＜マスタサーバ４０００＞＞
マスタサーバ４０００は、タスク実行管理部４０２０、リソース情報管理部４０４０、及びタスク情報管理部４０６０を有する。タスク実行管理部４０２０は、処理サーバ３０００に対してタスクを割り当てる処理や、処理サーバ３０００に対してタスクの開始又は中止を指示する処理などを行う。リソース情報管理部４０４０は、各処理サーバ３０００のリソース情報格納部３０４０からリソース情報を収集して管理する。タスク情報管理部４０６０は、分散システム５０００において実行されるタスクを管理する。そのために、タスク情報管理部４０６０は、各処理サーバ３０００のタスク情報格納部３０６０からタスク情報を収集して管理する。また、タスク情報管理部４０６０は、まだ処理サーバ３０００に割り当てられていないタスクに関する情報も管理している。

タスク実行管理部４０２０は、処理サーバ３０００のリソースに関する情報をリソース情報管理部４０４０から取得して、リソース特徴量取得部２０２０に対して入力する。さらに、タスク実行管理部４０２０は、処理サーバ３０００に割り当てる対象のタスク（以下、対象タスク）のタスク種別をタスク情報管理部４０６０から取得して、タスク種別取得部２１２０に対して入力する。割当判定装置２０００は、その処理サーバ３０００に対するタスクの割り当てについて判定を行い、判定結果をタスク実行管理部４０２０へ通知する。タスク実行管理部４０２０は、割当判定装置２０００から取得した判定結果に基づいて、処理サーバ３０００に対するタスクの割り当てを行う。

＜＜予測時間分布格納部６０００＞＞
予測時間分布格納部６０００は、タスク種別及びリソース特徴量に対応付けて予測時間分布を格納する。

図１２は、実施例１の分散システム５０００に含まれる処理サーバ３０００を示す図である。実施例１の分散システム５０００は、処理サーバ３０００として、コンピュータ c1 及び c2 を備えている。コンピュータ c1 と c2 は、１台のネットワークスイッチを介して接続されている。コンピュータ c1 は、タスク実行部３０２０として、プロセス P1 とP2 を有する。また、コンピュータ c2 は、タスク実行部３０２０として、プロセス P3 と P4 を有する。プロセス P1 はタスク T1 を実行しており、プロセスP3 はタスク T2 を実行している。なお、図１２において、マスタサーバ４０００は省略されている。

＜処理の具体例＞
以下、上述した想定環境で行われる処理の具体例を説明する。ここで、プロセス P2 が空いているために、コンピュータ c1 がマスタサーバ４０００に対してタスクの割り当てを要求したとする。するとマスタサーバ４０００は、次に割り当てるタスクを決定する。マスタサーバ４０００は、ジョブ間の資源割り当て量を均衡にする等の目的で、まず Type Aのタスクの割り当てを試みる。そこで、タスク実行管理部４０２０は、タスク種別取得部２１２０に対して Type A というタスク種別を入力する。また、タスク実行管理部４０２０は、候補処理サーバであるコンピュータ c1 のリソースに関するリソース特徴量をリソース特徴量取得部２０２０に入力する。ここで、コンピュータ c1 のリソース特徴量として、「ディスク I/O 発行率 = 90%」が入力されたとする。

図１３は、予測時間分布格納部６０００が格納している予測時間分布をテーブル形式で例示する図である。図１３に示されているテーブルを予測時間分布テーブル１００と表記する。予測時間分布テーブル１００は、タスク種別１０２、平均値１０４、及び標準偏差１０６という３つの列を有する。予測時間分布テーブル１００の各レコードは、タスク種別１０２で示されるタスク種別に対応付けて、平均値１０４及び標準偏差１０６で定まる正規分布を示す。

予測時間分布取得部２０４０は、予測時間分布格納部６０００から、「タスク種別１０２ = TypeA」に対応する平均値１０４及び標準偏差１０６を取得する。その結果、予測時間分布取得部２０４０は、平均値１０４として 10/(1-ρ)+5 を取得し、標準偏差１０６として 100ρ/3 を取得する。ここで、ρはディスク I/O 発行率を表す。

そして、予測時間分布取得部２０４０は、取得した平均値１０４及び標準偏差１０６に対して、「ディスク I/O 発行率（ρ）= 90%」を適用する。これにより、平均値は105 秒となり、標準偏差は 30 秒となる。この結果、予測時間分布取得部２０４０は、平均値が 105 秒であり、標準偏差が 30 秒である正規分布を得る。つまり、予測時間分布取得部２０４０は、「タスク種別 = TypeA」及び「ディスク I/O 発行率 = 90%」に対応する予測時間分布として、平均値が 105 秒であり、かつ標準偏差 30 秒である正規分布を取得する。図１４は、この予測時間分布を示すグラフである。

統計量算出部２０６０は、直接法を用いて予測時間分布の代表値を算出する。ここで、統計量算出部２０６０が算出した代表値が、110 秒 であるとする。

割当判定部２０８０は、算出された代表値を用いて、コンピュータ c1 に対する Type A のタスクの割り当てについて、判定を行う。前述したように、割当判定部２０８０は、候補処理サーバのリソース特徴量及びタスク種別の組み合わせについて取得した予測時間分布の代表値が90 秒を超える場合、そのタスク種別のタスクについては、その候補処理サーバに対して割り当てないと判定する。統計量算出部２０６０によって算出された代表値は 110 秒であり、90 秒を超えているため、割当判定部２０８０は、タスク種別が Type A であるタスクについては、コンピュータ c1 に対して割り当てないと判定する。

次に、マスタサーバ４０００は、コンピュータ c1 に対して Type B のタスクを割り当てようとしたとする。タスク実行管理部４０２０は、タスク種別取得部２１２０に対して、「タスク種別 = Type B」を入力する。また、タスク実行管理部４０２０は、リソース特徴量取得部２０２０に対して、「ディスク I/O 発行率 = 90%」を入力する。

予測時間分布取得部２０４０は、「タスク種別 = Type B」かつ「ディスク I/O 発行率 = 90%」に対応する予測時間分布を取得する。図１３に示すように、「タスク種別 = Type B」に対応するのは、平均値が 1/(1-ρ)+10、かつ標準偏差が 5ρの正規分布である。予測時間分布取得部２０４０は、この正規分布に「ディスク I/O 発行率 = 90%」を適用することで、平均値が20秒であり、かつ標準偏差4.5秒である正規分布を得る。つまり、予測時間分布取得部２０４０は、「タスク種別 = Type B」かつ「ディスク I/O 発行率 = 90%」に対応する予測時間分布として、平均値が20秒であり、かつ標準偏差4.5秒である正規分布を取得する。図１５は、この予測時間分布を示すグラフである。

統計量算出部２０６０は、予測時間分布の代表値を算出する。算出された代表値は、19 秒であるとする。

割当判定部２０８０は、コンピュータ c1 に対する Type B のタスクの割り当てについて、判定を行う。統計量算出部２０６０によって算出された代表値は 19 秒であり、90 秒より小さい。そこで、割当判定部２０８０は、コンピュータ c1 に対し、タスク種別が Type B であるタスクの割り当てを行うと判定する。その結果、コンピュータ c1 のプロセス P2 に対して、Type Bのタスクが割り当てられる。

さらに、コンピュータ c2 がプロセス P4 に対するタスク割り当てをマスタサーバ４０００に要求したとする。マスタサーバ４０００が Type A のタスクの割り当てを試みたとする。また、このときのコンピュータ c2 のディスクI/O発行率が 50% とする。すると、タスク実行管理部４０２０は、リソース特徴量取得部２０２０に対して「ディスクI/O発行率 = 50%」を入力し、タスク種別取得部２１２０に対して「タスク種別 = Type A」を入力する。

その結果、予測時間分布取得部２０４０は、平均値が25秒であり、かつ標準偏差が 30 秒である正規分布を、予測時間分布として取得する。図１６は、この予測時間分布を示すグラフである。

統計量算出部２０６０は、予測時間分布の代表値を算出する。ここで、算出された代表値は50 秒であるとする。この代表値は 90 秒より小さいため、割当判定部２０８０は、コンピュータ c2 に対して タスク種別が Type A であるタスクを割り当てると判定する。この結果、タスク実行管理部４０２０は、タスク種別が Type A であるタスクを、コンピュータ c2 のプロセス P4 に対して割り当てる。

さらに、コンピュータ c1 のプロセス P2 がタスクの実行を完了し、コンピュータ c1 がタスク割り当てをマスタサーバ４０００に要求したとする。ここで、マスタサーバが c1 に対して Type A のタスクを割り当てようとしたとする。タスク実行管理部４０２０は、リソース特徴量取得部２０２０に対して「ディスクI/O発行率 = 90%」を入力し、タスク種別取得部２１２０に対して「タスク種別 = Type A」を入力する。その結果、予測時間分布取得部２０４０は、平均値が105秒であり、かつ標準偏差30秒である正規分布を、予測時間分布として取得する（図１４参照）。

統計量算出部２０６０は、予測時間分布の代表値を算出する。ここで、統計量算出部２０６０が、代表値として 50 秒を算出したとする。この場合、代表値である 50 秒が 90 秒より小さいため、割当判定部２０８０は、コンピュータ c1 に対してタスクを割り当てると判定する。その結果、コンピュータ c1 のプロセス P2 に対して、タスク種別が Type A であるタスクが割り当てられる。

ここで、上述の例において、「ディスクI/O発行率 = 90%」かつ「タスク種別 = Type A」の場合について、タスクを割り当てないと判定される場合と、タスクを割り当てると判定される場合の双方があった。これは、統計量算出部２０６０が直接法を用いて、予測時間分布に従うランダムな値を代表値として算出したためである。このことから、「リソース使用率が同一又は近い場合におけるタスク処理時間のばらつき」が考慮されていることが分かる。

[実施例２]
割当判定装置２０００の別の実施例を、実施例２として説明する。下記で説明する点を除き、実施例２の想定環境は、実施例１の想定環境と同様である。図１７は実施例１の想定環境を示す図である。図１１において、矢印は情報の流れを表している。さらに、図１１において、各ブロックは、ハードウエア単位の構成ではなく、機能単位の構成を表している。

実施例２では、割当判定装置２０００がタスク種別取得部２１２０を有していない点が、実施例１と異なる。したがって、実施例２の想定環境を割当判定装置２０００は、タスク種別は考慮せず、リソース特徴量に対応する予測時間分布を取得する。

予測時間分布取得部２０４０は、複数の候補処理サーバそれぞれについて予測時間分布を取得する。統計量算出部２０６０は、複数の候補処理サーバそれぞれについて予測時間分布の代表値を算出する。割当判定部２０８０は、算出された複数の代表値を用いて確率分布を生成する。そして、割当判定部２０８０は、各候補処理サーバについて、その候補処理サーバについて算出した代表値が、上記確率分布における [μ−２σ, μ＋２σ] の範囲にある場合のみ、その候補処理サーバに対してタスクを割り当ててよいと判定する。ここで、μは確率分布の平均値であり、σは確率分布の標準偏差である。

図１８は、実施例２の分散システム５０００に含まれる処理サーバ３０００を示す図である。実施例２の分散システム５０００は、処理サーバ３０００として、コンピュータ c1 から c3 の３台を備えている。各コンピュータは、ネットワークスイッチを介して接続されている。各コンピュータは、タスク実行部３０２０として複数のプロセスを有する。具体的には、コンピュータ c1 はプロセス P1 とP2 を有し、コンピュータ c2 はプロセス P3 と P4 を有し、コンピュータ c3 はプロセス P5 とP6 を有する。なお、図１８において、マスタサーバ４０００は省略されている。

ここで、コンピュータ c1 がマスタサーバ４０００に対して、プロセス P2 で実行するタスクを要求したとする。マスタサーバ４０００は、コンピュータ c1 に対してタスクを割り当てるか否かを判定する。

リソース特徴量取得部２０２０には、各処理サーバ３０００のリソース特徴量を示すリソース情報が入力される。本実施例では、リソース特徴量としてネットワーク帯域利用率を利用する。図１９は、リソース特徴量取得部２０２０に入力されるリソース情報をテーブル形式で例示する図である。図１９に示されるテーブルを、リソース情報テーブル２００と表記する。リソース情報テーブル２００は、処理サーバ識別子２０２及びネットワーク帯域利用率２０４という２つの列を有する。リソース情報テーブル２００の各レコードは、処理サーバ識別子２０２で表される処理サーバ３０００に対応付けて、その処理サーバ３０００で利用されているネットワーク帯域の利用率を示す。図１９より、コンピュータ c1 に関するリソース特徴量は「ネットワーク帯域利用率 = 50%」であり、コンピュータ c2 に関するリソース特徴量は「ネットワーク帯域利用率 = 25%」であり、コンピュータ c3 に関するリソース特徴量は「ネットワーク帯域利用率 = 75%」である。

予測時間分布取得部２０４０は、コンピュータ c1、c2、c3 のそれぞれについて、予測時間分布を取得する。そして、統計量算出部２０６０は、コンピュータ c1、c2、c3 のそれぞれの予測時間分布について、代表値を算出する。ここで、算出された統計値がそれぞれ、20 秒、20 秒、80 秒であるとする。

割当判定部２０８０は、コンピュータ c1 から c3 それぞれについて、タスク割り当ての可否を判定する。割当判定部２０８０は、統計量算出部２０６０によって算出された全ての代表値の平均値μと標準偏差σを算出する。算出結果は、μ＝40 及び σ＝35 であるとする。この場合、[μ−２σ, μ＋２σ]は、[5, 75] となる。したがって、割当判定部２０８０は、あるコンピュータについて算出した代表値 x が 5<=x<=75 を満たす場合のみ、そのコンピュータに対してタスクを割り当ててよいと判定する。

コンピュータ c1 について算出した代表値は 20 であり、5≦20≦75 である。そのため、割当判定部２０８０は、コンピュータ c1 に対してタスクを割り当ててよいと判定する。同様に、コンピュータ c2 について算出した代表値も 20 であるため、割当判定部２０８０は、コンピュータ c2 に対してもタスクを割り当ててよいと判定する。一方、コンピュータ c3 について算出した代表値は 80 であり、[5, 75] の範囲外である。よって、割当判定部２０８０は、コンピュータ c3 にはタスクを割り当てないと判定する。

以上、図面を参照して本発明の実施形態について述べたが、これらは本発明の例示であり、上記以外の様々な構成を採用することもできる。

１０、２０、３０、４０、５０、６０、７０ グラフ
８０ 範囲
１００ 予測時間分布テーブル
１０２ タスク種別
１０４ 平均値
１０６ 標準偏差
２００ リソース情報テーブル
２０２ 処理サーバ識別子
２０４ ネットワーク帯域利用率
１０２０ バス
１０４０ プロセッサ
１０６０ メモリ
１０８０ ストレージ
１１００ ネットワークアダプタ
１２２０ リソース特徴量取得モジュール
１２４０ 予測時間分布取得モジュール
１２６０ 統計量算出モジュール
１２８０ 割当判定モジュール
２０００ 割当判定装置
２０２０ リソース特徴量取得部
２０４０ 予測時間分布取得部
２０６０ 統計量算出部
２０８０ 割当判定部
２１００ リソース特徴量算出部
２１２０ タスク種別取得部
３０００ 処理サーバ
３０２０ タスク実行部
３０４０ リソース情報格納部
３０６０ タスク情報格納部
４０００ マスタサーバ
４０２０ タスク実行管理部
４０４０ リソース情報管理部
４０６０ タスク情報管理部
５０００ 分散システム
６０００ 予測時間分布格納部

Claims (24)

1. タスクを割り当てる処理サーバの候補である候補処理サーバに関するリソース特徴量を取得するリソース特徴量取得手段と、
   前記リソース特徴量に対応する、タスク処理時間の予測値の確率分布である予測時間分布を取得する予測時間分布取得手段と、
   前記予測時間分布取得手段によって取得された予測時間分布の統計量を算出する統計量算出手段と、
   前記統計量に基づいて、前記候補処理サーバに対するタスクの割り当てについて判定を行う割当判定手段と、
   を有する割当判定装置。
2. 前記統計量算出手段は、前記予測時間分布の代表値を前記統計量として算出する請求項１に記載の割当判定装置。
3. 前記統計量算出手段は、前記予測時間分布の散布度を前記統計量として算出する請求項１に記載の割当判定装置。
4. 前記統計量算出手段は、前記予測時間分布の（50+X）パーセンタイル値と 50 パーセンタイル値との差分である第１散布度、及び前記予測時間分布の 50 パーセンタイル値と（50-X）パーセンタイル値との差分である第２散布度を算出し（0<x<50）、
   前記割当判定手段は、前記第１散布度と前記第２散布度を比較し、前記第１散布度の方が小さい場合、前記候補処理サーバに対してタスクを割り当てる請求項３に記載の割当判定装置。
5. 前記割当判定手段は、前記統計量が所定値を超えるか否かを判定し、前記統計量が前記所定値を超える場合、前記処理サーバに対してタスクを割り当てない請求項１乃至４いずれか一項に記載の割当判定装置。
6. 前記統計量算出手段は、複数の前記候補処理サーバそれぞれのリソース特徴量に対応する予測時間分布に基づいて、複数の前記候補処理サーバそれぞれについて予測時間分布の統計量を算出し、
   前記割当判定手段は、複数の前記候補処理サーバそれぞれについて算出された統計量を比較し、その比較結果に基づいて、複数の前記候補処理サーバのいずれかにタスクを割り当てる請求項１乃至３いずれか一項に記載の割当判定装置。
7. 前記候補処理サーバに割り当てるタスクの種別であるタスク種別を取得するタスク種別取得手段を有し、
   前記予測時間分布取得手段は、前記リソース特徴量及び前記タスク種別に対応する前記予測時間分布を取得する請求項１乃至６いずれか一項に記載の割当判定装置。
8. 前記予測時間分布取得手段は、複数のリソース特徴量それぞれに対応付けて前記予測時間分布を格納している予測時間分布格納手段から、前記リソース特徴量取得手段によって取得されたリソース特徴量に対応する予測時間分布を取得する請求項１乃至７いずれか一項に記載の割当判定装置。
9. 割当判定装置として動作するコンピュータによって実行される制御方法であって、
   タスクを割り当てる処理サーバの候補である候補処理サーバに関するリソース特徴量を取得するリソース特徴量取得ステップと、
   前記リソース特徴量に対応する、タスク処理時間の予測値の確率分布である予測時間分布を取得する予測時間分布取得ステップと、
   前記予測時間分布取得ステップで取得された予測時間分布の統計量を算出する統計量算出ステップと、
   前記統計量に基づいて、前記候補処理サーバに対するタスクの割り当てについて判定を行う割当判定ステップと、
   を有する制御方法。
10. 前記統計量算出ステップは、前記予測時間分布の代表値を前記統計量として算出する請求項９に記載の制御方法。
11. 前記統計量算出ステップは、前記予測時間分布の散布度を前記統計量として算出する請求項９に記載の制御方法。
12. 前記統計量算出ステップは、前記予測時間分布の（50+X）パーセンタイル値と 50 パーセンタイル値との差分である第１散布度、及び前記予測時間分布の 50 パーセンタイル値と（50-X）パーセンタイル値との差分である第２散布度を算出し（0<x<50）、
    前記割当判定ステップは、前記第１散布度と前記第２散布度を比較し、前記第１散布度の方が小さい場合、前記候補処理サーバに対してタスクを割り当てる請求項１１に記載の制御方法。
13. 前記割当判定ステップは、前記統計量が所定値を超えるか否かを判定し、前記統計量が前記所定値を超える場合、前記処理サーバに対してタスクを割り当てない請求項９乃至１２いずれか一項に記載の制御方法。
14. 前記統計量算出ステップは、複数の前記候補処理サーバそれぞれのリソース特徴量に対応する予測時間分布に基づいて、複数の前記候補処理サーバそれぞれについて予測時間分布の統計量を算出し、
    前記割当判定ステップは、複数の前記候補処理サーバそれぞれについて算出された統計量を比較し、その比較結果に基づいて、複数の前記候補処理サーバのいずれかにタスクを割り当てる請求項９乃至１２いずれか一項に記載の制御方法。
15. 前記候補処理サーバに割り当てるタスクの種別であるタスク種別を取得するタスク種別取得ステップを有し、
    前記予測時間分布取得ステップは、前記リソース特徴量及び前記タスク種別に対応する前記予測時間分布を取得する請求項９乃至１４いずれか一項に記載の制御方法。
16. 前記予測時間分布取得ステップは、複数のリソース特徴量それぞれに対応付けて前記予測時間分布を格納している予測時間分布格納手段から、前記リソース特徴量取得ステップによって取得されたリソース特徴量に対応する予測時間分布を取得する請求項９乃至１５いずれか一項に記載の制御方法。
17. コンピュータに割当判定装置として動作する機能を持たせるプログラムであって、前記コンピュータに、
    タスクを割り当てる処理サーバの候補である候補処理サーバに関するリソース特徴量を取得するリソース特徴量取得機能と、
    前記リソース特徴量に対応する、タスク処理時間の予測値の確率分布である予測時間分布を取得する予測時間分布取得機能と、
    前記予測時間分布取得機能によって取得された予測時間分布の統計量を算出する統計量算出機能と、
    前記統計量に基づいて、前記候補処理サーバに対するタスクの割り当てについて判定を行う割当判定機能と、
    を持たせるプログラム。
18. 前記統計量算出機能は、前記予測時間分布の代表値を前記統計量として算出する請求項１７に記載のプログラム。
19. 前記統計量算出機能は、前記予測時間分布の散布度を前記統計量として算出する請求項１７に記載のプログラム。
20. 前記統計量算出機能は、前記予測時間分布の（50+X）パーセンタイル値と 50 パーセンタイル値との差分である第１散布度、及び前記予測時間分布の 50 パーセンタイル値と（50-X）パーセンタイル値との差分である第２散布度を算出し（0<x<50）、
    前記割当判定機能は、前記第１散布度と前記第２散布度を比較し、前記第１散布度の方が小さい場合、前記候補処理サーバに対してタスクを割り当てる請求項１８に記載のプログラム。
21. 前記割当判定機能は、前記統計量が所定値を超えるか否かを判定し、前記統計量が前記所定値を超える場合、前記処理サーバに対してタスクを割り当てない請求項１７乃至２０いずれか一項に記載のプログラム。
22. 前記統計量算出機能は、複数の前記候補処理サーバそれぞれのリソース特徴量に対応する予測時間分布に基づいて、複数の前記候補処理サーバそれぞれについて予測時間分布の統計量を算出し、
    前記割当判定機能は、複数の前記候補処理サーバそれぞれについて算出された統計量を比較し、その比較結果に基づいて、複数の前記候補処理サーバのいずれかにタスクを割り当てる請求項１７乃至２０いずれか一項に記載のプログラム。
23. 前記コンピュータに、前記候補処理サーバに割り当てるタスクの種別であるタスク種別を取得するタスク種別取得機能を持たせ、
    前記予測時間分布取得機能は、前記リソース特徴量及び前記タスク種別に対応する前記予測時間分布を取得する請求項１７乃至２２いずれか一項に記載のプログラム。
24. 前記予測時間分布取得機能は、複数のリソース特徴量それぞれに対応付けて前記予測時間分布を格納している予測時間分布格納手段から、前記リソース特徴量取得機能によって取得されたリソース特徴量に対応する予測時間分布を取得する請求項１７乃至２３いずれか一項に記載のプログラム。

Images