(57)【特許請求の範囲】
【請求項１】
クラスタを構成するノードとしてネットワーク上に配置され、並列計算処理を実行する並列計算処理装置であって、
複数の前記ノードの中から、計算処理を担当するノードであるマスタノードを決定し、前記マスタノードに計算処理を振り分ける振分処理部と、
所定の計算ステップとして前記計算処理を実行する数値計算部と、
前記マスタノードの計算処理の処理結果を、前記マスタノードと計算処理を並列に実行する１つ以上のネイバノードに送信するとともに、前記ネイバノードの計算処理の処理結果を受信し、前記所定の計算ステップの次に実行する所定の計算ステップに必要な前記ネイバノードからの処理結果が揃っているか否かを判定し、揃っていると判定した場合に、受信した前記ネイバノードからの処理結果を、前記数値計算部に出力するデータ送受信同期部と、
前記データ送受信同期部が、前記ネイバノードからの処理結果が揃っていないと判定した場合に、前記次に実行する所定の計算ステップに必要となるデータとして、ダミーデータを生成し、前記数値計算部の計算処理を続行させる障害管理部と、
を備えることを特徴とする並列計算処理装置。
【請求項２】
前記数値計算部が実行した前記マスタノードとしての前記計算処理の処理結果の複製データと、前記データ送受信同期部が前記ネイバノードから受信した処理結果の複製データとを生成し、前記生成した各前記複製データを、前記マスタノード以外の他のノードであるレプリカノードに送信するデータ格納処理部を、さらに備えること
を特徴とする請求項１に記載の並列計算処理装置。
【請求項３】
前記マスタノードとして機能するノードの障害を検出した場合に、前記レプリカノードを前記マスタノードに昇格させる障害管理部を、さらに備えること
を特徴とする請求項２に記載の並列計算処理装置。
【請求項４】
クラスタを構成するノードとしてネットワーク上に配置される並列計算処理装置の並列計算処理方法であって、
前記並列計算処理装置は、
複数の前記ノードの中から、計算処理を担当するノードであるマスタノードを決定し、前記マスタノードに計算処理を振り分けるステップと、
所定の計算ステップとして前記計算処理を実行するステップと、
前記マスタノードの計算処理の処理結果を、前記マスタノードと計算処理を並列に実行する１つ以上のネイバノードに送信するとともに、前記ネイバノードの計算処理の処理結果を受信し、前記所定の計算ステップの次に実行する所定の計算ステップに必要な前記ネイバノードからの処理結果が揃っているか否かを判定するステップと、を実行し、
前記ネイバノードからの処理結果が揃っていると判定した場合に、受信した前記ネイバノードからの処理結果を用いて、次の所定の計算ステップを実行し、
前記所定の計算ステップの次に実行する所定の計算ステップに必要な前記ネイバノードからの処理結果が揃っているか否かを判定するステップにおいて、前記ネイバノードからの処理結果が揃っていないと判定した場合に、前記次に実行する所定の計算ステップに必要となるデータとして、ダミーデータを生成し、前記計算処理を続行させるステップを、さらに実行すること
を特徴とする並列計算処理方法。
【請求項５】
前記マスタノードとしての前記計算処理の処理結果の複製データと、前記ネイバノードから受信した処理結果の複製データとを生成し、前記生成した各前記複製データを、前記マスタノード以外の他のノードであるレプリカノードに送信するステップを、さらに実行すること
を特徴とする請求項４に記載の並列計算処理方法。
【請求項６】
前記マスタノードとして機能するノードの障害を検出した場合に、前記レプリカノードを前記マスタノードに昇格させるステップを、さらに実行すること
を特徴とする請求項５に記載の並列計算処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワーク上に分散配置されることによりクラスタを構成する並列計算処理装置および並列計算処理方法に関する。
【背景技術】
【０００２】
並列計算モデルのなかで、並列化された処理のステップ毎にインタラクション（相互作用）が生じ、それを同期しながら計算を進めるモデルとしてＢＳＰ（Bulk Synchronous Parallel：バルク同期並列）がある（非特許文献１参照）。このＢＳＰ計算モデルは、例えば、地図上のある地点の人や車の移動に関するシミュレーションにおいて、地図をメッシュ分割し、あるメッシュに存在する人や車を数える際に、当該地区（メッシュ）内を数えるだけでなく、隣接する地区（メッシュ）との出入（ｏｕｔ／ｉｎ）も数えることで、より正確な数値を求めるというような計算モデルである。
【０００３】
このＢＳＰは、「スーパーステップ（ｓｕｐｅｒｓｔｅｐ)」という処理単位を繰り返し実行することにより、分散環境でのデータ処理を実行する。図１は、ＢＳＰ計算モデルを説明するための図である。
【０００４】
スーパーステップは、図１（ａ）に示すように、スーパーステップ１（図１において「ＳＳ１」と記載。以下同様。）として「ローカル計算（ＬＣ：Local computation）」、スーパーステップ２（ＳＳ２）として「データ交換」、スーパーステップ３（ＳＳ３）といて「同期」の３つのフェーズから構成される。
具体的には、図１（ａ）示すように、複数のノード（ノード１〜ノード４）のうちのいずれかのノードがデータを受信すると、そのノード（例えば、ノード１）がスーパーステップ１（ＳＳ１）において、そのデータについての計算処理（ローカル計算（ＬＣ））を実行する。続いて、スーパーステップ２（ＳＳ２）において、各ノードが保持しているローカル計算の結果であるデータについて、ノード間でのデータ交換を実行する。次に、スーパーステップ３（ＳＳ３）において、同期処理を行う、より詳細には、すべてのノード間でのデータ交換の終了を待つ。
そして、Ｓｔｅｐ１として、一連のスーパーステップの処理（ＳＳ１〜ＳＳ３）が終了すると、各ノードはその計算結果を保持した上で、次の一連のスーパーステップの処理であるＳｔｅｐ２へと進む。
【０００５】
このＢＳＰを、対象領域をメッシュ分割してシミュレーションする計算（メッシュ分割シミュレーション計算）を行う場合に採用すると、図１（ｂ）に示す処理となる。メッシュ分割された対象領域は、各ノードに割り当てられる。ここで、分割されたメッシュのひとつとして「メッシュｘ」に注目すると、メッシュｘについて計算ステップをＳｔｅｐ ｎからＳｔｅｐ ｎ＋１に進めるには、メッシュｘとその隣接メッシュ（ｘnorth，ｘeast，ｘwest，ｘsouth）のＳｔｅｐ ｎの計算結果が必要となる。
具体的には、このメッシュ分割シミュレーション計算では、スーパーステップ１（ＳＳ１）において、各メッシュにおける計算処理（ローカル計算（ＬＣ））を実行する。続いて、スーパーステップ２（ＳＳ２）において、各メッシュ（隣接メッシュとの間）の計算結果の送受信（データ交換）を実行する。次に、スーパーステップ３（ＳＳ３）において、すべての隣接メッシュからのデータ（計算結果）の受信完了待ちを行う。このスーパーステップの一連の処理を繰り返すことにより、ＢＳＰ計算モデルによるシミュレーション計算を実行する。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Leslie G. Valiant, et al., “A bridging model for parallel computation”, Communications of the ACM, 1990.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、このＢＳＰ計算モデルは、以下に示す問題がある。
（問題１：負荷分散性の向上）
ＢＳＰ計算モデルは、前ステップの計算結果を引き継いで次ステップ以降の計算を進めていく（つまり、「ステートフル」である。）ため、複数の計算ノードでクラスタを構成して処理を行う際に、信号の振分処理がボトルネック化する等の理由により、負荷分散性を向上させるのが難しい。
【０００８】
（問題２：可用性（耐障害性）の向上）
ＢＳＰ計算モデルは、前ステップの計算結果を引き継いで次ステップ以降の計算を進めていく（つまり、「ステートフル」である。）ため、可用性（耐障害性）を高めるためには、データ保護・復旧等の仕組みが必要となる。また、ＢＳＰ計算モデルは、ノードが相互にインタラクションしながら処理を進めるため、一部のノード障害が全体に波及してしまう。
【０００９】
図２は、問題２（可用性（耐障害性）の向上）について、詳細に説明するための図である。
図２（ａ）に示すようなメッシュ分割されたシミュレーション計算を複数のノードが並列実行することを前提とする。ここで、ある注目するメッシュｘについて、Ｓｔｅｐ ｎの計算時間（データが揃ってから計算が完了するまでの時間）をｔ（ｘ，ｎ）、データ送受信の通信遅延をｌａｔｅｎｃｙ（簡易化のために定数とする。）とする。この場合、メッシュｘについて、計算開始からＳｔｅｐ ｎの計算とデータ送受信が完了するまでにかかる時間Ｔ（ｘ，ｎ）は、図１（ｂ）の（式１）となる。
ここで、メッシュｘの隣接メッシュをメッシュｘnorth，メッシュｘeast，メッシュｘwest，メッシュｘsouthとする。
【００１０】
このとき、すべてのメッシュについて、計算開始からＳｔｅｐ ｎの計算が完了するまでにかかる時間Ｔ（ａｌｌ，ｎ）は、図１（ｃ）の（式２）となる。
（式１）および（式２）により示されるように、シミュレーション計算時間は、各ステップにおけるローカル計算（ＬＣ）の計算時間の最大値に依存する。そのため、どこか一箇所のメッシュでも著しく計算時間が延びた場合、シミュレーション全体の計算時間が著しく延び、最悪の場合には停止してしまう。つまり、一部のメッシュの処理遅延や停止により、シミュレーション全体が遅延もしくは停止することとなる（図１の符号α）。
【００１１】
（問題３：動的な構成変更への対応）
計算処理するリソースを効率的に利用するために、処理負荷に応じたクラスタ規模の動的な拡大・縮小を可能とする必要がある。その際、クラスタ構成の変更（ノードの増減設）時の振分先決定処理のための再計算や、ノード間の処理（データ）引継ぎのコストを抑える必要がある。
【００１２】
（問題４：汎用化）
ＢＳＰ計算モデル等を採用する様々なアプリケーションに対し、問題１〜３を解決する汎用的なソリューションを提供する必要がある。
【００１３】
従来のＢＳＰ計算モデルでは、上記した問題１〜４が存在していたため、例えば、金融、通信、交通のようなミッションクリティカルなシステム（２４時間３６５日、止まらないことを要求される、極めて高い信頼性が必要とされる業務に使用されるシステム）には、適用できなかった。
【００１４】
このような背景を鑑みて本発明がなされたのであり、本発明は、ＢＳＰ計算モデルにおいて負荷分散性を向上させることができる、並列計算処理装置および並列計算処理方法を提供することを課題とする。
さらに、本発明は、ＢＳＰ計算モデルをミッションクリティカルなシステムに提供可能とする、並列計算処理装置および並列計算処理方法を提供することを課題とする。
【課題を解決するための手段】
【００１５】
前記した課題を解決するため、請求項１に記載の発明は、クラスタを構成するノードとしてネットワーク上に配置され、並列計算処理を実行する並列計算処理装置であって、複数の前記ノードの中から、計算処理を担当するノードであるマスタノードを決定し、前記マスタノードに計算処理を振り分ける振分処理部と、所定の計算ステップとして前記計算処理を実行する数値計算部と、前記マスタノードの計算処理の処理結果を、前記マスタノードと計算処理を並列に実行する１つ以上のネイバノードに送信するとともに、前記ネイバノードの計算処理の処理結果を受信し、前記所定の計算ステップの次に実行する所定の計算ステップに必要な前記ネイバノードからの処理結果が揃っているか否かを判定し、揃っていると判定した場合に、受信した前記ネイバノードからの処理結果を、前記数値計算部に出力するデータ送受信同期部と、前記データ送受信同期部が、前記ネイバノードからの処理結果が揃っていないと判定した場合に、前記次に実行する所定の計算ステップに必要となるデータとして、ダミーデータを生成し、前記数値計算部の計算処理を続行させる障害管理部と、を備えることを特徴とする並列計算処理装置とした。
【００１６】
また、請求項４に記載の発明は、クラスタを構成するノードとしてネットワーク上に配置される並列計算処理装置の並列計算処理方法であって、前記並列計算処理装置が、複数の前記ノードの中から、計算処理を担当するノードであるマスタノードを決定し、前記マスタノードに計算処理を振り分けるステップと、所定の計算ステップとして前記計算処理を実行するステップと、前記マスタノードの計算処理の処理結果を、前記マスタノードと計算処理を並列に実行する１つ以上のネイバノードに送信するとともに、前記ネイバノードの計算処理の処理結果を受信し、前記所定の計算ステップの次に実行する所定の計算ステップに必要な前記ネイバノードからの処理結果が揃っているか否かを判定するステップと、を実行し、前記ネイバノードからの処理結果が揃っていると判定した場合に、受信した前記ネイバノードからの処理結果を用いて、次の所定の計算ステップを実行し、前記所定の計算ステップの次に実行する所定の計算ステップに必要な前記ネイバノードからの処理結果が揃っているか否かを判定するステップにおいて、前記ネイバノードからの処理結果が揃っていないと判定した場合に、前記次に実行する所定の計算ステップに必要となるデータとして、ダミーデータを生成し、前記計算処理を続行させるステップを、さらに実行することを特徴とする並列計算処理方法とした。
【００１７】
このようにすることで、並列計算処理装置は、その計算処理を担当するノード（マスタノード）に振り分けた上で計算ステップを実行し、計算処理の処理結果を得ることができる。そして、マスタノードが、自身の計算処理の処理結果をネイバノードに送信するとともに、ネイバノードから処理結果を受信し、ネイバノードからの処理結果が揃っていると判定した場合に、次の計算ステップを実行することができる。
よって、計算処理を各ノード（マスタノード）に振り分けることができるので、振分処理のボトルネック化を防ぐことができるとともに、並列計算処理の負荷分散性を向上させることができる。また、並列化された処理ステップごとにデータ（処理結果）を送受信し、それを同期しながら計算する処理（ＢＳＰ計算モデル）を、所定の計算ステップとして汎用化して提供することが可能となる。
また、並列計算処理装置は、ネイバノードからの処理結果が揃っていないと判定した場合に、ダミーデータを生成し、そのダミーデータを用いて並列計算処理を続行することができる。
【００１８】
請求項２に記載の発明は、前記数値計算部が実行した前記マスタノードとしての前記計算処理の処理結果の複製データと、前記データ送受信同期部が前記ネイバノードから受信した処理結果の複製データとを生成し、前記生成した各前記複製データを、前記マスタノード以外の他のノードであるレプリカノードに送信するデータ格納処理部を、さらに備えることを特徴とする請求項１に記載の並列計算処理装置とした。
【００１９】
また、請求項５に記載の発明は、前記マスタノードとしての前記計算処理の処理結果の複製データと、前記ネイバノードから受信した処理結果の複製データとを生成し、前記生成した各前記複製データを、前記マスタノード以外の他のノードであるレプリカノードに送信するステップを、さらに実行することを特徴とする請求項４に記載の並列計算処理方法とした。
【００２０】
このように、並列計算処理装置は、マスタノードとして計算処理した処理結果と、ネイバノードから受信した処理結果とについて複製データを生成し、レプリカノードに記憶させることができる。
よって、マスタノードに障害が発生した場合であっても、レプリカノードの記憶された複製データにより、並列計算処理を継続することが可能となる。
【００２１】
請求項３に記載の発明は、前記マスタノードとして機能するノードの障害を検出した場合に、前記レプリカノードを前記マスタノードに昇格させる障害管理部を、さらに備えることを特徴とする請求項２に記載の並列計算処理装置とした。
【００２２】
また、請求項６に記載の発明は、前記マスタノードとして機能するノードの障害を検出した場合に、前記レプリカノードを前記マスタノードに昇格させるステップを、さらに実行することを特徴とする請求項５に記載の並列計算処理方法とした。
【００２３】
このように、並列計算処理装置は、マスタノードとして機能するノードの障害を検出した場合に、レプリカノードをマスタノードに昇格させることにより処理停止を防ぎ、昇格したマスタノードにより並列計算処理を継続することができる。
【発明の効果】
【００２７】
本発明によれば、ＢＳＰ計算モデルにおいて負荷分散性を向上させる、並列計算処理装置および並列計算処理方法を提供することができる。
さらに、本発明によれば、ＢＳＰ計算モデルをミッションクリティカルなシステムに適用可能とする、並列計算処理装置および並列計算処理方法を提供することができる。
【図面の簡単な説明】
【００２８】
【図１】ＢＳＰ計算モデルを説明するための図である。
【図２】本発明の課題である、可用性（耐障害性）の向上についての問題を、詳細に説明するための図である。
【図３】本実施形態に係る並列計算処理装置を含む並列計算処理システムの構成を示す図である。
【図４】本実施形態に係る並列計算処理装置が実行する処理の流れを示すフローチャートである。
【発明を実施するための形態】
【００２９】
次に、本発明を実施するための形態（以下、「本実施形態」という。）における、並列計算処理装置１および並列計算処理方法について説明する。
図３は、本実施形態に係る並列計算処理装置１を含む並列計算処理システム１０００の構成を示す図である。
並列計算処理システム１０００では、ネットワーク上に分散配置されることによりクラスタを構成する複数の並列計算処理装置１が相互に通信接続される。この並列計算処理装置１は、上記したＢＳＰ計算モデル等の、並列化された処理のステップ毎にインタラクション（相互作用）が生じ、それを同期しながら計算を進める計算処理を用いて、分割シミュレーション計算等を実行する装置である。なお、以下の説明においては、図１（ｂ）において示したメッシュ分割シミュレーション計算を例に説明するが、これに限定されない。
【００３０】
図３に示す並列計算処理システム１０００を構成する各並列計算処理装置１は、以下において説明する機能それぞれを一つ並列計算処理装置１が備えるものであるが、説明をより分かりやすくするため、並列計算処理装置１が、図１（ｂ）に示すようなメッシュ分割シミュレーション計算において、以下に示す３つの機能を実行する各ノードとして説明する。
１つ目の機能として説明するノード（並列計算処理装置１）は、信号を受信しその計算処理を担当するノード、つまり、図１（ｂ）においてメッシュｘを担当するノードである。このノードを、以下「ＬＣｘマスタノード１Ａ」（マスタノード）と記して説明する。
２つ目の機能として説明するノード（並列計算処理装置１）は、上記したＢＳＰのスーパーステップ２（ＳＳ２）において、計算結果（データ）の交換を行う、つまり、ステップ毎にＬＣｘマスタノード１Ａと相互にインタラクションが発生するノード（図１（ｂ）の隣接メッシュを担当するノード）である。このノードを、以下「ＬＣｘネイバノード１Ｂ）」（ネイバノード）と記して説明する。
３つ目の機能として説明するノード（並列計算処理装置１）は、ＬＣｘマスタノード１Ａに格納されるデータの複製を記憶するノードである。このノードを、以下「ＬＣｘレプリカノード１Ｃ」（レプリカノード）と記して説明する。
【００３１】
並列計算処理システム１０００においてクラスタを構成する各並列計算処理装置１は、ＬＣｘマスタノード１Ａ、ＬＣｘネイバノード１Ｂ、ＬＣｘレプリカノード１Ｃが実行する機能をそれぞれが備える。また、後記するように、ＬＣｘマスタノード１Ａが計算結果（データ）の送受信を行うＬＣｘネイバノード１Ｂは、当該ＬＣｘマスタノード１Ａに対応する１台以上の並列計算処理装置１が予め設定される。また、ＬＣｘマスタノード１Ａのデータの複製を記憶するＬＣｘレプリカノード１Ｃも、当該ＬＣｘマスタノード１Ａに対応する１台以上の並列計算処理装置１が予め設定される。
以下、並列計算処理装置１が備える各機能について詳細に説明する。
【００３２】
＜並列計算処理装置の構成＞
並列計算処理装置１は、不図示の、制御手段と、通信手段と、記憶手段とを備えるコンピュータである。
通信手段は、自身以外の他の並列計算処理装置１等との間で通信接続を行うための通信インタフェース等から構成される。
また、記憶手段は、ハードディスクやフラッシュメモリ、ＲＡＭ（Random Access Memory）等からなり、処理結果（データ）や、他の並列計算処理装置１との通信に必要となるアドレス（例えば、ＩＰアドレス）等の設定情報が格納される。
【００３３】
制御手段は、並列計算処理装置１全体の制御を司り、図３に示すように、数値計算部１０と、振分処理部２０と、データ送受信同期部３０と、データ格納処理部４０と、障害管理部５０とを含んで構成される。なお、並列計算処理装置１がＬＣｘマスタノード１Ａとして機能するときの各部の符号には「Ａ」を付し、並列計算処理装置１がＬＣｘネイバノード１Ｂとして機能するときの各部の符号には「Ｂ」を付し、並列計算処理装置１がＬＣｘレプリカノード１Ｃとして機能するときの各部の符号には「Ｃ」を付して適宜説明する。
また、この制御手段は、例えば、記憶手段に格納されたプログラムをＣＰＵ（Central Processing Unit：図示省略）がＲＡＭ（図示省略）に展開し実行することで実現される。
【００３４】
数値計算部１０は、上記したＢＳＰ計算モデルにおいて示したスーパーステップのローカル計算（ＬＣ：「ＳＳ１」）（所定の計算ステップ）を実行する。この数値計算部１０は、ＬＣｘ計算元データ取得部１１、ＬＣｘ計算部１２、ＬＣｘ計算結果出力部１３を含んで構成される。
【００３５】
ＬＣｘ計算元データ取得部１１は、ＬＣｘ（その並列計算処理装置１自身が担当するメッシュｘのローカル計算）に必要なデータセット（隣接メッシュを担当するノード（ＬＣｘネイバノード１Ｂ）すべてからのデータ）を、データ送受信同期部３０から取得する。
ＬＣｘ計算部１２は、ＬＣｘ計算元データ取得部１１が取得したデータセットを利用して計算処理を行う。
ＬＣｘ計算結果出力部１３は、ＬＣｘ計算部１２が計算した計算結果（データ）をデータ送受信同期部３０に出力する。
【００３６】
このＬＣｘ計算部１２のロジックを変更することにより、並列計算処理システム１０００において、様々な用途の計算に対応可能となる。つまり、様々なアプリケーションに対応したロジックをＬＣｘ計算部１２に設定することにより、汎用的に本システムを利用することができる。
【００３７】
振分処理部２０は、外部から受信した信号に付されたキー情報（ＬＣｘマスタノード１Ａを特定するＩＤ）に基づき、当該信号の振分先を決定し、その決定した振分先のノード（ＬＣｘマスタノード１Ａ）に、その信号を振り分ける。また、振分処理部２０は、データ送受信同期部３０の制御のもとで、ＬＣｘネイバノード１Ｂに対し、計算結果（データ）の送受信を行う。
この振分処理部２０は、データ振分部２１、データ交換部２２を含んで構成される。
【００３８】
データ振分部２１は、例えば、コンシステントハッシュ法に基づき、外部から受信した信号に付されたキー情報（ＬＣｘマスタノード１Ａを特定するＩＤ）を抽出してハッシュ値を算出することにより、ＬＣｘマスタノード１Ａとなるノードを決定する。そして、データ振分部２１は、その決定したＬＣｘマスタノード１Ａに受信した信号を送信する。
なお、図１（ｂ）に示したようなメッシュ分割シミュレーション計算においては、分割したメッシュごとにＩＤ（メッシュＩＤ）が割り振られ、そのメッシュＩＤのメッシュの処理を担当するノード（ＬＣｘマスタノード１Ａ（並列計算処理装置１））が予め設定される。そして、閉じたＩＤ空間上においてメッシュＩＤを例えば時計回りに配置しておき、信号を受信した際に、その信号に付されたキー情報から時計回りに辿った場合に最初に当たったメッシュＩＤのノード（並列計算処理装置１）が、その信号を担当するメッシュｘに対応するＬＣｘマスタノード１Ａとなる。このとき、メッシュＩＤと並列計算処理装置１のアドレス（ＩＰアドレス等）との対応表（メッシュＩＤ−ノード対応表）が予め各ノード（並列計算処理装置１）の記憶手段に記憶される。このコンシステントハッシュ法に基づく、分散処理システムでは、処理負荷に応じたノード（並列計算処理装置１）の増減設の際に、その増減設の対象となる並列計算処理装置１が保持するデータの移行処理（データの再配置）が、システム全体には及ばす一部のノード（並列計算処理装置１）に限定されるため、データ移行の処理負荷（再計算・再配置等のコスト）を軽減させ、動的な構成変更への対応を容易にすることができる。
このコンシステントハッシュ法については、「入江道生，他４名，“スケールアウトと柔軟な構成変更を実現するセッション制御サーバのクラスタモデル”，電子情報通信学会，2011年電子情報通信学会総合大会，通信講演論文集２，Ｂ−６−１１」に詳しい。
【００３９】
データ交換部２２は、データ送受信同期部３０から取得した計算結果（データ）を、ＬＣｘネイバノード１Ｂに送信する。また、データ交換部２２は、ＬＣｘネイバノード１Ｂから計算結果（データ）を受信し、データ送受信同期部３０に出力する。
なお、図１（ｂ）に示したようなメッシュ分割シミュレーション計算においては、そのＬＣｘマスタノード１Ａ（並列計算処理装置１）自身が担当するメッシュｘの隣接メッシュの情報が予め記憶手段に記憶される。具体的には、隣接メッシュのメッシュＩＤとそのメッシュＩＤに対応付けられたＬＣｘネイバノード１Ｂのアドレス（ＩＰアドレス等）の対応表（隣接メッシュ対応表）が、予めＬＣｘマスタノード１Ａ（並列計算処理装置１）の記憶手段に記憶される。データ交換部２２は、この対応表（隣接メッシュ対応表）を参照することにより、ＬＣｘネイバノード１Ｂとそのアドレス（ＩＰアドレス等）を特定し、計算結果を送信する。
【００４０】
データ送受信同期部３０は、ＬＣｘマスタノード１ＡとＬＣｘネイバノード１Ｂとの間で、数値計算部１０の計算結果（データ）の送受信等を行う。このデータ送受信同期部３０は、ネイバノードデータ送信部３１、ネイバノードデータ受信部３２、ＬＣｘ計算元データセット判定部３３、ＬＣｘ計算元データ出力部３４、ＬＣｘ計算結果取得部３５を含んで構成される。
【００４１】
ネイバノードデータ送信部３１は、ＬＣｘマスタノード１ＡとＬＣｘネイバノード１Ｂとの間で、計算結果等のデータを送信する。具体的には、並列計算処理装置１がＬＣｘマスタノード１Ａとして機能するときは、データ送受信同期部３０Ａ内のネイバノードデータ送信部３１が、振分処理部２０Ａ（データ交換部２２）を介して、ＬＣｘネイバノード１Ｂに向けて計算結果等のデータを送信する。また、並列計算処理装置１がＬＣｘネイバノード１Ｂとして機能するときは、データ送受信同期部３０Ｂ内のネイバノードデータ送信部３１が、振分処理部２０Ｂ（データ交換部２２）を介して、ＬＣｘマスタノード１Ａに向けて計算結果等のデータを送信する。
【００４２】
ネイバノードデータ受信部３２は、ＬＣｘマスタノード１ＡとＬＣｘネイバノード１Ｂとの間で、計算結果等のデータを受信する。具体的には、並列計算処理装置１がＬＣｘマスタノード１Ａとして機能するときは、データ送受信同期部３０Ａ内のネイバノードデータ受信部３２が、ＬＣｘネイバノード１Ｂから計算結果等のデータを受信する。また、並列計算処理装置１がＬＣｘネイバノード１Ｂとして機能するときは、データ送受信同期部３０Ｂ内のネイバノードデータ受信部３２が、ＬＣｘマスタノード１Ａからの計算結果等のデータを受信する。
このネイバノードデータ受信部３２は、ＬＣｘマスタノード１Ａの機能を実行する場合において、ＬＣｘネイバノード１Ｂからの計算結果（データ）を受信したときには、その計算結果（データ）をデータ格納処理部４０（４０Ａ）に出力し記憶させる。また、ネイバノードデータ受信部３２は、ＬＣｘネイバノード１Ｂの機能を実行する場合において、ＬＣｘマスタノード１Ａからの計算結果（データ）を受信したときには、その計算結果（データ）をデータ格納処理部４０（４０Ｂ）に出力し記憶させる。
【００４３】
ＬＣｘ計算元データセット判定部３３は、データ格納処理部４０（４０Ａ）に格納されるＬＣｘネイバノード１Ｂからの計算結果（データ）の格納状況を監視し、予め設定されたすべてのＬＣｘネイバノード１Ｂからの計算結果（データセット）が揃ったか否かを判定する。そして、ＬＣｘ計算元データセット判定部３３は、データセットが揃った場合に、その旨をＬＣｘ計算元データ出力部３４に通知する。また、ＬＣｘ計算元データセット判定部３３は、所定期間が経過してもデータセットが揃わない場合、つまり、タイムアウト等を契機として、その旨を障害管理部５０（５０Ａ）に通知する。
【００４４】
ＬＣｘ計算元データ出力部３４は、ＬＣｘ計算元データセット判定部３３から、データセットが揃った旨の通知を受信した場合に、その計算結果（データ）を記憶手段（不図示）から取得し数値計算部１０（１０Ａ）に出力する。
【００４５】
ＬＣｘ計算結果取得部３５は、数値計算部１０から計算結果（データ）を取得すると、その計算結果（データ）をデータ格納処理部４０に出力し記憶させる。また、ＬＣｘ計算結果取得部３５は、数値計算部１０から取得した計算結果（データ）を、ネイバノードデータ送信部３１に出力する。
【００４６】
なお、このデータ送受信同期部３０が、上記したＢＳＰ計算モデル（図１参照）において示したスーパーステップのデータ交換（「ＳＳ２」）および同期（「ＳＳ３」）を実行する。
【００４７】
データ格納処理部４０は、ＬＣｘマスタノード１ＡやＬＣｘネイバノード１Ｂが計算した計算結果（データ）を記憶手段（不図示）に格納するとともに、データの複製を作成（レプリケーション）し、ＬＣｘレプリカノード１Ｃに保存させる。このデータ格納処理部４０は、データ格納部４１、レプリケーション部４２を含んで構成される。
【００４８】
データ格納部４１は、データ送受信同期部３０（具体的には、ネイバノードデータ受信部３２やＬＣｘ計算結果取得部３５等）から計算結果であるデータを受け取り、記憶手段（不図示）に格納する。
【００４９】
レプリケーション部４２は、データ格納部４１が格納したデータ（図３のデータ１００）についての複製データを作成し、そのＬＣｘマスタノード１Ａに対応して予め設定された１つ以上のＬＣｘレプリカノード１Ｃに向けて、その複製データを送信することにより保存させる。
また、このレプリケーション部４２は、ＬＣｘレプリカノード１Ｃの機能を実行する場合において、ＬＣｘマスタノード１Ａから複製データ（データ１００）を受信すると、データ格納部４１を介して、自身の記憶手段に記憶させる。
【００５０】
レプリケーション部４２は、ＬＣｘマスタノード１Ａ（並列計算処理装置１）自身に格納したデータ１００の複製データを記憶させるＬＣｘレプリカノード１Ｃを、例えば、コンシステントハッシュ法に基づき特定する。具体的には、レプリケーション部４２は、上記した閉じたＩＤ空間上で、自身が担当するメッシュｘのメッシュＩＤから時計回りに次に位置するメッシュＩＤのノード（並列計算処理装置１）をＬＣｘレプリカノード１Ｃとして特定する。さらに、レプリケーション部４２は、時計回りにその次に位置するメッシュＩＤのノード（並列計算処理装置１）をＬＣｘレプリカノード１Ｃとして特定する。このようにして、レプリケーション部４２は、設定された冗長度に対応する数のＬＣｘレプリカノード１Ｃを特定し、複製データを送信することにより、ＬＣｘマスタノード１Ａのデータの複製データを記憶させることができる。
【００５１】
障害管理部５０は、ＬＣｘマスタノード１Ａとしての並列計算処理装置１自身の障害や、ＬＣｘネイバノード１Ｂとの間の障害、ＬＣｘレプリカノード１Ｃの障害等を監視するとともに、障害を検知した場合には、処理停止を防ぐために以下に示す処理を実行する。
【００５２】
（１）ＬＣｘマスタノード１Ａのローカル計算（ＬＣ）での障害
ＬＣｘマスタノード１Ａの障害管理部５０Ａは、ローカル計算（ＬＣ）中において、自身のノードの障害を検知した場合には、次の処理を実行する。
【００５３】
（１−１）障害管理部５０Ａは、ＬＣｘレプリカノード１ＣをＬＣｘマスタノード１Ａに昇格させ、昇格したＬＣｘマスタノード１Ａにローカル計算（ＬＣ）を実行させる。
この場合、１つ以上のＬＣｘレプリカノード１Ｃのうちのいずれか１つをＬＣｘマスタノード１Ａに昇格させる。このＬＣｘマスタノード１Ａ（昇格するＬＣｘレプリカノード１Ｃ）を決定するロジックは予め設定しておく。例えば、障害管理部５０Ａは、コンシステントハッシュ法に基づき、自身のメッシュｘのメッシュＩＤから閉じたＩＤ空間において時計回りに次に位置するメッシュＩＤのノード（ＬＣｘレプリカノード１Ｃ）を特定し、ＬＣｘマスタノード１Ａに昇格するノードとして決定する。障害管理部５０Ａは、この決定したＬＣｘレプリカノード１Ｃに、ＬＣｘマスタノード１Ａに昇格する旨の通知を送信すること等により、そのＬＣｘレプリカノード１Ｃを、ＬＣｘマスタノード１Ａに昇格させる。
【００５４】
（１−２）障害管理部５０Ａは、ＬＣｘマスタノード１Ａにおけるローカル計算（ＬＣ）と同時に、ＬＣｘレプリカノード１Ｃにおいてもローカル計算（ＬＣ）を実行させる。なお、ローカル計算（ＬＣ）を同時に実行させるＬＣｘレプリカノード１Ｃを決定するロジックは上記と同様、予め設定しておく。
これにより、例えば、障害管理部５０Ａが自身のＬＣｘマスタノード１Ａの軽微な障害を検知した場合に、予備的に並行してＬＣｘレプリカノード１Ｃにおいて、処理を実行しておくことができる。よって、ＬＣｘマスタノード１Ａがその後処理停止等に陥った場合に、即座に処理を引き継ぐことができる。
【００５５】
（１−３）障害管理部５０Ａは、ダミーデータを用いてローカル計算（ＬＣ）を数値計算部１０Ａに実行させる。
障害管理部５０Ａは、例えば、同じ処理要求（信号）に対する過去の計算結果（データ）の平均値を計算し、その平均値をダミーデータとする。このダミーデータを用いて、数値計算部１０Ａがローカル計算（ＬＣ）を実行することにより、計算精度は低下するが、並列計算処理装置１の処置停止を防ぐことができる。
【００５６】
（２）ＬＣｘネイバノード１Ｂへの処理結果（データ）送信中のＬＣｘマスタノード１Ａの障害
ＬＣｘマスタノード１Ａの障害管理部５０Ａは、ＬＣｘネイバノード１Ｂへの処理結果（データ）送信中において、ＬＣｘマスタノード１Ａに障害が発生した場合には、次の処理を実行する。
【００５７】
（２−１）障害管理部５０Ａは、ＬＣｘレプリカノード１ＣをＬＣｘマスタノード１Ａに昇格させ、昇格したＬＣｘマスタノード１Ａが、ＬＣｘネイバノード１Ｂへの計算結果（データ）の再送信を実行する。
（２−２）ＬＣｘネイバノード１Ｂのデータ送受信同期部３０Ｂ内のＬＣｘ計算元データセット判定部３３が、タイムアウト（所定の時間経過）等によりＬＣｘマスタノード１Ａからの計算結果（データ）を受信できていないと判定した旨を、障害管理部５０Ｂが受け取る。これにより、ＬＣｘネイバノード１Ｂの障害管理部５０Ｂが、ＬＣｘマスタノード１Ａからの計算結果のダミーデータを生成し、数値計算部１０Ｂに処理を続行させる。
このダミーデータは、過去にＬＣｘマスタノード１Ａから受信した計算結果（データ）の平均値でもよい。また、障害が発生したＬＣｘマスタノード１Ａ以外の並列計算処理装置１から受信したデータの平均値等をダミーデータとして利用してもよい。
【００５８】
（３）ＬＣｘネイバノード１Ｂからの処理結果（データ）受信中のＬＣｘマスタノード１Ａの障害
ＬＣｘマスタノード１Ａの障害管理部５０Ａは、ＬＣｘネイバノード１Ｂからの処理結果（データ）受信中において、ＬＣｘマスタノード１Ａに障害が発生した場合には、次の処理を実行する。
【００５９】
（３−１）障害管理部５０は、ＬＣｘレプリカノード１ＣをＬＣｘマスタノード１Ａに昇格させ、昇格したＬＣｘマスタノード１Ａが、ＬＣｘネイバノード１Ｂからの計算結果（データ）を再受信する。データの送受信は、例えば、ＰＵＳＨ型、ＰＵＬＬ型のいずれを採用してもよい。例えば、昇格したＬＣｘマスタノード１Ａが、タイムアウト等を契機として、まだ処理結果（データ）を受信していないＬＣｘネイバノード１Ｂに対し、データの再送信を要求することにより、計算結果（データ）を受信する。
【００６０】
（３−２）ＬＣｘマスタノード１Ａのデータ送受信同期部３０Ａ内のＬＣｘ計算元データセット判定部３３が、タイムアウト（所定の時間経過）等によりあるＬＣｘネイバノード１Ｂからの計算結果（データ）を受信できていないと判定した旨を、障害管理部５０Ａが受け取る。このとき、障害管理部５０Ａは、そのＬＣｘネイバノード１Ｂからの計算結果のダミーデータを生成し、数値計算部１０Ａに処理を続行させる。
このダミーデータは、過去にそのＬＣｘネイバノード１Ｂから受信した計算結果（データ）の平均値でもよいし、当該ＬＣｘネイバノード１Ｂ以外の他のＬＣｘネイバノード１Ｂから受信した計算結果（データ）の平均値等でもよい。
【００６１】
（４）ＬＣｘレプリカノード１Ｃの障害
ＬＣｘマスタノード１Ａの障害管理部５０Ａは、ＬＣｘレプリカノード１Ｃの障害を検知した場合には、正常な他の並列計算処理装置１から、新たなＬＣｘレプリカノード１Ｃを選出する。
この新たなＬＣｘレプリカノード１Ｃを決定するロジックは予め設定しておくものとする。例えば、障害管理部５０Ａは、コンシステントハッシュ法に基づき、自身のメッシュｘのメッシュＩＤから閉じたＩＤ空間において時計回りに次やその次等に位置するメッシュＩＤのノードとして決定（冗長度の対応して決定）したノード（ＬＣｘレプリカノード１Ｃ）のさらにその次に位置するメッシュＩＤのノードを、新たなＬＣｘレプリカノード１Ｃとして決定してもよい。これにより、障害管理部５０は、システム全体のとしての冗長度を回復することができる。
【００６２】
（５）ＬＣｘネイバノード１Ｂの障害
ＬＣｘネイバノード１Ｂに障害が発生した場合には、その並列計算処理装置１の障害管理部５０Ｂにより、その並列計算処理装置１のＬＣｘレプリカノード１Ｃを、ＬＣｘマスタノード１Ａとして昇格する処理が行われる（上記したＬＣｘマスタノード１Ａにおける障害対応（１−１）と同様の処理）。これにより、障害が発生したＬＣｘネイバノード１ＢのＬＣｘレプリカノード１Ｃが、ＬＣｘネイバノード１Ｂの機能を実行することができ、処理停止を防ぐことができる。
【００６３】
＜処理の流れ＞
次に、並列計算処理装置１が実行する処理の流れについて説明する。
図４は、本実施形態に係る並列計算処理装置１が実行する処理の流れを示すフローチャートである。図４においては、並列計算処理装置１がＬＣｘマスタノード１Ａである場合の処理に沿って説明するが、各並列計算処理装置１は、自身がＬＣｘマスタノード１Ａである場合の処理、ＬＣｘネイバノード１Ｂである場合の処理、ＬＣｘレプリカノード１Ｃである場合の処理のいずれも実行することができる。
また、ここでは、複数の並列計算処理装置１のいずれかが受信した信号が、その振分処理部２０により、その信号を担当するメッシュｘに対応する並列計算処理装置１（ＬＣｘマスタノード１Ａ）に振り分けられたものとして説明する。
【００６４】
まず、ＬＣｘマスタノード１Ａの振分処理部２０は、信号（データ）を受信した場合に（ステップＳ１）、コンシステントハッシュ法等に基づき、当該信号について自身が処理担当となる信号（データ）と判定し、その信号（データ）を、数値計算部１０Ａに出力する。そして、数値計算部１０Ａ（ＬＣｘ計算部１２）が、不図示の記憶手段に記憶されているデータ（各ＬＣｘネイバノード１Ｂの計算結果）を取得し、ローカル計算を実行する（ステップＳ２）。なお、初期状態において、各ＬＣｘネイバノード１Ｂの計算結果（データ）がまだ記憶手段に記憶されていない場合には、予め設定した初期値等を取得して、ローカル計算（ＬＣ）が実行される。
【００６５】
続いて、数値計算部１０ＡのＬＣｘ計算結果出力部１３が、計算結果（データ）をデータ送受信同期部３０Ａに出力する。計算結果（データ）を取得したデータ送受信同期部３０ＡのＬＣｘ計算結果取得部３５は、そのデータを、データ格納処理部４０Ａに出力する。そして、データ格納処理部４０Ａのデータ格納部４１が、当該データを記憶手段に格納する（ステップＳ３）。
【００６６】
次に、データ格納処理部４０Ａのレプリケーション部４２は、データ格納部４１が格納したデータの複製データを生成し（レプリケーション：ステップＳ４）、ＬＣｘレプリカノード１Ｃに送信することにより、その複製データをＬＣｘレプリカノード１Ｃの記憶手段に格納させる（ステップＳ５）。
【００６７】
続いて、ＬＣｘマスタノード１Ａのデータ送受信同期部３０Ａ（ネイバノードデータ送信部３１）は、数値計算部１０Ａのローカル計算の計算結果（データ）を、振分処理部２０Ａ（データ交換部２２）を介して、各ＬＣｘネイバノード１Ｂに送信する（ステップＳ６）。これにより、各ＬＣｘネイバノード１Ｂのデータ送受信同期部３０Ｂ（ネイバノードデータ受信部３２）が計算結果（データ）を受信し、記憶手段に格納する。
【００６８】
次に、各ＬＣｘネイバノード１Ｂのデータ送受信同期部３０Ｂ（ネイバノードデータ送信部３１）は、自身の数値計算部１０Ｂのローカル計算の計算結果（データ）を、振分処理部２０Ｂ（データ交換部２２）を介して、ＬＣｘマスタノード１Ａに送信する（ステップＳ７）。
【００６９】
ＬＣｘマスタノード１Ａのデータ送受信同期部３０Ａ（ネイバノードデータ受信部３２）は、ＬＣｘネイバノード１Ｂから計算結果（データ）を受信すると、データ格納処理部４０Ａに出力する。そして、データ格納処理部４０Ａのデータ格納部４１が、当該データを記憶手段（不図示）に格納する。また、データ格納処理部４０Ａのレプリケーション部４２が、ＬＣｘネイバノード１Ｂから取得した計算結果（データ）の複製データを生成し、ＬＣｘレプリカノード１Ｃに送信することにより（ステップＳ８）、その複製データをＬＣｘレプリカノード１Ｃの記憶手段に格納させる（ステップＳ９）。
このステップＳ８およびステップＳ９の処理は、ＬＣｘネイバノード１Ｂから計算結果（データ）を受信する度に実行される。これにより、各ＬＣｘネイバノード１Ｂから計算結果（データ）を受信中にＬＣｘマスタノード１Ａに障害が発生した場合においても、それまでに受信したデータをＬＣｘレプリカノード１Ｃが引継いで直ちに処理を続行させることができる。
【００７０】
次に、ＬＣｘマスタノード１Ａのデータ送受信同期部３０Ａ（ＬＣｘ計算元データセット判定部３３）は、設定されているすべてのＬＣｘネイバノード１Ｂから、計算結果（データ）を受信し記憶手段に格納したか否かを判定する。つまり、すべてのデータ（データセット）が揃ったか否かを判定する（ステップＳ１０）。そして、ＬＣｘ計算元データセット判定部３３が、所定の時間内において、すべてのデータ（データセット）が揃ったと判定した場合には（ステップＳ１０→Ｙｅｓ）、ステップＳ２に戻り、次の処理ステップに進む。一方、ＬＣｘ計算元データセット判定部３３が、所定の時間内において、すべてのデータ（データセット）が揃っていない、つまり受信できなかったデータがあると判定した場合には（ステップＳ１０→Ｎｏ）、その旨の情報を、障害管理部５０Ａに出力する。そして、障害管理部５０Ａが、該当する障害に対応する処理を実行する（ステップＳ１１）。例えば、障害管理部５０Ａは、ＬＣｘレプリカノード１ＣをＬＣｘマスタノード１Ａの昇格させることにより、処理を続行させたり、ダミーデータを利用して処理を続行させたりする等の処理を行う。そして、ステップＳ２に戻る。これにより、ＬＣｘマスタノード１Ａの処理停止を防ぐことができる。
【００７１】
以上説明した本実施形態に係る並列計算処理装置１および並列計算処理方法によれば、以下に示す顕著な効果を奏することができる。
（負荷分散性の向上）
従来のＢＳＰ計算モデルでは、複数の計算ノードでクラスタを構成して処理を行う際に、信号の振分処理がボトルネック化する等の理由により、負荷分散性を向上させるのが難しかった。しかしながら、本実施形態に係る並列計算処理装置１によれば、例えば、コンシステントハッシュ法等を用いて、信号を各計算ノードに振り分けることができる。よって、振分処理のボトルネック化を防ぐことができるとともに、並列計算処理の負荷分散性を向上させることができる。
【００７２】
（可用性（耐障害性）の向上）
従来のＢＳＰ計算モデルで問題であった、可用性（耐障害性）を高めるための、データの保護・復旧等の仕組みを、ＬＣｘレプリカノード１Ｃを設けること等により実現することができる。具体的には、ＬＣｘマスタノード１Ａが障害を検知した場合に、障害管理部５０により、ＬＣｘレプリカノード１ＣをＬＣｘマスタノード１Ａに昇格させたり、ＬＣｘレプリカノード１ＣをＬＣｘマスタノード１Ａと同時に予備的に実行させたり、ダミーデータを用いること等により、一部のノード障害が全体に波及しないようにして、処理を続行することができる。
【００７３】
（動的な構成変更への対応）
本実施形態に係る並列計算処理装置１は、信号の振分処理や、ＬＣｘレプリカノード１Ｃの決定処理等を、コンシステントハッシュ法等を用いて実行する。これにより、クラスタ構成の変更（ノードの増減設）があった場合における、ノード間の処理（データ）の引継ぎコストを抑えることができる。よって、処理負荷に応じたクラスタ規模の動的な拡大・縮小への対応が可能となる。
【００７４】
（汎用化）
本実施形態に係る並列計算処理装置１によれば、ＢＳＰ計算モデル等を採用する様々なアプリケーションを、ＬＣｘ計算部１２に適用することができる。これにより、汎用的なソリューションを提供することが可能となる。
【００７５】
このように、本実施形態に係る並列計算処理装置１および並列計算処理方法によれば、上記の効果を奏することができ、並列計算処理の負荷分散性を向上させるとともに、ＢＳＰ計算モデルをミッションクリティカルなシステムに適用することが可能となる。
【符号の説明】
【００７６】
１      並列計算処理装置
１Ａ    ＬＣｘマスタノード（マスタノード）
１Ｂ    ＬＣｘネイバノード（ネイバノード）
１Ｃ    ＬＣｘレプリカノード（レプリカノード）
１０    数値計算部
１１    ＬＣｘ計算元データ取得部
１２    ＬＣｘ計算部
１３    ＬＣｘ計算結果出力部
２０    振分処理部
２１    データ振分部
２２    データ交換部
３０    データ送受信同期部
３１    ネイバノードデータ送信部
３２    ネイバノードデータ受信部
３３    ＬＣｘ計算元データセット判定部
３４    ＬＣｘ計算元データ出力部
３５    ＬＣｘ計算結果取得部
４０    データ格納処理部
４１    データ格納部
４２    レプリケーション部
５０    障害管理部
１０００  並列計算処理システム
【図１】
0006450330.tif 000002
【図２】
0006450330.tif 000003
【図３】
0006450330.tif 000004
【図４】
0006450330.tif 000005