米国特許情報 | 欧州特許情報 | 国際公開(PCT)情報 | Google の米国特許検索
 
     特許分類
A 農業
B 衣類
C 家具
D 医学
E スポ−ツ;娯楽
F 加工処理操作
G 机上付属具
H 装飾
I 車両
J 包装;運搬
L 化学;冶金
M 繊維;紙;印刷
N 固定構造物
O 機械工学
P 武器
Q 照明
R 測定; 光学
S 写真;映画
T 計算機;電気通信
U 核技術
V 電気素子
W 発電
X 楽器;音響


  ホーム -> 計算機;電気通信 -> 株式会社野村総合研究所

発明の名称 格子型コンピュータシステム、タスク割り当てプログラム
発行国 日本国特許庁(JP)
公報種別 公開特許公報(A)
公開番号 特開2007−206987(P2007−206987A)
公開日 平成19年8月16日(2007.8.16)
出願番号 特願2006−25142(P2006−25142)
出願日 平成18年2月1日(2006.2.1)
代理人 【識別番号】100105924
【弁理士】
【氏名又は名称】森下 賢樹
発明者 宇和田 弘美
要約 課題
グリッドコンピューティングにおいて、ノード間の接続形態を考慮したタスク割り当てをする。

解決手段
それぞれがプロセッサを備える複数のノードを格子状に接続させた格子型コンピュータシステムにおいて、複数のノードとノード間接続装置の接続形態にしたがって論理ノードからなる格子モデルが作成される。格子モデルは、外部からなされる一つまたは複数のサービス要求に対応付けられた一つ以上の論理ノードを含む方形領域に分割される。方形領域内のいずれかの論理ノードにおいて実行されるスケジューラは、該方形領域に対応するサービス要求のジョブを構成するタスクの並列度および直列度に基づいて、方形領域内の他の論理ノードにタスクを処理するためのタスク処理プログラムを割り当てる。
特許請求の範囲
【請求項1】
それぞれがプロセッサを備える複数のノードを格子状に接続させた格子型コンピュータシステムにおいて、
格子型コンピュータシステムにおける複数のノードとノード間接続装置の接続形態にしたがって作成された論理ノードからなる格子モデルが、外部からなされる一つまたは複数のサービス要求に対応付けられた一つ以上の論理ノードを含む方形領域に分割されており、
この方形領域内のいずれかの論理ノードにおいて実行されるスケジューラが、該方形領域に対応するサービス要求のジョブを構成するタスクの並列度および直列度に基づいて、方形領域内の他の論理ノードにタスクを処理するためのプログラムを割り当てることを特徴とする格子型コンピュータシステム。
【請求項2】
前記スケジューラは、並列して実行可能なタスクを処理するためのプログラムを前記方形領域内で並列する論理ノードにそれぞれ割り当てることを特徴とする請求項1に記載の格子型コンピュータシステム。
【請求項3】
前記格子モデル内の各論理ノードには、それぞれ対応する物理ノードの処理能力に基づいて多重度が定められており、
前記スケジューラは、並列して実行可能なタスクを処理するプログラムを割り当てるとき、前記多重度を参照することを特徴とする請求項2に記載の格子型コンピュータシステム。
【請求項4】
前記スケジューラは、依存関係の存在するタスク群について、前記方形領域内で前記タスク群に含まれるタスク数と同数の隣接するノードを選択して、それぞれのタスクを処理するプログラムを割り当てることを特徴とする請求項1ないし3のいずれかに記載の格子型コンピュータシステム。
【請求項5】
前記スケジューラは、依存関係の存在するタスク群に含まれるいずれかのタスクが並列して実行可能な場合に、タスク群に含まれる各タスクの並列度の平均値を使用して、前記方形領域内で割り当てるべきノード数を決定することを特徴とする請求項4に記載の格子型コンピュータシステム。
【請求項6】
各ノードと直結されており他のノードを経由せずにアクセス可能な記憶装置をさらに備え、
前記記憶装置は請求項1ないし4のいずれかに記載のプログラムを格納し、前記スケジューラからの指令に応じて、前記プログラムを該当するノードに送信することを特徴とする格子型コンピュータシステム。
【請求項7】
それぞれがプロセッサを備える複数のノードを格子状に接続させた格子型コンピュータシステムにおいて、該システムは少なくとも一つの親ノードと複数の子ノードを有し、
前記親ノードは、格子型コンピュータシステムにおける複数のノードとノード間接続装置の接続形態にしたがって論理ノードからなる格子モデルを作成し、該格子モデルを外部からなされる一つまたは複数のサービス要求に対応付けられた一つ以上の論理ノードを含む方形領域に分割するスーパースケジューラを有し、
前記子ノードは、前記方形領域に対応するサービス要求のジョブを構成するタスクの並列度および直列度に基づいて、方形領域内の他のノードにタスクを処理するためのプログラムを割り当てるスケジューラを有することを特徴とする格子型コンピュータシステム。
【請求項8】
それぞれがプロセッサを備える複数のノードを格子状に接続させた格子型コンピュータシステムにおいて、
格子型コンピュータシステムにおける複数のノードとノード間接続装置の接続形態にしたがって作成された論理ノードからなる格子モデルが、外部からなされる一つまたは複数のサービス要求に対応付けられた一つ以上の論理ノードを含む方形領域に分割されており、
前記方形領域内のいずれかのノードにおいて実行されることで、該方形領域に対応するサービス要求のジョブを構成するタスクの並列度および直列度に基づいて、方形領域内の他のノードにタスクを処理するためのプログラムを割り当てる機能を発揮することを特徴とするタスク割り当てプログラム。
発明の詳細な説明
【技術分野】
【0001】
本発明は、複数のノードを格子状に接続したグリッドコンピューティング技術に関し、より詳細には、格子型のコンピュータシステムにおけるタスク割り当て技術に関する。
【背景技術】
【0002】
ユーザがウェブブラウザ等を使用してインターネット経由でサーバシステムに送信するサービス要求は、年々増大している。このようなウェブブラウザからなされるサービス要求は、ユーザが対話的に実行するためにサーバとのセッションが長時間に及ぶ場合がある。セッションからの断続的な要求にも即時応答するためには、セッション情報やプログラムをサーバのメモリ上に保持しておかなくてはならない。サービス要求の増大とともにサーバが必要とするメモリリソースも増加する傾向にあるため、メモリリソースを安価に確保したいという要請が存在する。
【0003】
そこで、比較的安価な複数のサーバまたはパーソナルコンピュータを網目状に接続してサービス要求から派生するタスクを分散することで、高速処理を実現するグリッドコンピューティングが注目されている。グリッドコンピューティングのユーザは、グリッドにプーリングされている処理能力や記憶容量を利用することができる。このようなグリッドコンピューティングにおいては、複数の子ノード、孫ノードのタスク割り当てを実行するスケジューラを有する親ノードを予め決定しておく必要がある。しかし、このような構成では、親ノードとその周辺のノードに負荷が偏り過ぎて、システム全体のスループットに影響を及ぼすことがある。
【0004】
最近の研究では、親ノードにスーパースケジューラを配置するとともに子ノードにもスケジューラを配置し、親ノードから子ノードが請け負ったタスクについては、子ノードに存在するスケジューラが孫ノードへのタスク割り当てを実行するようにして、親ノードの負荷を軽減する方法が考案されている(例えば、非特許文献1を参照)。また、特許文献1には、ローカルシステムの負荷状況に応じてタスク割り当て制御を行う分散処理システムが開示されている。
【非特許文献1】グリッド環境における資源管理、[online]、超高速コンピュータ網形成プロジェクト、[2005/12/20検索]、インターネット<URL:http://www.naregi.org/research/wp01.html>
【特許文献1】特開2004−13866号公報
【発明の開示】
【発明が解決しようとする課題】
【0005】
しかしながら、上記非特許文献1の技術では、利用可能なリソースがグリッド内のいずれに存在するかを考慮していないため、子ノードのスケジューラによるタスク移動が適切に実行できない可能性がある。また、上記特許文献1では、ノードが方形に接続された格子状のネットワークで適切なタスク移動を行うアルゴリズムが明示されておらず、分散システムの規模に応じたスループットを達成できない可能性がある。
【0006】
本発明はこうした状況に鑑みてなされたものであり、その目的は、ノードを格子状に接続した格子型コンピュータシステムにおいて、ノード間の接続形態を考慮したタスク割り当てをすることで、ネットワーク経由のサービス要求を効率良く捌く技術を提供することにある。
【課題を解決するための手段】
【0007】
本発明のある態様は、それぞれがプロセッサを備える複数のノードを格子状に接続させた格子型コンピュータシステムである。格子型コンピュータシステムにおける複数のノードとノード間接続装置の接続形態にしたがって作成された論理ノードからなる格子モデルが、外部からなされる一つまたは複数のサービス要求に対応付けられた一つ以上の論理ノードを含む方形領域に分割されており、この方形領域内のいずれかの論理ノードにおいて実行されるスケジューラが、該方形領域に対応するサービス要求のジョブを構成するタスクの並列度および直列度に基づいて、方形領域内の他の論理ノードにタスクを処理するためのプログラムを割り当てる。
【0008】
この態様によると、ノードの接続形態にしたがって格子モデルを予め作成しておくことで、所与の方形領域内において、サービス要求の特性を考慮したタスク割り当てをすることが可能になる。
【0009】
スケジューラは、並列して実行可能なタスクを処理するためのプログラムを方形領域内で並列する論理ノードにそれぞれ割り当てる。また、格子モデル内の各論理ノードには、それぞれ対応する物理ノードの処理能力に基づいて多重度が定められており、スケジューラは、並列して実行可能なタスクを処理するプログラムを割り当てるとき、多重度を参照してもよい。さらに、スケジューラは、依存関係の存在するタスク群について、方形領域内でタスク群に含まれるタスク数と同数の隣接するノードを選択して、それぞれのタスクを処理するプログラムを割り当ててもよい。
このように、依存関係の存在するタスクの処理手順にしたがって、方形領域内で例えば左右に連続する論理ノードに直列的なタスクを割り当て、上下に連続する論理ノードに並列的なタスクを割り当てることで、タスクを連携するためのデータの流れを一方向に制限でき、ループを生じることがない。そのため、連携データが交差する位置にあたる論理ノードに突出した処理負荷がかかって、その論理ノードにおけるタスク実行に悪影響を与える状況を回避することができる。
【0010】
スケジューラは、依存関係の存在するタスク群に含まれるいずれかのタスクが並列して実行可能な場合に、タスク群に含まれる各タスクの並列度の平均値を使用して、方形領域内で割り当てるべきノード数を決定してもよい。
【0011】
本発明の別の態様もまた、格子型コンピュータシステムである。このシステムは、各ノードと直結されており他のノードを経由せずにアクセス可能な記憶装置をさらに備える。記憶装置は上述したタスク処理プログラムを格納し、スケジューラからの指令に応じて、前記プログラムを該当するノードに送信する。この態様によると、格子型コンピュータシステム内のいずれのノードも孫ノードとしてタスク処理を実行することができる。
【0012】
本発明のさらに別の態様もまた、格子型コンピュータシステムである。この格子型コンピュータシステムは、それぞれがプロセッサを備える複数のノードを格子状に接続させた格子型コンピュータシステムにおいて、該システムは少なくとも一つの親ノードと複数の子ノードを有する。親ノードは、格子型コンピュータシステムにおける複数のノードとノード間接続装置の接続形態にしたがって論理ノードからなる格子モデルを作成し、該格子モデルを外部からなされる一つまたは複数のサービス要求に対応付けられた一つ以上の論理ノードを含む方形領域に分割するスーパースケジューラを有する。子ノードは、方形領域に対応するサービス要求のジョブを構成するタスクの並列度および直列度に基づいて、方形領域内の他のノードにタスクを処理するためのプログラムを割り当てるスケジューラを有する。
【0013】
この態様によると、方形領域内でのタスクの割り当ては子ノードのスケジューラで実行されるため、親ノードのスーパースケジューラのタスク割り当て負荷を軽減することができ、処理効率の向上につながる。
【0014】
なお、以上の構成要素の任意の組合せ、本発明を方法、装置、システム、記録媒体、コンピュータプログラムにより表現したものもまた、本発明の態様として有効である。
【発明の効果】
【0015】
本発明によれば、ノードの接続形態にしたがって格子モデルを予め作成しておくことで、所与の方形領域内において、サービス要求の特性を考慮したタスク割り当てをすることが可能になる。
【発明を実施するための最良の形態】
【0016】
図1は、本発明の一実施形態に係る格子型コンピュータシステムの構成の一例を示す。本発明が対象とする「格子型コンピュータシステム」とは、サーバまたはパーソナルコンピュータ等のそれぞれがプロセッサを備える複数のノードを格子状に接続したシステムのことを言う。
【0017】
図1に示すように、格子型コンピュータシステム50は、外部から発行される要求に対して一定のサービスを提供するサーバ群30を備える。サーバ群30は、複数のサーバ42と、それらを接続する多数のルータ40を含む。複数のサーバ42(図1では三台)は、ネットワークインタフェースを介して一台のルータ40に接続され、ルータ40は隣接する別のルータ40と複数列複数行(図1では三行三列)の格子を形成するように配置されている。これら格子状に配列されたルータ40の全てと通信可能なように別のルータ34が設けられ、このルータ34はインターネット、LAN、WAN等のネットワーク32に接続される。格子型コンピュータシステム50は、企業のデータセンタ等に配置され、多数のサービス要求に同時に応答することが可能である。
【0018】
ユーザは、ウェブブラウザを使用して、格子型コンピュータシステム50に対してサービス要求を発行する。このサービス要求は、例えば、証券の発注処理や、旅行の予約処理などが含まれる。これらの例に見られるサービス要求をサーバで処理する際に、ユーザはウェブブラウザを使用して対話的にサービス要求を具体化していく。
【0019】
サーバ群30内の各サーバ42は、ルータ40を介して記憶装置36と通信可能に構成されている。サービス要求の処理に必要となるスケジューラプログラム、アプリケーションプログラム、アプリケーションの実行に必要なマスタテーブルやデータベース等は記憶装置36に格納されており、必要に応じてプログラムやデータは記憶装置36からサーバ42に送信可能となっている。記憶装置36は一般にはハードディスク装置であり、通常、複数のディスクを集めてRAIDを構成している。記憶装置36は磁気テープ装置であってもよい。
【0020】
図2は、サーバ群30を構成する各サーバ42の構成を示す。サーバ42は、プログラムにしたがって各種処理を実行するCPU12と、一時的にデータやプログラムを記憶するメモリ14と、ハードディスクドライブ、DVDディスクドライブなどの記憶装置16と、ネットワークに接続し各種の入出力処理を実行するネットワークインタフェース18と、これらを相互接続するバス20と、を少なくとも含む。サーバ42は、必要に応じて、キーボードやマウス等の入力装置、ディスプレイなどの出力装置を有していてもよい。なお、一つのサーバが二つ以上のネットワークインタフェース18を有していてもよい。
【0021】
サーバ42は、一枚の基板にコンピュータとして動作するために必要な要素、つまりCPU、メモリ、ハードディスク、バスなどが搭載されたブレードサーバであることが好ましく、サーバ群30は、このブレードサーバが筐体に複数差し込まれているような構成を取ることが好ましいが、他の形態であってもよい。
【0022】
ところで、図1に示すような複数のサーバを接続して使用するグリッドコンピューティングにおいては、グリッドを構成するノード間において、サービス要求から派生するタスクをどのように割り当てるかが大きな問題となる。
【0023】
例えば、親子関係にあるノード間の帯域がサービス要求の特性に合っていないと、親子間通信のオーバーヘッドが大きくなり、システム全体のパフォーマンスに影響を及ぼす。
また、一つのサービス要求からいくつものタスクが派生し、それらのタスク間で情報を交換する場合には、タスクが割り当てられるノードを近傍にまとめた方が効率的に要求を処理することができる。しかしながら、いくつかのサービス要求に対してグリッド内のノードの占有を自由に認めると、データフローの交差などにより特定のノードの負荷が増大し、その結果システム全体のパフォーマンスが低下してしまうおそれがある。
また、ユーザがウェブブラウザを利用して発行するサービス要求は、インタラクティブに進行するため長時間のセッションとなることが多い。したがって、サーバ側では、セッション情報を大量かつ長時間保持するための十分なメモリリソースを準備しておくことが求められる。
【0024】
以上のような事情から、グリッドコンピューティングにおいては、サービス要求の特性を考慮したタスク割り当ての必要性が高い。本実施形態では、特に格子型コンピュータシステムにおいて、サービス要求の特性に応じたタスク割り当て技術を提供するものである。
【0025】
なお、本明細書において「タスク」とは、ある目的を達成するアプリケーションのプログラムコードを分割したものをいい、並列や直列といった実行の順序が定まっているものを言う。タスクは、データベーストランザクションを含む場合もあれば、ウェブページに埋め込まれているスクリプトの実行やコンポーネント呼出しを伴うもののデータベースにはアクセスしない場合もある。
【0026】
図3は、本実施形態における処理の基本的な流れを示す。まず、格子型コンピュータシステムを構成するノード間に「経路長」の概念を導入することで、論理ノードによる格子モデルを作成する(S10)。続いて、格子型コンピュータシステムで処理するサービス要求を分析して、それぞれのサービス要求の入口となる子ノードを格子モデル内で分散して配置し、さらにそれぞれのサービス要求に割り当てるべき複数のノードを格子モデル内に確保する(S12)。最後に、サービス要求の特性にしたがってタスクを各ノードに割り当てる(S14)。以下、この順序にしたがって各処理を説明する。
【0027】
1.論理ノードによる格子モデルの作成
この処理では、格子型コンピュータシステムを構成するサーバ等の物理ノードを論理ノードにマッピングすることによって、格子モデルを作成する。これによって、以降のタスク割り当ての処理を容易に実現することができる。
【0028】
より具体的には、サーバ等のノードと、ノード間を接続するルータ等のノード間接続装置の物理的な接続形態に対し「経路長」の概念を導入する。そして、システム内のノード間の位置関係をこの経路長で代表させることによって、複数の物理ノードを一つの論理ノードにまとめることが可能になる。
なお、物理ノードと論理ノードとのマッピング情報は、後述するスーパースケジューラを有する親ノードのメモリや、記憶装置36に格納される。
【0029】
本実施形態では、ノード間の経路長を「あるノードを起点としたときに、他のノードに到達するまでに経由するルータまたはスイッチの数をカウントしたホップ数から1を引いた値」と定義する。
【0030】
具体例を挙げて説明すると、図4は、図1に示した格子型コンピュータシステム50について、図中左上に位置するハッチングをかけたサーバからのホップ数を示す図である。図4において、図1のサーバ42は正方形で表され、正方形の内部の数字がホップ数を表す。「R」はルータ40を表す。ルータ間の接続は太い曲線で、ルータとサーバ間の接続は細線で描かれている。ネットワーク32、ルータ34、記憶装置36については省略している。
【0031】
図5は、ノード間経路長を使用して図1の物理ノードを論理ノードにまとめて作成される格子モデルを示す。格子モデルにおいては、ルータは省略され、サーバを表す正方形の内部にホップ数から1を減じた値である経路長が示される。一つのルータに接続され同一の経路長を持つ複数のノードは、一つの論理ノードで表すことができる。このことを示すために、図5では格子の一点に存在する論理ノードを複数枚の正方形が重ねられた状態で表している。各論理ノード間は、物理的な距離にかかわらず一定間隔で表す。
上記ルールにしたがった結果、図1の格子型コンピュータシステム50は、三行三列の論理ノードから構成される格子モデルに帰着され、ノード間の最大経路長は「4」となる。
【0032】
図6は、ノード間接続装置としてルータの代わりにネットワークスイッチ46を介して複数のサーバ42が格子状に接続されたサーバ群60を有する格子型コンピュータシステム70の構成を示す。図1の構成と同様に、複数のサーバ42(図6では三台)がネットワークインタフェースを介して一台のスイッチ46に接続され、スイッチ46は隣接する別のスイッチ46と複数列複数行(図6では二行三列)の格子を形成するように配置されている。これら格子状に配列されたスイッチ46の全てと通信可能なように、ネットワーク32に接続された別のルータ34が設けられている。記憶装置36は、図1で説明したものと同一である。
【0033】
ルータを用いない格子型コンピュータシステム70のようなネットワークスイッチのみによるノード間接続では、経路制御ができない。そのため、実際の伝送経路が見かけ上の経路よりも冗長になる場合があり、図4、図5で示したようにホップ数から単純に経路長を定義することができない。しかしこの場合でも、いくつかのスイッチで仮想的なネットワークグループであるVLANを構成することにより、伝送経路に制約をかけることができる。
【0034】
例えば図6では、左側のスイッチ群と右側のスイッチ群がそれぞれVLAN1、VLAN2を構成している。中央の二つのスイッチはVLAN1、VLAN2の両方に属し、VLANを越えるパケットについては、ネットワークスイッチの機能を利用してブリッジする。VLANの概念は周知であるのでこれ以上の説明は省略する。
【0035】
このように、ネットワークスイッチによりVLANが構成されていることを条件とすれば、上述のルータの場合と同様に、格子型コンピュータシステムを構成するノード間に経路長を定義して論理ノードによる格子モデルを作成することができる。
【0036】
図7は、図6に示した格子型コンピュータシステム70について、図中左上に位置するハッチングをかけたサーバからのホップ数を示す図である。図4と同様にサーバ42は正方形で表され、正方形の内部の数字がホップ数を表す。「S」はスイッチ46を表す。スイッチ間の接続は太線で、スイッチとサーバ間の接続は細線で描かれている。図8は、ノード間経路長を使用して図6の物理ノードを論理ノードにまとめて作成した格子モデルを示す。図5と同様に、サーバを表す正方形の内部にはホップ数から1を減じた値である経路長が示される。図6の格子型コンピュータシステム70は二行三列の論理ノードから構成される格子モデルに帰着され、ノード間の最大経路長は「3」となる。
【0037】
図9は、二つ以上のネットワークインタフェースを備える複数のサーバ42がルータ40を介して格子状に接続されたサーバ群80を有する格子型コンピュータシステム90の構成を示す。図示するように、四台一組のサーバ42がそれぞれ左右に位置するルータ40に接続されている。左列のルータ群82は、最上列から最下列まで順序通りにルータ間が接続されているが、右列のルータ群84は、左列のルータ群82と異なる経路でルータ間が接続されている。このような構成によって、左右いずれかのルータ群のうちの一台に障害が発生した場合でも、サーバ42間でルータを越えた通信が可能になるようなバックアップシステムを構築している。
【0038】
図9の構成では、左右のルータ群のいずれに対してもノード間経路長を定義することができるが、バックアップ用の一方のルータ群は無視し、正常時に専ら使用されるルータ群、図9の例では左列のルータ群82を基準としてノード間経路長を定義すればよい。
【0039】
図10は、図9に示した格子型コンピュータシステム90について、図中最上段に位置するハッチングをかけたサーバから左列のルータ群82を経由したときのホップ数を示す図である。図4と同様にサーバ42は正方形で表され、正方形の内部の数字がホップ数を表す。「R」はルータ40を表す。図10に示した例では、同じ行に配置されたノードの経路長は同一の値になる。図11は、ノード間経路長を利用して図9の物理ノードを論理ノードにまとめて作成した格子モデルを示す。図11の例では、論理ノードが直列に接続された格子モデルとなる。
【0040】
上述した三種類の格子型コンピュータシステムでは、一つのルータの下に配置されるサーバ(ノード)の数は全てのルータについて同一であったが、サーバの数が異なっている場合でもノード間経路長は同様に定義される。
【0041】
例えば図12において、各格子にルータ(図示せず)が一台ずつ配置され、正方形の数で表された複数のサーバが対応する位置のルータに接続され、さらにルータが格子状に接続されている格子型コンピュータシステムを考える。
図13は、図12の格子型コンピュータシステムを論理ノードによる格子モデルで表したものであり、正方形内の数字はノード間の経路長を表す。正方形の右上にある数字は「多重度」であり、各論理ノードに対応する物理ノード、つまりサーバの数を表している。例えば、図12の左上隅に位置する格子には六台のサーバが配置されているから、対応する論理ノードの多重度は「6」となる。この多重度は各論理ノードの処理能力の目安となり、後述する同時実行されるジョブの配置の際に使用される。
【0042】
なお、多重度は、同一性能のサーバが使用されているシステムにおいては単に各論理ノードに対応する物理ノードつまりサーバの数であってよいが、処理性能の異なるサーバが配置されている場合には、性能差を考慮して多重度を算出することが好ましい。
【0043】
以上説明したように、本実施形態では、種々の形態の格子型コンピュータシステムについて、論理ノードによる格子モデルを作成することができる。
【0044】
図14は、上述した論理ノードによる格子モデル作成のフローチャートである。
まず、格子型コンピュータシステム内で親となるノードを決定する(S20)。この親ノードは所与であってもよいし、システムの起動時にシステムの中で最も早く立ち上がったノードが親ノードとなり、そのことを他のノードに対して宣言するようにしてもよい。続いて、親ノードは、記憶装置36からスーパースケジューラを実現するためのプログラムをロードして実行する(S22)。親ノードのスーパースケジューラは、自身を起点とした他のノードとのノード間経路長、各論理ノードの多重度を上述した手順にしたがって決定する(S24)。決定された経路長を使用して、格子型コンピュータシステムの格子モデルを作成する(S26)。
【0045】
2.子ノードの展開と方形領域の確保
続いて、親ノードのスーパースケジューラは、格子型コンピュータシステムで処理するサービス要求を分析して、それぞれのサービス要求の入口となる子ノードを格子モデル内で分散して配置し、さらにそれぞれのサービス要求に割り当てるべき複数のノードを格子モデル内に確保する。以下では、この一連の処理について説明する。
【0046】
格子型コンピュータシステム内に、証券会社の発注システム、旅行会社の予約システム等の複数のシステムを構築するような場合を想定する。複数のシステムを構築する場合、それぞれのシステムを担当するべき子ノードがあることが望ましい。そこで、親ノードのスーパースケジューラは、格子モデル内に必要な数の子ノードを配置する。
【0047】
しかしながら、一般にグリッドコンピューティングにおいて、一つの親ノードの近傍に子ノードを集中して配置するようにすると、以下のような問題を生じる。
【0048】
まず、親ノードと子ノードの間の通信をする際に、他の子ノードを経由しなければならない状況が頻繁に生じるようになる。この場合、親ノードと子ノードの間での通信速度が、経由する子ノードにおける処理能力の影響を受けるだけでなく、子ノードがタスク処理に費やすべきリソースが通信により奪われてしまう。
また、格子モデル内で子ノードから孫ノードを展開しようとするとき、近傍に位置する別の子ノードによって先に確保されたノードにより孫ノードの展開が阻まれてしまい、必要な処理リソースを確保できなくなる可能性が高い。
【0049】
一方で、親ノードと子ノードとの経路長が離れ過ぎてしまうと通信に時間がかかるようになり、ノードの障害発生時にモデルを再構成する際などに、速やかに正常状態に復帰することができなくなるという不都合も生じる。
【0050】
そこで本実施形態では、物理的な計算モデルを親ノードと子ノードの間、および子ノード間に適用することで、格子モデル内での子ノードの適切な分散配置を実現するようにした。
【0051】
なお、本明細書においては、格子モデルの中で、スーパースケジューラを有し格子型コンピュータシステム全体のタスク割り当てを監視するノードを「親ノード」、スケジューラを有しサービス要求に応じて一定範囲内でのタスク割り当てを監視するノードを「子ノード」、子ノードのスケジューラによりタスク割り当てがなされるノードを「孫ノード」と呼ぶことにする。
【0052】
物理的な計算モデルを利用した、格子モデル内での子ノードの分散配置の処理を、図15の実施例を参照して具体的に説明する。図15(a)は、ノード間の経路長を利用して作成された格子モデルの例を示す。この格子モデルは、四行四列の論理ノードから構成されるとする。なお、より多数のノードを含む格子モデルであってもよいことは言うまでもない。
【0053】
親ノードのスーパースケジューラは、格子型コンピュータシステムに与えられる複数タスクからなるサービス要求を分析する。具体的には、システムに到来するサービス要求の種類や同時トランザクション数などの見積もりにしたがって、必要リソース量を推定する。続いて、スーパースケジューラは、この推定にしたがって、サービス要求毎に必要となるノード数を格子モデル内に確保しサービス要求処理の起点となる子ノードの数を決定する。
本実施例では、5つの子ノードが必要と決定されたものとする。また、親ノードは格子モデルの左下に位置する論理ノードに配置されるとする。
【0054】
続いて、スーパースケジューラは、格子モデル内での子ノードの配置を決定するために、親ノードを原点とする二次元座標を設定する。そして、この二次元座標上で、格子モデルを構成する各論理ノードの座標を便宜的に設定する。その様子を図15(b)に示す。この図では、x座標が0、x、x、x、y座標が0、y、y、yとなる格子状に論理ノードが配置される。なお、二次元座標における論理ノード間の距離は、全て同一にする。
【0055】
スーパースケジューラは、二次元座標上の任意の座標に、必要数(本実施例では5つ)の子ノードに対応する点を配置する。但し、子ノードが格子モデル内に収まるように、格子モデルの最も外側に位置する論理ノードのx座標(図15(b)ではx)、y座標(同y)以下であることが好ましい。
【0056】
次に、親ノードのスーパースケジューラは、親ノードと子ノードとの間、および子ノード同士の間に、以下の式(1)にしたがって擬似的な引力Fsを定義するとともに、式(2)にしたがって擬似的な斥力Frを定義する(図16を参照)。以下では、式(1)、(2)を合わせて「引力・斥力モデル」と呼ぶこともある。
Fs=−Cs・d−6・・・(1)
Fr=Cr・d−12・・・(2)
なお、この定義式については、竹本信雄、フックの法則はなぜ成り立つか、[online]、1990年9月1日、[2006年1月24日検索]、インターネット<URL:http://www008.upp.so-net.ne.jp/takemoto/hooke.htm>に開示されている。
【0057】
ここで「d」は、図15(b)に示す二次元座標上でのノード間のユークリッド距離であり、初期値は任意であってよい。また、Cs、Crは係数である。この係数は、親ノードと子ノード間の通信量に応じて決定されることが好ましい。つまり、親ノードと子ノードとが離れ過ぎていると、一部のノードに障害が発生したときに親ノードと子ノード間で通信がしにくくなるという問題があり、親ノードと子ノードとが近接し過ぎていると後述する子ノード毎の領域確保が困難になる。そのため、これらを考慮して経験的に係数を定めるか、または繰り返し処理により最適値を見つけ出すようにする。
【0058】
スーパースケジューラは、引力・斥力モデルにしたがって各ノードに働く疑似引力、疑似斥力の合計を計算し、その計算結果にしたがって子ノードを二次元座標内で移動させる計算を繰り返し実行する。そして、親ノードおよび子ノードが最も安定する座標上での位置を決定し、そのときの親ノードと子ノードの間、および子ノード間のユークリッド距離を算出する。但し、繰り返し計算中に、各子ノードの座標が格子モデルの外側に飛び出さないように、x座標とy座標の上限値および下限値が定められているものとする。
【0059】
このように、各ノードに働く力の計算と移動を繰り返すことによって、全てのノードについての最適なユークリッド距離を算出する。図15(c)は、繰り返し計算により各ノードが安定したときの二次元座標上での子ノードの位置を示す。なお、各ノードの位置は必ずしも一つに定まるとは限らないので、スーパースケジューラは、予め設定された繰り返し数を実行したら、上記のユークリッド距離の算出を終了するようにしてもよい。
【0060】
引力・斥力モデルを適用して親ノード、子ノードの座標上での位置が決定されると、親ノードのスーパースケジューラは、子ノードを二次元座標上で最も近い論理ノードに割り当てる。一例として、位置決定後の一つの子ノードの座標と、格子モデルの全ての論理ノードとの間のユークリッド距離を算出し、このユークリッド距離が最小になる座標を有する論理ノードにその子ノードを配置すると決定する。この処理を全ての子ノードについて繰り返す。図15(c)中の矢印は、各子ノードの最寄りの論理ノードを表している。図15(d)は、子ノードを最も近い論理ノードに配置した結果を示す。
【0061】
この引力・斥力モデルを適用することによって、子ノードを親ノードの近傍に偏らせず、格子モデルの全体にわたり配置することが可能になる。子ノード間に定義された斥力のために子ノードの周りに空きノードが確保されるため、後述する孫ノードの割り当てがしやすくなり、ひいては処理効率のアップにつながる。
【0062】
なお、図15の実施例では、親ノードを格子モデルの左下隅に配置したが、親ノードはこの位置に限られるわけではない。実際、格子モデルの中央付近に配置した方が、子ノードの周りに空きノードを確保しやすいという点では好ましい。
また、図15の実施例では、全てのノード間に疑似引力と疑似斥力を定義したが、一部のノード間にのみ定義してもよい。例えば、全ての親子ノード間に疑似引力と疑似斥力を定義するが、子ノード間では近隣の3つまでの子ノードとの間にのみ疑似引力と疑似斥力を定義するようにしてもよい。
【0063】
上述のユークリッド距離を算出する際に、格子モデルのサイズに比べて子ノードのばらつきが小さく、親ノードの周囲にかたまり過ぎてしまう事態も起こりえる。このような場合は、式(1)、(2)における係数Cs、Crを適宜修正することで、子ノードを格子モデル内で広く分散させて配置することができる。したがって、スーパースケジューラは、格子モデルの大きさを考慮して係数Cs、Crを設定することが好ましい。
【0064】
格子モデル内で子ノードを分散させて配置するための別の方法として、ばねモデルを利用することもできる。これは、上述の引力・斥力モデルを近似したものとも言える。ばねモデルは、例えば次式で表すように、全体のエネルギーEによって定義される。
【0065】
【数1】


【0066】
このばねモデルでは、全てのノード同士がばねでつながれており、各ばねは格子モデルにおけるノード間の経路長の最小値である「1」の自然長を持つものと想定する。上式において、nはノードの個数、kvivjはノードv、v間を結ぶばねのばね定数、lvivjはそのばねの自然長、dvivjはノードv、v間のユークリッド距離である。
【0067】
親ノードのスーパースケジューラは、上記式で算出されたエネルギーEをノードvのユークリッド距離dviで微分し、エネルギーEが最小になるユークリッド距離を算出する。算出したユークリッド距離を用いてエネルギーEを再計算し、続いて、別のノードvのユークリッド距離dviで微分し、エネルギーEが最小になるユークリッド距離を算出し、エネルギーEを再計算する。この計算を繰り返すことによって、全てのノードについての最適なユークリッド距離を算出する。
【0068】
スーパースケジューラは、算出されたユークリッド距離にしたがって、親ノードと子ノードを図15(b)に示すような二次元座標に配置する。子ノードを二次元座標上で最も近い論理ノードに割り当てる手順は、上述の引力・斥力モデルの場合と同様である。このばねモデルは計算式が簡単なことから、引力・斥力モデルと比べて計算が速いという利点がある。
【0069】
なお、親ノードのスーパースケジューラには、格子全体のリソースを管理し、新たに発生したサービス要求に対応するノードを格子モデル内に確保する必要があるとき、その起点となる子ノードを格子モデル内のいずれの位置に配置するかを決定するという役割もある。
この場合、ばねモデルであれば、新たに子ノードを追加して格子モデル内での配置を決定する場合には、格子モデルに配置済みの子ノードについては座標上での位置を固定しておき、新たに追加した子ノードと配置済みの子ノードおよび親ノードとを繋ぐばねのみを設定するようにする。こうすると、新たに設定されたばねのみについてエネルギーEを求め、上記計算を繰り返すことによって、新たに追加された子ノードの格子モデル内での配置を決定することができる。
【0070】
以上のようにして子ノードを格子モデル内の論理ノードに展開させた後、子ノードを構成する物理ノードに対して、子ノードに割り当てられるサービス要求に含まれるタスクを孫ノードに割り当てるためのスケジューラが記憶装置36から送信され、物理ノード上で実行される。子ノードのスケジューラは、それぞれ自らが必要とするリソースすなわちノード数を親ノードのスーパースケジューラに通知する。スーパースケジューラは、子ノード同士によるシステム内でのリソースの奪い合いによる影響を低下させるべく、子ノードがそれぞれ自由に使用できるノードを含む方形領域を格子モデル内に確保する。
【0071】
この格子モデル内での領域確保の方法として、本実施形態では、幾何学的な平面分割アルゴリズムである「平安京ビュー」を使用する。なお平安京ビューについては、伊藤貴之、小山田耕二、平安京ビュー〜階層型データを碁盤状に配置する視覚化手法、[online]、[2005/12/20検索]、インターネット<URL:htttp://online.vsj.or.jp/vc9/5-6.pdf>に説明されている。なお、平安京ビュー以外の他の既知の平面分割アルゴリズムを適用してもよいことは言うまでもない。
【0072】
スーパースケジューラで実行される平安京ビューのアルゴリズムは、以下のような手順となる。
まず、子ノードの格子ブロック内での位置を特定する。子ノードが格子モデル内で左からs番目、上からt番目にあるとき、これを[s,t]と表現する。この点を中心にして格子モデル内で渦巻き状に周囲のノードを確保していく。例えば、反時計回りに探索するとすれば、[s−1,t−1]〜[s−1,t+1]を探索し、続いて[s−1,t+1]〜[s+1,t+1]を探索し・・という順に、格子モデル内のノードを確保していく。
【0073】
この処理を、複数の子ノードそれぞれについて実行していき、他の子ノードが既に獲得した領域に遭遇したら、その方向の探索を終了する。また、子ノードから通知された必要なリソース分のノード数を確保したら、格子モデル内での探索を終了し、余分なリソースを取らないようにする。この方法によって、子ノードで処理するサービス要求に必要な数のノード数を過不足なく同時に格子モデル内で確保することができる。
なお、方形領域内で縦または横方向に連続するノード数は、子ノードに割り当てられるサービス要求のジョブを構成するタスクの並列度および直列度に基づいて決定されることが好ましい。
【0074】
続いて、方形領域の再配置を試みる。上述の引力・斥力モデルまたはばねモデルによって配置された子ノード間の距離は、この計算を実行するときに存在していたノードの配置状況によって決まってくる。そのため、ジョブが要求する方形領域を確保するのに適したノード配置になっていない場合がありうる。したがって、一旦確保された方形領域の位置を調整する必要がある。
[s,t]番目の子ノードについて確保された方形領域の4つの頂点のx座標値をx,xs+1、y座標値をy,ys+1と表したとき、この方形領域の配置を[x,xs+1,y,ys+1]と記述することにする。そして、各方形領域について、以下の二つの候補位置に、他の子ノードについて確保された方形領域と一つ以上の辺を接するように配置可能であるか否かを検証する。
候補位置1:[(x−w),(xs+1−w),y,ys+1
候補位置2:[x,xs+1,(y−w),(ys+1−w)]
但し、wは1以上の整数であり、1から開始して、他の方形領域の辺と接するか格子領域の境界に至るまで一つずつ増加させていくものとする。
この処理を全ての子ノードについて確保された方形領域に対して実行することで、再配置処理が実現される。なお、再配置処理は実行しなくてもよい。
【0075】
図17は、図15のように配置された子ノード毎に、方形領域を確保する処理を実行した結果の一例を示す。図中の楕円が親ノードを、円が子ノードを表し、太枠の四角形は、各子ノードの必要リソースに応じて格子モデルから切り取られた方形領域を表す。方形領域内のノードは、その領域に対応するサービス要求のタスクのみを処理し、他の方形領域に対応するサービス要求のタスク処理を担当することはない。
【0076】
子ノード毎の方形領域が確保されると、子ノードのスケジューラは、方形領域内でのタスク割り当てを担当する。タスクが割り当てられる孫ノードは、方形領域内でのみ展開される。例えば、図17において中央に位置する方形領域において、三角形の目印が付された孫ノードはこの方形領域内にのみ存在する。
【0077】
方形領域内での孫ノードの展開が終わった後、方形領域内のノードをまとめた仮想ノードのアドレスのみを、サービス要求のエントリポイントとすることが好ましい。スーパースケジューラは、エントリポイントにサービス要求が到来するように仮想ノードのアドレスをユーザアプリケーションに対して公開する。この後は、サービス要求は親ノードを介することなく各方形領域の仮想ノードに直接送信されるようになる。これ以降、障害の発生やブロックの組み替えの要求などが発生しない限り、親ノードのスーパースケジューラは休止する。
【0078】
図18は、子ノードの展開と方形領域の確保のプロセスを示すフローチャートである。
まず、親ノードのスーパースケジューラは、格子型コンピュータシステムに与えられる複数タスクからなるサービス要求を分析する(S30)。具体的には、システムに到来するサービス要求の数や必要リソース量の見積もりをする。この見積もりは、システムのオペレータによって手作業で入力されてもよいし、過去の統計に基づいてスーパースケジューラが算出してもよい。続いて、スーパースケジューラは、この見積もりにしたがって、サービス要求毎に必要となるノード数を格子モデル内に確保するための基点となる子ノードの数を決定する(S32)。スーパースケジューラは、決定された数の子ノードと親ノードとの間に上述した引力・斥力モデル、または、ばねモデルを適用し、親ノードと子ノードの二次元座標上での位置を計算し(S34)、座標上で最も近い論理ノードに子ノードを配置する(S36)。
【0079】
子ノードの配置が決定すると、記憶装置から子ノードに送信されたスケジューラが、自身のサービス要求を処理するために必要なリソースをスーパースケジューラに通知する(S38)。スーパースケジューラは、平面分割アルゴリズムを使用して、各子ノードに割り当てられるサービス要求に必要となるノード数を含む方形領域を格子モデル内に確保する(S40)。方形領域が確定すると、スーパースケジューラはノードブロック毎に仮想ノードを定義し(S42)、システム外部にはこの仮想ノードのネットワークアドレスのみを通知する。この後、子ノードのスケジューラがブロック内で孫ノードにタスクを割り当て、記憶装置に格納されているタスク処理のためのプログラムが孫ノードに送信される。
【0080】
図19は、スーパースケジューラのプログラムが実行される親ノードの機能ブロック図である。この場合の親ノードは、格子型コンピュータシステムにおいてタスクを割り当てる装置とみなすことができる。
親ノードは、モデル作成部102、サービス要求分析部104、子ノード数決定部106、子ノード配置部108、および方形領域確保部110を含む。モデル作成部102は、格子型コンピュータシステムにおける複数のノードとノード間接続装置の接続形態にしたがって論理ノードからなる格子モデルを作成する。サービス要求分析部104は、格子型コンピュータシステムに与えられる、複数タスクからなるサービス要求を分析する。
子ノード数決定部106は、サービス要求の分析結果にしたがって、サービス要求毎に必要となるノード数を格子モデル内に確保するための基点となる子ノードの数を決定する。子ノード配置部108は、決定された数の子ノードを格子モデル内に分散して配置する。方形領域確保部110は、子ノードを格子モデル内に分散配置した後に、各子ノードに割り当てられるサービス要求に必要となるノード数を含む方形領域を格子モデル内に確保する。
【0081】
以上のように、本実施形態によれば、サービス要求の分析に基づいて子ノード数を決定し、サービス要求の処理に必要なリソースにしたがって、引力・斥力モデルやばねモデルといった物理的な概念、平安京ビューといった幾何学的なアルゴリズムを利用することで子ノード毎に方形領域を格子モデル内に確保するようにした。そして、方形領域内でのタスク割り当ては子ノードの有するスケジューラで実施するようにした。
【0082】
したがって、格子型コンピュータシステムに互いに関連のない複数のサービス要求が与えられたときに、各サービス要求に必要な処理量に応じたノードを確保することができる。また、サービス要求の処理中に子ノードと孫ノードとの間には多数のトランザクション処理が発生するが、本実施形態では、同一のサービス要求に対するタスクのプログラムコードが、子ノード、孫ノードとして方形領域内の連続するノードにまとまって配置されるので、子ノードと孫ノード間の通信効率を高めることができ、処理時間の短縮に寄与する。
また、サービス要求毎に確保される方形領域内でのみ孫ノードが展開されるので、一部のサービス要求によって格子型コンピュータシステムのリソースが独占的に消費されてしまうような事態を回避することができる。さらに、サービス要求毎に別個の方形領域が確保されるため、各サービス要求に対応するシステム間でデータ処理の干渉が発生することがない。
【0083】
引力・斥力モデルを適用した場合には、親ノードと子ノードとの間に定義される引力のために、親ノードと子ノードとが格子モデル内で離れ過ぎることがない。そのため、親子ノード間の通信オーバーヘッドが削減される。さらに、親子ノード間の通信距離が短いことで、例えばシステム内のノードで障害が発生し、障害ノードを除いて格子モデルの作成や方形領域の確保を速やかに再実行することができる。また、子ノード同士の間に定義される斥力によって、子ノード同士がある程度離れて配置されているため、子ノードの周りに孫ノードを密集して配置することができる。さらに、あるサービス要求におけるジョブの同時実行数が増加して方形領域に含まれるノード数を増加させることが比較的容易に実現できるため、拡張性の点から好ましい。
【0084】
3.サービス要求の特性を考慮したタスク割り当て
子ノードのスケジューラは、ウェブブラウザを使用したユーザのインタラクティブ操作から生じるサービス要求の特性、すなわちタスクの並列度、直列度、同時実行ジョブ数に基づいて、それぞれの方形領域内でタスクをノードに割り当てる処理を実行する。
【0085】
ここで、タスクの並列度、直列度、同時実行ジョブ数について説明する。
インターネットを介した証券取引を例に取ると、ある顧客が異なる銘柄を同時に売買するとき、各銘柄のトランザクションは独立なので、タスクは並列に実行できる。このように、サービス要求において他のタスクの開始や終了を待たずに実行できるタスクの数を、本明細書では「並列度」と呼ぶ。このような並列的なタスクは、方形領域を構成する論理ノードの行数を増加させたり、論理ノードの多重度を増加させることで、サービス要求の増大に対応させることができる。
【0086】
より複雑なサービス要求の場合には、各タスク間の依存関係を維持するフロー制御が必要になる。例えば、インターネット経由で海外旅行の予約を受け付けるウェブサイトでは、「希望旅程の入力」に続いて「交通機関の予約」「宿泊施設の予約」などの処理を逐次実行していく必要がある。このような場合、後の処理を実行するためには前の処理の情報を引き継ぐ必要がある。このようなタスク間に依存関係があり直列的に処理する必要のあるタスクの連続数を、本明細書では「直列度」と呼ぶ。直列的なタスクは実行結果が処理順序に依存するため、方形領域内で連続するノードを確保することが必要になる。
【0087】
ジョブ同時実行数は、複数のユーザから同じサービス要求が発行された場合のサービス要求の数のことを言う。上述の例で言えば、証券取引サイトで複数のユーザが売買サービスをほぼ同時に要求する状況や、旅行予約サイトで複数のユーザが予約サービスをほぼ同時に要求する状況で、同時にサービスが提供される数に相当する。タスク並列度がユーザの待ち時間に影響するだけであるのに対して、ジョブ同時実行数は外部的要因によってもたらされる。ジョブ同時実行数の上限に達したシステムでは、ユーザからのサービス要求が拒絶されることもある。
【0088】
子ノードのスケジューラは、方形領域に対応するサービス要求のジョブを構成するタスクの並列度および直列度に基づいて、方形領域内の他の論理ノードにタスクを処理するためのタスク処理プログラムを割り当てる。具体的には、並列して実行可能なタスクを処理するためのタスク処理プログラムを、方形領域内で並列する論理ノードにそれぞれ割り当てる。依存関係のある直列的なタスク群については、方形領域内で直列するタスク数と同数の隣接する論理ノードを選択して、それぞれのタスクを処理するタスク処理プログラムを割り当てる。
【0089】
図20は、タスクの直列度と並列度にしたがったタスク割り当ての具体例を説明する図である。図中、斜線を付した丸は並列的なタスクを、白丸は直列的なタスクを表す。この例ではタスク並列度が「3」、タスクの直列度が「3」となる。所与の三行四列の方形領域において、並列的な3つのタスクは同じ列の連続する論理ノードに割り当てられ、直列的な3つのタスクは同じ行の連続する論理ノードに割り当てられる。
【0090】
このように、直列的なタスクの処理手順にしたがって、方形領域内で例えば左右方向に連続する論理ノードを割り当て、また並列的なタスクを上下方向に連続する論理ノードに割り当てるようにすると、タスクの処理が一方向に流れるようになり、方形領域内でデータの流れる方向が交差することがない。そのため、データが交差する論理ノードにおける処理負荷が突出して増大するような事態を回避することができる。これは、あるノードが故障したときにそのノードを除いてタスクの再割り当てをするときにも有利である。
【0091】
図21は、ジョブ同時実行数を考慮したタスク割り当てを説明する図である。複数のジョブを同時実行するときは、(タスク並列度×ジョブ同時実行数)にしたがって論理ノードの割り当てを行う。同時実行される二つのジョブのタスク並列度がそれぞれ「2」である場合は、図示するように、それぞれ二行の論理ノードが割り当てられる。
【0092】
なお、子ノードのスケジューラは、依存関係の存在する直列的なタスク群に含まれるいずれかのタスクが並列して実行可能な場合に、タスク群に含まれる各タスクの並列度の平均値を使用して、方形領域内で割り当てるべきノード数を決定してもよい。
【0093】
また、論理ノードの多重度がジョブ同時実行数以上の場合には、同じ論理ノードで複数のジョブを実行することができる。例えば、図21の例において、左上隅の二つの論理ノードの多重度がそれぞれ「3」「5」であった場合、これらの最小値はジョブの同時実行数2以上であるため、同時実行されるジョブそれぞれに二行の論理ノードを割り当てることなく、上二行の論理ノードのみでジョブを同時実行するようにしてもよい。
【0094】
図22は、タスクの直列度と並列度を考慮したタスク割り当てプロセスのフローチャートである。まず、各子ノードがスケジューラを記憶装置からロードする(S50)。子ノードは自身が処理するサービス要求を分析し(S52)、タスクの並列度、直列度、ジョブ同時実行数にしたがって、対応するタスク処理プログラムを方形領域内の他のノードに割り当てる(S54)。これらが孫ノードになる。タスク処理プログラムのコードは、実際のサービス要求が到着する前に記憶装置から孫ノードに送信されて、メモリに読み込まれた後、サービス要求に備えてメモリ上に待機する。
【0095】
子ノードのスケジューラは、タスク割り当ての結果を親ノードのスーパースケジューラに通知する(S56)。親ノードは各方形領域の仮想ノードのアドレスを外部からの要求に対して与え、以降のサービス要求は仮想ノードに直接供給される。そして、孫ノードにおいて、タスク処理プログラムによりタスクの処理が実行される(S58)。
【0096】
従来のグリッドコンピューティングにおけるタスク割り当てでは、ノード間の接続形態を考慮していなかった。これに対し本実施形態では、ノード間に経路長の概念を導入して、格子型コンピュータシステムを構成する物理ノードを論理ノードに置き換えた格子モデルを作成することによって、サービス要求の特性を考慮した効率的なタスク割り当てが可能になる。
【0097】
本実施形態は、スーパースケジューラを有する親ノードと、スケジューラを有する子ノードとが含まれる格子型コンピュータシステムと捉えることも可能である。この場合、親ノードのスーパースケジューラは、格子型コンピュータシステムにおける複数のノードとノード間接続装置の接続形態にしたがって論理ノードからなる格子モデルを作成する機能と、格子型コンピュータシステムに与えられる、複数タスクからなるサービス要求を分析する機能と、サービス要求の分析結果にしたがって、サービス要求毎に必要となるノード数を格子モデル内に確保するための基点となる子ノードの数を決定する機能と、決定された数の子ノードを格子モデル内に分散して配置する機能と、子ノードを格子モデル内に分散配置した後に、各子ノードに割り当てられるサービス要求に必要となるノード数を含む方形領域を格子モデル内に確保する機能と、を含む。また、子ノードのスケジューラは、該子ノードのために確保された方形領域内において、対応するサービス要求のジョブを構成するタスクの並列度および直列度に基づいて、方形領域内の他のノードにタスクを処理するためのタスク処理プログラムを割り当てる機能を含む。
【0098】
また、本実施形態は、親ノードで実行されるスーパースケジューラプログラムと、子ノードで実行されるスケジューラプログラムと、孫ノードで実行されるタスク処理プログラムとから構成されると捉えることも可能である。この場合の各種プログラムは、格子型コンピュータシステム内の複数のノードからアクセス可能な記憶装置から、スーパースケジューラまたはスケジューラの指令に応じて必要なノードに送信される。これによって、格子型コンピュータシステム内のいずれのノードも、親ノード、子ノード、孫ノードの全てに対応することができる。
【0099】
以上、本発明をいくつかの実施の形態をもとに説明した。これらの実施の形態は例示であり、それらの各構成要素や各処理プロセスの組合せにいろいろな変形例がありうること、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。
【0100】
請求項に記載の各構成要件が果たすべき機能は、本実施例において示された各機能ブロックの単体もしくはそれらの連係によって実現されることも当業者には理解されるところである。
【図面の簡単な説明】
【0101】
【図1】本発明の一実施形態に係る格子型コンピュータシステムの構成の一例を示す図である。
【図2】サーバ群を構成する各サーバの構成を示す図である。
【図3】本実施形態における処理の基本的な流れを示す図である。
【図4】図1に示した格子型コンピュータシステムについて、図中左上に位置するハッチングをかけたサーバからのホップ数を示す図である。
【図5】ノード間経路長を使用して図1の物理ノードを論理ノードにまとめて作成される格子モデルを示す図である。
【図6】ノード間接続装置としてルータの代わりにネットワークスイッチを介して複数のサーバが格子状に接続されたサーバ群を有する格子型コンピュータシステムの構成を示す図である。
【図7】図6に示した格子型コンピュータシステムについて、図中左上に位置するハッチングをかけたサーバからのホップ数を示す図である。
【図8】ノード間経路長を使用して図6の物理ノードを論理ノードにまとめて作成される格子モデルを示す図である。
【図9】二つ以上のネットワークインタフェースを備えるサーバがルータを介して接続された格子型コンピュータシステムの構成を示す図である。
【図10】図9に示した格子型コンピュータシステムについて、図中最上段に位置するハッチングをかけたサーバから、左列のルータ群を経由したときのホップ数を示す図である。
【図11】ノード間経路長を利用して図9の物理ノードを論理ノードにまとめて作成される格子モデルを示す図である。
【図12】格子毎のサーバ数が異なる格子型コンピュータシステムを示す図である。
【図13】図12の格子型コンピュータシステムを論理ノードによる格子モデルで表した図である。
【図14】論理ノードによる格子モデル作成方法のフローチャートである。
【図15】(a)〜(d)は、格子モデルに子ノードを分散させて配置する処理の一例を示す図である。
【図16】ノード間に働く引力および斥力のグラフである。
【図17】図15のように配置された子ノード毎に、方形領域を確保する処理を実行した結果の一例を示す図である。
【図18】子ノードの展開と方形領域の確保のプロセスを示すフローチャートである。
【図19】スーパースケジューラのプログラムが実行される親ノードの機能ブロック図である。
【図20】タスクの直列度と並列度にしたがったタスク割り当ての具体例を説明する図である。
【図21】ジョブ同時実行数を考慮したタスク割り当てを説明する図である。
【図22】タスクの直列度と並列度を考慮したタスク割り当てプロセスのフローチャートである。
【符号の説明】
【0102】
12 CPU、 14 メモリ、 16 記憶装置、 18 ネットワークインタフェース、 20 バス、 30、60、80 サーバ群、 32 ネットワーク、 34 ルータ、 36 記憶装置、 40 ルータ、 42 サーバ、 46 ネットワークスイッチ、 50、70、90 格子型コンピュータシステム、 102 モデル作成部、 104 サービス要求分析部、 106 子ノード数決定部、 108 子ノード配置部、 110 方形領域確保部。




 

 


     NEWS
会社検索順位 特許の出願数の順位が発表

URL変更
平成6年
平成7年
平成8年
平成9年
平成10年
平成11年
平成12年
平成13年


 
   お問い合わせ info@patentjp.com patentjp.com   Copyright 2007-2013