(57)【要約】【課題】単純なアルゴリズムによる高速な図形処理により、配線レイアウトに好適な配線図形の形状整形が実現でき、配線不要部分を削除できるようにした配線レイアウトの形状整形方法の提供。【解決手段】配線レイアウト図形内のうち、接続端子領域を認識する（Ｓ１００）。配線レイアウト図形の外形の各エッジを認識、分類する（Ｓ１０２、Ｓ１０４）。接続端子領域の外形の各エッジを認識、分類する（Ｓ１０６）。その分類した配線レイアウト図形のエッジを、接続端子領域のエッジを用いて分割し、その分割した各エッジに対して配線レイアウト図形の内側の方向にあるエッジを探索する（Ｓ１１０、Ｓ１１２）。次に、接続端子領域のエッジの存在の有無を判断し、この判断の結果に応じて、その各エッジを所定位置まで移動させる（Ｓ１１４〜Ｓ１１８）。【選択図】    図１
2004220512.tif 000002
【特許請求の範囲】
【請求項１】
半導体集積回路の配線のレイアウトを行う際に、その配線のレイアウト図形は互いに垂直な少なくとも４つの複数の辺からなる多角形で表され、前記配線レイアウト図形の線幅を設計規則上の最小の線幅になるように整形する方法であって、
前記配線レイアウト図形内のビアまたはコンタクトを形成するのに不可欠な領域を認識する第１のステップと、
前記不可欠な領域が維持されるように、前記配線レイアウト図形の前記複数の辺のうち一辺の位置を固定し、前記一辺と対向する他辺を前記配線レイアウト図形の内側方向に前記一辺に向かって移動する第２のステップと、
を有することを特徴とする配線レイアウト図形の形状整形方法。
【請求項２】
半導体集積回路の配線のレイアウトを行う際に、その配線のレイアウト図形は互いに垂直な少なくとも４つの複数の辺からなる多角形で表され、前記配線レイアウト図形の線幅を設計規則上の最小の線幅になるように整形する方法であって、
前記配線レイアウト図形内のビアまたはコンタクトを形成するのに不可欠な領域を認識する第１のステップと、
前記配線レイアウト図形の前記複数の辺のうちの任意の第１の辺を、この第１の辺に対応する前記不可欠な領域の辺に基づいて分割する第２のステップと、
前記不可欠な領域が維持されるように、前記第１の辺と対向する第２の辺を固定させた状態で、前記分割させた第１の辺を前記配線レイアウト図形の内側方向に前記第２の辺に向けて所定位置まで移動する第３のステップと、
を有することを特徴とする配線レイアウト図形の形状整形方法。
【請求項３】
前記第２のステップ、または前記第２および第３のステップは、前記多角形の上下左右の４方向の全ての辺に対して行うことを特徴とする請求項１または請求項２に記載の配線レイアウト図形の形状整形方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、半導体回路をシリコン基板上に実現するための配線レイアウトにおいて、２つまたはそれ以上の接続端子図形を電気的に接続する、単一のレイヤーからなる配線レイアウトの形状整形方法に関するものである。
【０００２】
【従来の技術】
半導体回路の配線レイアウトについては、電気的接続を維持し、なおかつ最小幅などの設計規則を満たしながら、できる限り小さい面積の形状でレイアウトされることが要求される。
これは、配線レイアウトの面積が小さいほど寄生容量が減少するので、回路上の信号の伝達速度が上がりさらに消費電力も小さくなり、回路の性能が向上するからである。
【０００３】
半導体回路のレイアウトが、ある設計規則１で既に設計されている場合、そのレイアウトを別の設計規則２に合うように変更するレイアウトマイグレーションにおいて、レイアウトを構成する図形の１つ１つを設計規則２に従ってある方向に詰めていく手法（方法）は、コンパクション（圧縮）手法として良く知られているが、その図形移動の処理を、図形を構成する辺（エッジ）に適用していく手法は、特にエッジベースコンパクションと呼ばれている。
【０００４】
このエッジベースコンパクションに係る装置として、本願出願人による「設計支援装置」が知られている（例えば、特許文献１参照）。
ところで、従来のレイアウトに対するエッジベースコンパクションの手法としては、次のようなものが知られている。
これは、レイアウトを構成する各レイヤーの図形に対して、まず、その図形のエッジのうち横方向のエッジを順次選択していき、それを下方向（または上方向）に移動できるだけ移動する。次に、これと同様の処理を縦方向のエッジにも適用して、左方向（または右方法）に移動できるだけ移動する。
【０００５】
ここで、エッジを移動する場合の移動可能な距離は、各レイヤーの最小幅やレイヤー同士間の最小間隔などの、あらかじめ設定されたマイグレーション先の設計規則２に従って決定される。
【０００６】
【特許文献１】
特開２０００−１９５９６３号公報（図４）
【０００７】
【発明が解決しようとする課題】
しかし、そのエッジベースコンパクションを用いて、設計規則１に従ったあるレイアウトを設計規則２に合うようにレイアウトマイグレーションした場合、配線を構成するレイアウト図形もエッジごとにコンパクションされる。このため、配線レイアウトにより接続されている周囲の図形に状況に応じて、場合によっては大きく引き伸ばされた図形となり、そのため配線レイアウトの面積が増大して寄生容量が増加し、回路特性の低下を招くという不都合が生じる。
【０００８】
図３は、このような状況を模式的に表現した図である。
図３中のＨ１は、左右の２つのＭＯＳトランジスタのソースまたはドレイン間を接続する配線レイアウトであり、Ｒ１とＲ２は、その周辺のレイアウトをイメージ的に表したものである。
図３では、設計規則１に従って設計されたレイアウト（図３（ａ））が、エッジベースコンパクションによって、設計規則２に適合するようにレイアウトマイグレーションされて、図３（ｂ）に示すように変形されたことを想定している。この際に、周辺レイアウト領域Ｒ１は横方向に大きくなり、周辺レイアウト領域Ｒ２は縦方向に大きくなったと仮定している。
【０００９】
この場合には、配線レイアウト領域Ｈ１は、図３（ｂ）に示すように、縦横方向に引き延ばされて不要な部分を有し、非常に冗長な図形になってしまう。
このような不都合を回避するためには、エッジの折れ曲がりを許したコンパクション手法（ジョグ挿入コンパクション手法）も考えられるが、折れ曲がりのために処理するデータ量が増大し、処理速度の低下という新たな不都合を引き起こしてしまう。
そこで、本発明の目的は、単純なアルゴリズムによる高速な図形処理により、配線レイアウトに好適な配線図形の形状整形が実現でき、配線不要部分を削除できるようにした配線レイアウトの形状整形方法を提供することにある。
【００１０】
【課題を解決するための手段】
上記課題を解決して本発明の目的を達成するために、請求項１〜請求項３に記載の発明は以下のように構成した。
すなわち、請求項１に記載の発明は、半導体集積回路の配線のレイアウトを行う際に、その配線のレイアウト図形は互いに垂直な少なくとも４つの複数の辺からなる多角形で表され、前記配線レイアウト図形の線幅を設計規則上の最小の線幅になるように整形する方法であって、前記配線レイアウト図形内のビアまたはコンタクトを形成するのに不可欠な領域を認識する第１のステップと、前記不可欠な領域が維持されるように、前記配線レイアウト図形の前記複数の辺のうち一辺の位置を固定し、前記一辺と対向する他辺を前記配線レイアウト図形の内側方向に前記一辺に向かって移動する第２のステップと、を有することを特徴とするものである。
【００１１】
請求項２に記載の発明は、半導体集積回路の配線のレイアウトを行う際に、その配線のレイアウト図形は互いに垂直な少なくとも４つの複数の辺からなる多角形で表され、前記配線レイアウト図形の線幅を設計規則上の最小の線幅になるように整形する方法であって、前記配線レイアウト図形内のビアまたはコンタクトを形成するのに不可欠な領域を認識する第１のステップと、前記配線レイアウト図形の前記複数の辺のうちの任意の第１の辺を、この第１の辺に対応する前記不可欠な領域の辺に基づいて分割する第２のステップと、前記不可欠な領域が維持されるように、前記第１の辺と対向する第２の辺を固定させた状態で、前記分割させた第１の辺を前記配線レイアウト図形の内側方向に前記第２の辺に向けて所定位置まで移動する第３のステップと、を有することを特徴とするものである。
【００１２】
請求項３に記載の発明は、請求項１または請求項２に記載の配線レイアウトの形状整形方法において、前記第２のステップ、または前記第２および第３のステップは、前記多角形の上下左右の４方向の全ての辺に対して行うことを特徴とするものである。
このように、本発明方法によれば、配線レイアウト図形の形状を整形して、より少ない面積で、接続端子間の接続を保持した配線レイアウトができる。
また、本発明方法によれば、配線レイアウトの図形の面積を縮小でき、その結果、配線レイアウトの寄生容量を減少させて、回路の特性を向上させることができる。
【００１３】
【発明の実施の形態】
以下、本発明の実施の形態について、図面を参照して説明する。
まず、本発明の実施形態の概要について以下に説明する。
この実施形態は、半導体回路をシリコン基板に実現するためのレイアウトにおいて、レイアウトマイグーションのためのエッジベースコンパクション処理後の配線レイアウトに対して、コンパクション過程で生成される冗長な配線レイアウトから不要な図形部分を除去することを目的とするものであり、以下の手順で行う。
【００１４】
まず、上記のコンパクション過程で生成された冗長な配線レイアウトは、その図形を構成する上下左右の４方向の辺（以下、エッジという）に分解する。すなわち、配線レイアウト図形の上側のエッジ、下側のエッジ、左側のエッジ、および右側のエッジにそれぞれ分解する。
次に、この分解された各エッジは、配線レイアウトの内部に存在する除去不能な接続端子領域のエッジの端点で、さらに分割する。
【００１５】
ここで、配線レイアウトの内部に存在する除去不能な領域とは、その配線レイアウトの置かれたレイヤー（配線層）と電気的接続を有するレイヤーの接続用図形に対して、製造工程上必要なオーバーラップ量を付与した領域のことである。この領域は、配線レイアウトが接続端子同士間を接続（コンタクト）するという配線としての働きを有するために、どのような形状整形の場合においても必ず保持しなければならない図形領域である。
【００１６】
このように分割された各エッジは、それぞれ配線レイアウト図形の内側方向に、設計規則の許す限り移動する。
ここで言う内側方向とは、右方向のエッジに対しては左方向、左方向のエッジに対しては右方向、上方向のエッジに対しては下方向、下方向のエッジに対しては上方向のことである。
【００１７】
その各エッジの内側方向での移動時の移動限界は、その方向に接続端子領域が存在するか否かにより異なる。移動方向の先に接続端子領域が存在する場合には、その接続端子領域に接するまでが移動限界である。一方、移動方向の先に接続端子領域が存在しない場合には、その移動先に存在する配線レイアウト図形または接続端子領域図形に属する逆方向のエッジ、例えば右エッジの場合には左エッジとの関係で、配線レイアウトのレイヤーの設計規則にある最小幅ルールにより決定される距離に応じた位置が移動限界である。このとき、移動するエッジが複数の逆方向のエッジと重なりを有している場合は、それら全ての逆方向エッジとの間で、最小幅ルールが満足される必要がある。
【００１８】
また、分割された各エッジの移動限界を決定する場合には、さらに以下の規則による。
すなわち、移動先に接続端子領域が存在する場合には、その接続端子領域の図形を構成する同方向のエッジにより、配線レイアウト図形のエッジが分割されているので、分割された各エッジは必ずいずれかの接続端子領域のエッジに内包される。従って、その内包している接続端子領域の図形エッジが、配線レイアウト図形の分割されたエッジの移動限界位置となる。
【００１９】
一方、移動先に接続端子領域が存在しない場合には、かかる配線レイアウト図形のエッジ分割の手法においては、分割されたエッジが接続端子領域と重なりを持つことはあり得ないので、接続端子領域の同方向エッジとの間の設計規則は存在しない。これは、例え分割されたエッジが接続端子領域と接する位置関係にあっても成立する規則である。
【００２０】
かかる状況においては、配線レイアウト図形のエッジは、配線レイアウト図形または接続端子図形に属する逆方向のエッジとの間に成立する最小幅の設計規則に従うことになる。しかし、最小幅を考慮すべき逆方向エッジは、エッジ間に重なりが存在する場合は勿論であるが、重なりが存在しなくて端点間の距離が最小値以下の場合でも、その該当逆方向エッジを移動しようとしている配線レイアウト図形のエッジとの間の、最小幅の設計規則を満足させる必要がある。
【００２１】
このようにして、ある一方向の配線レイアウト図形のエッジは、上記の方法により分割され、移動規則の許す限り内側方向に移動させられるが、この処理を上下左右の４方向に対して任意の順番で繰り返すことで、各方向に係わる配線レイアウトの配線不要部分を削除していくことができる。
この方法においては、上下左右の４方向を処理した後にも、削除可能な部分が残る場合があり得るので、上記の方法により配線レイアウト図形のエッジの移動が発生した場合には、再度、上下左右の４方向に対して上記方法を適用することで更なる改善を図り、エッジ移動によるそれ以上の改善が見られなくなるまで、繰り返し上記方法を適用する。
【００２２】
これにより、エッジベースコンパクション等で生成された冗長な配線レイアウトから、配線に不要な部分を除去したレイアウトを、簡単なアルゴリズムで高速に実現できる。
また、上記の方法は、本来存在する配線レイアウト図形の不要部分を削除するように働くため、新しいレイアウト部分を追加する必要がないので、他のレイアウト図形との最小間隔などの設計規則を考慮する必要がないという特徴がある。かかる特徴のため、この方法は該当配線レイアウトの周辺に存在する他のレイアウトを処理する必要がないために、非常に高速な処理が可能である。
【００２３】
さらに、上記方法を配線レイアウト図形に適用することで、配線レイアウトの面積を縮小し、配線の寄生容量の削減を実現できる。
ところで、半導体回路のレイアウトにおいて、冗長な配線レイアウトの図形は、エッジベースコンパクション処理結果の場合のみでなく、マニュアルによるラフな配線レイアウトの場合やコンパクションを伴わないレイアウトマイグレーションの場合にも発生することがあり得る。
【００２４】
そこで、このようなレイアウトに対しても、上記の方法を適用することで、不要部分を除去した配線レイアウトを得ることができ、その結果、少ないレイアウト面積で配線を実現することができるので、配線の寄生容量を削減して回路の電気的特性を向上させることができる。
以上説明した実施例の各手順は、コンピュータシステム上のプログラムにより実現されるものである。
【００２５】
図１は、この実施形態に係る配線レイアウトの形状整形方法をコンピュータで実現するための処理手順を示すフローチャートであり、この処理手順を図１を参照して説明する。
まず、半導体回路のレイアウトをコンパクション処理した後のレイアウトデータにおける、配線レイアウトデータを入力とし、ステップＳ１００では、配線レイアウト形状のうちで、接続に不可欠な部分を接続端子領域として認識する。
【００２６】
通常の場合は、その配線レイアウト図形に属するレイヤーとの接続を有する他のレイヤー、例えば、メタル１レイヤーに対するビアレイヤーがこれに相当するが、その接続他レイヤーに設計規則で規定された一定のオーバラップ量を取って膨らませた図形領域が、ステップＳ１００における接続端子領域になる。
次のステップＳ１０２では、配線レイアウト形状の外形を形成する各エッジを認識する。さらに、ステップＳ１０４では、その認識した各エッジを上下左右の４方向に分類する。
【００２７】
この時、例えば右エッジとは、図形の右側の辺を形成する縦方向のエッジのことであり、そのエッジの左側が図形の内側になり、そのエッジの右側が図形の外側となる。また、上エッジとは、図形の上側の辺を形成する横方向のエッジのことであり、そのエッジの下側が図形の内側になり、そのエッジの上側が図形の外側になる。
【００２８】
次のステップＳ１０６では、接続端子領域に対しても同様に、その図形の外形を構成する各エッジを認識し、各方向ごとに分類する。
次のステップＳ１０８では、その分類した各エッジの処理する方向を決定する。この際、各エッジの上下左右の方向の順番は任意である。その決定した各方向の処理を行う際には、配線レイアウト形状のエッジのうち、その方向に属するエッジのみ移動させられる。例えば、いま、右方向を処理していると、右エッジのみが移動の候補として、以下のように処理される。
【００２９】
まず、ステップＳ１１０では、選択された方向に属する外形エッジに対して、接続部分エッジ（接続端子領域のエッジ）の両端との位置関係を見て、その両端位置で外形エッジを分割する。この処理の対象となる接続部分エッジは、外形エッジと同方向の接続部分エッジに限定される。
次のステップＳ１１２では、その分割された各外形エッジに対して、エッジの移動が起こりうる内側の方向にあるエッジを探索し、さらにステップＳ１１４では、その探索されたエッジが接続部分エッジか否かを判定する。
【００３０】
この判定の結果、その探索されたエッジが接続部分エッジの場合にはステップＳ１１６に進み、外形エッジをその探索された接続部分エッジに重なるまで、内側に移動する。
一方、その探索されたエッジが接続部分エッジでない場合には、ステップＳ  １１８に進む。この場合には、探索されたエッジは対象となっている外形エッジと逆方法のエッジであるので、その移動先にある逆方法の外形エッジに対して、設計規則で許される最小幅の距離まで、内側に移動する。
【００３１】
次のステップＳ１２０では、全外形エッジを処理したか否かを判定する。この判定の結果、全外形エッジの処理が終了している場合にはステップＳ１２２に進み、その処理が終了していない場合にはステップＳ１１０に戻り、次の未処理の外形エッジに対して、ステップＳ１１０〜Ｓ１１８の各処理を実施する。
さらにステップＳ１２２では、上下左右全方向を処理したか否かを判定する。この判定の結果、全方向の処理が終了している場合にはステップＳ１２４に進み、その処理が終了していない場合には、ステップＳ１０８に戻り、未処理の方向に対してステップＳ１０８〜Ｓ１２０の各処理を実施する。
【００３２】
次のステップＳ１２４では、ステップＳ１０４〜Ｓ１２２の各処理において、外形エッジの移動が実際に発生したか否かを判定する。
この判定の結果、外形エッジの移動が発生したと判定した場合には、ステップＳ１０４に戻り、ステップＳ１０４〜ステップＳ１２４の各処理を再び実施する。一方、外形エッジの移動が発生していないと判定した場合には、その処理を終了する。
【００３３】
そのステップＳ１２４による繰り返しループは、あるエッジの移動によって、他の方向のエッジが新たに内側方向に移動できるようになる場合もあるので、この場合でも効率的な配線レイアウトの図形の形状整形を達成することを目的としている。
次に、この実施形態に係るレイアウトの形状整形方法の具体的な適用例について、図２を参照して説明する。
【００３４】
図２（ａ）はその適用の前の配線レイアウトの一例を示す図である。
この配線レイアウトは、図示のように、エッジＥ１〜Ｅ７などで囲まれた多角形領域Ｒ１１であり、ある１つの配線用のレイヤーに属しているものとする。そして、この多角形領域Ｒ１１内には、エッジＯ１、Ｐ１などで囲まれて斜線部で示す接続端子領域Ｃ１と、エッジＯ２、Ｐ２などで囲まれて斜線部で示す接続端子領域Ｃ２とが存在するものとする。
【００３５】
ここで、これらの接続端子領域Ｃ１、Ｃ２は、多角形領域Ｒ１１の形状整形時には削除できず、必ず保持しなければならない領域である。
次に、図２（ａ）の配線レイアウトに対して、右エッジＥ１〜Ｅ７を処理する場合について説明する。
右エッジＥ１〜Ｅ７の処理は、その各右エッジＥ１〜Ｅ７を可能な限り左方向に移動するという方法で行い、これにより、配線レイアウト図形は、形状整形処理により、その形状が小さくなるかまたは処理前と同じになる。
【００３６】
また、右エッジＥ１〜Ｅ７を左方向に移動する過程において、新たな配線レイアウト部分が追加されることもないので、処理後の配線レイアウト図形が他の周囲のレイアウト図形との設計規則に違反する恐れもない。
まず、図２（ａ）に示す配線レイアウト図形（多角形領域Ｒ１１）における右エッジを認識する。この場合には、その認識する右エッジは、Ｅ１〜Ｅ３、Ｅ４、Ｅ５〜Ｅ７の３つのエッジからなる。
【００３７】
次に、接続端子領域Ｃ１、Ｃ２の右エッジＰ１、Ｐ２を認識し、その認識した右エッジＰ１の両端を右方向に点線で示すように延長し、配線レイアウト図形の右エッジ部分Ｅ１〜Ｅ３を分割すると、右エッジＥ１〜Ｅ３はＥ１、Ｅ２、Ｅ３の３つの各エッジにそれぞれ分割される。同様に、その認識した右エッジＰ２の両端を右方向に点線で示すように延長し、配線レイアウト図形の右エッジ部分Ｅ５〜Ｅ７を分割すると、右エッジＥ５〜Ｅ７はＥ５、Ｅ６、Ｅ７の３つの各エッジにそれぞれ分割される。この結果、配線レイアウト図形の右エッジは、図２（ａ）に示すように、最終的にＥ１〜Ｅ７の各エッジに分割される。
【００３８】
次に、このように７つに分割された右エッジＥ１〜Ｅ７を、図２（ａ）の位置から設計規則の許す限り左方向に移動させる。
ここで、右エッジＥ２、Ｅ６は、移動方向に接続端子領域Ｃ１、Ｃ２の右エッジＰ１、Ｐ２が存在しているので、右エッジＥ２は右エッジＰ１の位置、右エッジＥ６は右エッジＰ２の位置までそれぞれ左方向に移動させられる。
【００３９】
右エッジＥ４の移動方向（左方向）に存在しているのは、多角形領域Ｒ１１の左エッジＥ１１である。このため、右エッジＥ４は、左エッジＥ１１から距離ｄだけ離れた位置まで左方向に移動させることができる。ここで、距離ｄは、多角形領域Ｒ１１のレイヤーの最小幅の設計規則で規定される距離である。
さらに、右エッジＥ１、Ｅ３に関しては、最小幅の設計規則を考えなければならない対象として、多角形領域Ｒ１１の左エッジＥ１１の他に、接続端子領域Ｃ１の左エッジＯ１がある。この結果、右エッジＥ１、Ｅ３は、接続端子領域Ｃ１の左エッジＯ１から距離ｄだけ右に離れた位置まで移動させることになる（図２（ｂ）参照）。同様に、右エッジＥ５、Ｅ７は、接続端子領域Ｃ２の左エッジＯ２から距離ｄだけ右に離れた位置まで移動させる（図２（ｂ）参照）。
【００４０】
このようにして、図２（ａ）に示す配線レイアウト図形は、図２（ｂ）に示すような配線レイアウト図形に整形することができる。
以上の例は、右エッジに対する処理の説明であるが、これを上下左右の４方向に実施し、さらに改善がなくなるまでその４方向への処理を繰り返すことで、配線レイアウト図形から不要な部分を削除し、その形状をより小さい面積に整形することができる。
【００４１】
以上説明したように、この実施形態によれば、コンパクション後の配線レイアウト図形の形状を整形して、より少ない面積で、接続端子間の接続を保持した配線レイアウトにできる。
また、この実施形態によれば、配線レイアウト図形の面積を縮小し、その結果、配線レイアウトの寄生容量を減少させて、回路の特性を向上させることができる。
【００４２】
【発明の効果】
以上説明したように、本発明によれば、配線レイアウト図形の形状を整形して、より少ない面積で、接続端子間の接続を保持した配線レイアウトができる。
また、本発明方法によれば、配線レイアウト図形の面積を縮小でき、配線レイアウトの寄生容量を減少させて、回路の特性を向上させることができる。
【図面の簡単な説明】
【図１】本発明の実施形態の処理手順を説明するフローチャートである。
【図２】その実施形態を適用した配線レイアウト図形の例を示す図であり、（ａ）はその適用前の図であり、（ｂ）はその適用後の図である。
【図３】従来の冗長な配線レイアウトを説明する図である。
【符号の説明】
Ｒ１１  多角形領域
Ｃ１、Ｃ２  接続端子領域
Ｅ１〜Ｅ７、Ｅ１１  エッジ
Ｏ１、Ｏ２、Ｐ１、Ｐ２  エッジ
【図１】
2004220512.tif 000003
【図２】
2004220512.tif 000004
【図３】
2004220512.tif 000005