(57)【特許請求の範囲】
【請求項１】
ネットワークに接続されアプリケーションを実行するクライアントと、当該ネットワークに接続され当該アプリケーションの実行環境を保持した状態で当該アプリケーション中の所定の計算部分に特化して処理サービスを提供するＣＰＵ資源プロバイダとを含み、
前記クライアントは、前記ＣＰＵ資源プロバイダに対するジョブのリクエストに際して当該ジョブの予測計算時間に関する情報を前記ネットワークを介して当該ＣＰＵ資源プロバイダに送信し、
前記ＣＰＵ資源プロバイダは、前記クライアントから送信された前記予測計算時間に基づき、当該予測計算時間を修正し、修正された予測計算時間をリソーススケジューリングに利用して前記ジョブの割り当てを行うことを特徴とするネットワークシステム。
【請求項２】
前記クライアントは、ネットワークに接続されるユーザ端末とのアプリケーション使用契約に伴い当該アプリケーションを提供するアプリケーションサービスプロバイダであることを特徴とする請求項１記載のネットワークシステム。
【請求項３】
前記ＣＰＵ資源プロバイダは、過去になされた前記クライアントの予測計算時間に対する実際のジョブ実行時間から得られた誤差情報を含むプロファイルを保持し、前記予測計算時間に対して前記プロファイルに基づく修正を施して前記ジョブの割り当てを行うことを特徴とする請求項１記載のネットワークシステム。
【請求項４】
前記ＣＰＵ資源プロバイダは、前記クライアントからリクエストのあった前記ジョブのスケジュールを当該クライアントに通知することを特徴とする請求項１記載のネットワークシステム。
【請求項５】
ネットワークに接続されたクライアントにて実行されるアプリケーションの実行環境を保持した状態で当該アプリケーション中の負荷の高い計算部分に特化して処理サービスを提供するＣＰＵ資源プロバイダであって、
前記クライアントのプロファイルを格納するプロファイル格納手段と、
前記クライアントからのジョブのリクエストに伴い、当該ジョブの予測計算時間を当該クライアントから受信する予測計算時間受信手段と、
前記プロファイル格納手段に格納された前記プロファイルをもとに、前記予測計算時間受信手段により受信された前記予測計算時間を修正する修正手段と
を備えることを特徴とするＣＰＵ資源プロバイダ。
【請求項６】
前記修正手段により修正された前記予測計算時間に基づいてジョブの割り当てを行うジョブ割当手段を更に備えたことを特徴とする請求項５記載のＣＰＵ資源プロバイダ。
【請求項７】
前記プロファイル格納手段は、前記プロファイルとして前記クライアントにおける計算時間予測の正確性を示す予測精度情報を格納し、前記ジョブにおける実際のジョブ実行時間に基づいて当該予測精度情報を更新することを特徴とする請求項５記載のＣＰＵ資源プロバイダ。
【請求項８】
クライアントにて実行されるアプリケーションの実行環境を保持した状態で当該アプリケーション中の所定の計算部分に特化して処理サービスを提供するＣＰＵ資源プロバイダであって、
前記クライアントから送信された予測計算時間に基づき、当該予測計算時間を修正して、当該クライアントからリクエストがあったジョブの実行時間を予測する実行時間予測手段と、
現在割り当て可能なノード数を把握する第１のノード数把握手段と、
予測された前記実行時間を用いて、前記第１のノード数把握手段により把握された現在割り当て可能なノード数にて前記ジョブを即座に実行したときの第１の終了予測時間を把握する第１終了予測時間把握手段と、
現在実行中である所定の実行中ジョブの終了を待って前記ジョブを実行したときに割り当て可能なノード数を把握する第２のノード数把握手段と、
予測された前記実行時間を用いて、前記第２のノード数把握手段により把握された前記ノード数にて前記ジョブを実行したときの第２の終了予測時間を把握する第２終了予測時間把握手段と、
把握された前記第１の終了予測時間および前記第２の終了予測時間に基づき、即座に実行する際または所定の実行中のジョブの終了を待った後に所定のノードを確保して前記ジョブを割り当てる割当手段と
を備えたことを特徴とするＣＰＵ資源プロバイダ。
【請求項９】
前記実行時間予測手段は、前記クライアントからの前記リクエストの到着があったときに、当該クライアントの予測傾向として存在する偏向傾向を過去の履歴から把握して前記予測計算時間を修正することを特徴とする請求項８記載のＣＰＵ資源プロバイダ。
【請求項１０】
前記第１終了予測時間把握手段と前記第２終了予測時間把握手段は、所定の確率でジョブが終了するまでの時間の共通の尺度を用いて前記第１の終了予測時間および前記第２の終了予測時間を把握し、
前記割当手段は、前記時間の共通の尺度を比較して現在実行中のジョブの終了を待つか否かを判断することを特徴とする請求項８記載のＣＰＵ資源プロバイダ。
【請求項１１】
アプリケーションを実行するクライアントからネットワークを介してなされるリクエストに基づいて当該アプリケーションの実行環境が保持された状態で当該アプリケーション中の計算負荷の高い部分に特化して処理サービスを提供する処理サービスの提供方法であって、
リクエストのあったジョブに対して、前記クライアントから前記ネットワークを介して当該ジョブの予測計算時間を受信し、
前記クライアントから前記ネットワークを介して受信した前記予測計算時間に基づき、前記処理サービスを提供する側で当該予測計算時間を修正してジョブの実行時間を推定し、
前記処理サービスを提供する側にて、推定された前記実行時間に基づいて前記ジョブに対するリソースの割り当てを行うことを特徴とする処理サービスの提供方法。
【請求項１２】
前記実行時間は、前記ジョブをリクエストしたクライアントの予測計算時間に対する予測傾向を示すクライアントプロファイルを参照して推定されることを特徴とする請求項１１記載の処理サービスの提供方法。
【請求項１３】
アプリケーションを実行するクライアントからのネットワークを介してなされるリクエストに基づいて当該アプリケーションの実行環境が保持された状態で当該アプリケーション中の計算負荷の高い部分に特化して処理サービスを提供する処理サービスの提供方法であって、
リクエストのあったジョブに対して、前記クライアントから前記ネットワークを介して受信した予測計算時間に基づき、前記処理サービスを提供する側で当該予測計算時間を修正して当該ジョブの実行時間を推定し、
推定された前記実行時間を用いて、現在の空きノードに対して前記ジョブを割り当てた際のジョブ終了予測と、現在実行中である所定のジョブが終了した後の空きノードに対して当該ジョブを割り当てた際のジョブ終了予測とを行い、これらのジョブ終了予測に基づき、現在の空きノードに対して当該ジョブを割り当てて実行するかまたは現在実行中の所定のジョブが終了した後に空きノードに対して当該ジョブを割り当てて実行するかを選択して、当該ジョブに対するリソースの割り当てを行うことを特徴とする処理サービスの提供方法。
【請求項１４】
前記ジョブにおける前記実行時間は、前記クライアントからのリクエストと同時に受信される予測計算時間に基づいて推定されることを特徴とする請求項１３記載の処理サービスの提供方法。
【請求項１５】
ネットワークに接続されたクライアントにて実行されるアプリケーションの実行環境を保持した状態で当該アプリケーション中の所定の計算部分に特化したサービスを提供するＣＰＵ資源プロバイダに、
前記クライアントからリクエストのあったジョブに対して、当該ジョブの予測計算時間を前記クライアントから前記ネットワークを介して受信する機能と、
前記クライアントから前記ネットワークを介して受信した前記予測計算時間に基づいてジョブの実行時間を修正する機能と、
修正された前記実行時間に基づいて前記ジョブに対するリソースの割り当てを行う機能と
を実現させるためのプログラム。
【請求項１６】
ネットワークに接続されたクライアントにて実行されるアプリケーションの実行環境を保持した状態で当該アプリケーション中の負荷の高い処理に特化したサービスを提供するＣＰＵ資源プロバイダに、
クライアントからリクエストのあったジョブに対して、当該クライアントから送信された予測計算時間に基づき、当該予測計算時間を修正して当該ジョブの実行時間を推定する機能と、
推定された前記実行時間を用いて、ＣＰＵにおける現在の空きノードに対して前記ジョブを割り当てた際のジョブ終了予測と、現在実行中である所定のジョブが終了した後の当該ＣＰＵにおける空きノードに対して当該ジョブを割り当てた際のジョブ終了予測とを行い、これらのジョブ終了予測に基づき、現在の空きノードに対して当該ジョブを割り当てて実行するかまたは現在実行中の所定のジョブが終了した後に空きノードに対して当該ジョブを割り当てて実行するかを選択して、当該ジョブに対するリソースの割り当てを行う機能と
を実現させるためのプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、計算負荷の高い処理サービスを提供するネットワークシステム等に係り、より詳しくは、所定のパフォーマンスを保証したサービスを提供するネットワークシステム等に関する。
【０００２】
【従来の技術】
近年、システム構築や運用コストの総費用を大幅に削減し、システム開発期間を短縮する等の目的で、インターネット経由で業務ソフトなどのアプリケーションを提供し期間単位で貸し出すサービスであるＡＳＰ(Application Service Provider)が急速に発展してきた。このＡＳＰを導入して業務のアウトソーシングを図ったユーザは、特別なアプリケーションのためにハードやソフトを購入する必要がなく、メンテナンスの費用も安価で済み、更に、専任要員などを少なくすることも可能である。
【０００３】
ここで、計算負荷の高いアプリケーションのＡＳＰとしては、例えば、有限要素法や境界要素法などによる、強度解析、熱解析、振動解析など、製品開発に係るエンジニアリングをコンピュータで支援するＣＡＥ(Computer Aided Engineering)がある。また、財務、会計等の金融工学を扱ったものも存在している。サーバの構成としては、例えば全ての処理をアプリケーションサーバが請け負ったものがある。こうした構成では、本格的に重い計算プロセスが動いた場合に、その他のインタラクティブなプロセスへの影響、並列計算における実現の困難性などが予想され、サービスレベルの維持、向上が困難となる。
【０００４】
最適化などの時間のかかるジョブを処理するＷｅｂベースのサービスでは、例えば、サブミットしたジョブを処理してメールで結果を返す、というシステムが存在している。しかしながら、あくまでも無料かつアカデミックな目的であり、パフォーマンスの保証がなされず、問題サイズも限られる。一方、大学等、公共機関の大型計算機センタでは、並列計算機をユーザに公開し、リソースマネージメントソフトウェアにより運用している。しかし、公平さと資源の効率的な利用を目的とし、その課金も合計ＣＰＵ時間をベースとしている。
【０００５】
また、計算資源のスケジューリング技術としては、バッチジョブのキューを管理し、ある程度の優先順位を調整しつつ、利用可能になったノードをジョブに割り当てていく手法が主流である。この背景として、現在の大規模計算機システムのほとんどを並列システムで構成している。しかし、アルゴリズムの裏をついて優先的にサービスを受ける、という抜け道がしばしば存在する。例えば、ノードに一時的に空きがあれば、短いジョブを前倒しで実行するbackfillという手法があるが、例えば１０分で終わるから、と割り込んで１時間粘る、といった実世界と同様な問題が起こり得る。
【０００６】
尚、特開平７−１４１３０５号公報には、並列計算機を不特定多数のユーザで同時に用いる際に、プロセッサの利用効率を上げる手法について開示されている。
【０００７】
【発明が解決しようとする課題】
ここで、大型計算機センタを利用する科学者や、コアコンピテンシーとして大規模サーバを導入するバイオ関連の大手企業等、既存のハイパフォーマンスコンピューティングのユーザ層に加え、潜在的なユーザとして、金融、製造業等においてモンテカルロシミュレーションや有限要素法といった負荷の高い処理を日常業務で使用するプロフェッショナル層がある。しかしながら、一般に大規模なシステムとなることから、導入および維持に際して、経済的、技術的負担が大きく、また、計算時間を短縮するため高性能にするほどアイドル時間も増えて効率が低下してしまう。また、ベンダーやアプリケーションによっては、プラットフォームが限定されるという不自由も存在してしまう。
【０００８】
かかる問題への解決法の一つがＡＳＰへの移行である。アプリケーションベンダーとしても、プラットフォームを固定して競争力の中心であるアルゴリズム部分に特化できるというメリットがあるが、前述のように、現状では計算待ち時間やレスポンスといったサービスの質を保証するレベルには達していない。また、スケジューリングアルゴリズムの裏をつかれる可能性もあり、ビジネスとして実現する上で重要である「公平さ」を確保することができない。
【０００９】
本発明は、以上のような技術的課題を解決するためになされたものであって、その目的とするところは、計算負荷の高いＷｅｂサービス等の処理サービスを提供するシステムにおいて、パフォーマンスを保証した公平なサービスを実現することにある。
また他の目的は、かかるシステムにおいて、正確な計算時間の予測に基づき資源の利用効率を高めると共に、インセンティブを通じてクライアントを正確かつ正直な予測をするように誘導することにある。
【００１０】
【課題を解決するための手段】
かかる目的を達成するために、本発明は、計算(並列計算)に適した構成のサーバ群を主体に、アプリケーション中の計算負荷の高いＷｅｂサービス等の処理サービスを提供するシステムにおいて、計算時間の予測をクライアントに求め、プロバイダでは、クライアント毎にプロファイルを管理して予測精度を解析し、サービスの管理に利用することで、全体のパフォーマンスへの影響に重点を置いた契約・課金体系を公平な形で実現している。言い換えると、既存の多くのバッチスケジューリングシステムで共通の問題となっている、入力データ(＝実行時間予測)の正確性を、クライアントプロファイルの利用により向上することを特徴としている。また、精度情報をスケジューリングに利用することで、計算機資源の効率的な利用を実現している。
【００１１】
即ち、本発明が適用されるネットワークシステムは、ネットワークに接続されアプリケーションを実行するＡＳＰ(アプリケーションサービスプロバイダ)等のクライアントと、このネットワークに接続されアプリケーションの実行環境を保持した状態でアプリケーション中の所定の計算部分(例えば、負荷の高い計算部分)に特化して処理サービスを提供するＣＰＵ資源プロバイダとを含み、このクライアントは、ＣＰＵ資源プロバイダに対するジョブのリクエストに際してジョブの予測計算時間に関する情報をネットワークを介してＣＰＵ資源プロバイダに送信し、ＣＰＵ資源プロバイダは、クライアントから送信された予測計算時間に基づき、この予測計算時間を修正してジョブの割り当てを行うことを特徴としている。
【００１２】
また、本発明が適用されるＣＰＵ資源プロバイダは、クライアントのプロファイルを格納するプロファイル格納手段と、クライアントからのジョブのリクエストに伴い、このジョブの予測計算時間を受信する予測計算時間受信手段と、プロファイル格納手段に格納されたプロファイルをもとに予測計算時間受信手段により受信された予測計算時間を修正する修正手段と、修正手段により修正された予測計算時間に基づいてリソーススケジューリングによるジョブの割り当てを行うジョブ割当手段とを備えることを特徴としている。
【００１３】
他の観点から把握すると、本発明が適用されるＣＰＵ資源プロバイダは、クライアントから送信された予測計算時間に基づき、この予測計算時間を修正して、クライアントからリクエストがあったジョブの実行時間を予測する実行時間予測手段と、現在割り当て可能なノード数を把握する第１のノード数把握手段と、予測された実行時間を用いて第１のノード数把握手段により把握された現在割り当て可能なノード数にてジョブを即座に実行したときの第１の終了予測時間を把握する第１終了予測時間把握手段と、現在実行中である所定の実行中ジョブの終了を待ってジョブを実行したときに割り当て可能なノード数を把握する第２のノード数把握手段と、予測された実行時間を用いて第２のノード数把握手段により把握されたノード数にてジョブを実行したときの第２の終了予測時間を把握する第２終了予測時間把握手段と、把握された第１の終了予測時間および第２の終了予測時間に基づき、即座に実行する際または所定の実行中のジョブの終了を待った後に所定のノードを確保してジョブを割り当てる割当手段とを備えたことを特徴としている。
【００１４】
ここで、この第１終了予測時間把握手段と第２終了予測時間把握手段は、例えば９０％の確率等、所定の確率でジョブが終了するまでの時間の尺度(例えばＬ値)を用いて第１の終了予測時間および第２の終了予測時間を把握し、この割当手段は、同じ（共通の）時間の尺度を比較して現在実行中のジョブの終了を待つか否かを判断することを特徴とすれば、共通の尺度を導入することで、クライアントごとの予測精度の違いをスケジューリングに組み込むことが可能となる点で好ましい。また、この実行時間予測手段は、クライアントからのリクエストの到着があったときに、クライアントの予測傾向として存在する偏向傾向を過去の履歴から把握して予測計算時間を修正することを特徴とすることができる。
【００１５】
また、本発明は、アプリケーションを実行すると共に、ネットワークに接続されるＣＰＵ資源プロバイダに対してアプリケーションの高度な計算を必要とする部分（所定の計算部分）に対するサービスを受けるクライアント装置から把握することができる。このクライアント装置は、ＣＰＵ資源プロバイダに対してジョブリクエストを送信するジョブリクエスト送信手段と、送信されるジョブリクエストにおけるジョブの問題規模から計算時間を予測する計算時間予測手段と、予測された予測計算時間をジョブリクエスト送信手段によるジョブリクエストの送信に伴ってＣＰＵ資源プロバイダに送信する予測計算時間送信手段と、ＣＰＵ資源プロバイダにてジョブの実行に要した実際の実行時間をＣＰＵ資源プロバイダから受信する受信手段とを備え、この計算時間予測手段は、受信手段により受信した実際の実行時間を、次のジョブにおける予測計算の精度を上げるために用いることを特徴している。ここで、このジョブリクエスト送信手段は、ジョブリクエストを送信するジョブの実行に必要なデータ、および実行ノード数、場合によってはアプリケーションのプログラムコード、並列実行可能な場合はその並列化性能を送信することを特徴とすることができる。
【００１６】
尚、本発明は、アプリケーションを実行するクライアントからのリクエストに基づいてアプリケーション中の計算負荷の高い部分に対して処理サービスを提供する処理サービスの提供方法として把握することができる。また、コンピュータであるクライアントとしての処理装置に、また、サービスを提供するコンピュータであるＣＰＵ資源プロバイダに、所定の機能を実現させるプログラムとして把握することができる。これらのプログラムは、ＣＤ−ＲＯＭ等の記憶媒体に格納されて提供される場合が考えられる。また、例えば、プログラム伝送装置によってネットワークを介してコンピュータに提供される形態が考えられる。このプログラム伝送装置としては、プログラムを格納するメモリと、ネットワークを介してプログラムを提供するプログラム伝送手段とを備えていれば足りる。
【００１７】
【発明の実施の形態】
以下、添付図面に基づき、本発明の実施の形態について詳細に説明する。
図１は、本実施の形態が適用されるネットワークシステムの全体構成を説明するための図である。ここでは、ネットワークであるインターネット９を介して、アプリケーションのエンドユーザであるユーザ１０とクライアントであるアプリケーションサービスプロバイダ(ＡＳＰ)２０とが接続されている。また、インターネット９を介して、アプリケーションサービスプロバイダ２０と計算集中ＷｅｂサーバであるＣＰＵ資源プロバイダ３０とが接続されている。
【００１８】
ユーザ１０は一般のアプリケーションの利用者である。また、ＣＰＵ資源プロバイダ３０は、計算負荷の高い部分に特化した処理サービスの提供者であり、アプリケーションサービスプロバイダ(ＡＳＰ)２０は、この処理サービスの利用者であるクライアントと定義できる。
【００１９】
本実施の形態では、ＣＰＵ資源プロバイダ３０は、クライアントであるアプリケーションサービスプロバイダ(ＡＳＰ)２０に対してリクエスト時に予測計算時間の申告を義務付けている。また、クライアントのプロファイルを管理し、申告時間、実際の待ち時間と実行時間の履歴等を保持している。更に、このプロファイルをもとに、
(ａ)計算時間予測の正確性、申告の傾向(バイアス)を解析し、リソーススケジューリングに利用する。
(ｂ)スケジューリング効率の向上に役立つ行為(クライアントによる正確な予測、事前予約)に対して、例えば、予測が正確であれば値段を下げる等のインセンティブを設定する。
(ｃ)割り当て優先順位、並列度を調整することで契約時間のサービスレベルを維持する。
ことにより、正確な予測を実現するとともに、正確かつ正直に予測を行うようにクライアントを誘導することで、更なる効率化を図っている。
【００２０】
まず、契約時において、ユーザ１０とアプリケーションサービスプロバイダ２０との間で所定のアプリケーション使用契約がなされる。また、アプリケーションサービスプロバイダ２０とＣＰＵ資源プロバイダ３０との間では、計算機資源使用契約がなされる。そして、アプリケーションサービスプロバイダ２０からＣＰＵ資源プロバイダ３０に対して、使用プログラムと並列化特性登録がなされる。
【００２１】
一方、運用時においては、ユーザ１０とアプリケーションサービスプロバイダ２０との間で使用契約がなされたアプリケーションが使用される。また、アプリケーションサービスプロバイダ２０からＣＰＵ資源プロバイダ３０に対しては、予測時間を含む計算リクエストが提示され、ＣＰＵ資源プロバイダ３０からアプリケーションサービスプロバイダ２０に対しては、計算結果と予測精度情報が提供される。
【００２２】
尚、アプリケーションサービスプロバイダ２０を介さず、ユーザ１０が直接、ＣＰＵ資源プロバイダ３０を利用する形態も考えられる。このときは、ユーザ１０であるクライアントマシンにインストールされたアプリケーションが、計算機負荷の高い解析部分のみインターネット９を通してＣＰＵ資源プロバイダ３０にリクエストするように設定される。かかる場合に、クライアントであるユーザ１０が計算時間を予測することは一般に困難であることから、何段階かで表現された問題規模の指標で代替する。履歴が蓄積されるとともに、この指標から計算時間への関数が指定できるため、計算時間の予測をＣＰＵ資源プロバイダ３０側で代行することになる。但し、計算時間の予測機能を含むプログラムをユーザ１０に提供し、クライアントであるユーザ１０が計算時間を予測するように構成することも可能である。
【００２３】
図２は、ＣＰＵ資源プロバイダ３０の構成を示した図である。本実施の形態におけるＣＰＵ資源プロバイダ３０は、計算集中Ｗｅｂサーバとして、複数の計算サーバ３６からなるサーバ群を備え、バス３５によってこれらの計算サーバ３６と接続されている。また、バス３５に接続されるフロントエンドプロセッサ上に、複数の計算サーバ３６のジョブ管理を行うＯＳであるスケジューラ３１を備えている。また、クライアントであるアプリケーションサービスプロバイダ２０のプロファイル等を格納する記憶装置３２、アプリケーションサービスプロバイダ２０との通信を行う通信部３３、課金計算等を行うアカウントマネージャ３４を備えている。
【００２４】
図１２は、アプリケーションサービスプロバイダ２０の構成を示した図であり、ＣＰＵ資源プロバイダ３０との関係に用いられる部分を示している。ここでは、ユーザ１０との間で使用されるアプリケーションに関するデータや実行ノード数、並列化性能、プログラムコード等が格納される格納部２５を備え、ＣＰＵ資源プロバイダ３０に対してジョブをリクエストする際に、把握される問題規模から計算時間を推定する計算時間予測部２１を備えている。また、格納部２５に格納される、実行に必要なデータ、実行ノード数をＣＰＵ資源プロバイダ３０に送付するジョブリクエスト送信部２２、計算時間予測部２１により予測された予測計算時間をＣＰＵ資源プロバイダ３０に送付する予測計算時間送信部２３を有している。更に、ＣＰＵ資源プロバイダ３０から、ジョブの実行による計算結果と共に、ジョブに要した実際の実行時間を受信する結果受信部２４を備えている。この結果受信部２４により受信された実際の実行時間は、計算時間予測部２１に入力され、次のジョブにおける予測計算の精度を上げるために用いられる。
【００２５】
次に、ＣＰＵ資源プロバイダ３０のスケジューラ３１にてなされるサービスレベルの設定方法および予測時間情報の管理について説明する。本実施の形態では、実現例として、クライアントとのサービスレベルの設定方法、予測誤差情報の管理、そしてこれらに基づくスケジューリングアルゴリズムを示している。リソース以上のリクエストが殺到する場合も有り得るために、常に性能を保証することは一般的に不可能であるが、“みなしノード数”という指標に対して、期間平均としての保証を考え、実績ベースで目標値を動的に変更することで対応している。また、Ｌ値(高い確率(例えば９０％)でジョブが終了するまでの時間)という共通の尺度を導入することで、クライアントごとの予測精度の違いをスケジューリングに組み込んでいる。
【００２６】
図３は、アプリケーションにおける並列化性能の例を示した図であり、これらの並列化性能は、アプリケーションサービスプロバイダ２０のクライアントからＣＰＵ資源プロバイダ３０に対して事前情報として提供されている。ここでは、ノード数(横軸)に対する性能(縦軸)が示されており、ポートフォリオ最適化とモンテカルロシミュレーションが挙げられている。
【００２７】
まず、準備について説明する。クライアントから図３に例示した並列化性能が事前情報として適用されるが、例えばこの関数を
【式１】
0003959516.tif 000002
とする。ここで、１ノードで１０時間かかるジョブを、しばらくの割り当て待ちの後、複数のノードで並列に実行され、サブミットされてから３時間で終了したものとする。このとき、
【式２】
0003959516.tif 000003
即ち、サブミットと同時に割り当てたという前提で相当するノード数を「みなしノード数」と呼んでいる。
【００２８】
次に、アプリケーションサービスプロバイダ２０の一つであるクライアントｃとのサービスレベルの設定は、ある契約期間において、
【式３】
0003959516.tif 000004
という形態とする。「平均みなしノード数」はサービスの質に相当し、「合計ＣＰＵ時間」はサービスの量に相当する。これらの目標値からの変位は、料金に反映される。
【００２９】
次に、契約期間(例えば当月)内にクライアントｃからリクエストされ実行されたジョブ毎のみなしノード数、ＣＰＵ時間を、それぞれ
【式４】
0003959516.tif 000005
とし、何らかの方法で見積もった今後のＣＰＵ消費を
【式５】
0003959516.tif 000006
とする。このとき、
【式６】
0003959516.tif 000007
を、クライアントｃのための「目標みなしノード数」とし、この値はジョブが終了する度に更新される。
【００３０】
ここで、誤差を加味した予測実行時間は、確率分布Ｘとみなせる。パラメータＰに対して、
【式７】
0003959516.tif 000008
を、それぞれＸのＥ値、ＸのＬ値と呼ぶ。例えば、Ｐ＝０.１のとき、Ｘは９０％の確率でＬ値よりも早く終了し、且つ、９０％の確率でＥ値よりも長くかかる。
【００３１】
更に、独立な正規分布に従うと仮定すれば、複数の分布の和(即ち、複数のジョブを順に実行した際にかかる時間の合計)を扱う際は、公式
【式８】
0003959516.tif 000009
を用いることができ、以降の手続中での計算を簡略化することができる。
【００３２】
次に、図２に示すような計算サーバ３６の群のように、大規模で能力の均一な並列計算機環境を想定し、各ジョブに割り当てるノード数は可変として実行時間を予測する。但し、各クライアントは、１ノードでシリアルに実行した場合の計算時間を予測する。ジョブを固定のノード数ｎfixedで実行する必要がある場合には、
【式９】
0003959516.tif 000010
とすることで対処可能である。
【００３３】
次に、スケジューラ３１にてなされるスケジューリングの手続きについて説明する。図４は、スケジューリングの手続き処理の流れを示したフローチャートである。まず、スケジューラ３１は、所定のイベントが発生するまで待機する(ステップ１０１)。リクエストが到着した場合には(ステップ１０２)、リクエスト到着時処理を実行し(ステップ１０３)、ステップ１０７のキューの再評価処理に移行する。リクエスト到着のイベントが発生していない場合に、ジョブが終了したか否かを判断する(ステップ１０４)。ジョブ終了のイベントが発生した場合には、ジョブ終了時処理を実行し(ステップ１０５)、ステップ１０７のキューの再評価処理に移行する。ステップ１０４のジョブ終了のイベントが発生していない場合に、一定時間が経過したか否かを判断する(ステップ１０６)。一定時間が経過していない場合には、ステップ１０１のイベント発生まで待機する。一定時間が経過した場合には、キューの再評価処理を実行し(ステップ１０７)、ステップ１０８であるジョブ割り当て処理に移行する。このジョブ割り当て処理を実行すると(ステップ１０８)、ステップ１０１に戻り、次のイベント発生まで待機する。
【００３４】
ここで、リクエスト到着時の処理について説明する。
図５は、図４のステップ１０３におけるリクエスト到着時処理を示すフローチャートである。スケジューラ３１は、計算リクエストの到着を受けて(ステップ２０１)、リクエストを出したクライアント(アプリケーションサービスプロバイダ２０)の予測傾向に基づいて、実行時間を予測(推定)する(ステップ２０２)。この予測(推定)した実行時間をキューへ追加する(ステップ２０３)。このリクエスト到着時において、リクエストされたジョブｉがクライアントｃ(ｉ)から到着した時刻をＴiarrivalとする。クライアントから申告された予測実行時間ｔiを過去の履歴の誤差解析により修正し、Ｅ[Ｘi]＝μiとした場合の予測実行時間の分布Ｘiが求められる。
【００３５】
図６は、あるクライアントの予測傾向について示した図である。ここでは、横軸を予測時間、縦軸を実際の実行時間としており、この誤差を解析し、予測時間の分布を求めてスケジューリングに利用する。簡単のため、ここでは並列性は省いている。図６に示すように、クライアントであるアプリケーションサービスプロバイダ２０から申告される予測時間に対し、図の太線矢印で示されるごとく、実行時間は所定のズレを生じている。そのために、本実施の形態では、リクエストの到着時に、クライアントの予測傾向として存在するバイアス(偏向傾向)を把握して修正する点に特徴がある。
【００３６】
図６の例に示す予測傾向を持つクライアントは、過去の履歴から、実際よりも少なめに予測する傾向が見て取れ、また、誤差のバラツキ具合も定量化可能である。例えば、申告された計算時間８０分から、期待値９０分、標準偏差３０分と推定されたとき、
９０＋３０×０.４＝１０２(分)
を予測実行時間としてスケジューリングする、といった運用により、誤差によるリスクを軽減することができる。誤差情報を更に精緻に利用することも可能である。
【００３７】
また、解析系のアプリケーションでは、パラメータを少しずつ変えて複数回実行することが頻繁にある。全て３０分ずつとして１０件の連続したリクエストがあり、最初の２つのジョブが４０分かかった場合、残りの８件も４０分程度かかる可能性が高い。こうした傾向は、申告値のバイアスの時系列解析(この場合、＋１０,＋１０→？,？,…)を行うことで、予測を修正することが可能となる。
【００３８】
次に、ジョブ終了時の処理について説明する。
図７は、図４のステップ１０５におけるジョブ終了時処理を示したフローチャートである。まず、スケジューラ３１では、ジョブ終了のイベントがあった後に(ステップ３０１)、ジョブｉの実際の実行時間に基づき、クライアントｃ(ｉ)の履歴、誤差情報等の予測精度情報が更新される(ステップ３０２)。また、クライアントｃ(ｉ)が他のジョブをリクエストしている場合には、そのジョブの予測情報も更新される(ステップ３０３)。また、クライアントｃ(ｉ)の目標みなしノード数
【式１０】
0003959516.tif 000011
を更新し(ステップ３０４)、これに基づき、キューの再評価が行われる。
【００３９】
次に、キューの管理について説明する。
図８は、図４のステップ１０７におけるキューの再評価処理を示したフローチャートである。まず、スケジューラ３１では、キュー内における各ジョブのｎirequiredが更新される(ステップ４０１)。計算機に割り当てられていないジョブは、現在時刻をＴcurrentとして、
【式１１】
0003959516.tif 000012
の大きい順にソートされ、ジョブが並び替えられる(ステップ４０２)。既存のバッチシステムでは到着順とすることが多いが、ここでは、即座に割り当てたとして“目標みなしノード数”を達成するのに必要なノード数、ｎirequiredが用いられる。この値は、時刻と共に変化することから、定期的に更新する必要がある。この再評価処理によって、ソート後におけるキューのｋ番目のジョブＩＤをｑ(ｋ)として、次のジョブの割り当て処理が実行される。
【００４０】
次に、ジョブの割り当てについて説明する。
図９は、図４のステップ１０８におけるジョブ割り当て処理を示したフローチャートである。このジョブ割り当て処理では、現在割り当て可能なノード数をＮavail、現在実行中のジョブの中でｋ番目にＬ値が小さいものが占有しているノード数をＮkavail、そのジョブＩＤをａ(ｋ)とする。まず、スケジューラ３１は、現在割り当て可能なノード数、即ち、空きノード数Ｎavailをチェックする(ステップ５０１)。次に、空きノードがあるか否かを判断し(ステップ５０２)、空きノードがない場合、即ち、Ｎavail＝０のときは、ジョブ割り当て処理は終了し、割当中のジョブが終了するまで待つ。
【００４１】
空きノードがあった場合に、先頭ジョブの必要分があるか否かが判断される(ステップ５０３)。先頭ジョブの必要分がある場合、即ち、
【式１２】
0003959516.tif 000013
のとき、ジョブｑ(１)を
【式１３】
0003959516.tif 000014
に割り当て、
【式１４】
0003959516.tif 000015
として必要数を割り当て(ステップ５０４)、ステップ５０１へ戻る。
【００４２】
ここで、ジョブｑ(１)を即座にＮavailノードで実行したときのＬ値をＬ0とする。また、ジョブａ(１)が終了するまで待ち、Ｎavail＋Ｎ1availノードで実行したときのＬ値をＬ1とする。更に、ジョブａ(ｋ)が終了するまで待ち、
【式１５】
0003959516.tif 000016
で実行したときのＬ値をＬkとする。
【００４３】
ステップ５０３で、空きノードが先頭ジョブの必要分なく、足りない場合、即ち、
【式１６】
0003959516.tif 000017
の場合に、Ｌ0＞Ｌkとなるｋが存在するか否かが判断される(ステップ５０５)。
【００４４】
Ｌ0＞Ｌkとなるｋが存在する場合には、ジョブａ(ｋ)の終了を待ってジョブｑ(ｋ)を割り当てることが得策となる。そこで、ジョブｋより早く終わる確率の高いジョブが存在するか否かが調べられ(ステップ５０６)、存在すれば、そのジョブを現状の空きノード数で割り当て(ステップ５０７)、処理が終了する。即ち、キューの先頭から調べていき、Ｎavailノードで実行したときのＬ値がジョブａ(ｋ)のＬ値よりも小さいものがあれば、Ｎavailノードで割り当てて処理が終了する。ステップ５０６で該当するジョブが存在しなければ、割り当て済みのジョブの何れかが終了するまで待つ。
【００４５】
ステップ５０５で、全てのｋに対してＬ0≦Ｌkのときには、先頭ジョブｑ(１)を現状の空きノード数(Ｎavailノード)に割り当てて(ステップ５０８)、処理が終了する。
【００４６】
図１０(ａ),(ｂ)は、上述したジョブの割り当て処理の一例を示した図である。図１０(ａ)は割り当て処理を施す前の現状を示し、図１０(ｂ)は割り当て処理の例を示している。図１０(ａ)に示すように、現状では４ノードが使用可能である。一方、１番目のキューのジョブｑ(１)および２番目のキューのジョブｑ(２)があり、１番目のジョブｑ(１)を割り当てる方法を考える。即ち、ここでは、キューの先頭にあるジョブｑ(１)は、目標みなしノード数が８で、約５０分かかる(Ｌ値は６０)と見込まれているが、現在の空きは４ノードしか存在していない。ここで、図１０(ａ)では、現在実行中である複数のジョブの中から、ジョブが終わりそうなもの(Ｌ値の小さいもの)から順に考察する。現在実行中のジョブの中で１番目にＬ値が小さいジョブａ(１)と、２番目にＬ値が小さいジョブａ(２)の２つのジョブが示されており、それ以外のジョブは省略されている。このジョブａ(１)が占有しているノード数であるＮ1availは２ノードであり、ジョブａ(２)が占有しているノード数であるＮ2availは６ノードである。
【００４７】
図１０(ａ)では、ジョブａ(１)およびａ(２)のそれぞれにおいて、実線で示す平均値と、Ｌ値とが示されている。ここでは、１番目のキューのジョブｑ(１)を実行するに際して、今すぐに空きノードである４ノードを割り当てて実行するのか、ジョブａ(１)を終了させて空きノードとして６(４＋２)ノードを確保して実行するのか、ジョブａ(２)が終了した後に確保される１２(４＋２＋６)ノードを用いて実行するのか、の判断がなされる。
【００４８】
ここで、１番目のキューのジョブｑ(１)を即座に４ノードで実行したときのＬ値は１２０、ジョブａ(１)が終了した後に６ノードで実行したときのＬ値は１１０、ジョブａ(２)が終了した後に１２ノードで実行したときのＬ値は７０であるとする。この場合に、ジョブａ(２)の終了後に実行するＬ値が最小となることから、この段階までジョブｑ(１)を待機させる。このとき、即座に４ノードで実行したときのＬ値が、ジョブａ(２)のＬ値３０よりも小さくなるジョブが存在する場合には、前倒しの実行が行われるが、ここでは、そのようなジョブが存在せず、前倒しの実行がなされていないものとする。
【００４９】
図１０(ｂ)に示すように、実際にジョブａ(２)が終了して１２ノードが可能になった時点で、キューの先頭ジョブｑ(１)は以前のままであるが、目標みなしノード数は、待機のために増加して、１６になっているものとする。このとき、この例では、これ以上待機してもＬ値の改善が見込めないものとして、図１０(ｂ)に示すように、１２ノードでこのジョブｑ(１)が割り当てられる。このように、本実施の形態によれば、正確な計算時間の予測に基づき、資源の利用効率を高めることが可能となる。
【００５０】
次に、本実施の形態が適用されたシステムの実現例を説明する。ここでは、金融関連アプリケーションのベンダーＰがＡＳＰサービスに移行し、図１に示すアプリケーションサービスプロバイダ２０になった場合を説明する。最新の市場価格などの情報提供、オンライン取引といったトランザクション処理には自前のサーバ群を利用している。しかし、デリバティブ価格付けのためのモンテカルロシミュレーション、ポートフォリオ最適化といった、数分から数時間にわたって複数のＣＰＵを占有する必要がある機能については、他のインタラクティブなサービスのレスポンスを下げる可能性がある。また、大規模並列化で実行速度を高めることが顧客満足度の向上につながることとなる。そのために、ＣＰＵ資源プロバイダ３０を利用することにする。ベンダーＰ(アプリケーションサービスプロバイダ２０)は、アプリケーション実行に必要なプログラムコードをＣＰＵ資源プロバイダ３０のシステムに登録し、並列実行可能な場合は、図３に示すような並列化性能もＣＰＵ資源プロバイダ３０に知らせておく。
【００５１】
ベンダーＰ(アプリケーションサービスプロバイダ２０)の提供するアプリケーションサービスのユーザ１０がモンテカルロ法の実行を指示すると、ベンダーＰ(アプリケーションサービスプロバイダ２０)は、実行に必要なデータ、実行ノード数、及び問題規模から推定した実行時間をＣＰＵ資源プロバイダ３０に送付する。ＣＰＵ資源プロバイダ３０は、このリクエストをキューに加え、リソースが空き次第、実行して、その結果をベンダーＰ(アプリケーションサービスプロバイダ２０)に送付する。
【００５２】
このとき、ＣＰＵ資源プロバイダ３０は、ベンダーＰの他にも、例えば遺伝子解析アプリケーションベンダーＱ、流体解析ベンダーＲなど、複数のアプリケーションサービスプロバイダ２０をクライアントとし、それぞれのアプリケーションの実行環境を保持して計算サービスを提供する。
【００５３】
この例のＣＰＵ資源プロバイダ３０のように、アプリケーション中の計算負荷の高い部分のみを担当するＷｅｂサービスをビジネスとして提供する際、合計ＣＰＵ時間だけでなく、各クライアントのリクエストから計算終了までのターンアラウンドを加味したサービスレベルを保証することが好ましい。本実施の形態では、例えば、１時間待った後に４ノードで１時間実行した場合、２ノード占有に相当する場合に、この尺度をもとに、延べ１ノード相当の計算時間、平均４ノード、９０％の確率で２ノード相当以上のパフォーマンス保証、といったサービスレベルを設定している。
【００５４】
このようなサービスレベルの向上には、効率的なリソーススケジューリングが不可欠となるが、それには正確な実行時間予測が必要となる。
図１１は、ノード数２でのジョブ割り当て例を示している。この２ノードの例では、ノード１のジョブ(Job)Ａが終了した段階で、キュー(Queue)での優先順位の最も高いジョブＣは２ノード必要とするため、ノード２が空くまで実行できない。そこで、従来では、破線で示すように、先にジョブＤをノード１で実行することで、全体の効率を改善していた。しかしながら、これが成り立つのはジョブＤが確実に予定時間内に終わる場合であり、ジョブＢが終了してもジョブＤが延々と続く場合には、ジョブＣのクライアントのサービスレベルが下がるとともに、ノード２がアイドル状態となり、システムの効率も低下してしまう。また、前述のように、アルゴリズムの裏を取ろうとする意図的な誤申告は、サービス全体の公平さを損ない、信頼を失い得る。
【００５５】
ここで、一般のリソーススケジューリングでは、資源利用の効率において、
0003959516.tif 000018
という関係が成り立つ。この、(ａ)予測計算時間に基づくオンラインアルゴリズムは、現在までの情報のみを元にして処理するアルゴリズムである。また、(ｃ)正確な計算時間に基づくオフラインアルゴリズム(最適解)は、将来にわたる全ての情報を元に処理するアルゴリズムである。つまり、具体的なアルゴリズムの実装方法にかかわらず、実行時間予測の精度を上げ、より将来の情報を持つことが資源利用効率の改善につながることが理解できる。
【００５６】
そのために、本実施の形態におけるＣＰＵ資源プロバイダ３０は、クライアントであるアプリケーションサービスプロバイダ２０に対して、リクエスト時に予測計算時間(または問題規模の指標)の申告(送信)を義務付けるように構成し、クライアントのプロファイルを管理し、申告時間、実際の待ち時間と実行時間等の履歴を保持している。また、このプロファイルをもとに、計算時間予測の正確性、申告の傾向(バイアス)を解析し、リソーススケジューリングに利用し、スケジューリング効率の向上に役立つ行為(クライアントによる正確な予測、事前予約)に対してインセンティブを設定している。更に、過去の履歴に基づき、割当優先順位、並列度を調整することで、契約期間のサービスレベルを維持している。尚、いかにスケジューリング性能が向上しても、負荷が集中した際には、全てのクライアントのサービスレベルを維持することはできない。そこで、処理が遅れた場合には、例えば、次回以降に優先的に早く割り当てる調整や、多くのノードを割り当てて処理を高速化する調整等によって、サービスレベルと顧客満足度の維持を図っている。
【００５７】
これらの構成よって、本実施の形態では、パフォーマンスを保証した公平なサービスを実現することが可能となり、正確な計算時間の予測に基づく資源の利用効率を高めると共に、インセンティブを通じてクライアントを正確かつ正直な予測をするように誘導することが可能となる。また、ジョブがインタラクティブでない分、ネットワークへの要求が低いことから、地域依存性が少なく、グローバルな顧客を対象にした時差による負荷分散が可能となり、スケールメリットを増すことができる。更には、大型計算機の新たなユーザ層を獲得できることから、市場を広げることができる。
【００５８】
また更に、Ｗｅｂサーバは多くのトランザクションを処理するための並列化がパフォーマンス向上の主眼であり、並列計算環境、高速スイッチなどを要求されるＣＰＵサーバとはハードウェア、ソフトウェアとも構成が大きく異なる。プロバイダ側では、これらを分離することで、それぞれに適した機器構成に特化できる。また、アプリケーションサービスプロバイダ２０にとっても、サービスビジネス化による一般的な効果として、安定したキャッシュフローを確保することが可能となる。更には、バージョンアップ等のユーザサポートの負荷を削減することも可能である。
【００５９】
【発明の効果】
このように、本発明によれば、計算負荷の高い処理サービスを提供するシステムにおいて、パフォーマンスを保証した公平なサービスを実現することが可能となる。
【図面の簡単な説明】
【図１】  本実施の形態が適用されるネットワークシステムの全体構成を説明するための図である。
【図２】  ＣＰＵ資源プロバイダの構成を示した図である。
【図３】  アプリケーションにおける並列化性能の例を示した図である。
【図４】  スケジューリングの手続き処理の流れを示したフローチャートである。
【図５】  図４のステップ１０３におけるリクエスト到着時処理を示すフローチャートである。
【図６】  あるクライアントの予測傾向について示した図である。
【図７】  図４のステップ１０５におけるジョブ終了時処理を示したフローチャートである。
【図８】  図４のステップ１０７におけるキューの再評価処理を示したフローチャートである。
【図９】  図４のステップ１０８におけるジョブ割り当て処理を示したフローチャートである。
【図１０】  (ａ),(ｂ)は、ジョブの割り当て処理の一例を示した図である。
【図１１】  ノード数２でのジョブ割り当て例を示した図である。
【図１２】  アプリケーションサービスプロバイダの構成を示した図である。
【符号の説明】
９…インターネット、１０…ユーザ、２０…アプリケーションサービスプロバイダ(ＡＳＰ)、２１…計算時間予測部、２２…ジョブリクエスト送信部、２３…予測計算時間送信部、２４…結果受信部、２５…格納部、３０…ＣＰＵ資源プロバイダ、３１…スケジューラ、３２…記憶装置、３３…通信部、３４…アカウントマネージャ、３５…バス、３６…計算サーバ
【図１】
0003959516.tif 000019
【図２】
0003959516.tif 000020
【図３】
0003959516.tif 000021
【図４】
0003959516.tif 000022
【図５】
0003959516.tif 000023
【図６】
0003959516.tif 000024
【図７】
0003959516.tif 000025
【図８】
0003959516.tif 000026
【図９】
0003959516.tif 000027
【図１０】
0003959516.tif 000028
【図１１】
0003959516.tif 000029
【図１２】
0003959516.tif 000030