(57)【要約】【課題】計算量の増加を抑えつつホットスポット候補となる配線箇所を精度よく検出する。【解決手段】処理部３１，７４は、露光パターンに含まれる複数の配線パターンのそれぞれから生成されるドロネー三角網に基づき、複数のノードベクトルを生成し、前記複数のノードベクトルの各要素と、蓄積された、ホットスポットに対応したノードベクトルに関するノードベクトル情報に基づき、候補ノードベクトル群を抽出し、前記候補ノードベクトル群に含まれる各ードベクトルについて、当該ノードベクトルに対応するドロネー三角網を参照し、当該ノードベクトルが参照するノードと隣接ノードとの距離に関する複数の距離評価値を算出し、前記複数の距離評価値に基づき、候補ノードベクトル群から、ホットスポット候補となる特定配線ノードベクトル群を抽出し、前記特定配線ノードベクトル群から、前記露光パターンにおけるホットスポットの発生箇所の候補を特定する。【選択図】図１４
2018165887.tif 000002
【特許請求の範囲】
【請求項１】
露光パターンに含まれる複数の配線パターンのそれぞれから生成されるドロネー三角網に基づき、前記ドロネー三角網における複数の三角形それぞれの中心に対応するノードに関連付けて、当該ノードおよび当該ノードの隣接ノードの情報を含む複数のノードベクトルを生成し、
前記複数のノードベクトルの各要素、および、記憶部に蓄積された、ホットスポットに対応したノードベクトルに関するノードベクトル情報に基づき、前記複数のノードベクトルから候補ノードベクトル群を抽出し、
前記候補ノードベクトル群に含まれるノードベクトルのそれぞれについて、当該ノードベクトルに対応するドロネー三角網を参照し、当該ノードベクトルが参照するノードと隣接ノードとの距離に関する複数の距離評価値を算出し、 
前記複数の距離評価値に基づき、前記候補ノードベクトル群から、ホットスポット候補となる特定配線ノードベクトル群を抽出し、
前記特定配線ノードベクトル群に基づき、前記露光パターンにおけるホットスポットの発生箇所の候補を特定する、
処理を、コンピュータに実行させる、予測プログラム。
【請求項２】
前記複数の距離評価値を、前記ノードと前記隣接ノードとを接続するエッジの重みとして与えられる、前記ノードと前記隣接ノードとの前記距離に応じた値に基づき算出する、
処理を、前記コンピュータに実行させる、請求項１に記載の予測プログラム。
【請求項３】
前記エッジの前記重みを、前記複数のノードベクトルの生成時に前記ノードの情報として付与する、
処理を、前記コンピュータに実行させる、請求項２に記載の予測プログラム。
【請求項４】
処理部を有し、
前記処理部は、
露光パターンに含まれる複数の配線パターンのそれぞれから生成されるドロネー三角網に基づき、前記ドロネー三角網における複数の三角形それぞれの中心に対応するノードに関連付けて、当該ノードおよび当該ノードの隣接ノードの情報を含む複数のノードベクトルを生成し、
前記複数のノードベクトルの各要素、および、記憶部に蓄積された、ホットスポットに対応したノードベクトルに関するノードベクトル情報に基づき、前記複数のノードベクトルから候補ノードベクトル群を抽出し、
前記候補ノードベクトル群に含まれるノードベクトルのそれぞれについて、当該ノードベクトルに対応するドロネー三角網を参照し、当該ノードベクトルが参照するノードと前記隣接ノードとの距離に関する複数の距離評価値を算出し、
前記複数の距離評価値に基づき、前記候補ノードベクトル群から、ホットスポット候補となる特定配線ノードベクトル群を抽出し、
前記特定配線ノードベクトル群から、前記露光パターンにおけるホットスポットの発生箇所の候補を特定する、予測装置。
【請求項５】
処理部が、
露光パターンに含まれる複数の配線パターンのそれぞれから生成されるドロネー三角網に基づき、前記ドロネー三角網における複数の三角形それぞれの中心に対応するノードに関連付けて、当該ノードおよび当該ノードの隣接ノードの情報を含む複数のノードベクトルを生成し、
前記複数のノードベクトルの各要素、および、記憶部に蓄積された、ホットスポットに対応したノードベクトルに関するノードベクトル情報に基づき、前記複数のノードベクトルから候補ノードベクトル群を抽出し、
前記候補ノードベクトル群に含まれるノードベクトルのそれぞれについて、当該ノードベクトルに対応するドロネー三角網を参照し、当該ノードベクトルが参照するノードと隣接ノードとの距離に関する複数の距離評価値を算出し、
前記複数の距離評価値に基づき、前記候補ノードベクトル群から、ホットスポット候補となる特定配線ノードベクトル群を抽出し、
前記特定配線ノードベクトル群に基づき、前記露光パターンにおけるホットスポットの発生箇所の候補を特定する、予測方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本件は、予測プログラム、予測装置、および予測方法に関する。
【背景技術】
【０００２】
近年、ＬＳＩ（Large Scale Integration）等の集積回路は、微細化技術の発展に伴って、トランジスタや配線の寸法が光の波長よりも小さくなっている。このため、リソグラフィ工程において、設計されたレイアウトパターンどおりに形成されたマスクにより露光を行なっても、光近接効果（Optical Proximity Effect）により、レイアウトパターンどおりに露光できない箇所が集積回路に生じる場合がある。
【０００３】
例えば、レイアウトパターンどおりに形成されたマスクによりウエハ上に配線パターンを露光しても、ウエハ上に形成される配線パターンが細かくなって断線したり、逆に配線パターンが太くなってショートしたり、といった欠陥が発生する場合がある。このような欠陥の発生する可能性の高い箇所のことを、以下「欠陥箇所」または「ホットスポット」と呼ぶ。このため、集積回路のレイアウトパターンから、ホットスポットが発生する箇所を事前に予測検出することにより、歩留まりを向上させる取り組みが行なわれている。なお、配線パターンは、レイアウトパターンに含まれる。
【０００４】
ホットスポットの発生は、配線の折れ曲がりや、周囲との位置関係により生じることが知られている。
【０００５】
そこで、ドロネー三角網によりレイアウトパターンを表現し、ドロネー三角網から得られるノード毎に、各ノードの属性情報をベクトル化し、ベクトル化した情報（ビットラベル）を用いて、ホットスポットが生じ得る類似パターンを検出することで、ホットスポットの発生箇所を予測する技術が存在する。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２０１６−１３３９３６号公報
【特許文献２】特開２０００−２００２９８号公報
【特許文献３】特開２０１３−１０９５４５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
上述のごとくビットラベルを利用した類似パターンの検出により、ある程度、ホットスポット候補を絞り込むことはできる。しかし、配線パターンの相対的な位置関係が同じでも、サイズや間隔の組み合わせによりホットスポットの発生有無が異なる状況（例えば図１参照）を反映できるほどの精度は得られないという課題がある。図１に示す例では、三本の矢印で示す長さ（配線パターンの間隔や配線パターンの長さ）の組み合わせの違いによって、ホットスポットが発生する場合（図１の右側）と発生しない場合（図１の左側）とがある。なお、図１において、網掛け部分はレイアウトパターンを示す。
【０００８】
一方、ベクトル（ビットラベル）において距離情報を示すビットの数を増加させることにより、ベクトル化段階での距離の高精度化は可能である。しかし、距離が離散的になることにより、却って、類似パターンの検出に支障が出てしまうなどの課題がある。
【０００９】
１つの側面では、本件は、計算量の増加を抑えつつ、ホットスポット候補となる配線箇所を精度よく検出することを目的とする。
【課題を解決するための手段】
【００１０】
本件の予測プログラムは、コンピュータに、以下の処理（１）〜（５）を実行させる。
（１）露光パターンに含まれる複数の配線パターンのそれぞれから生成されるドロネー三角網に基づき、前記ドロネー三角網における複数の三角形それぞれの中心に対応するノードに関連付けて、当該ノードおよび当該ノードの隣接ノードの情報を含む複数のノードベクトルを生成する処理。
（２）前記複数のノードベクトルの各要素、および、記憶部に蓄積された、ホットスポットに対応したノードベクトルに関するノードベクトル情報に基づき、前記複数のノードベクトルから候補ノードベクトル群を抽出する処理。
（３）前記候補ノードベクトル群に含まれるノードベクトルのそれぞれについて、当該ノードベクトルに対応するドロネー三角網を参照し、当該ノードベクトルが参照するノードと隣接ノードとの距離に関する複数の距離評価値を算出する処理。
（４）前記複数の距離評価値に基づき、前記候補ノードベクトル群から、ホットスポット候補となる特定配線ノードベクトル群を抽出する処理。
（５）前記特定配線ノードベクトル群に基づき、前記露光パターンにおけるホットスポットの発生箇所の候補を特定する処理。
【発明の効果】
【００１１】
計算量の増加を抑えつつ、ホットスポット候補となる配線箇所を精度よく検出することができる。
【図面の簡単な説明】
【００１２】
【図１】配線パターンの相対的な位置関係が同じでも、サイズや間隔の組み合わせによりホットスポット発生の有無が異なる状況の一例を示す図である。
【図２】関連手法におけるビットラベルの例を示す図である。
【図３】関連手法におけるレイアウトパターンのグラフ表現を説明する図である。
【図４】関連手法におけるノードラベルの構造を説明する図である。
【図５】（Ａ）は配線パターンの中心から着目ノードまでの距離の４段階表現を説明する図、（Ｂ）は配線パターンの中心から着目ノードへの方向の４段階表現を説明する図である。
【図６】ノードラベルに含まれる隣接情報の計算例を説明する図である。
【図７】関連手法における類似度計算アルゴリズムを示す図である。
【図８】（Ａ）および（Ｂ）は関連手法における課題を説明する図であり、（Ａ）はホットスポットが有る場合のグラフとノードラベルの例を示す図、（Ｂ）はホットスポットが無い場合のグラフとノードラベルの例を示す図である。
【図９】（Ａ）および（Ｂ）は関連手法において距離情報のビット数を増加させた際の効果および課題を説明する図であり、（Ａ）はホットスポットが有る場合のグラフとノードラベルの例を示す図、（Ｂ）はホットスポットが無い場合のグラフとノードラベルの例を示す図である。
【図１０】（Ａ）は、関連手法による、ノードラベルを付与したグラフの例を示す図、（Ｂ）は、本実施形態の手法による、ノードラベルおよびエッジ重みを付与したグラフの例を示す図である。
【図１１】関連手法のノードラベルと本手法でグラフに付与されるノードラベルおよびエッジ重みとを対比して示す図である。
【図１２】（Ａ）および（Ｂ）は類似度計算対象の二つのグラフの構造を示す図である。
【図１３】本実施形態の手法における類似度計算アルゴリズムを示す図である。
【図１４】本実施形態の予測装置の全体構成を示すブロック図である。
【図１５】本実施形態における既知パターンデータに含まれる既知パターンの一例を示す図である。
【図１６】（Ａ）〜（Ｃ）はドロネー三角分割の流れを説明する図である。
【図１７】自ノードと隣接ノードとの接続関係を示す図である。
【図１８】自ノードラベルに接続情報を付与する手法を説明する図である。
【図１９】本実施形態におけるグラフ生成部の動作を説明するフローチャートである。
【図２０】本実施形態におけるノードラベル生成部の動作を説明するフローチャートである。
【図２１】本実施形態における隣接情報付与部の動作を説明するフローチャートである。
【図２２】本実施形態におけるエッジ重み付与部の動作を説明するフローチャートである。
【図２３】本実施形態における識別モデル生成部の動作を説明するフローチャートである。
【図２４】本実施形態における類似度計算動作を説明するフローチャートである。
【図２５】本実施形態における類似度評価部の動作を説明するフローチャートである。
【図２６】本実施形態におけるエラー識別部の動作を説明するフローチャートである。
【図２７】未知パターンのエラーに関する情報を表示するとともに、未知パターンとの類似度が高い既知パターンに関する情報を類似度の高い順に表示する画面の一例を示す図である。
【図２８】本実施形態の予測プログラムを実行するコンピュータを示すブロック図である。
【発明を実施するための形態】
【００１３】
以下に、図面を参照し、本願の開示する予測プログラム、予測装置、および予測方法の実施形態について、詳細に説明する。ただし、以下に示す実施形態は、あくまでも例示に過ぎず、実施形態で明示しない種々の変形例や技術の適用を排除する意図はない。すなわち、本実施形態を、その趣旨を逸脱しない範囲で種々変形して実施することができる。また、各図は、図中に示す構成要素のみを備えるという趣旨ではなく、他の機能を含むことができる。そして、各実施形態は、処理内容を矛盾させない範囲で適宜組み合わせることが可能である。
【００１４】
〔１〕関連技術
まず、図２〜図９を参照しながら、本実施形態で説明する技術に関連する、リソグラフィホットスポットの発生箇所を予測する手法（関連手法ともいう）の一例について説明する。当該関連手法では、レイアウトパターンがドロネー三角網により表現され、ドロネー三角網から得られるノード毎に各ノードの属性情報がベクトル化される。そして、ベクトル化した情報であるビットラベルを用いて、ホットスポットが生じ得る類似パターンが検出され、ホットスポットの発生箇所が予測される。ビットラベルは、ノードラベル、あるいは単にラベルともいう。
【００１５】
より具体的に、当該関連手法は、ドロネー三角網の接続構造を扱うことができる、一般的なグラフカーネルを用いた、リソグラフィエラー識別モデルの生成手法、および、当該識別モデルによるエラー識別手法を含む。当該関連手法では、レイアウトパターンから生成した、ドロネー三角網に基づいたグラフにおける、ノードの属性情報と接続情報とが、図２に示すように、ビットラベルで表現される。そして、二つのグラフ間の類似度が、ノード毎のビットラベルを用いて計算される。
【００１６】
図２は、当該関連手法におけるビットラベルの例を示す図である。図２に示すように、ドロネー三角網の各三角形の中心（重心）をノードとし、各ノードに係る情報（属性情報および接続情報）がビットラベル（一のノードについて例えば８ビットのラベル）で表現される。なお、図２において、網掛け部分はレイアウトパターンを示す。また、接続情報は、着目ノードに接続される隣接ノード（隣接構造）に係る隣接情報であり、当該隣接情報については後述する。
【００１７】
図３は、当該関連手法におけるレイアウトパターン（配線パターン）のグラフ表現を説明する図である。図３に示すように、当該関連手法では、レイアウトパターンと、当該レイアウトパターンから生成したドロネー三角網に基づいたグラフとが、入力として与えられる。そして、グラフにおける各三角形の中心に対応する各ノードの属性情報がビットラベルで表現されてグラフに付与される。さらに、各ノードの隣接情報がビットラベルで表現されてグラフに付与される。これにより、ラベル付きドロネー三角網（ラベル付きグラフ）が出力され、このようなラベル付きグラフを用いて、二つのグラフ間の類似度が計算される。なお、図３において、網掛け部分はレイアウトパターンを示す。
【００１８】
ここで、図４を参照して、当該関連手法におけるノードラベル（ビットラベル）の構造について説明する。図４に示すように、ラベルは、着目ノード自身（以下、自ノードという）の特徴である属性情報を含む自ノード情報と、隣接ノードに係る隣接情報とを、ビット列で表現したものである。属性情報としては、例えば、配線ビア種別や三角形頂点の凹凸など、欠陥識別に有用な属性が表現される。図４に示す例では、左側に示すグラフ（配線パターン）における太枠三角形の重心に対応する自ノードv0のラベルが、１２ビットで表現されている。
【００１９】
自ノード情報としては、自ノードv0の位置情報（距離と方向）および電気的特性が含まれる。
【００２０】
距離は、グラフ（配線パターン；図４の左側参照）の中心から自ノードv0までの距離であり、例えば図５（Ａ）に示すごとく、０〜３の４段階（２ビット）で表現される。つまり、グラフ中心に対し自ノードv0が０；１；２；３の領域に存在する場合、ラベルにおける距離ビットは、それぞれ００；０１；１０；１１になる。図５（Ａ）は配線パターンの中心から着目ノードまでの距離の４段階（２ビット）表現を説明する図である。
【００２１】
方向は、グラフ（配線パターン；図４の左側参照）の中心から自ノードv0への方向であり、例えば図５（Ｂ）に示すごとく、０〜３の４段階（２ビット）で表現される。つまり、グラフ中心に対し自ノードv0が０；１；２；３の領域に存在する場合、ラベルにおける方向ビットは、それぞれ００；０１；１０；１１になる。図５（Ｂ）は配線パターンの中心から着目ノードへの方向の４段階（２ビット）表現を説明する図である。
【００２２】
電気的特性は、例えば、自ノードv0に対応する三角形の頂点が属する、配線パターンの多角形の数であり、上述した距離や方向と同様、０〜３の４段階（２ビット）で表現される。
【００２３】
なお、自ノードv0の距離，方向，電気的特性をそれぞれラベルにおける２ビット値に変換するための情報、つまり図５（Ａ）や図５（Ｂ）などの０〜３を２ビット値に対応付けるための情報は、例えばビットデータ（図１４の符号４１参照）として予め登録される。
【００２４】
一方、隣接情報は、図６に示すように、自ノードv0および隣接ノードv1，v2，v3についての自ノード情報である自ノードラベルＳ(vi)（i＝0, 1, 2, 3）の論理演算結果として定義される。例えば、ノードv0の隣接情報は、Ｓ(v0), Ｓ(v1), Ｓ(v2), Ｓ(v3)の排他的論理和（ＸＯＲ）とする。つまり、図６に示す例において、隣接情報は６ビットの値であり、Ｓ(v0)＝“010101”、Ｓ(v1)＝“010101”、Ｓ(v2)＝“100101”、Ｓ(v3)＝“011010”であるため、ノードv0の隣接情報＝ＸＯＲ(Ｓ(v0), Ｓ(v1), Ｓ(v2), Ｓ(v3))＝“111111”となる。図６は、ノードラベル（ビットラベル）に含まれる隣接情報の計算例を説明する図である。
【００２５】
次に、当該関連手法における類似度計算の具体例について説明する。ここでは、二つのグラフG1とグラフG2との類似度Ｋを、図７に示す類似度計算アルゴリズムによって計算する場合について説明する。
【００２６】
このとき、入力は、グラフG1のノードラベルのリストL1と、グラフG2のノードラベルのリストL2とする。なお、リストL1およびリストL2は、それぞれラベルの値でソート済みであり、リストL1およびリストL2の長さlength(L1)およびlength(L2)はそれぞれn1およびn2とする。ここで、グラフG1のリストL1およびグラフG2のリストL2は、それぞれ、例えば以下のような４組のビット列を含むため、n1＝n2＝４である。
【００２７】
グラフG1のリストL1
＝{“010101010101”, “010101111111”, “011010011010”, “100101100101”}
グラフG2のリストL2
＝{“010101010101”, “010101111111”, “011101011001”, “011110010111”}
【００２８】
上述のような入力に対し、図７に示す類似度計算アルゴリズムに基づく処理を行なうことで、グラフG1とグラフG2との類似度Ｋが、例えば以下のように計算される。
【００２９】
つまり、リストL1およびリストL2の先頭から順にラベルが比較され、ラベルの一致数cが計算される。図７に示す類似度計算アルゴリズムにおいて、関数match(L1[i], L2[j])は、ラベルL1[i]とラベルL2[j]とが一致すれば“１”となり、ラベルL1[i]とラベルL2[j]とが一致しなければ“０”となる。match(L1[i], L2[j])が1の場合、関数weightが計算され計算結果が一致数cに加算される。関数weight(L1[i], L2[j])は、ラベルL1[i], L2[j]の重み関数であり、０以上１以下の実数値をとる。図７に示す類似度計算アルゴリズムに基づく処理の結果として、グラフG1とグラフG2との類似度Ｋ＝c / (n1+n2-c)が計算されて出力される。
【００３０】
上述したリストL1およびリストL2では、ラベルL1[0]とラベルL2[0]とが一致するとともに、ラベルL1[1]とラベルL2[1]とが一致する。さらに、weight(L1[0], L2[0])＝１かつweight(L1[1], L2[1])＝１とすると、c＝２であり、類似度Ｋ＝２／（４＋４−２）＝0.333...が計算される。
【００３１】
なお、グラフG1とグラフG2とが同一である場合、c＝n1＝n2となるため、グラフG1とグラフG2との類似度Ｋ＝c / (n1+n2-c)＝c / c＝1.0となる。
【００３２】
次に、図８（Ａ）および図８（Ｂ）を参照しながら、当該関連手法における課題について説明する。図８（Ａ）はホットスポット（欠陥）が有る場合のグラフ(a)とノードラベルの例を示す図であり、図８（Ｂ）はホットスポット（欠陥）が無い場合のグラフ(b)とノードラベルの例を示す図である。
【００３３】
上述した関連技術における距離をラベルで表現する手法では、二つのグラフの図形間の相対的な位置関係（隣接情報）が一致し、距離のラベル（２ビット）が一致すれば、二つのグラフは同一であると評価される。実際のパターンでは、距離の微小な違いでホットスポットが発生したり発生しなかったりする。このため、距離が４段階（２ビット）で離散的に表現される当該関連手法では、距離の微小な違いを識別することは難しい。
【００３４】
例えば、図８（Ａ）に示す欠陥ありの配線パターン(a)と、図８（Ｂ）に示す欠陥なしの配線パターン(b)とでは、二つの配線パターン(a)と(b)とにおける多角形の位置関係が類似するが、配線パターン(a)で欠陥があり、配線パターン(b)で欠陥がない。このような場合、距離のラベルを２ビットで表現とすると、配線パターン(a)および(b)における太枠三角形の中心に対応するノードv0の距離（太線矢印の長さ）のラベルは、図８（Ａ）および図８（Ｂ）に示すように同じラベル“０１”になる。従って、図８（Ａ）に示すラベルと図８（Ｂ）に示すラベルとは同一になり、配線パターン(a)と配線パターン(b)とは同じであると認識され、欠陥（ホットスポット）を認識することができない。
【００３５】
そこで、ノードラベルにおいて、距離のラベル長つまり距離のビット数を増やせば、配線パターン(a)と配線パターン(b)とを異なるパターンとして認識することが可能になる。図９（Ａ）および図９（Ｂ）を参照しながら、当該関連手法において距離情報のビット数を増加させた際の効果および課題について説明する。図９（Ａ）はホットスポット（欠陥）が有る場合のグラフ(a)とノードラベルの例を示す図であり、図９（Ｂ）はホットスポット（欠陥）が無い場合のグラフ(b)とノードラベルの例を示す図である。
【００３６】
例えば、図９（Ａ）および図９（Ｂ）に示すように、距離のラベル長つまり距離のビット数を２ビットから４ビットに拡張すると、２ビットの場合に比べ、距離を１６段階で表現することができる。したがって、例えば、配線パターン(a)の距離ラベルは“０１”から“００１０”になり、配線パターン(b)の距離ラベルは“０１”から“０１０１”になり、配線パターン(a)と配線パターン(b)とを異なるパターンとして認識することが可能になる。
【００３７】
しかしながら、上述のように距離のビット数を拡張すると、距離の微小な違いでラベル値が変化し異なる値になるため、類似度計算においてラベルの一致数cが減ってしまう。したがって、二つのグラフ間の類似度Ｋは大きく低下し、類似するパターンを認識し難くなるという課題がある。
【００３８】
〔２〕本実施形態の概要
次に、図１０（Ａ）〜図１３を参照しながら、本実施形態の概要について、上述した関連手法と対比して説明する。
【００３９】
図１０（Ａ）は、上述した関連手法による、ノードラベルを付与したグラフの例を示す図である。図１０（Ａ）に示すように、上述した関連手法では、ノード毎に、距離や方向に関する属性を含むラベルが生成される。図１０（Ａ）に示す例では、ラベルは１２ビットであり、下線を付した部分が、距離や方向に関する属性に係るビットである。そして、関連手法では、距離に関する属性は、パターン中心位置○から着目ノード（自ノード）の位置ｘまでの距離として、ラベルで表現される。
【００４０】
これに対し、本実施形態の手法では、ラベルで表現されていたノード位置に関する属性（例えば距離，方向）が、自ノードと隣接ノードとの間の距離に対応する値として、ドロネー三角網に基づくグラフのエッジの重みで表現される。そして、類似度計算において、エッジに付与された重みが考慮される。
【００４１】
図１０（Ｂ）は、本実施形態の手法による、ノードラベルおよびエッジ重みを付与したグラフの例を示す図である。図１０（Ｂ）に示すように、本実施形態の手法（本手法）では、ノード位置に関する属性（例えば距離，方向）を、ラベルで表現するのに代え、エッジに付与される重み（例えば1.2）で表現する。したがって、本実施形態の手法のラベルでは、図１０（Ａ）に示すラベルで下線を付した８ビット分のビット列が削除されている。つまり、本実施形態の手法のラベルでは、自ノードの相対的位置関係に関する属性（例えば電気的特性）とそれに対応する隣接情報とのみが考慮されて表現される。
【００４２】
このように、本実施形態の手法によれば、ノード毎のラベルでは相対的位置関係に関する属性のみが考慮され、ノード間距離に対応するエッジの重みが類似度計算に際して考慮される。これにより、図形サイズや図形間隔の微小な差異を表現することができる。つまり、ラベルを用いて相対的位置関係の認識精度を保ちつつ、距離の微小な差異によるリソグラフィホットスポット発生有無の認識精度を向上させることができる。
【００４３】
ここで、図１０（Ａ）や図１０（Ｂ）に示すように、配線パターンから生成された、ドロネー三角網に基づくグラフにおいて、任意のノードに接続されるエッジの数は高々３である。このため、二つのグラフの類似度計算において、エッジの対応付けと重み計算とによる計算コストの増加は限定的であり、本実施形態では、一ノードについて最大３回の重み計算が追加されるだけである。したがって、以下のように、計算量の増加を抑えつつ、ホットスポット候補となる配線箇所を精度よく検出することができる。
【００４４】
図１１は、関連手法のノードラベルと本手法でグラフに付与されるノードラベルおよびエッジ重みとを対比して示す図である。図１１に示すように、関連手法では、自ノードv0の距離（太線矢印の長さ）のラベルは、配線パターン(a)と(b)とで同じラベル“０１”になる。これに対し、例えば図１１に示すように、本手法では、配線パターン(a)のグラフにおける、自ノードv0に接続するエッジv0-v1, v0-v2, v0-v3には、それぞれ、ノード間距離に対応する重み1.0, 1.0, 1.0が付与される。同様に、配線パターン(b)のグラフにおける、自ノードv0に接続するエッジv0-v1, v0-v2, v0-v3には、それぞれ、ノード間距離に対応する重み1.0, 1.0, 1.2が付与される。
【００４５】
このように付与されたエッジの重みを、類似度計算に際して考慮することで、図１１に示すような配線パターン(a)と(b)とを識別することが可能になる。
【００４６】
次に、本実施形態の手法における類似度計算の具体例について説明する。ここでは、二つのグラフG1とグラフG2との類似度Ｋを、図１３に示す類似度計算アルゴリズムによって計算する場合について説明する。
【００４７】
なお、類似度計算対象の二つのグラフG1およびグラフG2の構造をそれぞれ図１２（Ａ）および図１２（Ｂ）に示す。図１２（Ａ）に示すように、グラフG1において、自ノード（着目ノード）をv1[0]、自ノードv1[0]に隣接する３つの隣接ノードをそれぞれv1[1], v1[2], v1[3]とする。また、ノードv1[0]とノードv1[1]とを接続するエッジをe1[0]、ノードv1[0]とノードv1[2]とを接続するエッジをe1[1]、ノードv1[0]とノードv1[3]とを接続するエッジをe1[2]とする。同様に、図１２（Ｂ）に示すように、グラフG2において、自ノード（着目ノード）をv2[0]、自ノードv2[0]に隣接する３つの隣接ノードをそれぞれv2[1], v2[2], v2[3]とする。また、ノードv2[0]とノードv2[1]とを接続するエッジをe2[0]、ノードv2[0]とノードv2[2]とを接続するエッジをe2[1]、ノードv2[0]とノードv2[3]とを接続するエッジをe2[2]とする。
【００４８】
このとき、入力は、グラフG1の自ノードv1[0]のラベルリストL1と、自ノードv1[0]に接続するエッジの重みリストw1と、グラフG2の自ノードv2[0]のラベルリストL2と、自ノードv2[0]に接続するエッジの重みリストw2とを含む。
【００４９】
なお、リストL1およびリストL2は、それぞれラベルの値でソート済みであり、リストL1およびリストL2の長さlength(L1)およびlength(L2)はそれぞれn1およびn2とする。ここで、グラフG1のリストL1およびグラフG2のリストL2は、それぞれ、例えば以下のような４組のビット列を含むため、n1＝n2＝４である。
【００５０】
具体的に、入力は、下記のような、グラフG1, G2におけるノードとエッジの接続関係G1(V1,E1), G2(V2,E2)と、グラフG1, G2におけるノードラベルリストL1, L2と、グラフG1, G2におけるエッジの長さリストl1, l2と、グラフG1, G2におけるエッジの重みリストw1, w2とを含む。
【００５１】
グラフG1におけるノードV1とエッジE1の接続関係をG1(V1,E1)とし、グラフG2におけるノードV2とエッジE2との接続関係をG2(V2,E2)とすると、G1(V1,E1)およびG2(V2,E2)は、以下のように記述される。
【００５２】
G1(V1,E1)={V1={v1[0],v1[1],v1[2],v1[3]}, E1={e1[0],e1[1],e1[2]}}
G2(V2,E2)={V2={v2[0],v2[1],v2[2],v2[3]}, E2={e2[0],e2[1],e2[2]}}
【００５３】
ノードv1[i]のラベルはL1[i]に対応し、ノードv2[i]のラベルはL2[i]に対応する。ラベルL1[i]およびL2[i]は、自ノードの相対的位置関係に関する属性（例えば電気的特性）を表現する。そして、グラフG1のノードラベルリストL1(V1)およびグラフG2のノードラベルリストL2(V2)は、例えば以下のように与えられる。
【００５４】
グラフG1のノードラベルリストL1(V1)
＝{“0101”, “0101”, “0111”, “1010”}
グラフG2のノードラベルリストL2(V2)
＝{“0101”, “0101”, “0111”, “1010”}
【００５５】
グラフG1, G2にそれぞれ対応するエッジの長さリストl1, l2は、例えば以下のように与えられる。
【００５６】
グラフG1のエッジ(e1[0],e1[1],e1[2])の長さリスト l1={1.0, 1.2, 1.5}
グラフG2のエッジ(e2[0],e2[1],e2[2])の長さリスト l2={1.0, 0.9, 1.2}
【００５７】
このとき、グラフG1におけるノードv1[i]に接続するエッジの重みリストw1およびグラフG2におけるノードv2[i]に接続するエッジの重みリストw2は、それぞれ以下のように与えられる。
【００５８】
グラフG1: w1[0]={(v1[0]に接続するエッジの長さ)}=(1.0, 1.2, 1.5)
w1[1]={(v1[1]に接続するエッジの長さ)}=(1.0, 0.0, 0.0)
w1[2]={(v1[2]に接続するエッジの長さ)}=(1.2, 0.0, 0.0)
w1[3]={(v1[3]に接続するエッジの長さ)}=(1.5, 0.0, 0.0)
【００５９】
グラフG2: w2[0]={(v2[0]に接続するエッジの長さ)}=(1.0, 0.9, 1.2)
w2[1]={(v2[1]に接続するエッジの長さ)}=(1.0,0.0,0.0)
w2[2]={(v2[2]に接続するエッジの長さ)}=(0.9,0.0,0.0)
w2[3]={(v2[3]に接続するエッジの長さ)}=(1.2,0.0, 0.0)
【００６０】
なお、ドロネー三角網の各三角形が一つのノードに対応し、各三角形と辺を共有する最大３個の三角形が隣接ノードに対応する。したがって、各重みリストw1[i], w2[i]は、一つのノードに接続する３本のエッジの重みを含むリストになる。エッジの本数が３本未満の場合、重みリストw1[i]またはw2[i]における一以上の重み成分として重み“０”が設定される。
【００６１】
上述のような入力に対し、図１３に示す類似度計算アルゴリズムに基づく処理を行なうことで、グラフG1とグラフG2との類似度Ｋが、例えば以下のように計算される。
【００６２】
つまり、リストL1およびリストL2の先頭から順にラベルが比較され、ラベルの一致数cが計算される。図１３に示す類似度計算アルゴリズムにおいて、関数match(L1[i], L2[j])は、ラベルL1[i]とラベルL2[j]とが一致すれば“１”となり、ラベルL1[i]とラベルL2[j]とが一致しなければ“０”となる。match(L1[i], L2[j])が1の場合、関数weightが計算され計算結果が一致数cに加算される。
【００６３】
関数weight(v1[i], v2[j])は、グラフG1のノードv1[i]に接続するエッジの重みw1[i]と、グラフG2のノードv2[j]に接続するエッジの重みw2[j]とから決まるweight関数である。
【００６４】
そして、前記入力によれば、グラフG1,G2の類似度Ｋは、以下のように計算される。つまり、ノードv1[0]とv2[0]とのラベルが一致するとともに、ノードv1[1]とv2[1]とのラベルが一致するとき、関数weight(v1[i], v2[j])が下記(1)式によって計算される。
【００６５】
【数１】
2018165887.tif 000003
【００６６】
なお、係数αは、予め設定された値、または、後述する識別モデル生成部５３（図１４参照）で最適化された値である。ここでは、α＝１とする。
【００６７】
上記(1)式および図１３に示す類似度計算アルゴリズムに基づく処理の結果として、グラフG1とグラフG2との類似度Ｋ＝c / (n1+n2-c)が以下のように計算されて出力される。
【００６８】
一致度c ＝weight(v1[0],v2[0])+weight(v1[1],v2[1])
＝(exp(-(1.0-1.0)2)+exp(-(1.2-0.9)2)+exp(-(1.5-1.2)2))/3
＋(exp(-(1.0-1.0)2)+exp(-(0.0-0.0)2)+exp(-(0.0-0.0)2))/3
＝(1+0.91+0.91)/3+(1+1+1)/3
＝0.94+1
＝1.94
類似度Ｋ＝c / (n1+n2-c)＝1.94/(4+4-1.94)＝0.320
【００６９】
なお、グラフG1とグラフG2とが同一である場合、c＝n1＝n2となるため、グラフG1とグラフG2との類似度Ｋ＝c / (n1+n2-c)＝c / c＝1.0となる。
【００７０】
上述のごとく概要について説明した手法を実現すべく、本実施形態の手法では、コンピュータ（図２８の符号１００参照）によって、以下の処理（Ｐ１）〜（Ｐ５）が実行されてよい。
【００７１】
（Ｐ１）露光パターンに含まれる複数の配線パターンのそれぞれから生成されるドロネー三角網に基づき、当該ノードおよび当該ノードの隣接ノードの情報を含む複数のノードベクトルを生成する処理。このとき、前記複数のノードベクトルは、前記ドロネー三角網における複数の三角形それぞれの中心に対応するノードに関連付けて、生成される。前記複数のノードベクトルは、本実施形態の隣接情報考慮ラベルに相当する。
【００７２】
（Ｐ２）前記複数のノードベクトルの各要素、および、記憶部に蓄積された、ホットスポットに対応したノードベクトルに関するノードベクトル情報に基づき、前記複数のノードベクトルから候補ノードベクトル群を抽出する処理。前記候補ノードベクトル群は、本実施形態の隣接情報考慮ラベル付きグラフに相当する。前記記憶部は、後述する記憶部３０に相当する。
【００７３】
（Ｐ３）前記候補ノードベクトル群に含まれるノードベクトルのそれぞれについて、当該ノードベクトルに対応するドロネー三角網を参照し、当該ノードベクトルが参照するノードと隣接ノードとの距離に関する複数の距離評価値を算出する処理。前記距離評価値は、本実施形態の類似度に相当する。
【００７４】
（Ｐ４）前記複数の距離評価値に基づき、前記候補ノードベクトル群から、ホットスポット候補となる特定配線ノードベクトル群を抽出する処理。
【００７５】
（Ｐ５）前記特定配線ノードベクトル群に基づき、前記露光パターンにおける前記ホットスポットの発生箇所の候補を特定する処理。
【００７６】
このとき、前記複数の距離評価値は、前記ノードと前記隣接ノードとの前記距離に応じた値に基づき算出される。前記値は、前記ノードと前記隣接ノードとを接続するエッジの重みとして与えられる。また、前記エッジの前記重みを、前記複数のノードベクトルの生成時に前記ノードの情報として付与される（本実施形態の隣接情報考慮ラベル・エッジ重み付きグラフに相当）。
【００７７】
〔３〕本実施形態の予測装置の構成
本発明の一実施形態に係る予測装置１０について説明する。図１４は、本実施形態の予測装置１０の全体構成を示すブロック図である。予測装置１０は、ホットスポットの有無が未知のレイアウトパターンにおいて、ホットスポット発生箇所の候補を特定する、つまりホットスポット発生箇所を予測する装置である。そして、図１４に示すように、予測装置１０は、ホットスポット発生箇所の予測に用いる識別モデルを生成する識別モデル生成装置２０と、実際にホットスポット発生箇所の予測を行なう予測部６０によって構成される。
【００７８】
〔３−１〕本実施形態の識別モデル生成装置の構成
まず、識別モデル生成装置２０について説明する。なお、以下の実施形態では、ホットスポットの有無が未知のレイアウトパターンを「未知パターン」、ホットスポットに係る情報が付与されている、すなわち、ホットスポットの有無が既知のレイアウトパターンを「既知パターン」と表記する場合がある。既知パターン（第１配線パターン）に関するデータは、後述するごとく、既知パターンデータ４０として記憶部３０に蓄積される。未知パターン（第２配線パターン）は、「複数の配線パターン」の一例である。
【００７９】
識別モデル生成装置２０は、例えば、パーソナルコンピュータやサーバコンピュータ等のコンピュータなどである。識別モデル生成装置２０は、１台のコンピュータとして実装してもよく、また、複数台のコンピュータによるクラウドとして実装することもできる。なお、本実施形態では、識別モデル生成装置２０を１台のコンピュータとした場合を例として説明する。識別モデル生成装置２０は、ＣＡＤ（Computer Aided Design）装置などの設計者による集積回路の設計を支援する回路設計ソフトウェアが動作する設計装置であってもよい。図１４に示すように、識別モデル生成装置２０は、記憶部３０と、処理部３１とを有する。なお、図示しないが、識別モデル生成装置２０は、入力部、表示部および通信Ｉ／Ｆ（インタフェース）を有してもよい。
【００８０】
記憶部３０は、ハードディスク、ＳＳＤ（Solid State Drive）、ＳＣＭ（Storage Class Memory）、光ディスクなどの記憶装置である。なお、記憶部３０は、ＲＡＭ（Random Access Memory）、フラッシュメモリ、ＮＶＳＲＡＭ（Non Volatile Static Random Access Memory）等のデータを書き換え可能な半導体メモリであってもよい。
【００８１】
記憶部３０は、処理部３１で実行されるＯＳ（Operating System）や各種プログラムを記憶する。例えば、記憶部３０は、識別モデル生成に用いる各種のプログラムを記憶する。さらに、記憶部３０は、処理部３１で実行されるプログラムで用いられる各種データを記憶する。例えば、記憶部３０は、既知パターンデータ４０と、ビットデータ４１と、隣接情報考慮ラベル・エッジ重み付きグラフ４２と、エラー識別モデル情報４３とを記憶する。
【００８２】
既知パターンデータ４０は、既知パターン集合であるレイアウトパターン群Ｓに関する一連の情報を記憶したデータである。そして、本実施形態において、識別モデル生成装置２０は、レイアウトパターン群Ｓとして既知パターン集合ｓ１，・・・，ｓＮの入力を受け付けたものとして説明する。既知パターン集合ｓ１，・・・，ｓＮは、識別モデルの生成対象として入力されるものである。
【００８３】
既知パターンデータ４０は、既知パターン集合ｓ１，・・・，ｓＮにおいて、各既知パターンｓiを構成する矩形や多角形の頂点座標リストを含む。例えば、各既知パターンｓｉ（ｉ＝１，・・・，Ｎ）を構成する矩形や多角形の集合を、ｓｉ：｛ｐi1，ｐi2，・・・，ｐik，ｐim｝と表すことができる。また、多角形ｐikの頂点座標を、ｐik=｛（ｘik1，ｙik1），・・・，（ｘikn，ｙikn）｝と表すことができる（図１９等参照）。
【００８４】
図１５は、既知パターンデータ４０に含まれる既知パターンの一例を示す図である。図１５に示す例では、既知パターン毎に、既知パターンを構成する各構成部品の頂点座標リストが記録されている。頂点座標リストには、構成部品を示す図形のそれぞれの頂点座標が１行毎に記録されている。図１５に示す例では、既知パターンPATTERN1の頂点座標リストとして、矩形RECT1の４つの頂点座標や、多角形POLY2の７つの頂点座標が示されている。頂点座標リストとしては、ＧＤＳ（Graphic Data System）、ＯＡＳＩＳ（Open Artwork System Interchange Standard）等の既存の図形データフォーマットを利用してもよい。なお、既知パターンの中心位置は、ホットスポットの発生位置に対応する。また、各既知パターンは、同一または略同一のサイズおよび形状を有する局所的パターンである。
【００８５】
また、既知パターンデータ４０には、各既知パターンにおけるホットスポット発生の有無に関する情報（以下では「エラー有無情報」と表記する場合がある）も含まれる。例えば、既知パターンデータ４０には、既知パターン集合ｓ１，・・・，ｓｎに対応付けられたエラー有無情報も含まれる。各既知パターンｓｉのエラー有無情報ｈｉが既知パターンｓｉに対応付けられる（図１９等参照）。例えば、既知パターンｓｉでホットスポットが発生している場合（エラー有り）、エラー有無情報ｈｉに“１”を設定する一方、既知パターンｓｉでホットスポットが発生していない場合（エラー無し）、エラー有無情報ｈｉに“０”を設定することが考えられる。なお、エラー有無情報Ｈは、Ｈ＝{ｈ１，ｈ２，・・・，ｈＮ；ｈｉ＝{0, 1}}として定義され、上述した頂点座標等とともに入力される。
【００８６】
ビットデータ４１は、後述するノードラベル生成部５２ａがノードそれぞれについて、自ノードの相対的位置関係に関する属性（例えば電気的特性）をビット列で表現したラベルを生成する際に用いるデータである。すなわち、ビットデータ４１は、ラベル生成のためのルールを記憶したデータといえ、例えば、相対的位置関係に関する属性毎に所定のビット列（例えば２ビット）が対応付けられている。
【００８７】
後述するが、ノードラベル生成部５２ａは、自ノードの相対的位置関係に関する属性に基づくラベルを生成する。その際、ノードラベル生成部５２ａは、かかるビットデータ４１を用いる。具体的には、ノードラベル生成部５２ａは、まず、自ノードの相対的位置関係に関する属性を特定する。そして、ノードラベル生成部５２ａは、特定した属性に対応するビット列をビットデータ４１から読み出すことにより、ビット列で表現したラベルを生成し、生成したラベルを既知パターンデータ４０として各既知パターンに対応付けて格納する。なお、自ノードとは、ラベル生成対象または以下に示す隣接情報付与対象となっているノードを示す。
【００８８】
隣接情報考慮ラベル・エッジ重み付きグラフ４２は、後述するグラフ生成部５２（ノードラベル生成部５２ａ、隣接情報付与部５２ｂおよびエッジ重み付与部５２ｃ）によって生成される。隣接情報考慮ラベル・エッジ重み付きグラフは、以下、単に「グラフ」という場合がある。
【００８９】
グラフ４２には、ドロネー三角網生成部５１により各既知パターンから生成されたドロネー三角網に基づくグラフ情報（グラフ群Ｇ）も含まれる。さらに、グラフ４２には、かかるグラフ４２の各ノードを識別するためのラベル（ノードラベル）であって、各ノードの相対的位置関係に関する属性と各ノードに隣接するノード（隣接ノード）の属性である隣接情報とを考慮したラベルや、後述するエッジの重みに関する情報も含まれる。レイアウトパターンや、当該レイアウトパターンから生成されるドロネー三角網は一種のグラフと捉えることができ、そのようなグラフにおける三角形の中心（重心）はノードと呼ばれる。
【００９０】
ノードラベルは、後述するノードラベル生成部５２ａにより基盤が生成され、隣接情報付与部５２ｂによりさらに処理が加えられることで生成される。また、本実施形態では、後述するエッジ重み付与部５２ｃにより、ノード毎に、当該ノードと、当該ノードに隣接する最大３個の隣接ノードとの距離が計算され、計算された距離に対応する値が、当該ノードに接続する最大３本のエッジに、重みとして対応付けられる。これにより、隣接情報考慮ラベル付きグラフから、隣接情報考慮ラベルとエッジの重みとの両方を付与されたグラフ４２が生成される。隣接情報考慮ラベル付きグラフは、複数の隣接情報考慮ラベルの各要素や、記憶部３０に蓄積された既知パターンに係るノードベクトル情報に基づき、隣接情報考慮ラベルから抽出されてもよい。隣接情報考慮ラベルは、「複数のノードベクトル」の一例であり、隣接情報考慮ラベル付きグラフは、「候補ノードベクトル群」の一例である。また、既知パターンから生成された各グラフｇ’ｉに付与される隣接情報考慮ラベルは、「記憶部に蓄積された、ホットスポットに対応したノードベクトルに関するノードベクトル情報」の一例である。
【００９１】
例えば、グラフ群Ｇは、既知パターン集合ｓ１，・・・，ｓＮから生成されたドロネー三角網に基づくグラフｇ１，・・・，ｇＮを含む。つまり、グラフ群Ｇは、Ｇ＝｛ｇ１，・・・，ｇＮ｝として定義される。このとき、各グラフｇｉは、各グラフｇｉ＝（Ｖｉ，Ｅｉ）（ｉ＝１，・・・，Ｎ）のように形式的に定義することができる。Ｖｉは、ノード集合であり、Ｖｉ＝{ｖi1，ｖi2，・・・，ｖis；ｖik＝{(ｘik，ｙik)，fik}}と表すことができる。例えば、ノードｖikは、座標（ｘik，ｙik）に位置することを示す。fikは、ノードｖikの相対的位置関係に関する属性である。Ｅｉは、エッジ集合（枝集合）であり、Ｅｉ＝｛ｅi1，ｅi2，・・・，ｅit；ｅik＝（ｖik1，ｖik2）｝と表すことができる。つまり、各エッジ（枝）ｅikは、２つのノードｖik1とｖik2との間の無向エッジであることを示す。
【００９２】
また、ドロネー三角網に基づくグラフｇ１，・・・，ｇＮの各ノードｖikに対し、ノードｖikの相対的位置関係に関する属性fikと隣接情報とに基づいて生成された隣接情報考慮ラベルを付与された各グラフｇｉは、ｇ’ｉ＝（Ｖ’ｉ，Ｅ’ｉ，ｌ）のように形式的に定義することができる。ｇ’ｉ、Ｖ’ｉおよびＥ’ｉは、それぞれ、上述したｇｉ、ＶｉおよびＥｉと同様であるが、各グラフｇｉに上記隣接情報考慮ラベルを付与されている点でｇｉ、ＶｉおよびＥｉと異なっている。また、グラフ群Ｇ’は、Ｇ’＝{ｇ’１，・・・，ｇ’Ｎ}と定義される。ｌは、各ノードラベル情報を示し、ｌ：｛ｌ１，ｌ２，・・・，ｌｎ；ｌｉ∈Σ，Σ＝{0, 1}ｑ｝と表すことができる。つまり、ノードラベルｌは、ｌ１からｌｎまでの要素を含み、長さｑのビット列で表現されることを示す。
【００９３】
さらに、ドロネー三角網に基づくグラフｇ’１，・・・，ｇ’Ｎの各ノードｖ’ikについて、隣接ノードとの距離ｄik0，ｄik1，ｄik2が、各ノードｖ’ikの最大３本のエッジの重みｗik＝{ｄik0，ｄik1，ｄik2}として計算される。このような重みｗik＝{ｄik0，ｄik1，ｄik2}が、隣接情報考慮ラベル付きグラフｇ’ｉにおける各ノードｖ’ikのエッジに対応付けられる。このように隣接情報考慮ラベル付きグラフｇ’ｉに対しエッジの重みｗikを付与することで、隣接情報考慮ラベル・エッジ重み付きグラフ４２（グラフ群Ｇ’）が生成され記憶部３０に保存される。
【００９４】
エラー識別モデル情報４３は、ホットスポットの検証に用いるエラー識別モデルを記憶したデータである。エラー識別モデル情報４３は、後述する識別モデル生成部５３により生成され、後述する(5)式によって表現される。例えば、エラー識別モデル情報４３は、下記(4)または(5)式に示される重み係数αｉの値として格納される。
【００９５】
処理部３１は、識別モデル生成装置２０を制御するデバイスである。処理部３１としては、ＣＰＵ（Central Processing Unit）、ＭＰＵ（Micro Processing Unit）等の電子回路や、ＡＳＩＣ（Application Specific Integrated Circuit）、ＦＰＧＡ（Field Programmable Gate Array）等の集積回路を採用できる。処理部３１は、各種の処理手順を規定したプログラムや処理データを格納するための内部メモリを有し、これらによって種々の処理を実行する。処理部３１は、各種のプログラムを実行することにより、後述する各種機能を果たす。例えば、本実施形態において、処理部３１は、受付部５０、ドロネー三角網生成部５１、グラフ生成部５２、および識別モデル生成部５３としての機能を果たす。
【００９６】
受付部５０は、各種の受付を行なう。例えば、受付部５０は、図示しない所定の入力部を介して入力される、既知パターン集合や、各既知パターンにおけるエラー有無情報ｈｉを受け付ける。そして、受付部５０は、受け付けた既知パターン集合やエラー有無情報ｈｉを、既知パターンデータ４０として記憶部３０に格納する。なお、受付部５０は、処理部７４に付設された入力部７０を介して各種の受付を行なうように構成されてもよい。
【００９７】
ドロネー三角網生成部５１は、レイアウトパターン（配線パターン）ｓｉを構成する図形の頂点を結んでドロネー三角分割（Delaunay triangulation）を行なって、図形の頂点を結んで得られる複数の三角形（三角網）を求める。このような三角網は、ドロネー三角網と呼ばれる。ドロネー三角網生成部５１は、例えば、既知パターン集合ｓ１，・・・，ｓＮからそれぞれ生成した、ドロネー三角網に基づくグラフｇ１，・・・，ｇＮに関する情報（座標等）を、グラフ４２として、既知パターン集合ｓ１，・・・，ｓＮのそれぞれに対応付けて格納する。
【００９８】
図１６（Ａ）〜図１６（Ｃ）は、ドロネー三角分割の流れを説明する図である。図１６（Ａ）は、レイアウトパターン群Ｓに含まれる配線パターンの一例を示す。図１６（Ｂ）は、図１６（Ａ）に示す配線パターンに対し生成されるボロノイ図（Voronoi diagram）を示す。図１６（Ｃ）は、図１６（Ａ）に示す配線パターンもしくは図１６（Ｂ）に示すボロノイ図に対し生成されるドロネー図（Delaunay diagram）を示す。図１６（Ａ）〜図１６（Ｃ）において、網掛け部分は、レイアウトパターンにを含まれる配線パターンを示す。
【００９９】
ドロネー三角網生成部５１は、図１６（Ａ）に示すレイアウトパターンの配線部分の頂点座標を求め、求められた頂点座標から図１６（Ｂ）に示すボロノイ図を生成する。ボロノイ図は、平面または空間上の点集合の各点について、どの点に最も近いかによって分割して生成される図である。そして、ドロネー三角網生成部５１は、図１６（Ｂ）に示すボロノイ図から、隣接する領域の母点（generatrix）どうしを結ぶことにより、図１６（Ｃ）に示すドロネー図を生成する。このドロネー図は各図形間の相対位置関係を表現する。レイアウトパターンやドロネー三角網は、各三角形の中心であるノード間をつなぐエッジにより構成されるため、一種のグラフと捉えることができる。
【０１００】
グラフ生成部５２は、既知パターンに含まれるノード毎に、自ノードの相対的位置関係に関する属性と、自ノードに隣接する隣接ノードとの属性情報である隣接情報とに基づいたラベルを生成する。また、グラフ生成部５２は、自ノードと隣接ノードとの距離を、エッジの重みとして計算する。このため、図１４に示すように、グラフ生成部５２は、ノードラベル生成部５２ａ、隣接情報付与部５２ｂおよびエッジ重み付与部５２ｃを有する。ここで、相対的位置関係に関する属性は、例えば電気的特性である。グラフ生成部５２の動作については、図１９を参照しながら後述する。
【０１０１】
まず、ノードラベル生成部５２ａについて説明する。ノードラベル生成部５２ａは、既知パターンｓｉに含まれるノードｖik毎に、自ノードｖikの相対的位置関係に関する属性に基づく基盤となるラベルを生成する。具体的に、ノードラベル生成部５２ａは、既知パターンｓｉから生成されたドロネー三角網のノードｖik毎に、自ノードｖikの相対的位置関係に関する属性を所定長のビット列で表現したラベルを生成する。例えば、ノードラベル生成部５２ａは、ビットデータ４１を参照し、ドロネー三角網の各三角形に対応するノードｖik毎に、自ノードｖikの相対的位置関係に関する属性を２ビットのビット列で表現したラベルを生成する。そして、ノードラベル生成部５２ａは、生成したノードラベル（２ビットのビット列；ノードラベル情報ｌｉ）を、グラフｇｉ（ｇ’ｉ）に対応付けて格納する。ノードラベル生成部５２ａの動作については、図２０を参照しながら後述する。
【０１０２】
ついで、隣接情報付与部５２ｂについて説明する。隣接情報付与部５２ｂは、ノードラベル生成部５２ａにより自ノードの相対的位置関係に関する属性に基づき生成されたノードラベル毎に、さらに隣接情報を付与する。隣接情報は、自ノードに隣接する隣接ノードとの属性情報が表現された所定長のビット列である。具体的に、隣接情報付与部５２ｂは、自ノードの属性が表現された２ビットのビット列と、隣接ノードとの属性情報が表現された２ビットのビット列とを重なりなく結合することで、属性に基づく基盤ラベルにさらに隣接情報を付与したノードラベルを生成する。そして、隣接情報付与部５２ｂは、生成したノードラベル（４ビットのビット列；ノードラベル情報ｌｉ）を、グラフｇｉ（ｇ’ｉ）に対応付けて格納する。隣接情報付与部５２ｂの動作については、図２１を参照しながら後述する。
【０１０３】
上述のような隣接情報の生成および付与について、図１７および図１８を参照しながら説明する。なお、図１７は、自ノードと隣接ノードとの接続関係を示す図である。また、図１８は、自ノードラベルに接続情報を付与する手法を説明する図である。
【０１０４】
図１７に示すグラフｇ１は、既知パターンｓｉから生成されたドロネー三角網に基づくグラフである。自ノードをｖ０として、自ノードｖ０における属性に基づき生成されたノードラベルに隣接情報を付与する例について、以下で説明する。
【０１０５】
図１７より、自ノードｖ０と隣接する隣接ノードは、ノードｖ１、ｖ２、ｖ３およびｖ４である。ここで、図１８のＦ１に着目すると、自ノードｖ０と隣接するノードのラベルである隣接ノードラベルＬ（ｖ１）〜Ｌ（ｖ４）の長さは「ｒ」として示される。また、自ノードラベルＬ（ｖ０）の長さは「ｐ」として示される。ノードラベルの長さは、ビット数を示すが、ここでは概念的な記号で示すことにする。隣接情報付与部５２ｂは、自ノードラベルと隣接ノードラベルとの排他的論理和（ＸＯＲ）により、隣接ハッシュラベルを求める。算出された隣接ハッシュラベルは、自ノードラベルを左詰めとして隣接ノードラベルが重なりなく付与されるため、その長さは「ｒ＋ｐ」で示される。しかし、単に、自ノードラベルと隣接ノードラベルとのＸＯＲを算出してもこのような重なりのない構造のビット列のラベル（本実施形態では「ビットラベル」と表記する場合がある）は得られない。そこで、図１８のＦ２を参照して、隣接情報付与部５２ｂによるさらに具体的な処理について説明する。
【０１０６】
まず、隣接情報付与部５２ｂは、隣接ノードラベルＬ（ｖ１）〜Ｌ（ｖ４）の全てについてのＸＯＲとして得られるビットラベルを、隣接ノードハッシュラベルＮとして算出する（ステップＳ１）。また、隣接情報付与部５２ｂは、自ノードラベルＬ（ｖ０）を左詰めしたビットラベルＬ（ｖ０）’を算出する（ステップＳ２）。左詰めするとは、ＨＴＭＬタグとして「LEFTALIGN」を入力することに相当する。例えば、隣接情報付与部５２ｂは、２ビットのビット列「１０」で示される自ノードラベルＬ（ｖ０）を、５ビットのビット列に左詰めしたビットラベルとして算出する場合には、７ビットのビット列「０００００」を用いて、かかるビット列に対し「１０」を左詰めした「１００００」を、ビットラベルＬ（ｖ０）’として算出することになる。
【０１０７】
次に、隣接情報付与部５２ｂは、隣接ノードハッシュラベルＮと左詰めしたビットラベルＬ（ｖ０）’とのＸＯＲを算出する（ステップＳ３）。これにより、隣接情報付与部５２ｂは、自ノードラベルＬ（ｖ０）において隣接情報をハッシュして付与したラベルである隣接情報考慮ハッシュラベルＮ（ｖ０）を算出する。このような算出処理は、下記(2)式によって示される。
【０１０８】
Ｎ(v0)＝ＸＯＲ(ＸＯＲ(Ｌ(v1), Ｌ(v2), Ｌ(v3), Ｌ(v4)), LEFTALIGN L(vo))    (2)
【０１０９】
そして、隣接情報付与部５２ｂは、隣接情報を付与したラベル情報を、グラフｇｉに対応付けて格納する。また、隣接情報付与部５２ｂは、このような隣接情報付与処理は、記憶されている全ての既知パターンにおける全てのノードラベルについて行なわれる。隣接情報付与部５２ｂにより隣接情報が付与されたノードラベルを有するグラフｇｉは、「隣接情報考慮ラベル付きグラフ」（ｇ’i）と表記される場合がある。
【０１１０】
このように、隣接情報付与部５２ｂは、自ノードに対して隣接する全ての隣接ノードのラベルについてのＸＯＲ演算を行なう。そして、隣接情報付与部５２ｂは、かかるＸＯＲ演算によって得られたビットラベル（隣接ノードハッシュラベル）と、自ノードラベルを左詰めした新たなビットラベルとについてのＸＯＲ演算を行なう。これにより、隣接情報付与部５２ｂは、自ノードラベルにおける隣接情報考慮ハッシュラベルを算出する。すなわち、隣接情報付与部５２ｂは、自ノードラベルを示すビット列に対し、隣接ノードラベルのハッシュ値であるビット列を隣接情報として付与する。これにより、隣接情報付与部５２ｂは、ビットラベルが一致することによるハッシュ衝突を回避することができる。
【０１１１】
なお、隣接情報付与部５２ｂは、隣接情報を付与した自ノードのラベルに対し、さらにかかる自ノードの近傍に位置するノードのラベル情報である近傍ノードラベルを付与してもよい。図１７の例では、自ノードｖ０に対し、ノードｖ５、ｖ６、ｖ７およびｖ８は、隣接していないが近傍に存在している近傍ノードといえる。隣接情報付与部５２ｂは、上記のように算出した隣接情報考慮ハッシュラベルＮ（ｖ０）に対し、さらに近傍ノードラベルＬ（ｖ５）〜Ｌ（ｖ８）についてのＸＯＲ演算を行なって得られるハッシュ値を近傍情報として付与してもよい。
【０１１２】
そして、隣接情報付与部５２ｂは、かかる処理を所定回数繰り返してよい。例えば、自ノードｖ０からエッジを１ステップ進めたノードが隣接ノードｖ１〜ｖ４である。また、自ノードｖ０から隣接ノードｖ１〜ｖ４を経由してエッジを２ステップ進めたノードが近傍ノードｖ５〜ｖ８である。例えば、予測装置１０に繰り返し回数「１」が設定されている場合、隣接情報付与部５２ｂは、自ノードｖ０からエッジを１ステップ進めたノードである隣接ノードｖ１〜ｖ４に基づく隣接情報を、自ノードラベルＬ（ｖ０）に付与した隣接情報考慮ハッシュラベルＮ（ｖ０）を算出する。また、予測装置１０に繰り返し回数「２」が設定されている場合、隣接情報付与部５２ｂは、まず、自ノードラベルＬ（ｖ０）に隣接情報を付与した隣接情報考慮ハッシュラベルＮ（ｖ０）を算出する。次に、隣接情報付与部５２ｂは、自ノードｖ０からエッジを２ステップ進めたノードである近傍ノードのラベルＬ（ｖ５）〜Ｌ（ｖ８）についてのＸＯＲ演算を行なって得られるハッシュ値を、近傍情報として、隣接情報考慮ハッシュラベルＮ（ｖ０）とのＸＯＲ演算により付与する。
【０１１３】
ついで、エッジ重み付与部５２ｃについて説明する。エッジ重み付与部５２ｃは、自ノードと隣接ノードとの距離をエッジの重みとして計算する。エッジ重み付与部５２ｃは、ドロネー三角網に基づく隣接情報考慮ラベル付きの各グラフｇ’ｉにおける各ノードｖ’ikについて、隣接ノードｖ’ik0，ｖ’ik1，ｖ’ik2との距離に対応する値ｄik0，ｄik1，ｄik2を計算する。当該距離に対応する値ｄikm（ｍ＝0, 1, 2）は、例えば、下記(3)式によって計算される。
【０１１４】
ｄikm＝α * sqrt(|ｘ’ik−ｘ’ikm|2 ＋ |ｙ’ik−ｙ’ikm|2)    (3)
ただし、sgrt(Ｘ)はＸの平方根を示す。αは、予め設定される係数値であり、例えば１とする。（ｘ’ik，ｙ’ik）は自ノードｖ’ikの座標であり、（ｘ’ikm，ｙ’ikm）は隣接ノードｖ’ikmの座標である。また、係数値α＝１とした場合、距離に対応する値ｄikmは、ノードｖ’ikと隣接ノードｖ’ikmとの距離そのものである。
【０１１５】
そして、エッジ重み付与部５２ｃは、上述のように算出された、ノードｖ’ikと隣接ノードｖ’ikmとの距離ｄikmを、ノードｖ’ikと隣接ノードｖ’ikmとの間のエッジの重みｗik＝{ｄik0，ｄik1，ｄik2}として付与する。つまり、エッジ重み付与部５２ｃは、重みｗik＝{ｄik0，ｄik1，ｄik2}を、隣接情報考慮ラベル付きグラフｇ’ｉにおける各ノードｖ’ikの最大３本のエッジに対応付ける。これにより、エッジ重み付与部５２ｃは、隣接情報考慮ラベル・エッジ重み付きグラフ４２（グラフ群Ｇ’）を生成し記憶部３０に格納する。エッジ重み付与部５２ｃの動作については、図２２を参照しながら後述する。
【０１１６】
識別モデル生成部５３は、ホットスポットの有無が未知のレイアウトパターンにおいてホットスポットを検証するエラー識別モデルを生成する。例えば、識別モデル生成部５３は、既知パターンについてのレイアウトパターン群Ｓ＝｛ｓ１，・・・，ｓＮ｝およびエラー有無情報Ｈ＝｛ｈ１，・・・，ｈＮ｝を入力される。また、識別モデル生成部５３は、グラフ生成部５２で生成された隣接情報考慮ラベル・エッジ重み付きグラフ４２（グラフ群Ｇ’）を入力される。
【０１１７】
そして、識別モデル生成部５３は、グラフ生成部５２からのグラフ群Ｇ’と、各グラフｇ’ｉに対応するエラー有無情報ｈｉとから、下記(4)式を満たす係数値αｉを求める。このとき、サポートベクタマシンなどの既知手法が用いられる。下記(4)式におけるＫ（ｇ’ｉ，ｇ’ｊ）は、既知パターンどうしであるグラフｇ’ｉとグラフｇ’ｊとの類似度（距離評価値）である。本実施形態において、当該類似度Ｋ（ｇ’ｉ，ｇ’ｊ）は、例えば、上記(1)式および図１３に示す類似度計算アルゴリズムに基づく処理を行なうことで、つまり図２４を参照しながら後述する手順で計算される。これにより、エラー識別モデル情報４３は、下記(5)式で表現される。識別モデル生成部５３の動作については、図２３および図２４を参照しながら後述する。
【０１１８】
【数２】
2018165887.tif 000004
【０１１９】
【数３】
2018165887.tif 000005
【０１２０】
ただし、上記(4), (5)式において、sign(Ｘ)は、符号関数であり、Ｘ＞０のときsign(Ｘ)＝１、Ｘ＝０のときsign(Ｘ)＝０、Ｘ＜０のときsign(Ｘ)＝−１となる関数である。
【０１２１】
〔３−２〕本実施形態の予測部の構成
図１４に戻り、予測部６０について説明する。予測部６０は、未知パターン（第２配線パターン）よりグラフ群Ｇ”を生成する。このとき、予測部６０は、グラフ群Ｇ”の各グラフｇ”ｉに、グラフ群Ｇ’と同様の隣接情報考慮ラベル（ノードベクトル）とエッジの重みを付与する。なお、識別モデル生成装置２０で既知パターン（第１配線パターン）から生成されたグラフ群Ｇ’の各グラフｇ’ｉには、上述した隣接情報考慮ラベル（ノードベクトル）とエッジの重みが付与されている。
【０１２２】
そして、予測部６０は、グラフ群Ｇ’（既知パターン）とグラフ群Ｇ”（未知パターン）との類似度（距離評価値）を、各グラフに付与された隣接情報考慮ラベルとエッジの重みに基づき算出する。さらに、予測部６０は、類似度に基づき、複数の既知パターン（第１配線パターン）より、特定配線パターン群を抽出する。特定配線パターン群としては、例えば、類似度の高い上位ｒ個の配線パターンが抽出される。類似度は、「複数の距離評価値」の一例である。このとき、候補ノードベクトル群（隣接情報考慮ラベル付きグラフ）に含まれるノードベクトルのそれぞれについて、当該ノードベクトルに対応するドロネー三角網を参照し、当該ノードベクトルが参照するノードと隣接ノードとの距離に関する複数の距離評価値（類似度）を算出することができる。また、複数の距離評価値に基づき、上記候補ノードベクトル群から、ホットスポット候補となる、特定配線パターン群に対応する特定配線ノードベクトル群を抽出することができる。その際、特定配線パターン群もしくは特定配線ノードベクトル群に属する、類似度の高いパターンが列挙される（図２７参照）。
【０１２３】
また、予測部６０は、抽出した特定配線パターン群に基づいて、未知パターンにおけるホットスポット発生箇所の候補を特定する。ここで、予測部６０は、例えば、特定配線パターン群のうち、エラー識別モデルを用いてホットスポット（エラー）が有ると識別された配線パターンに基づいて、未知パターンにおけるホットスポット発生箇所の候補を特定する。これにより、予測部６０は、実際にホットスポット発生箇所の予測を行なう。このとき、上記特定配線ノードベクトル群に基づき、露光パターンにおけるホットスポットの発生箇所の候補を特定することができる。その際、ホットスポットが有ると判定されたノードベクトル群（配線パターン群）に対応するドロネー三角網が特定される。
【０１２４】
このように、予測部６０は、識別モデル生成装置２０により生成される、既知パターンの類似度Ｋ（ｇ’ｉ，ｇ’ｊ）に基づくエラー識別モデルを用いて、未知パターンにおけるホットスポットを検証する。例えば、予測部６０は、かかるエラー識別モデルを用いて、未知パターンにおけるホットスポットの有無を識別する。以下では、予測部６０のホットスポット検証に関する一連の処理について説明する。
【０１２５】
なお、上述した識別モデル生成装置２０は、既知パターンの集合を受け付け、各既知パターンに対応するドロネー三角網それぞれのノードにおいて、相対的位置関係に関する属性および隣接情報に基づくラベルを生成し各グラフｇｉに付与する。さらに、識別モデル生成装置２０は、自ノードと隣接ノードとの距離をエッジの重みとして計算し、計算したエッジの重みを、隣接情報考慮ラベル付きの各グラフｇ’ｉに付与する。生成したノードラベルおよびエッジの重みを用いて算出した各既知パターンどうしの類似度に基づいて識別モデルを生成する。
【０１２６】
これに対し、予測部６０は、予測対象である未知パターンを受け付け、受け付けた未知パターンに対応するドロネー三角網において、ノードの相対的位置関係に関する属性および隣接情報に基づくラベルを生成し各グラフに付与する。また、予測部６０は、ドロネー三角網において、自ノードと隣接ノードとの距離をエッジの重みとして計算し、計算したエッジの重みを、隣接情報考慮ラベル付きの各グラフに付与する。そして、予測部６０は、ノードラベルおよびエッジの重みを用いて、既知パターンとの類似度算出や、ホットスポットの有無に関する検証を行なう。
【０１２７】
このため、予測部６０の多くの構成要素は、識別モデル生成装置２０の構成要素と同様の処理を行なう。以下において、同様の処理を行なう構成要素についての詳細な説明は省略する。
【０１２８】
予測部６０は、例えば、パーソナルコンピュータやサーバコンピュータ等のコンピュータなどである。予測部６０は、１台のコンピュータとして実装してもよく、また、複数台のコンピュータによるクラウドとして実装することもできる。なお、本実施形態では、予測部６０を１台のコンピュータとした場合を例として説明する。予測部６０は、ＣＡＤ装置などの設計者による集積回路の設計を支援する回路設計ソフトウェアが動作する設計装置であってもよい。図１４に示すように、予測部６０は、入力部７０と、表示部７１と、通信Ｉ／Ｆ（インタフェース）部７２と、記憶部７３と、処理部７４とを有する。
【０１２９】
入力部７０は、各種の情報を入力する入力デバイスである。入力部７０としては、マウスやキーボード等の操作の入力を受け付ける入力デバイスが挙げられる。入力部７０は、各種の入力を受け付ける。例えば、入力部７０は、未知パターンおけるホットスポットの有無判定に関する各種の入力を受け付ける。入力部７０は、ユーザからの操作入力を受け付け、受け付けた操作内容を示す操作情報を処理部７４に入力する。
【０１３０】
表示部７１は、各種情報を表示する表示デバイスである。表示部７１としては、ＬＣＤ（Liquid Crystal Display）やＣＲＴ（Cathode Ray Tube）等の表示デバイスが挙げられる。表示部７１は、各種情報を表示する。例えば、表示部７１は、登録画面、操作画面、類似度評価結果（図１４の符号８２や図２７参照）、エラー判定結果（図１４の符号８３参照）など各種の画面を表示する。
【０１３１】
通信Ｉ／Ｆ部７２は、他の装置との間で通信制御を行なうインタフェースである。通信Ｉ／Ｆ部７２は、不図示のネットワークを介して他の装置と各種情報を送受信する。例えば、通信Ｉ／Ｆ部７２としては、ＬＡＮ（Local Area Network）カードなどのネットワークインタフェースカードを採用できる。
【０１３２】
記憶部７３は、ハードディスク、ＳＳＤ、ＳＣＭ、光ディスクなどの記憶装置である。なお、記憶部７３は、ＲＡＭ、フラッシュメモリ、ＮＶＳＲＡＭ等のデータを書き換え可能な半導体メモリであってもよい。
【０１３３】
記憶部７３は、処理部７４で実行されるＯＳや各種プログラムを記憶する。例えば、記憶部７３は、後述するホットスポットの検証や発生箇所の候補特定に用いる各種のプログラムを記憶する。さらに、記憶部７３は、処理部７４で実行されるプログラムで用いられる各種データを記憶する。例えば、記憶部７３は、未知パターンデータ８０と、ビットデータ８１と、類似度評価結果８２と、エラー判定結果８３とを記憶する。
【０１３４】
未知パターンデータ８０は、例えば、一以上の未知パターンｓｕに関する情報を記憶したデータである。ここでは、未知パターンｓｕの数は１とする。未知パターンｓｕは、ホットスポット発生箇所の予測対象として入力部７０を介して入力される。未知パターンデータ８０は、未知パターンｓｕを構成する矩形や多角形の頂点座標リストを含む。例えば、未知パターンｓｕを構成する矩形や多角形の集合を、ｓｕ：｛ｐ１，ｐ２，・・・，ｐｋ，ｐＭ｝と表すことができる。また、多角形ｐｋの頂点座標を、ｐｋ＝｛（ｘk1，ｙk1），・・・，（ｘkn，ｙkn）｝と表すことができる。ここで、図１５は、既知パターンデータ４０に含まれる既知パターンの一例を示す図であるが、未知パターンにも対応するものである。
【０１３５】
また、未知パターンデータ８０には、ドロネー三角網生成部９１により未知パターンｓｕから生成されたドロネー三角網のグラフ情報も含まれる。さらに、未知パターンデー
タ８０には、かかるグラフの各ノード毎に生成された、相対的位置関係に関する属性および隣接情報５基づくラベル（ノードベクトル）も含まれる。
【０１３６】
例えば、未知パターンｓｕから生成されたドロネー三角網に基づくグラフＧｕにおいて、Ｇｕ＝（Ｖ，Ｅ）のように形式的に定義することができる。Ｖは、ノード集合であり、Ｖ：｛ｖ１，ｖ２，・・・，ｖｎ；ｖｉ＝{(ｘｉ，ｙｉ)，ｆｉ｝と表すことができる。ここで、各ノードｖｉは、座標（ｘｉ，ｙｉ）に位置することを示す。fiは、ノードｖiの相対的位置関係に関する属性である。Ｅは、エッジ集合（枝集合）であり、Ｅ＝｛ｅ１，ｅ２，・・・，ｅｍ；ｅｊ＝（ｖj1，ｖj2）｝と表すことができる。つまり、各エッジ（各枝）ｅｊは、二つのノードｖj1とｖj2との間の無向エッジであることを示す。
【０１３７】
また、ドロネー三角網に基づくグラフＧｕの各ノードｖiに対し、当該ノードｖiの相対的位置関係に関する属性ｆｉと隣接情報とに基づいて生成された隣接情報考慮ラベルを付与されたグラフＧｕは、Ｇｕ＝（Ｖ，Ｅ，ｌ）のように形式的に定義することができる。ＶおよびＥは、上記の通りである。ｌは、各ノードラベル情報を示し、ｌ：｛ｌ１，ｌ２，・・・，ｌｎ；ｌｉ∈Σ，Σ＝{0, 1}ｑ｝と表すことができる。つまり、ノードラベルｌは、ｌ１からｌｎまでの要素を含み、長さｑのビット列で表現されることを示す。すなわち、未知パターンデータ８０は、未知パターンｓｕについて、ドロネー三角網に基づくグラフＧｕに関する情報を記憶したデータである。
【０１３８】
さらに、ドロネー三角網に基づくグラフＧｕの各ノードｖiについて、隣接ノードとの距離ｄi0，ｄi1，ｄi2が、各ノードｖiの最大３本のエッジの重みｗi＝{ｄi0，ｄi1，ｄi2}として計算される。このような重みｗi＝{ｄi0，ｄi1，ｄi2}が、隣接情報考慮ラベル付きグラフＧｕにおける各ノードｖiのエッジに対応付けられる。このように隣接情報考慮ラベル付きグラフＧｕに対しエッジの重みｗiを付与することで、隣接情報考慮ラベル・エッジ重み付きグラフＧ”が生成される。生成されたグラフＧ”は、記憶部７３において、例えば、未知パターンデータ８０として保存される。
【０１３９】
ビットデータ８１は、後述するノードラベル生成部９２ａがノードそれぞれについて、自ノードの相対的位置関係に関する属性（例えば電気的特性）をビット列で表現したラベルを生成する際に用いるデータである。すなわち、ビットデータ８１は、ラベル生成のためのルールを記憶したデータといえ、例えば、相対的位置関係に関する属性毎に所定のビット列（例えば２ビット）が対応付けられている。
【０１４０】
類似度評価結果８２は、例えば、後述する類似度評価部９３によって得られる、未知パターンと既知パターンとの類似度を、パターンの組み合わせに対応付けて記憶するデータである。類似度評価結果８２には、特定配線パターン群に属する、類似度の高い上位ｒ個の配線パターンに関する情報が含まれてもよい。
【０１４１】
エラー判定結果８３は、エラー識別モデルを用いたエラー識別部９４によるエラー識別の判定結果に関するデータである。例えば、エラー判定結果８３は、特定配線パターンに属するパターンについてのホットスポットの有無に関する情報や、その情報の信頼度といった情報を含む。
【０１４２】
処理部７４は、予測部６０を制御するデバイスである。処理部７４としては、ＣＰＵ、ＭＰＵ等の電子回路や、ＡＳＩＣ、ＦＰＧＡ等の集積回路を採用できる。制御部７４は、各種の処理手順を規定したプログラムや制御データを格納するための内部メモリを有し、これらによって種々の処理を実行する。処理部７４は、各種のプログラムが動作することにより各種機能を果たす。例えば、本実施形態において、処理部７４は、受付部９０、ドロネー三角網生成部９１、グラフ生成部９２、類似度評価部９３、エラー識別部９４、および表示制御部９５としての機能を果たす。
【０１４３】
受付部９０は、各種の受付を行う。例えば、受付部９０は、未知パターンデータ８０として用いる未知パターンの入力を受け付ける。例えば、受付部９０は、図示しない入力画面を表示させ、入力画面から未知パターンデータ８０として用いる未知パターンの入力を受け付ける。入力された未知パターンは、未知パターンデータ８０として記憶部７３に記憶される。
【０１４４】
ドロネー三角網生成部９１は、レイアウトパターン（配線パターン）を構成する図形の頂点を結んでドロネー三角分割を行なって、図形の頂点を結んで得られる複数の三角形（三角網）を求める。即ち、ドロネー三角網生成部９１は、識別モデル生成装置２０のドロネー三角網生成部５１と同様の処理を行なう構成要素であるため詳細な説明は省略する。なお、ドロネー三角網生成部９１は、例えば、未知パターンｓｕから生成したドロネー三角網に基づくグラフＧｕに関する情報（座標等）を、未知パターンデータ８０として、未知パターンｓｕに対応付けて格納する。
【０１４５】
グラフ生成部９２は、未知パターンに含まれるノード毎に、自ノードの相対的位置関係に関する属性と、自ノードに隣接する隣接ノードとの属性情報である隣接情報とに基づいたラベルを生成する。図１４に示すように、グラフ生成部９２は、ノードラベル生成部９２ａ、隣接情報付与部９２ｂおよびエッジ重み付与部９２ｃを有する。グラフ生成部９２の動作は、グラフ生成部５２の動作と同様であり、その動作については、図１９を参照しながら後述する。
【０１４６】
ノードラベル生成部９２ａは、未知パターンｓｕに含まれるノードｖｉ毎に、自ノードｖｉの相対的位置関係に関する属性に基づく基盤となるラベルを生成する。具体的に、ノードラベル生成部９２ａは、未知パターンｓｕから生成されたドロネー三角網のノードｖｉ毎に、自ノードｖｉの相対的位置関係に関する属性を所定長のビット列で表現したラベルを生成する。例えば、ノードラベル生成部９２ａは、ビットデータ８１を参照し、ドロネー三角網生成部９１により未知パターンｓｕから生成されたドロネー三角網に基づくグラフＧｕのノードｖｉ毎に、自ノードｖｉの相対的位置関係に関する属性を２ビットのビット列で表現したラベルを生成する。そして、ノードラベル生成部９２ａは、生成したノードラベル（２ビットのビット列；ノードラベル情報ｌｉ）を、未知パターンデータ８０として、未知パターンｓｕに対応付けて格納する。ノードラベル生成部９２ａの動作は、ノードラベル生成部５２ａの動作と同様であり、その動作については、図２０を参照しながら後述する。
【０１４７】
また、隣接情報付与部９２ｂは、ノードラベル生成部９２ａにより自ノードｖｉの相対的位置関係に関する属性に基づき生成されたノードラベル毎に、さらに隣接情報を付与する。上述したように、隣接情報は、自ノードに隣接する隣接ノードとの属性情報が表現された所定長のビット列である。具体的に、隣接情報付与部９２ｂは、自ノードの属性が表現された２ビットのビット列と、隣接ノードとの属性情報が表現された２ビットのビット列とを重なりなく結合することで、属性に基づく基盤ラベルにさらに隣接情報を付与したノードラベルを生成する（図１７および図１８参照）。例えば、隣接情報付与部９２ｂは、ドロネー三角網に基づくグラフＧｕにおいて、ノードラベル生成部９２ａにより自ノードｖｉの相対的位置関係に関する属性に基づいて生成されたノードラベル毎に、当該ノードラベルと重ならないよう隣接情報を付与する。そして、隣接情報付与部９２ｂは、隣接情報を付与したノードラベル（４ビットのビット列；ノードラベル情報ｌｉ）を、未知パターンデータ８０として、グラフＧｕに対応付けて格納する。隣接情報付与部９２ｂの動作は、隣接情報付与部５２ｂの動作と同様であり、その動作については、図２１を参照しながら後述する。
【０１４８】
さらに、エッジ重み付与部９２ｃは、未知パターンｓｕにおける各ノードｖｉと隣接ノードとの距離をエッジの重みとして計算する。エッジ重み付与部９２ｃは、ドロネー三角網に基づく隣接情報考慮ラベル付きのグラフＧｕについて、隣接ノードｖi0，ｖi1，ｖi2との距離に対応する値ｄi0，ｄi1，ｄi2を計算する。当該距離に対応する値ｄim（ｍ＝0, 1, 2）は、例えば、下記(6)式によって計算される。
【０１４９】
ｄim＝α * sqrt(|ｘi−ｘim|2 ＋ |ｙi−ｙim|2)    (6)
ただし、sgrt(Ｘ)はＸの平方根を示す。αは、予め設定される係数値であり、例えば１とする。（ｘi，ｙi）は自ノードｖ’iの座標であり、（ｘim，ｙim）は隣接ノードｖimの座標である。また、係数値α＝１とした場合、距離に対応する値ｄimは、ノードｖiと隣接ノードｖimとの距離そのものである。
【０１５０】
そして、エッジ重み付与部９２ｃは、上述のように算出された、ノードｖiと隣接ノードｖimとの距離ｄimを、ノードｖiと隣接ノードｖimとの間のエッジの重みｗi＝{ｄi0，ｄi1，ｄi2}として付与する。つまり、エッジ重み付与部９２ｃは、重みｗi＝{ｄi0，ｄi1，ｄi2}を、隣接情報考慮ラベル付きのグラフＧｕにおける各ノードｖiの最大３本のエッジに対応付ける。これにより、エッジ重み付与部９２ｃは、隣接情報考慮ラベル・エッジ重み付きグラフＧｕを生成し、未知パターンデータ８０として、記憶部７３に格納する。エッジ重み付与部９２ｃの動作は、エッジ重み付与部５２ｃの動作と同様であり、その動作については、図２２を参照しながら後述する。
【０１５１】
なお、ここでは、未知パターンｓｕの数が１でドロネー三角網に基づくグラフＧｕの数が１である場合について説明しているが、本手法は、未知パターンｓｕの数が２以上でドロネー三角網に基づくグラフＧｕの数が２以上である場合についても、上述した既知パターンが複数存在する場合と同様に適用される。このとき、例えば、未知パターンｓｕは未知パターン集合ｓ１，・・・，ｓＭとして記載され、グラフＧｕはグラフ群Ｇｕ＝｛ｇ１，・・・，ｇＭ｝として記載される。グラフｇｉ（ｉ＝１，・・・，Ｍ）は、ドロネー三角網生成部９１により未知パターンｓｉから生成されたドロネー三角網に基づくグラフである。また、各グラフｇｉは、各グラフｇｉ＝（Ｖｉ，Ｅｉ）のように形式的に定義することができる。そして、上述のごとくグラフ生成部９２によって隣接情報考慮ラベルおよびエッジ重みを付与されたグラフ群Ｇｕおよびグラフｇｉは、それぞれ、グラフ群Ｇ”およびグラフｇ”ｉとして記載される場合がある（図２５および図２６参照）。
【０１５２】
以上のことから、グラフ生成部５２とグラフ生成部９２とでは処理対象が未知パターンであるか既知パターンであるかの違いだけであり、予測部６０のグラフ生成部９２における構成要素９２ａ〜９２ｃは、それぞれ、識別モデル生成装置２０のグラフ生成部５２における構成要素５２ａ〜５２ｃと同様の処理を行なう構成要素である。よって、詳細な説明は省略する。
【０１５３】
類似度評価部９３は、未知パターンｓｕと既知パターンＳとの類似度Ｋを、パターンの組み合わせに対応付けて評価し、その評価結果を、類似度評価結果８２として記憶部７３に保存する。また、類似度評価部９３は、上述したように、類似度Ｋを、上記(1)式および図１３に示す類似度計算アルゴリズムに基づく処理に従って、各グラフに付与された隣接情報考慮ラベルとエッジの重みに基づき算出する。さらに、類似度評価部９３は、算出された類似度Ｋに基づき、複数の既知パターンより、特定配線パターン群を抽出する。特定配線パターン群としては、上述したように、例えば、類似度の高い上位ｒ個の配線パターンが抽出される。特定配線パターン群は、類似度評価結果８２に含まれていてもよい。類似度評価部９３の動作については、図２４および図２５を参照しながら後述する。
【０１５４】
エラー識別部９４は、類似度評価部９３によって抽出された特定配線パターン群に基づいて、未知パターンｓｕにおけるホットスポット発生箇所の候補を特定する。例えば、エラー識別部９４は、上述したエラー識別モデルを用いてホットスポットが有ると識別された未知パターンｓｕの特定配線パターン群（前記上位ｒ個の配線パターン）に属する配線パターンを、未知パターンｓｕにおけるホットスポット発生箇所の候補として特定する。エラー識別部９４は、その特定結果をエラー判定結果８３として記憶部７３に保存してもよい。なお、エラー識別モデルは、上述したように、識別モデル生成部５３によって生成される、既知パターンの類似度Ｋ（ｇ’ｉ，ｇ’ｊ）に基づくモデルｆ(ｘ)であり、例えば上記(5)式のごとく与えられる。エラー判定結果８３には、特定配線パターンに属するパターンについてのホットスポットの有無に関する情報や、その情報の信頼度といった情報が含まれていてもよい。エラー識別部９４の動作については、図２６を参照しながら後述する。
【０１５５】
表示制御部９５は、表示部７１の表示状態を制御する。例えば、表示制御部９５は、上述した類似度評価結果８２やエラー判定結果８３のほか、予測装置１０による予測処理を行なうために必要な各種情報を、表示部７１に図２７に示すごとく表示させるように、表示部７１の表示状態を制御する。表示制御部９５の動作については、図２７を参照しながら後述する。
【０１５６】
〔４〕本実施形態の予測装置の動作
次に、上述のごとく構成された本実施形態の予測装置１０の動作について、図１９〜図２７を参照しながら説明する。
【０１５７】
まず、識別モデル生成装置２０において、受付部５０によりエラー有無情報Ｈとともに既知パターン集合Ｓが既知パターンデータ４０として受け付けられる。既知パターン集合Ｓが受け付けられると、ドロネー三角網生成部５１によって、既知パターン集合Ｓの各既知パターンｓｉから、ドロネー三角網に基づくグラフｇｉが生成される。
【０１５８】
〔４−１〕グラフ生成部の動作
図１９に示すフローチャート（ステップＳ１０，Ｓ２０，Ｓ３０）に従って、本実施形態におけるグラフ生成部５２の動作について説明する。
【０１５９】
図１９に示すように、グラフ生成部５２には、上述のごとき既知パターン集合（レイアウトパターン群）Ｓ＝｛ｓ１，ｓ２，…，ｓＮ｝）と、上述のごときグラフ群Ｇ＝｛ｇ１，ｇ２，…，ｇＮ｝とが入力される。既知パターン集合Ｓおよびグラフ群Ｇが入力されると、まず、ノードラベル生成部５２ａにより、各既知パターンｓｉに対応するドロネー三角網に基づくグラフｇｉのノードｖikにおいて、相対的位置関係に関する属性に基づくラベルが生成され各グラフｇｉに付与される（ステップＳ１０）。ラベルを付与されたグラフｇｉはｇ’ｉと表記される。
【０１６０】
そして、隣接情報付与部５２ｂにより、各既知パターンｓｉに対応するドロネー三角網に基づくグラフｇｉのノードｖikにおいて、隣接情報に基づくラベルが生成され各グラフｇ’ｉに付与される（ステップＳ２０）。
【０１６１】
さらに、エッジ重み付与部５２ｃにより、自ノードと隣接ノードとの距離がエッジの重みとして計算され、計算されたエッジの重みが、隣接情報考慮ラベル付きの各グラフｇ’ｉに付与され、隣接情報考慮ラベル・エッジ重み付きグラフ４２（グラフ群Ｇ’）が生成される（ステップＳ３０）。このようにして、グラフ生成部５２（エッジ重み付与部５２ｃ）の出力として、図１９や図２２に示すような、隣接情報考慮ラベルとエッジ重み付きグラフ群Ｇ’が得られる。
【０１６２】
〔４−１−１〕ノードラベル生成部の動作
次に、図２０に示すフローチャート（ステップＳ１１〜Ｓ１５）に従って、図１９のステップＳ１０の処理、つまり本実施形態におけるノードラベル生成部５２ａの動作について説明する。
【０１６３】
図２０に示すように、既知パターン集合Ｓおよびグラフ群Ｇが入力されると、まず、ノードラベル生成部５２ａは、グラフ群Ｇの中から未選択のグラフｇｉを選択する（ステップＳ１１）。さらに、ノードラベル生成部５２ａは、グラフｇｉの中から未選択のノードｖikを選択する（ステップＳ１２）。
【０１６４】
そして、ノードラベル生成部５２ａは、ビットデータ４１を参照して、電気的属性情報（電気的特性）である相対的位置関係に関する属性ｆikからノードラベル情報ｌvikを生成する（ステップＳ１３）。生成されたノードラベル情報ｌvikは、例えば２ビットのビット列で、ノードｖikに対応付けられ付与される。
【０１６５】
この後、ノードラベル生成部５２ａは、グラフｇｉ内の全てのノードを選択したか否かを判断する（ステップＳ１４）。全てのノードを選択していない場合（ステップＳ１４のＮＯルート）、ノードラベル生成部５２ａはステップＳ１２の処理に戻る。
【０１６６】
全てのノードを選択した場合（ステップＳ１４のＹＥＳルート）、ノードラベル生成部５２ａは、グラフ群Ｇ内の全てのグラフを選択したか否かを判断する（ステップＳ１５）。全てのグラフを選択していない場合（ステップＳ１５のＮＯルート）、ノードラベル生成部５２ａはステップＳ１１の処理に戻る。
【０１６７】
全てのグラフを選択した場合（ステップＳ１５のＹＥＳルート）、ノードラベル生成部５２ａは、図２０に示すように、属性ｆikに基づく基盤となるラベルを付与されたグラフ群Ｇ’を隣接情報付与部５２ｂに出力し、処理を終了する。
【０１６８】
〔４−１−２〕隣接情報付与部の動作
次に、図２１に示すフローチャート（ステップＳ２１〜Ｓ２８）に従って、図１９のステップＳ２０の処理、つまり本実施形態における隣接情報付与部５２ｂの動作について説明する。
【０１６９】
図２１に示すように、属性ｆikに基づく基盤となるラベルを付与されたグラフ群Ｇ’がノードラベル生成部５２ａから入力されると、まず、隣接情報付与部５２ｂは、グラフ群Ｇ’の中から未選択のグラフｇ’ｉを選択する（ステップＳ２１）。さらに、隣接情報付与部５２ｂは、グラフｇ’ｉの中から未選択のノードｖ’ikを選択する（ステップＳ２２）。
【０１７０】
そして、隣接情報付与部５２ｂは、自ノード（着目ノード）ｖ’ikの隣接ノードｖ’ik1，…，ｖ’ikmのラベルｌik1，…，ｌikmについて、隣接情報考慮ラベルに必要な部分ビット列ｂik1，…，ｂikmを取り出す（ステップＳ２３）。隣接情報付与部５２ｂは、取り出した部分ビット列ｂik1，…，ｂikmについて、隣接情報ラベルＮik＝ＸＯＲ（ｂik1，…，ｂikm）を計算する（ステップＳ２４）。
【０１７１】
さらに、隣接情報付与部５２ｂは、自ノードｖ’ikの自ノードラベルｌvikを左詰めしたノードラベルｌ’vikを計算する（ステップＳ２５）。隣接情報付与部５２ｂは、計算されたノードラベルｌ’vikと隣接情報ラベルＮikとの論理和ＯＲ（ｌ’vik，Ｎik）を、隣接情報考慮ラベルｌvik_newとして計算する（ステップＳ２６）。計算された隣接情報考慮ラベルｌvik_newは、例えば４ビットのビット列で、ノードｖ’ikに対応付けられ付与される。
【０１７２】
この後、隣接情報付与部５２ｂは、は、グラフｇ’ｉ内の全てのノードを選択したか否かを判断する（ステップＳ２７）。全てのノードを選択していない場合（ステップＳ２７のＮＯルート）、隣接情報付与部５２ｂはステップＳ２２の処理に戻る。
【０１７３】
全てのノードを選択した場合（ステップＳ２７のＹＥＳルート）、隣接情報付与部５２ｂは、グラフ群Ｇ’内の全てのグラフを選択したか否かを判断する（ステップＳ２８）。全てのグラフを選択していない場合（ステップＳ１５のＮＯルート）、隣接情報付与部５２ｂはステップＳ２１の処理に戻る。
【０１７４】
全てのグラフを選択した場合（ステップＳ２８のＹＥＳルート）、隣接情報付与部５２ｂは、図２１に示すように、隣接情報考慮ラベルｌvik_newを付与されたグラフ群Ｇ’をエッジ重み付与部５２ｃに出力し、処理を終了する。
【０１７５】
〔４−１−３〕エッジ重み付与部の動作
次に、図２２に示すフローチャート（ステップＳ３１〜Ｓ３７）に従って、図１９のステップＳ３０の処理、つまり本実施形態におけるエッジ重み付与部５２ｃの動作について説明する。
【０１７６】
図２２に示すように、隣接情報考慮ラベルｌvik_newを付与されたグラフ群Ｇ’隣接情報付与部５２ｂから入力されると、まず、エッジ重み付与部５２ｃは、グラフ群Ｇ’の中から未選択のグラフｇ’ｉを選択する（ステップＳ３１）。さらに、エッジ重み付与部５２ｃは、グラフｇ’ｉの中から未選択のノードｖ’ikを選択する（ステップＳ３２）。
【０１７７】
そして、エッジ重み付与部５２ｃは、自ノードｖ’ikの隣接ノードｖ’ik0，ｖ’ik1，ｖ’ik2を選択する（ステップＳ３３）。ドロネー三角網に基づくノードにおいて、隣接ノードは、三角形の辺を共有するノードであり、最大３個存在する。
【０１７８】
エッジ重み付与部５２ｃは、上記(3)式によって、自ノードｖ’ikと隣接ノードｖ’ik0，ｖ’ik1，ｖ’ik2のそれぞれとの距離ｄik0，ｄik1，ｄik2を計算する（ステップＳ３４）。
【０１７９】
エッジ重み付与部５２ｃは、計算された３つの距離ｄik0，ｄik1，ｄik2を、ノードｖ’ikと隣接ノードｖ’ikmとの間のエッジの重みｗik＝{ｄik0，ｄik1，ｄik2}としてノードｖ’ikに対応付けてグラフｇ’に付与する（ステップＳ３５）。
【０１８０】
この後、エッジ重み付与部５２ｃは、グラフｇ’ｉ内の全てのノードを選択したか否かを判断する（ステップＳ３６）。全てのノードを選択していない場合（ステップＳ３６のＮＯルート）、エッジ重み付与部５２ｃはステップＳ３２の処理に戻る。
【０１８１】
全てのノードを選択した場合（ステップＳ３６のＹＥＳルート）、エッジ重み付与部５２ｃは、グラフ群Ｇ’内の全てのグラフを選択したか否かを判断する（ステップＳ３７）。全てのグラフを選択していない場合（ステップＳ３７のＮＯルート）、エッジ重み付与部５２ｃはステップＳ３１の処理に戻る。
【０１８２】
全てのグラフを選択した場合（ステップＳ３７のＹＥＳルート）、エッジ重み付与部５２ｃは、エッジの重みを付与された隣接情報考慮ラベル付きグラフ群Ｇ’を、隣接情報考慮ラベル・エッジ重み付きラベル４２として出力し、処理を終了する。
【０１８３】
〔４−１−４〕予測部におけるグラフ生成部の動作
ここでは、識別モデル生成装置２０におけるグラフ生成部５２（ノードラベル生成部５２ａ、隣接情報付与部５２ｂおよびエッジ重み付与部５２ｃ）の動作について説明しているが、予測部６０におけるグラフ生成部９２（ノードラベル生成部９２ａ、隣接情報付与部９２ｂおよびエッジ重み付与部９２ｃ）も同様に動作する。
【０１８４】
ただし、予測部６０に入力されるレイアウトパターン群ｓｕは、未知パターンデータ８０であるため、既知パターンデータ４０に含まれるエラー有無情報Ｈを含まない。グラフ生成部９２では、上述したグラフ生成部５２の動作と同様にして、未知パターンデータ８０についての、エッジの重みを付与された隣接情報考慮ラベル付きグラフ群Ｇ”が生成され出力される。
【０１８５】
〔４−２〕識別モデル生成部の動作
次に、図２３に示すフローチャート（ステップＳ４０）に従って、本実施形態における識別モデル生成部５３の動作について説明する。
【０１８６】
図２３に示すように、既知パターン集合Ｓ＝｛ｓ１，・・・，ｓＮ｝およびエラー有無情報Ｈ＝｛ｈ１，・・・，ｈＮ｝と、グラフ生成部５２からのグラフ群Ｇ’とが入力されると、識別モデル生成部５３は、以下の動作を行なう（ステップＳ４０）。
【０１８７】
つまり、識別モデル生成部５３は、グラフ群Ｇ’と、各グラフｇ’ｉに対応するエラー有無情報ｈｉとから、上記(4)式を満たす係数値αｉを求める。このとき、サポートベクタマシンなどの既知手法が用いられる。下記(4)式におけるＫ（ｇ’ｉ，ｇ’ｊ）は、既知パターンどうしであるグラフｇ’ｉとグラフｇ’ｊとの類似度である。
【０１８８】
本実施形態において、類似度Ｋ（ｇ’ｉ，ｇ’ｊ）は、上記(1)式および図１３に示す類似度計算アルゴリズムに基づく処理を行なうことで、つまり図２４を参照しながら後述する手順で計算される。これにより、生成したノードラベルおよびエッジの重みを用いて算出した各既知パターンどうしの類似度に基づいて、図２３に示すように、上記(5)式で表現されるエラー識別モデルが生成される。
【０１８９】
〔４−３〕類似度計算動作
ここで、図２４に示すフローチャート（ステップＳ５０〜Ｓ６０）に従って、本実施形態における類似度計算動作について説明する。当該類似度計算動作は、類似度を用いる識別モデル生成部５３および類似度評価部９３において実行される。
【０１９０】
識別モデル生成部５３の類似度計算対象の二つのグラフｇａおよびｇｂは、いずれも既知パターンから得られるグラフ群Ｇ’に属する。一方、類似度評価部９３の類似度計算対象の二つのグラフｇ”ｉおよびｇ’ｊは、それぞれ、未知パターンから得られるグラフ群Ｇ”、および、既知パターンから得られるグラフ群Ｇ’に属する。ここでは、識別モデル生成部５３での類似度計算について、つまり類似度計算対象がグラフ群Ｇ’に属する二つのグラフｇａおよびｇｂである場合について説明する。
【０１９１】
図２４に示すように、グラフ群Ｇ’に属する二つのグラフｇａおよびｇｂについての情報が、記憶部３０のグラフ４２から、もしくは、エッジ重み付与部５２ｃ（グラフ生成部５２）から入力されると、まず、初期値設定（ｉ＝１，ｊ＝１，ラベルの一致数ctotal＝０）が行なわれる（ステップＳ５０）。
【０１９２】
そして、グラフｇａのノードｖ’aiのラベルｌaiとグラフｇｂのノードｖ’bjのノードラベルｌbjとが一致するか否かが判定される（ステップＳ５１）。ノードラベルｌaiとｌbjとが一致する場合（ステップＳ５１のＹＥＳルート）、上記(1)式と同様の下記(7)式によってラベルの一致度ｃが計算される（ステップＳ５２）。
【０１９３】
【数４】
2018165887.tif 000006
【０１９４】
なお、係数αは、予め設定された値、または、識別モデル生成部５３で最適化された値である。ここでは、α＝１とする。
【０１９５】
この後、ｃtotalはｃtotal＋ｃに、ｉはｉ＋１に、ｊはｊ＋１にそれぞれ置き換えられてから（ステップＳ５３）、ｉがグラフｇａのノード数ｎに達したか、もしくは、ｊがグラフｇｂのノード数ｍに達したかが判定される（ステップＳ５４）。
【０１９６】
ｉがｎに到達しておらずｊがｍに到達していない場合（ステップＳ５４のＮＯルート）、ｉをｉ＋１に置き換えてから（ステップＳ５５）、ステップＳ５１の処理が実行される。ｉがｎに到達もしくはｊがｍに到達した場合（ステップＳ５４のＹＥＳルート）、グラフｇａとｇｂとの類似度Ｋ(ｇａ，ｇｂ)としてＫ(ｇａ，ｇｂ)＝ｃtotal / (ｎ＋ｍ−ｃtotal)が算出され出力される（ステップＳ６０）。
【０１９７】
一方、ノードラベルｌaiとｌbjとが一致しない場合（ステップＳ５１のＮＯルート）、ラベルの一致度ｃは“０”に設定される（ステップＳ５６）。そして、ノードラベルｌaiがノードラベルｌbjよりも小さいか否かが判定される（ステップＳ５７）。ノードラベルｌaiがノードラベルｌbjよりも小さい場合（ステップＳ５７のＹＥＳルート）、ｉをｉ＋１に置き換えてから（ステップＳ５８）、ステップＳ５４の処理が実行される。、ノードラベルｌaiがノードラベルｌbj以上である場合（ステップＳ５７のＮＯルート）、ｊをｊ＋１に置き換えてから（ステップＳ５９）、ステップＳ５４の処理が実行される。
【０１９８】
〔４−４〕類似度評価部の動作
次に、図２５に示すフローチャート（ステップＳ６１〜Ｓ６６）に従って、本実施形態における類似度評価部９３の動作について説明する。
【０１９９】
図２５に示すように、未知パターンから得られるグラフ群Ｇ”と既知パターンから得られるグラフ群Ｇ’とが類似度計算対象として入力されると、類似度評価部９３は、以下の動作を行なう（ステップＳ６１〜Ｓ６６）。
【０２００】
まず、類似度評価部９３は、グラフ群Ｇ”の中から未選択のグラフｇ”ｉを選択する（ステップＳ６１）。さらに、類似度評価部９３は、グラフ群Ｇ’の中から未選択のグラフｇ’ｊを選択する（ステップＳ６２）。
【０２０１】
そして、類似度評価部９３は、選択されたグラフｇ”ｉとｇ’ｊとの類似度Ｋ（ｇ”ｉ，ｇ’ｊ）を、図２４を参照しながら上述した手順で計算する（ステップＳ６３）。この後、類似度評価部９３は、グラフｇ”ｉとグラフ群Ｇ’内の全てのグラフとの類似度を計算したか否かを判断する（ステップＳ６４）。グラフ群Ｇ’内の全てのグラフとの類似度を計算していない場合（ステップＳ６４のＮＯルート）、類似度評価部９３はステップＳ６２の処理に戻る。
【０２０２】
グラフ群Ｇ’内の全てのグラフとの類似度を計算した場合（ステップＳ６４のＹＥＳルート）、類似度評価部９３は、類似度Ｋ（ｇ”ｉ，ｇ’ｊ）の値の上位ｒ個のグラフｇ’ｊを、グラフｇ”ｉの類似パターン（特定配線パターン群）として抽出列挙する（ステップＳ６５）。当該類似パターンに関する情報は、類似度評価結果８２として出力され、記憶部７３に保存される。
【０２０３】
この後、類似度評価部９３は、グラフ群Ｇ”内の全てのグラフを選択したか否かを判断する（ステップＳ６６）。全てのグラフを選択していない場合（ステップＳ６６のＮＯルート）、類似度評価部９３はステップＳ６１の処理に戻る。全てのグラフを選択した場合（ステップＳ６６のＹＥＳルート）、類似度評価部９３は処理を終了する。
【０２０４】
〔４−５〕エラー識別部の動作
次に、図２６に示すフローチャート（ステップＳ７１〜Ｓ７３）に従って、本実施形態におけるエラー識別部９４の動作を説明するフローチャートである。
【０２０５】
図２６に示すように、未知パターンから得られるグラフ群Ｇ”と上記(5)式に示すエラー識別モデル情報４３とが入力されると、エラー識別部９４は、以下の動作を行なう（ステップＳ７１〜Ｓ７３）。
【０２０６】
まず、エラー識別部９４は、グラフ群Ｇ”の中から未選択のグラフｇ”ｉを選択する（ステップＳ７１）。
【０２０７】
そして、エラー識別部９４は、選択されたグラフｇ”ｉについて、エラー識別モデルの値ｆ（ｇ”ｉ）を下記(8)式のごとく計算し、グラフｇ”ｉにおけるホットスポット（エラー）の有無を判定する（ステップＳ７２）。このとき、エラー識別部９４は、ｆ（ｇ”ｉ）≧０の場合、エラー有りと判定する一方、ｆ（ｇ”ｉ）＜０の場合、エラー無しと判定する。グラフｇ”ｉについての判定結果は、エラー判定結果８３として出力され、記憶部７３に保存される。
【０２０８】
【数５】
2018165887.tif 000007
【０２０９】
この後、エラー識別部９４は、グラフ群Ｇ”内の全てのグラフを選択したか否かを判断する（ステップＳ７３）。全てのグラフを選択していない場合（ステップＳ７３のＮＯルート）、エラー識別部９４はステップＳ７１の処理に戻る。全てのグラフを選択した場合（ステップＳ７３のＹＥＳルート）、エラー識別部９４は処理を終了する。
【０２１０】
これにより、エラー識別部９４による判定結果に基づき、グラフｇ”ｉ毎にエラー有無判定が行なわれる。そして、エラー有りと判定されたグラフｇ”ｉについて、類似度評価部９３によって抽出された上位ｒ個のグラフｇ’ｊが、ホットスポット発生箇所の候補として特定される。
【０２１１】
〔４−６〕表示制御部の動作
次に、表示制御部（提示部）９５の動作について説明する。表示制御部９５は、類似度評価部９３によって得られた類似度評価結果８２や、エラー識別部９４によって得られたエラー判定結果８３に基づいて、既知パターンを未知パターンとの類似度が高い順に表示部７１で提示させる。このとき、表示制御部９５は、エラー判定結果８３から、エラー識別部９４により求められたエラーの有無に関する情報やその情報の信頼度も併せて提示させてもよい。例えば、表示制御部９５は、エラー識別部９４から未知パターンｓｕの検証終了を示す信号を受け付けた場合に、類似度評価結果８２に従って、各既知パターンを、未知パターンｓｕとの類似度の大きさに応じた順に、表示部７１で表示させる。このとき、表示制御部９５は、例えば、各順位に、既知パターン名と、パターンの図面と、類似度とを対応付け、表示部７１に表示させる。
【０２１２】
ここで、図２７に、表示部７１により表示された画面の一例を示す。図２７は、未知パターンのエラーに関する情報を表示するとともに、未知パターンとの類似度が高い既知パターンに関する情報を類似度の高い順に表示する画面の一例を示す図である。図２７の例は、エラー識別部９４が未知パターン「Ｕ１００２２」に欠陥ありと識別し、その検証結果の信頼度を「０．９７」と算出したことを示している。また、図２７の例は、類似度評価部９３が未知パターン「Ｕ１００２２」と、既知パターン「Ｐ０２５」、「Ｐ００２」、「Ｐ００８」、「Ｐ０２７」それぞれとの類似度を、「０．９９」、「０．９８」、「０．９７」、「０．５８」と算出したことを示す。さらに、図２７の例は、類似度評価部９３が未知パターン「Ｕ１００２２」との類似度の大きさに応じた順位として、「Ｐ０２５：１位」、「Ｐ００２：２位」、「Ｐ００８：３位」、「Ｐ０２７：４位」といった順位付けを行なったことを示す。
【０２１３】
なお、図２７では、表示部７１を介して順位１位〜４位までの既知パターンを提示する例を示しているが、この例に限らず、例えば、１〜１０位までであってもよい。即ち、どの順位まで提示するかは、類似度評価部９３に対し任意に設定されてよい。
【０２１４】
〔５〕その他
以上、本発明の好ましい実施形態について詳述したが、本発明は、係る特定の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲内において、種々の変形、変更して実施することができる。
【０２１５】
なお、上述した実施形態では、予測装置１０は、グラフ４２（グラフ群Ｇ’，Ｇ”）およびエラー識別モデル４３を生成する識別モデル生成装置２０と、実際にエラーの発生箇所の特定を行なう予測部６０との異なる二つの装置によって構成される例を説明した。しかし、予測装置１０は、識別モデル生成装置２０と予測部６０とを一つの装置として構成されてもよい。
【０２１６】
即ち、識別モデル生成装置２０と予測部６０とが一体化された装置を予測装置１０としてもよく、このとき、例えば、受付部５０と９０、ドロネー三角網生成部５１と９１、グラフ生成部５２と９２において、これら各組合せの構成要素が行なう処理は互いに同一であるため、上記各組合せの構成要素は一つの構成要素として構成することができる。具体的には、上記各組合せの構成要素において、処理対象が未知パターンであるか既知パターンであるか、また、処理対象の組合せが、既知パターンどうしであるか、未知パターンと既知パターンとであるかの違いであり、処理動作そのものに違いはないため、一つの構成要素として構成することができる。また、ビットデータ４１および８１も、記憶しているデータ内容は同一のものであるため、一つの構成要素として構成することができる。
【０２１７】
さらに、本実施形態の予測装置１０における各処理機能は、その全部または任意の一部が、ＣＰＵおよび当該ＣＰＵにて実行される予測プログラムによって実現され、あるいは、ワイヤードロジックによるハードウェアとして実現され得る。
【０２１８】
特に、本実施形態で説明した各種の処理は、予め用意されたプログラムをパーソナルコンピュータやワークステーションなどのコンピュータシステムで実行することによって実現することができる。そこで、以下では、本実施形態と同様の機能を有するプログラムを実行するコンピュータシステムの一例について説明する。図２８は、本実施形態の予測プログラム１２０ａを実行するコンピュータ１００を示すブロック図である。
【０２１９】
図２８に示すように、コンピュータ１００は、ＣＰＵ１１０、ＲＯＭ（Read Only Memory）１２０、ＨＤＤ（Hard Disk Drive）１３０、ＲＡＭ１４０を有する。これらのＣＰＵ１１０、ＲＯＭ１２０、ＨＤＤ１３０、ＲＡＭ１４０の相互間はバス２００を介して接続される。
【０２２０】
ＲＯＭ１２０には、本実施形態の各構成要素と同様の機能を発揮する予測プログラム１２０ａが予め記憶される。例えば、本実施形態の受付部５０，９０；ドロネー三角網生成部５１，９１；グラフ生成部５２，９２；識別モデル生成部５３；類似度評価部９３；エラー識別部９４および表示制御部９５と同様の機能を発揮する予測プログラム１２０ａを記憶させる。なお、予測プログラム１２０ａについては、適宜分離してもよい。なお、ＨＤＤ１３０には、例えば、ＯＳや、各種処理に用いられる各種データを記憶される。
【０２２１】
そして、ＣＰＵ１１０が、予測プログラム１２０ａをＲＯＭ１２０から読み出して実行することで、本実施形態の各構成要素と同様の動作を実行する。つまり、予測プログラム１２０ａは、本実施形態の受付部５０，９０；ドロネー三角網生成部５１，９１；グラフ生成部５２，９２；識別モデル生成部５３；類似度評価部９３；エラー識別部９４および表示制御部９５と同様の動作を実現する。
【０２２２】
なお、上述した予測プログラム１２０ａについては、必ずしも最初からＲＯＭ１２０に記憶させることを要しない。予測プログラム１２０ａは、ＨＤＤ１３０に記憶させておいてもよい。この場合、ＣＰＵ１１０は、ＨＤＤ１３０から読み出した予測プログラム１２０ａをＲＡＭ１４０に展開して実行してもよい。
【０２２３】
また、例えば、コンピュータ１００に挿入されるフレキシブルディスク、ＣＤ−ＲＯＭ、ＤＶＤ、光磁気ディスク、ＩＣカード、ブルーレイディスクなどの「可搬型物理媒体」に予測プログラム１２０ａを記憶させておいてもよい。この場合、コンピュータ１００は、当該「可搬型物理媒体」から予測プログラム１２０ａを読み出して実行してもよい。ここで、ＣＤ−ＲＯＭはCompact Disk Read Only Memoryの略称であり、ＤＶＤはDigital Versatile Diskの略称であり、ＩＣはIntegrated Circuitの略称である。
【０２２４】
さらに、公衆回線、インターネット、ＬＡＮ、ＷＡＮ（Wide Area Network）などを介してコンピュータ１００に接続される「他のコンピュータ（またはサーバ）」などに予測プログラム１２０ａを記憶させておいてもよい。この場合、コンピュータ１００は、「他のコンピュータ（またはサーバ）」などから予測プログラム６０を読み出して実行してもよい。
【０２２５】
〔６〕付記
以上の本実施形態を含む実施形態に関し、さらに以下の付記を開示する。
【０２２６】
（付記１）
露光パターンに含まれる複数の配線パターンのそれぞれから生成されるドロネー三角網に基づき、前記ドロネー三角網における複数の三角形それぞれの中心に対応するノードに関連付けて、当該ノードおよび当該ノードの隣接ノードの情報を含む複数のノードベクトルを生成し、
前記複数のノードベクトルの各要素、および、記憶部に蓄積された、ホットスポットに対応したノードベクトルに関するノードベクトル情報に基づき、前記複数のノードベクトルから候補ノードベクトル群を抽出し、
前記候補ノードベクトル群に含まれるノードベクトルのそれぞれについて、当該ノードベクトルに対応するドロネー三角網を参照し、当該ノードベクトルが参照するノードと隣接ノードとの距離に関する複数の距離評価値を算出し、
前記複数の距離評価値に基づき、前記候補ノードベクトル群から、ホットスポット候補となる特定配線ノードベクトル群を抽出し、
前記特定配線ノードベクトル群に基づき、前記露光パターンにおけるホットスポットの発生箇所の候補を特定する、
処理を、コンピュータに実行させる、予測プログラム。
【０２２７】
（付記２）
前記複数の距離評価値を、前記ノードと前記隣接ノードとを接続するエッジの重みとして与えられる、前記ノードと前記隣接ノードとの前記距離に応じた値に基づき算出する、
処理を、前記コンピュータに実行させる、付記１に記載の予測プログラム。
【０２２８】
（付記３）
前記エッジの前記重みを、前記複数のノードベクトルの生成時に前記ノードの情報として付与する、
処理を、前記コンピュータに実行させる、付記２に記載の予測プログラム。
【０２２９】
（付記４）
処理部を有し、
前記処理部は、
露光パターンに含まれる複数の配線パターンのそれぞれから生成されるドロネー三角網に基づき、前記ドロネー三角網における複数の三角形それぞれの中心に対応するノードに関連付けて、当該ノードおよび当該ノードの隣接ノードの情報を含む複数のノードベクトルを生成し、
前記複数のノードベクトルの各要素、および、記憶部に蓄積された、ホットスポットに対応したノードベクトルに関するノードベクトル情報に基づき、前記複数のノードベクトルから候補ノードベクトル群を抽出し、
前記候補ノードベクトル群に含まれるノードベクトルのそれぞれについて、当該ノードベクトルに対応するドロネー三角網を参照し、当該ノードベクトルが参照するノードと隣接ノードとの距離に関する複数の距離評価値を算出し、
前記複数の距離評価値に基づき、前記候補ノードベクトル群から、ホットスポット候補となる特定配線ノードベクトル群を抽出し、
前記特定配線ノードベクトル群に基づき、前記露光パターンにおけるホットスポットの発生箇所の候補を特定する、予測装置。
【０２３０】
（付記５）
前記処理部は、前記複数の距離評価値を、前記ノードと前記隣接ノードとを接続するエッジの重みとして与えられる、前記ノードと前記隣接ノードとの前記距離に応じた値に基づき算出する、付記４に記載の予測装置。
【０２３１】
（付記６）
前記処理部は、前記エッジの前記重みを、前記複数のノードベクトルの生成時に前記ノードの情報として付与する、付記５に記載の予測装置。
【０２３２】
（付記７）
処理部が、
露光パターンに含まれる複数の配線パターンのそれぞれから生成されるドロネー三角網に基づき、前記ドロネー三角網における複数の三角形それぞれの中心に対応するノードに関連付けて、当該ノードおよび当該ノードの隣接ノードの情報を含む複数のノードベクトルを生成し、
前記複数のノードベクトルの各要素、および、記憶部に蓄積された、ホットスポットに対応したノードベクトルに関するノードベクトル情報に基づき、前記複数のノードベクトルから候補ノードベクトル群を抽出し、
前記候補ノードベクトル群に含まれるノードベクトルのそれぞれについて、当該ノードベクトルに対応するドロネー三角網を参照し、当該ノードベクトルが参照するノードと隣接ノードとの距離に関する複数の距離評価値を算出し、
前記複数の距離評価値に基づき、前記候補ノードベクトル群から、ホットスポット候補となる特定配線ノードベクトル群を抽出し、
前記特定配線ノードベクトル群に基づき、前記露光パターンにおけるホットスポットの発生箇所の候補を特定する、予測方法。
【０２３３】
（付記８）
前記処理部が、前記複数の距離評価値を、前記ノードと前記隣接ノードとを接続するエッジの重みとして与えられる、前記ノードと前記隣接ノードとの前記距離に応じた値に基づき算出する、付記７に記載の予測方法。
【０２３４】
（付記９）
前記処理部が、前記エッジの前記重みを、前記複数のノードベクトルの生成時に前記ノードの情報として付与する、付記８に記載の予測方法。
【符号の説明】
【０２３５】
１０    予測装置
２０    識別モデル生成装置
３０    記憶部
３１    処理部
４０    既知パターンデータ
４１    ビットデータ
４２    隣接情報考慮ラベル・エッジ重み付きグラフ
４３    エラー識別モデル情報
５０    受付部
５１    ドロネー三角網生成部
５２    グラフ生成部
５２ａ    ノードラベル生成部
５２ｂ    隣接情報付与部
５２ｃ    エッジ重み付与部
５３    識別モデル生成部
６０    予測部
７０    入力部
７１    表示部
７２    通信Ｉ／Ｆ部
７３    記憶部
７４    処理部
８０    未知パターンデータ
８１    ビットデータ
８２    類似度評価結果
８３    エラー判定結果
９０    受付部
９１    ドロネー三角網
９２    グラフ生成部
９２ａ    ノードラベル生成部
９２ｂ    隣接情報付与部
９２ｃ    エッジ重み付与部
９３    類似度評価部
９４    エラー識別部
９５    表示制御部（提示部）
１００    コンピュータ
１１０    ＣＰＵ（処理部）
１２０    ＲＯＭ
１２０ａ    予測プログラム
１３０    ＨＤＤ（記憶部）
１４０    ＲＡＭ（記憶部）
２００    バス
【図１】
2018165887.tif 000008
【図２】
2018165887.tif 000009
【図３】
2018165887.tif 000010
【図４】
2018165887.tif 000011
【図５】
2018165887.tif 000012
【図６】
2018165887.tif 000013
【図７】
2018165887.tif 000014
【図８】
2018165887.tif 000015
【図９】
2018165887.tif 000016
【図１０】
2018165887.tif 000017
【図１１】
2018165887.tif 000018
【図１２】
2018165887.tif 000019
【図１３】
2018165887.tif 000020
【図１４】
2018165887.tif 000021
【図１５】
2018165887.tif 000022
【図１６】
2018165887.tif 000023
【図１７】
2018165887.tif 000024
【図１８】
2018165887.tif 000025
【図１９】
2018165887.tif 000026
【図２０】
2018165887.tif 000027
【図２１】
2018165887.tif 000028
【図２２】
2018165887.tif 000029
【図２３】
2018165887.tif 000030
【図２４】
2018165887.tif 000031
【図２５】
2018165887.tif 000032
【図２６】
2018165887.tif 000033
【図２７】
2018165887.tif 000034
【図２８】
2018165887.tif 000035