(57)【要約】【課題】計算効率を落とすことなく、ジョブに対する計算機の割当てを最適化すること。【解決手段】複数の計算機２０を備える分散処理システム１において分散処理を行う場合、まずジョブを記憶し、その後、記憶された最先ジョブを最短時間で計算可能な計算機の台数を最適台数として導出する。続いて、ジョブ待ち状態の計算機２０の台数である待ち台数が最適台数以上か否かを判定する。このとき待ち台数が最適台数以上であれば、ジョブ待ち状態の計算機２０から最適台数分の計算機を選択し、選択された計算機２０に最先ジョブを分散処理させる。そして、分散処理の結果に基づいて最先ジョブの処理結果を出力する。【選択図】図５
2009151376.tif 000002
【特許請求の範囲】
【請求項１】
複数の計算機を備える分散処理システムにおける分散処理方法であって、
ジョブを記憶する記憶ステップと、
前記記憶ステップにおいて記憶されたジョブを最短時間で計算可能な前記計算機の台数を最適台数として導出する導出ステップと、
ジョブ待ち状態の前記計算機の台数である待ち台数が前記導出ステップにおいて導出された最適台数以上か否かを判定する判定ステップと、
前記判定ステップにおいて前記待ち台数が前記最適台数以上であると判定された場合に、前記ジョブ待ち状態の計算機から該最適台数分の計算機を選択する選択ステップと、
前記選択ステップにおいて選択された計算機に前記記憶ステップにおいて記憶されたジョブを分散処理させる処理ステップと、
前記処理ステップにおける分散処理の結果に基づいて、前記記憶ステップにおいて記憶されたジョブの処理結果を出力する出力ステップと、
を含むことを特徴とする分散処理方法。
【請求項２】
前記判定ステップでは、前記待ち台数が前記最適台数未満の場合に、前記ジョブ待ち状態の計算機の台数が該最適台数に達するまでの到達時間と前記最短時間との加算時間内に、前記記憶ステップにおいて記憶されたジョブを前記ジョブ待ち状態の計算機で計算できるか否かを判定し、
前記選択ステップでは、前記判定ステップにおいて前記加算時間内に前記ジョブを前記ジョブ待ち状態の計算機で計算できると判定された場合に、該ジョブ待ち状態の計算機をすべて選択する、
ことを特徴とする請求項１に記載の分散処理方法。
【請求項３】
前記記憶ステップでは、一つ以上の別ジョブを更に記憶し、
前記判定ステップでは、前記加算時間内に前記ジョブを前記ジョブ待ち状態の計算機で計算できないと判定した場合に、前記到達時間内に該ジョブ待ち状態の計算機で計算可能な前記別ジョブが存在するか否かを判定し、
前記選択ステップでは、前記判定ステップにおいて前記計算可能な別ジョブが存在すると判定された場合に、前記ジョブ待ち状態の計算機をすべて選択し、
前記処理ステップでは、前記判定ステップにおいて前記計算可能な別ジョブが存在すると判定された場合に、前記選択ステップにおいて選択された計算機に該計算可能な別ジョブを分散処理させる、
ことを特徴とする請求項２に記載の分散処理方法。
【請求項４】
ジョブの計算規模を示す係数と計算機の台数とにより定義された関数を用いて、前記計算機の総数以下の各台数について、前記記憶ステップにおいて記憶されたジョブを該台数で計算した場合の計算時間を算出する算出ステップを更に含み、
前記導出ステップでは、前記算出ステップにおいて算出された複数の計算時間のうち最短のものに対応する台数を前記最適台数として導出する、
ことを特徴とする請求項１〜３のいずれか一項に記載の分散処理方法。
【請求項５】
複数の計算機と通信可能な計算機管理装置であって、
ジョブを記憶する記憶手段と、
前記記憶手段に記憶されたジョブを最短時間で計算可能な前記計算機の台数を最適台数として導出する導出手段と、
ジョブ待ち状態の前記計算機の台数である待ち台数が前記導出手段により導出された最適台数以上か否かを判定する判定手段と、
前記判定手段により前記待ち台数が前記最適台数以上であると判定された場合に、前記ジョブ待ち状態の計算機から該最適台数分の計算機を選択する選択手段と、
前記選択手段により選択された計算機に前記記憶手段に記憶されたジョブを分散処理させる処理手段と、
前記処理手段による分散処理の結果に基づいて、前記記憶手段に記憶されたジョブの処理結果を出力する出力手段と、
を備えることを特徴とする計算機管理装置。
【請求項６】
前記判定手段が、前記待ち台数が前記最適台数未満の場合に、前記ジョブ待ち状態の計算機の台数が該最適台数に達するまでの時間と前記最短時間との加算時間内に、前記記憶手段に記憶されたジョブを前記ジョブ待ち状態の計算機で計算できるか否かを判定し、
前記選択手段が、前記判定手段により前記加算時間内に前記ジョブを前記ジョブ待ち状態の計算機で計算できると判定された場合に、該ジョブ待ち状態の計算機をすべて選択する、
ことを特徴とする請求項５に記載の計算機管理装置。
【請求項７】
前記記憶手段が、一つ以上の別ジョブを更に記憶し、
前記判定手段が、前記加算時間内に前記ジョブを前記ジョブ待ち状態の計算機で計算できないと判定した場合に、前記到達時間内に該ジョブ待ち状態の計算機で計算可能な前記別ジョブが存在するか否かを判定し、
前記選択手段が、前記判定手段により前記計算可能な別ジョブが存在すると判定された場合に前記ジョブ待ち状態の計算機をすべて選択し、
前記処理手段が、前記判定手段により前記計算可能な別ジョブが存在すると判定された場合に、前記選択手段により選択された計算機に該計算可能な別ジョブを分散処理させる、
ことを特徴とする請求項６に記載の計算機管理装置。
【請求項８】
ジョブの計算規模を示す係数と計算機の台数とにより定義された関数を用いて、前記計算機の総数以下の各台数について、前記記憶手段に記憶されたジョブを該台数で計算した場合の計算時間を算出する算出手段を更に備え、
前記導出手段が、前記算出手段により算出された複数の計算時間のうち最短のものに対応する台数を前記最適台数として導出する、
ことを特徴とする請求項５〜７のいずれか一項に記載の計算機管理装置。
【請求項９】
複数の計算機を備える分散処理システムであって、
ジョブを記憶する記憶手段と、
前記記憶手段に記憶されたジョブを最短時間で計算可能な前記計算機の台数を最適台数として導出する導出手段と、
ジョブ待ち状態の前記計算機の台数である待ち台数が前記導出手段により導出された最適台数以上か否かを判定する判定手段と、
前記判定手段により前記待ち台数が前記最適台数以上であると判定された場合に、前記ジョブ待ち状態の計算機から該最適台数分の計算機を選択する選択手段と、
前記選択手段により選択された計算機に前記記憶手段に記憶されたジョブを分散処理させる処理手段と、
前記処理手段による分散処理の結果に基づいて、前記記憶手段に記憶されたジョブの処理結果を出力する出力手段と、
を備えることを特徴とする分散処理システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークを介して接続された複数の計算機に計算を分散して実行させる分散処理方法、計算機管理装置及び分散処理システムに関するものである。
【背景技術】
【０００２】
分散コンピューティングは、大規模な計算の結果が高速に得られるため広い分野において採用されている。ユーザからの計算要求であるジョブが与えられたときの処理方法は大きく二通りある。
【０００３】
そのうちの一つである逐次処理方式では、サーバーが全計算機を用いてジョブを受付順に分散処理し、一つのジョブの処理が完了すると次のジョブの計算を開始する。つまり、逐次処理方式では一度に計算されるジョブは一つだけである。この場合、ジョブの規模に大小のばらつきが有ると、小規模のジョブが大規模のジョブの計算を待つなどの様に、待ち時間と処理時間との不平等が問題となる。
【０００４】
この問題を解消するために、ジョブの規模相応に計算機を割り当てて並列に計算を進行させる並列計算方式がある。例えば、下記特許文献１には、ジョブの完了期限が考慮されたジョブ配分を実現する分散処理システムが開示されている。この分散処理システムは、稼働情報を共有する複数の計算機を備え、一の計算機に投入されたジョブの実行完了時期を予測し、予測結果に応じて他の計算機にジョブの実行を依頼する。
【特許文献１】特開２００３−２５６２２２号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかし、並列処理方式では、ジョブの大きさや発生頻度の特性に応じて計算機の割当てを適切に設計しないと、計算機の稼動率が悪化し計算効率が悪くなる。例えば、大小のジョブに対する計算機の割当てを固定にした場合、大小のジョブが均等に与えられるならば各計算機は有効に機能するが、大小のジョブの数が不均衡であると計算効率が悪化してしまう。例えば大きなジョブが連続して与えられると小さなジョブに割り当てた計算機が稼動しないという状況が発生する。一方、ジョブに対する計算機への割当てを可変にすると、大小のジョブの数が不均衡でもすべての計算機がいずれかのジョブに対して常に稼動するため計算効率は悪化しない。しかし、分散処理中に計算機の割当てを変更可能とするプログラムの作成は非常に複雑である。
【０００６】
本発明は、上記課題を解決するためになされたものであり、計算効率を落とすことなく、ジョブに対する計算機の割当てを最適化することが可能な分散処理方法、計算機管理装置及び分散処理システムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明の分散処理方法は、複数の計算機を備える分散処理システムにおける分散処理方法であって、ジョブを記憶する記憶ステップと、記憶ステップにおいて記憶されたジョブを最短時間で計算可能な計算機の台数を最適台数として導出する導出ステップと、ジョブ待ち状態の計算機の台数である待ち台数が導出ステップにおいて導出された最適台数以上か否かを判定する判定ステップと、判定ステップにおいて待ち台数が最適台数以上であると判定された場合に、ジョブ待ち状態の計算機から該最適台数分の計算機を選択する選択ステップと、選択ステップにおいて選択された計算機に記憶ステップにおいて記憶されたジョブを分散処理させる処理ステップと、処理ステップにおける分散処理の結果に基づいて、記憶ステップにおいて記憶されたジョブの処理結果を出力する出力ステップと、を含むことを特徴とする。
【０００８】
また、本発明の計算機管理装置は、複数の計算機と通信可能な計算機管理装置であって、ジョブを記憶する記憶手段と、記憶手段に記憶されたジョブを最短時間で計算可能な計算機の台数を最適台数として導出する導出手段と、ジョブ待ち状態の計算機の台数である待ち台数が導出手段により導出された最適台数以上か否かを判定する判定手段と、判定手段により待ち台数が最適台数以上であると判定された場合に、ジョブ待ち状態の計算機から該最適台数分の計算機を選択する選択手段と、選択手段により選択された計算機に記憶手段に記憶されたジョブを分散処理させる処理手段と、処理手段による分散処理の結果に基づいて、記憶手段に記憶されたジョブの処理結果を出力する出力手段と、を備えることを特徴とする。
【０００９】
また、本発明の分散処理システムは、複数の計算機を備える分散処理システムであって、ジョブを記憶する記憶手段と、記憶手段に記憶されたジョブを最短時間で計算可能な計算機の台数を最適台数として導出する導出手段と、ジョブ待ち状態の計算機の台数である待ち台数が導出手段により導出された最適台数以上か否かを判定する判定手段と、判定手段により待ち台数が最適台数以上であると判定された場合に、ジョブ待ち状態の計算機から該最適台数分の計算機を選択する選択手段と、選択手段により選択された計算機に記憶手段に記憶されたジョブを分散処理させる処理手段と、処理手段による分散処理の結果に基づいて、記憶手段に記憶されたジョブの処理結果を出力する出力手段と、を備えることを特徴とする。
【００１０】
このような分散処理方法、計算機管理装置及び分散処理システムによれば、ジョブを最短時間で計算可能な計算機の台数である最適台数以上の計算機がジョブ待ち状態である場合に、ジョブ待ち状態の計算機から最適台数分の計算機が選択され、選択された計算機によりジョブが分散処理される。これにより、計算を実行中の計算機に影響を与えることなく（計算効率を落とすことなく）、ジョブに対する計算機の割当てを最適化することが可能になる。
【００１１】
本発明の分散処理方法では、判定ステップでは、待ち台数が最適台数未満の場合に、ジョブ待ち状態の計算機の台数が該最適台数に達するまでの到達時間と最短時間との加算時間内に、記憶ステップにおいて記憶されたジョブをジョブ待ち状態の計算機で計算できるか否かを判定し、選択ステップでは、判定ステップにおいて加算時間内にジョブをジョブ待ち状態の計算機で計算できると判定された場合に、該ジョブ待ち状態の計算機をすべて選択することが好ましい。
【００１２】
また、本発明の計算機管理装置では、判定手段が、待ち台数が最適台数未満の場合に、ジョブ待ち状態の計算機の台数が該最適台数に達するまでの時間と最短時間との加算時間内に、記憶手段に記憶されたジョブをジョブ待ち状態の計算機で計算できるか否かを判定し、選択手段が、判定手段により加算時間内にジョブをジョブ待ち状態の計算機で計算できると判定された場合に、該ジョブ待ち状態の計算機をすべて選択することが好ましい。
【００１３】
この場合、ジョブ待ち状態の計算機の台数が最適台数未満であると、現在ジョブ待ち状態にある計算機の台数が最適台数に達するまでの時間と最短時間との加算時間内にジョブを処理できるか否かが更に判定される。そして、処理可能と判定されれば、ジョブ待ち状態の計算機の台数が最適台数に達するまで待つことなく、現在待ち状態にある計算機がすべて選択されて分散処理が実行される。これにより、計算機をより有効に利用して、ジョブの処理をより早く完了することが可能になる。
【００１４】
本発明の分散処理方法では、記憶ステップでは、一つ以上の別ジョブを更に記憶し、判定ステップでは、加算時間内にジョブをジョブ待ち状態の計算機で計算できないと判定した場合に、到達時間内に該ジョブ待ち状態の計算機で計算可能な別ジョブが存在するか否かを判定し、選択ステップでは、判定ステップにおいて計算可能な別ジョブが存在すると判定された場合に、ジョブ待ち状態の計算機をすべて選択し、処理ステップでは、判定ステップにおいて計算可能な別ジョブが存在すると判定された場合に、選択ステップにおいて選択された計算機に該計算可能な別ジョブを分散処理させることが好ましい。
【００１５】
また、本発明の計算機管理装置では、記憶手段が、一つ以上の別ジョブを更に記憶し、判定手段が、加算時間内にジョブをジョブ待ち状態の計算機で計算できないと判定した場合に、到達時間内に該ジョブ待ち状態の計算機で計算可能な別ジョブが存在するか否かを判定し、選択手段が、判定手段により計算可能な別ジョブが存在すると判定された場合にジョブ待ち状態の計算機をすべて選択し、処理手段が、判定手段により計算可能な別ジョブが存在すると判定された場合に、選択手段により選択された計算機に該計算可能な別ジョブを分散処理させることが好ましい。
【００１６】
この場合、現在ジョブ待ち状態にある計算機がある一つのジョブを加算時間内に処理できないと判定された場合に、到達時間内に処理可能な別ジョブが存在するか否かが更に判定される。そして、そのような別ジョブが存在した場合に、現在待ち状態にある計算機がすべて選択され、別ジョブに対する分散処理が実行される。これにより、計算機をより有効に利用して、ジョブの実行時間を全体として短縮することが可能になる。
【００１７】
本発明の分散処理方法では、ジョブの計算規模を示す係数と計算機の台数とにより定義された関数を用いて、計算機の総数以下の各台数について、記憶ステップにおいて記憶されたジョブを該台数で計算した場合の計算時間を算出する算出ステップを更に含み、導出ステップでは、算出ステップにおいて算出された複数の計算時間のうち最短のものに対応する台数を最適台数として導出することが好ましい。
【００１８】
また、本発明の計算機管理装置では、ジョブの計算規模を示す係数と計算機の台数とにより定義された関数を用いて、計算機の総数以下の各台数について、記憶手段に記憶されたジョブを該台数で計算した場合の計算時間を算出する算出手段を更に備え、導出手段が、算出手段により算出された複数の計算時間のうち最短のものに対応する台数を最適台数として導出することが好ましい。
【００１９】
この場合、ジョブの計算規模を示す係数と計算機の台数とにより定義された関数を用いて計算時間が算出される。この算出は、使用する計算機が１〜総数の各場合について行われる。そして、算出された複数の計算時間のうち最短のものに対応する台数が最適台数として導出される。ジョブの計算時間はジョブの計算規模と計算機の台数に左右されるから、これら計算規模及び台数により定義された関数を用いることで最適台数をより正確に導出できる。
【発明の効果】
【００２０】
このような分散処理方法、計算機管理装置及び分散処理システムによれば、ジョブを処理する計算機が、ジョブを最短時間で計算可能な計算機の台数とジョブ待ち状態の計算機の台数との比較に基づいて選択されるので、計算効率を落とすことなく、ジョブに対する計算機の割当てを最適化できる。
【発明を実施するための最良の形態】
【００２１】
以下、添付図面を参照しながら本発明の実施形態を詳細に説明する。なお、図面の説明において同一又は同等の要素には同一の符号を付し、重複する説明を省略する。
【００２２】
まず、図１を用いて、実施形態に係る分散処理システム１を説明する。図１は分散処理システム１の全体構成を示す図である。図２は、図１に示す計算機管理装置１０のハードウェア構成を示す図である。図３はキュー管理情報の構成を示す図である。図４は計算機情報の構成を示す図である。
【００２３】
分散処理システム１は、複数のジョブを並列に処理することが可能な計算機システムであり、計算機管理装置１０とＮ台の計算機２０とを備えている。計算機管理装置１０と各計算機２０とは図示しないネットワーク（例えばインターネットや構内通信網（ＬＡＮ）など）を介して通信可能である。
【００２４】
計算機管理装置１０は、各計算機２０にジョブを割り当てて分散処理を実行させ、その分散処理の結果に基づいてジョブの処理結果を生成し出力する。このために、計算機管理装置１０は入力部１１、キュー管理部（記憶手段）１２、計算機管理部１３、計算時間予測部（算出手段）１４、分散処理開始部（導出手段、判定手段、選択手段、処理手段）１５、結果受信部１６及び出力部（出力手段）１７を備えている。
【００２５】
計算機管理装置１０は、図２に示すように、オペレーティングシステムやアプリケーションプログラムなどを実行するＣＰＵ１０１、ＲＯＭ及びＲＡＭで構成される主記憶部１０２、ハードディスクなどで構成される補助記憶部１０３、ネットワークカードなどの通信制御部１０４、キーボードやマウスなどの入力インタフェース（Ｉ／Ｆ）１０５、及びモニタやプリンタなどの出力インタフェース（Ｉ／Ｆ）１０６で構成される。図１に示される各機能は、図２に示すＣＰＵ１０１や主記憶部１０２の上に所定のソフトウェアを読み込ませ、ＣＰＵ１０１の制御の下で通信制御部１０４を動作させるとともに、主記憶部１０２や補助記憶部１０３におけるデータの読み出し及び書き込みを行うことで実現される。
【００２６】
入力部１１は、ユーザの計算要求であるジョブの入力を受け付けてキュー管理部１２に出力する手段である。入力部１１はユーザにより入力されたジョブを直接受け付けてもよいし、図示しない他の情報処理装置から入力されたジョブを受け付けてもよい。
【００２７】
キュー管理部１２は、入力部１１から入力されたジョブを、キューを用いて記憶（登録）する手段である。キュー管理部１２はキューの状態（各ジョブの状態）を示すキュー管理情報を保持している。
【００２８】
キュー管理情報は、図３に示すように、ジョブを識別するジョブ番号、ジョブの受付日時、ジョブの状況を示す計算状況、計算開始日時、計算条件及び計算時間予測テーブルを含んでいる。ジョブ番号は、記憶された日時が古いジョブから昇順に割り当てられる。計算状況は、例えば、「計算完了」、「（ｘ台で）計算中」、「計算待ち」などのように示される。計算条件とは、ジョブの計算に必要なパラメータである。計算時間予測テーブルは、計算機の台数毎に（１〜Ｎのそれぞれについて）算出したジョブの予測計算時間で構成される。例えば、図３におけるジョブ番号２のジョブを１台の計算機２０で計算した場合の計算時間はｘ（秒）と予測され、同ジョブをＮ台の計算機２０で計算した場合の計算時間はｘ´´（秒）と予測されている。
【００２９】
キュー管理部１２は、入力部１１からジョブが入力されると、そのジョブを記憶すると共に、そのジョブのキュー管理情報を生成して記憶する。その後、キュー管理部１２は分散処理開始部１５又は結果受信部１６から入力されたジョブの情報に基づいてキュー管理情報を更新する。分散処理開始部１５からジョブ情報が入力されると、キュー管理部１２は該当するジョブの計算状況を「ｘ台で計算中（ｘ＝１〜Ｎ）」に更新すると共に計算開始日時を更新する。また、結果受信部１６からジョブ情報が入力された場合には、キュー管理部１２は該当するジョブの計算状況を「計算完了」に更新する。
【００３０】
計算時間予測部１４は、キュー管理部１２に記憶されたジョブの内容に基づいてそのジョブの計算時間を算出（予測）する手段である。計算時間予測部１４は分散処理システム１内の計算機２０の総数以下の各台数についてその計算時間を算出する。
【００３１】
例えば、計算時間予測部１４は、下記式（１）で示される予測関数を用いて計算時間を算出する。なお、式（１）におけるｘはジョブの計算規模を示す係数（計算規模係数）であり、ｎは計算に用いる計算機の台数（分散台数）である。すなわち、予測関数は計算規模係数と分散台数により定義される。
ｆ（ｘ，ｎ）＝ｘ／ｎ＋０．１ｎｘ  …（１）
【００３２】
計算規模係数ｘは計算条件に基づいて決定され、ジョブの種類により異なる値が設定される。例えば、携帯電話のサービスエリアを推定するシステム（推定システム）において、ある地点における電波の受信強度を計算する場合には、計算規模係数は計算対象の地点の数で表すことができる。
【００３３】
また、計算時間予測部１４は、二種類の計算規模係数を含む予測関数ｆ（ｘ１，ｘ２，ｎ）を用いることもできる。例えば、計算時間予測部１４は上記推定システムの計算時間を計算対象の地点の数と基地局の数という二種類の計算規模係数を用いて予測することが可能である。
【００３４】
予測関数ｆ（ｘ１，ｘ２，ｎ）の右辺は多変量解析を用いて決定できる。したがって、予測関数は、適用対象のシステム（例えば上記推定システムなど）の計算条件であるパラメータと多変量解析とにより決定される。上記式（１）の右辺も、多変量解析により決定されたものである。
【００３５】
また、計算時間予測部１４は、式（１）のような予測関数とは異なる計算時間関数を用いてもよい。計算時間予測部１４は、適用対象のシステムにおいて計算条件と計算時間との関係が予め判明している場合に計算時間関数を用いることが可能である。例えば、適用対象のシステムにおいて、一つの事象（問題）を解くために必ず一定の時間ａが必要であることと、その事象をｎ台の計算機に分散処理させると計算時間が１／ｎになるが計算時間の１０分の１が分散処理のロスとして分散台数ｎの分だけ掛かることとが判明しているとする。この場合、計算時間予測部１４は、下記式（２）で示される計算時間関数を用いて計算時間を算出できる。なお、式（２）におけるｘ´は、事象の数（計算規模係数の一種）であり、ｎは分散台数である。すなわち、計算時間関数は解決すべき事象の数と分散台数により定義される。
ｆ（ｘ´，ｎ）＝ａ（ｘ´／ｎ＋０．１ｎｘ´）  …（２）
【００３６】
計算時間予測部１４は、キュー管理部１２がジョブを記憶したときに、キュー管理部１２からジョブに関する情報（例えば計算条件や計算規模など）を取得し、そのジョブに対する計算時間を分散台数１〜Ｎのそれぞれに対して算出する。そして、計算時間予測部１４は計算結果をキュー管理情報の計算時間予測テーブルに格納する。
【００３７】
計算機管理部１３は、Ｎ台の計算機２０のそれぞれの状態を記憶する手段である。計算機管理部１３は図４に示すような計算機情報を保持し、必要に応じてその計算機情報を更新する。
【００３８】
計算機情報は各計算機２０に対して設定されており、計算機番号と、計算状態と、その他情報とを含んでいる。計算機番号とは計算機２０の識別子である。計算状態とは計算機２０の現在の情報を示す情報である。例えば、現在ジョブを処理していることを示す「計算中」や、現在ジョブの処理を行っていないことを示す「計算待ち（ジョブ待ち）」などの値が計算状態として設定される。その他情報としては、例えば図４に示すようなＩＰアドレスが挙げられるが、他の情報（例えばマシン名や機種名など）をその他情報として設定してもよい。
【００３９】
計算機管理部１３は分散処理開始部１５又は結果受信部１６から入力された計算機２０の情報に基づいて計算機情報を更新する。分散処理開始部１５から計算機情報が入力されると、キュー管理部１２は該当する計算機２０の計算状態を「計算中」に更新し、結果受信部１６から計算機情報が入力されると、該当する計算機２０の計算状態を「計算待ち」に更新する。
【００４０】
分散処理開始部１５は、キュー管理部１２に記憶されているジョブを分割し、分割したジョブ（以下「被分割ジョブ」という）をジョブ待ち状態にある計算機に送信する手段である。
【００４１】
まず、分散処理開始部１５は計算機管理部１３に記憶されている計算機情報を参照してジョブ待ち状態の計算機２０が存在するか否かを判定する。このとき、そのような計算機２０が存在しなければ、分散処理開始部１５はいずれかの計算機２０において計算が終了するまで何も行わない。
【００４２】
一方、ジョブ待ち状態の計算機２０が存在する場合には、分散処理開始部１５はキュー管理部１２に記憶されている未処理のジョブのうち最も先に登録されたジョブ（以下「最先ジョブ」という）を最短時間で計算可能な計算機２０の台数を最適台数として導出する。例えばキュー管理情報が図３に示す状態にある場合、分散処理開始部１５はジョブ番号が４であるジョブの計算時間予測テーブルを参照し、予測計算時間が最小である台数を最適台数として選択する。なお、以下では、最適台数に対応する予測計算時間を最適計算時間（最短時間）Ｔｏという。
【００４３】
なお、最適計算時間Ｔｏに対応する台数が複数導出されることがある。この場合、分散処理開始部１５は、最適計算時間Ｔｏでの計算が期待できる台数のうち最も少ない台数を最適台数とする。例えば、あるジョブを４台又は５台の計算機に計算させると計算時間が最短になる場合には、分散処理開始部１５は最適台数を４に設定する。
【００４４】
続いて、分散処理開始部１５はジョブ待ち状態の計算機２０の台数である待ち台数が最適台数以上か否かを判定する。なお、図４に示す計算機情報では、計算状態が「計算待ち」である計算機番号３及び４がジョブ待ち状態の計算機に相当する。分散処理開始部１５は、待ち台数が最適台数以上である場合に、ジョブ待ち状態の計算機２０から最適台数分の計算機２０を選択する。続いて、分散処理開始部１５は、選択された計算機２０に最先ジョブを分散処理させるために、最先ジョブを分割し、選択された計算機２０のそれぞれに被分割ジョブを送信する。
【００４５】
一方、待ち台数が最適台数未満である場合、分散処理開始部１５はジョブ待ち状態の計算機の台数が最適台数に達するまでの時間（以下「到達時間Ｔａ」という）を算出し、到達時間Ｔａと最適計算時間（最短時間）Ｔｏとを加算する。分散処理開始部１５は、一以上のジョブについて処理終了までの時間を算出することで到達時間Ｔａを導出できる。例えば、あるジョブの計算開始時刻と現在時刻とがそれぞれ１０：００、１０：０２であり、そのジョブの処理時間が１８０秒であれば、そのジョブを実行している計算機は６０秒後に計算待ち状態になることが分かる。場合によっては、分散処理開始部１５は複数のジョブの処理時間に基づいて到達時間Ｔａを算出する。
【００４６】
続いて、分散処理開始部１５はジョブ待ち状態の計算機をすべて用いて最先ジョブを計算した場合の時間（以下「第２計算時間Ｔｓ」という）が加算時間（Ｔａ＋Ｔｏ）以下か否かを判定する。
【００４７】
ここで、Ｔｓ≦Ｔａ＋Ｔｏであれば、分散処理開始部１５は加算時間（Ｔａ＋Ｔｏ）以内に最先ジョブをジョブ待ち状態の計算機で計算できると判定し、ジョブ待ち状態の計算機２０をすべて選択する。続いて、分散処理開始部１５は、選択された計算機２０に最先ジョブを分散処理させるために、最先ジョブを分割し、選択された計算機２０のそれぞれに被分割ジョブを送信する。
【００４８】
一方、Ｔｓ＞Ｔａ＋Ｔｏである場合、分散処理開始部１５は到達時間Ｔａ内にジョブ待ち状態の計算機２０で計算可能な別ジョブ（最先ジョブ以外の未処理のジョブ）が存在するか否かを判定する。具体的には、分散処理開始部１５は、そのような別ジョブに対して、ジョブ待ち状態の計算機２０をすべて用いて計算した場合の時間（第２計算時間Ｔｔ）を算出し、Ｔｔ≦Ｔａか否かを判定する。分散処理開始部１５はこの判定処理を受付日時の古い別ジョブから順に実行する。
【００４９】
ここで、ある別ジョブについてＴｔ≦Ｔａである場合、分散処理開始部１５はジョブ待ち状態の計算機２０をすべて選択する。続いて、分散処理開始部１５は、選択された計算機２０にその別ジョブを分散処理させるために、その別ジョブを分割し、選択された計算機２０のそれぞれに被分割ジョブを送信する。一方、すべての別ジョブについてＴｔ＞Ｔａの場合、分散処理開始部１５は何も行わない。
【００５０】
分散処理開始部１５は、選択した計算機２０に被分割ジョブを送信すると、分散処理を行うジョブ（最先ジョブ又は別ジョブ）の情報をキュー管理部１２に出力すると共に、被分割ジョブの送信先である計算機２０の情報を計算機管理部１３に出力する。
【００５１】
結果受信部１６は、計算機２０から送信されてきた被分割ジョブの計算結果、すなわち分散処理の結果に基づいて、ジョブの処理結果を生成する手段である。結果受信部１６は、あるジョブに対する被分割ジョブの計算結果をすべて受信すると、その計算結果からジョブの計算結果を生成し出力部１７に出力する。また、結果受信部１６は、被分割ジョブの計算結果を受信すると、計算結果の送信元である計算機２０の情報を計算機管理部１３に送信する。更に、結果受信部１６は、あるジョブに対する被分割ジョブをすべて受信すると、そのジョブの情報をキュー管理部１２に出力する。
【００５２】
出力部１７は、結果受信部１６から入力された計算結果をモニタやプリンタなどの出力装置に出力する手段である。
【００５３】
計算機２０は、計算機管理装置１０から受信したジョブを処理し、処理結果を計算機管理装置１０に送信する。このために、計算機２０はジョブ受信部２１、ジョブ処理部２２及び結果送信部２３を備えている。計算機２０のハードウェア構成は図２に示すものと同様である。
【００５４】
ジョブ受信部２１は、計算機管理装置１０から被分割ジョブを受信する手段である。ジョブ受信部２１は受信した被分割ジョブをジョブ処理部２２に出力する。
【００５５】
ジョブ処理部２２は、被分割ジョブを処理する手段である。ジョブ処理部２２は入力された被分割ジョブに基づいて所定の計算を行い、計算結果を生成する。ジョブ処理部２２は、生成した計算結果を結果送信部２３に出力する。
【００５６】
結果送信部２３は、ジョブ処理部２２から入力された被分割ジョブの計算結果を計算機管理装置１０に送信する手段である。
【００５７】
次に、図５及び６を用いて、図１に示す分散処理システムの動作を説明するとともに本実施形態に係る分散処理方法について説明する。図５及び６はそれぞれ分散処理システムの処理を説明するフローチャートである。
【００５８】
まず、計算機管理装置１０において、入力部１１がジョブの入力を受け付け、キュー管理部１２が受け付けられたジョブを登録する（ステップＳ１１、記憶ステップ）。続いて、計算時間予測部１４が登録されたジョブの計算時間を算出して計算時間予測テーブルを生成する（ステップＳ１２、算出ステップ）。具体的には、計算時間予測部１４は、接続している計算機２０の台数を上限として、計算機の台数毎に所定の関数（例えば上記式（１）や式（２）など）を用いてジョブの計算時間を算出し、キュー管理情報内の計算時間予測テーブルに算出結果を記録する。
【００５９】
続いて、分散処理開始部１５が、ジョブ待ち状態の計算機２０が存在するか否かを判定する（ステップＳ１３）。このとき、そのような計算機２０が存在しなければ（ステップＳ１３；ＮＯ）、処理が終了する。一方、ジョブ待ち状態の計算機２０が存在すれば（ステップＳ１３；ＹＥＳ）、分散処理開始部１５は最先ジョブの計算時間予測テーブルに基づいて最先ジョブの最適台数を導出する（ステップＳ１４、導出ステップ）。続いて、分散処理開始部１５はジョブ待ち状態にある計算機２０の台数（待ち台数）が導出された最適台数以上か否かを判定し（ステップＳ１５、判定ステップ）、待ち台数が最適台数以上であれば（ステップＳ１５；ＹＥＳ）、ジョブ待ち状態の計算機から最適台数分の計算機を選択する（ステップＳ１６、選択ステップ）。
【００６０】
続いて、分散処理開始部１５は最先ジョブを分割し、被分割ジョブを選択された計算機２０のそれぞれに送信することで分散処理を開始する（ステップＳ１７、処理ステップ）。このとき、キュー管理部１２が最先ジョブのキュー管理情報を更新し、計算機管理部１３が選択された計算機２０の計算機情報を更新する（ステップＳ１８）。これにより、最先ジョブが処理されていること、及び最適台数分の計算機２０において計算が行われていることが記憶される。
【００６１】
その後、選択された各計算機２０において被分割ジョブの計算が実行される（ステップＳ１９）。続いて、計算機管理装置１０の結果受信部１６が被分割ジョブの計算結果を取得し、その計算結果に基づいて最先ジョブの計算結果を生成する（ステップＳ２０、出力ステップ）。このとき、キュー管理部１２が最先ジョブのキュー管理情報を更新し、計算機管理部１３が計算を実行した計算機２０の計算機情報を更新する（ステップＳ２１）。これにより、最先ジョブが処理されたこと、及び最適台数分の計算機２０がジョブ待ち状態に遷移したことが記憶される。続いて、出力部１７が結果受信部１６により生成された計算結果を出力する（ステップＳ２２、出力ステップ）。
【００６２】
なお、最先ジョブの分散処理が実行された後に他の計算待ちのジョブが存在する場合は（ステップＳ２３；ＹＥＳ）、新たな最先ジョブに対して上記ステップＳ１４〜Ｓ２２の処理が実行される。
【００６３】
以上に対して、上記ステップＳ１５においてジョブ待ち状態の計算機２０の台数が最適台数未満であった場合には（ステップＳ１５；ＮＯ）、図６に示す処理が実行される。
【００６４】
この場合、まず、分散処理開始部１５はジョブ待ち状態の計算機の台数が最適台数に達する間での時間（到達時間）を算出する（ステップＳ３１）。続いて、分散処理開始部１５はジョブ待ち状態の計算機をすべて用いて最先ジョブを計算した場合の時間（第２計算時間）をキュー管理情報から取得する（ステップＳ３２）。そして、分散処理開始部１５は第２計算時間が到達時間と最適計算時間との加算時間以下か否かを判定する（ステップＳ３３、判定ステップ）。このとき、第２計算時間が加算時間以下であれば（ステップＳ３３；ＹＥＳ）、分散処理開始部１５は、加算時間内に最先ジョブをジョブ待ち状態の計算機２０で計算できると判定し、ジョブ待ち状態の計算機２０をすべて選択する（ステップＳ３４、選択ステップ）。その後、最先ジョブについて上記ステップＳ１７以降の処理が実行される。
【００６５】
一方、第２計算時間が加算時間よりも長い場合には（ステップＳ３４；ＮＯ）、分散処理開始部１５は、到達時間内にジョブ待ち状態の計算機２０で計算可能な別ジョブが存在するか否かを判定する（ステップＳ３５、判定ステップ）。具体的には、分散処理開始部１５は最先ジョブ以外の未処理のジョブについて第２計算時間を算出し、その第２計算時間と到達時間とを比較することでその判定を実行する。このとき、計算可能な別ジョブが存在すれば（ステップＳ３５；ＹＥＳ）、分散処理開始部１５はジョブ待ち状態の計算機２０をすべて選択し（ステップＳ３４、選択ステップ）、その後、その別ジョブについて上記ステップＳ１７以降の処理が実行される。一方、そのような別ジョブが存在しなければ（ステップＳ３５；ＮＯ）、処理が終了する。
【００６６】
次に、図７〜９を用いて上記分散処理方法の具体例を説明する。図７はキュー管理情報の具体例を示す図である。図８は計算機情報の具体例を示す図である。図９は５台の計算機の稼働状況を時系列で示した図である。図７及び８においては、説明に直接関係の無い情報の記載を省略している。その一方で、図７においては、説明のために計算規模係数を記載している。
【００６７】
以下の説明では、分散処理システム１内には計算機が５台（計算機Ｃ１〜Ｃ５とする）あることを前提とする。図７の計算時間予測テーブルには上記式（１）の予測関数を用いて算出された予測計算時間（分）が格納されている。なお、この予測計算時間と実計算時間とは一致するものとする。
【００６８】
図９に示すように、ジョブＪ１が登録された９：００時点では計算機Ｃ１〜Ｃ５のいずれもジョブ待ちの状態にある。一方、図７を見ると、ジョブＪ１の最適台数は３である。したがって、分散処理開始部１５は３台の計算機を選択し（図９の例では計算機Ｃ１〜Ｃ３）、これらの計算機にジョブＪ１を実行させる。
【００６９】
その後、１１：００にジョブＪ２が登録される。ジョブＪ２の最適台数は３であるが、ジョブ待ち状態の計算機は２台（計算機Ｃ４，Ｃ５）しか存在しない。したがって、分散処理開始部１５はジョブＪ２の最適計算時間（１９０分）及び第２計算時間（２１０分）を取得すると共に、到達時間を３８０−１２０＝２６０（分）と算出する。このとき、第２計算時間（２１０分）は最適計算時間と到達時間との和（４５０分）よりも短いので、分散処理開始部１５は計算機Ｃ４，Ｃ５を選択し、これらの計算機にジョブＪ２を計算させる。
【００７０】
その後、１２：００にジョブＪ３が登録される。この時点ではジョブ待ち状態の計算機が存在しないので分散処理開始部１５は何も行わない。その後、１２：１０にジョブＪ４が登録されたときも同様である。
【００７１】
その後、１４：３０にジョブＪ２の計算が完了し、キュー管理情報及び計算機情報がそれぞれ図７，８のように更新される。すなわち、ジョブＪ２の計算状況が「完了」に更新され、計算機Ｃ４及びＣ５の計算状態が「計算待ち」に更新される。
【００７２】
この更新を受けて、分散処理開始部１５が次の未処理ジョブに対する処理を開始する。まず、分散処理開始部１５は受付時刻が最も古い未処理ジョブであるジョブＪ３を計算するか否かを判定する。ジョブＪ３の最適台数は３台であるがジョブ待ち状態の計算機は２台しかないので、分散処理開始部１５はジョブＪ３の最適計算時間（５０７分）及び第２計算時間（５６０分）と、到達時間３８０−３３０＝５０（分）とに基づいて、第２計算時間が最適計算時間と到達時間との和（５５７分）よりも長いと判定する。
【００７３】
したがって、分散処理開始部１５は受付時刻が二番目に古い未処理ジョブであるジョブＪ４を処理できるか否かを判定する。ジョブＪ４の第２計算時間は４２分であり到達時間は５０分であるから、分散処理開始部１５はジョブＪ４を処理すると判定し、計算機Ｃ４及びＣ５を選択してこれらの計算機にジョブＪ４を計算させる。
【００７４】
その後、１５：１２にジョブＪ４の計算が完了し、ジョブＪ４のキュー管理情報が更新される。この更新を受けて、分散処理開始部１５はジョブＪ３を計算するか否かを判定する。この時点での到達時間は３８０−３７２＝８（分）なので、分散処理開始部１５は第２計算時間（５６０分）が最適計算時間（５０７分）とその到達時間との和（５１５分）よりも長いと判定し、ジョブＪ３の計算を行わない。この時、処理待ちのジョブは存在しないので、分散処理開始部１５は計算中のジョブが終了するまで何も行わない。
【００７５】
その後、１５：２０にジョブＪ１の計算が完了し、ジョブＪ１のキュー管理情報が更新される。この時点で、ジョブＪ３の最適台数分の計算機２０が確保できるので、分散処理開始部１５はジョブＪ３の計算を開始する。このジョブＪ３の計算は２３：４７に終了する。したがって、分散処理システム１を用いて上記ジョブＪ１〜Ｊ４を処理した場合には、８８７分ですべての処理が完了する。
【００７６】
以上に対して、逐次処理を採用し、上記ジョブＪ１〜Ｊ４のすべてを５台の計算機による分散処理で計算した場合は、図１０に示すように、すべての処理が完了するまでに１２３２分掛かってしまう。したがって、分散処理システム１による並列処理を採用することで、計算時間が２８％短縮される。
【００７７】
以上説明したように、本実施形態によれば、最適台数以上の計算機２０がジョブ待ち状態である場合に、それらの計算機２０から最適台数分が選択され、選択された計算機２０により最先ジョブが分散処理される。これにより、計算を実行中の計算機２０に影響を与えることなく（計算効率を落とすことなく）、最先ジョブに対する計算機２０の割当てを最適化することが可能になる。
【００７８】
また本実施形態によれば、ジョブ待ち状態の計算機２０の台数が最適台数未満であると、到達時間と最適計算時間との加算時間内に最先ジョブを処理できるか否かが更に判定される。そして、処理可能と判定されれば、ジョブ待ち状態の計算機２０がすべて選択されて分散処理が実行される。これにより、計算機２０をより有効に利用して、最先ジョブの処理をより早く完了することが可能になる。
【００７９】
また本実施形態によれば、ジョブ待ち状態の計算機２０が最先ジョブを上記加算時間内に処理できないと判定された場合に、到達時間内に処理可能な別ジョブが存在するか否かが更に判定される。そして、そのような別ジョブが存在した場合に、ジョブ待ち状態の計算機２０がすべて選択され、別ジョブに対する分散処理が実行される。これにより、計算機２０をより有効に利用して、ジョブの実行時間を全体として短縮することが可能になる。
【００８０】
また本実施形態によれば、ジョブの計算規模を示す係数と計算機の台数とにより定義された関数（例えば上記式（１）や式（２））を用いて計算時間が算出される。この算出は、使用する計算機２０が１〜Ｎの各場合について行われる。そして、算出された複数の計算時間のうち最短のものに対応する台数が最適台数として導出される。ジョブの計算時間はジョブの計算規模と計算機２０の台数に左右されるから、これら計算規模及び台数により定義された関数を用いることで最適台数をより正確に導出できる。
【００８１】
以上、本発明をその実施形態に基づいて詳細に説明した。しかし、本発明は上記実施形態に限定されるものではない。本発明は、その要旨を逸脱しない範囲で以下のような様々な変形が可能である。
【００８２】
上記実施形態では、分散処理開始部１５において以下の三種類の判定処理が実行された。
（１）ジョブ待ち状態の計算機２０が最適台数以上存在するか
（２）最適計算時間と到達時間との加算時間内に、最先ジョブをジョブ待ち状態の計算機２０により実行できるか
（３）到達時間内に、最先ジョブ以外の別ジョブをジョブ待ち状態の計算機２０により実行できるか
しかし、分散処理開始部１５は上記三種類のうち一部の判定処理のみを実行してもよい。
【００８３】
例えば、上記（１）の判定のみを実行してもよいし、上記（１）及び（２）の判定のみを実行してもよい。上記（１）の判定のみを実行する場合には、ジョブ待ち状態の計算機２０が最適台数未満であると分散処理開始部１５は処理を終了する。また、上記（１）及び（２）の判定のみを実行する場合には、上記加算時間内に最先ジョブを実行できないと判明すると分散処理開始部１５は処理を終了する。
【００８４】
仮に、分散処理開始部１５が上記（１）の判定のみを行うものとする。このとき、図８に示されている計算機Ｃ１〜Ｃ５を用いて図７に示されているジョブＪ１〜Ｊ４を計算すると、図１１に示すように、すべての処理を１１１５分で完了できる。すなわち、図１０に示す逐次処理と比較して、計算時間が９％短縮される。
【００８５】
上記実施形態では、分散処理システム１は受付日時が古いジョブを優先して計算するが、ジョブの選択方法はこれに限定されない。例えば、分散処理システム１は受付日時が新しいジョブを優先して計算してもよいし、計算するジョブを、ジョブ毎に設定された優先度に基づいて選択してもよい。
【図面の簡単な説明】
【００８６】
【図１】実施形態に係る分散処理システムの全体構成を示す図である。
【図２】図１に示す計算機管理装置のハードウェア構成を示す図である。
【図３】キュー管理情報の構成を示す図である。
【図４】計算機情報の構成を示す図である。
【図５】図１に示す分散処理システムの処理を説明するフローチャートである。
【図６】図１に示す分散処理システムの処理を説明するフローチャートである。
【図７】キュー管理情報の具体例を示す図である。
【図８】計算機情報の具体例を示す図である。
【図９】図１に示す分散処理システムを用いた場合の、計算機の稼働状況の具体例を示す図である。
【図１０】比較のために示す、計算機の稼働状況の具体例を示す図である。
【図１１】変形例に係る分散処理システムを用いた場合の、計算機の稼働状況の具体例を示す図である。
【符号の説明】
【００８７】
１…分散処理システム、１０…計算機管理装置、１１…入力部、１２…キュー管理部（記憶手段）、１３…計算機管理部、１４…計算時間予測部（算出手段）、１５…分散処理開始部（導出手段、判定手段、選択手段、処理手段）、１６…結果受信部、１７…出力部（出力手段）、２０…計算機、２１…ジョブ受信部、２２…ジョブ処理部、２３…結果送信部
【図１】
2009151376.tif 000003
【図２】
2009151376.tif 000004
【図３】
2009151376.tif 000005
【図４】
2009151376.tif 000006
【図５】
2009151376.tif 000007
【図６】
2009151376.tif 000008
【図７】
2009151376.tif 000009
【図８】
2009151376.tif 000010
【図９】
2009151376.tif 000011
【図１０】
2009151376.tif 000012
【図１１】
2009151376.tif 000013