(57)【特許請求の範囲】
【請求項１】
タスクの実行が可能な複数のデータ処理装置を管理する管理装置であって、
データを取得するデータ取得部と、
前記データ取得部による前記データの取得前に生成されていたタスクである先行タスクが存在する場合に、前記先行タスクを前記複数のデータ処理装置のうちのいずれかのデータ処理装置に割り当て、前記先行タスクの割当て後に、前記データから複数のタスクを複数の通常タスクとして生成し、前記複数のデータ処理装置のうち、前記先行タスクを割り当てたデータ処理装置以外のデータ処理装置である通常データ処理装置間の処理量が均等になるように、前記通常データ処理装置に前記複数の通常タスクを割り当てるタスク割当て部とを有する管理装置。
【請求項２】
前記タスク割当て部は、
前記通常データ処理装置間の通常タスクの割当て数が均等になるように、前記通常データ処理装置に前記複数の通常タスクを割り当てる請求項１に記載の管理装置。
【請求項３】
前記管理装置は、更に、
前記通常データ処理装置が前記通常タスクを実行する前に、前記通常タスクの前処理を実行する前処理実行部を有する請求項１に記載の管理装置。
【請求項４】
前記管理装置は、更に、
前記通常データ処理装置による前記通常タスクの実行が完了した後に後処理を実行する後処理実行部を有する請求項１に記載の管理装置。
【請求項５】
タスクの実行が可能な複数のデータ処理装置を管理するコンピュータが行う管理方法であって、
前記コンピュータが、データを取得し、
前記データの取得前に生成されていたタスクである先行タスクが存在する場合に、前記コンピュータが、前記先行タスクを前記複数のデータ処理装置のうちのいずれかのデータ処理装置に割り当て、前記先行タスクの割当て後に、前記データから複数のタスクを複数の通常タスクとして生成し、前記複数のデータ処理装置のうち、前記先行タスクを割り当てたデータ処理装置以外のデータ処理装置である通常データ処理装置間の処理量が均等になるように、前記通常データ処理装置に前記複数の通常タスクを割り当てる管理方法。
【請求項６】
タスクの実行が可能な複数のデータ処理装置を管理するコンピュータに、
データを取得するデータ取得処理と、
前記データ取得処理による前記データの取得前に生成されていたタスクである先行タスクが存在する場合に、前記先行タスクを前記複数のデータ処理装置のうちのいずれかのデータ処理装置に割り当て、前記先行タスクの割当て後に、前記データから複数のタスクを複数の通常タスクとして生成し、前記複数のデータ処理装置のうち、前記先行タスクを割り当てたデータ処理装置以外のデータ処理装置である通常データ処理装置間の処理量が均等になるように、前記通常データ処理装置に前記複数の通常タスクを割り当てるタスク割当て処理とを実行させる管理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、管理装置、管理方法及び管理プログラムに関する。
【背景技術】
【０００２】
特許文献１の技術では、通常のジョブキューに加えて、特急ジョブキュー又は仮想ジョブキューを備えることで、特定のジョブの即時実行を実現している。なお、特急ジョブキューは特定のジョブを即時に起動するためのジョブキューである。また、仮想ジョブキューは即時に起動したいジョブの先頭ポインタを格納するジョブキューである。【０００３】
特許文献２の技術では、複数のコネクションを用いた高速かつ信頼性の高いファイル伝送が実現されている。具体的には、特許文献２では、あるコネクションにおいてデータパックの伝送にエラーが発生した場合に、エラーが発生したデータパックがリトライキューにエンキューされる。そして、特許文献２では、リトライキューのデータパックが優先的に伝送される。これにより、特許文献２では、高速かつ信頼性の高いファイル伝送が実現されている。【０００４】
非特許文献２の技術では、通常のジョブをエンキューするａｃｔｉｖｅキューと、タイムアウトが発生したジョブをエンキューするｅｘｐｉｒｅｄキューが用いられる。また、非特許文献２の技術では、ａｃｔｉｖｅキューのジョブがなくなったらｅｘｐｉｒｅｄキューのジョブが処理される。これにより、非特許文献２の技術では、ジョブの優先度に限らず、全てのジョブが必ず処理されることが保証される。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開平１１−１１０２３７号公報
【特許文献２】特開２００１−２４７３３号公報
【非特許文献】
【０００６】
【非特許文献１】Ｍｏｒｒｉｓ  Ｄｗｏｒｋｉｎ，  “Ｒｅｃｏｍｍｅｎｄａｔｉｏｎ  ｆｏｒ  Ｂｌｏｃｋ  Ｃｉｐｈｅｒ  Ｍｏｄｅｓ  ｏｆ  Ｏｐｅｒａｔｉｏｎ：  Ｇａｌｏｉｓ／Ｃｏｕｎｔｅｒ  Ｍｏｄｅ  （ＧＣＭ）  ａｎｄ  ＧＭＡＣ”，  ＮＩＳＴ  ＳＰ．８００−３８Ｄ，  Ｎｏｖ．  ２００７．  ｈｔｔｐ：／／ｎｖｌｐｕｂｓ．ｎｉｓｔ．ｇｏｖ／ｎｉｓｔｐｕｂｓ／Ｌｅｇａｃｙ／ＳＰ／ｎｉｓｔｓｐｅｃｉａｌｐｕｂｌｉｃａｔｉｏｎ８００−３８Ｄ．ｐｄｆ
【非特許文献２】Ｊｏｓｈ  Ａａｓ，  “Ｕｎｄｅｒｓｔａｎｄｉｎｇ  ｔｈｅ  Ｌｉｎｕｘ（登録商標）  ２．６．８．１  ＣＰＵ  Ｓｃｈｅｄｕｌｅｒ”，  Ｆｅｂ．  １７，  ２００５．  ｈｔｔｐ：／／ｗｗｗ．ｉｎｆ．ｅｄ．ａｃ．ｕｋ／ｔｅａｃｈｉｎｇ／ｃｏｕｒｓｅｓ／ｏｓ／ｃｏｕｒｓｅｗｏｒｋ／ｌｃｐｕｓｃｈｅｄ−ｆｕｌｌｐａｇｅ−２ｘ１．ｐｄｆ
【発明の概要】
【発明が解決しようとする課題】
【０００７】
大容量リアルタイム通信システムにおいて、随時入力される平文データの暗号化（あるいは暗号文データの復号、以下、両者をまとめて暗号化という）及び改ざん防止用のメッセージ認証子（ＭＡＣ）の生成（あるいはＭＡＣの検証、以下、両者をまとめてＭＡＣ生成という）を高速に処理することを考える。より具体的には、暗号化及びＭＡＣ生成を、複数の計算機によるクラスタ構成により高速に処理することを考える。また、暗号化及びＭＡＣ生成は、予め設定されたサイズの単位で実施するものとする。
この場合、随時入力される平文データに対して、暗号化とＭＡＣ生成をリアルタイムで実施する必要があるが、非特許文献２のジョブ管理手法では、ａｃｔｉｖｅキューのあるジョブの処理にエラーが発生すると、このジョブはｅｘｐｉｒｅｄキューへ格納される。そして、ａｃｔｉｖｅキューのジョブがなくなるまでｅｘｐｉｒｅｄキューのジョブは処理されない。このため、非特許文献２の技術では、入力される平文の順序に合わせた暗号化及びＭＡＣ生成ができない。このように、非特許文献２の技術では、先に処理すべきジョブ（ｅｘｐｉｒｅｄキューのジョブ）が先に処理されないという課題がある。【０００８】
特許文献２では、既定のデータサイズのデータパックを単位としてデータ処理が行われる。このため、特許文献２によれば、複数のデータ処理装置が存在する場合にもタスクの割当てはデータパック単位であるため、予め設定されたサイズの処理単位をデータ処理装置の数に応じてタスク分割を行う場合、一部のデータ処理装置に偏ってタスクが割り当てられる。従って、特許文献２の技術では、データ処理装置間で有効に負荷を分散することができないという課題がある。【０００９】
本発明は、このような課題を解決することを主な目的とする。より具体的には、先行するタスクの割当てを優先して行うことができ、また、データ処理装置間で有効に負荷分散を行うことができる構成を得ることを主な目的とする。
【課題を解決するための手段】
【００１０】
本発明に係る管理装置は、
タスクの実行が可能な複数のデータ処理装置を管理する管理装置であって、
データを取得するデータ取得部と、
前記データ取得部による前記データの取得前に生成されていたタスクである先行タスクが存在する場合に、前記先行タスクを前記複数のデータ処理装置のうちのいずれかのデータ処理装置に割り当て、前記先行タスクの割当て後に、前記データから複数のタスクを複数の通常タスクとして生成し、前記複数のデータ処理装置のうち、前記先行タスクを割り当てたデータ処理装置以外のデータ処理装置である通常データ処理装置間の処理量が均等になるように、前記通常データ処理装置に前記複数の通常タスクを割り当てるタスク割当て部とを有する。
【発明の効果】
【００１１】
本発明によれば、先行するタスクの割当てを優先して行うことができ、また、データ処理装置間で有効に負荷分散を行うことができる。
【図面の簡単な説明】
【００１２】
【図１】実施の形態１に係るデータ処理システムの構成例を示す図。
【図２】実施の形態１に係る管理ノードのハードウェア構成例を示す図。
【図３】実施の形態１に係る子ノードのハードウェア構成例を示す図。
【図４】実施の形態１に係る管理ノード及び子ノードの機能構成例を示す図。
【図５】実施の形態１に係る管理ノードの動作例を示すフローチャート。
【図６】実施の形態１に係る管理ノードの動作例を示すフローチャート。
【図７】実施の形態２に係る管理ノード及び子ノードの機能構成例を示す図。
【図８】実施の形態２に係る管理ノードの動作例を示すフローチャート。
【図９】実施の形態３に係る管理ノード及び子ノードの機能構成例を示す図。
【図１０】実施の形態３に係る管理ノードの動作例を示すフローチャート。
【図１１】実施の形態３に係るＭＡＣ１の生成手順を示す図。
【図１２】実施の形態３に係るＭＡＣ２の生成手順を示す図。
【図１３】実施の形態３に係る並列処理可能な暗号化の例を示す図。
【発明を実施するための形態】
【００１３】
以下、本発明の実施の形態について、図を用いて説明する。以下の実施の形態の説明及び図面において、同一の符号を付したものは、同一の部分又は相当する部分を示す。
【００１４】
実施の形態１．
＊＊＊構成の説明＊＊＊
図１は、実施の形態１に係るデータ処理システムの構成例を示す。実施の形態１に係るデータ処理システムは、管理ノード１０及び子ノード２１〜２ｎにより構成される。
管理ノード１０は管理装置に相当する。また、管理ノード１０で行われる処理は管理方法及び管理プログラムに相当する。
子ノード２１〜２ｎは、それぞれデータ処理装置に相当する。
なお、子ノード２１〜２ｎを区別する必要がない場合は、子ノード２１〜２ｎをまとめて子ノード２０と表記する。
【００１５】
管理ノード１０は、タスクスケジューラ１１、能動キュー１２及び失効キュー１３を備える。
タスクスケジューラ１１は、データを取得し、取得したデータから複数のタスクを生成する。そして、タスクスケジューラ１１は、タスクを能動キュー１２又は失効キュー１３にエンキューする。
能動キュー１２には、子ノード２０が新規に演算するタスクが格納される。失効キュー１３には、タイムアウト等で演算に失敗したタスクが格納される。
能動キュー１２に格納されたタスク及び失効キュー１３に格納されたタスクは、各子ノード２０に配信される。各子ノード２０は、タスクを受信し、受信したタスクを実行する。また、各子ノード２０は、タスクの演算結果を、管理ノード１０に送信する。管理ノード１０は、各子ノード２０からの演算結果を統合する。
【００１６】
図２は、管理ノード１０のハードウェア構成例を示す。
【００１７】
本実施の形態に係る管理ノード１０は、コンピュータである。
図２に示すとおり、管理ノード１０はプロセッサ１０１、記憶装置１０２及びネットワークインタフェース１０３を備える。
記憶装置１０２には、後述する平文取得部３１１、ノード管理部３１２、タスクスケジューラ３１３、タスク配信部３１４及び演算結果出力部３１５の機能を実現するプログラムが記憶されている。
そして、プロセッサ１０１がこれらプログラムを実行して、後述する平文取得部３１１、ノード管理部３１２、タスクスケジューラ３１３、タスク配信部３１４及び演算結果出力部３１５の動作を行う。
図２では、プロセッサ１０１が平文取得部３１１、ノード管理部３１２、タスクスケジューラ３１３、タスク配信部３１４及び演算結果出力部３１５の機能を実現するプログラムを実行している状態を模式的に表している。
ネットワークインタフェース１０３は、子ノード２０と接続されたネットワークとのインタフェースである。
【００１８】
図３は、子ノード２０のハードウェア構成例を示す。
【００１９】
本実施の形態に係る子ノード２０は、コンピュータである。
図３に示すとおり、子ノード２０はプロセッサ２０１、記憶装置２０２及びネットワークインタフェース２０３を備える。
記憶装置２０２には、後述するタスク取得部４１１、タスク演算部４１２及び演算結果送信部４１３の機能を実現するプログラムが記憶されている。
そして、プロセッサ２０１がこれらプログラムを実行して、後述するタスク取得部４１１、タスク演算部４１２及び演算結果送信部４１３の動作を行う。
図３では、プロセッサ２０１がタスク取得部４１１、タスク演算部４１２及び演算結果送信部４１３の機能を実現するプログラムを実行している状態を模式的に表している。
ネットワークインタフェース２０３は、管理ノード１０と接続されたネットワークとのインタフェースである。
【００２０】
図４は、管理ノード１０の機能構成例と子ノード２０の機能構成例を示す。
【００２１】
管理ノード１０において、平文取得部３１１は、子ノード２０に処理させる平文データを取得する。平文取得部３１１は、データ取得部に相当する。また、平文取得部３１１が行う処理はデータ取得処理に相当する。
【００２２】
ノード管理部３１２は、子ノード２０の死活状態を管理する。
また、ノード管理部３１２は、正常に動作している子ノード２０のうちタスクを実行中の子ノード２０とタスクを実行していない子ノード２０とを識別する。
正常に活動している子ノード２０のうち、タスクを実行していない子ノード２０は、以下、タスク待ち子ノードという。
【００２３】
タスクスケジューラ３１３は、図１に示すタスクスケジューラ１１である。
タスクスケジューラ３１３は、平文取得部３１１により取得された平文データのタスクの生成前に、失効キュー１３にタスクがあるか否かを判定する。失効キュー１３にあるタスクは、平文取得部３１１により取得された平文データのタスクに先行するタスクである。失効キュー１３にあるタスクは先行タスクに相当する。
また、タスクスケジューラ３１３は、平文取得部３１１により取得された平文データのタスクの生成前に、能動キュー１２にタスクがあるか否かを判定する。能動キュー１２にあるタスクは、平文取得部３１１により取得された平文データのタスクに先行するタスクである。能動キュー１２にあるタスクも先行タスクに相当する。
能動キュー１２及び失効キュー１３に先行タスクがない場合に、タスクスケジューラ３１３は、タスク待ち子ノードに割り当てるタスクを、平文取得部３１１により取得された平文データから生成する。
能動キュー１２及び失効キュー１３に先行タスクがない場合にタスクスケジューラ３１３により生成されるタスクを以下、通常タスクという。タスクスケジューラ３１３は、平文データから複数の通常タスクを生成する。また、タスクスケジューラ３１３は、生成した複数の通常タスクを能動キュー１２にエンキューする。
通常タスクが生成された時点でのタスク待ち子ノード、つまり、先行タスクが割り当てられていない子ノードは、通常データ処理装置に相当する。
タスクスケジューラ３１３は、後述するタスク配信部３１４とともにタスク割当て部に相当する。また、タスクスケジューラ３１３がタスク配信部３１４とともに行う処理はタスク割当て処理に相当する。
【００２４】
能動キュー１２又は失効キュー１３に先行タスクがある場合に、タスク配信部３１４は、能動キュー１２又は失効キュー１３から先行タスクを読み出し、読み出した先行タスクをいずれかの子ノード２０に割り当てる。つまり、タスク配信部３１４は、先行タスクをいずれかの子ノード２０に送信する。
また、タスク配信部３１４は、タスクスケジューラ３１３によりタスク待ち子ノード間の処理量が均等になるように生成された通常タスクをタスク待ち子ノードに割り当てる。
より具体的には、タスク配信部３１４は、能動キュー１２から通常タスクを読み出し、タスク待ち子ノード間の通常タスクの割当て数が均等となるように、読み出した通常タスクを各タスク待ち子ノードに配信する。
なお、「均等」には誤差が含まれていてもよい。つまり、タスク待ち子ノード間の通常タスクの処理量（割当て数）が完全に一致していなくてもよい。タスク分割は後述の式（１）により実施する。
例えば、３個のタスク待ち子ノードが存在する例を想定する。この例において、タスクスケジューラ３１３は、新たに入力された平文データを後述の式（１）に従い３等分する。そして、タスク配信部３１４が、３個のタスクを３個のタスク待ち子ノードへ配信する。実際の暗号化及びＭＡＣ生成にかかる処理は、（タスクサイズよりも小さな）暗号アルゴリズムの演算処理単位（１２８ビット等）で逐次的に行われる。このため、実際の暗号化及びＭＡＣ生成にかかる処理では、この演算処理単位の集合が各タスクとなる。
タスク配信部３１４は、前述したように、タスクスケジューラ３１３とともにタスク割当て部に相当する。また、タスク配信部３１４がタスクスケジューラ３１３とともに行う処理はタスク割当て処理に相当する。
【００２５】
演算結果出力部３１５は、各子ノード２０から、タスクの演算結果を受信し、受信した演算結果を統合する。そして、演算結果出力部３１５は、統合した演算結果を既定の出力先に出力する。例えば、演算結果出力部３１５は、各子ノード２０から演算結果として部分暗号化データを受信し、受信した部分暗号化データを統合する。そして、演算結果出力部３１５は、部分暗号化データの統合により得られた暗号化データを出力先に出力する。
【００２６】
子ノード２０において、タスク取得部４１１は、タスクを取得する。
タスク演算部４１２は、タスク取得部４１１により取得されたタスクの演算を行う。
演算結果送信部４１３は、タスク演算部４１２によるタスクの演算結果を管理ノード１０に送信する。
【００２７】
＊＊＊動作の説明＊＊＊
図５及び図６は、本実施の形態に係る管理ノード１０の動作例を示す。
【００２８】
ステップＳ１０１において平文取得部３１１が平文データを取得すると、ノード管理部３１２がｐｉｎｇ等のＩＣＭＰ（Ｉｎｔｅｒｎｅｔ  Ｃｏｎｔｒｏｌ  Ｍｅｓｓａｇｅ  Ｐｒｏｔｏｃｏｌ）コマンドを各子ノード２０へ送信し、各子ノード２０の死活状態をチェックする（ステップＳ１０２）。
ノード管理部３１２は、ＩＣＭＰコマンドに応答した子ノード２０は正常に動作していると判定する。一方、ノード管理部３１２は、ＩＣＭＰコマンドに応答しない子ノード２０は正常に動作していない、あるいはネットワークに接続されていないと判定する。
【００２９】
次に、ノード管理部３１２は、タスク待ち子ノードがあるか否かを判定する（ステップＳ１０３）。
初期状態、すなわちタスク配信部３１４によりいずれの子ノード２０にもタスクが配信されていない状態では、ノード管理部３１２は、管理ノード１０に接続されている全ての子ノード２０はタスク待ち子ノードであると判定する。
また、ノード管理部３１２は、後述するステップＳ１０７においてタスク配信部３１４によりタスクを配信された子ノード２０はタスクを実行中の子ノードであると判定する。演算結果出力部３１５が子ノード２０からタスクの演算結果を受信すると、ノード管理部３１２は、当該子ノード２０をタスク待ち子ノードであると判定する。
【００３０】
タスク待ち子ノードがある場合（ステップＳ１０３でＹＥＳ）に、タスクスケジューラ３１３が、失効キュー１３にタスクがあるか否かを判定する（ステップＳ１０４）。より具体的には、タスクスケジューラ３１３は、失効キュー１３の先頭タスクと最後尾タスクのポインタ値を比較する。そして、先頭タスクと最後尾タスクのポインタ値が同じであれば失効キュー１３にタスクはないと判定する。一方、先頭タスクと最後尾タスクのポインタ値が異なれば失効キュー１３にタスクがあると判定する。
【００３１】
次に、ステップＳ１０４において失効キュー１３にタスクがあると判定した場合に、タスクスケジューラ３１３はタスク配信部３１４に失効キュー１３のタスクの配信を指示する。
そして、タスク配信部３１４は、失効キュー１３の先頭のタスクから順に各タスクをタスク待ち子ノードに配信する（ステップＳ１０５）。
【００３２】
一方、ステップＳ１０４において失効キュー１３にタスクがないと判定した場合は、タスクスケジューラ３１３は、能動キュー１２にタスクがあるか否かを判定する（ステップＳ１０６）。
【００３３】
能動キュー１２にタスクがあると判定した場合は、タスクスケジューラ３１３はタスク配信部３１４に能動キュー１２のタスクの配信を指示する。そして、タスク配信部３１４は、能動キュー１２の先頭のタスクから順に各タスクをタスク待ち子ノードに配信する（ステップＳ１０７）。
【００３４】
能動キュー１２にタスクがないと判定した場合は、タスクスケジューラ３１３は、平文データを分割してタスクを生成する（ステップＳ１０８）。
次に、タスクスケジューラ３１３は、生成した各タスクを能動キュー１２へエンキューする（ステップＳ１０９）。また、タスクスケジューラ３１３は、タスク配信部３１４に能動キュー１２のタスクの配信を指示する。そして、タスク配信部３１４は、能動キュー１２の先頭のタスクから順に各タスクをタスク待ち子ノードに配信する（ステップＳ１０７）。
【００３５】
その後、管理ノード１０は、以降に取得する平文データにも同様の処理を繰り返す。
各子ノード２０は、タスクの演算が終了したら、管理ノード１０へ演算結果を送信する。その後、各子ノード２０は、タスク待ち状態へ遷移する。
管理ノード１０では、演算結果出力部３１５が、各子ノード２０から演算結果を受信し、受信した演算結果を統合する。そして、演算結果出力部３１５は、統合により得られた演算結果を出力先に出力する。
【００３６】
上記のステップＳ１０８、Ｓ１０９及びＳ１０７では、タスクスケジューラ３１３がタスク待ち子ノード間の処理量が均等になるように複数の通常タスクを生成し、タスク配信部３１４が通常タスクをタスク待ち子ノードに割り当てる。
例えば、平文データのサイズがｍｌｅｎであり、暗号化及びＭＡＣ生成の演算処理単位のサイズがｃａｌｃｓｉｚｅであると仮定する。この場合、暗号化及びＭＡＣ生成の演算処理単位の総数は（ｍｌｅｎ／ｃａｌｃｓｉｚｅ）個であり、タスク待ち子ノードの個数がｍである場合は、タスクスケジューラ３１３は式（１）により平文データをｍ個の通常タスクに分割する。タスク配信部３１４は、各タスク待ち子ノードｔｉ（１≦ｉ≦ｍ）に以下の数の演算処理単位ｃａｌｃｎｕｍ（ｔｉ）を割り当てる。
ｃａｌｃｎｕｍ（ｔｉ）＝［（ｍｌｅｎ／ｃａｌｃｓｉｚｅ＋ｉ−１）／ｍ］    式（１）
なお、式（１）において、フロア関数［ｘ］はｘの切り捨てを意味する。
例えば、ｍｌｅｎ＝１２８０、ｃａｌｃｓｉｚｅ＝１２８、ｍ＝４、１≦ｉ≦ｍの例を想定する。この例では、演算処理単位の総数は１２８０／１２８＝１０となる。このとき、式（１）により得られた、タスク待ち子ノードごとの演算処理単位はそれぞれ以下となる。なお、ｔ１〜ｔ４は、それぞれタスク待ち子ノードを意味する。ｔ１はｉ＝１のタスク待ち子ノードである。ｔ２はｉ＝２のタスク待ち子ノードである。ｔ３はｉ＝３のタスク待ち子ノードである。ｔ４はｉ＝４のタスク待ち子ノードである。
ｔ１：［（１２８０／１２８＋１−１）／４］＝２
ｔ２：［（１２８０／１２８＋２−１）／４］＝２
ｔ３：［（１２８０／１２８＋３−１）／４］＝３
ｔ４：［（１２８０／１２８＋４−１）／４］＝３
【００３７】
＊＊＊実施の形態の効果の説明＊＊＊
以上、本実施の形態では、管理ノード１０は、先行タスクを通常タスクに先行して子ノード２０に割り当てる。また、本実施の形態では、管理ノード１０は、子ノード２０間での処理量が均等になるように通常タスクを子ノード２０に割り当てる。
このため、本実施の形態によれば、先行するタスクの割当てを優先して行うことができ、また、子ノード２０間で有効に負荷分散を行うことができる。
【００３８】
実施の形態２．
＊＊＊構成の説明＊＊＊
本実施の形態に係るデータ処理システムの構成例は、図１に示すとおりである。
また、本実施の形態に係る管理ノード１０のハードウェア構成例は、図２に示すとおりである。
また、本実施の形態に係る子ノード２０のハードウェア構成例は、図３に示すとおりである。
【００３９】
図７は、本実施の形態に係る管理ノード１０と子ノード２０の機能構成例を示す。
図４と比較して、図７では、前処理実行部３２１が追加されている。
前処理実行部３２１は、タスク待ち子ノードが通常タスクを実行する前に、通常タスクの前処理を実行する。
つまり、前処理実行部３２１により前処理が実行された後の通常タスクがタスク配信部３１４によりタスク待ち子ノードに配信される。
なお、前処理実行部３２１も、平文取得部３１１、ノード管理部３１２、タスクスケジューラ３１３、タスク配信部３１４及び演算結果出力部３１５と同様にプログラムで実現される。
図７において、前処理実行部３２１以外の要素は、図４に示したものと同じであるため、説明を省略する。
【００４０】
＊＊＊動作の説明＊＊＊
図８は、本実施の形態に係る管理ノード１０の動作例を示す。
図８は、図６に対応する。つまり、図５に示すステップＳ１０４でＮＯと判定された場合に、図８のステップＳ１０６が行われる。
ステップＳ１０６において能動キュー１２にタスクがないと判定された場合に、図６と同様に、タスクスケジューラ３１３は平文データから通常タスクを生成する（ステップＳ１０８）。
ステップＳ２０１では、前処理実行部３２１が、ステップＳ１０８で生成された通常タスクに前処理を実行する。なお、前処理は、タスク待ち子ノード２０の通常タスクの実行に先行して行われる処理であれば、どのような処理でもよい。
そして、ステップＳ１０９では、タスクスケジューラ３１３が、前処理が実行された後の通常タスクを能動キュー１２にエンキューする。
そして、ステップＳ１０７において、タスク配信部３１４が、前処理が実行された後の通常タスクをタスク待ち子ノードに配信する。
【００４１】
＊＊＊実施の形態の効果の説明＊＊＊
本実施の形態によれば、実施の形態１で説明した効果に加えて、前処理を実行した後の通常タスクをタスク待ち子ノードに配信することができる。
【００４２】
実施の形態３．
＊＊＊構成の説明＊＊＊
本実施の形態に係るデータ処理システムの構成例は、図１に示すとおりである。
また、本実施の形態に係る管理ノード１０のハードウェア構成例は、図２に示すとおりである。
また、本実施の形態に係る子ノード２０のハードウェア構成例は、図３に示すとおりである。
【００４３】
図９は、本実施の形態に係る管理ノード１０と子ノード２０の機能構成例を示す。
図７と比較して、図９では、後処理実行部３２２が追加されている。
後処理実行部３２２は、タスク待ち子ノードによる通常タスクの実行が完了した後に後処理を実行する。
つまり、後処理実行部３２２により後処理が実行された後の演算結果が演算結果出力部３１５により統合される。
なお、後処理実行部３２２も、平文取得部３１１、ノード管理部３１２、タスクスケジューラ３１３、タスク配信部３１４、演算結果出力部３１５及び前処理実行部３２１と同様にプログラムで実現される。
図９において、後処理実行部３２２以外の要素は、図７に示したものと同じであるため、説明を省略する。
【００４４】
本実施の形態では、前処理実行部３２１が行う前処理の例として、ＭＡＣ生成アルゴリズムにおける前処理を説明する。また、後処理実行部３２２が行う後処理の例として、ＭＡＣの生成処理を説明する。
【００４５】
図１０は、本実施の形態に係る管理ノード１０の動作例を示す。
図１０は、図６及び図８に対応する。つまり、図５に示すステップＳ１０４でＮＯと判定された場合に、図１０のステップＳ１０６が行われる。
ステップＳ１０６において能動キュー１２にタスクがないと判定された場合に、図６と同様に、タスクスケジューラ３１３は平文データから通常タスクを生成する（ステップＳ１０８）。
ステップＳ２０１では、図８と同様に、前処理実行部３２１が、ステップＳ１０８で生成された通常タスクに前処理を実行する。前処理実行部３２１は、前処理として、例えば、ＭＡＣ生成アルゴリズムにおける前処理を実行する。
そして、ステップＳ１０９では、タスクスケジューラ３１３が、前処理が実行された後の通常タスクを能動キュー１２にエンキューする。
そして、ステップＳ１０７において、タスク配信部３１４が、前処理が実行された後の通常タスクをタスク待ち子ノードに配信する。
ステップＳ３０１では、演算結果出力部３１５が、通常タスクの配信先の子ノード２０から、ＭＡＣの計算に必要な演算結果を受信しているか否かを判定する。
演算結果出力部３１５がＭＡＣの計算に必要な演算結果を受信していると判定した場合（ステップＳ３０１でＹＥＳ）は、後処理実行部３２２が後処理を実行する。具体的には、演算結果出力部３１５が後処理実行部３２２に子ノード２０の演算結果を転送する。そして、後処理実行部３２２が、後処理として、ＭＡＣ演算を実行する（ステップＳ３０２）。後処理実行部３２２は、演算により得られたＭＡＣを演算結果出力部３１５に転送する。そして、演算結果出力部３１５は、統合された演算結果である暗号文データと、後処理実行部３２２から取得したＭＡＣを出力先に出力する（ステップＳ３０２）。
なお、ステップＳ３０１において演算結果出力部３１５がＭＡＣの計算に必要な演算結果を受信していないと判定した場合は（ステップＳ３０１でＮＯ）、処理が図５のステップＳ１０１に戻る。
【００４６】
ステップＳ２０１では、前処理実行部３２１は、前処理として、例えば図１１及び図１２に示すＧａｌｏｉｓ／Ｃｏｕｎｔｅｒ  Ｍｏｄｅ（ＧＣＭ）に代表される並列処理可能なＭＡＣ生成アルゴリズムにおける前処理（符号５１及び符号５３）を実行する。具体的には、前処理実行部３２１は、ＩＶ（ｉｎｉｔｉａｌ  ｖａｌｕｅ）の計算等、並列処理を行う上で必要となる値を算出する。なお、ＧＣＭは、ＮＩＳＴ  ＳＰ８００−３８Ｄにて標準化されている。
また、前処理実行部３２１は、前処理として、図１３に示す暗号化処理のＩＶの計算等、並列処理を行う上で必要となる値を算出してもよい。
【００４７】
また、ステップＳ３０２では、後処理実行部３２２は、後処理として、例えば、図１１の符号５２及び図１２の符号５４に示すように、前処理（符号５１及び符号５３）で算出された値又は並列処理の結果として算出された値を用いた演算を行う。
【００４８】
なお、本実施の形態では、前処理と後処理の両方が実行されることになっているが、後処理のみが実行されるようにしてもよい。
【００４９】
＊＊＊実施の形態の効果の説明＊＊＊
実施の形態１〜３に示したデータ処理システムは、例えば、衛星通信システム等の大容量通信かつリアルタイム性が要求されるシステムに適用可能である。例えば、管理ノードと子ノードを、複数の汎用計算機を用いたクラスタ構成（クライアントサーバモデル）による分散コンピューティングにより実現することができる。そして、ＧＣＭに代表される並列処理可能なＭＡＣ生成アルゴリズムを高速に実行する際に、ネットワーク異常等により一部の子ノードから演算結果が取得できない場合でも、本実施の形態によれば、平文データの入力順序に沿った順序でＭＡＣを生成することができる。
【００５０】
つまり、本実施の形態では、能動キュー１２のタスクに比べて失効キュー１３のタスクが優先的に処理されるため、タイムアウト等で演算に失敗したタスクを失効キュー１３へエンキューすることで、タスクの処理順序を制御可能である。
例えば、図１１及び図１２のように、平文１〜３からＭＡＣ１が生成され、平文４〜６からＭＡＣ２が生成され、ＭＡＣ１及びＭＡＣ２が、ＭＡＣ１、ＭＡＣ２の順で出力されることを考える。図１１及び図１２に示す例では、タスクサイズと、暗号化及びＭＡＣ生成の演算処理単位（のサイズ）が同じである。
能動キュー１２に順にエンキューされたタスク１〜タスク６を分散処理する過程で、タイムアウトによりタスク３の演算が失敗し、タスク３が失効キュー１３へエンキューされたと仮定する。本実施の形態によれば、能動キュー１２にエンキューされたタスク４〜６よりも先に失効キュー１３にエンキューされたタスク３が処理されるため、ＭＡＣ１及びＭＡＣ２が、ＭＡＣ１、ＭＡＣ２の順で出力される。また、本実施の形態では、入力される平文データの順序に従って暗号文データが生成され、出力される。
【００５１】
なお、実施の形態１〜３では、平文データから暗号化データを得る例を説明したが、実施の形態１〜３で示した手順を用いて、暗号化データから平文データを得るようにしてもよい。
また、実施の形態１〜３で示した手順を、暗号化又は復号以外のデータ処理に用いてもよい。
【００５２】
以上、本発明の実施の形態について説明したが、これらの実施の形態のうち、２つ以上を組み合わせて実施しても構わない。
あるいは、これらの実施の形態のうち、１つを部分的に実施しても構わない。
あるいは、これらの実施の形態のうち、２つ以上を部分的に組み合わせて実施しても構わない。
なお、本発明は、これらの実施の形態に限定されるものではなく、必要に応じて種々の変更が可能である。
【００５３】
＊＊＊ハードウェア構成の説明＊＊＊
最後に、管理ノード１０と子ノード２０のハードウェア構成の補足説明を行う。
プロセッサ１０１及びプロセッサ２０１は、それぞれ、プロセッシングを行うＩＣ（Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）である。
プロセッサ１０１及びプロセッサ２０１は、それぞれ、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）、ＤＳＰ（Ｄｉｇｉｔａｌ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｏｒ）等である。
記憶装置１０２及び記憶装置２０２は、それぞれ、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、フラッシュメモリ、ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）等である。
ネットワークインタフェース１０３及びネットワークインタフェース２０３は、それぞれ、データを受信するレシーバー及びデータを送信するトランスミッターを含む。
ネットワークインタフェース１０３及びネットワークインタフェース２０３は、それぞれ、例えば、通信チップ又はＮＩＣ（Ｎｅｔｗｏｒｋ  Ｉｎｔｅｒｆａｃｅ  Ｃａｒｄ）である。
【００５４】
また、記憶装置１０２には、ＯＳ（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ）も記憶されている。
そして、ＯＳの少なくとも一部がプロセッサ１０１により実行される。
プロセッサ１０１はＯＳの少なくとも一部を実行しながら、平文取得部３１１、ノード管理部３１２、タスクスケジューラ３１３、タスク配信部３１４、演算結果出力部３１５、前処理実行部３２１及び後処理実行部３２２の機能を実現するプログラムを実行する。
プロセッサ１０１がＯＳを実行することで、タスク管理、メモリ管理、ファイル管理、通信制御等が行われる。
また、平文取得部３１１、ノード管理部３１２、タスクスケジューラ３１３、タスク配信部３１４、演算結果出力部３１５、前処理実行部３２１及び後処理実行部３２２の処理の結果を示す情報、データ、信号値及び変数値の少なくともいずれかが、記憶装置１０２、プロセッサ１０１内のレジスタ及びキャッシュメモリの少なくともいずれかに記憶される。
また、平文取得部３１１、ノード管理部３１２、タスクスケジューラ３１３、タスク配信部３１４、演算結果出力部３１５、前処理実行部３２１及び後処理実行部３２２の機能を実現するプログラムは、磁気ディスク、フレキシブルディスク、光ディスク、コンパクトディスク、ブルーレイ（登録商標）ディスク、ＤＶＤ等の可搬記憶媒体に記憶されてもよい。
【００５５】
また、平文取得部３１１、ノード管理部３１２、タスクスケジューラ３１３、タスク配信部３１４、演算結果出力部３１５、前処理実行部３２１及び後処理実行部３２２の「部」を、「回路」又は「工程」又は「手順」又は「処理」に読み替えてもよい。
また、管理ノード１０は、ロジックＩＣ（Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）、ＧＡ（Ｇａｔｅ  Ａｒｒａｙ）、ＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ  Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）、ＦＰＧＡ（Ｆｉｅｌｄ−Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙ）といった処理回路により実現されてもよい。
【００５６】
また、記憶装置２０２には、ＯＳも記憶されている。
そして、ＯＳの少なくとも一部がプロセッサ２０１により実行される。
プロセッサ２０１はＯＳの少なくとも一部を実行しながら、タスク取得部４１１、タスク演算部４１２及び演算結果送信部４１３の機能を実現するプログラムを実行する。
プロセッサ２０１がＯＳを実行することで、タスク管理、メモリ管理、ファイル管理、通信制御等が行われる。
また、タスク取得部４１１、タスク演算部４１２及び演算結果送信部４１３の処理の結果を示す情報、データ、信号値及び変数値の少なくともいずれかが、記憶装置２０２、プロセッサ２０１内のレジスタ及びキャッシュメモリの少なくともいずれかに記憶される。
また、タスク取得部４１１、タスク演算部４１２及び演算結果送信部４１３の機能を実現するプログラムは、磁気ディスク、フレキシブルディスク、光ディスク、コンパクトディスク、ブルーレイ（登録商標）ディスク、ＤＶＤ等の可搬記憶媒体に記憶されてもよい。
【００５７】
また、タスク取得部４１１、タスク演算部４１２及び演算結果送信部４１３の「部」を、「回路」又は「工程」又は「手順」又は「処理」に読み替えてもよい。
また、子ノード２０は、ロジックＩＣ、ＧＡ、ＡＳＩＣ、ＦＰＧＡといった処理回路により実現されてもよい。
【００５８】
なお、本明細書では、プロセッサと、メモリと、プロセッサとメモリの組合せと、処理回路との上位概念を、「プロセッシングサーキットリー」という。
つまり、プロセッサと、メモリと、プロセッサとメモリの組合せと、処理回路とは、それぞれ「プロセッシングサーキットリー」の具体例である。
【符号の説明】
【００５９】
１０  管理ノード、１１  タスクスケジューラ、１２  能動キュー、１３  失効キュー、２０  子ノード、２１  子ノード、２２  子ノード、２ｎ  子ノード、１０１  プロセッサ、１０２  記憶装置、１０３  ネットワークインタフェース、２０１  プロセッサ、２０２  記憶装置、２０３  ネットワークインタフェース、３１１  平文取得部、３１２  ノード管理部、３１３  タスクスケジューラ、３１４  タスク配信部、３１５  演算結果出力部、３２１  前処理実行部、３２２  後処理実行部、４１１  タスク取得部、４１２  タスク演算部、４１３  演算結果送信部。
【要約】
管理ノード（１０）は、タスクの実行が可能な複数の子ノード（２０）を管理する。平文取得部（３１１）は、平文データを取得する。タスクスケジューラ（３１３）及びタスク配信部（３１４）は、平文取得部（３１１）による平文データの取得前に生成されていたタスクである先行タスクが存在する場合に、先行タスクを複数の子ノード（２０）のうちのいずれかの子ノード（２０）に割り当て、先行タスクの割当て後に、平文データから複数のタスクを複数の通常タスクとして生成し、複数の子ノード（２０）のうち、先行タスクを割り当てた子ノード（２０）以外の子ノード（２０）の間の処理量が均等になるように、子ノード（２０）に複数の通常タスクを割り当てる。【図１】
0006509475.tif 000002
【図２】
0006509475.tif 000003
【図３】
0006509475.tif 000004
【図４】
0006509475.tif 000005
【図５】
0006509475.tif 000006
【図６】
0006509475.tif 000007
【図７】
0006509475.tif 000008
【図８】
0006509475.tif 000009
【図９】
0006509475.tif 000010
【図１０】
0006509475.tif 000011
【図１１】
0006509475.tif 000012
【図１２】
0006509475.tif 000013
【図１３】
0006509475.tif 000014