自動回路設計のための方法と装置
回路の後の実装で生じうる逸脱に応じて回路設計を自動的に修正する方法と装置。一態様では、回路を設計する方法は、回路の設計の後の配線実装時に設計制約条件に違反する可能性があるかどうかを判定することと、後の実装で設計制約条件に違反する可能性を低減するように回路設計を修正することを含む。例えば、２よりも大きい多数のファンアウトを持ち、タイミング・クリティカル・パスまたはクリティカルに近いパス上のネットに対する経路は、経路トポロジに敏感であると考えられ、代替配線経路であると、タイミング制約に違反する可能性があり、その後の配線ソリューションのタイミング問題が発生する可能性を低減するために、コスト関数を悪化させない範囲で、回路設計に変換を選択的に適用するとよい。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、参照により本明細書に組み込まれる、２００３年５月３０日に発明者Ｃｈａｍｐａｋａ Ｒａｍａｃｈａｎｄｒａｎ、Ａｎｄｒｅｗ Ｃｒｅｗｓ、Ｋｅｎｎｅｔｈ Ｓ．ＭｃＥｌｖａｉｎにより出願された「Ｍｅｔｈｏｄ ａｎｄ Ａｐｐａｒａｔｕｓ ｆｏｒ Ａｕｔｏｍａｔｅｄ Ｃｉｒｃｕｉｔ Ｄｅｓｉｇｎ」という表題の仮出願第６０／４７５，０５９号の出願日の利益を主張するものである。
【０００２】
本発明は、自動回路設計に関するものであり、より具体的には、詳細な設計レイアウトを実行する前の回路設計の自動最適化に関するものである。
【背景技術】
【０００３】
デジタル回路の設計（例えば、超大規模集積回路技術のスケールの）では、設計者はコンピュータ援用手法を採用することが多い。デジタル回路の記述のためハードウェア記述言語（ＨＤＬ）などの標準言語が開発されたことで、複雑なデジタル回路の設計とシミュレーションを楽に行うことができる。ＶＨＤＬやＶｅｒｉｌｏｇなどのいくつかのハードウェア記述言語は、業界標準として発展してきた。ＶＨＤＬやＶｅｒｉｌｏｇは、汎用ハードウェア記述言語であって、これらの言語を利用することにより、抽象データ型を使用してゲート・レベル、レジスタ転送レベル（ＲＴＬ）、またはビヘイビア・レベルでハードウェア・モデルを決めることができる。デバイス技術の進歩に合わせて、ＨＤＬをより新しいデバイスや設計スタイルに対応させるため、さまざまな製品設計ツールが開発されてきた。
【０００４】
ＨＤＬコードを使って集積回路を設計する場合、まずコードを書き、その後、ＨＤＬコンパイラによりそのコードをコンパイルする。ＨＤＬソース・コードではあるレベルで回路素子を記述し、コンパイラが、このコンパイル結果からＲＴＬネットリストを出力する。ＲＴＬネットリストは、通常、フィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）または特定用途向け集積回路（ＡＳＩＣ）などの特定のベンダの集積回路の技術／アーキテクチャに依存しないという点で、技術独立のネットリストである。ＲＴＬネットリストは、回路素子の回路図表現に対応する（ビヘイビア図とは反対に）。そこで、技術独立のＲＴＬネットリストからベンダの技術／アーキテクチャで回路を作成するために使用できる技術特有のネットリストに変換するマッピング・オペレーションが実行される。ＦＰＧＡベンダはその集積回路内に論理回路を実装するためにさまざまな技術／アーキテクチャを使用することはよく知られている。したがって、技術独立のＲＴＬネットリストは、特定のベンダの技術／アーキテクチャに特有のネットリストを作成するようにマッピングされる。
【０００５】
このプロセスでは多くの場合望ましい１つのオペレーションで、特定の集積回路のレイアウトのプランニングを実行し、タイミング問題の制御と集積回路の領域間の相互接続の管理を行う。これは、ときには「フロア・プランニング」と呼ばれることもある。通常のフロア・プランニング・オペレーションでは、集積回路の回路エリアを、ときには「ブロック」とも呼ばれる複数の領域に分割し、その後、ブロック内に置かれるようにロジックを割り当てる。これらの領域は、矩形でも非矩形でもよい。このオペレーションの結果として、論理回路の位置に対する見積もり誤差が集積回路のサイズからブロックのサイズ（タイミング見積もりの誤差を小さくする傾向がある）に低減されることと、１つの非常に大きな問題から一連のより単純な問題に還元されるため配置と配線が通常高速化されることの２点が実現される。
【０００６】
チップ上にコンポーネントを配置し、コンポーネント間に配線した後、タイミング解析（例えば、タイミング・シミュレーション、または静的タイミング解析）を実行して、論理素子間の信号遅延を正確に決定することができる。バック・アノテーションを実行し、後の設計段階からの情報でより抽象的な設計を更新することができる。例えば、バック・アノテーションでは、配置と経路のデータベースから配線遅延情報と配置情報を読み込んで、論理合成設計のアノテーションを実行する。バック・アノテーションされた遅延情報は、タイミング要件が満たされていないクリティカル・パスを識別するために使用することができ、タイミング要件を満たすように論理合成を改善することもできる。
【０００７】
論理合成用の典型的なソフトウェア・プログラムでは、ネットのファンアウトに基づく遅延推定器機能を使用する。特定のファンアウトを持つネットに対応するすべての論理素子は、同じ配線遅延を持つと仮定されているため、推定された遅延情報はあまり正確ではない。実際には、配線遅延は、一方の論理素子から次の論理素子へ引き回される線の長さに依存する。配置距離と配線遅延との間の相関は、ファンアウトと配線遅延との間の相関よりも高い。論理合成の遅延推定器内の誤差のため、ソリューションが論理合成時には有効であるように見えても、配置と配線作業の後に無効であると判明することがある。
【０００８】
設計レイアウト（例えば、配置と配線）の後、サイズ変更またはバッファリングのような制限付きの最適化（インプレース最適化と呼ばれる）のみが通常実行される。しかし、インプレース最適化では、制限付きの改善しか得られない。インプレース最適化で、タイミング制約条件を満たすようにソリューションを調整できない場合、論理合成の調整を実行することにより、論理合成や配置と配線の反復が生じて費用が増大する。
【０００９】
クリティカル・パスの遅延短縮のための合成と論理回路の最適化は、論理回路を設計し、実装するうえで重要なステップである。合成段階で不正確な遅延推定だと、設計レイアウトが無効になる可能性があるため、よい品質の最適化結果を得るために正確な配線遅延情報を用意するのが望ましい。タイミング要件（例えば、スラック要件）を満たすように論理合成を改善しなければならない場合、合成と設計レイアウトとを繰り返さなければならず費用がかかる。スラックとは、望む遅延と実際の（推定または計算された）遅延との差のことであることに注意されたい。望む遅延が実際の遅延よりも大きい場合、スラックは正であり、そうでない場合、スラックは負である。通常、タイミング要件を満たすためにはスラックを正にする（またはゼロに近づける）必要がある（例えば、配線遅延を減らしてスラックを高めることで）。例えば、合成中に、トータル・ネガティブ・スラック・アルゴリズム（例えば、カリフォルニア州のＳｙｎｐｌｉｃｉｔｙ，Ｉｎｃ．社が販売している回路設計コンパイラＳｙｎｐｌｉｆｙで使用されている）では、スラックが改善に対する候補としてネイティブであるすべての場合を考慮するが、それは、ネガティブ・スラックを持つ候補はどれも、物理設計後、クリティカルになりうるからである。タイミング要件が満たされるようにスラックを正の値にするのがふつうである。
【発明の開示】
【課題を解決するための手段】
【００１０】
回路のその後の実装（例えば、配置と配線）で発生しうる逸脱に関する設計パラメータの感度に応じて回路設計（例えば、合成ソリューション）を自動的に修正する方法と装置が、本明細書では説明される。例えば、２よりも大きい多数のファンアウトを持ち、タイミング・クリティカル・パスまたはクリティカルに近いパス上のネットは、経路トポロジに敏感であると考えられ、代替配線経路だと、タイミング制約に違反する可能性があり、その後の配線ソリューションのタイミング問題が発生する可能性を低減するために、コスト関数を悪化させない範囲で、回路設計に変換を選択的に適用するとよい。本発明のいくつかの実施態様は、この節で要約されている。
【００１１】
本発明の一態様では、回路を設計する方法は、回路の設計のその後の配線実装時に設計制約条件に違反する可能性があるかどうかを判別することと、設計のその後の配線実装時に設計制約条件の違反の可能性を低減するように回路の設計を修正することを含む。一例では、設計のその後の配線実装時に設計制約条件に違反する可能性は、経路トポロジを推定する際の不確定性によるものである。一実施態様の一例では、設計のその後の配線実装時に設計制約条件に違反する可能性があるかどうかは、１）駆動素子の負荷素子を囲む境界ボックスと、２）ネットが駆動素子を負荷素子に接続する、タイミング・クリティカルまたはクリティカルに近いパス上のネットのファンアウトの個数に基づいて決定される。一実施態様の一例では、設計の修正は、第２の駆動素子を挿入するように第１の駆動素子を複製することと、第２の駆動素子の負荷素子として第１の駆動素子の負荷素子の一部を再接続することを含む。実施態様の別の例では、設計の修正は、第１の駆動素子の負荷素子としてバッファ素子を挿入することと、バッファ素子の負荷素子として第１の駆動素子の負荷素子の一部を再接続することを含む。一実施態様のさらに別の例では、設計の修正は、駆動素子の負荷素子の配置を再配列して駆動素子と負荷素子の境界ボックスの短い辺と長い辺との比を低減することを含む。一実施態様の一例では、設計の修正は、第２の素子の負荷素子として第１の素子の負荷素子の一部を変換することを含む。一例では、設計制約条件は、タイミング制約条件である（例えば、回路の最悪ネガティブ・スラック、回路の設計における論理素子のインスタンスのスラック、回路の設計におけるパス上の遅延、回路のトータル・ネガティブ・スラックなど）。一実施態様の一例では、代替経路トポロジが使用される場合にそれぞれが設計制約条件の違反を引き起こす可能性のある多数のネット候補が決定され、設計は、その多数のネット候補の部分集合について選択的に修正される。一実施態様の一例では、この部分集合は、それぞれのネット候補を通る多数のパスを表す流れに応じてその多数のネット候補から選択される。実施態様の別の例では、修正する部分集合を決定するために多数のネット候補を含むグラフに対し最小カットが実行される。
【００１２】
本発明の一態様では、回路を設計するための機械実装方法は、回路の設計に応じて駆動素子とその駆動子の負荷素子との間の第１の距離を推定することと、第１の距離を使用してタイミング制約条件が満たされているかどうかを検証することと、回路の設計に応じて駆動素子と負荷素子との間の、第１の距離よりも長い第２の距離を推定することと、第２の距離を使用してタイミング制約条件が満たされているかどうかを判定することとを含む。一実施態様の一例では、第１の距離は第１の経路トポロジに従い、第２の距離は第２の経路トポロジに従う。異なる経路トポロジは、配線全長の最小化、タイミング制約条件の適合、またはこれら２つの組み合わせなどのさまざまな配線目標の結果とすることができる。一実施態様の一例では、設計コスト関数を悪化させずに第２の距離を短縮するために回路の設計に対し変換を実行できるかどうかを判定することは、第２の距離が使用される場合にタイミング制約条件が満たされないとの判定に対する応答として決定される。例えば、変換は、駆動素子を複製すること、駆動素子をサイズアップすること、駆動素子と負荷素子との間にバッファ素子を挿入することとおよび／または駆動素子とその駆動素子の負荷素子のうちの少なくとも１つの素子の配置を調整することとすることができる。一実施態様の一例では、第２の距離は、経路トポロジの感度を低減するために駆動素子と負荷素子を接続するネットが選択された場合のみ推定され、ネットは、ネットがタイミング・クリティカルまたはクリティカルに近いパス上にあり、ネットのファンアウトの数が２よりも大きい場合にのみ選択される。一実施態様の一例では、ネットは、さらに、駆動素子の負荷素子を囲む境界ボックスの縦横比に応じて選択される。
【００１３】
便宜上、境界ボックスの縦横比は、縦横比が決して１を超えないような短い辺と長い辺との比と考えられる。
【００１４】
本発明の一態様では、回路を設計するための機械実装方法は、駆動素子とその駆動素子の複数の負荷素子の領域の形状を決定することと、その領域の形状に少なくとも基づき駆動素子と複数の負荷素子のうちの第１の素子との間の距離を推定することを含む。一実施態様の一例では、領域の形状は、異なる経路目標（配線全長の最小化、タイミング制約条件の適合、およびその両方の何らかの組み合わせなど）を使用するさまざまな配線アルゴリズムがどのように異なるかを推定するために使用される。一実施態様の一例では、領域の形状を決定することは、複数の負荷素子を囲む境界ボックスを決定することを含む。ただし、距離は、少なくとも境界ボックスに基づいて推定される。一実施態様の一例では、距離は、駆動素子と複数の負荷素子のうちの第１の素子との間の最小配線距離（例えば、マンハッタン距離）と境界ボックスの短い辺の距離の関数として推定される。一実施態様の一例では、この距離は、さらに、駆動素子のスラックに応じて推定される。一例では、境界ボックスは矩形である。
【００１５】
本発明の一態様では、回路を設計する方法は、第１の回路設計（例えば、配置ソリューションがある場合またはない場合の技術特有のネットリスト）の実装で設計制約条件（例えば、タイミング制約条件、最大静電容量、最大遷移、最大クロストーク）に違反する可能性を判定することと、設計制約条件に違反する可能性を低減するように第１の回路設計を修正することを含む。一例では、第１の回路設計の実装は、第１の回路設計を実装するための配線ソリューションを含み、第１の回路は、論理素子のインスタンスのサイズ設定、信号のバッファリング、信号の負荷遮蔽、論理素子の最も弱いドライバのサイズ設定、またはその他の操作を通じて修正される。一例では、設計制約条件は、タイミング制約条件を含む（例えば、回路の最悪ネガティブ・スラック、第１の回路設計における論理素子のインスタンスのスラック、第１の回路設計におけるパス上の遅延、回路のトータル・ネガティブ・スラックなど）。回路のトータル・ネガティブ・スラックは、回路のすべての端点におけるすべてのネガティブ・スラックの総和である。回路の端点は、パスの終端となる回路内の一点である。一例では、第１の回路設計を修正することは、第１の回路設計の実装における不確定性による論理素子のパラメータに対する設計制約条件の感度に応じて修正の論理素子のインスタンスを選択することを含む。別の例では、第１の回路設計を修正することは、第１の回路設計の実装における不確定性によるパス上の論理素子の少なくとも１つのパラメータに対する設計制約条件の感度に応じて修正のパスを選択することを含む。一例では、設計制約条件に違反する可能性は、第１の回路設計における論理素子のインスタンスに接続するネットの推定されるパラメータ（例えば、ネット長、ネット静電容量）の発生しうる変化から決定される。一例では、多数の候補が第１の回路設計の実装における不確定性に対する感度に基づいて第１の回路設計の論理素子のインスタンスから決定された後、その数の候補の部分集合が選択的に修正される（例えば、候補を通る多数のパスを表す流れに応じてその多数の候補のうちから１つの候補を選択し、選択された候補をサイズアップする、または候補のグラフに対し最小カットを実行する、そのカットの上の候補をサイズアップする）。一例では、サイズアップは、全体的設計制約条件を下げない範囲でのみ実行される（例えば、最悪のネガティブ・スラック）。
【００１６】
本発明は、これらの方法を実行するデータ処理システムを含むこれらの方法を実行する方法と装置、およびデータ処理システム上で実行した場合にこれらの方法をシステムに実行させるコンピュータ可読媒体を含む。
【００１７】
本発明の他の特徴は、付属の図面と以下で述べる詳細な説明とから明らかになる。
【００１８】
本発明は、付属の図面の図において限定されることなく例を使用して説明され、類似の参照番号は類似の要素を示す。
【発明を実施するための最良の形態】
【００１９】
以下の説明および図面は、本発明を例示するものであり、本発明を制限するものと解釈すべきではない。本発明を完全に理解できるようにするため、多数の具体的詳細を説明する。しかし、いくつかの場合には、本発明の説明をわかりにくくすることを避けるため、よく知られているまたは従来の内容については詳述しない。本開示の一実施形態を参照していても、同じ実施形態を参照する必要があるわけではなく、そのような参照は少なくとも１つを意味する。
【００２０】
本発明の少なくとも１つの実施形態は、回路設計の実装において設計制約条件に違反する可能性が低減されるように（例えば、配置と配線の後に）回路設計（例えば、技術特有の設計の合成ソリューション）を最適化しようとする。一実施形態では、タイミング目標の違反に関わる確率を低くするための変換についてインスタンスの最小の集合が選択される。
【００２１】
本発明の方法の多くは、従来の汎用コンピュータ・システムなどのデジタル処理システムにより実行することができる。１つの機能のみを実行するように設計またはプログラムされた専用コンピュータも使用することができる。
【００２２】
図１は、本発明とともに使用できる代表的なコンピュータ・システムの一例の図である。図１はコンピュータ・システムのさまざまなコンポーネントを例示しているが、そのような詳細は本発明と密接に関連していないためコンポーネントを相互接続する特定のアーキテクチャまたは方法を表すことは意図されていないことに注意されたい。また、より少ないコンポーネントまたはおそらくより多いコンポーネントを有するネットワーク・コンピュータやその他のデータ処理システムも、本発明とともに使用できることは理解されるであろう。図１のコンピュータ・システムは、例えば、Ｓｕｎワークステーション、またはＷｉｎｄｏｗｓ（登録商標）オペレーティング・システムが稼働しているパーソナル・コンピュータ、またはＡｐｐｌｅ Ｍａｃｉｎｔｏｓｈコンピュータとすることができる。
【００２３】
図１に示されているように、コンピュータ・システム１０１は、データ処理システムの一形態であり、マイクロプロセッサ１０３に結合されているバス１０２を含み、さらにＲＯＭ １０７、ＲＡＭ １０５、不揮発性メモリ１０６を備える。マイクロプロセッサ１０３は、図１の例に示されているように、キャッシュ・メモリ１０４に結合される。バス１０２は、これらのさまざまなコンポーネントを相互接続してつなぎ合わせ、またこれらのコンポーネント１０３、１０７、１０５、１０６をディスプレイ・コントローラやディスプレイ・デバイス１０８に相互接続し、またマウス、キーボード、モデム、ネットワーク・インターフェイス、プリンタ、スキャナ、ビデオカメラ、その他の当業でよく知られているデバイスとすることができる入出力（Ｉ／Ｏ）デバイスなどの周辺デバイスに相互接続する。通常、入出力デバイス１１０は、入出力コントローラ１０９を通じてシステムに結合される。揮発性ＲＡＭ １０５は、通常、メモリ内のデータをリフレッシュまたは保持するために絶えず電力を必要とするダイナミックＲＡＭ（ＤＲＡＭ）として実装される。不揮発性メモリ１０６は、通常、磁気ハード・ドライブまたは磁気光ドライブまたは光ドライブまたはＤＶＤ ＲＡＭまたはシステムの電源を切った後もデータを保持する他の種類のメモリ・システムである。通常、不揮発性メモリは、ランダム・アクセス・メモリであるが、そうである必要はない。図１は、不揮発性メモリがデータ処理システム内の残りのコンポーネントに直接結合されているローカル・デバイスであることを示しているが、本発明では、モデムまたはＥｔｈｅｒｎｅｔ（登録商標）インターフェイスなどのネットワーク・インターフェイスを通じてデータ処理システムに結合されているネットワーク記憶デバイスなどのシステムから離れた場所にある不揮発性メモリを使用することができることは理解されるであろう。バス１０２は、当業でよく知られているように、さまざまなブリッジ、コントローラ、および／またはアダプタを通じて互いに接続されている１つまたは複数のバスを備えることができる。一実施形態では、Ｉ／Ｏコントローラ１０９は、ＵＳＢ周辺機器を制御するためのＵＳＢ（Ｕｎｉｖｅｒｓａｌ Ｓｅｒｉａｌ Ｂｕｓ）アダプタ、および／またはＩＥＥＥ−１３９４周辺機器を制御するためのＩＥＥＥ−１３９４バス・アダプタを備える。
【００２４】
この説明から、本発明の複数の態様は、少なくとも一部は、ソフトウェアで実現できることは明白であろう。つまり、これらの手法は、ＲＯＭ １０７、揮発性ＲＡＭ １０５、不揮発性メモリ１０６、キャッシュ１０４、またはリモート記憶デバイスなどのメモリに格納されている命令シーケンスを実行するマイクロプロセッサなどのプロセッサに対する応答として、コンピュータ・システムまたはその他のデータ処理システム内で実行することができる。さまざまな実施形態において、本発明を実装するために、配線接続されている回路をソフトウェア命令と組み合わせて使用することができる。したがって、これらの手法は、ハードウェア回路とソフトウェアの特定の組み合わせに限定されず、またデータ処理システムにより実行される命令の特定のソースにも限定されない。さらに、この説明全体を通して、説明を簡単にするため、さまざまな機能や操作はソフトウェア・コードにより実行されるか、またはソフトウェア・コードにより引き起こされるものとして説明されている。しかし、当業者であれば、そのような表現が意味しているのは、それらの機能がマイクロプロセッサ１０３などのプロセッサによるコードの実行から結果として生じるということであると理解するであろう。
【００２５】
機械可読媒体が、データ処理システムにより実行されたときに本発明のさまざまな方法をシステムに実行させるソフトウェアとデータを格納するために用いられる。この実行可能ソフトウェアとデータは、図１に示されているように、例えば、ＲＯＭ １０７、揮発性ＲＡＭ １０５、不揮発性メモリ１０６、および／またはキャッシュ１０４をはじめとするさまざまな場所に格納することができる。このソフトウェアおよび／またはデータの一部分を、これらの記憶デバイスのうちのいずれか１つに格納することができる。
【００２６】
したがって、機械可読媒体は、機械によりアクセス可能な形態で情報を提供（つまり、格納および／または伝送）するメカニズムを備える（例えば、コンピュータ、ネットワークデバイス、パーソナルデジタルアシスタント、製造装置、１つまたは複数のプロセッサの集まりを含むデバイスなど）。例えば、機械可読媒体は、記録可能／記録不可能媒体（例えば、読み取り専用メモリ（ＲＯＭ）、ランダム・アクセス・メモリ（ＲＡＭ）、磁気ディスク記憶媒体、光記憶媒体、フラッシュ・メモリ・デバイス、などだけでなく、電気、光、音響、またはその他の形態の伝搬信号（例えば、搬送波、赤外線信号、デジタル信号など）などをも含む。
【００２７】
標準的な回路設計プロセスでは、論理合成ツールで、与えられた機能の集合を実行する論理素子回路網を作成する。論理合成ツールでは、遅延、領域、その他の設計目標を最適化するため論理回路を変形し再構成することができる。ゲート・レベル論理素子は、ベンダ固有のプリミティブにマッピングされ、技術特有のネットリストを生成する。その後、マッピングされた技術特有のネットリストは、チップ上のさまざまなブロックに割り当てられる。次に、配置と配線ツールでは、マッピングされたネットリストのベンダ特有のプリミティブをチップ上に配置し、それらのプリミティブの間に配線を行う。配置と配線の後、インプレース最適化は、通常、さらにタイミングを最適化するために実行される。インプレース最適化は、論理素子の配置を著しく変更することなく論理素子に対する制約付き変更を行う。配置と配線情報が利用できるようになった後、詳細なタイミング解析を実行して、タイミング制約条件がすべて満たされているかどうかを正確に判別することができる。タイミング要件すべてが満たされているわけではないと判断された場合、論理合成により生成された設計は、タイミング要件を満たすように変更される。
【００２８】
そのため、回路設計のための合成ツールの遅延予測の正確さは、よい品質の結果の生成のためには重要である。通常、バックエンド・ソフトウェア・プログラムは、合成ツールの設計結果を回路の詳細実装に使用する。例えば、配置と配線ツールは、合成ツールの設計結果を設計レイアウトに使用する。合成推定遅延に基づいて合成ツールにより予測されるクリティカル・パスの遅延は、設計の後段階（例えば、配線、レイアウトなど）から抽出された詳細データ（例えば、寄生データ、詳細配線情報）に基づいて計算されたタイミング目標との密接な忠実関係になければならない。合成ツールは、ハンドオフに先立ってこのバックエンド遅延を正確に予測する場合、合成ツールとバックエンド・ソフトウェア・プログラムを伴う費用のかかる反復を実行する必要性が避けられる。
【００２９】
しかし、合成ツールは、常にこのバックエンド遅延を正確に予測できるわけではない。ほとんどのタイミング目標は、長い配線によって引き起こされるセル遅延とネット遅延が関わる。長い配線遅延は、通常、長い配線をバッファリングし、それから、さらに小さな配線に効果的に分割することにより、合成において標準的な形で取り扱われる。そのため、セルの遅延を正確に予測することで、タイミング目標のよい予測を出すことができる。セルの遅延は、通常、セルの静電容量性負荷の関数である。静電容量性負荷の主要コンポーネントは、セルのドライバに接続されたネットの静電容量と負荷ピンの容量性負荷を含む。負荷ピンの静電容量は、設計の論理接続属性に基づいて推論できる。しかし、ネットの静電容量は、設計レイアウトが完了したときにしか正確に得ることができない。そのため、合成ツールは、最終的に設計レイアウトを作成するバックエンド・ソフトウェアのビヘイビアを予測する負担を有する。
【００３０】
正確な遅延を予測するのではなく、回路の一部分（例えば、ゲート、またはパス）がタイミング目標の違反に関わる確率を評価できるように、遅延の確率分布を決定することができる。本発明の少なくとも一実施形態では、バックエンド・ソフトウェア・プログラムを伴う反復の必要性を軽減するためにタイミング制約条件に違反する確率の高い回路の部分に対し変換を実行しようとする。
【００３１】
例えば、その後の実装に発生しうる逸脱（例えば、合成ツール内に埋め込まれたタイミング・エンジンにより推定されるものから逸脱する）によるタイミング制約条件に関するタイミング・パラメータの感度は、その後の実装における違反の確率を示す指標となる。本発明のいくつかの実施形態による合成ツールは、変換を実行して、タイミング目標の変化が、設計のレイアウトの実行後に、タイミング制約条件に関して、重要な意味を持たないようにする。本発明のいくつかの実施形態では、遅延推定からの可能な逸脱は、クリティカル・パスにそって小さく、かつクリティカルに近いパスにそって小さいことが望ましい。そのため、本発明の実施形態による合成ツールでは、回路の可能なレイアウト後クリティカル部分やクリティカルに近い部分を識別し、それらの部分に対して変換を実行し、クリティカル・パスとクリティカルに近いパス上の遅延の変動を低減し、それによって、設計レイアウトが実装された場合にタイミング制約条件違反が生じる可能性を低減する。
【００３２】
タイミング目標と合成ツールの推定におけるその不確定性は、主に、ネット・ファンアウト、インスタンスの駆動長、配線負荷などのその他の推定因子、また物理的合成では、経路長、輻輳効果、配線の単位長さ当たりの抵抗と容量などの技術情報に依存する。輻輳は、結合容量と配線長（例えば、迂回路を引き起こす）の両方に影響を及ぼす。
【００３３】
例えば、長いネットを駆動する低い駆動強度のセルがある場合、ネットの長さの小さな変動であっても、駆動セルの遅延に大きな影響を及ぼす可能性がある。すべての低い駆動強度セルを完全に排除し、高い駆動強度セルのみを使用することができるが、このようなアプローチでは、領域と負荷のペナルティが増大し、ひいては、すべてのタイミング目標に悪影響を及ぼす。そのため、本発明の少なくとも一つの実施形態では、駆動強度を改善する必要があるセルを選択的に選ぶ。
【００３４】
本発明の少なくとも一実施形態では、回路設計のネットリスト内のセルの部分集合に対し設計変更を選択的に実行する。変換のインスタンスの縮小された集合（例えば、最長集合）を識別するためのさまざまなアルゴリズムについて、以下で説明する。
【００３５】
本発明の少なくとも一実施形態では、推定された物理データに基づいてタイミング制約条件違反の確率を推定する。例えば、感度値に基づく違反の確率を使用して、インスタンスの改善を優先順位付けし、物理設計後に違反の確率が高いものが違反の確率が低いものに先立って改善されるようにする。それによって、候補リストは、違反の確率に基づき最小にすることができる。改善後の面積利用度がネガティブ・スラックを持つすべてのインスタンスの改善よりも小さくなるように、通常、候補リストの小さな集合を改善のために選択することができる。
【００３６】
本発明の一実施形態では、設計変更のために回路の一部分が選択され、部分（例えば、論理素子のインスタンス、または回路内のパス）がタイミング目標の違反に関わりうる確率に基づき、設計の後の方の段階でタイミング制約条件に違反する確率を低減するようにする。例えば、選択は、タイミング目標の違反に関与するそれぞれのゲートの確率（例えば、ゲートによる不確定性への感度）に基づいて実行できるか、または選択は、タイミング目標の違反に関与するそれぞれのパスの確率に基づいて実行できる。
【００３７】
本発明の一実施形態では、タイミング目標の違反に関わるかどうかを判別するために、インスタンスを一度に１つずつ調べる。例えば、駆動強度を改善するためにインスタンスの部分集合を選択することができ、サイズアップが設計の最悪のネガティブ・スラックの低下を引き起こさない、またサイズアップがさらに、あらかじめ決められている上限の範囲内で設計の面積利用度を保持するもののみを含めることによりインスタンスの部分集合のサイズを最小にする。
【００３８】
本発明の一実施形態では、設計の最悪のネガティブ・スラックに応じて、インスタンスの部分集合が選択される。例えば、回路の一部分が、スラックがしきい値よりも悪い（例えば、しきい値と最悪のネガティブ・スラックの間にある）インスタンスに対する設計変更に対して選択される。負荷の変化に対するこれらのインスタンスの感度を判別することができるが、これについては、以下で詳述する。負荷の増大によりインスタンスのスラックが最悪のネガティブ・スラックを超える場合、サイズ改善のため候補のリスト上でインスタンスが選択される。
【００３９】
本発明の他の実施形態では、スラックがネガティブであるインスタンスの部分集合が選択される。この部分集合内のすべてのインスタンスの感度が計算され、それらのインスタンスが、減少する感度値に基づいて設計変更に対して優先順位付けされる。このシナリオでは、設計のトータル・ネガティブ・スラックは低下しないことが保証される。
【００４０】
負荷の変化は、インスタンスの配置情報が利用可能でない場合に配線負荷モデルの摂動に基づいて推定することができる。物理的合成の場合、インスタンス上の負荷のこの変化は、さらに正確な物理的情報に基づいて判定することができる。
【００４１】
例えば、物理的合成時に詳細な配置が実行される場合、設計の中のすべてのインスタンスの正当な場所が利用可能である。ネットで推定する最も可能性の高い経路を決定するために、高速大域配線経路推定を実行できる。これらの推定された経路から、経路の予測される輻輳マップが決定される。
【００４２】
輻輳により、配線の結合容量が変動する。ひどく輻輳している領域内を引き回されるネットが輻輳領域の周りを迂回される可能性は、経路資源がその領域内で引き回される必要のあるネットの要求量よりも小さい場合に、最も高い。これらのタイプのネットは、ネット長の増大が生じる可能性が最も高い。
【００４３】
詳細配線の後のネットのレイヤ割り当てでも、配線の抵抗と静電容量の予測不可能な変化が生じる可能性がある。輻輳領域内のインスタンスの感度を下げると、詳細配線の後のタイミング要件の違反を引き起こす可能性のある予測不可能な変化の効果を低減することができる。
【００４４】
ネットが引き回される領域の過剰な輻輳に加えて、近隣領域内にも過剰な輻輳が存在する場合、迂回路の量が増える可能性がある。迂回路の量は、通常、輻輳している領域の形状とサイズに依存する。迂回路の量は、さらに、他のパラメータ（例えば、タイミング・パラメータ）にも依存する場合がある。したがって、これらのタイプのネットに対し発生する可能性のある長さの変化も、それに応じて推定できる。
【００４５】
一実施形態では、配線長の増大は、ネットのセグメントの経路輻輳だけでなく近隣領域経路輻輳にも依存する関数を使用して推定することができる。典型的な大域的配線経路推定では、ネットの実際の長さに対する下限が得られる。そのため、一実施形態では、下限の長さを超えるネット長の（経時的）摂動の量を表す実験的（または統計的）結果に基づく因子が加えられる。
【００４６】
ネット長の摂動により、インスタンスのスラックが最悪のネガティブ・スラックを超える場合、ネットの駆動素子は、摂動の効果がスラックの著しい変化に寄与しなくなる（例えば、スラックがしきい値よりも悪くなる）までサイズアップする必要がある。
【００４７】
本発明の一実施形態では、非最適経路（ｅｌ、経路の推定長）であることによるネット長の増大、ネットのファンアウト（ｆ）、ネット・セグメントの輻輳係数（ｃｇ）、ネット・セグメントの近隣の輻輳係数（ｎｃｇ）、輻輳しきい値（ｃｔ）、標準セル行の高さ（ｒｔ）に応じて、発生しうるネット静電容量（ｎｃｃ）の変化が推定される。例えば、発生しうるネット静電容量（ｎｃｃ）の変化は、以下のように推定できる。
【００４８】
ｎｃｃ＝ｋ0×ｅｌ×ｆ＋ｋ1×ｒｔ ｃｇ≦ｃｔの場合
【００４９】
ｎｃｃ＝ｋ2×ｃｇ＋ｋ3×ｎｃｇ ｃｇ＞ｃｔの場合
【００５０】
ただし、ｋ0、ｋ1、ｋ2、ｋ3は、統計データに基づいて導かれるパラメータである。例えば、バックエンド・ソフトウェア・ツールを使用して多数の合成ソリューションの配置と配線が行われた後、合成ソリューションに基づいて推定されたものと設計レイアウトの後に決定されたものとの間のネット静電容量の実際の変化を決定することができる。これらのソリューションに対する実際の変化と輻輳係数との相関を計算して、パラメータｋ0、ｋ1、ｋ2、ｋ3を決定することができる。前の設計ソリューションに対する設計レイアウトの後の実際の変化に基づいて（例えば、異なる回路の集合、所定の回路に対する前の多数の反復、その他に基づいて）パラメータｋ0、ｋ1、ｋ2、ｋ3を導くために、曲線当てはめ手法を使用できる。曲線当てはめ手法は、さらに、ネット静電容量の発生しうる変化の推定に対する公式の形を決定するためにも使用することができる。そのため、上で例示されているものと異なる式（または方程式）も使用できるが、異なる数の統計学に基づくパラメータを必要とする場合がある。
【００５１】
ネット長の変化も、同様にして決定できることに注意されたい。輻輳係数が推定できない場合（例えば、回路の素子のインスタンスに関する位置情報が利用できない場合）、輻輳係数を輻輳しきい値よりも小さい値に設定し、ネット静電容量（またはネット長）の推定された変化が輻輳係数に基づかないようにすることができる。
【００５２】
タイミング目標パラメータ（例えば、遅延、スラックなど）は、通常、ネット静電容量の関数である。そのため、ネット静電容量の変化は、タイミング目標パラメータの変化を判別するために使用することができる。
【００５３】
感度係数は、ｉ）発生しうる変化を考慮しないタイミング目標パラメータ（ｔobj）と、ii）発生しうる変化のあるタイミング目標パラメータ（ｔobjn）から決定することができる。さらに、タイミング目標パラメータ（ｔobjt）は、感度係数の決定の際に使用することができる。例えば、しきい値は、タイミング制約条件に違反する結果を超える、タイミング目標パラメータに対する限界値とすることができる。例えば、感度係数（ｓｆ）は以下のように評価することができる。
【００５４】
ｓｆ＝（ｔobjn−ｔobj）／ｔobjt
【００５５】
そのため、感度係数は、発生しうる実装の変化による基準値（例えば、しきい値）に関してタイミング目標パラメータの変化が増大すると増大する。
【００５６】
さまざまな代替感度係数定義を使用して、感度を定量化し、その後の実装における制約条件違反の確率を示すことができることが理解される。例えば、定式化は、以下のように、しきい値に近いタイミング目標を持つインスタンスについてより高い感度を示すために使用することができる。
【００５７】
【数１】
【００５８】
一実施形態では、感度係数を使用して、修正（または設計変更）対象の回路設計の部分を選択する。例えば、インスタンス・ベースのアプローチでは、個々のインスタンス要素によるタイミング・パラメータに対する感度を評価し、修正対象の敏感な素子を判別し、パス・ベースのアプローチでは、個々のパスに対するインスタンス要素によるタイミング・パラメータの感度を評価して、修正対象の敏感なパス（およびパス上の敏感な素子）を決定する。さらに、敏感な素子の部分集合を修正対象の敏感なパスから選択することができる。
【００５９】
それとは別に、インスタンスのパス感度は、設計内のタイミング終点から開始するすべてのパスの順方向と逆方向の幅優先探索(breadth first)を実行することから決定することができる。タイミング終点の集合は、ラッチ、レジスタ、フリップ・フロップ、Ｉ／Ｏポートを含む。例えば、パス感度ｓpathを決定することは、以下を含む。
【００６０】
ａ）設計内のすべてのインスタンスでインスタンス感度（ｓinstance）を計算する。
【００６１】
ｂ）逆方向幅優先探索を実行して、以下のように駆動インスタンスＪn（ｎ＝０，１，．．．，Ｎ）を持つインスタンスＩでの逆方向パス感度（ｓbackward）を計算する。
【００６２】
ｓbackward（Ｉ）＝ｓinstance（Ｉ）＋Ｍａｘ（ｓbackward（Ｊ0），ｓbackward（Ｊ1），．．．，ｓbackward（ＪN））、
【００６３】
ｃ）同様に、順方向幅優先探索を実行して、以下のように負荷インスタンスＪm（ｍ＝０，１，．．．，Ｍ）を持つインスタンスＩでの順方向パス感度（ｓforward）を計算する。
【００６４】
ｓforward（Ｉ）＝ｓinstance（Ｉ）＋Ｍａｘ（ｓforward（Ｊ0），ｓforward（Ｊ1），．．．，ｓforward（ＪM））、
【００６５】
ｄ）以下からインスタンスＩのパス感度を決定する。
【００６６】
ｓpath（Ｉ）＝Ｍａｘ（ｓforward（Ｉ），ｓbackward（ｌ））
【００６７】
駆動インスタンスは、負荷インスタンスへの直接入力として出力を生成し、負荷インスタンスは、駆動インスタンスから直接入力を受け取ることに注意されたい。
【００６８】
インスタンスまたはパスについて感度を定義する方法は多数あることは理解されるであろう。例えば、完全に確率論的なアプローチを使用することにより、タイミング・パラメータの変化の確率と平均期待値を決定することができ、これから、感度指標が決定されるが、確率および平均期待値の評価は多量の計算を必要とする場合がある。それとは別に、感度指標は、輻輳領域を回避するために発生する再配線によるネット長の変化などのさまざまな要因により識別された決定論的変化に基づいて評価することができる。さらに、輻輳係数などの統計学に基づくパラメータや決定論的に決定されたパラメータを組み合わせて、感度係数に対する実験式を定式化することができる。例えば、合成時に、ネット長は、ネットのファンアウトとブロック・サイズに従って配線負荷テーブルから求めることができる。ルックアップ値に基づく変化の特定の割合がネット長の可能な変化であると仮定することができる。それとは別に、配線負荷テーブルでネット長の変化の平均値を生成し、可能な変化を、ファンアウトとブロック・サイズに従ってルックアップするようにもできる。
【００６９】
パスに基づくアプローチでは、パス遅延がタイミング目標の違反を引き起こす可能性がある確率が評価される。例えば、多数の低駆動セルを持つパスに対するタイミング目標は、低駆動セルが少ししかないパスに比べて違反される可能性が高い。タイミング目標の違反の確率を正確に評価することは困難であるが、発見的アプローチを使用すると、タイミング目標の違反の確率を示す指標を決定することができる。例えば、パスに対するすべてのネット・セグメントの決定論的変化を識別し、パスの新しいタイミング目標の評価に組み込み、パス内の感度を決定することができる。その場合、バックエンド・ツール内のパスに対し適用されるすべての変化の最悪の場合のシナリオが仮定される。
【００７０】
タイミング目標の違反の確率を低減することを目的として（また、変換を適用する順序を決定するため）変換される必要のあるインスタンスの最小集合を選択するために、異なる選択方式を使用することができる。例えば、複数の候補を、感度に基づいて選択することができる。例えば、インスタンスのタイミング目標（例えば、遅延、またはゲートのスラック）がネットのネット長（またはネット静電容量）の変化に敏感な場合、ネットの駆動素子はサイズアップの候補として選択される。それとは別に、ネットの駆動素子を複製することができ、これにより駆動素子は効果的にサイズアップされる。駆動素子が複製された後、元の駆動素子の負荷素子は、元の駆動素子と新しい駆動素子の負荷素子として分割することができる。それとは別に、元の駆動素子と新しい駆動素子は、負荷素子をまとめて駆動することができる。同様に、パスのタイミング目標（例えば、パスにそっての遅延）がパス上の１つまたは複数のネットのネット長（またはネット静電容量）の変化に敏感な場合、パスは変換の候補として選択される。さらに、候補は、設計目標に対する影響に応じて選択することができる。例えば、クリティカル・パスまたはクリティカルに近いパス上の敏感な素子を選択することができる。さらに、回路内の影響の相対的重要度または範囲に基づいて、敏感な素子を選択することができる。例えば、多くのパス上にある敏感な素子は、少ないパス上にある類似の素子よりも優先度が高い。
【００７１】
例えば、１パスの物理的合成が実行された後、インスタンスの正当な位置を決定することができる。その後、敏感なインスタンスの候補集合を、感度基準に基づいて選択することができる。候補は、流れに基づいてソートされ、多数の異なるパスはそれらの候補のそれぞれを流れる。流れの大きな候補は、流れの小さな候補が処理される前に処理される。１つの素子のサイズアップは、他の関連するタイミング・パラメータに悪影響を及ぼす可能性があるため（例えば、上流素子のスラック）、サイズアップ・オペレーションは、これらの関連するタイミング・パラメータを許容不可能なレベルにまで低下させない範囲に限り実行される。したがって、例えば、候補のサイズアップが設計目標を悪化させないと判断された場合（例えば、最悪のネガティブ・スラック）、候補はサイズアップされ（例えば、所定の量だけ）、そうでなければ、候補は設計目標が低下しない限りサイズアップされ、バッファリング（オプション）される。感度を十分に引き下げるために候補のサイズアップおよびバッファリングを実行できない場合（例えば、他の設計制約条件のため）、候補の最も弱い駆動がサイズアップされ、本発明の一実施形態のさらに大きなインスタンスを駆動できる。
【００７２】
バックエンドにハンドオフされるネットリスト内に敏感なインスタンスが存在しない場合、実際の経路トポロジ内にある程度の変動があっても、設計内のクリティカル・パスの変化（例えば、合成段階の推定からの逸脱）によりタイミング制約条件には違反しない（または違反される可能性がきわめて小さい）。
【００７３】
本発明の他の実施形態では、敏感なインスタンスを通るパスを表すグラフが構築され、サイズアップするインスタンスを選択するためにグラフの最小カットを実行できる。最小カット・オペレーションにより、グラフを２つの非連結部分に分離するグラフ内の最小要素の集合を見つける。最小カット・オペレーションを実行する知られているアルゴリズムを使用することができる。最小カットの上の敏感な素子の集合は、回路の２つの部分の間の通信に影響を及ぼす最小の敏感な素子の部分集合を表す。そのため、最小カットの上のそのような敏感な素子の集合のサイズアップは、回路設計における感度を低減する費用効果のある手段である。そのカット内のインスタンスをサイズアップした後（例えば、所定の量について、または最悪のネガティブ・スラックを悪化させない範囲で）、さらに最小カット・オペレーションを実行することができる。最小カット・ベースの選択は、繰り返し、または他の選択方式と組み合わせて実行することができる。一例では、このグラフは、信号パスを通るパス上の敏感なインスタンスの位置決めを表し、敏感でないインスタンスは、このグラフ上には表されない。
【００７４】
この説明から、当業者であれば、さまざまな異なる選択と順序付け方式（例えば、異なる組み合わせや変更形態とともに、この説明の例で例示されているように）を使用して、サイズアップする必要のあるインスタンスの個数を効果的に減らし、インスタンスのサイズアップの費用有効性を高めることができる。
【００７５】
図２は、本発明の一実施形態により回路を設計する方法を示す図である。オペレーション２０１で第１の回路設計（例えば、技術特有のネットリスト、技術マッピング・ネットリスト、または回路図）を受け取った後、オペレーション２０３で、第１の回路設計を実装するために生成される第２の回路設計内で複数の設計制約条件（例えば、タイミング）に違反する可能性を判別する。例えば、合成ソリューションについて詳細設計レイアウトの後（例えば、配置と配線後）にタイミング制約条件に違反する可能性を決定することができる。オペレーション２０５では、第１の回路設計（例えば、素子のサイズ設定、信号のバッファリング、負荷の遮蔽など）を修正して、第１の回路設計の実装において複数の設計制約条件に違反する可能性を低減する。
【００７６】
図３は、本発明の一実施形態により回路を最適化する方法を示す図である。オペレーション２２１で第１の回路設計（例えば、ネットリスト、技術特有のネットリスト、配置ソリューション、配置と配線前の設計ソリューション）を受け取った後、オペレーション２２３で、第１の回路設計に対する１つの設計制約条件パラメータ（例えば、ネット上またはパス上の遅延、最悪ネガティブ・スラック、最速のシステム・クロック）を推定する。オペレーション２２５では、第１の回路設計内の不確定性による設計制約条件パラメータの感度を判別する。例えば、合成ツールにより推定される経路と異なる配線ソフトウェア・ツールで決定された経路によるタイミング・パラメータの変化である（例えば、輻輳領域を回避する迂回路、または推定からの逸脱によるもの）。オペレーション２２７では、第１の回路設計内の不確定性による設計制約条件パラメータの少なくとも感度に基づいて第１の回路設計を最適化する。この最適化は、さらに、修正、関連設計パラメータの許容される低下レベル、感度がクリティカルであるかどうかなどの費用有効性に基づくこともできる。
【００７７】
図４は、本発明の一実施形態により回路を最適化する詳細な方法を示す図である。オペレーション２４１で第１の回路設計（例えば、ネットリスト、技術特有のネットリスト、配置ソリューション、配置と配線前の設計ソリューション）を受け取った後、オペレーション２４３で、複数の設計制約条件パラメータ（例えば、ネットまたはパスによる遅延）を推定する。オペレーション２４５では、第１の回路設計を実装する際の不確定性を判別する（例えば、第１の回路設計の実装においてネット長および／またはネット静電容量に発生しうる変化）。オペレーション２４７で、第１の回路設計を実装する際の不確定性による設計制約条件パラメータの不確定性を表す指標（例えば、感度係数）を決定する。オペレーション２４９で、少なくともそれらの指標に基づいて第１の回路設計の一部分を選択的に修正する。
【００７８】
図５〜６は、本発明のいくつかの実施形態により回路を選択的に修正する詳細な方法を示す図である。
【００７９】
図５のオペレーション３０１で、設計ソリューション（例えば、技術特有のネットリスト）を生成するため第１の回路の物理的合成を実行する。オペレーション３０３では、状況に応じて、インスタンス（例えば、論理素子）の位置を決定する。オペレーション３０５で、第１の回路設計を実装する際の不確定性による１つまたは複数の設計制約条件パラメータの不確定性を表す指標を決定する。オペレーション３０７で、修正する少なくともいくつかの指標に基づいて第１の回路の複数の部分（例えば、インスタンスまたはパス）を決定する。オペレーション３０９では、複数の部分から１つを選択する（例えば、複数の流れを持つ１つのインスタンスを選択するか、または最小カットの上の敏感な素子の集合を選択するか、または敏感なパスから敏感なインスタンスを選択する）。一実施形態では、選択は、オペレーション３０５で決定された指標に基づく。例えば、最も敏感な指標を持つものが、変換対象として最初に選択される。オペレーション３１１で、選択されたものに対し修正を実行する（例えば、サイズアップ、負荷の遮蔽、信号のバッファリング）。オペレーション３１３で、その修正が受け入れ可能である（例えば、選択されたものに対する修正が、最悪のネガティブ・スラックを低下しない）と判断された場合には、オペレーション３１５は修正のために次のものを選択することに進み、そうでない場合には、オペレーション３１７は、他の候補を処理するために修正を破棄する。
【００８０】
図６のオペレーション３３１では、第１の回路設計の実装に際して設計制約に違反する可能性があるかどうかを示す指標を決定する。オペレーション３３３で、少なくともそれらの指標に基づいて第１の回路設計から複数の修正候補を決定する。オペレーション３３５で、修正候補をソートする（例えば、流れ、それぞれの候補を通る異なるパスの個数に応じて）。オペレーション３３７で、候補を選択する（例えば、最大の流れとともに）。オペレーション３３９では、候補をサイズアップする。オペレーション３４１で、その修正がタイミング制約条件全体を悪化すると判断した場合、オペレーション３４５で、サイズを修正し、および／またはバッファまたは負荷遮蔽を使用し（すなわち他の設計変更を適用し）、そうでなければ、次の候補をサイズ設定対象として選択する。一実施形態では、この候補は、感度を低減する（または感度を十分に下げる）ためにサイズアップもバッファリングも行えない場合、その候補の最も弱い駆動がサイズアップされる。
【００８１】
本発明の一実施形態では、修正対象に候補を選択するループ（例えば、図５のオペレーション３１５から３０９まで、または図６のオペレーション３４３から３３７まで）は、最大利用限度に到達するまで、または感度を低減する改善がしきい値を下回るまで、続けられる。例えば、最大領域利用度制約条件（または、領域使用度の最大増加）を使用して、サイズアップおよび／またはバッファリングの対象の候補を選択する反復を停止することができる。さらに、候補のサイズアップおよび／またはバッファリングを行っても感度の改善は非常に限られている場合には、反復を終了させることができる。
【００８２】
本発明のさまざまな例は、この説明からタイミング制約条件とともに設計制約条件として例示されているが、当業者には、本発明のさまざまな方法は、さらに、初期段階の設計の部分（例えば、敏感なインスタンス）を選択的に変換し、初期段階の設計に基づく後の段階の設計において他の設計制約条件に違反する可能性を低減することもできることは明白であろう。感度解析を実行して、設計規則違反のインスタンスの感度を判定する（回路内の最大静電容量、最大遷移、および／または最大クロストークなど）。これらの設計規則（または制約条件）に違反する可能性を減じるために、回路の部分（例えば、インスタンスまたはパス）の感度に基づいて変換（例えば、サイズ設定）を選択的に実行できる。
【００８３】
本発明のほとんどの実施形態はＨＤＬ設計合成ソフトウェア・プログラムで使用することが意図されているが、本発明は、そのような使用に必ずしも限定されない。他の言語とコンピュータ・プログラムの使用も可能である。例えば、コンピュータ・プログラムは、ハードウェアを記述するように書くことができ、したがって、ＨＤＬの式とみなすことができる。それとは別に、本発明は、いくつかの実施形態では、ＨＤＬを使用せずに作成された論理表現、例えば、ネットリストの割り当てと、割り当て解除を実行することができる。本発明のいくつかの実施形態は、限定はしないがＨＤＬ合成システムで使用する文脈で説明し、特に、ベンダ特有の技術／アーキテクチャを含む集積回路とともに使用するように設計されたものについて説明する。よく知られているように、ターゲット・アーキテクチャは、通常、ＩＣの製造会社により決定される。本発明のいくつかの実施形態は、ＬＳＩ Ｌｏｇｉｃ、ＮＥＣ、ＩＢＭ、Ａｒｔｉｓａｎ Ｃｏｍｐｏｎｅｎｔｓ Ｉｎｃなどのベンダから出されている、構造化ＡＳＩＣとプラットフォームＡＳＩＣを含む、特定用途向け集積回路（ＡＳＩＣ）と併用することができる。本発明のいくつかの実施形態は、プログラマブルＩＣと併用することもできる。ターゲット・アーキテクチャの一例は、カリフォルニア州サンノゼのＸｉｌｉｎｘ，Ｉｎｃ．社から市販されているフィールド・プログラマブル・ゲート・アレイである集積回路のプログラマブル・ルックアップ・テーブル（ＬＵＴ）や関連する論理回路である。ターゲット・アーキテクチャ／技術の他の例は、Ａｌｔｅｒａ、Ｌｕｃｅｎｔ Ｔｅｃｈｎｏｌｏｇｙ、Ａｄｖａｎｃｅｄ Ｍｉｃｒｏ Ｄｅｖｉｃｅｓ、およびＬａｔｔｉｃｅ Ｓｅｍｉｃｏｎｄｕｃｔｏｒなどのベンダから出ているフィールド・プログラマブル・ゲート・アレイや複雑なプログラマブル論理デバイスのよく知られているアーキテクチャを含む。
【００８４】
物理的合成時に、経路推定器を使用して、配線静電容量、配線抵抗、ピン間遅延を予測することができ、これは、バックエンド設計ソフトウェア・プログラムを使用して詳細な配線を実行した後でないと正確に判別できない。合成実行時に完全な詳細経路を最新状態に保つと資源（例えば、計算時間とメモリ使用量）を消費しすぎるため、経路推定器が通常使用される。合成時のネット遅延の正確な予測ができれば、バックエンド・ツールからの詳細情報を使用して決定されたタイミングと合成ツールのタイミング予測との間の相関を改善できる。しかし、ネット遅延は、ネット経路トポロジに大きく依存している。いくつかの条件の下では（例えば、ネットのファンアウトの個数が増えたとき）、バックエンド・ツールで使用されるネット経路トポロジは予測不可能になる。
【００８５】
図７〜８は、経路トポロジの不確定性による配線長を推定する際の不確定性を例示する図である。同じ全配線長を持つ経路トポロジが多数存在する場合がある。図７では、駆動素子４０１と負荷素子４０３〜４０７を接続するネットは、時計回りの方向に配線される。図８では、駆動素子４０１と負荷素子４０３〜４０７を接続するネットは、反時計回りの方向に配線される。ネットの全配線長は図７、８の経路トポロジの場合と同じであるが、負荷素子４０３と４０７との間の距離は、図７、８に例示されている異なる経路トポロジが使用される場合には著しく異なる。図７、８の異なる経路トポロジは、全配線長が同じままであったとしても、負荷素子４０３、４０７に対して非常に異なる距離、したがって異なる抵抗値を生じる。多くのバックエンド・ツールではネットを配線する際に全配線長を最小にしようとするので、合成ツール側で、図７、８の異なる経路トポロジのどれがバックエンド・ツールで使用できるかを予測することは困難である。例えば、一方のバックエンド・ツールで図７のトポロジを使用するが、他のバックエンド・ツールでは図８のトポロジを使用することがある。経路トポロジの不確定性により、バックエンド・ツールは、タイミング要件を満たさないソリューションを生成する場合があるが、それは、バックエンド・ツールは、合成ツールの推定と異なる経路トポロジを使用してネットを配線できるからである。
【００８６】
図９は、本発明の一実施形態により経路トポロジの不確定性を低減する方法を例示する図である。図９では、複製された駆動素子４０９は、元の駆動素子４０１の複製である。元の駆動素子のネットは変換され、ドライバ素子４０１、４０９に対し負荷素子４０３〜４０７を分割する。変換の後、元の駆動素子４０１は、素子４０３のみを駆動し、複製された駆動素子は、素子４０５、４０７を駆動する。したがって、バックエンド配線ツールで使用される予想経路トポロジは明らかになる。経路トポロジに対する感度が低減される。
【００８７】
経路トポロジ内には不確定性の原因が多数ある。バックエンド詳細ルータ（例えば、メーズ(maze)・ルータまたはチャネル・ルータ）では、合成ツールに埋め込まれているグローバル・ルータ・エスティメータと比較すると、ネットの配線に異なるアルゴリズムを使用することができ、したがって、異なる順序でネット上に負荷素子を配線することができる。また、配線輻輳の推定がわずかでも違うと、異なる選択になる可能性もある。この変動により、特に高いファンアウト・ネットの場合に、タイミングの著しい変動が出力される可能性がある。したがって、駆動素子と負荷素子との間の予測される配線遅延は、詳細な配線と抽出後に決定されるものとかなり異なる可能性がある。経路トポロジ内の不確定性により、合成ツールでモデル化されたドライバ負荷パス遅延は、設計の配線後にバックエンド内で決定されるドライバ負荷遅延とあまりよく相関しない可能性がある。
【００８８】
バックエンド・ルータ・ツールによって実行された配線が物理的合成時に推定される配線と相関する確率を高めるアルゴリズムが存在する。物理的合成ツールは、フォワード・アノテーションの形で配線に関する情報を提供することができる。フォワード・アノテーションは、ネット迂回路により生じうるネット遅延相関問題を最小限に抑えることを目的とする、ネット経路順序付けとアンカー・セルを含むことができる。しかし、従来の合成ツールでは、ネット遅延相関に対する負荷素子の順序の影響を考慮しない。
【００８９】
この相関問題を最小限に抑えるために、本発明の一実施形態では、相関問題を引き起こす可能性のあるネットを選択的に選び、優先順位順でそれらを変換する。これらの変換は、ファンアウトの個数を減らし、ネットの形状を非対称にすることによりネット遅延に対する不確定性を最小にする。コスト判定基準が満たされていることを保証しつつ遅延相関を改善する詳細な方法について以下で説明する。
【００９０】
本発明の一実施形態では、経路トポロジ変動最小化アルゴリズムを使用し、経路トポロジに対し敏感な遅延を持つネットの集合を見つけて変換する。異なる経路トポロジがバックエンド・ルータで使用される場合に、特に、バックエンド・ルータで使用される代替経路トポロジにより物理的合成時に予測されるのと異なるネット上のピンへの遅延特性が生じる可能性がある場合に、その変換が、発生するタイミング違反の可能性を低減する。一実施形態では、ネット選択と変換アルゴリズムは、新しいネットが変換できなくなるまで設計内のすべてのネットを調べ、所定のコスト関数を悪化させない方法で感度を低減する。それによって、回路の物理的合成設計は、バックエンド配線ツールが設計の配線に使用される場合に後続の無効な配線実装が続く可能性を低減して最適化される。
【００９１】
一実施形態では、コスト関数は、最悪ネガティブ・スラック、トータル・ネガティブ・スラック、変換されるネットの全配線長、ピーク利用制限、設計の最大許容面積増大のうちの１つまたは複数に基づく。最適化プロセスにおける異なる強調部分に対し、異なるコスト関数を構築できることは理解されるであろう。最適化プロセスに対する変換は、ユーザによって指定された論理的および物理的制約条件に違反しない。
【００９２】
本発明の一実施形態では、一組の論理的および物理的最適化を使用し、ネットを変換して経路トポロジに対する感度を低減する。例えば、ネットに接続されている論理回路は、複製、サイズ設定、バッファリング、配置変更を通じて変換することができる。ネットのドライバを複製できる場合、複製変換を使用して、ネットのシンク（ネットのドライバの負荷素子）を分割する。複製変換が使用できない場合（例えば、設計制約条件があるため）、ネットは、新しいバッファがネットのシンクのいくつかを駆動するようにバッファリングすることができる。複製されたインスタンス（またはバッファ）や元のドライバのサイズ設定は、コスト関数が悪化しないように実行することができる。
【００９３】
新しいインスタンスが変換により作成されると、それらは、正当な位置にあるダイス上に配置される。一実施形態では、コスト関数は、変更の公認の前後にチェックされる。それらの変更は、コスト関数が悪化する場合には逆転される。例えば、パス上の最悪ネガティブ・スラックが変換は後に悪化する場合、変換は逆転される。
【００９４】
本発明の一実施形態では、ネット毎に可能な代替経路トポロジを調べて、変換対象のネットを選択する。標準的な配線長駆動ルータは、特定の領域内の全配線長と輻輳を最小にする有効な経路を作成しようと試みる。そのような配線長駆動ルータは、非常に異なる遅延特性を持つが、ほぼ等しい配線長と輻輳特性を持つ、多数の異なる経路トポロジのうちの１つを使用することができる。標準的なタイミング駆動ルータは、遅延を最小にしようと試みる。しかし、タイミング駆動ルータであっても、輻輳または他のコストを最小にするために代替トポロジを使用することができる。タイミング駆動配線は、非常に高価であり、設計全体上で実施できない。輻輳は、さらに、配線経路アルゴリズムと設計内の小さな変動に基づいて変化する場合があるため、バックエンド配線ツール内で使用されるアルゴリズムが知られているとしても、まだ、実際の経路を予測することには困難な場合がある。したがって、本発明の一実施形態では、これらの経路のどれかが設計制約条件（例えば、タイミング要件）に違反するかどうかを判定するためにさまざまな配線経路アルゴリズムにより使用される可能性がある可能なトポロジを調べる。経路トポロジの選択に対する設計制約条件の有効性の影響を受ける可能性のあるネットを識別した後、変換を設計に適用し、バックエンド・ツールを使用して配線した後に設計が無効になる可能性を低減することができる。
【００９５】
複数のこのようなネットが特定のパス上に存在する場合に効果が高まることがあるので、本発明の一実施形態では、変動がないかサブパスまたはパスを調べる。
【００９６】
可能な経路トポロジを決定するのは時間がかかる場合があるため、また多くの資源を使用するので、本発明の一実施形態では、多数の発見的手法を使用して、異なる配線または配線推定を実行せずに経路トポロジに敏感なネットを判別する。例えば、ネットが多数の判定基準を満たしている場合、経路トポロジに敏感である可能性が非常に高いと判断され、ネット遅延相関の問題が生じうる。
【００９７】
一実施形態では、ネットのファンアウトの個数は、主要な選択基準である。ファンアウトの個数が増大した場合、シンク順序は、遅延モデル内の変動に対する高い影響を持つことがある。一実施形態では、ネットは、ネットのファンアウトの個数がしきい値よりも大きい（例えば、２）場合にのみ経路トポロジ感度の低減の対象とみなされる。ファンアウトの個数が少ない（例えば、２以下）場合、ネットは、経路トポロジに対し敏感でないとみなすことができる。
【００９８】
ネットの形状は、さらに、代替経路トポロジの可能性にも影響を及ぼすことがある。例えば、ネットの形状が正方形に近い場合、ルータがシンクの配線順序を選ぶ選択肢が増えることになり、したがって、ネットのシンクまでの遅延は、さらに予測不可能になる可能性がある。これは、特に、配線長駆動ルータの場合に当てはまるが、それは、正方形の形をしたネット上の個々のシンクまでの遅延は、全配線長が図７、８に例示されているようにかなり一定であっても、シンクが接続される順序とともに大幅に変化する可能性がある。そのため、一実施形態では、変換対象のネットも形状歪み基準を使用して選択される。
【００９９】
図１０〜１２は、本発明の一実施形態により経路トポロジの不確定性による配線長の変動を推定する方法を例示する図である。図１０は、長さＳの短い辺と長さＬの長い辺を持つ矩形形状のネットを例示している。駆動素子（Ａ５０１）の位置と負荷素子（Ｂ５０７、Ｃ５０５、Ｄ５０３）の位置は、ネットの形状を決定する。バックエンド・ルータは、通常、全配線長を最小にするので、ネットの配線は、ネットの形状の長い辺の方向ではなく短い辺の方向の迂回路を含むのがふつうである。例えば、図１１に例示されているＡ（５０１）からＤ（５０３）、Ｃ（５０５）への経路と比較して、図１０に例示されているＡ（５０１）からＢ（５０７）、Ｃ（５０５）、Ｄ（５０３）への経路は、Ｄ（５０３）に対する短い辺の方向の迂回路を含む。ネットの形状の短い辺の方向の迂回路は、ネットの境界ボックスの短い辺の長さの２倍、配線長を増やす。そのため、本発明の一実施形態では、負荷素子の位置から決定される、ネットの境界ボックスの短い辺の長さを使用して、経路トポロジの変動による配線長の変動を推定する。
【０１００】
図１２は、境界ボックスの短い辺の方向の迂回路の影響を例示している。図１２では、境界ボックス５２０は、駆動素子（５２１）の負荷素子（例えば、５２３〜５２７）を囲む。経路５３１（実線）は、ドライバ５２１と負荷５２３との間のマンハッタン距離（直線距離とも呼ばれる）を示す。マンハッタン距離は、通常、ドライバと負荷との間の配線距離の下限である。経路５３３（破線）は、素子５２３の前で素子５２７と５２５を接続する迂回路を示しており、これは、そのマンハッタン距離にわたる境界ボックス（５２０）の短い辺の長さ（Ｓ）の２倍だけ、素子５２３の配線長を近似的に増やす。そこで、本発明の一実施形態では、境界ボックスのマンハッタン距離と短い辺の長さ（Ｓ）を使用して、異なる経路トポロジを考慮して配線長（２つの論理素子間の距離）を推定する。
【０１０１】
一実施形態では、駆動素子と負荷素子との間の距離は、その駆動素子と負荷素子との間のマンハッタン距離（直線距離とも呼ばれる）に基づいて推定される。異なる経路トポロジの影響を考慮しつつ、距離は、さらに、マンハッタン距離と負荷素子の境界ボックスの短い辺の長さに基づいて推定される例えば、境界ボックスの短い辺の方向に迂回路があると、境界ボックスの短い辺の長さの２倍だけ、配線長が増大する。そのため、ｄMを駆動素子と負荷素子との間のマンハッタン距離とし、Ｓを負荷素子の境界ボックスの短い辺の長さとすると、この距離はｄM＋２×Ｓと推定することができる。その後、配線遅延は、Ｄuを単位配線遅延とすると、（ｄM＋２×Ｓ）×Ｄuと推定することができる。一実施形態では、ネットは、経路トポロジ内の差による配線長の推定される変動により、スラックが負になる（またはパス上の最悪ネガティブ・スラックを悪化させる）場合に変換の候補として選択される。
【０１０２】
異なる定式化を使用して、異なる状況にある経路トポロジの変動による距離変動をモデル化することができることに注意されたい。例えば、配線遅延は、曲線の当てはめにより統計データから求められる係数を含む実験式を使用して推定することができる。バック・アノテーション（または典型的な設計での試験実行）を使用して、特定のバックエンド・ソフトウェア・ツールに対する係数を導くことができる。したがって、異なるバックエンド・ソフトウェア・ツールに対し、異なる定式化を使用することができる。
【０１０３】
経路トポロジ内の不確定性による駆動素子と負荷素子との間のパス遅延の同じ変動は、異なるパス上のタイミング制約条件に対し非常に異なる影響を及ぼす可能性がある。そのため、本発明の一実施形態では、さらにタイミング要件に基づいて変換対象のネットを選択する。例えば、ドライバ・スラックがタイミング・クリティカルまたはクリティカルに近いパス上のネットについて範囲Ｔ内にある場合、そのネットは経路トポロジの感度の考慮対象として選択される。適切なスラックを持つパスであれば、遅延相関問題を引き起こす可能性はないと考えることができ、したがって、評価する必要はない。本発明の一実施形態では、適切なスラックを持つパスに対する遅延推定相関は、問題があるとは考えられない。そのため、タイミング・クリティカルまたはクリティカルに近いパス上のネットのみが、経路トポロジへの感度を低減する対象として考慮される。輻輳の量に関する不確定性を含む、最終経路に関する追加不確定性も、考慮することができる。例えば、輻輳の予測が正確であるほど、必要なＴの範囲は小さくてよい。さらに、Ｔの値は、典型的な設計についてバックエンド・ツールを何回も実行することに基づいて実験的に決定することが可能である。そのため、本発明の一実施形態では、ドライバ・スラックは、ネット・トポロジのせいで相関問題を生じる可能性があるネットを選択する際の追加判定基準である。
【０１０４】
ユーザ指定設計制約条件などの他の判定基準も、変換の候補として選択されるネットの集合をフィルタ処理するために使用することができる。例えば、いくつかのネットは、ユーザ指定設計制約条件に従って変換することができない。
【０１０５】
ネット候補の集合が変換対象として選択された後、ネットの集合を変換に関して優先順位付けすることができる。例えば、ネットの集合は、感度を低減する素子のサイズ設定について上で説明したのと同様に、流れに従って、または感度を指標に従って、またはグラフ上の最小カットに従って、優先順位付けすることができる。この流れは、ネット候補を通る全パスの数、またはネット候補を通るネガティブ・スラック・パスの個数、またはネット候補通る輻輳パスの個数、またはネット候補を通る敏感なネットを含むパスの個数、またはネット候補を通るパスの個数の重み付けカウント（例えば、輻輳係数、ネガティブ・スラック、感度の指標など）とすることができる。本発明の一実施形態では、多数の変換（例えば、バッファリング、複製、サイズ設定、配置並べ換え）を使用して、設計のコスト関数を悪化させることなく経路トポロジの影響を緩和する。
【０１０６】
通常、Ｉ／Ｏポートとマクロは複製から除外される。制約条件に違反した場合に設計の検証を妨げるものなどの設計制約条件も、状況によっては、複製を妨げる可能性がある。駆動インスタンスの複製が許容可能が場合（例えば、設計制約条件を破らない、コスト関数を悪化させない）、ネットは変換される。例えば、新しいネットの配線長の総和が元の単一ネットの配線長にほぼ等しくなるように、ネットのシンクを元の駆動インスタンスと複製された駆動インスタンスとの間に分割する。これにより、バラツキを減らしながら元のゲート面積と配線長を保持する。分割されたネットは、ネットの形状に関して高い歪みを持ち、したがって、元の駆動インスタンスと複製された駆動インスタンスの負荷素子の境界ボックスは、縦横比を減じている。元のドライバと新しいドライバは、コストが最小になるように適宜サイズ設定される。
【０１０７】
バッファリングは、複製ができない場合にできるようにする、またコスト判定基準に違反せずにトポロジの不確定性を低減する手段となる、もう１つの代替手段である。一実施形態では、パスにそって余分にバッファを追加することは、余分バッファが伝送のコスト（例えば、パス上の最悪ネガティブ・スラック）を上昇させない場合にのみ実行される。バッファの挿入が許容される場合（例えば、バッファを配置するための場所がある）、ネットのシンクは分割され、新しく作成されたネットがネットの形状に関して高い歪みを持つようにシンクの一部が挿入されたバッファに再接続される。したがって、変換の後、元のドライブの負荷素子の境界ボックスおよび新しいバッファの負荷素子の境界ボックスは、縦横比が小さくなる。さらに、新しいネットの配線長の合計が一実施形態の元の単一ネットの配線長にほぼ等しくなるように分割が行われる。この目標は、バラツキを改善（低減）しつつ元のゲート面積と配線長を保持する。元のドライバは、さらに、コスト関数が最小になるようにサイズ設定することができる。
【０１０８】
いくつかの場合において、ドライバ（またはバッファ）の複数がすでに存在する可能性があり、これは、経路トポロジの不確定性を低減すること以外の目的のために合成プロセスにおいて作成される場合がある。このような場合、これらの存在している素子の負荷素子は、既存の設計制約条件に反せずに経路トポロジの不確定性の低減のため再配分または再分割することができる。
【０１０９】
いくつかの場合において、負荷素子および／または駆動素子の配置位置は、経路トポロジ内の不確定性の影響を軽減するように調整することができる。そのため、ネットのシンクの配置を変えて、負荷素子の境界ボックスの縦横比を低減することができる（ネットの形状の歪みを大きくする）。
【０１１０】
その他、本発明の一実施形態では、適度な数のネットが修正対象に選択される。修正では一定に近い配線長とゲート面積を維持しようと試みるので、修正された設計の配線可能性とコストは未修正の設計と同様のままであるが、配線後に無効な設計となる可能性が低減されている。
【０１１１】
図１３は、本発明の一実施形態により回路を設計する方法を例示する図である。オペレーション６０１で回路の設計（例えば、回路の論理合成ソリューションのネットリスト表現）を受け取った後、オペレーション６０３は、回路の設計の配置を実行する。オペレーション６０５は、配線内の不確定性によるタイミング制約条件の違反の可能性を低減するために変換対象のネットの集合を選択する。オペレーション６０７では、ネットの選択された集合に対する回路設計の一部分に変換を実行して、ルータにより配線されたときにタイミング制約条件に違反することにそのネットの集合が関わる可能性を低減する。本発明の一実施形態では、変換は、配線長とゲート面積が実質的に同じままである範囲で実行されるが、その一方で、バックエンド配線ツールにより使用することができる経路トポロジ内の不確定性、特に、タイミング制約条件を満たさない配線ソリューションに至る可能性のある経路トポロジの不確定性を低減する。
【０１１２】
図１４は、本発明の一実施形態により回路設計を最適化する方法を例示する図である。オペレーション６２１が回路の設計に対する配置ソリューションを受け取った後、オペレーション６２３は、経路トポロジへの感度を低減することについてネットを調べる。オペレーション６２５でそのネットの遅延が経路トポロジに対し敏感であると判定した場合、オペレーション６２７で、経路トポロジに対するネットの感度を低減するために設計の一部分に変換を実行する。例えば、駆動素子を複製する、またはバッファを挿入する、または素子の配置を変更する、または負荷素子を既存の複製された駆動（またはバッファ）に再配分することができる。オペレーション６２９で、変換がコスト関数を悪化させる、または設計制約条件に違反すると判断された場合（例えば、新しく挿入された素子の配置に対する面積不足）、オペレーション６３３は、その変換をキャンセル（または逆転）し、そうでなければ、変換は保持される（６３１）。感度がすでに、正常に低減されていない場合、オペレーション６３５では、適用可能が代替変換があるかどうかを判別する。コスト関数を悪化させない、また設計制約条件に違反しないようにしながら、ネットの経路トポロジ感度を低減するための変換のリストの作成を行うことができる。それぞれのネットは、オペレーション６３７でネットがすでに考慮されていると判断するまで、経路トポロジに対する感度の低減について考慮される。
【０１１３】
本発明の一実施形態では、ネット上の遅延が経路トポロジに対し敏感であるか否かを推定するために多数の判定基準が使用される。例えば、ネットのファンアウトが３つよりも少なく、これは経路トポロジに敏感でないと考えることができる。さらに、ネットのドライバのスラックがしきい値よりも高い場合も、経路トポロジに敏感でないと考えることができる。さらに、経路トポロジ内の変動による余分な推定距離（例えば、負荷素子の境界ボックスの短い辺の長さの２倍）により、スラックが負にならない（またはパス上の最悪ネガティブ・スラックよりも悪くない）場合に、ネットは、経路トポロジに敏感でないと考えることができる。そのため、経路トポロジに対するネットの感度は、異なるアルゴリズムを使用して詳細配線を実行せずに、また実際の異なる経路トポロジを判別せずに、効率良く評価される。
【０１１４】
図１５は、本発明の一実施形態により最適化するネットを選択する方法を例示する図である。オペレーション６５１では、ネットの推定された経路を判別する。推定された経路は、グローバル・ルート・エスティメータを使用して決定することができる。それとは別に、推定される経路は、ネットの駆動素子と負荷素子の位置からのみ決定することができる。例えば、素子間の距離は、負荷素子と駆動素子との間のマンハッタン距離として推定できる。推定された経路は、タイミング要件が満たされているかどうか判別するために使用される。例えば、推定された経路を使用して、素子のスラック、パス上の最悪ネガティブ・スラック、その他のタイミング・パラメータを決定することができる。タイミング要件が満たされていない場合、回路の設計は修正される。通常、経路トポロジの感度の低減は、受け入れ可能なソリューションが得られた後でないと実行されないが、経路トポロジの感度の低減は合成プロセス時に実行することも可能である。オペレーション６５３で、ネットに対し代替経路があると判定した場合、オペレーション６５５は、代替経路がネットに使用される場合にタイミング・パラメータを決定する。代替経路は、異なる戦略を使用する配線を通じて決定することができるが、これは、時間のかかる作業である。本発明の一実施形態では、ネットに対し代替経路が存在しているかどうかは、複数の判定基準から決定されるが、これは、非常に効率よくチェックすることができる。これらの判定基準の例は、ネットのファンアウトの個数とネットの形状を含む。オペレーション６５７で、タイミング・パラメータが設計制約条件の範囲内にあると判定した場合（または、オペレーション６５３で、ネットに対する代替経路がないと判定された場合）、そのネット（６６１）には変換は不要であり、これは、経路トポロジに対する感度の低減のため変換を必要としない。オペレーション６５７で、タイミング・パラメータが設計制約条件の範囲内にないと判定した場合、オペレーション６５９は、経路トポロジに対する感度を低減する変換のためネットを選択する。
【０１１５】
図１６は、本発明の一実施形態により最適化するネットを選択する詳細な方法を例示する図である。オペレーション６７１では、クリティカル・パスとクリティカルに近いパス上のネットを判別する（例えば、クリティカルな値の範囲内のスラックを持つドライバ）。オペレーション６７３で、クリティカル・パスまたはクリティカルに近いパス上のネットのファンアウトの個数が２以下であると判定した場合、ネットは、感度低減オペレーション（６８５）に関して無視され、そうでなければ、オペレーション６７５は、ネットのシンクの境界ボックスの縦横比を決定する。オペレーション６７７で、境界ボックスの縦横比は１に近くない（例えば、０．５などしきい値よりも小さい、または統計データから求められた数値）場合、ネットは、感度低減オペレーション（６８５）に関して無視され、そうでなければ、オペレーション６７９で、代替配線パスによる余分な距離を推定する（例えば、矩形の境界ボックスの短い辺の２倍）。オペレーション６８１で、余分な距離がネガティブ・スラック（または他のタイミング要件の違反）に至らないと判定した場合、ネットは、感度低減オペレーション（６８５）に関して無視され、そのような判定しない場合、オペレーション６８３で、感度低減オペレーションに対するネットを選択する。図１６に例示されているすべての選択基準を使用する必要はないことに注意されたい。例えば、オペレーション６７７は、一実施形態では使用することができない。さらに、他の選択基準も、図１６に例示されている選択基準の一部またはすべてといっしょに使用することもできる。例えば、ネットの集合が変換のための候補として選択された後、流れに応じて、またはサイズ設計のための敏感なインスタンスの優先順位付けと同様にしてグラフ上の最小カットの選択を通じて、ネットの集合を優先順位付けすることができる。
【０１１６】
図１７は、本発明の一実施形態により経路トポロジの感度を低減するため回路設計を変換する詳細な方法を例示する図である。オペレーション７０１で感度低減オペレーションの対象のネットを選択した後、オペレーション７０３で、ドライバおよびシンクの配置を変更して、経路トポロジへの感度を低減する。例えば、配置を変更して、ネットのシンクの境界ボックスの縦横比を小さくできる。オペレーション７０５で、感度を下げるためにネットに対しさらに変換を必要とすると判断した場合（例えば、配置を変更することによりネットのシンクの境界ボックスの縦横比を十分に下げられない場合）、オペレーション７０７では、ネットのドライバを複製できるかどうかを判定する。設計制約条件により、ドライバの複製が可能である場合、オペレーション７１１で、ネットのドライバを複製し、オペレーション７１３で、複製されたドライバを配置し、オペレーション７１５で、ネットのシンクを、元のドライバのシンクと複製されたドライバのシンクとして分割し、経路トポロジに対する感度を低減し、オペレーション７１７で、元のドライバと複製されたドライバのサイズを設定する（例えば、コストを最小にするため）。しかし、ネットのドライバを複製できない場合（例えば、ネットのドライバがＩ／Ｏポートまたはマクロであるか、または複製されたドライバの配置に適切な場所がない）、オペレーション７０９で、ドライバとネットのシンクとの間にバッファを挿入できるかどうか（例えば、ドライバとネットのシンクとの間にバッファを配置するのに適した場所があるかどうか）を判別する。オペレーション７２１がネットの元のドライバのシンクとしてバッファを挿入した後、オペレーション７２３で、バッファを配置し、オペレーション７２５で、ネットのシンクを、元のドライバのシンクとバッファのシンクとして分割して経路トポロジへの感度を低減し、オペレーション７２７で、元のドライバのサイズを設定する（例えば、面積コストを低減するため）。本発明の一実施形態では、バッファの挿入は、修正しても回路を悪化させない場合にのみ受け入れられる。例えば、バッファの挿入は、パス上の最悪ネガティブ・スラックが悪化しない場合にのみ受け入れられ、その場合、推定された配線パスが、代替経路トポロジによる余分な距離を考慮せずに使用される。そのため、経路トポロジに対する感度の低減は、回路の設計を低下させずに実行される。ドライバの複製とバッファの挿入が許容可能でない場合、他の変換をさらに試みることが可能である。例えば、ドライバが複製されたインスタンスをすでに持っている場合、シンクを再分割して、その感度を低減することができる。
【０１１７】
上記の例の少なくとも一部は、タイミング制約条件に関係する設計制約条件を伴う（例えば、回路の最悪ネガティブ・スラック、回路の設計における論理素子のインスタンスのスラック、回路の設計におけるパス上の遅延、回路のトータル・ネガティブ・スラックなど）。しかし、設計制約条件は、他の種類の制約条件とすることが可能であることは理解できるであろう。例えば、これらの制約条件は、最大静電容量、ドライバ素子と負荷素子との間の最大配線長、または異なる種類の設計規則と制約条件の集合に関する条件とすることができる。設計制約条件は、幾何学的パラメータ、タイミング・パラメータ、インピーダンス・パラメータ、および／またはその他のパラメータに関する条件とすることができる。本発明の少なくともいくつかの実施形態によれば、これらの制約条件の変更の影響は、経路トポロジの変動として推定され、その後の実装の経路トポロジの変動がそれらの制約条件の違反を引き起こす可能性がある確率を低減するために変換が実行される。
【０１１８】
上記の例のうちのいくつかでは、初期の段階の設計（例えば、合成変換）における不確定性は、回路設計の異なる実装が後の方の段階の設計（例えば、配線）で実行された場合の設計制約条件に関連するパラメータの変更によるものである。しかし、不確定性は、さらに、いくつかの設計構成の設計制約条件に関連するパラメータを推定する際の可能な誤差からも発生しうる。例えば、いくつかのパラメータの推定の正確さは、特定の配線トポロジに関しては劣ることがある。そのため、一実施形態では、これらのパラメータのソリューションの束縛された誤差は、設計制約条件に違反する可能性を判別するために配線トポロジに関連付けられる。それとは別に、推定の正確さを低下させる配線トポロジは、合成変換を実行して、それらの構成を回避し、配線後に無効な設計が生じる可能性低減するように識別することもできる。
【０１１９】
例えば、いくつかのネット・トポロジは、合成時に使用される高速で、単純なネット遅延モデルでモデル化することは困難である。Ｅｌｍｏｒｅ遅延モデルは、高速なネット遅延モデルの一例である。簡単に計算できるネット・モデルは、状況によっては精度を落とす。これらの状況におけるタイプのネットは、経路トポロジの変更の影響を受けやすいと考えることができる。変換（例えば、複製）を使用して、単純な遅延モデルの不正確さを低減するために可能なネット・トポロジを修正することができる。
【０１２０】
例えば、回路設計においてドライバの近くにあるいくつかの負荷がネット上にあり、ほかは遠く離れている場合、パス遅延予測は、遠く離れている負荷、またはドライバに関して異なる方向に配置されている負荷上では不正確になる可能性があり、これは、特に、その負荷への著しい遷移低下がある場合にはそうである。さらに、経路トポロジの影響が不正確な遅延予測に加わる可能性がある。このような構成では、Ｅｌｍｏｒｅ遅延モデルは、正確でなく、設計は、異なる経路トポロジに敏感になる。そのため、単純な遅延モデル（例えば、Ｅｌｍｏｒｅ遅延モデル）が合成時に使用される場合、設計制約条件違反の可能性は高い。本発明の一実施形態では、そのようなネットのドライバは、近くの負荷が一方のドライバにより駆動され、遠い負荷が他方のドライバにより駆動されるように複製される。同様に、本発明の一実施形態では、同じドライバに関して異なる方向に配置されている負荷を持つことを回避することを試みる（例えば、ドライバを複製することにより）。ドライバを複製してシンクのいくつかに近づけると、遅延推定の精度が向上し、バックエンドで使用される異なる経路トポロジが設計制約条件の違反を引き起こす可能性を減じるこのような合成変換により、遅延の推定精度は向上し、後の段階の実装において無効な設計となる可能性が低くなる。
【０１２１】
本明細書では、発明は特定の例示的な実施形態を参照しつつ説明がなされている。本発明は、付属の請求項で定められているように、本発明の広い精神と範囲を逸脱することなくさまざまな修正を加えられることは明白であろう。したがって、明細書および図面は、限定ではなく、説明することを目的としているものとみなすべきである。
【図面の簡単な説明】
【０１２２】
【図１】本発明とともに使用できるデータ処理システムのブロック図の例である。
【図２】本発明の一実施形態により回路を設計する方法を示す図である。
【図３】本発明の一実施形態により回路を最適化する方法を示す図である。
【図４】本発明の一実施形態により回路を最適化する詳細な方法を示す図である。
【図５】本発明のいくつかの実施形態により回路を選択的に修正する詳細な方法を示す図である。
【図６】本発明のいくつかの実施形態により回路を選択的に修正する詳細な方法を示す図である。
【図７】経路トポロジの不確定性による配線長を推定する際の不確定性を例示する図である。
【図８】経路トポロジの不確定性による配線長を推定する際の不確定性を例示する図である。
【図９】本発明の一実施形態により経路トポロジの不確定性を低減する方法を例示する図である。
【図１０】本発明の一実施形態により経路トポロジの不確定性による配線長の変動を推定する方法を例示する図である。
【図１１】本発明の一実施形態により経路トポロジの不確定性による配線長の変動を推定する方法を例示する図である。
【図１２】本発明の一実施形態により経路トポロジの不確定性による配線長の変動を推定する方法を例示する図である。
【図１３】本発明の一実施形態により回路を設計する方法を例示する図である。
【図１４】本発明の一実施形態により回路設計を最適化する方法を例示する図である。
【図１５】本発明の一実施形態により最適化するネットを選択する方法を例示する図である。
【図１６】本発明の一実施形態により最適化するネットを選択する詳細な方法を例示する図である。
【図１７】本発明の一実施形態により経路トポロジの感度を低減するため回路設計を変換する詳細な方法を例示する図である。
【技術分野】
【０００１】
本出願は、参照により本明細書に組み込まれる、２００３年５月３０日に発明者Ｃｈａｍｐａｋａ Ｒａｍａｃｈａｎｄｒａｎ、Ａｎｄｒｅｗ Ｃｒｅｗｓ、Ｋｅｎｎｅｔｈ Ｓ．ＭｃＥｌｖａｉｎにより出願された「Ｍｅｔｈｏｄ ａｎｄ Ａｐｐａｒａｔｕｓ ｆｏｒ Ａｕｔｏｍａｔｅｄ Ｃｉｒｃｕｉｔ Ｄｅｓｉｇｎ」という表題の仮出願第６０／４７５，０５９号の出願日の利益を主張するものである。
【０００２】
本発明は、自動回路設計に関するものであり、より具体的には、詳細な設計レイアウトを実行する前の回路設計の自動最適化に関するものである。
【背景技術】
【０００３】
デジタル回路の設計（例えば、超大規模集積回路技術のスケールの）では、設計者はコンピュータ援用手法を採用することが多い。デジタル回路の記述のためハードウェア記述言語（ＨＤＬ）などの標準言語が開発されたことで、複雑なデジタル回路の設計とシミュレーションを楽に行うことができる。ＶＨＤＬやＶｅｒｉｌｏｇなどのいくつかのハードウェア記述言語は、業界標準として発展してきた。ＶＨＤＬやＶｅｒｉｌｏｇは、汎用ハードウェア記述言語であって、これらの言語を利用することにより、抽象データ型を使用してゲート・レベル、レジスタ転送レベル（ＲＴＬ）、またはビヘイビア・レベルでハードウェア・モデルを決めることができる。デバイス技術の進歩に合わせて、ＨＤＬをより新しいデバイスや設計スタイルに対応させるため、さまざまな製品設計ツールが開発されてきた。
【０００４】
ＨＤＬコードを使って集積回路を設計する場合、まずコードを書き、その後、ＨＤＬコンパイラによりそのコードをコンパイルする。ＨＤＬソース・コードではあるレベルで回路素子を記述し、コンパイラが、このコンパイル結果からＲＴＬネットリストを出力する。ＲＴＬネットリストは、通常、フィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）または特定用途向け集積回路（ＡＳＩＣ）などの特定のベンダの集積回路の技術／アーキテクチャに依存しないという点で、技術独立のネットリストである。ＲＴＬネットリストは、回路素子の回路図表現に対応する（ビヘイビア図とは反対に）。そこで、技術独立のＲＴＬネットリストからベンダの技術／アーキテクチャで回路を作成するために使用できる技術特有のネットリストに変換するマッピング・オペレーションが実行される。ＦＰＧＡベンダはその集積回路内に論理回路を実装するためにさまざまな技術／アーキテクチャを使用することはよく知られている。したがって、技術独立のＲＴＬネットリストは、特定のベンダの技術／アーキテクチャに特有のネットリストを作成するようにマッピングされる。
【０００５】
このプロセスでは多くの場合望ましい１つのオペレーションで、特定の集積回路のレイアウトのプランニングを実行し、タイミング問題の制御と集積回路の領域間の相互接続の管理を行う。これは、ときには「フロア・プランニング」と呼ばれることもある。通常のフロア・プランニング・オペレーションでは、集積回路の回路エリアを、ときには「ブロック」とも呼ばれる複数の領域に分割し、その後、ブロック内に置かれるようにロジックを割り当てる。これらの領域は、矩形でも非矩形でもよい。このオペレーションの結果として、論理回路の位置に対する見積もり誤差が集積回路のサイズからブロックのサイズ（タイミング見積もりの誤差を小さくする傾向がある）に低減されることと、１つの非常に大きな問題から一連のより単純な問題に還元されるため配置と配線が通常高速化されることの２点が実現される。
【０００６】
チップ上にコンポーネントを配置し、コンポーネント間に配線した後、タイミング解析（例えば、タイミング・シミュレーション、または静的タイミング解析）を実行して、論理素子間の信号遅延を正確に決定することができる。バック・アノテーションを実行し、後の設計段階からの情報でより抽象的な設計を更新することができる。例えば、バック・アノテーションでは、配置と経路のデータベースから配線遅延情報と配置情報を読み込んで、論理合成設計のアノテーションを実行する。バック・アノテーションされた遅延情報は、タイミング要件が満たされていないクリティカル・パスを識別するために使用することができ、タイミング要件を満たすように論理合成を改善することもできる。
【０００７】
論理合成用の典型的なソフトウェア・プログラムでは、ネットのファンアウトに基づく遅延推定器機能を使用する。特定のファンアウトを持つネットに対応するすべての論理素子は、同じ配線遅延を持つと仮定されているため、推定された遅延情報はあまり正確ではない。実際には、配線遅延は、一方の論理素子から次の論理素子へ引き回される線の長さに依存する。配置距離と配線遅延との間の相関は、ファンアウトと配線遅延との間の相関よりも高い。論理合成の遅延推定器内の誤差のため、ソリューションが論理合成時には有効であるように見えても、配置と配線作業の後に無効であると判明することがある。
【０００８】
設計レイアウト（例えば、配置と配線）の後、サイズ変更またはバッファリングのような制限付きの最適化（インプレース最適化と呼ばれる）のみが通常実行される。しかし、インプレース最適化では、制限付きの改善しか得られない。インプレース最適化で、タイミング制約条件を満たすようにソリューションを調整できない場合、論理合成の調整を実行することにより、論理合成や配置と配線の反復が生じて費用が増大する。
【０００９】
クリティカル・パスの遅延短縮のための合成と論理回路の最適化は、論理回路を設計し、実装するうえで重要なステップである。合成段階で不正確な遅延推定だと、設計レイアウトが無効になる可能性があるため、よい品質の最適化結果を得るために正確な配線遅延情報を用意するのが望ましい。タイミング要件（例えば、スラック要件）を満たすように論理合成を改善しなければならない場合、合成と設計レイアウトとを繰り返さなければならず費用がかかる。スラックとは、望む遅延と実際の（推定または計算された）遅延との差のことであることに注意されたい。望む遅延が実際の遅延よりも大きい場合、スラックは正であり、そうでない場合、スラックは負である。通常、タイミング要件を満たすためにはスラックを正にする（またはゼロに近づける）必要がある（例えば、配線遅延を減らしてスラックを高めることで）。例えば、合成中に、トータル・ネガティブ・スラック・アルゴリズム（例えば、カリフォルニア州のＳｙｎｐｌｉｃｉｔｙ，Ｉｎｃ．社が販売している回路設計コンパイラＳｙｎｐｌｉｆｙで使用されている）では、スラックが改善に対する候補としてネイティブであるすべての場合を考慮するが、それは、ネガティブ・スラックを持つ候補はどれも、物理設計後、クリティカルになりうるからである。タイミング要件が満たされるようにスラックを正の値にするのがふつうである。
【発明の開示】
【課題を解決するための手段】
【００１０】
回路のその後の実装（例えば、配置と配線）で発生しうる逸脱に関する設計パラメータの感度に応じて回路設計（例えば、合成ソリューション）を自動的に修正する方法と装置が、本明細書では説明される。例えば、２よりも大きい多数のファンアウトを持ち、タイミング・クリティカル・パスまたはクリティカルに近いパス上のネットは、経路トポロジに敏感であると考えられ、代替配線経路だと、タイミング制約に違反する可能性があり、その後の配線ソリューションのタイミング問題が発生する可能性を低減するために、コスト関数を悪化させない範囲で、回路設計に変換を選択的に適用するとよい。本発明のいくつかの実施態様は、この節で要約されている。
【００１１】
本発明の一態様では、回路を設計する方法は、回路の設計のその後の配線実装時に設計制約条件に違反する可能性があるかどうかを判別することと、設計のその後の配線実装時に設計制約条件の違反の可能性を低減するように回路の設計を修正することを含む。一例では、設計のその後の配線実装時に設計制約条件に違反する可能性は、経路トポロジを推定する際の不確定性によるものである。一実施態様の一例では、設計のその後の配線実装時に設計制約条件に違反する可能性があるかどうかは、１）駆動素子の負荷素子を囲む境界ボックスと、２）ネットが駆動素子を負荷素子に接続する、タイミング・クリティカルまたはクリティカルに近いパス上のネットのファンアウトの個数に基づいて決定される。一実施態様の一例では、設計の修正は、第２の駆動素子を挿入するように第１の駆動素子を複製することと、第２の駆動素子の負荷素子として第１の駆動素子の負荷素子の一部を再接続することを含む。実施態様の別の例では、設計の修正は、第１の駆動素子の負荷素子としてバッファ素子を挿入することと、バッファ素子の負荷素子として第１の駆動素子の負荷素子の一部を再接続することを含む。一実施態様のさらに別の例では、設計の修正は、駆動素子の負荷素子の配置を再配列して駆動素子と負荷素子の境界ボックスの短い辺と長い辺との比を低減することを含む。一実施態様の一例では、設計の修正は、第２の素子の負荷素子として第１の素子の負荷素子の一部を変換することを含む。一例では、設計制約条件は、タイミング制約条件である（例えば、回路の最悪ネガティブ・スラック、回路の設計における論理素子のインスタンスのスラック、回路の設計におけるパス上の遅延、回路のトータル・ネガティブ・スラックなど）。一実施態様の一例では、代替経路トポロジが使用される場合にそれぞれが設計制約条件の違反を引き起こす可能性のある多数のネット候補が決定され、設計は、その多数のネット候補の部分集合について選択的に修正される。一実施態様の一例では、この部分集合は、それぞれのネット候補を通る多数のパスを表す流れに応じてその多数のネット候補から選択される。実施態様の別の例では、修正する部分集合を決定するために多数のネット候補を含むグラフに対し最小カットが実行される。
【００１２】
本発明の一態様では、回路を設計するための機械実装方法は、回路の設計に応じて駆動素子とその駆動子の負荷素子との間の第１の距離を推定することと、第１の距離を使用してタイミング制約条件が満たされているかどうかを検証することと、回路の設計に応じて駆動素子と負荷素子との間の、第１の距離よりも長い第２の距離を推定することと、第２の距離を使用してタイミング制約条件が満たされているかどうかを判定することとを含む。一実施態様の一例では、第１の距離は第１の経路トポロジに従い、第２の距離は第２の経路トポロジに従う。異なる経路トポロジは、配線全長の最小化、タイミング制約条件の適合、またはこれら２つの組み合わせなどのさまざまな配線目標の結果とすることができる。一実施態様の一例では、設計コスト関数を悪化させずに第２の距離を短縮するために回路の設計に対し変換を実行できるかどうかを判定することは、第２の距離が使用される場合にタイミング制約条件が満たされないとの判定に対する応答として決定される。例えば、変換は、駆動素子を複製すること、駆動素子をサイズアップすること、駆動素子と負荷素子との間にバッファ素子を挿入することとおよび／または駆動素子とその駆動素子の負荷素子のうちの少なくとも１つの素子の配置を調整することとすることができる。一実施態様の一例では、第２の距離は、経路トポロジの感度を低減するために駆動素子と負荷素子を接続するネットが選択された場合のみ推定され、ネットは、ネットがタイミング・クリティカルまたはクリティカルに近いパス上にあり、ネットのファンアウトの数が２よりも大きい場合にのみ選択される。一実施態様の一例では、ネットは、さらに、駆動素子の負荷素子を囲む境界ボックスの縦横比に応じて選択される。
【００１３】
便宜上、境界ボックスの縦横比は、縦横比が決して１を超えないような短い辺と長い辺との比と考えられる。
【００１４】
本発明の一態様では、回路を設計するための機械実装方法は、駆動素子とその駆動素子の複数の負荷素子の領域の形状を決定することと、その領域の形状に少なくとも基づき駆動素子と複数の負荷素子のうちの第１の素子との間の距離を推定することを含む。一実施態様の一例では、領域の形状は、異なる経路目標（配線全長の最小化、タイミング制約条件の適合、およびその両方の何らかの組み合わせなど）を使用するさまざまな配線アルゴリズムがどのように異なるかを推定するために使用される。一実施態様の一例では、領域の形状を決定することは、複数の負荷素子を囲む境界ボックスを決定することを含む。ただし、距離は、少なくとも境界ボックスに基づいて推定される。一実施態様の一例では、距離は、駆動素子と複数の負荷素子のうちの第１の素子との間の最小配線距離（例えば、マンハッタン距離）と境界ボックスの短い辺の距離の関数として推定される。一実施態様の一例では、この距離は、さらに、駆動素子のスラックに応じて推定される。一例では、境界ボックスは矩形である。
【００１５】
本発明の一態様では、回路を設計する方法は、第１の回路設計（例えば、配置ソリューションがある場合またはない場合の技術特有のネットリスト）の実装で設計制約条件（例えば、タイミング制約条件、最大静電容量、最大遷移、最大クロストーク）に違反する可能性を判定することと、設計制約条件に違反する可能性を低減するように第１の回路設計を修正することを含む。一例では、第１の回路設計の実装は、第１の回路設計を実装するための配線ソリューションを含み、第１の回路は、論理素子のインスタンスのサイズ設定、信号のバッファリング、信号の負荷遮蔽、論理素子の最も弱いドライバのサイズ設定、またはその他の操作を通じて修正される。一例では、設計制約条件は、タイミング制約条件を含む（例えば、回路の最悪ネガティブ・スラック、第１の回路設計における論理素子のインスタンスのスラック、第１の回路設計におけるパス上の遅延、回路のトータル・ネガティブ・スラックなど）。回路のトータル・ネガティブ・スラックは、回路のすべての端点におけるすべてのネガティブ・スラックの総和である。回路の端点は、パスの終端となる回路内の一点である。一例では、第１の回路設計を修正することは、第１の回路設計の実装における不確定性による論理素子のパラメータに対する設計制約条件の感度に応じて修正の論理素子のインスタンスを選択することを含む。別の例では、第１の回路設計を修正することは、第１の回路設計の実装における不確定性によるパス上の論理素子の少なくとも１つのパラメータに対する設計制約条件の感度に応じて修正のパスを選択することを含む。一例では、設計制約条件に違反する可能性は、第１の回路設計における論理素子のインスタンスに接続するネットの推定されるパラメータ（例えば、ネット長、ネット静電容量）の発生しうる変化から決定される。一例では、多数の候補が第１の回路設計の実装における不確定性に対する感度に基づいて第１の回路設計の論理素子のインスタンスから決定された後、その数の候補の部分集合が選択的に修正される（例えば、候補を通る多数のパスを表す流れに応じてその多数の候補のうちから１つの候補を選択し、選択された候補をサイズアップする、または候補のグラフに対し最小カットを実行する、そのカットの上の候補をサイズアップする）。一例では、サイズアップは、全体的設計制約条件を下げない範囲でのみ実行される（例えば、最悪のネガティブ・スラック）。
【００１６】
本発明は、これらの方法を実行するデータ処理システムを含むこれらの方法を実行する方法と装置、およびデータ処理システム上で実行した場合にこれらの方法をシステムに実行させるコンピュータ可読媒体を含む。
【００１７】
本発明の他の特徴は、付属の図面と以下で述べる詳細な説明とから明らかになる。
【００１８】
本発明は、付属の図面の図において限定されることなく例を使用して説明され、類似の参照番号は類似の要素を示す。
【発明を実施するための最良の形態】
【００１９】
以下の説明および図面は、本発明を例示するものであり、本発明を制限するものと解釈すべきではない。本発明を完全に理解できるようにするため、多数の具体的詳細を説明する。しかし、いくつかの場合には、本発明の説明をわかりにくくすることを避けるため、よく知られているまたは従来の内容については詳述しない。本開示の一実施形態を参照していても、同じ実施形態を参照する必要があるわけではなく、そのような参照は少なくとも１つを意味する。
【００２０】
本発明の少なくとも１つの実施形態は、回路設計の実装において設計制約条件に違反する可能性が低減されるように（例えば、配置と配線の後に）回路設計（例えば、技術特有の設計の合成ソリューション）を最適化しようとする。一実施形態では、タイミング目標の違反に関わる確率を低くするための変換についてインスタンスの最小の集合が選択される。
【００２１】
本発明の方法の多くは、従来の汎用コンピュータ・システムなどのデジタル処理システムにより実行することができる。１つの機能のみを実行するように設計またはプログラムされた専用コンピュータも使用することができる。
【００２２】
図１は、本発明とともに使用できる代表的なコンピュータ・システムの一例の図である。図１はコンピュータ・システムのさまざまなコンポーネントを例示しているが、そのような詳細は本発明と密接に関連していないためコンポーネントを相互接続する特定のアーキテクチャまたは方法を表すことは意図されていないことに注意されたい。また、より少ないコンポーネントまたはおそらくより多いコンポーネントを有するネットワーク・コンピュータやその他のデータ処理システムも、本発明とともに使用できることは理解されるであろう。図１のコンピュータ・システムは、例えば、Ｓｕｎワークステーション、またはＷｉｎｄｏｗｓ（登録商標）オペレーティング・システムが稼働しているパーソナル・コンピュータ、またはＡｐｐｌｅ Ｍａｃｉｎｔｏｓｈコンピュータとすることができる。
【００２３】
図１に示されているように、コンピュータ・システム１０１は、データ処理システムの一形態であり、マイクロプロセッサ１０３に結合されているバス１０２を含み、さらにＲＯＭ １０７、ＲＡＭ １０５、不揮発性メモリ１０６を備える。マイクロプロセッサ１０３は、図１の例に示されているように、キャッシュ・メモリ１０４に結合される。バス１０２は、これらのさまざまなコンポーネントを相互接続してつなぎ合わせ、またこれらのコンポーネント１０３、１０７、１０５、１０６をディスプレイ・コントローラやディスプレイ・デバイス１０８に相互接続し、またマウス、キーボード、モデム、ネットワーク・インターフェイス、プリンタ、スキャナ、ビデオカメラ、その他の当業でよく知られているデバイスとすることができる入出力（Ｉ／Ｏ）デバイスなどの周辺デバイスに相互接続する。通常、入出力デバイス１１０は、入出力コントローラ１０９を通じてシステムに結合される。揮発性ＲＡＭ １０５は、通常、メモリ内のデータをリフレッシュまたは保持するために絶えず電力を必要とするダイナミックＲＡＭ（ＤＲＡＭ）として実装される。不揮発性メモリ１０６は、通常、磁気ハード・ドライブまたは磁気光ドライブまたは光ドライブまたはＤＶＤ ＲＡＭまたはシステムの電源を切った後もデータを保持する他の種類のメモリ・システムである。通常、不揮発性メモリは、ランダム・アクセス・メモリであるが、そうである必要はない。図１は、不揮発性メモリがデータ処理システム内の残りのコンポーネントに直接結合されているローカル・デバイスであることを示しているが、本発明では、モデムまたはＥｔｈｅｒｎｅｔ（登録商標）インターフェイスなどのネットワーク・インターフェイスを通じてデータ処理システムに結合されているネットワーク記憶デバイスなどのシステムから離れた場所にある不揮発性メモリを使用することができることは理解されるであろう。バス１０２は、当業でよく知られているように、さまざまなブリッジ、コントローラ、および／またはアダプタを通じて互いに接続されている１つまたは複数のバスを備えることができる。一実施形態では、Ｉ／Ｏコントローラ１０９は、ＵＳＢ周辺機器を制御するためのＵＳＢ（Ｕｎｉｖｅｒｓａｌ Ｓｅｒｉａｌ Ｂｕｓ）アダプタ、および／またはＩＥＥＥ−１３９４周辺機器を制御するためのＩＥＥＥ−１３９４バス・アダプタを備える。
【００２４】
この説明から、本発明の複数の態様は、少なくとも一部は、ソフトウェアで実現できることは明白であろう。つまり、これらの手法は、ＲＯＭ １０７、揮発性ＲＡＭ １０５、不揮発性メモリ１０６、キャッシュ１０４、またはリモート記憶デバイスなどのメモリに格納されている命令シーケンスを実行するマイクロプロセッサなどのプロセッサに対する応答として、コンピュータ・システムまたはその他のデータ処理システム内で実行することができる。さまざまな実施形態において、本発明を実装するために、配線接続されている回路をソフトウェア命令と組み合わせて使用することができる。したがって、これらの手法は、ハードウェア回路とソフトウェアの特定の組み合わせに限定されず、またデータ処理システムにより実行される命令の特定のソースにも限定されない。さらに、この説明全体を通して、説明を簡単にするため、さまざまな機能や操作はソフトウェア・コードにより実行されるか、またはソフトウェア・コードにより引き起こされるものとして説明されている。しかし、当業者であれば、そのような表現が意味しているのは、それらの機能がマイクロプロセッサ１０３などのプロセッサによるコードの実行から結果として生じるということであると理解するであろう。
【００２５】
機械可読媒体が、データ処理システムにより実行されたときに本発明のさまざまな方法をシステムに実行させるソフトウェアとデータを格納するために用いられる。この実行可能ソフトウェアとデータは、図１に示されているように、例えば、ＲＯＭ １０７、揮発性ＲＡＭ １０５、不揮発性メモリ１０６、および／またはキャッシュ１０４をはじめとするさまざまな場所に格納することができる。このソフトウェアおよび／またはデータの一部分を、これらの記憶デバイスのうちのいずれか１つに格納することができる。
【００２６】
したがって、機械可読媒体は、機械によりアクセス可能な形態で情報を提供（つまり、格納および／または伝送）するメカニズムを備える（例えば、コンピュータ、ネットワークデバイス、パーソナルデジタルアシスタント、製造装置、１つまたは複数のプロセッサの集まりを含むデバイスなど）。例えば、機械可読媒体は、記録可能／記録不可能媒体（例えば、読み取り専用メモリ（ＲＯＭ）、ランダム・アクセス・メモリ（ＲＡＭ）、磁気ディスク記憶媒体、光記憶媒体、フラッシュ・メモリ・デバイス、などだけでなく、電気、光、音響、またはその他の形態の伝搬信号（例えば、搬送波、赤外線信号、デジタル信号など）などをも含む。
【００２７】
標準的な回路設計プロセスでは、論理合成ツールで、与えられた機能の集合を実行する論理素子回路網を作成する。論理合成ツールでは、遅延、領域、その他の設計目標を最適化するため論理回路を変形し再構成することができる。ゲート・レベル論理素子は、ベンダ固有のプリミティブにマッピングされ、技術特有のネットリストを生成する。その後、マッピングされた技術特有のネットリストは、チップ上のさまざまなブロックに割り当てられる。次に、配置と配線ツールでは、マッピングされたネットリストのベンダ特有のプリミティブをチップ上に配置し、それらのプリミティブの間に配線を行う。配置と配線の後、インプレース最適化は、通常、さらにタイミングを最適化するために実行される。インプレース最適化は、論理素子の配置を著しく変更することなく論理素子に対する制約付き変更を行う。配置と配線情報が利用できるようになった後、詳細なタイミング解析を実行して、タイミング制約条件がすべて満たされているかどうかを正確に判別することができる。タイミング要件すべてが満たされているわけではないと判断された場合、論理合成により生成された設計は、タイミング要件を満たすように変更される。
【００２８】
そのため、回路設計のための合成ツールの遅延予測の正確さは、よい品質の結果の生成のためには重要である。通常、バックエンド・ソフトウェア・プログラムは、合成ツールの設計結果を回路の詳細実装に使用する。例えば、配置と配線ツールは、合成ツールの設計結果を設計レイアウトに使用する。合成推定遅延に基づいて合成ツールにより予測されるクリティカル・パスの遅延は、設計の後段階（例えば、配線、レイアウトなど）から抽出された詳細データ（例えば、寄生データ、詳細配線情報）に基づいて計算されたタイミング目標との密接な忠実関係になければならない。合成ツールは、ハンドオフに先立ってこのバックエンド遅延を正確に予測する場合、合成ツールとバックエンド・ソフトウェア・プログラムを伴う費用のかかる反復を実行する必要性が避けられる。
【００２９】
しかし、合成ツールは、常にこのバックエンド遅延を正確に予測できるわけではない。ほとんどのタイミング目標は、長い配線によって引き起こされるセル遅延とネット遅延が関わる。長い配線遅延は、通常、長い配線をバッファリングし、それから、さらに小さな配線に効果的に分割することにより、合成において標準的な形で取り扱われる。そのため、セルの遅延を正確に予測することで、タイミング目標のよい予測を出すことができる。セルの遅延は、通常、セルの静電容量性負荷の関数である。静電容量性負荷の主要コンポーネントは、セルのドライバに接続されたネットの静電容量と負荷ピンの容量性負荷を含む。負荷ピンの静電容量は、設計の論理接続属性に基づいて推論できる。しかし、ネットの静電容量は、設計レイアウトが完了したときにしか正確に得ることができない。そのため、合成ツールは、最終的に設計レイアウトを作成するバックエンド・ソフトウェアのビヘイビアを予測する負担を有する。
【００３０】
正確な遅延を予測するのではなく、回路の一部分（例えば、ゲート、またはパス）がタイミング目標の違反に関わる確率を評価できるように、遅延の確率分布を決定することができる。本発明の少なくとも一実施形態では、バックエンド・ソフトウェア・プログラムを伴う反復の必要性を軽減するためにタイミング制約条件に違反する確率の高い回路の部分に対し変換を実行しようとする。
【００３１】
例えば、その後の実装に発生しうる逸脱（例えば、合成ツール内に埋め込まれたタイミング・エンジンにより推定されるものから逸脱する）によるタイミング制約条件に関するタイミング・パラメータの感度は、その後の実装における違反の確率を示す指標となる。本発明のいくつかの実施形態による合成ツールは、変換を実行して、タイミング目標の変化が、設計のレイアウトの実行後に、タイミング制約条件に関して、重要な意味を持たないようにする。本発明のいくつかの実施形態では、遅延推定からの可能な逸脱は、クリティカル・パスにそって小さく、かつクリティカルに近いパスにそって小さいことが望ましい。そのため、本発明の実施形態による合成ツールでは、回路の可能なレイアウト後クリティカル部分やクリティカルに近い部分を識別し、それらの部分に対して変換を実行し、クリティカル・パスとクリティカルに近いパス上の遅延の変動を低減し、それによって、設計レイアウトが実装された場合にタイミング制約条件違反が生じる可能性を低減する。
【００３２】
タイミング目標と合成ツールの推定におけるその不確定性は、主に、ネット・ファンアウト、インスタンスの駆動長、配線負荷などのその他の推定因子、また物理的合成では、経路長、輻輳効果、配線の単位長さ当たりの抵抗と容量などの技術情報に依存する。輻輳は、結合容量と配線長（例えば、迂回路を引き起こす）の両方に影響を及ぼす。
【００３３】
例えば、長いネットを駆動する低い駆動強度のセルがある場合、ネットの長さの小さな変動であっても、駆動セルの遅延に大きな影響を及ぼす可能性がある。すべての低い駆動強度セルを完全に排除し、高い駆動強度セルのみを使用することができるが、このようなアプローチでは、領域と負荷のペナルティが増大し、ひいては、すべてのタイミング目標に悪影響を及ぼす。そのため、本発明の少なくとも一つの実施形態では、駆動強度を改善する必要があるセルを選択的に選ぶ。
【００３４】
本発明の少なくとも一実施形態では、回路設計のネットリスト内のセルの部分集合に対し設計変更を選択的に実行する。変換のインスタンスの縮小された集合（例えば、最長集合）を識別するためのさまざまなアルゴリズムについて、以下で説明する。
【００３５】
本発明の少なくとも一実施形態では、推定された物理データに基づいてタイミング制約条件違反の確率を推定する。例えば、感度値に基づく違反の確率を使用して、インスタンスの改善を優先順位付けし、物理設計後に違反の確率が高いものが違反の確率が低いものに先立って改善されるようにする。それによって、候補リストは、違反の確率に基づき最小にすることができる。改善後の面積利用度がネガティブ・スラックを持つすべてのインスタンスの改善よりも小さくなるように、通常、候補リストの小さな集合を改善のために選択することができる。
【００３６】
本発明の一実施形態では、設計変更のために回路の一部分が選択され、部分（例えば、論理素子のインスタンス、または回路内のパス）がタイミング目標の違反に関わりうる確率に基づき、設計の後の方の段階でタイミング制約条件に違反する確率を低減するようにする。例えば、選択は、タイミング目標の違反に関与するそれぞれのゲートの確率（例えば、ゲートによる不確定性への感度）に基づいて実行できるか、または選択は、タイミング目標の違反に関与するそれぞれのパスの確率に基づいて実行できる。
【００３７】
本発明の一実施形態では、タイミング目標の違反に関わるかどうかを判別するために、インスタンスを一度に１つずつ調べる。例えば、駆動強度を改善するためにインスタンスの部分集合を選択することができ、サイズアップが設計の最悪のネガティブ・スラックの低下を引き起こさない、またサイズアップがさらに、あらかじめ決められている上限の範囲内で設計の面積利用度を保持するもののみを含めることによりインスタンスの部分集合のサイズを最小にする。
【００３８】
本発明の一実施形態では、設計の最悪のネガティブ・スラックに応じて、インスタンスの部分集合が選択される。例えば、回路の一部分が、スラックがしきい値よりも悪い（例えば、しきい値と最悪のネガティブ・スラックの間にある）インスタンスに対する設計変更に対して選択される。負荷の変化に対するこれらのインスタンスの感度を判別することができるが、これについては、以下で詳述する。負荷の増大によりインスタンスのスラックが最悪のネガティブ・スラックを超える場合、サイズ改善のため候補のリスト上でインスタンスが選択される。
【００３９】
本発明の他の実施形態では、スラックがネガティブであるインスタンスの部分集合が選択される。この部分集合内のすべてのインスタンスの感度が計算され、それらのインスタンスが、減少する感度値に基づいて設計変更に対して優先順位付けされる。このシナリオでは、設計のトータル・ネガティブ・スラックは低下しないことが保証される。
【００４０】
負荷の変化は、インスタンスの配置情報が利用可能でない場合に配線負荷モデルの摂動に基づいて推定することができる。物理的合成の場合、インスタンス上の負荷のこの変化は、さらに正確な物理的情報に基づいて判定することができる。
【００４１】
例えば、物理的合成時に詳細な配置が実行される場合、設計の中のすべてのインスタンスの正当な場所が利用可能である。ネットで推定する最も可能性の高い経路を決定するために、高速大域配線経路推定を実行できる。これらの推定された経路から、経路の予測される輻輳マップが決定される。
【００４２】
輻輳により、配線の結合容量が変動する。ひどく輻輳している領域内を引き回されるネットが輻輳領域の周りを迂回される可能性は、経路資源がその領域内で引き回される必要のあるネットの要求量よりも小さい場合に、最も高い。これらのタイプのネットは、ネット長の増大が生じる可能性が最も高い。
【００４３】
詳細配線の後のネットのレイヤ割り当てでも、配線の抵抗と静電容量の予測不可能な変化が生じる可能性がある。輻輳領域内のインスタンスの感度を下げると、詳細配線の後のタイミング要件の違反を引き起こす可能性のある予測不可能な変化の効果を低減することができる。
【００４４】
ネットが引き回される領域の過剰な輻輳に加えて、近隣領域内にも過剰な輻輳が存在する場合、迂回路の量が増える可能性がある。迂回路の量は、通常、輻輳している領域の形状とサイズに依存する。迂回路の量は、さらに、他のパラメータ（例えば、タイミング・パラメータ）にも依存する場合がある。したがって、これらのタイプのネットに対し発生する可能性のある長さの変化も、それに応じて推定できる。
【００４５】
一実施形態では、配線長の増大は、ネットのセグメントの経路輻輳だけでなく近隣領域経路輻輳にも依存する関数を使用して推定することができる。典型的な大域的配線経路推定では、ネットの実際の長さに対する下限が得られる。そのため、一実施形態では、下限の長さを超えるネット長の（経時的）摂動の量を表す実験的（または統計的）結果に基づく因子が加えられる。
【００４６】
ネット長の摂動により、インスタンスのスラックが最悪のネガティブ・スラックを超える場合、ネットの駆動素子は、摂動の効果がスラックの著しい変化に寄与しなくなる（例えば、スラックがしきい値よりも悪くなる）までサイズアップする必要がある。
【００４７】
本発明の一実施形態では、非最適経路（ｅｌ、経路の推定長）であることによるネット長の増大、ネットのファンアウト（ｆ）、ネット・セグメントの輻輳係数（ｃｇ）、ネット・セグメントの近隣の輻輳係数（ｎｃｇ）、輻輳しきい値（ｃｔ）、標準セル行の高さ（ｒｔ）に応じて、発生しうるネット静電容量（ｎｃｃ）の変化が推定される。例えば、発生しうるネット静電容量（ｎｃｃ）の変化は、以下のように推定できる。
【００４８】
ｎｃｃ＝ｋ0×ｅｌ×ｆ＋ｋ1×ｒｔ ｃｇ≦ｃｔの場合
【００４９】
ｎｃｃ＝ｋ2×ｃｇ＋ｋ3×ｎｃｇ ｃｇ＞ｃｔの場合
【００５０】
ただし、ｋ0、ｋ1、ｋ2、ｋ3は、統計データに基づいて導かれるパラメータである。例えば、バックエンド・ソフトウェア・ツールを使用して多数の合成ソリューションの配置と配線が行われた後、合成ソリューションに基づいて推定されたものと設計レイアウトの後に決定されたものとの間のネット静電容量の実際の変化を決定することができる。これらのソリューションに対する実際の変化と輻輳係数との相関を計算して、パラメータｋ0、ｋ1、ｋ2、ｋ3を決定することができる。前の設計ソリューションに対する設計レイアウトの後の実際の変化に基づいて（例えば、異なる回路の集合、所定の回路に対する前の多数の反復、その他に基づいて）パラメータｋ0、ｋ1、ｋ2、ｋ3を導くために、曲線当てはめ手法を使用できる。曲線当てはめ手法は、さらに、ネット静電容量の発生しうる変化の推定に対する公式の形を決定するためにも使用することができる。そのため、上で例示されているものと異なる式（または方程式）も使用できるが、異なる数の統計学に基づくパラメータを必要とする場合がある。
【００５１】
ネット長の変化も、同様にして決定できることに注意されたい。輻輳係数が推定できない場合（例えば、回路の素子のインスタンスに関する位置情報が利用できない場合）、輻輳係数を輻輳しきい値よりも小さい値に設定し、ネット静電容量（またはネット長）の推定された変化が輻輳係数に基づかないようにすることができる。
【００５２】
タイミング目標パラメータ（例えば、遅延、スラックなど）は、通常、ネット静電容量の関数である。そのため、ネット静電容量の変化は、タイミング目標パラメータの変化を判別するために使用することができる。
【００５３】
感度係数は、ｉ）発生しうる変化を考慮しないタイミング目標パラメータ（ｔobj）と、ii）発生しうる変化のあるタイミング目標パラメータ（ｔobjn）から決定することができる。さらに、タイミング目標パラメータ（ｔobjt）は、感度係数の決定の際に使用することができる。例えば、しきい値は、タイミング制約条件に違反する結果を超える、タイミング目標パラメータに対する限界値とすることができる。例えば、感度係数（ｓｆ）は以下のように評価することができる。
【００５４】
ｓｆ＝（ｔobjn−ｔobj）／ｔobjt
【００５５】
そのため、感度係数は、発生しうる実装の変化による基準値（例えば、しきい値）に関してタイミング目標パラメータの変化が増大すると増大する。
【００５６】
さまざまな代替感度係数定義を使用して、感度を定量化し、その後の実装における制約条件違反の確率を示すことができることが理解される。例えば、定式化は、以下のように、しきい値に近いタイミング目標を持つインスタンスについてより高い感度を示すために使用することができる。
【００５７】
【数１】
【００５８】
一実施形態では、感度係数を使用して、修正（または設計変更）対象の回路設計の部分を選択する。例えば、インスタンス・ベースのアプローチでは、個々のインスタンス要素によるタイミング・パラメータに対する感度を評価し、修正対象の敏感な素子を判別し、パス・ベースのアプローチでは、個々のパスに対するインスタンス要素によるタイミング・パラメータの感度を評価して、修正対象の敏感なパス（およびパス上の敏感な素子）を決定する。さらに、敏感な素子の部分集合を修正対象の敏感なパスから選択することができる。
【００５９】
それとは別に、インスタンスのパス感度は、設計内のタイミング終点から開始するすべてのパスの順方向と逆方向の幅優先探索(breadth first)を実行することから決定することができる。タイミング終点の集合は、ラッチ、レジスタ、フリップ・フロップ、Ｉ／Ｏポートを含む。例えば、パス感度ｓpathを決定することは、以下を含む。
【００６０】
ａ）設計内のすべてのインスタンスでインスタンス感度（ｓinstance）を計算する。
【００６１】
ｂ）逆方向幅優先探索を実行して、以下のように駆動インスタンスＪn（ｎ＝０，１，．．．，Ｎ）を持つインスタンスＩでの逆方向パス感度（ｓbackward）を計算する。
【００６２】
ｓbackward（Ｉ）＝ｓinstance（Ｉ）＋Ｍａｘ（ｓbackward（Ｊ0），ｓbackward（Ｊ1），．．．，ｓbackward（ＪN））、
【００６３】
ｃ）同様に、順方向幅優先探索を実行して、以下のように負荷インスタンスＪm（ｍ＝０，１，．．．，Ｍ）を持つインスタンスＩでの順方向パス感度（ｓforward）を計算する。
【００６４】
ｓforward（Ｉ）＝ｓinstance（Ｉ）＋Ｍａｘ（ｓforward（Ｊ0），ｓforward（Ｊ1），．．．，ｓforward（ＪM））、
【００６５】
ｄ）以下からインスタンスＩのパス感度を決定する。
【００６６】
ｓpath（Ｉ）＝Ｍａｘ（ｓforward（Ｉ），ｓbackward（ｌ））
【００６７】
駆動インスタンスは、負荷インスタンスへの直接入力として出力を生成し、負荷インスタンスは、駆動インスタンスから直接入力を受け取ることに注意されたい。
【００６８】
インスタンスまたはパスについて感度を定義する方法は多数あることは理解されるであろう。例えば、完全に確率論的なアプローチを使用することにより、タイミング・パラメータの変化の確率と平均期待値を決定することができ、これから、感度指標が決定されるが、確率および平均期待値の評価は多量の計算を必要とする場合がある。それとは別に、感度指標は、輻輳領域を回避するために発生する再配線によるネット長の変化などのさまざまな要因により識別された決定論的変化に基づいて評価することができる。さらに、輻輳係数などの統計学に基づくパラメータや決定論的に決定されたパラメータを組み合わせて、感度係数に対する実験式を定式化することができる。例えば、合成時に、ネット長は、ネットのファンアウトとブロック・サイズに従って配線負荷テーブルから求めることができる。ルックアップ値に基づく変化の特定の割合がネット長の可能な変化であると仮定することができる。それとは別に、配線負荷テーブルでネット長の変化の平均値を生成し、可能な変化を、ファンアウトとブロック・サイズに従ってルックアップするようにもできる。
【００６９】
パスに基づくアプローチでは、パス遅延がタイミング目標の違反を引き起こす可能性がある確率が評価される。例えば、多数の低駆動セルを持つパスに対するタイミング目標は、低駆動セルが少ししかないパスに比べて違反される可能性が高い。タイミング目標の違反の確率を正確に評価することは困難であるが、発見的アプローチを使用すると、タイミング目標の違反の確率を示す指標を決定することができる。例えば、パスに対するすべてのネット・セグメントの決定論的変化を識別し、パスの新しいタイミング目標の評価に組み込み、パス内の感度を決定することができる。その場合、バックエンド・ツール内のパスに対し適用されるすべての変化の最悪の場合のシナリオが仮定される。
【００７０】
タイミング目標の違反の確率を低減することを目的として（また、変換を適用する順序を決定するため）変換される必要のあるインスタンスの最小集合を選択するために、異なる選択方式を使用することができる。例えば、複数の候補を、感度に基づいて選択することができる。例えば、インスタンスのタイミング目標（例えば、遅延、またはゲートのスラック）がネットのネット長（またはネット静電容量）の変化に敏感な場合、ネットの駆動素子はサイズアップの候補として選択される。それとは別に、ネットの駆動素子を複製することができ、これにより駆動素子は効果的にサイズアップされる。駆動素子が複製された後、元の駆動素子の負荷素子は、元の駆動素子と新しい駆動素子の負荷素子として分割することができる。それとは別に、元の駆動素子と新しい駆動素子は、負荷素子をまとめて駆動することができる。同様に、パスのタイミング目標（例えば、パスにそっての遅延）がパス上の１つまたは複数のネットのネット長（またはネット静電容量）の変化に敏感な場合、パスは変換の候補として選択される。さらに、候補は、設計目標に対する影響に応じて選択することができる。例えば、クリティカル・パスまたはクリティカルに近いパス上の敏感な素子を選択することができる。さらに、回路内の影響の相対的重要度または範囲に基づいて、敏感な素子を選択することができる。例えば、多くのパス上にある敏感な素子は、少ないパス上にある類似の素子よりも優先度が高い。
【００７１】
例えば、１パスの物理的合成が実行された後、インスタンスの正当な位置を決定することができる。その後、敏感なインスタンスの候補集合を、感度基準に基づいて選択することができる。候補は、流れに基づいてソートされ、多数の異なるパスはそれらの候補のそれぞれを流れる。流れの大きな候補は、流れの小さな候補が処理される前に処理される。１つの素子のサイズアップは、他の関連するタイミング・パラメータに悪影響を及ぼす可能性があるため（例えば、上流素子のスラック）、サイズアップ・オペレーションは、これらの関連するタイミング・パラメータを許容不可能なレベルにまで低下させない範囲に限り実行される。したがって、例えば、候補のサイズアップが設計目標を悪化させないと判断された場合（例えば、最悪のネガティブ・スラック）、候補はサイズアップされ（例えば、所定の量だけ）、そうでなければ、候補は設計目標が低下しない限りサイズアップされ、バッファリング（オプション）される。感度を十分に引き下げるために候補のサイズアップおよびバッファリングを実行できない場合（例えば、他の設計制約条件のため）、候補の最も弱い駆動がサイズアップされ、本発明の一実施形態のさらに大きなインスタンスを駆動できる。
【００７２】
バックエンドにハンドオフされるネットリスト内に敏感なインスタンスが存在しない場合、実際の経路トポロジ内にある程度の変動があっても、設計内のクリティカル・パスの変化（例えば、合成段階の推定からの逸脱）によりタイミング制約条件には違反しない（または違反される可能性がきわめて小さい）。
【００７３】
本発明の他の実施形態では、敏感なインスタンスを通るパスを表すグラフが構築され、サイズアップするインスタンスを選択するためにグラフの最小カットを実行できる。最小カット・オペレーションにより、グラフを２つの非連結部分に分離するグラフ内の最小要素の集合を見つける。最小カット・オペレーションを実行する知られているアルゴリズムを使用することができる。最小カットの上の敏感な素子の集合は、回路の２つの部分の間の通信に影響を及ぼす最小の敏感な素子の部分集合を表す。そのため、最小カットの上のそのような敏感な素子の集合のサイズアップは、回路設計における感度を低減する費用効果のある手段である。そのカット内のインスタンスをサイズアップした後（例えば、所定の量について、または最悪のネガティブ・スラックを悪化させない範囲で）、さらに最小カット・オペレーションを実行することができる。最小カット・ベースの選択は、繰り返し、または他の選択方式と組み合わせて実行することができる。一例では、このグラフは、信号パスを通るパス上の敏感なインスタンスの位置決めを表し、敏感でないインスタンスは、このグラフ上には表されない。
【００７４】
この説明から、当業者であれば、さまざまな異なる選択と順序付け方式（例えば、異なる組み合わせや変更形態とともに、この説明の例で例示されているように）を使用して、サイズアップする必要のあるインスタンスの個数を効果的に減らし、インスタンスのサイズアップの費用有効性を高めることができる。
【００７５】
図２は、本発明の一実施形態により回路を設計する方法を示す図である。オペレーション２０１で第１の回路設計（例えば、技術特有のネットリスト、技術マッピング・ネットリスト、または回路図）を受け取った後、オペレーション２０３で、第１の回路設計を実装するために生成される第２の回路設計内で複数の設計制約条件（例えば、タイミング）に違反する可能性を判別する。例えば、合成ソリューションについて詳細設計レイアウトの後（例えば、配置と配線後）にタイミング制約条件に違反する可能性を決定することができる。オペレーション２０５では、第１の回路設計（例えば、素子のサイズ設定、信号のバッファリング、負荷の遮蔽など）を修正して、第１の回路設計の実装において複数の設計制約条件に違反する可能性を低減する。
【００７６】
図３は、本発明の一実施形態により回路を最適化する方法を示す図である。オペレーション２２１で第１の回路設計（例えば、ネットリスト、技術特有のネットリスト、配置ソリューション、配置と配線前の設計ソリューション）を受け取った後、オペレーション２２３で、第１の回路設計に対する１つの設計制約条件パラメータ（例えば、ネット上またはパス上の遅延、最悪ネガティブ・スラック、最速のシステム・クロック）を推定する。オペレーション２２５では、第１の回路設計内の不確定性による設計制約条件パラメータの感度を判別する。例えば、合成ツールにより推定される経路と異なる配線ソフトウェア・ツールで決定された経路によるタイミング・パラメータの変化である（例えば、輻輳領域を回避する迂回路、または推定からの逸脱によるもの）。オペレーション２２７では、第１の回路設計内の不確定性による設計制約条件パラメータの少なくとも感度に基づいて第１の回路設計を最適化する。この最適化は、さらに、修正、関連設計パラメータの許容される低下レベル、感度がクリティカルであるかどうかなどの費用有効性に基づくこともできる。
【００７７】
図４は、本発明の一実施形態により回路を最適化する詳細な方法を示す図である。オペレーション２４１で第１の回路設計（例えば、ネットリスト、技術特有のネットリスト、配置ソリューション、配置と配線前の設計ソリューション）を受け取った後、オペレーション２４３で、複数の設計制約条件パラメータ（例えば、ネットまたはパスによる遅延）を推定する。オペレーション２４５では、第１の回路設計を実装する際の不確定性を判別する（例えば、第１の回路設計の実装においてネット長および／またはネット静電容量に発生しうる変化）。オペレーション２４７で、第１の回路設計を実装する際の不確定性による設計制約条件パラメータの不確定性を表す指標（例えば、感度係数）を決定する。オペレーション２４９で、少なくともそれらの指標に基づいて第１の回路設計の一部分を選択的に修正する。
【００７８】
図５〜６は、本発明のいくつかの実施形態により回路を選択的に修正する詳細な方法を示す図である。
【００７９】
図５のオペレーション３０１で、設計ソリューション（例えば、技術特有のネットリスト）を生成するため第１の回路の物理的合成を実行する。オペレーション３０３では、状況に応じて、インスタンス（例えば、論理素子）の位置を決定する。オペレーション３０５で、第１の回路設計を実装する際の不確定性による１つまたは複数の設計制約条件パラメータの不確定性を表す指標を決定する。オペレーション３０７で、修正する少なくともいくつかの指標に基づいて第１の回路の複数の部分（例えば、インスタンスまたはパス）を決定する。オペレーション３０９では、複数の部分から１つを選択する（例えば、複数の流れを持つ１つのインスタンスを選択するか、または最小カットの上の敏感な素子の集合を選択するか、または敏感なパスから敏感なインスタンスを選択する）。一実施形態では、選択は、オペレーション３０５で決定された指標に基づく。例えば、最も敏感な指標を持つものが、変換対象として最初に選択される。オペレーション３１１で、選択されたものに対し修正を実行する（例えば、サイズアップ、負荷の遮蔽、信号のバッファリング）。オペレーション３１３で、その修正が受け入れ可能である（例えば、選択されたものに対する修正が、最悪のネガティブ・スラックを低下しない）と判断された場合には、オペレーション３１５は修正のために次のものを選択することに進み、そうでない場合には、オペレーション３１７は、他の候補を処理するために修正を破棄する。
【００８０】
図６のオペレーション３３１では、第１の回路設計の実装に際して設計制約に違反する可能性があるかどうかを示す指標を決定する。オペレーション３３３で、少なくともそれらの指標に基づいて第１の回路設計から複数の修正候補を決定する。オペレーション３３５で、修正候補をソートする（例えば、流れ、それぞれの候補を通る異なるパスの個数に応じて）。オペレーション３３７で、候補を選択する（例えば、最大の流れとともに）。オペレーション３３９では、候補をサイズアップする。オペレーション３４１で、その修正がタイミング制約条件全体を悪化すると判断した場合、オペレーション３４５で、サイズを修正し、および／またはバッファまたは負荷遮蔽を使用し（すなわち他の設計変更を適用し）、そうでなければ、次の候補をサイズ設定対象として選択する。一実施形態では、この候補は、感度を低減する（または感度を十分に下げる）ためにサイズアップもバッファリングも行えない場合、その候補の最も弱い駆動がサイズアップされる。
【００８１】
本発明の一実施形態では、修正対象に候補を選択するループ（例えば、図５のオペレーション３１５から３０９まで、または図６のオペレーション３４３から３３７まで）は、最大利用限度に到達するまで、または感度を低減する改善がしきい値を下回るまで、続けられる。例えば、最大領域利用度制約条件（または、領域使用度の最大増加）を使用して、サイズアップおよび／またはバッファリングの対象の候補を選択する反復を停止することができる。さらに、候補のサイズアップおよび／またはバッファリングを行っても感度の改善は非常に限られている場合には、反復を終了させることができる。
【００８２】
本発明のさまざまな例は、この説明からタイミング制約条件とともに設計制約条件として例示されているが、当業者には、本発明のさまざまな方法は、さらに、初期段階の設計の部分（例えば、敏感なインスタンス）を選択的に変換し、初期段階の設計に基づく後の段階の設計において他の設計制約条件に違反する可能性を低減することもできることは明白であろう。感度解析を実行して、設計規則違反のインスタンスの感度を判定する（回路内の最大静電容量、最大遷移、および／または最大クロストークなど）。これらの設計規則（または制約条件）に違反する可能性を減じるために、回路の部分（例えば、インスタンスまたはパス）の感度に基づいて変換（例えば、サイズ設定）を選択的に実行できる。
【００８３】
本発明のほとんどの実施形態はＨＤＬ設計合成ソフトウェア・プログラムで使用することが意図されているが、本発明は、そのような使用に必ずしも限定されない。他の言語とコンピュータ・プログラムの使用も可能である。例えば、コンピュータ・プログラムは、ハードウェアを記述するように書くことができ、したがって、ＨＤＬの式とみなすことができる。それとは別に、本発明は、いくつかの実施形態では、ＨＤＬを使用せずに作成された論理表現、例えば、ネットリストの割り当てと、割り当て解除を実行することができる。本発明のいくつかの実施形態は、限定はしないがＨＤＬ合成システムで使用する文脈で説明し、特に、ベンダ特有の技術／アーキテクチャを含む集積回路とともに使用するように設計されたものについて説明する。よく知られているように、ターゲット・アーキテクチャは、通常、ＩＣの製造会社により決定される。本発明のいくつかの実施形態は、ＬＳＩ Ｌｏｇｉｃ、ＮＥＣ、ＩＢＭ、Ａｒｔｉｓａｎ Ｃｏｍｐｏｎｅｎｔｓ Ｉｎｃなどのベンダから出されている、構造化ＡＳＩＣとプラットフォームＡＳＩＣを含む、特定用途向け集積回路（ＡＳＩＣ）と併用することができる。本発明のいくつかの実施形態は、プログラマブルＩＣと併用することもできる。ターゲット・アーキテクチャの一例は、カリフォルニア州サンノゼのＸｉｌｉｎｘ，Ｉｎｃ．社から市販されているフィールド・プログラマブル・ゲート・アレイである集積回路のプログラマブル・ルックアップ・テーブル（ＬＵＴ）や関連する論理回路である。ターゲット・アーキテクチャ／技術の他の例は、Ａｌｔｅｒａ、Ｌｕｃｅｎｔ Ｔｅｃｈｎｏｌｏｇｙ、Ａｄｖａｎｃｅｄ Ｍｉｃｒｏ Ｄｅｖｉｃｅｓ、およびＬａｔｔｉｃｅ Ｓｅｍｉｃｏｎｄｕｃｔｏｒなどのベンダから出ているフィールド・プログラマブル・ゲート・アレイや複雑なプログラマブル論理デバイスのよく知られているアーキテクチャを含む。
【００８４】
物理的合成時に、経路推定器を使用して、配線静電容量、配線抵抗、ピン間遅延を予測することができ、これは、バックエンド設計ソフトウェア・プログラムを使用して詳細な配線を実行した後でないと正確に判別できない。合成実行時に完全な詳細経路を最新状態に保つと資源（例えば、計算時間とメモリ使用量）を消費しすぎるため、経路推定器が通常使用される。合成時のネット遅延の正確な予測ができれば、バックエンド・ツールからの詳細情報を使用して決定されたタイミングと合成ツールのタイミング予測との間の相関を改善できる。しかし、ネット遅延は、ネット経路トポロジに大きく依存している。いくつかの条件の下では（例えば、ネットのファンアウトの個数が増えたとき）、バックエンド・ツールで使用されるネット経路トポロジは予測不可能になる。
【００８５】
図７〜８は、経路トポロジの不確定性による配線長を推定する際の不確定性を例示する図である。同じ全配線長を持つ経路トポロジが多数存在する場合がある。図７では、駆動素子４０１と負荷素子４０３〜４０７を接続するネットは、時計回りの方向に配線される。図８では、駆動素子４０１と負荷素子４０３〜４０７を接続するネットは、反時計回りの方向に配線される。ネットの全配線長は図７、８の経路トポロジの場合と同じであるが、負荷素子４０３と４０７との間の距離は、図７、８に例示されている異なる経路トポロジが使用される場合には著しく異なる。図７、８の異なる経路トポロジは、全配線長が同じままであったとしても、負荷素子４０３、４０７に対して非常に異なる距離、したがって異なる抵抗値を生じる。多くのバックエンド・ツールではネットを配線する際に全配線長を最小にしようとするので、合成ツール側で、図７、８の異なる経路トポロジのどれがバックエンド・ツールで使用できるかを予測することは困難である。例えば、一方のバックエンド・ツールで図７のトポロジを使用するが、他のバックエンド・ツールでは図８のトポロジを使用することがある。経路トポロジの不確定性により、バックエンド・ツールは、タイミング要件を満たさないソリューションを生成する場合があるが、それは、バックエンド・ツールは、合成ツールの推定と異なる経路トポロジを使用してネットを配線できるからである。
【００８６】
図９は、本発明の一実施形態により経路トポロジの不確定性を低減する方法を例示する図である。図９では、複製された駆動素子４０９は、元の駆動素子４０１の複製である。元の駆動素子のネットは変換され、ドライバ素子４０１、４０９に対し負荷素子４０３〜４０７を分割する。変換の後、元の駆動素子４０１は、素子４０３のみを駆動し、複製された駆動素子は、素子４０５、４０７を駆動する。したがって、バックエンド配線ツールで使用される予想経路トポロジは明らかになる。経路トポロジに対する感度が低減される。
【００８７】
経路トポロジ内には不確定性の原因が多数ある。バックエンド詳細ルータ（例えば、メーズ(maze)・ルータまたはチャネル・ルータ）では、合成ツールに埋め込まれているグローバル・ルータ・エスティメータと比較すると、ネットの配線に異なるアルゴリズムを使用することができ、したがって、異なる順序でネット上に負荷素子を配線することができる。また、配線輻輳の推定がわずかでも違うと、異なる選択になる可能性もある。この変動により、特に高いファンアウト・ネットの場合に、タイミングの著しい変動が出力される可能性がある。したがって、駆動素子と負荷素子との間の予測される配線遅延は、詳細な配線と抽出後に決定されるものとかなり異なる可能性がある。経路トポロジ内の不確定性により、合成ツールでモデル化されたドライバ負荷パス遅延は、設計の配線後にバックエンド内で決定されるドライバ負荷遅延とあまりよく相関しない可能性がある。
【００８８】
バックエンド・ルータ・ツールによって実行された配線が物理的合成時に推定される配線と相関する確率を高めるアルゴリズムが存在する。物理的合成ツールは、フォワード・アノテーションの形で配線に関する情報を提供することができる。フォワード・アノテーションは、ネット迂回路により生じうるネット遅延相関問題を最小限に抑えることを目的とする、ネット経路順序付けとアンカー・セルを含むことができる。しかし、従来の合成ツールでは、ネット遅延相関に対する負荷素子の順序の影響を考慮しない。
【００８９】
この相関問題を最小限に抑えるために、本発明の一実施形態では、相関問題を引き起こす可能性のあるネットを選択的に選び、優先順位順でそれらを変換する。これらの変換は、ファンアウトの個数を減らし、ネットの形状を非対称にすることによりネット遅延に対する不確定性を最小にする。コスト判定基準が満たされていることを保証しつつ遅延相関を改善する詳細な方法について以下で説明する。
【００９０】
本発明の一実施形態では、経路トポロジ変動最小化アルゴリズムを使用し、経路トポロジに対し敏感な遅延を持つネットの集合を見つけて変換する。異なる経路トポロジがバックエンド・ルータで使用される場合に、特に、バックエンド・ルータで使用される代替経路トポロジにより物理的合成時に予測されるのと異なるネット上のピンへの遅延特性が生じる可能性がある場合に、その変換が、発生するタイミング違反の可能性を低減する。一実施形態では、ネット選択と変換アルゴリズムは、新しいネットが変換できなくなるまで設計内のすべてのネットを調べ、所定のコスト関数を悪化させない方法で感度を低減する。それによって、回路の物理的合成設計は、バックエンド配線ツールが設計の配線に使用される場合に後続の無効な配線実装が続く可能性を低減して最適化される。
【００９１】
一実施形態では、コスト関数は、最悪ネガティブ・スラック、トータル・ネガティブ・スラック、変換されるネットの全配線長、ピーク利用制限、設計の最大許容面積増大のうちの１つまたは複数に基づく。最適化プロセスにおける異なる強調部分に対し、異なるコスト関数を構築できることは理解されるであろう。最適化プロセスに対する変換は、ユーザによって指定された論理的および物理的制約条件に違反しない。
【００９２】
本発明の一実施形態では、一組の論理的および物理的最適化を使用し、ネットを変換して経路トポロジに対する感度を低減する。例えば、ネットに接続されている論理回路は、複製、サイズ設定、バッファリング、配置変更を通じて変換することができる。ネットのドライバを複製できる場合、複製変換を使用して、ネットのシンク（ネットのドライバの負荷素子）を分割する。複製変換が使用できない場合（例えば、設計制約条件があるため）、ネットは、新しいバッファがネットのシンクのいくつかを駆動するようにバッファリングすることができる。複製されたインスタンス（またはバッファ）や元のドライバのサイズ設定は、コスト関数が悪化しないように実行することができる。
【００９３】
新しいインスタンスが変換により作成されると、それらは、正当な位置にあるダイス上に配置される。一実施形態では、コスト関数は、変更の公認の前後にチェックされる。それらの変更は、コスト関数が悪化する場合には逆転される。例えば、パス上の最悪ネガティブ・スラックが変換は後に悪化する場合、変換は逆転される。
【００９４】
本発明の一実施形態では、ネット毎に可能な代替経路トポロジを調べて、変換対象のネットを選択する。標準的な配線長駆動ルータは、特定の領域内の全配線長と輻輳を最小にする有効な経路を作成しようと試みる。そのような配線長駆動ルータは、非常に異なる遅延特性を持つが、ほぼ等しい配線長と輻輳特性を持つ、多数の異なる経路トポロジのうちの１つを使用することができる。標準的なタイミング駆動ルータは、遅延を最小にしようと試みる。しかし、タイミング駆動ルータであっても、輻輳または他のコストを最小にするために代替トポロジを使用することができる。タイミング駆動配線は、非常に高価であり、設計全体上で実施できない。輻輳は、さらに、配線経路アルゴリズムと設計内の小さな変動に基づいて変化する場合があるため、バックエンド配線ツール内で使用されるアルゴリズムが知られているとしても、まだ、実際の経路を予測することには困難な場合がある。したがって、本発明の一実施形態では、これらの経路のどれかが設計制約条件（例えば、タイミング要件）に違反するかどうかを判定するためにさまざまな配線経路アルゴリズムにより使用される可能性がある可能なトポロジを調べる。経路トポロジの選択に対する設計制約条件の有効性の影響を受ける可能性のあるネットを識別した後、変換を設計に適用し、バックエンド・ツールを使用して配線した後に設計が無効になる可能性を低減することができる。
【００９５】
複数のこのようなネットが特定のパス上に存在する場合に効果が高まることがあるので、本発明の一実施形態では、変動がないかサブパスまたはパスを調べる。
【００９６】
可能な経路トポロジを決定するのは時間がかかる場合があるため、また多くの資源を使用するので、本発明の一実施形態では、多数の発見的手法を使用して、異なる配線または配線推定を実行せずに経路トポロジに敏感なネットを判別する。例えば、ネットが多数の判定基準を満たしている場合、経路トポロジに敏感である可能性が非常に高いと判断され、ネット遅延相関の問題が生じうる。
【００９７】
一実施形態では、ネットのファンアウトの個数は、主要な選択基準である。ファンアウトの個数が増大した場合、シンク順序は、遅延モデル内の変動に対する高い影響を持つことがある。一実施形態では、ネットは、ネットのファンアウトの個数がしきい値よりも大きい（例えば、２）場合にのみ経路トポロジ感度の低減の対象とみなされる。ファンアウトの個数が少ない（例えば、２以下）場合、ネットは、経路トポロジに対し敏感でないとみなすことができる。
【００９８】
ネットの形状は、さらに、代替経路トポロジの可能性にも影響を及ぼすことがある。例えば、ネットの形状が正方形に近い場合、ルータがシンクの配線順序を選ぶ選択肢が増えることになり、したがって、ネットのシンクまでの遅延は、さらに予測不可能になる可能性がある。これは、特に、配線長駆動ルータの場合に当てはまるが、それは、正方形の形をしたネット上の個々のシンクまでの遅延は、全配線長が図７、８に例示されているようにかなり一定であっても、シンクが接続される順序とともに大幅に変化する可能性がある。そのため、一実施形態では、変換対象のネットも形状歪み基準を使用して選択される。
【００９９】
図１０〜１２は、本発明の一実施形態により経路トポロジの不確定性による配線長の変動を推定する方法を例示する図である。図１０は、長さＳの短い辺と長さＬの長い辺を持つ矩形形状のネットを例示している。駆動素子（Ａ５０１）の位置と負荷素子（Ｂ５０７、Ｃ５０５、Ｄ５０３）の位置は、ネットの形状を決定する。バックエンド・ルータは、通常、全配線長を最小にするので、ネットの配線は、ネットの形状の長い辺の方向ではなく短い辺の方向の迂回路を含むのがふつうである。例えば、図１１に例示されているＡ（５０１）からＤ（５０３）、Ｃ（５０５）への経路と比較して、図１０に例示されているＡ（５０１）からＢ（５０７）、Ｃ（５０５）、Ｄ（５０３）への経路は、Ｄ（５０３）に対する短い辺の方向の迂回路を含む。ネットの形状の短い辺の方向の迂回路は、ネットの境界ボックスの短い辺の長さの２倍、配線長を増やす。そのため、本発明の一実施形態では、負荷素子の位置から決定される、ネットの境界ボックスの短い辺の長さを使用して、経路トポロジの変動による配線長の変動を推定する。
【０１００】
図１２は、境界ボックスの短い辺の方向の迂回路の影響を例示している。図１２では、境界ボックス５２０は、駆動素子（５２１）の負荷素子（例えば、５２３〜５２７）を囲む。経路５３１（実線）は、ドライバ５２１と負荷５２３との間のマンハッタン距離（直線距離とも呼ばれる）を示す。マンハッタン距離は、通常、ドライバと負荷との間の配線距離の下限である。経路５３３（破線）は、素子５２３の前で素子５２７と５２５を接続する迂回路を示しており、これは、そのマンハッタン距離にわたる境界ボックス（５２０）の短い辺の長さ（Ｓ）の２倍だけ、素子５２３の配線長を近似的に増やす。そこで、本発明の一実施形態では、境界ボックスのマンハッタン距離と短い辺の長さ（Ｓ）を使用して、異なる経路トポロジを考慮して配線長（２つの論理素子間の距離）を推定する。
【０１０１】
一実施形態では、駆動素子と負荷素子との間の距離は、その駆動素子と負荷素子との間のマンハッタン距離（直線距離とも呼ばれる）に基づいて推定される。異なる経路トポロジの影響を考慮しつつ、距離は、さらに、マンハッタン距離と負荷素子の境界ボックスの短い辺の長さに基づいて推定される例えば、境界ボックスの短い辺の方向に迂回路があると、境界ボックスの短い辺の長さの２倍だけ、配線長が増大する。そのため、ｄMを駆動素子と負荷素子との間のマンハッタン距離とし、Ｓを負荷素子の境界ボックスの短い辺の長さとすると、この距離はｄM＋２×Ｓと推定することができる。その後、配線遅延は、Ｄuを単位配線遅延とすると、（ｄM＋２×Ｓ）×Ｄuと推定することができる。一実施形態では、ネットは、経路トポロジ内の差による配線長の推定される変動により、スラックが負になる（またはパス上の最悪ネガティブ・スラックを悪化させる）場合に変換の候補として選択される。
【０１０２】
異なる定式化を使用して、異なる状況にある経路トポロジの変動による距離変動をモデル化することができることに注意されたい。例えば、配線遅延は、曲線の当てはめにより統計データから求められる係数を含む実験式を使用して推定することができる。バック・アノテーション（または典型的な設計での試験実行）を使用して、特定のバックエンド・ソフトウェア・ツールに対する係数を導くことができる。したがって、異なるバックエンド・ソフトウェア・ツールに対し、異なる定式化を使用することができる。
【０１０３】
経路トポロジ内の不確定性による駆動素子と負荷素子との間のパス遅延の同じ変動は、異なるパス上のタイミング制約条件に対し非常に異なる影響を及ぼす可能性がある。そのため、本発明の一実施形態では、さらにタイミング要件に基づいて変換対象のネットを選択する。例えば、ドライバ・スラックがタイミング・クリティカルまたはクリティカルに近いパス上のネットについて範囲Ｔ内にある場合、そのネットは経路トポロジの感度の考慮対象として選択される。適切なスラックを持つパスであれば、遅延相関問題を引き起こす可能性はないと考えることができ、したがって、評価する必要はない。本発明の一実施形態では、適切なスラックを持つパスに対する遅延推定相関は、問題があるとは考えられない。そのため、タイミング・クリティカルまたはクリティカルに近いパス上のネットのみが、経路トポロジへの感度を低減する対象として考慮される。輻輳の量に関する不確定性を含む、最終経路に関する追加不確定性も、考慮することができる。例えば、輻輳の予測が正確であるほど、必要なＴの範囲は小さくてよい。さらに、Ｔの値は、典型的な設計についてバックエンド・ツールを何回も実行することに基づいて実験的に決定することが可能である。そのため、本発明の一実施形態では、ドライバ・スラックは、ネット・トポロジのせいで相関問題を生じる可能性があるネットを選択する際の追加判定基準である。
【０１０４】
ユーザ指定設計制約条件などの他の判定基準も、変換の候補として選択されるネットの集合をフィルタ処理するために使用することができる。例えば、いくつかのネットは、ユーザ指定設計制約条件に従って変換することができない。
【０１０５】
ネット候補の集合が変換対象として選択された後、ネットの集合を変換に関して優先順位付けすることができる。例えば、ネットの集合は、感度を低減する素子のサイズ設定について上で説明したのと同様に、流れに従って、または感度を指標に従って、またはグラフ上の最小カットに従って、優先順位付けすることができる。この流れは、ネット候補を通る全パスの数、またはネット候補を通るネガティブ・スラック・パスの個数、またはネット候補通る輻輳パスの個数、またはネット候補を通る敏感なネットを含むパスの個数、またはネット候補を通るパスの個数の重み付けカウント（例えば、輻輳係数、ネガティブ・スラック、感度の指標など）とすることができる。本発明の一実施形態では、多数の変換（例えば、バッファリング、複製、サイズ設定、配置並べ換え）を使用して、設計のコスト関数を悪化させることなく経路トポロジの影響を緩和する。
【０１０６】
通常、Ｉ／Ｏポートとマクロは複製から除外される。制約条件に違反した場合に設計の検証を妨げるものなどの設計制約条件も、状況によっては、複製を妨げる可能性がある。駆動インスタンスの複製が許容可能が場合（例えば、設計制約条件を破らない、コスト関数を悪化させない）、ネットは変換される。例えば、新しいネットの配線長の総和が元の単一ネットの配線長にほぼ等しくなるように、ネットのシンクを元の駆動インスタンスと複製された駆動インスタンスとの間に分割する。これにより、バラツキを減らしながら元のゲート面積と配線長を保持する。分割されたネットは、ネットの形状に関して高い歪みを持ち、したがって、元の駆動インスタンスと複製された駆動インスタンスの負荷素子の境界ボックスは、縦横比を減じている。元のドライバと新しいドライバは、コストが最小になるように適宜サイズ設定される。
【０１０７】
バッファリングは、複製ができない場合にできるようにする、またコスト判定基準に違反せずにトポロジの不確定性を低減する手段となる、もう１つの代替手段である。一実施形態では、パスにそって余分にバッファを追加することは、余分バッファが伝送のコスト（例えば、パス上の最悪ネガティブ・スラック）を上昇させない場合にのみ実行される。バッファの挿入が許容される場合（例えば、バッファを配置するための場所がある）、ネットのシンクは分割され、新しく作成されたネットがネットの形状に関して高い歪みを持つようにシンクの一部が挿入されたバッファに再接続される。したがって、変換の後、元のドライブの負荷素子の境界ボックスおよび新しいバッファの負荷素子の境界ボックスは、縦横比が小さくなる。さらに、新しいネットの配線長の合計が一実施形態の元の単一ネットの配線長にほぼ等しくなるように分割が行われる。この目標は、バラツキを改善（低減）しつつ元のゲート面積と配線長を保持する。元のドライバは、さらに、コスト関数が最小になるようにサイズ設定することができる。
【０１０８】
いくつかの場合において、ドライバ（またはバッファ）の複数がすでに存在する可能性があり、これは、経路トポロジの不確定性を低減すること以外の目的のために合成プロセスにおいて作成される場合がある。このような場合、これらの存在している素子の負荷素子は、既存の設計制約条件に反せずに経路トポロジの不確定性の低減のため再配分または再分割することができる。
【０１０９】
いくつかの場合において、負荷素子および／または駆動素子の配置位置は、経路トポロジ内の不確定性の影響を軽減するように調整することができる。そのため、ネットのシンクの配置を変えて、負荷素子の境界ボックスの縦横比を低減することができる（ネットの形状の歪みを大きくする）。
【０１１０】
その他、本発明の一実施形態では、適度な数のネットが修正対象に選択される。修正では一定に近い配線長とゲート面積を維持しようと試みるので、修正された設計の配線可能性とコストは未修正の設計と同様のままであるが、配線後に無効な設計となる可能性が低減されている。
【０１１１】
図１３は、本発明の一実施形態により回路を設計する方法を例示する図である。オペレーション６０１で回路の設計（例えば、回路の論理合成ソリューションのネットリスト表現）を受け取った後、オペレーション６０３は、回路の設計の配置を実行する。オペレーション６０５は、配線内の不確定性によるタイミング制約条件の違反の可能性を低減するために変換対象のネットの集合を選択する。オペレーション６０７では、ネットの選択された集合に対する回路設計の一部分に変換を実行して、ルータにより配線されたときにタイミング制約条件に違反することにそのネットの集合が関わる可能性を低減する。本発明の一実施形態では、変換は、配線長とゲート面積が実質的に同じままである範囲で実行されるが、その一方で、バックエンド配線ツールにより使用することができる経路トポロジ内の不確定性、特に、タイミング制約条件を満たさない配線ソリューションに至る可能性のある経路トポロジの不確定性を低減する。
【０１１２】
図１４は、本発明の一実施形態により回路設計を最適化する方法を例示する図である。オペレーション６２１が回路の設計に対する配置ソリューションを受け取った後、オペレーション６２３は、経路トポロジへの感度を低減することについてネットを調べる。オペレーション６２５でそのネットの遅延が経路トポロジに対し敏感であると判定した場合、オペレーション６２７で、経路トポロジに対するネットの感度を低減するために設計の一部分に変換を実行する。例えば、駆動素子を複製する、またはバッファを挿入する、または素子の配置を変更する、または負荷素子を既存の複製された駆動（またはバッファ）に再配分することができる。オペレーション６２９で、変換がコスト関数を悪化させる、または設計制約条件に違反すると判断された場合（例えば、新しく挿入された素子の配置に対する面積不足）、オペレーション６３３は、その変換をキャンセル（または逆転）し、そうでなければ、変換は保持される（６３１）。感度がすでに、正常に低減されていない場合、オペレーション６３５では、適用可能が代替変換があるかどうかを判別する。コスト関数を悪化させない、また設計制約条件に違反しないようにしながら、ネットの経路トポロジ感度を低減するための変換のリストの作成を行うことができる。それぞれのネットは、オペレーション６３７でネットがすでに考慮されていると判断するまで、経路トポロジに対する感度の低減について考慮される。
【０１１３】
本発明の一実施形態では、ネット上の遅延が経路トポロジに対し敏感であるか否かを推定するために多数の判定基準が使用される。例えば、ネットのファンアウトが３つよりも少なく、これは経路トポロジに敏感でないと考えることができる。さらに、ネットのドライバのスラックがしきい値よりも高い場合も、経路トポロジに敏感でないと考えることができる。さらに、経路トポロジ内の変動による余分な推定距離（例えば、負荷素子の境界ボックスの短い辺の長さの２倍）により、スラックが負にならない（またはパス上の最悪ネガティブ・スラックよりも悪くない）場合に、ネットは、経路トポロジに敏感でないと考えることができる。そのため、経路トポロジに対するネットの感度は、異なるアルゴリズムを使用して詳細配線を実行せずに、また実際の異なる経路トポロジを判別せずに、効率良く評価される。
【０１１４】
図１５は、本発明の一実施形態により最適化するネットを選択する方法を例示する図である。オペレーション６５１では、ネットの推定された経路を判別する。推定された経路は、グローバル・ルート・エスティメータを使用して決定することができる。それとは別に、推定される経路は、ネットの駆動素子と負荷素子の位置からのみ決定することができる。例えば、素子間の距離は、負荷素子と駆動素子との間のマンハッタン距離として推定できる。推定された経路は、タイミング要件が満たされているかどうか判別するために使用される。例えば、推定された経路を使用して、素子のスラック、パス上の最悪ネガティブ・スラック、その他のタイミング・パラメータを決定することができる。タイミング要件が満たされていない場合、回路の設計は修正される。通常、経路トポロジの感度の低減は、受け入れ可能なソリューションが得られた後でないと実行されないが、経路トポロジの感度の低減は合成プロセス時に実行することも可能である。オペレーション６５３で、ネットに対し代替経路があると判定した場合、オペレーション６５５は、代替経路がネットに使用される場合にタイミング・パラメータを決定する。代替経路は、異なる戦略を使用する配線を通じて決定することができるが、これは、時間のかかる作業である。本発明の一実施形態では、ネットに対し代替経路が存在しているかどうかは、複数の判定基準から決定されるが、これは、非常に効率よくチェックすることができる。これらの判定基準の例は、ネットのファンアウトの個数とネットの形状を含む。オペレーション６５７で、タイミング・パラメータが設計制約条件の範囲内にあると判定した場合（または、オペレーション６５３で、ネットに対する代替経路がないと判定された場合）、そのネット（６６１）には変換は不要であり、これは、経路トポロジに対する感度の低減のため変換を必要としない。オペレーション６５７で、タイミング・パラメータが設計制約条件の範囲内にないと判定した場合、オペレーション６５９は、経路トポロジに対する感度を低減する変換のためネットを選択する。
【０１１５】
図１６は、本発明の一実施形態により最適化するネットを選択する詳細な方法を例示する図である。オペレーション６７１では、クリティカル・パスとクリティカルに近いパス上のネットを判別する（例えば、クリティカルな値の範囲内のスラックを持つドライバ）。オペレーション６７３で、クリティカル・パスまたはクリティカルに近いパス上のネットのファンアウトの個数が２以下であると判定した場合、ネットは、感度低減オペレーション（６８５）に関して無視され、そうでなければ、オペレーション６７５は、ネットのシンクの境界ボックスの縦横比を決定する。オペレーション６７７で、境界ボックスの縦横比は１に近くない（例えば、０．５などしきい値よりも小さい、または統計データから求められた数値）場合、ネットは、感度低減オペレーション（６８５）に関して無視され、そうでなければ、オペレーション６７９で、代替配線パスによる余分な距離を推定する（例えば、矩形の境界ボックスの短い辺の２倍）。オペレーション６８１で、余分な距離がネガティブ・スラック（または他のタイミング要件の違反）に至らないと判定した場合、ネットは、感度低減オペレーション（６８５）に関して無視され、そのような判定しない場合、オペレーション６８３で、感度低減オペレーションに対するネットを選択する。図１６に例示されているすべての選択基準を使用する必要はないことに注意されたい。例えば、オペレーション６７７は、一実施形態では使用することができない。さらに、他の選択基準も、図１６に例示されている選択基準の一部またはすべてといっしょに使用することもできる。例えば、ネットの集合が変換のための候補として選択された後、流れに応じて、またはサイズ設計のための敏感なインスタンスの優先順位付けと同様にしてグラフ上の最小カットの選択を通じて、ネットの集合を優先順位付けすることができる。
【０１１６】
図１７は、本発明の一実施形態により経路トポロジの感度を低減するため回路設計を変換する詳細な方法を例示する図である。オペレーション７０１で感度低減オペレーションの対象のネットを選択した後、オペレーション７０３で、ドライバおよびシンクの配置を変更して、経路トポロジへの感度を低減する。例えば、配置を変更して、ネットのシンクの境界ボックスの縦横比を小さくできる。オペレーション７０５で、感度を下げるためにネットに対しさらに変換を必要とすると判断した場合（例えば、配置を変更することによりネットのシンクの境界ボックスの縦横比を十分に下げられない場合）、オペレーション７０７では、ネットのドライバを複製できるかどうかを判定する。設計制約条件により、ドライバの複製が可能である場合、オペレーション７１１で、ネットのドライバを複製し、オペレーション７１３で、複製されたドライバを配置し、オペレーション７１５で、ネットのシンクを、元のドライバのシンクと複製されたドライバのシンクとして分割し、経路トポロジに対する感度を低減し、オペレーション７１７で、元のドライバと複製されたドライバのサイズを設定する（例えば、コストを最小にするため）。しかし、ネットのドライバを複製できない場合（例えば、ネットのドライバがＩ／Ｏポートまたはマクロであるか、または複製されたドライバの配置に適切な場所がない）、オペレーション７０９で、ドライバとネットのシンクとの間にバッファを挿入できるかどうか（例えば、ドライバとネットのシンクとの間にバッファを配置するのに適した場所があるかどうか）を判別する。オペレーション７２１がネットの元のドライバのシンクとしてバッファを挿入した後、オペレーション７２３で、バッファを配置し、オペレーション７２５で、ネットのシンクを、元のドライバのシンクとバッファのシンクとして分割して経路トポロジへの感度を低減し、オペレーション７２７で、元のドライバのサイズを設定する（例えば、面積コストを低減するため）。本発明の一実施形態では、バッファの挿入は、修正しても回路を悪化させない場合にのみ受け入れられる。例えば、バッファの挿入は、パス上の最悪ネガティブ・スラックが悪化しない場合にのみ受け入れられ、その場合、推定された配線パスが、代替経路トポロジによる余分な距離を考慮せずに使用される。そのため、経路トポロジに対する感度の低減は、回路の設計を低下させずに実行される。ドライバの複製とバッファの挿入が許容可能でない場合、他の変換をさらに試みることが可能である。例えば、ドライバが複製されたインスタンスをすでに持っている場合、シンクを再分割して、その感度を低減することができる。
【０１１７】
上記の例の少なくとも一部は、タイミング制約条件に関係する設計制約条件を伴う（例えば、回路の最悪ネガティブ・スラック、回路の設計における論理素子のインスタンスのスラック、回路の設計におけるパス上の遅延、回路のトータル・ネガティブ・スラックなど）。しかし、設計制約条件は、他の種類の制約条件とすることが可能であることは理解できるであろう。例えば、これらの制約条件は、最大静電容量、ドライバ素子と負荷素子との間の最大配線長、または異なる種類の設計規則と制約条件の集合に関する条件とすることができる。設計制約条件は、幾何学的パラメータ、タイミング・パラメータ、インピーダンス・パラメータ、および／またはその他のパラメータに関する条件とすることができる。本発明の少なくともいくつかの実施形態によれば、これらの制約条件の変更の影響は、経路トポロジの変動として推定され、その後の実装の経路トポロジの変動がそれらの制約条件の違反を引き起こす可能性がある確率を低減するために変換が実行される。
【０１１８】
上記の例のうちのいくつかでは、初期の段階の設計（例えば、合成変換）における不確定性は、回路設計の異なる実装が後の方の段階の設計（例えば、配線）で実行された場合の設計制約条件に関連するパラメータの変更によるものである。しかし、不確定性は、さらに、いくつかの設計構成の設計制約条件に関連するパラメータを推定する際の可能な誤差からも発生しうる。例えば、いくつかのパラメータの推定の正確さは、特定の配線トポロジに関しては劣ることがある。そのため、一実施形態では、これらのパラメータのソリューションの束縛された誤差は、設計制約条件に違反する可能性を判別するために配線トポロジに関連付けられる。それとは別に、推定の正確さを低下させる配線トポロジは、合成変換を実行して、それらの構成を回避し、配線後に無効な設計が生じる可能性低減するように識別することもできる。
【０１１９】
例えば、いくつかのネット・トポロジは、合成時に使用される高速で、単純なネット遅延モデルでモデル化することは困難である。Ｅｌｍｏｒｅ遅延モデルは、高速なネット遅延モデルの一例である。簡単に計算できるネット・モデルは、状況によっては精度を落とす。これらの状況におけるタイプのネットは、経路トポロジの変更の影響を受けやすいと考えることができる。変換（例えば、複製）を使用して、単純な遅延モデルの不正確さを低減するために可能なネット・トポロジを修正することができる。
【０１２０】
例えば、回路設計においてドライバの近くにあるいくつかの負荷がネット上にあり、ほかは遠く離れている場合、パス遅延予測は、遠く離れている負荷、またはドライバに関して異なる方向に配置されている負荷上では不正確になる可能性があり、これは、特に、その負荷への著しい遷移低下がある場合にはそうである。さらに、経路トポロジの影響が不正確な遅延予測に加わる可能性がある。このような構成では、Ｅｌｍｏｒｅ遅延モデルは、正確でなく、設計は、異なる経路トポロジに敏感になる。そのため、単純な遅延モデル（例えば、Ｅｌｍｏｒｅ遅延モデル）が合成時に使用される場合、設計制約条件違反の可能性は高い。本発明の一実施形態では、そのようなネットのドライバは、近くの負荷が一方のドライバにより駆動され、遠い負荷が他方のドライバにより駆動されるように複製される。同様に、本発明の一実施形態では、同じドライバに関して異なる方向に配置されている負荷を持つことを回避することを試みる（例えば、ドライバを複製することにより）。ドライバを複製してシンクのいくつかに近づけると、遅延推定の精度が向上し、バックエンドで使用される異なる経路トポロジが設計制約条件の違反を引き起こす可能性を減じるこのような合成変換により、遅延の推定精度は向上し、後の段階の実装において無効な設計となる可能性が低くなる。
【０１２１】
本明細書では、発明は特定の例示的な実施形態を参照しつつ説明がなされている。本発明は、付属の請求項で定められているように、本発明の広い精神と範囲を逸脱することなくさまざまな修正を加えられることは明白であろう。したがって、明細書および図面は、限定ではなく、説明することを目的としているものとみなすべきである。
【図面の簡単な説明】
【０１２２】
【図１】本発明とともに使用できるデータ処理システムのブロック図の例である。
【図２】本発明の一実施形態により回路を設計する方法を示す図である。
【図３】本発明の一実施形態により回路を最適化する方法を示す図である。
【図４】本発明の一実施形態により回路を最適化する詳細な方法を示す図である。
【図５】本発明のいくつかの実施形態により回路を選択的に修正する詳細な方法を示す図である。
【図６】本発明のいくつかの実施形態により回路を選択的に修正する詳細な方法を示す図である。
【図７】経路トポロジの不確定性による配線長を推定する際の不確定性を例示する図である。
【図８】経路トポロジの不確定性による配線長を推定する際の不確定性を例示する図である。
【図９】本発明の一実施形態により経路トポロジの不確定性を低減する方法を例示する図である。
【図１０】本発明の一実施形態により経路トポロジの不確定性による配線長の変動を推定する方法を例示する図である。
【図１１】本発明の一実施形態により経路トポロジの不確定性による配線長の変動を推定する方法を例示する図である。
【図１２】本発明の一実施形態により経路トポロジの不確定性による配線長の変動を推定する方法を例示する図である。
【図１３】本発明の一実施形態により回路を設計する方法を例示する図である。
【図１４】本発明の一実施形態により回路設計を最適化する方法を例示する図である。
【図１５】本発明の一実施形態により最適化するネットを選択する方法を例示する図である。
【図１６】本発明の一実施形態により最適化するネットを選択する詳細な方法を例示する図である。
【図１７】本発明の一実施形態により経路トポロジの感度を低減するため回路設計を変換する詳細な方法を例示する図である。
【特許請求の範囲】
【請求項１】
回路の設計の後の配線実装時に設計制約条件に違反する可能性があるかどうかを判定することと、
前記設計の後の配線実装で前記設計制約条件に違反する可能性を低減するように前記回路の前記設計を修正することと
を含む回路を設計する方法。
【請求項２】
前記設計のその後の配線実装時に前記設計制約条件に違反する可能性は、経路トポロジを推定する際の不確定性によるものである請求項１に記載の方法。
【請求項３】
前記設計のその後の配線実装時に前記設計制約条件に違反する可能性は、経路トポロジのパラメータを推定する際の不確定性による請求項１に記載の方法。
【請求項４】
さらに、
前記回路の前記設計における経路トポロジが、前記設計制約条件に関連するパラメータを決定する際に精度の低下を引き起こすかどうかを判定することを含む請求項３に記載の方法。
【請求項５】
前記設計のその後の配線実装時に前記設計制約条件に違反する可能性があるかどうかは、少なくとも駆動素子の負荷素子を囲む境界ボックスに基づいて判定される請求項１に記載の方法。
【請求項６】
前記設計のその後の配線実装時に前記設計制約条件に違反する可能性があるかどうかは、タイミング・クリティカルまたはクリティカルに近いパス上のネットのファンアウトの個数にさらに基づいて判定され、前記ネットは、前記駆動素子を前記負荷素子に接続する請求項５に記載の方法。
【請求項７】
前記修正することは、
第１の駆動素子を複製して、第２の駆動素子を挿入することと、
前記第１の駆動素子の負荷素子の一部を前記第２の駆動素子の負荷素子として再接続することとを含む請求項１に記載の方法。
【請求項８】
前記修正することは、
バッファ素子を第１の駆動素子の負荷素子として挿入することと、
前記第１の駆動素子の負荷素子の一部を前記バッファ素子の負荷素子として再接続することとを含む請求項１に記載の方法。
【請求項９】
前記修正することは、
駆動素子の負荷素子の配置を再配列して前記駆動素子と前記負荷素子の境界ボックスの短い辺と長い辺との比を低減することを含む請求項１に記載の方法。
【請求項１０】
前記修正することは、
第１の素子の負荷素子の一部を第２の素子の負荷素子として変換することを含む請求項１に記載の方法。
【請求項１１】
前記設計制約条件は、タイミング制約条件を含む請求項１に記載の方法。
【請求項１２】
前記タイミング制約条件は、
ａ）前記回路の最悪ネガティブ・スラック、
ｂ）前記回路の前記設計内の論理素子のインスタンスに対するスラック、
ｃ）前記回路の前記設計内のパス上の遅延、
ｄ）前記回路のトータル・ネガティブ・スラックのうちの１つを含む請求項１１に記載の方法。
【請求項１３】
前記設計制約条件は設計規則を含む請求項１に記載の方法。
【請求項１４】
前記設計規則は、
ａ）最大静電容量、および
ｂ）駆動素子と負荷素子との間の最大配線長のうちの１つを含む請求項１３に記載の方法。
【請求項１５】
前記修正することは、
代替経路トポロジが使用される場合に前記設計制約条件の違反をそれぞれ引き起こす可能性がある多数のネット候補を判別することと、
前記多数のネット候補の部分集合について前記設計を選択的に修正することとを含む請求項１に記載の方法。
【請求項１６】
前記選択的に修正することは、
流れに従って前記多数のネット候補から１つを選択し、前記流れはネット候補を通る多数のパスの重み付きカウントを表すことを含む請求項１５に記載の方法。
【請求項１７】
前記多数のパスは、
前記ネット候補を通るすべてのパス、
前記ネット候補を通るすべてのネガティブ・スラック・パス、
前記ネット候補を通る輻輳パス、
前記ネット候補を通る敏感なネットを含むパスのうちの１つである請求項１６に記載の方法。
【請求項１８】
前記選択的に修正することは、
修正する前記部分集合を決定するために前記多数のネット候補を含むグラフに対し最小カットを実行することを含む請求項１５に記載の方法。
【請求項１９】
回路を設計する機械実装方法であって、
前記回路の設計に応じて駆動素子と前記駆動素子の負荷素子との間の第１の距離を推定することと、
前記第１の距離を使用してタイミング制約条件が満たされているかどうかを検証することと、
前記回路の設計に応じて前記駆動素子と前記負荷素子との間の、前記第１の距離よりも長い第２の距離を推定することと、
前記第２の距離を使用してタイミング制約条件が満たされているかどうかを判定することとを含む機械実装方法。
【請求項２０】
前記第１の距離は第１の経路トポロジに従い、前記第２の距離は第２の経路トポロジに従う請求項１９に記載の方法。
【請求項２１】
さらに、
前記第２の距離が使用される場合にタイミング制約条件が満たされていないと判定したことに対する応答として、前記回路の前記設計に対して変換を実行して、設計コスト関数を悪化させずに前記第２の距離を短縮することができるかどうかを判定することを含む請求項１９に記載の方法。
【請求項２２】
前記変換は、
前記駆動素子を複製すること、
前記駆動素子をサイズアップすること、
前記駆動素子と前記負荷素子との間にバッファ素子を挿入することと、
前記駆動素子と前記駆動素子の負荷素子のうちの少なくとも１つの素子の配置を調整することのうちの少なくとも１つを含む請求項２１に記載の方法。
【請求項２３】
前記第２の距離は、前記駆動素子と前記負荷素子を接続するネットが経路トポロジの感度の低減のため選択された場合にのみ推定される請求項１９に記載の方法。
【請求項２４】
前記ネットは、前記ネットがタイミング・クリティカルまたはクリティカルに近いパス上にあり、前記ネットのファンアウトの個数が２よりも多い場合にのみ、選択される請求項２３に記載の方法。
【請求項２５】
前記ネットは、さらに、前記駆動素子の負荷素子を囲む境界ボックスの縦横比に応じてさらに選択される請求項２４に記載の方法。
【請求項２６】
パス遅延を推定する機械実装方法であって、
駆動素子と、その駆動素子の複数の負荷素子との領域の形状を決定することと、
前記領域の形状に少なくとも基づき前記駆動素子と前記複数の負荷素子のうちの第１の素子との間の距離を推定すること
を含む機械実装方法。
【請求項２７】
前記領域の前記形状の前記決定は、
前記複数の負荷素子を囲む境界ボックスを決定することを含み、
前記距離は、少なくとも前記境界ボックスに基づいて推定される請求項２６に記載の方法。
【請求項２８】
前記推定することは、
前記駆動素子と前記複数の負荷素子のうちの前記第１の素子との間のマンハッタン距離を決定することを含み、
前記距離は、前記マンハッタン距離と前記境界ボックスの短い辺の長さの関数として推定される請求項２７に記載の方法。
【請求項２９】
前記境界ボックスは矩形である請求項２８に記載の方法。
【請求項３０】
データ処理システムにより実行された場合に回路を設計する方法を前記システムに実行させる実行可能コンピュータ・プログラム命令を格納する機械可読媒体であって、前記実行方法は、
前記回路の設計の後の配線実装時に設計制約条件に違反する可能性があるかどうかを判定することと、
前記設計の後の配線実装で前記設計制約条件に違反する可能性を低減するように前記回路の前記設計を修正することと
を含む機械可読媒体。
【請求項３１】
前記設計のその後の配線実装時に前記設計制約条件に違反する可能性は、経路トポロジを推定する際の不確定性による請求項３０に記載の媒体。
【請求項３２】
前記設計のその後の配線実装時に前記設計制約条件に違反する可能性があるかどうかは、少なくとも駆動素子の負荷素子を囲む境界ボックスに基づいて判定される請求項３０に記載の媒体。
【請求項３３】
前記設計のその後の配線実装時に前記設計制約条件に違反する可能性があるかどうかは、タイミング・クリティカルまたはクリティカルに近いパス上のネットのファンアウトの個数にさらに基づいて判定され、前記ネットは、前記駆動素子を前記負荷素子に接続するものである請求項３２に記載の媒体。
【請求項３４】
前記修正することは、
第１の駆動素子を複製して、第２の駆動素子を挿入することと、
前記第１の駆動素子の負荷素子の一部を前記第２の駆動素子の負荷素子として再接続することとを含む請求項３０に記載の媒体。
【請求項３５】
前記修正することは、
バッファ素子を第１の駆動素子の負荷素子として挿入することと、
前記第１の駆動素子の負荷素子の一部を前記バッファ素子の負荷素子として再接続することとを含む請求項３０に記載の媒体。
【請求項３６】
前記修正することは、
駆動素子の負荷素子の配置を再配列して前記駆動素子と前記負荷素子の境界ボックスの短い辺と長い辺との比を低減することを含む請求項３０に記載の媒体。
【請求項３７】
前記修正することは、
第１の素子の負荷素子の一部を第２の素子の負荷素子として変換することを含む請求項３０に記載の媒体。
【請求項３８】
前記設計制約条件は、タイミング制約条件を含む請求項３０に記載の媒体。
【請求項３９】
前記タイミング制約条件は、
ａ）前記回路の最悪ネガティブ・スラック、
ｂ）前記回路の前記設計内の論理素子のインスタンスに対するスラック、
ｃ）前記回路の前記設計内のパス上の遅延、
ｄ）前記回路のトータル・ネガティブ・スラックのうちの１つを含む請求項３８に記載の媒体。
【請求項４０】
前記修正することは、
代替経路トポロジが使用される場合に前記設計制約条件の違反をそれぞれ引き起こす可能性がある多数のネット候補を判別することと、
前記多数のネット候補の部分集合について前記設計を選択的に修正することとを含む請求項３０に記載の媒体。
【請求項４１】
前記選択的に修正することは、
流れに従って前記多数のネット候補から１つを選択し、前記流れはネット候補を通る多数のパスの重み付きカウントを表すことを含む請求項４０に記載の媒体。
【請求項４２】
前記多数のパスは、
前記ネット候補を通るすべてのパス、
前記ネット候補を通るすべてのネガティブ・スラック・パス、
前記ネット候補を通る輻輳パス、
前記ネット候補を通る敏感なネットを含むパスのうちの１つである請求項４１に記載の媒体。
【請求項４３】
前記選択的に修正することは、
修正する前記部分集合を決定するために前記多数のネット候補を含むグラフに対し最小カットを実行することを含む請求項４０に記載の媒体。
【請求項４４】
データ処理システムにより実行された場合に回路を設計する方法を前記システムに実行させる実行可能コンピュータ・プログラム命令を格納する機械可読媒体であって、前記実行方法は、
前記回路の設計に応じて駆動素子と前記駆動素子の負荷素子との間の第１の距離を推定することと、
前記第１の距離を使用してタイミング制約条件が満たされているかどうかを検証することと、
前記回路の設計に応じて前記駆動素子と前記負荷素子との間の、前記第１の距離よりも長い第２の距離を推定することと、
前記第２の距離を使用してタイミング制約条件が満たされているかどうかを判定することとを含む機械可読媒体。
【請求項４５】
前記第１の距離は第１の経路トポロジに従い、前記第２の距離は第２の経路トポロジに従う請求項４４に記載の媒体。
【請求項４６】
前記方法は、さらに、
前記第２の距離が使用される場合にタイミング制約条件が満たされていないと判定したことに対する応答として、前記回路の前記設計に対して変換を実行して、設計コスト関数を悪化させずに前記第２の距離を短縮することができるかどうかを判定することを含む請求項４４に記載の媒体。
【請求項４７】
前記変換は、
前記駆動素子を複製すること、
前記駆動素子をサイズアップすること、
前記駆動素子と前記負荷素子との間にバッファ素子を挿入することと、
前記駆動素子と前記駆動素子の負荷素子のうちの少なくとも１つの素子の配置を調整することのうちの少なくとも１つを含む請求項４６に記載の媒体。
【請求項４８】
前記第２の距離は、前記駆動素子と前記負荷素子を接続するネットが経路トポロジの感度の低減のため選択された場合にのみ推定される請求項４４に記載の媒体。
【請求項４９】
前記ネットは、前記ネットがタイミング・クリティカルまたはクリティカルに近いパス上にあり、前記ネットのファンアウトの個数が２よりも多い場合にのみ、選択される請求項４８に記載の媒体。
【請求項５０】
前記ネットは、さらに、前記駆動素子の負荷素子を囲む境界ボックスの縦横比に応じてさらに選択される請求項４９に記載の媒体。
【請求項５１】
データ処理システムにより実行された場合にパス遅延を推定する方法を前記システムに実行させる実行可能コンピュータ・プログラム命令を格納する機械可読媒体であって、前記実行方法は、
駆動素子と、前記駆動素子の複数の負荷素子との領域の形状を決定することと、
前記領域の形状に少なくとも基づき前記駆動素子と前記複数の負荷素子のうちの第１の素子との間の距離を推定することを含む機械可読媒体。
【請求項５２】
前記領域の前記形状の前記決定は、
前記複数の負荷素子を囲む境界ボックスを決定することを含み、
前記距離は、少なくとも前記境界ボックスに基づいて推定される請求項５１に記載の媒体。
【請求項５３】
前記推定することは、
前記駆動素子と前記複数の負荷素子のうちの前記第１の素子との間のマンハッタン距離を決定することを含み、
前記距離は、前記マンハッタン距離と前記境界ボックスの短い辺の長さの関数として推定される請求項５２に記載の媒体。
【請求項５４】
前記境界ボックスは矩形である請求項５３に記載の媒体。
【請求項５５】
回路を設計するためのデータ処理システムであって、
前記回路の設計の後の配線実装時に設計制約条件に違反する可能性があるかどうかを判定する手段と、
前記設計の後の配線実装で前記設計制約条件に違反する可能性を低減するように前記回路の前記設計を修正する手段とを備えるデータ処理システム。
【請求項５６】
前記設計のその後の配線実装時に前記設計制約条件に違反する可能性は、経路トポロジを推定する際の不確定性による請求項５５に記載のデータ処理システム。
【請求項５７】
前記設計のその後の配線実装時に前記設計制約条件に違反する可能性があるかどうかは、少なくとも駆動素子の負荷素子を囲む境界ボックスに基づいて判定される請求項５５に記載のデータ処理システム。
【請求項５８】
前記設計のその後の配線実装時に前記設計制約条件に違反する可能性があるかどうかは、タイミング・クリティカルまたはクリティカルに近いパス上のネットのファンアウトの個数にさらに基づいて判定され、前記ネットは、前記駆動素子を前記負荷素子に接続するものである請求項５７に記載のデータ処理システム。
【請求項５９】
前記修正する手段は、
第１の駆動素子を複製して、第２の駆動素子を挿入する手段と、
前記第１の駆動素子の負荷素子の一部を前記第２の駆動素子の負荷素子として再接続する手段とを備える請求項５５に記載のデータ処理システム。
【請求項６０】
前記修正する手段は、
バッファ素子を第１の駆動素子の負荷素子として挿入する手段と、
前記第１の駆動素子の負荷素子の一部を前記バッファ素子の負荷素子として再接続する手段とを備える請求項５５に記載のデータ処理システム。
【請求項６１】
前記修正する手段は、
駆動素子の負荷素子の配置を再配列して前記駆動素子と前記負荷素子の境界ボックスの短い辺と長い辺との比を低減する手段を備える請求項５５に記載のデータ処理システム。
【請求項６２】
前記修正する手段は、
第１の素子の負荷素子の一部を第２の素子の負荷素子として変換する手段を備える請求項５５に記載のデータ処理システム。
【請求項６３】
前記設計制約条件は、タイミング制約条件を含む請求項５５に記載のデータ処理システム。
【請求項６４】
前記タイミング制約条件は、
ａ）前記回路の最悪ネガティブ・スラック、
ｂ）前記回路の前記設計内の論理素子のインスタンスに対するスラック、
ｃ）前記回路の前記設計内のパス上の遅延、
ｄ）前記回路のトータル・ネガティブ・スラックのうちの１つを含む請求項６３に記載のデータ処理システム。
【請求項６５】
前記修正する手段は、
代替経路トポロジが使用される場合に前記設計制約条件の違反をそれぞれ引き起こす可能性がある多数のネット候補を判別する手段と、
前記多数のネット候補の部分集合について前記設計を選択的に修正する手段とを備える請求項５５に記載のデータ処理システム。
【請求項６６】
前記選択的に修正する手段は、
流れに従って前記多数のネット候補から１つを選択し、前記流れはネット候補を通る多数のパスの重み付きカウントを表す手段を備える請求項６５に記載のデータ処理システム。
【請求項６７】
前記多数のパスは、
前記ネット候補を通るすべてのパス、
前記ネット候補を通るすべてのネガティブ・スラック・パス、
前記ネット候補を通る輻輳パス、
前記ネット候補を通る敏感なネットを含むパスのうちの１つである請求項６６に記載のデータ処理システム。
【請求項６８】
前記選択的に修正する手段は、
修正する前記部分集合を決定するために前記多数のネット候補を含むグラフに対し最小カットを実行する手段を備える請求項６５に記載のデータ処理システム。
【請求項６９】
回路を設計するためのデータ処理システムであって、
前記回路の設計に応じて駆動素子と前記駆動素子の負荷素子との間の第１の距離を推定する手段と、
前記第１の距離を使用してタイミング制約条件が満たされているかどうかを検証する手段と、
前記回路の設計に応じて前記駆動素子と前記負荷素子との間の、前記第１の距離よりも長い第２の距離を推定する手段と、
前記第２の距離を使用してタイミング制約条件が満たされているかどうかを判定する手段とを備えるデータ処理システム。
【請求項７０】
前記第１の距離は第１の経路トポロジに従い、前記第２の距離は第２の経路トポロジに従う請求項６９に記載のデータ処理システム。
【請求項７１】
さらに、
前記第２の距離が使用される場合にタイミング制約条件が満たされていないと判定したことに対する応答として、前記回路の前記設計に対して変換を実行して、設計コスト関数を悪化させずに前記第２の距離を短縮することができるかどうかを判定する手段を備える請求項６９に記載のデータ処理システム。
【請求項７２】
前記変換は、
前記駆動素子を複製すること、
前記駆動素子をサイズアップすること、
前記駆動素子と前記負荷素子との間にバッファ素子を挿入することと、
前記駆動素子と前記駆動素子の負荷素子のうちの少なくとも１つの素子の配置を調整することのうちの少なくとも１つを含む請求項７１に記載のデータ処理システム。
【請求項７３】
前記第２の距離は、前記駆動素子と前記負荷素子を接続するネットが経路トポロジの感度の低減のため選択された場合にのみ推定される請求項６９に記載のデータ処理システム。
【請求項７４】
前記ネットは、前記ネットがタイミング・クリティカルまたはクリティカルに近いパス上にあり、前記ネットのファンアウトの個数が２よりも多い場合にのみ、選択される請求項７３に記載のデータ処理システム。
【請求項７５】
前記ネットは、さらに、前記駆動素子の負荷素子を囲む境界ボックスの縦横比に応じてさらに選択される請求項７４に記載のデータ処理システム。
【請求項７６】
パス遅延を推定するためのデータ処理システムであって、
駆動素子と、
前記駆動素子の複数の負荷素子との領域の形状を決定する手段と、
前記領域の形状に少なくとも基づき前記駆動素子と前記複数の負荷素子のうちの第１の素子との間の距離を推定する手段を備えるデータ処理システム。
【請求項７７】
前記領域の前記形状を決定する前記手段は、
前記複数の負荷素子を囲む境界ボックスを決定する手段を含み、
前記距離は、少なくとも前記境界ボックスに基づいて推定される請求項７６に記載のデータ処理システム。
【請求項７８】
前記推定する手段は、
前記駆動素子と前記複数の負荷素子のうちの前記第１の素子との間のマンハッタン距離を決定する手段を含み、
前記距離は、前記マンハッタン距離と前記境界ボックスの短い辺の長さの関数として推定される請求項７７に記載のデータ処理システム。
【請求項７９】
前記境界ボックスは矩形である請求項７８に記載のデータ処理システム。
【請求項１】
回路の設計の後の配線実装時に設計制約条件に違反する可能性があるかどうかを判定することと、
前記設計の後の配線実装で前記設計制約条件に違反する可能性を低減するように前記回路の前記設計を修正することと
を含む回路を設計する方法。
【請求項２】
前記設計のその後の配線実装時に前記設計制約条件に違反する可能性は、経路トポロジを推定する際の不確定性によるものである請求項１に記載の方法。
【請求項３】
前記設計のその後の配線実装時に前記設計制約条件に違反する可能性は、経路トポロジのパラメータを推定する際の不確定性による請求項１に記載の方法。
【請求項４】
さらに、
前記回路の前記設計における経路トポロジが、前記設計制約条件に関連するパラメータを決定する際に精度の低下を引き起こすかどうかを判定することを含む請求項３に記載の方法。
【請求項５】
前記設計のその後の配線実装時に前記設計制約条件に違反する可能性があるかどうかは、少なくとも駆動素子の負荷素子を囲む境界ボックスに基づいて判定される請求項１に記載の方法。
【請求項６】
前記設計のその後の配線実装時に前記設計制約条件に違反する可能性があるかどうかは、タイミング・クリティカルまたはクリティカルに近いパス上のネットのファンアウトの個数にさらに基づいて判定され、前記ネットは、前記駆動素子を前記負荷素子に接続する請求項５に記載の方法。
【請求項７】
前記修正することは、
第１の駆動素子を複製して、第２の駆動素子を挿入することと、
前記第１の駆動素子の負荷素子の一部を前記第２の駆動素子の負荷素子として再接続することとを含む請求項１に記載の方法。
【請求項８】
前記修正することは、
バッファ素子を第１の駆動素子の負荷素子として挿入することと、
前記第１の駆動素子の負荷素子の一部を前記バッファ素子の負荷素子として再接続することとを含む請求項１に記載の方法。
【請求項９】
前記修正することは、
駆動素子の負荷素子の配置を再配列して前記駆動素子と前記負荷素子の境界ボックスの短い辺と長い辺との比を低減することを含む請求項１に記載の方法。
【請求項１０】
前記修正することは、
第１の素子の負荷素子の一部を第２の素子の負荷素子として変換することを含む請求項１に記載の方法。
【請求項１１】
前記設計制約条件は、タイミング制約条件を含む請求項１に記載の方法。
【請求項１２】
前記タイミング制約条件は、
ａ）前記回路の最悪ネガティブ・スラック、
ｂ）前記回路の前記設計内の論理素子のインスタンスに対するスラック、
ｃ）前記回路の前記設計内のパス上の遅延、
ｄ）前記回路のトータル・ネガティブ・スラックのうちの１つを含む請求項１１に記載の方法。
【請求項１３】
前記設計制約条件は設計規則を含む請求項１に記載の方法。
【請求項１４】
前記設計規則は、
ａ）最大静電容量、および
ｂ）駆動素子と負荷素子との間の最大配線長のうちの１つを含む請求項１３に記載の方法。
【請求項１５】
前記修正することは、
代替経路トポロジが使用される場合に前記設計制約条件の違反をそれぞれ引き起こす可能性がある多数のネット候補を判別することと、
前記多数のネット候補の部分集合について前記設計を選択的に修正することとを含む請求項１に記載の方法。
【請求項１６】
前記選択的に修正することは、
流れに従って前記多数のネット候補から１つを選択し、前記流れはネット候補を通る多数のパスの重み付きカウントを表すことを含む請求項１５に記載の方法。
【請求項１７】
前記多数のパスは、
前記ネット候補を通るすべてのパス、
前記ネット候補を通るすべてのネガティブ・スラック・パス、
前記ネット候補を通る輻輳パス、
前記ネット候補を通る敏感なネットを含むパスのうちの１つである請求項１６に記載の方法。
【請求項１８】
前記選択的に修正することは、
修正する前記部分集合を決定するために前記多数のネット候補を含むグラフに対し最小カットを実行することを含む請求項１５に記載の方法。
【請求項１９】
回路を設計する機械実装方法であって、
前記回路の設計に応じて駆動素子と前記駆動素子の負荷素子との間の第１の距離を推定することと、
前記第１の距離を使用してタイミング制約条件が満たされているかどうかを検証することと、
前記回路の設計に応じて前記駆動素子と前記負荷素子との間の、前記第１の距離よりも長い第２の距離を推定することと、
前記第２の距離を使用してタイミング制約条件が満たされているかどうかを判定することとを含む機械実装方法。
【請求項２０】
前記第１の距離は第１の経路トポロジに従い、前記第２の距離は第２の経路トポロジに従う請求項１９に記載の方法。
【請求項２１】
さらに、
前記第２の距離が使用される場合にタイミング制約条件が満たされていないと判定したことに対する応答として、前記回路の前記設計に対して変換を実行して、設計コスト関数を悪化させずに前記第２の距離を短縮することができるかどうかを判定することを含む請求項１９に記載の方法。
【請求項２２】
前記変換は、
前記駆動素子を複製すること、
前記駆動素子をサイズアップすること、
前記駆動素子と前記負荷素子との間にバッファ素子を挿入することと、
前記駆動素子と前記駆動素子の負荷素子のうちの少なくとも１つの素子の配置を調整することのうちの少なくとも１つを含む請求項２１に記載の方法。
【請求項２３】
前記第２の距離は、前記駆動素子と前記負荷素子を接続するネットが経路トポロジの感度の低減のため選択された場合にのみ推定される請求項１９に記載の方法。
【請求項２４】
前記ネットは、前記ネットがタイミング・クリティカルまたはクリティカルに近いパス上にあり、前記ネットのファンアウトの個数が２よりも多い場合にのみ、選択される請求項２３に記載の方法。
【請求項２５】
前記ネットは、さらに、前記駆動素子の負荷素子を囲む境界ボックスの縦横比に応じてさらに選択される請求項２４に記載の方法。
【請求項２６】
パス遅延を推定する機械実装方法であって、
駆動素子と、その駆動素子の複数の負荷素子との領域の形状を決定することと、
前記領域の形状に少なくとも基づき前記駆動素子と前記複数の負荷素子のうちの第１の素子との間の距離を推定すること
を含む機械実装方法。
【請求項２７】
前記領域の前記形状の前記決定は、
前記複数の負荷素子を囲む境界ボックスを決定することを含み、
前記距離は、少なくとも前記境界ボックスに基づいて推定される請求項２６に記載の方法。
【請求項２８】
前記推定することは、
前記駆動素子と前記複数の負荷素子のうちの前記第１の素子との間のマンハッタン距離を決定することを含み、
前記距離は、前記マンハッタン距離と前記境界ボックスの短い辺の長さの関数として推定される請求項２７に記載の方法。
【請求項２９】
前記境界ボックスは矩形である請求項２８に記載の方法。
【請求項３０】
データ処理システムにより実行された場合に回路を設計する方法を前記システムに実行させる実行可能コンピュータ・プログラム命令を格納する機械可読媒体であって、前記実行方法は、
前記回路の設計の後の配線実装時に設計制約条件に違反する可能性があるかどうかを判定することと、
前記設計の後の配線実装で前記設計制約条件に違反する可能性を低減するように前記回路の前記設計を修正することと
を含む機械可読媒体。
【請求項３１】
前記設計のその後の配線実装時に前記設計制約条件に違反する可能性は、経路トポロジを推定する際の不確定性による請求項３０に記載の媒体。
【請求項３２】
前記設計のその後の配線実装時に前記設計制約条件に違反する可能性があるかどうかは、少なくとも駆動素子の負荷素子を囲む境界ボックスに基づいて判定される請求項３０に記載の媒体。
【請求項３３】
前記設計のその後の配線実装時に前記設計制約条件に違反する可能性があるかどうかは、タイミング・クリティカルまたはクリティカルに近いパス上のネットのファンアウトの個数にさらに基づいて判定され、前記ネットは、前記駆動素子を前記負荷素子に接続するものである請求項３２に記載の媒体。
【請求項３４】
前記修正することは、
第１の駆動素子を複製して、第２の駆動素子を挿入することと、
前記第１の駆動素子の負荷素子の一部を前記第２の駆動素子の負荷素子として再接続することとを含む請求項３０に記載の媒体。
【請求項３５】
前記修正することは、
バッファ素子を第１の駆動素子の負荷素子として挿入することと、
前記第１の駆動素子の負荷素子の一部を前記バッファ素子の負荷素子として再接続することとを含む請求項３０に記載の媒体。
【請求項３６】
前記修正することは、
駆動素子の負荷素子の配置を再配列して前記駆動素子と前記負荷素子の境界ボックスの短い辺と長い辺との比を低減することを含む請求項３０に記載の媒体。
【請求項３７】
前記修正することは、
第１の素子の負荷素子の一部を第２の素子の負荷素子として変換することを含む請求項３０に記載の媒体。
【請求項３８】
前記設計制約条件は、タイミング制約条件を含む請求項３０に記載の媒体。
【請求項３９】
前記タイミング制約条件は、
ａ）前記回路の最悪ネガティブ・スラック、
ｂ）前記回路の前記設計内の論理素子のインスタンスに対するスラック、
ｃ）前記回路の前記設計内のパス上の遅延、
ｄ）前記回路のトータル・ネガティブ・スラックのうちの１つを含む請求項３８に記載の媒体。
【請求項４０】
前記修正することは、
代替経路トポロジが使用される場合に前記設計制約条件の違反をそれぞれ引き起こす可能性がある多数のネット候補を判別することと、
前記多数のネット候補の部分集合について前記設計を選択的に修正することとを含む請求項３０に記載の媒体。
【請求項４１】
前記選択的に修正することは、
流れに従って前記多数のネット候補から１つを選択し、前記流れはネット候補を通る多数のパスの重み付きカウントを表すことを含む請求項４０に記載の媒体。
【請求項４２】
前記多数のパスは、
前記ネット候補を通るすべてのパス、
前記ネット候補を通るすべてのネガティブ・スラック・パス、
前記ネット候補を通る輻輳パス、
前記ネット候補を通る敏感なネットを含むパスのうちの１つである請求項４１に記載の媒体。
【請求項４３】
前記選択的に修正することは、
修正する前記部分集合を決定するために前記多数のネット候補を含むグラフに対し最小カットを実行することを含む請求項４０に記載の媒体。
【請求項４４】
データ処理システムにより実行された場合に回路を設計する方法を前記システムに実行させる実行可能コンピュータ・プログラム命令を格納する機械可読媒体であって、前記実行方法は、
前記回路の設計に応じて駆動素子と前記駆動素子の負荷素子との間の第１の距離を推定することと、
前記第１の距離を使用してタイミング制約条件が満たされているかどうかを検証することと、
前記回路の設計に応じて前記駆動素子と前記負荷素子との間の、前記第１の距離よりも長い第２の距離を推定することと、
前記第２の距離を使用してタイミング制約条件が満たされているかどうかを判定することとを含む機械可読媒体。
【請求項４５】
前記第１の距離は第１の経路トポロジに従い、前記第２の距離は第２の経路トポロジに従う請求項４４に記載の媒体。
【請求項４６】
前記方法は、さらに、
前記第２の距離が使用される場合にタイミング制約条件が満たされていないと判定したことに対する応答として、前記回路の前記設計に対して変換を実行して、設計コスト関数を悪化させずに前記第２の距離を短縮することができるかどうかを判定することを含む請求項４４に記載の媒体。
【請求項４７】
前記変換は、
前記駆動素子を複製すること、
前記駆動素子をサイズアップすること、
前記駆動素子と前記負荷素子との間にバッファ素子を挿入することと、
前記駆動素子と前記駆動素子の負荷素子のうちの少なくとも１つの素子の配置を調整することのうちの少なくとも１つを含む請求項４６に記載の媒体。
【請求項４８】
前記第２の距離は、前記駆動素子と前記負荷素子を接続するネットが経路トポロジの感度の低減のため選択された場合にのみ推定される請求項４４に記載の媒体。
【請求項４９】
前記ネットは、前記ネットがタイミング・クリティカルまたはクリティカルに近いパス上にあり、前記ネットのファンアウトの個数が２よりも多い場合にのみ、選択される請求項４８に記載の媒体。
【請求項５０】
前記ネットは、さらに、前記駆動素子の負荷素子を囲む境界ボックスの縦横比に応じてさらに選択される請求項４９に記載の媒体。
【請求項５１】
データ処理システムにより実行された場合にパス遅延を推定する方法を前記システムに実行させる実行可能コンピュータ・プログラム命令を格納する機械可読媒体であって、前記実行方法は、
駆動素子と、前記駆動素子の複数の負荷素子との領域の形状を決定することと、
前記領域の形状に少なくとも基づき前記駆動素子と前記複数の負荷素子のうちの第１の素子との間の距離を推定することを含む機械可読媒体。
【請求項５２】
前記領域の前記形状の前記決定は、
前記複数の負荷素子を囲む境界ボックスを決定することを含み、
前記距離は、少なくとも前記境界ボックスに基づいて推定される請求項５１に記載の媒体。
【請求項５３】
前記推定することは、
前記駆動素子と前記複数の負荷素子のうちの前記第１の素子との間のマンハッタン距離を決定することを含み、
前記距離は、前記マンハッタン距離と前記境界ボックスの短い辺の長さの関数として推定される請求項５２に記載の媒体。
【請求項５４】
前記境界ボックスは矩形である請求項５３に記載の媒体。
【請求項５５】
回路を設計するためのデータ処理システムであって、
前記回路の設計の後の配線実装時に設計制約条件に違反する可能性があるかどうかを判定する手段と、
前記設計の後の配線実装で前記設計制約条件に違反する可能性を低減するように前記回路の前記設計を修正する手段とを備えるデータ処理システム。
【請求項５６】
前記設計のその後の配線実装時に前記設計制約条件に違反する可能性は、経路トポロジを推定する際の不確定性による請求項５５に記載のデータ処理システム。
【請求項５７】
前記設計のその後の配線実装時に前記設計制約条件に違反する可能性があるかどうかは、少なくとも駆動素子の負荷素子を囲む境界ボックスに基づいて判定される請求項５５に記載のデータ処理システム。
【請求項５８】
前記設計のその後の配線実装時に前記設計制約条件に違反する可能性があるかどうかは、タイミング・クリティカルまたはクリティカルに近いパス上のネットのファンアウトの個数にさらに基づいて判定され、前記ネットは、前記駆動素子を前記負荷素子に接続するものである請求項５７に記載のデータ処理システム。
【請求項５９】
前記修正する手段は、
第１の駆動素子を複製して、第２の駆動素子を挿入する手段と、
前記第１の駆動素子の負荷素子の一部を前記第２の駆動素子の負荷素子として再接続する手段とを備える請求項５５に記載のデータ処理システム。
【請求項６０】
前記修正する手段は、
バッファ素子を第１の駆動素子の負荷素子として挿入する手段と、
前記第１の駆動素子の負荷素子の一部を前記バッファ素子の負荷素子として再接続する手段とを備える請求項５５に記載のデータ処理システム。
【請求項６１】
前記修正する手段は、
駆動素子の負荷素子の配置を再配列して前記駆動素子と前記負荷素子の境界ボックスの短い辺と長い辺との比を低減する手段を備える請求項５５に記載のデータ処理システム。
【請求項６２】
前記修正する手段は、
第１の素子の負荷素子の一部を第２の素子の負荷素子として変換する手段を備える請求項５５に記載のデータ処理システム。
【請求項６３】
前記設計制約条件は、タイミング制約条件を含む請求項５５に記載のデータ処理システム。
【請求項６４】
前記タイミング制約条件は、
ａ）前記回路の最悪ネガティブ・スラック、
ｂ）前記回路の前記設計内の論理素子のインスタンスに対するスラック、
ｃ）前記回路の前記設計内のパス上の遅延、
ｄ）前記回路のトータル・ネガティブ・スラックのうちの１つを含む請求項６３に記載のデータ処理システム。
【請求項６５】
前記修正する手段は、
代替経路トポロジが使用される場合に前記設計制約条件の違反をそれぞれ引き起こす可能性がある多数のネット候補を判別する手段と、
前記多数のネット候補の部分集合について前記設計を選択的に修正する手段とを備える請求項５５に記載のデータ処理システム。
【請求項６６】
前記選択的に修正する手段は、
流れに従って前記多数のネット候補から１つを選択し、前記流れはネット候補を通る多数のパスの重み付きカウントを表す手段を備える請求項６５に記載のデータ処理システム。
【請求項６７】
前記多数のパスは、
前記ネット候補を通るすべてのパス、
前記ネット候補を通るすべてのネガティブ・スラック・パス、
前記ネット候補を通る輻輳パス、
前記ネット候補を通る敏感なネットを含むパスのうちの１つである請求項６６に記載のデータ処理システム。
【請求項６８】
前記選択的に修正する手段は、
修正する前記部分集合を決定するために前記多数のネット候補を含むグラフに対し最小カットを実行する手段を備える請求項６５に記載のデータ処理システム。
【請求項６９】
回路を設計するためのデータ処理システムであって、
前記回路の設計に応じて駆動素子と前記駆動素子の負荷素子との間の第１の距離を推定する手段と、
前記第１の距離を使用してタイミング制約条件が満たされているかどうかを検証する手段と、
前記回路の設計に応じて前記駆動素子と前記負荷素子との間の、前記第１の距離よりも長い第２の距離を推定する手段と、
前記第２の距離を使用してタイミング制約条件が満たされているかどうかを判定する手段とを備えるデータ処理システム。
【請求項７０】
前記第１の距離は第１の経路トポロジに従い、前記第２の距離は第２の経路トポロジに従う請求項６９に記載のデータ処理システム。
【請求項７１】
さらに、
前記第２の距離が使用される場合にタイミング制約条件が満たされていないと判定したことに対する応答として、前記回路の前記設計に対して変換を実行して、設計コスト関数を悪化させずに前記第２の距離を短縮することができるかどうかを判定する手段を備える請求項６９に記載のデータ処理システム。
【請求項７２】
前記変換は、
前記駆動素子を複製すること、
前記駆動素子をサイズアップすること、
前記駆動素子と前記負荷素子との間にバッファ素子を挿入することと、
前記駆動素子と前記駆動素子の負荷素子のうちの少なくとも１つの素子の配置を調整することのうちの少なくとも１つを含む請求項７１に記載のデータ処理システム。
【請求項７３】
前記第２の距離は、前記駆動素子と前記負荷素子を接続するネットが経路トポロジの感度の低減のため選択された場合にのみ推定される請求項６９に記載のデータ処理システム。
【請求項７４】
前記ネットは、前記ネットがタイミング・クリティカルまたはクリティカルに近いパス上にあり、前記ネットのファンアウトの個数が２よりも多い場合にのみ、選択される請求項７３に記載のデータ処理システム。
【請求項７５】
前記ネットは、さらに、前記駆動素子の負荷素子を囲む境界ボックスの縦横比に応じてさらに選択される請求項７４に記載のデータ処理システム。
【請求項７６】
パス遅延を推定するためのデータ処理システムであって、
駆動素子と、
前記駆動素子の複数の負荷素子との領域の形状を決定する手段と、
前記領域の形状に少なくとも基づき前記駆動素子と前記複数の負荷素子のうちの第１の素子との間の距離を推定する手段を備えるデータ処理システム。
【請求項７７】
前記領域の前記形状を決定する前記手段は、
前記複数の負荷素子を囲む境界ボックスを決定する手段を含み、
前記距離は、少なくとも前記境界ボックスに基づいて推定される請求項７６に記載のデータ処理システム。
【請求項７８】
前記推定する手段は、
前記駆動素子と前記複数の負荷素子のうちの前記第１の素子との間のマンハッタン距離を決定する手段を含み、
前記距離は、前記マンハッタン距離と前記境界ボックスの短い辺の長さの関数として推定される請求項７７に記載のデータ処理システム。
【請求項７９】
前記境界ボックスは矩形である請求項７８に記載のデータ処理システム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【公表番号】特表２００７−５２５７３５（Ｐ２００７−５２５７３５Ａ）
【公表日】平成１９年９月６日（２００７．９．６）
【国際特許分類】
【出願番号】特願２００６−５１５０００（Ｐ２００６−５１５０００）
【出願日】平成１６年５月２８日（２００４．５．２８）
【国際出願番号】ＰＣＴ／ＵＳ２００４／０１６８４２
【国際公開番号】ＷＯ２００４／１１１８９１
【国際公開日】平成１６年１２月２３日（２００４．１２．２３）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．Ｍａｃｉｎｔｏｓｈ
【出願人】（３０００５６４４０）シンプリシティ・インコーポレーテッド (5)
【Ｆターム（参考）】
【公表日】平成１９年９月６日（２００７．９．６）
【国際特許分類】
【出願日】平成１６年５月２８日（２００４．５．２８）
【国際出願番号】ＰＣＴ／ＵＳ２００４／０１６８４２
【国際公開番号】ＷＯ２００４／１１１８９１
【国際公開日】平成１６年１２月２３日（２００４．１２．２３）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．Ｍａｃｉｎｔｏｓｈ
【出願人】（３０００５６４４０）シンプリシティ・インコーポレーテッド (5)
【Ｆターム（参考）】
[ Back to top ]