| 【発明の名称】 |
タスク割当方法および装置およびプログラムおよび記録媒体 |
| 【発明者】 |
【氏名】佐々木 淳
|
| 【要約】 |
【課題】従来はサーバネットワークにのみ依存していたタスク割当／負荷均衡化を、クライアントを含むネットワークで行う。
【解決手段】線形ネットワークの右半分に全要素（タスク）を収集し、次いで、最小値からｋ番目に小さな（優先度が高い）要素までを選択するが、より大きな要素が右の方で選択されるようにする。 |
【特許請求の範囲】
【請求項１】 ｎプロセスから仮想的に構成される同期型の線形ネットワーク(Line Network)上に、タスクを処理するｋ個のプロセス（サーバ）が分散して存在し、ｎ個の各プロセスが初期状態で１タスクずつ保持している状況において、各タスクには優先度を表す値（以下では要素と呼ぶ）が付与されていて、初期状態では、左端のプロセス［外１］はｌｅｆｔ状態、右端のプロセス［外２］はｒｉｇｈｔ状態、それ以外のプロセスはｗａｉｔ状態とし、［外１］が保持している要素とｌｅｆｔメッセージおよび［外１］がサーバかどうかの情報とをｒｉｇｈｔへ、［外２］が保持している要素とｒｉｇｈｔメッセージおよび［外２］がサーバかどうかの情報とをｌｅｆｔへ、それ以外のプロセスが保持している要素とｎｕｌｌメッセージとをｒｉｇｈｔへと送信することで起動し、ｗａｉｔ状態とｌｅｆｔ状態においては、直前にｌｅｆｔから受信した要素と制御メッセージおよび［外１］からそのプロセスの間のサーバ数とをｒｉｇｈｔへ送信し、ｒｉｇｈｔ状態においては、保持している要素の中の最小の要素に直前にｒｉｇｈｔから受信した制御メッセージおよびそのプロセスから［外２］の間のサーバ数とをｌｅｆｔへ、最大の要素とｎｕｌｌメッセージとをｒｉｇｈｔへ送信し、ｒｅｌａｙ状態においては、それまでに受信したメッセージの内容から算出した左右のサーバ数とその時点で左右に存在する要素数とに基づいて、その時点で保持している各要素を、そのまま保持するか、ｌｅｆｔへ送信するか、ｒｉｇｈｔへ送信するか、削除するか、のいずれかを行う、という処理により、優先度の高いｋ個のタスクを選択すると同時にｋ台のサーバにそれらをひとつずつ割り当てることを特徴とするタスク割当方法。
【外１】
【外２】
【請求項２】 タスクを持たないプロセスには要素として∞を与える請求項１記載のタスク割当方法。
【請求項３】 優先度の代わりにそのタスクの大きさを要素として扱い、小さなタスクから順番に一旦割り当てた後、その順番とは逆の順番に残ったタスクを小さい順に割り当てる処理を、未割当タスクが存在する間は繰り返す請求項１記載のタスク割当方法。
【請求項４】 非同期モデル上では、同期メッセージを用いる請求項１ないし３のいずれかに記載のタスク割当方法。
【請求項５】 メッセージの通信時に要素をエンコードする請求項１ないし４のいずれかに記載のタスク割当方法。
【請求項６】 端プロセスを除く各プロセスが方向感覚を持たない場合に、初期状態でｗａｉｔ状態のプロセスが要素を全隣接プロセスに送信し、ｗａｉｔ状態の間は毎ラウンド、それぞれの隣接プロセスから受信した要素をそのままもう一方の隣接プロセスへ送信し、ｗａｉｔ状態から他の状態に遷移するときに受信する制御メッセージとその受信した方向により各通信リンクがｌｅｆｔかｒｉｇｈｔかを判断し、ｌｅｆｔメッセージを受信した時点で、ｒｉｇｈｔからｒｉｇｈｔメッセージを伴わずに受信した要素を削除する請求項１ないし５のいずれかに記載のタスク割当方法。
【請求項７】 請求項１ないし６のいずれかに記載のタスク割当方法を実行する手段を備えたことを特徴とするタスク割当装置。
【請求項８】 情報処理装置にインストールすることにより、その情報処理装置に、ｎプロセスから仮想的に構成される同期型の線形ネットワーク(Line Network)上に、タスクを処理するｋ個のプロセス（サーバ）が分散して存在する状況で、ｎ個の各プロセスが初期状態で１タスクずつ保持される場合に、優先度の高いｋ個のタスクを選択すると同時に、ｋ台のサーバにそれらタスクを割当て、各タスクには優先度を表す値（以下では要素と呼ぶ）が付与されていて、初期状態では、左端のプロセス［外１］はｌｅｆｔ状態、右端のプロセス［外２］はｒｉｇｈｔ状態、それ以外のプロセスはｗａｉｔ状態とし、［外１］が保持している要素とｌｅｆｔメッセージおよび［外１］がサーバかどうかの情報とをｒｉｇｈｔへ、［外２］が保持している要素とｒｉｇｈｔメッセージおよび［外２］がサーバかどうかの情報とをｌｅｆｔへ、それ以外のプロセスが保持している要素とｎｕｌｌメッセージとをｒｉｇｈｔへと送信することで起動し、ｗａｉｔ状態とｌｅｆｔ状態においては、直前にｌｅｆｔから受信した要素と制御メッセージおよび［外１］からそのプロセスの間のサーバ数とをｒｉｇｈｔへ送信し、ｒｉｇｈｔ状態においては、保持している要素の中の最小の要素に直前にｒｉｇｈｔから受信した制御メッセージおよびそのプロセスから［外２］の間のサーバ数とをｌｅｆｔへ、最大の要素とｎｕｌｌメッセージとをｒｉｇｈｔへ送信し、ｒｅｌａｙ状態においては、それまでに受信したメッセージの内容から算出した左右のサーバ数とその時点で左右に存在する要素数とに基づいて、その時点で保持している各要素を、そのまま保持するか、ｌｅｆｔへ送信するか、ｒｉｇｈｔへ送信するか、削除するか、のいずれかを行う処理を実行する手順を実行させることを特徴とするプログラム。
【請求項９】 タスクを持たないプロセスには要素として∞を与える手順を実行させる請求項８記載のプログラム。
【請求項１０】 優先度の代わりにそのタスクの大きさを要素として扱い、小さなタスクから順番に一旦割り当てた後、その順番とは逆の順番に残ったタスクを小さい順に割り当てる処理を、未割当タスクが存在する間は繰り返す手順を実行させる請求項８記載のプログラム。
【請求項１１】 非同期モデル上では、同期メッセージを用いる手順を実行させる請求項８ないし１０のいずれかに記載のプログラム。
【請求項１２】 メッセージの通信時に要素をエンコードする手順を実行させる請求項８ないし１１のいずれかに記載のプログラム。
【請求項１３】 端プロセスを除く各プロセスが方向感覚を持たない場合に、初期状態でｗａｉｔ状態のプロセスが要素を全隣接プロセスに送信し、ｗａｉｔ状態の間は毎ラウンド、それぞれの隣接プロセスから受信した要素をそのままもう一方の隣接プロセスへ送信し、ｗａｉｔ状態から他の状態に遷移するときに受信する制御メッセージとその受信した方向により各通信リンクがｌｅｆｔかｒｉｇｈｔかを判断し、ｌｅｆｔメッセージを受信した時点で、ｒｉｇｈｔからｒｉｇｈｔメッセージを伴わずに受信した要素を削除する手順を実行させる請求項８ないし１２のいずれかに記載のプログラム。
【請求項１４】 情報処理装置にインストールすることにより、その情報処理装置に請求項１ないし６のいずれかに記載のタスク割当方法を実行する機能を実現させることを特徴とするプログラム。
【請求項１５】 請求項８または１４記載のプログラムが記録された前記情報処理装置読み取り可能な記録媒体。
|
【発明の詳細な説明】【０００１】
【発明の属する技術分野】本発明は、分散システムにおけるタスク割り当てに関する。なお、並列システムは分散システムの一種であるため、本発明は並列システムでも分散システムでも使えるが、それぞれのシステムにおいては用語が異なるため、以下では並列システムにおけるプロセッサ、ＣＰＵ、分散システムにおけるエージェント、プロセス、計算機等の用語を一括してプロセスと呼ぶ。
【０００２】
【従来の技術】従来、集中的にタスクが到着する場合にのみ、負荷均衡化を考慮したタスク割当方法が村主俊彦,山下博之,木下真吾,岡田靖史,自律協調型分散システムにおける負荷分散方法,電子情報通信学会論文誌D-I,Vol.J81-D-I,No.10,pp.1115-1129,1998.等で述べられているが、分散的に存在するタスクに対するタスク割当方法は考えられていない。
【０００３】その代わり、分散的にタスクが存在する状況においては、辻敦宏,上野仁,山本幹,池田博昌,ネットワークを介した不均質な分散システムにおける自律負荷分散制御方式,電子情報通信学会論文誌B-I,Vol.J81-B-I,No.10,pp.587-595,1998.等では、負荷均衡化に絞って検討されている。
【０００４】なお、サーバ間で協調してそれぞれに到着したタスクを移動させずに、個々のタスクの自己最適化のみを目指してタスクを移動させる方法もあるが、移動させない場合に比べて良くならないという結果がH.Kameda, J.Li, Y.Hosokawa, E.Altman, and O.Pourtallier,Braess-like Paradoxes in Distributed PerformanceOptimization,電子情報通信学会技術研究報告，IN2000-33-42,pp.49-56,2000.等で述べられている。
【０００５】さらに、従来、考えられてきたタスク割当や負荷均衡化は、タスクの要求元であるクライアントを考慮せず、単にタスクがサーバへ届いた時点からのタスクの移動を検討している。しかし、クライアントが特定できる場合には、クライアントからのタスクの移動も考慮に入れた方がサーバ側の負担が減るなどの効果が期待できる。そのため、サーバだけでなく、クライアントも含めたネットワークにおけるタスク割当／負荷均衡化の方法があると非常に有用である。
【０００６】
【発明が解決しようとする課題】そこで、本発明では、分散的に存在するタスクを一箇所に集めることなく、分散させたままで、そのタスクを処理すべきサーバへ割り当てる方法を考える。その際、一般的にタスク数の方がサーバ数よりも多いため、どのタスクを優先的に割り当てるかが問題となる。
【０００７】本発明においてはその基準までは言及しないが、何かしらの基準となる数値を各タスクが持っていることを前提とする。そして、対象とするネットワークをサーバだけを取出したネットワークではなく、図１に示すようなタスクの要求元であるクライアントも含むネットワーク上で考える。図１においては、斜線のプロセスがサーバを、それ以外のプロセスがクライアントを表している。サーバ同士は直接通信リンクで結ばれていないため、サーバネットワークを構築するには、間にあるクライアントがサーバ間の通信を補助する必要がある。しかし、本発明においては、そのようなことをせず、クライアントとサーバが混在する状態のままでタスクを割り当てる。
【０００８】具体的には、サーバもクライアントの一種と考えてタスクを持つものとし、ｋ台のサーバとｎ−ｋ台のクライアント（以後、これらをまとめてプロセスと呼ぶ）により構成されるネットワーク上で、各プロセスが一つずつタスクを持つときに、優先度の高いｋ個のタスクを選択すると同時に、それらをｋ台のサーバへひとつずつ割り当てる方法を考える。
【０００９】このようなサーバ、クライアントは、図２〜図５に示すようにして構成される。これらの図のうち、図２がサーバの基本内部構成例、図３がクライアントの基本内部構成例である。ただし、本発明と関係がない装置は省略してあり、通常、クライアントにはそのクライアント独自の処理を行う装置がある。また、図４と図５は後に例として挙げる負荷均衡化を行うためのサーバの内部構成例である。図４に示すサーバは負荷均衡化装置とタスク処理装置とが別々の場合の例であり、図５に示すサーバは負荷均衡化装置とタスク処理装置とが同一装置の場合の例である。
【００１０】このような構成例の下で、単純に要素を選択して配送するのなら、分散ソーティング、あるいは、ランキングを行って小さい方からｋ要素選択し、次いで、それらを順次適切なプロセスへと配送すれば良い。しかし、そのような方法では割当に要する時間が長くなってしまうので、この二つの処理を同時に行うことが望まれる。
【００１１】この二つの処理を同時に行う方法の一つとして、佐々木淳，線形ネットワークにおける時間複雑度と通信複雑度が共に最適な分散ソーティング，電子情報通信学会研究報告，COMP2000-32,2000.で簡単に述べた動的な問題に対するアルゴリズムを利用する方法がある。ここでいう動的な問題とは、Doron Rotem,Nicola Santoro,and Jeffrey B.Sidney,Distributed Sorting,IEEE Transactions on Computers,Vol.C-34,No.4,pp.372-376,1985.で述べられている初期状態と最終状態とにおける各プロセスの要素数が異なる問題である。本発明が対象とする問題では、右端にダミーのプロセスを設けて、そのプロセスが最終状態でｎ−ｋ要素持つように問題を変更すれば、このアルゴリズムをそのまま利用できる。しかし、このアルゴリズムの時間複雑度はｎ−１よりも大きいため、本発明が対象とする問題に対しては最適なアルゴリズムではないことがわかる。
【００１２】以上で本発明が対象とする問題の概略と、それに対しては単純な対策では解決できないことを示した。以下では、より詳細な問題の定義を行う。そのために、まず、ネットワークや分散システムのモデルを述べる。
【００１３】本発明では、図６に示すような、プロセス［数１］と、［数２］と［数３］の間の双方向通信リンクから構成される線形ネットワークを対象とする。ただし、ここでは通信が線形ネットワーク上で行われているように見なせれば問題ないため、物理的なネットワークが線形である必要はなく、仮想的（論理的）なネットワークが線形であれば問題ない。
【数１】
【数２】
【数３】
【００１４】具体的な例を挙げて説明する。まず、図７に示すようなネットワークがあったとする。図７のＡ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ、Ｌはプロセス（計算機）を表し、Ｒはルータを表す。図７において、プロセスＡ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆが本発明を適用するクライアントあるいはサーバとする。そして、Ｒがルータ、Ｌが本発明を適用しないプロセスとする。このとき、図８の上の図に示すような経路の通信を行うようにすると、仮想的に同図の下の図に示すような線形ネットワークにおける通信を実現できる。なお、ＬはＥとＦとの間の通信の中継だけは行う。
【００１５】このような線形ネットワークに対して、本発明で置く仮定を述べる。まず、一般性を失うことなく、［外３］が左端となるように水平に置かれていると仮定する。このとき、各プロセスは左右の隣接プロセスをそれぞれ“ｌｅｆｔ”と“ｒｉｇｈｔ”という局所名でのみ認識する。ただし、左右の認識は全プロセスで一致しており、端プロセスではこれらのうち対応する局所名がｎｕｌｌとなる。また、プロセス［外４］は自身の識別子ｉとプロセス数ｎを知らないと仮定する。さらに、各プロセスの局所メモリの大きさを［数４］ビット、プロセス間の通信に用いられるメッセージの長さを［数５］ビットに制限する。ただし、Ｌは各タスクの優先度、大きさなどを表す要素の最大値を表し、［数６］である。つまり、この制約は一回の通信で１要素しか送信できないことを意味する。
【外３】
【外４】
【数４】
【数５】
【数６】
【００１６】このような仮定の下で、各プロセスは隣接プロセスと適切な回数だけ通信を行うことで問題を解決する。このようなシステムのモデルには主に同期モデルと非同期モデルとがある。同期モデルおよび非同期モデルについては、亀田恒彦，山下雅史，分散アルゴリズム，近代科学社，1994,Nancy A.Lynch,Distributed Algorithms,Morgan Kaufmann,1996.等で述べられている。
【００１７】同期モデルでは、送受信処理が毎ラウンド全てのプロセス間で同期的に行われる。一方、非同期モデルでは、各プロセスの送受信処理は独立に行われるが、各通信リンクがＦＩＦＯ(First In First Out)であることと、各通信リンクにおけるメッセージディレイが有限であることが仮定される。また、一般に、分散アルゴリズムの評価には時間複雑度と通信複雑度との二つの基準が存在する。前者は同期モデルではラウンド数、非同期モデルではメッセージの最長鎖に属するメッセージ数で表される。一方、後者にはメッセージ複雑度とビット複雑度とがあり、それぞれ総メッセージ数、メッセージの総ビット数で表されるが、本発明のメッセージ長に関する制約の下では両者は同じ大きさを表す。
【００１８】最後に本発明が対象とする問題を定義する。この問題はｋ−ｓｅｌｅｃｔｉｏｎ問題の一種となるが、分散ｋ−ｓｅｌｅｃｔｉｏｎ問題はｋ番目に小さな要素を求める問題であり、本問題とは多少異なるため、Ｄｉｓｔｒｉｂｕｔｅｄ Ａｒｒａｎｇｅｍｅｎｔ Ｓｅｌｅｃｔｉｏｎ問題と呼ぶことにする。この問題を以下のように定義する。ただし、［外５］をｉ番目に小さな要素、［外６］を最終状態で解を持つプロセスの集合とする。つまり、［数７］となる。まず、初期状態において、プロセス［外４］は要素［数８］を持ち、さらに、［数９］か否かを知っているものとする。そして、最終状態において、［数１０］の二つの条件を満たすように［外７］以下の要素を移動させる。
【外５】
【外６】
【外７】
【数７】
【数８】
【数９】
【数１０】
【００１９】なお、要素の大小、あるいは、ネットワークの左右を入れ替えたとしても、同一のアルゴリズムを適用することができる。要素の大小、つまり、左から昇順に並べるか降順に並べるかについては、要素を負の数と見なして（−１を掛けて大小比較を行って）本発明のアルゴリズムを適用すれば降順になるので問題ない。ネットワークの左右については名前の付け方の問題というだけなので、アルゴリズム自体に変更を加える必要はない。
【００２０】すなわち、本発明により、従来はサーバネットワークにのみ依存していたタスク割当／負荷均衡化を、クライアントを含むネットワークで行うことができるタスク割当方法および装置およびプログラムおよび記録媒体を提供することを目的とする。
【００２１】
【課題を解決するための手段】本発明の中心的なアイデアは、まず、ネットワークの右半分に全要素を収集し、次いで、最小値からｋ番目に小さな要素までを選択するが、より大きな要素が右の方で選択されるようにする。このアイデアにより、要素が相対的に大きなほど、それが選択されてから移動する距離が短くなる、という性質が実現される。最小値を求めるよりもｋ番目に小さな要素を求める方が時間がかかるため、この性質は非常に有用である。
【００２２】本発明の具体的な方法は、同期型のネットワークにおいては、初期状態では、左端のプロセス［外３］はｌｅｆｔ状態、右端のプロセス［外８］はｒｉｇｈｔ状態、それ以外のプロセスはｗａｉｔ状態とし、［外３］が保持している要素とｌｅｆｔメッセージ、および［外３］がサーバかどうかの情報とをｒｉｇｈｔへ、［外８］が保持している要素とｒｉｇｈｔメッセージ、および、［外８］がサーバかどうかの情報とをｌｅｆｔへ、それ以外のプロセスが保持している要素とｎｕｌｌメッセージとをｒｉｇｈｔへと送信することで起動し、ｗａｉｔ状態とｌｅｆｔ状態においては、直前にｌｅｆｔから受信した要素と制御メッセージ、および、［外３］からそのプロセスの間のサーバ数とをｒｉｇｈｔへ送信し、ｒｉｇｈｔ状態においては、保持している要素のなかの最小の要素に直前にｒｉｇｈｔから受信した制御メッセージ、および、そのプロセスから［外８］の間のサーバ数とをｌｅｆｔへ、最大の要素とｎｕｌｌメッセージとをｒｉｇｈｔへ送信し、ｒｅｌａｙ状態においては、それまでに受信したメッセージの内容から算出した左右のサーバ数とその時点で左右に存在する要素数とに基づいて、その時点で保持している各要素を、そのまま保持するか、ｌｅｆｔへ送信するか、ｒｉｇｈｔへ送信するか、削除するか、のいずれかの処理を実行する、というものである。なお、これらの状態間の状態遷移関係は図９に示すとおりである。図９は各楕円が各状態を表し、各矢印が各状態遷移を表す。そして、矢印に付与されているｌｅｆｔ、ｒｉｇｈｔは、その制御メッセージの受信により状態遷移が起こることを示している。なお、ｗａｉｔ状態からｒｅｌａｙ状態へ向かう矢印に付与されているｂｏｔｈは、ｌｅｆｔメッセージとｒｉｇｈｔメッセージとを同時に受信することを示している。各プロセスの初期状態は、［外３］がｌｅｆｔ状態、［外８］がｒｉｇｈｔ状態で、残りの全てのプロセスがｗａｉｔ状態である。また、実行終了（ｓｌｅｅｐ）は、ｌｅｆｔ状態かｒｅｌａｙ状態においてのみ行われる。
【外８】
【００２３】この方法においては、初期状態で全てのプロセスがちょうどひとつずつ要素を持つことが要求されるが、ｋ＋１番目以降の要素が削除されることを利用し、初期状態で要素を持たないプロセスに要素として∞を与えることで有効なタスクのみを抽出して割り当てることができる。なお、数値的には∞はＬを越える数であるが、∞を特殊な記号として扱い、例えばＬ＋１という数値を∞に割り当てるなどの方法により、∞のビット表現時のビット数が［数５］を越えないようにすることができる。また、初期状態の要素数がｋ個未満の場合には∞も割り当てられてしまうが、∞が割り当てられたプロセスはひとつも割り当てられなかったと見なせば実用上は何ら問題はない。
【００２４】さらに、タスクの優先度の代わりにそのタスクの大きさを要素として扱うと、サーバ（［外６］に属するプロセス）に小さなタスクから順に並ぶ、このことを利用して特願２０００−３５６０９３号（本願出願時に未公開）に示した簡略化した方法と同様の方法を採ると、サーバ間の負荷均衡化も実現できる。具体的には、小さなタスクから順番に一旦割り当てた後、その順番とは逆の順番に残ったタスクを小さい順番に割り当てればよい。
【００２５】本発明の以下の記述においては、同期モデルについてのみ詳細に述べるが、非同期モデルに対しては、同期メッセージを用いることで簡単に本発明を利用できる。具体的には、各プロセスは各ラウンドの動作を全ての隣接プロセスからの同期メッセージの受信により開始するようにすればよい。
【００２６】さらに、Michael C.Loui,The Complexity of Sorting on Distributed Systems,Information and Control,Vol.60,No.1-3,pp.70-85,1984,O.Gerstel and S.Zaks,The Bit Complexity of Distributed Sorting,Algorithmica,Vol.18,No.3,pp.405-416,1997．に述べられている要素のエンコード（圧縮）方法を用いると、通信するビット数を減らすことが可能になる。
【００２７】また、端プロセスを除く各プロセスが方向感覚を持たない場合であっても、初期状態でｗａｉｔ状態のプロセスが要素を全隣接プロセスに送信し、ｗａｉｔ状態の間は毎ラウンド、それぞれの隣接プロセスから受信した要素をそのままもう一方の隣接プロセスへ送信し、ｗａｉｔ状態から他の状態に遷移するときに受信する制御メッセージとその受信した方向により各通信リンクがｌｅｆｔかｒｉｇｈｔかを判断し、ｌｅｆｔメッセージを受信した時点で、ｒｉｇｈｔからｒｉｇｈｔメッセージを伴わずに受信した要素を削除する、という処理を追加することにより、通信量は多少増えるものの、同じ時間で同じ結果を得ることができる。
【００２８】すなわち、本発明の第一の観点は、タスク割当方法であって、本発明の特徴とするところは、ｎプロセスから仮想的に構成される同期型の線形ネットワーク(Line Network)上に、タスクを処理するｋ個のプロセス（サーバ）が分散して存在し、ｎ個の各プロセスが初期状態で１タスクずつ保持している状況において、各タスクには優先度を表す値（以下では要素と呼ぶ）が付与されていて、初期状態では、左端のプロセス［外３］はｌｅｆｔ状態、右端のプロセス［外８］はｒｉｇｈｔ状態、それ以外のプロセスはｗａｉｔ状態とし、［外３］が保持している要素とｌｅｆｔメッセージおよび［外３］がサーバかどうかの情報とをｒｉｇｈｔへ、［外８］が保持している要素とｒｉｇｈｔメッセージおよび［外８］がサーバかどうかの情報とをｌｅｆｔへ、それ以外のプロセスが保持している要素とｎｕｌｌメッセージとをｒｉｇｈｔへと送信することで起動し、ｗａｉｔ状態とｌｅｆｔ状態においては、直前にｌｅｆｔから受信した要素と制御メッセージおよび［外３］からそのプロセスの間のサーバ数とをｒｉｇｈｔへ送信し、ｒｉｇｈｔ状態においては、保持している要素の中の最小の要素に直前にｒｉｇｈｔから受信した制御メッセージおよびそのプロセスから［外８］の間のサーバ数とをｌｅｆｔへ、最大の要素とｎｕｌｌメッセージとをｒｉｇｈｔへ送信し、ｒｅｌａｙ状態においては、それまでに受信したメッセージの内容から算出した左右のサーバ数とその時点で左右に存在する要素数とに基づいて、その時点で保持している各要素を、そのまま保持するか、ｌｅｆｔへ送信するか、ｒｉｇｈｔへ送信するか、削除するか、のいずれかを行う、という処理により、優先度の高いk個のタスクを選択すると同時に、ｋ台のサーバにそれらをひとつずつ割り当てるところにある。
【００２９】これにより、従来はサーバネットワークにのみ依存していたタスク割当／負荷均衡化を、クライアントを含むネットワークで行うことができる。
【００３０】タスクを持たないプロセスには要素として∞を与えることにより、有効なタスクのみを抽出して割り当てることができる。
【００３１】優先度の代わりにそのタスクの大きさを要素として扱い、小さなタスクから順番に一旦割り当てた後、その順番とは逆の順番に残ったタスクを小さい順に割り当てる処理を、未割当タスクが存在する間は繰り返すことにより、負荷均衡を実現しつつタスクを割り当てることができる。
【００３２】非同期モデル上では、同期メッセージを用いることにより、非同期モデル上でも動作させることができる。
【００３３】メッセージの通信時に要素をエンコードすることにより、通信ビット数を減らすことができる。
【００３４】端プロセスを除く各プロセスが方向感覚を持たない場合に、初期状態でｗａｉｔ状態のプロセスが要素を全隣接プロセスに送信し、ｗａｉｔ状態の間は毎ラウンド、それぞれの隣接プロセスから受信した要素をそのままもう一方の隣接プロセスへ送信し、ｗａｉｔ状態から他の状態に遷移するときに受信する制御メッセージとその受信した方向により各通信リンクがｌｅｆｔかｒｉｇｈｔかを判断し、ｌｅｆｔメッセージを受信した時点で、ｒｉｇｈｔからｒｉｇｈｔメッセージを伴わずに受信した要素を削除することにより、端プロセスを除く各プロセスが方向感覚を持たない場合にも適用することができる。
【００３５】本発明の第二の観点は、本発明のタスク割当方法を実行する手段を備えたことを特徴とするタスク割当装置である。
【００３６】本発明の第三の観点はプログラムであって、本発明の特徴とするところは、情報処理装置にインストールすることにより、その情報処理装置に、ｎプロセスから仮想的に構成される同期型の線形ネットワーク(Line Network)上に、タスクを処理するｋ個のプロセス（サーバ）が分散して存在する状況で、ｎ個の各プロセスが初期状態で１タスクずつ保持される場合に、優先度の高いｋ個のタスクを選択すると同時に、ｋ台のサーバにそれらタスクを割当て、各タスクには優先度を表す値（以下では要素と呼ぶ）が付与されていて、初期状態では、左端のプロセス［外１］はｌｅｆｔ状態、右端のプロセス［外２］はｒｉｇｈｔ状態、それ以外のプロセスはｗａｉｔ状態とし、［外１］が保持している要素とｌｅｆｔメッセージおよび［外１］がサーバかどうかの情報とをｒｉｇｈｔへ、［外２］が保持している要素とｒｉｇｈｔメッセージおよび［外２］がサーバかどうかの情報とをｌｅｆｔへ、それ以外のプロセスが保持している要素とｎｕｌｌメッセージとをｒｉｇｈｔへと送信することで起動し、ｗａｉｔ状態とｌｅｆｔ状態においては、直前にｌｅｆｔから受信した要素と制御メッセージおよび［外１］からそのプロセスの間のサーバ数とをｒｉｇｈｔへ送信し、ｒｉｇｈｔ状態においては、保持している要素の中の最小の要素に直前にｒｉｇｈｔから受信した制御メッセージおよびそのプロセスから［外２］の間のサーバ数とをｌｅｆｔへ、最大の要素とｎｕｌｌメッセージとをｒｉｇｈｔへ送信し、ｒｅｌａｙ状態においては、それまでに受信したメッセージの内容から算出した左右のサーバ数とその時点で左右に存在する要素数とに基づいて、その時点で保持している各要素を、そのまま保持するか、ｌｅｆｔへ送信するか、ｒｉｇｈｔへ送信するか、削除するか、のいずれかを行う処理を実行する手順を実行させるところにある。
【００３７】タスクを持たないプロセスには要素として∞を与える手順を実行させることができる。
【００３８】優先度の代わりにそのタスクの大きさを要素として扱い、小さなタスクから順番に一旦割り当てた後、その順番とは逆の順番に残ったタスクを小さい順に割り当てる処理を、未割当タスクが存在する間は繰り返す手順を実行させることができる。
【００３９】非同期モデル上では、同期メッセージを用いる手順を実行させることができる。
【００４０】メッセージの通信時に要素をエンコードする手順を実行させることができる。
【００４１】端プロセスを除く各プロセスが方向感覚を持たない場合に、初期状態でｗａｉｔ状態のプロセスが要素を全隣接プロセスに送信し、ｗａｉｔ状態の間は毎ラウンド、それぞれの隣接プロセスから受信した要素をそのままもう一方の隣接プロセスへ送信し、ｗａｉｔ状態から他の状態に遷移するときに受信する制御メッセージとその受信した方向により各通信リンクがｌｅｆｔかｒｉｇｈｔかを判断し、ｌｅｆｔメッセージを受信した時点で、ｒｉｇｈｔからｒｉｇｈｔメッセージを伴わずに受信した要素を削除する手順を実行させることができる。
【００４２】あるいは、本発明のプログラムは、情報処理装置にインストールすることにより、その情報処理装置に本発明のタスク割当方法を実行する機能を実現させることを特徴とする。
【００４３】本発明の第四の観点は、本発明のプログラムが記録された前記情報処理装置読み取り可能な記録媒体である。
【００４４】
【発明の実施の形態】本発明実施例を図６〜図２５を参照して説明する。図６は線形ネットワークを示す図である。図１０〜図１９は詳細な実行例を示す図である。図２０〜図２４はさまざまな状況における実行例を示す図である。図２５は本タスク割当方法を負荷状均衡化に利用した際の実行例を示す図である。
【００４５】本発明の第一の観点はタスク割当方法であって、本発明の特徴とするところは、図６に示すように、ｎプロセスから仮想的に構成される同期型の線形ネットワーク(Line Network)上に、タスクを処理するｋ個のプロセス（サーバ）が分散して存在し、ｎ個の各プロセスが初期状態で１タスクずつ保持している状況において、図１１に示すように、各タスクには優先度を表す値である要素が付与されていて、初期状態では、左端のプロセス［外３］はｌｅｆｔ状態、右端のプロセス［外８］はｒｉｇｈｔ状態、それ以外のプロセスはｗａｉｔ状態とし、［外３］が保持している要素とｌｅｆｔメッセージおよび［外３］がサーバかどうかの情報とをｒｉｇｈｔへ、［外８］が保持している要素とｒｉｇｈｔメッセージおよび［外８］がサーバかどうかの情報とをｌｅｆｔへ、それ以外のプロセスが保持している要素とｎｕｌｌメッセージとをｒｉｇｈｔへと送信することで起動し、ｗａｉｔ状態とｌｅｆｔ状態においては、直前にｌｅｆｔから受信した要素と制御メッセージおよび［外３］からそのプロセスの間のサーバ数とをｒｉｇｈｔへ送信し、ｒｉｇｈｔ状態においては、保持している要素の中の最小の要素に直前にｒｉｇｈｔから受信した制御メッセージおよびそのプロセスから［外８］の間のサーバ数とをｌｅｆｔへ、最大の要素とｎｕｌｌメッセージとをｒｉｇｈｔへ送信し、ｒｅｌａｙ状態においては、それまでに受信したメッセージの内容から算出した左右のサーバ数とその時点で左右に存在する要素数とに基づいて、その時点で保持している各要素を、そのまま保持するか、ｌｅｆｔへ送信するか、ｒｉｇｈｔへ送信するか、削除するか、のいずれかを行う、という処理により、優先度の高いｋ個のタスクを選択すると同時に、ｋ台のサーバにそれらをひとつずつ割り当てるところにある。
【００４６】タスクを持たないプロセスには要素として∞を与える。
【００４７】優先度の代わりにそのタスクの大きさを要素として扱い、小さなタスクから順番に一旦割り当てた後、その順番とは逆の順番に残ったタスクを小さい順に割り当てる処理を、未割当タスクが存在する間は繰り返す。
【００４８】非同期モデル上では、同期メッセージを用いる。
【００４９】メッセージの通信時に要素をエンコードする。
【００５０】端プロセスを除く各プロセスが方向感覚を持たない場合に、初期状態でｗａｉｔ状態のプロセスが要素を全隣接プロセスに送信し、ｗａｉｔ状態の間は毎ラウンド、それぞれの隣接プロセスから受信した要素をそのままもう一方の隣接プロセスへ送信し、ｗａｉｔ状態から他の状態に遷移するときに受信する制御メッセージとその受信した方向により各通信リンクがｌｅｆｔかｒｉｇｈｔかを判断し、ｌｅｆｔメッセージを受信した時点で、ｒｉｇｈｔからｒｉｇｈｔメッセージを伴わずに受信した要素を削除する。
【００５１】本発明の第二の観点は、本発明のタスク割当方法を実行する手段を備えたことを特徴とするタスク割当装置であり、図２〜図５に示すように、サーバおよびクライアントの装置内に設けられる。
【００５２】本発明の第三の観点はプログラムであって、本発明の特徴とするところは、情報処理装置としてのコンピュータ装置にインストールすることにより、そのコンピュータ装置に、ｎプロセスから仮想的に構成される同期型の線形ネットワーク(Line Network)上に、タスクを処理するｋ個のプロセス（サーバ）が分散して存在する状況で、ｎ個の各プロセスが初期状態で１タスクずつ保持される場合に、優先度の高いｋ個のタスクを選択すると同時に、ｋ台のサーバにそれらタスクを割当て、各タスクには優先度を表す値（以下では要素と呼ぶ）が付与されていて、初期状態では、左端のプロセス［外１］はｌｅｆｔ状態、右端のプロセス［外２］はｒｉｇｈｔ状態、それ以外のプロセスはｗａｉｔ状態とし、［外１］が保持している要素とｌｅｆｔメッセージおよび［外１］がサーバかどうかの情報とをｒｉｇｈｔへ、［外２］が保持している要素とｒｉｇｈｔメッセージおよび［外２］がサーバかどうかの情報とをｌｅｆｔへ、それ以外のプロセスが保持している要素とｎｕｌｌメッセージとをｒｉｇｈｔへと送信することで起動し、ｗａｉｔ状態とｌｅｆｔ状態においては、直前にｌｅｆｔから受信した要素と制御メッセージおよび［外１］からそのプロセスの間のサーバ数とをｒｉｇｈｔへ送信し、ｒｉｇｈｔ状態においては、保持している要素の中の最小の要素に直前にｒｉｇｈｔから受信した制御メッセージおよびそのプロセスから［外２］の間のサーバ数とをｌｅｆｔへ、最大の要素とｎｕｌｌメッセージとをｒｉｇｈｔへ送信し、ｒｅｌａｙ状態においては、それまでに受信したメッセージの内容から算出した左右のサーバ数とその時点で左右に存在する要素数とに基づいて、その時点で保持している各要素を、そのまま保持するか、ｌｅｆｔへ送信するか、ｒｉｇｈｔへ送信するか、削除するか、のいずれかを行う処理を実行する手順を実行させるところにある。
【００５３】タスクを持たないプロセスには要素として∞を与える手順を実行させることができる。
【００５４】優先度の代わりにそのタスクの大きさを要素として扱い、小さなタスクから順番に一旦割り当てた後、その順番とは逆の順番に残ったタスクを小さい順に割り当てる処理を、未割当タスクが存在する間は繰り返す手順を実行させる。
【００５５】非同期モデル上では、同期メッセージを用いる手順を実行させることができる。
【００５６】メッセージの通信時に要素をエンコードする手順を実行させることができる。
【００５７】端プロセスを除く各プロセスが方向感覚を持たない場合に、初期状態でｗａｉｔ状態のプロセスが要素を全隣接プロセスに送信し、ｗａｉｔ状態の間は毎ラウンド、それぞれの隣接プロセスから受信した要素をそのままもう一方の隣接プロセスへ送信し、ｗａｉｔ状態から他の状態に遷移するときに受信する制御メッセージとその受信した方向により各通信リンクがｌｅｆｔかｒｉｇｈｔかを判断し、ｌｅｆｔメッセージを受信した時点で、ｒｉｇｈｔからｒｉｇｈｔメッセージを伴わずに受信した要素を削除する手順を実行させることができる。
【００５８】あるいは、本発明のプログラムは、コンピュータ装置にインストールすることにより、そのコンピュータ装置に本発明のタスク割当方法を実行する機能を実現させることを特徴とする。
【００５９】本発明の第四の観点は、本発明のプログラムが記録されたコンピュータ装置読み取り可能な記録媒体である。この記録媒体によりコンピュータ装置に本発明のプログラムをインストールすることによりそのコンピュータ装置を本発明のタスク割当装置に相応する装置とし、このコンピュータ装置に本発明のタスク割当方法を実行させる。コンピュータ装置への本発明のプログラムのインストールは、サーバからのダウンロードによって行うこともできる。
【００６０】以下ではより詳細な本方法を記述する。なお、［数１１］は二つの多重集合Ａ、Ｂの多重和集合を表す。［外９］は代入を“＝”は比較を表す。また、方向感覚を持たない場合などに追加される処理は先に述べたとおりなので、詳細なアルゴリズムは示さない。さらに、アルゴリズムの記述の区切りごとに、文章による説明を入れる。
【外９】
【数１１】
【００６１】
【数１２】
【００６２】
【数１３】
【００６３】
【数１４】
【００６４】
【数１５】
【００６５】
【数１６】
【００６６】
【数１７】
【００６７】
【数１８】
【００６８】
【数１９】
【００６９】
【数２０】
【００７０】
【数２１】
【００７１】
【数２２】
【００７２】
【数２３】
【００７３】
【数２４】
【００７４】
【数２５】
【００７５】
【数２６】
【００７６】
【数２７】
【００７７】
【数２８】
【００７８】
【数２９】
【００７９】
【数３０】
【００８０】
【数３１】
【００８１】
【数３２】
【００８２】
【数３３】
【００８３】
【数３４】
【００８４】
【数３５】
【００８５】
【数３６】
【００８６】
【数３７】
【００８７】
【数３８】
【００８８】
【数３９】
【００８９】
【数４０】
【００９０】
【数４１】
【００９１】
【数４２】
【００９２】
【数４３】
【００９３】
【数４４】
【００９４】
【数４５】
【００９５】
【数４６】
【００９６】
【数４７】
【００９７】
【数４８】
【００９８】
【数４９】
【００９９】
【数５０】
【０１００】（実行例）ここでは上記アルゴリズムおよび上記アルゴリズムを用いたタスク割当方法の実行例を示す。ただし、方向感覚を持たない場合などで処理が追加された場合の実行例は、ここで示す実行例と本質的な相違があるわけではないので示さない。まず、上記アルゴリズムの特徴的な動作例を四つ示す。最初の例におけるプロセス数が少ない場合でのみメッセージの内容も表示して詳細な実行例を示すが、残りは各ラウンドにおける要素の位置のみ示す。
【０１０１】
【数５１】
【０１０２】
【数５２】
【０１０３】
【数５３】
【０１０４】
【数５４】
【０１０５】
【数５５】
【０１０６】
【数５６】
【０１０７】
【数５７】
【０１０８】
【数５８】
【０１０９】例２：［外６］に属するプロセスが左半分に偏って分布している場合例１の図２０および図２１により、実行に要する時間が初期状態に依存しないことがわかるので、例２以降では例１の図２０に示した実行例と比較するために、全てｎ＝１４で初期状態における要素の並びが左から順に降順になっている場合の実行例を示す。例２では、［外６］に属するプロセスが左半分に偏って分布している場合の実行例として、図２５に［数５９］の場合の実行例を示す。
【数５９】
【０１１０】例３：［外６］に属するプロセスが右半分に偏って分布している場合例３では、［外６］に属するプロセスが右半分に偏って分布している場合の実行例として、図１８に［数６０］の場合の実行例を示す。
【数６０】
【０１１１】例４：全プロセスが［外６］に属する場合（分散ソーティング問題と同一）
例４では、全プロセスが［外６］に属する場合、つまり、分散ソーティング問題と同一の問題に対する実行例を図２４に示す。
【０１１２】例５：負荷均衡化を実現するタスク割当方法の例実行例の最後に、このアルゴリズムを利用した負荷均衡化方法を適用した例を示す。本発明においては、アルゴリズムを繰り返し適用する際に、割り当てられなかったタスクの扱いを規定していない。そのため、この例においては以下のように定める。
【０１１３】割り当てられなかったタスクは毎回ｎ−ｋ個生じる。それらタスクを［外１０］から［外８］が一つずつ保持するように、アルゴリズム中では削除されてしまうタスクを移動させる。ここではその具体的な方法は定めていないので、例においてはこのタスクの移動の詳細は示さない。さらに、アルゴリズムの実行の詳細は例１から例４までと同様のため、この例５では示さず、実行結果のみを示す。つまり、この例５では１回のタスク割当を１フェイズとして、１フェイズずつ示す。
【外１０】
【０１１４】ここでは、３台のサーバと６台のクライアントから構成される線形ネットワークにおいて、各サーバは未割当タスクを持たず、各クライアントが一つずつ優先度が等しい未割当タスクを持つ場合のタスク割当方法を示す。そして、各タスクの大きさがわかっているとして、負荷均衡化を考慮したタスクの割当を行う。なお、実際のシステムにおいては、動的にタスクが発生し、各クライアントが持つタスク数やタスクの優先度も等しいとは限らないので、この例よりも複雑になるが、基本となる処理は同じである。この例では、タスクが６個でサーバが３台なので、２フェイズですべてのタスクの割当が完了する。図２５にこの状況における初期状態、フェイズ１終了時の状態、フェイズ２終了時の状態を示す。各数値はタスクの大きさを表し、フェイズ２終了時点におけるサーバの負荷量はサーバが持つ二つのタスクの大きさの合計となる。なお、先に述べたように、タスクを持たないプロセスは要素として∞を持つものとして処理されるが、図２５においては明示しない。
【０１１５】この例においては６タスクの大きさの合計が２４なので、各サーバの負荷量が８ずつになるのが理想である。しかし、大きさ７のタスクがあるものの大きさ１のタスクが存在しないので、負荷量をちょうど８ずつにすることができない。そのため、この場合に最も負荷が均衡した状況は負荷量がそれぞれ７、８、９となる場合である。この結果を見ると、サーバ［数６１］の負荷量はそれぞれ９、８、７となっているので、それを実現できていることがわかる。全ての場合にこのように均衡化させることができるわけではないが、ある程度の均衡化が期待できる。
【数６１】
【０１１６】
【発明の効果】本発明により、従来はサーバネットワークにのみ依存していたタスク割当／負荷均衡化を、クライアントを含むネットワークで行うことができるようになる。ただし、現状では線形ネットワーク上のアルゴリズムしか構築されていないため、木形状等のネットワークでは現状では直接使用できないが、アルゴリズムだけを拡張すれば、タスク割当／負荷均衡化は同じ枠組みで実現できる。
【０１１７】なお、本発明はタスク割当を前提にして説明したが、同じ方法により、資源割当も行うことができる。例えば、サーバが持つデータベースへのアクセス権を本アルゴリズムにより各サーバに対して一つずつ割り当てる、ということが考えられる。これ以外にも、出力するプリンタの割当等にも利用できる。
【０１１８】一方、本発明で使用しているアルゴリズムは、従来は議論されていない新しい問題設定に対するアルゴリズムである。そして、厳密に最適な時間で実行されるという特徴を持つ。
【０１１９】なお、実際にクライアントにこのような処理をさせることは非現実的と見なされるかもしれないが、認証等のためのクライアント側の負荷と同様に考えれば、そのサーバを利用するためのアクセスプログラムに本発明の処理を埋め込むことで、クライアント側のユーザに本発明による挙動をあまり意識させずに実行することが期待できる。
|
| 【出願人】 |
【識別番号】０００００４２２６
【氏名又は名称】日本電信電話株式会社
|
| 【出願日】 |
平成１３年４月１３日（２００１．４．１３） |
| 【代理人】 |
【識別番号】１０００７８２３７
【弁理士】
【氏名又は名称】井出 直孝 （外１名）
|
| 【公開番号】 |
特開２００２−３１２３３７（Ｐ２００２−３１２３３７Ａ） |
| 【公開日】 |
平成１４年１０月２５日（２００２．１０．２５） |
| 【出願番号】 |
特願２００１−１１５５２２（Ｐ２００１−１１５５２２） |
|