(57)【要約】【課題】コスト関数を用いてターゲットパターンを複数のマスクパターンに分割するための技術を提供する。【解決手段】ターゲットパターンを複数回に分けて基板上に転写する複数回露光に用いられる複数のマスクのパターンデータを生成する生成方法は、セルごとに、前記複数のパターン要素のそれぞれがいずれかのグループに属するように前記複数のパターン要素を複数のグループに分ける工程と、配列された前記複数のセル間でのグループ同士の組み合わせによって１つのマスクのパターンデータが構成され、且つ１つのセル内のグループ同士が互いに異なるマスクのパターンデータに属するように前記複数のセルの各グループを振り分けて、複数のマスクのパターンデータを生成する工程とを含む。【選択図】図１
2018156042.tif 000002
【特許請求の範囲】
【請求項１】
ターゲットパターンを複数回に分けて基板上に転写する複数回露光に用いられる複数のマスクのパターンデータを生成する生成方法であって、
複数のパターン要素を有するセルのパターンのデータを複数のセルについて取得する第１工程と、
前記第１工程で取得したセルごとに、前記複数のパターン要素のそれぞれがいずれかのグループに属するように前記複数のパターン要素を複数のグループに分ける第２工程と、
前記複数のセルを配列させる第３工程と、
配列された前記複数のセル間でのグループ同士の組み合わせによって１つのマスクのパターンデータが構成され、且つ１つのセル内のグループ同士が互いに異なるマスクのパターンデータに属するように前記複数のセルの各グループを振り分けて、複数のマスクのパターンデータを生成する第４工程と、
を含み、
前記第２工程では、グループの数とパターン要素同士の距離とを変数としたコスト関数を用いて、閾値より小さい距離で配置されたパターン要素同士が互いに異なるグループに属するように、前記複数のパターン要素を複数のグループに分け、
前記第４工程では、マスクの数とグループ同士でのパターン要素の最小距離とを変数としたコスト関数を用いて、グループ間でのパターン要素の最小距離が閾値より小さいグループ同士が互いに異なるマスクのパターンデータに属するように、前記複数のセルの各グループを振り分ける、ことを特徴とする生成方法。
【請求項２】
前記第２工程および前記第４工程のそれぞれで用いられる閾値は、前記ターゲットパターンを基板に転写する装置の解像限界以上の値に設定される、ことを特徴とする請求項１に記載の生成方法。
【請求項３】
前記複数のパターン要素は、形状および寸法が同じである、ことを特徴とする請求項１又は２に記載の生成方法。
【請求項４】
前記第２工程では、前記複数のセルの各々について、グループの数が可能な限り少なくなるように、前記複数のパターン要素を複数のグループに分ける、ことを特徴とする請求項１乃至３のうちいずれか１項に記載の生成方法。
【請求項５】
前記複数のセルは、前記複数のパターン要素の配置が同じである第１セルおよび第２セルを含み、
前記第２工程では、前記第１セルにおける前記複数のパターン要素を複数のグループに分けた結果を前記第２セルに対して適用する、ことを特徴とする請求項１乃至４のうちいずれか１項に記載の生成方法。
【請求項６】
前記第４工程では、パターンデータの数が可能な限り少なくなるように、前記複数のセルの各グループを振り分ける、ことを特徴とする請求項１乃至５のうちいずれか１項に記載の生成方法。
【請求項７】
前記第４工程では、１つのマスクのパターンデータにおけるグループ間でのパターン要素の最小距離が可能な限り大きくなるように複数のセルの各グループを振り分ける、ことを特徴とする請求項１乃至６のうちいずれか１項に記載の生成方法。
【請求項８】
前記ターゲットパターンは、基板上に形成されたラインアンドスペースパターンにおける複数のライン要素の一部を除去するために用いられるパターンを含む、ことを特徴とする請求項１乃至７のうちいずれか１項に記載の生成方法。
【請求項９】
請求項１乃至８のうちいずれか１項に記載の生成方法をコンピュータに実行させるためのプログラム。
【請求項１０】
請求項１乃至８のうちいずれか１項に記載の生成方法を実行する情報処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ターゲットパターンから複数のマスクのパターンデータを生成する生成方法、情報処理装置、およびプログラムに関する。
【背景技術】
【０００２】
半導体デバイス等の製造に用いられる露光装置では、半導体デバイスの微細化に伴い、基板上に形成すべきターゲットパターン（設計パターン）を複数回に分けて基板上に転写する複数回露光（多重露光）が行われている。複数回露光は、露光装置の解像限界よりも小さなピッチで配置された複数のパターン要素を含むターゲットバターンを複数のマスクパターンに分割し、当該複数のマスクパターンを用いてターゲットパターンを基板上に転写する技術である。したがって、複数回露光では、ターゲットパターンを複数のマスクパターンに分割することが必要である。
【０００３】
非特許文献１には、ターゲットパターンを複数のマスクパターンに分割する１つの方法が提案されている。非特許文献１に記載された方法では、ターゲットパターンを構成する各セルの上下に配置されたパワーレールのグループ（色）を固定し、各セルの内側に配置された複数のパターン要素を２つのグループに分割して２つのマスクパターンを生成する。このとき、パワーレールに対する距離が露光装置の解像限界よりも小さいパターン要素を有するセルがある場合には、パワーレールとパターン要素との距離を拡げることなどによって当該セルの再設計が行われる。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Lars Liebmann et.al., “Decomposition-Aware Standard Cell DesignFlows to Enable Double-Patterning Technology”, Proc. of SPIE, USA, 2011,Vol.7974
【発明の概要】
【発明が解決しようとする課題】
【０００５】
非特許文献１には、コスト関数を用いてターゲットパターンを複数のマスクパターンに分割する方法については開示されていない。
【０００６】
そこで、本発明は、コスト関数を用いてターゲットパターンを複数のマスクパターンに分割するための技術を提供することを目的とする。
【課題を解決するための手段】
【０００７】
上記目的を達成するために、本発明の一側面としての生成方法は、ターゲットパターンを複数回に分けて基板上に転写する複数回露光に用いられる複数のマスクのパターンデータを生成する生成方法であって、複数のパターン要素を有するセルのパターンのデータを複数のセルについて取得する第１工程と、前記第１工程で取得したセルごとに、前記複数のパターン要素のそれぞれがいずれかのグループに属するように前記複数のパターン要素を複数のグループに分ける第２工程と、前記複数のセルを配列させる第３工程と、配列された前記複数のセル間でのグループ同士の組み合わせによって１つのマスクのパターンデータが構成され、且つ１つのセル内のグループ同士が互いに異なるマスクのパターンデータに属するように前記複数のセルの各グループを振り分けて、複数のマスクのパターンデータを生成する第４工程と、を含み、前記第２工程では、グループの数とパターン要素同士の距離とを変数としたコスト関数を用いて、閾値より小さい距離で配置されたパターン要素同士が互いに異なるグループに属するように、前記複数のパターン要素を複数のグループに分け、前記第４工程では、マスクの数とグループ同士でのパターン要素の最小距離とを変数としたコスト関数を用いて、グループ間でのパターン要素の最小距離が閾値より小さいグループ同士が互いに異なるマスクのパターンデータに属するように、前記複数のセルの各グループを振り分ける、ことを特徴とする。
【０００８】
本発明の更なる目的又はその他の側面は、以下、添付図面を参照して説明される好ましい実施形態によって明らかにされるであろう。
【発明の効果】
【０００９】
本発明によれば、例えば、コスト関数を用いてターゲットパターンを複数のマスクパターンに分割するための技術を提供することができる。
【図面の簡単な説明】
【００１０】
【図１】本発明に係る生成方法を示すフローチャートである。
【図２】Ｓ１３の具体的な処理を示すフローチャートである。
【図３】Ｓ１５の具体的な処理を示すフローチャートである。
【図４】第１制約条件を説明するための図である。
【図５】Ｓ１５の処理を説明するための図である。
【図６】Ｓ１５の処理を説明するための図である。
【図７】実施例１におけるターゲットパターンを示す図である。
【図８】実施例１においてグループ分割を行った結果を示す図である。
【図９】実施例１において複数のパターンデータを生成した結果を示す図である。
【図１０】実施例２におけるターゲットパターンを示す図である。
【図１１】実施例２においてグループ分割を行った結果を示す図である。
【図１２】実施例２において複数のパターンデータを生成した結果を示す図である。
【発明を実施するための形態】
【００１１】
以下、添付図面を参照して、本発明の好適な実施の形態について説明する。なお、各図において、同一の部材ないし要素については同一の参照番号を付し、重複する説明は省略する。
【００１２】
＜第１実施形態＞
図１は、本発明の第１実施形態における生成方法を示すフローチャートである。当該生成方法は、露光装置等による複数回露光に使用される複数のマスクの各々についてのパターンデータを生成するための方法であり、ＣＰＵ（処理部）やメモリ（記憶部）などを有するコンピュータなどの情報処理装置によって実行されうる。ここで、複数回露光とは、基板上に形成すべきターゲットパターン（目標パターン、設計パターン）を露光装置等により複数回に分けて基板上に転写する方法、即ち、基板上の１つの層（レイヤ）に複数のマスクの各々のパターンを重ねて形成する方法である。また、ターゲットパターンは、複数のパターン要素がそれぞれ配置された複数のスタンダードセルを含む。スタンダードセルは、ＮＯＴ回路やＮＡＮＤ回路などの論理回路の最小単位として標準的に使用される回路パターンを含み、セルライブラリに記憶されている。ターゲットパターンは、その目的に応じてセルライブラリから選択された複数のスタンダードセルを配列させることにより設計されうる。
【００１３】
Ｓ１１では、複数のマスクのパターンデータを生成する対象（分割対象）のターゲットパターンを取得する。Ｓ１２（第１工程）では、Ｓ１１で取得したターゲットパターンを構成するスタンダードセルの種類を特定する。即ち、ターゲットパターンがどのような種類のスタンダードセルによって構成されているのかを特定する。そして、特定された種類のスタンダードセルのパターンのデータをセルライブラリから取得する。ここで、Ｓ１２では、Ｓ１１で取得したターゲットパターンを構成するスタンダードセルの配置も特定しうる。即ち、Ｓ１２では、ターゲットパターンが、どのような種類のスタンダードセルがどのような配置によって構成されているのかを特定しうる。
【００１４】
Ｓ１３（第２工程）では、Ｓ１２でパターンのデータが取得されたスタンダードセルごとに、複数のパターン要素を振り分けた複数のグループを生成する。具体的には、図２に示すフローチャートに従い、グループの数を第１変数としパターン要素同士の距離を第２変数としたコスト関数を用いて、スタンダードセルごとに複数のパターン要素を複数のグループに分ける（振り分ける）。そして、スタンダードセルごとに複数のパターン要素を複数のグループに振り分けた結果を記憶する（スタンダードセルごとに生成した複数のグループを記憶する）。Ｓ１３の具体的な処理については後述する。
【００１５】
Ｓ１４（第３工程）では、Ｓ１２で取得した複数のスタンダードセルを、Ｓ１２で特定したスタンダードセルの配置に基づいて配列させる。Ｓ１５（第４工程）では、Ｓ１３により複数のスタンダードセルの各々について生成された複数のグループから複数のマスクのパターンデータを生成する。複数のマスクのパターンデータは、複数のスタンダードセルのうち少なくとも２つのスタンダードセル間でのグループ同士の組み合わせによって１つのマスクのパターンデータが構成されるように生成される。また、１つのセル内のグループ同士が互いに異なるマスクのパターンデータに属するようにも生成される。具体的には、図３に示すフローチャートに従い、パターンデータの数を第３変数とし、グループ間のパターン要素の最小距離を第４変数としたコスト関数を用いて、複数のパターンデータを生成する。
【００１６】
ここで、Ｓ１３およびＳ１５の具体的な処理について説明する。
【００１７】
まず、Ｓ１３の具体的な処理について、図２を参照しながら説明する。図２は、Ｓ１３の具体的な処理を示すフローチャートである。図２に示すフローチャートは、１つの着目スタンダードセルに対して行われる各工程を示しており、ターゲットパターンを構成する複数のスタンダードセルの各々に対して実行されるものである。
【００１８】
Ｓ１３−１では、着目スタンダードセルにおける複数のパターン要素の配置と複数のパターン要素間の距離とを解析する。また、Ｓ１３−２では、複数のパターン要素を複数のグループに振り分けるための第１制約条件を決定する。第１制約条件は、例えば図４（ａ）に示すように、着目パターン要素２ａの中心からの距離が閾値５より小さい範囲内にある他のパターン要素２ｂは、着目パターン要素２ａとは異なるグループに属さなければならないとの制約条件である。即ち、第１制約条件は、２つのパターン要素間の距離が閾値５より小さい場合には、当該２つのパターン要素を互いに異なるグループに属させるための制約条件であり、図４（ｂ）に示すようなコンフリクトグラフによって表わされうる。図４（ｂ）に示すコンフリクトグラフでは、各点６（vertex）がパターン要素２を表しており、各点間の距離が閾値５より小さくなる場合に線７（edge）によって繋がれる。つまり、線７によって繋がれた点同士（パターン要素同士）は、異なるグループに属さなければならないという制約が課されることを表している。ここで、閾値は、例えば、ターゲットパターンを基板に転写する装置（露光装置）の解像限界以上の値に設定されうる。
【００１９】
Ｓ１３−３では、着目スタンダードセルにおける複数のパターン要素を複数のグループに振り分けるためのコスト関数を設定する。コスト関数は、パターン要素間の距離が閾値以上となるように（好ましくは、当該距離が可能な限り大きくなるように）設定されうる。また、コスト関数は、グループの数が可能な限り少なくなるように（即ち、最小化するように）設定されうる。また、Ｓ１３−４では、Ｓ１３−１で解析したパターン要素間の距離とＳ１３−２で設定した第１制約条件とを用いて、Ｓ１３−３で設定したコスト関数を解くことにより、着目スタンダードセルにおける複数のパターン要素を複数のグループに振り分ける。
【００２０】
次に、Ｓ１５の具体的な処理について、図３を参照しながら説明する。図３は、Ｓ１５の具体的な処理を示すフローチャートである。
【００２１】
Ｓ１５−１では、複数のスタンダードセル間におけるグループ同士のパターン要素の最小距離（最も近いパターン要素同士の距離）の解析を行う。例えば、図５に示すように、スタンダードセル１ａにおける複数のパターン要素２がグループ１ａ１とグループ１ａ２とに分割され、スタンダードセル１ｂにおける複数のパターン要素２がグループ１ｂ１とグループ１ｂ２とに分割された場合を想定する。スタンダードセル１ａおよびスタンダードセル１ｂは互いに隣り合っているものとする。この場合、グループ１ａ１のパターン要素とグループ１ｂ１のパターン要素との最小距離Ｌ１（図６（ａ））、グループ１ａ１のパターン要素とグループ１ｂ２のパターン要素との最小距離Ｌ２（図６（ｂ））が解析される。同様に、グループ１ａ２のパターン要素とグループ１ｂ１のパターン要素との最小距離Ｌ３（図６（ｃ））、グループ１ａ２のパターン要素とグループ１ｂ２のパターン要素との最小距離Ｌ４（図６（ｄ））が解析される。
【００２２】
Ｓ１５−２では、複数のスタンダードセルの各々について選択されたグループ同士を組み合わせるための第２制約条件を設定する。第２制約条件は、２つのグループ間におけるパターン要素の最小距離が閾値より小さい場合には、当該２つのグループが互いに異なるパターンデータ（マスクパターン）に属するようにするための制約条件である。例えば、図６（ａ）において、グループ１ａ１のパターン要素とグループ１ｂ１のパターン要素との最小距離Ｌ１が閾値より小さい場合、グループ１ａ１とグループ１ｂ１とが互いに異なるパターンデータに属さなければならないという制約が課されることとなる。ここで、Ｓ１５−２における閾値は、Ｓ１３−２における閾値と同様の値に設定されるとよい。
【００２３】
Ｓ１５−３では、複数のスタンダードセルの各々について選択されたグループ同士を組み合わせて複数のパターンデータを生成するためのコスト関数を設定する。コスト関数は、互いに組み合わせられるグループ間でのパターン要素の最小距離が閾値以上となるように（好ましくは、当該最小距離が可能な限り大きくなるように）設定されうる。また、コスト関数は、パターンデータの数が可能な限り少なくなるように（即ち、最小化するように）設定されうる。また、Ｓ１５−４では、Ｓ１５−１で解析した最小距離とＳ１５−２で設定した第２制約条件とを用いて、Ｓ１５−３で設定したコスト関数を解くことにより、複数のパターンデータを生成する。
【００２４】
上述した工程を経ることにより、ターゲットパターンを複数のマスクパターンに分割し、複数回露光に用いられる複数のパターンデータを生成することができる。このようなターゲットパターンの分割は、色を塗り分ける作業と似ていることから「彩色問題」とも呼ばれることがある。以下では、ターゲットパターンを分割することを「色を塗り分ける」との表現を用いることがある。
【００２５】
以下に、１次元レイアウト技術において、Ｘ方向のピッチが４６ｎｍ、Ｙ方向のピッチが３６ｎｍのデザインルールを持つ１１ｎｍ＿ｎｏｄｅのターゲットパターンに上記の生成方法を適用する実施例について説明する。以下に説明する実施例では、閾値を、露光装置の解像限界以上の値である９０ｎｍとしている。
【００２６】
［実施例１］
実施例１では、複数のパターン要素として複数のコンタクトホールを有するターゲットパターン１０に上記の生成方法を適用する例について説明する。
【００２７】
Ｓ１１では、分割対象のターゲットパターン１０を取得する。本実施例におけるターゲットパターン１０では、図７（ａ）に示すように、複数のコンタクトホールを複数のパターン要素１２としてそれぞれ含む複数のスタンダードセル１１が配置されている。複数のパターン要素１２は、同一の形状（正方形）および大きさ（寸法）である。Ｓ１２では、取得したターゲットパターン１０を構成する複数のスタンダードセル１１の種類および配置を特定する。本実施例のターゲットパターン１０を構成する複数のスタンダードセル１１は、図７（ｂ）に示すように、６種類のスタンダードセルＡ〜Ｆを含み、スタンダードセルＡが反転したものや、スタンダードセルＥが反転したものも含む。
【００２８】
Ｓ１３では、複数のスタンダードセル１１の各々について、複数のパターン要素１２を複数のグループに振り分ける（以下では、グループ分割と称することがある）。本実施例では、数式として整数計画法を用いる例を説明する。
【００２９】
（１）変数の説明
ｊ：色番号（グループ番号）、１≦ｊ≦ｍ
ｍ：最大色番号
ｙj：色ｊを使うかどうかのバイナリ変数
（使う場合は「１」、使わない場合は「０」）
ｉ：パターン要素の番号
ｘij：ｉ番目のパターン要素においてｊ番目の色を使うかどうかのバイナリ変数
（使う場合は「１」、使わない場合は「０」）
Ｐall：全ての色の中でのパターン要素間の距離の最小値
Ｐj：ｊ番目の色におけるパターン要素間の距離の最小値
Ｄii’j：ｉ番目のパターン要素とｉ’番目のパターン要素ともｊ番目の色で塗るときは「１」、そうでないときは「０とするバイナリ変数
【００３０】
（２）定数の説明
pitchii’：ｉ番目のパターン要素とｉ’番目のパターン要素との距離（間隔）
α：色数のコスト関数の重み
β：全ての色の中におけるパターン要素間の距離のコスト関数の重み
γ：ｊ番目の色におけるパターン要素間の距離のコスト関数の重み
【００３１】
（３）数式の説明
コスト関数は、以下の式（１）に示すように、最小化によって表されうる。ここで、αは正の定数で、βおよびγは共に負の定数であり、最小の色数になり且つパターン要素間の距離の最小値が最大化することを表している。第１項が色数を表しており、第２項および第３項が同色間の最小距離を表している。
minimize
【００３２】
【数１】
2018156042.tif 000003
【００３３】
後に示すように、Σｙj（Σの上の「ｍ」およびΣの下の「ｊ＝１」は省略している。以下同じ。）が色数と等しくなるので、例えば色数が２から３に１増えれば、Σｙj＝２がΣｙj＝３となる。一方で、Ｐallは、分割されたパターン要素間の最小距離（ｎｍ）を表しているので、分割されたパターン要素間の最小距離が１ｎｍ小さくなると、Ｐallは１小さくなる。
【００３４】
本実施例では、色数（グループ数）が可能な限り少なくなるように、かつパターン要素間の距離が可能な限り大きくなるようにマスクパターン分割（グループ分割）を行うことが目的であるため、第１項の重みを大きくすることが好ましい。したがって、αの絶対値は、βおよびγの絶対値に比べて十分に大きくすることが好ましい。例えば、α＝１であれば、β＝−０．００１程度とするとよい。なぜならば、マスクパターン分割を行う必要がある問題では、Ｐallの値は１００前後であるので、ΣｙjやＰallが実質的ないかなる値をとろうとも、第１項の重みが第２項の重みよりも大きくなるからである。
【００３５】
また、全ての色におけるパターン要素間の距離を最大化した上で、個々の色のパターン要素間の最小距離も可能な限り最大化するために第３項を加えている。第３項の重みは、第２項の重みよりも小さくすべきであるため、例えばβ＝−０．００１の場合、γ＝−０．００００１程度にするとよい。ここで、第３項はなくても、本実施例はリソグラフィ・フレンドリなマスクパターン分割プログラムを提供することができる。そのため、第３項はなくてもよい。
【００３６】
コスト関数は、以下の式（２）のように、最大化によっても表すことができる。ここで、αは負の定数で、βおよびγは共に正の定数である。
maximize
【００３７】
【数２】
2018156042.tif 000004
【００３８】
制約条件は、以下の式（３）〜（１０）によって定義される。
subject to
【００３９】
【数３】
2018156042.tif 000005
【００４０】
【数４】
2018156042.tif 000006
【００４１】
【数５】
2018156042.tif 000007
【００４２】
【数６】
2018156042.tif 000008
【００４３】
【数７】
2018156042.tif 000009
【００４４】
【数８】
2018156042.tif 000010
【００４５】
【数９】
2018156042.tif 000011
【００４６】
【数１０】
2018156042.tif 000012
【００４７】
式（３）は、色番号を小さい順に使うことを表す制約条件である。例えば、解が２色になる場合には、ｙ1＝１、ｙ2＝１、ｙ3＝０、ｙ4＝０、・・・などとなる。ｙ1＝１、ｙ2＝０、ｙ3＝１、ｙ4＝０、・・・などとならないようにするための制約条件である。
【００４８】
式（４）は、ｉ番目のパターン要素のフラグｘiには、どれか１色だけ使うことを表す制約条件である。ｉ番目のパターン要素に複数の色が同時に塗られることはない。この制約条件により、例えば、ｉ番目のパターン要素について、ｘi1＝０、ｘi2＝１、ｘi3＝０、ｘi4＝０、・・・などのように、どれか１色の値だけが「１」となる。つまり、ｘi1＝１、ｘi2＝１、ｘi3＝０、ｘi4＝０、・・・などのように、ｉ番目のパターン要素について複数の色（ｘi1、ｘi2）が塗られることがなくなる。
【００４９】
式（５）は、使わない色では塗れないようにする制約条件である。ｊ番目の色番号を使わない（即ち、ｙj＝０である）にも関わらず、ｉ番目のパターン要素でｊ番目の色が使われる（即ち、ｘij＝１となる）ことがないようにするための制約条件である。例えば、解が２色になる場合には、ｙ1＝１、ｙ2＝１、ｙ3＝０、ｙ4＝０、・・・などとなり、３色目のパターン要素は存在しない。この場合において、ｉ番目のパターン要素に３番目の色が割り当てられること、つまりｘi3＝１となることが起きないようにしている。
【００５０】
式（６）は、コンフリクトグラフに基づくマスクパターン分割（グループ分割）の制約条件である。この制約条件は、例えば、コンフリクトグラフにおいて、ｉ番目のパターン要素とｉ’番目のパターン要素とが線で繋がれている場合には、ｉ番目のパターン要素とｉ’番目のパターン要素とは同じ色番号にしてはいけないことを意味している。
【００５１】
式（７）および式（８）は、Ｄii’jの制約条件であり、ｘijとｘi’jとが共に「１」のときにはＤii’j＝１となり、ｘijとｘi’jとの少なくとも一方が「０」のときにはＤii’j＝０となる。つまり、Ｄii’jは、ｘijとｘi’jとの論理積を意味している。例えば、ｉ番目のパターン要素とｉ’番目のパターン要素とが同時にｊ番目の色に割り当てられるときにのみＤii’j＝１となる。
【００５２】
式（９）は、Ｄii’j＝１のときにＰj≦pitchii’となり、Ｐｊの値がパターン要素間の距離の値以下になるようにするための制約条件である。Ｄii’j＝０のときには、Ｐj≦５００となる。「５００」との数値は、Ｄii’j＝０のときに常に実質的にＰjが制約されないようにするために大きい値としている。パターン要素間の距離よりも十分に大きい数として「５００」としているが、これ以外の値、例えば「１０００」であっても式の意味は同じであるので構わない。式（９）を、全てのｉ番目およびｉ’番目のパターン要素について立式することにより、コスト関数を解く際、Ｐjの意味合いとしては、ｊ番目の色のグループを構成するパターン要素間の最小距離となる。
【００５３】
ここで、式（７）、式（８）、式（９）は、全てのパターン要素間の距離を入力する必要はなく、例えばｋ１＞１．０となる距離は無視するなど、パターン要素間の距離により制約条件から除外することも可能である。この場合、計算の高速化を図ることができる。
【００５４】
式（１０）は、Ｐallは、Ｐjの最小値をとることを表す制約条件である。
【００５５】
境界条件は、以下の式（１１）〜（１３）によって定義される。式（１１）は、１色目は使うことを表す境界条件である。式（１２）は、各色におけるパターン要素間の距離の最小値が０以上の値をとることを示す境界条件である。式（１３）は、パターン要素間の距離の最小値が０以上の値をとることを示す境界条件である。
bound
【００５６】
【数１１】
2018156042.tif 000013
【００５７】
【数１２】
2018156042.tif 000014
【００５８】
【数１３】
2018156042.tif 000015
【００５９】
変数は、以下の式（１４）〜（１６）によって定義される。式（１４）〜（１６）で定義された変数はすべてバイナリ変数であり、０もしくは１となる。
【００６０】
【数１４】
2018156042.tif 000016
【００６１】
【数１５】
2018156042.tif 000017
【００６２】
【数１６】
2018156042.tif 000018
【００６３】
上記の式（１）〜（１６）を解くことにより、複数のスタンダードセル１１の各々について、パターン要素間の距離が最大化し且つグループの数が最小化するように、複数のパターン要素１２を複数のグループ（色分け用グループ）に振り分けることができる。図８は、複数のスタンダードセル１１の各々について、複数のパターン要素１２を複数のグループに分割した結果を示す図である。図８において、各パターン要素の下に記載された数字は、グループ番号（色番号）を示している。このように複数のスタンダードセル１１の各々について複数のパターン要素１２が振り分けられた複数のグループは、メモリ（記憶部）に記憶される。
【００６４】
ここで、ターゲットパターン１０を構成する複数のスタンダードセル１１の中に、複数のパターン要素１２の配置が同じである２つのスタンダードセル１１（第１スタンダードセル、第２スタンダードセル）が含まれる場合がある。例えば、図７（ｂ）における、スタンダードセルＡと反転スタンダードセルＡ、および２つの反転スタンダードセルＥのことである。この場合、それら２つのスタンダードセル１１の一方（第１スタンダードセル）について複数のパターン要素１２を複数のグループに振り分けた結果を、他方（第２スタンダードセル）に適用してもよい。これにより、計算時間の短縮を図ることができる。
【００６５】
Ｓ１４では、Ｓ１３で複数のグループがそれぞれ生成された複数のスタンダードセルを配列させる。
【００６６】
Ｓ１５では、複数のスタンダードセル１１の各々について選択されたグループ同士を組み合わせることにより、複数のパターンデータを生成する。本実施例では、数式として整数計画法を用いる例を説明する。また、Ｓ１５で用いられる数式は、以下の３つの相違点を除いて、上述したＳ１３の工程（変数および定数の説明も含む）と同様であり、Ｓ１５においてもＳ１３の式（１）〜（１６）が使用される。
【００６７】
１つ目の相違点は、数式群の中の「ｉ」の意味である。Ｓ１３では、各スタンダードセル１１を構成するパターン要素１２の番号を意味するのに対し、Ｓ１５では、Ｓ１３において複数のパターン要素１２が振り分けられた複数のグループの番号を意味する。即ち、Ｓ１３では、スタンダードセル１１ごとにパターン要素間の距離を評価したのに対し、Ｓ１５では、スタンダードセル１１間におけるグループ同士のパターン要素の最小距離を評価する。
【００６８】
２つ目の相違点は、式の適用対象である。Ｓ１５では、１つのスタンダードセル１１から生成（分割）された複数のグループについては、グループ同士のパターン要素の最小距離の評価は行わない。つまり、Ｓ１５は、１つのスタンダードセル１１から生成された複数のグループの各々と他のスタンダードセル１１から生成された複数のグループの各々とにおけるパターン要素の最小距離を評価する工程である。ここで、Ｓ１５では、全てのスタンダードセル間におけるグループ同士のパターン要素の最小距離の評価を行うのではなく、例えば、互いに隣り合う２つのスタンダードセル間におけるグループ同士のパターン要素の最小距離の評価のみを行ってもよい。これにより、計算時間の短縮を図ることができる。
【００６９】
３つ目の相違点は、式（１）〜（１６）の式に加え、以下の式（１７）も使用することである。式（１７）は、１つのグループ内におけるパターン要素の全てを１枚のマスクパターンに含めることを表す制約条件である。ここで、ｋは、スタンダードセル１１のグループ番号を示し、ｌは、グループの数（色数）を示している。例えば、図７に示すように複数のパターン要素１２が１８個のグループに振り分けた場合では、ｘ11＋ｘ21＝１、ｘ12＋ｘ22＝１、ｘ31＋ｘ32＝１、ｘ41＋ｘ42＝１、・・・ｘ17 1＋ｘ18 1＝１、ｘ17 2＋ｘ18 2＝１と表される。
【００７０】
【数１７】
2018156042.tif 000019
【００７１】
上記の式（１）〜（１７）を解くことにより、互いに組み合わせられるグループ同士のパターン要素の最小距離が最大化し且つパターンデータの数が最小化するように、複数のマスクのパターンデータを生成することができる。図９は、複数のスタンダードセル１１の各々について選択されたグループ同士を組み合わせることにより複数のマスクのパターンデータを生成した結果を示す図である。本実施例では、図９に示すように、ターゲットパターン１０から、濃色で表された複数のパターン要素１２ａを有するパターンデータと、淡色で表された複数のパターン要素１２ｂを有するパターンデータとが生成される。
【００７２】
ここで、分割前後におけるパターン要素間の最小距離について説明する。パターン要素間の最小距離は、分割前では４３ｎｍであったのに対し、分割後では９２ｎｍとすることができた。これは、ＮＡ１．３５を有するＡｒＦ液浸露光装置で考えると、ｋ１が０．１５から０．３２になったことを意味し、複数回露光の各々において露光装置の解像限界以上の最小距離を確保できていることを示している。
【００７３】
［実施例２］
実施例２では、複数のパターン要素として複数のカット要素（Ｍ１カットパターン）を有するターゲットパターン２０に上記の生成方法を適用する例について説明する。カット要素とは、基板上に形成された単一ピッチのラインアンドスペースパターンにおけるライン要素を部分的に除去して回路パターンを作製する方法において、当該ライン要素の一部を除去するために用いられるものである。ここで、実施例２で用いられる数式等は実施例１と同様であるため、ここでは数式等の説明を省略する。
【００７４】
図１０（ａ）は、Ｓ１１において取得されうるターゲットパターン２０を示す図である。本実施例におけるターゲットパターン２０では、複数のカット要素を複数のパターン要素２２としてそれぞれ含む複数のスタンダードセル２１が配置されている。複数のパターン要素２２は、同一の形状（長方形）および大きさ（寸法）である。また、図１０（ｂ）は、Ｓ１２において特定された複数のスタンダードセル２１の種類および配置を示す図である。本実施例におけるターゲットパターン２０を構成する複数のスタンダードセル２１は、６種類のスタンダードセルＧ〜Ｌを含み、スタンダードセルＧが反転したものや、スタンダードセルＫが反転したものも含む。
【００７５】
図１１は、Ｓ１３の工程を経ることにより、複数のスタンダードセル２１の各々について、複数のパターン要素２２を複数のグループに分割した結果を示す図である。図１１において、各パターン要素２２の下に記載された数字は、グループ番号（色番号）を示している。本実施例では、実施例１と同様に、式（１）〜（１６）を用いた整数計画法によりグループ分割が行われうる。また、図１２は、複数のスタンダードセル２１の各々について選択されたグループ同士を組み合わせることにより複数のパターンデータを生成した結果を示す図である。本実施例では、実施例１と同様に、式（１）〜（１７）を用いて複数のパターンデータが生成され、濃色で表された複数のパターン要素２２ａを有するパターンデータと、淡色で表された複数のパターン要素２２ｂを有するパターンデータとが生成される。
【００７６】
ここで、分割前後におけるパターン要素間の最小距離について説明する。パターン要素間の最小距離は、分割前では４６ｎｍであったのに対し、分割後では９２ｎｍとすることができた。これは、ＮＡ１．３５を有するＡｒＦ液浸露光装置で考えると、ｋ１を０．１６から０．３２になったことを意味し、複数回露光の各々において露光装置の解像限界以上の最小距離を確保できていることを示している。
【００７７】
＜その他の実施形態＞
本発明は、上述の実施形態の１以上の機能を実現するプログラムを、ネットワーク又は記憶媒体を介してシステム又は装置に供給し、そのシステム又は装置のコンピュータにおける１つ以上のプロセッサーがプログラムを読出し実行する処理でも実現可能である。また、１以上の機能を実現する回路（例えば、ＡＳＩＣ）によっても実現可能である。
【００７８】
以上、本発明の好ましい実施形態について説明したが、本発明はこれらの実施形態に限定されないことはいうまでもなく、その要旨の範囲内で種々の変形および変更が可能である。
【符号の説明】
【００７９】
１０，２０：ターゲットパターン
１，１１，２１：スタンダードセル
２，１２，２２：パターン要素
【図１】
2018156042.tif 000020
【図２】
2018156042.tif 000021
【図３】
2018156042.tif 000022
【図４】
2018156042.tif 000023
【図５】
2018156042.tif 000024
【図６】
2018156042.tif 000025
【図７】
2018156042.tif 000026
【図８】
2018156042.tif 000027
【図９】
2018156042.tif 000028
【図１０】
2018156042.tif 000029
【図１１】
2018156042.tif 000030
【図１２】
2018156042.tif 000031