(57)【要約】【課題】管理サーバの負担を重くせずに分散処理の進行状況を細かく監視しつつ計算処理の遅れを検出できる分散同期処理システムを提供する。【解決手段】分散同期処理システムは、並列に処理を行う複数の処理サーバ３０と、処理サーバ３０上で動作する複数の分散処理部２０と、対象とする計算処理に必要な複数の分散処理部２０を複数の処理サーバ３０に対して割り当てる管理サーバと、を有し、分散処理部２０は、所定単位に区分された計算処理を行う数値計算部２１と、他分散処理部２０との間でメッセージを送受信するメッセージ送受信部２２と、他分散処理部２０から送信される計算結果メッセージの受信時刻を監視する受信時刻監視部２３と、を備え、メッセージ送受信部２２は、隣接した他分散処理部２０から計算結果メッセージを所定時間内に受信できない場合、遅れ被疑メッセージを送信する。【選択図】図２
2018032346.tif 000002
【特許請求の範囲】
【請求項１】
並列に処理を行う複数の処理サーバと、前記処理サーバ上で動作する複数の分散処理部と、対象とする計算処理に必要な複数の前記分散処理部を複数の前記処理サーバに対して割り当てる管理サーバと、を有する分散同期処理システムであって、
前記分散処理部は、
所定単位に区分された計算処理を行う数値計算部と、
他分散処理部との間で計算結果メッセージを含むメッセージを送受信するメッセージ送受信部と、
他分散処理部から送信される計算結果メッセージの受信時刻を監視する受信時刻監視部と、を備え、
前記メッセージ送受信部は、隣接した他分散処理部から前記計算結果メッセージを所定時間内に受信できない場合、前記計算結果メッセージの送達が遅れていることを示す遅れ被疑メッセージを送信する、ことを特徴とする分散同期処理システム。
【請求項２】
前記分散処理部は、通知される前記遅れ被疑メッセージの受信量を管理する遅れ被疑メッセージ受信量管理部をさらに備え、
前記処理サーバは、自処理サーバ上で動作する複数の分散処理部に対して通知される前記遅れ被疑メッセージの受信量を監視し、自処理サーバ上の特定の分散処理部のみが前記遅れ被疑メッセージの受信量が所定値よりも多い場合、当該分散処理部の処理負荷が大きいと判定し、自処理サーバ上で動作する複数の分散処理部に対して通知される前記遅れ被疑メッセージの受信量がそれぞれ所定値よりも多い場合、自処理サーバの処理負荷が大きいと判定する負荷判定部を備える請求項１に記載の分散同期処理システム。
【請求項３】
前記処理サーバは、自処理サーバ上で動作する特定の分散処理部の処理負荷が大きいと判定された場合、当該特定の分散処理部についての委譲要求を前記管理サーバに通知する負荷委譲要求部をさらに備え、
前記管理サーバは、前記委譲要求が通知されると、前記特定の分散処理部を、前記委譲要求を通知した処理サーバよりも処理能力の高い処理サーバに割り当てる請求項２に記載の分散同期処理システム。
【請求項４】
前記処理サーバは、自処理サーバの処理負荷が大きいと判定された場合、自処理サーバ上で動作する複数の分散処理部のうちの一部についての委譲要求を前記管理サーバに通知する負荷委譲要求部をさらに備え、
前記管理サーバは、前記委譲要求が通知されると、前記委譲要求を通知した処理サーバ上で動作する複数の分散処理部のうちの一部を、他処理サーバに割り当てる請求項２に記載の分散同期処理システム。
【請求項５】
前記処理サーバは、自処理サーバ上で動作する特定の分散処理部の処理負荷が大きいと判定された場合、又は、自処理サーバの処理負荷が大きいと判定された場合、処理負荷調整要求を前記管理サーバに通知する負荷調整部をさらに備え、
前記管理サーバは、前記処理負荷調整要求が通知されると、既に複数の前記処理サーバに対して割り当てた全ての前記分散処理部を、前記処理負荷調整要求を通知した処理サーバに関する処理負荷を低減した新たな配置で、複数の前記処理サーバに対して再度割り当てる請求項２に記載の分散同期処理システム。
【請求項６】
前記分散処理部は、前記遅れ被疑メッセージを受信したときに、他分散処理部から送信される計算結果メッセージの待機状態である場合、前記遅れ被疑メッセージの受信量をカウントさせずに、受信した前記遅れ被疑メッセージを当該他分散処理部に転送する遅れ被疑メッセージ転送処理部をさらに備える請求項２から請求項５のいずれか一項に記載の分散同期処理システム。
【請求項７】
前記分散処理部は、前記遅れ被疑メッセージの受信時に、受信完了を示す信号を送信側に返させ、前記受信完了を示す信号が返ってこない場合、予め定められた回数だけ前記遅れ被疑メッセージを再送させ、前記遅れ被疑メッセージを前記回数だけ再送させても前記受信完了を示す信号が返ってこない場合、故障として検出する故障検出部をさらに備える請求項１から請求項６のいずれか一項に記載の分散同期処理システム。
【請求項８】
並列に処理を行う複数の処理サーバと、前記処理サーバ上で動作する複数の分散処理部と、対象とする計算処理に必要な複数の前記分散処理部を複数の前記処理サーバに対して割り当てる管理サーバと、を有する分散同期処理システムによる分散同期処理方法であって、
前記分散処理部は、
所定単位に区分された計算処理を行う数値計算ステップと、
少なくとも１つの他分散処理部との間で計算結果メッセージを含むメッセージを送受信するメッセージ送受信ステップと、
他分散処理部から送信される計算結果メッセージの受信時刻を監視する受信時刻監視ステップと、を有し、
前記メッセージ送受信ステップは、隣接した他分散処理部から前記計算結果メッセージを所定時間内に受信できない場合、前記計算結果メッセージの送達が遅れていることを示す遅れ被疑メッセージを送信する、ことを特徴とする分散同期処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分散処理システムに係り、特に、同期型の分散処理システムである分散同期処理システム及びその方法に関する。
【背景技術】
【０００２】
複数のコンピュータを有する分散処理システムのフレームワークとして、非特許文献１にはマップレデュース（ＭａｐＲｅｄｕｃｅ）が開示されている。但し、マップレデュースは、ある処理の結果を次の処理で利用するようなイテレーティブな処理には不向きであり、この種の処理には、非特許文献２に開示されているＢＳＰ（bulk-synchronous parallel）が適していると考えられる。
【０００３】
ＢＳＰでは、スーパーステップ（以下、ＳＳと表記する場合がある)という処理単位を繰り返し実行することにより、分散環境でのデータ処理を実行する。図１１に示すように、スーパーステップＳＳ１、ＳＳ２、…は、フェーズＰＨ１として「ローカル計算（ＬＣ：Local computation）」、フェーズＰＨ２として「データ交換（ＣＯＭ：Communication）」、フェーズＰＨ３として「同期（ＳＹＮＣ：Synchronization）」の３つのフェーズＰＨ１〜ＰＨ３を有している。つまり、ＢＳＰを適用した計算システムは同期型の分散処理システム（分散同期処理システム）である。
【０００４】
具体的には、図１１に示すように、複数のノード（ノード１〜ノード４）は、担当する計算処理に用いるデータが振り分けられると、最初のスーパーステップＳＳ１のフェーズＰＨ１において、そのデータについての計算処理、すなわち、ローカル計算（ＬＣ）を実行する。続いて、フェーズＰＨ２において、各ノードが保持しているローカル計算の結果であるデータについて、ノード間でのデータ交換を実行する。次に、フェーズＰＨ３において、同期処理を行う、より詳細には、すべてのノード間でのデータ交換の終了を待つ。そして、スーパーステップＳＳ１の処理（ＰＨ１〜ＰＨ３）が終了すると、各ノードはその計算結果を保持した上で、次のスーパーステップＳＳ２の処理へと進む。以下、同様にして、複数のスーパーステップが繰り返される。
【０００５】
従来、分散同期処理システムのフレームワークでは、master／workerモデルを採用しており、システムを管理する管理サーバ（master）が、対象とする計算処理の全体を所定単位に細分化した個々の計算処理を処理サーバ（worker）に割り振ることとしている。
【０００６】
非特許文献３には、ＢＳＰを適用した例として、Ｐｒｅｇｅｌという分散処理フレームワークが開示されている。Ｐｒｅｇｅｌにおいては、全体の処理内容をグラフＧ＝（Ｖ，Ｅ）として表現し、これをＢＳＰに落とし込んで実行することができる。ここで、Ｖは頂点（以下、vertexともいう）の集合であり、各頂点は、細分化された個々の処理内容に対応する。また、Ｅは有向辺（以下、edgeともいう）の集合であり、有向辺は、例えば頂点のもつスコアを計算する場合、各頂点間の情報伝達を行う経路に対応する。なお、交通シミュレーションのように、有向辺の上の車を動かしたり、混雑状況を計算したりする場合には、有向辺も計算対象となる。
【０００７】
前記グラフＧを例えば、交通システムの計算シミュレーションへ適用する場合、グラフＧにおける頂点を交差点、有向辺を通行方向が決まった道路として交通量をモデリングする。この場合、管理サーバ（master）が、各処理サーバ（worker）に対して１以上のＮ個の頂点をそれぞれ割り振り、処理サーバ（worker）単位で計算処理の進行状況を管理する。そして、処理サーバ（worker）において、担当する各頂点（vertex）に対応したＮ個の分散処理部（仮想マシン）が個々の計算処理を実行する。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】Dean, J., et al., ”MapReduce: Simplified Data Processing on Large Clusters,” OSDI '04, 2004, p.137-149
【非特許文献２】Valiant, L., et al., ”A bridging model for parallel computation,” Communications of the ACM, 1990, vol.33, No.8, p.103-111
【非特許文献３】Malewicz, G., et al., ”Pregel: A System for Large-Scale Graph Processing,” Proc. of ACM SIGMOD, 2010, p.136-145
【発明の概要】
【発明が解決しようとする課題】
【０００９】
個々の計算処理が遅れる原因を検出したり、検出した原因に応じて適切に対処したりすれば、計算対象とするシステムの挙動をより短時間にシミュレートすることが可能である。そのために、管理サーバ（master）がより細かく計算処理の進行状況を管理することが望まれる。しかしながら、管理サーバに対して、計算処理の進行状況を従来より細かく管理する機能を付加すると、管理サーバの負荷が重くなり、大規模な計算システムのシミュレーションには対応することができなくなってしまう問題がある。
【００１０】
そこで、本発明では、前記した問題を解決し、管理サーバの負担を重くせずに分散処理の進行状況を細かく監視しつつ計算処理の遅れを検出できる分散同期処理システム及びその方法を提供することを課題とする。
【課題を解決するための手段】
【００１１】
前記した課題を解決するため、本発明に係る分散同期処理システムは、並列に処理を行う複数の処理サーバと、前記処理サーバ上で動作する複数の分散処理部と、対象とする計算処理に必要な複数の前記分散処理部を複数の前記処理サーバに対して割り当てる管理サーバと、を有する分散同期処理システムであって、前記分散処理部が、所定単位に区分された計算処理を行う数値計算部と、他分散処理部との間で計算結果メッセージを含むメッセージを送受信するメッセージ送受信部と、他分散処理部から送信される計算結果メッセージの受信時刻を監視する受信時刻監視部と、を備え、前記メッセージ送受信部が、隣接した他分散処理部から前記計算結果メッセージを所定時間内に受信できない場合、前記計算結果メッセージの送達が遅れていることを示す遅れ被疑メッセージを送信する、ことを特徴とする。
【００１２】
また、前記した課題を解決するため、本発明に係る分散同期処理方法は、並列に処理を行う複数の処理サーバと、前記処理サーバ上で動作する複数の分散処理部と、対象とする計算処理に必要な複数の前記分散処理部を複数の前記処理サーバに対して割り当てる管理サーバと、を有する分散同期処理システムによる分散同期処理方法であって、前記分散処理部が、所定単位に区分された計算処理を行う数値計算ステップと、少なくとも１つの他分散処理部との間で計算結果メッセージを含むメッセージを送受信するメッセージ送受信ステップと、他分散処理部から送信される計算結果メッセージの受信時刻を監視する受信時刻監視ステップと、を有し、前記メッセージ送受信ステップが、隣接した他分散処理部から前記計算結果メッセージを所定時間内に受信できない場合、前記計算結果メッセージの送達が遅れていることを示す遅れ被疑メッセージを送信する、ことを特徴とする。
【００１３】
かかる構成の分散同期処理システム、及び、かかる手順の分散同期処理方法によれば、分散処理部は、所定単位に区分された計算処理を行い、他分散処理部との間でその計算結果メッセージを送受信する。その際に、各分散処理部は、隣接した他分散処理部から送信される計算結果メッセージの受信時刻を互いに監視し、所定時間内に受信できない場合、遅れ被疑メッセージを送信する。したがって、分散処理部が、計算結果メッセージの受信時刻を互いに自律的に監視することで分散処理の進行状況を細かく監視しつつ計算処理の遅れを検出することができる。
【００１４】
また、本発明に係る分散同期処理システムは、前記分散処理部が、通知される前記遅れ被疑メッセージの受信量を管理する遅れ被疑メッセージ受信量管理部をさらに備え、前記処理サーバが、自処理サーバ上で動作する複数の分散処理部に対して通知される前記遅れ被疑メッセージの受信量を監視し、自処理サーバ上の特定の分散処理部のみが前記遅れ被疑メッセージの受信量が所定値よりも多い場合、当該分散処理部の処理負荷が大きいと判定し、自処理サーバ上で動作する複数の分散処理部に対して通知される前記遅れ被疑メッセージの受信量がそれぞれ所定値よりも多い場合、自処理サーバの処理負荷が大きいと判定する負荷判定部を備えることとしてもよい。
かかる構成よれば、分散同期処理システムは、処理サーバで管理する分散処理部が受信する遅れ被疑メッセージの受信量に基づいて、処理サーバが遅れる原因が、特定の分散処理部の処理が重いことが原因であるのか、処理サーバが過負荷であることが原因であるのか、その原因を切り分けることができる。
【００１５】
また、本発明に係る分散同期処理システムは、前記処理サーバが、自処理サーバ上で動作する特定の分散処理部の処理負荷が大きいと判定された場合、当該特定の分散処理部についての委譲要求を前記管理サーバに通知する負荷委譲要求部をさらに備え、前記管理サーバが、前記委譲要求が通知されると、前記特定の分散処理部を、前記委譲要求を通知した処理サーバよりも処理能力の高い処理サーバに割り当てることとしてもよい。
例えば、処理能力の高い処理サーバと低い処理サーバが混在した分散処理システムでは、処理能力の低い処理サーバは処理が遅れる傾向にある。このように処理サーバの性能にバラツキがある場合であっても、かかる構成の分散同期処理システムによれば、ある処理サーバの処理が遅れる原因が、当該処理サーバ上で動作する特定の分散処理部の処理が重いことが原因である場合に、その特定の分散処理部を、処理能力の高い処理サーバに委譲することで委譲元の処理サーバの負荷を低減し、負荷を均一化することができる。
【００１６】
また、本発明に係る分散同期処理システムは、前記処理サーバが、自処理サーバの処理負荷が大きいと判定された場合、自処理サーバ上で動作する複数の分散処理部のうちの一部についての委譲要求を前記管理サーバに通知する負荷委譲要求部をさらに備え、前記管理サーバが、前記委譲要求が通知されると、前記委譲要求を通知した処理サーバ上で動作する複数の分散処理部のうちの一部を、他処理サーバに割り当てることとしてもよい。
例えば、ＢＳＰで繰り返し行われる毎回のスーパーステップでは、処理サーバは、複数のタスク処理を受けている状態にある。このように処理サーバが、あるスーパーステップで多数の分散処理部を受けている場合であっても、かかる構成の分散同期処理システムによれば、ある処理サーバの処理が遅れる原因が、処理能力によるものではなく分散処理部が多いことによって処理サーバが過負荷の状態になっている場合に、その一部の分散処理部を、他の処理サーバに委譲することで委譲元の処理サーバの負荷を低減し、負荷を均一化することができる。
【００１７】
また、本発明に係る分散同期処理システムは、前記処理サーバが、自処理サーバ上で動作する特定の分散処理部の処理負荷が大きいと判定された場合、又は、自処理サーバの処理負荷が大きいと判定された場合、処理負荷調整要求を前記管理サーバに通知する負荷調整部をさらに備え、前記管理サーバが、前記処理負荷調整要求が通知されると、既に複数の前記処理サーバに対して割り当てた全ての前記分散処理部を、前記処理負荷調整要求を通知した処理サーバに関する処理負荷を低減した新たな配置で、複数の前記処理サーバに対して再度割り当てることとしてもよい。
かかる構成によれば、分散同期処理システムは、処理サーバが遅れる原因が、特定の分散処理部の処理が重いことが原因である場合や、処理サーバが過負荷である場合に、適切に対処することができる。
【００１８】
また、本発明に係る分散同期処理システムは、前記分散処理部は、前記遅れ被疑メッセージを受信したときに、他分散処理部から送信される計算結果メッセージの待機状態である場合、前記遅れ被疑メッセージの受信量をカウントさせずに、受信した前記遅れ被疑メッセージを当該他分散処理部に転送する遅れ被疑メッセージ転送処理部をさらに備えることとしてもよい。
かかる構成によれば、遅れの影響範囲が広いほど遅れ被疑メッセージの受信量が増大し、いち早く遅れが確定されることになる。これにより、分散同期処理システムは、分散処理部の遅れを正確に検出する精度を向上させることができる。
【００１９】
また、本発明に係る分散同期処理システムは、前記分散処理部が、前記遅れ被疑メッセージの受信時に、受信完了を示す信号を送信側に返させ、前記受信完了を示す信号が返ってこない場合、予め定められた回数だけ前記遅れ被疑メッセージを再送させ、前記遅れ被疑メッセージを前記回数だけ再送させても前記受信完了を示す信号が返ってこない場合、故障として検出する故障検出部をさらに備えることとしてもよい。
かかる構成によれば、分散同期処理システムは、処理の遅れの原因が故障である場合に適切に対処することができる。
【発明の効果】
【００２０】
本発明によれば、管理サーバの負担を重くせずに分散処理の進行状況を細かく監視しつつ計算処理の遅れを検出することができる。
【図面の簡単な説明】
【００２１】
【図１】本発明の実施形態に係る分散同期処理システムを模式的に示す構成図である。
【図２】図１の処理サーバ及び分散処理部の構成例を示す機能ブロック図である。
【図３】対象とする計算処理を交通システムに適用する場合のグラフの説明図である。
【図４】分散処理部に対応した頂点（vertex）の一部の構成要素を模式的に示す説明図である。
【図５】分散処理部に対応した頂点（vertex）の構成要素の説明図である。
【図６】本発明の実施形態に係る分散同期処理システムの全体の動作を示すシーケンス図である。
【図７】処理サーバが担当する分散処理部がスーパーステップで時系列に実行する基本動作を示す模式図である。
【図８】本発明の実施形態に係る分散同期処理システムの動作説明図であって、（ａ）は計算対象のグラフ、（ｂ）はグラフ上に重ねた遅れ被疑メッセージを示している。
【図９】（ａ）、（ｂ）は処理サーバ毎の進行状況の具体例をそれぞれ示す模式図である。
【図１０】本発明の他の実施形態に係る分散同期処理システムの動作説明図であって、（ａ）は計算対象のグラフ、（ｂ）はグラフ上に重ねた遅れ被疑メッセージを示している。
【図１１】従来技術であるＢＳＰ計算モデルの説明図である。
【発明を実施するための形態】
【００２２】
以下、本発明の分散同期処理システム及び分散同期処理方法について図面を参照して詳細に説明する。
（第１実施形態）
［分散同期処理システムの構成］
図１に示すように、分散同期処理システム１は、管理サーバ１０と、管理サーバ１０にそれぞれ接続され並列に処理を行う複数の処理サーバ３０と、処理サーバ３０上で動作する複数の分散処理部２０（仮想マシン）と、を備えている。
【００２３】
管理サーバ１０及び処理サーバ３０は、ＣＰＵ（Central Processing Unit）、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、ＨＤＤ（Hard Disk Drive）等、一般的なコンピュータとしてのハードウエアを備えており、ＨＤＤには、ＯＳ（Operating System）、アプリケーションプログラム、各種データ等が格納されている。ＯＳおよびアプリケーションプログラムは、ＲＡＭに展開され、ＣＰＵによって実行される。なお、図２において、分散処理部２０及び処理サーバ３０の内部は、ＲＡＭに展開されたアプリケーションプログラム等によって実現される機能を、ブロックとして示している。
【００２４】
管理サーバ１０は、システム全体を管理するmasterとして機能する。管理サーバ１０は、対象とする計算処理の全体を所定単位に細分化した複数の計算処理を、workerとして機能する処理サーバ３０にそれぞれ割り振る。個々の計算処理には、データ入力、計算、メッセージの送受信等が含まれる。並列に処理を行う複数の処理サーバ３０上では、個々の計算処理にそれぞれ対応した複数の分散処理部２０が動作する。対象とする計算処理をグラフＧ＝（Ｖ，Ｅ）として表現したときに、この計算処理に必要な個々の計算処理は、グラフ中の個々の頂点（vertex）として表現される。つまり、分散処理部２０は頂点（vertex）として機能する。
【００２５】
管理サーバ１０は、対象とする計算処理に必要な複数の分散処理部２０を複数の処理サーバ３０に対して割り当てるものである。管理サーバ１０は、各処理サーバ３０に共通のスーパーステップの進行状況を管理する。管理サーバ１０は、必要に応じて、グラフトポロジを更新する。例えば、グラフ上の頂点の増減がある場合や、有向辺の増減がある場合にグラフトポロジを更新する。
【００２６】
分散処理部２０は、図２に示すように、数値計算部２１と、メッセージ送受信部２２と、受信時刻監視部２３と、遅れ被疑メッセージ受信量管理部２４と、を備えている。なお、遅れ被疑メッセージ転送処理部２５Ｂ、及び故障検出部２６Ｃは、別の実施形態の構成であり、その説明については後記する。
【００２７】
数値計算部２１は、所定単位に区分された計算処理を行うものである。この処理は、図１１を参照して説明したＢＳＰモデルのフェーズＰＨ１としてのローカル計算（ＬＣ：Local computation）に相当する。
【００２８】
メッセージ送受信部２２は、他分散処理部２０との間で計算結果メッセージを含むメッセージを送受信するものである。この処理は、図１１を参照して説明したＢＳＰモデルのフェーズＰＨ２としてのデータ交換（ＣＯＭ：Communication）に相当する。
本実施形態では、メッセージ送受信部２２は、隣接した他分散処理部２０から計算結果メッセージを所定時間内に受信できない場合、遅れ被疑メッセージを送信することとした。遅れ被疑メッセージは、計算結果メッセージの送達が遅れていることを示すメッセージである。メッセージ送受信部２２は、例えば、隣接した他分散処理部２０に対して、遅れ被疑メッセージを通知する。
【００２９】
受信時刻監視部２３は、他分散処理部２０から送信される計算結果メッセージの受信時刻を監視するものである。受信時刻監視部２３は、計算結果メッセージの受信時刻が所定の基準を超える他分散処理部２０は、遅れていると判定する。なお、具体例については後記する。
【００３０】
遅れ被疑メッセージ受信量管理部２４は、自分散処理部２０に通知される遅れ被疑メッセージの受信量を管理するものである。後記するように、この受信量は、当該分散処理部２０を担当する処理サーバ３０によって適宜参照され、当該処理サーバ３０又は当該分散処理部２０の負荷を判定するために用いられる。
【００３１】
処理サーバ（worker）３０は、図２に示すように、仮想化制御部３１と、負荷判定部３２と、を備えている。なお、負荷委譲要求部３３Ｄ、及び負荷調整部３３Ｅは、別の実施形態の構成であり、その説明については、後記する。
【００３２】
仮想化制御部３１は、仮想化技術に基づき、処理サーバ３０上に仮想化プラットホームを構築し、複数の分散処理部２０（仮想マシン）を配置する制御を行う。
【００３３】
負荷判定部３２は、自処理サーバ３０上で動作する複数の分散処理部２０に対して通知される遅れ被疑メッセージの受信量を監視するものである。
負荷判定部３２は、ある分散処理部２０に対して通知された遅れ被疑メッセージの受信量が所定の閾値を超えると、その遅れ被疑メッセージの通知を受けた分散処理部２０に関して処理の遅れを確定する。処理の遅れが確定した分散処理部２０に関しては、後記するように、遅れの原因を検出したり、さらに、検出した原因に対処したりすることが可能となる。
【００３４】
なお、遅れ被疑メッセージの受信量が所定の閾値を超えていない分散処理部２０の場合、遅れ被疑メッセージを送信した他分散処理部２０にとっては計算結果メッセージの送達が遅れているものの、分散同期処理システム１にとっては、当該分散処理部２０は処理が遅れていることにはならない。
【００３５】
［交通システムのシミュレーション］
次に、この分散同期処理システム１にて対象とする計算処理の具体例として、交通システムのシミュレーションについて説明する。対象とする計算処理をグラフＧ＝（Ｖ，Ｅ）として表現したときに、図３に示すように、各交差点が頂点（vertex）ｖ1〜ｖ4に対応付けられ、各交差点を結ぶ道路が有向辺（edge）ｅ1〜ｅ6に対応付けられている。ここで、有向辺は一方通行であり、双方向の道路は２つの有向辺に対応付けられる。ある頂点から見て、車両が出てゆく方向の有向辺を、出力辺（以下、outgoing edgeともいう）と呼び、車両が流入する方向の有向辺を、入力辺（以下、incoming edgeともいう）と呼ぶ。例えば、図３において、頂点ｖ2から頂点ｖ1を見ると、有向辺ｅ1は入力辺であり、有向辺ｅ2は出力辺である。逆に、頂点ｖ1から頂点ｖ2を見ると、有向辺ｅ1は出力辺であり、有向辺ｅ2は入力辺である。
【００３６】
＜頂点（vertex）の構成＞
図１及び図２に示す分散処理部２０は、前記したように、頂点（vertex）として機能する。この節では、頂点をvertexと呼び、vertexの構成について、図４及び図５を参照して説明する。図４は、グラフ上のvertexを模式的に示す説明図であり、図５は、vertexの構成要素の説明図である。なお、図４には、vertexの構成要素の一部（図５の一部）を図示している。
【００３７】
また、この節では、２つの有向辺をoutgoing edge，incoming edgeと呼ぶ。さらに、スーパーステップのステップ数のことを、ｎ（自然数）を用いて表す。スーパーステップにおいて現在のステップ数を単にステップｎと呼び、また、その直前のステップ数を、単にステップｎ−１と呼ぶ
例えば、現在のステップｎにおいて、vertex IDが１であるvertexの構成要素は、図４の実線で表されている部分であり、ｖ1,nと、ｅ1,3,nと、ｅ1,4,nと、ｍ2,1,n-1と、ｍ3,1,n-1と、ｍ2,1,nと、を備えている。
【００３８】
ここで、ｖ1,nは、現在のステップｎにおいてvertex IDが１であるvertexの状態を表す。
ｅ1,3,nは、現在のステップｎにおいてvertex IDが１であるvertexから、vertex IDが３であるvertexへのoutgoing edgeの状態を表す。
ｅ1,4,nは、現在のステップｎにおいてvertex IDが１であるvertexから、vertex IDが４であるvertexへのoutgoing edgeの状態を表す。
ｍ2,1,n-1は、前回ステップｎ−１において、vertex IDが２であるvertexから、vertex IDが１であるvertexへ送られたメッセージを表す。
ｍ3,1,n-1は、前回ステップｎ−１において、vertex IDが３であるvertexから、vertex IDが１であるvertexへ送られたメッセージを表す。なお、vertex IDが１であるvertexに関して、ｍ2,1,n-1及びｍ3,1,n-1はincomingメッセージであり、現在のステップｎにおいて、一つ前のステップ（ｎ−１）用のバッファＭin,n-1に保持されている。
ｍ2,1,nは、現在のステップｎにおいて、vertex IDが２であるvertexから、vertex IDが１であるvertexへ送られたメッセージを表す。なお、vertex IDが１であるvertexに関して、ｍ2,1,nはincomingメッセージであり、現在のステップｎにおいて、現在のステップ（ｎ）用のバッファＭin,nに保持されている。
【００３９】
なお、図４は、メッセージ送信の遷移の途中等であってスナップショットのようなある瞬間を模式的に示している。また、図４において破線で示した構成要素は、vertex IDが２，３，４であるvertexの構成要素の一部である。
ｖ2,nは、現在のステップｎにおいてvertex IDが２であるvertexの状態を表す。
ｖ3,nは、現在のステップｎにおいてvertex IDが３であるvertexの状態を表す。
ｖ4,nは、現在のステップｎにおいてvertex IDが４であるvertexの状態を表す。
ｍ1,3,n-1は、前回ステップｎ−１において、vertex IDが１であるvertexから、vertex IDが３であるvertexへ送られたメッセージを表す。
ｍ1,4,n-1は、前回ステップｎ−１において、vertex IDが１であるvertexから、vertex IDが４であるvertexへ送られたメッセージを表す。
【００４０】
図５に示すように、vertexは、図４に示した構成要素以外に、現在のステップｎにおける状態フラグＳnと、次のステップｎ＋１における状態フラグＳn+1と、計算・送信処理ｆと、を備えている。
現在のステップｎにおける状態フラグＳnは、現在のステップｎにおいてvertex（分散処理部２０）が計算処理をしていればactiveであり、計算処理を完了するとinactiveになる。
次のステップｎ＋１における状態フラグＳn+1は、次のステップｎ＋１においてvertex（分散処理部２０）が計算処理をする予定であればactiveであり、計算処理をしない予定であればinactiveになる。
【００４１】
計算・送信処理ｆは、スーパーステップ毎に行われる。現在のステップｎにおける計算・送信処理はｆnとなり、次のステップｎ＋１における計算・送信処理はｆn+1となる。例えば、現在のステップｎにおける計算・送信処理ｆnは、現在のステップｎにおけるvertexの状態、現在のステップｎにおけるoutgoing edgeの状態、及び前回ステップｎ−１におけるincomingメッセージをパラメータとして計算を行うことで、vertexの状態とoutgoing edgeの状態とを更新すると共に、計算結果メッセージを隣接vertexに送信するものである。このとき、前回ステップｎ−１におけるincomingメッセージは、その前回ステップｎ−１において「現在のステップ用のバッファ」に保持されているが、次のステップ、すなわち現在のステップｎでは、「一つ前のステップ用のバッファ」に移されて保持され、現在のステップｎにおける計算・送信処理ｆnのために用いられた後、廃棄される。
【００４２】
本実施形態のように交通システムの計算シミュレーションへ適用する場合、vertexの状態とは、例えば交差点内の信号の色（赤・黄・青）の状態を表す。
また、outgoing edgeの状態とは、道路内の車両の動き（車両の台数や、その台数における車両の平均速度）を表す。
また、incomingメッセージは、何時にどれだけの車両が入ってきたかといった情報を表す。
【００４３】
なお、図５において、outgoing edgeの状態（ｅ）と、そのoutgoing edgeの状態の集合（Ｅ）とは、アルファベットの小文字と大文字で区別している。また、図５において、incomingメッセージ（ｍ）と、それを格納するバッファ（Ｍ）とは、アルファベットの小文字と大文字で区別している。
【００４４】
［分散同期処理システムの動作］
次に、本発明の実施形態に係る分散同期処理システム１の動作について説明する。
＜全体動作＞
まず、分散同期処理システム１の全体の動作について図６を参照して説明する。
以下では、簡単のため、分散同期処理システム１は、２台の処理サーバ３０（worker1、worker2）を備えるものとして説明する。また、以下の説明におけるステップＳとは、全体動作における処理の流れを示す工程を意味するものである。
【００４５】
まず、管理サーバ（master）１０は、各処理サーバ３０に処理（分散処理部２０）を割り振る（ステップＳ１０１）。
これにしたがって、処理サーバ３０は、担当する分散処理部２０（vertex）のスーパーステップを実行する（ステップＳ１０２）。なお、この工程の詳細については後記する。
そして、処理サーバ３０は、担当する全ての分散処理部２０（vertex）の処理が完了したら、次のスーパーステップにおける各vertexの状態フラグ（active/inactive）を管理サーバ１０に報告する（ステップＳ１０３）。
【００４６】
管理サーバ１０は、全処理サーバ３０（worker1、worker2）から報告を受けると、自ら記憶管理しているスーパーステップのステップ数を＋１増加して更新する（ステップＳ１０４）。なお、管理サーバ１０は、必要な場合、グラフトポロジを更新する（ステップＳ１０５）。そして、管理サーバ１０は、次のスーパーステップへ移行するように各workerに指示する（ステップＳ１０５）。以降、分散同期処理システム１は、スーパーステップのステップ数を進めた上で、前記したステップＳ１０２〜ステップＳ１０６を繰り返す。
【００４７】
＜分散処理部の基本動作＞
次に、処理サーバ３０が担当する分散処理部２０がスーパーステップで時系列に実行する基本動作について図７を参照して説明する。
以下では、簡単のため、図８（ａ）に示すグラフＧを計算対象のグラフとする。また、グラフＧ上の頂点を符号ｖ1〜ｖ6で識別して説明する。また、管理サーバ１０は、グラフＧの頂点ｖ1〜ｖ3をworker1の担当として割り当て、頂点ｖ4〜ｖ6をworker2の担当として割り当て、各頂点ｖ1〜ｖ6に分散処理部２０がそれぞれ対応付けられていることとする。
【００４８】
スーパーステップ１では、各頂点ｖ1〜ｖ6は、図７において右下がりのハッチングで示すローカル計算（フェーズＰＨ１：図１１参照）をそれぞれ実行する。この処理は、図２に示す分散処理部２０の数値計算部２１が、所定単位に区分された計算処理を行うものである（数値計算ステップ）。
【００４９】
本実施形態のように交通システムの計算シミュレーションへ適用する場合、この数値計算ステップ（ローカル計算）では、例えば、所定時間内における、各頂点ｖ1〜ｖ6に対応付けられている交差点内の信号の色（赤・黄・青）や車両の動き等と、各頂点ｖ1〜ｖ6に接続されているoutgoing edgeに対応する道路内の車両の動き（車両の台数や平均速度）とをシミュレートする。
【００５０】
また、このスーパーステップ１では、各頂点ｖ1〜ｖ6は、図７において縦縞のハッチングで示すデータ交換（フェーズＰＨ２：図１１参照）をそれぞれ実行する。この処理は、図２に示す分散処理部２０のメッセージ送受信部２２が、他分散処理部２０との間で計算結果メッセージを含むメッセージを送受信するものである（メッセージ送受信ステップ）。
各処理サーバ３０は、頂点（vertex）毎に、これら計算・送信処理ｆn=1（ローカル計算、データ交換）が完了すると、outgoing edgeで接する頂点（vertex）への計算結果メッセージをバッファリングせずに直ちに送信する。
【００５１】
また、交通システムの計算シミュレーションへ適用する場合、メッセージ送受信ステップ（データ交換）では、outgoing edgeを介して接する他の頂点に対して、このoutgoing edge介して出てゆく車両の情報（アウトプット）を送信すると共に、incoming edgeを介して接する他の頂点から、このincoming edgeを介して流入する車両の情報（インプット）を受信する。なお、計算結果メッセージは、アウトプットが無くてもスーパーステップ毎に必ず送信する。
【００５２】
また、このスーパーステップ１では、各頂点ｖ1〜ｖ6は、図７においてドットのハッチングで示す同期（フェーズＰＨ３：図１１参照）をそれぞれ行う。この待機状態は、分散処理部２０が計算処理を完了して状態フラグがinactiveになっている状態である。ここでは、各処理サーバ３０は、各頂点の処理時刻の同期処理を行う。つまり、処理サーバ３０が、自ら担当する各頂点の状態フラグをまとめる。そして、全処理サーバ３０に共通のスーパーステップの区切りである同期ポイントにて、次のスーパーステップにおける各頂点の状態フラグ（active/inactive）を管理サーバ１０に報告する。そして、全処理サーバ３０が次のスーパーステップへ移行するように指示されると、各頂点ｖ1〜ｖ6がスーパーステップ２、３、…において同様の処理を実行する。
【００５３】
＜分散処理部の監視動作＞
次に、データ交換（メッセージ送受信ステップ）において、グラフ上で隣接する頂点（vertex）に対応する分散処理部２０（図２）が互いに処理の進行を監視する動作について図８（ａ）及び図８（ｂ）を参照して説明する。図８（ａ）は計算対象のグラフＧを示し、図８（ｂ）はグラフＧ上に重ねた遅れ被疑メッセージを模式的に示している。分散処理部２０は頂点（vertex）として機能するため、ここでは、図２の分散処理部２０を識別して説明するため、便宜的に分散処理部ｖ1〜ｖ6と呼ぶ。
【００５４】
各分散処理部ｖ1〜ｖ6は、incoming edgeにおいて隣接した分散処理部（ｖ1〜ｖ6のいずれか少なくとも１つ）からの計算結果メッセージの受信時刻を監視する。具体的には、図８（ｂ）に示すように、分散処理部ｖ2は、incoming edgeにおいて隣接した分散処理部ｖ1、ｖ3、ｖ4からのメッセージ受信時刻を監視する（ステップＳ２０１）。そして、分散処理部ｖ2は、所定の判定基準に基づいて、隣接した分散処理部ｖ1から計算結果メッセージを所定時間内に受信できない場合、この分散処理部ｖ1による処理の進行が遅れていると判定する（ステップＳ２０２）。
【００５５】
このときの判定基準としては、例えば、時刻の偏差値を用いることができる。具体的には、incoming edgeにおいて隣接した分散処理部ｖ1、ｖ3、ｖ4からの３つのメッセージの到達時刻から偏差値を算出すればよい。あるいは、２つのメッセージが到達してから所定時間経過しても残りのメッセージが到達していない場合に遅れていると判定してもよい。
【００５６】
そして、分散処理部ｖ2は、計算結果メッセージの送達が遅れていることを示す遅れ被疑メッセージＭ0を分散処理部ｖ1に送信する（ステップＳ２０３）。これらの処理は、分散処理部ｖ2を担当する処理サーバ３０（worker1）において実行される。
【００５７】
また、遅れ被疑メッセージＭ0が通知された分散処理部ｖ1を担当する処理サーバ３０（worker1）は、負荷判定部３２（図２参照）によって、分散処理部ｖ1における遅れ被疑メッセージＭ0の受信量が所定の閾値を超えたと判定すると、分散処理部ｖ1に関して処理の遅れを確定する（ステップＳ２０４）。また、処理の遅れが確定した分散処理部ｖ1に関しては、次のように遅れの原因を検出することが可能である。
【００５８】
本実施形態では、処理サーバ３０（worker1）の負荷判定部３２（図２参照）は、自処理サーバ３０（worker1）上の特定の分散処理部ｖ1のみが遅れ被疑メッセージの受信量が所定値よりも多い場合、当該分散処理部ｖ1の処理負荷が大きいと判定する。この所定値（閾値）は適宜設定される。このように特定の分散処理部ｖ1のみが遅れ被疑メッセージの受信量が多い場合、この特定の分散処理部ｖ1の処理が重いことが、worker1における進行の遅れの原因であると検出することができる。以下では、この原因のことを原因１ともいう。
【００５９】
また、本実施形態では、処理サーバ３０（worker1）の負荷判定部３２（図２参照）は、自処理サーバ３０（worker1）上で動作する複数の分散処理部ｖ1、ｖ2、ｖ3に対して通知される遅れ被疑メッセージの受信量がそれぞれ所定値よりも多い場合、自処理サーバ３０（worker1）の処理負荷が大きいと判定する。この所定値（閾値）も適宜設定される。このように自処理サーバ３０（worker1）で担当する複数の分散処理部ｖ1、ｖ2、ｖ3に通知される遅れ被疑メッセージの受信量が全体的に多い場合、自処理サーバ３０（worker1）が過負荷であることが、worker1における進行の遅れの原因であると検出することができる。以下では、この原因のことを原因２ともいう。
【００６０】
ここで、処理サーバ３０における処理の進行が遅れる原因（原因１、原因２）について
図９（ａ）及び図９（ｂ）を参照して説明する。２台の処理サーバ３０（worker1、worker2）において、worker1が担当する各頂点ｖ1、ｖ2、ｖ3がローカル計算に要する時間は、図７及び図８（ａ）に示す時間とは異なっている。
図９（ａ）は、worker1が担当する分散処理部ｖ1、ｖ2、ｖ3のうち、分散処理部ｖ2がローカル計算に他の分散処理部よりも長い時間を要している状況を例示している。
一方、図９（ｂ）は、worker1が担当する分散処理部ｖ1、ｖ2、ｖ3それぞれが、worker2が担当する分散処理部ｖ4、ｖ5、ｖ6よりもローカル計算に長い時間を要している状況を例示している。
【００６１】
既存の同期処理システムのフレームワークでは、管理サーバが処理サーバ（worker）単位で計算処理の進行状況を管理するので、図９（ａ）及び図９（ｂ）に例示したような状況が発生した場合、どちらも、worker1が遅れている、と検出し、それ以上のことは何も分からなかった。
これに対して、本実施形態の分散同期処理システム１では、処理サーバ３０（worker1）の負荷判定部３２（図２参照）が、自処理サーバ３０（worker1）で管理する分散処理部２０（vertex）が受信する遅れ被疑メッセージの受信量に基づいて、自処理サーバ３０（worker1）が遅れる原因（原因１又は原因２）を特定することができる。また、図９（ａ）及び図９（ｂ）に例示したような状況が発生した場合、特定の分散処理部２０の処理が重いことが原因（原因１）であるのか、自処理サーバ３０（worker）が過負荷であることが原因（原因２）であるのか、原因を切り分けることができる。
【００６２】
以上説明したように、本実施形態の分散同期処理システム１では、各処理サーバ３０（worker）上で動作する分散処理部２０（vertex）が互いに自律的に遅れを監視して必要に応じて遅れ被疑メッセージを送信するので、管理サーバ１０の負担を重くせずに分散処理の進行状況を細かく監視しつつ計算処理の遅れを検出することができる。
また、交差点単位で頂点（vertex）を定め、分散同期処理を実行することにより、大規模な交通システムであっても、管理サーバ１０の負担を重くせずに分散処理の進行状況を細かく監視しつつ計算処理の遅れを検出しながら、システムの挙動を短時間でシミュレートすることができる。
【００６３】
（第２実施形態）
第１実施形態のように、隣接する分散処理部２０（vertex）同士で、処理の進行の遅れがないか互いに監視する場合、特定の分散処理部２０の遅れに起因して、そこからoutgoing edgeでつながる分散処理部２０も遅れていると検出される場合が想定される。例えば図１０（ａ）に示す計算対象のグラフＧの場合、分散処理部ｖ6が遅れると、その下流で分散処理部ｖ6からの計算結果を待っている分散処理部ｖ4が遅れることになる。そして、この分散処理部ｖ4が遅れると、その下流で分散処理部ｖ4からの計算結果を待っている分散処理部ｖ2、ｖ3、ｖ5がそれぞれ遅れることになる。
【００６４】
また、特定の分散処理部２０からoutgoing edgeでつながる分散処理部２０が、既に自らの計算結果を完了した後に、その特定の分散処理部２０の計算結果を待っている状態であれば、進行の遅れの真の原因とは言えない。しかしながら、当該結果待ちの分散処理部２０のoutgoing edgeで接する分散処理部２０は、その結果待ちの分散処理部２０の進行が遅れていると判定して遅れ被疑メッセージを送信することになる。そうすると、結果待ちの分散処理部２０の遅れ被疑メッセージ受信量管理部２４（図２参照）が管理する受信量には、進行の遅れの真の原因が反映されず、この受信量に基づいた対処が適切ではなくなる可能性がある。
【００６５】
そこで、第２実施形態に係る分散同期処理システムでは、分散処理部２０が、図２に示すように、遅れ被疑メッセージ転送処理部２５Ｂを備えることとした。
被疑メッセージ転送処理部２５Ｂは、遅れ被疑メッセージを受信したときに、他分散処理部２０から送信される計算結果メッセージの待機状態である場合、遅れ被疑メッセージの受信量をカウントさせずに、受信した遅れ被疑メッセージを当該他分散処理部２０に転送する。
【００６６】
具体的には、図１０（ａ）に示す計算対象のグラフＧの場合、図１０（ｂ）に示すように、分散処理部ｖ2は、隣接する分散処理部ｖ3が遅れていると判定すると、遅れ被疑メッセージＭ1を送信する。この遅れ被疑メッセージＭ1が通知された分散処理部ｖ3は、分散処理部ｖ4からの計算結果を待っている状態であれば、このＭ1を自らの遅れ被疑メッセージの受信量にカウントせずに遅れ被疑メッセージＭ2として分散処理部ｖ4に転送する。
また、この遅れ被疑メッセージＭ2が通知される分散処理部ｖ4には、同様に、outgoing edgeで接する分散処理部ｖ2、ｖ5からも遅れ被疑メッセージＭ3、Ｍ4が通知される。
さらに、遅れ被疑メッセージＭ2、Ｍ3、Ｍ4が通知された分散処理部ｖ4は、分散処理部ｖ6からの計算結果を待っている状態であれば、これらＭ2、Ｍ3、Ｍ4を遅れ被疑メッセージの受信量にカウントせずに遅れ被疑メッセージＭ5として分散処理部ｖ6に転送する。
したがって、転送される遅れ被疑メッセージの受信量には、遅れの影響度合が反映されることになる。つまり、図１０（ｂ）の分散処理部ｖ6のように、遅れの影響範囲が広いほど（outgoingで連鎖する頂点（vertex）が多いほど）遅れ被疑メッセージの受信量が増大し、いち早く遅れが確定されることになる。これにより、遅れを正確に検出する精度を向上させることができる。
【００６７】
（第３実施形態）
第３実施形態に係る分散同期処理システムでは、分散処理部２０が、図２に示すように、故障検出部２６Ｃを備えることとした。
故障検出部２６Ｃは、遅れ被疑メッセージの受信時に、受信完了を示す信号（ＡＣＫ）を送信側に返させ、受信完了を示す信号（ＡＣＫ）が返ってこない場合、予め定められた回数だけ遅れ被疑メッセージを再送させる。これにより、メッセージ送受信部２２は、遅れ被疑メッセージの受信時に、受信完了を示す信号を送信側に返す。そして、故障検出部２６Ｃは、遅れ被疑メッセージを予め定められた回数だけ再送させても受信完了を示す信号が返ってこない場合、故障として検出する。したがって、処理の遅れの原因が故障である場合に適切に対処することができる。
【００６８】
（第４実施形態）
第４実施形態に係る分散同期処理システムでは、処理サーバ３０は、図２に示すように、負荷委譲要求部３３Ｄを備えることとした。
負荷委譲要求部３３Ｄは、自処理サーバ３０上で動作する特定の分散処理部２０（vertex）の処理負荷が大きいと判定された場合、当該特定の分散処理部２０についての委譲要求を管理サーバ１０に通知する。
管理サーバ１０は、この委譲要求が通知されると、この特定の分散処理部２０を、委譲要求を通知した処理サーバ３０よりも処理能力の高い処理サーバ３０に割り当てる。
これにより、処理サーバ３０は、前記した原因１のときに、自ら担当する分散処理部２０（vertex）を委譲することで、検出した原因１に適切に対処することが可能となる。
【００６９】
（第５実施形態）
第５実施形態に係る分散同期処理システムでは、検出した原因２に対処するように、第４実施形態を変形したものである。したがって、第４実施形態と同様に、処理サーバ３０は、図２に示すように、負荷委譲要求部３３Ｄを備えることとした。
ただし、第５実施形態では、負荷委譲要求部３３Ｄは、自処理サーバ３０の処理負荷が大きいと判定された場合に、自処理サーバ３０上で動作する複数の分散処理部２０（vertex）のうちの一部についての委譲要求を管理サーバ１０に通知する。
管理サーバ１０は、この委譲要求が通知されると、委譲要求を通知した処理サーバ３０上で動作する複数の分散処理部２０のうちの一部を、他処理サーバ３０に割り当てる。
これにより、処理サーバ３０は、前記した原因２のときに、自ら担当する複数の分散処理部２０（vertex）のうちの一部を委譲することで、検出した原因２に適切に対処することが可能となる。
【００７０】
（第５実施形態の変形例）
この変形例では、第４、５実施形態に係る分散同期処理システムと同様に、検出した原因１、２の双方に対処するように変形したものである。すなわち、管理サーバ１０は、特定の分散処理部２０（vertex）の委譲要求を受けると、この特定の分散処理部２０を、委譲要求を通知した処理サーバ３０よりも処理能力の高い処理サーバ３０に割り当て、一方、複数の分散処理部２０（vertex）のうちの一部についての委譲要求を受けると、この一部の分散処理部２０を他処理サーバ３０に割り当てる。
【００７１】
（第６実施形態）
第６実施形態に係る分散同期処理システムでは、処理サーバ３０は、図２に示すように、負荷調整部３４Ｅを備えることとした。
負荷調整部３４Ｅは、自処理サーバ３０上で動作する特定の分散処理部２０（vertex）の処理負荷が大きいと判定された場合、又は、自処理サーバ３０の処理負荷が大きいと判定された場合、処理負荷調整要求を管理サーバ１０に通知する。
管理サーバ１０は、処理負荷調整要求が通知されると、既に複数の処理サーバ３０に対して割り当てた全ての分散処理部２０を、処理負荷調整要求を通知した処理サーバ３０に関する処理負荷を低減した新たな配置で、複数の処理サーバ３０に対して再度割り当てる。
ここで、再割り当ての前後では、通常、処理負荷調整要求を通知した処理サーバ３０から、他の処理サーバ３０への通信コストも発生するので、再割り当ての前後で発生する通信コストをできるだけ低く抑えられように再割り当てをすることが好ましい。なお、管理サーバ１０は、全ての分散処理部２０（vertex）の配置をリフレッシュしてもよいが、必須ではない。
【００７２】
本発明は前記した各実施形態に限定されるものではなく、種々の変形が可能であり、第２〜第６実施形態の少なくとも２つを第1実施形態に組み合わせても構わない。また、以下のように変形してもよい。例えば、処理サーバ３０の台数は、複数台であれば特に限定されず、計算対象とするステムの規模等に応じて適宜設定される。処理サーバ３０上の分散処理部２０（vertex）の個数も特に限定されず、１００個以上でも構わない。
【００７３】
また、スーパーステップにおいて、処理サーバ３０は、頂点（vertex）毎に、計算・送信処理が完了すると、outgoing edgeで接する頂点（vertex）への計算結果メッセージをバッファリングせずに直ちに送信するものとしたが、これに限定されるものではない。例えば、図８（ｂ）のworker2が担当する頂点ｖ4のように、頂点ｖ4から頂点ｖ2への送信、及び、頂点ｖ4から頂点ｖ3への送信が、いずれも、外部のworker1への送信であれば、worker2の図示しない送受信管理部が、それぞれの計算結果メッセージをバッファリングしてまとめて送信する。このworker2のような処理をすることで、外部のworkerへの通信回数を削減することができ、通信コストを低減することができる。ただし、バッファリングが原因となって計算結果メッセージの送信処理が遅れてしまうと、隣接する頂点から遅れ被疑メッセージを通知される可能性がある。よって、分散処理の遅れを検出するための精度と、計算結果メッセージの通信コストの低減効果とはトレードオフの関係があると考えられるので、対象とする計算処理の内容や規模に応じて、どちらを優先するか適宜設定する必要がある。なお、図８（ａ）のworker1が担当する頂点ｖ1〜ｖ3のように、頂点ｖ1から頂点ｖ2への送信、頂点ｖ2から頂点ｖ3への送信、及び、頂点ｖ3から頂点ｖ2への送信が、いずれも、自処理サーバ３０内で完結していれば、計算結果メッセージをバッファリングせずに直ちに送信する。
【００７４】
また、分散処理部２０のメッセージ送受信部２２は、例えば、隣接した他分散処理部２０に対して、遅れ被疑メッセージを通知するものとしたが、処理サーバ３０の図示しない送信管理部に送信してもよい。この場合、遅れ被疑メッセージを通知された処理サーバ３０の送信管理部が、その遅れ被疑メッセージの発信元の分散処理部２０が遅れていると判定した、通知すべき宛先の他分散処理部２０へ通知すればよい。
【００７５】
また、前記第４、第５実施形態では、処理サーバ３０が負荷委譲要求部３３Ｄを備えることにより、管理サーバ１０は、委譲要求を処理する必要がある。このために、管理サーバ１０は、処理サーバ３０の状況を把握する。このときの把握方法としては、管理サーバ１０の負荷が大きくならない手法を採用することが好ましい。例えば、全ての処理サーバ３０の計算時間を常時把握するのではなく、より少ない頻度でサンプリングするなどの重たくない処理を併用して、全数調査ではなく統計的に計算時間を収集する手法が挙げられる。
【００７６】
また、委譲要求を管理サーバ１０に通知する処理サーバ３０は、処理負荷が重いので、その担当する分散処理部２０が遅れ被疑メッセージを受けている可能性が高い。より自律的に負荷分散させるために、処理サーバ３０が自己に隣接する処理サーバ３０の情報しか知り得ない場合は、管理サーバ１０は、委譲要求を受けたときに、遅れ被疑メッセージを通知した分散処理部２０を担当する処理サーバ３０のことを、分散処理部２０（vertex）の委譲先と決定してもよい。なお、この場合には、遅れ被疑メッセージを通知した側の分散処理部２０は、そのことを管理サーバ１０に予め報告しておく。
【符号の説明】
【００７７】
１      分散同期処理システム
１０    管理サーバ（master）
２０    分散処理部（vertex）
２１    数値計算部
２２    メッセージ送受信部
２３    受信時刻監視部
２４    遅れ被疑メッセージ受信量管理部
２５Ｂ  遅れ被疑メッセージ転送処理部
２６Ｃ  故障検出部
３０    処理サーバ（worker）
３１    仮想化制御部
３２    負荷判定部
３３Ｄ  負荷委譲要求部
３４Ｅ  負荷調整部
【図１】
2018032346.tif 000003
【図２】
2018032346.tif 000004
【図３】
2018032346.tif 000005
【図４】
2018032346.tif 000006
【図５】
2018032346.tif 000007
【図６】
2018032346.tif 000008
【図７】
2018032346.tif 000009
【図８】
2018032346.tif 000010
【図９】
2018032346.tif 000011
【図１０】
2018032346.tif 000012
【図１１】
2018032346.tif 000013