(57)【要約】【課題】  本発明は、相互接続資源のより効率的な利用を可能にする設計手順を提供する。【解決手段】  カスタム回路デバイス（１００）の設計方法は、仮想ワイヤによって接続されたサブシステムの高水準アーキテクチャから開始する。第１のステップは、サブシステムをタイル（１０２）上に空間配置することを含む。第２のステップは、相互接続アーキテクチャ（１０４）上に、タイルの境界を横切る仮想ワイヤを配線することを含む。相互接続アーキテクチャはスイッチおよびレジスタを備える。スイッチのいくつかが、第１のタイル上に配置された第１のサブシステムから第２のタイル上に配置された第２のサブシステムへ信号を転送する。レジスタの少なくとも２つが、反復期間以下の時間間隔で信号を連続してラッチする。第３のステップは、クロックサイクルに従ってタスクをスケジューリングすることを含む。【選択図】図１
2005135411.tif 000002
【特許請求の範囲】
【請求項１】
仮想ワイヤによって接続されたサブシステムの高水準アーキテクチャから開始する、カスタム回路デバイス（１００）を設計する方法であって、
前記サブシステムをタイル（１０２）上に空間配置するステップと、
スイッチのいくつかが、第１のタイル上に配置された第１のサブシステムから第２のタイル上に配置された第２のサブシステムへ信号を転送し、さらに、レジスタの少なくとも２つが、反復期間以下の時間間隔で前記信号を連続してラッチするような該スイッチおよび該レジスタを備える、相互接続アーキテクチャ（１０４）上に、前記タイル（１０２）の境界を横切る前記仮想ワイヤを配線するステップと、
クロックサイクルに従ってタスクをスケジューリングするステップと、
を含む方法。
【請求項２】
前記反復期間は、クロックサイクル期間を含む、
請求項１に記載のカスタム回路デバイスを設計する方法。
【請求項３】
前記反復期間は、複数のクロックサイクル期間を含む、
請求項１に記載のカスタム回路デバイスを設計する方法。
【請求項４】
前記サブシステムと、前記タイルの前記境界を横切らない前記仮想ワイヤを前記タイル（１０２）の回路にマッピングするステップ、
をさらに含む請求項１に記載のカスタム回路デバイスを設計する方法。
【請求項５】
前記サブシステムを前記タイル（１０２）上に空間配置する前記ステップは、異なるタイル上に配置された前記サブシステム間の通信の最適化を追求する、
請求項１に記載のカスタム回路デバイスを設計する方法。
【請求項６】
前記タスクをスケジューリングする前記ステップは、前記タイル（１０２）間の通信によって引き起こされる待ち時間を考慮することを含む、
請求項１に記載のカスタム回路デバイスを設計する方法。
【請求項７】
前記タスクをスケジューリングする前記ステップは、前記相互接続アーキテクチャ（１０４）の通信パスセグメントがその容量を超えないことを保証することを含む、
請求項１に記載のカスタム回路デバイスを設計する方法。
【請求項８】
前記タスクをスケジューリングする前記ステップは、サブシステムのタスクおよび前記タイル間の通信を含むオペレーションの全体のスケジュールを生成することを含む、
請求項１に記載のカスタム回路デバイスを設計する方法。
【請求項９】
前記カスタム回路デバイスは、特定用途向け集積回路を含む、
請求項１に記載のカスタム回路デバイスを設計する方法。
【請求項１０】
前記カスタム回路デバイスは、再構成可能なデバイスを含む、
請求項１に記載のカスタム回路デバイスを設計する方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、集積回路デバイスの設計分野に関する。詳細には、本発明は、設計手順が相互接続資源を効率的に利用する集積回路デバイスの設計分野に関する。
【０００２】
［関連出願］
この出願は、２００３年１０月３０日に出願された米国特許出願第１０／６９８，２７１号に関係する。
【背景技術】
【０００３】
ＶＬＳＩ（超大規模集積）デバイスには、マイクロプロセッサおよびカスタム回路デバイスが含まれる。カスタム回路デバイスには、ＡＳＩＣ（特定用途向け集積回路）およびプログラマブルデバイスが含まれる。一般に、ＡＳＩＣは、特定の実施態様を実行するように設計され製造される。プログラマブルデバイスには、再構成不能なデバイスおよび再構成可能なデバイスが含まれる。再構成不能なデバイスは、ヒューズ技術またはアンチヒューズ技術を使用して、さまざまな論理コンポーネントと回路との間の恒久的な相互接続を形成するものである。再構成可能なデバイスは、プログラマブルスイッチで実施される再構成可能な相互接続を使用して、論理コンポーネントと回路との間の信号を転送するものである。再構成可能なデバイスには、ＰＬＤ（プログラマブル論理デバイス）、ＦＰＧＡ（フィールドプログラマブルゲートアレイ）、および再構成可能なＤＳＰ（デジタル信号処理）デバイスが含まれる。
【０００４】
ＦＰＧＡは、一般に、再構成可能なデバイスの例示である。ＦＰＧＡは、再構成可能なスイッチを含む相互接続ワイヤによって接続された論理セルを含む。これらの相互接続ワイヤおよび再構成可能なスイッチによって、論理セルのいずれの２つの間でもデータを転送することが可能になる。
【０００５】
現在のＶＬＳＩ技術では、データ通信は、デバイスのコストおよび性能に重大な影響を与える。データ通信は、相互接続ワイヤ等のハードウェア資源を使用し、デバイスのコストに影響する。データ通信の遅延は、デバイスの性能に影響する。ＶＬＳＩ技術が、機能を縮小して、デバイス密度を増加させ続けるに伴い、デバイスのコストおよび性能に対する影響は増大することになる。例えば、トランジスタが多くなるほど、相互接続ワイヤも多くなり、コストを増加させることになる。トランジスタが小さくなるほど、トランジスタの詰め込み密度は大きくなり、これにより、相互接続ワイヤの断面サイズを削減させることが必要となり、信号が相互接続ワイヤを横断する際の伝送遅延が増加することになる。トランジスタを高速化すると、クロックサイクル速度も速くなり、データ通信に関連した遅延の影響が増大することになる。
【０００６】
コストおよび性能に対するデータ通信の影響は、特に、ＦＰＧＡ等の再構成可能なデバイスにとって重大である。ＦＰＧＡで実施されるカスタム回路デバイスでは、信号が相互接続ワイヤおよび再構成可能スイッチを横断する時間は、クロックサイクル期間の大きな部分を占めることが多い。さらに、相互接続資源を使い尽くすことは、再構成可能なデバイスの論理資源の使用できる部分を制約することが多い共通の問題である。再構成可能なデバイスの場合、相互接続資源をより効率的に使用できる方が有利となる。
【０００７】
ＡＳＩＣや再構成可能なデバイス等のカスタム回路デバイスの従来の設計フローは、段階間の抽象化を用いて段階的に行われている。共通の設計手法は、ＶｅｒｉｌｏｇやＶＨＤＬ等の高水準記述言語でレジスタ転送レベル（ＲＴＬ）設計の仕様を定めることである。ＲＴＬ設計は、次に、ハードウェア合成ツールに提供され、その後、配置／配線ツールに提供される。このような設計フローは、ＡＳＩＣおよびＦＰＧＡの双方に共通である。ＲＴＬ設計は、クロックサイクルレベルでハードウェアのオペレーションの仕様を定める。すなわち、各クロックサイクルで起こるべきことの仕様を定める。設計フローのその後のステップは、各サイクルで起こることの変更にほとんど柔軟性がなく、また、クロックサイクルの追加挿入に対してもほとんど柔軟性がない。このようなあらゆる調整は、可能であるとしても、非常に局所的であり、分岐してその後合流する異なるパスの（クロックサイクル数での）相対的な待ち時間を維持する等、非常に厳しい制限の下で行わなければならない。
【０００８】
従来の設計フローが、配置および配線に到達するまでには、抽象化のレベルは、非常に低くされている。この時点で、データ搬送要求条件が、共有されていないワイヤのレベルで表される。共有されていないワイヤは、配置／配線ツールによって配線される。データ転送およびデバイスのオペレーションのスケジューリングに関する決定は、ＲＴＬ設計では凍結される。従来の設計フローでは、これらの決定を行う際に、正確な配置情報を利用することはできない。さらに、デバイスのオペレーションのスケジューリングが、ＲＴＬ設計において固定されるので、この設計フローのその後の段階で相互接続の待ち時間に対する変更に対応することはできない。
【特許文献１】米国特許第６２０４６９０号
【特許文献２】米国特許第６２４３８５１号
【特許文献３】米国特許第６２９２０２２号
【特許文献４】米国特許第６５５３３９５号
【特許文献５】米国特許第６３５３８４１号
【非特許文献１】V. Kathail他, 「PICO(Program In, Chip Out): Automatically Designing Custom Computers」, 2002年9月, IEEE Computer, 35(9), p39-47
【非特許文献２】S. C. Goldstein他, 「Pipe Rench: A Reconfigurable Architecture and Complier」, 2000年4月, IEEE Computer, 33(4)
【非特許文献３】S. C. Goldstein他,「 Pipe Rench: A Coprocessor for Streaming Multimedia Acceleration」, 1999年, 26th Annual International Symposium  on Computer Architecture会報,  p28-39
【非特許文献４】V. Betz 及び J. Rose, 「Effect of the Prefabricated Routing Track Distribution on FPGA Area-Efficiency」, 1998年9月, IEEE Transactions on VLSI, 6(3), p445-456
【非特許文献５】Emre Ozer, Sanjeev Banerjia 及び Thomas M. Conte, 「Unified Assign and Schedule: A New Approach to Scheduling for Clustered Register File Microarchitectures」, 1998年, 31th Annual International Symposium on Microarchitecture(MICRO-31)会報, テキサス州ダラス,  p308-315
【非特許文献６】M. C. Papaefthymiou, 「Understanding Retiming Through Maximum Average-Delay Cycles」, 1994年, Mathematical Systems Theory, 1(27), p65-84
【非特許文献７】J. Babb, R. Tessier 及び A. Agarwal, 「Vitual Wires: Overcoming Pin Limitaions in FPGA-based Logic Emulators」, 1993年, IEEE Workshop ON FPGAs for Custom Computing Machines会報, カリフォルニア州ロスアラミトス, ｐ142-151
【非特許文献８】J. S. Rose 及び S. Brown, 「Flexibility of Interconnection Structures for Field-Programmable Gate Arrays」, 1991年3月, IEEE JSSC, 26(3), ｐ277-282
【非特許文献９】S. Note他, 「Cathedral III: Architecture driven high-level synthesis for high throughput DSP applications」, 1991年, 28th ACM/IEEE Design Automation Conference会報, DAC 91, カリフォルニア州サンフランシスコ, ｐ597-602
【非特許文献１０】Constantine N. ANAGNOSTOPOULOS 及び Paul P. K. LEE, 「Application-Specific Integrated Circuits」, The Electronics Handbook, 1996年, CRC Press, フロリダ州ボカラトン, ｐ731-748
【非特許文献１１】Bradley K. FAWCETT, 「Software Development Tools for Field Programmable Gate Array Devices」, The Electronics Handbook, 1996年, CRC Press, フロリダ州ボカラトン, ｐ784-793
【発明の開示】
【発明が解決しようとする課題】
【０００９】
相互接続資源のより効率的な利用を可能にする設計手順が必要とされている。
【課題を解決するための手段】
【００１０】
本発明は、カスタム回路デバイスを設計する方法である。一実施の形態によれば、本方法は、仮想ワイヤによって接続されたサブシステムの高水準アーキテクチャから開始する。本方法は、第１のステップから第３のステップを含む。第１のステップは、サブシステムをタイル上に空間配置することを含む。第２のステップは、相互接続アーキテクチャ上に、タイルの境界を横切る仮想ワイヤを配線することを含む。相互接続アーキテクチャはスイッチおよびレジスタを備える。スイッチのいくつかが、第１のタイル上に配置された第１のサブシステムから第２のタイル上に配置された第２のサブシステムへ信号を転送する。レジスタの少なくとも２つが、反復期間以下の時間間隔で信号を連続してラッチする。第３のステップは、クロックサイクルに従ってタスクをスケジューリングすることを含む。本方法の一実施の形態によれば、反復期間は、１クロックサイクル期間を含む。本方法の別の実施の形態によれば、反復期間は、複数のクロックサイクル期間を含む。
【００１１】
本方法の別の実施の形態において、本方法は、サブシステムとタイルを横切らない仮想ワイヤとをタイルの回路にマッピングする第４のステップ、をさらに含む。
【００１２】
本発明のこれらの態様および他の態様を本明細書でより詳細に説明する。
【００１３】
本発明を、その特定の例示の実施の形態について説明し、それに応じて図面を参照する。
【発明を実施するための最良の形態】
【００１４】
本発明は、ワイヤコストを低減すると同時に、性能を改善するデータ搬送手法を提供する。本発明の態様は、データ搬送アーキテクチャおよび設計手順を含む。双方の態様は、通信パスセグメントのパイプライン化を利用する。これは、長い通信パスが、システムサイクル時間に悪影響を与えることを防止する。さらに、本発明は、通信パスセグメントに沿った時間多重化を可能にする。これは、通信パスセグメントをより効率的に利用する。
【００１５】
仮想オペレーションと、仮想ワイヤによって接続されたデータオブジェクトとから成る仮想サブシステムの高水準アーキテクチャから始まって、設計手順は、このサブシステムの粗い配置が決定される空間計画から開始する。設計手順は、仮想ワイヤの少なくともいくつかが、データ搬送アーキテクチャ上に配置される配線に続く。パイプライン化および時間多重化に関する決定は、配線中に行われる。この決定を行う際に、パイプライン化は、データの発信源および宛先の空間位置の知識によって進められる。同様に、通信パスセグメントに沿った時間多重化の機会も、空間計画および通信の必要性から導出される。
【００１６】
設計手順は、特定のデバイスのタスクのスケジュールが決定されるスケジューリングで終了する。空間計画および配線を行った後にスケジューリングを行う結果として、少なくとも２つの利点が生じる。第１の利点は、スケジューリングは、パイプライン化および時間多重化に関する決定を利用して、データ搬送セグメント上でのデータ転送をスケジューリングすることである。第２の利点は、オペレーションの相対的な順序付けおよびタイミングをデータ搬送待ち時間に対応して調整できるように、スケジューリングは、パイプライン化の結果として生じる搬送待ち時間情報を利用することである。
【００１７】
本発明は、ＡＳＩＣ（特定用途向け集積回路）、ＦＰＧＡ（フィールドプログラマブルゲートアレイ）、ＰＬＤ（プログラマブル論理デバイス）、および他の再構成可能なデバイスを含めて、デジタルハードウェアシステム設計に適用することができる。ＦＰＧＡ、ＰＬＤ、および他の再構成可能なデバイスは、今日のデバイスに見られる再構成可能なデータ搬送素子とは異なる再構成可能なデータ搬送素子を実装することができる。これらの再構成可能なデータ搬送素子は、本発明のパイプライン化および時間多重化に、より良く適している。本発明の設計手順は、コンパイルツール、合成ツール、またはＣＡＤツール等の自動化設計ツールで明示することもできるし、手動の手順または両者の或る組み合わせによって達成することもできる。
【００１８】
本発明の再構成可能なデバイスの一実施の形態を図１に概略的に示す。再構成可能なデバイス１００は、タイル１０２および相互接続アーキテクチャ１０４を備える。タイル１０２のそれぞれは回路を備える。相互接続アーキテクチャ１０４は、データ交換点１０６として示される各タイル１０２の回路に接続する。用語「相互接続アーキテクチャ」は、本明細書で使用されるように、タイルを相互接続する構造を指す。
【００１９】
再構成可能なデバイス１００は、さまざまな計算素子、メモリ素子、相互接続素子、および制御素子を含むことができ、これらの素子は、さまざまな度合いで構成することができ、ハードウェア設計を実施するのに役立つものである。再構成可能なデバイス１００として考えられるコンポーネントのいくつかの具体例には、あらゆる組み合わせ論理機能を実施するようにプログラムできる参照表（ＬＵＴ）、キャリーチェーン等の特別な算術サポート、乗算器等の数学的演算または論理演算を実行する専用（ハードワイヤード）機能ユニット、プログラマブルスイッチを介して接続されたワイヤセグメント等の再構成可能な相互接続、およびメモリブロックが含まれる。このようなコンポーネントは、ＦＰＧＡに共通であり、かつ、ＤＳＰ（デジタル信号処理）業界向けのより計算指向型の再構成可能なアーキテクチャに共通である。再構成可能なデバイス１００の適用領域に応じて、他の特別なコンポーネント、例えば、内容アドレス指定可能メモリ（ＣＡＭ）が含まれることがある。
【００２０】
通常、再構成可能なデバイス１００の各タイル１０２は、さまざまなコンポーネントを混合したものを含み、したがって、異種的である。あるいは、タイル１０２の一部またはすべては、これらのタイル１０２を同種にする同一コンポーネントを含む。通常、タイル１０２は、タイル１０２の２次元グリッドで繰り返される。タイル１０２は、各タイル１０２内の一般的なデータ搬送では、そのデータ搬送が１クロックサイクル期間内に留まると予想されるようなサイズにされる一方、タイル１０２を越える一般的なデータ搬送では、そのデータ搬送が１クロックサイクル期間を超えると予想されるようなサイズにされる。上述し、かつ、以下にさらに詳述する設計手順の場合、タイル１０２は、粗い配置に便利で、かつ、パイプライン化の要求条件を推論するのに便利な単位を提供する。
【００２１】
再構成可能なデバイス１００の代替的な実施の形態では、タイル１０２は、各タイル１０２内の一般的なデータ搬送では、そのデータ搬送が１つの反復期間内に留まると予想されるようなサイズにされる一方、タイル１０２を越える一般的なデータ搬送では、そのデータ搬送が１つの反復期間を超えると予想されるようなサイズにされる。この代替的な実施の形態では、反復期間は、クロックサイクル期間の１つまたは２つ以上を含む。
【００２２】
タイル１０２は、図１に示すような方形である必要はなく、代わりに、３角形や６角形等の別の形状とすることもできることが当業者に容易に理解されよう。さらに、タイル１０２は、一様な形状である必要もなく、また、一様なサイズである必要もないことが当業者に容易に理解されよう。
【００２３】
通常、相互接続アーキテクチャ１０４は、データ搬送チャネル１０８の２次元ネットワークで構成される。データ搬送チャネル１０８のそれぞれは、複数のデータ搬送セグメントを含む。通常、データ搬送チャネル１０８は、データ交換点１０６に接続し、このデータ交換点１０６において、データは、相互接続アーキテクチャ１０４に入ることもできるし、相互接続アーキテクチャ１０４を離れることもできる。
【００２４】
相互接続アーキテクチャ１０４は、スイッチおよびレジスタを備える。スイッチは、タイル１０２の２つの間で信号を配線するものである。レジスタは、クロックサイクル期間内の時間間隔で信号をラッチするのが好ましい。あるいは、レジスタは、反復期間内の時間間隔で信号をラッチする。パイプライン化は、クロックサイクルごとに行われるので、連続的に信号をラッチする１対のレジスタは、パイプラインセグメントを形成する。
【００２５】
相互接続アーキテクチャ１０４の代替的な実施の形態では、反復期間が、１つまたは２つ以上のクロックサイクル期間を含む場合に、レジスタは、この反復期間内の時間間隔で信号をラッチする。この代替的な実施の形態では、レジスタは、反復期間の終了時に信号をラッチする。例えば、反復期間が、２つのクロックサイクル期間である場合に、レジスタは、１つおきのクロックサイクル期間に信号をラッチすることになる。
【００２６】
相互接続アーキテクチャ１０４の一実施の形態では、データ交換部１１０が、データ交換点１０６に配置される。この実施の形態では、データ交換部１１０は、スイッチの１つおよび１組のレジスタを備える。
【００２７】
通常、データ交換部１１０によって、データ搬送チャネル１０８の１つから入来するデータは、データ交換部１１０に接続されたデータ搬送チャネル１０８のいずれかに沿ってデータ交換部１１０を離れることが可能になる。また、そのデータを一時的なレジスタに記憶することもでき、したがって、各データ交換部において、複数のクロックサイクルの間、データを遅延されることができる。好都合なことに、タイル１０２は、データ交換部１１０を位置決めする基準フレームワークとして機能する。
【００２８】
データ交換点１０６は、タイル１０２と相互接続アーキテクチャ１０４との間の接続位置を表し、また、データ交換点１０６は、図１に概略的に示すようにタイル１０２の中心に配置される必要はないことが当業者に容易に理解されよう。さらに、データ交換部１１０は、データ交換点１０６に配置される必要はなく、１つまたは２つ以上の導電パスによってデータ交換点１０６に接続できることも当業者に容易に理解されよう。データ交換部１１０およびタイル１０２の１つの一部の一実施の形態を図２に概略的に示す。入力データ搬送セグメント２０２は、データ交換部１１０に入り、送出データ搬送セグメント２０４は、データ交換部１１０を離れる。データ搬送セグメントは、設計に適したビット幅、例えば４ビットニブルまたは８ビットニブルから成る。通常、レジスタ２０６は、入力データ搬送セグメント２０２をスイッチ２０８に接続する。レジスタファイル２１０は、スイッチ２０８に接続されることが好ましく、それによって、１つまたは２つ以上のクロックサイクルの間、データをデータ交換部１１０にバッファリングすることが可能になる。別法では、データ交換部１１０は、レジスタファイル２１０を含まない。
【００２９】
スイッチ２０８は、クロスバースイッチを備えることが好ましく、このクロスバースイッチによって、４つの入力データ搬送セグメント２０２、タイル１０２、またはレジスタファイル２１０のいずれからのデータも、送出データ搬送セグメント２０４のいずれか１つ（または複数）に送ったり、タイル１０２に送ったりすることが可能になる。別法では、スイッチ２０８は、クロスバースイッチよりもスイッチング容量が制限された別のスイッチを備える。
【００３０】
データ交換部１１０のレジスタファイル２１０は、書き込みポート２１２および読み出しポート２１４を含む。レジスタファイル２１０は、バッファリング機能を提供し、これによって、レジスタファイル２１０にデータを記憶することにより１つまたは２つ以上のクロックサイクル分、データを遅延させることが可能になる。最低でも、書き込みポート２１２の少なくとも１つおよび読み出しポート２１４の少なくとも１つがなければならない。入力データ搬送セグメント２０２のあらゆるものから到来するデータを記憶するのに十分な書き込みポート２１２が存在し、送出データ搬送セグメント２０４のすべてのデータを送信するのに十分な読み出しポート２１４が存在する場合に、レジスタファイル２１０は、最大限のスケジューリング柔軟性を提供する。書き込みポート２１２が、入力データ搬送セグメント２０２よりも少ない場合、各クロックサイクルで限られた量の入力データしか、レジスタファイル２１０にバッファリングすることができない。同様に、読み出しポート２１４が、送出データ搬送セグメント２０４よりも少ない場合、各クロックサイクルで限られた量のバッファリングされたデータしか、送出データ搬送セグメント２０４に沿って出力することができない。
【００３１】
タイル１０２は、データ交換部１１０にタイル１０２を接続する出力ポート２１６および入力ポート２１８を含む。最低でも、１つのタイル１０２につき少なくとも１つの出力ポート２１６が存在し、１つのタイル１０２につき少なくとも１つの入力ポート２１８が存在する。タイル１０２は、複数の出力ポート２１６および複数の入力ポート２１８を含むことが好ましい。オプションとして、タイル１０２を離れるデータを、スイッチ２０８に入る前に第１のレジスタ２２０にラッチすることができる。マルチプレクサ２２４は、ラッチされたデータおよびラッチされていないデータの一方を選択して、スイッチ２０８に接続することができる。同様に、オプションとして、タイル１０２に到来するデータを第２のレジスタ２２２にラッチすることができる。
【００３２】
代替的な実施の形態では、データ交換部１１０は、タイル１０２の出力ポート２１６を当該データ交換部１１０のスイッチ２０８に接続するレジスタを含む。
【００３３】
データ交換部１１０の一実施の形態は、データ搬送チャネル１０８のそれぞれにおける追加データ搬送セグメントのサポートを含むことができる。データ交換部１１０は、追加データ搬送セグメントを収容するために、スイッチ２０８の追加入力および追加出力を含むことができる。
【００３４】
あるいは、再構成可能なデバイス１００の一実施の形態は、データ交換点１０６のそれぞれにおいて複数のデータ交換部１１０を使用することもでき、各データ交換部１１０は、データ搬送セグメントのサブセットを接続する。この実施の形態は、より小さなスイッチを必要とするので、より拡張性があるが、各データ交換点１０６のセグメントを組に区画する。この実施の形態では、データ搬送セグメントをデータ交換点１０６間でどのようにワイヤ接続するのかにおいて高い柔軟性がある。例えば、設計は、そのデバイス全体にわたってデータ搬送セグメントを区画することができ、基本的には、複数の独立したデータ搬送ネットワークをデバイス上に重ね合わせる。あるいは、データ交換点１０６間のデータ搬送セグメントのワイヤリングは、ある区画の組から別の区画の組への交差を可能にして、データ搬送セグメントが重なり合わない区画へとデバイス上で分離することを防止できる。
【００３５】
本発明の一実施の形態では、本発明の相互接続アーキテクチャを通じたデータ転送を制御するのに、プログラム制御モードが、静的なスケジューリングと共に使用される。静的なスケジューリングは、共通資源へのアクセスの衝突を回避するために使用される。これは、共通の共有資源の使用に関与する関係者が実行時に起動する要求に基づいて、実行時に割り当てを決定する動的なアービトレーションとは対照的である。
【００３６】
プログラム制御の下、ローカルに順序付けられたプログラムは、各データ交換部を制御する。このローカルに順序付けられたプログラムは、メモリまたは状態マシンから引き出された命令を使用するプログラム実行メカニズムとすることができる。メモリまたは状態マシンのいずれも、ローカル制御スレッドを提供する。一実施の形態によれば、状態マシンは、再構成可能な論理回路を備える。ローカル制御スレッドは、外部コマンドがないときは制御連続性を提供する。制御の決定を行う際に、プログラム制御は、データ搬送セグメントを流れるコンテンツを考慮する必要はない。
【００３７】
一実施の形態では、ローカルに順序付けられた制御プログラムは、データ交換部がどのように動作するのかをクロックサイクルごとに指定する。プログラムは、データ交換部のスイッチがどのように構成されるのか、すなわち、どの入力が１つまたは複数のどの出力に接続されるのかを指定する。また、プログラムは、いずれかのデータをデータ交換部のレジスタファイルに記憶すべきかどうかも指定し、１つまたは複数の宛先レジスタを指名する。また、プログラムは、レジスタファイルから読み出すレジスタがもしあれば、そのレジスタも指名する。プログラムは、レジスタのそれぞれがそのクロックサイクルで新たな値をラッチするのかどうか、または、レジスタのそれぞれが事前にラッチされた値を保持するのかどうかも制御することができる。
【００３８】
実行パス上での柔軟なローカル制御を容易にするために、ローカルに順序付けられた制御プログラムは、ローカルな条件分岐を実行する機能を備える。一実施の形態は、条件分岐命令、条件変数を計算する汎用算術演算および論理演算、ならびにスクラッチレジスタを制御プログラムに装備する。これによって、例えば、制御プログラムは、ループが終了すべき時をローカルに決定する繰り返し回数をカウントするループカウンタをローカルに管理することが可能になる。
【００３９】
一般的なデータ転送パスは、複数のデータ交換部を含む。このようなパス上での転送を成功させるために、そのパスに沿ったデータ交換部のプログラム制御は、同期して動作し、正しいオペレーションが各サイクルで実行されることを確保する。上流側のデータ交換部の制御は、正しい値を出力しなければならない一方、下流側のデータ交換部は、適宜、その値を転送するか、または、レジスタに記憶しなければならない。この同期した協調は、静的に編成され、データ交換部で実行される制御プログラムに符号化される。
【００４０】
ローカルに順序付けられたプログラムが、デバイスの他の態様と協調することを可能にするために、プログラム制御は、そのローカル制御スレッドの分岐を外部から起動することを可能にする。リモート分岐メカニズムは、２００３年４月１日に出願された米国特許出願第１０／４０５，１７０号に記載されている。このリモート分岐メカニズムは、ローカル制御スレッドの分岐の外部からの起動を達成する１つの方法である。基本的には、データ交換部におけるプログラム制御は、デバイス上の他の制御エンティティから当該データ交換部に送信された分岐コマンドを受信する。プログラム制御は、リモート分岐コマンドを受信すると、自身のローカル制御スレッドを、分岐コマンドによって指定された分岐対象に転送し、そこから実行を継続する。
【００４１】
一実施の形態によれば、分岐コマンドは、計算を協調するすべてのデータ交換部に分岐命令をマルチキャストし、調和して動作するように静的に計画されていたコード列にそれらすべてのデータ交換部を分岐させる。このように、データ転送パス上のすべてのデータ交換部は、分岐命令の宛先の間に存在することができる。
【００４２】
一実施の形態は、各データ交換部において１つのプログラム制御スレッドをサポートすることができる。別の実施の形態は、静的な衝突解決法を依然として使用しつつ、複数のプログラム制御スレッドをサポートすることができる。これは、異なる制御フローを有する計算（すなわち、それらの計算は異なる分岐条件を有する）がデータ交換部を共有することを可能にするという利点を有する。それ以外の独立したスレッドを静的に資源区画することは、空間区画もしくは時間区画、またはその双方によって行うことができる。時間区画は、繰り返し発生する一続きのタイムスロットに時間を分割し、各タイムスロットを１つのスレッドに割り当てるものである。例えば、第１のスレッドは、奇数サイクルでデータ交換資源を使用する一方、第２のスレッドは、偶数サイクルでデータ交換部を使用する。あるいは、空間区画は、データ交換部内の異なる資源を各スレッドに割り当てるものである。例えば、データ交換部のスイッチは、第１の入力および第２の入力ならびに第１の出力および第２の出力が、第１のスレッドによって使用される一方、第３の入力および第４の入力ならびに第３の出力および第４の出力が、第２のスレッドによって使用されるように空間区画することができる。各制御スレッドは、自身がサイクルごとに制御をアサートしている資源を示し、その結果、複数のスレッドからの全制御のマージが簡単になる。資源割り当ては静的に行われるので、動的なアービトレーションおよび割り当ての必要はない。
【００４３】
プログラム制御メカニズムと異なり、タグベースのスイッチングは、通常パケットと呼ばれるデータ単位がデータ交換部の１つを流れる際に、そのパケットで運ばれる、時にヘッダと呼ばれるタグに基づいて当該データ単位をどのように取り扱うかを決定する。
【００４４】
タグベースのスイッチングメカニズムの一実施の形態では、各データ交換部の制御部は、プログラム可能参照表を保持する。各パケットで運ばれるタグは、この表の参照用キーとして使用される。参照が成功すると、そのパケットをデータ交換部の１つまたは複数のどの出力ポートに転送すべきか等の情報が得られる。
【００４５】
タグベースのスイッチングの簡単な実施態様では、データ交換部を伝播するパケットは、データ交換部のそれぞれで一定の遅延に遭遇する。この一定の遅延では、パケットが遭遇したデータ交換部のそれぞれから現れる前に、パケットの第１のデータチャンク（chunk of data）が、一定のクロックサイクル数だけ遅延される。これとは対照的に、プログラム制御は、データ交換部内のレジスタファイルにデータをバッファリングして、データを任意のクロックサイクル数の間、遅延させることができる。
【００４６】
別の実施態様では、タグベースのスイッチングが、プログラム可能な遅延によって増強される。プログラム可能な遅延によって、パケットは、遭遇するデータ交換部のそれぞれにおいて、自身に関連した異なる遅延を有することが可能になる。タグベースのスイッチングの下でのプログラム可能な遅延の一実施の形態は、成功した参照結果の一部として他の２つの値を含めるように、プログラム可能参照表を増強する。１つの値は、データ交換部を通る一定の通過遅延を増加させる追加遅延のサイクル数である。第２の値は、ベースバッファレジスタ名であり、データをバッファリングするのに使用されるデータ交換部のレジスタファイルにおける第１のレジスタの名前である。
【００４７】
パケットが、ｍクロックサイクルに及ぶデータを運び、ｎサイクルの遅延が必要とされる場合に、ｍｉｎ（ｎ，ｍ）個のレジスタが、この遅延を受けるデータをバッファリングするのに必要とされる。一実施の形態によれば、ｍはｎよりも大きく、その結果、ｍｉｎ（ｎ，ｍ）はｎとなる。一実施の形態は、このバッファリングのために、連続した名前を有するｎ個のレジスタを静的に割り当てることによってこれを実施する。データ交換部は、０から開始してサイクルごとにインクリメントする、所望の追加遅延サイクルｎを法としたモジュロカウンタを入力ポートごとに保持する。各クロックサイクルにおいて、この事前インクリメントカウント（pre-increment count）は、ベースバッファレジスタ名に追加されて、そのサイクルに到来するデータをバッファリングするのに使用される実際のレジスタを計算する。
【００４８】
複数の書き込みポートをサポートするデータ交換部の一実施の形態は、参照に成功した場合の参照表の読み出し結果に第３の値を含むことができる。この値は、データ交換部のレジスタファイル内にデータをバッファリングするのに使用される書き込みポートを指定する。同様に、複数の読み出しポートをサポートする一実施の形態も、参照結果に第４の値を含むことができ、この第４の値は、バッファリングされたデータを読み出してデータ交換部から送信する時に使用する読み出しポートを指定する。
【００４９】
データ交換部は、所望の遅延後にデータを読み出して、所望の出力ポートからデータを送出するメカニズムを含む。一実施の形態では、レジスタファイルの各読み出しポートは、今後、或る時間が経てば実行される読み出し動作の記録をとる保留動作キュー（pending action queue）を有する。データが、ｎサイクル遅延の間、レジスタファイルのレジスタｒにバッファリングされると、そのデータをｎサイクル後にレジスタｒから読み出す保留動作が、表の参照結果によって指定された読み出しポートと共にキューに入れられる。各クロックサイクルにおいて、保留動作キューは進められ、現時点となった保留動作が実行される。同様のキューは、データ交換部のスイッチの保留動作用にも保持される。わずかな相違は、スイッチでは、異なる資源を使用する複数の動作を各クロックサイクルで実行でき、したがって、スイッチの保留動作キューの各サイクルのエントリが、複数の動作を収容する必要があるということである。
【００５０】
保留動作キューは、パラレル／シリアルシフトキューによって実施することができる。動作が、多数の遅延サイクルを必要とする場合、その動作は、そのシフトキューにおいて、キューの先頭からその遅延サイクル数に対応する位置に挿入される。次いで、このキューは、クロックサイクルごとにシフトされる。動作は、キューの先頭に到達すると実行される。
【００５１】
上述したタグベースのスイッチングの実施の形態は、参照表を利用する。代替的な実施の形態はタグの内部で情報を運ぶ。パケットが、各データ交換部を通過すると、各データ交換部は、タグの先頭の情報を取り除き、後続のデータ交換部のために残余を残しておく。この実施の形態の利点は、参照表が必要とされないことである。また、この実施の形態では、参照表をセットアップするオーバーヘッドも回避される。これとは対照的に、参照表を使用するタグベースのスイッチングの利点は、タグがより小さくなるということである。
【００５２】
プログラム制御メカニズムは、その制御が、外部源によってトリガされた後、かなりの時間の間、ローカルに決定されたパスに従う場合に効率的になる。一例は、カウントされたループ本体の実行である。これに比べて、タグベースのスイッチングは、繰り返しの少ない、外部で決定された転送に適している。例としては、実行の非ループ部分におけるデータ転送がある。
【００５３】
本発明の再構成可能なデバイスの一実施の形態では、相互接続アーキテクチャおよび分岐制御ネットワークが、ハードウェア資源を共有するためにマージされる。別の実施の形態では、分岐制御ネットワークは、別個の回路を備える。さらに別の実施の形態では、再構成可能なデバイスは、タグベースのスイッチングに依拠し、分岐制御ネットワークの必要性は排除される。
【００５４】
本発明のパイプライン化および時間多重化を以下に提供する例で、より十分に説明する。
【００５５】
本発明のパイプライン化の例を、図３および図４について以下に説明する。本発明の再構成可能なデバイスの一実施の形態を図３に概略的に示す。この再構成可能なデバイス３００は、タイル１０２'、相互接続アーキテクチャ１０４'、およびデータ交換部１１０'を備える。第１のタイル３０２は、第１の値Ｖａを有する第１の配列Ａを含む。第２のタイル３０４は、第２の値Ｖｂを有する第２の配列Ｂを含む。第３のタイル３０６は、乗算／累積回路（ＭＡＣ（Multiply and Accumulate Circuit））を含む。相互接続アーキテクチャ１０４'は、第１のタイル３０２、第２のタイル３０４、および第３のタイル３０６にそれぞれ接続された第１のデータ交換部３１２、第２のデータ交換部３１４、および第３のデータ交換部３１６を含む。相互接続アーキテクチャ１０４'は、さらに、第４のデータ交換部３１８および第５のデータ交換部３２０も含む。
【００５６】
ＭＡＣを図４に概略的に示す。ＭＡＣ４００は、乗算器４０２、加算器４０４、およびレジスタ４０６を含む。オペレーション中、乗算器４０２は、第１の値Ｖａと第２の値Ｖｂとを乗算し、積を形成する。加算器４０４は、その積を、レジスタ４０６に配置されたレジスタ値に加算して、和を形成する。次いで、この和は、レジスタ４０６のレジスタ値に取って代わる。一連のＭＡＣ計算の開始時において、加算された値がレジスタ４０６に蓄積される前に、このレジスタ４０６は０に初期化される。
【００５７】
図３を参照して、オペレーション中、第１の値Ｖａは、第１のクロックサイクルにおいて、第１のデータ交換部３１２に接続されたタイル３０２の出力ポートのレジスタにラッチされる。第２のクロックサイクルにおいて、この第１の値Ｖａは、第４のデータ交換部３１８に転送される一方、第２のＶｂは、第２のデータ交換部３１４に接続されたタイル３０４の出力ポートのレジスタにラッチされる。第３のクロックサイクルにおいて、第１の値Ｖａは、第４のデータ交換部３１８から第５のデータ交換部３２０に転送される一方、第２の値Ｖｂは、第２のデータ交換部３１４から第３のデータ交換部３１６に転送される。第４のクロックサイクルにおいて、第１の値Ｖａは、第５のデータ交換部３２０から第３のデータ交換部３１６に転送される一方、第２の値Ｖｂは、第３のデータ交換部３１６から第３のタイル３０６に転送される。第５のクロックサイクルにおいて、第１の値Ｖａは、第３のデータ交換部３１６から第３のタイル３０６に転送される。表１は、第１の値Ｖａおよび第２の値Ｖｂに関して、第１のクロックサイクルから第５のクロックサイクルを要約したものである（表では、「データ交換部」は、ＤＩと略記されていることに留意されたい）。
【００５８】
【表１】
2005135411.tif 000003
【００５９】
資源の利用可能性に応じて、第１のクロックサイクルから第５のクロックサイクルの新たなシーケンスを各クロックサイクルで開始することが可能な場合がある。これは、起動間隔１と呼ばれる。このようなシナリオでは、パイプライン化によって、ＭＡＣ４００は、新たな１組の入力に対する作業を各クロックサイクルで開始することが可能になる。
【００６０】
しかし、資源の利用可能性に制限がある場合には、第１のクロックサイクルから第５のクロックサイクルの新たなシーケンスを１つおきのクロックサイクルでしか開始できない場合がある。これは、起動間隔２と呼ばれる。あるいは、第１のクロックサイクルから第５のクロックサイクルの新たなシーケンスを２つおきのクロックサイクルでしか開始できない場合もある。これは、起動間隔３と呼ばれる。例えば、第３のタイル３０６は、第１の値Ｖａおよび第２の値Ｖｂを受け取るのに利用可能なポートを１つしか有しない場合がある。このようなシナリオでは、パイプライン化によって、ＭＡＣ４００は、１つおきのクロックサイクルでオペレーションを実行することが可能になる。
【００６１】
プログラム制御モードが、第１の値Ｖａおよび第２の値Ｖｂの転送を制御するのに使用される場合、第１のデータ交換部３１２から第５のデータ交換部３２０のそれぞれには、転送の開始時にリモート分岐が送信される。システム全体にわたる同期した予測可能なタイミングによって、第１のデータ交換部３１２から第５のデータ交換部３２０は、協調して所望のスケジュールを実施する。本発明の一実施の形態では、リモート分岐のそれぞれは、転送の終了時を知るためのローカルカウントを保持する。
【００６２】
本発明のパイプライン化および時間多重化の一例を図５および図６について以下に説明する。再構成可能なデバイス３００を図５に概略的に示す。この再構成可能なデバイス３００は、第１のタイル３０２および第２のタイル３０４にそれぞれ配置された第１の配列および第２の配列から提供された第１の値Ｖａおよび第２の値Ｖｂを有する第３のタイル３０６で、ＭＡＣ４００（図４）の動作を継続する。これに加えて、第１のタイル３０２は、第３の値Ｖｃを有する第３の配列を含み、第６のタイル３０８は、第４の値Ｖｄを有する第４の配列を含む。第７のタイル３１０は、除算／記憶回路を含む。相互接続アーキテクチャは、第６のタイル３０８および第７のタイル３１０にそれぞれ接続した第６のデータ交換部３２２および第７のデータ交換部３２４を含む。
【００６３】
この除算／記憶回路を図６に概略的に示す。除算／記憶回路６００は、除算器６０２およびレジスタファイル６０４を備える。除算器６０２は、第３の値Ｖｃを第４の値Ｖｄで除算し、その結果、第５の値を得る。この第５の値は、レジスタファイル６０４に配置された第５の配列に記憶される。
【００６４】
図５を参照して、オペレーション中、第３の値Ｖｃは、第０クロックサイクルにおいて、第１のデータ交換部３１２に接続されたタイル出力ポートのレジスタにラッチされる。第１のクロックサイクルにおいて、第３の値Ｖｃは、第１のデータ交換部３１２から第４のデータ交換部３１８に転送される一方、第４の値Ｖｄは、第６のデータ交換部３２２に接続されたタイル出力ポートのレジスタにラッチされる。第２のクロックサイクルにおいて、第３の値Ｖｃは、第４のデータ交換部３１８から第５のデータ交換部３２０に転送される一方、第４の値Ｖｄは、第６のデータ交換部３２２から第７のデータ交換部３２４に転送される。第３のクロックサイクルにおいて、第３の値Ｖｃは、第５のデータ交換部３２０から第７のデータ交換部３２４に転送される一方、第４の値Ｖｄは、第７のデータ交換部３２４から第７のタイル３１０に転送される。第４のクロックサイクルにおいて、第３の値Ｖｃは、第７のデータ交換部３２４から第７のタイル３１０に転送される。表２は、第１の値Ｖａから第４の値Ｖｄに関して、第０のクロックサイクルから第５のクロックサイクルを要約したものである。
【００６５】
【表２】
2005135411.tif 000004
【００６６】
ＭＡＣ４００（図４）および除算／記憶回路６００（図６）が、起動間隔２で動作する場合、本発明の時間多重化によって、第１のデータ交換部３１２と第４のデータ交換部３１８との間、および、第４のデータ交換部３１８と第５のデータ交換部３２０との間のデータ転送セグメントの効率的な使用が可能になる。このようなシナリオでは、第１のセグメントの時間多重化は、第１のデータ交換部３１２から第４のデータ交換部へ第１の値Ｖａを１つおきのクロックサイクルで転送する。交互のクロックサイクルでは、第１のセグメントの時間多重化は、これらのデータ交換部の間で第３の値Ｖｃを転送する。第２のセグメントの時間多重化は、第４のデータ交換部３１８と第５のデータ交換部３２０との間で、第１の値Ｖａおよび第３の値Ｖｃの同様の転送を行う。ただし、これらの転送は、第１のデータ交換部３１２および第４のデータ交換部３１８との間の転送とは入れ替わったクロックサイクルで行われる。
【００６７】
ＭＡＣ４００または除算／記憶回路６００が、起動間隔１で動作する場合、時間多重化は、第１の値Ｖａおよび第３の値Ｖｃの転送にとって効率的でないことがある。このようなシナリオでは、第３の値Ｖｃの転送は、第１の値Ｖａの転送とは異なる配線を使用すると、より効率的になることがある。例えば、第３の値Ｖｃは、第８のデータ交換部３２６および第９のデータ交換部３２８を通る配線に設定することができる。これを行うには、第１の値Ｖａおよび第３の値Ｖｃを第１のデータ交換部３１２のレジスタへ同時に転送するために、２つの出力ポートが第１のタイル３０２で利用可能であることが必要となる。
【００６８】
本発明の設計手順を図７のフローチャートとして示す。設計手順ステップ７００は、空間計画ステップ７０２、配線ステップ７０４、およびスケジューリングステップ７０６を備える。
【００６９】
一般に、設計フローは、必要な計算のプログラム仕様から開始する。例えば、プログラム仕様は、Ｃ言語のプログラムとすることができる。ＣＡＤ（コンピュータ支援設計）産業は、時に、振る舞い仕様としてのプログラム仕様を指すことがある。このプログラム仕様は、クロックサイクルごとの動作を指定するのではなく、代わりに、より抽象的に動作を指定する点で、ＲＴＬ（レジスタ転送レベル）仕様とは異なる。プログラム仕様が、内部表現に変換され、コンパイラ／合成ツールによって解析されると、そのプログラム仕様は、メモリのロード／記憶、算術演算等を包含する動作の論理的な半順序関係を規定するものとしてみなすことができる。
【００７０】
コンパイラ／合成ツールは、通常、さまざまな最適化およびコード再構成を行って、冗長な計算を取り除き、並列性を明らかにする。これらのステップは、本発明の設計手順に先行して行われる。最適化およびコード再構成が完了すると、プログラム仕様は、仮想アーキテクチャに変換されたものとみなすことができる。この仮想アーキテクチャは、仮想ワイヤによって接続された仮想サブシステムを備え、本発明の設計手順の開始点を提供する。
【００７１】
仮想アーキテクチャは、オペレーションやメモリオブジェクト等の仮想エンティティを取り扱う。これは、機能ユニットおよびＲＡＭ（ランダムアクセスメモリ）ブロックのハードウェアエンティティとは異なる。ここで、機能ユニットは、オペレーションを実行するものであり、ＲＡＭブロックは、メモリオブジェクトを保持するものである。或る時点で、仮想エンティティからハードウェアエンティティへのマッピングが必要となる。このマッピングは、設計手順７００の前、間、または後に行うことができる。
【００７２】
本発明の設計手順の一実施の形態を図１０のフローチャートとして示す。この設計手順１０００は、仮想エンティティを物理エンティティへマッピングする第１のステップ１００２から開始する。設計手順１０００は、物理エンティティをタイル上に空間配置する第２のステップ１００４に続く。第３のステップ１００６は、タイル境界を横切る仮想ワイヤを相互接続アーキテクチャ上に配線することを含む。この方法は、資源の制約条件および待ち時間の制約条件に従ってタスクをスケジューリングする第４のステップ１００８で終了する。設計手順１０００では、第２のステップ１００４で配置されたサブシステムは、機能ユニットおよびＲＡＭブロックのハードウェアエンティティを備える。第２のステップ１００４は、タイル資源がオーバーコミットされないという制約条件の下で、機能ユニットおよびＲＡＭブロックのタイルへの粗い配置を行う。ハードウェアエンティティを取り扱うことによって、必要とされるタイル資源のより的確な見積もりが可能になる。それにもかかわらず、タイル資源の使用を追跡する際に、第４のステップ１００８の期間中に起こることがある一時的なバッファリングの必要性のため、付加的なバッファリング資源を取っておくべきである。
【００７３】
本発明の設計手順の別の実施の形態を図１１のフローチャートとして示す。この設計手順１１００は、仮想エンティティをタイル上に空間配置する第１のステップ１１０２から開始する。第２のステップ１１０４は、タイル境界を横切る仮想ワイヤを相互接続アーキテクチャ上に配線することを含む。この方法は、資源の制約条件およびクロックサイクル粒度の待ち時間の制約条件に従ってタスクをスケジューリングし、仮想エンティティを物理エンティティに同時にマッピングする第３のステップ１１０６で終了する。
【００７４】
設計手順１１００では、サブシステムは、仮想エンティティを備え、この仮想エンティティは、オペレーションおよびメモリオブジェクトを含む。第１のステップ１１０２は、オペレーションおよびメモリオブジェクトをタイル上に空間配置する。第１のステップ１１０２は、特定のタイルに配置される仮想エンティティに必要とされるタイル資源の或る種の認識を使用して、そこに配置されるすべての仮想エンティティを収容するのに十分なタイル資源が確実に存在するようにする。これを行う１つの方法は、仮想エンティティをサポートするのに必要とされる物理エンティティの予備的な最小資源使用見積もりを行うことである。この予備的なマッピングによって、フィット性の存在が確保される。予備的なマッピングの最適化が目的ではないので、予備的なマッピングは、簡単かつ高速に行うことができる。一例は、タイルにマッピングされたすべての仮想オペレーションを一括して実行できる異なるタイプのＡＬＵ（算術論理演算ユニット）の最小セットを選択することである。ソフトウェアパイプラインループ等のいくつかの特別なサブシステムの場合、ループの一定のスループット（性能）を達成するのに必要とされる物理エンティティを正確に決定する簡単な手順が存在する。このような手順は、仮想サブシステムの物理資源の要求条件を見積もるのに利用することができる。
【００７５】
設計手順７００の一実施の形態では、空間計画７０２は、通常、タイル間のデータ通信を最適化することを目的として行われる。例えば、空間計画７０２は、クリティカルな計算パスに沿ったデータ転送源と宛先との間の距離を最小にすることを目指すことができる。データ転送セグメントを共有する機会は、配置の決定中に別に考慮することができる事項である。
【００７６】
設計手順７００の一実施の形態では、配線７０４は、空間計画７０２に続いて行われる。別の実施の形態では、配線７０４は、空間計画７０２の完了前に開始する。例えば、或るサブシステムがタイル上に配置されると、次のサブシステムが配置される前に、そのサブシステムを他に配置されたサブシステムに接続する仮想ワイヤが配線される。この仮想ワイヤの配線７０４は、タイル境界を横切る仮想ワイヤを相互接続アーキテクチャ上に配置する。また、配線７０４は、データ通信のパイプライン化および時間多重化も決定する。配線の距離を削減するという従来の配線目的とは別に、配線７０４は、配線が性能に悪影響を与えない限り、データ搬送セグメントを共有する機会を有する配線を支持することもできる。このような共有の機会は、時間多重化、すなわち、重なり合わない期間に行われるデータ転送を利用する（つまり、第１のデータ転送が開始して終了し、その後、或る時間の経過後に、第２のデータ転送が開始して終了する）。
【００７７】
共有する機会を見つけるのに、いくつかの発見的方法が利用可能である。多重化の機会は、起動間隔２以上の起動間隔を有するデータ転送を特定することによって見つけることができる。重なり合わない期間に行われるデータ転送の機会は、同時にアクティブになることができないデータ転送によって特定することができる。このような排除情報源には、或る条件分岐の異なる分岐、および、制御／データ依存性またはコンパイラの課したシーケンスによって連続的になったコード部分が含まれる。
【００７８】
本発明の一実施の形態では、配線７０４が、タイル境界を横切る仮想ワイヤの配置を決定すると、プログラムの中間表現は、明示的なデータ通信オペレーションによって増強される。プログラム制御によって制御されたデータ転送の場合、データ交換部を通じてデータを移動させる明示的なコピーオペレーションが挿入される。データ転送のタグベースのスイッチングの場合、タグ形成オペレーションおよびデータ転送起動オペレーションが追加される。
【００７９】
次いで、スケジューリング７０６が、タスクのスケジュールを決定する。実際のスケジューリングの準備として、ハードウェア上の各オペレーションの待ち時間が抽出される。この待ち時間には、各データ転送オペレーションの待ち時間（すなわち、データ転送源と宛先との間にどれだけ多くのパイプラインステージが存在するか）、および、データ交換部におけるコピーオペレーションの待ち時間（そのデータセグメントを通って次のデータ交換部への遅延を含む）が含まれる。また。資源がオーバーコミットされないことを確保するために、各オペレーションの資源マップも準備される。次に、リストスケジューリングおよびソフトウェアパイプライン化ループ用のモジュール的スケジューラ（modular scheduler）等の従来の命令スケジューリング技術が適用されて、データ転送を含めて、オペレーションの全体的なスケジュールが生成される。
【００８０】
仮想エンティティの物理エンティティへのマッピングがスケジューリング７０６の前に固定されない場合の設計手順７００の実施の形態では、スケジューリング７０６は、ハードウェアエンティティを選択すること、および、仮想エンティティをその選択したハードウェアエンティティにマッピングすること同時に行われる。スケジューリング７０６は、ハードウェアエンティティの選択だけでなく、仮想エンティティと物理エンティティとの間のマッピングにも影響を与えるようにまとめられた部分的なスケジュールを考慮することができる。この柔軟性の結果、システムをより効率的にすることができる。
【００８１】
設計手順７００の一実施の形態によれば、先行する繰り返しで得られた結果を洗練して改善することを繰り返し試みる繰り返しループ内に設計手順７００を組み込むことができる。したがって、先行する繰り返しから収集された情報を使用して、現時点の繰り返しでの選択を案内することができる。
【００８２】
設計手順７００の第１の例示に実施の形態から第３の例示に実施の形態は、スケジュール７０６が、異なる配置にどのように応答できるかを示している。第１の例示の実施の形態から第３の例示の実施の形態は、以下に示す計算を実施する。この計算は、計算行番号１から９で特定される。
１．ｕＡｄｄｒ＝ａ＋４；
２．ｗＡｄｄｒ＝ｂ＋８；
３．ｕ＝ｌｏａｄ（ＯｂｊｅｃｔＵ，ｕＡｄｄｒ）；
４．ｗ＝ｌｏａｄ（ＯｂｊｅｃｔＷ，ｗＡｄｄｒ）；
５．ｒ＝ａ＋ｂ；
６．ｓ＝５＋ｃ；
７．ｘ＝ｕ＋ｒ；
８．ｙ＝ｗ＋ｓ；
９．ｚ＝ｓ＋ｒ；
【００８３】
第１の例示の実施の形態から第３の例示の実施の形態を、図１２として示すタイル構成について説明する。第１の実施の形態、第２の実施の形態、および第３の実施の形態のそれぞれは、空間計画ステップ７０２、配線ステップ７０４、およびスケジューリングステップ７０６を使用する計算ユニット、第１のメモリオブジェクト、および第２のメモリオブジェクトを備えるカスタム回路デバイスを設計する。計算ユニットは、計算行番号１、２、および５から９として上記で特定した、計算のうちの加算を実行する。また、計算ユニットは、計算で使用される自由変数の値（すなわち、ａ、ｂ、ｃ等の値）も保持する。データオブジェクトＯｂｊｅｃｔＵおよびデータオブジェクトＯｂｊｅｃｔＷは、第１のメモリオブジェクトおよび第２のメモリオブジェクトにそれぞれ配置される。
【００８４】
第１の例示の実施の形態では、空間計画７０２は、計算ユニット、第１のメモリオブジェクト、および第２のメモリオブジェクトを第１のタイル１２０２から第３のタイル１２０６にそれぞれ配置する。第２のタイル１２０４および第３のタイル１２０６は、第１のタイル１２０２に隣接して位置する。したがって、第１のメモリオブジェクトおよび第２のメモリオブジェクトは、計算ユニットに隣接して位置する。第１の例示の実施の形態では、スケジューリング７０６は、図１３として提供する表３に記載したような第１のスケジュールを決定する。
【００８５】
第２の例示の実施の形態では、空間計画７０２は、計算ユニット、第１のメモリオブジェクト、および第２のメモリオブジェクトを第１のタイル１２０２、第４のタイル１２０８、および第３のタイル１２０６にそれぞれ配置する。第１のタイル１２０２および第４のタイル１２０８は、第２のタイル１２０４によって隔てられる。したがって、第２の例示の実施の形態では、第２のメモリオブジェクトは、計算ユニットに隣接して位置し、第１のメモリオブジェクトは、間に介在するタイルによって計算ユニットから隔てられる。第２の例示の実施の形態では、スケジューリング７０６は、図１４として提供する表４に記載したような第２のスケジュールを決定する。値ｕは、時刻７までタイルＡで利用可能ではないことに留意されたい。したがって、スケジューリング７０６は、ｘ＝ｕ＋ｒの計算を時刻５から７へ移動させ、ｚ＝ｓ＋ｒの計算を時刻７から５へ移動させる。
【００８６】
第３の例示の実施の形態では、空間計画７０２は、計算ユニット、第１のデータメモリオブジェクト、および第２のメモリオブジェクトを第１のタイル１２０２、第２のタイル１２０４、および第５のタイル１２１０にそれぞれ配置する。第１のタイルおよび第５のタイルは、第３のタイル１２０６によって隔てられる。したがって、第３の例示の実施の形態では、第１のメモリオブジェクトは、計算ユニットに隣接して位置し、第２のメモリオブジェクトは、間に介在するタイルによって計算ユニットから隔てられる。第３の例示の実施の形態では、スケジューリング７０６は、図１５として提供する表５に記載したような第３のスケジュールを決定する。ここでは、ｗＡｄｄｒを第５のタイル１２１０に先行して送信できるように、ｗＡｄｄｒの計算が、ｕＡｄｄｒの計算の前に行われる。ｚ＝ｓ＋ｒの計算は、再び時刻５に配置される一方、ｘ＝ｕ＋ｒおよびｙ＝ｗ＋ｓの計算は、時刻６および７でそれぞれ行われる。
【００８７】
第１の例示の実施の形態から第３の例示の実施の形態は、空間計画７０２の後にスケジューリング７０６を実行し、良好なクロックサイクル粒度のタイミング情報が空間計画から導出されたことに伴う利点を示すものである。例えば、第１の例示の実施の形態において、スケジュールが配置前に固定され、配置が、その後、第１のデータオブジェクトタイルおよび第２のデータオブジェクトタイルの双方を計算タイルに隣接して配置できないとすると、その結果のシステムのクロックサイクル期間は、より長くなることを甘受しなければならない可能性が最も高くなる。
【００８８】
スケジューリング７０６が行われると、さらにデータパス合成を行って、バッファリングの必要性を判断することができる。この時点で、設計は、基本的には、ＲＴＬ仕様に類似した仕様に変換されている。この時点以降の合成は、制御状態機械の生成を含んだより古典的な合成フロー、および、各タイルのより古典的な配置および配線に従うことができる。
【００８９】
本発明の設計手順および再構成可能なデバイスは、多くの利点を提供する。相互接続アーキテクチャ内のデータ通信のパイプライン化によって、長距離通信を収容すると同時に、短いクロックサイクル時間が可能になる。データ通信の時間多重化によって、少なくとも部分的にデバイスの同じ領域を横断する論理的には別々の通信間でワイヤを共有することが可能になる。パイプライン化の前に空間計画を行うことによって、パイプラインセグメントおよびパイプラインの深さを正確に決定することが可能になる。空間計画後に時間多重化を決定することによって、通信パスの空間近接性に関する正確な情報を使用して、デバイス搬送セグメントの共有の機会を決定できることが保証される。パイプライン化および時間多重化の決定後にスケジューリングを行うことによって、スケジューリングは、パイプラインの遅延を考慮することが可能になる。パイプラインセグメントによってデータ通信を決定することにより、データ搬送セグメントの柔軟かつ効率的な共有が可能になる。相互接続アーキテクチャ内の中間点でバッファリングする機能を有することによって、デバイスの或る領域を通る複数のデータ通信の配線およびスケジューリングに柔軟性を持たせることが可能になる。
【００９０】
本発明の再構成可能なデバイスは、本発明の設計手順を効率的に利用するように構成されるが、この設計手順は、本発明の再構成可能なデバイス以外に、より広い適用範囲を有する。例えば、本発明の設計手順は、既存のＦＰＧＡ上のカスタム回路デバイスを構成するのに使用することができる。既存のＦＰＧＡの資源を仮想タイルおよび仮想相互接続アーキテクチャに区画することによって、既存のＦＰＧＡには本発明の再構成可能なデバイスの構造が欠けているにもかかわらず、既存のＦＰＧＡに、本発明の再構成可能なデバイスをエミュレートさせることができる。
【００９１】
例えば、本発明の設計手順は、今日の標準によれば大規模ＦＰＧＡになるものを構成するのに使用することができる。この大規模ＦＰＧＡは、仮想タイルに分割される。この仮想タイルは、今日の標準によれば中規模サイズのＦＰＧＡとなる。大規模ＦＰＧＡを仮想タイルにセグメント化し、かつ、本発明の設計手順を使用して当該大規模ＦＰＧＡを構成することにより、大規模ＦＰＧＡの構成は、簡単になり、仮想タイル間のデータ通信を効率的に実施することができる。
【００９２】
また、本発明の再構成可能なデバイスおよび設計手順は、ＡＳＩＣへの適用範囲も有する。一態様によれば、本発明の設計手順は、特定の用途を有する特定のＡＳＩＣを設計するのに利用される。別の態様によれば、本発明の再構成可能なデバイスは、再構成可能なＡＳＩＣを含む。
【００９３】
上述したように、本発明の設計手順は、既存の再構成可能なデバイスからカスタム回路デバイスを構成するのに使用される。これとは異なり、特定のＡＳＩＣに適用される本発明の設計手順は、特定のＡＳＩＣを設計する。この設計手順を適用して特定のＡＳＩＣを設計する実施の形態では、空間計画は、タイルを形成する１つまたは２つ以上のサブシステムに基づいてタイルを形成する。次いで、配線は、タイル間のデータ通信のパイプライン化および時間多重化用のレジスタおよびスイッチを含む相互接続アーキテクチャを形成する。
【００９４】
この設計手順を適用して特定のＡＳＩＣを設計する別の実施の形態では、タイルおよび相互接続アーキテクチャは、仮想テンプレートを形成する。空間計画ステップ、配線ステップ、およびスケジューリングステップを含む設計手順は、仮想テンプレートのタイルおよび相互接続アーキテクチャを構成する。これに続いて、使用されないタイルおよび相互接続アーキテクチャの資源が、仮想テンプレートから取り除かれ、その結果、特定のＡＳＩＣの設計が得られる。
【００９５】
特定のＡＳＩＣとは異なり、再構成可能なＡＳＩＣは、１群のアプリケーションに対処するように設計される。例えば、再構成可能なＡＳＩＣは、ＤＳＰ業界の用途の範囲に対処するように設計することができる。再構成可能なＡＳＩＣは、タイルおよび相互接続アーキテクチャを備える。再構成可能なＡＳＩＣの一実施の形態では、タイルは、特定用途向けタイルを含む。再構成可能なＡＳＩＣの別の実施の形態では、タイルは、特定用途向けタイルおよび一般用途向けタイルを含む。
【００９６】
再構成可能なＡＳＩＣの場合、設計手順は、再構成可能なＡＳＩＣのハードウェア設計から開始し、後に再構成可能なＡＳＩＣを特定用途向けに構成することで終了する。具体的には、再構成可能なＡＳＩＣの設計は、少なくとも、特定用途向けタイルを形成することによって空間計画を開始する。再構成可能なＡＳＩＣを特定用途向けに構成すると、特定用途向けタイルの中からタイルを選択し、場合によってはそれ以外のサブシステムを一般用途向けタイルに割り当てることにより、空間計画が完了する。また、再構成可能なＡＳＩＣの構成は、上述したような設計手順の配線ステップおよびスケジューリングステップも実施する。
【００９７】
本発明の再構成可能なデバイスの別の実施の形態を図８に概略的に示す。この再構成可能なデバイス８００は、ミニタイル８０３および相互接続アーキテクチャ８０４を備える。相互接続アーキテクチャ８０４は、ミニタイル８０３の交換点８０６に接続される。相互接続アーキテクチャ８０４のデータ搬送セグメント８０８は、ミニタイル８０３をミニタイル８０３の他のものに接続する。また、ミニタイル８０３は、ローカル相互接続８０９を介して、ミニタイル８０３の隣接するものにも接続する。再構成可能なデバイス８００の一実施の形態では、データ交換部８１０が、ミニタイル８０３のそれぞれを相互接続アーキテクチャ８０２に接続する。
【００９８】
ミニタイル８０３の１つの一部およびデータ交換部８１０を図９に概略的に示す。データ交換部８１０は、入力データ搬送セグメント９０２、送出データ搬送セグメント９０４、レジスタ９０６、交換スイッチ９０８、レジスタファイル９１０、ミニタイル出力ポート９１２、ミニタイル入力ポート９１４、入力バイパススイッチ９２０、バイパス９２２、および送出バイパススイッチ９２４を備える。入力データ搬送セグメント９０２は、レジスタ９０６および交換スイッチ９０８を介して送出データ搬送セグメント９０４に接続される。また、入力データ搬送セグメント９０２は、入力バイパススイッチ９２０、バイパス９２２、および送出バイパススイッチ９２４を介することによっても送出データ搬送セグメント９０４に接続する。データ交換部８１０のバイパス回路９２６は、１対の入力バイパススイッチ９２０および送出バイパススイッチ９２４と、バイパス９２２の１つとを備える。
【００９９】
特定のデバイスのクロック速度は、固定される必要はなく、代わりに、その特定のデバイスを構成する際に選択することができる。再構成可能なデバイス８００は、選択されたクロック速度に応じてタイルを決定する柔軟性を提供する。選択されたクロック速度によって、信号が約１クロックサイクル内でミニタイル８０３の１つを横断することが可能になると、タイルのそれぞれは、ミニタイル８０３の１つを構成することになり、このタイルは、第１のタイル８０２Ａとして図８に示す。クロック速度によって、信号がミニタイル８０３の２×２ブロックを横断することが可能になると、タイルは、第２のタイル８０２Ｂを構成することになる。同様に、クロック速度によって、信号がミニタイル８０３の３×３ブロックを横断することが可能になると、タイルは、第３のタイル８０２Ｃを構成することになる。
【０１００】
第２のタイル８０２Ｂおよび第３のタイル８０２Ｃの場合、ミニタイル８０３の１つが複数のタイル内に存在できるように、タイルは重なり合うことができる。このような手法では、タイルは、重なり合ったタイルを含む。例えば、再構成可能なデバイス８００が、重なり合ったタイルで構成される場合、第１のミニタイル８１３は、再構成可能なデバイス８００の端に沿って位置するので、第２のタイル８０２Ｂの２つのものの内部に位置する。第２のミニタイル８２３は、再構成可能なデバイス８００の端に沿って位置しないので、第２のタイル８０２Ｂの４つものの内部に位置する。この状況では、ミニタイル８０３の１つで発生したデータ通信は、ローカル相互接続８０９の１つを通じて、ミニタイル８０３の隣接するものに転送することができる。その理由は、ミニタイル８０３の双方が、第２のタイル８０２Ｂの一部を形成するからである。
【０１０１】
あるいは、第２のタイル８０２Ｂおよび第３のタイル８０２Ｃの場合、タイルは、重なり合わないタイルとして構成することもできる。このような手法では、再構成可能なデバイス８００のタイルが、第１のタイル８０２Ａを構成するのか、第２のタイル８０２Ｂを構成するのか、それとも第３のタイル８０２Ｃを構成するのかにかかわらず、第１のミニタイル８１３および第２のミニタイル８２３は、それぞれ、再構成可能なデバイス８００のタイルの１つの内部に位置する。
【０１０２】
再構成可能なデバイス８００のタイルが、第１のタイル８０２Ａを構成する場合であっても、すなわち、タイルのそれぞれが、ミニタイル８０３の１つを構成する場合であっても、転送源および宛先がミニタイル８０３の隣接するものに位置するときは、ローカル相互接続８０９を通じてデータ通信を配線することがより効率となることがある。また、このような手法は、タイルが、重なり合わないタイルを構成する場合にも有益であり、これによって、ローカル相互接続８０９は、重なり合わないタイルの隣接するもの同士の間でデータ通信を配線することが可能になる。
【０１０３】
第２のタイル８０２Ｂの場合、バイパス回路９２６によって、データ交換部８１０の１つおきのレジスタ９０６およびスイッチ９０８の回りに信号を配線することが可能になると同時に、その場合にも、１クロックサイクル期間内でデータ転送をラッチすることが可能になる。第３のタイル８０２Ｃの場合、バイパス回路９２６によって、データ交換部８１０の２つのレジスタ９０６およびスイッチ９０８の回りに信号を配線することが可能になると同時に、その場合にも、１クロックサイクル期間内でデータ転送をラッチすることが可能になる。
【０１０４】
再構成可能なデバイス８００のタイルは、３×３ブロックの第３のタイル８０３Ｃよりも大きなミニタイル８０３のブロックを含むことができるということが当業者に容易に理解されよう。さらに、デバイス交換部８１０は、レジスタファイル９１０を含む必要がないことも当業者に容易に理解されよう。その上、データ交換部８１０は、バイパス回路９２６を含む必要がないことも、当業者に容易に理解されよう。
【０１０５】
再構成可能なデバイス８００の一実施の形態によれば、複数のミニタイルのデータ交換部を通過する絶対時間がシステムクロック時間と同様になるように、一実施態様は、より速いクロック速度で相互接続をクロック制御することを選択することができる。例えば、３×３ブロックのミニタイルをそのタイルサイズとして使用するシステムの場合、データ交換部は、システムクロックの３倍の周波数でクロック制御を受けることができる。これによって、３つのミニタイルを横切るのと同様の絶対時間を維持しつつ、バイパス回路９２６の使用が回避される。これは、相互接続がより高いスループットを維持できるというさらなる利点を有する。
【０１０６】
本発明の代替的なデータ交換部は、パイプラインステージとして、かつ、場合によっては遅延ステーションまたは並べ替えステーションとして効率的に機能するわずか２つのポートしか有しないことも可能である。本発明の代替的なデータ搬送セグメントは、データ交換部に入る前に複数のタイルまたはミニタイルを横断して、より長い距離にわたるデータ搬送用スイッチをバイパスする高速通路として機能することもできる。この場合も、この代替的なデータ搬送セグメントは、適切な間隔でパイプラインレジスタを保持することができる。
【０１０７】
本発明の上記詳細な説明は、例示の目的で提供されたものであり、本発明を網羅するためのものでもなければ、本発明を開示した実施の形態に限定するためのものでもない。したがって、本発明の範囲は、添付した特許請求の範囲によって規定される。
【図面の簡単な説明】
【０１０８】
【図１】本発明の一実施の形態による再構成可能なデバイスを概略的に示す図である。
【図２】本発明の一実施の形態による再構成可能なデバイスのデータ交換部およびタイルの一部を概略的に示す図である。
【図３】本発明の一実施の形態による再構成可能なデバイスを概略的に示す図である。
【図４】本発明の一実施の形態による再構成可能なデバイスのタイル内の乗算／累積回路を概略的に示す図である。
【図５】本発明の一実施の形態による再構成可能なデバイスを概略的に示す図である。
【図６】本発明の一実施の形態による再構成可能なデバイスのタイル内の除算／記憶回路を概略的に示す図である。
【図７】本発明の一実施の形態による設計手順のフローチャートである。
【図８】本発明の一実施の形態によるミニタイルを含む再構成可能なデバイスを概略的に示す図である。
【図９】本発明の一実施の形態による再構成可能なデバイスのデータ交換部およびミニタイルの一部を概略的に示す図である。
【図１０】本発明の一実施の形態による設計手順のフローチャートである。
【図１１】本発明の一実施の形態による設計手順のフローチャートである。
【図１２】本発明の一実施の形態によるタイル構成を概略的に示す図である。
【図１３】本発明の一実施の形態による設計手順でスケジューリングされたタスク表である。
【図１４】本発明の一実施の形態による設計手順でスケジューリングされたタスク表である。
【図１５】本発明の一実施の形態による設計手順でスケジューリングされたタスク表である。
【符号の説明】
【０１０９】
１００・・・デバイス
１０２・・・タイル
１０４・・・相互接続アーキテクチャ
１０６・・・データ交換点
１０８・・・データ搬送チャネル
１１０・・・データ交換部
【図１】
2005135411.tif 000005
【図２】
2005135411.tif 000006
【図３】
2005135411.tif 000007
【図４】
2005135411.tif 000008
【図５】
2005135411.tif 000009
【図６】
2005135411.tif 000010
【図７】
2005135411.tif 000011
【図８】
2005135411.tif 000012
【図９】
2005135411.tif 000013
【図１０】
2005135411.tif 000014
【図１１】
2005135411.tif 000015
【図１２】
2005135411.tif 000016
【図１３】
2005135411.tif 000017
【図１４】
2005135411.tif 000018
【図１５】
2005135411.tif 000019