(57)【特許請求の範囲】
【請求項１】
プロセッサ・ネットワーク内の複数の処理ノードに複数のタスクを分散するコンピュータ実装方法で、前記方法が、
前記複数のタスクに関してタスクがプロセッサ処理量に占める割合であるプロセッサ消費量値を計算するステップと、
前記複数のノードに関してノードのプロセッサ消費量測定値を計算するステップと、
前記複数のノードに関してノードのプロセッサ消費量目標値を計算するステップであって、前記ノードのプロセッサ消費量目標値が前記ノードの容量に比例する、前記ノードの前記プロセッサ消費量目標値を計算するステップと、
ノードｉの前記ノードのプロセッサ消費量測定値とノードｉの前記ノードのプロセッサ消費量目標値との差として負荷指数値を計算するステップと、
各ノードの負荷指数の計算値が実質的にゼロである目標状態へ近づくように、各ノードの前記負荷指数の計算値に従ってノード間でプロセッサの作業負荷バランスをとるようノード間にタスクを分散するステップであって、あるノードから他のノードへのタスクの移動を、実際のプロセッサ作業負荷分散と全アフィニティ・ノードの負荷指数値が実質的にゼロになる目標プロセッサ作業負荷分散との差として求まる負荷指数の偏差の値が、移動後に所定の値を超えて小さくなることを前記タスクの前記プロセッサ消費値を用いて確認することを条件に実行するステップを含む、前記分散するステップと、
を有する方法。
【請求項２】
２以上のプロセッサのタイプがある場合に、ノードの各プロセッサのタイプを判断するステップと、
マトリクスの各次元がある特定プロセッサのタイプに対応するノードを表し、各セルが対応する次元のノードで実行されるタスクを表す、多次元のバランシング・マトリクスを作成するステップであって、タスクの移動があるタイプのノードから他のタイプのノードへと片方向へのみ可能な場合に、前記バランシング・マトリクスの前記あるタイプのノードを表す次元を前記他のタイプのノードで拡張する、前記作成するステップと、
前記バランシング・マトリクスの各次元の各ノードを、その負荷指数値が最も高いものから負荷指数値が最も低い順に並べ替えるステップと、
セル内のタスクを、所定の利用ルールに従い、かつ、前記分散するステップにおける条件に従い、タスクの再配列が非対称になるように再配列するステップとを更に含む、  請求項１に記載の方法。
【請求項３】
ネットワーク内の複数のノードに複数のタスクを分散するシステムで、前記システムが、
タスクを実行する複数のプロセッサと、
プロセッサを有する複数のノードと、
前記複数のタスクを受け取り、前記複数のタスクに関してタスクがプロセッサ処理量に占める割合であるプロセッサ消費量値を計算し、前記複数のノードに関してノードのプロセッサ消費量値を計算し、前記複数のノードに関して、ノードの容量に比例するノードのプロセッサ消費量目標値を計算し、ノードｉの前記ノードのプロセッサ消費量の計算値とノードｉの前記ノードのプロセッサ消費量目標値との差として負荷指数値を計算するタスク・ディスパッチャーと、
各ノードの前記負荷指数の計算値が実質的にゼロである目標状態へ近づくように、各ノードの前記負荷指数の計算値に従い、ノード間でプロセッサの作業負荷バランスをとるようにノード間にタスクを分散するバランサとを有し、
前記バランサが、あるノードから他のノードへのタスクの移動を、実際のプロセッサ作業負荷分散と全アフィニティ・ノードの負荷指数値が実質的にゼロになる目標プロセッサ作業負荷分散との差として求まる負荷指数の偏差の値が、移動後に所定の値を超えて小さくなることを前記タスクの前記プロセッサ消費値を用いて確認することを条件に実行する、
システム。
【請求項４】
前記タスク・ディスパッチャーと前記バランサがコンピュータ・システムに常駐するソフトウェアである、請求項３に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
開示する発明は一般にプロセッサの負荷バランシング分野に関係し、より具体的にはプロセッサ・アフィニティの負荷バランシングの分野に関係する。
【背景技術】
【０００２】
マルチプロセッサのアーキテクチャにおいては、キャッシングの利点を生かすために、タスクをできるだけ同じプロセッサで実行し続けることが望ましい。このことは、キャッシュ間のアクセス待ち時間がキャッシュ内のアクセス待ち時間より大幅に長い不均一メモリアクセス（ＮＵＭＡ）方式のアーキテクチャでは特に重要である。かかるＮＵＭＡアーキテクチャにおいて、タスクがハードウェア・キャッシュを共有しない複数のプロセッサに頻繁にディスパッチされると、大幅な性能の低下が起こる。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
タスクをできるだけ同じプロセッサ（またはプロセッサ群）で実行し続けるために、アフィニティ・ノードと呼ばれるロジック概念が定義される。アフィニティ・ノードとは、ハードウェア・キャッシュを共有するプロセッサ群である。タスクには、それをアフィニティ・ノードに関連付ける（そのアフィニティと呼ばれる）値をマークする。タスク・ディスパッチャーは、タスクをタスクのアフィニティ値が指定するアフィニティ・ノードに属するプロセッサに必ずディスパッチすることによって、タスクのアフィニティを受け取ろうとする。
【０００４】
タスクがそのそれぞれのアフィニティ・ノードに必ずディスパッチされるため、時間が経過すると、タスクの変化する特性と処理需要が、アフィニティ・ノード間のプロセッサ負荷の不均衡を生み出すことになる。そのため、全アフィニティ・ノード間でシステム・プロセッサ消費量全体のバランスをとるために、タスクのアフィニティの再割り当てにプロセッサの負荷バランシング・メカニズムが必要である。加えて、アフィニティ・ノードは異なる数のプロセッサを包含できるため、各アフィニティ・ノードは異なる容量を有しうる。「バランス」という用語は、全アフィニティ・ノードのプロセッサ消費量を等しくするというような、よく使われる意味ではなく、一般的に全アフィニティ・ノードのプロセッサ消費量に一定の基準を満たさせるという意味である。平衡システムの共通の基準とは、システム・プロセッサ消費量全体を全アフィニティ・ノード間にその容量に比例して分配することである。
【０００５】
ＵＮＩＸ（商標）（およびＵＮＩＸ変種）などの、運用オペレーティング・システムにおける既存のプロセッサ負荷・バランシング・スキームはある共通した特徴を有する。すなわち、そのすべては、プロセッサ負荷の予測として平均タスク実行キュー長さを使用することである。この理由は、タスク実行キュー長さ（実行キュー長さとしても知られる）が測定しやすく、現在の運用オペレーティング・システムの大半がタスクごとに精密なプロセッサ消費量を測定する内蔵機能を有さないからである。ほとんどの場合それで十分であるが、平均タスク実行キュー長さは実際のプロセッサ負荷を必ずしも正確に反映しているとは限らない。
【０００６】
図１を参照して、この概念を表すのに役立つ２つのノードを備えるプロセッサ・ネットワーク１００の簡単な例を示す。システムは２つのノード１４０および１６０で動作し、各ノードが１つのＣＰＵと、ロジカル・タスク・マネージャー１２０および１３０を包含する。タスク・マネージャー１２０はタスク１８０をノードＡ１４０にディスパッチし、タスク・マネージャー１３０はタスクをノードＢ１６０にディスパッチする。タスク・マネージャー１２０および１３０は独立して動作するため、時間が経過するとネットワーク１００内のプロセッサ負荷は、タスクの数とノード１４０および１６０に到達するタスクのＣＰＵ需要特性が大幅に異なりうるために不均衡になっていく可能性がある。そのため、ノード１４０および１６０におけるプロセッサ負荷のバランスをとるためには、バランサ１５０がタスク・マネージャー１２０と１３０の間でタスクを移動させる必要がある。周知のプロセッサ・ネットワークにおいては、バランサ１５０はノードのプロセッサ負荷を、そのノードの平均実行キュー長さを利用することによって判断する。すなわち、キュー長さが長くなるほど、ノードに負荷がかかる。しかし、この方法は、以下の例を使って示すように、いくつかの欠点がある。
【０００７】
ｎ＋１個のタスク１８０がアフィニティ・ノードＡ１４０に入り、そのノードが短時間ｔの間にその全処理容量を使ってすべてのタスク１８０が終了すると仮定する。それからアフィニティ・ノードＡ１４０内のプロセッサは短時間ｔの間アイドリングした後で別のｎ＋１個のタスク１８０がノードＡに入り、アフィニティＡに関してキューにタスクがなくなるまでこのサイクルを繰り返す。ノードＡ１４０の場合、プロセッサ負荷は平均して約５０％であり（すなわち、プロセッサは時間の半分がビジーで、プロセッサは時間の半分がアイドリング状態である）、実行キュー長さは約ｎ／２である（時間の半分はｎ個のタスクが待機し、時間の半分は待機するタスクがない）。
【０００８】
ここで、別のアフィニティ・ノードを考える。ノードＢ１６０では、単一の長時間実行プロセッサ・バウンドのタスクがノードＢの全処理容量を利用し、他のタスクは待機していない。このノードの場合、プロセッサ負荷は平均して１００％である（プロセッサは常にビジーである）が、実行キュー長さはゼロである（待機するタスクがない）。平均実行キュー長さ方法を利用するバランサ１５０は、半負荷のノードＡ１４０から全負荷のノードＢ１６０にタスクを移動することになるが、これは作業負荷をさらに不均衡にさせることになろう。
【０００９】
平均タスク実行キュー長さのアプローチに伴う別の問題は、タスクを移動してプロセッサ負荷のバランスをとる場合、移動されたタスクの実際のプロセッサ消費量は考慮しないため、システムの一層の不均衡を引き起こすおそれがある、ということである。別の例でこの点を例証していく。再び図１を参照して、アフィニティ・ノードＡ１４０は、定期的にノードに入るｎ＋１個のタスク１８０に加えて、ＣＰＵを占有する長時間実行のＣＰＵバウンドのタスクを有すると考える。このノードの場合、処理負荷は平均して１００％であり、実行キュー長さは約（ｎ＋１）／２である。ここで同じ単一の長時間実行ＣＰＵバウンドのタスクを有するアフィニティ・ノードＢ１６０を考える。ノードＢ１６０の場合、処理負荷は平均して１００％であり、実行キュー長さは０である。このシステムは明らかに不均衡であり、タスクをノードＡ１４０からノードＢ１６０に移動する必要がある。バランサ１５０は一般的に、キューの最後尾にあるタスクの待ち時間が最も長いため、移動すべきタスクをタスク実行キューの最後尾にあるタスク１８０を最初に移動するように選択する。移動するタスク１８０のプロセッサ消費量を考慮せずにこの方法を使うと、ノードＡ１４０の長時間実行ＣＰＵバウンドのタスクがキューの最後のタスクになってしまうこともあり、ノードＢ１６０に移動する可能性があるため、システムは一層不均衡になる可能性がある。その結果、ノードＡ１４０はここでもやはり（ノードＡ１４０が長時間実行のＣＰＵバウンドのタスクを有さなかった前の例で示したように）時間の半分がアイドリング状態である一方で、ノードＢ１６０は２つの長時間実行ＣＰＵバウンドのタスクで過負荷になり、各ノードともプロセッサ容量の５０％にしかならない。
【００１０】
図２は、複数のプロセッサを備えるプロセッサ・アーキテクチャ２００の負荷バランシングの別の例を示す。この図は、図１の２つのアフィニティ・ノードに加えて、さらに２つのアフィニティ・ノードを有する典型的なＮＵＭＡプロセッサ・アーキテクチャを示し、ここでは各ノードは１つではなく４つのＣＰＵを備える。実際には、アフィニティ・ノードの数と各ノード内のＣＰＵの数はともに異なることがある。各ノード内の４つのＣＰＵはＬ２キャッシュ（レベル２キャッシュ、またはマイクロプロセッサ外部のキャッシュ・メモリ）を共有する。Ｌ２キャッシュ・メモリは、マイクロプロセッサのチップ上に存在するレベル１キャッシュとは異なり、マイクロプロセッサのチップとは独立した別のチップ上に存在する。Ｌ２キャッシュは、複数のＣＰＵがキャッシュ・メモリを共有するために必要なものである。このプロセッサ・アーキテクチャ２００では、図１のタスク・マネージャー１２０および１３０がここでは４つのディスパッチャーであり、各ディスパッチャーがノードを１つ受け持つ。各ディスパッチャーはその特定ノードのタスクのジョブ・キューを受け取る。ディスパッチャー２２５はタスクをジョブ・キューＡ２２０からノードＡ１４０にディスパッチする。ディスパッチャー２３５はタスクをジョブ・キューＢ２３０からノードＢ１６０にディスパッチする。ディスパッチャー２４５はタスクをジョブ・キューＣ２４０からノードＣ２５０にディスパッチする。ディスパッチャー２５５はタスクをジョブ・キューＤ２５０からノードＤ２６０にディスパッチする。
【００１１】
各ノードは、負荷バランシングのために、ネットワーク２００を介してネットワーク内の他の全ノードに接続される。図２に図示するアーキテクチャ２００は実に単純なマルチプロセッサ・アーキテクチャであるが、規模を大幅に変更できる。実際に、現在ますます高まっている処理需要に伴い、数千台およびさらには数万台のプロセッサからなるネットワークが使用されており、ＣＰＵの負荷バランシングが不可欠になっているにも関わらず、現在の負荷バランシング・アルゴリズムは、平均実行キュー長さが実際のプロセッサ負荷を必ずしも正確に反映するとは限らないため、最適なバランスをとるまでに至っていない。
【００１２】
そのため、先行技術の欠点を克服するプロセッサの負荷バランシング方法が必要である。
【課題を解決するための手段】
【００１３】
簡単に言えば、請求する発明によると、複数のタスクをネットワーク内の複数の処理ノードに分散するコンピュータ実装方法は、複数のタスクに関してタスクのプロセッサ消費量値を計算するステップと、複数のノードに関してノードのプロセッサ消費量測定値を計算するステップと、複数のノードに関して、最適なノードのプロセッサ消費量を示すノードのプロセッサ消費量目標値を計算するステップと、ノードｉのノードのプロセッサ消費量測定値とノードｉのノードのプロセッサ消費量目標値との差として負荷指数値を計算するステップと、各ノードの負荷指数の計算値が実質的にゼロになるように、プロセッサの作業負荷をノード間でバランスをとるようタスクをノード間に分散するステップとを含む。
【００１４】
方法は多次元バランシング・マトリクスをさらに具体化し、マトリクスの各次元が様々なプロセッサのタイプに対応するノードを表し、各セルが次のステップに従って、多数のノードに割り当てられるタスクを表す。すなわち、負荷指数計算値を最も高い負荷指数値から最も低い負荷指数値の順に並べ替えるステップと、並べ替えた負荷指数値に従ってマトリクスにタスクを割り振るステップと、ノード間のプロセッサ作業負荷バランスを表すようにタスクをセルに再配列するステップと、マトリクス表示に従ってタスクをプロセッサに分散するステップである。
【発明の効果】
【００１５】
本方法は多次元バランシング・マトリクスの拡張をさらに具体化し、各次元は次のステップに従い、様々なプロセッサのタイプの多数のノードを表すことができる。すなわち、所定の利用ルールに従って、プロセッサの作業負荷をあるタイプのノードから別のタイプのノードに自由に移動できるが、逆方向には移動できないように、タスクをセルに再配列するステップである。
【発明を実施するための最良の形態】
【００１６】
本発明のある実施例によると、方法はプロセッサ・ネットワーク内にあるアフィニティ・ノードと呼ばれるプロセッサ群のセット全体にシステム・プロセッサの総消費量の負荷バランシングを行う。方法は、精密に測定したアフィニティ・ノードＣＰＵ消費量とタスクあたりのＣＰＵ消費量データを使用するアルゴリズムを採用する。このアルゴリズムは平均実行キュー長さに伴う欠陥を回避するために実際のタスクあたりのＣＰＵ消費量データとノードあたりのＣＰＵ消費量データを使用するため、平均タスク実行キュー長さ（平均実行キュー長さとしても知られる）を使用する周知の負荷バランシング・アルゴリズムを改善したものである。
グリーディ・負荷バランシング・アルゴリズム
【００１７】
負荷バランシングの目標を達成するために、本発明のある実施例によるアルゴリズムは、最大負荷（最もビジーな）アフィニティ・ノードから、最小負荷（最もアイドルな）アフィニティ・ノードに、移動するタスクがなくなってシステムが目標に近づくまで、タスクを繰返し移動する「グリーディ」（Ｇｒｅｅｄｙ）アプローチを採用する。グリーディ・アルゴリズムは科学および数学の分野に存在し、段階的な問題解決アプローチが必要なときによく使われる。グリーディ・アルゴリズムとはうまく付けられた名前であり、それはその時点で移動するのが最善と思われるものに基づいてタスクを移動するかしないかを決定するからであるが、考えられうるすべての移動を同時に考えたときにはそれが最終的に最善の決定になることもあればならないこともある。この欠点にも関わらず、グリーディ・アルゴリズムがよく使われるのは、考えられうるすべての移動を同時に列挙して、バランシングの目標を達成するのに絶対的に最善の移動セットを見つけようと試みるのは計算上実行不可能だからである。プロセッサの負荷バランシングに適用されるグリーディ・アルゴリズムは（グリーディ・アフィニティ・負荷バランシング・アルゴリズム）次の入力をとる。１）アフィニティ・ノードのリスト、その容量、およびそのノードのプロセッサ消費量測定値、および２）タスク、そのアフィニティ、およびそのタスクあたりのプロセッサ消費量の測定値。このアルゴリズムは図１に関して述べるアルゴリズムとは異なり、平均実行キュー長さの代わりに、各ノードと各タスクの実際のＣＰＵ消費量を考慮する。グリーディ・アフィニティ・アルゴリズムの出力は、システム・プロセッサの総消費量がアフィニティ・ノードのすべてにその容量に比例して分散するような、タスクのアフィニティ値の再割り当てである。
【００１８】
グリーディ・アフィニティ・負荷バランシング・アルゴリズムは次のような特徴を有する。
ａ）効率性：バランシングに必要な計算は非常に単純で、各タスクは最大で１回移動する。
ｂ）スラッシングの回避：タスクがあるアフィニティ・ノードから別のアフィニティ・ノードに連続的なバランシングの実行で絶えず移動する状況において、ＣＰＵのスラッシングが回避される。
ｃ）非均一性：アフィニティ・ノードは異なるタイプのものにでき（すなわち、ＣＰＵのタイプが異なる）、各タスクは２以上のタイプのアフィニティ・ノードでＣＰＵ消費量を有することができる。
ｄ）非対称バランシング：異なるタイプのアフィニティ・ノード間におけるバランシングは非対称でもよい。すなわち、負荷はあるタイプのアフィニティ・ノードから別のタイプのアフィニティ・ノードに自由に移動できるが、逆はできない。
ｅ）フィードバック：負荷バランシングと消費量測定作業を調整するＣＰＵ消費量モニタリング・メカニズムにフィードバックを提供する。
【００１９】
システムがその負荷バランシング目標にどれだけ近いかを定量化するために、ある単純な計算を行い、これらの計算結果を負荷バランサ１５０に報告する、またはその他同種のメカニズムが分散プロセッサ・ネットワーク内のプロセッサ間における負荷バランシングを調整する。最初の計算は、各アフィニティ・ノードｉについて、負荷指数（ｌｉ）を計算することである。ｌｉはノードｉのアフィニティ・ノードＣＰＵ消費量測定値（ｃｉ）とノードｉのアフィニティ・ノードＣＰＵ消費量目標値（ｔｉ）との差である。この計算は、次のように表すことができる。
【数１】
0005466354.tif 000002
【００２０】
上記式で、ｔｉは総システムＣＰＵ消費量をアフィニティ・ノード全部にその容量に比例して分散した場合の、あるアフィニティ・ノードの消費分である。あるノードｉのｔｉは次のように計算する。
１）全ノードのアフィニティ・ノードＣＰＵ消費量測定値ｃｉの総計と、全ノードのアフィニティ・ノード容量ｐｉの総計を出す。
２）ｃｉの総計をｐｉの総計で割る。
３）その商にあるノードｉのアフィニティ・ノード容量ｐｉを掛ける。
この計算は、次のように表すことができる。
【数２】
0005466354.tif 000003
上記式で、ｐｉはアフィニティ・ノード容量である。全アフィニティ・ノードの容量が同じ場合、アフィニティ・ノードＣＰＵ消費量目標値は、単純に全アフィニティ・ノードを平均した総システムＣＰＵ消費量となることに留意する。ｌｉは、アフィニティ・ノードにどれくらい「負荷」がかかっているかを測定する。ｌｉが高いほどアフィニティ・ノードの負荷は大きくなる。ｌｉはマイナスになりうることに留意する。マイナス値はアフィニティ・ノードが十分に利用されていないことを意味する。そのため、グリーディ・アフィニティ・負荷バランシング・アルゴリズムの目標は、全アフィニティ・ノードのｌｉをできるだけゼロに近づけることである。ゼロは完璧にバランスがとれていることを表す。アフィニティ・ノードＣＰＵ消費量の「開き」、すなわち全アフィニティ・ノードのｌｉがゼロである目標状態へのシステム全体の距離を測定するために、負荷指数偏差ｄを次のように計算する。
【数３】
0005466354.tif 000004
上記式で、ｎはアフィニティ・ノードの数である。全アフィニティ・ノードの容量が同じ場合、ｄはよく知られる標準偏差である。グリーディ・アフィニティ・バランシング・アルゴリズムの別の目的は、ｄがゼロにできるだけ近くなるようにｄを減少させることである。タスクがあるアフィニティ・ノードから別のアフィニティ・ノードに移動したときのｄの変化を把握するために、次の式を計算する。
【数４】
0005466354.tif 000005
上記式で、ｖ＝ｄ２は負荷指数の分散であり、添字１および２は、それぞれタスクを移動する前と移動した後の値を表す。ｄ１＞０かつｄ２＞０であるから、ｖ２−ｖ１＜０の場合、ｄ２−ｄ１＜１になる。すなわち、タスクを移動して負荷指数の分散が小さくなる場合、負荷指数の偏差も小さくなる。また、ＣＰＵ消費量がｗのタスクをアフィニティ・ノードｉからｊに移動する場合、次のようになる。
【数５】
0005466354.tif 000006
単純な数学で、次の式を導ける。
【数６】
0005466354.tif 000007
ｗ＞０かつｎ＞０であるから、ｗ＋ｌｊ−ｌｉ＜０の場合、ｖ２−ｖ１＜０になり、従ってｄ２−ｄ１＜０を意味する。そのため、タスクをアフィニティ・ノードｉからｊに移動してシステムがそのバランシング目標に近づくかどうかを判断するには、次の不等式を点検すればよい。
【数７】
0005466354.tif 000008
不等式が成り立つ場合、移動するとシステムはそのバランシング目標に近づき、成り立たなければ近づかない。
【００２１】
図３のフローチャートを参照すると、グリーディ・アフィニティ・バランシング・アルゴリズムのロジックは次のように進行する。ステップ３１０で、バランサ１５０はシステム内の全アフィニティ・ノードのリストＮを準備する。ステップ３２０で、２以上のアフィニティ・ノードがあるかどうかの判定を行わなければならない。アフィニティ・ノードが１つしかない場合、ノード間で負荷バランシングをする必要はない。ただし、システムが２以上のアフィニティ・ノードを包含する場合、処理はステップ３３０に進んで、各ノードｉのｌｉを求める。各ノードのｌｉを計算したら、負荷指数値ｌＳが最も高いノードＳを特定しなければならない。加えて、負荷指数値ｌＴが最も低いノードＴも特定しなければならない。アフィニティＳを有する全タスクのリストＭを準備する。
【００２２】
ステップ３４０に進んで、リストＭに問い合わせる。Ｍがゼロに等しい場合（すなわち、アフィニティＳを有するタスクがない）、ステップ３９０でノードＳは全ノードのリストＮから削除され、ステップ３２０の処理に戻る。そうでなければ、アフィニティＳを有する全タスクのリストＭから、最もＣＰＵを消費するタスクＷ（そのＣＰＵ消費量はｗである）を探し、さらにそれをＭから（１度だけ移動するように）削除する。次のステップ３６０で、ｗ＋ｌＴ−ｌＳ値を計算する。この値がゼロ未満の場合、タスクをＳからＴに移動するとシステムのバランスが改善する。そのため、処理はステップ３７０に進んで、Ｗのアフィニティを（ＳからＴに）再割り当てする。ゼロ未満でなければ、タスクをＳからＴに移動しても改善せず、システムのバランスは一層悪くなるであろう。そのため、このタスクは無視して、ステップ３４０に戻り、リストＭから次に大きくＣＰＵを消費するタスクを選ぶ。
【００２３】
次のステップ３８０で、再びＭに問い合わせをして、ゼロまで減少した（アフィニティＳを有するタスクがもうない）かどうかを判定する。もしそうであれば、ステップ３９０でアフィニティ・ノードのリストＮからＳを削除して、ステップ３２０に進んで処理すべきノードが残っているかどうかを判定する。そうではなく、Ｍがゼロより大きければ（すなわち、アフィニティＳを有するタスクが少なくとも１つは残っている）、ステップ３２０に戻るが、リストＮからＳは削除しない。アフィニティ・ノードのリストが１に減少するまでこのようにプロセスを続ける。
【００２４】
図３の処理の擬似コードは次のようになる。
Ｎ＝アフィニティ・ノードのリストとする
（Ｎが２以上のアフィニティ・ノードを有する）場合
｛
最も高い負荷指数値ｌＳのアフィニティ・ノードＳを求める
最も低い負荷指数値ｌＴのアフィニティ・ノードＴを求める
Ｍ＝アフィニティＳを有するタスクのリストとする
（Ｍが空ではない）場合
｛
Ｍの中で最もＣＰＵを消費するタスクＷを求める
ＭからＷを削除する
（ｗ＋ｌＴ−ｌＳ＜０）の場合
｛
ＴになるようにＷのアフィニティを再割り当てする
改行
｝
｝
（Ｍが空）の場合、ＮからＳを削除する
｝
【００２５】
本質的には、図３のフローチャートに描かれるアルゴリズムは、移動すると負荷指数の偏差が小さくなる場合にのみ、最もＣＰＵを消費するタスクＷを、最大負荷アフィニティ・ノードＳから最小負荷アフィニティ・ノードＴに繰返し移動する。移動すると負荷指数の偏差が小さくなるかどうかを判定する条件、ｗ＋ｌＴ−ｌＳ＜０は、非常に単純で、非常に迅速に計算できる。加えて、バランサ１５０自体が負う計算のオーバーヘッドを減らすために、各タスクは１度だけ移動する。タスクを移動する度に、最大負荷アフィニティ・ノードＳと最小負荷アフィニティ・ノードＴが変わることに留意する。そのため、アルゴリズムはそのパラメータを絶えず更新しなければならない。アフィニティ・ノードの全タスクを考慮したら、そのアフィニティ・ノードは負荷バランシングに参加するアフィニティ・ノードＮのリストから削除する。リストＮに残るアフィニティ・ノードが１つだけになったら、アルゴリズムは終了する。図１に示すバランサ１５０は、上記ステップを実行するロジックの単なる例であることは理解するべきである。当業者には、本発明の主旨および範囲内で他の例も可能であることは認識されるであろう。
【００２６】
負荷バランシング・アルゴリズムの重要な特徴は、ＣＰＵのスラッシングを回避することである。ＣＰＵのスラッシングは、タスクがあるアフィニティ・ノードから別のアフィニティ・ノードに連続したバランシングの実行で繰返し移動すると起こる。実行キュー長さベースのバランシング・アルゴリズムを使って、アルゴリズムが実行キュー長さのバランスを厳しくとろうと試みると（すなわち、個々の実行キュー長さをすべて等しくしようとする）、ＣＰＵのスラッシングが起こりうる。ＣＰＵのスラッシングを回避する１つの方法が、平均的なシステムの実行キュー長さからの個々の実行キュー長さの誤差の許容差を認めることである。グリーディ・アフィニティ・負荷バランシング・アルゴリズムでも、図４、５、および６の例に示すようにＣＰＵのスラッシングは起こりうる。
【００２７】
２つのアフィニティ・ノードＳ４４０およびＴ４６０（単純にするために、各ノードの容量は等しくなっている）、３つのタスクｉ４１０、ｊ４２０、およびｋ４３０があり、各タスクは各々ほぼ同じＣＰＵ処理量、すなわち１０％を消費すると仮定する。タスクのうちの２つ、たとえばｉをＳに、ｊをＴに割り当てた後、３番目のタスクｋはＳまたはＴのいずれにも割り当てることができる。図４に示すように、ｋをＳに割り当てると仮定する。ここで、次にバランシング・アルゴリズムを実行したときに、ｊのＣＰＵ消費量が１０％から９％にわずかに変化し、ｋのＣＰＵ消費量も１０％から１１％にわずかに変化したとする。すると、図５に示すように、ノードＳにはタスクｋ＝１１％とｉ＝１０％、ノードＴにはタスクｊ＝９％が割り当てられる。ノードＳとＴの平均ＣＰＵ消費量は（（１１％＋１０％）＋９％）／２＝１５％となる。Ｓの負荷指数は（１１％＋１０％）−１５％＝６％で、ノードＴの負荷指数は９％−１５％＝−６％となることに留意する。
【００２８】
バランサ１５０がタスクｋをノードＳからノードＴに移動させたとすると、１１％−６％−６％＝−１％＜０となる。そのため、移動すると負荷指数の偏差が小さくなり、容認される（図５の破線の矢印で示す）。それで今度は、ノードＳにはタスクｉ＝１０％、ノードＴにはタスクｋ＝１１％およびｊ＝９％となる。次にバランシング・アルゴリズムを実行したときに、ｉのＣＰＵ消費量が１０％から９％にわずかに変化し、ＪのＣＰＵ消費量も９％から１０％にわずかに変化したとする。今度の状況は最後にバランシング・アルゴリズムを実行したときの状況（図５に示す）と正反対であることが容易に分かる。ここで、タスクｋをノードＴからＳに戻す（図６の破線の矢印で示す）。この「ピンポン」効果（ＣＰＵのスラッシング）はあらゆる周知の負荷バランシングの状況で起こりうることであり、無制限に起こり続きうる。
【００２９】
グリーディ・アフィニティ・負荷バランシング・アルゴリズムにおけるＣＰＵのスラッシングの理由は、タスクを移動させる条件ｗ＋ｌＴ−ｌＳ＜０がタスクのＣＰＵ消費量の小さな変動に敏感に反応するため、すなわち、減少の量がいかに小さくても、負荷指数の偏差が小さくなるときは必ずタスクの再割り当てを行うためであることは明らかである。ＣＰＵのスラッシングを回避するには、タスクを移動させる条件を修正する必要がある。グリーディ・アフィニティ・負荷バランシング・アルゴリズムはタスクを移動させる条件を、計算に閾値を加えて修正する。新たな閾値条件は次のとおりである。
【数８】
0005466354.tif 000009
【００３０】
換言すると、移動すると負荷指数の偏差がある量Ｔ（閾値の量）を超えて小さくなる場合に限り、タスクを移動させる。Ｔはバランシング・アルゴリズムのパラメータとすることができ、作業負荷特性によって調整できる。修正条件を使うと、グリーディ・アフィニティ・負荷バランシング・アルゴリズムは、タスクのＣＰＵ消費量の変動がアフィニティ・ノード間の負荷の不均衡が大幅に生じるほど大きく、そのため移動すると負荷指数の偏差が有意な量で小さくなる場合に限り、タスクを移動する。
【００３１】
標準的な汎用ＣＰＵに加えて、システムは、ある一定のタイプの処理に特化したＣＰＵである専用ＣＰＵを有することがある。たとえば、ＩＢＭのｚＳｅｒｉｅｓ  Ａｐｐｌｉｃａｔｉｏｎ  Ａｓｓｉｓｔ  Ｐｒｏｃｅｓｓｏｒ（ｚＡＡＰ）はＪａｖａアプリケーションだけを実行する。ｚＡＡＰなどの専用ＣＰＵの利点は、その演算コストが汎用ＣＰＵよりはるかに低いことである。たとえば、ＩＢＭのＷｅｂＳｐｈｅｒｅなど、Ｊａｖａの作業負荷の大きいカスタマは、ｚＡＡＰ上でそのＪａｖａアプリケーションを実行することによってコストを大幅に節約できる。現在異なるタイプのアフィニティ・ノードがあり、すなわち、異なるタイプのＣＰＵを包含するアフィニティ・ノードがあり、アフィニティ・ノードを各タイプで独立してバランスをとらなければならない、あるいは多数のタイプのアフィニティ・ノードを集合的にバランスをとらなければならないため、専用ＣＰＵは負荷バランシング・アルゴリズムに新たな課題をもたらす。ここでは、タスクは多数のアフィニティを有しうる、すなわち異なるタイプのアフィニティ・ノードで実行し、異なるタイプのＣＰＵリソースを消費しうるのである。あるタスクを移動すると、多数のアフィニティ・ノードの負荷が変化しうる。
【００３２】
ある実施例では、グリーディ・アフィニティ・負荷バランシング・アルゴリズムは、異なるタイプのアフィニティ・ノードをサポートするように拡張する。基本概念は、異なるタイプのアフィニティ・ノードと多数のアフィニティを有するタスクを表すためにバランシング・マトリクスを使うことである。バランシング・マトリクスはあらゆる次元にでき、各次元は１タイプのアフィニティ・ノードを表す。バランシング・マトリクスの各セルは対応するセルの次元のアフィニティを有するタスクを表す。一般性を失うことなく単純化するために、この概念を例証するにあたって、２次元のバランシング・マトリクスの例を使用する（すなわち、２種類のアフィニティ・ノード）。
２次元のバランシング・マトリクス
【表１】
0005466354.tif 000010
【００３３】
表１のバランシング・マトリクスは、２種類のアフィニティ・ノード、標準ＣＰＵタイプ（Ｓ）ノードとｚＡＡＰ  ＣＰＵタイプ（Ｚ）ノードを示す。標準アフィニティ・ノードはＳ１、Ｓ２、Ｓ３の３つ、ｚＡＡＰアフィニティ・ノードはＺ１、Ｚ２、Ｚ３、Ｚ４の４つある。各セルの数字、たとえばセル［Ｓ１、Ｚ２］の９は、アフィニティ・ノードＳ１およびＺ２の両方でＣＰＵリソースを消費し、そのためアフィニティ［Ｓ１、Ｚ２］を有するタスクが９個あることを意味する。数字の書かれていないセルは、そのセルを表す両アフィニティ・ノードでＣＰＵリソースを消費したタスクがないことを意味する。たとえば、アフィニティ・ノードＳ１およびＺ１の両方でＣＰＵリソースを消費したタスクはない。グリーディ・アフィニティ・バランシングアルゴリズムをバランシング・マトリクスに適合させるために、以下の手順をとるべきである。
【００３４】
バランシング・マトリクスの行と列を負荷指数が最も高い値から負荷指数が最も低い値の順に並べ替える。たとえば、上記バランシング・マトリクスはすでに並べ替えが行われていると仮定する。そのため、Ｓ１は負荷指数が最も高い標準アフィニティ・ノードであり、Ｓ３は負荷指数が最も低いノードであることが分かる。同様に、Ｚ１は負荷指数値が最も高いｚＡＡＰアフィニティ・ノードであり、Ｚ４は負荷指数値が最も低いｚＡＡＰアフィニティ・ノードである。
【００３５】
両タイプのアフィニティ・ノードのバランスをとるために、まず一方のタイプのバランスをとってから、他方のタイプのバランスをとる。たとえば、標準アフィニティ・ノードのバランスをとる場合、最大負荷Ｓ１で最も標準ＣＰＵを消費するタスクを求めるが、それはアフィニティ［Ｓ１、Ｚ２］を有する９個のタスクのうちどれか、またはアフィニティ［Ｓ１、Ｚ４］を有する１１個のタスクのうちどれかである。前者だと仮定すると、おそらくこのタスクはＳ３に移動できる、すなわち、［Ｓ３、Ｚ２］として再割り当てできる。しかし、それを行う前に、このタスクはｚＡＡＰ消費量も必要とするため、アルゴリズムはタスクが代わりに［Ｓ３、Ｚ４］に再割り当てできるかどうかを判定しなければならない。この再割り当てはＳ１からＳ３に、およびＺ２からＺ４に負荷を同時にバランスをとるため、こちらの方が優れた再割り当てである。標準ノードのバランスをとった後、ｚＡＡＰアフィニティ・ノードのバランスをとるために同じ手順を行う。たとえば、最もｚＡＡＰ  ＣＰＵを消費するタスクが最大負荷Ｚ１にアフィニティ［Ｓ２、Ｚ１］を有する８個のタスクのうちどれかだと仮定する。アルゴリズムは、［Ｓ２、Ｚ１］から［Ｓ３、Ｚ４］に移動できるかどうかを判定する。できない場合、タスクは［Ｓ２、Ｚ１］から［Ｓ２、Ｚ４］に移動する。２つのタスクを移動した後のバランシング・マトリクスの中間ステップを示す表２を参照すること。
２タスクを移動した後の二次元のバランシング・マトリクス
【表２】
0005466354.tif 000011
【００３６】
アフィニティ・ノードにもうタスクが残っていなければ、そのアフィニティ・ノードを表すバランシング・マトリクスの行または列をマトリクスから削除する。たとえば、アフィニティ［Ｓ１、＊］を有するタスクがもう残っていない場合、バランシング・マトリクスのＳ１の行を削除し、バランシング・マトリクスは２行×４列に縮小する。同様に、アフィニティ［＊、Ｚ１］を有するタスクがもう残っていない場合、バランシング・マトリクスのＺ１の列を削除し、バランシング・マトリクスは２行×３列に縮小する。バランシング・マトリクスが１セルまで縮小すると、アルゴリズムは終了する。
【００３７】
示してきたように、異なるタイプのアフィニティ・ノード間のバランシングを行うことはできるが、バランシングが非対称になる場合もある。すなわち、作業負荷はあるタイプのアフィニティ・ノードＺから別のノードＳには自由に移動できるが、逆はできない。これは、標準プロセッサＳはどのタイプのコードも実行できるが、プロセッサＺは専用プロセッサであり、Ｊａｖａなど一定のタイプのコードしか実行できないからである。そのため、特殊プロセッサの作業負荷は標準プロセッサに移動できるが、標準プロセッサの作業負荷が特殊プロセッサに移動できるとは必ずしもいえない。
【００３８】
ある実施例において、グリーディ・アフィニティ・負荷バランシング・アルゴリズムが、当該非対称バランシングをサポートするようさらに拡張される。これは、次元の各々が２以上のタイプのアフィニティ・ノードを表すことができるようにバランシング・マトリクスを拡張して行う。新しいバランシング・マトリクスの例を表３に示す。
非対称バランシング・サポート付き２次元のバランシング・マトリクス
【表３】
0005466354.tif 000012
【００３９】
上記新たなバランシング・マトリクスでは、ｚＡＡＰアフィニティ・ノードＺ１〜Ｚ４を表す列が、標準アフィニティ・ノードＳ１〜Ｓ３を表す列を追加されて拡張していることが分かる。これは、ｚＡＡＰアフィニティ・ノードのバランスをとる場合、標準アフィニティ・ノードをｚＡＡＰアフィニティ・ノードのように扱えることを意味する。こうして、負荷をｚＡＡＰアフィニティ・ノードから標準アフィニティ・ノードに移動できる。たとえば、最もｚＡＡＰ  ＣＰＵを消費するタスクがアフィニティ［Ｓ２、Ｚ１］を有する８個のタスクのどれかにある場合、上記説明した考えられうる移動に加えて、ここではさらに２つの移動が考えられうる。すなわち、［Ｓ２、Ｚ１］から［Ｓ２、Ｓ２］（破線）で、これはタスクのｚＡＡＰ  ＣＰＵ消費量をＺ１からＳ２に効果的に移動する。または、これが可能でない場合（すなわち、Ｓ２に十分な空きがない場合）、［Ｓ２、Ｚ１］から［Ｓ３、Ｓ３］（点線）に試行でき、これはタスクの標準ＣＰＵとｚＡＡＰ  ＣＰＵの消費量の両方を標準アフィニティ・ノードＳ３に効果的に移動する。Ｓ３をｚＡＡＰ  ＣＰＵ消費量を受け取る対象として選んだのは、それが最小負荷標準アフィニティ・ノードだからであることに留意する。標準アフィニティ・ノードのバランスをとる場合、標準ＣＰＵ消費量はｚＡＡＰアフィニティ・ノードには自由に移動できないため、なおも表１の元の非拡張バランシング・マトリクスの行Ｓ１〜Ｓ３しか使えない。
【００４０】
上記例のように精密に測定したＣＰＵ消費量データを使う負荷バランシング・アルゴリズムの効果は、ＣＰＵ消費量データの質にかかっていることは明らかである。負荷バランシング・アルゴリズムに著しい影響を有するＣＰＵ消費量データの質の一面がデータの精度で、ＣＰＵ消費量データを得ることのできる詳細レベルである。たとえば、ｚ／ＯＳでは、アプリケーションは、アプリケーション・コードおよびデータを収容する連続した仮想メモリ領域である、いわゆるアドレス空間によって表される。アドレス空間内には、タスク制御ブロック（ＴＣＢ）と呼ばれる一または複数の実行ユニットがありうる。ＵＮＩＸなどの他のオペレーティング・システムでは、アドレス空間とＴＣＢは、それぞれＵＮＩＸプロセスおよびスレッドと同様に高レベルである。ｚ／ＯＳは個々のＴＣＢのＣＰＵ消費量を測定する内蔵メカニズムを有するが、デフォルトでは、個々のＴＣＢをモニタリングするオーバーヘッドが高いため、アドレス空間の総計ＣＰＵ消費量しか測定しない。より粗いアドレス空間の総計ＣＰＵ消費量しか使わなければ、負荷バランシング・アルゴリズムは効果が減る。そのため、バランサ１５０とＣＰＵ消費量測定メカニズムを互いに調和させて、良好な負荷バランシングと低測定オーバーヘッドとの最善のトレードオフを達成する必要がある。
【００４１】
負荷指数の偏差を使用すると、グリーディ・アフィニティ・負荷バランシング・アルゴリズムはシステムが「どれくらい良好に」バランスがとれているかを簡単に測ることができる。バランサ１５０は負荷指数の偏差の閾値を使用し、それ未満であればシステムは十分にバランスがとれていると考える。同時に、バランサ１５０はバランシングの実行中に移動しなかったＣＰＵを消費する上位のアドレス空間のトラックもいくつか維持する。この情報はそれ以降の実行に役立つ。グリーディ・アフィニティ・負荷バランシング・アルゴリズムが負荷指数の偏差を閾値未満にできなければ、測定メカニズムに対して、追跡した「問題のある」アドレス空間（これらは通常、より上位のＣＰＵを消費するアドレス空間である）内における個々のＴＣＢのＣＰＵ消費量のモニタリングの開始を通知する。そのため、グリーディ・アフィニティ・負荷バランシング・アルゴリズムは必要な場合にだけ、追加のＣＰＵ消費量を測定するオーバーヘッドを負う。アルゴリズムが良好にシステムのバランスをとっている場合、ＣＰＵ消費量測定メカニズムに対して、ＴＣＢのモニタリングを停止し、それぞれのアドレス空間に戻ってＴＣＢを総計するよう通知する。
【００４２】
そのため、現在好適な実施例と考えられるものを説明してきたが、当業者には本発明の主旨の範囲内で他の変更も行えることは理解されるであろう。
【図面の簡単な説明】
【００４３】
【図１】周知の技術による負荷バランシング・システムの図である。
【図２】周知の技術による別の負荷バランシング・システムの図である。
【図３】本発明のある実施例による、グリーディ・アフィニティ・負荷バランシングの方法を示すフローチャートである。
【図４】本発明のある実施例による、負荷バランシング・システムにおけるタスク割り当ての図である。
【図５】本発明のある実施例による、負荷バランシング・システムにおけるタスク割り当ての図である。
【図６】本発明のある実施例による、負荷バランシング・システムにおけるタスク割り当ての図である。
【図１】
0005466354.tif 000013
【図２】
0005466354.tif 000014
【図３】
0005466354.tif 000015
【図４】
0005466354.tif 000016
【図５】
0005466354.tif 000017
【図６】
0005466354.tif 000018