(57)【特許請求の範囲】
【請求項１】
集積回路設計内の初期配線経路を設計することであって、初期配線幅と、初期配線間隔と、前記配線経路の初期形状および位置とを確立する前記設計することと、
前記初期配線経路に基づいて、前記集積回路設計のクリティカル・エリアをモデル化することであって、配線幅と配線間隔とを変数とし、配線のショートおよび開放に関する欠陥密度を表す定数を含む関数を用いて前記モデル化をおこなうことと、
前記初期配線幅と前記初期配線間隔とを調節して修正済配線経路を生成することであって、前記配線経路の前記初期形状および位置を維持しながら前記初期配線幅と前記初期配線間隔とを修正して前記修正済配線経路を生成することと、
最適化プロセスを前記修正済配線経路に対して実施して、前記クリティカル・エリアが最適化され、最適化された歩留まりを生み出す最終的配線経路を選択することと
を含む方法。
【請求項２】
前記初期配線幅と前記初期配線間隔との前記調節が修正済配線幅と修正配線間隔とを生成する請求項１に記載の方法。
【請求項３】
前記最適化プロセスが配線幅と配線間隔との間の折り合いをつける請求項１に記載の方法。
【請求項４】
前記調節および前記最適化プロセスが前記集積回路設計の異なる層について増分式に実施される請求項１に記載の方法。
【請求項５】
前記初期配線経路を設計することは、電圧／ 電流要件を最適化するように前記初期配線経路の調節を行うことを含む、請求項１に記載の方法。
【請求項６】
コンピュータに、
集積回路設計内の初期配線経路を設計することであって、初期配線幅と、初期配線間隔と、前記配線経路の初期形状および位置とを確立する前記設計することと、
前記初期配線経路に基づいて、前記集積回路設計のクリティカル・エリアをモデル化することであって、配線幅と配線間隔とを変数とし、配線のショートおよび開放に関する欠陥密度を表す定数を含む関数を用いて前記モデル化をおこなうことと、
前記初期配線幅と前記初期配線間隔とを調節して修正済配線経路を生成することであって、前記配線経路の前記初期形状および位置を維持しながら前記初期配線幅と前記初期配線間隔とを修正して前記修正済配線経路を生成することと、
最適化プロセスを前記修正済配線経路に対して実施して、前記クリティカル・エリアが最適化され、最適化された歩留まりを生み出す最終的配線経路を選択することと
を実行させるコンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、設計のための歩留まり認識ＩＣ経路指定（yield-aware IC routing）を実施する方法およびコンピュータ・プログラムに関する。
【背景技術】
【０００２】
ＶＬＳＩ（超大規模集積）レイアウトの配線層内のクリティカル・エリアを縮小させる（したがって不規則欠陥歩留まりを向上させる）伝統的な方法は、経路指定中に、または経路指定後ステップとして、ワイヤ間隔を制御し、孤立したバイア数を低減し、全ワイヤ長を短縮する。ワイヤ・スプレッディング（個々のワイヤ間のスペースを拡大させること）は、ワイヤ間に生じてショートを引き起こすスポット欠陥の可能性を低減させ、ワイヤ長最小化は、開路を引き起こすスポット欠陥の可能性と、ショートを引き起こすスポット欠陥の可能性をどちらも低減させ、冗長バイア挿入は、遮断されたバイアが致命的な（歩留まりを低下させる）欠陥となる可能性を低減させる。
【非特許文献１】S. Gandemer, B. C. Tremintin, andJ. J. Charlot, "Critical area and critical levels calculations in IC yieldmodeling," IEEE J. Solid-State Circuits, Vol. 35, No. 3, pp. 158-166, Feb.1988
【発明の開示】
【発明が解決しようとする課題】
【０００３】
したがって、不規則欠陥開路に影響を及ぼす従来の方法は、全ワイヤ長を短縮することによるものである。デュアル・ダマシン製造プロセスでは、配線開路の出現率は以前の技術よりもずっと高い。開路の可能性を低減するより効果的な技法が明らかに求められている。
【課題を解決するための手段】
【０００４】
本発明の実施形態により、設計のために歩留まり認識ＩＣ経路指定を実施する方法およびコンピュータ・プログラムなどが提供される。この方法は、配線輻輳制約を満たす初期グローバル経路指定を実施する。次に、この方法は、例えば２次輻輳最適化（quadratic congestion optimization）に基づいて、グローバル経路指定に対して層ごとにワイヤ・スプレッディングおよびワイヤ拡幅（wire widening）を実施する。その後に続いて、ワイヤ・スプレッディングおよびワイヤ拡幅の結果を使用して、タイミング・クロージャ（timing closure）すなわちタイミング収束がグローバル経路指定に対して実施される。次いで、クリティカル・エリア歩留まりモデルを使用して、経路指定後の配線幅およびワイヤ・スプレッディング調節が行われる。
【０００５】
経路指定後配線幅調節を行ったとき、この方法は、修正済配線幅と、ワイヤ間の修正済間隔とを生成する。経路指定後の配線幅および長さ調節を行うことにより、ワイヤ幅とワイヤ間隔との折り合いがつけられる。経路指定後の配線幅および長さ調節を行うことにより、配線経路の相対的位置を変更することが回避される。
【０００６】
したがって、本発明の実施形態は、集積回路設計内の初期配線経路を設計し、初期配線幅と、配線経路の初期形状および位置とを確立する。初期配線幅を調節するとき、この方法は、修正済配線経路を生成する。一実施形態では、配線幅のみが修正され、修正済配線経路は、配線経路の初期形状および相対的位置を維持する。代替実施形態では、この方法は、初期配線幅を調節し、配線経路間の間隔を調節して、修正済配線経路を生成する。どちらの実施形態でも、この方法は、最適化された歩留まりを生み出す最終的配線経路を選択する最適化プロセスを修正済配線経路に対して実施する。
【０００７】
最適化プロセスは、不規則欠陥の可能性を推定すること、および不規則結果の可能性に基づいて不規則欠陥歩留まりを計算することを含む。初期配線幅の調節によって修正済配線幅が生成され、不規則欠陥の可能性の推定は、修正済配線幅に基づく。最適化プロセスは、ワイヤ幅とワイヤ間隔との間の折り合いをつける。調節および最適化プロセスは、集積回路設計の異なる層について増分式に実施される。
【０００８】
不規則欠陥歩留まりを正確にモデル化するために、本発明は、S. Gandemer,B. C. Tremintin, and J. J. Charlot, "Critical area and critical levelscalculations in IC yield modeling," IEEE J. Solid-State Circuits, Vol. 35,No. 3, pp. 158-166, Feb. 1988のクリティカル・エリア分析（ＣＡＡ）の概念を使用する。クリティカル・エリアは、不規則欠陥に対するＶＬＳＩレイアウトの感受性の数学的尺度である。クリティカル・エリア・モデルは、相異なる回路網内のレイアウト形状をブリッジするショートと、形状を通過しそれによって電気的開路を生成する開路と、層間接続を流れる電流を遮断するバイア遮断とを明らかにする。本開示で提示される配線最適化技法は、ショートおよび開路に対処する。
【０００９】
より具体的には、歩留まりのためにワイヤ幅および間隔を最適化すると共に、タイミング収束および信号保全性の課題を達成するグローバル経路指定方法を以下で説明する。経路指定後最適化ステップでは、本発明は、ワイヤ幅、長さ、および間隔に関連する費用関数を導出し、制約を形成して、設計規則および接続性を表現する。次いで、本発明は、既存の位相空間関係を維持しながら最適化を行う（例えば、ワイヤを再経路指定することなくバイアを移動することができる）。その結果、設計の全クリティカル・エリアが低減されるように幅および間隔が調節された１組のワイヤが得られる。グローバル経路指定解決策を用いずに、それ自体に対して経路指定後最適化ステップを使用することができる。したがって、設計を経路指定するのに使用された経路指定技術の如何に関わらず、ある程度の歩留まり最適化が可能となる。
【００１０】
本発明の上記およびその他の態様および目的は、以下の説明および添付の図面と共に考慮するときにより良く理解される。しかし、以下の説明は本発明の好ましい実施形態およびその多数の具体的な詳細を示しているが、限定ではなく、例示として与えたものであることを理解されたい。本発明の精神から逸脱することなく、本発明の範囲内で多数の変更および修正を行うことができ、本発明はそのようなすべての修正形態を含む。
【００１１】
図面を参照しながら、以下の詳細な説明から本発明をより良く理解できるであろう。
【発明を実施するための最良の形態】
【００１２】
添付の図面に示し、以下の説明で詳述される非限定的な実施形態を参照しながら、本発明ならびにその様々な特徴および有利な詳細をより完全に説明する。図面に示す特徴は必ずしも原寸に比例して描いているわけではないことに留意されたい。本発明を不必要に不明瞭にしないように、周知の構成要素および処理技法の説明を省略する。本明細書で使用する例は、本発明を実施することのできる方式の理解を容易にし、さらに、当業者が本発明を実施することを可能にするためのものに過ぎない。したがって、本発明の範囲を限定するものとして例を解釈すべきではない。
【００１３】
上述のように、開路（意図せずに切断された回路）の可能性を低減するより効果的な技法が明らかに求められている。本発明の実施形態は、レイアウト内のワイヤ幅を修正して、開路の可能性の低減を達成する。ワイヤ幅制御は自動経路指定の標準部分であるが、伝統的に、ルータが、歩留まりのためではなく信号保全性のためにワイヤ幅を選んでいた。さらに、様々な幅の配線は一般により難しい経路指定問題を引き起こすので、ルータは、広いワイヤを使用することを避ける傾向がある。一般には、ルータは、歩留まり向上のためにワイヤの幅を拡大しない。従来の工具は、歩留まり最適化のための経路指定後ワイヤ幅調節を実施しない。過去における主眼はワイヤ・スプレッディングおよび冗長バイア挿入であったからである。
【００１４】
歩留まり最適化のための開路およびショートの処理に必要な修正は矛盾する。ワイヤを拡散させることにより、間隔が広がり、全ワイヤ長が増大する可能性があるが、ワイヤを広げることにより、間隔が狭まる。本発明は、ワイヤ幅とワイヤ間隔との間の歩留まりの折り合いを考慮に入れたモデルを提示し、そのモデルが、ワイヤ幅または間隔あるいはその両方を調節するような歩留まり最適化を行う方法を開発するのに使用される。
【００１５】
不規則欠陥歩留まりを正確にモデル化するために、本発明は、以下でより詳細に説明するクリティカル・エリアの概念を使用する。最終的に、本発明は、クリティカル・エリア・モデルを使用して、ワイヤ幅およびスペースの調節を導く。より具体的には、歩留まりに関してワイヤ幅および間隔を最適化すると共に、タイミング収束および信号保全性の課題を達成するグローバル経路指定方法を以下で説明する。本発明は、詳細ルータがグローバル・ルータで選択された基本経路指定経路、層、および幅に追従するという理解に基づいている。経路指定後の最適化ステップでは、本発明は、ワイヤ幅、長さ、および間隔に関連する費用関数を導出し、設計規則および接続性を表現するための制約を形成する。次いで、本発明は、既存の位相空間関係を維持しながら最適化を行う（例えば、ワイヤを再経路指定することなくバイアを移動することができる）。その結果、設計の全クリティカル・エリアを低減するように幅および間隔が調節された１組のワイヤが得られる。グローバル経路指定解決策を用いずに、それ自体に対して経路指定後最適化ステップを使用することができる。したがって、設計を経路指定するのに使用された経路指定技術の如何に関わらず、ある程度の歩留まり最適化が可能となる。
【００１６】
より具体的には、図面を参照すると、図１に、本発明の一実施形態が示されている。より具体的には、図１は、経路指定済み設計での配線の幅および間隔が最適化される一実施形態を示す。具体的には、図１は、集積回路内の初期配線経路の設計に関する一実施形態を示す。ステップ１００では、この方法は、輻輳制約、電圧／電流要件、およびエリア使用法を満たす経路を配線するための初期（３次元）詳細経路指定を実施することで始まる。次いで、詳細な経路指定の歩留まり駆動間隔および幅調節（yield-driven spacing and width adjustment）がステップ１０２で実施される。
【００１７】
代替実施形態では、この方法は、初期配線幅を調節し、配線経路間の間隔を調節して、修正済配線経路を生成する。そのような一実施形態を図２に示す。より具体的には、ステップ２００では、この方法は初期配線経路を設計することで始まり、初期配線経路は、初期配線幅と配線経路の初期形状および位置とを確立する。次いで、電圧／電流要件を最適化するように調節を行う、エリア使用法を最適化する（ステップ２０２）などの他の活動が実施される。ステップ２０４では、本発明は、例えば２次輻輳目標を最適化する、フロー・ベースの１次元スプレッディングを実施する。ステップ２０６は、グローバル経路指定のタイミング収束を表す。次いで、ステップ２０８では、この方法は、初期配線幅および配線間隔を調節する。ステップ２０８は修正済配線経路を生成する。この実施形態では、やはり配線形状または位置を変更することなく、配線幅およびワイヤ間の間隔だけが修正される。言い換えれば、この実施形態は、経路指定プロセス中に歩留まりを最適するためにワイヤ幅およびワイヤ間隔の調節を含む。次いでこの方法は、最適化された歩留まりを生み出す最終的配線経路を選択する歩留まり駆動最適化プロセス（ステップ２１０）を修正済配線経路に対して実施する。
【００１８】
初期配線幅の調節は修正済配線幅を生成し、初期配線間隔の調節（ステップ２０８）は修正済配線間隔を生成する。調節および最適化プロセスは、集積回路設計の異なるレベルについて増分式に実施することができる。したがって、本発明の実施形態は、配線輻輳制約を満たす初期グローバル経路指定（２００）を実施する方法を提示する。グローバル経路指定（２００）の一部として、この方法は、例えば２次輻輳最適化に基づいて、グローバル経路に対して（層ごとに）ワイヤ・スプレッディングおよびワイヤ拡幅を実施する。ワイヤ・スプレッディングおよびワイヤ拡幅の結果を使用して、タイミング収束（２０６）がグローバル経路に対して実施される。クリティカル・エリア歩留まりモデルに基づく最適化を使用して、経路指定後配線幅およびワイヤ・スプレッディング（２０８）調節が行われる。配線幅および間隔の調節により、ワイヤ幅とワイヤ間隔との間の折り合いがつけられる。
【００１９】
グローバル経路指定（２００）に対して多くの手法がある。グローバル経路指定のための基本的な数学的定式化は、線形目標を用いる多種フロー・ベースの方法を使用する。この定式化は、図２に示すように目標関数を使用して拡張することができる。図１に示す実施形態では、完全な初期グローバル経路指定が、好ましい任意の方法によって実施され、次いで、歩留まり目標が１度に１層ずつ最適化される。図１に示す実施形態は、容易に並列化可能であるという利点を有し、経路探索を必要としない。
【００２０】
したがって、例えば、図２に示す実施形態は、図３に示すような単純化した多種フロー問題に基づく定式化を使用することができる。この定式化は、各配線網Ｎｉについて単一の商品を割り当てることができ、問題は、図３の注目の層上のその配線網のワイヤの間隔全体にわたってその商品についてのフローを見つけることである。トラックはグローバル・セルの行と定義される。配線網をグローバル・セルのいずれかで経路指定することができるので、各配線網Ｎｉおよびグローバル・セルＴｋについて、フロー変数Ｆｉｋが作成される。トラック割当てを導くために、各配線網Ｎｉについて、各トラックＴｋ上の経路指定の費用が存在し、それをＷｉｋと表す。最適化の目標は、
ΣＡｉｋ＊Ｆｉｋ＋ΣＳｋ＊（ΣＦｉｋ）２を最小限に抑えることである。
【００２１】
線形重みＡｉｋおよび２次重みＳｋは、歩留まりに対するワイヤ長と間隔の寄与の折り合いを最適につけるように選択される。２次項は各トラックの全輻輳を不利にし、直接的に輻輳の拡散を引き起こす。これらの２つの定数に対する値が、以下の説明で示すＦｓｈｏｒｔｓ関数およびＦｏｐｅｎｓ関数から導出される。
【００２２】
トラックＴｋへの配線網Ｎｉの割当ては、［０，１］変数としてモデル化される。したがって、配線網ＮｉをトラックＴｋに割り当てるべきである場合、Ｆｉｋ＝１であり、そうでない場合、Ｆｉｋ＝０である。これにより制約が導入される。
Ｃ１）０≦Ｆｉｋ≦１、かつ
Ｃ２）Ｆｉｋは整数
【００２３】
１度に配線網の単一のセグメントが経路指定されるので、配線網当たりのフロー数は１を超えない。これにより、各配線網Ｎｉについてのマス・バランス制約が生じる。
Ｃ３）各配線網Ｎｉについて、ΣＦｉｋ＝１
【００２４】
あらゆるトラックＴｋについて、各スロットＳｊで、トラックに割り当てられた配線網数だけがトラックの容量を超えることができない。これにより、バンドル制約が生じる。
Ｃ４）あらゆるスロットＳｊ、あらゆるトラックＴｋ、および幅Ｗｉを有するあらゆる配線網Ｎｉについて、０≦ΣＷｉ＊Ｆｉｋ≦Ｃｋ
【００２５】
一般には、各スロットＳｊについて１組のＦｉｋがあり、それをＦｉｋ（ｊ）と書くことができる。このモデルは、配線網が単一のトラックに割り当てられるように制限される点で解を限定する。グローバル経路指定で対処される従来の問題を解決し、次いでそれと共に、得られた配線を歩留まりに関して最適化するために、連続する経路指定ステージの設計が意図される。ワイヤ・スプレッディングおよびワイヤ拡大がどちらも考慮に入れられる。上記で議論したワイヤ・サイズ調節のための経路指定後最適化ステップは、多くの異なる方式で実施することができる。最適化の一例を以下で議論する。圧縮ベースのレイアウト・オプティマイザを使用して、この方法は、ある方向でレイアウト内の配線および遮断形状を走査することができる。この方向に垂直なワイヤについて、幅およびスペースが修正され、この走査方向に平行なワイヤについて、長さが修正される。
【００２６】
次いで、修正が可能なワイヤに、事前定義されたジョグ・ポイントを組み込むことができる。これらのジョグ・ポイントは、ロング・ウェイ・ワイヤ・セグメントが挿入される場所である。グランド規則を表すために縁部間で制約を形成することができる。主に、最適化中に間隔規則および幅規則を実施すべきである。電気的接続性を維持するために、制約を縁部間およびレイアウト・オブジェクト（ワイヤ、バイア、ピン）間で形成することができる。さらに、方法要件を表す他の制約を形成することができる（フローズン配線網、ピン制約など）。
【００２７】
走査方向に垂直な各ワイヤ・セグメントについて、この方法は、縁部の対間の目標を形成し、クリティカル・エリアをモデル化する。隣接するワイヤのない単一の対のワイヤおよび所与の配線ピッチ（ｐ）について、ワイヤの幅（ｗ）および間隔（ｓ）を図４に示すように設定することができる。図４では、Ｃ（ｓ，ｗ）をこうした２つのワイヤのクリティカル・エリアの１次推定であるとすると、
Ｃ（ｓ，ｗ）＝ＫｓｈｏｒｔＬ／ｓ＋ＫｏｐｅｎＬ／ｗ
＝ＫｓｈｏｒｔＬ／（ｐ−ｗ）＋ＫｏｐｅｎＬ／ｗ
であり、Ｗ＝ｐ／［１＋ｓｑｒｔ（Ｋｓｈｏｒｔ／Ｋｏｐｅｎ）］
であるとき、Ｃ（ｓ，ｗ）が最小限に抑えられる。
【００２８】
ここで、Ｋｓｈｏｒｔは、当該層上のワイヤに関するショートについての欠陥密度を表す定数であり、Ｋｏｐｅｎは、その層上のワイヤに関する開路についての欠陥密度である。これらの定数は、設計が製作される製作プロセスに特有のものである。２つの固定の対象間の１群の平行なワイヤについて、幅およびスペースに関する同様の式を導出することができる。ワイヤ長に関連するクリティカル・エリアをモデル化するために、単純な線形関数を使用することができる。
【００２９】
上述の重み因子および制約を使用して、すべての費用関数が組み合わされ、最適化される。費用関数および制約はすべて区分的線形関数であり、したがって区分的線形条件付き最適化ルーチンを使用することができる。あるいは、費用関数および制約を線形にすることもでき、標準線形プログラミング・パッケージを使用することができる。次いで、垂直方向に処理を反復することができる。
【００３０】
上述のグローバル経路指定中の不規則欠陥歩留まりのモデル化に関して、本明細書のこの部分では、グローバル経路指定アルゴリズムを導く費用関数および方法を記載する。そのような目標は、局所的に最適な歩留まりの経路を見つけるアルゴリズムを導く。次いでこれらの目標は、グローバル経路指定中にワイヤを拡散するフロー方法で使用される。
【００３１】
この目標の原理は、クリティカル・エリアの推定に基づく。クリティカル・エリアは、集積回路（ＩＣ）のレイアウト内の不規則欠陥の可能性を推定するのに使用される周知のメトリックである。
【００３２】
クリティカル・エリア分析を使用して、以下のようにレイアウト歩留まりを推定することができる。
【００３３】
１．何らかの故障構造による、形状に対して、または形状間で生じる故障の可能性による故障の確率を計算する。
【００３４】
２．故障の確率を故障欠陥密度ｆａｂ定数（fault defect densityfab constant）に掛け、故障推定を生成する。故障量は歩留まりの対数に比例する。この量は平均故障とも呼ばれる。
【００３５】
３．距離Ｓだけ隔てられた、幅Ｗ、平行ランの長さＬの１組の平行ワイヤ間のショートによる平均故障は、
【００３６】
【数１】
0005208404.tif 000002
【００３７】
４．同じ１組のワイヤの開路による平均故障は、
【００３８】
【数２】
0005208404.tif 000003
【００３９】
５．紛失／遮断されたバイアによる平均故障を、バイア当たりの定数で近似することができる。この定数は、バイアが冗長であるかどうか、すなわちバイアが複数の「カット」で構築されるかどうかに応じて小さくなる。
【００４０】
６．全平均故障は、すべての欠陥構造による故障の和である。
【００４１】
７．全故障に関する負の２項近似式を使用して、歩留まりの推定を得ることができる。
【００４２】
【数３】
0005208404.tif 000004
【００４３】
全故障メトリックＦｔｏｔａｌは、歩留まりの予測子であり、レイアウト最適化で有用であることが判明している。この関数を単純化して使用および計算を単純化することができ、それによって全故障メトリックは、ワイヤの幅（Ｗ）および長さ（Ｌ）、隣接するワイヤとの共通ラン・レングス（Ｌｃ）、ならびに隣接するワイヤとの間隔（Ｓ）のみの関数である。この関数でＬｃおよびＬは同一であることに留意されたい。Ｆｔｏｔａｌに関して得られる関数は、
【００４４】
【数４】
0005208404.tif 000005
【００４５】
定数Ｋｖｉａは、単一（すなわち非冗長）バイアが正しく製造されない確率であり、Ｎｖｉａは、考慮している配線中の単一バイアの数である。さらに、最適化したとき、全故障メトリックは、ワイヤ長と隣接低減（adjacency reduction）との間の平衡を実現し、したがってキャパシタンス低減のための単純な１次メトリックである。キャパシタンス低減の応用例では、より正確なモデルが、経路指定上面および下面内の配線の平均密度を測定することにより、定数Ｋを調節して、アップ・キャパシタンスおよびダウン・キャパシタンスを補償する。別の調節は、横方向キャパシタンス成分が１／Ｓのべき乗に比例する可能性があり、Ｓが十分大きい場合に消失する可能性があることでよい。
【００４６】
雑音低減および目標のキャパシタンス低減のために、配線網隣接情報に基づいてＫ定数を調節することにより、「不良」キャパシタンスの成分だけを含むようにＦｔｏｔａｌ関数を修正することができる。一般にはキャパシタンス低減は雑音を低減し、性能を向上させるので、本明細書に記載の技法は、製造歩留まりを向上させることに加えて、性能の助けとなるという副次的利点を有する。
【００４７】
Ｆｔｏｔａｌメトリックを最小限に抑える経路を見つけることを可能にするタイル・ベースのルータに対する拡張を以下で説明する。
【００４８】
ベース・グローバル経路指定アルゴリズムは以下のステップを含む。
【００４９】
１．経路指定領域をタイル（グローバル経路指定セル、すなわち「ｇｃｅｌｌ」）に分割する
【００５０】
２．ｇｃｅｌｌ内およびｇｃｅｌｌ間の経路指定容量を計算する
【００５１】
３．容量制約を満たすと共に、ｇｃｅｌｌを通じて配線網を経路指定する
【００５２】
４．ルータ目標は、通常はワイヤ長およびバイア・カウントを最小限に抑えることである
【００５３】
得られるグローバル経路指定は１つの特徴を有する。ｇｃｅｌｌはチップの任意に大きな面積を抽象化し、グローバル・ルータは遮断および配線網間遮断の問題を直接的に考慮することができないからである。その代わりに、ｇｃｅｌｌは、概ね合法的な経路発見に焦点を当てる。こうした理由で、グローバル経路指定は高速なプロセスであることが知られている。
【００５４】
このセクションの残りでは、故障（Ｆｔｏｔａｌ）メトリックを最適化するように意図されるグローバル経路指定問題に対する拡張を説明する。故障目標の開路部分は、ワイヤ長およびバイア・カウント最小化目標に等しいように見える。しかし、ショート目標は十分に表現されない。以下のモデルは、歩留まり目標のこの部分を組み込む。
【００５５】
歩留まり目標のショート部分は、共通ランＬおよびワイヤ間の間隔Ｓの関数である。共通ランＬは、グローバル経路ではワイヤのワイヤ長であると推定することができる。ワイヤ間の間隔は、最小クリアランス規則のように小さくてよい。すべてのワイヤを最小間隔に詰め込むべき場合、ショート歩留まり目標はワイヤ長に比例し、したがってワイヤ長グローバル経路指定は十分である。しかし、最大のワイヤ間隔は、ワイヤが経路指定されるエリアの輻輳の関数である。幅Ｗｇのｇｃｅｌｌ内に幅ｗのｎ本のワイヤがあるとすると、これらのワイヤ間の最大スペース（Ｓｍａｘ）は、
【００５６】
【数５】
0005208404.tif 000006
【００５７】
したがって、このｇｃｅｌｌ内で経路指定されるすべてのワイヤが寄与する最小故障は、
【００５８】
【数６】
0005208404.tif 000007
【００５９】
比較のために、ｇｃｅｌｌを通じてｎ個の配線網を経路指定するときの、開路による故障費用は、
【００６０】
【数７】
0005208404.tif 000008
【００６１】
完全な故障ベースの目標は、
Ｆｔｏｔａｌ（ｇｃｅｌｌ）＝Ｆｓｈｏｒｔ（ｇｃｅｌｌ）＋Ｆｏｐｅｎ（ｇｃｅｌｌ）
【００６２】
ここでは、線形費用とは異なり、故障メトリックを用いるｇｃｅｌｌを通じての経路指定の費用は、どれほどの経路が既にｇｃｅｌｌ内にあるかに依存する。この目標の利点は、元の線形費用を含むことであり、したがってＫｓｈｏｒｔおよびＫｏｐｅｎを調節することにより、グローバル・レベルでのワイヤ・スプレッディングとワイヤ長との間の折り合いの調節が可能であることである。この費用の別の特徴は、過輻輳（over-congestion）を自然に不利にすることである。ｇｃｅｌｌ内のワイヤ幅の和がｇｃｅｌｌの幅と等しくなるｎｗ＝Ｗｇで、目標が無限となることに留意されたい。
【００６３】
不規則欠陥歩留まりを正確にモデル化するために、本発明は、クリティカル・エリアの概念を使用する。最終的に、本発明は、経路指定の前または後に、クリティカル・エリア・モデルに基づいて最適化を実施してワイヤ幅およびスペースを調節する。より具体的には、歩留まりのためにワイヤ幅および間隔を最適化すると共に、タイミング収束および信号保全性の課題を達成するグローバル経路指定方法を説明する。経路指定後最適化ステップでは、本発明は、ワイヤ幅、長さ、および間隔に関連する費用関数を導出し、制約を形成して、設計規則および接続性を表現する。次いで、本発明は、既存の位相空間関係を維持しながら最適化を行う（例えば、ワイヤを再経路指定することなくバイアを移動することができる）。その結果、設計の全クリティカル・エリアが最適化されるように幅および間隔が調節された１組のワイヤが得られる。グローバル経路指定解決策を用いずに、それ自体に対して経路指定後最適化ステップを使用することができる。したがって、設計を経路指定するのに使用された経路指定技術の如何に関わらず、ある程度の歩留まり最適化が可能となる。
【００６４】
本発明は、製造歩留まり認識（manufacturing-yieldawareness）をグローバル経路指定ステップに一体化し、配線ショートおよび開路が低減されるように経路を配置することを可能にする。本発明は、既に経路指定されている設計内の配線を、不規則欠陥ショートおよび開路に関して最適化することを可能にする。これらのどちらの場合にも、本発明は、経路指定中、または経路指定が完了した後に、ショートに対する感度と開路に対する感度との明示的な折り合いをつけることを可能にする。
【００６５】
好ましい実施形態によって本発明を説明したが、添付の特許請求の範囲の趣旨および範囲内の修正と共に本発明を実施できることを当業者は理解されよう。
【図面の簡単な説明】
【００６６】
【図１】本発明の方法を示す流れ図である。
【図２】本発明の好ましい方法を示す流れ図である。
【図３】フロー問題を示す略図である。
【図４】平行ワイヤの略図である。
【符号の説明】
【００６７】
ｐ  配線ピッチ
ｗ  ワイヤの幅
ｓ  ワイヤの間隔
Ｌ  ワイヤの長さ
【図１】
0005208404.tif 000009
【図２】
0005208404.tif 000010
【図３】
0005208404.tif 000011
【図４】
0005208404.tif 000012