図面 (/)

技術 分散同期処理システム及びその方法

出願人 日本電信電話株式会社株式会社エヌ・ティ・ティ・データ
発明者 小林弘明北野雄大岡本光浩福元健米森力堤田恭太矢実貴志大谷智洋司南
出願日 2016年8月26日 (3年6ヶ月経過) 出願番号 2016-166184
公開日 2018年3月1日 (2年0ヶ月経過) 公開番号 2018-032346
状態 特許登録済
技術分野 マルチプログラミング
主要キーワード 全数調査 各処理サーバ 委譲要求 影響度合 仮想化制御 有向辺 調整要求 負荷調整
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2018年3月1日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (12)

課題

管理サーバの負担を重くせずに分散処理進行状況を細かく監視しつつ計算処理遅れを検出できる分散同期処理システムを提供する。

解決手段

分散同期処理システムは、並列に処理を行う複数の処理サーバ30と、処理サーバ30上で動作する複数の分散処理部20と、対象とする計算処理に必要な複数の分散処理部20を複数の処理サーバ30に対して割り当てる管理サーバと、を有し、分散処理部20は、所定単位区分された計算処理を行う数値計算部21と、他分散処理部20との間でメッセージ送受信するメッセージ送受信部22と、他分散処理部20から送信される計算結果メッセージの受信時刻を監視する受信時刻監視部23と、を備え、メッセージ送受信部22は、隣接した他分散処理部20から計算結果メッセージを所定時間内に受信できない場合、遅れ被疑メッセージを送信する。

概要

背景

複数のコンピュータを有する分散処理システムフレームワークとして、非特許文献1にはマップデュース(MapReduce)が開示されている。但し、マップレデュースは、ある処理の結果を次の処理で利用するようなイテレティブな処理には不向きであり、この種の処理には、非特許文献2に開示されているBSP(bulk-synchronous parallel)が適していると考えられる。

BSPでは、スーパーステップ(以下、SS表記する場合がある)という処理単位を繰り返し実行することにより、分散環境でのデータ処理を実行する。図11に示すように、スーパーステップSS1、SS2、…は、フェーズPH1として「ローカル計算(LC:Local computation)」、フェーズPH2として「データ交換(COM:Communication)」、フェーズPH3として「同期(SYNC:Synchronization)」の3つのフェーズPH1〜PH3を有している。つまり、BSPを適用した計算システム同期型の分散処理システム(分散同期処理システム)である。

具体的には、図11に示すように、複数のノード(ノード1〜ノード4)は、担当する計算処理に用いるデータが振り分けられると、最初のスーパーステップSS1のフェーズPH1において、そのデータについての計算処理、すなわち、ローカル計算(LC)を実行する。続いて、フェーズPH2において、各ノードが保持しているローカル計算の結果であるデータについて、ノード間でのデータ交換を実行する。次に、フェーズPH3において、同期処理を行う、より詳細には、すべてのノード間でのデータ交換の終了を待つ。そして、スーパーステップSS1の処理(PH1〜PH3)が終了すると、各ノードはその計算結果を保持した上で、次のスーパーステップSS2の処理へと進む。以下、同様にして、複数のスーパーステップが繰り返される。

従来、分散同期処理システムのフレームワークでは、master/workerモデルを採用しており、システムを管理する管理サーバ(master)が、対象とする計算処理の全体を所定単位細分化した個々の計算処理を処理サーバ(worker)に割り振ることとしている。

非特許文献3には、BSPを適用した例として、Pregelという分散処理フレームワークが開示されている。Pregelにおいては、全体の処理内容グラフG=(V,E)として表現し、これをBSPに落とし込んで実行することができる。ここで、Vは頂点(以下、vertexともいう)の集合であり、各頂点は、細分化された個々の処理内容に対応する。また、Eは有向辺(以下、edgeともいう)の集合であり、有向辺は、例えば頂点のもつスコアを計算する場合、各頂点間情報伝達を行う経路に対応する。なお、交通シミュレーションのように、有向辺の上の車を動かしたり、混雑状況を計算したりする場合には、有向辺も計算対象となる。

前記グラフGを例えば、交通システムの計算シミュレーションへ適用する場合、グラフGにおける頂点を交差点、有向辺を通行方向が決まった道路として交通量をモデリングする。この場合、管理サーバ(master)が、各処理サーバ(worker)に対して1以上のN個の頂点をそれぞれ割り振り、処理サーバ(worker)単位で計算処理の進行状況を管理する。そして、処理サーバ(worker)において、担当する各頂点(vertex)に対応したN個の分散処理部(仮想マシン)が個々の計算処理を実行する。

概要

管理サーバの負担を重くせずに分散処理の進行状況を細かく監視しつつ計算処理の遅れを検出できる分散同期処理システムを提供する。分散同期処理システムは、並列に処理を行う複数の処理サーバ30と、処理サーバ30上で動作する複数の分散処理部20と、対象とする計算処理に必要な複数の分散処理部20を複数の処理サーバ30に対して割り当てる管理サーバと、を有し、分散処理部20は、所定単位に区分された計算処理を行う数値計算部21と、他分散処理部20との間でメッセージ送受信するメッセージ送受信部22と、他分散処理部20から送信される計算結果メッセージの受信時刻を監視する受信時刻監視部23と、を備え、メッセージ送受信部22は、隣接した他分散処理部20から計算結果メッセージを所定時間内に受信できない場合、遅れ被疑メッセージを送信する。

目的

本発明では、前記した問題を解決し、管理サーバの負担を重くせずに分散処理の進行状況を細かく監視しつつ計算処理の遅れを検出できる分散同期処理システム及びその方法を提供する

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

(分野番号表示ON)※整理標準化データをもとに当社作成

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

並列に処理を行う複数の処理サーバと、前記処理サーバ上で動作する複数の分散処理部と、対象とする計算処理に必要な複数の前記分散処理部を複数の前記処理サーバに対して割り当てる管理サーバと、を有する分散同期処理システムであって、前記分散処理部は、所定単位区分された計算処理を行う数値計算部と、他分散処理部との間で計算結果メッセージを含むメッセージを送受信するメッセージ送受信部と、他分散処理部から送信される計算結果メッセージの受信時刻監視する受信時刻監視部と、を備え、前記メッセージ送受信部は、隣接した他分散処理部から前記計算結果メッセージを所定時間内に受信できない場合、前記計算結果メッセージの送達遅れていることを示す遅れ被疑メッセージを送信する、ことを特徴とする分散同期処理システム。

請求項2

前記分散処理部は、通知される前記遅れ被疑メッセージの受信量を管理する遅れ被疑メッセージ受信管理部をさらに備え、前記処理サーバは、自処理サーバ上で動作する複数の分散処理部に対して通知される前記遅れ被疑メッセージの受信量を監視し、自処理サーバ上の特定の分散処理部のみが前記遅れ被疑メッセージの受信量が所定値よりも多い場合、当該分散処理部の処理負荷が大きいと判定し、自処理サーバ上で動作する複数の分散処理部に対して通知される前記遅れ被疑メッセージの受信量がそれぞれ所定値よりも多い場合、自処理サーバの処理負荷が大きいと判定する負荷判定部を備える請求項1に記載の分散同期処理システム。

請求項3

前記処理サーバは、自処理サーバ上で動作する特定の分散処理部の処理負荷が大きいと判定された場合、当該特定の分散処理部についての委譲要求を前記管理サーバに通知する負荷委譲要求部をさらに備え、前記管理サーバは、前記委譲要求が通知されると、前記特定の分散処理部を、前記委譲要求を通知した処理サーバよりも処理能力の高い処理サーバに割り当てる請求項2に記載の分散同期処理システム。

請求項4

前記処理サーバは、自処理サーバの処理負荷が大きいと判定された場合、自処理サーバ上で動作する複数の分散処理部のうちの一部についての委譲要求を前記管理サーバに通知する負荷委譲要求部をさらに備え、前記管理サーバは、前記委譲要求が通知されると、前記委譲要求を通知した処理サーバ上で動作する複数の分散処理部のうちの一部を、他処理サーバに割り当てる請求項2に記載の分散同期処理システム。

請求項5

前記処理サーバは、自処理サーバ上で動作する特定の分散処理部の処理負荷が大きいと判定された場合、又は、自処理サーバの処理負荷が大きいと判定された場合、処理負荷調整要求を前記管理サーバに通知する負荷調整部をさらに備え、前記管理サーバは、前記処理負荷調整要求が通知されると、既に複数の前記処理サーバに対して割り当てた全ての前記分散処理部を、前記処理負荷調整要求を通知した処理サーバに関する処理負荷を低減した新たな配置で、複数の前記処理サーバに対して再度割り当てる請求項2に記載の分散同期処理システム。

請求項6

前記分散処理部は、前記遅れ被疑メッセージを受信したときに、他分散処理部から送信される計算結果メッセージの待機状態である場合、前記遅れ被疑メッセージの受信量をカウントさせずに、受信した前記遅れ被疑メッセージを当該他分散処理部に転送する遅れ被疑メッセージ転送処理部をさらに備える請求項2から請求項5のいずれか一項に記載の分散同期処理システム。

請求項7

前記分散処理部は、前記遅れ被疑メッセージの受信時に、受信完了を示す信号を送信側に返させ、前記受信完了を示す信号が返ってこない場合、予め定められた回数だけ前記遅れ被疑メッセージを再送させ、前記遅れ被疑メッセージを前記回数だけ再送させても前記受信完了を示す信号が返ってこない場合、故障として検出する故障検出部をさらに備える請求項1から請求項6のいずれか一項に記載の分散同期処理システム。

請求項8

並列に処理を行う複数の処理サーバと、前記処理サーバ上で動作する複数の分散処理部と、対象とする計算処理に必要な複数の前記分散処理部を複数の前記処理サーバに対して割り当てる管理サーバと、を有する分散同期処理システムによる分散同期処理方法であって、前記分散処理部は、所定単位に区分された計算処理を行う数値計算ステップと、少なくとも1つの他分散処理部との間で計算結果メッセージを含むメッセージを送受信するメッセージ送受信ステップと、他分散処理部から送信される計算結果メッセージの受信時刻を監視する受信時刻監視ステップと、を有し、前記メッセージ送受信ステップは、隣接した他分散処理部から前記計算結果メッセージを所定時間内に受信できない場合、前記計算結果メッセージの送達が遅れていることを示す遅れ被疑メッセージを送信する、ことを特徴とする分散同期処理方法。

技術分野

0001

本発明は、分散処理システム係り、特に、同期型の分散処理システムである分散同期処理システム及びその方法に関する。

背景技術

0002

複数のコンピュータを有する分散処理システムのフレームワークとして、非特許文献1にはマップデュース(MapReduce)が開示されている。但し、マップレデュースは、ある処理の結果を次の処理で利用するようなイテレティブな処理には不向きであり、この種の処理には、非特許文献2に開示されているBSP(bulk-synchronous parallel)が適していると考えられる。

0003

BSPでは、スーパーステップ(以下、SS表記する場合がある)という処理単位を繰り返し実行することにより、分散環境でのデータ処理を実行する。図11に示すように、スーパーステップSS1、SS2、…は、フェーズPH1として「ローカル計算(LC:Local computation)」、フェーズPH2として「データ交換(COM:Communication)」、フェーズPH3として「同期(SYNC:Synchronization)」の3つのフェーズPH1〜PH3を有している。つまり、BSPを適用した計算システムは同期型の分散処理システム(分散同期処理システム)である。

0004

具体的には、図11に示すように、複数のノード(ノード1〜ノード4)は、担当する計算処理に用いるデータが振り分けられると、最初のスーパーステップSS1のフェーズPH1において、そのデータについての計算処理、すなわち、ローカル計算(LC)を実行する。続いて、フェーズPH2において、各ノードが保持しているローカル計算の結果であるデータについて、ノード間でのデータ交換を実行する。次に、フェーズPH3において、同期処理を行う、より詳細には、すべてのノード間でのデータ交換の終了を待つ。そして、スーパーステップSS1の処理(PH1〜PH3)が終了すると、各ノードはその計算結果を保持した上で、次のスーパーステップSS2の処理へと進む。以下、同様にして、複数のスーパーステップが繰り返される。

0005

従来、分散同期処理システムのフレームワークでは、master/workerモデルを採用しており、システムを管理する管理サーバ(master)が、対象とする計算処理の全体を所定単位細分化した個々の計算処理を処理サーバ(worker)に割り振ることとしている。

0006

非特許文献3には、BSPを適用した例として、Pregelという分散処理フレームワークが開示されている。Pregelにおいては、全体の処理内容グラフG=(V,E)として表現し、これをBSPに落とし込んで実行することができる。ここで、Vは頂点(以下、vertexともいう)の集合であり、各頂点は、細分化された個々の処理内容に対応する。また、Eは有向辺(以下、edgeともいう)の集合であり、有向辺は、例えば頂点のもつスコアを計算する場合、各頂点間情報伝達を行う経路に対応する。なお、交通シミュレーションのように、有向辺の上の車を動かしたり、混雑状況を計算したりする場合には、有向辺も計算対象となる。

0007

前記グラフGを例えば、交通システムの計算シミュレーションへ適用する場合、グラフGにおける頂点を交差点、有向辺を通行方向が決まった道路として交通量をモデリングする。この場合、管理サーバ(master)が、各処理サーバ(worker)に対して1以上のN個の頂点をそれぞれ割り振り、処理サーバ(worker)単位で計算処理の進行状況を管理する。そして、処理サーバ(worker)において、担当する各頂点(vertex)に対応したN個の分散処理部(仮想マシン)が個々の計算処理を実行する。

先行技術

0008

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 theACM, 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

発明が解決しようとする課題

0009

個々の計算処理が遅れる原因を検出したり、検出した原因に応じて適切に対処したりすれば、計算対象とするシステムの挙動をより短時間にシミュレートすることが可能である。そのために、管理サーバ(master)がより細かく計算処理の進行状況を管理することが望まれる。しかしながら、管理サーバに対して、計算処理の進行状況を従来より細かく管理する機能を付加すると、管理サーバの負荷が重くなり、大規模な計算システムのシミュレーションには対応することができなくなってしまう問題がある。

0010

そこで、本発明では、前記した問題を解決し、管理サーバの負担を重くせずに分散処理の進行状況を細かく監視しつつ計算処理の遅れを検出できる分散同期処理システム及びその方法を提供することを課題とする。

課題を解決するための手段

0011

前記した課題を解決するため、本発明に係る分散同期処理システムは、並列に処理を行う複数の処理サーバと、前記処理サーバ上で動作する複数の分散処理部と、対象とする計算処理に必要な複数の前記分散処理部を複数の前記処理サーバに対して割り当てる管理サーバと、を有する分散同期処理システムであって、前記分散処理部が、所定単位に区分された計算処理を行う数値計算部と、他分散処理部との間で計算結果メッセージを含むメッセージを送受信するメッセージ送受信部と、他分散処理部から送信される計算結果メッセージの受信時刻を監視する受信時刻監視部と、を備え、前記メッセージ送受信部が、隣接した他分散処理部から前記計算結果メッセージを所定時間内に受信できない場合、前記計算結果メッセージの送達が遅れていることを示す遅れ被疑メッセージを送信する、ことを特徴とする。

0012

また、前記した課題を解決するため、本発明に係る分散同期処理方法は、並列に処理を行う複数の処理サーバと、前記処理サーバ上で動作する複数の分散処理部と、対象とする計算処理に必要な複数の前記分散処理部を複数の前記処理サーバに対して割り当てる管理サーバと、を有する分散同期処理システムによる分散同期処理方法であって、前記分散処理部が、所定単位に区分された計算処理を行う数値計算ステップと、少なくとも1つの他分散処理部との間で計算結果メッセージを含むメッセージを送受信するメッセージ送受信ステップと、他分散処理部から送信される計算結果メッセージの受信時刻を監視する受信時刻監視ステップと、を有し、前記メッセージ送受信ステップが、隣接した他分散処理部から前記計算結果メッセージを所定時間内に受信できない場合、前記計算結果メッセージの送達が遅れていることを示す遅れ被疑メッセージを送信する、ことを特徴とする。

0013

かかる構成の分散同期処理システム、及び、かかる手順の分散同期処理方法によれば、分散処理部は、所定単位に区分された計算処理を行い、他分散処理部との間でその計算結果メッセージを送受信する。その際に、各分散処理部は、隣接した他分散処理部から送信される計算結果メッセージの受信時刻を互いに監視し、所定時間内に受信できない場合、遅れ被疑メッセージを送信する。したがって、分散処理部が、計算結果メッセージの受信時刻を互いに自律的に監視することで分散処理の進行状況を細かく監視しつつ計算処理の遅れを検出することができる。

0014

また、本発明に係る分散同期処理システムは、前記分散処理部が、通知される前記遅れ被疑メッセージの受信量を管理する遅れ被疑メッセージ受信管理部をさらに備え、前記処理サーバが、自処理サーバ上で動作する複数の分散処理部に対して通知される前記遅れ被疑メッセージの受信量を監視し、自処理サーバ上の特定の分散処理部のみが前記遅れ被疑メッセージの受信量が所定値よりも多い場合、当該分散処理部の処理負荷が大きいと判定し、自処理サーバ上で動作する複数の分散処理部に対して通知される前記遅れ被疑メッセージの受信量がそれぞれ所定値よりも多い場合、自処理サーバの処理負荷が大きいと判定する負荷判定部を備えることとしてもよい。
かかる構成よれば、分散同期処理システムは、処理サーバで管理する分散処理部が受信する遅れ被疑メッセージの受信量に基づいて、処理サーバが遅れる原因が、特定の分散処理部の処理が重いことが原因であるのか、処理サーバが過負荷であることが原因であるのか、その原因を切り分けることができる。

0015

また、本発明に係る分散同期処理システムは、前記処理サーバが、自処理サーバ上で動作する特定の分散処理部の処理負荷が大きいと判定された場合、当該特定の分散処理部についての委譲要求を前記管理サーバに通知する負荷委譲要求部をさらに備え、前記管理サーバが、前記委譲要求が通知されると、前記特定の分散処理部を、前記委譲要求を通知した処理サーバよりも処理能力の高い処理サーバに割り当てることとしてもよい。
例えば、処理能力の高い処理サーバと低い処理サーバが混在した分散処理システムでは、処理能力の低い処理サーバは処理が遅れる傾向にある。このように処理サーバの性能にバラツキがある場合であっても、かかる構成の分散同期処理システムによれば、ある処理サーバの処理が遅れる原因が、当該処理サーバ上で動作する特定の分散処理部の処理が重いことが原因である場合に、その特定の分散処理部を、処理能力の高い処理サーバに委譲することで委譲元の処理サーバの負荷を低減し、負荷を均一化することができる。

0016

また、本発明に係る分散同期処理システムは、前記処理サーバが、自処理サーバの処理負荷が大きいと判定された場合、自処理サーバ上で動作する複数の分散処理部のうちの一部についての委譲要求を前記管理サーバに通知する負荷委譲要求部をさらに備え、前記管理サーバが、前記委譲要求が通知されると、前記委譲要求を通知した処理サーバ上で動作する複数の分散処理部のうちの一部を、他処理サーバに割り当てることとしてもよい。
例えば、BSPで繰り返し行われる毎回のスーパーステップでは、処理サーバは、複数のタスク処理を受けている状態にある。このように処理サーバが、あるスーパーステップで多数の分散処理部を受けている場合であっても、かかる構成の分散同期処理システムによれば、ある処理サーバの処理が遅れる原因が、処理能力によるものではなく分散処理部が多いことによって処理サーバが過負荷の状態になっている場合に、その一部の分散処理部を、他の処理サーバに委譲することで委譲元の処理サーバの負荷を低減し、負荷を均一化することができる。

0017

また、本発明に係る分散同期処理システムは、前記処理サーバが、自処理サーバ上で動作する特定の分散処理部の処理負荷が大きいと判定された場合、又は、自処理サーバの処理負荷が大きいと判定された場合、処理負荷調整要求を前記管理サーバに通知する負荷調整部をさらに備え、前記管理サーバが、前記処理負荷調整要求が通知されると、既に複数の前記処理サーバに対して割り当てた全ての前記分散処理部を、前記処理負荷調整要求を通知した処理サーバに関する処理負荷を低減した新たな配置で、複数の前記処理サーバに対して再度割り当てることとしてもよい。
かかる構成によれば、分散同期処理システムは、処理サーバが遅れる原因が、特定の分散処理部の処理が重いことが原因である場合や、処理サーバが過負荷である場合に、適切に対処することができる。

0018

また、本発明に係る分散同期処理システムは、前記分散処理部は、前記遅れ被疑メッセージを受信したときに、他分散処理部から送信される計算結果メッセージの待機状態である場合、前記遅れ被疑メッセージの受信量をカウントさせずに、受信した前記遅れ被疑メッセージを当該他分散処理部に転送する遅れ被疑メッセージ転送処理部をさらに備えることとしてもよい。
かかる構成によれば、遅れの影響範囲が広いほど遅れ被疑メッセージの受信量が増大し、いち早く遅れが確定されることになる。これにより、分散同期処理システムは、分散処理部の遅れを正確に検出する精度を向上させることができる。

0019

また、本発明に係る分散同期処理システムは、前記分散処理部が、前記遅れ被疑メッセージの受信時に、受信完了を示す信号を送信側に返させ、前記受信完了を示す信号が返ってこない場合、予め定められた回数だけ前記遅れ被疑メッセージを再送させ、前記遅れ被疑メッセージを前記回数だけ再送させても前記受信完了を示す信号が返ってこない場合、故障として検出する故障検出部をさらに備えることとしてもよい。
かかる構成によれば、分散同期処理システムは、処理の遅れの原因が故障である場合に適切に対処することができる。

発明の効果

0020

本発明によれば、管理サーバの負担を重くせずに分散処理の進行状況を細かく監視しつつ計算処理の遅れを検出することができる。

図面の簡単な説明

0021

本発明の実施形態に係る分散同期処理システムを模式的に示す構成図である。
図1の処理サーバ及び分散処理部の構成例を示す機能ブロック図である。
対象とする計算処理を交通システムに適用する場合のグラフの説明図である。
分散処理部に対応した頂点(vertex)の一部の構成要素を模式的に示す説明図である。
分散処理部に対応した頂点(vertex)の構成要素の説明図である。
本発明の実施形態に係る分散同期処理システムの全体の動作を示すシーケンス図である。
処理サーバが担当する分散処理部がスーパーステップで時系列に実行する基本動作を示す模式図である。
本発明の実施形態に係る分散同期処理システムの動作説明図であって、(a)は計算対象のグラフ、(b)はグラフ上に重ねた遅れ被疑メッセージを示している。
(a)、(b)は処理サーバ毎の進行状況の具体例をそれぞれ示す模式図である。
本発明の他の実施形態に係る分散同期処理システムの動作説明図であって、(a)は計算対象のグラフ、(b)はグラフ上に重ねた遅れ被疑メッセージを示している。
従来技術であるBSP計算モデルの説明図である。

実施例

0022

以下、本発明の分散同期処理システム及び分散同期処理方法について図面を参照して詳細に説明する。
(第1実施形態)
[分散同期処理システムの構成]
図1に示すように、分散同期処理システム1は、管理サーバ10と、管理サーバ10にそれぞれ接続され並列に処理を行う複数の処理サーバ30と、処理サーバ30上で動作する複数の分散処理部20(仮想マシン)と、を備えている。

0023

管理サーバ10及び処理サーバ30は、CPU(Central Processing Unit)、RAM(Random Access Memory)、ROM(Read Only Memory)、HDD(Hard Disk Drive)等、一般的なコンピュータとしてのハードウエアを備えており、HDDには、OS(Operating System)、アプリケーションプログラム、各種データ等が格納されている。OSおよびアプリケーションプログラムは、RAMに展開され、CPUによって実行される。なお、図2において、分散処理部20及び処理サーバ30の内部は、RAMに展開されたアプリケーションプログラム等によって実現される機能を、ブロックとして示している。

0024

管理サーバ10は、システム全体を管理するmasterとして機能する。管理サーバ10は、対象とする計算処理の全体を所定単位に細分化した複数の計算処理を、workerとして機能する処理サーバ30にそれぞれ割り振る。個々の計算処理には、データ入力、計算、メッセージの送受信等が含まれる。並列に処理を行う複数の処理サーバ30上では、個々の計算処理にそれぞれ対応した複数の分散処理部20が動作する。対象とする計算処理をグラフG=(V,E)として表現したときに、この計算処理に必要な個々の計算処理は、グラフ中の個々の頂点(vertex)として表現される。つまり、分散処理部20は頂点(vertex)として機能する。

0025

管理サーバ10は、対象とする計算処理に必要な複数の分散処理部20を複数の処理サーバ30に対して割り当てるものである。管理サーバ10は、各処理サーバ30に共通のスーパーステップの進行状況を管理する。管理サーバ10は、必要に応じて、グラフトポロジを更新する。例えば、グラフ上の頂点の増減がある場合や、有向辺の増減がある場合にグラフトポロジを更新する。

0026

分散処理部20は、図2に示すように、数値計算部21と、メッセージ送受信部22と、受信時刻監視部23と、遅れ被疑メッセージ受信量管理部24と、を備えている。なお、遅れ被疑メッセージ転送処理部25B、及び故障検出部26Cは、別の実施形態の構成であり、その説明については後記する。

0027

数値計算部21は、所定単位に区分された計算処理を行うものである。この処理は、図11を参照して説明したBSPモデルのフェーズPH1としてのローカル計算(LC:Local computation)に相当する。

0028

メッセージ送受信部22は、他分散処理部20との間で計算結果メッセージを含むメッセージを送受信するものである。この処理は、図11を参照して説明したBSPモデルのフェーズPH2としてのデータ交換(COM:Communication)に相当する。
本実施形態では、メッセージ送受信部22は、隣接した他分散処理部20から計算結果メッセージを所定時間内に受信できない場合、遅れ被疑メッセージを送信することとした。遅れ被疑メッセージは、計算結果メッセージの送達が遅れていることを示すメッセージである。メッセージ送受信部22は、例えば、隣接した他分散処理部20に対して、遅れ被疑メッセージを通知する。

0029

受信時刻監視部23は、他分散処理部20から送信される計算結果メッセージの受信時刻を監視するものである。受信時刻監視部23は、計算結果メッセージの受信時刻が所定の基準を超える他分散処理部20は、遅れていると判定する。なお、具体例については後記する。

0030

遅れ被疑メッセージ受信量管理部24は、自分散処理部20に通知される遅れ被疑メッセージの受信量を管理するものである。後記するように、この受信量は、当該分散処理部20を担当する処理サーバ30によって適宜参照され、当該処理サーバ30又は当該分散処理部20の負荷を判定するために用いられる。

0031

処理サーバ(worker)30は、図2に示すように、仮想化制御部31と、負荷判定部32と、を備えている。なお、負荷委譲要求部33D、及び負荷調整部33Eは、別の実施形態の構成であり、その説明については、後記する。

0032

仮想化制御部31は、仮想化技術に基づき、処理サーバ30上に仮想化プラットホーム構築し、複数の分散処理部20(仮想マシン)を配置する制御を行う。

0033

負荷判定部32は、自処理サーバ30上で動作する複数の分散処理部20に対して通知される遅れ被疑メッセージの受信量を監視するものである。
負荷判定部32は、ある分散処理部20に対して通知された遅れ被疑メッセージの受信量が所定の閾値を超えると、その遅れ被疑メッセージの通知を受けた分散処理部20に関して処理の遅れを確定する。処理の遅れが確定した分散処理部20に関しては、後記するように、遅れの原因を検出したり、さらに、検出した原因に対処したりすることが可能となる。

0034

なお、遅れ被疑メッセージの受信量が所定の閾値を超えていない分散処理部20の場合、遅れ被疑メッセージを送信した他分散処理部20にとっては計算結果メッセージの送達が遅れているものの、分散同期処理システム1にとっては、当該分散処理部20は処理が遅れていることにはならない。

0035

[交通システムのシミュレーション]
次に、この分散同期処理システム1にて対象とする計算処理の具体例として、交通システムのシミュレーションについて説明する。対象とする計算処理をグラフG=(V,E)として表現したときに、図3に示すように、各交差点が頂点(vertex)v1〜v4に対応付けられ、各交差点を結ぶ道路が有向辺(edge)e1〜e6に対応付けられている。ここで、有向辺は一方通行であり、双方向の道路は2つの有向辺に対応付けられる。ある頂点から見て、車両が出てゆく方向の有向辺を、出力辺(以下、outgoing edgeともいう)と呼び、車両が流入する方向の有向辺を、入力辺(以下、incoming edgeともいう)と呼ぶ。例えば、図3において、頂点v2から頂点v1を見ると、有向辺e1は入力辺であり、有向辺e2は出力辺である。逆に、頂点v1から頂点v2を見ると、有向辺e1は出力辺であり、有向辺e2は入力辺である。

0036

<頂点(vertex)の構成>
図1及び図2に示す分散処理部20は、前記したように、頂点(vertex)として機能する。この節では、頂点をvertexと呼び、vertexの構成について、図4及び図5を参照して説明する。図4は、グラフ上のvertexを模式的に示す説明図であり、図5は、vertexの構成要素の説明図である。なお、図4には、vertexの構成要素の一部(図5の一部)を図示している。

0037

また、この節では、2つの有向辺をoutgoing edge,incoming edgeと呼ぶ。さらに、スーパーステップのステップ数のことを、n(自然数)を用いて表す。スーパーステップにおいて現在のステップ数を単にステップnと呼び、また、その直前のステップ数を、単にステップn−1と呼ぶ
例えば、現在のステップnにおいて、vertex IDが1であるvertexの構成要素は、図4実線で表されている部分であり、v1,nと、e1,3,nと、e1,4,nと、m2,1,n-1と、m3,1,n-1と、m2,1,nと、を備えている。

0038

ここで、v1,nは、現在のステップnにおいてvertex IDが1であるvertexの状態を表す。
e1,3,nは、現在のステップnにおいてvertex IDが1であるvertexから、vertex IDが3であるvertexへのoutgoing edgeの状態を表す。
e1,4,nは、現在のステップnにおいてvertex IDが1であるvertexから、vertex IDが4であるvertexへのoutgoing edgeの状態を表す。
m2,1,n-1は、前回ステップn−1において、vertex IDが2であるvertexから、vertex IDが1であるvertexへ送られたメッセージを表す。
m3,1,n-1は、前回ステップn−1において、vertex IDが3であるvertexから、vertex IDが1であるvertexへ送られたメッセージを表す。なお、vertex IDが1であるvertexに関して、m2,1,n-1及びm3,1,n-1はincomingメッセージであり、現在のステップnにおいて、一つ前のステップ(n−1)用のバッファMin,n-1に保持されている。
m2,1,nは、現在のステップnにおいて、vertex IDが2であるvertexから、vertex IDが1であるvertexへ送られたメッセージを表す。なお、vertex IDが1であるvertexに関して、m2,1,nはincomingメッセージであり、現在のステップnにおいて、現在のステップ(n)用のバッファMin,nに保持されている。

0039

なお、図4は、メッセージ送信遷移の途中等であってスナップショットのようなある瞬間を模式的に示している。また、図4において破線で示した構成要素は、vertex IDが2,3,4であるvertexの構成要素の一部である。
v2,nは、現在のステップnにおいてvertex IDが2であるvertexの状態を表す。
v3,nは、現在のステップnにおいてvertex IDが3であるvertexの状態を表す。
v4,nは、現在のステップnにおいてvertex IDが4であるvertexの状態を表す。
m1,3,n-1は、前回ステップn−1において、vertex IDが1であるvertexから、vertex IDが3であるvertexへ送られたメッセージを表す。
m1,4,n-1は、前回ステップn−1において、vertex IDが1であるvertexから、vertex IDが4であるvertexへ送られたメッセージを表す。

0040

図5に示すように、vertexは、図4に示した構成要素以外に、現在のステップnにおける状態フラグSnと、次のステップn+1における状態フラグSn+1と、計算・送信処理fと、を備えている。
現在のステップnにおける状態フラグSnは、現在のステップnにおいてvertex(分散処理部20)が計算処理をしていればactiveであり、計算処理を完了するとinactiveになる。
次のステップn+1における状態フラグSn+1は、次のステップn+1においてvertex(分散処理部20)が計算処理をする予定であればactiveであり、計算処理をしない予定であればinactiveになる。

0041

計算・送信処理fは、スーパーステップ毎に行われる。現在のステップnにおける計算・送信処理はfnとなり、次のステップn+1における計算・送信処理はfn+1となる。例えば、現在のステップnにおける計算・送信処理fnは、現在のステップnにおけるvertexの状態、現在のステップnにおけるoutgoing edgeの状態、及び前回ステップn−1におけるincomingメッセージをパラメータとして計算を行うことで、vertexの状態とoutgoing edgeの状態とを更新すると共に、計算結果メッセージを隣接vertexに送信するものである。このとき、前回ステップn−1におけるincomingメッセージは、その前回ステップn−1において「現在のステップ用のバッファ」に保持されているが、次のステップ、すなわち現在のステップnでは、「一つ前のステップ用のバッファ」に移されて保持され、現在のステップnにおける計算・送信処理fnのために用いられた後、廃棄される。

0042

本実施形態のように交通システムの計算シミュレーションへ適用する場合、vertexの状態とは、例えば交差点内の信号の色(赤・黄・青)の状態を表す。
また、outgoing edgeの状態とは、道路内の車両の動き(車両の台数や、その台数における車両の平均速度)を表す。
また、incomingメッセージは、何時にどれだけの車両が入ってきたかといった情報を表す。

0043

なお、図5において、outgoing edgeの状態(e)と、そのoutgoing edgeの状態の集合(E)とは、アルファベット小文字大文字で区別している。また、図5において、incomingメッセージ(m)と、それを格納するバッファ(M)とは、アルファベットの小文字と大文字で区別している。

0044

[分散同期処理システムの動作]
次に、本発明の実施形態に係る分散同期処理システム1の動作について説明する。
<全体動作>
まず、分散同期処理システム1の全体の動作について図6を参照して説明する。
以下では、簡単のため、分散同期処理システム1は、2台の処理サーバ30(worker1、worker2)を備えるものとして説明する。また、以下の説明におけるステップSとは、全体動作における処理の流れを示す工程を意味するものである。

0045

まず、管理サーバ(master)10は、各処理サーバ30に処理(分散処理部20)を割り振る(ステップS101)。
これにしたがって、処理サーバ30は、担当する分散処理部20(vertex)のスーパーステップを実行する(ステップS102)。なお、この工程の詳細については後記する。
そして、処理サーバ30は、担当する全ての分散処理部20(vertex)の処理が完了したら、次のスーパーステップにおける各vertexの状態フラグ(active/inactive)を管理サーバ10に報告する(ステップS103)。

0046

管理サーバ10は、全処理サーバ30(worker1、worker2)から報告を受けると、自ら記憶管理しているスーパーステップのステップ数を+1増加して更新する(ステップS104)。なお、管理サーバ10は、必要な場合、グラフトポロジを更新する(ステップS105)。そして、管理サーバ10は、次のスーパーステップへ移行するように各workerに指示する(ステップS105)。以降、分散同期処理システム1は、スーパーステップのステップ数を進めた上で、前記したステップS102〜ステップS106を繰り返す。

0047

<分散処理部の基本動作>
次に、処理サーバ30が担当する分散処理部20がスーパーステップで時系列に実行する基本動作について図7を参照して説明する。
以下では、簡単のため、図8(a)に示すグラフGを計算対象のグラフとする。また、グラフG上の頂点を符号v1〜v6で識別して説明する。また、管理サーバ10は、グラフGの頂点v1〜v3をworker1の担当として割り当て、頂点v4〜v6をworker2の担当として割り当て、各頂点v1〜v6に分散処理部20がそれぞれ対応付けられていることとする。

0048

スーパーステップ1では、各頂点v1〜v6は、図7において右下がりハッチングで示すローカル計算(フェーズPH1:図11参照)をそれぞれ実行する。この処理は、図2に示す分散処理部20の数値計算部21が、所定単位に区分された計算処理を行うものである(数値計算ステップ)。

0049

本実施形態のように交通システムの計算シミュレーションへ適用する場合、この数値計算ステップ(ローカル計算)では、例えば、所定時間内における、各頂点v1〜v6に対応付けられている交差点内の信号の色(赤・黄・青)や車両の動き等と、各頂点v1〜v6に接続されているoutgoing edgeに対応する道路内の車両の動き(車両の台数や平均速度)とをシミュレートする。

0050

また、このスーパーステップ1では、各頂点v1〜v6は、図7において縦縞のハッチングで示すデータ交換(フェーズPH2:図11参照)をそれぞれ実行する。この処理は、図2に示す分散処理部20のメッセージ送受信部22が、他分散処理部20との間で計算結果メッセージを含むメッセージを送受信するものである(メッセージ送受信ステップ)。
各処理サーバ30は、頂点(vertex)毎に、これら計算・送信処理fn=1(ローカル計算、データ交換)が完了すると、outgoing edgeで接する頂点(vertex)への計算結果メッセージをバッファリングせずに直ちに送信する。

0051

また、交通システムの計算シミュレーションへ適用する場合、メッセージ送受信ステップ(データ交換)では、outgoing edgeを介して接する他の頂点に対して、このoutgoing edge介して出てゆく車両の情報(アウトプット)を送信すると共に、incoming edgeを介して接する他の頂点から、このincoming edgeを介して流入する車両の情報(インプット)を受信する。なお、計算結果メッセージは、アウトプットが無くてもスーパーステップ毎に必ず送信する。

0052

また、このスーパーステップ1では、各頂点v1〜v6は、図7においてドットのハッチングで示す同期(フェーズPH3:図11参照)をそれぞれ行う。この待機状態は、分散処理部20が計算処理を完了して状態フラグがinactiveになっている状態である。ここでは、各処理サーバ30は、各頂点の処理時刻の同期処理を行う。つまり、処理サーバ30が、自ら担当する各頂点の状態フラグをまとめる。そして、全処理サーバ30に共通のスーパーステップの区切りである同期ポイントにて、次のスーパーステップにおける各頂点の状態フラグ(active/inactive)を管理サーバ10に報告する。そして、全処理サーバ30が次のスーパーステップへ移行するように指示されると、各頂点v1〜v6がスーパーステップ2、3、…において同様の処理を実行する。

0053

<分散処理部の監視動作
次に、データ交換(メッセージ送受信ステップ)において、グラフ上で隣接する頂点(vertex)に対応する分散処理部20(図2)が互いに処理の進行を監視する動作について図8(a)及び図8(b)を参照して説明する。図8(a)は計算対象のグラフGを示し、図8(b)はグラフG上に重ねた遅れ被疑メッセージを模式的に示している。分散処理部20は頂点(vertex)として機能するため、ここでは、図2の分散処理部20を識別して説明するため、便宜的に分散処理部v1〜v6と呼ぶ。

0054

各分散処理部v1〜v6は、incoming edgeにおいて隣接した分散処理部(v1〜v6のいずれか少なくとも1つ)からの計算結果メッセージの受信時刻を監視する。具体的には、図8(b)に示すように、分散処理部v2は、incoming edgeにおいて隣接した分散処理部v1、v3、v4からのメッセージ受信時刻を監視する(ステップS201)。そして、分散処理部v2は、所定の判定基準に基づいて、隣接した分散処理部v1から計算結果メッセージを所定時間内に受信できない場合、この分散処理部v1による処理の進行が遅れていると判定する(ステップS202)。

0055

このときの判定基準としては、例えば、時刻の偏差値を用いることができる。具体的には、incoming edgeにおいて隣接した分散処理部v1、v3、v4からの3つのメッセージの到達時刻から偏差値を算出すればよい。あるいは、2つのメッセージが到達してから所定時間経過しても残りのメッセージが到達していない場合に遅れていると判定してもよい。

0056

そして、分散処理部v2は、計算結果メッセージの送達が遅れていることを示す遅れ被疑メッセージM0を分散処理部v1に送信する(ステップS203)。これらの処理は、分散処理部v2を担当する処理サーバ30(worker1)において実行される。

0057

また、遅れ被疑メッセージM0が通知された分散処理部v1を担当する処理サーバ30(worker1)は、負荷判定部32(図2参照)によって、分散処理部v1における遅れ被疑メッセージM0の受信量が所定の閾値を超えたと判定すると、分散処理部v1に関して処理の遅れを確定する(ステップS204)。また、処理の遅れが確定した分散処理部v1に関しては、次のように遅れの原因を検出することが可能である。

0058

本実施形態では、処理サーバ30(worker1)の負荷判定部32(図2参照)は、自処理サーバ30(worker1)上の特定の分散処理部v1のみが遅れ被疑メッセージの受信量が所定値よりも多い場合、当該分散処理部v1の処理負荷が大きいと判定する。この所定値(閾値)は適宜設定される。このように特定の分散処理部v1のみが遅れ被疑メッセージの受信量が多い場合、この特定の分散処理部v1の処理が重いことが、worker1における進行の遅れの原因であると検出することができる。以下では、この原因のことを原因1ともいう。

0059

また、本実施形態では、処理サーバ30(worker1)の負荷判定部32(図2参照)は、自処理サーバ30(worker1)上で動作する複数の分散処理部v1、v2、v3に対して通知される遅れ被疑メッセージの受信量がそれぞれ所定値よりも多い場合、自処理サーバ30(worker1)の処理負荷が大きいと判定する。この所定値(閾値)も適宜設定される。このように自処理サーバ30(worker1)で担当する複数の分散処理部v1、v2、v3に通知される遅れ被疑メッセージの受信量が全体的に多い場合、自処理サーバ30(worker1)が過負荷であることが、worker1における進行の遅れの原因であると検出することができる。以下では、この原因のことを原因2ともいう。

0060

ここで、処理サーバ30における処理の進行が遅れる原因(原因1、原因2)について
図9(a)及び図9(b)を参照して説明する。2台の処理サーバ30(worker1、worker2)において、worker1が担当する各頂点v1、v2、v3がローカル計算に要する時間は、図7及び図8(a)に示す時間とは異なっている。
図9(a)は、worker1が担当する分散処理部v1、v2、v3のうち、分散処理部v2がローカル計算に他の分散処理部よりも長い時間を要している状況を例示している。
一方、図9(b)は、worker1が担当する分散処理部v1、v2、v3それぞれが、worker2が担当する分散処理部v4、v5、v6よりもローカル計算に長い時間を要している状況を例示している。

0061

既存の同期処理システムのフレームワークでは、管理サーバが処理サーバ(worker)単位で計算処理の進行状況を管理するので、図9(a)及び図9(b)に例示したような状況が発生した場合、どちらも、worker1が遅れている、と検出し、それ以上のことは何も分からなかった。
これに対して、本実施形態の分散同期処理システム1では、処理サーバ30(worker1)の負荷判定部32(図2参照)が、自処理サーバ30(worker1)で管理する分散処理部20(vertex)が受信する遅れ被疑メッセージの受信量に基づいて、自処理サーバ30(worker1)が遅れる原因(原因1又は原因2)を特定することができる。また、図9(a)及び図9(b)に例示したような状況が発生した場合、特定の分散処理部20の処理が重いことが原因(原因1)であるのか、自処理サーバ30(worker)が過負荷であることが原因(原因2)であるのか、原因を切り分けることができる。

0062

以上説明したように、本実施形態の分散同期処理システム1では、各処理サーバ30(worker)上で動作する分散処理部20(vertex)が互いに自律的に遅れを監視して必要に応じて遅れ被疑メッセージを送信するので、管理サーバ10の負担を重くせずに分散処理の進行状況を細かく監視しつつ計算処理の遅れを検出することができる。
また、交差点単位で頂点(vertex)を定め、分散同期処理を実行することにより、大規模な交通システムであっても、管理サーバ10の負担を重くせずに分散処理の進行状況を細かく監視しつつ計算処理の遅れを検出しながら、システムの挙動を短時間でシミュレートすることができる。

0063

(第2実施形態)
第1実施形態のように、隣接する分散処理部20(vertex)同士で、処理の進行の遅れがないか互いに監視する場合、特定の分散処理部20の遅れに起因して、そこからoutgoing edgeでつながる分散処理部20も遅れていると検出される場合が想定される。例えば図10(a)に示す計算対象のグラフGの場合、分散処理部v6が遅れると、その下流で分散処理部v6からの計算結果を待っている分散処理部v4が遅れることになる。そして、この分散処理部v4が遅れると、その下流で分散処理部v4からの計算結果を待っている分散処理部v2、v3、v5がそれぞれ遅れることになる。

0064

また、特定の分散処理部20からoutgoing edgeでつながる分散処理部20が、既に自らの計算結果を完了した後に、その特定の分散処理部20の計算結果を待っている状態であれば、進行の遅れの真の原因とは言えない。しかしながら、当該結果待ちの分散処理部20のoutgoing edgeで接する分散処理部20は、その結果待ちの分散処理部20の進行が遅れていると判定して遅れ被疑メッセージを送信することになる。そうすると、結果待ちの分散処理部20の遅れ被疑メッセージ受信量管理部24(図2参照)が管理する受信量には、進行の遅れの真の原因が反映されず、この受信量に基づいた対処が適切ではなくなる可能性がある。

0065

そこで、第2実施形態に係る分散同期処理システムでは、分散処理部20が、図2に示すように、遅れ被疑メッセージ転送処理部25Bを備えることとした。
被疑メッセージ転送処理部25Bは、遅れ被疑メッセージを受信したときに、他分散処理部20から送信される計算結果メッセージの待機状態である場合、遅れ被疑メッセージの受信量をカウントさせずに、受信した遅れ被疑メッセージを当該他分散処理部20に転送する。

0066

具体的には、図10(a)に示す計算対象のグラフGの場合、図10(b)に示すように、分散処理部v2は、隣接する分散処理部v3が遅れていると判定すると、遅れ被疑メッセージM1を送信する。この遅れ被疑メッセージM1が通知された分散処理部v3は、分散処理部v4からの計算結果を待っている状態であれば、このM1を自らの遅れ被疑メッセージの受信量にカウントせずに遅れ被疑メッセージM2として分散処理部v4に転送する。
また、この遅れ被疑メッセージM2が通知される分散処理部v4には、同様に、outgoing edgeで接する分散処理部v2、v5からも遅れ被疑メッセージM3、M4が通知される。
さらに、遅れ被疑メッセージM2、M3、M4が通知された分散処理部v4は、分散処理部v6からの計算結果を待っている状態であれば、これらM2、M3、M4を遅れ被疑メッセージの受信量にカウントせずに遅れ被疑メッセージM5として分散処理部v6に転送する。
したがって、転送される遅れ被疑メッセージの受信量には、遅れの影響度合が反映されることになる。つまり、図10(b)の分散処理部v6のように、遅れの影響範囲が広いほど(outgoingで連鎖する頂点(vertex)が多いほど)遅れ被疑メッセージの受信量が増大し、いち早く遅れが確定されることになる。これにより、遅れを正確に検出する精度を向上させることができる。

0067

(第3実施形態)
第3実施形態に係る分散同期処理システムでは、分散処理部20が、図2に示すように、故障検出部26Cを備えることとした。
故障検出部26Cは、遅れ被疑メッセージの受信時に、受信完了を示す信号(ACK)を送信側に返させ、受信完了を示す信号(ACK)が返ってこない場合、予め定められた回数だけ遅れ被疑メッセージを再送させる。これにより、メッセージ送受信部22は、遅れ被疑メッセージの受信時に、受信完了を示す信号を送信側に返す。そして、故障検出部26Cは、遅れ被疑メッセージを予め定められた回数だけ再送させても受信完了を示す信号が返ってこない場合、故障として検出する。したがって、処理の遅れの原因が故障である場合に適切に対処することができる。

0068

(第4実施形態)
第4実施形態に係る分散同期処理システムでは、処理サーバ30は、図2に示すように、負荷委譲要求部33Dを備えることとした。
負荷委譲要求部33Dは、自処理サーバ30上で動作する特定の分散処理部20(vertex)の処理負荷が大きいと判定された場合、当該特定の分散処理部20についての委譲要求を管理サーバ10に通知する。
管理サーバ10は、この委譲要求が通知されると、この特定の分散処理部20を、委譲要求を通知した処理サーバ30よりも処理能力の高い処理サーバ30に割り当てる。
これにより、処理サーバ30は、前記した原因1のときに、自ら担当する分散処理部20(vertex)を委譲することで、検出した原因1に適切に対処することが可能となる。

0069

(第5実施形態)
第5実施形態に係る分散同期処理システムでは、検出した原因2に対処するように、第4実施形態を変形したものである。したがって、第4実施形態と同様に、処理サーバ30は、図2に示すように、負荷委譲要求部33Dを備えることとした。
ただし、第5実施形態では、負荷委譲要求部33Dは、自処理サーバ30の処理負荷が大きいと判定された場合に、自処理サーバ30上で動作する複数の分散処理部20(vertex)のうちの一部についての委譲要求を管理サーバ10に通知する。
管理サーバ10は、この委譲要求が通知されると、委譲要求を通知した処理サーバ30上で動作する複数の分散処理部20のうちの一部を、他処理サーバ30に割り当てる。
これにより、処理サーバ30は、前記した原因2のときに、自ら担当する複数の分散処理部20(vertex)のうちの一部を委譲することで、検出した原因2に適切に対処することが可能となる。

0070

(第5実施形態の変形例)
この変形例では、第4、5実施形態に係る分散同期処理システムと同様に、検出した原因1、2の双方に対処するように変形したものである。すなわち、管理サーバ10は、特定の分散処理部20(vertex)の委譲要求を受けると、この特定の分散処理部20を、委譲要求を通知した処理サーバ30よりも処理能力の高い処理サーバ30に割り当て、一方、複数の分散処理部20(vertex)のうちの一部についての委譲要求を受けると、この一部の分散処理部20を他処理サーバ30に割り当てる。

0071

(第6実施形態)
第6実施形態に係る分散同期処理システムでは、処理サーバ30は、図2に示すように、負荷調整部34Eを備えることとした。
負荷調整部34Eは、自処理サーバ30上で動作する特定の分散処理部20(vertex)の処理負荷が大きいと判定された場合、又は、自処理サーバ30の処理負荷が大きいと判定された場合、処理負荷調整要求を管理サーバ10に通知する。
管理サーバ10は、処理負荷調整要求が通知されると、既に複数の処理サーバ30に対して割り当てた全ての分散処理部20を、処理負荷調整要求を通知した処理サーバ30に関する処理負荷を低減した新たな配置で、複数の処理サーバ30に対して再度割り当てる。
ここで、再割り当ての前後では、通常、処理負荷調整要求を通知した処理サーバ30から、他の処理サーバ30への通信コストも発生するので、再割り当ての前後で発生する通信コストをできるだけ低く抑えられように再割り当てをすることが好ましい。なお、管理サーバ10は、全ての分散処理部20(vertex)の配置をリフレッシュしてもよいが、必須ではない。

0072

本発明は前記した各実施形態に限定されるものではなく、種々の変形が可能であり、第2〜第6実施形態の少なくとも2つを第1実施形態に組み合わせても構わない。また、以下のように変形してもよい。例えば、処理サーバ30の台数は、複数台であれば特に限定されず、計算対象とするステムの規模等に応じて適宜設定される。処理サーバ30上の分散処理部20(vertex)の個数も特に限定されず、100個以上でも構わない。

0073

また、スーパーステップにおいて、処理サーバ30は、頂点(vertex)毎に、計算・送信処理が完了すると、outgoing edgeで接する頂点(vertex)への計算結果メッセージをバッファリングせずに直ちに送信するものとしたが、これに限定されるものではない。例えば、図8(b)のworker2が担当する頂点v4のように、頂点v4から頂点v2への送信、及び、頂点v4から頂点v3への送信が、いずれも、外部のworker1への送信であれば、worker2の図示しない送受信管理部が、それぞれの計算結果メッセージをバッファリングしてまとめて送信する。このworker2のような処理をすることで、外部のworkerへの通信回数を削減することができ、通信コストを低減することができる。ただし、バッファリングが原因となって計算結果メッセージの送信処理が遅れてしまうと、隣接する頂点から遅れ被疑メッセージを通知される可能性がある。よって、分散処理の遅れを検出するための精度と、計算結果メッセージの通信コストの低減効果とはトレードオフの関係があると考えられるので、対象とする計算処理の内容や規模に応じて、どちらを優先するか適宜設定する必要がある。なお、図8(a)のworker1が担当する頂点v1〜v3のように、頂点v1から頂点v2への送信、頂点v2から頂点v3への送信、及び、頂点v3から頂点v2への送信が、いずれも、自処理サーバ30内で完結していれば、計算結果メッセージをバッファリングせずに直ちに送信する。

0074

また、分散処理部20のメッセージ送受信部22は、例えば、隣接した他分散処理部20に対して、遅れ被疑メッセージを通知するものとしたが、処理サーバ30の図示しない送信管理部に送信してもよい。この場合、遅れ被疑メッセージを通知された処理サーバ30の送信管理部が、その遅れ被疑メッセージの発信元の分散処理部20が遅れていると判定した、通知すべき宛先の他分散処理部20へ通知すればよい。

0075

また、前記第4、第5実施形態では、処理サーバ30が負荷委譲要求部33Dを備えることにより、管理サーバ10は、委譲要求を処理する必要がある。このために、管理サーバ10は、処理サーバ30の状況を把握する。このときの把握方法としては、管理サーバ10の負荷が大きくならない手法を採用することが好ましい。例えば、全ての処理サーバ30の計算時間を常時把握するのではなく、より少ない頻度サンプリングするなどの重たくない処理を併用して、全数調査ではなく統計的に計算時間を収集する手法が挙げられる。

0076

また、委譲要求を管理サーバ10に通知する処理サーバ30は、処理負荷が重いので、その担当する分散処理部20が遅れ被疑メッセージを受けている可能性が高い。より自律的に負荷分散させるために、処理サーバ30が自己に隣接する処理サーバ30の情報しか知り得ない場合は、管理サーバ10は、委譲要求を受けたときに、遅れ被疑メッセージを通知した分散処理部20を担当する処理サーバ30のことを、分散処理部20(vertex)の委譲先と決定してもよい。なお、この場合には、遅れ被疑メッセージを通知した側の分散処理部20は、そのことを管理サーバ10に予め報告しておく。

0077

1 分散同期処理システム
10管理サーバ(master)
20分散処理部(vertex)
21数値計算部
22メッセージ送受信部
23受信時刻監視部
24遅れ被疑メッセージ受信量管理部
25B 遅れ被疑メッセージ転送処理部
26C故障検出部
30処理サーバ(worker)
31仮想化制御部
32負荷判定部
33D負荷委譲要求部
34E負荷調整部

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

該当するデータがありません

関連する公募課題

該当するデータがありません

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

(分野番号表示ON)※整理標準化データをもとに当社作成

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

  • みずほ情報総研株式会社の「 影響調査システム、影響調査方法及び影響調査プログラム」が 公開されました。( 2019/09/19)

    【課題】複数の情報処理が実行されるシステム内で利用される情報の影響範囲を予測するための影響調査システム、影響調査方法及び影響調査プログラムを提供する。【解決手段】影響調査システム20の制御部21が、ジ... 詳細

  • 三菱電機株式会社の「 制御システム」が 公開されました。( 2019/09/19)

    【課題】センサ構成の変更、制御プログラムの更新等によって処理負荷が増大する状況に確実に対応することができる制御システムを提供する。【解決手段】車両制御システム100は、既設ECU101に対して新設20... 詳細

  • 富士通株式会社の「 制御方法、情報処理装置および制御プログラム」が 公開されました。( 2019/09/12)

    【課題】利用者は、物理マシンを使いたいときに使いたいスペック、機種の物理マシンを使うことが可能となる。【解決手段】情報処理装置1は、物理マシンの使用要求を受け付けると、記憶部に記憶された物理マシンと予... 詳細

この 技術と関連性が強い技術

関連性が強い 技術一覧

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

該当するデータがありません

この 技術と関連する公募課題

該当するデータがありません

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ