(57)【要約】【課題】  ある種のタスクの発生／到着の増加による他種のタスクのレスポンスタイムの悪化を防ぎ、群集効果を抑制し、高速に負荷均衡を図ることで、レスポンスタイムを短縮する装置、及び方法の提供。【解決手段】  ノードグループ構築手段１２は、システム構成情報と事前に測定されたタスク−ノード特性とタスク受信手段１１によって測定されるタスク到着率と実行時性能測定手段１４によって測定されるノードの実行時性能情報とからノードグループを構成し、更に実行時に得られる負荷情報を用いて各ノードグループのサイズを適切な値に設定する。負荷情報管理手段３６は、精度の異なる情報から、負荷情報を再構成し、移送タスク決定手段３９は、ノード優先度割り当て手段３７が割り当てる優先度順に、一つのノードに対して一つ以上のタスクを移送することと、一つ以上のノードに、タスクを移送することを決定する。【選択図】  図１０
2005148911.tif 000002
【特許請求の範囲】
【請求項１】
複数のノードを含む計算機システムを対象とした負荷分散装置であって、
システムの構成情報と、システムの運用条件と、事前に測定されたタスク−ノード特性情報とを入力するシステム構成入力手段と、
システムに到着するタスクの種類を判別し、タスク到着率をタスクごとに測定するタスク受信手段と、
実行時にノードの実行性能情報を測定する実行性能測定手段と、
前記システムの構成情報と、前記システムの運用条件と、事前に測定された前記タスク−ノード特性と、実行時に測定される前記タスク到着率と、ノードの実行時性能情報とのうちの少なくとも一つに基づき、ノードグループを構成し、前記ノードグループ上で実行されるタスク種を決定するノードグループ構築手段と、
タスクを実行するノードを前記ノードグループより選択し、前記ノードに対してタスクを転送するタスク転送手段と、
を含む、ことを特徴とする負荷分散装置。
【請求項２】
タスクの転送先のノードにおける滞留タスク数が予め定められた所定数を超えないように、タスクをキューイングするキューイング手段（「グローバルキューイング手段」という）をさらに有する、ことを特徴とする請求項１記載の負荷分散装置。
【請求項３】
前記ノードグループ構築手段が、一つのノードグループに対して、前記システムの運用条件を満足するタスク種を対応させ、他のノードグループに対して前記システムの運用条件を満足しないタスク種を対応させる、ことを特徴とする請求項１又は２に記載の負荷分散装置。
【請求項４】
前記ノードグループ構築手段が、一つのノードグループ上で一種類のタスク処理が行なわれるようにノードグループを構成し、前記ノードグループと前記ノードグループに対応するタスク種とを関連付けて記憶管理する、ことを特徴とする請求項１又は２に記載の負荷分散装置。
【請求項５】
前記タスク−ノード特性情報は、前記タスク到着率とスループット、及び／又は、前記タスク到着率とレスポンスの特性情報を含む、ことを特徴とする請求項１記載の負荷分散装置。
【請求項６】
計算機システムを構成するノードにおいて、
タスク又はタスクの実行結果の送受信を行うタスク送受信手段と、
前記タスク送受信手段で受信したタスクをキューイングするキューイング手段（「ローカルキューイング手段」という）と、
負荷情報を共有する負荷情報共有手段と、
前記負荷情報共有手段が提供する他ノードの負荷情報に基づいて、どのタスクをどのノードに移送するかを決定し、前記タスク送受信手段にタスクの移送を依頼する負荷分散手段と、
実行を依頼されたタスクを処理し、前記タスクの実行結果を、前記ローカルキューイング手段に返すタスク実行手段と、
を含む、ことを特徴とするノード。
【請求項７】
前記負荷分散手段は、
負荷情報を管理する負荷情報管理手段と、
自ノードで実行すべきタスクの量を、動的に計算する均衡度計算手段と、
ノードに対して優先度を割り当てるノード優先度割り当て手段と、
優先度順に、負荷の移送対象のノードを選択し、選択したノードに移送するタスクの個数を決定する移送タスク決定手段と、
を含む、ことを特徴とする請求項６記載のノード。
【請求項８】
前記ノード優先度割り当て手段が、前記ノードに対する優先度の割り当てを、循環単調増加優先度割り当てにしたがって行う、こと特徴する請求項６又は７に記載のノード。
【請求項９】
前記負荷情報共有手段は、異なる精度を持つ負荷情報を共有し、
前記負荷分散手段の前記負荷情報管理手段は、単純空間精度補完を行い、
前記負荷分散手段の前記ノード優先度割り当て手段は、負荷情報の精度が高いノードに対してより高い優先度を割り当てる、ことを特徴とする、請求項６乃至８のいずれか一に記載のノード。
【請求項１０】
タスクの実行数別に、スループットを算出するためのレスポンスタイムテーブルを有し、
前記負荷分散手段の前記ローカルキューイング手段は、前記レスポンステーブルを参照して、同時に実行するタスク数を、動的に変化させる、ことを特徴とする請求項６乃至９のいずれか一に記載のノード。
【請求項１１】
スイッチング装置と、
請求項６乃至１０のいずれか一に記載のノードを複数備え、
前記複数のノードは、前記スイッチング装置に接続され、前記スイッチング装置を介して通信する、ことを特徴とする負荷分散システム。
【請求項１２】
請求項１乃至５のいずれか一に記載の負荷分散装置を備え、
請求項６乃至１０のいずれか一に記載のノードを複数備え、
複数の前記ノードはクラスタシステムを構成し、
前記負荷分散装置は、前記ノードに接続され、前記ノードグループの構成変更情報を、前記クラスタシステムを構成する前記ノードに通知し、
同一のノードグループに属するノード間で、負荷情報を共有する、ことを特徴とする負荷分散システム。
【請求項１３】
タスクは、タスク種毎に異なるノードグループで実行され、ノードグループ間でのタスクの移送は行われない、ことを特徴とする、請求項１２記載の負荷分散システム。
【請求項１４】
計算機システムを構成する複数のノードをノードグループに分け、どのノードグループでどのタスク種を実行させるかを決定し、その際、入力装置から得られるシステム構成情報、及び／又は、実行時の性能測定情報を用いて、各ノードグループに含まれるノードの数を可変に制御することで、所定の運用条件を満足するように、制御する手段と、
タスク種を実行するノードグループの中からノードを選択し、選択されたノードに対してタスクを転送する手段と、
を含む、ことを特徴とする負荷分散装置。
【請求項１５】
タスク処理要求を受け付け、タスクの種類を判別して、タスク到着率を測定する手段をさらに有する、ことを特徴とする請求項１４記載の負荷分散装置。
【請求項１６】
ノードグループを構築するノードをノードグループ毎に管理するためのノードグループ構成表と、
タスク種と、前記タスク種を実行するノードグループとの対応を記憶するタスク種−ノードグループ対応表と、
タスク到着率及び実行時のノードの性能測定データを管理する測定データ管理表と、
を備え、
前記ノードグループ構成表、及び、前記タスク種−ノードグループ対応表は、入力された運用条件と、タスク−ノード特性と、前記測定データ管理表の内容に基づき、更新される、ことを特徴とする請求項１４又は１５記載の負荷分散装置。
【請求項１７】
タスクの転送先のノードに滞留しているタスク数が予め定められた所定個数を超えないように、タスクをキューイングする手段をさらに有する、ことを特徴とする請求項１４記載の負荷分散装置。
【請求項１８】
複数のノードを有する計算機システムで負荷分散を行う方法において、
システムの構成情報と、事前に測定されたタスク−ノード特性と、タスク到着率と、ノードでの実行時の性能情報のうちの少なくとも一つに基づき、前記ノードからノードグループを構成するステップと、
実行時に得られる負荷情報を用いて、前記ノードグループのノードの数を適切な値に設定するステップを有する、ことを特徴とする負荷分散方法。
【請求項１９】
前記負荷分散装置が、計算機システムを構成する複数のノードをどのノードグループに分け、さらに、どのノードグループでどのタスク種を実行させるかを決定し、その際、入力装置から得られるシステム構成情報、及び／又は、測定された実行時の性能測定情報を用いて、前記ノードグループに含まれるノードの数を可変に制御することで、所定の運用条件を満足するように制御するステップと、
前記負荷分散装置が、所望のタスク種を実行するノードグループの中から一つのノードを選択するステップと、
前記負荷分散装置が、選択されたノードに対して前記タスクを転送するステップと、
を含む、ことを特徴とする負荷分散方法。
【請求項２０】
前記負荷分散装置が、タスク処理要求を受け付け、タスクの種類を判別して、タスク到着率を測定するステップをさらに有する、ことを特徴とする請求項１９記載の負荷分散方法。
【請求項２１】
前記負荷分散装置が、前記ノードに滞留しているタスク数が予め定められた所定個数を超えないように、タスクをキューイングするステップをさらに有する、ことを特徴とする請求項１９記載の負荷分散方法。
【請求項２２】
複数のノードが計算機システムを構成するシステムの負荷分散方法において、
一のノードは、他ノードの負荷情報に基づいて、負荷の移送対象のノードを決定し、前記ノードにタスクを移送することで、負荷分散処理を行うステップを含む、ことを特徴とする負荷分散方法。
【請求項２３】
前記負荷分散処理を行うステップが、
自ノードで実行すべきタスクの量を計算するステップと、
ノードに対して優先度を割り当てるステップと、
優先度順に、負荷の移送対象のノードを選択し、該ノードに移送するタスクの個数を決定するステップと、
を有する、ことを特徴とする請求項２２記載の負荷分散方法。
【請求項２４】
前記ノードに割り当てる優先度は、循環単調増加優先度割り当てにしたがって行われる、ことを特徴とする請求項２３記載の負荷分散方法。
【請求項２５】
負荷情報を共有する負荷情報共有部で、異なる精度を持つ負荷情報を共有し、
他ノードから送られる負荷情報の値と精度から、前記負荷情報を再構築するステップを含む、ことを特徴とする、請求項２２乃至２４のいずれか一に記載の負荷分散方法。
【請求項２６】
負荷情報の精度が高いノードに対して、より高い優先度を割り当てるステップを含む、ことを特徴とする請求項２５記載の負荷分散方法。
【請求項２７】
タスクのレスポンスタイムを測定し測定結果を、タスクの実行数別にスループットを算出するためのレスポンスタイムテーブルに反映させるステップと、
前記レスポンスタイムテーブルを参照して、同時に実行するタスクの数を変化させるステップを有する、ことを特徴とする請求項２２又は２３に記載の負荷分散方法。
【請求項２８】
自ノードの負荷が予め定められた閾値を越えた時に、過去に、負荷の移送判断を行ったノードの負荷情報と、現在負荷の移送判断を行っているノードの負荷情報とに基づき、負荷の移送判断を行うステップを有する、ことを特徴とする請求項２２又は２３記載の負荷分散方法。
【請求項２９】
負荷の移送対象の一つのノードに対して、一つ以上のタスクを移送し、一つ以上のノードにタスクを移送することを決定することで、負荷を均衡させるステップを有する、ことを特徴とする請求項２２又は２３記載の負荷分散方法。
【請求項３０】
タスクを受信するステップと、
受信したタスクをキューイングし、その際、タスクの実行結果の返信先を判別可能に記録しておくステップと、
前記キューイングされているタスクについて、キューの先頭から所定数のタスクを除いて、どのノードで実行すればよいかを決定するステップと、
タスクを、前記決定された他のノードに移送するステップと、
他のノードに移送されなかった、前記キューの先頭から所定数のタスクを実行するステップと、
他ノードに移送したタスクの実行結果が返ってきている場合に、前記実行結果を受信するステップと、
自ノードでタスクの実行結果を受け付けるか、他ノードに移送したタスクの実行結果が受信されている場合、対応するタスクを前記キューから外し前記タスクの実行結果を返信先に送信するステップと、
を含む、ことを特徴とする請求項２２又は２３記載の負荷分散方法。
【請求項３１】
前記負荷分散処理を行うステップが、
（Ａ１）許容できる自ノードの負荷の上限である閾値を算出するステップと、
（Ａ２）他のノードに対して優先度を割り当てるステップと、
（Ａ３）自ノードで移送したい負荷の量（オーバ）を算出し、負荷の移送対象ノードが受け入れ可能な負荷の量（アンダー）を初期化するステップと、
（Ａ４）前記移送したい負荷の量（オーバ）が正値であるか判定し、前記移送したい負荷の量（オーバ）が負又は零である場合には、負荷分散を行わずに終了するステップと、
（Ａ５）前記移送したい負荷の量（オーバ）が正値であれば、優先度の高いノードから順に、負荷の移送に関する判断を行うノードを選択するステップと、
（Ａ６）対象となる全てのノードに対して負荷の移送に関する判断が行われているか判定し、対象となる全てのノードに対して負荷の移送に関する判断が行われている場合、負荷分散を終了するステップと、
（Ａ７）負荷の移送に関し判断が行われていないノードが存在する場合、前記負荷の移送対象ノードが受け入れ可能な負荷の量（アンダー）を更新するステップと、
（Ａ８）前記負荷の移送対象ノードが受け入れ可能な負荷の量（アンダー）が所定量以上でなければ、ステップ（Ａ５）に戻り、負荷の移送対象ノードを変更するステップと、
（Ａ９）前記負荷の移送対象ノードが受け入れ可能な負荷の量（アンダー）が所定量以上であれば、負荷を所定単位分だけ、負荷の移送対象ノードに移送することを決定するステップと、
（Ａ１０）自ノードの負荷情報を、自ノードが持つ移送対象ノードの負荷情報を更新し、負荷分散を終了するステップと、
を含む、ことを特徴とする、請求項２２記載の負荷分散方法。
【請求項３２】
前記負荷分散処理を行うステップが、
（Ａ１）許容できる自ノードの負荷の上限である閾値を算出するステップと、
（Ａ２）他のノードに対して優先度を割り当てるステップと、
（Ａ３）自ノードで移送したい負荷の量（オーバ）を算出し、負荷の移送対象ノードが受け入れ可能な負荷の量（アンダー）を初期化するステップと、
（Ａ４）前記移送したい負荷の量（オーバ）が正値であるか判定し、前記移送したい負荷の量（オーバ）が負又は零である場合には、負荷分散を行わずに終了するステップと、
（Ａ５）前記移送したい負荷の量（オーバ）が正値であれば、優先度の高いノードから順に、負荷の移送に関する判断を行うノードを選択するステップと、
（Ａ６）対象となる全てのノードに対して負荷の移送に関する判断が行われているか判定し、対象となる全てのノードに対して負荷の移送に関する判断が行われている場合、負荷分散を終了するステップと、
（Ａ７）負荷の移送に関し判断が行われていないノードが存在する場合、前記負荷の移送対象ノードが受け入れ可能な負荷の量（アンダー）を更新するステップと、
（Ａ８）前記負荷の移送対象ノードが受け入れ可能な負荷の量（アンダー）が所定量以上でなければ、ステップ（Ａ５）に戻り、負荷の移送対象ノードを変更するステップと、
（Ｂ１）自ノードで移送したい負荷の量（オーバ）が、負荷の移送対象ノードが受け入れ可能な負荷の量（アンダー）以下であるか否か判定するステップと、
（Ｂ２）自ノードで移送したい負荷の量（オーバ）が、負荷の移送対象ノードが受け入れ可能な負荷の量（アンダー）以下である場合には、自ノードで移送したい負荷の量（オーバ）分の負荷を、負荷の移送対象ノードに移送することを決定するステップと、
（Ｂ３）自ノードの負荷情報と、自ノードが保持する移送対象ノードの負荷情報を更新し、負荷分散を終了するステップと、
（Ｂ４）自ノードで移送したい負荷の量（オーバ）が、負荷の移送対象ノードが受け入れ可能な負荷の量（アンダー）よりも大きい場合、負荷の移送対象ノードが受け入れ可能な負荷の量（アンダー）分の負荷を、負荷の移送対象ノードに移送することを決定するステップと、
（Ｂ５）自ノードの負荷情報と、自ノードが保持する負荷の移送対象ノードの負荷情報、自ノードで移送したい負荷の量（オーバ）と負荷の移送対象ノードが受け入れ可能な負荷の量（アンダー）を更新し、前記ステップ（Ａ５）へ進むステップと、
を含む、ことを特徴とする請求項２２記載の負荷分散方法。
【請求項３３】
（Ｃ１）タスクの実行の開始時刻を保持し、タスクの実行結果を受け取ると、現在時刻と前記開始時刻との差を求め、レスポンスタイムを求めるステップと、
（Ｃ２）前記レスポンスタイムテーブルにおけるレスポンスタイムの総和に、前記ステップＣ１で求めたレスポンスタイムを加算し、対応する測定個数を更新するステップと、
（Ｃ３）前記レスポンスタイムテーブルを参照して、レスポンスタイムの総和と測定個数から平均レスポンスタイムを求め、平均レスポンスタイムの値から望ましいタスクの実行数を求めるステップと、
（Ｃ４）同時に実行するタスク数の最大値を、前記タスクの実行数に基づき、更新するステップと、
をさらに有し、
同時に実行するタスク数別にレスポンスタイムを測定し、最大で、いくつのタスクを同時に実行するのが望ましいかを、動的に決定する、ことを特徴とする、請求項２７記載の負荷分散方法。
【請求項３４】
タスクは、タスク種毎に異なるノードグループで実行され、ノードグループ間でのタスクの移送が行われない、ことを特徴とする、請求項２２又は２３記載の負荷分散方法。
【請求項３５】
複数のノードを含む計算機システムを対象としたグローバル負荷分散装置を構成するコンピュータに、
システムの構成情報と、システムの運用条件と、事前に測定されたタスク−ノード特性とを入力するシステム構成入力処理と、
システムに到着するタスクの種類を判別し、タスク到着率をタスクごとに測定するタスク受信処理と、
実行時にノードの実行性能情報を測定する実行性能測定処理と、
前記システム構成情報と、前記システムの運用条件と、事前に測定された前記タスク−ノード特性と、実行時に測定される前記タスク到着率と、ノードの実行時性能情報と、を用いて、ノードグループを構成し、前記ノードグループ上で実行されるタスク種を決定するノードグループ構築処理と、
タスクを実行するノードを前記ノードグループより選択して、前記ノードに対してタスクを転送するタスク転送処理と、
を実行させるためのプログラム。
【請求項３６】
請求項３５記載のプログラムにおいて、
タスク転送先ノード上の滞留タスク数が予め定められた所定数を超えないように、タスクをキューに繋ぐ処理を、前記コンピュータに実行させるためのプログラム。
【請求項３７】
請求項３５又は３６記載のプログラムにおいて、
一つのノードグループに対して、運用条件を満足するタスク種を対応させ、他のノードグループに対して運用条件を満足しないタスク種を対応させる処理を含む前記ノードグループ構築処理を、前記コンピュータに実行させるためのプログラム。
【請求項３８】
請求項３５又は３６記載のプログラムにおいて、
一つのノードグループ上で一種類のタスク処理が行なわれるようにノードグループを構成する処理と、
前記ノードグループに対してタスク種の対応付けを行う処理と、
を含む前記ノードグループ構築処理を、前記コンピュータに実行させるためのプログラム。
【請求項３９】
計算機システムを構成するノードを構成するコンピュータに、
タスク又はタスクの実行結果の送受信を行うタスク送受信処理と、
前記タスク送受信手段で受信したタスクをキューに繋ぐキューイング処理と、
負荷情報を共有する負荷情報共有部が提供する他ノードの負荷情報に基づいて、どのタスクをどのノードに移送するかを決定し、前記タスク送受信処理にタスクの移送を依頼する負荷分散処理と、
実行を依頼されたタスクを処理し、前記タスクの実行結果を、前記ローカルキューイング手段に返すタスク実行処理と、
を実行させるためのプログラム。
【請求項４０】
請求項３９記載のプログラムにおいて、
負荷情報を管理する負荷情報管理処理と、
自ノードで実行すべきタスクの量を動的に計算する均衡度計算処理と、
ノードに対して優先度を割り当てるノード優先度割り当て処理と、
優先度順に、負荷の移送対象のノードを選択し、該ノードに移送するタスクの個数を決定する移送タスク決定処理と、
を含む前記負荷分散処理を、前記コンピュータに実行させるためのプログラム。
【請求項４１】
請求項４０記載のプログラムにおいて、
他ノードに割り当てる優先度を、循環単調増加優先度割り当てにしたがって行う前記ノード優先度割り当て処理を、前記コンピュータに実行させるためのプログラム。
【請求項４２】
請求項３９記載のプログラムにおいて、
前記負荷情報共有部は、異なる精度を持つ負荷情報を共有し、
他ノードから送られる負荷情報の値と精度とから、前記負荷情報を再構築する処理を、前記コンピュータに実行させるためのプログラム。
【請求項４３】
請求項３９記載のプログラムにおいて、
タスクの実行数別に、スループットを算出するためのレスポンスタイムテーブルを参照して、同時に実行するタスク数を、動的に変化させる処理を、前記コンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は負荷分散方法および装置に関し、特に、ネットワークで接続された複数のノードからなるクラスタに用いて好適な、負荷分散方法及び装置とシステムとプログラムに関する。
【背景技術】
【０００２】
複数の計算資源から構成されるシステム上で、複数種類のタスクを処理する際の負荷分散の方法が、例えば、後記する非特許文献１等に記載されている。非特許文献１に記載されている負荷分散方法は、静的なものである。すなわち、各計算資源の性能やタスクの負荷内容あるいはタスクの到着特性などを、事前に、何らかの方法で決定しておき、実行時に、事前に決定された特性に変化がないことを前提とした制御方法である。静的な負荷分散は、変動が少なく定常的な負荷を分散させ均衡させるためには、有効であるが、実際の負荷は、常に変動しており、短い時間間隔においては、常に、負荷の不均衡が生じている。このような問題を解決するのが、動的負荷分散である。
【０００３】
複数種類のトランザクションを対象とする動的負荷分散方法の一例として、複数の負荷を合成した負荷特性（ジョブミックス）と、プログラムの処理時間の伸長率を推定することで、動的な負荷分散を行なう方法が提案されている（例えば後記する特許文献１参照）。ジョブミックスを用いるのは、一つの解決策ではあるが、ジョブミックスが同じような場合であっても、ジョブミックスを構成する複数種類のトランザクションのうち、どの種類のトランザクションがシステム性能全体に影響を与えているかという要因は、考慮に入れられていない。従って、ある種類のトランザクション処理が必要以上に他の種類のトランザクション実行を妨げているような場合に対する問題の解決はなされていない。
【０００４】
各ノードが自ノードが持つ負荷情報に基づいて負荷の移送先を決定する負荷分散方法の一例が、例えば後記する非特許文献２等に記載されている。非特許文献２には、各ノードが周期的に他の全ノードの負荷情報を収集し、自ノードの負荷と、全ノードで最も負荷の軽いノードの負荷の差Δが、ある値よりも大きくなった場合、到着したタスクを、最も負荷の軽いノードに移送する、という負荷分散方法が提案されている。
【０００５】
非特許文献２に記載される手法では、他の全ノードから情報を収集してタスクの移送先を選択するために、多数のノードからなるシステムにおいては、負荷情報の共有に必要な計算・通信コストが高くなり、負荷分散を行うことによる性能の向上は、情報共有コストによって打ち消されてしまう。だからといって、情報共有コストを削減するために情報更新間隔(情報収集の周期)を長くすると、古い情報に基づいて負荷分散を行うことになる。そして、負荷情報の更新時には負荷が軽かったが、現在は負荷が重いノードにタスクを移送してしまう場合も生じ、負荷を均衡させることが、困難になる。
【０００６】
また、精度の異なる情報を共有することで、低コストで、多数のノードの負荷情報を共有する方法が、先行出願１に記載されているが、非特許文献２に記載された方法では、精度の異なる情報を扱うことができない。
【０００７】
多数のノードがある低負荷なノードの負荷情報を持っている場合に、この低負荷なノードに、多数のノードがほぼ同時に負荷を移送してしまい、低負荷ノードが過負荷なノードになってしまうという「群集効果」が発生する。群集効果は、負荷均衡を妨げる理由の一つである。
【０００８】
負荷情報を収集するノードはタスクの移送先になり得るノードであることから、負荷情報を収集するノードをランダムに定数個選択すれば、情報共有コストを抑えつつ、群集効果の発生を抑制することができる。このようなアルゴリズムについては、例えば後記する非特許文献３の記載が参照される。ただし、非特許文献３に記載された手法では、システム全体の負荷情報を知ることができないため、システム全体に亘って、負荷が均衡するとは限らない。
【０００９】
タスクの到着だけでなく、タスクの出発によっても負荷の変化が生じる。上記二つのアルゴリズムが行うのは、タスクの到着を分散させることである。このため、タスクの実行時間のばらつきによって生じる負荷の不均衡を直接解消することはできない。つまり、既に到着したタスクを移送することはできない。
【００１０】
既に到着したタスクを最も負荷の低いノードに移送するアルゴリズムが、例えば後記する非特許文献４に記載されている。しかしながら、非特許文献４に記載の手法では、一度に移送するタスクの個数は、最大で二つであり、移送先ノードも単一のノードに限られるため、負荷不均衡の度合いが大きい場合には、負荷を均衡させるのに時間がかかってしまう。また、群集効果も発生する。
【００１１】
［先行出願１］
特願２００２−３３３７４１号（図１、図２）
【００１２】
【特許文献１】特開２００１−１０９６３８号公報（第６頁）
【非特許文献１】ジエ・リー(Jie Li)、ヒサオ・カメダ(Hisao Kameda)著、”ロードバランシングプロブレム  フォア  マルチクラス  ジョブ  イン、ディストリビューテッド／パラレル  コンピュータシステム（Load Balancing Problems for Multi-class Jobs in Distributed/Parallel Computer Systems）”、アイ・イー・イー・イー・トランザクションズ・オン・コンピューターズ(IEEE Transactions on Computers)、米国、１９９８年、第４７巻、第３号、３２２〜３３２頁
【非特許文献２】ソンニアン・ゾウ(Songnian Zhou)著、”ア  トレースドリブン  シミュレーション  スタディ  オブ  ダイナミック  ロードバランシング”（A Trace-Driven Simulation Study of Dynamic Load Balancing）、アイ・イー・イー・イー・トランザンションズ・オン・ソフトウェアエンジニアリング(IEEE Transactions on Software Engineering)、米国、１９８８年、第１４巻、第９号、１３２７〜１３４１頁
【非特許文献３】マイケル・ミッツェンマッシャー(Michael Mitzenmacher)著、”ハウユースフル  イズ  オールド  インフォーメーション”（How Useful Is Old Information?）、アイ・イー・イー・イー・トランザクションズ・オン・パラレル・アンド・ディストリビューテッド・システムズ(IEEE Transactions on Parallel and Distributed Systems)、米国、２０００年、第１１巻、第１号、６〜２０頁
【非特許文献４】ジョン・スタンコビック(John Stankovic)著、シミュレーション  オブ  スリー  アダプティブ  デセントラライズド  コントロールド  ジョブ  スケジューリング  アルゴリズム”（Simulations of three adaptive, decentralized controlled, job scheduling algorithms）、コンピューティングネットワークス(Computing Networks)、米国、１９８４年、第８巻、１９９〜２１７頁
【非特許文献５】亀田壽夫、紀一誠、李頡著、「性能評価の基礎と応用」、共立出版、１９９８年、第４．２章
【非特許文献６】伊理正夫、藤野和建著、「数値計算の常識」、第15章  補間（内挿）、第16章  雲形定規とスプライン−続補間（第109〜122頁）、共立出版、1985年、
【発明の開示】
【発明が解決しようとする課題】
【００１３】
上記した従来の負荷分散は以下の問題点を有している。
【００１４】
第１の問題点は、複数のノードから構成されるクラスタシステム上で複数のタスク処理を行うような状況下では、ある種のタスクの発生／到着が極端に増えてしまった場合に、関係のないタスクの実行が影響を受け、レスポンスタイムの極端な悪化等の状況が生じてしまう、ということである。
【００１５】
その理由は、ノードでは、複数の種類のタスクが実行されるため、あるタスク種の実行が他のタスク種の実行を妨げるためである。
【００１６】
第２の問題点は、群集効果が生じる、ということである。
【００１７】
その理由は、個々のノードが他のノードの負荷移送を考慮していない、ためである。
【００１８】
第３の問題点は、負荷の不均衡の度合いが大きいと、負荷を均衡させるために長時間を要する、ということである。
【００１９】
その理由は、到着したタスクの移送のみを行うか、既に到着したタスクを移送したとしても、少数ずつ単一のノードに移送するだけの構成とされている、ためである。
【００２０】
第４の問題点は、情報共有コストを低くすると、適切な負荷分散を行うことができない、ということである。
【００２１】
その理由は、情報更新間隔を長くした場合、情報更新時には負荷が軽かったが現在は負荷が重いノードにタスクを移送してしまう、という問題が生じるためである。また、一部のノードの負荷情報のみを共有した場合は、局所的に負荷が均衡させることができても、全体的な負荷均衡を図るのが困難になる、という問題が生じるためである。
【００２２】
したがって、本発明は、上記問題点に鑑みて創案されたものであって、その目的は、異なる種類のタスクによる負荷が互いのタスク実行に影響を及ぼさないように、タスク種にノードを割り当てることができる方法及び装置とシステム並びにプログラムを提供することにある。
【００２３】
本発明の他の目的は、群集効果を発生し難くする負荷分散方法及び装置とシステム並びにプログラムを提供することにある。
【００２４】
本発明のさらに他の目的は、負荷を高速に均衡させることができる負荷分散方法及び装置とシステム並びにプログラムを提供することにある。
【００２５】
本発明のさらに他の目的は、低コストで提供される、精度の異なる負荷情報に基づいて負荷分散を行っても、負荷を均衡させることができる負荷分散方法及び装置とシステム並びにプログラムを提供することにある。
【課題を解決するための手段】
【００２６】
前記目的を達成する本発明は、ユーザが望むレスポンスタイムを満足するように、複数種類のタスクを処理可能とし、各ノードは、自ノードが持つ負荷情報に基づいて、負荷の移送先を決定できるようにしたものである。
【００２７】
より詳細には、本発明の一つのアスペクトに係る負荷分散装置（「グローバル負荷分散装置」ともいう）は、システム構成情報とシステムの運用条件と事前に測定されたタスク−ノード特性とを入力するシステム構成入力手段と、システムに到着するタスクの種類を判別し、タスク到着率をタスクごとに測定するタスク受信手段と、実行時にノードの実行時性能情報を測定する実行性能測定手段と、前記システム構成情報と、システムの運用条件と、事前に測定されたタスク−ノード特性と、実行時に測定される前記タスク到着率と、ノードの実行時性能情報と、を用いて、ノードグループを構成し、ノードグループ上で実行されるタスク種を決定するノードグループ構築手段と、タスクを実行するノードを、ノードグループより選択して、選択したノードに対してタスクを転送するタスク転送手段と、を有する。
【００２８】
本発明に係る負荷分散装置において、タスク転送先ノード上の滞留タスク数が予め定められた所定数を超えないように、タスクをキューイングするグローバルキューイング手段をさらに有する構成としてもよい。
【００２９】
本発明に係る負荷分散装置において、前記ノードグループ構築手段が、一つのノードグループに対して運用条件を満足するタスク種を対応させ、他のノードグループに対して運用条件を満足しないタスク種を対応させる構成としてもよい。
【００３０】
本発明に係る負荷分散装置において、前記ノードグループ構築手段が、一つのノードグループ上で一種類のタスク処理が行なわれるようにノードグループを構成し、前記ノードグループに対してタスク種の対応付けを行う構成としてもよい。
【００３１】
本発明の他のアスペクトに係るノードは、計算機システムを構成するノードであって、
タスクまたはタスクの実行結果の送受信を行うタスク送受信手段と、前記タスク送受信手段で受信したタスクをキューイングするローカルキューイング手段と、負荷情報を共有する負荷情報共有手段と、前記負荷情報共有手段が提供する他ノードの負荷情報に基づいて、どのタスクをどのノードに移送するかを決定し、前記タスク送受信手段にタスクの移送を依頼する負荷分散手段と、実行を依頼されたタスクを処理し、前記タスクの実行結果を、前記ローカルキューイング手段に返すタスク実行手段と、を有する。
【００３２】
本発明に係るノードにおいて、前記負荷分散手段は、好ましくは、負荷情報を管理する負荷情報管理手段と、自ノードで実行すべきタスクの量を動的に計算する均衡度計算手段と、ノードに対して優先度を割り当てるノード優先度割り当て手段と、優先度順に、負荷の移送対象のノードを選択し、該ノードに移送するタスクの個数を決定する移送タスク決定手段と、を有する。
【００３３】
本発明に係るノードにおいて、前記ノード優先度割り当て手段が、他ノードに割り当てる優先度は、循環単調増加優先度割り当てとされる。
【００３４】
本発明に係るノードにおいて、前記負荷情報共有手段は、異なる精度を持つ負荷情報を共有し、前記負荷分散手段の前記負荷情報管理手段は、単純空間精度補完を行い、前記負荷分散手段の前記ノード優先度割り当て手段は、負荷情報の精度が高いノードに対してより高い優先度を割り当てる構成としてもよい。
【００３５】
本発明に係るノードにおいて、タスクの実行数別に、スループットを算出するためのレスポンスタイムテーブルを有し、前記負荷分散手段の前記ローカルキューイング手段は、前記レスポンステーブルを参照して、同時に実行するタスク数を動的に変化させる構成としてもよい。
【００３６】
本発明のさらに他のアスペクトに係る方法は、システム構成情報と、事前に測定されたタスク−ノード特性と、タスク到着率と、ノードの実行時性能情報の少なくとも１つに基づき、ノードグループを構成し、実行時に得られる負荷情報を用いて、各ノードグループのサイズを適切な値に設定するステップを有する。
【００３７】
本発明の他のアスペクトに係る方法は、負荷分散装置が、タスク処理要求を受け付け、タスクの種類を判別し、タスクの到着率を測定するステップと、前記負荷分散装置が、計算機システムを構成するノードを複数のノードグループに分け、どのノードグループでどのタスク種を実行させるかを決定し、その際、入力装置から得られるシステム構成情報と、測定された実行時の性能測定情報とを用いて、各ノードグループに含まれるノードの数を調整することで、ユーザが指定する運用条件を満足するように制御するステップと、前記負荷分散装置が、あるタスク種を実行するノードグループの中から１つのノードを選択し、選択されたノードに対して前記タスクを転送するステップと、を含む。
【００３８】
本発明に係る方法においては、前記負荷分散装置が、ノード上に滞留しているタスク数が予め定められた所定個数を超えないように、タスクをキューイングするステップを有する。
【００３９】
本発明の他のアスペクトに係る方法においては、複数のノードが計算機システムを構成するシステムの負荷分散方法において、他ノードの負荷情報に基づいて、負荷の移送対象のノードを決定し、前記ノードにタスクを移送することで、負荷分散処理を行うステップを含む。
【００４０】
本発明に係る方法においては、前記負荷分散処理を行うステップが、
自ノードで実行すべきタスクの量を計算するステップと、
ノードに対して、優先度を割り当てるステップと、
優先度順に、負荷の移送対象のノードを選択し、該ノードに移送するタスクの個数を決定するステップと、を有する。
【００４１】
さらに、本発明の他のアスペクトに係るプログラムは、複数のノードを含む計算機システムを対象としたグローバル負荷分散装置を構成するコンピュータに、
システム構成情報と、システムの運用条件と、事前に測定されたタスク−ノード特性とを入力するシステム構成入力処理と、
システムに到着するタスクの種類を判別し、タスク到着率をタスクごとに測定するタスク受信処理と、
実行時にノードの実行性能情報を測定する実行性能測定処理と、
前記システム構成情報と、前記システムの運用条件と、事前に測定された前記タスク−ノード特性と、実行時に測定される前記タスク到着率と、ノードの実行時性能情報と、のうちの少なくとも一つを用いて、ノードグループを構成し、前記ノードグループ上で実行されるタスク種を決定するノードグループ構築処理と、
タスクを実行するノードを前記ノードグループより選択して、前記ノードに対してタスクを転送するタスク転送処理と、
を実行させるためのプログラムよりなる。
【００４２】
さらに、本発明の他のアスペクトに係るプログラムは、計算機システムを構成するノードを構成するコンピュータに、
タスクまたはタスクの実行結果の送受信を行うタスク送受信処理と、
前記タスク送受信手段で受信したタスクをキューイングするキューイング処理と、
負荷情報を共有する負荷情報共有部が提供する他ノードの負荷情報に基づいて、どのタスクをどのノードに移送するかを決定し、前記タスク送受信手段にタスクの移送を依頼する負荷分散処理と、
実行を依頼されたタスクを処理し、前記タスクの実行結果を、前記ローカルキューイング手段に返すタスク実行処理と、
を実行させるためのプログラムよりなる。
【００４３】
本発明に係るプログラムにおいて、前記負荷分散処理を実行する前記プログラムは、
負荷情報を管理する負荷情報管理処理と、
自ノードで実行すべきタスクの量を動的に計算する均衡度計算処理と、
ノードに対して優先度を割り当てるノード優先度割り当て処理と、
優先度順に、負荷の移送対象のノードを選択し、該ノードに移送するタスクの個数を決定する移送タスク決定処理とを、ノードを構成する前記コンピュータに実行させるためのプログラムよりなる。
【発明の効果】
【００４４】
本発明によれば、ノードグループを構成し、該ノードグループを構成するノード数を、実行時に、最適な値に制御し、かつ、ノードグループ上で実行されるタスクの種類を決定するために、あるノードグループ上で実行されるタスク種が、たとえ過負荷になったとしても、他のノードグループ上で実行されるタスク種の実行性能に悪影響を及ぼすことがない、という効果を有する。
【００４５】
本発明によれば、タスク種を実行するノードグループを構成するため、ノードグループを超えて、タスクの実行に影響が及ばず、あるタスク種が突然大量に発生しても、関係のないタスク種の実行は、影響を受けず、事前に定められたレスポンスタイムを満足させることができる。
【００４６】
本発明によれば、自ノードの負荷が閾値を越えた時に、過去に移送判断を行ったノードの負荷と、現在移送判断を行っているノードの負荷とから、負荷移送の判断を行っており、他ノードのタスク移送を考慮することにより、群衆効果を緩和することができる。
【００４７】
本発明によれば、一つのノードに対して一つ以上のタスクを移送することと、一つ以上のノードにタスクを移送することを決定することにより、高速に負荷を均衡させることができることにある。本発明によれば、余剰負荷を複数ノードに対して、それぞれ複数個ずつ移動させるためである。
【００４８】
本発明によれば、異なる精度を持つ負荷情報に基づいて負荷移送の判断を行うことにより、低コストで共有できる。さらに、異なる精度を持つ負荷情報の精度と負荷から負荷情報を再構築することで、適切な負荷分散を実現することができる。
【発明を実施するための最良の形態】
【００４９】
次に、本発明の第１の実施の形態について図面を参照して詳細に説明する。
【００５０】
図１には、本発明の第１の実施の形態のグローバル負荷分散装置１の構成が示されている。図１を参照すると、本発明の第１の実施の形態のグローバル負荷分散装置１は、システム構成に関する情報（例えば、システム構成情報と、システムの運用条件と、事前に測定されたタスク−ノード特性）を入力するシステム構成入力手段１３と、システムに到着するタスクの種類を判別しタスク到着率をタスクごとに測定するタスク受信手段１１と、ノードの実行時性能情報を測定する実行性能測定手段１４と、システム構成情報と、システムの運用条件と、事前に測定されたタスク−ノード特性と、実行時に測定されるタスク到着率と、ノードの実行時性能情報とを用いてノードグループを構成し、ノードグループ上で実行されるタスク種を決定するノードグループ構築手段１２と、タスクを実行するノードをノードグループより選択し、選択したノードに対して、タスクを転送するタスク送信手段１５とを備えている。上記各手段は、グローバル負荷分散装置１を構成するコンピュータで実行されるプログラムによりその処理、機能が実現される。
【００５１】
本発明が対象とするクラスタシステムは、処理能力が異なるＫ種類のノードが、それぞれＮ（ｋ）個（ｋ＝１〜Ｋ）から構成され、またシステム上で実行されるタスクの種類は、全部でＪ種類であるものとする。また、全ノード数をＮと表記する。すなわち、
Ｎ＝Ｎ（１）＋・・・＋Ｎ（Ｋ）        …（１）
【００５２】
図２は、本発明の第１の実施の形態のグローバル負荷分散装置１の処理手順を説明するための流れ図である。図１及び図２を参照して、本発明の第１の実施の形態のグローバル負荷分散装置１の動作について説明する。
【００５３】
タスク受信手段１１は、グローバル負荷分散装置１へのタスク処理要求を受け付け（図２のステップ１０１）、タスクの種類を判別し（ステップ１０２）、タスクの到着率を測定する（ステップ１０３）。
【００５４】
ノードグループ構築手段１２は、全部でＮ個あるノードをいくつかのグループ（これを「ノードグループ」と呼ぶ）に分けて管理し、どのノードグループで、どのタスク種を実行させるかを決定する。この際に、システム構成入力手段１３から得られる情報と、実行性能測定手段１４から得られる情報とを用いて、各グループに含まれるノード数を実行時に制御し（ステップ１０４）、ユーザが指定する運用条件を満足するように、動作する。
【００５５】
タスク送信手段１５は、あるタスク種を実行するノードグループの中から適切なノードを一つ選び出し（ステップ１０５）、選択されたノードに対して、タスクを転送する（ステップ１０６）。
【００５６】
このような動作を行なうために、グローバル負荷分散装置１は、ノードグループを構築するノードを管理するノードグループ構成表１９３（図１９参照）と、あるタスク種を実行するノードグループを管理するタスク種−ノードグループ対応表１９４（図１４参照）と、実行時に測定する性能データを管理する測定データ管理表とを記憶装置に記憶保持する。この測定データ管理表は、図１７に示すタスク到着率管理表１９１と、図１８に示すノード性能管理表１９２とから構成される。
【００５７】
更に、グローバル負荷分散装置１内に、グローバルキューイング手段１６を追加した場合には、各ノード上に滞留しているタスク数が一定個数を超えないように、グローバルキューイング手段１６上に、タスクをキューイングするように動作を拡張することもできる。
【００５８】
次に、本発明の第２の実施の形態について図面を参照して詳細に説明する。
【００５９】
図３は、本発明の第２の実施の形態のシステム及びノードの構成を示す図である。図３を参照すると、本発明の第２の実施の形態は、スイッチング装置２と、ノード３−１〜３−ｎと、を含む。ただし、ｎは、ある自然数である。ノード３−１〜３−ｎは、スイッチング装置２を経由して通信を行なうことができ、タスクは、スイッチング装置２を経由してノード３−１〜３−ｎに到着する。各ノード３−１〜３−ｎは同一の構成を有し、図３では、ノード３−１の構成が示されている。各ノードは、負荷分散手段３１と、負荷情報共有手段３２と、タスク送受信手段３３と、タスク実行手段３４と、ローカルキューイング手段３５とを含む。これらの手段は、ノードを構成するコンピュータで実行されるプログラムによってその機能が実現され、それぞれ概略つぎのように動作する。
【００６０】
タスク送受信手段３３は、タスクまたはタスクの実行結果の送受信を行う。
【００６１】
タスク実行手段３４は、依頼されたタスクを処理し、実行結果をローカルキューイング手段３５に返す。
【００６２】
ローカルキューイング手段３５は、タスク送受信手段３３で受信したタスクをキューイングし、キューの先頭から、ある個数のタスクをタスク実行手段３４に渡す。タスク実行手段３４から実行結果を受け取るか、タスク送受信手段３３に実行結果が到着していれば、対応するタスクをキューから外す。そして、実行結果の送信をタスク送受信手段３３に依頼する。
【００６３】
負荷情報共有手段３２は、上記先行出願１に記載される情報共有方法及び装置と等価な動作を行う。ただし、他ノードの負荷情報が更新されたときに、下記負荷分散手段３１に情報をプッシュする機能が追加されている。
【００６４】
負荷分散手段３１は、負荷情報共有手段３２が提供する他ノードの負荷情報に基づいて、どのタスクをどのノードに移送するかを決定し、タスク送受信手段３３にタスクの移送を依頼する。
【００６５】
図４は、図３の負荷分散手段３１の構成を示す図である。図４を参照すると、負荷分散手段３１は、負荷情報管理手段３６と、ノード優先度割り当て手段３７と、均衡度計算手段３８と、どのタスクをどのノードに移送するかを決定する移送タスク決定手段３９とを持つ。これらの手段はそれぞれ概略つぎのように動作する。
【００６６】
負荷情報管理手段３６は、負荷情報共有手段３２からプッシュされた負荷情報を受け取り、あらかじめ定められた方法に従って、情報を再構成する。また、負荷情報管理手段３６は、下記の移送タスク決定手段３９からの負荷情報の問い合わせに答える。さらに、負荷情報管理手段３６は、移送タスク決定手段３９からのノードの負荷情報の更新を、そのノードに関する負荷情報共有手段３２からの情報のプッシュがあるまで保持する。
【００６７】
ノード優先度割り当て手段３７は、あらかじめ定められた方法に従って、どのノードから負荷の移送判断を行うかを決めるための優先度をノードに割り当てる。ただし、以下では、優先度の値が小さいほど、優先度は高いものとする。
【００６８】
均衡度計算手段３８は、あらかじめ定められた方法に従って、自ノードで実行すべきタスクの量（threshold)を動的に計算する。
【００６９】
移送タスク決定手段３９は、優先度の高いノードから、タスクを移送するかどうかを決定する。
【００７０】
図５は、本発明の第２の実施の形態の動作を説明するための流れ図である。次に、図３乃至図５を参照して、本発明の第２の実施の形態の全体の動作について詳細に説明する。
【００７１】
まず、タスクをタスク送受信手段３３で受信する(図５のステップＬ１）。
【００７２】
次に、受信したタスクを、ローカルキューイング手段３５がキューイングする。ただし、キューイング時にタスクの実行結果の返信先が判別できるようにしておく。例えば、ＴＣＰによる通信でタスクが送信されたのであれば、キューイング時にタスクとコネクションの対応を記録しておく（ステップＬ２）。
【００７３】
負荷分散手段３１は、ローカルキューイング手段３５中のタスクに関して、キューの先頭から、ある数Ｑのタスクを除いて、どのノードで実行すればよいかを決定する（ステップＬ３）。
【００７４】
この決定に基づいて、タスク送受信手段３３はタスクを他のノードに移送する（ステップＬ４）。
【００７５】
他のノードに移送されなかった、キューの先頭からＱ個のタスクは、タスク実行手段３４で実行される（ステップＬ５）。
【００７６】
タスク送受信手段３３は、他ノードに移送したタスクの実行結果が返ってきていれば、これを受信する（ステップＬ６）。
【００７７】
ローカルキューイング手段３５は、タスク実行手段３４から実行結果を受け付けるか、タスク送受信手段３３で実行結果が受信されていれば、対応するタスクをキューから外し、タスク送受信手段３３を用いて実行結果を送信する（ステップＬ７）。ただし、負荷情報共有手段３２は、負荷分散手段３１に対して適宜負荷情報をプッシュする。
【００７８】
図６は、本実施の形態の負荷分散手段３１の動作を説明するための流れ図である。図４、図６を参照して、本実施の形態の負荷分散手段３１の動作について以下に詳細に説明する。
【００７９】
まず、均衡度計算手段３８を用いて、許容できる自ノードの負荷の上限である閾値（threshold)を算出する（図６のステップＡ１)。
【００８０】
次に、ノード優先度割り当て手段３７を用いて、他のノードに対して優先度を割り当てる(ステップＡ２)。以下では、優先度が高いノードを「近いノード」、優先度が低いノードを「遠いノード」と呼ぶ。
【００８１】
そして、移送タスク決定手段３９は、移送したい負荷の量「over」（オーバ）を算出する。「over」は、自ノードの負荷と、閾値「threshold」以上の最小の整数の差である。また、負荷移送対象ノードが受け入れることができる負荷の量「under」（アンダー）を「０」で初期化する(ステップＡ３)。
【００８２】
移送タスク決定手段３９は、移送したい負荷の量「over」が正値であるか否か判定し、正値でなければ、負荷分散を行わずに終了する(ステップＡ４)。
【００８３】
移送したい負荷の量「over」が正値であれば、移送タスク決定手段３９は、近いノードから順に、負荷移送判断を行うノードを選択する（ステップＡ５)。以下では、選択されたノードを、「負荷移送対象ノード」と呼ぶ。
【００８４】
既に全てのノードに対して、負荷移送判断が行われていれば、選択できるノードがないので、負荷分散を終了する(ステップＡ６)。
【００８５】
移送タスク決定手段３９は、受け入れ可能な負荷の量「under」に、閾値「threshold」と、負荷移送対象ノードの(負荷情報管理手段３６に問い合わせて得られた)負荷情報との差を加える(ステップＡ７)。
【００８６】
加算された受け入れ可能な負荷の量「under」が「１」以上でなければ、ステップＡ５に戻って、負荷移送対象ノードを変更する（ステップＡ８)。
【００８７】
加算された受け入れ可能な負荷の量「under」が「１」以上であれば、負荷を「１」だけ負荷移送対象ノードに移送することを決定する(ステップＡ９)。
【００８８】
そして、負荷情報管理手段３６を用いて、自ノードの負荷情報を「１」減らし、自ノードが持つ移送対象ノードの負荷情報を、「１」増やして(ステップＡ１０)、負荷分散を終了する。
【００８９】
次に、本発明の第２の実施の形態の作用効果について説明する。
【００９０】
本発明の第２の実施の形態において、
「over」は、自ノードの過負荷状態を解消するために移送すべき負荷の量を意味する。
「under」は、最も近くにあるノードから負荷移送対象ノードまでのノードが、過負荷になることなく受け入れられる負荷の量を意味する。
【００９１】
したがって、「under」が正になる最も近いノード(ノードα)に対して、負荷を移送することは、自ノードと、ノードαの間にあるノードは、それらのノード間での負荷移送によって、負荷均衡を図ることを考慮する、ことを意味する。このようにして、他ノードの負荷移送を考慮して自ノードの負荷移送を決定するため、群集効果を防ぐことができる。
【００９２】
次に、本発明の第３の実施の形態について図面を参照して詳細に説明する。本発明の第３の実施の形態の基本構成は、図３乃至図５を参照して説明した前記第２の実施の形態の構成と同様である。
【００９３】
本発明の第３の実施の形態は、前記第２の実施の形態に対し、負荷分散手段３１（図４参照）の処理手順を示す図６において、タスク移送先を決定する動作であるステップＡ９と、負荷情報を更新する動作であるＡ１０の代わりに、図７のステップＢ１〜Ｂ５を実行する点が異なる。
【００９４】
「under」が「１」以上であり、かつ、「over」が「under」以下であれば、移送タスク決定手段３９は、「over」分の負荷を負荷移送対象ノードに移送することを決定する（図７のステップＢ２）。
【００９５】
そして、負荷情報管理手段３６（図４参照）を用いて、自ノードの負荷情報を「over」分減らし、自ノードが持つ移送対象ノードの負荷情報を「over」分増やして（ステップＢ３)、負荷分散は終了する。
【００９６】
「under」が「１」以上であり、かつ、「over」の値が「under」の値よりも大きければ、移送タスク決定手段３９は、floor(under)(＝under以下の最大の整数)分の負荷を、負荷移送対象ノードに移送することを決定する（ステップＢ４）。
【００９７】
そして、負荷情報管理手段３６を用いて、自ノードの負荷情報と「over」を、「floor(under)」減らし、自ノードが持つ負荷移送対象ノードの負荷情報を、「floor(under)」増やす。さらに、「under」から、「floor(under)」を差し引く（ステップＢ５)。そしてステップＡ５へ進む。
【００９８】
次に、本発明の第３の実施の形態の作用効果について説明する。
【００９９】
本発明の第３の実施の形態では、「under」が正になったノード(ノードα)に対して、「under」分の負荷を移送する。これは、ノードαと、ノードαにより近いノードを過負荷状態にしないので、他ノードの負荷移送を考慮して、自ノードの負荷移送を行うことを意味する。従来、複数個のタスク移送を行うと、群衆効果が強まってしまうために、性能は向上しないが、本実施形態では、他ノードのタスク移送を考慮することで群衆効果を緩和できるため、複数タスクを複数ノードに移送しても、高速に負荷を均衡させることができる。
【０１００】
次に、本発明の第４の実施の形態について詳細に説明する。本発明の第４の実施の形態は、前記第３の実施の形態と同一の構成とされるが、負荷情報共有手段３２（図３参照）、負荷分散手段３１の負荷情報管理手段３６（図４参照）の処理が相違している。すなわち、本発明の第４の実施の形態は、
（Ｉ）負荷情報共有手段３２（図３参照）が、精度の異なる情報を、負荷分散手段３１に提供し、
（ＩＩ）負荷分散手段３１の負荷情報管理手段３６（図４参照）が、負荷情報の値と精度から、負荷情報を再構築する
構成とされており、上記（Ｉ）、（ＩＩ）で、前記第３の実施の形態と相違している。
【０１０１】
次に、本発明の第４の実施の形態の作用効果について説明する。
【０１０２】
本発明の第４の実施の形態では、他ノードから送られる負荷情報の値と精度から、負荷情報を再構築する構成とされているため、低コストで負荷情報を共有することができる。ノード毎に異なる精度を持つ負荷情報に基づいていても、他ノードのタスク移送を考慮し、余剰負荷を複数ノードに対して、それぞれ複数個ずつ移送するように構成されているため、低コストでありながら、高速に、負荷を均衡させることができる。
【０１０３】
次に、本発明の第５の実施の形態について図面を参照して詳細に説明する。本発明の第５の実施の形態は、前記本発明の第３、第４の実施の形態とは相違して、負荷分散手段３１（図３、図４参照）は、レスポンスタイムテーブル（図８参照）を備えている。
【０１０４】
ローカルキューイング手段３５（図３参照）において、タスクのレスポンスタイムを測定し、その結果を、レスポンスタイムテーブルに反映させ、レスポンスタイムテーブルを参照して、実行時に同時に実行するタスクの数を変化させる制御が行われる。
【０１０５】
図８を参照すると、レスポンスタイムテーブル３１０は、レスポンスタイムの総和と測定個数(和を取ったレスポンスタイムの個数)を記録する。この二つの値は、実行数(同時に実行されていたタスク数)別に記録される。例えば三つのタスクが実行されていて、そのうちの一つが終了したら、このレスポンスタイムは実行数が「３」の時のものとして扱われる。
【０１０６】
次に、図５と図９を参照して、本実施の形態におけるローカルキューイング手段３５の動作について詳細に説明する。
【０１０７】
ローカルキューイング手段３５は、図５のステップＬ５で、タスク実行手段３４にタスクを渡すときの時刻を、タスク毎に保持する。また、図５のステップＬ６では、実行結果を受け取る度に、図９に示す動作を加えて行う。
【０１０８】
まず、ローカルキューイング手段３５は、実行結果をタスク実行手段３４から受け取ると、現在時刻とステップＬ５で保持したタスクの実行開始時刻の差を求める（図９のステップＣ１）。
【０１０９】
次に、現在のキュー長に「１」を足した実行数のレスポンスタイムの総和に、ステップＣ１で求めたレスポンスタイムを加算し、対応する測定個数を「１」増やし、レスポンスタイムテーブル３１０を更新する（ステップＣ２）。
【０１１０】
さらに、レスポンスタイムテーブル３１０を参照して、ｓ個以上のレスポンスタイムの総和を、対応する測定個数で割ることで、平均レスポンスタイムを求め、これら平均レスポンスタイムの値から望ましい実行数Ｒを求める（ステップＣ３）。ただし、ｓは、あらかじめ定められた値であり、「有効サンプリング数」と呼ぶ。
【０１１１】
そして、同時に実行するタスク数の最大値Ｑを、（Ｒ＋ｖ）に変更する（ステップＣ４）。ただし、ｖは、あらかじめ定められた非負の整数であり、「付加実行数」と呼ぶ。
【０１１２】
次に、本発明の第５の実施の形態の作用効果について説明する。
【０１１３】
本発明の第５の実施の形態では、同時に実行するタスク数別にレスポンスタイムを測定し、最大で、いくつのタスクを同時に実行するのが望ましいかを、動的に決定するように構成されているため、多重実行によるノードのスループットの向上と、タスクの移送制限(一度実行されたタスクは移送しない)による負荷不均衡のトレードオフを図り、システム全体のスループットを向上させることができる。
【０１１４】
次に、本発明の第６の実施の形態について図面を参照して詳細に説明する。
【０１１５】
図１０を参照すると、本発明の第６の実施の形態は、前記第５の実施の形態と相違して、スイッチング装置２（図３参照）の代わりに、グローバル負荷分散装置１を備えている。グローバル負荷分散装置１は、図１に示した構成とされるが、ノードグループ構築手段１２の処理が一部相違している。ノードは、図３に示した構成とされるが、負荷情報共有手段３２が相違している。
【０１１６】
グローバル負荷分散装置１は、前記第１の実施の形態と相違して、図２のステップ１０４において、ノードグループ構築手段１２が、ノードグループの変更を、変更が加えられるグループに含まれる各ノードの負荷情報共有手段３２に通知する動作を行う。
【０１１７】
また、本実施の形態における負荷情報共有手段３２は、前記第５の実施の形態と相違して、ノードグループ変更の通知を受け取り、他のノードグループに属するノードとは情報を共有しないようにする動作を行う。したがって、本実施の形態では、ノードグループ間を越えて、負荷が移送されることはない。
【０１１８】
次に、本発明の第６の実施の形態の作用効果について説明する。
【０１１９】
本発明の第６の実施の形態によれば、タスクは、タスク種毎に異なるノードグループで実行され、ノードグループ間でのタスクの移送が起きないように構成されているため、あるタスク種が突然大量に発生しても、他のタスク種の実行には影響を及ぼすことはなく、事前に定められたレスポンスタイムを満足させる、ことができる。
【０１２０】
また、ノードグループ内での負荷均衡が高速に達成されるため、より少ないノード数でノードグループを構成しても、事前に定められたレスポンスタイムを満足させる、ことができる。
【０１２１】
さらに、過負荷になったノードグループにノードを追加した直後に、負荷均衡状態に移行できるため、ノードを追加するタイミングを遅らせる、ことができる。その結果、今は、過負荷であるが、ノード追加時には低負荷になってしまった不適切なノード追加判断を減らし、システムのスループットを向上させる、ことができる。
【実施例】
【０１２２】
次に、上記した実施の形態についてさらに詳細に説明すべく、具体的な実施例に即して説明する。
【０１２３】
図１は、本発明の第１の実施例の構成を示す図である。グローバル負荷分散装置１に到着するタスクは、タスク受信手段１１が受け付け、タスク受信手段１１は、タスクの種類を判別する。タスクの種類を判別する方法の一例をあげる。プロトコルとして、ＨＴＴＰ（HyperText Transport Protocol）を用いた場合には、ＨＴＴＰリクエストの最初の行（リクエストライン）や、リクエストヘッダや、リクエストボディにタスクの種類を明示的に示しておくことで、タスクの種類を判断することができる。また、プロトコルが異なるものを異なるタスクと判別することもできる。あるいは、用いるポート番号が異なる場合に異なるタスクと判別することもできる。このようにして、タスク受信手段１１ではタスクの種類を判別する。
【０１２４】
また、タスク受信手段１１では、あらかじめ定められた測定時間間隔内に到着したタスクの個数をタスク種ごとに計数し、タスク到着率（単位時間当たりに到着したタスク数）を算出し、タスク到着率管理表１９１（図１７参照）にて、測定データを管理する。測定間隔が経過するたびに、タスク受信手段１１は、タスク到着率を算出し、タスク到着率管理表１９１を更新する。
【０１２５】
タスク到着率管理表１９１は、最新のタスク到着率だけではなく、前回の測定値や、その前の測定値なども管理対象とし、事前に定められた数（＝Ｌ）分の測定データを保存する。
【０１２６】
システム構成入力手段１３は、クラスタシステムを構成するノードの種類Ｋと、ｋ番目のノード種のノード数Ｎ（ｋ）と、システム上で実行されるタスクの種類数Ｊと、事前に測定されたタスク特性と、どのような条件でシステムを運用するかを定めるシステム運用条件との入力を受け付ける。
【０１２７】
なお、
Ｎ＝Ｎ（１）＋Ｎ（２）＋・・・＋Ｎ（Ｋ）      …（２）
とする。
【０１２８】
図１１（Ａ）、図１１（Ｂ）は、タスク特性の一つの具体例をそれぞれ示す図である。図１１（Ａ）は、一つのノード上で、一種類のタスク処理を行なった場合の、タスクの到着率（横軸）と、スループット（縦軸）との関係を示し、図１１（Ｂ）は、タスクの到着率（横軸）と、レスポンス（縦軸）との関係を示す図である（図１１に示したスループットとレスポンスとタスク到着率の特性を、「タスク−ノード特性」、もしくは「Ｔ−Ｎ特性」と呼ぶ）。
【０１２９】
システム運用条件の一つの具体例は、タスク処理時間として許容でき得る値（許容レスポンス）と、そのような許容レスポンスを達成するようにシステムが動作する限界範囲を定める限界到着率である。
【０１３０】
タスク到着率が、予め定められた限界到着率未満であれば、システムは許容レスポンスを達成するように、図１のノードグループ構築手段１２が、グループの構成を行なう。しかしながら、タスク到着率が限界到着率を超えてしまう場合には、保証範囲外の状態としてとらえ、システムとしては、許容レスポンスを達成するようなグループ構成は行なわない。
【０１３１】
図１２に、入力の一例を示す。図１２を参照すると、第ｊ番目のタスク種と、第ｋ番目のノード種に対して、許容レスポンスタイムＲ（図では、「０．１１」）と、限界到着率Λ＿Ｌｉｍ（図では、「１．９９」）が指定され、更に、表形式で１ノードへのタスク到着率と、その時のスループットとレスポンスタイムとの関係（「タスク−ノード特性」、もしくは「Ｔ−Ｎ特性」という）が与えられている。
【０１３２】
このような表は、システムを実際に運用する前の段階で、１ノードを用いて、タスク処理性能を測定するような実験を行なうことにより取得される。あるいは、シングルプロファイル法を用いることで、一つのタスクを実行するために必要となるＣＰＵ利用時間やディスク・アクセス時間などから算出することができる（詳細は前記非特許文献５の記載参照）。
【０１３３】
図１２において、Ｔ−Ｎ特性の一つの行は、１ノードに与えるタスク到着率を一定にした状態で、多数のタスク処理を１ノード上で行った時に得られるスループットとレスポンスタイムの平均値である。
【０１３４】
システムで処理するタスクの種類がＪ個、システムを構成するノードの種類がＫ個あるので、図１２のような入力データは、ｊ＝１〜Ｊとｋ＝１〜Ｋの組み合わせに対して用意される。
【０１３５】
図１の実行性能測定手段１４では、運用時における個々のノードの処理性能を測定する。具体的には、測定間隔を定めて、その間にノードへ転送したタスク数（転送数）と、ノード上で処理が終了したタスク数（処理数）と、タスク処理に要する時間（レスポンスタイム）とを測定する。測定間隔として、通常、数百ミリ秒から数秒程度としている。
【０１３６】
処理が終了したタスクの個数を、測定間隔で除することで、ノードのスループットが得られる。
【０１３７】
また、直前の測定間隔における性能測定値や、その更に前の値なども管理対象とし、事前に定められた数（＝Ｌ）分の測定データを保存する。このような値を管理するために、図１８に示すような、ノード性能管理表１９２を用いる。ノード性能管理表１９２は、ノードＩＤに対して、レスポンス、スループット、転送数、処理数の欄を有し、それぞれの値のノード全体での平均値が記録され、過去（Ｌ回前）の測定から、現在の測定に対応して保持される。
【０１３８】
ノード性能管理表１９２は、タスク種と、ノード種ごとに作成される。ここで、転送タスク数と、完了タスク数とを用いることで、滞留タスク数を算出することができる。すなわち、次式（３）の関係が成り立つ。
【０１３９】
（滞留タスク数）＝（直前の測定間隔における滞留タスク数）
＋（転送タスク数）
−（完了タスク数）      …（３）
【０１４０】
従って、本実施例では、滞留タスク数は、直接測定する必要はない。
【０１４１】
ノードグループ構築手段１２は、全部でＮ個あるノードをグループ化し、どのノードグループでどのタスク種が実行されるかを管理する。そのために必要となる情報を管理するために、ノードグループ構成表１９３（図１９参照）と、タスク種−ノードグループ対応表１９４（図１４参照）とを更新する。
【０１４２】
図１９に示すように、ノードグループ構成表１９３は、ノードグループの番号と、そのノードグループを構成するノード番号をノードの種対ごとに対応付ける表である。すなわち、ノードグループの番号に対して、ノードグループを構成するノードの、ノードＩＤとノード数の対の情報を、ノード種１、２、…に対して有する。
【０１４３】
また、図１４に示すように、タスク種−ノードグループ対応表１９４は、第ｊ番目のタスク種を実行するノードグループを管理する表であり、タスクＩＤと、ノードグループ番号の対応表からなる。図１４に示す例では、タスクＩＤが１と３のタスクは、ノードグループ番号１で実行され、タスクグループＡのタスクを構成し、タスクＩＤが２のタスクは、ノードグループ番号２で実行され、タスクグループＢのタスクを構成している。
【０１４４】
これら二つの表（ノードグループ構成表１９３、タスク種−ノードグループ対応表１９４）を更新する際に、ノードグループ構築手段１２は、入力された運用条件と、Ｔ−Ｎ特性と、およびタスク到着率管理表１９１と、ノード性能管理表１９２とを参照する。
【０１４５】
以下では、ノードの種類が一つ（Ｋ＝１、すなわち、全てのノードの処理能力が等しい場合）で、かつ、一つのノードグループに対して一つのタスク種が対応付けられる場合（すなわち、Ｊ個のノードグループがあり、第ｊ番目のノードグループ上で、第ｊ番目のタスク種が実行されているという場合）に関して、ノードグループ構成表１９３、および、タスク種−ノードグループ対応表１９４を更新する具体的な方法に関して、詳細に説明する。なお、説明の都合上、次のような記号を定義する。
【０１４６】
第ｊ番目のタスク種の入力データとして与えられる許容レスポンスをＲ（ｊ）、限界到着率をΛ＿Ｌｉｍ（ｊ）とする。
【０１４７】
また、１ノードで達成可能な最大スループットを、Ｔ＿ｍａｘ（ｊ）とし、１ノードの許容到着率をλ（ｊ）とする。
【０１４８】
ここで、許容到着率λ（ｊ）は、許容レスポンスＲ（ｊ）を与えるような１ノードへのタスク到着率のことである。
【０１４９】
図１２に示されるような表形式のＴ−Ｎ特性を利用して、１ノードで達成することができる最大スループットＴ＿ｍａｘ（ｊ）と、１ノードの許容到着率λ（ｊ）とを次のようにして求める。
【０１５０】
最大スループットＴ＿ｍａｘ（ｊ）は、入力されたＴ−Ｎ特性の中から、スループットの最大値を選び、その値とする。
【０１５１】
１ノードの許容到着率λ（ｊ）は、到着率とレスポンスとの関係と、許容レスポンスタイムを用いて求める。
【０１５２】
到着率とレスポンスは、測定点におけるデータの組が、入力データとして与えられている。
【０１５３】
このような複数の測定点を、適切な方式で補間することで、レスポンスタイムを到着率の関数として表したり、逆に、到着率を、レスポンスタイムの関数として表すことができる。
【０１５４】
具体的な補間の詳細は、前記非特許文献６（「数値計算の常識」（伊理正夫、藤野和建著）共立出版（1985年）の第１５章  補間（内挿）と第１６章  雲形定規とスプライン−続補間）に詳述されているので、前記非特許文献６が参照される。本実施例においては、補間の詳細を省略する。
【０１５５】
このように、到着率とレスポンスタイムとの関係を近似的に関数で表すことで、許容レスポンスタイムＲ（ｊ）を与える到着率λ（ｊ）を求めることができる。
【０１５６】
前述したように、図１１（Ａ）、（Ｂ）は、Ｔ−Ｎ特性をグラフ表示したものである。タスク到着率とレスポンスとのグラフは、到着率がレスポンスタイムの関数として計算できるのであれば、許容レスポンスＲ（ｊ）から１ノードの許容到着率λ（ｊ）が容易に求められることを示している。
【０１５７】
第ｊ番目のノードグループ上で実行するタスク種が、第ｊ番目のタスク種のみである場合、第ｊ番目のタスク種の到着率Λ（ｊ）が与えられた時に、許容レスポンスＲ（ｊ）を満たすために、第ｊ番目のノードグループに含まれるノード数（これを「許容ノード数」と呼ぶ）を算出する関数Ｎ＿ｈ（ｊ）（Λ（ｊ））は、次のようになる。
【０１５８】
なお、タスク種ｊの到着率Λ（ｊ）は、タスク到着率管理表１９１で管理される値である。この表では最近Ｌ回の測定結果を管理しており、Λ（ｊ）として最近Ｌ回の測定結果の重み付け平均値を用いることができる。
【０１５９】
許容ノード数をｎ（ｊ）とすると、一つのノードに対する到着率が許容到着率λ（ｊ）以下であれば、許容レスポンスを満足すると考えられる。
【０１６０】
すなわち、
λ（ｊ）≧Λ（ｊ）／ｎ（ｊ）                …（４）
が成り立つように、ｎ（ｊ）を定めればよい。
【０１６１】
従って、
ｎ（ｊ）≧Λ（ｊ）／λ（ｊ）                …（５）
【０１６２】
ノード数は、整数値であることと、最低限必要な値ということを考慮すると、
Ｎ＿ｈ（ｊ）（Λ（ｊ））＝Ｃｅｉｌ（Λ（ｊ）／λ（ｊ））  …（６）
である。ここで、Ｃｅｉｌ（ｘ）は、ｘより小さくない最小の整数を示す。
【０１６３】
なお、タスク到着率Λ（ｊ）が、限界到着率λ＿Ｌｉｍ（ｊ）より大きい時には、必要以上に多くのノードを第ｊ番目のノードグループに対して割当てないようにしなければならない。
【０１６４】
このような条件を考慮し、Ｎ＿ｈは、最終的に、以下のような関数となる。
【０１６５】
Ｎ＿ｈ（ｊ）（Λ（ｊ））＝Ｃｅｉｌ（ｍｉｎ（Λ（ｊ），Λ＿Ｌｉｍ（ｊ））／λ（ｊ））、        …（７）
【０１６６】
ここで、ｍｉｎ（ａ，ｂ）は、ａとｂとの大きくない方を返す関数である。
【０１６７】
上記で求めた、１ノードの許容到着率λ（ｊ）と、許容ノード数を与える関数Ｎ＿ｈ（ｊ）（Λ（ｊ））とは、入力データを解析した段階で求められるものであり、実行時に測定される値を利用する必要は特にない。
【０１６８】
次に、実行時に、変化するタスク到着率Λ（ｊ）に応じて、Ｊ個のタスクに対して割り当てられるノード数を算出する手順（手続きＰ）を、図１３の流れ図を参照して説明する。この手順は、図１のノードグループ構築手段１２上で定期的に実行されるものであり、下記のようなステップから構成される。
【０１６９】
ｊ＝１〜ＪなるＪ個のタスクの中から、
Λ＿Ｌｉｍ（ｊ）＞Λ（ｊ）          …（８）
を満たす（すなわち到着率が許容到着率未満の）タスク種をタスクグループＡとし、
満たされないタスク種をタスクグループＢとする（ステップ１２２）。
【０１７０】
タスクグループＢのタスク種ｊに対しては、上記で導いた割り当てノード数を算出する（ステップ１２３）。
【０１７１】
関数Ｎ＿ｈ（ｊ）（Λ（ｊ））で得られる値を、ノード数として割り当てる。ここで、タスクグループＢのタスク種ｊに対して割り当てられたノード数の合計をＮｂとする。
【０１７２】
タスクグループＡのタスク種ｊに対しては、残りのＮａ＝Ｎ−Ｎｂ個のノードを適切に割り当てる（ステップ１２４）。このような割り当て方の一例は、ノードグループの仮想的な使用率がバランスするような割り当て方である。ここで、ノードグループの仮想的な使用率とは、次の通りである。タスク種ｊのスループットをΦ（ｊ）とし、ｊ番目のノードグループのノード数をｎ（ｊ）とする。この時、ｎ（ｊ）個のノードで達成できるスループットの最大値は、１ノードの最大スループットＴ＿ｍａｘ（ｊ）を用いて、
ｎ（ｊ）×Ｔ＿ｍａｘ（ｊ）                …（９）
と表すことができる。
【０１７３】
このスループットの最大値に対する現在のスループットの比
Φ（ｊ）／（ｎ（ｊ）×Ｔ＿ｍａｘ（ｊ））  …（１０）
をｊ番目のノードグループの仮想的な使用率とする。
【０１７４】
このようにして算出されるノードグループの仮想使用率が、タスクグループＡに含まれるタスク種ｊに対してほぼ一定値となるように、ｎ（ｊ）を定めることで、適切な割り当てノード数を算出することができる。
【０１７５】
ただし、
ｎ（１）＋…＋ｎ（Ｊ）＝Ｎａ              …（１１）
である。
【０１７６】
上記ステップ１２４で求めたノード数ｎ（ｊ）に関して、
ｎ（ｊ）≧Ｎ＿ｈ（ｊ）（Λ（ｊ））        …（１２）
が満たされる否かをチェックする（ステップ１２５）。
【０１７７】
Ｎ＿ｈ（ｊ）（Λ（ｊ））で算出される値は、最低限必要なノード数である。このような条件が満たされない場合には、不正な割り当てが起こっている、ということであるので、システム管理者に、割り当てられる十分な数のノードがないことを通知する。
【０１７８】
上記手続きＰを実行する前に、各ノードグループｊに割り当てられているノード数をＮＧ（ｊ）とし、手続きＰを実行して得られる割り当てノード数をＮＧ’（ｊ）とする。ただし、ｊ=１〜Jは、ノードグループ番号である。
【０１７９】
ここで、ノード数の変化分を、
ΔＮＧ（ｊ）=ＮＧ’（ｊ）−ＮＧ（ｊ）          …（１２）
と定める。
【０１８０】
得られたノード割り当てＮＧ’（ｊ）、ｊ＝１〜Ｊ、を実現するには、
ΔＮＧ（ｊ）＜０                                …（１３）
となるようなノードグループｊの中から、ノードを一つ選択して、そのノードグループから削除し、
ΔＮＧ（ｉ）＞０                                …（１４）
となるようなノードグループｉに、そのノードを追加するという手続きを繰り返し、最終的に、ノードグループに対するノード割り当て数が、ＮＧ’（ｊ）を満たすようにすると良い。
【０１８１】
ここで、ノードグループｊの中から一つのノードを選択する手法としては、
・ランダムな選択方式、又は、
・負荷としてタスク滞留数、もしくは平均レスポンスタイム、あるいは平均スループットなどの指標を用いて、最小負荷のノードを選択する方式
を用いることができる。
【０１８２】
従って、本実施例においては、ノードグループ構成表１９３（図１９参照）の中から、
ΔＮＧ（ｊ）＜０                                  …（１５）
となるようなノードグループｊを選び出し、ノードグループ構成表１９３中のｊ行の中から、前記の方法を用いて、一つのノードを選択して、ノードＩＤを表中から削除する。
【０１８３】
更に、ノードグループ構成表１９３の中から、
ΔＮＧ（ｉ）＞０                                  …（１６）
となるようなノードグループｉを選び出し、表中のｉ行に前記削除されたノードＩＤを追加するという操作を行なう。
【０１８４】
タスク送信手段１５では、タスク種−ノードグループ対応表１９４（図１４参照）を参照して、タスク種ｊに属するタスクを、タスクグループｊに属するノードに転送する。
【０１８５】
タスクグループｊに属するノードが複数個ある場合には、複数個のノードの中からリクエストを転送するノードを、一つ選択する必要がある。
【０１８６】
このようなノード選択の方法としては、
・複数個のノードを順番に選択するラウンドロビン手法、
・複数個のノードの中からランダムに一つのノードを選択するランダム選択手法、
・ノード上に滞留しているリクエスト数が最小のノードを選択する最小リクエストノード選択手法、
・レスポンスタイムが最小のノードを選択する最小レスポンス選択手法、
・スループットが最大のノードを選択する最大スループット選択手法、
のいずれかを用いることができる。
【０１８７】
この時に必要となる、各ノードの滞留リクエスト数、レスポンスタイム、スループットなど性能値は、ノード性能管理表１９２（図１８参照）で管理されている値を参照すれば良い。
【０１８８】
また、ノード性能管理表１９２の値は、最近Ｌ回の測定結果が保存されているため、最新の測定結果だけではなく、Ｌ個の測定結果の重み付け平均などを用いることもできる。
【０１８９】
本実施例では、タスク種ｊに割り当てるノード数を求める関数Ｎ＿ｈ（ｊ）を用いる。
タスク種ｊの到着率Λ（ｊ）が、限界到着率Λ＿ｌｉｍ（ｊ）未満の時には、
Ｃｅｉｌ（Λ（ｊ）／λ（ｊ））個のノードを割り当て、
タスク種ｊの到着率Λ（ｊ）が限界到着率Λ＿ｌｉｍ（ｊ）以上の時には、
Ｃｅｉｌ（Λ＿ｌｉｍ（ｊ）／λ（ｊ））個のノードを割り当てる、ように動作している。
【０１９０】
上記のように動作させることで、本実施例によれば、許容到着率以上の到着率を持つタスク種に対する割り当てノード数に制限を与え、他のタスク種に対して、十分な量のノードが割り当てられる、という効果を奏する。
【０１９１】
上記の実施例では、システム構成入力手段１３が受け付けるＴ−Ｎ特性として、図１２で示されるような表形式のデータを想定している。
【０１９２】
しかしながら、前述したシングルプロファイル法を用いると、一つのタスクを実行する際に必要となるノード内資源（ＣＰＵやディスク）の利用時間を用いて、リクエスト到着率に対するスループット、およびレスポンスタイムを算出することができる。このような場合には、入力データとして、一つのタスクを実行する際に消費するＣＰＵ、および、ディスクの利用時間が必要となる。
【０１９３】
また、上記の実施例では、一つのノードグループに対して、一つのタスク種が対応付けられている、という条件が設けられている。
【０１９４】
以下では、この条件を緩め、一つのグループに対して複数のタスク種が対応付けられた場合の実施例について述べる。
【０１９５】
ノードグループ構築手段１２では、システムを構成する全ノードを、例えば二つのノードグループ（ノードグループ１とノードグループ２）とに分け、ノードグループ１では、タスクグループＡに属するタスク種を実行し、ノードグループ２では、タスクグループＢに属するタスク種を実行するような制御を行なう（タスクグループＡとＢは、手続きＰのステップ１２２により構成することができる）。
【０１９６】
そのためのデータ構造として、タスク種−ノードグループ対応表１９４（図１４参照）を用いる。
【０１９７】
図１４には、タスク種（タスクＩＤ）２の到着率Λが許容到着率Λ＿ｌｉｍ以上であるため、タスクグループＢに分類され、タスク種１と３との到着率が許容到着率未満であるため、ノードグループＡに分類された時に、タスク種１と３とがノードグループ１に割り当てられ、タスク種２がノードグループ２に割り当てられた場合の対応表の例が示されている。
【０１９８】
ノードグループＢに割り当てられるノード数としては、図１３のステップ１２３で算出されるＮｂを割り当て、ノードグループＡに割り当てられるノード数としては、Ｎ−Ｎｂを割り当てる（ここで、Ｎは全ノード数を示す）。
【０１９９】
タスク送信手段１５（図１参照）は、タスク種−ノードグループ対応表１９４（図１４参照）を参照して、タスク種ｊに属するタスクを転送するノードグループを決定する。
【０２００】
上記実施例においては、ノードの処理能力が全て等しい場合を仮定していた。
【０２０１】
以下では、ノードの処理能力が異なる場合について、すなわち、ノードは、処理能力に応じて分類され、システム全体に、Ｋ種類のノードがある場合の実施例を説明する。
【０２０２】
なお、ノードグループｊに割り当てられているノード種ｋの個数を、Ｎ（ｊ，ｋ）と表記する。
【０２０３】
また、１ノードの許容到着率をノードの種類ごとに与え、タスク種ｊのノード種ｋに対する許容到着率をλ（ｊ，ｋ）と表記する。
【０２０４】
更に、ノードグループｊ上でタスク種ｊが実行されるような状況を想定する。
【０２０５】
この場合、上記実施例で用いていたｊ番目のノードグループに割り当てるノード数を求める関数Ｎ＿ｈ（ｊ）の代わりに、以下で示されるような手続きに従って、割り当てるノード数を決定する。この手続きは、図１３のステップ１２３を、図１５のステップ１２３０〜１２３２で、また図１３のステップ１２４を、図１６の１２４１〜１２４２で置き換えたものである。
【０２０６】
図１５を参照すると、ステップ１２３０では、
タスクグループＢのタスク種ｊ全てに対して、下記の二つのステップ（１２３１と１２３２）を実行する。
【０２０７】
次のステップ１２３１では、
下記の条件を満たすノード数の組、Ｎ’（ｊ，ｋ）（ｋ＝１〜Ｋ）を全て求める。
【０２０８】
Λ＿Ｌｉｍ（ｊ）≧Ｎ’（ｊ，１）λ（ｊ，１）＋Ｎ’（ｊ，１）λ（ｊ，１）＋…＋Ｎ’（ｊ，Ｋ）λ（ｊ，Ｋ）            …（１７）
【０２０９】
次のステップ１２３２では、
得られたノード数の組Ｎ’（ｊ，１）の中から、手続き実行直前のノード数の組Ｎ（ｊ，ｋ）を用いて算出される次式（１８）の値（距離）が最小となるＮ（ｊ，ｋ）を、新たな割り当てノード数の組とする。
｜Ｎ’（ｊ，１）−Ｎ（ｊ，１）｜
＋｜Ｎ’（ｊ，２）−Ｎ（ｊ，２）｜
＋・・・
＋｜Ｎ’（ｊ，Ｋ）−Ｎ（ｊ，Ｋ）｜        …（１８）
【０２１０】
また、ノード種ｋに関して、Ｎ（ｊ，ｋ）の総和をＮｂ（ｋ）とする（ただし、ｊはタスクグループＢに属するタスク種）。
【０２１１】
図１６を参照すると、ステップ１２４１では、
タスクグループＡのタスク種に対して割り当て可能なノード数をノード種ｋごとに算出する。すなわち、
Ｎａ（ｋ）＝Ｎ（ｋ）−Ｎｂ（ｋ）（ｋ＝１〜Ｋ）    …（１９）
とする。
【０２１２】
ステップ１２４２では、
タスクグループＡの各タスク種ｊに対して、Ｎａ（ｋ）を適切に割り当てる。このような割り当て方の一例は、ノードグループを構成するｋ番目のノード種に対する仮想的な使用率がバランスするような割り当て方のことである。このような条件を具体的に記述すると下記の通りである。
【０２１３】
ノード種ｋを用いた時のタスク種ｊのスループットをΦ（ｊ，ｋ）とし，ｊ番目のノードグループのノード種ｋのノード数をｎ（ｊ，ｋ）とする。
【０２１４】
この時、ｎ（ｊ，ｋ）個のノードで達成できるスループットの最大値は、ノード種ｋを１ノード用いて達成できる最大スループットＴ＿ｍａｘ（ｊ，ｋ）を用いて、
ｎ（ｊ，ｋ）×Ｔ＿ｍａｘ（ｊ，ｋ）        …（２０）
と表すことができる。
【０２１５】
この最大スループットに対する現在のスループットの比を
β（ｊ，ｋ）＝Φ（ｊ，ｋ）／（ｎ（ｊ，ｋ）×Ｔ＿ｍａｘ（ｊ，ｋ））  …（２１）
とする。
【０２１６】
この時、β（ｊ，ｋ）がｊ＝１〜Ｊに対して、ほぼ同じ値を取る時、ノードグループを構成するｋ番目のノード種に対する仮想的な使用率が「バランスする」と呼ぶ。このような条件を満たすように、ｎ（ｊ，ｋ）を定めることで、最適な割り当てノード数を算出することができる。
【０２１７】
ただし、
ｎ（１，ｋ）＋…＋ｎ（ｊ，ｋ）＝Ｎａ（ｋ）            …（２２）
である。
【０２１８】
次に、グローバル負荷分散装置１内に、グローバルキューイング手段１６を持つ場合の実施例の拡張について説明する。この場合、タスク送信手段１５が、ノードに対してタスクを送信する際に、送信先候補のノード上にある滞留タスク数が、ある一定値を超えた時には、そのノードを、送信対象ノードとはせずに、他の送信先候補のノードを選択する。送信先候補として上がった全てのノード上の滞留タスク数が、一定値を超えていたときには、タスク送信手段１５は、タスクをノードに送信せずに、グローバルキューイング手段上に、タスクを保存する。
【０２１９】
そのようなタスクは、あるノード上でのタスク処理が完了した時に、そのノード上に送信される。なお、タスクを送信するかどうかという判断に用いる滞留タスク数は、許容レスポンスＲ（ｊ）と、許容到着率λ（ｊ）と、から、リトルの公式を用いて、算出される値であるＲ、
（ｊ）×λ（ｊ）                    …（２３）
を採用することが考えられる。あるいは、余裕を見込んで、
α×Ｒ（ｊ）×λ（ｊ）、          …（２４）
ただし、０≦α＜１、としても良い。
【０２２０】
次に、本発明の第２の実施例を、図面を参照して説明する。本実施例は、本発明の第２の実施の形態に対応するものである。ただし、まず以下の前提(前提１)を置く。
【０２２１】
前提１：
０からｎ−１の絶対ノードＩＤを持つｎ個のノードからなるクラスタで、到着したタスクを処理する。
【０２２２】
またノードに対しては、相対ノードＩＤが定義される。相対ノードＩＤは、例えばノードｉ(ｉは０以上ｎ−１以下の整数)から見ると、ノードｉ＋１は、相対ノードＩＤが「１」のノードである、というように計算される。
【０２２３】
ノードｉからみたノードｊの相対ノードＩＤの計算式は、
(ｉ−ｊ＋ｍ)  ｍｏｄ  ｍ                    …（２５）
となる。ただし、ｍはある自然数である。以下、単に、ノードＩＤと言えば、相対ノードＩＤを指すものとする。
【０２２４】
負荷情報は、ボトルネックになるリソースに関する情報であり、ここでは、ローカルキューイング手段のキュー長を負荷情報とする。負荷情報は実数で表されるが、負荷の移送単位は、整数とする。
【０２２５】
実行されるのは、キューにつながれたタスクのうち、先頭から定数個のみであり、移送可能なタスクは、まだ実行されていないタスクである。ただし、ここでは、キューの先頭から一つ目のタスクのみが実行可能であるとする。
【０２２６】
本実施例では、負荷情報共有手段３２は、他の全ノードの情報を共有しており、ノード優先度割り当て手段３７は、優先度として、ノードＩＤを割り当てる(値が小さい方が優先度が高い)。
【０２２７】
負荷分散手段３１の均衡度計算手段３８（図４参照）は、全ノードの負荷の平均値以上の最小の整数を算出する。
【０２２８】
そして、本実施例において、負荷分散手段３１は、前述した図６の流れ図に従って動作する。
【０２２９】
図２０に、８ノードからなるクラスタでの本実施例の動作例を示す。図２０には、表形式で、負荷移送対象ノード毎に、
・対象ノードの負荷情報の初期値(initial load info.)と、
・タスク移送判断後のノードの負荷情報(modified load info.)、
・タスク移送判断前のunderの値(under(b))、
・タスク移送判断後のunderの値(under(a))、
・タスク移送判断後のoverの値(over)
が示されている。
【０２３０】
ノード０（自ノード）は、自ノードの負荷(=５)と負荷情報から算出した閾値threshold(=「３」)の差が正であるので、自ノードが過負荷であることを認識して、負荷移送を開始する。
【０２３１】
そして、ノード０は、優先度が最も高いノード１から順に、移送先ノードを探す。
【０２３２】
負荷移送対象ノードの負荷情報と、閾値「threshold」の差を、順に、「under」に加算していくと、ノード６で、初めて、「under」が「１」以上になるので、ノード６にタスクを一つ移送し、自ノードとノード６の負荷情報を更新して、負荷分散を終了する。
【０２３３】
以上がノード０の動作であるが、他のノードも同様の動作を行うことに注意する。図２０には、過負荷なノード１、ノード２、ノード３からのタスク移送も、破線で示した。
【０２３４】
同じ負荷状態を仮定して、全ノードで最も負荷が軽いノードであるノードLと、自ノードの負荷を比較して、その差が、Δ(ただし、ここではΔ＝１とする)になるように、ノードLにタスクを一つずつ移送した場合、ノード６には、４つのタスク移送がなされ、群集効果が発生する。
【０２３５】
本実施例で群集効果が発生していないのは、図２０に示した通りである。
【０２３６】
三つのノードx, y, zに対して、
xがyに割り当てる優先度が、xがzに割り当てる優先度よりも高ければ、
yがzに割り当てる優先度は、yがxに割り当てる優先度よりも高く、
zがxに割り当てる優先度は、zがyに割り当てる優先度よりも高い、
となるような、優先度割り当てを本明細書（説明部）及び特許請求の範囲では、「循環単調増加優先度割り当て」と呼ぶ。本実施例では、任意の三つのノードに対して、循環単調優先度割り当てが成り立っている。
【０２３７】
したがって、あるノードへの負荷移送を行う場合、そのノードよりも近くのノードによる負荷移送が起こるかを考えれば、群集効果を防ぐことができる。
【０２３８】
一方、一部の三つのノード間の優先度が、循環単調増加になっていなければ、その分群集効果が発生する。
【０２３９】
どの程度の群集効果が発生するかは、負荷の状態と、循環単調増加優先度割り当てにならない三つノードの組み合わせの数に依存する。
【０２４０】
次に、本発明の第３の実施例を、図面を参照して説明する。本実施例は、第３の実施の形態に対応するものである。
【０２４１】
本実施例では、上記した「前提１」を仮定しており、前記第２の実施例と同じく、負荷情報共有手段３２、ノード優先度割り当て手段３７、均衡度計算手段３８を持つが、移送タスク決定手段３９は、図６のステップＡ９を、図７のステップＢ１〜Ｂ５で置き換えて動作する。
【０２４２】
図２１に、８ノードからなるクラスタでの本実施例の動作例を示す。図２１に表形式で表すものは、前記第２の実施例と同様である。
【０２４３】
第２の実施例における動作とは異なり、ノード０は、負荷の量「under」が２以上のノードに対してはタスクを、「under」分移送する。
【０２４４】
そして、全ノードを移送対象ノードとして選択するか、過負荷状態が解消される(「over」が「０」になる)と、負荷分散を終了する。
【０２４５】
したがって、最初に「under」が「１」以上になったノードが全ての過負荷分のタスクを受け入れられない場合、複数ノードにタスクが移送されることになる。図２１では、ノード２において「under」が３になるので、ノード２に３つのタスクを移送している。しかし、まだ「over」は「１」以上なので、さらにタスク移送先ノードを探し、ノード３と４に２つのタスクを、ノード７に、１つのタスクを移送する。
【０２４６】
同じ負荷状態を仮定して、全ノードで最も負荷が軽いノードであるノードLと自ノードの負荷を比較して、その差がΔ(ただし、ここではΔ＝１とする)になるように、ノードLにタスクを一つずつ移送する場合、負荷分散終了後であってもノード０の過負荷状態はほとんど解消されない。
【０２４７】
本実施例では、複数タスクの移送を許すため、負荷分散終了後には、負荷が均衡する。通常、複数のタスクを移動すると、群集効果が強まるが、本実施例では、群集効果が生じていない。これは、他のノードのタスク移送を考慮して、自ノードのタスク移送を決定しているためである。
【０２４８】
次に、本発明の第４の実施例を図面を参照して説明する。本実施例は、上記第４の実施の形態に対応するものである。
【０２４９】
本実施例では、前提１の下、空間精度を落とした負荷情報を共有する場合の負荷分散を行う。
【０２５０】
空間精度は、一ノード分の負荷情報が、何ノード分の負荷情報を表しているか、ということを表す。
【０２５１】
例えば、ある４ノードの負荷の平均値が負荷情報として送信され、この平均値をこれらのノードの負荷情報とするとすれば、この情報の空間精度は、１／４とする。つまり、空間精度は、次式（２６）で定義される。
【０２５２】
空間精度＝１／（その情報で表すノード数）        …（２６）
【０２５３】
本実施例の負荷情報共有手段３２（図３参照）では、各ノードは、
ノード０（自ノード）の負荷と、
ノードｇ1から送信されたノードｇ1〜ｇ2−1の負荷の平均、
ノードｇ2から送信されたノードｇ2〜ｇ3−1の負荷の平均、…、
ノードｇk-1から送信されたノードｇk-1〜ｇk−1の負荷の平均
を情報として持つ。
【０２５４】
ただし、
ｇk-1 < ｎ <= ｇk、かつ、ｍ ＝  ｇk
であり、
ｉ < ｊの時、
ｇi+1−ｇi <= ｇj+1−ｇj
が成り立つ。
【０２５５】
そして、ｇiは、静的に定められる値である。また、負荷情報は、周期的に更新される(この情報共有方法は、前記先行出願１の方法によって実現される)。
【０２５６】
図６のステップＡ１での均衡度計算手段３８による閾値thresholdの計算は、以下のように行われる。ただし、load(i)は、自ノードが持つノードｉの負荷情報である。
【０２５７】
threshold  ={load(0)+Σi=1k-2load(gi)×(gi+1- gi)+load(gk-1)×(n-gk-1)}/n
…（２７）
【０２５８】
ただし、演算記号Σi=1k-2で始まる項は、load(gi)×(gi+1- gi)のi=1からi=k-2までの総和を表している。
【０２５９】
さらに、図６のステップＡ２のノード間距離の決定では、前記第３の実施例と同様に、ノード優先度割り当て手段３７はノードＩＤを割り当てる。移送タスク決定手段３９は、前記第３の実施例と同様に動作する。
【０２６０】
負荷情報共有手段３２からプッシュされるのは、ノードｇiの情報のみであり、ノードｇi+1〜ノードｇi+1−1の情報はプッシュされない。
【０２６１】
そこで、負荷情報管理手段３６は、ノードｇi+１〜ノードｇi+1−1の情報問い合わせを受けた場合、基本的に、ノードｇiの情報を返すことで、負荷情報を、再構築する。この操作を本明細書（説明部）及び特許請求の範囲では「単純空間精度補完」と呼ぶ。
【０２６２】
ただし、移送タスク決定手段３９からの情報更新が行われたノードに関しては、この更新後に、ノードｇiの情報がプッシュされていなければ、移送タスク決定手段３９によって更新された情報を返す。
【０２６３】
本実施例の、８ノードからなるクラスタでの動作例について説明する。まず、動作例で用いる情報共有方法を、図２２に示す。
【０２６４】
図２２に示す例では、
ノード０は、
・ノード1から、ノード１の情報を、
・ノード２から、ノード２とノード３の情報の平均を、
・ノード４から、ノード４とノード７の情報を
受け取っている。
【０２６５】
ノード２がノード２と３の情報の平均を送信できるのは、ノード２がノード３からノード３の情報を受け取っているからであり、ノード４がノード４と７の情報の平均を送信できるのは、ノード５からノード５の情報を、ノード６からノード６とノード７の平均を受け取っているためである。
【０２６６】
図２３は、本実施例の動作の一例を示す図である。図２３の下部の表形式で表すものは、前記第２の実施例と同様である。
【０２６７】
ノード０（自ノード）は、負荷情報から算出した閾値threshold(=「２．５」)から、負荷の量「over」(=「３」)個のタスクを、他ノードに移送する。そして、ノード1から順に移送先ノードを探す。ノードＩＤが若いノードの情報ほど空間精度が高くなっている。
【０２６８】
こうすると、近くのノードのみを使って、負荷不均衡が解消できることが、高い精度の情報のみを使って、負荷不均衡が解消できることにつながり、より効率のよい負荷分散が可能になる。
【０２６９】
さらに、遠くのノードに負荷を投げる場合でも、情報精度の低下の影響は抑えられるようになっている。なぜなら、各ノードが近くのノードとはより正確な負荷分散を行うため、基本的には遠くにあるノードの負荷を同一とみなせるからである。
【０２７０】
図２３に示す例では、単純空間精度補完を行っているため、ノード２と３の負荷を「１．５」とみなし、ノード４〜７の負荷を「２」とみなしている。
【０２７１】
実際の個々のノードの負荷には、ばらつきがある。例えば、ノード４の負荷は「４」であるが、ノード５の負荷は「０」である。しかし、ノード４も負荷分散を行い、ノード５に、タスクの移送を行うために、この差は緩和される。そこで、ノード０は、これらのノードは同じ負荷であるとみなして、タスクの移送を行うことができる。
【０２７２】
ノード数を「ｎ」とし、情報更新の周期を「ｐ」とすると、本実施例で用いた負荷情報共有方法のコストはＯ(ｐｎ log ｎ)であり、全ノードの情報を共有する場合のコスト、O(ｐｎ2)に比べて低コストである。
【０２７３】
それにも関わらず、本実施例が負荷分散は比較的正確に行うことができるのは、本実施例では、近くのノードの情報は、比較的正確な情報であり、近くのノードには、優先的にタスクを移送するためである。
【０２７４】
さらに、本実施例では、他ノードの負荷移送を考慮し、複数タスクの移送を許しているため、低コストで群集効果の影響を受けずに高速に負荷の均衡を図ることができる。
【０２７５】
次に、本発明の第５の実施例を図面を参照して説明する。本実施例は、前記第５の実施の形態に対応する。本実施例は、「前提１」を前提とする。
【０２７６】
実行可能なのは、キューの先頭からＱ個のタスクであるとする。この時、ノードのローカルキューイング手段３５（図３参照）は、実行数別に、実行数が「１」から「Ｑ」の時のレスポンスタイムの総和と、測定個数を保持する。また、有効サンプリング数は、「１０」、付加実行数は「１」とする。
【０２７７】
本発明の第５の実施の形態における図９のステップＣ３において、有効な平均レスポンスタイムが求められたとし、平均レスポンスタイムが求まる実行数の集合をＶ’とする。
【０２７８】
そして、Ｖ’のうち最大の要素をａとして、ＶをＶ’と｛ａ＋１｝の和集合とする。Ｌｉｔｔｌｅの公式（滞在タスク数は、タスク到着率と平均レスポンスタイムの積に等しい）にしたがって、実行数を平均レスポンスタイムで割ることで、Ｖ’に属する実行数に関してのスループットが求まる。
【０２７９】
ｋをＶに属する実行数として、実行数がｋの時のスループットをＴ（ｋ）とすると、Ｔ（ｋ）とＴ（ｊ）がほぼ等しくなるような最小のｋを見つけ、これを望ましい実行数Ｒとする。
【０２８０】
ただし、ｊは、Ｖに属するｋより大きい実行数のうち最小のものである。また、
Ｔ（ａ＋１）＝Ｔ（ａ）            …（２８）
とし、Ｖが空である場合には、Ｒの値は変化しないとする。
【０２８１】
図２４は、Ｑ＝４の時のレスポンスタイムテーブルである。したがって、実行数が「４」以下の場合のレスポンスタイムの総和と測定個数が有効である。この時、有効サンプリング数以上のレスポンスタイムの総和が記録されているのは、同時実行数が「１」と「２」の場合である(「５」以上の値は考慮しない)。
【０２８２】
そこで、レスポンスタイムの総和を測定個数で割ってレスポンスタイムを求めると、実行数が「１」のときの平均レスポンスタイムは「０．９４」、実行数が「２」のときの平均レスポンスタイムは「１．６３」である。
【０２８３】
したがって、
Ｔ（１）＜Ｔ（２）＝Ｔ（３）
となるので、
Ｒ＝２とする。
【０２８４】
図２５は、Ｑ＝３の時のレスポンスタイムテーブルである。この時、有効サンプリング数以上のレスポンスタイムの総和が記録されているのは、同時実行数が、「１」と「２」と「３」の場合である。
【０２８５】
Ｔ（１）＜Ｔ（２）＜Ｔ（３）＝Ｔ（４）
となるので、
Ｒ＝３とする。
【０２８６】
通常は、入出力（Ｉ／Ｏ）待ち等によって、タスクにリソースが割り当てられていてもタスクを実行できない時間が存在する。従って、複数のタスクを同時に実行すれば、一つのタスクが実行できなくとも、他のタスクを実行することができるようになるため、スループットが向上する。
【０２８７】
その一方で、一度実行を開始したタスクを移送する場合、タスクを最初から実行しなおすか、タスクの状態をも移送して途中から実行するかのいずれかの方法をとる必要があり、実行開始前のタスクを移送するのに比べて、オーバーヘッドが大きいため、本発明では、実行開始前のタスクのみを移送対象としている。
【０２８８】
そのため、同時に実行するタスクの数を増やすと、個々のノードのスループットは向上するが、その分負荷均衡を図るためのタスク移送に制限がつく。
【０２８９】
本実施例では、動的に同時に実行するタスク数を決定することで、ノード毎のスループットの向上と、負荷不均衡によるスループットの低下のトレードオフを行うことで、システム全体のスループットを向上させる。
【０２９０】
次に本発明の第６の実施例を図面を参照して詳細に説明する。本実施例は、前記第６の実施の形態に対応するものである。
【０２９１】
本実施例では、ノードグループ構築手段１２（図１参照）は、ノードグループを変更するときに、変更されたノードグループに含まれる各ノードに同じグループに含まれるノードは何か（ノードグループデータ）を送信する。
【０２９２】
例えば、１６ノード（ノード０〜１５、本実施例では、ノードＩＤは、絶対ノードＩＤとする）からなるクラスタで、
・ノード０〜４が、第一のノードグループ、
・ノード５〜７が、第二のノードグループ、
・ノード８〜１５が第三のノードグループ、
を構成しているときに、
グローバル負荷分散装置１が、
ノード５を、第一のノードグループに移す判断を行うと、
グローバル負荷分散装置１は、
ノード０〜５には、０〜５までの整数をノードグループのデータとして送信し、
ノード６〜７には、６〜７までの整数をノードグループのデータとして送信する。
【０２９３】
ノードグループデータを受けとったノードの負荷情報共有手段３２（図３参照）は、この情報に基づいて情報共有方法を変更する。
【０２９４】
各ノードがノードグループ内の他の全ノードに負荷情報を送信している状況を仮定すると、ノードグループの変更前に、第一のノードグループに属するノード０は、ノード１〜４に情報を送信していたが、変更後は、ノード１〜５に情報を送信する。
【０２９５】
情報がないノードは、負荷分散対象ノードとして選択されないため、グループ間の負荷移送は行われない。
【０２９６】
ノードグループデータを受け取ったノードの負荷情報共有手段３２は、前記先行出願１に示される通り、情報共有対象となるノード数によらない形での情報共有方法が与えられているため、具体的に、どのノードに情報を送信するのか、またはどのノードから情報を受信するのかをノードグループデータから再構築できる。
【０２９７】
図２６は、ノードグループ変更時の動作の一例を示す図である。
【０２９８】
図２６には、ノード０、１、２の３ノードからなるノードグループに、さらに、３つのノード（ノード３、４、５）を加えた時の動作が示されている。
【０２９９】
ノードを追加した直後は、負荷の不均衡が大きいが、本発明における負荷分散手段３１(図３、図４参照)によって、瞬時に負荷均衡状態へと移行する。
【０３００】
これによって、あるタスク種による負荷が急激に増加したとしても、他のタスク種の実行が妨げられないだけでなく、変動するタスク種毎の負荷に速やかに追従できるため、より少ないリソースで、事前に定められたレスポンスタイムを満足させることができる。
【０３０１】
以上本発明を上記実施の形態及び実施例に即して説明したが、本発明は、上記実施例にのみ限定されるものでなく、特許請求の範囲の各請求項の発明の範囲内で当業者であればなし得るであろう各種変形、修正を含むことは勿論である。
【産業上の利用可能性】
【０３０２】
本発明によれば、複数の計算ノードから構成されるクラスタシステムを、用途に応じて複数のグループに分割し、実行時の負荷状況に応じてグループを構成するノード数を適切に保ち、システム全体の性能を向上させるような用途に適用できる。
【０３０３】
また、突発的に過負荷状態が生じたとしても、グループの構成変更を行うことで生じる負荷のアンバランスを改善し、システム全体の性能を向上させる用途にも適用できる。
【０３０４】
特に、ウェブサーバやアプリケーションサーバに対する負荷分散や、ウェブサーバやアプリケーションサーバとして用いるサーバ数を実行時に最適な台数に保つという用途にも適用可能である。
【図面の簡単な説明】
【０３０５】
【図１】本発明の第１の実施の形態の構成を示す図である。
【図２】本発明の第１の実施の形態の負荷分散装置の処理手順を説明する流れ図である。
【図３】本発明の第２の実施の形態の構成を示す図である。
【図４】本発明の第２の実施の形態の負荷分散手段の構成を示す図である。
【図５】本発明の第２の実施の形態の動作を示す流れ図である。
【図６】本発明の第２の実施の形態の動作における、タスクの移送先ノード決定時の動作を示す流れ図である。
【図７】本発明の第３の実施の形態の動作における、タスクの移送先ノード決定時の動作を示す流れ図である。
【図８】本発明の第５の実施の形態のレスポンスタイムテーブルを示す図である。
【図９】本発明の第５の実施の形態の動作における、レスポンスタイムテーブル更新時の動作を示す流れ図である。
【図１０】本発明の第６の実施の形態の構成を示すブロック図である。
【図１１】（Ａ）、（Ｂ）は、本発明の実施の形態で用いられる、タスク−ノード特性の一例をグラフ表示した図である。
【図１２】本発明の実施の形態において、システム構成入力手段１３に入力するシステム運用条件とタスク−ノード特性の一例を示す図である。
【図１３】本発明の実施の形態において、ノードグループに割り当てるノード数を算出する手続きの一例を示す流れ図である。
【図１４】本発明の実施の形態において、タスク種とノードグループの対応を管理する表の構成の一例を示す図である。
【図１５】本発明の実施の形態において、図１３のステップ１２３を拡張する手続きの一例を示す流れ図である。
【図１６】本発明の実施の形態において、図１３のステップ１２４を拡張する手続きの一例を示す流れ図である。
【図１７】本発明の実施の形態において、タスク到着率を管理する表の構成の一例を示す図である。
【図１８】本発明の実施の形態において、ノード性能を管理する表の構成の一例を示す図である。
【図１９】本発明の実施の形態において、ノードグループの構成を管理する表の構成の一例を示す図である。
【図２０】本発明の第２の実施例におけるタスク移送を説明するための図である。
【図２１】本発明の第３の実施例におけるタスク移送を説明するための図である。
【図２２】本発明の第４の実施例に情報共有を説明するための図である。
【図２３】本発明の第４の実施例におけるタスク移送を説明するための図である。
【図２４】本発明の第５の実施例におけるレスポンスタイムテーブルを示す図である。
【図２５】本発明の第５の実施例にレスポンスタイムテーブルを示す図である。
【図２６】本発明の第６の実施例におけるタスク移送を説明するための図である。
【符号の説明】
【０３０６】
１    グローバル負荷分散装置
１１    タスク受信装置
１２    ノードグループ構築手段
１３    システム構成入力手段
１４    実行性能測定手段
１５    タスク送信手段
１６    グローバルキューイング手段
１９１    タスク到着率管理表
１９２    ノード性能管理表
１９３    ノードグループ構成表
１９４    タスク種−ノードグループ対応表
２    スイッチング装置
３−ｉ    ノード
３１    負荷分散手段
３２    負荷情報共有手段
３３    タスク送受信手段
３４    タスク実行手段
３５    ローカルキューイング手段
３６    負荷情報管理手段
３７    ノード優先度割り当て手段
３８    均衡度計算手段
３９    移送タスク決定手段
３１０    レスポンスタイムテーブル
【図１】
2005148911.tif 000003
【図２】
2005148911.tif 000004
【図３】
2005148911.tif 000005
【図４】
2005148911.tif 000006
【図５】
2005148911.tif 000007
【図６】
2005148911.tif 000008
【図７】
2005148911.tif 000009
【図８】
2005148911.tif 000010
【図９】
2005148911.tif 000011
【図１０】
2005148911.tif 000012
【図１１】
2005148911.tif 000013
【図１２】
2005148911.tif 000014
【図１３】
2005148911.tif 000015
【図１４】
2005148911.tif 000016
【図１５】
2005148911.tif 000017
【図１６】
2005148911.tif 000018
【図１７】
2005148911.tif 000019
【図１８】
2005148911.tif 000020
【図１９】
2005148911.tif 000021
【図２０】
2005148911.tif 000022
【図２１】
2005148911.tif 000023
【図２２】
2005148911.tif 000024
【図２３】
2005148911.tif 000025
【図２４】
2005148911.tif 000026
【図２５】
2005148911.tif 000027
【図２６】
2005148911.tif 000028