(57)【要約】【課題】リソース制約による予期せぬアイドル時間を抑制する、分散同期処理システムおよび分散同期処理方法を提供する。【解決手段】分散同期処理システム１の処理サーバ１０それぞれは、分散処理部２０による所定の計算ステップにおける計算処理、および、当該分散処理部２０の接続先となる他の分散処理部２０との間でのデータ送受信を完了し、当該分散処理部２０が、次の計算ステップについて実行可能な状態を示す実行可能状態であることを検出する隣接同期分散管理部１３と、実行可能状態となった分散処理部２０に優先度を付し、優先度の高い分散処理部２０のスレッドを優先的にＣＰＵの処理スケジュールに割り当てる優先度設定部１４と、を備える。【選択図】図９
2018136588.tif 000002
【特許請求の範囲】
【請求項１】
複数の処理サーバと、前記処理サーバ上で動作する複数の分散処理部と、を有する分散同期処理システムであって、
前記分散処理部のそれぞれには、当該分散処理部自身が属する処理サーバのＣＰＵにおける１コアのスケジューリング対象として、個別の実行単位である１スレッドが割り当てられるものであり、
前記処理サーバのそれぞれは、
前記分散処理部による所定の計算ステップにおける計算処理、および、当該分散処理部の接続先となる他の分散処理部との間でのデータ送受信を完了し、当該分散処理部が、次の前記計算ステップについて実行可能な状態を示す実行可能状態であることを検出する隣接同期分散管理部と、
前記実行可能状態となった分散処理部に優先度を付し、前記優先度の高い分散処理部のスレッドを優先的に前記ＣＰＵの処理スケジュールに割り当てる優先度設定部と、
を備えることを特徴とする分散同期処理システム。
【請求項２】
前記処理サーバのそれぞれは、
計算対象となる各分散処理部の接続関係として、前記分散処理部と当該分散処理部が算出したデータの出力先となる他の分散処理部とが出力辺で繋がり、前記分散処理部と次の前記計算ステップで必要となるデータの入力元となる他の分散処理部とが入力辺で繋がることを示すグラフトポロジを記憶する記憶部を備えており、
前記優先度設定部は、前記実行可能状態となった分散処理部それぞれについての前記出力辺の数を算出し、前記算出した出力辺の数が多い前記分散処理部のスレッドを優先して前記ＣＰＵの処理スケジュールに割り当てること
を特徴とする請求項１に記載の分散同期処理システム。
【請求項３】
前記隣接同期分散管理部は、各前記分散処理部が実行している前記計算ステップのステップ番号を監視しており、
前記優先度設定部は、前記実行可能状態となった分散処理部それぞれについての前記計算ステップのステップ番号を参照し、他の前記分散処理部と比べ処理が遅延している分散処理部のスレッドを優先して前記ＣＰＵの処理スケジュールに割り当てること
を特徴とする請求項１に記載の分散同期処理システム。
【請求項４】
前記処理サーバのそれぞれは、
計算対象となる各分散処理部の接続関係として、前記分散処理部と当該分散処理部が算出したデータの出力先となる他の分散処理部とが出力辺で繋がり、前記分散処理部と次の前記計算ステップで必要となるデータの入力元となる他の分散処理部とが入力辺で繋がることを示すグラフトポロジを記憶する記憶部を備えており、
前記優先度設定部は、前記実行可能状態となった分散処理部それぞれについての前記出力辺の数を算出し、前記算出した出力辺の数が多い前記分散処理部のスレッドを優先して前記ＣＰＵの処理スケジュールに割り当てることの指標となる第１の優先度を求め、
前記隣接同期分散管理部は、各前記分散処理部が実行している前記計算ステップのステップ番号を監視しており、
前記優先度設定部は、前記実行可能状態となった分散処理部それぞれについての前記計算ステップのステップ番号を参照し、他の前記分散処理部と比べ処理が遅延している分散処理部のスレッドを優先して前記ＣＰＵの処理スケジュールに割り当てることの指標となる第２の優先度を求め、
前記優先度設定部は、前記第１の優先度および前記第２の優先度の双方を用いた各前記分散処理部の優先度を算出し、前記算出した優先度が高い前記分散処理部のスレッドを優先して前記ＣＰＵの処理スケジュールを割り当てること
を特徴とする請求項１に記載の分散同期処理システム。
【請求項５】
前記処理サーバのそれぞれは、
計算対象となる各分散処理部の接続関係として、前記分散処理部と当該分散処理部が算出したデータの出力先となる他の分散処理部とが出力辺で繋がり、前記分散処理部と次の前記計算ステップで必要となるデータの入力元となる他の分散処理部とが入力辺で繋がることを示すグラフトポロジを記憶する記憶部を備えており、
前記分散処理部のそれぞれは、前記入力元となる他の分散処理部からのデータの送信がないため、次の前記計算ステップに移行できず入力待ち状態となっている場合に、当該入力元となる他の分散処理部に対し、入力待ち情報を送信することにより投票し、
前記入力待ち情報を受信した入力元となる他の分散処理部は、受信した前記入力待ち情報の数を優先度投票値として集計し、
前記処理サーバそれぞれの前記優先度設定部は、前記入力元となる他の分散処理部のうち、前記優先度投票値の多い分散処理部のスレッドを優先して前記ＣＰＵの処理スケジュールに割り当てること
を特徴とする請求項１に記載の分散同期処理システム。
【請求項６】
前記入力待ち情報を受信した入力元となる他の分散処理部は、自身も前記入力待ち状態である場合に、前記集計した優先度投票値に自身の遅延分を加えた優先度投票値を付した前記入力待ち情報を、前記入力元となる他の分散処理部のさらに入力元であり遅延の原因である他の分散処理部に送信すること
を特徴とする請求項５に記載の分散同期処理システム。
【請求項７】
複数の処理サーバと、前記処理サーバ上で動作する複数の分散処理部と、を有する分散同期処理システムの分散同期処理方法であって、
前記分散処理部のそれぞれには、当該分散処理部自身が属する処理サーバのＣＰＵにおける１コアのスケジューリング対象として、個別の実行単位である１スレッドが割り当てられるものであり、
前記処理サーバのそれぞれは、
前記分散処理部による所定の計算ステップにおける計算処理、および、当該分散処理部の接続先となる他の分散処理部との間でのデータ送受信を完了し、当該分散処理部が、次の前記計算ステップについて実行可能な状態を示す実行可能状態であることを検出する手順と、
前記実行可能状態となった分散処理部に優先度を付し、前記優先度の高い分散処理部のスレッドを優先的に前記ＣＰＵの処理スケジュールに割り当てる手順と、
を実行することを特徴とする分散同期処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分散配置された複数のサーバを同期させて処理を実行する分散同期処理システムおよび分散同期処理方法に関する。
【背景技術】
【０００２】
ネットワーク上に複数のサーバを分散配置する分散処理システムのフレームワークとして、非特許文献１にはＭａｐＲｅｄｕｃｅが開示されている。但し、このＭａｐＲｅｄｕｃｅは、処理の度に、外部のデータストアからの入力データの読み込みや、結果の書き出し処理が必要であるため、ある処理の結果を次の処理で利用するようなイテレーティブな（反復する）処理には向いていない。この種の処理には、非特許文献２に開示されているＢＳＰ（Bulk Synchronous Parallel：バルク同期並列）が適している。
【０００３】
このＢＳＰは、「スーパーステップ（ＳＳ：superstep)」という処理単位を繰り返し実行することにより、分散環境でのデータ処理を実行する。図１は、ＢＳＰ計算モデルを説明するための図である。
【０００４】
１つのスーパーステップは、図１に示すように、次の３つのフェーズ（ＰＨ：phase）、「ローカル計算（ＬＣ：Local computation）」（フェーズＰＨ１）、「データ交換（Ｃｏｍ：Communication）」（フェーズＰＨ２）、「同期（Sync）」（フェーズＰＨ３）から構成される。
具体的には、複数のノード（ノード１〜ノード４）のうちのいずれかのノードがデータを受信すると、そのノード（例えば、ノード１）がフェーズＰＨ１において、そのデータについての計算処理（ローカル計算（ＬＣ））を実行する。続いて、フェーズＰＨ２において、各ノードが保持しているローカル計算の結果であるデータについて、ノード間でのデータ交換を実行する。次に、フェーズＰＨ３において、同期処理を行う、より詳細には、すべてのノード間でのデータ交換の終了を待つ。
そして、スーパーステップＳＳ１として、一連のスーパーステップの処理（ＰＨ１〜ＰＨ３）が終了すると、各ノードはその計算結果を保持した上で、次の一連の処理であるスーパーステップＳＳ２へと進む。
【０００５】
このＢＳＰを採用した分散処理フレームワークとして、非特許文献３にはＰｒｅｇｅｌが開示されている。このＰｒｅｇｅｌ等のフレームワークでは、全体の処理をグラフＧ＝（Ｖ，Ｅ）として表現し、これをＢＳＰに適用して実行する。ここで、Ｖは「バーテックス（vertex：頂点）の集合」であり、Ｅは「エッジ（edge：辺）の集合」を意味する。
【０００６】
ここで、図２を参照し、交通シミュレーションにＢＳＰを適用した例を説明する。
図２においては、各交差点（ｖ）が頂点（vertex）に対応付けられる（図２のｖ１〜ｖ４）。また、各交差点を結ぶ道路（ｅ）が辺（edge）に対応付けられる（図２のｅ１〜ｅ６）。ここで、辺（edge）は一方通行であり、双方向の道路は２つの辺（edge）に対応付けられる。また、ある頂点（vertex）から見て、車両が出てゆく方向の辺（edge）を、「出力辺（outgoing edge）」と呼び、車両が流入する方向の辺（edge）を「入力辺（incoming edge）」と呼ぶ。例えば、図２において、頂点ｖ２からみると、辺ｅ１は入力辺であり、辺ｅ２は出力辺になる。逆に、頂点ｖ１からみると、辺ｅ１は出力辺であり、辺ｅ２は入力辺になる。
【０００７】
図１で示したスーパーステップでは、フェーズＰＨ１（ローカル計算）において、頂点（vertex）毎に、経過時間（Δｔ）における、各頂点ｖ１〜ｖ４に対応付けられている交差点の状態（例えば、信号の色（青、黄、赤）や交差点内の車両の動き等）と、それに付随する出力辺としての道路内の状態（車両の動き（台数・平均速度等））とをシミュレートする。フェーズＰＨ２（データ交換）では、ある頂点（vertex）は、出力辺を介して接する他の頂点（vertex）に対して、当該出力辺を介して出てゆく車両の動きの情報（台数等）を送信するとともに、入力辺を介して入ってくる車両の動きの情報（台数等）を受信する。フェーズＰＨ３（同期）では、頂点（vertex）間で、シミュレーション時刻ｔを同期する。つまり、全ての頂点（vertex）間でデータ交換の完了を待つ。
この交通シミュレーションにおいては、このように交差点（頂点（vertex））単位で、並列処理することにより、計算時間を短縮することが可能となる。
【０００８】
しかしながら、上記のＢＳＰを採用した分散同期処理システムの構成では、スーパーステップ毎に、全頂点（vertex）を同期するため、最も処理が遅い頂点（vertex）にあわせることとなる。よって、たった一つでも全体から著しく遅い頂点（vertex）があると、その影響が全体に及ぶ。つまり、最も処理が遅い頂点（vertex）にあわせて、全体が著しく遅延してしまう。
【０００９】
上記の問題を解決する手法として、非特許文献４に記載の技術が提案されている。
非特許文献４では、全体同期ではなく、隣接する頂点（vertex）の間で局所的に同期処理を行う。具体的には、「自頂点（vertex）および入力辺で接する全ての頂点（vertex）の計算・送信処理（ローカル計算（フェーズＰＨ１）およびデータ交換（フェーズＰＨ２））が完了していること」（以下、「隣接同期」と称する。）を満たしている場合に、各頂点（vertex）が次のスーパーステップに移行する。これにより、同期（Sync）（フェーズＰＨ３）における待ち時間が削減されるため、システム全体としての処理速度の向上させることができる。
【先行技術文献】
【非特許文献】
【００１０】
【非特許文献１】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.
【非特許文献４】小林弘明，岡本光浩，「分散処理フレームワークの同期処理に関する一検討」，電子情報通信学会，2016年電子情報通信学会通信ソサイエティ大会講演論文集，Ｂ−７−１，2016年9月6日
【発明の概要】
【発明が解決しようとする課題】
【００１１】
この非特許文献４に記載の分散同期処理システムは、全ての頂点（vertex）のローカル計算（フェーズＰＨ１）を並列実行できるという前提で評価を行っていた。しかしながら、実際には、各頂点（vertex）のローカル計算（フェーズＰＨ１）を実行する処理サーバ（後記する「worker」）は、各頂点（vertex）に個別のスレッドを割り当てて処理するため、ＣＰＵ（Central Processing Unit）の１コアに複数のスレッドが割り当てられた場合（以下、「リソース制約」と称する。）に、予期せぬアイドル時間が生じる可能性がある。
【００１２】
本発明は、前記した問題を鑑みてなされたものであり、分散同期処理を行うシステムにおいて、リソース制約による予期せぬアイドル時間を抑制することができる、分散同期処理システムおよび分散同期処理方法を提供することを課題とする。
【課題を解決するための手段】
【００１３】
前記した課題を解決するため、請求項１に記載の発明は、複数の処理サーバと、前記処理サーバ上で動作する複数の分散処理部と、を有する分散同期処理システムであって、前記分散処理部のそれぞれには、当該分散処理部自身が属する処理サーバのＣＰＵにおける１コアのスケジューリング対象として、個別の実行単位である１スレッドが割り当てられるものであり、前記処理サーバのそれぞれが、前記分散処理部による所定の計算ステップにおける計算処理、および、当該分散処理部の接続先となる他の分散処理部との間でのデータ送受信を完了し、当該分散処理部が、次の前記計算ステップについて実行可能な状態を示す実行可能状態であることを検出する隣接同期分散管理部と、前記実行可能状態となった分散処理部に優先度を付し、前記優先度の高い分散処理部のスレッドを優先的に前記ＣＰＵの処理スケジュールに割り当てる優先度設定部と、を備えることを特徴とする。
【００１４】
また、請求項７に記載の発明は、複数の処理サーバと、前記処理サーバ上で動作する複数の分散処理部と、を有する分散同期処理システムの分散同期処理方法であって、前記分散処理部のそれぞれには、当該分散処理部自身が属する処理サーバのＣＰＵにおける１コアのスケジューリング対象として、個別の実行単位である１スレッドが割り当てられるものであり、前記処理サーバのそれぞれが、前記分散処理部による所定の計算ステップにおける計算処理、および、当該分散処理部の接続先となる他の分散処理部との間でのデータ送受信を完了し、当該分散処理部が、次の前記計算ステップについて実行可能な状態を示す実行可能状態であることを検出する手順と、前記実行可能状態となった分散処理部に優先度を付し、前記優先度の高い分散処理部のスレッドを優先的に前記ＣＰＵの処理スケジュールに割り当てる手順と、を実行することを特徴とする。
【００１５】
このようにすることで、分散処理システムの各処理サーバのリソース制約による予期せぬアイドル時間を抑制することができる。これにより、各処理サーバのリソース利用効率が向上し、同期処理計算の高速化（実行時間の短縮）を図ることができる。
【００１６】
請求項２に記載の発明は、前記処理サーバのそれぞれが、計算対象となる各分散処理部の接続関係として、前記分散処理部と当該分散処理部が算出したデータの出力先となる他の分散処理部とが出力辺で繋がり、前記分散処理部と次の前記計算ステップで必要となるデータの入力元となる他の分散処理部とが入力辺で繋がることを示すグラフトポロジを記憶する記憶部を備えており、前記優先度設定部が、前記実行可能状態となった分散処理部それぞれについての前記出力辺の数を算出し、前記算出した出力辺の数が多い前記分散処理部のスレッドを優先して前記ＣＰＵの処理スケジュールに割り当てることを特徴とする。
【００１７】
このようにすることで、分散処理システムの処理サーバは、出力辺の数が多い、つまり、隣接する分散処理部が多く、他の分散処理部に影響を及ぼす分散処理部のスレッドを優先して処理することができる。これにより、リソース制約によるアイドル時間を抑制することができる。
【００１８】
請求項３に記載の発明は、前記隣接同期分散管理部が、各前記分散処理部が実行している前記計算ステップのステップ番号を監視しており、前記優先度設定部が、前記実行可能状態となった分散処理部それぞれについての前記計算ステップのステップ番号を参照し、他の前記分散処理部と比べ処理が遅延している分散処理部のスレッドを優先して前記ＣＰＵの処理スケジュールに割り当てることを特徴とする。
【００１９】
このようにすることで、分散処理システムの処理サーバは、各分散処理部のうち、実行している計算ステップが遅い分散処理部のスレッドを優先して処理することができる。これにより、リソース制約によるアイドル時間を抑制することができる。
【００２０】
請求項４に記載の発明は、前記処理サーバのそれぞれが、計算対象となる各分散処理部の接続関係として、前記分散処理部と当該分散処理部が算出したデータの出力先となる他の分散処理部とが出力辺で繋がり、前記分散処理部と次の前記計算ステップで必要となるデータの入力元となる他の分散処理部とが入力辺で繋がることを示すグラフトポロジを記憶する記憶部を備えており、前記優先度設定部が、前記実行可能状態となった分散処理部それぞれについての前記出力辺の数を算出し、前記算出した出力辺の数が多い前記分散処理部のスレッドを優先して前記ＣＰＵの処理スケジュールに割り当てることの指標となる第１の優先度を求め、前記隣接同期分散管理部が、各前記分散処理部が実行している前記計算ステップのステップ番号を監視しており、前記優先度設定部が、前記実行可能状態となった分散処理部それぞれについての前記計算ステップのステップ番号を参照し、他の前記分散処理部と比べ処理が遅延している分散処理部のスレッドを優先して前記ＣＰＵの処理スケジュールに割り当てることの指標となる第２の優先度を求め、前記優先度設定部が、前記第１の優先度および前記第２の優先度の双方を用いた各前記分散処理部の優先度を算出し、前記算出した優先度が高い前記分散処理部のスレッドを優先して前記ＣＰＵの処理スケジュールを割り当てることを特徴とする。
【００２１】
このようにすることで、分散処理システムの処理サーバは、各分散処理部の出力辺の数および実行している計算ステップの双方を考慮して優先度を算出し、算出した優先度の高い分散処理部のスレッドを優先して処理することができる。これにより、リソース制約によるアイドル時間を抑制することができる。
【００２２】
請求項５に記載の発明は、前記処理サーバのそれぞれが、計算対象となる各分散処理部の接続関係として、前記分散処理部と当該分散処理部が算出したデータの出力先となる他の分散処理部とが出力辺で繋がり、前記分散処理部と次の前記計算ステップで必要となるデータの入力元となる他の分散処理部とが入力辺で繋がることを示すグラフトポロジを記憶する記憶部を備えており、前記分散処理部のそれぞれが、前記入力元となる他の分散処理部からのデータの送信がないため、次の前記計算ステップに移行できず入力待ち状態となっている場合に、当該入力元となる他の分散処理部に対し、入力待ち情報を送信することにより投票し、前記入力待ち情報を受信した入力元となる他の分散処理部は、受信した前記入力待ち情報の数を優先度投票値として集計し、前記処理サーバそれぞれの前記優先度設定部が、前記入力元となる他の分散処理部のうち、前記優先度投票値の多い分散処理部のスレッドを優先して前記ＣＰＵの処理スケジュールに割り当てることを特徴とする。
【００２３】
このようにすることで、分散処理システムの処理サーバは、実際に隣接している分散処理部を入力待ち状態にさせている分散処理部のスレッドを優先して処理することができる。これにより、リソース制約によるアイドル時間を抑制することができる。
【００２４】
請求項６に記載の発明は、前記入力待ち情報を受信した入力元となる他の分散処理部が、自身も前記入力待ち状態である場合に、前記集計した優先度投票値に自身の遅延分を加えた優先度投票値を付した前記入力待ち情報を、前記入力元となる他の分散処理部のさらに入力元であり遅延の原因である他の分散処理部に送信することを特徴とする。
【００２５】
このようにすることで、分散処理システムの処理サーバは、隣接している分散処理部を入力待ち状態にさせている分散処理部だけでなく、その分散処理部をさらに入力待ち状態にさせている分散処理部も考慮して優先すべき分散処理部を決定することができる。これにより、リソース制約によるアイドル時間をさらに抑制することができる。
【発明の効果】
【００２６】
本発明によれば、分散同期処理を行うシステムにおいて、リソース制約による予期せぬアイドル時間を抑制することができる、分散同期処理システムおよび分散同期処理方法を提供することができる。
また、上記効果に伴い、分散同期処理システムを構成する処理サーバのリソース利用効率を向上させ、同期処理計算の高速化（実行時間の短縮）を図ることができる。
【図面の簡単な説明】
【００２７】
【図１】ＢＳＰ計算モデルを説明するための図である。
【図２】交通シミュレーションにＢＳＰ計算モデルを適用した例を説明するための図である。
【図３】比較例に係る分散同期処理システムの構成を説明するための図である。
【図４】ＢＳＰ計算モデルにおける計算対象のグラフトポロジを例示する図である。
【図５】比較例の分散同期処理システムおける処理の流れを説明するための図である。
【図６】非特許文献４の分散同期処理システムにおける処理の流れを説明するための図である。
【図７】本発明の課題を説明するための図である。
【図８】本実施形態に係る分散同期処理システムの処理概要を説明するための図である。
【図９】本実施形態に係る分散同期処理システムの構成を示す図である。
【図１０】出力辺数優先方式（ＬＥＦ）による優先度設定処理を説明するための図である。
【図１１】遅延ステップ優先方式（ＬＳＦ）による優先度設定処理を説明するための図である。
【図１２】複合優先方式（ＨＬ２）による優先度の算出式を示す図である。
【図１３】遅延投票数優先方式（ＭＶＦ）による優先度設定処理を説明するための図である。
【図１４】本実施形態に係る分散同期処理システムの処理の流れを示すフローチャートである。
【発明を実施するための形態】
【００２８】
＜比較例の分散同期処理手法の内容と課題の詳細な説明＞
初めに、本実施形態に係る分散同期処理システム１および分散同期処理方法の特徴構成を説明するため、比較例として従来技術における分散同期処理システム１ａ，１ｂおよびその分散同期処理方法を、詳細に説明する。
まず、従来のＢＳＰを用いた分散同期処理システム１ａ（図３〜図５参照）を説明し、その後、非特許文献４に記載の分散同期処理システム１ｂ（図６参照）を説明する。
【００２９】
比較例の分散同期処理システム１ａは、図３に示すように、複数のworker（処理サーバ）１０ａそれぞれが、複数の頂点（vertex）２０ａを備えて構成される。そして、この構成にＢＳＰを適用するとき、各worker１０ａは、自身が備える全ての頂点（vertex）２０ａについて、現在のスーパーステップ（以下、単に「ステップ」と称することがある。）の状態を管理する。また、各worker１０ａは、自身が備える全ての頂点（vertex）２０ａの処理（フェーズＰＨ１，２）が完了すると、その完了情報を他のworker１０ａに報告し、それぞれのworker１０ａは、全worker１０ａからの報告を受けると、スーパーステップを次のスーパーステップに移行する。
なお、各worker１０ａのうちの１つを代表worker１０ａとし、各worker１０ａから完了情報を取得し、全worker１０ａからの報告を受け、次のスーパーステップへの移行指示を各worker１０ａに送信するようにしてもよい。また、１つのmaster（管理サーバ）を設けて、各worker１０ａから完了情報を取得し、全worker１０ａからの報告を受け、次のスーパーステップへの移行指示を各worker１０ａに送信するようにしてもよい。
【００３０】
ここで、頂点（vertex）に着目すると、各頂点（vertex）は、次に示す処理を実行する。
頂点（vertex）は、ＢＳＰのフェーズＰＨ１において、現在のその頂点（vertex）の状態、出力辺の状態、および、前スーパーステップの入力メッセージにより取得した情報（入力辺の状態）をパラメータとして計算を行い、頂点（vertex）の状態および出力辺の状態を更新する。そして、頂点（vertex）は、フェーズＰＨ２において、更新した出力辺の状態を出力メッセージとして、その出力辺に隣接する頂点（vertex）に送信する。また、頂点（vertex）は、入力辺で隣接する頂点（vertex）から、更新した入力辺の状態を入力メッセージとして受信する。
この各頂点（vertex）が実行する、フェーズＰＨ１における計算処理およびフェーズＰＨ２におけるデータ交換を、以下「計算・送信処理」と記載する。また、スーパーステップｎ（ｎは、正の整数）における計算・送信処理を、「計算・送信処理ｆｎ」と記載する。
【００３１】
次に、図５を参照して、比較例の分散同期処理システム１ａが実行する処理の流れについて説明する。なお、ここでは、計算対象が、図４に示すグラフトポロジ（グラフＧ）であるものとして説明する。また、図５に示すように、分散同期処理システム１ａが２台のworker（worker１，worker２）で構成され、頂点（vertex）ｖ１〜ｖ６のうち、頂点（vertex）ｖ１〜ｖ３をworker１が担当し、頂点（vertex）ｖ４〜ｖ６をworker２が担当するものとする。以下、全体の処理の流れを通して説明する。
【００３２】
まず、各worker（worker１，worker２）は、担当する頂点（vertex）のスーパーステップを実行する（ステップＳ１０１）。具体的には、フェーズＰＨ１のローカル計算を実行し、スーパーステップの処理を開始する。
【００３３】
次に、各workerは、自身が担当する頂点（vertex）の処理の進行を監視し、各頂点（vertex）が、フェーズＰＨ２のデータ交換まで完了したか否かを判定する。そして、各workerは、担当する全ての頂点（vertex）が、フェーズＰＨ２までの処理を完了したと確認した場合に、その完了情報を他のworkerに送信する（ステップＳ１０２）。
【００３４】
続いて、各workerは、自身を含む全てのworker（ここでは、worker１，worker２）から完了情報を受信したか否かを確認する。そして、各workerは、全てのworkerから完了情報を受信した場合に、スーパーステップを「＋１」に更新し（ステップＳ１０３）、担当する各頂点（vertex）に次のスーパーステップの実行を指示する（ステップＳ１０４）。
そして、各workerは、ステップＳ１０１〜Ｓ１０４を繰り返す。
【００３５】
比較例の分散同期処理システム１ａにおいては、スーパーステップ毎に、計算対象となる全ての頂点（vertex）を同期する。具体的には、図５に示す全体同期ポイントにおいて同期するため、最も遅い頂点（vertex）にあわせることとなる。例えば、図５のスーパーステップＳＳ１では、頂点（vertex）ｖ１〜ｖ６のうち、最も遅い頂点（vertex）ｖ２にあわせることとなる。また、スーパーステップＳＳ２では、最も遅い頂点（vertex）ｖ６にあわせることとなる。よって、著しく遅い頂点（vertex）があると、その頂点（vertex）にあわせるために、頂点（vertex）の処理全体が著しく遅延してしまう。
【００３６】
このような問題を解決するため非特許文献４の分散同期処理システム１ｂでは、従来の全頂点（vertex）での同期を行わず、頂点（vertex）毎に次のスーパーステップへの移行を判断している。具体的には、非特許文献４の分散同期処理システム１ｂでは、「自頂点（vertex）および入力辺で接する全ての頂点（vertex）の計算・送信処理ｆｎ（ローカル計算（フェーズＰＨ１）およびデータ交換（フェーズＰＨ２））が完了していること」（隣接同期）を満たしている場合に、各頂点（vertex）が次のスーパーステップに移行するものとしている。
【００３７】
図６は、図５において示した比較例の分散同期処理システム１ａが実行する処理（図６（ａ）参照）と、非特許文献４の分散同期処理システム１ｂが実行する処理（図６（ｂ）参照）とを示す図である。
非特許文献４の分散同期処理システム１ｂでは、上記のように、「自頂点（vertex）および入力辺で接する全ての頂点（vertex）の計算・送信処理ｆｎ（ローカル計算（フェーズＰＨ１）およびデータ交換（フェーズＰＨ２））が完了していること」（隣接同期）により、次のスーパーステップに移行する。
【００３８】
例えば、図６（ｂ）の頂点（vertex）ｖ２に着目すると、頂点（vertex）ｖ２は、入力辺で接する頂点（vertex）ｖ１，ｖ３，ｖ４の計算・送信処理ｆｎと自身の計算・送信処理ｆｎが終わった時点が隣接同期する隣接同期ポイントとなる。ここで頂点（vertex）ｖ２は、スーパーステップＳＳ１のとき、自身の計算・送信処理ｆ１の終了が頂点（vertex）ｖ１，ｖ３，ｖ４より遅く一番後であったので、その時点が隣接同期ポイントとなっている。
頂点（vertex）ｖ３に着目すると、頂点（vertex）ｖ３は、入力辺で接する頂点（vertex）ｖ２，ｖ４の計算・送信処理ｆｎと自身の計算・送信処理ｆｎが終わった時点が隣接同期する隣接同期ポイントとなる。ここで頂点（vertex）ｖ３は、スーパーステップＳＳ１のとき、自身の計算・送信処理ｆ１が終わった時点では、頂点（vertex）ｖ４の計算・送信処理ｆ１は終わっているが、頂点（vertex）ｖ２の計算・送信処理ｆ１が終わっていないため、待機状態となり（図６（ｂ）の符号α）、頂点（vertex）ｖ２の計算・送信処理ｆ１が終わった時点が隣接同期する隣接同期ポイントとなる。
また、頂点（vertex）ｖ１に着目すると、頂点（vertex）ｖ１は、入力辺で接する頂点（vertex）は存在しない、よって、スーパーステップＳＳ１のとき、自頂点（vertex）の計算・送信処理ｆ１が終了した時点が隣接同期する隣接同期ポイントとなる。
【００３９】
図６（ｂ）に示すように、処理全体のある時点でみると、各頂点（vertex）間においてスーパーステップがずれる可能性がある。そのため、頂点（vertex）間でメッセージを送受信するときには上書きせずに、スーパーステップ毎に管理する。つまり、各workerは、スーパーステップの情報（ステップ番号）をあわせて記憶するようにする。
【００４０】
このようにすることで、図６（ａ）に示す、従来の分散同期処理システム１ａに比べ、フェーズ３の同期待ちをする時間が大幅に削減されるため、システム全体としての処理速度や各workerの利用効率を改善することが可能となった。
【００４１】
この図６（ｂ）に示した非特許文献４に記載の分散同期処理システム１ｂでは、全ての頂点（vertex）のローカル計算（フェーズＰＨ１）を並列実行できるという前提で評価を行っている。しかしながら、実際には、上記のように、各頂点（vertex）のローカル計算（フェーズＰＨ１）を実行するworkerは、各頂点（vertex）に個別のスレッドを割り当てて処理するため、ＣＰＵの１コアに複数のスレッドが割り当てられた場合に、予期せぬアイドル時間が生じる可能性がある。以下、具体的に説明する。
【００４２】
図７は、本発明の課題を説明するための図である。
ここでは、図７（ａ）に示すように、頂点（vertex）ｖ１，ｖ２，ｖ３をworker１が担当し、頂点（vertex）ｖ４，ｖ５，ｖ６をworker２が担当する。そして、頂点（vertex）間の矢印で示すようなグラフトポロジ（グラフＧ）であるものとする。
また、前提として、各頂点（vertex）には個別のスレッドが割り当てられるものとする。なお、ここでは、プロセスも含め、ＣＰＵの１コアのスケジューリング対象として、個別の実行単位が割り当てられる処理単位をスレッドと称する。
【００４３】
図７（ａ）において、各頂点（vertex）それぞれには１つのスレッドが割り当てられる。図７等では、各workerにおけるスレッド（ここでは、３つのスレッド）を区別するために、濃いドット、薄いドット、ドットなしでスレッドを示している。また、各スレッドの矩形毎に付された番号は、スーパーステップの番号を示し、例えば、頂点（vertex）ｖ１は、スーパーステップＳＳ１〜３を実行することを示す。そして、矩形の１つが、そのworkerのＣＰＵコアにおけるＣＰＵ時間の割り当て単位（Time Slice）を示す。例えば、頂点（vertex）ｖ１は、スーパーステップＳＳ１において、３単位（Time Slice）のＣＰＵ時間の割り当てが必要であり、スーパーステップＳＳ２において、５単位（Time Slice）のＣＰＵ時間の割り当てが必要であり、スーパーステップＳＳ３において、３単位（Time Slice）のＣＰＵ時間の割り当てが必要であることを示している。
【００４４】
図７（ｂ）は、各workerのＣＰＵが１コアである場合のスレッド処理のスケジューリングにおけるＣＰＵ消費を示している。
スレッド処理のスケジューリングは、通常、実行可能なスレッドの割り当て単位（Time Slice）毎にラウンドロビン等で決定されるため、例えば、図７（ａ）の処理を、worker１，２が非特許文献４に記載の隣接同期を用いて実行すると、図７（ｂ）の符号αで示すように、頂点（vertex）ｖ３のスーパーステップＳＳ１が終わらないと、入力辺で接する頂点（vertex）ｖ４，ｖ５，ｖ６は、次のスーパーステップＳＳ２に進めない。よって、アイドル時間（矩形の中を斜線で示す）が発生してしまう。
また、図７（ｂ）の符号βで示すように、頂点（vertex）ｖ３のスーパーステップＳＳ２が終わらないと、入力辺で接する頂点（vertex）ｖ４，ｖ５，ｖ６は、次のスーパーステップＳＳ３に進めない。よって、アイドル時間が発生してしまう。
【００４５】
図７（ｂ）においては、説明を容易にするため、各workerがシングルコアの例で説明しているが、１コアに複数のスレッドが割り当てられる場合には、マルチコアでも同様の問題が発生する。つまり、各workerのリソース制約により、予期せぬアイドル時間が生じる可能性がある。
本実施形態に係る分散同期処理システム１では、後記するように、各頂点（vertex）のスレッドに適切な優先度を付与し、優先度が高いスレッドから優先的にＣＰＵ時間を割り当てることにより、アイドル時間を削減することができる。
【００４６】
≪本実施形態に係る分散同期処理システム≫
次に、本実施形態に係る分散同期処理システム１について説明する。
まず、分散同期処理システム１の処理概要について図８を参照して説明する。
【００４７】
図８は、本実施形態に係る分散同期処理システム１の処理概要を説明するための図である。図８（ａ），（ｂ）は、図７（ａ），（ｂ）において示した図と同様の図であり、非特許文献４の分散同期処理システム１ｂにおいて各頂点（vertex）毎に隣接同期処理を行った場合でのアイドル時間の発生を示している。
図８（ｃ）は、本実施形態に係る分散同期処理システム１のworker（後記する「処理サーバ１０」）が、各頂点（vertex）のスレッドに優先度を付与し、優先度が高いスレッドからＣＰＵ時間を割り当てることにより、アイドル時間を削減した例を示している。
【００４８】
図８（ｃ）においては、worker１が担当する各頂点（vertex）ｖ１，ｖ２，ｖ３の優先度を、優先度の高い順にｖ３，ｖ２，ｖ１とし（以下、「ｖ３＞ｖ２＞ｖ１」のように記載する。）、worker２が担当する各頂点（vertex）ｖ４，ｖ５，ｖ６の優先度を、ｖ５＞ｖ４＞ｖ６とした例を示している。各worker（処理サーバ１０）がこの優先度を導出するための所定のアルゴリズムは後記して詳細に説明する。
【００４９】
各worker（処理サーバ１０）のＣＰＵのスレッド処理のスケジュールにおいて、優先度の高いスレッドからＣＰＵ時間に割り当てることにより、ＣＰＵのアイドル時間を削減することができる。図８（ｃ）では、頂点（vertex）ｖ３の処理待ちのためのアイドル時間をなくして、頂点（vertex）ｖ４が処理を実行することができる（図８（ｃ）の符号α）。これにより、優先度による制御をしていない図８（ｂ）の処理に比べ、worker（処理サーバ１０）のリソース利用効率を向上させ、システム全体として更なる高速化（実行時間の短縮）を図ることができる。
【００５０】
＜分散同期処理システムの構成＞
次に、本実施形態に係る分散同期処理システム１の構成について説明する。
図９は、本実施形態に係る分散同期処理システム１の構成を示す図である。
図９に示すように、分散同期処理システム１は、複数の処理サーバ１０（worker）と、各処理サーバ１０上で動作する複数の分散処理部２０（頂点（vertex））と、を備える。
【００５１】
処理サーバ１０は、ＣＰＵ、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、ＨＤＤ（Hard Disk Drive）等、一般的なコンピュータとしてのハードウエアを備えており、ＨＤＤには、ＯＳ（Operating System）、アプリケーションプログラム、各種データ等が格納されている。ＯＳおよびアプリケーションプログラムは、ＲＡＭに展開され、ＣＰＵによって実行される。なお、図９において、処理サーバ１０および分散処理部２０の内部は、ＲＡＭに展開されたアプリケーションプログラム等によって実現される機能（特徴構成）を、ブロックとして示している。
各処理サーバ１０（worker）上では、個々の計算処理（ローカル計算）に対応した複数の分散処理部２０がＢＳＰ（バルク同期並列）における頂点（vertex）として動作する。
以下、分散同期処理システム１を構成する各装置について詳細に説明する。
【００５２】
＜分散処理部（頂点（vertex））＞
分散処理部２０（頂点（vertex））は、ＢＳＰにおける所定の単位に区分された計算処理を実行し、数値計算部２１、メッセージ送受信部２２および状態通知部２３を含んで構成される。また、後記するように、処理サーバ１０（worker）の優先度算出アルゴリズムの設定に伴い、処理待ち投票部２４を備える場合がある。
【００５３】
数値計算部２１は、ＢＳＰにおけるフェーズＰＨ１（ローカル計算）の処理を実行する。この数値計算部２１は、メッセージ送受信部２２を介して処理サーバ１０（worker）から受信する、次のスーパーステップへの移行指示（以下、「次ステップ移行指示」と称する。）に従い、次のスーパーステップへの移行を行う。なお、数値計算部２１は、自身の計算・送信処理ｆｎが完了した後、次ステップ移行指示を受信するまで待機する。
【００５４】
メッセージ送受信部２２は、他の分散処理部２０や処理サーバ１０（worker）との間での情報の送受信を行う。具体的には、メッセージ送受信部２２は、ＢＳＰにおけるフェーズＰＨ２（データ交換）において、自身の出力辺の状態を出力メッセージとして、その出力辺で接続する分散処理部２０（頂点（vertex））へ向けて送信する。なお、この出力メッセージには、その出力辺の状態に対応付けてその時点でのスーパーステップのステップ番号が付される。また、メッセージ送受信部２２は、入力辺で接続する分散処理部２０（頂点（vertex））から入力辺の状態を入力メッセージとして受信する。また、この入力メッセージには、その入力辺に状態に対応付けてその時点でのスーパーステップのステップ番号が付される。なお、メッセージ送受信部２２は、この出力メッセージおよび入力メッセージを、処理サーバ（worker）１０のメッセージ処理部１２を介して送受信する。
また、このメッセージ送受信部２２は、自身が属する処理サーバ１０（worker）から、次ステップ移行指示を受信し、数値計算部２１に出力する。
【００５５】
状態通知部２３は、ＢＳＰにおける自身の分散処理部２０（頂点（vertex））の状態を監視し、処理サーバ１０（worker）に状態情報として通知する。
具体的には、状態通知部２３は、後記する処理サーバ１０の優先度設定部１４に設定された所定の優先度設定アルゴリズムで必要となる自身の状態情報を検出し、処理サーバ１０に送信する。
例えば、状態通知部２３は、「計算・送信処理」（フェーズＰＨ１における計算処理およびフェーズＰＨ２におけるデータ交換）の際、自身の計算処理と出力メッセージ（出力辺の状態）の送信が終わった時点において、入力辺で接する他の分散処理部２０（頂点（vertex））からの入力メッセージがない状態（入力辺で接する全ての頂点（vertex）から入力メッセージを受信できていない状態）（以下、「入力待ち状態」と称する。）である場合に、自身が「入力待ち状態」であることを、処理サーバ１０（worker）に通知する。
状態通知部２３は、入力待ち状態であることを処理サーバ１０に通知する際に、現在の自身のスーパーステップｎのステップ番号を付して、通知するようにする。
【００５６】
処理サーバ１０の後記する優先度設定部１４に、優先度算出アルゴリズムとして「遅延頂点投票方式」が設定された場合、分散処理部２０（頂点（vertex））には、処理待ち投票部２４が設けられる。
【００５７】
処理待ち投票部２４は、フェーズＰＨ１における計算処理およびフェーズＰＨ２における出力メッセージの送信処理が終わった時点において、入力辺で接する他の分散処理部２０（頂点（vertex））からの入力メッセージがないために入力待ち状態となっている場合に、その入力辺で接する他の分散処理部２０（頂点（vertex））に「入力待ち情報」を送信する。各分散処理部２０（頂点（vertex））の処理待ち投票部２４は、スレッド処理の優先順を決定する指標となる優先度投票値を状態情報（初期値＝０）として保持しており、他の分散処理部２０（頂点（vertex））から、入力待ち情報を１つ受信する度に、自身の優先度投票値を「＋１」に更新する。そして、処理待ち投票部２４は、更新した自身の優先度投票値を処理サーバ１０に送信する。
なお、処理待ち投票部２４の上記処理（詳細は、図１３（ａ）を参照し後記する。）は、処理サーバ１０の優先度設定部１４に、優先度算出アルゴリズムとして「遅延頂点投票方式（パターン１）」が設定された場合の処理である。
【００５８】
処理待ち投票部２４は、入力辺で接する他の分散処理部２０（頂点（vertex））から入力待ち情報を受信した場合に、自身が「入力待ち状態」または「実行可能状態」（フェーズＰＨ１のローカル計算とフェーズＰＨ２のデータ交換が完了し、次のスーパーステップｎ＋１のローカル計算を実行可能である状態）に該当するか否かを判定する。
そして、処理待ち投票部２４は、自身が入力待ち状態である場合に、受信した入力待ち情報に付された他の分散処理部２０（頂点（vertex））の優先度投票値を、自身が保持する優先度投票値に加える。そして、処理待ち投票部２４は、自身の遅延分（「＋１」）を加えて自身の優先度投票値を更新し、入力待ちとなっている他の分散処理部２０（頂点（vertex））に、更新した優先度投票値を入力待ち情報に付して送信する。
また、処理待ち投票部２４は、自身が実行可能状態である場合に、受信した入力待ち情報に付された他の分散処理部２０（頂点（vertex））の優先度投票値を、自身が保持する優先度投票値に加える。そして、処理待ち投票部２４は、自身が保持する優先度投票値を処理サーバ１０に送信する。
なお、処理待ち投票部２４の上記処理（詳細は、図１３（ｂ）参照し後記する。）は、処理サーバ１０の優先度設定部１４に、優先度算出アルゴリズムとして「遅延頂点投票方式（パターン２）」が設定された場合の処理である。
【００５９】
この処理待ち投票部２４は、他の分散処理部２０（頂点（vertex））から入力待ち情報を受信した時点におけるスーパーステップでの処理が完了すると、自身の優先度投票値をゼロに初期化する。
【００６０】
＜処理サーバ（worker）＞
処理サーバ１０（worker）（図９参照）は、他の処理サーバ１０（worker）と通信接続され、処理単位となる分散処理部２０（頂点（vertex））を複数備える。この処理サーバ１０（worker）は、自身が備える分散処理部２０（vertex）の処理の進行状態等を管理するとともに、他の処理サーバ１０（worker）との間での情報の送受信を行う。また、この処理サーバ１０（worker）は、仮想化制御部１１、メッセージ処理部１２、隣接同期分散管理部１３、優先度設定部１４および記憶部１５を含んで構成される。なお、この記憶部１５には、計算対象となる各分散処理部２０（頂点（vertex））の接続関係を示すグラフトポロジが記憶される。
【００６１】
仮想化制御部１１は、仮想化技術に基づき、処理サーバ１０上に仮想化プラットホームを構築し、複数の分散処理部２０（仮想マシン）を配置する制御を行う。
【００６２】
メッセージ処理部１２は、自身に属する各分散処理部２０（頂点（vertex））から、ＢＳＰにおけるフェーズＰＨ２（データ交換）の際に、出力辺の状態を示す出力メッセージを受け取り、計算対象のグラフＧのグラフトポロジに基づき、その出力辺で接続する分散処理部２０（頂点（vertex））に、受信した出力メッセージを、入力辺の状態を示す入力メッセージとして出力する。なお、以降、出力メッセージと入力メッセージとを特に区別しない場合、単に「メッセージ」と称する場合がある。
【００６３】
隣接同期分散管理部１３は、自身に属する分散処理部２０（頂点（vertex））を監視し、各分散処理部２０（頂点（vertex））が、フェーズＰＨ１における計算処理およびフェーズＰＨ２における出力メッセージの送信処理が終わった時点において、入力辺で接する全ての分散処理部２０（頂点（vertex））からの入力メッセージ（入力辺の状態）が揃っているか否かを判定する。
【００６４】
そして、隣接同期分散管理部１３は、自身に属する分散処理部２０（頂点（vertex））それぞれについて、入力メッセージ（入力辺の状態）が揃っている場合、つまり、隣接する分散処理部２０（頂点（vertex））から、次の計算ステップ（次のスーパーステップ）において必要な計算結果の取得が完了している場合には、本実施形態における隣接同期の条件「自頂点（vertex）および入力辺で接する全ての頂点（vertex）の計算・送信処理ｆｎ（ローカル計算（フェーズＰＨ１）およびデータ交換（フェーズＰＨ２））が完了していること」（隣接同期）を満たすものとする。隣接同期分散管理部１３は、この場合に、次のスーパーステップに移行する（スーパーステップを「＋１」する。）ように、「次ステップ移行指示」を、その分散処理部２０（頂点（vertex））に出力する。
また、隣接同期分散管理部１３は、その分散処理部２０（頂点（vertex））が隣接同期の条件を満たしたこと、つまり、実行可能状態であることを優先度設定部１４に出力する。
【００６５】
隣接同期分散管理部１３は、入力辺で接する他の分散処理部２０（頂点（vertex））からの入力メッセージの入力待ち状態となっている分散処理部２０が、いずれかの分散処理部２０）から入力メッセージ（入力辺の状態）を受信した場合には、その受信を契機として、再度、入力メッセージ（入力辺の状態）が揃っているか否か、つまり、隣接同期の条件を満たすか否かの判定を実行する。
【００６６】
優先度設定部１４は、実行可能状態となった各分散処理部２０（頂点（vertex））のスレッドに所定の優先度算出アルゴリズムの方式で算出した優先度を付し、優先度の高いスレッドから順にＣＰＵ時間を割り当てるスケジューリングを行う。優先度設定部１４がスケジューリングしたＣＰＵ時間の割り当てにそって、各分散処理部２０（頂点（vertex））のＣＰＵによる処理が実行させる。
【００６７】
優先度設定部１４には、例えば、以下に示す優先度算出アルゴリズムのいずれかが設定される。
（１）出力辺数優先方式（ＬＥＦ：Largest Edge First）
（２）遅延ステップ優先方式（ＬＳＦ：Latest Step First）
（３）出力辺数および遅延ステップの複合優先方式（ＨＬ２：Hybrid of LEF and LSF）
（４）遅延投票数優先方式（ＭＶＦ：Most Voted First）
以下、各方式について、具体的に説明する。
【００６８】
［出力辺数優先方式（ＬＥＦ）］
出力辺数優先方式（ＬＥＦ）は、実行可能状態（フェーズＰＨ１のローカル計算とフェーズＰＨ２のデータ交換が完了し、次のスーパーステップのローカル計算を実行可能である状態）の分散処理部２０（頂点（vertex））のうち、出力辺の数が最も多い分散処理部２０（頂点（vertex））にＣＰＵ時間を優先して割り当てる方式である。この出力辺数優先方式（ＬＥＦ）は、出力辺の数が多い、つまり、隣接する頂点（vertex）が多いほど、より多くの頂点（vertex）に影響を及ぼすため、優先的にＣＰＵ時間を割り当てるべき、というロジックに基づく。
【００６９】
例えば、図１０に示すグラフトポロジ（グラフＧ）の場合では、worker１（処理サーバ１０）の３つの頂点（vertex）ｖ１，ｖ２，ｖ３の各出力辺の数は、「１：１：４」となるため、優先度を「ｖ３＞ｖ２＝ｖ１」と設定する。また、worker２（処理サーバ１０）の３つの頂点（vertex）ｖ４，ｖ５，ｖ６の各出力辺の数は、「１：３：０」となるため、優先度を「ｖ５＞ｖ４＞ｖ６」と設定する。
ここで、優先度設定部１４は、算出した優先度が同じである場合には、ランダムにどちらかの頂点（vertex）を優先させて設定してもよいし、同じ優先度の頂点（vertex）のスレッドを、ＣＰＵ時間の割り当て単位（Time Slice）毎に交互に実行するように設定してもよい。
【００７０】
図８（ｃ）に示すＣＰＵ消費の優先度制御の結果は、出力辺数優先方式（ＬＥＦ）において、図１０に示すように、頂点ｖ２と頂点ｖ１の優先度が同じ（ｖ２＝ｖ１）であった場合に、頂点ｖ２を頂点ｖ１より優先するように設定し、全体の優先度を「ｖ３＞ｖ２＞ｖ１」として設定した例を示している。
このように、優先度設定部１４が、優先度を適切に設定することにより、ＣＰＵのアイドル時間を削減することが可能となる。
【００７１】
［遅延ステップ優先方式（ＬＳＦ）］
遅延ステップ優先方式（ＬＥＦ）は、実行可能状態の分散処理部２０（頂点（vertex））のうち、実行ステップ（現時点のスーパーステップ）が最も遅い分散処理部２０（頂点（vertex））にＣＰＵ時間を優先して割り当てる方式である。この遅延ステップ優先方式（ＬＥＦ）は、スーパーステップの処理が遅れている頂点（vertex）ほど、隣接する頂点（vertex）により大きな影響を及ぼすため、優先的にＣＰＵ時間を割り当てるべき、というロジックに基づく。
【００７２】
例えば、図１１に示すグラフトポロジ（グラフＧ）の場合では、worker１（処理サーバ１０）の３つの頂点（vertex）ｖ１，ｖ２，ｖ３それぞれの現時点のスーパーステップｎは、「４：５：５」となるため、優先度を「ｖ１＞ｖ２＝ｖ３」と設定する。また、worker２（処理サーバ１０）の３つの頂点（vertex）ｖ４，ｖ５，ｖ６それぞれのスーパーステップｎは、「５：５：４」となるため、優先度を「ｖ６＞ｖ４＝ｖ５」と設定する。
ここで、優先度設定部１４は、算出した優先度が同じである場合には、ランダムにどちらかの頂点（vertex）を優先させて設定してもよいし、同じ優先度の頂点（vertex）のスレッドを、ＣＰＵ時間の割り当て単位（Time Slice）毎に交互に実行するように設定してもよい。
【００７３】
優先度設定部１４は、実行可能状態の分散処理部２０（頂点（vertex））について、その実行ステップ（現時点のスーパーステップ）が変わる度に、動的に優先度を算出し直して更新する。
【００７４】
［出力辺数および遅延ステップの複合優先方式（ＨＬ２）］
出力辺数および遅延ステップの複合優先方式（ＨＬ２）（以下「複合優先方式（ＨＬ２）」と略す。）は、実行可能状態の分散処理部２０（頂点（vertex））のうち、出力辺の数と実行ステップの双方に基づき、各頂点（vertex）の優先度を算出し、優先度が最も高い頂点（vertex）にＣＰＵ時間を優先して割り当てる方式である。この複合優先方式（ＨＬ２）は、どの頂点（vertex）にＣＰＵ時間を優先して割り当てるべきかは、出力辺の数、実行ステップのいずれか一方のみではなく双方を考慮すべき、というロジックに基づく。
【００７５】
優先度設定部１４は、出力辺数に基づく優先度（第１の優先度）、実行ステップに基づく優先度（第２の優先度）のそれぞれに重みをかけ、その和を算出する。複合優先方式（ＨＬ２）の優先度の算出式（式１）を、図１２に示す。優先度設定部１４は、（式１）を用いて、各頂点（vertex）の優先度を算出し、その算出した値が高い頂点（vertex）を優先してＣＰＵ時間を割り当てる。
【００７６】
［遅延投票数優先方式（ＭＶＦ）］
遅延投票数優先方式は、遅延している頂点（vertex）に対し、その頂点（vertex）からの入力メッセージ待ちで待機状態（入力待ち状態）にある頂点（vertex）が投票し、投票数が最も多い頂点（vertex）にＣＰＵ時間を優先して割り当てる方式である。この遅延投票数優先方式（ＭＶＦ）は、実際に隣接する頂点（vertex）を入力待ち状態にさせている頂点（vertex）に対し、優先的にＣＰＵ時間を割り当てるべき、というロジックに基づく。
【００７７】
この遅延投票数優先方式（ＭＶＦ）では、各分散処理部２０（頂点（vertex））の処理待ち投票部２４から上記の優先度投票値を受信し、その値がより高い頂点（vertex）を優先してＣＰＵ時間を割り当てる。
具体的には、優先度設定部１４は、各分散処理部２０（頂点（vertex））の処理待ち投票部２４と連携して以下の処理を実行する。
【００７８】
（パターン１：自身の遅延のみを投票）
各分散処理部２０（頂点（vertex））の処理待ち投票部２４は、入力待ち状態となった、つまり、遅延の原因となっている頂点（vertex）に入力待ち情報を送信する。つまり、処理待ち投票部２４が、遅延の原因となっている頂点（vertex）に１票を投票する。これにより、入力待ち情報を受信した分散処理部２０（頂点（vertex））の処理待ち投票部２４は、自身の優先度投票値（Ｐｖ）を「＋１」に更新する。
図１３（ａ）に示す例では、頂点ｖ２が、頂点ｖ１からの入力メッセージ待ちで待機状態（入力待ち状態）になると、遅延の原因となっている頂点ｖ１に、入力待ち情報を送信（１票を投票）する（図１３（ａ）の符号α１）。これにより、頂点ｖ１の処理待ち投票部２４は、優先度投票値（Ｐｖ１）を「＋１」に更新する（図１３（ａ）の符号α２）。
【００７９】
各分散処理部２０（頂点（vertex））の処理待ち投票部２４は、優先度投票値が更新されると、処理サーバ１０の優先度設定部１４に、その更新した優先度投票値を送信する。そして、優先度設定部１４が、受信した優先度投票値が高い分散処理部２０（頂点（vertex））のスレッドを優先するように優先度の設定を行い、ＣＰＵ時間を割り当てる。
【００８０】
（パターン２：遅延の連鎖を投票）
各分散処理部２０（頂点（vertex））の処理待ち投票部２４は、自頂点（vertex）が遅延の原因となっており、入力待ち情報を受信して自身の優先度投票値を更新した場合、その更新した優先度投票値に、自身の遅延分（＋１）を加えて、遅延の原因となっている頂点（vertex）に入力待ち情報を送信（優先度投票値を投票）する（図１３の符号β１）。
【００８１】
図１３（ｂ）に示す例では、頂点ｖ６が遅延の原因になっている頂点とすると、頂点ｖ６からの入力メッセージ待ちで、頂点ｖ４が遅延する。さらに、頂点ｖ４からの入力メッセージ待ちで、頂点ｖ２，ｖ３，ｖ５が遅延する（図１３（ｂ）の符号β２）。
よって、頂点ｖ２は、頂点ｖ４に入力待ち情報（１票）を送信する。また、頂点ｖ２は、頂点ｖ３にも入力待ち情報（１票）を送信する。頂点ｖ３は、優先度投票値を更新（＋１）し、自身の遅延分（＋１）を加えた入力待ち情報（２票）を頂点ｖ４に送信する。頂点ｖ５は、頂点ｖ４に入力待ち情報（１票）を送信する。そして、頂点ｖ４は、受信した入力待ち情報を合計（１＋２＋１＝４票）に、自身の遅延分（＋１）を加えた入力待ち情報（５票）を、頂点ｖ６に送信する。
【００８２】
各分散処理部２０（頂点（vertex））の処理待ち投票部２４は、自身が実行可能状態である場合において、入力待ち情報を他の分散処理部２０（頂点（vertex））から受信したときに、受信した入力待ち情報に付された優先度投票値を用いて自身の優先度投票値を更新する。そして、その処理待ち投票部２４は、処理サーバ１０の優先度設定部１４に、その更新した優先度投票値を送信する。
図１３（ｂ）では、頂点ｖ５の優先度投票値（初期値＝０）の場合に、頂点ｖ４から入力待ち情報（優先度投票値＝５票）を受信したとき、頂点ｖ５の処理待ち投票部２４は、自身の優先度投票値を更新（０＋５＝５票）し、その更新した優先度投票値（５票）を、処理サーバ１０の優先度設定部１４に送信する。そして、優先度設定部１４は、受信した優先度投票値が高い分散処理部２０（頂点（vertex））のスレッドを優先するように優先度の設定を行い、ＣＰＵ時間を割り当てる。
【００８３】
このように、遅延している頂点（vertex）に対し、その頂点（vertex）からの入力メッセージ待ちで待機状態（入力待ち状態）にある頂点（vertex）が投票し、投票数が最も多い頂点（vertex）にＣＰＵ時間を優先して割り当てる。これにより、より影響範囲の広い（影響度の高い）頂点（vertex）ほど優先度を高くすることができる。
【００８４】
≪分散同期処理システムの動作≫
次に、本実施形態に係る分散同期処理システム１の動作について説明する。
図１４は、本実施形態に係る分散同期処理システム１の処理の流れを示すフローチャートである。
なお、ここでは、予め対象とする計算処理に必要な個々の計算処理（頂点（vertex））の設定と、その個々の計算処理（頂点（vertex））の各処理サーバ１０（worker）への割り振りが終わっているものとして説明する。この個々の計算処理（頂点）の設定と、各処理サーバ１０（worker）への割り振りとは、例えば、これらの機能を、システム全体の管理サーバを備えさせたり、処理サーバ１０の中の代表サーバに備えさせたりすることにより、事前に実行しておけばよい。
【００８５】
まず、処理サーバ１０の隣接同期分散管理部１３は、自身に属する分散処理部２０（頂点）を監視することにより、ある分散処理部２０（頂点）について、フェーズＰＨ１における計算処理およびフェーズＰＨ２における出力メッセージの送信処理が完了したことを検出する（ステップＳ１）。
【００８６】
続いて、隣接同期分散管理部１３は、その分散処理部２０（頂点）について、入力辺で接する全ての分散処理部２０（頂点）からの入力メッセージ（入力辺の状態）が揃っているか否かを判定する（ステップＳ２）。つまり、隣接同期分散管理部１３は、隣接同期の条件を満たすか否かを判定する。
【００８７】
ここで、隣接同期分散管理部１３は、入力メッセージ（入力辺の状態）が揃っていないと判定した場合には（ステップＳ２→Ｎｏ）、その分散処理部２０（頂点）が入力待ち状態であると把握する（ステップＳ３）。なお、隣接同期分散管理部１３は、各分散処理部２０（頂点）から入力待ち状態であることの通知を受信することにより、その分散処理部２０（頂点）が入力待ち状態であることを把握してもよい。
【００８８】
続いて、隣接同期分散管理部１３は、入力待ち状態で待機している分散処理部２０（頂点）に対し、入力辺で接するいずれかの分散処理部２０（頂点）から、当該分散処理部２０（頂点）が入力メッセージ（入力辺の状態）を受信したか否かを判定する（ステップＳ４）。
そして、隣接同期分散管理部１３は、入力待ち状態で待機している分散処理部２０（頂点）が入力メッセージを受信していなければ（ステップＳ４→Ｎｏ）、受信するまで待つ。一方、隣接同期分散管理部１３は、入力待ち状態で待機している分散処理部２０（頂点）が入力メッセージを受信した場合には（ステップＳ４→Ｙｅｓ）、そのことを契機として、ステップＳ２に戻る。
【００８９】
ステップＳ２において、隣接同期分散管理部１３は、入力メッセージ（入力辺の状態）が揃っている（隣接同期の条件を満たす）と判定した場合には（ステップＳ２→Ｙｅｓ）、ステップＳ５に進む。
【００９０】
ステップＳ５において、優先度設定部１４は、実行可能状態となった分散処理部２０（頂点）のスレッドに、所定の優先度算出アルゴリズムの方式で優先度を算出し、その算出した優先度の高いスレッドから順にＣＰＵ時間を割り当てるスケジューリングを行う（優先度設定処理を実行）。
【００９１】
なお、優先度設定部１４に、上記した、（１）出力辺数優先方式（ＬＥＦ）、（２）遅延ステップ優先方式（ＬＳＦ）、（３）出力辺数および遅延ステップの複合優先方式（ＨＬ２）、（４）遅延投票数優先方式（ＭＶＦ）のいずれかが、予め設定されることにより、ステップＳ５の優先度設定処理が実行される。
【００９２】
また、隣接同期分散管理部１３は、ステップＳ２において隣接同期の条件を満たした分散処理部２０（頂点）について、次のスーパーステップに移行するように、「次ステップ移行指示」を出力する（ステップＳ６）。これにより、「次ステップ移行指示」を受信した分散処理部２０（頂点）の数値計算部２１は、次のスーパーステップ（ｎ＋１）の計算・送信処理ｆｎ＋１を実行する。
【００９３】
以上説明したように、本実施形態に係る分散同期処理システム１および分散同期処理方法によれば、処理サーバ１０（worker）のリソース制約による予期せぬアイドル時間を抑制することができる。
これにより、各処理サーバ１０（worker）のリソース利用効率が向上し、同期処理計算の高速化（実行時間の短縮）を図ることができる。
【００９４】
なお、本実施形態においては、隣接同期の条件を満たすか否かの判定を、各処理サーバ１０（worker）において、自律分散的に実行するものとした。しかしながら、分散同期処理システム１において、各処理サーバ１０（worker）と通信接続される管理サーバ（master）を設け、その管理サーバ（master）が、各分散処理部２０（頂点（vertex））について、隣接同期の条件を満たすか否かの判定を行うようにしてもよい。
【符号の説明】
【００９５】
１      分散同期処理システム
１０    処理サーバ（worker）
１１    仮想化処理部
１２    メッセージ処理部
１３    隣接同期分散管理部
１４    優先度設定部
１５    記憶部
２０    分散処理部２０（頂点（vertex））
２１    数値計算部
２２    メッセージ送受信部
２３    状態通知部
２４    処理待ち投票部
【図１】
2018136588.tif 000003
【図２】
2018136588.tif 000004
【図３】
2018136588.tif 000005
【図４】
2018136588.tif 000006
【図５】
2018136588.tif 000007
【図６】
2018136588.tif 000008
【図７】
2018136588.tif 000009
【図８】
2018136588.tif 000010
【図９】
2018136588.tif 000011
【図１０】
2018136588.tif 000012
【図１１】
2018136588.tif 000013
【図１２】
2018136588.tif 000014
【図１３】
2018136588.tif 000015
【図１４】
2018136588.tif 000016