(57)【要約】【課題】  ハイパーキューブネットワークで、スイッチのリンク数を増やすことなくノード間の平均Ｈｏｐ数を小さくすることができるネットワーク装置を得る。【解決手段】  複数のノード10-0〜10-(N-1)を相互に接続するためネットワークシステムにおいて、これらノードの各々に接続されノードの数と同数のスイッチを各々が有する複数のネットワーク50-1〜50-Jを含み、あるノードが他のノードに対してメッセージを送出する際に、複数のネットワークのいずれか一つを利用することにより、他のノードへメッセージが到達可能に構成されている。また、経由するスイッチ数が最も少ないネットワークを選択してこの選択したネットワーク内のスイッチを介してメッセージを送信する。【選択図】  図１
2006080703.tif 000002
【特許請求の範囲】
【請求項１】
複数のノードを相互に接続するためネットワークシステムであって、
前記複数のノードの各々に接続され前記ノードの数と同数のスイッチを、各々が有する複数のネットワークを含み、
あるノードが他のノードに対してメッセージを送出する際に、前記複数のネットワークのいずれか一つを利用することにより、前記他のノードへ前記メッセージが到達可能に構成されていることを特徴とするネットワークシステム。
【請求項２】
前記ノードの各々は、他のノードに対してメッセージを送出する際に、経由するスイッチ数が最も少ないネットワークを選択してこの選択したネットワーク内のスイッチを介して前記メッセージを送信する手段を有することを特徴とする請求項１記載のネットワークシステム。
【請求項３】
前記複数のネットワークの各々は、前記スイッチによりハイパーキューブ構成とされていることを特徴とする請求項１または２記載のネットワークシステム。
【請求項４】
前記ネットワークが２個以上の場合、第１及び第２のハイパーキューブネットワークは、異なる接続関係で構成されていることを特徴とする請求項１〜３いずれか記載のネットワークシステム。
【請求項５】
前記ネットワークが３個以上の場合、第１〜第３のハイパーキューブネットワークは、異なる接続関係で構成されていることを特徴とする請求項１〜３いずれか記載のネットワークシステム。
【請求項６】
Ｎ個（Ｎ≦Ｐ＝２のｎ乗であり、ｎは２以上の整数）のノードを相互に接続するためのネットワークシステムであって、
前記ノードの各々に接続され前記ノードの数と同数のスイッチを、各々が有するＪ個（Ｊは２以上の整数）のネットワークを含み、
前記ノードを接続する前記ネットワークの各ポートは０から（Ｎ−１）までの固有の識別子を有し、
Ｎ×Ｊ個の前記スイッチはそれぞれｎ本のスイッチ間双方向リンクを有し、
前記Ｎ個の第ｊスイッチ（ｊは１からＪまでの整数）の第ｍリンク（ｍは０から（ｎ−１）までの整数）は、Ｋｊ（ｍ）（Ｋｊ（ｍ）はｍを引数とする関数であり、０から（Ｐ−１）までの整数の任意の一つをとる）と前記第ｊスイッチが接続しているポートの識別子との排他論理和をとって得られる値を識別子に持つポートが存在する場合、そのポートと接続したスイッチの第ｍリンクと接続し、前記関数Ｋｊ（ｍ）で作られる前記Ｎ個のスイッチ間の接続関係を含む第ｊハイパーキューブネットワークを構成し、
前記第１及び第２ハイパーキューブネットワークは異なる接続関係で構成され、前記Ｊ個のハイパーキューブネットワークの何れか一つを利用することにより全てのノードに到達可能であり、
前記ノードの各々は、他のポートに向けてメッセージを送出する際に、宛先ポートに到達するまでに経由するスイッチ数が最も少ないものを前記Ｊ個のハイパーキューブネットワークから優先的に選択し、そのネットワークを構成するスイッチに該メッセージを出力する手段を有することを特徴とするネットワークシステム。
【請求項７】
Ｎ個（Ｎ≦Ｐ＝２のｎ乗であり、ｎは２以上の整数）のノードを相互に接続するためのネットワークシステムであって、
前記ノードの各々に接続され前記ノードの数と同数のスイッチを、各々が有するＪ個（Ｊは２以上の整数）のネットワークを含み、
前記ノードを接続する前記ネットワークの各ポートは０から（Ｎ−１）までの固有の識別子を有し、
Ｎ×Ｊ個の前記スイッチはそれぞれ（ｎ−１）本のスイッチ間双方向リンクを有し、
前記Ｎ個の第ｊスイッチ（ｊは１からＪまでの整数）の第ｍリンク（ｍは０から（ｎ−２）までの整数）は、Ｋｊ（ｍ）（Ｋｊ（ｍ）はｍを引数とする関数であり、０から（Ｐ−１）までの整数の任意の一つをとる）と前記第ｊスイッチが接続しているポートの識別子との排他論理和をとって得られる値を識別子に持つポートが存在する場合、そのポートと接続したスイッチの第ｍリンクと接続し、前記関数Ｋｊ（ｍ）で作られる前記Ｎ個のスイッチ間の接続関係を含む第ｊハイパーキューブネットワークを構成し、
前記第１〜第３ハイパーキューブネットワークは異なる接続関係で構成され、前記Ｊ個のハイパーキューブネットワークの何れか一つを利用することにより全てのノードに到達可能であり、
前記ノードの各々は、他のポートに向けてメッセージを送出する際に、宛先ポートに到達するまでに経由するスイッチ数が最も少ないものを前記Ｊ個のハイパーキューブネットワークから優先的に選択し、そのネットワークを構成するスイッチに該メッセージを出力する手段を有することを特徴とするネットワークシステム。
【請求項８】
前記ネットワークの幾つかにおけるハイパーキューブの接続に捻りが加えられることを特徴とする請求項３〜７いずれか記載のネットワークシステム。
【請求項９】
前記第１ハイパーキューブネットワークの関数Ｋ１（ｍ）はｎビットの２進数で、ビットｍが１で他のビットが０の数字であり、前記第２ハイパーキューブネットワークの関数Ｋ２（ｍ）は、
ｍがｑ（ｑは０から（ｎ−１）の整数）より小さい場合、Ｋ２（ｍ）＝Ｋ１（ｍ）であり、
ｍがｑ以上の場合、２進数で下位ｑビットは任意の値をとり、
上位（ｎ−ｑ）ビットは、
（１）（ｎ−ｑ）が奇数の場合、
（ａ）ｍがｑのとき全ビットが１の数字であり、ｍがｑ以外のときビットｍが０で他が１の数字、あるいは、
（ｂ）ｍがｑのとき全ビットが１の数字であり、ｍがｑ以外のときビットｍとビットｑが０で他が１の数字、あるいは、
（ｃ）ｍがｑのとき全ビットが１の数字であり、ｍがｑ以外のときビットｍとビットｑが１で他が０の数字、あるいは、
（ｄ）ｍがｑのとき全ビットが１の数字であり、ｍがｑ以外のときビットｍが１で他が０の数字、あるいは、
（ｅ）ｍがｑのときビットｑが１で他が０の数字であり、ｍがｑ以外のときビットｍが０で他が１の数字、あるいは、
（ｆ）ｍがｑのときビットｑが１で他が０の数字であり、ｍがｑ以外のときビットｍとビットｑが０で他が１の数字、あるいは、
（ｇ）ｍがｑのときビットｑが１で他が０の数字であり、ｍがｑ以外のときビットｍとビットｑが１で他が０の数字であり、
（２）（ｎ−ｑ）が偶数の場合、
（ａ）ｍがｑのとき全ビットが１の数字であり、ｍがｑ以外のときビットｍが０で他が１の数字、あるいは、
（ｂ）ｍがｑのとき全ビットが１の数字であり、ｍがｑ以外のときビットｍとビットｑが０で他が１の数字、あるいは、
（ｃ）ｍがｑのとき全ビットが１の数字であり、ｍがｑ以外のときビットｍが１で他が０の数字、あるいは、
（ｄ）ｍがｑのときビットｑが０で他が１の数字であり、ｍがｑ以外のときビットｍが０で他が１の数字、あるいは、
（ｅ）ｍがｑのときビットｑが０で他が１の数字であり、ｍがｑ以外のときビットｍとビットｑが１で他が０の数字、あるいは、
（ｆ）ｍがｑのときビットｑが１で他が０の数字であり、ｍがｑ以外のときビットｍとビットｑが１で他が０の数字である、
ことを特徴とする請求項６記載のネットワークシステム。
【請求項１０】
ｑ（ｑは０から（ｎ−１）の整数）で（ｎ−ｑ）が２以上の偶数であり、
前記第１ハイパーキューブネットワークの関数Ｋ１（ｍ）は、
（１）ｍがｑ（ｑは０から（ｎ−１）の整数）より小さい場合、ビットｍが１で他が０の数字であり、
（２）ｍがｑ以上の場合、２進数で下位ｑビットは任意の値をとり、上位（ｎ−ｑ）ビットはビット（ｍ＋１）が１で他が０の数字であり、
前記第２ハイパーキューブネットワークの関数Ｋ２（ｍ）は、
（１）ｍがｑ（ｑは０から（ｎ−１）の整数）より小さい場合、Ｋ２（ｍ）＝Ｋ１（ｍ）であり、
（２）ｍがｑ以上の場合、２進数で下位ｑビットは任意の値をとり、上位（ｎ−ｑ）ビットはビット（ｍ＋１）が０で他が１の数字であり、
前記第３ハイパーキューブネットワークの関数Ｋ３（ｍ）は、
（１）ｍがｑ（ｑは０から（ｎ−１）の整数）より小さい場合、Ｋ３（ｍ）＝Ｋ１（ｍ）であり、
（２）ｍがｑ以上の場合、２進数で下位ｑビットは任意の値をとり、上位（ｎ−ｑ）ビットはビット（ｍ＋１）とビットｑが１で他が０の数字である、
ことを特徴とする請求項７記載のネットワークシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は複数のノードを相互に接続するネットワークシステムに関し、特にノード間通信のレイテンシを削減することができるネットワークシステムに関するものである。
【背景技術】
【０００２】
従来、ハイパーキューブネットワークでそのネットワークの性能を向上させる技術が非特許文献１に開示されている。この非特許文献１に開示の技術について、以下に図面を参照しつつ説明する。なお、一例として、ネットワークに接続されるノード数が８の場合について説明するものとする。
【０００３】
図２２に、ネットワーク150 により接続されるノード100-0 の構成を示す。ノード100-0 は、メッセージを発生させる通信発生装置101-0 を有する。通信発生装置101-0 で生成されたメッセージは、通信制御装置102-0 に渡され、ルーティング情報を持ったパケットに変換されて、ネットワーク150 のスイッチ103-0 に渡される。スイッチ103-0 は、ルーティング情報を参照し、双方向リンク104-0 〜104-3 の何れかに当該パケットを出力する。
【０００４】
図２３はネットワーク150 を構成する８個のスイッチ103-0 〜103-7 の接続関係を示したものである。スイッチ103 の第ｍリンク（ｍは０，１，２，３とする）は、それぞれ２進数で“001 ”，“010 ”，“100 ”，“111 ”と表される数字と、スイッチ番号（図中カッコ内に２進数で表示された数字で該スイッチと接続されたノードの番号とも一致）との排他論理和をとって得られる数字で表されるスイッチ103 と接続している。例えば、スイッチ103-0 は第０リンクでスイッチ103-1 と接続し、第１リンクではスイッチ103-2 と、第２リンクではスイッチ103-4 と、第３リンクではスイッチ103-7 と、それぞれ接続する。
【０００５】
この技術は、従来第０から第２の３本のリンクでハイパーキューブネットワークを構成していたものに、さらに第３リンク（図中点線で示した接続）を加えることにより、あるノード100 から別のノード100 に到達するために経由するスイッチ間のリンク数（以下、Ｈｏｐ数と記す）を減らす効果を持たせている。
【０００６】
図２４に、第０から第２リンクにより構成した場合のノード100-0 から他のノード100 へのＨｏｐ数を示す。また、図２５に、第０から第３リンクにより構成した場合のＨｏｐ数を示す。これから明らかなように、ノード100-0 からの平均Ｈｏｐ数は１．５から１．２５に減らすことができている。図２４や図２５において、ノード番号と宛先ノード番号との排他論理和を取って得られる数字を、ノード番号として記したものとして解釈すれば、他のノード100-1 〜100-7 でも、同様に、平均Ｈｏｐ数が１．５や１．２５となる。
【０００７】
このように、この従来技術では、スイッチのリンク数を１本増やすことで、ノード100 間の平均Ｈｏｐ数を小さくしてネットワークの性能を向上させることが可能となっている。
【０００８】
また、非特許文献２を参照すると、ハイパーキューブネットワークで、リンクを捻りノード間の平均Ｈｏｐ数を小さくする技術が開示されている。この非特許文献２の技術を図面を参照しつつ説明する。なお、ネットワークに接続されるノード数が８の場合について説明するものとする。
【０００９】
ノードの構成は、先の非特許文献１の場合と同じく、図２２に示す構成となっている。図２６に、スイッチ103-0 〜103-7 の接続関係を示す。この例では、従来、スイッチ103-0 とスイッチ103-2 とを接続していたリンクと、スイッチ103-1 とスイッチ103-3 を接続していたリンクとを捻り、スイッチ103-0 とスイッチ103-3 とを、スイッチ103-1 とスイッチ103-2 とを、それぞれ接続したものである。
【００１０】
これにより、スイッチ103-0 から他のスイッチ103 へのＨｏｐ数は、図２７に示すように、Ｈｏｐ数１のスイッチが３個、Ｈｏｐ数２のスイッチが４個となる。他のスイッチ103 でも同様である。これによりノード間の平均Ｈｏｐ数を１．５から約１．４に小さくすることが可能となっている。このように、この従来技術では、スイッチのリンクを捻ることにより、ノード100 間の平均Ｈｏｐ数を小さくして、ネットワークの性能を向上させることができるようになっている。
【００１１】
また、特許文献１を参照すると、階層的に構成された複数のハイパーキューブネットワークを持ち、スイッチのリンク数を減らす技術が開示されている。この特許文献１の技術について、図面を参照しつつ、ネットワークに接続されるノード数が３２の場合について説明する。
【００１２】
ノード200-0 の構成を図２８に、ノード200-1 の構成を図２９に、それぞれ示す。ノード200-0 は、メッセージを発生させる通信発生装置201-0 を有する。通信発生装置201-0 で生成されたメッセージは、通信制御装置202-0 に渡され、ルーティング情報を持ったパケットに変換されて、バス205-0 を介してネットワーク250 のスイッチ203-0 あるいはネットワーク251 のスイッチ213-0 に渡される。スイッチ203-0 はルーティング情報を参照し、双方向リンク204-0-0 〜204-3-0 の何れかにこのパケットを出力する。スイッチ213-0 も同様に、ルーティング情報を参照し、双方向リンク214-0-0 〜214-3-0 の何れかにパケットを出力する。また、スイッチ203-0 およびスイッチ213-0 は、バス205-0 で相互に接続され、ルーティング情報に従ってスイッチ間でパケットの受け渡しを行う。
【００１３】
ノード200-1 の構成を図２９に示す。ノード200-0 との違いは、ネットワーク251 とは接続せず、ネットワーク250 を構成するスイッチ203-1 とのみバス205-1 を介して接続している点である。
【００１４】
図３０にネットワーク250 の構成を示す。３２個のノードが８個のノードからなる４つのクラスタに分割され、クラスタ内の８個のノードがネットワーク250 で接続される。図中の白丸は一つのスイッチを表し、その横の３ビットの２進数は各スイッチが接続するノードの番号の下位３ビットを表している。図から明らかなように、このネットワーク250 は３次元のハイパーキューブ構成である。図３１にネットワーク250 とネットワーク251 との両方の構成を示す。図中黒丸で示したものは、ノード200-0 のように、ネットワーク250 とネットワーク251 との両方に接続しているノードを表しており、白丸はノード200-1 のようにネットワーク250 にのみ接続しているノードを表している。
【００１５】
ネットワーク251 は各４個のクラスタの中からそれぞれ下位３ビットが０００と１１１の２個のノードを選び、それら計８個のノードを３次元のハイパーキューブで接続したものである。
【００１６】
このように構成することにより、従来３２ノードを接続するハイパーキューブではスイッチのリンク数が５であったのを、３に減らすことができている。一方、ノード間の平均Ｈｏｐ数は、バス205 を介したスイッチ間の通信も１Ｈｏｐとして数えると、約４となる。
【００１７】
【特許文献１】特開平５−２０４８７６号公報
【非特許文献１】“Properties and Performance of Folded Hypercubes ”, Ahmed El-Amawy and Shahram Latifi, IEEE TRANSACTION ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 2, NO. 1, JANUARY 1991
【非特許文献２】“The Twisted N-Cube with Application to Mutiprocessing ”, Abdol-Hossein Esfahanian, Lionel M. Ni, and Bruce E. Sagan, IEEE TRANSACTION ON COMPUTERS, VOL. 40, NO. 1, JANUARY 1991
【発明の開示】
【発明が解決しようとする課題】
【００１８】
第１の問題点は、スイッチのリンク数が増加することである。その理由は、非特許文献１の技術では、スイッチにリンクを付加してノード間の平均Ｈｏｐ数を小さくしているからである。第２の問題点は、スイッチのリンク数が多いことにある。その理由は、ノード数がＮ（Ｎは２のｎ乗）のとき、非特許文献１の技術では、スイッチに（ｎ＋１）本のリンクを必要とし、非特許文献２の技術では、スイッチにｎ本のリンクを必要とするからである。第３の問題点は、特許文献１の技術では、通信制御装置と複数のスイッチとの接続としてバスが必要となることである。その理由は、スイッチ間の通信が必要であるからである。
【００１９】
本発明の第１の目的は、異なるネットワークを構成するスイッチ間の通信を不要として、すなわち、他のノードに到達するために複数のネットワークを経由する必要がなく、よってノード間通信のレイテンシの削減を可能としたネットワーク装置を提供することである。
【００２０】
本発明の第２の目的は、スイッチのリンク数を増やすことなくノード間の平均Ｈｏｐ数を減らすことが可能なネットワーク装置を提供することである。
本発明の第３の目的は、ｎ本よりも少ないリンク数でＮ個のノード数を接続可能なネットワーク装置を提供することである。
【課題を解決するための手段】
【００２１】
本発明によるネットワクーシステムは、複数のノードを相互に接続するためネットワークシステムであって、前記複数のノードの各々に接続され前記ノードの数と同数のスイッチを、各々が有する複数のネットワークを含み、あるノードが他のノードに対してメッセージを送出する際に、前記複数のネットワークのいずれか一つを利用することにより、前記他のノードへ前記メッセージが到達可能に構成されていることを特徴とする。また、前記ノードの各々は、他のノードへメッセージわ送信する場合、経由するスイッチ数が最も少ないネットワークを選択してこの選択したネットワーク内のスイッチを介して前記メッセージを送信する手段を有することを特徴とする。
【００２２】
本発明による他のネットワクーシステムは、Ｎ個（Ｎ≦Ｐ＝２のｎ乗であり、ｎは２以上の整数）のノードを相互に接続するためのネットワークシステムであって、前記ノードの各々に接続され前記ノードの数と同数のスイッチを、各々が有するＪ個（Ｊは２以上の整数）のネットワークを含み、前記ノードを接続する前記ネットワークの各ポートは０から（Ｎ−１）までの固有の識別子を有し、Ｎ×Ｊ個の前記スイッチはそれぞれｎ本のスイッチ間双方向リンクを有し、前記Ｎ個の第ｊスイッチ（ｊは１からＪまでの整数）の第ｍリンク（ｍは０から（ｎ−１）までの整数）は、Ｋｊ（ｍ）（Ｋｊ（ｍ）はｍを引数とする関数であり、０から（Ｐ−１）までの整数の任意の一つをとる）と前記第ｊスイッチが接続しているポートの識別子との排他論理和をとって得られる値を識別子に持つポートが存在する場合、そのポートと接続したスイッチの第ｍリンクと接続し、前記関数Ｋｊ（ｍ）で作られる前記Ｎ個のスイッチ間の接続関係を含む第ｊハイパーキューブネットワークを構成し、前記第１及び第２ハイパーキューブネットワークは異なる接続関係で構成され、前記Ｊ個のハイパーキューブネットワークの何れか一つを利用することにより全てのノードに到達可能であり、前記ノードの各々は、他のポートに向けてメッセージを送出する際に、宛先ポートに到達するまでに経由するスイッチ数が最も少ないものを前記Ｊ個のハイパーキューブネットワークから優先的に選択し、そのネットワークを構成するスイッチに該メッセージを出力する手段を有することを特徴とする。
【００２３】
本発明による更に他のネットワークシステムは、Ｎ個（Ｎ≦Ｐ＝２のｎ乗であり、ｎは２以上の整数）のノードを相互に接続するためのネットワークシステムであって、前記ノードの各々に接続され前記ノードの数と同数のスイッチを、各々が有するＪ個（Ｊは２以上の整数）のネットワークを含み、記ノードを接続する前記ネットワークの各ポートは０から（Ｎ−１）までの固有の識別子を有し、Ｎ×Ｊ個の前記スイッチはそれぞれ（ｎ−１）本のスイッチ間双方向リンクを有し、前記Ｎ個の第ｊスイッチ（ｊは１からＪまでの整数）の第ｍリンク（ｍは０から（ｎ−２）までの整数）は、Ｋｊ（ｍ）（Ｋｊ（ｍ）はｍを引数とする関数であり、０から（Ｐ−１）までの整数の任意の一つをとる）と前記第ｊスイッチが接続しているポートの識別子との排他論理和をとって得られる値を識別子に持つポートが存在する場合、そのポートと接続したスイッチの第ｍリンクと接続し、前記関数Ｋｊ（ｍ）で作られる前記Ｎ個のスイッチ間の接続関係を含む第ｊハイパーキューブネットワークを構成し、前記第１〜第３ハイパーキューブネットワークは異なる接続関係で構成され、前記Ｊ個のハイパーキューブネットワークの何れか一つを利用することにより全てのノードに到達可能であり、前記ノードの各々は、他のポートに向けてメッセージを送出する際に、宛先ポートに到達するまでに経由するスイッチ数が最も少ないものを前記Ｊ個のハイパーキューブネットワークから優先的に選択し、そのネットワークを構成するスイッチに該メッセージを出力する手段を有することを特徴とする。
【発明の効果】
【００２４】
本発明によれば、スイッチのリンク数を減らして、且つノード間の平均Ｈｏｐ数を減らすことができるという効果がある。その理由は、３つ以上の接続関係が異なるハイパーキューブネットワークで、Ｊ個のハイパーキューブネットワークの何れか一つを利用することにより、全てのノードに到達可能なものを、リンク数が１本少ないスイッチで構成可能であり、また振り分け回路がそれらハイパーキューブネットワークの中で宛先ノードまでのＨｏｐ数が一番小さいものを優先的に選択して、そのネットワークを構成するスイッチの一つにメッセージを出力するからである。
【００２５】
また、本発明によれば、スイッチのリンク数を増やすことなく、ノード間の平均Ｈｏｐ数を減らすことができる。その理由は、複数の接続関係が異なるハイパーキューブネットワークを有し、振り分け回路がそれらハイパーキューブネットワークの中で宛先ノードまでのＨｏｐ数が一番小さいものを優先的に選択して、そのネットワークを構成するスイッチの一つにメッセージを出力するからである。
【発明を実施するための最良の形態】
【００２６】
以下に、図面を参照しつつ本発明の実施の形態につき詳述する。図１は本発明の第１の実施の形態の構成を示すマルチノードシステムのブロック図である。図１を参照すると、Ｎ個（ＮはＮ≦Ｐ＝２のｎ乗を満足する整数、ｎは自然数）のノード10-0〜10-(N-1)が、Ｊ個（Ｊは２以上の整数）のネットワーク50-1〜50-Jで接続された構成を含む。
【００２７】
また、本発明に基づくノード10-i（ｉは０から（Ｎ−１）の整数）の構成と、そのノード10-iに接続されたＪ個のネットワーク50-1〜50-Jを構成するスイッチ14-1-i〜14-J-iとの接続関係を図２に示す。
【００２８】
ノード10-iは、メッセージを生成する通信発生装置11-iと、通信発生装置11-iが生成したメッセージを受ける通信制御装置12-iを有する。通信制御装置12-1はネットワーク50-1〜50-Jを構成するスイッチ14-1-i〜14-J-iと接続する。スイッチ14-j-i（ｊは１からＪの整数）は、ｎ本の双方向リンク15-j-0-i〜15-j-(n-1)-iを有する。以降ノード10-iはそれぞれ、”ｉ”をノード番号とするものとする。
【００２９】
スイッチ14-j-i（ｊは１からＪの整数）の第ｍリンク15-j-m-i（ｍは０から（ｎ−１）までの整数）は、Ｋｊ（ｍ）（Ｋｊ（ｍ）は０から（Ｐ−１）までの整数の任意の一つで、ｍを引数とする関数である）と該スイッチ14-j-iが接続しているノード10-iのノード番号ｉとの排他論理和をとって得られる番号Ｈｊ（ｍ）をノード番号とするノード10-Hj(m)が存在する場合、即ちＨｊ（ｍ）がＮより小さい場合、そのノード10-Hj(m)と接続したスイッチ14-j-Hj(m)の第ｍリンク15-j-m-Hj(m)と接続する。ネットワーク50-jは、Ｎ個のスイッチ14-jのＮ×ｎ本のリンク15-jのこのようにして定義される接続を含む。
【００３０】
ネットワーク50-1とネットワーク50-2は異なる関数Ｋ１とＫ２とを有し、異なる接続関係で構成される。また、またＪ個のネットワーク50-1〜50-Jの何れか一つを利用することにより全てのノードに到達可能である。
【００３１】
本発明による通信制御装置12-iは、振り分け回路13-iを有する。振り分け回路は、他のノードにメッセージを送信する際に、宛先ノードに到達するまでのＨｏｐ数がもっとも小さいものをＪ個のネットワーク50-1〜50-Jから優先的に選択し、そのネットワークを構成するスイッチに該メッセージを出力する。
【００３２】
このような構成を採用することで、本発明によるマルチノードシステムは、スイッチのリンク数を増やすことなく、ノード間の平均Ｈｏｐ数を減らすことができる。更に、あるノードに到達するのに複数のネットワークを経由する必要がないので、異なるネットワークを構成するスイッチ間の接続が不要になる。
【００３３】
次に、本発明の第２の実施の形態について図面を参照して詳細に説明する。本例におけるマルチノードシステムは図１と同様であり、Ｎ個（ＮはＮ＝２のｎ乗であり、ｎは自然数）のノード10-0〜10-(N-1)が、Ｊ個（Ｊは３以上の整数）のネットワーク50-1〜50-Jで接続された構成を含む。ネットワーク５０は、図３に示すように、それぞれＮ個のスイッチ１４で構成され、各スイッチは（ｎ−１）本のスイッチ間双方向リンク１５を有する。
【００３４】
また、本例におけるノード10-i（ｉは０から（Ｎ−１）の整数）の構成と、そのノード10-iに接続されたＪ個のネットワーク50-1〜50-Jを構成するスイッチ14-1-i〜14-J-iとの接続関係は、図３に示されている。ノード10-iは、メッセージを生成する通信発生装置11-iと、通信発生装置11-iが生成したメッセージを受ける通信制御装置12-iを有する。通信制御装置12-1はネットワーク50-1〜50-Jを構成するスイッチ14-1-i〜14-J-iと接続する。スイッチ14-j-i（ｊは１からＪの整数）は、（ｎ−１）本の双方向リンク15-j-0-i〜15-j-(n-2)-iを有する。以降ノード10-iはそれぞれ、”ｉ”をノード番号とするものとする。
【００３５】
スイッチ14-j-i（ｊは１からＪの整数）の第ｍリンク15-j-m-i（ｍは０から（ｎ−２）までの整数）は、Ｋｊ（ｍ）（Ｋｊ（ｍ）は０から（Ｐ−１）までの整数の任意の一つで、ｍを引数とする関数である）と該スイッチ14-j-iが接続しているノード10-iのノード番号”ｉ”との排他論理和をとって得られる番号”Ｈｊ（ｍ）”をノード番号とするノード10-Hj(m)と接続したスイッチ14-j-Hj(m)の第ｍリンク15-j-m-Hj(m)と接続する。Ｎ個のスイッチ14-jのＮ×ｎ本のリンク15-jがこのようにして接続しネットワーク50-jを構成する。
【００３６】
ネットワーク50-1とネットワーク50-2とネットワーク50-3は、それぞれ異なる関数Ｋ１とＫ２とＫ３を有し、異なる接続関係で構成される。また、Ｊ個のネットワーク50-1〜50-Jの何れか一つを利用することにより、全てのノードに到達可能である。
【００３７】
本例における通信制御装置12-iは振り分け回路13-iを有する。振り分け回路は、他のノードにメッセージを送信する際に、宛先ノードに到達するまでのＨｏｐ数がもっとも小さいものをＪ個のネットワーク50-1〜50-Jから優先的に選択し、そのネットワークを構成するスイッチに該メッセージを出力する。
【００３８】
このような構成を採用することにより、本発明によるマルチノードシステムは、スイッチのリンク数を従来のハイパーキューブネットワークで必要とされたｎ本よりも少ない（ｎ−１）本で、Ｎ個のノードを接続できるマルチプロセッサシステムを構成することができ、また、ノード間の平均Ｈｏｐ数を減らすことができる。更に、あるノードに到達するのに複数のネットワークを経由する必要がないので、異なるネットワークを構成するスイッチ間の接続が不要になる。
【実施例１】
【００３９】
次に、図面を参照して本発明の第１の実施の形態の実施例を説明する。この例は８個のノード10-0〜10-7が２個のネットワーク50-1と50-2で接続される場合を示している。
【００４０】
本実施例のネットワーク50-1及び50-2におけるスイッチ１４の接続関係を図４（Ａ），（Ｂ）に示す。図に示した例で、ネットワーク50-1の構成を規定する関数Ｋ１は、Ｋ１（０）＝”001 ”、Ｋ１（１）＝”010 ”、Ｋ１（２）＝”100 ”である。また、ネットワーク50-2の関数Ｋ２は、Ｋ２（０）＝”111 ”、Ｋ２（１）＝”101 ”、Ｋ２（２）＝”011 ”である。
【００４１】
図５に、ネットワーク50-1と50-2のそれぞれについて、ノード10-iからのＨｏｐ数で８個のノード10を分類した結果を示す。図中に示した数字は、”ｉ”と各ノード１０のノード番号との排他的論理和をとって得られる値を示している。以降ノード10-0を例にとり説明する。ネットワーク50-1では、ノード10-0がＨｏｐ数０であり、ノード10-1、10-2、10-4がＨｏｐ数１であり、ノード10-3、10-5、10-6がＨｏｐ数２であり、ノード10-7がＨｏｐ数３である。ネットワーク50-2では、ノード10-0がＨｏｐ数０であり、ノード10-3、10-5、10-7がＨｏｐ数１であり、ノード10-2、10-4、10-6がＨｏｐ数２であり、ノード10-1がＨｏｐ数３である。このように、ネットワーク50-1と50-2では、同じノードでもＨｏｐ数が異なる。
【００４２】
図６に振り分け回路13-iの１構成例を示す。振り分け回路13-iは、宛先ノード番号と自ノード番号”ｉ”を入力とする演算器20-iを有する。この演算器20-iは、入力された２値の排他的論理和を求めた結果を出力する。演算器20-iの出力された値は、テーブル21-iのインデックスとして利用され、選択されたテーブル21-iの値が出力される。このテーブル21-iはノード数と同じエントリ数８で構成される。そして、０番エントリには”１１”、１番エントリには”０１”、２番エントリには”０１”、３番エントリには”１０”、４番エントリには”０１”、５番エントリには”１０”、６番エントリには”１１”、７番エントリには”１０”が格納される。
【００４３】
“０１”が出力された場合、振り分け回路13-iはネットワーク50-1を選択する。”１０”が出力された場合、振り分け回路13-iはネットワーク50-2を選択する。“１１”が出力された場合、ネットワーク50-1あるいはネットワーク50-2のどちらかを選択する。例えば、該ノード番号が偶数であれば、ネットワーク50-1、奇数であれば、ネットワーク50-2としても良い。また、メッセージのあるビットが０であれば、ネットワーク50-1、１であれば、ネットワーク50-2としても良い。また、テーブル21-iに格納する値を”１０”あるいは”０１”のどちらかに固定しても良い。
【００４４】
このように、振り分け回路13-iが利用するネットワークを選択することで、ノード間の平均Ｈｏｐ数は１となる。ネットワーク50-1のみの構成では、平均Ｈｏｐ数１．５であるので、平均Ｈｏｐ数を０．５小さくすることができる。
【００４５】
以上の説明では、Ｎが２の３乗の場合を例にとって説明したが、Ｎが２のｎ乗（ｎは２以上の整数）でも同様に構成することが可能である。その場合、ネットワーク50-1のＫ１（ｍ）はビットｍが１で他が０の数字であり、ネットワーク50-2のＫ２（ｍ）はｍが０のときは全ビットが１の数字、ｍが０以外のときはビットｍが０で他が１の数字である。例えば、ｎが４の場合のネットワーク50-1およびネットワーク50-2は図７（Ａ），（Ｂ）に示す接続関係となる。また、この場合の各ネットワークのノード間Ｈｏｐ数を図８に示す。また、テーブル21-iは図９に示すように１６エントリで構成され、図に示すような値が格納される。この場合平均Ｈｏｐ数は約１．４となる。
【００４６】
また、Ｋ２（ｍ）は、ｎが奇数の場合、次に示す６つの何れかであっても良い。
（１）ｍが０のとき全ビットが１の数字であり、ｍが０以外のときビットｍとビット０が０で他が１の数字。
（２）ｍが０のとき全ビットが１の数字であり、ｍが０以外のときビットｍとビット０が１で他が０の数字。
（３）ｍが０のとき全ビットが１の数字であり、ｍが０以外のときビットｍが１で他が０の数字。
（４）ｍが０のときビット０が１で他が０の数字であり、ｍが０以外のときビットｍが０で他が１の数字。
（５）ｍが０のときビット０が１で他が０の数字であり、ｍが０以外のときビットｍとビット０が０で他が１の数字。
（６）ｍが０のときビット０が１で他が０の数字であり、ｍが０以外のときビットｍとビット０が１で他が０の数字。
【００４７】
また、Ｋ２（ｍ）は、ｎが偶数の場合、次に示す５つの何れかであっても良い。
（１）ｍが０のとき全ビットが１の数字であり、ｍが０以外のときビットｍとビット０が０で他が１の数字、あるいは、
（２）ｍが０のとき全ビットが１の数字であり、ｍが０以外のときビットｍが１で他が０の数字、あるいは、
（３）ｍが０のときビット０が０で他が１の数字であり、ｍが０以外のときビットｍが０で他が１の数字、あるいは、
（４）ｍが０のときビット０が０で他が１の数字であり、ｍが０以外のときビットｍとビット０が１で他が０の数字、あるいは、
（５）ｍが０のときビット０が１で他が０の数字であり、ｍが０以外のときビットｍとビット０が１で他が０の数字である。
ただし、Ｋ２（ｍ）はこれらに制限されるものではなく、０から（Ｐ−１）までの整数のいかなる組み合わせであっても良い。
【実施例２】
【００４８】
次に、図面を参照して本発明の第１の実施の形態の別の実施例を説明する。この例は、１６個のノード10-0〜10-15 が３個のネットワーク50-1、50-2、50-3で接続される場合を示している。本例のネットワーク50-1及び50-2のスイッチ１４の接続関係は実施例１と同じ図７に示した接続関係になる。
【００４９】
図１０に本実施例のネットワーク50-3のスイッチ14-3の接続関係を示す。図に示した例で、ネットワーク50-3の構成を規定する関数Ｋ３は、Ｋ３（０）＝”1110”、Ｋ３（１）＝”0011”、Ｋ３（２）＝”0101”、Ｋ３（３）＝”1001”である。
【００５０】
この場合の各ネットワーク50-1〜50-3のノード間Ｈｏｐ数を図１１に示す。また、テーブル21-iは、図１２に示すように、１６エントリで構成され、図に示すような３ビットの値がそれぞれ格納される。この場合の平均Ｈｏｐ数は約１．１となり、ネットワーク50-1だけの場合の平均Ｈｏｐ数２、ネットワーク50-1とネットワーク50-2の２個で構成される場合の約１．４よりもさらに小さくすることができる。
【実施例３】
【００５１】
次に、図面を参照して本発明の第２の実施の形態の実施例を説明する。この例は、１６個のノード10-0〜10-15 が３個のネットワーク50-1、50-2、50-3で接続される場合を示している。本実施例のネットワーク50-1、50-2、50-3の接続関係を、図１３〜図１５にそれぞれ示す。
【００５２】
図に示した例で、ネットワーク50-1の構成を規定する関数Ｋ１は、Ｋ１（０）＝”0010”、Ｋ１（１）＝”0100”、Ｋ１（２）＝”1000”である。ネットワーク50-2の関数Ｋ２は、Ｋ２（０）＝”1101”、Ｋ２（１）＝”1011”、Ｋ２（２）＝”0111”である。ネットワーク50-3の関数Ｋ３は、Ｋ３（０）＝”0011”、Ｋ３（１）＝”0101”、Ｋ３（２）＝”1001”である。
【００５３】
この場合の各ネットワーク50-1〜50-3のノード間Ｈｏｐ数を図１６に示す。また、テーブル21-iは、図１７に示すように、１６エントリで構成され、図に示すような３ビットの値がそれぞれ格納される。この場合の平均Ｈｏｐ数は約１．５となり、実施例２のネットワーク50-1だけの場合の平均Ｈｏｐ数２よりも小さくすることができている。また、従来１６ノードを接続するハイパーキューブネットワークでは、スイッチのリンク数が４である必要があったが、本実施例では３と、１本少なくて済んでいる。
【００５４】
以上の説明では、Ｎが２の４乗の場合を例にとって説明したが、Ｎが２のｎ乗（ｎは２以上の偶数）でも、同様に構成することが可能である。その場合、ネットワーク50-1の構成を規定する関数Ｋ１（ｍ）は、ビット（ｍ＋１）が１で、他が０の数字である。ネットワーク50-2の関数Ｋ２（ｍ）は、ビット（ｍ＋１）が０で、他が１の数字である。ネットワーク50-3の関数Ｋ３（ｍ）は、ビット０とビット（ｍ＋１）が１で、他が０の数字である。
【実施例４】
【００５５】
次に、図面を参照して本発明の第２の実施の形態の別の実施例を説明する。この例は、実施例３に非特許文献１で開示されている従来技術を適用した例である。この従来技術では、スイッチのリンクを１本追加することにより、ノード間平均Ｈｏｐ数を少なくするものである。本実施例のネットワーク50-1の接続関係を図１８に示す。ネットワーク50-2、ネットワーク50-3も同様であるので、ここでは省略する。
【００５６】
図に示した例で、ネットワーク50-1の構成を規定する関数Ｋ１は、Ｋ１（０）＝”0010”、Ｋ１（１）＝”0100”、Ｋ１（２）＝”1000”、Ｋ１（３）＝”1110”である。追加したリンクに対応する関数Ｋ１（３）は、ネットワーク50-1で到達できるノードの中で最もＨｏｐ数が多いものを接続するものである。
【００５７】
他のネットワーク50-2やネットワーク50-3でも、同様の接続を行って、各ネットワーク50-1〜50-3のノード間Ｈｏｐ数を求めた結果を図１９に示す。また、テーブル21-iは実施例３と同じく、図１７に示すように、１６エントリで構成され、図に示すような３ビットの値がそれぞれ格納される。この場合の平均Ｈｏｐ数は約１．１となり、実施例３の平均Ｈｏｐ数１．５よりも小さくすることができている。
【実施例５】
【００５８】
次に、図面を参照して本発明の第２の実施の形態の別の実施例を説明する。この例は、実施例３に非特許文献２で開示されている従来技術を適用した例である。この従来技術では、スイッチのリンクを捻ることにより、ノード間平均Ｈｏｐ数を少なくするものである。本実施例のネットワーク50-1の接続関係を図２０に示す。ネットワーク50-2、ネットワーク50-3も同様であるので、ここでは省略する。
【００５９】
図に示した例で、ネットワーク50-1の構成を規定する関数Ｋ１は、実施例３と同様に、Ｋ１（０）＝”0010”、Ｋ１（１）＝”0100”、Ｋ１（２）＝”1000”である。ただし、次の二つのリンク捻りを行ったものである。第１のリンク捻りは、スイッチ14-1-0とスイッチ14-1-4を接続していたリンクと、スイッチ14-1-2とスイッチ14-1-6を接続していたリンクを捻り、スイッチ14-1-0とスイッチ14-1-6を、スイッチ14-1-2とスイッチ14-1-4を接続したものである。第２のリンク捻りは、スイッチ14-1-1とスイッチ14-1-5を接続していたリンクと、スイッチ14-1-3とスイッチ14-1-7を接続していたリンクを捻り、スイッチ14-1-1とスイッチ14-1-7を、スイッチ14-1-3とスイッチ14-1-5を接続したものである。
【００６０】
他のネットワーク50-2やネットワーク50-3でも、同様のリンク捻りを行って、各ネットワーク50-1〜50-3のノード０から他のノードへのＨｏｐ数を求めた結果を図２１に示す。また、テーブル21-iは、実施例３と同じく図１７に示すように１６エントリで構成され、図に示すような３ビットの値がそれぞれ格納される。この場合の平均Ｈｏｐ数は約１．４となり、実施例３の平均Ｈｏｐ数１．５よりも小さくすることができている。
【００６１】
（実施形態の変形例）
これまでの実施例の説明では、Ｋ１（ｍ）とＫ２（ｍ）が全てのｍで異なる場合を説明したが、ｍがｑ（ｑは０から（ｎ−１）の整数）より小さい場合は、Ｋ２（ｍ）＝Ｋ１（ｍ）とし、ｍがｑ以上の場合のみＫ２（ｍ）≠Ｋ１（ｍ）としても良い。これは、実装上いくつかのノードとスイッチを一つのまとまりとして、基盤やバックプレーンなどを使ってパターンで配線する場合に、それらのまとまりを部品として共通化できるという利点を持つ。
【００６２】
例えば、ｑを１として、ビット０のみが異なる二つのスイッチを一つの基板上に実装し、そのスイッチの第０リンクをパターンで実現し、バックプレーンを使って二つのスイッチと二つのノードをパターンで配線する場合である。この場合、Ｋ１（０）とＫ２（０）で異なる値を持たせた場合、二つで異なる基盤あるいはバックプレーンを用いる必要が生じ、コストアップの原因となる。Ｋ１（０）とＫ２（０）を同じ値にしておけば、両者で共通の基盤あるいはバックプレーンを用いることができ、コストの増加を押させることが出来る。
【００６３】
このような変形では、例えば実施例１に示した例では、Ｋ１（ｍ）およびＫ２（ｍ）は次のようにすることができる。
（１）Ｋ１（ｍ）はｎビットの２進数で、ビットｍが１で他のビットが０の数字。
（２）Ｋ２（ｍ）は、
（ａ）ｍがｑ（ｑは０から（ｎ−１）の整数）より小さい場合、Ｋ２（ｍ）＝Ｋ１（ｍ）、
（ｂ）ｍがｑ以上の場合、２進数で下位ｑビットは任意の値をとり、上位（ｎ−ｑ）ビットは、ｍがｑのとき全ビットが１の数字であり、ｍがｑ以外のときビットｍが０で他が１の数字。
【００６４】
また、実施例３に示した例では、ｎが２以上の偶数の場合に適用できる例として示したが、（ｎ−ｑ）が２以上の偶数の場合に適用することが可能となる。またそのとき、Ｋ１（ｍ）、Ｋ２（ｍ）、Ｋ３（ｍ）はそれぞれ次のようになる。
（１）Ｋ１（ｍ）
（ａ）ｍがｑ｛ｑは０から（ｎ−１）の整数｝より小さい場合、ビットｍが１で他が０の数字、
（ｂ）ｍがｑ以上の場合、２進数で下位ｑビットは任意の値をとり、上位（ｎ−ｑ）ビットはビット（ｍ＋１）が１で他が０の数字。
（２）Ｋ２（ｍ）
（ａ）ｍがｑ｛ｑは０から（ｎ−１）の整数｝より小さい場合、Ｋ２（ｍ）＝Ｋ１（ｍ）、
（ｂ）ｍがｑ以上の場合、２進数で下位ｑビットは任意の値をとり、上位（ｎ−ｑ）ビットはビット（ｍ＋１）が０で他が１の数字。
（３）Ｋ３（ｍ）
（ａ）ｍがｑ｛ｑは０から（ｎ−１）の整数｝より小さい場合、Ｋ３（ｍ）＝Ｋ１（ｍ）であり、
（ｂ）ｍがｑ以上の場合、２進数で下位ｑビットは任意の値をとり、上位（ｎ−ｑ）ビットはビット（ｍ＋１）とビットｑが１で他が０の数字である。
【図面の簡単な説明】
【００６５】
【図１】本発明のマルチノードシステムの構成を示す図である。
【図２】本発明の第１の実施の形態のマルチノードシステムのノードの構成とそのノードと接続するネットワークのスイッチを示した図である。
【図３】本発明の第２の実施の形態のマルチノードシステムのノードの構成とそのノードと接続するネットワークのスイッチを示した図である。
【図４】本発明の実施例１のネットワークの構成を示した図である。
【図５】本発明の実施例１のノード間Ｈｏｐ数を示した図である。
【図６】本発明の実施例１の振り分け回路の構成を示した図である。
【図７】本発明の実施例１でｎが４の場合のネットワークの構成を示した図である。
【図８】本発明の実施例１でｎが４の場合のノード間Ｈｏｐ数を示した図である。
【図９】本発明の実施例１でｎが４の場合の振り分け回路のテーブルの内容を示した図である。
【図１０】本発明の実施例２のネットワークの構成を示した図である。
【図１１】本発明の実施例２のノード間Ｈｏｐ数を示した図である。
【図１２】本発明の実施例２の振り分け回路のテーブルの内容を示した図
【図１３】本発明の実施例３のネットワークの構成を示した図である。
【図１４】本発明の実施例３のネットワークの構成を示した図である。
【図１５】本発明の実施例３のネットワークの構成を示した図である。
【図１６】本発明の実施例３のノード間Ｈｏｐ数を示した図である。
【図１７】本発明の実施例３の振り分け回路のテーブルの内容を示した図である。
【図１８】本発明の実施例４のネットワークの構成を示した図である。
【図１９】本発明の実施例４のノード間Ｈｏｐ数を示した図である。
【図２０】本発明の実施例５のネットワークの構成を示した図である。
【図２１】本発明の実施例５のノード間Ｈｏｐ数を示した図である。
【図２２】従来のマルチノードシステムのノードの構成とそのノードと接続するネットワークのスイッチを示した図である。
【図２３】従来のネットワークの構成の一例を示した図である。
【図２４】従来のネットワークで、第３リンクがない場合のノード間Ｈｏｐ数を示した図である。
【図２５】従来のネットワークのノード間Ｈｏｐ数を示した図である。
【図２６】従来のネットワークの構成の他の例を示した図である。
【図２７】従来のネットワークのノード間Ｈｏｐ数を示した図である。
【図２８】従来のマルチノードシステムのあるノードの構成とそのノードと接続するネットワークのスイッチを示した図である。
【図２９】従来のマルチノードシステムの別のノードの構成とそのノードと接続するネットワークのスイッチを示した図である。
【図３０】ハイパーキューブ接続のネットワークの一例の構成を示す図である。
【図３１】ハイパーキューブ接続のネットワークの他の例の構成を示す図である。
【符号の説明】
【００６６】
１０，１００  ノード
１１，１０１  通信発生装置
１２，１０２  通信制御装置
１３  振り分け回路
１４，１０３  スイッチ
１５  双方向リンク
２０  演算器
２１  テーブル
５０  ネットワーク
【図１】
2006080703.tif 000003
【図２】
2006080703.tif 000004
【図３】
2006080703.tif 000005
【図４】
2006080703.tif 000006
【図５】
2006080703.tif 000007
【図６】
2006080703.tif 000008
【図７】
2006080703.tif 000009
【図８】
2006080703.tif 000010
【図９】
2006080703.tif 000011
【図１０】
2006080703.tif 000012
【図１１】
2006080703.tif 000013
【図１２】
2006080703.tif 000014
【図１３】
2006080703.tif 000015
【図１４】
2006080703.tif 000016
【図１５】
2006080703.tif 000017
【図１６】
2006080703.tif 000018
【図１７】
2006080703.tif 000019
【図１８】
2006080703.tif 000020
【図１９】
2006080703.tif 000021
【図２０】
2006080703.tif 000022
【図２１】
2006080703.tif 000023
【図２２】
2006080703.tif 000024
【図２３】
2006080703.tif 000025
【図２４】
2006080703.tif 000026
【図２５】
2006080703.tif 000027
【図２６】
2006080703.tif 000028
【図２７】
2006080703.tif 000029
【図２８】
2006080703.tif 000030
【図２９】
2006080703.tif 000031
【図３０】
2006080703.tif 000032
【図３１】
2006080703.tif 000033