JPH0830571A

JPH0830571A - データ転送ネットワーク

Info

Publication number: JPH0830571A
Application number: JP7186831A
Authority: JP
Inventors: Takehisa Hayashi; 林　　剛久; Koichiro Omoda; 耕一郎面田; Teruo Tanaka; 輝雄田中; Naoki Hamanaka; 直樹濱中; Shigeo Nagashima; 重夫長島
Original assignee: Hitachi Ltd
Current assignee: Hitachi Ltd
Priority date: 1995-07-24
Filing date: 1995-07-24
Publication date: 1996-02-02

Abstract

(57)【要約】【目的】適用分野が広く性能のよいデータ転送ネットワ
ークを提供する。【構成】データ転送ネットワークは、グループ分けされ
た複数のプロセッサをグループ内で相互に接続する部分
ネットワークと、プロセッサの各々に１対１対応する複
数の交換スイッチを有し、交換スイッチは、ある部分ネ
ットワークから受信したパケットの送り先アドレスが、
その交換スイッチが接続されたプロセッサと一致する場
合、これをプロセッサに転送し、他のパケットの場合
は、それを受信した部分ネットワークと異なる部分ネッ
トワークに転送する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明はパケット形式のデータを
転送する、データ転送ネットワークに関する。

【０００２】

【従来の技術】近年ＬＳＩ技術の進歩により、高速大容
量のプロセッサを多数接続し、並列処理を行なうこと
で、高性能の並列計算機システムを実現することが可能
になりつつある。この様なシステムにおいては、プロセ
ッサ間、プロセッサ・メモリ間等で、大量のデータを授
受することが必要であり、例えば図３に示す様なプロセ
ッサ間を結合するデータ転送ネットワークが必要とな
る。データ転送ネットワークの従来の構成方法について
は、例えば、黒川他、情報処理Vol.２７，(１９８６
年）、Ｎo.９，特集「並列処理技術」３，１，結合方
式、ｐｐ．１００５〜１０２１に詳しく説明されてい
る。

【０００３】データ転送ネットワークとしては、クロス
バスイッチを用いるものや、多段スイッチを用いるもの
が知られているが、この場合、転送すべきデータに転送
先のアドレスを付加したパケットが、データ転送ネット
ワークに送り出され、そのパケッに対して順次バスがネ
ットワーク中に生成されていく。

【０００４】

【発明が解決しようとする課題】データ転送ネットワー
クをクロスバスイッチで構成した場合、ハードウェアが
膨大なものとなり、実現が困難である。従って、多段ス
イッチ方式を用いることが現実的である。上記パケット
において、データの長さは通常数十ビット以上であり、
また、転送先アドレスも、数千台以上のプロセッサを用
いる場合、十数ビット以上必要である。パケットの高速
転送のためにはそのパケットの全ビットを並列に転送す
ることが望ましいことは言うまでもないが、パケットの
全ビットを並列に送れるようにすると、信号線数、スイ
ッチ数が膨大になるため、データ転送路のビット幅ｄ
は、比較的小さなもの（高々１０ビット程度以下）とな
らざるを得ない。従って、実用的観点からは、図２Ｂに
示すように各パケットをそれぞれ複数のビット数ｄから
成る複数のサブパケットに分け、各サブパケット内に全
ピットは並列に転送し、異なるサブパケットは順次転送
するという方法が必要である。この場合、データのみな
らず、転送先アドレスも少なくとも２つ以上の部分アド
レスに分割することが必要となる。

【０００５】データ転送ネットワークを構成する多段の
スイッチの各スイッチは、入力されたパケットの行き先
をそのパケット内の転送先アドレスから判断し、適当な
スイッチングを行なって、そのパケットを適当な出力端
に出力する。前述の様にデータ及び転送先アドレスを分
割した場合でも、すべての部分アドレスの到着を待つこ
とによりこのスイッチングを各スイッチに行なわせるこ
とができる。一旦スイッチングが行なわれると、転送先
アドレスの後に順序送られてくるデータ用のサブパケッ
トはパイプライン的に次段のスイッチに送ることができ
る。しかし、各スイッチのスイッチングが部分アドレス
すべての到着を待って行なわれたのでは、転送先アドレ
スの全ピットを並列に転送する場合に比べ、スイッチン
グ開始時間が大幅に遅れるという問題がある。

【０００６】本発明の目的は、転送先アドレスを複数の
部分アドレスに分割した場合でも各スイッチのスイッチ
ング開始時間を余り遅らせなくてすむデータ転送ネット
ワークを提供することにある。

【０００７】

【課題を解決するための手段】このため本発明では、あ
るスイッチがパケットを送出すべき次段のスイッチを確
定するために必要な部分アドレスが、そのスイッチに供
給される部分アドレスをそれぞれ含む複数のサブパケッ
トの内の最初にものに含まれている場合には、そのスイ
ッチは最初のパケットが到着したときにスイッチングを
開始するようにそのスイッチを構成した。さらに望まし
い様として、次段のスイッチがスイッチングするのに
必要な部分アドレスが先頭のサブパケットに含まれてい
ない場合、前段のスイッチは、その部分アドレスが先頭
のサブパケットに含まれるように部分アドレスをサブパ
ケット間で入れ換れるようにした。

【０００８】

【作用】本発明では、上記のような構成をとることによ
り、データ転送ネットワークを構成するスイッチがスイ
ッチングを開始するまでに必要な待ち時間を削減し、高
速なデータ転送ネットワークを実現できる。

【０００９】

【実施例】本発明の実施例の説明の前に、分割アドレス
を用いるが、本発明によるスイッチングの早期化を図ら
ないデータ転送ネットワークの例として本発明者が考え
たものを図５に即して説明する。

【００１０】図５は多段スイッチ構成のデータ転送ネッ
トワーク（以下、単にネットワークとも言う）を示し、
１６入力／１６出力を有すると仮定する。

【００１１】図５において、Ｓ００−Ｓ３７はネットワ
ークを構成する２入力／２出力のスイッチであり、それ
ぞれのスイッチの上部に付記した〔〕の中の数字はそ
の番号を示す。

【００１２】０′〜１５′はネットワークの入力ポー
ト、０″〜１５″はネットワークの出力ポートである。
出力ポート０″〜１５″はそのアドレスを２進数で各々
（００００）〜（１１１１）と表現する。図６は上記多
段スイッチにおいて、転送先アドレスを分割して転送す
るために、図５のネットワークに用いるスイッチの構成
の一例であり、図６において、１１，１２はスイッチの
入力ポート、０１，０２は出力ポート、Ｅ１は出力ポー
ト選択回路、Ｑ₁，Ｑ₂は出力キュー，Ｑ₃，Ｑ₄は出力キ
ュー，Ｌ１，Ｌ２，Ｌ３，Ｌ４は上記サブパケット中に
含まれる部分アドレスを記憶するためのレジスタ、Ｓ
１，Ｓ２はセレクタであり、ＭＳ１はスイッチの動作に
必要な情報・手順を格納したメモリ、Ｐ１はスイッチの
動作を制御するスイッチコントローラである。

【００１３】ここで、簡単のため、ネットワークに与え
られるパケットは、転送先アドレスが４ピット、データ
が４ピットとし、データ転送路のピット幅が２ビットで
あると仮定し、図４に示すように転送先アドレスは部分
アドレスＡ₁，Ａ₂に分割され、データＤ₁，Ｄ₂に分割さ
れているとする。また、このパケットが、図５に太線で
示す様に、入力ポート１′から、出力ポート１１″に転
送される場合を考える。１１″のアドレスは（１０１
１）であるので、Ａ₁，Ａ₂はそれぞれ１０，１１なるビ
ット列を表わす。このときの図５、図６のデータ転送ネ
ットワークの動作を図７を用いて説明する。図７に示す
様に、図５の

〔００〕座標のスイッチＳ００の入力ポー
ト１２に部分アドレスＡ₁，Ａ₂，部分データＤ₁，Ｄ₂が
順次入力されるとする。このとき、スイッチＳ００で
は、第１、第２の部分アドレスＡ₁，Ａ₂をそれぞれレジ
スタＬ３，Ｌ４に記憶し、また、部分アドレスＡ₁，Ａ₂
部分データＤ₁，Ｄ₂は順次入力キューに格納する。レジ
スタＬ３，Ｌ４の出力Ｃ３，Ｃ４（今の場合は部分アド
レスＡ₁，Ａ₂に等しい）はそれぞれスイッチ・コントロ
ーラＰ１に与えられており、スイッチコントローラＰ１
は、部分アドレスＡ₁，Ａ₂がそれぞれレジスタＬ１，Ｌ
２にセットされたときにスイッチ内メモリＭＳ１の内容
とレジスタＬ３，Ｌ４の出力Ｃ３，Ｃ４に応答して出力
ポート選択回路Ｅ１内のセレクタＳ１，Ｓ２の制御情報
Ｍ１，Ｍ２を作成してこれらに与える。さらに具体的に
は、この場合、スイッチコントローラＰ１は、図７で＊
で示す様な、第１サブパケットの第１ビットが判定ビッ
トであるという判定ビット位置情報Ｊ１がメモリＭＳ１
から与えられ出力Ｃ３（＝Ａ１），Ｃ４（＝Ａ２）から
なる４ビットのアドレスの内上記判定ビットを取り出
す。今の場合、この値が１であるので、これに基づい
て、Ｅ１中のセレクタＳ２に対して、入力ポート１２か
ら出力ポート０２へ至るパスを生成する様な制御情報Ｍ
２を与える。こうして上記サブパケットは順次出力キュ
ーＱ３を介して、出力ポート０２から次段のスイッチＳ
１４ヘ送信される。

【００１４】図５で、スイッチＳ００内で出力ポート０
２が選択されるため、上記のパケットはスイッチＳ１４
の入力では、図７に示す様に、判定ビット位置が第１サ
ブパケットの第２ビットであるという判定ピット位置情
報Ｊ１が、そのスイッチ内のメモリＭＳ１から与えれ、
判定ピット（この場合０）がスイッチＳ１４の入力ポー
ト１１から出力ポート０１へ至るパスが生成されパケッ
トはスイッチＳ２４へ送られる。以下、スイッチＳ２４
では判定ビット（この場合）であり、スイッチＳ３５で
は第２サブパケットの第２ピットであり、スイッチＳ３
５では第２サブパケットの第２ビット（この場合１）で
あって、同様の処理によって、パケットはネットワーク
の出力ポート１１″に転送される。

【００１５】上記動作のタイミング図を図８に示す。図
８において、上記の各サブパケツトは時間Ｔごとに順次
入力ポートに与えられるとする。また、各スイッチ内の
スイッチコントローラＰ１、セレクタＳ１，Ｓ２等は充
分高速に動作するとする。図６からわかる様に、図５、
図６のデータ転送ネットワークでは、各スイッチでは２
つの分割アドレスの到着をまってスイッチングを開始し
ている。このためサブパケット４個の転送時間４Ｔに加
え、各スイッチでの、二つの分割アドレスの到着待ちの
時間２Ｔ×４＝８Ｔが加わるため、ネットワークの転送
所要時間は１２Ｔ必要である。

【００１６】次に、本発明の実施例を説明する。

【００１７】図９は本発明による多段スイッチからなる
データ転送ネットワークであり、その構成において、図
５と異なるのはスイッチＳ００′〜Ｓ３７′が転送先ア
ドレスを含む全てのサブ・パケットの到着を待つことな
く、第１のサブ・パケット到着後、スイッチングを行
い、パケットを送出すべき次段のスイッチに接続された
出力ポートを確定してサブパケットの送出を開始する点
および第２段目のスイッチＳ１０′〜Ｓ１７′が、分割
された転送先アドレスを含む複数のサブパケットに対
し、上記分割アドレスを第１のサブパケットと第２のサ
ブパケット間で入れ替えるように構成されている点であ
る。図５，図６で説明した、Network の例では、第１段
目のスイッチＳ００〜Ｓ０７、及び第２段目のスイッチ
Ｓ１０〜Ｓ１７では、各スイッチでパケットを送出すべ
き次段のスイッチを確定するために必要な部分アドレス
はそれぞれに入力されるパケットの第１サブパケット内
にある第１部分アドレスＡ１であるが、第３段目、第４
段目のスイッチＳ２０〜Ｓ３７における、それは、第２
サブパケット内の第２部分アドレスＡ２である。しか
し、図９の様に、第２段目のスイッチＳ１０′〜Ｓ１
７′に入力されたサブパケット列が出力される際に、第
１サブパケットに第２部分アドレスＡ２、第２サブパケ
ットに第１部分アドレスＡ₁が含まれる様に部分アドレ
スＡ₁，Ａ₂を第２段目のスイッチＳ１０′〜Ｓ１７′で
入れ替えることで、次段のスイッチが、スイッチングに
要する部分アドレスが先頭サブパケットに含まれる。

【００１８】図１は図９の第２段目のスイッチＳ１０′
〜Ｓ１７′の構成の一例であり、その構成において図６
と異なるのは、入力ポート１１または１２に対しレジス
タＬ１，Ｌ２またはＬ３，Ｌ４に記憶された部分アドレ
スの内、先に送出すべきものを先に選択するように、レ
ジスタＬ１，Ｌ２の出力Ｃ１，Ｃ２を選択するセレクタ
Ｓ３、及びレジスタＬ３，Ｌ４の出力Ｃ３，Ｃ４を選択
するセレクタＳ５，セレクタＳ３またはＳ５から出力さ
れた部分アドレス列を入力キューＱ１またはＱ２格納さ
れた部分データに先立って選択して出力ポート選択回路
Ｅ１に与えるためのセレクタＳ４、またはＳ６を有する
点、及び、スイッチングコントローラＰ２は入力ポート
１１または１２へのパケットの先頭のサブパケットの到
着と同期して、このパケットと並列に与えられるパケッ
トスタート信号ＰＳＴＲ１またはＰＳＴＲ２に応答して
動作を開始し、パケットの末尾が入力ポート１１または
１２へ到着するのに同期して与えられるパケット終了信
号ＰＥＮＤ１またはＰＥＮＤ２に応答して動作を終了す
る点、及びメモリＭＳ２から与えられる判定ビット位置
情報Ｊ２はつねに先頭のサブパケット内の部分アドレス
のいずれかのビットを指す点、である。

【００１９】また、第１段のスイッチＳ００′〜Ｓ０
７′及び第３段、第４段のスイッチＳ２０′〜Ｓ３７′
は図２に示すように、図１から、サブパットを記憶する
レジスタＬ１，Ｌ３，及びセレクタＳ３〜Ｓ６を省略し
たものである。即ち、これらのスイッチは、サブパケッ
トの入れ替えを行なわない点で主に第２段のスイッチＳ
１０′〜Ｓ１７′と異なるが、パケットスタート信号Ｐ
ＳＴＲ１，ＰＳＴＲ２，パケット終了信号ＰＥＮＤ２に
応答する点では同じである。図５の場合と同様に、図９
の動作説明のため、データ転送路のビット幅が２ビット
であり、転送先アドレスは２つの部分アドレスＡ₁，Ａ₂
からなりデータは２つの部分データＤ₁，Ｄ₂からなりそ
れぞれは各々２ビットの長さのサブパケットに含まれ
る。図７の太線で示す様に入力ポート１′から出力ポー
ト１１′に転送される場合を考える。このときの図９の
データ転送ネットワークの動作を図８を参照して説明す
る。図１０に示す様に、図９の

〔００〕の座標のスイッ
チＳ００′の入力ポート１２に、図５〜図７の場合と同
様の部分アドレスＡ₁，Ａ₂と部分データＤ₁，Ｄ₂が順次
入力されるとする。図７におけるスイッチＳ００′，Ｓ
２４′，Ｓ５３の動作は、図９におけるスイッチＳ０
０，Ｓ２４，Ｓ３５の動作とほぼ同様であるが、異なる
のは各スイッチは最初の部分アドレスの到着時に動作を
開始する点習ある。すなわち図９の場合、各スイッチか
らのパケットの送出先スイッチを決定するための判定ビ
ット位置は図１０に＊で示すようにいずれも第１サブパ
ケットの部分アドレス内にあるため、第２サブパケット
の到着を待つことなく、送出先が決まり、送出が開始さ
れる点が異なっている。

【００２０】次に図９におけるスイッチＳ１４′の動作
の一例を図１１のタイムチャートを参照して説明する。
スイッチＳ１４′にはスイッチＳ００′から、部分アド
レスＡ₁，Ａ₂，部分データＤ₁，Ｄ₂、が入力ポート１１
に順次送られる。このとき先頭の部分アドレスの到着と
同期して、かつパケットの転送と並行してパケットスタ
ート信号ＰＳＲＴ１がスイッチコントローラＰ２に与え
られる。スイッチコントローラＰ２はスイッチＳ００′
が以下の動作とするように制御動作を開始する。スイッ
チＳ１４′では、第１のタイミングで第１部分アドレス
Ａ₁をレジスタＬ２に記憶し、続く第２のタイミングで
この第１部分アドレスＡＡ₁をレジスタＬ１に移動し、
かつ第２部分アドレスＡ₂をレジスタＬ２に記憶する。
また、第３、第４のタイミングでそれぞれ部分データＤ
₁，Ｄ₂を順次入力キューＱ₁に格納する。ここで、レジ
スタＬ２の内容Ｃ２はスイッチコントローラＰ２に与え
られている。今の場合、第１部分アドレスＡ₁がレジス
タＬ２に到着した時点でこの部分アドレスＡ₁がＣ１と
してスイッチコントローラＰ２に与えられる。スイッチ
コントローラＰ２は出力Ｃ２の内、メモリＭＳ２から与
えられる判定ビット位置情報Ｊ２で示される位置のビッ
トに応答して、出力ポート選択回路Ｅ１内のセレクタＳ
１，Ｓ２の制御情報Ｍ１，Ｍ２を作成して、これらに与
え、入力ポート１１から出力ポート０１へ至るバスを生
成する。さらにスイッチコントローラＰ２は、レジスタ
Ｌ１に記憶された第１の部分アドレスＡ₁、レジスタＬ
２に記憶された第２の部分アドレスＡ₁の内、上記第３
のタイミングで、Ａ₂を、また、上記第４のタイミング
でＡ₂を選択する様な制御信号Ｍ３をセレクタＳ３に与
え、これによって部分アドレスＡ₁とＡ₂の順序を入れ替
える。さらに、スイッチコントローラＰ２は、上記第３
のタンミングでセレクタＳ３から出力される部分アドレ
スＡ₂を、上記第４のタイミングでセレクタＳ３から出
力される部分アドレスＡ₁をそれぞれ選択し、また、第
５、第６のタイミングで、入力キューＱ１に格納された
部分データＤ₁，Ｄ₂をそれぞれ選択して、出力ポート選
択回路Ｅ１に与える様な制御信号Ｍ４をセレクタＳ４に
与える。選択回路Ｅ１の出力はキューＱ３に与えられ、
上記第３、第４、第５、第６のタイミングで、それぞれ
Ａ₁，Ａ₂，Ｄ₁，Ｄ₂が出力キューＱ３に入力・記憶され
る。これによって、上記の様に部分アドレスＡ₁，Ａ₂を
入れ替えて作られた転送先アドレスを入力キューＱ１内
に格納されたデータに先立って選択的に出力ポート選択
回路Ｅ１に与えることができる。

【００２１】図１１は図９のスイッチＳ００′、Ｓ２
４′、Ｓ３５′でアドレス到着待ちの時間が、図５の場
合の半分の時間Ｔで済む。従って、ネットワークの転送
所要時間は９Ｔとなり、図５の場合（図８）の１２Ｔと
比べて２５％高速化されることがわかる。

【００２２】なお、スイッチコントローラＰ２は入力ポ
ート１２から与えられるパケットに対しても同様な処理
を行なうことができ、図６の場合と同様に、入力ポート
１１と１２の入力データの優先判断を行うことができ
る。スイッチコントローラＰ２には、出力ポート０１、
０２の各々の出力許可信号ＯＥ１，ＯＥ２が与えられて
おり、ＯＥ１が出力許可状態となったとき、出力制御信
号ＯＣ１がスイッチコントローラＰ２から出力キューＱ
３に与えられ、出力キューＱ３から、上記部分アドレス
Ａ₁，Ａ₂，部分データＤ₁，Ｄ₂が順次出力ポート０１に
送出される。同様に信号ＯＥ２が出力許可状態となった
とき、出力制御信号ＯＣ２がスイッチコントローラＰ２
から出力キューＱ４に与えられる。出力キューＱ３，Ｑ
４がデータで満たされ、新しいデータを記憶できない状
態になった場合、それぞれスイッチコントローラＰ２に
接続されたステータス信号ＳＱ１，ＳＱ２がスイッチコ
ントローラＰ２に与えられる。そこからは通常入力端子
１１、１２の入力許可信号ＩＡ１，ＩＡ２が出力されて
いるが、上記ステータス信号ＳＱ１，ＳＱ２によって入
力許可信号ＩＡ１，ＩＡ２は入力禁止状態とされ、新た
なパケットが入力されることを禁止する。図９の構成の
場合、後段のスイッチの入力許可信号ＩＡ１（又はＩＡ
２）を、前段のスイッチに出力許可信号ＯＥ１（ＯＥ
２）として入力することで、送転径路の途中でキューの
あふれによってパケットが失なわれることを防げる。図
１において、レジスタＬ１，Ｌ２，出力キューＱ１，Ｑ
３へのデタのセットタイミングの制御は信号Ｔ１１，Ｔ
１２，Ｔ１３，Ｔ１４により、また、レジスタＬ３、Ｌ
４、出力キューＱ２、Ｑ４へデータのセットタイミング
の制御は信号Ｔ２１，Ｔ２２，Ｔ２３，Ｔ２４により行
なわれ、これらの信号はスイッチコントローラＰ２から
与えられる。図１３は図１のスイッチコントローラＰ２
の概略構成図である。図において、タイミング供給回路
１０Ａ，１０Ｂは、パケットスタースタート信号ＰＳＴ
Ｒ１又はＰＳＴＲ２に応答してアドレスデコーダ１６Ａ
又は１６Ｂを励動し、かつ、タイミングクロックをカウ
ンタ１２Ａ又は１２Ｂに与え、パケットの末尾が入力ポ
ート１１又は１２（図１）に与えられたタイミングに同
期して与えられる。パケット終了信号ＰＥＮＤ１に応答
して、カウンタ１２Ａ又は１２Ｂおよびタイミングデコ
ーダ１４Ａ又は１４Ｂをリセットするものである。アド
レスデコーダ１６Ａ又は１６ＢはレジスタＬ２はＬ４の
出力Ｃ２又Ｃ４の内、メモリＭＳ２から与えられ判定ピ
ット位置情報Ｊ２にて示されるピットを切り出し入力さ
れたパケットを出力ポート０１，０２のいずれに送るべ
きかの信号としてコンフリクト制御２２へ送出する。タ
イミングデコーダ１４Ａ、１４Ｂはカウンタ１２Ａ，１
２Ｂのカウント値にそれぞれ応答して、制御信号Ｔ１１
〜Ｔ１３，Ｍ３，Ｍ４を出力するとともに出力キュー制
御１８Ａ又は１８Ｂおよびセレクタ制御２４′を起動す
るものである。コンフリクト制御２２はアドレスデーダ
１６Ａ，１６Ｂの出力の間にコンフリクトがないかをチ
ェックし、なければセレクタ制御２４に送る。そこでセ
レクタ制御信号Ｍ１，Ｍ２を発生させる。コンフリクト
制御には上記２つの出力の間にコンフリクトがあればそ
の一方にのみ応答してセレクタ制御２４に送る。それと
ともに、アドレスデコーダ１６Ａ，１６Ｂの他方に対応
して設けられた入力制御２０Ａ又は２０Ｂ信号を送る。
入力・制御２０Ａ，２０Ｂは新たなパケットの送信を禁
止する信号ＩＡ１又はＩＡ２を発生マ、前段のスイッチ
に送る。

【００２３】出力キュー制御１８Ａ、１８Ｂは、出力キ
ューＱ３又はＱ４を制御する信号Ｔ１４，ＯＣを生成す
るとともに、パケットスタート信号ＰＳＴＲ１又はＰＳ
Ｔ２，パケット終了信号ＰＥＮＤ１又はＰＥＮＤ２を、
出力キューＱ３又はＱ４によるパケットの送信開始およ
びパケットの送信終了に同期して生成し、これらの信号
を次段のスイッチに送出するものである。

【００２４】図１２は、図８、図９の回路を用いて図１
１と異なるタイミング制御を行なう場合のタイムチャー
トを示している。この場合、図１１の場合と同様、図８
の回路のスイッチＳ１４′にはスイッチＳ００′から部
分アドレスＡ₁，Ａ₂，部分データＤ₁，Ｄ₂が入力ポート
１１に順次送られる。スイッチＳ１４′では第１のタイ
ミングで第１部分アドレスＡ₁をレジスタＬ２に記憶す
るとともに、次にデータを送出すべき出力ポートを決定
する。続く第２のタイミングで、第１部分アドレスをレ
ジスタＬ１に移動し、かつ、第２部分アドレスＡ₂をレ
ジスタＬ２をスルーさせて出力キューＱ３に送る。図１
２の実施例において、Ｓ１４′でパケットの転送先を決
めるために処理（解釈）が必要な部分アドレスＡ₁は第
１サブパケットに含まれており、第２サブパケットに含
まれる部分アドレスＡ₂はＳ１４′で処理（解釈）を必
要としない。従って、上記の様に第２のタイミングでレ
ジスタをスルーさせることが可能である。このときのス
イッチコントローラＰ２，セレクタＳ１，Ｓ２，Ｓ３，
Ｓ４の制御は図１１の場合と類似の方法で実現できる。
次に第３、第４のタイミングでそれぞれ部分データ
Ｄ₁，Ｄ₂を順次入力キューＱ１に格納し、かつ、第３の
タイミングでＡ₁、第４のタイミングでＤ₁、第５のタン
ミングでＤ₂をそれぞれ出力キューＱ３に送る。これに
よって、図１２では、図１１で必要だったＳ１４′にお
ける１Ｔ分の待ち時間を短縮する。図１２では図１１１
で９Ｔ必要であった転送時間を８Ｔに短縮し、待ち時間
のないバイブライン動作が実現できる。

【００２５】なお、以上の説明では、簡単のため、上記
部分アドレスＡ₁，Ａ₂、部分データＤ₁，Ｄ₂は一旦出力
キューＱ３に順次記憶されるとしたが、初めから出力許
可信号ＯＥ１が出力許可状態にあるとき、出力キューＱ
３をバイパス、又はスルーして直接、上記第３、第４、
第５、第６のタイミングで出力ポート０１に送出する構
成としても良いことは明らかである。また、部分アドレ
ス列、部分データ列が記憶される出力キューＱ３，Ｑ４
を出力ポートの前でなく、入力ポートの後に設けてもよ
く、また、その両方に設けても良いことは明らかであ
る。また、入力キューＱ１，Ｑ２出力キューＱ３，Ｑ４
はＦＩＦＯメモリであって良いが、ＲＡＭやレジスタフ
ァイルで構成しても良い。図２でレジスタＬ３とＬ４、
レジスタＬ１とＬ２は直列接続の構成としているが、セ
レクタを介して第１のサブパケットはレジスタＬ１（又
はＬ３）に、第２のサブパケットはレジスタＬ２（又は
Ｌ４）に格納する構成としてもよい。また、この場合、
レジスタＬ１〜Ｌ４は（データ語長が充分ある）ＲＡＭ
はレジスタファイルの一部分を用いて構成しても良い。

【００２６】以上の説明から明らかな様に、本発明の効
果はネットワークが大規模で、スイッチの段数が増すほ
ど効果が大となる。これまでの説明でデータ転送路のデ
ータ幅を２ビット、転送先アドレスを４ビット、データ
を４ビットとしたが、転送先アドレスのビット数が、デ
ータ転送路のデータ幅よりも大きければ、任意の値の場
合に本発明が有効であることは明らかである。また、ス
イッチは２入力／２出力のものを用いて説明したが、ス
イッチの構成、ネットワークの構成によらず本発明が有
効であることも明らかである。

【００２７】図１４は本発明の他の実施例を示す図であ
り、ＰＥ１１〜ＰＥ４４はプロセッサであり、各々のプ
ロセッサを接続するデータ転送ネットワークは、スイッ
チＥＸ１１〜ＥＸ４４とＸ部分ネットワークＮＸ１〜Ｎ
Ｘ４とＹ部分ネットワークとから成る。データ転送ネッ
トワークにおいて転送されるパケットは、図４に示した
ものと同じである。但し、転送先部分アドレスＡ₁，Ａ₂
はプロセッサＰＥ₁₁のＸ方範の添字ｉ、Ｙ方向の添字ｊ
に等しく定める。すなわち、プロセッサＰＥｉｊのアド
レスをＸアドレスｉ、Ｙアドレスｊの組にて表わす。

【００２８】図１４において、ｉが同じプロセッサＰＥ
ｉｊ（ｊ＝１〜４，ｉ＝１，２，３，４）および、ｊが
同じプロセッサＰＥｉｊ（ｉ＝１〜４，ｊ＝１，２，
３，４）がそれぞれ一つのクラスタに属する。

【００２９】Ｘ部分ネットワークＮＸｉ（ｉ＝１，２，
３，４）は、ｉを共通にするクラスタ（Ｘクラスタと呼
ぶ）のプロセッサＰＥｉｊ（ｊ＝１〜４）を相互に結合
し、Ｙ部分ネットワークＮＹｊ（ｊ＝１，２，３，４）
は、ｊを共通にするクラスタ（Ｙクラスタと呼ぶ）に属
するプロセッサＰＥｉｊ（ｉ＝１〜４）を相互に結合す
る。これら部分ネットワークＮＸｉ，ＮＹｊは、図９に
示されたような多段のスイッチにて構成されるネットワ
ークである。後に説明するように、そこに用いる多段ス
イッチの各々は部分アドレスの入れ替えをする必要がな
く、従って、図２のスイッチにて構成できる。スイッチ
ＥＸｉｊ（ｉ＝１〜４，ｉ＝１〜４）は、Ｘ部分ネット
ワークＮＸｉとＹ部分ネットワークＮＹｊとプロセッサ
ＰＥｉｊを相互に結合する３入力／３出力ポートのスイ
ッチである。

【００３０】例えば、部分ネットワークＮＸ１には、プ
ロセッサＰＥ１１，ＰＥ１２，ＰＥ１３，ＰＥ１４がそ
れぞれ、スイッチＥＸ１１，ＥＸ１２，ＥＸ１３，ＥＸ
１４を介して接続され、ＮＹ１には、プロセッサＰＥ１
１，ＰＥ１２，ＰＥ３１，ＰＥ４１がそれぞれレスイッ
チＥＸ１１，ＥＸ２１，ＥＸ３１，ＥＸ４１を介して接
続される。

【００３１】スイッチＥＸｉｊは図１５に示すようにプ
ロセッサＰＥｉｊとの入力ポートＩＰｉｊ、出力ポート
ＯＰｉｊ、部分ネットワークＮＸｉとの入力ポートＩＸ
ｉｊ、出力ポートＯＸｉｊ、部分ネットワークＮＹｊと
の入力ポートＩＹｉｊと出力ポートＯＹｉｊを有する。

【００３２】なお、スイッチＥＸｉｊは、後述するよう
に、部分アドレスＡ₁，Ａ₂の入れ替えをする必要がある
ため、例えば、図１のスイッチを３入力／３出力に変更
した図１６のものを用いる。図１６の各部分および、各
信号は図１の同じ英文字または英文字列で始まる符号を
持つ部分および信号と同様である。

【００３３】本実施例において、プロセッサＰＥｉｊと
プロセッサＰＥｋ１（１≦ｉ，ｊ，ｋ，１≦４）の間の
データ転送は、後に詳述するように、ＰＥｉｊ→ＥＸｉ
ｊ→ＮＸｉ→ＥＸｉ１→ＮＹ１→ＥＸｋ１→ＰＥｋ１ま
たは、ＰＥｉｊ→ＥＸｉｊ→ＮＹｉ→ＥＸｋｊ→ＮＸｋ
→ＥＸｋ１→ＰＥｋ１の２つの経路のいずれかを介して
行なうことができる。

【００３４】以下、図１４のネットワークの動作を図１
７〜図１９を参照して説明する。

【００３５】あるプロセッサＰＥｉｊからスイッチＥＸ
ｉｊが入力ポートＩＰｉｊを介してプロセッサＰＥｋ１
宛のパケットを受信した（ステップ１３０）とする。

【００３６】このパケットの先頭にある第１，第２部分
アドレスＡ₁，Ａ₂は今の場合宛先のプロセッサＰＥｋ１
のＸ方向アドレスｋ、Ｙ方向アドレスｌに等しい。

【００３７】（１）さて、スイッチＥＸｉｊは、図１７
に示すように、このパケットが第１の条件Ａ₁（＝ｋ）
＝自己のＸ方向アドレス（ｉ）を満すかを判定（ステッ
プ１３２）し、この条件が満されると、（すなわち、送
信先プロセッサＰＥｋ１と送信元プロセッサＰＥｉｊと
が同じＸクラスに属する場合）、このパケットが第２の
条件Ａ₂＝自己のＸ方向アドレス（ｊ）を満すか否かを
判定（ステップ）１３４）し、この条件も満される場合
（すなわち、送信元プロセッサＰＥｉｊと送信先プロセ
ッサＰＥｋ１とが同じ場合）、スイッチＥＸｉｊはその
出力ポートＯＰｉｊを介してこのパケットをプロセッサ
ＰＥｉｊに送る（スイップ１６３）。一方、ステップ１
３４における第２の条件の判定の結果、第２の条件が満
されなかった。場合（すなわち、送信先プロセッサＰＥ
ｋ１がプロセッサＰＥｉｊと同じＸクラスタに属する他
のプロセッサの場合）、部分アドレスＡ₁，Ａ₂を入れか
え（ステップ１３８）、出力端ＯＸｉｊを介して、Ｘ部
分ネットワークＮＸｉに、このパケットを送出する（ス
テップ１４０）。このアドレス入れかえにより、送信先
プロセッＰＥｋ１のＹ方向アドレスｌがこのパケットの
先頭に位置する。この結果、Ｘ部分ネットワークＮＸｉ
（＝ＮＸｋ）の各スイッチは、このパケットの最初のサ
ブパケットが到着し次第、その先頭部分にある部分部分
アドレスＡ₂に応答してスイッチングを開始できる。部
分ネットワークＮＸｋはこのパケットをスイッチＥＸｋ
１にそれの入力ポートＩＸｋ１を介して送出する。この
スイッチＥＸｋ１は、このパケットを受信する（ステッ
プ）と、図１８に示すように、そのパケットの先頭のサ
ブパケットにある部分アドレス（今の場合Ａ₂（＝
ｌ））がそのスイッチＥＸｋ１（＝ＥＸｉ１）のＹ方向
アドレスｌと等しいから判定する（ステップ１６４）。
今の場合、これらが等しいという条件が満されるのでス
イッチＥＸｋ１は、その出力ポートＯＰｋ１を介してプ
ロセッサＰＥｋ１にこのパケットを送る（ステップ１６
５）。

【００３８】こうして、同じＸクラスタ内にあるプロセ
ッサ間でパケット伝送が行なわれる。

【００３９】（２）図１７のステップ１３２では第１条
件の判定の結果、第１条件が満たされないことが分かっ
た場合（すなわち、送信先プロセッサＰＥｋ１と送信元
プロセッサＰＥｉｊが同じＸクラスタに属さない場
合）、第２の条件Ａ₂（＝ｌ）＝自己のＹ方向アドレス
（ｊ）か否かを判定する（ステップ１４２）。この判定
の結果、この条件が満された場合（すなわち、プロセッ
サＰＥｋ１とＰＥｉｊとは同じＸクラスタに属さないが
同じＹクラスタに属する場合、スイッチＥＸｉｊは、こ
のパケットをＹ部分ネットワークＮＹｊに、出力ポート
ＯＹｉｊを経由して送出する（ステップ１４４）。

【００４０】部分ネットワークＮＹｊは、このパケット
の先頭にある部分アドレスＡ₁（＝ｋ）と等しいＸアド
レスをもつスイッチ（Ｅｋｊ）にこのポケットを送る。
そのスイッチ（Ｅｋｊ）では、図１９に示すように、こ
のパケットを入力端ＩＹｋｊより受信する（ステップ１
５２）と、このパケットが第２部分アドレスＡ₂＝自己
のＹ方向アドレスと等しいかを判定する（ステップ１５
４）。今の場合、この条件は満されるので、スイッチＥ
ｋｊはそのパケットをそこにつながっているプロセッサ
（ＰＥｋｊ）に出力ポートＯＰｋｊを介して送る。こう
して、同じＹクラスタに属する２つのプロセッサ間のパ
ケット転送ができる。

【００４１】（３）また、図１７のステップ１４２にお
ける判定の結果が否定的な場合、すなわち、送信先プロ
セッサＰＥｋ１と送信元プロセッサＰＥｉｊが同じＸク
ラスタにも属さず、又同じＹクラスタにも属さない場
合、これらの２つのプロセッサを結ぶ経路は２通りあ
る。すなわち、第１のルートＸ部分ネットワークにまず
パケットを転送するルートであり、具体的にはＰＥｉｊ
→ＥＸｉｊ→ＮＸｉ→ＥＸｉ１→ＮＹ１→ＥＸｋ１→Ｐ
Ｅｋ１である。このルートではＹアドレスが先に決まる
ので以下このルートをＹ優先ルートとよぶ。第２のルー
トは、Ｙ部分ネットワークにまず、バケットを転送する
ルートであり、具体的にはＰＥｉｊ→ＥＸｉｊ→ＮＹｊ
→ＥＸｋｊ→ＮＸｋ→ＥＸｋ１→ＰＥｋ１である。この
ルートではＸアドレスが先に決まるので以下、これを優
先ルートと呼ぶ。

【００４２】ステップ１４６ではこれら２つのルートの
いずれかを選択する。

【００４３】この選択はあらかじめ各スイッチＥＸｉｊ
ごとに定めておいてもよい。この場合、ステップ１４６
は省略される。また、ネットワークの各部分ネットワー
クを通りパケットの量（負荷）を計測し、この負荷が出
来るだけ均一になるように動的に上記の選択をかえても
よい。

【００４４】ステップ１４６でＸ優先ルートが選ばれた
場合、ステッチＥＸｉｊはパケットを出力ポートＯＹｉ
ｊを介して部分ネットワークＮＹｊに送出する（ステッ
プ１４４）。このパケットを受けて、この部分ネットワ
ークＮＹｊは、そのパケットの先頭にある部分アドレス
Ａ₁（＝ｋ）に等しいＸアドレスをもつスイッチＥｋｊ
の入力ポートＩＹｋｊを介して送出する。このスイッチ
では、図１９に示すように、これを受信する（ステップ
１５２）と、このパケットの第２部分アドレスＡ₂（＝
１）＝自己のＹアドレス（＝ｊ）が満されるか否かを判
定する（ステップ１５４）。今の場合、ｊ≠ｌと仮定し
ているのでこの判定の結果は否定的となる。このスイッ
チＥｋｊはこのパケットの部分アドレスＡ₁，Ａ₂を入れ
か、部分アドレスＡ₂を先頭に移す（ステップ１５
８）。その後、このパケットをＸ部分ネットワークＮＸ
ｋに、出力ポートＯＸｊｋを介して送出する。

【００４５】この部分ネットワークＮＸｋの中の各スイ
ッチは、このパケットの先頭にある部分アドレスＡ₂が
到着次第それに応答できる。そうして、この部分ネット
ワークは部分アドレスＡ₂（＝ｌ）に等しいＹ方向アド
レスをもつスイッチＥｋ１にこのパケットを送出する。

【００４６】このスイッチＥｋ１は、入力ポートＩＸｋ
１を介してこのパケットを受信する（ステップ１６２、
図１８と、このパケットの第１部分アドレスＡ₁自己の
Ｘ方向アドレス（＝ｋ）に等しいかを判定する。今の場
合、この判定結果は肯定的であるので、このパケットを
スイッチＥｋ１はプロセッサＰＥｋ１に送出する。こう
して、同じクラスタに属さない２つのプロセッサ間のパ
ケット転送がＸ優先ルートによりなされる。

【００４７】なお、ステップ１４６（図１７）で、Ｙ優
先ルートが選ばれた場合、スイッチＥＸｉｊは、パケッ
ト中の部分アドレスＡ₁，Ａ₂を入れかえＡ₂を先頭に移
す（ステップ１３８）。その後、このパケットをＸ部分
ネットワークＮＸｉに送出する（ステップ１４０）。こ
の部分ネットワークＮＸｉはこのパケットを、この部分
アドレスＡ₁（＝ｌ）に等しいＹアドレスをもつスイッ
チＥＸｉ１にこのパケットを送出する。

【００４８】このスイッチＥＸｉｌでは図１８に示す
と、このバケット受信（ステップ１６２）した後、Ａ₁
（＝ｋ）＝自己のＸ方向アドレス（＝ｉ）と等しいかを
判定する（ステップ１６４）。今の場合、この判定結果
は否定的となり、このスイッチは部分アドレスＡ₂，Ａ₁
を入れかえ、Ａ₁をパケットの先頭に移し（ステップ１
６８）、再びこのパケットをＹ部分ネットワークＮＹ１
に転送する（ステップ１７０）。この部分ネットワーク
ＮＹ１により、このパケットはこのパケットの第１部分
アドレスＡ₁（＝ｋ）に等しいＸ方向アドレスをもって
スイッチＥｋｌにこのパケットを転送する。このスイッ
チＥｋｌでは図１４のステップ１５２，１５４，１５６
によりこのパケットをそこに接続されたプロセッサＰＥ
ｋｌに送出する。こうして、同じクラスタに属さない２
つのプロセッサ間でパケットがＹ優先ルートによりなさ
れる。

【００４９】本実施例のようなネットワークの利点は、
各部分ネットワークの規模が小さくなることにより、実
装が容易となる点にある。そして、上記の様にプロセッ
サがクラスタ化されているため、部分ネットワークＮＹ
ｊの中では転送先アドレスのうち第１部分アドレスＡ₁
のみ、ＮＸｉの中では第２部分アドレスＡ₂のみが必要
となる。本実施例では、スイッチＥＸｉｊ中にＡ₁，Ａ₂
の入れ替え手段を有するため、各部分ネットワークＮＸ
ｉ、ＮＸｊ中で必要な部分アドレスが常に第１サブパケ
ットにあるので、部分ネットワーク中のそれぞれのスイ
ッチは部分アドレスの全ての到着を待つ必要はなく、高
速なデータ転送が可能となる。

【００５０】図１４のネットワークの動作時、次のよう
にかえると更に高速化される。

【００５１】すなわち、図１８においては、ｍ，ｎを整
数としてそれぞれのスイッチ（ＥＸｍｎ）がＸ部分ネッ
トワークＮＸｍからパケットを受信したときの判定１６
４は、ネットワークＮＸｍから部分アドレスＡ₁の到着
をまって行う必要がある。しかし、すでに述べたよう
に、ネットワークＮＸｎでは、パケットは部分アドレス
Ａ₂をその先頭に有する。したがって、上記判定１６４
は部分ネットワークＮＸｍから２つ目のサブパケットが
スイッチＥＸｍｎに到着するのをまって始めて可能にな
る。同じ問題は図１９の判定１５４についても生じる。
これらの問題は部分ネットワークＮＸｍ、ＮＹｎ等を以
下のように変更することにより改良される。

【００５２】すなわち、部分ネットワークＮＸｍ又はＮ
Ｙｎ等をそれぞれ図２０，図２１のステップ１８０Ａ、
１８０Ｂとして、示すように、それぞれからパケットを
あるスイッチＥＸｍｎに出力する際、そのスイッチに最
も近い部分ネットワーク内スイッチにおいて、パケット
中の部分アドレスＡ₁，Ａ₂を入れかえるように構成す
る。これは、図１２において説明した方法と同様に実現
できる。

【００５３】これらの結果Ｘ部分ネットワークからＮＸ
ｍかはパケットに受信したスイッチＥＸｎｍの動作は、
図２２に示すようになる。図において図１８と同じ参照
番号は同じ処理をさす。この図から分かるようにこの改
良された動作では、スイッチＥＸｍｎは、部分アドレス
Ａ₁についての判定処理１４４を行うのは図１８の場合
と同じであるが、すでに述べた改良によりＸ部分ネット
ワークＮＸｍから送られるパケットの先頭にこの部分ア
ドレスＡ₁が含まれているので、この判定処理１４４は
この部分アドレスＡ₁が到着し次第開始できる。また、
Ｘ部分ネットワークＮＸｍがパケット出力時にアドレス
を入れかえた結果、図１８で必要としたアドレス入れか
え図２２においては必要としない同様にＹ部分ネットワークＮＹｍからパケットを受信し
たときのスイッチＥＸｍの動作は、図２３のようにな
る。図において図１９を同じ参照番号は同じものをさ
す。この場合も、図２２と図１８についての比較がその
ままあてはまる。

【００５４】なお上記の説明で、Ａ₁，Ａ₂は２ビット、
ｄは２ビットとしたが、これが任意のビット数であって
も本発明の効果に変わりはない。また、転送先アドレス
を３分割とし、Ｘ，Ｙ方向の他にＺ方向の様な部分ネッ
トワークを設け、ＥＸｉｊをＥＸｉｊｋの様に４入力ポ
ート／４出力ポートとする、という様に、転送先アドレ
スの分割数を増して良いことも明らかである。

【００５５】図２４はそのようなデータ転送ネットワー
クの実施例を示す。図において、ＮＸ₁₁，ＮＸ₁₂、ＮＸ
₁₄、Ｎ₄₄等はＸ方向の部分転送ネットワーク７．１を表
わし、ＮＹ₁₁，ＮＹ₁₂，ＮＹ₁₄、ＮＹ₄₄等はＹ方向の部
分転送ネットワークを表わし、これらは第１１Ａ図と同
じものである本実施例ではＺ方向の部分ネットワークＮ
Ｚ₁₁、ＮＺ₂₁、ＮＺ₄₁，ＮＺ₁₄…ＮＺ₄₄等が設けられて
いる。

【００５６】これら３つの部分ネットワークの交叉点に
スイッチＥＸ₁₁₁、Ｅ₁₄₁、ＥＸ₄₁₁、ＥＸ₄₄₄等およびプ
ロセッサＰＥ₁₁₁、ＰＥ₁₄₁、ＰＥ₄₁₁、ＰＥ₄₄₄が設けら
れている。

【００５７】図では簡単化のために各部分ネットワーク
を直線で表わし、かつ、スイッチ、プロセッサは一部の
み表わし、かつ、スイッチ、プロセッサは一部のみ表わ
している。

【００５８】スイッチＥＸ₁₁₁は、Ｘ方向部分ネットワ
ークＮＸ₁₁、Ｙ方向部分ネットワークＮＹ₁₁、Ｚ方向部
分ネットワークＮＺ₁₁およびプロセッサＰＥｌ₁₁のそれ
ぞれに対して入力ポートと出力ポートで接続されてい
る。

【００５９】他のプロセッサについても同じである。

【００６０】あるプロセッサから他のプロセッサにパケ
ットを転送する場合、パケット内の転送先アドレスをＡ
₁、Ａ₂、Ａ₃の部分から構成する。それぞれはパケット
送信先のプロセッサをＰｉｊｋとするとき、それぞれの
Ｘ，Ｙ，Ｚ方向座標ｉ，ｊ，ｋに等しい。

【００６１】今、例えば、プロセッサＰＥ₁₁₂からＰＥ
₄₄₄にパケットを送出する場合、パケット転送ルートは
いくつかある。たとえば、ＰＥ₁₁₁→ＥＸ₁₁₁→ＮＸ₁₂→
ＥＸ₄₁₁→ＮＹ₁₄→ＥＸ₄₄₁→ＮＺ₄₄→ＥＸ₄₄₄→ＰＥ₄₄₄
はその一つである。

【００６２】このルートにしたがってパケットを転送す
る場合の動作は以下のとおりである。

【００６３】スイッチＥＸ₁₁₁がこのパケットを部分ネ
ットワークＮＸ₁₁に送出する場合、スイッチＥＸ₁₁₁は
図１７の場合と同様に、部分アドレスＡ₁，Ａ₂，Ａ₃を
入れかえることなく、転送する。部分ネットワークＮＸ
₁₁はこのパケットを、アドレスＡ₁に等しいＸ座標をも
つスイッチＥＸ₄₁₁に送出する。スイッチＥＸ₄₁₁はこの
パケット内の部分アドレスＡ₃，Ａ₂，Ａ₁の内のＡ₂が自
己のＹ座標と異なるので、Ｙ方向部分ネットワークＮＹ
₁₄に送出する。その際パケット内のアドレスをＡ₂、
Ａ₃、Ａ₁の順に入れかえる。このネットワークはパケッ
トをアドレスＡ₂に等しいＹ座標をもつスイッチＥＸ₄₄₁
に送出する。

【００６４】スイッチＥＸ₄₄₁では、この中の部分アド
レスＡ₂が自己のＺ座標と異なるので、このパケットを
Ｚ方向部分ネットワークＮＺ₄₄に送出する。その際、ア
ドレスをＡ₃、Ａ₁、Ａ₂の順に入れかえる。このネット
ワークはこのパケットをアドレスＡ₂に等しいＺ座標を
もつＥＸ₄₄に送出する。これを受けたスイッチＥＸ₄₄₄
はこのパケットをプロセッサＰＥ₄₄₄に送出する。

【００６５】このように本実施例では、図１４の場合よ
りも多くのプロセッサがある場合に、それらの間のデー
タ転送を行うことができる。かつ、上述のようなアドレ
ス入れかえを各スイッチＥＸが行うので部分ネットワー
クが到着したパケットの先頭の部分アドレスに応答して
スイッチできる。

【００６６】なお、図２２、図２３で示したように、ス
イッチ時ＥＸ₄₁₁、ＥＸ₄₄₁でのアドレスの入れかえにか
え、部分ネットワークＮＸ₁₁、ＮＹ₁₁、ＮＺ₄₄が、パケ
ット出力時に３アドレス入れかえをする方がより高速な
動作が処理できる。

【００６７】図２５は本発明の実施例である。ＰＥはプ
ロセッサ、ＥＸはスイッチであり、図に示す如く、プロ
セッサＰＥ１００と同様な複数のプロセッサの各々に対
して、スイッチＥＸ１００と同様な１個のスイッチが設
けられ、かつ各々のスイッチＥＸは互いに４近傍のスイ
ッチに入力ボート、出力ボートにより接続されて、網状
のデータ転送ネットワークを構成している。また、図２
６に示すように、スイッチＥＸ１００はプロセッサＰＥ
１００との間の入力／出力ボートＩＰ１００／ＯＰ１０
０、また４近傍スイッチとの間の入力／出力ポート、Ｉ
Ｎ１００／ＯＮ１００、ＩＷ１００／ＯＷ１００、ＩＳ
１００／ＯＳ１００、ＩＥ１００／ＯＥ１００を有して
いる。本実施例でも、これまで述べたと同様、プロセッ
サ間を転送されるパケットは、図２８の様に、データ転
送路のビット幅ｄごとに分割されたサブパケットの例か
ら成るパケットとして授受される。本実施例が他の実施
例と異なるのは、上記パケット中の転送先アドレスがｄ
−１ビット以下のビット数となる様に２分割され、分割
された転送先アドレスの上位の部分をグローバル・アド
レスＡ_G、下位の部分をローカル・アドレスＡ_Lとして用
いるとともに、Ａ_G，Ａ_Lがそれぞれ上記のサブパケット
に格納され、かつ、先頭のサブパケットには、それが格
納している分割アドレスがＡ_GかＡ_Lかを示すフラグビッ
トＬを設けた点である。これで簡単のため、ｄ＝４と
し、Ａ_G，Ａ_Lがそれぞれ３ビットとする。図２７に示す
様に、Ａ_G，Ａ_L合計６ビットで表わされる６４個のプロ
セッサが同図２６の様にスイッチで結合されており、か
つ、プロセッサは図２７の様に、同じグローバル・アド
レスを持つもの８個ずつクラスタ化されている。本実施
例では、各々のスイッチは、例えば図９、図１６と同様
なスイッチを５入力ポート／出力ポートの構成とした、
図３０に示す構成を用いることができる。図３０の各部
の動作、及び符号の意味は図９の同じ英文字（列）で始
まる符号を持つ各部と同様である。図３０の構成では図
９の構成と異なるのは、分割アドレス記憶用レジスタＬ
１２，Ｌ２２とセレクタＳ３１の間に、上記フラグビッ
トＬのセット回路Ｘ２１を設けたことである。Ｘ２１は
スイッチコントローラＰ２１からのセット信号ＸＣ２１
により上記フラグビットＬをセットする。以下スイッチ
の動作につき述べる。なお、図２０で、Ｒ２２〜Ｒ２５
で示される部分は、Ｒ２１で示される部分と同様の構成
であり、簡単なため省略して示してある。各プロセッサ
では、データを始めて送出する際にＡ_Gを先頭サブパケ
ットに入れ、かつ、Ｌビットを０とする。各スイッチに
おける処理の手順を図２９に示す。本実施例では、Ｌビ
ットが設けられているため、各スイッチはＬ＝０である
間はローカルアドレスＡ_Lを参照する必要がなく、従っ
て、上記の様に分割された転送先アドレスを含む全ての
サブパケットの到着を待つことなく、パケットを送出す
べき次段のスイッチを確定することができる。パケット
が次々と転送されて、目標のプロセッサと同じグローバ
ルアドレスを持クラスタ中のスイッチに入ると、該スイ
ッチでは、ローカルアドレスＡ_Lを含むサブパケットの
到着を待ち、図９の場合と同様にＡ_LとＡ_Gを入れ替え
て、ローカルアドレスが第１サブパケットに入るように
するとともに、Ｌ＝１として次段に送出する。以降のス
イッチでは、今度はグローバルアドレスを含む第２サブ
パケットの到着を待つことなく、パケットを送出すべき
次段のスイッチを確定することができる。

【００６８】図２７で各プロセッサは、図示の様なアド
レスを持つと、Ａ₀＝０００，Ａ_L＝１１０のプロセッサ
ＮＳから、Ａ₀＝１１０，Ａ_L＝１１０のプロセッサＮＲ
へバケットを送る場合を考える。ここで、各々のスイッ
チには隣接のプロセッサのローカルアドレスと、隣接の
クラスタのグローバルアドレスが、自己のアドレスとと
もに記憶されており、Ｌ＝０の間はグローバルアドレス
Ａ₀と自己のグローバルアドレスを比較し、異なる場合
は、Ａ₀と隣接クラスタのグローバルアドレスを比較し
て転送方向、出力ポートを決定する。最も単純には、グ
ローバルアドレスの差が最も小さくなる方向に送出すれ
ば良い。このアルゴリズムに従うと、パケットは図２７
の様な経路をたどり、ＮＸで示された位置（Ａ₀＝１１
０，Ａ_L＝０００）のスイッチに至る。ここでＮＸのス
イッチは図９のスイッチの場合と同様にＡ_LとＡ₀を入れ
替え、Ｌ＝１として次段に送出する。以降は、ローカル
アドレスを隣接プロセッサのローカルアドレスと比較
し、上記と同様のアルゴリズムにより、転送方向、出力
ポートを決定していくことができる。本実施例で各段の
スイッチのうち、Ａ₀とＡ_Lを含んだ２つのサブパケット
の到着を待つ必要があるのはＮＸのスイッチのみであ
り、その他のスイッチでは、転送先アドレスの到着待ち
の時間は、本発明を使わない場合の半分で済み、特にプ
ロセッサの台数が大きいとき、効果が非常に大きい。

【００６９】上記の説明でＡ₀，Ａ_Lは各々３ビットとし
たが任意のビット数でも本発明の効果に変わりはない。

【００７０】また、転送先アドレスは２分割としたが、
分割数を増すとともに、上記Ｌなるビットをこれに応じ
て複数ビットとしても、本発明の効果に変わりはない。
さらに、データ転送ネットワークのスイッチは４近傍と
接続されているとしたが、任意の側数と接続それていて
も本発明の効果に変わりはない。

【００７１】これまでの実施例の説明では、データパケ
ットの行先は、始めの２つ以上のサブパケットに含まれ
る転送先アドレスによって示されるとしてきたが、これ
と等価な、転送先アドレスを示すためのタグ情報であっ
ても良いことは明らかである。この様なタグ情報として
は、例えば、発信プロセッサのアドレスと転送先アドレ
スのExclusive Orをとったもの、等を用いることができ
る。

【００７２】

【発明の効果】以上本発明によれば、データ転送ネット
ワークの、多段に構成された複数のスイッチの各々の段
で、転送先アドレスを含む複数のサブパケット全ての到
着を待つ必要がないので、高速なデータ転送が可能にな
る。

【図面の簡単な説明】

【図１】図８の装置の第２段のスイッチ（Ｓ１４’等）
の概略構成図。

【図２】図８の装置の第１、第３又は第４段のスイッチ
（Ｓ００’，Ｓ２４’orＳ３５’）の概略構成図。

【図３】本発明によるデータ転送Networkが適用それる
並列計算機システムのブロックを示す図。

【図４】本発明のパケットの構造を示す図。

【図５】本発明と比較するための低速のデータ転送ネッ
トワークの概略構成図。

【図６】図３のネットワークのスイッチ（Ｓｉｊ）の概
略構成図。

【図７】図３のネットワークのスイッチの動作を説明す
るための図。

【図８】図３のネットワークの動作のタイムチャート。

【図９】本発明によるデータ転送ネットワークの概略構
成図。

【図１０】図８の装置のスイッチの動作を説明するため
の図。

【図１１】図８の装置の動作の１例のタイムチャート。

【図１２】図８の装置の動作の他の例のタイムチャー
ト。

【図１３】図９のスイッチに用いるスイッチコントロー
ラ（Ｐ２）の概略構成図。

【図１４】部分ネットワークを用いた、本発明によるデ
ータ転送ネットワークの他の実施例。

【図１５】部分ネットワークを用いた、本発明によるデ
ータ転送ネットワークの他の実施例。

【図１６】図１４、図１５の装置に用いるスイッチ（Ｅ
Ｘｉｊ）の概略構成図。

【図１７】図１６のスイッチ（ＥＸｉｊ）が、パケット
をプロセッサから受信したときの動作のフローチャー
ト。

【図１８】図１６の装置に用いるスイッチ（ＥＸｉｊ）
がパケットを部分ネットワークＮＹから受信したときの
動作のフローチャート。

【図１９】図１６の装置に用いるスイッチ（ＥＸｉｊ）
がパケットを部分ネットワークＮＸから受信したときの
動作のフローチャート。

【図２０】図１６の装置のＸ方向部分ネットワーク（Ｎ
Ｘｊ）の改良された動作のフローチャート。

【図２１】図１６の装置のＹ方向部分ネットワーク（Ｎ
Ｙｉ）の改良された動作のフローチャート。

【図２２】図１６の装置のスイッチ（ＥＸｉｊ）がＹ方
向部分ネットワーク（ＮＹｉ）からパケットを受信した
ときの改良された動作のフローチャート。

【図２３】図１６の装置のスイッチ（ＥＸｉｊ）がＸ方
向部分ネットワーク（ＮＸｊ）からパケットを受信した
ときの改良された動作のフローチャート。

【図２４】３次元の、部分ネットワークを用いたデータ
転送ネットワークの実施例。

【図２５】格子結合のネットワークを用いた本発明の他
の実施例。

【図２６】図２５のスイッチ（ＥＸ１００）の入出力ポ
ートを示す図。

【図２７】図２５の装置におけるデータ転送ルートを示
す図。

【図２８】図２５の装置に用いるパケットを示す図。

【図２９】図２５の装置のスイッチ（ＥＸ）の動作のフ
ローチャート。

【図３０】図２５の装置のスイッチ（ＥＸ）の概略構成
図。

───────────────────────────────────────────────────── フロントページの続き (72)発明者濱中直樹東京都国分寺市東恋ケ窪１丁目280番地株式会社日立製作所中央研究所内 (72)発明者長島重夫東京都国分寺市東恋ケ窪１丁目280番地株式会社日立製作所中央研究所内

Claims

【特許請求の範囲】

【請求項１】複数のプロセッサを接続し、それら相互の
間でデータを転送するためのデータ転送ネットワークに
おいて、プロセッサ間のデータ転送は、送り先プロセッサのアド
レスまたはアドレスを示すタグと送達されるべきデータ
とを含むパケットの送受によって行なわれ、上記送り先プロセッサのアドレスまたはアドレスを示す
タグは、複数ビットから構成されるＤ組の部分アドレス
（Ｄは２以上の整数）から構成され、上記複数のプロセッサは、上記Ｄ組のうちのある組の部
分アドレスが同じものごとにグループ分けされ、データ転送ネットワークは、該グループ分けされた複数
のプロセッサをグループ内で相互に接続する部分ネット
ワークと、上記プロセッサの各々に１対１体応する複数
の交換スイッチを有し、該交換スイッチによって、各プ
ロセッサは、上記Ｄ個の組の部分アドレスに各々対応す
るＤ個の部分ネットワークに接続され、上記交換スイッチは、ある部分ネットワークから受信し
たパケットの送り先アドレスが、その交換スイッチが接
続されたプロセッサと一致する場合、これをプロセッサ
に転送し、他のパケットの場合は、それを受信した部分
ネットワークと異なる部分ネットワークに転送すること
を特徴とするデータ転送ネットワーク。
【請求項２】複数のプロセッサを接続し、それら相互の
間でデータを転送するためのデータ転送ネットワークに
おいて、プロセッサ間のデータ転送は、送り先プロセッサのアド
レスまたはアドレスを示すタグと送達されるべきデータ
とを含むパケットの送受によって行なわれ、上記送り先プロセッサのアドレスまたはアドレスを示す
タグは、複数ビットから構成されるＤ組の部分アドレス
（Ｄは２以上の整数）から構成され、上記複数のプロセッサは、上記Ｄ組のうちのある組の部
分アドレスが同じものごとにグループ分けされ、データ転送ネットワークは、該グループ分けされた複数
のプロセッサをグループ内で相互に接続する部分ネット
ワークと、上記プロセッサの各々に１対１対応する複数
の交換スイッチを有し、該交換スイッチによって、各プ
ロセッサは、上記Ｄ個の組の部分アドレスに各々対応す
るＤ個の部分ネットワークに接続され、上記交換スイッチは、ある部分ネットワークから受信し
たパケットの送り先アドレスが、その交換スイッチが接
続されたプロセッサと一致する場合、これをプロセッサ
に転送し、他のパケットの場合は、それを受信した部分
ネットワークと異なる部分ネットワークに転送し、上記部分ネットワークは上記部分アドレスのうちのあら
かじめ決められた１または複数のビットをデコードして
上記パケットの転送先を決定する転送先決定手段を有
し、上記交換スイッチは、受信された複数の上記部分アドレ
スの転送順序を変更するための転送順序変更手段を有
し、上記パケットがある部分ネットワークから他の部分
ネットワークに転送されるときに、上記転送先決定手段
が転送先を決定するに必要な部分アドレスを、受信した
すべての部分アドレスのなかで最初に転送することを特
徴とするデータ転送ネットワーク。
【請求項３】複数のプロセッサを接続し、それら相互の
間でデータを転送するためのデータ転送ネットワークに
おいて、プロセッサ間のデータ転送は、送り先プロセッサのアド
レスまたはアドレスを示すタグと送達されるべきデータ
とを含むパケットの送受によって行なわれ、上記送り先プロセッサのアドレスまたはアドレスを示す
タグは、複数ビットから構成されるＤ組の部分アドレス
（Ｄは２以上の整数）から構成され、上記複数のプロセッサは、上記Ｄ組のうちのある組の部
分アドレスが同じものごとにグループ分けされ、データ転送ネットワークは、該グループ分けされた複数
のプロセッサグループ内で相互に接続する部分ネットワ
ークと、上記プロセッサの各々に１対１対応する複数の
交換スイッチを有し、該交換スイッチによって、各プロ
セッサは、上記Ｄ個の組の部分アドレスに各々対応する
Ｄ個の部分ネットワークに接続され、上記交換スイッチは、ある部分ネットワークから受信し
たパケットの送り先アドレスが、その交換スイッチが接
続されたプロセッサと一致する場合、これをプロッサに
転送し、他のパケットの場合は、それを受信した部分ネ
ットワークと異なる部分ネットワークに転送し、上記パケットに含まれるデータは、複数ビットから構成
される複数の部分データを有し、上記部分ネットワークは、複数のスイッチが多段に接続
され、上記部分ネットワークおよび交換スイッチを構成する各
々のスイッチは、前段および後段のスイッチにそれぞれ
接続され、前段のスイッチから、上記パケットを受信す
る手段を有し、上記受信手段は、上記複数の部分アドレスの個々の部分
アドレスはそのすべてのビットを並列に受信し、上記複
数の部分データの個々の部分データはそのすべてのビッ
トを並列に受信し、かつ、複数の部分アドレス、複数の
部分データを逐次的に受信し、各々のスイッチは、上記受信手段と次段の複数のスイッ
チの間に接続された経路選択手段を有し、該経路選択手段は、受信された複数の部分アドレスの個
々の部分アドレスそはのすべてのビットを並列に転送
し、また複数の部分データの個々の部分データはそのす
べてのビッを並列に転送し、かつ複数の部分アドレス、
複数の部分データを逐次的に転送し、各々のスイッチは、上記受信手段と経路選択手段に接続
された制御手段を有し、該制御手段は、上記部分アドレスのうちのあらかじめ決
められた１または複数のビットに応動して上記経路選択
手段を制御し、上記スイッチの少なくとも一部のスイッ
チに含まれる上記制御手段は、パケットの最初の部分ア
ドレスの到着に応動して残りの少なくとも１つ以上の部
分アドレスが到着する前に、該最初の部分アドレスの中
の予め決められた１または複数のビットをデコードして
上記経路選択手段を制御することを特徴とするデータ転
送ネットワーク。
【請求項４】複数のプロセッサを接続し、それら相互の
間でデータを転送するためのデータ転送ネットワークに
おいて、プロセッサ間のデータ転送は、送り先プロセッサのアド
レスまたはアドレスを示すタグと送達されるべきデータ
とを含むパケットの送受によって行なわれ、上記送り先プロセッサのアドレスまたはアドレスを示す
タグは、複数ビットから構成されるＤ組の部分アドレス
（Ｄは２以上の整数）から構成され、上記複数のプロセッサは、上記Ｄ組のうちのある組の部
分アドレスが同じものごとにグループ分けされ、データ転送ネットワークは、該グループ分けされた複数
のプロセッサをグループ内で相互に接続する部分ネット
ワークと、上記プロセッサの各々に１対１対応する複数
の交換スイッチを有し、該交換スイッチによって、各プ
ロセッサは、上記Ｄ個の組の部分アドレスに各々対応す
るＤ個の部分ネットワークに接続され、上記交換スイッチは、ある部分ネットワークから受信し
たパケットの送り先アドレスが、その交換スイッチが接
続されたプロセッサと一致する場合、これをプロセッサ
に転送し、他のパケットの場合は、それを受信した部分
ネットワークと異なる部分ネットワークに転送し、上記パケットに含まれるデータは、複数ビットから構成
される複数の部分データを有し、上記部分ネットワークは、複数のスイッチが多段に接続
され、上記部分ネットワークおよび交換スイッチを構成する各
々のスイツチは、前段および後段のスイッチにそれぞれ
接続され、前段のスイッチから、上記パケットを受信す
る手段を有し、上記受信手段は、上記複数の部分アドレスの個々の部分
アドレスはそのすべてのビットを並列に受信し、上記複
数の部分データの個々の部分データはそのすべてのビッ
トを並列に受信し、かつ、複数の部分アドレス、複数の
部分データを逐次的に受信し、各々のスイッチは、上記受信手段と次段の複数のスイッ
チの間に接続された経路選択手段を有し、該経路選択手段は、受信された複数の部分アドレスの個
々の部分アドレスはそのすべてのビットを並列に転送
し、また複数の部分データの個々の部分データのすべて
のビットを並列に転送し、かつ複数の部分アドレス、複
数の部分データを逐次的に転送し、各々スイッチは、上記受信手段と経路選択手段に接続さ
れた制御手段を有し、該制御手段は、上記部分アドレスのうちのあらかじめ決
められた１または複数のビットに応動して上記経路選択
手段を制御し、上記スイッチのうちの少なくとも上記交換スイッチは、
受信された複数の上記部分アドレスの転送順序を変更す
るための転送順序変更手段を有し、上記パケットがある
部分ネットワークから他の部分ネットワークに転送され
るときに、該他の部分ネットワークに含まれるスイッチ
の上記制御手段がその経路選択手段を制御するに必要な
部分アドレスを、受信したすべての部分アドレスのなか
で最初に転送することを特徴とするデータ転送ネットワ
ーク。
【請求項５】複数のプロセッサを接続し、それら相互の
間でデータ転送するためのデータ転送ネットワークにお
いて、プロセッサ間のデータ転送は、送り先プロセッサのアド
レスまたはアドレスを示すタグと送達されるべきデータ
とを含むパケットの送受によって行なわれ、上記送り先プロセッサのアドレスまたはアドレスを示す
タグは、複数ビットから構成されるＤ組の部分アドレス
（Ｄは３以上の整数）から構成され、上記複数のプロセッサは、上記Ｄ組のうちのある組の部
分アドレスが同じものごとにグループ分けされ、データ転送ネットワークは、該グループ分けされた複数
のプロセッサをグループ内で相互に接続する部分ネット
ワークと、上記プロセッサの各々に１対１対応する複数
の交換スイッチを有し、該交換スイッチによって、各プ
ロセッサは、上記Ｄ個の組の部分アドレスに各々対応す
るＤ個の部分ネットワークに接続され、上記交換スイッチは、ある部分ネットワークから受信し
たパケットの送り先アドレスが、その交換スイッチが接
続されたプロセッサと一致する場合、これをプロセッサ
に転送し、他のパケットの場合は、それを受信した部分
ネットワークと異なる部分ネットワークのなかで、その
部分ネットワークに対応する上記部分アドレスが、その
交換スイッチが接続されたプロセッサと異なる部分ネッ
トワークに転送することを特徴とするデータ転送ネット
ワーク。
【請求項６】複数のプロセッサを接続し、それら相互の
間でデータを転送するためのデータ転送ネットワークに
おいて、プロセッサ間のデータ転送は、送り先プロセッサのアド
レスまたはアドレスを示すタグと送達されるべきデータ
とを含むパケットの送受によって行なわれ、上記送り先プロセッサのアドレスまたはアドレスを示す
タグは、複数ビットから構成されるＤ組の部分アドレス
（Ｄは３以上の整数）から構成され、上記複数のプロセッサは、上記Ｄ組のうちのある組の部
分アドレスが同じものごとにグループ分けされ、データ転送ネットワークは、該グループ分けされた複数
のプロセッサをグループ内で相互に接続する部分ネット
ワークと、上記プロセッサの各々に１対１対応する複数
の交換スイッチを有し、該交換スイッチによって、各プ
ロセッサは、上記Ｄ個の組の部分アドレスに各々対応す
るＤ個の部分ネットワークに接続され、上記交換スイッチは、ある部分ネットワークから受信し
たパケットの送り先アドレスが、その交換スイッチが接
続されたプロセッサと一致する場合、これをプロセッサ
に転送し、他のパケットの場合は、それを受信した部分
ネットワークと異なる部分ネットワークのなかで、その
部分ネットワークに対応する上記部分アドレスが、その
交換スイッチが接続されたプロセッサと異なる部分ネッ
トワークに転送し、上記部分ネットワークは上記部分アドレスのうちのあら
かじめ決められた１または複数のビットをデコードして
上記パケットの転送先を決定する手段を有し、上記交換スイッチは、受信された複数の上記部分アドレ
スの転送順序を変更するための手段を有し、上記パケッ
トがある部分ネットワークから他の部分ネットワークに
転送されるときに、上記転送先決定手段が転送先を決定
するに必要な部分アドレスを、受信したすべての部分ア
ドレスのなかで最初に転送することを特徴とするデータ
転送ネットワーク。
【請求項７】複数のプロセッサを接続し、それら相互の
間でデータを転送するためのデータ転送ネットワークに
おいて、プロセッサ間のデータ転送は、送り先プロセッサのアド
レスまたはアドレスを示すタグと送達されるべきデータ
とを含むパケットの送受によって行なわれ、上記送り先プロセッサのアドレスまたはアドレスを示す
タグは、複数ビットから構成されるＤ組の部分アドレス
（Ｄは３以上の整数）から構成され、上記複数のプロセッサは、上記Ｄ組のうちのある組の部
分アドレスが同じものごとにグループ分けされ、データ転送ネットワークは、該グループ分けされた複数
のプロセッサをグループ内で相互に接続する部分ネット
ワークと、上記プロセッサの各々に１対１対応する複数
の交換スイッチを有し、該交換スイッチによって、各プ
ロセッサは、上記Ｄ個の組の部分アドレスに各々対応す
るＤ個の部分ネットワークに接続され、上記交換スイッチは、ある部分ネットワークから受信し
たパケットの送り先アドレスが、その交換スイッチが接
続されたプロセッサと一致する場合、これをプロセッサ
に転送し、他のパケットの場合は、それを受信した部分
ネッワークと異なる部分ネットワークのなかで、その部
分ネットワークに対応する上記部分アドレスが、その交
換スイッチが接続されたプロセッサと異なる部分ネット
ワークに転送し、上記パケットに含まれるデータは、複数ビットから構成
される複数の部分データを有し、上記部分ネットワークは、複数のスイッチが多段に接続
され、上記部分ネットワークおよび交換スイッチを構成する各
々のスイッチは、前段および後段のスイッチにそれぞれ
接続され、前段のスイッチから、上記パケットを受信す
る手段を有し、上記受信手段は、上記複数の部分アドレスの個々の部分
アドレスはそのすべてのビットを並列に受信し、上記複
数の部分データの個々の部分データはそのすべてのビッ
トを並列に受信し、かつ、複数の部分アドレス、複数の
部分データを逐次的に受信し、各々のスイッチは、上記受信手段と次段の複数のスイッ
チの間に接続された経路選択手段を有し、該経路選択手段は、受信された複数の部分アドレスの個
々の部分アドレスはそのすべてのビットを並列に転送
し、また複数の部分データの個々の部分データのすべて
のビットを並列に転送し、かつ複数の部分アドレス、複
数の部分データを逐次的に転送し、各々のスイッチは、上記受信手段と経路選択手段に接続
された制御手段を有し、該制御手段は、上記部分アドレスのうちのあらかじめ決
められた１または複数のビットに応動して上記経路選択
手段を制御し、上記スイッチの少なくとも一部のスイッ
チに含まれる上記制御手段は、パケットの最初の部分ア
ドレスの到着に応動して残りの少なくとも１つ以上の部
分アドレスが到着する前に、該最初の部分アドレスの中
の予め決められた１または複数のビットをデコードして
上記経路選択手段を制御することを特徴とするデータ転
送ネットワーク。
【請求項８】複数のプロセッサを接続し、それら相互の
間でデータを転送するためのデータ転送ネットワークに
おいて、プロセッサ間のデータ転送は、送り先プロセッサのアド
レスまたはアドレスを示すタグと送達されるべきデータ
とを含むパケットの送受によって行なわれ、上記送り先プロセッサのアドレスまたはアドレスを示す
タグは、複数ビットから構成されるＤ組の部分アドレス
（Ｄは３以上の整数）から構成され、上記複数のプロセッサは、上記Ｄ組のうちのある組の部
分アドレスが同じものごとにグループ分けされ、データ転送ネットワークは、該グループ分けされた複数
のプロセッサをグループ内で相互に接続する部分ネット
ワークと、上記プロセッサの各々に１対１対応する複数
の交換スイッチを有し、該交換スイッチによって、各プ
ロセッサは、上記Ｄ個の組の部分アドレスに各々対応す
るＤ個の部分ネットワークに接続され、上記交換スイッチは、ある部分ネットワークから受信し
たパケットの送り先アドレスが、その交換スイッチが接
続されたプロセッサと一致する場合、これをプロセッサ
に転送し、他のパケットの場合は、それを受信した部分
ネットワークと異なる部分ネットワークのなかで、その
部分ネットワークに対応する上記部分アドレスが、その
交換スイッチが接続されたプロセッサと異なる部分ネッ
トワークに転送し、上記パケットに含まれるデータは、複数ビットから構成
される複数の部分データを有し、上記部分ネットワークは、複数のスイッチが多段に接続
され、上記部分ネットワークおよび交換スイッチを構成する各
々のスイッチは、前段および後段のスイッチにそれぞれ
接続され、前段のスイッチから、上記パケットを受信す
る手段を有し、上記受信手段は、上記複数の部分アドレスの個々の部分
アドレスはそのすべてのビットを並列に受信し、上記複
数の部分データの個々の部分データはそのすべてのビッ
トを並列に受信し、かつ、複数の部分アドレス、複数の
部分データを逐次的に受信し、各々のスイッチは、上記受信手段と次段の複数のスイッ
チの間に接続された経路選択手段を有し、該経路選択手段は、受信された複数の部分アドレスの個
々の部分アドレスはそのすべてのビットを並列に転送
し、また複数の部分データの個々の部分データのすべて
のビットを並列に転送し、かつ複数の部分アドレス、複
数の部分データを逐次的に転送し、各々のスイッチは、上記受信手段と経路選択手段に接続
された制御手段を有し、該制御手段は、上記部分アドレスのうちのあらかじめ決
められた１または複数のビットに応動して上記経路選択
手段を制御し、上記スイッチのうちの少なくとも上記交換スイッチは、
受信された複数の上記部分アドレスの転送順序を変更す
るための転送順序変更手段を有し、上記パケットがある
部分ネットワークから他の部分ネットワークに転送され
るときに、該他の部分ネットワークに含まれるスイッチ
の上記制御手段がその経路選択手段を制御するに必要な
部分アドレスを、受信したすべての部分アドレスのなか
で最初に転送することを特徴とするデータ転送ネットワ
ーク。