(57)【要約】  それぞれの相互接続リソース制約内で無制限の形で第１の複数の導体を導体の他の複数の組に接続するために使用されるスイッチ（１５１〜１６０）と中間（ステージの）導体を有するスケーラブル・ノンブロッキング・スイッチング・ネットワーク（ＳＮ）。ＳＮ（２００）は、ネットワーク、ルータ、プログラム可能論理回路で使用される大きいスイッチ・ネットワークをもたらすために、並列にまたは階層的に、広範囲の応用例に適用することができる。ＳＮは、導体の第１組（１０１〜１０４）をＳＮを介して所与の論理回路階層内の導体の複数の組に接続するのに使用され、これによって、複数の組のそれぞれに含まれる導体が同等または交換可能になり、これによって、構成によって、導体の第１組が、回路階層の次のレベルで使用される時に同等になる。ＳＮは、導体の多きいサイズの組にスケーラブルであり、大きいサイズの回路の中のプログラム可能相互接続を可能にするために階層的に使用することができる。
2007531461.tif 000002
【特許請求の範囲】
【請求項１】
Ｍ個の第１の複数の導体と、
ｋ組のＮ個の第２の複数の導体（ｋ×Ｎ個の導体）と、
Ｍが少なくともｋ＋Ｎであり、ｋが少なくとも２であり、Ｎが少なくとも２である、スイッチング・ネットワーク（ＳＮ）と
を含む集積回路であって、前記ＳＮが、
複数のスイッチと、
ｉ＝［１−Ｎ０］についてＮ０組のＩ０i個の導体を含む１０個の第３の複数の導体であって、Ｎ０が少なくとも２であり、Ｎが少なくともＮ０であり、Ｉ０が少なくともＭと等しくＭが（ｋ×Ｎ）より小さい時にＭと（ｋ×Ｎ）の間である、１０個の第３の複数の導体と
を含み、
前記Ｍ個の第１の複数の導体のうちの任意の２つの導体が、別の導体のトラバーサルを必要とせずに前記複数のスイッチを介してｐ、ｑ＝［１−Ｎ０］についてそれぞれ少なくとも２つの異なるＩ０p個の導体とＩ０q個の導体からそれぞれ選択される少なくとも２つの異なる導体に選択的に結合され、
前記少なくとも２つの異なる導体のうちの第１導体が、前記ＳＮを介して多くとも（ｋ×（Ｍ／Ｎ０））個の導体の第１組に選択的に結合され、多くとも（ｋ×（Ｍ／Ｎ０））個の導体の前記第１組が、前記ｋ組のＮ個の導体のそれぞれからの多くとも（Ｍ／Ｎ０）個の導体を有し、
前記少なくとも２つの異なる導体のうちの第２導体が、前記ＳＮを介して多くとも（ｋ×（Ｍ／Ｎ０））個の導体の第２組に選択的に結合され、多くとも（ｋ×（Ｍ／Ｎ０））個の導体の前記第２組が、前記ｋ組のＮ個の導体のそれぞれからの多くとも（ｋ×（Ｍ／Ｎ０））個の導体の前記第１組と異なる多くとも（Ｍ／Ｎ０）個の導体を有する
集積回路。
【請求項２】
前記Ｉ０i個の導体の各導体が、別の導体のトラバーサルを必要とせずに前記ＳＮを介してｋ個の導体に選択的に結合される請求項１に記載の集積回路。
【請求項３】
前記Ｉ０i個が、多くとも（ｋ×Ｎ／Ｎ０）個と（Ｍ／Ｎ０）個のうちの大きい方であり、前記複数のスイッチが、少なくとも［（Ｍ−Ｎ＋１）×Ｎ＋Ｍ×ｋ］個のスイッチであり、多くともＭ×（ｋ＋Ｎ）個のスイッチである請求項２に記載の集積回路。
【請求項４】
ｋ個のプログラム可能論理セルをさらに含み、前記ｋ個のプログラム可能論理セルのそれぞれが、Ｎ個の入力導体を有し、前記ｋ個の導体のそれぞれが、前記ｋ個のプログラム可能論理セルの前記Ｎ個の入力導体のうちの１つの導体に対応する請求項２に記載の集積回路。
【請求項５】
Ｍが、Ｒ×（ｋ×Ｎ）と等しく、Ｒが、少なくとも０．５であり、多くとも１．０である請求項１に記載の集積回路。
【請求項６】
前記Ｉ０i個の導体に選択的に結合される第４の複数のＩ１i個の導体であって、前記Ｉ１i個の導体が、ｊ＝［１−Ｎ１］についてＮ１個のグループのＩ１ij個の導体を含み、Ｎ１が少なくとも２である、第４の複数のＩ１i個の導体
をさらに含み、
前記Ｉ０i個の導体のうちの任意の２つの導体が、別の導体のトラバーサルを必要とせずに前記複数のスイッチを介して前記Ｉ１i個の導体のうちの２つの異なる導体に選択的に結合され、ｒ、ｓ＝［１−Ｎ１］について、前記２つの異なる導体のうちの第３導体が、Ｉ１ir個の導体からであり、前記２つの異なる導体のうちの第４導体が、Ｉ１is個の導体からであり、数ｒが数ｓと異なり、
前記第３導体が、前記ＳＮを介して前記ｋ組のＮ個の導体からの多くとも（ｋ×（Ｍ／（Ｎ０×Ｎ１）））個の導体の第３組に選択的に結合され、多くとも（ｋ×（Ｍ／（Ｎ０×Ｎ１）））個の導体の前記第３組が、前記ｋ組のＮ個の導体のそれぞれからの多くとも（Ｍ／（Ｎ０×Ｎ１））個の導体を有し、
前記第４導体が、前記ＳＮを介して前記ｋ組のＮ個の導体からの多くとも（ｋ×（Ｍ／（Ｎ０×Ｎ１）））個の導体の第４組に選択的に結合され、多くとも（ｋ×（Ｍ／（Ｎ０×Ｎ１）））個の導体の前記第４組が、前記ｋ組のＮ個の導体のそれぞれからの、多くとも（ｋ×（Ｍ／（Ｎ０×Ｎ１）））個の導体の前記第３組と異なる多くとも（Ｍ／（Ｎ０×Ｎ１））個の導体を有する
請求項１に記載の集積回路。
【請求項７】
前記Ｉ１ij個の導体の各導体が、別の導体のトラバーサルを必要とせずに前記ＳＮを介してｋ個の導体を選択的に結合する請求項６に記載の集積回路。
【請求項８】
ｋ個のプログラム可能論理セルをさらに含み、前記ｋ個のプログラム可能論理セルのそれぞれが、Ｎ個の入力導体を有し、前記ｋ個の導体のそれぞれが、前記ｋ個のプログラム可能論理セルの前記Ｎ個の入力導体のうちの１つの導体に対応する請求項７に記載の集積回路。
【請求項９】
前記Ｉ１ij個が、多くとも（ｋ×Ｎ／（Ｎ０×Ｎ１））個と（Ｍ／（Ｎ０×Ｎ１））個のうちの大きい方であり、前記複数のスイッチが、多くとも［Ｍ×（Ｎ０＋Ｎ１＋ｋ）］のスイッチからなる請求項７に記載の集積回路。
【請求項１０】
前記複数のスイッチのそれぞれが、少なくともプログラム制御パスゲートからなる請求項１に記載の集積回路。
【請求項１１】
前記複数のスイッチのそれぞれが、少なくともプログラム制御ドライバ／レシーバからなる請求項１に記載の集積回路。
【請求項１２】
前記複数のスイッチのそれぞれが、プログラム制御パスゲートとプログラム制御ドライバ／レシーバのうちの少なくとも１つからなる請求項１に記載の集積回路。
【請求項１３】
前記複数のスイッチのうちの１つが、プログラム制御されるオン状態とオフ状態を有する請求項１に記載の集積回路。
【請求項１４】
前記集積回路が、メモリ・デバイスを組み込むプロセス・テクノロジを使用して実装される請求項１に記載の集積回路。
【請求項１５】
前記集積回路が、不揮発性メモリ・デバイスを組み込むプロセス・テクノロジを使用して実装される請求項１に記載の集積回路。
【請求項１６】
前記集積回路が、ヒューズ・デバイスを組み込むプロセス・テクノロジを使用して実装される請求項１に記載の集積回路。
【請求項１７】
前記集積回路が、アンチヒューズ・デバイスを組み込むプロセス・テクノロジを使用して実装される請求項１に記載の集積回路。
【請求項１８】
前記集積回路が、強誘電デバイスを組み込むプロセス・テクノロジを使用して実装される請求項１に記載の集積回路。
【請求項１９】
Ｍが、Ｒ×（ｋ×Ｎ）によって決定され、Ｒが、少なくとも０．５であり、多くとも１．０である請求項１に記載の集積回路。
【請求項２０】
Ｍ個の第１の複数の導体と、ｋ組のＮ個の第２の複数の導体（ｋ×Ｎ個の導体）と、Ｍが少なくともｋ＋Ｎであり、ｋが少なくとも２であり、Ｎが少なくとも２であるスイッチング・ネットワーク（ＳＮ）とを含む集積回路内の接続性の方法であって、前記ＳＮが、複数のスイッチと、ｉ＝［１−Ｎ０］についてＮ０組のＩ０i個の導体を含む１０個の第３の複数の導体であって、Ｎ０が少なくとも２であり、Ｎが少なくともＮ０であり、Ｉ０が少なくともＭと等しくＭが（ｋ×Ｎ）より小さい時にＭと（ｋ×Ｎ）の間である、１０個の第３の複数の導体とを含み、前記方法が、
別の導体のトラバーサルを必要とせずに前記複数のスイッチを介してｐ、ｑ＝［１−Ｎ０］についてそれぞれ少なくとも２つの異なるＩ０p個の導体とＩ０q個の導体からそれぞれ選択される少なくとも２つの異なる導体に前記Ｍ個の第１の複数の導体のうちの任意の２つの導体を選択的に結合することと、
前記ＳＮを介して多くとも（ｋ×（Ｍ／Ｎ０））個の導体の第１組に前記少なくとも２つの異なる導体のうちの第１導体を選択的に結合することであって、多くとも（ｋ×（Ｍ／Ｎ０））個の導体の前記第１組が、前記ｋ組のＮ個の導体のそれぞれからの多くとも（Ｍ／Ｎ０）個の導体を有する、選択的に結合することと、
前記ＳＮを介して多くとも（ｋ×（Ｍ／Ｎ０））個の導体の第２組に前記少なくとも２つの異なる導体のうちの第２導体を選択的に結合することであって、多くとも（ｋ×（Ｍ／Ｎ０））個の導体の前記第２組が、前記ｋ組のＮ個の導体のそれぞれからの、多くとも（ｋ×（Ｍ／Ｎ０））個の導体の前記第１組と異なる多くとも（Ｍ／Ｎ０）個の導体を有する、選択的に結合することと
を含む方法。
【請求項２１】
前記Ｉ０i個の導体の各導体を、別の導体のトラバーサルを必要とせずに前記ＳＮを介してｋ個の導体に選択的に結合することをさらに含む請求項２０に記載の方法。
【請求項２２】
導体の前記Ｉ０i個が、多くとも（ｋ×Ｎ／Ｎ０）個と（Ｍ／Ｎ０）個のうちの大きい方であり、前記複数のスイッチが、少なくとも［（Ｍ−Ｎ＋１）×Ｎ＋Ｍ×ｋ］個のスイッチであり、多くともＭ×（ｋ＋Ｎ）個のスイッチである請求項２１に記載の方法。
【請求項２３】
ｋ個のプログラム可能論理セルをさらに含み、前記ｋ個のプログラム可能論理セルのそれぞれが、Ｎ個の入力導体を有し、前記ｋ個の導体のそれぞれが、前記ｋ個のプログラム可能論理セルの前記Ｎ個の入力導体のうちの１つの導体に対応する請求項２１に記載の方法。
【請求項２４】
Ｍが、Ｒ×（ｋ×Ｎ）と等しく、Ｒが、少なくとも０．５であり、多くとも１．０である請求項２０に記載の方法。
【請求項２５】
Ｉ１i個の第４の複数の導体を前記Ｉ０i個の導体に選択的に結合することであって、前記Ｉ１i個の導体が、ｊ＝［１−Ｎ１］についてＮ１個のグループのＩ１ij個の導体を含み、Ｎ１が少なくとも２つである、選択的に結合することと、
前記Ｉ０i個の導体のうちの任意の２つの導体を、別の導体のトラバーサルを必要とせずに前記複数のスイッチを介して前記Ｉ１i個の導体のうちの２つの異なる導体に選択的に結合することであって、ｒ、ｓ＝［１−Ｎ１］について、前記２つの異なる導体のうちの第３導体がＩ１ir個の導体からであり、前記２つの異なる導体のうちの第４導体がＩ１is個の導体からであり、ｒがｓと異なる、選択的に結合することと、
前記第３導体を、前記ＳＮを介して前記ｋ組のＮ個の導体からの多くとも（ｋ×（Ｍ／（Ｎ０×Ｎ１）））個の導体の第３組に選択的に結合することであって、多くとも（ｋ×（Ｍ／（Ｎ０×Ｎ１）））個の導体の前記第３組が、前記ｋ組のＮ個の導体のそれぞれからの多くとも（Ｍ／（Ｎ０×Ｎ１））個の導体を有する、選択的に結合することと、
前記第４導体を、前記ＳＮを介して前記ｋ組のＮ個の導体からの多くとも（ｋ×（Ｍ／（Ｎ０×Ｎ１）））個の導体の第４組に選択的に結合することであって、多くとも（ｋ×（Ｍ／（Ｎ０×Ｎ１）））個の導体の前記第４組が、前記ｋ組のＮ個の導体のそれぞれからの、多くとも（ｋ×（Ｍ／（Ｎ０×Ｎ１）））個の導体の前記第３組と異なる多くとも（Ｍ／（Ｎ０×Ｎ１））個の導体を有する、選択的に結合することと
をさらに含む請求項２０に記載の方法。
【請求項２６】
前記Ｉ１ij個の導体の各導体を、別の導体のトラバーサルを必要とせずにｋ個の導体に選択的に結合することをさらに含む請求項２５に記載の方法。
【請求項２７】
ｋ個のプログラム可能論理セルをさらに含み、前記ｋ個のプログラム可能論理セルのそれぞれが、Ｎ個の入力導体を有し、前記ｋ個の導体のそれぞれが、前記ｋ個のプログラム可能論理セルの前記Ｎ個の入力導体のうちの１つの導体に対応する請求項２６に記載の方法。
【請求項２８】
前記Ｉ１ij個が、多くとも（ｋ×Ｎ／（Ｎ０×Ｎ１））個と（Ｍ／（Ｎ０×Ｎ１））個のうちの大きい方であり、前記複数のスイッチが、多くとも［Ｍ×（Ｎ０＋Ｎ１＋ｋ）］のスイッチを含む請求項２６に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、スイッチング・ネットワークに関し、具体的には、プログラム可能論理回路と共に使用されるスイッチング・ネットワークに関する。
【背景技術】
【０００２】
フィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）とも称するプログラム可能論理回路は、論理機能を実行するためにユーザがプログラムできる既製品の集積論理回路である。回路設計者が所望の論理機能を定義し、それに対応して信号を処理するように回路がプログラムされる。論理密度要件と生産量に応じて、プログラム可能論理回路は、コストと製品化までの時間に関して優れた代替物である。通常のプログラム可能論理回路は論理セルからなり、論理セルのそれぞれは、入力変数に関して論理機能を実行するようにプログラムされる。さらに、相互接続リソースが、プログラム可能論理回路全体に設けられ、これをプログラムして、ユーザ仕様に従って論理セルの出力から論理セルの入力に信号を伝えることができる。
【０００３】
技術が進歩して、より大きくより洗練されたプログラム可能論理回路が可能になると、論理セルの個数と必要な相互接続リソースの両方が回路内で増える。論理セルと相互接続リソースの増加した個数と競合するのが、回路サイズを小さく保つ必要性である。必要な回路サイズを最小化する形の１つが、あるレベルの接続性を維持しながら相互接続リソースを最小にすることである。したがって、チップ上で実装される機能性が増えるにつれて、多数の信号を接続するのに必要な相互接続するリソースがより早く使い果たされる可能性があることがわかるであろう。トレード・オフは、回路サイズを小さく保って回路内の論理セルの利用をより低くするか、あるいは回路サイズを劇的に増やすことになる、より多くのルーティング・リソースを設けることである。
【０００４】
最近４０年間に、プログラム可能論理回路の分野でますます複雑になる接続スタイルの進歩があった。Ｌ．Ｍ．Ｓｐａｎｄｏｒｆｅｒは、１９６５年に、隣接相互接続を使用するプログラム可能論理回路と、Ｃｌｏｓネットワーク内でスイッチを使用する複数の導体を介する接続との可能な実施を説明した。Ｒ．Ｇ．Ｓｈｏｕｐは、１９７０年の彼の博士論文で、隣接相互接続の使用と、より長距離の相互接続用のバスの使用との両方を説明した。
【０００５】
Ｆｒｅｅｍａｎは、１９８９年の米国特許第４８７０３０２号で、隣接相互接続、短（長さ１、単一と呼ばれる）距離相互接続と、クロックなどの信号用のグローバル信号線を使用するＦＰＧＡの商業的実施を説明した。短距離相互接続は、論理セルの入力と出力に相互作用し、各入力は、論理セルに隣接するすべての短いワイヤにスイッチを介して接続され、水平・垂直の短いワイヤが、ジャンクション内のスイッチ・ボックスを介して接続される。Ｅｌ  Ｇａｍａｌ他は、米国特許第４７５８７４５号で、セグメント化されたルーティングを導入し、この場合に、論理セルの入出力が、１次元の異なる長さのルーティング・セグメントと相互作用する。
【０００６】
Ｐｅｔｅｒｓｏｎ他の米国特許第５２６０６１０号とＣｌｉｆｆ他の米国特許第５２６０６１１号で、論理要素の組とインターフェースする導体のローカル・セットが導入され、ここで、論理要素のすべての入力が、スイッチを介してその組のすべてのローカル導体に接続され、追加のチップ長導体が水平・垂直の両方に導入され、その水平導体は垂直導体に接続され、水平導体が複数のローカル導体に接続される。米国特許第４８７０３０２号、米国特許第５２６０６１０号、米国特許第４７５８７４５号、米国特許第５２６０６１１号で、論理セルの入力導体が、ローカル導体の組への完全な接続を有する（たとえば、ｎ個の入力とｋ個のローカル導体の場合に、入力をローカル導体に接続するｎ×ｋ個のスイッチがある。マルチプレクサ（ＭＵＸ）方式を使用することもでき、その結果、トランジスタの個数が減る）。米国特許第４８７０３０２号、米国特許第４７５８７４５号、米国特許第５２６０６１０号、米国特許第５２６０６１１号で、全般的な相互接続リソースが、１つまたは２つの異なる長さに制限され（すなわち、米国特許第４８７０３０２号の単一の長さ、米国特許第５２６０６１０号と米国特許第５２６０６１１号ではローカルおよびチップ長）、あるいは１次元に制限される（すなわち、米国特許第４７５８７４５号では水平方向の異なる長さ、米国特許第５２６０６１０号と米国特許第５２６０６１１号では垂直方向のローカル）。
【０００７】
Ｃａｍａｒｏｔａ他の米国特許第５１４４１６６号とＫｅａｎの米国特許第５４６９００３号で、両方の次元で複数の異なる長さを有し、これらの導体の到達範囲に制限があるルーティング方式が導入された。米国特許第５１４４１６６号は、複数の可能な駆動ソースによって各ワイヤを選択的に駆動することを可能にするが、米国特許第５４６９００３号は、各ワイヤがＭＵＸ出力にハードワイヤされるという点で単一方向に制限されている。米国特許第５１４４１６６号と米国特許第５４６９００３号の両方で実現される接続性は、両方の接続が隣接または相対的にローカルであるという前提に基づけば非常に低く、あるいは、論理セル自体を、論理機能の実行ではなく相互接続リソースとして使用することができる。Ｔｉｎｇの米国特許第５４５７４１０号、米国特許第６５０７２１７号、米国特許第６０５１９９１号、米国特許第６５９７１９６号に、複数の長さの導体が論理セルの階層内のスイッチを介して相互接続される、複数レベル・アーキテクチャが記載されている。
【０００８】
Ｙｏｕｎｇ他の米国特許出願第２００１／０００７４２８と米国特許第５９１４６１６号に、２次元の複数の長さのワイヤ（各次元で３つ）を有するアーキテクチャが記載されており、ここで、短いローカル接続について、クロスバーに近い方式が使用され、論理セル出力の組が出力ポートの減らされた組に多重化され、この減らされた組が他の相互接続リソースにインターフェースされる。より長いワイヤは、一般に、めいめいの次元でより短い長さのワイヤにファンインする。Ｒｅｄｄｙ他の米国特許第６４１７６９４号に、インタースーパー領域導体、インター領域導体、ローカル導体が使用されるもう１つのアーキテクチャが開示されている。ローカル・ワイヤが論理要素の入力へのユニバーサル・アクセスを有するために、クロスバー方式が最低レベルで（ＭＵＸを使用して）使用される。Ｒｅｄｄｙ他の米国特許第５８８３５２６号に、ローカル・クロスバー内の回路削減技法を有するさまざまな方式が開示されている。
【０００９】
回路階層のベース・レベルでは、４入力ルック・アップ・テーブル（ＬＵＴ）論理セルが一般的に使用される。ベース論理セルでＬＵＴを使用することに２つの利益がある。１つの利益は、回路が、プログラム可能な制御を有するすべての４入力１出力ブール機能を可能にすることである。もう１つの利益は、４つの入力が交換可能であり、論理的に同等であることである。したがって、ＬＵＴが正しく機能するために、この４つの信号がＬＵＴの４つの入力に接続される限り、どの信号がＬＵＴのどの入力ピンに接続されるかは問題でない。
【発明の開示】
【発明が解決しようとする課題】
【００１０】
プログラム可能論理回路で解決されるべき共通の問題は、相互接続性の問題すなわち、信号を発する論理セルとその信号を受け取る論理セルが集積回路内の広い面積に分散している場合に（すなわち、各出力が複数の論理セルの入力に接続される場合のＭ論理セルのＭ出力）、信号を搬送する導体の第１組をこれらの信号を受け取る導体の複数の組にどのように接続するかである。非常に望ましいがほとんどの場合に非実用的な解決策は、クロス・バー・スイッチを使用することであり、この場合に、第１組のすべての導体が、スイッチを介して導体の複数の組のすべての導体に接続可能である。ある段階または別の段階の以前の解決策は、分割統治戦略を使用して接続性問題を複数の片に分割することを試み、その際、論理セルのローカル・クラスタが相互接続され、ローカル接続の延長を介してまたはより長距離の接続を使用してのいずれかで、論理の他のクラスタに延長される。これらの以前の相互接続方式は、アド・ホックであり、ほとんどは経験的体験に基づく。望ましいルーティング・モデルまたは相互接続アーキテクチャは、常に、回路の大きい部分にまたがる導体の複数の組を接続する多数の入出力の（プログラム可能な相互接続導体を介する）十分な接続性を保証しなければならない。
【００１１】
総合接続リソースを追跡するために複雑なソフトウェアが必要であると同時に、アルゴリズムが、プログラム可能論理回路を使用してカスタム設計を実装するプレース・アンド・ルート(place and route)ステージ中に相互接続性を改善するのに使用される。したがって、ルータビリティ(routability)または相互接続性をよりグローバルなスケールで保証できると同時に、相互接続のコストが必要なスイッチに関して低いままであり、カスタム設計実装のプレース・アンド・ルートを判定するソフトウェア労力が単純化される、プログラム可能論理回路用の新しい相互接続方式を有することが望ましい。
【発明を実施するための最良の形態】
【００１２】
本発明の目的、特徴、利益は、次の詳細な説明から明らかになる。
【００１３】
革新的なスケーラブル・ノンブロッキング・スイッチング・ネットワーク（ＳＮ）であって、スイッチを使用し、第１の複数の導体を導体の複数の組に接続する導体の中間ステージを含み、第１の複数の導体の各導体がＳＮを介して導体の複数の組のそれぞれからの１つの導体に接続することができる、スケーラブル・ノンブロッキング・スイッチング・ネットワークをまず説明する。このスケーラブル・ノンブロッキング・スイッチング・ネットワークは、単一ステージで、または複数ステージで階層的に、のいずれかで使用される時に、スイッチング回路、ルータ回路、プログラム可能論理回路で使用される大きいスイッチ・ネットワークを実現するために、広範囲の応用例に適用することができる。スケーラブル・ノンブロッキング・スイッチング・ネットワークは、導体の第１組をＳＮを介して導体の複数の組に接続するのに使用され、これによって、複数の組のそれぞれに含まれる導体が同等または交換可能になり、たとえば、複数の組のうちの１組の導体が論理セルの入力（ＬＵＴへの入力または論理セルの階層への入力とすることができる）になる。本発明のスケーラブル・ノンブロッキング・スイッチング・ネットワークは、導体の第１組の任意のサブセットを、ＳＮを介して導体の第２の複数の組の導体に接続することを可能にし、その結果、このサブセットの各導体を、導体の複数の組の各組からの１つの導体に接続できるようになる。
【００１４】
次の説明では、説明のために、本発明の完全な理解を提供するために多数の具体的な詳細を示す。本発明の実施形態をこれらの詳細なしで実践できることは、当業者に明白であろう。他の場合に、周知の構造と回路は、本発明を不必要に不明瞭にしないようにするために、ブロック図形式で図示する。説明のために、そうでないと指定されない限り、プログラム制御スイッチとスイッチの各用語は、この説明の文脈で交換可能であり、プログラム構成論理セル、論理セル、セル、ルック・アップ・テーブル（ＬＵＴ）、プログラム可能論理セルの各用語は、この説明の文脈で交換可能であり、導体、信号、ピン、ポート、信号線の各用語は、この説明の文脈で交換可能である。本発明が、使用されるスイッチの状態をセットするためにプログラム制御手段を使用し、この制御手段を、ヒューズ／アンチヒューズ・テクノロジなど、ワン・タイムとしたり、あるいは、ＳＲＡＭ（揮発性である）、フラッシュ（不揮発性である）、強誘電性（不揮発性である）など、再プログラム可能とすることができる実施形態を説明することに留意されたい。したがって、本発明は、スタティック・ランダム・アクセス・メモリ（ＳＲＡＭ）プロセス、ダイナミック・ランダム・アクセス・メモリ（ＤＲＡＭ）プロセス、ヒューズ／アンチヒューズ・プロセス、消去可能プログラム可能読取専用メモリ（ＥＰＲＯＭ）プロセス、フラッシュなどの電気的消去可能プログラム可能読取専用メモリ（ＥＥＰＲＯＭ）プロセス、強誘電プロセスを含むがこれらに限定されないさまざまなプロセスに関する。
【００１５】
本明細書で説明するプログラム可能論理回路で利用されるスケーラブル・ノンブロッキング・スイッチング・ネットワークの概念は、一般に、接続要件が使用可能な導体を超えない限り、複数の導体と導体の複数の組との間の無制限の接続を可能にするために適用することができる。
【００１６】
プログラム制御スイッチが、ある導体を別の導体に相互接続するのに使用される時に、ドライバ回路をそのスイッチに結合して、これらの導体をトラバースする信号の速度を改善することができる。さらに、複数の導体（信号）が、プログラム制御スイッチを介して１つの導体にファンインする場合に、望まれるならば、使用されるプロセス・テクノロジに応じて、導体への負荷を減らすか回路サイズを減らすかその両方のために、ＭＵＸ方式を使用することが可能である。ＭＵＸが使用される場合に、複数のスイッチが新しいスイッチ機構に変換される。ここで、有効な状態の個数はスイッチの個数と同一であり、接続性は、２つの導体を接続する際に特定の状態（複数のスイッチが使用される場合のスイッチに対応する）を選択することによってイネーブルされ、状態はプログラム可能制御によって決定される。
【００１７】
さまざまなタイプのスケーラブル・ノンブロッキング・スイッチング・ネットワークを説明するが、これには、ステージ０スケーラブル・ノンブロッキング・スイッチング・ネットワーク（０−ＳＮ）、ステージ１スケーラブル・ノンブロッキング・スイッチング・ネットワーク（１−ＳＮ）、ステージ２スケーラブル・ノンブロッキング・スイッチング・ネットワーク（２−ＳＮ）を含み、さらにマルチステージ・スケーラブル・ノンブロッキング・スイッチング・ネットワークへの拡張とプログラム可能論理回路への接続性を実現する上でのこれらのスケーラブル・ノンブロッキング・スイッチング・ネットワークの階層的な使用が含まれるが、これに限定はされない。
【００１８】
図１に、クラスタ（ＣＬＳＴ４）回路１００の実施形態を示すが、これには、スケーラブル・ノンブロッキング・スイッチング・ネットワーク２００が含まれ、ｋ個の４入力論理セル（この実施形態ではｋ＝４である）１０、２０、３０、４０と、２つのフリップフロップ５０、６０が含まれる。論理セル１０〜４０のそれぞれは、それぞれセル１０〜４０の４つの出力としての４つの導体１２１〜１２４と共に、セル１０の４つの入力１０１〜１０４（Ｎ０［０−３］）、セル２０の４つの入力１０５〜１０８（Ｎ１［０−３］）、セル３０の４つの入力１０９〜１１２（Ｎ２［０−３］）、セル４０の４つの入力１１３〜１１６（Ｎ３［０−３］）を有する。スイッチ１５１〜１５６、１５９、１６０は、論理セル出力がフリップフロップを駆動するのか、論理セルが回路１００出力１２５〜１２８を直接に出力するのかを制御するのに使用される。フリップフロップ５０、６０は、スイッチ１５７、１５８、１６１、１６２を使用して回路１００出力１２５〜１２８に出力する。さらに、導体１３１は、スイッチ１４１を介してセル１０の導体１０１を、スイッチ１４２を介してセル２０の導体１０５を駆動することができる。同様に、導体１３２は、それぞれスイッチ１４３、１４４を介してセル３０、４０を駆動することができる。セル２０は、導体１３３へのスイッチ１４５を使用して、出力１２２を介して隣接するＣＬＳＴ４回路（図１には図示せず）を駆動することができる。セル４０の出力１２４は、図１のスイッチ１４６を介して導体１３４を駆動する。３つの他の信号１３５〜１３７は、それぞれＳＥＴ、ＣＬＯＣＫ、ＣＬＥＡＲとしてフリップフロップを制御するのに使用される。さらに、図１は、スイッチ・ネットワークＭＴＸ２００を使用して１６個の入力１０１〜１１６を駆動するためにファン・インする（Ｘ＋１）個の導体１８０（Ｍ［０−Ｘ］）を有する。導体Ｍ［０−Ｘ］１８０は、Ｍ導体と呼ばれ、Ｍは、図１の実施形態の導体の個数（Ｘ＋１）と等しい。ｉ＝［０−（ｋ−１）］の入力導体Ｎｉ［０−３］１０１〜１１６はＮｉ導体と呼ばれ、Ｎｉは入力の個数と等しく、図１の実施形態では４である。図示のために、サイズＮｉ＝Ｎ＝４が図１に示されている。代替案では、各Ｎｉが、本明細書で説明する接続性特性を変更せずに異なるサイズを有することができる。
【００１９】
図２に、一実施形態を示すが、ここでは、図１のＭＴＸ２００が、ステージ０スケーラブル・ノンブロッキング・スイッチング・ネットワーク（０−ＳＮ）３００によって表されており、各Ｎ導体１０１〜１１６が、Ｍ導体（たとえば、図１の導体１８０）２０１〜２１１（Ｍ［０−１０］）の（Ｍ−Ｎ＋１）個の導体に接続可能であり、したがって、導体１０１〜１１６の入力導体ごとに図２に示されたスイッチの個数は、図２の０−ＳＮ３００では（Ｍ−Ｎ＋１）＝８である。スイッチ・ネットワーク０−ＳＮ３００は、接続の個数が使用可能な相互接続リソースを超えない限り（すなわち、論理セルのうちのいずれかの入力を駆動するＭ導体の個数が論理セルの入力の個数を超えることはできない）、Ｍ導体２０１〜２１１の任意のサブセットが一切ブロッキングなしで３００のスイッチを使用して論理セル１０〜４０のそれぞれの１つの入力導体を駆動することを可能にする。図２の方式は、クロス・バー接続に対する改善であり、ここで、Ｍ×（ｋ×Ｎ）＝１１×（４×４）＝１７６個のスイッチを含むフル・スイッチ・マトリックスではなく、スイッチの個数は、（Ｍ−Ｎ＋１）×（ｋ×Ｎ）＝１２８個である。図２の０−ＳＮ３００は、論理セルのそれぞれの４つの入力が交換可能または論理的に同等（したがって、図１のセル１０の導体１０１〜１０４が同等または交換可能である）であり、したがって、接続要件が特定のＭ導体を所与の論理セルに接続することである場合に、特定のＭ導体（すなわち、Ｍ［４］導体２０５）を所与の論理セルの入力ピンのいずれか（すなわち、スイッチ２２２を使用して図１のセル１０の導体１０１〜１０４のうちの導体１０１）に接続することだけが必要であると仮定することによって、上で述べた接続性を可能にする。
【００２０】
プログラム可能回路で使用されるテクノロジに応じて、いくつかの面積最小化を達成することができる。たとえば、６つのトランジスタを有するＳＲＡＭメモリ・セルを、パスゲートを使用して実施される各スイッチのプログラム制御として使用することによって、入力線１０１あたりの図２の８つのスイッチ２２１〜２２８が、５６個のトランジスタを必要とするようになる。その代わりに、３つのメモリ・ビットを使用する８入力ＭＵＸを使用して８つの状態を制御して、８つのＳＲＡＭビットと８つのスイッチを効果的に置換することができる。ＭＵＸ方式では、３ビット、１４個のパスゲート、おそらく１つのインバータ（信号を再生成するため）が、３４個のトランジスタを使用し、これは、各スイッチのプログラム制御として８つのＳＲＡＭメモリ・セルと共に使用される５６個のトランジスタからの大幅な削減である。導体１０１の負荷が、ＭＵＸ実施を使用して減らされると同時に、８対１ＭＵＸに起因する追加の遅延がある。
【００２１】
図３に、図１のＭＴＸ２００が、サブグループＭａ＝［Ａ０−Ａ４］＝５  ３０１〜３０５導体とＭｂ＝［Ｂ０−Ｂ４］＝５  ３０６〜３１０導体からなるＭ＝Ｍａ＋Ｍｂ＝１０個の導体３０１〜３１０を有する２つのステージ０スケーラブル・ノンブロッキング・スイッチング・ネットワーク３３０、３２０を使用することによって表される実施形態を示す。４つの論理セルのそれぞれの上側の２つの入力導体（セル１０は導体１０１〜１０２からなり、セル２０は導体１０５〜１０６からなり、セル３０は導体１０９〜１１０からなり、セル４０は導体１１３〜１１４からなる）について、Ｎａ＝２であり、ｋ＝４の論理セルの下側の２つの入力導体（セル１０は導体１０３〜１０４からなり、セル２０は導体１０７〜１０８からなり、セル３０は導体１１１〜１１２からなり、セル４０は導体１１５〜１１６からなる）について、Ｎｂ＝２である。図３のフル・サイズ・ステージ０スケーラブル・ノンブロッキング・スイッチング・ネットワークは、入力導体あたり（Ｍ−Ｎ＋１）＝１０−４＋１＝７個のプログラム制御スイッチを有するはずである。その代わりに、図３の実施形態で、入力スイッチの数は、別々のＭａ導体およびＭｂ導体（Ｍａ＝Ｍｂ＝５）のゆえに、数Ｎが２つの部分に分割される（Ｎａ＝Ｎｂ＝２）ので、４つだけである。したがって、ネットワーク３３０の入力導体あたりのプログラム制御スイッチの個数は、Ｍａ−Ｎａ＋１＝５−２＋１＝４であり、ネットワーク３２０の入力導体あたりのプログラム制御スイッチの使用は、Ｍｂ−Ｎｂ−１＝４である。ネットワーク３３０を使用する４つの論理セルの上側の２つの入力に接続されるＭａ  ３０１〜３０５導体が、図２に示された接続性を維持する（ネットワーク３２０を使用する４つの論理セルの下側の２つの入力へのＭｂ導体３０６〜３１０についても同様である）ことは事実であるが、４つの論理セルにファンインするための［Ａ０−Ａ４］、［Ｂ０−Ｂ４］の任意の使用がそうであることは事実ではない。この制約は、図３の２つの０−ＳＮ３２０、３３０を介するＮ導体へのＭ導体の任意の割り当てを妨げる。しかし、ステージ０スケーラブル・ノンブロッキング・スイッチング・ネットワーク３２０、３３０は、一緒に、プログラム可能論理回路のよい接続性を実現する経済的な実施とすることができると同時に、許容可能なＭ導体使用を記帳し、追跡する上でのソフトウェア労力は、図２の方式より複雑である。図３は、１０個のうちの少なくとも８つのＭ導体を４つの論理セルの入力に任意に接続することを可能にするが、各１つの導体が、ネットワーク３２０、３３０を使用して４つの論理セルのそれぞれへの１つの入力に接続され、ここでの制約は、１０個の導体を図２の事例のように任意に割り当てることができないことである。
【００２２】
本発明の実施形態で、導体の第１グループは、スイッチ・ネットワークを介して同等の導体の複数のグループに接続される。ここまでは、０−ＳＮを提示し、ここで、Ｍ導体の第１組とＮ導体の複数のｋ組の間を無制限に接続するために（Ｍ−Ｎ＋１）×Ｎ×ｋ個のスイッチがあり、Ｍ導体の任意のサブセットを、ブロックなしで０−ＳＮを使用してＮ導体のｋ個の組のそれぞれへの１つの導体に接続することができる。
【００２３】
図４に、０−ＳＮの接続特性を変更せずにスイッチ・ネットワーク内で使用されるスイッチの個数を大きく減らすことができる代替実施形態方式を示す。図４には、図１のＭＴＸ２００が、ステージ１スケーラブル・ノンブロッキング・スイッチング・ネットワーク（１−ＳＮ）によって表されている実施形態が示されている。１−ＳＮ４００は、１−ＳＮ４００の２つのスイッチと１つの中間導体を使用して、導体４０１〜４１１のＭ導体を導体１０１〜１１６のＮ導体に接続する。Ｍ導体２０１〜２１１を図２のネットワーク３００（１２８個のスイッチが使用される）を介してＮ導体１０１〜１１６のｋ個の組に直接に接続するのではなく、図４の１−ＳＮ４００は、まずスイッチ４３７を介して中間Ｉ導体４５４に接続し、次にサブネットワーク４５０のスイッチ４４１を介してＮ導体１０９に接続することによって、Ｍ導体４０７（Ｍ［６］）をＮ導体１０９に接続する。同様に、同一のＭ導体４０７を、それぞれスイッチ４４２、４４３、４４４を介して同一の中間導体４５４を介してＮ導体１０１、１０５、１１３に接続することができる。図４の１−ＳＮ４００は、９６個のスイッチを有し、これは、図２の０−ＳＮ３００と比較して、スイッチの個数の２５％の削減である。相互接続の中間ステージを有するスケーラブル・ノンブロッキング・スイッチング・ネットワークを作成することによって０−ＳＮに必要なスイッチの個数を減らすことが可能であり、ここで、Ｍ導体のそれぞれを、Ｎ導体のｋ個の組のそれぞれからの導体に任意に接続することができる。このスケーラブル・ノンブロッキング・スイッチング・ネットワークは、Ｍ導体をＮ導体のｋ個の組のそれぞれからの複数の導体に接続することができるが、論理的に、Ｎ導体のそれぞれの複数の導体に接続する必要はない。
【００２４】
図４に、ｉ＝［１−Ｎ］の中間導体ＩiのＮ個の組を有する１−ＳＮ４００を示すが、ここで、１１個のＭ導体４０１〜４１１、４組のＮ導体１０１〜１０４、１０５〜１０８、１０９〜１１２、１１３〜１１６の４つの組があり、ｋは４である。たとえば、第１中間導体Ｉ1は、Ｎ導体のそれぞれの第１入力、したがって導体１０１、１０５、１０９、１１３に関連する４つの導体４５１〜４５４である。同様に、導体４６１〜４６４は、導体１０４、１０８、１１２、１１６に関連するＩ4導体である。０−ＳＮのＮ導体の各導体の（Ｍ−Ｎ＋１）個のスイッチが、図４の対応するＩi導体の間で分散される。たとえば、Ｍ導体４０１〜４０８を結合する８つのスイッチ４３１〜４３８が、Ｉ1導体４５１〜４５４に分散され、Ｉ1導体のそれぞれは、［（Ｍ−Ｎ＋１）／Ｉ1］個のスイッチに結合され、この個数は２である。図４の例では、Ｉi導体のそれぞれの中間導体の個数が、４である。一般に、異なるＩiは、均一の個数である必要はない（下で説明する）。図４の１−ＳＮ４００は、［（Ｍ−Ｎ＋１）×Ｎ＋ｓｕｍi=[1-N]（Ｉi×ｋ）］＝３２＋６４＝９６個のスイッチを有し、Ｉiは、Ｉi中間導体のＮ個の組のそれぞれの中間導体の個数である。図４の１−ＳＮ４００は、図２のめいめいの０−ＳＮ３００と同一の接続特性を可能にし、Ｍ導体の任意の導体を１−ＳＮ４００の２つのスイッチと１つの中間導体を介してＮ導体の各ｋ組の１つの導体に接続する。
【００２５】
図４の１−ＳＮ４００では、Ｍ導体の任意のＮタプルが、Ｉi導体の異なるＮ組のスイッチの適当な選択を有する。たとえば、導体４０１、４０４、４０５、４１０は、Ｍ導体の４タプル（Ｎ＝４）であり、導体４０１は、スイッチ４３１を介して導体４５１（Ｉ1導体の）に接続され、導体４０４は、スイッチ４４６を介して導体４６６（Ｉ2導体の）に接続され、導体４０５は、スイッチ４４７を介して導体４６７（Ｉ3導体の）に接続され、導体４１０は、スイッチ４２７を介して導体４６４（Ｉ4導体の）に接続される。Ｍ導体のＮタプルの任意のサブセットが、中間導体への同一特性の接続を有する。さらに、Ｉi導体の各中間導体は、Ｎ導体のｋ組のそれぞれの１つのＮ導体に接続可能である。たとえば、導体４５１〜４５４の任意の導体が、サブネットワーク４５０内のスイッチを介して導体１０１、１０５、１０９、１１３に接続可能である。同様に、導体４６１〜４６４の任意の導体が、サブネットワーク４２０内のスイッチを介して導体１０４、１０８、１１２、１１６に接続可能である。
【００２６】
図５に、図１のＭＴＸ２００を表す１−ＳＮの代替実施形態を示す。１−ＳＮ  ５００には、１２個のＭ導体５０１〜５１２と、４組のＮ導体１０１〜１１６と、Ｎ組の中間Ｉ1導体５２１〜５２３、Ｉ2導体５２４〜５２６、Ｉ3導体５２７〜５２９、Ｉ4導体５３０〜５３２とがあり、Ｍ＝Ｉ1＋Ｉ2＋Ｉ3＋Ｉ4またはＩi＝Ｍ／Ｎ＝３である。図５のスイッチの個数は、［（Ｍ−Ｎ＋１）×Ｎ＋ｓｕｍi=[1-N]（Ｉi×ｋ）］＝３６＋４８＝８４である。対応する０−ＳＮは、１４４個のスイッチを有し、クロス・バーは、１９２個のスイッチを有するはずである。図５の１−ＳＮ  ５００の接続特性は、図４の１−ＳＮ４００に関して前に述べたものと同一であるが、より少数の中間導体とスイッチを有する。図４と図５の図は、それぞれ図４のサブネットワーク４５０のスイッチと図５のサブネットワーク５４０のスイッチを介して導体１０１、１０５、１０９、１１３（図１の４つの論理セル１０〜４０のそれぞれの第１入力である）に接続される第１組の中間Ｉ1導体（図４の導体４５１〜４５４と図５の導体５２１〜５２３）を有する。同等に効果的な代替案は、この例の特定の論理セルの４つの入力のそれぞれが、Ｉi導体の異なる組によってカバーされる限り、４つの論理セルのそれぞれからの任意の１つの導体（ｉ番目ではなく）にＩi導体の各組を接続することである。
【００２７】
図６に、図５の１−ＳＮ  ５００より強い接続性特性を有するステージ１スケーラブル・ノンブロッキング・スイッチング・ネットワークの異なる版の一実施形態を示す。より多くのスイッチを必要とするが、１−ＳＮ６００の１２個のＭ導体６０１−６１２（Ｍ［０］−Ｍ［１１］）は、Ｉi中間導体６２１〜６２３、６２４〜６２６、６２７〜６２９、６３０〜６３２のＮ組のそれぞれのすべての導体に接続可能である。これは、図４と図５のＭ導体の（Ｍ−Ｎ＋１）個の導体への結合と対照的である。１−ＳＮ６００では、導体６０１〜６１２が、サブネットワーク６２０のスイッチを介してＩ1導体６２１〜６２３に接続可能である。導体６０１〜６１２は、サブネットワーク６４０のスイッチを介してＩ2導体６２４〜６２６に接続可能である。導体６０１〜６１２は、サブネットワーク６５０のスイッチを介してＩ3導体６２７〜６２９に接続可能である。導体６０１〜６１２は、サブネットワーク６６０のスイッチを介してＩ4導体６３０〜６３２に接続可能である。図６の１２個のＭ導体６０１〜６１２は、図５の１−ＳＮ  ５００と比較してより強い接続性特性を有し、Ｍ／Ｉi導体のうちの１つの導体をプログラム選択して、ｋ組のうちのいずれかの特定のＮ導体に接続することができる。例として、図６の実施形態では、Ｎタプル導体６０１〜６０４、６０５〜６０８、６０９〜６１２（Ｍ導体の）のどれであっても、１−ＳＮを使用してＮ導体の４つの（ｋ＝４）組のいずれかの任意の特定の入力導体に接続することができるが、各４タプル内の導体は、特定の入力導体に対して相互に排他的である。図６の１−ＳＮ６００で必要なスイッチの個数は、［Ｍ×Ｎ＋ｓｕｍi=[1-N]（Ｉi×ｋ）］＝４８＋４８＝９６個のスイッチである。
【００２８】
必要なスイッチに関する０−ＳＮと１−ＳＮの間の相違は、図５の場合に［（Ｍ−Ｎ＋１）×Ｎ×ｋ］と［（Ｍ−Ｎ＋１）×Ｎ＋ｓｕｍi=[1-N]（Ｉi×ｋ）］の間の差であり、ここで、（Ｍ−Ｎ＋１）個のＭ導体が、１−ＳＮを介してＩi導体のＮ組のそれぞれのＩi導体に接続可能である。必要なスイッチに関する０−ＳＮと１−ＳＮの間の相違は、図６の場合に［Ｍ×Ｎ×ｋ］と［Ｍ×Ｎ＋ｓｕｍi=[1-N]（Ｉi×ｋ）］の間の差である。各Ｉi＝ｋと単純化すると、Ｍは、図５の場合に少なくとも［ｋ＋Ｎ＋１／（ｋ−１）］であり、Ｍは、少なくとも［ｋ＋１＋１／（ｋ−１）］であり、図５の方式が、それでもＭを上の個数未満にするために働くことに留意する価値がある。さらに、１−ＳＮの方式が働くためには、中間導体［（Ｍ−Ｎ＋１）／Ｉi］あたりのスイッチの個数が、ＳＮのノンブロッキング特性を失わずに、Ｎを超えてはならない。この個数［（Ｍ−Ｎ＋１）／Ｉi］は、整数でない場合があり、その場合に、整数Ｐiが、数（Ｍ−Ｎ＋１）／Ｉiを上または下に丸めながら、ｓｕｍi=[1-N]Ｐi＝（Ｍ−Ｎ＋１）にすることによって使用される。同様に、図６の場合に、Ｍが（Ｍ−Ｎ＋１）の代わりに使用され、したがって、Ｐiは、（Ｍ／Ｉi）を上または下に丸めながら、ｓｕｍi=[1-N]Ｐi＝Ｍにした整数である。さらに、図４と図５の例では、中間導体の個数ｓｕｍi=[1-N]Ｉiが、少なくともＭを上限とし、ｋ×ＮがＭより大きい場合に、ｓｕｍi=[1-N]Ｉiは、Ｍまたはｋ×Ｎのいずれかあるいはその間のある数になる。各個々のＩiはＭ／Ｎ、ｋ、またはその間のある数を上限とするが、Ｍ／Ｎが整数で割り切れない場合があるので、Ｉiは、Ｍ／Ｎを上または下に丸めることによる整数となり、したがって、個々のＩiがｉ＝［１−Ｎ］のすべてのｉの間で均一でない場合があることがわかる。
【００２９】
図７に、図６の実施形態のスイッチの個数が、１−ＳＮの接続性特性を大きく変更せずに減らすことができる実施形態を示す。図７は、導体６０１が導体６２１に短縮され、導体６０２が導体６２４に短縮され、導体６０３が導体６２７に短縮され、導体６０４が図６の導体６３０に短縮され、図６のサブネットワーク６７０の１６個のスイッチが削除され、スイッチの個数が、図６の９６個ではなく図７で８０個である削減を表す。図７の１−ＳＮ  ７００からサブネットワーク７１０、７２０、７３０、７４０を引き、Ｍ導体６０５〜６１２を加えたものは、図６で説明した１−ＳＮ６００と同一の、より強い接続性特性を有し、Ｍ＝８の１−ＳＮである。たとえば、より多くのＭ導体を中間導体に短縮することによって、スイッチの個数をさらに減らすことが可能であるが、接続性特性が、大きく減り、接続パターンを判定する際のソフトウェア労力が、ますますより複雑になるはずである。
【００３０】
図８に、Ｍ＝４８、ｋ＝４、Ｎ＝１６であり、ｉ＝［１−１６］についてＩi＝３である１−ＳＮの実施形態を示す。１−ＳＮ８００には７２０個のスイッチがあるので、０−ＳＮは、２１１２個のスイッチを必要とし、クロス・バーは、３０７２個のスイッチを必要とするはずである。Ｉi中間導体のＮ（＝１６）組のそれぞれ、たとえばＩ16が、３つの導体（サブネットワーク８１０の内部）を有し、Ｉ16導体は、図８では（Ｍ−Ｎ＋１）＝３３個のＭ導体に結合され、この中間導体のそれぞれが、サブネットワーク８１１内の１１個のスイッチを介して１１個のＭ導体に結合される。接続経路に中間導体と余分のスイッチを導入することによって、１−ＳＮ８００は、０−ＳＮと比較して、必要なスイッチの個数の大きな減少を実現する。
【００３１】
さまざまな実施形態で、Ｍがｋ×Ｎより小さく、Ｍ導体がファンイン信号を担持する導体であり、Ｎ導体のＫ個の組がこれらのファンイン信号を受け取る導体である例を使用した。これがそうである必要はない。単純に、Ｍがｋ×Ｎより大きいＳＮを有することができる。代替案では、たとえば、図６の導体１０１〜１０４、１０５〜１０８、１０９〜１１２、１１３〜１１６を、論理セルの４つのクラスタからの１６個の出力と考え、１６個から１２個への出力削減のために１−ＳＮを使用することを考えることができ、ここで、１６個の出力のうちの１２個の出力の任意のサブセットを、１−ＳＮを使用して選択することができる。さらに、さまざまな図面の導体１０１〜１０４、１０５〜１０８、１０９〜１１２、１１３〜１１６は、論理セルの入力または出力のいずれかである必要はなく、複数の同等の導体とすることができ、ここで、複数の同等の導体の特定の導体への接続と異なって、この複数の同等の導体のどの導体への接続でも十分である。
【００３２】
プログラム可能論理回路の相互接続アーキテクチャの設計において、回路サイズ、速度、顧客指定の設計をプレース・アンドルートするソフトウェアの簡単さなどのエンジニアリング・トレードオフに基づいて、適度な接続性と適度な相互接続リソースを設けることが重要である場合がある。Ｍ導体とＮ導体のｋ個の組の間に比Ｒがあり、Ｒ＝Ｍ／（ｋ×Ｎ）であり、Ｒが小さすぎる場合に、接続性はより大きいＲより制限される。たとえば、図６の回路はＲ＝０．７５を有する。Ｒを、スケーラブル・ノンブロッキング・スイッチング・ネットワークを使用する回路の階層を構成する際のエクスパンション・エクスポーネント(expansion exponent)と呼ぶ。スケーラブル・ノンブロッキング・スイッチング・ネットワークを使用するプログラム可能論理回路の設計用の一般的に使用されるエクスパンション・エクスポーネントは、０．５と１．０の間の範囲内にあり、その選択は、エンジニアリング設計トレードオフ（すなわち、論理利用度、回路面積最小化、ソフトウェア・プレース・アンド・ルートの簡単さなど）、使用されるテクノロジ（すなわち、ＳＲＡＭ、アンチヒューズなど）などの要因に依存する。時々、回路の一部で、たとえば、多数の出力がＳＮを使用してより少ない個数に減らされる出力削減で、この範囲を超えることが有利である。
【００３３】
前の議論は、０−ＳＮと１−ＳＮの使用を扱ったが、これらは、プログラム可能論理セルの相互接続用の回路階層を構築するのに使用することができ、これによって、階層の各レベルに、さまざまなスケーラブル・ノンブロッキング・スイッチング・ネットワークを使用する回路全体のさまざまな導体に接続するための関連する０−ＳＮおよび／または１−ＳＮと共に複数のプログラム可能論理回路が含まれる。前に説明した方式は、相互接続リソースと論理機能が使用可能なままである限り、０−ＳＮと１−ＳＮを使用して、回路階層のすべてのレベルの任意の信号への接続が、階層内の論理セルのいずれへの入力にも達することを可能にする。
【００３４】
下では、ステージ１とステージ２のスケーラブル・ノンブロッキング・スイッチング・ネットワークを階層的に使用してプログラム可能論理回路を構築する方式を説明する。図９に、１６個のＭ導体９０１〜９１６と、４組のＮ導体１０１〜１０４、１０５〜１０８、１０９〜１１２、１１３〜１１６（Ｎ＝４）と、ｉ＝［１−Ｎ］であり各Ｉi＝Ｍ／Ｎ＝４であるＮ組のＩi導体９３１〜９３４、９３５〜９３８、９３９〜９４２、９４３〜９４６とを有するステージ１スケーラブル・ノンブロッキング・スイッチング・ネットワークを使用する図１のＣＬＳＴ４回路１００のＭＴＸ回路２００の一実施形態を示す。エクスパンション・エクスポーネントＲは、図９の実施形態では１．０である。
【００３５】
たとえば図９の１−ＳＮ９００を使用して、プログラム可能回路を作る際の構成によって、Ｍ導体９０１〜９１６の任意のサブセットを、１−ＳＮ９００を介してＮ導体のｋ個の組のそれぞれの１つの導体に個別に接続することができる。これらのＭ導体自体が、次に、論理的に同等になる。図１のＣＬＳＴ４回路１００の外部のどこかで発する任意の信号を図１の４つの論理セル１０〜４０のそれぞれからの４つの入力（導体１０１から１０４から１つ、導体１０５から１０８から１つ、導体１０９から１１２から１つ、導体１１３から１１６から１つ）まで接続するために、Ｍ導体のうちの１つに接続することだけが必要である。したがって、これらのＭ導体９０１〜９１６を、階層的にＮ導体（Ｎ＝１６）として扱うことができ、１−ＳＮと一緒に４つの論理セルと２つのフリップ・フロップを含む回路をそれぞれが有するこれらの新しいＮ導体の複数の新しいｋ個の組が、Ｍ導体の新しい組によって、ＳＮなどの新しいスイッチ・ネットワークを介して選択的に接続される。このプロセスを、所望の回路が上で述べた無制限の接続性を可能にしながら所望の回路サイズに達するまで繰り返すことができる。
【００３６】
図１０に、４組の図１のＣＬＳＴ４  １００（図１０のＣＬＳＴ４  １０１０、ＣＬＳＴ４  １０２０、ＣＬＳＴ４  １０３０、ＣＬＳＴ４  １０４０）を使用する回路階層ＣＬＳＴ１６  １０００の次のレベルのブロック図実施形態を示すが、ここで、回路ＭＴＸ２００は、図９の１−ＳＮ９００と、４８個の導体１０５５（Ｍ［０−４７］）と１６個の導体１０５６（ＯＷ［０−７］、ＯＥ［０−７］）を有する６４個のＭ導体と４組のＮ導体１０６０、１０７０、１０８０、１０９０とを備えた回路ＭＴＸ１６  １０５０のステージ２スケーラブル・ノンブロッキング・スイッチング・ネットワークとを使用して実装され、Ｎ導体のそれぞれは、図９の１６個のＭ導体９０１〜９１６に対応する１６個の導体を有する。図１０では、６４個のＭ導体１０５５、１０５６のうちの１６個の導体１０５６が、４つのＣＬＳＴ４  １００回路１０１０、１０２０、１０３０、１０４０の４つの出力１０６５、１０７５、１０８５、１０９５に直接に接続される。４つの導体の４つの組を有する１６個の導体１０５６（ＯＷ［０−７］、ＯＥ［０−７］）と４つの導体のそれぞれは、図１のＣＬＳＴ４  １００回路の４つの出力１２５〜１２８（Ｏ［０−３］）に対応する。エクスパンション・エクスポーネントＲは、この回路１０００では、やはり１．０である。
【００３７】
多数の導体を導体の複数の組に接続する、回路階層のこの次レベルのスケーラブル・ノンブロッキング・スイッチング・ネットワークの使用を、図１１Ａに示す。図１１Ａには、ブロック図形式で、図１０の回路ＭＴＸ１６  １０５０の実施形態が示され、ここで、６４個のＭ導体１１０１（Ｍ［０−４７］、ＯＷ［０−７］、ＯＥ［０−７］）は、図１０の導体１０５５、１０５６に対応する。中間導体の第１ステージは、Ｎ０組（Ｎ０＝４）の１６個のＩ０i導体（ｉ＝［１−Ｎ０］についてＩ０i＝Ｍ／Ｎ０＝１６）１１５０、１１６０、１１７０、１１８０からなる。Ｍ導体１１０１は、サブネットワーク１１１０、１１２０、１１３０、１１４０のスイッチを使用して、最初の４組の中間ステージＩ０i導体１１５０、１１６０、１１７０、１１８０にインターフェースする。図１１Ｂに、導体１１０１がサブネットワーク１１２０を介して導体１１６０に接続される方式を示す。導体１１０１がサブネットワーク１１２０を介して導体１１５０に、サブネットワーク１１３０を介して導体１１７０に、サブネットワーク１１４０を介して導体１１８０に接続される接続方式は、図１１Ｂのサブネットワーク１１２０と同一である。この実施形態でＭ導体１１０１と４組の第１ステージ中間導体１１５０、１１６０、１１７０、１１８０の間で使用されるスイッチの個数は、Ｍ×Ｎ０＝２５６である。図５に関して説明したように、代替実施形態は、その代わりに（Ｍ−Ｎ０＋１）×Ｎ０個のスイッチを有することである。
【００３８】
図１に、回路ＴＡ１  １１６５の実施形態を示すが、ここで、導体１１６０は、第２のＮ０個の組のＩ０i導体であり、ｉ＝２であり、Ｉ０i＝１６であり、中間導体１２０１〜１２１６（図１１Ａの導体１１６０に対応する）は、１６個の導体１２４１〜１２５６（図１１Ａの導体１１６１〜１１６４に対応する）にインターフェースする。図１１Ａのサブネットワーク１１５５、１１７５、１１８５は、サブネットワーク１１６５と同一の回路であって、導体１１５０、１１７０、１１８０を、それぞれ図１１Ａの導体１１５１〜１１５４、１１７１〜１１７４、１１８１〜１１８４に相互接続する。
【００３９】
図１２では、回路ＴＡ１が、図１１Ａの１−ＳＮ１１６５であり、Ｍ導体１２０１〜１２１６は、図１１Ａの１６個の中間Ｉ０2導体１１６０（Ｉ１＿１［０−１５］）であり、１６個の中間導体１２２１〜１２３６は、ｉ＝２、ｊ＝［１−Ｎ１］のＮ１（＝４）組のＩ１2j（Ｉ１2j＝Ｍ／Ｎ１＝４）すなわち、導体１２２１〜１２２４、１２２５〜１２２８、１２２９〜１２３２、１２３３〜１２３６からなる。Ｉ１2j導体は、それぞれ、ｊ＝［１−Ｎ１］の４組の宛先導体１２４１〜１２４４、１２４５〜１２４８、１２４９〜１２５２、１２５３〜１２５６に接続される。図１２の１−ＳＮ１１６５は、図９の同一の１−ＳＮ９００を使用する。しかし、１−ＳＮ１１６５は、図１１Ａのステージ２スケーラブル・ノンブロッキング・スイッチング・ネットワークの第２部分内の４つ（サブネットワーク１１５５、１１６５、１１７５、１１８５）のうちの１つであり、２−ＳＮの導体１１５１〜１１５４、１１６１〜１１６４、１１７１〜１１７４、１１８１〜１１８４は、それぞれ図１０のＣＬＳＴ４回路１０１０、１０２０、１０３０、１０４０のＭ導体１０６０、１０７０、１０８０、１０９０である。ＣＬＳＴ４回路１０１０、１０２０、１０３０、１０４０のそれぞれは、図９の１−ＳＮ９００と共に、図１のＣＬＳＴ４回路１００に対応する。
【００４０】
図１２のＴＡ１回路１１６５は、導体１２０１〜１２１６を導体１２４１〜１２５６に選択的にすなわち１２４１、１２４５、１２４９、１２５３に接続し、これらの導体は、図１０のＣＬＳＴ４  １０１０の１６個のＭ導体１０６０のうちの４つ（Ｃ０［０−１５］のＣ０［４−７］）に対応する図１１Ａの導体１１６１（Ｎ０［４−７］）である。同様に、導体１２４２、１２４６、１２５０、１２５４は、図１１Ａの導体１１６２（Ｎ１［４−７］）であり、これは、図１０のＣＬＳＴ４  １０３０の１６個のＭ導体１０８０のうちの４つ（Ｃ１［０−１５］のＣ１［４−７］）に対応する。導体１２４３、１２４７、１２５１、１２５５は、図１１Ａの導体１１６３（Ｎ２［４−７］）であり、これは、図１０のＣＬＳＴ４  １０２０の１６個のＭ導体１０７０のうちの４つ（Ｃ２［０−１５］のＣ２［４−７］）に対応する。導体１２４４、１２４８、１２５２、１２５６は、図１１Ａの導体１１６４（Ｎ３［４−７］）であり、これは、図１０のＣＬＳＴ４  １０４０の１６個のＭ導体１０９０のうちの４つ（Ｃ３［０−１５］のＣ３［４−７］）に対応する。
【００４１】
図１１ＡのＭＴＸ  １０５０回路の１−ＳＮ実装では、Ｍ＝６４、ｋ＝４、Ｎ＝１６であり、２−ＳＮ実装では、中間導体の各ステージの組の個数Ｎ０＝４およびＮ１＝４であり、積Ｎ０×Ｎ１はＮと等しい。図６と図９で述べた、より強い接続性のＳＮを使用する図１０の２−ＳＮ１０５０のスイッチの個数は、Ｍ×Ｎ０＋ｓｕｍi=[1-N0]［（Ｉ０i×Ｎ１）＋ｓｕｍj=[1-N1]（Ｉ１ij×（Ｉ０i／Ｎ１））］であり、ここで、ネットワーク１０５０でｉ＝［１−Ｎ０］についてＩ０i＝Ｍ／Ｎ０であり、ｉ＝［１−Ｎ０］、ｊ＝［１−Ｎ１］についてＩ１ij＝Ｉ０i／Ｎ１であり、したがって、Ｉ０i＝１６、Ｉ１ij＝４であり、１０５０の２−ＳＮは７６８個のスイッチを有する。１−ＳＮ実装は１２８０個のスイッチを必要とし、フル・クロス・バー・スイッチは４０９６個のスイッチを必要とするはずである。各Ｉ０i導体が、Ｍ個ではなく（Ｍ−Ｎ０＋１）のＭ導体にインターフェースされ、各Ｉ１ij導体が、Ｉ０i個ではなく（Ｉ０i−Ｎ１＋１）個のＩ０i導体にインターフェースされる場合に、スイッチの個数は、（Ｍ−Ｎ０＋１）×Ｎ０＋ｓｕｍi=[1-N0]［（Ｉ０i−Ｎ１＋１）×Ｎ１）＋ｓｕｍj=[1-N1]（Ｉ１ij×（Ｉ０i／Ｎ１））］になる。図１０の場合に、Ｎ＝Ｎ０×Ｎ１、Ｉ０i＝Ｍ／Ｎ０、Ｉ１ij＝Ｍ／Ｎ＝ｋであり、したがって、この場合の２−ＳＮのスイッチの個数は［Ｍ×（Ｎ０＋Ｎ１＋ｋ）］である。
【００４２】
前に述べたように、異なるＳＮのＮ導体のＫ個の組のＮ導体のそれぞれは均一のサイズである必要がない。ＳＮは、異なるサイズを有するＮiを用いて構成することができ、ここで、最大のサイズを有するＮiが、均一のサイズを有する新しいＮとして使用され、仮想導体とスイッチを、より小さいサイズを有するＮiに追加し、そのＮiがサイズＮを有するように見せることができる。相互接続仕様は、より小さいサイズを有するＮiがＮiより多数の接続を有することを要求しないので、ＳＮの接続性特性の変更はない。例として、図１で、それぞれ論理セル１０〜４０の入力としての４組のＮ導体１０１〜１０４、１０５〜１０８、１０９〜１１２、１１３〜１１６の代わりに、図１の論理セル１０が、３つの入力１０１〜１０３だけを有することができる。Ｍ導体６０１〜６１２を有する図６のＳＮで、図６のスイッチおよび中間導体６２１〜６３２は、同一のままであるが、サブネットワーク６８０の３つのスイッチと導体１０４が、「仮想」であり、図６のＳＮから除外できることが異なる。
【００４３】
スケーラブル・ノンブロッキング・スイッチング・ネットワークの複数のステージを、上で説明した方式を使用して作ることができ、たとえば、図１０のＭＴＸ  １０５０を、Ｎ０＝２、Ｎ１＝２、Ｎ２＝４を、ｉ＝［１−Ｎ０］、ｊ＝［１−Ｎ１］、ｋ＝［１−Ｎ２］について、第１中間Ｉ０i導体Ｉ０i＝Ｍ／Ｎ０、Ｉ１ij＝Ｉ０i／Ｎ１、Ｉ２ijk＝Ｉ１ij／Ｎ２と共に使用して、ステージ３スケーラブル・ノンブロッキング・スイッチング・ネットワークとして実施することができ、ここで、Ｎ０×Ｎ１×Ｎ２＝Ｎ＝１６であり、これは、図１０の４つのＣＬＳＴ４回路１０１０、１０２０、１０３０、１０４０のそれぞれの入力の個数である。同様に、ＳＮ１０５０を、ステージ４  ＳＮとして実施することができ、ここでＮ０＝２、Ｎ１＝２、Ｎ２＝２、Ｎ３＝２であり、導体の４つの中間ステージが、Ｍ導体をＮ導体に接続する。図１０のＳＮ１０５０内の１−ＳＮ実装の上の２−ＳＮ実装は、Ｎ×Ｍ＝１６Ｍと（Ｎ０＋Ｎ１）×Ｍ＝（４＋４）×Ｍ＝８Ｍの間の差によるスイッチの個数の減少を有し、それぞれ（Ｎ０＋Ｎ１＋Ｎ２）＝（２＋２＋４）＝８および（Ｎ０＋Ｎ１＋Ｎ２＋Ｎ３）＝（２＋２＋２＋２）＝８の３−ＳＮと４−ＳＮは、（Ｎ０＋Ｎ１）＝（４＋４）＝８の２−ＳＮに対する改善を有しない。したがって、これは、Ｎiの合計すなわち各ステージの中間導体の組の個数が、合計して前のステージのマルチステージＳＮより少ない時に限って意味をなす可能性がある。したがって、Ｎ＝６４について、Ｎ０＝Ｎ１＝Ｎ２＝４を使用し、（Ｎ０＋Ｎ１＋Ｎ２）＝１２である３−ＳＮは、Ｎ０＝Ｎ１＝８を使用し、（Ｎ０＋Ｎ１）＝１６である２−ＳＮに対してスイッチ削減において非常に効果的であり、Ｎ＝６４で１−ＳＮに対する２−ＳＮも同様である。
【００４４】
したがって、６４個のＭ導体が２−ＳＮとその後に１−ＳＮを介して１６個の４入力論理セルにファン・インする、スケーラブル・ノンブロッキング・スイッチング・ネットワークを使用する回路階層の２レベルを説明した。６４個のＭ導体のうちの１６個は、４つのＣＬＳＴ４（図１の１００の１２５〜１２８）回路のそれぞれの１６個の出力に直接に接続され、任意の出力から１６個の論理セルのすべてへ無制限に接続できる。回路階層の第１レベルに、図９の１−ＳＮ９００として実施されたＭＴＸ２００と共に図１の回路ＣＬＳＴ４  １００が含まれ、ＣＬＳＴ４  １００は、図１に示されているように、４つの４入力論理セル１０〜４０と２つのフリップフロップ５０、６０を有する。回路階層の次に上位の第２レベルは、図１０に示された２−ＳＮ  ＭＴＸ１６  １０５０と共に４つのＣＬＳＴ４  １００回路を有する図１０のＣＬＳＴ１６  １０００回路であり、ネットワーク１０５０実装は、図１１Ａ、図１１Ｂ、図１２に示されている。ＣＬＳＴ１６  １０００では、１６個の出力１０６５、１０７５、１０８５、１０９５のそれぞれ（導体１０５６に直接に接続される）が、ＣＬＳＴ１６  １０００回路内のすべての論理セルへの無制限の接続性を有し、図１０の他の４８個のＭ導体１０５５は、回路階層の次のレベルを作る際にＣＬＳＴ１６  １０００のＮ導体として扱うことができる。図１０の４つのＣＬＳＴ４回路１０１０、１０２０、１０３０、１０４０のそれぞれの図１のＣＬＳＴ４  １００の１６個の出力１２５〜１２８は、１６個のＭ導体１０５６に直接に配線され、その出力を、さらに、ＳＮを介して、基本構成ブロックとしてＣＬＳＴ１６  １０００回路を使用して回路階層の次の第３レベルに接続することができ、４８個の他のＭ導体は、ＣＬＳＴ１６  １０００回路の同等のピンまたは入力導体であって、プログラム可能論理回路の継続する高い接続性をもたらす。
【００４５】
図１０のＣＳＬＴ  １０００回路は、４つの１−ＳＮをカスケード接続する２−ＳＮと、６４個のＭ導体１０５５、１０５６と、４つのグループ１０１０、１０２０、１０３０、１０４０に編成された１６個の４入力論理セルを使用し、さまざまなＳＮすなわち図１０のＳＮ１０５０と図１０のグループ１０１０〜１０４０ごとの図１のＳＮ  ２００の間の合計１２８０個のスイッチを使用するものとして図示されている。図１０のＣＬＳＴ  １０００回路は、６４個のＮ導体、ｋ（たとえば１６）個のＮ（たとえば４）導体と共に１−ＳＮを使用し、図９で述べた方法を使用する代替実施を有することができる。スイッチの個数は、本明細書で述べた分析を使用するとＭ×（Ｎ＋ｋ）＝１２８０である。この場合に、１−ＳＮ実装と図１０の実施形態の両方が、同一の個数のスイッチを有することがわかる。
【００４６】
どの実施がより適するかを判定する際の判断は、図１０の実施形態の導体のより多数の中間ステージを有する４入力ＭＵＸ実施または１６入力ＭＵＸと１−ＳＮ実施の導体のより少数の中間ステージがＳＲＡＭテクノロジの使用より好ましいかどうか、１つのスタイルがレイアウト実施でより好ましいかどうかなどのエンジニアリング考慮事項に依存する。上の分析に基づいて、スイッチの総数と回路階層の次のレベルで別のＳＮを使用して論理セルの複数のベース・アレイをつなぎ合わせることのオーバーヘッドが論理セルのより大きいサイズのベース・アレイを実施することを超えないようにするために、ＳＮを介して接続される論理セルの適度なサイズのベース・アレイを有することが好ましいことに留意することが重要である。ほとんどのプログラム可能論理回路で、ベース論理セル（ＳＮを有する論理セル・アレイの）は、通常、３入力または４入力のいずれかを有し、上で述べた図示の例から、ベース論理アレイ内の論理セルの個数ｋを小さい個数にしてはならず、むしろ、Ｎのサイズに応じて、ＳＮを相互接続ネットワークとして効率的に使用するために、ｋ×Ｎを適度なサイズ（たとえば、図１のＣＬＳＴ４  １００回路）にしなければならないと認めることが穏当である。
【００４７】
多数の実施形態と図示を使用して、さまざまなスケーラブル・ノンブロッキング・スイッチング・ネットワークを作ることの詳細な説明が、与えられ、さまざまな組合せで使用されて、プログラム可能論理回路の入力と出力の両方の相互接続が設けられた。テクノロジおよびエンジニアリングの考慮事項に応じて、メモリ制御の数を減らすためのＭＵＸの使用、スイッチ削減などを含むがこれに限定されない、このスケーラブル・ノンブロッキング・スイッチング・ネットワークの実施の変形を使用することができる。
【図面の簡単な説明】
【００４８】
【図１】スケーラブル・ノンブロッキング・スイッチング・ネットワーク（ＳＮ）を使用する４つの４入力論理セルおよび２つのフリップ・フロップを有する回路の実施形態を示す図である。
【図２】４つのＮ導体の４つの組にアクセスする１１個のＭ導体を有するステージ０スケーラブル・ノンブロッキング・スイッチング・ネットワーク（０−ＳＮ）を使用する回路の一実施形態を示す図である。
【図３】各０−ＳＮが２つのＮ導体の４つの組にアクセスする５つのＭ導体を有する、２つのステージ０スケーラブル・ノンブロッキング・スイッチング・ネットワークを使用する回路の一実施形態を示す図である。
【図４】４つの中間導体のＮ個の組を介して４つのＮ導体の４つの組にアクセスする１１個のＭ導体を有するステージ１スケーラブル・ノンブロッキング・スイッチング・ネットワーク（１−ＳＮ）を使用する回路の一実施形態を示す図である。
【図５】より少数の中間導体を介して４つのＮ導体の４つの組にアクセスする１２個のＭ導体を有するステージ１スケーラブル・ノンブロッキング・スイッチング・ネットワークを使用する回路の一実施形態を示す図である。
【図６】より強い接続性特性を有する４つのＮ導体の４つの組にアクセスする１２個のＭ導体を有するステージ１スケーラブル・ノンブロッキング・スイッチング・ネットワークを使用する回路の一実施形態を示す図である。
【図７】より少数のスイッチを有する削減されたステージ１スケーラブル・ノンブロッキング・スイッチング・ネットワークの一実施形態を示す図である。
【図８】より大きいサイズのステージ１スケーラブル・ノンブロッキング・スイッチング・ネットワークの一実施形態を示す図である。
【図９】１６個のＭ導体を有するのステージ１スケーラブル・ノンブロッキング・スイッチング・ネットワークの一実施形態を示す図である。
【図１０】それぞれが図９のスケーラブル・ノンブロッキング・スイッチング・ネットワークを使用する、図１の４つの論理回路を有する回路とステージ２スケーラブル・ノンブロッキング・スイッチング・ネットワーク（２−ＳＮ）との一実施形態を示すブロック図である。
【図１１Ａ】図１０のステージ２スケーラブル・ノンブロッキング・スイッチング・ネットワークのブロック図実施形態を示す図である。
【図１１Ｂ】図１１Ａのステージ２スケーラブル・ノンブロッキング・スイッチング・ネットワークの第１部分の一実施形態を示す図である。
【図１２】図１１Ａの２−ＳＮの第２部分を実施するステージ１スケーラブル・ノンブロッキング・スイッチング・ネットワークの一実施形態を示す図である。
【図１】
2007531461.tif 000003
【図２】
2007531461.tif 000004
【図３】
2007531461.tif 000005
【図４】
2007531461.tif 000006
【図５】
2007531461.tif 000007
【図６】
2007531461.tif 000008
【図７】
2007531461.tif 000009
【図８】
2007531461.tif 000010
【図９】
2007531461.tif 000011
【図１０】
2007531461.tif 000012
【図１１Ａ】
2007531461.tif 000013
【図１１Ｂ】
2007531461.tif 000014
【図１２】
2007531461.tif 000015
【国際調査報告】
2007531461.tif 000016