JPH0630455A - マトリクス検索ネットワーク - Google Patents
マトリクス検索ネットワークInfo
- Publication number
- JPH0630455A JPH0630455A JP19874391A JP19874391A JPH0630455A JP H0630455 A JPH0630455 A JP H0630455A JP 19874391 A JP19874391 A JP 19874391A JP 19874391 A JP19874391 A JP 19874391A JP H0630455 A JPH0630455 A JP H0630455A
- Authority
- JP
- Japan
- Prior art keywords
- matrix
- search
- stage
- bus
- cells
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L12/00—Data switching networks
- H04L12/54—Store-and-forward switching systems
- H04L12/56—Packet switching systems
- H04L12/5601—Transfer mode dependent, e.g. ATM
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F7/22—Arrangements for sorting or merging computer data on continuous record carriers, e.g. tape, drum, disc
- G06F7/24—Sorting, i.e. extracting data from one or more carriers, rearranging the data in numerical or other ordered sequence, and rerecording the sorted data on the original carrier or on a different carrier or set of carriers sorting methods in general
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L49/00—Packet switching elements
- H04L49/10—Packet switching elements characterised by the switching fabric construction
- H04L49/104—Asynchronous transfer mode [ATM] switching fabrics
- H04L49/105—ATM switching elements
- H04L49/106—ATM switching elements using space switching, e.g. crossbar or matrix
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L49/00—Packet switching elements
- H04L49/15—Interconnection of switching modules
- H04L49/1553—Interconnection of ATM switching modules, e.g. ATM switching fabrics
- H04L49/1561—Distribute and route fabrics, e.g. Batcher-Banyan
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L49/00—Packet switching elements
- H04L49/15—Interconnection of switching modules
- H04L49/1553—Interconnection of ATM switching modules, e.g. ATM switching fabrics
- H04L49/1576—Crossbar or matrix
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F2207/00—Indexing scheme relating to methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F2207/22—Indexing scheme relating to groups G06F7/22 - G06F7/36
- G06F2207/228—Sorting or merging network
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L12/00—Data switching networks
- H04L12/54—Store-and-forward switching systems
- H04L12/56—Packet switching systems
- H04L12/5601—Transfer mode dependent, e.g. ATM
- H04L2012/5625—Operations, administration and maintenance [OAM]
- H04L2012/5627—Fault tolerance and recovery
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L12/00—Data switching networks
- H04L12/54—Store-and-forward switching systems
- H04L12/56—Packet switching systems
- H04L12/5601—Transfer mode dependent, e.g. ATM
- H04L2012/5628—Testing
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Physics & Mathematics (AREA)
- Mathematical Physics (AREA)
- General Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Computer Hardware Design (AREA)
- General Physics & Mathematics (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
- Use Of Switch Circuits For Exchanges And Methods Of Control Of Multiplex Exchanges (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
(57)【要約】
【目的】 検索マトリクスの段数を少なくすることによ
り、遅延量を小さくし演算速度を速くする。また、検索
マトリクスを（ｌｏｇ2Ｎ）のステージで構成すること
により、完全に配置されたネットワークのサイズを減少
する。 【構成】 Ｎ入力を検索してＮ出力を出力するマトリク
ス検索ネットワークにおいて、検索マトリクスは（ｌｏ
ｇ2Ｎ）のステージから構成され、各ステージは（Ｎ／
２Ｍ）×（Ｎ／２Ｍ）マトリクスの検索セルを含むよう
に構成される。ここでＭは第１のステージのマトリクス
ではＮ／２、第２のステージのマトリクスではＮ／４、
第３のステージのマトリクスではＮ／８、第ｍのステー
ジのマトリクスではＮ／２mの値を取る数である。
り、遅延量を小さくし演算速度を速くする。また、検索
マトリクスを（ｌｏｇ2Ｎ）のステージで構成すること
により、完全に配置されたネットワークのサイズを減少
する。 【構成】 Ｎ入力を検索してＮ出力を出力するマトリク
ス検索ネットワークにおいて、検索マトリクスは（ｌｏ
ｇ2Ｎ）のステージから構成され、各ステージは（Ｎ／
２Ｍ）×（Ｎ／２Ｍ）マトリクスの検索セルを含むよう
に構成される。ここでＭは第１のステージのマトリクス
ではＮ／２、第２のステージのマトリクスではＮ／４、
第３のステージのマトリクスではＮ／８、第ｍのステー
ジのマトリクスではＮ／２mの値を取る数である。
Description
【０００１】
【産業上の利用分野】本発明はデータ処理システムに関
するものであり、より詳細にはパケット交換システムに
関するものである。さらに詳しく述べれば、本発明は、
例えば、非同期転送モード（ＡＴＭ）交換制御又はコン
ピュータのコプロセサに用いる検索ネットワークに関す
るものである。
するものであり、より詳細にはパケット交換システムに
関するものである。さらに詳しく述べれば、本発明は、
例えば、非同期転送モード（ＡＴＭ）交換制御又はコン
ピュータのコプロセサに用いる検索ネットワークに関す
るものである。
【０００２】
【従来の技術】ＡＴＭパケット交換ネットワークにおい
ては、外部回線の競合を解決するためにしばしばバンヤ
ン(Banyan)ネットワークのような内部バッファが用いら
れる。バッファに代わるものとして、検索ネットワーク
が用いられる。最も有名なものはバッチャー・バンヤン
(Batcher Banyan)ネットワーク中で動作するバッチャ・
ビトニック(Batcher bitonic)検索装置である。
ては、外部回線の競合を解決するためにしばしばバンヤ
ン(Banyan)ネットワークのような内部バッファが用いら
れる。バッファに代わるものとして、検索ネットワーク
が用いられる。最も有名なものはバッチャー・バンヤン
(Batcher Banyan)ネットワーク中で動作するバッチャ・
ビトニック(Batcher bitonic)検索装置である。
【０００３】一般に、通信システム、コンピュータシス
テムにおいては、システムが受信した信号を検索するた
めに、バッチャ・ビトニック検索装置が必要又は望まし
いものである。検索の結果、例えば、優先度の低いもの
と高いものとが区別される。信号の優先度は、例えば、
特殊な信号成分の振幅を基準に定められる。
テムにおいては、システムが受信した信号を検索するた
めに、バッチャ・ビトニック検索装置が必要又は望まし
いものである。検索の結果、例えば、優先度の低いもの
と高いものとが区別される。信号の優先度は、例えば、
特殊な信号成分の振幅を基準に定められる。
【０００４】図２は従来の３２ポートのバッチャ検索ネ
ットワークを示す図である。図において、各セルは基本
的には２入力２出力の２極双投式スイッチとして動作す
る。図中で相互に接続された２４０のセル３１は３２の
入力を検索して３２の出力を得るために用いられる。こ
の検索ネットワークは本発明のマトリクス検索ネットワ
ークよりも少ない簡単なセルを使用しているが、相互接
続トポロジは複雑になっている。特に、出力方向につい
ては複雑であり、かつ、柔軟性が少ないものである。
ットワークを示す図である。図において、各セルは基本
的には２入力２出力の２極双投式スイッチとして動作す
る。図中で相互に接続された２４０のセル３１は３２の
入力を検索して３２の出力を得るために用いられる。こ
の検索ネットワークは本発明のマトリクス検索ネットワ
ークよりも少ない簡単なセルを使用しているが、相互接
続トポロジは複雑になっている。特に、出力方向につい
ては複雑であり、かつ、柔軟性が少ないものである。
【０００５】従来の検索機は検索モジュールを構成する
検索セルのサブステージの組を含んでいる。この検索モ
ジュールはステージ毎に２の因数によってサイズが増加
する。従来のこのような検索装置は２進演算を行い２つ
のマトリクスを１つのマトリクスに合体させ一対の検索
リスト上に出力していた。従来の技術の検索装置におけ
るステージとサブステージ間の接続パターンは非常に規
則的であり、３次元用としては最高のものである。
検索セルのサブステージの組を含んでいる。この検索モ
ジュールはステージ毎に２の因数によってサイズが増加
する。従来のこのような検索装置は２進演算を行い２つ
のマトリクスを１つのマトリクスに合体させ一対の検索
リスト上に出力していた。従来の技術の検索装置におけ
るステージとサブステージ間の接続パターンは非常に規
則的であり、３次元用としては最高のものである。
【０００６】
【発明が解決しようとする課題】しかしながら、、その
ような検索装置では面上へ投射するときに非常に大きな
スペースが必要となる。そのような検索装置では交差す
る信号、クロック及び電源を供給するために３重又は４
重の相互接続のための層が必要である。そのような複雑
な相互接続トポロジのために、バッチャ検索装置の一部
を取り除くことは不可能であった。
ような検索装置では面上へ投射するときに非常に大きな
スペースが必要となる。そのような検索装置では交差す
る信号、クロック及び電源を供給するために３重又は４
重の相互接続のための層が必要である。そのような複雑
な相互接続トポロジのために、バッチャ検索装置の一部
を取り除くことは不可能であった。
【０００７】複雑なマトリクス構成中に同一の単純な検
索セルを含む検索ネットワークを用いることにより、よ
り良い動作とよりフレキシブルな構成が得られる。特
に、列と行によって既に検索されたＮ入力に対して、Ｎ
／２列のセルとＮ／２行のセルの検索マトリクスを用い
て、２つの入力群を合体することによって斜め出力線上
にＮ検索出力を生じる。前もって検索された入力群は、
単一の入力のレベルに落とした出力と同じ種類の２つの
より小さなマトリクス出力になる。
索セルを含む検索ネットワークを用いることにより、よ
り良い動作とよりフレキシブルな構成が得られる。特
に、列と行によって既に検索されたＮ入力に対して、Ｎ
／２列のセルとＮ／２行のセルの検索マトリクスを用い
て、２つの入力群を合体することによって斜め出力線上
にＮ検索出力を生じる。前もって検索された入力群は、
単一の入力のレベルに落とした出力と同じ種類の２つの
より小さなマトリクス出力になる。
【０００８】したがって、本発明は、（ｌｏｇ2Ｎ）ス
テージの検索マトリクスを含むＮ信号を検索するための
装置を提供するものである。そのマトリクス中で各ステ
ージは検索マトリクス（Ｎ／２Ｍ）×（Ｎ／２Ｍ）を含
む。ここでＭは第１のステージのマトリクスではＮ／
２、第２のステージのマトリクスではＮ／４、第３のス
テージのマトリクスではＮ／８、第ｍのステージのマト
リクスではＮ／２mの値を取る数である。
テージの検索マトリクスを含むＮ信号を検索するための
装置を提供するものである。そのマトリクス中で各ステ
ージは検索マトリクス（Ｎ／２Ｍ）×（Ｎ／２Ｍ）を含
む。ここでＭは第１のステージのマトリクスではＮ／
２、第２のステージのマトリクスではＮ／４、第３のス
テージのマトリクスではＮ／８、第ｍのステージのマト
リクスではＮ／２mの値を取る数である。
【０００９】そのような装置の好ましい演算は、検索マ
トリクスは（Ｎ／２Ｍ）×（［Ｎ／２Ｍ］＋１）の検索
マトリクスを含むほぼ正方マトリクスでなされる。この
ような上記装置は入力集合と対応する出力間でいずれか
の端部に沿ってネットワークを部分的に取り除いても残
りのネットワークの動作に影響を与えないという利点が
ある。これは、試験及び故障診断を行う場合に、完全に
配置されたネットワークのサイズを劇的に減少させるこ
とが容易である。
トリクスは（Ｎ／２Ｍ）×（［Ｎ／２Ｍ］＋１）の検索
マトリクスを含むほぼ正方マトリクスでなされる。この
ような上記装置は入力集合と対応する出力間でいずれか
の端部に沿ってネットワークを部分的に取り除いても残
りのネットワークの動作に影響を与えないという利点が
ある。これは、試験及び故障診断を行う場合に、完全に
配置されたネットワークのサイズを劇的に減少させるこ
とが容易である。
【００１０】本発明の検索マトリクスはバッチャ・ビト
ニック検索装置と較べてＮの増加によってサイズがより
早く大きくなるという不利益はある。すなわち、本発明
ではサイズ増加はＮの２乗に比例するが、一方、バッチ
ャ・ビトニック検索装置のサイズ増加は（ｌｏｇ2Ｎ）
の２乗に比例する。
ニック検索装置と較べてＮの増加によってサイズがより
早く大きくなるという不利益はある。すなわち、本発明
ではサイズ増加はＮの２乗に比例するが、一方、バッチ
ャ・ビトニック検索装置のサイズ増加は（ｌｏｇ2Ｎ）
の２乗に比例する。
【００１１】しかしながら、ある範囲を超えた場合は、
本発明のマトリクス検索装置の演算速度はより早くな
る。例えば、１６又は３２程度の小さなＮに対しては、
これらの２つの装置のハードウエア構成はほぼ同様であ
るが、本発明のマトリクス検索装置の演算速度はバッチ
ャ・ビトニック検索装置と比較して非常に速いものであ
る。この演算速度はセルの段数によって変化する。例え
ば、従来技術の図１においては最上段の直線のルートを
通じて検索が行われる場合はセルが１５個直列に入る
が、本発明の図３においては最上段の直線のルートを通
じて検索が行われる場合はセルが５個直列に入るのみで
ある。したがって、本発明においてはセルの数を少なく
できるのでセルによる遅延が小さくなり、検索速度が非
常に速くなる。
本発明のマトリクス検索装置の演算速度はより早くな
る。例えば、１６又は３２程度の小さなＮに対しては、
これらの２つの装置のハードウエア構成はほぼ同様であ
るが、本発明のマトリクス検索装置の演算速度はバッチ
ャ・ビトニック検索装置と比較して非常に速いものであ
る。この演算速度はセルの段数によって変化する。例え
ば、従来技術の図１においては最上段の直線のルートを
通じて検索が行われる場合はセルが１５個直列に入る
が、本発明の図３においては最上段の直線のルートを通
じて検索が行われる場合はセルが５個直列に入るのみで
ある。したがって、本発明においてはセルの数を少なく
できるのでセルによる遅延が小さくなり、検索速度が非
常に速くなる。
【００１２】
【課題を解決するための手段】本発明は、Ｎ入力を検索
してＮ出力を出力するマトリクス検索ネットワークにお
いて、検索マトリクスは（ｌｏｇ2Ｎ）のステージから
構成され、各ステージは（Ｎ／２Ｍ）×（Ｎ／２Ｍ）マ
トリクスの検索セルを含むように構成される。ここでＭ
は第１のステージのマトリクスではＮ／２、第２のステ
ージのマトリクスではＮ／４、第３のステージのマトリ
クスではＮ／８、第ｍのステージのマトリクスではＮ／
２mの値を取る数である。
してＮ出力を出力するマトリクス検索ネットワークにお
いて、検索マトリクスは（ｌｏｇ2Ｎ）のステージから
構成され、各ステージは（Ｎ／２Ｍ）×（Ｎ／２Ｍ）マ
トリクスの検索セルを含むように構成される。ここでＭ
は第１のステージのマトリクスではＮ／２、第２のステ
ージのマトリクスではＮ／４、第３のステージのマトリ
クスではＮ／８、第ｍのステージのマトリクスではＮ／
２mの値を取る数である。
【００１３】
【作用】本発明においては、検索マトリクスは（ｌｏｇ
2Ｎ）のステージから構成され、検索に際して第１のス
テージ、第２のステージ、第３のステージ、第４のステ
ージのようなステージを経由して検索が行われる。した
がって、従来の検索パスと比較してステージの段数が少
なくなるので遅延量が小さくなり演算速度が速くなる。
2Ｎ）のステージから構成され、検索に際して第１のス
テージ、第２のステージ、第３のステージ、第４のステ
ージのようなステージを経由して検索が行われる。した
がって、従来の検索パスと比較してステージの段数が少
なくなるので遅延量が小さくなり演算速度が速くなる。
【００１４】
【実施例】図１は本発明の一実施例のマトリクス検索ネ
ットワークを示す図である。図において、３２の入力信
号を検索するための検索ネットワーク１０は５つの（ｌ
ｏｇ2Ｎ）ステージを有している。５つの各ステージは
１２ａー１２ｐ、１３ａ−１３ｈ、１４ａ−１４ｄ、１
５ａ−１５ｂ及び１６である。そこでは次のマトリクス
への行／列入力が診断出力となる。最終マトリクス１６
の３２の診断出力（１７ａ、１７ａ’から１７ｐ、１７
ｐ’まで）は全ネットワーク１０の出力を表わしてい
る。
ットワークを示す図である。図において、３２の入力信
号を検索するための検索ネットワーク１０は５つの（ｌ
ｏｇ2Ｎ）ステージを有している。５つの各ステージは
１２ａー１２ｐ、１３ａ−１３ｈ、１４ａ−１４ｄ、１
５ａ−１５ｂ及び１６である。そこでは次のマトリクス
への行／列入力が診断出力となる。最終マトリクス１６
の３２の診断出力（１７ａ、１７ａ’から１７ｐ、１７
ｐ’まで）は全ネットワーク１０の出力を表わしてい
る。
【００１５】図３は図１に対応した本発明の３２ポート
マトリクス検索ネットワークの相互接続の詳細を示す図
である。各マトリクス１２ａー１２ｐ、１３ａ−１３
ｈ、１４ａ−１４ｄ、１５ａ−１５ｂ及び１６は正方マ
トリクスではなく、それぞれ１×２、２×３、４×５、
８×９、及び１６×１７のマトリクスである。このよう
に正方マトリクスを用いない理由は、マトリクスの主斜
め線に沿った特別のセルを持たないように、各マトリク
スの主斜め線を２つの斜め線に分割する必要があるから
である。
マトリクス検索ネットワークの相互接続の詳細を示す図
である。各マトリクス１２ａー１２ｐ、１３ａ−１３
ｈ、１４ａ−１４ｄ、１５ａ−１５ｂ及び１６は正方マ
トリクスではなく、それぞれ１×２、２×３、４×５、
８×９、及び１６×１７のマトリクスである。このよう
に正方マトリクスを用いない理由は、マトリクスの主斜
め線に沿った特別のセルを持たないように、各マトリク
スの主斜め線を２つの斜め線に分割する必要があるから
である。
【００１６】図４は図３におけるマトリクス１５ａをよ
り詳細に説明するための図である。マトリクス１５ａは
８列９行のセルを有する。それらのセルの１つが図４の
１８に示される。さらに、このセル１８の詳細は図５に
示される。マトリクス１５ａは水平バス入力Ａ１−Ａ８
と垂直バス入力Ｂ１−Ｂ８を有する。斜めバスＣ１−Ｃ
１６は出力バスであり、この斜め出力バスからの出力信
号はマトリクス１６に入力される。
り詳細に説明するための図である。マトリクス１５ａは
８列９行のセルを有する。それらのセルの１つが図４の
１８に示される。さらに、このセル１８の詳細は図５に
示される。マトリクス１５ａは水平バス入力Ａ１−Ａ８
と垂直バス入力Ｂ１−Ｂ８を有する。斜めバスＣ１−Ｃ
１６は出力バスであり、この斜め出力バスからの出力信
号はマトリクス１６に入力される。
【００１７】１６の斜め出力信号を発生するために、マ
トリクスの主斜め出力バスＣ８はセルの他の行を加算す
ることによって斜め出力バスＣ８とＣ９に分割され、８
×９のマトリクスの行と列によってによって完全に検索
され、１６の入力が１６の斜め出力バスＣ１ーＣ１６に
出力される。
トリクスの主斜め出力バスＣ８はセルの他の行を加算す
ることによって斜め出力バスＣ８とＣ９に分割され、８
×９のマトリクスの行と列によってによって完全に検索
され、１６の入力が１６の斜め出力バスＣ１ーＣ１６に
出力される。
【００１８】他の構成によれば、マトリクス１５ａの主
斜め出力バスＣ８に沿った図示されない「特別の」セル
を設け、そのセルによって出力を得るように構成するこ
ともできる。（Ｎ／２）×（［Ｎ／２］＋１）のマトリ
クス構成では（Ｎ／２）×（Ｎ／２）のマトリクス構成
よりもセルの数が少し多くなるだけで、全てのセルはま
ったく同じである。
斜め出力バスＣ８に沿った図示されない「特別の」セル
を設け、そのセルによって出力を得るように構成するこ
ともできる。（Ｎ／２）×（［Ｎ／２］＋１）のマトリ
クス構成では（Ｎ／２）×（Ｎ／２）のマトリクス構成
よりもセルの数が少し多くなるだけで、全てのセルはま
ったく同じである。
【００１９】検索セルの回路と方向について図４、図５
を用いて以下に説明する。図４において、マトリクス１
５ａの右上方の三角形中のセル（１８のような）はマト
リクス１５ａの左下方の三角形中のセルと、斜め出力バ
スＣ８とＣ９間の線に関し鏡面映像の関係にある。図４
中の全てのセルは図５に示されるセル１８と同じ構成で
ある。セル１８は入力バスＡ２、Ｂ３から入力される。
を用いて以下に説明する。図４において、マトリクス１
５ａの右上方の三角形中のセル（１８のような）はマト
リクス１５ａの左下方の三角形中のセルと、斜め出力バ
スＣ８とＣ９間の線に関し鏡面映像の関係にある。図４
中の全てのセルは図５に示されるセル１８と同じ構成で
ある。セル１８は入力バスＡ２、Ｂ３から入力される。
【００２０】図５において、セル１８は比較器１９、セ
レクタ２０及びスイッチ２１を含む。比較器１９はＡ
２、Ｂ３上の入力のアナログ信号又はディジタル符号化
されたディジタル信号の振幅を比較する。セレクタ２０
は比較された信号を選択し、スイッチ２１は選択された
信号を斜め出力バスＣ４に出力する。
レクタ２０及びスイッチ２１を含む。比較器１９はＡ
２、Ｂ３上の入力のアナログ信号又はディジタル符号化
されたディジタル信号の振幅を比較する。セレクタ２０
は比較された信号を選択し、スイッチ２１は選択された
信号を斜め出力バスＣ４に出力する。
【００２１】多くのセルは潜在的に斜め出力バスＣ１−
Ｃ１６に接続できるが、これらは衝突する可能性があ
る。この衝突を防止するために、セル１８は２つの禁止
入力２２、２３と２つの禁止出力２４、２５を含む。２
つの禁止入力２２、２３と２つの禁止出力２４、２５は
隣のセルと水平及び垂直に接続され、制御の流れは斜め
出力バスＣ８、Ｃ９（主斜め出力バス）の方向になる。
Ｃ１６に接続できるが、これらは衝突する可能性があ
る。この衝突を防止するために、セル１８は２つの禁止
入力２２、２３と２つの禁止出力２４、２５を含む。２
つの禁止入力２２、２３と２つの禁止出力２４、２５は
隣のセルと水平及び垂直に接続され、制御の流れは斜め
出力バスＣ８、Ｃ９（主斜め出力バス）の方向になる。
【００２２】マトリクスの周辺のセルは、経済的な理由
から同一の構造をしていても、セル１８と同じような通
常のセルではない。周辺のセルはマトリクスの外部から
禁止入力を受信しない。同様に、斜め線Ｃ８、Ｃ９に沿
ったセル２６、２６’はそれぞれ、斜め出力バスＣ８か
らＣ９へ、又はＣ９からＣ８へ禁止制御を交差させない
ために、禁止出力を発生しない。セル１８は独立にバス
Ａ２、Ｂ３で受信した入力を比較し、セレクタ２０によ
って選択を行う。この選択は、禁止入力２２、２３が双
方ともオフの場合のみ次の真理値表に従って、ＮＯＲゲ
ート２７が斜め出力バスＣ４にスイッチすることによっ
て行われる。
から同一の構造をしていても、セル１８と同じような通
常のセルではない。周辺のセルはマトリクスの外部から
禁止入力を受信しない。同様に、斜め線Ｃ８、Ｃ９に沿
ったセル２６、２６’はそれぞれ、斜め出力バスＣ８か
らＣ９へ、又はＣ９からＣ８へ禁止制御を交差させない
ために、禁止出力を発生しない。セル１８は独立にバス
Ａ２、Ｂ３で受信した入力を比較し、セレクタ２０によ
って選択を行う。この選択は、禁止入力２２、２３が双
方ともオフの場合のみ次の真理値表に従って、ＮＯＲゲ
ート２７が斜め出力バスＣ４にスイッチすることによっ
て行われる。
【００２３】 禁止入力２１ 禁止入力２３ ＮＯＲゲート２７ ０ ０ １ ０ １ ０ １ ０ ０ １ １ ０
【００２４】これはもちろん、斜め出力バスＣ４が同時
に複数の信号を受信しないということを保証するもので
ある。同時に、禁止入力２２、２３とまったく独立に、
セル１８は禁止出力２４、２５の１つをオンに変化させ
る。特に、もし、バスＡ２からの信号が選択されると
（図５において、例えば、Ａ≧Ｂの場合）、垂直出力２
５はオフに変化し水平出力２４はオンになる。もしバス
Ｂ３が選択されると水平出力２４はオフになり垂直出力
２５はオンに変化する（図５において、例えば、Ａ＜Ｂ
の場合）。
に複数の信号を受信しないということを保証するもので
ある。同時に、禁止入力２２、２３とまったく独立に、
セル１８は禁止出力２４、２５の１つをオンに変化させ
る。特に、もし、バスＡ２からの信号が選択されると
（図５において、例えば、Ａ≧Ｂの場合）、垂直出力２
５はオフに変化し水平出力２４はオンになる。もしバス
Ｂ３が選択されると水平出力２４はオフになり垂直出力
２５はオンに変化する（図５において、例えば、Ａ＜Ｂ
の場合）。
【００２５】このように、セル１８はバスを選択し、隣
のセルを同時に禁止する。そのような選択と禁止は遅延
によってリップルが生じないという重要な結果を生じ
る。すなわち、選択と禁止が同時に発生し、選択と禁止
との間に遅延が生じないために、ネットワークは非常に
高速となる。ネットワーク１０に対してＮ＝３２の場
合、ｌｏｇ2Ｎセルのオーダの遅延である。セルの遅延
は比較器１９とセレクタ２０の遅延のみである。
のセルを同時に禁止する。そのような選択と禁止は遅延
によってリップルが生じないという重要な結果を生じ
る。すなわち、選択と禁止が同時に発生し、選択と禁止
との間に遅延が生じないために、ネットワークは非常に
高速となる。ネットワーク１０に対してＮ＝３２の場
合、ｌｏｇ2Ｎセルのオーダの遅延である。セルの遅延
は比較器１９とセレクタ２０の遅延のみである。
【００２６】検索の向きは増加、減少の方向に任意に選
択される。しかしながら、マトリクス１５ａの上方の三
角形中では全てのセルは同じ方向に、また、下方の三角
形中では反対方向に動作しなければならない。
択される。しかしながら、マトリクス１５ａの上方の三
角形中では全てのセルは同じ方向に、また、下方の三角
形中では反対方向に動作しなければならない。
【００２７】セル１８に対するそれぞれの入力Ａ２、Ｂ
３で入力信号が等しい場合は、いずれかの信号（どちら
であるかは問題でない）が選択され、対応する禁止出力
を発生する。しかしながら、一般に言えば、選択の基準
は単に大きさを比較することとは異なる。例えば、ディ
ジタルパケット信号に対してはある優先的符号化部分が
比較され、信号Ａ又は信号Ｂのいずれかの選択に従って
決定がなされる。
３で入力信号が等しい場合は、いずれかの信号（どちら
であるかは問題でない）が選択され、対応する禁止出力
を発生する。しかしながら、一般に言えば、選択の基準
は単に大きさを比較することとは異なる。例えば、ディ
ジタルパケット信号に対してはある優先的符号化部分が
比較され、信号Ａ又は信号Ｂのいずれかの選択に従って
決定がなされる。
【００２８】本発明におけるネットワーク１０はさらに
ステージ間に、少なくとも検索ネットワークの最後のス
テージにおけるより長い信号パスに対して、図示されな
いドライバ又はバッファを含むことが好ましい。入力ス
テージにおいては、ファンアウトが２、３、５、９のよ
うな場合、バスは非常に短かく、これらのバスは簡単な
スイッチによって接続される。
ステージ間に、少なくとも検索ネットワークの最後のス
テージにおけるより長い信号パスに対して、図示されな
いドライバ又はバッファを含むことが好ましい。入力ス
テージにおいては、ファンアウトが２、３、５、９のよ
うな場合、バスは非常に短かく、これらのバスは簡単な
スイッチによって接続される。
【００２９】本発明のネットワーク１０では正しく禁止
決定がされる前に全てのデータが比較のために用いられ
る。これはデータがアナログ形式又は平行ディジタル形
式で伝送されるところでは当たり前のことである。も
し、並列変換が各セル又はステージ間で行われるならば
バスＡ、Ｂ、Ｃ及び／又はステージ間の直列ディジタル
伝送が可能である。
決定がされる前に全てのデータが比較のために用いられ
る。これはデータがアナログ形式又は平行ディジタル形
式で伝送されるところでは当たり前のことである。も
し、並列変換が各セル又はステージ間で行われるならば
バスＡ、Ｂ、Ｃ及び／又はステージ間の直列ディジタル
伝送が可能である。
【００３０】直列１ビット比較回路と結合されたバス
Ａ、Ｂ、Ｃ上の直列ディジタル伝送は遅延は大きくなる
が、必要なハードウエア量を減少させ、大きな検索マト
リクスを単一の回路上に形成することを潜在的に可能に
する。なお、この遅延は比較されるワード長に依存す
る。
Ａ、Ｂ、Ｃ上の直列ディジタル伝送は遅延は大きくなる
が、必要なハードウエア量を減少させ、大きな検索マト
リクスを単一の回路上に形成することを潜在的に可能に
する。なお、この遅延は比較されるワード長に依存す
る。
【００３１】検索ネットワーク１０のパターンは基本的
には２次元であり、概念的には水平バス、垂直バス及び
１方向の斜めバスのとだけから構成される。クロックと
電源バスはこれらのバスに沿って設けられる。線形のレ
イアウトは、究極的にはコストで制限されるが、拡張は
トポロジ的には難しくはないということを意味する。パ
ターンの面は単にセル及び３つのバスＡ、Ｂ、Ｃで覆わ
れ、これらのバスはお互いに切断されかつ繋ぎ合わされ
る。
には２次元であり、概念的には水平バス、垂直バス及び
１方向の斜めバスのとだけから構成される。クロックと
電源バスはこれらのバスに沿って設けられる。線形のレ
イアウトは、究極的にはコストで制限されるが、拡張は
トポロジ的には難しくはないということを意味する。パ
ターンの面は単にセル及び３つのバスＡ、Ｂ、Ｃで覆わ
れ、これらのバスはお互いに切断されかつ繋ぎ合わされ
る。
【００３２】
【発明の効果】以上説明したように、本発明における検
索マトリクスは（ｌｏｇ2Ｎ）のステージから構成さ
れ、検索に際して第１のステージ、第２のステージ、第
３のステージ、第４のステージのようなステージを経由
して検索が行われる。したがって、従来の検索パスと比
較してステージの段数が少なくなるので遅延量が小さく
なり演算速度が速くなる。
索マトリクスは（ｌｏｇ2Ｎ）のステージから構成さ
れ、検索に際して第１のステージ、第２のステージ、第
３のステージ、第４のステージのようなステージを経由
して検索が行われる。したがって、従来の検索パスと比
較してステージの段数が少なくなるので遅延量が小さく
なり演算速度が速くなる。
【００３３】また、本発明のマトリクス検索において
は、ネットワークの分割部は、１つの入力又は１群の入
力と対応する出力間のいずれかの端に沿って、ネットワ
ークの残りの動作に影響を与えることなく除去すること
ができる。完全に配置されたネットワークのサイズが劇
的に減少するために、本発明を試験と誤り診断の目的の
ために使用すれば非常に有効である。
は、ネットワークの分割部は、１つの入力又は１群の入
力と対応する出力間のいずれかの端に沿って、ネットワ
ークの残りの動作に影響を与えることなく除去すること
ができる。完全に配置されたネットワークのサイズが劇
的に減少するために、本発明を試験と誤り診断の目的の
ために使用すれば非常に有効である。
【図１】本発明の一実施例の３２ポートマトリクス検索
ネットワークを示す図である。
ネットワークを示す図である。
【図２】従来の３２ポートのバッチャ検索ネットワーク
の構成を示す図である。
の構成を示す図である。
【図３】図１に示す本発明の一実施例のマトリクス検索
ネットワークの相互接続の詳細を示す図である。
ネットワークの相互接続の詳細を示す図である。
【図４】図３に示す８×９のマトリクスをより詳細に説
明するための図である。
明するための図である。
【図５】セルの詳細ブロックを示す図である。
【符号の説明】 １０ 検索ネットワーク １１ａー１１ｐ 入力 １１ａ’ー１１ｐ’入力 １２ａー１２ｐ １×１マトリクス １３ａー１３ｈ ２×２マトリクス １４ａー１４ｄ ４×４マトリクス １５ａー１５ｂ ８×８マトリクス １６ １６×１６マトリクス １７ａー１７ｐ 最終マトリクス１６の診断出力 １７ａ’ー１７ｐ’最終マトリクス１６の診断出力 １８ セル １９ 比較器 ２０ セレクタ ２１ スイッチ ２２ 垂直入力 ２３ 水平入力 ２４ 水平出力 ２５ 垂直出力 ２７ ＮＯＲゲート Ｃ１ーＣ１６ 斜め出力バス Ａ１ーＡ８ 水平入力バス Ｂ１ーＢ８ 垂直入力バス
Claims (7)
- 【請求項１】 Ｎ入力を検索してＮ出力を出力するマト
リクス検索ネットワークにおいて、 検索マトリクスは（ｌｏｇ2Ｎ）のステージから構成さ
れ、 各ステージは（Ｎ／２Ｍ）×（Ｎ／２Ｍ）マトリクスの
検索セルをＭ個を含むことを特徴とするマトリクス検索
ネットワーク。ここでＭは第１のステージのマトリクス
ではＮ／２、第２のステージのマトリクスではＮ／４、
第３のステージのマトリクスではＮ／８、第ｍのステー
ジのマトリクスではＮ／２mの値を取る数である。 - 【請求項２】 Ｎ入力を検索してＮ出力を出力するマト
リクス検索ネットワークにおいて、 検索マトリクスは（ｌｏｇ2Ｎ）のステージから構成さ
れ、 各ステージは（Ｎ／２Ｍ）×（［Ｎ／２Ｍ］＋１）マト
リクスの検索セルＭ個を含むことを特徴とするマトリク
ス検索ネットワーク。ここでＭは第１のステージのマト
リクスではＮ／２、第２のステージのマトリクスではＮ
／４、第３のステージのマトリクスではＮ／８、第ｍの
ステージのマトリクスではＮ／２mの値を取る数であ
る。 - 【請求項３】 前記各検索セルが第１のバス及び第２の
バスから入力信号を受信し、前記第１のバスと第２のバ
スからの入力の１つを選択して出力する比較器を含むこ
とを特徴とする請求項１記載のマトリクス検索ネットワ
ーク。 - 【請求項４】 前記検索セルはさらに隣のセルから２つ
の禁止入力信号を受信し、２つの禁止出力信号を隣のセ
ルに供給することを特徴とする請求項１記載のマトリク
ス検索ネットワーク。 - 【請求項５】 第１の入力バスと第２の入力バスに入力
した信号を比較する比較器と、前記比較器に対応して前
記２つの信号の中の１つを選択するセレクタと、前記２
つの信号の１つを出力バスに供給するためのスイッチ手
段とを含むことを特徴とする検索セル。 - 【請求項６】 前記検索セルに供給される禁止入力信号
に応答して、前記スイッチ手段を禁止するための手段を
さらに含むことを特徴とする請求項５記載の検索セル。 - 【請求項７】 ２つの禁止出力信号を供給するための手
段をさらに含むことを特徴とする請求項６記載の検索セ
ル。
Applications Claiming Priority (3)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US07/552,320 US5216420A (en) | 1990-07-12 | 1990-07-12 | Matrix sorting network for sorting N inputs onto N outputs |
| US552,320 | 1990-07-12 | ||
| CA552,320 | 1990-07-12 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH0630455A true JPH0630455A (ja) | 1994-02-04 |
| JP3194597B2 JP3194597B2 (ja) | 2001-07-30 |
Family
ID=24204848
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP19874391A Expired - Fee Related JP3194597B2 (ja) | 1990-07-12 | 1991-07-12 | マトリクス検索ネットワーク |
Country Status (3)
| Country | Link |
|---|---|
| US (1) | US5216420A (ja) |
| JP (1) | JP3194597B2 (ja) |
| CA (1) | CA2037732C (ja) |
Families Citing this family (11)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5319788A (en) * | 1991-03-29 | 1994-06-07 | The Regents Of University Of Calif. | Modified batcher network for sorting N unsorted input signals in log2 N sequential passes |
| JP3202074B2 (ja) * | 1992-10-21 | 2001-08-27 | 富士通株式会社 | 並列ソート方式 |
| US6088353A (en) * | 1997-07-08 | 2000-07-11 | Lucent Technologies, Inc. | Sorting networks having reduced-area layouts |
| US6091723A (en) * | 1997-10-22 | 2000-07-18 | Lucent Technologies, Inc. | Sorting networks having improved layouts |
| US6185220B1 (en) * | 1998-06-15 | 2001-02-06 | Lucent Technologies, Inc. | Grid layouts of switching and sorting networks |
| US6525650B1 (en) * | 1999-06-11 | 2003-02-25 | Trw Inc. | Electronic switching matrix |
| US6757284B1 (en) * | 2000-03-07 | 2004-06-29 | Cisco Technology, Inc. | Method and apparatus for pipeline sorting of ordered streams of data items |
| US20080104374A1 (en) * | 2006-10-31 | 2008-05-01 | Motorola, Inc. | Hardware sorter |
| TWI511038B (zh) * | 2013-06-19 | 2015-12-01 | Univ Nat Chiao Tung | 可重組之排序裝置與排序方法 |
| US12450029B1 (en) | 2023-10-27 | 2025-10-21 | Robert Bernard Kent | Top down merge sort method and apparatus |
| US12306776B1 (en) | 2024-04-22 | 2025-05-20 | Robert Bernard Kent | Single-stage merge sorting method and apparatus |
Family Cites Families (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US3593295A (en) * | 1968-05-10 | 1971-07-13 | Bell Telephone Labor Inc | Rearrangeable switching network |
| US4654842A (en) * | 1984-08-02 | 1987-03-31 | Coraluppi Giorgio L | Rearrangeable full availability multistage switching network with redundant conductors |
| US4922246A (en) * | 1986-11-25 | 1990-05-01 | Massachusetts Institute Of Technology | Message merging device |
| EP0309670B1 (de) * | 1987-09-29 | 1994-04-13 | Siemens Aktiengesellschaft | Konzentrator für schnelle Datenvermittlungsnetze |
| US4833468A (en) * | 1987-10-14 | 1989-05-23 | Unisys Corporation | Layered network |
| US4899334A (en) * | 1987-10-19 | 1990-02-06 | Oki Electric Industry Co., Ltd. | Self-routing multistage switching network for fast packet switching system |
-
1990
- 1990-07-12 US US07/552,320 patent/US5216420A/en not_active Expired - Lifetime
-
1991
- 1991-03-07 CA CA002037732A patent/CA2037732C/en not_active Expired - Fee Related
- 1991-07-12 JP JP19874391A patent/JP3194597B2/ja not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| JP3194597B2 (ja) | 2001-07-30 |
| US5216420A (en) | 1993-06-01 |
| CA2037732A1 (en) | 1992-01-13 |
| CA2037732C (en) | 1998-01-06 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| KR100211123B1 (ko) | 고속 패킷 스위칭을 위한 다단 상호 연결 망 | |
| Patel | Processor-memory interconnections for multiprocessors | |
| EP0397372B1 (en) | Network topology for reduced blocking and photonic system implementation thereof | |
| US4516238A (en) | Self-routing switching network | |
| JP2523207B2 (ja) | 多段ネットワ―ク制御方法 | |
| US8270400B2 (en) | Fully connected generalized multi-stage networks | |
| US8170040B2 (en) | Fully connected generalized butterfly fat tree networks | |
| JP3194597B2 (ja) | マトリクス検索ネットワーク | |
| US5023864A (en) | Crossover network utilizing two-dimensional arrays of nodes | |
| EP0397370B1 (en) | Network control arrangement for processing a plurality of connection requests | |
| JP2609742B2 (ja) | 連続的に相互接続された複数の段からなるネットワークとその制御方法 | |
| US4910730A (en) | Batcher-banyan network | |
| US7065076B1 (en) | Modular scalable switching networks | |
| Hanawa et al. | Multistage interconnection networks with multiple outlets | |
| US6091723A (en) | Sorting networks having improved layouts | |
| US5220664A (en) | Merging network with three or more simultaneous inputs | |
| Chakrabarty et al. | Matrix-based nonblocking routing algorithm for Beneš networks | |
| EP0186595B1 (en) | Routing technique | |
| WO1984003977A1 (en) | A self routing steering network | |
| EP0569905B1 (en) | Method and system for selecting an optimal rearrangement sequence for a cross-connect communication matrix | |
| Li et al. | B-tree: a high-performance fault-tolerant ATM switch | |
| Hamandi | Performance of augmented baseline interconnection networks in buffered packet-switched environments | |
| Zhou et al. | A kind of multistage interconnection networks with multiple paths | |
| Zhou et al. | Adaptive message routing in a class of fault-tolerant multistage interconnection networks | |
| Harissis et al. | Analysis and design of circuit switching interconnection networks using 4× 4 nodes |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| LAPS | Cancellation because of no payment of annual fees |