トップ :: G 物理学 :: G06 計算;計数




【発明の名称】 集積回路設計の相互接続遅延駆動型の配置および経路指定
【発明者】 【氏名】チェン，シイ・ケイ

【氏名】ヤオ，ソウ−ゼン
【要約】 【課題】サブミクロンＩＣ設計の必要性に、より適切に対処する配置および経路指定技法を提供する。

【解決手段】ＥＤＡツールに、相互接続遅延駆動型という形でＩＣ設計の配置と経路指定を最適化する配置および経路指定（Ｐ＆Ｒ）モジュールを備え、そのＰ＆Ｒモジュールが、それぞれ構成要素を介して２つのピンを相互接続しているその構成セグメントの相互接続遅延を改善できるかどうかを判定することによって、現在のクリティカルな相互接続経路指定パスの相互接続遅延を改善できるかどうかを体系的に判定する。
【特許請求の範囲】
【請求項１】 集積回路設計の配置および経路指定を最適化する方法であって、それぞれが第１ピンから構成要素を介して第２ピンへ接続している複数の相互接続経路指定パスから一群のクリティカルな相互接続経路指定パスを指定することと、前記指定したクリティカルな相互接続経路指定パスの各々について、異なる位置に再配置した構成要素を介して、あるいは異なる位置に配置された論理的に等価な構成要素を介して第１のピンを第２のピンに接続する異なるパスによって相互接続遅延を減少させることができるかどうかを自動的に決定することと、前記指定したクリティカルな相互接続経路指定パスの各々について、前記第１のピンを前記第２のピンに相互接続する異なるパスの１つを前記相互接続遅延を減少させることができるかどうかに基づいて選択することを含むことを特徴とする方法。
【請求項２】 前記クリティカルな相互接続経路指定パスについての相互接続遅延を減少させることができるかどうかの自動的な決定が、性能駆動型経路指定を使用して、前記第１のピンを複数の候補位置に相互接続する第１の複数の相互接続経路指定パスに関する相互接続遅延、および前記第２のピンを同じ複数の候補位置に相互接続する第２の複数の相互接続経路指定パスに関する相互接続遅延を決定することを含む請求項１に記載の方法。
【請求項３】 前記性能駆動型経路指定が、性能駆動型迷路経路指定である請求項２に記載の方法。
【請求項４】 あるクリティカルな相互接続経路指定パスの相互接続遅延を減少させることができるかどうかの自動的な決定が、前記第１のピンと候補位置との間に発生する相互接続遅延と、前記第２のピンと同じ候補位置との間に発生する相互接続遅延とを合計することをさらに含む請求項２に記載の方法。
【請求項５】 あるクリティカルな相互接続経路指定パスの相互接続遅延を減少させることができるかどうかの自動的な決定が、相互接続遅延の合計と、再配置された構成要素で発生する遅延とを合計することをさらに含む請求項４に記載の方法。
【請求項６】 あるクリティカルな相互接続経路指定パスの相互接続遅延を減少させることができるかどうかの自動的な決定が、前記相互接続遅延の合計と、候補位置で配置された論理的に等価の構成要素で発生する遅延とを合計することをさらに含む請求項４に記載の方法。
【請求項７】 あるクリティカルな相互接続経路指定パスの相互接続遅延を減少させることができるかどうかの自動的な決定が、少なくとも一部は相互接続経路指定候補の長さに基づいて、複数の相互接続経路指定候補の抵抗を決定することを含む請求項１に記載の方法。
【請求項８】 あるクリティカルな相互接続経路指定パスの相互接続遅延を減少させることができるかどうかの自動的な決定が、少なくとも一部は相互接続経路指定候補のシーリングとフロアの密平面の配置位置に基づいて、複数の相互接続経路指定候補のキャパシタンスを決定することを含む請求項１に記載の方法。
【請求項９】 前記キャパシタンスの決定が、所定のワイヤ間平均距離と、様々なフロアおよびシーリングの密平面の組合せとを使用して、所定のキャパシタンス・テーブルからキャパシタンス値をルックアップすることをさらに含む請求項８に記載の方法。
【請求項１０】 前記キャパシタンスの決定が、複数の相互接続面に関する輻輳条件を決定することを含む請求項８に記載の方法。
【請求項１１】 コンピュータによって実行されたときにそれぞれが第１ピンから構成要素を介して第２ピンへ接続している複数の相互接続経路指定パスから一群のクリティカルな相互接続経路指定パスを指定することと、前記指定したクリティカルな相互接続経路指定パスの各々について、異なる位置に再配置した構成要素を介して、あるいは異なる位置に配置された論理的に等価な構成要素を介して第１のピンを第２のピンに接続する異なるパスによって相互接続遅延を減少させることができるかどうかを自動的に決定することと、前記指定したクリティカルな相互接続経路指定パスの各々について、前記第１のピンを前記第２のピンに相互接続する異なるパスの１つを前記相互接続遅延を減少させることができるかどうかに基づいて選択することを含む方法を実施する命令が記録されている記録可能媒体。
【請求項１２】 前記クリティカルな相互接続経路指定パスについての相互接続遅延を減少させることができるかどうかの自動的な決定が、性能駆動型経路指定を使用して、前記第１のピンを複数の候補位置に相互接続する第１の複数の相互接続経路指定パスに関する相互接続遅延、および前記第２のピンを同じ複数の候補位置に相互接続する第２の複数の相互接続経路指定パスに関する相互接続遅延を決定することを含む請求項１１に記載の記録可能媒体。
【請求項１３】 前記性能駆動型経路指定が、性能駆動型迷路経路指定である請求項１２に記載の記録可能媒体。
【請求項１４】 あるクリティカルな相互接続経路指定パスの相互接続遅延を減少させることができるかどうかの自動的な決定が、前記第１のピンと候補位置との間に発生する相互接続遅延と、前記第２のピンと同じ候補位置との間に発生する相互接続遅延とを合計して相互接続遅延の合計を得ることをさらに含む請求項２に記載の記録可能媒体。
【請求項１５】 あるクリティカルな相互接続経路指定パスの相互接続遅延を減少させることができるかどうかの自動的な決定が、前記相互接続遅延の合計と、再配置された構成要素で発生する遅延とを合計することをさらに含む請求項１４に記載の記録可能媒体。
【請求項１６】 あるクリティカルな相互接続経路指定パスの相互接続遅延を減少させることができるかどうかの自動的な決定が、前記相互接続遅延の合計と、候補位置で配置された論理的に等価の構成要素で発生する遅延とを合計することをさらに含む請求項１４に記載の記録可能媒体。
【請求項１７】 あるクリティカルな相互接続経路指定パスの相互接続遅延を減少させることができるかどうかの自動的な決定が、少なくとも一部は相互接続経路指定候補の長さに基づいて、複数の相互接続経路指定候補の抵抗を決定することを含む請求項１１に記載の記録可能媒体。
【請求項１８】 あるクリティカルな相互接続経路指定パスの相互接続遅延を減少させることができるかどうかの自動的な決定が、少なくとも一部は相互接続経路指定候補のシーリングとフロアの密平面の配置位置に基づいて、複数の相互接続経路指定候補のキャパシタンスを決定することを含む請求項１１に記載の記録可能媒体。
【請求項１９】 前記キャパシタンスの決定が、所定のワイヤ間平均距離と、様々なフロアおよびシーリングの密平面の組合せとを使用して、所定のキャパシタンス・テーブルからキャパシタンス値をルックアップすることをさらに含む請求項１８に記載の記録可能媒体。
【請求項２０】 前記キャパシタンスの決定が、複数の相互接続面に関する輻輳条件を決定することを含む請求項１９に記載の記録可能媒体。
【請求項２１】 複数のプログラミング命令を格納した記録可能媒体と、前記複数のプログラミング命令を実行するために前記記録可能媒体に連結されたプロセッサであって、前記複数のプログラミング命令が、それぞれが第１ピンから構成要素を介して第２ピンへ接続している複数の相互接続経路指定パスから一群のクリティカルな相互接続経路指定パスを指定することと、前記指定したクリティカルな相互接続経路指定パスの各々について、異なる位置に再配置した構成要素を介して、あるいは異なる位置に配置された論理的に等価な構成要素を介して第１のピンを第２のピンに接続する異なるパスによって相互接続遅延を減少させることができるかどうかを自動的に決定することと、前記指定したクリティカルな相互接続経路指定パスの各々について、前記第１のピンを前記第２のピンに相互接続する異なるパスの１つを前記相互接続遅延を減少させることができるかどうかに基づいて選択することを含む方法を実施するプロセッサとを有することを特徴とするコンピュータ・システム。
【請求項２２】 前記クリティカルな相互接続経路指定パスについての相互接続遅延を減少させることができるかどうかの自動的な決定が、性能駆動型経路指定を使用して、前記第１のピンを複数の候補位置に相互接続する第１の複数の相互接続経路指定パスに関する相互接続遅延、および前記第２のピンを同じ複数の候補位置に相互接続する第２の複数の相互接続経路指定パスに関する相互接続遅延を決定することを含む請求項２１に記載のコンピュータ・システム。
【請求項２３】 前記性能駆動型経路指定が、性能駆動型迷路経路指定である請求項２２に記載のコンピュータ・システム。
【請求項２４】 あるクリティカルな相互接続経路指定パスの相互接続遅延を減少させることができるかどうかの自動的な決定が、前記第１のピンと候補位置との間に発生する相互接続遅延と、前記第２のピンと同じ候補位置との間に発生する相互接続遅延とを合計して相互接続遅延の合計を得ることをさらに含む請求項２に記載のコンピュータ・システム。
【請求項２５】 あるクリティカルな相互接続経路指定パスの相互接続遅延を減少させることができるかどうかの自動的な決定が、前記相互接続遅延の合計と、再配置された構成要素で発生する遅延とを合計することをさらに含む請求項２４に記載のコンピュータ・システム。
【請求項２６】 あるクリティカルな相互接続経路指定パスの相互接続遅延を減少させることができるかどうかの自動的な決定が、前記相互接続遅延の合計と、候補位置で配置された論理的に等価の構成要素で発生する遅延とを合計することをさらに含む請求項２４に記載のコンピュータ・システム。
【請求項２７】 あるクリティカルな相互接続経路指定パスの相互接続遅延を減少させることができるかどうかの自動的な決定が、少なくとも一部は相互接続経路指定候補の長さに基づいて、複数の相互接続経路指定候補の抵抗を決定することを含む請求項２１に記載のコンピュータ・システム。
【請求項２８】 あるクリティカルな相互接続経路指定パスの相互接続遅延を減少させることができるかどうかの自動的な決定が、少なくとも一部は相互接続経路指定候補のシーリングとフロアの密平面の配置位置に基づいて、複数の相互接続経路指定候補のキャパシタンスを決定することを含む請求項２１に記載のコンピュータ・システム。
【請求項２９】 前記キャパシタンスの決定が、所定のワイヤ間平均距離と、様々なフロアおよびシーリングの密平面の組合せとを使用して、所定のキャパシタンス・テーブルからキャパシタンス値をルックアップすることをさらに含む請求項２８に記載のコンピュータ・システム。
【請求項３０】 前記キャパシタンスの決定が、複数の相互接続面に関する輻輳条件を決定することを含む請求項２８に記載のコンピュータ・システム。
【発明の詳細な説明】【０００１】
【産業の利用分野】本発明は、集積回路（ＩＣ）設計の分野に関する。より詳細には、本発明は、ＩＣ設計のための配置および経路指定の最適化に関する。
【０００２】
【従来の技術】長年の間にＩＣ設計の複雑さが絶えず増し続けてきたことにより、ＩＣ設計者は、ＩＣ設計を支援するために、ますます電子設計自動化（ＥＤＡ）ツールに頼るようになってきた。これらの支援は、合成、配置、経路指定から、レイアウト検証に至るまで、設計プロセス全体に渡るものである。
【０００３】配置および経路指定、すなわち構成要素の配置および様々な構成要素を接続している接続の経路指定の技術分野では、様々な技法が知られている。たとえば、Ｗａｎｇ等に発行された米国特許第５８１８７２９号では、「２次配置」および「スパニング・ツリー」モデルを使用してセルを配置するための方法およびシステムが開示され、Ａｓｈｔａｐｕｔｒｅ等に発行された米国特許第５０７２４０２号では、「チャネル」方式を使用して相互接続を経路指定するための方法が開示され、Ｘｉｏｎｇ等に発行された米国特許第５５５０７４８号では、「領域検索」方式を使用してタイミング制約を満たすための「遅延した」経路指定に関する方法が開示されている。
【０００４】近年では、配置および経路指定を「結合的に」実行するための様々な技法も知られるようになった。たとえば、Ｃｈｅｎｇに発行された米国特許第５７９８９３６号では、経路指定輻輳(routing congestion)のルックアヘッドを含む配置方法が開示され、Ｖａｒａｄａｒａｊａｎ等に発行された米国特許第５８３８５８３号では、配置および経路指定を最適化するための「結合」方法が開示され、Ｃｈｅｎｇに発行された米国特許第５８４７９６５号では、ＩＣを配置および経路指定するための「結合」領域ベースの方法が開示された。
【０００５】
【発明が解決しようとする課題】これら従来技術の技法はそれぞれが独自の利点を有するが、すべての技法は、サブミクロンＩＣを配置および経路指定する必要性に適切に対処していないという、少なくとも１つの共通した欠点を共有している。さらに、相互接続遅延が、動作速度を上げるためにサブミクロンＩＣをより一層小型化するのを妨げる大きな障害となっている。したがって、サブミクロンＩＣ設計の必要性に、より適切に対処する配置および経路指定技法が求められている。
【０００６】
【課題を解決するための手段】ＥＤＡツールには、相互接続遅延駆動型という形でＩＣ設計の配置および経路指定を最適化する、配置および経路指定（Ｐ＆Ｒ）モジュールが備えられている。Ｐ＆Ｒモジュールは、構成要素を介して２つのピンを接続しているパスの構成セグメントそれぞれの相互接続遅延を改善できるかどうかを判定することによって、クリティカルな相互接続経路指定パスの相互接続遅延を改善できる（すなわち減少させられる）かどうかを、体系的に判定することができる。そのようなそれぞれのセグメントでは、Ｐ＆Ｒモジュールが、異なる位置に再配置された構成要素を介して、あるいは異なる位置に配置された論理的に等価の構成要素を介して、２つのピンを相互接続する異なる相互接続経路指定パスを使用することにより、セグメントの相互接続遅延が改善できるかどうかを判定する。
【０００７】一実施態様では、ソース・ピンといくつかの候補位置との間の相互接続遅延、および候補位置と宛先ピンとの間の相互接続遅延を決定することによって、各セグメントの相互接続遅延が決定される。一実施態様では、それぞれの場合の相互接続遅延の決定に、セグメントのソース／宛先部分候補の抵抗およびキャパシタンスを決定することが含まれる。
【０００８】一実施態様では、性能駆動型経路指定技法を使用して、セグメントのソース／宛先部分候補の相互接続遅延が決定される。それぞれの場合で、抵抗の決定には、セグメントのソース／宛先部分候補の長さを決定することが含まれ、キャパシタンスの決定には、様々な相互接続面の輻輳条件と、ソース／宛先部分候補が配設される相互接続面のワイヤ間平均距離とを決定することが含まれる。決定されたワイヤ間平均距離は、所定のキャパシタンス・テーブルから様々な相互接続面ペアのキャパシタンス寄与をルックアップする際に使用される。次いで、このルックアップされたキャパシタンス寄与が、重み付けされた形でキャパシタンスを決定する際に使用される。
【０００９】本発明について、限定的ではなく、例示的な実施形態によって添付の図面で説明するが、この図面では、同じ要素が同じ参照番号で示されている。
【００１０】（発明の詳細な説明）以下の説明で本発明の様々な態様について記載し、本発明について徹底的に理解するために様々な詳細について述べる。ただし、当分野の技術者であれば、本発明が本発明の一部のみまたはすべての態様で実施可能であること、および本発明が特定の詳細なしでも実施可能であることが明らかであろう。その他の場合には、本発明が不明瞭にならないように、周知の特徴が省略または簡略化される。
【００１１】説明には、当分野の技術者が当分野の他の技術者に作業の内容を伝えるために、セル、相互接続面など、通常使用している用語を使用して示した部分がある。また、説明には、テーブル、データなどの用語を使用して、コンピュータ・システムによって実行される動作に関して示した部分もある。当分野の技術者であればよく理解しているように、これらのものは、デジタル・システムの電気的構成要素を介して格納、転送、結合、あるいは操作することができる、電気信号、磁気信号、または光信号の形式をとり、デジタル・システムという用語には、スタンドアロン型、付属型、または組込型の、汎用ならびに特定用途向けのデータ処理マシン、システムなどが含まれる。
【００１２】次に、本発明を理解する上で最も役立つ方法で、様々な動作について、複数の個々のステップを実行しながら説明する。ただし、説明の順序は、これらの動作を記述された順序どおりに実行する必要があることを意味するものとして、さらには順序に依存しているものとして解釈するべきではない。最後に、「一実施形態では」という語句を繰返し使用しているが、これは同じ実施形態を参照する場合もあるが、必ずしもそうではない。
【００１３】ここで、一実施形態による本発明の概要を示す構成図である図１を参照する。図に示されるように、本発明によれば、ＥＤＡツールの配置および経路指定（Ｐ＆Ｒ）モジュールは、クリティカルな相互接続経路指定パスの相互接続遅延を改善することを体系的に試行することにより、ＩＣ設計の配置および経路指定を最適化する。Ｐ＆Ｒモジュールは、中間構成要素を介してソース・ピンと宛先ピンのペア（ＰsとＰd）を相互接続している、パスのそれぞれの構成セグメントの相互接続遅延を改善することを体系的に試行することにより、クリティカルパスの相互接続遅延を改善しようと試みる。詳細には、以下でより詳細に説明するように、Ｐ＆Ｒモジュールは、中間構成要素を再配置するか、または候補位置で中間構成要素を他の論理的に等価の構成要素に置き換えるために、いくつかの候補位置について考慮することにより、セグメントのソース部分／宛先部分それぞれの相互接続遅延を改善しようと試みる（図１０を参照のこと）。
【００１４】ブロック１０２では、Ｐ＆Ｒモジュールが、すべての相互接続経路指定パスまたはパス・セグメントに関する相互接続遅延の所与の配置および経路指定を決定する。ブロック１０４では、相互接続経路指定パスおよびパス・セグメントについて決定された相互接続遅延に基づいて、Ｐ＆Ｒモジュールがクリティカルな相互接続パスを識別する。一実施形態では、これらは、設計基準を超える相互接続遅延を招く相互接続パスである。他の実施形態では、クリティカルな相互接続パスは、最大の相互接続遅延を招く相互接続パスである。他の実施形態では、代わりに他の定義を使用する場合がある。ブロック１０６では、Ｐ＆Ｒモジュールが、これらのクリティカルな相互接続パスそれぞれについて、クリティカルな相互接続パスの相互接続遅延が改善可能であるかどうかを判定する。この判定を下す方法について、以下でより詳細に説明する。
【００１５】例示された実施形態では、毎回繰り返した後に、プロセスを繰り返すかどうかをＰ＆Ｒモジュールが判定する。すなわち、設計基準を下回るレベルにまでクリティカルな相互接続パスの相互接続遅延を減少させるためにＰ＆Ｒモジュールを使用するか、あるいは、達成可能な最良の相互接続遅延を判定するためにＰ＆Ｒモジュールを使用するかである。前者の場合、ブロック１０４では、設計基準を超える相互接続遅延を招くすべての相互接続パスが、クリティカルな相互接続パスとして識別される。１回繰り返した後、Ｐ＆Ｒモジュールは、遅延を減少させるための代替方法について考察できるように、設計基準を超える相互接続遅延を依然として招いているクリティカルな相互接続パスの報告および識別を、設計者に対して行うだけである。後者の場合、ブロック１０４で、最大の相互接続遅延を招いている相互接続パスが、クリティカルな相互接続パスとして識別される。毎回繰り返した後に、Ｐ＆Ｒモジュールは１０４で、最大の相互接続遅延を招いているクリティカルな相互接続パスの識別を再度続行する。新しいクリティカルな相互接続パスが出現していなければ、Ｐ＆Ｒモジュールはプロセスを終了し、同じ技法を使用してこれ以上改善が達成されることはないとして、１０５に分岐する。たとえば、３つのクリティカルな相互接続パスがあり、そのうち２つのパスの相互接続遅延が２０％改善され、３番目のパスは１０％改善された場合、その３番目のパスが最大相互接続遅延を招いている唯一のパスとして残る。ただし、少なくとも１つの新しいクリティカルな相互接続パスが出現した場合、Ｐ＆Ｒモジュールは、新しいクリティカルな相互接続パスに対して１０６を繰り返す。たとえば、ここでも再度、３つのクリティカルな相互接続パスがあり、そのうち２つのパスの相互接続遅延が２０％改善され、３番目のパスは１０％改善された場合、３番目のパスと４番目の相互接続パスとが、現在最大の相互接続遅延を招いていることになる。４番目の相互接続パスは、新しく出現したクリティカルな相互接続パスである。
【００１６】図２を参照すると、一実施形態による、図１の動作１０６をより詳細に例示した構成図が示されている。図に示されるように、２０２では、Ｐ＆Ｒモジュールが、中間構成要素を介してソース・ピンを宛先ピンに相互接続するクリティカルな相互接続パスのセグメントを選択する。ブロック２０４では、Ｐ＆Ｒモジュールが、異なる位置に再配置された中間構成要素を介して、あるいは異なる位置で配設された論理的に等価の構成要素を介して、ソース・ピンを宛先ピンに相互接続する別の経路を使用し、クリティカルな相互接続パス・セグメントの相互接続遅延が改善（すなわち減少）できるかどうかを判定する。
【００１７】改善が不可能な場合、追加のセグメントがあれば、プロセスは２０６で他のセグメントについて続行する。あるいは改善が可能である場合、すなわち相互接続遅延が少ない相互接続経路指定パスが１つまたは複数存在する場合、Ｐ＆Ｒモジュールは２０８で、主として、相互接続遅延に基づいて、これら代替相互接続経路指定パスのうちの１つを選択する。他の実施形態では、ワイヤ・サイズなどの他の要素についても考察することができる。プロセスは、クリティカルな相互接続パスのそのようなセグメントすべてに関する改善が最終的に試行されるまで、続行する。
【００１８】図３は、一実施形態による図２の動作２０４を示す図である。図に示されるように、ブロック３０２で、Ｐ＆Ｒモジュールは、ＩＣをいくつかの領域（位置とも呼ばれる）に論理的に分割する。３０４で、Ｐ＆Ｒモジュールは、ソース・ピンをいくつかの候補位置に相互接続している様々な代替経路指定候補について、相互接続遅延を決定する。３０６で、Ｐ＆Ｒモジュールは、宛先ピンをいくつかの候補位置に相互接続している様々な代替経路指定候補について、相互接続遅延を決定する。様々な実施形態では、候補位置の識別を含むこれらの相互接続遅延の決定が、様々な性能駆動型経路指定技法を使用して実行される。一実施形態では、１９９６年６月のＬｉｕ等による「Ｎｅｗ Ｐｅｒｆｏｒｍａｎｃｅ Ｄｒｉｖｅｎ Ｒｏｕｔｉｎｇ Ｔｅｃｈｎｉｑｕｅｓ Ｗｉｔｈ Ｅｘｐｌｉｃｉｔ Ａｒｅａ／Ｄｅｌａｙ Ｔｒａｄｅｏｆｆ ａｎｄ Ｓｉｍｕｌｔａｎｅｏｕｓ Ｗｉｒｉｎｇ Ｓｉｚｉｎｇ」、３３ｒｄ Ｄｅｓｉｇｎ Ａｕｔｏｍａｔｉｏｎ Ｃｏｎｆｅｒｅｎｃｅで開示された方法に従って、性能駆動型経路指定が実行される。他の実施形態では、１９９７年６月のＬｉｕ等による「Ｄｅｓｉｇｎ ａｎｄ Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆ ａ Ｇｌｏｂａｌ Ｒｏｕｔｅｒ Ｂａｓｅｄ ｏｎ ａ Ｎｅｗ Ｌａｙｏｕｔ−Ｄｒｉｖｅｎ ｔｉｍｉｎｇ Ｍｏｄｅｌ ｗｉｔｈ Ｔｈｒｅｅ Ｐｏｌｅｓ」、ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｃｉｒｃｕｉｔｓ ａｎｄ Ｓｙｓｔｅｍｓで開示された方法に従って、性能駆動型経路指定が実行される。他の実施形態では、１９９９年４月のＨｕｒ等による「Ｔｉｍｉｎｇ Ｄｒｉｖｅｎ Ｍａｚｅ Ｒｏｕｔｉｎｇ」、Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｐｈｙｓｉｃａｌ Ｄｅｓｉｇｎ（ＩＳＰＤ）で開示された方法に従って、性能駆動型経路指定が実行される。
【００１９】ブロック３０８で、Ｐ＆Ｒモジュールは候補位置の相互接続遅延の合計を決定する。Ｐ＆Ｒは、それぞれの候補位置について、ソース・ピンを位置に相互接続する部分に対して生じる相互接続遅延と、候補位置を宛先ピンに相互接続する部分に対して生じる相互接続遅延とを合計する。さらに、候補位置で構成要素が再配置可能であり、論理的に等価の構成要素が候補位置にない場合、Ｐ＆Ｒモジュールは、構成要素によって生じる相互接続遅延をさらに合計する。ただし、候補位置では構成要素の再配置が不可能であるが、論理的に等価の構成要素が候補位置に存在する場合、Ｐ＆Ｒモジュールは、論理的に等価の構成要素によって生じる相互接続遅延をさらに合計する。どちらのオプションも利用可能である場合、Ｐ＆Ｒは、（候補位置に再配置された）構成要素によって生じる相互接続遅延と、（候補位置で配設された）論理的に等価の構成要素のうち少ない方、すなわち、２つのオプションのどちらか良い方を選択して、これをさらに合計する。
【００２０】図４は、相互接続経路指定パス・セグメントに関する相互接続遅延の決定を示す構成図である。図に示されるように、Ｐ＆Ｒモジュールは、４０２で、相互接続経路指定パス・セグメントの抵抗を決定する。一実施形態では、相互接続経路指定パス・セグメントの抵抗が、主として、相互接続経路指定パス・セグメントの寸法に基づいて決定される。Ｐ＆Ｒモジュールは、４０４で、相互接続経路指定パス・セグメントのキャパシタンスを決定する。一実施形態では、相互接続経路指定パス・セグメントのキャパシタンスが、主として、相互接続経路指定パス・セグメントのシーリング(ceiling）およびフロア(floor）の密平面(dense plane）の配設位置、ならびにこれらの面の輻輳条件(congestion condition)に基づいて、以下でより詳細に説明するように決定される。４０６では、Ｐ＆Ｒモジュールが、パス・セグメントに関して決定された抵抗およびキャパシタンスを使用して、相互接続経路指定パスの相互接続遅延を決定する。一実施形態では、相互接続遅延が、Ｅｌｍｏｒｅモデルを使用して決定される。（抵抗がキャパシタンスよりも前に決定されるように図示されているが、本発明はキャパシタンスを最初に決定しても実施可能である。）
【００２１】次に図５を参照すると、一実施形態による、相互接続経路指定パス・セグメントに関するキャパシタンスの決定を例示した構成図が示されている。図５に示されるように、ブロック５０２で、Ｐ＆Ｒモジュールは、様々な相互接続面の輻輳条件を最初に決定する。一実施形態では、Ｐ＆Ｒモジュールは、パス・セグメントが配設される面の輻輳条件と、適用可能であれば（すなわち、パス・セグメントが配設される面が最上部、最上部のすぐ下、最下部、または最下部のすぐ上である場合を除く）、上の２面および下の２面の輻輳条件とを決定する。一実施形態では、輻輳条件はワイヤ密度、すなわち単位面積当たりのワイヤ数に関して測定される。代替実施形態では、代わりに、それよりも多いかまたは少ない隣接面について考察される場合がある。ブロック５０４で、Ｐ＆Ｒモジュールは、パス・セグメントが配設される面に関するワイヤ間の平均距離を推定する。一実施形態では、この推定は、経験に基づいて決定された関数を使用する、決定された輻輳条件に基づくものである。ブロック５０６で、Ｐ＆Ｒモジュールは、決定されたワイヤ間の平均距離を使用して、いくつかのフロアおよびシーリングの密平面の組合せに関して、所定のキャパシタンス・テーブルからいくつかのキャパシタンス値をルックアップする。最終的に、ブロック５０８で、Ｐ＆Ｒモジュールは、所定のキャパシタンス・テーブルから取り出したキャパシタンス値を使用して、キャパシタンス値を推定する。一実施形態では、Ｐ＆Ｒモジュールが、重み付けの形で推定を実行する。すなわち、決定された輻輳条件を使用して、いくつかの所定の可能性関数から計算される、様々なシーリングとフロアの密平面の組合せが発生する可能性により、取り出されたキャパシタンス値を重み付けすることによる。たとえば、一実施形態では、平面ｉ＋２、ｉ＋１、ｉ、ｉ−１、およびｉ−２それぞれに関する所定の輻輳条件が０．７、０．６、０．８、０．５、および０．３であり、様々な密平面の組み合わせに関して取り出されたキャパシタンス値が、｛ｉ＋１，ｉ−１｝、｛ｉ＋１，ｉ−２｝、｛ｉ＋２，ｉ−１｝、および｛ｉ＋２，ｉ−２｝それぞれの組合せに関してｃ１、ｃ２、ｃ３、およびｃ４である場合、キャパシタンスは、０．５×０．６×ｃ１＋０．６×（１−０．５）×ｃ２＋（１−０．６）×０．５×ｃ３＋（１−０．６）×（１−０．５）×ｃ４を合計することによって推定される。（１−ｐ）項は、シーリング／フロアの密平面がｉ＋１／ｉ−１面に配設されていない可能性を表す。他の推定方法も使用可能である。テーブル７００に格納されたキャパシタンス値は経験に基づいて決定される。
【００２２】ここで図６を参照すると、相互接続経路指定パス・セグメントに関する、フロアとシーリングの密平面の概念を図示した多層ＩＣの透視図が示されている。図に示されるように、相互接続経路指定パス・セグメントは、「接続層」とラベル表示された層（相互接続面とも呼ばれる）の１つの上に配設される。フロアとシーリングの密平面は、所定のレベルを超える輻輳レベルを有する接続層「より上」および「より下」の層または相互接続面である。言い換えれば、シーリングの密平面は、「接続層＋１」、「接続層＋２」などで配設可能であるが、フロアの密平面は「接続層−１」などで配設可能である。十分に輻輳された「接続層」よりも上の相互接続層がない場合、または「接続層」が最上層である場合、相互接続経路指定パス・セグメントにはシーリング密平面がないということである。同様に、十分に輻輳された「接続層」よりも下の相互接続層がない場合、または「接続層」が最下層である場合、相互接続経路指定パス・セグメントにはフロア密平面がないということである。
【００２３】図７は、一実施形態によるキャパシタンス・テーブルの一例を示す図である。図に示されるように、例示された実施形態の場合、キャパシタンス・テーブル７００は多次元テーブルであり、「シーリング密平面」がどこに配設されるかに従って複数の２次元テーブル７０２が反復される。２次元テーブル７０２それぞれが、複数行のキャパシタンス値（ｃij）７０４を、フロア密平面の対応する配設それぞれについて１つ格納する。たとえば、層ｉ＋１上に配設された「シーリング密平面」の場合は、接続層ｉ−１および接続層ｉ−２などに配設されたフロア密平面のキャパシタンス値である。各行７０４は、特定のシーリングとフロアの密平面の組合せ、たとえば平面ｉ＋１およびｉ−１について、様々なワイヤ間平均距離のキャパシタンス値（ｃij）を格納する。
【００２４】ここで図８を参照すると、一実施形態による本発明のＰ＆Ｒモジュールが組み込まれたＥＤＡツールが示されている。図に示されるように、ＥＤＡツール・スゥィート８００には、図１〜７および１０を参照しながら前述したように、本発明の教示に組み込まれたＰ＆Ｒモジュール８０２が含まれる。さらに、ＥＤＡツール・スゥィート８００には、他のツール・モジュール８０４も含まれる。これらの他のツール・モジュール８０２の例には、合成モジュール、レイアウト検証モジュールなどが含まれるが、これらに限定されるものではない。
【００２５】図９は、本発明の実践に使用するのに好適なコンピュータ・システムの一実施形態を示す図である。図に示されるように、コンピュータ・システム９００には、システム・バス９０６を介して相互に結合された、プロセッサ９０２およびメモリ９０４が含まれる。システム・バス９０６には、ハード・ディスク、フロッピィ・ディスクなどの不揮発性大容量記憶装置９０８、キーボード、ディスプレイなどの入力／出力装置９１０、ならびにモデム、ＬＡＮインターフェースなどの通信インターフェース９１２が結合される。これらの要素は、それぞれ当分野で知られたその従来の機能を実行する。詳細には、システム・メモリ９０４および不揮発性大容量記憶装置９０８は、前述の本発明の教示を実施するプログラミング命令の、作業コピーおよび永続コピーを格納するために使用される。システム・メモリ９０４および不揮発性大容量記憶装置９０８は、ＩＣ設計を格納するために使用することもできる。本発明を実施するためのプログラミング命令の永続コピーは、配布ソース／媒体９１４およびオプションで通信インターフェース９１２を使用して、工場内または現場で、不揮発性大容量記憶装置９０８にロードすることができる。配布媒体９１４の例には、テープ、ＣＤ−ＲＯＭ、ＤＶＤなどの記録可能媒体が含まれる。一実施形態では、プログラミング命令は、図８のＥＤＡツール８００を実施するプログラミング命令の集合体の一部である。要素９０２〜９１４の構成はよく知られているため、詳細には説明しない。
【００２６】一般に、当分野の技術者であれば、本発明が記載された実施形態に限定されるものでないことを理解されよう。その代わりに、本発明は、添付の特許請求の範囲の精神および範囲内で修正および変更を実施することができる。したがって本発明の説明は、限定的なものではなく例示的なものとみなされる。
【００２７】以上、ＩＣ設計の配置および経路指定を最適化するための方法および装置について、相互接続遅延駆動型の形で説明した。
【出願人】 【識別番号】５００２４１８６０
【氏名又は名称】メンター・グラフィクス・コーポレーション
【出願日】 平成１２年１月２４日（２０００．１．２４）
【代理人】 【識別番号】１０００６４６２１
【弁理士】
【氏名又は名称】山川 政樹
【公開番号】 特開２００３−２７１６９０（Ｐ２００３−２７１６９０Ａ）
【公開日】 平成１５年９月２６日（２００３．９．２６）
【出願番号】 特願２００３−１４３８６（Ｐ２００３−１４３８６）