(57)【要約】  半導体レイアウトの修正の方法、更に、半導体レイアウトの修正のためのシステム及びコンピュータプログラム製品を提供する。本発明は、半導体レイアウトの修正の方法を提供する。レイアウトは、コーナ及びエッジを有する半導体材料のオブジェクトを含む。本方法は、隣接するエッジ及び／又はコーナの間の関係を示す近接性と、どの境界内で近接性が有効であるかの修正に対する境界を定めるトリガと、半導体レイアウトに対する物理的要件を表す設計規則との組を受け取る段階（６１）を含む。本方法は、更に、受け取った近接性、トリガ、及び設計規則に基づいて、制約の組における各制約が近接性を変更することなく内部で半導体レイアウトを修正することができる限界を定める１組の制約を発生させる段階（６２）を含む。次に、修正された半導体レイアウトを得るための制約の組が解かれる（６３）。【選択図】図６
2010531505.tif 000002
【特許請求の範囲】
【請求項１】
コーナ及びエッジを有する半導体材料のオブジェクトを含む半導体レイアウトを修正する方法であって、
隣接するエッジ及び／又はコーナの間の関係を示す近接性と、どの境界内で該近接性が有効であるかの修正に対する境界を定めるトリガと、半導体レイアウトに対する物理的要件を表す設計規則との組を受け取る段階（６１）と、
前記受け取った近接性、トリガ、及び設計規則に基づいて、制約の組の各制約が該近接性を変更することなく内部で前記半導体レイアウトを修正することができる限界を定める１組の制約を発生させる段階（６２）と、
前記制約の組を解いて（６３）、修正された半導体レイアウトを得る段階と、
を含むことを特徴とする方法。
【請求項２】
前記オブジェクトのうちの特定の１つに対して移動の自由度を制限することにより前記半導体レイアウトの更なる最適化を禁止する少なくとも１つの重大制約を識別する段階（６４）と、
前記オブジェクトのうちの前記特定の１つに対して前記移動自由度を増大させるように前記トリガの少なくとも１つを適応させる段階（６５）と、
前記適応させたトリガに基づいて前記制約の組を再生する段階（６２）と、
前記再生された制約の組を解く段階（６３）と、
を更に含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記識別する段階（６４）、適応させる段階（６５）、再生する段階（６２）、及び解く段階（６３）は、所定の最適化基準が満たされるまで反復的に実行されることを特徴とする請求項２に記載の方法。
【請求項４】
前記適応させる段階（６５）は、トリガを除去、変更、又は追加する段階を含むことを特徴とする請求項２に記載の方法。
【請求項５】
前記適応させる段階（６５）は、前記除去、変更、又は追加されたトリガに関連するエッジに対する近接性を追加又は除去する段階を更に含むことを特徴とする請求項４に記載の方法。
【請求項６】
前記修正は、前記オブジェクトの２次元移動をもたらすことを特徴とする請求項１に記載の方法。
【請求項７】
前記制約の組を解く前記段階（６３）は、前記修正の後に前記レイアウトのサイズを最小にするために所定の最適化関数を適用する段階を含むことを特徴とする請求項１に記載の方法。
【請求項８】
半導体レイアウトの修正のためのコンピュータプログラム製品であって、
プロセッサに請求項１に記載の方法を実行させるように作動する、
ことを特徴とする製品。
【請求項９】
コーナ及びエッジを有する半導体材料のオブジェクトを含む半導体レイアウトの修正のためのシステムであって、
隣接するエッジ及び／又はコーナの間の関係を示す近接性と、どの境界内で該近接性が有効であるかの修正に対する境界を定めるトリガと、半導体レイアウトに対する物理的要件を表す設計規則との組を受け取るための入力部と、
前記受け取った近接性、トリガ、及び設計規則に基づいて、制約の組の各制約が該近接性を変更することなく内部で前記半導体レイアウトを修正することができる限界を定める１組の制約を発生させ、かつ
前記制約の組を解いて、修正された半導体レイアウトを得る、
ように構成されたプロセッサと、
を含むことを特徴とするシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、半導体レイアウトの修正の方法に関する。レイアウトは、コーナ及びエッジを有する半導体材料のオブジェクトを含む。本方法は、レイアウト表現を受け取る段階、レイアウトを修正することができる範囲を表す方程式を発生させる段階、及び修正レイアウトを得るために方程式を解く段階を含む。
本発明は、更に、半導体レイアウトの修正のためのシステム及びコンピュータプログラム製品に関する。
【背景技術】
【０００２】
半導体レイアウトは、導体又は半導体材料を通じて相互接続した半導体材料のオブジェクトを含む。一般的に、これらのオブジェクトは、エッジ及びコーナを有する多角形であり、これらは、２Ｄ座標系における座標を有する。オブジェクトは、異なる層内に置くことができ、レイアウトは３Ｄシステムになる。
レイアウト修正は、例えば、レイアウト移動、設計規則の固定化、又はレイアウト圧縮を伴う場合がある。レイアウトの圧縮は、半導体レイアウトのサイズを最小にする方法である。他の修正技術は、主にレイアウト圧縮に基づくが、別の最適化基準を有する。レイアウト圧縮システムでは、主な最適化基準は、レイアウトのサイズである。最適化は、１組の設計規則を考慮に入れながら実施される。半導体レイアウトは、設計規則として書かれたいくつかの設計基準、及び可能な付加的条な組の（局所的）制約を満たさなければならない。１Ｄ圧縮では、２つのパスでレイアウトが変更され、第１のパス中にエッジが１つの方向にのみ移動され、第２のパス中にエッジが他方の方向に移動される。このパス中に、所定の組の制約及び設計規則によるレイアウトに対する最適化問題は、一般的に、公知のアルゴリズムで解くことができる線形問題に変換される。
しかし、１つの方向における修正は、一部の欠点を有する。一方の方向における修正は、他方の方向における修正に対して影響を有する。問題が２つの異なる独立した最適化問題に分割されるので、１Ｄ修正の結果は、準最適である。更に、修正作業の結果は、いずれの方向が最初に修正されたかに依存し、２Ｄ設計規則及び制約は考慮されない。
【０００３】
ＵＳ２００３／００９７２８として公開され、Ｄａｖｉｄ  Ｐ．Ｍａｒｐｌｅによって出願された米国特許出願は、水平、垂直、及び対角の制約を考慮する２Ｄ圧縮法を説明している。対角制約は、本質的に非線形であり、従って、解くことが非常に困難である。圧縮を実施するのを可能にするために、非線形制約の線形近似が用いられる。次に、２Ｄ圧縮問題が線形解法を用いて解かれる。圧縮の後に、非線形関数の線形化が良好な推定ではないと思われる場合には、何らかの付加的な反復を実施して、レイアウトが補正される。
【０００４】
Ｍａｒｐｌｅの方法及び他の２Ｄ圧縮法の問題は、２Ｄ圧縮が多くの移動自由度を与え、従って、出力結果においてどのレイアウトオブジェクトが近傍になることになるかを「予測」することが困難であることである。近傍にあるものは、それらの間の最小距離のような制約を受ける必要がある。従って、理論的に、どのオブジェクトもどの他のオブジェクトの近傍になる可能性がある場合には、レイアウトオブジェクトの全ての対の間に制約を適用すべきである。従って、制約数の程度は、レイアウトオブジェクト数の二乗である。今日の大規模なチップ設計では、これは、多数の制約をもたらし、従って、今日のコンピュータ及びメモリに対して問題が大きくなり過ぎると考えられる。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】ＵＳ２００３／００９７２８
【特許文献２】欧州特許出願第０７１０４８６３号
【特許文献３】ＵＳ２００３／０００９７２８
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本発明の目的は、２Ｄレイアウト修正に適し、かつ妥当な数の制約を用いる半導体レイアウトの修正の方法を提供することである。本明細書における「妥当」は、制約数がレイアウトオブジェクト数の二乗の程度におけるものよりも有意に小さいことを意味する。
【課題を解決するための手段】
【０００７】
本発明の第１の態様によると、この目的は、コーナ及びエッジを有する半導体材料のオブジェクトを含む半導体レイアウトの修正の方法を提供することによって達成される。本方法は、隣接するエッジ及び／又はコーナの間の関係を示す近接性と、どの境界内で近接性が有効であるかの修正に対する境界を定めるトリガと、半導体レイアウトに対する物理的要件を表す設計規則との組を受け取る段階と、受け取った近接性、トリガ、及び設計規則に基づいて、制約の組における各制約が近接性を変更することなく内部で半導体レイアウトを修正することができる限界を定める１組の制約を発生させる段階と、制約の組を解いて修正された半導体レイアウトを得る段階とを含む。
【０００８】
近接性は、隣接するエッジ及び／又はコーナの間の関係である。トリガは、どの境界内でレイアウトを変更することができ、どの境界内で現在の組の近接性が有効であるかを表している。近接性は、直接の近傍の間にしか定義されないので、関係数は比較的小さく、オブジェクト数と線形に保たれる。欧州特許出願第０７１０４８６３号は、半導体レイアウトを走査し、近接性及びトリガをデータベースに記憶する方法及びシステムを説明している。上記特許出願はまた、近接性及びトリガの広範囲な説明を提供しており、この特許は、本明細書に引用によって含まれている。
【０００９】
設計規則を近接性に適用すると、制約が得られる。例示的設計規則は、２つのオブジェクトの間の最小空間を定めることができる。近接性の組は、そのような設計規則を適用すべきであるレイアウト内の位置を定める。近接性、近接性に関連するレイアウト情報、及び近接性に適用される設計規則は、合わせて制約を生じる。
制約は、トリガからも起因する。トリガは、内部で近接性の組がレイアウトのトポロジーの有効な表現を与える境界を定める。トリガに基づいて制約を発生させることにより、近接性の組が、レイアウト修正の後に有効のまま留まることが保証される。その結果、元のレイアウトでは直接の近傍ではないオブジェクト間の関係を考慮に入れなくてもよい。それによって解かれる制約の組は比較的小さくなる。次に、近接性、トリガ、及び設計規則から導出された制約の組が解かれ、解は、修正されたレイアウトを表している。
【００１０】
本発明による方法の好ましい実施形態は、オブジェクトのうちの特定の１つに対して移動の自由度を制限することにより半導体レイアウトの更なる最適化を禁止する少なくとも１つの重大制約を識別する段階と、オブジェクトのうちの特定の１つに対して移動の自由度を増大させるようにトリガのうちの少なくとも１つを適応させる段階と、適応させたトリガに基づいて制約の組を再生する段階と、再生された制約の組を解く段階とを更に含む。
【００１１】
本発明の方法では、半導体レイアウトにおけるオブジェクトは、開始位置から終了位置へと移動される。修正は、現在の制約の組内での更なる最適化がそれ以上できない時に停止する。制約は、オブジェクトが設計規則に違反する位置又は初期の近接性の組が有効ではない位置に移動されないことを保証する。修正が停止する時に、１つ又はそれよりも多くのオブジェクトは、もう少しのところで設計規則を破るか又はトリガをパスする位置まで移動されている場合がある。更なるレイアウト最適化を禁止するこれらの制約は、「重大制約」と呼ばれる。全ての重大制約を有するリストを「重大経路」と呼ぶ。近接性及びトリガの組は、次に、これらの重大制約のうちの少なくとも１つを除去し、より多くの移動自由度を与えるために変更することができる。好ましくは、制約の組は、最初に、重大制約を引き起こすトリガを除去又は変更することによって変更される。トリガを変更することにより、より多くの移動自由度、又は少なくとも好ましい方向におけるより多くの移動自由度が生じる。次に、近接性の組は、新しい移動自由度を用いる時に直接の近傍になる場合があるオブジェクト間の近接関係を含むように適応させる。この目的のために、変更又は省略されたトリガの周囲の区域は、近接性の組の変更に関して検査される。一部の近接性は、もはや関連がない場合があり、従って、除去することができる。新しい近接性及びトリガの組から、新しい制約の組が発生される。好ましくは、トリガ、近接性、及び／又は制約の適応化は、不用な計算を回避するために重大経路の周囲で局所的にのみ実施される。次に、変更された制約の組は、更に良好なレイアウトを得るために解かれる。好ましくは、以前の制約の組に対する解は、次の要求の組を解くための基準として用いられる。トリガ及び近接性の局所的適応化、制約の再生、及び再生された制約の組の求解は、好ましくは、最適化基準の所定の目標値を満たすレイアウト構成が得られるまで繰り返される。適応化は、好ましくは、自動システムによって実施されるが、操作者に対して判断を行い、システムに命令して適応化の１つ又はそれよりも多くを適用させるように要求することもできる。
【００１２】
本発明の第２の態様によると、コーナ及びエッジを有する半導体材料のオブジェクトを含む半導体レイアウトの修正のためのシステムが提供される。システムは、入力部及びプロセッサを含む。入力部は、隣接するエッジ及び／又はコーナの間の関係を示す近接性と、どの境界内で近接性が有効であるかの修正に対する境界を定めるトリガと、半導体レイアウトの物理的要件を表している設計規則との組を受け取るように構成される。プロセッサは、受け取った近接性、トリガ、及び設計規則に基づいて、制約の組の各制約が近接性を変更することなく内部で半導体レイアウトを修正することができる限界を定める制約の組を発生させ、かつ制約の組を解いて修正された半導体レイアウトを得るように構成される。
【図面の簡単な説明】
【００１３】
【図１】３つのオブジェクトを有する半導体レイアウトの一部を示す図である。
【図２】半導体レイアウトの修正を示す図である。
【図３】半導体レイアウトにおけるオブジェクトの２つの隣接するエッジを示す図である。
【図４】半導体レイアウトにおけるオブジェクトの２つの隣接するエッジを示す図である。
【図５】半導体レイアウトにおけるオブジェクトの２つの筋向かいのコーナを示す図である。
【図６】本発明による方法の実施形態の流れ図である。
【図７】半導体レイアウトの修正の後でトリガ及び近接性を適応させる例を示す図である。
【発明を実施するための形態】
【００１４】
図１は、３つのオブジェクト（１０、１１、１２）を有する２Ｄ半導体レイアウトの一部を示している。オブジェクト（１０、１１、１２）は、これらの機能に依存して導体、半導体、又は絶縁材料のものとすることができる。レイアウトは、例えば、トランジスタ、ワイヤ、抵抗器、及びコンデンサなどを含むことができる。図１では、オブジェクトは多角形として表されている。欧州特許出願第０７１０４８６３号に説明されている方法によると、レイアウトのトポロジーが、エッジ及び近接性と共にデータベースに記憶される。近接性（１３、１４、１５）は、直接の近傍であるエッジ又はコーナの間の関係である。図１は、図示のオブジェクト（１０、１１、１２）のエッジ及びコーナの間の近接関係（１３、１４、１５）の一部を示している。
【００１５】
本発明による方法は、直接の近傍の間の相互作用が、他のオブジェクトの間の相互作用よりも遥かに重大であるということを利用する。レイアウトを修正する時には、直接の近傍の間の相互作用に対する影響が特に考えられている。レイアウト修正システムは、データベースから近接性の組を受け取り、これらの近接性を解析して設計規則のインスタンスを得る。例えば、設計規則は、２つのオブジェクト（１０、１２）のエッジ間の最短距離を規定することができる。近接性データベースは、そのようなエッジ間の近接性１３を含む。近接性の組を解析することにより、エッジＬとエッジＱの間の設計規則のインスタンスが求められる。エッジＬ及びＱの互いに対する移動を制限する制約が発生される。レイアウトの解析の後に、得られた制約の組は解かれて、これらの制約に違反せず、従って、設計規則にも違反しない修正レイアウトが得られる。
【００１６】
同様に図１は、エッジＬ及びＲの２つの筋向かいのコーナの間の近接性１４を示している。２つの筋向かいのエッジの間の距離に対する設計規則は、両方の方向（ｘ及びｙ）における１００ｎｍの最短距離を規定することができる。近接関係１４及び設計規則の組合せは、以下の２つの制約をもたらすことができる。
ｘＲ−ｘＬ≧１００
ｙＴ−ｙＢ≧１００
図１は、１つのオブジェクト１１の２つの対向するエッジの間の近接性１５を示している。オブジェクト１１の最小及び／又は最大幅に対する設計規則は、エッジの移動自由度を制限する制約を生じる。
【００１７】
制約は、設計規則のみから導出されるわけではない。図２は、半導体レイアウトの修正を示している。最初の状況では、オブジェクト２２は、オブジェクト２０とオブジェクト２１の間に位置する。オブジェクト２１及び２２の隣接するエッジの間で近接関係２６が存在する。オブジェクト２１が、その新しい位置に移動された時に、対応するエッジが直接の近傍ではなくなるので、近接性２６は消失する。更に、オブジェクト２１のエッジ又はコーナとオブジェクト２０及び２２のエッジ又はコーナとの新しい関係を定めるために、新しいトリガ２４及び２７が必要である。オブジェクト２１内の近接関係２５は、オブジェクト２１のその新しい位置への移動によって影響を受けない。オブジェクト２１は、オブジェクト２２を超えて移動した時にオブジェクト２０に接近する。最初の状況では、オブジェクト２０とオブジェクト２１の間には近接性が適用されず、従って、オブジェクト２１がオブジェクト２０に接近し過ぎるのを防止する制約も発生されない。
【００１８】
オブジェクト２１を移動する時の設計規則違反の可能性を防止するには、オブジェクト２１の移動自由度を制限しなくてはならない。この制限は、トリガに基づいて付加的制約を追加することによって実施される。トリガは、超えた場合に対応する近接性が無効になり、レイアウトトポロジーが変更されるレイアウト変更に対する限界を定める。トリガは、記憶された対応するエッジ及びコーナの近接性及び相対位置に基づいて判断される。本発明によると、トリガは、近接性と共にデータベースから受け取ることができる。代替的に、トリガは、レイアウト修正の方法の一部として受け取られたレイアウト情報から発生される。
【００１９】
図３は、半導体レイアウトにおけるオブジェクトの２つの隣接するエッジＬ及びＲをこれらに関連付けられた近接性３１及びトリガ３２、３３、３４と共に示す。最初の制約は、近接性３１及び設計規則に基づいて発生させることができる。
ｘＲ−ｘＬ≧５０
この最初の制約は、エッジＲとエッジＬとが互いに接近し過ぎるのを防止する。例えば、エッジＲが、コーナＬｔｏｐを超えて上がると、近接性３１は消失し、レイアウトトポロジーが変化する。この移動は、トリガ３３を定め、トリガ３３及びそれに対応するエッジから制約を導出することによって防止することができる。
ｙＲｂｏｔｔｏｍ≦ｙＬｔｏｐ
【００２０】
付加的制約は、コーナＲｔｏｐをコーナＬｔｏｐの上に、コーナＲｂｏｔｔｏｍをコーナＬｂｏｔｔｏｍの上に保つことができる。
ｙＲｔｏｐ≧ｙＬｔｏｐ
ｙＲｂｏｔｔｏｍ≧ｙＬｂｏｔｔｏｍ
最後の制約は、エッジＬの長さが可変の場合にのみ必要である。エッジＬの高さが一定に留まる場合には、第３の制約（ｙＲｔｏｐ≧ｙＬｔｏｐ）は、コーナＲｂｏｔｔｏｍがＬｂｏｔｔｏｍよりも下がることも防止する。
【００２１】
図４は、半導体レイアウトにおけるオブジェクトの２つの隣接するエッジＬ及びＲを有する別の状況をこれらに関連付けられた近接性４１及びトリガ４２、４３と共に示す。以下の３つの制約は、エッジＲの全体が、右側にエッジＬに対向して５０ｎｍの最短距離で留まることを保証する。
ｙＲｔｏｐ≦ｙＬｔｏｐ
ｙＲｂｏｔｔｏｍ≧ｙＬｂｏｔｔｏｍ
ｘＲ−ｘＬ≧５０
【００２２】
図５は、半導体レイアウトにおけるオブジェクトの２つの筋向かいのコーナＬｔｏｐ及びＲｂｏｔｔｏｍをこれらに関連付けられた近接性５１及びトリガ５２、５３と共に示す。ＲｂｏｔｔｏｍをＬｔｏｐの斜め上に保つには、以下の２つの制約で十分である。
ｘＲ＞ｘＬ
ｙＲｂｏｔｔｏｍ＞ｙＬｔｏｐ
これらの制約は、それぞれトリガ５２及び５３に起因する。設計規則は、少なくとも１つの方向の最短距離が４０ｎｍであることを付加的に規定することができる。この設計規則は、少なくとも一方を違反することができない以下の２つの制約を生じる。
ｘＲ−ｘＬ≧４０
ｙＲｂｏｔｔｏｍ−ｙＬｔｏｐ≧４０
【００２３】
図５の陰付き区域は、コーナＲｂｏｔｔｏｍが、上述の制約の一方を違反することになる区域を示している。ユークリッド距離規則の場合には、これらの最後の２つの方程式は準最適であり、ユークリッド（２次）距離方程式を用いると、恐らくより小さい結果を得ることができる。２次方程式は、非線形解法を用いて、又は２次方程式を最初に線形化することによって解くことができる（ＵＳ２００３／０００９７２８におけるものと同様に）。
【００２４】
図６は、本発明による方法の実施形態の流れ図を示している。開始段階６０中に、一部の開始パラメータが定められる。そのような開始パラメータは、解決される修正問題の種類（例えば、圧縮、移動）、レイアウトサイズ、出力優先度、入力データの記憶場所などを含むことができる。
データ入力段階６１では、レイアウト修正システムは、近接性、トリガ、及び設計規則の組を受け取る。近接性は、レイアウトを走査した後にシステム自体の中に記憶されたデータベースから得ることができる。代替的に、レイアウトの走査は、別々のシステムによって実施することができ、近接性データは、外部供給源から得ることができる。エッジ間の近接性と共に、材料、及び近接性が適用される位置のトポロジーに関する情報を記憶することができる。そのような情報は、近接関係の種類の定義（空間、幅、延び、重複）を含むことができる。トリガは、近接性と共に受け取ることができ、又はシステムは、受け取った近接性及び他のレイアウト情報に基づいてトリガを判断することができる。近接性及びトリガは、レイアウトのトポロジーを表す情報である。同様にシステムは、設計規則を受け取る。計画された修正に対する特定の設計規則は、半導体チップの製造業者が供給することができ、又は標準の設計規則を用いることができる。
【００２５】
制約発生段階６２では、データ入力段階６１において受け取られた情報が処理される。システムは、設計規則のインスタンスを得るために近接性の組を通して検索を行う。設計規則を適用される位置では、この位置の近接関係に対応するエッジの移動自由度を制限する方程式が案出される。図３、図４、及び図５を参照して上述したように、方程式は、トリガからも導出される。方程式の組には、レイアウト修正操作の目的に依存して最適化関数が補足される。レイアウト圧縮システムでは、主な最適化基準は、レイアウトサイズである。
【００２６】
求解段階６３では、方程式は、１次元又は２次元レイアウト変更によって解くことができる。求解段階６３は、現在の制約の組内で最適化基準が満たされると終了する。例えば、レイアウト圧縮は、いかなるレイアウト変更も制約を違反せずにレイアウトサイズをそれ以上縮小することができない時に終了する。
一般的に、求解は、１つ又はそれよりも多くの制約が１つ又はそれよりも多くのオブジェクトの移動を好ましい方向に制限する点で停止する。例えば、レイアウトの圧縮中に、第１のオブジェクトは、第２のオブジェクトの７０ｎｍ上から第２のオブジェクトの５０ｎｍ上まで下げられる。設計規則は、２つのオブジェクトの間で５０ｎｍの最小距離を規定することができる。従って、設計規則及びオブジェクトに対応する制約は、第１のオブジェクトをそれよりも下げることを禁止する。従って、この制約は厳しい制約と呼ばれる。いかなる更なるレイアウト変更もレイアウトサイズを縮小することができない場合には、解法は、制約を違反することなく停止される。更なるレイアウト最適化を禁止するこれらの厳しい制約を「重大制約」と呼ぶ。
【００２７】
結果解析段階６４では、重大制約が識別され、全ての重大制約のリスト（以下「重大経路」と呼ぶ）が作られる。厳しい制約の一部は、設計規則に起因する距離制約であることになる。設計規則が変更されない限り、これらの制約を除去することはできない。一般的に、設計規則は、変更してはならない固定規則である。しかし、時によっては、設計規則は、同時に満たすことができない衝突する制約を招く場合がある。システムは、任意的に、ユーザに照会が行われた後に設計規則を変更又は削除することができる。設計規則は、レイアウト内のいずれかを特定の場所でしか変更することができない。他の重大制約は、トリガによって引き起こされる。トリガは、設計規則との関係を持たず、省略された場合に必ずしも設計規則違反を生じるわけではない。これらのトリガ（トリガの一部）を省略又は変更した後には、レイアウトオブジェクトの移動自由度が変化し、レイアウトを元の制限を超えて修正することができる。元の境界を超えてオブジェクトを移動することにより、レイアウトの更なる最適化をもたらすことができる。
【００２８】
トリガは、近接性の組がその間で有効である境界を定める。トリガを削除又は変更した後に、レイアウト変更の余地が存在する場合がある。設計規則違反を招くことなくレイアウトを安全に変更するために、用いられる基準に従って新しい近接性及び制約を作成する必要があり、冗長なものを削除すべきである。適応化段階６５では、トリガ調節の結果が計算される。好ましくは、近接性の適応化は、変更されたトリガの隣接場所において局所的にのみ実施される。近接性の組を局所的にしか適応させないことにより、時間を消費する完全なレイアウト走査が回避される。トリガを除去／変更した後に再走査を行う区域を選択する良い方法は、トリガに関連付けられたオブジェクト及びこれらのオブジェクトの直接の近傍だけを考えることである。適応化段階６５中にはレイアウトは修正されず、近接性、トリガ、及び制約のみが修正されることに注意されたい。
【００２９】
この後、適応済み近接性及びトリガの組は、任意的に適応済み設計規則の組と共に、適応済み情報を入力データとして用いて制約発生段階６２を繰り返すために用いられる。次に、再生された制約の組は、求解段階６３において解かれ、その結果は、結果解析段階６４において解析される。この反復工程は、修正が望ましい結果を生じるまで、又はレイアウトの更なる最適化がそれ以上できなくなるまで繰り返される。
【００３０】
図７は、半導体レイアウトの修正の後にトリガ及び近接性を適応させる段階の例を示している。本発明による方法のこの例示的な実施形態では、第１のオブジェクト７１は、第２のオブジェクト７２に対して平行に下がっている。トリガ７３に起因する制約は、第１のオブジェクト７１の底部エッジを第２のオブジェクト７２の底部エッジの上に保つ。その結果、第１のオブジェクト７１は、第２のオブジェクト７２の右側に保たれる。本発明による修正ルーチンが一度実施された後には、第１のオブジェクト７１は、第１のオブジェクト７１の底部エッジが第２のオブジェクト７２の右底部エッジと同じ高さである点まで正確に下げられている。第１のオブジェクト７１が更に下げられることになる場合には、元の近接性はもはや有効ではなくなる。このトリガ７３に起因する制約が「重大経路」上にあり、すなわち、レイアウトの更なる最適化を禁止する場合には、この制約は重大制約であり、それを除去又は変更した方が良い場合がある。
【００３１】
第１のオブジェクトを更に一層下げ、それによって制約に違反することは、即座に設計規則違反を生じることにはならない。従って、トリガ７３を変更又は除去することができる。このイベントでは、元の制約（底部２≦底部１）は、新しい制約（底部２≧底部１）に変更され、第１のオブジェクト７１の底部エッジは、第２のオブジェクト７２の底部エッジよりも下がることが許される。しかし、第１のオブジェクト７１を元の制約を超えて移動することにより、新しい近接関係７４が確実に生じる。第１のオブジェクト７１が第２のオブジェクト７２の下に位置するオブジェクトに接近し過ぎるのを回避するために、これらの新しい近接関係７４に基づいて、新しい制約が発生される。この目的のために、第１のオブジェクト７１は、限りなく小さい距離エプシロン（ε）だけＬよりも下がっており、それによって追加近接性７４が必要になるという仮定が用いられる。好ましくは、新しい近接性及びトリガを走査する段階、及び新しい制約の発生段階は、除去／変更されたトリガの近くで局所的にのみ実施される。例えば、制約の組を適応させる時に、変更するトリガに対応するオブジェクト７１及び７２、及びこれらのオブジェクト７１、７２の直接の近傍７４、４５のみが考えられている。トポロジーの適応化段階中には、レイアウトは修正されず、近接性、トリガ、及び制約のみが修正されることに注意されたい。
【００３２】
以上の実施形態は、本発明を限定するのではなく例示しており、当業者は、特許請求の範囲から逸脱することなく多くの代替実施形態を設計することができることになることに注意すべきである。特許請求の範囲では、括弧内に入れられたいかなる参照符号も特許請求の範囲を限定するものと解釈すべきではない。動詞「含む」及びその活用形の使用は、特許請求の範囲内に説明されるもの以外の要素又は段階の存在を除外しない。要素に先行する冠詞「ａ」又は「ａｎ」は、複数のそのような要素の存在を除外しない。本発明は、いくつかの個別要素を含むハードウエア、及び適切にプログラムされたコンピュータを用いて実施することができる。いくつかの手段を列挙する請求項では、これらの手段のうちのいくつかは、１つの同じハードウエア品目によって具現化することができる。ある一定の手段が互いに異なる従属請求項に記載されているという単なる事実は、これらの手段の組合せを有利に用いることができないことを示していない。
【符号の説明】
【００３３】
６１  設計規則の組を受け取る段階
６２  １組の制約を発生させる段階
６３  制約の組を解く段階
【図１】
2010531505.tif 000003
【図２】
2010531505.tif 000004
【図３】
2010531505.tif 000005
【図４】
2010531505.tif 000006
【図５】
2010531505.tif 000007
【図６】
2010531505.tif 000008
【図７】
2010531505.tif 000009
【国際調査報告】
2010531505.tif 000010
2010531505.tif 000011
2010531505.tif 000012