JPH02503244A - メッセージパケットのルーティング方法とその装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 メツセージパケットのルーティング方法とその装置関連出願の引用 関連出願は以下のとおりである。

・　「並列処理装置」　（出願番号４９９，４７４）および「並列処理装置／記 録回路」　（出願番号４９９，４７１）、いずれも１９８３年５月３１日比願。

・　「メツセージパケットのルーティング方法とその装置」　（出願番号６７１ 　、８３５）、１９８４年１１月１５日出願、現在米国特許４，５９８，４００ ゜ ・　「ハイパー次元配列における処理処置の相互接続方法とその装置」　（出願 番号７４０，９４３）、１９８５年５月３１日出願。

・　ｒ大容量コンピュータ」　（出願番号９０２，２９０）、１９８６年８月２ ９日出願。

・　ｒ大容量並列処理装置」　（出願番号９２４，０９０）、　１９８６年１０ 月２８日出願。

発明の背景 本発明はメツセージパケットのルーティング方法とその装置に係わり、特に前記 関連出願４９９，４７１および４９９．４７４ならびに前記米国特許４，５９８ ，４００で開示された大容量並列処理装置においてメツセージパケットのルーテ ィングに適する方法と装置とに関する。

第１図に米国特許４，５９８，４００の第１Ａ図を再録した。

第１図において、当該アプリケーションのコンピュータシステムは、メインフレ ームコンピュータ１０．マイクロコントローラ２０、並列処理集積回路３５から なる配列３０、データソース４０．第一バッファおよびマルチプレクサ／デマル チプレクサ５０．第一、第二、第三、第四両方向バス制御回路６０．６５．７０ ．７５、第二バッファおよびマルチプレクサ／デマルチプレクサ８０、ならびに データシンク９０を有して構成されている。メインフレームコンピュータ１０は 、デジタルエクイブメント社ラムを具備する市販の汎用コンピュータである。マ イクロコントローラ２０は、一連の命令を生成する既存設計の命令シーケンサで ある。これらの命令は、３２ビツトの並列バス２２を介して配列３０へと印加さ れる。マイクロコントローラ２０は１回線２６を介して配列３０から信号を受は 取る。この信号は汎用（Ｇ　Ｌ　ＯＢ　Ａ　Ｌ）信号であり、データ出力情報と 状態情報に使用できる。バス２２と回線２６はそれぞれの集積回路３５に並列に 接続されている。このため、マイクロコントローラ２０からの信号は、配列３０ 内の各集積回路３５に同時に印加される。

また、回線２６を介し、てマイクロコントローラ２０に印加される信号は、配列 内にあるすべての集積回路３５からの信号出力を組合せることによって生成され る。

配列３０は、数千におよぶ同−型の集積回路３５を具備している。各集積回路３ ５は、数個の同−型のプロセッサ／メモリ３６を含む、米国特許４，５９８，４ ００で開示された実施例では、この配列に最大３２．７６１１１個（＝２”）の 同−型の集積回路３５を具備できる。各集積回路３５は、３２個（＝２″）の同 −型のプロセッサ／メモリ３６を内蔵することができる１本特許の出願の時点で 、同−型のプロセッサ／メモリ２６個（＝２’）をそれぞれ具備する同−型の集 積回路３５を最大４　、０９６個（＝２”）内蔵した配列が、被譲渡人によって 製造され、「コネクション・マシン」　（登録部ｍｌ）コンピュータとして出荷 された。

米国特許４，５９８，４００のプロセッサ／メモリ３６は、二種類の構成によっ て組織され、相互接続されている。

そのうち、第一の構成は、従来の二次元のグリッドパターンである。このパター ンでは、プロセッサ／メモリは長方形の配列に構成され、各プロセッサ／メモリ は、配列内で隣接するもっとも近い４個のプロセッサ／メモリに接続されている 。説明の便宜を図るため、この配列の各面を「北」、「東」、「南」、「西」と それぞれみなす、各プロセッサ／メモリを、隣接するもっとも近いプロセッサ／ メモリに接続する場合、個々のプロセッサ／メモリは、導体を介してグリッドの 各行、各列において相互接続されている。

第二の構成は、プールｎ次元立方体の構成である。

ｎ次元立方体接続パターンを理解する場合、（１５次元の立方体であれば）集積 回路を０から３２，７６７まで番号付けし、１５個の２進ビツトを使用してこれ らの番号を２進法で表示すると便利である。ある物体の二次元グリッドにおける 位置は数字２個で指定できる。２個の数字のうち、１個は二次元グリッドにおけ る第一次元の位置を指定し、他の１個は同グリッドにおける第二次元の位置を指 定する。同様に、１個の数字を使用して、プール１５次元立方体の各次元におけ る各集積回路の位置を指定できる。ただし、ｎ次元立方体においては、集積回路 は、０ないし１の２個の異なる位置のいずれかのみを各次元で取ることができる 。このように、１５ビツトの集積回路の２進アドレスは、ｎ次元立方体の１５の 次元における集積回路の位置の指定に使用することが可能であり、また実際に使 用されている。さらに、各２進ビツトは、Ｏまたは１のいずれかの値のみ取るこ とができ、各集積回路は１５個の２進ビツトによって一意に指定される。このた め、各集積回路に対し、そのアドレスと１ビツトのみ異なる２進アドレスをそれ ぞれ有する１５個の集積回路がある。こうしたアドレスを有する集積回路を、各 集積回路の最近接回路と呼ぶ、ハミング距離の数学上の定義を熟知する技能者は 。

各集積回路がその１５個の最近接回路からハミング距離１で隔てられていること を理解することができよう。

前記のアプリケーションの集積回路３５をプール１５次元立方体として接続する ためには、各集積回路を１５本の入力回線３８と１５本の出力回線３９とを介し て１５個の最近接回路へと接続する。各集積回路３５に接続されたこれら１５本 の入力回線３８は、プール１５次元立方体の各次元にそれぞれ対応している。同 様に、各集積回路３５からの１５本の出力回線３９も、プール１５次元立方体の 各次元にそれぞれ対応している。ｎ次元立方体の配線の詳細については、前記引 用の出願第７４０，９４３号に記されている。

プールｎ次元立方体の相互接続パターンによって通信を行なうため、演算の結果 をメツセージパッケージの形式で組織化する。これらのパッケージは、その一部 を構成するアドレス情報に従い、各集積回路に内蔵されたルーティング回路を介 して隣接する集積回路の間を転送される。

各集積回路３５は、米国特許第４，５９８，４００号の第７Ａ図、および出願番 号９２４，０９０　ｒ大容量並列処理装置」の第４図ならびに第６図に詳細に開 示された複数のプロセッサ／メモリを具備する。第７Ａ図に示されるように、プ ロセッサ／メモリ３６は、ランダムアクセスメモリ（ＲＡＭ）　２５０．論理演 算装置（ＡＬＵ）２８０、およびフラグコントローラ２９０を有する。ＲＡＭ２ ５０への入力には、米国特許第４，５９８，４００号の第６Ｂ図記載の通信イン ターフェース装Ｗ　（ＣＩ　Ｕ）　１８０から出ているメツセージパケット入力 回線１２２が含まれる。

ＲＡ　Ｍ　２５０からの出力は、Ａ　Ｌ　Ｕ　２８０へと至る回線２５６．２５ ７からなる。ＡＬＵは、三種類のソース、すなわちＲＡＭ内の２個のレジスタと １個のフラグ入力とから与えられるデータの演算を行ない、２個の出力を生成す る。一方の出力は、回！！　２８５上の合計出力であり、これはＲＡＭレジスタ のひとつへと書き込まれる。他方の出力は１回線２８７上の桁上げ出力であり、 これはフラグコントローラ内の特性のレジスタで利用でき。

メツセージパケット出力回線１２３を介して通信インターフェース装置１８０へ と転送することが可能である。

かかるプロセッサ／メモリの代替設計が、出願番号９２４．０９０　ｒ大容量並 列処理装置」に開示されている。

該出願の第４図と第６図に示されるように、プロセッサとメモリは、同一の回路 基板に配されて独立した集積回路３３４および３４０に内蔵されている。各集積 回路３３４は、１６個の同−型のプロセッサ３３６、制御袋！３３７、ルータ３ ３８．およびメモリインタフェース３３９からなる。

メモリインタフェースは、集積回路３３４の１６個のプロセッサを、対応する各 メモリへそれぞれ接続している。

これらのメモリは、たとえば６個の独立した集積回路３４０上に配置される。ル ータ３３８は、　１２次元のハイパーキューブに接続された１２個の最近接ルー タに、１６個のプロセッサを接続している。

さらに各集積回路３５は、集積回路上のプロセッサ／メモリに対応する監視回路 と、各集積回路をプールｎ次元立方体の最近接回路へと接続すためのルーティン グ回路とを具備する０本出願の第２図は、米国特許第４．５９８，４００号の第 ６Ｂ図を再現したものである。第２図に示されるように、前記監視回路は、タイ ミング発生器１４０．プログラム可能論理回路１５０．および通信インタフェー ス１８０からなる。プログラム可能論理回路１５０は、マイクロコントローラ２ ０から送られた命令をデコードして集積回路のプロセッサ／メモリへと送る。

通信インタフェース１８０は、各集積回路のプロセッサ／メモリと、当該集積回 路に対応するルーティング回路２００との間で交換されるメツセージパケットの フローを制御する。

ルーティング回路２００は、プールｎ次元立方体における最近接集積回路間にお けるメツセージパケットのルーティングを制御する。この回路は１回線割当て器 ２０５、メツセージ検出器２１０、バッファ／アドレス復元器２１５．およびメ ツセージ注入器２２０からなる。これらの構成部品は、上記の順序で直列に接続 されてループを形成している。このため、各構成部品の出力は１次の段階で構成 部品の入力へと供給される。メツセージ注入器２２０の出力は１回線割当て器２ ０５へと供給される。

回線割当て器２０５は、入力回線３８で受信したメツセージパケットのアドレス を分析して、これらのパケットが当該集積回路に送られたか、もしくは他の集積 回路に送られたものかを決定する０回線割当て器は、受信したメツセージパケッ トを可能な限りその宛先へと転送する。当該集積回路に送られたメツセージパケ ットと１回路の割当て上の競合のため転送できないメツセージパケットは、すべ てこの回線割当て器が蓄積する６回線割当て器２０５は、同一型のルーティング 論理セルからなるＩｓ　Ｘ　１５の配列４００を具備する。この配列の各行は、 ルーティング回路２００でのメツセージパケット１個の蓄積を制御する。

メツセージ検出器２１０は、メツセージパケットの受信を確認し、回線割当て器 から回線２０７へと送られたメツセージパケットのアドレスを検査し、当該集積 回路に宛れられたこれらのメツセージパケットを１通信インタフェース１８０へ と供給する。バッファ／アドレス復元器２１５は、タップシフトレジスタを有す る。バッファ／アドレス復元器の出力は、メツセージ注入器へと供給される。メ ツセージ注入器２２０は、１回につき１個のメツセージパケットを１通信インタ フェース１８０から、ルーティング回路を循環しているメツセージパケットのグ ループ内へと注入する。

ルーティング回路からの信号は、回線１９７，１９８゜１９９を経て通信インタ フェースＣＩ　Ｕ１８０への供給される。信号回線１９７は、入力メツセージパ ケットがルーティング回路から得られるかどうかを示す０回９１９８は、入力メ ツセージパケット自体を示す０回線１９９は、回線１９θ上の出力メツセージパ ケットが、ルーティング回路によって成功裏に受信されたものかどうかを示す０ 回線１９４上の信号は、ルーティング用のメツセージパケットがいつ得られ、か っこのメツセージパケットがいつ回線１９６上に出力されるかを示す。

ルーティング上の競合が発生しなければ、メツセージパケット１個が、−次元の ルーティングセルへの入力から、プロセッサ／メモリ内のレジスタのうち、１回 のメツセージサイクルで宛先の指定を受けたレジスタ１個へと転送される。ルー ティング上の競合が発生した場合、メツセージパケットが、１個ないし複数の中 間点で、ルーティング回路の処理蓄積手段によって一時的に蓄積される。メツセ ージパケットをその宛先に送達するためには、複数のルーティングサイクルを必 要とする。

発明の要約 本発明は、パケットの指定する宛先へとメツセージパケットを送達するための改 良型ルーティング回路に係わる０本発明では、大容量並列式コンピュータでメツ セージパケットのルーティングを行なう場合に特に有効であるため、この観点か ら本発明について説明する。

本発明による集積回路のルータは、米国特許第４，５９８，４００号で説明され た機能と同一の機能を提供する。すなわち、メツセージパケットが当該集積回路 を宛先として指定されているかどうかを決定する機能。

可能な場合はメツセージパケットをその宛先へと転送する機能、および当該集積 回路宛てのメツセージパケットならびに回路競合のため転送できないメツセージ パケットを蓄積する機能である。

またこのルータは、次のような機能も提供する。すなわち、同一の宛先を有する メツセージパケットをマージする機能、メツセージルーティングサイクルの各有 意点におけるルータの状態を保管する機能、およびルーティングサイクル全体を 逆方向に進める機能である。この最後の機能により、配列内の特定のプロセッサ に対して、メツセージパケットを選択的に同報通信することができる。

本発明の実施例は１次のような手段を有する。すなわち、送信元プロセッサから 宛先プロセッサへと送られるメツセージパケットを蓄積する手段、メツセージパ ケットを、送信元プロセッサと宛先プロセッサとの間にあるノードに接続された 通信回線へ選択的に接続するための手段、宛先プロセッサにルーティングされる べく指定されたメツセージパケットを、送信元プロセッサの待ち行列に選択的に 挿入するための手段、宛先プロセッサの前記メモリから、該プロセッサに宛てら れたメツセージパケットを選択的に削除するための手段、第一のプロセッサから 第二のプロセッサへとメツセージパケットが転送される工程において、前記の選 択的接続手段１選択的挿入手段、および選択的削除手段が、おのおのの動作の段 階を順次経過する際の。

それぞれの作動状態を記録するための手段、および前記の選択的接続手段、選択 的挿入手段、選択的削除手段の作動状態を、前記プロセッサ間でのメツセージパ ケットの転送ルートの逆の順序で再現し、これによって第二のプロセッサから第 一のプロセッサへとメツセージパケットを転送するための手段を有する。

図面の簡単な説明 本発明の前記その他の諸目的、特徴ならびに利益は。

以下の実施例の説明ならびに添付図面から明瞭になろ第１図は本発明を適用した 大容量並列処理装置の概略図、第２図は先行技術によるルーティング回路の概略 図、第３図は本発明の一実施例を構成する集積回路の概略図、第４図は、第３図 の集積回路のひとつに含まれるプロセッサの概略図、第５図は、第３図の集積回 路のひとつに含まれるルータの概略図、および第６図から第１６図までは、第５ 図のルータの詳細を示す図面である。

発明の詳細な説明 本発明は、単一命令多重データ（ＳＩＭＤ）並列式コンピュータに適用される。

このコンピュータは、たとえば１２８個の回路基板上に配設された６５，５３６ （＝２１＄）個のプロセッサからなる配列を有して構成される。出願第９２４， ０９０号に詳しく説明されているように、できれば、これらのプロセッサは４個 の装置にまとめて収納され、各装置はマイクロプロセッサの制御下に置かれ、か つ各装置は４台のホストコンピュータの１台にそれぞれ接続できることが望まし い、少なくとも該コンピュータの各装置の内部では、プロセッサが並列に運転さ れて、供給されたデータに対して同一の命令が各プロセッサによって同時に実行 されるようになっている。供給されるデータは異なるため、実行の結果はプロセ ッサごとに異なるととがある。このため実際の動作中には命令の完全な実行が抑 止されることがある。

各回路基板には３２個の集積回路が配設されている。

第３図に示すように、これらの集積回路１００は、１６個のプロセッサからなる 配列１１０、交換器１２０、ルータ１３０、メモリインタフェース１４０、およ び制御回路１５０を有して構成される。また各回路基板は、同基板上に設置され た各集積回路の各プロセッサ１１２に対応する４にビットの読出し書込み用メモ リ（ＲＡＭ）１６０を有する。

各集積回路１００は、コンピュータの他の構成部位との接続用に６８個のビンを 有する。これらのビンのうち。

４本は制御ビン１５２．２０本はプロセッサ命令ビン０ＰＯ−ＯＦ２、ｌｏ−１ １６，２２本はメモリビニ／ＭＯ−Ｍ１５およびＥＣＣ０−ＥＣＣ５，１４本は 通信ビン１３２、および８本は電源ビン１０２である。下記の表Ｉでこれらのビ ンの機能をさらに説明する。

以下余白 表１ 舞匙〉 クロック　１　　　人力　　　高　　　　命令実行用のストローブ出カ プロセッサ命令ピン ０ＰＯ−２３人力　　　高　　　　命令の種類通信ビン ラッｆＲ１人力　　　高　　　　ルータ入力のラッチ送）ｍ　　　ｌ　　　入力 　　　低　　　　ル−タ入力の送信Ｃ売く） ４社〉 ＶＤＤ４　　　　電源　　　高　　　　＋５ｖ電源ＶＳＳ４　　　電源　　低　 　　接地 合計　６ １６個のプロセッサ１１２のそれぞれの出力は、幅１６回線分の並列データバス １１４を介して交換器１２０へと供給される。データバスの各回線は、１台のプ ロセッサからの信号をそれぞれ伝送する。交換器は、これらの回線上の信号の交 換や順列を行なう、こうした処理は、現在出願中の［ＭがＮより小さい場合のＮ 次元ネットワークにおけるＭ次元接続ネットワークのシミュレーションの方法と その装置」で詳しく説明されている方法で行なわれる。交換器１２０から出てい る幅１６回線のデータバス１２２は、その出力信号をメモリインタフェース１４ ０および命令ビンｌ０−１１５へと供給する。

メモリインタフェース１４０は、同様に係属中であって１９８６年９月１５日に 出願された「並列処理装置のエラーのチェック方法」　（出願番号９０７，６７ １）、および１９８６年１２月１０日に出願された「エラー制御の方法とその装 置」　（８願番号９３９，５９９）にて詳しく説明されている。

前記出願は、いずれも参照のため本出願で引用している。第３図に示されるよう に、メモリインタフェースは、メモリビンＭＯ−Ｍ１５およびＥＣＣ０−ＥＣＣ ５を介してメモリ１６０に信号を供給し、同じビンを介して該メモリから信号を 受信する。

第３図に示されるように、たとえばメモリ１６０は、各集積回路１００に対応す る２２個の４に×１ピットＲＡＭ集積回路１６２として配設されている。該メモ リ内では、１６個の４ＫＸ１ビツトスライスが、１６個の同−型のプロセッサ１ １２のそれぞれに対応するメモリとして機能する。残りの６個の４に×１ビット スライスは、１６個の同−型のプロセッサのメモリに格納されているデータのパ リティピットまたはシンドロームビットを格納する。各集積回路１００から出て いる２２個のメモリビンＭＯ−Ｍ１５およびＥＣＣ０−ＥＣＣ５は、それぞれ１ 個のＲＡＭ集積回路１６２に接続されている。

集積回路１６２は、アドレスデコーダ１６４によって並列にアドレス指定される 。これにより、アドレスデコーダで指定されたアドレスを有する各集積回路に並 列データが書き込まれ、かつ該回路から並列データが読み出される。実際には、 １個のアドレスデコーダを使用して、１個の回路基板上にあるすべてのＲＡＭ集 積回路１６２の並列アドレス指定、もしくは６５，５３６個のプロセッサで構成 される配列全体のすべてのＲＡＭ集積回路１６２の並列アドレス指定を制御する ことができる。読み出し書込み用メモリ１６０に関しては、前記引用の出願第９ ３９，５９９号で詳細に説明している。

メモリインタフェース１４０から出る信号は１幅１６回線の並列データバス１４ ２を介して、１６個のプロセッサ１１２およびルータ１３０へと供給されている 。該バスの各回線は、それぞれ１台のプロセッサへ信号を転送する。

ルータ１３０は、ｎ立方体接続パターンを介して、他の集積回路上にあるプロセ ッサとの通信を行なう、かかるパターンはたとえば１２次元（ｎ＝１２）で構成 される。該接続は、１２個の立方体配線１３２により配設される。コンピュータ 内のすべての集積回路１００に対応するルータは、並列に作動する。すなわち、 各ルータは他のすべてのルータと同時に同一の動作を行なう、ルータは順方向モ ード、トレースモード、逆方向モードの三種類のモードのうち、いずれかで作動 する。順方向モードでは、メツセージが指定された宛先へと送信される。トレー スモードでは、送信されたメツセージとその宛先が記録される。逆方向モードで は、順方向モードでメツセージをルーティングして設定した経路の逆方向にメツ セージを転送する。逆方向モードやトレースモードを使用するためには１作動サ イクルのあらゆる状態におけるルータ１３０の全スイッチの出力を記録しておく 必要がある。

ルータ１３０は１幅１６回線の並列データバス１３４．メモリインタフェース１ ４０．メモリ１６０．およびデータバス１４２を介して、集積回路１００上のプ ロセッサ１１２とインタフェースをとる。データバス１３４の各回線は、各プロ セッサ１１２とそれぞれ対応している。他の集積回路上のプロセッサから受信さ れたメツセージパケットは。

次の順序でそれぞれの宛先プロセッサに送達される。

すなわち、メツセージパケットは、データバス１３４を構成する回線のうち、宛 先プロセッサに対応した回線上に出力され、ついでインタフェース１４０を介し てメモリ１６０へと転送される。メツセージパケットは、いったんメモリ１６０ に蓄積されたのち、宛先プロセッサによってフェッチされる。これにより、メツ セージパケットは、インタフェース１４０と、データバス１４２の対応する回線 とを介して、宛先プロセッサへと送達される。

以下余白 メツセージパケットは、次の順序で他の集積回路上のプロセッサへと転送される 。すなわち、メツセージパケットは、データバス１１４．交換器１２０．データ バス１２２、およびメモリインタフェース１４０を介してメモリ１６０へと送ら れる。メツセージパケットをその宛先に転送するための回路をルータが確保する と、該パケットは、メモリインタフェース１４０とデータバス１４２とを介して ルータに送られる。ついでメツセージパケットは、適当な立方体配線１３２を介 して他の集積回路へと送られる。ルータ回路の動作に関しては、添付の第５図か ら第１６図までを参照しながら以下に詳しく説明する。

制御回路１５０は、命令デコーダ（図示せず）を有している。この命令デコーダ は、プロセッサ命令ピンに印加された信号を復停して、オンチップ制御信号を生 成する。命令信号は、幅１６回線の並列命令バス１５４を介して制御回路へと供 給される。制御信号は、図示していない回線を介して集積回路の各種構成部品へ と供給される。制御回路１５０は、さらに状態レジスタ（第３図には示さず）を 有している。これらの状態レジスタは、集積回路内に分散して配設されており、 該集積回路内のデータフロー経路におけるスイッチの状態を格納するために使用 する。該状態データにより、トレースモードと逆方向モードにおけるルータの動 作が可能となる。プロセッサと制御回路１５０との間では１幅１６回線の並列デ ータバス１１６および１５６を介して大量の状態情報が交換される。すでに説明 したように、各プロセッサは、各データバス１１６および１５６のそれぞれの異 なる回線と対応している。また、状態情報は、データバス１３６および１５８を 介して制御回路１５０とルータ１３０との間でも交換される。

前記米国特許第４，５９８，４００号で示されているように。

本出願を実施する際には、プロセッサ１１２の多様な実施例を利用することがで きるが、プロセッサ１１２の好ましい実施例を第４図に示した。この図に示され るように、プロセッサは、ＡＬＵ５００．８ビツトフラグ回路５２０．４個のラ ッチＡ、Ｂ、Ｃ，Ｆ、条件回路５３０゜および４個のマルチプレクサ５４１，５ ４２，５４３．５４４を有して構成されている。ＡＬＵは、２個の８対１マルチ プレクサ５０２．５０４を有する。これらのマルチプレクサは、２個の２進真理 表を構成している。ＡＬＵは、３個の入力、すなわちラッチＡ、Ｂ、Ｆからの入 力の演算を行ない、２個の出力を生成する。そのうち一方は合計出力であって、 この出力は、データバス１４４および１２２す構成する回線のうちいずれか１回 線、交換器１２０、およびメモリインタフェース１４０を介して、メモリ１６０ へと書き込まれる。他方の出力は桁上げ出力であり、これはフラグ回路５２０へ と書き込まれる。

データは通常、メモリ１６０からデータバス１３２の１回線を経てラッチＡおよ びＢへと書き込まれる。ルータ１３０から出た信号は、マルチプレクサ５４３を 介してラッチＢへと書き込まれ、命令バス１５４から出た信号は。

マルチプレクサ５４２を介してラッチＡへと書き込まれる。ラッチＦは、フラグ 回路５２０からの入力を受信する。ラッチＣには通常、マルチプレクサ５４１を 介してラッチＡど同一のデータが書き込まれる。

条件回路５３０は、合計出力と桁上げ出力とが、新しく演算された値を伴って書 き込まれるか、あるいは前と同じ値を伴って書き込まれるかを決定する０条件回 路は、フラグ回路によってロードされ、またゲート５３２．５３４およびマルチ プレクサ５４４を介してＡＬＵの出力を制御する。

第５図にルータ１３０の詳細な回路図を示す、この図には、メツセージパケット 注入器５５０、回線割当て器５６０、組合せ器５６０、アドレス検査器５７０、 エジェクタ５７５、オフチップメツセージパケットバッファメモリ５８０、およ びパリティ発生器５９０が含まれている。ルータはさらに、１６ビツトラツチ５ ５２．１６ビツトレジスタ５５４、マルチプレクサ５６２．５７７、５８２．５ ８３，５８４、および幅７ビツトのラッチ５８６，５８７，５８８．５８９を有 して構成されている。データは、７個のデータ経路６００を経て順方向に流れ、 ７個のデータ経路６０２を経て逆方向に流れる。各経路には、流れの同一方向に ある他の６個の経路に対する優先順位がそれぞれ定められている。

メツセージパケットは、パリティ発生器を出た時点では、アドレス情報、データ およびパリティ情報をたとえば以下の表Ｈに示すようなフォーマットで有してい る。

表■ ビット位置　　　値　　　　　　　　　　　　摘ｏ　　　　ｍｓｇ−ｐ　　　　 　　　メツセージが正しいかどうかを示す。

ＫからＬまで　データ０−Ｎ　　　　　Ｎ＋１ビツトのメツセージデータＬ＋１ 　　　　パリティ 注入器５５０は、４×１６のクロスバ−スイッチである。

このスイッチは、１６個のプロセッサ１１２のいずれかより送られるメツセージ を受信し、これをパリティ発生器５９０に至る４個のデータ経路のうちいずれか へと出力する。ついでパリティビットが計算され、パリティ発生器５９０によっ て各パケットに付加される。パケットは、回線割当て器５６０へと送られる。メ ツセージパケットは、以下で説明するように、メッセージバケツドパソファメモ リ５８０から受信することもできる。

回線割当て器は、メツセージパケットのアドレス情報に従い、異なる次元にある 他の集積回路に、立方体配線１３２を介して該メツセージパケットを転送するこ とを試みる。同時に、他のすべての集積回路のルータは、すべてのメツセージパ ケットを該回路に同じように転送しようと試みる。メツセージの転送を行なう場 合、立方体配線を１回に１本ずつ検査して、該配線がルーティングに利用できる かどうかを決定する。いずれかの立方体配線が利用可能である場合、当該立方体 配線（または次元）に宛先として指定されている最も高い優先順位のデータ経路 上にあるメツセージパケットが、該配線上に送出される。この結果、出力された メツセージパケットのあったデータ経路６００が再度利用可能となる。優先順位 の低い残りのデータ経路上にあるメツセージパケットが、１本のデータ経路分だ け進められるため、少なくとも最も優先順位の低いデータ経路１本が開放される 。

さらに、メツセージパケットは、他の集積回路から立方体配線１３２を介して受 信される。受信時には、各パケットは最も優先順位の低いデータ経路に挿入され る。これらのパケットは１回線割当て器内の他のデータ経路上にあるメツセージ パケットと同様な方法で処理される。このため、受信された各パケットは、デー タ経路上で空きが生ずるに従い、優先順位の高いデータ経路へとシフトされてゆ く、任意の立方体配線に宛てられたメツセージパケットのうち、最も優先順位の 高いメツセージパケットは、該パケットの宛先として指定された立方体配線へと 送出される。この結果、各メツセージパケットは、送信元プロセッサから宛先プ ロセッサへと至るルーティング中に、複数の異なる集積回路上にある回線割当て 器の少なくとも一部を通過することになるのが普通である。かかるルーティング は、回線割当て器を介して１回で実行することもできるが、ルーティング上の競 合のため複数回かかって実行されることが多い。

各立方体配線を介してメツセージパケットを受信するデータ経路を確保するため １回線割当て器は、各立方体配線を介して、メツセージパケットを最も優先順位 の低いデータ経路へと自動的に送出する。この場合、メツセージパケットが該デ ータバスに宛れられでいるかどうかは問題とされない、この技術は「すてばちル ーティングＪ　　（ｄｅｓｐｅｒａｔｉｏｎ　ｒｏｕｔｉｎｇ）と呼ばれている 。

回線割当て器から送られるメツセージパケットは。

データ経路６００を介して組合せ器５６５へと送達される。

この組合せ器は、同一のアドレスに宛てられたメツセージパケットを結合するた めのものである。メツセージパケットに対しては、次の四種類の演算が組合せ器 によって実行される。すなわち、最大化（当該プロセッサ宛ての最大２進数を選 択する）、加算（任意のプロセッサ宛てのメツセージを加算する）、論理和（任 意のプロセッサ宛てのメツセージの論理和を計算する）、および重ね書き（最後 に供給されたメツセージを選択する）である。

アドレス検査器５７０は１回線割当て器を出るメツセージパケットのアドレスを 検査することにより、宛先集積回路に到着したパケットを１回線５７２を介して エジェクタ５７５へと通知する。エジェクタ５７５は、７Ｘ１６のクロスバ−ス イッチである。このスイッチは、いずれのデータ経路上にあるメツセージパケッ トでも１幅１６回線のデータバス５７６およびメモリ１６０を介して、１６個の プロセッサ１１２のうちいずれかに転送することができる。とりわけメツセージ は、データバス１４２の適当な回線を介して、プロセッサのＢレジスタに転送さ れる。

７個のデータ経路上にあるメツセージパケットは。

さらにオフチップメツセージパケットバッファメモリ５８０へと転送される。こ のメモリはパケットのバッファとして機能し、このメモリから宛先に送られなか ったパケットは、パリティ発生器５９０へと挿入によって戻される。このバッフ ァメモリは、メモリ１６０の一部として実施することができる。

データの損失を防ぐため、バッファメモリから出たメツセージパケットは、プロ セッサ１１２から挿入されるすべてのメツセージパケットに優先する。その他の 面では、これらのメツセージパケットもルータによって同様に処理される。こう して、各メツセージパケットのパリティピットはパリティ発生器５９０によって 再度計算され、当該パケットに付加される。各パケットは、データ経路６００の いずれかを介して回線割当て器へと送られる。

データ経路６０２を介した逆方向のデータの流れは、順方向の流れと似ている。

ただし逆方向の場合、プロセッサ１１２からでるメツセージパケットは、エジェ クタ５７５を介してルータに送られたのち、組合せ器５６５゜回線割当て器５６ ０、パリティ発生器５９０および注入器５５０を介して転送される。逆方向のル ーティングでは。

トレースモードを使用して、並列処理装置の状態を記録する。これらの状態は、 １台以上の送信元プロセッサから１台以上の宛先プロセッサへとメツセージを転 送するために必要な状態を言う、これらの状態を記録したのち、該状態を逆方向 に使用することにより、宛先プロセッサから送信元プロセッサへとメツセージを 返送する１組合せ器は、順方向のメツセージ転送における組合せ工程の逆の順序 でメツセージパケットを複製するため、多数のプロセッサに対してメツセージパ ケットの同報通信を行なうことができる０回線割当て器は、メツセージパケット を送信元の集積回路へと返送する。ついで注入器は、メツセージパケットを適当 なプロセッサに送信するか、もしくは送信が可能となるまで該パケットをバッフ ァメモリに一時的に格納する。

第６図に、注入器５５０ならびにパリティ発生器５９０に入るデータの流れ、お よびこれらの構成部品から呂るデータの流れを示す、かかる構成部品に加えて、 第６図は、幅１６ビツトの要求ラッチ５５２、幅１６ビツトのレジスタ５５４、 および幅７ビツトのラッチ５８６を含んでいる。ラッチ５５２およびレジスタ５ ５４の各ビット位置は、１６個の異なるプロセッサ１１２のそれぞれに対応して おり、かつ注入器５５０の４×１６クロスバースイツチの各列に接続されている 。ラッチ５８６の各ビット位置は、バッファメモリ５８０の各データ経路に対応 している。

ラッチ５８６でいずれかのビットが“１”に設定されると、対応するデータ経路 が空いたため、メツセージパケットの受信が可能になったことを意味する。この ため、ラッチ５８６は、データ経路利用可能（空き）ラッチと呼ばれる。また第 ６図には、４個のＯＲゲート配列５５６が示されている。各ＯＲゲートは、注入 器５５０の４×１６クロスバースイツチの各行に対応している。また各ＯＲゲー トは、１６本の入力回線５５７を有する。各入力回線は、注入器５５０の４×１ ６クロスバースイツチの同一行にある各列から出ている。

パリティ発生器５９０は、４個の入力マルチプレクサ５９２からなる第一の配列 、７個の入力マルチプレクサ５９３からなる第二の配列、７個のパリティビット 演算回路５９５．４個の出力マルチプレクサ５９７、および３個の出力ゲート５ ９８を有して構成されている。各入力マルチプレクサ５９２は、２個の入力を有 する。一方の入力は、ＯＲゲート配列５５６の出力から出ており、他方の入力は 、データバス６０４の４個のデータ経路のうちのいずれかより出ている。各入力 マルチプレクサ５９３は、２個の入力を有する。そのうち一方の入力は、逆方向 データバス６０２のデータ経路のいずれかより出ており、他方の入力は、入力マ ルチプレクサ５９２の出力、もしくはデータバス６０４の残りのデータ経路のい ずれかより出ている。７個のマルチプレクサ５９３の各々の入力は、７個のパリ ティビット演算回路５９５の各々に供給される。各パリティ回路の出力は、いず れか１個の順方向データ経路６００を介して１回線割当て器に供給される。また 、パリティ回路のこれらの出力は、マルチプレクサ５９７と幅７ビツトの並列デ ータバス５９９へのゲート５９８とを介して、ランチ５８２およびバッファメモ リ５８０へと接続されている。

１６個のプロセッサ１１２から出るメツセージパケットは、レジスタ５５４とデ ータバス５５５とを介して、注入器５５０へと供給される。また、バッファメモ リ５８０から出るメツセージパケットは、レジスタ５８７と７回線並列データバ ス６０４とを介して、パリティ発生器５９０へと供給される。プロセッサによる 送信を待つメツセージパケットが存在する場合、当該プロセッサに対応する要求 ラッチ５５２のビット位置に“１”を１個立てて該存在を示す、要求ラッチ５５ ２から出る信号は、データバス５５３を介して、注入器５５０の４×１６クロス バースイツチの各列へと供給される。このラッチの１６個のビット位置は、スイ ッチの異なる各列に対応している。データ経路に空きがあってメツセージパケッ トが送信できることを示す信号は１幅１６回線のデータバス５５８を介して、プ ロセッサ１１２へと供給される。バス１４２．５５３．５５５の回線が注入器５ ５０の４×１６クロスバースイツチの各列に対応しているのと同様な形式で、デ ータバスの各回線は、異なる各プロセッサに対応している。

以上のように、特定のデータ経路に対応する位置のバッファメモリにメツセージ パケットがない場合、当該データ経路に対応する空きラッチ５８６の適当なビッ ト位置に“１”を１個立てて該存在を示す、空きラッチ５８６のビット位置のう ち、４個の最も低い優先順位のデータ経路に対応する４個のビット位置から出る 信号は、並列のデータバス６０５を経て、注入器５５０の４×１６クロスバース イツチの４行と、かかる行に対応する４個のマルチプレクサ５９２へと供給され る。空きラッチ５８４内に“１″ビツトがあれば、該ビットの対応するクロスバ −スイッチの行の条件付けが行なわれて、レジスタ５５４に格納されているメツ セージパケット（ある場合のみ）が受信される。また、この“１ｎビツトにより 、前記行に対応するマルチプレクサ５９２の条件付けが行なわれて、該行に対応 するＯＲゲート配列５５６から入力信号が受信される。このとき、データバス６ ０４からデータ経路上に入力された信号が存在する場合、これらの信号はすべて 拒否される。

マルチプレクサ５９３に印加された制御信号は、７個の順方向データ経路６００ および７個の逆方向データ経路６０２から出る信号の方向と流れを制御する。と りわけマルチプレクサ５９３に印加された制御信号は、データ経路６０２からの 逆方向信号を選択するか、もしくは注入器５５０またはデータバス６０４からの 順方向信号を選択して、パリティビット演算回路による処理を行なう。

空きラッチ５８６の７個のビット位置から出る７個の信号は、データバス６０６ を介して、マルチプレクサ５９７およびゲート５９８へと印加される。ゲート５ ９８へと印加される信号は、並列データバス６０９の７回線のうち３回線へのア クスを制御する。ラッチ５８６からマルチブレクサ５９７へと印加される信号に より、４個のパリティ演算回路の出力を、４回線並列データバス６０７か。

または並列データバス６０９の残りの４回線のいずれが八と選択的に供給するこ とができる。データバス６０９の７本の回線は、それぞれラッチ５８２およびバ ッファメモリ５８０へと接続されている。

データバス６０７の４本の回線は、１６６回線並バス６０ｇへとファンアウト接 続されている。これらの回線はそれぞれ、注入器５５０の４×１６クロスバース イツチの同一行で異なる列にあるスイッチへ、入力ととして供給される０回線６ ０８上にあるメツセージパケットで、注入器５５０と同一の集積回路の１６個の プロセッサに宛てられたメツセージパケットは、幅１６回線の並列データバス５ ５９の回線に対応するプロセッサへと供給される。

該データバスの各回線は、注入器５５０の４×１６クロスバースイツチの列のう ちの１本に接続されており、また１６個のプロセッサとそれぞれ対応している。

第７図に注入器５５０の注入回路の詳細を示す、この回路は、二種類のセル６１ ２，６１３の４×１６クロスバ一スイツチ配列６１０を有している。この配列は 、第７図のなかでは該セルの最初と最後の各２セルによって表示されている。各 列は、チップ上のプロセッサ１１２にそれぞれ対応している。各列は、その対応 するプロセッサから回線５５３上に送信要求信号を受信する。この信号は、メツ セージパケット１個が送信待ち状態であり。

回線５５５上にあることを示している。送信要求信号は。

回線６２２および６２４の各セルを介して各列に伝搬する。

また各列では、メツセージパケットは列のすべてのセルに並列に供給されるが、 以下のような方法で１個のセルのみが該パケットを受信する。

配列内の４列は、注入器の７個のデータ経路のうち。

利用可能な４個に対応する。より詳細には、該４列は最も優先順位の低い４個の データ経路に対応する。バッファメモリ内の特定のデータ経路上にメツセージパ ケットがないことを示す信号が、回線６０５を介して各行のセルに印加される。

これらの信号は１回線６２６および６２８を介して配列中に伝搬される。順方向 に送られるメツセージパケットは、回線５５７を介してＯＲゲート配列５５６に 供給される。逆方向に送られるメツセージパケットは１回Ｉｉ！６０８を介して 該配列のセルに供給され、さらに１６本の回線５５９を介してプロセッサ１１２ へと供給される。

セルの配列は、二次元の受理水（ｇｒａｎｔ−ｔｒｅｅ）構造を形成する。この 木構造は、プロセッサから送られた回線５５３上の信号ならびにメツセージパケ ットバッファメモリから送られた回線６０５上の信号とに基づき。

プロセッサ１１２から送られるメツセージパケットを受信するためのデータ経路 に空きがあるかどうかを決定する。空きがある場合、当該プロセッサは、対応す る受理回線５５８を介してその旨通知を受ける。適当なセルが条件付けされると 、該プロセッサからメツセージパケットが受信され、空いているデータ経路に入 力される。

第８図に２個のセル６１２，６１３の詳細を示す、これらのセルは、たとえば第 ７図の配列６１０の左上に位置するセルである０図に示されるように、セル６１ ２は、５個の論理ゲート６４１〜６４５．および否定回路６４７からなる配列を 有して構成されている。セル６１３は、５個の論理ゲート６５１〜６５５、およ び否定回路６５７からなる同様な配列を有している。この回路は、プロセッサか ら送られたメツセージパケットを、最も優先順位が高くて利用可能なデータ経路 に挿入し、かつ他のデータ経路への該パケットの挿入を防ぐように接続されてい る。

データ経路がこのように占有された場合、当該行の回線６２６．６２８上にある 信号を変更して、該データ経路の占有を示す必要がある。このように、プロセッ サは。

優先順位に基づいてデータ経路にアクセスすることができる。この場合、左端の 列に対応するプロセッサの優先順位が最も高く、列が右側に進むにつれて、対応 するプロセッサの優先順位が低くなる。

以下余白 これらの機能は、セル６１２の論理ゲートをひとつのパターンで接続し、セル６ １３の論理ゲートを異なるパターンで接続して実現する。また論理回路は、要求 回線とデータ経路空き回線にある信号が、セル６１２とセル６１３とに対してそ れぞれ異なる方式で処理されるように設計されている。より詳細には、各セル６ １２は。

データ経路空き回線６０５または６２８にある否定回路を含んでいる０図中では 該回線上の吹き出し部、ＮＡＮＤゲート６４５．および否定入力を有するＡＮＤ ゲート６４１として示されている。逆に言えば、各セル６１３は、要求回線６２ ４上の否定回路、否定入力を有するＡＮＤゲて要求回線５５３または６２２で受 信され、さらに高信号が回線６０５または６２８で受信されると、ゲート６４３ からの出力信号は高状態となる。これによりゲート６４２が使用可能となる。こ のゲートには、当該列に対応するメツセージパケットが、回線５５５を介して供 給される。

この結果、メツセージパケットは、ゲート６４２から回線５５７を経てＯＲゲー ト配列５５６へと転送される。このＯＲゲート配列は、配列６１０の同一行から 出ている１本おきの回線５５７からの入力を受ける０回線５５３（または６６２ ）および６０５（または６２８）に入力された高信号は、ゲート６４１から出て いる回線６２６上にも高信号を生成する。この信号は、当該行に対応するデータ 経路が現在占有されていることを示す、さらにこの信号は。

配列の同一行の残りの列に伝搬する。このため、優先順位の低い列のいずれかに おいては、セル６１３への要求回線６２６の入力の極性にかかわらず、回線６２ ６に低極性が現れると、ゲート６５３が使用禁止となり、ゲート６５１からの信 号が強制的に高状態とされる。また、優先順位の低い列のいずれかにおいては、 セル６１２への要求回線５５３または６２２の入力の極性にかかわらず、セル６ １２に至る回、ｉ！６２８に低極性が現れると、ゲート６４３が使用禁止となり 、ゲート６４１からの出力信号が強制的に低状態とされる。ゲート６５３が使用 禁止になると、回１＆１６２６上のゲート６５２も同様に使用禁止となるため、 メツセージパケットはセル６１３によっては受は付けられない、ゲート６４３が 使用禁止になると、ゲート６４２も同様に使用禁止となるため、メツセージパケ ットはセル６１２によって受は付けられない。

また１回線５５３（または６６２）および６０５（または６２８）のセル６１２ に入力された高信号は、ゲート６４５の出力に高信号を生成し１回線６２４に低 信号を生成する０回線６２４の低信号は、残りのデータ経路にメツセージパケッ トを受信させる要求がなされていないことを示している。またこの信号は、同一 列の残りの行へと伝搬する。このように、優先順位の低い行のいずれかにおいて は、セル６１３に至るデータ経路空き回ｗＡ６０５の極性にかかわらず、該セル に至る回線６２４に低極性が現れると、／７’−）−６５３が使用禁止となり、 ゲート６５５からの出力信号が強制的に低状態とされる。また、優先順位の低い 行のいずれかにおいては、セル６１２に至るデータ経路空き回線６０５（または ６２８）の極性にかかわらず、該セルにいたる回ＮＩＡ６２２に低極性が現れる と、ゲート６４３が使用禁止となり、ゲート６４５からの出力信号が強制的に高 状態とされる。さらに、ゲート６５３または６４３を使用禁止にすると、メツセ ージパケットはセル６１３または６１２によってそれぞれ受信されない、最後に 、回線６２２および６２４の各列を伝搬する信号は、回線５５８に出力され、受 理信号としてプロセッサ１１２へと戻される。この受理信号は、要求が受理され ると一方の極性をとり、要求が拒絶されると他方の極性をとる。これにより、プ ロセッサが注入器にメツセージパケットを送信できるかどうかが、該プロセッサ に通知される。

しかしながら、送信要求がセル６１２に送られて、該セルに対応するデータ経路 に空きがないために拒絶されると、ゲート６４５の出力は低状態となる。これに より、最も近い下位のセル６１３のゲート６５３が使用可能となる。ここで、該 セルに対応するデータ経路が利用可能であれば、否定回路６５７に印加される信 号は高信号となり、ゲート６５３の出力は高状態となる。これにより、ゲート６ ５２が使用可能となってメツセージパケットが受信される。この場合、ゲート６ ５１の出力は、データ経路が利用不可能となったことを示し、ゲート６５５の出 力は、要求が受理されて、同一列の下位セルがいずれのメツセージパケットも受 信しないことを示す、セル６１３に対応するデータ経路が利用不可能であれば、 ゲート６５５の出力は高状態であり、最も近い下位のセル６１２のゲート６４３ が使用可能となる。

送信要求が回線６２２によって配列内の任意の列に供給されない場合、当該列の 任意の行において回線６０５上へ入力されたデータ経路空き信号は１次の列の同 一行へと次々に送られてゆく、この転送は、配列内のいずれかの列で送信要求が 検出されるまで継続する。

ゲート６４３および６５３でも１回線６０８が接続されたゲート６４４および６ ５４の使用の可能・禁止を制御する。このため、ラッチ５５２および５８６から の信号を使用して。

逆方向に送られるメツセージパケットを受信し、ゲート６３２およびデータバス ５５９の回線のうちいずれか１本を介して、該パケットをプロセッサ１１２へと 供給する。

順方向に送られるメツセージパケットは、データバス６００を介して回線割当て 器５６０へと供給される。この回線割当て器は、たとえば同一の論理セル５６２ からなる７×１２配列を有する。この配列の各行は、７個のデータ経路をそれぞ れ介してメツセージパケットを処理する。またこの配列の各列は、通信ネットワ ークの１２次元のうちいずれかの次元で、立方体配線１３２を介して最近接集積 回路と通信を行なう、第９図にこれら論理セルの第一列、第二列、および最後列 を示す。

データバス６００の７本のデータバスは、回線割当て器５６０のセルの第一列に おいて、７個のセル５６７への各入力として配設されている。これらのセルは、 第９図の左側に示されている。またメツセージパケットは。

回線６６０上の各セルにも入力できる。これらの回線は、各セルに対応する立方 体配線に接続されている。当該セルの他のいかなる信号があるかにより、セルに 受信された順方向メツセージパケットは、次の三種類の回線のいずれかを介して 該セルの外部へと転送される。

第一の回線は、回４！６６３であり、これは、当該セルの存在する列に対応した 立方体配線に接続されている。

第二の回線は、折回線６６４であり、これは配列内で行が同一であって列が１個 右隣であるセルに対して入力を供給する。第三の回線は１列回ｌＸ６６６であり 、これは同一列の最も近い上位のセルに対して入力を供給する。以下で明らかに なるように、最も近い上位のセルに転送されたメツセージパケットは、実際には 、同一行の右側の列にあるセルに供給されている。

逆方向に送られるメツセージパケットは、配列内を逆方向に流れる。バス６０２ の７個のデータ経路は、配列の最後列にある７個のセルに対し、それぞれ入力と して配設されている。これらのセルは、第９図の右側に示されている。また、メ ツセージパケットは１回線６６０上の各セルに入力できる。この回線は、各セル に対応した立方体配線に接続されている。セル内にある信号の種類により、次の 二種類の回線のうちいずれかを介して該セルの外部へと転送される。第一の回線 は。

回線６６２であり、これは当該セルの存在する列に対応した立方体配線に接続さ れている。第二の回線は、回線６６８であり、これは次の２個のセルへと入力を 供給する。そのうち一方のセルは、配列内で行が同一であって列が１個左隣であ るセルである。他方のセルは。

前記セルに最も近い下位セルである。

制御信号は１回線６７２，６７４，６７６．６７８，６８０を介して各セルへと 印加される０回線６７２上の優先順位信号によって、データ経路上の信号が立方 体をアクセスする際の優先順が決定される。より詳細には、セル内の回路は回線 ６７２上の信号を使用して以下の二種類の動作を行なう、第一に、当該次元に宛 てられている列にある最も優先順位の高いメツセージパケットに対して。

立方体配線１３２へのアクセスを許容する。第二に、当該列の下位セルにあるメ ツセージパケットを、立方体配線へと転送することを禁止する。セルへの入力時 点で回線６７２上に高信号が存在すると、該セルは、メツセージパケットを立方 体配線１３２へと転送することができる。低信号の場合は、かかる転送が禁止さ れる。

このため、任意の列において最上位のセルに印加された低信号は、実質的にネッ トワークから当該立方体配線を除去することになる。このため、回線６７２に印 加される信号を制御すれば、ネットワークの規模を変更することができる。さら に、相互接続ネットワーク内で特定の配線が断線した場合、該当する回線６７２ に低信号でバイアスをかけるだけでこの配線を除去することができる。

回線６７４上の全占有信号は、各列の各セルに対して。

当該列のすべての上位セルにメツセージパケットが存在するかどうかを通知する 。いずれかの上位セルが空いている場合、下位セルにあるメツセージパケットは 。

セル１個分だけ列内で上位に進められる０回線６７６は。

メツセージパケットの「すてばちルーティング」の起点となる行を特定すること により、各列のセル１個が立方体配線を介してメツセージパケット１個をいつで も受信できるように保証する６通常、この行は配列の最下位の行であるが、ソフ トウェアによる制御で回線６７６を介してこの行を変更することができる６回線 ６７８゜６８０上の各セルにタイミング信号が印加される。より詳細には、セル の各列に対応する回線６７８上の信号がは、ラッチ６９２．６９４の動作を制御 する。この結果、並列式コンピュータ内のすべての回線割当て器のタイミングが 適切に同期さ九て、全回線割当て器の各第一列が各回線割当て器内の各メツセー ジパケットの第一アドレスビットを同時に処理し、ついで第二列が各メツセージ パケットの第ニアドレスビットを同時に処理し、以下同様となる。

第１０図にセル６５２の詳細を示す、各セルは、第一メツセージラッチ６９２、 第二メツセージラッチ６９４、第一ゲート６９６、第ニゲ−トロ９８．４個のマ ルチプレクサ７０２、７０４．７０６．７０８．決定回路７１０、および制御ラ ッチ７１２．７１４を有して構成されている。以下に詳しく説明するように、セ ルの任意の列でルーティングの決定がなされると、当該列の各ラッチ６９４は、 メツセージパケットの先端にある一ｓｇ−ｐビットを格納する。これにより、該 セルを介してルーティングされるメツセージパケットの存在または不在が示され る。各ラッチ６９２は、セルの当該行に接続された立方体配線１３２の次元に対 応するアドレスビットを格納する。ラッチ６９２゜６９４に格納されたデータは 、回線６９３．６９５をそれぞれ介して決定回路７１０へと供給される。制御信 号６７２゜６７４．６７６もまた入力としてこの決定回路へと印加される０回路 ７１０の出力はラッチ７１２．７１４へと印加されて、セルが受信したメツセー ジパケットのルーティング経路を決定する。ラッチ７１２の出力に高信号が現れ ると（出力端子の吹出し部で示される反転の前）、ゲート６９６ならびに回Ｉ！ ６６６への信号の流れが使用禁止となり、ゲート６９８が使用可能となる。ゲー ト６９８の出力は、立方体配線１３２に接続されている。逆に言えば、低信号が 現れると、ゲート６９６が使用可能となり、ゲート６９８が使用禁止となる。こ のように、ラッチ７１２は、立方体配線がメツセージパケットを受信するかどう かを制御する。各ラッチ７１２の動作は、当該列の回［６７２上の優先順位信号 と、セルの該列に接続された立方体配線の次元に対応するアドレスビットの存在 とによって制御される。

ラッチフ１４の出力は、セル内にあるマルチプレクサ７０８を制御する。このセ ルは、自身のゲート６９６の出力で供給されるメツセージパケットを選択するか 、もしくは、同一列上で最も近い下位セルのゲート６９６の出力で供給されるメ ツセージパケットを選択する。こうして選択されたメツセージパケットは１行が 同一で列が１本右隣であるセルへの入力として、行回線６６４に供給される。こ のように、ラッチ７１４は、セルの列内でメツセージパケットを上方向に圧縮す るかどうかを決定する。各ラッチ７１４の動作は、三種類の要因、すなわち回線 ６７４上の全占有信号、ラッチ６９４のｍｓｇ−ｐビット、およびセルがメツセ ージパケットに対して立方体配線へのアクセスを許容したかどうかによって制御 される。

同様にして、３個のラッチがメツセージパケットの逆方向の流れを制御する。す なわち、ラッチ７１４からの出力信号は、マルチプレクサ７０２が、同一行の右 隣の列にあるセルからの入力を回ｇ　６６ｇ上で受取るか、もしくは１行上にあ るセルからの入力を回線６６８上で受取ることを決定する。またラッチ７１２か らの出力信号は、マルチプレクサ７０４が、マルチプレクサ７０２からの入力を 受取るか、もしくは立方体配！１３２からの入力を受取ることを決定する。

第１１図に決定回路７１０の詳細を示す１図示されているように、この決定回路 は、ＡＮＤゲート７２１、ＮＯＲゲート７２２，７２３、ＯＲゲート７２４．オ ヨびＮＡＮＤゲート７２５を有して構成されている。また、ラッチ７１２．７１ ４に至る入力回線の否定回路７１６，７１７も示されている。決定回路７１０の 機能は、メツセージパケットをセルから立方体配線１３２、行目＠　６６４およ び列回線６６６へと供給する際に該供給を制御すること、ならびに制御信号を回 線６７２および６７４へと印加することである１回線６７２への制御信号は、当 該立方体配線が使用中であるかどうかを示し、回線６７４への制御信号は、空き データ経路があるかどうかを示す。

空きデータ経路は、セルを介して１行回線６６４上で次の三通りの場合に利用可 能となる。第一に、回［ＦＪ当で器の上位行のうちのひとつに空きデータ経路が 存在する場合である。この場合１回線６７４上に低信号が現れる。第二に、当該 セルを通る行目線が空いている場合である。この場合、ｍｓｇ−ｐビットにゼロ が設定される。第三に、セル内のメツセージパケットが立方体配線へと送り出さ れる場合である。これらの条件はそれぞれ、ＮＡＮＤゲート７２５に至る入力回 線上に低信号が現れることによって表現される。これらの条件が満たされると１ 次の下位セルに至る回１１６７４上に低信号が現れて、空きデータ経路が存在す ることが示される。同一の信号が、ラッチ７１４の入力として否定回路７１７に 印加される。この信号によりマルチプレクサ７０８は次の下位セルからメツセー ジパケットを受取り、行目線６６４へと該パケットを供給する。ＮＡＮＤゲート ７２５への入力が高状態であれば１回［６７４上のゲート７２５の出力は高信号 となり、すべての上位データ経路が占有されていることが示される。マルチプレ クサ７０８は、ラッチ６９２．６９４からメツセージパケットを受取って行目線 ６６４へと供給する。

メツセージパケットは、次の二通りの場合に立方体配線１３２へとルーティング によって送出される。第一の場合は、メツセージパケットが当該立方体配線に宛 てられており、かつ該配線に宛てられているメツセージパケットのなかでは該パ ケットが最も高い優先順位を有する場合である。これは入力回線６７２上に高信 号が現れることによって示される。第二の場合は、すべてのデータ経路が占有さ れており（回線６７４上に高信号が現れる）１回＠　６７６上の高信号によって ずてばちルーティング用にセルが選択される場合である。

回線６７４および６７６では、ＡＮＤゲート７２１によって高信号の有無が検査 される。このゲートの出力、ならびに回線６７２上の優先順位信号とラッチ６９ ２からのアドレスビットが、ＮＯＲゲート７２２に供給される。セルに対応する 立方体配線にメツセージパケットが宛てられている場合は、ラッチ６９２からの 信号は高状態となる。これらのいずれの場合にも、ＮＯＲゲート７２２の出力は 低状態となる。この出力は１回線６７２上の優先順位信号とともに、ＮＯＲゲー ト７２３およびＯＲゲート７２４へと供給される０列内で優先順位の高い任意の セルに対して、立方体配線１３２へのアクセスが許されない場合、ゲート７２３ および７２４に印加される優先順位信号は低状態となる。このように、ゲート７ ２３の出力は高状態となり、ゲート７２４の出力は低状態となる。

ゲート７２３からの高出力により、ゲート６９８は、回線６６２を介して立方体 配ｌＩ＆１３２へとメツセージパケットのルーティングを行なう、ゲート７２４ からの低出力によってゲート７２５からの回線６７４が低状態に置かれることに より、空きデータ経路があることが示される。

ＮＯＲゲート７２２からの出力は、回ｗＡ６７２を介して同一列内の優先順位の 低いセルにも供給される。ゲート７２１またはラッチ６９２からの高信号、もし くは優先順位信号は、当該回線に低状態の出力を生成する。これは立方体配線が 利用不可能であることを示している。

ｍｓｇ−ｐビットと適当な時限アドレスビットとを、任意のセルのラッチ６９４ および６９２に設定するためには、各メツセージパケットのアドレスビットを、 回線割当て器のセルを介して円形パターンでシフトする必要がある。これは、各 セル内のラッチ６９２．６９４をソフトウェアで制御することにより達成される 。第１２図に、１２次元の回線割当て器を介してメツセージパケットを送る場合 のシフト動作のシーケンスを示す、第１２Ａ図と第１２Ｂ図では、２Ｘ１２個の ボックスによってラッチ６９２および６９４の内容が示されている。これらのラ ッチは、メツセージパケットが伝搬される対象となる回線割当て器内において、 セルからなる１２列の各々につき存在する。セルからなる第一列から最後列まで ルーティングが行なわれるため、第１２Ａ図と第１２Ｂ図に示されたセルは、１ 個の回線割当て器の同一行内にすべであるわけではないことに注目する必要があ る。実際には、メツセージパケットが１個以上の立方体配線を介してルーティン グされるため、これらのセルは、いくつかの異なる回線割当て器の複数の異なる 行内に存在する可能性が高い。

メツセージパケット内のほとんどのビットは１回線割当て器のセルのラッチ６９ ２，６９４を介して伝搬する。

このためこれらのビットは、１２個のセルの各々において、最初にラッチ６９２ に入り、ついでラッチ６９４へと入る。このように、第１２Ａ図と第１２Ｂ図に 示されたこれらのラッチでは、　ｍｓｇ−ｐビット、データビットｘＯ−ｄｎ、 およびパリティビットｐａｒが、ゼロ次元セルのラッチ６９２の入口点から、第 １１次元セルのラッチ６９４の出口点まで、のこぎり波経路を通過する。しかし ながら、メツセージパケットのアドレスビットは異なる経路を通過する。より詳 細には、各次元のアドレスビットは、当該次元に対応するセルによって以下の場 合に検査される。すなわち、アドレスビットが当該セルのラッチ６９２にあり、 かつｍｓｇ−ｐビットが該セルのラッチ６９４にある場合である。

アドレスビットをこのように位置決めするため、これらのアドレスビットを異な るパターンでルーティングする。第１２Ａ図のサイクル１の場合のように、第一 アドレスビットａＯは、ゼロ次元セルのラッチ６９２に設定され、ここでゼロ次 元の立方体配線を介したルーティングについて検査される。その後、アドレスビ ットａＯは、サイクル２のラッチ６９４へと移動され、サイクル１４に達するま でこのラッチで保留される。アドレスビットａｌは、サイクル２のゼロ次元セル のラッチ６９２へと移動され、ついでサイクル３の第一次元セルのラッチ６９２ へと移動される。このラッチで、アドレスビットａ１は、−次元の立方体配線を 介したメツセージパケットのルーティングについて検査される。

ついでアドレスビットａｌは、サイクル４で一次元セルのラッチ６９４へと移動 され、サイクル１５に達するまでこのラッチで保留される。他のアドレスビット も。

同様に各セルのラッチ６９４へと移動され、ルーティングについて検査されたの ち、それぞれのラッチで１２サイクル分保留される。

最後にアドレスビットが回線割当て器に入ると、ラッチ６９４に格納されている アドレスビットが１回に１個ずつ取り出され、次の次元のセルのラッチ６９２へ と移動される。このラッチを出ると、アドレスビットは残りのすべてのセルのラ ッチ６９２のみを通過する。この動作はすべてのセルからアドレスビットが離れ るまで継続する。この装置により、メツセージパケットのビットは回線割当て器 に入力された順序と同一の順序で元通りに配列されて、メツセージパケットが再 生さ第１３Ａ図と第１３Ｂ図に１回線割当て器を介したメツセージパケットのル ーティングの例を示す、説明の便宜のため、３個のデータ経路と４個の列のみを 有する回線割当て器を図示した。５個のメツセージパケットＡ、Ｂ、Ｃ，Ｄ、Ｅ は、次の表ｍに示すようなアドレスビットを有している。

表■ ｍ　　ａｏ　　ａｌ　　ａ２　　ａ３ Ａｌ　　１０　０　０ Ｂｌ　　１０　１　０ Ｃ１００１１ ＤＩ　　００　１− １００ＯＩ 参照の便宜のため、これらのビットの値は第１３Ａ図と第１３Ｂ図ではかっこに 入れて示している。

サイクル１において、メツセージパケットＡ、Ｂ。

Ｃが回線割当て器に挿入される。サイクル２では、メツセージパケットＡがゼロ 次元の立方体配線へと送出される。これは、該パケットがゼロ次元に宛てられて いて最も高い優先順位を有しているためである。メツセージパケットＢ、Ｃはデ ータ経路上で上方向に繰上げられる。メツセージパケットＤは、ゼロ次元の立方 体配線で受取られたのち、最も低い優先順位のデータ経路に送り出される０回線 割当て器内に残っているメツセージパケットは、いずれも−次元でのルーティン グを目的として宛先を指定されていない、しかしながら、サイクル４では、これ らのメツセージパケットのうち、いずれかについてルーティングが行なわれなけ ればならない、このため、最も優先順位の低いデータ経路にあるメツセージパケ ット（パケットＤ）のルーティングが行なわれる。パケットＥは、−次元の立方 体配線上で受信されたのち、最も優先順位の低いデータ経路に送り出される。

たとえば二次元の立方体配線を使用禁止にすると、サイクル６でのルーティング は行なわれない、三次元に対して宛てられた最も優先順位の高°いメツセージパ ケットはメツセージパケットＣであるため、サイクル８の進行中にこのパケット が三次元の立方体配線へと送り出される。パケットＥはデータ経路１本分だけ繰 上げられ、パケットＦは、受信されると最も優先順位の低いデータ経路へと送り 出される。

第５図に示すように、メツセージパケットは次に組合せ器５６５とアドレス検査 器５７０とに供給される。アドレス検査器は、各データ経路６００上のメツセー ジパケットを検査して、これらのパケットが各々の宛先に到着したかどかを確認 する。特定の次元に宛てられたメツセージパケットのアドレスビットは、該次元 の立方体配線上にメツセージパケットが送り出された時点で反転されているため 、宛先の集積回路ではアドレスビットはすべてゼロでなければならない、したが って、アドレス検査器は、各アドレスビットにゼロがあるかどうかだけを検査す る。ゼロ以外のビットが検出された場合、メツセージパケットはその宛先に到着 していない、この場合メツセージパケットは、回ｗＡ５６７を介してバッファメ モリへと転送される。メツセージパケットは１次のルーティングサイクルが開始 されるまでこのバッファメモリに格納される。すべてのビットがゼロである場合 、アドレス検査器は、メモリラッチのビット位置１３−１６　（表■の例）にプ ロセッサアドレスビットを格納する。また、アドレス検査器は、メツセージパケ ットの指定するプロセッサに該メツセージパケットを送るための命令を、回線５ ７２上のエジェクタに供給する。さらに、アドレス検査器は、７回線データバス ７６１を介して、各メツセージパケットのｍｓｇ−ｐビットを組合せ器５６５に 供給する。

第１４図に示された組合せ器５６５は、二種類のセルフ３０．７９０からなる配 列を有している。セルフ３０は、隣接するデータバス６００または６０２上のメ ツセージパケットを検査して、これらのメツセージパケットが同一の宛先のプロ セッサに対して送られたものかどうかを確認する。

これらのメツセージパケットの宛先が同一であれば、セルフ９０が起動され、予 め決められた動作に従ってメツセージパケットの組合せを行なう、たとえばこの 動作としては１次の四種類のうちのいずれかを選択する。

すなわち、最大化（プロセッサ宛ての最大２進数を選択する）、加算（プロセッ サ宛てのメツセージを加算する）、論理和（プロセッサ宛てのメツセージの論理 和を計算する）、および重ね書き（最後に供給されたメツセージを選択する）の うちのいずれかである。

第１５図にセルフ３０の詳細の例を示す０図に示されるように、セルフ３０ハ、 排他的ＯＲゲート７３２、ＮＡＮＤゲート７３６、ＡＮＤゲート７４０、ＯＲゲ ート７４４、ラッチ７４８．７５２、Ｎ　Ａ　Ｎ　Ｄゲート７５６，７６０，７ ６４、否定回路７６８、ＡＮＤゲート７７２．７７６、およびマルチプレクサ７ ８０を有して構成されている。ラッチ７４１１７５２は。

回線７４５、ＯＲゲート７４４および回線７４６を芥して、それぞれのラッチに “１ｎビツトをロードすることによて初期化される。ラッチ７５２に“１″ビツ トを設定すると、ＡＮＤゲート７４０が使用可能となる。排他的ＯＲゲート７３ ２およびＮＡＮＤゲート７３６は、２個の隣接するデータ経路６００上のメツセ ージパケットのアドレスを比較するように機能する。これらのアドレスは、入力 回、１１７３３．６００を介して排他的ＯＲゲートへと供給される。タイミング 信号が回線７３３を介してＮＡＮＤゲート７３６に供給されることにより、メツ セージパケットのアドレスの各ピット位置に対して、回線７３５上で排他的ＯＲ ゲート７３２の出力がサンプリングされる。

このタイミング信号は、第１４図に示したセルの列に対する演算のシーケンスを 決定する。

２個のアドレス内のビットが同一である間は、排他的ＯＲゲート７３２の出力は 低状態であり、ＮＡＮＤゲート７３６の出力は高状態であり、かつラッチ７４８ ．７５２に印加された信号ならびに該ラッチの出力に現れた信号は高状態である 。アドレス内のビットの組がいずれも異なる場合、排他的ＯＲゲートの出力は高 状態となり、ラッチ７５２の出力は低状態となる。前者の出力が低状態になると 、ＡＮＤゲート７４０は使用禁止となり。

ラッチの出力はリセットされるまで低状態のままとなる。

ラッチ７５２の出力が高状態であり、アドレス検査器５７０から出ている回線７ ６１上のｍｓｇ−ｐビットの値が高状態であり、かつＮＡＮＤゲート７６０に至 る受理回線７６２上の信号が高状態であれば、ＮＡＮＤゲート７６４が使用可能 となる。これにより、回線６００上の信号は、優先順位の低いデータ経路からセ ルフ９０へと回＠　７６５を介して転送される。これらの信号はまた、ＡＮＤゲ ート７７２から出ている受理口＠７７３上に低信号を生成し、ＡＮＤゲート７７ ６を使用可能にすることにより１回線７６１上の＋ｍｓｇ−ｐ信号を組合せ器の 同一行内の次のセルフ３０へと転送する。

逆方向のデータの流れに関しては、否定回路７６８の出力に高信号が現れると、 マルチプレクサ７８０が、データ経路６０２から出ている回線７８１上の入力と 接続される。このデータ経路６０２は、当該セルに対応した逆方向データ経路６ ０２より優先順位が１段階低い、この結果５両データ経路上に同一の信号が現れ る。実際には。

優先順位の高いデータ経路上の信号が複製されることになる。

セルフ９０は、対応するデータ経路６００からメツセージパケットを受信する。

２個のメツセージパケットが同一のアドレスを有する場合、セルフ９０は、自身 より下位にある列内のセルフ３０のうちのいずれかよりメツセージパケットを受 信する。１個のメツセージパケットのみがセルフ９０に供給されると、このメツ セージパケットは、同一のデータ経路６００上にあって１本右隣の列にあるセル フ３０へとマルチプレクサ７９２によって転送される。２個のメツセージパケッ トがセルフ９０によって受信されると、これらのパケットは、ルーティングによ って選択される機能に従って組合せられる。このルーティングはマルチプレクサ ７９４によって行なわれ、セルフ９０内の回路のうち、当該機能の実行に適した 回路にメツセージパケットを転送する動作である。たとえば、論理和演算が選択 されると、２個のメッセージパケットはＯＲゲート７９６へと送られ、加算演算 が選択されると、これらのパケットは排他的ＯＲゲート７９７へと送られる。ま た、メツセージパケットを全加算器に供給してもよい、当該技術で知られている 他の回路を使用して、最大化機能や重ね書き機能（７９８゜７９９）　、および 他の有益な機能を実施することもできる。

これらの回路の出力は、セルフ９０と同一のデータ経路６００上にあって１本右 隣の列にあるセルフ３０へと同様に供給される。

組合せ器５６５のセルフ３０および７９０は、同一のプロセッサ１１２に宛てら れたすべてのメツセージパケットの識別１組合せを行ない、またデータ経路６０ ０上でこの経路より優先順位の高い経路に対して上方向にパケットの圧縮を行な う。

次にメツセージパケットはエジェクタ５７５へと供給される。エジェクタ５７５ は、７Ｘ１６クロスバースイツチである。このスイッチは、いずれかのデータ経 路６００上にあるメツセージパケットを、いずれかのプロセッサ１１２に対応す る出力回線へと供給する。またエジェクタは、プロセッサ１１２から回線１４２ を介して送られた逆方向メツセージパケットを受信して、これらのパケットをデ ータ経路６０２のいずれかへと送り出すことができる。

第１６図に示されるように、エジェクタは、たとえば７個の１対１６マルチブレ クサ８０２と１６個のＯＲゲート８０４として実施できる。各マルチプレクサは 、データ経路６００のいずれかより入力を受け、１６個の出力をそれぞれＯＲゲ ート８０４に供給する。集積回路上のプロセッサ１１２のいずれかに宛てられた メツセージパケットが受信されたことを示す信号が、アドレス検査器５７０から 回線５７２を介して送られると、マルチプレクサはこの信号によって使用可能に される。任意のマルチプレクサから出ている特定の出力回線が１表■の例で示さ れたビット位置１３−１６のプロセッサアドレスビットによって選択される。こ れらのビットは１回線５７２を介してアドレス検査器５７０からマルチプレクサ の制御入力へと供給される。

エジェクタ５７５はさらに、７個の１６対ｌマルチプレクサを有している。それ ぞれのマルチプレクサは１６個の入力を有する。すなわち１６個のプロセッサ１ １２から出ている回線１４２の各々より１点ずつの入力である。

また各マルチプレクサは、データバス６０２の７回線のいずれかに対して１点の 出力を有する。マルチプレクサに至る特定の入力回線が、メツセージパケットの プロセッサアドレスビットによって選択される。これらのビットは、回線８０５ を介してマルチプレクサの制御入力に供給されている。

以上の説明で明ら、かなように、ラッチを使用して。

メツセージパケットを注入器２回線割当て器および組合せ器の間で切換えている 。これらのラッチの状態は。

制御回路１５０によっていつでも読取ることができる。

また特にこの制御回路は、ルータのすべてのサイクルにおけるラッチの状態を記 録できる。ラッチの状態がメツセージパケットの順方向のルーティング経路を決 定しているため、この情報を、ラッチから得た順序と逆の順序でラッチに戻すこ とにより、メツセージパケットの逆方向のルーティング経路を決定できる。すな わち、パケットの順方向のルーティングのために最後に使用した情報が、該パケ ットの逆方向のルーティングのために最初に使用する情報となる。

例式コンピュータに同報通信機能を実現することができる。複数のメツセージパ ケットを、共通の宛先に向けて順方向にルーティングすることが可能である。こ れらのパケットは組合せ器によって単一のパケットに組替えられ、このパケット が最終的に宛先プロセッサに供給される。そののち、宛先プロセッサからパケッ ト１個がエジェクタ内のメツセージ経路へと挿入されて、逆方向へと送られる。

このパケットは、組合せ器に達すると複製される。このときセルフ３０内のラッ チは、順方向メツセージパケットが組合せられた条件を。

逆の順序で再現する４、複製されたメツセージパケットは、回線割当て器を経て 、順方向メツセージパケットの出発点である回路へと戻される。このとき回線割 当て器内のラッチ７１２．７１４は、立方体配線のルーティングシーケンスを逆 の順序で再現する。最後にメツセージパケットは、ＪＪ方向メツセージパケット の出発点であるプロセッサへと至る。このときラッチ５５２．５８６は。

順方向メツセージパケットがルーティングのために受理された・条件を逆の順序 で再現する。

以上で明らかなように、多数の実施例が本出願の精神と範囲を逸脱することなく 可能である。

ＦＩＧ、８ ＦＩＧ、１１ ＦＩＧ、　　１２Ａ ＦＩＧ、１３Ａ ＦＩＧ、１３Ｂ ＦＩＧ、’１６ 補正書の翻訳文提出書（特許法第１８４条の８）平成　１年１０月２７日 特許庁長官　吉　１）文　毅　殿 １、国際出願番号　　　ＰＣＴ／ＵＳ８８１０１３４１３、特許出願人 住　所　　　アメリカ合衆国　マサチューセッツ　０２１４２ケインブリツジ　 ファースト　ストリート　２４５名　称　　　スインキング　マシーンズ　コー ポレーション代表者　ハンドラー　、シェリル 国　籍　　　アメリカ合衆国 ４、代理人 住　　所　　　　東京都千代田区丸の内−丁目５番１号５、補正書の提出年月日 　　１９８９年（平成１年）６月１５日６、添付書類の目録 請求の範囲 １、複数のプロセッサと、Ｎが２以上であるＮ次元の各々においてプロセッサ間 の通信に使用される通信回線を有するＮ次元相互接続ネットワークとからなる並 列式コンピュータにおいて、第一のプロセッサから第二のプロセッサへと至る前 記通信回線上で宛先を指定されたメツセージパケットのルーティングを行なう装 置であって、前記ネットワーク内の複数のノードの各々において、 送信元プロセッサから宛先プロセッサへと送られるメツセージパケットを途中で 蓄積するメモリと、ルーティングの対象であるメツセージパケットを、前記送信 元プロセッサと前記宛先プロセッサとの間のノードに接続される通信回線へと選 択的に接続する手段であって、前記接続を前記メツセージパケット内のアドレス 情報に従って行なう手段と。

宛先プロセッサへのルーティングを指定されたメツセージパケットを、送信元プ ロセッサにおいて待ち行列内へと選択的に挿入する手段と。

宛先プロセッサにある前記メモリから、前記宛先プロセッサに宛てられたメツセ ージパケットを選択的に取除く手段と。

メツセージパケットを第一のプロセッサから第二のプロセッサへとルーティング を行なう過程において。

前記選択的接続手段、前記選択的挿入手段、および前記選択的除去手段の連続し た動作行程での動作状態を記録する手段と、 前記選択的接続手段、前記選択的挿入手段、および前記選択的除去手段の前記動 作状態を、メツセージパケットを第一のプロセッサから第二のプロセッサへとル ーティングする場合と逆の順序で再生することにより、メツセージパケットを前 記第二プロセッサから前記第一プロセッサへと送る手段とを有することを特徴と する装置。

２、請求項１記載の装置であって、同一のプロセッサに宛てられた複数のメツセ ージパケットを組合せる手段を有する装置。

３、請求項２記載の装置であって。

メツセージパケットを第一のプロセッサから第二のプロセッサへとルーティング する過程での連続した動作行程における組合せ手段の動作状態を記録する手段と 。

前記複数のメツセージパケット組合せる場合と逆の順序で組合せを行なう組合せ 器の動作状態を再生することにより、前記第二プロセッサから送られるメツセー ジパケットを複製する手段とを有する装置。

４、請求項１記載の装置において、前記メモリが前記選択的接続手段、前記選択 的挿入手段、および前記選択的除去手段を経て流れる複数のチャネルを有してお り、 前記選択的接続手段が、各チャネルとネットワークの各次元とに対して、前記メ ツセージパケット内のアドレス情報を検査して、前記メツセージパケットを、宛 先であるネットワークの任意の次元に対応する通信回線へと挿入するための装置 を有していることにおいて構成されている装置。

５、Ｍ求項１記載の装置において、前記メモリが前記選択的接続手段、前記選択 的挿入手段、および前記選択的除去手段を経て流れる複数のチャネルを有してお り。

前記選択的挿入手段が、少なくとも１個のチャネルと前記ノードにあるすべての プロセッサとに対して。

メツセージパケットを１台のプロセッサから前記チャネルへと挿入する切換え手 段を有しており、１０、請求項６記載の装置において、前記メモリが前記選択的 接続手段、前記選択的挿入手段、および前記選択的除去手段を経て流れる複数の チャネルを有しており。

前記選択的挿入手段が、少なくとも１個のチャネルと前記ノードにあるすべての プロセッサとに対して。

メツセージパケットを１台のプロセッサから前記チャネルへと挿入する切換え手 段を有しており。

前記選択的除去手段が、少なくとも１個のチャネルと前記ノードにあるすべての プロセッサとに対して。

前記プロセッサに宛てられたメツセージパケットを前記チャネルから移動する手 段を有していることにおいて構成されている装置。

１１、複数のプロセッサと、Ｎが２以上であるＮ次元の各々においてプロセッサ 間の通信に使用される通信回線を有するＮ次元相互接続ネットワークとからなる 並列式コンピュータにおいて、第一のプロセッサから第二のプロセッサとの間の 通信回線を介して、宛先を指定されたメツセージパケットのルーティングを行な う方法であって。

前記ネットワーク内の複数のノードの各々において。

送信元プロセッサから宛先プロセッサへと送られるメツセージパケットを途中で 蓄積する段階と、前記送信元プロセッサと前記宛先プロセッサとの間にあるノー ドに接続された通信回線に、メツセージパケットを選択的に接続する段階であっ て、前記接続を前記メツセージパケット内のアドレス情報に従って行なう段階と 。

宛先プロセッサへのルーティングを指定されたメツセージパケットを、送信元プ ロセッサにおいて待ち行列内へと選択的に挿入する段階と、 宛先プロセッサにある前記メモリから、前記宛先ブ取除く段階と、 国際調査報告

Claims (19)

【特許請求の範囲】
1. １．複数のプロセッサと、Ｎが２以上であるＮ次元の各々においてプロセッサ間 の通信に使用される通信回線を有するＮ次元相互接続ネットワークとからなる並 列式コンピュータにおいて、第一のプロセッサから第二のプロセッサへと至る前 記通信回線上で宛先を指定されたメッセージパケットのルーティングを行なう装 置であって、前記ネットワーク内の複数のノードの各々において、 送信元プロセッサから宛先プロセッサへと送られるメッセージパケットを途中で 蓄積するメモリと、ルーティングの対象であるメッセージパケットを、前記送信 元プロセッサと前記宛先プロセッサとの間のノードに接続される通信回線へと選 択的に接続する手段であって、前記接続を前記メッセージパケット内のアドレス 情報に従って行なう手段と、 宛先プロセッサへのルーティングを指定されたメッセージパケットを、送信元プ ロセッサにおいて待ち行列内へと選択的に挿入する手段と、 宛先プロセッサにある前記メモリから、前記宛先プロセッサに宛てられたメッセ ージパケットを選択的に取除く手段と、 メッセージパケットを第一のプロセッサから第二のプロセッサへとルーティング を行なう過程において、前記選択的接続手段、前記選択的挿入手段、および前記 選択的除去手段の連続した動作行程での動作状態を記録する手段と、 前記選択的接続手段、前記選択的挿入手段、および前記選択的除去手段の前記動 作状態を、メッセージパケットを第一のプロセッサから第二のプロセッサへとル ーティングする場合と逆の順序で再生することにより、メッセージパケットを前 記第二プロセッサから前記第一プロセッサへと送る手段とを有することを特徴と する装置。
2. ２．請求項１記載の装置であって、同一のプロセッサに宛てられた複数のメッセ ージパケットを組合せる手段を有する装置。
3. ３．請求項２記載の装置であって、 メッセージパケットを第一のプロセッサから第二のプロセッサへとルーティング する過程での連続した動作行程における組合せ手段の動作状態を記録する手段と 、 前記複数のメッセージパケット組合せる場合と逆の順序で組合せを行なう組合せ 器の動作状態を再生することにより、前記第二プロセッサから送られるメッセー ジパケットを複製する手段とを有する装置。
4. ４．請求項１記載の装置において、前記メモリが前記選択的接続手段、前記選択 的挿入手段、および前記選択的除去手段を経て流れる複数のチャネルを有してお り、 前記選択的接続手段が、各チャネルとネットワークの各次元とに対して、前記メ ッセージパケット内のアドレス情報を検査して、前記メッセージパケットを、宛 先であるネットワークの任意の次元に対応する通信回線へと挿入するための装置 を有していることにおいて構成されている装置。
5. ５．請求項１記載の装置において、前記メモリが前記選択的接続手段、前記選択 的挿入手段、および前記選択的除去手段を経て流れる複数のチャネルを有してお り、 前記選択的挿入手段が、少なくとも１個のチャネルと前記ノードにあるすべての プロセッサとに対して、メッセージパケットを１台のプロセッサから前記チャネ ルへと挿入する切換え手段を有しており、前記選択的除去手段が、少なくとも１ 個のチャネルと前記ノードにあるすべてのプロセッサとに対して、前記プロセッ サに宛てられたメッセージパケットを前記チャネルから移動する手段を有してい ることにおいて構成されている装置。
6. ６．並列式コンピュータであって、 それぞれ少なくとも１台のプロセッサを有する複数の集積回路を有し、 Ｎ次元の各々においてプロセッサ間の通信に使用される通信回線を有する集積回 路を相互接続するＮ次元のネットワークであって、Ｎが２以上であるネットワー クを有し、 第一のプロセッサから第二のプロセッサへと前記通信回線を介して、宛先を指定 されたメッセージパケットのルーティングを行なう手段であって、前記ネットワ ーク内での複数の前記集積回路の各々について、送信元プロセッサから宛先プロ セッサへと送られるメッセージバケットを途中で蓄積するメモリと、メッセージ パケットを、前記送信元プロセッサと前記宛先プロセッサとの間の集積回路に接 続される通信回線へと選択的に接続する手段であって、前記接続を前記メッセー ジパケット内のアドレス情報に従って行なう手段と、 宛先プロセッサへのルーティングを指定されたメッセージパケットを、送信元プ ロセッサにおいて待ち行列内へと選択的に挿入する手段と、 宛先プロセッサにある前記メモリから、前記宛先プロセッサに宛てられたメッセ ージパケットを選択的に取除く手段と、 メッセージパケットを第一のプロセッサから第二のプロセッサへとルーティング を行なう過程において、前記選択的接続手段、前記選択的挿入手段、および前記 選択的除去手段の連続した動作行程での動作状態を記録する手段と、 前記選択的接続手段、前記選択的挿入手段、および前記選択的除去手段の前記動 作状態を、メッセージパケットを第一のプロセッサから第二のプロセッサへとル ーティングする場合と逆の順序で再生することにより、メッセージパケットを前 記第二プロセッサから前記第一プロセッサへと送る手段とからなるルーティング 手段とを有することを特徴とする並列式コンピュータ。
7. ７．請求項６記載の装置であって、同一のプロセッサに宛てられた複数のメッセ ージバケットを組合せる手段を有する装置。
8. ８．請求項６記載の装置であって、 メッセージバケットを第一のプロセッサから第二のプロセッサへとルーティング する過程での連続した動作行程における動作状態を記録する手段と、前記複数の メッセージバケットを組合せる場合と逆の順序で組合せを行なう組合せ器の動作 状態を再生することにより、前記第二プロセッサから送られるメッセージパケッ トを複製する手段とを有する装置。
9. ９．請求項６記載の装置であって、 前記メモリが前記選択的接続手段、前記選択的挿入手段、および前記選択的除去 手段を経て流れる複数のチャネルを有しており、 前記選択的接続手段が、各チャネルとネットワークの各次元とに対して、前記メ ッセージパケット内のアドレス情報を検査して、前記メッセージバケットを、宛 先であるネットワークの任意の次元に対応する通信回線へと挿入するための装置 を有していることにおいて構成されている装置。
10. １０．請求項６記載の装置において、前記メモリが前記選択的接続手段、前記選 択的挿入手段、および前記選択的除去手段を経て流れる複数のチャネルを有して おり、 前記選択的挿入手段が、少なくとも１個のチャネルと前記ノードにあるすべての プロセッサとに対して、メッセージパケットを１台のプロセッサから前記チャネ ルへと挿入する切換え手段を有しており、前記選択的除去手段が、少なくとも１ 個のチャネルと前記ノードにあるすべてのプロセッサとに対して、前記プロセッ サに宛てられたメッセージパケットを前記チャネルから移動する手段を有してい ることにおいて構成されている装置。
11. １１．複数のプロセッサと、Ｎが２以上であるＮ次元の各々においてプロセッサ 間の通信に使用される通信回線を有するＮ次元相互接続ネットワークとからなる 並列式コンピュータにおいて、第一のプロセッサから第二のプロセッサとの間の 通信回線を介して、宛先を指定されたメッセージパケットのルーティングを行な う方法であって、 前記ネットワーク内の複数のノードの各々において、送信元プロセッサから宛先 プロセッサへと送られるメッセージパケットを途中で蓄積する段階と、前記送信 元プロセッサと前記宛先プロセッサとの間にあるノードに接続された通信回線に 、メッセージパケットを選択的に接続する段階であって、前記接続を前記メッセ ージパケット内のアドレス情報に従って行なう段階と、 宛先プロセッサへのルーティングを指定されたメッセージパケットを、送信元プ ロセッサにおいて待ち行列内へと選択的に挿入する段階と、 宛先プロセッサにある前記メモリから、前記宛先プロセッサに宛てられたメッセ ージパケットを選択的に取除く段階と、 メッセージパケットを第一のプロセッサから第二のプロセッサへとルーティング を行なう過程において、前記選択的接続手段、前記選択的挿入手段．および前記 選択的除去手段の連続した動作行程での動作状態を記録する段階と、 前記選択的接続手段、前記選択的挿入手段、および前記選択的除去手段の前記動 作状態を、メッセージパケットを第一のプロセッサから第二のプロセッサへとル ーティングする場合と逆の順序で再生することにより、メッセージパケットを前 記第二プロセッサから前記第一プロセッサへと送る段階とからなる方法。
12. １２．請求項１１記載の方法であって、同一のプロセッサに宛てられた複数のメ ッセージパケットを組合せる段階を有する方法。
13. １３．請求項１２記載の方法であって、メッセージパケットを第一のプロセッサ から第二のプロセッサへとルーティングする過程での連続した動作行程における 組合せ手段の動作状態を記録する段階と、 前記複数のメッセージパケットを組合せる場合と逆の順序で組合せを行なう組合 せ器の動作状態を再生することにより、前記第二プロセッサから送られるメッセ ージバケットを複製する段階とからなる方法。
14. １４．請求項１１記載の方法であって、メッセージパケットが複数のチャネル内 に蓄積されており、選択的接続段階が、各チャネルとネットワークの各次元とに 対して、前記メッセージパケット内のアドレス情報を検査して、前記メッセージ パケットを、宛先であるネットワークの任意の次元に対応する通信回線へと挿入 することにより構成されている方法。
15. １５．二次元以上のパターンで相互に接続されたノードからなるネットワークを 介して、メッセージパケットのルーティングを行なう方法であって、メッセージ パケット内のアドレス情報に従って前記パターンで第一のノードから第二のノー ドへとルーティングされる前記メッセージバケットを生成する段階であって、前 記アドレス情報は次元数と同一数の桁からなり、各桁が単一の次元に対応するア ドレス指定情報を提供することにより構成される段階と、任意のノードで受信さ れた前記メッセージパケットのアドレスの各桁を検査して、該桁に対応する次元 での宛先にメッセージバケットが到達したかどうかを決定する段階と、 検査された桁が、当該次元での宛先にメッセージパケットが到達していないこと を示しており、かつ同一次元で異なるノードへの接続が可能である場合に、前記 メッセージパケットを該ノードへとルーティングする段階と、 前記メッセージパケットのルーティングがなされない場合に、前記メッセージバ ケットのアドレスの他の桁を検査して、該桁に対応する次元においてメッセージ パケットがその宛先へ到達したかどうかを決定する段階と、 メッセージパケットを第一のノードから第二のノードへとルーティングする過程 での連続した動作行程におけるルーティング手段の動作状態を記録する段階と、 メッセージパケットを第一のノードから第二のノードへとルーティングする場合 と逆の順序で、ルーティング手段の動作状態を再生することにより、前記第二ノ ードから前記第一ノードへとメッセージパケットを送る段階とからなる方法。
16. １６．二次元以上のパターンで相互に接続されたノードからなるネットワークを 介して、メッセージパケットのルーティングを行なう方法であって、複数のメッ セージパケットを生成する段階であって、各メッセージパケットが前記パターン で該パケットのアドレス情報に従ってそれぞれ異なる送信元ノードから宛先ノー ドへとルーティングされ、前記アドレス情報は次元数と同一数の桁からなり、各 市が単一の次元に対するアドレス指定情報を提供することにより構成される段階 と、 各ノードにおいて受信された前記メッセージパケットのアドレスの各桁を検査し て、該桁に対応する次元においてメッセージパケットがその宛先に到達したかど うかを決定する段階と、 検査された桁が、当該次元での宛先にメッセージパケットが到達していないこと を示しており、かつ同一次元で異なるノードへの接続が可能である場合に、前記 メッセージパケットを該ノードへとルーティングする段階と、 前記メッセージパケットのルーティングがなされない場合に、前記メッセージパ ケットのアドレスの他の桁を検査して、該桁に対応する次元においてメッセージ パケットがその宛先へ到達したかどうかを決定する段階と、 メッセージパケットを送信元ノードから宛先ノードへとルーティングする過程で の連続した動作行程におけるルーティング手段の動作状態を記録する段階と、メ ッセージバケットを送信元ノードから宛先ノードへとルーティングする場合と逆 の順序で、ルーティング手段の動作状態を再生することにより、前記宛先ノード から前記送信元ノードへとメッセージパケットを送る段階とからなる方法。
17. １７．二次元以上のパターンで相互に接続されたノードからなるネットワークを 介して、メッセージパケットのルーティングを行なう方法であって、メッセージ パケットを生成する段階であって、該メッセージパケットが前記パターンで該パ ケットのアドレス情報に従って第一のノードから第二のノードへとルーティング され、前記アドレス情報は次元数と同一数の桁からなり、各桁が単一の次元に対 するアドレス指定情報を提供することにおいて構成される段階と、ルーティング サイクルの第一の周期において、前記メッセージバケットのアドレスの最初の桁 を検査する段階であって、前記メッセージパケットは前記桁に対応する第一のノ ードにあり、前記検査によって前記桁に対応する一次元の宛先にメッセージパケ ットが到着したかどうかを決定する段階と、 検査された桁が、当該次元での宛先にメッセージパケットが到達していないこと を示しており、かつ同一次元で異なるノードへの接続が可能である場合に、前記 メッセージバケットを該ノードへとルーティングする段階と、 同一のルーティングサイクルの第二の周期において、前記メッセージバケットの アドレスの第二の桁を検査する段階であって、前記メッセージパケットは前記桁 に対応するノードにあり、前記検査によって前記桁に対応する二次元の宛先にメ ッセージパケットが到着したかどうかを決定する段階と、 検査された桁が、当該次元での宛先にメッセージパケットが到達していないこと を示しており、かつ同一次元で異なるノードへの接続が可能である場合に、前記 メッセージパケットを該ノードへとルーティングする段階と、 同一のルーティングサイクルの追加周期において、アドレス情報の全桁が、各桁 に対応するノードにて検査されるまでメッセージパケットのルーティングを行な うことにより、１回のルーティングサイクルで、メッセージパケットを次元数と 同一数のノードを介して直列にルーティングする段階と、 メッセージパケットを第一のノードから第二のノードへとルーティングする過程 において、連続した動作行程でルーティング段階を実行する手段の動作状態を記 録する段階と、 メッセージバケットを第一のノードから第二のノードへとルーティングする場合 と逆の順序で、前記ルーティング段階を実行する手段の動作状態を再生すること により、前記第二ノードから前記第一ノードへとメッセージバケットを送る段階 とからなる方法。
18. １８．二次元以上のパターンで相互に接続されたノードからなるネットワークを 介して、メッセージパケットのルーティングを行なう方法であって、メッセージ バケットを生成する段階であって、該メッセージパケットが前記パターンで該パ ケットのアドレス情報に従って第一のノードから第二のノードへとルーティング され、前記アドレス情報は次元数と同一数の桁からなり、各桁が単一の次元に対 するアドレス指定情報を提供することにおいて構成される段階と、ルーティング サイクルの連続する周期において、前記メッセージパケットのアドレスの連続す る桁を検査する段階であって、当該メッセージパケットは検査中の各桁に対応す るノードにあり、前記検査によってメッセージパケットが該桁に対応する次元で その宛先に到達したかどうかを決定する段階と、 検査された桁が、当該次元での宛先にメッセージパケットが到達していないこと を示しており、かつ該次元で異なるノードへの接続が可能である場合に、前記メ ッセージパケットを該ノードへとルーティングする段階と、 メッセージバケットがその宛先であるノードに到達するまでルーティングサイク ルを繰返す段階と、メッセージバケットを第一のノードから第二のノードへとル ーティングする過程において、連続した動作行程で前記メッセージパケットのル ーティングを行なう手段の動作状態を記録する手段と、 メッセージパケットを第一のノードから第二のノードへとルーティングする場合 と逆の順序でルーティング手段の動作状態を再生することにより、前記第二ノー ドから前記第一ノードへとメッセージパケットを送る段階とからなる方法。
19. １９．二次元以上のパターンで相互に接続されたノードからなるネットワークを 介して、メッセージバケットのルーティングを行なう装置であって、メッセージ パケットを生成する手段であって、該メッセージバケットが前記パターンで該パ ケットのアドレス情報に従って第一のノードから第二のノードへとルーティング され、前記アドレス情報は次元数と同一数の桁からなり、各桁が単一の次元に対 するアドレス指定情報を提供することにおいて構成される手段と、ルーティング サイクルの連続する周期において機能する手段であって、前記メッセージパケッ トのアドレスの連続する桁を検査し、当該メッセージバケットは検査中の各桁に 対応するノードにあり、前記検査によってメッセージバケットが該桁に対応する 次元でその宛先に到達したかどうかを決定する手段であるとともに、検査された 桁が、当該次元での宛先にメッセージパケットが到達していないことを示してお り、かつ該次元で異なるノードへの接続が可能である場合に、前記メッセージパ ケットを該ノードへとルーティングする手段と、 メッセージパケットがその宛先であるノードに到達するまでルーティングサイク ルを繰返す手段と、メッセージパケットを第一のノードから第二のノードへとル ーティングする過程において、連続した動作行程での前記ルーティング手段の動 作状態を記録する手段と、 メッセージパケットを第一のノードから第二のノードへとルーティングする場合 と逆の順序でルーティング手段の動作状態を再生することにより、前記第二ノー ドから前記第一ノードへとメッセージパケットを送る段階とからなる方法。