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