"複数のノードを有し、各ノードにおいて動作する仮想的な計算単位であり、前記ノード間の移動が可能な複数のエントリにおいて、並列処理を行う並列分散処理方法であって、前記ノードは、前記エントリにおいて、計算処理を行うとともに、ノードが変更されるエントリのデータを、前記エントリの変更先のノードへ移動することを特徴とする並列分散処理方法。前記ノードは、前記エントリにおいて、計算処理を行うとともに、ノードが変更されるエントリのデータを、前記エントリの変更先ノードへコピーし、前記計算処理およびコピーの終了後に、前記コピーしたエントリに関するデータを削除することによって、前記移動を行うことを特徴とする請求項1に記載の並列分散処理方法前記ノードは、少なくとも前記エントリと、該エントリを有するノードと、該ノードの識別情報と、が組の情報として格納されているパーティションテーブルを有することを特徴とする請求項1または請求項2に記載の並列分散処理方法。前記ノードは、自身の前記ノードに前記残すエントリから計算処理を始め、前記変更元ノードから移動されたデータを用いた計算処理は、前記自身のノードに残すエントリにおける計算処理の終了後に行うことを特徴とする請求項1から請求項3のいずれか一項に記載の並列分散処理方法。前記ノードは、各エントリの計算処理において、各エントリから異なるエントリへメッセージを送信することが可能であり、各ノードは、自身が保持するエントリが他のエントリから送信されたメッセージを受信するためのバッファを備え、前記データとともに、前記バッファのデータも変更先ノードへ移動することを特徴とする請求項4に記載の並列分散処理方法。前記ノードは、前記移動エントリから計算処理を始めるとともに、前記計算処理の結果と、前記計算処理に使用したデータを変更先ノードへコピーし、前記計算処理を行うとともに、前記計算処理に使用したデータを移動し、前記移動エントリにおける計算処理が終了すると、自身に残すエントリにおける計算処理を行い、当該計算処理の結果を自身の記憶部に格納することを特徴とする請求項1から請求項3のいずれか一項に記載の並列分散処理方法。複数のノードを有し、各ノードにおいて動作する仮想的な計算単位であり、ノード間の移動が可能な複数のエントリにおいて、並列処理を行う並列分散処理方法であって、互いに前記エントリのバックアップ元と、前記エントリのバックアップ先の関係にある第1のノードと、第2のノードとが存在し、前記第1のノードが計算処理を行い、前記計算処理の結果である計算結果を前記第2のノードへコピーするとともに、前記第2のノードが計算処理を行い、前記計算処理の結果である計算結果を前記第1のノードへコピーし、前記第1のノードで、すべての計算結果が得られたが、前記第2のノードにおいて、計算結果を得ていない場合、前記第1のノードは、前記第2のノードにおいて、計算結果を得ていないエントリにおける計算結果を保持し、次の計算処理が始まった際に、前記第1のノードおよび前記第2のノードは、計算処理および計算結果のコピーを互いに行うとともに、前記第1のノードは、前記保持している計算結果を前記第2のノードへコピーすることを特徴とする並列分散処理方法。前記第1のノードおよび前記第2のノードで行われる、前記計算結果を得ていないエントリにおける計算結果を保持した後における計算処理は、前記計算結果が保持されているエントリの計算が、後になるよう行われることを特徴とする請求項7に記載の並列分散処理方法。前記エントリは、複数のタイプに分類され、前記並列処理毎に、異なるタイプの前記エントリで、当該並列処理を行うことを特徴とする請求項1から請求項8のいずれか一項に記載の並列分散処理方法。複数のノードにおいて並列処理を行う仮想的な計算単位である、複数のエントリが配置されている並列分散処理システムであって、前記ノードは、前記エントリにおいて、計算処理を行うとともに、ノードが変更されるエントリのデータを、前記エントリの変更先のノードへ移動することを特徴とする並列分散処理システム。複数のノードにおいて並列処理を行う仮想的な計算単位である、複数のエントリが配置されている並列分散処理システムであって、互いに前記エントリのバックアップ元と、前記エントリのバックアップ先の関係にある第1のノードと、第2のノードとが存在し、前記第1のノードが計算処理を行い、前記計算処理の結果である計算結果を前記第2のノードへコピーするとともに、前記第2のノードが計算処理を行い、前記計算処理の結果である計算結果を前記第1のノードへコピーし、前記第1のノードで、すべての計算結果が得られたが、前記第2のノードにおいて、計算結果を得ていない場合、前記第1のノードは、前記第2のノードにおいて、計算結果を得ていないエントリにおける計算結果を保持し、次の計算処理が始まった際に、前記第1のノードおよび前記第2のノードは、計算処理および計算結果のコピーを互いに行うとともに、前記第1のノードは、前記保持している計算結果を前記第2のノードへコピーすることを特徴とする並列分散処理システム。非特許文献1に記載の技術は、ノード障害に対する対策としてチェックポイントを利用している。チェックポイントとは、ある瞬間のシステム状態エントリの状態をストレージ装置に記録しておき、障害発生時にストレージ装置からデータを読み出し、チェックポイント取得時の配置状態に戻す手法である。チェックポイントの取得は、エントリの配置が確定している状態で行う必要があるため、システムは、エントリ間のメッセージ送信が終了し、各エントリにおける並列計算処理が行われる直前にチェックポイントを取得する必要がある。すなわち、チェックポイント取得のためだけの処理時間が必要になり、全体的な処理時間が増大するという課題がある。また、非特許文献1に記載の技術は、ノードの負荷均等化を実現するため、パーティション関数を使ってエントリのノードへの配置方法を決定している。パーティション関数はエントリ識別子を引数として与えると、そのエントリを配置すべきノードの識別子を出力する関数である。この方法ではエントリとノードとの関係が固定的になる。一方、複数ジョブの同時実行が可能なシステムでは、ジョブ実行前において、すでに他のジョブが実行されている場合や、ジョブ実行中に他のジョブが実行される場合があり、各ノードの余剰リソースの比が動的に変化するという特徴がある。このような計算機環境において、非特許文献1の記載の技術のようなエントリの配置を固定的に決める方法では、各ノードの負荷を均等化できない場合がある。また、特許文献1に記載の技術は、前記したように、各ノードの処理負荷を均等化するため、ノードへのデータ配置を変更する手法である。この技術を非特許文献1に適用しようとすると、非特許文献1に記載の技術では、エントリの配置が確定している状態でデータ配置の変更を行う必要があるため、チェックポイント取得と同様に、データ配置変更のためだけの処理時間が必要になり、全体として処理時間が増大するという課題がある。特許文献2に記載の技術は、前記したように、予めデータの複製を異なるノードに作成しておき、あるノードの負荷が高くなったときに複製データを持つノードが処理を代理実行することで、ノードの負荷均等化を実現するものである。しかしながら、このような技術を非特許文献1に記載の技術に適用しようとすると、非特許文献1に記載の技術では、エントリの配置が確定している状態で複製データを作成する必要があるため、チェックポイント取得の場合と同様に、データの複製作成のためだけの処理時間が必要になり、全体として処理時間が増大する。そのため、並列分散処理システムにおいて、効率的にエントリを移動する技術が求められる。本発明における一の手段は、複数のノードを有し、各ノードにおいて動作する仮想的な計算単位であり、前記ノード間の移動が可能な複数のエントリにおいて、並列処理を行う並列分散処理方法であって、前記ノードは、前記エントリにおいて、計算処理を行うとともに、ノードが変更されるエントリのデータを、前記エントリの変更先のノードへ移動することを特徴とする。さらに、本発明の他の手段は、複数のノードを有し、各ノードにおいて動作する仮想的な計算単位であり、ノード間の移動が可能な複数のエントリにおいて、並列処理を行う並列分散処理方法であって、互いに前記エントリのバックアップ元と、前記エントリのバックアップ先の関係にある第1のノードと、第2のノードとが存在し、前記第1のノードが計算処理を行い、前記計算処理の結果である計算結果を前記第2のノードへコピーするとともに、前記第2のノードが計算処理を行い、前記計算処理の結果である計算結果を前記第1のノードへコピーし、前記第1のノードで、すべての計算結果が得られたが、前記第2のノードにおいて、計算結果を得ていない場合、前記第1のノードは、前記第2のノードにおいて、計算結果を得ていないエントリにおける計算結果を保持し、次の計算処理が始まった際に、前記第1のノードおよび前記第2のノードは、計算処理および計算結果のコピーを互いに行うとともに、前記第1のノードは、前記保持している計算結果を前記第2のノードへコピーすることを特徴とする。その他の解決手段については、実施形態中で説明することとする。本発明によれば、並列分散処理システムにおいて、効率的にエントリを移動することができる。次に、本発明を実施するための形態実施形態というについて、適宜図面を参照しながら詳細に説明する。システム構成図図1は、本実施形態に係る並列分散処理システムの構成例を示す図である。並列分散処理システム100は、1つのマスタノード1、複数のスレーブノード2、クライアントノード3を有している。マスタノード1と、スレーブノード2は、それぞれ論理的な計算機であり、1つのサーバで複数のノードマスタノード1、スレーブノード2を実行してもよいし、単独のノードを実行するようにしてもよい。なお、各ノードは仮想的なネットワーク4で相互に接続されている。マスタノード1は、スレーブノード2の動作状況を管理する論理的な計算機であり、実際の計算処理はスレーブノード2上で行われる。なお、マスタノード1がスレーブノード2を兼ねることも可能である。また、並列分散処理システム100が実行する各ジョブは、複数のタスク21に分割されて実行される。マスタノード1は、ジョブマネージャ11および分散ファイルシステム12を実行している。ジョブマネージャ11は、スレーブノード2におけるジョブや、タスク21の実行状態を管理する。具体的には、ジョブとタスク21との対応関係、タスク21とそのタスク21を実行するスレーブノード2との対応関係、各タスク21の進捗率などを管理する。なお、分散ファイルシステム12については後記する。スレーブノード2は、実際の計算処理を行う論理的な計算機であり、少なくとも1つのタスク21と、タスクマネージャ23と、分散ファイルシステム24が実行されている。タスク21では、複数のエントリ22が実行されている。エントリ22は、タスク21や、ノード間を移動可能である。タスクマネージャ23は、各スレーブノード2で実行中のタスク21の実行状態実行中タスク21の進捗率などを管理する。タスクマネージャ23はタスク21を実行する際、1つのタスク21に対して複数のスレッドを割り当て実行することで、CPUCentralProcessingUnit201図2がマルチコアの場合にもCPUリソースを有効活用できる。なお、ファイルサイズが大きい場合、1つのファイルが複数のノードに分割配置されることがある。分散ファイルシステム12,24は、このような場合に、並列分散処理システム100のようにファイルの本体が複数のノードに分散配置されたときに、同一のパス名で、どのノードからもすべてのファイルへアクセス可能にするためのシステムである。分散ファイルシステム12,24を使用すると、アクセスすべきデータが、自身のノードに格納されておらず、他のノードに格納されている場合、他のノードの分散ファイルシステム12,24を経由して、データにアクセスする。スレーブノード2群の負荷状況に応じて、生成したタスク21の実行スレーブノードが動的に決定されるため、計算処理を実際に実行するスレーブノード2をどれにするかは事前に決まっていない。分散ファイルシステム12,24を使用することによって、どのスレーブノード2でタスク21が実行された場合も、そのタスク21は指定したファイルの指定したデータ位置にアクセスすることが可能となる。クライアントノード3はユーザインタフェースを提供する計算機端末である。利用者がクライアントノード3を操作して、並列分散処理システム100にジョブ実行指示を通知すると、クライアントノード3はマスタノード1のジョブマネージャ11にジョブ実行指示を送信する。ジョブマネージャ11は指示されたジョブを複数のタスク21に分割し、スレーブノード2のタスクマネージャ23に各タスク21を配布し、タスクマネージャ23に実行指示する。各スレーブノード2が複数のジョブを同時実行する場合は、図1に示すように、1つのスレーブノード2内に複数のタスク21が生成される場合がある。ジョブマネージャ11とタスクマネージャ23は並列分散処理システム100に常に常駐しており、サービスプロセスとして動作する。すなわち、ジョブを実行していないときは、ジョブマネージャ11とタスクマネージャ23は利用者からのジョブ実行要求を待つ待機状態となっている。また、タスク21はジョブを実行するたびに動的に生成されるプロセスであり、ジョブ実行を開始すると、タスクマネージャ23はタスク21に対応するプロセスを動的に生成する。異なるジョブ同士が影響しあうと、ジョブ実行の性能や安定性が低くなる場合があるため、タスクマネージャ23は、異なるジョブを異なるプロセスに分離することで、ジョブ同士の影響を低減している。ハードウェア構成図2は、本実施形態に係るマスタノードや、スレーブノードを実行する計算機のハードウェア構成図である。計算機200は、CPU201、LANLocalAreaNetwork250に接続されるLANI/F202、入出力I/F203、メモリ204、ディスクI/F205がバス206を介して内部で接続されている。入出力I/F203には、キーボード210、マウス220、ディスプレイ230が接続されており、利用者はこれらを使用してジョブの実行を指示する。ディスクI/F205には、OSOperatingSystemや、各ノードで動作するサービスプロセスのプログラムや、処理を行うための解析対象データが記録されているHDDHardDiskDrive240が接続されている。並列分散処理システム100図1起動時にディスク装置109から各プログラムがメモリ204に読み込まれ、CPU201がプログラムを実行することで、ジョブマネージャ11、タスク21、エントリ22、タスクマネージャ23などが具現化する。なお、マスタノード1図1とスレーブノード2図2を実行している計算機200については、ユーザが直接入出力操作を行うことはないため、キーボード210、マウス220、ディスプレイ230を省略することができる。並列処理モデル図3は、本実施形態に係る並列処理のモデル例を示す図である。なお、以下、本実施形態に係る並列分散処理システム100を、適宜本システム100あるいはシステム100と称することがある。本システム100では、キー-データ値形式のデータを保持するエントリ2222a~22c同士が相互にメッセージを交換する。例えば、エントリ22aはk1というキーとv11というデータ値を保持している。同様に、エントリ22bはk2というキーとv21というデータ値を保持しており、エントリ22cはk3というキーとv31というデータ値を保持している。キーはエントリ22の識別子であり、エントリ22の生成時に作成され、ジョブの実行中は変更されることはない。データ値はエントリ22が保持するデータそのものであり、並列処理を実行する過程で変更される場合がある。各エントリ22は、他のエントリ22からメッセージを受信すると、自身が保持するデータ値と受信したメッセージに基づいて計算処理を行い、必要に応じてデータ値を更新し、他のエントリ22に新たなメッセージを送信する。この処理はユーザプログラムとして実装される。メッセージ送信は送信先エントリのキーを指定することで行われる。各エントリ22はシステム100内のスレーブノード2に分散配置されるが、各エントリ22がどのスレーブノード2に配置されているかは、ジョブマネージャ11が管理しているため、ユーザプログラムはメッセージの送信先スレーブノード2を指定する必要はない。ここで、データ値は1つの値である必要はなく、複数の値の組であっても、ネスト構造であってもよい。従って、データ値の更新処理においてデータ値全体を更新する場合もあるし、データ値の一部を更新する場合もある。図4に示すように、本システム100では、BSPモデルに基づき、一連の並列計算とメッセージ送信とが同期しながら実行される。なお、図4において、符号22a~22cは図3と同様であるため、説明を省略する。例えばPhase1では、各エントリ22は、ユーザプログラムに記載された処理計算処理、データ値更新、メッセージ送信などを行う。各エントリ22の処理は並列実行され、すべてのエントリ22の処理が完了するまで待つ同期。すべてのエントリ22で、処理が完了したら、システム100はPhase2に移行し、各エントリ22は再びユーザプログラムに記載された処理を行う。このとき、v11、v21、v31の各データ値は、v12、v22、v32に更新される。このように、Phase1でエントリ22が送信したメッセージは、Phase2で初めて利用可能となる。BSPモデルでは、このような各Phaseのことをsuperstepと呼ぶ。以下、本実施形態では、このsuperstepを並列処理期間と称することとする。そして、この並列処理期間に各エントリ22において分散して行われる処理を並列処理計算処理、データ値更新、メッセージ送信などと称することとする。本システム100では、非特許文献1のようにエントリ22間のエッジを仮定しないが、エッジの有無に関して本質的な差異はない。つまり、本システム100においてエッジが設定されるようにしてもよい。本システム100においてメッセージの送信先エントリがわかっていない場合、そのエントリ22のキーを送信元エントリ22がデータ値として保持しておく必要があるが、これはエントリ22から別のエントリ22へのエッジを作成することと等価であるからである。パーティションテーブル図5は、本実施形態に係るパーティションテーブルの例を示す図でる。パーティションテーブルは、どのキーを有するエントリ22が、どのタスク21、あるいは、どのノードで実行されているかを管理するためのテーブルである。図1で説明したように、本システム100では、各タスク21が複数のエントリ22を保持しており、各タスク21が複数のエントリ22の処理を行う。各タスク21が保持するエントリ22の一覧は、図5に示すパーティションテーブルで管理されている。パーティションテーブルにおける各レコードが1つのタスク21に対応している。開始キーと終了キーとで示された範囲が、対応するタスク21が保持するエントリ22のキーの範囲を表す。タスクIDIdentificationはタスク21の識別子であり、ノードIDはそのタスク21が存在するノードの識別子である。宛先は、対応するノードの受信アドレスである。パーティションテーブルはジョブ毎に生成されるが、ジョブマネージャ11とそのジョブに関わるすべてのタスク21を管理しているタスクマネージャ23が同一のパーティションテーブルを保持している。ジョブマネージャ11は、ジョブ開始時にパーティションテーブル図5を作成し、タスクマネージャ23にタスク21の生成を指示する。タスク21の宛先はスレーブノード2のアドレスとポート番号の組から構成される。複数ジョブが同時実行される場合、複数のタスク用プロセスを1つのスレーブノード2上で実行するため、各タスク用プロセスに異なる受信用ポートを割り当てる必要がある。タスクマネージャ23はタスク21の生成指示を受けると、タスク用プロセスへの受信ポートの割り当てを行い、タスク用プロセスを生成する。タスク用プロセスの生成が完了すると、タスクマネージャ23はタスク21の宛先アドレスとポート番号をジョブマネージャ11に返し、ジョブマネージャ11は自身のパーティションテーブルにおいて、対応するタスク21の宛先図5を更新する。すべてのタスク21について生成が完了すると、ジョブマネージャ11は実行しているジョブに関わるすべてのタスク21を管理しているタスクマネージャ23へパーティションテーブルを送信する。このようにして、タスク21の生成時にすべてのタスクマネージャ23に同一のパーティションテーブルが配布される。データテーブル図6は、本実施形態に係るデータテーブルの例を示す図である。データテーブルは、どのエントリ22が、どのようなデータ値を保持しているかを管理するためのテーブルである。各タスクマネージャ23は、図6に示すデータテーブルを参照して、自身が保持するエントリ22のデータ値を管理している。データテーブルは、エントリ22のキーk、計算処理の結果のデータ値であるDn、並列処理中に受信したメッセージであるBr、並列処理期間開始前にエントリ22が保持しているデータ値であるD、前回の並列処理で受信したメッセージであるBuを有している。Buは、エントリにおいて他のエントリから送信されたメッセージを受信するためのバッファである。ここで、Dn=DBuである前記したように、並列処理中に受信したメッセージBrは、次の並列処理期間にならないと使用することができない。なお、実際には、DnはDとの差分が格納されることが多い。さらに、データテーブルは、データ値のバックアップであるDb、メッセージのバックアップであるBbの各データ値を有している。このうちDbとBbは、エントリ22を二重化する場合に利用する第3実施形態で後記。なお、図6において、各欄が空欄となっているが、実際にはデータ値が格納されている。ジョブマネージャ11は、図6に示すようなすべてのエントリ22に関するデータテーブルを有しているが、タスクマネージャ23は、システム100における、すべてのエントリ22に関するデータテーブルを有してもよいし、自身に対応するエントリ22に関するデータテーブルを有してもよい。並列処理の概要ここで、並列処理の概要を記載する。具体的な処理は、図7以降を参照して後記する。並列処理期間において、各エントリ22はデータテーブルを参照して、自身に対応するエントリ22のDとBuを用いてユーザが定義した計算処理を実行する。前記したように、Dは、並列処理期間開始時にエントリ22が保持しているデータ値であり、Buは前回の並列処理期間で受信したメッセージである。データ値の更新を行う場合、エントリ22は、更新前との差分を計算処理の結果Dnとして格納する。各タスク21は自分が保持するすべてのエントリ22の並列処理が終了したら、DnとDとをマージデータの結合などし、マージ後のデータ値を、新たなDとする。各タスク21は、この新たなDを並列処理期間終了後のデータ値として更新する。各タスク21は、他のタスク21が保持するエントリ22に対してメッセージを送信する。このとき、タスク21は、タスクマネージャ23が保持しているパーティションテーブルの宛先図5を参照して、送信先スレーブノード2を決定する。すなわちタスク21は、メッセージ送信時に宛先エントリ22のキーに対応するエントリ22をパーティションテーブルから検出する。そして、タスク21は、検出されたエントリ22の宛先図5に対してメッセージを送信する。送信するメッセージには、メッセージ本体と宛先エントリ22のキーが含まれている。メッセージを受信したタスク21は、自身が保持するデータテーブル図6を参照し、メッセージに含まれるキーに対応するエントリ22のBr並列処理中に受信したメッセージに受信したメッセージを追加する。Brへのメッセージ追加方法は、aメッセージを単純に追加していく方法と、b集約計算を行う方法がある。aの場合、Brは、最終的に複数のエントリ22から受信したメッセージのリストになる。また、bの例として、すべてのエントリ22から受信したメッセージの和をBrの結果とする処理などが挙げられる。和は結合法則と交換法則を満たすため、bの場合、メッセージを受信するたびに、タスク21は、受信したメッセージをBrのデータ値に加算したデータ値を計算し、その結果を新たなBrの値として更新する。このような演算が集約処理であり、結合法則と交換法則を満たす演算であればどのような演算であってもよい。他の集約処理の例として、最大、最小、二乗和などが用いられていてもよい。また、集約処理を行う場合、送信側タスク21において、同一エントリ22へ送信するメッセージを予め集約した後、集約結果を送信してもよい。これによって、ネットワーク転送量を削減することができる。メッセージ送信処理は、並列処理期間の途中では他のエントリ22からメッセージを受信する可能性があり、Brのデータ値を確定することができない。従って、ある並列処理期間が終了した時点、つまりすべてのエントリ22がある並列処理期間での並列処理を終えた時点で、その並列処理期間で更新されたBrの値が確定する。ある並列処理期間が終了しBrが確定したら、タスク21は、並列処理中にBrをBu並列処理期間開始前にエントリ22が保持しているデータ値に移動する。これによって、タスク21は、次回の並列処理期間において、受信したメッセージを使えるようになる。負荷均等化の具体例続いて、図1を参照しつつ、図7~図18に沿って本システム100における負荷均等化の手法を説明する。これは各スレーブノード2が保持するデータ量をノード性能に応じて調整することで、スレーブノード2の計算負荷を均等化する方法である。これを行うためにはデータ値をスレーブノード2間で移動する必要があるが、前記したように、BSPモデルにおける並列処理期間と次の並列処理期間の間にデータ移動を行うと、データ移動処理のためだけの時間が必要になる。そこで本実施形態におけるシステム100は、並列処理期間の実行中にデータ移動を並行して行うことで、データ移動処理の時間を並列処理期間の処理時間の中に隠蔽し、全体処理時間を削減するようにする。例えば、初期配置状態では図7の上段に示すように各ノード以降では、スレーブノード2のことを単にノードと称するにエントリ22が割り当てられたと仮定する。図7の横軸は各ノードが保持するエントリ22のキーを表している。図7の上段の例に示すように、ノード1はk1~k150、ノード2はk151図示せず~k225、ノード3はk226図示せず~k300のキーに対応するエントリ22を保持している。各ノードの性能が同一であれば、図7の上段に示す図では、ノード1に係る負荷が大きいため、図7の下段のようにエントリ22を移動して、各ノードにおける負荷を均等化する。すなわち、ジョブマネージャ11は、図7の下段のように各ノードに割り当てるキーの範囲を変更する。このとき、ジョブマネージャ11は、k101~k150のキー範囲のエントリ22をノード1からノード2へ移動する。そして、ジョブマネージャ11は、k201~k225のキー範囲のエントリ22をノード2からノード3へ移動する。このようにすることで、ノード1はk1~k100までのエントリ22を有し、ノード2はk101図示せず~k200までのエントリ22を有し、ノード3はk201図示せず~k300までのエントリ22を有する。つまり、各ノードは、100づつのエントリ22を有することになり、各ノードの性能が同一であれば、負荷均等化を図ることができる。なお、ここでは、説明を簡単にするため、各ノードの性能が同一であることを仮定したが、ノード性能が異なる場合は、ノード性能の比に応じてエントリ22の分配比を調整すればよい。《第1実施形態》続いて、図7に示すような負荷均等化の具体的な手順の第1実施形態を、図8~図13を参照して説明する。なお、第1実施形態~第3実施形態におけるシステム100の構成、ハードウェア構成は、図1および図2に示す構成と同様であるため、説明を省略する。なお、図8~図25において、縦軸が各ノードタスク21が保持するエントリ22のキーを示している。また、各エントリ22は、横方向に対応する各種データ値を有している。また、図8~図25において、破線で示した矩形はデータ値が存在しないことを示しており、実線の矩形はデータ値が存在することを示している。図8~図25の各図において、矩形内に示した記号の添え字はデータ値のバージョンを示す。例えば図8においてノード1は、同期開始前にエントリ22が保持しているデータ値であるDと、前回の並列処理期間で受信したメッセージBuを自分が担当するすべての範囲のキーに対して保持している。DにはD1、BuにはB1と記載されているが、この添え字1がバージョンである。詳細は後記するが、図9のノード1では、k100~k85の範囲のキーについてエントリ22の並列処理が終了し、データ値の差分であるDnの部分にd2と記載されている。ここで、添え字が2になっているが、このデータ値がバージョン1のデータ値D1とB1に基づいて生成されたため、バージョンが2に上がったことによる。まず各タスク21は、データ値の再分配を行う前に並列処理期間を最低1回実行し、各ノードにおける並列処理期間の実行時間を計測する。並列処理期間が終了したら、計測結果は各タスク21からジョブマネージャ11に集められ、ジョブマネージャ11は計測結果に基づき、各ノードに割り当てるキーの比を計算する。具体的には、既存のエントリ22の分配比がx1:x2:x3であり、処理時間の比がt1:t2:t3であった場合、ジョブマネージャ11は、エントリ22の分配比がx1/t1:x2/t2:x3/t3になるように調整することで、理論的には次回の処理時間の比を1:1:1にすることができる。ジョブマネージャ11は、このようなエントリ22の分配比を、パーティションテーブル図5を参照して計算する。このようにして算出した各ノードへのエントリ22の割り当てが、図7の下段に示すようにノード1に対してk1~k100、ノード2に対してk101~k200、ノード3に対してk201~k300になったと仮定する。ジョブマネージャ11は、再配置後のキーの範囲つまり、図5のパーティションテーブルを各ノードに配布し、次回の並列処理期間を開始するように各タスク21に要求する。以下、図7の上段の配置状態から、図7の下段の配置状態へエントリ22を再配置する具体的な手順を説明する。図8並列処理期間の開始時点で各ノードが保持するエントリ22は図8のようになっている。ここで、図8におけるエントリ22の配置状態は、図7の上段と同様の配置状態である。各ノードのタスク21は、ジョブマネージャ11から配布された再配置後のキーの範囲に基づき、他のノードに送信すべきキーの範囲を確定する。具体的には、ノード1はk101~k150をノード2に送信し、ノード2はk201~k225をノード3に送信することを確定する。この結果、この並列処理期間の終了後には、ノード1がk1~k100のエントリ22を有し、ノード2がk101~k200のエントリ22を有し、ノード3がk201~k300のエントリ22を有することになる。図9図9は、並列処理期間開始からしばらく時間が経過したときの、各ノードにおけるエントリの配置状態を示す図である。各ノードのタスク21は再配置後に自身が担当するキー範囲のエントリ22の並列処理の実行を開始すると共に、再配置対象のエントリ22のデータ値DおよびBuを宛先ノードのタスク21にする。例えば、ノード2は再配置後にk101~k200の範囲のキーを担当することになるが、k101~k150の範囲のキーは保持していない現時点では、ノード1が保持している。従って、ノード2は、エントリ22の並列処理の実行を、再配置後自身が保持し、かつ、現時点でも自身が保持している最大のキーであるk200から開始し、キーの値が小さくなる方向k200→k151にエントリ22の並列処理を進めていく。なお、図9~図13において、並列処理を進める方向を黒く塗りつぶした矢印で示す。図9の時刻では、ノード2はk200からk185まで並列処理を進めており、計算処理の結果としてk200~k185の範囲のエントリ22においてDnのデータ値d2が格納されている。このような計算処理と並行して、各ノードは、D、Buのデータ値を再配置後のノードへコピーしていくが、このとき、以下に記載するような手順でデータ値のコピーを行う。例えば、前記したようなノード2の並列処理動作を見越して、ノード1はノード2との再配置前のキー境界に近いデータ値から優先的にノード2にコピーする。つまり、ノード2はk200から順にキーの値が小さくなる方向にエントリ22の並列処理を行うため、ノード1はk101~k150の範囲のデータ値をノード2にコピーするときに、再配置前のキー境界であるk150からコピーを開始しする。そして、ノード1は、k150からキーの値が小さくなる方向k150→k101にk101まで順次データ値をコピーする。なお、図9~図13において、コピーしていく方向をハッチングの矢印で示し、コピーされるていく方向を白抜きの矢印で示す。これによって、ノード2におけるエントリ22の処理をなるべく滞らせずに実行することが可能となる。なお、図9において、ノード1はk150~k130までのデータ値をコピーしているのに、ノード2ではk150~k135までしかデータ値を受信していない。これは、送信受信のタイムラグのためである。すべてのノードにおいて、エントリ22の実行順序と、エントリ22のノード間送信順序はこのようなルールに基づいて実行する。なお、エントリ22の計算処理とエントリ22のデータ値のコピーは非同期に行われるため、エントリ22の計算処理が完了したキーに対応するすべてのDn、Dのコピーが完了しているわけではない。なお、エントリ22の計算処理とエントリ22のデータ値のコピーが同期的に行われてもよい。図9におけるDn、D、Buにおけるエントリの配置状態を、以下に整理する。ノード1:k100~k85まで計算処理が完了済みd2。k150~k130までのデータ値D1、B1がノード2へコピー済み。ノード2:k200~k185まで計算処理が完了済みd2。k1225~k205までのデータ値D1、B1がノード3へコピー済み。k150~k135までのデータ値D1、B1がノード1から受信済み。ノード3:k300~k285まで計算処理が完了済みd2。k225~k210までのデータ値D1、B1がノード2から受信済み。並列処理期間中に各エントリ22が他のエントリ22に対して送信するメッセージは、再配置後のエントリ配置に基づき送信される。従って、各ノードは再配置後に自身が担当する範囲のキーに対応するメッセージを受信することになる。例えば、ノード1は再配置後にk1~k100のキー範囲のエントリ22を担当するため、Brはこの範囲のデータ値のみを受信し、保持する。図9では、ノード1において、k1~k100のキー範囲に該当するBrが実線の矩形として示されている。ただし、並列処理期間実行中でありBrの値は確定していないため、図9において、Brではバージョン番号を伴ったデータ値を記載していない以降の図でも同様の理由から、確定前のBrにはバージョン番号を記載しない。また、再配置後、ノード1はそもそもk101~k150のキー範囲のエントリ22を担当しないため、図9では対応するBrの部分の破線表示を行っていない。同様の理由から、ノード2ではk101~k200のキー範囲に該当するBrが、ノード3ではk201~k300のキー範囲に該当するBrが実線の矩形として示されている。以降の図でも、Brは同様に示されるため、図10、図11ではBrの説明を省略することとする。図10図10は、図9からさらに時間が経過したときの、各ノードにおけるエントリの配置状態を示す図である。各ノードにおけるエントリの配置状態は以下の通りである。ノード1:k100~k55まで計算処理が完了済みd2。k150~k105までのデータ値D1、B1がノード2へコピー済み。ノード2:k200~k155まで計算処理が完了済みd2。k1225~k201までのデータ値D1、B1がノード3へコピー済み。k150~k110までのデータ値D1、B1がノード1から受信済み。ノード3:k300~k255まで計算処理が完了済みd2。k225~k201までのデータ値D1、B1がノード2から受信済み。図10に示す時刻では、ノード2からノード3へのデータ値DおよびBuのコピーは完了しているが、ノード1からノード2へのデータ値のコピーは未完である。図11図11は、図10からさらに時間が経過したときの、各ノードにおけるエントリの配置状態を示す図である。各ノードにおけるエントリの配置状態は以下の通りである。ノード1:k100~k15まで計算処理が完了済みd2。k150~k101までのデータ値D1、B1がノード2へコピー済み。ノード2:k200~k115まで計算処理が完了済みd2。k1225~k201までのデータ値D1、B1がノード3へコピー済み。k150~k101までのデータ値D1、B1がノード1から受信済み。ノード3:k300~k2215まで計算処理が完了済みd2。k225~k201までのデータ値D1、B1がノード2から受信済み。図11に示す時刻では、ノード2からノード3へのデータ値DおよびBuのコピーに加え、ノード1からノード2へのデータ値のコピーも完了している。しかし、各ノードにおける計算処理d2は未完である。図12図12は、図11からさらに時間が経過したときの、各ノードにおけるエントリの配置状態を示す図である。図12では、データ値のコピー、および各ノードにおける計算処理が終了している。図12の時点で並列処理期間における並列処理が終了し、BSPモデルにおける同期の配置状態へ移行する。並列処理期間が終了したことで、Brの状態が確定しているため、各ノードにおけるBrの矩形の内部にB2とバージョン番号の添え字付の値を記載している。また、ノード1におけるk150~k101、ノード2におけるk225~k201は、該当するノードにおける計算処理を行っていないため、データ値が存在しない破線矩形となっている。図13図13は、図12からさらに時間が経過したときの、各ノードにおけるエントリの配置状態を示す図である。図13は同期中におけるエントリの配置状態を示しており、この同期中に、各ノードのタスク21は、Dnの値をDにマージしd2D1、Dnをクリアする。また各ノードのタスク21は、BrをBuに移動し、Brをクリアする。図13ではDの値がD2になっているが、1つ前のバージョンのデータ値であるD1が新バージョンデータ値への差分d2をマージした結果D2になったためであるd2D1=D2。最後に、各ノードのタスク21は、自身が保持するパーティションテーブル図5の開始キー、終了キーを再配置後の値に更新する。第1実施形態の効果以上説明したように、並列処理期間において各ノードが再配置後のエントリ22に対する処理を行いつつ、データ値のコピー送信を行うことで、システム100はエントリ22の再配置処理時間を隠蔽することができ、全体処理時間を短縮することが可能になる。つまり、並列処理期間において、各ノードがエントリ22の計算処理を行うとともに、再配置後のエントリ22に従ってデータ値をコピーするため、システム100はエントリ22の再配置処理時間をエントリ22の計算処理に隠すことができ、全体処理時間を短縮することが可能になる。なお、データ値のコピーは、計算処理に比べて、CPU201図2やメモリ204図2の使用率が著しく低いため、データ値のコピーが並列処理時間に与える影響は小さい。《第2実施形態》続いて、図7に示すような負荷均等化の具体的な手順の第2実施形態を、図14~図18を参照して説明する。第1実施形態の技術は、エントリ22の再配置処理でDとBuをノード間で送信していたが、コピーするデータ量が多い場合、データ値のコピー処理に多くの時間を費やしてしまい、全体処理時間の削減効果が小さくなるという課題がある。そこで第2実施形態におけるシステム100は、再配置処理でDとBuの代わりにDnとDを送信する方法について説明する。この方式は、Buに比較してDnのデータ量が十分に小さい場合に有効になる。第1実施形態との違いはエントリ22の再配置処理であるため、以下ではエントリ22の再配置処理のみ説明する。第1実施形態と同様、図7に示すようにエントリ22の再配置を行う場合を例として説明する。各ノードのタスク21が他のノードにコピーするエントリ22のキーの範囲を確定する処理までは、第1実施形態と同じであるため説明を省略する。図14図14は、並列処理期間の開始時点における各ノードにおけるエントリの配置状態を示す図である。図14は、図8と同様であるため、説明を省略する。図15並列処理期間が開始すると、各ノードは、再配置前のエントリ22に対する処理を行うと共に、再配置後のエントリ22については計算処理の結果のDnとDを再配置先にコピーする。例えば、ノード1は、同期開始時点でk1~k150のキー範囲のエントリ22を保持しており、このうちk101~k150のキー範囲のエントリ22に対応するデータ値がノード2に送信される必要がある。ネットワーク4図1の状態によっては、データ値の送信には時間がかかる可能性があるため、システム100は送信対象エントリ22ノード1ではk101~k150の並列処理を優先して実行し、このキー範囲のデータ値のコピー処理を開始する。従って、ノード1はk101~k150のキー範囲のエントリ22における並列処理を、再配置後にもノード1に残るエントリ22k1~k100より先に実行し、計算処理結果であるDnd2が作成できたものから順にノード2にコピーする。このような制御を行うため、ノード1はk150からエントリ22の並列処理を開始し、キーの値が小さくなる方向k150→k1に並列処理を行っている。つまり、ノード1は再配置前のノード間のキー境界ここでは、k150に近いデータ値からエントリ22の並列処理を開始している。図15において、ノード1はk150からk125までのエントリ22の計算処理が完了し、対応するDnd2の作成が完了している。エントリ22の計算処理とエントリ22のデータ値のコピーは非同期に行われるため、エントリ22の計算処理が完了したキーに対応するすべてのDn、Dのコピーが完了しているわけではない。なお、エントリ22の計算処理とエントリ22のデータ値のコピーが同期的に行われてもよい。図15では、ノード1において計算処理が完了しているk150~k125のデータ値のうち、k150~k130の範囲のDn、Dのコピーが完了しているノード2参照。また、第2実施形態では、同じエントリ22に対応するDnとDとを対にして、送信先ノードへコピーする。ただし、必ずしもDnとDを対にしてコピーする必要はなく、ネットワーク4の帯域に余裕がある場合は、すべてのDnのコピーが完了する前に、すべてのDのコピーを完了してもよい。なお、図15、図16において、計算およびコピーしていく方向を黒く塗りつぶした矢印で示し、コピーされていく方向を白抜きの矢印で示す。同様に、図15において、k225~k201の範囲のエントリ22をノード3に再配置する必要があるため、ノード2は再配置前のキー境界k225からk225→k201の方向にエントリ22の並列処理を開始し、k205まで計算処理を終えている。そしてノード3はk225~k210の範囲のDnd2とDD1の受信を完了している。図15におけるDn、Dにおけるエントリの配置状態を、以下に整理する。ノード1:k150~k125まで計算処理が完了済みd2。k150~k130までのデータ値d2、D1がノード2へコピー済みノード2のDn、D参照。ノード2:k225~k205まで計算処理が完了済みd2。k225~k210までのデータ値d2、D1がノード3へコピー済みノード3のDn、D参照。k150~k130までのデータ値d2、D1がノード1から受信済み。ノード3:k300~k280まで計算処理が完了済みd2。k225~k210までのデータ値d2、D1がノード2から受信済み。なお、第2実施形態では、既に計算処理を行った結果Dnを送信先ノードで送っているため、送信先ノードでは、改めてDとBuを用いた計算処理を行う必要はない。そのため、各ノードにおいてBuのコピーは行われていない図16、図17も同様。また、Brについては、第1実施形態と同様であるため、説明を省略する。図16図16は、図15からさらに時間が経過したときの、各ノードにおけるエントリの配置状態を示す図である。なお、前記したように計算およびコピーの方向を黒く塗りつぶした矢印で示し、コピーされる方向を白抜きの矢印で示している。各ノードにおけるエントリの配置状態は以下の通りである。ノード1:k150~k95まで計算処理が完了済みd2。k150~k101までのデータ値d2、D1がノード2へコピー済みノード2のDn、D参照。ノード2:k225~k170まで計算処理が完了済みd2。k225~k201までのデータ値d2、D1がノード3へコピー済みノード3のDn、D参照。k150~k101までのデータ値d2、D1がノード1から受信済み。ノード3:k300~k226まで計算処理が完了済みd2。k225~k201までのデータ値d2、D1がノード2から受信済み。図16では、各ノードにおけるデータ値のコピーは完了しているが、ノード1、ノード2において計算処理が未完であるノード3は計算処理も完了している。図17図17は、図16からさらに時間が経過したときの、各ノードにおけるエントリの配置状態を示す図である。各ノードにおけるエントリの配置状態は以下の通りである。ノード1:k150~k1まで計算処理が完了済みd2。k150~k101までのデータ値d2、D1がノード2へコピー済みノード2のDn、D参照。ノード2:k225~k151まで計算処理が完了済みd2。k225~k201までのデータ値d2、D1がノード3へコピー済みノード3のDn、D参照。k150~k101までのデータ値d2、D1がノード1から受信済み。ノード3:k300~k226まで計算処理が完了済みd2。k225~k201までのデータ値d2、D1がノード2から受信済み。図17の時点で、各ノードにおける計算処理およびデータ値のコピーが完了している。そして、図17の時点で、並列処理期間の並列処理が終了し、BSPモデルにおける同期の状態へ以降する。ここで、第1実施形態と同様に、並列処理期間が終了したことで、Brの状態が確定しているため、Brの矩形の内部にB2とバージョン番号の添え字付の値を記載している。図18図18は、図17からさらに時間が経過したときの、各ノードにおけるエントリの配置状態を示す図である。図18は同期中におけるエントリの配置状態を示しており、この同期中に、各ノードのタスク21は、再配置後のエントリ22に対してDnの値をDにマージしd2D1=D2、また、Dnをクリアする。そして、各ノードのタスク21は、BrをBuに移動し、Brをクリアする。なお、Dにおけるバージョン番号は第1実施形態と同様であるため、説明を省略する。最後に、各ノードのタスク21は、自身が保持するパーティションテーブルの開始キー、終了キーを再配置後の値に更新する。第2実施形態の効果第2実施形態によれば、Buの代わりにDnこの値は、差分であることが多いのでデータ量が小さいを、送信先ノードへコピー送信することにより、送信データ量の削減が可能となる。《第3実施形態》次に、図19から図25を参照して、本発明の第3実施形態を説明する。第3実施形態におけるシステム100は、耐障害性を維持しつつ、データ移動の時間を隠蔽することを目的とする。耐障害性とノードの負荷均等化を両立するための技術として特許文献2に記載の技術が挙げられるが、前記したように、データ値の複製処理に対して余分な時間が必要となり、全体の処理時間が増大するという課題がある。このような課題に対し、第3実施形態におけるシステム100は、エントリ22における並列処理を行いつつ、データ値の複製を行うことで、全体の処理時間を削減する。第3実施形態と、第1実施形態、第2実施形態との違いは並列処理期間におけるエントリ22の処理とデータ複製処理であるため、この部分を中心に説明する。第3実施形態ではすべてのエントリ22のデータ値は2つのノードが保持する。主としてデータ値を管理し、エントリ22の処理を行うノードをプライマリノードと呼び単にプライマリと適宜称する:第1のノード、データ値の複製を保持し、負荷が小さいときにエントリ22の処理を代理実行するノードつまり、バックアップ用のノードをレプリカノードと呼ぶ単にレプリカと適宜称する:第2のノード。第3実施形態において、レプリカは別のキー範囲に対するプライマリを兼ねるため、プライマリに比べて計算処理能力代理実行能力が低いと仮定する。ただし、レプリカを専用のノードとし、プライマリと同等の計算処理能力を持つ構成としてもよい。図19図19は、並列処理期間の開始時点におけるプライマリとレプリカにおけるエントリの配置状態を示す図である。図19に示すように、プライマリとレプリカとでは、キー範囲k1~k100に対するエントリ22のデータ値D、Buが二重化されている。図20図20は、並列処理期間開始からしばらく時間が経過したときの、各ノードにおけるエントリの配置状態を示す図である。並列処理期間が開始されエントリ22の処理が始まると、プライマリはキーの値が最小であるk1からエントリ22の並列処理を開始し、k100の方向k1→k100へ並列処理を進めていく。プライマリは計算処理が完了したエントリ22から順に、計算処理結果であるDnd1をレプリカへコピーする。エントリ22の計算処理とDnのコピーは非同期に行われるため、計算処理中のエントリ22のキーとコピー中のDnに対応するキーは一致しない。なお、エントリ22の計算処理とDnのコピーが同期的に行われてもよい。図19では、k1~k40のエントリ22における計算処理が完了し、k1~k20のDnのコピーが完了しているレプリカ参照。なお、図20~図23において、計算およびコピーしていく方向を黒く塗りつぶした矢印で示し、コピーされていく方向を白抜きの矢印で示す。レプリカは負荷に余裕があり代理実行が可能であれば、プライマリが行うエントリ22の処理を肩代わりする。図20の例では、レプリカはプライマリの実行と処理が重ならないようにするため、プライマリとは逆順にエントリ22の処理を代理実行している。つまり、キーの値が最大であるk100からエントリ22の処理を開始し、k1の方向k100→k1へ進めていく。レプリカは代理実行したエントリ22の計算処理の結果であるDnd1をプライマリへコピーする。図19の例では、レプリカはk100~k85のエントリ22における計算処理が完了し、このうち、k100~k90のエントリ22についてデータ値Dnのコピーが完了しているプライマリ参照。なお、プライマリと、レプリカの並列処理が重ならないようにすれば、並列処理の方向は、図19に示す方向に限らない。例えば、それぞれの向きが逆向きでもよいし、任意のエントリ22から互いに逆方向に並列処理を進めてもよい。このようにプライマリとレプリカはエントリ22の処理を分担するが、そのエントリ22の並列処理を実行したノードがプライマリであってもレプリカであっても、並列処理を行っている他のエントリ22が送信したメッセージは、プライマリに送信される。従って、図19~図25において、レプリカにはBrが存在していない。ただし、他のエントリ22へのメッセージは、プライマリおよびレプリカから送信される。つまり、レプリカは、自身が計算したエントリ22については、メッセージの送信を行う。図20の時点におけるプライマリと、レプリカにおけるエントリの配置状態を整理すると以下のようになる。プライマリ:k1~k40まで計算処理が完了済みd1。k1~k20までのデータ値がレプリカへコピー済みレプリカのDn参照。k100~k90までのデータ値をレプリカから受信済みd1。レプリカ:k100~k85まで計算処理が完了済みd1。k100~k90までのデータ値がプライマリへコピー済みプライマリのDn参照。k1~k20までのデータ値をプライマリから受信済みd1。図21図21は、図20からさらに時間が経過したときの、各ノードにおけるエントリの配置配置状態を示す図である。プライマリと、レプリカにおけるエントリの配置配置状態は以下の通りである。プライマリ:k1~k80まで計算処理が完了済みd1。k1~k50までのデータ値がレプリカへコピー済みレプリカのDn参照。k100~k80までのデータ値をレプリカから受信済みd1。レプリカ:k100~k70まで計算処理が完了済みd1。k100~k80までのデータ値がプライマリへコピー済みプライマリのDn参照。k1~k50までのデータ値をプライマリから受信済みd1。図21の時点で、並列処理期間が終了したとする。すると、図21の時点で、プライマリはすべてのエントリ22についての計算処理結果d1を保持している。プライマリ自身が計算処理を実行したエントリ22と、レプリカから受信した計算処理結果が一致した地点がk80である。一方、図21の時点で、レプリカはk100から開始した代理実行がk70まで進んでおり、プライマリにはこのうちk100~k80のデータ値がコピーされている。すなわち、k70~k80のエントリ22については、プライマリとレプリカの両方で計算処理を行っている。前記したように、プライマリも、レプリカも自身が計算したエントリ22については、メッセージの送信を行うため、k70~k80のエントリ22に関して、プライマリとレプリカの双方からメッセージが送信されてしまう。その結果、他のノードにおけるプライマリは、プライマリとレプリカの双方から送信されたメッセージを受信してしまう。同一メッセージを2回Brに適用すると、Brの値が不正になるため、各ノードのプライマリではメッセージの重複受信を検出する必要がある。例えば、各ノードのプライマリでは受信したメッセージの送信元エントリのキーの集合を保持しておくことで、重複受信を検出することができる。つまり、各ノードのプライマリは、メッセージを受信したとき、そのメッセージの送信元のキーを保持しておく。そして、プライマリはメッセージを受信するたびに、そのメッセージの送信元のキーと、保持しているキーとを比較することで、メッセージを重複受信していないか否かを判定する。なお、メッセージを重複受信していることが検知された場合、プライマリは、後から受信したメッセージを破棄するなどの処理を行う。図21→図22ここで、前記したように図21の時点で並列処理期間は終了しており、BSPモデルにおける同期の状態になる。この間、レプリカは自身が保持するDnをDにマージし、Dnを保持していないキー範囲k51~k69のDとBuについては、それぞれレプリカ自身のDb、Bbにバックアップする。また、プライマリは、すべてのエントリ22においてDnをDにマージし、BrをBuへ移動する。さらに、プライマリは、レプリカが保持していないk51~k69のDnd1をプライマリ自身のDbにバックアップする。またプライマリは、すべてのエントリ22におけるBrをまとめてレプリカへコピーする。レプリカは、プライマリからBrを受信すると、受信したBrをBuに格納する。このようにすることで、キー範囲k1~k50およびk70~k100に対応するデータ値D、Buについては、並列処理期間実行後のデータ値が二重化されることになる。それ以外のキー範囲、すなわちk51~k69については、プライマリは並列処理期間実行後のデータ値DD1、BuB1を保持している。しかし、レプリカは、このキー範囲k51~k69については、Dを保持していない。ただし、レプリカはこのキー範囲k51~k69において、Db、Bbに並列処理期間実行前のデータ値D0、B0を保持しているため、これを使用して再計算することで並列処理期間実行後のDD1を作成することができるD0B0=d1、d1D0=D1。つまり、レプリカは、並列処理期間実行後のデータ値D1、B1を持つことと等価であり、データ値は問題なく二重化されていると言える。以上の処理を完了した結果が、図22に示される状態である。なお、プライマリ-レプリカ間の並列処理が完了しても、他のエントリ22における計算処理が完了していない場合がある。このような場合、他のエントリ22の計算処理が完了するのを待つ必要があるため、プライマリレプリカは、以下のような処理を行ってもよいが、本実施形態では、以下の処理を行わなかったものとして処理の説明を進める。つまり、この待ち時間を利用してプライマリはレプリカへ、適時k51~k69のDbd1をコピーしてもよい。そして、レプリカはd1を受信したらDbD0とマージし、マージ結果をDD1に格納していく。そして、レプリカは、マージと、マージ結果の格納と並行して更新が完了したキーに対応するDbとBbを順次クリアするようにしてもよい。またプライマリでは、Dbd1のコピーが完了したキーに対応するDbを順次クリアしてもよい。図22→図23次の並列処理期間において、レプリカでエントリ22の計算処理を代理実行する際にキーを進める方向として、ak1→k100、およびbk100→k1の2つの選択肢がある。この場合、どちらの方向から計算処理の代理実行を行うのかが、以下に示すように設定される必要がある。図22の時点で、レプリカは中間のキー範囲k51~k69のエントリ22のデータ値Dを保持していないため、この範囲のエントリ22における計算処理を実行することはできない。そこでレプリカは、なるべく多くのエントリ22に対して代理実行を実行できるようにするため、Dの存在するキー範囲においてエントリ22が多い側から代理実行を開始する。次の並列処理期間開始時点で図22に示すような配置状態であれば、k1~k50のキー範囲のレプリカの方が、k70~k100のキー範囲より、多くのデータ値DD1を保持している。よって、レプリカは、k1→k100の方向で代理実行を進めるよう代理実行の方向を設定する。レプリカは自身がプライマリとして管理するエントリ22を保持するため、並列処理期間が開始されたら直ちに代理実行を開始するわけではない。並列処理期間開始時にレプリカは代理実行の方向を決めておき、実際の代理実行は、自身の負荷が低いときに行う。レプリカが代理実行の方向を決めたらプライマリは、その逆順つまり、k100→k1の方向でエントリ22の並列処理を行う。これによって、並列処理を行うエントリ22が、プライマリとレプリカとで重複しないようにすることができる。また、プライマリはDbd1の残りをレプリカに送信するが、なるべくレプリカでの代理実行を継続できるように、レプリカの代理実行の方向と同方向となるようDbをコピーする。すなわち、本実施形態では、レプリカがk1→k100の方向で代理実行を行うので、プライマリは同方向となるk51→k69の方向でDbd1を送信する。図23図23は、並列処理期間開始から所定時間が経過したときにおけるエントリの配置状態を示す図である。図23の時点におけるエントリの配置状態は以下の通りである。プライマリ:k100~k40まで計算処理が完了済みd2。k100~k55までのデータ値d2がレプリカへコピー済みレプリカのDn参照。k1~k10までのデータ値d2をレプリカから受信済みd2。k51~k65までのDbd1をレプリカへ送信済み。レプリカ:k1~k10まで計算処理が完了済み。k1~k10までのデータ値d2がプライマリへコピー済みプライマリのDn参照。k100~k55までのデータ値d2をプライマリから受信済み。k51~k65までのデータ値d1をプライマリから受信し、それを自身のDbD0とマージすることでDD1を生成済み。ここで、レプリカからプライマリへコピーしたキー範囲が、k1~k10と同じであるのは、レプリカが自身の負荷に余裕のあるときに計算コピーを行っているためである。図24図24は、図23の時点からさらに時間が経過し、並列処理期間が終了した直後におけるエントリの配置状態を示す図である。図24の時点におけるエントリの配置状態は以下の通りである。プライマリ:k100~k30まで計算処理が完了済み。k100~k50までのデータ値d2がレプリカへコピー済みレプリカのDn参照。k1~k30までのデータ値d2をレプリカから受信済み従って、Dnのデータ値をすべて保持している。k51~k69までのDbd1をレプリカへ送信済み。レプリカ:k1~k30まで計算処理が完了済み。k1~k30までのデータ値d2がプライマリへコピー済みプライマリのDn参照。k100~k50までのデータ値d2をプライマリから受信済み。k51~k69までのデータ値d1をプライマリから受信し、それを自身のDbD0とマージすることでDD1を生成済み従って、DD1のデータ値をすべて保持している。ここで、プライマリではk100~k30までの計算処理が完了しているのに、レプリカがk100~k50までしかデータ値を受信していないのは、レプリカの性能が、プライマリより低いためである。図24の時点において、レプリカは、前回の並列処理期間で処理が完了していなかったk51~k69のキー範囲のデータ値DD1をすべて保持することができるが、新たにk31~k49のキー範囲のデータ値Dnd2について計算処理が間に合わず、当該範囲のデータ値を保持していない状態となっている。図24→図25図24の時点で並列処理期間が終了したとすると、図24におけるエントリの配置状態から、プライマリおよびレプリカは、図21→図22と同様の処理を行う。すなわち、レプリカは自身が保持しているキー範囲k1~k30、k50~k100のDnd2をDD1にマージして、マージした結果D2をDに格納する。また、レプリカは、Dnを保持していないキー範囲k31~k49のDD1とBuB1については、それぞれ自身のDb、Bbにバックアップをとる。またプライマリは、Dnd2をDD1にマージし、BrB2をBuに移動する。そして、プライマリは、レプリカが保持していないk31~k49のキー範囲のDnd2を自身のDbにバックアップする。またプライマリは、すべてのキー範囲のBrB2をまとめてレプリカに送信する。レプリカはBrB2をプライマリから受信したら、受信したデータ値B2をBuに代入する。以上の処理を行うことで、各エントリ22におけるエントリの配置状態は、図25に示すようになる。そして、ジョブマネージャ11は、各エントリ22に関する情報をデータテーブルに反映することによって、データテーブルを更新する。第3実施形態の効果第3実施形態によれば、システム100はレプリカにおいて、すべての代理実行が終了せずに並列処理期間が終了しても、次の並列処理期間で終了しなかったキー範囲の代理実行を行いつつ、新たな代理実行も行うことができるため、効率的に複製を行うことができる。《第4実施形態》図26は、第4実施形態に係る並列計算処理の概要を示す図である。なお、第4実施形態でも、システム構成、ハードウェア構成は、図1、図2と同様であるので、システム構成、ハードウェア構成に対する図示、説明を省略する。第1実施形態~第3実施形態では、図4に示すような、各並列処理期間で同一のエントリ群が並列計算を実行するモデルに基づいていた。しかしながら、実際には、図26に示すように、並列処理期間毎に異なるエントリ群が並列計算を実行する場合がある。第4実施形態では、このような並列分散処理システム100の場合を、第1実施形態~第3実施形態に適用した場合について説明する。図26において、各エントリ22は、図3,図4に示すようなキー,データ値に加えてタイプ種別という属性を有している。例えば、図11の左上に記載したエントリ22にはT1,k1,v11と記載されているが、これはタイプがT1で、キーがk1で、データ値がv11であることを示している。この、並列分散処理システム100ではタイプが同一のエントリ群が同じ並列処理期間で並列計算処理を行い、同期後の次の並列処理期間では、前回の並列処理期間とは異なるタイプのエントリ群が並列計算処理を行う。そして並列処理期間を繰り返すうちに、ある並列処理期間で以前処理を実行したエントリ群が再び並列処理を行う。例えば、図26におけるPhase1ではタイプがT1のエントリ群が並列計算処理を行い、次のPhase2ではタイプがT2のエントリ群が並列計算処理を行っている。そして、Phase3では再びタイプがT1のエントリ群の処理を行っている。なお、タイプT2のエントリ群におけるw11はデータ値を示している。このような並列分散処理システム100を実現するために、図5に示すパーティションテーブルおよび図6に示すデータテーブルがタイプ毎に作成される。前記したように、元々、パーティションテーブル、データテーブルはジョブ毎に作成していたため、第4実施形態では、パーティションテーブルおよびデータテーブルがジョブとタイプの組み合わせ毎に作成されることになる。なお、1つのタイプに属するエントリ群の処理が並列実行されるため、タイプ単位で負荷の均等化が実現できることが望ましい。このために、タイプ毎にパーティションテーブルおよびデータテーブルが作成されている。続いて、図26に示す並列分散処理システム100を第1実施形態~第3実施形態のそれぞれに適用した場合の処理について説明する。第1実施形態に適用した場合第1実施形態の図8から図13で説明したデータ再配置処理において、エントリ22が送信したメッセージは並列処理期間で並列処理を実行中のエントリ群が受け取っていたが、第4実施形態では次の並列処理期間で並列計算処理を実行するタイプのエントリ群従って、現在並列計算処理を行っているエントリ群とは異なるエントリ群が受信することになる。従って、図8から図13に、各エントリ22が送信したメッセージは図示されているBrへは送信されず、次の並列処理期間で並列計算処理を行うエントリ群のBrへメッセージが送信される。そして、再配置の際に、システム100はメッセージ送信先のエントリ群のデータ値の再配置は行わず、メッセージ送信元のエントリ群のデータ値の再配置を行う。つまり、システム100は、現在並列計算処理を行っているエントリ群については再配置を行うが、次の並列処理期間で並列計算処理を行うエントリ群については、再配置を行わない。従って、エントリ22のメッセージを実際に送信するノードは、次に並列処理を行うタイプのパーティションテーブルを使って決定される。その他の処理については、第1実施形態で説明した処理とと同様である。ただし、第1実施形態に適用する場合、ある並列処理期間で各タスクの実行時間が計測され、各タスクへのデータ配置が決定された後、システム100は、次に最初のタスクとはタイプが異なるタスク群の並列処理を実行している間に、最初のタスクに関するデータの再配置を行うことができる。またデータの再配置が完了する前に、最初に実行時間を計測したタスクと同じタイプのタスク群を実行することになった場合、データの再配置を続けながらそのタスク群の並列処理を行うことが可能である。このように、システム100はデータの再配置処理を効率化することができる。例えば図26の例ではPhase1でタイプがT1のエントリ群の並列計算処理を行うタスク群の実行時間が計算され、各タスクへの最適なデータ配置が決定される。そしてPhase2でT2のエントリ群の並列計算処理を行っている間に、T1のエントリ群の再配置が行われる。第2実施形態に適用した場合第4実施形態に係る並列分散処理システム100を、第2実施形態に適用した場合も第1実施形態に適用した場合と同様である。すなわち、エントリ22のメッセージを実際に送信するノードは、次に並列処理を行うタイプのパーティションテーブルを使って決定する。図15~図17では、並列処理期間で並列計算処理を実行中のエントリ22のBrに受信したメッセージが蓄積されていくが、第4実施形態を適用すると、並列処理期間で処理を実行中のエントリ群はメッセージを受信せず、次の並列処理期間で並列計算処理を行うエントリ群がメッセージを受信する。その他の処理については、第2実施形態と同様の処理である。第2実施形態においても、第1実施形態へ第4実施形態を適用した場合のデータ再配置効率化手法を実施することが可能である。ただし、第2実施形態はエントリの計算を行ってから計算結果を再配置先へ送信するため、データ再配置処理が次回の並列計算処理を開始するまでに完了しなかった場合、各タスクは次回の並列計算処理開始時点で保持するデータに対して並列計算処理を行い、その結果を再配置先へ送信することになる。第3実施形態に適用した場合第4実施形態係る並列分散処理システム100を、第3実施形態に適用した場合についても、エントリ22のメッセージ送信に関しては第1実施形態、第2実施形態に適用した場合と同様である。各エントリ22が送信したメッセージは、次の並列処理期間で並列計算処理を実行するエントリ群のプライマリに対して送信される。従って、図21、図22に移行する過程で、プライマリは、レプリカへBrの内容を送信しているが、第4実施形態を適用した場合では、次の並列処理期間を実行するエントリ群のプライマリから、次の並列計算処理を実行するレプリカに対してBrの内容を送信することになる。つまり、並列処理の実行順が図26で示すような順番であるとすると、Phase1終了時に、T2のプライマリはT2のレプリカへBrの内容を送信し、次のPhase2終了時に、T1のプライマリはT1のレプリカへBrの内容を送信することとなる。また、図22において、プライマリのDbにバックアップされた未送信データ値d2が残っているが、次の並列処理期間図23~図25では、これらのプライマリ、レプリカは、並列計算処理を行わないため、次の並列処理期間の処理中に、プライマリのDbのデータ値d2をレプリカに送信し、レプリカは、受信したデータ値を基にDを生成することができる。そのため、第3実施形態より効率的な複製が可能となる。その他の処理については、第3実施形態における処理と同様である。第4実施形態の効果第4実施形態によれば、並列処理期間毎に異なるエントリ群で並列計算処理を行うことで、並列分散処理システム100全体の負荷を低減することができる。"