(57)【要約】      （修正有）【課題】稼動状況を事前に予測できないようなジョブ及びリソース環境に対して、ジョブの要求を満たすように動的に且つ自律的にリソースの割り当て及び変更を行うことができるジョブ実行を実現する。【解決手段】ネットワーク接続された複数のコンピュータの中の１つのコンピュータに任意のタスク数に分割可能なジョブを提供して、１つのコンピュータでジョブのタスクを所定時間処理する。所定時間におけるタスク処理の進捗率を算出して進捗率及び所定時間に基づき１つのコンピュータでのタスク処理の完了時間を推定する。推定した完了時間がジョブの要求項目を満たすか否かを判定する。推定した完了時間が要求項目を満たす場合には、ジョブのタスクを１つのコンピュータで処理して結果を生成する。推定した完了時間が要求項目を満たさない場合には、ジョブのタスクを１つのコンピュータに残すタスクと他のコンピュータに移動するタスクとに分割して処理させる。【選択図】図６
2008123205.tif 000002
【特許請求の範囲】
【請求項１】
ネットワーク接続された複数のコンピュータで任意のタスク数に分割可能なジョブを実行するジョブ実行方法であって、
前記複数のコンピュータの中の１つのコンピュータに前記ジョブを提供して、前記１つのコンピュータで前記ジョブのタスクを所定時間処理し、
前記１つのコンピュータの処理装置により、前記所定時間におけるタスク処理の進捗率を算出して前記進捗率及び前記所定時間に基づき前記１つのコンピュータでのタスク処理の完了時間を推定し、
前記処理装置により、前記推定した完了時間が前記ジョブの要求項目を満たすか否かを判定し、
前記推定した完了時間が前記要求項目を満たす場合には、前記１つのコンピュータにおける前記ジョブのタスクを前記１つのコンピュータで処理して結果を生成し、
前記推定した完了時間が前記要求項目を満たさない場合には、前記処理装置により、前記１つのコンピュータにおける前記ジョブのタスクを前記１つのコンピュータに残すタスクと前記複数のコンピュータの中の他のコンピュータに移動するタスクとに分割し、
残した前記ジョブのタスクを前記１つのコンピュータで更に所定時間処理すると共、前記処理装置により、前記移動するタスクを前記他のコンピュータに移動して処理させ、
前記推定した完了時間が前記要求項目を満たすまで、前記タスク処理の完了時間を推定することから前記ジョブのタスクを分割して残した前記ジョブのタスクを更に所定時間処理すると共に前記移動するタスクを前記他のコンピュータに移動して処理させることまでを繰り返し、
前記処理装置により、前記他のコンピュータから前記移動して処理させたタスクの結果を取得して前記取得した結果と前記１つのコンピュータで処理したタスクの結果とをマージする、
ことを含む前記ジョブ実行方法。
【請求項２】
前記進捗率を算出することが、前記処理装置により、処理したタスク数を監視及び計数して前記ジョブの処理すべきタスク数に対する比率を計算することを含む、請求項１に記載のジョブ実行方法。
【請求項３】
前記タスク処理の完了時間を推定することが、前記処理装置により、前記完了時間をＴＥとし、前記所定時間をＴとし、前記進捗率をｐとして、ＴＥ＝Ｔ（１−ｐ）/ｐを計算することを含む、請求項１又は２に記載のジョブ実行方法。
【請求項４】
前記推定した完了時間が前記ジョブの要求項目を満たすか否かを判定することが、前記要求項目を前記ジョブのデッドライン時刻（実行終了希望時刻）として、前記処理装置により、前記デッドライン時刻までの残余時間が前記推定した完了時間よりも長いか否かを判定することを含む、請求項１に記載のジョブ実行方法。
【請求項５】
前記推定した完了時間が前記ジョブの要求項目を満たすか否かを判定することが、前記要求項目を前記コンピュータの使用コスト（課金）から定まる前記ジョブについて前記コンピュータを使用できる使用可能時間として、前記処理装置により、前記使用可能時間が前記推定した完了時間よりも長いか否かを判定することを含む、請求項１に記載のジョブ実行方法。
【請求項６】
前記ジョブのタスクを前記残すタスクと前記移動するタスクとに分割することが、前記移動するタスクを準備するのに掛かる準備時間と前記移動して処理させたタスクの結果を取得するのに掛かる取得時間とを推定し、前記推定した完了時間と前記推定した準備時間及び取得時間と前記１つのコンピュータに対する前記他のコンピュータの性能比とに基づいて前記推定した完了時間を分割し、前記推定した完了時間を分割した分割比を前記残すタスクと前記移動するタスクとの分割比にすることを含む、請求項１に記載のジョブ実行方法。
【請求項７】
前記他のコンピュータとして前記複数のコンピュータの中のリソース使用率が低いコンピュータを選択して、前記リソース使用率が低いコンピュータに前記移動するタスクを移動して処理させることを含む、請求項１に記載のジョブ実行方法。
【請求項８】
前記移動するタスクを前記他のコンピュータに移動して処理させることが、前記１つのコンピュータで前記ジョブのタスクを処理するのと同じ様にして前記他のコンピュータに移動したタスクについても処理することを含み、前記他のコンピュータから前記移動して処理させたタスクの結果を取得することが、前記他のコンピュータで同じ様にしてタスクを処理してマージした結果を前記他のコンピュータから前記１つのコンピュータに戻すことを含む、請求項１に記載のジョブ実行方法。
【請求項９】
前記１つのコンピュータに前記ジョブを提供することが、前記複数のコンピュータに接続されたセンター・コンソールから前記１つのコンピュータに前記ジョブを提供することを含み、前記移動するタスクを前記他のコンピュータに移動して処理させることが、前記センター・コンソールが選択した前記他のコンピュータに前記移動するタスクを移動して処理させることを含み、前記センター・コンソールが前記１つのコンピュータでマージした結果を前記ジョブの結果として受け取る、請求項１に記載のジョブ実行方法。
【請求項１０】
ネットワーク接続された複数のコンピュータと、前記複数のコンピュータにネットワーク接続されたセンター・コンソールとを含み、任意のタスク数に分割可能なジョブを実行するジョブ実行システムであって、
前記コンピュータが、前記コンピュータの処理装置により実行される、前記ジョブのタスクを分割して結果をマージするための拡張部を含む拡張アプリケーション部と、前記処理装置により実行される、前記拡張アプリケーション部を起動して前記拡張アプリケーション部に前記ジョブのタスクを分割させ結果をマージさせる実行アダプタ部と、前記処理装置により実行される、前記実行アダプタ部を起動して前記拡張アプリケーション部及び前記実行アダプタ部を管理する実行管理部とを含み、
前記センター・コンソールが、前記センター・コンソールの処理装置により実行される、前記実行アダプタ部から前記コンピュータにおける前記ジョブの実行状況データを取得し、前記コンピュータで前記ジョブのタスクを分割するときに、分割タスクを移動する移動先として前記複数のコンピュータから他のコンピュータを選択して前記実行アダプタ部に指示する実行情報管理部を含む、
前記ジョブ実行システム。
【請求項１１】
前記拡張部が、
前記コンピュータで処理した前記ジョブのタスク数を監視し、タスク処理の進捗率のデータを生成する進捗監視部と、
前記コンピュータで未処理のタスクを前記コンピュータの記憶装置から読み出して分割し、移動するタスクのデータを生成して前記記憶装置に記憶する分割処理部と、
前記分割により残したタスクを処理した結果のデータと、前記分割により移動したタスクを移動先で処理した結果のデータとをマージするマージ処理部と、
前記進捗監視部、前記分割処理部及び前記マージ処理部を前記実行アダプタ部から呼び出すためのフック用ライブラリと、
を含む請求項１０に記載のジョブ実行システム。
【請求項１２】
前記実行アダプタ部が、
前記進捗監視部から前記タスク処理の進捗率のデータを取得して前記タスク処理の完了時間を推定し、前記コンピュータのメモリ装置から前記ジョブの要求項目のデータを取得して、前記推定した完了時間が前記要求項目を満たすか否かを判定する分割判定部と、
前記記憶装置から前記分割により移動するタスクのデータを準備し、前記メモリ装置から移動先のデータを取得し、前記実行管理部に提供してタスクの移動を実行させるタスク移動処理部と、
移動先で前記移動したタスクを処理することが終了したかを監視するタスク終了監視部と、
を含む請求項１１に記載のジョブ実行システム。
【請求項１３】
前記実行管理部が、拡張されたアプリケーションソフト及び実行アダプタソフトを提供されたときに前記拡張アプリケーション部及び前記実行アダプタ部を夫々生成し、前記分割により移動するタスクを移動先の前記他のコンピュータに提供する、請求項１０に記載のジョブ実行システム。
【請求項１４】
前記実行情報管理部が、
前記実行アダプタ部から前記コンピュータにおける終了ジョブ割合及びリソース使用率のデータを取得するジョブ実行状況監視部と、
前記ジョブ実行状況監視部から前記終了ジョブ割合及びリソース使用率のデータを取得して、ジョブ全体の進捗状況のデータを生成するジョブ実行状況表示部と、
を含む、請求項１０に記載のジョブ実行システム。
【請求項１５】
前記実行情報管理部が、
前記複数のコンピュータについての前記終了ジョブ割合及びリソース使用率のデータを取得して、前記終了ジョブ割合及びリソース使用率のデータに基づき移動先として前記他のコンピュータを選択し、当該選択した前記他のコンピュータを前記実行アダプタ部に指示する移動先選択部を含む、請求項１４に記載のジョブ実行システム。
【請求項１６】
前記センター・コンソールが、ユーザーから前記ジョブのアプリケーションソフト及びデータを受け付け、前記アプリケーションソフトから拡張されたアプリケーションソフトを作成すると共に実行アダプタソフトを作成し、前記ジョブのデータ、前記拡張されたアプリケーションソフト及び前記実行アダプタソフトを前記コンピュータに提供して前記ジョブを実行させ、前記コンピュータから前記ジョブを実行した結果を受け取って前記ユーザーに提供する、請求項１０に記載のジョブ実行システム。
【請求項１７】
ネットワーク接続された複数のコンピュータで任意のタスク数に分割可能なジョブを実行するためのプログラムであって、前記複数のコンピュータの中の１つのコンピュータに、
前記ジョブのタスクを所定時間処理し、
前記１つのコンピュータの処理装置により、前記所定時間におけるタスク処理の進捗率を算出して前記進捗率及び前記所定時間に基づき前記１つのコンピュータでのタスク処理の完了時間を推定し、
前記処理装置により、前記推定した完了時間が前記ジョブの要求項目を満たすか否かを判定し、
前記推定した完了時間が前記要求項目を満たす場合には、前記１つのコンピュータにおける前記ジョブのタスクを前記１つのコンピュータで処理して結果を生成し、
前記推定した完了時間が前記要求項目を満たさない場合には、前記処理装置により、前記１つのコンピュータにおける前記ジョブのタスクを前記１つのコンピュータに残すタスクと前記複数のコンピュータの中の他のコンピュータに移動するタスクとに分割し、
残した前記ジョブのタスクを前記１つのコンピュータで更に所定時間処理すると共、前記処理装置により、前記移動するタスクを前記他のコンピュータに移動して処理させ、
前記推定した完了時間が前記要求項目を満たすまで、前記タスク処理の完了時間を推定することから前記ジョブのタスクを分割して残した前記ジョブのタスクを更に所定時間処理すると共に前記移動するタスクを前記他のコンピュータに移動して処理させることまでを繰り返し、
前記処理装置により、前記他のコンピュータから前記移動して処理させたタスクの結果を取得して前記取得した結果と前記１つのコンピュータで処理したタスクの結果とをマージする、
ことを実行させるための前記プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ジョブのタスクを分散処理する技術に関し、より詳細には、ジョブ実行時に自律的にタスクを分割して処理する方法、その方法を実現するシステム及びその方法をコンピュータで実現するためのコンピュータプログラムに関する。
【背景技術】
【０００２】
グリッド・コンピューティング等の分散処理においては、計算機資源のリソースに対してジョブ（タスク）を割り当てることは、ジョブのパフォーマンス（終了時刻等）やリソース環境の稼働率を左右する重要な決定要素となっている。非特許文献１には、各ジョブの動作特徴を予め観測し、幾つかのパラメータ（ＣＰＵ平均使用率、ＣＰＵ使用のバースト率等）で表現されるプロファイルを作成して、割り当ての計画に利用する方法が示されている。ジョブの実行中に特別なドライバー等を用いて、リソースのサービス品質であるＱｏＳ（Quality of Service）を制御することによりその計画は遂行される。しかし、この方法には、プロファイルのない初めてのようなジョブに対応できないこと、たとえプロファイルの少数パラメータを利用しても複数ジョブがリソースを共有する状況を正確に予測することが困難であること、リソースのＱｏＳ制御のために特別な処理が必要であること等、重大な課題が残っている。
【０００３】
一方、非特許文献２には、稼動中のジョブを動的に他のリソース環境に再配置させる手法が示されている。アプリケーション層でのジョブには一切の修正を加えることなく、タスクに分割されたジョブ全体を他のリソース環境に移動させるので、実行中のジョブの状況に応じて実行の計画を動的に変更するといった用途に適用できる。しかし、タスクの構成を変えることなくジョブ全体を移動単位とするので、移動先として十分に適合するリソース環境が利用可能であることを前提とする。従って、高い使用率で稼動するリソース環境の場合には、移動先の割り当てが困難となることがある。それに、移動した後のジョブ実行の品質を保証するものではない。
【０００４】
また、特許文献１には、各ノードのタスク負荷量を定期的に格納するテーブルを共通アクセス可能な各ノードの共有メモリに有し、自ノード内で生成されたタスクが制限時間内に処理できないと判断されるときに、共有メモリを参照して自ノードより低いタスク負荷量の他ノードを探索し、処理できないタスクの代替処理を他ノードに依頼するようにした動的負荷分散並列計算機システムが示されている。各ノードで処理タスクが増加したときに、その増加分に対して動的に対応することができる。しかし、絶えず全てのノードにおけるタスク負荷量を検査してそのデータを各ノードの共有メモリに保持しておかなければならず、共有メモリを参照したときに自ノードより低いタスク負荷量の他ノードが常に見出される保証はなく、タスクの代替処理を他ノードに依頼できない事態も起こり得る。
【０００５】
さらに、特許文献２には、管理サーバにより、ジョブが割り当てられた計算機の稼動状況を監視し、稼動状況がジョブ終了時間等の所定の条件を満たさない場合に未完了のジョブを検出し、未完了のジョブを実行するのに必要なリソースの情報に基づき実行可能な他の計算機を抽出して、未完了のジョブを他の計算機に割り当てるようにしたジョブスケジューリング管理方法が示されている。リソースの稼動状況に応じたジョブスケジューリングを行うことができるが、ジョブを実行する複数の計算機について、ジョブ実行内容、ジョブ実行に必要なリソース、使用可能なリソース等の情報を常に管理サーバで集中管理して、管理サーバだけでジョブのスケジュールをしなければならない。
【０００６】
【非特許文献１】B. Urgaonkar and P. Shenoy andT. Roscoe, “ResourceOverbooking and Application Profiling in Shared Hosting Platforms”, In Proceedings of the FifthSymposium on Operating Systems Design and Implementation (OSDI), December 2002.
【非特許文献２】Paul Ruth, Junghwan Rhee,Dongyan Xu, Rick Kennell, Sebastien Goasguen, “Autonomic Live Adaptation ofVirtual Computational Environments in a Multi Domain Infrastructure”, International Conference onAutonomic Computing (ICAC) 2006
【特許文献１】特開平９−１６０８８４号公報
【特許文献２】特開２００５−３１７７１号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
本発明は、上記先行技術の課題を解決することができる、特に、稼動状況を事前に予測できないようなジョブ及びリソース環境に対して、ＳＬＡ（Service Level Agreement）及びＳＬＯ（Service Level Objective）等のジョブの要求を満たすように動的に且つ自律的にリソースの割り当て及び変更を行うことができるジョブ実行を実現することを目的とする。本発明の目的には、そのようなジョブ実行を実現する、ジョブを実行時に自律的にタスクを分割して処理する方法、その方法を実現するシステム及びその方法をコンピュータで実現するためのコンピュータプログラムを提供することが含まれる。本発明では、上記先行技術の課題を解決する際に、既に利用可能なリソース環境（Globus Toolkit 4 等）の上で動作させる等の汎用性も考慮され、さらに、均一な処理性能を有するリソース環境だけでなく、異機種混合のリソース環境や処理性能が変化するようなリソース環境においても、柔軟で適切なリソースの割り当てを行えることも考慮されている。
【課題を解決するための手段】
【０００８】
本発明によるネットワーク接続された複数のコンピュータで任意のタスク数に分割可能なジョブを実行する方法では、少なくとも次のことを行う。先ず、複数のコンピュータの中の１つのコンピュータにジョブを提供して、１つのコンピュータでジョブのタスクを所定時間処理する。そして、１つのコンピュータの処理装置により、所定時間におけるタスク処理の進捗率を算出して進捗率及び所定時間に基づき１つのコンピュータでのタスク処理の完了時間を推定する。それから、その処理装置により、推定した完了時間がジョブの要求項目を満たすか否かを判定する。この判定で推定した完了時間が要求項目を満たす場合には、１つのコンピュータにおけるジョブのタスクを１つのコンピュータで処理して結果を生成する。しかし、この判定で推定した完了時間が要求項目を満たさない場合には、その処理装置により、１つのコンピュータにおけるジョブのタスクを１つのコンピュータに残すタスクと複数のコンピュータの中の他のコンピュータに移動するタスクとに分割する。そして、残したジョブのタスクを１つのコンピュータで更に所定時間処理すると共、その処理装置により、移動するタスクを他のコンピュータに移動して処理させる。特に、この推定した完了時間が要求項目を満たさない場合には、推定した完了時間が要求項目を満たすまで、タスク処理の完了時間を推定することからジョブのタスクを分割して残したジョブのタスクを更に所定時間処理すると共に移動するタスクを他のコンピュータに移動して処理させることまでを繰り返す。それから、その処理装置により、他のコンピュータから移動して処理させたタスクの結果を取得して取得した結果と１つのコンピュータで処理したタスクの結果とをマージする。
【０００９】
本発明による上記方法では、好ましくは、移動するタスクを他のコンピュータに移動して処理させることに、１つのコンピュータでジョブのタスクを処理するのと同じ様にして他のコンピュータに移動したタスクについても処理することを含み、また、他のコンピュータから移動して処理させたタスクの結果を取得することに、他のコンピュータで同じ様にしてタスクを処理してマージした結果を他のコンピュータから１つのコンピュータに戻すことを含と良い。
【００１０】
本発明による任意のタスク数に分割可能なジョブを実行するシステムは、ネットワーク接続された複数のコンピュータと複数のコンピュータにネットワーク接続されたセンター・コンソールとを含み、少なくとも次の構成を成す。即ち、コンピュータが、コンピュータの処理装置により実行される、ジョブのタスクを分割して結果をマージするための拡張部を含む拡張アプリケーション部と、その処理装置により実行される、拡張アプリケーション部を起動して拡張アプリケーション部にジョブのタスクを分割させ結果をマージさせる実行アダプタ部と、その処理装置により実行される、実行アダプタ部を起動して拡張アプリケーション部及び実行アダプタ部を管理する実行管理部とを含む。また、センター・コンソールが、センター・コンソールの処理装置により実行される、実行アダプタ部からコンピュータにおけるジョブの実行状況データを取得し、コンピュータでジョブのタスクを分割するときに、分割タスクを移動する移動先として複数のコンピュータから他のコンピュータを選択して実行アダプタ部に指示する実行情報管理部を含む。
【００１１】
本発明による上記システムでは、好ましくは、拡張アプリケーション部の拡張部に、コンピュータで処理したジョブのタスク数を監視し、タスク処理の進捗率のデータを生成する進捗監視部と、コンピュータで未処理のタスクをコンピュータの記憶装置から読み出して分割し、移動するタスクのデータを生成して記憶装置に記憶する分割処理部と、分割により残したタスクを処理した結果のデータと、分割により移動したタスクを移動先で処理した結果のデータとをマージするマージ処理部と、進捗監視部、分割処理部及びマージ処理部を実行アダプタ部から呼び出すためのフック用ライブラリと、を含むと良い。  さらに、実行アダプタ部に、進捗監視部からタスク処理の進捗率のデータを取得してタスク処理の完了時間を推定し、コンピュータのメモリ装置からジョブの要求項目のデータを取得して、推定した完了時間が要求項目を満たすか否かを判定する分割判定部と、記憶装置から分割により移動するタスクのデータを準備し、メモリ装置から移動先のデータを取得し、実行管理部に提供してタスクの移動を実行させるタスク移動処理部と、移動先で移動したタスクを処理することが終了したかを監視するタスク終了監視部と、を含むと良い。
【００１２】
本発明による上記システムでは、センター・コンソールが、ユーザーからジョブのアプリケーションソフト及びデータを受け付け、アプリケーションソフトから拡張されたアプリケーションソフトを作成すると共に実行アダプタソフトを作成し、ジョブのデータ、拡張されたアプリケーションソフト及び実行アダプタソフトをコンピュータに提供してジョブを実行させ、コンピュータからジョブを実行した結果を受け取ってユーザーに提供するようにすると良い。
【００１３】
本発明によるネットワーク接続された複数のコンピュータで任意のタスク数に分割可能なジョブを実行するためのプログラムは、複数のコンピュータの中の１つのコンピュータに、少なくとも次のことを実行させる。即ち、先ず、ジョブのタスクを所定時間処理することである。そして、１つのコンピュータの処理装置により、所定時間におけるタスク処理の進捗率を算出して進捗率及び所定時間に基づき１つのコンピュータでのタスク処理の完了時間を推定することである。それから、その処理装置により、推定した完了時間がジョブの要求項目を満たすか否かを判定することである。この判定で推定した完了時間が要求項目を満たす場合には、１つのコンピュータにおけるジョブのタスクを１つのコンピュータで処理して結果を生成することである。しかし、この判定で推定した完了時間が要求項目を満たさない場合には、その処理装置により、１つのコンピュータにおけるジョブのタスクを１つのコンピュータに残すタスクと複数のコンピュータの中の他のコンピュータに移動するタスクとに分割することである。そして、残したジョブのタスクを１つのコンピュータで更に所定時間処理すると共、その処理装置により、移動するタスクを他のコンピュータに移動して処理させることである。特に、この推定した完了時間が要求項目を満たさない場合には、推定した完了時間が要求項目を満たすまで、タスク処理の完了時間を推定することからジョブのタスクを分割して残したジョブのタスクを更に所定時間処理すると共に移動するタスクを他のコンピュータに移動して処理させることまでを繰り返すことである。それから、その処理装置により、他のコンピュータから移動して処理させたタスクの結果を取得して取得した結果と１つのコンピュータで処理したタスクの結果とをマージすることである。
【発明の効果】
【００１４】
本発明により、稼動状況を事前に予測できないようなジョブ及びリソース環境に対して、ジョブの要求を満たすように動的に且つ自律的にリソースの割り当て及び変更を行うことができるジョブ実行が達成される。そのようなリソースの割り当ては、スケーラブルで汎用性があり、様々なリソース環境に柔軟で適切に対応できて、リソース環境の動的な状況変化にロバストである。
【発明を実施するための最良の形態】
【００１５】
本発明の実施態様では、任意の数のタスクに分割できるジョブが複数のノードで実行される。そして、各ノードにおけるタスクの稼動状況に応じて、必要であれば各ノードでタスクを適宜分割すると共に一部を他のノードに移動させて実行することにより、スケーラブルで適正なタスク分割を伴うジョブの分散実行が実現される。そのような分割可能なジョブとしては、多くのパラメータをそれぞれ試行するパラメータ・スイープ（parameter sweep）・アプリケーション、モンテカルロ・シミュレーション、分割統治（divide and conquer）・アプリケーション等が挙げられる。タスクの稼動状況に応じたタスク分割を伴うジョブの分散実行においては、データ処理の手順に次の動作を含む。
(1)  ジョブ全体を１つのノードに送り、１つのタスクとして実行を開始する。
(2)  ノードでのタスク処理において、実行終了希望時刻（デッドライン）やリソース使用コスト（課金）等の要求項目（ＳＬＡ/ＳＬＯ）に対して結果的に違反しそうな状況であると判定されたとき、実行中のタスクを一時的に中断する。
(3)  ジョブデータの範囲を分ける等の処理により、タスクを分割する。
(4)  処理タスクを残して、それ以外の分割タスクを他のノードに移動する。
(5)  処理タスク及び分割タスクをそれぞれ再開あるいは開始する。
(6)  各ノードにおいて、(2) から (5) の手順を繰り返す。
【００１６】
各ノードでは、ジョブ実行状況の詳細を予測するのではなくて、単純なカウンタ等を用いて要求項目違反の可能性を判定する。例えば、進捗を表すカウンタと総タスク量と経過時間とから、定期的に予想終了時刻を見積もり、所定のデッドラインと比較して要求項目違反の可能性を判定する。この判定は、各ノードで独立して行われるので、異機種が混ざった環境でも非常にロバストに動作するし、また、ローカル・ジョブによるパフォーマンスの揺らぎ等の影響についても柔軟に追従する。なお、最終的なジョブの結果は、分割・移動により動的に構成されたノードの階層的な木構造の関係を利用して、木構造の葉から根の方向へ逆に辿ることにより結果を階層的に集計することで、最初のノードに戻される。
【００１７】
本発明の１実施態様では、センター・コンソールとして機能するコンピュータ・システムの処理装置により実現される実行情報管理部が、リソースの全ノード群の上位に位置し、ユーザーからの問合せのインターフェースになったり、ジョブ全体の進捗状況やリソースの使用状況の監視、分割タスクの移動先ノード候補の提示等を行ったりして、ジョブ実行の全体をサポートする。センター・コンソールのコンピュータ・システムは、ジョブ定義のためのジョブ記述ファイルとノードのジョブ進捗状況を記録したテーブルとを記憶装置に保持する。ジョブ定義は、基本的にグリッド・システムに投入されるジョブの性質を記述したものであり、次のような情報を含む。
-  ジョブに関するＳＬＯ、例えば、実行終了希望時刻（デッドライン）。
-  アプリケーションに固有のパラメータ等を記述している入力ファイル。
-  ジョブを最初に投入した（木構造の根の部分となる）ノードのＩＤ。
また、ノードのジョブ実行状況管理テーブルは、次の項目を含む。
-  ノードＩＤ。
-  終了ジョブ割合。
-  リソース使用率。
-  処理すべきタスクの一部を移動させた移動先ノードリスト。
【００１８】
また、ジョブ実行ノードとして機能するコンピュータ・システムの処理装置により実現される実行アダプタ部が、グリッド・ミドルウエアによって起動された後に、ジョブ（タスク）のアプリケーションが拡張された拡張部を備える拡張アプリケーション部によってタスクの進捗状況を監視する。実行アダプタ部は、ノードのリソース使用率も監視して、定期的に実行情報管理部に報告する。実行情報管理部は、ジョブの分割・移動を行うノードから移動先ノードの問い合わせを受けたときに、その報告に基づいた適切な移動先ノードを回答する。タスクの進捗状況に応じてタスクを分割・移動するとき、実行アダプタ部は、拡張部によって、タスクの処理を一時的に中断させ、タスクを分割させ、分割タスクを他のノードに移動させ、残ったタスクを再開させる。また、実行アダプタ部は、拡張部によって、残ったタスクの処理結果と移動したタスクの処理結果をマージさせる。
【００１９】
以下、本発明を実施するための最良の形態を図面に基づいて詳細に説明するが、以下の実施形態は特許請求の範囲にかかる発明を限定するものではなく、また実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。なお、実施形態の説明の全体を通じて同じ要素には同じ番号を付している。
【００２０】
図１に、本発明の１実施形態に係る、ジョブ実行時に自律的にタスクを分割して処理するジョブ実行システム１００の概略構成を示す。図１に示されるように、本発明によるジョブ実行システム１００の実施形態においては，ネットワーク１０５を介してセンター・コンソール１１０が複数のノード１２０に接続されている。センター・コンソール１１０は、ノード１２０で実行するジョブについての情報の入出力とノード１２０でのジョブ実行状況の監視とを行う。ジョブを実際に実行するノード１２０が計算機資源１３０を構成する。計算機資源１３０の複数のノード１２０は、ノード１、ノード２、．．．ノードｎのように、それぞれがまたネットワーク１０５で接続されている。
【００２１】
センター・コンソール１１０は、入出力されるジョブについての情報を処理する、例えばＣＰＵのような処理装置１１１と、キーボード、マウス等の入力装置１１２と，ジョブ実行システム１００におけるジョブ実行状況の情報を表示する例えばＣＲＴディスプレイのような表示装置１１３と、種々のデータを記憶する例えばＨＤＤのような記憶装置１１４とを含むコンピュータ・システムで構成される。本発明を実施した場合には、ノード１２０でのジョブ実行の情報を管理する実行情報管理部１１５が処理装置１１１により実現される。実行情報管理部１１５については後で説明する。ジョブを処理するアプリケーションソフト、ジョブを記述したジョブ記述ファイル、処理対象のジョブデータ等のジョブについての情報は、入力装置１１２から入力しても良いし、又は、センター・コンソール１１０にネットワークで接続された端末装置等の外部装置から入力しても良い。
【００２２】
計算機資源１３０における各ノード１２０も，例えばＣＰＵのような処理装置１２１と、例えばＤＲＡＭのようなメモリ装置１２２と，例えばＨＤＤのような記憶装置１２３を含むコンピュータ・システムのようなジョブの実行に必要な機能を有するものであれば良く，それらの性能や機種は同一である必要はない。本発明は、クラスタ環境のみならず，グリッド環境に代表されるような異機種混合環境に対しても適用可能である。本発明を実施した場合には、ジョブを処理するソフトウェアのためのアプリケーション部１２４及びジョブの実行を管理するための実行管理部１２５に加えて、ジョブ実行時にタスクを分割して移動する実行アダプタ部１２６が処理装置１２１により実現される。
【００２３】
各ノード１２０では、実行管理部１２５のもとでアプリケーション部１２４のソフトウェアが実行される。実行管理部１２５は、任意のアプリケーションソフトを起動することができ、アプリケーションソフトの開始から終了までを管理し，呼び出し側との間で入出力データを確実にやりとりすることを保証する。実行管理部１２５は、例えば既存の製品であるGlobus Toolkit等を用いて実施することができる。本発明では、実行管理部１２５においてアプリケーション部１２４のアプリケーションソフトを直接起動せず，それらの間にソフトウェアで実現される実行アダプタ部１２６を介してアプリケーション部１２４のアプリケーションソフトを起動する。
【００２４】
図２は、センター・コンソール１１０における実行情報管理部１１５の主要機能の１実施形態をその構成及びデータの流れと共に示す機能ブロック図である。ジョブ受付部２００は，入力装置１１２等から、ユーザーが処理依頼するジョブを記述したファイル（デッドラインの記述を含む）即ちジョブ記述ファイルと、実際にそのジョブを処理するアプリケーションソフトと、処理の対象となるジョブデータとを受け付ける。そして、センター・コンソール１１０がユーザー依頼のジョブを本発明に従って実行するようなジョブ実行サービスを提供する場合には、実行アダプタソフト、拡張されたアプリケーションソフト、ジョブ記述ファイル及びジョブデータが、ジョブセットにしてジョブ受付部２００から適当なノード１２０の実行管理部１２５に提供される。この段階ではどのノード１２０に提供しても構わない。なお、センター・コンソール１１０が実行アダプタソフト及び拡張されたアプリケーションソフトを提供せずに、ユーザーがそれらを準備してジョブセットをセンター・コンソール１１０に提供し、センター・コンソール１１０からジョブセットを適当なノード１２０の実行管理部１２５に提供しても良い。右端の一番上にあるジョブセットを提供された実行管理部１２５は、最初にジョブの処理を実行するノード１２０に存在し、先ず実行アダプタソフトを起動して実行アダプタ部１２６を生成し、その後、実行アダプタ部１２６がアプリケーションソフトで生成されるアプリケーション部１２４を起動する。
【００２５】
ジョブ実行状況監視部２０５は、ジョブを処理しているノード１２０の実行アダプタ部１２６と通信し、終了ジョブ割合及びリソース使用率の各データを取得し、ジョブ実行状況表示部２１０へ各ノードのジョブ終了率のデータを提供する。また、ジョブ実行状況監視部２０５は、それらの終了ジョブ割合及びリソース使用率の各データを記憶装置１１４に提供する。それらの各データは、記憶装置１１４に設定されているノード管理テーブル３００に保持されると共に随時更新される。ジョブ実行状況監視部２０５と通信する実行アダプタ部１２６は簡略のため１つしか示されていないが、ジョブ実行状況監視部２０５が複数のノード１２０の実行アダプタ部１２６と通信してそれらのデータを取得することを理解されたい。
【００２６】
ジョブ実行状況表示部２１０は、受け取った各ノードのジョブ終了率のデータに基づいて、ジョブ処理全体についての進捗状況のデータを表示装置１１３に提供する。実行情報管理部１１５では、ジョブ実行状況監視部２０５からの各ノードのジョブ終了率のデータからジョブ全体についての進捗状況のデータを算出することができる。これにより、ジョブ全体についての進捗状況が、センター・コンソール１１０で表示装置１１３に表示され、そのセンターのオペレータ又はユーザーに通知される。
【００２７】
移動先選択部２１５は、実行アダプタ部１２６によりジョブを分割・移動する必要が生じた場合に、記憶装置１１４のノード管理テーブル３００を参照して各ノードのリソース使用率データを取得する。そして、移動先選択部２１５は、例えばそのリソース使用率データから各ノードのＣＰＵ使用率を調べて最もＣＰＵ使用率が低いノードを選択する、又はリソース使用率データを取得していないジョブ処理に未関与のノード等、各ノードのリソース使用率データに基づいて移動先ノードを選択し、選択した移動先ノードのノード名データをその実行アダプタ部１２６に提供する。ジョブの分割によりタスクを移動する必要が生じるノードは１つとは限らないので、移動先選択部２１５と通信する実行アダプタ部１２６は簡略のため１つしか示されていないが、移動先選択部２１５が複数のノード１２０の実行アダプタ部１２６と通信して移動先ノード名のデータを提供することを理解されたい。
【００２８】
結果出力部２２０は、最初にジョブ処理の実行を依頼したノード１２０の実行管理部１２５からジョブ処理の結果ファイルを受け取り、記憶装置１１４の結果ファイル３０５に保存する。右端の一番上にある実行管理部１２５について述べたとおり、右端の一番上と一番下にある実行管理部１２５は同じノードのものである。
【００２９】
図３に、記憶装置１１４に設定されているノード管理テーブル３００のデータ構成の１例を示す。ノード管理テーブル３００は、各ノードでのジョブ処理の実行状況を管理するテーブルなので、次のような項目についてのデータを含む。ノード名の欄にはノードＩＤのようなノードを一意に識別できる名称のデータを格納する。図３にはノード１及びノード２が代表的に示されている。終了ジョブ割合の欄には各ノードでの現時点で処理したタスクの割合を示すデータを格納する。各ノードではタスクが一つ一つ処理されるので、タスクを処理するたびに処理されたタスク数をカウントしてジョブの全タスク数と比較することにより、終了ジョブ割合は算出され得る。図３の（Ａ）に示されるように、ジョブ実行開始直後の所定時間にノード１では２％のタスクが終了し、ノード２ではタスクの処理はまだ行われていない。しかし、図３の（Ｂ）に示されるように、ノード１でのジョブの分割と移動後には、ノード１では３％のタスクが終了し、ノード２では１％のタスクが終了している。リソース使用率の欄には各ノードでのＣＰＵ、メモリ等計算機資源の使用率のデータを格納する。各ノードのＯＳコマンド(UNIX(R)であればvmstat等)を利用することにより、リソース使用率のデータを取得することができる。ジョブ実行開始直後の所定時間にノード１では８０％のリソースが使用されている。しかし、ノード１でのタスクの分割と移動後にはノード１では５０％のリソースが使用され、ノード２では６０％のリソースが使用されている。移動先ノードリストの欄には各ノードから他ノードへタスクが移動した場合の移動先ノード名のデータを格納する。ノード１でのジョブの分割と移動後にはノード１からノード２へタスクが分割されて移動している。これらの項目のデータは、ノード名の欄を除いて適宜更新される。
【００３０】
図４は，ノード１２０における実行アダプタ部１２６及び拡張アプリケーション部１２７の主要機能の１実施形態を実行管理部１２５と共に示す機能ブロック図である。従来のアプリケーションソフトでは、実行管理部１２５が、ジョブデータを受け取ると記憶装置１２３のジョブデータファイル４００に保存してアプリケーション部を起動する。アプリケーション部では、ジョブデータとして与えられたタスクが、記憶装置１２３のジョブデータファイル４００からジョブデータ処理部４０５に読み込まれて、タスク処理部４１０で処理される。そして、結果データが、結果データ処理部４１５に書き出されて実行管理部１２５に渡される。本発明においては、図１に示されたノード１２０のアプリケーション部１２４は、拡張されたアプリケーションソフトにより生成される拡張アプリケーション部１２７の構成を成す。拡張アプリケーション部１２７では、実行管理部１２５がジョブセットを受け取ると、実行アダプタソフト、拡張されたアプリケーションソフト及びジョブ記述ファイルが、記憶装置１２３のジョブ用ソフトファイル４２０に保持される。また、タスク処理部４１０で生成される結果データが、記憶装置１２３の結果データファイル４２５に保持される。そして、拡張アプリケーション部１２７には、拡張部４３０が設けられている。拡張部４３０には、分割処理部４３１、マージ処理部４３２、進捗監視部４３３及びそれらとタスク処理部４１０との間に介在するフック用ライブラリ４３４が含まれる。このように、ノード１２０でタスクを自律的に分割して移動することを実現するためにアプリケーション部１２４は拡張される。先に述べたとおり、実行情報管理部１１５からジョブセットが提供されたノード１２０の実行管理部１２５は、先ず実行アダプタソフトを起動して実行アダプタ部１２６を生成し、その後、実行アダプタ部１２６が拡張されたアプリケーションソフトを起動して拡張アプリケーション部１２７を生成する。
【００３１】
拡張部４３０のフック用ライブラリ４３４は、定期的に実行アダプタ部１２６の分割判定部４３５と通信して、タスク分割の判定を行う。このとき、拡張部４３０の進捗監視部４３３が、呼び出されてタスク処理の進捗率を算出し実行アダプタ部１２６に提供する。実行アダプタ部１２６は、タスク処理の進捗率から終了ジョブ割合を求めて、実行情報管理部１１５のジョブ実行状況監視部２０５に提供する。実行アダプタ部１２６は、分割判定部４３５で分割が必要と判定されたら、センター・コンソール１１０の実行情報管理部１１５に問い合わせて移動先のノードを確保し、その移動先ノード名のデータをメモリ装置１２２の移動先ノードリストに記憶する。そして、実行アダプタ部１２６は、分割ジョブデータを記憶装置１２３に書き出すための分割ジョブデータファイル４４０のファイル名をフック用ライブラリ４３４に通知する。
【００３２】
フック用ライブラリ４３４は拡張部４３０の分割処理部４３１を呼び出し、分割処理部４３１により、未処理タスクが記憶装置１２３から読み出されて分割され、移動する部分がファイル名指定の記憶装置１２３の分割ジョブデータファイル４４０に書き出され保持される。また、自ノードでのタスク処理範囲が残す部分だけに修正される。そして、タスク移動の準備ができたことが実行アダプタ部１２６に通知される。特に、拡張アプリケーション部１２７では分割比率と出力ファイル名が指定されて、未処理ジョブデータが指定された分割比率で分けられると共に、移動される未処理ジョブデータが指定された出力ファイルに書き出される。この出力ファイルは移動先ノードに提供されて、移動先ノードで処理対象の入力ファイルとなる。
【００３３】
実行アダプタ１２６のタスク移動処理部４４５により、ジョブ定義のジョブ記述ファイルが作成され、拡張アプリケーション部１２７と実行アダプタ部１２６（指定したファイル名）と共に、実行管理部１２５に新しいタスクの移動が依頼される。このとき、移動先ノードは、分割判定部４３５で確保してメモリ装置１２２に記憶した移動先ノードリストのノードである。移動先ノードでのタスク処理が終了すると、移動先ノードから分割結果データが提供され記憶装置１２３の分割結果データファイル４５０に保持される。
【００３４】
拡張アプリケーション部１２７でのタスク処理が終了したら、フック用ライブラリ４３４によりマージ処理が行なわれる。フック用ライブラリ４３４は、実行アダプタ１２６のタスク終了監視部４５５に問い合わせて、タスク処理を委譲した移動先ノードがタスク処理を終了するのを待って、分割結果データを入手し、記憶装置１２３の分割結果データファイル４５０に保持する。そして、フック用ライブラリ４３４は、拡張部４３０のマージ処理部４３２を呼び出し、マージ処理部４３２は、分割結果データを記憶装置１２３の分割結果データファイル４５０から読み込み、記憶装置１２３の結果データファイル４２５に記憶されている自ノードの結果データとマージする。これを、タスク処理を委譲した移動先ノードの数だけ繰り返す。タスク処理部４１０では、マージ処理が終ると、マージされた結果データが、最後に結果データとして結果データ処理部４１５に書き出され、実行管理部１２５に渡される。
【００３５】
実行管理部１２５は、グリッド・ミドルウエア等から成り、実行アダプタ部１２６を起動するのであるが、それ以外に、ジョブデータ等ジョブセットを他ノードの実行管理部１２５から受け取り、記憶装置１２３に保存する。図４には、実行管理部１２５はジョブデータ等ジョブセットを他ノードの実行管理部１２５から受け取るように示されているが、最初にジョブが提供されたノードの場合には、他ノードの実行管理部１２５ではなくてセンター・コンソール１１０の実行情報管理部１１５であることを理解されたい。また、実行管理部１２５は、拡張アプリケーション部１２７の結果データ処理部４１５から結果データを取得し、ジョブセットを提供した他ノードの実行管理部１２５にその結果データを戻す。このように、実行管理部１２５はジョブセットの入力から結果データの出力に至るまでのプロセスを管理する。実行管理部１２５のこのような処理に例えば既存のツールであるGlobus Toolkit 4（GT4）やGRAM（Globus Resource Allocation Manager）を用いることができる（図４の４６０）。さらに、実行管理部１２５は、ノードでタスクを分割して移動する場合に、実行アダプタ部１２６のタスク移動処理部４４５から実行アダプタソフト、アプリケーションソフト及びジョブ記述ファイルと分割・移動されるジョブデータ及び移動先ノード名データとを取得して、その移動先ノードの実行管理部１２５にそれらを提供する。実行管理部１２５のこのような処理に例えば既存のglobusrun-wsを用いることができる（図４の４６５）。
【００３６】
図５に、本発明の実施によりアプリケーションを拡張する方法を概略的に示す。図５の（Ａ）に対象となる１例に過ぎないアプリケーションの基本動作が示されている。対象となるアプリケーションは、ジョブの処理を開始し（ステップ５００）、ジョブデータを入力データとして読み込み（ステップ５０５）、全てのタスクを処理したかどうかを判定し（ステップ５１０）、全てのタスクを処理した場合には、ジョブ処理を終了し（ステップ５１５）、全てのタスクを処理していない場合には、一つずつタスクの処理を行い（ステップ５２０）、最後に結果データを記憶装置１２３の結果データファイル４２５に出力する、以上の動作を行うものとする。この他にも、再帰的にタスクを処理するアプリケーション等が考えられる。
【００３７】
図５の（Ｂ）に本発明による拡張されたアプリケーションの動作が示されている。本発明においては，アプリケーション本来の処理フローは変更することなく，拡張部（太線の部分）を図５の（Ｂ）の処理フローに示されるステップ５２５及び５３０の位置に挿入するだけで，ジョブの自律的な分割・移動の機能を実現している。この拡張された機能は、所定の頻度で例えばタスクを処理するたびにジョブの分割が必要かどうかのテストを行い、必要であれば実際に分割を行うためのジョブ分割処理のフックを追加することと、全てのタスクを終了した後でジョブ実行時に他のノードに移動したタスク処理の結果を集めてマージするためのマージ処理のフックを追加することである。拡張部４３０に、これらのフックのためにフック用ライブラリ４３４が追加される以外に、分割処理部４３１、マージ処理部４３２及び進捗監視部４３３が、処理フローとは独立したコールバックの形式で追加される。これらのコールバック型拡張部（コンポーネント）はそれぞれフック用ライブラリ４３４から同期的に呼び出される。なお、タスクが分割・移動された場合には、分割後に残ったタスクを処理した結果が、拡張アプリケーション部１２７の一時的な出力ファイルに書き出される。最終的には、移動先ノードからの結果とマージして本来のジョブの処理結果を生成する。
【００３８】
図６に、ジョブ分割処理のフック（図５のステップ５２５）における動作を概略的に表わした流れを６００として示す。フック用ライブラリ４３４によりフックを開始して（ステップ６０５）、先ず、拡張部４３０の進捗監視部４３３を呼び出し、タスク処理の進捗率を取得する（ステップ６１０）。次に、実行アダプタ部１２６の分割判定部４３５に取得した進捗率を提供して分割の判定をさせる（ステップ６１５）。分割判定部４３５によりタスクの分割が必要であると判定されたときには、分割したジョブデータを書き込むためのファイル名と分割比とを分割判定部４３５から受け取る。タスクの分割が必要でなければ（ステップ６２０）、フック処理を終える（ステップ６４５）。タスクの分割が必要であれば（ステップ６２０）、コールバック型拡張部の分割処理部４３１を呼び出し、分割比とファイル名を渡して分割を依頼する（ステップ６２５）。分割処理部４３１により分割されたタスクの第１部分、例えばタスクの前半部分を移動するかどうかを判定し（ステップ６３０）、分割タスクの第１部分を移動する場合には、実行アダプタ部１２６のタスク移動処理部４４５に分割タスクの第１部分を移動先ノードに移動させる（ステップ６３５）。移動しない分割されたタスクの第２部分、例えばタスクの後半部分は、実行アダプタ部１２６により自ノードでの処理のため追加起動される。分割タスクの第１部分を移動させない場合には、実行アダプタ部１２６のタスク移動処理部４４５に分割タスクの第２部分を移動先ノードに移動させる（ステップ６４０）。移動しない分割タスクの第１部分は、実行アダプタ部１２６により自ノードでの処理のため追加起動される。いずれの場合も、実行アダプタ部１２６に分割タスクの第１部分又は第２部分の移動を依頼して、フック処理を終了する（ステップ６４５）。
【００３９】
図７は、実行アダプタ部１２６の分割判定部４３５における処理の概略な流れを７００として示す。分割判定部４３５では、進捗監視部４３３からのタスク処理の進捗率に基づいてタスク分割の必要性を判定し、タスク分割が必要であれば移動先ノードを確保して、分割ジョブデータを書き込むための分割入力ファイル名と分割比とを決める。先ず、図６のステップ６１０よりメモリ装置１２２に保持されている、進捗監視部４３３から取得したタスク処理の進捗率ｐ（０＜ｐ＜１）が入力として提供され、メモリ装置１２２の開始時刻のデータを参照して、経過時間Ｔを算定する（ステップ７０５）。次に、進捗率ｐと経過時間Ｔとから、ジョブの完了までに掛かる完了時間ＴＥを、ＴＥ＝Ｔ（１−ｐ）/ｐより推定する（ステップ７１０）。それから、メモリ装置１２２に保持されているデッドライン時刻のデータを参照してデッドライン時刻までに残っている残余時間を算定し、完了時間ＴＥと比較する（ステップ７１５）。残余時間のほうが長ければ、分割不要として分割判定の処理を終え、図６のステップ６２０へ進む。残余時間が完了時間ＴＥよりも長くなければ、センター・コンソール１１０の実行情報管理部１１５に問い合わせて、移動先のノードを確保する（ステップ７２０）。このとき、実行情報管理部１１５より確保した移動先ノード名のデータをメモリ装置１２２の移動先ノードリストに記録・更新しておく。なお、センター・コンソール１１０の実行情報管理部１１５に問い合わせる方法のほかにも、Ｐ２Ｐ（ピア・ツー・ピア）方式でブロードキャストを使って周囲のノードの実行管理部１２５に問い合わせて移動先ノードを決定する方法もある。さらに、分割比を決定する（ステップ７２５）。分割比の決定については後で言及する。分割したタスクの内の移動する部分を書き込むためのファイル名を決定して、分割入力ファイル名のデータをメモリ装置１２２に記録・更新する（ステップ７３０）。最後に分割比とファイル名の各データを呼び出して、それらを出力として図６のステップ６２０に進む。タスクの分割が必要でなければ、何も出力しない。
【００４０】
図８は、実行アダプタ部１２６のタスク移動処理部４４５における処理の概略な流れを８００として示す。図６のステップ６３０より、タスク移動処理部４４５は、タスク移動の依頼を受けたら、以下のステップで処理を進める。先ず、分割されたタスクの結果を書き込むためのファイル名を決定して、分割出力ファイル名のデータをメモリ装置１２２に記録・更新する（ステップ８０５）。次に、メモリ装置１２２の移動先ノード名等の情報を参照して、ジョブ定義のジョブ記述ファイルを作成する（ステップ８１０）。それから、記憶装置１２３のジョブ用ソフトファイル４２０からジョブ記述ファイル、実行アダプタソフト及び拡張されたアプリケーションソフトを実行管理部１２５に提供して、分割ジョブ実行の依頼を行わせる（ステップ８１５）。
【００４１】
図９を参照して、オーバーヘッドを考慮したタスク分割の割合決定方法９００について説明する。あるノードＡにおいて、タスクの分割が必要と判断されたなら、先ず、分割データのコピー等の準備に掛かる準備時間ＴＳＩと、遠隔ノードＢでの処理が完了した後で処理結果を受け取るのに掛かる取得時間ＴＳＯとを想定して、推定した完了時間ＴＥにそれらを足し合わせて２分割にし、ＴＥの内のノードＡに残す例えば前半部のような分割タスク第１部分の所要時間をＴ１とし、ＴＥの内の残りをノードＢに委譲する例えば後半部のような分割タスク第２部分の所要時間をＴ２とする。ノードＡとノードＢとに性能の差がある場合には、その性能比をｒ（ノードＢがノードＡよりも処理速度が遅い場合は、ｒ＜１）として、図９に示すように、重み付けをした分割比を計算する。
ＴＥ＝Ｔ１＋Ｔ２
Ｔ１＝ＴＳＩ＋ＴＳＯ＋Ｔ２/ｒ  より
Ｔ１＝ＴＥ/(１＋ｒ) ＋ ｒ(ＴＳＩ＋ＴＳＯ)/(１＋ｒ)
Ｔ２＝ｒＴＥ/(１＋ｒ) − ｒ(ＴＳＩ＋ＴＳＯ)/(１＋ｒ)
【００４２】
これらの所要時間Ｔ１及びＴ２の比率より、即ち、残すタスク対移動するタスクの比率がＴ１対Ｔ２の比率となるように、タスクの分割比を決めると良い。この分割処理により短縮される実行時間ＴＲは、ＴＥから第１部分の所要時間Ｔ１と分割処理のオーバーヘッドＴＤ及びマージ処理のオーバーヘッドＴＭとを差し引いた長さになる。この長さＴＲがゼロ以下となる場合には分割による効果がなく、逆に分割によりジョブ実行時間が延びると判断できる。従って、ＴＲがＴＥに比べてある程度大きい場合に限り分割処理を進めるといった判断が必要になる。例えば、計算ノードの上限数から主に決められる閾値ｓを設定して、ＴＲ/ＴＥ＞ｓを判定する。
ＴＲ＝(ＴＥ−ＴＳＩ−ＴＳＯ)ｒ/(１＋ｒ) −ＴＤ−ＴＭ ＞ｓＴＥ
【００４３】
図１０に、ジョブデータが再帰的に複数ノードで分割・移動される１例１０００を示す。センター・コンソール１１０の実行情報管理部１１５は、図１０に示すように、ジョブデータ（１００％）、実行アダプタソフト（ＥＡ）、アプリケーションソフト（Ａ）及びジョブ記述ファイル（ＪＤ）を適当なノード（ここではノード１）に全て投入する。ノード１では、先に説明した手順に沿ってジョブを実行するが、デッドラインを満たせないと予想され、タスクの分割・移動の必要性が生じた段階でノード２へタスクの移動を行う。図１０では、ジョブ全体の２％を処理した段階で残り９８％を２分割し、４９％をノード２へ移動させたことを表している。また、さらに１％を処理した後再びタスクの移動の必要が生じ、残り４８％を２分割し、今度はノード３へ２４％のタスクを移動させたことを表している。そして、さらに２％を処理した後再びタスクの移動の必要が生じ、残り２２％を２分割し、今度はノード５へ１１％のタスクを移動させたことを表している。
【００４４】
他のノードでも同様のことが起きている。即ち、ノード２でも、ノード１からジョブデータの４９％を提供され、１％を処理した後タスクの移動の必要が生じ、残り４８％を２分割し、ノード４へ２４％のタスクを移動させたことを表している。また、さらに２％を処理した後再びタスクの移動の必要が生じ、残り２２％を２分割し、今度はノード７へ１１％のタスクを移動させたことを表している。やはり、ノード４でも、ノード２からジョブデータの２４％を提供され、２％を処理した後タスクの移動の必要が生じ、残り２２％を２分割し、ノード８へ１１％のタスクを移動させたことを表している。この例は、分割・移動がノード１→ノード２、ノード２→ノード４、ノード１→ノード３、ノード１→ノード５、ノード２→ノード７、ノード４→ノード８の順に起きた場合を示している。このように、本発明では、実際にどのような順番でタスクの分割・移動が発生するかは、前もって予測しないし、またその必要もない。
【００４５】
図１１は、マージ処理のフック（図５のステップ５３０）における動作を概略的に表わした流れを１１００として示す。マージ処理のフックの動作では、図５（Ｂ）の５１０より開始され、先ず、実行アダプタ部１２６のタスク終了監視部４５５にタスク終了待ちであることを通知してタスク終了のモニタを依頼する（ステップ１１０５）。次に、マージすべき分割結果が存在するか判定する（ステップ１１１０）。マージすべき分割結果がなければ、図５（Ｂ）の５３５へ進んでフック処理を終了する。マージすべき分割結果があれば、分割結果データを出力したファイル名を拡張部４３０のマージ処理部４３２に提供してマージ処理部４３２を呼び出し、マージ処理を行って結果データを更新する（ステップ１１１５）。このようにして、自ノードよりタスクを分割・移動させた移動先ノードからの結果を全て読み込みマージしたら、自ノードにおける最終結果データとして実行管理部１２５から出力する。
【００４６】
図１２に、マージ処理のタスク終了待ち（図１１のステップ１１０５）における動作を概略的に表わした流れを１２００として示す。実行アダプタ部１２６のタスク終了監視部４５５で移動先ノードのタスク終了を待つ処理の流れは、次のとおりである。図５（Ｂ）の５１０又は図１１の１１１５より開始され、メモリ装置１２２を参照して、移動先のタスクが全て終了したかどうかを判定する（ステップ１２０５）。移動先のタスクが全て終了したならば、図１１の１１１０を経て図５（Ｂ）の５３５へ進み、マージ処理は不要として終了する。移動先のタスクが全て終了していなければ、未了移動先タスクが終了するまでブロックして待つ（ステップ１２１０）。未了移動先タスクが終了したら、移動先分割タスクの結果データのファイルを準備して記憶装置１２３の分割結果データファイル４５０に書き込む（ステップ１２１５）。その後は、図１１の１１１０へ進む。
【００４７】
図１３に、各ノードでタスクが終了した後、各ノードにおける処理結果がどのように回収・マージされ、全体の結果がセンター・コンソール１１０の実行情報管理部１１５へと戻って来るかを示す。マージの処理は分割・移動の過程を逆に辿ることによって行われる。例えば、分割・移動の過程でノード２→ノード４→ノード８という順にタスクが分散したため、末端のノード８でタスクが終了した後、部分結果ファイルがノード４へと戻され、さらにノード４における部分結果とマージされた結果がノード２へ戻される、という過程に従う。ノード２だけでなく、ノード１より分割・移動が生じた他のノード３及５からも部分結果ファイルがノード１へと戻される。このようして、各ノードで得られた結果はマージされつつ最初にジョブを投入したノード１へと戻り、ノード１でジョブ全体の最終結果が得られる。
【００４８】
図１４は、本発明によるタスクの分割・移動の様子を分かり易く表した概念図である。本発明では、タスク処理において目標のデッドラインを満たすために、少しずつタスクの分割を各ノードで繰り返して、最終的にリソースの全ノードでデッドライン目標を達成できるようにする。先ず、（ａ）に示されるように、最初は全体量等が不明のジョブを処理するものとする。このジョブに対するデッドラインが与えられる。（ｂ）で、例えばセンター・コンソールから投入されて１つのノードでタスク処理が開始される。短時間（Ｔ）だけタスク処理が実行されて（角柱の濃い部分）、タスク処理の終了時間が推定される。これによって、最初は全体量等が不明であったが、ジョブの試行と試行からの推定とで、終了時間が推定されジョブの全体量が大体把握される。明らかに推定される終了時間（角柱の下端）はデッドラインを超えている。そこで、（ｃ）では、ノードのタスク処理が中断され、タスクの分割が行われてタスクの後半部分（角柱の下部分）が他ノードに移動される。（ｄ）では、タスク処理が再開され、タスク処理が行われている各ノードでは、また短時間（Ｔ）だけタスク処理が行われて（角柱の濃い部分）、タスク処理の終了時間が再び推定される。各ノードでの推定される終了時間（角柱の下端）は、リソース使用率の変動やタスクの分割・移動により変化する。最初のノードでは、（ｃ）及び（ｄ）の分割時の終了時間よりも、夫々（ｄ）及び（ｅ）での再度推定した終了時間のほうが長い。（ｅ）でも、全ての分割されたタスクがデッドライン前に完了すると推定されるまで、推定される終了時間（角柱の下端）がデッドラインを超えているかの検査が各ノードで行われ、タスクの中断、分割、移動及び再開は繰り返される。
【００４９】
デッドライン目標が達成可能であると判定された後も、そのような検査を定期的に繰り返し各ノードで行うことにより、リソースの使用状況が時々刻々と変化している場合にも柔軟に追従することができる。また、タスクの全体量が少ない程、終了時間の推定精度は高くなる。従って、タスクの分割により各ノードではタスクの量を少なくして終了時間を推定することができるので、デッドライン目標を達成可能であるかどうかの検査は結果の確度が担保される。図１４により、１つのノードに投入したジョブを実行しながら自律的にタスクを分割して、そのジョブを最終的に６つのノードに分散して実行することになった経緯が分かる。なお、各ノードでタスクが次々と分割時に２分割される例が示されているが、分割時に２分割よりも多いい複数分割を適切な分割比率で行うようにしても良く、本発明におけるタスク分割がそのような２分割に限定されないことを理解されたい。また、各ノードにおけるデッドラインまでの空いた時間は、同様に他のジョブを実行するために使われる。
【００５０】
図１５は、本発明において５つの異なる複数のジョブがどのように稼動するかその様子を表したグラフである。図１５の（Ａ）は、要求リソース（プロセッサ）数と想定処理時間とを与えてスケジュールを作成し、リソースを予約してそれら複数のジョブを処理する従来方式を示している。このように、スケジュールを作成するためにも、それら複数のジョブについての情報が事前に必要である。これに対して、図１５の（Ｂ）は、本発明によりジョブを実行中に自律的にタスクを分割しながらリソースを割り当ててそれら複数のジョブを処理する方式を示している。図１５の（Ａ）のような異なるジョブ間にリソースが稼動していないような時間は存在せず、リソースの稼働率が高くなり、そのために全体的にジョブの終了時刻も早くなっていることが分かる。
【００５１】
以上、実施形態を用いて本発明の説明を行ったが、本発明の技術的範囲は上記実施形態に記載の範囲には限定されない。上記実施形態に種々の変更又は改良を加えることが可能であり、そのような変更又は改良を加えた形態も当然に本発明の技術的範囲に含まれる。
【図面の簡単な説明】
【００５２】
【図１】本発明の１実施形態に係るジョブ実行システムの概略構成を示す図である。
【図２】実行情報管理部の主要機能の１実施形態を示す機能ブロック図である。
【図３】センター・コンソールの記憶装置におけるノード管理テーブルのデータ構成例を示す図である。
【図４】実行アダプタ部及び拡張アプリケーション部の主要機能の１実施形態を示す機能ブロック図である。
【図５】本発明の実施によりアプリケーションを拡張する方法を概略的に示す図である。
【図６】ジョブ分割処理のフックにおける動作を概略的に表わした流れ図である。
【図７】分割判定部における動作を概略的に表わした流れ図である。
【図８】タスク移動処理部における動作を概略的に表わした流れ図である。
【図９】オーバーヘッドを考慮したタスク分割の割合決定方法を概略的に示す図である。
【図１０】本発明によるタスクの分割・移動の様子を分かり易く表した概念図である。
【図１１】マージ処理のフックにおける動作を概略的に表わした流れ図である。
【図１２】タスク終了監視部における動作を概略的に表わした流れ図である。
【図１３】各ノードから処理結果が回収・マージされる１例を示す図である。
【図１４】ジョブデータが再帰的に複数ノードで分割・移動される１例を示す図である。
【図１５】５つの異なる複数のジョブがどのように稼動するかを表したグラフである。
【符号の説明】
【００５３】
１００  ジョブ実行システム
１１０  センター・コンソール
１１１  処理装置
１１４  記憶装置
１１５  実行情報管理部
１２０  ノード
１２１  処理装置
１２２  メモリ装置
１２３  記憶装置
１２５  実行管理部
１２６  実行アダプタ部
１２７  拡張アプリケーション部
４３０  拡張部
４３１  分割処理部
４３２  マージ処理部
４３３  進捗監視部
４３４  フック用ライブラリ
４３５  分割判定部
４４５  タスク移動処理部
４５５  タスク終了監視部
【図１】
2008123205.tif 000003
【図２】
2008123205.tif 000004
【図３】
2008123205.tif 000005
【図４】
2008123205.tif 000006
【図５】
2008123205.tif 000007
【図６】
2008123205.tif 000008
【図７】
2008123205.tif 000009
【図８】
2008123205.tif 000010
【図９】
2008123205.tif 000011
【図１０】
2008123205.tif 000012
【図１１】
2008123205.tif 000013
【図１２】
2008123205.tif 000014
【図１３】
2008123205.tif 000015
【図１４】
2008123205.tif 000016
【図１５】
2008123205.tif 000017
【手続補正書】
【提出日】平成19年5月11日(2007.5.11)
【手続補正１】
【補正対象書類名】図面
【補正対象項目名】図１２
【補正方法】変更
【補正の内容】
【図１２】
2008123205.tif 000018