(57)【要約】      （修正有）【課題】All-to-all通信が行われるファットツリー型のシステムにおいて、通信の信頼性を向上させる。【解決手段】経路データ生成装置は、データ格納部と、複数のスイッチがツリー状に接続されるシステムであり、ツリーの末端に位置する複数の末端スイッチと、システムにおいて複数の末端スイッチより上位に位置する複数の上位スイッチとの間の通信経路を定義する経路データを、複数の末端スイッチのうち第１の末端スイッチに接続された第１のノードから複数の末端スイッチのうち第２の末端スイッチに接続された第２のノードへの通信データが経由する上位スイッチと、第２のノードから第１のノードへの通信データが経由する上位スイッチとが一致するように生成し、データ格納部に格納する生成部と、を有する。【選択図】図２
2015169987.tif 000002
【特許請求の範囲】
【請求項１】
データ格納部と、
複数のスイッチがツリー状に接続されるシステムにおいて前記ツリーの末端に位置する複数の末端スイッチと、前記システムにおいて前記複数の末端スイッチより上位に位置する複数の上位スイッチとの間の通信経路を定義する経路データを、前記複数の末端スイッチのうち第１の末端スイッチに接続された第１のノードから前記複数の末端スイッチのうち第２の末端スイッチに接続された第２のノードへの通信データが経由する上位スイッチと、前記第２のノードから前記第１のノードへの通信データが経由する上位スイッチとが一致するように生成し、前記データ格納部に格納する生成部と、
を有する経路データ生成装置。
【請求項２】
前記システムが起動された場合、前記データ格納部に格納された前記経路データを用いて、前記複数の上位スイッチ及び前記複数の末端スイッチに対し、前記複数の上位スイッチ及び前記複数の末端スイッチが実行するルーティングについての設定をする設定部、
をさらに有する請求項１記載の経路データ生成装置。
【請求項３】
前記第１のノードが送信する通信データの宛先のノードが接続された末端スイッチと、前記第１の末端スイッチに接続された他のノードが送信する通信データの宛先のノードが接続された末端スイッチとが、各送信時点において異なる
ことを特徴とする請求項２記載の経路データ生成装置。
【請求項４】
前記経路データは、行方向及び列方向の位置が前記複数の末端スイッチの識別情報により特定され且つ要素が前記複数の上位スイッチの識別情報である行列のデータであり、
前記生成部は、
１の行における複数の要素の中に同じ要素が無く且つ１の列における複数の要素の中に同じ要素が無いという第１の条件と、行方向における末端スイッチの識別情報と列方向における末端スイッチの識別情報とが同じである要素を対象軸とした場合に線対称の位置にある２つの要素が同じであるという第２の条件とを満たすように、前記経路データを生成する
ことを特徴とする請求項１乃至３のいずれか１つ記載の経路データ生成装置。
【請求項５】
複数のスイッチがツリー状に接続されるシステムにおいて前記ツリーの末端に位置する複数の末端スイッチと、前記システムにおいて前記複数の末端スイッチより上位に位置する複数の上位スイッチとの間の通信経路を定義する経路データを、前記複数の末端スイッチのうち第１の末端スイッチに接続された第１のノードから前記複数の末端スイッチのうち第２の末端スイッチに接続された第２のノードへの通信データが経由する上位スイッチと、前記第２のノードから前記第１のノードへの通信データが経由する上位スイッチとが一致するように生成し、
生成された前記経路データをデータ格納部に格納する、
処理をコンピュータが実行する経路データ生成方法。
【請求項６】
複数のスイッチがツリー状に接続されるシステムにおいて前記ツリーの末端に位置する複数の末端スイッチと、前記システムにおいて前記複数の末端スイッチより上位に位置する複数の上位スイッチとの間の通信経路を定義する経路データを、前記複数の末端スイッチのうち第１の末端スイッチに接続された第１のノードから前記複数の末端スイッチのうち第２の末端スイッチに接続された第２のノードへの通信データが経由する上位スイッチと、前記第２のノードから前記第１のノードへの通信データが経由する上位スイッチとが一致するように生成し、
生成された前記経路データをデータ格納部に格納する、
処理をコンピュータに実行させるための経路データ生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路データ生成装置、経路データ生成方法及び経路データ生成プログラムに関する。
【背景技術】
【０００２】
All-to-all通信は、ネットワークに接続されたノードの各々が、ネットワークに接続された全ノード（そのノード自身を含む）について通信データの送信及び受信をする集合通信である。All-to-all通信は、通信データのサイズ或いはネットワークトポロジによって適切な通信アルゴリズムが異なる。例えば、通信データのサイズが一般的な通信データのサイズより小さい場合には、通信遅延及び通信回数がボトルネックになる。そのため、通信遅延が生じにくく且つ通信回数を少なくすることができる通信アルゴリズムが選択される。また、通信データのサイズが一般的な通信データのサイズより大きい場合には、通信帯域の幅がボトルネックになる。そのため、通信帯域の幅を広く確保できる通信アルゴリズムが選択される。
【０００３】
All-to-all通信に関して、以下のような技術が知られている。具体的には、並列計算機内の各計算機について、通信待ちになることがないように各フェーズにおける通信相手を決定することで、通信の高速化を図る。
【０００４】
また、All-to-all通信に関して、以下のような技術も知られている。具体的には、マルチコアＰＣ（Personal Computer）クラスタにおけるネットワークスイッチ内で発生するＨｏＬ（Head-of-Line）ブロッキングを回避するため、Ｒｉｎｇアルゴリズムではなく２−Ｌｅｖｅｌ  Ｒｉｎｇアルゴリズムを採用する。これにより、ＨｏＬブロッキングを回避し、All-to-all通信を行う場合にネットワークの利用効率が低下するのを防ぐ。
【０００５】
All-to-all通信は、ファットツリーと呼ばれるネットワークトポロジを採用する、ファットツリー型のシステムにおいても行われる。ファットツリー型のシステムとは、例えば図１に示すように、ネットワークスイッチが多段に接続され、最上位のネットワークスイッチが複数設けられたシステムである。図１の例においては、ファットツリーの末端の位置にＬｅａｆスイッチ１乃至３が配置され、Ｌｅａｆスイッチ１乃至３より上位のネットワークスイッチとしてＳｐｉｎｅスイッチ１乃至３が配置されている。Ｌｅａｆスイッチ１乃至３の各々には、ノードが接続されている。具体的には、Ｌｅａｆスイッチ１にノード０乃至２が接続され、Ｌｅａｆスイッチ２にノード３乃至５が接続され、Ｌｅａｆスイッチ３にノード６乃至８が接続されている。ノード間で交換される通信データは、Ｓｐｉｎｅスイッチ１乃至３のいずれかを経由するようになっている。
【０００６】
このようなファットツリー型のシステムにおいては、All-to-all通信の通信アルゴリズムが適切でないとネットワークスイッチに障害が発生した際の影響範囲が大きくなる。しかし、上記の従来技術は、このような点には着目していない。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開平１１−１１０３６２号公報
【非特許文献】
【０００８】
【非特許文献１】成瀬彰，中島耕太，住元真司，久門耕一，「マルチコアPCクラスタ向けAll-to-all通信アルゴリズムの提案と評価」，先進的計算基盤システムシンポジウムSACSIS2010論文集，p.311-318，平成２２年５月
【発明の概要】
【発明が解決しようとする課題】
【０００９】
従って、本発明の目的は、１つの側面では、All-to-all通信が行われるファットツリー型のシステムにおいて、通信の信頼性を向上させるための技術を提供することである。
【課題を解決するための手段】
【００１０】
本発明に係る経路データ生成装置は、データ格納部と、複数のスイッチがツリー状に接続されるシステムにおいてツリーの末端に位置する複数の末端スイッチと、システムにおいて複数の末端スイッチより上位に位置する複数の上位スイッチとの間の通信経路を定義する経路データを、複数の末端スイッチのうち第１の末端スイッチに接続された第１のノードから複数の末端スイッチのうち第２の末端スイッチに接続された第２のノードへの通信データが経由する上位スイッチと、第２のノードから第１のノードへの通信データが経由する上位スイッチとが一致するように生成し、データ格納部に格納する生成部とを有する。
【発明の効果】
【００１１】
１つの側面では、All-to-all通信が行われるファットツリー型のシステムにおいて、通信の信頼性を向上させることができるようになる。
【図面の簡単な説明】
【００１２】
【図１】図１は、ファットツリー型のシステムの一例を示す図である。
【図２】図２は、ファットツリー型のシステムにおいて行われるAll-to-all通信について説明するための図である。
【図３】図３は、ファットツリー型のシステムにおいて行われるAll-to-all通信について説明するための図である。
【図４】図４は、ファットツリー型のシステムにおいて行われるAll-to-all通信について説明するための図である。
【図５】図５は、経路データ生成装置の機能ブロック図である。
【図６】図６は、経路データに従って構築されるシステムの一例を示す図である。
【図７】図７は、ノードの機能ブロック図である。
【図８】図８は、ルーティングについて説明するための図である。
【図９】図９は、経路データ生成装置が実行する処理の概要を説明するための図である。
【図１０】図１０は、経路データ生成装置が実行する処理の概要を説明するための図である。
【図１１】図１１は、経路データ生成装置が実行する処理の処理フローを示す図である。
【図１２】図１２は、Ｓｐｉｎｅスイッチ決定処理の処理フローを示す図である。
【図１３】図１３は、経路データ生成装置が実行する処理のためのプログラムの一例を示す図である。
【図１４】図１４は、Ｓｐｉｎｅスイッチ決定処理を実行するためのプログラムの一例を示す図である。
【図１５】図１５は、経路データ生成装置が実行する処理を具体的に説明するための図である。
【図１６】図１６は、経路データ生成装置が実行する処理を具体的に説明するための図である。
【図１７】図１７は、経路データ生成装置が実行する処理を具体的に説明するための図である。
【図１８】図１８は、ネットワーク管理部が実行する処理の処理フローを示す図である。
【図１９】図１９は、ノードの識別情報の割り当てについて説明するための図である。
【図２０】図２０は、ノードが実行する処理の処理フローを示す図である。
【図２１】図２１は、ノードが実行する処理のためのプログラムの一例を示す図である。
【図２２】図２２は、各フェーズにおける宛先のノードを各ノードについて示す図である。
【図２３】図２３は、Ｓｐｉｎｅスイッチの増加について説明するための図である。
【図２４】図２４は、Ｓｐｉｎｅスイッチの増加について説明するための図である。
【図２５】図２５は、コンピュータの機能ブロック図である。
【発明を実施するための形態】
【００１３】
図２乃至図４を用いて、ファットツリー型のシステムにおいて行われるAll-to-all通信について説明する。まず、図２を用いて、通信経路の競合を回避するための仕組みについて簡単に説明する。図２に示したシステムは、図１に示したシステムと同じ構成を有している。矢印は、Ｌｅａｆスイッチ１の配下にあるノードがＬｅａｆスイッチ２の配下にあるノード及びＬｅａｆスイッチ３の配下にあるノードに通信データを送信する場合の通信経路を表している。実線の矢印はノード４及びノード７に通信データを送信する場合の通信経路を表し、一点鎖線の矢印はノード３及びノード６に通信データを送信する場合の通信経路を表し、二点鎖線の矢印はノード５及びノード８に通信データを送信する場合の通信経路を表す。
【００１４】
ノード４及びノード７に通信データを送信する場合の通信経路は、Ｓｐｉｎｅスイッチ２を通るため、ノード４及びノード７とＳｐｉｎｅスイッチ２とは同じ模様が付されている。ノード３及びノード６に通信データを送信する場合の通信経路は、Ｓｐｉｎｅスイッチ１を通るため、ノード３及びノード６とＳｐｉｎｅスイッチ１とは同じ模様が付されている。ノード５及びノード８に通信データを送信する場合の通信経路は、Ｓｐｉｎｅスイッチ３を通るため、ノード５及びノード８とＳｐｉｎｅスイッチ３とは同じ模様が付されている。
【００１５】
このように、ファットツリー型のシステムにおいては、経由するＳｐｉｎｅスイッチを宛先に応じて変えるような通信アルゴリズム（例えば、ラウンドロビン）を採用することで、通信経路の競合を避け、通信性能の劣化を防ぐことができる。
【００１６】
図２に示したシステムにおいて行われるAll-to-all通信について、図３を用いてより詳細に説明する。図３においては、ｎ（図３の例では、ｎ＝９）ノードの間での通信データの交換がｎフェーズで実施される。番号がｋ（ｋは０以上８以下の整数）であるノードは、フェーズｉ（ｉは０以上８以下の整数）において番号が「（ｋ＋ｉ）をｎで割った余り」（以下では、（ｋ＋ｉ）％ｎのように表す）であるノードに通信データを送信する。
【００１７】
例えば、ノード２は、フェーズ０においてノード２に通信データを送信し、フェーズ１においてノード３に通信データを送信し、フェーズ２においてノード４に通信データを送信し、フェーズ３においてノード５に通信データを送信し、フェーズ４においてノード６に通信データを送信し、フェーズ５においてノード７に通信データを送信し、フェーズ６においてノード８に通信データを送信し、フェーズ７においてノード０に通信データを送信し、フェーズ８においてノード１に通信データを送信する。なお、図３に示したような通信態様は、シフト通信パターンと呼ばれる。
【００１８】
このようにすることで、同じＬｅａｆスイッチの配下にある複数のノードが同一フェーズで送信した通信データは、異なるＳｐｉｎｅスイッチを経由するようになる。これにより、複数のノードが各フェーズにおいて同時に通信データを送信する場合においても通信経路の競合を避け、通信性能の劣化を防ぐことができる。
【００１９】
但し、図２及び図３を用いて説明した方法だと、通信データの往路と復路とが異なる。例えば図４に示すように、ノード０がノード８に送信した通信データはＳｐｉｎｅスイッチ３を経由するが、ノード８がノード０に送信した通信データはＳｐｉｎｅスイッチ１を経由する。そのため、Ｓｐｉｎｅスイッチ１及びＳｐｉｎｅ３のいずれかが故障すると、ノード０とノード８との間で通信を行うことができなくなる。
【００２０】
そこで、以下では、ファットツリー型のシステムにおいて行われるAll-to-all通信において、経路競合を避けることで高速性を維持しつつ、信頼性及び保守性を確保する方法について説明する。
【００２１】
図５に、本実施の形態における経路データ生成装置１の機能ブロック図を示す。経路データ生成装置１は、Ｓｐｉｎｅスイッチ決定部１１、データ管理部１２及び順序決定部１３を有する経路データ生成部１０と、経路データ格納部１４と、ネットワーク管理部１５とを有する。
【００２２】
経路データは、行と列とが規定された行列のデータである。順序決定部１３は、経路データにおける複数の要素のうちどの要素を次に処理するか決定し、Ｓｐｉｎｅスイッチ決定部１１を呼び出す。Ｓｐｉｎｅスイッチ決定部１１は、順序決定部１３からの呼び出しに応じ、Ｓｐｉｎｅスイッチの識別情報を決定し、データ管理部１２に出力する。データ管理部１２は、Ｓｐｉｎｅスイッチ決定部１１から受け取ったＳｐｉｎｅスイッチの識別情報を用いて、経路データ格納部１４に格納された経路データを更新する。
【００２３】
経路データ格納部１４に格納された経路データは、経路データ生成装置１の表示装置（図示せず）に表示される。管理者等は、経路データの内容を確認すると、経路データに従ってファットツリー型のシステムを構築する。例えば、Ｌｅａｆスイッチ１の配下にあるノード０とＬｅａｆスイッチ２の配下にあるノード４との間の通信データがＳｐｉｎｅスイッチ１を経由する場合には、Ｌｅａｆスイッチ１とＳｐｉｎｅスイッチ１とをケーブルで接続し、Ｌｅａｆスイッチ２とＳｐｉｎｅスイッチ１とをケーブルで接続する。
【００２４】
ネットワーク管理部１５は、経路データに従って構築されたファットツリー型システムが起動した場合、経路データ格納部１４に格納された経路データに基づき、ファットツリー型システム内のＳｐｉｎｅスイッチ及びＬｅａｆスイッチに対し、ルーティングについての設定を行う。
【００２５】
図６に、経路データ格納部１４に格納された経路データに従って構築されるシステムの一例を示す。ファットツリー型システム１００は、例えばＬＡＮスイッチ（Local Area Network）であるＳｐｉｎｅスイッチ１０１乃至１０３と、例えばＬＡＮスイッチであるＬｅａｆスイッチ１１１乃至１１３と、ノード１１１１乃至１１１３と、ノード１１２１乃至１１２３と、ノード１１３１乃至１１３３とを有する。Ｌｅａｆスイッチ１１１乃至１１３は、ファットツリーの末端に位置するスイッチであり、Ｓｐｉｎｅスイッチ１０１乃至１０３は、Ｌｅａｆスイッチの上位に位置するスイッチである。なお、Ｓｐｉｎｅスイッチ及びＬｅａｆスイッチの数は３であり、ノードの数は９であるが、数に限定は無い。
【００２６】
ファットツリー型システム１００における各装置は、インフィニバンド（InfiniBand）のネットワークを介して接続される。ノード１１１１乃至１１１３はＬｅａｆスイッチ１１１に接続され、ノード１１２１乃至１１２３はＬｅａｆスイッチ１１２に接続され、ノード１１３１乃至１１３３はＬｅａｆスイッチ１１３に接続される。Ｌｅａｆスイッチ１１１乃至１１３の各々は、Ｓｐｉｎｅスイッチ１０１乃至１０３に接続される。但し、Ｓｐｉｎｅスイッチ１０１乃至１０３とＬｅａｆスイッチ１１１乃至１１３との間の接続は一例である。
【００２７】
ファットツリー型システム１００におけるノードは、ＭＰＩ（Message Passing Interface）等の通信ライブラリを使用して通信を行う計算機である。図７に、ノード１１１１の機能ブロック図を示す。ノード１１１１は、宛先決定部１２００と、宛先データ格納部１３００とを有する。宛先決定部１２００は、各フェーズにおける宛先のノードを決定し、決定内容を示すデータを宛先データ格納部１３００に格納する。ファットツリー型システム１００における、ノード１１１１以外のノードの機能ブロック図は、ノード１１１１の機能ブロック図と同じであるので、説明を省略する。
【００２８】
All-to-all通信のような集合通信が行われるシステムにおいては、通信経路の競合を回避するため、規則的且つ固定的なルーティングが行われるインフィニバンドのネットワークが利用される。図８を用いて、ファットツリー型システム１００におけるルーティングについて説明する。図８において、丸の図形はノードを表し、正方形の図形はスイッチを表す。線分はインフィニバンドのネットワークを表し、線分の傍にある数値は宛先のノードの識別情報を表す。太い実線の矢印はパケットの経路を表す。
【００２９】
図８においては、ノード３が、宛先がノード１であるパケットを送信する。パケットのヘッダには、宛先の識別情報（例えばＬＩＤ（Local IDentifier））が含まれる。各スイッチにおける各出力ポートには宛先のノードの識別情報が対応付けられているので、各スイッチは、パケットのヘッダに含まれる宛先の識別情報に対応する出力ポートにパケットを出力する。図８の例では、パケットはスイッチＣ、スイッチＢ及びスイッチＡを経由してノード１に到達する。
【００３０】
すなわち、ファットツリー型システム１００のネットワークは、イーサネット（登録商標）のように自動的に経路が行われるネットワークではなく、規則的且つ固定的なルーティングが行われるネットワークである。
【００３１】
次に、図９乃至図２４を用いて、図６に示したシステムにおいて行われる処理について説明する。まず、図９乃至図１８を用いて、経路データ生成装置１が実行する処理について説明する。
【００３２】
図９を用いて、経路データ生成装置１が実行する処理の概要を説明する。経路データは、図９に示すように、行方向の位置は送信元のノードが接続されたＬｅａｆスイッチの識別情報によって特定され、列方向の位置は宛先のノードが接続されたＬｅａｆスイッチの識別情報によって特定され、且つ行列の要素がＳｐｉｎｅスイッチの識別情報であるデータである。
【００３３】
経路データ生成装置１における経路データ生成部１０は、制約条件１及び制約条件２を満たすように経路データを生成する。制約条件１は、或る一行の中に同じＳｐｉｎｅスイッチの識別情報が無く且つ或る１列の中に同じＳｐｉｎｅスイッチの識別情報が無いという条件である。制約条件２は、行方向におけるＬｅａｆスイッチの識別情報と列方向におけるＬｅａｆスイッチの識別情報とが同じである要素を対象軸とした場合に線対称の位置にある２つの要素が同じであるという条件である。
【００３４】
このような経路データを生成すると、往路の通信データが経由するＳｐｉｎｅスイッチと、復路の通信データが経由するＳｐｉｎｅスイッチとが同じになる。図１０に具体例を示す。図１０の例においては、Ｌｅａｆスイッチ１の配下にあるノードと、Ｌｅａｆスイッチ２の配下にあるノードとが通信をしている。この場合には、往路の通信データ及び復路の通信データは共にＳｐｉｎｅスイッチ１を経由し、その他のＳｐｉｎｅスイッチを経由しない。また、図９に示した経路データに従ってルーティングについての設定が行われると、Ｌｅａｆスイッチ１の配下にあるノードとＬｅａｆスイッチ３の配下にあるノードとが通信をする場合には通信データはＳｐｉｎｅスイッチ３を経由し、Ｌｅａｆスイッチ２の配下にあるノードとＬｅａｆスイッチ３の配下にあるノードとが通信をする場合には通信データはＳｐｉｎｅスイッチ２を経由する。
【００３５】
次に、図１１乃至図１８を用いて、経路データ生成装置１が実行する処理を詳細に説明する。まず、順序決定部１３は、変数ｉの値を１に設定し（図１１：ステップＳ１）、ｉ＜ｓｉｚｅが満たされるか判断する（ステップＳ３）。ｓｉｚｅは、Ｌｅａｆスイッチの数を表す値であり、例えば図１０の例では、ｓｉｚｅ＝３である。
【００３６】
ｉ＜ｓｉｚｅが満たされない場合（ステップＳ３：Ｎｏルート）、処理を終了する。一方、ｉ＜ｓｉｚｅが満たされる場合（ステップＳ３：Ｙｅｓルート）、順序決定部１３は、ｘ１の値をｉに設定し、ｙ１の値を０に設定し、ｘ２の値をｓｉｚｅ−１に設定し、ｙ２の値をｓｉｚｅ−１−ｉに設定する（ステップＳ５）。ここで、ｘ１及びｘ２は経路データにおける列方向の位置を特定するための変数であり、ｙ１及びｙ２は経路データにおける行方向の位置を特定するための変数である。
【００３７】
順序決定部１３は、経路データにおける（ｘ１，ｙ１）の要素を決定済みであるか判断する（ステップＳ７）。決定済みである場合（ステップＳ７：Ｙｅｓルート）、次のｉについて処理するため、順序決定部１３は、ｉの値を１インクリメントする（ステップＳ１９）。そしてステップＳ３の処理に戻る。
【００３８】
一方、決定済みではない場合（ステップＳ７：Ｎｏルート）、順序決定部１３は、Ｓｐｉｎｅスイッチ決定部１１を呼び出す。そして、Ｓｐｉｎｅスイッチ決定部１１は、（ｘ１，ｙ１）についてＳｐｉｎｅスイッチ決定処理を実行する（ステップＳ９）。Ｓｐｉｎｅスイッチ決定処理については、図１２を用いて説明する。
【００３９】
まず、Ｓｐｉｎｅスイッチ決定部１１は、Ｓｐｉｎｅスイッチの識別情報を１に設定し（図１２：ステップＳ２１）、同じ行における識別情報のいずれかと一致するか判断する（ステップＳ２３）。ここで、「同じ行」とは、行方向の位置がｙ１である行である。
【００４０】
同じ行における識別情報のいずれかと一致する場合（ステップＳ２３：Ｙｅｓルート）、その識別情報を使用することはできないので、Ｓｐｉｎｅスイッチ決定部１１は、その識別情報を１インクリメントする（ステップＳ２７）。そしてステップＳ２３の処理に戻る。
【００４１】
一方、同じ行における識別情報のいずれとも一致しない場合（ステップＳ２３：Ｎｏルート）、Ｓｐｉｎｅスイッチ決定部１１は、同じ列における識別情報のいずれかと一致するか判断する（ステップＳ２５）。ここで、「同じ列」とは、列方向の位置がｘ１である列である。
【００４２】
同じ列における識別情報のいずれかと一致する場合（ステップＳ２５：Ｙｅｓルート）、その識別情報を使用することはできないので、Ｓｐｉｎｅスイッチ決定部１１は、その識別情報を１インクリメントする（ステップＳ２７）。そしてステップＳ２３の処理に戻る。
【００４３】
一方、同じ列における識別情報のいずれとも一致しない場合（ステップＳ２５：Ｎｏルート）、その識別情報を使用することができるので、その識別情報並びにｘ１及びｙ１の値をデータ管理部１２に出力する。そして呼び出し元の処理に戻る。なお、データ管理部１２は、経路データ格納部１４に格納された経路データにおける（ｘ１，ｙ１）の要素を、Ｓｐｉｎｅスイッチ決定部１１から受け取った識別情報に設定する。
【００４４】
以上のような処理を実行すれば、制約条件１を満たすようにＳｐｉｎｅスイッチの識別情報を決定できるようになる。
【００４５】
図１１の説明に戻り、順序決定部１３は、（ｘ１，ｙ１）及び（ｙ１，ｘ１）に、Ｓｐｉｎｅスイッチ決定処理において決定されたＳｐｉｎｅスイッチの識別情報を割り当てる（ステップＳ１０）。
【００４６】
順序決定部１３は、ｘ１及びｙ１を１インクリメントする（ステップＳ１１）。
【００４７】
順序決定部１３は、経路データにおける（ｘ２，ｙ２）の要素を決定済みであるか判断する（ステップＳ１３）。決定済みである場合（ステップＳ１３：Ｙｅｓルート）、次のｉについて処理するため、順序決定部１３は、ｉの値を１インクリメントする（ステップＳ１９）。そしてステップＳ３の処理に戻る。
【００４８】
一方、決定済みではない場合（ステップＳ１３：Ｎｏルート）、順序決定部１３は、Ｓｐｉｎｅスイッチ決定部１１を呼び出す。そして、Ｓｐｉｎｅスイッチ決定部１１は、（ｘ２，ｙ２）についてＳｐｉｎｅスイッチ決定処理を実行する（ステップＳ１５）。Ｓｐｉｎｅスイッチ決定処理については、図１２を用いて説明したとおりである。
【００４９】
順序決定部１３は、（ｘ２，ｙ２）及び（ｙ２，ｘ２）に、Ｓｐｉｎｅスイッチ決定処理において決定されたＳｐｉｎｅスイッチの識別情報を割り当てる（ステップＳ１６）。
【００５０】
順序決定部１３は、ｘ２及びｙ２を１デクリメントする（ステップＳ１７）。そしてステップＳ７の処理に戻る。
【００５１】
なお、図１１を用いて説明した処理を実行するためのプログラムは、例えば図１３に示すようなプログラムである。また、図１２を用いて説明した処理を実行するためのプログラムは、例えば図１４に示すようなプログラムである。
【００５２】
図１５乃至図１７を用いて、図１１及び図１２を用いて説明した処理をより具体的に説明する。
【００５３】
図１５を用いて、要素が処理される順序について説明する。図１５において、円で囲まれた数字は処理される順番を表し、矢印は処理の対象の遷移を表す。実線の矢印は、図１３に示したプログラムにおいてｗｈｉｌｅ文のループから脱出していないことを表し、点線の矢印は、図１３に示したプログラムにおいてｗｈｉｌｅ文のループから脱出したことを表す。
【００５４】
ｓｉｚｅ＝５であるシステムについて実行すると、図１５に示すように、（ｘ１，ｙ１）は（１，０）→（２，１）→（２，０）→（３，１）→（３，０）→（４，０）と遷移し、（ｘ２，ｙ２）は（４，３）→（３，２）→（４，２）→（４，１）と遷移する。
【００５５】
また、行方向におけるＬｅａｆスイッチの識別情報と列方向におけるＬｅａｆスイッチの識別情報とが同じである要素を対象軸とした場合に線対称の位置にある要素は、同じ順番で処理される。従って、経路データ全体は、図１６に示す順番で処理される。
【００５６】
そして、図１２を用いて説明した処理によってＳｐｉｎｅスイッチの識別情報を決定すると、最終的には、図１７に示すような経路データが生成される。
【００５７】
経路データ格納部１４に格納された経路データは、経路データ生成装置１の表示装置（図示せず）に表示される。管理者等は、経路データの内容を確認すると、経路データに従ってファットツリー型システム１００を構築する。
【００５８】
経路データに従って構築されたファットツリー型システム１００が起動した場合、ネットワーク管理部１５は、図１８に示すような処理を実行する。
【００５９】
まず、ネットワーク管理部１５は、ファットツリー型システム１００が起動したことを検出する（図１８：ステップＳ３１）。
【００６０】
ネットワーク管理部１５は、経路データ格納部１４に格納された経路データに基づき、ファットツリー型システム１００内のＳｐｉｎｅスイッチ及びＬｅａｆスイッチに対し、ルーティングについての設定を行う（ステップＳ３３）。そして処理を終了する。
【００６１】
以上のような処理を実行すれば、往路の通信データが経由するＳｐｉｎｅスイッチと、復路の通信データが経由するＳｐｉｎｅスイッチとが同じになるので、Ｓｐｉｎｅスイッチに障害が発生した際の影響範囲が小さくなる。よって、通信の信頼性を向上させることができるようになる。
【００６２】
また、２つのＬｅａｆスイッチに関係するＳｐｉｎｅスイッチの数が１つになるので、保守が容易になる。
【００６３】
次に、図１９乃至図２２を用いて、通信経路の競合を回避するための処理について説明する。なお、本実施の形態においては、ノードに対する識別情報の割り当てを図２に示したように単純に行うのではなく、図１９に示したように識別情報を割り当てる。具体的には、Ｌｅａｆスイッチ１にノード０、ノード３及びノード６が接続され、Ｌｅａｆスイッチ２にノード１、ノード４及びノード７が接続され、Ｌｅａｆスイッチ３にノード２、ノード５及びノード８が接続される。
【００６４】
そして、ファットツリー型システム１００におけるノード１１１１は、以下のような処理を実行する。まず、ノード１１１１における宛先決定部１２００は、ファットツリー型システム１００におけるノードのうち未処理のノードを１つ特定する（図２０：ステップＳ４１）。
【００６５】
宛先決定部１２００は、ステップＳ４１において特定されたノードについて、各フェーズにおける宛先のノードを決定し、宛先のノードを示すデータを宛先データ格納部１３００に格納する（ステップＳ４３）。ステップＳ４３において、第ｉ（ｉは０以上８以下の整数）フェーズにおける宛先のノードの識別情報は、（ｄ＊ｏｆｆｓｅｔ＋（ｓｅｌｆ＋（ｏｆｆｓｅｔ＋ｉ／ｄ＋ｉ）％ｄ）％ｄ＋ｄ＊（ｉ／ｄ））％ｎにより求められる。ここで、ｓｅｌｆは、図１９で説明したように定められた自ノードの識別情報であり、ｎはノード数であり、ｄは次数（ｎ＝ｄ2）であり、ｏｆｆｓｅｔは例えば図２２に示した値である。また、ｉ／ｄの小数部分を切り捨てる。図２２については後で説明する。
【００６６】
宛先決定部１２００は、未処理のノードが有るか判断する（ステップＳ４５）。未処理のノードが有る場合（ステップＳ４５：Ｙｅｓルート）、次のノードについて処理するため、ステップＳ４１の処理に戻る。一方、未処理のノードが無い場合（ステップＳ４５：Ｎｏルート）、処理を終了する。
【００６７】
そして、ノード１１１１は、宛先データ格納部１３００に格納されたデータをノード１１１１以外のデータに配布する。これによって、ノード１１１１以外のノードも適切に通信データを送信できるようになる。
【００６８】
なお、ここではノード１１１１がファットツリー型システム１００内の全ノードについてステップＳ４３の処理を実行する例を説明したが、ファットツリー型システム１００内の各ノードがそのノードのみについてステップＳ４３の処理を実行するようにしてもよい。
【００６９】
図２０を用いて説明した処理を実行するためのプログラムは、例えば図２１に示すようなプログラムである。
【００７０】
図２２に、ステップＳ４３の処理によって求められた宛先を示す。ノード０とノード３とノード６とには同じ模様が付され、ノード１とノード４とノード７とには同じ模様が付され、ノード２とノード５とノード８とには同じ模様が付されている。オフセットの値は、ノード０、ノード１及びノード２は０であり、ノード３、ノード４及びノード５は１であり、ノード６、ノード７及びノード８は２である。図２２に示したように、各フェーズにおいて、１つのＬｅａｆスイッチの配下にある複数のノードから送信された通信データは、それぞれ別のＬｅａｆスイッチに転送される。例えば、フェーズ２において、ノード０はＬｅａｆスイッチ３の配下にあるノード２に通信データを送信し、ノード３はＬｅａｆスイッチ１の配下にあるノード３に通信データを送信し、ノード６はＬｅａｆスイッチ２の配下にあるノード７に通信データを送信する。従って、通信経路の競合を回避できるようになる。
【００７１】
但し、本実施の形態の方法を用いると、Ｓｐｉｎｅスイッチの数が増えることになる。図２３に、Ｓｐｉｎｅスイッチの数と次数ｄとの関係を示す。図２３において、横軸は次数を表し、縦軸はＳｐｉｎｅスイッチの数を表す。実線は本実施の形態の方法を用いた場合におけるＳｐｉｎｅスイッチの数を表し、点線は本実施の形態の方法を用いない場合におけるＳｐｉｎｅスイッチの数を表す。図２３に示すように、次数が４である場合を除き、本実施の形態の方法を用いる方がＳｐｉｎｅスイッチの数が多くなる。
【００７２】
図２４に、Ｓｐｉｎｅスイッチの増加率と次数ｄとの関係を示す。Ｓｐｉｎｅスイッチの増加率は、（本実施の形態の方法を用いた場合におけるＳｐｉｎｅスイッチの数）／（本実施の形態の方法を用いない場合におけるＳｐｉｎｅスイッチの数）によって求められる。図２４において、横軸は次数を表し、縦軸はＳｐｉｎｅスイッチの増加率を表す。実線は本実施の形態の方法を用いた場合におけるＳｐｉｎｅスイッチの増加率を表し、点線は本実施の形態の方法を用いない場合におけるＳｐｉｎｅスイッチの増加率を表す。
【００７３】
図２４に示すように、次数が１８以下である場合、本実施の形態の方法を用いると、増加率は最大で１．２５である。よって、増加率の分だけ障害が発生する確率は増えることになる。しかし、本実施の形態の方法によれば、障害の影響範囲を１／２にすることができるので、全体としては、障害の発生率を下げることができるようになる。これにより、通信の信頼性を向上させることができる。
【００７４】
以上本発明の一実施の形態を説明したが、本発明はこれに限定されるものではない。例えば、上で説明した経路データ生成装置１及びノード１１１１の機能ブロック構成は実際のプログラムモジュール構成に一致しない場合もある。
【００７５】
また、上で説明した各テーブルの構成は一例であって、上記のような構成でなければならないわけではない。さらに、処理フローにおいても、処理結果が変わらなければ処理の順番を入れ替えることも可能である。さらに、並列に実行させるようにしても良い。
【００７６】
なお、上で述べた例では、ネットワーク管理部１５を経路データ生成装置１に設けているが、ファットツリー型システム１００内のＳｐｉｎｅスイッチ、Ｌｅａｆスイッチ又はノードに設けてもよい。この場合には、ネットワーク管理部１５は、経路データ生成装置１から受け取った経路データに従ってルーティングについての設定を行う。
【００７７】
また、ファットツリー型システム１００内のネットワークは、インフィニバンドのネットワークに限られない。インフィニバンドのように基本的に固定ルーティングであり且つルーティングの規則がインフィニバンドと同じであれば、インフィニバンド以外のネットワークであってもよい。
【００７８】
なお、上で述べた経路データ生成装置１及びノードは、コンピュータ装置であって、図２５に示すように、メモリ２５０１とＣＰＵ（Central Processing Unit）２５０３とハードディスク・ドライブ（ＨＤＤ：Hard Disk Drive）２５０５と表示装置２５０９に接続される表示制御部２５０７とリムーバブル・ディスク２５１１用のドライブ装置２５１３と入力装置２５１５とネットワークに接続するための通信制御部２５１７とがバス２５１９で接続されている。オペレーティング・システム（ＯＳ：Operating System）及び本実施例における処理を実施するためのアプリケーション・プログラムは、ＨＤＤ２５０５に格納されており、ＣＰＵ２５０３により実行される際にはＨＤＤ２５０５からメモリ２５０１に読み出される。ＣＰＵ２５０３は、アプリケーション・プログラムの処理内容に応じて表示制御部２５０７、通信制御部２５１７、ドライブ装置２５１３を制御して、所定の動作を行わせる。また、処理途中のデータについては、主としてメモリ２５０１に格納されるが、ＨＤＤ２５０５に格納されるようにしてもよい。本発明の実施例では、上で述べた処理を実施するためのアプリケーション・プログラムはコンピュータ読み取り可能なリムーバブル・ディスク２５１１に格納されて頒布され、ドライブ装置２５１３からＨＤＤ２５０５にインストールされる。インターネットなどのネットワーク及び通信制御部２５１７を経由して、ＨＤＤ２５０５にインストールされる場合もある。このようなコンピュータ装置は、上で述べたＣＰＵ２５０３、メモリ２５０１などのハードウエアとＯＳ及びアプリケーション・プログラムなどのプログラムとが有機的に協働することにより、上で述べたような各種機能を実現する。
【００７９】
以上述べた本発明の実施の形態をまとめると、以下のようになる。
【００８０】
本実施の形態の第１の態様に係る経路データ生成装置は、（Ａ）データ格納部と、（Ｂ）複数のスイッチがツリー状に接続されるシステムにおいてツリーの末端に位置する複数の末端スイッチと、システムにおいて複数の末端スイッチより上位に位置する複数の上位スイッチとの間の通信経路を定義する経路データを、複数の末端スイッチのうち第１の末端スイッチに接続された第１のノードから複数の末端スイッチのうち第２の末端スイッチに接続された第２のノードへの通信データが経由する上位スイッチと、第２のノードから第１のノードへの通信データが経由する上位スイッチとが一致するように生成し、データ格納部に格納する生成部とを有する。
【００８１】
第１のノードから第２のノードへの通信データが経由する上位スイッチと第２のノードから第１のノードへの通信データが経由する上位スイッチとが異なる場合には、いずれの上位スイッチに故障が発生したとしても通信を行うことができなくなる。そこで、上で述べたようにすれば、１つの上位スイッチしか経由しないので、通信の信頼性を向上させることができるようになる。
【００８２】
また、本経路データ生成装置は、（Ｃ）システムが起動された場合、データ格納部に格納された経路データを用いて、複数の上位スイッチ及び複数の末端スイッチに対し、複数の上位スイッチ及び複数の末端スイッチが実行するルーティングについての設定をする設定部をさらに有してもよい。このようにすれば、複数の末端スイッチ及び複数の上位スイッチが実際にルーティングを行えるようになる。
【００８３】
また、第１のノードが送信する通信データの宛先のノードが接続された末端スイッチと、第１の末端スイッチに接続された他のノードが送信する通信データの宛先のノードが接続された末端スイッチとが、各送信時点において異なっていてもよい。このようにすれば、通信経路の競合を避けることができるので、All-to-all通信の性能の劣化を防げるようになる。
【００８４】
また、上で述べた経路データは、行方向及び列方向の位置が複数の末端スイッチの識別情報により特定され且つ要素が複数の上位スイッチの識別情報である行列のデータであってもよい。そして、上で述べた生成部は、（ｂ１）１の行における複数の要素の中に同じ要素が無く且つ１の列における複数の要素の中に同じ要素が無いという第１の条件と、行方向における末端スイッチの識別情報と列方向における末端スイッチの識別情報とが同じである要素を対象軸とした場合に線対称の位置にある２つの要素が同じであるという第２の条件とを満たすように、経路データを生成してもよい。このようにすれば、往路の通信データが経由する上位スイッチと復路の通信データが経由する上位スイッチとを同じにすることができるようになる。
【００８５】
本実施の形態の第２の態様に係る経路データ生成方法は、（Ｄ）複数のスイッチがツリー状に接続されるシステムにおいてツリーの末端に位置する複数の末端スイッチと、システムにおいて複数の末端スイッチより上位に位置する複数の上位スイッチとの間の通信経路を定義する経路データを、複数の末端スイッチのうち第１の末端スイッチに接続された第１のノードから複数の末端スイッチのうち第２の末端スイッチに接続された第２のノードへの通信データが経由する上位スイッチと、第２のノードから第１のノードへの通信データが経由する上位スイッチとが一致するように生成し、（Ｅ）生成された経路データをデータ格納部に格納する処理を含む。
【００８６】
なお、上記方法による処理をコンピュータに行わせるためのプログラムを作成することができ、当該プログラムは、例えばフレキシブルディスク、ＣＤ−ＲＯＭ、光磁気ディスク、半導体メモリ、ハードディスク等のコンピュータ読み取り可能な記憶媒体又は記憶装置に格納される。尚、中間的な処理結果はメインメモリ等の記憶装置に一時保管される。
【００８７】
以上の実施例を含む実施形態に関し、さらに以下の付記を開示する。
【００８８】
（付記１）
データ格納部と、
複数のスイッチがツリー状に接続されるシステムにおいて前記ツリーの末端に位置する複数の末端スイッチと、前記システムにおいて前記複数の末端スイッチより上位に位置する複数の上位スイッチとの間の通信経路を定義する経路データを、前記複数の末端スイッチのうち第１の末端スイッチに接続された第１のノードから前記複数の末端スイッチのうち第２の末端スイッチに接続された第２のノードへの通信データが経由する上位スイッチと、前記第２のノードから前記第１のノードへの通信データが経由する上位スイッチとが一致するように生成し、前記データ格納部に格納する生成部と、
を有する経路データ生成装置。
【００８９】
（付記２）
前記システムが起動された場合、前記データ格納部に格納された前記経路データを用いて、前記複数の上位スイッチ及び前記複数の末端スイッチに対し、前記複数の上位スイッチ及び前記複数の末端スイッチが実行するルーティングについての設定をする設定部、
をさらに有する付記１記載の経路データ生成装置。
【００９０】
（付記３）
前記第１のノードが送信する通信データの宛先のノードが接続された末端スイッチと、前記第１の末端スイッチに接続された他のノードが送信する通信データの宛先のノードが接続された末端スイッチとが、各送信時点において異なる
ことを特徴とする付記２記載の経路データ生成装置。
【００９１】
（付記４）
前記経路データは、行方向及び列方向の位置が前記複数の末端スイッチの識別情報により特定され且つ要素が前記複数の上位スイッチの識別情報である行列のデータであり、
前記生成部は、
１の行における複数の要素の中に同じ要素が無く且つ１の列における複数の要素の中に同じ要素が無いという第１の条件と、行方向における末端スイッチの識別情報と列方向における末端スイッチの識別情報とが同じである要素を対象軸とした場合に線対称の位置にある２つの要素が同じであるという第２の条件とを満たすように、前記経路データを生成する
ことを特徴とする付記１乃至３のいずれか１つ記載の経路データ生成装置。
【００９２】
（付記５）
複数のスイッチがツリー状に接続されるシステムにおいて前記ツリーの末端に位置する複数の末端スイッチと、前記システムにおいて前記複数の末端スイッチより上位に位置する複数の上位スイッチとの間の通信経路を定義する経路データを、前記複数の末端スイッチのうち第１の末端スイッチに接続された第１のノードから前記複数の末端スイッチのうち第２の末端スイッチに接続された第２のノードへの通信データが経由する上位スイッチと、前記第２のノードから前記第１のノードへの通信データが経由する上位スイッチとが一致するように生成し、
生成された前記経路データをデータ格納部に格納する、
処理をコンピュータが実行する経路データ生成方法。
【００９３】
（付記６）
複数のスイッチがツリー状に接続されるシステムにおいて前記ツリーの末端に位置する複数の末端スイッチと、前記システムにおいて前記複数の末端スイッチより上位に位置する複数の上位スイッチとの間の通信経路を定義する経路データを、前記複数の末端スイッチのうち第１の末端スイッチに接続された第１のノードから前記複数の末端スイッチのうち第２の末端スイッチに接続された第２のノードへの通信データが経由する上位スイッチと、前記第２のノードから前記第１のノードへの通信データが経由する上位スイッチとが一致するように生成し、
生成された前記経路データをデータ格納部に格納する、
処理をコンピュータに実行させるための経路データ生成プログラム。
【符号の説明】
【００９４】
１  経路データ生成装置    １０  経路データ生成部
１１  Ｓｐｉｎｅスイッチ決定部    １２  データ管理部
１３  順序決定部    １４  経路データ格納部
１５  ネットワーク管理部    １００  ファットツリー型システム
１０１，１０２，１０３  Ｓｐｉｎｅスイッチ
１１１，１１２，１１３  Ｌｅａｆスイッチ
１１１１，１１１２，１１１３，１１２１，１１２２，１１２３，１１３１，１１３２，１１３３  ノード
１２００  宛先決定部    １３００  宛先データ格納部
【図１】
2015169987.tif 000003
【図２】
2015169987.tif 000004
【図３】
2015169987.tif 000005
【図４】
2015169987.tif 000006
【図５】
2015169987.tif 000007
【図６】
2015169987.tif 000008
【図７】
2015169987.tif 000009
【図８】
2015169987.tif 000010
【図９】
2015169987.tif 000011
【図１０】
2015169987.tif 000012
【図１１】
2015169987.tif 000013
【図１２】
2015169987.tif 000014
【図１３】
2015169987.tif 000015
【図１４】
2015169987.tif 000016
【図１５】
2015169987.tif 000017
【図１６】
2015169987.tif 000018
【図１７】
2015169987.tif 000019
【図１８】
2015169987.tif 000020
【図１９】
2015169987.tif 000021
【図２０】
2015169987.tif 000022
【図２１】
2015169987.tif 000023
【図２２】
2015169987.tif 000024
【図２３】
2015169987.tif 000025
【図２４】
2015169987.tif 000026
【図２５】
2015169987.tif 000027