図面 (/)

技術 通信制御プログラム、通信制御方法および情報処理装置

出願人 富士通株式会社
発明者 三輪真弘
出願日 2019年4月16日 (1年10ヶ月経過) 出願番号 2019-077727
公開日 2020年10月29日 (3ヶ月経過) 公開番号 2020-178181
状態 未査定
技術分野 広域データ交換 計算機・データ通信
主要キーワード データ部分集合 メッシュシステム 上位スイッチ データ送信経路 プロセス配置 手順テーブル フェーズ内 単一グループ
関連する未来課題
重要な関連分野

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

図面 (20)

課題

ノード間の通信競合を抑制する。

解決手段

複数のノードと複数の第1の中継装置と複数の第2の中継装置とを含み、複数の第1の中継装置それぞれが2以上の第2の中継装置と接続されたシステムにおいて、接続された第2の中継装置が同一でない異なる第1の中継装置に接続された異なるノードが、異なるグループ分類されるように、複数のノードを複数のグループに分類する。複数のグループそれぞれから代表ノードを選択する。複数の代表ノードの間で実行される第1のノード間通信通信順序を、第1のツリーに従ってデータを転送し、これと並列に第2のツリーに従って異なるデータを転送するように決定する。複数のグループそれぞれについて実行される第2のノード間通信の通信順序を、第3のツリーに従ってデータを転送し、これと並列に第4のツリーに従って異なるデータを転送するように決定する。

概要

背景

複数の情報処理装置ノードとして含む並列処理システムがある。並列処理システムは、同一のジョブに属する複数のプロセスを複数のノードに割り振り、それら複数のプロセスを複数のノードにより並列に実行する。ジョブの中ではノード間で通信を行うことがある。ノード間で通信を行うユーザプログラムは、MPI(Message Passing Interface)ライブラリなどの通信ライブラリを利用して実装されることがある。ノード間の通信としては、ジョブに使用される複数のノードが一斉にデータ送信に参加するコレクティブ通信(集合通信または集団通信と言うこともある)がある。コレクティブ通信には、複数の他のノードが分散してもつデータを1つのノードに転送するReduce通信や、1つのノードから複数の他のノードに同一データコピーするブロードキャスト通信が含まれる。

ところで、並列処理システムが多数のノードを含む場合、単一のスイッチなど単一の中継装置に全てのノードを直接接続することは難しい。そのため、複数のノードおよび複数の中継装置の接続形態を示すネットワークトポロジ(単にトポロジと言うことがある)が問題となる。1つのノードと別の1つのノードとの間の通信が、2以上の中継装置を経由することがある。並列処理システムのトポロジの選択では、ノード間の通信経路冗長性や、中継装置の個数などのコストが考慮されることがある。

並列処理システムの1つとして、多層フルメッシュトポロジをもつ多層フルメッシュシステムが提案されている。提案の多層フルメッシュシステムは、複数のノードと複数のLeaf(葉)スイッチと複数のSpine(背骨)スイッチを含み、複数の層(レイヤ)を形成する。各ノードは何れか1つのLeafスイッチに接続され、各Leafスイッチは何れか1つの層に属し、各Spineスイッチは複数の層を貫通する。

層内では、2以上のLeafスイッチがフルメッシュトポロジにより接続されている。Leafスイッチのペア毎に、他のLeafスイッチを経由しない通信経路が存在する。ただし、Leafスイッチのペア毎に、その間に1つのSpineスイッチが配置されている。よって、層内では、1つのLeafスイッチは別の1つのLeafスイッチと、1つのSpineスイッチを経由して通信することになる。このSpineスイッチは複数の層を接続している。よって、当該1つのLeafスイッチは別の層に属する1つのLeafスイッチとも、1つのSpineスイッチを経由して通信できる。

なお、ツリー状に接続された複数のノードを含む並列コンピュータが提案されている。提案の並列コンピュータは、ツリーのルートに位置する1つのノードから末端に位置する複数のノードに向かってデータをコピーすることで、ブロードキャスト通信を実現する。また、並列コンピュータは、ツリーの末端に位置する複数のノードからルートに位置する1つのノードに向かってデータを転送することで、Reduce通信を実現する。

概要

ノード間の通信の競合を抑制する。複数のノードと複数の第1の中継装置と複数の第2の中継装置とを含み、複数の第1の中継装置それぞれが2以上の第2の中継装置と接続されたシステムにおいて、接続された第2の中継装置が同一でない異なる第1の中継装置に接続された異なるノードが、異なるグループ分類されるように、複数のノードを複数のグループに分類する。複数のグループそれぞれから代表ノードを選択する。複数の代表ノードの間で実行される第1のノード間通信通信順序を、第1のツリーに従ってデータを転送し、これと並列に第2のツリーに従って異なるデータを転送するように決定する。複数のグループそれぞれについて実行される第2のノード間通信の通信順序を、第3のツリーに従ってデータを転送し、これと並列に第4のツリーに従って異なるデータを転送するように決定する。

目的

本発明は、ノード間の通信の競合を抑制できる通信制御プログラム通信制御方法および情報処理装置を提供する

効果

実績

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

この技術が所属する分野

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

請求項1

コンピュータに、複数のノードと複数の第1の中継装置と複数の第2の中継装置とを含み、前記複数のノードそれぞれが前記複数の第1の中継装置の1つと接続され、前記複数の第1の中継装置それぞれが前記複数の第2の中継装置の一部である2以上の第2の中継装置と接続されたシステムにおいて、接続された前記2以上の第2の中継装置が同一でない異なる第1の中継装置に接続された異なるノードが、異なるグループ分類されるように、前記システムに含まれる前記複数のノードを複数のグループに分類し、前記複数のグループそれぞれから代表ノードを選択し、前記複数のグループに対応する複数の代表ノードの間で実行される第1のノード間通信通信順序を、1つの代表ノードを基点として、前記1つの代表ノード以外の他の代表ノードが第1のツリーに従ってデータを転送する第1の転送処理を行い、前記第1の転送処理と並列に、前記他の代表ノードが第2のツリーに従って前記第1の転送処理と異なるデータを転送する第2の転送処理を行うように決定し、前記複数のグループそれぞれについて、前記第1のノード間通信の前または後に当該グループに含まれる2以上のノードの間で実行される第2のノード間通信の通信順序を、当該グループの代表ノードを基点として、当該代表ノード以外の他のノードが第3のツリーに従ってデータを転送する第3の転送処理を行い、前記第3の転送処理と並列に、前記他のノードが第4のツリーに従って前記第3の転送処理と異なるデータを転送する第4の転送処理を行うように決定する、処理を実行させる通信制御プログラム

請求項2

前記複数のノードの分類では、接続された前記2以上の第2の中継装置が同一である異なる第1の中継装置に接続された異なるノードを、同じグループに分類する、請求項1記載の通信制御プログラム。

請求項3

前記複数のグループそれぞれの代表ノードは、当該グループに含まれる前記2以上のノードのうち、配置されたプロセスの識別番号が最小のノードである、請求項1記載の通信制御プログラム。

請求項4

前記第1のノード間通信は、前記第2のノード間通信の後に実行され、前記第3の転送処理では、前記他のノードに記憶されたデータの一部を当該グループの代表ノードに転送し、前記第4の転送処理では、前記他のノードに記憶されたデータの他の一部を当該グループの代表ノードに転送し、前記第1の転送処理では、前記他の代表ノードに集約されたデータの一部を前記1つの代表ノードに転送し、前記第2の転送処理では、前記他の代表ノードに集約されたデータの他の一部を前記1つの代表ノードに転送する、請求項1記載の通信制御プログラム。

請求項5

前記第1のノード間通信の通信順序の決定では、前記第1のツリーの中で前記他の代表ノードの位置を巡回シフトすることで前記第2のツリーを生成し、前記第2のノード間通信の通信順序の決定では、前記第3のツリーの中で前記他のノードの位置を巡回シフトすることで前記第4のツリーを生成する、請求項1記載の通信制御プログラム。

請求項6

コンピュータが、複数のノードと複数の第1の中継装置と複数の第2の中継装置とを含み、前記複数のノードそれぞれが前記複数の第1の中継装置の1つと接続され、前記複数の第1の中継装置それぞれが前記複数の第2の中継装置の一部である2以上の第2の中継装置と接続されたシステムにおいて、接続された前記2以上の第2の中継装置が同一でない異なる第1の中継装置に接続された異なるノードが、異なるグループに分類されるように、前記システムに含まれる前記複数のノードを複数のグループに分類し、前記複数のグループそれぞれから代表ノードを選択し、前記複数のグループに対応する複数の代表ノードの間で実行される第1のノード間通信の通信順序を、1つの代表ノードを基点として、前記1つの代表ノード以外の他の代表ノードが第1のツリーに従ってデータを転送する第1の転送処理を行い、前記第1の転送処理と並列に、前記他の代表ノードが第2のツリーに従って前記第1の転送処理と異なるデータを転送する第2の転送処理を行うように決定し、前記複数のグループそれぞれについて、前記第1のノード間通信の前または後に当該グループに含まれる2以上のノードの間で実行される第2のノード間通信の通信順序を、当該グループの代表ノードを基点として、当該代表ノード以外の他のノードが第3のツリーに従ってデータを転送する第3の転送処理を行い、前記第3の転送処理と並列に、前記他のノードが第4のツリーに従って前記第3の転送処理と異なるデータを転送する第4の転送処理を行うように決定する、通信制御方法

請求項7

複数のノードと複数の第1の中継装置と複数の第2の中継装置とを含み、前記複数のノードそれぞれが前記複数の第1の中継装置の1つと接続され、前記複数の第1の中継装置それぞれが前記複数の第2の中継装置の一部である2以上の第2の中継装置と接続されたシステムにおいて、前記複数のノードの間のノード間通信の通信順序を示す通信制御データを記憶する記憶部と、前記ノード間通信の通信順序を決定する処理部と、を有し、前記処理部は、接続された前記2以上の第2の中継装置が同一でない異なる第1の中継装置に接続された異なるノードが、異なるグループに分類されるように、前記システムに含まれる前記複数のノードを複数のグループに分類し、前記複数のグループそれぞれから代表ノードを選択し、前記複数のグループに対応する複数の代表ノードの間で実行される第1のノード間通信の通信順序を、1つの代表ノードを基点として、前記1つの代表ノード以外の他の代表ノードが第1のツリーに従ってデータを転送する第1の転送処理を行い、前記第1の転送処理と並列に、前記他の代表ノードが第2のツリーに従って前記第1の転送処理と異なるデータを転送する第2の転送処理を行うように決定し、前記複数のグループそれぞれについて、前記第1のノード間通信の前または後に当該グループに含まれる2以上のノードの間で実行される第2のノード間通信の通信順序を、当該グループの代表ノードを基点として、当該代表ノード以外の他のノードが第3のツリーに従ってデータを転送する第3の転送処理を行い、前記第3の転送処理と並列に、前記他のノードが第4のツリーに従って前記第3の転送処理と異なるデータを転送する第4の転送処理を行うように決定する、情報処理装置

技術分野

0001

本発明は通信制御プログラム通信制御方法および情報処理装置に関する。

背景技術

0002

複数の情報処理装置をノードとして含む並列処理システムがある。並列処理システムは、同一のジョブに属する複数のプロセスを複数のノードに割り振り、それら複数のプロセスを複数のノードにより並列に実行する。ジョブの中ではノード間で通信を行うことがある。ノード間で通信を行うユーザプログラムは、MPI(Message Passing Interface)ライブラリなどの通信ライブラリを利用して実装されることがある。ノード間の通信としては、ジョブに使用される複数のノードが一斉にデータ送信に参加するコレクティブ通信(集合通信または集団通信と言うこともある)がある。コレクティブ通信には、複数の他のノードが分散してもつデータを1つのノードに転送するReduce通信や、1つのノードから複数の他のノードに同一データコピーするブロードキャスト通信が含まれる。

0003

ところで、並列処理システムが多数のノードを含む場合、単一のスイッチなど単一の中継装置に全てのノードを直接接続することは難しい。そのため、複数のノードおよび複数の中継装置の接続形態を示すネットワークトポロジ(単にトポロジと言うことがある)が問題となる。1つのノードと別の1つのノードとの間の通信が、2以上の中継装置を経由することがある。並列処理システムのトポロジの選択では、ノード間の通信経路冗長性や、中継装置の個数などのコストが考慮されることがある。

0004

並列処理システムの1つとして、多層フルメッシュトポロジをもつ多層フルメッシュシステムが提案されている。提案の多層フルメッシュシステムは、複数のノードと複数のLeaf(葉)スイッチと複数のSpine(背骨)スイッチを含み、複数の層(レイヤ)を形成する。各ノードは何れか1つのLeafスイッチに接続され、各Leafスイッチは何れか1つの層に属し、各Spineスイッチは複数の層を貫通する。

0005

層内では、2以上のLeafスイッチがフルメッシュトポロジにより接続されている。Leafスイッチのペア毎に、他のLeafスイッチを経由しない通信経路が存在する。ただし、Leafスイッチのペア毎に、その間に1つのSpineスイッチが配置されている。よって、層内では、1つのLeafスイッチは別の1つのLeafスイッチと、1つのSpineスイッチを経由して通信することになる。このSpineスイッチは複数の層を接続している。よって、当該1つのLeafスイッチは別の層に属する1つのLeafスイッチとも、1つのSpineスイッチを経由して通信できる。

0006

なお、ツリー状に接続された複数のノードを含む並列コンピュータが提案されている。提案の並列コンピュータは、ツリーのルートに位置する1つのノードから末端に位置する複数のノードに向かってデータをコピーすることで、ブロードキャスト通信を実現する。また、並列コンピュータは、ツリーの末端に位置する複数のノードからルートに位置する1つのノードに向かってデータを転送することで、Reduce通信を実現する。

先行技術

0007

国際公開第2002/069168号
特開2018−185650号公報

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

0008

コレクティブ通信のアルゴリズムには、複数のノードの間の通信順序がツリー状になるように各ノードの通信相手を決定するTreeアルゴリズムがある。Treeアルゴリズムによれば、例えば、プロセス1,3がプロセス2にデータを転送し、プロセス5,7がプロセス6にデータを転送し、プロセス2,6がプロセス4にデータを転送するというように、ツリーの末端からルートに向かってReduce通信を行う。また、例えば、プロセス4がプロセス2,6にデータをコピーし、プロセス2がプロセス1,3にデータをコピーし、プロセス6がプロセス5,7にデータをコピーするというように、ツリーのルートから末端に向かってブロードキャスト通信を行う。

0009

ただし、単一のツリーに従ってコレクティブ通信を行うと、各ノードにおいてデータの送信および受信の少なくとも一方を行っていない空き時間が生じやすく、リンク通信帯域が十分に活用されないことがある。そこで、コレクティブ通信のアルゴリズムとしてTwoTreeアルゴリズムが提案されている。TwoTreeアルゴリズムでは、データ集合を2つに分割すると共に、複数のノードの間の異なる通信順序を示す2つのツリーを生成する。そして、一方のデータ部分集合を一方のツリーに従って集約またはコピーし、他方のデータ部分集合を他方のツリーに従って集約またはコピーする。これにより、コレクティブ通信中のリンク使用率を向上させて通信時間を削減できる。

0010

しかし、並列処理システムのトポロジによっては、複数のツリーに基づく通信を並列に実行すると、通信が競合するリスクが高くなるという問題がある。一方のツリーに従ってプロセス2がプロセス4にデータを転送し、これと並列に他方のツリーに従ってプロセス3がプロセス5にデータを転送する場合、2つの通信経路が同じリンクを使用すると通信が競合し得る。通信が競合すると、パケット送信待ちが発生する、1つのリンクの通信帯域が分割されるなどにより、通信遅延が発生して通信時間が長くなる。

0011

例えば、前述の多層フルメッシュシステムでは、2つのLeafスイッチの間に存在する最短経路の個数は、当該2つのLeafスイッチに共通に接続されているSpineスイッチの個数に相当する。同じ層に属する2つのLeafスイッチの間にある最短経路は1つのみである。よって、1つのLeafスイッチの配下にプロセス2,3が配置され、別の1つのLeafスイッチの配下にプロセス4,5が配置されている場合、プロセス2からプロセス4への通信とプロセス3からプロセス5への通信が競合することがある。

0012

1つの側面では、本発明は、ノード間の通信の競合を抑制できる通信制御プログラム、通信制御方法および情報処理装置を提供することを目的とする。

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

0013

1つの態様では、コンピュータに以下の処理を実行させる通信制御プログラムが提供される。複数のノードと複数の第1の中継装置と複数の第2の中継装置とを含み、複数のノードそれぞれが複数の第1の中継装置の1つと接続され、複数の第1の中継装置それぞれが複数の第2の中継装置の一部である2以上の第2の中継装置と接続されたシステムにおいて、接続された2以上の第2の中継装置が同一でない異なる第1の中継装置に接続された異なるノードが、異なるグループ分類されるように、システムに含まれる複数のノードを複数のグループに分類する。複数のグループそれぞれから代表ノードを選択する。複数のグループに対応する複数の代表ノードの間で実行される第1のノード間通信の通信順序を、1つの代表ノードを基点として、1つの代表ノード以外の他の代表ノードが第1のツリーに従ってデータを転送する第1の転送処理を行い、第1の転送処理と並列に、他の代表ノードが第2のツリーに従って第1の転送処理と異なるデータを転送する第2の転送処理を行うように決定する。複数のグループそれぞれについて、第1のノード間通信の前または後に当該グループに含まれる2以上のノードの間で実行される第2のノード間通信の通信順序を、当該グループの代表ノードを基点として、当該代表ノード以外の他のノードが第3のツリーに従ってデータを転送する第3の転送処理を行い、第3の転送処理と並列に、他のノードが第4のツリーに従って第3の転送処理と異なるデータを転送する第4の転送処理を行うように決定する。

0014

また、1つの態様では、コンピュータが実行する通信制御方法が提供される。また、1つの態様では、記憶部と処理部とを有する情報処理装置が提供される。

発明の効果

0015

1つの側面では、ノード間の通信の競合を抑制できる。

図面の簡単な説明

0016

第1の実施の形態の情報処理システムの例を説明する図である。
第2の実施の形態の多層フルメッシュシステムの例を示す図である。
多層フルメッシュシステムの配線例を示す図である。
サーバハードウェア例を示すブロック図である。
スイッチのハードウェア例を示すブロック図である。
Treeアルゴリズムの例を示す図である。
TreeによるReduce通信の送受信関係の例を示す図である。
TwoTreeアルゴリズムの例を示す図である。
TwoTreeによるReduce通信の送受信関係の例を示す図である。
プロセスの第1の配置例を示す図である。
TwoTreeの生成例を示す図である。
Reduce通信の競合例を示す図である。
プロセスの第2の配置例を示す図である。
ローカルTwoTreeの生成例を示す図である。
グローバルTwoTreeの生成例を示す図である。
サーバとジョブスケジューラの機能例を示す図である。
通信手順テーブルの例を示す図である。
通信手順決定の処理例を示すフローチャートである。
コレクティブ通信の処理例を示すフローチャートである。

実施例

0017

以下、本実施の形態を図面を参照して説明する。
[第1の実施の形態]
第1の実施の形態を説明する。

0018

図1は、第1の実施の形態の情報処理システムの例を説明する図である。
第1の実施の形態の情報処理システムは、並列に情報処理を行う複数のノードの間のノード間通信を制御する。ノード間通信は、コレクティブ通信、集合通信または集団通信と言われるものであってもよい。コレクティブ通信には、複数のノードに分散して記憶されたデータを転送して1つのノードに集約するReduce通信が含まれる。また、コレクティブ通信には、1つのノードに記憶されたデータをコピーして複数のノードに配布するブロードキャスト通信が含まれる。ノード間通信を行う対象のシステムは、例えば、多層フルメッシュトポロジをもつ多層フルメッシュシステムである。ただし、対象のシステムは、後述する構成を備えていれば多層フルメッシュシステムでなくてもよい。

0019

第1の実施の形態の情報処理システムは、情報処理装置10を含む。情報処理装置10は、ノード間通信を行う対象のシステムを制御するジョブスケジューラなどの制御装置でもよいし、対象のシステムに含まれるノードの1つであってもよい。

0020

情報処理装置10は、記憶部および処理部を有する。記憶部は、RAM(Random Access Memory)などの揮発性メモリでもよいし、HDD(Hard Disk Drive)やフラッシュメモリなどの不揮発性ストレージでもよい。処理部は、例えば、CPU(Central Processing Unit)、GPU(Graphics Processing Unit)、DSP(Digital Signal Processor)などのプロセッサである。ただし、処理部は、ASIC(Application Specific IntegratedCircuit)やFPGA(Field Programmable Gate Array)などの特定用途電子回路を含んでもよい。プロセッサは、メモリに記憶されたプログラムを実行する。複数のプロセッサの集合を「マルチプロセッサ」または単に「プロセッサ」と言うことがある。

0021

ノード間通信を行う対象のシステムは、ノード11,12,13,14,15,16,17,18を含む複数のノードを有する。また、対象のシステムは、中継装置21,22,23,24,25,26,27,28を含む複数の中継装置を有する。中継装置21,22,23,24は、下位の中継装置(第1の中継装置)である。中継装置25,26,27,28は、上位の中継装置(第2の中継装置)である。中継装置21,22,23,24,25,26,27,28は、接続関係に応じてデータを転送する。

0022

複数のノードはそれぞれ、複数の第1の中継装置のうちの1つと接続される。複数の第1の中継装置はそれぞれ、複数の第2の中継装置の一部である2以上の第2の中継装置と接続される。図1の例では、ノード11,12が中継装置21に接続され、ノード13,14が中継装置22に接続され、ノード15,16が中継装置23に接続され、ノード17,18が中継装置24に接続される。中継装置21が中継装置25,26に接続され、中継装置22が中継装置25,26に接続され、中継装置23が中継装置26,27に接続され、中継装置24が中継装置26,27に接続される。

0023

情報処理装置10は、対象のシステム上で実行されるノード間通信について、複数のノードの間の通信順序を決定する。ノード間通信は、例えば、複数のフェーズに分割して実行される。1つのフェーズの中で、2以上のノードが並列にデータを送信することがある。ノード間通信の通信順序の決定では、例えば、各フェーズにおいて何れのノードが送信元ノードとして動作するかが決定される。

0024

まず、情報処理装置10は、対象のシステムに含まれる複数ノードを複数のグループに分類する。このとき、情報処理装置10は、複数の第1の中継装置を、接続された2以上の第2の中継装置の同一性に基づいて複数のグループに分類する。接続された2以上の第2の中継装置が一致しない第1の中継装置を、異なるグループに振り分けるようにする。例えば、接続された2以上の第2の中継装置が同一である第1の中継装置を、同一グループに振り分けるようにする。情報処理装置10は、あるグループに分類した第1の中継装置に接続されたノードを、当該グループに属するノードと判定する。1つのノードは何れか1つのグループに属する。

0025

図1の例では、中継装置21と中継装置22は共に、上位の中継装置として中継装置25,26と接続されている。中継装置23と中継装置24は共に、上位の中継装置として中継装置26,27と接続されている。そこで、中継装置21と中継装置22は同一のグループに分類してもよい。また、中継装置23と中継装置24は同一のグループに分類してもよい。一方、中継装置21と中継装置23,24は異なるグループに分類する。また、中継装置22と中継装置23,24は異なるグループに分類する。

0026

ここでは、情報処理装置10は、中継装置21に接続されたノード11,12および中継装置22に接続されたノード13,14を、グループ31に分類する。また、情報処理装置10は、中継装置23に接続されたノード15,16および中継装置24に接続されたノード17,18を、グループ32に分類する。ただし、ノード11,12とノード13,14を異なるグループに分類することも許容される。また、ノード15,16とノード17,18を異なるグループに分類することも許容される。

0027

次に、情報処理装置10は、複数のグループそれぞれから代表ノードを選択する。ここでは、各グループから1つのノードが代表ノードとして選択されればよく、何らかの選択基準を予め定めておけばよい。例えば、情報処理装置10は、グループ内の2以上のノードのうち、実行するプロセスの識別番号が最小のノードを選択する。図1の例では、情報処理装置10は、グループ31からノード11を代表ノードとして選択する。また、情報処理装置10は、グループ32からノード15を代表ノードとして選択する。

0028

次に、情報処理装置10は、複数のグループに対応する複数の代表ノードの間で実行されるノード間通信33(第1のノード間通信)の通信順序を決定する。また、情報処理装置10は、複数のグループそれぞれについて、当該グループに含まれる2以上のノードの間で実行されるノード間通信34(第2のノード間通信)の通信順序を決定する。ノード間通信33とノード間通信34は、それぞれ全体のノード間通信の一部として実行され、異なる段階として区別されて実行される。ノード間通信33はグループ間通信であり、ノード間通信34はグループ内通信である。ノード間通信33では、グループ毎に1つの代表ノードのみが通信に参加する。ノード間通信34は、ノード間通信33の前または後に実行される。例えば、Reduce通信の場合、ノード間通信34はノード間通信33の前に実行され、ブロードキャスト通信の場合、ノード間通信34はノード間通信33の後に実行される。複数のグループのノード間通信34は並列に実行してもよい。

0029

情報処理装置10は、ノード間通信33が以下の条件を満たすように、複数のグループに対応する複数の代表ノードの間の通信順序を決定する。情報処理装置10は、1つの代表ノードを基点として選択し、基点以外の他の代表ノードの間のデータ転送順序を示すツリー35(第1のツリー)およびツリー36(第2のツリー)を生成する。ツリー35とツリー36は、代表ノードの間の異なるデータ転送順序を示している。例えば、ツリー36は、ツリー35における各代表ノードの位置を巡回シフトしたものである。ツリー35,36は、基点に接続されて大きなツリーを形成する。

0030

ノード間通信33では、基点以外の他の代表ノードがツリー35に従ってデータを転送する第1の転送処理を行う。また、第1の転送処理と並列に、基点以外の他の代表ノードがツリー36に従って第1の転送処理と異なるデータを転送する第2の転送処理を行う。

0031

Reduce通信の場合、各代表ノードに記憶されたデータの一部がツリー35の葉からルートに向かって転送され、各代表ノードに記憶されたデータの他の一部(例えば、第1の転送処理で残ったデータ)がツリー36の葉からルートに向かって転送される。これにより、各代表ノードに記憶されたデータが基点に集約される。ブロードキャスト通信の場合、基点に記憶されたデータの一部がツリー35のルートから葉に向かって転送され、基点に記憶されたデータの他の一部がツリー36のルートから葉に向かって転送される。これにより、基点に記憶されたデータが各代表ノードにコピーされる。ここで決定されるノード間通信33の通信順序は、TwoTreeアルゴリズムに基づいていてもよい。

0032

また、情報処理装置10は、ノード間通信34が以下の条件を満たすように、グループ内の2以上のノードの間の通信順序を決定する。情報処理装置10は、グループ内の2以上のノードのうち代表ノードを基点として選択し、基点以外の他のノードの間のデータ転送順序を示すツリー37(第3のツリー)およびツリー38(第4のツリー)を生成する。ツリー37とツリー38は、ノード間の異なるデータ転送順序を示している。例えば、ツリー38は、ツリー37における各ノードの位置を巡回シフトしたものである。ツリー37,38は、基点に接続されて大きなツリーを形成する。

0033

ノード間通信34では、基点以外の他のノードがツリー37に従ってデータを転送する第3の転送処理を行う。また、第3の転送処理と並列に、基点以外の他のノードがツリー38に従って第3の転送処理と異なるデータを転送する第4の転送処理を行う。

0034

Reduce通信の場合、各ノードに記憶されたデータの一部がツリー37の葉からルートに向かって転送され、各ノードに記憶されたデータの他の一部(例えば、第3の転送処理で残ったデータ)がツリー38の葉からルートに向かって転送される。これにより、各ノードに記憶されたデータが代表ノードに集約される。ブロードキャスト通信の場合、代表ノードに記憶されたデータの一部がツリー37のルートから葉に向かって転送され、代表ノードに記憶されたデータの他の一部がツリー38のルートから葉に向かって転送される。これにより、代表ノードから各ノードにデータがコピーされる。ここで決定されるノード間通信34の通信順序は、TwoTreeアルゴリズムに基づいていてもよい。

0035

情報処理装置10は、ノード間通信33の通信順序とノード間通信34の通信順序とを結合して、全体のノード間通信(例えば、全体のコレクティブ通信)の通信手順を決定する。情報処理装置10は、決定した通信手順を示す通信制御情報を生成して記憶する。情報処理装置10がノードの1つである場合、情報処理装置10は、生成した通信制御情報を参照してノード間通信を実行してもよい。情報処理装置10が制御装置である場合、情報処理装置10は、生成した通信制御情報を複数ノードに配布してもよい。

0036

第1の実施の形態の情報処理システムによれば、接続された上位の中継装置が同一でないような異なる下位の中継装置に接続された異なるノードが、異なるグループに分類されるように、ノードがグループ分けされ、グループ毎に代表ノードが選択される。そして、全体のノード間通信が、代表ノード間のノード間通信とグループ内のノード間通信に分けて実行される。代表ノード間のノード間通信およびグループ内のノード間通信それぞれでは、異なる転送順序を示す複数のツリーに基づいて異なるデータが並列に転送されるアルゴリズムに従い、ノード間の通信順序が決定される。

0037

代表ノード間のノード間通信およびグループ内のノード間通信それぞれでは、分割されたデータが異なる転送順序で並列に転送されるため、単一のツリーに基づいて全てのデータを転送する場合よりも、リンクの通信帯域の空き時間を抑制できる。よって、リンクの通信帯域を活用して、Reduce通信やブロードキャスト通信などのノード間通信を高速化できる。また、上記のグループ内通信では、下位の中継装置と上位の中継装置との間の通信経路が冗長化されているため、通信競合が抑制される。また、グループ間通信に参加するノードはグループ毎に1つであるため、グループ間の通信経路の冗長度が低い場合であっても通信競合が抑制される。従って、ノード間通信の全体を通じて通信競合を抑制でき、通信遅延を抑制して通信時間を短縮できる。

0038

[第2の実施の形態]
次に、第2の実施の形態を説明する。
図2は、第2の実施の形態の多層フルメッシュシステムの例を示す図である。

0039

第2の実施の形態の多層フルメッシュシステムは、複数のサーバおよび複数のスイッチを含み、それら複数のサーバおよび複数のスイッチが多層フルメッシュトポロジで接続された並列処理システムである。サーバは、ユーザプログラムを実行可能なノードであり、コンピュータや情報処理装置と言うこともできる。

0040

スイッチは、サーバ間で送信されるデータを中継する通信装置である。後述するように、スイッチはLeafスイッチとSpineスイッチとに分類される。LeafスイッチとSpineスイッチは、同様のハードウェアをもつスイッチであってもよい。第2の実施の形態では、説明を簡単にするため、スイッチのポート数が6であるとする。ただし、スイッチのポート数は、8や10や36など6より大きい偶数であってもよい。

0041

多層フルメッシュシステムは、複数の層を形成する。各サーバは、何れか1つのLeafスイッチに接続される。各Leafスイッチは、何れか1つの層に属する。各Spineスイッチは、複数の層を貫通しており、複数の層のLeafスイッチに接続される。

0042

層内では、複数のLeafスイッチがフルメッシュトポロジを形成する。よって、Leafスイッチのペア毎に、他のLeafスイッチを経由しない最短経路が存在する。2つのLeafスイッチの間には、複数の層を貫通するSpineスイッチが配置される。よって、同じ層に属する2つのLeafスイッチは、1つのSpineスイッチを経由する通信経路によって通信することができる。異なる層に属する2つのLeafスイッチも、1つのSpineスイッチを経由する通信経路によって通信することができる。Leafスイッチは、データをその宛先に応じて最短経路で転送するよう設定される。

0043

ポート数が6である第2の実施の形態では、多層フルメッシュシステムは3つの層を形成する。各層は4つのLeafスイッチを含む。各Leafスイッチには、3つのサーバと3つのSpineスイッチが接続される。各Spineスイッチには、層毎に2つのLeafスイッチが接続され、3つの層の合計で6つのLeafスイッチが接続される。多層フルメッシュシステムは6つのSpineスイッチを含む。

0044

一般に、ポート数がp(pは6以上の偶数)であるスイッチを使用すると、多層フルメッシュシステムはp/2個の層を形成する。各層はp/2+1個のLeafスイッチによってp/2+1角形を形成する。多層フルメッシュシステムは、p2(p+2)/8個のサーバと3p(p+2)/8個のスイッチを含む。p=8の場合、多層フルメッシュシステムは、5角形の4層を形成し、80個のサーバと30個のスイッチを含む。p=10の場合、多層フルメッシュシステムは、6角形の5層を形成し、150個のサーバと45個のスイッチを含む。p=36の場合、多層フルメッシュシステムは、19角形の18層を形成し、6156個のサーバと513個のスイッチを含む。

0045

第2の実施の形態の多層フルメッシュシステムは、層41,42,43を形成する。層41は、Leafスイッチ200,210,220,230を含む。Leafスイッチ200,210,220,230にはそれぞれ3つのサーバが接続される。

0046

Leafスイッチ200とLeafスイッチ210の間にSpineスイッチ240が配置される。Leafスイッチ200とLeafスイッチ220の間にSpineスイッチ241が配置される。Leafスイッチ200とLeafスイッチ230の間にSpineスイッチ242が配置される。Leafスイッチ210とLeafスイッチ220の間にSpineスイッチ243が配置される。Leafスイッチ210とLeafスイッチ230の間にSpineスイッチ244が配置される。Leafスイッチ220とLeafスイッチ230の間にSpineスイッチ245が配置される。

0047

層42,43も、Leafスイッチ200,210,220,230に対応するLeafスイッチを含む。Spineスイッチ240,241,242,243,244,245は、層41,42,43を貫通しており層41,42,43の間で共通である。

0048

例えば、層42は、Leafスイッチ200,220,230に対応するLeafスイッチ201,221,231を含む。Leafスイッチ201とLeafスイッチ231の間にSpineスイッチ242が配置される。Leafスイッチ221とLeafスイッチ231の間にSpineスイッチ245が配置される。層43は、Leafスイッチ202,222,232を含む。Leafスイッチ202とLeafスイッチ232の間にSpineスイッチ242が配置される。Leafスイッチ222とLeafスイッチ232の間にSpineスイッチ245が配置される。

0049

また、第2の実施の形態の多層フルメッシュシステムは、ジョブスケジューラ300を含む。ジョブスケジューラ300は、ユーザからジョブ要求受け付け、ジョブに使用するサーバ(ノード)を選択するサーバ装置である。ジョブスケジューラ300は、コンピュータや情報処理装置と言うこともできる。ジョブは、ユーザプログラムから起動される複数のプロセスを含む。ユーザプログラムは、MPIライブラリなどの通信ライブラリを用いることがある。複数のプロセスには、ランクと呼ばれる非負整数の識別番号が付与される。1つのサーバには1つのプロセスが配置される。ジョブスケジューラ300は、プロセスの配置を決定し、サーバに対してプロセス配置に関する情報を通知する。

0050

ジョブスケジューラ300とサーバとの間の通信には、上記のLeafスイッチやSpineスイッチを含むデータ用ネットワークを使用してもよいし、データ用ネットワークとは異なる管理用ネットワークを使用してもよい。

0051

図3は、多層フルメッシュシステムの配線例を示す図である。
図3は、図2の多層フルメッシュシステムに含まれるサーバとLeafスイッチとSpineスイッチの間の配線を、図2とは異なる形式表現したものである。

0052

多層フルメッシュシステムは、Spineスイッチ240,241,242,243,244,245(SpineスイッチA,B,C,D,E,F)を含む。
また、多層フルメッシュシステムは、Leafスイッチ200,201,202(Leafスイッチa1,a2,a3)を含む。Leafスイッチ200,201,202はそれぞれ、Spineスイッチ240,241,242の3つのSpineスイッチに接続されている。Leafスイッチ200には、サーバ100,101,102が接続されている。Leafスイッチ201には、サーバ103,104,105が接続されている。Leafスイッチ202には、サーバ106,107,108が接続されている。

0053

また、多層フルメッシュシステムは、Leafスイッチ210,211,212(Leafスイッチb1,b2,b3)を含む。Leafスイッチ210,211,212はそれぞれ、Spineスイッチ240,243,244の3つのSpineスイッチに接続されている。Leafスイッチ210には、サーバ110,111,112が接続されている。Leafスイッチ211には、サーバ113,114,115が接続されている。Leafスイッチ212には、サーバ116,117,118が接続されている。

0054

また、多層フルメッシュシステムは、Leafスイッチ220,221,222(Leafスイッチc1,c2,c3)を含む。Leafスイッチ220,221,222はそれぞれ、Spineスイッチ241,243,245の3つのSpineスイッチに接続されている。Leafスイッチ220には、サーバ120,121,122が接続されている。Leafスイッチ221には、サーバ123,124,125が接続されている。Leafスイッチ222には、サーバ126,127,128が接続されている。

0055

また、多層フルメッシュシステムは、Leafスイッチ230,231,232(Leafスイッチd1,d2,d3)を含む。Leafスイッチ230,231,232はそれぞれ、Spineスイッチ242,244,245の3つのSpineスイッチに接続されている。Leafスイッチ230には、サーバ130,131,132が接続されている。Leafスイッチ231には、サーバ133,134,135が接続されている。Leafスイッチ232には、サーバ136,137,138が接続されている。

0056

このように、各Leafスイッチには、上位スイッチとして3つのSpineスイッチが接続されている。層41,42,43の間の対応する位置にあるLeafスイッチは、同一のSpineスイッチに接続されている。第2の実施の形態では、接続されている3つのSpineスイッチが全て同一であるLeafスイッチおよびその配下のサーバを、「層間グループ」または単に「グループ」と言うことがある。

0057

Leafスイッチ200,201,202およびその配下のサーバ100,101,102,103,104,105,106,107,108は、1つのグループ(グループa)を形成する。Leafスイッチ210,211,212およびその配下のサーバ110,111,112,113,114,115,116,117,118は、1つのグループ(グループb)を形成する。Leafスイッチ220,221,222およびその配下のサーバ120,121,122,123,124,125,126,127,128は、1つのグループ(グループc)を形成する。Leafスイッチ230,231,232およびその配下のサーバ130,131,132,133,134,135,136,137,138は、1つのグループ(グループd)を形成する。

0058

図4は、サーバのハードウェア例を示すブロック図である。
サーバ100は、CPU151、RAM152、HDD153、画像インタフェース154、入力インタフェース155、媒体リーダ156およびHCA(Host Channel Adapter)157を有する。上記ユニットバスに接続されている。他のサーバやジョブスケジューラ300も、サーバ100と同様のハードウェアを有する。

0059

CPU151は、プログラムの命令を実行するプロセッサである。CPU151は、HDD153に記憶されたプログラムやデータの少なくとも一部をRAM152にロードし、プログラムを実行する。なお、CPU151は複数のプロセッサコアを備えてもよく、サーバ100は複数のプロセッサを備えてもよい。複数のプロセッサの集合を「マルチプロセッサ」または単に「プロセッサ」と言うことがある。

0060

RAM152は、CPU151が実行するプログラムやCPU151が演算に使用するデータを一時的に記憶する揮発性半導体メモリである。なお、サーバ100は、RAM以外の種類のメモリを備えてもよく、複数のメモリを備えてもよい。

0061

HDD153は、OS(Operating System)やミドルウェアアプリケーションソフトウェアなどのソフトウェアのプログラム、および、データを記憶する不揮発性ストレージである。なお、サーバ100は、フラッシュメモリやSSD(Solid State Drive)など他の種類のストレージを備えてもよく、複数のストレージを備えてもよい。

0062

画像インタフェース154は、CPU151からの命令に従って、サーバ100に接続された表示装置161に画像を出力する。表示装置161として、CRT(Cathode Ray Tube)ディスプレイ液晶ディスプレイ(LCD:Liquid Crystal Display)、有機EL(OEL:Organic Electro-Luminescence)ディスプレイ、プロジェクタなど、任意の種類の表示装置を使用することができる。また、サーバ100に、プリンタなど表示装置161以外の出力デバイスが接続されてもよい。

0063

入力インタフェース155は、サーバ100に接続された入力デバイス162から入力信号を受け付ける。入力デバイス162として、マウスタッチパネルタッチパッドキーボードなど、任意の種類の入力デバイスを使用することができる。また、サーバ100に複数種類の入力デバイスが接続されてもよい。

0064

媒体リーダ156は、記録媒体163に記録されたプログラムやデータを読み取る読み取り装置である。記録媒体163として、フレキシブルディスクFD:Flexible Disk)やHDDなどの磁気ディスク、CD(Compact Disc)やDVD(Digital Versatile Disc)などの光ディスク、半導体メモリなど、任意の種類の記録媒体を使用することができる。媒体リーダ156は、例えば、記録媒体163から読み取ったプログラムやデータを、RAM152やHDD153などの他の記録媒体にコピーする。読み取られたプログラムは、例えば、CPU151によって実行される。なお、記録媒体163は可搬型記録媒体であってもよく、プログラムやデータの配布に用いられることがある。また、記録媒体163やHDD153を、コンピュータ読み取り可能な記録媒体と言うことがある。

0065

HCA157は、InfiniBandの通信インタフェースである。HCA157は、全二重通信が可能であり、データの送信と受信を並列に行える。HCA157は、Leafスイッチ200に接続される。ただし、サーバ100は、HCA157に代えてまたはHCA157に加えて、他の通信規格の通信インタフェースを有してもよい。

0066

図5は、スイッチのハードウェア例を示すブロック図である。
Leafスイッチ200は、CPU251、RAM252、ROM253および通信ポート254,255,256,257,258,259を有する。他のLeafスイッチやSpineスイッチも、Leafスイッチ200と同様のハードウェアを有する。

0067

CPU251は、通信制御プログラムを実行するプロセッサである。CPU251は、通信制御プログラムに従い、受信されたパケットをその宛先に応じた通信ポートに出力する。CPU251は、ROM253に記憶された通信制御プログラムの少なくとも一部をRAM252にロードし、通信制御プログラムを実行する。ただし、通信制御の少なくとも一部を、専用のハードウェア回路を用いて実装することもできる。

0068

RAM252は、CPU251が実行する通信制御プログラムや通信制御に使用するデータを一時的に記憶する揮発性の半導体メモリである。データには、パケットの宛先と出力先の通信ポートとを対応付けルーティング情報が含まれる。ROM253は、通信制御プログラムを記憶する不揮発性ストレージである。ただし、Leafスイッチ200は、フラッシュメモリなど書き換え可能な不揮発性ストレージを備えてもよい。

0069

通信ポート254,255,256,257,258,259は、InfiniBandの通信インタフェースである。通信ポート254,255,256,257,258,259は、全二重通信が可能であり、データの送信と受信を並列に行える。通信ポート254は、サーバ100に接続される。通信ポート255は、サーバ101に接続される。通信ポート256は、サーバ102に接続される。通信ポート257は、Spineスイッチ241に接続される。通信ポート258は、Spineスイッチ242に接続される。通信ポート259は、Spineスイッチ243に接続される。ただし、Leafスイッチ200は、通信ポート254,255,256,257,258,259に代えてまたは通信ポート254,255,256,257,258,259に加えて、他の通信規格の通信インタフェースを有してもよい。

0070

次に、多層フルメッシュシステム上のコレクティブ通信について説明する。
同一のジョブに属する複数のプロセスは、それら複数のプロセスが一斉にデータ送信に参加するコレクティブ通信を行うことがある。ユーザプログラムがMPIライブラリのコレクティブ通信の命令を呼び出すことで、一斉のデータ送信を開始できる。

0071

コレクティブ通信の1つの種類として、Reduce通信がある。Reduce通信では、ランク0のプロセスなど特定のプロセスに、他の全てのプロセスがもつデータを集約する。1ノード1プロセスを仮定すると、Reduce通信は、特定のサーバ(ノード)に他のサーバ(ノード)がもつデータを転送するものであると言える。複数のプロセスは異なるデータをもつことが多い。集約するデータは、ジョブの実行結果を示す結果データであることもあるし、ジョブの途中経過を示す中間データであることもある。

0072

また、コレクティブ通信の1つの種類として、ブロードキャスト通信がある。ブロードキャスト通信では、ランク0のプロセスなど特定のプロセスがもつデータを、他の全てのプロセスにコピーする。1ノード1プロセスを仮定すると、ブロードキャスト通信は、あるサーバ(ノード)から他の全てのサーバ(ノード)に同一データを送信するものであると言える。コピーするデータは、プロセスに入力する入力データであることもある。

0073

また、コレクティブ通信の1つとして、Allreduce通信がある。Allreduce通信では、複数のプロセスがもつデータの全体を、それら複数のプロセスの全てにコピーする。Allreduce通信は、複数のプロセスがもつデータを集約する処理と、集約したデータを全てのプロセスにコピーする処理に分割できる。よって、Allreduce通信は、Reduce通信とブロードキャスト通信を組み合わせて実現できる。

0074

コレクティブ通信のアルゴリズムの1つにTreeアルゴリズムがある。以下では、コレクティブ通信の種類として主にReduce通信を想定する。
図6は、Treeアルゴリズムの例を示す図である。

0075

ここでは、サーバ100がランク0のプロセスを実行し、サーバ101がランク1のプロセスを実行し、サーバ102がランク2のプロセスを実行し、サーバ103がランク3のプロセスを実行するものとする。また、サーバ104がランク4のプロセスを実行し、サーバ105がランク5のプロセスを実行し、サーバ106がランク6のプロセスを実行し、サーバ107がランク7のプロセスを実行するものとする。

0076

Treeアルゴリズムでは、通信相手のトポロジが二分木になるように複数のサーバの間の通信手順が決定される。ツリーのルート以外に位置するサーバは、1つ上(ルートに近付く方向)のレベルに位置する何れか1つのサーバと通信する。ツリーの葉以外に位置するサーバは、1つ下(葉に近付く方向)のレベルに位置する何れか1つまたは2つのサーバと通信する。ツリーを構成するプロセスは、そのランク番号がインオーダの順になるようツリーに配置される。あるサーバに配置されたプロセスのランクは、左下に位置するサーバに配置されたプロセスのランクより大きく、右下に位置するサーバに配置されたプロセスのランクより小さい。ただし、複数のサーバの通信相手が木構造で決定されればよく、ランクがインオーダの順で木構造に配置されなくてもよい。

0077

あるサーバと左下のサーバとの間の通信は、当該サーバと右下のサーバとの間の通信と同一のリンクを使用することになるため、並列には実行されない。よって、ツリー上の分岐があるレベルの通信は、左側の通信のフェーズと右側の通信のフェーズの2つに分割される。ツリー上の分岐がないレベルの通信は、1つのフェーズで実行される。

0078

Reduce通信は、ツリーの葉からルートへ向かうデータ転送として表現される。ブロードキャスト通信は、ツリーのルートから葉へ向かうデータ転送として表現される。Allreduce通信は、ツリーの葉からルートへ向かうデータ転送の後に、ツリーのルートから葉へ向かうデータ転送を行うものとして表現される。

0079

ここでは、サーバ100がツリーのルートに位置する。サーバ101,103,105,107がツリーの葉に位置する。サーバ101がサーバ102と通信し、これと並列にサーバ105がサーバ106と通信する。サーバ103がサーバ102と通信し、これと並列にサーバ107がサーバ106と通信する。サーバ102がサーバ104と通信する。サーバ106がサーバ104と通信する。サーバ104がサーバ100と通信する。

0080

Reduce通信の場合、サーバ101のデータをサーバ101がサーバ102に送信し、これと並列にサーバ105のデータをサーバ105がサーバ106に送信する。サーバ103のデータをサーバ103がサーバ102に送信し、これと並列にサーバ107のデータをサーバ107がサーバ106に送信する。サーバ101,102,103のデータをサーバ102がサーバ104に送信する。サーバ105,106,107のデータをサーバ106がサーバ104に送信する。最後に、サーバ101,102,103,104,105,106,107のデータをサーバ104がサーバ100に送信する。

0081

これにより、サーバ100にサーバ100,101,102,103,104,105,106,107のデータが集約される。このように、ツリーの葉でもルートでもないサーバは、下位の2つのサーバからデータを受信し、受信したデータに自身のデータを加えて上位のサーバに転送する。なお、ツリーの同一レベルの左側通信と右側通信は、何れを先に実行してもよい。また、データを複数のブロックに分割し、分割したブロック単位パイプライン通信を行うようにすることもできる。この場合、ツリーの葉でもルートでもないサーバは、あるブロックを下位のサーバから受信することと、別のブロックを上位のサーバに送信することを、並列に行うことができる。

0082

ブロードキャスト通信の場合、サーバ100がデータをコピーしてサーバ104に送信する。サーバ104がデータをコピーしてサーバ106に送信する。また、サーバ104がデータをコピーしてサーバ102に送信する。サーバ106がデータをコピーしてサーバ107に送信し、これと並列にサーバ102がデータをコピーしてサーバ103に送信する。サーバ106がデータをコピーしてサーバ105に送信し、これと並列にサーバ102がデータをコピーしてサーバ101に送信する。

0083

これにより、サーバ100のデータがサーバ101,102,103,104,105,106,107にコピーされる。このように、ツリーの葉でもルートでもないサーバは、上位のサーバからデータを受信し、受信したデータを下位の2つのサーバに転送する。なお、上記のようにパイプライン通信を行うこともできる。この場合、ツリーの葉でもルートでもないサーバは、あるブロックを上位のサーバから受信することと、別のブロックを下位のサーバに送信することを、並列に行うことができる。

0084

以下では、データを分割してパイプライン通信を行うことを想定する。
図7は、TreeによるReduce通信の送受信関係の例を示す図である。
パイプライン通信においても、各サーバは、リンクを共用することになるため、異なる2つのサーバから並列にブロックを受信することはせず、異なる2つのサーバに並列にブロックを送信することはしない。一方で、各サーバは、全二重通信が可能なため、あるサーバからのブロックの受信と、あるサーバへのブロックの送信とを並列に行える。

0085

そこで、図6のTreeに従ったサーバ間通信は、図7のように2つのフェーズに分割される。同一フェーズ内の異なるノードペアの通信は並列に行える。2つのフェーズは、分割された複数のブロックの転送が完了するまで交互に実行される。

0086

ここでは、図6のTreeの左側のエッジの通信と右側のエッジの通信とを異なるフェーズに割り振る方法を採用する。すると、Reduce通信の左側フェーズは、サーバ101からサーバ102への送信と、サーバ105からサーバ106への送信と、サーバ102からサーバ104への送信と、サーバ104からサーバ100への送信とを含む。右側フェーズは、サーバ103からサーバ102への送信と、サーバ107からサーバ106への送信と、サーバ106からサーバ104への送信とを含む。

0087

ただし、パイプライン方式であるため、各フェーズにおいて図7に規定された全ての通信が行われるとは限らない。送信元サーバは、転送すべきブロックがまだ到着していない場合はデータ送信を行わない。また、送信元サーバは、全てのブロックの転送が完了して次に転送すべきブロックが無い場合はデータ送信を行わない。

0088

例えば、1回目の左側フェーズにおいて、サーバ101,105がそれぞれ1番目のブロックを送信する。このとき、サーバ102,104はデータ送信を行わない。次に、1回目の右側フェーズにおいて、サーバ103,107がそれぞれ1番目のブロックを送信する。このとき、サーバ106はデータ送信を行わない。

0089

次に、2回目の左側フェーズにおいて、サーバ101,105がそれぞれ2番目のブロックを送信する。また、サーバ102が、サーバ101,102,103の1番目のブロックのReduction結果をサーバ104に送信する。このとき、サーバ104はデータ送信を行わない。次に、2回目の右側フェーズにおいて、サーバ103,107がそれぞれ2番目のブロックを送信する。また、サーバ106が、サーバ105,106,107の1番目のブロックのReduction結果をサーバ104に送信する。

0090

次に、3回目の左側フェーズにおいて、サーバ101,105がそれぞれ3番目のブロックを送信する。また、サーバ102が、サーバ101,102,103の2番目のブロックのReduction結果をサーバ104に送信する。また、サーバ104が、サーバ101,102,103,104,105,106,107の1番目のブロックのReduction結果をサーバ100に送信する。次に、3回目の右側フェーズにおいて、サーバ103,107がそれぞれ3番目のブロックを送信する。また、サーバ106が、サーバ105,106,107の2番目のブロックのReduction結果をサーバ104に送信する。このように、複数のブロックがパイプライン方式で転送される。

0091

ただし、各サーバはデータの送信と受信の両方を行う通信帯域をもっている一方、単純なTreeアルゴリズムでは、パイプライン通信を採用しても、各サーバにおいてデータの送信と受信の少なくとも一方を行っていない空き時間が多く生じる。そのため、通信帯域が十分に活用されずコレクティブ通信の所要時間が長くなるおそれがある。この問題に対して、Treeアルゴリズムを改良したTwoTreeアルゴリズムがある。

0092

TwoTreeアルゴリズムについては、次の非特許文献にも記載がある。Peter Sanders, Jochen Speck and Jesper Larsson Traff, "Two-tree algorithms for full bandwidth broadcast, reduction and scan", ScienceDirect Parallel Computing, Volume 35, Issue 12, pp.581-594, December 2009。

0093

図8は、TwoTreeアルゴリズムの例を示す図である。
TwoTreeアルゴリズムでは、ルート以外のサーバの間で通信手順が異なる2つの部分木を生成し、2つの部分木とルートとを結合してTwoTreeを生成する。一方の部分木は、例えば、他方の部分木のランクを1つだけ巡回シフトすることで生成できる。ただし、巡回シフト以外の方法で他方の部分木を生成してもよい。

0094

2つの部分木に従った通信は並列に実行される。データ集合全体が2つに分割され、一方のデータ部分集合が一方の部分木に従って転送され、他方のデータ部分集合が他方の部分木に従って転送される。TwoTreeアルゴリズムは、Treeアルゴリズムでは空いていたリンクの通信帯域を活用することでコレクティブ通信の時間を短縮することを目的としている。ここで、TwoTreeの場合、単純にTwoTreeのエッジの左側の通信と右側の通信を異なるフェーズに振り分けると、同じフェーズの中で1つのサーバがブロックの送信または受信を複数実行する状況が発生することがある。これを解決するため、カラーリングと呼ばれる通信スケジュールを設定する方法が上記の非特許文献などで提案されている。カラーリングによって、大部分のサーバは各フェーズで高々1つの送信と高々1つの受信を行うことができる。一方、同じフェーズの中で1つのサーバが異なる2つのサーバにデータを送信することはない。また、同じフェーズの中で1つのサーバが異なる2つのサーバからデータを受信することはない。

0095

図8は、カラーリングの設定例を示している。エッジに付された番号がカラーである。同じカラーが付された通信は同じフェーズに分類される。よって、図8のTwoTreeからは、カラー0フェーズとカラー1フェーズが形成される。カラー0フェーズに属する複数の通信は並列に実行可能である。また、カラー1フェーズに属する複数の通信は並列に実行可能である。カラー0フェーズとカラー1フェーズとは交互に実行される。

0096

ここでは、サーバ101がサーバ102と通信し、これと並列にサーバ107がサーバ106と通信し、これと並列にサーバ104がサーバ103と通信し、これと並列にサーバ106がサーバ107と通信する。サーバ103がサーバ102と通信し、これと並列にサーバ105がサーバ106と通信し、これと並列にサーバ102がサーバ103と通信し、これと並列にサーバ101がサーバ107と通信する。サーバ102がサーバ104と通信し、これと並列にサーバ103がサーバ105と通信する。サーバ106がサーバ104と通信し、これと並列にサーバ107がサーバ105と通信する。サーバ105がサーバ100と通信する。サーバ104がサーバ100と通信する。

0097

Reduce通信の場合、サーバ101の半分のデータをサーバ101がサーバ102に送信し、これと並列にサーバ107の半分のデータをサーバ107がサーバ106に送信する。更に、サーバ104の半分のデータをサーバ104がサーバ103に送信し、これと並列にサーバ106の半分のデータをサーバ106がサーバ107に送信する。

0098

サーバ101,102,103の半分のデータのReduction結果をサーバ102がサーバ104に送信し、これと並列にサーバ102,103,104の半分のデータのReduction結果をサーバ103がサーバ105に送信する。また、サーバ105,106,107の半分のデータのReduction結果をサーバ106がサーバ104に送信し、これと並列にサーバ101,106,107の半分のデータのReduction結果をサーバ107がサーバ105に送信する。

0099

サーバ101,102,103,104,105,106,107の半分のデータのReduction結果をサーバ105がサーバ100に送信する。サーバ101,102,103,104,105,106,107の半分のデータのReduction結果をサーバ104がサーバ100に送信する。

0100

ブロードキャスト通信の場合、サーバ100が半分のデータをコピーしてサーバ105に送信する。サーバ100が半分のデータをコピーしてサーバ104に送信する。サーバ105が半分のデータをサーバ103に送信し、これと並列にサーバ104が半分のデータをサーバ102に送信する。また、サーバ105が半分のデータをサーバ107に送信し、これと並列にサーバ104が半分のデータをサーバ106に送信する。

0101

サーバ107が半分のデータをサーバ106に送信し、これと並列にサーバ103が半分のデータをサーバ104に送信する。更に、サーバ106が半分のデータをサーバ107に送信し、これと並列にサーバ102が半分のデータをサーバ101に送信する。また、サーバ107が半分のデータをサーバ101に送信し、これと並列にサーバ103が半分のデータをサーバ102に送信する。更に、サーバ106が半分のデータをサーバ105に送信し、これと並列にサーバ102が半分のデータをサーバ103に送信する。

0102

上記のデータ通信パイプライン化できる。左部分木右部分木それぞれについて、分割データを更に複数のブロックに分割してパイプライン方式で転送することができる。
図9は、TwoTreeによるReduce通信の送受信関係の例を示す図である。

0103

Reduce通信のカラー0フェーズは、サーバ101からサーバ102への送信と、サーバ102からサーバ104への送信と、サーバ107からサーバ106への送信と、サーバ105からサーバ100への送信とを含む。また、カラー0フェーズは、サーバ103からサーバ105への送信と、サーバ104からサーバ103への送信と、サーバ106からサーバ107への送信とを含む。

0104

Reduce通信のカラー1フェーズは、サーバ103からサーバ102への送信と、サーバ105からサーバ106への送信と、サーバ106からサーバ104への送信と、サーバ104からサーバ100への送信とを含む。また、カラー1フェーズは、サーバ102からサーバ103への送信と、サーバ101からサーバ107への送信と、サーバ107からサーバ105への送信とを含む。

0105

例えば、1回目のカラー0フェーズにおいて、サーバ101,104,106,107がそれぞれ1番目のブロックを送信する。次に、1回目のカラー1フェーズにおいて、サーバ101,102,103,105がそれぞれ1番目のブロックを送信する。

0106

次に、2回目のカラー0フェーズにおいて、サーバ101,104,106,107がそれぞれ2番目のブロックを送信する。また、サーバ102,103が1番目のブロックのReduction結果を送信する。次に、2回目のカラー1フェーズにおいて、サーバ101,102,103,105がそれぞれ2番目のブロックを送信する。また、サーバ106,107が1番目のブロックのReduction結果を送信する。

0107

次に、3回目のカラー0フェーズにおいて、サーバ101,104,106,107がそれぞれ3番目のブロックを送信する。また、サーバ102,103が2番目のブロックのReduction結果を送信する。また、サーバ105が1番目のブロックのReduction結果を送信する。次に、3回目のカラー1フェーズにおいて、サーバ101,102,103,105がそれぞれ3番目のブロックを送信する。また、サーバ106,107が2番目のブロックのReduction結果を送信する。また、サーバ104が1番目のブロックのReduction結果を送信する。

0108

ただし、TwoTreeアルゴリズムでは、Treeアルゴリズムよりもデータ通信の並列度が増加する。よって、プロセスの配置状況によっては、データ通信が競合するリスクが高くなる。同じフェーズにおいて2つのデータ通信が同じリンクを同じ方向に使用する場合、データ通信が競合している(衝突している)と言える。データ通信が競合すると、パケットの送信待ちが発生する、1つのリンクの通信帯域が分割されるなどにより、通信遅延が発生して通信時間が長くなるおそれがある。以下、通信競合について説明する。

0109

図10は、プロセスの第1の配置例を示す図である。
通信競合の例を説明するにあたり、36個のサーバのうちの32個のサーバに、ランク0からランク31の32個のプロセスを配置することを考える。

0110

ここでは、グループaのサーバ100,101,102,103,104,105,106,107,108に、ランク0,1,2,3,4,5,6,7,8のプロセスが配置される。グループbのサーバ110,111,112,113,114,115,116,117,118に、ランク9,10,11,12,13,14,15,16,17のプロセスが配置される。グループcのサーバ120,121,122,123,124,125,126,127,128に、ランク18,19,20,21,22,23,24,25,26のプロセスが配置される。グループdのサーバ130,131,132,133,134に、ランク27,28,29,30,31のプロセスが配置される。

0111

図11は、TwoTreeの生成例を示す図である。
ランク0からランク31の32個のプロセスの間でTwoTreeが生成される。
左部分木では、サーバ103,105,110,116,118,125,130,132とサーバ102,106,111,115,120,124,128,133の間でデータ通信が並列に行われる。サーバ101,107,112,114,121,123,127,134とサーバ102,106,111,115,120,124,128,133の間でデータ通信が並列に行われる。

0112

また、サーバ106,111,120,133とサーバ104,113,122,131の間でデータ通信が並列に行われる。サーバ102,115,124,128とサーバ104,113,122,131の間でデータ通信が並列に行われる。サーバ104,131とサーバ108,126の間でデータ通信が並列に行われる。サーバ113,122とサーバ108,126の間でデータ通信が並列に行われる。サーバ126とサーバ117の間でデータ通信が行われる。サーバ108とサーバ117の間でデータ通信が行われる。サーバ117とサーバ100の間でデータ通信が行われる。

0113

右部分木では、サーバ102,108,113,115,122,124,128,101とサーバ103,107,112,116,121,125,130,134の間でデータ通信が並列に行われる。サーバ104,106,111,117,120,126,131,133とサーバ103,107,112,116,121,125,130,134の間でデータ通信が並列に行われる。

0114

また、サーバ107,112,121,134とサーバ105,114,123,132の間でデータ通信が並列に行われる。サーバ103,116,125,130とサーバ105,114,123,132の間でデータ通信が並列に行われる。サーバ114,123とサーバ110,127の間でデータ通信が並列に行われる。サーバ105,132とサーバ110,127の間でデータ通信が並列に行われる。サーバ127とサーバ118の間でデータ通信が行われる。サーバ110とサーバ118の間でデータ通信が行われる。サーバ118とサーバ100の間でデータ通信が行われる。

0115

図12は、Reduce通信の競合例を示す図である。
上記の図11のTwoTreeに従ってReduce通信を行った場合、第2の実施の形態の多層フルメッシュシステムでは通信競合が生じる。例えば、左部分木には、プロセス24が配置されたサーバ126からプロセス16が配置されたサーバ117へのデータ送信が規定される。一方、右部分木には、同じレベルで、プロセス25が配置されたサーバ127からプロセス17が配置されたサーバ118へのデータ送信が規定される。この2つのデータ通信は、Leafスイッチ222とSpineスイッチ243とLeafスイッチ212を順に経由する通信経路を使用しており、通信競合が生じる。

0116

図13は、プロセスの第2の配置例を示す図である。
ランク0からランク31の32個のプロセスを配置する別の例を考える。
ここでは、グループaのサーバ100,101,102,103,104,105,106,107に、ランク0,1,2,3,4,5,6,7のプロセスが配置される。グループbのサーバ110,111,112,113,114,115,116,117に、ランク8,9,10,11,12,13,14,15のプロセスが配置される。グループcのサーバ120,121,122,123,124,125,126,127に、ランク16,17,18,19,20,21,22,23のプロセスが配置される。グループdのサーバ130,131,132,133,134,135,136,137に、ランク24,25,26,27,28,29,30,31のプロセスが配置される。

0117

しかし、図13のようにグループa,b,c,dに均等にプロセスを配置しても、TwoTreeに従ってReduce通信を行った場合には通信競合が生じる。例えば、左部分木には、プロセス24が配置されたサーバ130からプロセス16が配置されたサーバ120へのデータ送信が規定される。一方、右部分木には、同じレベルで、プロセス25が配置されたサーバ131からプロセス17が配置されたサーバ121へのデータ送信が規定される。この2つのデータ通信は、Leafスイッチ230とSpineスイッチ245とLeafスイッチ220を順に経由する通信経路を使用しており、通信競合が生じる。

0118

そこで、第2の実施の形態の多層フルメッシュシステムは、通信競合が生じないようにコレクティブ通信の手順を規定する。具体的には、各グループから1つの代表プロセスを選択し、グループ毎に当該グループに属する複数のプロセスの間で代表プロセスをルートとするローカルTwoTreeを生成する。グループ内ではローカルTwoTreeに従ってデータが転送される。また、複数のグループに対応する複数の代表プロセスの間で、ローカルTwoTreeとは別にグローバルTwoTreeを生成する。グループ間ではグローバルTwoTreeに従ってデータが転送される。各グループの代表プロセスは、例えば、グループ内でランクが最小のプロセスである。ただし、代表プロセスはグループ毎に1つに決まればよく、他の選択基準を採用してもよい。

0119

Reduce通信の場合、グループ内でローカルTwoTreeに従ってデータが代表プロセスに集約される。複数のグループのグループ内通信は並列に実行される。グループ内通信の後、グループ間でグローバルTwoTreeに従ってデータが1つのプロセスに集約される。ブロードキャスト通信の場合、1つのプロセスのデータがグローバルTwoTreeに従って各グループの代表プロセスにコピーされる。グループ間通信の後、グループ内でローカルTwoTreeに従って代表プロセスから他のプロセスにデータがコピーされる。複数のグループのグループ内通信は並列に実行される。以下、第2の実施の形態のコレクティブ通信の手順を説明する。

0120

図14は、ローカルTwoTreeの生成例を示す図である。
ここでは、32個のプロセスが図13のように配置されているとする。32個のプロセスは、グループa,b,c,dに8個ずつ分配されている。そこで、グループa,b,c,dに対応する4つのローカルTwoTreeが生成される。

0121

グループaのローカルTwoTreeでは、ランク0のプロセスが代表プロセスである。右部分木は、左部分木のランクを1つだけ巡回シフトしたものである。サーバ101,107がサーバ102,106と通信し、これと並列にサーバ104,106がサーバ103,107と通信する(カラー0フェーズの第1段)。サーバ103,105がサーバ102,106と通信し、これと並列にサーバ102,101がサーバ103,107と通信する(カラー1フェーズの第1段)。サーバ102がサーバ104と通信し、これと並列にサーバ103がサーバ105と通信する(カラー0フェーズの第2段)。サーバ106がサーバ104と通信し、これと並列にサーバ107がサーバ105と通信する(カラー1フェーズの第2段)。サーバ105がサーバ100と通信する(カラー0フェーズの第3段)。サーバ104がサーバ100と通信する(カラー1フェーズの第3段)。

0122

グループbのローカルTwoTreeでは、ランク8のプロセスが代表プロセスである。右部分木は、左部分木のランクを1つだけ巡回シフトしたものである。サーバ111,117がサーバ112,116と通信し、これと並列にサーバ114,116がサーバ113,117と通信する(カラー0フェーズの第1段)。サーバ113,115がサーバ112,116と通信し、これと並列にサーバ112,111がサーバ113,117と通信する(カラー1フェーズの第1段)。サーバ112がサーバ114と通信し、これと並列にサーバ113がサーバ115と通信する(カラー0フェーズの第2段)。サーバ116がサーバ114と通信し、これと並列にサーバ117がサーバ115と通信する(カラー1フェーズの第2段)。サーバ115がサーバ110と通信する(カラー0フェーズの第3段)。サーバ114がサーバ110と通信する(カラー1フェーズの第3段)。

0123

グループcのローカルTwoTreeでは、ランク16のプロセスが代表プロセスである。右部分木は、左部分木のランクを1つだけ巡回シフトしたものである。サーバ121,127がサーバ122,126と通信し、これと並列にサーバ124,126がサーバ123,127と通信する(カラー0フェーズの第1段)。サーバ123,125がサーバ122,126と通信し、これと並列にサーバ122,121がサーバ123,127と通信する(カラー1フェーズの第1段)。サーバ122がサーバ124と通信し、これと並列にサーバ123がサーバ125と通信する(カラー0フェーズの第2段)。サーバ126がサーバ124と通信し、これと並列にサーバ127がサーバ125と通信する(カラー1フェーズの第2段)。サーバ125がサーバ120と通信する(カラー0フェーズの第3段)。サーバ124がサーバ120と通信する(カラー1フェーズの第3段)。

0124

グループdのローカルTwoTreeでは、ランク24のプロセスが代表プロセスである。右部分木は、左部分木のランクを1つだけ巡回シフトしたものである。サーバ131,137がサーバ132,136と通信し、これと並列にサーバ134,136がサーバ133,137と通信する(カラー0フェーズの第1段)。サーバ133,135がサーバ132,136と通信し、これと並列にサーバ132,131がサーバ133,137と通信する(カラー1フェーズの第1段)。サーバ132がサーバ134と通信し、これと並列にサーバ133がサーバ135と通信する(カラー0フェーズの第2段)。サーバ136がサーバ134と通信し、これと並列にサーバ137がサーバ135と通信する(カラー1フェーズの第2段)。サーバ135がサーバ130と通信する(カラー0フェーズの第3段)。サーバ134がサーバ130と通信する(カラー1フェーズの第3段)。

0125

Reduce通信の場合、グループaでは、ローカルTwoTreeに従ってランク0,1,2,3,4,5,6,7のデータがサーバ100に集約される。グループbでは、ローカルTwoTreeに従ってランク8,9,10,11,12,13,14,15のデータがサーバ110に集約される。グループcでは、ローカルTwoTreeに従ってランク16,17,18,19,20,21,22,23のデータがサーバ120に集約される。グループdでは、ローカルTwoTreeに従ってランク24,25,26,27,28,29,30,31のデータがサーバ130に集約される。

0126

ブロードキャスト通信の場合、グローバルTwoTreeに基づくグループ間通信により、サーバ100,110,120,130が同一データを保持することになる。グループaでは、ローカルTwoTreeに従ってサーバ100から他のサーバにデータがコピーされる。グループbでは、ローカルTwoTreeに従ってサーバ110から他のサーバにデータがコピーされる。グループcでは、ローカルTwoTreeに従ってサーバ120から他のサーバにデータがコピーされる。グループdでは、ローカルTwoTreeに従ってサーバ130から他のサーバにデータがコピーされる。

0127

Reduce通信をパイプライン方式で行う場合、カラー0フェーズの第1段が1番目のブロックを送信している間、カラー0フェーズの第2段および第3段はデータ送信を行わない。カラー1フェーズの第1段が1番目のブロックを送信している間、カラー1フェーズの第2段および第3段はデータ送信を行わない。カラー0フェーズの第1段が2番目のブロックを送信している間、カラー0フェーズの第2段が1番目のブロックを転送し、カラー0フェーズの第3段はデータ送信を行わない。カラー1フェーズの第1段が2番目のブロックを送信している間、カラー1フェーズの第2段が1番目のブロックを転送し、カラー1フェーズの第3段はデータ送信を行わない。カラー0フェーズの第1段が3番目のブロックを送信している間、カラー0フェーズの第2段が2番目のブロックを転送し、カラー0フェーズの第3段が1番目のブロックを転送する。カラー1フェーズの第1段が3番目のブロックを送信している間、カラー1フェーズの第2段が2番目のブロックを転送し、カラー1フェーズの第3段が1番目のブロックを転送する。

0128

このようなグループ内通信では競合を回避可能である。これは、グループ内ネットワークがFatTreeトポロジに相当するためである。FatTreeトポロジは、Treeトポロジに含まれる上位の通信装置を多重化することで、異なる下位の通信装置の間の通信経路を多重化し、トラフィック混雑を軽減するネットワークトポロジである。

0129

第2の実施の形態の多層フルメッシュシステムでは、3つのLeafスイッチそれぞれがもつSpineスイッチ側のリンクは3本であり、サーバ側のリンクと同数である。また、1つのLeafスイッチから別の1つのLeafスイッチに到達する通信経路は3つある。3つのLeafスイッチと3つのSpineスイッチの間には合計で9つの通信経路が存在することになり、3つのLeafスイッチに接続されたサーバと同数である。よって、1つのサーバに対してLeafスイッチとSpineスイッチの間の1つの通信経路を割り当てれば、9つのサーバは競合なしにデータ通信を行うことができる。

0130

図15は、グローバルTwoTreeの生成例を示す図である。
グループa,b,c,dそれぞれのローカルTwoTreeに加えて、グループa,b,c,dの代表プロセスであるランク0,8,16,24のプロセスの間でグローバルTwoTreeが生成される。ランク0のプロセスがグローバルTwoTreeのルートに相当する。右部分木は、左部分木のランクを巡回シフトしたものである。サーバ130がサーバ120と通信し、これと並列にサーバ110がサーバ130と通信する(カラー0フェーズの第1段)。サーバ110がサーバ120と通信し、これと並列にサーバ120がサーバ130と通信する(カラー1フェーズの第1段)。サーバ120がサーバ100と通信する(カラー0フェーズの第2段)。サーバ130がサーバ100と通信する(カラー1フェーズの第2段)。

0131

Reduce通信の場合、ローカルTwoTreeに従ってサーバ110に集約されたランク8,9,10,11,12,13,14,15のデータがサーバ100に転送される。また、ローカルTwoTreeに従ってサーバ120に集約されたランク16,17,18,19,20,21,22,23のデータがサーバ100に転送される。また、ローカルTwoTreeに従ってサーバ130に集約されたランク24,25,26,27,28,29,30,31のデータがサーバ100に転送される。ブロードキャスト通信の場合、サーバ100がもつデータがサーバ110,120,130にコピーされる。

0132

全体のReduce通信は、ローカルTwoTreeのReduce通信の後に、グローバルTwoTreeのReduce通信を行うことで実現される。全体のブロードキャスト通信は、グローバルTwoTreeのブロードキャスト通信の後に、ローカルTwoTreeのブロードキャスト通信を行うことで実現される。全体のAllreduce通信は、ローカルTwoTreeのReduce通信、グローバルTwoTreeのReduce通信、グローバルTwoTreeのブロードキャスト通信およびローカルTwoTreeのブロードキャスト通信を順に行うことで実現される。これは、ローカルTwoTreeのReduce通信、グローバルTwoTreeのAllreduce通信およびローカルTwoTreeのブロードキャスト通信を順に行うものであるとも言える。

0133

このように、各グループから代表プロセスを選択し、代表プロセスが配置されたサーバのみが通信を行うようにすると、グループ間通信において競合が生じない。これは、異なるグループに属するLeafスイッチの間にはフルメッシュの通信経路が存在するためである。フルメッシュの通信経路が存在するため、例えば、グループbからグループcへのデータ送信経路は、グループcからグループdへのデータ送信経路とリンクを共有しない。代表プロセスの配置されたサーバが異なる層に跨がっていても同様である。

0134

次に、サーバとジョブスケジューラの機能について説明する。
図16は、サーバとジョブスケジューラの機能例を示す図である。
サーバ100は、通信手順決定部171、通信手順記憶部172およびコレクティブ通信実行部173を有する。通信手順記憶部172は、例えば、RAM152またはHDD153の記憶領域を用いて実現される。通信手順決定部171およびコレクティブ通信実行部173は、例えば、CPU151が実行するプログラムを用いて実現される。他のサーバもサーバ100と同様のモジュールを有する。

0135

通信手順決定部171は、ジョブスケジューラ300から、ジョブに属する複数のプロセスの配置に関するプロセス配置情報を受信する。プロセス配置情報は、グループとプロセスの対応関係や、サーバ100に配置されたプロセスのTwoTree上の位置を、通信手順決定部171が把握するのに十分な情報であればよい。プロセス配置情報に含めるべき情報は、プロセス配置アルゴリズムについて、通信手順決定部171とジョブスケジューラ300とが事前にどの程度合意しているかにも依存する。

0136

例えば、プロセス配置情報は、プロセスのランクとプロセスが配置されたサーバのノードIDとを対応付けた情報を含んでもよい。また、プロセス配置情報は、ジョブに使用するグループの数、グループ毎のプロセス数、全体のプロセス数などを含んでもよい。また、プロセス配置情報は、サーバ100に配置されたプロセスが属するグループの中におけるランクのオフセットを含んでもよい。

0137

通信手順決定部171は、受信したプロセス配置情報に基づいて、コレクティブ通信における複数のプロセスの間の通信手順を決定する。Reduce通信の手順とブロードキャスト通信の手順は逆の関係にあり、Allreduce通信はReduce通信とブロードキャスト通信の組み合わせであるため、Reduce通信とブロードキャスト通信の何れか一方の手順を決定すればよい。第2の実施の形態では、通信手順決定部171は、Reduce通信の手順を決定する。通信手順決定部171は、決定した通信手順を示す通信手順情報を生成し、通信手順記憶部172に格納する。

0138

コレクティブ通信の手順は、MPIライブラリなどの通信ライブラリの初期化時に決定される。通信ライブラリを使用するユーザプログラムが複数のサーバに配置され、それらサーバでユーザプログラムが起動されると、通信ライブラリが初期化される。初期化時にはサーバ間で通信が行われることがある。プロセス配置情報の少なくとも一部を、ジョブスケジューラ300から受信する代わりに、サーバ間の通信によって収集してもよい。また、コレクティブ通信の手順を、通信ライブラリの初期化時に行う代わりに、ユーザプログラムからコレクティブ通信を最初に要求されたときに行ってもよい。

0139

ここで決定される通信手順は、ランク0のプロセスを基点とするものである。ランク0以外の特定のプロセスがReduce結果を使用する場合、ランク0のプロセスからデータを取得すればよい。また、ランク0以外のプロセスがもつデータをブロードキャストする場合、ランク0のプロセスにデータを渡せばよい。ただし、ランク0以外のプロセスを基点とするコレクティブ通信の手順を決定することも可能である。また、通信手順決定部171が生成する通信手順情報は、ジョブに含まれる全てのプロセスの間の通信手順を示す。複数のサーバは、同一のプロセス配置情報と同一のコレクティブ通信アルゴリズムを使用すれば、同一の通信手順情報を生成することになる。ただし、生成する通信手順情報を、サーバ100の通信手順のみを示すようにしてもよい。

0140

通信手順記憶部172は、通信手順決定部171が生成した通信手順情報を記憶する。通信手順情報は、コレクティブ通信の各フェーズにおいて、データを送信する際の送信先プロセスのランクと、データを受信する際の送信元プロセスのランクとを示す。

0141

コレクティブ通信実行部173は、コレクティブ通信を開始する命令をユーザプログラムが呼び出すと、通信手順記憶部172に記憶された通信手順情報に基づいてコレクティブ通信を実行する。コレクティブ通信実行部173は、通信手順情報が示す複数のフェーズを1つずつ実行する。あるフェーズで送信元プロセスが指定されている場合、コレクティブ通信実行部173は、送信元プロセスからデータを受信する。あるフェーズで送信先プロセスが指定されている場合、コレクティブ通信実行部173は、保持しているデータをコピーして送信先プロセスに送信する。コレクティブ通信をパイプライン方式で行う場合、コレクティブ通信実行部173は、全てのブロックの転送が完了するまで、複数のフェーズ(例えば、カラー0フェーズとカラー1フェーズ)を交互に実行する。

0142

データ送信では、コレクティブ通信実行部173は、送信先プロセスが配置されたサーバのアドレスとデータ本体とを含むパケットを生成し、HCA157を介してLeafスイッチ200にパケットを出力する。各プロセスが配置されたサーバのアドレスは、通信ライブラリの初期化時に把握される。

0143

第2の実施の形態では、コレクティブ通信はTwoTreeアルゴリズムに従って実行される。そこで、コレクティブ通信実行部173は、データ集合を2つに分割して管理する。2つのデータ部分集合のサイズは、できる限り均等であることが好ましい。データ集合が複数のレコードを含む場合、それら複数のレコードが2つに分割される。コレクティブ通信をパイプライン方式で行う場合、2つの部分木に対応する2つのデータ部分集合がそれぞれ複数のブロックに更に分割される。コレクティブ通信実行部173は、各ブロックにブロック番号を付して複数のブロックを管理するようにしてもよい。

0144

Reduce通信の場合、コレクティブ通信実行部173は、グループ内通信およびグループ間通信のフェーズ毎に、高々1つのサーバからデータを受信し、高々1つのサーバにデータを送信する。一方の部分木に従って集約されるデータはデータ集合の前半に対応し、他方の部分木に従って集約されるデータはデータ集合の後半に対応する。ブロードキャスト通信の場合、コレクティブ通信実行部173は、グループ内通信およびグループ間通信のフェーズ毎に、高々1つのサーバからデータを受信し、高々1つのサーバにデータを送信する。一方の部分木に従ってコピーされるデータはデータ集合の前半に対応し、他方の部分木に従ってコピーされるデータはデータ集合の後半に対応する。

0145

ジョブスケジューラ300は、プロセス配置決定部371を有する。プロセス配置決定部371は、例えば、CPUが実行するプログラムを用いて実現される。
プロセス配置決定部371は、ユーザからジョブ要求を受け付け、受け付けたジョブ要求に応じてジョブに含まれる複数のプロセスの配置を決定する。起動するプロセスの数は、ユーザからのジョブ要求で指定される。第2の実施の形態では、プロセス配置決定部371は、同一のジョブに属する複数のプロセスが、できる限り2以上のグループに均等に配置されるようにプロセス配置を決定する。プロセス配置決定部371は、決定したプロセス配置に関するプロセス配置情報を、ジョブで使用するサーバに送信する。

0146

図17は、通信手順テーブルの例を示す図である。
送信手順テーブル174,175および受信手順テーブル176,177は、通信手順決定部171により生成されて通信手順記憶部172に格納される。送信手順テーブル174および受信手順テーブル176は、ローカルTwoTreeに基づくReduce通信の手順を示している。送信手順テーブル175および受信手順テーブル177は、グローバルTwoTreeに基づくReduce通信の手順を示している。

0147

送信手順テーブル174は、複数のランクそれぞれに対応付けて、カラー0フェーズで当該ランクのプロセスがデータを送信する際の送信先プロセスのランクと、カラー1フェーズで当該ランクのプロセスがデータを送信する際の送信先プロセスのランクとを含む。送信先プロセスが存在しない場合、すなわち、当該ランクのプロセスがデータを送信しない場合、「−1」などランクに使用されない所定の数値登録される。例えば、カラー0フェーズでランク1のプロセスがランク2のプロセスにデータを送信し、カラー1フェーズでランク1のプロセスがランク7のプロセスにデータを送信することが登録される。ただし、送信すべきデータが存在しない場合は実際にはデータ通信が行われない。

0148

送信手順テーブル175は、複数の代表プロセスのランクそれぞれに対応付けて、カラー0フェーズの送信先プロセスのランクと、カラー1フェーズの送信先プロセスのランクとを含む。例えば、カラー0フェーズでランク8のプロセスがランク24のプロセスにデータを送信し、カラー1フェーズでランク8のプロセスがランク16のプロセスにデータを送信することが登録される。送信手順テーブル174がグループ内通信を表しているのに対し、送信手順テーブル175はグループ間通信を表している。

0149

受信手順テーブル176は、複数のランクそれぞれに対応付けて、カラー0フェーズで当該ランクのプロセスがデータを受信する際の送信元プロセスのランクと、カラー1フェーズで当該ランクのプロセスがデータを受信する際の送信元プロセスのランクとを含む。送信元プロセスが存在しない場合、すなわち、当該ランクのプロセスがデータを受信しない場合、「−1」などランクに使用されない所定の数値が登録される。例えば、カラー0フェーズでランク0のプロセスがランク5のプロセスからデータを受信し、カラー1フェーズでランク0のプロセスがランク4のプロセスからデータを受信することが登録される。ただし、受信すべきデータが存在しない場合は実際にはデータ通信が行われない。

0150

受信手順テーブル177は、複数の代表プロセスのランクそれぞれに対応付けて、カラー0フェーズの送信元プロセスのランクと、カラー1フェーズの送信元プロセスのランクとを含む。例えば、カラー0フェーズでランク0のプロセスがランク16のプロセスからデータを受信し、カラー1フェーズでランク0のプロセスがランク24のプロセスからデータを受信することが登録される。受信手順テーブル176がグループ内通信を表しているのに対し、受信手順テーブル177はグループ間通信を表している。

0151

Reduce通信を行う場合、各サーバは、送信手順テーブル174から相手ランクを読み出してデータ送信を制御し、受信手順テーブル176から相手ランクを読み出してデータ受信を制御する。その後、配置されたプロセスのランクが送信手順テーブル175および受信手順テーブル177に登録されているサーバは、送信手順テーブル175から相手ランクを読み出してデータ送信を制御し、受信手順テーブル177から相手ランクを読み出してデータ受信を制御する。パイプライン方式の場合、各サーバは、カラー0フェーズとカラー1フェーズを交互に実行することになる。例えば、カラー0フェーズから先に実行される。ただし、カラー1フェーズから先に実行してもよい。

0152

ブロードキャスト通信を行う場合、送信と受信の役割がReduce通信とは逆になる。よって、送信手順テーブル174,175の送信先プロセスがブロードキャスト通信における送信元プロセスと解釈され、受信手順テーブル176,177の送信元プロセスがブロードキャスト通信における送信先プロセスと解釈される。

0153

そこで、配置されたプロセスのランクが送信手順テーブル175および受信手順テーブル177に登録されているサーバは、受信手順テーブル177から相手ランクを読み出してデータ送信を制御し、送信手順テーブル175から相手ランクを読み出してデータ受信を制御する。その後、各サーバは、受信手順テーブル176から相手ランクを読み出してデータ送信を制御し、送信手順テーブル174から相手ランクを読み出してデータ受信を制御する。パイプライン方式の場合、各サーバは、カラー0フェーズとカラー1フェーズを交互に実行することになる。例えば、カラー0フェーズから先に実行される。ただし、カラー1フェーズから先に実行してもよい。

0154

次に、サーバ100の処理手順について説明する。
図18は、通信手順決定の処理例を示すフローチャートである。
(S30)プロセス配置決定部371は、ジョブに対して使用するグループの数を決定する。具体的には、プロセス配置決定部371は、ジョブに含まれるプロセスの数(全プロセス数)を、グループa,b,c,dそれぞれに含まれるサーバの数(グループノード数)で割ることで、使用するグループの数(グループ数)を算出する。ここでは小数点以下は切り上げる。例えば、第2の実施の形態ではグループノード数が9であるため、全プロセス数が32である場合、グループ数は32÷9=4と算出される。

0155

(S31)プロセス配置決定部371は、全プロセス数を、ステップS30で算出したグループ数で割ることで、各グループに配置されるプロセスの数(ローカルプロセス数)を算出する。例えば、全プロセス数が32である場合、32÷4=8と算出される。

0156

プロセス配置決定部371は、ステップS30で算出した個数のグループそれぞれに対して、グループ内ではランクが連続するようにローカルプロセス数だけプロセスを配置する。例えば、グループaにランク0,1,2,3,4,5,6,7が割り当てられる。グループbにランク8,9,10,11,12,13,14,15が割り当てられる。グループcにランク16,17,18,19,20,21,22,23が割り当てられる。グループdにランク24,25,26,27,28,29,30,31が割り当てられる。

0157

(S32)プロセス配置決定部371は、プロセスが配置されるサーバそれぞれに対して、決定したプロセス配置に関するプロセス配置情報を通知する。なお、プロセス配置情報は、グループ数、ローカルプロセス数、全体のプロセス数などを含んでもよい。また、各サーバとジョブスケジューラ300とがプロセス配置アルゴリズムについて事前に合意している場合、ステップS30,S31をサーバ100で実行してもよい。

0158

(S33)通信手順決定部171は、ランク0のプロセスを全体のルートに設定する。
(S34)通信手順決定部171は、ランク0からランクがローカルプロセス数−1までのプロセスの間で、ローカルTwoTreeを生成する。具体的には、通信手順決定部171は、ランク1からランクがローカルプロセス数−1までのプロセスの間で、ランク番号順にインオーダで配置した二分木になるように左部分木を生成する。通信手順決定部171は、左部分木のランクを1つだけ巡回シフトすることで右部分木を生成する。通信手順決定部171は、左部分木と右部分木をランク0のプロセスに連結することでローカルTwoTreeとする。これにより、例えば、図14の1番目のローカルTwoTreeが生成される。

0159

(S35)通信手順決定部171は、グループ数が1であるか、すなわち、ジョブに含まれる全てのプロセスが単一グループに閉じているか判断する。グループ数が1である場合はステップS39に進み、グループ数が2以上である場合はステップS36に進む。なお、グループ数が1である場合はグローバルTwoTreeは生成されない。

0160

(S36)通信手順決定部171は、ステップS34で生成したローカルTwoTreeのランクに所定のオフセットを加えて、残りのグループのローカルTwoTreeを生成する。オフセットは、ローカルプロセス数の整数倍である。例えば、図14の1番目のローカルTwoTreeのランクに8を加えることで、2番目のローカルTwoTreeが生成される。また、1番目のローカルTwoTreeのランクに16を加えることで、3番目のローカルTwoTreeが生成される。また、1番目のローカルTwoTreeのランクに24を加えることで、4番目のローカルTwoTreeが生成される。

0161

(S37)通信手順決定部171は、ステップS34,S36で生成されたローカルTwoTreeそれぞれのルートに位置するプロセスを代表プロセスとして選択する。
(S38)通信手順決定部171は、ステップS37で選択した複数の代表プロセスの間でグローバルTwoTreeを生成する。具体的には、通信手順決定部171は、複数の代表プロセスの間で、ランク番号順にインオーダで配置した二分木になるように左部分木を生成する。通信手順決定部171は、左部分木のランクを巡回シフトすることで右部分木を生成する。この巡回シフトでは、最大ランク以外のプロセスについては、ランクを代表プロセスの中で1つ大きいランクに変更し、最大ランクのプロセスについては、ランクを代表プロセスの中でランク0の次に小さいランクに変更する。通信手順決定部171は、左部分木と右部分木をランク0のプロセスに連結することでグローバルTwoTreeとする。これにより、例えば、図15のグローバルTwoTreeが生成される。

0162

(S39)通信手順決定部171は、ステップS34,S36で生成されたローカルTwoTreeに従って、グループ内のReduce通信の手順を決定する。また、グローバルTwoTreeが生成されている場合、通信手順決定部171は、ステップS38で生成されたグローバルTwoTreeに従って、グループ間のReduce通信の手順を決定する。通信手順決定部171は、決定した通信手順に基づいて、送信手順テーブル174,175および受信手順テーブル176,177を生成し、通信手順記憶部172に格納する。

0163

図19は、コレクティブ通信の処理例を示すフローチャートである。
(S40)コレクティブ通信実行部173は、ユーザプログラムからコレクティブ通信が指示されると、送信手順テーブル174,175と受信手順テーブル176,177を取得する。ユーザプログラムからのコレクティブ通信の指示は、Reduce通信の指示、ブロードキャスト通信の指示またはAllreduce通信の指示である。

0164

(S41)コレクティブ通信実行部173は、次のフェーズを選択する。例えば、コレクティブ通信実行部173は、カラー0フェーズとカラー1フェーズを交互に選択する。初回は、例えば、カラー0フェーズが選択される。

0165

(S42)コレクティブ通信実行部173は、データ受信に関して、ステップS41で選択したフェーズとサーバ100に配置されたプロセスのランクとの組に対応する数値を読み出す。Reduce通信の場合、コレクティブ通信実行部173は、最初は受信手順テーブル176から数値を読み出し、グループ内通信が完了した後は受信手順テーブル177から数値を読み出す。ブロードキャスト通信の場合、コレクティブ通信実行部173は、最初は送信手順テーブル175から数値を読み出し、グループ間通信が完了した後は送信手順テーブル174から数値を読み出す。コレクティブ通信実行部173は、読み出した数値が送信元ランクを表しているか、すなわち、該当する送信元ランクが登録されているか判断する。読み出した数値が「−1」である場合、送信元ランクが登録されていないことになる。送信元ランクが登録されている場合はステップS43に進み、送信元ランクが登録されていない場合はステップS44に進む。

0166

(S43)コレクティブ通信実行部173は、送信元ランクが示す相手プロセスからデータを受信できるように待機し、データを受信する。例えば、コレクティブ通信実行部173は、相手プロセスに対応する受信バッファを定期的に確認し、受信バッファにデータが到着している場合には到着したデータを取り出す。データ受信は、以下のステップS44,S45と並列に実行でき、ステップS46までに実行されればよい。コレクティブ通信実行部173は、受信したデータを保持しておく。

0167

(S44)コレクティブ通信実行部173は、データ送信に関して、ステップS41で選択したフェーズとサーバ100に配置されたプロセスのランクとの組に対応する数値を読み出す。Reduce通信の場合、コレクティブ通信実行部173は、最初は送信手順テーブル174から数値を読み出し、グループ内通信が完了した後は送信手順テーブル175から数値を読み出す。ブロードキャスト通信の場合、コレクティブ通信実行部173は、受信手順テーブル177から数値を読み出し、グループ間通信が完了した後は受信手順テーブル176から数値を読み出す。コレクティブ通信実行部173は、読み出した数値が送信先ランクを表しているか、すなわち、該当する送信先ランクが登録されているか判断する。読み出した数値が「−1」である場合、送信先ランクが登録されていないことになる。送信先ランクが登録されている場合はステップS45に進み、送信先ランクが登録されていない場合はステップS46に進む。

0168

(S45)コレクティブ通信実行部173は、送信先ランクが示す相手プロセスにデータを送信する。送信データはパケットに分割され、各パケットには相手プロセスが配置されたサーバのアドレスが付加される。アドレスはノードIDを兼ねることがある。データ集合は、左部分木に対応するデータ部分集合と右部分木に対応するデータ部分集合の2つに分割されて管理される。パイプライン方式の場合、2つのデータ部分集合それぞれが複数のブロックに分割されて管理される。送信するデータは、サーバ100が生成したデータを含むこともあるし、他のサーバから受信したデータを含むこともある。

0169

(S46)コレクティブ通信実行部173は、サーバ100が転送すべきデータの全ての転送が完了したか判断する。全てのデータの転送が完了した場合はコレクティブ通信を終了し、未転送のデータがある場合はステップS41に戻る。

0170

なお、第2の実施の形態では、接続されているSpineスイッチが同一である複数のLeafスイッチおよびそれら複数のLeafスイッチの配下のサーバから、1つのグループを形成した。これに対して、1つのLeafスイッチおよび当該Leafスイッチの配下のサーバから、1つのグループを形成することもできる。

0171

この場合、Leafスイッチ毎に1つの代表プロセスが選択される。グループ間通信については、複数のLeafスイッチに対応する複数の代表プロセスの間でグローバルTwoTreeが形成される。グループ内通信については、各Leafスイッチの配下にある複数のプロセスの間でローカルTwoTreeが形成される。例えば、図2,3の多層フルメッシュシステムでは12個のグループが形成される。このようにサーバをグループ化しても、複数のLeafスイッチの間のグループ間通信では通信競合が生じない。また、Leafスイッチ配下のグループ内通信でも通信競合が生じない。

0172

また、第2の実施の形態では二段階でコレクティブ通信を行ったが、グループを階層化して三段階でコレクティブ通信を行ってもよい。接続されているSpineスイッチが同一である複数のLeafスイッチおよびそれら複数のLeafスイッチの配下のサーバから、1つの大グループを形成する。また、1つのLeafスイッチおよび当該Leafスイッチの配下のサーバから、1つの小グループを形成する。

0173

この場合、大グループ毎に上位代表プロセスが選択され、更にLeafスイッチ毎に下位代表プロセスが選択される。第1階層として、複数の大グループに対応する複数の上位代表プロセスの間で上位グローバルTwoTreeが形成される。第2階層として、複数のLeafスイッチに対応する複数の下位代表プロセスの間で下位グローバルTwoTreeが形成される。第3階層として、各Leafスイッチの配下にある複数のプロセスの間でローカルTwoTreeが形成される。例えば、図2,3の多層フルメッシュシステムでは、4個の大グループと12個の小グループが形成される。サーバが多い場合、このようにLeafスイッチ単位でグループを形成することも有用である。

0174

第2の実施の形態の多層フルメッシュシステムによれば、多層フルメッシュトポロジが採用される。多層フルメッシュトポロジでは、上位の通信装置が冗長化され、下位の通信装置の間の通信経路が冗長化される。よって、トラフィックの混雑を抑制することができる。また、単純なFatTreeトポロジと比べて通信装置の個数を削減でき、システム構築コストを削減できる。また、第2の実施の形態の多層フルメッシュシステムによれば、TwoTreeに従い、リンクの空き通信帯域が減少するようにコレクティブ通信が実行される。よって、コレクティブ通信を高速に実行できる。

0175

また、接続されているSpineスイッチの集合が同一であるLeafスイッチおよびその配下のノードがグループ化され、各グループから代表ノードが選択される。そして、コレクティブ通信が、代表ノード間のデータ送信と代表ノードを基点とするグループ内のデータ送信の二段階に分離されて実行される。ここで、複数のグループの間にはフルメッシュの通信経路が存在するため、通信に参加するノードがグループ毎に1つであれば、複数のノードが並列通信を行っても通信競合は生じない。また、グループ内のネットワークトポロジはFatTreeに相当するため、グループ内のノード同士の閉じた通信であれば、複数のノードが並列通信を行っても通信競合を回避できる。よって、通信競合を抑制でき、通信遅延を抑制してコレクティブ通信の所要時間を短縮できる。

0176

10情報処理装置
11,12,13,14,15,16,17,18ノード
21,22,23,24,25,26,27,28中継装置
31,32グループ
33,34ノード間通信
35,36,37,38 ツリー

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

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

関連する公募課題

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

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

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

関連性が強い人物一覧

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

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

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

関連する公募課題一覧

astavision 新着記事

サイト情報について

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

主たる情報の出典

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