(57)【要約】      （修正有）【課題】フルメッシュシステムにおいてオールリデュース通信を行う場合に経路競合が発生することを回避する。【解決手段】本情報処理システムは、接続形態がフルメッシュである複数のスイッチと、複数のスイッチのいずれかにそれぞれ接続される複数の情報処理装置とを有する。そして、複数の情報処理装置の各々が、自情報処理装置に接続されるスイッチの識別子である第１の識別子と、自情報処理装置に割り当てられた一次独立な数の集合のうち通信フェーズに対応する数との排他的論理和により、第２の識別子を生成する生成部と、第２の識別子を有するスイッチに接続される情報処理装置との通信を行う第１通信部とを有する。【選択図】図２１
2019008648.tif 000002
【特許請求の範囲】
【請求項１】
接続形態がフルメッシュである複数のスイッチと、
前記複数のスイッチのいずれかにそれぞれ接続される複数の情報処理装置と、
を有し、
前記複数の情報処理装置の各々が、
自情報処理装置に接続されるスイッチの識別子である第１の識別子と、前記自情報処理装置に割り当てられた一次独立な数の集合のうち通信フェーズに対応する数との排他的論理和により、第２の識別子を生成する生成部と、
前記第２の識別子を有するスイッチに接続される情報処理装置との通信を行う第１通信部とを有する、
情報処理システム。
【請求項２】
前記複数のスイッチの台数は２k（ｋは自然数）であり、
前記複数のスイッチの各々には（２k−１）台の情報処理装置が接続される、
請求項１記載の情報処理システム。
【請求項３】
前記一次独立な数の集合は、一次独立なｋ個のｋ桁のビット列の集合であり、
前記複数のスイッチの各々の識別子はｋ桁のビット列であり、
前記複数のスイッチの各々に接続された（２k−１）台の情報処理装置が各通信フェーズで使用するビット列の集合は、１から（２k−１）までの１０進数に対応するビット列を含む、
請求項２記載の情報処理システム。
【請求項４】
前記複数の情報処理装置の各々が、
前記第１の識別子を有するスイッチに接続された他の情報処理装置との通信を行う第２通信部
をさらに有し、
前記第１通信部は、
前記第２の識別子を有するスイッチに接続される情報処理装置であって且つ前記自情報処理装置以外の情報処理装置が送信するデータを受信しない情報処理装置に対してデータを送信する、
請求項１乃至３のいずれか１つ記載の情報処理システム。
【請求項５】
接続形態がフルメッシュである複数のスイッチと、前記複数のスイッチのいずれかにそれぞれ接続される複数の情報処理装置とを有する情報処理システムにおいて実行される情報処理方法であって、
前記複数の情報処理装置の各々が、
自情報処理装置に接続されるスイッチの識別子である第１の識別子と、前記自情報処理装置に割り当てられた一次独立な数の集合のうち通信フェーズに対応する数との排他的論理和により、第２の識別子を生成し、
前記第２の識別子を有するスイッチに接続される情報処理装置との通信を行う、
処理を実行する情報処理方法。
【請求項６】
接続形態がフルメッシュである複数のスイッチと前記複数のスイッチのいずれかにそれぞれ接続される複数の情報処理装置とを含むフルメッシュシステムが複数のスパインスイッチにより複数連結された情報処理システムであって、
複数の前記フルメッシュシステムの各々における前記複数の情報処理装置の各々が、
自情報処理装置を収容する第１のリーフスイッチに接続されるスパインスイッチに接続され且つ前記第１のリーフスイッチが含まれるフルメッシュシステムとは異なるフルメッシュシステムに含まれる第２のリーフスイッチに接続される情報処理装置との通信を行う第１通信部と、
前記第１のリーフスイッチに収容される他の情報処理装置との通信を行う第２通信部と、
前記第１のリーフスイッチの識別子である第１の識別子と、前記自情報処理装置に割り当てられた一次独立な数の集合のうち通信フェーズに対応する数との排他的論理和により、第２の識別子を生成する生成部と、
前記第２の識別子を有し且つ前記自情報処理装置と同じフルメッシュシステムに含まれるリーフスイッチに収容される情報処理装置との通信を行う第３通信部とを有する、
情報処理システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、集団通信の技術に関する。
【背景技術】
【０００２】
並列計算機におけるサーバ及びスイッチの接続形態（すなわちネットワークトポロジ）の最適化により並列計算機内での通信を効率化すれば、並列計算機が実行する並列分散処理のスループットを高めることができる。また、並列計算機におけるネットワークトポロジの最適化により少数のスイッチで多数のサーバを接続することができれば、並列計算機の構築コストを抑えることができる。
【０００３】
ネットワーク内の各ノードが他のノードのいずれとも直接接続されたトポロジはフルメッシュトポロジと呼ばれる。或る文献は、各スイッチが他のスイッチの各々と直接接続された構造を採用するシステム（以下、フルメッシュシステムと呼ぶ）を開示する。また、上記文献は、複数のフルメッシュシステムがＳｐｉｎｅスイッチにより連結されたシステムを開示する。上記文献の技術によれば、フルメッシュシステムにおいて全対全（all-to-all）通信時の経路競合を回避することができる。ここで、経路競合とは、１つの経路の同一方向に同時に複数のパケットが送信されることを意味する。
【０００４】
但し、並列計算機においては、ジョブの種類によっては全対全通信以外の通信が行われる場合がある。全対全通信以外の通信としては、例えばオールリデュース通信が知られている。オールリデュース通信とは対象の全ノードが持つデータを用いて実行した演算の結果を対象の全ノードが持つための通信のことであり、オールリデュースとは、その演算のことである。上記文献に開示された技術は全対全通信を対象としており、オールリデュース通信の実行時の経路競合を回避することはできない。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０１５−２３２８７４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本発明の目的は、１つの側面では、フルメッシュシステムにおいてオールリデュース通信を行う場合に経路競合が発生することを回避するための技術を提供することである。
【課題を解決するための手段】
【０００７】
第１の態様に係る情報処理システムは、接続形態がフルメッシュである複数のスイッチと、複数のスイッチのいずれかにそれぞれ接続される複数の情報処理装置とを有する。そして、複数の情報処理装置の各々が、自情報処理装置に接続されるスイッチの識別子である第１の識別子と、自情報処理装置に割り当てられた一次独立な数の集合のうち通信フェーズに対応する数との排他的論理和により、第２の識別子を生成する生成部と、第２の識別子を有するスイッチに接続される情報処理装置との通信を行う第１通信部とを有する。
【０００８】
第２の態様に係る情報処理システムは、接続形態がフルメッシュである複数のスイッチと複数のスイッチのいずれかにそれぞれ接続される複数の情報処理装置とを含むフルメッシュシステムが複数のスパインスイッチにより複数連結された情報処理システムである。そして、複数のフルメッシュシステムの各々における複数の情報処理装置の各々が、自情報処理装置を収容する第１のリーフスイッチに接続されるスパインスイッチに接続され且つ第１のリーフスイッチが含まれるフルメッシュシステムとは異なるフルメッシュシステムに含まれる第２のリーフスイッチに接続される情報処理装置との通信を行う第１通信部と、第１のリーフスイッチに収容される他の情報処理装置との通信を行う第２通信部と、第１のリーフスイッチの識別子である第１の識別子と、自情報処理装置に割り当てられた一次独立な数の集合のうち通信フェーズに対応する数との排他的論理和により、第２の識別子を生成する生成部と、第２の識別子を有し且つ自情報処理装置と同じフルメッシュシステムに含まれるリーフスイッチに収容される情報処理装置との通信を行う第３通信部とを有する。
【発明の効果】
【０００９】
１つの側面では、フルメッシュシステムにおいてオールリデュース通信を行う場合に経路競合が発生することを回避できるようになる。
【図面の簡単な説明】
【００１０】
【図１】図１は、オールリデュース通信について説明するための図である。
【図２】図２は、オールリデュース通信について説明するための図である。
【図３】図３は、オールリデュース通信について説明するための図である。
【図４】図４は、オールリデュース通信について説明するための図である。
【図５】図５は、オールリデュース通信を一般的なツリー構造のトポロジにおいて実行した場合の経路競合を示す図である。
【図６】図６は、ファットツリー構造のトポロジにおいて実行した場合の経路競合を示す図である。
【図７】図７は、第１の実施の形態における単層フルメッシュシステムを示す図である。
【図８】図８は、インフィニバンドのネットワークにおけるルーティングについて説明するための図である。
【図９】図９は、第１の実施の形態における管理装置の機能ブロック図である。
【図１０】図１０は、第１の実施の形態におけるサーバの機能ブロック図である。
【図１１】図１１は、第１の実施の形態における管理装置が実行する処理の処理フローを示す図である。
【図１２】図１２は、第１生成処理の処理フローを示す図である。
【図１３】図１３は、スイッチ配下のサーバ間でのオールリデュースについて説明するための図である。
【図１４】図１４は、スイッチ配下のサーバ間でのオールリデュースについて説明するための図である。
【図１５】図１５は、スイッチ配下のサーバ間でのオールリデュースについて説明するための図である。
【図１６】図１６は、スイッチ配下のサーバ間でのオールリデュースについて説明するための図である。
【図１７】図１７は、スイッチ配下のサーバ間でのオールリデュースについて説明するための図である。
【図１８】図１８は、第１の通信表の一例を示す図である。
【図１９】図１９は、第２生成処理の処理フローを示す図である。
【図２０】図２０は、第２の通信表の一例を示す図である。
【図２１】図２１は、第２の通信表に従って行われる通信について説明するための図である。
【図２２】図２２は、第２の通信表に従って行われる通信について説明するための図である。
【図２３】図２３は、第１の実施の形態におけるサーバが実行する処理の処理フローを示す図である。
【図２４】図２４は、第１の実施の形態におけるサーバが実行する処理の処理フローを示す図である。
【図２５】図２５は、第２の実施の形態における多層フルメッシュシステムを示す図である。
【図２６】図２６は、第２の実施の形態における管理装置の機能ブロック図である。
【図２７】図２７は、第２の実施の形態におけるサーバの機能ブロック図である。
【図２８】図２８は、第２の実施の形態における管理装置が実行する処理の処理フローを示す図。
【図２９】図２９は、第３生成処理の処理フローを示す図である。
【図３０Ａ】図３０Ａは、第３の通信表に従って行われる通信について説明するための図である。
【図３０Ｂ】図３０Ｂは、第３の通信表に従って行われる通信について説明するための図である。
【図３０Ｃ】図３０Ｃは、第３の通信表に従って行われる通信について説明するための図である。
【図３１】図３１は、第４生成処理の処理フローを示す図である。
【図３２】図３２は、第５生成処理の処理フローを示す図である。
【図３３】図３３は、第２の実施の形態におけるサーバが実行する処理の処理フローを示す図である。
【図３４】図３４は、第２の実施の形態におけるサーバが実行する処理の処理フローを示す図である。
【図３５】図３５は、第２の実施の形態におけるサーバが実行する処理の処理フローを示す図である。
【図３６】図３６は、第３の実施の形態における単層フルメッシュシステムの一例を示す図である。
【図３７】図３７は、第３の実施の形態における第２通信表の一例を示す図である。
【図３８】図３８は、貪欲法のアルゴリズムの一例を示す図である。
【図３９】図３９は、コンピュータのハードウエア構成図である。
【図４０】図４０は、スイッチのハードウエア構成図である。
【発明を実施するための形態】
【００１１】
図１乃至図４は、オールリデュース通信について説明するための図である。図１においては、サーバｎ０が値「４」を持っており、サーバｎ１が値「８」を持っており、サーバｎ２が値「１」を持っており、サーバｎ３が値「５」を持っており、サーバｎ４が値「６」を持っており、サーバｎ５が値「３」を持っている。オールリデュースにおいて指定された演算が「加算」である場合、サーバｎ０乃至ｎ５はそれぞれ値「２７」を持つことになる。
【００１２】
図１の右側に示した状態を実現するためのオールリデュース通信は、例えば図２及び図３に示すように行われる。まず、図２（ａ）に示すように、サーバｎ０とサーバｎ３との間で値が共有されて加算により値「９」が算出され、サーバｎ１とサーバｎ４との間で値が共有されて加算により値「１４」が算出され、サーバｎ２とサーバｎ５との間で値が共有されて加算により値「４」が算出される。
【００１３】
そして、図２（ｂ）に示すように、サーバｎ０とサーバｎ１との間で値が共有されて加算により値「２３」が算出され、サーバｎ３とサーバｎ４との間で値が共有されて加算により値「２３」が算出される。
【００１４】
そして、図３（ａ）に示すように、サーバｎ１とサーバｎ２との間で値が共有されて加算により値「２７」が算出され、サーバｎ４とサーバｎ５との間で値が共有されて加算により値「２７」が算出される。
【００１５】
最後に、図３（ｂ）に示すように、サーバｎ１がサーバｎ０に値「２７」を送信し、サーバｎ４がサーバｎ３に値「２７」を送信する。これにより、図３（ｂ）に示すように、サーバｎ０乃至ｎ５が値「２７」を持つことができる。
【００１６】
ここで、対象はサーバｎ０乃至ｎ５の全てでなくてもよく、サーバｎ０乃至ｎ５のうち一部のサーバを対象としてもよい。一例として、サーバｎ０、ｎ１、ｎ３及びｎ４を対象とする場合のオールリデュース通信について説明する。まず、図４（ａ）に示すように、サーバｎ０とサーバｎ３との間で値が共有されて加算により値「９」が算出され、サーバｎ１とサーバｎ４との間で値が共有されて加算により値「１４」が算出される。
【００１７】
そして、図４（ｂ）に示すように、サーバｎ０とサーバｎ１との間で値が共有されて加算により値「２３」が算出され、サーバｎ３とサーバｎ４との間で値が共有されて加算により値「２３」が算出される。これにより、サーバｎ０、ｎ１、ｎ３及びｎ４が値「２３」を持つことができる。
【００１８】
第１の実施の形態においては、このようなオールリデュース通信を単層フルメッシュシステムにおいて実行する場合に経路競合が発生しないようにすることを考える。上で述べたように、経路競合とは、１つの経路の同一方向に同時に複数のパケットが送信されることを意味し、経路競合の発生により通信時間が長くなる。例として、図５に、オールリデュース通信を一般的なツリー構造のトポロジにおいて実行した場合の経路競合を示す。図５において、丸の図形はサーバを表し、ハッチングされていない正方形の図形はＬｅａｆスイッチを表し、ハッチングされた正方形の図形はＳｐｉｎｅスイッチを表す。図５において、経路Ｒ１において経路競合が発生し、経路Ｒ２においても経路競合が発生する。このケースにおいては、例えば図６に示すように、ツリー構造をファットツリー構造に変えることで経路競合を回避することが可能であるが、ファットツリー構造を採用すると総スイッチ数は図５の例よりも多くなる。
【００１９】
図７は、第１の実施の形態における単層フルメッシュシステム１０００を示す図である。本実施の形態の単層フルメッシュシステム１０００は、例えばインフィニバンドスイッチ等である４つのスイッチがフルメッシュトポロジで接続される。各スイッチは２桁のビット列である識別子ｓを有し、各スイッチの識別子ｓは他のスイッチが有する識別子ｓのいずれとも異なる。具体的には、スイッチ００と、スイッチ０１と、スイッチ１０と、スイッチ１１とが存在する。
【００２０】
スイッチ００は、スイッチ０１、スイッチ１０及びスイッチ１１に直接接続される。スイッチ０１は、スイッチ００、スイッチ１０及びスイッチ１１に直接接続される。スイッチ１０は、スイッチ００、スイッチ０１及びスイッチ１１に直接接続される。スイッチ１１は、スイッチ００、スイッチ０１及びスイッチ１０に直接接続される。
【００２１】
なお、図７の例においては４台のスイッチにより角の数が４である多角形のトポロジが形成されているが、スイッチの数が２k（ｋは２以上の自然数）であって且つ角の数が２kである多角形のトポロジがスイッチにより形成されていれば、本実施の形態を適用可能である。
【００２２】
各スイッチには（２k−１）台のサーバが接続される。図７の例においてはｋ＝２であるので、３（＝２2−１）台のサーバが各スイッチに接続される。単層フルメッシュシステム１０００における各サーバは、例えばＭＰＩ（Message Passing Interface）等の通信ライブラリを使用して通信を行う情報処理装置である。単層フルメッシュシステム１０００の１２台のサーバにより並列計算が実現される。以下では、各スイッチに接続されるサーバの台数をｄとする。図７の例においてはｄ＝３である。
【００２３】
本実施の形態においては、経路競合を回避するため、規則的且つ固定的なルーティングが行われるインフィニバンドのネットワークが利用される。図８を用いて、インフィニバンドのネットワークにおけるルーティングについて説明する。図８において、丸の図形はサーバを表し、正方形の図形はスイッチを表す。線分はインフィニバンドのリンクを表し、線分の傍にある文字列は宛先のサーバの識別情報を表す。太い実線の矢印は通信経路を表す。
【００２４】
図８の例においては、サーバＮ３が、宛先がサーバＮ１であるパケットを送信する。パケットのヘッダには、宛先の識別情報（例えばＬＩＤ（Local IDentifier））が含まれる。各スイッチにおける各出力ポートには宛先のサーバの識別情報が対応付けられているので、各スイッチは、パケットに含まれる宛先の識別情報に対応する出力ポートにパケットを出力する。図８の例では、パケットはスイッチＳＷ１、スイッチＳＷ２及びスイッチＳＷ４を経由してサーバＮ１に到達する。
【００２５】
すなわち、本実施の形態のネットワークは、イーサネット（登録商標）のように自動的に経路が決定されるネットワークではなく、規則的且つ固定的なルーティングが行われるネットワークである。
【００２６】
なお、上記の識別情報とは別に、各サーバには番号が割り振られているとする。具体的には、各スイッチ配下の３台の各サーバには、０から２までのいずれかの番号が割り当てられ、各スイッチには「０」が割り振られたサーバと「１」が割り振られたサーバと「２」が割り振られたサーバとが接続される。これらの番号は、オールリデュースにおける通信先の特定に使用される。
【００２７】
図９に示すように、単層フルメッシュシステム１０００は管理装置３に管理ＬＡＮ（Local Area Network）等で接続され、単層フルメッシュシステム１０００における通信は管理装置３により管理される。管理装置３は、通信表生成部３０１と、通信表格納部３０３と、トポロジデータ格納部３０５とを有する。通信表生成部３０１は、例えば、図３９におけるメモリ２５０１にロードされたプログラムがＣＰＵ（Central Processing Unit）２５０３に実行されることで実現される。通信表格納部３０３及びトポロジデータ格納部３０５は、例えば、図３９におけるメモリ２５０１又はＨＤＤ（Hard Disk Drive）２５０５に設けられる。
【００２８】
通信表生成部３０１は、トポロジデータ格納部３０５に格納されている、単層フルメッシュシステム１０００のネットワークトポロジの情報に基づき、第１の通信表及び第２の通信表を生成し、生成された第１の通信表及び第２の通信表を通信表格納部３０３に格納する。通信表生成部３０１は、通信表格納部３０３に格納された第１の通信表及び第２の通信表を、所定のタイミングで又はリクエストに応じて、単層フルメッシュシステム１０００における各サーバに送信する。
【００２９】
図１０は、サーバの機能ブロック図である。サーバは、処理部１０１と、通信表格納部１０３と、ビット列生成部１０５とを有する。処理部１０１は、第１通信部１０１１と、第２通信部１０１３とを有する。処理部１０１及びビット列生成部１０５は、例えば、図３９におけるメモリ２５０１にロードされたプログラムがＣＰＵ２５０３に実行されることで実現される。通信表格納部１０３は、例えば、図３９におけるメモリ２５０１又はＨＤＤ２５０５に設けられる。
【００３０】
通信表格納部１０３には、管理装置３から受信した第１の通信表及び第２の通信表が格納される。ビット列生成部１０５は、通信表格納部１０３に格納された第２の通信表に基づきビット列を生成する。処理部１０１における第１通信部１０１１は、通信表格納部１０３に格納された第１の通信表に従って通信を行う。処理部１０１における第２通信部１０１３は、ビット列生成部１０５により生成されたビット列に基づき通信を行う。
【００３１】
次に、図１１乃至図２２を用いて、管理装置３が実行する処理について説明する。
【００３２】
図１１は、管理装置３が実行する処理の処理フローを示す図である。
【００３３】
管理装置３における通信表生成部３０１は、単層フルメッシュシステム１０００のネットワークトポロジの情報をトポロジデータ格納部３０５から読み出す（図１１：ステップＳ１）。ネットワークトポロジの情報は、例えば、スイッチとサーバとの接続関係の情報等を含む。
【００３４】
通信表生成部３０１は、ステップＳ１において読み出したネットワークトポロジの情報に基づき、第１の通信表を生成する処理である第１生成処理を実行する（ステップＳ３）。
【００３５】
図１２乃至図１８を用いて、第１生成処理について説明する。図１２は、第１生成処理の処理フローを示す図である。
【００３６】
通信表生成部３０１は、単層フルメッシュシステム１０００における各スイッチ配下でのオールリデュースの各フェーズにおいて通信を実行するサーバの識別情報を含む第１の通信表を生成する（図１２：ステップＳ１１）。
【００３７】
図１３乃至図１７は、単層フルメッシュシステム１０００における各スイッチ配下のサーバ間でのオールリデュースについて説明するための図である。図１３乃至図１７において、正方形の図形はスイッチを表し、丸の図形はサーバを表し、スイッチとサーバとを結ぶ線分はリンクを表す。サーバに付された数字はサーバが持つ値を表す。
【００３８】
まず、図１３及び図１４を用いて、スイッチ配下のサーバの数が偶数（ここでは、２の冪である４）である場合について説明する。
【００３９】
例えば、図１３（ａ）に示すように、４台のサーバがそれぞれ「３」、「７」、「８」、「５」を持つとする。この場合、２台のサーバを含むペアの各々において値が共有され、値の演算（ここでは加算）が行われる。ここでは、１つの経路の同一方向に同時に複数のパケットが送信されることはないので、経路競合は発生しない。
【００４０】
すると、図１３（ｂ）に示すように、２台のサーバが値「１０」を持ち、残りの２台のサーバが値「１３」を持つ。そして、値「１０」を持つサーバと値「１３」を持つサーバとを含むペアの各々において値が共有され、値の演算（ここでは加算）が行われる。ここでは、１つの経路の同一方向に同時に複数のパケットが送信されることはないので、経路競合は発生しない。
【００４１】
これにより、最終的には図１４に示すように各サーバが値「２３」を持つ。
【００４２】
次に、図１５乃至図１７を用いて、スイッチ配下のサーバの数が奇数（ここでは５）である場合について説明する。
【００４３】
例えば、図１５（ａ）に示すように、５台のサーバがそれぞれ「１」、「４」、「５」、「２」、「８」を持つとする。この場合、５台のうち２台のサーバにおいて値が共有され、値の演算（ここでは加算）が行われる。ここでは、１つの経路の同一方向に同時に複数のパケットが送信されることはないので、経路競合は発生しない。
【００４４】
すると、図１５（ｂ）に示すように、５台のサーバがそれぞれ「１」、「４」、「５」、「１０」、「１０」を持つ。そして、値「１」を持つサーバと値「４」を持つサーバとの間で値が共有され値の演算が行われ、値「５」を持つサーバと値「１０」を持つサーバとの間で値が共有され値の演算が行われる。ここでは、１つの経路の同一方向に同時に複数のパケットが送信されることはないので、経路競合は発生しない。
【００４５】
すると、図１６（ａ）に示すように、５台のサーバがそれぞれ「５」、「５」、「１５」、「１５」、「１０」を持つ。そして、値「５」を持つサーバと値「１５」を持つサーバとの間で値が共有され値の演算が行われ、値「５」を持つサーバと値「１５」を持つサーバとの間で値が共有され値の演算が行われる。ここでは、１つの経路の同一方向に同時に複数のパケットが送信されることはないので、経路競合は発生しない。
【００４６】
すると、図１６（ｂ）に示すように、５台のサーバがそれぞれ「２０」、「２０」、「２０」、「２０」、「１０」を持つ。そして、値「２０」を持つサーバが値「１０」を持つサーバに対して値「２０」を通知する。ここでは、１つの経路の同一方向に同時に複数のパケットが送信されることはないので、経路競合は発生しない。
【００４７】
すると、図１７に示すように、最終的に５台のサーバがそれぞれ値「２０」を持つようになる。
【００４８】
以上の説明は複数のサーバの間で行われるオールリデュースの一例についての説明であるが、サーバ数がこの例以外の数である場合においても、基本的には同様の方法でオールリデュースを行うことができる。
【００４９】
ここで、ｎ台（ｎは自然数）のサーバの間でのオールリデュースを行う場合における通信表を生成する処理（以下、Ａｌｌｒｅｄｕｃｅ（ｎ）のように呼ぶ）について説明する。本実施の形態においては、再帰的な処理によって通信表が生成される。
【００５０】
（１）スイッチ配下のサーバの数ｎが１である場合、処理は終了する。
【００５１】
（２）スイッチ配下のサーバの数ｎが２である場合、２台のサーバの間での通信についての通信情報（具体的には、サーバのペアの情報）が通信表に書き込まれる。
【００５２】
（３）スイッチ配下のサーバの数ｎが奇数２ｍ＋１（ｍは自然数）である場合、ｎ台のサーバのうち２台のサーバ（サーバＰおよびサーバＱ）が選択され、サーバＰとサーバＱとの間でオールリデュース通信についての通信情報が通信表に書き込まれる。そして、サーバＰ及びサーバＱのうちいずれかのサーバと残りの（２ｍ−１）台のサーバと（つまり、２ｍ台のサーバ）について、Ａｌｌｒｅｄｕｃｅ（２ｍ）が呼び出される。そして、Ａｌｌｒｅｄｕｃｅ（２ｍ）の結果をサーバＰからサーバＱに伝えるための通信情報が通信表に書き込まれる。
【００５３】
（４）スイッチ配下のサーバの数が２ｍ（ｍは２以上の自然数）である場合、スイッチはｍ台のグループとｍ台のグループとに分けられ、同時並行でそれぞれのグループについてＡｌｌｒｅｄｕｃｅ（ｍ）が呼び出される。
【００５４】
以上のような処理を実行すれば、ｎ台のサーバの間でのオールリデュースを行う場合における通信表が生成される。図１３乃至図１７の説明から明らかなように、このような方法で生成された通信表に従ってオールリデュース通信が行われれば経路競合は発生しない。
【００５５】
図１２の説明に戻り、通信表生成部３０１は、ステップＳ１１において生成された第１の通信表を通信表格納部３０３に格納する（ステップＳ１３）。そして処理は呼び出し元に戻る。
【００５６】
図１８は、第１の通信表の一例を示す図である。図１８の例においては、フェーズ番号と、通信を実行するサーバのペアの情報とが第１の通信表に登録されている。Ｎ１等の文字列はサーバの識別情報（例えばＬＩＤ）を表す。通信１と通信２とは同時並行で実行される。例えばフェーズ１においては、サーバＮ１とサーバＮ２との間の通信と、サーバＮ３とサーバＮ４との間の通信とが同時並行で実行される。図１８に示した通信表によれば、フェーズ０乃至３における各サーバの通信相手は以下のとおりである。
【００５７】
サーバＮ１：−，Ｎ２，Ｎ３，−
サーバＮ２：−，Ｎ１，Ｎ４，−
サーバＮ３：−，Ｎ４，Ｎ１，−
サーバＮ４：Ｎ５，Ｎ３，Ｎ２，Ｎ５（送）
サーバＮ５：Ｎ４，−，−，Ｎ４（受）
【００５８】
ここで、「−」は通信が行われないことを表す。「（送）」は送信することを表し、「（受）」は受信することを表す。例えばサーバＮ５は、フェーズ０においてサーバＮ４と通信し、フェーズ１及び２においては通信を行わず、フェーズ３においてはサーバＮ４からデータを受信する。なお、説明を簡単にするため図１８には１台のスイッチにおけるオールリデュースについての通信情報が登録されているが、実際には各スイッチにおけるオールリデュースについての通信情報が登録される。
【００５９】
図１１の説明に戻り、通信表生成部３０１は、ステップＳ１において読み出されたネットワークトポロジの情報に基づき、第２の通信表を生成する処理である第２生成処理を実行する（ステップＳ５）。
【００６０】
図１９乃至図２２を用いて、第２生成処理について説明する。図１９は、第２生成処理の処理フローを示す図である。
【００６１】
通信表生成部３０１は、同一番号が割り振られたサーバ間で行われるオールリデュースにおいて各サーバが各フェーズで送信するデータの送信先を特定するために使用されるビット列ａi,jを含む第２の通信表を生成する（図１９：ステップＳ２１）。ここで、ｉはフェーズ番号を表す変数であり、ｊはサーバに割り振られた番号を表す変数である。
【００６２】
上で述べたように、各スイッチは識別子ｓを有しており、本実施の形態においては、識別子ｓとａi,jとを用いて送信先のサーバが収容されたスイッチが特定される。具体的には、割り当てられた番号がｊであるサーバがフェーズｉにおいて行う通信の相手は、そのサーバが収容されたスイッチの識別子ｓと、ビット列ａi,jとを用いて、ｓ ｘｏｒ ａi,jにて生成されるビット列を識別子とするスイッチに収容され且つ割り当てられた番号がｊであるサーバである。
【００６３】
ａi,jは、以下のような特徴を有する。
【００６４】
（i）ａ1,j，ａ2,j，．．．，ａk,jは一次独立である。
（ii）ａi,1，ａi,2，．．．，ａi,d-1は｛１，２，３，．．．，２d−１｝の並び替えに相当する。
【００６５】
なお、ｋ桁のビット列の集合ｂ1，ｂ2，．．．，ｂkが一次独立であるとは、それらｋ個のビット列から１又は複数のビット列を選択して排他的論理和を計算すると、選択されるビット列の組合せに関わらず、計算結果は０ではないことを意味する。例えば、ビット列の集合００１，０１０，１００は一次独立であるが、ビット列の集合１０１０，１１１１，０１０１，１０１１は、最初の３つのビット列に対する排他的論理和の計算結果が０であるので、一次独立ではない。
【００６６】
一次独立なビット列の集合を生成する方法としては、１から（ｄ−１）までの１０進数に対応する（ｄ−１）個のｋ桁のビット列を、連続するｋ個のビット列をどのように選択したとしても選択されたｋ個のビット列が一次独立になるように円形に並べる円環方式が有る。この円環方式においては、例えば貪欲法（Greedy Algorithm）を利用することができる。また、数列からａi,jを生成する方法も有る。具体的には、ｉ行ｊ列の表を生成し、１行目には数列をそのまま配置し、２行目には数列を横に１つ分ずらした状態で配置し、３行目には数列を横に２つ分ずらした状態で配置し、．．．というように、ｋ行目まで処理を実行する。
【００６７】
図２０は、第２の通信表の一例を示す図である。図２０には、ｋ＝２の場合における第２の通信表の一例が示されている。第２の通信表はｋ行ｄ列であり、ｉはフェーズ番号を表し、ｊはサーバに割り当てられた番号を表す。１列目におけるビット列００とビット列１１との排他的論理和の計算結果は１１であるので、１列目におけるビット列００とビット列１１とは一次独立である。２列目におけるビット列１１とビット列１０との排他的論理和の計算結果は０１であるので、２列目におけるビット列１１とビット列１０とは一次独立である。３列目におけるビット列１０とビット列０１との排他的論理和の計算結果は１１であるので、３列目におけるビット列１０とビット列０１とは一次独立である。各列におけるビット列が一次独立であることは、オールリデュース通信が可能であることの要件である。また、各フェーズにおいて１から（ｄ−１）までの１０進数に対応するビット列が網羅されていることは、競合が発生しないことの要件である。
【００６８】
図２１及び図２２を用いて、第２の通信表に従って行われる通信について説明する。図２０の例においては、２フェーズの通信が行われ、フェーズ０は図２１の通信に対応し、フェーズ１は図２２の通信に対応する。図２１及び図２２において矢印は通信を表し、図２０におけるハッチングの種類と図２１及び図２２におけるハッチングの種類とは対応している。スイッチ内の数字列は識別子（すなわちビット列）を表し、サーバ内の番号はサーバに割り振られた番号である。
【００６９】
まず、フェーズ０の通信について説明する。スイッチ００の配下のサーバであって割り当てられた番号が０である場合、００と０１との排他的論理和の結果が０１であるので、スイッチ０１の配下のサーバであって割り当てられた番号が０であるサーバとの通信を行う。スイッチ００の配下のサーバであって割り当てられた番号が１である場合、００と１１との排他的論理和の結果が１１であるので、スイッチ１１の配下のサーバであって割り当てられた番号が１であるサーバとの通信を行う。スイッチ００の配下のサーバであって割り当てられた番号が２である場合、００と１０との排他的論理和の結果が１０であるので、スイッチ１０の配下のサーバであって割り当てられた番号が２であるサーバとの通信を行う。
【００７０】
スイッチ０１の配下のサーバであって割り当てられた番号が０である場合、０１と０１との排他的論理和の結果が００であるので、スイッチ００の配下のサーバであって割り当てられた番号が０であるサーバとの通信を行う。スイッチ０１の配下のサーバであって割り当てられた番号が１である場合、０１と１１との排他的論理和の結果が１０であるので、スイッチ１０の配下のサーバであって割り当てられた番号が１であるサーバとの通信を行う。スイッチ０１の配下のサーバであって割り当てられた番号が２である場合、０１と１０との排他的論理和の結果が１１であるので、スイッチ１１の配下のサーバであって割り当てられた番号が２であるサーバとの通信を行う。
【００７１】
スイッチ１０の配下のサーバであって割り当てられた番号が０である場合、１０と０１との排他的論理和の結果が１１であるので、スイッチ１１の配下のサーバであって割り当てられた番号が０であるサーバとの通信を行う。スイッチ１０の配下のサーバであって割り当てられた番号が１である場合、１０と１１との排他的論理和の結果が０１であるので、スイッチ０１の配下のサーバであって割り当てられた番号が１であるサーバとの通信を行う。スイッチ１０の配下のサーバであって割り当てられた番号が２である場合、１０と１０との排他的論理和の結果が００であるので、スイッチ００の配下のサーバであって割り当てられた番号が２であるサーバとの通信を行う。
【００７２】
スイッチ１１の配下のサーバであって割り当てられた番号が０である場合、１１と０１との排他的論理和の結果が１０であるので、スイッチ１０の配下のサーバであって割り当てられた番号が０であるサーバとの通信を行う。スイッチ１１の配下のサーバであって割り当てられた番号が１である場合、１１と１１との排他的論理和の結果が００であるので、スイッチ００の配下のサーバであって割り当てられた番号が１であるサーバとの通信を行う。スイッチ１１の配下のサーバであって割り当てられた番号が２である場合、１１と１０との排他的論理和の結果が０１であるので、スイッチ０１の配下のサーバであって割り当てられた番号が２であるサーバとの通信を行う。
【００７３】
次に、フェーズ１の通信について説明する。スイッチ００の配下のサーバであって割り当てられた番号が０である場合、００と１１との排他的論理和の結果が１１であるので、スイッチ１１の配下のサーバであって割り当てられた番号が０であるサーバとの通信を行う。スイッチ００の配下のサーバであって割り当てられた番号が１である場合、００と１０との排他的論理和の結果が１０であるので、スイッチ１０の配下のサーバであって割り当てられた番号が１であるサーバとの通信を行う。スイッチ００の配下のサーバであって割り当てられた番号が２である場合、００と０１との排他的論理和の結果が０１であるので、スイッチ０１の配下のサーバであって割り当てられた番号が２であるサーバとの通信を行う。
【００７４】
スイッチ０１の配下のサーバであって割り当てられた番号が０である場合、０１と１１との排他的論理和の結果が１０であるので、スイッチ１０の配下のサーバであって割り当てられた番号が０であるサーバとの通信を行う。スイッチ０１の配下のサーバであって割り当てられた番号が１である場合、０１と１０との排他的論理和の結果が１１であるので、スイッチ１１の配下のサーバであって割り当てられた番号が１であるサーバとの通信を行う。スイッチ０１の配下のサーバであって割り当てられた番号が２である場合、０１と０１との排他的論理和の結果が００であるので、スイッチ００の配下のサーバであって割り当てられた番号が２であるサーバとの通信を行う。
【００７５】
スイッチ１０の配下のサーバであって割り当てられた番号が０である場合、１０と１１との排他的論理和の結果が０１であるので、スイッチ０１の配下のサーバであって割り当てられた番号が０であるサーバとの通信を行う。スイッチ１０の配下のサーバであって割り当てられた番号が１である場合、１０と１０との排他的論理和の結果が００であるので、スイッチ００の配下のサーバであって割り当てられた番号が１であるサーバとの通信を行う。スイッチ１０の配下のサーバであって割り当てられた番号が２である場合、１０と０１との排他的論理和の結果が１１であるので、スイッチ１１の配下のサーバであって割り当てられた番号が２であるサーバとの通信を行う。
【００７６】
スイッチ１１の配下のサーバであって割り当てられた番号が０である場合、１１と１１との排他的論理和の結果が００であるので、スイッチ００の配下のサーバであって割り当てられた番号が０であるサーバとの通信を行う。スイッチ１１の配下のサーバであって割り当てられた番号が１である場合、１１と１０との排他的論理和の結果が０１であるので、スイッチ０１の配下のサーバであって割り当てられた番号が１であるサーバとの通信を行う。スイッチ１１の配下のサーバであって割り当てられた番号が２である場合、１１と０１との排他的論理和の結果が１０であるので、スイッチ１０の配下のサーバであって割り当てられた番号が２であるサーバとの通信を行う。
【００７７】
以上のように、いずれの通信経路においても同一方向のパケットが同時に送信されることがない。すなわち、経路競合が発生しない。
【００７８】
図１９の説明に戻り、通信表生成部３０１は、ステップＳ２１において生成された第２の通信表を通信表格納部３０３に格納する（ステップＳ２３）。そして処理は呼び出し元に戻る。
【００７９】
図１１の説明に戻り、通信表生成部３０１は、通信表格納部３０３に格納された第１の通信表及び第２の通信表を読み出し、読み出した第１の通信表及び第２の通信表を単層フルメッシュシステム１０００における各サーバに送信する（ステップＳ７）。そして処理は終了する。
【００８０】
以上のような処理を実行すれば、各サーバは第１の通信表及び第２の通信表に従って適切な手順でオールリデュース通信を実行できるようになる。
【００８１】
次に、図２３及び図２４を用いて、サーバが実行する処理について説明する。本処理は、第１の通信表及び第２の通信表を管理装置３から受信した各サーバが実行する処理である。
【００８２】
図２３は、サーバが実行する処理の処理フローを示す図である。
【００８３】
サーバにおける第１通信部１０１１は、フェーズ番号を表す変数を０に設定する（図２３：ステップＳ３１）。
【００８４】
第１通信部１０１１は、通信表格納部１０３に格納されている第１の通信表から、フェーズｉの通信情報を特定する（ステップＳ３３）。
【００８５】
第１通信部１０１１は、自サーバ（すなわち、本処理を実行しているサーバ）がフェーズｉにおいて通信を実行するか判定する（ステップＳ３５）。自サーバがフェーズｉにおいて通信を実行するか否かは、特定された通信情報に自サーバの識別情報が含まれているか否かにより判定される。
【００８６】
自サーバがフェーズｉにおいて通信を実行しない場合（ステップＳ３５：Ｎｏルート）、処理はステップＳ３９に移行する。一方、自サーバがフェーズｉにおいて通信を実行する場合（ステップＳ３５：Ｙｅｓルート）、第１通信部１０１１は、ステップＳ３３において特定された通信情報に従って通信を実行する（ステップＳ３７）。
【００８７】
上で述べたように、第１の通信表に従って行われる通信は、同一のスイッチ配下のサーバ間でのオールリデュース通信であり、各サーバはオールリデュースに係る演算を実行する。
【００８８】
第１通信部１０１１は、ｉ＝ｉmax1が成立するか判定する（ステップＳ３９）。ｉmax1は、第１の通信表に従って行われる通信のフェーズ番号の最大値である。ｉ＝ｉmax1が成立しない場合（ステップＳ３９：Ｎｏルート）、第１通信部１０１１は、ｉを１インクリメントする（ステップＳ４１）。そして処理はステップＳ３３に移行する。なお、フェーズの終了はバリア同期によって確認される。
【００８９】
一方、ｉ＝ｉmax1が成立する場合（ステップＳ３９：Ｙｅｓルート）、処理は端子Ａを介して図２４のステップＳ４３に移行する。
【００９０】
図２４の説明に移行し、第２通信部１０１３は、自サーバに割り振られた番号ｊを、例えばメモリ等の記憶装置から取得する（図２４：ステップＳ４３）。
【００９１】
第２通信部１０１３は、フェーズ番号を表す変数ｉを０に設定する（ステップＳ４５）。
【００９２】
第２通信部１０１３は、ビット列生成部１０５を呼び出す。これに応じ、ビット列生成部１０５は、通信表格納部１０３に格納された第２の通信表から、ビット列ａi,jを特定する（ステップＳ４７）。
【００９３】
ビット列生成部１０５は、自サーバを収容するスイッチに割り当てられたビット列ｓと、ステップＳ４７において特定されたビット列ａi,jとの排他的論理和を計算する（ステップＳ４９）。ビット列生成部１０５は、ステップＳ４９の計算結果のビット列を第２通信部１０１３に渡す。
【００９４】
第２通信部１０１３は、ステップＳ４９の計算結果のビット列が割り当てられたスイッチの配下のサーバであって且つ自サーバに割り振られた番号と同じ番号が割り振られたサーバとの通信を実行する（ステップＳ５１）。
【００９５】
ステップＳ５１の処理が終了すると、第２通信部１０１３は、ｉ＝ｉmax2が成立するか判定する（ステップＳ５３）。ｉmax2は、第２の通信表に従って行われる通信のフェーズ番号の最大値である。ｉ＝ｉmax2が成立しない場合（ステップＳ５３：Ｎｏルート）、第２通信部１０１３は、ｉを１インクリメントする（ステップＳ５５）。そして処理はステップＳ４７に移行する。なお、フェーズの終了はバリア同期によって確認される。
【００９６】
一方、ｉ＝ｉmax2が成立する場合（ステップＳ５３：Ｙｅｓルート）、処理は終了する。
【００９７】
以上のように、第１の通信表に従った通信によって、各スイッチの配下においては全サーバが同一の値を持つようになる。そして、第２の通信表に従った通信によって、単層フルメッシュシステム１０００における全サーバが同じ値を持つようになる。すなわち、単層フルメッシュシステム１０００においてオールリデュースが実現される。
【００９８】
また、上で述べたように、本実施の形態においては、オールリデュース通信の過程で経路競合が発生することはない。
【００９９】
また、本実施の形態の方法であれば、Ｏ（ｌｏｇ ｎ）（ｎは全サーバ台数）程度の計算量でオールリデュースを実行することができるようになる。対数の底は２である。
【０１００】
［実施の形態２］
第１の実施の形態における単層フルメッシュシステム１０００を複数連結することで、多層フルメッシュシステム２０００を構築することが可能である。以下では、多層フルメッシュシステム２０００においてオールリデュース通信を行う場合に経路競合が発生することを回避する方法について説明する。
【０１０１】
図２５は、第２の実施の形態における多層フルメッシュシステム２０００を示す図である。図２５においては、３つの単層フルメッシュシステム１０００が、ＳｐｉｎｅスイッチＡ乃至Ｆにより連結されている。図２５の例においては、Ｌｅａｆスイッチ及びＳｐｉｎｅスイッチのポート数は６であり、層の数は３であり、３６台のサーバが多層フルメッシュシステム２０００に含まれる。但し、Ｌｅａｆスイッチ及びＳｐｉｎｅスイッチのポート数、層の数及びサーバ数は、図２５に示した例には限られない。
【０１０２】
なお、図２５に示した単層フルメッシュシステム１０００は、ＳｐｉｎｅスイッチＡ乃至Ｆが存在する点を除き第１の実施の形態における単層フルメッシュシステム１０００と同じであるので、ここでは詳細な説明を省略する。
【０１０３】
ＳｐｉｎｅスイッチＡは、各層において、Ｌｅａｆスイッチ０１及びＬｅａｆスイッチ１０に接続される。ＳｐｉｎｅスイッチＢは、各層において、Ｌｅａｆスイッチ００及びＬｅａｆスイッチ１１に接続される。ＳｐｉｎｅスイッチＣは、各層において、Ｌｅａｆスイッチ００及びＬｅａｆスイッチ０１に接続される。ＳｐｉｎｅスイッチＤは、各層において、Ｌｅａｆスイッチ１０及びＬｅａｆスイッチ１１に接続される。ＳｐｉｎｅスイッチＥは、各層において、Ｌｅａｆスイッチ０１及びＬｅａｆスイッチ１０に接続される。ＳｐｉｎｅスイッチＦは、各層において、Ｌｅａｆスイッチ０１及びＬｅａｆスイッチ１１に接続される。
【０１０４】
図２６に示すように、多層フルメッシュシステム２０００は管理装置３に管理ＬＡＮ等で接続され、多層フルメッシュシステム２０００における通信は管理装置３により管理される。管理装置３は、通信表生成部３０１と、通信表格納部３０３と、トポロジデータ格納部３０５とを有する。
【０１０５】
通信表生成部３０１は、トポロジデータ格納部３０５に格納されている、多層フルメッシュシステム２０００のネットワークトポロジの情報に基づき、第３の通信表、第４の通信表及び第５の通信表を生成し、生成された第３の通信表、第４の通信表及び第５の通信表を通信表格納部３０３に格納する。通信表生成部３０１は、通信表格納部３０３に格納された第３の通信表、第４の通信表及び第５の通信表を、所定のタイミングで又はリクエストに応じて、多層フルメッシュシステム２０００における各サーバに送信する。
【０１０６】
図２７は、サーバの機能ブロック図である。サーバは、処理部１０１と、通信表格納部１０３と、ビット列生成部１０５とを有する。処理部１０１は、第３通信部１０１５と、第４通信部１０１７と、第５通信部１０１９とを有する。
【０１０７】
通信表格納部１０３には、管理装置３から受信した第３の通信表、第４の通信表及び第５の通信表が格納される。ビット列生成部１０５は、通信表格納部１０３に格納された第５の通信表に基づきビット列を生成する。処理部１０１における第３通信部１０１５は、通信表格納部１０３に格納された第３の通信表に従って通信を行う。処理部１０１における第４通信部１０１７は、通信表格納部１０３に格納された第４の通信表に従って通信を行う。処理部１０１における第５通信部１０１９は、ビット列生成部１０５により生成されたビット列に基づき通信を行う。
【０１０８】
次に、図２８乃至図３２を用いて、管理装置３が実行する処理について説明する。
【０１０９】
図２８は、管理装置３が実行する処理の処理フローを示す図である。
【０１１０】
管理装置３における通信表生成部３０１は、多層フルメッシュシステム２０００のネットワークトポロジの情報をトポロジデータ格納部３０５から読み出す（図２８：ステップＳ６１）。ネットワークトポロジの情報は、例えば、Ｌｅａｆスイッチ、Ｓｐｉｎｅスイッチ及びサーバの接続関係の情報等を含む。
【０１１１】
通信表生成部３０１は、ステップＳ６１において読み出したネットワークトポロジの情報に基づき、第３の通信表を生成する処理である第３生成処理を実行する（ステップＳ６３）。
【０１１２】
図２９乃至図３０Ｃを用いて、第３生成処理について説明する。図２９は、第３生成処理の処理フローを示す図である。
【０１１３】
通信表生成部３０１は、同じカラムに属し且つ同じ番号が割り振られたサーバの間で行われるオールリデュース通信について、各フェーズにおいて通信を実行するサーバの識別情報を含む第３の通信表を生成する（ステップＳ７１）。
【０１１４】
本実施の形態において、カラムは、層内の位置が同じであるＬｅａｆスイッチおよびそのＬｅａｆスイッチの配下にあるサーバを含む。例えば図３０Ａにおいて、各層におけるＬｅａｆスイッチ００及びＬｅａｆスイッチ００の配下にあるサーバは、同じカラムに属する。同様に、各層におけるＬｅａｆスイッチ０１及びＬｅａｆスイッチ０１の配下にあるサーバは、同じカラムに属する。同様に、各層におけるＬｅａｆスイッチ１０及びＬｅａｆスイッチ１０の配下にあるサーバは、同じカラムに属する。同様に、各層におけるＬｅａｆスイッチ１１及びＬｅａｆスイッチ１１の配下にあるサーバは、同じカラムに属する。
【０１１５】
言い換えると、同じＳｐｉｎｅスイッチに接続されるＬｅａｆスイッチとそのＬｅａｆスイッチの配下のサーバとは同じカラムに属する。例えば、各層におけるＬｅａｆスイッチ００はＳｐｉｎｅスイッチＡ、ＳｐｉｎｅスイッチＢ及びＳｐｉｎｅスイッチＣに接続されているので、各層におけるＬｅａｆスイッチ００は同じカラムに属し、各層におけるＬｅａｆスイッチ００の配下のサーバも同じカラムに属する。同様に、各層におけるＬｅａｆスイッチ０１はＳｐｉｎｅスイッチＣ、ＳｐｉｎｅスイッチＥ及びＳｐｉｎｅスイッチＦに接続されているので、各層におけるＬｅａｆスイッチ０１は同じカラムに属し、各層におけるＬｅａｆスイッチ０１の配下のサーバも同じカラムに属する。同様に、各層におけるＬｅａｆスイッチ１０はＳｐｉｎｅスイッチＡ、ＳｐｉｎｅスイッチＤ及びＳｐｉｎｅスイッチＥに接続されているので、各層におけるＬｅａｆスイッチ１０は同じカラムに属し、各層におけるＬｅａｆスイッチ１０の配下のサーバも同じカラムに属する。同様に、各層におけるＬｅａｆスイッチ１１はＳｐｉｎｅスイッチＢ、ＳｐｉｎｅスイッチＤ及びＳｐｉｎｅスイッチＦに接続されているので、各層におけるＬｅａｆスイッチ１１は同じカラムに属し、各層におけるＬｅａｆスイッチ１１の配下のサーバも同じカラムに属する。
【０１１６】
第３の通信表に従って行われるオールリデュースにおいては、各Ｌｅａｆスイッチ配下のｄ台のサーバが、同時並行で通信を行う。ここで、図３０Ａ乃至図３０Ｃに示すように、各番号のサーバが異なる経路（すなわちリンク）で通信を行えば、経路上を同一方向の複数のパケットが同時に通ることはない。従って、第３の通信表に従って行われるオールリデュースにおいて経路競合が発生することはない。なお、同じＳｐｉｎｅスイッチが複数のパケットを同時に処理することになるが、これは経路競合ではなく、スループットの低下をもたらすこともない。
【０１１７】
第３の通信表は、第１の通信表と同様の方法で生成される。
【０１１８】
なお、第３の通信表に従って行われるオールリデュースにかかる時間は、ｔ＊ｌｏｇ（ｄ）で表される。ここで、ｔは各サーバがデータを送るのに要する時間を表す。
【０１１９】
図２９の説明に戻り、通信表生成部３０１は、ステップＳ７１において生成された第３の通信表を通信表格納部３０３に格納する（ステップＳ７３）。そして処理は呼び出し元に戻る。
【０１２０】
図２８の説明に戻り、通信表生成部３０１は、ステップＳ６１において読み出されたネットワークトポロジの情報に基づき、第４の通信表を生成する処理である第４生成処理を実行する（ステップＳ６５）。
【０１２１】
図３１を用いて、第４生成処理について説明する。図３１は、第４生成処理の処理フローを示す図である。
【０１２２】
通信表生成部３０１は、多層フルメッシュシステム２０００における各Ｌｅａｆスイッチ配下でのオールリデュースの各フェーズにおいて通信を実行するサーバの識別情報を含む第４の通信表を生成する（図３１：ステップＳ８１）。
【０１２３】
ステップＳ８１においては、ステップＳ１１の処理と同様の処理が、複数の単層フルメッシュシステム１０００を対象として実行される。従って、第４の通信表には、各層についての通信情報が含まれる。第４の通信表は、第１の通信表と同様の方法で生成される。
【０１２４】
通信表生成部３０１は、ステップＳ８１において生成された第４の通信表を通信表格納部３０３に格納する（ステップＳ８３）。そして処理は呼び出し元に戻る。
【０１２５】
図２８の説明に戻り、通信表生成部３０１は、ステップＳ６１において読み出されたネットワークトポロジの情報に基づき、第５の通信表を生成する処理である第５生成処理を実行する（ステップＳ６７）。
【０１２６】
図３２を用いて、第５生成処理について説明する。図３２は、第５生成処理の処理フローを示す図である。
【０１２７】
通信表生成部３０１は、各層において同一番号が割り振られたサーバ間で行われるオールリデュースにおいて各サーバが各フェーズで送信するデータの送信先を特定するために使用されるビット列ａi,jを含む第５の通信表を生成する（図３２：ステップＳ９１）。ここで、ｉはフェーズ番号を表す変数であり、ｊはサーバに割り振られた番号を表す変数である。
【０１２８】
ステップＳ９１においては、ステップＳ２１の処理と同様の処理が、複数の単層フルメッシュシステム１０００を対象として実行される。第２の実施の形態においては、各層について図２０に示したような通信表が生成されるので、第５の通信表には各層についての通信表が含まれる。
【０１２９】
通信表生成部３０１は、ステップＳ９１において生成された第５の通信表を通信表格納部３０３に格納する（ステップＳ９３）。そして処理は呼び出し元に戻る。
【０１３０】
図２８の説明に戻り、通信表生成部３０１は、通信表格納部３０３に格納された第３の通信表、第４の通信表及び第５の通信表を読み出し、読み出した第３の通信表、第４の通信表及び第５の通信表を多層フルメッシュシステム２０００における各サーバに送信する（ステップＳ６９）。そして処理は終了する。
【０１３１】
以上のような処理を実行すれば、各サーバは第３の通信表、第４の通信表及び第５の通信表に従って適切な手順でオールリデュース通信を実行できるようになる。
【０１３２】
次に、図３３乃至図３５を用いて、サーバが実行する処理について説明する。本処理は、第３の通信表、第４の通信表及び第５の通信表を管理装置３から受信した各サーバが実行する処理である。
【０１３３】
図３３は、サーバが実行する処理の処理フローを示す図である。
【０１３４】
サーバにおける第３通信部１０１５は、フェーズ番号を表す変数を０に設定する（図３３：ステップＳ１０１）。
【０１３５】
第３通信部１０１５は、通信表格納部１０３に格納されている第３の通信表から、フェーズｉの通信情報を特定する（ステップＳ１０３）。
【０１３６】
第３通信部１０１５は、自サーバ（すなわち、本処理を実行しているサーバ）がフェーズｉにおいて通信を実行するか判定する（ステップＳ１０５）。自サーバがフェーズｉにおいて通信を実行するか否かは、特定された通信情報に自サーバの識別情報が含まれているか否かにより判定される。
【０１３７】
自サーバがフェーズｉにおいて通信を実行しない場合（ステップＳ１０５：Ｎｏルート）、処理はステップＳ１０９に移行する。一方、自サーバがフェーズｉにおいて通信を実行する場合（ステップＳ１０５：Ｙｅｓルート）、第３通信部１０１５は、ステップＳ１０３において特定された通信情報に従って通信を実行する（ステップＳ１０７）。
【０１３８】
上で述べたように、第３の通信表に従って行われる通信は、同一のカラムに属し且つ同じ番号が割り当てられたサーバ間でのオールリデュース通信であり、各サーバはオールリデュースに係る演算を実行する。
【０１３９】
第３通信部１０１５は、ｉ＝ｉmax3が成立するか判定する（ステップＳ１０９）。ｉmax3は、第３の通信表に従って行われる通信のフェーズ番号の最大値である。ｉ＝ｉmax3が成立しない場合（ステップＳ１０９：Ｎｏルート）、第３通信部１０１５は、ｉを１インクリメントする（ステップＳ１１１）。そして処理はステップＳ１０３に移行する。なお、フェーズの終了はバリア同期によって確認される。
【０１４０】
一方、ｉ＝ｉmax3が成立する場合（ステップＳ１０９：Ｙｅｓルート）、処理は端子Ｂを介して図３４のステップＳ１１３に移行する。
【０１４１】
図３４の説明に移行し、第４通信部１０１７は、フェーズ番号を表す変数を０に設定する（図３４：ステップＳ１１３）。
【０１４２】
第４通信部１０１７は、通信表格納部１０３に格納されている第４の通信表から、フェーズｉの通信情報を特定する（ステップＳ１１５）。
【０１４３】
第４通信部１０１７は、自サーバがフェーズｉにおいて通信を実行するか判定する（ステップＳ１１７）。自サーバがフェーズｉにおいて通信を実行するか否かは、特定された通信情報に自サーバの識別情報が含まれているか否かにより判定される。
【０１４４】
自サーバがフェーズｉにおいて通信を実行しない場合（ステップＳ１１７：Ｎｏルート）、処理はステップＳ１２１に移行する。一方、自サーバがフェーズｉにおいて通信を実行する場合（ステップＳ１１７：Ｙｅｓルート）、第４通信部１０１７は、ステップＳ１１５において特定された通信情報に従って通信を実行する（ステップＳ１１９）。
【０１４５】
上で述べたように、第４の通信表に従って行われる通信は、同一のＬｅａｆスイッチ配下のサーバ間でのオールリデュース通信であり、各サーバはオールリデュースに係る演算を実行する。
【０１４６】
第４通信部１０１７は、ｉ＝ｉmax4が成立するか判定する（ステップＳ１２１）。ｉmax4は、第４の通信表に従って行われる通信のフェーズ番号の最大値である。ｉ＝ｉmax4が成立しない場合（ステップＳ１２１：Ｎｏルート）、第４通信部１０１７は、ｉを１インクリメントする（ステップＳ１２３）。そして処理はステップＳ１１５に移行する。なお、フェーズの終了はバリア同期によって確認される。
【０１４７】
一方、ｉ＝ｉmax4が成立する場合（ステップＳ１２１：Ｙｅｓルート）、処理は端子Ｃを介して図３５のステップＳ１２５に移行する。
【０１４８】
図３５の説明に移行し、第５通信部１０１９は、自サーバに割り振られた番号ｊを、例えばメモリ等の記憶装置から取得する（図３５：ステップＳ１２５）。
【０１４９】
第５通信部１０１９は、フェーズ番号を表す変数ｉを０に設定する（ステップＳ１２７）。
【０１５０】
第５通信部１０１９は、ビット列生成部１０５を呼び出す。これに応じ、ビット列生成部１０５は、通信表格納部１０３に格納された第５の通信表から、ビット列ａi,jを特定する（ステップＳ１２９）。
【０１５１】
ビット列生成部１０５は、自サーバを収容するＬｅａｆスイッチに割り当てられたビット列ｓと、ステップＳ１２９において特定されたビット列ａi,jとの排他的論理和を計算する（ステップＳ１３１）。ビット列生成部１０５は、ステップＳ１３１の計算結果のビット列を第５通信部１０１９に渡す。
【０１５２】
第５通信部１０１９は、ステップＳ１３１の計算結果のビット列が割り当てられたＬｅａｆスイッチの配下のサーバであって且つ自サーバに割り振られた番号と同じ番号が割り振られたサーバとの通信を実行する（ステップＳ１３３）。
【０１５３】
ステップＳ１３３の処理が終了すると、第５通信部１０１９は、ｉ＝ｉmax5が成立するか判定する（ステップＳ１３５）。ｉmax5は、第５の通信表に従って行われる通信のフェーズ番号の最大値である。ｉ＝ｉmax5が成立しない場合（ステップＳ１３５：Ｎｏルート）、第５通信部１０１９は、ｉを１インクリメントする（ステップＳ１３７）。そして処理はステップＳ１２９に移行する。なお、フェーズの終了はバリア同期によって確認される。
【０１５４】
一方、ｉ＝ｉmax5が成立する場合（ステップＳ１３５：Ｙｅｓルート）、処理は終了する。
【０１５５】
以上のように、第３の通信表に従った通信によって、同じカラムに属し且つ同じ番号が割り当てられたサーバは同じ値を持つようになる。次に、第４の通信表に従った通信によって、各Ｌｅａｆスイッチ配下における複数のサーバが同じ値を持つようになる。そして、第５の通信表に従った通信によって、多層フルメッシュシステム２０００における全サーバが同じ値を持つようになる。すなわち、多層フルメッシュシステム２０００においてオールリデュースが実現される。
【０１５６】
また、上で述べたように、本実施の形態においては、オールリデュース通信の過程で経路競合が発生することはない。
【０１５７】
また、本実施の形態の方法であれば、Ｏ（ｌｏｇ ｎ）（ｎはノード台数）程度の計算量でオールリデュースを実行することができるようになる。
【０１５８】
［実施の形態３］
第１の実施の形態および第２の実施の形態においてはｋ＝２であるが、ｋが３以上の自然数であったとしても、経路競合が発生することなくオールリデュース通信を実現することができる。
【０１５９】
一例として、ｋ＝３の場合における単層フルメッシュシステム３０００を図３６に示す。図３６においては、８台のノードの各々に３桁のビット列が割り当てられており、８台のスイッチがフルメッシュトポロジで接続されている。具体的には、スイッチ０００と、スイッチ００１と、スイッチ０１０と、スイッチ０１１と、スイッチ１００と、スイッチ１０１と、スイッチ１１０と、スイッチ１１１とがフルメッシュトポロジで接続されている。図３６には示されていないが、各スイッチには、７（＝２3−）台のサーバが接続される。
【０１６０】
図３７は、ｋ＝３の場合におけるａi,jの一例を示す図である。各列における３つのビット列は一次独立であるため、オールリデュース通信を実現することが可能である。また、各行における７つのビット列は１から７までの１０進数に対応するビット列であるため、経路競合を回避することが可能である。
【０１６１】
［実施の形態４］
第３の実施の形態における単層フルメッシュシステム３０００を複数連結することで、Ｋが３以上の自然数である場合における多層メッシュシステムを構築してもよい。この場合におけるオールリデュースは、基本的には第２の実施の形態の方法と同じ方法で実行される。
【０１６２】
以上本発明の一実施の形態を説明したが、本発明はこれに限定されるものではない。例えば、上で説明した管理装置３及びサーバの機能ブロック構成は実際のプログラムモジュール構成に一致しない場合もある。
【０１６３】
また、上で説明した各テーブルの構成は一例であって、上記のような構成でなければならないわけではない。さらに、処理フローにおいても、処理結果が変わらなければ処理の順番を入れ替えることも可能である。さらに、並列に実行させるようにしても良い。
【０１６４】
［付録］
１．ビット列ａi,jの生成
円環方式に基づきビット列ａi,jを生成した結果を以下に示す。
【０１６５】
ｋ＝２の場合、｛０１, １１, １０｝である。
【０１６６】
ｋ＝３の場合、｛００１，０１１，１１０，０１０，１０１，１００，１１１｝である。
【０１６７】
ｋ＝４の場合、｛０１１０，０１１１，１００１，１０００，１０１０，１１００，１０１１，１１１１，１１１０，００１１，０１００，０００１，１１０１，００１０，０１０１｝である。
【０１６８】
ｋ＝５の場合、｛００１１０，００１１１，０１００１，０１０１１，１０１０１，０１１０１，０１１００，０１１１０，１０００１，１０１１０，０１１１１，１００１０，１００１１，１１０１０，１００００，１１１０１，１１０１１，１０１００，１０１１１，１１１００，１１１１０，１１０００，０００１１，０１０００，００００１，１１１１１，００１０１，０１０１０，０００１０，００１００，１１００１｝である。
【０１６９】
ｋ＝６の場合、｛１００００１，１０００１０，１００１００，１０１０００，１１００００，００１０１１，００１００１，００１０１０，１０１１１０，００１１０１，１１００１１，１０１１０１，１０１１００，１１１０００，１１０１１０，００１１００，１１１０１１，１１１１００，０１０１０１，００１１１０，１１１１１１，１１１１１０，０１００００，００１１１１，０１００１０，０００１１１，０１００１１，１０１００１，０１０００１，０１１１００，０１１０００，００１０００，０１０１１０，１０１０１０，０１１０１１，０１１００１，０１０１１１，０１１１１１，０１１１１０，１０１０１１，０１１０１０，１０００００，１０００１１，０１０１００，０１１１０１，０００１１０，１００１１０，１００１１１，１１０００１，１１１１０１，１１１０１０，１１１００１，１１０１００，１０１１１１，０００１０１，０００１００，００００１０，１００１０１，００００１１，１１００１０，０００００１，１１０１０１，１１０１１１｝である。
【０１７０】
２．貪欲法のアルゴリズム
円環方式において利用する貪欲法のアルゴリズムは、例えば図３８に示すようなアルゴリズムである。
【０１７１】
以上で付録を終了する。
【０１７２】
なお、上で述べた管理装置３及び各サーバは、コンピュータ装置であって、図３９に示すように、メモリ２５０１とＣＰＵ２５０３とＨＤＤ２５０５と表示装置２５０９に接続される表示制御部２５０７とリムーバブル・ディスク２５１１用のドライブ装置２５１３と入力装置２５１５とネットワークに接続するための通信制御部２５１７とがバス２５１９で接続されている。オペレーティング・システム（ＯＳ：Operating System）及び本実施例における処理を実施するためのアプリケーション・プログラムは、ＨＤＤ２５０５に格納されており、ＣＰＵ２５０３により実行される際にはＨＤＤ２５０５からメモリ２５０１に読み出される。ＣＰＵ２５０３は、アプリケーション・プログラムの処理内容に応じて表示制御部２５０７、通信制御部２５１７、ドライブ装置２５１３を制御して、所定の動作を行わせる。また、処理途中のデータについては、主としてメモリ２５０１に格納されるが、ＨＤＤ２５０５に格納されるようにしてもよい。本発明の実施例では、上で述べた処理を実施するためのアプリケーション・プログラムはコンピュータ読み取り可能なリムーバブル・ディスク２５１１に格納されて頒布され、ドライブ装置２５１３からＨＤＤ２５０５にインストールされる。インターネットなどのネットワーク及び通信制御部２５１７を経由して、ＨＤＤ２５０５にインストールされる場合もある。このようなコンピュータ装置は、上で述べたＣＰＵ２５０３、メモリ２５０１などのハードウエアとＯＳ及びアプリケーション・プログラムなどのプログラムとが有機的に協働することにより、上で述べたような各種機能を実現する。
【０１７３】
また、上で述べたスイッチ、Ｌｅａｆスイッチ及びＳｐｉｎｅスイッチは、図４０に示すように、メモリ２６０１とＣＰＵ２６０３とＨＤＤ２６０５と表示装置２６０９に接続される表示制御部２６０７とリムーバブル・ディスク２６１１用のドライブ装置２６１３と入力装置２６１５とネットワークに接続するための通信制御部２６１７（図４０では、２６１７ａ乃至２６１７ｃ）とがバス２６１９で接続されている構成の場合もある。なお、場合によっては、表示制御部２６０７、表示装置２６０９、ドライブ装置２６１３、入力装置２６１５は含まれない場合もある。オペレーティング・システム（ＯＳ：Operating System）及び本実施の形態における処理を実施するためのアプリケーション・プログラムは、ＨＤＤ２６０５に格納されており、ＣＰＵ２６０３により実行される際にはＨＤＤ２６０５からメモリ２６０１に読み出される。必要に応じてＣＰＵ２６０３は、表示制御部２６０７、通信制御部２６１７、ドライブ装置２６１３を制御して、必要な動作を行わせる。なお、通信制御部２６１７のいずれかを介して入力されたデータは、他の通信制御部２６１７を介して出力される。ＣＰＵ２６０３は、通信制御部２６１７を制御して、適切に出力先を切り替える。また、処理途中のデータについては、メモリ２６０１に格納され、必要があればＨＤＤ２６０５に格納される。本技術の実施例では、上で述べた処理を実施するためのアプリケーション・プログラムはコンピュータ読み取り可能なリムーバブル・ディスク２６１１に格納されて頒布され、ドライブ装置２６１３からＨＤＤ２６０５にインストールされる。インターネットなどのネットワーク及び通信制御部２６１７を経由して、ＨＤＤ２６０５にインストールされる場合もある。このようなコンピュータ装置は、上で述べたＣＰＵ２６０３、メモリ２６０１などのハードウエアとＯＳ及び必要なアプリケーション・プログラムとが有機的に協働することにより、上で述べたような各種機能を実現する。
【０１７４】
以上述べた本発明の実施の形態をまとめると、以下のようになる。
【０１７５】
本実施の形態の第１の態様に係る情報処理システムは、（Ａ）接続形態がフルメッシュである複数のスイッチ（実施の形態におけるスイッチ００乃至１１は上記複数のスイッチの一例である）と、複数のスイッチのいずれかにそれぞれ接続される複数の情報処理装置（実施の形態におけるサーバは上記複数の情報処理装置の一例である）とを有する。そして、複数の情報処理装置の各々が、（ｂ１）自情報処理装置に接続されるスイッチの識別子である第１の識別子と、自情報処理装置に割り当てられた一次独立な数の集合のうち通信フェーズに対応する数との排他的論理和により、第２の識別子を生成する生成部（実施の形態におけるビット列生成部１０５は上記生成部の一例である）と、（ｂ２）第２の識別子を有するスイッチに接続される情報処理装置との通信を行う第１通信部（実施の形態における第２通信部１０１３は上記第１通信部の一例である）とを有する。
【０１７６】
各情報処理装置が自情報処理装置に割り当てられた一次独立な数の集合を使用することで、フルメッシュシステムにおいてオールリデュース通信を行う場合に経路競合が発生することを回避できるようになる。
【０１７７】
また、複数のスイッチの台数は２k（ｋは自然数）であってもよく、複数のスイッチの各々には（２k−１）台の情報処理装置が接続されてもよい。
【０１７８】
スイッチの台数及び情報処理装置の台数が適切ではない場合には経路競合なくオールリデュース通信をすることができないが、上で述べたような情報処理システムであれば経路競合なくオールリデュース通信をすることが可能である。
【０１７９】
また、一次独立な数の集合は、一次独立なｋ個のｋ桁のビット列の集合であってもよく、複数のスイッチの各々の識別子はｋ桁のビット列であってもよく、複数のスイッチの各々に接続された（２k−１）台の情報処理装置が各通信フェーズで使用するビット列の集合は、１から（２k−１）までの１０進数に対応するビット列を含んでもよい。
【０１８０】
また、複数の情報処理装置の各々が、（ｂ３）第１の識別子を有するスイッチに接続された他の情報処理装置との通信を行う第２通信部（実施の形態における第１通信部１０１１は上記第２通信部の一例である）をさらに有してもよい。そして、第１通信部は、（ｂ２１）第２の識別子を有するスイッチに接続される情報処理装置であって且つ自情報処理装置以外の情報処理装置が送信するデータを受信しない情報処理装置に対してデータを送信してもよい。
【０１８１】
各情報処理装置が同じ計算結果を持つことできるようになる。
【０１８２】
本実施の形態の第２の態様に係る情報処理システムは、接続形態がフルメッシュである複数のスイッチと複数のスイッチのいずれかにそれぞれ接続される複数の情報処理装置とを含むフルメッシュシステムが複数のスパインスイッチにより複数連結された情報処理システムである。そして、複数のフルメッシュシステムの各々における複数の情報処理装置の各々が、（Ｃ）自情報処理装置を収容する第１のリーフスイッチに接続されるスパインスイッチに接続され且つ第１のリーフスイッチが含まれるフルメッシュシステムとは異なるフルメッシュシステムに含まれる第２のリーフスイッチに接続される情報処理装置との通信を行う第１通信部（実施の形態における第３通信部１０１５は上記第１通信部の一例である）と、（Ｄ）第１のリーフスイッチに収容される他の情報処理装置との通信を行う第２通信部（実施の形態における第４通信部１０１７は上記第２通信部の一例である）と、（Ｅ）第１のリーフスイッチの識別子である第１の識別子と、自情報処理装置に割り当てられた一次独立な数の集合のうち通信フェーズに対応する数との排他的論理和により、第２の識別子を生成する生成部（実施の形態におけるビット列生成部１０５は上記生成部の一例である）と、（Ｆ）第２の識別子を有し且つ自情報処理装置と同じフルメッシュシステムに含まれるリーフスイッチに収容される情報処理装置との通信を行う第３通信部（実施の形態における第５通信部１０１９は上記第３通信部の一例である）とを有する。
【０１８３】
多層フルメッシュシステムにおいてオールリデュース通信を行う場合に経路競合が発生することを回避できるようになる。
【０１８４】
本実施の形態の第３の態様に係る情報処理方法は、接続形態がフルメッシュである複数のスイッチと、複数のスイッチのいずれかにそれぞれ接続される複数の情報処理装置とを有する情報処理システムにおける複数の情報処理装置のうち第１の情報処理装置に実行される。そして、上記情報処理方法は、（Ｇ）第１の情報処理装置に接続されるスイッチの識別子である第１の識別子と、第１の情報処理装置に割り当てられた一次独立な数の集合のうち通信フェーズに対応する数との排他的論理和により、第２の識別子を生成し、（Ｈ）第２の識別子を有するスイッチに接続される情報処理装置との通信を行う処理を含む。
【０１８５】
なお、上記方法による処理をプロセッサに行わせるためのプログラムを作成することができ、当該プログラムは、例えばフレキシブルディスク、ＣＤ−ＲＯＭ、光磁気ディスク、半導体メモリ、ハードディスク等のコンピュータ読み取り可能な記憶媒体又は記憶装置に格納される。尚、中間的な処理結果はメインメモリ等の記憶装置に一時保管される。
【０１８６】
以上の実施例を含む実施形態に関し、さらに以下の付記を開示する。
【０１８７】
（付記１）
接続形態がフルメッシュである複数のスイッチと、
前記複数のスイッチのいずれかにそれぞれ接続される複数の情報処理装置と、
を有し、
前記複数の情報処理装置の各々が、
自情報処理装置に接続されるスイッチの識別子である第１の識別子と、前記自情報処理装置に割り当てられた一次独立な数の集合のうち通信フェーズに対応する数との排他的論理和により、第２の識別子を生成する生成部と、
前記第２の識別子を有するスイッチに接続される情報処理装置との通信を行う第１通信部とを有する、
情報処理システム。
【０１８８】
（付記２）
前記複数のスイッチの台数は２k（ｋは自然数）であり、
前記複数のスイッチの各々には（２k−１）台の情報処理装置が接続される、
付記１記載の情報処理システム。
【０１８９】
（付記３）
前記一次独立な数の集合は、一次独立なｋ個のｋ桁のビット列の集合であり、
前記複数のスイッチの各々の識別子はｋ桁のビット列であり、
前記複数のスイッチの各々に接続された（２k−１）台の情報処理装置が各通信フェーズで使用するビット列の集合は、１から（２k−１）までの１０進数に対応するビット列を含む、
付記２記載の情報処理システム。
【０１９０】
（付記４）
前記複数の情報処理装置の各々が、
前記第１の識別子を有するスイッチに接続された他の情報処理装置との通信を行う第２通信部
をさらに有し、
前記第１通信部は、
前記第２の識別子を有するスイッチに接続される情報処理装置であって且つ前記自情報処理装置以外の情報処理装置が送信するデータを受信しない情報処理装置に対してデータを送信する、
付記１乃至３のいずれか１つ記載の情報処理システム。
【０１９１】
（付記５）
接続形態がフルメッシュである複数のスイッチと、前記複数のスイッチのいずれかにそれぞれ接続される複数の情報処理装置とを有する情報処理システムにおいて実行される情報処理方法であって、
前記複数の情報処理装置の各々が、
自情報処理装置に接続されるスイッチの識別子である第１の識別子と、前記自情報処理装置に割り当てられた一次独立な数の集合のうち通信フェーズに対応する数との排他的論理和により、第２の識別子を生成し、
前記第２の識別子を有するスイッチに接続される情報処理装置との通信を行う、
処理を実行する情報処理方法。
【０１９２】
（付記６）
接続形態がフルメッシュである複数のスイッチと前記複数のスイッチのいずれかにそれぞれ接続される複数の情報処理装置とを含むフルメッシュシステムが複数のスパインスイッチにより複数連結された情報処理システムであって、
複数の前記フルメッシュシステムの各々における前記複数の情報処理装置の各々が、
自情報処理装置を収容する第１のリーフスイッチに接続されるスパインスイッチに接続され且つ前記第１のリーフスイッチが含まれるフルメッシュシステムとは異なるフルメッシュシステムに含まれる第２のリーフスイッチに接続される情報処理装置との通信を行う第１通信部と、
前記第１のリーフスイッチに収容される他の情報処理装置との通信を行う第２通信部と、
前記第１のリーフスイッチの識別子である第１の識別子と、前記自情報処理装置に割り当てられた一次独立な数の集合のうち通信フェーズに対応する数との排他的論理和により、第２の識別子を生成する生成部と、
前記第２の識別子を有し且つ前記自情報処理装置と同じフルメッシュシステムに含まれるリーフスイッチに収容される情報処理装置との通信を行う第３通信部とを有する、
情報処理システム。
【符号の説明】
【０１９３】
１０１  処理部    １０３  通信表格納部
１０５  ビット列生成部    １０１１  第１通信部
１０１３  第２通信部    １０１５  第３通信部
１０１７  第４通信部    １０１９  第５通信部
３  管理装置    ３０１  通信表生成部
３０３  通信表格納部    ３０５  トポロジデータ格納部
１０００，３０００  単層フルメッシュシステム
２０００  多層フルメッシュシステム
【図１】
2019008648.tif 000003
【図２】
2019008648.tif 000004
【図３】
2019008648.tif 000005
【図４】
2019008648.tif 000006
【図５】
2019008648.tif 000007
【図６】
2019008648.tif 000008
【図７】
2019008648.tif 000009
【図８】
2019008648.tif 000010
【図９】
2019008648.tif 000011
【図１０】
2019008648.tif 000012
【図１１】
2019008648.tif 000013
【図１２】
2019008648.tif 000014
【図１３】
2019008648.tif 000015
【図１４】
2019008648.tif 000016
【図１５】
2019008648.tif 000017
【図１６】
2019008648.tif 000018
【図１７】
2019008648.tif 000019
【図１８】
2019008648.tif 000020
【図１９】
2019008648.tif 000021
【図２０】
2019008648.tif 000022
【図２１】
2019008648.tif 000023
【図２２】
2019008648.tif 000024
【図２３】
2019008648.tif 000025
【図２４】
2019008648.tif 000026
【図２５】
2019008648.tif 000027
【図２６】
2019008648.tif 000028
【図２７】
2019008648.tif 000029
【図２８】
2019008648.tif 000030
【図２９】
2019008648.tif 000031
【図３０Ａ】
2019008648.tif 000032
【図３０Ｂ】
2019008648.tif 000033
【図３０Ｃ】
2019008648.tif 000034
【図３１】
2019008648.tif 000035
【図３２】
2019008648.tif 000036
【図３３】
2019008648.tif 000037
【図３４】
2019008648.tif 000038
【図３５】
2019008648.tif 000039
【図３６】
2019008648.tif 000040
【図３７】
2019008648.tif 000041
【図３８】
2019008648.tif 000042
【図３９】
2019008648.tif 000043
【図４０】
2019008648.tif 000044