JPH05204876A

JPH05204876A - 階層型ネットワークおよび階層型ネットワークを用いたマルチプロセッサシステム

Info

Publication number: JPH05204876A
Application number: JP4261112A
Authority: JP
Inventors: Shinji Fujiwara; 真二藤原; Yoichi Shintani; 洋一新谷; Mitsuru Nagasaka; 充長坂
Original assignee: Hitachi Ltd
Current assignee: Hitachi Ltd
Priority date: 1991-10-01
Filing date: 1992-09-30
Publication date: 1993-08-13

Abstract

(57)【要約】【目的】膨大なプロセッサ台数を有するマルチプロセッ
サシステムにおける新しいプロセッサ間接続ネットワー
クとして、階層型ネットワークを提供する。【構成】本発明の階層型ネットワークは、互いのノード
がｐ進ｎ次元キューブとして接続線で結合されているネ
ットワークを複数個階層的に接続して一つのネットワー
クを構成するものであり、下層のｐ進ｎ次元ネットワー
クから複数のノードを選択し、選択されたゲートノード
間をｐ進ｍ次元キューブとして相互に接続して次層のｐ
進ｍ次元ネットワークを構成する。同様にして、複数の
次層のｐ進ｍ次元ネットワークからゲートノードを選択
し、ｐ進１次元キューブとして相互に接続して、さらに
上層のｐ進１次元ネットワークを構成して、全体で１つ
の階層型ネットワークを構成する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】ノード間パスの数が少ない階層型
ネットワークと、それを利用するマルチプロセッサシス
テムに関する。

【０００２】

【従来の技術】複数のノードを結合するネットワークに
関しては、従来から研究がなされており、種々のネット
ワークが考案されている。これらのノードの結合方式に
関しては、黒川恭一氏および相礒秀夫氏による解説論文
「結合方式」（情報処理、vol２７，Ｎo．９，Sep. １
９８９，pp．１００５−１０２１）に紹介がなされてい
る。この解説ではネットワークは、入出力間の結合が動
的に変化するか否かに従って、「動的」ネットワークお
よび「動的」ネットワークに分離されている。動的なネ
ットワークとしてはクロスバネットワーク、ベースライ
ンネットワーク、オメガネットワーク、バタフライネッ
トワーク（間接ｎキューブ）、デルタネットワーク、バ
ンヤンネットワーク等が挙げられている。一方、静的な
ネットワークとしては、リングネットワーク、スターネ
ットワーク、ツリーネットワーク、格子網、完全結合
網、ｎキューブ、ＣＣＣ等が挙げられている。

【０００３】一方、計算機アーキテクチャの分野では、
上記に挙げたネットワークを適用した種々のマルチプロ
セッサシステムが研究開発されており、それらの代表的
なものとしては、Ｅ．Ｄ．Brocks 等による論文「ＢＢ
ＮＴＣ２０００ Architecture and Programming Mod
els」 (Proc. of COMPCON '９１pp．４６−５０，１９９
１）に記載のバタフライネットワークを用いたＴＣ２０
００（米国ＢＢＮ社）がある。また、日本特許「特開昭
５７−２０１９３１」に記載されている２重化されたYn
et と呼ばれるツリーネットワークを用いたマルチプロ
セッサシステム等が挙げられる。近年ではネットワーク
として特にハイパキューブ(ｎキューブ）型が注目され
ており、この型のネットワークを適用したマルチプロセ
ッサとしてｎＣＵＢＥ（米国ｎＣＵＢＥ社）や、ｉＰＳ
Ｃ（米国インテル社）が開発されている。

【０００４】このようにハイパキューブは今日のマルチ
プロセッサシステムの主流の一つとなってきている。ま
た、上記静的なネットワークの大部分を包括する概念と
して、ｋ-array n-cube がある(Ｊ．DALLY，“Preforma
nce Analysis of k-arry n-cube Interconnection Netw
ork”, Trans. on Computers, vol 39, No. 6, JUNE199
0). ハイパキューブはもちろんのこと、リングネットワ
ーク、格子網、トータルネットワーク、オメガネットワ
ーク、間接ｎキューブ等は、全て、このｋ-array ｎ-cu
be ネットワークの特化したものあるいはそれと同型の
ネッワークである。

【０００５】

【発明が解決しようとする課題】従来技術のネットワー
クを構成するハイパキューブについて図４，図５を用い
て簡単に説明する。図４の（ａ）から（ｄ）はそれぞれ
２次元、３次元、４次元のハイパキューブを示し、図５
は５次元のハイパキューブを示すノード数Ｎと１個のノ
ードから出るノード間接続リンクの本数Ｍは１次元の場
合はＮ＝２、Ｍ＝１、２次元の場合はＮ＝４、Ｍ＝２、
３次元の場合はＮ＝８、Ｍ＝３、４次元の場合はＮ＝１
６、Ｍ＝４、５次元の場合はＮ＝３２、Ｍ＝５、ｎ次元
の場合はＮ＝２＾ｎ（演算子“＾”はベき乗を表わす。
以下同じ）、Ｍ＝ｎ。従来技術のハイパキューブではノ
ード数が増加するにつれて、ノード間接続バスの本数Ｍ
Ｍが増大する。例えばノード数Ｎ（＝２＾ｎ）のハイパ
キューブではＭＭ＝（Ｎlog₂Ｎ）／２。例えば、図４の
（ｂ）に示される１次元の場合はＮ＝２であるから、Ｍ
Ｍ＝（２log₂２）／２＝１に示される３次元の場合はＮ
＝８であるから、ＭＭ＝（８log₂８）／２＝１２、ノー
ド数Ｎが２＾１６個の場合にはＭＭ＝５２４，２８８本
となる。このようにノード数が増大するとノード間接続
バスの数が膨大になる。そのため、各ノードにプロセッ
サを配置するようにこのネットワークを用いてマルチプ
ロセッサシステムを構成することが実際上困難になって
くる。

【０００６】この問題を解決するためにハイパキューブ
の各頂点ノードをリング状にしてノード数を拡張するＣ
ＣＣ（Cube Connected Cycle）ネットワーク等が考案さ
れた（前記解説論文第１０２７に記載）。しかし、こ
のネットワークでは各ノードの位置により、ノード間転
送距離が、同程度のノード数を持つハイパキューブと比
べて、大きくなってしまうという問題があった。前記解
説論文の第１０１４頁に記載の階層型ネットワークであ
るツリーネットワークでは、ノード間の接続バス数が小
さくなる半面ＣＣＣと同機にノード間転送距離が、大き
くなるという問題点がある。例えば、（２＾ｎ）−１個
のノードを有するｎ段の２進ツリーネットワークでは、
ノード間転送距離がほぼ同数のノードを有するｎ次元ハ
イパキューブと比較して約２倍になる。マルチプロセッ
サシステムにおいてはプロセッサ間の通信時間が非常に
重要である。プロセッサ間通信時間は通常ノード間転送
経路の距離に比例して増大する。ハイパキューブネット
ワークの場合、ノード間転送距離の最大値 Dmax は、ノ
ード数Ｎ（＝２＾ｎ）とした場合、 Dmax ＝log₂Ｎとな
る。例えばノード数Ｎ＝２＾１６であるシステムではそ
の最大転送距離 Dmax ＝１６となる。

【０００７】また、ハイパキューブネットワークを利用
したマルチプロセッサシステムでは拡張性に課題があ
る。すなわち、任意のハイパキューブシステムにおいて
あるプロセッサを付加する場合には、対応する既存のプ
ロセッサのネットワーク接続ポートを一つずつ増加させ
る必要がある。したがって、あらかじめ設計されたポー
ト数以上にプロセッサを追加することは事実上不可能で
ある。

【０００８】さらに、トリーネットワークでは、さら
に、転送経路が一意に決定されるため、通信路の閉塞状
態が頻繁に発生しデータの並列転送を阻害するという問
題点があった。

【０００９】加えて、一つのモジュールあるいはＬＳＩ
チップの上に、複数のプロセッサを実装した、１モジュ
ールチップマルチプロセッサシステムを複数用いて大規
模なマルチプロセッサシステムを構築する際には以下の
ような問題点が生じてくる。例えば２＾１６個のプロセ
ッサからなるマルチプロセッサシステムを、例えば１２
８（＝２＾７）個のプロセッサを収めた１チップマルチ
プロセッサを複数ハイパキューブネットワークに適用し
て実現する場合を想定する。このチップを２＾９個もち
いて１６次元ハイパキューブシステムを構築しようとす
ると１チップから、１１５２本のノード間接続バスを出
す必要があり、明らかにピンネックとなる。このような
状況は構成するプロセッサ台数の規模が増大するにつれ
てより深刻な問題となって来る。

【００１０】本発明では、多数のノードを有するネット
ワークを構成する際に、少ないノード間接続バス数で構
成できる階層型ネットワークを提供することを目的とす
る。本発明ではまた、ノード間の最大通信距離が短かい
階層型ネットワークを提供することを目的とする。

【００１１】本発明ではさらに、下層のネットワークの
ノードの中から、より上層のネットワークに属する複数
のノードを選択する手法に符号理論を適用することによ
り、ノード間接続バス数が少なく、かつ、ノード間の最
大転送距離が、同一ノード数を有する単一階層ネットワ
ークと比較して、同等もしくはそれ以下の階層型ネット
ワークを提供することを目的とする。

【００１２】上記の新しい階層型ネットワークにおける
通信方式を提供することも本発明の目的とする。

【００１３】本発明ではまた、かかる新しい階層型ネッ
トワークを用いたマルチプロセッサシステムを提供する
ことを目的とする。

【００１４】本発明では更にネットワークを階層型にす
ることにより拡張性に優れたマルチプロセッサシステム
を提供することを目的とする。

【００１５】本発明では更にまた、複数のプロセッサを
１つのモジュールあるいは半導体チップに実装し、それ
らを複数組み合わせてより大規模なマルチプロセッサシ
ステムを構築する際に、各モジュールあるいは半導体チ
ップ間の接続バス数を少なくすることにより、モジュー
ルあるいは半導体チップのピンネックの問題を回避でき
るマルチプロセッサシステムを提供することを目的とす
る。

【００１６】

【課題を解決するための手段】本発明では、複数のノー
ドを有する複数の下層ネットワークのそれぞれから複数
のノードが上層ネットワークのノードとして選択される
（以下、選択されたノードをゲートノードと呼ぶ）同一
の下層ネットワークに属するゲートノード間は、ネット
ワーク内における通信距離より短くなるように相互に接
続される、同一の下層ネットワークに属さないゲートノ
ード間は、互いに通信が行なえるように相互に接続され
る。これにより、同一下層ネットワーク内での転送距離
を小さくしつつ、異なる下層ネットワークに属するノー
ド間の転送を可能にする階層型ネットワークが提供され
る。

【００１７】また、本発明では、複数のｐ進ｎ次元下層
ネットワークのそれぞれのノードに全下層ネットワーク
内で一意に決定できるｐ進ｎ桁のノード番号を与えられ
る。これらのノード番号を符号とみなしたとき符号語に
相当するノード番号が付与されたノードがゲートノード
として選択され、ゲートノードは、ｐ進ｍ次元上層ネッ
トワークのノードとして、相互に接続される。その結
果、同数のノードを有するｐ進キューブより、ノード間
接続バス数が少なく、通信距離が同等もしくはそれ以下
のネットワークを提供する。

【００１８】本発明では更に、複数の下層ネットワーク
の各々内のノードに一意に与えられたノード番号を符号
と見なしたとき、ノード番号がｔ重誤り訂正符号の符号
語となっているノードがゲートノードとして選択され階
層ネットワークが構築することにより、ノード間接続バ
ス数が小さく、通信距離が同数のノードを有する単階層
ネットワークと同等もしくはそれ以下のネットワークを
提供する。

【００１９】本発明では、上記に示したネットワークの
ノードにプロセッサが配置された、マルチプロセッサシ
ステムを提供する。

【００２０】本発明では、上記マルチプロセッサシステ
ムで、ゲートノードとして選択されたノードを主記憶共
有型マルチプロセッサにより、その他のノード（以下、
リーフノードと呼ぶ）を単一プロセッサにより構成し、
拡張性に優れたマルチプロセッサシステムを提供するこ
とを可能にする。

【００２１】本発明では、前記マルチプロセッサシステ
ムのプロセッサ間通信方式として、ノードに配置された
プロセッサからデータを転送するとき、同一下層ネット
ワークに属するノードに対しては下層ネットワーク内の
最短経路によりデータを転送し、他のネットワークに属
するノードに対しては上層のネットワークに接続される
ゲートノードを介してデータを転送する。

【００２２】さらに前記階層型ネットワークを構成する
際にゲートノードを選択する手段としてｔ重誤り訂正符
号を用いている場合には、リーフノードａから、ゲート
ノードｂへ至る経路を、リーフノードａに与えられた下
層ネットワークにおけるノード番号を符号と見なしてこ
れをｔ重誤り訂正符号における誤り訂正手段により訂正
して該符号の符号語を求め、得られた符号語が割り当て
られたゲートノードｂに至る経路とすることによりデー
タを転送する。

【００２３】

【作用】以上の性能比較からも明らかなように本発明に
よる、多段符号キューブは、従来のハイパキューブに比
べてノード間の接続バスの本数を大幅に削減することが
できる。例えば、符号化に単一誤り訂正符号である
（７、４）線形符号を用い、７次元ハイパキューブを８
個ずつ集めて４段のハイパキューブにインタリーブさせ
た、階層型ネットワーク（以下、４段（７、４）符号キ
ューブと呼ぶ）は、全ノード数が２の（７＋（７−４）
・（４−１））乗個、すなわち、２の１６乗個である
が、ノード間接続バスの本数は２６２,０８０本であ
り、同数ノードを持つ１６次元ハイパキューブのノード
間接続バスの本数５２４,２８８の、約半分となる。一
般にノード数が２のｎ乗である多段符号キューブのノー
ド間接続バスの本数は、基本となるハイパキューブの次
元数をｍ、１つの上層のハイパキューブにまとめる基本
ハイパキューブ数（上記の例の場合は８）をｐとしたと
きに（ｐ／（ｐ−１））・（２＾ｎ）・／２で近似される（演算子「＾」は、べき乗を表す）。した
がって、多段符号キューブのノード間接続バスの本数は
基本となるハイパキューブの次元数ｍおよび基本ハイパ
キューブをまとめる単位ｐは適用する符号に依存して決
まるのである符号化を適用した多段符号キューブのノー
ド間接続バスはそのノード数にのみ比例して増加する。

【００２４】また本発明による多段符号キューブを用い
たマルチプロセッサシステムは、プロセッサ間接続ネッ
トワークの大幅な削減により、低価格で大規模なマルチ
プロセッサシステムを構築することを可能とする。とく
にシステムを拡張する際にゲートノード当たるプロセッ
サのみを拡張すればよいのでそのシステム拡張性は非常
に優れている。

【００２５】さらに本発明では基本ハイパキューブを一
つのモジュール上に実装し、それらを組み合わせてより
大きなネットワークを構築する際のモジュール間の接続
線数を大幅に減らすことができる。例えば先の基本キュ
ーブが７次元ハイパキューブである多段（７，４）符号
キューブではノード数が２の１６乗のときにそのモジュ
ール間接続線数が６７本でありこれは１チップに１２８
プロセッサを実装した場合に十分実現可能な数字であ
る。一方、１６次元ハイパキューブを７次元ハイパキュ
ーブを基本キューブとして実装するとモジュール間の接
続線数は１１５２本になり、彼我の差は歴然としてい
る。

【００２６】さらに本発明では、多段符号キューブのゲ
ートノードユニットを主記憶共有のマルチプロセッサ構
成とすることで、プロセッサモジュールボードの追加の
みでそのゲートノードユニットの機能を拡張できる。こ
のことにより、本システムのは旧システムのハードウェ
アを変更することなくプロセッサボードおよびネットワ
ークボード等の追加のみでシステムを拡張できる。

【００２７】本発明による多段符号キューブを適用する
と、ノード間通信時間をハイパキューブと比較して削減
することが可能である。例えば前述の４段（７，４）符
号キューブではノード間最大距離が１３であり、プロッ
サ数が等しいハイパキューブの１６よりも小さい。ま
た、全システムに対するブロードキャストに要するステ
ップ数もそれに応じて削減され、さらに、ブロードキャ
ストノードを最上層のハイパキューブに属するノードに
すると、そのステップ数はさらに削減される。例えば先
の例ではブロードキャストノードを第４段ハイパキュー
ブにすると、１０ステップで実行できる。

【００２８】

【実施例】以下に、本発明による階層型ネットワーク
と、それを利用したマルチプロセッサシステムを、添付
図面を参照して、詳細に説明する。

【００２９】本発明ではｍ次元ハイパキューブを基本ネ
ットワークとし、複数の基本ネットワークの各々の中か
らいくつかのノードが選択され（以下ゲートノードと呼
ぶ）、選択されたゲートノードからより上位のネットワ
ークが形成される。この上位のネットワークを次の段の
基本ネットワークとして、再帰的に同じ処理を繰り返す
ことにより階層ネットワークが構成される。

【００３０】一般に、ｐ進数ｎ桁の数字を情報桁と誤り
訂正桁からなる符号と考えると、誤り訂正符号空間の一
点を表わす。例えばｍ次元ハイパキューブの各ノードに
２進数を、ノード番号として付与した場合、ノード番号
が符号語となっているノードがゲートノードとして選択
される。これにより各ノードは自ノード番号が誤りを訂
正することができる符号（以下ＥＣＣという）か否かを
判断することにより自ノードがゲートノードであるか否
かを判定することが出来る。自ノートがゲートノード以
外のノード（以下、リーフノードと呼ぶ）であった場合
には、自ノード番号に最も近いＥＣＣを求めることによ
り、自ノードに最も近いゲートノードと通信することが
出来る。

【００３１】このようにゲートノードを選択する際に符
号理論を適用すると、自ノードに最も近いゲートノード
のアドレスを容易に求めることができ、また、ゲートノ
ードを基本ネットワーク内から均一に選択することがで
きるという利点がある。ゲートノードを選択する方法と
して符号理論を用いた階層型ネットワークのことを、以
下では「多段符号ネットワーク」と呼び、特に基本ネッ
トワークとして「ハイパキューブ」を用いるものを「多
段符号キューブ」と呼ぶ。

【００３２】図３は多段符号キューブの各段の関係を概
念的に示した図である。多段符号キューブでは、基本キ
ューブである第一段のキューブ２０の中から選択された
ゲートノード（５）でより上位の第２位段のハイパキュ
ーブ（５）が構築される。図の中の小さい四角は基本キ
ューブ中のリーフノード２３を示す。リーフノードは第
１段の基本キューブ内にのみ存在する。その他の四角は
第一段におけるゲートノードを表す。全てのゲートノー
ドは第二段のキューブのノードとなる。第二段のキュー
ブにおいて、それらを構成するノードの中から第３段の
キューブのノードとなるゲートノードが選択される。こ
のように、ゲートノードはそのノードが何段目のキュー
ブのノードになっているかにより分類できる。ここでは
第二段のキューブまでのノードとなっているゲートノー
ドを第一段ゲートノード、第三段のキューブまでのノー
ドとなっているゲートノードを第二段ゲートノードと呼
ぶ。一般に第ｎ段のキューブまでのノードとなっている
ゲートノードを第（ｎ−１）段のゲートノードと呼ぶ。
この図においては、第１段ゲートノード２４、第２段ゲ
ートノード２５、第３段ゲートノード２６が示されてい
る。

【００３３】図１の（ｂ）は、本実施例の基本ネットワ
ークとしての３次元ハイパキューブの構造を示す。３次
元ハイパキューブは８つのノードを有するネットワーク
である。本実施例の以下の説明では、３次元ハイパキュ
ーブのことを単にキューブと呼ぶ。本実施例による階層
構造を有するネットワーク、すなわち、階層型ネットワ
ークの構築方法を以下に示す。

【００３４】図１の（ａ）は、本発明による階層型ネッ
トワークの一実施例である。本実施例では、３次元ハイ
パキューブを用いて２層の階層型ネットワークが実現さ
れる。まず、キューブを４つ並べる。この例では３次元
ハイパキューブを基本キューブと呼ぶ。各基本キューブ
には００番から１１番までのキューブ番号を付ける。次
に、各基本キューブから、互いの通信距離が１よりも大
きい２つのノードを選択する（図１の（ａ）で黒丸で示
したノード）。最後に、選択された８つのノードを互い
に接続して、即ち、各基本キューブの対応するノード間
を接続し、かつ、同一基本キューブ内のノード間を接続
して第２層の３次元ハイパキューブを構成する。このよ
うに、本実施例では、各基本ネットワークから選択され
たゲートノードは上層のネットワーク、すなわち、３次
元ハイパキューブを構成するように接続されており、ま
た、同一基本ネットワークから選択されたゲートノー
ド、例えば０００００と００１１１は基本ネットワーク
における通信距離が３に対して、上層のネットワークで
は通信距離１で接続されている。

【００３５】以上の手順により２層の階層型ネットワー
クが構築できる。本発明による階層型ネットワークで
は、基本ネットワークから選択されたゲートノードが上
層のネットワークを構成するように接続される。その結
果同一基本ネットワークから選択されたゲートノード間
の通信距離は基本ネットワークにおける通信距離よりも
短くなる。これにより、本発明による階層型キューブネ
ットワークでは同数のノードを有するハイパキューブネ
ットワークよりも、接続バス数が少なく、かつ、基本ハ
イパキューブ内のそれ以下のノード間通信距離が実現す
ることができる。

【００３６】図２は、３次元ハイパキューブを用いた３
層の階層型ネットワークの構成の一例である。本実施例
では、図４に示す階層型ネットワークを基本ネットワー
クと考え、即ち第２層の３次元ハイパキューブを基本キ
ューブと考え、前述した手順により第３層のネットワー
クを構成したものである。この実施例で明らかなよう
に、本発明による階層型ネットワーク構成方法を繰り返
して適用すると、多階層からなる大規模な階層型ネット
ワークを構築することが可能となる。

【００３７】図６は、他の符号を用いた例を示す。この
例では、７次元ハイパキューブを用いた２層の階層型ネ
ットワークが示される。

【００３８】まず、最下層のネットワークである７次元
ハイパキューブを８つ並べる。この例では７次元ハイパ
キューブを基本キューブと呼ぶ。図６に示す基本キュー
ブでは７次元ハイパキューブの接続線の一部分が示され
ている。各基本キューブには０番から７番までキューブ
番号を付与する。各基本キューブは１２８（＝２＾７）
個のノードを有する。次に各基本キューブの１２８個の
ノードからそれぞれ１６個のゲートノードを選択する。
図６では選択されたゲートノードは示されている。８つ
のキューブから選択されたゲートノードは１２８個（＝
１６×８）あるので、これらのノード間を新たな７次元
ハイパキューブを構成するように接続して第２層のネッ
トワークを構成する。

【００３９】以下、３次元ハイパキューブの例と同様の
処理を繰り返せば、多層ネットワークを構成することが
できる。

【００４０】次に、本発明による階層型ネットワークシ
ステムを構築する際に好適なゲートノードの選択方法に
ついて説明する。

【００４１】まず、階層型ネットワークの基本となる最
下層のネットワークを、ｐ進ｎ次元ネットワークとす
る。以下、このネットワークを基本ネットワークと呼
ぶ。基本ネットワークの各ノードには、ｐ進数ｍ桁のノ
ード番号（アドレス）が付与される。例えば、図２に示
した３次元ハイパキューブ（２進３次元ネットワーク）
では各ノードに２進数で００００〜１１１のノード番号
が与えられる。このようにして与えられたノード番号を
上位ｒ桁と下位ｋ桁とに分割し（ｒ＋ｋ＝ｍ）、誤り訂
正理論に従って上位ｒ桁の番号の各々に１つの下位ｋ桁
を一意に割り当てる。一意に割り当てられた番号をノー
ド番号として有するノードがゲートノードとして選択さ
れる。実施例では、２進数３桁のノード番号を上位１桁
と下位２桁に分割し、上位１桁が０の場合には下位２桁
は００を、上位１桁が１の場合には下位２桁は１１をそ
れぞれ一意に割り当てる。このようにして決められたノ
ード番号０００および１１１を有するノードをゲートノ
ードとして選択する。

【００４２】以上の手順により基本ネットワークの中か
ら均一にゲートノードを選択することが可能となる。更
に、上記方法において、上位桁のデータと、その上位桁
データに対応する下位桁のデータを決定する方法とし
て、上位桁データを情報ビット、下位桁データを誤り検
出／訂正ビットと見なして、情報ビットに対応する誤り
検出／訂正ビットを一意に対応づける方法がある。上記
例では、２進多数決符号（情報ビット１桁、誤り検出／
訂正ビット２桁）を用いてゲートノードを選択した。

【００４３】基本ネットワークとしての基本キューブの
次元数、および、ゲートノードを選択する際に用いる符
号化方式は層間で同一であってもよいし、異なっていて
もよい。以上の例では、説明を容易にするために、層間
における基本キューブの次元数、および、符号化方式は
同一であるものと仮定されている。

【００４４】図７は、７次元ハイパキューブを用いた階
層型ネットワーク、即ち多段（７、４）符号キューブネ
ットワークのノード番号の付け方を説明する図である。
まず、図７の（ａ）に示すように基本キューブ内の物理
的ノード位置に従って、各ノードに２進数７ビットのキ
ューブ内ノード番号が付与される。図では、キューブ内
のｘ軸、ｙ軸、ｚ軸におけるノードの位置をそれぞれ３
ビット、３ビット、１ビットで表し、下位から順に並べ
ることにより基本キューブ内ノード番号が付与される。
本実施例で示すネットワークは、基本キューブを８つ接
続することにより構成されているので、図７の（ｂ）に
示すようにそれぞれの基本キューブに０〜７のキューブ
番号が付与される。このキューブ番号をノード番号の上
位に付与することにより基本ネットワーク内で一意なノ
ード番号が定義される。即ち、図７の（ｅ）に示される
フォーマットで基本ネットワーク内のノードを特定でき
る。なお、以下の説明をより明確にするために、ノード
がゲートノードかリーフノードかにより先頭に“Ｇ”あ
るいは“Ｌ”を付加することにする。

【００４５】ゲートノードを選択する際に、情報ビット
が４ビット、訂正ビットが３ビット、合計７ビットから
なる１誤り訂正符号を用いている。以下、この符号を
（７、４）符号と呼ぶ（符号の長さが７ビット、情報ビ
ットが４ビット）。（７、４）符号の非誤り符号語は以
下に示す１６個である。

【００４６】情報ビット訂正ビット情報ビット訂正ビット０００００００１０００１１１０００１０１１１００１１００００１０１０１１０１００１０００１１１１０１０１１００１０１００１１０１１００００１０１０１１０１１１０１０１００１１００１１１１１０１０００１１１０００１１１１１１１このように、基本キューブ内番号が、非誤り符号と一致
するノードをゲートノードとすることにより、階層型ネ
ットワーク、「多段（７、４）符号キューブ」が構成さ
れる。図６で示されるネットワークは２段（７、４）符
号キューブである。

【００４７】以下では、図６を参照して、２段（７、
４）符号キューブの説明をする。キューブ＃０のゲート
ノードＧ０００は、キューブ＃０内のリーフノードＬ０
０１，Ｌ００２，Ｌ００４，Ｌ０１０，Ｌ０２０，Ｌ０
４０，Ｌ０８０に接続される。一方、第２段の７次元ハ
イパキューブでは、キューブ＃０内のゲートノードＧ０
１３，Ｇ０２５，Ｇ０４６，Ｇ０８７と各々接続され
る。また他のキューブのゲートノードＧ１００，Ｇ２０
０，Ｇ４００と接続される。このように、第２段のネッ
トワークにおいて、ゲートノードは、４つの同一基本キ
ューブ内ゲートノードと、３つの他キューブ内において
対応する位置にあるゲートノードと、各々接続される。
即ち、各ゲートノードは、基本キューブ内で７本の接続
線を、第２段のネットワークにおいて７本の接続線、合
計１４本の接続線を有する。

【００４８】図８は基本キューブ内のゲートノードの接
続の状態を詳細に示した図である。（７、４）符号を用
いてゲートノードを選択すると、同一キューブ内のゲー
トノード間の最小距離は３となる。このため、基本キュ
ーブ内の任意のリーフノードは、距離１離れたところに
必ずゲートノードを有する。例えばゲートノードＧ００
０とＧ０１３は基本キューブ内において距離が３であ
る。これらの２つのゲートノード間には、Ｌ００１，Ｌ
００２，Ｌ００３等のリーフノードが存在するが、距離
１のところにゲートノードが存在する。即ち、Ｌ００１
およびＬ００２はゲートノードＧ０００から、Ｌ００３
はゲートノードＧ０１３から距離１である。したがっ
て、（７、４）符号キューブにおける任意のノードから
ゲートノードへの通信距離は１以内であるといえる。ま
た通信距離が３であるゲートノード間は直接接続され
る。従って、第２段のネットワークを介したゲートノー
ド間の１回の通信は、基本キューブ内の３回の通信に相
当する。

【００４９】多段符号キューブをマルチプロセッサシス
テムのプロセッサ間接続ネットワークとして適用するこ
とにより効率の良いマルチプロセッサシステムを構築す
ることができる。このためには、多段符号キューブの各
ノードは少なくと１つの情報処理装置（プロセッサ）を
含み、ノード間の接続は通信線となる。ここで、基本キ
ューブの次元数をｍ、システム全体のノード数を２のｎ
乗とし、各基本キューブから２のｒ乗個のゲートノード
を選択するものとする。リーフノードは既存のハイパキ
ューブを用いたシステムにおける各ノードと全く同様の
手法を用いることにより構成することができる。すなわ
ち、ｍ次元ハイパキューブ内のノード間接続のための通
信ポートをｍ個持つプロセッサモジュールで構成するこ
とができる。多段符号キューブマルチプロセッサシステ
ムと従来のハイパキューブマルチプロセッサシステムの
違いは、ゲートノードである。

【００５０】図９は、図４に示した２段符号キューブを
適用したマルチプロセッサシステムの構成を詳細に示し
たブロック図である。キューブ０乃至キューブ３は第１
段キューブであり、ここで、Ｌ０２〜Ｌ３６はリーフノ
ードであり、プロセッサモジュールからなる。

【００５１】プロセッサモジュールは図１０Ａに示すよ
うに主記憶７１、プロセッサ７２ネットワークルータと
同一キューブ内接続用ネットワークチャネルからなる。
また、ゲートノードＧ００〜Ｇ３７図１０の（ｂ）に示
すようなマルチプロセッサモジュールからなる。図１０
の（ｂ）の詳細は以下に図１１に示すとおりである。キ
ューブ０乃至キューブ３は第１段キューブであり、ゲー
トノードＧ００〜Ｇ３７からなるキューブが第２段キュ
ーブである。リーフノード間の通信線は細線で示され、
ゲートノード間の通信線は太線で示されている。

【００５２】図１２は、各ノードに置かれたプロセッサ
の番号、キューブ番号、キューブ内番号、次段キューブ
内番号を表として示したものである。次段キューブ内番
号は基本３次元キューブのキューブ内番号が０（００
０）と７（１１１）のものにのみ与えられる。さらに次
段キューブが４つ設けられると、次段キューブ番号が付
される。

【００５３】図１１は多段符号キューブマルチプロセッ
サシステムにおけるゲートノードとして用いられるマル
チプロセッサモジュールの一実施例である。本実施例
は、第１段ゲートノードの構成を示す。ゲートノード４
０は、第１段キューブ側のプロセッサ４３と第２段側の
プロセッサ４７第１段キューブ側ネットワークルータ
（ＮＲ）４６と第２段キューブ側ネットワークルータ５
０およびそれらを結合するノード内のキューブ間接続バ
ス４２およびこれらのプロセッサ間の共有メモリ４１で
構成される。

【００５４】ゲートノード内の第１段キューブ、即ち第
１段の階層に属するプロセッサ４３は情報処理装置４５
およびひプライベートメモリ４４を有し、ゲートノード
内の第２段キューブ、即ち第２段の階層に属するプロセ
ッサ４７は情報処理装置４９およびプライベートメモリ
４８を有する。

【００５５】同一キューブ内のデータ転送はプロセッサ
内のプライベートメモリを介して転送される。一方、異
なる階層のキューブ間の転送は共有メモリ４１を介して
行なわれる。このようにマルチプロセッサモジュールで
ゲートノードを実現することによりより多くの段数のゲ
ートノードへと容易に拡張することが可能となる。例え
ば、本実施例の第１段ゲートノードを第２段ゲートノー
ドに拡張する場合には第３段キューブに属するプロセッ
サをノード内のキューブ間接続バス４２上に接続するだ
けで良い。

【００５６】本実施例におけるゲートノードはバス結合
による主記憶共有密結合マルチプロセッサ構成を取った
が、ゲートノードを共有メモリを持たない、分散メモリ
型マルチプロセッサ構成で実現することももちろん可能
である。また、拡張性を犠牲にするならばゲートノード
をリーフノードとは異なるプロセッサと、ネットワーク
ルータとを用いたシングルプロセッサとして別途設計し
ても一向に構わない。この際にはゲートノードに使用さ
れるプロセッサは、何段のゲートノードかに依存してリ
ーフノードに使用されるプロセッサの整数倍のネットワ
ーク接続チャネルを持つことが要求される。

【００５７】図１３の（ａ）及び（ｂ）にノードユニッ
トの他の実施例を示す。本実施例では、リーフノード
は、図１３の（ａ）に示すように、メモリ７１とデータ
を処理するプロセッサ７２とノード間のデータ通信制御
を行なうネットワークルータ（ＮＲ）７３で構成する。
ゲートノードは、図１３の（ｂ）に示すように、各階層
のネットワーク内におけるメッセージの流れを制御する
複数のネットワークルータ４６、５０を有し、各階層の
ネットワークをそれぞれ制御する。階層間にまたがるデ
ータ転送は、ネットワークルータ間を接続するバス４２
を介して行なう。本実施例では、転送経路上にあるノー
ドにおいてはデータはプロセッサ内に取り込まれること
なくネットワークルータ４６、５０のみを介して転送さ
れる。従って、転送経路上に存在するプロセッサの動作
に影響を与えることがない。また、ネットワークルータ
を増加すれば、ネットワークの拡張に対応可能である。

【００５８】図１４（ｂ）は、ゲートノードの更に他の
実施例を示す。本発明のネットワークでは、ゲートノー
ドに複数の階層のネットワークが集中する。ｍ次元ハイ
パキューブを基本キューブとして用いた場合、第ｉ段ゲ
ートノードから出力されるリンクの総数は、（ｍ×（ｉ
＋１））本となる（ｉ≧０：ｉ＝０はリーフノード）。
これらのリンクを制御するネットワークルータは、自プ
ロセッサ内にデータを取り込むリンクが更にもう１本必
要であることを考慮すると、（ｍ×（ｉ＋１）＋１）本
の入出力線を持つクロスバスイッチで実現できる。図１
４の（ａ）と（ｂ）は、３次元ハイパキューブを基本キ
ューブとして用いた本ネットワークのリーフとゲートの
ノードの構成の一実施例を示す。本実施例では、基本モ
ジュールとして、プロセッサ、第１段のネットワークル
ータ（４×４クロスバスイッチ）、及び、上層のネット
ワークへ接続するための拡張ポートセレクタを有するモ
ジュールを用いる。リーフノードは図１４の（ａ）に示
すように基本モジュールをそのまま用いる。一方、ゲー
トノードは、図１４（ｂ）に示すように、基本モジュー
ルと拡張スイッチモジュール４８により構成する。本実
施例では、第１段ゲートノードのネットワークルータを
構成するために必要な７×７のクロスバスイッチを（４
＋３）×（４＋３）に分割し、４×４のクロスバ１個、
４×３のクロスバ１個、３×４のクロスバ１個、３×３
のクロスバ１個で構成し、各クロスバの出力信号線をセ
レクタにより結合している。基本モジュールには、これ
らのスイッチの内、４×４のクロスバが内蔵されている
ので、残る３個のクロスバと、２個のセレクタを含む拡
張スイッチモジュールが基本モジュールの拡張ポートに
接続される。

【００５９】本実施例では、基本モジュールを全てのノ
ードで共通に利用することができるため、基本モジュー
ルの生産コストを削減することができる。また、ゲート
ノードを構成するのに必要なネットワークルータを分割
して実現することにより、ネットワークルータのピンボ
トルネックを解消することが可能である。一般にｐ×ｐ
のクロスバスイッチは、（ｑ＋ｒ）×（ｓ×ｔ）に分割
することができ（ｑ＋ｒ＝ｓ＋ｔ＝ｐ）、ｑ×ｓ、ｑ×
ｔ、ｒ×ｓ、ｒ×ｔの４個のクロスバおよびそれらを結
合するセレクタで実現することができる。このクロスバ
スイッチの分割方法は、ネットワークルータを構成する
場合以外にも適用できることは明らかである。

【００６０】次に本発明によるデータ転送手順を図１５
を参照して説明する。データ転送時には、ソースノード
とディスティネーションノードが、メッセージにセット
される。データの転送は、元ノードと先ノードが同一ネ
ットワークにあるかどうかを判定する処理８０と、同一
ネットワークにあった場合には該ネットワーク内におけ
る転送経路によりデータを転送する処理８６と、同一ネ
ットワークになかった場合には、元ノードに最も近いゲ
ートノードｐを求める処理８１と、ディスティネーショ
ンノードに最も近いゲートノードｑを求める処理８２
と、ソースノードからゲートノードｐヘ内部ネットワー
クを用いてデータと転送する処理８３と、ゲートノード
ｐからゲートノードｑへ一段上層のネットワークを介し
てデータを転送する処理８４と、ゲートノードｑからデ
ィスティネーションノードへ、それを含む内部ネットワ
ークを用いてデータを転送する処理８５とにより行なわ
れる。ゲートノードｐからゲートノードｑへデータを転
送する処理は本手続きを再帰的に呼び出すことにより行
なう。

【００６１】図１６は多段符号キューブにおけるノード
間でのデータの転送を説明する図である。本図は、３段
（７，４）符号キューブにおけるノード間通信のなか
で、その転送距離が最大となる場合の一例について示し
ている。

【００６２】各ノードの番号は以下のようにして付け
る。図７の（ｂ）を参照して３段（７，４）符号キュー
ブは７次元キューブを基本キューブとして構成され、そ
れらを３段に構築したキューブである。ノード数は８１
９２（１２８×６４）であり、ノード番号は１３ビット
で表現できる。ノード番号の下位７ビットは基本キュー
ブ内におけるアドレスを示している。その中から、上位
４ビットが情報ビットで下位３ビットが訂正ビットであ
るような（７，４）符号を選択するとその上位４ビット
が００００から１１１１であるような１６個の符号語が
選択できる。

【００６３】そこでこれらの上位４ビットのさらに上位
に３ビットを付加することにより第２段の７次元キュー
ブのノードを特定することが出来る。この第２段の７次
元キューブの数は８、またノード数、すなわち第１段ゲ
ートノードの数は１０２４（１６×６４＝１２８×８）
である。第３段のキューブへの拡張も同様の手法を用い
ることにより実現する。第３段の７次元キューブの数は
１、またノード数、すなわち第２段ゲートノードの数は
１２８（１６×８）である。

【００６４】以上の手順に依り、ノード番号の上位７ビ
ットが第３段キューブにおけるアドレス、上位４ビット
から上位１０ビット目までが第２段キューブにおけるア
ドレス、上位７ビット目から最下位ビットまでが第１段
キューブにおけるアドレスとなる。アドレスの割当て
は、例えば次のように行なわれる。

【００６５】第１段のキューブのノードに７ビット（上
位７ビット目から最下位ビットまで）のアドレスが割り
当てられるが、この７ビットの上位４ビットは情報ビッ
トであり、下位３ビットは誤り訂正用ビットである。非
誤り符号の７ビットがゲートノードに割り当てられる。
第２段の各基本キューブのノード（第１段ゲートノー
ド）に上位４ビットから上位１０ビット目までの７ビッ
トがアドレスとして割り当てられるが、第１段の各基本
キューブのノードへのアドレス割付けで既に割り当てら
れている上位７ビット目から上位１０ビットまでの３ビ
ットをそのままにして残りの４ビット（上位４ビットか
ら上位６ビット目まで）を割当て、アドレスとする。第
３段のキューブのノード（第２段ゲートノード）へのア
ドレスの割当ては、上記第２段でのアドレスの割当てと
同様にして行なわれる。

【００６６】このようにして決められた１３ビットがノ
ード番号となる。

【００６７】以下ではこのようにして付けたノード番号
を参照しながら転送の手順について説明する。

【００６８】図１６において、リーフノード５５（ノー
ド番号０００００００００１１１１）からリーフノード
６０（ノード番号１１１１１１１１１００００）データ
を転送する際の経路を示している。リーフノード５５は
第１段キューブ群６１の中の第０番目のキューブに属
し、リーフノード６０は第１段キューブ群６１の第６３
番目のキューブに属する。従ってこれらのノード間の通
信を行なう場合にはより上位のキューブ間のネットワー
クを使う必要がある。

【００６９】そこで、リーフノード５５の最も近いゲー
トノードに対してまずデータを転送しなければならな
い。基本キューブのゲートノードは互いの距離が３であ
るような１誤り訂正符号を用いて選択しているので各リ
ーフノードからは必ず距離１のところにゲートノードが
存在する。各段ごとのハイパキューブにおける任意のノ
ードに対するゲートノードは、そのノードの該キューブ
における二進アドレスを符号とみなし、そのアドレスを
符号理論で確立されている誤り訂正方法を用いて訂正す
ることにより、容易に求めることができる。

【００７０】リーフノード５５の第１段のキューブにお
けるアドレスは（０００１１１１）であるのでこれを誤
り訂正すると、（０００１０１１）となり、ゲートノー
ド５６（ノード番号０００００００００１０１１）に到
達する。同様の方法で、転送先のリーフノード６０に対
応するゲートノードは、ゲートノード５９（ノード番号
１１１１１１１１１０１００）を求めることができる。

【００７１】このようにして求めたゲートノードが同一
キューブ内にあればそれらをその階層のハイパキューブ
を用いて転送することができるが、この例ではゲートノ
ード５６が第２段キューブ群６２の異なるキューブ６５
（キューブ番号０）および、６６（キューブ番号７）に
存在する。従って、これらのノード間の転送を行なう際
にはより上位のキューブを用いる必要があることが分か
る。

【００７２】一方、ゲートノード５６および５９は第１
段のゲートノードであり、第２段のキューブ内では共に
リーフノードである。従って、第３段のキューブに接続
するためにはこれらのノードの第２段のキューブにおけ
るゲートノードすなわち第２段ゲートノードにデータを
転送する必要がある。

【００７３】ゲートノード５６の第２段キューブ６５内
におけるアドレスは（００００００１）であるので、こ
のアドレスの誤り訂正をすると（０００００００）とな
り、データを転送する第２段ゲートノード５７を求める
ことができる。従って、第１段ゲートノード５６から、
第２段ゲートノード５７（ノード番号００００００００
０００００）へデータを転送する。同様に第２段キュー
ブ群におけるデータ転送先ノードであるノード５９に対
応するゲートノードは第２段ゲートノード５８（ノード
番号１１１１１１１１１１１１１）が容易に求められ
る。

【００７４】これらの第２段ゲートノードは第３段のキ
ューブ６３内のノードであり、各々キューブ内アドレス
は０００００００および１１１１１１１であるので、第
３段のキューブ内で７回の転送を行なえば通信すること
ができる。

【００７５】以上のことからリーフノード５５からリー
フノード６０へのデータ転送は、ゲートノード５６、５
７を経て第３段キューブに転送され、その中で７回の転
送を行なうことによりゲートノード５８に転送される。
その後、ゲートノード５９を経てリーフノード６０に転
送される。これらの転送の総ステップ数はノード間の転
送を１とした場合、１１となる。この転送距離が３段
（７，４）符号キューブにおける最大転送距離である。
同一ノード数を持つハイパキューブの場合、最大転送距
離は１３であるので、明らかに多段符号キューブの方が
転送距離が短い。

【００７６】以下では、従来のネットワークと多段符号
キューブのハードウェア量および転送距離に関する評価
結果について述べる。評価対象は、ハイパキューブ、８
進ｎ次元ハイパクロスバ（ＨＸＢ）、２次元トーラス
網、二分木網、および、３次元ハイパキューブを基本キ
ューブとした多段多数決符号キューブ（以下、（３，
１）ＣＣＮと呼ぶ）、ならびに、７次元ハイパキューブ
を基本キューブとした多段（７，４）符号キューブ（以
下、（７，４）ＣＣＮと呼ぶ）とした。多段符号キュー
ブ以外の、上記のネットワークの構造を以下に示す。

【００７７】（１）ハイパキューブ図１７（ａ）に５次元ハイパキューブの構成を示す。ｎ
次元ハイパキューブの各ノードはｎ本のリンクを持ち、
ハミング距離が１となるｎ個のノードと接続される。ハ
ミング距離とは、ノード番号を２進数で表現したときに
異なるビット数である。例えば、ノード番号が２０番
（＝０００１０１００）と５４番（＝００１１０１１
０）のハミング距離は２となる。

【００７８】（２）ハイパクロスバ図１７（ｂ）に８×８の２次元ハイパクロスバの構成を
示す。各ノードは２本のリンクを有し、横方向の８×８
クロスバと縦方向の８×８クロスバスイッチにそれぞれ
接続されている。一般に、ｐ₁×ｐ₂×…×ｐｄ構成のｄ
次元ハイパクロスバは、各次元ｉ方向にｐｉ個のノード
を完全接合網（クロスバ）で結合したネットークであ
り、各ノードはｄ本のリンクを持つ。

【００７９】（３）トーラス網図１７（ｃ）に８×８構成の２次元トーラス網の構成を
示す。このネットワークは、横方向に８つのノードを、
縦方向に８つのノードをそれぞれリング状に結合したネ
ットワークである。ｐ₁×ｐ₂×…×ｐｄ構成のｄ次元ト
ーラス網は、各次元ｉ方向にｐｉ個のノードをリング状
に結合したネットワークである。各ノードは２ｄ本のリ
ンクで接続される。

【００８０】（４）二分木網図１７（ｄ）に二分木網の構成を示す。２分木網は２の
ｎ乗個のノードと２のｎ乗−１個のネットワークルータ
を持つ。各ノードは１本、ネットワークルータは３本の
リンクをそれぞれ持つ。

【００８１】ここではネットワークのノード当たり平均
リンク数、モジュール間平均リンク数に関して評価した
結果を述べる。

【００８２】（１）１ノード当たりの平均リンク数各ノードを接続するリンクの数は実装時の各ＬＳＩのピ
ン数及び配線量を表す。ネットワークを構成するＬＳＩ
ではピン数ネックになることが多い。従って、ネットワ
ークのハードウェアコストを、プロセッサ１台当たりの
平均リンク数で比較する。１本のリンクは２つのノード
で共有される。したがって、平均リンク数は、ネットワ
ークの総リンク数の２倍をノード数で割った値となる。
図１８（ａ）は種々のネットワークの平均リンク数を示
す表であり、Ｆｉｇ．１８Ｂ図１８（ｂ）は、横軸がネ
ットワークのノード数の対数を示し、縦軸がプロセッサ
当たりの平均リンク数を示すグラフである。この結果よ
り、トーラス網、二分木網、（３，１）ＣＣＮはノード
数にかかわらず概ね４本／ノード、（７，４）ＣＣＮは
約８本／ノードのリンクを有する。これに対して、ハイ
パキューブとハイパクロスバはノード数の対数に比例し
てリンク数が増加する。

【００８３】以上の結果から、ハードウェアの実装を考
慮すると、多数台のノードを接続する場合には、本発明
による階層型ネットワークや、２分木網や、トーラス網
が望ましいことが分かる。

【００８４】（２）モジュール間リンク数複数のプロセッサを１チップあるいは１モジュールに集
積した並列計算機が考える場合、１つのチップあるいは
モジュールから出力できるピン数が問題となる。従っ
て、大規模並列計算機では、モジュール間のリンク数を
削減することが必須となる。例えば１つのモジュールに
８つのプロセッサを集積した場合の各モジュール間のリ
ンク数をそれぞれのネットワークについて評価した。図
１９（ａ）はその計算結果を示す表であり、図１９
（ｂ）は横軸がネットワークのノード数の対数を示し、
縦軸がモジュール間のリンク数を示すグラフである。こ
の結果より、ハイパキューブとハイパクロスバのモジュ
ール間リンク数が多く、本発明による階層型ネットワー
クや、２分木網、トーラス網は比較的少ないリンク数で
実現できることが分かる。

【００８５】（３）平均転送距離全ノード対全ノードのランダム通信を行なう場合にはメ
ッセージの衝突が頻繁に発生する。この場合、転送時間
はメッセージの衝突回数に大きく影響される。メッセー
ジの衝突回数は転送距離が大きくなるほど多くなる。そ
こで、各種ネットワークの平均転送距離を比較すること
によりネットワークのデータ転送性能を評価することが
できる。すなわち、平均転送距離が小さいほどネットワ
ークの転送性能が良いといえる。

【００８６】図２０は横軸がネットワークのノード数の
対数、縦軸がネットワークの平均転送距離を示す。図よ
りハイパキューブの転送距離が最小であることが分か
る。ハイパキューブの転送距離を１とした場合、６４Ｋ
ノード構成では、（７，４）ＣＣＮはハイパキューブの
１．１倍、ハイパクロスバは１．２倍、（３，１）ＣＣ
Ｎは１．６倍、二分木網は３．８倍、トーラス網は１６
倍の平均転送距離となる。この結果から、ハイパキュー
ブ、（７，４）ＣＣＮ、ハイパクロスバ、（３，１）Ｃ
ＣＮは、ネットワークの転送性能が高いことが分かる。

【００８７】次に、ハードウェアコストを一定にして種
々のネットワークを構成した場合の性能、即ち、ネット
ワークのコストパフォーマンスの比較を行なった。ネッ
トワークのハードウェアコストがネットワークのリンク
のコストに依存すると仮定すると、ハードウェアコスト
を一定にした場合には、ネットワークの総リンク数と各
リンクの転送速度（スループット）は反比例の関係とな
る。

【００８８】したがって、各リンクの距離をネットワー
クコストを一定にして正規化すると、正規化された各リ
ンクの転送速度Ｌｔは、

【００８９】

【数１】Ｌｔ＝１／（平均リンク数） …（１）となる。したがって、正規化された平均転送距離ＮＤ
は、

【００９０】

【数２】ＮＤ＝（平均転送距離）／Ｌｔ＝（平均転送距離）×（平均リンク数） …（２）となる。

【００９１】図２１は横軸がプロセッサ台数の対数、縦
軸が正規化された平均距離を示す。本結果から、多段符
号キューブは従来のネットワークと比較して正規化され
た平均転送距離が最も小さいことが分かる。例えば、６
４Ｋノード構成時の（３，１）ＣＣＮの正規化された平
均転送距離を１とすると、（７，４）ＣＣＮが３．３、
ハイパクロスバが５．１、二分木網が５．５、ハイパキ
ューブが５．９、トーラス網が２３．６となり、本発明
による階層型ネットワークのコストパフォーマンスが他
のネットワークと比較して極めて高いことが分かる。

【００９２】以上の評価より、本発明による階層型ネッ
トワークを用いると、ハードウェアコストが低く、か
つ、転送性能が高いネットワークが実現可能となる。

【００９３】

【発明の効果】本発明は以上の説明から明らかなよう
に、全く新しい階層型ネットワークトポロジを提供し、
かつそのトポロジは内部にハイパキューブを有し、さら
に、プロセッサ台数が数万から数百万、あるいはそれ以
上の、大規模マルチプロセッサシステムにおいて、ノー
ド間接続線数、拡張性、モジュール間接続線数、データ
転送距離のいずれにおいても、ハイパキューブよりも優
れた性質を有する。

【図面の簡単な説明】

【図１】本発明の多段符号キューブの一実施例を示す図
である。

【図２】本発明の多段符号キューブの他の一実施例を示
す図である。

【図３】多段符号キューブの各段の関係を概念的に示し
た図である。

【図４】ハイパキューブを説明する図である。

【図５】ハイパキューブを説明する図である。

【図６】本発明の実施例である７次元ハイパキューブを
２段に重ねた階層型ネットワークを示す図である。

【図７】多段（７，４）符号キューブのノード番号の付
け方を説明する図である。

【図８】多段（７，４）符号キューブの基本キューブ内
のゲートノードの接続の状態を示した図である。

【図９】図３に示した多段符号キューブを適用したマル
チプロセッサシステムである多段符号キューブマルチプ
ロセッサシステムの構成を示したブロック図である。

【図１０】多段符号キューブを用いたマルチプロセッサ
システムにおけるリーフノード及びゲートノードの一実
施例の図である。

【図１１】多段符号キューブを用いたマルチプロセッサ
システムにおけるゲートノードの一実施例の構成図であ
る。

【図１２】図９の各ノードに置かれたプロセッサユニッ
トのプロセッサ番号、キューブ番号、キューブ内番号、
次段キューブ内番号を表として示した図である。

【図１３】多段符号キューブを用いたマルチプロセッサ
システムにおけるハーフノード及びゲートノードの他の
一実施例の構成図である。

【図１４】多段符号キューブを用いたマルチプロセッサ
システムにおけるハーフノード及びゲートノードの他の
一実施例の構成図である。

【図１５】多段符号キューブのネットワークにおけるデ
ータ転送手順を説明する図である。

【図１６】多段符号キューブのネットワークにおけるノ
ード間のデータ転送を説明する図である。

【図１７】従来のネットワークの構成を示す図である。

【図１８】本発明による多段符号キューブと、従来のネ
ットワークとの、１ノードあたりのリンク数の比較を示
す表及びグラフである。

【図１９】本発明による多段符号キューブと、従来のネ
ットワークとの、モジュール間接続リンク数の比較を示
す表及びグラフである。

【図２０】本発明による多段符号キューブと、従来のネ
ットワークとの、平均転送距離の比較を示すグラフであ
る。

【図２１】本発明による多段符号キューブと、従来のネ
ットワークとの、正規化された平均転送距離の比較を示
すグラフである。

Claims

【特許請求の範囲】

【請求項１】複数のノードを有する複数の下層のネット
ワークとこれらを階層的に接続して構成する上層のネッ
トワークからなる階層型ネットワークであり、前記複数のノードを有する複数の下層のネットワークか
らそれぞれ複数のゲートノードを選択してより上層のネ
ットワークのノードとし、該ゲートノードの内、同一の下層ネットワークに属する
前記選択されたゲートノード間は互いのゲートノード間
の通信距離が下層のネットワークにおける通信距離より
短くなるように相互に接続し、同一の下層ネットワークに属さない前記選択されたゲー
トノード間は、互いの通信が行なえるように相互に接続
することを特徴とする階層型ネットワーク。
【請求項２】請求項１記載の階層型ネットワークにおい
て、第ｉ層を構成するネットワークをｐ_i進ｎ_i次元ネットワ
ークで構成することを特徴とする階層型ネットワーク。
【請求項３】複数のノードを有する複数の下層のｐ進ｎ
次元ネットワークとこれらを階層的に接続して構成する
上層のｐ進ｍ次元ネットワークからなる階層型ネットワ
ークであり、前記複数のノードを有する複数の下層のｐ進ｎ次元ネッ
トワークのそれぞれのノードに、該下層ネットワーク内
で一意に決定できるｐ進ｎ桁のノード番号を与え、該ノ
ード番号を符号とみなしたとき符号語に相当するノード
番号に対応する複数のゲートノードを選択し、複数の下層ネットワークから選択された複数のゲートノ
ードをより上層のｐ進ｍ次元ネットワークのノードとし
て相互に接続することを特徴とする階層型ネットワー
ク。
【請求項４】請求項１または請求項３記載の階層型ネッ
トワークにおいて、第ｉ層を構成するネットワークをｎ_i次元ハイパキュー
ブで構成することを特徴とする階層型ネットワーク。
【請求項５】請求項３または請求項４記載の階層型ネッ
トワークにおいて上層のネットワークに属するゲートノ
ードを選択する際、各々の下層のネットワークに属するノードの中から、ｔ
重誤り訂正符号の符号語に当たるノード番号に対応する
複数のゲートノードを選択して、複数の下層ネットワークから選択された複数のゲートノ
ードをより上層のネットワークのノードとして相互に接
続することを特徴とする階層型ネットワーク。
【請求項６】請求項１乃至請求項５のいずれかに記載の
階層型ネットワークにおいて、ネットワークの各ノードにプロセッサモジュールを配置
し、ネットワークの接続線を通信線として構成したこと
を特徴とする階層型ネットワークマルチプロセッサシス
テム。
【請求項７】請求項６記載の階層型ネットワークマルチ
プロセッサシステムにおいて、前記下層のネットワークからなるマルチプロセッサシス
テムを、１チップあるいは１モジュールで構成したこと
を特徴とする階層型ネットワークマルチプロセッサシス
テム。
【請求項８】請求項６記載の階層型ネットワークマルチ
プロセッサシステムにおいて、ゲートノード以外のノードを構成するプロセッサモジュ
ールは、プライベートメモリと、前記プライベートメモ
リに接続されたプロセッサと、前記プロセッサと前記下
層ネットワークに接続されたネットワークルータとを含
み、各ゲートノードを構成するプロセッサモジュールは、バ
スと、前記バスに接続された共有メモリと、前記バスに
接続された二つ以上のプロセッサと、前記複数のプロセ
ッサの各々と各層のネットワークに接続された複数のネ
ットワークルータとを含むことを特徴とする階層型ネッ
トワークマルチプロセッサシステム。
【請求項９】請求項６記載の階層型ネットワークマルチ
プロセッサシステムにおいて、ゲートノード以外のノードを構成するプロセッサモジュ
ールは、第一のプライベートメモリと、前記第一のプラ
イベートメモリに接続されたプロセッサと、前記プロセ
ッサと前記下層ネットワークに接続されたネットワーク
ルータとを含み、各ゲートノードを構成するプロセッサモジュールは、第
二のプライベートメモリと、前記第二のプライベートメ
モリに接続されたプロセッサと、前記プロセッサに接続
されたバスと、前記バスと各層のネットワークに接続さ
れた少なくとも二つ以上のネットワークルータとを含む
ことを特徴とする階層型ネットワークマルチプロセッサ
システム。
【請求項１０】請求項６記載の階層型ネットワークマル
チプロセッサシステムにおいて、ゲートノード以外のノードを構成するプロセッサモジュ
ールは、プロセッサと、最下層ネットワークに接続される入力ポートと出力ポー
トと、拡張ポートと、前記プロセッサ、前記入力ポート、前記出力ポート、前
記拡張ポートに接続され前記入力ポートからの入力と前
記プロセッサからの出力を前記プロセッサへの入力と前
記出力ポートへ選択的に接続するためのネットワークル
ータと、前記ネットワークルータからの出力と前記拡張ポートか
らの入力とのうちの一つをプロセッサに供給するための
セレクタとを含み、各ゲートノードを構成するプロセッサモジュールは、前記ゲートノート以外のノードを構成するプロセッサモ
ジュールと、前記拡張ポート、前記上層ネットワーク、前記下層ネッ
トワークに接続され、前記上層ネットワークからの入力、前記下層ネットワー
クからの入力、前記拡張ポートからのプロセッサモジュ
ールの出力を、前記プロセッサモジュールの拡張ポート
への入力、前記上層ネットワークへの出力、前記下層ネ
ットワークへの出力へ選択的に接続するための拡張ネッ
トワークルータと、前記プロセッサモジュールからの入力と、前記拡張ネッ
トワークルータからの出力を前記上層ネットワークの出
力と前記下層ネットワークの出力へ選択的に供給するた
めの選択手段を含むことを特徴とする階層型ネットワー
クマルチプロセッサシステム。
【請求項１１】請求項６記載の階層型ネットワークマル
チプロセッサシステムにおいて、ノードに配置されたプロセッサからデータを転送すると
き、同一下層ネットワークに属するノードに対しては下
層ネットワーク内の最短経路によりデータを転送し、他
のネットワークに属するノードに対してはより上層のネ
ットワークに接続されるノードにデータを転送し、より
上位のネットワークを介してデータを転送するよう構成
したことを特徴とする階層型ネットワークマルチプロセ
ッサシステム。
【請求項１２】請求項１１記載の階層型ネットワークマ
ルチプロセッサシステムにおいて、下層のネットワークと上層のネットワークを接続するノ
ード以外のノードａから、下層のネットワークと上層の
ネットワークを接続するノードｂへ至る経路は、ノード
ａに与えられた下層ネットワークにおけるノード番号を
符号と見なしてこれをｔ重誤り訂正符号における誤り訂
正手段により訂正して、該符号の符号語を求め、得られ
た符号語が割り当てられたノードｂに至る経路とする手
段を備えたことを特徴とする階層型ネットワークマルチ
プロセッサシステム。
【請求項１３】複数のプロセッサモジュールをネットワ
ークで結合したマルチプロセッサシステムにおいて、前記プロセッサモジュールは、プロセッサと、ネットワークに接続される入力ポートと出力ポートと、拡張ポートと、前記プロセッサ、前記入力ポート、前記出力ポート、前
記拡張ポートに接続され前記入力ポートからの入力と前
記プロセッサからの出力を前記プロセッサへの入力と前
記出力ポートへ選択的に接続するためのネットワークル
ータと、前記ネットワークルータからの出力と前記拡張ポートか
らの入力とのうちの一つをプロセッサに供給するための
セレクタとを含み、前記プロセッサモジュールは、少なくとも一つのプロセ
ッサと、複数のネットワーク入出力ポートと、ネットワ
ークルータと、さらに、ネットワークの入出力ポートを
拡張するための拡張ポート並びにセレクタを備えている
ことを特徴とするマルチプロセッサシステム。