タスク割当装置およびタスク割当方法
【課題】分散処理システムにおいて、処理結果を取得するまでの時間を考慮してタスクを割当てる技術を提供する。
【解決手段】複数の情報処理装置が通信ネットワークで接続された分散処理システムにおいて、タスクを情報処理装置に割当てるタスク割当装置に、複数の情報処理装置の演算能力、通信オーバヘッド時間およびデータ転送速度を記憶する演算資源記憶手段と、依頼されたタスクの実行に必要な演算量およびタスクを情報処理装置に割当てたときに発生する転送データ量を取得するタスク情報取得部と、演算資源記憶手段に記憶された情報処理装置に関する情報と、タスク情報取得手段によって取得されたタスクの演算量および転送データ量とに基づいて、タスクを割当てる情報処理装置を決定するタスク割当先決定手段と、を備える。
【解決手段】複数の情報処理装置が通信ネットワークで接続された分散処理システムにおいて、タスクを情報処理装置に割当てるタスク割当装置に、複数の情報処理装置の演算能力、通信オーバヘッド時間およびデータ転送速度を記憶する演算資源記憶手段と、依頼されたタスクの実行に必要な演算量およびタスクを情報処理装置に割当てたときに発生する転送データ量を取得するタスク情報取得部と、演算資源記憶手段に記憶された情報処理装置に関する情報と、タスク情報取得手段によって取得されたタスクの演算量および転送データ量とに基づいて、タスクを割当てる情報処理装置を決定するタスク割当先決定手段と、を備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信ネットワークで接続された分散処理システムにおいてタスクを割当てる技術に関する。
【背景技術】
【０００２】
複数のコンピュータがネットワークによって接続された分散処理システムでは、実行する処理を複数の部分（タスク）に分割し、これらのコンピュータが並列的に処理している。この際、各コンピュータにタスクを適切に振り分けることで、演算資源を効率的に利用することができ、したがって、システム全体の負荷分散および処理速度の高速化が可能となる。これは、特許文献１に記載のように、各コンピュータの負荷状況を把握し、最も負荷の低いコンピュータに対してタスクを実行させることによって実現されている。
【特許文献１】特開平１１−３３２３号公報
【特許文献２】特開２００３−２９８５９９号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
しかしながら、上記のような従来技術の場合、各コンピュータの負荷状況（ＣＰＵ処理能力、空きメモリ容量等）のみを基準にタスクの割当先を決定しているため、実際に最も早く処理が完了するコンピュータにタスクが割当てられない場合があるという問題点があった。
【０００４】
すなわち、各コンピュータはネットワークを介して接続されており、タスクを実行するには必要に応じてこのネットワークを通じてデータやプログラム等を転送する必要がある。したがって、例えば、大量のデータを通信しなければならないときに、プロセッサの処理速度は速いがデータ転送速度の遅い通信路に接続されているコンピュータにタスクを割当てると、処理結果を取得するまでに時間がかかってしまうという問題があった。
【０００５】
このように、従来の技術では、割当先のコンピュータでの処理時間が短くなるようにタスクが割当てられており、割当から処理結果を取得できるまでの時間は考慮されていなかった。
【０００６】
これは特に、分散処理システムを、処理時間保証に対する要求が厳しいリアルタイム用途に使用する場合に問題となる。
【０００７】
本発明は上記実情に鑑みてなされたものであって、その目的とするところは、分散処理システムにおいて、処理結果を取得するまでの時間を考慮してタスクを割当てる技術を提供することにある。
【課題を解決するための手段】
【０００８】
上記目的を達成するために本発明は、以下のような構成をとる。
【０００９】
本発明に係るタスク割当装置は、複数の情報処理装置が通信ネットワークで接続された分散処理システムにおいて、実行を依頼されたタスクを情報処理装置に割当てるタスク割当装置である。タスク割当装置は、タスクの実行依頼を受け付け、このタスクを実行すべき情報処理装置を決定しタスクを割当てる。タスク割当装置は、タスクを割当てた情報処理装置に対しタスクを転送し、情報処理装置からの処理結果を受け取る。そして処理結果を得た後に依頼元に対して処理結果を送信する。
【００１０】
本発明にかかるタスク割当装置は、演算資源記憶手段とタスク情報取得手段とタスク割当先決定手段とを有する。
【００１１】
演算資源記憶手段は、システム内の複数の情報処理装置（演算資源）の演算能力、通信オーバヘッド時間およびデータ転送速度を記憶する。
【００１２】
情報処理装置の演算能力は、例えば、ＣＰＵ（中央演算処理装置）が単位時間当たりに行える計算量をあらわす情報や、ＣＰＵの使用率や、使用可能メモリ容量や、その他演算処理に影響のある情報や、これらの組み合わせを使用することができる。また、ＣＰＵが単位時間当たりに行える計算量としては、ＭＩＰＳ（Ｍｉｌｌｉｏｎ Ｉｎｓｔｒｕｃｔｉｏｎｓ Ｐｅｒ Ｓｅｃｏｎｄ）などの数値や、ＣＰＵの種類やその動作周波数などを用いることができる。
【００１３】
通信オーバヘッド時間は、通信を開始する命令を実行してから実際に通信が開始されるまでにかかる時間であり、送信しようとする転送データ量に無関係の時間である。
【００１４】
データ転送速度は、単位時間当たりに転送することのできるデータ量である。
【００１５】
タスク情報取得手段は、依頼されたタスクの実行に必要な演算量およびタスクを情報処理装置に割当てたときに発生する転送データ量を取得する。タスクの実行に必要な演算量とは、タスクが割当てられた情報処理装置で行われる演算量である。タスクを情報処理装置に割当てたときに発生する転送データ量とは、タスクを情報処理装置に割当てたときにその情報処理装置に送信するデータやプログラムのデータ量である。また、タスクの実行完了後に情報処理装置からタスク割当装置に送信される処理結果のデータ量を含むものであっても良い。
【００１６】
タスクの演算量および転送データ量は、タスク割当装置にタスクの実行が依頼されるときに同時に通知されても良いし、タスク自身の中に記録されていても良い。
【００１７】
タスク割当先決定手段は、タスクの実行を依頼されたときに、演算資源記憶手段に記憶された情報処理装置に関する情報と、タスク情報取得手段によって取得されたタスクの演算量および転送データ量とに基づいて、タスクを割当てる情報処理装置を決定する。この際、最も早く処理結果が得られる情報処理装置にタスクを割当てても良いし、タスクの実行完了までの制限時間（デッドライン）が決められている場合には時間内に処理を終了することのできる情報処理装置のうちの適当なものにタスクを割当てても良い。
【００１８】
このように、本発明に係るタスク割当装置は、各情報処理装置について演算能力と、通信オーバヘッド時間およびデータ転送速度の通信に関わる情報とを記憶し、これらとタスクの演算量および転送データ量とに基づいてタスクを割当てる情報処理装置を決定するため、単に演算に要する時間だけではなく通信時間をも含むタスクの割当から処理結果取得までの時間を考慮して、タスクの割当先を決定することが可能となる。
【００１９】
また、通信処理にかかる時間を、転送データ量に拘らず各情報処理装置ごとに一定である通信オーバヘッド時間と、実際のデータ転送にかかる時間（転送データ量とデータ転送速度）に分けて見積もることができるため、より正確な評価をすることが可能である。
【００２０】
また、本発明におけるタスク割当先決定手段は、演算資源記憶手段に記憶されている情報処理装置の演算能力、通信オーバヘッド時間およびデータ転送速度と、タスクの演算量および転送データ量とを変数とする評価関数によって各情報処理装置のタスク処理能力を
評価し、このタスク処理能力に基づいてタスクを割当てる情報処理装置を決定しても良い。
【００２１】
タスク処理能力とは、情報処理装置の演算処理に関する能力だけでなく、情報処理装置との間での通信処理に関する能力も含めた処理能力のことであり、タスクを割当ててから処理結果を得るまでの間の全ての処理を如何に早く行えるかを表すものである。
【００２２】
このように評価関数を用いることにより、タスクの割当先を決定することが容易となる。
【００２３】
また、本発明におけるタスク割当先決定手段は、演算能力および演算量から演算時間を推定し、通信オーバヘッド時間、データ転送速度および転送データ量から通信時間を推定し、演算時間と通信時間の和をタスク処理能力とする評価関数を用いることも好ましい。
【００２４】
演算能力と演算量から演算時間を推定することができる。また、転送データ量とデータ転送速度からデータの転送に要する時間を推定でき、これに通信オーバヘッド時間を加えることで通信時間を推定することができる。
【００２５】
そしてこれらの和を情報処理装置の有するタスク処理能力とする評価関数を用いる。すなわち、上記和が小さいほどタスク処理能力が高いということになる。
【００２６】
このようにタスクを割当ててから処理結果を得るまでの時間を予測してタスクを割当てる情報処理装置を決定するため、最も早く処理が完了する情報処理装置にタスクを割当てることが可能となる。
【００２７】
また、本発明におけるタスク割当先決定手段は、タスク情報取得手段が取得したタスクの演算量と転送データ量のうちどちらがタスクの処理結果を得るまでの時間に与える影響が大きいか判断する。つまり、依頼されたタスクが、演算量が多く演算に要する時間が長いのか、転送データ量が多く通信に要する時間が長いのかを判断する。そして、演算量が与える影響度が大きいと判断したときは、演算能力の重み付けを大きくした評価関数を用い、転送データ量が与える影響度が大きいと判断したときは、通信オーバヘッド時間およびデータ転送速度の重み付けを大きくした評価関数を用いることが好ましい。
【００２８】
ここで、上記の判断は、例えば、転送データ量が所定の閾値以上であるか否かで判断することができる。つまり、転送データ量が閾値以上であれば、転送データ量が与える影響度が大きいと判断し、転送データ量が閾値未満であれば、演算量が与える影響度が大きいと判断する。
【００２９】
この判断の結果、転送データ量の影響度が大きいと判断された場合には、通信オーバヘッド時間およびデータ転送速度に大きく重み付けし、演算能力に小さく重み付けして割当先を決定しても良く、データ転送速度のみに基づいて（つまり、演算能力の重み付けが０として）割当先の情報処理装置を決定しても良い。演算量の影響度が大きいと判断された場合には、演算能力に大きく重み付けし、通信オーバヘッド時間およびデータ転送速度に小さく重み付けして割当先を決定しても良く、演算能力のみに基づいて（つまり、データ転送速度の重み付けが０として）割当先の情報処理装置を決定しても良い。
【００３０】
このように、演算量の多いタスクか通信量の多いタスクかを判別し、異なる評価関数を用いることで、タスクの種類に応じた割当先を容易に決定することが可能となる。
【００３１】
本発明は、移動端末である情報処理装置が無線通信ネットワークによって接続された分
散処理システムに対して適用された場合に有効性がより発揮される。無線通信では、電波状況により通信オーバヘッド時間やデータ転送速度が変わるため、これらの情報をタスクの割当先の決定に用いる重要性が増すからである。
【００３２】
また、本発明に係るタスク割当装置は、情報処理装置通信する際の通信オーバヘッド時間およびデータ転送速度を定期的に測定する演算資源監視手段を有することも好ましい。そして、演算資源監視手段は、演算資源記憶手段に記憶されている通信オーバヘッド時間およびデータ転送速度を更新する。
【００３３】
通信オーバヘッド時間およびデータ転送速度の測定は、実際にデータを送信して測定しても良く、電波強度やエラー率を測定することにより推定しても良い。
【００３４】
このように、通信オーバヘッド時間およびデータ転送速度を測定することにより、電波状況の変化に応じた通信オーバヘッド時間およびデータ転送速度の変化を適切に把握することが可能となる。したがって、タスクの割当先決定においてより正確な判断が可能となる。
【００３５】
また、タスクの優先度を考慮してタスクの割当先を決定することも好ましい。タスクの優先度は次のように割当先決定の際に考慮される。本発明におけるタスクには、それぞれ優先度が付されており、演算資源記憶手段は、情報処理装置にすでに割当てられているタスクの優先度を記憶する。そして、タスク割当先決定手段は、依頼されたタスクの優先度と、情報処理装置にすでに割当てられているタスクの優先度とを考慮して、依頼されたタスクを割当てる情報処理装置を決定する。
【００３６】
このように優先度を用いることで、重要なタスクを早く処理する優先制御が可能となる。この際、依頼されたタスクより低い優先度のタスクが割当てられている情報処理装置もしくはタスクが割当てられていない情報処理装置にタスクを割当てることで、タスクを割当てた情報処理装置においてタスクがすぐに処理されることが保証される。
【００３７】
本発明に係るタスク割当方法は、複数の情報処理装置が通信ネットワークで接続された分散処理システムにおいて、タスクを情報処理装置に割当てるタスク割当方法である。本発明に係るタスク割当方法は、複数の情報処理装置の演算能力、通信オーバヘッド時間およびデータ転送速度を記憶する演算資源記憶手段を有するタスク割当装置が、依頼されたタスクの実行に必要な演算量およびタスクを情報処理装置に割当てたときに発生する転送データ量を取得するステップと、前記演算資源記憶手段に記憶された情報処理装置に関する情報と、前記取得するステップによって取得されたタスクの演算量および転送データ量とに基づいて、タスクを割当てる情報処理装置を決定するステップとを含む。
【発明の効果】
【００３８】
本発明によれば、分散処理システムにおいて処理結果を取得するまでの時間を考慮してタスクを割当てることが可能となる。
【発明を実施するための最良の形態】
【００３９】
以下に図面を参照して、この発明の好適な実施の形態を例示的に詳しく説明する。
【００４０】
ここでは、具体例として、路車間通信を使用して車両に搭載した車載端末から、基地局側に設置されたタスク割当装置にタスクを依頼する例を挙げる。
【００４１】
＜システム構成＞
図１は本実施形態のシステム構成を示す図である。路側に設置された基地局１にはＬＡ
Ｎを介してタスク割当装置２、依頼されたタスクを実行するサーバＤ，Ｅが接続されている。基地局１の通信可能エリア内に車両Ａ，Ｂ，Ｃが存在し、各車両には車載端末３ａ，３ｂ，３ｃがそれぞれ搭載されている。各車両の車載端末は、タスクの実行を基地局１を介してタスク割当装置２に依頼する。また、車載端末３ａ，３ｂ，３ｃも、タスク割当装置２からタスクを割当てられ、そのタスクを実行する。
【００４２】
図２は、タスク割当装置２の構成を示す概要図である。タスク割当装置２は、演算資源監視部１１、演算資源記憶部１４、タスク管理部１５、タスク情報取得部１６およびタスク割当先決定部１７を含む。
【００４３】
演算資源監視部１１は、システム内の演算資源（ここでは車載端末３ａ，３ｂ，３ｃおよびサーバＤ，Ｅ）についての情報を監視する。演算資源監視部１１が監視する情報は、各演算資源の演算能力に関する情報およびタスク割当装置２と演算資源との間の通信に関わる情報である。これらの情報は、各演算資源が定期的に演算資源監視部１１に通知する構成をとっても良く、演算資源監視部１１側から各演算資源に対して問い合わせを行う構成をとっても良い。
【００４４】
演算資源監視部１１が取得した情報は、演算資源記憶部１４に記憶される。図３は、演算資源記憶部１４が有する各演算資源の情報を記憶したテーブルを示す図である。
【００４５】
本実施形態において、演算資源の演算能力は、ＣＰＵ能力２１とＣＰＵにかかる負荷（ＣＰＵ空き率２２）とによって管理される。ＣＰＵ能力２１は、各演算資源の有するＣＰＵが単位時間当たりに行える演算の量に比例する点数（スコア）によって管理される。このＣＰＵ能力２１はＣＰＵに負荷がかからない状態での演算能力であるため、このＣＰＵ能力２１とＣＰＵ空き率２２とから、タスク割当時における各演算装置の実質的な演算能力を求めることができる。
【００４６】
通信オーバヘッド時間２３は、タスク割当装置２と演算資源との間で通信を行う際に、送信命令を指示してから実際に通信が開始されるまでに要する時間である。通信オーバヘッド時間２３は、送信するデータ量に影響を受けない値である。通信オーバヘッド時間２３は、例えば、送信元の端末が送信を指示した時刻と、受信先の端末が受信処理を開始した時刻との差分として求めることができる。
【００４７】
データ転送速度２４は、タスク割当装置２と演算資源との間で通信を行う際に単位時間当たりに送信することのできるデータ量である。データ転送速度２４は、例えば、過去に送信した単位時間当たりのデータ量から求めたり、定期的に一定長のデータを送信して、このデータを送信するのに要する時間を測定することによって求めたり、空き時間にある程度まとまった容量のデータを送信して、このデータを送信するのに要する時間を測定することによって求めることができる。
【００４８】
優先度２５は、演算資源に現在割当てられているタスクの優先度であり、ここでは数字が小さいほど優先度の高いタスクである。タスクが割当てられていない演算装置には、優先度についての情報は記憶されない。
【００４９】
タスク管理部１５は、依頼元からのタスクの実行依頼の受付、タスクの受信、演算資源へのタスクの転送、演算資源からのタスクの処理結果の受け取り、依頼元への処理結果の送信を行う。
【００５０】
タスク情報取得部１６は、依頼されたタスクの実行に必要な演算量、および演算資源との間で発生する転送データ量を取得する。演算量と、演算資源記憶部１４が記憶している
演算資源の演算能力とから、演算に要する時間を見積もることが可能である。
【００５１】
演算資源との間で発生する転送データ量は、タスクを転送する際に発生する通信量と、処理結果を受け取る際に発生する通信量の合計である。転送データ量と、演算資源記憶部１２が記憶している演算資源との間の転送速度とから通信に要する時間を見積もることが可能である。
【００５２】
タスク割当先決定部１７は、演算資源記憶部１４に記憶された情報およびタスク情報取得部１６が取得したタスクに関する情報に基づいて、タスク管理部１５が依頼を受け付けたタスクの割当先を決定する。割当先決定の処理については後述する。
【００５３】
＜タスク＞
本実施形態で実行が依頼されるタスクとしては、例えば経路探索処理などがある。経路探索処理は、一般道優先や所要時間優先の複数にタスクに分けたり、中間地点を指定して区間ごとに経路探索を行うタスクに分けたりすることができる。タスクの分割は、車載端末（ナビゲーションシステム）側で行っても良いし、タスク割当装置２内のタスク管理部１５で行っても良い。本実施形態においては、車載端末側でタスクを分割して、それぞれのタスクについてタスク割当装置２に対して実行を依頼するものとする。
【００５４】
＜処理フロー＞
タスク割当装置２にタスクの実行が依頼されてからタスクが演算資源に割当てるまでの処理の流れを図４のフローチャートを用いて説明する。
【００５５】
まずステップＳ１０１で、タスク管理部１５がタスクの依頼を受け付ける。次にステップＳ１０２で、タスク情報取得部１６が、依頼されたタスクの演算量および転送データ量とを取得する。
【００５６】
ステップＳ１０３で、タスク割当先決定部１７が演算資源記憶部１４に記憶された各演算資源に関する情報とタスク情報取得部１６が取得した演算量および転送データ量とに基づいて、タスクを割当てる演算資源を決定する。
【００５７】
ステップＳ１０４で、タスク管理部１５が割当先の演算資源に対してタスクを転送する。
【００５８】
＜割当先決定処理＞
ステップＳ１０３でタスク割当先決定部１７が行う、タスクの割当先の決定処理について説明する。
【００５９】
本実施形態においては、演算資源記憶部１４に記憶された演算資源の演算能力、通信オーバヘッド時間およびデータ転送速度と、タスク情報取得部１６が取得したタスクの演算量および転送データ量とを変数とする評価関数を用いて、各演算資源のタスク処理能力を評価する。本実施形態における評価関数では、タスクを演算資源に割当ててから処理結果が得られるまでの時間を演算資源のタスク処理能力とする。
【００６０】
本実施形態では、以下の評価関数によって、演算資源のタスク処理能力を評価する。
（タスク処理能力）＝（演算量）／（演算能力）＋（通信オーバヘッド時間）＋（転送データ量）／（データ転送速度）
【００６１】
図５は上記の評価関数を概念的に説明する図である。まず、タスクの演算量と演算資源の演算能力とから演算に要する時間を見積もることが可能である。本実施形態においては
、演算資源の演算能力を、ＣＰＵの処理能力とＣＰＵの負荷（空きＣＰＵ率）とで把握しているため、タスク割当時点での各演算資源の演算能力として、ＣＰＵの処理能力に空きＣＰＵ率を乗じたものを使用する。また、ＣＰＵの処理能力はスコアによって把握されており、所定のスコアを有するＣＰＵの処理できる演算量はあらかじめ分かるので、タスクの実行に要する演算量からタスクの演算に要する時間を見積もることが可能である。
【００６２】
また、転送データ量と転送速度に基づいて、データの転送に要する時間を見積もる。この転送時間と、通信を行う際に発生する通信オーバヘッド時間とを加えることで、通信時間を見積もる。
【００６３】
このように算出した演算時間と通信時間とを加えることで、タスクの転送から結果取得までに要する処理時間を求めることが可能である。本実施形態における評価関数ではこの処理時間を、各演算資源のタスク処理能力とし、処理時間の小さいものほどタスク処理能力が大きいものとする。
【００６４】
また、演算資源記憶部１４は、各演算資源に割当てられているタスクの優先度を記憶しており、依頼されたタスクの優先度以上の優先度が割当てられている演算資源にはタスクの割当を行わない。タスクを割当ててもすぐには実行されないからである。
【００６５】
タスク割当先決定部１７は、依頼されたタスクの優先度未満のタスクが割当てられている演算資源もしくはタスクが割当てられていない演算資源のうち、上記で算出したタスク処理能力が最も大きい演算資源にタスクを割当てるよう決定する。ただし、必ずしもタスク処理能力が最大の演算資源にタスクを割当てる必要はなく、タスクの処理完了までの制限時間（デッドライン）が決められている場合には、この制限時間以内に処理を完了できる演算資源であればいずれの演算資源にタスクを割当てても良い。
【００６６】
このように本実施形態におけるタスク割当装置２は、タスクを割当てる演算資源（情報処理装置）を決定する際に、演算に要する時間と通信に要する時間とを総合した時間に基づいて割当先を決定するため、タスクを割当ててから処理結果を得られるまでの時間が最短となる演算資源にタスクを割当てることが可能となる。
【００６７】
また、通信時間の算出において、転送データ量に依らない通信オーバヘッド時間と、転送データ量に比例するデータ転送速度とに分けて算出するので、より正確な通信時間を算出することができる。例えば、転送データ量が少ない場合には通信オーバヘッド時間が相対的に重要になり、転送データ量が多い場合にはデータ転送速度が相対的に重要になる。
【００６８】
また、本実施形態における分散処理システムは無線通信を用いた移動端末（車載端末）により構成されているため、端末の移動に伴い電波状況が常時変化する。演算資源監視部１１が、通信オーバヘッド時間やデータ転送速度を監視するため、通信状況に応じた割当が可能となる。
【００６９】
＜変形例＞
（割当先決定処理の変形例）
本実施形態におけるタスク割当先決定部１７は、上記のような割当先決定方法のほかに、依頼されたタスクが演算量の多いタスクか通信量の多いタスクかを判断して、異なる評価関数を使用する方法を用いても良い。
【００７０】
すなわち、評価関数として以下の関数を用い、重み付けパラメータであるｐおよびｑをタスクの種類に応じて異なる値を使用する。
（タスク処理能力）＝ｐＣ（演算量，演算能力）＋ｑＴ（転送データ量，通信オーバヘッ
ド時間，データ転送速度）
ここで、Ｃは演算量と演算能力から演算に関する能力（演算時間）を評価する関数、Ｔは転送データ量、通信オーバヘッド時間およびデータ転送速度から通信に関する能力（通信時間）を評価する関数であり、ｐおよびｑは重み付けパラメータである。
【００７１】
タスクの特性の解析は、例えば、通信量が所定の閾値以上であるか否かを判断し、所定の閾値以上であれば通信量の多いタスクとみなし、閾値未満であれば演算量の多いタスクとみなすことができる。
【００７２】
そして、演算量の多いタスクの場合には、ＣＰＵの処理能力とＣＰＵ空き率の重み付けを大きくし、転送速度と通信オーバヘッド時間の重み付けを小さくする評価関数を用いる。通信量の多いタスクの場合には、転送速度と通信オーバヘッド時間の重み付けを大きくし、ＣＰＵの処理能力とＣＰＵ空き率の重み付けを小さくする評価関数を用いる。
【００７３】
また、演算量の多いタスクの場合には、転送速度等への重み付けをなくし、ＣＰＵの処理能力とＣＰＵ空き率とを乗じた値をタスク処理能力とする評価関数を用いても良い。通信量の多いタスクの場合には、ＣＰＵ処理能力等への重み付けをなくし、転送速度と通信オーバヘッド時間に基づいた値をタスク処理能力とする評価関数を用いても良い。
【００７４】
このような処理により割当先を決定することで、簡単な処理によってタスクの特性に応じた評価を行うことができる。
【００７５】
（演算資源の監視方法の変形例）
本実施形態においては、演算能力としてＣＰＵの処理能力および負荷のみを用いたが、例えば、演算資源の使用可能メモリ量とタスク実行に要するメモリ量とを取得し、これらの情報も加味して割当先を決定しても良い。また、その他のリソースを考慮して割当先を決定しても良い。
【００７６】
また、本実施形態においては、通信オーバヘッド時間やデータ転送速度は、演算資源監視部１１が実測によって測定しているが、各演算装置が有するＯＳや使用機器毎にあらかじめ定められた値を用いても良い。これは、通信状況が安定しているときには、測定を省くことができるため効率的になるという利点がある。
【００７７】
（システム構成の変形例）
本実施形態において基地局１は１つであり、車両Ａ，Ｂ，Ｃは基地局１の通信可能エリア内に存在したが、図６に示すように複数の基地局１ａ，１ｂ，１ｃが存在しそれらがネットワークを介して存在するようなシステム構成であっても構わない。
【００７８】
このように複数の基地局がそれぞれネットワークで接続されることで、基地局の通信可能エリアを実質的に拡げたことになり、広範囲に及ぶシステムを構築することができる。
【００７９】
また、本実施形態においてはシステム内にタスク割当装置２が１つしか存在しなかったが、複数存在しても良い。例えば、図７に示すように基地局がなく各端末が自律的にネットワークを形成するアドホックネットワークにおいては、各端末（車両Ａ，Ｂ，Ｃ）がそれぞれタスク割当装置２ａ，２ｂ，２ｃを有することが好ましい。
【００８０】
車両Ａ，Ｂ，Ｃは車車間通信により、各車両が有する車載端末３ａ，３ｂ，３ｃの演算能力などの情報を互いに通知する。そして、車載端末からタスクを依頼するときは、自車が有するタスク割当装置に対して依頼を行う。
【００８１】
この際、このシステムは車車間通信のみでなく、さらに基地局との間の通信も行うことができ基地局側にタスクの演算を行えるサーバがあることも好ましい。この場合、一般的に車載端末は演算能力は低いが通信コストが低い演算資源であり、サーバは演算能力は高いが通信コストも高い演算資源といえる。したがって、このように多様な演算資源が混在する環境においては、各車両のタスク割当装置がタスクの特性に応じて適切な割当先を決定することの重要性が高まる。
【図面の簡単な説明】
【００８２】
【図１】本実施形態におけるシステム構成を示す概要図である。
【図２】本実施形態におけるタスク割当装置の構成を示す図である。
【図３】本実施形態における演算資源についての情報を記憶したテーブルの例を示す図である。
【図４】本実施形態におけるタスクの割当先を決定する処理を示すフローチャート図である。
【図５】本実施形態における各演算資源の処理能力の算出方法を説明する図である。
【図６】本実施形態におけるシステム構成を示す概要図である。
【図７】本実施形態におけるシステム構成を示す概要図である。
【符号の説明】
【００８３】
Ａ，Ｂ，Ｃ 車両
Ｄ，Ｅ サーバ
１ 基地局
２，２ａ，２ｂ，２ｃ タスク割当装置
３ａ，３ｂ，３ｃ 車載端末
１１ 演算資源監視部
１４ 演算資源記憶部
１５ タスク管理部
１６ タスク情報取得部
１７ タスク割当先決定部
【技術分野】
【０００１】
本発明は、通信ネットワークで接続された分散処理システムにおいてタスクを割当てる技術に関する。
【背景技術】
【０００２】
複数のコンピュータがネットワークによって接続された分散処理システムでは、実行する処理を複数の部分（タスク）に分割し、これらのコンピュータが並列的に処理している。この際、各コンピュータにタスクを適切に振り分けることで、演算資源を効率的に利用することができ、したがって、システム全体の負荷分散および処理速度の高速化が可能となる。これは、特許文献１に記載のように、各コンピュータの負荷状況を把握し、最も負荷の低いコンピュータに対してタスクを実行させることによって実現されている。
【特許文献１】特開平１１−３３２３号公報
【特許文献２】特開２００３−２９８５９９号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
しかしながら、上記のような従来技術の場合、各コンピュータの負荷状況（ＣＰＵ処理能力、空きメモリ容量等）のみを基準にタスクの割当先を決定しているため、実際に最も早く処理が完了するコンピュータにタスクが割当てられない場合があるという問題点があった。
【０００４】
すなわち、各コンピュータはネットワークを介して接続されており、タスクを実行するには必要に応じてこのネットワークを通じてデータやプログラム等を転送する必要がある。したがって、例えば、大量のデータを通信しなければならないときに、プロセッサの処理速度は速いがデータ転送速度の遅い通信路に接続されているコンピュータにタスクを割当てると、処理結果を取得するまでに時間がかかってしまうという問題があった。
【０００５】
このように、従来の技術では、割当先のコンピュータでの処理時間が短くなるようにタスクが割当てられており、割当から処理結果を取得できるまでの時間は考慮されていなかった。
【０００６】
これは特に、分散処理システムを、処理時間保証に対する要求が厳しいリアルタイム用途に使用する場合に問題となる。
【０００７】
本発明は上記実情に鑑みてなされたものであって、その目的とするところは、分散処理システムにおいて、処理結果を取得するまでの時間を考慮してタスクを割当てる技術を提供することにある。
【課題を解決するための手段】
【０００８】
上記目的を達成するために本発明は、以下のような構成をとる。
【０００９】
本発明に係るタスク割当装置は、複数の情報処理装置が通信ネットワークで接続された分散処理システムにおいて、実行を依頼されたタスクを情報処理装置に割当てるタスク割当装置である。タスク割当装置は、タスクの実行依頼を受け付け、このタスクを実行すべき情報処理装置を決定しタスクを割当てる。タスク割当装置は、タスクを割当てた情報処理装置に対しタスクを転送し、情報処理装置からの処理結果を受け取る。そして処理結果を得た後に依頼元に対して処理結果を送信する。
【００１０】
本発明にかかるタスク割当装置は、演算資源記憶手段とタスク情報取得手段とタスク割当先決定手段とを有する。
【００１１】
演算資源記憶手段は、システム内の複数の情報処理装置（演算資源）の演算能力、通信オーバヘッド時間およびデータ転送速度を記憶する。
【００１２】
情報処理装置の演算能力は、例えば、ＣＰＵ（中央演算処理装置）が単位時間当たりに行える計算量をあらわす情報や、ＣＰＵの使用率や、使用可能メモリ容量や、その他演算処理に影響のある情報や、これらの組み合わせを使用することができる。また、ＣＰＵが単位時間当たりに行える計算量としては、ＭＩＰＳ（Ｍｉｌｌｉｏｎ Ｉｎｓｔｒｕｃｔｉｏｎｓ Ｐｅｒ Ｓｅｃｏｎｄ）などの数値や、ＣＰＵの種類やその動作周波数などを用いることができる。
【００１３】
通信オーバヘッド時間は、通信を開始する命令を実行してから実際に通信が開始されるまでにかかる時間であり、送信しようとする転送データ量に無関係の時間である。
【００１４】
データ転送速度は、単位時間当たりに転送することのできるデータ量である。
【００１５】
タスク情報取得手段は、依頼されたタスクの実行に必要な演算量およびタスクを情報処理装置に割当てたときに発生する転送データ量を取得する。タスクの実行に必要な演算量とは、タスクが割当てられた情報処理装置で行われる演算量である。タスクを情報処理装置に割当てたときに発生する転送データ量とは、タスクを情報処理装置に割当てたときにその情報処理装置に送信するデータやプログラムのデータ量である。また、タスクの実行完了後に情報処理装置からタスク割当装置に送信される処理結果のデータ量を含むものであっても良い。
【００１６】
タスクの演算量および転送データ量は、タスク割当装置にタスクの実行が依頼されるときに同時に通知されても良いし、タスク自身の中に記録されていても良い。
【００１７】
タスク割当先決定手段は、タスクの実行を依頼されたときに、演算資源記憶手段に記憶された情報処理装置に関する情報と、タスク情報取得手段によって取得されたタスクの演算量および転送データ量とに基づいて、タスクを割当てる情報処理装置を決定する。この際、最も早く処理結果が得られる情報処理装置にタスクを割当てても良いし、タスクの実行完了までの制限時間（デッドライン）が決められている場合には時間内に処理を終了することのできる情報処理装置のうちの適当なものにタスクを割当てても良い。
【００１８】
このように、本発明に係るタスク割当装置は、各情報処理装置について演算能力と、通信オーバヘッド時間およびデータ転送速度の通信に関わる情報とを記憶し、これらとタスクの演算量および転送データ量とに基づいてタスクを割当てる情報処理装置を決定するため、単に演算に要する時間だけではなく通信時間をも含むタスクの割当から処理結果取得までの時間を考慮して、タスクの割当先を決定することが可能となる。
【００１９】
また、通信処理にかかる時間を、転送データ量に拘らず各情報処理装置ごとに一定である通信オーバヘッド時間と、実際のデータ転送にかかる時間（転送データ量とデータ転送速度）に分けて見積もることができるため、より正確な評価をすることが可能である。
【００２０】
また、本発明におけるタスク割当先決定手段は、演算資源記憶手段に記憶されている情報処理装置の演算能力、通信オーバヘッド時間およびデータ転送速度と、タスクの演算量および転送データ量とを変数とする評価関数によって各情報処理装置のタスク処理能力を
評価し、このタスク処理能力に基づいてタスクを割当てる情報処理装置を決定しても良い。
【００２１】
タスク処理能力とは、情報処理装置の演算処理に関する能力だけでなく、情報処理装置との間での通信処理に関する能力も含めた処理能力のことであり、タスクを割当ててから処理結果を得るまでの間の全ての処理を如何に早く行えるかを表すものである。
【００２２】
このように評価関数を用いることにより、タスクの割当先を決定することが容易となる。
【００２３】
また、本発明におけるタスク割当先決定手段は、演算能力および演算量から演算時間を推定し、通信オーバヘッド時間、データ転送速度および転送データ量から通信時間を推定し、演算時間と通信時間の和をタスク処理能力とする評価関数を用いることも好ましい。
【００２４】
演算能力と演算量から演算時間を推定することができる。また、転送データ量とデータ転送速度からデータの転送に要する時間を推定でき、これに通信オーバヘッド時間を加えることで通信時間を推定することができる。
【００２５】
そしてこれらの和を情報処理装置の有するタスク処理能力とする評価関数を用いる。すなわち、上記和が小さいほどタスク処理能力が高いということになる。
【００２６】
このようにタスクを割当ててから処理結果を得るまでの時間を予測してタスクを割当てる情報処理装置を決定するため、最も早く処理が完了する情報処理装置にタスクを割当てることが可能となる。
【００２７】
また、本発明におけるタスク割当先決定手段は、タスク情報取得手段が取得したタスクの演算量と転送データ量のうちどちらがタスクの処理結果を得るまでの時間に与える影響が大きいか判断する。つまり、依頼されたタスクが、演算量が多く演算に要する時間が長いのか、転送データ量が多く通信に要する時間が長いのかを判断する。そして、演算量が与える影響度が大きいと判断したときは、演算能力の重み付けを大きくした評価関数を用い、転送データ量が与える影響度が大きいと判断したときは、通信オーバヘッド時間およびデータ転送速度の重み付けを大きくした評価関数を用いることが好ましい。
【００２８】
ここで、上記の判断は、例えば、転送データ量が所定の閾値以上であるか否かで判断することができる。つまり、転送データ量が閾値以上であれば、転送データ量が与える影響度が大きいと判断し、転送データ量が閾値未満であれば、演算量が与える影響度が大きいと判断する。
【００２９】
この判断の結果、転送データ量の影響度が大きいと判断された場合には、通信オーバヘッド時間およびデータ転送速度に大きく重み付けし、演算能力に小さく重み付けして割当先を決定しても良く、データ転送速度のみに基づいて（つまり、演算能力の重み付けが０として）割当先の情報処理装置を決定しても良い。演算量の影響度が大きいと判断された場合には、演算能力に大きく重み付けし、通信オーバヘッド時間およびデータ転送速度に小さく重み付けして割当先を決定しても良く、演算能力のみに基づいて（つまり、データ転送速度の重み付けが０として）割当先の情報処理装置を決定しても良い。
【００３０】
このように、演算量の多いタスクか通信量の多いタスクかを判別し、異なる評価関数を用いることで、タスクの種類に応じた割当先を容易に決定することが可能となる。
【００３１】
本発明は、移動端末である情報処理装置が無線通信ネットワークによって接続された分
散処理システムに対して適用された場合に有効性がより発揮される。無線通信では、電波状況により通信オーバヘッド時間やデータ転送速度が変わるため、これらの情報をタスクの割当先の決定に用いる重要性が増すからである。
【００３２】
また、本発明に係るタスク割当装置は、情報処理装置通信する際の通信オーバヘッド時間およびデータ転送速度を定期的に測定する演算資源監視手段を有することも好ましい。そして、演算資源監視手段は、演算資源記憶手段に記憶されている通信オーバヘッド時間およびデータ転送速度を更新する。
【００３３】
通信オーバヘッド時間およびデータ転送速度の測定は、実際にデータを送信して測定しても良く、電波強度やエラー率を測定することにより推定しても良い。
【００３４】
このように、通信オーバヘッド時間およびデータ転送速度を測定することにより、電波状況の変化に応じた通信オーバヘッド時間およびデータ転送速度の変化を適切に把握することが可能となる。したがって、タスクの割当先決定においてより正確な判断が可能となる。
【００３５】
また、タスクの優先度を考慮してタスクの割当先を決定することも好ましい。タスクの優先度は次のように割当先決定の際に考慮される。本発明におけるタスクには、それぞれ優先度が付されており、演算資源記憶手段は、情報処理装置にすでに割当てられているタスクの優先度を記憶する。そして、タスク割当先決定手段は、依頼されたタスクの優先度と、情報処理装置にすでに割当てられているタスクの優先度とを考慮して、依頼されたタスクを割当てる情報処理装置を決定する。
【００３６】
このように優先度を用いることで、重要なタスクを早く処理する優先制御が可能となる。この際、依頼されたタスクより低い優先度のタスクが割当てられている情報処理装置もしくはタスクが割当てられていない情報処理装置にタスクを割当てることで、タスクを割当てた情報処理装置においてタスクがすぐに処理されることが保証される。
【００３７】
本発明に係るタスク割当方法は、複数の情報処理装置が通信ネットワークで接続された分散処理システムにおいて、タスクを情報処理装置に割当てるタスク割当方法である。本発明に係るタスク割当方法は、複数の情報処理装置の演算能力、通信オーバヘッド時間およびデータ転送速度を記憶する演算資源記憶手段を有するタスク割当装置が、依頼されたタスクの実行に必要な演算量およびタスクを情報処理装置に割当てたときに発生する転送データ量を取得するステップと、前記演算資源記憶手段に記憶された情報処理装置に関する情報と、前記取得するステップによって取得されたタスクの演算量および転送データ量とに基づいて、タスクを割当てる情報処理装置を決定するステップとを含む。
【発明の効果】
【００３８】
本発明によれば、分散処理システムにおいて処理結果を取得するまでの時間を考慮してタスクを割当てることが可能となる。
【発明を実施するための最良の形態】
【００３９】
以下に図面を参照して、この発明の好適な実施の形態を例示的に詳しく説明する。
【００４０】
ここでは、具体例として、路車間通信を使用して車両に搭載した車載端末から、基地局側に設置されたタスク割当装置にタスクを依頼する例を挙げる。
【００４１】
＜システム構成＞
図１は本実施形態のシステム構成を示す図である。路側に設置された基地局１にはＬＡ
Ｎを介してタスク割当装置２、依頼されたタスクを実行するサーバＤ，Ｅが接続されている。基地局１の通信可能エリア内に車両Ａ，Ｂ，Ｃが存在し、各車両には車載端末３ａ，３ｂ，３ｃがそれぞれ搭載されている。各車両の車載端末は、タスクの実行を基地局１を介してタスク割当装置２に依頼する。また、車載端末３ａ，３ｂ，３ｃも、タスク割当装置２からタスクを割当てられ、そのタスクを実行する。
【００４２】
図２は、タスク割当装置２の構成を示す概要図である。タスク割当装置２は、演算資源監視部１１、演算資源記憶部１４、タスク管理部１５、タスク情報取得部１６およびタスク割当先決定部１７を含む。
【００４３】
演算資源監視部１１は、システム内の演算資源（ここでは車載端末３ａ，３ｂ，３ｃおよびサーバＤ，Ｅ）についての情報を監視する。演算資源監視部１１が監視する情報は、各演算資源の演算能力に関する情報およびタスク割当装置２と演算資源との間の通信に関わる情報である。これらの情報は、各演算資源が定期的に演算資源監視部１１に通知する構成をとっても良く、演算資源監視部１１側から各演算資源に対して問い合わせを行う構成をとっても良い。
【００４４】
演算資源監視部１１が取得した情報は、演算資源記憶部１４に記憶される。図３は、演算資源記憶部１４が有する各演算資源の情報を記憶したテーブルを示す図である。
【００４５】
本実施形態において、演算資源の演算能力は、ＣＰＵ能力２１とＣＰＵにかかる負荷（ＣＰＵ空き率２２）とによって管理される。ＣＰＵ能力２１は、各演算資源の有するＣＰＵが単位時間当たりに行える演算の量に比例する点数（スコア）によって管理される。このＣＰＵ能力２１はＣＰＵに負荷がかからない状態での演算能力であるため、このＣＰＵ能力２１とＣＰＵ空き率２２とから、タスク割当時における各演算装置の実質的な演算能力を求めることができる。
【００４６】
通信オーバヘッド時間２３は、タスク割当装置２と演算資源との間で通信を行う際に、送信命令を指示してから実際に通信が開始されるまでに要する時間である。通信オーバヘッド時間２３は、送信するデータ量に影響を受けない値である。通信オーバヘッド時間２３は、例えば、送信元の端末が送信を指示した時刻と、受信先の端末が受信処理を開始した時刻との差分として求めることができる。
【００４７】
データ転送速度２４は、タスク割当装置２と演算資源との間で通信を行う際に単位時間当たりに送信することのできるデータ量である。データ転送速度２４は、例えば、過去に送信した単位時間当たりのデータ量から求めたり、定期的に一定長のデータを送信して、このデータを送信するのに要する時間を測定することによって求めたり、空き時間にある程度まとまった容量のデータを送信して、このデータを送信するのに要する時間を測定することによって求めることができる。
【００４８】
優先度２５は、演算資源に現在割当てられているタスクの優先度であり、ここでは数字が小さいほど優先度の高いタスクである。タスクが割当てられていない演算装置には、優先度についての情報は記憶されない。
【００４９】
タスク管理部１５は、依頼元からのタスクの実行依頼の受付、タスクの受信、演算資源へのタスクの転送、演算資源からのタスクの処理結果の受け取り、依頼元への処理結果の送信を行う。
【００５０】
タスク情報取得部１６は、依頼されたタスクの実行に必要な演算量、および演算資源との間で発生する転送データ量を取得する。演算量と、演算資源記憶部１４が記憶している
演算資源の演算能力とから、演算に要する時間を見積もることが可能である。
【００５１】
演算資源との間で発生する転送データ量は、タスクを転送する際に発生する通信量と、処理結果を受け取る際に発生する通信量の合計である。転送データ量と、演算資源記憶部１２が記憶している演算資源との間の転送速度とから通信に要する時間を見積もることが可能である。
【００５２】
タスク割当先決定部１７は、演算資源記憶部１４に記憶された情報およびタスク情報取得部１６が取得したタスクに関する情報に基づいて、タスク管理部１５が依頼を受け付けたタスクの割当先を決定する。割当先決定の処理については後述する。
【００５３】
＜タスク＞
本実施形態で実行が依頼されるタスクとしては、例えば経路探索処理などがある。経路探索処理は、一般道優先や所要時間優先の複数にタスクに分けたり、中間地点を指定して区間ごとに経路探索を行うタスクに分けたりすることができる。タスクの分割は、車載端末（ナビゲーションシステム）側で行っても良いし、タスク割当装置２内のタスク管理部１５で行っても良い。本実施形態においては、車載端末側でタスクを分割して、それぞれのタスクについてタスク割当装置２に対して実行を依頼するものとする。
【００５４】
＜処理フロー＞
タスク割当装置２にタスクの実行が依頼されてからタスクが演算資源に割当てるまでの処理の流れを図４のフローチャートを用いて説明する。
【００５５】
まずステップＳ１０１で、タスク管理部１５がタスクの依頼を受け付ける。次にステップＳ１０２で、タスク情報取得部１６が、依頼されたタスクの演算量および転送データ量とを取得する。
【００５６】
ステップＳ１０３で、タスク割当先決定部１７が演算資源記憶部１４に記憶された各演算資源に関する情報とタスク情報取得部１６が取得した演算量および転送データ量とに基づいて、タスクを割当てる演算資源を決定する。
【００５７】
ステップＳ１０４で、タスク管理部１５が割当先の演算資源に対してタスクを転送する。
【００５８】
＜割当先決定処理＞
ステップＳ１０３でタスク割当先決定部１７が行う、タスクの割当先の決定処理について説明する。
【００５９】
本実施形態においては、演算資源記憶部１４に記憶された演算資源の演算能力、通信オーバヘッド時間およびデータ転送速度と、タスク情報取得部１６が取得したタスクの演算量および転送データ量とを変数とする評価関数を用いて、各演算資源のタスク処理能力を評価する。本実施形態における評価関数では、タスクを演算資源に割当ててから処理結果が得られるまでの時間を演算資源のタスク処理能力とする。
【００６０】
本実施形態では、以下の評価関数によって、演算資源のタスク処理能力を評価する。
（タスク処理能力）＝（演算量）／（演算能力）＋（通信オーバヘッド時間）＋（転送データ量）／（データ転送速度）
【００６１】
図５は上記の評価関数を概念的に説明する図である。まず、タスクの演算量と演算資源の演算能力とから演算に要する時間を見積もることが可能である。本実施形態においては
、演算資源の演算能力を、ＣＰＵの処理能力とＣＰＵの負荷（空きＣＰＵ率）とで把握しているため、タスク割当時点での各演算資源の演算能力として、ＣＰＵの処理能力に空きＣＰＵ率を乗じたものを使用する。また、ＣＰＵの処理能力はスコアによって把握されており、所定のスコアを有するＣＰＵの処理できる演算量はあらかじめ分かるので、タスクの実行に要する演算量からタスクの演算に要する時間を見積もることが可能である。
【００６２】
また、転送データ量と転送速度に基づいて、データの転送に要する時間を見積もる。この転送時間と、通信を行う際に発生する通信オーバヘッド時間とを加えることで、通信時間を見積もる。
【００６３】
このように算出した演算時間と通信時間とを加えることで、タスクの転送から結果取得までに要する処理時間を求めることが可能である。本実施形態における評価関数ではこの処理時間を、各演算資源のタスク処理能力とし、処理時間の小さいものほどタスク処理能力が大きいものとする。
【００６４】
また、演算資源記憶部１４は、各演算資源に割当てられているタスクの優先度を記憶しており、依頼されたタスクの優先度以上の優先度が割当てられている演算資源にはタスクの割当を行わない。タスクを割当ててもすぐには実行されないからである。
【００６５】
タスク割当先決定部１７は、依頼されたタスクの優先度未満のタスクが割当てられている演算資源もしくはタスクが割当てられていない演算資源のうち、上記で算出したタスク処理能力が最も大きい演算資源にタスクを割当てるよう決定する。ただし、必ずしもタスク処理能力が最大の演算資源にタスクを割当てる必要はなく、タスクの処理完了までの制限時間（デッドライン）が決められている場合には、この制限時間以内に処理を完了できる演算資源であればいずれの演算資源にタスクを割当てても良い。
【００６６】
このように本実施形態におけるタスク割当装置２は、タスクを割当てる演算資源（情報処理装置）を決定する際に、演算に要する時間と通信に要する時間とを総合した時間に基づいて割当先を決定するため、タスクを割当ててから処理結果を得られるまでの時間が最短となる演算資源にタスクを割当てることが可能となる。
【００６７】
また、通信時間の算出において、転送データ量に依らない通信オーバヘッド時間と、転送データ量に比例するデータ転送速度とに分けて算出するので、より正確な通信時間を算出することができる。例えば、転送データ量が少ない場合には通信オーバヘッド時間が相対的に重要になり、転送データ量が多い場合にはデータ転送速度が相対的に重要になる。
【００６８】
また、本実施形態における分散処理システムは無線通信を用いた移動端末（車載端末）により構成されているため、端末の移動に伴い電波状況が常時変化する。演算資源監視部１１が、通信オーバヘッド時間やデータ転送速度を監視するため、通信状況に応じた割当が可能となる。
【００６９】
＜変形例＞
（割当先決定処理の変形例）
本実施形態におけるタスク割当先決定部１７は、上記のような割当先決定方法のほかに、依頼されたタスクが演算量の多いタスクか通信量の多いタスクかを判断して、異なる評価関数を使用する方法を用いても良い。
【００７０】
すなわち、評価関数として以下の関数を用い、重み付けパラメータであるｐおよびｑをタスクの種類に応じて異なる値を使用する。
（タスク処理能力）＝ｐＣ（演算量，演算能力）＋ｑＴ（転送データ量，通信オーバヘッ
ド時間，データ転送速度）
ここで、Ｃは演算量と演算能力から演算に関する能力（演算時間）を評価する関数、Ｔは転送データ量、通信オーバヘッド時間およびデータ転送速度から通信に関する能力（通信時間）を評価する関数であり、ｐおよびｑは重み付けパラメータである。
【００７１】
タスクの特性の解析は、例えば、通信量が所定の閾値以上であるか否かを判断し、所定の閾値以上であれば通信量の多いタスクとみなし、閾値未満であれば演算量の多いタスクとみなすことができる。
【００７２】
そして、演算量の多いタスクの場合には、ＣＰＵの処理能力とＣＰＵ空き率の重み付けを大きくし、転送速度と通信オーバヘッド時間の重み付けを小さくする評価関数を用いる。通信量の多いタスクの場合には、転送速度と通信オーバヘッド時間の重み付けを大きくし、ＣＰＵの処理能力とＣＰＵ空き率の重み付けを小さくする評価関数を用いる。
【００７３】
また、演算量の多いタスクの場合には、転送速度等への重み付けをなくし、ＣＰＵの処理能力とＣＰＵ空き率とを乗じた値をタスク処理能力とする評価関数を用いても良い。通信量の多いタスクの場合には、ＣＰＵ処理能力等への重み付けをなくし、転送速度と通信オーバヘッド時間に基づいた値をタスク処理能力とする評価関数を用いても良い。
【００７４】
このような処理により割当先を決定することで、簡単な処理によってタスクの特性に応じた評価を行うことができる。
【００７５】
（演算資源の監視方法の変形例）
本実施形態においては、演算能力としてＣＰＵの処理能力および負荷のみを用いたが、例えば、演算資源の使用可能メモリ量とタスク実行に要するメモリ量とを取得し、これらの情報も加味して割当先を決定しても良い。また、その他のリソースを考慮して割当先を決定しても良い。
【００７６】
また、本実施形態においては、通信オーバヘッド時間やデータ転送速度は、演算資源監視部１１が実測によって測定しているが、各演算装置が有するＯＳや使用機器毎にあらかじめ定められた値を用いても良い。これは、通信状況が安定しているときには、測定を省くことができるため効率的になるという利点がある。
【００７７】
（システム構成の変形例）
本実施形態において基地局１は１つであり、車両Ａ，Ｂ，Ｃは基地局１の通信可能エリア内に存在したが、図６に示すように複数の基地局１ａ，１ｂ，１ｃが存在しそれらがネットワークを介して存在するようなシステム構成であっても構わない。
【００７８】
このように複数の基地局がそれぞれネットワークで接続されることで、基地局の通信可能エリアを実質的に拡げたことになり、広範囲に及ぶシステムを構築することができる。
【００７９】
また、本実施形態においてはシステム内にタスク割当装置２が１つしか存在しなかったが、複数存在しても良い。例えば、図７に示すように基地局がなく各端末が自律的にネットワークを形成するアドホックネットワークにおいては、各端末（車両Ａ，Ｂ，Ｃ）がそれぞれタスク割当装置２ａ，２ｂ，２ｃを有することが好ましい。
【００８０】
車両Ａ，Ｂ，Ｃは車車間通信により、各車両が有する車載端末３ａ，３ｂ，３ｃの演算能力などの情報を互いに通知する。そして、車載端末からタスクを依頼するときは、自車が有するタスク割当装置に対して依頼を行う。
【００８１】
この際、このシステムは車車間通信のみでなく、さらに基地局との間の通信も行うことができ基地局側にタスクの演算を行えるサーバがあることも好ましい。この場合、一般的に車載端末は演算能力は低いが通信コストが低い演算資源であり、サーバは演算能力は高いが通信コストも高い演算資源といえる。したがって、このように多様な演算資源が混在する環境においては、各車両のタスク割当装置がタスクの特性に応じて適切な割当先を決定することの重要性が高まる。
【図面の簡単な説明】
【００８２】
【図１】本実施形態におけるシステム構成を示す概要図である。
【図２】本実施形態におけるタスク割当装置の構成を示す図である。
【図３】本実施形態における演算資源についての情報を記憶したテーブルの例を示す図である。
【図４】本実施形態におけるタスクの割当先を決定する処理を示すフローチャート図である。
【図５】本実施形態における各演算資源の処理能力の算出方法を説明する図である。
【図６】本実施形態におけるシステム構成を示す概要図である。
【図７】本実施形態におけるシステム構成を示す概要図である。
【符号の説明】
【００８３】
Ａ，Ｂ，Ｃ 車両
Ｄ，Ｅ サーバ
１ 基地局
２，２ａ，２ｂ，２ｃ タスク割当装置
３ａ，３ｂ，３ｃ 車載端末
１１ 演算資源監視部
１４ 演算資源記憶部
１５ タスク管理部
１６ タスク情報取得部
１７ タスク割当先決定部
【特許請求の範囲】
【請求項１】
複数の情報処理装置が通信ネットワークで接続された分散処理システムにおいて、タスクを前記情報処理装置に割当てるタスク割当装置であって、
前記複数の情報処理装置の演算能力、通信オーバヘッド時間およびデータ転送速度を記憶する演算資源記憶手段と、
依頼されたタスクの実行に必要な演算量および該タスクを前記情報処理装置に割当てたときに発生する転送データ量を取得するタスク情報取得手段と、
前記演算資源記憶手段に記憶された前記情報処理装置に関する情報と、前記タスク情報取得手段によって取得された前記タスクの演算量および転送データ量とに基づいて、前記タスクを割当てる情報処理装置を決定するタスク割当先決定手段と、
を有するタスク割当装置。
【請求項２】
前記タスク割当先決定手段は、前記情報処理装置の前記演算能力、前記通信オーバヘッド時間および前記データ転送速度と、前記タスクの前記演算量および前記転送データ量とを変数とする評価関数によって各情報処理装置のタスク処理能力を評価し、該タスク処理能力に基づいて前記タスクを割当てる情報処理装置を決定する
ことを特徴とする請求項１に記載のタスク割当装置。
【請求項３】
前記タスク割当先決定手段は、前記演算能力および前記演算量から演算時間を推定し、前記通信オーバヘッド時間、前記データ転送速度および前記転送データ量から通信時間を推定し、演算時間と通信時間の和を前記タスク処理能力とする評価関数を用いる
ことを特徴とする請求項２に記載のタスク割当装置。
【請求項４】
前記タスク割当先決定手段は、タスクの前記演算量および前記転送データ量のうちどちらがタスクの処理結果を得るまでの時間に与える影響が大きいか判断し、前記演算量が与える影響度が大きいと判断したときは、前記演算能力の重み付けを大きくした評価関数を用い、前記転送データ量が与える影響度が大きいと判断したときは、前記通信オーバヘッド時間および前記データ転送速度の重み付けを大きくした評価関数を用いる
ことを特徴とする請求項２に記載のタスク割当装置。
【請求項５】
前記通信ネットワークは無線通信ネットワークである
ことを特徴とする請求項１〜４のいずれかに記載のタスク割当装置。
【請求項６】
前記情報処理装置と通信する際の通信オーバヘッド時間およびデータ転送速度を定期的に測定し、前記演算資源記憶手段に記憶されている通信オーバヘッド時間およびデータ転送速度を更新する演算資源監視手段を有する
ことを特徴とする請求項１〜５のいずれかに記載のタスク割当装置。
【請求項７】
タスクには、それぞれ優先度が付されており、
前記演算資源記憶手段は、前記情報処理装置にすでに割当てられているタスクの優先度を記憶し、
前記タスク割当先決定手段は、依頼されたタスクを割当てる情報処理装置を決定する際に、依頼されたタスクの優先度と、前記情報処理装置にすでに割当てられているタスクの優先度とを考慮する
ことを特徴とする請求項１〜６のいずれかに記載のタスク割当装置。
【請求項８】
複数の情報処理装置が通信ネットワークで接続された分散処理システムにおいて、タスクを前記情報処理装置に割当てるタスク割当方法であって、
前記複数の情報処理装置の演算能力、通信オーバヘッド時間およびデータ転送速度を記
憶する演算資源記憶手段を有するタスク割当装置が、
依頼されたタスクの実行に必要な演算量および該タスクを前記情報処理装置に割当てたときに発生する転送データ量を取得するステップと、
前記演算資源記憶手段に記憶された前記情報処理装置に関する情報と、前記取得するステップにおいて取得された前記タスクの前記演算量および前記転送データ量とに基づいて、前記タスクを割当てる情報処理装置を決定するステップと、
を含むタスク割当方法。
【請求項１】
複数の情報処理装置が通信ネットワークで接続された分散処理システムにおいて、タスクを前記情報処理装置に割当てるタスク割当装置であって、
前記複数の情報処理装置の演算能力、通信オーバヘッド時間およびデータ転送速度を記憶する演算資源記憶手段と、
依頼されたタスクの実行に必要な演算量および該タスクを前記情報処理装置に割当てたときに発生する転送データ量を取得するタスク情報取得手段と、
前記演算資源記憶手段に記憶された前記情報処理装置に関する情報と、前記タスク情報取得手段によって取得された前記タスクの演算量および転送データ量とに基づいて、前記タスクを割当てる情報処理装置を決定するタスク割当先決定手段と、
を有するタスク割当装置。
【請求項２】
前記タスク割当先決定手段は、前記情報処理装置の前記演算能力、前記通信オーバヘッド時間および前記データ転送速度と、前記タスクの前記演算量および前記転送データ量とを変数とする評価関数によって各情報処理装置のタスク処理能力を評価し、該タスク処理能力に基づいて前記タスクを割当てる情報処理装置を決定する
ことを特徴とする請求項１に記載のタスク割当装置。
【請求項３】
前記タスク割当先決定手段は、前記演算能力および前記演算量から演算時間を推定し、前記通信オーバヘッド時間、前記データ転送速度および前記転送データ量から通信時間を推定し、演算時間と通信時間の和を前記タスク処理能力とする評価関数を用いる
ことを特徴とする請求項２に記載のタスク割当装置。
【請求項４】
前記タスク割当先決定手段は、タスクの前記演算量および前記転送データ量のうちどちらがタスクの処理結果を得るまでの時間に与える影響が大きいか判断し、前記演算量が与える影響度が大きいと判断したときは、前記演算能力の重み付けを大きくした評価関数を用い、前記転送データ量が与える影響度が大きいと判断したときは、前記通信オーバヘッド時間および前記データ転送速度の重み付けを大きくした評価関数を用いる
ことを特徴とする請求項２に記載のタスク割当装置。
【請求項５】
前記通信ネットワークは無線通信ネットワークである
ことを特徴とする請求項１〜４のいずれかに記載のタスク割当装置。
【請求項６】
前記情報処理装置と通信する際の通信オーバヘッド時間およびデータ転送速度を定期的に測定し、前記演算資源記憶手段に記憶されている通信オーバヘッド時間およびデータ転送速度を更新する演算資源監視手段を有する
ことを特徴とする請求項１〜５のいずれかに記載のタスク割当装置。
【請求項７】
タスクには、それぞれ優先度が付されており、
前記演算資源記憶手段は、前記情報処理装置にすでに割当てられているタスクの優先度を記憶し、
前記タスク割当先決定手段は、依頼されたタスクを割当てる情報処理装置を決定する際に、依頼されたタスクの優先度と、前記情報処理装置にすでに割当てられているタスクの優先度とを考慮する
ことを特徴とする請求項１〜６のいずれかに記載のタスク割当装置。
【請求項８】
複数の情報処理装置が通信ネットワークで接続された分散処理システムにおいて、タスクを前記情報処理装置に割当てるタスク割当方法であって、
前記複数の情報処理装置の演算能力、通信オーバヘッド時間およびデータ転送速度を記
憶する演算資源記憶手段を有するタスク割当装置が、
依頼されたタスクの実行に必要な演算量および該タスクを前記情報処理装置に割当てたときに発生する転送データ量を取得するステップと、
前記演算資源記憶手段に記憶された前記情報処理装置に関する情報と、前記取得するステップにおいて取得された前記タスクの前記演算量および前記転送データ量とに基づいて、前記タスクを割当てる情報処理装置を決定するステップと、
を含むタスク割当方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公開番号】特開２００６−３３８２６４（Ｐ２００６−３３８２６４Ａ）
【公開日】平成１８年１２月１４日（２００６．１２．１４）
【国際特許分類】
【出願番号】特願２００５−１６１３６６（Ｐ２００５−１６１３６６）
【出願日】平成１７年６月１日（２００５．６．１）
【出願人】（５０２０８７４６０）株式会社トヨタＩＴ開発センター (232)
【出願人】（０００００３２０７）トヨタ自動車株式会社 (59,920)
【Ｆターム（参考）】
【公開日】平成１８年１２月１４日（２００６．１２．１４）
【国際特許分類】
【出願日】平成１７年６月１日（２００５．６．１）
【出願人】（５０２０８７４６０）株式会社トヨタＩＴ開発センター (232)
【出願人】（０００００３２０７）トヨタ自動車株式会社 (59,920)
【Ｆターム（参考）】
[ Back to top ]