(57)【要約】 【課題】分散計算環境でパラメータを計算する際のパラメータ等の中間計算結果の授受のための通信量を削減する。【解決手段】通信システムは、複数のノードがそれぞれ担当するデータを用いて要素を計算する分散計算環境を構成する一のノードが計算した要素が、次に当該要素を必要とするノードへと直接通信できるか否かを判定する直接通信判定手段と、前記直接通信判定手段の判定の結果をもとに、前記ノード間での要素の直接的な通信を計画する直接通信計画手段と、前記計画に従って、前記ノード間の通信を実現する通信手段と、を備える。【選択図】図１
2018120470.tif 000002
【特許請求の範囲】
【請求項１】
複数のノードがそれぞれ担当するデータを用いて要素を計算する分散計算環境を構成する一のノードが計算した要素が、次に当該要素を必要とするノードへと直接通信できるか否かを判定する直接通信判定手段と、
前記直接通信判定手段の判定の結果をもとに、前記ノード間での要素の直接的な通信を計画する直接通信計画手段と、
前記計画に従って、前記ノード間の通信を実現する通信手段と、
を備えることを特徴とする通信システム。
【請求項２】
さらに、予め作成された前記ノード間の通信計画及び前記直接通信計画手段により作成される直接的な通信計画を保持する通信情報記録部を備え、
前記通信手段は、前記通信情報記録部に保持されている通信計画及び直接的な通信計画に基づいて、前記ノード間の通信を実現する請求項１の通信システム。
【請求項３】
さらに、それぞれのノードにおいて更新される要素を記憶する更新要素記憶部を備え、
前記直接通信判定手段は、前記更新要素記憶部を参照して、ある計算ステップにおいて、ある要素を計算するノードが１つである場合、直接通信可能と判定する請求項１又は２の通信システム。
【請求項４】
前記直接通信計画手段は、
前記直接通信判定手段により、直接通信可能と判定されたステップと要素の組に対して、前記要素が更新された前記ステップの近傍のステップを特定し、
前記通信計画から、前記近傍のステップ及び前記直接通信可能と判定されたステップとの前記要素に係る間接的な通信を削除し、前記通信計画に、前記要素に係る直接的な通信を追加する請求項２又は３の通信システム。
【請求項５】
前記通信情報記録部は、前記計算した要素を所定のノードに集約する通信にかかる情報を記録するｒｅｄｕｃｅ通信要素テーブルと、前記集約した要素を次のステップで必要となるノードに拡散するｂｒｏａｄｃａｓｔ通信要素テーブルと、ノード間での要素の直接的な通信に係る情報を記録する直接通信要素テーブルと、を備え、
前記通信手段は、前記各テーブルに記録された情報に従って、前記ノード間の通信を実現する請求項２の通信システム。
【請求項６】
前記要素は、機械学習に用いるモデルのパラメータを修正するための差分値である請求項１から５いずれか一に記載の通信システム。
【請求項７】
請求項１から６いずれか一に記載の通信システムと、
複数のノードがそれぞれ担当するデータを用いて要素を計算する分散計算環境を構成する一のノードと、を含む分散計算システム。
【請求項８】
複数のノードがそれぞれ担当するデータを用いて要素を計算する分散計算環境を構成する一のノードが計算した要素が、次に当該要素を必要とするノードへと直接通信できるか否かを判定する直接通信判定手段と、
前記直接通信判定手段の判定の結果をもとに、前記ノード間での要素の直接的な通信を計画する直接通信計画手段と、
前記計画に従って、前記ノード間の通信を実現する通信手段と、
を備えることを特徴とするノード。
【請求項９】
複数のノードがそれぞれ担当するデータを用いて要素を計算する分散計算環境に配置されたコンピュータが、
前記分散計算環境を構成する一のノードが計算した要素が、次に当該要素を必要とするノードへと直接通信できるか否かを判定するステップと、
前記判定の結果をもとに、前記ノード間での要素の直接的な通信を計画するステップと、
前記計画に従って、前記ノード間の通信を実現するステップと、
を含むことを特徴とするノード間の情報共有方法。
【請求項１０】
複数のノードがそれぞれ担当するデータを用いて要素を計算する分散計算環境に配置されたコンピュータに、
前記分散計算環境を構成する一のノードが計算した要素が、次に当該要素を必要とするノードへと直接通信できるか否かを判定する処理と、
前記判定の結果をもとに、前記ノード間での要素の直接的な通信を計画する処理と、
前記計画に従って、前記ノード間の通信を実現する処理と、
を実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信システム、分散計算システム、ノード、情報共有方法及びプログラムに関し、特に、分散計算環境を構成する複数のノード間の通信を担う通信システム、分散計算システム、ノード、情報共有方法及びプログラムに関する。
【背景技術】
【０００２】
機械学習が近年積極的に研究されている。機械学習は、多数のデータから規則性を学習して、未知の事象に対して予測を行うことを目的とする。予測式（モデルともいう）をパラメータで表し、データを正しく説明できるように、パラメータの値をデータにもとづき最適化する。予測式のパラメータの数は数個から多ければ数千万程度まで及ぶ。
【０００３】
疎なデータやモデルの学習に注目が集まっている。具体的な応用先として、文書解析や商品の推薦がある。疎なデータとは、データを特徴づける次元が大量にある（例えば文章に含まれる語彙数、数千万オーダー）が、データの個々のサンプル（文書解析で言えば個々の文書）に含まれる単語は少数である、という特徴がある。疎なデータを学習するときは、モデルのパラメータがデータの特徴に対応するため、パラメータの数は膨大になる。
データの容量が増えるにしたがって、処理時間が増加する。そのため機械学習を分散した計算ノードで実行することがある。単一のノードにおける計算処理量を減らし、実行完了までの時間を短縮する。例えば、特許文献１に、分散計算機システムを用いて機械学習を行う構成が開示されている。
【０００４】
機械学習におけるモデルパラメータの最適化には、一度の処理でデータ全体を用いる勾配降下法という手法と、データの一部だけを利用する確率的勾配降下法という手法がある。処理に用いるデータの部分集合を「ミニバッチ」と呼ぶ。確率的勾配降下法とは、パラメータの更新部分を計算するときに、データ全体を利用するのではなく、所定のミニバッチを利用する（利用するミニバッチは毎回変える）。分散ノードでこれを行う場合は、各ミニバッチを用いた計算ごとに、計算結果を集約してパラメータを更新して、更新したパラメータを次のミニバッチを用いた計算に利用できるように通信する。例えば、特許文献２に、複数の計算ノード部とパラメタ更新処理部を備えて確率的勾配降下法によるパラメタ学習を行うパラメタ学習装置が開示されている。
【０００５】
その他非特許文献１、２に、分散ノード環境で機械学習を行う際の、パラメータの通信と管理を行うパラメータサーバが提案されている。パラメータサーバは、分散した計算ノードと協調して動作し、計算ノードの通知によりパラメータを送信する。計算ノードは計算を行い、変化したパラメータ（の変化分）をパラメータサーバに対して送信する。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２０１２−２２５５８号公報
【特許文献２】特開２０１２−７９０８０号公報
【非特許文献】
【０００７】
【非特許文献１】Ｍu Li, et al. "Scaling distributed machine learning with the parameter server." 11th USENIX Symposium on Operating Systems Design and Implementation (OSDI 14). 2014.
【非特許文献２】Ｍu Li, et al. "Communication efficient distributed machine learning with the parameter server." Advances in Neural Information Processing Systems. 2014.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
以下の分析は、本発明によって与えられたものである。疎なデータに対する機械学習において、確率的勾配降下法を適用することを考える。疎なデータは、サンプルに含まれる特徴の数が、全体に比して非常に少ない。ミニバッチに含まれるサンプルが多くないのであれば、ミニバッチに含まれる特徴の数が全体に比して少なくなり、そのミニバッチを利用した計算により更新されるパラメータも全体に比して少なくなる。
【０００９】
非特許文献１、２では、計算ノードで計算を行った結果を、一度サーバに送信し、次のステップでその値が必要な計算ノードに送信している。特許文献１、２も、それぞれ分散モデル更新部及びパラメタ更新処理部がパラメータの収集と配布を行っている。
【００１０】
しかしながら、次のステップで値が必要な計算ノードがもしひとつだけであれば、サーバに送信して、計算ノードに送信するという処理を踏む必要はなく、直接に値を必要とするノードに送信すれば十分である。このように、パラメータサーバに代表される要素の集約と分散を行う方式においては、一部で不要な通信が発生している。
【００１１】
本発明は、分散計算環境でパラメータを計算する際のパラメータ等の中間計算結果の授受のための通信量の削減に貢献できる通信システム、分散計算システム、ノード、情報共有方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
第１の視点によれば、複数のノードがそれぞれ担当するデータを用いて要素を計算する分散計算環境を構成する一のノードが計算した要素が、次に当該要素を必要とするノードへと直接通信できるか否かを判定する直接通信判定手段を備える通信システムが提供される。この通信システムは、さらに、前記直接通信判定手段の判定の結果をもとに、前記ノード間での要素の直接的な通信を計画（直接通信計画）する直接通信計画手段を備える。さらに、この通信システムは、前記直接通信計画に従って、前記ノード間の通信を実現する通信手段とを備える。
【００１３】
第２の視点によれば、上記した通信システムと、複数のノードがそれぞれ担当するデータを用いて要素を計算する分散計算環境を構成する一のノードと、を含む分散計算システムが提供される。
【００１４】
第３の視点によれば、上記した通信システムに相当する機能を備えるノードが提供される。
【００１５】
第４の視点によれば、複数のノードがそれぞれ担当するデータを用いて要素を計算する分散計算環境に配置されたコンピュータが、前記分散計算環境を構成する一のノードが計算した要素が、次に当該要素を必要とするノードへと直接通信できるか否かを判定するステップと、前記判定の結果をもとに、前記ノード間での要素の直接的な通信を計画（直接通信計画）するステップと、前記直接通信計画に従って、前記ノード間の通信を実現するステップと、を含むノード間の情報共有方法が提供される。本方法は、分散計算環境に配置されて要素に通信を制御するコンピュータという、特定の機械に結びつけられている。
【００１６】
第５の視点によれば、複数のノードがそれぞれ担当するデータを用いて要素を計算する分散計算環境に配置されたコンピュータに、前記分散計算環境を構成する一のノードが計算した要素が、次に当該要素を必要とするノードへと直接通信できるか否かを判定する処理と、前記判定の結果をもとに、前記ノード間での要素の直接的な通信を計画（直接通信計画）する処理と、前記直接通信計画に従って、前記ノード間の通信を実現する処理と、を実行させるプログラムが提供される。なお、このプログラムは、コンピュータが読み取り可能な（非トランジエントな）記憶媒体に記録することができる。即ち、本発明は、コンピュータプログラム製品として具現することも可能である。
【発明の効果】
【００１７】
本発明によれば、分散計算環境でパラメータを計算する際のパラメータ等の中間計算結果の授受のための通信量を削減することが可能となる。
【図面の簡単な説明】
【００１８】
【図１】本発明の一実施形態の構成を示す図である。
【図２】本発明が好適に適用される分散計算システムの構成例を示す図である。
【図３】本発明の第１の実施形態の通信システムの構成を示す図である。
【図４】本発明の第１の実施形態の通信システムの更新要素記憶部に保持される情報（更新対象要素テーブル）の一例を示す図である。
【図５】本発明の第１の実施形態の通信システムの通信情報記録部に保持される情報（ｒｅｄｕｃｅ通信要素テーブル）の一例を示す図である。
【図６】本発明の第１の実施形態の通信システムの通信情報記録部に保持される情報（Ｂｒｏａｄｃａｓｔ通信要素テーブル）の一例を示す図である。
【図７】本発明の第１の実施形態の通信システムの通信情報記録部に保持される情報（直接通信要素テーブル）の一例を示す図である。
【図８】本発明の第１の実施形態の通信システムの通信情報記録部に保持される情報（担当範囲テーブル）の一例を示す図である。
【図９】本発明の第１の実施形態の通信システムの動作を表したフローチャートである。
【図１０】本発明の第２の実施形態の通信システムの構成を示す図である。
【図１１】本発明の第２の実施形態の通信システムの直接通信判定手段の詳細構成を示す図である。
【図１２】本発明の第２の実施形態の通信システムの直接通信計画手段の詳細構成を示す図である。
【図１３】本発明の第２の実施形態の通信システムの動作を表した流れ図である。
【図１４】図１３のステップＳ２０１の詳細を表したフローチャートである。
【図１５】図１３のステップＳ２０３の詳細を表したフローチャートである。
【図１６】図１３のステップＳ２０３の詳細を表した別のフローチャートである。
【図１７】図１３のステップＳ２０４の詳細を表したフローチャートである。
【図１８】図１３のステップＳ２０４の詳細を表した別のフローチャートである。
【図１９】図１３のステップＳ２０５の詳細を表したフローチャートである。
【図２０】図１３のステップＳ２０５の詳細を表した別のフローチャートである。
【発明を実施するための形態】
【００１９】
はじめに本発明の一実施形態の概要について図面を参照して説明する。なお、この概要に付記した図面参照符号は、理解を助けるための一例として各要素に便宜上付記したものであり、本発明を図示の態様に限定することを意図するものではない。また、以降の説明で参照する図面等のブロック間の接続線は、双方向及び単方向の双方を含む。一方向矢印については、主たる信号（データ）の流れを模式的に示すものであり、双方向性を排除するものではない。
【００２０】
本発明は、その一実施形態において、図１に示すように、直接通信判定手段１１と、直接通信計画手段１２と、通信手段１３とを備える通信システムの形態を採ることができる。より具体的には、直接通信判定手段１１は、複数のノード（図１の計算ノード２）がそれぞれ担当するデータを用いて要素を計算する分散計算環境を構成する一のノードが計算した要素が、次に当該要素を必要とするノードへと直接通信できるか否かを判定する。前記直接通信の可否は、計算した要素を直接次計算ノードに送信すれば足りるか否かにて判定することができる。
【００２１】
直接通信計画手段１２は、前記直接通信判定手段の判定の結果をもとに、前記ノード間での要素の直接的な通信を計画する。直接的な通信の計画は、送信元の計算ノードと、送信先の計算ノードと、送信すべき要素と、当該通信が行われる計算ステップとの組み合わせにて記述することができる。また、この直接的な通信の計画において、該当ステップにおいて、当該要素を他の計算ノードに送信しないように計画の修正も行われる。
【００２２】
通信手段１３は、前記直接通信計画に従って、前記ノード間の通信を実現する。この前記ノード間の通信は、典型的には、通信システムが計算ノードに対し、要素の直接送信を指示することによって実現することができる。
【００２３】
以上のような通信システム１によれば、直接通信可能と判断された要素は、直接次計算ノードに送信されることになる。結果として、計算ノード間で、当該要素を集約したり、これを配布するために要する通信量を削減することができる。
【００２４】
［第１の実施形態］
続いて、本発明の第１の実施形態について図面を参照して詳細に説明する。はじめに、本発明の通信システムが利用される分散計算システムについて説明する。図２は、分散計算システムの構成例を示す図である。図２を参照すると、複数の計算ノード２と計算ノード２を接続するネットワークによって構成された分散計算システムが示されている。計算ノード２としては、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）、メモリ、補助記憶装置、ＩＯ（Ｉｎｐｕｔ／Ｏｕｔｐｕｔ）バスなどから構成される一般的な計算機を用いることができる。
【００２５】
計算ノード２は、それぞれが最適化要素を保持する。この最適化要素は、機械学習を例にとれば、予測モデルのパラメータに相当する。計算ノード２は、最適化要素を最適な値にするように、計算をくり返す。計算ノード２は、前記計算の都度、最適化要素を最適にするための更新差分を求め、それを最適化要素に足しこむ。
【００２６】
計算の繰り返し（ステップ）ごとに、計算ノード２は、計算した更新差分を他の計算ノードと共有する。ネットワークは、前記計算した更新差分を共有するために使用される。
【００２７】
前記複数の計算ノード２による更新差分の共有方法の一例を述べる。計算ノード２は、最適化要素の一部を集約担当部分（以後、集約担当部分を単に、担当部分とも呼ぶ）とする。担当部分は、範囲で指定するのが一般的である（その場合、担当部分を担当範囲と呼ぶ。）。それぞれの計算ノードの担当部分は、重複なく、漏れがない。計算ノードは、最適化要素に対する処理を行い、それぞれの担当部分を介して、計算結果の共有を行う。
【００２８】
本発明の第１の実施形態の通信システムは、上記分散計算システムが行った計算結果の共有を担う。通信システムは、分散計算システムのそれぞれのノードがそれぞれのステップで更新する要素を記憶している（図４参照）。また、それぞれの計算ノードの担当部分についても記憶している（図８参照）。
【００２９】
通信システムは、各ステップの計算が終了するごとに、それぞれの計算ノード２が更新した要素の差分を、前記要素を含む集約担当部分を有する計算ノード２に対して送信する。これをｒｅｄｕｃｅ通信と呼ぶ。その後、計算ノードは、担当部分の要素に対して、他の計算ノードから送信されたものを足し合わせる（集約）。計算ノード２は足し合わせたそれぞれの要素を、次のステップで必要な計算ノード、すなわち、次のステップで前記要素を更新する計算ノード２に対して送信する。これをｂｒｏａｄｃａｓｔ通信と呼ぶ。以上の通信操作はすべてブロッキング通信であると想定して、以下説明を行う。
【００３０】
なお、上記した通信システムは、典型的には、計算ノード２間のパラメータを授受するパラメータサーバとして実現できる。また、上記した通信システムは、物理的に計算ノードと独立している必要はなく、例えば、計算ノードと同じ計算機の上の別々のプログラムとして実装されていても良い。
【００３１】
図３は、本発明の第１の実施形態の通信システムの構成を示す図である。図３を参照すると、直接通信判定手段１１０と、直接通信計画手段１２０と、更新要素記憶部１３０と、通信情報記録部１４０と、通信手段１５０とを備えた構成が示されている。
【００３２】
まず、更新要素記憶部１３０と通信情報記録部１４０に保持されるデータの構造について説明する。
【００３３】
更新要素記憶部１３０には、図４に示すように、分散計算システムが計算を行うステップをＩＤとした、ステップ数分のテーブルが保持される。それぞれのテーブルは、ＩＤとした特定のステップにおいて、それぞれの計算ノードにおいて更新される要素（更新対象要素）が記録されている。図４の例では、計算ノード２はノード番号で指定されている。更新される要素も整数（インデックス）で指定されている。例えば、図４の例では、ステップｍにおいて、ノード番号＝１の計算ノードが４５、２８９、３５８という番号で特定される要素を更新することを示している。
【００３４】
通信情報記録部１４０には、ｒｅｄｕｃｅ通信要素テーブル、ｂｒｏａｄｃａｓｔ通信要素テーブル、直接通信要素テーブル、担当範囲テーブルとが保持される。これらは通信手段１５０が通信を行う際に参照される。以下、それぞれのテーブルについて説明する。
【００３５】
ｒｅｄｕｃｅ通信要素テーブルには、図５に示すように、各ステップにおいて、送信ノードから受信ノードに対してｒｅｄｕｃｅ通信される要素が記述される。ｒｅｄｕｃｅ通信要素テーブルは、計算ノード２が計算するステップ数分用意され、ｒｅｄｕｃｅ通信の際に参照される。なお、通信対象となる要素は、先の更新対象要素と同様に、インデックスで指定される。受信ノードが受信する要素は、当該受信ノードの担当範囲に含まれる要素が設定される。これによりそれぞれの受信ノードが担当部分の要素に、受信した要素の差分を足しこんで自身の担当範囲の要素の集約を実施する。
【００３６】
ｂｒｏａｄｃａｓｔ通信要素テーブルには、図６に示すように、各ステップにおいて、送信ノードから受信ノードに対してｂｒｏａｄｃａｓｔ通信される要素が記述される。ｂｒｏａｄｃａｓｔ通信要素テーブルは、計算ノード２が計算するステップ数分用意され、ｂｒｏａｄｃａｓｔ通信の際に参照される。なお、要素は、先のｒｅｄｕｃｅ通信要素テーブルと同様に、インデックスで指定される。ｂｒｏａｄｃａｓｔ通信要素テーブルにおいて、送信ノードが送信する要素は、当該送信ノードの担当範囲に含まれる要素が設定される。これによりそれぞれの送信ノードの担当範囲の要素が次のステップで当該要素を必要とする計算ノードに送信されることになる。
【００３７】
なお、以下の説明においては、ｒｅｄｕｃｅ通信要素テーブル及びｂｒｏａｄｃａｓｔ  通信要素テーブルは、あるステップにおける、ある要素を更新するノードが１つであるか否かを考慮せず、必要な計算ノードに要素が集約及び配布されるように設定されているものとして説明する。
【００３８】
直接通信要素テーブルには、図７に示すように、各ステップにおいて、送信ノードから受信ノードに対して、直接通信される要素が記憶される。直接通信要素テーブルも、計算ノード２が計算するステップ数分用意され、直接通信の際に参照される。ここで、直接通信とは、ｒｅｄｕｃｅ通信、ｂｒｏａｄｃａｓｔ通信という処理を経ずに、ある要素に対して、更新を行ったノードから次に必要とするノードへと直接的に通信する通信の方法である。通信システムの動作開始前には、直接通信要素テーブルの通信インデックスフィールドは、すべて空（ｎｕｌｌ）となっている。
【００３９】
図８は、担当範囲テーブルの一例を示す図である。図８の例では、各ノードの担当範囲が担当範囲開始インデクックスにより記述されている。この場合、あるノードの担当範囲は、担当範囲開始インデクックスから、次の番号のノードの担当範囲開始インデックスまでとなる。
【００４０】
続いて、上記更新要素記憶部１３０と、通信情報記録部１４０に格納される情報を用いた直接通信判定手段１１０、直接通信計画手段１２０、通信手段１５０の動作について説明する。
【００４１】
直接通信判定手段１１０は、分散計算システムを構成する各ノードにおいて行われる計算ステップで、所定の要素を、ｒｅｄｕｃｅ通信、ｂｒｏａｄｃａｓｔ通信によらず、直接通信に変更可能であるかどうかを判定する。本実施形態では、ステップｍにおいて要素ｘを更新する計算ノードがただ一つである場合に、ステップｍにおいて、要素ｘが直接通信可能であるということを判定することとしている。
【００４２】
直接通信計画手段１２０は、直接通信判定手段１１０が直接通信を行うことが可能であると判定した要素に関して、通信要素テーブルの内容を変更する。ステップｍにおいて直接通信が可能と判定された要素をｘとすると、直接通信計画手段１２０は、要素ｘに関する直近のｒｅｄｕｃｅ通信とｂｒｏａｄｃａｓｔ通信を削除する。通信を削除するとは、当該通信を行わないように、ｒｅｄｕｃｅ通信要素テーブル及びｂｒｏａｄｃａｓｔ通信要素テーブルの通信インデックスフィールドから、該当する要素インデックスを削除する、との意味である。そして、直接通信計画手段１２０は、要素ｘが更新された直近のステップにおいて、要素ｘの直接通信を追加する。ここで、通信を追加するとは、通信を行うように直接通信要素テーブルの通信インデックスフィールドに該当する要素のインデックスを追加することである。
【００４３】
通信手段１５０は、通信情報記録部１４０に記憶されている通信要素テーブルの内容に基づいて、計算ノード２間での要素の通信を制御する。
【００４４】
なお、図１、３に示した通信システムの各部（処理手段）は、通信システム（計算ノードであってもよい）を構成するコンピュータに、そのハードウェアを用いて、上記した各処理を実行させるコンピュータプログラムにより実現することもできる。
【００４５】
続いて、本実施形態の動作について図面を参照して詳細に説明する。図９は、直接通信計画の作成指示を受けた場合の通信システムの動作を表したフローチャートである。図９を参照すると、まず、通信システムの直接通信判定手段１１０が、ステップｍで要素ｘを更新する計算ノードがただ一つであるかどうかを判定する（ステップＳ１０１〜Ｓ１０２）。例えば、更新要素記憶部１３０のステップｍのテーブルを走査して、要素ｘを更新する計算ノードが１つであれば、当該要素ｘは直接通信に変更可能と判定される（ステップＳ１０２の判定Ｙｅｓ）。逆に、要素ｘを更新する計算ノードが０又は２以上ある場合、直接通信に変更不可と判定される（ステップＳ１０２の判定Ｎｏ）。
【００４６】
ステップＳ１０２で判定Ｙｅｓの場合、直接通信判定手段１１０は、直接通信計画手段１２０に、直接通信に変更可能と判定したステップｍの要素ｘの情報を通知する。直接通信計画手段１２０は、ｒｅｄｕｃｅ通信要素テーブル及びｂｒｏａｄｃａｓｔ通信要素テーブルの通信インデックスフィールドから、該当する要素インデックスを削除する（ステップＳ１０３）。例えば、図５のｒｅｄｕｃｅ通信要素テーブルから要素ｘ（例えば、図５の＃４０１２の要素）を削除することで、当該要素がｒｅｄｕｃｅ通信の対象から外れることになる。同様に、図６のｂｒｏａｄｃａｓｔ通信要素テーブルから要素ｘを削除することで、当該要素がｂｒｏａｄｃａｓｔ通信の対象から外れることになる。
【００４７】
次に、直接通信計画手段１２０は、ステップｍの直接通信要素テーブルに、該当する要素インデックスを追加する（ステップＳ１０４）。直接通信要素テーブルへの追加箇所は、ｒｅｄｕｃｅ通信要素テーブル又はｂｒｏａｄｃａｓｔ通信要素テーブルの削除したエントリの送信ノードを送信ノードとし、ｒｅｄｕｃｅ通信要素テーブル又はｂｒｏａｄｃａｓｔ通信要素テーブルの削除したエントリの受信ノードを受信ノードとする位置である。例えば、ステップｍ１で更新される要素＃２４５を直接通信可能と判定した場合、図５のステップｍ１のｒｅｄｕｃｅ通信要素テーブルから要素＃２４５を削除し、図７のステップｍ１の直接通信要素テーブルの送信ノード＝２、受信ノード＝１のフィールドに＃２４５を追加する処理が行われることになる。
【００４８】
直接通信判定手段１１０と直接通信計画手段１２０は、以上の処理をすべてのステップのすべての要素について実施する。即ち、ステップｍ＝０からスタートし、要素ｘを０から１つずつ増加して判定を繰り返し、あるステップの要素についての判定が完了すると、ステップｍを１つ増加して、再びすべての要素ｘについて直接通信可能かどうかを判定する。最終的に、すべてのステップのすべての要素について判定が完了すると、図９のループから抜けて直接通信計画の作成処理が完了する。
【００４９】
以上のように、本実施形態によれば、分散計算システムにおいて、無駄が発生している通信をすべて抽出し、直接通信に切り替えることが可能となる。
【００５０】
［第２の実施形態］
続いて、近傍更新ステップという概念を導入して、より効率のよい直接通信計画を作成可能とした第２の実施形態について図面を参照して詳細に説明する。以下、第１の実施形態との相違点を中心に説明する。
【００５１】
図１０は、本発明の第２の実施形態の通信システムの構成を示す図である。図３に示した第１の実施形態の通信システムとの相違点は、直接通信判定手段２１０及び直接通信計画手段２２０の機能に変更が加えられている点である。以下では、前記２つの構成要素について詳細に説明する。
【００５２】
図１１は、本実施形態の直接通信判定手段２１０の詳細構成を示す図である。図１１に示したとおり、直接通信判定手段２１０は、更新ノード計数手段２１１と、単一ノード更新判定手段２１２と、を備える。
【００５３】
更新ノード計数手段２１１は、所定のステップにおける所定の要素の更新回数を数える。具体的には、更新ノード計数手段２１１は、ノード更新回数ステップと要素のインデックスが入力されると、更新ノード計数手段２１１は、更新要素記憶部１３０から、指定されたステップ数に対応するテーブルを参照して、前記ステップにおいて前記要素が更新される計算ノードの数を返す。
【００５４】
単一ノード更新判定手段２１２は、所定の要素が所定のステップにおいて計算されたノードの数が１であるか否かを判定する。具体的には、単一ノード更新判定手段２１２は、更新ノード計数手段２１１の出力を入力とし、判定を行って、ノードの数が１と判定した計算ノードを出力する。
【００５５】
図１２は、本実施形態の直接通信計画手段２２０の詳細構成を示す図である。図１２に示したとおり、直接通信計画手段２２０は、近傍更新ステップ特定手段２２１と、ｒｅｄｕｃｅ通信削除手段２２２と、ｂｒｏａｄｃａｓｔ通信削除手段２２３と、直接通信追加手段２２４と、を備える。
【００５６】
本実施形態の直接通信計画手段２２０は、前方向の動作と後方向の動作があり、動作するときは両者の処理を行う。前方向の場合は、直接通信可能と判定された要素のステップよりも、以前の通信情報を修正する。後方向の場合は、直接通信可能と判定された要素のステップよりも、以後の通信情報を修正する。
【００５７】
近傍更新ステップ特定手段２２１は、直接通信が可能と判定された要素ｘ、ステップｍとから、要素ｘが更新されたステップのうち、ステップｍにもっとも近いものを特定する。より具体的には、近傍更新ステップ特定手段２２１には、要素、ステップ、方向（前方向または後方向）とが入力される。前方向が指定されたとき、近傍更新ステップ特定手段２２１は、指定したステップ以前で、指定した要素が更新される、ステップｍからもっとも近いステップを、後方向が指定されたときは、指定したステップ以後で、指定した要素が更新される、ステップｍからもっとも近いステップを求める。
【００５８】
近傍更新ステップ特定手段２２１のはたらきを、前方向の場合についてより詳しく説明する。指定されたステップがｍ、要素がｘであったとする。近傍更新ステップ特定手段２２１は、ステップｍから前方向に順に要素ｘが更新されたかどうかを確認する（確認しているステップを「確認ステップ」と呼ぶ）。確認ステップにおいて、要素ｘが更新されていないとき、近傍更新ステップ特定手段２２１は、前記確認ステップより１つ前のステップを確認する。確認ステップにおいて、要素ｘがいずれかのノードで更新されていたとき、近傍更新ステップ特定手段２２１は、当該確認ステップを近傍更新ステップ（以下、ステップｍ０とも記す）として、出力する。
【００５９】
ｒｅｄｕｃｅ通信削除手段２２２は、直接通信が可能と判定された要素について、直接通信に置き換えできるｒｅｄｕｃｅ通信を削除する。ｒｅｄｕｃｅ通信削除手段２２２には、直接通信が可能と判定された要素ｘ、ステップｍ、ステップｍで要素ｘが更新された計算ノードａ、および、近傍更新ステップ特定手段にて特定された近傍更新ステップｍ０が入力される。ｒｅｄｕｃｅ通信削除手段２２２は、ステップｍ０がｍの前方向のとき（これはｍ０＜ｍと同値）、ステップｍ０で要素ｘを更新したノードを特定する（Ａ０とする）。ｒｅｄｕｃｅ通信削除手段２２２は、ステップｍ０において集合Ａ０に属する計算ノードらを送信元とする要素ｘのｒｅｄｕｃｅ通信を削除する。
【００６０】
一方、ステップｍ０がｍの後方向のとき（これはｍ０＞ｍと同値）、ｒｅｄｕｃｅ通信削除手段２２２は、ステップｍにおいて計算ノードａを送信元とする、要素ｘのｒｅｄｕｃｅ通信を削除する。なお、上記の説明において、所定の要素のｒｅｄｕｃｅ通信を削除するとは、当該通信を行わないように、通信情報記録部１４０の該当ステップのｒｅｄｕｃｅ通信要素テーブルの通信インデックスフィールドから、該当する要素インデックスを削除する、との意味である。
【００６１】
ｂｒｏａｄｃａｓｔ通信削除手段２２３は、直接通信が可能と判定された要素について、直接通信に置き換えできるｂｒｏａｄｃａｓｔ通信を削除する。ｂｒｏａｄｃａｓｔ通信削除手段２２３には、直接通信が可能と判定された要素ｘ、ステップｍ、ステップｍで要素ｘが更新された計算ノードａ、および、近傍更新ステップ特定手段２２１の出力であるステップｍ０が入力される。ｂｒｏａｄｃａｓｔ通信削除手段２２３は、ステップｍ０がｍの前方向のとき（これはｍ０＜ｍと同値）、ステップ（ｍ−１）において、要素ｘを担当部分に含む計算ノード（ｂとする）を送信元とする、要素ｘのｂｒｏａｄｃａｓｔ通信を削除する。
【００６２】
ステップｍ０がｍの後方向のとき（これはｍ０＞ｍと同値）、ｂｒｏａｄｃａｓｔ通信削除手段２２３は、ステップ（ｍ０−１）で計算ノードｂを送信元とする、要素ｘのｂｒｏａｄｃａｓｔ通信を削除する。なお、上記の説明において、所定の要素のｂｒｏａｄｃａｓｔ通信を削除するとは、当該通信を行わないように、通信情報記録部１４０の該当ステップのｂｒｏａｄｃａｓｔ通信要素テーブルの通信インデックスフィールドから、該当する要素インデックスを削除する、との意味である。
【００６３】
直接通信追加手段２２４は、直接通信が可能と判定された要素について、直接通信を追加する。直接通信追加手段２２４には、直接通信が可能と判定された要素ｘ、ステップｍ、ステップｍで要素ｘが更新された計算ノードａ、および、近傍更新ステップ特定手段の出力であるステップｍ０が入力される。直接通信追加手段２２４は、ステップｍ０がｍの前方向のとき（これはｍ０＜ｍと同値）、ステップｍ０において、要素ｘを更新する計算ノード（一般に複数）を特定する。ステップｍ０において、直接通信追加手段２２４は、前記計算ノードを送信元、計算ノードａを送信先とする、要素ｘの直接通信を追加する。
【００６４】
一方、ステップｍ０がｍの後方向のとき（これはｍ０＞ｍと同値）、直接通信追加手段２２４は、ステップｍ０で要素ｘを更新する計算ノード（一般に複数）を特定する。その上で、直接通信追加手段２２４は、ステップｍで、計算ノードａを送信元、前記計算ノードを送信先とする、要素ｘの直接通信を追加する。
【００６５】
続いて、本実施形態の通信システムの動作について図面を参照して詳細に説明する。図１３は、本発明の第２の実施形態の通信システムの動作を表したフローチャートである。基本的な動作は、第１の実施形態と同様であり、直接通信判定手段２１０の動作（ステップＳ２０１）、直接通信計画手段２２０の近傍更新ステップ特定手段の動作（ステップＳ２０３）、ｒｅｄｕｃｅ通信削除手段およびｂｒｏａｄｃａｓｔ通信削除手段の動作（ステップＳ２０４）、直接通信追加手段の動作（ステップＳ２０５）が行われる。第１の実施形態と同様に、通信システムは、ステップ数をｍ、要素をｘ、として、ｍ×ｘ回の処理を繰り返し、直接通信可能と判定された要素を直接通信に切り替える処理を行う。以下、１つのループにおける動作を詳細に説明する。
【００６６】
図１４は、直接通信判定手段２１０の動作を示したフローチャートである。図１４を参照すると、更新ノード計数手段２１１は、ステップｍにおいて要素ｘが更新される計算ノードを計数する（ステップＳ２１０１）。単一ノード更新判定手段２１２は、更新した計算ノードの数が１であるかそれ以外かを判定する（ステップＳ２１０２）。更新した計算ノードが１であると判定したとき、単一ノード更新判定手段２１２は、その更新した計算ノードを出力する。
【００６７】
以下は、図１３のステップＳ２０２でＹｅｓとされた場合の説明である。以下の説明において、直接通信判定手段２１０で出力された計算ノードをａとする。図１５及び図１６は、直接通信計画手段２２０の近傍更新ステップ特定手段２２１の動作を表したフローチャートであり、図１５は、前方向の近傍更新ステップ探索処理を示し、図１６は、後方向の近傍更新ステップ探索処理を示している。
【００６８】
まず、図１５を参照して、近傍更新ステップ特定手段２２１による前方向の探索処理を説明する。まず、近傍更新ステップ特定手段２２１は、確認ステップｍ０にｍ−１を代入する（ステップＳ２３１１）。次に、近傍更新ステップ特定手段２２１は、ステップｍ０で要素ｘを更新した計算ノードがあるかどうかを判定する（ステップＳ２３１２）。  前記判定の結果、ステップｍ０で要素ｘを更新した計算ノードが存在する場合（ステップＳ２３１２でＹｅｓ）、近傍更新ステップ特定手段２２１は、ｍ０を出力して動作を終了する（ステップＳ２３１３）。
【００６９】
一方、ステップｍ０で要素ｘを更新した計算ノードが存在しない場合（ステップＳ２３１２でＮｏ）、近傍更新ステップ特定手段２２１は、ステップｍ０が最初の要素、つまりステップｍ０が最初のステップであるかどうかを判定する（ステップＳ２３１４）。ｍ０が最初のステップである場合（ステップＳ２３１４でＹｅｓ）、前方向に要素ｘが更新されたステップがないことになるので、近傍更新ステップ特定手段２２１は、以降の処理も含め直接通信計画手段２２０の前方向の探索動作を終了する（ステップＳ２３１５）。一方、ステップｍ０が最初のステップでない場合（ステップＳ２３１４でＮｏ）、近傍更新ステップ特定手段２２１は、ｍ０の値をひとつ減らす（ステップＳ２３１６）。そして、ステップＳ２３１２の判定に戻る。以上のようにして、近傍更新ステップ特定手段２２１は、要素ｘが更新されたステップｍより前に要素ｘが更新されたステップｍ０を探索していく。以上が、近傍更新ステップ特定手段２２１の前方向の探索動作である。
【００７０】
近傍更新ステップ特定手段２２１の後方向の動作は、ほぼ前方向との処理と同様である。具体的には、近傍更新ステップ特定手段２２１は、要素ｘを更新したステップｍ０が見つかるまで、ｍ０を１つずつ増やしながら、要素ｘが更新されたステップｍより後に要素ｘが更新されたステップｍ０を探索していく。その過程で、ｍ０が最後のステップになってしまった場合は、以降の処理も含め後方向の探索動作を終了する（ステップＳ２３２５）。以上が、近傍更新ステップ特定手段２２１の後方向の探索動作である。
【００７１】
続いて、図１３のステップＳ２０４のｒｅｄｕｃｅ通信削除手段２２２及びｂｒｏａｄｃａｓｔ通信削除手段２２３の動作について説明する。図１７及び図１８は、直接通信計画手段２２０のｒｅｄｕｃｅ通信削除手段２２２及びｂｒｏａｄｃａｓｔ通信削除手段２２３の動作を表したフローチャートであり、図１７は、前方向の近傍更新ステップｍ０が見つかった場合の通信削除処理を示し、図１８は、後方向の近傍更新ステップｍ０が見つかった場合の通信削除処理を示している。
【００７２】
まず、図１７を参照して、ｒｅｄｕｃｅ通信削除手段２２２及びｂｒｏａｄｃａｓｔ通信削除手段２２３による前方向の通信削除処理を説明する。まず、ｒｅｄｕｃｅ通信削除手段２２２及びｂｒｏａｄｃａｓｔ通信削除手段２２３は、ステップｍ０において、要素ｘを更新した計算ノード（一般に複数）を特定する（ステップＳ２４１１）。ｒｅｄｕｃｅ通信削除手段２２２は、ステップｍ０で前記ノードを送信元とする要素ｘのｒｅｄｕｃｅ通信を削除する（ステップＳ２４１２）。次に、ｂｒｏａｄｃａｓｔ通信削除手段２２３は、ステップｍ−１で要素ｘのｂｒｏａｄｃａｓｔ通信を削除する（ステップ２４１３）。
【００７３】
続いて、図１８を参照して、ｒｅｄｕｃｅ通信削除手段２２２及びｂｒｏａｄｃａｓｔ通信削除手段２２３による後方向の通信削除処理を説明する。まず、ｒｅｄｕｃｅ通信削除手段２２２は、ステップｍにおける、計算ノードａを送信元とする、要素ｘのｒｅｄｕｃｅ通信を削除する（ステップＳ２４２１）。次に、ｂｒｏａｄｃａｓｔ通信削除手段２２３は、ステップｍ０−１における、要素ｘのｂｒｏａｄｃａｓｔ通信を削除する（ステップＳ２４２２）。
【００７４】
続いて、図１３のステップＳ２０５の直接通信追加手段２２４の動作について説明する。図１９及び図２０は、直接通信計画手段２２０の直接通信追加手段２２４の動作を表したフローチャートであり、図１９は、前方向の近傍更新ステップｍ０が見つかった場合の通信追加処理を示し、図２０は、後方向の近傍更新ステップｍ０が見つかった場合の通信追加処理を示している。
【００７５】
まず、図１９を参照して、直接通信追加手段２２４による前方向の通信追加処理を説明する。まず、直接通信追加手段２２４は、ステップｍ０において、要素ｘを更新する計算ノードを特定する（ステップＳ２５１１）。次に、直接通信追加手段２２４は、ステップｍ０において、先に特定したノードを送信元、計算ノードａを送信先とする要素ｘの直接通信を追加する（ステップＳ２５１２）。
【００７６】
続いて、図２０を参照して、直接通信追加手段２２４による後方向の通信追加処理を説明する。まず、直接通信追加手段２２４は、ステップｍ０において、要素ｘを更新する計算ノードを特定する（ステップＳ２５２１）。次に、直接通信追加手段２２４は、ステップｍ０において、先に特定した計算ノードを送信元、計算ノードａを送信先とする要素ｘの直接通信を追加する（ステップＳ２５２２）。
【００７７】
以上のように、本実施形態によれば、分散計算システムにおいて、直接通信が可能なステップｍと要素ｘのみならず、その要素ｘを更新した前後のステップを探しだし、その区間も直接通信に切り替えることが可能となっている。このため、第１の実施形態よりもいっそう通信を効率化することが可能となっている。
【００７８】
以上、本発明の各実施形態を説明したが、本発明は、上記した実施形態に限定されるものではなく、本発明の基本的技術的思想を逸脱しない範囲で、更なる変形・置換・調整を加えることができる。例えば、各図面に示したネットワーク構成、各要素の構成、メッセージの表現形態は、本発明の理解を助けるための一例であり、これらの図面に示した構成に限定されるものではない。
【００７９】
最後に、本発明の好ましい形態を要約する。
［第１の形態］
（上記第１の視点による通信システム参照）
［第２の形態］
上記した通信システムは、さらに、予め作成された前記ノード間の通信計画及び前記直接通信計画手段により作成される直接的な通信計画を保持する通信情報記録部を備え、前記通信手段は、前記通信情報記録部に保持されている通信計画及び直接的な通信計画に基づいて、前記ノード間の通信を実現する構成を採ることができる。
［第３の形態］
上記した通信システムは、
さらに、それぞれのノードにおいて更新される要素を記憶する更新要素記憶部を備え、
前記直接通信判定手段は、前記更新要素記憶部を参照して、ある計算ステップにおいて、ある要素を計算するノードが１つである場合、直接通信可能と判定する構成を採ることができる。
［第４の形態］
上記した通信システムの直接通信計画手段は、
前記直接通信判定手段により、直接通信可能と判定されたステップと要素の組に対して、前記要素が更新された前記ステップの近傍のステップを特定し、前記通信計画から、前記近傍のステップ及び前記直接通信可能と判定されたステップとの前記要素に係る間接的な通信を削除し、前記通信計画に、前記要素に係る直接的な通信を追加する構成を採ることができる。
［第５の形態］
上記した通信システムの前記通信情報記録部は、前記計算した要素を所定のノードに集約する通信にかかる情報を記録するｒｅｄｕｃｅ通信要素テーブルと、前記集約した要素を次のステップで必要となるノードに拡散するｂｒｏａｄｃａｓｔ通信要素テーブルと、ノード間での要素の直接的な通信に係る情報を記録する直接通信要素テーブルと、を備え、前記通信手段は、前記テーブルに記録された情報に従って、前記ノード間の通信を実現する構成を採ることができる。
［第６の形態］
上記した通信システムの前記要素は、機械学習に用いるモデルのパラメータを修正するための差分値とすることができる。
［第７の形態］
（上記第２の視点による分散計算システム参照）
［第８の形態］
（上記第３の視点によるノード参照）
［第９の形態］
（上記第４の視点によるノード間の情報共有方法参照）
［第１０の形態］
（上記第５の視点によるコンピュータプログラム参照）
なお、上記第７〜第１０の形態は、第１の形態と同様に、第２〜第６の形態に展開することが可能である。
【００８０】
なお、上記の特許文献および非特許文献の各開示を、本書に引用をもって繰り込むものとする。本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態ないし実施例の変更・調整が可能である。また、本発明の開示の枠内において種々の開示要素（各請求項の各要素、各実施形態ないし実施例の各要素、各図面の各要素等を含む）の多様な組み合わせ、ないし選択が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。特に、本書に記載した数値範囲については、当該範囲内に含まれる任意の数値ないし小範囲が、別段の記載のない場合でも具体的に記載されているものと解釈されるべきである。
【符号の説明】
【００８１】
１、１００、２００  通信システム
２  計算ノード
１１、１１０、２１０  直接通信判定手段
１２、１２０、２２０  直接通信計画手段
１３、１５０  通信手段
１３０  更新要素記憶部
１４０  通信情報記録部
２１１  更新ノード計数手段
２１２  単一ノード更新判定手段
２２１  近傍更新ステップ特定手段
２２２  ｒｅｄｕｃｅ通信削除手段
２２３  ｂｒｏａｄｃａｓｔ通信削除手段
２２４  直接通信追加手段
【図１】
2018120470.tif 000003
【図２】
2018120470.tif 000004
【図３】
2018120470.tif 000005
【図４】
2018120470.tif 000006
【図５】
2018120470.tif 000007
【図６】
2018120470.tif 000008
【図７】
2018120470.tif 000009
【図８】
2018120470.tif 000010
【図９】
2018120470.tif 000011
【図１０】
2018120470.tif 000012
【図１１】
2018120470.tif 000013
【図１２】
2018120470.tif 000014
【図１３】
2018120470.tif 000015
【図１４】
2018120470.tif 000016
【図１５】
2018120470.tif 000017
【図１６】
2018120470.tif 000018
【図１７】
2018120470.tif 000019
【図１８】
2018120470.tif 000020
【図１９】
2018120470.tif 000021
【図２０】
2018120470.tif 000022