JPH02501183A - 層をなしたネツトワーク - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるため要約のデータは記録されません。

Description

【発明の詳細な説明】 をなしたネットワーク １員技１ 同時に問題の一部分を各々処理する複数のプロセッサにより構成されるシステム のデータ処理能力は、大きな処理能力の強力なコンピュータでも限界にきている 。プロセッサの有効な利用に対する主たる障害の１つは、プロセッサ間のコミュ ニケーションである。

多（のディジタルコンピュータにより構成されるシステムの重大な制限は、要求 される多量のコミュニケーションにある。実在する相互接続ネットワークは、非 常に高価であり、処理もおそく、また要求された接続パターンの小さな部分集合 だけを接続させている。

本発明の層をなしたネットワークは、非常に安いブロッキングネットワークから 、丈夫な、完全なルート割当を行うネットワークまで全範囲に渡る。システム設 計者は、システムの必要要件に基づいて層をなしたクラスの適切な部分を選択す ることができる。

従来の相互接続ネットワーク（ベースライン、バニアン等）は、中央ネットワー ク制御に関連した問題を避けるため分配するルート割当て機構を使用する。従来 のネットワークは、「リクエスト」のビットの１つにより、各々のスイッチを設 定することによって接続を確立する。リクエストは単に接続が行われるべきプロ セッサの数である。Ｎのプロセッサを備えるベースラインネットワークでは、ｌ ｏｇ、Ｎビットの各々が経路の大きさ２×２のｌｏｇｉＮスイッチの１つをセッ トするのに使用される。残念ながら、１つの完全な接続は、多くの他の存在を妨 げる。従って、２つのリクエストが１つのスイッチに同時に到着し、そして双方 が同じ端子を使用する必要があるとき「ブロッキング」が起る。層をなしたネッ トワークは、１以上のディジットからルートを選択することができ、その結果、 本来ならブロックされる接続に出力することができる。

つ及びフェン（Ｗｕ　ａｎｄ　Ｆｅｎｇ　）によって編集され、Ｉ　ＥＥＥコン ピューター協会より１９８４年に発行された「平行及び分配処理のための相互接 続ネットワークＪは、相互接続ネットワークにおける従来技術を表わした論文集 を含む、これ等の論文の中には、カンドル（Ｃａｎｔｏｒ）ネットワークを含む いくつかのネットワークを批評する「回路スイッチングネットワークのサンプル 」　（コンピュータ、１９７９年６月）がある。この論文は、カンドルネットワ ークが無閉そ（（ｎｏｎ−ｂｌｏｃｋｉｎｇ）である（即ち、任意の不使用入力 から任意の不使用出力への経路を見い出すことができる）という簡単な証明を述 べているが、ルート割当てアルゴリズムが一度に最適な１つのルートを割当てる ことができるとは、言及していない［第１５４頁ピッベンジャ−（Ｐｉｐｐｅｎ ｇｅｒ　）参照］。

クロスバ−スイッチ（つ及びフェンの第１４６頁参照）は、速い無閉そく方法で 接続できるが、その費用は接続されるプロセッサの数と共に急増する。つ及びフ ェンは、彼らの論文「逆変換相互接続ネットワークＪ　（ＩＥＥＥ）−ランスコ ンピュータ、１９８０年９月）において、ベースライン、オメガ、フリップ、バ ニアン等を含む研究した多（の相互接続ネットワーク間の機能的関係を示してい る。彼らはまた、これらのネットワークが行うことができる全ての可能な順列の 部分集合を確認している。つ及びフェンにより教示された位相幾何学上の順列は 、本発明の位相と共に、且つ他の実施態様を提供するために本発明の範囲内に使 用されてもよい。

カンドルネットワークと異なり、ベースラインネットワークは、高速ルート割当 てアルゴリズムを有しているが、これらは閉そく（ｂｌｏｃｋｉｎｇ）である。

つ及びフェン：ま、またベネス（Ｂｅｎｅｓ　）ネットワークについても論述し ている。ベネスネットワークは、全てのＮ階乗（Ｎり順列を行うことができる。

更に全ての順列が可能であり、はるかに少ない組合せであるルート割当てアルゴ リズムは、集中マトリクス操作を必要とする。要約すると、現在のネットワーク は高価であり（クロスバ−）、有効なルート割当てアルゴリズムに欠けている（ カンドール、ベネス）か、又は全ての順列及び組合せの作成が十分でない（ベー スライン）かのいずれかである。

クロスバ−スイッチ（第１図）は、その高速度、繰返し構造及び完全相互接続能 力のために、多くの従来の相互接続システムに使用されてきた。クロスバ−は、 基本的には、出力が入力に「従う（ｌｉｓｔｅｎ）　Ｊ単指向性の装置である。

各々の出力は矛盾な（、要求されるどんな入力にも従うことができる。そのクロ スバ−の完全な無閉そ（特性及び分配制御は、理想的標準として役立つ。しかし 、クロスバ−は、０（Ｎ２）程度のコスト高を示し、異なる傾聴者が同じ入力か らの異なる価値を受信する場合、特殊な放送操作を許さない。（（記号０　（Ｎ ”）は「程度の」を意味し、換言すると、Ｎ２に比例する値であり、この場合、 ｒＮＪはネットワークに接続した処理ノード（ｎｏｄｅ）の数である。）例えば 、「フエツチアンドオブ（Ｆｅｔｃｈ−ａｎｄ−ｏｐ）オペレーションは、大型 のマルチプロセシングシステムには有用である。

これらの制限は、第２図に示したオメガネットワークのような、ベースラインネ ットワークと位相幾何学的に等しいマルチステージ相互接続ネットワークに研究 者たちを導いた。従来のベースラインに同等なネットワークの中、第３図のバニ アンネットワークが本発明の層をなしたネットワークに最もよく類似している。

そのようなネットワークは、分配ルート割当てアルゴリズム、良好なコスト及び 呼出し遅延増加、及びサポート、フエツチアンドオブオペレーションを有してい るが、そのようなネットワークでの固有の閉そく特性が密に結合したプロセスの 性能には好ましくない不確定な遅延を課している。第４図のカンドルネットワー クは、そのＯ（Ｎ　ｌｏｇ２Ｎ）コスト高及びその簡単に試験できる無閉そく特 性のため有利である。しかし、そのようなネットワークに対するスイッチの設定 が比較的遅（、且つ適切に分配されない。

要求されるネットワークの性能の５つの対策は、完全相互接続、分配ルート割当 てアルゴリズム、最小呼出し時間、低コスト増加、特殊放送オペレーションのサ ポート（フエツチアンドオブのような）である。本開示の新しいクラスの層をな した相互接続ネットワークは、これらの基準を満足し、且つＯ（Ｎｌｏｇ”Ｎ） コスト増加を有する全てのＮ”相互接続パターンを提供できる。

同時コンピュータシステムにおいて、プロセッサ間のデータ交換のための、「層 をなした」ネットワークと呼ばれるマルチステージ相互接続ネットワークの新し いクラスが、本開示によって紹介されている。層をなしたネットワークは、ベー スラインネットワークと等価の高閉そくの従来のネットワークの代わりの方法を 提供する。

層をなしたネットワークは、従来よりもはるかに多いセットの接続を行う。層を なしたネットワークのサブクラスである「２進法の、完全に層をなした」ネット ワークは、分配スイッチのセツティングアルゴリズムを用いているクロスバ−で 全て接続可能であるが、より多くのプロセッサを有するシステムに拡大しても、 おそくなってコスト高であることを示している。

この開示のネットワーク（層をなしたネットワークと名付ける）は、マルチステ ージ相互接続ネットワークを具備する。

それはディジタルコンピュータ又は他の電子装置間の通信経路、同一スイッチ構 造及びスイッチセツティングを決定する分配方法を提供する。複数のディジタル コンピュータから構成されるシステムに課せられる重大な制限は、要求される多 量のコミュテーションにある。実在する相互接続ネットワークは、非常に高価で あり、処理もおそく、また要求された接続パクーンの小さな部分集合だけを接続 させている。このクラスの層をなしたネットワークは、非常に安いブロッキング ネットワークから、丈夫な、完全なルート割当を行うネットワークまで全範囲に 渡る。システム設計者は、システムの必要要件に基づいて贋をなしたクラスの適 切な部分を選択することができる。

以下余白 図面の簡単な説明 本発明の種々の特徴及び利点は、本発明の以下の詳細な説明及び添付図面を参照 して最もよく理解されるであろう。

第１図は従来技術の４×４クロスバ−スイッチネットワークのブロック図； 第２図は従来技術のベースラインネットワークのブロック図：第３図は従来技術 の逆方向バニアンネットワークのブロック図；第４図は従来技術のカンドールネ ットワークのブロック図；第５図は本発明の実施態様によって構成した２つの層 になったネットワークのブロック図； 第６図は本発明の実施態様によって構成した完全に層をなしたネットワークのブ ロック図： 第７図はネットワークのスイッチングステージのブロック図；第８図は本発明の 開示した実施態様に使用されるスイッチング回路の全ブロック図；そして 第９図乃至第２６図は第８図のスイッチング回路の実施の詳細ブロック図である 。

１凱久説コ 本開示の贋をなしたネットワークは、それらの間にポイント対ポイント接続を有 する多（のスイッチにより構成されている。そのネットワークは、スイッチを通 り「リクエスト」を中継することによりリクエスターからレスボンダーへの接続 を確立する。各々のスイッチはリクエスト及びレスポンスを送出するためにビル トインコントロール論理を備えている。そのスイッチ設定は、リクエストと、ネ ットワーク内のリクエストの現在位置との比較を用いることで決定する。各々の スイッチは、リクエストに含まれる情報のみを使用してリクエストを送出し、集 中コントローラなしで分配されるルート割当てを規定するために送出する。その スイッチ設定は、関連するリクエストと同じ経路上であるが、逆方向のレスポン スを送出するように記憶される。

層をなしたネットワークは、スイッチが次のステージの単一のｂの（ｂ−ａｒｙ ）ディジットを除いて、同じスイッチ番号を有する他のスイッチに信号を送出で きるように構成されている。リクエストは所望のレスポンスポートを示している ｂの数を含む。スイッチは、リクエストをスイッチ番号と比較する。比較したｂ のディジットが同じであれば、リクエストは直線に送出されるが、同じでなけれ ばリクエストはリクエスト内のディジットに適合する他のスイッチに送出される 。ネットワークの終端では、リクエストはスイッチ番号が正確にリクエストに適 合するｌｏｇ１Ｎ番目のステージのスイッチに達しなければならない。開示した 実施態様では、２進デイジツトが用いられる。

典型的な相互接続ネットワーク（ベースラインに同等な）は、集中ネットワーク 制御に関連した問題を避けるために、分配されるルート割当て機構を用いる。典 型的ネットワークは「リクエスト」内のビットの１つによって各々のスイッチを セットすることにより接続を確立する。リクエストは単に接続されるべきプロセ ッサの数である。Ｎプロセッサを備えるベースラインネットワークでは、１ｏｇ ｚＮビットの各々がその経路のサイズ２Ｘ２の１ｏｇｚＮスイッチの１つをセッ トするのに用いられる。残念ながら、１つの完全な接続は、多（の他の接続の存 在を妨げる。従って、１つのスイッチで２つのリクエストがともに同じ端子を使 用する必要があるときに、「閉そ＜　（ｂｌｏｃｋｉｎｇ）　Ｊが起る。他方に おいて、層をなしたネットワークは１以上の接続から選択すればよい、そして典 型的なベースラインに同等なネットワークによってブロックされたリクエスト及 びレスポンスを送出できる。

３つのパラメータ（Ｎ・・・ネットワークに接続されたプロセッサの数、ｂ・・ ・対数のベース及び数表示、Ｐ・・・ネットワーク内に接続する「平面」の番号 ）が層をなしたネットワークを規定する。層をなしたネットワークにおける平面 は、スイッチ設定でのコンテンションを減少する追加の経路を供給する。Ｎ＝３ ２、ｂ＝２、Ｐ＝２を持つ層をなしたネットワークの全体的概略が第５図に示さ れている。

その層をなしたネットワークは、スイッチが単一のｂの（ベースｂ）ディジット を除き、同一のスイッチ番号を持つ次のステージにおいて他のスイッチに信号（ リクエスト又はレスポンスデータ）を送出できるように構成されている。Ｎ＝８ 、Ｐ　＝　１ｏｇＪ％ｂ＝２を有する層をなしたネットワークが第６図に示され ている。

スイッチ設定アルゴリズムは、そのスイッチを使用するこれらの接続だけに関す る情報を要求する。各々のスイッチは、分配されたスイッチ設定を許容する同一 のステージ内のスイッチ間で情報交換することなく独立にセットされる。そのス イッチは、スイッチ番号を有する所望のレスポンスポートを示すｂの番号である リクエストと比較する。比較したｂのディジットが同じデータであれば、リクエ ストは直線に送出され、同じでなければ、リクエスト内のｂのディジットに適合 する他のスイッチに送出される。ネットワークの終端では、リクエストは、スイ ッチ番号がリクエストに正確に適合する１０ｇｂＮ番目のステージでスイッチに 達しなければならない。

層をなしたネットワークを操作する他の方法は、ハミング距離の構想を利用する ことである。２進法の場合、ｂ＝２であり、２つの番号間のビット差の量である 。各々のビットは、等しい有意の他の番号のビットと比較され、そして異なるビ ットがカウントされる。

同様に、２よりも大きいｂに対しては、ハミング距離ｄは、第２の番号ｔ　（ｄ ＝ｒ″ｘｏｒ″ｔ）の振幅で排他的論理和による番号ｒの振幅だけ異なるｂのデ ィジットの量である。リクエストに対するハミング距離は、所望のレスポンスポ ート（リクエストと呼ばれる）を示す番号を示しているスイッチ番号と比較する ことによって計算される。リクエストのハミング距離がゼロに等しければ、リク エストはスイッチ番号に等しい。最終ステージのスイッチは、入力番号がスイッ チ番号に合っているレスポンスポートに接続される。

リクエストが最終ステージのスイッチに達し、そしてハミング距離ゼロを有して いれば、それは所望の接続にうまく送出された。そのステージは、もう１つのｂ のディジットに適合する次のステージにおけるスイッチにリクエストをスイッチ することにより、リクエストが伝播されるので、リクエストのハミング距離を減 少する。ｂ＝２、Ｐ　＝　１ｏｇｂＮのとき、全てのＮ”　リクエストがうまく ルートをセットする。

１９７８年４月１１日にフレミング（Ｆｌｅｍｉｎｇ　）等に発行され、且つ本 発明の譲受人に譲渡された「■適合コンテントアドレス可能なメモリ」と題する 米国特許第４．０８４．２６０号のシステムが、本発明に適応されるハミング距 離回路を示している。その米国特許は参照により本願に包含される。特許第４． ０８４．２６０号の回路を本発明に適応するために、この特許のサーチワードレ ジスタが、スイッチ番号の補数の２進表示を受けとり、ベストマツチワードレジ スタがプロセッサアドレスを受けとり、サーチファイルレジスタが連続して他の プロセッサアドレスを受けとる。スイッチ番号の補数が使用されるので、マツチ レジスタにおける最後のワードは、最小距離よりもむしろ、最大ハミング距離を 有するプロセッサアドレスである。

最大ハミング距離を有するアドレスはファイルから除かれ、そのプロセスは、最 大ハミング距離に対する第２のアドレスを得るために残りのサーチファイルレジ スフプロセッサアドレスを用いて繰返される。このプロセスは、全てのリクエス トがハミング距離により指令されるまで繰返される。

リクエストターミナル番号は、ラベルとしてアドレスした各々のプロセッサに送 られなければならない。しかし、リクエスト番号はハミング距離計算に含まれて いない。

五又Σ２二之頂立 この章で規定したネットワーク構造は、層をなしたネットワークのための注釈上 の基礎を提供する。この章は、スイッチのサイズ及び作成、使用又は技術に関係 のないそれ等の相互接続を論する。

３つのパラメーター（Ｎ・・・プロセッサの数、ｂ・・・対数のベース。

Ｐ・・・平面の数）が層をなしたネットワークを特定する。使用されるスイッチ は、ｂ＊Ｐ入力、及びｂ＊Ｐ出力を有していなければならない、この場合水は乗 法を示している。層をなしたネットワークはＮ　＊　（ｌｏｇｌ、Ｎ　＋　１　 ）の同じスイッチを使用する。プロセッサの数Ｎはｂの整数倍でなければならな い（Ｎ＝ｂ″、　ｎ＝：ｌｏｇｂＮ）。そのスイッチが入力数の２乗に比例する コストを有すると仮定すると（クロスバ−に言えるように）、全ネットワークコ ストは、Ｎ＊（ｌｏｇゎＮ＋１）＊　（ｂ＊Ｐ）”に比例する。スイッチは、ス テージ当りＮスイッチを有するステージと呼ばれる縦列に配列される。

従って、ｌｏｇｂＮ　＋　１ステージがネットワークを形成するために接続され る。層をなしたネットワークは、所望により高パーセントの有効なルート割当て を得るためにベースライン型ネットワークのように縦列接続（ｃａｓｃａｄｅ　 ）できる。

各々の対称（リクエスト端子、レスポンス端子、ステージ、スイッチ、及びスイ ッチング又はネットワーク端子）は、形式名称、すなわち、識別子（パラメータ ーのリスト）を有している。ステージは、ステージ番号が０からｌｏｇｂＮの範 囲の場合、ステージ（ステージ番号）によって表わされる。スイッチは、スイッ チ番号がＯからＮ−１の範囲にあたる場合、スイッチ（ステージ番号、スイッチ 番号）によって表わされる。スイッチ端子は、平面番号が０からＰ−１及びディ ジット番号が０からｂ−１の場合、「圧側の」端子に対して（「右側の」端子に 対しては代わりにＳｗＴｅｒｍＲ）　ＳｗＴｅｒｍＬ（ステージ番号、スイッチ 番号、平面番号、ディジット番号）によって表わされる。

全ての層をなしたネットワークは、スイッチ配線を決定するために同じ接続フオ ーミュラを使用する。パラメーターＮ、ｂ及びＰが層をなしたネットワークの型 式を規定する。下記の構成手順の限定が贋をなしたネットワークを生じる。

ｃｌ）プロセッサーの数、Ｎ、対数ベース、ｂ、及び平面の数、Ｐを選ぶ、ｂ＊ ｐ左側端子を有するスイッチサイズ及びｂ＊Ｐ右側端子を決定する（本は「乗法 」を意味する）。（端子は１以上のワイヤ又はカップリングより成っていればよ い。）ｃ２）ステージ番号が０から１０ｇ１．Ｎまでの範囲にある場合、ステー ジ（ステージ番号）を表わすスイッチのｌｏｇｂＮ　＋　１ステージを確立する 。

ｃ３）スイッチ番号がＯからＮ−４までの範囲にある場合、スイッチ（ステージ 番号、スイッチ番号）を表わす各々のステージ内にＮスイッチを置く。

ｃ４）下記により、各々の右側スイッチ端子を左側スイッチ端子に接続する： ＳｗＴｅｒｍＲ（ステージ、スイッチ、平面、ディジット）　−１３ｗＴｅｒｍ Ｌ（ステージ＋１、スイッチ、平面、ディジット）；　ここで、ｅｆｐｌ＝（平 面＋１ｏｇｂＮ　−１−ステージ）　ＭＯＤｌｏｇｂＮ　；有効平面であれば、 ｄｉｒ＝（スイッチＤＩＶｂ””）ＭＯＤｂ　。

ＳＷ＝スイッチ＋（（ディジット＋ｄｉｇ）ＭＯＤｂ）＊ｂ””；ｃ５）それぞ れＲｅｓ　（入力番号）、Ｒｅｑ（出力番号）を示す、ネットワークの右側のＮ レスポンス端子、及び左のＮリクエスト端子を確立する、この場合入力番号及び 出力番号は０からＮ−１の範囲である。スイッチはプロセッサからのリクエスト によりセットされる。「ネットワークへの入力」は到着したリクエストに応対し 、そして所望のデータを提供する。

ｃ６）下記により、リクエスト端子をスイッチの「第１の」縦列に接続する。

Ｒｅｑ　（出力番号）　−３＊ＴｅｒｍＬ　（０、出力番号、０，０）ｃ７）下 記により、レスポンス端子をスイッチの「最後の」縦列に接続する。

Ｒｅｓ　（入力番号）　−３ｗＴｅｒｍＲ（１ｏｇｂＮ　、入力番号、ｌ　（入 力番号ＤＩＶｂ’−”）ＭＯＤｂ）。

これが縦列接続することな（層をなしたネットワークの厳しい規定を完成する。

縦列接続したネットワークは、上記のようにスイッチのいくつかのセットのステ ージを有している。しかし、層をなしたネットワークは、単一のセットのステー ジでも非常に強力であるから縦列接続は僅かな追加の接続性を提供する。

下記のこれ等のネットワーク構造のルールによって入力及び出力ボート間の連絡 ワイヤのパターンは、Ｎ、ｂ、及び各々の選択に対して確立される。例えば、第 ５図においてＮ＝３２、ｂ＝２そしてＰ＝２の場合、２つの相互接続パターンが あり、その中の１つは、２本のワイヤにより隣接する縦列内の同じ番号のスイッ チに接続されている縦列内の各々のスイッチにより作成されている。（これは図 の水平ラインによって図示されている）。他のパターンは残りのワイヤによって 作成される（これは図の傾斜したラインにより図示されている）。（Ｐの値は１ つのパターンにおける水平ワイヤの数及びスイッチの１縦列から隣接する縦列へ の他のパターンにおける傾斜したラインの対応する数を示している。）第６図に おいて、Ｎ＝８、ｂ＝２及びＰ＝３の場合、１つの相互接続パターンは１縦列の スイッチから隣接する縦列の同じ番号のスイッチへの３つの水平ラインによって リクエストされる。他のパターンは残りの傾斜したワイヤによって作成される。

従って、２つの相互接続パターンはＮ及びｂの関数であり、これは上記のネット ワーク構造ルールｃ１乃至ｃ７によって確立される。

ム工ヱ孟股Ｉ 新規なスイッチの接続に加えて、スイッチ設定アルゴリズム自身が層をなしたネ ットワークの特色である。層をなしたスイッチの簡単な意図はクロスバ−であり 、それはその入力のいかなる順列又は組合せをもその出力に接続することができ 、スイッチをセットするために機構に結合される。

層をなしたネットワークスイッチは同時に最大ｂ＊Ｐリクエストにおいて受けと る。スイッチに対する各々のリクエストのハミング距離が計算される。最大の距 離を有するリクエストがｂ＊Ｐ端子の１つを選択し、それが、そのような端子が 存在すれば、その距離を減少する。従って、他のリクエストが減少するハミング 距離順序で端子を選択する。この方法では、最大「相関関係」を必要とするこれ 等の信号がその距離を減少するために端子選択において優先権を有している。

リクエストのルート割当ては、少なくともレスポンス端子のパラメータより成っ ているリクエストを出力する各々のリクエスト端子で始まる。追加のビットは、 メモリアドレス、フェッチアンドオブ（ｆｅｔｃｈ−ａｎｄ−ｏｐ）パラメータ 、誤りコードビット、又はハンドシェイクラインを表わす。ＩＪＵ上のレスポン ス端子がリクエスト端子に接続されるにすぎないが、いかなる数のリクエストボ ートも単一のレスポンス端子に接続してもよい０層をなしたネットワークのルー ト割当ては、下記のステップにより達成される：ＳＬ）必要なとき各々のリクエ スト端子がらりクエストを発する。

Ｓ２）上記のルールｃ６によりリクエストな０番目のステージスイッチに送信す る。

Ｓ３）ステージの各々のスイッチに対して下記を繰返すことによりスイッチのス テージをセットする。

５３ａ）同じリクエストと１に結合。その組み合せを記録する。

５３ｂ）各々のリクエストのハミング距離を決定する。

５３ｃ）下記によって右側の端子に割当てる：１）大きなハミング距離を備えた 信号が端子選択において優先権を有する。

２）１以上のリクエストは同じ端子に割当てることができない。

３）ハミング距離を減少する最上位の（最も高い番号の）有効な平面を使用する 。有効な平面、　ｅｆｐｌ＝　（平面＋ｌｏｇｂＮ　−１−ステージ）　Ｍ　Ｏ Ｄ　１層ｇｂＮ　−４）そのリクエストが、その有効平面が距離を減少すれば端 子を選択し、そしてリクエストにおける対応するディジットに適合する「ディジ ット」を選ぶ。

５）最低番号の有効平面上に、直線接続に使用するのに好ましい任意の端上に前 のステップによって割当てることができないいくつかのリクエストを置く。

８３ｄ）リクエストを、上記Ｃ４で作った接続を経て次のステージに送信する。

Ｓ４）全ての残りのステージに対してＳ３を繰返す。

Ｓ５）リクエストを１層ｇｂＮ番目のステージから上記の０７で作った接続を経 てレスポンス端子に送信する。

これで層をなしたネットワークが送出される。スイッチによるリクエストルート 割当ての適切な記憶により、レスポンスは、その経路に従い、しかも、反対方向 に、リクエスト端子に戻ることができる。

轡　に　をなしたネットワーク 完全に層をなしたネットワークは、Ｐ　＝　ｌｏｂ、Ｎを有する層をなしたネッ トワークである。１ｏｂｂ　Ｎ平面は、スイッチ一番号がゼロ又は１のハミング 距離だけ異なる次のステージ内のいかなるスイッチへのリクエストにもルート割 当てを許容する。２進の、完全に贋をなしたネットワークは、ネットワークコス ト式に、ｂ＝２及びｐ＝１ｏｇｚＮを代入することによって決定した反復的定義 （ｒｅｃｕｒｓｉｖｅｄｅｆｉｎｉｔｉｏｎ）でないＮ　ｌｏｇ”　Ｎ程度のコ スト増加を有している。Ｎ＝８、ｂ＝２及びｐ＝３を有する２進の完全に層をな したネットワークが第６図に示されている。端子の２乗に比例するコストを有す るクロスバ−であると予め仮定したスイッチが、贋をなしたネットワークによっ て置き換えられると、コストはＮ　＊　ｌｏｇ”Ｎ　＊　ｌｏｇｌｏｇ”　Ｎの 程度に下降する。

２進の完全に贋をなしたネットワークの無量そ＜　（ｎｏｎ−ｂｌｏｃｋｉｎｇ ｌ特性の下記の証明及びアルゴリズムは、リクエストとスイッチ番号との間のハ ミング距離がリクエストがネットワークを通り送られるとき、０に減少すること を立証している。最後のステージにおけるリクエストとスイッチ番号との間のＯ のハミング距離は、ルート割当てが終了したことを暗示している。以下の頁に対 して、ｌｏｇ　Ｎは１０ｇｔＮを指す。

明らかに、信号が全てのステージにおいて有用な端子（ハミング距離を減少する ）を選択できれば、出力番号とリクエストとの間のｌｏｇ　Ｎビット差はｌｏｇ 　Ｎステージで変化できる。しかし、端子選択における相反するリクエストの「 パンピング（ｂｕｍｐｉｎｇ）　Ｊは、全ての信号が全てのステージで（それら のハミング距離を減少することによって）役立たせることができないことを意味 する。２つのリクエストが同じＳｗＴｅｒｍＲを選んだ時、「バンブ」がスイッ チ設定中に起こる。ルールＳ３ｃによって、１つのリクエストがその選択をされ ると、他のリクエストは、残りの端子に「バンブ」される。その証拠は、いかな るバンブした信号もネットワークの後のステージにより分解されるのに十分小さ い距離を持つことを示している。その証拠は、５番目のステージ後、ハミング距 離（ｄ、、、）を有するリクエストの数が最大１ｏｇＮ−ｊにあることを示して いる。

バンブされるために、リクエストの異なるビットを処理する全ての端子は、等し い又はより大きい距離を有するリクエストによって要求されなければならない、 従って、順次平面選択におけるｇ番目のリクエストがバンブされると、その距離 ｄ１０、は、ｇよりも少なくなる。ｒｄｒ、ｔＪは、リクエストｒと、期間ｔと の間のハミング距離である。ｒもｔもｌｏｇ　Ｎビットで表わされる範囲（［Ｏ ，、Ｎ−１］）を有する。ｄｒ、ｔに対する値は、範囲［０，、ｌｏｇ　Ｎｌを 有する。

リクエスト端子は０番目のステージ、ネットワーク端子の０番目の平面に接続さ れる。１つのリクエストのみがスイッチの第１のステージの平面選択によって処 理されるから、バンブは起きない。

更に、ｄ　ｒ、　ｔ　＝　ｌｏｇ　Ｎを有するこれ等の信号は０番目の平面を選 択しなければならないから、これが有効平面が１ｏｇＮ−１である平面である。

従って、第１のステージ後、いかなるリクエストの最大距離もｌｏｇ　Ｎ　−１ であり、そしてこれ等のリクエストが０番目の平面を占める。同様に、５番目の ステージ後、１ｏｇＮ−ｊの最大距離を有する全ての信号が、ｊ−１番目の有効 平面を占める。距離ｌｏｇ　Ｎ−ｊを有する１つの信号のみが、各々の平面選択 スイッチのためのｊ＋１番目のステージの始めに存在し、より少ない距離の信号 の他の量もまた制限される。最大距離を有するいかなる信号も、平面の第１の選 択を得て、その信号をその宛先の近くにもたらす。従って、５番目のステージ後 、いかなる信号の最大距離も１ｏｇＮ−ｊである。ｌｏｇ　Ｎ番目のステージ後 、最大距離はゼロである。

２准の、。　に　をなしたネットワークのルートアビリイテイ■匹印旦旦公り この章は、どのようにして上記のルート割当てアルゴリズムが２進の、完全に層 をなしたネットワークを送出するかを示している。

ルート可能なネットワークは、全てのルートが同時に選択される同時プロセッサ システムに十分である。無量そ（の通例の定義、現存の接続を妨げることなくい かなる接続をも送出する能力は、同時に全てのリクエストを送出しようとするネ ットワークに関係がない。重要なことは、ネットワークが（ｌｏｇＮ）時間程度 で送出できることである。（カンドル（Ｃａｎｔｏｒ）ネットワークは無量そ（ であるが、ここで使用されている用語の意味において「ルート可能」ではない。

） ２進の、完全に層をなしたネットワークは、右の端子２１ｏｇＨによって２１ｏ ｇＮ左の端子を有するスイッチにより成っている。その構造は単一の接続及び端 子を論じているが、その経路はＷワイヤが必要である、この場合、Ｗはデータ経 路の幅である。ｙ、＋＝ｌは直列接続であり、一方、ｗ　＝　１ｏｇｔＮはワー ド並列である。

Ａ）全てのスイッチは、それ等のスイッチ番号において何番目の平面ディジット のみだけ異なるスイッチに接続する端子上にリクエストを置くことができる。

任意のスイッチ、Ｓ（ステージ、スイッチ）を考える。ルールｃ４により、右の スイッチ端子ＳｗＴｅｒｍＲ（ステージ、スイッチ、平面、ディジット）は、左 のスイッチ端子ＳｗＴｅｒｍＬ　（ステージ＋ｌ。

Ｓ、Ｗ、、平面＋　ｄｘｇ　）に接続される。この場合、平面＝　［０，。

１ｏｇＮ−１］、ディジット＝　［０，、１］　、　ｅｆｐｌ＝　（平面＋ｌｏ ｇ　。

Ｎ−１−ステージ）　ＭＯＤｌｏｇ　ｔ　Ｎ、　ｄ　ｉ　ｇ＝　（スイッチＤＩ Ｖ２””）　ＭＯＤ　２　、そしてｓｗ＝スイッチ＋（（ディジット−ｄｉｇ） ＭＯＤ２）＊２　”ｐｌ、スイッチ一番号の差、ｓｅ−スイッチ＝（（ディジッ ト−ｄ　１　ｇ）　Ｍ　ＯＤ　２　）　＊２　”ＰＬｅ従って、ｓｗ及びスイッ チはｅｆｐ１番目のビットを除き同一であり、且つｌのハミング距離を有してい る。

Ｂ）リクエストが特定のステージにおいてルール８３ｃにバンブしなければ、リ クエストのハミング距離はｌだけ減少する。

リクエストが、ルール８３ｃにより、従って、上記のＡによりその異なるビット の１つに適合する平面を得れば、リクエストはｅｆｐ１番目のディジットが変化 される端子に移動する。従って、ｅｆｐ１番目のディジットはもはや差がな（、 次のステージにおけるその新スイッチへのリクエストのハミング距離は１だけ減 少される。

Ｃ）平面選択中、平面に割当てられたｇ番目の信号が選択バンブ（ｓｅｌｅｃｔ 　ｂｕｍｐ　）すれば、ｇ＞ｄ、、ｔである。

バンブするｇ番目の信号に対する唯一の方法は等しい、又は大きい距離のリクエ ストに対して距離を減少できるｄ、、を平面の全てを要求することである。従っ て、より大きい又は等しい距離のｇ−１リクエストがｄ　ｇ、　を端子をクレー ムし、且つｇｏｄ、、ｔでなければならない。

Ｄ）ステージｊスイッチ及びいくつかの任意の距離ｄ１．えに対するバーリング バンブ（ｂａｒｒｉｎｇ　ｂａｍｐ）　Ｔ距離ｄｒ、を又はより大きいｋを有す る単一のスイッチにおけるリクエスト数はに＝ｌｏｇＮ−ｊ＋１　ｄｒ、ｔに制 限される。

第１のステージ後、ネットワーク組立て部分の０６により各々のスイッチに対す る１つの信号のみにより、各々のリクエストはルール５３ｃ３により最上位ビッ トの差の平面を選択した。出力においてｄ　ｒ、　ｔ　＝　ｌｏｇ　Ｎを有する これ等の信号は、それ等がビット毎に異なるので、ｌｏｇ　Ｎ　−１番目の有効 平面を占めなければならない。

各々のステージにおいて、ｄ　ｒ、　ｔ　＝　ｌｏｇ　Ｎ　−Ｊの最大距離を有 するリクエストは全て、リクエストがネットワークを下方に進むに従って同じ有 効平面（ｌｏｇ−ｊ−１番目）を選択する。同様に、ｄｒ、ｔ＝１ｏｇＮ−１で スタートするリクエストは、ルール５３ｃ３により有効平面ｌｏｇ　Ｎ　−１又 はｌｏｇＮ−２のいずれかを選択し、そして最大の２つの平面において占有し続 けなければならない。量大距離信号が含まれるので、ｄ　ｒ、　ｔ　＝　ｌｏｇ 　Ｎ　−ｊを有する信号の全可能な数はに＝２である。より少ない距離のリクエ ストに対しても、その特性はｋ＜ｌｏｇ　Ｎ−ｊ＋１−ｄ、、ｔのような最大に 信号において割当て（ａｌｌｏｗｉｎｇ）を保持する。

Ｅ）バンブに対するいかなるリクエストに対しても、それはハミング距離ｄ、、 ｔ＜　（ｌｏｇ　Ｎ−ｊ＋１）／２を有していなければならない。

上記のＣでは、バンブに対してｇ＞ｄｇ、ｉ−Ｄではｓｄｒ、ｔを有する最大に 信号において、ｋ　＜　＝　ｌｏｇ　Ｎ　−ｊ＋　１−　ｄ　ｒ、　ｔのようで ある。ｇ＝ｒ＝ｋを選ぶ。するとｄ、、ｔ＜ｇ＜＝ｌｏｇ　Ｎ−ｊ　＋　１−ｄ ア６、。従って、ｄｌｏ、＜　（ｌｏｇ　Ｎ−ｊ＋１）／２である。

Ｆ）ｌｏｇＮ−ｊ又は１ｏｇＮ−ｊ−１のいずれかの距離を有するステージｊに 入るリクエストはバンブしない、且つそれ等の距離を１だけ減少する。

上記のＣでは、ｇ番目のリクエストがバンブすれば、ｇ　＞　ｄ　、、ｔである 。Ｅでは、ｄ　ｔ、　ｔ　＜　（ｌｏｇ　Ｎ−，３＋　１　）　／　２である＊ ｄｒ、ｔ＝１ｏｇＮ又は１ｏｇＮ−ｊ−ＩＫを有するリクエストは、（１ｏｇＮ −ｊ＋１）／２より少ないことはないから、それ等はバンブしない。

上記のＢでは、リクエストの距離は１だけ減少する。

Ｇ）　ｌｏｇ　Ｎ番目のステージ後、全てのリクエストはｄ、、、＝Ｏを有する 。

上記のＦでは、ステージｊ後、いかなるリクエストの最大距離も１ｏｇＮ−ｊで ある。ｊ＝ｌｏｇＮのとき、ｄ、、ｔ＝Ｏである。

Ｈ）最終ステージが適当な入力からの情報を得る。

上記のＧでは、最終ステージ、即ちネットワーク構造の意のルールｃ７の前に、 全てのリクエストは、ネットワーク端子が所望の入力に適合することを意味する ゼロ距離を有している。最終ステージは、リクエストをルール５３ｃ５及びｃ４ によりゼロ番目の有効平面に送出して、ルールｃ７からの入力との接続を完成す る。

ルート　（Ｒｏｕｔａｂｉｌｉｔ シュミレーションを使用した層をなしたネットワークの調査は初めに、相互接続 の定義及びルート割当てアルゴリズムを決定し、且つ改良することである。シュ ミレーションにおける完全に層をなしたネットワークの観察により、ルート能力 立証の形式化となった。興味あることには、ｂ＝３又は４を有する完全に層をな したネットワークがシュミレーションにおいて完全に全てのパターンを送出した が、ｂ＝５又はそれより大きいネットワークでは送出しなかった。シュミレーシ ョンでは、ｐ＝２を有する層をなしたネットワークがｐ＝ｌを有するネットワー ク（これは非常にベースライン等価ネットワークに類似している）よりも実質的 に僅かな不完全な接続を示した。ｐ＝２及びｂ＝２を有する２つの完全に層をな したネットワークは、シュミレーションにおいて縦列接続されたとき、全ての接 続がうま（送出された。

フェッチアンドアト（ｆｅｔｃｈ−ａｎｄ−ａｄｄ　）リクエスト結合を使用す る２つの平面を有する眉をなしたネットワークは、ベースラインに同等なネット ワークに比べて「ホットスポット（ｈｏｔ−ｓｐｏｔ）　Ｊコンテンションを実 質的に減少させていると信じられている。従って、層をなしたネットワークは、 密に接続された同時システムに要求されるような、急速な、自由な通信を提供す る。２進の、完全に層をなしたネットワークはクロスバ−の全てのＮＮ接続を作 成するが、（ｌｏｇ　Ｎ）ステージ程度であり、（Ｎｌｏｇ”Ｎ）程度のコスト 増加を有している。２千面の層をなしたネットワークは単一平面のネットワーク よりも実質的に多いセットの許容し得る接続を有することが期待される。

第５図及び第６図のネットワークは、好ましくは同一のスイッチ（第７図）より 構成される。各々のスイッチチップは、スイッチの各々の側に４つの平行なボー ト間でリクエストとレスポンスを送出する自己設定ゲートを形成する。処理ノー ド（ｎｏｄｅ）がリクエストを出力し、これが所望するメモリ位置を含むノード に送出される。

それからノードは、メモリから所望するワードを引き出し、レスポンスが初めの リクエストと同じ経路に従ってネットワークを通り再び中継される。リクエスト 及びレスポンスは、新リクエストをノードクロックと同じ周期の２５ナノ秒のネ ットワーククロック周期で１５０ナノ秒毎に、全てのノードから発し得るネット ワークを通りパイプラインで送られる。

各々のネットワークスイッチは単一の３０にゲー）、ＣＭＯＳ。

ＶＨＳＩＣスケールチップとして構成される。各々のリクエストは順方向経路及 びレスポンス経路の双方の上の各々のスイッチを通り伝播するために、３つの２ ５ナノ秒クロックサイクルを取る。従って、チップ変更せずに１０２４プロセツ サまでを有するシステムを相互に接続するのに使用できる。チップは１０２４プ ロセツサ以上を扱うように容易に変更される。スイッチは、システムの利用性を 高めるために誤り検出器及び故障防止器を組み入れてもよい。

ネットワークは、同一の４×４の自己設定スイッチより成っている。そのネット ワークは、リクエスト及びレスポンス２つの形式の入力／出力端子を有している 。このシステムの各々の処理ノードは各々に１つ有している。プロセッサがリモ ートメモリをアクセスしようとするとき、それは、そのリクエスト端子上に４つ のサイクル「リクエスト」を発する。第１の２つのサイクルはノード及びメモリ アドレスを含み、第２の２つのサイクルはスワップ（ｓｗａｐ）又はフェッチア ンドアトパラメータを保持する。リクエストは、ネットワークを横切ってアドレ スしたノードのレスポンス端子に送信される。アドレスしたノードが所望のメモ リを取り出し、データはネットワークを通り最初のリクエストボートに再び中継 される。フェッチアンドアト及びスワップオペレーションは、メモリセルを付加 分に変更するために読出し後、書込みのため受信ノードな要求する。

リクエスト及びレスポンス端子は、全てのノードにおいてネットワークインタフ ェースチップによって管理される。ネットワークインタフェースチップがリクエ ストを初期設定し、レスポンスを取出し、そして取出しくｆｅｔｃｈ　）メモリ 位置を適切に変更する。

２層型（ｔｗｏ−１ａｙｅｒｅｄ　ｖｅｒｓｉｏｎ　）は、可能な接続の丈夫な セットを提供し、現在、ＶＨ３ＩＣ−スケール１．２５ミクロン及び利用可能な パッケージング技術を用いて構成できるので、いくつかの応用に対して完全に層 をなしたネットワークより利点を有している。６４の処理ノードに対するネット ワークは、各々６４チツプの７ステージに配置した４４８の同じＣＭＯＳチップ より成っている。このスイッチは、２つの平面と１０２４までの２のベキ乗に等 しい、処理ノード数Ｎとを有する層をなしたネットワークに必要な機能性（ｆａ ｎｃｔｉｏｎａｌｉｔｙ　）を実行する。スイッチは単一のＶＬＳ　Ｉチップで 占めている。スイッチは、リクエスター側に、４つの「入力」と、レスボンダー 側に４つの「出力」とを有している。各々の入力及び出力は、適切な制御信号と 共に増加した１６ビツト両方向兼用の並列経路より成っている。スイッチは、ネ ットワークを通りパイプライン波（ｐｉｐｅｌｉｎｅｄ　ｗａｖｅ）の中に、こ れらのリクエストに対するリクエスト及びレスポンスを送出する。

各々のスイッチは、その左の端子でリクエストを受信し、それは次にそのスイッ チ設定及びパラメータ変更を計算し、適切な右の端子にリクエストを送り、レス ポンススイッチ設定及び適切なフェッチアンドアト（又はフェッチアンドオプ） 又はスワップパラメータを記録する。最後に、右の端子にレスポンスを受信した とき、それがスイッチ設定及びパラメータをリコールし、多分変更されたレスポ ンスを適切な左の端子に送信する。

これ等のスイッチは特定のスイッチハンドル（ｓｗｉｔｃｈ　ｈａｎｄｌｅｓ） を、リクエストに含まれた情報のみを用いて並列にセットされる。

４つのリクエストまでが同時に任意の特定のスイッチに達する。各々のリクエス トは、その誤りコードをチェックされ、いかなる誤りリクエストも中継されない 。２又はそれ以上のリクエストが同じ宛先の処理ノード、メモリアドレス及びオ ペレーションを有していれば、これ等は結合される。フェッチアンドアトリクエ ストはパラメータを加えることにより結合される。スワップリクエストはパラメ ータの１つを選び、それを送ることによって結合される。宛先ノードは合ってい るが、オペレーション又はメモリアドレスが合わない全ての他の事情においては 、１つのリクエストが他に優先する。一旦スイッチ設定が決定されると、リクエ ストはスイッチの次のステージに送信される。スイッチ設定はリクエストのルー ト割り当て中記憶されるので、レスポンスは、ネットワークを通り同じ経路を、 しかし最初の設定をリコールすることによって逆の方向に従う。

層をなしたネットワークは共同作動の一致を容易にするために、２つのオペレー ション、フェッチアンドアト及びスワップを備えている。フェッチアンドアトオ ペレーションはジョブスケジューリング及びデータフローバッファに使用される 待ち行列を管理するのに使用できる。スワップオペレーションは、動的データ構 造に使用されるポインタの変更を可能にする。フェッチアンドアトオペレーショ ンは、多（のプロセッサをして、同時に同じメモリ位置で「読取り、それから加 える（ｒｅａｄ　ａｎｄ　ａｄｄ）　Ｊを可能にし、且つオペレーションがあた かもいくつかの逐次順序で起ったかのようにレスポンスを受信可能にする。フェ ッチアンドアトは、ジョブキューポインタを同時にいく人かの使用者によって参 照可能にし、且つ各々のプロセッサに異なるジョブポインタを提供する。スワッ プオペレーションは、動的シェアド（ｄｙｎａｍｉｃ　５ｈａｒｅｄ）データ構 造に使用されているポインタの操作を可能にする。

フェッチアンドアトオペレーションは、指示したメモリ場所の値に戻すが、フェ ッチアンドアトパラメータをそれに加えることによってメモリに残された値を増 加する。メモリ場所がキューポインタとして使用されると、各々のフェッチアン ドアトレファレンスは、異なる値を戻す。このネットワークは任意の又は全ての 処理ノードをフェッチアンドアトオペレーションと同時に同じメモリ場所にアク セス可能にし、各々のノードは、あたかもフェッチアンドアトオペレーションが いくつかの逐次順序で起ったかのように、戻った全（別の値を得る。この特性は 、多くのプロセッサをジョブキューに同時にアクセス可能にし、そして、その結 果、全てのプロセッサを最小のオーバーヘッドでとジーに保つ。同様に、多くの 読み書き（ｍａｎｙ　ｒｅａｄｅｒ　−ｍａｎｙ　ｗｒｉｔｅｒ　）データフロ ーキューは、いくつかの処理ノードによって同時にアクセスされる。メモリの簡 単な読取りは、ゼロのパラメータを有するフェッチアンドアトによって達成され る。

スワップオペレーションは、指示したメモリ場所の値に戻るが、メモリ内の値を スワップパラメータで置き換える。このスワップオペレーションはポインタの操 作のため意図されている。例えば、単連結（ｓｔｎｇｌｙ−１ｉｎｋｅｄ　）リ スト内への記録の挿入は、記録のポインタ上でスワップオペレーションを行い、 その後、新しい記録が挿入される。スワップパラメータは新しい記録のためのポ インタであり、そして戻った値が、リストを続けるために新しい記録内のポイン タに書込まれる。スワップオペレーションは、任意の又は全ての処理ノードを同 時に同じメモリ場所にスワップ可能にし、且つあたかもスワップオペレーション がいくつかの逐次順序で起きたかのように戻った値を得るために、ネットワーク に結合される。スワップオペレーション結合は、任意の数の処理ノードを同時に 同じリスト内への新しい記録の挿入を可能にする。

スイッチオペレーションの 第７図に示したように、ネットワークスイッチは、リクエスターの方に４つの左 の端子と、レスボンダーの方に４つの右の端子と、配線による（ｈａｒｄ　ｗｉ ｒｅｄ）パラメータと、い（つかのクロックと、保守用インタフェースとを有し ている。リクエストは左の端子で受信され、リクエストパラメータを適切に変更 して右の端子に送出される。レスポンスは右の端子で受信され、初めのリクエス トルート割当てについて記憶した情報を用いることで変更した左の端子に送出さ れる。

リクエストは、スイッチ設定に使用される情報を含む。リクエストはそれ等のノ ードアドレス、メモリアドレス及びリクエストのタイプによって結合され、延期 され（ｄｅｆｅｒ　）　、又はスイッチされる。レスポンスは、関連するリクエ ストによってアドレスされたメモリ場所に配憶される多分変更されたワードを含 む。レスポンスは、それ等の関連したリクエストが結合されれば変更してもよい 。

リクエストパラメータから計算され、記憶されたレスポンスパラメータは、リク エストが結合されたならばレスポンスに加えらえる。

更に、レスポンスは関連したリクエストが１つに結合されたならば２又はそれ以 上のレスポンスに分けられる。

フェッチオン、フェッチアンド、フェッチマルチブライのようなフェッチアンド モディファイ（Ｆｅｔｃｈ−ａｎｄ−Ｍｏｄｉｆｙ）がスワップオペレーション と共に使用されるので、従って、パラメータはそれ等の関連するリクエストによ って変更される。リクエストが結合されるときパラメータ変更が、同時処理の一 致に必要な同時オペレーションの見掛は連続化（ｓｅｒｉａｌｉｚａｔｉｏｎ　 ）を支持する。

スイッチ２０の左及び右のスイッチ端子は、４つのグループのワイヤで構成され ている。各グループのワイヤは、１６のデータワイヤと、２つの誤りコードワイ ヤと、３つの制御ワイヤとを含む。

ワイヤは全て両方向兼用に使用される。左のスイッチ端子がリクエストを受信し 、レスポンスを送信する。リクエストは４つのクロックサイクルでドライブされ る。第１の２つのサイクルはノード宛先及びメモリアドレス情報を含み、第２の ２つのサイクルはフェッチアンドアト又はスワップパラメータを含む。レスポン スは更に２つのサイクルで同じワイヤ上を反対方向にドライブされる。ネットワ ークのどのスイッチもこれ等の６つの交換を平行して行う。従って、新しいリク エストは６クロツクサイクル毎に任意の又は全ての処理ノードからのネットワー クインタフェースから発せられる。

第７図に示した４つの左の端子及び４つの右の端子の各々は２１０両方向兼用ラ インから成っている。つまり、１６のデータ、２つのチェックコード、そして３ つのトランザクションタイプである。

１５のチップビンが配線によるパラメータに使用されている。２つのビットビッ クチョイス（Ｂｉｔ　Ｐｉｃｋ　Ｃｈｏｉｃｅ　）の各々に対して４゜このチッ プの適切なアドレスビットに対して２．及びスライダオフセットに対し５である 。これ等のチップビンは、システム初期化のときセットした計算状態（ｃｏｎｆ ｉｇｕｒａｔｉｏｎ　）レジスタでもよい。

７つのクロックがチップによって使用される。４０ＭＨｚシステムクロック及び データの６つのシステムクロックサイクルルート割当てにコーディネートする６ つのトランザクションフェーズクロックである。７つのクロックは、４０ＭＨｚ システムクロックと６のフェーズを得るための同期クロックの２つでもよい。

リクエストのためのノード及びメモリアドレスは、２つの受信リクエストクロッ クが能動であるとき、１つのスイッチの右のネットワーク端子から次のステージ のスイッチの左のネットワーク端子に移される。リクエストに対するパラメータ （フェッチアンドアト又はスワップ）は、２つの受信パラメータクロックが能動 であるとき、同じ方向に次のシステムサイクルに移される。最後に、リクエスト に対するレスポンスは、２つの送信レスポンスクロックが能動であるとき、反対 方向に再びリクエスターに移される。６つのトランザクションクロックがスイッ チ間に整然とデータの移動を保証する。

トランザクションはチップを通りバイブラインされるが、トランザクションクロ ックの各々が能動であるときスイッチの作動について説明するよりもむしろ個々 にオペレーションの３つの部分（２つの３セツト）について説明する方が容易で ある。ノードアドレス。

メモリアドレス及びリクエストタイプを含むリクエストのスイッチングをまず説 明する。リクエストに含まれる情報は、リクエスト、パラメータのスイッチング 、そして結局レスポンスを決定するのに使用される。次にスイッチング及びパラ メータの可能な変更について説明する。最後に、レスポンスのスイッチング及び 可能な変更について説明する。

スイッチは、受信リクエストフェーズが能動であるとき、その左のネットワーク 端子上で４つのリクエストまでを同時に受信する。

２つの１６ビツトデータフイールドは、１０ビツトのノードアドレス及び２２ビ ツトのメモリアドレスと解釈される。リクエストはフェッチアンドアト又はスワ ップのいずれかのタイプを有している。

同じノードアドレス、メモリアドレス及びタイプを有するリクエストは単一のリ クエストに結合される。各々のノードが単一のボートメモリを含むので１つのメ モリアドレスのみが一度にアクセスされる。従って、同じノードアドレスである が、異なるメモリアドレスを有する２つ（又はそれ以上）のリクエストは結合で きない、従って、１つのリクエストのみ、他方が延滞したときに次のステージに 移される。メツセージの結合又は延滞（ｄｅｆｅｒｒａｌ）のためのルールは下 記の通りである。

１、ノード及びメモリアドレスが等しく、且つそれ等のタイプがフェッチアンド アトである全てのリクエストをフェッチアンドアトが結合する。

２、ノード及びメモリアドレスが等しく、且つそれ等のタイプがスワップである 全てのリクエストをスワップが結合する。

３．２つ（又はそれ以上）のリクエストが等しいノードアドレスを有しているが 、異なるメモリアドレスであるとき、遥小のメモリを有するリクエストを除き全 てが延滞される（ｄｅｆｅｒ　）。

４．１つ（又はそれ以上）のスワップリクエストがフェッチアンドアトリクエス トと同じノードアドレスを有していれば、フェッチアンドアトリクエストは延滞 される。

５、データ経路上にチェックコード誤り又はタイプ上にパリティ誤りを有するい かなるリクエストも自動的に延滞される。

６、選択が行われなければ、小さい左の端子ナンバーを有するリクエストをとる 。

リクエストが他のリクエストに結合されるか、又は他のリクエストによって延滞 される（ｄｅｆｅｒ　）とき、組み合せ又は延滞は、終局の結果のスイッチング が決定されるように指示される。延滞されない又は他に結合されない全てのリク エストは端子のクレームのために使用可能にされる。

リクエストが右の端子をクレームできる前に、どの端子が役立つかが決定されな ければならない。スイッチは、リクエストを次のステージに対する接続の２つの 「平面」のいずれかの上に置（ことができる。第５図及び第６図の平面の各々が リクエストのノードアドレスの１ビツトに対応している。スイッチは、リクエス トのいずれかの平面上の「直線」又は「クロス」端子上に置いてもよい。直線端 子は、同じスイッチ番号を有する次のステージのスイッチに接続する。クロス端 子は、単一ビット、平面に対応するビットを除き、同じスイッチ番号を有する次 のステージのスイッチに接続する。

平面に対応するビットは２つの配線による４ビツトバラメークによりチップのた めに識別される。これ等の２つのビットは、各々のリクエストのノードアドレス から抽出される。これ等のビットは、配線されているスイッチ番号の２つのビッ トと比較される。リクエストの抽出ビットが対応す宕ハードストラップされたビ ットと異なれば、その平面上のクロス端子がリクエストをアドレスしたノードに 接近させる。クロス端子のいずれか有用な方が右の端子をクレームするのに使用 される。

各々の使用可能なリクエストに対しては、いずれの（若しあれば）クロス端子が 有用であるかに基づいて、異なる右の端子がクレームされる。同時に全てのクレ ームを行うために、特殊な論理構造が考案されていた。端子フレーミングに対す るルールは下記の通りである。

１．直線よりもクロス端子を、平面０よりも平面１の方をクレームするのがよい 。

２、誤り制御の意で示したように、機能不全スイッチに接続したいかなる端子も クレームしてはならない。

３、全てその他が等しければ、低いナンバーの左の端子上のリクエストが優先権 を有する。

４、所望のクロス端子がクレームされれば、利用可能な直線端子を使用する。直 線端子が利用できなければ、平面Ｏを利用するのは有用でなくてもクロス端子を 使用する。

一旦右の端子がクレームされると、スイッチ設定が決定されなければならない。

１セツトの４つの加算ツリー（ａｄｄｅｒ　ｔｒｅｅ）がルート割当て及び結合 に使用される。各々の加算ツリーが、４つのリクエストの任意の又は全てのデー タフィールドを加算するのに選択できる。リクエストがスイッチされると、加算 ツリーが単一のセレクタのように作用する。各々のツリーは右の端子の１つに結 合される・各々のツリーが右の端子をクレームするリクエストを選択し、それに ゼロを加算する。最後に、リクエストは次のステージのため右の端子上に送信さ れる。

受信パラメータフェーズが能動であるとき、各々のリクエストに従うリクエスト パラメータは多少異なって送出される。使用されるべき右の端子は既に決定され ている。しかし、２又はそれ以上のリクエストが結合されれば、パラメータが加 えられる。

全てのフェッチアンドアト結合リクエストのパラメータが、結合リクエストのた めのパラメータを形成するために加えられる。リクエストがスワップ結合される とき、最低ナンバーの左の端子からのパラメータが選択される。

リクエスト及びパラメータルート割当てに加え、加算ツリーは、レスポンスが受 信されるとき、使用されるレスポンスパラメータを計算するのにも使用される。

スイッチに結合されたフェッチアトアトリクエストに対するレスポンスは、リク エストがあたかも逐次に起きたように、各々の結合したリクエストがデータを得 るように変更されなければならない。記憶したパラメータは、レスポンスのルー ト割当て中レスポンスに加えられる。パラメータは、低いナンバーの左の端子か ら来る全てのフェッチアンドアト結合リクエストパラメータの合計である。

スワップリクエストが結合されるとき、パラメータの一方は、他方が蓄えられて いる間に送られる。レスポンスを受信すると、そのレスポンスは変更されずにリ クエストの１つに送られ、一方、他方が他のスワップ結合リクエストの１つのリ クエストパラメータを受けとる。各々の結合リクエストに対するスワップパラメ ータは、次の最大の左の端子から来るリクエストのパラメータ、又はこれが最大 であればゼロである。

１ｏｇＮ＋１スイッチを通過後、リクエスト及びそれ等のパラメータは所望のノ ードに達する。メモリ場所が取出され、その値がレスポンスとしてネットワーク 上に戻される。レスポンスは、送信レスポンスが能動であれば、左の端子から前 のステージの右の端子に移される。各々のスイッチは、シフトレジスタのように 作用するよう形成されたファイル内にパラメータ及びレスポンススイッチ設定を 保持する。スライダーと呼ばれるファイルが、見掛はシフトレジスタの長さを決 定するために、ステージディレィ　（ｓｔａｇｅ−ｄｅｌａｙ）と呼ばれるパラ メータを使用する。この値は、ネットワークの右側に対するほぼステージ数であ るように配線されている。（正確な式のスがその右の端子からのスイッチ内にラ ッチされるとき、そのスライダーは、必要なパラメータ及びレスポンススイッチ 設定を自動的に提供する。

レスポンススイッチ設定及びレクエストルート割当て中に、計算され、且つスラ イダに記憶されたレスポンスパラメータは、リクエストが結合されたか、延滞さ れたか、あるいは変更されずスイッチされたかによって変化する。レスポンスス イッチ設定がレスポンスデータワードの１つ又は記憶したパラメータに加えられ るべきゼロを選択する。更に、レスポンスに関連したタイプは選択されるか、あ るいは、リクエストが延滞されたことを示すタイプによって代えられる。レスポ ンススイッチ設定を支配するルールは下記のようである。

１、非結合、非延滞（ｕｎｄｅｆｅｒｅｄ）リクエストは、そのリクエストがレ スポンスデータワード及びタイプに送出（ｒｏｕｔ）された端子を選択する。加 えられるべきレスポンスパラメータはゼロである。

２、フェッチアンドアト結合リクエストは、結合リクエストがレスポンスデータ 及びタイプに送出された端子を選択する。加えられるべきレスポンスパラメータ は、低ナンバーの左の端子から来る全ての結合リクエストの合計である。

３、スワップ結合リクエストは、結合リクエストがタイプのみに送出された端子 を選択する。最高ナンバーの左の端子から来るリクエストがレスポンスデータワ ードを選択し、そしてゼロレスポンスパラメータを加える。

全てその他は、次の最高ナンバーの左の端子からの記憶したレスポンスパラメー タであるレスポンスパラメータに加えられるべきゼロを選択する。

４、延滞したリクエストは、ゼロ選択パラメータに加えられるべきゼロを選択し 、戻されるべき「ネットワークコンフリクト（ｎｅｔｗｏｒｋｃｏｎｆｌｉｃｔ ）　Ｊタイプに押し込む。

変更される可能性のあるリクエストタイプ及びデータワードは、送信レスポンス フェーズが能動であるとき、との端子から送信される。

要約すると、ネットワークスイッチは、６つの２５ナノ秒クロックサイクルでス イッチを通り、リクエスト及びレスポンスを送出（ｒｏｕｔｅ）する。このスイ ッチはフェッチアンドアト、又はスワップリクエストに結合し、そしてレスポン スを分ける。リクエスト結合は、多くの処理ノードを同じメモリ場所にフェッチ アンドアト又はスワップ可能にし、あたかもリクエストの各々が逐次起きたよう にレスポンスを受信する。最も重要なことは、リクエスト及びレスポンスが各々 の方向に各々のスイッチを横切るのに３クロツクサイクルしか必要としないので 、ネットワーク待ち時間が低（、リクエスト及びレスポンスがネットワークを通 りパイプラインされているのでスルーブツトが高く、新しいリクエストが１５０ ナノ秒毎に全ての処理ノードから発することができる。

奔出ムロ　なリクエスト 層をなしたネットワーク相互接続の主たる特徴は、個々のリクエストに対すると 同じネットワーク送信時間で、レスボンディングノードにおいて全体として満足 できる結合リクエスト内にコンパチブルリクエストを結合するその能力である。

この効果の最も簡単な実施例は放送読取り（ｂｒｏａｄｃａｓｔ　ｒｅａｄ）で ある。この場合、いくつかのプロセッサが同時に同じメモリセルの読取りをたま たまリクエストする。放送内に含まれる各々のスイッチが１又はそれ以上のその ようなリクエストを送信すべき単一のリクエストに結合し、一致（ｃｏｉｎｃｉ ｄｅｎｃｅ）の発生を記憶する。読取りデータが戻るとき、スイッチがそれを初 めの入って来るリクエストの各々にコピーする。

同じ原理がもつと複雑なリクエストに適用できる。肝要な必要条件は、リクエス トがいかなる順序でも結合可能であり、その結合が単一のリクエストで表わすこ とができることである。そのようなリクエストが与えられると、それ等はメモリ 場所を含むネットワーク又はノードのいづれかに時間のかかる衝突（ｃｏｎｆｌ ｉｃｔ）なく共用（ｓｈａｒｅｄ）メモリ場所に加えられる。そのような場所を 指示するプログラムは、いかなる順序でも発生してそれ等を処理するように作成 されなければならない。これがマルチタスキングの本質である。

更に、ネットワーク及びノードメモリは、等個直列順序（ｓｅｒｉａｌｏｒｄｅ ｒ）％即ち、メモリセル及びすべてのタスクに同じ結果値を生ずるオペレーショ ンのいくつかの直列順序があることを保証する。

リクエストの結合は、メモリ読出し及び書込みを容易に明示できる。「フェッチ アンドアト（ｆｅｔｃｈ−ａｎｄ−ｏｐ）　Ｊと呼ばれる算術及び論理演算の類 が文献に記載されている。［ＭＩＭＤ　ｒ共用メモリコンピュータに関する問題 ：　ＮＹＵウルトラコンピュータアプローチ、コンピュータ構造に関する第１２ 回定例シンポジウムＪ　１９８５年第１２６頁参照］。それは、メモリセル内容 がＡＤＤ又はＡＮＤのような結合的オペレーションによって変更されるオペレー ションを規定している。変更前にメモリセルの値がリクエスターに戻される。

スワップオペレーションがメモリセル内容をリクエストの供給したデータに代え て、メモリセルの原の内容に戻す。結合リクエストに対して等化直列順序を保証 することはネットワークにとって簡単であるが、このオペレーションは結合的で はない。非結合性は、スワップオペレーションに使用するソフトウェアが、可能 な異なる発注（ｏｒｄｅｒｉｎｇ）を処理するために作成されなければならない ことを意味する。

結合可能なリクエストの動機づけは、高位の（ｈｉｇｈ　ｏｒｄｅｒ）言語（Ｈ ＯＬ）におけるタスク中変数を共有する問題から来ている。共有変数（Ｓｈａｒ ｅｄ　Ｖａｒｉａｂｌｅ）に同時にアクセスしようとする多くの、多分測子とい うタスクがあれば、それ等は性能にひどい影響を与えずに継続的に起こり得ない 。従って、出願人は、すべての共有変数は結合可能なオペレーションにのみ関連 づけられなければならない。

待ち時間及びスルーブツトが共同システムの重要な必要条件である。新しいリク エストは、６クロツクサイクル毎、又は１５０ナノ秒毎に発することができるの で、６．６ミリオンのリクエストを発することができ、レスポンスが毎秒各々の ノードによって受信できる。６４ノードシステムでは、このネットワークは１秒 当り５３ピリオンのビットを運ぶことができる（ボート当り４０　Ｍ　Ｈｚ　＊ ６４ノード＊２１ビット）。ネットワークのスルーブツトはプロセッサの数と共 に直線的に増大するが、ネットワーク待ち時間は加えたノードと共に対数的に増 大する。メツセージの待ち時間（リクエスト発生からレスポンス受信までの時間 ）は、リクエストルート割当て（ｒｏｕｔｉｎｇ）　、メモリアクセス、及びレ スポンス戻りの合計である。６４−プロセッサシステムは７つの（ｌｏｇ　Ｎ＋ １）縦列のスイッチを有しており、各々の縦列がリクエスト及びレスポンスルー ト割当てのために遅延の１ネツトワーク（全部で６クロツクサイクル）を課せら れている。

メモリ取出しくｆｅｔｃｈ）が１５０ナノ秒で行うことができれば、６４処理ノ ードシステム（２つがネットワークプラスメモリアクセスを通過する）に対する 全待ち時間は、１２００ナノ秒である。

ネットワークによって提供される優れた待ち時間及びスルーブツトが、加えるプ ロセッサによって得られる処理パワーを有効に利用するのに必要な高速通信を可 能にする。

層をなしたネットワークに対する下記のチップ明細書は、ビン接続、フオーメイ テイング（ｆｏｒｍａｔｔｉｎｇ）、タイミング及びリクエストが結合され、デ コムバイン（ｄｅｃｏｍｂｉｎｅ）され、そして送出される（例えば、フェッチ アンドアト及びスワップオペレーションの使用によって）方法を説明している。

層をなしたネットワークのスイッチチップ明細書１、入出力ビンリスト概要 Ａ、データ Ｂ、チェックビット Ｃ，コマンドタイプ Ｄ、クロック（３００） Ｅ、配線による制御 Ｆ、リセット（６１１） Ｇ、パワー、グラウンド Ｈ１保守ボート（テスト）、誤り報告（６３７）２、リクエスト　フォーマット ３、レスポンス　フォーマット ４、タイプ　フォーマット ５、ハンドシェイク　フォーマット ６、クロック　フォーマット ７、配線による制御ビン Ａ、　ＥＦＰＬＯ（３３０）　、　ＥＦＰＬＩ　（３３１）Ｂ、　ＤＩＧＩＴＯ （３３２）　、　ＤＩＧＩＴＩ　（３３３）Ｃ，５ＴＡＧｊＤＥＬＡＹ　（６１ ０）８、リセット（６１１） ９、パワービン必要要件 １０、保守ボート（テスト）−誤り報告１１、機能 Ａ、結合リクエスト、デコムバイニングレスポンスＢ、ルート割当てリクエスト Ｃ１戻り経路の記憶及び記憶したレスポンスパラメータＤ、誤り検出 １２、配線による制御ビンセツティングのための３２ノ一ド例１、入出力ビンリ スト概要 全ビンカウントは、パワー及びアースを含めて２１３である。

８セツトの２１ビツト端子がある。ネットワークの前のステージに接続するため に左に４セツト、そしてネットワークの次のステージに接続するために右に４つ ある。

Ａ、データ。ターミナル当り１６ビツト、合計１２８．ビンタイプは入出力。

データラインは、アドレス、パラメータ及びレスポンスデータの送信及び受信に 使用される。

左のネットワークデータ端子Ｏとして読取り、ビット０〜１５ＬＨＮＴＤＴＯ［ ０・・１５］　（３０７Ａ）ＬＨＮＴＤＴＩ　［０・・１５］　（３０７Ｂ）Ｌ ＨＮＴＤＴ２　［０・・１５１　（３０７Ｃ）ＬＨＮＴＤＴ３　［０・・１５］ 　（３０７Ｄ）右のネットワークデータ端子０として読取り、ビット０−１５Ｒ ＨＮＴＤＴＯ［０・・１５］　（５４６Ａ）（平面０直線を表わす）ＲＨＮＴＤ ＴＩ　［０・・１５］　（５４６Ｂ）（平面Ｏクロスを表わす）Ｒ）ＩＮＴＤＴ ２　［０・・１５］　（５４６Ｃ）（平面１直線を表わす）ＲＨＮＴＤＴ３　［ ０・・１５］　（５４６Ｄ）（平面１クロスを表わす）Ｂ、チェックビット、端 子当り２ビツト合計１６゜ビンタイプチェックビットはそれぞれのデータポート ＭＯＤ３を表わす。

左のネットワークチェックコード端子Ｏとして読取る。ビット０、ｌ。

ＬＨＮＴＣＣＯ［０・・１］　（３０８Ａ）ＬＨＮＴＣＣＩ　［０・・１１　（ ３０８Ｂ）ＬＨＮＴＣＣ２［０・・ｌ］　（３０８Ｃ）ＬＨＮＴＣＣ３［０・・ １１　（３０８Ｄ）右のネットワークチェックコード端子０として読取る。ビッ ト０．１゜ ＲＨＮＴＣＣＯ［０・・１］　（５４７Ａ）（平面Ｏ直線を表わす）ＲＨＮＴＣ ＣＩ　［０・１１　（５４７Ｂ）　（平面０クロスを表わす）ＲＨＮＴＣＣ２［ ０−１］　（５４７Ｃ）　（平面１直線を表わす）ＲＨＮＴＣＣ３［０・・１］ 　（５４７Ｄ）（平面１クロスを表わす）Ｃ，コマンドタイプ。端子当り３ビツ ト合計２４．ビンタイプは入出力。

コマンドタイプは、２ビツトのコマンドタイプと１ビツトの奇数のパリティとか ら成っている。ビット２はパリティビットである。

タイプビットは誤りがネットワークに生じたとき、ネットワークのステージ間の ハンドシェーク及び誤りコードのリクエストタイプを制御するのに用いられる。

左側のネットワークタイプ端子０として読取る。ビットｏ、１゜２゜ ＬＨＮＴＴＹＯ［０・・２］　（３０９Ａ）ＬＨＮＴＴＹＩ　［０・・２］　（ ３０９Ｂ）ＬＨＮＴＴＹ２　［０・・２］　（３０９Ｃ）ＬＨＮＴＴＹ３　［０ ・・２］　（３０９Ｄ）右側のネットワークタイプ端子Ｏとして読取る。ビット ０，１゜２゜ １（）ＩＮＴＴＹＯ（０・・２］　（５４８Ａ）（平面０直線を表わす）ＲＨＮ ＴＴＹＩ　［０・・２］　（５４８Ｂ）（平面０クロスを表わす）ＲＨＮＴＴＹ ２　［０・・２］　（５４８Ｃ）（平面１直線を表わす）Ｒ１（ＮＴＴＹ３　［ ０・・２］　（５４８Ｄ）（平面１クロスを表わす）Ｄ、クロック　７クロツク がある。ビンタイプは入力。

ＣＬＯＣＫ　（３００）　（ネットワークシステムクロック）ＲＣＶＪＥＱＪ　 （３０１）（リクエスト受信−第１半部）ＲＣＶ−ＲＥＱＪ　（３０２）　（リ クエスト受信−第２半部）ＲＣＶｊＡＲＡＭＪ　（３０３）（パラメータ受信− 第１半部）ＲＣＶＪＡＲＡＭＪ　（３０４）（パラメータ受信−第２半部）ＲＣ Ｖ−ＲＥＳＰＪ　（３０５）　（レスポンス受信−第１半部）ＲＣＶＪＥＳＰＪ 　（３０６）　（レスポンス受信−第２半部）Ｅ、配線による制御。１５の制御 ビンがあり、ビンタイプは入力制御ビンは、それがネットワーク内にある場合ス イッチを言う。

ＤＩＧＧＴＯ（３３２）有効何番目平面のスイッチナンバーＤＩＧＧＴＩ　（３ ３３）有効何番目平面のスイッチナンバーＥＦＰＬＯ［０・・３］　（３３０） 平面Ｏに対する有効平面ＥＦＰＬＩ　［０・・３］　（３３１）平面１に対する 有効平面５ＴＡＧＥ、−ＤＥＬＡＹ　［０・・４］　（６１０）スライダに対す る書込み。

読取りカウンタオフセット。

Ｆ、　ＲＥＳＥＴ　（６１１）　１リセツトビン。ビンタイプは入力Ｇ、パワー グラウンド。合計１２又はそれ以上、ビンタイプはパワーパッド。

Ｈ０保守ボート（テスト）−誤り報告（６３７）。１０ビン２、リクエストフォ ーマット 初期のノードからのリクエストは、４つの部分に分けられる必要がある。スイッ チチップが制（卸クロックフェーズ（ＲＣＶ−ＲＥＱＪ　（３０１）等）の負エ ツジ（ｎｅｇａｔｉｖｅ　ｅｄｇｅ　）上のラインをサンプルする。スイッチチ ップの左端子を調べる必要がある。

ＲＣＶＪＥＱｊ　（３０１’）　： Ｎ０ＤＥ　ＡＤＲＳ　端子の１０ビツト［６・・１５］ＭＥＭＯＲＹ　ＡＤＲＳ 端子の６（メモリアドレスの最上位ビット）ビットＣＨＥＣＫ　２ ＲＣＶＪＥＱＪ　：　（３０２） ＭＥＭＯＲＹ　ＡＤＲＳ　１６　（最下位ビット）ＴＹＰＥ　３ ＣＨＥＣＫ　２ ＲＣＶｊＡＲＡＭ−、Ａ　（３０３）　：ＰＡＲＡＭＥＴＥＲ１６（最下位ビッ ト）ＨＡＮＤＳＨＡＲＥ　３ ＣＨＥＣＫ　２ ＲＣＶ−ＰＡＲＡＭＪ　（３０４）　：ＰＡＲＡＭＥＴＥＲ１６（最上位ビット ）ＨＡＮＤＳＨＡＲＥ　３ ＣＨＥＣＫ　２ リクエストは、最上位ハーフファースト（ＲＣＶ−ＲＥＱＪ　、３０１）を、パ ラメータハ、ｆｆｉ下位ハーフ　７７’−ス）　（ＲＣＶ−ＰＡＲＡＪＡ　、３ ０３）を有する。リクエストは、正しいルート指示をするために最上位ノ１−フ ファーストが必要である。パラメータは、２半部に渡って加算するために最下位 ハーフファーストが必要である。

リクエストの立上り部分は、各々のスイッチチップを通過するために３クロツク フエーズをとる。従って、情報は下記の時間中、右の端子に現われる。

ＲＣＶ−ＰＡＲＡＭＪ　（３０４）　：Ｎ０ＤＥ　ＡＤＲ３端子の１０ビツト［ ６・・１５コＭＥＭＯＲＹ　ＡＤＲ３端子の６（メモリアドレスの最上位ビット ）ビットＣＨＥＣＫ　２ ＳＮＩｌｊＲＥＳＰＪ　（３０５）　：ＭＥ卜！ＯＲＹ　ＡＤＲ３ｌ　６　（最 下位ビット）ＴＹＰＥ　３ ＣＨＥＣＫ　２ ＳＮＪＲＥＳＰＪ　（３０６）　： ＰＡＲＡＭＥＴＥＲ１６（最下位ビット）ＨＡＮＤＳＨＡＫＥ　３ ＣＨＥＣＫ　２ ＲＣＶＪＥＱＪ　（３０１）　： ＰＡＲＡＭＥＴＥＲ１６（最上位ビット）ＨＡＮＤＳＨＡＫＥ　３ ＣＨＥＣＫ　２ 上記のフェーズは、次のステージの左の端子が期待するものと整合しないので、 各々のステージに対するクロックフェーズを調べるために別々に割当てなければ ならない。６つのクロックフェーズがあり、チップを通過するのに３フエーズを とるから、全ての他のステージは同じフェーズ割当てを有することがわかる。同 じライン上にある下記の入力ビンは、同じクロックフェーズを受信しなければな らない。

Ｓｔａｇｅ　ＯＳｔａｇｅ　Ｉ　Ｓｔａｇｅ　２　Ｓｔａｇｅ　３　Ｓｔａｇｅ 　＝ＲＣＶ−ＲＥＱＪ　＝　ＲＣＶＪＡＲＡＭＪ＝　ＲＣＶ−ＲＥＱＪ　＝　Ｒ ＣＶ−ＰＡＲＡＭＪ＝　・・・ＲＣＶＪＥＱ−Ｂ　＝　５ＮＤ−ＲＥＳＰＪ　＝ 　ＲＣＶ−ＲＥＱＪ　＝　５ＮＤＪＥＳＰＪ　＝　・・・ＲＣＶ−ＰＡＲＡＭＪ ＝　５ＮＤＪＥＳＰＪ　＝　ＲＣＶＪＡＲＡＭＪ＝　５ＮＪＲＥＳＰＪ　＝　− ・・ＲＣＶＪＡＲＡＭ−Ｂ＝　ＲＣＶＪＥＱＪ　＝　ＲＣＶｊＡＲＡＭＪ＝　Ｒ ＣＶＪＥＱＪ　＝　−・・５ＮＤＪＥＳＰＪ　＝　ＲＣＶ−ＲＥＱＪ　＝　５Ｎ ＤＪＥＳＰＪ　＝　ＲＣＶＪＥＱＪ　＝　−・・５ＮＤ−ＲＥＳＰＪ　＝　ＲＣ Ｖ−ＰＡＲＡＭＪ＝　５ＮＤ−ＲＥＳＰＪ　＝　ＲＣＶｊＡＲＡＭＪ＝　・・・ 例えば、Ｓｔａｇｅ　ＯのＲＣＶ−ＲＥＱ−Ａ　（３０１）で示した入力ビンは 、Ｓｔａｇｅ　１のＲＣＶ−ＰＡＲＡＭ−Ｂ　（３０４’）で示した入力ビンと 同じクロックフェーズを受信しなければならい。

３、レスポンスフォーマット レスポンスは、下記のクロックフェーズの間、左の端子から前のステージに送信 される。

５ＮＤＪＥＳＰＪ　（３０５）　： ＲＥＳＰＯＮＳＥ　ＰＡＲＡＭ　１６　（最下位ビット）ＴＹＰＥ　３ ＣＨＥＣＫ　２ ＳＮＤ−ＲＥＳＰＪ　（３０６）　： ＲＥＳＰＯＮＳＥ　ＰＡＲＡＭ　１６　（最下位ビット）ＴＹＰＥ　３ ＣＨＥＣＫ　２ 隣接するステージのクロックフェーズは、別々に割当てられるから、右の端子が 下記のフェーズの負のエツジ上のレスポンスをサンＲＣＶＪＥＱＪ　（３０２） ： ＲＥＳＰＯＮＳＥ　ＰＡＲＡＭ　１６　（最下位ビット）ＴＹＰＥ　３ ＣＨＥＣＫ　２ ＲＣＶＪＡＲＡＭＪ　（３０３）： ＲＥＳＰＯＮＳＥ　ＰＡＲＡＭ　１６　（最上位ビット）ＴＹＰＥ　３ ＣＨＥＣＫ　２ ４、コマンドタイプ コマンドタイプは３ビツトより成っている。２つの最下位ビットがコマンドタイ プを示し、最上位ビットは奇数パリティに対してである。これ等のタイプは ビット：２１０ １　（００１）フェッチアンドアト ２　（０１０）スワップ ４　（１００）リクエストネットワーク衝突（ｃｏｎｆｌｉｃｔ）なし５、ハン ドシェイクフォーマット ステージ間でのハンドシェイキングはタイプライン（３０９Ａ−Ｄ、５４８Ａ− Ｄ）上で起こる。起こり得るハンドシェイク状態は４　（１００）リクエスト受 信 ７　（１１１）誤り検出 ハンドシェイクは、ＲＣＶ−ＰＡＲＡ］Ａ　（３０３）及びＲＣＶ−ＰＡＲＡＭ −８（３０４）の間、左の端子によって前のステージに出力され、５ＮＤＪＥＳ ＰＪ　（３０６）及びＲＣＶ−ＲＥＱ−Ａ　（３０１）　（７）負ノエッジ上で 右の端子により次のステージからサンプルされる。

６．クロックフォーマット ３００　ＣＬＯＧＫ　０１０１０１０１０１０１０１０１０１０１０１０１０１ ０１０１０１０１０１０１０１３０１　ＲＣＶＪＥＱＪ　０１１０００００００ ０００１１００００００００００１１００００００００００１１０３０２　ＲＣ ＶＪＥＱＪ　０００１１００００００００００１１００００００００００１１０ ０００００００００１３０３　ＲＣＶｊＡＲＡＭＪ　０００００１１０００００ ０００００１１００００００００００１１０００００００００３０４　ＲＣＶｊ ＡＲＡＭＪ　０００００００１１００００００００００１１０００００００００ ０１１０００００００３０５５ＮＤ−ＲＥＳＰＪ　０００００００００１１００ ００００００００１１００００００００００１１０００００３０６５ＮＤＪＥＳ ＰＪ　１００００００００００１１００００００００００１１００００００００ ００１１０００７、配線による制御ビン Ａ、　ＥＦＰＬＯ（３３０）　、　ＥＦＰＬＩ　（３３１）あて先ノードアドレ スは、０ビツトから９ビツト目の１０ビツトで構成されている。ＥＦＰＬＯ（３ ３０）は平面０の有効平面であり、Ｏから９までの任意の値をとることができる 。ＥＦＰＬＩ　（３３０）は平面Ｏが作用するノードアドレスのビット位置であ る。ここで平面０がノードアドレスのビット６の値に基づいてスイッチされてい れば、ＥＦＰＬＯ（３３０）は６として配線される。ＥＦＰＬＩ　（３３１）は それが平面ｌの有効平面であることを除き同様である。

Ｂ、　ＤＩＧＩＴＯ（３３２）　、　ＤＩＧＩＴＩ　（３３３）Ｎノードネット ワークでは、Ｎ横列のスイッチ及びｌｏｇ、Ｎ　＋　１の縦列がある。スイッチ のように思われる横列（０・・Ｎ−１）もまたスイッチ番号と呼ばれ６．０ＩＧ ＩＴＯ（３３２）は、ビットＥＦＰＬＯ（３３０）のスイッチ番号である。ＤＩ ＧＩＴＩ　（３３３）は、ビットＥＦＰＬＩ（３３１）のスイッチ番号である０ 例えば、スイッチ番号が６４（０００１００００００２進）テアリ、ＥＦＰＬＯ （３３０）　カ６’ＴアｆｉｉｆＤＩＧＩＴＯ（３３２）は１である。

上記の制御入力が使用される方法は、ＤＩＧＩＴＯ（３３２）が、宛先ノードア ドレスのビットＥＦＰＬＯ（３３０）に整合しなければ、リクエストは平面Ｏク ロスを必要とし、整合すれば平面。直線を必要とする。ＤＩＧＩＴＩＩ　（３３ ３）が宛先ノードアドレスのビットＥＦＰＬＩ（３３１）に整合しなければ、リ クエストは平面１クロスを必要とし、整合すれば平面１の直線を必要とする。ク ロス接続した端子の必要が直線接続した端子よりも優先権を有する。

Ｃ、５ＴＡＧｊＤＥＬＡＹ　（６１０）ステージディレィ（６１０）ビンは、現 在のリクエストに対するレスポンスが戻るまでの待ち時間をスイッチチップに知 らせるのに使用される。Ｎノードのネットワーク内にｌｏｇｚ　（Ｎ　）　”　 １ステージ（縦列）のスイッチがある。

５ＴＡＧｊＤＥＬＡＹ　（６１０）　：　＝　１＋　（ｌｏｇｔ　（Ｎ）　−ｓ ｔａｇｅ　）　＋（Ｍｅｍｏｒｙ−ａｃｃｅｓｓ−ｃｙｃｌｅｓ＋　０ｔｈｅｒ −ｃｙｃｌｅｓ−１０）　／１６ステージが縦列番号である場合、スイッチはネ ットワーク内にある。ステージは０がらｌｏｇｚ（Ｎ）までの値をとることがで きる。

ネットワークの左側（最も左）がステージ。であり、右側（最も右）がステージ ｌｏｇｚ（Ｎ）である。

メモリアクセスサイクル（Ｍｅｍｏｒｙ−ａｃｃｅｓｓ−ｃｙｃｌｅｓ）は、ネ ットワーククロックの数であり、１つのリクエストが同じメモリ場所にアクセス するのに必要である。新しいリクエストは６ネツトワーククロツク毎に来る。こ れ等の６つのネットワークサイクル内でメモリ場所が読出され、誤りが修正され 、ＭＯＤ３計算が行われ、フェッチアト又はスワップによって変更され、新しい 徴候が計算され、そして最後に再び同じメモリ場所に書込まれる。（他の代りの 方法はレスポンスの修正を行うことではな（、エラーが起きたならば、メモリ誤 りを発することである。それか、ワード読取りを修正し、修正した型（ｖｅｒｓ ｉｏｎ　）を再びメモリに書き込み、変更したプロセスをスキップする。そのリ クエストは、後で再び送られなければならない。）メモリアクセスサイクルは、 次のリクエストが来る前に現在のリクエストを終るため、メモリの順で６より少 ないか又は６に等しくなければならない。他のサイクル（Ｏｔｈｅｒ−ｃｙｃｌ ｅｓ）は、任意のネットワークインタフェースチップ及び任意の他のパイプライ ン又は遅延を通り両方の経路を行くのにかがる時間を含む。全ての他のサイクル は、パイプラインより成っていなければならない。時間はネットワーククロック サイクルで測定される。メモリアクセスサイクルと他のサイクルとの和は、ネッ トワークの右側を出るリクエストの立ち上がり先端と、ネットワークの右側へ戻 るレスポンスの立ち上がり先端との間の全時間である。メモリアクセスサイクル と他のサイクルとの和は、下記の値のみとることができる。

１０．１６．２２，２８．３４．　・ｔｏ＋６＊ｉ　ｉ＞＝０メモリアクセスサ イクルと他のサイクルとの和が上記の値の中間であれば、遅延ステージは、次の 高い値に四捨五入して切り上げられる０例えば、Ｎを３２、ステージを３、メモ リアクセスサイクルを６（最低値）、そして他のサイクルを４（他のサイクルに 対する最小値は、メモリアクセスサイクルと他のサイクルとの和が１゜よりも大 きいか、又は等しくなければならないがら、４である。）とすると、ステージデ ィレィは、以下のようになる。

５ＴＡＧＥＪＥＬＡＹ　（６１０）　：　＝　１　＋　（ｌｏｇｘ（３２）−３ ）　＋（６＋　４−１０）／　６：＝１＋２＋Ｏ：＝３ ３つの新しいリクエストは、現在のリクエストに対するレスポンスがスイッチス テージ３に戻る前に、スイッチステージ３によって送り出される。

５ＴＡＧＥ−ＤＥＬＡＹ　（６１０）上の振幅制約（ｍａｇｎｉｔｕｄｅ　ｃｏ ｎｓｔｒａｉｎｓ）は、１　＜＝ＳＴＡＧＥＪＥＬＡＹ　（６１０）　＜＝３１ である。

ここで、“０”は許されない。通路事象（％−ａｙ　ｅｖｅｎｔｓ）により５Ｔ ＡＧＩ、ＤＥＬＡＹ　（６１０）が“０“でチップ内にパイプラインされれば、 チップは正しく機能しない。

８、　ＲＥＳＥＴ　（６１１） リセット（６１１）ビンは、３２ＲＡＭを通りスライダーリセットコントロール （６１３）ステップがアドレスしている間、高位（ＨＩＧＨ）にもらされ、且つ 高位に保たれなければならない。

スライダー（１０３）　（７）ＲＡＭ　（ＲＡＭ−ＬＳ６０３．　ＲＡＭＪＩＳ ６０６）が初期化されなければならない、従って、リセット信号はクロックと非 同期であり得ない。

９、パワービン必要用件 計算は、１６の出力当り１セツトのパワー、グラウンドパッド（ｇｒｏｕｎｄ　 ｐａｄ）に基づいている。１６８の入出力ビンがあるが、それ等の中の半分のみ が一時に、即ち１６８／２／１　ｅ　：　＝５．２５に出力として作用する。６ セツトのパワーグラウンドパッドに切り上げる。

１０．保守端子（テスト）−誤り報告（６３７）誤りは全て報告する必要がある 。従って、ネットワークの残りからのノード隔離に失敗した場合は、構成変形を 行うことができる。

外部ＬＳＳＤ及び自己テスト特徴が含まれている。

１１、機能 Ａ、リクエスト・デコムバイニング（ｄｅｃｏｍｂｉｎｉｎｇ　）レスポンスの 結合 同じ宛先ノードアドレス、同じメモリアドレス、及び同じタイプを持ち、且つリ クエスト内にチェックコード誤りを持たないリクエストは、１つのリクエストに 結合される。そのタイプが異なれば、スワップは送信され、フェッチアトは中止 される。メモリアドレスは異なるが、ノードアドレスが同じであれば、低位のメ モリアドレスは送信され、高位のメモリアドレスは中止される。第１１−１図の タイミング線図の例は３セツトのリクエストを示している。時間は半ネットワー クサイクルで測定される。この例の配線によるパラメータは、 ＥＦＰＬＯ（３３０）　：＝９ ＥＦＰＬＩ　（３３１）　：＝Ｏ ＤＩＧＩＴＯ（３３２）　：　＝Ｏ ＤＩＧＩＴＩ　（３３３）　：　＝Ｏ ３ＴＡＧＥ、−ＤＥＬＡＹ　（６１０）　：　＝　１である。

時間２乃至９中の第１のセットのリクエストは、同じ宛先ノード及びメモリアド レスに行く４フエツチアドレス（Ｆｅｔｃｈ　ａｄｄｓ）より成っている。これ 等は（特記されていなければ、これ等の数は１６進法である） ＦＥＴＣＨ−ＡＤＤ　（ＡＤＤＲＥＳＳ、ＰＡＲＡＭＥＴＥＲ）Ｒｅｑｕｅｓｔ Ｏ：　ＦＥＴＣＨ−ＡＤＤ　（ＣＯＯＯ０ＯＯＯ，０ＯＯＡ　ＡＡＡＡ　）Ｒｅ ｑｕｅｓｔｌ　：　ＦＥＴＣ）Ｉ−ＡＤＤ　（ＣＯＯＯ００００，０ＯＯＢ　Ｂ ＢＢＢ　）Ｒｅｑｕｅｓｔ２　：　ＦＥＴＣＨＪＤＤ　（ＣＯＯＯ００００，０ ＯＯＣＣＣＣＣ）Ｒｅｑｕｅｓｔ３　：　ＦＥＴＣＨＪＤＤ　（ＣＯＯＯ０００ ０，０ＯＯＤ　ＤＤＤＤ　）である。

アドレス及びパラメータは、双方とも読み易さを高めるために、最下位ハーフフ ァーストを記載している。このパラメータはタイミング線図の最下位ハーフファ ーストを送る。上記リクエストの宛先ノードアドレスは、１１００００００００ 　（２進法）である。

メモリアドレスは、“０”である。

４つのアドレスは、１つのリクエストに結合され、時間８乃至１５の間に右の端 子ｌ　（平面０クロス）から出る。結合したリクエストとは、 ＦＥＴＣＨＪＤＤ　（ＣＯＯＯ００００、００３１１１０Ｅ）　この場合、００ ３１１１０Ｅ：＝０００Ａ　ＡＡＡＡ＋０００８　ＢＢＢＢ＋０００ＣＣＣＣＣ ＋０００Ｄ　ＤＤＤＤ記憶したレスポンスパラメータは（レスポンスをデコムバ インするために）、 ＲｅｑｕｅｓｔＯ：　００００００００Ｒｅｑｕｅｓｔｌ　：　０ＯＯＡ　ＡＡ ＡＡＲｅｑｕｅｓｔ２　：　００１６６６６５：：０００Ａ　ＡＡＡＡ＋０００ Ｂ　ＢＢＢＢＲｅｑｕｅｓｔ３　：　００２３３３３１：：０００Ａ　ＡＡＡＡ ＋０００８　ＢＢＢＢ＋０００ＣＣＣＣＣである。戻り経路の値（逆のルート割 当てに対し）は、ＲｅｑｕｅｓｔＯ：　Ｉ Ｒｅｑｕｅｓｔｌ　：　Ｉ Ｒｅｑｕｅｓｔ２：　Ｉ Ｒｅｑｕｅｓｔ３　：　１である。

上記のリクエストに対するレスポンスは、時間２８乃至３１中にメモリ（又は次 のステージ）から来る、そしてパラメータ０ＯＯＤ　ＦＤＤＤより成っている。

新しいメモリ内容は、 ００３Ｆ　０ＥＦＢ：＝００３１１１０Ｅ　＋０ＯＯＤ　ＦＤＤＤである。

デコムバインしたレスポンスは、時間３４乃至３７中に左ま端子から前のステー ジに送られる。そのレスポンスは下記のように形成される。

Ｒｅ５ｐｏｎｓｅＯ：　００００　ＦＤＤＤ：＝０００Ｄ　ＦＤＤＤＲｅｓｐｏ ｎｓｅｌ　：　００１８　Ａ３８７：：０ＯＯＤ　ＦＤＤＤ＋０ＯＯＡ　ＡＡＡ ＡＲｅｓｐｏｎｓｅ２　：　００２４６４４２：：０００Ｄ　ＦＤＤＤ＋００１ ６６６６５Ｒｅｓｐｏｎｓｅ３　：　００３１３１０ε：＝０００Ｄ　ＦＤＤＤ ＋００２３３３３１４つのリクエストは、０．１．２．３の順に継続的に処理さ れたかのようである。

時間１４乃至２１中の第２のセットのリクエストは、同じ宛先ノード及びメモリ アドレスに行（４つのスワップから成っている。

それ等は、 ５ＷＡＰ　（ＡＤＤＲＥＳＳ、ＰＡＲＡＭＥＴＥＲ）ＲｅｑｕｅｓｔＯ：　５Ｗ ＡＰ　（ＣＯＯＯ００００，００００ＡＡＡＡ　）Ｒｅｑｕｅｓｔｌ　：　５Ｗ ＡＰ　（ＣＯＯＯ００００，００００８ＢＢＢ　）Ｒｅｑｕｅｓｔ２　：　５Ｗ ＡＰ　（ＣＯＯＯ００００，００００ＣＣＣＣ）Ｒｅｑｕｅｓｔ３　：　５ＷＡ Ｐ　（ＣＯＯＯ００００，００００ＤＤＤＤ　）である。

４つのリクエストは、１つのリクエストに結合され、そして時間２０乃至２７中 に右の端子１（平面Ｏクロス）から出る。結合したリクエストは、 ５ＷＡＰ　（ＣＯＯＯ００００，００００ＡＡＡＡ　）である。

記憶したレスポンスパラメータ（レスポンスをデコムバインするために）は、 ＲｅｑｕｅｓｔＯ：　００００　ＢＢＢＢＲｅｑｕｅｓｔｌ　：　００００　Ｃ ＣＣＣＲｅｑｕｅｓｔ２　：　００００　ＤＤＤＤＲｅｑｕｅｓｔ３　：　００ ００００００である。

戻り経路値（逆のルート割当てのために）は、ＲｅｑｕｅｓｔＯ：　Ｉ Ｒｅｑｕｅｓｔｌ　：　Ｉ Ｒｅｑｕｅｓｔ２　：　Ｉ Ｒｅｑｕｅｓｔ３　：　１である。

上記リクエストに対するレスポンスは、時間４０乃至４３中にメモリ（又は次の ステージ）から来る、そしてパラメータは、ＦＦＦＤ　ＦＤＤＤより成っている 。

新しいメモリ内容は、００００　ＡＡＡＡである。

デコムバインにしたレスポンスは、時間４６乃至４９中に左の端子から前のステ ージに送られる。レスポンスは下記のようである。

Ｒｅ５ｐｏｎｓｅＯ：　００００　ＢＢＢＢＲｅｓｐｏｎｓｅｌ　：　００００ 　ＣＣＣＣＲｅ５ｐｏｎｓｅ２　：　００００　ＤＤＤＤＲｅｓｐｏｎｓｅ３　 ：　ＦＦＦＤ　ＦＤＤＤ４つのリクエストは、３．２．１、Ｏの順に継続的に処 理されたかのようである。フェッチアト順序と異なっているスワップ遂次順序の 理由は、上記の順序がより容易であるということである。

時間２６乃至３３中の第３のセットのリクエストは、２つのフェッチアト及び２ つのスワップより成っている。それ等は、ＦＥＴＣＨＪＤＤ　（ＡＤＤＲＥＳＳ 、ＰＡＲＡＭＥＴＥＲ）ＲｅｑｕｅｓｔＯ：　ＦＥＴＣＨｊＤＤ　（００４００ ００１，ＡＯＯＯ００００）Ｒｅｑｕｅｓｔｌ　：　ＦＥＴＣ）ｌ−ＡＤＤ　（ ００４００００１，ＢＯＯＯ１１１１）Ｒｅｑｕｅｓｔ２：　５ＷＡＰ　（１０ ４００００１，Ｃ００Ｏ２２２２）Ｒｅｑｕｅｓｔ３：　５ＷＡＰ　（１０４０ ０００１，ＤＯＯＤ　３３３３　）である。

２フエツチアトの宛先ノードアドレスは、０００００００００１　（２進法）で ある。

２スワツプの宛先ノードアドレスは、 ０００１０００００１　（２進法）である。

メモリアドレスは、４つの全リクエストで“ｌ”である。２フエツチアトは、１ つのリクエストに結合される、そして時間３２乃至３９中に右の端子３（平面ｌ クロス）から出る。結合したリクエストは、ＦＥＴＣＨＪＤＤ　（００４０００ ０１，５０００１１１１）であり、この場合、５０００１１１１は、３２ビツト に切ったＡＯＯＯ００００とＢ［１００１１１１との和である。２つの最初のパ ラメータの加算中に起きた２の補数オーバーフローに注意する。ネットワークは 、現在オーバーフローを検出していないが、加算論理が加えられれば可能である 。２スワツプは１つのリクエストに結合される、そして時間３２乃至３９中に右 の端子２（平面１直線）から出る。結合したリクエストは、５ＷＡＰ　（１０４ ００００１，Ｃ００Ｏ２２２２）である。

記憶したレスポンスパラメータ（レスポンスをデコムバインするために）は、 ＲｅｑｕｅｓｔＯ：　００００００００Ｒｅｑｕｅｓｔｌ　：　ＡＯＯＯ０００ ０Ｒｅｑｕｅｓｔ２　：　ＤＯＯＯ３３３３Ｒｅｑｕｅｓｔ３　：　０００００ ０００である。

戻り経路値（逆のルート割り当てのために）は、ＲｅｑｕｅｓｔＯ：　３ Ｒｅｑｕｅｓｔｌ　：　３ Ｒｅｑｕｅｓｔ２　：　２ Ｒｅｑｕｅｓｔ３　：　２である。

レスポンスは、時間５２乃至５５中に、メモリ（又は次のステージ）から戻る。

この場合、２つのレスポンスは、あて先ノードアドレスがフェッチアト及びスワ ップに対して異なるので、２つの異なるメモリバンクから来る。フェッチアドレ スポンスパラメータは、右の端子３（平面１クロス）で３０００７７７７であり 、そしてスワップレスポンスパラメータは、右の端子２（平面１直線）で２００ ００６６６６である。フェッチアト場所の新しいメモリ内容は、８０００８８８ ８　：　＝５０００１１１１　＋３０００７７７７　（２の補数オーバーフロー ）であり。スワップに対する新しいメモリ内容は、Ｃ００Ｏ２２２２である。

デコムバインしたレスポンスは、時間５８乃至６１中に左の端子から送られる。

レスポンスは下記のように形成される。

Ｒｅ５ｐｏｎｓｅＯ：　３０００７７７７Ｒｅｓｐｏｎｓｅｌ　：　ＤＯＯＯ７ ７７７：＝　３０００７７７７＋ＡＯＯ０００００Ｒｅｓｐｏｎｓｅ２　：　Ｄ ＯＯＯ３３３３Ｒｅｓｐｏｎｓｅ３　：　Ｚｏｏ（１６６６６それは、２つのフ ェッチアトが０．１の順に継続的に処理され、そして２つのスワップが３．２の 順に継続的に処理されたかのようである。

結合したリクエストは、ＦＥＴＣＨＪＤＤ　（ＣＯＯＯ００００，００１６６６ ６５）である。

記憶したレスポンスパラメータ（レスポンスをデコムバインするために）は、 ＲｅｑｕｅｓｔＯ：　００００００００Ｒｅｑｕｅｓｔｌ　：　０ＯＯＡ　ＡＡ ＡＡメモリからのレスポンスは、００００　ＦＤＤＤ　、新しいメモリ内容は、 ００２４６４４２：＝ＯＯ１６６６６５＋０００Ｄ　ＦＤＤＤ　。

Ｒｅ５ｐｏｎｓｅＯ：　０ＯＯＤ　ＦＤＤＤ：＝ＯＯＯＤ　ＦＤＤＤＲｅｓｐｏ ｎｓｅｌ　：　００１８　Ａ３８７：：０００Ｄ　ＦＤＤＤ＋０ＯＯＡ　ＡＡＡ Ａである。

３つのスワップリクエストは、下記のように結合され、デコン゛バインされる。

５ＷＡＰ　（ＡＤＤＲＥＳＳ、ＰＡＲＡλＩＥＴＥＲ）ＲｅｑｕｅｓｔＯ：　５ ＷＡＰ　（ＣＯＯＯ００００，００００ＡＡＡＡ　）Ｒｅｑｕｅｓｔｌ　：　５ ｌｌｆＡＰ　（ＣＯＱｏ　００００．（１０００ＢＢＢＢ　）Ｒｅｑｕｅｓｔ２ 　：　５ＷＡＰ　（ＣＯＯＯ００００，００００ＣＧＣＧ　）結合したリクエス トは、 ５ＷＡＰ　（ＣＯＯＯ００００，００００ＡＡＡＡ　）である。

記憶したレスポンスパラメータ（レスポンスをデコムバインするために）は、 ＲｅｑｕｅｓｔＯ：　００００　ＢＢＢＢＲｅｑｕｅｓｔｌ　：　００００　Ｃ ＣＣＧＲｅｑｕｅｓｔ２　：　００００００００である。

メモリからのレスポンスは、ＦＦＦＤ　ＦＤＤＤ　。

新しいメモリ内容は、００００　ＡＡＡＡ、Ｒｅ５ｐｏｎｓｅＯ：　００００　 ＢＢＢＢＲｅｓｐｏｎｓｅｌ　：　００００　ＣＣＣＣＲｅ５ｐｏｎｓｅ２　： 　ＦＦＦＤ　ＦＤＤＤである。

２つのスワップリクエストは、下記のように結合され、デコンバインされる。

５ＷＡＰ　（ＡＤＤＲＥＳＳ、ＰＡＲＡＭＥＴＥＲ）ＲｅｑｕｅｓｔＯ：　５Ｗ ＡＰ　（ＣＯＯＯ００００，００００ＡＡＡＡ　）Ｒｅｑｕｅｓｔｌ　：　５Ｗ ＡＰ　（ＣＯＯＯ００００，００００８ＢＢＢ　）結合したリクエストは、 ５ＷＡＰ　（ＣＯＯＯ００００，００００ＡＡＡＡ　）である。

記憶したレスポンスパラメータ（レスポンスをデコムバインするために）は、 ＲｅｑｕｅｓｔＯ：　００００　ＢＢＢＢＲｅｑｕｅｓｔｌ　：　［１ＯＤ００ ０００である。

メモリからのレスポンスは、ＦＦＦＤ　ＦＤＤＤ、新しいメモリ内容は、０００ ０８ＢＢＢ、Ｒｅ５ｐｏｎｓｅＯ：　００００　ＢＢＢＢＲｅｓｐｏｎｓｅｌ　 ：　ＦＦＦＤ　ＦＤＤＤである。

Ｂ、ルート割当てリクエスト 優先順位は、平面１が平面Ｏよりも常に優先する。リクエストがクロス接続端子 を要求する場合、クロス接続端子は直線端子にイ！失する。リクエストがいかな るクロス接続端子をも要求せず（それが直線接続端子を要求することを意味する ）、直線端子が利用できない場合、クロス接続端子が平面０と共に優先して選ば れる、というのは、次のステージにおいて「キャッチアップ」平面を用いてトラ ックに戻すチャンスがあるからである。他の平面全てが等しければ低い番号の左 の端子に優先を与えるために任意の決定がされる。

平面１がキャッチアップ平面であり、従って平面１を必要とするいかなるリクエ ストも、それを得なければならない、というのは、第１のステージになければ、 その場合に最後のステージにキャッチアップ平面の第２のチャンスがあるからで ある。平面０が主平面である０次のステージはキャッチアップ平面と同じ有効平 面を有しているので、ルートを得る第２のチャンスがある。

例えば、上記のタイミング図の例では、ＥＦＰＬＯ（３３０）は９、ＥＦＰＬＩ 　（３３１）はＯ％ＤＩＧＩＴＯ（３３２）は０、ＤＩＧＩＴＩ　（３３３）は Ｏである。宛先ノードアドレスは、１１００００００００　（２進法’）　（Ｃ ０００００００ＨＥＸ）である、　ＤＩＧＩＴＯ（３３２）は宛先ノードアドレ スのビット９に適合しないので、リクエストは平面Ｏクロスが必要である。ＤＩ ＧＩＴＩ　（３３３）は宛先ノードアドレスのビット０に適合するので、リクエ ストは平面１クロスを必要としない。結合したリクエストは、平面０クロス（Ｒ ＨＮＴＤＴＩ、５４６Ｂ）を得ることで終る。

Ｃ０戻り経路及び記憶したレスポンスパラメータの記憶スイッチチップは、戻り 経路とルート割当て、且つレスポンスをデコムバインすめために使用されなけれ ばならないバラメークとを記憶する。

この戻り経路及び記憶したパラメータは、どの左の端子がリクエストに加わった かによって所定の場所に記憶される。戻り経路値は、リクエストが出る右の端子 である。戻り経路及び記憶したレスポンスパラメータの例に対するリクエスト結 合及びレスポンスデコムバインに関する章を参照。

Ｄ、誤り検出 スイッチチップは、リクエスト及びレスポンスがチップを通過するときに、リク エスト及びレスポンスに関する誤りの検出を行う。

誤りが発生した場合、リクエストがチップを去らず、且つリクエストに対するレ スポンスタイプが誤り状態に強制されていなければ、リクエストは停止される。

右の端子がクレームした後、誤りが検出されれば、リクエストは通過を許可され るが、レスポンスはフォースエラー（ｆｏｒｃｅ　ｅｒｒｏｒ　）レスポンスと して記憶される。

１２、配線による制御ビン設定のための３２ノ一ド例そのネットワーク例は、３ ２のノードにより構成される。ネットワークに６ステージあり、その結果１９２ 　（６＊３２）のスイッチチップが要求される。ステージＯ左の端子をリクエス トノードへのネットワークインタフェースチップに接続する。「ノーリクエスト ｊタイプが常に送られるように、他の３つの左の端子を抵抗に結合する。（ネッ トワークインターフェースがこれを処理できる。）端子が両方向性であるから抵 抗結合（ｔｉｅ　ｏｆｆ　）が必要である。左の端子０が最高優先権を有する。

ステージ５右の端子２（平面１直線）をメモリへのネットワークインタフェース チップに接続する。ネットワークインタフェースが他の３つの右の端子の結合を 処理できる。ルート割当ての誤りは、リクエストが実査位に不使用端子のいくつ かに現われるときのみ送り返される。リクエストが現われなければ「ノーリクエ スト」レスポンスタイプを送り返す。右の端子２は、直線端子が必要であるとき 最高優先権を有する。各々のスイッチチップの配線による接続を下記に示す。

Ｓｔａｇｅ　０　１　２　３　４　５ ＥＦＬＰ　ＥＯＥＩ　ＥＯＥＩ　ＥＯＥＩ　ＥＯＥＩ　ＥＯＥＩ　ＥＯＥＩ４０ 　３４　２３　１２　０１　０Ｏ ＳＴＡＧＥＤＥＬＡＹ　６　５　４　３　２　１１）ＩＧＨ丁　ＤＯＤＩ　ＤＯ ＤＩ　ＤＯＤＩ　Ｔｌ０ＤＩ　ＤＯＤＩ　ＤＯＤＩＳｗｉｔｃｈ　ｎｕｍｂｅｒ ｏｏｏｏｏｏｏｏ　ｏｏ　ｏｏ　ｏｏ　ｏｏ　ｏ。

３０００１１００　００　Ｇｏ　１０　１１　１１６００１１０００　００　１ ０　１１　０１　Ｇ。

１６１００００１０　０１　００　００　００　Ｇ。

１９１００１１１１　０１　Ｇｏ　１０　１１　１１２４１１０００１０　１１ 　０１　Ｇｏ　００　００スイ・ンチチ・ツブの・細な舌日 第８図は、スイッチ２０チツプの全ブロック線図を示している。

４つのリクエストまでが前のステージから左のバッファ（１００）に入ることが できる。入って来る「リクエスト」は正しい右の端子に順方向に送出され、可能 であれば結合される。次にリクエストは右のバッファ（１０５）を通り次のステ ージへ出て行く。スライダー（１０３）は、逆方向スイッチ設定及び結合された リクエストに対するレスポンスをデコムバインするために、用意したレスポンス パラメータを蓄積する。レスポンスは次のステージから右のバッファ（１０５） を通り、レスポンスリバースルーテイングデコムバイニング（Ｒｅｓｐｏｎｓｅ 　Ｒｅｖｅｒｓｅ　Ｒｏｕｔｉｎｇ　Ｄｅｃｏｍｂｉｎｉｎｇ）　（１０４）に 入る。レスポンスは正しい左の端子に発送され、必要があればデコムバインされ る。それからレスポンスは、左のバッファ（１００）を通り前のステージに行く 。誤り制御ブロック（１０１）がチップを通る４つの経路をモニタし、誤り発生 を記録し、そして多過ぎる誤りが特定の経路に起きれば、その経路は遮断され、 すべてのデータは残りの経路を通り送出されなければならなない。

ビットビック（Ｂｉｔ　Ｐｉｃｋ）　（２００）と明示した回路がリクエストの ノードアドレスを検査し、どの右の端子が各々のリクエストを必要とするかを決 定する。リクエスト評価（２０１）が各々のリクエストを全ての他のリクエスト と比較し、リクエストが結合されるかどうか、そのリクエストが他のリクエスト より優先権を有しているかを決定する。リクエスト評価（２０１）は、またデー タ経路上のＭＯＤ３誤りをチェックする。クレームセクション（２０２）が必要 な右の端子を各々のリクエストを割り当てる。スナップレジスタ（Ｓｎａｐ　ｒ ｅｇｉｓｔｅｒ　）　（２０４）は、将来の使用のためにクロックフェーズ間に データを貯える。

スイッチ設定（２０３）が割り当てられた右の端子及び結合能力情報を受けとり 、選択加算器（２０５）への制御ラインを調節し。

正しい右の端子へのリクエストを発信して結合する。スイッチ設定（２０３）は 、レスポンスデコムバインのために記憶したレスポンスパラメータを計算する選 択加算器制御ラインを調節する。また、スイッチ設定（２０３）は、レスポンス をレスポンスセレクター（１０４）を通り送出するために逆方向スイッチ設定を 計算する。

若し、全てのリクエストに対して十分な右の動作端子がなければ。

スライダー（１０３）の逆方向スイッチ設定を貯える代りに、フォースエラーレ スポンスビットがスライダーにセットされて、リクエストが送出されていないこ とを示す。選択加算器（２０５）は、リクエストを送出し、順方向パラメーター を送出し、且つ計算し。

そして用意したパラメーターを計算するのに使用される。

第９図乃至第２６図はネットワークスイッチの詳細なブロック図を示している。

ラッチで明示されている全てのブロックはフィールドスルーラッチである。デー タはクロックがへイのとき、出力にフィードスルーされ、出力はクロックがロー のとき保持される。左のバッファ（１００）において（これは両方向Ｉ１０制御 回路３１０Ａ〜３１０Ｄを含む）、１６ビツトのリクエストデータ（ＬＨＮＴＤ Ｔ、−。

３０７Ａ−Ｄ）及びデータのための２ビツトのチェックコード（ＬＨＮＴＣＣ− 。

３０８Ａ−Ｄ）は、クロック７ｊ−−ズＲＣＶ−ＲＥＱ−Ａ　（３０１）　、　 ＲＣＶ−ＲＥＱ−Ｂ（３０２）　、　ＲＣＶＪＡＲＡＭＪ　（３０３）及びＲＣ Ｖ−ＰＡＲＡＭ−Ｂ　（３０４）中に、前のステージから受け入れられる。レス ポンスデータ及びチェックコードは、クロックフェーズ５ＮＤＪＥＳＰＪ　（３ ０５）及び５ＮＤ−ＲＥＳＰＪ　（３０６）中に、同じラインで前のステージに 送られる。３ビツトのリクエストタイプ（ＬＨＮＴＴＹ−、３０９Ａ−Ｄ）は、 クロックフェーズＲＣＶ、−ＲＥＱＪ　（３０１）及びＲＣＶ−ＲＥＱ−Ｂ　（ ３０２＞中に、前のステージから受け入れられる。レスポンスタイプは、クロッ クフェーズ５ＮＤ−ＲＥＳＰＪ　（３０５）及び５ＮＤ−ＲＥＳＰ−Ｂ　（３０ ６）中に、前のステージに送られる。ハンドシェイク「妥当な（Ｖａｌｉｄ）リ クエスト受信」（３１４Ａ−Ｄ）は、クロックフェーズＲＣＶ−ＰＡＲＡｌｉｌ −Ａ　（３０３）及びＲＣＶ−ＰＡＲＡＭＪ　（３０４）中に、パイプライン（ ３０９Ａ−Ｄ）上を前のステージに送られる。左のバッファハンドシェイク回路 （３１５Ａ−Ｄ）が第２６図に示されている。このハンドシェイク回路は受信し たタイプが奇数パリティを有し、パリティが奇数であれば４を、パリティが偶数 であれば（誤りを示す）７を出すのをチェックする。

データライン（ＬＲＱＤＴ、−［６・・１５］　、　３２７Ｅ−Ｈ）の上部１０ ビツトは、どの右の端子が必要であるか（３３８Ａ−Ｈ）を決定するためにビッ トビック（２００）に送られる。これ等の１０ビツトはＲＣＶＪＥＱ−Ｂ（３０ ２）中に、宛先プロセッサアドレスを表わす。クロス接続した右の端子のみが「 必要な」信号を有している。直線接続した右の端子はクロス端子がリクエストに よって望まれなければデフォルトである。

第１４図は、ビットビックの詳細を示している。ビットビック内の１０：１マク セス（ｍｕｘｅｓ　）が有効平面を示すために制御ラインとしてＥＦＰＬＯ（３ ３０）又はＥＦＰＬＩ　（３３１）を用いて宛先プロセッサアドレスの１ビツト を選択する。それから選択したビットは、ＲＥＱＪ％ＡＮ’ｊ　（３３８Ａ−Ｈ ）を生成するために、ＤＩＧＩＴＯ（３３２）又はＤＩＧＩＴ！　（３３３）の いずれかにより排他的論理和される。ＬＲＱＤＴ−［６・・１５］　（３２７Ｅ −Ｈ）がまた１−ビットイクォリティチェッカー（Ｅｑｕａｌｉｔｙ　Ｃｈｅｃ ｋｅｒ）　（３３５）に送られて、任意の２つの宛先プロセッサアドレスが等し いかどうかを調べる。生成された信号がＰＡＪＱ−（３０４Ａ−Ｆ）である。

１６ビツトの全データ（ＬＲＱＤＴ−，３２７Ａ−Ｄ）が１６ビツト振幅比較器 （３３６）に送られて、どのメモリアドレスが等しいか（λ１Ａｊ（ｊ３４］Ａ −Ｆ）と°のメモリアドレスが他のメモリアドレス（ＭＡ−６丁−，３４２Ａ− Ｌ）よりも大きいかを見い出す。その振幅比較は、ＲＣＶ−ＲＥＱ−Ｂ　（３０ ２）及びＲＣＶ−ＰＡＲＡＭ−Ａ　（３０３）中のみ有効である。

ＲＣＶ−ＲＥＱＪ　（３０２）　、　ＲＣＶｊＡＲＡＭＪ　（３０３）　、　Ｒ ＣＶ−ＰＡＲＡＭ−８（３０４）、及び５ＮＤ−ＲＥＳＰＪ　（３０５）中に、 ＭＯＤ３チェックがデータ（ＬＲＱＤ’ｊ　、３２７Ａ−Ｄ）で行われ、ブロッ クリクエスト評価ＭＯＤ３チェック（４０４）内でチェックコード（ＬＲＱＣＣ −，３２８Ａ−Ｄ）に比較される。ＭＯＤ３チェック−組立体（第１５図）は、 ２ビツトＭＯＤ３加算ツリーより成っている。ツリーの第１列は、特に縮小した ＭＯＤ３加算器であって、２ビツトＭＯＤ３ナンバーのセットへの１６ビツト２ 進ナンバーの変換を担当する。ＭＯＤ３加算器の論理が第２４図に示されている 。リクエスト評価ＭＯＤ３チェックブロック内でタイプラインの更に他のチェッ クが行われる。リクエストタイプは、サスペンドチェック（Ｓｕｓｐｅｎｄ　Ｃ ｈｅｃｋ　）　（４０５）内でフェッチアト又はスワップ（ＴＹｊＳＦＡ、　４ ００Ａ−Ｄ及びＴＹ−ＩＳＳＷ、　４００Ｅ−Ｈ）のいずれかにデコードされる 。

タイプデコーディングが第１６図に示されている。このタイプがフェッチアト（ 即ち、フェッチアンドアト）又はスワップのいずれでもなければ、リクエストの ＤＴＪＫ　（４０２Ａ−Ｄ）ラインは、データが無視できることを示すローに保 たれる。誤りがあったか又はリクエストがないかのいずれかである。ＤＴ−ＯＫ 　（４０２Ａ−Ｄ）ラインの補数がＲＱＥＪＲ−（４０１Ａ−Ｄ）であり、チッ プを通る各々の経路上の誤りをモニタするための誤り制御に送られる。

サスペンドチェック（４０５）は、リクエスト内に誤りがあったので、又はリク エストが低位優先権を有しており、且つ高位優先権リクエストと同じ宛先プロセ ッサアドレスを有しているが高位優先権リクエストと結合できないので、リクエ ストを一時停止する必要があるかを調べるためにチェックする。

サスペンドチェック論理が第１６図に示されている。小さいメモリアドレスが大 きいメモリアドレスよりも優先権を有している。

スワップがフェッチアトよりも優先権を有してる。従って、サスペンド（ＳＵＳ ＰＥＮＤ−）　（４０３Ａ−Ｄ）がマージチェック（４５２）及びＲｅｑ−ａｃ ｔｉｖｅ　（４５３）に送られる。マージチェックが各々のリクエストを全ての 他のリクエストと比較し、どのリクエストがどれに結合できるかを調べる。

第２３図はマージチェック及びＲｅｑ−ａｃｔｉｖｅの論理を示している。

リクエストは、それ等の宛先プロセッサアドレスが等しく、それ等のメモリアド レスが等しく、それ等のタイプが等しく、それ等が一時中止されていないときの み結合される。Ｒｅｑ−ａｃｔｉｖｅ　（４５３）はどのリクエストが、結合が 行われた後アクティブであるかを決定する。１セツトの結合したリクエストにお いて、最低ナンバーの左の端子を有するものが、アクティグであり、且つ結合し たリクエストの制御内にあるものである。結合されない、且つ一時中止されない リクエストもまたアクティグである。リクエストは２半部に分けられるので（外 部ピンカウントを制限するために多重送信される）。

第１半部中に行った決定が、なお第２半部中でも有効であるかを調べるために、 リクエストの第２半部間で比較が行われなければならない。アンドゲートグルー プ４５４及び４５５が第１半部のマージ信号を第２半部と比較する。

マージが起きる唯一の方法は、第１半部及び第２半部の双方がマージするかどう かということである。アンドゲートグループ４５６（ＲＥＱＪＢＯＲＴ、　４２ ９Ａ−Ｃ）　＋：！、ＲＥＱ−ＡＣＴＩＶＥ　（４０８Ａ−Ｄ）信号が前（７） マージのときのメモリアドレスの不一致、又はリクエストの第２半部でのタイプ 又は誤りの不一致により、中断したかどうかを調べるためにチェックする。リク エスト３が他のリクエストとマージすればリクエスト３はアクティグでないので ＲＥＱ３ＪＢＯＲＴはない。アンドゲートグループ４５７　（ＲＥＱ−ＮＥＷ、 ４３０Ａ−Ｃ）は、新しいリクエストが第１半部中にアクティグでなかったとき 第２半部中にアクティグである新しいリクエストをチェックする。　ＲＥＱ、− ＮＥＷラインは、マージされるリクエストのグループ内の最低ナンバーのリクエ ストが、リクエストの第２半部中に一時中止されていれば高位になる。

リクエストがいくつかの他のリクエストとマージされれば、左の端子０に到着す るリクエストが常にリクエストの第１半部中に制御リクエストであるからＲＥＱ ＪＥＷラインはない。このリクエストが最高優先権を有する。　ＭＥＲＧＥ、Ａ ＢＯＲＴ、及びＮＥＷ信号が断制御リクエス）　（Ｎｅｗ　Ｃｏｎｔｒｏｌｌｉ ｎｇ　Ｒｅｑｕｅｓｔ　）　（４３７）に送られてどのリクエストが制御してい たかを決定し、第１半部が、どのリクエストが第２の半部中に制御されるかを比 較する。新制御リクエスト（４３７）の論理が第１７図に示されている。出力信 号は、ＮＥＷの前のナンバーが古い制御リクエストを示す場合、及びＮＥＷ後の ナンバーが新制御リクエストを示す場合、ＪＮＥＷ−（４３６Ａｊ）である。

クレームマトリクス（２０２）が、右の端子にリクエストを割当てる。誤り制御 がラインＰＯ３ＢＡＤ、　ＰＯＣＢＡＤ、　ＰＩＳＢＡＤ又はＰＩＣＢＡＤ　（ ６００Ａ−Ｄ）の１つを高位にもたらすことによって右の端子を使用不能にする ことができる。クレームマトリクスは、ＲＥＱＪＡＮＴ−（３３８Ａ−Ｈ）及び （４０８Ａ−Ｄ）ラインを右の端子に割り当てるのに使用する。クレームマトリ クスが第１８図に示されている。クレームセル（ＣｌａｉｍＣｅｌｌ）が第２２ 図に示されている。右の端子に割り当てるときの優先順位は平面１クロス（ＰＩ Ｃ）、平面０クロス（ＰＯＣ）、平面１直線（ＰＩＳ）そして平面０直線（ＰＯ Ｓ）である。

この優先機構はクレームマトリクスにおける縦列の順位によって表わされる。リ クエストがクロス端子を必要とせず、直線端子の双方が既にクレームされていれ ば、そのリクエストはクレームマトリクスの最後の２縦列からクロス端子を得る のに役立つ。優先順位は平面Ｏクロス、次に平面１クロスである。平面Ｏクロス は、次のステージにおいてリクエストが平面ｌクロスを必要とし、「キャッチア ップ」平面を用いることによってトラックに戻すことができるので、優先権が与 えられる。

横列の順位が左の端子ナンバーに基づくリクエストの優先権を示す。全ての他の ものが等しければ、低いナンバーの左の端子に達するリクエストが優先権を有し ている。縦列優先順位が横列優先順位よりも優先する。クロスした右の端子の必 要性が低いナンバーの左の端子の必要性よりも高い優先権を有する。クレームマ トリクスの出力はＲ−ＧＥＴ−（４１７Ａ−Ｐ）である。

ＨＪＧＥ’ｊ　（４１９Ａ−Ｐ）及びＲ−ＮＥＷ　（４３６Ａ−Ｉ）がニューゴ ットイッツ（Ｎｅｗ　Ｇｏｔ　Ｉｔｓ　）　（４３８）に送られて、リクエスト の第２半部中に右の端子にどのように再割当てされるかを決定する。リクエスト 間のイ！先権は第２半部中に中断によって変化したかも知れないので第２半部中 に、単にクレームマトリクスによりクレームを再び行うだけでは十分ではない。

優先権が変更され、クレームが再び行われれば、リクエストは２つの右の端子間 に分けられる。例えば、リクエスト０．２及び３が結合され、平面１クロスを必 要とし、リクエストがそれ自身によって通過し、また平面クロスｌを必要とすれ ば、リクエストの第１半部の端において、リクエストＯが平面ｌクロスを得る、 そしてリクエスト１が平面１直線を得る。第２半部中にリクエスト０が中断され ると、クレームマトリクスによる再評価が平面１クロスを得、そしてリクエスト ２が平面１直線を得る結果となる。２セツトのリクエストが混合される。必要な ことは、信号ＨＲＯＧＥＴＰＩＣ（４１９Ｄ）をとり、それをＮＥＷ−Ｒ２ＧＥ ＴＩＣ（４４５Ｌ）に再び割り当てることである。そこでリクエストは正しい右 の端子上にとどまり、相互に混合されない。ニューゴットイッッ（Ｎｅｗ　Ｇｏ ｔ　Ｉｔｓ　）の論理が第１７図に示されている。

スナップレジスタ（Ｓｎａｐ　Ｒｅｇｉｓｔｅｒ　）　（２０３）は、将来のク ロックフェーズに使用するためのデータを保持するのに使用される。

レジスタ（４２０）はタイプ５ＮＴＹ−（４２１Ａ−Ｄ）を保持する。

レジスタ４２４はパラメータのデータの第１半部及びチェックビットを保持する 。パラメータのデータの第２半部及びチェックビットが左のバッファレジスタ３ ２４Ａ−Ｄ及び３２５Ａ−Ｄ内に保持される。パラメータの第１及び第２半部が 信号ＳＮＤ’ｊ　（４４９Ａ−Ｄ）及び５ＮＣＣ−（４５ＯＡ−Ｄ）を生成する レジスタ４５１に多重系にされ（４４６）、次にそれ等の信号が選択加算器（Ｓ ｅｌｅｃｔｉｖｅ　Ａｄｄｅｒ　）　（２０５，５２０）に送られる。

スナップレジスタの理由は、リクエストパラメータが２回使用される必要がある ということである。１回は順方向パラメータを計算するため、そして１回は記憶 したレスポンスパラメータを計算するためである。順方向パラメータを計算する とき、パラメータの双方の半部は、マクス（ｍｕｘ）（４４６）の端子Ｏを通り 流れる。記憶したレスポンスパラメータを計算するとき、パラメータの第１半部 はマクス（４４６）の端子１から生じ、そしてパラメータの第２半部はマクス（ ４４６）の端子０から生ずる。レジスタ４３３が将来の使用のためにマージ信号 ５ＮＲＪＡ−（４３４Ａ−Ｆ）及び５ＮＲ−５Ｗ−（４３５Ａ−Ｆ）を蓄えてい る。

スイッチ設定（２０３）は選択加算器（２０５）のための制御ラインを調節する 。記憶したレスポンスパラメータ選択加算器スイッチ設定（５０２）は、マージ 信号５ＮＲＪＡ−（４３４Ａ−Ｆ）及び５ＮＲ−３Ｗ−（４３５Ａ−Ｆ）を受け とり、記憶したレスポンスパラメータを計算するためにどのように選択加算器を 調節するかを決定する。記憶したレスポンスパラメータ選択加算器スイッチ設定 （５０２）の論理が第２０図に示されている。リクエストがいかなる他のリクエ ストとも結合されていなければ、記憶したレスポンスパラメータは０である。リ クエストが他のリクエストと結合したフェッチアトであれば、記憶したレスポン スパラメータは、低位の左の端子ナンバーを有している結合されている他のリク エストのパラメータの合計である。リクエストが結合されているこれ等のリクエ ストの最低の左の端子ナンバーを有していれば、記憶したレスポンスパラメータ は０である。

リクエストが他のリクエストと結合したスワップであれば、記憶したレスポンス パラメータは次の高位の左の端子ナンバーを有するリクエスト（結合されている これ等の中）のパラメータである。

リクエストが結合されているこれ等のリクエストの最高の左の端子ナンバーを有 していれば、記憶したレスポンスパラメータは０である。

選択加算器スイッチ設定（５１４）は、信号５ＮＲＪＡ−（４３４Ａ−Ｆ）。

５ＮＲＪＷ　（４３５Ａ−Ｆ）　、　ＮＥＷＪＪＥＴ−（４４５Ａ−Ｐ）及びＨ Ｆ−ＡＤＤ−（５０９Ａ−Ｆ）　。

（記憶したレスポンスパラメータ選択加算器スイッチ設定）を受けとり、選択加 算器を制御する信号、　ＦＪＤＤ−（５１５Ａ−Ｐ）を生成する。

ＦＪＤＤ−において、ＡＤＤの前のナンバーが左の端子ナンバーを示し、ＡＤＤ Ｏ後のナンバーが右の端子ナンバーを示している。

選択加算器スイッチ設定（５１４）の論理が第２０図に示されている。ＲＣＶＪ ＡＲＡＭＪ　（３０３）及びＲＣＶ−ＰＡＲＡＭ−Ｂ　（３０４）中に、リクエ ストは、単にリクエストを得た右の端子に基づいて選択加算器を通り送出される 。追加は行われない、　５ＮＤ−ＲＥＳＰＪ　（３０５）及びＳＮＤ、、−ＲＥ ＳＰＪ　（３０６）中に、順方向リクエストパラメータが計算される。

リクエストがいかなる他のリクエストとも結合されていなければパラメータは、 リクエストを得た右の端子に基づいて選択加算器を通り送出される。リクエスト が他のリクエストと結合したフェッチアトであれば、順方向パラメータは結合さ れている全てのパラメータの合計である。リクエストが他のリクエストと結合し たスワップであれば、順情報パラメータは、制定ナンバーの左の端子ではリクエ ストのパラメータである。ＲＣＶ−ＲＥＱ−Ａ　（３０１）及びＲＣＶ−ＲＥＱ −Ｂ（３０２）中に記憶したパラメータは上記のように計算される。

レスポンスセレクタスイッチ設定（５０１）は各々のリクエストが実際にマージ 信号５ＮＲＪＡ−（４３４Ａ−Ｆ）　、　５ＮＲＪＷ　（４３５Ａ−Ｆ）及びニ ューゴットイツツＮＥＷＪ−ＧＥＴ−（４４５Ａ−Ｐ）に基づいて出た右の端子 を計算する。レスポンスセレクタスイッチ設定（５０１）の論理が第１９図に示 されている。割り当てた右の端子は、２低位（１０Ｗｏｒｄｅｒ　）ビットのＢ ｊＥＬ　（５１３Ａ−Ｄ）にエンコードされる。高位のビットのＪＳＥＬ　ｔ５ １３Ａ−Ｄ）はリクエストが不一致又は誤りによって右の端子に出て行かなけれ ば、セットされる。高位ビットは、レスポンスがチップを通りカムバックすると き誤りレスポンスを追出すのに使用される。レスポンスセレクタスイッチ設定ビ ットは、レスポンスを逆に送出するのに使用するためスライダー（１０３）内に 貯えられる。

フォースゼロアト（Ｆｏｒｃｅ　Ｚｅｒｏ　Ａｄｄ）　（５００）は、結合した スワップであるレスポンスをデコムバインするとき、制御に使用される。フォー スゼロアト（５００）の論理が第１７図に示されている。スワップをデコムバイ ンするとき、最高ナンバーの左の端子のときの初めのリクエストは右のバッファ （１０，５）内に入るレスポンスパラメータを得る。他のリクエストは右のバッ ファ（１０５）から来るレスポンスを無視し、そしてフォースゼロアトビットＺ Ｅ−（５１２Ａ−Ｄ）に基づいてそれ等の記憶したレスポンスパラメータを使用 する。フォースゼロアトビットは、レスポンスがカムバックするときに使用する ためスライダー（１０３）に貯えられる。

選択加算器（２０５）はリクエストを送出し、順方向パラメータを送出及び計算 し、上記のように記憶したレスポンスパラメータを計算するのに使用される。パ ラメータは２つの半部に分けられるので、キャリービットはレジスタ５２２によ って半部の間に貯えられる。選択加算器は４つのセットの加算器より成っており 、それ等の各々は４人カデータライン（ＳＮＤＴ−、４４９Ａ−Ｄ）のいかなる 組み合せとも一緒に加えることができる。４つの演算数までが一緒に加算できる ので加算器セット当り２キヤリービツトである必要がある。

選択加算器の論理が第１１図及び第２１図に示されている。加算される演算数の チェックコードは、ＭＯＤ３加算器を使用して加算される。加算の第２半部中に 、加算の第１半部からのキャリーピッ）　（ＨＣＡＲＲＹ４　、５２１Ａ−Ｈ） が、特殊ＭＯＤ３加算器（Ｓｐｅｃｉａｌ　ＭＯＤ３Ａｄｄｅｒ）　（第２４図 ）を用いてチェックコードに加算される。加算の第１半部中に記憶したキャリー ビット、　ＨＣＡＲＲＹ−（５２１Ａ−Ｈ）はゼロである。加算の双方の半部中 に、選択加算器からの現在のキャリービット（Ｃａｒｒｙ−、５２４Ａ−Ｈ）は 、特殊ＭＯＤ３加算器に加算されて、次にＭＯＤ３がチェックコードから減算さ れて最終チェックコードＦＳＷＣＣ−（５２９Ａ−Ｄ）を生成する。これは、キ ャリーの存在において正しく保つためにパラメータの１６ビツト半部の各々に対 してチェックコードを必要とする。ＭＯＤＢＸ算器が第２５図に示されている。

リクエストタイプは、ＲＣＶ−ＰＡＲＡＭ−Ａ　（３０３）及びＲＣＶ−ＰＡＲ ＡＭ−Ｂ（３０４）中に、リクエストと共に送出され、全て他の時間において無 視される。アンドゲートのグループ２０１８　（第２１図）は、リクエストがそ の特定の右の端子に使用されていなければ「ノーリクエスト」を出す。送出した リクエストタイプはＦＳＷＴＹ−（５３０Ａ−Ｄ）である。送出したデータ信号 はＦＳＷＤＴ　（５２８Ａ−Ｄ）である。

第１１図において、選択加算器（５２０）の出力は、２つのリクエスト及び順方 向パラメータを右のバッファ（１０５）に送り、そして他のレジスタ（５３５） が記憶したレスポンスパラメータをスライダー（１０３）に送る。右のバッファ （１０５）がＲＣＶ−ＰＡＲＡＭ−Ｂ　（３０４）、ＳＮＤ、−ＲＥＳＰＪ（３ ０５）、５ＮＤＪＥＳＰＪ（３０６）及びＲＣＶ−ＲＥＱｊ　（３０１）中に、 次のステージにデータ及びチェックコードアウトを送る。左のバッファ（１００ ）内に入るリクエストと右のバッファ（１０５）から出るリクエストとの間の３ つのフェーズオフセット（ｐｈａｓｅ　ｏｆｆｓｅｔ）に注目。レスポンスデー タ及びチェックコードはＲＣＶ−ＲＥＱ−Ｂ　（３０２）及びＲＣＶ−ＰＡＲＡ Ｍ−Ａ　（３０３）中に、次のステージから受けとられる。

リクエストタイプは、ＲＣＶｊＡＲＡＭＪ　（３０４）及び５ＮＤ−ＲＥＳＰ− Ａ（３０５）中に、次のステージから送られる。ハンドシェイク信号が、５ＮＤ −ＲＥＳＰＪ　（３０６）及びＲＣＶ−ＲＥＱ−Ａ　（３０１）中にクイブライ ン上で次のステージから受けとられる。レスポンスタイプはＲＣＶ−ＲＥＱＪ　 （３０２）及びＲＣＶ−ＰＡＲＡＭ−Ａ　（３０３）中に次ノステージから受け とられる。ハンドシェイク論理（５５７）が第２６図に示されている。ハンドシ ェイク誤りが起これば、誤り制御（１０１）はラインＨＡＮＤＥＲＲ，−（５５ ９Ａ−Ｄ）を経て、経路が問題を有していることを通知される。

スライダー（１０３）は２部分のＲＡＭより成っており、第１２図に示されてい る。第１の部分、ＲＡＭ−ＬＳ　（６０３）は８８ビツトワイド及び２２ワード デイープ（ｄｅｅｐ）である。第２の部分、ＲＡＭＪＳ（６０６）は７２ビツト ワイド及び３２ワードデイープである。スライダーリセットコントロール（６０ ３）が２進１００（４デシマル）を全てのＪＳＥＬ　（５１３Ａ−Ｄ）位置にロ ードし、ＲＥＳＥＴ　（６１１）がアクティグであるときＯを全てのＲＡＭ位置 内にロードする。

２進１００は「ノーリクエスト」を示す。スライダーリセットコントロール（６ １３）はＲＡＭ−（６０３，６０６）の全３２アドレスをステップすることによ って作動し、データライン（５１２、５１３Ａ−Ｄ。

５３７Ａ−Ｄ、　５３８Ａ−Ｄ）に正しい値を押し込み、ライトイネーブルライ ン（Ｗｒｉｔｅ　Ｅｎａｂｌｅ　１ｉｎｅ　６０２，６０５　）を各々のアドレ ス中に作動させる。５ビツトライトカウンタ（６０９）及び５ビットリードカウ ンタ（６１２）がある。リードカウンタが０に初期化され、リセット（６１１） がアクティブであるとき、ライトカウンタがステージ遅延（ＳＴＡＧｊＤＥＬＡ Ｙ　）　（６１０）に初期化される。リード及びライトカウンタはスイッチチッ プの全動作中ステージ遅延（６１０）によって常にオフセットされる。ステージ 遅延（６１０）はレスポンスが右のバッファのスイッチチップにカムバックする のが期待されるときを示す。

ライト及びリードカウンタの双方は、カウンタの１つがクロックスタート中余分 の時間進む可能性を避けるために、同時に進められる。ＲＪＬＳ　（６０３）は 、ＲＣＶ−ＲＥＱ−Ｂ　（３０２）中に７．ｔ−スゼロアドピット（ＺＥ−、５ １２Ａ−Ｄ）　、逆方向スイッチ設定（Ｂ−３ＥＬ　、　５１３Ａ−Ｄ）、及び 記憶したレスポンスパラメータの第１半部（ＨＦＳＷＤ’ｊ　。

５３７Ａ−Ｄ及びＨＦ５ＷＣＣ−、５３８Ａ−Ｄ）を貯える。記憶したレスポン スパラメータの第２半部がＲＣＶ−ＰＡＲＡＭＪ　（３０３）中のＲＡＭ−ＭＳ 　（６０６）に貯えらえる。記憶した情報は、５ＮＤＪＥＳＰ−Ｂ　（３０６） 中に読出され、将来の使用のためにレジスタ（６２７）に貯えられる。データが 早目に読出され、ＲＡＭ−（６０３，６０６）に書込むとき不一致を避けるため 貯えられる。記憶したレスポンスパラメータの最下位（第１）ハーフがレスポン スセレクタ（１０４）に送られ、そしてＲＣＶｊＡＲＡＭＪ　（３０３）中に使 用される。

記憶したレスポンスパラメータの最上位（第２）ハーフがレスポンスセレクタ（ １０４）に送られ、そして５ＮＤ−ＲＥＳｊＡ　（３０５）中に使用される。不 連続クロックフェーズ中にレスポンスの２半部を計算する計算の理由は、左のバ ッファ（１００）にレジスタを貯えることである。

レスポンスセレクタ（１０４）論理が第１３図に示されている。

右のバッファ・（１０５）からのデータ（ＬＲＳ、Ｄ’ｊ、　５５４Ａ−Ｄ）は 、スライダー（ｓｔｓｓ−［０・・１　］　、　］６２９Ａ−Ｄからの逆方向ス イッチ設定ビットに基づいてマクス（ＭｔｌＸ）　（７０３）によって正しい左 の端子（ＭＵＸＪ’ｊ　、　７０４Ａ−Ｄ）に送出される。フォースゼロアトビ ット（ＳＬＺＥ、　６２ｇＡ−Ｄ）がセットされれば、右のバッファ（１０５） からのデータが無視される。送出したデータ（ＭＵＸ−Ｄ’ｊ　、　７０４Ａ− Ｄ）がビット加算器（７１７）によって記憶したレスポンスパラメータ（ＬＳＤ Ｔ−、６３５Ａ−Ｄ）に加算される。キャリイズ（（ａｒｒｉｅｓ　）がレスポ ンス（ＨＣＡＲＲＹＬＩ−、７２５Ａ−Ｄ）の半部間に貯えらえる。加算器（７ １７）の出力がレジスタ（７１６）に貯えられ、ＨＲ５ＤＴ−（７０ＱＡ−Ｄ） として左のバッファ（１００）に送られる。チェックコード（ＬＲＳＣＣ−、５ ５５Ａ−Ｄ）が同様に正しい左の端子（λ！ＵＪｃｃ−，７０６Ａ−Ｄ）に送出 される。

チェックコード（ＭＵＸ、ＣＣ−、７０６Ａ−Ｄ）は、記憶したチェックコード （ＳＬＣＧ−、６３６Ａ−Ｄ）に加えたＭＯＤ３であり、記憶したキャリービッ ト（）ＩＣＡＲＲＹ−、７２５Ａ−Ｄ）に加えられる。現在のキャリービット（ ＣＡＲＲＹ−，７１９Ａ−Ｄ　）はチェックコードから引かれたＭＯＤ３である 。チェックコードはレジスタ（７６１）に貯えられ、ＨＲ３ＣＣ−（７０１Ａ− Ｄ）として左のバッファ（１００）に送られる。またレスポンスセレクタ（１０ ４）は入りデータ経路（５５４Ａ−Ｄ、　５５５Ａ−Ｄ）上にＭＯＤ３チェック （第１５図）を送る。いかなる誤りもＭＩＸ（７３１）が誤りレスポンスをタイ プルーティング（ｔｙｐｅ　ｒｏｕｔｉｎｇ）　ＭＬＩＸ　（７３５）に押し込 む場合、ＭＩＸ（７３１）により正しい左の端子に送出される。レスポンスタイ プはＭＩＸ（７３５）により正しい左の端子に送出される。

逆方向スイッチ設定ライン（ＳＬＳＳ−［２］　、　６２９Ａ−Ｄ）がセットさ れ（レスポンスが期待されないことを示して）、レスポンスが受信されるか、又 はチェックコード誤りが起きれば、大レスポンスタイプが無視され、そして誤り タイプがラインＨＲＳＴＹ　（７０２Ａ−Ｄ）上を左のバッファ（１００）に送 られる。誤りがなければ、レスポンスタイプは正しい左の端子に送出されて、ル ート割当てプロセスを終了する。

ベースうイ〉λ・ソトつ−７ 耐ち臼べ＝τン）ット・フード ０　−　へ　ｎ　マ　Ｇ　Φ　Ｎ べ ０−へ１？ｆ１ψトロの９＝ツつ！す！セ！色８＆沼＝品＝真に冗＝宮ぢ０　− 　へ　約　ぐ　□　ψ　Ｎ 呼拘λｔ７′３判費 ｈ）餡　＼言、ｎ　：１１イ）？ １ν１１つ゛）？− ？へヒ夷遂衿イえ一アＩＬ−ｉち 冬〉久Ｌゾ゛ス９ｔテλト久 （イ’ｌ−１ｊ’ｌ　４９＜ムス） （イγ￥９４タイζλ） ＳＮ　Ｒ２５Ｗ３　ＴＺＥ２ ；：淋：ｏＨＨＴｒＳ＋、′ｃ８＝ｑｐ＋ｏｃｃｖｐ＋。４１７Ｄ１６０９Ａ　 ＲＯＧＥＴＰＯＣＢ＝［Σ→ＲＯＧＥＴＰＯＣ４１７８ＲＯＧＥＴＰＩＳ　４１ ７０ ＲＯＧＥＴＰＯ５４１７Ａ に１％％　Ｓ鼾Ｓ”：＝Ｓ　：＝＝に〉−一〉ＲＩＧＥＴＰＩＣ４１７Ｈ閤Ａ　 Ｒ１：ＥＴＰＯＣＡ　ｎ→・・・ε・〜Ｃ４１７ＦＦＴＩＧＥＴＰＩＳ　４１７ Ｇ ＲＩＧＥＴＰＯ５４１７Ｅ １６２５Ａ　Ｒ２ＧＥＴＰＩＣＡ １６３４Ａ　ＲＺＧＥＴＰＩＣＢ　ｍ口ｘ０Ｒ２ＧＥＴＰＩＣ４１７Ｌ１６２７ Ａ　Ｒ２ＧＥＴＰＯＣＡ ＋６３２ＡＲ２ＧＥＴＰＯＣＢ　３→Ｒ２ＧＥＴＰＯ（：　４１７ＪＲ２ＧＥＴ ＰＩＳ　４１７Ｋ Ｒ２ａＣｒｐｏｓ　４ｆ７Ｔ Ｉ６４４Ａ　Ｒ３ＧＥＴＰＯＣＢ　１Σ−＋　ＲｓｃＥｒｐｏｃ　４１７ＮＲ３ ＧＥＴＰＩＳ　４１７０ Ｒ３ａＥＴｐｏｓ　４１７Ｍ ４４５Ｑ　ＮＥＩＡＩ−Ｒ３ＧＥＴＰＩＳ４：３４Ａ　５ＮＲＯＦＡＩ　ｒ＋Ｆ ｏａｏｏ＋　５０５Ｂ４：Ｓ４Ｂ　５ＮＲＯＦＡ２　ＴＨＦＯＡＣＩＤ２５０５ Ｃ４３４Ｃ５ＮＲＯＦＡ３　ＴＨＦＯＡＤＤ３５０５Ｄ４３５Ａ　５ＮＲＯＳＷ Ｉ　ＴＨＦＩＡＤＤＯ５０５Ｅ４３４［）　５ＮＦｌｌＦＡ２　ＴＨＦＩＡＤＤ ２　５０５Ｇ４３４Ｅ　５ＮＲＩＦＡ３　ｙ＋ｒ＋Ａｏｏ３５０５ＨＳＮＲＩＳ Ｗ２　Ｔ）ＩＦ２ＡＤＤｌ　５０５Ｊ４３５Ｆ　５ＮＲ２ＳＷ３　ＴＨＦ３ＡＤ Ｃ）２５０５０ど 国際調査報告 １ｍ−Ｈ門−１−１１ｅＭｌｉｌ１６’ｔｃａＬｓ’＋１１１１．ｐｃτ／Ｌテ ＳεＢ１０３６０Ｂ国際調査報告 １　： □ ！ ・′１ □ ！ ］ □ １　：

Claims (14)

【特許請求の範囲】
1. １．Ｎ個までのレスポンダー手段をＮ個までのリクエスター手段に接続するネツ トワーク相互接続システムにおいて、各々がＮ個のスイツチ手段を有しているＳ ステージのスイツチ手段と、 但し、この場合、Ｓは［（ｌｏｇｂＮ）＋１］に等しく、ｂは１よりも大きい選 択された整数の対数のベースである、リクエストポートを具備しており、前記ス イツチ手段のリクエストステージを除く、前記スイツチ手段の各々に対するｂ× Ｐの第１の端子手段と、 レスポンスポートを具備しており、前記スイツチ手段のレスポンスステージを除 く、前記スイツチ手段の各々に対するｂ×Ｐの第２の端子手段とを具備しており 、 但し、この場合Ｐは１よりも大きい選択した整数である、前記スイツチのリクエ ストステージの各々のスイツチ手段が、前記リクエスター手段の単一の１つに接 続可能である出力端子手段を有し、 前記リクエスター手段に近いステージのスイツチ手段に結合されている各々の第 ２の端子手段が前記レスポンダー手段に近いステージのスイツチ手段に結合され ている第１の端子手段に接続可能であるように、前記スイツチ手段の第１及び第 ２の端子手段が、夫々、他のステージの出力及び入力端子手段に接続可能であり 、但しこの場合、前記スイツチ手段の前記Ｓステージは、ステージＯがリスエス トステージであり、ステージＳ−１がレスポンスステージであるように０乃至Ｓ −１のように示される、前記Ｎ個のスイツチ手段が、ｂの、Ｓ−１デイジツト、 非負の整数によつて表わされる０乃至Ｎ−１として各々のステージ内に示されて いて、 前記ｂ×Ｐの第１及び第２の端子手段が各々Ｐ平面にグループに分けられていて 、それ等のＰ平面が０乃至Ｐ−１で示されており、且つ平面当り０乃至ｂ−１で 示されるｂ端子より成つており、前記第１及び第２の端子手段の各々が４つのパ ラメーターによつて表わされており、それ等のパラメーターがそれぞれステージ パラメーター、スイツチパラメーター、平面パラメーター、及びデイジツトパラ メーターであり、 但しこの場合に、前記スイツチパラメーターが各々ｌｏｇｂＮデイジツトによつ て表わされ、前記デイジツトパラメーターの各々が単一のｂのデイジツトによつ て表わされており、前記第２のステージパラメーターが前記第１のステージパラ メータープラス１と同じステージを表わし、前記平面パラメーターが同じ平面を 表わし、前記第１のステージ及び第２のステージの前記スイツチ及びデイジツト パラメーターが、所定の関係によつて決定され、１つのステージの前記第１の端 子の各々における、その結果が、他のステージの前記第２の端子の１つのみに殆 んど接続されることを特徴とするネツトワーク相互接続システム。
2. ２．Ｐ＝ｌｏｇｂＮ、及びｂとＮがＰに対して整数を生ずるように選択される請 求項１に記載のネツトワーク相互接続システム。
3. ３．ｂ＝２である請求項１に記載のネツトワーク接続システム。
4. ４．Ｎ個までのレスポンダー手段をＮ個までのリクエスター手段に接続するネツ トワーク接続システムにおいて、Ｑスイツチ手段を具備し、この場合にＱがＣ× Ｓに等しく、Ｓが［（ｌｏｇｂＮ）＋１］に等しく、ｂが選択した対数ベースで あり、Ｃが、前記ネツトワークにおけるスイツチ手段の同じ縦列接続グルーブの 数を表わす整数であり、その各々のグループがＳスイツチ手段を有しており、 前記スイツチ手段の前記Ｓステージが、ステージ０がリクエストステージであり 、ステージＳ−１がレスポンスステージであるように、０乃至Ｓ−１として示さ れていて、前記Ｎ個のスイツチ手段が、ｂのＳ−１デイジツト、非負の整数によ つて表わされる０乃至Ｎ−１として各々のステージ内に示されており、 前記ｂ×Ｐの第１及び第２の端子手段が各々Ｐ平面にクループに分けられていて 、それ等の平面が０乃至Ｐ−１として示されており、且つ平面当り０乃至ｂ−１ で示されているｂ端子より成つていて、 前記第１及び第２端子手段が各々４つのパラメーターによつて表わされていて、 それ等がそれぞれステージパラメータ、スイツチパラメーター、平面パラメータ 及びデイジツトパラメーターであり、前記スイツチパラメーターの各々がｌｏｇ ｂＮデイジトによつて表わされ、前記デイジツトパラメーターの各々が単一のｂ のデイジツトによつて表わされ、前記第２のステージバラメーターが前記第１の ステージパラメータープラス１と同じステージを表わし、前記平面パラメーター が同じ平面であり、前記第１ステージ及び前記第２のステージの前記スイツチ及 びデイジツトパラメーターが所定の関係によつて決定され、１ステージの前記第 １の端子の各々のその結果が、他のステージの前記第２の端子の１つのみに殆ん ど接続されていることを特徴とするネツトワーク相互接続システム。
5. ５．Ｐ＝１ｏｇｂＮ、及びｂとＮがＰに対して整数を生ずるように選択される請 求項４に記載のネツトワーク相互接続システム。
6. ６．ｂ＝２である請求項５に記載のネツトワーク相互接続システム。
7. ７．Ｏ乃至Ｓ−１のナンバーのステージに配置された複数のスイツチ手段と、 但し、この場合、Ｓ−１はシステムの最高ナンバーのステージであり、各々のス テージが等しいナンバーの前記スイツチ手段を有しており、前記スイツチ手段の 各々が、ステージ０の前記スイツチ手段を除き複数の第１の端子手段を具備し、 前記ステージ０の前記スイツチ手段がリクエスト端子手段に接続した単一の第１ の端子手段を具備しており、前記スイツチ手段の各々が、ステージＳ−１の前記 スイツチ手段を除き、複数の第２の端子手段を具備し、そして前記ステージＳ− １の前記スイツチ手段がレスポンス端子手段に接続した単一の第２の端子手段を 具備しており、前記スイツチ手段の与えられた１つの任意の単一の第１の端子手 段を前記同じスイツチ手段の任意の単一の第２の端子手段に選択的に結合する接 続手段と、 リクエストコードを受信し、そして前記第１のトランシーバー手段と、 レスポンスコードを受信し、そして前記第２の端子手段を経てリクエストコード を送信する第２のトランシーバー手段と、前記記憶手段にアクセスし、且つ下記 のシナリオの１つによつて前記相互接続手段を制御する制御手段を具備し、（ａ ）一定のスイツチ手段の第１の端子手段が次の低いナンバーのステージのリクエ スティンクスイツチ手段の第２の端子手段への接続をリクエストされていれば、 あるいは出力端子手段が、所定の時間期間中、ステージＳ−１のりクエステイン グスイツチ手段によつてリクエストされていれば、前記リクエスティンクスイツ チ手段と同じステージの他のスイツチ手段が、前記一定のスイツチ手段の任意の 第１の端子手段、又は前記時間期間中に、前記出力端子手段をリクエストしてい なければ、前記リクエストした第１の端子手段、又は前記出力端子手段が、リク エステインクスイツチ手段の第２の端子手段に接続されるか、又は、 （ｂ）前記リクエストしたスイツチ手段の１以上の前記第１の端子手段が、ステ ージＳ−１以外の、リクエスティンクスイツチ手段と同じステージの他のスイツ チ手段によつてリクエストされているかあるいは出力端子手段が、前記時間期間 中にステージＳ−１のリクエステインクスイツチ手段によつてリクエストされて いれば、前記リクエストした第１の端子手段、又は前記出力端子手段が前記所定 の時間期間中に前記記憶手段に記憶されたレスポンスコードから前記制御手段に より引き出されたあらかじめ定めたレスポンスコード優先権によつてリクエステ ィンクスイツチの第２の端子手段に接続される請求項ｂに記載のネツトワーク相 互接続システム。
8. ８．前記優先権機構が、前記リクエストコードと共にパラメーターコードを送る ことによつて実施され、前記記憶手段が前記パラメーターコードを記憶し、この 場合に前記一定のスイツチ手段の識別した第１及び第２の端子手段、又は識別し た第１の端子手段及び出力端子手段が、前記リクエストしたスイツチ手段の前記 第１の端子手段によつて受信した２またはそれ以上の識別したリクエストコード に結合されるとき、前記パラメーターコードが前記レスポンスコードを結合する ために前記制御手段によつて利用され、前記結合したレスポンスコードが前記制 御手段によりデコムバインされて、前記識別した第１及び第２の端子手段、又は 前記識別した第１の端子手段を接続するための前記優先権機構を確立している請 求項７に記載のネツトワーク相互接続システム。
9. ９．前記優先権機構が、２つまたはそれ以上のレスポンスコードが前記リクエス ティンクスイツチ手段に結合されるとき、前記リクエスティンクスイツチ手段の 前記第２の端子手段中に継続的に優先順位を確立するフエツチーアンドー変更動 作と、前記リクエスティンクスイツチ手段の前記第２の端子手段中に逆方向の継 続的順位を確立するスワップ動作とを利用する請求項８に記載のネツトワーク相 互接続システム。
10. １０．前記制御手段が、前記動作の他のものに優先して前記フエツチーアンドー 変更及び前記スワツプ動作の１つを延滞する請求項９に記載のネツトワーク相互 接続システム。
11. １１．ネツトワーク相互接続システムにおいて、０乃至Ｓ−１のナンバーのステ ージに配置された複数のスイツチ手段と、 但しこの場合、Ｓ−１がシステムの最高ナンバーのステージであり、各々のステ ージが等しいナンバーの前記スイツチ手段を有し、前記スイツチ手段の各々がス テージ０の前記スイツチ手段を除き、複数の第１の端子手段を具備し、前記ステ ージ０の前記スイツチ手段が、リクエスト端子手段に接続した単一の第１の端子 手段を具備し、前記スイツチ手段の各々が、ステージＳ−１の前記スイツチ手段 を除き、複数の第２の端子手段を具備しており、前記ステージＳ−１の前記スイ ツチ手段が、レスポンス端子手段に接続した単一の第２の端子手段を具備してい る、 前記スイツチ手段の与えられた１つの任意の単一ま第１の端子手段を前記同じス イツチ手段の任意の単一の第２の端子手段に選択的に結合する相互接続手段と、 リクエストコードを受信し、且つ前記第１の端子手段を経てレスポンスコードを 送信する第１のトランシーバー手段と、レスポンスコードを受信し、且つ前記第 ２の端子手段を経てリクエストコードを送信する第２のトランシーバー手段と、 前記記憶手段にアクセスし、且つ下記のシナリオの１つにより前記相互接続手段 を制御する制御手段とを具備しており、（ａ）一定のスイツチ手段の第１の端子 手段が次の低いナンバーのステージのリクエスティンクスイツチ手段の第２の端 子手段への接続をリクエストされていれば、あるいは出力端子手段が、所定の時 間期間中、ステージＳ−１のリクエスティンクスイツチ手段によつてリクエスト されていれば、そして前記リクエスティンクスイツチ手段と同じステージの他の スイツチ手段が、前記一定のスイツチ手段の任意の第１の端子手段、又は前記時 間期間中に、前記出力端子手段をリクエストしていなければ、前記リクエストし た第１の端子手段、又は前記出力端子出力手段が、リクエストしているスイツチ 手段の第２の端子手段に接続されるか、又は、（ｂ）前記リクエストしたスイツ チ手段の１以上の前記第１の端子手段が、ステージＳ−１以外の、リクエスティ ンクスイツチ手段と同じステージの他のスイツチ手段によつてリクエストされて いるかあるいは出力手段が、前記時間期間中にステージＳ−１のリクエスティン クスイツチ手段によつてリクエストされていれば、前記リクエストした第１の端 子手段、又は前記出力端子手段が、前記所定の時間期間中に前記記憶手段に記憶 されたレスポンスコードから前記制御手段により引き出されたあらかじめ定めた レスポンスコード優先権によつてリクエステインクスイツチの第２端子手段に接 続していることを特徴とするネツトワーク相互接続システム。
12. １２．前記優先権機構が、前記リクエストコードと共にパラメーターコードを送 ることによつて実施され、前記記憶手段が前記パラメーターコードを記憶し、こ の場合に前記一定のスイツチ手段の識別した第１及び第２の端子手段、又は識別 した第１の端子手段及び第２の端子手段が、前記リクエストしたスイツチ手段の 前記第１の端子手段によつて受信した２又はそれ以上の識別したリクエストコー ドに結合されるとき、前記パラメーターコードが前記レスポンスコードを結合す るため前記制御手段によつて利用され、前記結合したレスポンスコードが前記制 御手段によりデコムバインされて、前記識別した第１及び第２の端子手段、又は 前記識別した第１の端子手段及び出力端子手段を確立している請求項１１に記載 のネツトワーク相互接続システム。
13. １３．前記優先権機構が、２つまたはそれ以上のレスポンスコードが前記リクエ スティンクスイツチ手段に結合されるとき、前記リクエスティンクスイツチ手段 の前記第２の端子手段中に継続的に優先順位を確立するフエツチーアンドー変更 動作と、前記リクエスティンクスイツチ手段の前記第２の端子手段中に逆方向の 継続的順位を確立するスワツプ動作とを利用する請求項１２に記載のネツトワー ク相互接続システム。
14. １４．前記制御手段が、前記動作の他のものに優先して前記フエツチーアンドー 変更及び前記スワツプ動作の１つを延滞する請求項１３に記載のネツトワーク相 互継続システム。