(57)【要約】【課題】集積回路のパターン形成工程で生じる欠陥箇所の有無を短時間で精度よく判定する。【解決手段】集積回路のレイアウトパターンにおける複数の頂点のそれぞれの位置と属性とに基づいて、レイアウトパターン上で前記欠陥箇所が生じる可能性の高い位置を、欠陥箇所候補として抽出し、抽出した欠陥箇所候補を中心とする領域を、欠陥箇所判定領域としてレイアウトパターンから切り出し、切り出した欠陥箇所判定領域と記憶部に記憶され欠陥箇所の有無の判定に用いられる判定情報とに基づいて、欠陥箇所判定領域における欠陥箇所の有無を判定する。【選択図】図４
2016212539.tif 000002
【特許請求の範囲】
【請求項１】
集積回路のパターン形成工程で生じる欠陥箇所の有無を判定する処理部と、
前記欠陥箇所の有無の判定に用いられる判定情報を記憶する記憶部と、を有し、
前記処理部は、
前記集積回路のレイアウトパターンにおける複数の頂点のそれぞれの位置と属性とに基づいて、前記レイアウトパターン上で前記欠陥箇所が生じる可能性の高い位置を、欠陥箇所候補として抽出し、
抽出した前記欠陥箇所候補を中心とする領域を、欠陥箇所判定領域として前記レイアウトパターンから切り出し、
切り出した欠陥箇所判定領域と前記記憶部に記憶された前記判定情報とに基づいて、前記欠陥箇所判定領域における前記欠陥箇所の有無を判定する、情報処理装置。
【請求項２】
前記処理部は、
前記欠陥箇所候補を抽出する際、
前記複数の頂点を複数のクラスタに分割し、
前記複数のクラスタのそれぞれの中心位置を、各クラスタに属する頂点の位置と属性とに基づいて算出し、
前記各クラスタに属する各頂点の位置と当該クラスタ以外の他クラスタの中心位置との距離に応じて前記各頂点を当該クラスタから前記他クラスタへ移動させることで、近接する頂点どうしが同一クラスタに属するように前記複数の頂点のクラスタリングを行ない、
前記クラスタリングによって得られたクラスタ毎に、当該クラスタに属する頂点の密集度を算出し、
算出した密集度に応じて、当該クラスタの中心位置が前記欠陥箇所候補であるか否かを判定する、請求項１に記載の情報処理装置。
【請求項３】
前記処理部は、
処理対象頂点の属性が前記レイアウトパターンにおける凹頂点である場合の重みを、前記処理対象頂点の属性が前記凹頂点以外である場合の重みよりも大きく設定し、
設定した重みによる重み付けを、前記各クラスタに属する頂点の位置に対し行なって、前記中心位置を算出する、請求項２に記載の情報処理装置。
【請求項４】
前記処理部は、
前記レイアウトパターンを格子状に分割することで、前記複数のクラスタを生成する、請求項２または３に記載の情報処理装置。
【請求項５】
前記処理部によって分割される前記レイアウトパターンの格子サイズは、前記パターン形成工程での露光強度が所定値以上になる範囲に基づいて決定される、請求項４に記載の情報処理装置。
【請求項６】
前記処理部は、
前記中心位置の算出と前記クラスタリングとを、前記クラスタ間での前記各頂点の移動が無くなるまで繰り返し実行する、請求項２〜請求項５のいずれか一項に記載の情報処理装置。
【請求項７】
前記処理部は、
前記中心位置の算出と前記クラスタリングとを所定回数繰り返し実行しても前記クラスタ間での前記各頂点の移動が行なわれる場合、前記中心位置の算出と前記クラスタリングとを終了する、請求項６に記載の情報処理装置。
【請求項８】
前記欠陥箇所候補を中心とする領域のサイズは、前記パターン形成工程での露光強度が所定値以上になる範囲に基づいて決定される、請求項１〜請求項７のいずれか一項に記載の情報処理装置。
【請求項９】
集積回路のパターン形成工程で生じる欠陥箇所の有無を判定するコンピュータに、
前記集積回路のレイアウトパターンにおける複数の頂点のそれぞれの位置と属性とに基づいて、前記レイアウトパターン上で前記欠陥箇所が生じる可能性の高い位置を、欠陥箇所候補として抽出し、
抽出した前記欠陥箇所候補を中心とする領域を、欠陥箇所判定領域として前記レイアウトパターンから切り出し、
切り出した欠陥箇所判定領域と記憶部に記憶され前記欠陥箇所の有無の判定に用いられる判定情報とに基づいて、前記欠陥箇所判定領域における前記欠陥箇所の有無を判定する
処理を実行させる、欠陥箇所判定プログラム。
【請求項１０】
コンピュータにより、集積回路のパターン形成工程で生じる欠陥箇所の有無を判定する欠陥箇所判定方法であって、
前記集積回路のレイアウトパターンにおける複数の頂点のそれぞれの位置と属性とに基づいて、前記レイアウトパターン上で前記欠陥箇所が生じる可能性の高い位置を、欠陥箇所候補として抽出し、
抽出した前記欠陥箇所候補を中心とする領域を、欠陥箇所判定領域として前記レイアウトパターンから切り出し、
切り出した欠陥箇所判定領域と記憶部に記憶され前記欠陥箇所の有無の判定に用いられる判定情報とに基づいて、前記欠陥箇所判定領域における前記欠陥箇所の有無を判定する、欠陥箇所判定方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本件は、情報処理装置、欠陥箇所判定プログラム、および欠陥箇所判定方法に関する。
【背景技術】
【０００２】
近年、ＬＳＩ（Large Scale Integration）等の集積回路の高集積化に伴い、リソグラフィ工程において、レイアウトパターンをウエハ上で寸法通りに露光できない箇所が生じる場合がある。図１１（Ａ）に示すオリジナルパターンをウエハ上に転写した場合、図１１（Ｂ）に示すように、光近接効果（Optical Proximity Effect）により、オリジナルパターンを忠実にウエハ上に転写することができない。場合によっては、配線のパターンが細くなって断線したり、逆に配線のパターンが太くなってショートしたり、といった製造不良が生じる。このような製造不良の発生する可能性の高い箇所のことを、以下「欠陥箇所」もしくは「ホットスポット」と呼ぶ。
【０００３】
ホットスポットの発生を回避しオリジナルパターンを忠実にウエハ上に転写すべく、一般に、オリジナルパターンに対し、予め、光近接効果による劣化を見込んだ補正、いわゆるＯＰＣ（Optical Proximity Correction）を施すことが行なわれている。図１２（Ａ）は、図１１（Ａ）に示すオリジナルパターンに対しＯＰＣを施した例を示している。図１２（Ａ）に示すオリジナルパターンをウエハ上に転写すると、ウエハ上では図１２（Ｂ）に示すようなパターンが形成される。
【０００４】
ここで、ホットスポットの発生に影響を与える領域は、露光装置によって照射される光の強度が所定値以上の領域であると考えられる。例えば、図１３（Ａ）に示すように露光強度が所定値以上の領域の長さ（径）をＬとすると、図１３（Ｂ）に示すように、一辺がＬの正方形領域が、ホットスポットｘの発生に影響を与える領域となる。当該領域内でホットスポットｘが発生するか否かは、当該領域内のレイアウトパターンの形状に依存する。
【０００５】
このとき、当該領域内のレイアウトパターンの形状によっては、例えば図１４に示すように、ＯＰＣを施してもホットスポットの発生を回避することができない場合がある。図１４に示す例では、２つのパターンｐ１，ｐ２のそれぞれに対してＯＰＣを施すことにより、外形線ｐ１′，ｐ２′をもつ２つの補正パターンが形成され、これらの補正パターンの間にホットスポットｘが発生している。
【０００６】
このため、ＯＰＣを施す前にホットスポット（欠陥箇所，危険箇所）を予測し、設計段階でホットスポットの発生を回避することが望まれる。配線後のレイアウトパターンからホットスポットを予測する手法としては以下のような手法［１］〜［４］が挙げられる。
【０００７】
ＬＳＩチップ等のレイアウトパターンは一辺が数mm程度の矩形領域を有している。手法［１］では、当該矩形領域を、一辺が数μm程度の複数の小領域（小矩形領域）に分割し、分割した小領域毎にホットスポットの有無を判定する。小領域毎のホットスポット判定に際しては、例えばパターンマッチングや機械学習が用いられる。その際、配線密度の低い小領域やパターン数の少ない小領域など、明らかにホットスポットの無い小領域を判定対象から除外した上で、パターンマッチングや機械学習によるエラー識別などを用いて、小領域毎のホットスポット判定が行なわれる。上述のように矩形領域を小領域に分割する場合、ホットスポット判定の精度は、小領域の境界位置（分割位置）に依存する。例えば、小領域の中央付近に位置するホットスポットは認識判定することができても、小領域の境界上や境界付近に位置するホットスポットは認識判定できない場合がある。このため、小領域の境界をシフトさせ異なる境界位置で分割した小領域を複数組生成し、生成した小領域の組毎にホットスポット判定を行なうことが考えられる。
【０００８】
手法［２］では、各パターンの頂点にマークを配置し、配置したマークをほぼ中心としてＯＰＣの影響が強く及ぶパターンについて、危険箇所であるか否かの判定を行なう（特許文献１）。その際、上述した手法［１］と同様、レイアウトパターンに対して設定されるグリッド（格子）をシフトさせ、複数種類のグリッド（グループ分け）を生成し、生成したグリッド毎に上記判定を行なうことで、危険箇所の抽出もれを抑止することが可能である。
【０００９】
手法［３］では、レイアウトパターンを格子状のメッシュに分割し、各メッシュ内のパターンがリソグラフィエラーになるか否かの判定を行なう（特許文献２）。この手法［３］でも、メッシュ位置によっては危険箇所を見逃す可能性があるため、上述した手法［１］と同様、複数の異なる位置のメッシュを用意し、用意したメッシュ毎に上記判定を行なうことが考えられる。
【００１０】
手法［４］では、ウインドウ内をスキャンして領域を切り出し、切り出した領域内のパターンとデータベース上のエラーパターンとのパターンマッチングを行なうことにより、ホットスポットの有無を判定する（特許文献３）。この手法［４］でも、ウインドウの境界位置（格子位置）によるホットスポットの見逃しを防ぐために、ウインドウ境界をずらす手段が開示されている。
【先行技術文献】
【特許文献】
【００１１】
【特許文献１】特開２００６−１２６７４５号公報
【特許文献２】特開２００７−２９２９８３号公報
【特許文献３】米国特許出願公開第２００９／０２７１７４９号明細書
【発明の概要】
【発明が解決しようとする課題】
【００１２】
上述したように、手法［１］〜［４］では、基本的に、レイアウトパターンを格子状の小領域に分割するかレイアウトパターンからウインドウを切り出す処理を行なってから、分割した小領域毎またはウインドウ毎にホットスポット判定処理を行なうという、二段階の処理が行なわれる。
【００１３】
前段の処理では、格子分割もしくはウインドウ切出しを基本としているが、特許文献１〜３等には詳細な分割手法やウィンドウ切出し手法については開示されていない。また、格子分割やウィンドウ切出しを行なう場合、ホットスポットの判定精度を向上させホットスポットの見逃しを回避するためには、格子分割の位置やウィンドウの位置をずらしながらホットスポット判定を行なうことになる。このため、後段の処理でのホットスポット判定の対象になる小領域またはウィンドウの数が増大し、ホットスポット判定に要する処理時間が増大する。
【００１４】
１つの側面では、本件明細書に開示の発明は、集積回路のパターン形成工程で生じる欠陥箇所の有無を短時間で精度よく判定することを目的とする。
【課題を解決するための手段】
【００１５】
本件の情報処理装置は、集積回路のパターン形成工程で生じる欠陥箇所の有無を判定する処理部と、前記欠陥箇所の有無の判定に用いられる判定情報を記憶する記憶部と、を有する。前記処理部は、以下の処理（１）〜（３）を行なう。
（１）前記集積回路のレイアウトパターンにおける複数の頂点のそれぞれの位置と属性とに基づいて、前記レイアウトパターン上で前記欠陥箇所が生じる可能性の高い位置を、欠陥箇所候補として抽出する処理。
（２）抽出した前記欠陥箇所候補を中心とする領域を、欠陥箇所判定領域として前記レイアウトパターンから切り出す処理。
（３）切り出した欠陥箇所判定領域と前記記憶部に記憶された前記判定情報とに基づいて、前記欠陥箇所判定領域における前記欠陥箇所の有無を判定する処理。
【発明の効果】
【００１６】
一実施形態によれば、集積回路のパターン形成工程で生じる欠陥箇所の有無を短時間で精度よく判定することができる。
【図面の簡単な説明】
【００１７】
【図１】本発明の一実施形態としての欠陥箇所判定機能を有する情報処理装置の機能構成の一例を示すブロック図である。
【図２】本発明の一実施形態としての欠陥箇所判定機能を実現する情報処理装置のハードウェア構成の一例を示すブロック図である。
【図３】本実施形態の欠陥箇所判定動作における処理の流れおよびデータの流れを説明する図である。
【図４】本実施形態の欠陥箇所判定動作を説明するフローチャートである。
【図５】外部から入力されるレイアウトパターンの図形データの例を示す図である。
【図６】本実施形態において生成される頂点リストの例を示す図である。
【図７】本実施形態の属性／重み対応表の例を示す図である。
【図８】本実施形態におけるクラスタリング処理を説明するフローチャートである。
【図９】（Ａ）は本実施形態で生成される初期クラスタの例を示す図、（Ｂ）は（Ａ）に示す初期クラスタに対し本実施形態のクラスタリング処理を実行して得られるクラスタの例を示す図である。
【図１０】（Ａ）は一般的手法によって切り出されるホットスポット判定対象のウインドウの例を示す図、（Ｂ）は本実施形態の手法によって切り出されるホットスポット判定対象のウインドウの例を示す図である。
【図１１】（Ａ）および（Ｂ）はホットスポットを説明する図である。
【図１２】（Ａ）および（Ｂ）はＯＰＣを説明する図である。
【図１３】（Ａ）および（Ｂ）はホットスポットの発生に影響を与える領域を説明する図である。
【図１４】ＯＰＣによってホットスポットの発生を回避できないレイアウトパターンの例を示す図である。
【発明を実施するための形態】
【００１８】
以下に、図面を参照し、本願の開示する情報処理装置、欠陥箇所判定プログラム、および欠陥箇所判定方法の実施形態について、詳細に説明する。ただし、以下に示す実施形態は、あくまでも例示に過ぎず、実施形態で明示しない種々の変形例や技術の適用を排除する意図はない。すなわち、本実施形態を、その趣旨を逸脱しない範囲で種々変形して実施することができる。また、各図は、図中に示す構成要素のみを備えるという趣旨ではなく、他の機能を含むことができる。そして、各実施形態は、処理内容を矛盾させない範囲で適宜組み合わせることが可能である。
【００１９】
〔１〕欠陥箇所判定機能を実現する本実施形態の情報処理装置のハードウェア構成
まず、図２を参照しながら、本実施形態の欠陥箇所判定機能を実現する情報処理装置（コンピュータ）１０のハードウェア構成について説明する。図２は、当該ハードウェア構成の一例を示すブロック図である。
【００２０】
コンピュータ１０は、例えば、プロセッサ１１，ＲＡＭ（Random Access Memory）１２，ＨＤＤ（Hard Disk Drive）１３，グラフィック処理装置１４，入力インタフェース１５，光学ドライブ装置１６，機器接続インタフェース１７およびネットワークインタフェース１８を構成要素として有する。これらの構成要素１１〜１８は、バス１９を介して相互に通信可能に構成される。
【００２１】
プロセッサ（処理部）１１は、コンピュータ１０全体を制御する。プロセッサ１１は、マルチプロセッサであってもよい。プロセッサ１１は、例えばＣＰＵ（Central Processing Unit），ＭＰＵ（Micro Processing Unit），ＤＳＰ（Digital Signal Processor），ＡＳＩＣ（Application Specific Integrated Circuit），ＰＬＤ（Programmable Logic Device），ＦＰＧＡ（Field Programmable Gate Array）のいずれか一つであってもよい。また、プロセッサ１１は、ＣＰＵ，ＭＰＵ，ＤＳＰ，ＡＳＩＣ，ＰＬＤ，ＦＰＧＡのうちの２種類以上の要素の組み合わせであってもよい。
【００２２】
ＲＡＭ（記憶部）１２は、コンピュータ１０の主記憶装置として使用される。ＲＡＭ１２には、プロセッサ１１に実行させるＯＳ（Operating System）プログラムやアプリケーションプログラムの少なくとも一部が一時的に格納される。また、ＲＡＭ１２には、プロセッサ１１による処理に必要な各種データが格納される。アプリケーションプログラムには、コンピュータ１０によって本実施形態の欠陥箇所判定機能を実現するためにプロセッサ１１によって実行される欠陥箇所判定プログラム（図１の符号３１参照）が含まれてもよい。
【００２３】
ＨＤＤ（記憶部）１３は、内蔵したディスクに対して、磁気的にデータの書き込み及び読み出しを行なう。ＨＤＤ１３は、コンピュータ１０の補助記憶装置として使用される。ＨＤＤ１３には、ＯＳプログラム，アプリケーションプログラム、及び各種データが格納される。なお、補助記憶装置としては、フラッシュメモリ等の半導体記憶装置（ＳＳＤ：Solid State Drive）を使用することもできる。
【００２４】
グラフィック処理装置１４には、モニタ１４ａが接続されている。グラフィック処理装置１４は、プロセッサ１１からの命令に従って、画像をモニタ１４ａの画面に表示させる。モニタ１４ａとしては、ＣＲＴ（Cathode Ray Tube）を用いた表示装置や液晶表示装置等が挙げられる。
【００２５】
入力インタフェース１５には、キーボード１５ａおよびマウス１５ｂが接続されている。入力インタフェース１５は、キーボード１５ａやマウス１５ｂから送られてくる信号をプロセッサ１１に送信する。なお、マウス１５ｂは、ポインティングデバイスの一例であり、他のポインティングデバイスを使用することもできる。他のポインティングデバイスとしては、タッチパネル，タブレット，タッチパッド，トラックボール等が挙げられる。
【００２６】
光学ドライブ装置１６は、レーザ光等を利用して、光ディスク１６ａに記録されたデータの読み取りを行なう。光ディスク１６ａは、光の反射によって読み取り可能にデータを記録された可搬型の非一時的な記録媒体である。光ディスク１６ａには、ＤＶＤ（Digital Versatile Disc），ＤＶＤ−ＲＡＭ，ＣＤ−ＲＯＭ（Compact Disc Read Only Memory），ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等が挙げられる。
【００２７】
機器接続インタフェース１７は、コンピュータ１０に周辺機器を接続するための通信インタフェースである。例えば、機器接続インタフェース１７には、メモリ装置１７ａやメモリリーダライタ１７ｂを接続することができる。メモリ装置１７ａは、機器接続インタフェース１７との通信機能を搭載した非一時的な記録媒体、例えばＵＳＢ（Universal Serial Bus）メモリである。メモリリーダライタ１７ｂは、メモリカード１７ｃへのデータの書き込み、またはメモリカード１７ｃからのデータの読み出しを行なう。メモリカード１７ｃは、カード型の非一時的な記録媒体である。
【００２８】
ネットワークインタフェース１８は、ネットワーク１８ａに接続される。ネットワークインタフェース１８は、ネットワーク１８ａを介して、他のコンピュータまたは通信機器との間でデータの送受信を行なう。
【００２９】
以上のようなハードウェア構成を有するコンピュータ１０によって、図３〜図１０を参照しながら後述する本実施形態の欠陥箇所判定機能を実現することができる。
なお、コンピュータ１０は、例えばコンピュータ読み取り可能な非一時的な記録媒体に記録されたプログラム（欠陥箇所判定プログラム等）を実行することにより、本実施形態の欠陥箇所判定機能を実現する。コンピュータ１０に実行させる処理内容を記述したプログラムは、様々な記録媒体に記録しておくことができる。例えば、コンピュータ１０に実行させるプログラムをＨＤＤ１３に格納しておくことができる。プロセッサ１１は、ＨＤＤ１３内のプログラムの少なくとも一部をＲＡＭ１２にロードし、ロードしたプログラムを実行する。
【００３０】
また、コンピュータ１０（プロセッサ１１）に実行させるプログラムを、光ディスク１６ａ，メモリ装置１７ａ，メモリカード１７ｃ等の非一時的な可搬型記録媒体に記録しておくこともできる。可搬型記録媒体に格納されたプログラムは、例えばプロセッサ１１からの制御により、ＨＤＤ１３にインストールされた後、実行可能になる。また、プロセッサ１１が、可搬型記録媒体から直接プログラムを読み出して実行することもできる。
【００３１】
〔２〕欠陥箇所判定機能を有する本実施形態の情報処理装置の機能構成
次に、図１を参照しながら、本実施形態の欠陥箇所判定機能を有する情報処理装置（コンピュータ）１０の機能構成について説明する。図１は、当該機能構成の一例を示すブロック図である。
【００３２】
コンピュータ１０は、ＬＳＩ等の集積回路のレイアウトパターン３２について、パターン形成工程で生じるホットスポット、特にリソグラフィ工程で光近接効果により生じるホットスポットの、有無を判定し、当該ホットスポットの位置と重要度とを出力する機能を果たす。このため、コンピュータ１０は、図１に示すように、少なくとも処理部２０，記憶部３０，入力部４０および表示部５０としての機能を有している。
【００３３】
処理部２０は、例えば図２に示すようなプロセッサ１１であり、上述した欠陥箇所判定プログラム３１を実行することで、後述する頂点リスト生成部２１，ホットスポット候補抽出部２２，ウインドウリスト生成部２３，ホットスポット判定部２４としての機能を果たす。
【００３４】
記憶部３０は、例えば図２に示すようなＲＡＭ１２，ＨＤＤ１３であり、欠陥箇所判定機能を実現するための各種情報を記憶し保存する。当該各種情報としては、上述した欠陥箇所判定プログラム３１のほか、レイアウトパターン３２，頂点リスト３３，属性／重み対応表３４，ウインドウリスト３５，ホットスポット判定用ＤＢ（データベース）３６，
ホットスポット情報３７などが含まれる。
【００３５】
レイアウトパターン３２は、外部から入力されるホットスポットの有無の判定対象であり、例えば図５を参照しながら後述するような図形データである。当該レイアウトパターン３２は、光ディスク１６ａまたはメモリ装置１７ａまたはメモリカード１７ｃまたはネットワーク１８ａから入力されてもよい。なお、以下では、レイアウトパターンを、図形データまたはレイアウト図形データという場合がある。
【００３６】
頂点リスト３３は、後述するごとく頂点リスト生成部２１によってレイアウトパターン３２から生成される。頂点リスト３３においては、例えば図６を参照しながら後述するごとく、図形データ３２に含まれる多角形の各頂点について、各頂点のＩＤ（identification）と各頂点の位置（ｘ，ｙ座標）と各頂点の属性（type）とが対応付けられる。各頂点の属性としては、凸頂点（凸点），凹頂点（凹点），ビア図形の頂点（ビア），その他が挙げられる。頂点リスト３３は、後述するごとくクラスタリング処理部２２ｂがクラスタの中心位置や距離Ｌorg，Ｌnewを算出する際に用いられる。なお、凸頂点は、多角形の頂点であって、内角が１８０度未満の頂点である。また、凹頂点は、多角形の頂点であって、内角が１８０度を超える頂点である。
【００３７】
属性／重み対応表３４は、後述するごとくクラスタリング処理部２２ｂがクラスタの中心位置を算出する際や、ホットスポット候補判定部２２ｃが頂点密集度を算出する際に用いられる。属性／重み対応表３４は、例えば図７を参照しながら後述するごとく、図形データ３２に含まれる多角形の頂点の種類（type；属性）と、クラスタの中心位置を算出する際に用いられる重み係数の値との関係を対応付ける。特に、本実施形態では、処理対象頂点の属性が図形データ３２における凹頂点（凹点）である場合の重みは、処理対象頂点の属性が凹頂点以外（例えば凸頂点，ビア図形の頂点など）である場合の重みよりも大きく設定される。なお、属性／重み対応表３４は、光ディスク１６ａまたはメモリ装置１７ａまたはメモリカード１７ｃまたはネットワーク１８ａから入力されてもよいし、ユーザが入力部４０を操作することによって設定入力されてもよい。
【００３８】
ウインドウリスト３５は、後述するごとくウインドウリスト生成部２３によって生成される。ウインドウリスト３５においては、レイアウトパターン３２から切り出される各ウインドウについて、各ウインドウのＩＤと、各ウインドウの中心位置（ｘ，ｙ座標）とが対応付けられる。ここで、各ウインドウは、後述するごとくホットスポット候補抽出部２２によって抽出される正方形領域（矩形領域）に相当する。
【００３９】
ホットスポット判定用ＤＢ３６は、ホットスポットの有無の判定に用いられる判定情報を含む。当該判定情報は、例えば、ホットスポット判定を行なうパターンマッチングに用いられるパターン情報、あるいは、ホットスポット判定を行なう機械学習エンジンに関する情報である。ホットスポット判定用ＤＢ３６は、光ディスク１６ａ，メモリ装置１７ａ，メモリカード１７ｃ，ネットワーク１８ａのいずれから入力されてもよい。
【００４０】
ホットスポット情報３７は、後述するごとくホットスポット判定部２４によって生成され出力される。ホットスポット情報３７は、ホットスポット判定部２４によるホットスポットの有無の判定結果であり、ホットスポットの位置（ｘ，ｙ座標）と重要度（危険度）とを含む。
【００４１】
入力部４０は、例えば図２に示すようなキーボード１５ａおよびマウス１５ｂであり、ユーザによって操作され、ホットスポットの有無を判定するための各種指示を行なう。なお、マウス１５ｂに代え、タッチパネル，タブレット，タッチパッド，トラックボール等が用いられてもよい。
【００４２】
表示部５０は、例えば図２に示すようなモニタ１４ａであり、ユーザが本実施形態のコンピュータ１０を用いてホットスポットの有無を判定する際に、その判定経過に伴う各種状況を表示する。
【００４３】
欠陥箇所判定プログラム３１は、上述のごとく、処理部２０（プロセッサ１１）に、後述する頂点リスト生成部２１，ホットスポット候補抽出部２２，ウインドウリスト生成部２３，ホットスポット判定部２４による処理を実行させるものである。
【００４４】
次に、処理部２０（プロセッサ１１）によって実現される、頂点リスト生成部２１，ホットスポット候補抽出部２２，ウインドウリスト生成部２３およびホットスポット判定部２４としての機能について説明する。
【００４５】
頂点リスト生成部２１は、外部から入力されるレイアウトパターン３２から、頂点ＩＤと各頂点の位置と各頂点の属性とを対応付ける頂点リスト３３（図６参照）を生成する。
【００４６】
ホットスポット候補抽出部２２は、各頂点の位置と属性とに基づくクラスタリングを行ない、レイアウトパターン３２において頂点が密集する領域を抽出し、各領域についてホットスポット候補であるか否かを判定する。当該領域は、例えば、後述するクラスタ中心位置を中心とする正方形領域（ウインドウ）とする。つまり、ホットスポット候補抽出部２２は、レイアウトパターン３２における複数の頂点のそれぞれの位置と属性とに基づいて、レイアウトパターン３２上でホットスポットが生じる可能性の高い位置（クラスタ中心位置）を、ホットスポット候補として抽出する。なお、上記正方形領域のサイズは、パターン形成工程（リソグラフィ工程）での露光強度が所定値以上になる範囲に基づいて決定される。例えば図１３（Ａ）および図１３（Ｂ）を参照しながら前述したように露光強度が所定値以上の領域の長さ（径）Ｌを、上記正方形領域の一辺の長さとする。
【００４７】
ホットスポット候補抽出部２２は、初期クラスタ生成部２２ａ，クラスタリング処理部２２ｂ，ホットスポット候補判定部２２ｃとしての機能を有している。
【００４８】
初期クラスタ生成部２２ａは、レイアウトパターン３２を格子状に分割してレイアウトパターン３２に含まれる複数の頂点を複数のクラスタに分割することで（図９（Ａ）参照）、初期クラスタを生成する。このとき、初期クラスタ生成部２２ａによって分割されるレイアウトパターン３２の格子サイズは、パターン形成工程（リソグラフィ工程）での露光強度が所定値以上になる範囲に基づいて決定される。例えば図１３（Ａ）および図１３（Ｂ）を参照しながら前述したように露光強度が所定値以上の領域の長さ（径）Ｌを、格子の間隔とする。なお、上述のごとく生成される初期クラスタでは、頂点の密集度等に関係なく格子状に分割され境界線が引かれるため、近接する頂点どうしが同一クラスタ（同一グループ）に属する状態になるとは限らない。そこで、本実施形態では、後述するクラスタリング処理が実行される。
【００４９】
クラスタリング処理部２２ｂは、頂点リスト３３および属性／重み対応表３４を参照し、各クラスタに属する頂点の位置と属性とに基づいて、複数のクラスタ（初期クラスタ）のそれぞれの中心位置を算出する。クラスタの中心位置を算出する具体的な数式については後述する（数１参照）。ここで、ホットスポットとなるパターンにおいては、配線が密集しており、特に折れ曲がり図形による凹頂点が見られると考えられる。このため、本実施形態の属性／重み対応表３４（図７参照）においては、属性が凹頂点の頂点についての重み係数の値が、他の属性の頂点についての重み係数の値よりも大きく設定される。そして、クラスタリング処理部２２ｂは、当該重みによる重み付けを、各クラスタに属する頂点の位置（座標）に対し行なって、各クラスタの中心位置を算出する（数１参照）。
【００５０】
また、クラスタリング処理部２２ｂは、頂点リスト３３を参照し、各クラスタに属する各頂点の位置と当該クラスタ以外の他クラスタの中心位置との距離Ｌnew（図８参照）に応じて各頂点を当該クラスタから他クラスタへ移動させる。これにより、クラスタリング処理部２２ｂは、近接する頂点どうしが同一クラスタに属するように複数の頂点のクラスタリングを行なう。なお、クラスタリングアルゴリズムとしては、例えばｋ-means法などの既知のアルゴリズムが利用され、クラスタ中心位置がホットスポット候補となるように、頂点属性による重み付けが行なわれる（図８参照）。
【００５１】
そして、クラスタリング処理部２２ｂは、上述したクラスタ中心位置の算出とクラスタリングとを、クラスタ間での各頂点の移動が無くなるまで繰り返し実行する。ただし、クラスタリング処理部２２ｂは、上述したクラスタ中心位置の算出とクラスタリングとを所定回数繰り返し実行してもクラスタ間での各頂点の移動が行なわれる場合、上述したクラスタ中心位置の算出とクラスタリングとを終了する（図８参照）。
【００５２】
ホットスポット候補判定部２２ｃは、上述したクラスタリングによって得られたクラスタ毎に、当該クラスタに属する頂点の密集度を算出し（数３参照）、算出した密集度に応じて、当該クラスタの中心位置がホットスポット候補であるか否かを判定する。なお、ホットスポット候補判定部２２ｃは、頂点の密集度に代え後述するごとく特徴ベクトルを算出し、算出した特徴ベクトルをホットスポット判定モデルに適用することで、当該クラスタの中心位置がホットスポット候補であるか否かを判定してもよい。
【００５３】
ウインドウリスト生成部２３は、ホットスポット判定部２４によって切り出される各ウインドウのＩＤと中心位置とを対応付けるウインドウリスト３５を生成する。ここで、各ウインドウは、ホットスポット判定領域（欠陥箇所判定領域）であって、ホットスポット候補抽出部２２によって抽出されるクラスタ中心位置（ホットスポット候補）を中心とする正方形領域もしくは矩形領域（図９（Ｂ），図１０（Ｂ）参照）である。
【００５４】
ホットスポット判定部２４は、ウインドウリスト３５を参照し、各ウインドウをレイアウトパターン３２から切り出し、切り出したウインドウとホットスポット判定用ＤＢ３６の判定情報とに基づいて、ウインドウ内におけるホットスポットの有無を判定する。ウインドウ内にホットスポットが有る場合、ホットスポット判定部２４は、当該ホットスポットの位置（ｘ，ｙ座標）と重要度（危険度；欠陥の発生する可能性の高さ）とを含むホットスポット情報３７を出力し、記憶部３０に格納したり表示部５０に表示させたりする。なお、ホットスポットの有無の判定には、パターンマッチング（パターン認識）や機械学習が用いられる。パターンマッチングの場合、ホットスポット判定用ＤＢ３６におけるパターン情報が用いられ、機械学習の場合、ホットスポット判定用ＤＢ３６における機械学習エンジンに関する情報が用いられる。また、ホットスポットの有無の判定には、特開２０１３−１７５０１６号公報に開示の技術を用いることもできる。
【００５５】
〔３〕欠陥箇所判定機能を有する本実施形態の情報処理装置の動作
次に、図３〜図１０を参照しながら、本実施形態の情報処理装置１０による具体的なホットスポット判定動作について説明する。
【００５６】
〔３−１〕ホットスポット判定動作の概略
まず、図３および図４を参照しながら、本実施形態におけるホットスポット判定動作の概略を説明する。図３は、本実施形態のホットスポット判定動作における処理の流れおよびデータの流れを説明する図であり、図４は、本実施形態のホットスポット判定動作を説明するフローチャートである。なお、以下、図３と図４とを対応付けてホットスポット判定動作の概略について説明する。図３に示すステップＳ１，Ｓ２ａ〜Ｓ２ｃ，Ｓ３，Ｓ４の処理は、それぞれ図４に示すステップＳ１１，Ｓ１２ａ〜Ｓ１２ｃ，Ｓ１３，Ｓ１４の処理に対応している。
【００５７】
頂点リスト生成処理（ステップＳ１）において、頂点リスト生成部２１は、外部から入力されるレイアウトパターン３２に含まれる多角形の各頂点について、座標と種類（属性）とを算出し、頂点リスト３３（図６参照）を生成する（ステップＳ１１）。ここで、レイアウトパターン３２は、例えばＧＤＳ（Graphic Data System）形式，ＯＡＳＩＳ（Open Artwork System Interchange Standard）形式のデータである。ステップＳ１，Ｓ１１における頂点リスト生成処理については、項目〔３−２〕において後述する。
【００５８】
ホットスポット候補抽出処理（ステップＳ２）において、ホットスポット候補抽出部２２は、初期クラスタ生成部２２ａ，クラスタリング処理部２２ｂ，ホットスポット候補判定部２２ｃによる処理Ｓ２ａ〜Ｓ２ｃを実行する。
【００５９】
初期クラスタ生成処理（ステップＳ２ａ）において、初期クラスタ生成部２２ａは、レイアウトパターン３２を格子状に分割してレイアウトパターン３２に含まれる複数の頂点を複数のクラスタ（格子内領域）に分類することで、初期クラスタを生成する（ステップＳ１２ａ）。ステップＳ２ａ，Ｓ１２ａにおける初期クラスタ生成処理については、項目〔３−３−１〕において後述する。
【００６０】
クラスタリング処理（ステップＳ２ｂ）において、クラスタリング処理部２２ｂは、頂点リスト３３および属性／重み対応表３４を参照し、各クラスタに属する頂点の位置と属性とに基づいて、クラスタリングを行なう。このとき、クラスタリング処理部２２ｂは、ｋ-means法などの手法を利用して、クラスタ中心位置がホットスポット候補となるように頂点属性（頂点種類）に応じた重み付けを行なってクラスタリングを実行する（ステップＳ１２ｂ）。ステップＳ２ｂ，Ｓ１２ｂにおけるクラスタリング処理については、項目〔３−３−２〕において後述する。
【００６１】
ホットスポット候補判定処理（ステップＳ２ｃ）において、ホットスポット候補判定部２２ｃは、クラスタリング処理によって得られたクラスタ毎に、当該クラスタに属する頂点の密集度を算出する。そして、ホットスポット候補判定部２２ｃは、算出した密集度に応じて、当該クラスタの中心位置がホットスポット候補であるか否かを判定する（ステップＳ１２ｃ）。ステップＳ２ｃ，Ｓ１２ｃにおけるホットスポット候補判定処理については、項目〔３−３−３〕において後述する。
【００６２】
ウインドウリスト生成処理（ステップＳ３）において、ウインドウリスト生成部２３は、ホットスポット候補であると判定されたクラスタの中心位置を中心とする、所定サイズのウインドウ（ホットスポット判定領域）のウインドウリスト３５を生成する（ステップＳ１３）。ステップＳ３，Ｓ１３におけるウインドウリスト生成処理については、項目〔３−４〕において後述する。
【００６３】
ホットスポット判定処理（ステップＳ４）において、ホットスポット判定部２４は、ウインドウリスト３５を参照し、各ウインドウについてホットスポット判定用ＤＢ３６の判定情報を用いてホットスポットの有無を判定する。ウインドウ内にホットスポットが有る場合、ホットスポット判定部２４は、当該ホットスポットの位置と重要度とを含むホットスポット情報３７を出力する（ステップＳ１４）。ステップＳ４，Ｓ１４におけるホットスポット判定処理については、項目〔３−５〕において後述する。
【００６４】
〔３−２〕頂点リスト生成処理（ステップＳ１，Ｓ１１）
次に、図５〜図７を参照しながら、頂点リスト生成処理（ステップＳ１，Ｓ１１）について、より具体的に説明する。図５は、外部から入力されるレイアウトパターン３２の図形データの例を示す図である。図６は、本実施形態において生成される頂点リスト３３の例を示す図である。図７は、本実施形態の属性／重み対応表３４の例を示す図である。
【００６５】
図５では、外部から入力されるレイアウトパターン３２の図形データの一部、つまり、２つの配線パターンＡ，Ｂの図形データと、配線パターンＡ上に位置するビアの図形データとが示されている。図５において、丸印は、各図形の頂点を示し、各丸印に付された数字０〜１９は、各頂点のＩＤを示す。配線パターンＡの図形データは、頂点ＩＤ０〜３，６，７，１０〜１５の１２個の頂点を有し、配線パターンＡ上のビアの図形データは、頂点ＩＤ４，５，８，９の４個の頂点を有し、配線パターンＢの図形データは、頂点ＩＤ１６〜１９の４個の頂点を有している。
【００６６】
頂点リスト生成部２１は、図５に示すような図形データから、各頂点の位置（ｘ，ｙ座標）と各頂点の属性（type）とを取得して、図６に示すような頂点リスト３３を作成することができる。各頂点の属性（type）としては、当該頂点が配線パターンの頂点かビアの頂点かに関する情報が取得されるとともに、当該頂点が配線パターンの頂点である場合には凹頂点であるか凸頂点であるかに冠する情報が取得される。
【００６７】
図６に示すように、頂点リスト３３においては、レイアウトパターン３２の図形データから取得された、頂点ＩＤと、各頂点の位置（ｘ，ｙ座標）と、各頂点の属性（type）とが対応付けられる。頂点がビアの頂点である場合、その頂点は凸頂点であるので、頂点リスト３３の属性（type）欄には「ビア」と表記されている。また、頂点が配線パターンの頂点である場合、その頂点は凹頂点か凸頂点かのいずれか一方であるので、頂点リスト３３の属性（type）欄には、当該頂点が凹頂点と凸頂点とのいずれであるかに関する情報が記入される。なお、図６では、凹頂点を凹点と表記し、凸頂点を凸点と表記する。
【００６８】
図６に示す頂点リスト３３では、図５に示す図形データのうちＩＤ０〜６の頂点について得られた情報が記入されている。例えば、ＩＤ０の頂点については、ｘ座標０とｙ座標２５０と属性「凸点」とが記入され、ＩＤ２の頂点については、ｘ座標１４０とｙ座標１５０と属性「凹点」とが記入され、ＩＤ４の頂点については、ｘ座標１２０とｙ座標−１５０と属性「ビア」とが記入されている。
【００６９】
このような頂点リスト３３における各頂点の座標および属性は、ホットスポット候補抽出処理Ｓ２におけるクラスタリング処理Ｓ２ａの際に、つまりクラスタリング処理部２２ｂがクラスタの中心位置や距離Ｌorg，Ｌnewを算出する際に用いられる（図８参照）。
【００７０】
一方、上述したように、ホットスポットとなるパターンにおいては、配線が密集しており、特に折れ曲がり図形による凹頂点が見られると考えられる。そこで、本実施形態では、クラスタリング処理Ｓ２ｂにおいて属性に応じた重み付けが行なわれる（数１参照）。このため、図７に示すような属性／重み対応表３４が予め用意される。図７に示す属性／重み対応表３４では、ホットスポットの発生に影響を与える属性「凹点」には重み「１．５」が与えられ、ホットスポットの発生にあまり影響を与えない属性「ビア」には重み「０．５」が与えられる。属性「凸点」や凸点，凹点，ビア以外の属性には、凹点ほどホットスポットの発生に影響を与えずビアよりもホットスポットの発生に影響を与えるものと考えて重み「１．０」が付与されている。
【００７１】
〔３−３〕ホットスポット候補抽出処理（Ｓ２）
次に、図８，図９（Ａ），図９（Ｂ）および数１〜数３を参照しながら、ホットスポット候補抽出処理（Ｓ２）について説明する。ホットスポット候補抽出処理（Ｓ２）では、各頂点の位置と属性とに基づくクラスタリングが行なわれ、レイアウトパターン３２において頂点が密集する領域が抽出され、各領域についてホットスポット候補であるか否かが判定される。
【００７２】
以下、ホットスポット候補抽出処理（Ｓ２）において実行される初期クラスタ生成処理（Ｓ２ａ，Ｓ１２ａ），クラスタリング処理（Ｓ２ｂ，Ｓ１２ｂ）およびホットスポット候補判定処理（Ｓ２ｃ，Ｓ１２ｃ）について、より詳細に説明する。なお、図８は、本実施形態におけるクラスタリング処理（Ｓ２ｂ，Ｓ１２ｂ）を説明するフローチャートである。図９（Ａ）は本実施形態で生成される初期クラスタの例を示す図、図９（Ｂ）は図９（Ａ）に示す初期クラスタに対し本実施形態のクラスタリング処理（Ｓ２ｂ，Ｓ１２ｂ；図８参照）を実行して得られるクラスタの例を示す図である。
【００７３】
〔３−３−１〕初期クラスタ生成処理（Ｓ２ａ，Ｓ１２ａ）
初期クラスタ生成処理（Ｓ２ａ，Ｓ１２ａ）では、初期クラスタ生成部２２ａによって、図９（Ａ）において点線で示すように、レイアウトパターン３２が格子状に分割され、各格子内領域の頂点集合が、初期クラスタＣ1，…，Ｃi，…，ＣNとして生成される。ここで、Ｎ（１以上の整数）は初期クラスタの数である。ｉはＮ個のクラスタのうちの一つを特定するパラメータであり１〜Ｎの整数である。なお、図９（Ａ）では、レイアウトパターンを１２の格子に分割した例、つまりＮ＝１２の例が示されている。
【００７４】
図９（Ａ）に示す格子のサイズ（間隔）は、前述したように、パターン形成工程（リソグラフィ工程）での露光強度が所定値以上になる範囲に基づいて決定される。このように格子分割によって生成される初期クラスタでは、前述したように、頂点の密集度等に関係なく格子状に分割され境界線が引かれるため、近接する頂点どうしが同一クラスタ（同一グループ）に属する状態になるとは限らない。そこで、以下のようなクラスタリング処理（Ｓ２ｂ，Ｓ１２ｂ）が実行される。
【００７５】
〔３−３−２〕クラスタリング処理（Ｓ２ｂ，Ｓ１２ｂ）
クラスタリング処理（Ｓ２ｂ，Ｓ１２ｂ）では、近接する頂点どうしが同一クラスタに属するように複数の頂点のクラスタリングが行なわれる。クラスタリングアルゴリズムとしては、例えばｋ-means法などの既知のアルゴリズムが利用され、クラスタ中心位置がホットスポット候補となるように、以下に説明するごとく頂点属性による重み付けが行なわれる。
【００７６】
次に、図８に示すフローチャート（ステップＳ２１〜Ｓ３１）に従って、クラスタリング処理（Ｓ２ｂ，Ｓ１２ｂ）について説明する。
【００７７】
なお、以下では、クラスタＣiに属する頂点集合ｖiを(ｖi1，ｖi2，…，ｖij，…，ｖini)とし、頂点ｖijの座標を（ｘij，ｙij）とする。ここで、ｎi（１以上の整数）は、クラスタＣiに属する頂点の数である。ｊは、頂点集合ｖiに属するｎi個の頂点のうちの一つを特定するパラメータであり１〜ｎiの整数である。頂点の数を表すｎiは、ｎiと表記される場合がある。
【００７８】
まず、ステップＳ２１において、クラスタリング処理部２２ｂは初期化処理を行なう。つまり、クラスタリング処理部２２ｂは、頂点リスト３３および属性／重み対応表３４を参照し、各クラスタに属する頂点の位置と属性とに基づいて、各クラスタＣiの頂点集合ｖi＝（ｖi1，ｖi2，…，ｖini）から、各クラスタＣiの中心位置（Ｃix，Ｃiy）を算出する。
【００７９】
ここで、各クラスタＣiの中心位置（Ｃix，Ｃiy）は、下記の数１で示す数式のように定義され算出される。
【００８０】
【数１】
2016212539.tif 000003
【００８１】
上記数１において、ｗtype(ｖij)は、頂点ｖijの属性に対応する重み（重み係数の値）である。クラスタリング処理部２２ｂは、頂点ｖijのＩＤで頂点リスト３３を検索することで頂点ｖijの属性を取得し、取得した属性で属性／重み対応表３４を検索することで当該属性に対応する重みを取得することができる。
【００８２】
前述したように、ホットスポットとなるパターンにおいては、配線が密集しており、特に折れ曲がり図形による凹頂点が見られると考えられる。このため、属性が凹頂点の頂点についての重みが、他の属性の頂点についての重みよりも大きく設定される。そして、クラスタリング処理部２２ｂは、上記数１に示す数式に従って、当該重みによる重み付けを、各クラスタＣiに属する頂点ｖijの座標（ｘij，ｙij）に対し行なって、各クラスタＣiの中心位置を算出する。
【００８３】
ついで、クラスタリング処理部２２ｂは、ステップＳ２２〜Ｓ２６の処理を含むmovecluster処理を実行する。
【００８４】
ステップＳ２２において、クラスタリング処理部２２ｂは、後述する頂点移動処理の実行回数を示すパラメータであるnchangeを０に設定するとともに、ｉを１インクリメントする（ｉ＝ｉ＋１；ｉの初期値は０）。なお、パラメータnchangeは、記憶部３０に保存されてもよい。
【００８５】
この後、ステップＳ２３において、クラスタリング処理部２２ｂは、頂点リスト３３を参照し、クラスタＣiの頂点ｖijの位置（ｘij，ｙij）と、ステップＳ２１で算出したクラスタＣiの中心位置（Ｃix，Ｃiy）との距離Ｌorgを下記の数２で示す数式によって算出する。なお、距離Ｌorgの“org”は“original”の略記である。
【００８６】
【数２】
2016212539.tif 000004
【００８７】
ついで、ステップＳ２４において、クラスタリング処理部２２ｂは、クラスタＣiの頂点ｖijの位置（ｘij，ｙij）と、クラスタＣiを除いたクラスタＣ1〜Ｃi-1，Ｃi+1〜Ｃniそれぞれの中心位置との距離Ｌnewを、上記数２に示す数式に従って算出する。なお、クラスタＣ1〜Ｃi-1，Ｃi+1〜Ｃniそれぞれの中心位置（Ｃ1x，Ｃ1y）〜（Ｃi-1x，Ｃi-1y），（Ｃi+1x，Ｃi+1y）〜（Ｃnix，Ｃniy）は、ステップＳ２１（もしくは後述するステップＳ３１）で算出されている。
【００８８】
さらに、ステップＳ２４において、クラスタリング処理部２２ｂは、クラスタＣiを除いたクラスタＣ1〜Ｃi-1，Ｃi+1〜Ｃniのうち、クラスタ中心位置と頂点ｖijの位置（ｘij，ｙij）との距離Ｌnewが、ステップＳ２３で算出した距離Ｌorgよりも小さくなるクラスタを探す。距離Ｌnewが距離Ｌorgよりも小さくなるクラスタが複数存在する場合、クラスタリング処理部２２ｂは、頂点ｖijを、クラスタＣiから、これらのクラスタのうち距離Ｌnewが最も短くなるクラスタへ移動させる。
【００８９】
また、距離Ｌnewが距離Ｌorgよりも小さくなるクラスタが一つだけ存在する場合、クラスタリング処理部２２ｂは、頂点ｖijを、クラスタＣiから、距離Ｌnewが距離Ｌorgよりも小さくなる当該クラスタへ移動させる。距離Ｌnewが距離Ｌorgよりも小さくなるクラスタが一つも存在しない場合、クラスタリング処理部２２ｂは、頂点ｖijをクラスタＣiから他のクラスタへ移動させる処理を行なわない。
【００９０】
クラスタリング処理部２２ｂは、頂点ｖijを他のクラスタへ移動させた場合、クラスタＣ1〜Ｃniに属する頂点ｖijを管理する情報を更新する。当該情報は、記憶部３０に保存されてもよい。
【００９１】
ステップＳ２４において頂点ｖijが他のクラスタへ移動された場合、クラスタリング処理部２２ｂは、ステップＳ２５において、パラメータnchangeを１インクリメントする（nchange＝nchange＋１）。一方、ステップＳ２４において頂点ｖijの移動が行なわれなかった場合、クラスタリング処理部２２ｂは、パラメータnchangeに対するインクリメントを行なわず、パラメータnchangeの値をそのまま維持する。
【００９２】
この後、ステップＳ２６において、クラスタリング処理部２２ｂは、ステップＳ２３〜Ｓ２５による移動処理を、クラスタＣiに属する全ての頂点ｖij（ｊ＝１〜ｎiの全て）について行なったか否かを判断する。全ての頂点ｖijについて行なっていない場合（ステップＳ２６のＮＯルート）、クラスタリング処理部２２ｂは、ｊのインクリメント処理等を行ない、ステップＳ２３〜Ｓ２５による移動処理を繰り返し実行する。
【００９３】
移動処理を全ての頂点ｖijについて行なった場合（ステップＳ２６のＹＥＳルート）、ステップＳ２７において、クラスタリング処理部２２ｂは、ステップＳ２２〜Ｓ２６によるmovecluster処理を、全てのクラスタＣiについて行なったか否かを判断する。全てのクラスタＣiについて行なっていない場合（ステップＳ２７のＮＯルート）、クラスタリング処理部２２ｂは、ステップＳ２２に戻り、ステップＳ２２〜Ｓ２６によるmovecluster処理を繰り返し実行する。
【００９４】
movecluster処理を、全てのクラスタＣiについて行なった場合（ステップＳ２７のＹＥＳルート）、ステップＳ２８において、クラスタリング処理部２２ｂは、パラメータnchangeを参照し、少なくとも一のクラスタで頂点の移動が行なわれたか否かを判断する。いずれのクラスタにおいても頂点の移動が全く行なわれなかった場合（ステップＳ２８のＮＯルート）、ステップＳ２９において、クラスタリング処理部２２ｂは、現時点で算出されている各クラスタＣiの中心位置（Ｃix，Ｃiy）を、ホットスポット候補として抽出して出力し、処理を終了する。
【００９５】
一方、少なくとも一のクラスタで頂点の移動が行なわれた場合（ステップＳ２８のＹＥＳルート）、ステップＳ３０において、クラスタリング処理部２２ｂは、ループ回数、つまり後述するステップＳ３１と前述したステップＳ２２〜Ｓ２８による処理の繰返し回数が所定回数に達したか否かを判断する。
【００９６】
繰返し回数が所定回数に達していない場合（ステップＳ３０のＮＯルート）、ステップＳ３１において、クラスタリング処理部２２ｂは、formcluster処理を行なう。当該formcluster処理において、クラスタリング処理部２２ｂは、頂点の数がＫ個以下のクラスタを削除し、残った各クラスタＣiの中心位置（Ｃix，Ｃiy）を、上記数１で示す数式に従って算出する。中心位置の算出後、クラスタリング処理部２２ｂは、ステップＳ２２の処理に戻る。なお、Ｋは、例えば３以上の整数である。
【００９７】
繰返し回数が所定回数に達した場合（ステップＳ３０のＹＥＳルート）、ステップＳ２９において、クラスタリング処理部２２ｂは、現時点で算出されている各クラスタＣiの中心位置（Ｃix，Ｃiy）を、ホットスポット候補として抽出して出力し、処理を終了する。このように、ステップＳ２２〜Ｓ２８，Ｓ３１による処理の繰返し回数が所定回数に達した場合にクラスタリング処理を終了させることで、ステップＳ２２〜Ｓ２８，Ｓ３１による処理が無限ループに陥ることを抑止することができる。
【００９８】
上述のようなクラスタリング処理（Ｓ２ｂ，Ｓ１２ｂ）を、図９（Ａ）に示す１２個の初期クラスタに対し実行することで、図９（Ｂ）に示すように、５個のクラスタ（１）〜（５）に絞られる。ここで、各クラスタ（１）〜（５）は、一辺が上記長さＬの正方形領域であり、当該正方形領域の中心位置が、ホットスポット候補（クラスタ中心位置）である。
【００９９】
〔３−３−３〕ホットスポット候補判定処理（Ｓ２ｃ，Ｓ１２ｃ）
ホットスポット候補判定処理（Ｓ２ｃ，Ｓ１２ｃ）において、ホットスポット候補判定処理部２２ｃは、上述したクラスタリング処理（Ｓ２ｂ，Ｓ１２ｂ）によって得られたクラスタ（例えば図９（Ｂ）参照）毎に、当該クラスタの中心位置がホットスポット候補であるか否かを判定する。本実施形態におけるホットスポット候補判定処理は、折れ曲がり図形や微小な突出しなどの数や集中度がホットスポットのなり易さ（出現可能性）を決めるという傾向に基づいて、下記の第１手法または第２手法によって行なわれる。
【０１００】
第１手法では、ホットスポット候補判定部２２ｃは、クラスタリング処理（Ｓ２ｂ，Ｓ１２ｂ）によって得られたクラスタ毎に、当該クラスタに属する頂点の密集度を、下記の数３に示す数式によって算出する。ホットスポット候補判定部２２ｃは、算出した頂点密集度が所定値よりも大きい場合に当該クラスタＣiの中心位置（Ｃix，Ｃiy）がホットスポット候補であると判定する。
【０１０１】
【数３】
2016212539.tif 000005
【０１０２】
ここで、αtypeijは、上記数１におけるｗtype(ｖij)と同じもので、頂点ｖijの属性に対応する重み（重み係数の値）である。また、Ｄjは、クラスタＣiの頂点ｖijの位置（ｘij，ｙij）とクラスタＣiの中心位置（Ｃix，Ｃiy）との距離であり、上記距離Ｌorgと同様、上記数２に示す数式によって算出される。
【０１０３】
第２手法では、ホットスポット候補判定部２２ｃは、ラスタリング処理（Ｓ２ｂ，Ｓ１２ｂ）によって得られたクラスタ毎に、下記特徴ベクトルＶを算出し、算出した特徴ベクトルＶを下記ホットスポット判定モデルに適用することで、各クラスタＣiの中心位置（Ｃix，Ｃiy）がホットスポット候補であるか否かを判定する。
【０１０４】
特徴ベクトルＶは、例えば（Ｎ1，Ｎ2，…，Ｎk，Ｒ1，Ｒ2，…，Ｒk）とする。ここで、ｋは頂点種類（属性；type）の数であり、本実施形態では、図７に示す属性／重み対応表３４のごとくｋ＝４である。Ｎｍは頂点種類ｍ（ｍは１〜ｋの整数）の頂点の数であり、Ｒｍは頂点種類ｍの各頂点とクラスタＣiの中心位置との距離の平均値である。
【０１０５】
また、［ホットスポット候補判定モデル］＝Σβr＊Ｖrとする。ここで、ｒは、特徴ベクトルＶ＝（Ｎ1，Ｎ2，…，Ｎk，Ｒ1，Ｒ2，…，Ｒk）の要素を特定するパラメータで、１〜２ｋの整数である。Ｖrは、特徴ベクトルＶのｒ番目の要素であり、βrは、特徴ベクトルＶのｒ番目の要素Ｖrに付与される重みである。
【０１０６】
ホットスポット候補判定モデルは、既知データを用いて生成される。そして、ホットスポット候補判定モデルによって算出される一次元の値は、上述した頂点密集度に相当するもので、その値の大きさによって、第１手法と同様、クラスタＣiの中心位置（Ｃix，Ｃiy）がホットスポット候補であるか否かを判定することができる。
【０１０７】
〔３−４〕ウインドウリスト生成処理（Ｓ３，Ｓ１３）
ウインドウリスト生成処理（Ｓ３，Ｓ１３）では、ウインドウリスト生成部２３によって、ホットスポット判定部２４が切り出す各ウインドウ（例えば図１０（Ｂ）参照）のＩＤと中心位置（例えば図１０（Ｂ）のｘ参照）とを対応付けるウインドウリスト３５が生成される。各ウインドウは、前述したように、ホットスポット判定領域（欠陥箇所判定領域）であって、ホットスポット候補抽出部２２によって抽出されるクラスタ中心位置（ホットスポット候補）を中心とする、一辺が上記長さＬの正方形領域である。
【０１０８】
〔３−５〕ホットスポット判定処理（Ｓ４，Ｓ１４）
ホットスポット判定処理（Ｓ４，Ｓ１４）では、ホットスポット判定部２４によって、ウインドウリスト３５が参照され、ウインドウリスト３５に登録された各ウインドウがレイアウトパターン３２から切り出される。そして、ホットスポット判定部２４によって、切り出されたウインドウと記憶部３０に記憶された判定情報とに基づき、各ウインドウ内におけるホットスポットの有無が判定される。
【０１０９】
ウインドウ内にホットスポットが有る場合、ホットスポット判定部２４によって、当該ホットスポット（クラスタ中心）の位置（ｘ，ｙ座標）と重要度とを含むホットスポット情報３７が出力され記憶部３０に格納されたり表示部５０に表示されたりする。
【０１１０】
〔４〕欠陥箇所判定機能を有する本実施形態の情報処理装置の効果
ここで、図１０（Ａ）は一般的手法によって切り出されるホットスポット判定対象のウインドウの例を示す図であり、図１０（Ｂ）は本実施形態の手法によって切り出されるホットスポット判定対象のウインドウの例を示す図である。図１０（Ａ）および図１０（Ｂ）において、ｘで示す位置は、ホットスポット候補となりうる位置であり、本実施形態では、クラスタリング処理によってクラスタ中心になる位置を示す。
【０１１１】
上述したように、従来、格子分割やウィンドウ切出しを行なう場合、ホットスポットの判定精度を向上させホットスポットの見逃しを回避するためには、格子分割の位置やウィンドウの位置をずらしながらホットスポット判定を行なうことになる。例えば図１０（Ａ）に示すように、配線パターンの存在する領域において、ホットスポット判定対象のウインドウを格子に沿ってずらす。これにより、ホットスポット候補となりうる位置ｘを含む領域を、できるだけ異なる２以上のウインドウで切り出し、切り出した各ウインドウ内の領域についてホットスポット判定が行なわれる。このため、図１０（Ａ）では、例えば１８個のウインドウ（１）〜（１８）が切り出されホットスポットの判定対象領域になる。
【０１１２】
本実施形態では、ウィンドウ切り出し手法を変えることで、ホットスポット判定対象となるウィンドウ数が、一般的手法よりも削減される。つまり、本実施形態では、クラスタリング処理により、頂点の座標および属性に基づいて、クラスタ中心がホットスポット候補として抽出され、抽出されたホットスポット候補を中心としたウィンドウがホットスポット判定対象領域となる。例えば、図１０（Ｂ）に示すように、本実施形態では、ｘで示す１２個のクラスタ中心位置がホットスポット候補として抽出され、各ホットスポット候補を中心とする１２個のウインドウ（１）〜（１２）が切り出されホットスポットの判定対象領域になる。
【０１１３】
このように、格子分割位置やウインドウ位置をシフトする一般的手法では、図１０（Ａ）に示すごとく判定対象として切り出すウインドウの数が多くなり、ホットスポット判定処理に要する時間が増大する。
【０１１４】
これに対し、本実施形態によれば、格子分割位置やウインドウ位置をシフトする必要がなく、ホットスポット判定対象として切り出すウインドウの数を、図１０（Ｂ）に示すごとく低減することができる。したがって、集積回路のパターン形成工程（リソグラフィ工程）で生じるホットスポットの有無を短時間で精度よく判定することができる。
【０１１５】
以下に、本実施形態による切出しウインドウ数の低減による、ホットスポット判定処理に要する時間の削減効果を、一般的手法と対比させて具体的に説明する。
【０１１６】
ここで、レイアウトパターンのサイズを９５０μm＊９８０μmとし、切り出されるウインドウのサイズを５μm＊５μmとする。このとき、或るレイアウトパターンについて、本実施形態の手法によって抽出されるホットスポット候補の数（つまりは、切り出されるウインドウの数）は、１１０３であった。
【０１１７】
これに対し、同じレイアウトパターンについて、一般的手法の格子分割で２種類の格子位置を用いる場合の全ウインドウの数は（９５０／５）＊（９８０／５）＊２＝７４４８０となる。ただし、全ウインドウのうち９０％が図形（配線パターン等）の少なさから非ホットスポットとして除外されたとすると、一般的手法によって抽出されるホットスポット候補の数（つまりは、切り出されるウインドウの数）は、７４４８となり、本実施形態の手法でのホットスポット候補の数との差は、６３４５となる。
【０１１８】
このとき、ホットスポット判定に特開２０１３−１７５０１６号公報に開示の技術を用いた場合についてのホットスポット判定処理に要する時間を、一般的手法と本実施形態の手法との両方について概算すると、以下の通りである。
【０１１９】
［一般的手法での処理時間］＝［一ウインドウ当たりに要するホットスポット判定時間０．１８秒］＊［ホットスポット候補数７４４８］＝１３４０．６４秒
【０１２０】
［本実施形態の手法での処理時間］＝［ホットスポット候補抽出時間（クラスタリング処理時間）０．７５秒］＋［一ウインドウ当たりに要するホットスポット判定時間０．１８秒］＊［ホットスポット候補数１１０３］＝１９９．２９秒
【０１２１】
したがって、１９９．２９／１３４０．６４＊１００≒１５．０であり、本実施形態の手法によれば、ホットスポット判定処理に要する時間は、一般的手法の処理時間の約１５％に短縮される。
【０１２２】
〔５〕その他
以上、本発明の好ましい実施形態について詳述したが、本発明は、係る特定の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲内において、種々の変形、変更して実施することができる。
【０１２３】
なお、上述した実施形態においては、ウインドウ（ホットスポット判定領域）が正方形領域である場合について説明したが、ウインドウの形状は、これに限定されるものではなく、矩形領域，多角形形状であってもよい。
【０１２４】
〔６〕付記
以上の実施形態に関し、さらに以下の付記を開示する。
（付記１）
集積回路のパターン形成工程で生じる欠陥箇所の有無を判定する処理部と、
前記欠陥箇所の有無の判定に用いられる判定情報を記憶する記憶部と、を有し、
前記処理部は、
前記集積回路のレイアウトパターンにおける複数の頂点のそれぞれの位置と属性とに基づいて、前記レイアウトパターン上で前記欠陥箇所が生じる可能性の高い位置を、欠陥箇所候補として抽出し、
抽出した前記欠陥箇所候補を中心とする領域を、欠陥箇所判定領域として前記レイアウトパターンから切り出し、
切り出した欠陥箇所判定領域と前記記憶部に記憶された前記判定情報とに基づいて、前記欠陥箇所判定領域における前記欠陥箇所の有無を判定する、情報処理装置。
【０１２５】
（付記２）
前記処理部は、
前記欠陥箇所候補を抽出する際、
前記複数の頂点を複数のクラスタに分割し、
前記複数のクラスタのそれぞれの中心位置を、各クラスタに属する頂点の位置と属性とに基づいて算出し、
前記各クラスタに属する各頂点の位置と当該クラスタ以外の他クラスタの中心位置との距離に応じて前記各頂点を当該クラスタから前記他クラスタへ移動させることで、近接する頂点どうしが同一クラスタに属するように前記複数の頂点のクラスタリングを行ない、
前記クラスタリングによって得られたクラスタ毎に、当該クラスタに属する頂点の密集度を算出し、
算出した密集度に応じて、当該クラスタの中心位置が前記欠陥箇所候補であるか否かを判定する、付記１に記載の情報処理装置。
【０１２６】
（付記３）
前記処理部は、
処理対象頂点の属性が前記レイアウトパターンにおける凹頂点である場合の重みを、前記処理対象頂点の属性が前記凹頂点以外である場合の重みよりも大きく設定し、
設定した重みによる重み付けを、前記各クラスタに属する頂点の位置に対し行なって、前記中心位置を算出する、付記２に記載の情報処理装置。
【０１２７】
（付記４）
前記処理部は、
前記レイアウトパターンを格子状に分割することで、前記複数のクラスタを生成する、付記２または３に記載の情報処理装置。
【０１２８】
（付記５）
前記処理部によって分割される前記レイアウトパターンの格子サイズは、前記パターン形成工程での露光強度が所定値以上になる範囲に基づいて決定される、付記４に記載の情報処理装置。
【０１２９】
（付記６）
前記処理部は、
前記中心位置の算出と前記クラスタリングとを、前記クラスタ間での前記各頂点の移動が無くなるまで繰り返し実行する、付記２〜付記５のいずれか一項に記載の情報処理装置。
【０１３０】
（付記７）
前記処理部は、
前記中心位置の算出と前記クラスタリングとを所定回数繰り返し実行しても前記クラスタ間での前記各頂点の移動が行なわれる場合、前記中心位置の算出と前記クラスタリングとを終了する、付記６に記載の情報処理装置。
【０１３１】
（付記８）
前記欠陥箇所候補を中心とする領域のサイズは、前記パターン形成工程での露光強度が所定値以上になる範囲に基づいて決定される、付記１〜付記７のいずれか一項に記載の情報処理装置。
【０１３２】
（付記９）
集積回路のパターン形成工程で生じる欠陥箇所の有無を判定するコンピュータに、
前記集積回路のレイアウトパターンにおける複数の頂点のそれぞれの位置と属性とに基づいて、前記レイアウトパターン上で前記欠陥箇所が生じる可能性の高い位置を、欠陥箇所候補として抽出し、
抽出した前記欠陥箇所候補を中心とする領域を、欠陥箇所判定領域として前記レイアウトパターンから切り出し、
切り出した欠陥箇所判定領域と記憶部に記憶され前記欠陥箇所の有無の判定に用いられる判定情報とに基づいて、前記欠陥箇所判定領域における前記欠陥箇所の有無を判定する
処理を実行させる、欠陥箇所判定プログラム。
【０１３３】
（付記１０）
前記欠陥箇所候補を抽出する際、
前記複数の頂点を複数のクラスタに分割し、
前記複数のクラスタのそれぞれの中心位置を、各クラスタに属する頂点の位置と属性とに基づいて算出し、
前記各クラスタに属する各頂点の位置と当該クラスタ以外の他クラスタの中心位置との距離に応じて前記各頂点を当該クラスタから前記他クラスタへ移動させることで、近接する頂点どうしが同一クラスタに属するように前記複数の頂点のクラスタリングを行ない、
前記クラスタリングによって得られたクラスタ毎に、当該クラスタに属する頂点の密集度を算出し、
算出した密集度に応じて、当該クラスタの中心位置が前記欠陥箇所候補であるか否かを判定する
処理を、前記コンピュータに実行させる、付記９に記載の欠陥箇所判定プログラム。
【０１３４】
（付記１１）
処理対象頂点の属性が前記レイアウトパターンにおける凹頂点である場合の重みを、前記処理対象頂点の属性が前記凹頂点以外である場合の重みよりも大きく設定し、
設定した重みによる重み付けを、前記各クラスタに属する頂点の位置に対し行なって、前記中心位置を算出する
処理を、前記コンピュータに実行させる、付記１０に記載の欠陥箇所判定プログラム。
【０１３５】
（付記１２）
前記レイアウトパターンを格子状に分割することで、前記複数のクラスタを生成する
処理を、前記コンピュータに実行させる、付記１０または１１に記載の欠陥箇所判定プログラム。
【０１３６】
（付記１３）
前記レイアウトパターンの格子サイズは、前記パターン形成工程での露光強度が所定値以上になる範囲に基づいて決定される、付記１２に記載の欠陥箇所判定プログラム。
【０１３７】
（付記１４）
前記中心位置の算出と前記クラスタリングとを、前記クラスタ間での前記各頂点の移動が無くなるまで繰り返し実行する
処理を、前記コンピュータに実行させる、付記１０〜付記１３のいずれか一項に記載の欠陥箇所判定プログラム。
【０１３８】
（付記１５）
前記中心位置の算出と前記クラスタリングとを所定回数繰り返し実行しても前記クラスタ間での前記各頂点の移動が行なわれる場合、前記中心位置の算出と前記クラスタリングとを終了する
処理を、前記コンピュータに実行させる、付記１４に記載の欠陥箇所判定プログラム。
【０１３９】
（付記１６）
前記欠陥箇所候補を中心とする領域のサイズは、前記パターン形成工程での露光強度が所定値以上になる範囲に基づいて決定される、付記９〜付記１５のいずれか一項に記載の欠陥箇所判定プログラム。
【０１４０】
（付記１７）
コンピュータにより、集積回路のパターン形成工程で生じる欠陥箇所の有無を判定する欠陥箇所判定方法であって、
前記集積回路のレイアウトパターンにおける複数の頂点のそれぞれの位置と属性とに基づいて、前記レイアウトパターン上で前記欠陥箇所が生じる可能性の高い位置を、欠陥箇所候補として抽出し、
抽出した前記欠陥箇所候補を中心とする領域を、欠陥箇所判定領域として前記レイアウトパターンから切り出し、
切り出した欠陥箇所判定領域と記憶部に記憶され前記欠陥箇所の有無の判定に用いられる判定情報とに基づいて、前記欠陥箇所判定領域における前記欠陥箇所の有無を判定する、欠陥箇所判定方法。
【０１４１】
（付記１８）
前記欠陥箇所候補を抽出する際、
前記複数の頂点を複数のクラスタに分割し、
前記複数のクラスタのそれぞれの中心位置を、各クラスタに属する頂点の位置と属性とに基づいて算出し、
前記各クラスタに属する各頂点の位置と当該クラスタ以外の他クラスタの中心位置との距離に応じて前記各頂点を当該クラスタから前記他クラスタへ移動させることで、近接する頂点どうしが同一クラスタに属するように前記複数の頂点のクラスタリングを行ない、
前記クラスタリングによって得られたクラスタ毎に、当該クラスタに属する頂点の密集度を算出し、
算出した密集度に応じて、当該クラスタの中心位置が前記欠陥箇所候補であるか否かを判定する、付記１７に記載の欠陥箇所判定方法。
【０１４２】
（付記１９）
処理対象頂点の属性が前記レイアウトパターンにおける凹頂点である場合の重みを、前記処理対象頂点の属性が前記凹頂点以外である場合の重みよりも大きく設定し、
設定した重みによる重み付けを、前記各クラスタに属する頂点の位置に対し行なって、前記中心位置を算出する、付記１８に記載の欠陥箇所判定方法。
【０１４３】
（付記２０）
前記中心位置の算出と前記クラスタリングとを、前記クラスタ間での前記各頂点の移動が無くなるまで繰り返し実行する、付記１７〜付記１９のいずれか一項に記載の欠陥箇所判定方法。
【符号の説明】
【０１４４】
１０    コンピュータ（欠陥箇所判定機能を有する情報処理装置）
１１    プロセッサ（処理部）
１２    ＲＡＭ（記憶部）
１３    ＨＤＤ（記憶部）
１４    グラフィック処理装置
１４ａ    モニタ（表示部）
１５    入力インタフェース
１５ａ    キーボード（入力部）
１５ｂ    マウス（入力部）
１６    光学ドライブ装置
１６ａ    光ディスク
１７    機器接続インタフェース
１７ａ    メモリ装置
１７ｂ    メモリリーダライタ
１７ｃ    メモリカード
１８    ネットワークインタフェース
１８ａ    ネットワーク
１９    バス
２０    処理部
２１    頂点リスト生成部
２２    ホットスポット候補抽出部
２２ａ    初期クラスタ生成部
２２ｂ    クラスタリング処理部
２２ｃ    ホットスポット候補判定部
２３    ウインドウリスト生成部
２４    ホットスポット判定部
３０    記憶部
３１    欠陥箇所判定プログラム
３２    レイアウトパターン
３３    頂点リスト
３４    属性／重み対応表
３５    ウインドウリスト
３６    ホットスポット判定用ＤＢ
３７    ホットスポット情報
４０    入力部
５０    表示部
【図１】
2016212539.tif 000006
【図２】
2016212539.tif 000007
【図３】
2016212539.tif 000008
【図４】
2016212539.tif 000009
【図６】
2016212539.tif 000010
【図７】
2016212539.tif 000011
【図８】
2016212539.tif 000012
【図９】
2016212539.tif 000013
【図１０】
2016212539.tif 000014
【図１３】
2016212539.tif 000015
【図１４】
2016212539.tif 000016
【図５】
2016212539.tif 000017
【図１１】
2016212539.tif 000018
【図１２】
2016212539.tif 000019