(57)【要約】  【課題】  好ましい実施形態は、異機種混合分散コンピューティング環境内のワークロードの増大に対処する拡張性の高いワークロード・スケジューリング・システムを提供する。  【解決手段】  より詳細には、好ましい実施形態は、修正版平均コンセンサス・アルゴリズムを利用してネットワーク・トラフィック及びジョブを複数のコンピュータに均一に分散させる。このため、好ましい実施形態は、ユーザがこれらのコンピュータの論理トポロジを含む仮想ネットワークを確立することを可能にする。各コンピュータの状態情報は、修正版平均コンセンサス・アルゴリズムによって残りのコンピュータに伝搬される。これにより、好ましい実施形態は、要求されるリソースが個々のコンピュータのリソースの所望の使用率と最適な形で整合するジョブを個々のコンピュータが独自に選択することを可能にすることにより、マスタ・サーバの必要性を解消することが可能となる。  【選択図】  図１
2011516998.tif 000002
【特許請求の範囲】
【請求項１】
複数のコンピュータのワークロードをスケジューリングする方法であって、
連結グラフを形成するようにリンクされた前記コンピュータのうちの少なくともいくつかのコンピュータを含むネットワークを確立するステップ（２０）と、
前記ネットワークの所望の動作点を定めるステップ（２２）と、
前記ネットワーク内の前記コンピュータのうちの少なくともいくつかのコンピュータのリソースについて、前記いくつかのコンピュータ上で実行中の１つ又は複数のジョブによる現在の使用率を判定するステップ（２４）と、
前記ネットワーク内の各コンピュータの予想状態値を、前記各コンピュータのリソースの現在の使用率及び前記所望の動作点から計算するステップ（２６）と、
前記ネットワーク内の前記コンピュータのうちの１つのコンピュータの予想状態値が前記コンピュータのリソースの現在の使用率を実質的に上回る場合は、前記１つのコンピュータによって次に実行されるべき別のジョブを選択するステップ（２８）と、
を含む方法。
【請求項２】
前記ネットワーク内の前記コンピュータのうちの少なくともいくつかのコンピュータのリソースの現在の使用率を判定する前記ステップ（２４）は、前記リソースの現在の使用率に関する情報を監視ソフトウェアによって収集されるリソース消費メトリックから取得するステップを含む、請求項１に記載の方法。
【請求項３】
請求項１又は２に記載の方法は、各ステップに先立って、ユーザが前記ネットワークのトポロジを選択することを可能にするステップを含み、
前記ネットワークを確立するステップ（２０）は、選択された前記トポロジに従って前記コンピュータ同士をリンクさせるステップを含む、
請求項１又は２に記載の方法。
【請求項４】
前記ネットワーク内の各コンピュータの予想状態値を計算する前記ステップ（２６）は、
ユーザが近傍値を選択することを可能にするステップと、
前記ネットワークの前記グラフ内の前記コンピュータに最も近いコンピュータを前記近傍値の数だけ含む近傍グループを、各コンピュータ毎に形成するステップと、
前記予想状態値を、前記所望の動作点と、前記コンピュータ及び前記コンピュータの近傍グループ内のコンピュータのリソースの現在の使用率との平均から計算するステップと、
を含む、前記請求項のいずれか一項に記載の方法。
【請求項５】
あるコンピュータの予想状態値が前記コンピュータのリソースの現在の使用率を実質的に上回る場合は、それ自体のリソース要求が前記コンピュータの予想状態値と前記コンピュータのリソースの現在の使用率との差に最も近いジョブが、前記コンピュータによる実行のために選択される、前記請求項のいずれか一項に記載の方法。
【請求項６】
複数のコンピュータのワークロードをスケジューリングするシステムであって、前記請求項のいずれか一項に記載の方法を実行するように適合された１つ又は複数の構成要素を備えるシステム。
【請求項７】
コンピュータ・システム上で実行されたときに請求項１乃至５のいずれか一項に記載の方法を実行する命令を含むコンピュータ・プログラム。
【請求項８】
コンピュータ・マシンによって読み取り可能な媒体に記憶され、請求項７に記載のコンピュータ・プログラムが有形に実装されたコンピュータ・プログラム製品。
【請求項９】
請求項１乃至５のいずれか一項に記載の方法を実行するデータ処理システム内に配備されるサービス。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、異機種混合分散コンピューティング・システムにおけるワークロード・スケジューリング方法、システム、及びコンピュータ・プログラムに関するものである。
【背景技術】
【０００２】
近年、ワークロード・スケジューリングは、ＩＴ環境の構成要素としての重要性が益々高まっている。実際、多くのグリッド・コンピューティング環境は、分散リソース・セット間の作業（例えば計算、ストレージ、通信能力、ソフトウェア・ライセンス、特殊機器等）のスケジューリングによって主導される。スケジューリングは、突き詰めれば最適化の問題であり、関与するリソース・タイプが１つしか存在しない場合は非常に単純なものとなる。しかしながら、更なる性能改善はより多くのリソース変数をスケジューリング・プロセスに含めることで達成され得るが、その結果得られる多変数最適化は、難解な数学問題となる。
【０００３】
従来のジョブ・スケジューリング手法は、ジョブのセットアップ、スケジューリング、及び管理が中央サーバ（「マスタ」サーバとして知られる）から行われるマスタ／エージェント・アーキテクチャを利用している。実際の作業は、他のサーバ上にインストールされるエージェントによって行われる。使用において、マスタは、ジョブの割り当て先を決定することができるようにジョブや利用可能なサーバ等に関する情報を維持し、その変換処理を行う。一方、エージェントは、マスタからのコマンドを待ち、コマンドを実行し、マスタに終了コードを返す。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】A. Mostefaoui, et al. Proceedings of the 8th International Colloquium on StructuralInformation and Communication Complexity (SIROCCO'01), 275-291, CarletonUniv. Press, 2001
【非特許文献２】Alsalih, W., Akl, S. and Hassancin, H., Proceedings. 19th International Parallel andDistributed Processing Symposium, 2005, IPDPS 2005, 4-8 April 2005,Denver, CA, USA, p. 242a
【非特許文献３】L.Xiao et al., Journal of Parallel andDistributed Computing, Volume67 (1), 2007, 33-46
【発明の概要】
【発明が解決しようとする課題】
【０００５】
マスタ／エージェント・アーキテクチャによってジョブの厳格な制御が可能となるが、マスタとエージェントの同期状態を維持する必要があり（その分ネットワーク及びマスタの可用性にも依存し）、このことがアーキテクチャの重大な制約となる。これに関連して、マスタとエージェントの間のネットワーク・トラフィックの集中度が高まると、アーキテクチャ全体の性能を低下させる恐れがある。別の問題は、マスタ／エージェント・アーキテクチャの拡張性が限られることである。特に、マスタは限られた数のエージェントしかサポートすることができず、また、新しいマスタ又はインスタンスが作成されると個別の新しい管理が発生し、したがって、作成されるインスタンスが増えるほど必要となる管理も増大する。
【課題を解決するための手段】
【０００６】
本発明によれば、複数のコンピュータのワークロードをスケジューリングする方法であって、
・連結グラフを形成するようにリンクされた前記コンピュータのうちの少なくともいくつかのコンピュータを含むネットワークを確立するステップと、
・前記ネットワークの所望の動作点（operating point）を定めるステップと、
・前記ネットワーク内の前記コンピュータのうちの少なくともいくつかのコンピュータのリソースについて、前記いくつかのコンピュータ上で実行中の１つ又は複数のジョブによる現在の使用率を判定するステップと、
・前記ネットワーク内の各コンピュータの予想状態値を、前記各コンピュータのリソースの現在の使用率及び前記所望の動作点から計算するステップと、
・前記ネットワーク内の前記コンピュータのうちの１つのコンピュータの予想状態値が前記コンピュータのリソースの現在の使用率を実質的に上回る場合は、前記１つのコンピュータによって次に実行されるべき別のジョブを選択するステップと、
を含む方法が提供される。
【０００７】
好ましい実施形態は、異機種混合分散コンピューティング環境内のワークロードの増大に対処する拡張性の高いワークロード・スケジューリング・システムを提供する。より詳細には、好ましい実施形態は、修正版平均コンセンサス・アルゴリズムを利用してネットワーク・トラフィック及びジョブを複数のコンピュータに均一に分散させる。このため、好ましい実施形態は、ユーザがこれらのコンピュータの論理トポロジを含む仮想ネットワークを確立することを可能にする。各コンピュータの状態情報は、修正版平均コンセンサス・アルゴリズムによって残りのコンピュータに伝搬される。これにより、好ましい実施形態は、要求されるリソースが個々のコンピュータのリソースの所望の使用率と最適な形で整合するジョブを個々のコンピュータが独自に選択することを可能にすることにより、マスタ・サーバの必要性を解消することが可能となる。
【図面の簡単な説明】
【０００８】
以下では単なる例示として、添付図面を参照しながら本発明の一実施形態について説明する。
【０００９】
【図１】好ましい実施形態のワークロード・スケジューリング・システムのソフトウェア・アーキテクチャのブロック図である。
【図２】好ましい実施形態のワークロード・スケジューリング方法のフローチャートである。
【図３】好ましい実施形態のワークロード・スケジューリング方法をサポートするように適合されたコンピュータ・システムのブロック図である。
【発明を実施するための形態】
【００１０】
１．序論
好ましい実施形態は、異機種混合分散コンピューティング環境におけるジョブ分散のための、コンセンサス・アルゴリズムに基づくワークロード・スケジューリング・システムを提供する。より具体的には、好ましい実施形態は、この手法を利用して従来のマスタ／エージェント・アーキテクチャにおける中央（マスタ）サーバの必要性をなくすことを企図する。これにより、ネットワークの拡張性及び耐障害性が高まり、ネットワーク内のトラフィック分散の均一性も高まる。
【００１１】
耐障害性システムでは多くの場合、独立したコンピュータ又はプロセス同士がある種の合意（又はシステム状態の共通認識）に達することを可能にするメカニズムが必要とされる。このメカニズムは、例えば冗長システムのコンピュータが周期的に内部クロックの同期をとるのに必要となる可能性がある。障害がない場合、満足のいく合意に達することは比較的容易である。多くの場合は、値を単純に交換し、ある種の平均値を計算するだけで済む。一方、コンピュータのうちの１つ又は複数に障害が生じた場合は、上記の交換プロセスは信頼性が低下する。特に、障害のあるコンピュータは、第１のコンピュータにある値を報告しても他のコンピュータには別の値を報告する可能性があり、その結果、コンピュータ毎に異なる「平均値」が計算される恐れがある。耐障害性システムにおける共通認識の達成の問題は、分散コンピューティングにおける大きな課題であり、ビザンチン将軍（Byzantinegenerals）問題、ビザンチン合意（Byzantine agreement）、又はコンセンサス問題を含めたいくつかの名前で知られている。
【００１２】
双方向リンクに沿ったメッセージ交換を利用して通信することが可能なｎ個のコンピュータで構成されるネットワークについて考える。コンセンサスは、あるメッセージがソース・コンピュータから配信されたときに、当該メッセージが変更されずにすべての受信側コンピュータによって確実に受信されるように試行するものである。更に、受信側コンピュータによって受信されるメッセージは、ソース・コンピュータから発行されるメッセージと同一でなければならない。しかしながら、メッセージを受信する側のコンピュータは、ソース・コンピュータが信頼可能であるか否かを事前に知らされない。この問題を克服するために、受信される値／メッセージの同一性に関して受信側コンピュータ間で合意を形成することを可能にするプロトコルが必要となる。このため、受信側コンピュータは、それぞれが受信した値を交換しなければならなくなる。しかしながら、コンピュータは完全に信頼可能であるとは限らない可能性があるため、受信されたものと異なるメッセージ／値が交換される恐れがあり、これらの障害を克服するために複数回の交換ラウンドが必要となる。
【００１３】
A. Mostefaoui, et al. Proceedings of the 8th International Colloquium on StructuralInformation and Communication Complexity (SIROCCO'01), 275-291, CarletonUniv. Press, 2001には、最大ｆ回のプロセス・クラッシュの発生に耐え、ｎ個のプロセスを対象とするコンセンサス問題を解決するプロトコルを設計することが可能な入力ベクトル集合を識別することを含む条件ベース手法が記載されている。しかしながら、この文献は、異機種混合分散コンピューティング環境におけるワークロード・スケジューリングの問題について論じたものではない。むしろ、この文献は、同じマシン上のプロセス通信に使用される（共用メモリ内の）書き込み動作の回数を減少させるメカニズムを説明するものである。
【００１４】
Alsalih, W., Akl, S. and Hassancin, H., Proceedings. 19th International Parallel andDistributed Processing Symposium, 2005, IPDPS 2005, 4-8 April 2005,Denver, CA, USA, p. 242aには、モバイル・ワイヤレス・アドホック・ネットワーク（ＭＡＮＥＴ）内の１組のモバイル・コンピューティング・デバイス間に計算タスクを分散させてエネルギーを節約し性能を改善するヒューリスティック・アルゴリズムが記載されている。しかしながら、このアルゴリズムは、コンセンサス・アルゴリズムに基づく分散スケジューラではなく通常の分散スケジューラに関するものである。
【００１５】
L. Xiao etal., Journal of Parallel andDistributed Computing, Volume67 (1), 2007, 33-46には、各ノードが最小平均二乗偏差を使用してそれぞれの負荷を設定する分散平均コンセンサスを使用したロード・バランシング・メカニズムが記載されている。しかしながら、この手法では、コンセンサス・アルゴリズムは、ユーザによる修正又は変更が可能でない固定された平均値に達することになる。
【００１６】
２．好ましい実施形態の概要
図１を参照すると、好ましい実施形態５は、分散異機種混合ネットワーク１２で実行すべきジョブ
【数１】
2011516998.tif 000003
のリポジトリ１０を備える。各ジョブ（ｊｏｂｉ）には、そのジョブで必要とされるリソース（例えばＣＰＵ使用率、メモリ、ネットワーク・トラフィック等）を指示する要求ベクトル
【数２】
2011516998.tif 000004
が付加されている。それ故、ジョブ・リポジトリ１０には事実上、ジョブと要求ベクトルの対で構成される行列
【数３】
2011516998.tif 000005
が収容される。即ち、
【数４】
2011516998.tif 000006
。
【００１７】
簡略化のために、分散異機種混合ネットワーク１２は、ｎ個のノード
【数５】
2011516998.tif 000007
を含み、各ノード（ｎｏｄｅｉ）は、リソース
【数６】
2011516998.tif 000008
を所有するものと仮定する。好ましい実施形態は、トポロジ形成アルゴリズム１４ならびに修正版平均コンセンサス・アルゴリズム１６を利用して、分散異機種混合ネットワーク１２内の各ノードがそれぞれの現在のステータス及び新しいジョブの実行に使用できる可能性をネットワーク内の他のノードに知らせることを可能にする。好ましい実施形態は更に、分散異機種混合ネットワーク１２内のノード
【数７】
2011516998.tif 000009
が各ノード（ｎｏｄｅｉ）のリソース
【数８】
2011516998.tif 000010
に関するユーザ定義された所望の使用率と、ジョブ（ｊｏｂｋ）のリソース要求（resource requirement）
【数９】
2011516998.tif 000011
と、に従って、（次に実行すべき）最適なジョブ（ｊｏｂｋ）をジョブ・リポジトリ１０から選択することを可能にするジョブ選択モジュール１８も備える。
【００１８】
３．好ましい実施形態のシステムの詳細な説明
（ａ）トポロジ形成アルゴリズム（１４）
トポロジ形成アルゴリズム１４は、分散異機種混合ネットワーク１２内のノード
【数１０】
2011516998.tif 000012
の論理トポロジを含む仮想ネットワークを確立する。仮想ネットワーク内では、この論理トポロジによってどのノードが互いに通信可能であるかが定められる。特に、この論理トポロジは、各ノードがｊ個の隣接ノード（但し、ｊ＜ｎ−１）と直接連結される（且つ通信可能となる）ように定義される。それ故、ｎｏｄｅｉには、ｊ個のノード（ｎｏｄｅｐ、ｐ＝１〜ｊ）を含む近傍Ｎｉが提供される。あるノードの連結先となるノードの数はユーザによって定義することができ、好ましい実施形態の耐障害性（及び収束速度）は、かかるノードの数を増加させることによって改善される。このトポロジに課される唯一の条件は、仮想ネットワークによって形成されるグラフが連結でなければならないこと、換言すると、各ノードから他の任意のノードに任意のステップ数で到達可能でなければならないことである。
【００１９】
それ故、リング・トポロジでは、各ノードは２つの連結及び２つの近傍のみを有することになる。したがって、例えば図１を参照すると、ｎｏｄｅ１はｎｏｄｅ２及びｎｏｄｅ６と直接連結されている。同様に、ｎｏｄｅ２はｎｏｄｅ１及びｎｏｄｅ３と、ｎｏｄｅ６はｎｏｄｅ１及びｎｏｄｅ５とそれぞれ直接連結されている。言うまでもなく、図１に示したトポロジは、単なる例示として示されるものであり、好ましい実施形態をリング・トポロジに限定するように決して解釈すべきではないことが理解されるだろう。特に、好ましい実施形態は、分散異機種混合ネットワーク１２内の任意のトポロジ及び任意の数のノードと共に動作可能である（上述の連結制約は課される）ことが当業者には理解されるだろう。
【００２０】
（ｂ）ノード（使用リソース）状態変数
仮想ネットワーク内の各ノード（ｎｏｄｅｉ）は、各ノードのリソースがそれ自体の上で現在実行されているジョブによってどの程度占有されるかを指示する使用リソース状態変数（usedresources state variable）を含む。この情報は、監視ソフトウェアによって収集される実時間リソース消費メトリックから取得することができる。具体的には、
【数１１】
2011516998.tif 000013
を所与のリソース・ベクトル
【数１２】
2011516998.tif 000014
に関連する消費メトリック・ベクトルとして定義した場合、所与のノードのリソースが（現在実行中のジョブによって）占有される程度は、ノード（ｎｏｄｅｉ）のリソース変数の消費メトリックの加重和であるスカラ変数ｓｔａｔｅｉ、即ち、
【数１３】
2011516998.tif 000015
によって与えられ得る。また、スカラ変数ｓｔａｔｅｉのベクトル表記は、
【数１４】
2011516998.tif 000016
となる。但し、
【数１５】
2011516998.tif 000017
好ましい実施形態の修正版平均コンセンサス・アルゴリズム１６を用いると、各ノードは、上記の情報を仮想ネットワーク全体にわたって、発信元のノードが直接連結されていないノードにも伝搬させることが可能となる。
【００２１】
同様の表記法を使用して（ジョブ・リポジトリ内の）特定のジョブの要求を記述することができる。具体的には、ジョブ（ｊｏｂｑ）の正味要求（netrequirement）（ｅｑ）は、次式のように定義することができる。
【数１６】
2011516998.tif 000018
【００２２】
（ｃ）修正版平均コンセンサス・アルゴリズム（１６）
従来の平均コンセンサス・モデル
グラフの平均コンセンサス・モデルは、ｎｏｄｅｉに対する入力ｕｉ及びその近傍（Ｎｉ）によってグラフ展開を計算する分散方法を提供する。それ故、ｎｏｄｅｉのｓｔａｔｅｉの展開が
【数１７】
2011516998.tif 000019
で示すことが可能であるならば、
【数１８】
2011516998.tif 000020
又は
【数１９】
2011516998.tif 000021
により、コンセンサス問題が連結グラフに漸近的に解決されることを証明することができる。したがって、動的システムは、
【数２０】
2011516998.tif 000022
又は
【数２１】
2011516998.tif 000023
で表される初期状態の平均に収束する。上式の各極限の証明は、それぞれに関連するナイキスト線図から導出される。
【００２３】
修正版平均コンセンサス・アルゴリズム（１６）
好ましい実施形態は、仮想ネットワーク内の他のすべてのノードと直接連結される仮想ノードＶ（図示せず）を導入することにより、上述した従来の平均コンセンサス・アルゴリズムを修正する。それ故、仮想ノードＶは、ｎｏｄｅｉの近傍Ｎｉの範囲内に含まれる。この手法を使用した場合、各ノード（ｎｏｄｅｉ）は、
・それ自体の現在の状態（ｓｔａｔｅｉ（ｋ））、及び
・それ自体の近傍Ｎｉ内の他のノード（仮想ノードＶを含む）の現在の状態
から、それ自体の次の状態（ｓｔａｔｅｉ（ｋ＋１））を次式を使用して計算する。
【数２２】
2011516998.tif 000024
【００２４】
仮想ノードＶは、仮想ネットワーク内のすべてのノードの所望のワークロードを表すユーザ構成可能な固定状態を有する。仮想ノードＶが仮想ネットワーク内の各ノードの近傍に含まれることにより、仮想ネットワーク内の他のすべてのノードにおける平均コンセンサス・アルゴリズムが仮想ノードＶの固定状態と釣り合い、その固定状態に収束することになる（収束速度はネットワーク・グラフのラプラシアンと関係付けられる）。それ故、仮想ノードＶの状態をユーザ構成可能にすることにより、好ましい実施形態は、仮想ネットワーク内の各ノードのリソースの所望の使用率（即ち動作点）が満たされるように（即ち、仮想ネットワークの動作点が効果的に変更されるように）ワークロード・スケジュールを調整するメカニズムを効果的に提供する。
【００２５】
（ｄ）ジョブ選択モジュール（１８）
ジョブ選択モジュール１８は、ノード（ｎｏｄｅｉ）が次に実行すべきジョブをそれ自体の現在の状態及び計算された次の状態に従って（ジョブ・リポジトリ１０から）選択することを可能にする。特に、ｓｔａｔｅｉ（ｋ＋１）＜ｓｔａｔｅｉ（ｋ）である場合には、次の反復時にそのノードが引き受ける新しいジョブは存在しないことになる。一方、ｓｔａｔｅｉ（ｋ＋１）≧ｓｔａｔｅｉ（ｋ）である場合には、差分変数Δは、Δ＝ｓｔａｔｅｉ（ｋ＋１）−ｓｔａｔｅｉ（ｋ）（即ち、ｎｏｄｅｉの計算された次の状態と該ノードの現在の状態との差）として定義される。（ジョブ・リポジトリから）選択される次のジョブ（ｊｏｂｋ＋１）は、それ自体の正味要求変数（ｅｔ）が差分変数Δからの最小差分を有する（即ち、ｅｔ｜ｍｉｎｔ（Δ−ｅｔ））ジョブ（ｊｏｂｔ）である。
【００２６】
４．好ましい実施形態の方法の詳細な説明
図２を参照すると、好ましい実施形態の方法は、
・連結グラフ制約が課された所望のトポロジに従って仮想ネットワークを確立するステップ（２０）と、
・異機種混合分散コンピューティング環境の所望の動作点（即ち、該環境内の各ノードのリソースが実行対象のジョブによって占有されることになる程度）を定めるステップ（２２）と、
・仮想ネットワーク内の各ノードの現在の状態を、各ノードのリソースが各ノード上で現在実行中のジョブによって占有される程度から判定するステップ（２４）と、
・ネットワーク内の各ノードの次の状態を、それぞれの現在の状態、それぞれの近傍内のノードの現在の状態、及び所望の動作点から計算するステップ（２６）と、
・所与のノードによって実行されるべきジョブを、そのノードの現在の状態がそのノードの計算された次の状態とどの程度異なるかに従ってジョブ・リポジトリから選択するステップ（２８）と、
を含む。
【００２７】
５．好ましい実施形態の方法に関する汎用コンピュータ・システムの説明
図３を参照すると、好ましい実施形態をサポートするように適合された汎用コンピュータ・システム４０は、システム・バス４２と並列接続されるいくつかのユニットによって形成される。詳細には、１つ又は複数のマイクロプロセッサ（ＸＰ）４４は、コンピュータ４０の動作を制御し、ＲＡＭ４６は、マイクロプロセッサ４４によって直接ワーキング・メモリとして使用され、ＲＯＭ４８は、コンピュータ４０のブートストラップ用の基本コードを記憶する。周辺ユニットは、（それぞれのインターフェースを利用して）ローカル・バス５０の周囲にクラスタ化される。特に、大容量メモリは、ハード・ディスク５２、及びＣＤ‐ＲＯＭ５６を読み取るドライブ５４で構成される。更に、コンピュータ４０は、入力デバイス５８（例えばキーボード及びマウス）と、出力デバイス（例えばモニタ及びプリンタ）と、を含む。ネットワーク・インターフェース・カード（ＮＩＣ）６２は、コンピュータ４０をネットワークに接続するのに使用される。ブリッジ・ユニット６４は、システム・バス４２とローカル・バス５０のインターフェースをとる。各マイクロプロセッサ４４及びブリッジ・ユニット６４は、情報を送信するためにシステム・バス４２に対するアクセス要求を行うマスタ・エージェントとして動作することができる。アービタ６６は、相互排除を用いてシステム・バス４２に対するアクセス権の付与を管理する。
【００２８】
システムが異なるトポロジを有する場合、又は他のネットワークに基づく場合も同様の考えが当てはまる。別の方法では、コンピュータは、等価なユニットを含む異なる構造を有し、又は他のデータ処理エンティティ（ＰＤＡや携帯電話等）で構成される。
【００２９】
上記の実施形態には本発明の範囲から逸脱しない限り様々な変更及び修正を施すことが可能である。
【図１】
2011516998.tif 000025
【図２】
2011516998.tif 000026
【図３】
2011516998.tif 000027
【手続補正書】
【提出日】平成22年11月1日(2010.11.1)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数のコンピュータのワークロードをスケジューリングする方法であって、
連結グラフを形成するようにリンクされた前記コンピュータのうちの少なくともいくつかのコンピュータを含むネットワークを確立するステップ（２０）と、
前記ネットワークの所望の動作点を定めるステップ（２２）と、
前記ネットワーク内の前記コンピュータのうちの少なくともいくつかのコンピュータのリソースについて、前記いくつかのコンピュータ上で実行中の１つ又は複数のジョブによる現在の使用率を判定するステップ（２４）と、
前記ネットワーク内の各コンピュータの予想状態値を、前記各コンピュータのリソースの現在の使用率及び前記所望の動作点から計算するステップ（２６）と、
前記ネットワーク内の前記コンピュータのうちの１つのコンピュータの予想状態値が前記コンピュータのリソースの現在の使用率を実質的に上回る場合は、前記１つのコンピュータによって次に実行されるべき別のジョブを選択するステップ（２８）と、
を含む方法。
【請求項２】
前記ネットワーク内の前記コンピュータのうちの少なくともいくつかのコンピュータのリソースの現在の使用率を判定する前記ステップ（２４）は、前記リソースの現在の使用率に関する情報を監視ソフトウェアによって収集されるリソース消費メトリックから取得するステップを含む、請求項１に記載の方法。
【請求項３】
請求項１又は２に記載の方法は、各ステップに先立って、ユーザが前記ネットワークのトポロジを選択することを可能にするステップを含み、
前記ネットワークを確立するステップ（２０）は、選択された前記トポロジに従って前記コンピュータ同士をリンクさせるステップを含む、
請求項１又は２に記載の方法。
【請求項４】
前記ネットワーク内の各コンピュータの予想状態値を計算する前記ステップ（２６）は、
ユーザが近傍値を選択することを可能にするステップと、
前記ネットワークの前記グラフ内の前記コンピュータに最も近いコンピュータを前記近傍値の数だけ含む近傍グループを、各コンピュータ毎に形成するステップと、
前記予想状態値を、前記所望の動作点と、前記コンピュータ及び前記コンピュータの近傍グループ内のコンピュータのリソースの現在の使用率との平均から計算するステップと、
を含む、前記請求項のいずれか一項に記載の方法。
【請求項５】
あるコンピュータの予想状態値が前記コンピュータのリソースの現在の使用率を実質的に上回る場合は、それ自体のリソース要求が前記コンピュータの予想状態値と前記コンピュータのリソースの現在の使用率との差に最も近いジョブが、前記コンピュータによる実行のために選択される、前記請求項のいずれか一項に記載の方法。
【請求項６】
複数のコンピュータのワークロードをスケジューリングするシステムであって、前記請求項のいずれか一項に記載の方法を実行するように適合された１つ又は複数の構成要素を備えるシステム。
【請求項７】
コンピュータ・システム上で実行されたときに請求項１乃至５のいずれか一項に記載の方法を実行する命令を含むコンピュータ・プログラム。
【請求項８】
請求項７に記載の前記コンピュータ・プログラムを、コンピュータによって読み取り可能な媒体に記憶した、コンピュータ可読記録媒体。
【請求項９】
請求項１乃至５のいずれか一項に記載の方法を実行するデータ処理システム内に配備されるサービス。
【国際調査報告】
2011516998.tif 000028
2011516998.tif 000029