(57)【要約】  本情報処理システムは、ｎ（ｎは３以上の自然数）次のハイパーキューブ状に接続されている２ｎ個のノードを有している。そして、上記２ｎ個のノードのうち所定の条件を満たす特定のノードの各々と他の特定のノードの各々との間にチャネルが設けられており、上記所定の条件が、直接接続されているノード間でハミング距離が１となるようにｎ桁の２進数のノード番号をノードの各々に対し付与した場合において、ノード番号の下１桁目及び下２桁目以外の桁の数値が全て一致するという条件である。
2012056547.tif 000002
【特許請求の範囲】
【請求項１】
ｎ（ｎは３以上の自然数）次のハイパーキューブ状に接続されている２ｎ個のノード
を有し、
前記２ｎ個のノードのうち所定の条件を満たす特定のノードの各々と他の前記特定のノードの各々との間にチャネルが設けられており、
前記所定の条件が、直接接続されているノード間でハミング距離が１となるようにｎ桁の２進数のノード番号を前記ノードの各々に対し付与した場合において、ノード番号の下１桁目及び下２桁目以外の桁の数値が全て一致するという条件である
情報処理システム。
【請求項２】
ｎ（ｎは３以上の自然数）次のハイパーキューブ状に接続されている２ｎ個のノードを有し、直接接続されているノード間でハミング距離が１となるようにｎ桁の２進数のノード番号が前記ノードの各々に対し付与されており且つノード番号の下１桁目及び下２桁目以外の桁の数値が全て一致するという第１の条件を満たす特定のノードの各々と他の前記特定のノードの各々との間にチャネルが設けられている情報処理システムにおける前記２ｎ個のノードのいずれかである第１のノードにより実行されるルーティング方法であって、
データを宛先ノードに送信する場合、前記第１のノードのノード番号の下１桁目の数値と宛先ノードのノード番号の下１桁目の数値とが異なっており且つ前記第１のノードのノード番号の下２桁目の数値と前記宛先ノードのノード番号の下２桁目の数値とが異なっているという第２の条件を満たすか判断するステップと、
前記第２の条件を満たすと判断された場合には、下１桁目の数値が前記第１のノードのノード番号の下１桁目の数値を反転させた数値であり、下２桁目の数値が前記第１のノードのノード番号の下２桁目の数値を反転させた数値であり且つノード番号の下１桁目及び下２桁目以外の桁の数値が前記第１のノードのノード番号の下１桁目及び下２桁目以外の桁の数値と同じであるノード番号が付与されているノードに対し、当該ノードと前記第１のノードとの間に設けられているチャネルを介して、前記宛先ノードに送信すべきデータを送信するステップと、
を含むルーティング方法。
【請求項３】
前記第２の条件を満たさないと判断された場合には、前記第１のノードのノード番号と前記宛先ノードのノード番号とを最上位桁から順に比較し、数値が一致しない桁のうち最上位の桁である第１の桁を特定するステップと、
前記第１のノードのノード番号における前記第１の桁の数値を反転させたノード番号が付与されているノードに対し、前記宛先ノードに送信すべきデータを送信するステップと、
をさらに含む請求項２記載のルーティング方法。
【請求項４】
ｎ（ｎは３以上の自然数）次のハイパーキューブ状に接続されている２ｎ個のノードを有し、直接接続されているノード間でハミング距離が１となるようにｎ桁の２進数のノード番号が前記ノードの各々に対し付与されており且つノード番号の下１桁目及び下２桁目以外の桁の数値が全て一致するという第１の条件を満たす特定のノードの各々と他の前記特定のノードの各々との間にチャネルが設けられている情報処理システムにおける前記２ｎ個のノードのいずれかである第１のノードに実行させるためのルーティングプログラムであって、
データを宛先ノードに送信する場合、前記第１のノードのノード番号の下１桁目の数値と宛先ノードのノード番号の下１桁目の数値とが異なっており且つ前記第１のノードのノード番号の下２桁目の数値と前記宛先ノードのノード番号の下２桁目の数値とが異なっているという第２の条件を満たすか判断するステップと、
前記第２の条件を満たすと判断された場合には、下１桁目の数値が前記第１のノードのノード番号の下１桁目の数値を反転させた数値であり、下２桁目の数値が前記第１のノードのノード番号の下２桁目の数値を反転させた数値であり且つノード番号の下１桁目及び下２桁目以外の桁の数値が前記第１のノードのノード番号の下１桁目及び下２桁目以外の桁の数値と同じであるノード番号が付与されているノードに対し、当該ノードと前記第１のノードとの間に設けられているチャネルを介して、前記宛先ノードに送信すべきデータを送信するステップと、
を実行させるためのルーティングプログラム。
【請求項５】
ｎ（ｎは３以上の自然数）次のハイパーキューブ状に接続されている２ｎ個のノード
を有し、
直接接続されているノード間でハミング距離が１となるようにｎ桁の２進数のノード番号が前記ノードの各々に対し付与されており、
ノード番号の下１桁目及び下２桁目以外の桁の数値が全て一致するという第１の条件を満たす特定のノードの各々と他の前記特定のノードの各々との間にチャネルが設けられており、
前記ノードの各々が、
データを宛先ノードに送信する場合、当該ノードのノード番号の下１桁目の数値と宛先ノードのノード番号の下１桁目の数値とが異なっており且つ当該ノードのノード番号の下２桁目の数値と前記宛先ノードのノード番号の下２桁目の数値とが異なっているという第２の条件を満たすか判断する判断部と、
前記第２の条件を満たすと判断された場合には、下１桁目の数値が当該ノードのノード番号の下１桁目の数値を反転させた数値であり、下２桁目の数値が当該ノードのノード番号の下２桁目の数値を反転させた数値であり且つノード番号の下１桁目及び下２桁目以外の桁の数値が当該ノードのノード番号の下１桁目及び下２桁目以外の桁の数値と同じであるノード番号が付与されているノードである第１のノードに対し、当該ノードと前記第１のノードとの間に設けられているチャネルを介して、前記宛先ノードに送信すべきデータを送信する通信部と、
を有する情報処理システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本技術は、ネットワークのトポロジ及びルーティング技術に関する。
【背景技術】
【０００２】
情報処理システムにおいてノード（例えばプロセッサ）間におけるレイテンシの短縮を図る場合、全てのノード間をポイントツーポイント（Point to Point）で接続する完全結合網を用いることが有効である。完全結合網は、例えば図１に示すようなネットワークである。しかし、完全結合網は、レイテンシの短縮には有効であるものの、ネットワークの大規模化（すなわち多ノード化）に伴い物理チャネル数が著しく増加するため、拡張コストや実装難易度が問題となることがある。【０００３】
そこで、大規模なネットワークでは、物理チャネル数を減少させることを目的として、ハイパーキューブ（Hyper Cube）型ネットワークなどのリンク構造のネットワークを用いることがある。ハイパーキューブ型ネットワークは、例えば図２に示すようなネットワークであり、図２は３次元のハイパーキューブ型ネットワークを示している。ハイパーキューブ型ネットワークでは、ハイパーキューブの各頂点にノードを配置するようになっており、ｎ次元のハイパーキューブ型ネットワークの場合、各ノードはＬｏｇ２ｎ個のノードと直接接続される。【０００４】
図３は、完全結合網およびハイパーキューブ型ネットワークについてノード数とチャネル数との関係を示したものである。図３の縦軸はチャネル数を表し、横軸はノード数を表す。図３に示すように、ハイパーキューブ型ネットワークは、ノード数が多くなっても完全結合網ほど著しくチャネル数が増加することはない。【０００５】
ところで、ハイパーキューブ型のネットワーク等に利用される固定型ルーティング（Deterministic Routing）としては、e-cubeルーティングが代表的である。e-cubeルーティングは、次元順ルーティングとも呼ばれ、優先順位が高い次元方向のチャネルから順番に使うようにルーティングを行うことにより、発信ノードから宛先ノードまでデータを転送する。e-cubeルーティングは比較的単純な論理回路で実現できるため、経路情報を保持するためのルーティングテーブルをノードが保持しなくてもよい。また、相互接続（Interconnected）のハイパーキューブ型ネットワークの場合、e-cubeルーティングにおけるデッドロックフリーが保障されているため、トーラス型ネットワークなどの場合に考慮している仮想チャネル機構が不要である。【０００６】
しかしながら、リンク構造のネットワークにおける共通の問題点として、ネットワークの大規模化に伴い長距離リンクが出現することや平均ホップ数が増加することが挙げられる。これらは、ノード間におけるレイテンシの伸長を引き起こし、処理性能を劣化させる原因となる。【０００７】
このような問題に関し、８つのノードによるハイパーキューブ網（クラスタ）において、各々のノードに接続線を１本追加して他のクラスタにおけるノードと接続することにより、クラスタを跨るノード間でデータ転送を行う技術が存在する。【０００８】
また、ハイパーキューブ網において、最大ＰＥ（Processing Element＝処理要素）間距離を有するＰＥ間にバイパス用リンクを付加し、ＰＥ集合体を構成する技術が存在する。【０００９】
しかしながら、これらの技術では、ハイパーキューブ型ネットワークにおける通信効率を十分に向上させることができなかった。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】特開平３−２５６１５９号公報
【特許文献２】特開平３−１８６９６３号公報
【非特許文献】
【００１１】
【非特許文献１】William J. Dally et al."Deadlock-Free Message Routing in Multiprocessor Interconnection Networks",IEEE TRANSACTIONS ON COMPUTERS,VOL.C-36,NO.5
【発明の概要】
【発明が解決しようとする課題】
【００１２】
従って、本技術の目的は、一側面において、ハイパーキューブ型ネットワークにおける通信効率を向上させるための技術を提供することである。
【課題を解決するための手段】
【００１３】
本実施の形態の第１の態様に係る情報処理システムは、ｎ（ｎは３以上の自然数）次のハイパーキューブ状に接続されている２ｎ個のノードを有している。そして、上記２ｎ個のノードのうち所定の条件を満たす特定のノードの各々と他の特定のノードの各々との間にチャネルが設けられており、上記所定の条件が、直接接続されているノード間でハミング距離が１となるようにｎ桁の２進数のノード番号をノードの各々に対し付与した場合において、ノード番号の下１桁目及び下２桁目以外の桁の数値が全て一致するという条件である。【００１４】
本実施の形態の第２の態様に係るルーティング方法は、ｎ（ｎは３以上の自然数）次のハイパーキューブ状に接続されている２ｎ個のノードを有し、直接接続されているノード間でハミング距離が１となるようにｎ桁の２進数のノード番号がノードの各々に対し付与されており且つノード番号の下１桁目及び下２桁目以外の桁の数値が全て一致するという第１の条件を満たす特定のノードの各々と他の特定のノードの各々との間にチャネルが設けられている情報処理システムにおける２ｎ個のノードのいずれかである第１のノードにより実行される。そして、本方法は、（Ａ）データを宛先ノードに送信する場合、第１のノードのノード番号の下１桁目の数値と宛先ノードのノード番号の下１桁目の数値とが異なっており且つ第１のノードのノード番号の下２桁目の数値と宛先ノードのノード番号の下２桁目の数値とが異なっているという第２の条件を満たすか判断するステップと、（Ｂ）第２の条件を満たすと判断された場合には、下１桁目の数値が第１のノードのノード番号の下１桁目の数値を反転させた数値であり、下２桁目の数値が第１のノードのノード番号の下２桁目の数値を反転させた数値であり且つノード番号の下１桁目及び下２桁目以外の桁の数値が第１のノードのノード番号の下１桁目及び下２桁目以外の桁の数値と同じであるノード番号が付与されているノードに対し、当該ノードと第１のノードとの間に設けられているチャネルを介して、宛先ノードに送信すべきデータを送信するステップとを含む。
【図面の簡単な説明】
【００１５】
【図１】図１は、完全結合網について説明するための図である。
【図２】図２は、ハイパーキューブ型ネットワークについて説明するための図である。
【図３】図３は、完全結合網及びハイパーキューブ型ネットワークについてノード数とチャネル数との関係を示す図である。
【図４】図４は、３次元のハイパーキューブ型ネットワークの構成を示す図である。
【図５】図５は、８ノードによるSSP Cube型ネットワークの構成を示す図である。
【図６】図６は、１６ノードによるSSP Cube型ネットワークの構成を示す図である。
【図７】図７は、プロセッサの機能ブロック図である。
【図８】図８は、ノードにより行われるルーティング処理の処理フローを示す図である。
【図９】図９は、完全結合網及びSSP Cube型ネットワークについてノード数とチャネル数との関係を示す図である。
【図１０】図１０は、ハイパーキューブ型ネットワーク及びSSP Cube型ネットワークの特徴について説明するための図である。
【図１１】図１１は、ハイパーキューブ型ネットワーク及びSSP Cube型ネットワークについてノード数とチャネル数との関係を示す図である。
【図１２】図１２は、ハイパーキューブ型ネットワークにおけるブロードキャストについて説明するための図である。
【図１３】図１３は、SSP Cube型ネットワークにおけるブロードキャストについて説明するための図である。
【図１４】図１４は、デッドロック状態について説明するための図である。
【図１５】図１５は、デッドロック状態の回避について説明するための図である。
【図１６】図１６は、SSP Cube型ネットワークを適用したコンピュータシステムを示す図である。
【発明を実施するための形態】
【００１６】
まず、本実施の形態に係るネットワークの形状について説明する。本実施の形態に係るネットワークの形状は、相互接続のハイパーキューブ型ネットワークを基本構造とした亜種キューブ形状である。以下、本実施の形態に係るネットワークのことを「SSP Cube型ネットワーク」と呼ぶ。「SSP」は「Subspecies（亜種）」であることを表している。
【００１７】
例えば８ノードによるSSP Cube型ネットワークは、図４に示すような３次元のハイパーキューブ型ネットワークが基本構造となる。図４においては、各ノードにはｎ桁（ここではｎ＝３）の２進数のノード番号が割り当てられており、直接（すなわち１リンクで）接続されるノード間でノード番号のハミング距離が１となるようにノードが接続されている。このようなノード番号の割り当ては、ハイパーキューブ型ネットワークにおけるノードに対して一般的に行われるノード番号の割り当て方法と同じである。なお、図を見やすくするため、ノード番号の先頭には「Ｎ」を付している。
【００１８】
また、各ノードには各次元ｄにチャネル番号が「Ｃｄｋ」である出力チャネルが設けられており、これにより他のノードに接続している。ここで、ｄは次元を表す番号であり、ｋはノード番号である。例えば、ノード番号が「０００」であるノードは、チャネル番号が「１０００」である出力チャネルを介してノード番号が「００１」であるノードに接続し、チャネル番号が「２０００」である出力チャネルを介してノード番号が「０１０」であるノードに接続し、チャネル番号が「３０００」である出力チャネルを介してノード番号が「１００」であるノードに接続している。なお、図を見やすくするため、チャネル番号の先頭には「Ｃ」を付している。
【００１９】
そして、８ノードによるSSP Cube型ネットワークは、図４に示した３次元のハイパーキューブ型ネットワークにさらにチャネルを追加したものであり、図５に示すようなネットワークである。具体的には、ノード番号が「０００」であるノードにチャネル番号が「４０００」である出力チャネルを追加してノード番号が「０１１」であるノードに接続し、ノード番号が「００１」であるノードにチャネル番号が「４００１」である出力チャネルを追加してノード番号が「０１０」であるノードに接続し、ノード番号が「０１０」であるノードにチャネル番号が「４０１０」である出力チャネルを追加してノード番号が「００１」であるノードに接続し、ノード番号が「０１１」であるノードにチャネル番号が「４０１１」である出力チャネルを追加してノード番号が「０００」であるノードに接続し、ノード番号が「１００」であるノードにチャネル番号が「４１００」である出力チャネルを追加してノード番号が「１１１」であるノードに接続し、ノード番号が「１０１」であるノードにチャネル番号が「４１０１」である出力チャネルを追加してノード番号が「１１０」であるノードに接続し、ノード番号が「１１０」であるノードにチャネル番号が「４１１０」である出力チャネルを追加してノード番号が「１０１」であるノードに接続し、ノード番号が「１１１」であるノードにチャネル番号が「４１１１」である出力チャネルを追加してノード番号が「１００」であるノードに接続する。すなわち、データを出力する側のノードに、ノード番号の下１桁目及び下２桁目の数値がいずれも異なり且つ下１桁目及び下２桁目以外の桁の数値が全て一致するノードに対する、Ｃ（ｎ＋１）ｋ（ここではｎ＝３）というチャネル番号を有する出力チャネルを追加する。なお、ここでは図を見やすくするため、新たに追加したチャネルにのみチャネル番号を付している。
【００２０】
このようにして出力チャネルを追加すると、ノード番号の下１桁目及び下２桁目以外の桁の数値が全て一致する４ノードのグループにおける各ノードが、同じグループ内の他のノードのいずれに対しても出力チャネルを有するようになる。すなわち、８ノードのキューブにおける１組の向かい合う面がそれぞれ完全結合網になり、マルチエリア構成を実現する。そのため、SSP Cube型ネットワークは８ノード以上でなければ構築できず、ノード数は２ｍ（ｍは３以上の自然数）であることが条件となる。
【００２１】
図６に、１６ノードによるSSP Cube型ネットワークの構成を示す。１６ノードによるSSP Cube型ネットワークは、４次元のハイパーキューブ型ネットワークにさらにチャネルを追加したネットワークである。具体的には、ノード番号が「００００」であるノードにチャネル番号が「５００００」である出力チャネルを追加してノード番号が「００１１」であるノードに接続し、ノード番号が「０００１」であるノードにチャネル番号が「５０００１」である出力チャネルを追加してノード番号が「００１０」であるノードに接続し、ノード番号が「００１０」であるノードにチャネル番号が「５００１０」である出力チャネルを追加してノード番号が「０００１」であるノードに接続し、ノード番号が「００１１」であるノードにチャネル番号が「５００１１」である出力チャネルを追加してノード番号が「００００」であるノードに接続し、ノード番号が「０１００」であるノードにチャネル番号が「５０１００」である出力チャネルを追加してノード番号が「０１１１」であるノードに接続し、ノード番号が「０１０１」であるノードにチャネル番号が「５０１０１」である出力チャネルを追加してノード番号が「０１１０」であるノードに接続し、ノード番号が「０１１０」であるノードにチャネル番号が「５０１１０」である出力チャネルを追加してノード番号が「０１０１」であるノードに接続し、ノード番号が「０１１１」であるノードにチャネル番号が「５０１１１」である出力チャネルを追加してノード番号が「０１００」であるノードに接続し、ノード番号が「１０００」であるノードにチャネル番号が「５１０００」である出力チャネルを追加してノード番号が「１０１１」であるノードに接続し、ノード番号が「１００１」であるノードにチャネル番号が「５１００１」である出力チャネルを追加してノード番号が「１０１０」であるノードに接続し、ノード番号が「１０１０」であるノードにチャネル番号が「５１０１０」である出力チャネルを追加してノード番号が「１００１」であるノードに接続し、ノード番号が「１０１１」であるノードにチャネル番号が「５１０１１」である出力チャネルを追加してノード番号が「１０００」であるノードに接続し、ノード番号が「１１００」であるノードにチャネル番号が「５１１００」である出力チャネルを追加してノード番号が「１１１１」であるノードに接続し、ノード番号が「１１０１」であるノードにチャネル番号が「５１１０１」である出力チャネルを追加してノード番号が「１１１０」であるノードに接続し、ノード番号が「１１１０」であるノードにチャネル番号が「５１１１０」である出力チャネルを追加してノード番号が「１１０１」であるノードに接続し、ノード番号が「１１１１」であるノードにチャネル番号が「５１１１１」である出力チャネルを追加してノード番号が「１１００」であるノードに接続する。すなわち、８ノードによるSSP Cube型ネットワークの場合と同様に、データを出力する側のノードに、ノード番号の下１桁目及び下２桁目の数値がいずれも異なり且つ下１桁目及び下２桁目以外の桁の数値が全て一致するノードに対する、Ｃ（ｎ＋１）ｋ（ここではｎ＝４）というチャネル番号を有する出力チャネルを追加する。
【００２２】
また、１６ノードによるSSP Cube型ネットワークの場合においても、ノード番号の下１桁目及び下２桁目以外の桁の数値が全て一致する４ノードのグループにおける各ノードが、同じグループ内の他のノードのいずれに対しても出力チャネルを有している。すなわち、８ノードのキューブにおける１組の向かい合う面がそれぞれ完全結合網になり、マルチエリア構成を実現する。
【００２３】
なお、上で述べた例では、８ノード及び１６ノードによるSSP Cube型ネットワークについて説明したが、ノード数が２ｍ（ｍは３以上の自然数）であれば、SSP Cube型ネットワークを構築することが可能である。
【００２４】
次に、SSP Cube型ネットワークにおいて行われるルーティング処理について説明する。
【００２５】
図７に、SSP Cube型ネットワークにおけるノードの機能ブロック図を示す。例えばプロセッサであるノード１は、SSP Cube型ネットワークにおける他のノードから受信したデータ等を格納するメモリ１１と、データを送信すべきノード等を決定する処理を行う判断部１２と、判断部１２により決定されたノードに対してデータを送信する処理を行ったり、受信したデータをメモリ１１に格納する処理等を行う通信部１３とを含む。
【００２６】
次に、図８を用いて、図７に示したノード１が行う処理について説明する。以下では、ノード１のノード番号をＮｉとし、Ｎｉの０ビット目（すなわち１桁目）を表すときはＮｉ[0]とする。これを用いて、ＮｉをＮｉ＝｛Ｎｉ[n-1],Ｎｉ[n-2],...,Ｎｉ[1],Ｎｉ[0]｝（ｎはSSP Cube型ネットワークの基本構造となるハイパーキューブ型ネットワークの次元数）と表す。最終的にデータを送り届けるべきノード（以下、宛先ノードと呼ぶ）のノード番号Ｎｊ、データの送信先ノード（以下、経由ノード（routed node）と呼ぶ）のノード番号Ｎｒ及び経由ノードにデータを送信する際に使用するチャネル（以下、通過チャネル（passage channel）と呼ぶ）のチャネル番号Ｃｐについても同様に表すとする。
【００２７】
まず、判断部１２は、宛先ノードに送信すべきデータをメモリ１１から読み出し、当該データに付与されている宛先ノードのノード番号と、ノード１のノード番号とを比較し、下１桁目及び下２桁目の数値がいずれも異なっているか判断する（図８：ステップＳ１）。すなわち、「Ｎｉ[1]≠Ｎｊ[1] ∧ Ｎｉ[0]≠Ｎｊ[0]」であるか判断する。
【００２８】
そして、「Ｎｉ[1]≠Ｎｊ[1] ∧ Ｎｉ[0]≠Ｎｊ[0]」であると判断された場合（ステップＳ１：Ｙｅｓルート）、判断部１２は、通過チャネルのチャネル番号Ｃｐを、最上位桁の数値がｎ＋１であり、最上位桁以外の桁の数値がノード１のノード番号と同じであるチャネル番号に決定する（ステップＳ３）。すなわち、Ｃｐ＝｛Ｃｐ[n]＝ｎ＋１,Ｃｐ[n-1]＝Ｎｉ[n-1],...,Ｃｐ[1]＝Ｎｉ[1],Ｃｐ[0]＝Ｎｉ[0]｝とする。
【００２９】
また、判断部１２は、経由ノードのノード番号Ｎｒを、下１桁目がノード１のノード番号の下１桁目を反転させた数値であり、下２桁目がノード１のノード番号の下２桁目を反転させた数値であり且つ下１桁目及び下２桁目以外の桁の数値がノード１のノード番号の下１桁目及び下２桁目以外の桁の数値と同じであるノード番号に決定する（ステップＳ５）。すなわち、Ｎｒ＝｛Ｎｒ[n-1]＝Ｎｉ[n-1],Ｎｒ[n-2]＝Ｎｉ[n-2],...,Ｎｒ[1]＝¬Ｎｉ[1],Ｎｒ[0]＝¬Ｎｉ[0]｝とする。
【００３０】
そして、通信部１３は、ステップＳ３において決定された通過チャネルを介して、ステップＳ５において決定された経由ノードに、宛先ノードに送信すべきデータを送信する（ステップＳ１９）。
【００３１】
一方、ステップＳ１において「Ｎｉ[1]≠Ｎｊ[1] ∧ Ｎｉ[0]≠Ｎｊ[0]」ではないと判断された場合（ステップＳ１：Ｎｏルート）、判断部１２は、初期化式をｘ＝ｎ−１、再初期化式をｘ＝ｘ−１としてｘを定義する（ステップＳ７）。すなわち、既にｘが定義されている場合にはｘ＝ｘ−１として再定義し、未だｘが定義されていない場合にはｘ＝ｎ−１としてｘを定義する。
【００３２】
そして、判断部１２は、ｘ≧０であるか判断する（ステップＳ９）。ｘ≧０ではないと判断された場合（ステップＳ９：Ｎｏルート）、処理を終了する。
【００３３】
一方、ｘ≧０であると判断された場合（ステップＳ９：Ｙｅｓルート）、判断部１２は、ノード１のノード番号のｘビット目の数値と宛先ノードのノード番号のｘビット目の数値とが異なっているか判断する（ステップＳ１１）。すなわち、Ｎｉ[x]≠Ｎｊ[x]であるか判断する。
【００３４】
そして、Ｎｉ[x]≠Ｎｊ[x]ではない、すなわちＮｉ[x]＝Ｎｊ[x]であると判断された場合には（ステップＳ１１：Ｎｏルート）、次の桁について処理するため、ステップＳ７の処理に戻る。
【００３５】
一方、Ｎｉ[x]≠Ｎｊ[x]であると判断された場合（ステップＳ１１：Ｙｅｓルート）、判断部１２は、通過チャネルのチャネル番号Ｃｐを、最上位桁の数値がｘ＋１であり、最上位桁以外の桁の数値がノード１のノード番号と同じであるチャネル番号に決定する（ステップＳ１３）。すなわち、Ｃｐ＝｛Ｃｐ[n]＝ｘ＋１,Ｃｐ[n-1]＝Ｎｉ[n-1],...,Ｃｐ[1]＝Ｎｉ[1],Ｃｐ[0]＝Ｎｉ[0]｝とする。
【００３６】
また、判断部１２は、経由ノードのノード番号Ｎｒを、ノード１のノード番号と同じ番号に決定する（ステップＳ１５）。すなわち、Ｎｒ＝｛Ｎｒ[n-1]＝Ｎｉ[n-1],Ｎｒ[n-2]＝Ｎｉ[n-2],...,Ｎｒ[1]＝Ｎｉ[1],Ｎｒ[0]＝Ｎｉ[0]｝とする。さらに、判断部１２は、ステップＳ１５において決定された経由ノードのノード番号のｘビット目の値を反転させる（ステップＳ１７）。すなわち、Ｎｒ[x]＝¬Ｎｒ[x]とする。
【００３７】
そして、通信部１３は、ステップＳ１３において決定された通過チャネルを介して、ステップＳ１５及びＳ１７において決定された経由ノードに、宛先ノードに送信すべきデータを送信する（ステップＳ１９）。そして処理を終了する。
【００３８】
ここで、上で説明したルーティング処理を、簡単な具体例を用いて説明する。ここでは、図５に示したSSP Cube型ネットワークにおいて、ノード番号が「０００」であるノードからノード番号が「１１１」であるノードまでデータを転送する場合について説明する。
【００３９】
まず、ノード番号が「０００」であるノード（以下、Ｎ０００と表す。他のノードについても同様とする。）は、ステップＳ１において、Ｎ０００のノード番号と宛先ノードのノード番号とを比較し、下１桁目及び下２桁目の数値がいずれも異なっているか判断する。ここでは、下１桁目及び下２桁目の数値がいずれも異なっていると判断される。
【００４０】
そして、Ｎ０００は、ステップＳ３において通過チャネルの番号を「４０００」に決定し、またステップＳ５において経由ノードのノード番号を「０１１」に決定する。そして、ステップＳ１９において、チャネル番号が「４０００」であるチャネルを介してＮ０１１にデータを送信する。
【００４１】
一方、Ｎ０１１はＮ０００からデータを受信すると、ステップＳ１において、Ｎ０１１のノード番号と宛先ノードのノード番号とを比較し、下１桁目及び下２桁目の数値がいずれも異なっているか判断する。ここでは、下１桁目及び下２桁目の数値がいずれも一致しているため、ステップＳ７においてｘ＝３−１＝２と定義し、ステップＳ９のＹｅｓルートを経て、ステップ１１においてＮ０１１のノード番号の２ビット目と宛先ノードのノード番号の２ビット目とが異なっているか判断する。ここでは、異なっていると判断される。
【００４２】
そして、Ｎ０１１は、ステップＳ１３において通過チャネルのチャネル番号を「３０１１」に決定し、またステップＳ１５及びＳ１７において経由ノードのノード番号を「１１１」に決定する。そして、ステップＳ１９において、チャネル番号が「３０１１」であるチャネルを介してＮ１１１にデータを送信する。
【００４３】
一方、Ｎ１１１はＮ０１１からデータを受信すると、ステップＳ１においてＮ１１１のノード番号と宛先ノード番号とを比較し、下１桁目及び下２桁目の数値がいずれも異なっているか判断する。ここでは、下１桁目及び下２桁目の数値がいずれも一致しているため、ステップＳ７においてｘ＝３−１＝２と定義し、ステップＳ９のＹｅｓルートを経て、ステップ１１においてＮ１１１のノード番号の２ビット目と宛先ノード番号の２ビット目とが異なっているか判断する。ここでは、一致していると判断され、データが宛先ノードまで到達したので、処理を終了する。
【００４４】
以上述べたようなSSP Cube型ネットワークは、完全結合網と比較すると、チャネルの総数を減少させることができる。図９は、完全結合網及びSSP Cube型ネットワークについてノード数とチャネル数との関係を示したものである。図９の縦軸はチャネル数を表し、横軸はノード数を表す。図９に示すように、ノード数の増加（すなわちネットワークの大規模化）に伴ってその効果は顕著となる。チャネル数が減少することにより製造コストを削減することができ、また実装難易度も軽減される。さらに、高密度配線の解消により発生熱の抑制も期待できる。
【００４５】
また、e-cubeルーティングを適用したハイパーキューブ型ネットワークと比較しても、通信効率において有利である。例えば４次元のハイパーキューブ型ネットワークと１６ノードによるSSP Cube型ネットワークとの比較では、図１０に示すように、平均リンク数（他のノードまでのリンク数の平均）及び最大リンク数において有利であることがわかる。また、完全結合される４ノードを１エリアとみなした場合、SSP Cube型ネットワークではエリア内のいずれのノードに対しても１リンクで通信することが可能であり、エリア内パフォーマンスも向上している。但し、チャネル数についてはハイパーキューブ型ネットワークよりも不利である。図１１は、ハイパーキューブ型ネットワーク及びSSP Cube型ネットワークについてノード数とチャネル数との関係を示したものである。図１１の縦軸はチャネル数を表し、横軸はノード数を表す。図１１に示すように、ハイパーキューブ型ネットワークと比較すると、チャネル数の極端な増加はないものの、多少の増加を避けることはできない。
【００４６】
さらに、ハイパーキューブ型ネットワークと比較すると、SSP Cube型ネットワークはネットワーク内のトラフィックの緩和及び分散に有利である。例えばネットワークにおける各ノードが他の全ノードと通信を行うと、４次元のハイパーキューブ型ネットワークでは５１２のチャネルを使用するのに対し、１６ノードによるSSP Cube型ネットワークでは４４８に抑えることができる。つまり、実効レイテンシを改善することができると共にトータルスループットを改善することができるようになる。これにより、チャネルの性能を低下させてもスループットを維持することができるので、ハイパーキューブ型ネットワークよりもトータルコストが低くなる。また、図１２に示したハイパーキューブ型ネットワークにおけるブロードキャストと、図１３に示したSSP Cube型ネットワークにおけるブロードキャストとを比較すると、SSP Cube型ネットワークの方が使用するチャネルを分散させることができる。これにより、ブロードキャスト性能の向上が期待できる。
【００４７】
次に、デッドロックフリーについて考察する。
【００４８】
一般に、全てのノード間が相互接続されたネットワーク以外では、チャネルが埋め尽くされてデッドロック状態となることを防ぐための対策を講じなければならない。デッドロックフリーなルーティングが行われることを証明するには、チャネル依存グラフを作成し、チャネル依存グラフ内で循環が生じていないことを示せばよい。
【００４９】
例えば図１３の相互連結グラフに示すようなネットワークである場合、各ノードが当該ノードの２つ先のノードにデータを送信すると、次のノードにデータを送信するためのチャネルが全て埋め尽くされてデッドロック状態になる。このネットワークに対応するチャネル依存グラフには、チャネルＣ０からチャネルＣ３までの間で循環が生じている。
【００５０】
そこで、図１４の相互連結グラフに示すように出力チャネルを追加し、それに応じたルーティング方式を定める。ここでは、ノード番号が宛先ノードのノード番号よりも小さければハイチャネル（すなわちチャネル番号の２桁目が１となるチャネル）を使用し、ノード番号が宛先ノードよりも大きければローチャネル（すなわちチャネル番号の２桁目が０となるチャネル）を使用する。但し、チャネルＣ００は使用しないこととする。これにより、各ノードが２つ先のノードにデータを送信してもチャネルは埋め尽くされず、デッドロック状態を回避できる。そして、このネットワークに対応するチャネル依存グラフには循環が生じていない。
【００５１】
そこで、SSP Cube型ネットワークについても、チャネル依存グラフに循環が生じないことを示すことにより、デッドロックフリーなルーティングが行われることを証明する。
【００５２】
SSP Cube型ネットワークは、ネットワークを構築する際に、ノードに対して割り当てるノード番号及びチャネルに対して割り当てるチャネル番号を決定できることが特徴である。そして、SSP Cube型ネットワークにおけるルーティングは、チャネル番号が大きい順にチャネルを使用して発信ノードから宛先ノードまでデータを転送する次元順ルーティング（dimension order routing）である。従って、チャネル依存グラフを描く場合、チャネル間の循環は皆無となる。これにより、デッドロックフリーなルーティングが行われることが証明される。
【００５３】
次に、SSP Cube型ネットワークの適用例について説明する。図１５は、１６ノードによるSSP Cube型ネットワークをコンピュータシステムに適用した場合の構成例を示している。図１５の例では、同一のシステムボードに搭載される４つのＣＰＵ（Central Processing Unit）が完全結合されるように物理配線が設けられており、マルチエリア構成となっている。ここでは、物理配線は相互接続チャネルである。
【００５４】
実際にどのようにノード番号を割り当てるかは、コンピュータシステムに求められる要件や規約に依るが、上で述べたような構成であれば、特にシステムボード内の通信効率の向上を図るのに有効である。これは、各ＣＰＵは同一のシステムボード上にある他のＣＰＵ配下のＤＩＭＭ（Dual Inline Memory Module）に対して１ホップでアクセス可能となっているからである。従って、１つのシステムボード内で単一のアプリケーションを稼働させるようなエリア別並列処理の場合に有利であり、完全結合網を適用する場合と比べると大幅に物理配線量を削減することができる。
【００５５】
以上本技術の一実施の形態を説明したが、本技術はこれに限定されるものではない。例えば、上で説明したプロセッサ１の機能ブロック図は必ずしも実際のプログラムモジュール構成に対応するものではない。
【００５６】
また、上で説明した処理フローは、処理結果が変わらなければ処理の順番を入れ替えることも可能である。さらに、並列に実行させるようにしても良い。
【００５７】
以上述べた本実施の形態をまとめると以下のようになる。
【００５８】
本実施の形態の第１の態様に係る情報処理システムは、ｎ（ｎは３以上の自然数）次のハイパーキューブ状に接続されている２ｎ個のノードを有している。そして、上記２ｎ個のノードのうち所定の条件を満たす特定のノードの各々と他の特定のノードの各々との間にチャネルが設けられており、上記所定の条件が、直接接続されているノード間でハミング距離が１となるようにｎ桁の２進数のノード番号をノードの各々に対し付与した場合において、ノード番号の下１桁目及び下２桁目以外の桁の数値が全て一致するという条件である。
【００５９】
このようにすれば、従来のハイパーキューブ型情報処理システムと比較して、チャネルの数を大幅に増加させることなく、平均ホップ数や最大ホップ数を効果的に減少させて通信効率を向上させることができるようになる。
【００６０】
本実施の形態の第２の態様に係るルーティング方法は、ｎ（ｎは３以上の自然数）次のハイパーキューブ状に接続されている２ｎ個のノードを有し、直接接続されているノード間でハミング距離が１となるようにｎ桁の２進数のノード番号がノードの各々に対し付与されており且つノード番号の下１桁目及び下２桁目以外の桁の数値が全て一致するという第１の条件を満たす特定のノードの各々と他の特定のノードの各々との間にチャネルが設けられている情報処理システムにおける２ｎ個のノードのいずれかである第１のノードにより実行される。そして、本方法は、（Ａ）データを宛先ノードに送信する場合、第１のノードのノード番号の下１桁目の数値と宛先ノードのノード番号の下１桁目の数値とが異なっており且つ第１のノードのノード番号の下２桁目の数値と宛先ノードのノード番号の下２桁目の数値とが異なっているという第２の条件を満たすか判断するステップと、（Ｂ）第２の条件を満たすと判断された場合には、下１桁目の数値が第１のノードのノード番号の下１桁目の数値を反転させた数値であり、下２桁目の数値が第１のノードのノード番号の下２桁目の数値を反転させた数値であり且つノード番号の下１桁目及び下２桁目以外の桁の数値が第１のノードのノード番号の下１桁目及び下２桁目以外の桁の数値と同じであるノード番号が付与されているノードに対し、当該ノードと第１のノードとの間に設けられているチャネルを介して、宛先ノードに送信すべきデータを送信するステップとを含む。
【００６１】
このようにすれば、従来のハイパーキューブ型情報処理システムにおけるルーティング（例えばe-cubeルーティング）と比較して、宛先ノードまでより少ないホップ数でデータを転送することができるようになる。
【００６２】
また、上で述べた本方法は、（Ｃ）第２の条件を満たさないと判断された場合には、第１のノードのノード番号と宛先ノードのノード番号とを最上位桁から順に比較し、数値が一致しない桁のうち最上位の桁である第１の桁を特定するステップと、（Ｄ）第１のノードのノード番号における第１の桁の数値を反転させたノード番号が付与されているノードに対し、宛先ノードに送信すべきデータを送信するステップとをさらに含むようにしてもよい。これにより、データが最小のホップ数で宛先ノードまで到達するようにルーティングが行われるようになる。
【００６３】
なお、上で述べたような処理をハードウエア（例えばプロセッサ）に実施させるためのプログラムを作成することができ、当該プログラムは、例えばフレキシブル・ディスク、ＣＤ−ＲＯＭ、光磁気ディスク、半導体メモリ、ハードディスク等のコンピュータ読み取り可能な記憶媒体又は記憶装置に格納される。なお、処理途中のデータについては、コンピュータのメモリ等の記憶装置に一時保管される。
【図１】
2012056547.tif 000003
【図２】
2012056547.tif 000004
【図３】
2012056547.tif 000005
【図４】
2012056547.tif 000006
【図５】
2012056547.tif 000007
【図６】
2012056547.tif 000008
【図７】
2012056547.tif 000009
【図８】
2012056547.tif 000010
【図９】
2012056547.tif 000011
【図１０】
2012056547.tif 000012
【図１１】
2012056547.tif 000013
【図１２】
2012056547.tif 000014
【図１３】
2012056547.tif 000015
【図１４】
2012056547.tif 000016
【図１５】
2012056547.tif 000017
【図１６】
2012056547.tif 000018
【手続補正書】
【提出日】平成25年3月19日(2013.3.19)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】
本技術は、ネットワークのトポロジ及びルーティング技術に関する。
【背景技術】
【０００２】
情報処理システムにおいてノード（例えばプロセッサ）間におけるレイテンシの短縮を図る場合、全てのノード間をポイントツーポイント（Point to Point）で接続する完全結合網を用いることが有効である。完全結合網は、例えば図１に示すようなネットワークである。しかし、完全結合網は、レイテンシの短縮には有効であるものの、ネットワークの大規模化（すなわち多ノード化）に伴い物理チャネル数が著しく増加するため、拡張コストや実装難易度が問題となることがある。
【０００３】
そこで、大規模なネットワークでは、物理チャネル数を減少させることを目的として、ハイパーキューブ（Hyper Cube）型ネットワークなどのリンク構造のネットワークを用いることがある。ハイパーキューブ型ネットワークは、例えば図２に示すようなネットワークであり、図２は３次元のハイパーキューブ型ネットワークを示している。ハイパーキューブ型ネットワークでは、ハイパーキューブの各頂点にノードを配置するようになっており、ｎ次元のハイパーキューブ型ネットワークの場合、各ノードはＬｏｇ２ｎ個のノードと直接接続される。
【０００４】
図３は、完全結合網およびハイパーキューブ型ネットワークについてノード数とチャネル数との関係を示したものである。図３の縦軸はチャネル数を表し、横軸はノード数を表す。図３に示すように、ハイパーキューブ型ネットワークは、ノード数が多くなっても完全結合網ほど著しくチャネル数が増加することはない。
【０００５】
ところで、ハイパーキューブ型のネットワーク等に利用される固定型ルーティング（Deterministic Routing）としては、e-cubeルーティングが代表的である。e-cubeルーティングは、次元順ルーティングとも呼ばれ、優先順位が高い次元方向のチャネルから順番に使うようにルーティングを行うことにより、発信ノードから宛先ノードまでデータを転送する。e-cubeルーティングは比較的単純な論理回路で実現できるため、経路情報を保持するためのルーティングテーブルをノードが保持しなくてもよい。また、相互接続（Interconnected）のハイパーキューブ型ネットワークの場合、e-cubeルーティングにおけるデッドロックフリーが保障されているため、トーラス型ネットワークなどの場合に考慮している仮想チャネル機構が不要である。
【０００６】
しかしながら、リンク構造のネットワークにおける共通の問題点として、ネットワークの大規模化に伴い長距離リンクが出現することや平均ホップ数が増加することが挙げられる。これらは、ノード間におけるレイテンシの伸長を引き起こし、処理性能を劣化させる原因となる。
【０００７】
このような問題に関し、８つのノードによるハイパーキューブ網（クラスタ）において、各々のノードに接続線を１本追加して他のクラスタにおけるノードと接続することにより、クラスタを跨るノード間でデータ転送を行う技術が存在する。
【０００８】
また、ハイパーキューブ網において、最大ＰＥ（Processing Element＝処理要素）間距離を有するＰＥ間にバイパス用リンクを付加し、ＰＥ集合体を構成する技術が存在する。
【０００９】
しかしながら、これらの技術では、ハイパーキューブ型ネットワークにおける通信効率を十分に向上させることができなかった。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】特開平３−２５６１５９号公報
【特許文献２】特開平３−１８６９６３号公報
【非特許文献】
【００１１】
【非特許文献１】William J. Dally et al."Deadlock-Free Message Routing in Multiprocessor Interconnection Networks",IEEE TRANSACTIONS ON COMPUTERS,VOL.C-36,NO.5
【発明の概要】
【発明が解決しようとする課題】
【００１２】
従って、本技術の目的は、一側面において、ハイパーキューブ型ネットワークにおける通信効率を向上させるための技術を提供することである。
【課題を解決するための手段】
【００１３】
本実施の形態の第１の態様に係る情報処理システムは、ｎ（ｎは３以上の自然数）次のハイパーキューブ状に接続されている２ｎ個のノードを有している。そして、上記２ｎ個のノードのうち所定の条件を満たす特定のノードの各々と他の特定のノードの各々との間にチャネルが設けられており、上記所定の条件が、直接接続されているノード間でハミング距離が１となるようにｎ桁の２進数のノード番号をノードの各々に対し付与した場合において、ノード番号の下１桁目及び下２桁目以外の桁の数値が全て一致するという条件である。
【００１４】
本実施の形態の第２の態様に係るルーティング方法は、ｎ（ｎは３以上の自然数）次のハイパーキューブ状に接続されている２ｎ個のノードを有し、直接接続されているノード間でハミング距離が１となるようにｎ桁の２進数のノード番号がノードの各々に対し付与されており且つノード番号の下１桁目及び下２桁目以外の桁の数値が全て一致するという第１の条件を満たす特定のノードの各々と他の特定のノードの各々との間にチャネルが設けられている情報処理システムにおける２ｎ個のノードのいずれかである第１のノードにより実行される。そして、本方法は、（Ａ）データを宛先ノードに送信する場合、第１のノードのノード番号の下１桁目の数値と宛先ノードのノード番号の下１桁目の数値とが異なっており且つ第１のノードのノード番号の下２桁目の数値と宛先ノードのノード番号の下２桁目の数値とが異なっているという第２の条件を満たすか判断するステップと、（Ｂ）第２の条件を満たすと判断された場合には、下１桁目の数値が第１のノードのノード番号の下１桁目の数値を反転させた数値であり、下２桁目の数値が第１のノードのノード番号の下２桁目の数値を反転させた数値であり且つノード番号の下１桁目及び下２桁目以外の桁の数値が第１のノードのノード番号の下１桁目及び下２桁目以外の桁の数値と同じであるノード番号が付与されているノードに対し、当該ノードと第１のノードとの間に設けられているチャネルを介して、宛先ノードに送信すべきデータを送信するステップとを含む。
【図面の簡単な説明】
【００１５】
【図１】図１は、完全結合網について説明するための図である。
【図２】図２は、ハイパーキューブ型ネットワークについて説明するための図である。
【図３】図３は、完全結合網及びハイパーキューブ型ネットワークについてノード数とチャネル数との関係を示す図である。
【図４】図４は、３次元のハイパーキューブ型ネットワークの構成を示す図である。
【図５】図５は、８ノードによるSSP Cube型ネットワークの構成を示す図である。
【図６】図６は、１６ノードによるSSP Cube型ネットワークの構成を示す図である。
【図７】図７は、プロセッサの機能ブロック図である。
【図８】図８は、ノードにより行われるルーティング処理の処理フローを示す図である。
【図９】図９は、完全結合網及びSSP Cube型ネットワークについてノード数とチャネル数との関係を示す図である。
【図１０】図１０は、ハイパーキューブ型ネットワーク及びSSP Cube型ネットワークの特徴について説明するための図である。
【図１１】図１１は、ハイパーキューブ型ネットワーク及びSSP Cube型ネットワークについてノード数とチャネル数との関係を示す図である。
【図１２】図１２は、ハイパーキューブ型ネットワークにおけるブロードキャストについて説明するための図である。
【図１３】図１３は、SSP Cube型ネットワークにおけるブロードキャストについて説明するための図である。
【図１４】図１４は、デッドロック状態について説明するための図である。
【図１５】図１５は、デッドロック状態の回避について説明するための図である。
【図１６】図１６は、SSP Cube型ネットワークを適用したコンピュータシステムを示す図である。
【発明を実施するための形態】
【００１６】
まず、本実施の形態に係るネットワークの形状について説明する。本実施の形態に係るネットワークの形状は、相互接続のハイパーキューブ型ネットワークを基本構造とした亜種キューブ形状である。以下、本実施の形態に係るネットワークのことを「SSP Cube型ネットワーク」と呼ぶ。「SSP」は「Subspecies（亜種）」であることを表している。
【００１７】
例えば８ノードによるSSP Cube型ネットワークは、図４に示すような３次元のハイパーキューブ型ネットワークが基本構造となる。図４においては、各ノードにはｎ桁（ここではｎ＝３）の２進数のノード番号が割り当てられており、直接（すなわち１リンクで）接続されるノード間でノード番号のハミング距離が１となるようにノードが接続されている。このようなノード番号の割り当ては、ハイパーキューブ型ネットワークにおけるノードに対して一般的に行われるノード番号の割り当て方法と同じである。なお、図を見やすくするため、ノード番号の先頭には「Ｎ」を付している。
【００１８】
また、各ノードには各次元ｄにチャネル番号が「Ｃｄｋ」である出力チャネルが設けられており、これにより他のノードに接続している。ここで、ｄは次元を表す番号であり、ｋはノード番号である。例えば、ノード番号が「０００」であるノードは、チャネル番号が「１０００」である出力チャネルを介してノード番号が「００１」であるノードに接続し、チャネル番号が「２０００」である出力チャネルを介してノード番号が「０１０」であるノードに接続し、チャネル番号が「３０００」である出力チャネルを介してノード番号が「１００」であるノードに接続している。なお、図を見やすくするため、チャネル番号の先頭には「Ｃ」を付している。
【００１９】
そして、８ノードによるSSP Cube型ネットワークは、図４に示した３次元のハイパーキューブ型ネットワークにさらにチャネルを追加したものであり、図５に示すようなネットワークである。具体的には、ノード番号が「０００」であるノードにチャネル番号が「４０００」である出力チャネルを追加してノード番号が「０１１」であるノードに接続し、ノード番号が「００１」であるノードにチャネル番号が「４００１」である出力チャネルを追加してノード番号が「０１０」であるノードに接続し、ノード番号が「０１０」であるノードにチャネル番号が「４０１０」である出力チャネルを追加してノード番号が「００１」であるノードに接続し、ノード番号が「０１１」であるノードにチャネル番号が「４０１１」である出力チャネルを追加してノード番号が「０００」であるノードに接続し、ノード番号が「１００」であるノードにチャネル番号が「４１００」である出力チャネルを追加してノード番号が「１１１」であるノードに接続し、ノード番号が「１０１」であるノードにチャネル番号が「４１０１」である出力チャネルを追加してノード番号が「１１０」であるノードに接続し、ノード番号が「１１０」であるノードにチャネル番号が「４１１０」である出力チャネルを追加してノード番号が「１０１」であるノードに接続し、ノード番号が「１１１」であるノードにチャネル番号が「４１１１」である出力チャネルを追加してノード番号が「１００」であるノードに接続する。すなわち、データを出力する側のノードに、ノード番号の下１桁目及び下２桁目の数値がいずれも異なり且つ下１桁目及び下２桁目以外の桁の数値が全て一致するノードに対する、Ｃ（ｎ＋１）ｋ（ここではｎ＝３）というチャネル番号を有する出力チャネルを追加する。なお、ここでは図を見やすくするため、新たに追加したチャネルにのみチャネル番号を付している。
【００２０】
このようにして出力チャネルを追加すると、ノード番号の下１桁目及び下２桁目以外の桁の数値が全て一致する４ノードのグループにおける各ノードが、同じグループ内の他のノードのいずれに対しても出力チャネルを有するようになる。すなわち、８ノードのキューブにおける１組の向かい合う面がそれぞれ完全結合網になり、マルチエリア構成を実現する。そのため、SSP Cube型ネットワークは８ノード以上でなければ構築できず、ノード数は２ｍ（ｍは３以上の自然数）であることが条件となる。
【００２１】
図６に、１６ノードによるSSP Cube型ネットワークの構成を示す。１６ノードによるSSP Cube型ネットワークは、４次元のハイパーキューブ型ネットワークにさらにチャネルを追加したネットワークである。具体的には、ノード番号が「００００」であるノードにチャネル番号が「５００００」である出力チャネルを追加してノード番号が「００１１」であるノードに接続し、ノード番号が「０００１」であるノードにチャネル番号が「５０００１」である出力チャネルを追加してノード番号が「００１０」であるノードに接続し、ノード番号が「００１０」であるノードにチャネル番号が「５００１０」である出力チャネルを追加してノード番号が「０００１」であるノードに接続し、ノード番号が「００１１」であるノードにチャネル番号が「５００１１」である出力チャネルを追加してノード番号が「００００」であるノードに接続し、ノード番号が「０１００」であるノードにチャネル番号が「５０１００」である出力チャネルを追加してノード番号が「０１１１」であるノードに接続し、ノード番号が「０１０１」であるノードにチャネル番号が「５０１０１」である出力チャネルを追加してノード番号が「０１１０」であるノードに接続し、ノード番号が「０１１０」であるノードにチャネル番号が「５０１１０」である出力チャネルを追加してノード番号が「０１０１」であるノードに接続し、ノード番号が「０１１１」であるノードにチャネル番号が「５０１１１」である出力チャネルを追加してノード番号が「０１００」であるノードに接続し、ノード番号が「１０００」であるノードにチャネル番号が「５１０００」である出力チャネルを追加してノード番号が「１０１１」であるノードに接続し、ノード番号が「１００１」であるノードにチャネル番号が「５１００１」である出力チャネルを追加してノード番号が「１０１０」であるノードに接続し、ノード番号が「１０１０」であるノードにチャネル番号が「５１０１０」である出力チャネルを追加してノード番号が「１００１」であるノードに接続し、ノード番号が「１０１１」であるノードにチャネル番号が「５１０１１」である出力チャネルを追加してノード番号が「１０００」であるノードに接続し、ノード番号が「１１００」であるノードにチャネル番号が「５１１００」である出力チャネルを追加してノード番号が「１１１１」であるノードに接続し、ノード番号が「１１０１」であるノードにチャネル番号が「５１１０１」である出力チャネルを追加してノード番号が「１１１０」であるノードに接続し、ノード番号が「１１１０」であるノードにチャネル番号が「５１１１０」である出力チャネルを追加してノード番号が「１１０１」であるノードに接続し、ノード番号が「１１１１」であるノードにチャネル番号が「５１１１１」である出力チャネルを追加してノード番号が「１１００」であるノードに接続する。すなわち、８ノードによるSSP Cube型ネットワークの場合と同様に、データを出力する側のノードに、ノード番号の下１桁目及び下２桁目の数値がいずれも異なり且つ下１桁目及び下２桁目以外の桁の数値が全て一致するノードに対する、Ｃ（ｎ＋１）ｋ（ここではｎ＝４）というチャネル番号を有する出力チャネルを追加する。
【００２２】
また、１６ノードによるSSP Cube型ネットワークの場合においても、ノード番号の下１桁目及び下２桁目以外の桁の数値が全て一致する４ノードのグループにおける各ノードが、同じグループ内の他のノードのいずれに対しても出力チャネルを有している。すなわち、８ノードのキューブにおける１組の向かい合う面がそれぞれ完全結合網になり、マルチエリア構成を実現する。
【００２３】
なお、上で述べた例では、８ノード及び１６ノードによるSSP Cube型ネットワークについて説明したが、ノード数が２ｍ（ｍは３以上の自然数）であれば、SSP Cube型ネットワークを構築することが可能である。
【００２４】
次に、SSP Cube型ネットワークにおいて行われるルーティング処理について説明する。
【００２５】
図７に、SSP Cube型ネットワークにおけるノードの機能ブロック図を示す。例えばプロセッサであるノード１は、SSP Cube型ネットワークにおける他のノードから受信したデータ等を格納するメモリ１１と、データを送信すべきノード等を決定する処理を行う判断部１２と、判断部１２により決定されたノードに対してデータを送信する処理を行ったり、受信したデータをメモリ１１に格納する処理等を行う通信部１３とを含む。
【００２６】
次に、図８を用いて、図７に示したノード１が行う処理について説明する。以下では、ノード１のノード番号をＮｉとし、Ｎｉの０ビット目（すなわち１桁目）を表すときはＮｉ[0]とする。これを用いて、ＮｉをＮｉ＝｛Ｎｉ[n-1],Ｎｉ[n-2],...,Ｎｉ[1],Ｎｉ[0]｝（ｎはSSP Cube型ネットワークの基本構造となるハイパーキューブ型ネットワークの次元数）と表す。最終的にデータを送り届けるべきノード（以下、宛先ノードと呼ぶ）のノード番号Ｎｊ、データの送信先ノード（以下、経由ノード（routed node）と呼ぶ）のノード番号Ｎｒ及び経由ノードにデータを送信する際に使用するチャネル（以下、通過チャネル（passage channel）と呼ぶ）のチャネル番号Ｃｐについても同様に表すとする。
【００２７】
まず、判断部１２は、宛先ノードに送信すべきデータをメモリ１１から読み出し、当該データに付与されている宛先ノードのノード番号と、ノード１のノード番号とを比較し、下１桁目及び下２桁目の数値がいずれも異なっているか判断する（図８：ステップＳ１）。すなわち、「Ｎｉ[1]≠Ｎｊ[1] ∧ Ｎｉ[0]≠Ｎｊ[0]」であるか判断する。
【００２８】
そして、「Ｎｉ[1]≠Ｎｊ[1] ∧ Ｎｉ[0]≠Ｎｊ[0]」であると判断された場合（ステップＳ１：Ｙｅｓルート）、判断部１２は、通過チャネルのチャネル番号Ｃｐを、最上位桁の数値がｎ＋１であり、最上位桁以外の桁の数値がノード１のノード番号と同じであるチャネル番号に決定する（ステップＳ３）。すなわち、Ｃｐ＝｛Ｃｐ[n]＝ｎ＋１,Ｃｐ[n-1]＝Ｎｉ[n-1],...,Ｃｐ[1]＝Ｎｉ[1],Ｃｐ[0]＝Ｎｉ[0]｝とする。
【００２９】
また、判断部１２は、経由ノードのノード番号Ｎｒを、下１桁目がノード１のノード番号の下１桁目を反転させた数値であり、下２桁目がノード１のノード番号の下２桁目を反転させた数値であり且つ下１桁目及び下２桁目以外の桁の数値がノード１のノード番号の下１桁目及び下２桁目以外の桁の数値と同じであるノード番号に決定する（ステップＳ５）。すなわち、Ｎｒ＝｛Ｎｒ[n-1]＝Ｎｉ[n-1],Ｎｒ[n-2]＝Ｎｉ[n-2],...,Ｎｒ[1]＝¬Ｎｉ[1],Ｎｒ[0]＝¬Ｎｉ[0]｝とする。
【００３０】
そして、通信部１３は、ステップＳ３において決定された通過チャネルを介して、ステップＳ５において決定された経由ノードに、宛先ノードに送信すべきデータを送信する（ステップＳ１９）。
【００３１】
一方、ステップＳ１において「Ｎｉ[1]≠Ｎｊ[1] ∧ Ｎｉ[0]≠Ｎｊ[0]」ではないと判断された場合（ステップＳ１：Ｎｏルート）、判断部１２は、初期化式をｘ＝ｎ−１、再初期化式をｘ＝ｘ−１としてｘを定義する（ステップＳ７）。すなわち、既にｘが定義されている場合にはｘ＝ｘ−１として再定義し、未だｘが定義されていない場合にはｘ＝ｎ−１としてｘを定義する。
【００３２】
そして、判断部１２は、ｘ≧０であるか判断する（ステップＳ９）。ｘ≧０ではないと判断された場合（ステップＳ９：Ｎｏルート）、処理を終了する。
【００３３】
一方、ｘ≧０であると判断された場合（ステップＳ９：Ｙｅｓルート）、判断部１２は、ノード１のノード番号のｘビット目の数値と宛先ノードのノード番号のｘビット目の数値とが異なっているか判断する（ステップＳ１１）。すなわち、Ｎｉ[x]≠Ｎｊ[x]であるか判断する。
【００３４】
そして、Ｎｉ[x]≠Ｎｊ[x]ではない、すなわちＮｉ[x]＝Ｎｊ[x]であると判断された場合には（ステップＳ１１：Ｎｏルート）、次の桁について処理するため、ステップＳ７の処理に戻る。
【００３５】
一方、Ｎｉ[x]≠Ｎｊ[x]であると判断された場合（ステップＳ１１：Ｙｅｓルート）、判断部１２は、通過チャネルのチャネル番号Ｃｐを、最上位桁の数値がｘ＋１であり、最上位桁以外の桁の数値がノード１のノード番号と同じであるチャネル番号に決定する（ステップＳ１３）。すなわち、Ｃｐ＝｛Ｃｐ[n]＝ｘ＋１,Ｃｐ[n-1]＝Ｎｉ[n-1],...,Ｃｐ[1]＝Ｎｉ[1],Ｃｐ[0]＝Ｎｉ[0]｝とする。
【００３６】
また、判断部１２は、経由ノードのノード番号Ｎｒを、ノード１のノード番号と同じ番号に決定する（ステップＳ１５）。すなわち、Ｎｒ＝｛Ｎｒ[n-1]＝Ｎｉ[n-1],Ｎｒ[n-2]＝Ｎｉ[n-2],...,Ｎｒ[1]＝Ｎｉ[1],Ｎｒ[0]＝Ｎｉ[0]｝とする。さらに、判断部１２は、ステップＳ１５において決定された経由ノードのノード番号のｘビット目の値を反転させる（ステップＳ１７）。すなわち、Ｎｒ[x]＝¬Ｎｒ[x]とする。
【００３７】
そして、通信部１３は、ステップＳ１３において決定された通過チャネルを介して、ステップＳ１５及びＳ１７において決定された経由ノードに、宛先ノードに送信すべきデータを送信する（ステップＳ１９）。そして処理を終了する。
【００３８】
ここで、上で説明したルーティング処理を、簡単な具体例を用いて説明する。ここでは、図５に示したSSP Cube型ネットワークにおいて、ノード番号が「０００」であるノードからノード番号が「１１１」であるノードまでデータを転送する場合について説明する。
【００３９】
まず、ノード番号が「０００」であるノード（以下、Ｎ０００と表す。他のノードについても同様とする。）は、ステップＳ１において、Ｎ０００のノード番号と宛先ノードのノード番号とを比較し、下１桁目及び下２桁目の数値がいずれも異なっているか判断する。ここでは、下１桁目及び下２桁目の数値がいずれも異なっていると判断される。
【００４０】
そして、Ｎ０００は、ステップＳ３において通過チャネルの番号を「４０００」に決定し、またステップＳ５において経由ノードのノード番号を「０１１」に決定する。そして、ステップＳ１９において、チャネル番号が「４０００」であるチャネルを介してＮ０１１にデータを送信する。
【００４１】
一方、Ｎ０１１はＮ０００からデータを受信すると、ステップＳ１において、Ｎ０１１のノード番号と宛先ノードのノード番号とを比較し、下１桁目及び下２桁目の数値がいずれも異なっているか判断する。ここでは、下１桁目及び下２桁目の数値がいずれも一致しているため、ステップＳ７においてｘ＝３−１＝２と定義し、ステップＳ９のＹｅｓルートを経て、ステップ１１においてＮ０１１のノード番号の２ビット目（Ｎｉ[2]）と宛先ノードのノード番号の２ビット目（Ｎj[2]）とが異なっているか判断する。ここでは、異なっていると判断される。
【００４２】
そして、Ｎ０１１は、ステップＳ１３において通過チャネルのチャネル番号を「３０１１」に決定し、またステップＳ１５及びＳ１７において経由ノードのノード番号を「１１１」に決定する。そして、ステップＳ１９において、チャネル番号が「３０１１」であるチャネルを介してＮ１１１にデータを送信する。
【００４３】
一方、Ｎ１１１はＮ０１１からデータを受信すると、ステップＳ１においてＮ１１１のノード番号と宛先ノード番号とを比較し、下１桁目及び下２桁目の数値がいずれも異なっているか判断する。ここでは、下１桁目及び下２桁目の数値がいずれも一致しているため、ステップＳ７においてｘ＝３−１＝２と定義し、ステップＳ９のＹｅｓルートを経て、ステップ１１においてＮ１１１のノード番号の２ビット目（Ｎｉ[2]）と宛先ノード番号の２ビット目（Ｎj[2]）とが異なっているか判断する。ここでは、一致していると判断され、データが宛先ノードまで到達したので、処理を終了する。
【００４４】
以上述べたようなSSP Cube型ネットワークは、完全結合網と比較すると、チャネルの総数を減少させることができる。図９は、完全結合網及びSSP Cube型ネットワークについてノード数とチャネル数との関係を示したものである。図９の縦軸はチャネル数を表し、横軸はノード数を表す。図９に示すように、ノード数の増加（すなわちネットワークの大規模化）に伴ってその効果は顕著となる。チャネル数が減少することにより製造コストを削減することができ、また実装難易度も軽減される。さらに、高密度配線の解消により発生熱の抑制も期待できる。
【００４５】
また、e-cubeルーティングを適用したハイパーキューブ型ネットワークと比較しても、通信効率において有利である。例えば４次元のハイパーキューブ型ネットワークと１６ノードによるSSP Cube型ネットワークとの比較では、図１０に示すように、平均リンク数（他のノードまでのリンク数の平均）及び最大リンク数において有利であることがわかる。また、完全結合される４ノードを１エリアとみなした場合、SSP Cube型ネットワークではエリア内のいずれのノードに対しても１リンクで通信することが可能であり、エリア内パフォーマンスも向上している。但し、チャネル数についてはハイパーキューブ型ネットワークよりも不利である。図１１は、ハイパーキューブ型ネットワーク及びSSP Cube型ネットワークについてノード数とチャネル数との関係を示したものである。図１１の縦軸はチャネル数を表し、横軸はノード数を表す。図１１に示すように、ハイパーキューブ型ネットワークと比較すると、チャネル数の極端な増加はないものの、多少の増加を避けることはできない。
【００４６】
さらに、ハイパーキューブ型ネットワークと比較すると、SSP Cube型ネットワークはネットワーク内のトラフィックの緩和及び分散に有利である。例えばネットワークにおける各ノードが他の全ノードと通信を行うと、４次元のハイパーキューブ型ネットワークでは５１２のチャネルを使用するのに対し、１６ノードによるSSP Cube型ネットワークでは４４８に抑えることができる。つまり、実効レイテンシを改善することができると共にトータルスループットを改善することができるようになる。これにより、チャネルの性能を低下させてもスループットを維持することができるので、ハイパーキューブ型ネットワークよりもトータルコストが低くなる。また、図１２に示したハイパーキューブ型ネットワークにおけるブロードキャストと、図１３に示したSSP Cube型ネットワークにおけるブロードキャストとを比較すると、SSP Cube型ネットワークの方が使用するチャネルを分散させることができる。これにより、ブロードキャスト性能の向上が期待できる。
【００４７】
次に、デッドロックフリーについて考察する。
【００４８】
一般に、全てのノード間が相互接続されたネットワーク以外では、チャネルが埋め尽くされてデッドロック状態となることを防ぐための対策を講じなければならない。デッドロックフリーなルーティングが行われることを証明するには、チャネル依存グラフを作成し、チャネル依存グラフ内で循環が生じていないことを示せばよい。
【００４９】
例えば図１４の相互連結グラフに示すようなネットワークである場合、各ノードが当該ノードの２つ先のノードにデータを送信すると、次のノードにデータを送信するためのチャネルが全て埋め尽くされてデッドロック状態になる。このネットワークに対応するチャネル依存グラフには、チャネルＣ０からチャネルＣ３までの間で循環が生じている。
【００５０】
そこで、図１５の相互連結グラフに示すように出力チャネルを追加し、それに応じたルーティング方式を定める。ここでは、ノード番号が宛先ノードのノード番号よりも小さければハイチャネル（すなわちチャネル番号の２桁目が１となるチャネル）を使用し、ノード番号が宛先ノードよりも大きければローチャネル（すなわちチャネル番号の２桁目が０となるチャネル）を使用する。但し、チャネルＣ００は使用しないこととする。これにより、各ノードが２つ先のノードにデータを送信してもチャネルは埋め尽くされず、デッドロック状態を回避できる。そして、このネットワークに対応するチャネル依存グラフには循環が生じていない。
【００５１】
そこで、SSP Cube型ネットワークについても、チャネル依存グラフに循環が生じないことを示すことにより、デッドロックフリーなルーティングが行われることを証明する。
【００５２】
SSP Cube型ネットワークは、ネットワークを構築する際に、ノードに対して割り当てるノード番号及びチャネルに対して割り当てるチャネル番号を決定できることが特徴である。そして、SSP Cube型ネットワークにおけるルーティングは、チャネル番号が大きい順にチャネルを使用して発信ノードから宛先ノードまでデータを転送する次元順ルーティング（dimension order routing）である。従って、チャネル依存グラフを描く場合、チャネル間の循環は皆無となる。これにより、デッドロックフリーなルーティングが行われることが証明される。
【００５３】
次に、SSP Cube型ネットワークの適用例について説明する。図１６は、１６ノードによるSSP Cube型ネットワークをコンピュータシステムに適用した場合の構成例を示している。図１６の例では、同一のシステムボードに搭載される４つのＣＰＵ（Central Processing Unit）が完全結合されるように物理配線が設けられており、マルチエリア構成となっている。ここでは、物理配線は相互接続チャネルである。
【００５４】
実際にどのようにノード番号を割り当てるかは、コンピュータシステムに求められる要件や規約に依るが、上で述べたような構成であれば、特にシステムボード内の通信効率の向上を図るのに有効である。これは、各ＣＰＵは同一のシステムボード上にある他のＣＰＵ配下のＤＩＭＭ（Dual Inline Memory Module）に対して１ホップでアクセス可能となっているからである。従って、１つのシステムボード内で単一のアプリケーションを稼働させるようなエリア別並列処理の場合に有利であり、完全結合網を適用する場合と比べると大幅に物理配線量を削減することができる。
【００５５】
以上本技術の一実施の形態を説明したが、本技術はこれに限定されるものではない。例えば、上で説明したプロセッサ１の機能ブロック図は必ずしも実際のプログラムモジュール構成に対応するものではない。
【００５６】
また、上で説明した処理フローは、処理結果が変わらなければ処理の順番を入れ替えることも可能である。さらに、並列に実行させるようにしても良い。
【００５７】
以上述べた本実施の形態をまとめると以下のようになる。
【００５８】
本実施の形態の第１の態様に係る情報処理システムは、ｎ（ｎは３以上の自然数）次のハイパーキューブ状に接続されている２ｎ個のノードを有している。そして、上記２ｎ個のノードのうち所定の条件を満たす特定のノードの各々と他の特定のノードの各々との間にチャネルが設けられており、上記所定の条件が、直接接続されているノード間でハミング距離が１となるようにｎ桁の２進数のノード番号をノードの各々に対し付与した場合において、ノード番号の下１桁目及び下２桁目以外の桁の数値が全て一致するという条件である。
【００５９】
このようにすれば、従来のハイパーキューブ型情報処理システムと比較して、チャネルの数を大幅に増加させることなく、平均ホップ数や最大ホップ数を効果的に減少させて通信効率を向上させることができるようになる。
【００６０】
本実施の形態の第２の態様に係るルーティング方法は、ｎ（ｎは３以上の自然数）次のハイパーキューブ状に接続されている２ｎ個のノードを有し、直接接続されているノード間でハミング距離が１となるようにｎ桁の２進数のノード番号がノードの各々に対し付与されており且つノード番号の下１桁目及び下２桁目以外の桁の数値が全て一致するという第１の条件を満たす特定のノードの各々と他の特定のノードの各々との間にチャネルが設けられている情報処理システムにおける２ｎ個のノードのいずれかである第１のノードにより実行される。そして、本方法は、（Ａ）データを宛先ノードに送信する場合、第１のノードのノード番号の下１桁目の数値と宛先ノードのノード番号の下１桁目の数値とが異なっており且つ第１のノードのノード番号の下２桁目の数値と宛先ノードのノード番号の下２桁目の数値とが異なっているという第２の条件を満たすか判断するステップと、（Ｂ）第２の条件を満たすと判断された場合には、下１桁目の数値が第１のノードのノード番号の下１桁目の数値を反転させた数値であり、下２桁目の数値が第１のノードのノード番号の下２桁目の数値を反転させた数値であり且つノード番号の下１桁目及び下２桁目以外の桁の数値が第１のノードのノード番号の下１桁目及び下２桁目以外の桁の数値と同じであるノード番号が付与されているノードに対し、当該ノードと第１のノードとの間に設けられているチャネルを介して、宛先ノードに送信すべきデータを送信するステップとを含む。
【００６１】
このようにすれば、従来のハイパーキューブ型情報処理システムにおけるルーティング（例えばe-cubeルーティング）と比較して、宛先ノードまでより少ないホップ数でデータを転送することができるようになる。
【００６２】
また、上で述べた本方法は、（Ｃ）第２の条件を満たさないと判断された場合には、第１のノードのノード番号と宛先ノードのノード番号とを最上位桁から順に比較し、数値が一致しない桁のうち最上位の桁である第１の桁を特定するステップと、（Ｄ）第１のノードのノード番号における第１の桁の数値を反転させたノード番号が付与されているノードに対し、宛先ノードに送信すべきデータを送信するステップとをさらに含むようにしてもよい。これにより、データが最小のホップ数で宛先ノードまで到達するようにルーティングが行われるようになる。
【００６３】
なお、上で述べたような処理をハードウエア（例えばプロセッサ）に実施させるためのプログラムを作成することができ、当該プログラムは、例えばフレキシブル・ディスク、ＣＤ−ＲＯＭ、光磁気ディスク、半導体メモリ、ハードディスク等のコンピュータ読み取り可能な記憶媒体又は記憶装置に格納される。なお、処理途中のデータについては、コンピュータのメモリ等の記憶装置に一時保管される。
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ｎ（ｎは３以上の自然数）次のハイパーキューブ状に接続されている２ｎ個のノードを有し、直接接続されているノード間でハミング距離が１となるようにｎ桁の２進数のノード番号が前記ノードの各々に対し付与されており且つノード番号の下１桁目及び下２桁目以外の桁の数値が全て一致するという第１の条件を満たす特定のノードの各々と他の前記特定のノードの各々との間にチャネルが設けられている情報処理システムにおける前記２ｎ個のノードのいずれかである第１のノードにより実行されるルーティング方法であって、
データを宛先ノードに送信する場合、前記第１のノードのノード番号の下１桁目の数値と宛先ノードのノード番号の下１桁目の数値とが異なっており且つ前記第１のノードのノード番号の下２桁目の数値と前記宛先ノードのノード番号の下２桁目の数値とが異なっているという第２の条件を満たすか判断するステップと、
前記第２の条件を満たすと判断された場合には、下１桁目の数値が前記第１のノードのノード番号の下１桁目の数値を反転させた数値であり、下２桁目の数値が前記第１のノードのノード番号の下２桁目の数値を反転させた数値であり且つノード番号の下１桁目及び下２桁目以外の桁の数値が前記第１のノードのノード番号の下１桁目及び下２桁目以外の桁の数値と同じであるノード番号が付与されているノードに対し、当該ノードと前記第１のノードとの間に設けられているチャネルを介して、前記宛先ノードに送信すべきデータを送信するステップと、
を含むルーティング方法。
【請求項２】
前記第２の条件を満たさないと判断された場合には、前記第１のノードのノード番号と前記宛先ノードのノード番号とを最上位桁から順に比較し、数値が一致しない桁のうち最上位の桁である第１の桁を特定するステップと、
前記第１のノードのノード番号における前記第１の桁の数値を反転させたノード番号が付与されているノードに対し、前記宛先ノードに送信すべきデータを送信するステップと、
をさらに含む請求項１記載のルーティング方法。
【請求項３】
ｎ（ｎは３以上の自然数）次のハイパーキューブ状に接続されている２ｎ個のノードを有し、直接接続されているノード間でハミング距離が１となるようにｎ桁の２進数のノード番号が前記ノードの各々に対し付与されており且つノード番号の下１桁目及び下２桁目以外の桁の数値が全て一致するという第１の条件を満たす特定のノードの各々と他の前記特定のノードの各々との間にチャネルが設けられている情報処理システムにおける前記２ｎ個のノードのいずれかである第１のノードに実行させるためのルーティングプログラムであって、
データを宛先ノードに送信する場合、前記第１のノードのノード番号の下１桁目の数値と宛先ノードのノード番号の下１桁目の数値とが異なっており且つ前記第１のノードのノード番号の下２桁目の数値と前記宛先ノードのノード番号の下２桁目の数値とが異なっているという第２の条件を満たすか判断するステップと、
前記第２の条件を満たすと判断された場合には、下１桁目の数値が前記第１のノードのノード番号の下１桁目の数値を反転させた数値であり、下２桁目の数値が前記第１のノードのノード番号の下２桁目の数値を反転させた数値であり且つノード番号の下１桁目及び下２桁目以外の桁の数値が前記第１のノードのノード番号の下１桁目及び下２桁目以外の桁の数値と同じであるノード番号が付与されているノードに対し、当該ノードと前記第１のノードとの間に設けられているチャネルを介して、前記宛先ノードに送信すべきデータを送信するステップと、
を実行させるためのルーティングプログラム。
【請求項４】
ｎ（ｎは３以上の自然数）次のハイパーキューブ状に接続されている２ｎ個のノード
を有し、
直接接続されているノード間でハミング距離が１となるようにｎ桁の２進数のノード番号が前記ノードの各々に対し付与されており、
ノード番号の下１桁目及び下２桁目以外の桁の数値が全て一致するという第１の条件を満たす特定のノードの各々と他の前記特定のノードの各々との間にチャネルが設けられており、
前記ノードの各々が、
データを宛先ノードに送信する場合、当該ノードのノード番号の下１桁目の数値と宛先ノードのノード番号の下１桁目の数値とが異なっており且つ当該ノードのノード番号の下２桁目の数値と前記宛先ノードのノード番号の下２桁目の数値とが異なっているという第２の条件を満たすか判断する判断部と、
前記第２の条件を満たすと判断された場合には、下１桁目の数値が当該ノードのノード番号の下１桁目の数値を反転させた数値であり、下２桁目の数値が当該ノードのノード番号の下２桁目の数値を反転させた数値であり且つノード番号の下１桁目及び下２桁目以外の桁の数値が当該ノードのノード番号の下１桁目及び下２桁目以外の桁の数値と同じであるノード番号が付与されているノードである第１のノードに対し、当該ノードと前記第１のノードとの間に設けられているチャネルを介して、前記宛先ノードに送信すべきデータを送信する通信部と、
を有する情報処理システム。
【国際調査報告】
2012056547.tif 000019
2012056547.tif 000020