(57)【要約】【課題】ホットスポットの検出精度を向上する。【解決手段】処理部１２は、露光範囲を包含する大きさごとに半導体集積回路の露光パターン１１ａを分割して生成されるクリップ領域１１ｂ１〜１１ｂｎの情報を取得し、その情報に基づいてクリップ領域１１ｂ１〜１１ｂｎのそれぞれにおいて、露光パターン１１ａにあるホットスポットの検出に用いられるドロネー三角網１５を、ドロネー三角形分割により生成し、ドロネー三角網１５において、クリップ領域１１ｂ１〜１１ｂｎのそれぞれの境界に配置された露光パターン１１ａの一部である図形の頂点を含む複数の三角形から、１つ以上の頂点が境界に位置する第１の三角形群、及び、２つ以上の頂点が境界に位置する第２の三角形群を抽出し、ドロネー三角網１５から第１の三角形群を除いた三角網１６ａ、及び、ドロネー三角網１５から第２の三角形群を除いた三角網１６ｂを生成する。【選択図】図１
2019159905.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータに、
露光範囲を包含する大きさごとに半導体集積回路の露光パターンを分割して生成される複数の矩形領域の情報を取得し、
前記情報に基づいて前記複数の矩形領域のそれぞれにおいて、前記露光パターンにあるホットスポットの検出に用いられるドロネー三角網を、ドロネー三角形分割により生成し、
前記ドロネー三角網において、前記複数の矩形領域のそれぞれの境界に配置された前記露光パターンの一部である図形の頂点を含む複数の三角形から、１つ以上の頂点が前記境界に位置する第１の三角形群、及び、２つ以上の頂点が前記境界に位置する第２の三角形群を抽出し、
前記ドロネー三角網から前記第１の三角形群を除いた第１の三角網、及び、前記ドロネー三角網から前記第２の三角形群を除いた第２の三角網を生成する、
処理を実行させる生成プログラム。
【請求項２】
前記第１の三角形群、及び、前記第２の三角形群は、前記複数の三角形のうち、中心が前記境界から第１の距離よりも離れている第１の三角形を除外して抽出される、
請求項１に記載の生成プログラム。
【請求項３】
前記第１の三角網、及び、前記第２の三角網は、前記ホットスポットの有無が既知の前記矩形領域を教師データとして、前記ホットスポットの検出に用いられるそれぞれ異なる２つの識別モデルを機械学習により生成する際に用いられる、
請求項１または２に記載の生成プログラム。
【請求項４】
前記複数の三角形のそれぞれに設定されるノードには、前記境界に位置する前記複数の三角形のそれぞれの頂点数を示す第１の情報が割り当てられている、
請求項１乃至３の何れか一項に記載の生成プログラム。
【請求項５】
前記複数の三角形のそれぞれに設定されるノードには、前記中心が前記境界から前記第１の距離よりも離れているか否かを示す第２の情報が割り当てられている、
請求項２に記載の生成プログラム。
【請求項６】
露光範囲を包含する大きさごとに半導体集積回路の露光パターンを分割して生成される複数の矩形領域の情報を記憶する記憶部と、
前記情報に基づいて、前記複数の矩形領域のそれぞれにおいて、前記露光パターンにあるホットスポットの検出に用いられるドロネー三角網を、ドロネー三角形分割により生成し、前記ドロネー三角網において、前記複数の矩形領域のそれぞれの境界に配置された前記露光パターンの一部である図形の頂点を含む複数の三角形から、１つ以上の頂点が前記境界に位置する第１の三角形群、及び、２つ以上の頂点が前記境界に位置する第２の三角形群を抽出し、前記ドロネー三角網から前記第１の三角形群を除いた第１の三角網、及び、前記ドロネー三角網から前記第２の三角形群を除いた第２の三角網を生成する処理部と、
を有する生成装置。
【請求項７】
コンピュータが実行する生成方法であって、
露光範囲を包含する大きさごとに半導体集積回路の露光パターンを分割して生成される複数の矩形領域の情報を取得し、
前記情報に基づいて前記複数の矩形領域のそれぞれにおいて、前記露光パターンにあるホットスポットの検出に用いられるドロネー三角網を、ドロネー三角形分割により生成し、
前記ドロネー三角網において、前記複数の矩形領域のそれぞれの境界に配置された前記露光パターンの一部である図形の頂点を含む複数の三角形から、１つ以上の頂点が前記境界に位置する第１の三角形群、及び、２つ以上の頂点が前記境界に位置する第２の三角形群を抽出し、
前記ドロネー三角網から前記第１の三角形群を除いた第１の三角網、及び、前記ドロネー三角網から前記第２の三角形群を除いた第２の三角網を生成する、
生成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ドロネー三角網の生成プログラム、生成装置及び生成方法に関する。
【背景技術】
【０００２】
半導体集積回路の露光工程において基板に転写される露光パターン（レイアウトパターン）は、ホットスポットを含む場合がある。ホットスポットは、光近接効果などの影響により、露光パターンが寸法通りに基板に転写されず、形成される配線に断線などの欠陥が生じる可能性のある箇所である。ホットスポットは、折れ曲がりのある配線が近接する箇所などに生じる。また、露光パターンに含まれる複数の図形のサイズや位置関係などによってホットスポットが生じるか否かが分かれる。
【０００３】
従来、ドロネー三角網を用いて露光パターンを表現し、ドロネー三角網に含まれる各三角形の特徴を表す特徴ベクトルに基づいて問題が生じ得る箇所を特定することで、ホットスポットを検出する技術がある。ドロネー三角網を用いたホットスポットの検出処理時には、ドロネー三角網に含まれる微小な三角形が隣接する箇所が、ホットスポットであると認識されやすい。
【０００４】
なお、ホットスポットを検出する際に、露光範囲を包含する大きさごとに露光パターンを分割することで、複数の矩形領域（以下クリップ領域という）が生成され、クリップ領域ごとに検出が行われる。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０１６−１３３９３６号公報
【特許文献２】特開２００７−２５８３３１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
ところでクリップ領域の境界付近には、分割された露光パターンによる微小な辺や微小な矩形領域が多く生じ、微小な三角形が多く形成される可能性がある。そのため、クリップ領域の境界付近においてホットスポットが誤検出される可能性があった。この問題を解決するために、単にクリップ領域の境界から所定距離以内の露光パターンの図形を、ドロネー三角網の三角形の生成対象外とすることも考えられる。しかし、その場合、クリップ領域のサイズが実質的に縮小されるため、特徴ベクトルで表される境界付近の図形情報が失われ、ホットスポットの検出精度が悪化する可能性がある。
【０００７】
１つの側面では、本発明は、ホットスポットの検出精度を向上することを目的とする。
【課題を解決するための手段】
【０００８】
１つの実施態様では、コンピュータに、露光範囲を包含する大きさごとに半導体集積回路の露光パターンを分割して生成される複数の矩形領域の情報を取得し、前記情報に基づいて前記複数の矩形領域のそれぞれにおいて、前記露光パターンにあるホットスポットの検出に用いられるドロネー三角網を、ドロネー三角形分割により生成し、前記ドロネー三角網において、前記複数の矩形領域のそれぞれの境界に配置された前記露光パターンの一部である図形の頂点を含む複数の三角形から、１つ以上の頂点が前記境界に位置する第１の三角形群、及び、２つ以上の頂点が前記境界に位置する第２の三角形群を抽出し、前記ドロネー三角網から前記第１の三角形群を除いた第１の三角網、及び、前記ドロネー三角網から前記第２の三角形群を除いた第２の三角網を生成する、処理を実行させる生成プログラムが提供される。
【０００９】
また、１つの実施態様では、生成装置が提供される。また、１つの実施態様では、生成方法が提供される。
【発明の効果】
【００１０】
１つの側面では、本発明は、ホットスポットの検出精度を向上できる。
【図面の簡単な説明】
【００１１】
【図１】第１の実施の形態の生成装置の一例を示す図である。
【図２】情報処理装置のハードウェア例を示すブロック図である。
【図３】情報処理装置の機能例を示すブロック図である。
【図４】レイアウト検証工程の一例の流れを示すフローチャートである。
【図５】ホットスポット検出処理の一例の流れを示すフローチャートである。
【図６】欠陥識別モデル生成処理の一例の流れを示すフローチャートである。
【図７】自身のノードの属性を示すラベル情報の計算処理の一例の流れを示すフローチャートである。
【図８】隣接ノードの属性を示すラベル情報を追加してノードラベル情報を生成する処理の一例の流れを示すフローチャートである。
【図９】生成されるノードラベル情報の一例を示す図である。
【図１０】類似度の計算処理の一例の流れを示すフローチャートである。
【図１１】ホットスポット有無判定処理の一例の流れを示すフローチャートである。
【図１２】類似度の評価処理の一例の流れを示すフローチャートである。
【図１３】ホットスポットの有無の判定処理の一例の流れを示すフローチャートである。
【図１４】ホットスポットの有無の判定結果の表示例を示す図である。
【図１５】ドロネー三角網と一部の三角形群を除外した三角網の一例を示す図である。
【発明を実施するための形態】
【００１２】
以下、発明を実施するための形態を、図面を参照しつつ説明する。
（第１の実施の形態）
図１は、第１の実施の形態の生成装置の一例を示す図である。
【００１３】
第１の実施の形態の生成装置１０は、半導体集積回路の露光パターンに存在するホットスポットの検出に用いられるドロネー三角網を生成する。
生成装置１０は、記憶部１１及び処理部１２を有する。
【００１４】
記憶部１１は、ＲＡＭ（Random Access Memory）などの揮発性の記憶装置、または、ＨＤＤ（Hard Disk Drive）やフラッシュメモリなどの不揮発性の記憶装置である。
記憶部１１は、クリップ領域１１ｂ１，１１ｂ２，…，１１ｂｎを記憶する。
【００１５】
クリップ領域１１ｂ１〜１１ｂｎは、露光範囲を包含する大きさごとに、半導体集積回路の露光パターン１１ａを分割して生成される。クリップ領域１１ｂ１〜１１ｂｎのそれぞれが、ホットスポットの検出範囲の一単位となる。露光パターン１１ａは、半導体集積回路の製造工程の１つである露光工程において基板に転写される回路や配線などのレイアウトパターンである。露光パターン１１ａは、図形（配線パターンや素子パターンなど）の集合を含み、図形は頂点座標で定義されている。なお、露光パターン１１ａは、たとえば、半導体集積回路の全体のレイアウトパターンであり、大規模なものでは、たとえば、１辺が１０２μｍ〜１０４μｍの大きさである。クリップ領域１１ｂ１〜１１ｂｎのそれぞれは、たとえば、１辺が１０μｍ以下の大きさの矩形である。
【００１６】
処理部１２は、ＣＰＵ（Central Processing Unit）やＤＳＰ（Digital Signal Processor）などのプロセッサである。ただし、処理部１２は、ＡＳＩＣ（Application Specific Integrated Circuit）やＦＰＧＡ（Field Programmable Gate Array）などの特定用途の電子回路を含んでもよい。プロセッサは、ＲＡＭなどのメモリに記憶されたプログラムを実行する。たとえば、ドロネー三角網の生成プログラムが実行される。なお、複数のプロセッサの集合を「マルチプロセッサ」または単に「プロセッサ」ということがある。
【００１７】
処理部１２は、クリップ領域１１ｂ１〜１１ｂｎの情報（図形の頂点座標などを含む）を記憶部１１から取得する。
なお、処理部１２は、露光パターン１１ａの情報を記憶部１１から取得し、露光パターン１１ａを分割してクリップ領域１１ｂ１〜１１ｂｎを生成し、記憶部１１にクリップ領域１１ｂ１〜１１ｂｎの情報を記憶してもよい。
【００１８】
処理部１２は、取得した情報に基づいて、クリップ領域１１ｂ１〜１１ｂｎのそれぞれにおいて、露光パターン１１ａに存在するホットスポットの検出に用いられるドロネー三角網を、ドロネー三角形分割（Delaunay Triangulation）により生成する。
【００１９】
処理部１２は、たとえば、クリップ領域１１ｂ１〜１１ｂｎのそれぞれに対して、まず、ボロノイ図（Voronoi diagram）を生成し、その後、複数の三角形によるドロネー三角網を生成する。なお、処理部１２は、たとえば、逐次添加法を用いて、ボロノイ図を生成することなく、図形の各頂点座標からドロネー三角網を生成することも可能である。
【００２０】
また、処理部１２は、ドロネー三角網において、クリップ領域１１ｂ１〜１１ｂｎのそれぞれの境界に配置された図形の頂点を含む複数の三角形から、１つ以上の頂点がその境界に位置する第１の三角形群を抽出する。また、処理部１２は、上記複数の三角形から、２つ以上の頂点がその境界に位置する第２の三角形群を抽出する。
【００２１】
図１には、クリップ領域１１ｂ１において生成されたドロネー三角網１５の一部の例が示されている。なお、後述のように、ドロネー三角網１５をグラフとして表すために、全三角形のそれぞれにはノードが設定されるが（たとえば、三角形の中心に設定される）、一部の三角形に設定されるノードを除いて図示が省略されている。ノードには、その三角形の特徴を表す特徴ベクトル（以下、ノードラベル情報という）が割り当てられる。
【００２２】
たとえば、ノード１５ａ１が設定されている三角形１５ｂ１は、図形１５ｃの頂点を含み、１つの頂点がクリップ領域１１ｂ１の境界に位置している。このような三角形１５ｂ１が第１の三角形群に含まれる。一方、ノード１５ａ２が設定されている三角形１５ｂ２は、図形１５ｃの頂点を含み、２つの頂点がクリップ領域１１ｂ１の境界に位置している。このような三角形１５ｂ２が第１の三角形群及び第２の三角形群に含まれる。
【００２３】
その後、処理部１２は、ドロネー三角網から上記第１の三角形群を除いた第１の三角網、及び、ドロネー三角網から上記第２の三角形群を除いた第２の三角網を生成する。
図１には、第１の三角網の一例である三角網１６ａと、第２の三角網の一例である三角網１６ｂが示されている。三角網１６ａは、ドロネー三角網１５から、１つ以上の頂点が境界にある三角形を除外したものである。そのため、たとえば、ドロネー三角網１５に含まれていた三角形１５ｂ１，１５ｂ２が三角網１６ａには含まれていない。三角網１６ｂは、ドロネー三角網１５から、２つ以上の頂点が境界にある三角形を除外したものである。そのため、たとえば、ドロネー三角網１５に含まれていた三角形１５ｂ２が三角網１６ｂには含まれていないが、三角形１５ｂ１は三角網１６ｂに含まれている。
【００２４】
処理部１２は、ドロネー三角網の生成結果（三角網１６ａ，１６ｂなどの情報）を記憶部１１に記憶してもよい。ドロネー三角網の生成結果には、たとえば、三角網１６ａ，１６ｂに含まれる三角形のノード（たとえば、三角形の中心に設定される）の座標や、その三角形に隣接する三角形のノードの座標などが含まれる。
【００２５】
上記のような三角網１６ａ，１６ｂは、たとえば、ホットスポットの有無が既知のクリップ領域を教師データとして、ホットスポットの検出に用いられるそれぞれ異なる２つの欠陥識別モデルを機械学習により作成する際に用いられる（その例は後述する）。
【００２６】
前述のように微小な三角形が隣接する箇所は、ホットスポットであると認識されやすく、クリップ領域１１ｂ１の境界付近は分割された露光パターンによる微小な辺や微小な矩形領域が多く生じ、微小な三角形が多く形成される可能性がある。つまり、ホットスポットではないにもかかわらず、ホットスポットと誤検出される可能性がある。
【００２７】
上記の手法で生成された三角網１６ａ，１６ｂは、ドロネー三角網１５と比べて、クリップ領域１１ｂ１の境界付近に生成される微小な三角形の数が減少する。そのため、三角網１６ａ，１６ｂを用いてホットスポットの検出が行われる場合、ドロネー三角網１５を用いてホットスポットの検出が行われる場合よりも、境界付近でのホットスポットの誤検出の発生を抑制できる。これにより、ホットスポットの検出精度を向上できる。
【００２８】
なお、三角網１６ａ，１６ｂの何れをホットスポットの検出に用いるかについては、ホットスポットの検出に関する後述の評価処理の結果がよいものを用いればよい。結果の良し悪しは、露光パターン１１ａによって変わるためである。
【００２９】
また、上記の処理でドロネー三角網１５に含まれる複数の三角形のなかで、三角形の中心がクリップ領域の境界（たとえば、中心から最も近い境界）から所定の距離より離れている三角形は、抽出される第１の三角形群及び第２の三角形群から除外されてもよい。中心が境界から所定の距離より離れている三角形は、比較的大きい三角形になる傾向があり、このような三角形まで除外すると、ノード数が少なくなり、ホットスポット検出に用いる情報量が少なくなり、検出精度が悪化する可能性があるためである。所定の距離は、たとえば、露光パターンの基準寸法（最小配線幅）に基づいて予め決定される。たとえば、所定の距離は基準寸法の３倍などと予め決定される。なお、ホットスポットの検出に関する後述の評価処理の結果がよくなるように、上記所定の距離を変化させてもよい。
【００３０】
ところで、クリップ領域の境界にある三角形の頂点数と、三角形の中心と境界までの距離から除外対象とする三角形を決定するのではなく、クリップ領域の境界に辺が接している三角形の各辺の長さから除外対象とする三角形を決定することも考えられる。
【００３１】
その場合、まず、三角形の各辺がクリップ領域の境界に接しているか否かの判定が行われ、その後、境界に接している辺をもつ三角形の各辺の長さから、除外対象とすべき小さい三角形であるか否かの判定が行われることになる。
【００３２】
後者の判定処理は、３辺の長さの組み合わせによって、除外対象か否かの判定を行うことになるため、判定処理は複雑となる。クリップ領域の境界にある三角形の頂点数と、三角形の中心と境界までの距離から除外対象とする三角形を決定する手法は、三角形の辺を用いる手法よりも判定処理や判定条件が簡便である。そのため、計算量の増加が抑えられ、高速性が要求されるホットスポット検出において有効である。
【００３３】
以下、上記のような三角網の生成方法を用いたホットスポットの検出処理の一例を第２の実施の形態として説明する。
（第２の実施の形態）
ホットスポットの検出処理は、たとえば、以下のような情報処理装置を用いて実行される。
【００３４】
図２は、情報処理装置のハードウェア例を示すブロック図である。
情報処理装置２０は、ＣＰＵ２１、ＲＡＭ２２、ＨＤＤ２３、画像信号処理部２４、入力信号処理部２５、媒体リーダ２６及び通信インタフェース２７を有する。上記ユニットは、バスに接続されている。
【００３５】
ＣＰＵ２１は、プログラムの命令を実行する演算回路を含むプロセッサである。ＣＰＵ２１は、ＨＤＤ２３に記憶されたプログラムやデータの少なくとも一部をＲＡＭ２２にロードし、プログラムを実行する。なお、ＣＰＵ２１は複数のプロセッサコアを備えてもよく、情報処理装置２０は複数のプロセッサを備えてもよく、以下で説明する処理を複数のプロセッサまたはプロセッサコアを用いて並列に実行してもよい。
【００３６】
ＲＡＭ２２は、ＣＰＵ２１が実行するプログラムやＣＰＵ２１が演算に用いるデータを一時的に記憶する揮発性の半導体メモリである。なお、情報処理装置２０は、ＲＡＭ以外の種類のメモリを備えてもよく、複数個のメモリを備えてもよい。
【００３７】
ＨＤＤ２３は、ＯＳ（Operating System）やミドルウェアやアプリケーションソフトウェアなどのソフトウェアのプログラム、及び、データを記憶する不揮発性の記憶装置である。プログラムには、たとえば、ドロネー三角網の生成やホットスポットの検出を情報処理装置２０に実行させるプログラムが含まれる。なお、情報処理装置２０は、フラッシュメモリやＳＳＤ（Solid State Drive）などの他の種類の記憶装置を備えてもよく、複数の不揮発性の記憶装置を備えてもよい。
【００３８】
画像信号処理部２４は、ＣＰＵ２１からの命令にしたがって、情報処理装置２０に接続されたディスプレイ２４ａに画像を出力する。ディスプレイ２４ａとしては、ＣＲＴ（Cathode Ray Tube）ディスプレイ、液晶ディスプレイ（ＬＣＤ：Liquid Crystal Display）、プラズマディスプレイ（ＰＤＰ：Plasma Display Panel）、有機ＥＬ（ＯＥＬ：Organic Electro-Luminescence）ディスプレイなどを用いることができる。
【００３９】
入力信号処理部２５は、情報処理装置２０に接続された入力デバイス２５ａから入力信号を取得し、ＣＰＵ２１に出力する。入力デバイス２５ａとしては、マウスやタッチパネルやタッチパッドやトラックボールなどのポインティングデバイス、キーボード、リモートコントローラ、ボタンスイッチなどを用いることができる。また、情報処理装置２０に、複数の種類の入力デバイスが接続されていてもよい。
【００４０】
媒体リーダ２６は、記録媒体２６ａに記録されたプログラムやデータを読み取る読み取り装置である。記録媒体２６ａとして、たとえば、磁気ディスク、光ディスク、光磁気ディスク（ＭＯ：Magneto-Optical disk）、半導体メモリなどを使用できる。磁気ディスクには、フレキシブルディスク（ＦＤ：Flexible Disk）やＨＤＤが含まれる。光ディスクには、ＣＤ（Compact Disc）やＤＶＤ（Digital Versatile Disc）が含まれる。
【００４１】
媒体リーダ２６は、たとえば、記録媒体２６ａから読み取ったプログラムやデータを、ＲＡＭ２２やＨＤＤ２３などの他の記録媒体にコピーする。読み取られたプログラムは、たとえば、ＣＰＵ２１によって実行される。なお、記録媒体２６ａは、可搬型記録媒体であってもよく、プログラムやデータの配布に用いられることがある。また、記録媒体２６ａやＨＤＤ２３を、コンピュータ読み取り可能な記録媒体ということがある。
【００４２】
通信インタフェース２７は、ネットワーク２７ａに接続され、ネットワーク２７ａを介して他の情報処理装置と通信を行うインタフェースである。通信インタフェース２７は、スイッチなどの通信装置とケーブルで接続される有線通信インタフェースでもよいし、基地局と無線リンクで接続される無線通信インタフェースでもよい。
【００４３】
次に、情報処理装置２０の機能及び処理手順を説明する。
図３は、情報処理装置の機能例を示すブロック図である。
情報処理装置２０は、露光パターン記憶部３１、ドロネー三角網記憶部３２、ラベル付きノード情報記憶部３３、欠陥識別モデル情報記憶部３４を有する。また、情報処理装置２０は、取得部３５，３６、ドロネー三角網生成部３７，３８、ラベル付きノード設定部３９，４０を有する。さらに、情報処理装置２０は、除外対象三角形群設定部４１、欠陥識別モデル生成部４２、欠陥識別モデル評価部４３、欠陥識別モデル選択部４４、欠陥判定部４５、出力部４６を有する。
【００４４】
露光パターン記憶部３１、ドロネー三角網記憶部３２、ラベル付きノード情報記憶部３３、欠陥識別モデル情報記憶部３４は、たとえば、ＲＡＭ２２またはＨＤＤ２３に確保した記憶領域を用いて実装できる。
【００４５】
取得部３５，３６、ドロネー三角網生成部３７，３８、ラベル付きノード設定部３９，４０は、たとえば、ＣＰＵ２１が実行するプログラムモジュールを用いて実装できる。除外対象三角形群設定部４１、欠陥識別モデル生成部４２、欠陥識別モデル評価部４３、欠陥識別モデル選択部４４、欠陥判定部４５、出力部４６も、たとえば、ＣＰＵ２１が実行するプログラムモジュールを用いて実装できる。
【００４６】
露光パターン記憶部３１は、露光パターンを分割して生成されるＮ個のクリップ領域の集合Ｓ＝｛ｓ１，ｓ２，…，ｓＮ｝の情報を記憶する。各クリップ領域の情報は、各クリップ領域に含まれる図形の頂点座標を含む。たとえば、ｉ番目のクリップ領域ｓｉに含まれるｍ個の図形の集合Ｐ＝｛ｐｉ１，ｐｉ２，…，ｐｉｍ｝のうち、ｋ番目のｎ角形の図形ｐｉｋのｎ個の頂点座標は、｛（ｘｉｋ１，ｙｉｋ１），…，（ｘｉｋｎ，ｙｉｋｎ）｝と表せる。
【００４７】
また、露光パターン記憶部３１は、各クリップ領域に予め割り当てられた、ホットスポットの有無を示す欠陥情報を記憶する。露光パターン記憶部３１に記憶される複数のクリップ領域は、ホットスポットの有無を識別する欠陥識別モデルを生成するための教師データとして用いられる。Ｎ個のクリップ領域のそれぞれに割り当てられた欠陥情報の集合Ｈは、Ｈ＝｛ｈ１，ｈ２，…，ｈＮ｝と表せる。欠陥情報ｈ１〜ｈＮは、たとえば、ホットスポットがある場合には１、ホットスポットがない場合には０である。
【００４８】
ドロネー三角網記憶部３２は、ドロネー三角網生成部３７が生成したドロネー三角網に関する情報を記憶する。以下、ドロネー三角網を、たとえば、各三角形の中心に設定されるノード間を接続したグラフとみなし、Ｎ個のクリップ領域から生成されたグラフ群をＧ＝｛ｇ１，ｇ２，…，ｇＮ｝と表記する。ドロネー三角網記憶部３２は、グラフｇ１〜ｇＮに関する情報が記載される。グラフｇ１〜ｇＮに関する情報には、各ノードの座標や、ノード間を接続する線（以下エッジという）の両端のノード、各ノードが配置される三角形の頂点の座標などがある。
【００４９】
たとえば、ｉ番目のグラフｇｉに含まれるｓ個のノードの集合Ｖｉ＝｛ｖｉ１，ｖｉ２，…，ｖｉｓ｝のうち、ｋ番目のノードｖｉｋの座標は、（ｘｉｋ，ｙｉｋ）と表せる。また、ｉ番目のグラフｇｉに含まれるｔ個のエッジの集合Ｅｉ＝｛ｅｉ１，ｅｉ２，…，ｅｉｔ｝のうち、ｋ番目のエッジｅｉｋの両端のノードは、（ｖｉｋ１，ｖｉｋ２）と表せる。
【００５０】
さらに、ドロネー三角網記憶部３２は、露光パターン記憶部３１から取得される情報に基づいて得られるクリップ領域の境界を示す情報（以下境界情報という）を記憶する。境界情報は、たとえば、クリップ領域の４つの頂点のうち、ｘ座標とｙ座標が共に異なる２頂点の座標（たとえば、クリップ領域の左下頂点と右上頂点の座標）である。たとえば、ｉ番目のクリップ領域の境界情報Ｃｉは、Ｃｉ＝｛（ｘｉ１，ｙｉ１），（ｘｉ２，ｙｉ２）｝と表せる。
【００５１】
なお、境界情報は、露光パターン記憶部３１に予め記憶されていてもよい。
ラベル付きノード情報記憶部３３は、ラベル付きノード設定部３９において、複数のノードの各々に割り当てられたノードラベル情報を記憶する。ノードラベル情報は、複数のノードの各々の設定場所などの属性を示し、ビット列で表される。属性には、ノードが設定される三角形の辺の長さ（周囲長）や面積の情報、三角形の頂点が、配線パターンなどの図形の凹部の頂点か、凸部の頂点かを示す情報（頂点種別）、隣接する三角形がどのような三角形かを示す情報などがある。さらに、属性には、三角形の頂点のうち、クリップ領域の境界に位置する頂点の数、及び、三角形の中心がクリップ領域の境界（たとえば、中心から最も近い境界）から所定の距離ｄｔｈよりも離れているか否かを示す情報が含まれる。
【００５２】
たとえば、ｓ個のノードをもつｉ番目のグラフｇｉのノードラベル情報ｌｉは、ｌｉ＝｛ｌｉ１，ｌｉ２，…，ｌｉｓ｝と表せる。ｌｉ１〜ｌｉｓのそれぞれは、ｓ個のノードのうち対応するノードに割り当てられたノードラベル情報である。自身のノードの属性の情報と隣接するノードの属性の情報をそれぞれｑビットとすると、ノードラベル情報ｌｉ１〜ｌｉｓのそれぞれの長さは２ｑビットである。
【００５３】
欠陥識別モデル情報記憶部３４は、欠陥識別モデル選択部４４が選択した欠陥識別モデルの情報を記憶する。欠陥識別モデルの情報は、機械学習を利用して計算された、各教師データ（クリップ領域）に対応した重み値を含む。たとえば、ホットスポットがある教師データの重み値は、ホットスポットがない教師データの重み値よりも大きくなる。
【００５４】
取得部３５は、露光パターン記憶部３１に記憶されている複数のクリップ領域の情報を取得する。
ドロネー三角網生成部３７は、各クリップ領域に対して、まず、ボロノイ図を生成し、その後、複数の三角形を含むドロネー三角網を生成し、各三角形にノードを設定してグラフ群Ｇ＝｛ｇ１，ｇ２，…，ｇＮ｝を生成する。なお、ドロネー三角網生成部３７は、たとえば、逐次添加法を用いて、ボロノイ図を生成することなく、図形の各頂点座標からドロネー三角網を生成することも可能である。
【００５５】
ラベル付きノード設定部３９は、各クリップ領域に含まれる図形の頂点座標やクリップ領域の境界情報、ドロネー三角網の生成結果、距離ｄｔｈに基づいて、各ノードに各ノードの設定場所などの属性を示す上記のようなノードラベル情報を割り当てる。ノードラベル情報の割り当て方法の一例については後述する。
【００５６】
除外対象三角形群設定部４１は、欠陥識別モデル生成部４２が欠陥識別モデルを生成する際のクリップ領域間の類似度の算出の際に、計算から除外する三角形群（ノード群）を設定する。また、除外対象三角形群設定部４１は、欠陥判定部４５がホットスポットの有無を判定する際の類似度の算出の際に、計算から除外する三角形群（ノード群）を設定する。
【００５７】
たとえば、除外対象三角形群設定部４１は、クリップ領域の境界に１つ以上の頂点が位置し、かつ、三角形の中心から最も近い境界までの距離が所定の距離ｄｔｈ以下である三角形群を除外対象とする場合には、設定値ｋｄ＝１とする。一方、除外対象三角形群設定部４１は、クリップ領域の境界に２つ以上の頂点が位置し、かつ、三角形の中心から最も近い境界までの距離が所定の距離ｄｔｈ以下である三角形群を除外対象とする場合には、設定値ｋｄ＝２とする。
【００５８】
欠陥識別モデル生成部４２は、欠陥情報とノードラベル情報と設定値ｋｄとに基づいて、ホットスポットの有無が未知の露光パターンに対してホットスポットの有無を判定するための欠陥識別モデルを生成する。たとえば、欠陥識別モデル生成部４２は、機械学習を利用して以下の式（１）から各教師データに対応した重み値αｉを計算する。重み値αｉが、欠陥識別モデルを表すための情報となる。
【００５９】
【数１】
2019159905.tif 000003
【００６０】
式（１）において、ｇｉは、ホットスポットの有無が既知のＮ個のクリップ領域のうち、ｉ番目のクリップ領域に生成されたドロネー三角網によるグラフを示し、教師データとなる。ｇｊは、ホットスポットの有無が既知のＮ個のクリップ領域のうち、ｊ番目のクリップ領域に生成されたドロネー三角網によるグラフを示す。また、ｈｊは、ｊ番目のクリップ領域の欠陥情報を示し、ホットスポットがある場合には０以上、ホットスポットがない場合には０より小さくなる。
【００６１】
Ｋ（ｇｉ，ｇｊ）はグラフｇｉとグラフｇｊとの類似度を示し、ｓｉｇｎ（…）は、カッコ内の値が０より大きければ１、０であれば０、０より小さければ−１となるシグナム関数である。類似度の計算方法の例については後述する。
【００６２】
欠陥識別モデル生成部４２は、類似度Ｋ（ｇｉ，ｇｊ）が大きいほど、式（１）の右辺が、ｊ番目のクリップ領域の欠陥情報ｈｊに一致するように、重み値αｉを決定する。欠陥識別モデル生成部４２は、Ｎ個のクリップ領域のそれぞれに対応したＮ個のグラフｇ１〜ｇＮのそれぞれをグラフｇｊとして、式（１）の右辺がｊ番目のクリップ領域の欠陥情報に一致するように上記のような重み値αｉを決定する。
【００６３】
欠陥識別モデル評価部４３は、欠陥識別モデル生成部４２が生成した欠陥識別モデルに対して、たとえば、上記のＮ個のクリップ領域を適用した交差検証を行い、ホットスポットの有無の正答率を求め、正答率に基づいた評価値を算出する。欠陥識別モデル評価部４３は、設定値ｋｄ＝１に基づいて生成された欠陥識別モデルと、設定値ｋｄ＝２に基づいて生成された欠陥識別モデルのそれぞれについて、評価値を算出する。
【００６４】
欠陥識別モデル選択部４４は、設定値ｋｄ＝１に基づいて生成された欠陥識別モデルと、設定値ｋｄ＝２に基づいて生成された欠陥識別モデルのうち、評価値が他方よりも高い欠陥識別モデルを選択する。そして、欠陥識別モデル選択部４４は、選択した欠陥識別モデルにおける重み値αｉを欠陥識別モデル情報記憶部３４に記憶する。
【００６５】
取得部３６は、ホットスポットの有無が未知の露光パターンを分割した複数のクリップ領域（以下検証対象クリップ領域という）の情報を取得する。各検証対象クリップ領域の情報は、各検証対象クリップ領域に含まれる図形の頂点座標を含む。
【００６６】
なお、ホットスポットが存在する露光パターン上の領域の見逃しを防ぐため、複数の検証対象クリップ領域は、一部同じ領域を含むように、境界部分が互いに重なるように生成される。取得部３６は、複数の検証対象クリップ領域の情報を情報処理装置２０の外部から取得してもよい。複数の検証対象クリップ領域の情報がＨＤＤ２３に記憶されている場合には、取得部３６はＨＤＤ２３からそれらを取得してもよい。
【００６７】
なお、取得部３６は、露光パターンを分割した全ての検証対象クリップ領域の情報ではなく、一部の検証対象クリップ領域の情報を取得してもよい。
ドロネー三角網生成部３８は、ドロネー三角網生成部３７と同様の処理により、複数の検証対象クリップ領域のそれぞれにおいて、ドロネー三角網によるグラフを生成する。
【００６８】
ラベル付きノード設定部４０は、ラベル付きノード設定部３９と同様の処理により、グラフの各ノードにノードラベル情報を割り当てる。なお、ドロネー三角網生成部３８が生成したグラフの情報（ノードの座標や三角形の頂点の座標など）や、ラベル付きノード設定部４０が割り当てたノードラベル情報が、たとえば、ＲＡＭ２２に記憶されるようにしてもよい。
【００６９】
欠陥判定部４５は、ラベル付きノード情報記憶部３３に記憶されたノードラベル情報、欠陥識別モデルの情報、ラベル付きノード設定部４０がノードに割り当てたノードラベル情報、設定値ｋｄを受ける。そして、欠陥判定部４５は、これらの情報に基づいて、検証対象クリップ領域におけるホットスポットの有無を判定する。判定処理の一例については後述する。
【００７０】
出力部４６は、欠陥判定部４５の判定結果を出力する。出力部４６は、たとえば、判定結果を、ディスプレイ２４ａに表示させてもよいし、ＨＤＤ２３に記憶してもよいし、情報処理装置２０の外部に出力してもよい。
【００７１】
以下、図２や図３に示したような情報処理装置２０によるホットスポット検出処理の一例を説明する。なお、ホットスポットの検出処理は、以下に示すような半導体集積回路の製造工程の一工程であるレイアウト検証工程にて行われる。
【００７２】
（レイアウト検証工程の一例）
図４は、レイアウト検証工程の一例の流れを示すフローチャートである。
なお、以下では、図２や図３に示したような１つの情報処理装置２０を用いて処理が行われるものとして説明するが複数の情報処理装置を用いて以下の処理が行われるようにしてもよい。
【００７３】
情報処理装置２０において、プロセッサ２１は、たとえば、ＨＤＤ２３に格納されたプログラムを読み出してＲＡＭ２２上に展開して、図４に示すような各ステップの処理を実行する。
【００７４】
ステップＳ１０：レイアウト検証処理が開始すると、プロセッサ２１は、露光パターンにおけるホットスポット検出処理を行う。
ステップＳ１１：プロセッサ２１は、ステップＳ１０の処理によりホットスポットが検出されたか否かを判定する。ホットスポットが検出された場合には、ステップＳ１２の処理が行われ、ホットスポットが検出されない場合には、レイアウト検証工程が終了し、マスクの製造や、マスクを用いた露光工程などの半導体集積回路の製造工程が行われる。
【００７５】
ステップＳ１２：プロセッサ２１は、ユーザによる入力に基づき、露光パターンに対してＯＰＣ（Optical Proximity Correction）処理を行い、その後、ステップＳ１０の処理が再び行われる。
【００７６】
図５は、ホットスポット検出処理の一例の流れを示すフローチャートである。
ホットスポット検出処理は、図５に示すように、欠陥識別モデル生成処理（ステップＳ２０）と、ホットスポット有無判定処理（ステップＳ２１）を含む。以下、図３に示した情報処理装置２０による欠陥識別モデル生成処理とホットスポット有無判定処理の一例を説明する。
【００７７】
（欠陥識別モデル生成処理）
図６は、欠陥識別モデル生成処理の一例の流れを示すフローチャートである。
ステップＳ３０：まず、取得部３５は、露光パターン記憶部３１に記憶されている複数のクリップ領域の情報を取得する。
【００７８】
ステップＳ３１：ドロネー三角網生成部３７は、ステップＳ３０の処理で取得した各クリップ領域の情報に基づいて、各クリップ領域に対して、ドロネー三角網によるグラフを生成する。
【００７９】
ステップＳ３２：ラベル付きノード設定部３９は、各クリップ領域に含まれる図形の頂点座標、クリップ領域の境界情報、ドロネー三角網の生成結果、距離ｄｔｈに基づいて、各ノードにノードラベル情報を割り当てる。
【００８０】
ステップＳ３３：除外対象三角形群設定部４１は、欠陥識別モデル生成部４２が欠陥識別モデルの生成の際に算出するクリップ領域間の類似度の算出の際に、計算から除外する三角形群（ノード群）を設定する（設定値ｋｄを＝１または２とする）。
【００８１】
ステップＳ３４：欠陥識別モデル生成部４２は、欠陥情報とノードラベル情報と設定値ｋｄに基づいて、前述した式（１）を用いて、ホットスポットの有無が未知の露光パターンに対してホットスポットの有無を判定するための欠陥識別モデルを生成する。
【００８２】
ステップＳ３５：欠陥識別モデル評価部４３は、欠陥識別モデル生成部４２が生成した欠陥識別モデルに対して、たとえば、上記のＮ個のクリップ領域を適用した交差検証を行い、ホットスポットの有無の正答率を求め、正答率に基づいた評価値を算出する。
【００８３】
ステップＳ３６：欠陥識別モデル評価部４３は、設定値ｋｄ＝１に基づいて生成された欠陥識別モデルと、設定値ｋｄ＝２に基づいて生成された欠陥識別モデルの全てについて評価を行ったか否かを判定する。全欠陥識別モデルについての評価が終わっていない場合には、ステップＳ３３からの処理が繰り返される。全欠陥識別モデルについての評価が終わった場合には、ステップＳ３７の処理が行われる。
【００８４】
ステップＳ３７：欠陥識別モデル選択部４４は、設定値ｋｄ＝１に基づいて生成された欠陥識別モデルと、設定値ｋｄ＝２に基づいて生成された欠陥識別モデルのうち、評価値が他方よりも高い欠陥識別モデルを選択する。そして、欠陥識別モデル選択部４４は、選択した欠陥識別モデルにおける重み値αｉを欠陥識別モデル情報記憶部３４に記憶する。これにより、欠陥識別モデルの生成処理が終わる。
【００８５】
以下ステップＳ３２のノードラベル情報の割り当て処理の一例の流れを説明する。
ノードラベル情報の割り当て処理は、自身のノードの属性を示すｑビットのラベル情報を計算する処理と、隣接するノード（以下隣接ノードという）の属性を示すラベル情報を追加してノードラベル情報を生成する処理を含む。
【００８６】
図７は、自身のノードの属性を示すラベル情報の計算処理の一例の流れを示すフローチャートである。
ステップＳ４０：ラベル付きノード設定部３９は、ドロネー三角網生成部３７が生成したドロネー三角網によるグラフのうち、未選択のグラフを選択する。
【００８７】
ステップＳ４１：ラベル付きノード設定部３９は、選択したグラフに含まれるノードのうち、未選択のノードを選択する。
ステップＳ４２：ラベル付きノード設定部３９は、選択したノードが設定される三角形の頂点のうちクリップ領域の境界にある頂点数と、その三角形の中心から境界までの距離に関する情報以外のノードの属性からラベル情報を計算する。そのような属性として、三角形の頂点が、配線パターンなどの図形の凹部の頂点か、凸部の頂点かを示す情報（頂点種別）などがある。ラベル付きノード設定部３９は、このような属性を、各クリップ領域に含まれる図形の頂点座標やドロネー三角網の生成結果から計算し、ビット列に変換する。
【００８８】
たとえば、ラベル付きノード設定部３９は、上記の頂点種別が凸部の頂点のとき、“０００”、頂点種別が凹部の頂点のとき、“００１”、頂点種別が凸部と凹部の両方の頂点のとき、“０１０”、などと頂点種別をビット列に変換してもよい。複数の属性があるときには、各属性のビット列を組み合わせてラベル情報が生成される。
【００８９】
なお、どのような属性を、どのようなビット列で表すかを示す情報は、予め、たとえば、ＨＤＤ２３などに記憶されており、ラベル付きノード設定部３９は、その情報を読み出してビット列を生成することができる。
【００９０】
ステップＳ４３：ラベル付きノード設定部３９は、選択したノードが設定される三角形における、クリップ領域の境界にある頂点数をラベル情報に追加する。ラベル付きノード設定部３９は、クリップ領域の境界情報と、ドロネー三角網の生成結果に含まれる各三角形の座標に基づいて、選択したノードが設定される三角形の頂点のうちクリップ領域の境界にある頂点数を求める。そして、その頂点数を示す２ビット列をラベル情報に追加する（たとえば、下位側に追加する）。三角形の３つの頂点のうち、クリップ領域の境界にある頂点数が０の場合の２ビット列は“００”、境界にある頂点数が１の場合の２ビット列は“０１”となる。また、境界にある頂点数が２の場合の２ビット列は“１０”、境界にある頂点数が３の場合の２ビット列は“１１”となる。
【００９１】
ステップＳ４４：ラベル付きノード設定部３９は、選択したノードが設定される三角形の中心から、クリップ領域の境界（三角形の中心から最も近い境界）までの距離が距離ｄｔｈ以下なら１、それ以外の場合は０をラベル情報に追加する。ラベル付きノード設定部３９は、距離ｄｔｈと、ドロネー三角網記憶部３２に記憶されているドロネー三角網の生成結果（ノードの座標を含む）、クリップ領域の境界情報に基づいて、三角形の中心から境界までの距離が距離ｄｔｈ以下か否かを判定する。
【００９２】
距離ｄｔｈは、たとえば、露光パターンの基準寸法（最小配線幅）に基づいて予め決定される。たとえば、距離ｄｔｈは基準寸法の３倍などと予め決定される。距離ｄｔｈは、たとえば、ＨＤＤ２３に予め記憶されている。
【００９３】
距離ｄｔｈは、欠陥識別モデルの評価値がよくなるように、変更してもよい。
なお、ステップＳ４４の処理で追加される１ビットの情報は、たとえば、ステップＳ４３の処理で追加された２ビット列の下位側に追加される。
【００９４】
ステップＳ４５：ラベル付きノード設定部３９は、ステップＳ４０の処理で選択したグラフの全ノードを選択したか否かを判定する。全ノードを選択していない場合には、ステップＳ４１からの処理が繰り返され、全ノードを選択した場合には、ステップＳ４６の処理が行われる。
【００９５】
ステップＳ４６：ラベル付きノード設定部３９は、全グラフを選択したか否かを判定する。全グラフを選択していない場合には、ステップＳ４０からの処理が繰り返され、全グラフを選択した場合には、自身のノードの属性を示すラベル情報の計算処理が終了する。
【００９６】
なお、上記図７のフローチャートの各ステップの処理順序は、上記の例に限定されない。たとえば、ステップＳ４２〜Ｓ４４の処理順序は適宜入れ替えてもよい。
次に、隣接ノードの属性を示すラベル情報を追加してノードラベル情報を生成する処理の一例を説明する。
【００９７】
図８は、隣接ノードの属性を示すラベル情報を追加してノードラベル情報を生成する処理の一例の流れを示すフローチャートである。
ステップＳ５０：ラベル付きノード設定部３９は、ドロネー三角網生成部３７が生成したドロネー三角網によるグラフのうち、未選択のグラフを選択する。
【００９８】
ステップＳ５１：ラベル付きノード設定部３９は、選択したグラフに含まれるノードのうち、未選択のノードを選択する。
ステップＳ５２：ラベル付きノード設定部３９は、選択したノードの隣接ノードのラベル情報のビット列（図７の処理で計算された隣接ノード自身の属性を示すビット列）を抽出する。なお、ラベル付きノード設定部３９は、隣接ノードのラベル情報の全ビットのうち、考慮すべき一部のビット列を抽出してもよい。
【００９９】
ステップＳ５３：ラベル付きノード設定部３９は、隣接ノードが複数ある場合には、各隣接ノードのラベル情報のビット列のＸＯＲ（排他的論理和）を計算する。たとえば、ある隣接ノードのラベル情報のビット列が“０１０１”、別の隣接ノードのラベル情報のビット列が“１１０１”である場合、対応する各ビットのＸＯＲが計算され、“１０００”というビット列が得られる。
【０１００】
ステップＳ５４：ラベル付きノード設定部３９は、選択したノードのラベル情報に隣接ノードに関するラベル情報（ビット列）を追加する。ラベル付きノード設定部３９は、たとえば、まず、選択したノードのラベル情報のビット数と、追加するビット列のビット数とを合わせたビット数のノードラベル情報の上位側に、選択したノードのラベル情報を設定する。選択したノードのラベル情報のビット数と、追加するビット列のビット数とがともにｑビットである場合には、２ｑビットの上位ｑビットに選択したノードのラベル情報が設定される。この段階では、下位のｑビットは、全て“０”である。
【０１０１】
そして、ラベル付きノード設定部３９は、そのノードラベル情報と、追加するビット列とのＯＲ（論理和）を計算することで、隣接ノードに関するビット列を追加したノードラベル情報を生成する。
【０１０２】
ステップＳ５５：ラベル付きノード設定部３９は、ステップＳ５０の処理で選択したグラフの全ノードを選択したか否かを判定する。全ノードを選択していない場合には、ステップＳ５１からの処理が繰り返され、全ノードを選択した場合には、ステップＳ５６の処理が行われる。
【０１０３】
ステップＳ５６：ラベル付きノード設定部３９は、全グラフを選択したか否かを判定する。全グラフを選択していない場合には、ステップＳ５０からの処理が繰り返され、全グラフを選択した場合には、ノードラベル情報の生成処理が終了する。
【０１０４】
図９は、生成されるノードラベル情報の一例を示す図である。
図９には、２２ビットのノードラベル情報の一例が示されている。上位１１ビットは、このノードラベル情報が割り当てられるノード自身の属性を示すラベル情報であり、下位１１ビットは、図８の処理でラベル情報に追加される隣接ノードに関するビット列である。上位１１ビットと下位１１ビットのそれぞれのうち、最下位ビットには、三角形の中心がクリップ領域の境界から距離ｄｔｈ以下であるか否かを示す値が設定される。その最下位ビットの上位２ビットには、境界上に位置する三角形の頂点数が設定される。
【０１０５】
次に、図６のステップＳ３４の欠陥識別モデル生成処理で用いられる式（１）における類似度の計算処理の一例の流れを説明する。
なお、以下では、欠陥識別モデル生成部４２が、ドロネー三角網によるグラフ群Ｇ＝｛ｇ１，ｇ２，…，ｇＮ｝に含まれるグラフｇ１〜ｇＮのうちの２つのグラフの類似度を計算する例を説明する。以下では、２つのグラフのうち、一方をグラフｇａ、他方をグラフｇｂと表記する。
【０１０６】
また、グラフｇａに含まれるｎ個のノードの集合Ｖａを、Ｖａ＝｛ｖａ１，ｖａ２，…，ｖａｎ｝、グラフｇｂに含まれるｍ個のノードの集合Ｖｂを、Ｖｂ＝｛ｖｂ１，ｖｂ２，…，ｖｂｍ｝と表記する。また、グラフｇａのノードラベル情報ｌａを、ｌａ＝｛ｌａ１，ｌａ２，…，ｌａｎ｝と表記する。ｌａ１〜ｌａｎのそれぞれは、ｎ個のノードｖａ１〜ｖａｎのうち対応するノードに割り当てられたノードラベル情報である。また、グラフｇｂのノードラベル情報ｌｂを、ｌｂ＝｛ｌｂ１，ｌｂ２，…，ｌｂｍ｝と表記する。ｌｂ１〜ｌｂｍのそれぞれは、ｍ個のノードｖｂ１〜ｖｂｍのうち対応するノードに割り当てられたノードラベル情報である。
【０１０７】
また、以下では、ノードｖａ１〜ｖａｎ，ｖｂ１〜ｖｂｍは、割り当てられたノードラベル情報の値が小さい順にソートされているものとする。
図１０は、類似度の計算処理の一例の流れを示すフローチャートである。
【０１０８】
ステップＳ６０：欠陥識別モデル生成部４２は、変数ｉ，ｊ，ｃｔｏｔａｌの初期値を設定する。以下では、欠陥識別モデル生成部４２は、変数ｉ＝１、変数ｊ＝１、変数ｃｔｏｔａｌ＝０とすることで各変数の初期値の設定を行うものとする。
【０１０９】
ステップＳ６１：欠陥識別モデル生成部４２は、グラフｇａに含まれるｎ個のノードｖａ１〜ｖａｎのうち、ｉ番目のノードｖａｉが類似度計算から除外される除外対象であるか否かを判定する。欠陥識別モデル生成部４２は、前述した設定値ｋｄと、ノードｖａｉに割り当てられたノードラベル情報ｌａｉに基づいて、ノードｖａｉが除外対象であるか否かを判定する。たとえば、設定値ｋｄが１のとき、ノードｖａｉが設定される三角形の頂点数が１以上であり、その三角形の中心が境界から距離ｄｔｈ以下である場合には、ノードｖａｉは、除外対象として判定される。設定値ｋｄが２のとき、ノードｖａｉが設定される三角形の頂点数が２以上であり、その三角形の中心が境界から距離ｄｔｈ以下である場合には、ノードｖａｉは、除外対象として判定される。
【０１１０】
なお、設定値ｋｄとノードラベル情報ｌａｉに基づいて、除外対象か否かを示す判定結果として１または０を出力する関数が予め定義されている場合には、欠陥識別モデル生成部４２はその関数を用いて、上記の判定を行ってもよい。
【０１１１】
ノードｖａｉが、除外対象として判定された場合には、ステップＳ６７の処理が行われ、除外対象ではないと判定された場合には、ステップＳ６２の処理が行われる。
ステップＳ６２：欠陥識別モデル生成部４２は、ステップＳ６１と同様の処理により、グラフｇｂに含まれるｍ個のノードｖｂ１〜ｖｂｍのうち、ｊ番目のノードｖｂｊが類似度計算から除外される除外対象であるか否かを判定する。ノードｖｂｊが、除外対象として判定された場合には、ステップＳ６８の処理が行われ、除外対象ではないと判定された場合には、ステップＳ６３の処理が行われる。
【０１１２】
ステップＳ６３：欠陥識別モデル生成部４２は、ノードｖａｉに割り当てられたノードラベル情報ｌａｉの値と、ノードｖｂｊに割り当てられたノードラベル情報ｌｂｊの値が一致しているか否かを判定する。ノードラベル情報ｌａｉの値と、ノードラベル情報ｌｂｊの値とが一致している場合には、ステップＳ６４の処理が行われ、一致していない場合には、ステップＳ６６の処理が行われる。
【０１１３】
ステップＳ６４：欠陥識別モデル生成部４２は、ｃ＝ｗｅｉｇｈｔ（ｖａｉ，ｖｂｊ）を計算する。ｗｅｉｇｈｔ関数は、ノードｖａｉ，ｖｂｊの属性（ノードラベル情報）に基づいて、０から１の実数を出力する関数である。なお、ｗｅｉｇｈｔ（ｖａｉ，ｖｂｊ）は常に１であってもよい。
【０１１４】
ステップＳ６５：欠陥識別モデル生成部４２は、ｃｔｏｔａｌ＝ｃｔｏｔａｌ＋ｃを計算する。さらに、欠陥識別モデル生成部４２は、ｉ＝ｉ＋１、ｊ＝ｊ＋１とする。その後、欠陥識別モデル生成部４２は、ステップＳ６９の処理を行う。
【０１１５】
なお、ｗｅｉｇｈｔ（ｖａｉ，ｖｂｊ）が常に１の場合には、変数ｃｔｏｔａｌは、ノードラベル情報ｌａｉの値と、ノードラベル情報ｌｂｊの値とが一致した回数と等しくなる。
【０１１６】
ステップＳ６６：欠陥識別モデル生成部４２は、ノードラベル情報ｌａｉの値が、ノードラベル情報ｌｂｊの値よりも小さいか否かを判定する。ノードラベル情報ｌａｉの値が、ノードラベル情報ｌｂｊの値よりも小さい場合には、ステップＳ６７の処理が行われ、ノードラベル情報ｌａｉの値が、ノードラベル情報ｌｂｊの値よりも大きい場合には、ステップＳ６８の処理が行われる。
【０１１７】
ステップＳ６７：欠陥識別モデル生成部４２は、ｉ＝ｉ＋１としてステップＳ６９の処理に進む。
ステップＳ６８：欠陥識別モデル生成部４２は、ｊ＝ｊ＋１としてステップＳ６９の処理に進む。
【０１１８】
ステップＳ６９：欠陥識別モデル生成部４２は、ｉ＞ｎまたはｊ＞ｍであるか否かを判定する。ｉ＞ｎまたはｊ＞ｍである場合には、ステップＳ７０の処理が行われ、ｉ＞ｎでもなくｊ＞ｍでもない場合には、ステップＳ６１からの処理が繰り返される。
【０１１９】
ステップＳ７０：欠陥識別モデル生成部４２は、類似度Ｋ（ｇａ，ｇｂ）＝ｃｔｏｔａｌ／（ｎ＋ｍ−ｃｔｏｔａｌ）を算出し、類似度の計算処理を終える。
以下、類似度の算出例を説明する。
【０１２０】
なお、以下では説明を簡単にするため、グラフｇａ，ｇｂのノード数がそれぞれ４つ（すなわち、ｎ＝ｍ＝４）であるとする。また、グラフｇａのノードラベル情報ｌａ１を“０１０１０１０１０１００”、ノードラベル情報ｌａ２を“０１０１０１１１１１００”、ノードラベル情報ｌａ３を“０１１０１００１１０１０”、ノードラベル情報ｌａ４を“１１１１１１００００００”とする。また、グラフｇｂのノードラベル情報ｌｂ１を“０１０１０１０１０１００”、ノードラベル情報ｌｂ２を“０１０１０１１１１１００”、ノードラベル情報ｌｂ３を“０１１１０１０１１０００”、ノードラベル情報ｌｂ４を“０１１１１００１０１１０”とする。また、グラフｇａ，ｇｂのノードｖａ１〜ｖａ４，ｖｂ１〜ｖｂ４が何れも類似度計算の除外対象ではないとする。また、ｗｅｉｇｈｔ（ｖａｉ，ｖｂｊ）が常に１であるとする。
【０１２１】
ｉ＝１、ｊ＝１のとき、ノードラベル情報ｌａ１の値と、ノードラベル情報ｌｂ１の値が一致するため、ステップＳ６５の処理では、ｃｔｏｔａｌ＝１となる。また、ｉ＝２、ｊ＝２となる。ｉ＝２、ｊ＝２のとき、ノードラベル情報ｌａ２の値と、ノードラベル情報ｌｂ２の値が一致するため、ステップＳ６５の処理では、ｃｔｏｔａｌ＝２となる。また、ｉ＝３、ｊ＝３となる。
【０１２２】
ｉ＝３、ｊ＝３のとき、ノードラベル情報ｌａ３の値よりノードラベル情報ｌｂ３の値が大きいため、ｉ＝４となり、ｊは３のままとなる。ｉ＝４、ｊ＝３のとき、ノードラベル情報ｌａ４の値は、ノードラベル情報ｌｂ３の値より大きいため、ｊ＝４となり、ｉは４のままとなる。
【０１２３】
ｉ＝４、ｊ＝４のとき、ノードラベル情報ｌａ４の値は、ノードラベル情報ｌｂ４の値より大きいため、ｊ＝５となり、ｊ＞４となる。したがって、ステップＳ７０の処理では、Ｋ（ｇａ，ｇｂ）＝ｃｔｏｔａｌ／（ｎ＋ｍ−ｃｔｏｔａｌ）＝２／（４＋４−２）＝１／３となる。
【０１２４】
なお、グラフｇａとグラフｇｂが同じものである場合には、ｃｔｏｔａｌ＝ｎ＝ｍとなり、Ｋ（ｇａ，ｇｂ）＝１となる。
欠陥識別モデル生成部４２は、グラフ群Ｇ＝｛ｇ１，ｇ２，…，ｇＮ｝に含まれるグラフｇ１〜ｇＮのうちの２つのグラフの全組み合わせについて、類似度を上記のように求める。そして欠陥識別モデル生成部４２は、求めた類似度を、式（１）に適用して、機械学習により各教師データ（ホットスポットの有無が既知であるグラフｇ１〜ｇＮのそれぞれ）に対応した重み値αｉを計算する。欠陥識別モデル生成部４２は、計算した重み値αｉを欠陥識別モデルの情報として欠陥識別モデル情報記憶部３４に記憶する。
【０１２５】
なお、上記図１０のフローチャートの各ステップの処理順序は、上記の例に限定されない。たとえば、ステップＳ６１，Ｓ６２の処理順序は適宜入れ替えてもよい。
次に、図５に示したホットスポット有無判定処理の一例を説明する。
【０１２６】
（ホットスポット有無判定処理）
図１１は、ホットスポット有無判定処理の一例の流れを示すフローチャートである。
ステップＳ８０：取得部３６は、ホットスポットの有無が未知の露光パターンを分割した複数の検証対象クリップ領域の情報を取得する。
【０１２７】
ステップＳ８１：ドロネー三角網生成部３８は、ステップＳ８０の処理で取得した複数の検証対象クリップ領域のそれぞれにおいて、ドロネー三角網によるグラフを生成する。
ステップＳ８２：ラベル付きノード設定部４０は、前述の処理と同様の処理により、ノードラベル情報を生成する。
【０１２８】
ステップＳ８３：欠陥判定部４５は、ラベル付きノード情報記憶部３３に記憶されたノードラベル情報と、ステップＳ８２の処理で得られたノードラベル情報とに基づいて、ステップＳ８１の処理で得られたグラフと、教師データのグラフとの類似度を評価する。類似度の評価処理の例については後述する。
【０１２９】
ステップＳ８４：欠陥判定部４５は、類似度の評価結果と、欠陥識別モデルの情報とに基づいて、検証対象クリップ領域にホットスポットがあるか否かを判定する。判定処理の例については後述する。
【０１３０】
ステップＳ８５：出力部４６は、欠陥判定部４５の判定結果を出力する。
以下、ステップＳ８３，Ｓ８４の処理の一例の流れを説明する。なお、以下では、Ｎ個のクリップ領域から生成されたグラフ群Ｇ＝｛ｇ１，ｇ２，…，ｇＮ｝に対して、Ｍ個の検証対象クリップ領域から生成されたグラフ群をＧａ＝｛ｇａ１，ｇａ２，…，ｇａＭ｝と表記する。
【０１３１】
図１２は、類似度の評価処理の一例の流れを示すフローチャートである。
ステップＳ９０：欠陥判定部４５は、グラフ群Ｇａ＝｛ｇａ１，ｇａ２，…，ｇａＭ｝から、未選択のグラフｇａｊを選択する。
【０１３２】
ステップＳ９１：欠陥判定部４５は、グラフ群Ｇ＝｛ｇ１，ｇ２，…，ｇＮ｝から、未選択のグラフｇｉを選択する。
ステップＳ９２：欠陥判定部４５は、選択したグラフｇａｊと、グラフｇｉの類似度Ｋ（ｇａｊ，ｇｉ）を計算する。類似度Ｋ（ｇａｊ，ｇｉ）は、ラベル付きノード情報記憶部３３に記憶されたノードラベル情報と、ステップＳ８２の処理で得られたノードラベル情報とに基づいて、図１０に示した処理によって算出することができる。
【０１３３】
ステップＳ９３：欠陥判定部４５は、グラフ群Ｇの全てのグラフとグラフｇａｊの類似度を計算したか否かを判定する。グラフ群Ｇの全てのグラフとグラフｇａｊの類似度を計算した場合には、ステップＳ９４の処理が行われ、グラフ群Ｇの全てのグラフとグラフｇａｊの類似度を計算していない場合には、ステップＳ９１からの処理が繰り返される。
【０１３４】
ステップＳ９４：欠陥判定部４５は、類似度Ｋ（ｇａｊ，ｇｉ）の値が大きい上位ｒ（１以上の所定の整数）個のグラフｇｉとその類似度Ｋ（ｇａｊ，ｇｉ）の値とを、たとえば、ＲＡＭ２２またはＨＤＤ２３に記憶する。
【０１３５】
ステップＳ９５：欠陥判定部４５は、グラフ群Ｇａの全てのグラフを選択したか否かを判定する。グラフ群Ｇａの全てのグラフを選択した場合には、類似度の評価処理が終了し、グラフ群Ｇａの全てのグラフを選択していない場合には、ステップＳ９０からの処理が繰り返される。
【０１３６】
図１３は、ホットスポットの有無の判定処理の一例の流れを示すフローチャートである。
ステップＳ１００：欠陥判定部４５は、グラフ群Ｇａ＝｛ｇａ１，ｇａ２，…，ｇａＭ｝から、未選択のグラフｇａｊを選択する。
【０１３７】
ステップＳ１０１：欠陥判定部４５は、グラフｇａｊが生成された検証対象クリップ領域にホットスポットがあるか否かを判定する。欠陥判定部４５は、欠陥識別モデルの情報（重み値αｉ）と、類似度Ｋ（ｇａｊ，ｇｉ）とを、以下の式（２）に代入することで、ホットスポットの有無を判定する。
【０１３８】
【数２】
2019159905.tif 000004
【０１３９】
式（２）において、ｆ（ｇａｊ）が０以上のときは、グラフｇａｊが生成された検証対象クリップ領域にホットスポットがあることを示し、ｆ（ｇａｊ）が０より小さいときは、グラフｇａｊが生成された検証対象クリップ領域にホットスポットがないことを示す。
【０１４０】
なお、欠陥判定部４５は、グラフｇ１〜ｇａＮの全てと、グラフｇａｊとの類似度を用いなくてもよく、グラフｇ１〜ｇａＮのうち、グラフｇａｊとの類似度が大きい上位ｒ個のグラフとグラフｇａｊとの類似度以外は用いなくてもよい。
【０１４１】
ステップＳ１０２：欠陥判定部４５は、ホットスポットの有無の判定結果を、たとえば、ＲＡＭ２２またはＨＤＤ２３に記憶する。
ステップＳ１０３：欠陥判定部４５は、グラフ群Ｇａの全てのグラフを選択したか否かを判定する。グラフ群Ｇａの全てのグラフを選択した場合には、ホットスポットの有無の判定処理が終了し、グラフ群Ｇａの全てのグラフを選択していない場合には、ステップＳ１００からの処理が繰り返される。
【０１４２】
なお、図１１のステップＳ８５の処理において、出力部４６は、上記のホットスポットの有無の判定結果を、ディスプレイ２４ａに表示させてもよい。
図１４は、ホットスポットの有無の判定結果の表示例を示す図である。
【０１４３】
画面５０には、検証対象クリップ領域５１を図示したものと、検証対象クリップ領域５１の名前、ホットスポットの判定結果（図１４の例では“あり”と表示されている）が表示されている。さらに、検証対象クリップ領域５１との類似度が大きい上位４つのクリップ領域５２，５３，５４，５５（つまり、検証対象クリップ領域５１から得られるグラフとの類似度が大きい上位４つのグラフが生成されるクリップ領域）の名前と、類似度が表示されている。なお、クリップ領域５２〜５５（またはクリップ領域５２〜５５から得られるグラフ）は、ホットスポットの有無が既知である教師データである。
【０１４４】
以上のような第２の実施の形態のホットスポットの検出処理では、図１０に示したステップＳ６１，Ｓ６２の判定処理によって類似度計算から除外されるノードが判定され、そのノードのノードラベル情報を用いずに類似度計算が行われる。つまり、実質的に、その除外対象のノードが設定される三角形が抽出され、そのような三角形による三角形群が除外された三角網が生成され、その三角網に対して類似度計算が行われることに相当する処理が行われる。つまり、第１の実施の形態の三角網の生成方法と実質的に同様の処理が行われている。
【０１４５】
このため、クリップ領域または検証対象クリップ領域の境界付近に生成され、ホットスポットの誤検出の要因となる微小な三角形の数を実質的に減少でき、境界付近でのホットスポットの誤検出の発生を抑制できる。これにより、ホットスポットの検出精度を向上できる。また、設定値ｋｄ＝１，２の両方の値に基づいて生成された欠陥識別モデルのうち、何れの評価値が高くなるかについては、露光パターンによって変わる可能性がある。そのため、評価値が高い方を選択してホットスポットを検出することで、様々な露光パターンに対して、検出精度のよりよいホットスポットの検出を行うことができる。
【０１４６】
また、図１０に示したステップＳ６１，Ｓ６２の判定処理では、中心がクリップ領域の境界（たとえば、中心から最も近い境界）から所定の距離ｄｔｈよりも離れている三角形のノードについては類似度計算の除外対象とはならない。中心が境界から所定の距離より離れている三角形は、比較的大きい三角形になる傾向があるため、そのような三角形のノードまで除外するとノード数が少なくなり、ホットスポット検出に用いる情報量が少なくなり、検出精度が悪化する可能性があるためである。
【０１４７】
図１５は、ドロネー三角網と一部の三角形群を除外した三角網の一例を示す図である。
図１５には、クリップ領域６０に生成されたドロネー三角網６１が示されている。このようなドロネー三角網６１から、距離ｄｔｈを考慮せず、単にクリップ領域６０の境界に１つ以上の頂点がある三角形を除外した三角網６１ａを生成した場合、比較的広い領域６２には、計算に用いられる三角形のノードがなくなる。
【０１４８】
そこで、中心がクリップ領域６０の境界から所定の距離ｄｔｈよりも離れている三角形（第２の実施の形態では、その三角形に設定されたノード）については、除外対象（第２の実施の形態では類似度計算の除外対象）として抽出されない。たとえば、図１５に示すような中心からクリップ領域６０までの距離ｄが距離ｄｔｈよりも大きい三角形６３については、除外対象として抽出されない。これにより、類似度計算に用いられるドロネー三角網は、実質的に三角網６１ｂのようになる。なお、図１５のドロネー三角網６１の例では、境界に１つ以上の頂点がある三角形であり、かつ、ｄ≦ｄｔｈとなる三角形が存在しないため、三角網６１ｂは、ドロネー三角網６１と同じとなっている。
【０１４９】
このように、比較的大きい三角形を除外対象としないようにすることで、ホットスポット検出に用いる情報量が少なくなることを抑制でき、より精度よくホットスポットの検出を行うことができる。
【０１５０】
また、除外対象とする三角形（第２の実施の形態では、その三角形に設定されたノード）をステップＳ６１，Ｓ６２の判定処理で決定する際に、欠陥識別モデル生成部４２や欠陥判定部４５は、ノードラベル情報に設定されたビット列を参照すればよい。そのため、類似度計算の高速性が損なわれることを抑制できる。
【０１５１】
なお、ドロネー三角網生成部３７，３８が、予め図１０に示したステップＳ６１，Ｓ６２の判定処理と同様の処理により、除外対象となる三角形群を抽出し、その三角形群をドロネー三角網から除いた三角網を生成してもよい。その場合、除外される三角形に設定されるノードの情報は、たとえば、ドロネー三角網記憶部３２から削除される。
【０１５２】
なお、前述のように、上記の処理内容は、情報処理装置２０にプログラムを実行させることで実現できる。
プログラムは、コンピュータ読み取り可能な記録媒体（たとえば、記録媒体２６ａ）に記録しておくことができる。記録媒体として、たとえば、磁気ディスク、光ディスク、光磁気ディスク、半導体メモリなどを使用できる。磁気ディスクには、ＦＤ及びＨＤＤが含まれる。光ディスクには、ＣＤ、ＣＤ−Ｒ（Recordable）／ＲＷ（Rewritable）、ＤＶＤ及びＤＶＤ−Ｒ／ＲＷが含まれる。プログラムは、可搬型の記録媒体に記録されて配布されることがある。その場合、可搬型の記録媒体から他の記録媒体（たとえば、ＨＤＤ２３）にプログラムをコピーして実行してもよい。
【０１５３】
以上、実施の形態に基づき、本発明の生成プログラム、生成装置及び生成方法の一観点について説明してきたが、これらは一例にすぎず、上記の記載に限定されるものではない。
【符号の説明】
【０１５４】
１０  生成装置
１１  記憶部
１１ａ  露光パターン
１１ｂ１〜１１ｂｎ  クリップ領域
１２  処理部
１５  ドロネー三角網
１５ａ１，１５ａ２  ノード
１５ｂ１，１５ｂ２  三角形
１５ｃ  図形
１６ａ，１６ｂ  三角網
【図１】
2019159905.tif 000005
【図２】
2019159905.tif 000006
【図３】
2019159905.tif 000007
【図４】
2019159905.tif 000008
【図５】
2019159905.tif 000009
【図６】
2019159905.tif 000010
【図７】
2019159905.tif 000011
【図８】
2019159905.tif 000012
【図９】
2019159905.tif 000013
【図１０】
2019159905.tif 000014
【図１１】
2019159905.tif 000015
【図１２】
2019159905.tif 000016
【図１３】
2019159905.tif 000017
【図１４】
2019159905.tif 000018
【図１５】
2019159905.tif 000019