(57)【要約】【課題】  ハードウェアソルバの配線遅延および／または輻輳を削減するシステムおよび方法を提供する。【解決手段】  本発明の一実施の形態は、中間コード（５０３）のハードウェアソルバを生成する（５０２）方法であって、ソルバの配線遅延および輻輳の少なくとも一方を引き起こすことがある少なくとも１つのインスタンス化の中間コードを解析すること、少なくとも１つのインスタンス化の補償を形成する（５３３）こと、および補償に従ってソルバを形成する（５０７）こと、を含む方法である。
2006502502.tif 000002
【特許請求の範囲】
【請求項１】
中間コード（５０３）のハードウェアソルバ（hardware solver）を生成する（５０２）方法であって、
前記ソルバの配線遅延および輻輳の少なくとも一方を引き起こすことがある少なくとも１つのインスタンス化の中間コードを解析する（５０８）こと、
前記少なくとも１つのインスタンス化の補償を形成する（５３３）こと、および
前記補償に従って前記ソルバを形成する（５０７）こと、
を含む方法。
【請求項２】
前記インスタンス化は、資源の起こり得る共有であり、
前記補償（５３３）は、前記起こり得る共有が発生するのを防止する、
請求項１に記載の中間コードのハードウェアソルバを生成する方法。
【請求項３】
前記解析する（５０８）ことは、
前記中間コード（５０３）からモデルネットリストを形成する（５３１）こと、
を備え、
前記モデルネットリストは複数のネットを備える、
請求項１に記載の中間コードのハードウェアソルバを生成する方法。
【請求項４】
前記解析する（５０８）ことは、
前記モデルネットリストを複数のパーティションにパーティショニングする（５１２）こと、および
該パーティショニングによってカットされる少なくとも１つのネットを決定すること、
をさらに含む、請求項３に記載の中間コードのハードウェアソルバを生成する方法。
【請求項５】
前記カットされたネットに補償を加える（５３３）こと、
をさらに含む、請求項４に記載の中間コードのハードウェアソルバを生成する方法。
【請求項６】
前記解析する（５０８）ことは、
前記カットされたネットのコストを決定すること、
をさらに含む、請求項４に記載の中間コードのハードウェアソルバを生成する方法。
【請求項７】
前記解析する（５０８）ことは、
各パーティションの面積に関連した値を決定すること、
をさらに含む、請求項４に記載の中間コードのハードウェアソルバを生成する方法。
【請求項８】
前記解析する（５０８）ことは、
前記中間コード（５０３）に対してデータフロー解析を行う（５３０）こと、
を含む、請求項１に記載の中間コードのハードウェアソルバを生成する方法。
【請求項９】
前記ソルバを形成することは、
前記中間コード（５０３−１）を前記補償で変更すること、および
前記変更した中間コードで前記ソルバを形成する（５０７）こと、
を含む、請求項１に記載の中間コードのハードウェアソルバを生成する方法。
【請求項１０】
前記ソルバを形成することは、
少なくとも１つの制約条件（５０９）を前記補償で形成すること、および
前記少なくとも１つの制約条件に従って前記中間コードで前記ソルバを形成する（５０２）こと、
を含む、請求項１に記載の中間コードのハードウェアソルバを生成する方法。
【発明の詳細な説明】
【技術分野】
【０００１】
［発明の分野］
本発明は、包括的には、コンピュータシステムに関し、詳細には、ハードウェアソルバの配線遅延および／または輻輳を削減するシステムおよび方法に関する。
【背景技術】
【０００２】
［関連技術の説明］
設計自動化は、Ｃ等の高級言語で記述されたコンピュータプログラムを取り入れ、そのコンピュータプログラムと同じ機能を有するハードウェア回路を生成するプロセスである。換言すると、プログラムのコードは、そのプログラムの計算を実行する計算（compute）デバイス（乗算器や加算器等）、そのプログラムのデータを記憶するメモリデバイス（レジスタやＲＡＭ等）、およびそのプログラムの命令を実行する制御デバイス（有限状態マシンやマイクロコントローラ等）に変換される。設計自動化の結果生成されたハードウェア回路は、レジスタ転送レベル（ＲＴＬ）で指定される。ＲＴＬは、ハードウェアのすべてのサイクルレベルの構造記述である。この「Ｃ−ｔｏ−ＲＴＬ（ＣからＲＴＬへ）」の自動化が完了すると、物理設計によって、ＲＴＬは、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）やスタンダードセル等の物理バックエンドターゲットにマッピングされる。
【０００３】
図１は、プログラムを処理してチップ設計にするフローチャート１００を示している。このフローチャート１００は、コンピュータプログラム１０１から開始し、このコンピュータプログラム１０１は、コンパイラ１０２によって処理されて中間コード１０３にされる。このコンパイラは、制御フロー解析、データフロー解析、繰り返しスケジューリング等の一般的なコンパイラオペレーションを実行する。また、コンパイラは、デッドコードの削除、強度削減等の最適化も実行する。中間コード１０３は、次に、機能ユニット（ＦＵ）割り当て、スケジューリング、およびハードウェア（ＨＷ）合成１０４を通じて処理される。
【０００４】
ＦＵ割り当て１０４では、例えば加算器や乗算器等の論理デバイスが、中間コード１０３の命令を実行するのに選択される。割り当てられた論理デバイスの量は、通常、目標性能内でタスクを実行するのに必要な最小限度にされる。性能は、通常、ループ開始間隔（ＩＩ（initiation interval））の観点から測定される。ＩＩは、ループの繰り返しを実行するのに利用可能なサイクル数である。ＩＩ＞１である場合、ハードウェアの共有を可能とすることができる。例えば、ＩＩ＝２であり、２つのＡＤＤオペレーションが繰り返し存在する場合、同じ物理的な加算器上で双方のオペレーションを実行することが可能である。一般に、ＦＵ割り当てでは、所与のＩＩのオペレーションを実行できる最少の資源が割り当てられる。
【０００５】
スケジューリングの期間中、中間コードのオペレーションが、特定の時間間隔において、選択された機能ユニット上にスケジューリングされる。ＨＷ合成の期間中、選択された機能ユニットは、ハードウェアコンポーネントとしてインスタンス化され、スケジュールに従って互いに接続され、プログラム１０１と同じ機能を有するハードウェア回路にされる。その結果、ハードウェア回路のレジスタレベルのビューであるネットリスト１０５が生成される。物理設計１０６の期間中、ネットリストは、テクノロジーマッピング、フロアプランニング、配置および配線、タイミング収束、および（必要に応じて）マスク生成を通る。その結果、プログラム１０１の機能を有するターゲット技術のハードウェア１０７が生成される。例えば、ＦＰＧＡのターゲットの結果、ＦＰＧＡファブリックにダウンロードされるビットファイルが生成されることができる。スタンダードセル技術の場合、シリコンへの製造準備ができた１組のマスクが生成される。
【０００６】
このプロセスの特定の使用によって、ネストしたコードループの機能を実行するハードウェアアクセラレータが形成される。このアクセラレータは、コードの一部の機能を効率的に実行するプログラム化できないハードウェア部分であり、通常、ネストしたループである。ネストしたループコードは、外部ループのインクリメントごとに内部ループを繰り返し処理しなければならないので、プロセスにとって非常に多くの時間を要するものとなる可能性がある。したがって、ハードウェアアクセラレータは、少量のチップ面積の価格で同じタスクを非常に高速に実行することができる。
【０００７】
設計自動化プロセスによって生成されたハードウェアソルバは、ハードウェア記述言語（ＨＤＬ）によって構造的に記述される。この記述は、レジスタ転送レベル（ＲＴＬ）記述とも呼ばれる。ＲＴＬ記述は、レジスタ、加算器、ＲＡＭ、マルチプレクサ等のコンポーネントが互いにどのように接続されるかを指定するものである。これらの接続はネットと呼ばれる。ＲＴＬ記述は、１組のネットを定義し、したがって、ネットリストとも呼ばれる。図２は、ネットリスト１０５の一例である。ネットは、１つの出力端子と複数の入力端子との間の１組の接続である。入力端子は、デバイス（レジスタ、乗算器、加算器など）への１ビット入力である。出力端子は、デバイスからの１ビット出力である。例えば、図２は、複数の機能ユニット２０１および１つのネット２０２を示している。別のネットも存在するので、簡単にするために１つのネットしか示していないことに留意されたい。このネットは、入力端子２０３および複数の出力端子２０４を含む。この例では、入力端子２０３は、レジスタからの１ビットの出力である。ネットの長さ、遅延、輻輳への影響等のネットの物理特性はネットリストに記述されないことに留意されたい。
【０００８】
設計自動化プロセスでは、多くの場合、所与の性能目標を満たすことが重要である。性能を満たすために、ハードウェアソルバは、一定のクロック速度で実行できるものでなければならない。これは、あらゆるレジスタ間パスの遅延がクロック周期の範囲内でなければならないことを意味する。例えば、１００ＭＨｚクロックは１０ｎｓのクロック周期を有する。ネットリストのパスが、レジスタ（１ｎｓ）の出力から加算器（４ｎｓ）を通り、マルチプレクサ（２ｎｓ）を通り、そして、レジスタ（１ｎｓ）の入力へ向かうと仮定する。このパスの全遅延は、配線遅延をカウントしないとして、８ｎｓである。このパスに関連した配線遅延が２ｎｓの範囲内である場合、このパスはタイミングを満たす。問題は、バックエンド物理設計プロセス後まで、配線遅延が分からないということである。
【０００９】
既存の設計自動化方法の中には、配線遅延の余地を残すために、１０４の期間中、ハードウェアソルバをオーバ設計することによって配線遅延に対処するものがある。配線遅延用に「見送られた」状態にされたクロック周期の量は、ワイヤリング遊び（wiring slack）、ルーティング遊び（routing slack）、またはジャスト遊び（just slack）と呼ばれる。問題は、回路ごとに配線遅延が大きく変化するということである。或るソルバが配線遅延用にクロック周期の１０％を必要とすることがある一方、別のソルバは２０％を必要とすることがある。これを予測することは、各配線の遅延が、コンポーネントの配置およびバックエンド物理設計中に資源を配線する接続に依存するので、困難となる可能性がある。
【００１０】
配線遅延の変化に対処する１つの方法は、１０４の期間中、積極的なものであって、少量の配線遊びを残すものであり、バックエンド物理設計が失敗すると、異なる遊びの目標により新たなハードウェアソルバを生成するものである。バックエンド物理設計は非常に多くの時間を要するプロセスであるので、この方法は、設計時間が高価となる。別の方法は、控えめなものであり、バックエンド物理設計の実行を必要とする回数が１回のみとなる可能性が非常に高くなるように、十分な配線遊びを残すものである。この方法の欠点は、あまりにも多くの遊びが提供されたことになるので、多くのハードウェアソルバがオーバ設計されることになることである。この結果、必要以上に多くのレジスタが作成されたことになるので、ハードウェアソルバの面積が水増しされたものとなるおそれがある。
【００１１】
配線輻輳は、バックエンド物理設計中に発生する別の問題である。バックエンド物理設計の一部として、ソルバ内の異なる位置に信号を配線しなければならない。これらの信号は、（ＦＰＧＡターゲットにおけるような）固定配線や（スタンダードセルターゲットにおけるような）金属層に作製できる配線等の配線資源上を進む。どの所与のサイクルにおいても、配線は、１つの信号しか転送することができない。その結果、信号は、これらの配線資源を得るために競合しなければならない。配線輻輳は、信号が配線資源を得るために競合することによる信号の干渉である。配線輻輳は、多くの場合、面積、タイミング、および／または電力消費に影響を与える可能性があるので、良くないものである。多くの場合、設計は、これらの面積の１つまたは２つ以上に制約条件を有し、ＲＴＬがあまりにも多くの配線輻輳を引き起こすことによって、要件（例えば、面積、タイミング、電力等）の１つまたは２つ以上が満たされない可能性がある。
【００１２】
配線輻輳問題は、難しいバックエンドターゲット技術ごとに異なることがある。例えば、ＦＰＧＡは、通常、バス、スイッチ、ドライバ、マルチプレクサ等の、固定配線資源によって接続された論理ブロックの格子から構成される。各論理ブロックは、一定の１組の機能を実行することができる。物理設計は、論理合成およびテクノロジーマッピングを含み、これらの論理合成およびテクノロジーマッピングは、レジスタや加算器等のＲＴＬコンポーネントを１組の機能に変換する。この１組の機能のそれぞれは、論理ブロック上で実行することができる。次に、面積を最小にし、かつ、タイミングを満たすように、配置によって、これらの機能が論理ブロックに割り当てられる。問題は、ネットリストがあまりにも多く接続されると、機能間に多くの通信を有する多くの機能を互いに非常に接近させて配置する必要があることである。しかしながら、ＦＰＧＡでは、単位面積あたりの配線資源が一定の量であるので、これらの機能を互いに接近させて配置するのに十分な配線資源が存在しないことがある。これらの接近した配置によって、配線資源のすべてが使い尽くされる。それゆえ、配置アルゴリズムは、より多くの配線資源が利用可能となるように、機能をさらに離して配置しなければならない。しかし、それによって、１）今度は通信がより遠く進まなければならないので、タイミングがより難しくなり、２）機能間の間隔が物理的にさらに離れるので、面積が増加する。
【００１３】
バックエンド物理設計１０６の期間中の配線遅延および輻輳に対処する既存の技法がある。これらの技法には、バッファ挿入、パイプライン化、およびリタイミングが含まれる。タイミング問題および／または輻輳問題を有する配線は、通常、転送素子４０１、４０２（図４）をその配線に追加することによって対処される。例えば、このような素子は、バッファを含むことができ、バッファは、より多くの電流で長い配線の信号をランプアップして、信号がその宛先にクロック周期内で到達できるようにする。しかしながら、バッファを回路に追加することは、面積および電力の点で高価である。
【００１４】
転送素子の別の例はレジスタである。ネットにレジスタを配置することによって、信号は、２つまたは３つ以上の信号に分けられる。これらの信号は、それぞれ、より大きなクロック周期を配線遅延に利用可能とすることができる。ネットにレジスタを配置するのに、リタイミングおよびパイプライン化の２つの既知の技法を使用することができる。リタイミングは、回路内の既存のレジスタを、配線遅延が問題となっているネット等の他の位置に移動させるものである。しかしながら、デバイス（乗算器等）全体にわたって初期値を有するレジスタを移動させることは困難であることから、リタイミングは、多くの場合、使用されない。その理由は、新たな値を求めるには、デバイスの機能を反転する必要があり、これは、多くの場合、不可能なタスクであるからである。さらに、レジスタを回路のサイクルに加える（またはサイクルから除外する）ことができないので、リタイミングは限られたものとなる。したがって、配線遅延問題を有するパスがサイクルの一部であり、配線遅延を補償するのに、そのサイクルの周りで利用可能なレジスタよりも多くのレジスタを必要とする場合には、リタイミングは役立たない。別の技法はパイプライン化である。パイプライン化は、回路の待ち時間を増加させることによって、回路に付加的なレジスタを追加するものである。しかしながら、パイプライン化は、多くの場合、使用されない。その理由は、待ち時間を増加させることによって、回路のＩ／Ｏの振る舞いが変化し、一定の設計にとって許容できないことがあるからである。
【００１５】
物理設計１０６の期間中の配線遅延問題および輻輳問題に対処するこれらの手法は、ＲＴＬネットリスト１０５から開始することに留意されたい。１０４によって決定されるような（ハードウェアソルバ１０５は手作業でも設計されるので、手作業で決定されるような）回路の機能ユニットおよびオペレーションのスケジューリングの混合体は、変更されない。
【００１６】
バックエンド物理設計１０６の期間中、転送素子４０１、４０２を必要とするネットを特定するために、大きな回路は、通常、図４に示すようないくつかのより小さなセグメントに分割される。この分割は、パーティショニング、フロアプランニング、またはクラスタリングと呼ばれ、セグメントは、パーティションまたはクラスタと呼ばれる。したがって、ハードウェアコンポーネント間の通信は、パーティション内通信およびパーティション間通信とみなすことができる。パーティショニングは、パーティション内通信を最大にして、パーティション間通信を制限しようと試みる。本明細書での説明のため、パーティション内接続はローカル配線として定義され、パーティション間接続はグローバル配線として定義される。グローバル信号は、ローカル信号よりも遠くに進まなければならないので、グローバル配線は、通常、ローカル配線よりも大きな配線遅延を有する。
【００１７】
図３は、図２のネットリストの２つのパーティション３０１、３０２へのパーティショニング（バイパーティショニング）を示している。図３では、出力端子２０３および２つの入力端子３０３、３０４は、一方のパーティション３０１に配置される一方、５つの入力端子３０５、３０６、３０７、３０８、３０９は、他方のパーティション３０２に配置される。バイパーティショニングに関連したコストは、カットサイズ（cutsize）と呼ばれる。このカットサイズは、パーティショニングによって「カット」されたネットの個数（パーティション間信号の個数）を指す。図２から、５つの接続、すなわち、出力端子２０３から入力端子３０５、３０６、３０７、３０８、３０９へ通じる接続がカットされることが分かる。しかしながら、それは１つのネットであるので、５つの異なる値ではなく、同じ値が各接続を流れている。したがって、１つのネット３１０のみがカットされ、カットサイズは１である。このビューは、図２の１つのネットのカットを示しているにすぎないことに留意されたい。他のネットもカットすることができ、これは、２つのパーティション３０１、３０２間の別の接続として表される。全カットサイズは、双方のパーティションにおける端子を有するネット数となる。
【００１８】
また、パーティションは、標準的なフロアプランニング技法によっても形成することができる。このフロアプランニング技法では、パーティションは幾何学的に編成することができる。例えば、９つのパーティションは、３×３の２次元パーティション配列を形成することができる。ここで、ｐ００は左上のパーティションであり、ｐ２２は右下のパーティションである。この場合、パーティショニングの品質は、パーティションのカットサイズだけでなく、パーティション配列内におけるネットの及ぶ距離にも基づくことができる。例えば、シミュレーテッドアニーリングアルゴリズムは、各ネットの半周長の点からパーティショニングを評価する。この半周長は、パーティション配列を有するネットによってカバーされた全端子のバウンディングボックスの全周の２分の１に等しい。次に、スパニングツリーおよび／またはシュタイナツリーを介して、転送素子を挿入することができ、これらのツリーは、信号を幾何学的に分散させる一方で、配線長および配線遅延を削減する従来の構造である。
【００１９】
【特許文献１】米国特許出願公開第２００２／１３８８１６号
【特許文献２】米国特許第６０７５９３５号
【特許文献３】米国特許第６４３８７３９号
【非特許文献１】DEY S ET AL: "Exploiting hardware sharing in high-leve synthesis for partial scan optimization" IEEEIACM INTERNATIONAL CONFERENCE' ON COMPUTER AIDED DESIGN. DIGEST OF TECHNICAL PAPERS (ICCAD). SANTA CLARA, NOV. 7 - Il, 1993. LOS ALAMITOS, IEEE. COMP. SOC. PRESS, US, vol. CONF. 11, 7 November 1993 (1993-11-07), pages 20-25, XP010216466 ISBN: 0-8186-4490-7 abstract page 22, column l, paragraph 5 - column 2, paragraph l figure 3 page 23, column l, paragraphs 1,2 page 23, column 2, paragraph 6 page 24, column 2, paragraph 3-7 page 25, column 1, paragraph 5
【非特許文献２】YE TERRY TAO ET AL: "Data path placement with regularity" IEEE ACM INT CONF CCMPUT AIDED DES DIG TECH PAP; IEEEIACM INTERNATIONAL CONFERENCE ON COMPUTER-AIDED DESIGN, DIGEST OF TECHNICAL PAPERS 2000 IEEE, LOS ALAMITOS, CA, USA, 5 November 2000 (2000-ll-05), pages 264-270, XP002280674 abstract page 264, column l, paragraph 4 - column 2, paragraph 3 page 267, column 2, paragraph 4 - page 268, column 2, paragraph 6
【非特許文献３】MOONWOOK OH ET AL: "Rate optimal VLSI design from data flow graph" DESlGN AUTOMATION CONFERENCE, 1998, PROCEEDINGS SAN FRANCISCO, CA, USA 15-19 JUNE 1998, NEW YORK, NY, USA,IEEE, US, 15 June 1998 (1998-06-15), pages ll8-121, XP010309332 ISBN: 0-89791-964-5 abstract page ll8, column l, paragraph 3 page 1l9, column l, paragraph 7 - column 2, paragraph 6
【非特許文献４】PANNER J H ET AL: "A 300 K-circuit ASIC 1ogic family CAD system" IEEE CUSTOM INTEGRATED IRCUIT CCNFERENCE, 13 May 1990 (1990-05-13), pages 104-1, XP01O005367 abstract figure 1 page 10,4.2, column 2, paragraph 2-4
【非特許文献５】BARA S ET AL: "Ultra-fast Poisson's equation solvers using wired-up processors for virtual devices architectures" SEMICCNDUCTOR CONFERENCE, 1999, CAS '99 PROCEEDINGS. 1999 INTERNATIONAL SINAIA, ROMANIA 5-9 OCT, 1999, PISCATAWAY, NJ, USA,IEEE, US, 5 October 1999 (1999-l0-05), pages 249-252. XP010364702 ISBN: 0-7803-5139-8 abstract
【発明の開示】
【課題を解決するための手段】
【００２０】
［発明の簡単な概要］
本発明の一実施の形態は、中間コードのハードウェアソルバを生成する方法であって、ソルバの配線遅延および輻輳の少なくとも一方を引き起こすことがある少なくとも１つのインスタンス化の中間コードを解析すること、少なくとも１つのインスタンス化の補償を形成すること、および補償に従ってソルバを形成すること、を含む方法である。
【００２１】
本発明の別の実施の形態は、中間コードのハードウェアソルバを生成するシステムであって、ソルバの配線遅延および輻輳の少なくとも一方を引き起こすことがある少なくとも１つのインスタンス化の中間コードを解析し、少なくとも１つのインスタンス化の補償を形成する評価器と、補償に従ってソルバを形成するハードウェア合成器と、
を含むシステムである。
【００２２】
本発明の別の実施の形態は、中間コードのハードウェアソルバを生成するコンピュータプログラムロジックが記録されたコンピュータ可読媒体である。このコンピュータプログラムロジックは、ソルバにおける配線遅延および輻輳の少なくとも一方を引き起こすことがある少なくとも１つのインスタンス化の中間コードを解析するロジックと、少なくとも１つのインスタンス化の補償を形成するロジックと、当該補償に従ってソルバを形成するロジックとを含む。
【００２３】
本発明の別の実施の形態は、中間コードのハードウェアソルバの形成を可能にする評価器である。この評価器は、ソルバにおける配線遅延および輻輳の少なくとも一方を引き起こすことがある少なくとも１つのインスタンス化の中間コードを解析する手段と、少なくとも１つのインスタンス化の補償を形成する手段とを備える。それによって、ソルバは、当該補償に従って形成される。
【発明を実施するための最良の形態】
【００２４】
［詳細な説明］
本発明の一実施の形態は、バックエンド物理設計前のハードウェアソルバの自動合成中に配線遅延および／または輻輳に対処する方法である。本発明の一実施の形態は、ハイレベル合成を修正して、成功した物理設計により従順（amenable）であり、かつ、配線遅延および／または輻輳を削減する論理デバイスのネットリストを生成するものである。成功した物理設計は、ＦＰＧＡやスタンダードセル等のターゲット技術の範囲内での面積要件およびタイミング要件を満たす。既存の設計自動化方法は、配線遅延の余地を残すために、ハードウェアソルバをオーバ設計することによって配線遅延に対処する。配線遅延用に「見送られた」状態にされたクロック周期の量は、ワイヤリング遊び、ルーティング遊び、またはジャスト遊びと呼ばれる。問題は、回路ごとに配線遅延が大きく変化し、これを予測することは、各配線の遅延が、コンポーネントの配置およびバックエンド物理設計中の配線資源の競合に依存するので、困難となる可能性があるということである。モデルネットリストは、中間コードから形成されることが好ましく、配線遅延および輻輳に影響を与えることがあるインスタンス化について解析されることが好ましい。解析は、パーティショニングおよび／またはフロアプランニング等のバックエンド物理設計技法を利用するが、ハードウェア割り当ておよびスケジュールの前に行われることが好ましい。本発明の一実施の形態は、次に、インスタンス化の少なくとも１つの補償を形成し、その補償に従ってハードウェアソルバを生成する。その結果生成されるハードウェアソルバは、配線遅延および／または輻輳を削減するように設計された補償による影響を受けたハードウェア混合体（hardware mix）および／またはオペレーションのスケジュールを有する。本発明の一実施の形態によって、設計自動化プロセスは、積極的な遊びの目標を使用するが、それにもかかわらず、バックエンド物理設計の実行を必要とする回数が１回のみとなる可能性を非常に高くすることが可能になる。
【００２５】
本発明は、ハードウェアの割り当ておよびスケジューリングの前および／または期間中におけるハイレベル合成中に動作することが好ましい。本発明は、物理設計中に配線遅延および／または輻輳に影響する可能性のあるプログラムグラフのエッジを特定する。このようなエッジは、通常、プログラムグラフにおいて高いファンアウトを有するか、または、小さなファンアウトを有するが、バックエンド物理設計中に配置の制約条件によりグローバル接続となる。高いファンアウトのプログラムグラフエッジは、通常、ネットリストにおいて、多くの端子を有するネットになる。このネットは、次に、より大きな配線遅延および／または輻輳をもたらす。高いファンアウトのネットの中には、自身の端子を互いに接近して配置できるものがあるが、多くを配置することはできない。本発明は、どのエッジがその端子を互いに接近させる（例えば、ローカル配線で接続される）のに最も適したネットになるかを予測し、その後、どのエッジが、物理設計中にグローバル配線となる可能性がより高いことから、配線遅延および／または輻輳について「問題がある」かを予測することによって、この問題に対処する。本発明は、これら問題のあるエッジから生成されたネットの問題が小さくなるように補償を導入することによって、これら問題のあるエッジを管理する。補償の１つの形は、エッジをパイプライン化する効果を有するものである。すなわち、この補償の１つの形は、問題のあるエッジに沿って付加的な待ち時間を挿入する。最終的なネットリストでは、この補償は、問題のある接続においてレジスタの形を取る。
【００２６】
図５Ａは、本発明の一実施の形態の一例のブロック図を示している。コンポーネント５０１、５０２、および５０３は、それぞれ、図１のコンポーネント１０１、１０２、および１０３と同様のものである。中間コード５０３の形成後、中間コードは、次に、評価器５０８によって処理される。評価器５０８は、コードのどの依存関係がハードウェアの配線遅延および／または輻輳に影響するのかを予測する。評価器は、次に、制約条件５０９および／またはコード５０３の変更として補償をコード５０３−１に導入することによって、これら問題のあるエッジを補償する。補償の１つの形は、信号をパイプライン化するために、問題のある接続にレジスタを導入する効果を有するものである。補償の別の形は、ファンアウトおよびグローバル接続数を削減するために、機能ユニットやレジスタ等のハードウェアコンポーネントの共有を制約するものである。ＦＵ割り当て、スケジューリング、およびハードウェア合成のステップ５０４は、補償されたコード５０３−１および補償制約条件５０９からハードウェアソルバ５０５を作成する。その結果生成されたネットリストの方が、バックエンド物理設計５０６の期間中に成功する可能性が高い。
【００２７】
評価器５０８を図５Ｂに詳細に示す。中間コード５０３は、まず、プログラムグラフ５１０に変換されることが好ましい。問題のあるエッジを特定するために、プログラムグラフは、次に、モデルネットリスト５１１としてモデル化される。このモデルネットリスト内のコンポーネントは、高価な機能ユニットおよびサイクルの時間多重化等の問題に対処するために共にグループ化される（５３２）。その結果、変更されたモデルネットリスト５１１−１が生成される。ノードは、パーティショニングに備えてパーティション編成５１４を決定する（５３４）。パーティショニング５１２によって、５１１−１のコンポーネントは５１４のパーティションに割り当てられ、パーティション間通信の最小化が試みられる。パーティショニングの結果５１２に基づいて、機能ユニット割り当て、スケジューリング、および合成５０４に対する制約条件５０９の形、および／または、コード５０３に対するコード５０３−１への変更の形で、補償がノード５３３に挿入される。
【００２８】
本発明は、従来技術のように、中間コード５０３を、ノードおよびエッジを含むプログラムグラフに変換することが好ましい。ステップ５０８でプログラムグラフを形成するために、プログラムの各オペレーションはグラフのノードになる。プログラムの各フロー依存関係はグラフのエッジになる。エッジは、変数定義（ＤＥＦ）を含んだオペレーションを有するノードを、その変数の定義を使用（ＵＳＥ）できるオペレーションを含んだすべてのノードに接続することによって形成される。プログラムにおけるすべての定義使用（ＤＵ）チェーンを検出する既知の技法が存在する。本発明は、予測された命令のＤＵチェーン解析に或る変更を行うことが好ましい。予測された命令は、述語と呼ばれる特別なオペランドを有し、この述語は、値が０または１であり、命令が実行されるかどうかを決定するものである。プログラムのオペレーションＸからオペレーションＹへの各ＤＵチェーンに対して、本発明は、オペレーションＹに対するＸの述語を定義する、そのオペレーションからの付加的ＤＵチェーンを作成することが好ましい。これらの付加的ＤＵチェーンによって、補償挿入５３３の期間中に特定のタイプの補償を挿入することが可能になる。
【００２９】
図６Ａは、中間コード５０３の一部を示している。図６Ａに示すコード部分は、２つの命令またはオペレーション、すなわち、ＯＰ１  ６０１およびＯＰ２５  ６０２を備える。これらの命令は、ＵＳＥレジスタに検出されたデータに対するコマンドのオペレーションを備えることができる。例えば、ｏｐｃｏｄｅＦおよびｏｐｃｏｄｅＧといったコマンドは、移動（ｍｏｖｅ）、加算（ａｄｄ）、乗算（ｍｕｌｔｉｐｌｅ）、除算（ｄｉｖｉｄｅ）、シフト（ｓｈｉｆｔ）等のコマンドを含むことができる。各命令は、変数の定義（ＤＥＦ）を含む。例えば、ＯＰ１  ６０１は変数ａおよびｂ６０３を定義し、ＯＰ２５  ６０２は変数ｃおよびｄ６０６を定義する。また、各命令は、その計算の一部としても変数を使用する（ＵＳＥ）。例えば、ＯＰ１  ６０１は変数ｙからｚ６０５の内容を使用し、ＯＰ２５  ６０２は変数ａからｑ６０４の内容を使用する。したがって、ＯＰ１は変数ｙからｚのデータに対してｏｐｃｏｄｅＦを実行し、その結果を変数ａおよびｂに置く。ＯＰ１  ６０１は変数ａを定義し、ＯＰ２５は変数ａを使用することに留意されたい。したがって、ＯＰ１とＯＰ２５との間にデータのフロー依存関係６０７が存在する。
【００３０】
図５のプログラムグラフノードの構築５３０は、中間コードをプログラムグラフ５１０に変換する。例えば、図６Ａのコードは、図６Ｂに示すプログラムグラフに変換される。図６Ｂに示すように、ノード６０１−Ｂおよび６０２−Ｂはオペレーションであり、それらノード間のエッジまたは接続６０７−Ｂはそれらオペレーション間の依存関係である。
【００３１】
本発明は、ノードおよびエッジを含んだプログラムグラフ５１０を、コンポーネントおよびネットを含んだモデルネットリストに変換する。本発明は、次に、モデルネットリストを解析して、補償を生成する。モデルネットリストは、ＦＵ割り当ておよび／またはスケジューリングの援助を受けて作成することができるが、実際のＦＵ割り当て、スケジューリング、および合成５０４には使用されない。しかしながら、モデルネットリストから生成された補償５０９および／または５０３−１は、ＦＵ割り当て、スケジューリング、および合成５０４に影響を与える。
【００３２】
プログラムグラフをモデルネットリストに変換するいくつかの方法がある。プログラムグラフのエッジとネットリストのネットとの間には関連性があり、プログラムグラフのノードとネットリストの機能ユニットとの間には関連性があることに留意されたい。しかしながら、この関連性は、オペレーションが機能ユニットではなく、エッジがネットではないことから、１対１にならないことがある。例えば、中間コードの１ビット変数の単一のＤＥＦは、ネットリストの複数のネットになることがある。これは、スケジューラが多くの異なるサイクルで或る変数のＤＥＦおよびＵＳＥをスケジューリングでき、それによって、異なる物理ネットになることによる。しかし、スケジューラは、すべてのＵＳＥを同じサイクルにスケジューリングすることもでき、それによって、単一のネットになる。また、複数のオペレーションが同じ機能ユニットを使用することもできる。例えば、開始間隔（ＩＩ）が１よりも大きなネストループでは、複数のオペレーションを同じ機能ユニットにマッピングできるように、単一の機能ユニットを時間多重することができる。ＩＩが４である場合、ループの繰り返しは、平均して４サイクルごとに完了する。したがって、４つのオペレーションを同じ機能ユニットにマッピングすることができ、例えば、４つの加算オペレーションを同じ加算器にマッピングすることができる。
【００３３】
好ましい手法では、コンポーネントが、プログラムグラフのノードごとにモデルネットリストに作成される。選択されたコンポーネントは、オペレーションを実行できる最小コストの機能ユニットであることが好ましい。例えば、プログラムグラフにＡＤＤ（加算）オペレーションがあり、共にＡＤＤを実行する加算器コンポーネントおよびＡＬＵコンポーネントがあると仮定する。加算器がＡＬＵよりも安価である場合には、加算器コンポーネントがＡＤＤノード用に作成される。また、各コンポーネントには、コンポーネントの面積に密接に関係した重みも与えられる。悲観的な観点では、共有は行われず、コンポーネントの重みは、ちょうど、コンポーネントの面積になる。楽観的な観点では、完全な共有が行われ、コンポーネントの重みは、コンポーネントの面積をＩＩで除算したものとなる。悲観的と楽観的との間の観点を使用することができる。この好ましい観点は、コンポーネントの重みが、コンポーネントの面積をＩＩで除算したものとなる場合に楽観的なものであるが、パーティショニングの前および／または期間中に、ＩＩのバランシング概念を高価なコンポーネントに加えて、この楽観性が正しいことを保証するものである。その後のコンポーネントのグループ化ステップ５３２は、ＩＩバランシングに対処するために、パーティショニングの前に実行されることが好ましい。
【００３４】
好ましい方法では、ネットは、プログラムグラフの各ＤＥＦのモデルネットリストに作成される。プログラムグラフの各エッジは、ＤＵチェーンの結果として、２つのオペレーションを接続することを思い出されたい。モデルネットリストでは、ネットは、所与のＤＥＦに関連付けられたすべてのエッジから作成される。ネットは、ＤＥＦが行われたコンポーネントを、そのＤＥＦの到達ＵＳＥ（reaching USE）を含んだコンポーネントに接続する。
【００３５】
好ましい方法では、各ネットは、変数ＤＥＦのビット幅に従って重み付けされる。ネットの幅は、パーティショニングステップ５１２の期間中にネットをカットするコストを決定するのに使用される。オペレーションは、変数のＸビットのみを定義することが可能であり、このＤＥＦのＵＳＥのいくつかは、そのビットのＷ＜Ｘを使用することが可能である。しかしながら、ほとんどのプログラムは、ＤＥＦの幅およびＵＳＥの幅がほぼ同じであるようになっているので、本発明は、ＤＥＦ変数の幅をネット幅として使用することが好ましい。異なる幅を異なる組に収集して、幅がどのように変化するかに応じて各ＤＥＦについて複数のネットを作成するような代替的な方法も可能である。
【００３６】
モデルネットリストの構築ステップ５３１後の結果は、重み付けネット（幅）および重み付けコンポーネント（面積）を有するモデルネットリストである。
【００３７】
プログラムグラフをモデルネットリストに変換する他の方法が存在する。例えば、各プログラム変数は、その変数のすべてのＤＥＦおよびすべてのＵＳＥを接続することによって、ネットを形成することができる。別の手法は、変数ＤＥＦの各ビットをネットにし、次いで、すべてのネットを幅１にするものである。
【００３８】
本発明は、モデルネットリスト上でパーティショニングアルゴリズムを動作させて、複数のパーティションを形成する。パーティショニングを行うには、パーティションの個数をノード５３４で決定しなければならない。最終的なハードウェアレイアウトを形成するのに使用される物理設計ツールに対してパーティションの個数を較正することができる。代替的に、パーティションの個数を、見積もられた面積に基づくものとすることができる。別の選択肢は、パーティションの個数を試すものであり、或るパーティションの個数が機能しない場合には、別の個数が試される。
【００３９】
パーティションの個数を決定する本発明の好ましい方法は、バックエンド物理設計ツールの較正を介するものである。例えば、バックエンドツールに基づいてパーティションの個数を決定するのにＭｘｐモデル５３５を使用することができる。これによって、例えばＦＰＧＡセルまたはスタンダードセルといったターゲット技術に基づいて、異なる個数のパーティションを使用することが可能になる。Ｍｘｐモデルは、ワイヤリング遊び「ｘ」を有するサイズ「Ｍ」の回路の物理設計がワンパスで成功する確率「ｐ」を決定する。目標確率ｐおよび遊びｘが、自動化された合成プロセスの一部として既知であると仮定すると、その遊びおよび確率に対応する面積Ｍを得るのにＭｘｐモデルを使用することができる。この場合、パーティションの個数Ｎは、Ｍによって分割されたモデルネットリストの面積である。
【００４０】
このように、大きな回路は、Ｎ個の小さな部分回路に分割される。各部分回路のサイズはほぼＭである。部分回路では、部分回路間の接続がほとんどなく、パイプライン化されている。これを達成するために、本発明は、モデルネットリストをＮ個のパーティションにパーティショニングすると同時に、パーティション間通信を最少にする。各パーティションのサイズはほぼＭである。次いで、本発明は、生成された実際のハードウェアソルバが同様の構造を有することを確実にする補償を作成する。
【００４１】
パーティショニング５１２の間、本発明は、異なるパーティション間でコンポーネントを移動させ、カットされたネットの個数および／またはネットがカバーする幾何学的距離を最小にするように試みる。コンポーネントをグループ化するノード５３２は、入力としてモデルネットリストを受け取り、出力としてモデルネットリストを生成する。出力のモデルネットリストでは、元のコンポーネントの一部が、より大きなコンポーネントにグループ化されている。グループ化によって、グループ内のコンポーネントは強制的に同じパーティションにされる。
【００４２】
グループ化する１つの理由は、高価なコンポーネントを確実に共有できるようにするためである。ＩＩ＞１の設計では、多くのオペレーションにわたってコンポーネントを時間多重化することができる。しかしながら、パーティショニング後、ノード５３３は、共有を妨げる補償を挿入する。コンポーネントをグループ化することによって、共有を可能とすることが保証される。好ましい実施の形態では、共有を防止することが面積を増加させる可能性があるので、グループ化は高価なコンポーネントに適用される。例えば、ＩＩ＝２であり、プログラムが、１つの機能ユニットを共有できる２つの除算オペレーション（除算オペレーションは、論理ユニットとして構築する面積および複雑度の点で高価である）を有する場合、これら２つのオペレーションは、同じ除算器コンポーネント上で実行することができる。このように、ＦＵ割り当て器は、２つのオペレーション用に１つの除算器機能ユニットを割り当てることのみを行えばよい。これは、本発明の後のオペレーションが各パーティションに対して個別に実際の機能ユニット割り当てを実行するので、重要である。したがって、同じ機能ユニットを共有でき、異なるパーティションに存在するオペレーションには、別々の機能ユニットが割り当てられる。
【００４３】
高価なコンポーネントをグループ化する好ましい実施の形態は、次の通りである。高価なコンポーネントのタイプが特定される。これは、一定の範囲（例えば、＞２０００ゲート）とすることもできるし、モデルネットリストの総面積の或る割合（例えば、＞５％）とすることもできる。一般に、本発明は、たとえ、グループ化が場合によって共有を防止することになっても、安価なコンポーネントをグループ化しないことを好む。コンポーネントは安価であるので、最終的なネットリストに追加される面積は小さくなり、最終的なネットリストが物理設計に対してより従順であるという利点がある。次に、各タイプのコンポーネントの個数が求められる。共有が可能である場合、ＩＩのバランシングが各コンポーネントタイプについて実行される。パーティション間の共有が許容されていないと仮定すると、ＩＩのバランシングは、パーティショニングを伴わないコンポーネントの最小数が、パーティショニングを伴うコンポーネントの最小数と同じであることを必要とする。換言すると、ＮをタイプＸのコンポーネントの個数とし、Ｎｉを、パーティションｉにおけるタイプＸのコンポーネントの個数とすると、ＩＩのバランシングは、ｃｅｉｌ（Ｎｉ／ＩＩ）の（すべてのｉにわたる）総和＝ｃｅｉｌ（Ｎ／ＩＩ）であることを必要とする。例えば、Ｎ＝８、ＩＩ＝３とする。３つのパーティションを仮定し、Ｎ１＝３、Ｎ２＝４、Ｎ３＝１とする。この場合、ｃｅｉｌ（Ｎｉ／ＩＩ）の（すべてのｉにわたる）総和＝ｃｅｉｌ（３／３）＋ｃｅｉｌ（４／３）＋ｃｅｉｌ（１／３）＝４となる。しかし、ｃｅｉｌ（８／３）＝３である。したがって、これはバランスされていない。しかし、Ｎ１＝３、Ｎ２＝３、Ｎ３＝２は、ｃｅｉｌ（３／３）＋ｃｅｉｌ（３／３）＋ｃｅｉｌ（２／３）＝３となるので、バランスされている。
【００４４】
ＩＩのバランシングを実行するいくつかの方法がある。好ましい方法では、欲張りアルゴリズムが使用される。高価な各コンポーネントタイプは、最も高いものから最も低いものへと処理される。ノード５１２のアルゴリズム等のパーティショニングアルゴリズムは、パーティションの空間を探索するのに使用される。このタイプについてＩＩのバランシングも行われる最も良いパーティションは、グループ化を決定するのに使用される。同じパーティションに割り当てられている現在のタイプのコンポーネントは、共にグループ化される。この場合、アルゴリズムは、次の最も高価なコンポーネントタイプに対して繰り返されるが、パーティショニング中、前のグループ化が順守される（honor）。すべてのコンポーネントタイプが考慮された後、ＩＩのバランシングが保証されるように、すべての高価なコンポーネントがグループ化される。パーティショニングは、長く実行されるほど、より良い結果を生成するので、このステップのパーティショニングは、高価なタイプの個数および利用可能なコンパイル時間量に応じて、速くなることもあるし、遅くなることもあることに留意されたい。
【００４５】
プログラムグラフのサイクルも、コンポーネントのグループ化を引き起こすことがある。コンピュータプログラムは、一定のオペレーションがどのようにスケジューリングされるか、または、いつスケジューリングされるかを制約する変数を使用するサイクルを有することが多い。例えば、プログラムグラフがＯＰＢに依存するＯＰＡを有し、ＯＰＢがＯＰＣに依存し、ＯＰＣがＯＰＡに依存すると仮定する。繰り返しの全体にわたる依存関係およびＩＩを調べることによって、オペレーションのサイクルの周りにあるスケジューリング遊びを決定することができる。スケジューリング遊びは、スケジューリング中に、依存したオペレーションを切り離すことができる余分な個数のサイクルである。プログラムグラフのサイクルは、その利用可能な遊びの観点から常に仕切られている。これらのオペレーションを異なるパーティションに配置することは、スケジューリングに違反することがある。その理由は、ノード５３３における補償の挿入がスケジューリング遊びの量を削減することがあるからである。
【００４６】
サイクルを取り扱う好ましい方法は、サイクルを形成するすべてのオペレーションに関連付けられたコンポーネントをグループ化することである。これは、標準的な方法のように、プログラムグラフを解析して、強連結成分（ＳＣＣ（strongly connected component））をすべて見つけることによって行うことができる。グラフのＳＣＣは、そのグラフのサイクルのすべてを表す。
【００４７】
別の手法は、パーティショニング中に遊びを有するサイクルを取り扱うものである。パーティショニングのコスト関数の一部として、パーティショニングによってカットされたサイクルの周りの遊びの量を評価しなければならない。どのサイクルについても、０よりも少ない遊びを有するパーティショニングは、最終的なパーティショニングとして選択されることはない。
【００４８】
グループ化が完了した後、新たなモデルネットリストが形成される。この新たなモデルネットリストでは、各グループが単一のコンポーネントとなり、コンポーネントの重みがそのグループ内のコンポーネントの重みの総和であり、グループ内のコンポーネントに接続するどのネットも新たなコンポーネントに接続する。コンポーネントをグループ化するノード５３２の出力は、新たなモデルネットリスト５１１−１である。
【００４９】
パーティショニングノード５１２は、ローカルネットおよびグローバルネットを識別するために、バックエンド物理設計からの標準技法をモデルネットリストに適用する。例えば、パーティションの面積バランスが相対的に図られ（あらゆる所与のパーティション内のコンポーネントの総面積が下限を有する）、パーティション間通信が最小になるように、パーティショニング／配置／フロアプランニングは、ネットリストのコンポーネントをパーティションに割り当てる。パーティショニング後、パーティション間のネットはグローバルネットとして取り扱われる。グローバルネットに対応するプログラムグラフのエッジは、補償を必要とする問題のあるエッジとしてのタグが付けられる。
【００５０】
パーティションの個数５１４およびモデルネットリスト５１１−１が与えられると、本発明はパーティショニング５１２を実行する。より具体的には、本発明は、モデルネットリストの各コンポーネントをＮ個のパーティション５１４の１つに割り当てる。パーティションの重み（パーティション内のすべてのコンポーネントの総和）がパーティション間でバランスされるように、すなわち、パーティションが重みにおいてほぼバランスされるように、評価器はコンポーネントをパーティションに割り当てる。このバランシングは、正確である必要はないが、約１０％内に維持されることが好ましい。また、評価器は、ネットのカットのコストおよび／またはネットがカバーする幾何学的距離が最小になるように、コンポーネントをパーティションに割り当てる。
【００５１】
本発明は、トポロジー的パーティショニングまたは幾何学的パーティショニングをサポートすることができる。トポロジー的パーティショニングでは、本発明は、再帰的なバイパーティショニングを使用して、Ｎ個のパーティションを得ることが好ましい。例えば、ＫＬＦＭ（Kernigham, Lin, Fiduccia, Mattheyses）といったバイパーティショニングを実行する標準的なアルゴリズムが存在する。
【００５２】
幾何学的パーティショニングでは、本発明は、標準的なフロアプランニング技法を使用することが好ましい。まず、Ｎ個のパーティションが幾何学的に編成される。例えば、本発明は、９個のパーティションが３×３の２次元パーティション配列を形成すると仮定することができる。ここで、ｐ００は左上のパーティションであり、ｐ２２は右下のパーティションである。この場合、パーティショニングの品質は、パーティションのカットサイズだけでなく、パーティション幾何学的配列内におけるネットの及ぶ距離にも基づく。例えば、シミュレーテッドアニーリングアルゴリズムは、各ネットの半周長の点からパーティションを評価する。この半周長は、パーティション配列内のネットによってカバーされた全端子のバウンディングボックスの全周の２分の１に等しい。
【００５３】
双方の技法は、カットされたネットの個数および／またはネットがカバーする幾何学的距離を最小にしつつ、コンポーネントをパーティションに割り当てる。パーティショニングの完了後、本発明は、コンポーネントのパーティションへの割り当て５１３を返す。
【００５４】
本発明は、パーティショニングから導出された情報を使用して、２つの方法の一方または双方で補償を挿入する。この補償は、ＦＵ割り当て、スケジューリング、およびＨＷ合成５０４に対して、それらのオペレーション時に制約条件５０９として提供することができる。また、この補償は、中間コード５０３をコード５０３−１に変更することによって提供することもできる。この補償は、変更された中間コード５０３−１および制約条件５０９の双方を含むこともできる。中間コード５０３−１は、次に、評価器５０８が作成した制約条件５０９（もしあれば）に従い、機能ユニット（ＦＵ）割り当て、スケジューリング、およびハードウェア（ＨＷ）合成と通じて処理される。その結果、ハードウェアソルバのレジスタレベルのビューを表すネットリスト５０５が生成され、プログラム１０１の機能を有し、これに加えて、補償５０９／５０３−１の特性も有する。
【００５５】
本発明は、２つの形の補償の一方または双方を導入して、配線遅延および／または輻輳を取り扱うことが好ましい。タイプ１の補償は、信号をパイプライン化するために、パーティション間接続にレジスタを導入する効果を有するものである。タイプ２の補償は、ファンアウト、輻輳、およびグローバル接続数を削減するために、機能ユニットやレジスタ等のハードウェアコンポーネントの共有を制限するものである。
【００５６】
本発明は、モデルネットリストのカットされた各ネットが物理ネットリストでは少なくとも２つのネットになるように、タイプ１の補償を導入することが好ましい。これら２つの物理ネットは、１つまたは２つ以上のレジスタによって接続されることになる。この補償を作成するために、本発明は、１つまたは２つ以上の明示的なＭＯＶＥオペレーションをプログラムに挿入することが好ましい。例えば、カットされたネットは、一方のパーティションに単一のＤＥＦおよび０または１つ以上のＵＳＥを有し、他方のパーティションに１つまたは２つ以上のＵＳＥを有する。ネットのＤＥＦを含んだパーティション以外のＵＳＥは、ネットから除去され、１つまたは２つ以上のＭＯＶＥオペレーションからのＵＳＥによって置き換えられる。このＭＯＶＥオペレーションは、スケジュールにおいて少なくとも１サイクルを要する。（ゼロサイクルのＭＯＶＥオペレーションが存在する場合には、これら挿入されたＭＯＶＥオペレーションは、スケジューリング中に、ゼロサイクルのＭＯＶＥオペレーションと区別されるべきであることに留意されたい。）ＭＯＶＥオペレーションは、互いに接続されて、ネットのパイプラインを提供することができる。このパイプラインは、物理ネットリストでは、レジスタのパイプラインとなる。
【００５７】
図７Ａ〜図７Ｄは、カットされたネットに遅延を加える好ましい方法を示している。図７Ａおよび図７Ｂは、プログラムグラフ、したがって中間コード５０３−１に移動オペレーションを挿入することを含んでいる。これは、移動が少なくとも１サイクルのオペレーションを必要とし、少なくとも１つのレジスタを変更されたネットリストに加えることを前提としていることに留意されたい。したがって、移動の挿入は、モデルネットリストおよびその結果生成される物理ネットリスト５０５に遅延を加える。
【００５８】
図７Ａは、図７Ｂの中間コードのプログラムグラフを示している。５つのＤＥＦ、すなわちＡ、Ｂ、Ｃ、Ｄ、およびＥがあることに留意されたい。これは、５つのネットがあることを意味する。しかしながら、簡略化のために、ＤＥＦ  Ａ  ７０１のネットのみが示されている。ＤＥＦ  Ａは、４つのＵＳＥ７０２、すなわちＢ、Ｃ、Ｄ、およびＥを有する。これらのＵＳＥのうちの２つ、すなわちＤおよびＥは、ＤＥＦ  Ａと共に或るパーティションにあり、それ以外の２つ、すなわちＢおよびＣは、別のパーティション７０４にある。図７Ｃは、プログラムグラフおよび中間コードへの移動オペレーションＦ７０５の挿入を示している。したがって、ＦはＡのＵＳＥとなり、ＢおよびＣはＦのＵＳＥ７０６となる。このように、Ｆの挿入によって、少なくとも１サイクルの遅延が提供される。この遅延は、基本的に、パーティション間からのデータをパイプライン化する。
【００５９】
タイプ１の補償を提供する代替的な方法も存在する。例えば、タイプ１の補償は、スケジューラ５０４に対する制約条件５０９の形を取ることができる。タイプ１の補償は、スケジューラが、異なるパーティションで生成された値を使用するオペレーションの最も早い開始時間を増加させることを要求することができる。増加量は、パーティション間の所望の遅延に対応する。また、制約条件５０９は、ＨＷ合成器が、モデルネットリストのパーティショニングから決定された通りに、必要な遅延をカットされた接続部に挿入しなければならないことを示すこともできる。
【００６０】
タイプ１の補償の例として、８つのＵＳＥを有し、一方のパーティション「Ａ」には、ＤＥＦおよびこれらＵＳＥのうちの４つを有し、他方のパーティション「Ｂ」には、それ以外の４つのＵＳＥを有するプログラムグラフＤＥＦについて考える。補償がない場合には、このＤＥＦは、ハードウェアソルバにおいて、パーティション「Ａ」に５つの端子およびパーティション「Ｂ」に４つの端子の９つの端子を有する単一のネットになることがある。補償がある場合には、このプログラムエッジは、ハードウェアソルバにおいて、５つのパーティション「Ａ」コンポーネントと移動コンポーネントを接続する１つまたは２つ以上のネット、および、４つのパーティション「Ｂ」端子と移動コンポーネントを接続する１つまたは２つ以上のネットの少なくとも２つのネットになる。ＭＯＶＥオペレーションの結果生成されたレジスタは、パーティション間の信号伝送に遅延を加える。したがって、信号は、パーティション間でパイプライン化される。この補償は、このパイプライン化が最終的なネットリストに組み込まれることを保証する。したがって、過剰な配線遅延を有するネットになった可能性のあるものは、パーティションの境界にわたってパイプラインステージを備えた、遅延のより小さな１つまたは２つ以上のネットに置き換えられる。
【００６１】
幾何学的パーティショニングの場合、本発明は、複数のパーティションに及ぶネットに対して、異なるタイプのタイプ１の補償を挿入することができる。例えば、スパニングツリーおよび／またはシュタイナツリーを形成してＵＳＥを接続する多くの移動オペレーションを作成することができる。スパニングツリーおよびシュタイナツリーは、信号を幾何学的に分散させる一方で、配線長および配線遅延を削減する従来の構造である。
【００６２】
タイプ１の補償は、問題のある接続に沿ってレジスタを加えるので、物理設計中、タイミング収束はより簡単に行われ、回路は、物理設計中に、バッファおよび／またはレジスタを配線に追加して挿入することを必要としないことがある。補償はスケジューリング前に挿入されるので、本発明は、パイプライン化の適用および既存のネットリストに対するリタイミングとは異なるネットリストになることがあることに留意されたい。本発明の結果生成されたネットリストは、タイプ１の補償なしに作成されたネットリストにパイプライン化およびリタイミングを適用したネットリストとは異なる機能ユニット混合体およびオペレーションのバインドを有することがある。
【００６３】
タイプ２の補償は、結果として生成されるハードウェアソルバの通信の集中化を少なくして当該通信を分散させるために資源の共有を制限することによって、配線遅延および輻輳を削減するものである。通信が集中すると、配線輻輳がより多くなる。好ましい方法では、タイプ２の補償は制約条件５０９の形を取る。この制約条件によって、ＦＵ割り当ては、パーティションごとに、それ以外のパーティションのＦＵ割り当てから独立して行われる。スケジューリング中、各オペレーションの代替リストは、そのオペレーションのパーティション内の機能ユニットに制限される。これによって、モデルネットリストにおいて遠く離れているとみなされる２つのオペレーション（例えば、それらのオペレーションは異なるパーティションにある）が物理ネットリストの同じ機能ユニットハードウェアを共有することが防止される。
【００６４】
例えば、或るパーティションにおける２つのオペレーションｚ＝ｘ＋ｙ；ｗ＝ｚ＊ｒ、および、別のパーティションにおける２つのオペレーションａ＝ｂ＋ｃ；ｇ＝ａ／ｄを考える。この＋オペレーションが、同じ加算器機能ユニットを共有する場合、その加算器を、ｚ＊ｒをマッピングする乗算器およびａ／ｄをマッピングする除算器に接続しなければならない。したがって、加算器の結果を双方のパーティションに接続しなければならない。これは、この特定の共有が認められない場合よりも多くの配線遅延を要する可能性がある。さらに、配置アルゴリズムは、加算器、乗算器、および除算器を互いに接近して配置することを好む。なお、これは、配線輻輳につながる可能性がある。
【００６５】
タイプ２の補償の別の形は、データの記憶の共有を防止するものである。好ましい方法では、あらゆる変数が各パーティションにおいて一意に改名されるように、コードが変更される。このコードの変更によって、記憶の合成が、所与の変数の同じ記憶構造体を使用しようとすることが防止される。本発明は、以下の方法で、予測されたオペレーションを取り扱うことが好ましい。変数が相互排他述語（mutual exclusive predicate）の下で複数の定義を有する場合、別のパーティションのｕｓｅに到達する定義は、そのＵＳＥを含むパーティションでマージされることが好ましい。プログラムグラフの作成５０８中にＤＵチェーンの生成に拡張することによって、所与のｕｓｅについて到達するすべての定義の述語が同じパーティション内になる。その結果、マージを実行するのに必要なオペランドがそのパーティションで利用可能となる。好ましい方法では、マージは、複数の述語付きＭＯＶＥオペレーションをコード５０３−１に挿入することによって行われる。
【００６６】
タイプ２の補償の別の手法は、制約条件５０９を追加することであって、制約条件５０９は、記憶の合成が、異なる変数が同じ記憶構造体を共有することを許さないようにすることである。
【００６７】
本発明の結果は、物理設計に対してより従順なネットリスト５０５となる。詳細には、結果として生成されるハードウェアソルバは、ハードウェア混合体と、配線遅延および／または輻輳を削減するように設計された補償によって影響を受けたオペレーションのスケジュールとを有する。本発明によって、タイミング駆動スケジューラは、積極的な遊びの目標を使用することが可能となる一方で、依然として、バックエンド物理設計の実行を必要とする回数が１回のみとなる可能性を非常に高くすることが可能となる。
【００６８】
図９Ａ〜図９Ｇは、コード部分が、図５Ａ〜図５Ｂの本発明の実施の形態によって動作されることを示している。図９Ａは、８つのオペレーションを有するＦＩＲフィルタのカーネルの中間コードを示している。８つのオペレーションは、分岐ＯＰ２７５、２つの加算ＯＰ６２、ＯＰ７５、１つの移動ＯＰ１００、２つのロードＯＰ１０７、ＯＰ１１４、乗加算ＯＰ１２８、および記憶ＯＰ１５３を含む。２１８、２、３、５、６、７、および１２８の番号が付けられた７つの変数がある。表記ｖａｒ＿ｎｕｍ［１］は、前の繰り返しからの変数の参照であり、データ依存関係も引き起こすことになることに留意されたい。目標性能はＩＩ＝２として与えられる。
【００６９】
図９Ｂは、コード９０１においてノード５３０により作成されたプログラムグラフ９０２を示している。各ノードプログラムグラフについて、最初の行にはＵＳＥが列挙され、第２行にはＯＰが列挙され、第３行にはＤＥＦ（もしあれば）が列挙されている。オペランドの幅も設けられている。
【００７０】
図９Ｃは、プログラムグラフ９０２からのノード５３１によって作成されたモデルネットリスト９０３を示している。各コンポーネントについて、コンポーネントの一部であるオペレーションに加えて、重み（例えば、面積）も列挙されている。各ネットについて、ネットによって定義された変数に加えて、重み（例えば、幅）も列挙されている。例えば、コンポーネント１００３は、１５２の重みを有し、加算オペレーション７５から作成され、ネット１０２に接続される。ネット１０２は、３２の重みを有し、変数３から作成されたものである。
【００７１】
図９Ｄは、コンポーネントがノード５３２によってグループ化されていないと仮定して、モデルネットリスト９０３からのノード５１２によって作成されるバイパーティショニング９０４を示している。２つのパーティション９０５および９０６が形成されている。カットサイズは、パーティショニングによってカットされたネットの全重みである。この場合、９０５および９０６によってカットされたネットは、ネット１０７（重み１）、ネット１０５（重み１６）、およびネット１０６（重み１６）であり、３３のカットサイズをもたらす。
【００７２】
図９Ｅは、コンポーネントをグループ化するノード５３２の後のネットリストを示している。簡略化のために、図９Ｅの例は、加算器コンポーネントのＩＩのバランシングに関してのみ、このノードのオペレーションを示している。モデルネットリスト９０３は、２つの加算器コンポーネント１００５および１００３を有する。各加算器コンポーネントは１５２の重みを有する。モデルネットリストは、これらが高価なコンポーネントであると判断するものと仮定する。ＩＩ＝２であるので、それらの加算器コンポーネントは、ステップ５３２によって共にグループ化される。その結果生成されるモデルネットリスト９０７を図９Ｅに示す。モデルネットリスト９０３からのコンポーネント１００５および１００３は、モデルネットリスト９０７のコンポーネント１００９によって置き換えられていることに留意されたい。この新たなコンポーネント１００９の重みは３０４であり、このコンポーネントは、ネット１０７、１０２、および１０３を接続する。
【００７３】
図９Ｆは、モデルネットリスト９０７からのノード５１２によって作成されたバイパーティショニング９０８を示している。２つのパーティション９０９および９１０が形成されている。２つの加算オペレーション７５、６２は、ここでは、同じパーティション９０９にある一方、グループ化ステップがない場合に、それらのオペレーションは、図９Ｄに示すように異なるパーティションにあることに留意されたい。したがって、これらの加算は、パーティショニング９０８の同じハードウェアを共有することができる一方、２つの加算器は、パーティショニング９０４に必要とされていたことになる。しかしながら、パーティショニング９０８のカットサイズは、ここでは、グループ化のために、５７に増加されている（ネット１０７、１０２、１０４、および１０６は、それぞれ、１、３２、８、および１６の重みでカットされる）。
【００７４】
図９Ｇは、９０８のパーティショニングにおいてノード５３３により形成されたコードのプログラムグラフ９１１を示している。補償の第１の形は、ＦＵ割り当ておよびスケジューリングに対する制約条件である。オペレーションは、パーティション９１２および９１３にグループ化されている。機能ユニット割り当てが、各パーティションに対して、他のパーティションとは独立に行われる。さらに、スケジューリングが、対応するパーティションからの機能ユニットにオペレーションをマッピングするもののみに制約される。補償の別の形はＭＯＶＥオペレーションである。この例では、２つの移動オペレーションが、カットされた各ネットに追加された。例えば、述語変数２１８は、述語移動オペレーションＯＰ２８１およびＯＰ２８２を介して、パーティション９１２からパーティション９１３へ移動される。２１８のファンアウトは削減されており、これは配線遅延を削減できることに留意されたい。元のプログラムグラフ９０２では、変数２１８のファンアウトは７であった。補償後のプログラムグラフ９１１では、２１８のファンアウトは５である。９０２における２１８の他の３つのＵＳＥは、ここでは、９１１の新たな述語変数２２２によって駆動される。ファンアウトの削減に加えて、補償により、最終的なネットリストは、小さなサイズの部分回路を有する。これらは、図９Ｇのパーティション９１２および９１３として識別することができる。これらのパーティションのそれぞれは、それ自身の機能ユニット割り当てを有し、したがって、それ自身の部分回路となる。さらに、パーティション間の移動はレジスタになり、したがって、バックエンド物理設計は、依然としてタイミングを満たしつつ、これらのパーティションを遠く離れて配置する柔軟性を有することになる。
【００７５】
ソフトウェアで実施された場合、本発明の要素は、基本的に、必要なタスクを実行するコードセグメントとなる。プログラムまたはコードセグメントは、プロセッサ可読媒体に記憶することもできるし、搬送波に具現化されたコンピュータデータ信号または搬送波によって変調された信号により伝送媒体を介して伝送することもできる。「プロセッサ可読媒体」には、情報を記憶または転送できるあらゆる媒体が含まれ得る。プロセッサ可読媒体の例には、電子回路、半導体メモリデバイス、ＲＯＭ、フラッシュメモリ、消去可能ＲＯＭ（ＥＲＯＭ）、フロッピィ（登録商標）ディスケット、コンパクトディスクＣＤ−ＲＯＭ、光ディスク、ハードディスク、光ファイバ媒体、無線周波数（ＲＦ）リンク等が含まれる。コンピュータデータ信号には、電子ネットワークチャネル、光ファイバ、大気、電磁気、ＲＦリンク等の伝送媒体を介して伝播できるあらゆる信号が含まれ得る。コードセグメントは、インターネットやイントラネット等のコンピュータネットワークを介してダウンロードすることができる。
【００７６】
図８は、本発明を使用するように適合されたコンピュータシステム８００を示している。中央処理装置（ＣＰＵ）８０１は、システムバス８０２に接続される。ＣＰＵ８０１は、ＨＰのＰＡ−８５００やIntelのＰｅｎｔｉｕｍ（登録商標）プロセッサ等の任意の汎用ＣＰＵとすることができる。しかしながら、本発明は、ＣＰＵ８０１が、本明細書で説明したような本発明のオペレーションをサポートする限り、ＣＰＵ８０１のアーキテクチャによって限定されるものではない。バス８０２は、ランダムアクセスメモリ（ＲＡＭ）８０３に接続される。ＲＡＭ８０３は、ＳＲＡＭ、ＤＲＡＭ、またはＳＤＲＡＭとすることができる。ＲＯＭ８０４もバス８０２に接続される。ＲＯＭ８０４は、ＰＲＯＭ、ＥＰＲＯＭ、またはＥＥＰＲＯＭとすることができる。ＲＡＭ８０３およびＲＯＭ８０４は、当該技術分野で既知のように、ユーザデータおよびシステムデータならびにプログラムを保持する。
【００７７】
バス８０２は、入出力（Ｉ／Ｏ）コントローラカード８０５、通信アダプタカード８１１、ユーザインターフェースカード８０８、および表示カード８０９にも接続される。Ｉ／Ｏアダプタカード８０５は、ハードドライブ、ＣＤドライブ、フロッピィディスクドライブ、テープドライブの１つまたは２つ以上のもの等の記憶デバイス８０６をコンピュータシステムに接続する。Ｉ／Ｏアダプタ８０５は、プリンタ８１４にも接続される。プリンタ８１４によって、システムは、文書、写真、記事等の情報の用紙のコピーを印刷することが可能になる。このプリンタは、プリンタ（たとえば、ドットマトリックス、レーザ等）、ファックス装置、または複写機装置とすることができることに留意されたい。通信カード８１１は、コンピュータシステム８００をネットワーク８１２に接続するように適合される。ネットワーク８１２は、電話網、ローカルエリアネットワーク（ＬＡＮ）および／もしくはワイドエリアネットワーク（ＷＡＮ）、イーサネット（登録商標）ネットワーク、ならびに／またはインターネットネットワークの１つまたは２つ以上とすることができる。ユーザインターフェースカード８０８は、キーボード８１３、ポインティングデバイス８０７、マイク８１６等のユーザ入力デバイスをコンピュータシステム８００に接続する。また、ユーザインターフェースカード８０８は、スピーカ（または複数のスピーカ）８１５を介してユーザに音出力も提供する。表示カード８０９は、ＣＰＵ８０１によって駆動されて、表示デバイス８１０上の表示を制御する。
【図面の簡単な説明】
【００７８】
【図１】従来技術による、プログラムを処理してチップ設計にするフローチャートである。
【図２】一般的なネットリストの一例を示す図である。
【図３】従来技術による、図２のネットリストの２つのパーティション３０１へのパーティショニングを示す図である。
【図４】図３のパーティションの異なるビューを示す図である。
【図５Ａ】本発明の一実施の形態の一例のブロック図である。
【図５Ｂ】本発明の一実施の形態の一例のブロック図である。
【図６Ａ】本発明による、中間コードおよび関連したプログラムグラフの一部を示す図である。
【図６Ｂ】本発明による、中間コードおよび関連したプログラムグラフの一部を示す図である。
【図７Ａ】本発明による、カットされたネットに遅延を加える好ましい方法を示す図である。
【図７Ｂ】本発明による、カットされたネットに遅延を加える好ましい方法を示す図である。
【図７Ｃ】本発明による、カットされたネットに遅延を加える好ましい方法を示す図である。
【図７Ｄ】本発明による、カットされたネットに遅延を加える好ましい方法を示す図である。
【図８】本発明を使用するように適合されたコンピュータシステムのブロック図である。
【図９Ａ】８つのオペレーションを有するＦＩＲフィルタのカーネルにおける本発明のオペレーションの一例を示す図である。
【図９Ｂ】８つのオペレーションを有するＦＩＲフィルタのカーネルにおける本発明のオペレーションの一例を示す図である。
【図９Ｃ】８つのオペレーションを有するＦＩＲフィルタのカーネルにおける本発明のオペレーションの一例を示す図である。
【図９Ｄ】８つのオペレーションを有するＦＩＲフィルタのカーネルにおける本発明のオペレーションの一例を示す図である。
【図９Ｅ】８つのオペレーションを有するＦＩＲフィルタのカーネルにおける本発明のオペレーションの一例を示す図である。
【図９Ｆ】８つのオペレーションを有するＦＩＲフィルタのカーネルにおける本発明のオペレーションの一例を示す図である。
【図９Ｇ−１】８つのオペレーションを有するＦＩＲフィルタのカーネルにおける本発明のオペレーションの一例を示す図である。
【図９Ｇ−２】８つのオペレーションを有するＦＩＲフィルタのカーネルにおける本発明のオペレーションの一例を示す図である。
【符号の説明】
【００７９】
５０３  中間コード
５０５  ハードウェアソルバ
５０６  バックエンド物理設計
５０８  評価器
５０９  制約条件
８００  コンピュータシステム
８０１  中央処理装置（ＣＰＵ）
８０２  システムバス
８０３  ランダムアクセスメモリ（ＲＡＭ）
８０４  ＲＯＭ
８０５  Ｉ／Ｏアダプタ
８０６  記憶デバイス
８０７  ポインティングデバイス
８０８  ユーザインターフェースカード
８０９  表示カード
８１０  表示デバイス
８１１  通信アダプタカード
８１２  ネットワーク
８１３  キーボード
８１４  プリンタ
８１５  スピーカ
８１６  マイク
【図１】
2006502502.tif 000003
【図２】
2006502502.tif 000004
【図３】
2006502502.tif 000005
【図４】
2006502502.tif 000006
【図５Ａ】
2006502502.tif 000007
【図５Ｂ】
2006502502.tif 000008
【図６Ａ】
2006502502.tif 000009
【図６Ｂ】
2006502502.tif 000010
【図７Ａ】
2006502502.tif 000011
【図７Ｂ】
2006502502.tif 000012
【図７Ｃ】
2006502502.tif 000013
【図７Ｄ】
2006502502.tif 000014
【図８】
2006502502.tif 000015
【図９Ａ】
2006502502.tif 000016
【図９Ｂ】
2006502502.tif 000017
【図９Ｃ】
2006502502.tif 000018
【図９Ｄ】
2006502502.tif 000019
【図９Ｅ】
2006502502.tif 000020
【図９Ｆ】
2006502502.tif 000021
【図９Ｇ−１】
2006502502.tif 000022
【図９Ｇ−２】
2006502502.tif 000023
【国際調査報告】
2006502502.tif 000024
2006502502.tif 000025
2006502502.tif 000026
2006502502.tif 000027