図面 (/)

技術 分散同期処理システムおよび分散同期処理方法

出願人 日本電信電話株式会社株式会社エヌ・ティ・ティ・データ
発明者 小林弘明北野雄大岡本光浩福元健米森力堤田恭太矢実貴志大谷智洋司南
出願日 2016年8月26日 (3年7ヶ月経過) 出願番号 2016-166182
公開日 2018年3月1日 (2年0ヶ月経過) 公開番号 2018-032344
状態 特許登録済
技術分野 マルチプログラミング
主要キーワード 同期並列 同期バー 入力エッジ 出力エッジ 計算終了後 イテレーション active状態 接バー
関連する未来課題
重要な関連分野

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

図面 (13)

課題

同期処理に伴うシステム全体の処理遅延を低減することができる、分散同期処理システムおよび分散同期処理方法を提供する。

解決手段

分散同期処理システム1の処理サーバ30は、分散処理部20による所定の計算ステップにおける計算・送信処理の完了を検出して、完了報告管理サーバ10に送信するとともに、管理サーバ10から次ステップ移行指示を受信して分散処理部20に出力する分散処理管理部バーテックス管理部33)を備える。管理サーバ10は、完了報告を受信し、次の計算ステップにおいて必要な計算結果の取得が完了しているか否かを判定し、取得が完了しているときに次ステップ移行指示を処理サーバ30に送信する隣接同期処理部11を備える。

概要

背景

ネットワーク上に複数のサーバ分散配置する分散処理システムフレームワークとして、非特許文献1にはMapReduceが開示されている。但し、このMapReduceは、処理の度に、外部のデータストアからの入力データの読み込みや、結果の書き出し処理が必要であるため、ある処理の結果を次の処理で利用するようなイテレティブな(反復する)処理には向いていない。この種の処理には、非特許文献2に開示されているBSP(Bulk Synchronous Parallel:バル同期並列)が適している。

このBSPは、「スーパーステップSS:superstep)」という処理単位を繰り返し実行することにより、分散環境でのデータ処理を実行する。図1は、BSP計算モデルを説明するための図である。

1つのスーパーステップは、図1に示すように、次の3つのフェーズ(PH:phase)、「ローカル計算(LC:Local computation)」(フェーズPH1)、「データ交換(Com:Communication)」(フェーズPH2)、「同期(Sync)」(フェーズPH3)から構成される。
具体的には、複数のノード(ノード1〜ノード4)のうちのいずれかのノードがデータを受信すると、そのノード(例えば、ノード1)がフェーズPH1において、そのデータについての計算処理(ローカル計算(LC))を実行する。続いて、フェーズPH2において、各ノードが保持しているローカル計算の結果であるデータについて、ノード間でのデータ交換を実行する。次に、フェーズPH3において、同期処理を行う、より詳細には、すべてのノード間でのデータ交換の終了を待つ。
そして、スーパーステップSS1として、一連のスーパーステップの処理(PH1〜PH3)が終了すると、各ノードはその計算結果を保持した上で、次の一連の処理であるスーパーステップSS2へと進む。

このBSPを採用した分散処理フレームワークとして、非特許文献3にはPregelが開示されている。このPregel等のフレームワークでは、全体の処理をグラフG=(V,E)として表現し、これをBSPに適用して実行する。ここで、Vは「バーテックス(vertex:頂点)の集合」であり、Eは「エッジ(edge:辺)の集合」を意味する。

ここで、図2を参照し、交通シミュレーションにBSPを適用した例を説明する。
図2においては、各交差点(v)がバーテックス(vertex)に対応付けられる(図2のv1〜v4)。また、各交差点を結ぶ道路(e)がエッジ(edge)に対応付けられる(図2のe1〜e6)。ここで、エッジ(edge)は一方通行であり、双方向の道路は2つのエッジに対応付けられる。また、あるバーテックス(vertex)から見て、車両が出てゆく方向のエッジを、「出力エッジ(outgoing edge)」と呼び、車両が流入する方向のエッジを「入力エッジ(incoming edge)」と呼ぶ。例えば、図2において、バーテックスv2からみると、エッジe1は入力エッジであり、エッジe2は出力エッジになる。逆に、バーテックスv1からみると、エッジe1は出力エッジであり、エッジe2は入力エッジになる。

図1で示したスーパーステップでは、フェーズPH1(ローカル計算)において、バーテックス(vertex)毎に、経過時間(Δt)における、各バーテックスv1〜v4に対応付けられている交差点の状態(例えば、信号の色(青、黄、赤)や交差点内の車両の動き等)と、それに付随する出力エッジとしての道路内の状態(車両の動き(台数・平均速度等))とをシミュレートする。フェーズPH2(データ交換)では、あるバーテックスは、出力エッジを介して接する他のバーテックスに対して、当該出力エッジを介して出てゆく車両の動きの情報(台数等)を送信するとともに、入力エッジを介して入ってくる車両の動きの情報(台数等)を受信する。フェーズPH3(同期)では、バーテックス間で、シミュレーション時刻tを同期する。つまり、全てのバーテックス間でデータ交換の完了を待つ。
この交通シミュレーションにおいては、このように交差点(バーテックス)単位で、並列処理することにより、計算時間を短縮することが可能となる。

概要

同期処理に伴うシステム全体の処理遅延を低減することができる、分散同期処理システムおよび分散同期処理方法を提供する。分散同期処理システム1の処理サーバ30は、分散処理部20による所定の計算ステップにおける計算・送信処理の完了を検出して、完了報告管理サーバ10に送信するとともに、管理サーバ10から次ステップ移行指示を受信して分散処理部20に出力する分散処理管理部(バーテックス管理部33)を備える。管理サーバ10は、完了報告を受信し、次の計算ステップにおいて必要な計算結果の取得が完了しているか否かを判定し、取得が完了しているときに次ステップ移行指示を処理サーバ30に送信する隣接同期処理部11を備える。

目的

本発明では、前記した問題を解決し、同期処理に伴うシステム全体の処理遅延を低減することができる、分散同期処理システムおよび分散同期処理方法を提供する

効果

実績

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

この技術が所属する分野

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

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

請求項1

並列に処理を行う複数の処理サーバと、前記処理サーバ上で動作する複数の分散処理部と、対象とする計算処理に必要な複数の前記分散処理部を複数の前記処理サーバに対して割り当てる管理サーバと、を有する分散同期処理システムであって、前記処理サーバは、前記分散処理部による所定の計算ステップにおける、計算処理および計算結果出力先として接続された分散処理部への送信処理を示す計算・送信処理の完了を検出し、前記計算・送信処理の完了を示す完了報告を生成して、前記管理サーバに送信するとともに、前記管理サーバから次の前記計算ステップへの移行の指示である次ステップ移行指示を受信し、前記計算・送信処理を完了した分散処理部に出力する分散処理管理部を備え、前記管理サーバは、前記完了報告を受信し、前記計算・送信処理を完了した分散処理部が、次の前記計算ステップにおいて必要な計算結果の取得が完了しているか否かを前記計算結果の入力元として接続された分散処理部からの完了報告を受信しているか否かに基づき判定し、前記計算結果の取得が完了しているときに、前記次ステップ移行指示を前記完了報告を送信してきた処理サーバに送信する隣接同期処理部を備えることを特徴とする分散同期処理システム。

請求項2

並列に処理を行う複数の処理サーバと、前記処理サーバ上で動作する複数の分散処理部と、を有する分散同期処理システムであって、前記処理サーバは、前記分散処理部による所定の計算ステップにおける、計算処理および計算結果の出力先として接続された分散処理部への送信処理を示す計算・送信処理の完了を検出し、前記計算・送信処理を完了した分散処理部が、計算結果の入力元として接続された分散処理部から、次の前記計算ステップにおいて必要な計算結果の取得が完了しているか否かを判定し、前記計算結果の取得が完了しているときに、次の前記計算ステップへの移行の指示である次ステップ移行指示を、前記計算・送信処理を完了した分散処理部に出力する隣接同期分散管理部を備えることを特徴とする分散同期処理システム。

請求項3

並列に処理を行う複数の処理サーバと、前記処理サーバ上で動作する複数の分散処理部と、対象とする計算処理に必要な複数の前記分散処理部を複数の前記処理サーバに対して割り当てる管理サーバと、を有する分散同期処理システムの分散同期処理方法であって、前記処理サーバは、前記分散処理部による所定の計算ステップにおける、計算処理および計算結果の出力先として接続された分散処理部への送信処理を示す計算・送信処理の完了を検出し、前記計算・送信処理の完了を示す完了報告を生成して、前記管理サーバに送信する手順と、前記管理サーバから次の前記計算ステップへの移行の指示である次ステップ移行指示を受信し、前記計算・送信処理を完了した分散処理部に出力する手順と、を実行し、前記管理サーバは、前記完了報告を受信し、前記計算・送信処理を完了した分散処理部が、次の前記計算ステップにおいて必要な計算結果の取得が完了しているか否かを前記計算結果の入力元として接続された分散処理部からの完了報告を受信しているか否かに基づき判定し、前記計算結果の取得が完了しているときに、前記次ステップ移行指示を前記完了報告を送信してきた処理サーバに送信する手順を実行することを特徴とする分散同期処理方法。

請求項4

並列に処理を行う複数の処理サーバと、前記処理サーバ上で動作する複数の分散処理部と、を有する分散同期処理システムの分散同期処理方法であって、前記処理サーバは、前記分散処理部による所定の計算ステップにおける、計算処理および計算結果の出力先として接続された分散処理部への送信処理を示す計算・送信処理の完了を検出する手順と、前記計算・送信処理を完了した分散処理部が、計算結果の入力元として接続された分散処理部から、次の前記計算ステップにおいて必要な計算結果の取得が完了しているか否かを判定し、前記計算結果の取得が完了しているときに、次の前記計算ステップへの移行の指示である次ステップ移行指示を、前記計算・送信処理を完了した分散処理部に出力する手順と、を実行することを特徴とする分散同期処理方法。

技術分野

0001

本発明は、分散配置された複数のサーバを同期させて処理を実行する分散同期処理システムおよび分散同期処理方法に関する。

背景技術

0002

ネットワーク上に複数のサーバを分散配置する分散処理システムフレームワークとして、非特許文献1にはMapReduceが開示されている。但し、このMapReduceは、処理の度に、外部のデータストアからの入力データの読み込みや、結果の書き出し処理が必要であるため、ある処理の結果を次の処理で利用するようなイテレティブな(反復する)処理には向いていない。この種の処理には、非特許文献2に開示されているBSP(Bulk Synchronous Parallel:バル同期並列)が適している。

0003

このBSPは、「スーパーステップSS:superstep)」という処理単位を繰り返し実行することにより、分散環境でのデータ処理を実行する。図1は、BSP計算モデルを説明するための図である。

0004

1つのスーパーステップは、図1に示すように、次の3つのフェーズ(PH:phase)、「ローカル計算(LC:Local computation)」(フェーズPH1)、「データ交換(Com:Communication)」(フェーズPH2)、「同期(Sync)」(フェーズPH3)から構成される。
具体的には、複数のノード(ノード1〜ノード4)のうちのいずれかのノードがデータを受信すると、そのノード(例えば、ノード1)がフェーズPH1において、そのデータについての計算処理(ローカル計算(LC))を実行する。続いて、フェーズPH2において、各ノードが保持しているローカル計算の結果であるデータについて、ノード間でのデータ交換を実行する。次に、フェーズPH3において、同期処理を行う、より詳細には、すべてのノード間でのデータ交換の終了を待つ。
そして、スーパーステップSS1として、一連のスーパーステップの処理(PH1〜PH3)が終了すると、各ノードはその計算結果を保持した上で、次の一連の処理であるスーパーステップSS2へと進む。

0005

このBSPを採用した分散処理フレームワークとして、非特許文献3にはPregelが開示されている。このPregel等のフレームワークでは、全体の処理をグラフG=(V,E)として表現し、これをBSPに適用して実行する。ここで、Vは「バーテックス(vertex:頂点)の集合」であり、Eは「エッジ(edge:辺)の集合」を意味する。

0006

ここで、図2を参照し、交通シミュレーションにBSPを適用した例を説明する。
図2においては、各交差点(v)がバーテックス(vertex)に対応付けられる(図2のv1〜v4)。また、各交差点を結ぶ道路(e)がエッジ(edge)に対応付けられる(図2のe1〜e6)。ここで、エッジ(edge)は一方通行であり、双方向の道路は2つのエッジに対応付けられる。また、あるバーテックス(vertex)から見て、車両が出てゆく方向のエッジを、「出力エッジ(outgoing edge)」と呼び、車両が流入する方向のエッジを「入力エッジ(incoming edge)」と呼ぶ。例えば、図2において、バーテックスv2からみると、エッジe1は入力エッジであり、エッジe2は出力エッジになる。逆に、バーテックスv1からみると、エッジe1は出力エッジであり、エッジe2は入力エッジになる。

0007

図1で示したスーパーステップでは、フェーズPH1(ローカル計算)において、バーテックス(vertex)毎に、経過時間(Δt)における、各バーテックスv1〜v4に対応付けられている交差点の状態(例えば、信号の色(青、黄、赤)や交差点内の車両の動き等)と、それに付随する出力エッジとしての道路内の状態(車両の動き(台数・平均速度等))とをシミュレートする。フェーズPH2(データ交換)では、あるバーテックスは、出力エッジを介して接する他のバーテックスに対して、当該出力エッジを介して出てゆく車両の動きの情報(台数等)を送信するとともに、入力エッジを介して入ってくる車両の動きの情報(台数等)を受信する。フェーズPH3(同期)では、バーテックス間で、シミュレーション時刻tを同期する。つまり、全てのバーテックス間でデータ交換の完了を待つ。
この交通シミュレーションにおいては、このように交差点(バーテックス)単位で、並列処理することにより、計算時間を短縮することが可能となる。

先行技術

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

上記のような、BSPを採用した分散処理フレームワークを実現するためのアーキテクチャとして、master/worker構成が採用されている。図3に示すように、master/worker構成は、処理単位となるバーテックス20aを複数備えるworker(処理サーバ30a)が複数台と、workerの処理について進行状況の管理等を行うmaster(管理サーバ10a)1台とで、構成される。

0010

ここで、master(管理サーバ10a)の役割は、worker(処理サーバ30a)への処理(バーテックス20a)の割り振り(グラフGのパーティショニング)、workerの処理の進行状況の管理、全workerに共通となる全体としてのスーパーステップの管理、バーテックスやエッジの追加や削除に伴うグラフトポロジの管理等である。
また、worker(処理サーバ30a)の役割は、各スーパーステップにおけるフェーズPH1のローカル計算、フェーズPH2における、隣接するバーテックスとの間のデータの送受信、masterへの報告である。

0011

既存のフレームワークにおけるアーキテクチャの多くは、このmaster/worker構成を採用しており、BSPが適用されるときには、workerは、自身が備える全てのバーテックスの処理(フェーズPH1,2)が完了すると、masterに報告する。masterは、全workerからの報告を受けると、スーパーステップを「+1」し、次のスーパーステップに移行するように、各workerに指示を出すこととなる。

0012

しかしながら、上記の構成では、スーパーステップ毎に、全バーテックスを同期するため、最も処理が遅いバーテックスにあわせることとなる。よって、たった一つでも全体から著しく遅いバーテックスがあると、その影響が全体に及ぶ。つまり、最も処理が遅いバーテックスにあわせて、全体が著しく遅延してしまう。
また、大規模なグラフGを処理対象とする場合、つまり、多数のバーテックスとエッジを備えた計算対象を扱うときには、master/worker構成では、一つのmasterでグラフ全体を管理するため、グラフGの規模が大きいと、masterがボトルネックとなってしまう。

0013

そこで、本発明では、前記した問題を解決し、同期処理に伴うシステム全体の処理遅延を低減することができる、分散同期処理システムおよび分散同期処理方法を提供することを課題とする。

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

0014

前記した課題を解決するため、請求項1に記載の発明は、並列に処理を行う複数の処理サーバと、前記処理サーバ上で動作する複数の分散処理部と、対象とする計算処理に必要な複数の前記分散処理部を複数の前記処理サーバに対して割り当てる管理サーバと、を有する分散同期処理システムであって、前記処理サーバが、前記分散処理部による所定の計算ステップにおける、計算処理および計算結果の出力先として接続された分散処理部への送信処理を示す計算・送信処理の完了を検出し、前記計算・送信処理の完了を示す完了報告を生成して、前記管理サーバに送信するとともに、前記管理サーバから次の前記計算ステップへの移行の指示である次ステップ移行指示を受信し、前記計算・送信処理を完了した分散処理部に出力する分散処理管理部を備え、前記管理サーバが、前記完了報告を受信し、前記計算・送信処理を完了した分散処理部が、次の前記計算ステップにおいて必要な計算結果の取得が完了しているか否かを前記計算結果の入力元として接続された分散処理部からの完了報告を受信しているか否かに基づき判定し、前記計算結果の取得が完了しているときに、前記次ステップ移行指示を前記完了報告を送信してきた処理サーバに送信する隣接同期処理部を備えることを特徴とする分散同期処理システムとした。

0015

また、請求項3に記載の発明は、並列に処理を行う複数の処理サーバと、前記処理サーバ上で動作する複数の分散処理部と、対象とする計算処理に必要な複数の前記分散処理部を複数の前記処理サーバに対して割り当てる管理サーバと、を有する分散同期処理システムの分散同期処理方法であって、前記処理サーバが、前記分散処理部による所定の計算ステップにおける、計算処理および計算結果の出力先として接続された分散処理部への送信処理を示す計算・送信処理の完了を検出し、前記計算・送信処理の完了を示す完了報告を生成して、前記管理サーバに送信する手順と、前記管理サーバから次の前記計算ステップへの移行の指示である次ステップ移行指示を受信し、前記計算・送信処理を完了した分散処理部に出力する手順と、を実行し、前記管理サーバが、前記完了報告を受信し、前記計算・送信処理を完了した分散処理部が、次の前記計算ステップにおいて必要な計算結果の取得が完了しているか否かを前記計算結果の入力元として接続された分散処理部からの完了報告を受信しているか否かに基づき判定し、前記計算結果の取得が完了しているときに、前記次ステップ移行指示を前記完了報告を送信してきた処理サーバに送信する手順を実行することを特徴とする分散同期処理方法とした。

0016

このように、分散同期処理システムは、管理サーバが、分散処理部ごとに、次の計算ステップに移行してよいのかを判定することができる。よって、全ての分散処理部の計算・送信処理の終了まで待機する必要がないため、同期処理に伴うシステム全体の処理遅延を低減することができる。

0017

請求項2に記載の発明は、並列に処理を行う複数の処理サーバと、前記処理サーバ上で動作する複数の分散処理部と、を有する分散同期処理システムであって、前記処理サーバが、前記分散処理部による所定の計算ステップにおける、計算処理および計算結果の出力先として接続された分散処理部への送信処理を示す計算・送信処理の完了を検出し、前記計算・送信処理を完了した分散処理部が、計算結果の入力元として接続された分散処理部から、次の前記計算ステップにおいて必要な計算結果の取得が完了しているか否かを判定し、前記計算結果の取得が完了しているときに、次の前記計算ステップへの移行の指示である次ステップ移行指示を、前記計算・送信処理を完了した分散処理部に出力する隣接同期分散管理部を備えることを特徴とする分散同期処理システムとした。

0018

また、請求項4に記載の発明は、並列に処理を行う複数の処理サーバと、前記処理サーバ上で動作する複数の分散処理部と、を有する分散同期処理システムの分散同期処理方法であって、前記処理サーバが、前記分散処理部による所定の計算ステップにおける、計算処理および計算結果の出力先として接続された分散処理部への送信処理を示す計算・送信処理の完了を検出する手順と、前記計算・送信処理を完了した分散処理部が、計算結果の入力元として接続された分散処理部から、次の前記計算ステップにおいて必要な計算結果の取得が完了しているか否かを判定し、前記計算結果の取得が完了しているときに、次の前記計算ステップへの移行の指示である次ステップ移行指示を、前記計算・送信処理を完了した分散処理部に出力する手順と、を実行することを特徴とする分散同期処理方法とした。

0019

このように、分散同期処理システムは、処理サーバが、分散処理部ごとに、次の計算ステップに移行してよいのかを判定することができる。よって、全ての分散処理部の計算・送信処理の終了まで待機する必要がないため、同期処理に伴うシステム全体の処理遅延を低減することができる。
さらに、各処理サーバ自律分散的に、次の計算ステップへの移行を判定するため、処理サーバおよび分散処理部が多数となる大規模なシステムであっても、システム全体の処理遅延を低減することが可能となる。

発明の効果

0020

本発明によれば、同期処理に伴うシステム全体の処理遅延を低減する、分散同期処理システムおよび分散同期処理方法を提供することができる。

図面の簡単な説明

0021

BSP計算モデルを説明するための図である。
交通シミュレーションにBSP計算モデルを適用した例を説明するための図である。
比較例に係る分散同期処理システムのmaster/worker構成を説明するための図である。
バーテックスの構成要素の定義を説明するための図である。
1つのバーテックスの構成要素を例示する図である。
BSP計算モデルにおける計算対象のグラフを例示する図である。
比較例の分散同期処理システムにおける処理の流れを説明するための図である。
比較例に係る分散同期処理システムの処理の流れ(図8(a))と、本実施形態に係る分散同期処理システムの処理の流れ(図8(b))とを、説明するための図である。
本実施形態に係る分散同期処理システムの全体構成を示す図である。
本実施形態に係る分散同期処理システムの処理の流れを示すシーケンス図である。
本実施形態の変形例に係る分散同期処理システムの全体構成を示す図である。
本実施形態の変形例に係る分散同期処理システムの処理の流れを示すフローチャートである。

実施例

0022

<比較例の分散処理手法の内容と課題の詳細な説明>
初めに、本実施形態に係る分散同期処理システム1および分散同期処理方法の特徴構成を説明するため、比較例として従来技術における分散同期処理システム1aおよび分散同期処理方法を、詳細に説明する。

0023

比較例の分散同期処理システム1aは、図3に示したような、master/worker構成を採用し、複数のworkerそれぞれが、複数のバーテックス(vertex)を備える。そして、このmaster/worker構成にBSPを適用するとき、各workerは、自身が備える全てのバーテックスの処理(フェーズPH1,2)が完了するとmasterに報告し、masterは、全workerからの報告を受けると、スーパーステップを次のスーパーステップに移行する。

0024

ここで、バーテックスに着目すると、各バーテックスは、次に示す処理を実行する。
バーテックスは、BSPのフェーズPH1において、現在のバーテックスの状態、出力エッジの状態、および、前スーパーステップ(以下、単に「ステップ」と称することがある。)の入力メッセージにより取得した情報(入力エッジの状態)をパラメータとして計算を行い、バーテックスの状態および出力エッジの状態を更新する。そして、バーテックスは、フェーズPH2において、更新した出力エッジの状態を出力メッセージとして、その出力エッジに隣接するバーテックスに送信する。なお、この「出力エッジに隣接するバーテックス」は、「計算結果の出力先として接続されたバーテックス」を意味する。

0025

上記の処理(計算・送信処理)は、次の式(1)として表わすことができる。
f(vvid,n,Eout,n,Min,n-1)=(vvid,n+1,Eout,n+1,Mout,n) ・・・式(1)
ここで、バーテックスの各構成要素の定義について、図4に示す。

0026

図4に示すように、「vid」は、「vertex ID」を示す。「vvid,n」は、「バーテックスの状態」を示す。「n」は、現在のステップ(スーパーステップ)を示す。「Eout,n」は、出力エッジの状態の集合を示す。「Min,n」は、入力エッジの状態を示す入力メッセージのバッファに記憶される情報(現在のステップ用)を示す。「Min,n-1」は、入力メッセージのバッファに記憶される情報(1つ前のステップ用)を示す。「sn」は、現在のステップの「状態フラグ(active/inactive)」を示す。「sn+1」は、次のステップの「状態フラグ(active/inactive)」を示す。f(vvid,n,Eout,n,Min,n-1)=(vvid,n+1,Eout,n+1,Mout,n)は、式(1)において示したように、計算・送信処理を示す。ここで、以降、ステップ(スーパーステップ)nにおける計算・送信処理を、「計算・送信処理fn」と記載する。
なお、「sn」の状態フラグは、そのバーテックスがBSPのフェーズ1,2の処理を実行している間は、「active」の状態とし、フェーズPH3の同期処理で他のバーテックスの処理待ち状態であるときに、「inactive」の状態とする。また、「sn+1」は、次のステップの処理に移行する設定の場合に「active」の状態とし、シミュレーション処理の設定時間が終了したこと等により、次のステップにおいて処理を実行しない設定の場合に、「inactive」の状態とする。

0027

図5は、1つのバーテックスに注目した場合の構成要素を例示する図である。
図5に示すように、現在のステップ「n」における「vertex ID」が「1」のバーテックス「1」は、ステップ「n」おけるバーテックスの状態「v1,n」を保持する。また、バーテックス「1」は、出力エッジの状態として、「e1,3,n」をバーテックス「3」に出力し、「e1,4,n」をバーテックス「4」に出力する。そして、バーテックス「1」は、入力メッセージの情報(入力エッジの状態)として、バーテックス「2」から「m2,1,n」を受信し、バーテックス「3」から「m3,1,n」を受信する。

0028

worker(図3参照)は、自身が備えるバーテックス毎に、現在のステップ(スーパーステップ)の状態フラグ(active/inactive)と次のステップ(スーパーステップ)の状態フラグ(active/inactive)を管理する。また、workerは、自身に属するバーテックスから、他のworkerに属するバーテックスに出力エッジの状態を出力メッセージとして送信するときには、同じworkerに属するバーテックスへのメッセージバッファリングすることにより、まとめて送信するようにしてもよい。このようにすることで、通信コストを削減することができる。

0029

次に、図7を参照して、比較例の分散同期処理システム1aが実行する処理の流れについて説明する。なお、ここでは、グラフGの計算対象が、図6に示すグラフトポロジであるものとして説明する。また、図7に示すように、1台のmasterと2台のworker(worker1,worker2)で構成され、バーテックスv1〜v6のうち、バーテックスv1〜v3をworker1が担当し、バーテックスv4〜v6をworker2が担当するものとする。以下、全体の処理の流れを通して説明する。

0030

まず、masterは、図6に示すグラフGの各バーテックス(バーテックスv1〜v6)を、処理対象として設定しworkerに割り振る(ステップS101)、つまり、グラフGのパーティショニングを実行する。
ここでは、図6に示すように、バーテックスv1〜v6のうち、バーテックスv1〜v3をworker1に割り振り、バーテックスv4〜v6をworker2に割り振るものとする。

0031

続いて、各worker(worker1,worker2)は、担当するバーテックスのスーパーステップを実行する(ステップS102)。具体的には、フェーズPH1のローカル計算を実行し、スーパーステップの処理を開始する。

0032

次に、各workerは、自身が担当するバーテックスの処理の進行を監視し、各バーテックスが、フェーズPH2のデータ交換まで完了したか否かを判定する。そして、各workerは、担当する全てのバーテックスが、フェーズPH2までの処理を完了したと確認した場合に、各バーテックスの次のスーパーステップにおける状態フラグをmasterに報告(送信)する(ステップS103)。ここで、workerは、各バーテックスの次のスーパーステップにおける状態フラグとして「active」(次のスーパーステップの処理に移行する設定であること)を報告する。

0033

そして、masterは、全てのworker(worker1,worker2)から、処理の完了を示す状態フラグの報告を受けたか否かを確認する。masterは、全てのworkerから報告を受けた場合に、スーパーステップを「+1」に更新する(ステップS104)。
ここで、masterは、グラフトポロジに変更がある場合、例えば、バーテックスやエッジの追加や削除がある場合には、そのグラフトポロジの変更を、各workerに通知する。

0034

続いて、masterは、全てのworker(worker1,worker2)に対して、次にスーパーステップに移行するように指示する(ステップS105)。そして、各workerは、ステップS102〜S105を繰り返す。

0035

比較例の分散同期処理システム1aにおいては、スーパーステップ毎に、計算対象となる全てのバーテックスを同期する、具体的には、図7に示す全体同期ポイントにおいて同期するため、最も遅いバーテックスにあわせることとなる。例えば、図7のスーパーステップSS1では、バーテックスv1〜v6のうち、最も遅いバーテックスv2にあわせることとなる。また、スーパーステップSS2では、最も遅いバーテックスv6にあわせることとなる。よって、著しく遅いバーテックスがあると、そのバーテックスにあわせるために、バーテックスの処理全体が著しく遅延してしまう。
また、master/worker構成では、一つのmasterで全体を管理することになるため、グラフGの規模が大きくなった場合、つまり、バーテックスの数やworkerの数が多くなるときに、masterがボトルネックとなる。

0036

上記した全体としての処理速度の遅延や、フェーズPH3において処理をせず同期待ちが多いこと(処理の効率性)の問題(以下、「処理速度/効率性」の問題と称する。)を解決するために、非同期型の分散処理フレームワークが提案されている(例えば、非特許文献4参照)。
ここで、非特許文献4は、「Low, Y., et al., “Distributed GraphLab”, Proc. of the VLDB Endowment, 2012.」である。

0037

しかしながら、非特許文献4に記載の非同期型の分散処理フレームワークでは、処理速度/効率性と計算精度トレードオフの関係になるため、処理を設計する際におけるプログラマの負担(プラグラム複雑性)が増大してしまう。
具体的には、非同期型では、各バーテックスによって、同じスーパーステップを実行していることが保証されないため、プログラマが、バーテックス間の処理の追い越し上書きの考慮が必要となる。追い越されたイテレーション反復処理)は、無効になってしまうため、精度の低下をまねくこととなる。また、スーパーステップの追い越し数が無制限に増えることにより、精度の理論的保証が困難になってしまう。

0038

本実施形態に係る分散同期処理システム1(図9参照)および分散同期処理方法では、これらの問題に対し、同期型で、プログラマに優しい(つまり、処理の追い越しや上書きの考慮が不要となる)シンプルなフレームワークを提供しつつ、同期型で問題であった処理速度/効率性を改善することを課題とする。
さらに、masterのボトルネック化を回避し、大規模なグラフGでも処理速度/効率性を担保することを課題とする。

0039

なお、本来masterが実行するグラフトロポジの管理のうち、「要素(バーテックスおよびエッジ)の動的な追加」については、システムとして構成の変更等が必要となるため、本発明の適用対象外とし、「要素の動的な追加」の必要がないケースを本発明の対象とする。

0040

<本実施形態の概要
次に、本実施形態に係る分散同期処理システム1が実行する処理の概要について説明する。
本実施形態に係る分散同期処理システム1(後記する図9)では、master(後記する「管理サーバ10」)による全バーテックス(後記する「分散処理部20」)での同期処理を行わず、バーテックス毎に次のスーパーステップへの移行を判断することを特徴とする。これにより、分散同期処理システム1は、著しく処理の遅いバーテックスの影響を低減する。

0041

具体的には、分散同期処理システム1において、次のスーパーステップへの移行条件を「自バーテックスおよび入力エッジで接する全てのバーテックスの計算・送信処理fnが完了していること」と設定する。なお、「入力エッジで接する全てのバーテックス」は、計算結果の入力元として接続された全てのバーテックス」を意味する。以下、この「次のスーパーステップへの移行条件」を「隣接同期」と称する。この隣接同期の詳細を、図8を参照して説明する。

0042

図8は、図7において示した比較例の分散同期処理システム1aが実行する処理(図8(a)参照)と、本実施形態に係る分散同期処理システム1が実行する処理(図8(b)参照)とを示す図である。
本実施形態に係る分散同期処理システム1では、上記のように、「自バーテックスおよび入力エッジで接する全てのバーテックスの計算・送信処理fnが完了していること」(「隣接同期」)により、次のスーパーステップに移行する。

0043

例えば、図8(b)のバーテックスv2に着目すると、バーテックスv2は、入力エッジで接するバーテックスv1,v3,v4の計算・送信処理fnと自身の計算・送信処理fnが終わった時点が隣接同期する隣接同期ポイントとなる。ここでバーテックスv2は、スーパーステップSS1のとき、自身の計算・送信処理f1の終了がバーテックスv1,v3,v4より遅く一番後であったので、その時点が隣接同期ポイントとなっている。
バーテックスv3に着目すると、バーテックスv3は、入力エッジで接するバーテックスv2,v4の計算・送信処理fnと自身の計算・送信処理fnが終わった時点が隣接同期する隣接同期ポイントとなる。ここでバーテックスv3は、スーパーステップSS1のとき、自身の計算・送信処理f1が終わった時点では、バーテックスv4の計算・送信処理f1は終わっているが、バーテックスv2の計算・送信処理f1が終わっていないため、「inactive」の状態で待機し(図8(b)の符号α)、バーテックスv2の計算・送信処理f1が終わった時点が隣接同期する隣接同期ポイントとなる。
また、バーテックスv1に着目すると、バーテックスv1は、入力エッジで接するバーテックスは存在しない、よって、スーパーステップSS1のとき、自バーテックスの計算・送信処理f1が終了した時点が隣接同期する隣接同期ポイントとなる。

0044

図8(b)に示すように、処理全体のある時点でみると、各バーテックス間においてスーパーステップがずれる可能性がある。そのため、バーテックス間でメッセージを送受信するときには上書きせずに、スーパーステップ毎に管理する。つまり、スーパーステップの情報(ステップ番号)をあわせて記憶するようにする。そのため、図4において示したバーテックスの要素に加え、本実施形態における各バーテックスは、「Min,n+m」を入力メッセージのバッファに記憶する。ここで、「Min,n+m」は、ステップ番号n+m(「m」は正の整数)において、入力エッジの状態としてバッファに記憶される情報を示す。各バーテックスは、自身のスーパーステップ(例えば、ステップ番号「n」(現在のステップ))よりも先に、次のスーパーステップに移行したバーテックスから、入力エッジの状態を取得した場合、ステップ番号n+1,n+2,…,n+m、としたステップ番号とともに、入力メッセージの状態を記憶しておく。

0045

このように、隣接同期に基づき次のスーパーステップに移行することにより、論理的には、バーテックスそれぞれに着目すると同一スーパーステップ内での同期がとれている。そのため、プログラマは、非同期型のような処理速度/効率性と計算精度のトレードオフを考慮する必要がなくすことができる。
また、図8(a)に示す比較例にくらべ、inactiveとして同期待ちをする時間が大幅に削減されるため(図8(b)の符号β)、処理速度/効率性を改善することが可能となる。つまり、システム全体としての処理速度の遅延や、フェーズPH3において処理をせず同期待ちが多いこと(処理の効率性)の問題を解決することができる。

0046

≪分散同期処理システムの構成≫
次に、本実施形態に係る分散同期処理システム1の構成について具体的に説明する。
図9に示すように、分散同期処理システム1は、管理サーバ10(master)と、管理サーバ10にそれぞれ接続され並列に処理を行う複数の処理サーバ30(worker)と、処理サーバ30上で動作する複数の分散処理部20(vertex)と、を備える。

0047

管理サーバ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によって実行される。なお、図9において、管理サーバ10、分散処理部20および処理サーバ30の内部は、RAMに展開されたアプリケーションプログラム等によって実現される機能(特徴構成)を、ブロックとして示している。

0048

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

0049

<管理サーバ(master)>
管理サーバ10は、対象とする計算処理に必要な個々の計算処理(vertex)の設定と、その個々の計算処理(vertex)の各処理サーバ30(worker)への割り振りを行う。また、管理サーバ10は、システム上に設定したバーテックス(vertex)毎に、BSPにおける、次のスーパーステップに移行するか否かを判断する処理を行うことにより、対象とする計算処理の全体を管理する。
図3に示した、従来の分散同期処理システム1aのmasterとの違いは、次のスーパーステップへの移行を、全てのバーテックスの処理が終了していることにより判断するのではなく、本実施形態に係る管理サーバ10(master)では、バーテックス毎に、上記した「隣接同期」に基づき判定することである。

0050

この管理サーバ10は、その特徴構成として、隣接同期処理部11を備える。
隣接同期処理部11は、各処理サーバ30(worker)から、分散処理部20(vertex)毎に、計算・送信処理fnが完了したとき、つまり、フェーズPH1(ローカル計算)およびフェーズPH2(データ交換)が完了したときに、計算・送信処理fnの完了報告(以下、「計算・送信処理完了報告」と称する。)を受信する。
そして、隣接同期処理部11は、受信した計算・送信処理完了報告で示される分散処理部20(vertex)、すなわち、計算・送信処理が完了した分散処理部20(vertex)について、次のスーパーステップへの移行判断を上記の「隣接同期」の条件に基づき行う。つまり、隣接同期処理部11は、「自バーテックスおよび入力エッジで接する全てのバーテックスの計算・送信処理fnが完了していること」(隣接同期)の条件を満たすか否かを判定する。なお、この隣接同期の判定は、次のスーパーステップにおいて必要な計算結果の取得が完了しているか否かを、隣接する分散処理部20(vertex)からの計算・送信処理完了報告を受信しているか否かに基づき判定することを意味する。

0051

隣接同期処理部11は、受信した計算・送信処理完了報告で示される分散処理部20(vertex)が、隣接同期の条件を満たす場合には、その分散処理部20(vertex)について、次のスーパーステップに移行する(スーパーステップを「+1」する。)ように、その分散処理部20(vertex)を担当する処理サーバ30(worker)に指示を送信する。なお、隣接同期処理部11による、次のスーパーステップへの移行指示を、以下「次ステップ移行指示」と称する。

0052

また、隣接同期処理部11は、ある分散処理部20(vertex)の計算・送信処理完了報告を受信した場合に、その計算・送信処理完了報告で示される分散処理部20(vertex)が出力エッジで接する分散処理部20(vertex)のうち、当該分散処理部20(vertex)のみからの入力メッセージ待ち(入力エッジの状態の取得待ち)」の理由により、inactive状態で待機している分散処理部20(vertex)がある場合には、その分散処理部20(vertex)を次のスーパーステップへ移行させるように、次ステップ移行指示を送信する。

0053

具体的には、図8(b)を参照して説明する。スーパーステップSS1のときのバーテックスv3に着目すると、バーテックスv3は、入力エッジで接するバーテックスv2,v4と自身の計算・送信処理f1が終わった時点が隣接同期する隣接同期ポイントとなる。ここでバーテックスv3は、自身の計算・送信処理f1が終わった時点では、バーテックスv4の計算・送信処理f1は終わっているが、バーテックスv2の計算・送信処理f1が終わっていないため、「inactive」の状態で待機している。この状態において、管理サーバ10の隣接同期処理部11が、処理サーバ30(worker1)からバーテックスv2の計算・送信処理f1が終わった旨の計算・送信処理完了報告を受信した場合には、バーテックスv2のみからの入力メッセージ待ち(入力エッジの状態の取得待ち)をしていた、バーテックスv3に対して、次ステップ移行指示を送信する。
このようにすることで、自身の計算・送信処理fnが終了し、inactive状態で待機していた分散処理部20(vertex)について、次にステップに移行させることができる。

0054

<分散処理部(vertex)>
図9戻り、分散処理部20(vertex)は、所定単位に区分された計算処理を実行し、数値計算部21およびメッセージ送受信部22を含んで構成される。

0055

数値計算部21は、BSPにおけるフェーズPH1(ローカル計算)の処理を実行する。この数値計算部21は、メッセージ送受信部22を介して受信する次ステップ移行指示に従い、次のスーパーステップへの移行を行う。なお、数値計算部21は、自身の計算・送信処理fnが完了した後、次ステップ移行指示を受信するまで、inactive状態で待機する。

0056

メッセージ送受信部22は、他の分散処理部20や処理サーバ30(worker)との間での情報の送受信を行う。具体的には、メッセージ送受信部22は、BSPにおけるフェーズPH2(データ交換)において、自身の出力エッジの状態を出力メッセージとして、その出力エッジで接続するバーテックスへ向けて送信する。なお、この出力メッセージには、その出力エッジの状態に対応付けてその時点でのスーパーステップのステップ番号が付される。また、メッセージ送受信部22は、入力エッジで接続するバーテックスから入力エッジの状態を入力メッセージとして受信する。また、この入力メッセージには、その入力エッジに状態に対応付けてその時点でのスーパーステップのステップ番号が付される。なお、メッセージ送受信部22は、この出力メッセージおよび入力メッセージを、処理サーバ(worker)30のメッセージ処理部32を介して送受信する。
また、このメッセージ送受信部22は、自身が属する処理サーバ30(worker)から、次ステップ移行指示を受信し、数値計算部21に出力する。

0057

<処理サーバ(worker)>
処理サーバ30(worker)(図9参照)は、管理サーバ10(master)や他の処理サーバ30(worker)と接続される。この処理サーバ30(worker)は、処理単位となる分散処理部20(vertex)を複数備え、自身が備える分散処理部20(vertex)の処理の進行状態等を管理するとともに、他の処理サーバ30(worker)や管理サーバ10(master)との間での情報の送受信を行う。また、この処理サーバ30(worker)は、仮想化制御部31、メッセージ処理部32およびバーテックス管理部33(分散処理管理部)を含んで構成される。

0058

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

0059

メッセージ処理部32は、自身に属する各分散処理部20(vertex)から、BSPにおけるフェーズPH2(データ交換)の際に、出力エッジの状態を示す出力メッセージを受け取り、計算対象のグラフGのグラフトポロジに基づき、その出力エッジで接続するバーテックスに、受信した出力メッセージを、入力エッジの状態を示す入力メッセージとして出力する。なお、以降、出力メッセージと入力メッセージとを特に区別しない場合、単に「メッセージ」と称する場合がある。

0060

メッセージ処理部32は、出力エッジで隣接する分散処理部20(vertex)へのメッセージを、例えば、次に示す2つのタイミングで送信することができる。
(タイミング1)
自分散処理部20(vertex)の計算終了後に直ちに送信する。
具体的には、メッセージ処理部32は、自分散処理部20(vertex)から、出力メッセージを受信した場合に、出力エッジで接続する分散処理部20(vertex)が、自身に属する分散処理部20(vertex)であるとき、および、他の処理サーバ30に属する分散処理部20(vertex)であるときに、直ちに、その分散処理部20(vertex)に送信する。
このようにすることにより、通信遅延の影響を低減させることができる。

0061

(タイミング2)
出力エッジで接続する分散処理部20(vertex)(隣接バーテックス)が、次のスーパーステップに移行する直前までバッファリングする。
具体的には、メッセージ処理部32は、自分散処理部20(vertex)から、出力メッセージを受信した場合に、出力エッジで接続する分散処理部20(vertex)が、他の処理サーバ30に属する分散処理部20(vertex)であるときに、その分散処理部20(vertex)が次のスーパーステップに移行する情報(次ステップ移行指示)を受ける状態になった時点で、管理サーバ10から、その次ステップ移行指示を出す旨の情報を事前に取得する。そして、移行直前にバッファリングしたメッセージをまとめて出力エッジで接続する分散処理部20(vertex)に送信する。
このようにすることで、他の処理サーバ30に属する分散処理部20(vertex)に送信する回数通信回数)を削減することができる。
なお、メッセージ処理部32は、自分散処理部20(vertex)から、出力メッセージを受信した場合に、出力エッジで接続する分散処理部20(vertex)が、自身に属する分散処理部20(vertex)であるとき、上記のような通信回数の削減効果は得られないので、バッファリングせず、直ちに送信するようにする。

0062

バーテックス管理部33(分散処理管理部)は、自身に属する分散処理部20(vertex)を監視し、各分散処理部20(vertex)が、計算・送信処理fnが完了したとき、つまり、フェーズPH1(ローカル計算)およびフェーズPH2(データ交換)が完了したときに、計算・送信処理fnの完了報告(計算・送信処理完了報告)を生成し、管理サーバ10(master)に送信する。
そして、バーテックス管理部33は、管理サーバ10(master)から、計算・送信処理完了報告に対する応答として、次ステップ移行指示を受信した場合に、その次ステップ移行指示を対象となる分散処理部20(vertex)に出力する。

0063

≪分散同期処理システムの動作≫
次に、分散同期処理システム1の動作について説明する。
図10は、本実施形態に係る分散同期処理システム1の処理の流れを示すシーケンス図である。
なお、ここでは、管理サーバ10(master)により、対象とする計算処理に必要な個々の計算処理(vertex)の設定と、その個々の計算処理(vertex)の各処理サーバ30(worker)への割り振りがすでに終わっているものとして説明する。

0064

まず、処理サーバ30(worker)のバーテックス管理部33(分散処理管理部)は、自身に属する分散処理部20(vertex)を監視することにより、ある分散処理部20(vertex)について計算・送信処理fnが完了したことを検出する(ステップS10)。そして、バーテックス管理部33は、その分散処理部20(vertex)の識別番号とその時点でのスーパーステップのステップ番号(n)とを付した計算・送信処理完了報告を、管理サーバ10に送信する(ステップS11)。

0065

次に、計算・送信処理完了報告を受信した管理サーバ10(master)は、隣接同期処理部11が、受信した計算・送信処理完了報告で示される分散処理部20(vertex)について、隣接同期の条件を満たすか否かを判定する(ステップS12)。具体的には、隣接同期処理部11は、「自バーテックスおよび入力エッジで接する全てのバーテックスの計算・送信処理fnが完了していること」を満たすか否かを判定する。

0066

そして、管理サーバ10(master)の隣接同期処理部11は、隣接同期の条件を満たさない場合には(ステップS12→No)、処理サーバ30(worker)から次の計算・送信処理完了報告を受信するまで待つ。

0067

一方、ステップS12において、管理サーバ10(master)の隣接同期処理部11は、隣接同期の条件を満たす場合に(ステップS12→Yes)、計算・送信処理完了報告を送信してきた処理サーバ30(worker)に、その分散処理部20(vertex)について、次のスーパーステップに移行するように、次ステップ移行指示を送信する(ステップS13)。

0068

また、管理サーバ10(master)の隣接同期処理部11は、ステップS12において、受信した計算・送信処理完了報告で示される分散処理部20(vertex)が出力エッジで接する分散処理部20(vertex)のうち、当該分散処理部20(vertex)のみからの入力メッセージ待ち(入力エッジの状態の取得待ち)」の理由により、inactive状態で待機している分散処理部20(vertex)があるか否かを判定する。そして、隣接同期処理部11は、該当する分散処理部20(vertex)がある場合には、その分散処理部20(vertex)が属する処理サーバ30(worker)に対しても、次ステップ移行指示を送信する。

0069

次ステップ移行指示を受信した処理サーバ30(worker)のバーテックス管理部33は、その計算・送信処理fnが完了した分散処理部20(vertex)、および、上記ステップS12の際に、inactive状態で待機していたと判定された分散処理部20(vertex)に対し、次ステップ移行指示を出力する(ステップS14)。これにより、次ステップ移行指示を受信した分散処理部20(vertex)の数値計算部21は、次のスーパーステップ(n+1)の計算・送信処理fn+1を実行する。

0070

以上説明したように、本実施形態に係る分散同期処理システム1および分散同期処理方法によれば、比較例の分散同期処理システムにおいて問題であった、システム全体としての処理速度の遅延や、フェーズPH3において処理をせず同期待ちが多いことの問題、つまり、処理速度/効率性の問題を解決し、処理が著しく遅い分散処理部20(vertex)の影響を低減することができる。
また、プログラマは、バーテックス間の処理の追い越しや上書きを考慮する必要がなく、シンプルなフレームワークとして、本システムのプログラムを作成することが可能となる。

0071

〔本実施形態の変形例〕
次に、本実施形態に係る分散同期処理システム1の変形例について説明する。
図11は、本実施形態の変形例に係る分散同期処理システム1Aの全体構成を示す図である。
図9で示した本実施形態に係る分散同期処理システム1では、管理サーバ10(master)が、各分散処理部20(vertex)について、隣接同期の条件を満たすか否かの判定を行っていた。つまり、隣接同期の判定を管理サーバ10が行う「master集中型」であった。これに対し、図11に示す、分散同期処理システム1Aは、管理サーバ10(master)を備えず、各分散処理部20(vertex)について、隣接同期の条件を満たすか否かの判定を、各処理サーバ30(worker)において自律分散的に実行する。つまり、分散同期処理システム1Aは、自律分散型(master-less型)で、隣接同期を行うことを特徴とする。
具体的には、本実施形態の変形例に係る分散同期処理システム1Aでは、図9に示す分散同期処理システム1における管理サーバ10(master)を備えない構成とするとともに、各処理サーバ30A(worker)におけるバーテックス管理部33を備えないものとし、その代わりに、図11に示すように、処理サーバ30Aに、隣接同期バーテックス管理部34(隣接同期分散管理部)を備えるものとした。
なお、図9で示す構成と同じ機能を備える構成については、同一の名称と符号を付し、説明を省略する。

0072

隣接同期バーテックス管理部34(隣接同期分散管理部)は、自身に属する分散処理部20(vertex)を監視し、各分散処理部20(vertex)が、計算・送信処理fnが完了したとき、つまり、フェーズPH1(ローカル計算)およびフェーズPH2(データ交換)が完了したときに、入力エッジで接する全ての分散処理部20(vertex)からの入力メッセージ(入力エッジの状態)が揃っているか否かを判定する。なお、隣接同期バーテックス管理部34は、各分散処理部20(vertex)の入力メッセージ(incomingメッセージ)のバッファ(図4の「Min,n」(現在のステップ用))を参照して、入力メッセージ(入力エッジの状態)が揃っているか否かを判定する。
なお、本実施形態の変形例においても、本実施形態と同様に、処理全体のある時点でみると、各バーテックス間においてスーパーステップがずれる可能性がある。そのため、バーテックス間でメッセージを送受信するときには上書きせずに、スーパーステップ毎に管理する。よって、各バーテックスは、自身のスーパーステップよりも先に、次のスーパーステップに移行した入力エッジで接するバーテックスから取得した入力エッジの状態を、「Min,n+m」として入力メッセージのバッファに記憶しておく。

0073

そして、隣接同期バーテックス管理部34は、入力メッセージ(入力エッジの状態)が揃っている場合、つまり、隣接する分散処理部20(vertex)から、次の計算ステップにおいて必要な計算結果の取得が完了している場合には、本実施形態における隣接同期の条件「自バーテックスおよび入力エッジで接する全てのバーテックスの計算・送信処理fnが完了していること」を満たすものとする。隣接同期バーテックス管理部34は、この場合に、次のスーパーステップに移行する(スーパーステップを「+1」する。)ように、「次ステップ移行指示」を、計算・送信処理fnが完了した分散処理部20(vertex)に出力する。

0074

隣接同期バーテックス管理部34は、inactive状態で待機している分散処理部20(vertex)に対し入力エッジで接するいずれかの分散処理部20(vertex)から、当該分散処理部20(vertex)が入力メッセージ(入力エッジの状態)を受信した場合には、その受信を契機として、再度、入力メッセージ(入力エッジの状態)が揃っているか否か、つまり、隣接同期の条件を満たすか否かの判定を実行する。

0075

なお、処理サーバ30A(worker)のメッセージ処理部32は、隣接同期バーテックス管理部34の上記した隣接同期の判定のため、入力エッジの状態としてのデータがない場合(例えば、データが「0」)であっても、フェーズPH1(ローカル計算)が終わった時点で、出力エッジで接する分散処理部20(vertex)に対して、入力メッセージを送信する。また、処理サーバ30A(worker)のメッセージ処理部32は、隣接同期バーテックス管理部34の隣接同期の条件による判定のため、出力メッセージをバッファリングせずに、直ちに送信する。

0076

≪変形例の分散同期処理システムの動作≫
次に、変形例に係る分散同期処理システム1Aの動作について説明する。
図12は、本実施形態の変形例に係る分散同期処理システム1Aの処理の流れを示すフローチャートである。
なお、ここでは、予め対象とする計算処理に必要な個々の計算処理(vertex)の設定と、その個々の計算処理(vertex)の各処理サーバ30A(worker)への割り振りが終わっているものとして説明する。この個々の計算処理(vertex)の設定と、各処理サーバ30A(worker)への割り振りとは、例えば、これらの機能を、システム全体の管理サーバを備えさせたり、処理サーバ30Aの中の代表サーバに備えさせたりすることにより、事前に実行しておけばよい。

0077

まず、処理サーバ30A(worker)の隣接同期バーテックス管理部34(隣接同期分散管理部)は、自身に属する分散処理部20(vertex)を監視することにより、ある分散処理部20(vertex)について計算・送信処理fnが完了したことを検出する(ステップS20)。

0078

続いて、隣接同期バーテックス管理部34は、その分散処理部20(vertex)について、入力エッジで接する全ての分散処理部20(vertex)からの入力メッセージ(入力エッジの状態)が揃っているか否かを判定する(ステップS21)。

0079

ここで、隣接同期バーテックス管理部34は、入力メッセージ(入力エッジの状態)が揃っていると判定した場合には(ステップS21→Yes)、隣接同期の条件「自バーテックスおよび入力エッジで接する全てのバーテックスの計算・送信処理fnが完了していること」を満たすものし、後記するステップS24(「次ステップ移行指示」の出力)に進む。

0080

一方、隣接同期バーテックス管理部34は、入力メッセージ(入力エッジの状態)が揃っていないと判定した場合には(ステップS21→No)、「次ステップ移行指示」を出力しない。そのため、その計算・送信処理fnが完了した分散処理部20(vertex)は、inactive状態での待機となる(ステップS22)。

0081

続いて、隣接同期バーテックス管理部34は、inactive状態で待機している分散処理部20(vertex)に対し、入力エッジで接するいずれかの分散処理部20(vertex)から、当該分散処理部20(vertex)が入力メッセージ(入力エッジの状態)を受信したか否かを判定する(ステップS23)。そして、隣接同期バーテックス管理部34は、inactive状態で待機している分散処理部20(vertex)が入力メッセージを受信していなければ(ステップS23→No)、受信するまで待つ。一方、隣接同期バーテックス管理部34は、inactive状態で待機している分散処理部20(vertex)が入力メッセージを受信した場合には(ステップS23→Yes)、そのことを契機として、ステップS21に戻る。

0082

一方、隣接同期バーテックス管理部34は、隣接同期の条件を満たす場合には(ステップS21→Yes)、ステップS24において、その分散処理部20(vertex)について、次のスーパーステップに移行するように、「次ステップ移行指示」を出力する。これにより、「次ステップ移行指示」を受信した分散処理部20(vertex)の数値計算部21は、次のスーパーステップ(n+1)の計算・送信処理fn+1を実行する。

0083

以上説明したように、本実施形態の変形例に係る分散同期処理システム1Aおよび分散同期処理方法によれば、本実施形態に係る分散同期処理システム1の効果に加えて、自律分散型を採用することにより、管理サーバ10(master)のボトルネックを回避し、大規模なグラフGにおいても、処理速度/効率性を担保することができる。

0084

1,1A 分散同期処理システム
10管理サーバ(master)
11 隣接同期処理部
20分散処理部(vertex)
21数値計算部
22メッセージ送受信部
30,30A処理サーバ(worker)
31仮想化制御部
32メッセージ処理部
33バーテックス管理部(分散処理管理部)
34 隣接同期バーテックス管理部(隣接同期分散管理部)

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

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

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

関連する公募課題

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

ページトップへ

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

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

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

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

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

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

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

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

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

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

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

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

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

関連性が強い 技術一覧

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

関連性が強い人物一覧

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

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

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

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

astavision 新着記事

サイト情報について

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

主たる情報の出典

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