(57)【特許請求の範囲】
【請求項１】
配線のクリティカルエリアを算出するクリティカルエリア演算装置におけるクリティカルエリア演算方法であって、
配線データを所定の方向に走査し、
当該走査の結果に基づいて、相互に平行に配置される３本の配線の存在する領域を検出し、
当該検出した領域について、前記３本の配線における、２番目配線である中間の配線ｎj を含む、１番目配線及び前記２番目配線と等距離にある線分と前記２番目配線及び３番目配線と等距離にある線分に囲まれた領域に関して、Ｌを当該領域の長さ、ａ1 及びｂ1 を前記１番目配線である最下層の配線ｎk の各々下端及び上端の座標、ａ2 及びｂ2 を前記中間の配線ｎj の各々下端及び上端の座標、ａ3 及びｂ3 を前記３番目配線である最上層の配線ｎi の各々下端及び上端の座標とした場合に、ＡＣ＝ｒ0 2 Ｌ（２／（ａ3 −ｂ1 ）−１／（２ａ3 −ｂ1 −ａ2 ）−１／（ａ3 ＋ｂ2 −２ｂ1 ））により、クリティカルエリアＡＣを算出する
ことを特徴とするクリティカルエリア演算方法。
【請求項２】
前記クリティカルエリアを算出した領域について、その３本の配線の中で前記走査において最初に検出された配線を当該領域から除外する
ことを特徴とする請求項１に記載のクリティカルエリア演算方法。
【請求項３】
前記相互に平行に配置される３本の配線の存在する領域は、相互に平行に配置される２本の配線に対して、他の１本の配線の重なりを調べることにより検出する
ことを特徴とする請求項１に記載のクリティカルエリア演算方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、クリティカルエリア演算方法に関し、特に、ＬＳＩ等のレイアウト設計におけるクリティカルエリアの算出を行うクリティカルエリア演算方法に関する。
【０００２】
【従来の技術】
近年、半導体集積回路装置（以下、ＬＳＩ）の集積度向上や、1 チップに搭載可能な回路の大規模化に伴い、ＬＳＩの製造歩留りの低下が問題となっている。ＬＳＩの製造歩留りは、大別すると、製造プロセスの不具合によるシステム歩留りと、製造プロセス内に入り込んだ小さなごみ（デフェクト）によりチップ上の配線がショート（短絡）又はオープン（開放）を起こしてしまうランダム歩留りに分けられる。この内、与えられたチップに対するランダム歩留りの指標となる量として、クリティカルエリアがある。
【０００３】
クリティカルエリアは、以下のようにして求められる。今、図１８に示すように、デフェクトが半径ｒの円形であるとする。デフェクトの中心（デフェクト中心）がそこに落ちたときに、配線ショート又はオープン（以下、単にショートという）を起こすチップ上の点からなる領域の面積をＡ（ｒ）とする。面積Ａ（ｒ）は半径ｒのデフェクトのショート故障頻度の指標となる。即ち、面積Ａ（ｒ）が大きければ故障は多く、小さければ故障は少ないと考えられる。半径ｒのデフェクトの分布確率密度をＤ（ｒ）とする。このとき、デフェクト半径ｒのショート領域面積Ａ（ｒ）を分布確率密度Ｄ（ｒ）で積分した量ＡＣを" クリティカルエリア" といい、以下のように求まる。即ち、
ＡＣ＝∫Ａ（ｒ）Ｄ（ｒ）ｄｒ（∫は「０」から「∞」まで）
である。
【０００４】
【発明が解決しようとする課題】
クリティカルエリアＡＣは、チップのデフェクトに対する平均的なショート領域面積を表しており、ショート故障頻度、更にはランダム歩留りの指標となると考えられる。このようなクリティカルエリアを高速かつ正確に計算する演算方法は、ＬＳＩ製造歩留り向上のために大きく寄与すると考えられる。
【０００５】
クリティカルエリアＡＣを計算する方法としては、モンテカルロ法、グリッド法、ボロノイ図法等、種々の方法が提案されている。しかし、いずれも計算時間が多くなるか、アルゴリズムが煩雑で実装が困難なものである。これは、従来のクリティカルエリアの計算では、チップ上の配線が任意の形をとるので、これに対応して、形状についての普遍性が高い手法を用いるためである。即ち、演算に普遍性を求めるが故に、計算量の増加やアルゴリズムの複雑化を招いている。
【０００６】
そこで、比較的簡便で高速なアルゴリズムによる方法が求められている。本発明者は、配線形状が、一般に、各配線領域において配線方向への細長い長方形が平行に並んでいる場合が多いことに着目して、このような配線形状の性質を利用すれば、比較的簡便で高速なクリティカルエリアの演算が可能になるのではないかと考えた。
【０００７】
本発明は、ＬＳＩ等のレイアウト設計におけるクリティカルエリアの算出を比較的簡便で高速に行うことができるクリティカルエリア演算方法を提供することを目的とする。
【０００８】
【課題を解決するための手段】
本発明のクリティカルエリア演算方法は、配線のクリティカルエリアを算出するクリティカルエリア演算装置におけるクリティカルエリア演算方法であって、配線データを所定の方向に走査し、当該走査の結果に基づいて相互に平行に配置される３本の配線の存在する領域を検出し、当該検出した領域について、前記３本の配線における、２番目配線である中間の配線ｎj を含む、１番目配線及び前記２番目配線と等距離にある線分と前記２番目配線及び３番目配線と等距離にある線分に囲まれた領域に関して、Ｌを当該領域の長さ、ａ1 及びｂ1 を前記１番目配線である最下層の配線ｎk の各々下端及び上端の座標、ａ2 及びｂ2 を前記中間の配線ｎj の各々下端及び上端の座標、ａ3 及びｂ3 を前記３番目配線である最上層の配線ｎi の各々下端及び上端の座標とした場合に、ＡＣ＝ｒ0 2 Ｌ（２／（ａ3 −ｂ1 ）−１／（２ａ3 −ｂ1 −ａ2 ）−１／（ａ3 ＋ｂ2 −２ｂ1 ））により、クリティカルエリアＡＣを算出する。
【０００９】
本発明のクリティカルエリア演算方法によれば、任意の形状をとる配線についての普遍性が高い手法を用いることなく、配線方向への細長い長方形が平行に並んでいる形状の配線領域を検出して、この領域についてのみ、前述の式に示すように、この領域の長さ及び座標を用いて、そのクリティカルエリアＡＣを算出する。これにより、配線データを走査するのみで、比較的簡単なアルゴリズムで、短い計算時間で、クリティカルエリアＡＣを近似的に計算することができ、ショート故障頻度等の指標とすることができる。また、比較的簡単なアルゴリズムであるので、コンピュータへ容易に実装することができる。
【００１０】
【発明の実施の形態】
図１はクリティカルエリア演算装置構成図であり、本発明のクリティカルエリア演算方法を実行するクリティカルエリア演算装置の構成の概略を示す。
【００１１】
クリティカルエリア演算装置は、クリティカルエリア演算処理部（以下、演算処理部）１、配線データ格納部２、クリティカルエリア格納部３からなる。配線データ格納部２は、例えばＬＳＩの実際のレイアウト設計の結果得られた配線データを格納する。なお、配線データは、ＬＳＩについての配線データに限られず、セラミックの配線基板やプリント基板上の配線データ等であってもよい。クリティカルエリア格納部３は、演算処理部１において算出されたクリティカルエリアの値を格納する。演算処理部１は、配線データ格納部２から配線データを読み出して、これについてクリティカルエリアの値を算出し、その値をクリティカルエリア格納部３に格納する。
【００１２】
演算処理部１は、ノード操作処理部１１、算出処理部１２、マージ処理部１３からなる。ノード操作処理部１１は、詳細は後述するが、配線データ格納部２から配線データを読み出して、この中から本発明により導入される複数の配線の重なり部分（以下、重なりノードと言う）を検出し、これに所定の操作する処理を行う。算出処理部１２は、ノード操作処理部１１における重なりノードの操作の結果に基づいて、所定の状態となった重なりノードについてクリティカルエリアの値を算出し、その値をクリティカルエリア格納部３に格納する。この後、算出処理部１２は、クリティカルエリアの値を算出した当該重なりノードについて、所定の処理を行う。即ち、当該重なりノードを構成する複数の配線から１本の配線を取り除き、当該重なりノードの状態を重なりの度合いが少なくなるように操作する。マージ処理部１３は、算出処理部１２におけるこのような重なりノードの操作の結果に基づいて、隣接する複数の重なりノードをマージする。
【００１３】
演算処理部１は、当該演算処理（クリティカルエリア演算処理）を行うクリティカルエリア演算プログラムを当該クリティカルエリア演算装置のＣＰＵで実行することにより実現される。クリティカルエリア演算プログラムは、フレキシブルディスク、ＣＤ−ＲＯＭ、ＣＤＲ／Ｗ、ＤＶＤ等の種々のコンピュータ読み取り可能な記録媒体に格納することにより提供される。
【００１４】
ここで、本発明におけるクリティカルエリアの値の演算についての基本概念を図２及び図３に示す。
【００１５】
前述のように、従来のクリティカルエリアの計算では、チップ上の配線の形状が任意であることに対応するために、形状についての普遍性が高い手法を用いているので、計算量の増加やアルゴリズムの複雑化を招いている。しかし、一般に、配線形状は、各配線領域において、配線方向への細長い長方形が平行に並んでいる場合が多い。そこで、本発明のクリティカルエリアの計算では、このような配線が相互に平行に配置されるという配線形状の性質を利用する。
【００１６】
まず、本発明のクリティカルエリアの演算処理が対象とする配線形状を説明する。図２に示すように、ＬＳＩチップ上において、配線は配線方向において同一の又は平行な領域（以下、トラックと言う）上に乗っているものとする。このような配線の形状は、例えばゲートアレイＬＳＩにおいて多く見られる。トラックは、下から順に、I 、II、III 、・・・とされる。トラックの長さは、最大でＬとされる。ＬＳＩチップ（又は、処理対象の配線領域、以下同じ）の下辺Ｂ及び上辺Ｔは、長さＬのトラックであり、その全体に配線が形成されているものとみなす（仮定する）。クリティカルエリアの演算処理時の走査方向は、例えば図２のように定められる。即ち、トラックＢ、I 、II、III 、・・・Ｔの順に操作され、同一のトラックにおいてその左側から順に走査される。走査を開始する位置の座標を「０」とする。
【００１７】
また、本発明のクリティカルエリアの演算処理においては、デフェクト半径に関する分布確率密度Ｄ（ｒ）は、以下の式で表されると（経験則から）仮定する。即ち、
0004071537.tif 000002
である。ここで、ｃ＝（ｑ＋１）（ｐ−１）／（ｐ＋ｑ）である。更に、説明の簡単のため、以下の説明においては、ｐ＝３、ｑ＝１とする。
【００１８】
いま、図３に示すように、ＬＳＩの配線データの中で、3 本の（横方向に）平行な配線があるとする。このとき、中間（2 本目）の配線を含む、１番目及び２番目配線と等距離にある線分と２番目及び３番目配線と等距離にある線分に囲まれた領域に関するクリティカルエリア（図３において太い斜線を付して示す）は簡単に計算でき、
ＡＣ＝ｒ0 2 Ｌ（２／（ａ3 −ｂ1 ）−１／（２ａ3 −ｂ1 −ａ2 ）−１／（ａ3 ＋ｂ2 −２ｂ1 ））
となる。ここで、図３に示すように、Ｌは当該領域の長さ、ａ1 及びｂ1 は最下層の配線ｎk の各々下端及び上端の座標、ａ2 及びｂ2 は中間の配線ｎj の各々下端及び上端の座標、ａ3 及びｂ3 は最上層の配線ｎi の各々下端及び上端の座標である。
【００１９】
本発明のクリティカルエリアの演算処理は、配線データを前述の走査方向に順に走査することにより、図３のような配線の重なり（重なりノード）を検出し、それについて逐次的にクリティカルエリアを近似的計算する。例えば、図２の配線データにおいても、図３の配線の重なりを持つ領域が数多く存在し、これらはその配線の座標を調べることにより容易に検出することができ、かつ、そのクリティカルエリアも前述の式により容易に近似的計算することができる。これにより、基本的に、配線（配線データ）の走査のみでクリティカルエリアの演算処理を行うことができるため、高速に計算することができる。
【００２０】
次に、本発明におけるクリティカルエリアの値の演算のために用いる記号等について、図４及び図５により説明する。
【００２１】
３本の平行配線の重なり部分（以下「重なりノード」と称す）を
ｎi ｎj ｎk 〔α，β〕
と表現する。ここで、図４に示すように、ｎi 、ｎj 及びｎk は重なっている配線（3 本以下とする）を表し、α及びβは各々重なり区間の左端の座標及び右端座標を示す。配線の重なり又は重なりノードとは（左側から走査するとして）、相互に平行な２本の配線において、一方の配線の右端の座標が、他方の配線の左端の座標よりも大きい値を持つ場合において、座標値が同一の領域のことである。この場合における重なりノードを、斜線を付して示す。重なりノードのみに着目すると、図３と同様に考えることができ、クリティカルエリアの値の演算処理を容易に行うことができる。
【００２２】
また、配線（配線データ）を走査する場合、図５に示すように、配線は、その左側の配線のない区間（左側隣接無配線区間）と一体の区間（領域）として処理することとし、
ｎ（ｘ，α，β）
と記す。ここで、図５に示すように、ｎは当該配線の配線名、ｘは当該配線ｎの左側隣接無配線区間の左端の座標（即ち、左側に隣接する配線の右端の座標）、α及びβは各々当該配線のｎの実際の左端の座標及び右端の座標である。
【００２３】
次に、ノード操作処理部１１が実行する操作（操作処理）について、図６乃至図１０により説明する。ノード操作処理部１１は、本発明におけるクリティカルエリアの値の演算の基礎となる重なりノード及び配線の操作を実行する。
【００２４】
重なりノード及び配線の操作は、基本的には、重なりノードと配線との交叉を順に検出して、逐次的に以下のいずれかの操作を行うことによる。この場合において、重なりノードは、既に重なっている２本（最下層及び中間）の配線により作られる。即ち、ｎi ｎj 〔α，β〕である。配線は、新たな３本目（最上層）の配線である。即ち、ｎ（ｘ，μ，ν）である。従って、本発明のクリティカルエリアの値は、前述のように、相互に平行に配置される３本の配線の存在する領域について算出されるが、当該領域を、相互に平行に配置される２本の配線に対して、他の１本の配線の重なりを調べることにより検出する。
【００２５】
第１の操作は、図６に示すように、μ＜ν＜α＜β（実線で示す配線ｎの場合）又はα＜β＜μ＜ν（点線で示す配線ｎの場合）の場合である。即ち、重なりノードｎi ｎj 〔α，β〕と配線ｎ（ｘ，μ，ν）とが重ならない（交わらない）場合である。具体的には、重なりノードである領域（ア）と配線である領域（イ）とが重ならない。この場合、重なりノードｎi ｎj 〔α，β〕に変化はない。従って、第１の操作は、実質的には、操作を行わないに等しい。なお、図６において、斜線を付した部分は、重なりノードの領域（範囲）を示す。
【００２６】
第２の操作は、図７に示すように、α＜μ＜β＜νの場合である。即ち、重なりノードｎi ｎj 〔α，β〕と配線ｎ（ｘ，μ，ν）とが部分的に重なる場合であって、前者が左側に後者が右側に相互に少しづつずれている場合である。この場合、重なりノードが領域（ウ）と領域（エ）とに２分割されるように操作される。即ち、
重なりノード→領域（ウ）∪領域（エ）
であり、換言すれば、
ｎi ｎj 〔α，β〕→ｎi ｎj 〔α，μ〕∪ｎｎi ｎj 〔μ，β〕
である。
【００２７】
第３の操作は、図８に示すように、μ＜α＜β＜νの場合である。即ち、重なりノードｎi ｎj 〔α，β〕と配線ｎ（ｘ，μ，ν）とが完全に重なる場合であって、前者を後者が包含する場合（前者よりも後者が広い又は長い）場合である。この場合、重なりノードが領域（オ）とされるように操作される。即ち、
重なりノード→領域（オ）
であり、換言すれば、
ｎi ｎj 〔α，β〕→ｎｎi ｎj 〔α，β〕
である。
【００２８】
第４の操作は、図９に示すように、μ＜α＜ν＜βの場合である。即ち、重なりノードｎi ｎj 〔α，β〕と配線ｎ（ｘ，μ，ν）とが部分的に重なる場合であって、前者が右側に後者が左側に相互に少しづつずれている場合である。この場合、重なりノードが領域（カ）と領域（キ）とに２分割されるように操作される。即ち、
重なりノード→領域（カ）∪領域（キ）
であり、換言すれば、
ｎi ｎj 〔α，β〕→ｎｎi ｎj 〔α，ν〕∪ｎi ｎj 〔ν，β〕
である。
【００２９】
第５の操作は、図１０に示すように、α＜μ＜ν＜βの場合である。即ち、重なりノードｎi ｎj 〔α，β〕と配線ｎ（ｘ，μ，ν）とが完全に重なる場合であって、前者が後者を包含する場合（前者が後者よりも広い又は長い）場合である。この場合、重なりノードが領域（ク）、領域（ケ）及び領域（コ）とに３分割されるように操作される。即ち、
重なりノード→領域（ク）∪領域（ケ）∪領域（コ）
であり、換言すれば、
ｎi ｎj 〔α，β〕→ｎi ｎj 〔α，μ〕∪ｎｎi ｎj 〔μ，ν〕∪ｎi ｎj 〔ν，β〕
である。
【００３０】
次に、算出処理部１２が実行するクリティカルエリアの演算処理について、図１１により説明する。算出処理部１２は、本発明におけるクリティカルエリアの値の演算処理を実行する。
【００３１】
前述の重なりノード及び配線の操作に基づいて、クリティカルエリアの演算処理を行う。本発明のクリティカルエリアの演算処理は、図３を参照して説明したように、図３のような３本の配線の作る重なりノードを検出し、それについて逐次的にクリティカルエリアを近似的計算する。従って、前述の操作の結果、図７の領域（エ）、図８の領域（オ）、図９の領域（カ）、図１０の領域（ケ）について、重なりノードで３本の配線が重なっているので、これがクリティカルエリアの演算処理の対象となる重なりノードとして検出される。そこで、図１１に示すように、ノード操作の結果得られたこれらの領域について、各々についてのクリティカルエリアの演算を図３の式により行う。
【００３２】
更に、このクリティカルエリアの演算の後、当該重なりノードの範囲における最下層（即ち、最初に走査により検出された配線）の配線ｎk を、当該重なりノード即ちクリティカルエリアの演算の処理対象から除外する。即ち、配線データを走査して、２本の配線ｎk 及びｎj の重なりノードを求めた後、３本目の配線ｎi との交叉を調べて前述のいずれかの操作を行い、３本の配線が重なる重なりノードｎi ｎj ｎk 〔α，β〕を求めて、そのクリティカルエリアの演算を行い、図１１に示すように、演算が済んだ領域については演算対象から除くために最下層の配線ｎk を処理対象から除外する。これにより、２本の配線ｎj 及びｎi の重なりノードを求める。この後、配線データを走査することにより検出された新たな配線が検出され、これと前記重なりノードとの交叉を調べて前述のいずれかの操作を行うことを繰り返す。
【００３３】
次に、マージ処理部１３が実行するマージ処理について、図１２により説明する。マージ処理部１３は、本発明におけるクリティカルエリアの値の演算を容易にするための重なりノードのマージ処理を実行する。
【００３４】
前述のように、クリティカルエリアの演算が済んだ領域を演算対象から除くために、その時点での最下層の配線ｎ2 及びｎ1 を、順に処理対象から除外していく。この結果、図１２に示すように、配線ｎ2 及びｎ1 を除外した時点で、それまでは分割されていたが、重なり配線が同じで隣接する（連続する）２個の重なりノードが残される場合がある。この場合、これらの２個の重なりノードを
ｎi ｎj 〔α，β〕∪ｎi ｎj 〔β，γ〕→ｎi ｎj 〔α，γ〕
の操作即ちマージ処理を行うことにより、１個の重なりノードとする。これにより、この後の重なりノードと配線との交叉を容易に検出することができる。
【００３５】
図１３は、クリティカルエリア演算処理フローであり、本発明のクリティカルエリアの演算処理について示す。
【００３６】
ノード操作処理部１１が、クリティカルエリアの演算処理のための初期設定を行う（ステップＳ１１）。即ち、図２において説明したように、便宜上、ＬＳＩチップの下辺及び上辺を配線とみなして、図５に従って、各々、Ｂ（０，０，Ｌ）及びＴ（０，０，Ｌ）とする。また、ステップＳ１２における走査において、Ｂ（０，０，Ｌ）を最初の配線とし、Ｔ（０，０，Ｌ）を最後の配線とし、重なりノードの初期状態をＢ〔０，Ｌ〕とする（図１４参照）。更に、クリティカルエリアの値を「０」とする。
【００３７】
ノード操作処理部１１が、配線データ格納部２から配線データを読み出し、図２に示すように、読み出した配線データについて配線トラックを下から上へ、同一トラック内を左から右へ走査し、即ち、この順に個々の配線のデータを取り出し、図６乃至図１０に示すように、当該配線と重なりノード状態の交叉具合を調べ、これに基づいていずれかの操作を行う（ステップＳ１２）。
【００３８】
算出処理部１２が、前記操作の結果、例えば図７の領域（エ）のような３本の配線が重なる重なりノードが存在するか否かを調べ、存在する場合、当該領域についてのクリティカルエリアの値を図３に示した式により近似的に算出し、その値をクリティカルエリアの値に加算する（ステップＳ１３）。この後、算出処理部１２は、図１１に示すように、演算が済んだ領域の最下層の配線を処理対象から除外する（ステップＳ１３）。
【００３９】
マージ処理部１３が、前記配線を除外した結果、図１２に示すような重なり配線が同じで隣接する（連続する）２個の重なりノードの存在の有無を調べ、存在する場合、当該２個の重なりノードをマージして、１個の重なりノードとする（ステップＳ１4 ）。
【００４０】
ノード操作処理部１１が、配線データに残りの配線があるか否かを調べ、ある場合、ステップＳ１２以下を繰り返す。ない場合、その時点でのクリティカルエリアの値をクリティカルエリア格納部３に格納する（ステップＳ１５）。
【００４１】
次に、実際のＬＳＩ上の配線を例にとって、本発明のクリティカルエリアの演算処理について説明する。図１４乃至図１７は、クリティカルエリア演算説明図である。
【００４２】
例えば、図１４に示すような配線があるとする。なお、説明の簡単のために、第１及び第２トラックＩ及びIIのみを示す。例えば、第１トラックI における配線は、第１の配線が１（０，ｓ１，ｒ１）、第２の配線が２（ｒ１，ｓ２，ｒ２）、・・・である。前述のように、ノード操作処理部１１は、ＬＳＩチップの下辺及び上辺を便宜上の配線とみなして、各々、Ｂ（０，０，Ｌ）及びＴ（０，０，Ｌ）とし、重なりノードの初期状態をＢ〔０，Ｌ〕とし、クリティカルエリアの値を「０」とする（ステップＳ１１）。
【００４３】
次に、ノード操作処理部１１は、第１トラックＩを走査する。即ち、第１、第２、第３の配線をこの順に読み出して操作する。
【００４４】
まず、第１の配線（０，ｓ１，ｒ１）を読み出して、これと初期状態の重なりノードＢ〔０，Ｌ〕との交叉を調べると、図１０の場合に該当するので、当該第５の操作を行う。これにより、重なりノードの状態は、３分割されて、
Ｂ〔０，Ｌ〕→Ｂ〔０，ｓ１〕∪１Ｂ〔ｓ１，ｒ１〕∪Ｂ〔ｒ１，Ｌ〕
となる。なお、以下の説明においては、ノード操作の式の左辺の表示を省略することとする。また、例えば、重なりノード１Ｂ〔ｓ１，ｒ１〕における「１Ｂ」は、当該重なりノードの名前であり、第１の配線「１」と最下層の配線「Ｂ」との間における重なりノードであることを示し、数字が２個であることは２本の配線の重なりノードであることを示す（ステップＳ１２）。
【００４５】
この時点では、クリティカルエリアの算出処理の対象がなく（ステップＳ１３）、重なりノードのマージ処理の対象がなく（ステップＳ１４）、次の配線が存在するので（ステップＳ１５）、その処理のために、ステップＳ１２以下を繰り返す。以下、図１３により説明したように、各々の配線の処理の都度にこの処理を繰り返すが、以下においては説明を省略する。
【００４６】
次に、第２の配線（ｒ１，ｓ２，ｒ２）を読み出して、これと重なりノード（Ｂ〔ｒ１，Ｌ〕）との交叉を調べると、図１０の場合に該当するので、当該第５の操作を行う。これにより、重なりノードの状態は、３番目の重なりノードＢ〔ｒ１，Ｌ〕が３分割されて、
Ｂ〔０，ｓ１〕∪１Ｂ〔ｓ１，ｒ１〕∪Ｂ〔ｒ１，ｓ２〕∪２Ｂ〔ｓ２，ｒ２〕∪Ｂ〔ｒ２，Ｌ〕
となる。
【００４７】
次に、第３の配線（ｒ２，ｓ３，Ｌ）を読み出して、これと重なりノード（Ｂ〔ｒ２，Ｌ〕）との交叉を調べると、図１０の場合に該当するので、当該第５の操作を行う。これにより、重なりノードの状態は、重なりノードＢ〔ｒ２，Ｌ〕が３分割されて、
Ｂ〔０，ｓ１〕∪１Ｂ〔ｓ１，ｒ１〕∪Ｂ〔ｒ１，ｓ２〕∪２Ｂ〔ｓ２，ｒ２〕∪Ｂ〔ｒ２，ｓ３〕∪３Ｂ〔ｓ３，Ｌ〕
となる。この状態は、図１５から第４の配線を除いたものに等しい。即ち、最下層の配線Ｂと第１トラックＩの配線との間における重なりノードについては、全て調べられている。図１５において、各々の重なりノードにその名前を付して示している。
【００４８】
次に、ノード操作処理部１１は、第２トラックIIを走査する。即ち、第４、第５の配線をこの順に読み出して操作する。この時、第２トラックIIの初期状態の重なりノードとして、１行前の状態、即ち、第１トラックＩの走査を終了した時点の重なりノードの状態を引き継ぐ。
【００４９】
まず、図１５に示すように、第４の配線（０，ｓ４，ｒ４）を読み出して、これと第２トラックIIの初期状態の重なりノードとの交叉を調べる。この場合、図１５から判るように、重なりノード１Ｂ〔ｓ１，ｒ１〕については、図７の場合に該当するので、当該第２の操作を行う。また、重なりノードＢ〔ｒ１，ｓ２〕については、図９の場合に該当するので、当該第４の操作を行う。これにより、重なりノードの状態は、
Ｂ〔０，ｓ１〕∪１Ｂ〔ｓ１，ｓ４〕∪４１Ｂ〔ｓ４，ｒ１〕∪４Ｂ〔ｒ１，ｒ４〕∪Ｂ〔ｒ４，ｓ２〕∪２Ｂ〔ｓ２，ｒ２〕∪Ｂ〔ｒ２，ｓ３〕∪３Ｂ〔ｓ３，Ｌ〕
となる。この状態を図１６（Ａ）に示す。図１６（Ａ）において、最下層の配線Ｂ及び第１トラックＩの配線と第４の配線との間における重なりノードについては、全て調べられている。図１６（Ａ）において、各々の重なりノードにその名前を付して示している。
【００５０】
ここで、重なりノード４１Ｂ〔ｓ４，ｒ１〕は、その名前が示すように、第４の配線、第１の配線及び最下層の配線の３本の配線により構成される重なりノードである。そこで、この相互に平行に配置される３本の配線の存在する領域について、図１６（Ｂ）に示すように、クリティカルエリアを算出する演算を、図３に示す式を用いて行う。
【００５１】
この時、図１６（Ｂ）と図３との比較から判るように、当該配線（この場合、第１の配線）の上下の領域（右下がりの斜線部分）についてのクリティカルエリアの値が、図３に示す式により算出される。最下層の配線Ｂに接する領域（左下がりの斜線部分）についてのクリティカルエリアの値は、配線Ｂと第１トラックＩとの距離は既知であるので、重なりノード４１Ｂ〔ｓ４，ｒ１〕における座標値ｓ４及びｒ１を与えるのみで、容易に算出することができる。
【００５２】
この後、前述のように、重なりノード４１Ｂ〔ｓ４，ｒ１〕における最下層の配線Ｂを処理対象から除外する。これにより、重なりノードの状態は、
Ｂ〔０，ｓ１〕∪１Ｂ〔ｓ１，ｓ４〕∪４１〔ｓ４，ｒ１〕∪４Ｂ〔ｒ１，ｒ４〕∪Ｂ〔ｒ４，ｓ２〕∪２Ｂ〔ｓ２，ｒ２〕∪Ｂ〔ｒ２，ｓ３〕∪３Ｂ〔ｓ３，Ｌ〕
となる。この状態を図１６（Ｃ）に示す。図１６（Ｃ）において、斜線を付した部分は、未だクリティカルエリアの演算の処理対象として残っている領域を示す。一方、斜線を付していない部分は、クリティカルエリアの演算の済んだ領域（重なりノード４１Ｂ〔ｓ４，ｒ１〕における最下層の配線Ｂを除外したことに対応する領域）か、又は、配線が走査されていない部分である（ステップＳ１３）。
【００５３】
次に、第５の配線（ｒ４，ｓ５，L ）を読み出して、これと前述の重なりノードとの交叉を調べる。この場合、図１７から判るように、重なりノード２Ｂ〔ｓ２，ｒ２〕については、図７の場合に該当するので、当該第２の操作を行う。また、重なりノードＢ〔ｒ２，ｓ３〕については、図８の場合に該当するので、当該第３の操作を行う。更に、重なりノード３Ｂ〔ｓ３，Ｌ〕については、図９の場合に該当するので、当該第４の操作を行う。これにより、重なりノードの状態は、
Ｂ〔０，ｓ１〕∪１Ｂ〔ｓ１，ｓ４〕∪４１〔ｓ４，ｒ１〕∪４Ｂ〔ｒ１，ｒ４〕∪Ｂ〔ｒ４，ｓ２〕∪２Ｂ〔ｓ２，ｓ５〕∪５２Ｂ〔ｓ５，ｒ２〕∪５Ｂ〔ｒ２，ｓ３〕∪５３Ｂ〔ｓ３，Ｌ〕
となる。
【００５４】
ここで、重なりノード５２Ｂ〔ｓ５，ｒ２〕及び５３Ｂ〔ｓ３，Ｌ〕は、各々、３本の配線により構成される重なりノードである。そこで、この２個の領域について、クリティカルエリアを算出する演算を、図３に示す式を用いて行う。この時、前述のように、当該配線（この場合、第２及び第３の配線）の上下の領域についてのクリティカルエリアの値、及び、配線Ｂに接する領域についてのクリティカルエリアの値が算出される。
【００５５】
この後、前述のように、重なりノード５２Ｂ〔ｓ５，ｒ２〕及び５３Ｂ〔ｓ３，Ｌ〕における最下層の配線（この場合は、共に配線Ｂ）を処理対象から除外する。これにより、重なりノードの状態は、
Ｂ〔０，ｓ１〕∪１Ｂ〔ｓ１，ｓ４〕∪４１〔ｓ４，ｒ１〕∪４Ｂ〔ｒ１，ｒ４〕∪Ｂ〔ｒ４，ｓ２〕∪２Ｂ〔ｓ２，ｓ５〕∪５２〔ｓ５，ｒ２〕∪５Ｂ〔ｒ２，ｓ３〕∪５３〔ｓ３，Ｌ〕
となる。この状態を図１７に示す。図１７において、斜線を付した部分は、現在のクリティカルエリアの演算の処理対象である領域を示す。一方、斜線を付していない部分は、クリティカルエリアの演算の済んだ領域（第１、第２及び第３の配線の下部の一部領域）か、又は、配線が走査されていない部分である（ステップＳ１３）。
【００５６】
以上ようなトラック走査、重なりノード操作及びクリティカルエリアの算出を、最上層の配線Ｔまで繰り返し実行して（ステップＳ１５）、当該ＬＳＩチップ全体のクリティカルエリアを計算する。
【００５７】
以上から判るように、本発明の実施の形態の特徴を列記すると以下のとおりである。
（付記１）  配線のクリティカルエリアを算出するクリティカルエリア演算装置におけるクリティカルエリア演算方法であって、
配線データを所定の方向に走査し、
当該走査の結果に基づいて、相互に平行に配置される３本の配線の存在する領域を検出し、
当該検出した領域について、クリティカルエリアを算出する
ことを特徴とするクリティカルエリア演算方法。
（付記２）  前記クリティカルエリアを算出した領域について、その３本の配線の中で前記走査において最初に検出された配線を当該領域から除外する
ことを特徴とする付記１に記載のクリティカルエリア演算方法。
（付記３）  当該処理対象の配線領域の下辺及び上辺は、各々、その全体に形成された配線とみなし、
前記配線は、当該配線とその左側の配線のない区間とを一体の区間として構成される
ことを特徴とする付記１に記載のクリティカルエリア演算方法。
（付記４）  前記相互に平行に配置される３本の配線の存在する領域は、相互に平行に配置される２本の配線に対して、他の１本の配線の重なりを調べることにより検出する
ことを特徴とする付記１に記載のクリティカルエリア演算方法。
（付記５）  前記相互に平行に配置される２本の配線の存在する領域であって、当該配線が同じで隣接する２個の領域をマージして１個の領域とする
ことを特徴とする付記４に記載のクリティカルエリア演算方法。
（付記６）  配線のクリティカルエリアを算出するクリティカルエリア演算装置であって、
配線データを所定の方向に走査し、当該走査の結果に基づいて、相互に平行に配置される３本の配線の存在する領域を検出するノード操作手段と、
当該検出した領域について、クリティカルエリアを算出する算出手段とを備える
ことを特徴とするクリティカルエリア演算装置。
（付記７）  配線のクリティカルエリアを算出するクリティカルエリア演算方法を実現するクリティカルエリア演算プログラムであって、
前記プログラムは、コンピュータに、
配線データを所定の方向に走査させ、
当該走査の結果に基づいて、相互に平行に配置される３本の配線の存在する領域を検出させ、
当該検出した領域について、クリティカルエリアを算出させる
ことを特徴とするクリティカルエリア演算プログラム。
（付記８）  配線のクリティカルエリアを算出するクリティカルエリア演算方法を実現するプログラムを記録するプログラム記憶媒体であって、
前記プログラムは、コンピュータに、
配線データを所定の方向に走査させ、
当該走査の結果に基づいて、相互に平行に配置される３本の配線の存在する領域を検出させ、
当該検出した領域について、クリティカルエリアを算出させる
ことを特徴とするプログラム記録媒体。
【００５８】
【発明の効果】
以上説明したように、本発明によれば、クリティカルエリア演算方法において、任意の形状をとる配線についての普遍性が高い手法を用いることなく、配線方向への細長い長方形が平行に並んでいる形状の配線領域を検出して、この領域についてのみ、この領域の長さ及び座標を用いて、そのクリティカルエリアＡＣを算出する。これにより、配線データを走査するのみで、比較的簡単なアルゴリズムで、短い計算時間で、クリティカルエリアＡＣを近似的に計算することができ、ショート故障頻度等の指標とすることができる。また、比較的簡単なアルゴリズムであるので、コンピュータへ容易に実装することができる。
【図面の簡単な説明】
【図１】クリティカルエリア演算装置構成図である。
【図２】クリティカルエリア演算説明図である。
【図３】クリティカルエリア演算説明図である。
【図４】クリティカルエリア演算説明図である。
【図５】クリティカルエリア演算説明図である。
【図６】クリティカルエリア演算説明図である。
【図７】クリティカルエリア演算説明図である。
【図８】クリティカルエリア演算説明図である。
【図９】クリティカルエリア演算説明図である。
【図１０】クリティカルエリア演算説明図である。
【図１１】クリティカルエリア演算説明図である。
【図１２】クリティカルエリア演算説明図である。
【図１３】クリティカルエリア演算処理フローである。
【図１４】クリティカルエリア演算説明図である。
【図１５】クリティカルエリア演算説明図である。
【図１６】クリティカルエリア演算説明図である。
【図１７】クリティカルエリア演算説明図である。
【図１８】半径ｒのデフェクトに対する（配線ショートの）クリティカルエリアを示す概念図である。
【符号の説明】
１    演算処理部
２    配線データ格納部
３    クリティカルエリア格納部
１１    ノード操作処理部
１２    算出処理部
１３    マージ処理部
【図１】
0004071537.tif 000003
【図２】
0004071537.tif 000004
【図３】
0004071537.tif 000005
【図４】
0004071537.tif 000006
【図５】
0004071537.tif 000007
【図６】
0004071537.tif 000008
【図７】
0004071537.tif 000009
【図８】
0004071537.tif 000010
【図９】
0004071537.tif 000011
【図１０】
0004071537.tif 000012
【図１１】
0004071537.tif 000013
【図１２】
0004071537.tif 000014
【図１３】
0004071537.tif 000015
【図１４】
0004071537.tif 000016
【図１５】
0004071537.tif 000017
【図１６】
0004071537.tif 000018
【図１７】
0004071537.tif 000019
【図１８】
0004071537.tif 000020