(57)【特許請求の範囲】
【請求項１】
集積回路の階層型ネットワークであって、前記階層型ネットワークは、
Ｍ個の出力及びＮ個の入力を有する複数の演算素子と、
スイッチのステージとして配置される複数のスイッチと、を備え、
前記複数の演算素子は、配線により第１のステージのスイッチに接続され、
前記第１のステージの前記スイッチは、配線により前記複数の演算素子と第２のステージのスイッチとに接続され、前記第２のステージの前記スイッチは、配線により前記第１のステージの前記スイッチに接続され、
少なくともＭ＋１個の隣接演算素子の各々は、前記第１のステージの１つのスイッチを通じて少なくとも２つの隣接演算素子に直接接続し、
全ての演算素子は、前記階層型ネットワーク内の他の全ての演算素子と接続するように構成可能である、
集積回路の階層型ネットワーク。
【請求項２】
複数の演算素子はＭ個の出力を有し、複数の演算素子はＭ＋１個の出力を有し、前記第１のステージの複数のスイッチはＭ個の入力を有し、前記第１のステージの複数のスイッチはＭ＋１個の入力を有する、
請求項１に記載の集積回路のための階層型ネットワーク。
【請求項３】
少なくとも２Ｍ−１個の演算素子はＭ個の出力を有し、前記第１のステージの少なくとも２Ｍ−１個のスイッチはＭ個の入力を有する、
請求項２に記載の集積回路のための階層型ネットワーク。
【請求項４】
２Ｍ−１個の演算素子はＭ個の出力を有し、残りの前記演算素子はＭ＋１個の出力を有する、
請求項３に記載の集積回路のための階層型ネットワーク。
【請求項５】
前記第１のステージの少なくとも２Ｍ−１個のスイッチはＭ−１個の出力を有し、前記第２のステージの少なくとも２Ｍ−１個のスイッチはＭ−１個の入力を有する、
請求項２に記載の集積回路のための階層型ネットワーク。
【請求項６】
前記第２のステージの少なくとも２Ｍ個のスイッチはＭ−１個の出力を有し、第３のステージの２Ｍ個のスイッチはＭ−１個の入力を有する、
請求項２に記載の集積回路のための階層型ネットワーク。
【請求項７】
前記第２のステージの２Ｍ個のスイッチはＭ−１個の出力を有し、前記第２のステージの残りのスイッチはＭ個の出力を有する、
請求項６に記載の集積回路のための階層型ネットワーク。
【請求項８】
前記配線は、双方向二重配線である、
請求項１に記載の集積回路のための階層型ネットワーク。
【請求項９】
集積回路の階層型ネットワークであって、前記階層型ネットワークは、
少なくともＭ個の出力及びＮ個の入力を有する複数の演算素子と、
スイッチのステージとして配置される複数のスイッチと、を備え、
前記複数の演算素子は、配線により第１のステージのスイッチに接続され、
前記第１のステージの前記スイッチは、配線により前記複数の演算素子と第２のステージのスイッチとに接続され、前記第２のステージの前記スイッチは、配線により前記第１のステージの前記スイッチに接続され、
複数の演算素子はＭ個の出力を有し、複数の演算素子はＭ＋１個の出力を有し、前記第１のステージの複数のスイッチはＭ個の入力を有し、前記第１のステージの複数のスイッチはＭ＋１個の入力を有し、
全ての演算素子は、前記階層型ネットワーク内の他の全ての演算素子と接続するように構成可能である、
集積回路の階層型ネットワーク。
【請求項１０】
集積回路のための階層型ネットワークの演算素子間でデータを送信するための方法であって、前記方法は、
前記階層型ネットワーク内で、演算素子から第１のステージのスイッチにデータを送信するステップを含み、前記階層型ネットワークは、
Ｍ個の出力及びＮ個の入力を有する複数の演算素子と、
スイッチのステージとして配置される複数のスイッチと、を有し、
前記複数の演算素子は、配線により前記第１のステージのスイッチに接続され、
前記第１のステージの前記スイッチは、配線により前記複数の演算素子と第２のステージのスイッチとに接続され、前記第２のステージの前記スイッチは、配線により前記第１のステージの前記スイッチに接続され、
前記第１のステージのスイッチから他の演算素子にデータを送信し、少なくともＭ＋１個の隣接演算素子の各々は、前記第１のステージの１つのスイッチを通じて少なくとも２つの隣接演算素子にデータを送信するように構成可能である、
集積回路のための階層型ネットワークの演算素子間でデータを送信するための方法。
【請求項１１】
複数の演算素子はＭ個の出力を有し、複数の演算素子はＭ＋１個の出力を有し、前記第１のステージの複数のスイッチはＭ個の入力を有し、前記第１のステージの複数のスイッチはＭ＋１個の入力を有する、
請求項１０に記載の方法。
【請求項１２】
少なくとも２Ｍ−１個の演算素子はＭ個の出力を有し、前記第１のステージの少なくとも２Ｍ−１個のスイッチはＭ個の入力を有する、
請求項１１に記載の方法。
【請求項１３】
２Ｍ−１個の演算素子はＭ個の出力を有し、残りの前記演算素子はＭ＋１個の出力を有する、
請求項１２に記載の方法。
【請求項１４】
前記第１のステージの少なくとも２Ｍ−１個のスイッチはＭ−１個の出力を有し、前記第２のステージの少なくとも２Ｍ−１個のスイッチはＭ−１個の入力を有する、
請求項１１に記載の方法。
【請求項１５】
前記第２のステージの少なくとも２Ｍ個のスイッチはＭ−１個の出力を有し、第３のステージの２Ｍ個のスイッチはＭ−１個の入力を有する、
請求項１１に記載の方法。
【請求項１６】
前記第２のステージの２Ｍ個のスイッチはＭ−１個の出力を有し、前記第２のステージの残りのスイッチはＭ個の出力を有する、
請求項１５に記載の方法。
【請求項１７】
前記配線は、双方向二重配線である、
請求項１０に記載の方法。
【請求項１８】
集積回路の階層型ネットワークであって、前記階層型ネットワークは、
Ｍ個の出力及びＮ個の入力を有する複数の演算素子と、
スイッチのステージとして配置される複数のスイッチと、を備え、
前記複数の演算素子は、配線により第１のステージのスイッチに接続され、
前記第１のステージの前記スイッチは、配線により前記複数の演算素子と第２のステージのスイッチとに接続され、前記第２のステージの前記スイッチは、配線により前記第１のステージの前記スイッチに接続され、
２Ｍ−１個の演算素子はＭ個の出力を有し、残りの前記演算素子はＭ＋１個の出力を有し、前記第１のステージの２Ｍ−１個のスイッチはＭ個の入力を有し、残りの前記スイッチはＭ＋１個の入力を有し、
前記第１のステージの２Ｍ−１個のスイッチはＭ−１個の出力を有し、前記第１のステージの残りのスイッチはＭ個の出力を有し、前記第２のステージの２Ｍ−１個のスイッチはＭ−１個の入力を有し、前記第２のステージの残りのスイッチはＭ個の入力を有し、
前記第２のステージの２Ｍ個のスイッチはＭ−１個の出力を有し、前記第２のステージの残りのスイッチはＭ個の出力を有し、
全ての演算素子は、前記階層型ネットワーク内の他の全ての演算素子と接続するように構成可能である、
集積回路の階層型ネットワーク。
【請求項１９】
Ｍ個の出力及びＮ個の入力を有する複数の演算素子と、
スイッチのステージとして配置される複数のスイッチと、を備え、
前記複数の演算素子は、配線により第１のステージのスイッチに接続され、
前記第１のステージの前記スイッチは、配線により前記複数の演算素子と第２のステージのスイッチとに接続され、前記第２のステージの前記スイッチは、配線により前記第１のステージの前記スイッチに接続され、
少なくともＭ＋１個の隣接演算素子の各々は、前記第１のステージの１つのスイッチを通じて少なくとも２つの隣接演算素子に直接接続し、
全ての演算素子は、フィールドプログラマブルゲートアレイ内の他の全ての演算素子と接続するように構成可能である、
フィールドプログラマブルゲートアレイ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プロセッサ、ステートマシン、ゲートアレイ、プログラマブルゲートアレイ、フィールドプログラマブルゲートアレイ（field programmable gate arrays (FPGAs)）、及びシステムオンチップ（system-on-chips (SOCs)）を含む（が、これに限定されない）ロジック及び／又は計算回路素子に対するスイッチネットワーク又はアーキテクチャを生成するための技術及びその回路素子に関する。例えば、本発明は、ＦＰＧＡ回路素子内で用いることができ、より具体的には、境界のない基数ネットワークを生成するためのシステム及び方法に用いることができる。以下では、本発明及び／又は実施形態は、ＦＰＧＡ回路素子という面において述べられるが、そのような議論において、本発明及び／又は実施形態は、プロセッサ、ステートマシン、ゲートアレイ、プログラマブルゲートアレイ、及びＳＯＣを含む（が、これに限定されない）ロジック及び／又は計算回路素子にも適用できる。簡潔にするために、開示する発明の各観点に関して、各ロジック及び／又は計算回路素子の全てについて別々の議論を行わないが、当業者にとってその応用性は、この開示に基づき明白である。
【背景技術】
【０００２】
ＦＰＧＡは、製造後に購入者や設計者が構成するように設計された集積回路である。ＦＰＧＡ構成は、ハードウェア記述言語（ＨＤＬ）を用いて指定されるのが一般的である。現代のＦＰＧＡは、ロジックゲート及びランダムアクセスメモリ（ＲＡＭ）ブロックの大きなリソースを有し、複雑なデジタル計算を実行する。ＦＰＧＡは、「コンフィギュラブルロジックブロック（configurable logic blocks (CLB)）」又は「ロジックアレイブロック（logic array blocks (LAB)）」と呼ばれるプログラマブルロジック部品と、ブロック同士が互いに通信できる再構成可能なインターコネクトの階層を含むのが典型的である。ロジックブロックは、複雑な組合せ機能、又は単に、ＡＮＤとＸＯＲのようなシンプルなロジックゲートを実行するように構成される。ほとんどのＦＰＧＡでは、ロジックブロックは、シンプルなフリップフロップやより完全なメモリのブロックとなりうるメモリ構成要素も有する。
【０００３】
応用回路は、十分なリソースが利用可能であるという条件で、ＦＰＧＡにマップ可能である。要求されるＣＬＢ／ＬＡＢ及びＩ／Ｏの数は、設計から容易に決定される一方で、必要とされる配線トラックの数は、同量のロジックを用いた設計同士間でさえも大幅に変化する。例えば、クロスバースイッチでは、同じゲート総数のシストリックアレイよりも非常に多くの配線が要求されるのが典型的である。未使用の配線トラック（すなわち、ワイヤ）は、何の利益ももたらすことなくその部分のコストを増やす（及び性能を低下させる）ので、ＦＰＧＡ製造者は、過不足なくトラックを提供しようと試み、ルックアップテーブル（Lookup tables (LUTs)）及びＩＯの見地に合う最も多くの設計を見つけ出すことができる。これは、レントの法則か既存の設計を用いた実験から導かれるような見積もりによって決定される。
【０００４】
一般的に、階層型ネットワークでは、情報は、繰り返し直接接続される様々な構成要素（例えば、ＣＥ、スイッチなど）間で、送信及び／又は受信される。典型的には、現代の階層型ネットワークは、２×２スイッチの２＊lｏｇ（Ｙ）個のステージによって互いに通信するＹ演算素子（computing elements (CEs)）を有するＢｅｎｅｓネットワークに基づいている。Ｂｅｎｅｓネットワークは、再編成可能で、非ブロックであり、ＣＥ間で輻輳のない通信をもたらす。ファットツリー（fat-tree）ネットワークは、各ステージで前後に通信を可能とすることで、２＊lｏｇ（Ｙ）個からlｏｇ（Ｙ）個にステージの数を低減できる。
【０００５】
２×２スイッチの５個のステージを有し、８個のＣＥを含むＢｅｎｅｓネットワークを図１Ａに示す。ネットワーク１００は、８つのＣＥ１０２を有し、それぞれ２個の入力１１０及び２個の出力１０４を有する。複数のＣＥは、より多くの入力及び出力ワイヤを加えることで単一のＣＥへと抽象化できる。例えば、ＣＥ７及びＣＥ８は、４個の出力を有するブロック１１２を形成するように結合できる。同様に、ＣＥ７及びＣＥ８は、４個の入力を有するブロック１１４を形成するように結合できる。この抽象化に従って、任意の単一配線Ｂｅｎｅｓネットワークは、図１Ｂに示すとおり、二重配線Ｂｅｎｅｓネットワークへと変換できる。ネットワーク１５０では、ステージごとのスイッチの数は、単一配線スイッチの代わりに二重配線スイッチを用いることで、ネットワーク１００に比べて半分に低減できる。例えば、図１Ａに示したスイッチ１１６及び１１８は、両方とも２個の入力及び２個の出力を有する単一配線スイッチである。しかしながら、図１Ｂの抽象化したスイッチ１５２は、４個の入力（２ペア）及び４個の出力（２ペア）を有する二重配線スイッチである。異なって構成されているが、ネットワーク１００及びネットワーク１５０の機能は、同一である。４入力のＣＥは、より一般的にＦＰＧＡに適用されるので、以降の本記載は、二重配線スイッチを有する４入力のＣＥを用いて示される。しかし、本記載が、上記の議論と同様の抽象化技術を用いて、任意の数の入力及び出力を有する様々なＣＥ、並びに任意の数のステージ及び入出力配線を有する様々なスイッチに適用可能であることは、当業者にとっては明白である。例として、５個のステージアートを有し、８個のＣＥを含むＢｅｎｅｓネットワークを図１Ｃに示す。ネットワーク１８０は、５個のステージを有し、８個のＣＥを含み、各ＣＥは、二重配線スイッチに利用する４入力、４出力を有する。
【０００６】
２×２スイッチの３状態を有し、８個のＣＥを備えるファットツリーネットワークを図２に示す。ネットワーク２００は、スイッチの両側に４個の双方向ワイヤを有する２×２スイッチ２０２を含む。スイッチの両側に４個の双方向ワイヤ２０４を有するように描いているが、同様に、スイッチの各側に８個の一方向ワイヤ２０６（４入力、４出力）としても実装できる。
【０００７】
２×２スイッチの４個のステージを有する１６個のＣＥの基数２ファットツリーネットワークを図３に示す。ネットワーク３００は、クロス配線を有し、ＣＥと様々なスイッチとの間の距離を計算できる。例えば、（クロス配線３０２のような）第１のステージのクロス配線は、Ｚ＝１（ステージに対応するＺ）として２Ｚ−１である、１の距離を有する。（クロス配線３０４のような）第２のステージのクロス配線は、Ｚ＝２として２Ｚ−１である、２の距離を有する。（クロス配線３０６のような）第３のステージのクロス配線は、Ｚ＝３として２Ｚ−１である、４の距離を有する。（クロス配線３０８のような）第４のステージのクロス配線は、Ｚ＝３として２Ｚ−１である、８の距離を有する。さらに、基数境界は、境界の各クロス配線がファットツリーネットワークを実現する中で横断するように（点線で示すとおりに）定義される。例えば、ＣＥとステージ１との間の配線では、クロス配線３０２は、基数境界３１０を横断する。同様に、ステージ１とステージ２との間のデータ送信では、クロス配線３０４は境界３１２を横断する。また、ステージ２とステージ３との間では、クロス配線３０６は、境界３１４を横断し、ステージ３とステージ４との間では、クロス配線３０８は、境界３１６を横断する。
【発明の概要】
【課題を解決するための手段】
【０００８】
発明の実施形態に従ったネットワークを生成する方法を含む（が、これに限定されない）境界のない階層型ネットワークを実装するためのシステム及び方法を開示する。１つの実施形態では、集積回路の階層型ネットワークは、前記階層型ネットワークが、Ｍ個の出力及びＮ個の入力を有する複数の演算素子と、スイッチのステージとして配置される複数のスイッチと、を備え、前記複数の演算素子は、配線により第１のステージのスイッチに接続され、前記第１のステージの前記スイッチは、配線により前記複数の演算素子と第２のステージのスイッチとに接続され、前記第２のステージの前記スイッチは、配線により前記第１のステージの前記スイッチに接続され、少なくともＭ＋１個の隣接演算素子は、ステージ１のスイッチを通じて少なくとも２つの最近接演算素子に接続でき、全ての演算素子は、前記階層型ネットワーク内の他の全ての演算素子と接続できる。
【図面の簡単な説明】
【０００９】
【図１Ａ】単一又は二重配線２×２スイッチの３又は５個のステージを有する４又は８個の演算素子（computing elements (CEs)）のＢｅｎｅｓネットワークを、ブロック図形成において示す。
【図１Ｂ】単一又は二重配線２×２スイッチの３又は５個のステージを有する４又は８個の演算素子（computing elements (CEs)）のＢｅｎｅｓネットワークを、ブロック図形成において示す。
【図１Ｃ】単一又は二重配線２×２スイッチの３又は５個のステージを有する４又は８個の演算素子（computing elements (CEs)）のＢｅｎｅｓネットワークを、ブロック図形成において示す。
【図２】２×２スイッチの３個のステージを有する８個のＣＥのＢｅｎｅｓネットワークに対するファットツリーネットワークを、ブロック図形成において示す。
【図３】２×２スイッチの４個のステージを有する１６個のＣＥの基数２ファットツリーネットワークを、ブロック図形成において示す。
【図４Ａ】発明の実施形態に従った、基数２ネットワークの基数３の境界のないネットワークアーキテクチャへの例示的な変換を、ブロック図形成において、様々なステージで示す。
【図４Ｂ】発明の実施形態に従った、基数２ネットワークの基数３の境界のないネットワークアーキテクチャへの例示的な変換を、ブロック図形成において、様々なステージで示す。
【図４Ｃ】発明の実施形態に従った、基数２ネットワークの基数３の境界のないネットワークアーキテクチャへの例示的な変換を、ブロック図形成において、様々なステージで示す。
【図４Ｄ】発明の実施形態に従った、基数２ネットワークの基数３の境界のないネットワークアーキテクチャへの例示的な変換を、ブロック図形成において、様々なステージで示す。
【図４Ｅ】発明の実施形態に従った、基数２ネットワークの基数３の境界のないネットワークアーキテクチャへの例示的な変換を、ブロック図形成において、様々なステージで示す。
【図４Ｆ】発明の実施形態に従った、基数２ネットワークの基数３の境界のないネットワークアーキテクチャへの例示的な変換を、ブロック図形成において、様々なステージで示す。
【図４Ｇ】発明の実施形態に従った、基数２ネットワークの基数３の境界のないネットワークアーキテクチャへの例示的な変換を、ブロック図形成において、様々なステージで示す。
【図４Ｈ】発明の実施形態に従った、基数２ネットワークの基数３の境界のないネットワークアーキテクチャへの例示的な変換を、ブロック図形成において、様々なステージで示す。
【図５Ａ】発明の実施形態に従った、境界のない基数３ネットワークの均一分散配線の例示的な実施形態を、ブロック図形成において、様々なステージで示す。
【図５Ｂ】発明の実施形態に従った、境界のない基数３ネットワークの均一分散配線の例示的な実施形態を、ブロック図形成において、様々なステージで示す。
【図５Ｃ】発明の実施形態に従った、境界のない基数３ネットワークの均一分散配線の例示的な実施形態を、ブロック図形成において、様々なステージで示す。
【図６】発明の実施形態に従った、第３のステージでプルーニングされたスイッチを有する例示的な境界のない基数３ネットワークを、ブロック図形成において示す。特に、この例示的な実施形態では、境界のない基数３ネットワークは、第３のステージと第４のステージとの間で短縮化したワイヤ長を有し、（プルーニングされていないネットワークに対して）５０％に低減した第４のステージのスイッチを有する。
【図７】発明の実施形態に従った、第４のステージでプルーニングされたスイッチを有する例示的な境界のない基数３ネットワークを、ブロック図形成において示す。
【図８】発明の実施形態に従った、第４のステージと第５のステージとの間でワイヤ長が短縮化し、第５のステージのスイッチが５０％に低減する、第４のステージでプルーニングされたスイッチを有する例示的な境界のない基数３ネットワークを、ブロック図形成において示す。
【図９Ａ】４×４スイッチの２個のステージを有する１６個のＣＥの基数４ファットツリーネットワークを、ブロック図形成において示す。
【図９Ｂ】４×４スイッチの２個のステージを有する１６個のＣＥの基数４ファットツリーネットワークを、ブロック図形成において示す。
【図１０】発明の実施形態に従った、第１のステージの基数５スイッチを使用した１６個のＣＥの例示的な境界のない基数４ファットツリーネットワークを、ブロック図形成において示す。
【図１１Ａ】発明の実施形態に従った、スイッチマトリックスマクロを使用した例示的な異種のマクロベースの設計を、ブロック図形成において示す。
【図１１Ｂ】発明の実施形態に従った、スイッチマトリックスマクロを使用した例示的な異種のマクロベースの設計を、ブロック図形成において示す。
【図１２Ａ】発明の実施形態に従った、スイッチマトリックス（switch matrix (SM)）マクロの１６個のＣＥ接続を表す例示的なＦＰＧＡ設計を、ブロック図形成において示す。
【図１２Ｂ】発明の実施形態に従った、スイッチマトリックス（switch matrix (SM)）マクロの１６個のＣＥ接続を表す例示的なＦＰＧＡ設計を、ブロック図形成において示す。
【図１３Ａ】発明の実施形態に従った、３つの主なタイプのＣＥ素子を有する例示的なＦＰＧＡ設計を、ブロック図形成において示す。
【図１３Ｂ】発明の実施形態に従った、３つの主なタイプのＣＥ素子を有する例示的なＦＰＧＡ設計を、ブロック図形成において示す。
【図１４】発明の実施形態に従った、４個の階層に分割された例示的な物理設計フローを示す。
【図１５Ａ】発明の実施形態に従った、最上位レベルのＣＥ図及びＳＭ図を有する例示的なＦＰＧＡ設計を示す。
【図１５Ｂ】発明の実施形態に従った、最上位レベルのＣＥ図及びＳＭ図を有する例示的なＦＰＧＡ設計を示す。
【図１６Ａ】発明の実施形態に従った、ＦＰＧＡ設計の例示的な最上位レベルのインターコネクトアーキテクチャを示す。
【図１６Ｂ】発明の実施形態に従った、ＦＰＧＡ設計の例示的な最上位レベルのインターコネクトアーキテクチャを示す。
【図１６Ｃ】発明の実施形態に従った、ＦＰＧＡ設計の例示的な最上位レベルのインターコネクトアーキテクチャを示す。
【図１７Ａ】未変換ネットワークの一部を示す。
【図１７Ｂ】未変換ネットワークの一部を示す。
【図１７Ｃ】未変換ネットワークの一部を示す。
【図１７Ｄ】未変換ネットワークの一部を示す。
【図１８Ａ】１つ以上の実施形態に従った、（例えば、ここで記載した技術を用いた変換後の）例示的な境界のない階層型ネットワークを、ブロック図形成において示す。
【図１８Ｂ】１つ以上の実施形態に従った、（例えば、ここで記載した技術を用いた変換後の）例示的な境界のない階層型ネットワークを、ブロック図形成において示す。
【図１８Ｃ】１つ以上の実施形態に従った、（例えば、ここで記載した技術を用いた変換後の）例示的な境界のない階層型ネットワークを、ブロック図形成において示す。
【図１８Ｄ】１つ以上の実施形態に従った、（例えば、ここで記載した技術を用いた変換後の）例示的な境界のない階層型ネットワークを、ブロック図形成において示す。
【図１９Ａ】１つ以上の実施形態に従った、（例えば、ここで記載した技術を用いた変換後の）例示的な境界のない階層型ネットワークを、ブロック図形成において示す。
【図１９Ｂ】１つ以上の実施形態に従った、（例えば、ここで記載した技術を用いた変換後の）例示的な境界のない階層型ネットワークを、ブロック図形成において示す。
【発明を実施するための形態】
【００１０】
以下の詳細な説明中では、添付した図面を参照する。これらの図面は、本発明の異なる観点を示し、適切な場合において、参照番号は、所定の参照を行うために利用される。明確に示したもの以外の構造、部品、及び／又は構成要素の様々な組合せが考えられ、これらは本発明の範囲内にあると理解される。
【００１１】
さらに、ここで記載及び図示する多くの発明がある。本発明は、任意の単一の観点やその実施形態にも限定されず、また、そのような観点及び／又は実施形態の任意の組合せ及び／又は置換にも限定されない。さらに、本発明の各観点及び／又はその実施形態は、単独で用いることができ、また、１つ以上の本発明の他の観点及び／又はその実施形態との組合せに用いることもできる。簡潔にするために、ある一定の置換及び組合せは、ここで別々に議論及び／又は図示しない。特に、「例示」としてここで記載する実施形態又は実装は、例えば、他の実施形態又は実装よりも好ましいか有利になるように解釈されるべきではなく、むしろ、少なくとも１つの実施形態は、例えば、本発明の「例示の」実施形態であることを反映又は指し示すものとする。
【００１２】
ここで図面を参照して、発明の実施形態に従ったネットワークを生成する方法を含む（が、これに限定されない）、境界のない階層型ネットワークを実装するためのシステム及び方法を示す。多くの実施形態では、階層型ネットワークは、Ｍ個の出力及びＮ個の入力を有する複数の演算素子（computing elements (CEs)）を含み、各ＣＥは、様々なステージに配置されたスイッチを用いてネットワーク内の他のＣＥと通信できる。いくつかの実施形態では、各ＣＥは、様々なタイプの配線（例えば、単一、二重、一方向、及び／又は双方向）を通じて第１のステージのスイッチに接続される。様々な実施形態では、第１のステージのスイッチは、ＣＥ及び第２のステージのスイッチに接続される。第２のステージのスイッチは、第１のステージのスイッチに接続され、多くの場合、第３のステージのスイッチにも接続される。多くの実施形態では、境界のない階層型ネットワークは、少なくともＭ＋１個の隣接ＣＥ（adjacent CE）を有し、これらは、ステージ１のスイッチを通じて少なくとも２つの最近接ＣＥに接続可能である。
【００１３】
発明のいくつかの実施形態では、基数３の境界のないアーキテクチャを生成する方法は、階層型ネットワークのステージを選択するステップを含み、選択されたステージの先に存在する少なくとも１つの中央２×２配線トラックを同定するステップを含む。方法は、同定した少なくとも１つの中央２×２配線トラックを、選択されたステージよりも前の配線チャネルに移動させるステップをさらに含む。中央２×２配線トラックの同定及び移動を繰り返すことで、１つ以上のステージは、基数３の境界のないネットワークに変換できる。ある実施形態では、本発明は、上述した変換に起因する不均一分散配線を処理するステップをさらに含む。いくつかの実施形態では、不均一分散配線は、インターコネクト配線を再分配することにより、及び／又は、スイッチの数を低減することにより修正される。以下でさらに議論するように、境界のないスイッチネットワークを創出するための技術は、任意の特定レベルの階層、演算素子の数、又は個々のスイッチ容量に限定されない。
【００１４】
様々な実施形態では、マクロベースの設計実装は、以下に述べる技術を実行するために、ＦＰＧＡの設計において利用される。多くの実施形態では、ＦＰＧＡ設計は、異種のインターコネクト及び演算素子を考慮してなされる。いくつかの実施形態では、階層型設計フローが利用される。さらなる実施形態では、最上位レベルのインターコネクトアーキテクチャが、設計プロセスにおいて可視化される。上述したとおり、発明の実施形態がＦＰＧＡ回路素子という面においてよく述べられるが、発明の実施形態は、プロセッサ、ステートマシン、ゲートアレイ、プログラマブルゲートアレイ、及びＳＯＣを含む（が、これに限定されない）、適用可能なロジック及び／又は計算回路素子を用いて解釈することもできる。簡潔にするために、開示する発明の各観点に関して、各ロジック及び／又は計算回路の全てについて別々の議論を行わないが、当業者にとってその応用性は、この開示に基づき明白である。
【００１５】
基数２ネットワークステージの境界のない基数３ネットワークへの変換
一般的に、ネットワークの異なるＣＥは、インターコネクトネットワークアーキテクチャを用いて、全体の計算、記憶、及び／又は通信機能に寄与する様々な機能を実行する。階層型ネットワークに対しては、互いに通信するために、信号が多くのステージを通過する必要があるので、１つ以上の基数境界を横断するＣＥ同士間のローカル配線は、非効率である。例えば、図３では、ＣＥ８及びＣＥ９は、最近接である（互いに隣接して位置する）が、互いに通信するために、信号は、ネットワーク階層の４個のステージを通過する必要がある。以下でさらに議論するように、基数２ネットワークは、ネットワークの各ステージを変換することで、境界のない基数３ネットワークに変換できる。同様に、より高次の基数ネットワークも、境界のない基数ネットワークに変換できる。基数ネットワークの１つ以上のステージを、境界のない基数ネットワーク及び境界のない基数ネットワーク実装の１つ以上のステージに生成又は変換するための、発明の様々な実施形態に従ったプロセスを、以下でさらに議論する。
【００１６】
バタフライ構造の同形変換による１６個のＣＥのファットツリーネットワークを図４Ａ及び４Ｂに示す。ネットワーク４００は、１６個のＣＥを有する。デモンストレーションのために、スイッチ４０１のＣＥ１３−１６及びそれらの最初の２個のステージを、図４Ｂで明らかにして示す。ＣＥ１５及び１６について、クロス配線４０２、４０３、４０４、４０５の組は、１の距離を有するステージ１のスイッチ４０６、４０７を用いて、ＣＥ１５とＣＥ１６との間の接続をもたらす。多くの実施形態では、そのようなクロス配線接続は、２個のスイッチ又はＣＥをつなぐ１組のワイヤ及びすぐ隣のステージのスイッチ又はＣＥを有する特定のステージのスイッチとして定義される。クロス配線の同様の組が、スイッチ４０８、４０９を用いて、ＣＥ１３と１４との間の接続に対して存在する（図示した例では、ＣＥとステージ１のスイッチとの間の全てのクロス配線接続は、１の距離を有する）。しかしながら、クロス配線接続が、ＣＥとスイッチ（又は、１つのステージのスイッチとすぐ隣のステージのスイッチ）との間で存在しないとき、いわゆる「ギャップ」が現れる。例えば、ギャップ４１０は、ＣＥ１４及びＣＥ１５とスイッチ４０９、４０６との間に現れる。言い換えると、ギャップは、１組のスイッチの間又は１組のＣＥ及びスイッチの間のクロス配線接続の欠如として定義される。ギャップの他の例を、参照４１１及び４１２によって指し示す。
【００１７】
多くの実施形態では、境界のない基数３変換は、より上位の階層（上流、すなわち、より後のステージ）から利用可能なクロス配線をサーチして、より下位の階層（下流）にこれらを移動させることで、より下位の階層でギャップを埋める。様々な実施形態では、４１０のようなギャップで始めて、サーチは上流に導かれ、適切な距離を有する１組のクロス配線（この例では、既存のステージ１のクロス配線は距離１を有するので、距離は１である）を見出す。そのようなクロス配線は上流にあり、ステージ１のスイッチ４０９、４０６及びステージ２のスイッチ４１３、４１８を接続する４１４、４１５、４１６、及び４１７（まとめて、「ネット」）として同定される。同定されたクロス配線は、下流にあるより下位の階層に対する距離基準を満たす、１の距離を有する。多くの実施形態では、これらのネットは、移動に備えるために現在のスイッチから切り離される。ＣＥとステージ１との間のギャップを埋めるための距離基準を満たす他のクロス配線が、（図４Ａ及び４Ｂに破線の円で印すとおり）同定される。そのようなクロス配線も、現在のスイッチから切り離され、より下位の階層に移動する。多くの実施形態では、クロス配線は、ステージ２と３との間のような他の階層に由来し、ギャップ４１２を埋めるために使用する４１９、４２０、４２１、及び４２２によって印される。基準を満たす他の組のクロス配線は、ステージ３と４との間に見出され、ギャップ４１１を埋めるために使用する４２３、４２４、４２５、及び４２６によって印される。多くの実施形態では、第１のステージ後の配線チャネルに対する中央２×２配線トラック（最短の配線トラック）は、下流に移動するために（図４Ａ及び４Ｂに破線の円で示すとおり）同定される。
【００１８】
第１のステージを基数３の境界のないネットワークに変換するために、同定した中央２×２配線トラックを第１のステージ下の配線チャネルに移動させた後の、発明の実施形態に従ったファットツリーネットワークを図４Ｃに示す。多くの実施形態では、１のインターコネクト長を有する２×２配線トラックが同定される。図４Ｄの挿入図４２７に示すとおり、２×２クロス配線４１４、４１５、４１６、及び４１７は切り離され、前の位置から移動し、ＣＥ１４、１５がスイッチ４０９、４０６と接続するように再結合し、ギャップ４１０を埋める。同様に、２×２クロス配線４１９、４２０、４２１、及び４２２は切り離され、前の位置から移動し、ギャップ４１２を埋めるように再結合する。また、２×２クロス配線４２３、４２４、４２５、及び４２６は切り離され、前の位置から移動し、ギャップ４１１を埋めるように移動及び再結合する。
【００１９】
第２のステージと第３のステージとの間、及び、第３のステージと第４のステージとの間で同定される中央２×２配線トラックを有する、発明の実施形態に従ったファットツリーネットワークを図４Ｅに示す。上述したとおりにクロス配線を移動した後、ステージ１とステージ２との間に残存するクロス配線４３０、４３１、４３２、及び４３３は３の距離を有する。多くの実施形態では、３の距離を有するクロス配線は、（図４Ｅに破線の円で示すとおり）同定され、切り離されて下流に移動する。そのようなクロス配線は、４４４、４４５、４４６、及び４４７によって符号を付したとおり、ステージ２と３との間から由来し、また、４４８、４４９、４５０、及び４５１によって符号を付したとおり、さらなる上流から由来する。
【００２０】
第２のステージを基数３の境界のないネットワークに変換するために、同定した中央２×２配線トラックを第１のステージと第２のステージとの間の配線チャネルに移動させた後の、発明の実施形態に従ったファットツリーネットワークを図４Ｆに示す。いくつかの実施形態では、３のインターコネクト長を有する２×２配線トラックが、上述のとおり、同定される。２×２クロス配線４４４、４４５、４４６、及び４４７は、切り離され、（前の位置から移動し、）ギャップ４５２を埋めるよう再結合する。同様に、２×２クロス配線４４８、４４９、４５０、及び４５１は、切り離され、（前の位置から移動し、）ギャップ４５３を埋めるよう再結合する。
【００２１】
第３のステージと第４のステージとの間で同定される中央２×２配線トラックを有する、発明の実施形態に従ったファットツリーネットワークを図４Ｇに示す。多くの実施形態では、ステージ２とステージ３との間のクロス配線は、符号４６０、４６１、４６２、及び４６３によって同定されるとおり、５の距離を有するか、または、符号４６４、４６５、４６６、及び４６７によって同定されるとおり、７の距離を有する。いくつかの実施形態では、（円で示す）５及び７の距離を有するクロス配線は、上流で同定され、切り離されて下流に移動する。図示したとおり、５の距離を有するクロス配線は、上流で４６８、４６９、４７０、及び４７１を有する。７の距離を有するクロス配線は、４７２、４７３、４７４、及び４７５を有する。
【００２２】
第３のステージを基数３の境界のないネットワークに変換するために、同定した中央２×２配線トラックを第２のステージと第３のステージとの間の配線チャネルに移動させた後の、発明の実施形態に従ったファットツリーネットワークを図４Ｈに示す。２×２クロス配線４６８、４６９、４７０、４７１、４７２、４７３、４７４、及び４７５は、上述したとおり、切り離され、前の位置から移動し、ギャップ４７６を埋めるよう再結合する。
【００２３】
基数２ネットワークの境界のない基数３ネットワークへの所定の変換について、図４Ａ−Ｈで上述したが、段階を踏んだ上述の変換は、最上位の任意の階層に続く。あるいは、変換は、任意の階層で停止し、従来の基数２ネットワークとして残存するより上位の階層を保持する。さらに、図４Ａ−Ｈは、基数３の境界のないアーキテクチャへの変換を示すが、同様の技術は、任意の数のＣＥに関して、より高次の基数に対し用いることができる。基数６アーキテクチャは、基数４ネットワークへの拡張として使用され、基数１２アーキテクチャは、基数８ネットワークへの拡張として使用される、などである。さらに、チャネルごとの配線の所定数（すなわち、２×２配線トラック）について、図４Ａ−Ｈで上述したが、所定の応用の要求に適した、チャネルの配線の任意の組合せを、発明の実施形態に従って利用できる。
【００２４】
上述したとおり、様々な実施形態において、ここで記載した技術は、本発明のスイッチネットワーク又はアーキテクチャを生成するために、ここで記載した１つ以上の機能又は操作を実行、遂行、及び／又は評価するよう（適切にプログラムされた）１つ以上のプロセッサを用いて実装できる。
【００２５】
再分配インターコネクト配線による規則的な配線パターン形成
従来のネットワークを境界のないネットワークに（例えば、基数２を境界のない基数３ネットワークに）変換する時、システム及び／又はネットワークは、不均一分散配線パターンを有する（すなわち、いくつかのスイッチは、他のスイッチよりも多くの配線を接続する必要がある）。第１のステージ上のワイヤが５０％にまで低減したので、不均一分散配線が生じる。これらの事情のもと、インターコネクト配線を再分配することで、規則的な（均一分散）配線システムを形成するのが好適である。
【００２６】
発明の実施形態に従った、インターコネクト配線を再分配することで形成した境界のない基数３ネットワークを、図５Ａ−Ｃに示す。図５Ｂの挿入図５０１は、再分配に対して未だ修正していないネットワークのセクションを示す（図４Ｈも参照のこと）。符号５０２及び５０４の基数境界を見ると、境界のないネットワークへの変換は、５０４のような新たな基数境界を創出する。多くの実施形態では、クロス配線は、（５０６、５０８、５１０、５１２のように）３の距離を有するが、基数境界を横断するために、２の距離（２Ｚ−１、Ｚはステージに対応し、ここではＺ＝２である）のみを必要とする。そのようなクロス配線は、図５Ｂの挿入図５０３に示すとおり、２の距離に短縮化される。ここで、クロス配線（「ネット」）５１８、５２０、５２２、及び５２４（短縮化して、スイッチ５１４及び５１６から切り離す前の先の５０６、５０８、５１０、及び５１２）のクラスタは、スイッチ５２６及び５２８に接続され、一方で、他端は、スイッチ５３０及び５３２に接続したままである。
【００２７】
挿入図５０３では、クロス配線は、スイッチ５２６、５２８、５３０、及び５３２に接続する５１８、５２０、５２２、及び５２４のようにペアになるが、いくつかのスイッチは、スイッチ５１４、５３４と５１６、５３６との間のようなギャップを有する。様々な実施形態では、クロス配線ペアは、単一のクロス配線に分けることができ、１つの組の単一のクロス配線は、挿入図５０５に示すとおり、隣接するネイバリングスイッチに移動する。挿入図５０５では、（挿入図５０３の）正式にペアとなるクロス配線５１８、５２０、５２２、及び５２４は、スイッチ５１４、５３４及び５１６、５３６を接続するよう、単一のクロス配線（５３８、５４０、５４２、５４４）に分割でき、クロス配線５４０及び５４４は、スイッチ５２６、５２８、５３０、及び５３２に接続したままである。
【００２８】
いくつかの実施形態では、同様の変換が、他の様々なステージに対して適用できる。図５Ｃの挿入図５０７は、未だ修正していないネットワークのセクションを示す（図４Ｈも参照のこと）。基数境界は、点線５５０によって符号を付される。この階層に対して、クロス配線の距離は、Ｚ＝４である２Ｚ−１により定義されるとおり、８である。この時、ネットは、スイッチ５５２、５５４、５５６、５５８、５６０、５６２、５６４、及び５６６から切り離され、８の距離に短縮化され、挿入図５０９に示すとおり、スイッチ５６８、５７０、５７２、５７４、５７６、５７８、５８０、及び５８２に接続される。クロス配線ペアは、単一のクロス配線に分けられ、１つの組のクロス配線は、挿入図５１１に示すとおり（図５Ａも参照のこと）、隣接する組のネイバリングスイッチに移動する。
【００２９】
様々な実施形態では、代替の方法が、クロス配線ペアを分け、そのブランチの１つを移動するように使用される。図５Ｃの挿入図５０９に示すとおり、スイッチ５９０、５９２、５９４、及び５９６は、（データが、他のブランチと同一の方向に進行するような垂直な軸に沿って）水平に配線をミラーリングすることによって移動でき、挿入図５１３に示すとおり、隣接する組のネイバリングスイッチに移動する。図５Ｃの挿入図５１３に示すとおり、多くの実施形態では、そのような方法により、５６０、５６２、５６４、５６６、５７６、５７８、５８０、及び５８２のようなスイッチは、任意のクロス配線接続にもはや接続できないので、プルーニングされ、ステージ４及びより高次のステージのスイッチの数を５０％に低減する（図７も参照のこと）。
【００３０】
スイッチの数のプルーニングによる規則的な配線パターン形成
上述したとおり、基数２を境界のない基数３ネットワークに変換することで、不均一分散配線を招く。規則的な配線パターンを形成するために、ある階層上で用いられるスイッチの数を低減するためのプルーニングプロセスを実装することが好適である。
【００３１】
第３と第４のステージとの間のインターコネクトに対するワイヤ長を短縮化し、第４のステージのスイッチを５０％に低減する、第３のステージでプルーニングされたスイッチを有する、発明の実施形態に従った境界のない基数３ネットワークを図６に示す。多くの実施形態では、第３のステージのスイッチは、ワイヤを二重ワイヤに変えることでプルーニングされ、第３のステージのスイッチの数を半分に低減する。いくつかの実施形態では、残存する第３のステージのスイッチが集中し、第３と第４のステージとの間のワイヤに対するインターコネクト長を短縮化して、第４のステージのスイッチの数を半分に低減する。ネットワーク６００は、上述の様々な技術を用いる境界のないネットワークへの変換を示す。ステージ１と２との間のクロス配線ペアは、上述した再分配方法を利用して、単一のクロス配線（例えば、６０２、６０４、６０６、及び６０８）に分けられる。ステージ２と３との間のクロス配線に対しても、同様の技術が適用できる。さらに、上述したとおりに短縮化する方法は、６１０、６１２、６１４、６１６、及び６１８、６２０、６２２、６２４のようなクロス配線ペアに適用でき、ステージ３及びより高次のステージのスイッチの数を５０％に低減する。プルー二ングにより、６２６及び６２８のようなステージ３と４との間のクロス配線は、基数境界６３０を横断するよう、４の距離のみを必要とするので、クロス配線は、短縮化され、４の距離で実装される。
【００３２】
発明の実施形態に従った、第４のステージでプルーニングされたスイッチを有する境界のない基数３ネットワークを図７に示す。多くの実施形態では、第４のステージのスイッチは、ワイヤの移動によってプルーニングされ、第４のステージのスイッチの数を半分に低減する。いくつかの実施形態では、第４のステージのスイッチは、ネットワークの半分にあり、より上位の階層のワイヤ長を低減する。ネットワーク７００は、上述の様々な技術を用いた、境界のないネットワークへの変換を示す。ステージ１と２との間のクロス配線ペアは、上述した再分配方法を利用して、単一のクロス配線（例えば、７０２、７０４、７０６、及び７０８）に分けられる。ステージ２と３との間のクロス配線に対しても、同様の技術が適用でき、単一のクロス配線７１０、７１２、７１４、及び７１６になる。ステージ３と４との間のクロス配線に対して、上述した方法が適用でき、ステージ４及びより高次のステージのスイッチの数を５０％に低減する。
【００３３】
第４のステージと第５のステージとの間のインターコネクトに対するワイヤ長を短縮化し、ステージ５のスイッチを５０％に低減する、第４のステージでプルーニングされたスイッチを有する、発明の実施形態に従った境界のない基数３ネットワークを図８に示す。多くの実施形態では、１６個のＣＥネットワークは、そのローカルネットワークの半分のみを占有する第４のステージのスイッチを各々有するので、第４と第５のステージとの間のインターコネクトに対するワイヤ長を低減し、ステージ５のスイッチの数を半分に低減する。ネットワーク８００では、図７のネットワーク７００は、８０２として抽象化され、８０４として（水平な軸に沿って）垂直にコピー及びミラーリングされる。構造８０２及び８０４は、ステージ４及び５のスイッチ並びに８０６、８０８、８１０、及び８１２のようなクロス配線ペアを通じて接続される。プルーニングにより、８０６、８０８、８１０、及び８１２のようなステージ４と５との間のクロス配線は、基数境界８１４を横断するよう、８の距離をカバーして実装されるので、クロス配線は、８の距離で実装される。
【００３４】
プルーニングによって規則的な配線パターンを形成するための所定の技術について、図５−８で上述したが、インターコネクト配線の再分配及び異なる階層の様々なステージに適用されるスイッチの数のプルーニングを含む、所定の応用の要求に適した任意の様々な技術を、発明の実施形態に従って利用できる。
【００３５】
境界のない基数４ネットワーク
上述したとおり、境界のないネットワークを創出するための技術は、任意の特定レベルの階層、演算素子の数、又は個々のスイッチ容量に限定されない。
【００３６】
４×４スイッチの２個のステージを有する１６個のＣＥの基数４ファットツリーネットワークを図９Ａに示す。ＣＥ及びスイッチは、ネットワーク９００内で明確にするために符号が付されている。同形変換は、ＣＥ及びスイッチを並べ替えることで、このネットワーク上で実行できるが、任意のネットを切り離して再結合せず、図９Ｂに示すとおりの変換となる。ネットワーク９２０は、９００と機能的に同等である。第１のステージの全てのクロス配線は、９２２、９２４、及び９２６の符号をそれぞれ付したとおり、１、２、又は３の距離を有する。他の全ての階層からの、１、２、又は３の距離を有するクロス配線は、クロス配線９２８、９３０、９３２、９３４、９３６、９３８、９４０、９４２、９４４、９４６、９４８、及び９５０のように同定される。この例では、選択されたクロス配線は、１又は３の距離のみを有し、２の距離を有さない。上述した基数２の方法論に従うと、これらのクロス配線は、移動に備えて、現在のスイッチから切り離される。
【００３７】
発明の実施形態に従った、第１のステージの基数５スイッチを用いた１６個のＣＥの境界のない基数４ファットツリーネットワークを図１０に示す。いくつかの実施形態では、境界のないネットワーク１０００は、１、２、又は３のインターコネクト距離を有する第１のステージと第２のステージとの間のワイヤを同定することによって構築される。多くの実施形態では、同定されたワイヤは、第１のステージを境界のないネットワークに変換するために、第１のステージ下で移動する。上述した基数２の方法論に従うと、例示のクロス配線９２８、９３０、９３２、９３４、９３６、９３８、９４０、９４２、９４４、９４６、９４８、及び９５０は、下流から移動し、ＣＥとステージ１のスイッチとの間を再接続し、図１０に示すとおりの境界のない基数４ファットツリーネットワークとなる。
【００３８】
マクロベースの設計実装
マクロベースの設計方法論は、発明の様々な実装に対して採用される。大きなＦＰＧＡをより小さく、同等のマクロへと分割することにより、ＦＰＧＡは、より容易に構築される。しかしながら、最適化されたインターコネクトアーキテクチャは、様々なサイズ及び形状のマクロになるのが典型的である。多くの実施形態では、異種のマクロベースの設計が、実装のために利用される。
【００３９】
発明の実施形態に従った、異種のマクロベースの設計を図１１Ａに示す。多くの実施形態では、スイッチマトリックスの各「行」は、１つの大きなスイッチマトリックス（switch matrix (SM)）マクロとして、まとめてグループ化され、そのような場合において、ＳＭＡ１１０２及びＳＭＢ１１０４のような、２つのタイプのより大きなＳＭマクロが構築される。
【００４０】
発明の実施形態に従った、異種のマクロベースの設計用のＳＭマクロを図１１Ｂに示す。多くの実施形態では、大きなＳＭマクロ構造（１１０２及び１１０４）は、図の単純化のためにマクロの内部ワイヤリング（１１０６及び１１０８）を取り除くように抽象化される。いくつかの実施形態では、入力／出力ワイヤは、マクロに対して示される。
【００４１】
マクロベースの設計実装のための所定の技術について、図１１Ａ−Ｂで上述したが、所定の応用の要求に適した、マクロベースの設計実装のための任意の様々な技術を、発明の実施形態に従って利用できる。
【００４２】
異種のインターコネクト及び演算素子を有するＦＰＧＡ設計
ＦＰＧＡは、異種のインターコネクト及びＣＥから成り立っている。マクロベースの設計を用いて、複数のＳＭマクロは、様々なＣＥをインターコネクトするために利用される。
【００４３】
発明の実施形態に従った、１つのＳＭマクロによって各々表わされる１６個のＣＥ接続を示すＦＰＧＡ設計を図１２Ａに示す。
【００４４】
発明の実施形態に従った、様々な入力／出力接続を必要とする異種のＣＥを表すＦＰＧＡ設計を図１２Ｂに示す。多くの実施形態では、インターコネクトアーキテクチャは、ＣＥの内部構造に依存しないので、ＦＰＧＡ設計は、典型的には、ＣＥからＳＭまでのＩＯの数に整合することのみを必要とする。いくつかの実施形態では、ＣＥ及びＳＭ設計の非干渉化は、より簡易な統合を可能にする。
【００４５】
異種のインターコネクト及びＣＥを有するＦＰＧＡ設計のための所定の技術について、図１２Ａ−Ｂで上述したが、任意の大きな数のＣＥを有するシステムを含んだ、所定の応用の要求に適した、異種のインターコネクト及びＣＥを有するＦＰＧＡ設計のための任意の様々な技術を、発明の実施形態に従って利用できる。
【００４６】
ＦＰＧＡ設計の演算素子考察
ＦＰＧＡは、様々なタイプ及び数のＣＥを有する。多くの実施形態では、ＦＰＧＡ設計は、４つの主なタイプのＣＥを有する。すなわち、高密度の再構成可能なロジックブロック（スライス（Slice）Ｌ）、シフトレジスタ及び分散メモリを有する高密度の再構成可能なロジックブロック（スライスＭ）、乗法のための高性能なデジタル信号プロセッサ（digital signal processor (DSP)）及び他のデジタル信号操作（スライスＤＳＰ）、並びに読み出し・書き込みアクセス用の１つ以上のポートを含み、再構成可能であるとは限らないブロックメモリ（スライスＢＲＡＭ）である。
【００４７】
ＳＭマクロが、より大きなマクロを形成するためにＣＥと統合される、発明の実施形態に従ったＦＰＧＡ設計を図１３Ａに示す。様々な実施形態では、Ｉ／Ｏの数により、スライスＬ１３０２は、６個のＳＭマクロを使用し、一方で、スライスＭ１３０４は、７個のＳＭマクロを使用する。スライスＤＳＰは、大きな数のＩ／Ｏで大型となり、多くの実施形態では、スライスＤＳＰ１３０６は、１１×３ＳＭアレイのような３３個のＳＭマクロを使用して実装され、スライスＤＳＰコアの上下に分割される。
【００４８】
発明の実施形態に従った、スライスＢＲＡＭのＦＰＧＡ設計を図１３Ｂに示す。いくつかの実施形態では、各ＳＭマクロは、手動で設計される。多くの実施形態では、スライスＢＲＡＭ１３０８は、９×４アレイのような３６個のＳＭマクロを使用する。様々な実施形態では、３６ＫｂＢＲＡＭは、約８個のＳＭマクロの幅を有し、ＢＲＡＭは、２ＢＲＡＭのＩＰ及び９×８アレイのような７２個のＳＭを用いて、二重ＢＲＡＭマクロ１３１０として統合される。
【００４９】
ＣＥの考察においてＦＰＧＡ設計のための所定の技術について、図１３Ａ−Ｂで上述したが、所定の応用の要求に適した、ＦＰＧＡ設計のための任意の様々な技術を、発明の実施形態に従って利用できる。さらに、発明の実施形態に従った、任意の大きな数のＣＥを有するインターコネクトアーキテクチャにおいて、同様の技術を利用できる。
【００５０】
階層型設計フローを用いたＦＰＧＡ設計の実装
設計フローは、集積回路の設計を実装する時に役立つ。発明の実施形態に従った物理設計フローを図１４に示す。多くの実施形態では、物理設計フローは、４個の階層に分割できる。第１の階層１４０２では、ＳＭマクロは、手動で設計される。第２の階層では、ＳＭマクロは、ＣＥと統合され、コンフィギュラブルロジックブロック（Configurable Logic Block (CLB)）として参照できる１つの大きなマクロ１４０４になる。第３の階層では、異種のＣＬＢは、タイル１４０６に統合される。第４の階層では、９個のタイルが、最上位レベルのチップ１４０８に統合される。
【００５１】
階層型設計フローを用いたＦＰＧＡ設計の実装のための所定の技術について、図１４で上述したが、所定の応用の要求に適した、ＦＰＧＡ設計を実装するための任意の様々な技術を、発明の実施形態に従って利用できる。
【００５２】
ＦＰＧＡ設計における最上位レベルのインターコネクトアーキテクチャ
典型的には、ＦＰＧＡは、異種のＳＭマクロとの異種のＣＥの統合である。発明の実施形態に従ったＦＰＧＡ設計の最上位レベルのＣＥ図を図１５Ａに示す。多くの実施形態では、チップ１５００は、９個の長方形タイルに分割でき、８個のタイルは、スライスＬ、Ｍ、ＤＳＰ、及びＢＲＡＭの組合せを含み、１つのタイルは、（６４−８ｋＦＦＴ及び１６−ｃｏｒｅＵＤＳＰとしてここで示した）所定のＣＥ１５０２を含む。
【００５３】
発明の実施形態に従ったＦＰＧＡ設計の最上位レベルのＳＭ図を図１５Ｂに示す。ここで、レベル１４の１５０２、レベル１３の１５０４、レベル１２の１５０６、レベル１１の１５０８、及びレベル１０の１５１０のように、（１４個のうちの）上位５個のインターコネクト階層のみを、簡素化のために示す。
【００５４】
発明の実施形態に従ったＦＰＧＡ設計の最上位レベルのインターコネクトアーキテクチャを図１６Ａ−Ｃに示す。多くの実施形態では、図１６Ａに示すとおり、最上位レベルのインターコネクトアーキテクチャ１６００は、２０４８０個のＳＭマクロ１６００を有し、７個の異種設計に分割され、（各ボックス１６０２によって示すとおりに）さらに分けられる。図１６Ｂに示すとおり、異種設計１６０２は、５１２個のより小さなＳＭマクロ１６０６を有し、各ＳＭマクロは、様々なＣＥをさらに有する。１つの可能なＳＭマクロの例を図１６Ｃに１６０６で示す。
【００５５】
ＦＰＧＡ設計において最上位レベルのインターコネクトアーキテクチャを用いるための所定の技術について、図１５Ａ−Ｂ及び１６で上述したが、所定の応用の要求に適した、ＦＰＧＡ設計における最上位レベルのインターコネクトアーキテクチャを用いるための任意の様々な技術を、発明の実施形態に従って利用できる。
【００５６】
境界のない階層型ネットワークの特性
境界のない階層型ネットワークは、Ｍ個の出力及びＮ個の入力を有する複数のＣＥを含み、各ＣＥは、先に上述したとおりの変換に基づきステージに配置したスイッチを用いて、他のＣＥと通信できる。多くの実施形態では、多くの異なる方法で、境界のない階層型ネットワークにたどり着ける。さらに、ＣＥについて、（特異な構成要素として）従来の意味で上述したが、様々な実施形態では、ＣＥ自身が、境界のないネットワークとなることが可能である。
【００５７】
発明の実施形態に従った未変換ネットワークを図１７Ａ−Ｃに示す。図１７Ａでは、ネットワーク１７００は、１組のステージ１のスイッチ用いてデータを転送するための双方向ワイヤを利用した（代わりに、一方向ワイヤも利用できる）６個のＣＥを有する。多くの実施形態では、ＣＥ及びスイッチは、Ｍ個の出力及びＮ個の入力を有する。例えば、ネットワーク１７００では、各ＣＥは、（ＣＥ１に対して１７０１、１７０２で同定される）２個の出力（Ｍ＝２）を有し、データを上流に送信する（各ステージの１つのスイッチは、２個の入力を有し、ＣＥから送信されたデータを受信する）。同様に、ネットワーク１７００では、各ＣＥは、（ＣＥ１に対して１７０３及び１７０４で同定される）２個の入力（Ｎ＝２）を有し、下流に向かって、ステージ１のスイッチからのデータを受信する。さらに、ネットワーク１７００の各ＣＥは、ブランチごとに特定の数の配線（Ｗ）を有するように記述でき、ブランチごとの配線の数は、出力又は入力の定義に影響しない。発明の実施形態に従った、ブランチごとに２個の配線（Ｗ＝２）を有するネットワークの例を図１７Ｂに示す。ネットワーク１７１０は、各ブランチ（１７１１、１７１２、１７１３、及び１７１４）が２つの配線（すなわち、二重ワイヤ）を有するように構築される。多くの実施形態では、各ブランチは、異なる値のＷを有する。配線の数は、ここでは２であるが、１７０１の各ＣＥは、２個の出力（Ｍ＝２）及び２個の入力（Ｎ＝２）をなおも有する。ブランチごとに１個の配線（Ｗ＝１）を有するが、１個の出力ブランチ（Ｍ＝１）及び２個の入力ブランチ（Ｎ＝２）のみを有する、発明の実施形態に従ったネットワークの例を、ネットワーク１７２０として図１７Ｃに示す。ブランチごとに１個の配線（Ｗ＝１）を有するが、４個の出力ブランチ（Ｍ＝４）及び４個の入力ブランチ（Ｎ＝４）を有する、発明の実施形態に従ったネットワークの例を、ネットワーク１７３０として図１７Ｄに示す。
【００５８】
いくつかの実施形態では、ボックスは、Ｍ＋１個のＣＥ（及びＭ＋１個の対応するスイッチ）のサイズを有するように定義される。未変換ネットワークでは、サイズＭ＋１個の任意のボックスは、ステージ１のスイッチを使用して互いに直接通信できない、少なくとも２つの最近接ＣＥ（直接隣接するＣＥ）を有する。例えば、１７００ネットワークでは、ボックス１７０５は、ＣＥ１、ＣＥ２、及びＣＥ３を有するように描かれ、ＣＥ２の１７０６及びＣＥ３の１７０７は、ステージ１のスイッチを使用して互いに直接通信できない。同様に、ネットワーク１７１０では、ボックス１７１５は、ＣＥ２、３、及び４を有し、ＣＥ２の１７１６は、ステージ１のスイッチを使用してＣＥ３の１７１７と直接通信できない。さらなる例は、ネットワーク１７２０を有し、ボックス１７２１は、ＣＥ３、４、及び５を有し、ＣＥ４の１７２２は、ステージ１のスイッチを使用してＣＥ５の１７２３と直接通信できない。さらに、ネットワーク１７３０は、ＣＥ１、２、３、４、及び５を有するボックス１７３１を定義でき、ＣＥ４の１７３２及びＣＥ５の１７３３は、ステージ１のスイッチを使用して互いに直接通信できない。
【００５９】
それに対して、上述したとおりの変換方法を利用した境界のないネットワークでは、ボックスは、ボックスの各ＣＥがステージの１つのスイッチを通じて最近接ＣＥと通信できるように定義される。発明の実施形態に従った、境界のないネットワークを図１８Ａ−Ｄに示す。多くの実施形態では、様々なＣＥは、１つ以上の変換により付加的な入力及び／又は出力を有する。他のＣＥ、特に、（ネットワーク１８４０の）１８４１及び１８４２、（ネットワーク１８５０の）１８５１及び１８５２、（ネットワーク１８６０の）１８６１及び１８６２、（ネットワーク１８７０の）１８７６、１８７７、１８７８、及び１８７９のようなネットワークの端付近のＣＥは、同数の入力及び出力を維持する（すなわち、ブランチは追加されない）のが典型的である。上述したとおり、変換したネットワークは、ボックスの定義を可能とし、ボックスの全てのＣＥは、ステージの１つのスイッチを通じて任意の最近接ＣＥと通信できる。例えば、ネットワーク１８４０では、ボックス１８４３は、ＣＥ１、２、３、及び４を有し、各ＣＥは、ステージ１のスイッチを通じて最近接ＣＥと直接通信できる。同様に、ネットワーク１８５０では、ボックス１８５３は、ＣＥ２、３、４、及び５を有し、各ＣＥは、ステージ１のスイッチを通じて最近接ＣＥと直接通信できる。また、ネットワーク１８６０では、ボックス１８６３は、ＣＥ３、４、５、及び６を有するよう定義され、各ＣＥは、ステージ１のスイッチを通じて最近接ＣＥと直接通信できる。さらに、ネットワーク１８７０では、ボックス１８７１は、ＣＥ１、２、３、４、５、及び６を有するよう定義され、各ＣＥは、ステージ１のスイッチを通じて最近接ＣＥと通信できる。
【００６０】
さらに、入力及び／又は出力が３個よりも大きい（ネットワーク１８７０のような）ネットワークでは、いくつかのネット（１８７２、１８７３）は必須であり、これによってＣＥ４及びＣＥ５を５個の入力を有するように変換する。しかし、１８７４及び１８７５のようないくつかのネットは任意であり、５個の入力及び出力に変換する選択肢をＣＥ３及びＣＥ６に与える。
【００６１】
多くの実施形態では、同一のネットワークは、他の全ての階層型ステージに適用できる。図１９Ａ−Ｂは、ステージ１とステージ２との間の階層型ネットワークの一部を示す。従来の未変換ネットワークは、１９８０の符号を付して、左に示され、各ステージの１つのスイッチは、２個の出力（Ｍ＝２）及び２個の入力（Ｎ＝２）を有し、二重ワイヤ（Ｗ＝２）を使用する。変換ネットワークは、１９９０の符号を付して、右に示される。この図では、ステージ１及びステージ２のスイッチを同一のＳＭマクロ内で直接接続する、１９９１の符号を付したローカル配線は二重ワイヤ（Ｗ＝２）を有し、一方で、ステージ２のスイッチに同一のＳＭマクロ外で接続する、１９９２及び１９９３の符号を付したブランチは単一ワイヤ（Ｗ＝１）を有する。このアプローチにより、ワイヤ総数を増大させずに、スイッチの基数Ｒが増大する（Ｒは、Ｎ又はＭのうち大きい方であり、この例では、Ｒは、２から３に増大する）。境界のない階層型ネットワークの所定の特性について、図１７−１９Ｂで上述したが、境界のない階層型ネットワークの任意の様々な特性は、発明の実施形態に従って、所定の応用の要求に適したとおりに定義できる。
【００６２】
さらに、ここで記載及び／又は図示した独創的なネットワーク又はアーキテクチャを生成及び／又はインスタンス生成するために用いるスイッチ及びマルチプレクサは、現在知られているか、今後開発される任意のタイプのスイッチ及びマルチプレクサを用いて実装される。例えば、１つの実施形態では、従来タイプのスイッチ及びマルチプレクサは、独創的なネットワーク又はアーキテクチャを実装するために用いられる。他の実施形態では、参照によってここで全体に盛り込まれる、２０１３年３月１５日に出願した、「ＦＰＧＡインターコネクトにおける細粒度型パワーゲーティング」というタイトルの米国特許仮出願シリアル番号６１／７９１，２４３に記載及び図示された１つ以上のスイッチ及びマルチプレクサを用いる。例えば、１つの実施形態では、ここで記載及び／又は図示した独創的なネットワーク又はアーキテクチャは、独創的なネットワーク又はアーキテクチャを形成するために、米国特許仮出願番号６１／７９１，２４３（２４３米国特許仮出願）に記載及び図示された１つ以上の独創的なスイッチ及びマルチプレクサ（そのようなスイッチ及びマルチプレクサと一体となった制御信号及びバッファを含む）を有する。特に、２４３米国特許仮出願で記載及び図示されたスイッチ及びマルチプレクサの全ての置換及び組合せは、ネットワーク又はアーキテクチャを生成及びインスタンス生成するために用いられる。すなわち、ここで図示したスイッチ及びマルチプレクサブロックは、従来のスイッチ及びマルチプレクサ、並びに／又は、２４３米国特許仮出願に記載及び図示された独創的なスイッチ及びマルチプレクサ、並びに／又は、未だ開発されていないスイッチ及びマルチプレクサの代表であり、そのような全ての組合せは、本発明の範囲内にあるものとする。
【００６３】
上述したとおり、ここで記載した技術は、本発明のスイッチネットワーク又はアーキテクチャを生成するために、ここで記載した１つ以上の機能又は操作を実行、遂行、及び／又は評価するよう（適切にプログラムされた）１つ以上のプロセッサを用いて実装できる。
【００６４】
特に、ここで開示した様々な回路及び回路素子は、コンピュータ支援設計ツールを用いて記述でき、例えば、動作、レジスタ転送、ロジック部品、トランジスタ、レイアウトジオメトリ、及び／又は他の特徴に関する、様々なコンピュータ可読媒体で具現化されるデータ及び／又は命令として表現される（又は、代表される）点にさらに注意すべきである。そのような回路表現が実装されるファイルと他のオブジェクトのフォーマットは、Ｃ、ヴェリログ、及びＨＬＤＬのような動作言語をサポートするフォーマット、ＲＴＬのようなレジスタレベルの記述言語をサポートするフォーマット、並びにＧＤＳII、ＧＤＳIII、ＧＤＳIＶ、ＣＩＦ、ＭＥＢＥＳ及び任意の他の適切なフォーマットと言語のようなジオメトリ記述言語をサポートするフォーマットを含むが、これに限定されない。そのようにフォーマットされたデータ及び／又は命令が具現化されるコンピュータ可読媒体は、様々な形態（例えば、光学、磁気、又は半導体ストレージ媒体）の不揮発性ストレージ媒体、及び、そのようにフォーマットされたデータ及び／又は命令を、無線、光学、若しくは有線信号送信媒体、又はこれらの任意の組合せを通じて転送するために用いる搬送波を含むが、これに限定されない。そのようにフォーマットされたデータ及び／又は命令の搬送波による転送例は、１つ以上のデータ転送プロトコル（例えば、ＨＴＴＰ、ＦＴＰ、ＳＭＴＰ、など）による、インターネット及び／又は他のコンピュータネットワークにわたった転送（アップロード、ダウンロード、Ｅメール、など）を含むが、これに限定されない。本発明は、ここで述べた回路素子の表現、及び／又はこれにより実装される技術も対象とし、これ自体、本発明の範囲内にあるものとする。
【００６５】
実際、１つ以上のコンピュータ可読媒体によるコンピュータシステム内で受信するとき、上記の回路のそのようなデータ及び／又は命令に基づく表現は、ネットリスト生成プログラム、配置配線プログラムなどを限度なく含む、１つ以上の他のコンピュータプログラムの実行と合わせて、コンピュータシステム内で処理エンティティ（例えば、１つ以上のプロセッサ）により処理され、そのような回路の物理的発現の表現又はイメージを生成する。その後で、そのような表現又はイメージは、例えば、デバイス製造工程で回路の様々な部品を形成するために使用する１つ以上のマスクの生成を可能とすることにより、デバイス製造に使用される。
【００６６】
さらに、ここで開示した様々な回路及び回路素子、並びに技術は、コンピュータ支援設計、シミュレーション、及び／又はテストツールを用いて、シミュレーション及び命令に基づくシミュレーション表現により表される。ここで実装した独創的なプロセス又は技術を含み、及び／又は、そのような独創的なネットワーク又はアーキテクチャ並びにロジック及び／又は計算回路素子による、ロジック及び／又は計算回路素子のための独創的なネットワークのシミュレーションは、コンピュータシステムによって実行され、そのような回路素子の特徴及び操作、並びにこれによって実装される技術が、コンピュータシステムによりシミュレーション、模倣、複製、分析、及び／又は予測される。本発明は、独創的なネットワークのそのようなシミュレーション及びテスト、並びに／又は、ロジック及び／又は計算回路素子のためのアーキテクチャ、並びに／又は、ここで実装した独創的な技術、並びに／又は、そのようなネットワーク、ロジック回路素子、及び／又は計算回路素子によって実装される技術も対象とし、それ自体、本発明の範囲内にあるものとする。そのようなシミュレーション及び／又はテストツールに対応するコンピュータ可読媒体及びデータもまた、本発明の範囲内にあるものとする。
【００６７】
本発明について、ある所定の観点で述べたが、多くの付加的な修正及びバリエーションは、当業者にとっては明白であろう。従って、本発明は、本発明の範囲及び精神から離れることなく明確に記載される場合を除いても、実施可能であると理解すべきである。従って、本発明の実施形態は、全ての点において、例示的であり、限定的ではないと考えるべきである。すなわち、発明の範囲は、例示した実施形態によってではなく、添付した請求項及びその同等物によって決定されるべきである。
【００６８】
特に、請求項において、「集積回路」という言葉は、プロセッサ、ステートマシン、ゲートアレイ、プログラマブルゲートアレイ、フィールドプログラマブルゲートアレイ、及びシステムオンチップを含む（が、これに限定されない）集積ロジック及び／若しくは計算回路、又は、本発明の１つ以上の階層型ネットワークを用いた任意の他の集積回路、及び／若しくは、本発明の１つ以上の方法に従って設計／製造される任意の他の集積回路を意味する。
【図１Ａ】
0006518648.tif 000002
【図１Ｂ】
0006518648.tif 000003
【図１Ｃ】
0006518648.tif 000004
【図２】
0006518648.tif 000005
【図３】
0006518648.tif 000006
【図４Ａ】
0006518648.tif 000007
【図４Ｂ】
0006518648.tif 000008
【図４Ｃ】
0006518648.tif 000009
【図４Ｄ】
0006518648.tif 000010
【図４Ｅ】
0006518648.tif 000011
【図４Ｆ】
0006518648.tif 000012
【図４Ｇ】
0006518648.tif 000013
【図４Ｈ】
0006518648.tif 000014
【図５Ａ】
0006518648.tif 000015
【図５Ｂ】
0006518648.tif 000016
【図５Ｃ】
0006518648.tif 000017
【図６】
0006518648.tif 000018
【図７】
0006518648.tif 000019
【図８】
0006518648.tif 000020
【図９Ａ】
0006518648.tif 000021
【図９Ｂ】
0006518648.tif 000022
【図１０】
0006518648.tif 000023
【図１１Ａ】
0006518648.tif 000024
【図１１Ｂ】
0006518648.tif 000025
【図１２Ａ】
0006518648.tif 000026
【図１２Ｂ】
0006518648.tif 000027
【図１３Ａ】
0006518648.tif 000028
【図１３Ｂ】
0006518648.tif 000029
【図１４】
0006518648.tif 000030
【図１５Ａ】
0006518648.tif 000031
【図１５Ｂ】
0006518648.tif 000032
【図１６Ａ】
0006518648.tif 000033
【図１６Ｂ】
0006518648.tif 000034
【図１６Ｃ】
0006518648.tif 000035
【図１７Ａ】
0006518648.tif 000036
【図１７Ｂ】
0006518648.tif 000037
【図１７Ｃ】
0006518648.tif 000038
【図１７Ｄ】
0006518648.tif 000039
【図１８Ａ】
0006518648.tif 000040
【図１８Ｂ】
0006518648.tif 000041
【図１８Ｃ】
0006518648.tif 000042
【図１８Ｄ】
0006518648.tif 000043
【図１９Ａ】
0006518648.tif 000044
【図１９Ｂ】
0006518648.tif 000045