(57)【要約】【解決手段】  コンピュータにより実行される、分散コンピューティング資源の組（102 - 114）にタスクを割り当てる方法が提供される。この方法は、分散コンピューティング資源の組について記述する資源データ（200）を取得すること（604）と、実行されるコンピューティング・タスクについて記述するタスク・データ（400）を取得すること（602）と、を含んでいる。本方法は、次に、タスクの取得された記述に基づいてタスクを実行するための分散コンピューティング資源の少なくとも１つを選択する（606）。【選択図】図６
2009528649.tif 000002
【特許請求の範囲】
【請求項１】
分散コンピューティング資源の組について記述する資源データを取得し、
実行されるコンピューティング・タスクについて記述するタスク・データを取得し、
前記タスクの前記取得された記述に基づいて前記タスクを実行するための前記分散コンピューティング資源の少なくとも１つを選択する、
ことを備える、コンピュータにより実行される、分散コンピューティング資源の組にタスクを割り当てる方法。
【請求項２】
前記資源データおよび（または）前記タスク・データが、前記分散コンピューティング資源が相互接続されるネットワークのオペレーティング・システムによって読み取り可能なフォーマット、例えばＸＭＬの形態である、請求項１の方法。
【請求項３】
前記資源データが、ユーザによって設定された少なくとも１つの特性について前記分散コンピューティング資源の特性について記述している、請求項１または２に記載の方法。
【請求項４】
前記タスク・データが、ユーザによって設定された少なくとも１つの計算要件について前記タスクの特性について記述している、先行する請求項のいずれか１項の方法。
【請求項５】
前記分散コンピューティング資源の少なくとも１つを選択することは、前記分散コンピューティング資源の性能についての既存の知識を埋め合わせるヒューリスティック法を備えた動的計画法および整数計画法技術に基づいたアルゴリズムを用いる、先行する請求項のいずれか１項の方法。
【請求項６】
前記資源データが、
前記ネットワーク内の第１資源を選択する工程と、
前記第１資源に応答指令信号を発してその特性を割り出す工程と、
前記特性について記述するデータを格納する工程と、
前記第１資源と通信している別の少なくとも１つの資源を選択するとともに前記別の少なくとも１つの資源について前記割り出す工程および格納する工程を繰り返す工程と、
を用いて取得される、先行する請求項のいずれか１項の方法。
【請求項７】
前記資源について格納されている前記特性が、前記ユーザによって設定された前記少なくとも１つの特性と一致する、請求項３を引用する場合の請求項６の方法。
【請求項８】
前記タスク・データが、前記タスクについて記述するソースまたは実行可能コードを分析して前記タスクの計算要件の統計（あるいは推定された統計）を取得することによって取得される、先行する請求項のいずれか１項の方法。
【請求項９】
統計／推定された統計を得るための計算要件が、前記ユーザによって設定された前記少なくとも１つの計算要件に一致する、請求項４を引用する場合の請求項８の方法。
【請求項１０】
プログラムがコンピュータ上で実行される際に先行する請求項のいずれか１項の方法ステップを実行するためのプログラム・コード手段を備えるコンピュータ・プログラム。
【請求項１１】
プログラムがコンピュータ上で実行される際に先行する請求項１乃至９のいずれか１項の方法ステップを実行するための、コンピュータ読み取り可能媒体に格納されているプログラム・コード手段を備えるコンピュータ・プログラム製品。
【請求項１２】
実質的に、添付の図面を参照して明細書において記載されている方法。
【請求項１３】
分散コンピューティング資源の組について記述する資源データを取得するように構成されている装置と、
実行されるコンピューティング・タスクについて記述するタスク・データを取得するように構成されている装置と、
前記タスクの取得された記述に基づいて前記タスクを実行するための前記分散コンピューティング資源の少なくとも１つを選択するように構成されている装置と、
を備える、分散コンピューティング資源の組にタスクを割り当てるための装置。
【請求項１４】
実質的に、添付の図面を参照して明細書において記載されている装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分散コンピューティングに関する。 
【背景技術】
【０００２】
現在、コンピュータ・アプリケーションが分散コンピューティングネットワーク／資源に実行依頼される際、ＴＣＰ／ＩＰおよびＭＰＩのような通信の標準的なモードが用いられる。ＴＣＰ／ＩＰは、ネットワークにおいてレイテンシの計画や管理を一切行なわず、また、ＭＰＩは並列のプロセス間の通信を同期させるためだけに用いられる。
【０００３】
並列、あるいは分散されたコンピュータ・ジョブがネットワークに実行依頼される場合、ジョブの最適な区分（分割）を推測的に評価したり、別のアプリケーション、またはユーザ、またはプロセスによる資源に対する競合の程度を推定したりすること以外に通信を管理する既存の方法は存在しない。付加された、またはトポロジーまたはネットワーク性能の変化に適合している、新たな資源を利用する方法もない。
【発明の開示】
【０００４】
本発明の第１の態様によれば、分散コンピューティング資源の組について記述する資源データを取得し、実行されるコンピューティング・タスクについて記述するタスク・データを取得し、タスクの取得された記述に基づいてこのタスクを実行するための分散コンピューティング資源の少なくとも１つを選択する、ことを備える、コンピュータにより実行される、分散コンピューティング資源の組にタスクを割り当てる方法が提供される。
【０００５】
本発明の第２の態様によれば、分散コンピューティング資源の組について記述する資源データを取得するように構成されている装置と、実行されるコンピューティング・タスクについて記述するタスク・データを取得するように構成されている装置と、タスクの取得された記述に基づいてこのタスクを実行するための分散コンピューティング資源の少なくとも１つを選択するように構成されている装置と、を備える、分散コンピューティング資源の組にタスクを割り当てるための装置が提供される。
【０００６】
本発明のさらなる態様によれば、ネットワーク内の分散コンピューティング資源の組について記述する資源情報を生成するための、コンピュータにより実行される方法であって、ネットワーク内の第１資源を選択する工程と、第１資源に応答指令信号を発してその特性を割り出す工程と、特性について記述するデータを格納する工程と、第１資源と通信している別の少なくとも１つの資源を選択するとともにこの別の少なくとも１つの資源について先の割り出す工程および格納する工程を繰り返す工程と、を備える方法が提供される。本発明の別の態様によれば、この方法を行なうように構成されている装置が提供される。
【０００７】
本発明のさらに別の態様によれば、分散コンピューティング資源を用いて行なわれるコンピューティング・タスクについて記述するタスク情報を生成する、コンピュータにより実行される方法であって、タスクについて記述するソースまたは実行可能コードを分析してタスクの計算要件の統計（あるいは推定された統計）を取得することによって取得されることを具備する方法が提供される。本発明の別の態様によれば、この方法を行なうように構成されている装置が提供される。
【０００８】
本発明のさらなる態様によれば、プログラム・コードがロードされるとコンピュータに本明細書に実質的に記載されている方法を実行させるコンピュータ・プログラム・コード手段を有するコンピュータ読み取り可能媒体を備えるコンピュータ・プログラム製品が提供される。
【０００９】
本発明は、上に記載されている一方、上のまたは下の記載の特徴の発明性のある組合せのあらゆるものに及ぶ。本発明の例示的な実施形態は添付の図面を参照して本明細書において詳細に記載されているが、本発明がそれらの実施例そのものに制限されていないことが理解されるべきである。そのため、多くの改良体および変形体は、当業者にとって明白であろう。また、個別にまたは実施形態の一部として記載されている特定の特徴は、他の特徴および実施形態がこの具体的な特徴に言及していなくとも、これらの別の個別に記載されている特徴または別の実施形態の一部と組み合わせられることが可能である。
【００１０】
本発明は様々なやり方でまたあくまで例として実行され得、本発明の実施形態が次に記載される。
【発明を実施するための最良の形態】
【００１１】
図１は、分散コンピューティング・タスクを実行するのに利用可能な資源の組の図である。資源は、ネットワーク上で相互に接続された様々なハードウェア装置を含んでいる。図において示されている基本的な配置があくまで例示であり、また多くの変形体が可能であることが理解される。
【００１２】
図１に示されている例では、第１コンピューティング装置１０２は通信リンク１０４上で第２コンピューティング装置１０６に接続されている。コンピューティング装置が幾つかの形態をとり得ることが理解されるであろう。例えば、コンピューティング装置は、ソフトウェアを実行して分散されたタスクを実行するのに適したものにされる汎用デスクトップ・パソコンであり、またはより特化されたハードウェアであり得る。同様に、通信リンクは幾つかの形態、例としてローカルエリア・ネットワークまたはイーサネット（登録商標）・リンクを取り得、有線または無線の形態であり得る。第２コンピューティング装置は、リンク１０８上で記憶装置１１０（例えば外部ハード・ドライブまたはＲＡＩＤ（redundant array of independent disks）記憶装置構成に接続されている。記憶装置１１０は、リンク１１２を介して第３コンピューティング装置１１４に接続されている。
【００１３】
当業者に知られるように、ネットワーク内の様々なノード（例えばコンピューティング装置／記憶装置）およびそれらの間のリンクは、多くの相違する個々の特徴を有し得る。従来は、多くの場合、ユーザが、どの要素が分散コンピューティング・タスクを行なうために使用されるかを選択する前に、これらの特徴を知得したり、推定したり、参照したりする必要がある。これは人為的ミスにつながりがちであり、また、最も適切な資源にタスクが最適に分配される結果に通常ならないであろう。本システムの実施形態は、この問題を解決しようとして、次の特徴を提供する。
【００１４】
１．分散コンピューティング・ジョブを割り当てるとともに管理する目的で、プロセッサ能力およびキャッシュ・メモリ、ＲＡＭ、ローカル・ディスクを含む（しかしこれらに限定されない）局部記憶装置と、ネットワーク帯域幅およびレイテンシと、サービスの保証品質および資源あたりのコストと、に関する最適化を可能にする程度に詳細にＩＴネットワークを記述するための方法。
【００１５】
２．上の１で定義されるようなネットワーク特性を自動的に割り出すためのメカニズム。これは、ネットワーク上に存在するとともにクエリーに応答するかまたは代理で（on a proxy）情報を通知するかまたはオンデマンドで資源をポーリングするデーモン・プロセス、あるいはネットワーク上で動作するプログラムまたは関連するネットワークに関する公開されているあるいは格納されている情報を参照するプロセスであり得る。
【００１６】
３．演算回数、通信帯域幅およびスケジュール、メモリ要件、入出力動作および外部プロセスへのリンクを含む（しかし、これらに限定されない）、ＩＴネットワーク上で動作させられるプロセスを記述するための方法。
【００１７】
４．ＵＭＬメタ・コード、ソース・コード、オブジェクト・コードから上の３の要素を自動的に割り出すためのメカニズム。
【００１８】
プロセス１乃至４を実現するためのコードを実行する１つまたは複数のコンピュータが用いられることが可能である。この１つまたは複数のコンピュータは、分散コンピューティング・タスクを実行するために用いられるネットワークの一部であってもよいし、またはネットワークから分離していてもよい。プロセス１乃至４は、１つのアプリケーションの一部であってもよいし、または個別のモジュール、例として資源記述構築プログラム、タスク記述構築プログラム、へと分離されていてもよい。
【００１９】
図２は、１において概説された目的のために用いられることが可能なデータ構造２００を概略的に示している。このデータ構造は、資源の様々な特性を表わす変数の組を含んでいる。資源は、制御演算装置、または記憶装置、または通信リンクであり得る。典型的には、資源データは、分散コンピューティング資源の特性、例としてメモリ、通信帯域幅、処理速度、データ転送速度について記述する。しかしながら、図において用いられている変数があくまで例示であり、また示されているものに加えてまたはこれらに代えて別の特性が記述されることが可能であることが理解されるであろう。例えば行列演算の際に非常に高速であるような特殊な機能を有することを明示する、プロセッサの特性を表す変数が含められることが可能である。Ｉ／Ｏ装置の特性、例として装置のタイプおよび（または）Ｉ／Ｏ装置が共に動作するＩ／Ｏのタイプ、例としてキーボード、ハプティック・グローブ（haptic glove）、ビジュアライザーション・ウォール／スクリーン（visualisation wall/screen）、仮想現実装置、が表されることも可能である。データ構造は、所望により、適切なユーザ・インターフェースを用いて、書き入れ／編集されることが可能である。場合によっては、データ構造は、ファイル・エディタ等を用いることによって完成されることを容易にするためにプログラマにとってよく知られているフォーマットを用いて実現され得る。その記述は、汎用であるとともに新たなハードウェア資源などが含められるように適応させるのが簡単なものであることが意図されている。
【００２０】
図３は、利用可能な資源の記述を生成するために行なわれるステップの例を概略的に示している。図において示されている工程ステップがあくまで例示であり、また変形体、例としてステップのうちの幾つかが省略されたり、また（または）それらの順序／反復が変更されたりすることが可能であることが理解されるであろう。ステップ３０２において、受け入れ可能な接続タイプおよびどのネットワーク資源が用いられることになるかを決定することに関係する資源属性の記述が入力され得る。例えば、記述されている受け入れ可能資源が、ある閾値を越えている処理／データ転送速度を有するノード／接続だけが用いられることになることを明示しているかもしれない。この記述は、実行されるタスクおよび（または）ネットワーク化された資源（およびそれらの現在の利用可能度等）についての知識を有しているかもしれないユーザから取得されることが可能で、または資源記述構築プログラムによって設定されているデフォルト値から取得されてもよい。
【００２１】
ステップ３０４において、ネットワーク・ノードのうちの１つが「先頭ノード」として選択される。先頭ノードは、利用可能資源の記述を構築するプロセスのための開始点である。この先頭ノード・データは、使用者によって選択／入力され得、または記憶装置から取り出され得、例えば、資源記述構築プログラムが１つまたは複数のネットワーク・セットアップ用にデフォルトの先頭ノード・データでセット・アップ済みである。
【００２２】
ステップ３０６および３０８は、ステップのループの一部として行われ得る。選択された先頭ノードから始めて、資源記述構築プログラムは、そのノードと通信している他のノードおよび接続に応答指令信号を発する（interrogate）とともにそれらの属性について記述するデータを生成する。次に、ステップ３１０において、この記述データは、例えば図２に示されているデータ構造２００で保存される。ステップ３０６および３０８は、直前に応答指令信号を受けたノード／接続と通信中の発見された他のあらゆるノード／接続について、ネットワーク内のノード／接続がすべて網羅されるまで、繰り返される。当業者は、このことを達成するための様々な方法、例として先頭ノードから始めて縦型探索タイプのアルゴリズムを用いて再帰的にネットワークの全体を検討すること、があることを認識するであろう。
【００２３】
図４は、上の３で概説された目的のために用いられることが可能なデータ構造４００を概略的に示している。このデータ構造は、分散されるタスクの様々な特性を表わす変数の組を含んでいる。典型的には、タスク・データは、浮動小数点演算回数、整数演算回数、要求されるメモリ、データ転送量のような特性を用いてタスクを記述する。しかしながら、これらの変数および図４に示されている変数があくまで例示であり、示されているものに加えてまたはこれらに代えて別の特性が記述されることが可能であることが理解されるであろう。
【００２４】
図５は、タスクの記述を生成するために行なわれるステップの例を概略的に示している。ステップ５０２において、計算要件の組が取得される。計算要件の組は記憶装置（デフォルト値）から取り出されることが可能であり、またはユーザが、実行される分散コンピューティング・タスクおよび（または）（利用可能な）ネットワーク資源の知識を場合によっては用いて選択してもよい。例えば、ユーザが、典型的な計算要件のリスト／メニューから１つ以上の要件を選ぶことが可能である。そのような要件の全てを網羅してはいないリストは、浮動小数点演算回数、整数演算回数、必要なメモリ、（ノード間の）データ交換量を含んでいる。
【００２５】
ステップ５０４において、実行されるタスクはその（ステップ５０２で取得された計算要件についての）計算要件を割り出すために分析される。これを行なう様々な方法があることが認識されるであろう。例えば、タスクの全体がステップごとに、またはステップの部分／グループへと分割され得、また、特定のステップ／部分によって要求される整数演算回数が、タスク・ソースまたは実行可能コードを分析するプログラムを用いて記録され得る。あるいは、ユーザがコードを分析して推定値を生成してもよい。次に、タスク全体についての全ての整数演算の合計が算出されることが可能である。次に、本プロセスは、別の計算要件のために繰り返され得る。ステップ５０６において、ステップ５０４の結果を表わす出力が生成される。これは、任意の適切なフォーマットの形態、例としてＸＭＬ、できればネットワーク・オペレーティング・システムが読み取り可能なＸＭＬおよびタスクを行なうためにネットワーク資源を割り当てるためのプログラムである。
【００２６】
図６は、タスク・データ構造によって記述されている分散コンピューティング資源のどれがタスク・データ構造によって記述されているタスクを行なうために用いられるかを選択するために行われるステップの例を概略的に示している。ステップ６０２において、図５のステップを用いて生成されたタスク記述データがロードされる。また、ステップ６０４において、図３のステップを用いて生成された、ネットワーク資源を記述するデータがロードされる。
【００２７】
ステップ６０６において、タスクはネットワーク資源の少なくとも１つに割り当てられる。これを行なう様々な方法があることが認識されるであろう。例えば、資源を割り当てるプログラムは、従来のアルゴリズム、例として確率的、または確定的、またはヒューリスティックな最適化アルゴリズムを用いて様々な資源にタスクの一部を割り当てることが可能である。当業者は、オペレーションズ・リサーチの分野からの適切な技術を発見／導出することができるであろう。これらは、（変数があらかじめ定義された値の組だけを取り得る）離散型および（変数が任意の（ベクトルの）実数値の数である）連続型最適化方法の両方向けの線形且つ整数プログラム技術を含むことが可能である。非線形技術が用いられてもよい。
【００２８】
適切なオペレーションズ・リサーチ技術の例の全てを網羅してはいないリストは、：分岐限定法（探索をツリー状に組織化することによって離散型最適化問題を解決するための技術。ツリーの各ノードで目的関数上の境界（bounds on the objective）が算出され、これがツリーの一部を探索から除外するために用いられる。）や、動的計画法（再帰を用いて、動的（つまり時間構造を伴った）最適化問題を解決するための方法）や、整数計画法（変数が整数値（つまり０、１、２、３…）のみをとり得る最適化）や、ラグランジュ緩和（最適化問題の変形体であり、（ラグランジュ乗数と呼ばれる）補助的なパラメータを乗じられた目的関数へと制約条件が移動される。これらの乗数はいわゆる双対問題中では変数になる）や、線形計画法（目的関数および制約条件が線形である最適化）や、シンプレックス（単体）・アルゴリズム（制約条件のない最適化であり、目的関数値のみ（すなわち、派生物（derivative）無し）を用いる。目的関数値は単体の頂点において算出される。また、新しい頂点が、他の頂点によって作られる平面内での最悪の頂点を反射することにより生成される。ネルダー・ミード・シンプレックス法は、理解および実行が簡単であるとともにタスクの一部を様々な資源に割り当てるための派生物を必要としない故に、非常に人気が高い）や、２次計画法（目的関数が非線形で、制約条件が線形の最適化）を含んでいる。適切な最適化スキームは、上の（および（または）他の）スキームの組合せであってもよいし、処理中の特定の問題に関する知識を要求するいわゆるヒューリスティックなものであってもよい。処理タスクをネットワーク化された資源に分散するために、ネットワーク資源を指揮する際の整数値の解釈についての既存の（通常過去の実績の記録に基づいている）知識を埋め合わせる（account for）ためのヒューリスティック法を含めて、動的計画法と整数計画法の組合せが最良であろう。
【００２９】
資源利用可能度と費用のような因子がアルゴリズムによって考慮されてもよい。本方法は、遺伝的アルゴリズムや、焼きなまし法や、演算解析技術や、以前の知識に基づいたヒューリスティック法や、ニューラル・ネットおよび人工知能のようなマシン学習手法を含み得る。これらは、すべて、当業者にとって良く知られているものである。
【００３０】
ネットワーク資源がタスクの実行の間に変化する場合、ステップ６０８が行われ得る。例えば、プロセッサが別のタスクを行なうために至急必要とされているか、またはその他の理由により利用不能になると、資源割り当てプログラムは、残りの利用可能な資源を（取得された記述に基づいて）分析するとともに分配されたタスクの一部を別の適切な資源に割り当てることを試みる。この再割り当ては、動的にまたは静的に行なわれることが可能である。ネットワーク分散プログラムが既に実行されている場合、タスクを実行するために資源を再割り当てしている最中にこのプログラムを停止（または休止）することは望ましくないかもしれない。資源の利用可能度（または費用）がその場で変化するかもしれないからである。動的な再割り当てによって、本プロセスが、将来の資源割り当てプロファイル（すなわち、タスク記述および資源記述に基づいた割り当て最適化プロセスの結果）を変更しながら実質的に中断されないでいることが可能である。上に説明された最適化技術は静的・動的な計画の両方の動作を有効にすることが可能である。したがって、技術の選択は、ネットワーク・オペレーティング・システムの能力によって決定されることが可能である。
【００３１】
上の本発明の方法によって提供される明確な技術的利益は、エンドユーザが、ジョブを実行依頼する前に資源の利用可能度を推測したり、不慣れなコードについての資源要件を完全に理解したりすることが、もはや必要ではないということである。通信路を最適化する際のＴＣＰ／ＩＰの制約は本発明によって対処される。プロセスがオペレーティング・システムおよび特化された副部品（specialist sub-component）に供給できる資源要件の記述がより豊富であるからである。
【図面の簡単な説明】
【００３２】
【図１】ネットワーク上で接続されている分散コンピューティング資源の組の例を概略的に示している。
【図２】分散コンピューティング資源について記述するデータの図式的な表示である。
【図３】図２のデータを生成するために行なわれるステップを概略的に示している。
【図４】コンピューティング・タスクについて記述するデータの図式的な表示である。
【図５】図４のデータを生成するために行なわれるステップを概略的に示している。
【図６】どの分散コンピューティング資源がタスクを行なうために使用されるかを選択するために行なわれるステップを概略的に示している。
【図１】
2009528649.tif 000003
【図２】
2009528649.tif 000004
【図３】
2009528649.tif 000005
【図４】
2009528649.tif 000006
【図５】
2009528649.tif 000007
【図６】
2009528649.tif 000008
【国際調査報告】
2009528649.tif 000009
2009528649.tif 000010
2009528649.tif 000011