(57)【特許請求の範囲】
【請求項１】
電子回路記述に基づいて、セルを含むセルライブラリを使用することによりコンピュータによりデジタル回路の最初の集積回路レイアウトを設計する自動化された方法において、
（ａ）セルライブラリから複数のワイヤによって互いに結合されるように意図され、選択された複数のセルを得るためにコンピュータに入力された電子回路記述に基づいたデジタル回路を構成するために使用することのできる複数のセルを選択し、それらの選択された複数のセルの幾つかのものは、予め定められたタイミング制約に確実に合致するために関連した最初の意図されている遅延を有しており、
（ｂ）コンピュータプログラムからの命令のシーケンスを使用して選択された複数のセルおよびそれに結合されているワイヤの配置を決定し、
（ｃ）前記幾つかのセルの面積を決定し、
それらの各セルの面積は、それらのセルのそれぞれに結合されたワイヤの長さを使用して、それらの各セルの最初に意図された遅延が実現されるように決定され、各ワイヤの長さはそのワイヤに結合されたセルの配置によって決定されることを特徴とする集積回路レイアウトの自動化された設計方法。
【請求項２】
集積回路レイアウトを生成するようにデジタル回路のルートを設定する請求項１記載の方法。
【請求項３】
ルート設定に先立って、選択された複数のセルのそれぞれの面積、配置、およびワイヤ長を最終化する請求項２記載の方法。
【請求項４】
複数のセルは、コンピュータに入力された電子回路記述に基づいて互いに結合される請求項１記載の方法。
【請求項５】
複数のワイヤはそれぞれ関連する容量性負荷値を有し、
各ワイヤは、ワイヤの関連する容量性負荷値に関して前記ステップ（ａ）のデジタル回路の全面積の感度を表わすネット加重値と関連している請求項１記載の方法。
【請求項６】
選択されたセルに結合されたワイヤのネット加重値ｗi は、
【数１】
0004594519.tif 000007
ここでＡはステップ（ａ）のデジタル回路の全面積であり、Ｃi は選択されたセルに結合されたワイヤの関連する容量性負荷である請求項５記載の方法。
【請求項７】
選択された幾つかのセルの決定された面積は、予め定められたタイミング制約に合致するためにネット加重値ｗi とネット負荷Ｃi との積に基づいて選択される請求項６記載の方法。
【請求項８】
選択されたセルはそれと関連した最初に意図した遅延を有している請求項１記載の方法。
【請求項９】
決定するステップでは選択されたセルの全ての面積を決定する請求項１記載の方法。
【請求項１０】
配置を決定するステップ後で面積を決定するステップ前にワイヤの１つにバッファを挿入する請求項１記載の方法。
【請求項１１】
予め定められたタイミング制約に合致しながらバッファが挿入されることができるワイヤを決定し、
挿入により面積が節約される場合にはそのワイヤ中にバッファを挿入する請求項１０記載の方法。
【請求項１２】
配置を決定するステップ後で面積を決定するステップ前に選択されたセルの面積を減少させるために選択されたセルの最初に意図した遅延を伸長する請求項１記載の方法。
【請求項１３】
配置を決定するステップ後で面積を決定するステップ前に結合されたセルのそれぞれの面積を減少させるために互いに結合された複数の選択されたセルの関連する相対的遅延値を引伸ばす請求項１記載の方法。
【請求項１４】
配置を決定するステップ後で面積を決定するステップ前に選択されたセルの最初に意図した遅延を圧縮する請求項１記載の方法。
【請求項１５】
さらに、圧縮するステップは選択されたセルの利得要求によって制限される請求項１４記載の方法。
【請求項１６】
さらに、配置を決定するステップ後で面積を決定するステップ前に選択された複数のセルの最初に意図した遅延を圧縮する請求項１記載の方法。
【請求項１７】
前記幾つかのセルのグループはバケット中に割当てられ、動作する請求項１記載の方法。
【請求項１８】
前記幾つかのセルのグループは２０乃至２００個のセルである請求項１７記載の方法。
【請求項１９】
請求項１記載の方法によって製造された集積回路レイアウト。
【請求項２０】
電子回路記述に基づいて、セルライブラリから選択されたセルに基づいてコンピュータを使用して集積回路レイアウトを設計する自動化された方法において、
（ａ）セルがワイヤによって互いに結合されて関連する予め定められた遅延制約を有する回路パスを形成するように集積回路レイアウト中にセルおよびそれと関連するワイヤを配置し、セルはコンピュータに入力された電子回路記述に基づいてワイヤにより結合され、電子回路記述は各セルと関連している最初に意図した遅延を含んでおり、
（ｂ）回路パスの予め定められた遅延制約を満足させるために少なくとも１つのセルの面積を決定し、このセルの面積は、最初に意図した遅延が実現されるように前記セルに結合されているワイヤの入力キャパシタンスと出力キャパシタンスとの比の関数として定められていることを特徴とする集積回路レイアウトの自動化された設計方法。
【請求項２１】
各ワイヤは関係する容量性負荷値を有し、
各ワイヤは、ワイヤの関係する容量性負荷値に関する集積回路レイアウトの全体面積の感度を表わすネット加重値と関連している請求項２０記載の方法。
【請求項２２】
セルに結合されたワイヤのネット加重値ｗi は、
【数２】
0004594519.tif 000008
であり、ここでＡは集積回路レイアウトの全面積であり、Ｃi はセルに結合されたワイヤの関連する容量性負荷である請求項２１記載の方法。
【請求項２３】
少なくとも幾つかのセルの面積は、予め定められたタイミング制約に合致するためにネット加重値ｗi とネット負荷値Ｃi との積に基づいて選択される請求項２２記載の方法。
【請求項２４】
各ワイヤの長さはそのワイヤに結合されたセルの配置によって決定される請求項２３記載の方法。
【請求項２５】
各ワイヤの長さはそのワイヤに結合されたセルの配置によって決定される請求項２０記載の方法。
【請求項２６】
さらに、配置を決定するステップ後で面積を決定するステップ前にワイヤの１つにバッファを挿入する請求項２０記載の方法。
【請求項２７】
さらに、配置を決定するステップ後で面積を決定するステップ前に選択されたセルの関連する相対的遅延値を伸長する請求項２０記載の方法。
【請求項２８】
さらに、配置を決定するステップ後で面積を決定するステップ前に選択されたセルの関連する相対的遅延値を圧縮する請求項２０記載の方法。
【請求項２９】
圧縮するステップは選択されたセルの利得要求によって制限される請求項２８記載の方法。
【請求項３０】
決定ステップは選択されたセルの全ての面積を決定する請求項２０記載の方法。
【請求項３１】
デジタル回路についての情報を含んでいる電子回路記述に基づいてコンピュータを使用して複数のワイヤによって互いに結合された４以上のセルのデジタル回路の集積回路レイアウトを設計する自動化された方法において、
（ａ）電子回路記述に基づいてデジタル回路を構成するために使用することができる複数のセルを選択し、それら複数のセルはそれぞれ関連する負荷およびそれと関連する予め定められたタイミング制約に合致する最初に意図した遅延を有し、選択された複数のセルは、少なくとも第１の負荷を有する第１のセルと、第２の負荷を有する第２のセルと、第３の負荷を有する第３のセルと、第４の負荷を有する第４のセルとを含み、
（ｂ）第１のセルと、第２のセルと、第３のセルと、第４のセルとを含む選択された複数のセルのそれぞれに対して最初の設置位置を決定し、
（ｃ）予め定められたタイミング制約に合致するように選択された複数のセルのサイズおよび各セルの負荷を設定し、各セルのサイズは最初に意図した遅延が実現されるように各セルに結合されたワイヤの長さを使用して決定され、各ワイヤの長さはそのワイヤに結合されたセルの配置によって決定されることを特徴とする集積回路レイアウトの自動化された設計方法。
【請求項３２】
各負荷は関係する容量性負荷値を有し、
各負荷は、その負荷の関係する容量性負荷値に関する集積回路レイアウトの全体面積の感度を表わすネット加重値と関連している請求項３１記載の方法。
【請求項３３】
セルに結合された負荷のネット加重値ｗi は、
【数３】
0004594519.tif 000009
であり、ここでＡは集積回路レイアウトの全面積であり、Ｃi はセルに結合された負荷の関連する容量性負荷である請求項３２記載の方法。
【請求項３４】
少なくとも幾つかのセルの面積は、予め定められたタイミング制約に合致するためにネット加重値ｗi とネット負荷値Ｃi との積に基づいて選択される請求項３３記載の方法。
【請求項３５】
選択された幾つかのセルの面積は、前記選択された幾つかのセルに結合された負荷のネット負荷値ｗi および前記選択されたセルに結合された負荷の長さに基づいて選択される請求項３４記載の方法。
【請求項３６】
請求項３１記載の方法によって製造された集積回路レイアウト。
【請求項３７】
デジタル回路についての情報を含んでいる電子回路記述に基づいてコンピュータを使用して４以上のセルのデジタル回路の集積回路レイアウトを決定する自動化された方法において、
（ａ）電子回路記述を使用してデジタル回路を構成するために使用することができる複数のセルを選択し、それら複数のセルは第１の負荷および第１の最初に意図した遅延を有する第１のセルと、第１のセルに接続され第２の負荷および第２の最初に意図した遅延を有する第２のセルと、第２のセルに接続され第３の負荷および第３の最初に意図した遅延を有する第３のセルと、第３のセルに接続され第４の負荷および第４の最初に意図した遅延を有する第４のセルとを含んでおり、デジタル回路は予め定められたタイミング制約を有しており、
（ｂ）第１のセルと、第２のセルと、第３のセルと、第４のセルとを含む選択された複数のセルのそれぞれに対して配置位置を決定し、
（ｃ）第１の最初に意図した遅延が実現されるように第１のセルの第１の負荷に基づいて第１のセルのサイズを選択し、第１のセルのサイズは第１のセルに結合されたワイヤの長さを使用して決定され、各ワイヤの長さはそのワイヤに結合されたセルの配置によって決定され、
（ｄ）第２の最初に意図した遅延が実現されるように第２のセルの第２の負荷に基づいて第２のセルのサイズを選択し、第２のセルのサイズは第２のセルに結合されたワイヤの長さを使用して決定され、各ワイヤの長さはそのワイヤに結合されたセルの配置によって決定され、
（ｅ）第３の最初に意図した遅延が実現されるように第３のセルの第３の負荷に基づいて第３のセルのサイズを選択し、第３のセルのサイズは第３のセルに結合されたワイヤの長さを使用して決定され、各ワイヤの長さはそのワイヤに結合されたセルの配置によって決定され、
（ｆ）第４の最初に意図した遅延が実現されるように第４のセルの第４の負荷に基づいて第４のセルのサイズを選択し、第４のセルのサイズは第４のセルに結合されたワイヤの長さを使用して決定され、各ワイヤの長さはそのワイヤに結合されたセルの配置によって決定され、
第１、第２、第３、第４のセルの面積の選択によってそれと関連する予め定められたタイミング制約が確実に満足されることを特徴とする集積回路レイアウトの自動化された決定方法。
【請求項３８】
請求項３７記載の方法によって製造された集積回路レイアウト。
【請求項３９】
さらに、デジタル回路の経路を設定するステップを含んでいる請求項３７記載の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、一般的に集積回路設計の技術分野に関するものであり、特に、デジタル回路設計におけるタイミング制約を満足させる方法に関する。
【０００２】
【従来の技術】
電子回路およびシステムの設計においてコンピュータ自動化設計システムが種々のプロトタイプの回路形態を決定し、検証するために使用されている。回路決定の一部として遅延制約が回路設計者によって特定される。これらの遅延制約はプロトタイプの回路が製造されるときに満足されなければならない。
【０００３】
通常の回路設計方法においては、典型的に次のようなステップが行われる：
（１）回路中の各セルに対する負荷キャパシタンスはファーンアウトベースのモデルを使用して評価される。
（２）各セルの大きさは回路のタイミングを最適にするように設定される。
（３）セルが配置され、回路のネット（ワイヤ）長が評価される。
（４）ワイヤが所定経路で導かれる。
（５）最終解析によってタイミング閉鎖（すなわちタイミング制約の満足度）が達成されたか否かの決定が行われる。
【０００４】
ステップ（２）において、回路内のセルの大きさが選択され、一度選択されると一定に保持される。その後使用される配置アルゴリズムは，セル間の異なったネット長を割当て、これらのネット長は通常配置に先立つて予測することは困難である。ネット長は、ファーンアウトゲートの数に基づいたネットの負荷値を与える評価関数またはテーブルを使用することによって配置に先立つて評価されるが、この評価関数は通常不正確である。このようにネット長を正確に予測することが困難であることによって、配置が行われた後で予測できない遅延の影響が生じる。例えば、いくつかのネットは予期されたよりも結果的に長くなる。これらの長いネットは長い遅延を生じてデジタル回路のタイミング制約を満足させることができなくなる。したがって、通常の設計方法では、タイミング閉鎖は配置後まで確定されない。
【０００５】
配置後にタイミング閉鎖を達成することに失敗すると、価格が増加し、設計者に対して別の問題を提起する。タイミング閉鎖を達成するために失敗を修正するには、設計者は手作業で設計を固定するオプションを有するが、自動化された最適化されたデジタルネットワークは容易に理解することができないために、それは困難で時間を要する作業である。第２のオプションとして設計者はハードウェア言語（ＨＤＬ）明細を変更して設計プロセスを反復することができる。しかしながら、この場合にもタイミング閉鎖は配置後まで確定されない。したがって設計プロセスは、ＨＤＬ明細変更がタイミング閉鎖をエネーブルするのに成功したことを設計者が決定する前に反復されなければならない。
【０００６】
【発明が解決しようとする課題】
不正確なネット負荷評価を処理する通常の方法は、典型的に評価されたよりもかなり大きい値でネット負荷を評価することによるものである。この方法は配置後のタイミング制約に合致する可能性を増加させるが、ゲートの大きさを必要以上に著しく増加させる。必要以上に大きいゲートはシリコンウエハの面積を無駄にし、また無駄な電力消費を生じる。それはまたチップを大きくして製造価格を増加させ、必要以上に電力を使用する結果をもたらす。
【０００７】
通常の回路設計方法の別の問題は、最適化中および配置中に必要となるタイミング解析に関するものである。通常の回路設計プロセスを通じて行われるタイミング解析は非常に時間がかかり、通常の回路設計システムの動作時間の大部分について考慮しなければならない。
【０００８】
通常の回路設計方法のさらに別の欠点は、配置プログラムにより行われるネット長の変更に関するものである。各ゲートに対して選択された位置に応じて、各ネット長が修正されなければならない。各ネット長が修正されるとき、ネットの容量性負荷は変化する。その結果、ネットを駆動するゲートの遅延が変化する。それ故、論理設計中に注意深く最適化された遅延はセルの配置後に値が大きく異なったものとなり、それによってネットワークの最適化を低下させる影響を与える。
【０００９】
さらに、デジタル回路設計に対する現在の技術における進歩の多くは集積度の増加によって特徴付けられ、それはソフトウェアシステムの複雑さを増加させ、それは速度が遅く、設計および保守が困難である。
【００１０】
通常の回路設計方法のさらに別の欠点は、配置と寸法決定の反復が必要であることである。それは論理合成プログラムはしばしばＨＤＬ明細を書いた論理設計者によって動作されるが、配置プログラムは設計が完成した後でシリコンチップの製造業者によって動作されることが多いからである。
【００１１】
一定の遅延を維持しながら、ゲート負荷の線形関数として大きさを表わす１つの提案が成されている。例えばＪ．Ｇrodstein，Ｅ．Ｌehmab ，Ｈ．Ｈarkness ，Ｂ．Ｇrundmann，およびＹ．ワタナベの“Ａ  Ｄelay  Ｍodel for  Ｌogic  Ｓ ynthesis of  Ｃontinuously-Ｓized  Ｎetwork”，Ｄigest ＩNT. ＣONF.onＣomputer Ａided  Ｄesign ，458 〜 462頁ＣＡ，11月５〜９，1995年を参照されたい。この提案では、ゲート負荷が変化するとき、ゲートの大きさが自動的に十分に成長して遅延を一定に保持している。
【００１２】
一定遅延のモデルは、マッピングアルゴリズムにおいて提案されている。例えば、Ｅ．Ｌehmab ，Ｙ．ワタナベ，Ｊ．ＧrodsteinおよびＨ．Ｈarkness の“Ｌogic  Ｄecomposition  ＤURING ＴECHNOLOGY Ｍapping”，Ｄigest Ｉnt. ＣONF.on  Ｃomputer Ａided  Ｄesign  264〜271 頁ＣＡ，11月５〜９，1995年を参照されたい。しかしながら、この提案は一定の遅延を選択する良好な方法を与えず、さらに、マッピングにため対して一定の遅延のモデルを与えているだけである。
【００１３】
同様に、一定の遅延のモデルは、ファーンアウト最適化に対して提案されている。例えば、Ｋ．Ｋodandapani，Ｊ．Ｇrodstein，Ａ．ＤomicおよびＨ．Ｔouati の“Ａ  Ｓimple Ａlgorism For Ｆanout Ｏptimization Ｕsing  Ｈigh Ｐerformance  Ｂuffer Ｌibraries”，Ｄigest Ｉnt. ＣONF. on Ｃomputer Ａided  Ｄesign  466〜471 頁ＣＡ，11月 7〜11，1993年を参照されたい。上記の参考文献は一定の遅延のモデルの重要性を注目させるが、“電気的努力”とも呼ばれる利得の重要性については注目していない。
【００１４】
Ｓutherland およびＲ．Ｓproll による文献“論理的努力の理論：エンベロープのバックにおける速度に対する設計”ＶＬＳＩにおける最近の研究、カリホルニア大学、サンタクルーズ1991年においては、遅延は利得に対する依存性であるとされている。遅延最適化問題の寸法に依存しない公式もまた与えられているが、その解は厳密でない、スクラッチパッド型の計算として使用されることを意図したものであり、集積回路の設計におけるセル配置に対する全体的な集積された自動化された解の一部ではない。Ｖ．Ｋumarの文献“論理的努力の拡張による抵抗性接続の一般化された遅延最適化”Ｐroc.Ｉnt. Ｓymp. on Ｃircuit and  Ｓystems, 1993年 vol.3, 2106〜2109頁 5月 3〜6 ，1993年では上記の方法は顕著な量のＲＣ遅延を有する長いワイヤを解析するために使用されている。
【００１５】
米国特許第5,654,898 号明細書には、集積回路レイアウトを決定するための方法および装置が示され説明されており、それによってタイミング駆動バッファサイズの決定がタイミング要求を満足させるように行われている。しかしながら、この解決方法は厳密ではない計算に依存しており、集積回路の設計におけるセル配置に対する全体的な集積された自動化された解を示唆するものではない。前述の欠点を克服し、デジタル回路またはネットワークの配置および経路設定に対するタイミング閉鎖を維持するための方法および装置が必要とされ、発明されることが求められている。
【００１６】
【課題を解決するための手段】
本発明は、概括的に言えば、電子回路記述に基づいて、関連する相対的な遅延値をそれぞれ有するセルを含むセルライブラリを使用することにより集積回路レイアウトを設計する自動化された方法において、
（ａ）複数のワイヤによって互いに結合されることを意図しており、電子回路記述に基づいたデジタル回路を構成するために使用することのできる複数のセルを選択し、
（ｂ）集積回路における選択された複数のセルのそれぞれの最初に意図された位置を決定し、そのステップにおいて選択された複数のセルの少なくとも幾つかのものは最初に意図された面積が選択されたセルの関連する相対的な遅延値およびその選択されたセルに結合された幾つかのワイヤの最初の意図された長さを使用して決定され、
（ｃ）選択された複数のセルのそれぞれの位置および面積ならびにワイヤの長さを最終的に定め、
（ｄ）選択された複数のセルのそれぞれの最終的な位置および面積ならびに最終的なワイヤ長を使用して集積回路レイアウトを生成するようにデジタル回路のルートを設定するステップを含んでいる。
【００１７】
本発明によれば、設計プロセスを通してタイミング閉鎖のメンテナンスを容易にする利点が得られる。本発明は設計プロセスにおける配置および経路設定プロセスにより予測できない遅延効果を補償することのできる別の利点を有する。
【００１８】
本発明のさらに別の利点は、本発明によって通常の方法の高価なタイミング解析を避けることができることである。対照的に従来の通常の設計プロセスはプロセッサ全体にわたってタイミング解析が必要とされる。
【００１９】
最適化の目的として、タイミングの代りに、回路面積を設定することにより本発明により以下のようなことが可能になる。第１に、１つのモジュール中に形成される過剰な回路の面積は他のモジュールによって互いに補償されることができる。対照的に１つのモジュール中における過剰なタイミングは他のモジュールによって通常補償されることはできない。第２に、２つの異なった回路を比較するとき、面積は測定可能なパラメータである。対照的に、タイミングは各回路パスで異なる可能性があるから、タイミングに基づいて２つの回路の特性の利点を比較することは困難である。第３に、もしも回路面積が一定に設定されるならば、経路設定が達成されることは保証されない。
【００２０】
【発明の実施の形態】
当業者は本発明の以下の説明が単なる例示であり、本発明の技術的範囲を限定するものではないことを認識するであろう。本発明のその他の実施形態は当業者に容易に示唆されよう。
【００２１】
類似の部分またはステップが類似の参照符号により識別されている図面を詳細に参照すると、図１では、本発明を実行することができるホストコンピュータシステム100 の概略図が示されている。ホストコンピュータシステム100 は好ましくはコンピュータ105 、ディスプレイ110 、プリンタ115 、プロッタ120 を含んでいる。コンピュータ105 は典型的にパーソナルコンピュータまたはワークステーションである。ディスプレイ110 は集積回路の設計に関するグラフィックおよびテキスト材料との両者を表示する。またコンピュータシステム100 にはキーボード130 と“マウス”等の指向装置135 が含まれている。集積回路設計で使用されるソフトウェアツールと共に動作するとき、コンピュータシステム100 は基本的に特別な設計機能を実現するための直列の電子回路になる。このようなソフトウェアツールの１例はアクエリアス（Aquarius）であり、これはカリフォルニア州フレモントの Avant！社から入手可能である。
【００２２】
図２は、コンピュータシステム100 （図１）により設計されることができ本発明を理解するため付加的な背景材料として与えられる典型的な集積回路150 の一部を示している。デジタル回路150 はゲートｉ、ｊ、ｋを含んでいる複数のゲートを具備している。ゲートは組合わせのゲートであり、その機能は例えば演算子ＡＮＤ、ＯＲ、ＮＯＴに基づいてブール式として表される。ゲートはまたレジスタでもある。
【００２３】
各ゲート（例えばゲートｊ）は１以上の入力155 と１つの出力160 を有する。回路150 のゲートは複数のネットにより共に結合されている。例えばゲートｉはネット 165ａに接続する第１の入力と、ネット 165ｂによりゲートｋの出力に接続される第２の入力とを有する。ゲートｊはネット 165ｃによりゲートｉの出力に接続されている第１の入力と、ネット 165ｄに接続されている第２の入力と、ネット 165ｅに接続されている出力とを有する。
【００２４】
ゲートの出力が１つゲートの入力に接続されているゲートは集合的に後者のゲートの“ファーンイン”と呼ばれる。したがってゲートｋはゲートｉのファーンインにある。ゲートの入力が１つのゲートの出力に接続されているゲートは集合的に後者のゲートの“ファーンアウト”と呼ばれる。したがってゲートｊはゲートｉのファーンアウトにある。
【００２５】
デジタル回路150 は多数のサイクルでデジタル２進入力データを処理することにより論理機能を実行する。入力データは１次入力170 でデジタル回路150 へ与えられ、デジタル回路機能の計算結果が１次出力175 で与えられる。典型的に、デジタル回路機能の計算は１以上のサイクルを必要とする。各サイクル中に、ゲート機能が計算され、計算結果は次のサイクルで使用するためにレジスタに記憶される。
【００２６】
図２の回路150 は組合わせ回路網として知られている。図３はコンピュータシステム100 （図１）によって設計されることのできる順次回路網180 の概略回路図である。順次回路網180 では、フィードバックループは典型的に少なくとも１つのレジスタを含んでいる。例えばフィードバックループ182 はレジスタ184 を含んでいる。
【００２７】
図４は、本発明の自動化方法の概略を示すフロー図であり、これは以下説明する種々のステップのそれぞれを実行する命令のシーケンスを含んでいるコンピュータプログラムを使用して実行されることができる。自動化プログラムはしたがって以下のステップを含む方法を実行する。図４のフローチャートでは、各ステップはその固有の異なるコンピュータ命令を有する（即ち各ステップ 200−300 はさらにステップを有する）ことにさらに留意すべきである。ステップ200 で、合成（またはその他の回路記述）により生成されたネットリストが読取られる。ステップ205 で、回路全体の機能を維持しながらデジタル回路の接続数を減少するために構造の最適化が実行される。付加的に、ライブラリ209 のライブラリ解析207 がステップ205 期間中、またはその前に実行されてもよい。以下さらに詳細に説明するように、ライブラリ解析207 中に、デジタル回路で使用される各ゲートの遅延が決定される。ステップ210 で、デジタル回路はセルのライブラリ209 にマップされる。ステップ215 で、回路面積すなわち回路の占有する面積を最適化するためのオプションとしてバッファがデジタル回路に付加されてもよい。ステップ220 で、ゲート遅延の“伸長”および／または“圧縮”が予め定められたタイミング制約を満たし回路網面積を最適化するために実行される。ステップ225 で、セルの配置が行われ、その期間に本発明にしたがって一定のセル遅延特性を維持するためにセルのサイズが決定される。ステップ230 で、回路網経路設定が実行され、セルのネット負荷がタイミング制約と回路面積とをさらに妥協するように調節されてもよい。ステップ230 後、チップレイアウトが生成される（ステップ235 ）。
［ネットリストの読取り］
ステップ200 （図４）で、本発明はターゲットの技術のボックスの詳細な相互接続リストであるネットリストを読取り、そこから自動化論理図が集積回路製造のために生成される。ネットリストは典型的にVerilog またはＶＨＤＬフォーマットであり、Synopsy 社からのSynopsys Design Compiler（商標名）、またはAmbit Design Systems社からのBuildGate （商標名）のような合成ツールから生成される。合成ツールは所望の論理機能を記述する複雑なVerilog またはＶＨＤＬ構成の解析を実行する。合成ツールはさらに特性の合成、リタイミング、リソース共有、スケジューリング、状態マシンの最適化、レジスタマッピングのような順次最適化を実行する。
［ライブラリ解析］
図４のステップ210 の期間中またはその前に、ライブラリ解析207 が回路設計に使用されるライブラリ209 で実行される。ライブラリ解析207 は合成される実際の回路に依存せず、したがって図４で示されている回路設計プロセスとは別々に実行されることができる。ライブラリ解析207 中に、遅延Ｄがデジタル回路で使用される各ゲートに対して決定される。ライブラリ209 のゲートが容量性負荷値Ｃとサイズ値Ｓを有し、ここでＳは連続的な正の実数の可変値であり、これは駆動能力とゲート面積の両者を線形に増加する。ゲートの遅延Ｄは式（１）により近似されることができる。
（１）  Ｄ＝Ｆ（Ｃ／Ｓ）
遅延Ｄは負ではなく、Ｃ／Ｓ値の増加と共に増加する。
【００２８】
遅延Ｄの値はセルにより与えられる遅延と、セルのネット（ワイヤ）負荷により与えられる遅延とに基づいている。したがって、配置／経路設定の前および後に遅延Ｄを一定値に理想的に維持するために、ネット負荷抵抗が考慮されなければならない。本発明により、以下詳細に説明するようにＤを“一定”に維持するために、容量性負荷の変化に基づいてセルの配置後にゲートサイズが調節される。しかしながら、ワイヤ負荷も抵抗を有するので、（ゲートサイズ調節後の）Ｄ値は予め定められたＤ値から無視できる程度の量だけ実際に変化してもよい。この変化は無視できる程度であるので、Ｄはセルの配置前またはセルの配置およびゲートサイズの調節後は近似的に“一定”とされる。
【００２９】
遅延Ｄの値はゲートの異なる入力に対して異なっており、ゲートを通って伝播する信号の下降遷移および上昇遷移では異なる。負荷値がサイズ“１”のゲートにより駆動されることができるので、Ｃ／Ｓ値は“典型的な負荷”として定義される。ライブラリ解析は利得の考慮に基づいてライブラリ中の各ゲートのＣ／Ｓに“良好な”値を決定する。直列接続の理想的なインバータのセットで最大の利得を得るために、各インバータの利得はｅ、即ち約２．７であるべきであることが当業者に知られている。しかしながら実際のインバータは理想的ではなく、それ故、寄生の自己負荷を有し、これは固定されインバータのサイズおよびインバータにより駆動される負荷キャパシタンスと独立している寄生遅延を生じる。主に寄生遅延を与えているのはトランジスタのソース／ドレイン領域のキャパシタンスと、ソース／ドレインとインバータの出力を駆動するトランジスタのゲートとの間のミラーキャパシタンスである。この寄生遅延を考慮するならば、直列接続のインバータで最大利得を得るために、各インバータの利得は２．７よりも大きく例えば約３．６に設定される。
【００３０】
インバータ以外のゲートの好ましい利得を発見する方法について説明する。任意の回路または回路網では、良好な動作点は、利得と遅延との間の良好な妥協が実現できる点である。この妥協を最適化するため“連続的なバッファリング想定”が使用され、これはI. E. Sutherlandと、R. F. Sproull の“The Theory of Logical Effort:Designing for Speed on the Back of an Envelope ”、Advanced Research in VLSI 、１−16頁、UC Santa Cruz 、1991年に記載されている考えに基づいている。
【００３１】
一定の遅延を発見する方法はインバータに対するゲートの比較に基づく。この方法は、幾つかの点でゲート自体の利得を増加するのではなく利得を増加するためにバッファを使用することがさらに有効になるという考えに基づいている。さらにバッファを付加することにより、各付加されたバッファは先に付加されたバッファよりも大きいサイズであり、組合わせ（ゲートとバッファ）の利得は遅延の増加と共に指数関数的に大きくなる。
【００３２】
以下の解析では、連続的なバッファリングが行われることができ、それによって極小量のバッファリングの挿入が可能であることが想定される。幾つかのゲートを有する所定のパスでは、幾つかの分数バッファが１つの実際のバッファに組み合わせられることができる。したがって、多数の論理レベルを有する回路では、連続的なバッファリングがほぼ現実的に実現されるか現実に近いものとなる。
【００３３】
連続的なバッファリングが行われることができると想定すると、直列の理想的なインバータの遅延はτｌｏｇ（ｈinv ）として書かれることができ、ここでτは時定数であり、ｈinv はインバータの利得である。換言すると、直列のバッファの利得はその遅延と共に指数関数的に増加する。
【００３４】
直列の理想的なインバータに結合されるゲートの遅延を考慮する。式（２ａ）に示されているように、ゲートの遅延ｄgateは部分的にゲートの負荷に依存し、ゲートの負荷はインバータの利得ｈinv により除算される組合わせの負荷（Ｃout ）である。
（２ａ）  ｄgate＝Ｐgate＋Ｒgate（Ｃout ／ｈinv ）＋τｌｏｇ（ｈinv ）
パラメータＰgateはゲートの固有の遅延であり、Ｒgateはゲート抵抗である。所定のＣout に対するｄgateを最小にするために、ｄgateの導関数（式（２ａ））はｈinv に関して取られ、その結果が式（２ｂ）により示されている。
【数４】
0004594519.tif 000002
【００３５】
式（２ｂ）をゼロ（０）に設定することにより、式（２ｃ）が得られる。
（２ｃ）ＲgateＣout ＝τｈinv
バッファが必要とされない地点では、ｈinv ＝１であり、ＲgateＣout ＝τである。式（２ｃ）を式２（ａ）に代入することによって、各ゲートの遅延は固有の遅延Ｐgateプラス時定数τである。
【００３６】
この一定遅延の使用を解釈すると、この遅延がバッファの使用対利得の伸長間のクロスオーバー点であることである。換言すると、臨界的なパス上のゲートの遅延はこのクロスオーバー点の値よりも低速であることはない。これは利得または遅延の最適化問題を処理する明瞭な規則を与える。もしもより大きいパス利得が必要とされるならば、バッファはゲートを遅くするのではなく速くする方法がとられる。またバッファの使用はさらに区域の面積を高める解である。前述のこれらの結果を以下のように使用する。所定のライブラリでは、インバータが最初に解析される。インバータの利得が約３．６である結果を使用して、典型的な負荷Ｃtyp が式（２ｄ）により示されているように得られる。
【００３７】
（２ｄ）  Ｃtyp ＝（３．６）Ｃin
ここで、Ｃinはインバータの入力キャパシタンスである。典型的な負荷はインバータの一定の遅延を得るために使用される。これは実際の非理想的なインバータであるので、式（２ｅ）で示されているように以下のルールが適用される。
【００３８】
（２ｅ）  Ｒinv Ｃinv ＝τ
Ｒinv は式（２ｆ）により表されるように遅延式から決定される。
【数５】
0004594519.tif 000003
【００３９】
同じルールをライブラリの全ゲートに適用すると次式（２ｇ）が得られる。
【数６】
0004594519.tif 000004
【００４０】
以下の例を通して、図５のａとｂで示されているように、Ｐチャンネルトランジスタの抵抗Ｒinv は同一幅のＮチャンネルトランジスタの抵抗Ｒinv の２倍の高さであると仮定される。実際の非理想的なインバータ250 の概略図を示している図５のａを最初に参照する。インバータ250 はＰチャンネルトランジスタ252 とＮチャンネルトランジスタ254 とを含んでいる。トランジスタ252 と254 がそれぞれ１ユニットの抵抗Ｒinv を有すると仮定されるならば、Ｐチャンネルトランジスタ252 はＮチャンネルトランジスタ254 の幅の２倍である。さらにインバータ250 の入力キャパシタンスＣinが３ユニットであると仮定する（ここでＮチャンネルトランジスタ254 は１ユニットの入力キャパシタンスを有し、Ｐチャンネルトランジスタ252 は２ユニットの入力キャパシタンスを有する）。インバータ250 の典型的な負荷は、非理想的なインバータの利得が約３．６であるべきであるという事実を使用して得ることができる。したがって式（２ｄ）に基づいて、典型的な負荷Ｃtyp が式（２ｈ）により示される。
（２ｈ）  Ｃtyp ＝（３．６）Ｃin＝（３．６）（３）＝１０．８
典型的な負荷値Ｃtyp はインバータ250 の遅延を得るために使用されることができ、それにおいて、Ｒinv ＝１であり、τ＝Ｒinv Ｃinv ＝（１）（１０．８）＝１０．８である。
【００４１】
図５のｂを参照すると、ＮＯＲゲート256 はＰチャンネルトランジスタ258 、260 と、Ｎチャンネルトランジスタ262 、264 を含んでいる。図５のｂの全てのトランジスタが同一のサイズを有すると仮定すると、プルアップ抵抗は（Ｐチャンネルトランジスタ258 、260 の両者を通じて）４ユニットであり、プルダウン抵抗は（Ｎチャンネルトランジスタ262 またはＮチャンネルトランジスタ264 の一方を通じて）１ユニットである。典型的な負荷は式（２ｉ）に基づいて決定される。
【００４２】
（２ｉ）  ＲgateＣtyp ＝τ
Ｒgate＝４、τ＝１０．８であるプルアップ抵抗に対して、式（２ｉ）はＣtyp ＝２．７になる。Ｒgate＝１、τ＝１０．８であるプルダウン抵抗に対しては、式（２ｉ）はＣtyp ＝１０．８になる。同一のゲートでＣtyp の異なる回答を有することは望ましくない。ＮＯＲゲート256 では１つの実数のキャパシタンスが存在できるので、複数のオプションが有効である。例えば、２つのＣtyp 値（２．７と１０．８）の平均が選択されてもよい。代わりに、Ｃtyp に対する最も制約する値が選択されてもよい。通常、図５のｂで示されているようなこのような不平衡ゲートは伝播する信号の上昇および下降遷移の両者で良好に動作するように同調されることができない。大きい相違は不適切な大きさのゲートを示している。
【００４３】
前述したように、各ゲートは多数のゲート入力のために１よりも多数の遅延式を有する。また異なる遅延式は上昇信号遷移と落下信号遷移に対応する。
［構造の最適化］
ステップ205 （図４）では、本発明はステップ200 からネットリストを読取った後、構造上の最適化を実行する。このステップ中に、回路の構造とゲートのブール関数が回路の全体的な機能を変更せずに接続の総数を減少するように変更される。構造の最適化は（リソース共有等の）動作の最適化と、（リタイミング等の）順次最適化と、（核抽出等の）代数的最適化と、（冗長除去等の）ブール最適化を含むことができる。前述の最適化のクラスは当業者によく知られている。
［マッピング］
ステップ210 （図４）では、回路はセルのライブラリ209 にマップされる。即ち回路ゲートの論理機能はライブラリ209 からの実際のセルで実行される。マッピングによって、回路遅延とその他の物理的特性も決定されることができる。本発明のステップ210 では、一般的なマッピングプロセスが使用されてもよい。図６はマッピングプロセス（ステップ210 ）を示しており、これはさらに、分解300 、クラスタ生成305 、整合310 、カバーリング315 の付加的なステップを含んでいる。分解ステップ300 は大きい交換可能なゲートを入力の交換可能なゲートに分割する。
【００４４】
クラスタ生成ステップ305 は論理で整合を選択する。成功率の低いクラスタは避けられることが好ましく、それによって整合するクラスタの総数はそれ程大きくならない。
【００４５】
整合ステップ310 はクラスタの機能を実行できるライブラリ機能を発見するプロセスである。このステップは文献（K.Keutzer 、“DAGON : Technology Binding and Local Optimization by DAG Matching ”、Proceeding of the 24th ACM/IEEE Design Automation Conference、マイアミビーチ、フロリダ州（1987年６月、 341〜347 頁、IEEE Computer Society Press 1987）に記載されているアルゴリズムのような通常の整合アルゴリズムを使用することにより実行される。
【００４６】
カバーリングステップ315 はデジタル回路を実際に構成するために使用される整合を決定する。ダイナミックプログラミングに基づくタイミング駆動カバーリング方法がこのステップで使用されてもよい。このカバーリング方法にしたがって、回路の構成はその到着時間に基づいて可能な構成のセットから選択される（データのゲートにおける到着時間はファーンインゲートの最大の到着時間に、ゲートの入力ピンから出力ピンまでの測定された遅延をプラスすることにより計算される）。最速の到着時間である回路の構成はカバーリングステップ315 期間中に選択されてもよい。本発明と対照的に、通常のマッピングプロセスは到着時間が多数のファーンアウト点の選択された構成に基づいているので、“到着時間”の正確な計算を実現しない欠点を有する。通常のプロセスでは、このような多数のファーンアウト点の選択された構成は相互に依存している。
【００４７】
本発明による回路の構成に対する到着時間の計算について説明する。ゲートの到着時間計算を議論するための回路の一部の概略図を示している図７のａ−ｃを参照する。図７のａでは、（段335 の）ゲート330 に対する到着時間はファーンインゲート（線 340、 345、 350）の到着時間に、ゲート330 の入力端子355 から出力端子360 までの信号遅延をプラスすることにより決定される。段365 におけるファーンアウトの構成はしたがってゲート330 の到着時間の計算では因数分解されない。図７のｂでは、段370 に対する到着時間はファーンインゲート330 と372 の到着時間プラスゲート370 の入力端子375 と出力端子380 との間の遅延により決定される。同様に、図７のｃでは、（段387 の）ゲート385 の到着時間はファーンインゲート370 と390 の到着時間プラス入力端子395 と出力端子400 との間の遅延により決定される。
【００４８】
前述のプロセスは出力端子404 に結合された出力を有するゲート402 に対して反復される。したがって、図７のａ−ｃの回路の出力端子404 の到着時間はゲート402 の到着時間に基づいて決定されることができる。
【００４９】
したがって、図７のａ−ｃに示されているような、本発明の一定遅延方法では、マルチファーンアウトのその他のファーンアウトは到着時間の計算に無関係である。到着時間はしたがってレベル化される方法で入力から出力まで回路を通過することにより計算されることができる。所定のパスのゲートの到着時間を決定することによって、回路のパスの遅延全体が決定されることができる。
［レベル減少］
セル配置ステップ（図４のステップ225 ）の前に、遅延が一定に保持される事実により回路の変更が通常一般的に可能であるよりもさらに可能である。タイミング制約が満たされ、形成される回路の変更が知られているので、回路変更が行われるとき遅延の影響が予測されることができる。マップされた回路で行われることができる１つの特定の変化および変更は論理レベルの減少である。本発明による一定遅延モデルを使用する利点を示すため図８のａおよびｂを参照する。図８のａはゲート 555、 560、 565、 570を含むゲート連鎖550 の概略図である。最初に、ゲート555 は線 575と 580で接続されたファーンインを有する。ゲート 560、 565、 570はそれぞれ線 585、 590、 595で接続されたファーンインを有する。ローカル変換がゲート連鎖回路550 の論理レベルの数を減少するために使用される。変換結果が図８のｂのゲート連鎖回路 550' として示される。論理レベル数がゲート555 を前方にすることにより減少される。一定遅延モデル方法では、この変換の効果は容易に予測されることができる。負荷変更を保障するために（配置期間中またはその後）ゲートサイズが調節されながら遅延は一定に維持されるので、ゲート負荷の変更は遅延に影響しない。（ゲート連鎖回路550 ）の遅延に影響する唯一の変化はゲート555 のファーンインの変更である。この遅延変化は線 590、 575、 580で接続されているファーンインにより与えられるゲート遅延を単に付加することにより予測されることができる（図８のｂのゲート連鎖回路550'を参照）。
【００５０】
図８のｂに示されている変換が有効であるように、ゲート 555、 560、 565にファーンアウトがないことを必要とする。ゲート 555、 560、 565にファーンアウトがないならば、これらはコピー論理を通じてファーンアウトがないように製造される。例えば、回路550 （図８のａ）でゲート555 が付加的なファーンアウト597 を有することを想定する。ゲート555 の機能は回路550'で変化しないので、回路550'のゲート555 （図８のｂ）は付加的なファーンアウト597 を駆動しない。したがって、回路550'ではファーンアウト597 を駆動するため（回路550 のゲート555 の複製である）コピー論理回路555'が設けられる。
【００５１】
対照的に、通常の設計方法の欠点を以下説明する。通常の論理設計下では、コピー論理はゲート上の負荷を増加し、その出力は線 575、 580、 590に接続されている。図８のｂの例では、コピー論理回路555'はゲート上の負荷を増加し、その出力は線 575、580 へ接続されている。図８のｂの例では、コピー論理回路555'はゲートの負荷を増加し、その出力は線 575、580 へ接続されている。変換が遅延を改良するか否かを予測するために、正確な遅延モデルを有する完全な静的タイミング解析を実行することが必要である。（回路550 から550'への）変換が実際に遅延に悪影響するならば、変換は実行してはならない。
［面積解析とネット加重計算］
マップされた回路のゲートサイズが計算される区域（面積）解析を最初に説明する。ゲートサイズはゲートの実際の負荷をゲートの予め定められた典型的な負荷により除算することによりＣ／Ｓとして計算される。１例として、所定のゲートｉの実際の負荷がＣi として表されると仮定し、ここでＣi はゲート負荷のキャパシタンス測定値である。実際の負荷Ｃi は式（３）により近似的に計算される。
（３）  Ｃi ＝□i ＋ΣＣj ＊（１／ｈij）
パラメータ□i は所定のゲートｉのネット（ワイヤ）負荷（ここではネット負荷は前述のファーンアウトベースのモデル等の一般的なネット負荷モデルを使用して評価されることができる）プラス回路構成の１次的な出力の負荷等のその他の固定した負荷を表している。パラメータΣＣj ＊（１／ｈij）は入力負荷であり、ここで下付き文字ｊは所定のゲートｉのファーンアウトゲートであり、ｈはゲートｉとｊ間の電気的な労力である。
【００５２】
式（３）は式（４）で示されるマトリックス表記で表されることができる。
（４）  ｃ＝□＋（Ｈ）（ｃ）
ここでＨ＝［１／ｈij］であり、これは電気的な努力のマトリックスである。パラメータｃはゲート負荷のベクトルであり、ｃ＝［Ｃi ］であり、これはゲート負荷のマトリックスであり、□はワイヤ負荷□i のベクトルである。
【００５３】
式（３）または（４）にしたがって、所定のゲートｉのサイズを計算するために、図７のａ乃至７のｃに関して示されているようにそのファーンアウトゲートｊのサイズが最初に計算されなければならない。ファーンアウトゲートｊのサイズはその出力容量性負荷Ｃj に依存する。ファーンアウトゲートに対するこの依存はデータ流のゲート負荷計算ダウンストリームの実行を必要とする。デジタル回路が組合わせ回路網（例えば図２の回路150 を参照）であるならば、ゲート負荷計算は１次的な出力175 で開始し、１次入力170 方向にレベルされた順序で回路を横切る。
【００５４】
デジタル回路が順次回路網（図３の回路180 を参照）であるならば、周期的な依存が生じる１以上のループ（例えばループ182 ）が存在する（即ち“最も右側の”ゲートは存在しない）。ゲート負荷計算はサイクルの任意の位置で開始することができ、サイクルの計算は負荷キャパシタンス値が収斂するか、十分に小さい差を有するまで数回実行される。しかしながら、負荷キャパシタンス値が収斂せずサイクル計算毎に漸進的にさらに大量に増加する状況が存在する。負荷キャパシタンス値のこの増加は、固定した数のサイクル計算後、計算された負荷値が予め設定した最大値を超過したならば検出されることができる。計算された負荷値が収斂しないとき、特定の回路180 は実行不可能な解を有し、これは回路利得が非常に小さいのでデジタル回路が設定速度で動作しないことが予期されることを示している。回路利得を増加するために変更が必要とされ、これらの変更は通常、回路遅延の増加につながる。
【００５５】
前述の例では、ゲートｉのサイズＳはゲートｉの予め定められた典型的な負荷Ｃ／Ｓにより実際の負荷Ｃi を除算することによって決定される。サイズＳは“サイズを定められたゲート”の面積を決定するためゲートの全てのトランジスタチャンネル幅に適用されるスケールファクタである。サイズＳはゲートの出力負荷駆動容量とその入力ピン負荷とをスケールするために使用されるスケールファクターでもある。
【００５６】
サイズを定められたゲートの面積は式（５）により決定される。
（５）  サイズを定められたゲートの面積＝Ｓ＊（ゲートの面積）
マップされたデジタル回路の面積は、サイズを定められたゲートの面積全体とネット面積（これは回路の全てのネットの全長から評価される）との合計に基づいて評価されることができる。
【００５７】
マッピングステップ期間中に、可能な回路構成はネットの加重計算に基づいて評価されてもよい。したがって、以下“ネット加重”の計算について説明する。ネット加重は特定のネットの負荷に関するデジタル回路の面積全体の感度を表す。１例として、デジタル回路の１次入力に直接結合された所定のゲートのネット加重は単位負荷当りの面積に等しい。式（６）を使用して、デジタル回路のその他のゲートのネット加重はデジタル回路の１次出力方向にレベルされた順序で計算される。
【数７】
0004594519.tif 000005
【００５８】
式（６）では、下付き文字ｊは所定のゲートｉのファーンインゲートを表している。パラメータｗi はゲートｉのネット加重であり、Ａはデジタル回路の全体の面積であり、ａi はゲートｉの面積であり、Ｃi はゲートｉの容量性負荷である。前述したように、ｈijはゲートｉとｊとの間の電気的な労力である。
【００５９】
式（６）は式（７）で示されているようなマトリックス表記で表現されることができる。（７）  ｗ＝□＋（Ｈ）（ｗ）
【数８】
0004594519.tif 000006
【００６０】
式（６）からのネット加重値は配置ステップ（図４のステップ225 ）後にセルのセル面積を後で計算するためにも使用されることができる。このセル面積は式（８）により表される。
（８）  Ａ＝Σ（ｗi ）（ωi ）
ここでパラメータωi は所定のゲートｉのワイヤ負荷を表している。
【００６１】
マッピング期間中に、計算されたネット加重値は、計算されたネット加重値が回路面積を考慮することを可能にするので、デジタル回路を構成するために使用される整合の決定に使用されることができる。式（６）で示されているように、所定のゲートｉのネット加重は（既にマップされた）ファーンインコーンの論理にのみ基づいており、ここではネット加重はセルの負荷に関する回路の全体の面積の感度を表している。さらに式（８）で示されているように、ネット加重が増加したならばセルの全体の面積は増加する。したがって、例えば所望の回路機能では、第１の回路構成は第２の回路構成のネット加重よりも高いネット加重を有する。それ故、第１の回路構成は第２の回路構成よりも可能な負荷に対して大きい面積を有する。それ故、遅延を無視すると、両者の回路構成の面積値は設計プロセスのこの段で決定されないが、第２の回路構成は第１の回路構成よりも好ましい。
【００６２】
前述の例により示されているように、ネット計算は部分的にゲート面積に基づいて回路構成決定を行うことを許容する。ネット加重計算は１つのセルの面積が別のセルの面積と相対的に比較されることを許容し、両者のセルは所望のデジタル回路網で同一機能を有する。ネット加重計算の利点は、セルの面積を比較するとき、セルの実際の面積値が知られる必要のないことである。
［バッファリング］
セルの配置前に、ある整合が図４のステップ215 に示されているようにデジタル回路網にバッファを挿入することにより変更されることができる。このステップでは、バッファの付加は遅延を増加するが、負荷がさらに小さいためのソースゲートはサイズがさらに小さくなるので面積を節約する。大きな負荷は特に信号タイミングが臨界的ではないときバッファにより駆動されることが好ましい。バッファリングはソースセルがサイズを小さくすることを可能にし、それによって回路の面積を減少する。
【００６３】
バッファリングステップ215 （図４）を図９を参照にさらに詳細に説明する。ステップ650 では、バッファが付加されることができる回路の位置が決定され、それによってバッファの挿入はさらにタイミング制約が満足されることを許容する。バッファ挿入後に予測されたスラック値を与えるために“ローカルスラック”からバッファの遅延を減算することによりこの決定は行われる。タイミング制約が満たされるならば、スラックはゼロまたは正である。さらに、回路の全てのスラックは１つの“最悪の”スラック数である“回路網スラック”により要約されることができる。回路網スラックが負ではないならば、タイミング閉鎖が実現される。ステップ650 で計算された予測されたスラックが回路網スラックよりも大きいならば、回路遅延を増加せずにバッファを挿入することが可能である。
【００６４】
ステップ655 では、バッファ挿入のために付加された面積が、ソースゲートのサイズを下げることによって節約された面積を超過しないか否かを決定する。付加された面積（バッファの挿入により）はバッファサイズにより乗算されたバッファの面積に等しく、ここでバッファサイズはバッファの典型的な負荷Ｃ／Ｓにより除算されたバッファ負荷Ｃにより決定される。ソースゲートのサイズを下げることにより節約された面積はバッファ挿入のためにネット負荷の変更を最初に計算することにより決定される。このネット負荷の変更は（１）幾つかのシンク（シンク電流）が除去され、（２）バッファの入力負荷が付加され、（３）ゲートのファーンアウト数が変更されるためである。
【００６５】
ネット加重の式（６）を使用して、動作面積についてのバッファ挿入の影響が評価される（ステップ660 ）。ステップ665 では、回路面積のインパクトが正であるならばバッファが挿入される（即ち回路面積が減少される）。バッファの挿入後、ステップ670 では、キャパシタンス値がバッファのファーンインコーン中で更新される必要があり、一方ネット加重はバッファのファーンアウトコーン中で更新される必要がある。この更新ステップはネット加重を正確に維持し、ネット加重の再計算をバッファ挿入により影響を受ける回路部分に限定するように作用する。
【００６６】
図１０はゲート680 の出力負荷に挿入されたバッファ685 と690 を有するゲート680 を示している。バッファ685 と690 はゲート680 がサイズを下げられることを許容する。回路692 の面積インパクトが正であるならば、面積バッファ685 と690 が挿入される（回路692 の面積がバッファリングのために減少される）。バッファ挿入は回路面積を最適化するための方法である。バッファ挿入の結果として、回路のタイミングは遅くなるが、回路タイミングはタイミング制約を満足する。バッファ挿入はバッファから付加された遅延のためにネット遅延を増加させる。タイミング制約が既に満たされている回路部分では、バッファの付加は先に決定されたタイミング制約を満足する結果となる。
【００６７】
タイミング制約内にあることが好ましいが、タイミング制約を越え、設計プロセスで回路を後に補正し、タイミング制約が漸進的に満たされることも本発明の技術的範囲内である。付加的に、満たされるタイミング制約よりも節約面積が重要であることが決定された場合、先に決定されたタイミング制約が満たされなくてもバッファは面積を節約するために挿入されることができる。回路の多数のパスは臨界的なタイミング要件をもたず、したがってバッファは面積を節約するためにこれらのパスに挿入されることができる。
［ゲート遅延の圧縮または伸長］
セルの配置前に、個々のゲートの遅延は図４のステップ220 で示されているように遅延制約を満たすために伸長または圧縮されてもよい。図１１のａで示されているように、所定の速度の遅延を圧縮（減少）することにより、ゲート利得は減少する。遅延制約を満たしていない長いパス上のゲートは、長いパスが遅延制約を満たすまで（遅延で）圧縮される。複数のゲート（単数のゲート）の遅延が最小の必要な利得要件が満たされる限り減少される。
【００６８】
所定のゲートの遅延を伸長（増加）することにより、ゲートの利得は増加する（図１１のａ参照）。容易に遅延制約を満たす短いパス上のゲートは、伸長された遅延を有するゲートが同一負荷で少い面積しか必要としないので（遅延において）伸長される。パス中の複数のゲート（単数のゲート）の遅延はデジタル回路のタイミング制約が満たされる程度まで伸長される。
【００６９】
ゲート遅延の伸長および圧縮ステップはゲートサイズの調節に関連されない。前述したように、ゲート遅延を伸長または圧縮するために、ゲート利得は近似的に調節される。伸長および圧縮ステップをデジタル回路750 部分を示している図１１を参照してさらに詳細に説明する。１例として、約０．１ピコファラドの入力キャパシタンス負荷（Ｃin）をもちながら、ゲート752 は約２．０ピコファラドの出力キャパシタンス負荷（Ｃout ）を駆動する要求を有する。したがってゲート752 の利得要件はＣout ／Ｃin＝２．０／０．１である。ゲート754 は約２．０ピコファラドの出力キャパシタンス負荷と約０．２ピコファラドの入力キャパシタンス負荷を有すると仮定する。したがって、ゲート754 の利得要求は２．０／０．２である。
【００７０】
また、ゲート752 は遅延Ｄ＝１を有すると仮定する。ゲート752 が“パス１”上にあることがさらに仮定され、これは開始点756 における約１の到着時間要件と、終端点758 における約４の到着時間要件を有する。したがって式（９）により示されているように、パス１の遅延制約は約３に等しい。
（９）  制約＝到着時間（点756 ）−到着時間（点758 ）＝４−１＝３
ゲート752 の遅延Ｄが１に等しく、パス１の遅延制約が３に等しいので、パス１に対するスラックは式（10）により示されているように２に等しい。
（10）  スラック＝遅延制約−ゲート遅延＝３−１＝２
ゲート754 は遅延Ｄ＝５を有することがさらに仮定される。ゲート754 が“パス２”上であることがさらに仮定され、これは開始点760 における約１の到着時間要件と、終端点762 における約４の到着時間要件を有する。したがって式（11）により示されているように、パス２の遅延制約は約３に等しい。
【００７１】
（11）  制約＝到着時間（点760 ）−到着時間（点762 ）＝４−１＝３
ゲート754 の遅延（Ｄ＝５）が３のパス２の遅延制約よりも大きいので、ゲート754 の遅延はタイミング制約を満たさない。
【００７２】
本発明はパス毎のベースで動作し、それによってデジタル回路750 の最も臨界的なパスが最初に評価される。すなわち、パス１はこれが最も臨界的なパスであるならば最初に評価される。パス２はこれが最も臨界的なパスであるならば最初に評価される。パス２が最も臨界的なパスであると仮定すると、ゲート754 の利得の影響を観察しながら、ゲート754 の遅延はパス２の３の遅延制約を満たすために圧縮される。前述したように、ゲート754 の利得要件はＣout ／Ｃin＝２．０／０．１である。しかしながら、図１１のａで示されているように、特定のサイズにされたゲートの利得はゲート遅延Ｄが減少すると減少する。したがってゲート754 の圧縮はその利得要求により限定される。
【００７３】
ゲート754 がパス２のタイミング制約を満たすように調節された後、これは“ロック”され、それによってゲート754 の遅延は残りの圧縮および伸長ステップのためにさらに調節されることはない。パスが１よりも多くのゲートを含んでいるならば、好ましくはそれらの遅延はパスのタイミング制約を満たすために等量で圧縮（伸長）されることにさらに留意される。例えば、４つのゲートは所定のパス中にあり、２ナノ秒の遅延が所定のパスに付加されることができると仮定する。本発明の好ましい実施形態にしたがって、０．５ナノ秒の遅延が４つの各ゲートに付加されることができ、それによって所定のパスに付加される２ナノ秒の遅延を同等に分配する。
【００７４】
本発明は次の臨界的なパスを評価するステップに進む。パス１が次に最も臨界的なパスであると仮定する。図１１では、ゲート752 の遅延（Ｄ＝１）がパス１の３の遅延制約を満し、したがってゲート752 の遅延は２のスラックに基づいて伸長されることができる。ゲート752 はその遅延が伸長された後にロックされる。複数のゲートがパス１上にあるならば、好ましくはそれらの遅延は同等量に伸長される。
【００７５】
本発明は次の臨界的なパスを評価し、それによってゲート遅延は伸長または圧縮されてもよい。ゲート遅延伸長ステップ中にスラック値を減少するとき、ワイヤ遅延のような下流方向の遅延効果を補償するためにパスに小量のスラックを維持することが好ましい。さらに、幾つかの例では、ライブラリのルールがスラック値の減少量を限定してもよい。
【００７６】
伸長および圧縮の目的で、回路中のレジスタは、それらの終了するパスの一部ではなく、それらが開始するパスの一部として考慮されることが好ましい。伸長および圧縮ステップはさらに図１２のフローチャートで示されている。ステップ770 で、回路の最も臨界的なパスが評価され、ステップ775 で、パスの１つのゲート（または複数のゲート）の遅延が伸長または圧縮される。ステップ780 で、次に臨界的なパスが評価され、ステップ782 で、パスの１つのゲート（または複数のゲート）の遅延が伸長または圧縮される。ステップ784 で、全てのパスが評価されていないならば、本発明は次の臨界的なパスを評価するためステップ780 へ戻る。ステップ784 で、全てのパスが評価されているならば、本発明はステップ785 へ進み、ここでセルの配置が実行される。
［セルの配置］
ステップ225 （図４）で、セルの配置が実行される。図１３のａと１３のｂはセルの配置ステップ225 （図４）中に回路設計が論理的階級830 から物理的階級832 へ変換される態様を示している。物理的階級832 では、論理的階級830 の中間論理レベルがバケット834 で関連され、あるいはそこでグループ化され、各バケット834 は例えば約１００のセル836 を保持する。バケット834 は図１３のｃで示されているようにアレイで整列される。設計者がセル836 のグループを共に維持することを選択したならば、セル836 のグループは同一のバケット834 または近隣のバケットでグループ化される。好ましくはバケット834 はその中のセルの配置がタイミングにほとんど影響されないような十分小さい寸法にされる。換言すると、バケット834 のサイズはバケット834 中のワイヤ遅延に無関係であるようにされる。しかしながら、パケットのサイズはバケットに含まれるセル836 のリマッピングとリサイジングに適合するのに十分な大きさでなければならない。バケット内に位置されることができるセルの数は好ましくは約２０セルから約２００セルの範囲である。
【００７７】
（プレーサと全般的なルータを駆動するための）事前経路と事前配置はバケット834 構造に駆動される。しかしながら、本発明は通常の配置方法およびシステムで実施または実行されてもよいことにさらに留意すべきである。
【００７８】
本発明にしたがって、タイミング閉鎖はセル836 の配置が生じた後に維持される。タイミング閉鎖を維持するために、特定のゲートのサイズは配置中またはその後に調節されてもよい。この調節は配置アルゴリズムが異なるネット長を異なるネットへ割当て、これらの異なるネット長は配置ステップ前に予測が困難であるという事実を補償する。したがって、本発明の実施により、ゲートサイズは配置前に決定された遅延値を維持するために調節される。
【００７９】
対照的に、通常の配置方法は、配置アルゴリズムにより生じるネット長の変化による遅延の変化を補償してワイヤの長さを最適化する。したがって通常の配置方法は、本発明では避けられる高価で時間のかかる遅延解析を含んでいる。
【００８０】
前述したように、式（８）は配置されたセルのセル面積を決定する。
（８）  Ａ＝Σ（ｗi ）（ωi ）
前述したように、パラメータωi は所定のゲート（例えばゲートｉ）のワイヤ負荷を表している。式（８）に基づいて、各ゲートの面積は積（ｗi ）（ωi ）に基づいて決定される。したがって、所定のゲートｉは適切な寸法にされることができ、実際のネット長が配置前の評価されたネット長と異なるとき通常の方法で必要とされた高価な遅延解析を避けることが可能である。
【００８１】
デジタル回路の経路設定
ステップ230 （図４）で、配置された回路の経路設定がチップレイアウト235 を完了するために実行される。経路設定ステップは配置ステップ中またはその前に先に決定されたワイヤを配置する。ステップ230 で、ゲート遅延およびゲートサイズが固定される。ルータはしたがって遅延を基本的に一定に維持しタイミング閉鎖を実現するためにワイヤ負荷を制御する。ゲート遅延およびゲートサイズは前もって固定されている。ルータはしたがって例えばワイヤ905 と910 間の距離900 を制御する。２つのワイヤ905 と910 間のキャパシタンスはワイヤ間の距離900 の増加と共に減少する。通常のルータは距離900 を制御することに使用されることができる。
【００８２】
この使用は集積回路レイアウトが生成されるときに存在するコンポーネント（例えばバッファ、セル、ネット）を示している。しかしながら、本発明にしたがってレイアウトの生成前にステップを実行するとき、示されたコンポーネントはコンピュータに記憶されたデータ表示であり実際の装置ではないことが当業者により認識される。
【００８３】
したがって、本発明は特定の実施形態を参照してここで説明され、変形の許容範囲、種々の変化および代用が前述の説明で意図され、幾つかの例では本発明の幾つかの特性はその他の特性を対応して使用せず本発明の技術的範囲を逸脱せずに使用されることが認識されよう。
【図面の簡単な説明】
【図１】  本発明を実行することのできるホストコンピュータシステムの概略図。
【図２】  図１のコンピュータシステムによって設計されることのできる組合わせ回路網の概略回路図。
【図３】  図１のコンピュータシステムによって設計されることのできる順次回路網の概略回路図。
【図４】  本発明による方法を示すフロー図。
【図５】  理想的および理想的でないインバータとＮＯＲゲートの概略図。
【図６】  マッピング方法を示すフロー図。
【図７】  到着時間計算を議論するために示した回路の一部の概略図と、その回路の次の段を含んだ回路の概略図と、さらに次の段を含んだ回路の概略図。
【図８】  ４レベルの論理を有するゲート連鎖の概略図およびそのゲート連鎖の論理レベルの数が減少した変換後の概略図。
【図９】  本発明によるバッファ方法を示すフロー図。
【図１０】  バッファが最適化されたネットワーク領域に挿入されているデジタル回路の一部の概略図。
【図１１】  ゲート遅延の伸長および圧縮方法を示すデジタル回路の一部の概略図およびゲート利得Ｃout ／Ｃinとゲート遅延Ｄとの関係を示すグラフ。
【図１２】  本発明によるゲート遅延の伸長および圧縮方法を示すフロー図。
【図１３】  本発明によるネットワークの論理的階級とそれから変換されたネットワークの物理的階級のブロック図およびセルがバケットの内部に配置された複数のバケットの部分的上部正面図。
【図１４】  経路設定後のタイミング制約を制御するための容量性負荷値の調整を説明するために示されたネット中の２つのワイヤの部分的斜視図。
【図１】
0004594519.tif 000010
【図２】
0004594519.tif 000011
【図３】
0004594519.tif 000012
【図４】
0004594519.tif 000013
【図５】
0004594519.tif 000014
【図６】
0004594519.tif 000015
【図７】
0004594519.tif 000016
【図８】
0004594519.tif 000017
【図９】
0004594519.tif 000018
【図１０】
0004594519.tif 000019
【図１１】
0004594519.tif 000020
【図１２】
0004594519.tif 000021
【図１３】
0004594519.tif 000022
【図１４】
0004594519.tif 000023