パターンデータ処理方法、装置、プログラム及び記録媒体
【目的】厳しい設計制約を設けることなく、階層化された複数のセルを有するパターンデータに対して所定の処理を効率的に行う。
【構成】共通侵入領域算出処理部２０５は各セル毎に外部パターンが当該セルに侵入する領域を共通侵入領域として当該セルに関連付ける。影響範囲算出処理部２１４は共通侵入領域に基づき、パターンデータに対する所定の処理の内容に応じて、各セルの中で外部パターンとともに前記所定の処理を行う必要のある領域を当該セルの影響範囲として算出する。共通データ領域算出処理部２１５はセルのデータ存在領域から当該セルの影響範囲を除外した領域を当該セルの共通データ領域として算出する。図形処理部２０６は各セルの共通データ領域については前記所定の処理を一度行い、影響範囲については当該セルに侵入する外部パターンとともに前記所定の処理を行うことにより、パターンデータに対する前記所定の処理を行う。
【構成】共通侵入領域算出処理部２０５は各セル毎に外部パターンが当該セルに侵入する領域を共通侵入領域として当該セルに関連付ける。影響範囲算出処理部２１４は共通侵入領域に基づき、パターンデータに対する所定の処理の内容に応じて、各セルの中で外部パターンとともに前記所定の処理を行う必要のある領域を当該セルの影響範囲として算出する。共通データ領域算出処理部２１５はセルのデータ存在領域から当該セルの影響範囲を除外した領域を当該セルの共通データ領域として算出する。図形処理部２０６は各セルの共通データ領域については前記所定の処理を一度行い、影響範囲については当該セルに侵入する外部パターンとともに前記所定の処理を行うことにより、パターンデータに対する前記所定の処理を行う。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、階層化された複数のセルを有するパターンデータに対して、論理演算処理等の予め定めた所定の処理を行うパターンデータ処理方法、パターンデータ処理装置、前記パターンデータ処理方法をコンピュータに実行させるためのパターンデータ処理用プログラム及び前記パターンデータ処理用プログラムを記録したコンピュータ読み取り可能な記録媒体に関する。
【背景技術】
【０００２】
従来から、携帯電話の表示パネルやＦＰＤ（Flat Panel Display）等の表示装置のマスクパターン設計、ＬＳＩ（Large Scale Integration circuit）設計、ＭＥＭＳ（Micro Electro Mechanical Systems）設計、機構設計等、多岐の分野にわたってＣＡＤ（Computer Aided Design）が利用されている。
ＬＳＩやＭＥＭＳ、ＦＰＤ等において、素子や配線パターン等の構成要素のレイアウトパターンを複数のレイヤに分けたパターンデータによって構成し、前記パターンデータを基に、マスクを使用したフォトリソグラフィや印刷技術を用いて最終製品を製造することは、近年の大量生産を支える基本技術となっている。
【０００３】
レイアウトパターンは、最終製品上に形成される形状を示す設計の最終データであり、設計上及び製造上から来る最小の線幅や間隔等の各種ルールを満たす必要があるため、レイアウトパターンの検査処理等のパターンデータ処理が必要である。また、製造のために、レイアウトパターンの重複除去処理や、サイジングをはじめとするデータ変更処理等の種々のパターンデータ処理が必要不可欠となっている。
【０００４】
そのために、ＬＳＩやＦＰＤ等のレイアウトパターン(換言すれば、マスクパターン)データが製造上必要なルールを満たすことの検証(デザインルールチェック)を行う場合や、電子線描画装置のための描画データを作成する場合等に、パターンデータの検証処理や変更処理等のパターンデータに対する所定の処理を行うために、種々のパターンデータ処理方法やパターンデータ処理装置が利用されている。
【０００５】
特にＬＳＩでは、近年の製造プロセスの微細化に伴うデータ規模の増大が著しく、パターンデータ処理の高速化が課題となっている。この解決策として、パターンデータが階層構造を有する複数の階層セルを有するように構成し、各セルの階層構造に着目して、同一のデータは境界領域を除き一度だけ処理することによって処理の効率化を図るようにした階層処理方法が開発されている（例えば、特許文献１、２参照）。
【０００６】
しかしながら、前記特許文献１、２に記載された処理方法では、各階層セル間で各階層セルのパターンが重複しない領域或いは各階層セル間で各階層のパターンが重複する領域を、下位階層セル内部の周囲領域とするように設計制約を設けている。そして、係る厳しい設計制約を前提として所定のパターンデータ処理を行うようにしている。前記制約条件を満たすパターンのみの場合は処理の効率化を図り得るが、前記制約条件を満たさないパターンが存在する場合、処理効率が著しく低下したり、処理不能に陥る可能性がある。
【０００７】
ＬＳＩのパターンは、一般に階層セル間で大きく重複するものではないが、階層セル間のパターン重複禁止領域や重複領域をセル内部の周囲領域に限定することは、レイアウト設計上厳しい制約となり、設計結果のチップサイズ増大や設計期間の増加など大きな弊害となってしまう。
一方、パターンのサイジング処理や寸法チェック処理など階層セル間のパターンの影響が距離に依存する処理は、前記特許文献１、２に記載された処理方法でも実現可能である。しかしながら、例えば重複関係のある図形を選択する等のトポロジーを使用した対象選択処理では、階層間の影響を距離で限定できないため、正確な結果を得ることができないという問題がある。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開平６−２１６０１２号公報
【特許文献２】特開２００２−１９７１３０号公報
【発明の開示】
【発明が解決しようとする課題】
【０００９】
本発明は、前述したような厳しい設計制約を設けることなく、階層化された複数のセルを有するパターンデータに対して論理演算処理等の予め定めた所定の処理を効率的に行うことを課題としている。
【課題を解決するための手段】
【００１０】
本発明の第１の視点によれば、階層化された複数のセルを有するパターンデータに対して予め定めた所定の処理を行うパターンデータ処理方法において、セル毎に外部から当該セルに侵入する外部パターンを検出し、前記外部パターンが当該セルに侵入する領域を共通侵入領域として当該セルに関連付ける共通侵入領域算出ステップと、セルに関連付けられた前記共通侵入領域に基づいて、前記所定の処理の内容に応じて、当該セルの中で前記外部パターンとともに前記所定の処理を行う必要のある領域を当該セルの影響範囲として算出する影響範囲算出ステップと、セルのデータ存在領域から当該セルの影響範囲を除外した領域を当該セルの共通データ領域として算出する共通データ領域算出ステップと、前記各セルの共通データ領域については前記所定の処理を一度行うと共に前記影響範囲については当該セルに侵入する前記外部パターンとともに前記所定の処理を行うことにより、前記パターンデータに対する前記所定の処理を行うパターンデータ処理ステップとを備えて成ることを特徴とするパターンデータ処理方法が提供される。
【００１１】
また、本発明の第２の視点によれば、階層化された複数のセルを有するパターンデータに対して予め定めた所定の処理を行うパターンデータ処理装置において、セル毎に外部から当該セルに侵入する外部パターンを検出し、前記外部パターンが当該セルに侵入する領域を共通侵入領域として当該セルに関連付ける共通侵入領域算出手段と、セルに関連付けられた前記共通侵入領域に基づいて、前記所定の処理の内容に応じて、当該セルの中で前記外部パターンとともに前記所定の処理を行う必要のある領域を当該セルの影響範囲として算出する影響範囲算出手段と、セルのデータ存在領域から当該セルの影響範囲を除外した領域を当該セルの共通データ領域として算出する共通データ領域算出手段と、前記各セルの共通データ領域については前記所定の処理を一度行うと共に前記影響範囲については当該セルに侵入する前記外部パターンとともに前記所定の処理を行うことにより、前記パターンデータに対する前記所定の処理を行うパターンデータ処理手段とを備えて成ることを特徴とするパターンデータ処理装置が提供される。
【００１２】
また、本発明の第３の視点によれば、コンピュータに階層化された複数のセルを有するパターンデータに対して予め定めた所定の処理を実行させるためのパターンデータ処理用プログラムにおいて、本発明に係るパターンデータ処理方法をコンピュータに実行させることを特徴とするパターンデータ処理用プログラムが提供される。
【００１３】
また、本発明の第４の視点によれば、コンピュータに本発明のパターンデータ処理方法を実行させるためのパターンデータ処理用プログラムを記録したコンピュータ読み取り可能な記録媒体が提供される。
【発明の効果】
【００１４】
本発明のパターンデータ処理方法によれば、厳しい設計制約を設けることなく、階層化された複数のセルを有するパターンデータに対して論理演算処理等の予め定めた所定の処理を効率的に行うことが可能になる。
また、本発明のパターンデータ処理装置によれば、厳しい設計制約を設けることなく、階層化された複数のセルを有するパターンデータに対して論理演算処理等の予め定めた所定の処理を効率的に行うことが可能になる。
また、コンピュータが本発明のパターンデータ処理用プログラムを実行することにより、厳しい設計制約を設けることなく、階層化された複数のセルを有するパターンデータに対して論理演算処理等の予め定めた所定の処理を効率的に行うことが可能になる。
また、本発明の記録媒体に記録したパターンデータ処理用プログラムをコンピュータに実行させることにより、厳しい設計制約を設けることなく階層化された複数のセルを有するパターンデータに対して論理演算処理等の予め定めた所定の処理を効率的に行うことが可能なパターンデータ処理装置を構築することが可能になる。
【図面の簡単な説明】
【００１５】
【図１】本発明の原理を説明するための説明図である。
【図２】本発明の実施の形態に係るパターンデータ処理装置のブロック図である。
【図３】本発明の実施の形態におけるセル間重複パターン検出処理を示すフローチャートである。
【図４】本発明の実施の形態における共通侵入領域検出処理を示すフローチャートである。
【図５】本発明の実施の形態におけるセルを示す図である。
【図６】本発明の実施の形態におけるセルの階層構造を示す図である。
【図７】本発明の実施の形態におけるセル間重複パターン検出処理を示す説明図である。
【図８】本発明の実施の形態におけるセル間重複パターン検出処理を示す説明図である。
【図９】本発明の実施の形態におけるセル間重複パターン検出処理を示す説明図である。
【図１０】本発明の実施の形態におけるセル間重複パターン検出処理を示す説明図である。
【図１１】本発明の実施の形態におけるセル間重複パターン検出処理を示す説明図である。
【図１２】本発明の実施の形態におけるセル間重複パターン検出処理を示す説明図である。
【図１３】本発明の実施の形態におけるセル間重複パターン検出処理を示す説明図である。
【図１４】本発明の実施の形態における共通侵入領域検出処理を示す説明図である。
【図１５】本発明の実施の形態における共通侵入領域検出処理を示す説明図である。
【図１６】本発明の実施の形態における共通侵入領域検出処理を示す説明図である。
【図１７】本発明の実施の形態における共通侵入領域検出処理を示す説明図である。
【図１８】本発明の実施の形態におけるＡＮＤ処理を示すフローチャートである。
【図１９】本発明の実施の形態におけるＡＮＤ処理を示す説明図である。
【図２０】本発明の実施の形態におけるＡＮＤ処理を示す説明図である。
【図２１】本発明の実施の形態におけるＡＮＤ処理を示す説明図である。
【図２２】本発明の実施の形態におけるＡＮＤ処理を示す説明図である。
【図２３】本発明の実施の形態におけるＡＮＤ処理を示す説明図である。
【図２４】本発明の実施の形態におけるＡＮＤ処理を示す説明図である。
【図２５】本発明の実施の形態におけるＡＮＤ処理を示す説明図である。
【図２６】本発明の実施の形態におけるＳＵＢ処理を示す説明図である。
【図２７】本発明の実施の形態におけるＳＵＢ処理を示す説明図である。
【図２８】本発明の実施の形態におけるＳＵＢ処理を示す説明図である。
【図２９】本発明の実施の形態におけるＳＵＢ処理を示す説明図である。
【発明を実施するための形態】
【００１６】
本発明の実施の形態の概要を説明すると、階層化された複数のセルを有するパターンデータに対して論理演算処理等の予め定めた所定の処理（パターンデータ処理）を行う場合、先ず、パターンデータのレイヤ毎に、各セルの外部から各セル内に実際に侵入するパターン（外部パターン）の形状を検出する。
セルはパターンの集合であり又パターンデータの構成要素である。各セルは、自セルの内部に他のセルを参照することによって階層構造を成している。パターンデータは前記階層化された複数のセルによって構成される。
【００１７】
尚、或るセルへのパターンの侵入とは、「参照点ごとに、或るセルと前記或るセルの傘下にある全ての下位階層セルとを除外した残り全てのパターンのうちの、いずれかのパターンが、前記或るセルのデータが存在する領域（データ存在領域）に対して重なること」を意味している。ここで、「或るセルの全ての下位階層セル」とは、「或るセルの傘下にある全ての下位の階層セル」の意味である。「或るセルの傘下にある下位階層セル」とは、「下位階層セルから順に上位階層へ辿って行ったとき、前記或るセルに到達することができる場合の当該下位階層セル」を意味している。
【００１８】
次に、各セルに侵入する前記外部パターンの形状のＯＲ領域（以下、共通侵入領域と称す。）を求める。次に、前記共通侵入領域を基に、前記外部パターンの影響でパターンデータ処理の結果が不正確になる（換言すれば、外部パターンが異なることによってパターンデータ処理の結果が異なる）可能性がある各セル内領域（以下、影響範囲と称す。）を抽出する。前記影響範囲はパターン処理の内容に応じて定められる。このようにして、前記外部パターンの形状を基に前記影響範囲を求める。
【００１９】
次に、前記処理結果が異なる可能性のあるセル内のパターンは、影響範囲を元に抽出することができる。したがって、前記処理結果が異なる可能性のあるセル内のパターンは、前記外部パターンとマージして前記所定のパターンデータ処理を行う。前記処理結果が共通となる（換言すれば、外パターンが異なってもパターンデータ処理の結果が同じになる）セルのパターンについても影響範囲を元に抽出することができ、これについては単独で一度だけ前記所定のパターンデータ処理を行う。
【００２０】
尚、影響範囲は、セル内の演算結果が外部パターンの影響で変動する領域、換言すればセル内パターンの影響で外部の演算結果が変動する領域である。即ち、影響範囲は、パターンデータ全体について最終的に正しいパターンデータ処理の結果を得るためには、外部パターンとセル内のパターンをマージした上で演算することが必要なセル内領域を意味している。
【００２１】
これにより、パターンデータ全体に対して所定のパターンデータ処理が行われる。このようにして、セル間のパターン重複領域をセル内周囲の領域に設定することなく、所定のパターンデータ処理を行うことが可能となる。したがって、厳しい設計制約を設けることなく、階層化された複数のセルを有するパターンデータに対して、論理演算処理等の予め定めた所定の処理を効率的に行うことが可能になる。
【００２２】
パターンデータ処理には、パターンの論理演算を行う論理演算処理、パターンの大きさやパターン間の間隔等を変更する変更処理、パターンの大きさやパターン間の間隔等を検査する検証処理、パターンの形状やパターン間の重複関係でパターンを選択する選択処理などがある。より具体的には、ＡＮＤ処理やＯＲ処理等の論理演算処理、配線や素子のパターンのサイズを変更するサイジング処理、パターンや素子等の寸法チェック処理、あるいは重複するパターンだけの抽出等を行う対象選択処理等、種々のパターンデータ処理がある。
パターンデータ処理の内容に応じて影響範囲は異なることになる。しかしながら、いずれのパターンデータ処理の場合でも、パターンデータ処理の内容に応じて、外部パターンの形状を基に前記影響範囲を決定することが可能である。
【００２３】
本発明の実施の形態の概要について更に詳しく説明すると、仮に、或るセルが参照している複数の同一構成のセル（参照点）に対して、参照点毎にセル内に外部パターンが侵入する領域（パターン侵入領域）を基にしてパターンデータ処理を行うとした場合には、参照点数に応じたオーダーの処理を行うことになり、各セルの全てのパターンを展開して処理することと同等の膨大なデータ処理量になってしまう。
一方、参照点の一箇所でもパターン侵入領域が存在すると、影響範囲に対するパターンデータ処理の結果は前記パターン侵入領域の影響によって変わるため、全ての参照点で同一の処理結果が得られるわけではない。しかしながら、この影響範囲を除いた領域に対するパターンデータ処理の結果は、全ての参照点で同一となる。
【００２４】
階層処理で必要なのは、同一の結果となるデータは一度だけの処理とすることであるから本発明の実施の形態では、先ず、セル毎に全ての参照点で外部パターンが侵入する形状のＯＲ領域（以下、共通侵入領域と称す。）を求めておく。次に、前記共通侵入領域に基づいて、パターンデータ処理の内容に応じた影響範囲を算出し、セル内のパターンデータが存在し得る最大領域から前記影響範囲を除いた領域（以下、共通データ領域と称す。）についてパターンデータ処理を行う。
【００２５】
前記共通データ領域についてのパターンデータ処理の結果をこの階層セルの処理結果とすることにより、共通データ領域についてのパターンデータ処理は一度だけの処理とすることが可能となる。
前記影響範囲については、各セル毎に、外部パターンにマージして個別にパターンデータ処理を行う。このように共通データ領域と影響範囲に分けてパターンデータ処理を行い、それらの処理結果を統合することにより、パターンデータ全体についてのパターンデータ処理を行うことが可能になる。
【００２６】
前記影響範囲は、パターンデータ処理の結果として得られるパターン形状が、共通侵入領域に含まれる外部パターンの影響を受けて変更される可能性のある、セル内の最大領域である。同様に共通データ領域は、共通侵入領域に含まれる外部パターンの影響を受けずに、パターンデータ処理を行うことが可能な領域であり、パターンデータ処理結果として得られるパターン形状が、外部パターンによって変更されることがないセル内の最大領域である。
セルの共通データ領域は、当該セルのデータが存在する領域であるデータ存在領域から当該セルの影響範囲を除外した領域である。
【００２７】
例えば、ＡＮＤ処理、ＯＲ処理、ＳＵＢ処理等の論理演算処理では、共通侵入領域の内側領域の処理結果のみが外部パターンによって変更され、共通侵入領域の外側領域の処理結果が変更されることはない。
また、ＷＩＤＴＨ処理（パターンの幅を指定した検証）、ＳＰＡＣＥ処理（パターンの間隔を指定した検証）、ＥＮＣ処理（包含余裕を指定した検証）等の寸法チェック処理やサイジング処理では、共通侵入領域からルールによって指定した幅に応じた外側の領域までの処理結果が変更される可能性がある。例えば、共通侵入領域からルール値の範囲は一般に影響を受けるが、コーナー部の仕様としてルール値の√２倍の距離まで外部パターンが影響する場合、これを考慮して影響範囲を算出する必要がある。
【００２８】
また、指定レイヤと重複するパターンを抽出するなどの対象選択処理では、共通侵入領域と重複するセル内パターンは、外部パターンの有無により選択あるいは非選択の演算結果が異なる可能性があるため、前記共通侵入領域と重複するセル内パターン全体が影響範囲となる。
【００２９】
このように、共通侵入領域が同一の場合でも、パターンデータ処理の内容によって影響範囲は異なることになる。共通侵入領域に含まれる外部パタ−ンの形状によってパターンデータ処理の結果が異なってしまう最大の領域を考慮して影響範囲を求めることにより、共通侵入領域に基づいてパターンデータ処理の内容に応じた影響範囲を容易に求めることが可能である。
【００３０】
例えば、多くのパターンデータ処理内容の影響範囲は距離により規定でき、この場合共通侵入領域を一定距離拡大した領域を影響範囲とすることができる。また、外部パターンが接触や重複、包含など接続することでパターンデータ処理内容の結果が異なる場合、共通侵入領域が接触するパターン全体により影響範囲を規定することができる。このように、パターンデータ処理内容により影響範囲を規定する項目を明確化し、この項目が最大となる形状を共通侵入領域に含まれる外部パタ−ンの形状に仮定することで、影響範囲を求めることができる。
【００３１】
影響範囲についてパターンデータ処理する場合、影響範囲内の処理結果を決定するために必要な範囲のセル内パターン（以下、境界パターンと称す。）を例えばデータ展開し、セル外のパターンとマージして個別処理することで、各参照点の個別のパターンデータ処理結果を得ることができる。尚、共通侵入領域からの影響と同様に、影響範囲内の処理結果は、影響範囲の近傍のパターンから演算内容に応じた影響を受ける。このため、前記境界パターンは影響範囲の外部のパターンを含む場合もある。この範囲を求める方法は、共通侵入領域から影響範囲を求める方法と同様である。
【００３２】
このとき、境界パターンの形状により、セル内の処理結果に比べてパターンが追加される部分と削除される部分がある。パターンが追加される部分は、上位階層セルに処理結果のパターンとして追加すればよいことから、セル内の処理結果に影響はない。パターンが削除される部分は、上位階層セルで削除することができないため、削除される可能性のある部分をセル内の結果から予め削除しておき、セル内の該当部分と合わせた結果を上位階層セル内に作成する等の方法をとることになる。
【００３３】
ここで、実際のパターンデータ処理方法は、必ずしも前記のように共通データ領域に対応する階層のパターンデータ処理と、展開された共通侵入領域に基づく影響範囲のパターンデータ処理とに限定するものではない。影響範囲のパターンデータ処理結果に対し、参照点ごとに新たなセルとしこれを参照することで、同一の処理結果を共通化する方法を採用することや、あるいは共通データ領域とあわせた新たなセルとする方法を採用することも可能である。
【００３４】
また、共通侵入領域に基づく影響範囲は、参照点毎に個別処理が必要となるため、処理時間短縮のためにはできるだけ少ないことが望ましい。このため、パターンデータ処理の内容をより詳細に考慮して影響範囲を狭い範囲にするような算出方法を採用することは可能である。
【００３５】
また、各セルにおいて、当該セル内の下位階層を含めた全てのデータを包含する領域（データ存在領域）は、当該セルにおいて全てのレイヤで共通であるようにしている。データ存在領域は、全てのデータを包含するＸＹ軸方向に沿った長方形が基本であるが、
・データが存在しない大面積の領域がある場合、データが存在しない部分を除く
・距離に依存する処理に対して、その影響距離分拡張する
・領域の外部の重複関係が検出できない場合、外部を全て重複すると扱う
等のバリエーションは可能である。
以上により、重複領域に厳しい制約を設けることなく、正確で効率的な階層処理を実現することが可能となる。
【００３６】
以下、本発明の実施の形態について、図面を参照しながら詳細に説明する。
図１は、本発明の実施の形態の原理を説明するための説明図で、ＬＳＩ（Large Scale Integration circuit）の例を示している。
パターンデータは、フォトリソグラフィで使用するマスクに対応した複数のレイヤ構造を持っており、パターンデータ処理もこのレイヤを基準に実行する。
【００３７】
このため、パターンデータを構成する各セルのレイヤ毎に、セルの外部からパターン（外部パターン）が侵入した領域を共通侵入領域として保持する。共通侵入領域は、外部パターンが侵入した領域の個々の形状は不要であり、侵入した個々の領域を結合し、それを枠取りした形状でよい。即ち、階層セルの共通侵入領域は、外部パターンのうちの当該階層セルのデータ存在領域に侵入した部分をＯＲ処理することによって得られる領域である。次に、パターンデータ処理の処理内容に応じて、共通侵入領域を基にして、外部パターンと一緒にパターンデータ処理する必要のある領域（影響範囲）を求める。
【００３８】
影響範囲の処理は、階層セル内のパターンのうち影響範囲の処理に必要な範囲のパターンを、上位階層セルに展開する等して、外部パターンと一緒に個別処理する。セルのデータ存在領域から前記影響範囲を除いた部分は、セルの外部の処理とは無関係に独立して処理可能な部分（共通データ領域）である。この部分は、一度だけ処理しておけば、同一セルの共通データ領域に関する処理が、パターンデータにおける他の領域においても必要な場合には、当該処理結果を利用することができる。
【００３９】
共通侵入領域が同じ場合でも、影響範囲の算出方法はパターンデータ処理の内容に応じた演算処理毎に異なるが、影響範囲は共通侵入領域を基準に求めることができる。したがって、共通侵入領域を一度求めておけば、階層処理を行う場合に、実際にパターンデータ処理に影響を与える影響範囲や共通データ領域を容易に求めることが可能になる。影響範囲については個別にパターンデータ処理すると共に、共通データ領域については一度だけパターンデータ処理することにより、厳しい制約を設けることなく、正確で効率的な階層処理を実現することが可能となる。
【００４０】
図１（ｉ）において、セルａ、セルｂは階層構造を有しており、セルａは上位階層セル（例えばトップ（Ｔｏｐ）セル）、セルｂは下位階層セルである。セルａは２つのセルｂを参照点として有すると共に、配線等のパターン１０１、１０２を有している。パターン１０１、１０２は、セルｂから見れば、外部からセルｂ内へ侵入する外部パターンである。
尚、各セルに含まれるパターン等のデータは各セルのデータ存在領域内に存在するが、図１の例では、各セルａ、セルｂのデータ存在領域は実線の長方形枠で囲まれた領域である。以下の各図においても、セルのデータ存在領域は実線の長方形枠で囲まれた領域としているが、他の形状の枠をデータ存在領域とすることができる。
【００４１】
図１（ｉｉ）に示すように、パターン１０１、１０２のうち各セルｂに侵入する部分のＯＲ処理を行うことにより、共通侵入領域１０３が得られる。共通侵入領域１０３は、参照点（図１の例ではセルｂ）のいずれかに外部のパターン１０１、１０２が侵入する領域である。共通侵入領域１０３を基に、パターンデータ処理の演算内容に応じたセルｂの影響範囲が決定できる。
【００４２】
影響範囲は、パターンデータ処理が例えばＡＮＤ処理やＯＲ処理等の論理演算処理の場合には、共通侵入領域１０３に含まれる領域となる。パターンデータ処理がサイジング処理や寸法チェック処理の場合には、影響範囲は、共通侵入領域を所定サイズ幅拡大した領域となる。また、パターンデータ処理が対象選択処理の場合には、影響範囲は、共通侵入領域内に外部パターンが存在することによってパターンデータ処理の結果（選択又は非選択）が変化するパターン全体の領域となる。
【００４３】
影響範囲は、上位階層セルａの演算処理を行う際に上位階層セルａとマージして演算が必要な領域である。下位階層セルｂのデータ存在領域から影響範囲を除いた部分は、他の処理から独立してパターンデータ処理可能な領域（共通データ領域）である。
このように、本発明の実施の形態は、各セル毎に共通侵入領域１０３を求めておき、共通侵入領域１０３を用いて論理演算処理等の各種のパターンデータ処理を行うことを特徴とするものである。
【００４４】
また、本発明の実施の形態は、各セル毎に求めた共通侵入領域を基に、パターンデータ処理の内容に応じた影響範囲を求め、影響範囲については上位に展開して個別にパターンデータ処理を行い、セルのデータ存在領域から影響範囲を除外した共通データ領域については一度だけパターンデータ処理を行うことにより、パターンデータ全体のパターンデータ処理を行うことを特徴とするものである。
【００４５】
即ち、本発明の実施の形態では、セルの階層構造に着目して、各セルの参照点毎に、当該セルと前記当該セルの傘下にある全ての下位階層セルとを除外した残り全てのパターンから当該セルのデータ存在領域に侵入するパターン（これらのパターンを纏めて外部パターンと称す。）を検出して、各セルに外部パターンが侵入する全ての領域の和を当該セルの共通侵入領域として関連付けて持たせておく。
【００４６】
パターンデータ処理を行う際に、共通侵入領域及びパターンデータ処理の内容に応じて影響範囲及び共通データ領域を算出する。前記共通データ領域については一度のみのパターンデータ処理とすることにより、同一セルが複数使用されている場合にパターンデータ処理回数を低減する。また、前記影響範囲についてはセル毎に個別にパターンデータ処理を行う。
これにより、パターンデータ処理全体に対する処理が可能になるため、厳しい設計制約を設けることなく、効率的に階層的パターンデータ処理を実現できる。
【００４７】
以下、本発明の実施の形態に係るパターンデータ処理方法、パターンデータ処理装置、前記パターンデータ処理方法をコンピュータに実行させるためのパターンデータ処理用プログラム及び前記パターンデータ処理用プログラムを記録したコンピュータ読み取り可能な記録媒体について、図面に沿って詳細に説明する。尚、各図において、同一部分には同一符号を付している。
【００４８】
図２は、本発明の実施の形態に係るパターンデータ処理装置２００のブロック図である。
図２において、パターンデータ処理装置２００は、コンピュータによって構成することができ、ＣＡＤ（Computer Aided Design）によって作成したパターンデータ２１７に対する論理演算等の各種処理を行う機能を有している。本実施の形態では、パターンデータとしてＬＳＩのパターンデータ２１７の例を示している。パターンデータ２１７は、階層化された複数のセルから成るセルデータ２１１を有している。
【００４９】
セルのデータ（セルデータ）はレイアウトデータとも称され、セルデータ２１１は複数のセルデータによって構成されている。各セルのセルデータは、配線パターンや電子回路素子等の構成要素（レイアウト図形要素）の多角形の図形データと当該多角形の座標データを有しており又、参照するセルのデータとして、セル名称、座標、反転・回転・繰り返し等のデータを有している。
【００５０】
パターンデータ２１７は複数のセルデータによって構成され、セルデータ２１１の一部若しくは全部の複数のセルデータによって構成される。複数のセルデータ２１１の中から、ＬＳＩや表示装置のパターンデータ処理対象を表すのに必要な複数のセルデータが組み合わされてパターンデータ２１７が構成されている。
【００５１】
パターンデータ処理装置２００は、中央処理装置（ＣＰＵ）によって構成されパターンデータ処理を行うパターンデータ処理部２０１、液晶表示装置（ＬＣＤ）等によって構成された表示部２０２、マウスやキーボードを有する操作部２０３、パターンデータ処理部２０１が実行するプログラムや各種データを記憶する記憶部２０４を備えている。
記憶部２０４は磁気ディスク等によって構成されている。記憶部２０４には、処理対象のパターンデータ２１７がパターンデータ処理を行う前に格納される。
【００５２】
ＣＤ−ＲＯＭ（Compact Disc − Read Only Memory）等のコンピュータ読み取り可能な記録媒体２１３には、パターンデータ処理部２０１が実行するパターンデータ処理用プログラムが記録されている。記録媒体２１３に記録された前記パターンデータ処理用プログラムは、記憶部２０４のプログラム領域に記憶して利用される。
パターンデータ処理部２０１は、記憶部２０４に記憶したパターンデータ処理用プログラムを実行することにより、共通侵入領域算出処理部２０５及び図形処理部２０６を構築する。
【００５３】
共通侵入領域算出処理部２０５は、ＣＡＤによって作成され記憶部２０４に記憶されたパターンデータ２１７を利用して共通侵入領域を算出する機能を有する。共通侵入領域算出処理部２０５は、セル間の重複領域を検出するセル間重複領域検出処理部２１６、セル間の重複パターンを抽出するセル間重複パターン抽出処理部２０７、及び、外部パターンから共通侵入領域を検出する共通侵入領域検出処理部２０８を有している。外部パターンは、セル間重複パターンと、上位階層セルのパターンの中の各セル内に侵入するパターンとを合わせたものである。
【００５４】
セル間重複領域検出処理部２１６は、セル毎に、当該セルのセルゾーンと、他の全ての同位階層のセルのセルゾーンとが重複する領域（セル間重複領域）を検出する。ここで、前記他の全ての同位階層のセルは、前記当該セルの全ての上位階層セル（前記当該セルよりも１階層上位の全てのセル）によって直接参照されているセルである。
【００５５】
セル間重複パターン抽出処理部２０７はセル間重複パターン抽出処理を行う。セル間重複領域検出処理部２１６によるセル間重複領域検出処理と、セル間重複パターン抽出処理部２０７によるセル間重複パターン抽出処理とによって、セル間重複パターン検出処理が行われる。
【００５６】
セル間重複パターン検出処理は、セル毎に、前記セル間重複領域に存在する当該セルおよび当該セルの傘下にある最下位階層セルに至るまでの全ての下位階層セルのパターンを検出する処理である。ここで、セルゾーンはセルのデータ存在領域（上位階層セルから見れば参照点）であり、当該セルの全データを包含する領域である。セルゾーンは必ずしも長方形でなくてもよい。
【００５７】
共通侵入領域検出処理部２０８は共通侵入領域検出処理を行う。共通侵入領域検出処理は、セルデータ２１１のセル毎に、当該セルに侵入する外部パターンの侵入部分をＯＲ処理することによって得られる領域（共通侵入領域）を求める処理である。共通侵入領域検出処理部２０８は、求めた共通侵入領域の形状データを、当該セルの共通侵入領域データとして当該セルに対応付けて記憶する。
【００５８】
セル間重複領域検出処理部２１６のセル間重複領域検出処理、セル間重複パターン抽出処理部２０７のセル間重複パターン抽出処理及び共通侵入領域検出処理部２０８の共通侵入領域検出処理によって共通侵入領域算出処理が行われる。
尚、パターンデータ２１７を構成する全てのセルについて共通侵入領域検出処理を予め行うようにすれば、他のパターンデータに対するパターンデータ処理を行う場合に各セルの共通侵入領域を利用することができるが、処理を短時間で済ませる場合には、パターンデータ２１７を構成するセルについてのみ共通侵入領域検出処理を行うようにしてもよい。
【００５９】
図形処理部２０６は、共通侵入領域データ２１２を用いて、パターンデータ２１７に対して所定のパターンデータ処理を行う処理部である。図形処理部２０６は、影響範囲算出処理部２１４、共通データ領域算出処理部２１５、共通データ領域処理部２０９及び影響範囲処理部２１０を備えている。
【００６０】
影響範囲算出処理部２１４は、パターンデータ処理の内容に応じて、セルの共通侵入領域に基づいて当該セルの影響範囲を求める処理を行う。
共通データ領域算出処理部２１５は、セルのデータ存在領域と当該セルの影響範囲から共通データ領域を求める処理を行う。
共通データ領域処理部２０９は各セルの共通データ領域についてパターンデータ処理を行う。影響範囲処理部２１０は各セルの影響範囲についてパターンデータ処理を行う。
【００６１】
図形処理部２０６は、共通データ領域処理部２０９と影響範囲処理部２１０が行ったパターンデータ処理の結果を統合することによって、パターンデータ２１７全体に対するパターンデータ処理結果を得る。図形処理部２０６は、このパターンデータ処理結果を記憶部２０４に記憶する。
【００６２】
ここで、表示部２０２は表示手段を構成し、操作部２０３は操作手段を構成し、記憶部２０４は記憶手段を構成し、パターンデータ処理部２０１は処理手段を構成している。
また、共通侵入領域算出処理部２０５は共通侵入領域算出手段を構成し、図形処理部２０６はデータ処理手段を構成している。
また、セル間重複領域検出処理部２１６はセル間重複領域検出手段を構成し、セル間重複パターン抽出処理部２０７はセル間重複パターン抽出手段を構成し、共通侵入領域検出処理部２０８は共通侵入領域検出手段を構成している。
また、セル間重複領域検出処理部２１６及びセル間重複パターン抽出処理部２０７はセル間重複パターン検出手段を構成している。
【００６３】
また、影響範囲算出処理部２１４は影響範囲算出手段を構成し、共通データ領域算出処理部２１５は共通データ領域算出手段を構成している。
また、共通データ領域処理部２０９は共通データ領域処理手段を構成し、影響範囲処理部２１０は影響範囲処理手段を構成している。
また、図形処理部２０６から影響範囲算出処理部２１４及び共通データ領域算出処理部２１５を除いた部分はパターンデータ処理手段を構成している。
【００６４】
図３は、本実施の形態におけるセル間重複パターン検出処理を示すフローチャートで、パターンデータ処理部２０１が記憶部２０４に記憶したパターンデータ処理用プログラムを実行することによって行う処理である。セル間重複パターン検出処理はパターンデータ処理部２０１のセル間重複領域検出処理部２１６及びセル間重複パターン抽出処理部２０７が行う。
【００６５】
セル間重複パターン検出処理は、各セルのデータ存在領域が他の全ての同位階層のセルのデータ存在領域と重複する領域（セル間重複領域）を検出する処理であるセル間重複領域検出処理（ステップＳ３０１〜Ｓ３０５、Ｓ３１０）と、セルの傘下にある最下位階層セルに至るまでの全ての下位階層セルのパターンのうち、当該セルのセル間重複領域に重複するパターンであるセル間重複パターンを抽出するセル間重複パターン抽出処理（ステップＳ３０６〜Ｓ３０９、Ｓ３１１）を有している。
【００６６】
図４は、本実施の形態における共通侵入領域検出処理を示すフローチャートで、パターンデータ処理部２０１が記憶部２０４に記憶したパターンデータ処理用プログラムを実行することによって行う処理である。共通侵入領域検出処理はパターンデータ処理部２０１の共通侵入領域検出処理部２０８が行う。
【００６７】
図５は本発明の実施の形態で使用するセルを示す図で、図６は本実施の形態で使用する各セルの階層構造を示す図である。
図５及び図６に示すように、図５（ｉ）は最上位階層（トップ）セルＴｏｐ、図５（ｉｉ）はセルＴｏｐの１階層下位に位置しセルＴｏｐが参照する階層セルＡ、図５（ｉｉｉ）はセルＴｏｐの１階層下位に位置しセルＴｏｐが参照する階層セルＢ、図５（ｉｖ）は階層セルＡの下位階層に位置し階層セルＡが参照する階層セルＣ、図５（ｖ）は階層セルＡ及び階層セルＢの下位階層に位置し階層セルＡ及び階層セルＢが参照する階層セルＤである。
【００６８】
参照セルは、当該参照セルの一階層上のセルによって参照されるセルである。また、参照セルは、当該参照セルの一階層上のセルに直接含まれるセルである。セルＣは、セルＡを介して間接的にセルＴｏｐに含まれるため、セルＴｏｐの参照セルではない。セルＤも、セルＡ、セルＢを介して間接的にセルＴｏｐに含まれるため、セルＴｏｐの参照セルではない。
【００６９】
セルＴｏｐは、ＬＳＩ全体を表すパターンデータ２１７に相当し、２つのセルＡ及び１つのセルＢを参照セルとして有すると共に、最上位階層のパターンとしてパターン５０１を有している。
セルＡは、１つのセルＣ及び１つのセルＤを参照セルとして含むと共に、当該セルＡの階層のパターンとしてパターン５０２を有している。
【００７０】
セルＢは、１つのセルＤを参照セルとして含むと共に、当該セルＢの階層のパターンとしてパターン５０３を有している。
セルＣは、最下位階層（ボトム）のセルであり、参照セルを含んでおらず、当該セルＣの階層のパターンとしてパターン５０４を有している。
セルＤはセルＣと同様に、最下位階層（ボトム）のセルであり、参照セルを含んでおらず、当該セルＤの階層のパターンとしてパターン５０５を有している。
【００７１】
セルＡ、Ｂ、Ｃ、Ｄは、セルＴｏｐの傘下にあるセルである。セルＡの傘下にあるセルはセルＣ、Ｄである。セルＢの傘下にあるセルはセルＤのみである。セルＣはセルＡの傘下にある下位階層セルではあるが、セルＢの下位階層セルではない。セルＤはセルＡ、Ｂの傘下にある下位階層セルである。セルＡ、Ｂは同位階層のセル（1階層上に同じ上位階層セルを有するセル）である。
【００７２】
セルＣ、Ｄは、セルＡを基準にして見た場合、セルＡの1階層下にあるため、セルＣ、ＤはセルＡを基準とする場合には同位階層である。しかしながら、セルＢを基準にして見た場合には、セルＤはセルＢの1階層下にあるが、セルＢの１階層下には位置しないため、セルＣ、ＤはセルＢを基準とする場合には同位階層ではない。
【００７３】
セルゾーンはすべてのレイヤを対象としたものであるため、セルゾーンには当該セルの全てのレイヤのパターンが含まれる。しかし、パターンは共通侵入領域を求めるレイヤのパターンのみ記述しているため、セルゾーンの含まれるパターンの範囲とレイヤに含まれる範囲は必ずしも一致していない。
【００７４】
図７〜図１３はセル間重複パターン検出処理の説明図で、図７〜図１０はセル間重複領域検出処理の説明図、図１１〜図１３はセル間重複領域を用いて行うセル間重複パターン検出処理の説明図である。セル間重複領域検出処理と、セル間重複パターン抽出処理によってセル間重複パターン検出処理が行われる。
【００７５】
また、図１４〜図１７は共通侵入領域検出処理の説明図である。
前述したように、前記セル間重複パターン検出処理及び共通侵入領域検出処理を行うことによって共通侵入領域が算出される。
以下、図２〜図１７を用いて、セル間重複パターン検出処理及び共通侵入領域検出処理を含む共通侵入領域算出処理について説明する。
【００７６】
共通侵入領域算出処理部２０５のセル間重複領域検出処理部２１６及びセル間重複パターン抽出処理部２０７は、記憶部２０４からパターンデータ処理の対象であるパターンデータ２１７を読み込んで、図３のセル間重複パターン検出処理を行う。
セル間重複パターン検出処理では、セル間重複領域検出処理部２１６がセル間重複領域検出処理（処理ステップＳ３０１〜Ｓ３０５、Ｓ３１０）を行い、セル間重複パターン抽出処理部２０７がセル間重複パターン抽出処理（処理ステップＳ３０６〜３０９、Ｓ３１１）を行う。
【００７７】
［セル間重複領域検出処理］
セル間重複領域検出処理は、セル間重複領域検出処理部２１６が全セルに対してセル毎に、当該セルのセルゾーンが同位階層の他のセルのセルゾーンと重複するセル間重複領域を検出すると共に、当該セルから直接参照されている全てのセル（換言すれば、当該セルが参照している１階層下位の全てのセル）のセルゾーンのうち、当該セルのセル間重複領域に含まれる下位セルの領域を下位セルのパターンの展開が必要な領域（以下、パターン展開必要領域と称する。）として検出するために行う処理である。
【００７８】
セル間重複領域に含まれる当該セルと各下位階層セルのパターンは、重複する相手セルに対する侵入パターンであり、これを求めるためには、セル間重複領域に含まれる最下位階層セルまでのパターンを展開する必要がある。これを効率的に行うため、セル間重複領域に含まれる一階層下位のセルのセルゾーンをパターン展開必要領域として検出して下位階層セルに登録し、順次最下位階層まで伝播させる。
【００７９】
具体的には、最上位階層セルから最下位階層セルまでの全てのセル（換言すればパターンデータ２１７として使用している全てのセル）に対して、最上位階層セルから最下位階層セルへ順に、処理ステップＳ３０１〜Ｓ３０５、Ｓ３１０の処理を行う。最上位階層セルから最下位階層セルまでの使用している全てのセルまで、当該セルに含まれる一階層下位のセル間のセル間重複領域の検出を行うと共に、当該セルが有するセル間重複領域と当該セルが有するパターン展開必要領域とのＯＲ領域に対して一階層下位のセルのセルゾーンとの間の重複領域を当該下位階層セルのパターン展開必要領域として順次検出する。
【００８０】
尚、パターン展開必要領域の分配処理（ステップＳ３０２）を行う前に当該セルのセル間重複領域が求められていればよく、パターン展開必要領域の分配処理（ステップＳ３０２）とセル間重複領域登録処理（ステップＳ３０４）は必ずしも同一セルに対し連続して行う必要は無い。ここで、上下階層間のように直接参照する関係にあるものや、あるいは他の階層を挟んで複数階層にまたがり引用関係にあるもの（換言すれば、間接的に参照する関係にあるもの）は、セル間の重複としては扱わず、パターン展開あるいは後述するパターンの侵入の場合にのみ評価する。
【００８１】
（ｉ）下位階層セルのセルゾーン計算処理ステップ（ステップＳ３０１）
処理ステップＳ３０１では、現時点でセル間重複領域作成の対象としているセルが参照している下位階層セルのセルゾーンを計算する。図７（ｉ）は、最上位階層セルＴｏｐの例である。最上位階層セルＴｏｐは下位階層として、２つのセルＡと１つのセルＢを参照している。
【００８２】
（ｉｉ）パターン展開必要領域の分配処理（ステップＳ３０２）
処理ステップＳ３０２では、当該セルのセル間重複領域とパターン展開必要領域のＯＲ領域を下位階層セルに分配する。前記分配処理は、下位階層セルと当該セルの前記ＯＲ領域の関係を抽出処理し、下位の各セルと重複するＯＲ領域を下位セルのパターン展開必要領域として順次追加する処理である。
【００８３】
図８（ｉ）は最上位階層セルＴｏｐの例である。セルＴｏｐは上位階層セルや同位階層セルがないため、同位階層の他のセルとの重複が無く又上位から侵入するパターンも無く、セル間重複領域がない。したがって、セルＴｏｐのセル間重複領域に含まれる一階層下のセルＡ、Ｂのセル領域（セルＡ、Ｂのパターン展開必要領域）も無い。
【００８４】
尚、当該セルのセル間重複領域は、当該セルの上位階層セルについて成された下位階層セルのセル間重複領域登録処理（ステップＳ３０４）によって得られたものを用い、当該セルのパターン展開必要領域は当該セルを直接参照している全てのセル（換言すれば、当該セルを参照している１階層上位の全てのセル）についてのパターン展開必要領域の分配処理（ステップＳ３０２）によって得られたものを用いる。
【００８５】
例えばセルＡの場合は、図８（ｉｉ）に示すように、処理ステップＳ３０４によって得られたもの（図１０（ｉ）参照）を用いる。セルＡはハッチングで示すセル間重複領域を有しているが、パターン展開必要領域は有していない。セルＡのセル間重複領域とセルＡのパターン展開領域のＯＲ領域（ここでは、セルＡはパターン展開必要領域は無い。）と、下位階層セルＣのセルゾーンとが重複しており、前記重複する領域がセルＣのパターン展開必要領域となる。
【００８６】
（ｉｉｉ）下位階層セルの重複領域検出処理（ステップＳ３０３）
処理ステップＳ３０３では、上位階層セルにおいて、下位階層セルのセルゾーンの重複部分をセル間重複領域として抽出する。図９（ｉ）のハッチング部分が、前記下位階層セルのセル間重複領域である。
【００８７】
（ｉｖ）下位階層セルのセル間重複領域登録処理（ステップＳ３０４）
処理ステップＳ３０４では、（ｉｉｉ）で求めた下位階層セルのセル間重複領域を当該下位階層セルのセル間重複領域として重複相手セルのセル間重複領域と関連付けて追加登録する。相手セル、領域とも同一のものが既に登録されている場合、追加は行わない。（図１０（ｉ））。
【００８８】
ここで得られたセル間重複領域のデータは、前述したように次の下位階層セルのパターン展開必要領域の分配処理（ステップＳ３０２）で使用される（ステップＳ３１０）。
前記処理を最上位階層セルから最下位階層セルまで順に終了するまで繰り返す（ステップＳ３０５）。このとき処理するセルの順序は、上位階層セルについての処理が全て終了しているセルを処理対象として選択する。
【００８９】
セルＡに関して前記処理を行う場合、図７（ｉｉ）、図８（ｉｉ）、図９（ｉｉ）、図１０（ｉｉ）の順で処理が行われ、図１０（ｉｉ）に示すように、セルＣ、Ｄのセル間重複領域とパターン展開必要領域のＯＲ領域が検出される。セルＢ〜Ｄに関しても同様の処理が行われる。これにより、セル毎にセル間重複領域が検出される。セル間重複領域に存在する当該セルおよび最下位階層に至るまでの下位セルのパターンは、他のいずれかのセルへ侵入するものである。
最上位階層セルから最下位階層セルまで全てのセルについて前記セル間重複領域検出処理が完了すると、次のセル間重複パターン抽出処理が行われる。
【００９０】
［セル間重複パターン抽出処理］
セル間重複パターン抽出処理部２０７は、セル毎に、前記のようにして検出したセル間重複領域においてセル間で重複するパターン（セル間重複パターン）を検出するためのセル間重複パターン検出処理を行う。セル間重複パターン検出処理では、全てのセルに対して、最下位階層セルから最上位階層セルへ順序に、処理ステップＳ３０６〜Ｓ３０９、Ｓ３１１の処理を行う。
【００９１】
（ｉ）評価対象パターン検出処理（ステップＳ３０６）
処理ステップＳ３０６では、現時点でセル間重複パターン検出処理の対象としているセルのパターンと、当該セルから直接参照されている全てのセル（換言すれば、当該セルが参照している１階層下位のセル）から展開された展開パターンのＯＲ処理を行い、前記ＯＲ処理の結果得られたパターンを当該セルの評価対象パターンとする。評価対象パターンとは、当該セルとその下位階層セルのパターンのうち、当該セルおよび上位階層におけるセル間重複パターンであるか否かの評価の対象となるパターンである。
【００９２】
図１１（ｉ）は、現時点のセル間重複パターン検出処理対象のセルが最下位階層セルＣ、Ｄの例である。最下位階層セルＣ、Ｄは参照点である下位階層セルを有しないため、下位から展開された展開パターン（上位階層セル間重複パターン）が無く、セル内のパターンのみが対象となる。
【００９３】
尚、前記下位階層セルからの展開パターンは、当該セルから直接参照されている全てのセル（換言すれば、当該セルが参照している１階層下位の全てのセル）に関するパターン展開必要領域のパターン展開処理（ステップＳ３０７）によって得られたものを用いる。例えば、セルＡの場合は、（図１２（ｉｉ）、ステップＳ３０７）によって得られたものを用いる。
以上のようにして、セル内のパターンと、当該セルが参照している１階層下位の全ての階層セルから展開された展開パターンとをＯＲ処理することによって得られるパターンである評価対象パターンが、セル毎に得られる。
【００９４】
（ｉｉ）パターン展開必要領域のパターン展開処理（ステップＳ３０７）
処理ステップＳ３０７では、前記検出した評価対象パターンのうちパターン展開必要領域に存在するもの（展開パターン）を、当該セルを直接参照している全ての上位セル（換言すれば、当該セルを参照している１階層上位の全てのセル）における当該セルの参照点に展開する。図１２（ｉ）は、セルＣからセルＡへの展開パターンである。尚、セルＡにはパターン展開必要領域が無いため（図８参照）、図１２（ｉｉ）に示すように、セルＡからセルＴｏｐへの展開パターンは無い。
【００９５】
前述したように、ここで得られた展開パターンは、次の上位階層セルの評価対象パターン検出処理（ステップＳ３０６）で使用される（ステップＳ３１１）。
ここでは、全ての当該セルの参照点に展開しているが、パターン展開必要領域の分配処理（ステップＳ３０２）において、分配元となった上位セル名と位置をパターン展開必要領域と合わせて登録することで、必要な参照点にのみ展開することも可能である。どちらの手順も処理効率の違いであり、共通侵入領域の算出結果は同一となる。
【００９６】
（ｉｉｉ）セル間重複パターン登録処理（ステップＳ３０８）
処理ステップＳ３０８では、前記検出した評価対象パターンのうちセル間重複領域に存在するものを、セル間重複パターンとして重複相手セル名および重複位置に関連付けて記憶部２０４に記憶する。セルＣ、Ｄに関して得られたセル間重複パターンは、図１３（ｉ）のハッチングで示す領域となる。図１３に示すように、自セル内のパターンのうち、セル間重複領域と重複するパターン部分が、セル間重複パターンとなる。セル間重複パターンは、同じセル間重複領域を有する他のセルへ侵入するパターンとなる。
【００９７】
前記処理を最下位階層セルから最上位階層セルまで順に終了するまで繰り返す（ステップＳ３０９）。このときの順序は、当該セルから直接参照されている全ての下位階層セル（換言すれば、当該セルが参照している１階層下位のセル）についてセル間重複パターン抽出処理が終了しているセルを、セル間重複パターン抽出処理の対象として選択する。
【００９８】
セルＡに関して前記処理を行う場合、図１１（ｉｉ）、図１２（ｉｉ）、図１３（ｉｉ）となる。セルＡのセル間重複パターンは、図１２（ｉｉ）の評価対象パターンとセル間重複領域とが重なる領域であり、図１３（ｉｉ）のハッチングを付した領域となる。他のセルに関しても同様の処理が行われる。以上のようにしてセル間重複パターン検出処理が行われることにより、各セル毎に、同じセル間重複領域を有する他のセルへ侵入するセル間重複パターンが得られる。
【００９９】
このように、本発明の実施の形態では、先ずセル間重複領域を検出しておき、次に、評価対象パターンのうち前記セル間重複領域に重複するパターンをセル間重複パターンとして求めるようにしているため、はじめから各セル内の全ての領域についてセル間重複パターンを求める方法に比べて、少ないデータ規模で求めることが可能になる。
【０１００】
次に、共通侵入領域検出処理部２０８は、前述した処理によって記憶部２０４に記憶されたセル間重複パターンのデータを読み込んで、図４の共通侵入領域検出処理を行う。
［共通侵入領域検出処理］
共通侵入領域検出処理では、最上位階層セルから最下位層セルまでの全てのセルに対して、上位階層セルから下位階層セルへ順に、処理ステップＳ４０１〜Ｓ４０６を行う。
【０１０１】
（１）セル間侵入領域作成処理（ステップＳ４０１）
処理ステップＳ４０１では、現時点で共通侵入領域検出処理の対象としているセルと同位階層のセルを当該セルの重複相手セルとして、処理ステップＳ３０８で関連付けられた全てのセル間重複パターンを、当該セルの対応する位置（当該セルと重複相手セルの重なる位置）にセル間侵入領域として作成する。セル間侵入領域は、当該セルに関連付けられた他の全ての同位階層セル（前記重複相手セル）のセル間重複パターンを、当該セルのデータ存在領域内の対応する位置に配置したものである。
【０１０２】
図１４（ｉ）は最上位階層セルＴｏｐの例であり、セルＴｏｐには同位階層セルが存在しないため、最上位階層セルＴｏｐにはセル間侵入領域は無い。セルＡ、Ｂのセル間侵入領域は図１４（ｉ）に示すようになり又、セルＣ、Ｄのセル間侵入領域は図１４（ｉｉ）のようになる。
尚、このステップをここで行うのではなく、処理ステップＳ３０８でセル間重複パターンを登録する代わりに、このステップの処理とあわせ、重複相手セルへセル間侵入領域を登録することも同一の結果を得ることができる。
【０１０３】
（２）共通侵入領域完成処理（ステップＳ４０２）
処理ステップＳ４０２では、当該セルを直接参照している全ての上位階層セル（換言すれば、当該セルを参照している１階層上位の全てのセル）から切り出した侵入領域（即ち、１階層上位の全てのセルに含まれるパターンのうち、当該セルのデータ存在領域に重なる領域）と前記セル間侵入領域のＯＲ処理を行うことにより、セル毎に共通侵入領域算出処理が完了する。前記ＯＲ処理の結果得られる領域が共通侵入領域であり、これを図１５に示す。
【０１０４】
図１５（ｉ）は最上位階層セルＴｏｐの例であり、セルＴｏｐには上位階層セルが存在しないため、上位階層セルから切り出した侵入領域図形は無く、したがって共通侵入領域は無い。セルＡの場合には、最上位階層セルＴｏｐのパターン中のセルＡと重なる領域が「上位階層セルから切り出した侵入領域」となり、図１５（ｉｉ）のハッチングで示す共通侵入領域が得られる。
尚、前記全ての上位階層セル（即ち、当該セルを参照している１階層上位の全てのセル）から切り出した侵入領域は、上位階層セルの下位階層侵入領域作成処理（ステップＳ４０４）によって得られたものを用いる。
【０１０５】
（３）下位階層侵入評価パターン作成処理（ステップＳ４０３）
処理ステップＳ４０３では、当該セルの共通侵入領域と、前記共通侵入領域検出処理対象セルの対象レイヤのパターン（下位階層のパターンは含まない）とのＯＲ処理を行うことにより、下位階層に対する侵入評価パターン（下位階層侵入評価パターン）を作成する。下位階層侵入評価パターンとは、上位階層セルから下位階層セルのデータ存在領域内に侵入するか否かの判定対象となるパターンである。図１６（ｉ）は最上位階層セルＴｏｐの例であり、最上位階層セルＴｏｐには上位階層セルが存在しないため、前記共通侵入領域は無く、したがって下位階層侵入評価パターンはセルＴｏｐの対象レイヤのパターン（ハッチング領域）のみとなる。セルＡの下位階層侵入評価パターンは図１６（ｉｉ）のハッチング領域となる。
【０１０６】
（４）分配処理（ステップＳ４０４）
処理ステップＳ４０４では、前記下位階層侵入評価パターンを参照点毎に下位階層のセルに分配する（図１７（ｉ））。前記分配処理は、参照セルゾーンと下位階層侵入評価パターンの重なり領域を抽出処理し、抽出した領域を対応するセルに付与する処理である。
前記分配された領域は図１４に示したセル間侵入領域に追加処理されて（図１７（ｉ））、図１５の共通侵入領域が得られる。図１７（ｉ）では、セルＡ、Ｂの侵入領域及び分配された下位階層侵入評価パターンにハッチングが付されており、これらが図１５の共通侵入領域となる。
【０１０７】
このように、当該セルの共通侵入領域と当該セルのパターンとのＯＲ処理の結果を下位階層セルに分配することで、下位セルにおける上位セルからの侵入領域を算出する。前述したように、ここで得られた侵入領域のデータは、下位階層セルの共通侵入領域の完成処理（ステップＳ４０２）で使用される。
【０１０８】
前記処理を最上位階層セルから最下位階層セルまで順に終了するまで繰り返す（ステップＳ４０５）。このときの順序は、全ての上位階層セルの処理が終了したセルを対象として選択する。このときの順序は、その全ての上位階層セルについて共通侵入領域検出処理が終了しているセルを、共通侵入領域検出処理の対象として選択する。
セルＡに関して前記処理を行う場合、図１４（ｉｉ）、図１５（ｉｉ）、図１６（ｉｉ）、図１７（ｉｉ）となる。セルＣ、Ｄの場合、共通侵入領域は、図１７（ｉｉ）のハッチングを付した領域となる。他のセルに関しても同様の処理が行われ、共通侵入領域が得られる。共通侵入領域は、セル領域内で外部パターンが重複する可能性のある領域である。
【０１０９】
ここでは、セル間侵入領域（ステップＳ４０１）と上位セルパターンによる侵入領域（ステップＳ４０４）を別に求めているが、セルパターンと共通侵入領域の重複部分をドントケアとする場合、他の手順も可能である。たとえば、パターン展開必要領域とともにセル間重複領域に存在するパターンを上位階層セルに展開し、上位セルパターンによる侵入領域（ステップＳ４０４）にて一括して共通侵入領域を求めることができる。この場合も、共通侵入領域の計算方法が異なるが、セル間重複領域を求め、これをもとにセル間重複パターンを求めていることは同様である。
【０１１０】
次に、前述のようにして算出した共通侵入領域を用いて、パターンデータ２１７に対する所定の処理を行う例について説明する。
パターンデータ２１７に対する処理としては、パターンデータ２１７の形状や配置が正しいか否かの検証処理やパターンデータ２１７の変更処理等がある。また、パターンデータ処理には、ＡＮＤ処理、ＯＲ処理等の論理演算処理、セルが有するパターンの寸法を変更するサイジング処理、スペースやパターンの寸法チェック処理、対象選択処理等、種々の処理がある。以下に、パターンデータ処理の具体例を説明する。
【０１１１】
図１８は、パターンデータ処理部２０１の図形処理部２０６がパターンデータ処理としてＡＮＤ処理を行う場合のフローチャートである。
図１９は、パターンデータ２１７を構成するセルデータ２１１の中の、下位階層セルＸの構成を示す図である。セルＸは複数のレイヤ（本実施の形態では第１レイヤ及び第２レイヤ）を有するセルで、第１レイヤにパターン３０１を有し、第２レイヤにパターン３０２を有している。
【０１１２】
図２０は、パターンデータとしての最上位階層セルＴｏｐの構成を示す図である。セルＴｏｐは、２つのセルＸを参照セルとして有すると共に、第１レイヤにパターン３０３、３０４を有し又、第２レイヤにパターン３０５、３０６を有している。
図２１〜図２４は、パターンデータに対するＡＮＤ処理の説明図であり、セルＴｏｐにおける第１レイヤの全パターンと第２レイヤの全パターンとのＡＮＤ処理を行う動作の説明図である。
以下、図２、図１８〜図２４を用いて本実施の形態におけるパターンデータ処理の例として、異なるレイヤに存在するパターン同士のＡＮＤ処理について説明する。
【０１１３】
共通侵入領域算出処理部２０８は、各階層セル毎に全ての参照点（即ち、最上位階層セルＴｏｐに至るまでの全ての上位階層セルの中で当該セルを参照している箇所）における外部パターンの侵入部分をレイヤ毎に求め、前記各レイヤ毎の侵入部分のＯＲ領域を、各レイヤの共通侵入領域として当該セルに関連付けて記憶部２０４に格納する（図１８のステップＳ５０１）。
これにより、共通侵入領域として、図２１に示すように、第１レイヤの共通侵入領域４０１及び第２レイヤの共通侵入領域４０２が得られる。この共通侵入領域４０１、４０２は全ての演算で共通に使用できるものであり、レイヤ毎に一度だけ求める。
【０１１４】
次に、影響範囲算出処理部２１４は、共通侵入領域４０１、４０２に基づいて、パターンデータ処理の内容（ここではＡＮＤ処理）に応じて影響範囲を算出する。
一般に、２つのレイヤを入力する処理では、第１レイヤの共通侵入領域による影響（第１レイヤの影響）と第２レイヤの共通侵入領域による影響（第２レイヤの影響）は内容が異なる。同様に、境界パターンについても、それぞれのレイヤの影響範囲によりそれぞれに入力レイヤに対する効果が異なる。このため、
以下の４種を考慮する必要がある。
・第１レイヤの影響範囲による第１レイヤ境界パターン
・第１レイヤの影響範囲による第２レイヤ境界パターン
・第２レイヤの影響範囲による第１レイヤ境界パターン
・第２レイヤの影響範囲による第２レイヤ境界パターン
【０１１５】
パターンデータ処理がＡＮＤ処理の場合は、演算自体が距離に依存せずパターンの重複関係のみでパターンデータ処理結果が決定される。また、セル内パターンと外部パターンの同じレイヤの重複部分はセル内の処理結果が使用可能であり、他階層の処理結果は考慮不要（ドントケア（Don't Care））となる。
このことから、各レイヤの影響範囲は
・第１レイヤの影響範囲は、第１レイヤの共通侵入領域から第１レイヤのセル内パターンを除いた領域
・第２レイヤの影響範囲は、第２レイヤの共通侵入領域から第２レイヤのセル内パターンを除いた領域
となる。
【０１１６】
また、階層間にまたがって考慮が必要なケースは、セルのパターンと外部パターンので異なるレイヤのパターンが重複する部分のみであることから、ＡＮＤ処理の境界図形は、
・第１レイヤの影響範囲による第１レイヤ境界図形および第２レイヤの影響範囲による第２レイヤ境界図形は不要
・第１レイヤの影響範囲による第２レイヤ境界図形は、第１レイヤの影響範囲内に存在する、第２レイヤのセル内パターン
・第２レイヤの影響範囲による第１レイヤ境界図形は、第２レイヤの影響範囲内に存在する、第１レイヤのセル内パターン
である。
【０１１７】
したがって、図形処理部２０６の影響範囲算出処理部２１４は、共通侵入領域４０１、４０２から、共通侵入領域４０１、４０２と同一レイヤのセル内パターンとの重複領域を除いた領域を、演算処理で使用する影響範囲として算出する（ステップＳ５０２）。前記影響範囲は図２２に示すように、第１レイヤの影響範囲３０７、第２レイヤの影響範囲３０８となる。
【０１１８】
共通データ領域算出処理部２１５は、セルのデータ存在領域から前記影響範囲を除いた領域を共通データ領域として算出し、当該セルに関連付けて記憶部２０４に格納する（ステップＳ５０３）。ただし、ＡＮＤ処理の場合、第１レイヤの影響範囲、第２レイヤの影響範囲とも一方のレイヤのパターンしか存在せず、処理結果のパターンは存在しないため、前記影響範囲の削除は不要である。
【０１１９】
次に、共通データ領域処理部２０９は、記憶部２０４に記憶した前記セルの共通データ領域に対してＡＮＤ処理を行う。この場合、共通データ領域処理部２０９は前記ＡＮＤ処理を当該セル単体で行い、当該セルの共通データ領域に対するパターンデータ処理結果として当該セルに関連付けて記憶部２０４に格納する。共通データ領域処理部２０９は、図２３に示すように、下位階層セルＸについて単独で、第１レイヤと第２レイヤのＡＮＤ処理を行うことにより、共通データ領域に対するＡＮＤ処理結果として、ＡＮＤ領域３０９が得られる。
【０１２０】
次に、上位階層の演算に影響するセル内パターンを抽出するため、影響範囲処理部２１０は、図２４に示すように、第１レイヤのセル内パターン３０１と第２レイヤの影響範囲３０８との重複部分、第２レイヤのセル内パターン３０２と第１レイヤの影響範囲３０７との重複部分を各々第１レイヤ境界パターン３１０、第２レイヤ境界パターン３１１として算出し、全参照点に展開する（ステップＳ５０４）。
境界パターンは、セル内パターンのうち外部パターンと一緒に処理する必要のあるパターンであり、ＡＮＤ処理では影響範囲にある異なるレイヤのセル内パターンである。単なるＡＮＤ処理に比べると手順は複雑となるが、演算対象データ量はセル単位であり非常に少なくなるため、全体としては演算処理時間の短縮が可能となる。
【０１２１】
影響範囲処理部２１０は、図２５（ｉ）に示すように、当該セルから直接参照されている全ての下位階層セル（換言すれば、当該セルが参照している全ての１階層下位のセル）から展開した境界パターンと上位階層セルのパターンを相互にマージし、図２５（ｉｉ）に示すように上位階層セルの第１レイヤと第２レイヤのＡＮＤ処理を実行する（ステップＳ５０５）。これにより、領域６０１、６０２が得られる。
【０１２２】
図形処理部２０６は、図２５（ｉｉ）に示すように、共通データ領域処理部２０９がＡＮＤ処理を行うことによって算出した領域３０９と、影響範囲処理部２１０がＡＮＤ処理を行うことによって算出した領域６０１、６０２との和を、パターンデータ処理の結果として算出する。図形処理部２０６は、前記パターンデータ処理の結果を記憶部２０４に記憶する（ステップＳ５０６）。これにより、フラット処理と同じ演算結果を得ることができる。
【０１２３】
次に、パターンデータ処理としてＳＵＢ処理の例を、前記ＡＮＤ処理の例で使用したパターンデータを用いて説明する。ＳＵＢ処理に特有の処理を図２６〜図２９に示している。ＳＵＢ処理も、前記ＡＮＤ処理と同様に、図２のパターンデータ処理装置２００を用いて行われる。使用するパターンデータは、前述したＡＮＤ処理で用いたものと同じため、共通侵入領域は前記ＡＮＤ処理のものと同じであり、共通侵入領域４０１、４０２である。
ＳＵＢ処理は、処理自体が距離に依存せずパターンの重複関係のみで結果が決定されることはＡＮＤ処理と同様である。しかしながら、ＳＵＢ処理は、セル内パターンと外部パターンの重複に関しては、第１レイヤから第２レイヤを除く演算であるため、２つのレイヤで扱いがＡＮＤ処理の場合とは異なることになる。
【０１２４】
即ち、セル内の第２レイヤのパターンは、上位階層セルの第２レイヤのパターンが重複していても結果は変わらないが、第１レイヤのパターンが重複する場合、第２レイヤで削除するのはセル内のパターンだけではなく、上位のパターンも削除する必要がある。
つまりセル内の第１レイヤの有無に拘わらず全てのセル外部の第１レイヤと重複する領域は一度のみの共通の処理とすることができず、個別処理が必要になる。
【０１２５】
このことから、ＳＵＢ処理における各レイヤの影響範囲は
・第１レイヤの影響範囲は、第１レイヤの共通侵入領域全体
・第２レイヤの影響範囲は、第２レイヤの共通侵入領域から第２レイヤのセル内パターンを除いた領域
となる。
【０１２６】
また、階層間にまたがって考慮が必要なケースは、各レイヤの影響範囲と異なるレイヤのパターンが重複する部分であることから、ＳＵＢ処理の境界図形は、
・第１レイヤの影響範囲による第１レイヤ境界図形および第２レイヤの影響範囲による第２レイヤ境界図形は不要
・第１レイヤの影響範囲による第２レイヤ境界図形は、第１レイヤの影響範囲内に存在する、第２レイヤのセル内パターン
・第２レイヤの影響範囲による第１レイヤ境界図形は、第２レイヤの影響範囲内に存在する、第１レイヤのセル内パターン
である。
【０１２７】
したがって、図形処理部２０６の影響範囲算出処理部２１４は、第１レイヤの共通侵入領域４０１全体と同一の領域と、第２レイヤの共通侵入領域４０２から第２レイヤのセル内パターンと重複する領域を除いた領域とを、パターンデータ処理で使用する影響範囲として算出する（図１８の処理ステップＳ５０２及び図２１参照）。
その結果、図２６に示すように、第１レイヤの共通侵入領域４０１全体と同一の領域として、第１レイヤの影響範囲３１２が得られる（同図（ｉ））。また、第２レイヤの共通侵入領域４０２から第２レイヤのセル内パターンと重複する領域を除いた領域として、第２レイヤの影響範囲３１３が得られる（同図（ｉｉ））。
【０１２８】
ＳＵＢ処理の場合、第１レイヤの影響範囲は、セル内のパターンに影響しないため共通データ領域に対して考慮不要（ドントケア（Don't care））である。また、第２レイヤの影響範囲は、セル内パターンが削除される可能性がある領域に相当するため、共通データ領域から除く必要がある。
共通データ領域算出処理部２１５は、セルのデータ存在領域から前記第２レイヤの影響範囲を除いた領域を共通データ領域として算出し、当該セルに関連付けて記憶部２０４に格納する（ステップＳ５０３）。
【０１２９】
次に共通データ領域処理部２０９は、記憶部２０４に記憶した前記セルの共通データ領域に対してＳＵＢ処理を行う。この場合、共通データ領域処理部２０９は、セル内の共通データ領域の演算はセル単体で一度のみ演算を行い、共通データに関するセルの処理結果として各セルデータ２１１に関連付けて記憶部２０４に格納する。
【０１３０】
このため、セル内の演算処理（共通データ領域についてのＳＵＢ処理）は、図２７に示すように下位階層セルＸについて単独で、第１レイヤと第２レイヤのＳＵＢ処理を行い、さらに共通データ領域とＡＮＤ処理することにより、ＳＵＢ領域３１４が得られる。
上位階層セルの処理に影響するセル内パターンを抽出するため、影響範囲処理部２１０は、図２８に示すように、第１レイヤのセル内パターン３０１と第２レイヤの影響範囲３１３との重複部分及び第２レイヤのセル内パターン３０２と第１レイヤの影響範囲３１２との重複部分を、各々第１レイヤ境界パターン３１５、第２レイヤ境界パターン３１６として算出し、全参照点に展開する（ステップＳ５０４）。
【０１３１】
次に影響範囲処理部２１０は、図２９（ｉ）に示すように当該セルから直接参照されている全ての下位階層セル（換言すれば、当該セルが参照している全ての１階層下位のセル）から展開した境界パターンと上位階層セルのパターンを相互にマージし、図２９（ｉｉ）に示すように上位階層セルの第１レイヤと第２レイヤのＳＵＢ処理を実行する（ステップＳ５０４）。これにより、領域３１７、３１８が得られる。
【０１３２】
図形処理部２０６は、図２９（ｉｉ）に示すように、共通データ領域処理部２０９が算出した領域３１４と影響範囲処理部２１０が算出した領域３１７、３１８の和を、パターンデータ処理の結果として算出する。図形処理部２０６は、前記パターンデータ処理の結果を記憶部２０４に記憶する（ステップＳ５０６）。これにより、フラット処理と同じ演算結果を得ることができる。
【０１３３】
他のパターンデータ処理の例としてＯＲ処理の場合は、階層間で影響を及ぼさないため影響範囲はなく、各階層毎に独立にＯＲ処理を行えばよい。
【０１３４】
その他のパターンデータ処理も演算処理の内容や演算実現手順は異なるが、
（１）共通侵入領域を用いて、これにより結果が変化する範囲を影響範囲として入力レイヤごとに求め、
（２）セル内の演算を行うと共に影響範囲内で結果が不正となる可能性があるパターンを削除し、
（３）影響範囲に対する各参照点における個別処理に必要な境界パターンを作成して、上位階層の演算を順次実行する
ことにより、所定の階層的演算処理が実現できる。ここで、（１）〜（３）の実現手段は、これまでに例示したようにパターンデータ処理の内容により異なるが、いずれも共通侵入領域に基づいて決定可能である。
【０１３５】
以上述べたように、本発明の実施の形態に係るパターンデータ処理方法は、階層化された複数のセルを有するパターンデータに対して予め定めた所定の処理を行うパターンデータ処理方法において、セル毎に外部から当該セルに侵入する外部パターンを検出し、前記外部パターンが当該セルに侵入する領域を共通侵入領域として当該セルに関連付ける共通侵入領域算出ステップと、セルに関連付けられた前記共通侵入領域に基づいて、前記所定の処理の内容に応じて、当該セルの中で前記外部パターンとともに前記所定の処理を行う必要のある領域を当該セルの影響範囲として算出する影響範囲算出ステップと、セルのデータ存在領域から当該セルの影響範囲を除外した領域を当該セルの共通データ領域として算出する共通データ領域算出ステップと、前記各セルの共通データ領域については前記所定の処理を一度行うと共に前記影響範囲については当該セルに侵入する前記外部パターンとともに前記所定の処理を行うことにより、前記パターンデータに対する前記所定の処理を行うパターンデータ処理ステップとを備えて成ることを特徴としている。
【０１３６】
ここで、前記共通侵入領域算出ステップは、セルが同位階層の他のセルと重複する領域であるセル間重複領域を検出するセル間重複領域検出ステップと、各セルのパターンと各セルの最下位階層セルに至るまでの全ての下位階層セルのパターンの内、当該セルのセル間重複領域に重複するパターンであるセル間重複パターンを抽出するセル間重複パターン抽出ステップと、各セルに重複する同位階層の他のセルのセル間重複パターンと、当該セルの最上位階層に至るまでの全ての上位階層のセルのパターンのうち当該セルのデータ存在領域に重複するパターンとから成る前記共通侵入領域を算出する共通侵入領域検出ステップとを備えて成るように構成してもよい。
【０１３７】
また、前記セル間重複領域検出ステップは、各セルと同位階層セルとの間の重複領域をセル間重複領域として検出する処理と、最上位階層セルから最下位階層セルまで順に各セルのセル間重複領域と上位階層の処理で検出した当該セルのパターン展開必要領域のＯＲ領域の内、一階層下位のセルのデータ存在領域と重複する領域を下位階層のセルのパターン展開必要領域として検出する処理であり、
前記セル間重複パターン抽出ステップは、最下位階層セルから最上位階層セルまで順に、各セルのパターンと下位階層から展開された評価対象パターンを合わせたパターンを当該セルの評価対象パターンとし、当該セルのセル間重複領域に重複する評価対象パターンを当該セルのセル間重複パターンとして抽出すると共に、前記当該セルのパターン展開必要領域に存在する当該セルの評価対象パターンを上位階層に展開する処理であり、
前記共通侵入領域検出ステップは、最上位階層セルから最下位階層セルまで順に、各セルに重複する同位階層のセルのセル間重複パターンと、当該セルに重複する一階層上位のセルのパターンと、当該セルに重複する一階層上位のセルの共通侵入領域とから成る前記共通侵入領域を算出する処理であるように構成してもよい。
【０１３８】
前記影響範囲算出ステップは、セルに関連付けられた前記共通侵入領域に基づいて、前記所定の処理の内容に応じて、当該セルのデータ存在領域の中で、当該セル単独で前記所定の処理を行うと前記外部パターンの影響を受けて誤った結果が得られるため前記外部パターンとともに前記所定の処理を行う必要のある領域を当該セルの影響範囲として算出する処理である。
【０１３９】
本発明の実施の形態に係るパターンデータ処理方法は、前記のように構成されているため、厳しい設計制約を設けることなく、階層化された複数のセルを有するパターンデータに対して論理演算処理等の所定の処理を効率的に行うことができる。
また、レイアウト設計においては、階層間のパターン制約を考慮する必要がなく、従来と同じ設計条件のみを考慮しての設計が可能となるため、制約増加によるレイアウト面積の増加や設計工数、期間の増大が防止できる。パターンデータ処理においては、実際には重複がなくとも階層間のパターン制約によって展開されるパターン量より、実際階層間の重複による影響範囲のみのパターン量の方が一般に少なくできる。処理時間は、ほぼこの展開パターン量に依存するため、共通侵入領域作成にかかる時間以上に処理時間は短縮が可能となる。
【０１４０】
また、ＬＳＩやＦＰＤ等のためのレイアウトパターン(マスクパターン)設計にあたり、設計ルールを満たしていることの検証は、論理演算、サイジング、寸法チェック、対象選択処理などを組み合わせることで実現している。また、製造工程に受け渡すデータの作成も、同様にこれらの処理を組み合わせることで実現する。このような図形処理を、高速に実施するための階層処理の実現に用いることが可能である。
【０１４１】
また、本発明の実施の形態に係るパターンデータ処理装置２００は、階層化された複数のセルを有するパターンデータに対して予め定めた所定の処理を行うパターンデータ処理装置において、各セル毎に外部から当該セルに侵入する外部パターンを検出し、前記外部パターンが当該セルに侵入する領域を共通侵入領域として当該セルに関連付ける共通侵入領域算出処理部２０５と、セルに関連付けられた前記共通侵入領域に基づいて、前記所定の処理の内容に応じて、当該セルの中で前記外部パターンとともに前記所定の処理を行う必要のある領域を当該セルの影響範囲として算出する影響範囲算出処理部２１４と、セルのデータ存在領域から当該セルの影響範囲を除外した領域を当該セルの共通データ領域として算出する共通データ領域算出処理部２１５と、前記各セルの共通データ領域については前記所定の処理を一度行うと共に前記影響範囲については当該セルに侵入する前記外部パターンとともに前記所定の処理を行うことにより、前記パターンデータに対する前記所定の処理を行うパターンデータ処理手段とを備えて成ることを特徴としている。
【０１４２】
ここで、共通侵入領域算出処理部２０５は、セルが同位階層の他のセルと重複する領域であるセル間重複領域を検出するセル間重複領域検出処理部２１６と、各セルのパターンと各セルの最下位階層に至るまでの全ての下位階層セルのパターンの内、当該セルのセル間重複領域に重複するパターンであるセル間重複パターンを抽出するセル間重複パターン抽出処理部２０７と、各セルに重複する同位階層の他のセルのセル間重複パターンと、当該セルの最上位階層に至るまでの全ての上位階層のセルのパターンのうち当該セルのデータ存在領域に重複するパターンとから成る前記共通侵入領域を算出する共通侵入領域検出処理部２０８とを備えて成るように構成することができる。
【０１４３】
セル間重複領域検出処理部２１６は、各セルと同位階層セルとの間の重複領域をセル間重複領域として検出すると共に、最上位階層セルから最下位階層セルまで順に各セルのセル間重複領域と上位階層の処理で検出した当該セルのパターン展開必要領域のＯＲ領域の内、一階層下位のセルのデータ存在領域と重複する領域を下位階層のセルのパターン展開必要領域として検出し、
セル間重複パターン抽出処理部２０７は、最下位階層セルから最上位階層セルまで順に、各セルのパターンと下位階層から展開された評価対象パターンを合わせたパターンを当該セルの評価対象パターンとし、当該セルのセル間重複領域に重複する評価対象パターンを当該セルのセル間重複パターンとして抽出すると共に、前記当該セルのパターン展開必要領域に存在する当該セルの評価対象パターンを上位階層に展開し、
共通侵入領域検出処理部２０８は、最上位階層セルから最下位階層セルまで順に、各セルに重複する同位階層のセルのセル間重複パターンと、当該セルに重複する一階層上位のセルのパターンと、当該セルに重複する一階層上位のセルの共通侵入領域とから成る前記共通侵入領域を算出するように構成することができる。
本発明の実施の形態に係るパターンデータ処理装置２００は、前記のように構成されているため、厳しい設計制約を設けることなく、階層化された複数のセルを有するパターンデータに対して論理演算処理等の所定の処理を効率的に行うことができる等の効果を奏する。
【０１４４】
また、本発明の実施の形態によれば、コンピュータに階層化された複数のセルを有するパターンデータに対して予め定めた所定の処理を実行させるためのパターンデータ処理用プログラムにおいて、コンピュータに前述したパターンデータ処理方法を実行させることを特徴とするパターンデータ処理用プログラムが提供される。
コンピュータは本実施の形態に係るパターンデータ処理用プログラムを実行することにより、階層化された複数のセルを有するパターンデータに対して、予め定めた所定の処理を実行させることができる。
また、本発明の実施の形態に係るパターンデータ処理用プログラムをコンピュータに実行させることにより、パターンデータ処理装置２００を構築することが可能になる。
【０１４５】
また、本発明の実施の形態によれば、コンピュータに前述したパターンデータ処理方法を実行させるためのパターンデータ処理用プログラムを記録したコンピュータ読み取り可能な記録媒体が提供できる。
【０１４６】
尚、本発明の実施の形態は種々の変更が可能である。例えば、本発明の実施の形態では、パターンデータ処理の例としてＬＳＩの例で説明したが、ＦＰＤのパターンデータをはじめとして、階層化された複数のセルを有するパターンデータに所定の処理を行う場合に適用可能である。
【産業上の利用可能性】
【０１４７】
ＬＳＩやＦＰＤのパターンデータをはじめとして階層化された複数のセルを有するパターンデータの論理演算処理、検査処理、変更処理等の各種処理に適用できる。
【符号の説明】
【０１４８】
１０１、１０２、３０１〜３０６、５０１〜５０５・・・パターン
１０３、４０１、４０２・・・共通侵入領域
２００・・・パターンデータ処理装置
２０１・・・パターンデータ処理部
２０２・・・表示部
２０３・・・操作部
２０４・・・記憶部
２０５・・・共通侵入領域算出処理部
２０６・・・図形処理部
２０７・・・セル間重複パターン抽出処理部
２０８・・・共通侵入領域検出処理部
２０９・・・共通データ領域処理部
２１０・・・影響範囲処理部
２１１・・・セルデータ
２１２・・・共通侵入領域データ
２１３・・・記録媒体
２１４・・・影響範囲算出処理部
２１５・・・共通データ領域算出処理部
２１６・・・セル間重複領域検出処理部
２１７・・・パターンデータ
３０７、３０８・・・影響範囲
３０９、６０１、６０２・・・ＡＮＤ領域
３１０、３１１・・・境界パターン
Ｔｏｐ、Ａ、Ｂ、Ｃ、Ｄ、Ｘ・・・セル
３１２、３１３・・・影響範囲
３１４・・・ＳＵＢ領域
３１５、３１６・・・境界パターン
３１７、３１８・・・領域
【技術分野】
【０００１】
本発明は、階層化された複数のセルを有するパターンデータに対して、論理演算処理等の予め定めた所定の処理を行うパターンデータ処理方法、パターンデータ処理装置、前記パターンデータ処理方法をコンピュータに実行させるためのパターンデータ処理用プログラム及び前記パターンデータ処理用プログラムを記録したコンピュータ読み取り可能な記録媒体に関する。
【背景技術】
【０００２】
従来から、携帯電話の表示パネルやＦＰＤ（Flat Panel Display）等の表示装置のマスクパターン設計、ＬＳＩ（Large Scale Integration circuit）設計、ＭＥＭＳ（Micro Electro Mechanical Systems）設計、機構設計等、多岐の分野にわたってＣＡＤ（Computer Aided Design）が利用されている。
ＬＳＩやＭＥＭＳ、ＦＰＤ等において、素子や配線パターン等の構成要素のレイアウトパターンを複数のレイヤに分けたパターンデータによって構成し、前記パターンデータを基に、マスクを使用したフォトリソグラフィや印刷技術を用いて最終製品を製造することは、近年の大量生産を支える基本技術となっている。
【０００３】
レイアウトパターンは、最終製品上に形成される形状を示す設計の最終データであり、設計上及び製造上から来る最小の線幅や間隔等の各種ルールを満たす必要があるため、レイアウトパターンの検査処理等のパターンデータ処理が必要である。また、製造のために、レイアウトパターンの重複除去処理や、サイジングをはじめとするデータ変更処理等の種々のパターンデータ処理が必要不可欠となっている。
【０００４】
そのために、ＬＳＩやＦＰＤ等のレイアウトパターン(換言すれば、マスクパターン)データが製造上必要なルールを満たすことの検証(デザインルールチェック)を行う場合や、電子線描画装置のための描画データを作成する場合等に、パターンデータの検証処理や変更処理等のパターンデータに対する所定の処理を行うために、種々のパターンデータ処理方法やパターンデータ処理装置が利用されている。
【０００５】
特にＬＳＩでは、近年の製造プロセスの微細化に伴うデータ規模の増大が著しく、パターンデータ処理の高速化が課題となっている。この解決策として、パターンデータが階層構造を有する複数の階層セルを有するように構成し、各セルの階層構造に着目して、同一のデータは境界領域を除き一度だけ処理することによって処理の効率化を図るようにした階層処理方法が開発されている（例えば、特許文献１、２参照）。
【０００６】
しかしながら、前記特許文献１、２に記載された処理方法では、各階層セル間で各階層セルのパターンが重複しない領域或いは各階層セル間で各階層のパターンが重複する領域を、下位階層セル内部の周囲領域とするように設計制約を設けている。そして、係る厳しい設計制約を前提として所定のパターンデータ処理を行うようにしている。前記制約条件を満たすパターンのみの場合は処理の効率化を図り得るが、前記制約条件を満たさないパターンが存在する場合、処理効率が著しく低下したり、処理不能に陥る可能性がある。
【０００７】
ＬＳＩのパターンは、一般に階層セル間で大きく重複するものではないが、階層セル間のパターン重複禁止領域や重複領域をセル内部の周囲領域に限定することは、レイアウト設計上厳しい制約となり、設計結果のチップサイズ増大や設計期間の増加など大きな弊害となってしまう。
一方、パターンのサイジング処理や寸法チェック処理など階層セル間のパターンの影響が距離に依存する処理は、前記特許文献１、２に記載された処理方法でも実現可能である。しかしながら、例えば重複関係のある図形を選択する等のトポロジーを使用した対象選択処理では、階層間の影響を距離で限定できないため、正確な結果を得ることができないという問題がある。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開平６−２１６０１２号公報
【特許文献２】特開２００２−１９７１３０号公報
【発明の開示】
【発明が解決しようとする課題】
【０００９】
本発明は、前述したような厳しい設計制約を設けることなく、階層化された複数のセルを有するパターンデータに対して論理演算処理等の予め定めた所定の処理を効率的に行うことを課題としている。
【課題を解決するための手段】
【００１０】
本発明の第１の視点によれば、階層化された複数のセルを有するパターンデータに対して予め定めた所定の処理を行うパターンデータ処理方法において、セル毎に外部から当該セルに侵入する外部パターンを検出し、前記外部パターンが当該セルに侵入する領域を共通侵入領域として当該セルに関連付ける共通侵入領域算出ステップと、セルに関連付けられた前記共通侵入領域に基づいて、前記所定の処理の内容に応じて、当該セルの中で前記外部パターンとともに前記所定の処理を行う必要のある領域を当該セルの影響範囲として算出する影響範囲算出ステップと、セルのデータ存在領域から当該セルの影響範囲を除外した領域を当該セルの共通データ領域として算出する共通データ領域算出ステップと、前記各セルの共通データ領域については前記所定の処理を一度行うと共に前記影響範囲については当該セルに侵入する前記外部パターンとともに前記所定の処理を行うことにより、前記パターンデータに対する前記所定の処理を行うパターンデータ処理ステップとを備えて成ることを特徴とするパターンデータ処理方法が提供される。
【００１１】
また、本発明の第２の視点によれば、階層化された複数のセルを有するパターンデータに対して予め定めた所定の処理を行うパターンデータ処理装置において、セル毎に外部から当該セルに侵入する外部パターンを検出し、前記外部パターンが当該セルに侵入する領域を共通侵入領域として当該セルに関連付ける共通侵入領域算出手段と、セルに関連付けられた前記共通侵入領域に基づいて、前記所定の処理の内容に応じて、当該セルの中で前記外部パターンとともに前記所定の処理を行う必要のある領域を当該セルの影響範囲として算出する影響範囲算出手段と、セルのデータ存在領域から当該セルの影響範囲を除外した領域を当該セルの共通データ領域として算出する共通データ領域算出手段と、前記各セルの共通データ領域については前記所定の処理を一度行うと共に前記影響範囲については当該セルに侵入する前記外部パターンとともに前記所定の処理を行うことにより、前記パターンデータに対する前記所定の処理を行うパターンデータ処理手段とを備えて成ることを特徴とするパターンデータ処理装置が提供される。
【００１２】
また、本発明の第３の視点によれば、コンピュータに階層化された複数のセルを有するパターンデータに対して予め定めた所定の処理を実行させるためのパターンデータ処理用プログラムにおいて、本発明に係るパターンデータ処理方法をコンピュータに実行させることを特徴とするパターンデータ処理用プログラムが提供される。
【００１３】
また、本発明の第４の視点によれば、コンピュータに本発明のパターンデータ処理方法を実行させるためのパターンデータ処理用プログラムを記録したコンピュータ読み取り可能な記録媒体が提供される。
【発明の効果】
【００１４】
本発明のパターンデータ処理方法によれば、厳しい設計制約を設けることなく、階層化された複数のセルを有するパターンデータに対して論理演算処理等の予め定めた所定の処理を効率的に行うことが可能になる。
また、本発明のパターンデータ処理装置によれば、厳しい設計制約を設けることなく、階層化された複数のセルを有するパターンデータに対して論理演算処理等の予め定めた所定の処理を効率的に行うことが可能になる。
また、コンピュータが本発明のパターンデータ処理用プログラムを実行することにより、厳しい設計制約を設けることなく、階層化された複数のセルを有するパターンデータに対して論理演算処理等の予め定めた所定の処理を効率的に行うことが可能になる。
また、本発明の記録媒体に記録したパターンデータ処理用プログラムをコンピュータに実行させることにより、厳しい設計制約を設けることなく階層化された複数のセルを有するパターンデータに対して論理演算処理等の予め定めた所定の処理を効率的に行うことが可能なパターンデータ処理装置を構築することが可能になる。
【図面の簡単な説明】
【００１５】
【図１】本発明の原理を説明するための説明図である。
【図２】本発明の実施の形態に係るパターンデータ処理装置のブロック図である。
【図３】本発明の実施の形態におけるセル間重複パターン検出処理を示すフローチャートである。
【図４】本発明の実施の形態における共通侵入領域検出処理を示すフローチャートである。
【図５】本発明の実施の形態におけるセルを示す図である。
【図６】本発明の実施の形態におけるセルの階層構造を示す図である。
【図７】本発明の実施の形態におけるセル間重複パターン検出処理を示す説明図である。
【図８】本発明の実施の形態におけるセル間重複パターン検出処理を示す説明図である。
【図９】本発明の実施の形態におけるセル間重複パターン検出処理を示す説明図である。
【図１０】本発明の実施の形態におけるセル間重複パターン検出処理を示す説明図である。
【図１１】本発明の実施の形態におけるセル間重複パターン検出処理を示す説明図である。
【図１２】本発明の実施の形態におけるセル間重複パターン検出処理を示す説明図である。
【図１３】本発明の実施の形態におけるセル間重複パターン検出処理を示す説明図である。
【図１４】本発明の実施の形態における共通侵入領域検出処理を示す説明図である。
【図１５】本発明の実施の形態における共通侵入領域検出処理を示す説明図である。
【図１６】本発明の実施の形態における共通侵入領域検出処理を示す説明図である。
【図１７】本発明の実施の形態における共通侵入領域検出処理を示す説明図である。
【図１８】本発明の実施の形態におけるＡＮＤ処理を示すフローチャートである。
【図１９】本発明の実施の形態におけるＡＮＤ処理を示す説明図である。
【図２０】本発明の実施の形態におけるＡＮＤ処理を示す説明図である。
【図２１】本発明の実施の形態におけるＡＮＤ処理を示す説明図である。
【図２２】本発明の実施の形態におけるＡＮＤ処理を示す説明図である。
【図２３】本発明の実施の形態におけるＡＮＤ処理を示す説明図である。
【図２４】本発明の実施の形態におけるＡＮＤ処理を示す説明図である。
【図２５】本発明の実施の形態におけるＡＮＤ処理を示す説明図である。
【図２６】本発明の実施の形態におけるＳＵＢ処理を示す説明図である。
【図２７】本発明の実施の形態におけるＳＵＢ処理を示す説明図である。
【図２８】本発明の実施の形態におけるＳＵＢ処理を示す説明図である。
【図２９】本発明の実施の形態におけるＳＵＢ処理を示す説明図である。
【発明を実施するための形態】
【００１６】
本発明の実施の形態の概要を説明すると、階層化された複数のセルを有するパターンデータに対して論理演算処理等の予め定めた所定の処理（パターンデータ処理）を行う場合、先ず、パターンデータのレイヤ毎に、各セルの外部から各セル内に実際に侵入するパターン（外部パターン）の形状を検出する。
セルはパターンの集合であり又パターンデータの構成要素である。各セルは、自セルの内部に他のセルを参照することによって階層構造を成している。パターンデータは前記階層化された複数のセルによって構成される。
【００１７】
尚、或るセルへのパターンの侵入とは、「参照点ごとに、或るセルと前記或るセルの傘下にある全ての下位階層セルとを除外した残り全てのパターンのうちの、いずれかのパターンが、前記或るセルのデータが存在する領域（データ存在領域）に対して重なること」を意味している。ここで、「或るセルの全ての下位階層セル」とは、「或るセルの傘下にある全ての下位の階層セル」の意味である。「或るセルの傘下にある下位階層セル」とは、「下位階層セルから順に上位階層へ辿って行ったとき、前記或るセルに到達することができる場合の当該下位階層セル」を意味している。
【００１８】
次に、各セルに侵入する前記外部パターンの形状のＯＲ領域（以下、共通侵入領域と称す。）を求める。次に、前記共通侵入領域を基に、前記外部パターンの影響でパターンデータ処理の結果が不正確になる（換言すれば、外部パターンが異なることによってパターンデータ処理の結果が異なる）可能性がある各セル内領域（以下、影響範囲と称す。）を抽出する。前記影響範囲はパターン処理の内容に応じて定められる。このようにして、前記外部パターンの形状を基に前記影響範囲を求める。
【００１９】
次に、前記処理結果が異なる可能性のあるセル内のパターンは、影響範囲を元に抽出することができる。したがって、前記処理結果が異なる可能性のあるセル内のパターンは、前記外部パターンとマージして前記所定のパターンデータ処理を行う。前記処理結果が共通となる（換言すれば、外パターンが異なってもパターンデータ処理の結果が同じになる）セルのパターンについても影響範囲を元に抽出することができ、これについては単独で一度だけ前記所定のパターンデータ処理を行う。
【００２０】
尚、影響範囲は、セル内の演算結果が外部パターンの影響で変動する領域、換言すればセル内パターンの影響で外部の演算結果が変動する領域である。即ち、影響範囲は、パターンデータ全体について最終的に正しいパターンデータ処理の結果を得るためには、外部パターンとセル内のパターンをマージした上で演算することが必要なセル内領域を意味している。
【００２１】
これにより、パターンデータ全体に対して所定のパターンデータ処理が行われる。このようにして、セル間のパターン重複領域をセル内周囲の領域に設定することなく、所定のパターンデータ処理を行うことが可能となる。したがって、厳しい設計制約を設けることなく、階層化された複数のセルを有するパターンデータに対して、論理演算処理等の予め定めた所定の処理を効率的に行うことが可能になる。
【００２２】
パターンデータ処理には、パターンの論理演算を行う論理演算処理、パターンの大きさやパターン間の間隔等を変更する変更処理、パターンの大きさやパターン間の間隔等を検査する検証処理、パターンの形状やパターン間の重複関係でパターンを選択する選択処理などがある。より具体的には、ＡＮＤ処理やＯＲ処理等の論理演算処理、配線や素子のパターンのサイズを変更するサイジング処理、パターンや素子等の寸法チェック処理、あるいは重複するパターンだけの抽出等を行う対象選択処理等、種々のパターンデータ処理がある。
パターンデータ処理の内容に応じて影響範囲は異なることになる。しかしながら、いずれのパターンデータ処理の場合でも、パターンデータ処理の内容に応じて、外部パターンの形状を基に前記影響範囲を決定することが可能である。
【００２３】
本発明の実施の形態の概要について更に詳しく説明すると、仮に、或るセルが参照している複数の同一構成のセル（参照点）に対して、参照点毎にセル内に外部パターンが侵入する領域（パターン侵入領域）を基にしてパターンデータ処理を行うとした場合には、参照点数に応じたオーダーの処理を行うことになり、各セルの全てのパターンを展開して処理することと同等の膨大なデータ処理量になってしまう。
一方、参照点の一箇所でもパターン侵入領域が存在すると、影響範囲に対するパターンデータ処理の結果は前記パターン侵入領域の影響によって変わるため、全ての参照点で同一の処理結果が得られるわけではない。しかしながら、この影響範囲を除いた領域に対するパターンデータ処理の結果は、全ての参照点で同一となる。
【００２４】
階層処理で必要なのは、同一の結果となるデータは一度だけの処理とすることであるから本発明の実施の形態では、先ず、セル毎に全ての参照点で外部パターンが侵入する形状のＯＲ領域（以下、共通侵入領域と称す。）を求めておく。次に、前記共通侵入領域に基づいて、パターンデータ処理の内容に応じた影響範囲を算出し、セル内のパターンデータが存在し得る最大領域から前記影響範囲を除いた領域（以下、共通データ領域と称す。）についてパターンデータ処理を行う。
【００２５】
前記共通データ領域についてのパターンデータ処理の結果をこの階層セルの処理結果とすることにより、共通データ領域についてのパターンデータ処理は一度だけの処理とすることが可能となる。
前記影響範囲については、各セル毎に、外部パターンにマージして個別にパターンデータ処理を行う。このように共通データ領域と影響範囲に分けてパターンデータ処理を行い、それらの処理結果を統合することにより、パターンデータ全体についてのパターンデータ処理を行うことが可能になる。
【００２６】
前記影響範囲は、パターンデータ処理の結果として得られるパターン形状が、共通侵入領域に含まれる外部パターンの影響を受けて変更される可能性のある、セル内の最大領域である。同様に共通データ領域は、共通侵入領域に含まれる外部パターンの影響を受けずに、パターンデータ処理を行うことが可能な領域であり、パターンデータ処理結果として得られるパターン形状が、外部パターンによって変更されることがないセル内の最大領域である。
セルの共通データ領域は、当該セルのデータが存在する領域であるデータ存在領域から当該セルの影響範囲を除外した領域である。
【００２７】
例えば、ＡＮＤ処理、ＯＲ処理、ＳＵＢ処理等の論理演算処理では、共通侵入領域の内側領域の処理結果のみが外部パターンによって変更され、共通侵入領域の外側領域の処理結果が変更されることはない。
また、ＷＩＤＴＨ処理（パターンの幅を指定した検証）、ＳＰＡＣＥ処理（パターンの間隔を指定した検証）、ＥＮＣ処理（包含余裕を指定した検証）等の寸法チェック処理やサイジング処理では、共通侵入領域からルールによって指定した幅に応じた外側の領域までの処理結果が変更される可能性がある。例えば、共通侵入領域からルール値の範囲は一般に影響を受けるが、コーナー部の仕様としてルール値の√２倍の距離まで外部パターンが影響する場合、これを考慮して影響範囲を算出する必要がある。
【００２８】
また、指定レイヤと重複するパターンを抽出するなどの対象選択処理では、共通侵入領域と重複するセル内パターンは、外部パターンの有無により選択あるいは非選択の演算結果が異なる可能性があるため、前記共通侵入領域と重複するセル内パターン全体が影響範囲となる。
【００２９】
このように、共通侵入領域が同一の場合でも、パターンデータ処理の内容によって影響範囲は異なることになる。共通侵入領域に含まれる外部パタ−ンの形状によってパターンデータ処理の結果が異なってしまう最大の領域を考慮して影響範囲を求めることにより、共通侵入領域に基づいてパターンデータ処理の内容に応じた影響範囲を容易に求めることが可能である。
【００３０】
例えば、多くのパターンデータ処理内容の影響範囲は距離により規定でき、この場合共通侵入領域を一定距離拡大した領域を影響範囲とすることができる。また、外部パターンが接触や重複、包含など接続することでパターンデータ処理内容の結果が異なる場合、共通侵入領域が接触するパターン全体により影響範囲を規定することができる。このように、パターンデータ処理内容により影響範囲を規定する項目を明確化し、この項目が最大となる形状を共通侵入領域に含まれる外部パタ−ンの形状に仮定することで、影響範囲を求めることができる。
【００３１】
影響範囲についてパターンデータ処理する場合、影響範囲内の処理結果を決定するために必要な範囲のセル内パターン（以下、境界パターンと称す。）を例えばデータ展開し、セル外のパターンとマージして個別処理することで、各参照点の個別のパターンデータ処理結果を得ることができる。尚、共通侵入領域からの影響と同様に、影響範囲内の処理結果は、影響範囲の近傍のパターンから演算内容に応じた影響を受ける。このため、前記境界パターンは影響範囲の外部のパターンを含む場合もある。この範囲を求める方法は、共通侵入領域から影響範囲を求める方法と同様である。
【００３２】
このとき、境界パターンの形状により、セル内の処理結果に比べてパターンが追加される部分と削除される部分がある。パターンが追加される部分は、上位階層セルに処理結果のパターンとして追加すればよいことから、セル内の処理結果に影響はない。パターンが削除される部分は、上位階層セルで削除することができないため、削除される可能性のある部分をセル内の結果から予め削除しておき、セル内の該当部分と合わせた結果を上位階層セル内に作成する等の方法をとることになる。
【００３３】
ここで、実際のパターンデータ処理方法は、必ずしも前記のように共通データ領域に対応する階層のパターンデータ処理と、展開された共通侵入領域に基づく影響範囲のパターンデータ処理とに限定するものではない。影響範囲のパターンデータ処理結果に対し、参照点ごとに新たなセルとしこれを参照することで、同一の処理結果を共通化する方法を採用することや、あるいは共通データ領域とあわせた新たなセルとする方法を採用することも可能である。
【００３４】
また、共通侵入領域に基づく影響範囲は、参照点毎に個別処理が必要となるため、処理時間短縮のためにはできるだけ少ないことが望ましい。このため、パターンデータ処理の内容をより詳細に考慮して影響範囲を狭い範囲にするような算出方法を採用することは可能である。
【００３５】
また、各セルにおいて、当該セル内の下位階層を含めた全てのデータを包含する領域（データ存在領域）は、当該セルにおいて全てのレイヤで共通であるようにしている。データ存在領域は、全てのデータを包含するＸＹ軸方向に沿った長方形が基本であるが、
・データが存在しない大面積の領域がある場合、データが存在しない部分を除く
・距離に依存する処理に対して、その影響距離分拡張する
・領域の外部の重複関係が検出できない場合、外部を全て重複すると扱う
等のバリエーションは可能である。
以上により、重複領域に厳しい制約を設けることなく、正確で効率的な階層処理を実現することが可能となる。
【００３６】
以下、本発明の実施の形態について、図面を参照しながら詳細に説明する。
図１は、本発明の実施の形態の原理を説明するための説明図で、ＬＳＩ（Large Scale Integration circuit）の例を示している。
パターンデータは、フォトリソグラフィで使用するマスクに対応した複数のレイヤ構造を持っており、パターンデータ処理もこのレイヤを基準に実行する。
【００３７】
このため、パターンデータを構成する各セルのレイヤ毎に、セルの外部からパターン（外部パターン）が侵入した領域を共通侵入領域として保持する。共通侵入領域は、外部パターンが侵入した領域の個々の形状は不要であり、侵入した個々の領域を結合し、それを枠取りした形状でよい。即ち、階層セルの共通侵入領域は、外部パターンのうちの当該階層セルのデータ存在領域に侵入した部分をＯＲ処理することによって得られる領域である。次に、パターンデータ処理の処理内容に応じて、共通侵入領域を基にして、外部パターンと一緒にパターンデータ処理する必要のある領域（影響範囲）を求める。
【００３８】
影響範囲の処理は、階層セル内のパターンのうち影響範囲の処理に必要な範囲のパターンを、上位階層セルに展開する等して、外部パターンと一緒に個別処理する。セルのデータ存在領域から前記影響範囲を除いた部分は、セルの外部の処理とは無関係に独立して処理可能な部分（共通データ領域）である。この部分は、一度だけ処理しておけば、同一セルの共通データ領域に関する処理が、パターンデータにおける他の領域においても必要な場合には、当該処理結果を利用することができる。
【００３９】
共通侵入領域が同じ場合でも、影響範囲の算出方法はパターンデータ処理の内容に応じた演算処理毎に異なるが、影響範囲は共通侵入領域を基準に求めることができる。したがって、共通侵入領域を一度求めておけば、階層処理を行う場合に、実際にパターンデータ処理に影響を与える影響範囲や共通データ領域を容易に求めることが可能になる。影響範囲については個別にパターンデータ処理すると共に、共通データ領域については一度だけパターンデータ処理することにより、厳しい制約を設けることなく、正確で効率的な階層処理を実現することが可能となる。
【００４０】
図１（ｉ）において、セルａ、セルｂは階層構造を有しており、セルａは上位階層セル（例えばトップ（Ｔｏｐ）セル）、セルｂは下位階層セルである。セルａは２つのセルｂを参照点として有すると共に、配線等のパターン１０１、１０２を有している。パターン１０１、１０２は、セルｂから見れば、外部からセルｂ内へ侵入する外部パターンである。
尚、各セルに含まれるパターン等のデータは各セルのデータ存在領域内に存在するが、図１の例では、各セルａ、セルｂのデータ存在領域は実線の長方形枠で囲まれた領域である。以下の各図においても、セルのデータ存在領域は実線の長方形枠で囲まれた領域としているが、他の形状の枠をデータ存在領域とすることができる。
【００４１】
図１（ｉｉ）に示すように、パターン１０１、１０２のうち各セルｂに侵入する部分のＯＲ処理を行うことにより、共通侵入領域１０３が得られる。共通侵入領域１０３は、参照点（図１の例ではセルｂ）のいずれかに外部のパターン１０１、１０２が侵入する領域である。共通侵入領域１０３を基に、パターンデータ処理の演算内容に応じたセルｂの影響範囲が決定できる。
【００４２】
影響範囲は、パターンデータ処理が例えばＡＮＤ処理やＯＲ処理等の論理演算処理の場合には、共通侵入領域１０３に含まれる領域となる。パターンデータ処理がサイジング処理や寸法チェック処理の場合には、影響範囲は、共通侵入領域を所定サイズ幅拡大した領域となる。また、パターンデータ処理が対象選択処理の場合には、影響範囲は、共通侵入領域内に外部パターンが存在することによってパターンデータ処理の結果（選択又は非選択）が変化するパターン全体の領域となる。
【００４３】
影響範囲は、上位階層セルａの演算処理を行う際に上位階層セルａとマージして演算が必要な領域である。下位階層セルｂのデータ存在領域から影響範囲を除いた部分は、他の処理から独立してパターンデータ処理可能な領域（共通データ領域）である。
このように、本発明の実施の形態は、各セル毎に共通侵入領域１０３を求めておき、共通侵入領域１０３を用いて論理演算処理等の各種のパターンデータ処理を行うことを特徴とするものである。
【００４４】
また、本発明の実施の形態は、各セル毎に求めた共通侵入領域を基に、パターンデータ処理の内容に応じた影響範囲を求め、影響範囲については上位に展開して個別にパターンデータ処理を行い、セルのデータ存在領域から影響範囲を除外した共通データ領域については一度だけパターンデータ処理を行うことにより、パターンデータ全体のパターンデータ処理を行うことを特徴とするものである。
【００４５】
即ち、本発明の実施の形態では、セルの階層構造に着目して、各セルの参照点毎に、当該セルと前記当該セルの傘下にある全ての下位階層セルとを除外した残り全てのパターンから当該セルのデータ存在領域に侵入するパターン（これらのパターンを纏めて外部パターンと称す。）を検出して、各セルに外部パターンが侵入する全ての領域の和を当該セルの共通侵入領域として関連付けて持たせておく。
【００４６】
パターンデータ処理を行う際に、共通侵入領域及びパターンデータ処理の内容に応じて影響範囲及び共通データ領域を算出する。前記共通データ領域については一度のみのパターンデータ処理とすることにより、同一セルが複数使用されている場合にパターンデータ処理回数を低減する。また、前記影響範囲についてはセル毎に個別にパターンデータ処理を行う。
これにより、パターンデータ処理全体に対する処理が可能になるため、厳しい設計制約を設けることなく、効率的に階層的パターンデータ処理を実現できる。
【００４７】
以下、本発明の実施の形態に係るパターンデータ処理方法、パターンデータ処理装置、前記パターンデータ処理方法をコンピュータに実行させるためのパターンデータ処理用プログラム及び前記パターンデータ処理用プログラムを記録したコンピュータ読み取り可能な記録媒体について、図面に沿って詳細に説明する。尚、各図において、同一部分には同一符号を付している。
【００４８】
図２は、本発明の実施の形態に係るパターンデータ処理装置２００のブロック図である。
図２において、パターンデータ処理装置２００は、コンピュータによって構成することができ、ＣＡＤ（Computer Aided Design）によって作成したパターンデータ２１７に対する論理演算等の各種処理を行う機能を有している。本実施の形態では、パターンデータとしてＬＳＩのパターンデータ２１７の例を示している。パターンデータ２１７は、階層化された複数のセルから成るセルデータ２１１を有している。
【００４９】
セルのデータ（セルデータ）はレイアウトデータとも称され、セルデータ２１１は複数のセルデータによって構成されている。各セルのセルデータは、配線パターンや電子回路素子等の構成要素（レイアウト図形要素）の多角形の図形データと当該多角形の座標データを有しており又、参照するセルのデータとして、セル名称、座標、反転・回転・繰り返し等のデータを有している。
【００５０】
パターンデータ２１７は複数のセルデータによって構成され、セルデータ２１１の一部若しくは全部の複数のセルデータによって構成される。複数のセルデータ２１１の中から、ＬＳＩや表示装置のパターンデータ処理対象を表すのに必要な複数のセルデータが組み合わされてパターンデータ２１７が構成されている。
【００５１】
パターンデータ処理装置２００は、中央処理装置（ＣＰＵ）によって構成されパターンデータ処理を行うパターンデータ処理部２０１、液晶表示装置（ＬＣＤ）等によって構成された表示部２０２、マウスやキーボードを有する操作部２０３、パターンデータ処理部２０１が実行するプログラムや各種データを記憶する記憶部２０４を備えている。
記憶部２０４は磁気ディスク等によって構成されている。記憶部２０４には、処理対象のパターンデータ２１７がパターンデータ処理を行う前に格納される。
【００５２】
ＣＤ−ＲＯＭ（Compact Disc − Read Only Memory）等のコンピュータ読み取り可能な記録媒体２１３には、パターンデータ処理部２０１が実行するパターンデータ処理用プログラムが記録されている。記録媒体２１３に記録された前記パターンデータ処理用プログラムは、記憶部２０４のプログラム領域に記憶して利用される。
パターンデータ処理部２０１は、記憶部２０４に記憶したパターンデータ処理用プログラムを実行することにより、共通侵入領域算出処理部２０５及び図形処理部２０６を構築する。
【００５３】
共通侵入領域算出処理部２０５は、ＣＡＤによって作成され記憶部２０４に記憶されたパターンデータ２１７を利用して共通侵入領域を算出する機能を有する。共通侵入領域算出処理部２０５は、セル間の重複領域を検出するセル間重複領域検出処理部２１６、セル間の重複パターンを抽出するセル間重複パターン抽出処理部２０７、及び、外部パターンから共通侵入領域を検出する共通侵入領域検出処理部２０８を有している。外部パターンは、セル間重複パターンと、上位階層セルのパターンの中の各セル内に侵入するパターンとを合わせたものである。
【００５４】
セル間重複領域検出処理部２１６は、セル毎に、当該セルのセルゾーンと、他の全ての同位階層のセルのセルゾーンとが重複する領域（セル間重複領域）を検出する。ここで、前記他の全ての同位階層のセルは、前記当該セルの全ての上位階層セル（前記当該セルよりも１階層上位の全てのセル）によって直接参照されているセルである。
【００５５】
セル間重複パターン抽出処理部２０７はセル間重複パターン抽出処理を行う。セル間重複領域検出処理部２１６によるセル間重複領域検出処理と、セル間重複パターン抽出処理部２０７によるセル間重複パターン抽出処理とによって、セル間重複パターン検出処理が行われる。
【００５６】
セル間重複パターン検出処理は、セル毎に、前記セル間重複領域に存在する当該セルおよび当該セルの傘下にある最下位階層セルに至るまでの全ての下位階層セルのパターンを検出する処理である。ここで、セルゾーンはセルのデータ存在領域（上位階層セルから見れば参照点）であり、当該セルの全データを包含する領域である。セルゾーンは必ずしも長方形でなくてもよい。
【００５７】
共通侵入領域検出処理部２０８は共通侵入領域検出処理を行う。共通侵入領域検出処理は、セルデータ２１１のセル毎に、当該セルに侵入する外部パターンの侵入部分をＯＲ処理することによって得られる領域（共通侵入領域）を求める処理である。共通侵入領域検出処理部２０８は、求めた共通侵入領域の形状データを、当該セルの共通侵入領域データとして当該セルに対応付けて記憶する。
【００５８】
セル間重複領域検出処理部２１６のセル間重複領域検出処理、セル間重複パターン抽出処理部２０７のセル間重複パターン抽出処理及び共通侵入領域検出処理部２０８の共通侵入領域検出処理によって共通侵入領域算出処理が行われる。
尚、パターンデータ２１７を構成する全てのセルについて共通侵入領域検出処理を予め行うようにすれば、他のパターンデータに対するパターンデータ処理を行う場合に各セルの共通侵入領域を利用することができるが、処理を短時間で済ませる場合には、パターンデータ２１７を構成するセルについてのみ共通侵入領域検出処理を行うようにしてもよい。
【００５９】
図形処理部２０６は、共通侵入領域データ２１２を用いて、パターンデータ２１７に対して所定のパターンデータ処理を行う処理部である。図形処理部２０６は、影響範囲算出処理部２１４、共通データ領域算出処理部２１５、共通データ領域処理部２０９及び影響範囲処理部２１０を備えている。
【００６０】
影響範囲算出処理部２１４は、パターンデータ処理の内容に応じて、セルの共通侵入領域に基づいて当該セルの影響範囲を求める処理を行う。
共通データ領域算出処理部２１５は、セルのデータ存在領域と当該セルの影響範囲から共通データ領域を求める処理を行う。
共通データ領域処理部２０９は各セルの共通データ領域についてパターンデータ処理を行う。影響範囲処理部２１０は各セルの影響範囲についてパターンデータ処理を行う。
【００６１】
図形処理部２０６は、共通データ領域処理部２０９と影響範囲処理部２１０が行ったパターンデータ処理の結果を統合することによって、パターンデータ２１７全体に対するパターンデータ処理結果を得る。図形処理部２０６は、このパターンデータ処理結果を記憶部２０４に記憶する。
【００６２】
ここで、表示部２０２は表示手段を構成し、操作部２０３は操作手段を構成し、記憶部２０４は記憶手段を構成し、パターンデータ処理部２０１は処理手段を構成している。
また、共通侵入領域算出処理部２０５は共通侵入領域算出手段を構成し、図形処理部２０６はデータ処理手段を構成している。
また、セル間重複領域検出処理部２１６はセル間重複領域検出手段を構成し、セル間重複パターン抽出処理部２０７はセル間重複パターン抽出手段を構成し、共通侵入領域検出処理部２０８は共通侵入領域検出手段を構成している。
また、セル間重複領域検出処理部２１６及びセル間重複パターン抽出処理部２０７はセル間重複パターン検出手段を構成している。
【００６３】
また、影響範囲算出処理部２１４は影響範囲算出手段を構成し、共通データ領域算出処理部２１５は共通データ領域算出手段を構成している。
また、共通データ領域処理部２０９は共通データ領域処理手段を構成し、影響範囲処理部２１０は影響範囲処理手段を構成している。
また、図形処理部２０６から影響範囲算出処理部２１４及び共通データ領域算出処理部２１５を除いた部分はパターンデータ処理手段を構成している。
【００６４】
図３は、本実施の形態におけるセル間重複パターン検出処理を示すフローチャートで、パターンデータ処理部２０１が記憶部２０４に記憶したパターンデータ処理用プログラムを実行することによって行う処理である。セル間重複パターン検出処理はパターンデータ処理部２０１のセル間重複領域検出処理部２１６及びセル間重複パターン抽出処理部２０７が行う。
【００６５】
セル間重複パターン検出処理は、各セルのデータ存在領域が他の全ての同位階層のセルのデータ存在領域と重複する領域（セル間重複領域）を検出する処理であるセル間重複領域検出処理（ステップＳ３０１〜Ｓ３０５、Ｓ３１０）と、セルの傘下にある最下位階層セルに至るまでの全ての下位階層セルのパターンのうち、当該セルのセル間重複領域に重複するパターンであるセル間重複パターンを抽出するセル間重複パターン抽出処理（ステップＳ３０６〜Ｓ３０９、Ｓ３１１）を有している。
【００６６】
図４は、本実施の形態における共通侵入領域検出処理を示すフローチャートで、パターンデータ処理部２０１が記憶部２０４に記憶したパターンデータ処理用プログラムを実行することによって行う処理である。共通侵入領域検出処理はパターンデータ処理部２０１の共通侵入領域検出処理部２０８が行う。
【００６７】
図５は本発明の実施の形態で使用するセルを示す図で、図６は本実施の形態で使用する各セルの階層構造を示す図である。
図５及び図６に示すように、図５（ｉ）は最上位階層（トップ）セルＴｏｐ、図５（ｉｉ）はセルＴｏｐの１階層下位に位置しセルＴｏｐが参照する階層セルＡ、図５（ｉｉｉ）はセルＴｏｐの１階層下位に位置しセルＴｏｐが参照する階層セルＢ、図５（ｉｖ）は階層セルＡの下位階層に位置し階層セルＡが参照する階層セルＣ、図５（ｖ）は階層セルＡ及び階層セルＢの下位階層に位置し階層セルＡ及び階層セルＢが参照する階層セルＤである。
【００６８】
参照セルは、当該参照セルの一階層上のセルによって参照されるセルである。また、参照セルは、当該参照セルの一階層上のセルに直接含まれるセルである。セルＣは、セルＡを介して間接的にセルＴｏｐに含まれるため、セルＴｏｐの参照セルではない。セルＤも、セルＡ、セルＢを介して間接的にセルＴｏｐに含まれるため、セルＴｏｐの参照セルではない。
【００６９】
セルＴｏｐは、ＬＳＩ全体を表すパターンデータ２１７に相当し、２つのセルＡ及び１つのセルＢを参照セルとして有すると共に、最上位階層のパターンとしてパターン５０１を有している。
セルＡは、１つのセルＣ及び１つのセルＤを参照セルとして含むと共に、当該セルＡの階層のパターンとしてパターン５０２を有している。
【００７０】
セルＢは、１つのセルＤを参照セルとして含むと共に、当該セルＢの階層のパターンとしてパターン５０３を有している。
セルＣは、最下位階層（ボトム）のセルであり、参照セルを含んでおらず、当該セルＣの階層のパターンとしてパターン５０４を有している。
セルＤはセルＣと同様に、最下位階層（ボトム）のセルであり、参照セルを含んでおらず、当該セルＤの階層のパターンとしてパターン５０５を有している。
【００７１】
セルＡ、Ｂ、Ｃ、Ｄは、セルＴｏｐの傘下にあるセルである。セルＡの傘下にあるセルはセルＣ、Ｄである。セルＢの傘下にあるセルはセルＤのみである。セルＣはセルＡの傘下にある下位階層セルではあるが、セルＢの下位階層セルではない。セルＤはセルＡ、Ｂの傘下にある下位階層セルである。セルＡ、Ｂは同位階層のセル（1階層上に同じ上位階層セルを有するセル）である。
【００７２】
セルＣ、Ｄは、セルＡを基準にして見た場合、セルＡの1階層下にあるため、セルＣ、ＤはセルＡを基準とする場合には同位階層である。しかしながら、セルＢを基準にして見た場合には、セルＤはセルＢの1階層下にあるが、セルＢの１階層下には位置しないため、セルＣ、ＤはセルＢを基準とする場合には同位階層ではない。
【００７３】
セルゾーンはすべてのレイヤを対象としたものであるため、セルゾーンには当該セルの全てのレイヤのパターンが含まれる。しかし、パターンは共通侵入領域を求めるレイヤのパターンのみ記述しているため、セルゾーンの含まれるパターンの範囲とレイヤに含まれる範囲は必ずしも一致していない。
【００７４】
図７〜図１３はセル間重複パターン検出処理の説明図で、図７〜図１０はセル間重複領域検出処理の説明図、図１１〜図１３はセル間重複領域を用いて行うセル間重複パターン検出処理の説明図である。セル間重複領域検出処理と、セル間重複パターン抽出処理によってセル間重複パターン検出処理が行われる。
【００７５】
また、図１４〜図１７は共通侵入領域検出処理の説明図である。
前述したように、前記セル間重複パターン検出処理及び共通侵入領域検出処理を行うことによって共通侵入領域が算出される。
以下、図２〜図１７を用いて、セル間重複パターン検出処理及び共通侵入領域検出処理を含む共通侵入領域算出処理について説明する。
【００７６】
共通侵入領域算出処理部２０５のセル間重複領域検出処理部２１６及びセル間重複パターン抽出処理部２０７は、記憶部２０４からパターンデータ処理の対象であるパターンデータ２１７を読み込んで、図３のセル間重複パターン検出処理を行う。
セル間重複パターン検出処理では、セル間重複領域検出処理部２１６がセル間重複領域検出処理（処理ステップＳ３０１〜Ｓ３０５、Ｓ３１０）を行い、セル間重複パターン抽出処理部２０７がセル間重複パターン抽出処理（処理ステップＳ３０６〜３０９、Ｓ３１１）を行う。
【００７７】
［セル間重複領域検出処理］
セル間重複領域検出処理は、セル間重複領域検出処理部２１６が全セルに対してセル毎に、当該セルのセルゾーンが同位階層の他のセルのセルゾーンと重複するセル間重複領域を検出すると共に、当該セルから直接参照されている全てのセル（換言すれば、当該セルが参照している１階層下位の全てのセル）のセルゾーンのうち、当該セルのセル間重複領域に含まれる下位セルの領域を下位セルのパターンの展開が必要な領域（以下、パターン展開必要領域と称する。）として検出するために行う処理である。
【００７８】
セル間重複領域に含まれる当該セルと各下位階層セルのパターンは、重複する相手セルに対する侵入パターンであり、これを求めるためには、セル間重複領域に含まれる最下位階層セルまでのパターンを展開する必要がある。これを効率的に行うため、セル間重複領域に含まれる一階層下位のセルのセルゾーンをパターン展開必要領域として検出して下位階層セルに登録し、順次最下位階層まで伝播させる。
【００７９】
具体的には、最上位階層セルから最下位階層セルまでの全てのセル（換言すればパターンデータ２１７として使用している全てのセル）に対して、最上位階層セルから最下位階層セルへ順に、処理ステップＳ３０１〜Ｓ３０５、Ｓ３１０の処理を行う。最上位階層セルから最下位階層セルまでの使用している全てのセルまで、当該セルに含まれる一階層下位のセル間のセル間重複領域の検出を行うと共に、当該セルが有するセル間重複領域と当該セルが有するパターン展開必要領域とのＯＲ領域に対して一階層下位のセルのセルゾーンとの間の重複領域を当該下位階層セルのパターン展開必要領域として順次検出する。
【００８０】
尚、パターン展開必要領域の分配処理（ステップＳ３０２）を行う前に当該セルのセル間重複領域が求められていればよく、パターン展開必要領域の分配処理（ステップＳ３０２）とセル間重複領域登録処理（ステップＳ３０４）は必ずしも同一セルに対し連続して行う必要は無い。ここで、上下階層間のように直接参照する関係にあるものや、あるいは他の階層を挟んで複数階層にまたがり引用関係にあるもの（換言すれば、間接的に参照する関係にあるもの）は、セル間の重複としては扱わず、パターン展開あるいは後述するパターンの侵入の場合にのみ評価する。
【００８１】
（ｉ）下位階層セルのセルゾーン計算処理ステップ（ステップＳ３０１）
処理ステップＳ３０１では、現時点でセル間重複領域作成の対象としているセルが参照している下位階層セルのセルゾーンを計算する。図７（ｉ）は、最上位階層セルＴｏｐの例である。最上位階層セルＴｏｐは下位階層として、２つのセルＡと１つのセルＢを参照している。
【００８２】
（ｉｉ）パターン展開必要領域の分配処理（ステップＳ３０２）
処理ステップＳ３０２では、当該セルのセル間重複領域とパターン展開必要領域のＯＲ領域を下位階層セルに分配する。前記分配処理は、下位階層セルと当該セルの前記ＯＲ領域の関係を抽出処理し、下位の各セルと重複するＯＲ領域を下位セルのパターン展開必要領域として順次追加する処理である。
【００８３】
図８（ｉ）は最上位階層セルＴｏｐの例である。セルＴｏｐは上位階層セルや同位階層セルがないため、同位階層の他のセルとの重複が無く又上位から侵入するパターンも無く、セル間重複領域がない。したがって、セルＴｏｐのセル間重複領域に含まれる一階層下のセルＡ、Ｂのセル領域（セルＡ、Ｂのパターン展開必要領域）も無い。
【００８４】
尚、当該セルのセル間重複領域は、当該セルの上位階層セルについて成された下位階層セルのセル間重複領域登録処理（ステップＳ３０４）によって得られたものを用い、当該セルのパターン展開必要領域は当該セルを直接参照している全てのセル（換言すれば、当該セルを参照している１階層上位の全てのセル）についてのパターン展開必要領域の分配処理（ステップＳ３０２）によって得られたものを用いる。
【００８５】
例えばセルＡの場合は、図８（ｉｉ）に示すように、処理ステップＳ３０４によって得られたもの（図１０（ｉ）参照）を用いる。セルＡはハッチングで示すセル間重複領域を有しているが、パターン展開必要領域は有していない。セルＡのセル間重複領域とセルＡのパターン展開領域のＯＲ領域（ここでは、セルＡはパターン展開必要領域は無い。）と、下位階層セルＣのセルゾーンとが重複しており、前記重複する領域がセルＣのパターン展開必要領域となる。
【００８６】
（ｉｉｉ）下位階層セルの重複領域検出処理（ステップＳ３０３）
処理ステップＳ３０３では、上位階層セルにおいて、下位階層セルのセルゾーンの重複部分をセル間重複領域として抽出する。図９（ｉ）のハッチング部分が、前記下位階層セルのセル間重複領域である。
【００８７】
（ｉｖ）下位階層セルのセル間重複領域登録処理（ステップＳ３０４）
処理ステップＳ３０４では、（ｉｉｉ）で求めた下位階層セルのセル間重複領域を当該下位階層セルのセル間重複領域として重複相手セルのセル間重複領域と関連付けて追加登録する。相手セル、領域とも同一のものが既に登録されている場合、追加は行わない。（図１０（ｉ））。
【００８８】
ここで得られたセル間重複領域のデータは、前述したように次の下位階層セルのパターン展開必要領域の分配処理（ステップＳ３０２）で使用される（ステップＳ３１０）。
前記処理を最上位階層セルから最下位階層セルまで順に終了するまで繰り返す（ステップＳ３０５）。このとき処理するセルの順序は、上位階層セルについての処理が全て終了しているセルを処理対象として選択する。
【００８９】
セルＡに関して前記処理を行う場合、図７（ｉｉ）、図８（ｉｉ）、図９（ｉｉ）、図１０（ｉｉ）の順で処理が行われ、図１０（ｉｉ）に示すように、セルＣ、Ｄのセル間重複領域とパターン展開必要領域のＯＲ領域が検出される。セルＢ〜Ｄに関しても同様の処理が行われる。これにより、セル毎にセル間重複領域が検出される。セル間重複領域に存在する当該セルおよび最下位階層に至るまでの下位セルのパターンは、他のいずれかのセルへ侵入するものである。
最上位階層セルから最下位階層セルまで全てのセルについて前記セル間重複領域検出処理が完了すると、次のセル間重複パターン抽出処理が行われる。
【００９０】
［セル間重複パターン抽出処理］
セル間重複パターン抽出処理部２０７は、セル毎に、前記のようにして検出したセル間重複領域においてセル間で重複するパターン（セル間重複パターン）を検出するためのセル間重複パターン検出処理を行う。セル間重複パターン検出処理では、全てのセルに対して、最下位階層セルから最上位階層セルへ順序に、処理ステップＳ３０６〜Ｓ３０９、Ｓ３１１の処理を行う。
【００９１】
（ｉ）評価対象パターン検出処理（ステップＳ３０６）
処理ステップＳ３０６では、現時点でセル間重複パターン検出処理の対象としているセルのパターンと、当該セルから直接参照されている全てのセル（換言すれば、当該セルが参照している１階層下位のセル）から展開された展開パターンのＯＲ処理を行い、前記ＯＲ処理の結果得られたパターンを当該セルの評価対象パターンとする。評価対象パターンとは、当該セルとその下位階層セルのパターンのうち、当該セルおよび上位階層におけるセル間重複パターンであるか否かの評価の対象となるパターンである。
【００９２】
図１１（ｉ）は、現時点のセル間重複パターン検出処理対象のセルが最下位階層セルＣ、Ｄの例である。最下位階層セルＣ、Ｄは参照点である下位階層セルを有しないため、下位から展開された展開パターン（上位階層セル間重複パターン）が無く、セル内のパターンのみが対象となる。
【００９３】
尚、前記下位階層セルからの展開パターンは、当該セルから直接参照されている全てのセル（換言すれば、当該セルが参照している１階層下位の全てのセル）に関するパターン展開必要領域のパターン展開処理（ステップＳ３０７）によって得られたものを用いる。例えば、セルＡの場合は、（図１２（ｉｉ）、ステップＳ３０７）によって得られたものを用いる。
以上のようにして、セル内のパターンと、当該セルが参照している１階層下位の全ての階層セルから展開された展開パターンとをＯＲ処理することによって得られるパターンである評価対象パターンが、セル毎に得られる。
【００９４】
（ｉｉ）パターン展開必要領域のパターン展開処理（ステップＳ３０７）
処理ステップＳ３０７では、前記検出した評価対象パターンのうちパターン展開必要領域に存在するもの（展開パターン）を、当該セルを直接参照している全ての上位セル（換言すれば、当該セルを参照している１階層上位の全てのセル）における当該セルの参照点に展開する。図１２（ｉ）は、セルＣからセルＡへの展開パターンである。尚、セルＡにはパターン展開必要領域が無いため（図８参照）、図１２（ｉｉ）に示すように、セルＡからセルＴｏｐへの展開パターンは無い。
【００９５】
前述したように、ここで得られた展開パターンは、次の上位階層セルの評価対象パターン検出処理（ステップＳ３０６）で使用される（ステップＳ３１１）。
ここでは、全ての当該セルの参照点に展開しているが、パターン展開必要領域の分配処理（ステップＳ３０２）において、分配元となった上位セル名と位置をパターン展開必要領域と合わせて登録することで、必要な参照点にのみ展開することも可能である。どちらの手順も処理効率の違いであり、共通侵入領域の算出結果は同一となる。
【００９６】
（ｉｉｉ）セル間重複パターン登録処理（ステップＳ３０８）
処理ステップＳ３０８では、前記検出した評価対象パターンのうちセル間重複領域に存在するものを、セル間重複パターンとして重複相手セル名および重複位置に関連付けて記憶部２０４に記憶する。セルＣ、Ｄに関して得られたセル間重複パターンは、図１３（ｉ）のハッチングで示す領域となる。図１３に示すように、自セル内のパターンのうち、セル間重複領域と重複するパターン部分が、セル間重複パターンとなる。セル間重複パターンは、同じセル間重複領域を有する他のセルへ侵入するパターンとなる。
【００９７】
前記処理を最下位階層セルから最上位階層セルまで順に終了するまで繰り返す（ステップＳ３０９）。このときの順序は、当該セルから直接参照されている全ての下位階層セル（換言すれば、当該セルが参照している１階層下位のセル）についてセル間重複パターン抽出処理が終了しているセルを、セル間重複パターン抽出処理の対象として選択する。
【００９８】
セルＡに関して前記処理を行う場合、図１１（ｉｉ）、図１２（ｉｉ）、図１３（ｉｉ）となる。セルＡのセル間重複パターンは、図１２（ｉｉ）の評価対象パターンとセル間重複領域とが重なる領域であり、図１３（ｉｉ）のハッチングを付した領域となる。他のセルに関しても同様の処理が行われる。以上のようにしてセル間重複パターン検出処理が行われることにより、各セル毎に、同じセル間重複領域を有する他のセルへ侵入するセル間重複パターンが得られる。
【００９９】
このように、本発明の実施の形態では、先ずセル間重複領域を検出しておき、次に、評価対象パターンのうち前記セル間重複領域に重複するパターンをセル間重複パターンとして求めるようにしているため、はじめから各セル内の全ての領域についてセル間重複パターンを求める方法に比べて、少ないデータ規模で求めることが可能になる。
【０１００】
次に、共通侵入領域検出処理部２０８は、前述した処理によって記憶部２０４に記憶されたセル間重複パターンのデータを読み込んで、図４の共通侵入領域検出処理を行う。
［共通侵入領域検出処理］
共通侵入領域検出処理では、最上位階層セルから最下位層セルまでの全てのセルに対して、上位階層セルから下位階層セルへ順に、処理ステップＳ４０１〜Ｓ４０６を行う。
【０１０１】
（１）セル間侵入領域作成処理（ステップＳ４０１）
処理ステップＳ４０１では、現時点で共通侵入領域検出処理の対象としているセルと同位階層のセルを当該セルの重複相手セルとして、処理ステップＳ３０８で関連付けられた全てのセル間重複パターンを、当該セルの対応する位置（当該セルと重複相手セルの重なる位置）にセル間侵入領域として作成する。セル間侵入領域は、当該セルに関連付けられた他の全ての同位階層セル（前記重複相手セル）のセル間重複パターンを、当該セルのデータ存在領域内の対応する位置に配置したものである。
【０１０２】
図１４（ｉ）は最上位階層セルＴｏｐの例であり、セルＴｏｐには同位階層セルが存在しないため、最上位階層セルＴｏｐにはセル間侵入領域は無い。セルＡ、Ｂのセル間侵入領域は図１４（ｉ）に示すようになり又、セルＣ、Ｄのセル間侵入領域は図１４（ｉｉ）のようになる。
尚、このステップをここで行うのではなく、処理ステップＳ３０８でセル間重複パターンを登録する代わりに、このステップの処理とあわせ、重複相手セルへセル間侵入領域を登録することも同一の結果を得ることができる。
【０１０３】
（２）共通侵入領域完成処理（ステップＳ４０２）
処理ステップＳ４０２では、当該セルを直接参照している全ての上位階層セル（換言すれば、当該セルを参照している１階層上位の全てのセル）から切り出した侵入領域（即ち、１階層上位の全てのセルに含まれるパターンのうち、当該セルのデータ存在領域に重なる領域）と前記セル間侵入領域のＯＲ処理を行うことにより、セル毎に共通侵入領域算出処理が完了する。前記ＯＲ処理の結果得られる領域が共通侵入領域であり、これを図１５に示す。
【０１０４】
図１５（ｉ）は最上位階層セルＴｏｐの例であり、セルＴｏｐには上位階層セルが存在しないため、上位階層セルから切り出した侵入領域図形は無く、したがって共通侵入領域は無い。セルＡの場合には、最上位階層セルＴｏｐのパターン中のセルＡと重なる領域が「上位階層セルから切り出した侵入領域」となり、図１５（ｉｉ）のハッチングで示す共通侵入領域が得られる。
尚、前記全ての上位階層セル（即ち、当該セルを参照している１階層上位の全てのセル）から切り出した侵入領域は、上位階層セルの下位階層侵入領域作成処理（ステップＳ４０４）によって得られたものを用いる。
【０１０５】
（３）下位階層侵入評価パターン作成処理（ステップＳ４０３）
処理ステップＳ４０３では、当該セルの共通侵入領域と、前記共通侵入領域検出処理対象セルの対象レイヤのパターン（下位階層のパターンは含まない）とのＯＲ処理を行うことにより、下位階層に対する侵入評価パターン（下位階層侵入評価パターン）を作成する。下位階層侵入評価パターンとは、上位階層セルから下位階層セルのデータ存在領域内に侵入するか否かの判定対象となるパターンである。図１６（ｉ）は最上位階層セルＴｏｐの例であり、最上位階層セルＴｏｐには上位階層セルが存在しないため、前記共通侵入領域は無く、したがって下位階層侵入評価パターンはセルＴｏｐの対象レイヤのパターン（ハッチング領域）のみとなる。セルＡの下位階層侵入評価パターンは図１６（ｉｉ）のハッチング領域となる。
【０１０６】
（４）分配処理（ステップＳ４０４）
処理ステップＳ４０４では、前記下位階層侵入評価パターンを参照点毎に下位階層のセルに分配する（図１７（ｉ））。前記分配処理は、参照セルゾーンと下位階層侵入評価パターンの重なり領域を抽出処理し、抽出した領域を対応するセルに付与する処理である。
前記分配された領域は図１４に示したセル間侵入領域に追加処理されて（図１７（ｉ））、図１５の共通侵入領域が得られる。図１７（ｉ）では、セルＡ、Ｂの侵入領域及び分配された下位階層侵入評価パターンにハッチングが付されており、これらが図１５の共通侵入領域となる。
【０１０７】
このように、当該セルの共通侵入領域と当該セルのパターンとのＯＲ処理の結果を下位階層セルに分配することで、下位セルにおける上位セルからの侵入領域を算出する。前述したように、ここで得られた侵入領域のデータは、下位階層セルの共通侵入領域の完成処理（ステップＳ４０２）で使用される。
【０１０８】
前記処理を最上位階層セルから最下位階層セルまで順に終了するまで繰り返す（ステップＳ４０５）。このときの順序は、全ての上位階層セルの処理が終了したセルを対象として選択する。このときの順序は、その全ての上位階層セルについて共通侵入領域検出処理が終了しているセルを、共通侵入領域検出処理の対象として選択する。
セルＡに関して前記処理を行う場合、図１４（ｉｉ）、図１５（ｉｉ）、図１６（ｉｉ）、図１７（ｉｉ）となる。セルＣ、Ｄの場合、共通侵入領域は、図１７（ｉｉ）のハッチングを付した領域となる。他のセルに関しても同様の処理が行われ、共通侵入領域が得られる。共通侵入領域は、セル領域内で外部パターンが重複する可能性のある領域である。
【０１０９】
ここでは、セル間侵入領域（ステップＳ４０１）と上位セルパターンによる侵入領域（ステップＳ４０４）を別に求めているが、セルパターンと共通侵入領域の重複部分をドントケアとする場合、他の手順も可能である。たとえば、パターン展開必要領域とともにセル間重複領域に存在するパターンを上位階層セルに展開し、上位セルパターンによる侵入領域（ステップＳ４０４）にて一括して共通侵入領域を求めることができる。この場合も、共通侵入領域の計算方法が異なるが、セル間重複領域を求め、これをもとにセル間重複パターンを求めていることは同様である。
【０１１０】
次に、前述のようにして算出した共通侵入領域を用いて、パターンデータ２１７に対する所定の処理を行う例について説明する。
パターンデータ２１７に対する処理としては、パターンデータ２１７の形状や配置が正しいか否かの検証処理やパターンデータ２１７の変更処理等がある。また、パターンデータ処理には、ＡＮＤ処理、ＯＲ処理等の論理演算処理、セルが有するパターンの寸法を変更するサイジング処理、スペースやパターンの寸法チェック処理、対象選択処理等、種々の処理がある。以下に、パターンデータ処理の具体例を説明する。
【０１１１】
図１８は、パターンデータ処理部２０１の図形処理部２０６がパターンデータ処理としてＡＮＤ処理を行う場合のフローチャートである。
図１９は、パターンデータ２１７を構成するセルデータ２１１の中の、下位階層セルＸの構成を示す図である。セルＸは複数のレイヤ（本実施の形態では第１レイヤ及び第２レイヤ）を有するセルで、第１レイヤにパターン３０１を有し、第２レイヤにパターン３０２を有している。
【０１１２】
図２０は、パターンデータとしての最上位階層セルＴｏｐの構成を示す図である。セルＴｏｐは、２つのセルＸを参照セルとして有すると共に、第１レイヤにパターン３０３、３０４を有し又、第２レイヤにパターン３０５、３０６を有している。
図２１〜図２４は、パターンデータに対するＡＮＤ処理の説明図であり、セルＴｏｐにおける第１レイヤの全パターンと第２レイヤの全パターンとのＡＮＤ処理を行う動作の説明図である。
以下、図２、図１８〜図２４を用いて本実施の形態におけるパターンデータ処理の例として、異なるレイヤに存在するパターン同士のＡＮＤ処理について説明する。
【０１１３】
共通侵入領域算出処理部２０８は、各階層セル毎に全ての参照点（即ち、最上位階層セルＴｏｐに至るまでの全ての上位階層セルの中で当該セルを参照している箇所）における外部パターンの侵入部分をレイヤ毎に求め、前記各レイヤ毎の侵入部分のＯＲ領域を、各レイヤの共通侵入領域として当該セルに関連付けて記憶部２０４に格納する（図１８のステップＳ５０１）。
これにより、共通侵入領域として、図２１に示すように、第１レイヤの共通侵入領域４０１及び第２レイヤの共通侵入領域４０２が得られる。この共通侵入領域４０１、４０２は全ての演算で共通に使用できるものであり、レイヤ毎に一度だけ求める。
【０１１４】
次に、影響範囲算出処理部２１４は、共通侵入領域４０１、４０２に基づいて、パターンデータ処理の内容（ここではＡＮＤ処理）に応じて影響範囲を算出する。
一般に、２つのレイヤを入力する処理では、第１レイヤの共通侵入領域による影響（第１レイヤの影響）と第２レイヤの共通侵入領域による影響（第２レイヤの影響）は内容が異なる。同様に、境界パターンについても、それぞれのレイヤの影響範囲によりそれぞれに入力レイヤに対する効果が異なる。このため、
以下の４種を考慮する必要がある。
・第１レイヤの影響範囲による第１レイヤ境界パターン
・第１レイヤの影響範囲による第２レイヤ境界パターン
・第２レイヤの影響範囲による第１レイヤ境界パターン
・第２レイヤの影響範囲による第２レイヤ境界パターン
【０１１５】
パターンデータ処理がＡＮＤ処理の場合は、演算自体が距離に依存せずパターンの重複関係のみでパターンデータ処理結果が決定される。また、セル内パターンと外部パターンの同じレイヤの重複部分はセル内の処理結果が使用可能であり、他階層の処理結果は考慮不要（ドントケア（Don't Care））となる。
このことから、各レイヤの影響範囲は
・第１レイヤの影響範囲は、第１レイヤの共通侵入領域から第１レイヤのセル内パターンを除いた領域
・第２レイヤの影響範囲は、第２レイヤの共通侵入領域から第２レイヤのセル内パターンを除いた領域
となる。
【０１１６】
また、階層間にまたがって考慮が必要なケースは、セルのパターンと外部パターンので異なるレイヤのパターンが重複する部分のみであることから、ＡＮＤ処理の境界図形は、
・第１レイヤの影響範囲による第１レイヤ境界図形および第２レイヤの影響範囲による第２レイヤ境界図形は不要
・第１レイヤの影響範囲による第２レイヤ境界図形は、第１レイヤの影響範囲内に存在する、第２レイヤのセル内パターン
・第２レイヤの影響範囲による第１レイヤ境界図形は、第２レイヤの影響範囲内に存在する、第１レイヤのセル内パターン
である。
【０１１７】
したがって、図形処理部２０６の影響範囲算出処理部２１４は、共通侵入領域４０１、４０２から、共通侵入領域４０１、４０２と同一レイヤのセル内パターンとの重複領域を除いた領域を、演算処理で使用する影響範囲として算出する（ステップＳ５０２）。前記影響範囲は図２２に示すように、第１レイヤの影響範囲３０７、第２レイヤの影響範囲３０８となる。
【０１１８】
共通データ領域算出処理部２１５は、セルのデータ存在領域から前記影響範囲を除いた領域を共通データ領域として算出し、当該セルに関連付けて記憶部２０４に格納する（ステップＳ５０３）。ただし、ＡＮＤ処理の場合、第１レイヤの影響範囲、第２レイヤの影響範囲とも一方のレイヤのパターンしか存在せず、処理結果のパターンは存在しないため、前記影響範囲の削除は不要である。
【０１１９】
次に、共通データ領域処理部２０９は、記憶部２０４に記憶した前記セルの共通データ領域に対してＡＮＤ処理を行う。この場合、共通データ領域処理部２０９は前記ＡＮＤ処理を当該セル単体で行い、当該セルの共通データ領域に対するパターンデータ処理結果として当該セルに関連付けて記憶部２０４に格納する。共通データ領域処理部２０９は、図２３に示すように、下位階層セルＸについて単独で、第１レイヤと第２レイヤのＡＮＤ処理を行うことにより、共通データ領域に対するＡＮＤ処理結果として、ＡＮＤ領域３０９が得られる。
【０１２０】
次に、上位階層の演算に影響するセル内パターンを抽出するため、影響範囲処理部２１０は、図２４に示すように、第１レイヤのセル内パターン３０１と第２レイヤの影響範囲３０８との重複部分、第２レイヤのセル内パターン３０２と第１レイヤの影響範囲３０７との重複部分を各々第１レイヤ境界パターン３１０、第２レイヤ境界パターン３１１として算出し、全参照点に展開する（ステップＳ５０４）。
境界パターンは、セル内パターンのうち外部パターンと一緒に処理する必要のあるパターンであり、ＡＮＤ処理では影響範囲にある異なるレイヤのセル内パターンである。単なるＡＮＤ処理に比べると手順は複雑となるが、演算対象データ量はセル単位であり非常に少なくなるため、全体としては演算処理時間の短縮が可能となる。
【０１２１】
影響範囲処理部２１０は、図２５（ｉ）に示すように、当該セルから直接参照されている全ての下位階層セル（換言すれば、当該セルが参照している全ての１階層下位のセル）から展開した境界パターンと上位階層セルのパターンを相互にマージし、図２５（ｉｉ）に示すように上位階層セルの第１レイヤと第２レイヤのＡＮＤ処理を実行する（ステップＳ５０５）。これにより、領域６０１、６０２が得られる。
【０１２２】
図形処理部２０６は、図２５（ｉｉ）に示すように、共通データ領域処理部２０９がＡＮＤ処理を行うことによって算出した領域３０９と、影響範囲処理部２１０がＡＮＤ処理を行うことによって算出した領域６０１、６０２との和を、パターンデータ処理の結果として算出する。図形処理部２０６は、前記パターンデータ処理の結果を記憶部２０４に記憶する（ステップＳ５０６）。これにより、フラット処理と同じ演算結果を得ることができる。
【０１２３】
次に、パターンデータ処理としてＳＵＢ処理の例を、前記ＡＮＤ処理の例で使用したパターンデータを用いて説明する。ＳＵＢ処理に特有の処理を図２６〜図２９に示している。ＳＵＢ処理も、前記ＡＮＤ処理と同様に、図２のパターンデータ処理装置２００を用いて行われる。使用するパターンデータは、前述したＡＮＤ処理で用いたものと同じため、共通侵入領域は前記ＡＮＤ処理のものと同じであり、共通侵入領域４０１、４０２である。
ＳＵＢ処理は、処理自体が距離に依存せずパターンの重複関係のみで結果が決定されることはＡＮＤ処理と同様である。しかしながら、ＳＵＢ処理は、セル内パターンと外部パターンの重複に関しては、第１レイヤから第２レイヤを除く演算であるため、２つのレイヤで扱いがＡＮＤ処理の場合とは異なることになる。
【０１２４】
即ち、セル内の第２レイヤのパターンは、上位階層セルの第２レイヤのパターンが重複していても結果は変わらないが、第１レイヤのパターンが重複する場合、第２レイヤで削除するのはセル内のパターンだけではなく、上位のパターンも削除する必要がある。
つまりセル内の第１レイヤの有無に拘わらず全てのセル外部の第１レイヤと重複する領域は一度のみの共通の処理とすることができず、個別処理が必要になる。
【０１２５】
このことから、ＳＵＢ処理における各レイヤの影響範囲は
・第１レイヤの影響範囲は、第１レイヤの共通侵入領域全体
・第２レイヤの影響範囲は、第２レイヤの共通侵入領域から第２レイヤのセル内パターンを除いた領域
となる。
【０１２６】
また、階層間にまたがって考慮が必要なケースは、各レイヤの影響範囲と異なるレイヤのパターンが重複する部分であることから、ＳＵＢ処理の境界図形は、
・第１レイヤの影響範囲による第１レイヤ境界図形および第２レイヤの影響範囲による第２レイヤ境界図形は不要
・第１レイヤの影響範囲による第２レイヤ境界図形は、第１レイヤの影響範囲内に存在する、第２レイヤのセル内パターン
・第２レイヤの影響範囲による第１レイヤ境界図形は、第２レイヤの影響範囲内に存在する、第１レイヤのセル内パターン
である。
【０１２７】
したがって、図形処理部２０６の影響範囲算出処理部２１４は、第１レイヤの共通侵入領域４０１全体と同一の領域と、第２レイヤの共通侵入領域４０２から第２レイヤのセル内パターンと重複する領域を除いた領域とを、パターンデータ処理で使用する影響範囲として算出する（図１８の処理ステップＳ５０２及び図２１参照）。
その結果、図２６に示すように、第１レイヤの共通侵入領域４０１全体と同一の領域として、第１レイヤの影響範囲３１２が得られる（同図（ｉ））。また、第２レイヤの共通侵入領域４０２から第２レイヤのセル内パターンと重複する領域を除いた領域として、第２レイヤの影響範囲３１３が得られる（同図（ｉｉ））。
【０１２８】
ＳＵＢ処理の場合、第１レイヤの影響範囲は、セル内のパターンに影響しないため共通データ領域に対して考慮不要（ドントケア（Don't care））である。また、第２レイヤの影響範囲は、セル内パターンが削除される可能性がある領域に相当するため、共通データ領域から除く必要がある。
共通データ領域算出処理部２１５は、セルのデータ存在領域から前記第２レイヤの影響範囲を除いた領域を共通データ領域として算出し、当該セルに関連付けて記憶部２０４に格納する（ステップＳ５０３）。
【０１２９】
次に共通データ領域処理部２０９は、記憶部２０４に記憶した前記セルの共通データ領域に対してＳＵＢ処理を行う。この場合、共通データ領域処理部２０９は、セル内の共通データ領域の演算はセル単体で一度のみ演算を行い、共通データに関するセルの処理結果として各セルデータ２１１に関連付けて記憶部２０４に格納する。
【０１３０】
このため、セル内の演算処理（共通データ領域についてのＳＵＢ処理）は、図２７に示すように下位階層セルＸについて単独で、第１レイヤと第２レイヤのＳＵＢ処理を行い、さらに共通データ領域とＡＮＤ処理することにより、ＳＵＢ領域３１４が得られる。
上位階層セルの処理に影響するセル内パターンを抽出するため、影響範囲処理部２１０は、図２８に示すように、第１レイヤのセル内パターン３０１と第２レイヤの影響範囲３１３との重複部分及び第２レイヤのセル内パターン３０２と第１レイヤの影響範囲３１２との重複部分を、各々第１レイヤ境界パターン３１５、第２レイヤ境界パターン３１６として算出し、全参照点に展開する（ステップＳ５０４）。
【０１３１】
次に影響範囲処理部２１０は、図２９（ｉ）に示すように当該セルから直接参照されている全ての下位階層セル（換言すれば、当該セルが参照している全ての１階層下位のセル）から展開した境界パターンと上位階層セルのパターンを相互にマージし、図２９（ｉｉ）に示すように上位階層セルの第１レイヤと第２レイヤのＳＵＢ処理を実行する（ステップＳ５０４）。これにより、領域３１７、３１８が得られる。
【０１３２】
図形処理部２０６は、図２９（ｉｉ）に示すように、共通データ領域処理部２０９が算出した領域３１４と影響範囲処理部２１０が算出した領域３１７、３１８の和を、パターンデータ処理の結果として算出する。図形処理部２０６は、前記パターンデータ処理の結果を記憶部２０４に記憶する（ステップＳ５０６）。これにより、フラット処理と同じ演算結果を得ることができる。
【０１３３】
他のパターンデータ処理の例としてＯＲ処理の場合は、階層間で影響を及ぼさないため影響範囲はなく、各階層毎に独立にＯＲ処理を行えばよい。
【０１３４】
その他のパターンデータ処理も演算処理の内容や演算実現手順は異なるが、
（１）共通侵入領域を用いて、これにより結果が変化する範囲を影響範囲として入力レイヤごとに求め、
（２）セル内の演算を行うと共に影響範囲内で結果が不正となる可能性があるパターンを削除し、
（３）影響範囲に対する各参照点における個別処理に必要な境界パターンを作成して、上位階層の演算を順次実行する
ことにより、所定の階層的演算処理が実現できる。ここで、（１）〜（３）の実現手段は、これまでに例示したようにパターンデータ処理の内容により異なるが、いずれも共通侵入領域に基づいて決定可能である。
【０１３５】
以上述べたように、本発明の実施の形態に係るパターンデータ処理方法は、階層化された複数のセルを有するパターンデータに対して予め定めた所定の処理を行うパターンデータ処理方法において、セル毎に外部から当該セルに侵入する外部パターンを検出し、前記外部パターンが当該セルに侵入する領域を共通侵入領域として当該セルに関連付ける共通侵入領域算出ステップと、セルに関連付けられた前記共通侵入領域に基づいて、前記所定の処理の内容に応じて、当該セルの中で前記外部パターンとともに前記所定の処理を行う必要のある領域を当該セルの影響範囲として算出する影響範囲算出ステップと、セルのデータ存在領域から当該セルの影響範囲を除外した領域を当該セルの共通データ領域として算出する共通データ領域算出ステップと、前記各セルの共通データ領域については前記所定の処理を一度行うと共に前記影響範囲については当該セルに侵入する前記外部パターンとともに前記所定の処理を行うことにより、前記パターンデータに対する前記所定の処理を行うパターンデータ処理ステップとを備えて成ることを特徴としている。
【０１３６】
ここで、前記共通侵入領域算出ステップは、セルが同位階層の他のセルと重複する領域であるセル間重複領域を検出するセル間重複領域検出ステップと、各セルのパターンと各セルの最下位階層セルに至るまでの全ての下位階層セルのパターンの内、当該セルのセル間重複領域に重複するパターンであるセル間重複パターンを抽出するセル間重複パターン抽出ステップと、各セルに重複する同位階層の他のセルのセル間重複パターンと、当該セルの最上位階層に至るまでの全ての上位階層のセルのパターンのうち当該セルのデータ存在領域に重複するパターンとから成る前記共通侵入領域を算出する共通侵入領域検出ステップとを備えて成るように構成してもよい。
【０１３７】
また、前記セル間重複領域検出ステップは、各セルと同位階層セルとの間の重複領域をセル間重複領域として検出する処理と、最上位階層セルから最下位階層セルまで順に各セルのセル間重複領域と上位階層の処理で検出した当該セルのパターン展開必要領域のＯＲ領域の内、一階層下位のセルのデータ存在領域と重複する領域を下位階層のセルのパターン展開必要領域として検出する処理であり、
前記セル間重複パターン抽出ステップは、最下位階層セルから最上位階層セルまで順に、各セルのパターンと下位階層から展開された評価対象パターンを合わせたパターンを当該セルの評価対象パターンとし、当該セルのセル間重複領域に重複する評価対象パターンを当該セルのセル間重複パターンとして抽出すると共に、前記当該セルのパターン展開必要領域に存在する当該セルの評価対象パターンを上位階層に展開する処理であり、
前記共通侵入領域検出ステップは、最上位階層セルから最下位階層セルまで順に、各セルに重複する同位階層のセルのセル間重複パターンと、当該セルに重複する一階層上位のセルのパターンと、当該セルに重複する一階層上位のセルの共通侵入領域とから成る前記共通侵入領域を算出する処理であるように構成してもよい。
【０１３８】
前記影響範囲算出ステップは、セルに関連付けられた前記共通侵入領域に基づいて、前記所定の処理の内容に応じて、当該セルのデータ存在領域の中で、当該セル単独で前記所定の処理を行うと前記外部パターンの影響を受けて誤った結果が得られるため前記外部パターンとともに前記所定の処理を行う必要のある領域を当該セルの影響範囲として算出する処理である。
【０１３９】
本発明の実施の形態に係るパターンデータ処理方法は、前記のように構成されているため、厳しい設計制約を設けることなく、階層化された複数のセルを有するパターンデータに対して論理演算処理等の所定の処理を効率的に行うことができる。
また、レイアウト設計においては、階層間のパターン制約を考慮する必要がなく、従来と同じ設計条件のみを考慮しての設計が可能となるため、制約増加によるレイアウト面積の増加や設計工数、期間の増大が防止できる。パターンデータ処理においては、実際には重複がなくとも階層間のパターン制約によって展開されるパターン量より、実際階層間の重複による影響範囲のみのパターン量の方が一般に少なくできる。処理時間は、ほぼこの展開パターン量に依存するため、共通侵入領域作成にかかる時間以上に処理時間は短縮が可能となる。
【０１４０】
また、ＬＳＩやＦＰＤ等のためのレイアウトパターン(マスクパターン)設計にあたり、設計ルールを満たしていることの検証は、論理演算、サイジング、寸法チェック、対象選択処理などを組み合わせることで実現している。また、製造工程に受け渡すデータの作成も、同様にこれらの処理を組み合わせることで実現する。このような図形処理を、高速に実施するための階層処理の実現に用いることが可能である。
【０１４１】
また、本発明の実施の形態に係るパターンデータ処理装置２００は、階層化された複数のセルを有するパターンデータに対して予め定めた所定の処理を行うパターンデータ処理装置において、各セル毎に外部から当該セルに侵入する外部パターンを検出し、前記外部パターンが当該セルに侵入する領域を共通侵入領域として当該セルに関連付ける共通侵入領域算出処理部２０５と、セルに関連付けられた前記共通侵入領域に基づいて、前記所定の処理の内容に応じて、当該セルの中で前記外部パターンとともに前記所定の処理を行う必要のある領域を当該セルの影響範囲として算出する影響範囲算出処理部２１４と、セルのデータ存在領域から当該セルの影響範囲を除外した領域を当該セルの共通データ領域として算出する共通データ領域算出処理部２１５と、前記各セルの共通データ領域については前記所定の処理を一度行うと共に前記影響範囲については当該セルに侵入する前記外部パターンとともに前記所定の処理を行うことにより、前記パターンデータに対する前記所定の処理を行うパターンデータ処理手段とを備えて成ることを特徴としている。
【０１４２】
ここで、共通侵入領域算出処理部２０５は、セルが同位階層の他のセルと重複する領域であるセル間重複領域を検出するセル間重複領域検出処理部２１６と、各セルのパターンと各セルの最下位階層に至るまでの全ての下位階層セルのパターンの内、当該セルのセル間重複領域に重複するパターンであるセル間重複パターンを抽出するセル間重複パターン抽出処理部２０７と、各セルに重複する同位階層の他のセルのセル間重複パターンと、当該セルの最上位階層に至るまでの全ての上位階層のセルのパターンのうち当該セルのデータ存在領域に重複するパターンとから成る前記共通侵入領域を算出する共通侵入領域検出処理部２０８とを備えて成るように構成することができる。
【０１４３】
セル間重複領域検出処理部２１６は、各セルと同位階層セルとの間の重複領域をセル間重複領域として検出すると共に、最上位階層セルから最下位階層セルまで順に各セルのセル間重複領域と上位階層の処理で検出した当該セルのパターン展開必要領域のＯＲ領域の内、一階層下位のセルのデータ存在領域と重複する領域を下位階層のセルのパターン展開必要領域として検出し、
セル間重複パターン抽出処理部２０７は、最下位階層セルから最上位階層セルまで順に、各セルのパターンと下位階層から展開された評価対象パターンを合わせたパターンを当該セルの評価対象パターンとし、当該セルのセル間重複領域に重複する評価対象パターンを当該セルのセル間重複パターンとして抽出すると共に、前記当該セルのパターン展開必要領域に存在する当該セルの評価対象パターンを上位階層に展開し、
共通侵入領域検出処理部２０８は、最上位階層セルから最下位階層セルまで順に、各セルに重複する同位階層のセルのセル間重複パターンと、当該セルに重複する一階層上位のセルのパターンと、当該セルに重複する一階層上位のセルの共通侵入領域とから成る前記共通侵入領域を算出するように構成することができる。
本発明の実施の形態に係るパターンデータ処理装置２００は、前記のように構成されているため、厳しい設計制約を設けることなく、階層化された複数のセルを有するパターンデータに対して論理演算処理等の所定の処理を効率的に行うことができる等の効果を奏する。
【０１４４】
また、本発明の実施の形態によれば、コンピュータに階層化された複数のセルを有するパターンデータに対して予め定めた所定の処理を実行させるためのパターンデータ処理用プログラムにおいて、コンピュータに前述したパターンデータ処理方法を実行させることを特徴とするパターンデータ処理用プログラムが提供される。
コンピュータは本実施の形態に係るパターンデータ処理用プログラムを実行することにより、階層化された複数のセルを有するパターンデータに対して、予め定めた所定の処理を実行させることができる。
また、本発明の実施の形態に係るパターンデータ処理用プログラムをコンピュータに実行させることにより、パターンデータ処理装置２００を構築することが可能になる。
【０１４５】
また、本発明の実施の形態によれば、コンピュータに前述したパターンデータ処理方法を実行させるためのパターンデータ処理用プログラムを記録したコンピュータ読み取り可能な記録媒体が提供できる。
【０１４６】
尚、本発明の実施の形態は種々の変更が可能である。例えば、本発明の実施の形態では、パターンデータ処理の例としてＬＳＩの例で説明したが、ＦＰＤのパターンデータをはじめとして、階層化された複数のセルを有するパターンデータに所定の処理を行う場合に適用可能である。
【産業上の利用可能性】
【０１４７】
ＬＳＩやＦＰＤのパターンデータをはじめとして階層化された複数のセルを有するパターンデータの論理演算処理、検査処理、変更処理等の各種処理に適用できる。
【符号の説明】
【０１４８】
１０１、１０２、３０１〜３０６、５０１〜５０５・・・パターン
１０３、４０１、４０２・・・共通侵入領域
２００・・・パターンデータ処理装置
２０１・・・パターンデータ処理部
２０２・・・表示部
２０３・・・操作部
２０４・・・記憶部
２０５・・・共通侵入領域算出処理部
２０６・・・図形処理部
２０７・・・セル間重複パターン抽出処理部
２０８・・・共通侵入領域検出処理部
２０９・・・共通データ領域処理部
２１０・・・影響範囲処理部
２１１・・・セルデータ
２１２・・・共通侵入領域データ
２１３・・・記録媒体
２１４・・・影響範囲算出処理部
２１５・・・共通データ領域算出処理部
２１６・・・セル間重複領域検出処理部
２１７・・・パターンデータ
３０７、３０８・・・影響範囲
３０９、６０１、６０２・・・ＡＮＤ領域
３１０、３１１・・・境界パターン
Ｔｏｐ、Ａ、Ｂ、Ｃ、Ｄ、Ｘ・・・セル
３１２、３１３・・・影響範囲
３１４・・・ＳＵＢ領域
３１５、３１６・・・境界パターン
３１７、３１８・・・領域
【特許請求の範囲】
【請求項１】
階層化された複数のセルを有するパターンデータに対して予め定めた所定の処理を行うパターンデータ処理方法において、
セル毎に外部から当該セルに侵入する外部パターンを検出し、前記外部パターンが当該セルに侵入する領域を共通侵入領域として当該セルに関連付ける共通侵入領域算出ステップと、
セルに関連付けられた前記共通侵入領域に基づいて、前記所定の処理の内容に応じて、当該セルの中で前記外部パターンとともに前記所定の処理を行う必要のある領域を当該セルの影響範囲として算出する影響範囲算出ステップと、
セルのデータ存在領域から当該セルの影響範囲を除外した領域を当該セルの共通データ領域として算出する共通データ領域算出ステップと、
前記各セルの共通データ領域については前記所定の処理を一度行うと共に前記影響範囲については当該セルに侵入する前記外部パターンとともに前記所定の処理を行うことにより、前記パターンデータに対する前記所定の処理を行うパターンデータ処理ステップとを備えて成ることを特徴とするパターンデータ処理方法。
【請求項２】
前記共通侵入領域算出ステップは、
セルが同位階層の他のセルと重複する領域であるセル間重複領域を検出するセル間重複領域検出ステップと、
各セルのパターンと各セルの最下位階層セルに至るまでの全ての下位階層セルのパターンの内、当該セルのセル間重複領域に重複するパターンであるセル間重複パターンを抽出するセル間重複パターン抽出ステップと、
各セルに重複する同位階層の他のセルのセル間重複パターンと、当該セルの最上位階層に至るまでの全ての上位階層のセルのパターンのうち当該セルのデータ存在領域に重複するパターンとから成る前記共通侵入領域を算出する共通侵入領域検出ステップとを備えて成ることを特徴とする請求項１記載のパターンデータ処理方法。
【請求項３】
前記セル間重複領域検出ステップは、各セルと同位階層セルとの間の重複領域をセル間重複領域として検出する処理と、最上位階層セルから最下位階層セルまで順に各セルのセル間重複領域と上位階層の処理で検出した当該セルのパターン展開必要領域のＯＲ領域の内、一階層下位のセルのデータ存在領域と重複する領域を下位階層のセルのパターン展開必要領域として検出する処理であり、
前記セル間重複パターン抽出ステップは、最下位階層セルから最上位階層セルまで順に、各セルのパターンと下位階層から展開された評価対象パターンを合わせたパターンを当該セルの評価対象パターンとし、当該セルのセル間重複領域に重複する評価対象パターンを当該セルのセル間重複パターンとして抽出すると共に、前記当該セルのパターン展開必要領域に存在する当該セルの評価対象パターンを上位階層に展開する処理であり、
前記共通侵入領域検出ステップは、最上位階層セルから最下位階層セルまで順に、各セルに重複する同位階層のセルのセル間重複パターンと、当該セルに重複する一階層上位のセルのパターンと、当該セルに重複する一階層上位のセルの共通侵入領域とから成る前記共通侵入領域を算出する処理であることを特徴とする請求項２記載のパターンデータ処理方法。
【請求項４】
階層化された複数のセルを有するパターンデータに対して予め定めた所定の処理を行うパターンデータ処理装置において、
セル毎に外部から当該セルに侵入する外部パターンを検出し、前記外部パターンが当該セルに侵入する領域を共通侵入領域として当該セルに関連付ける共通侵入領域算出手段と、
セルに関連付けられた前記共通侵入領域に基づいて、前記所定の処理の内容に応じて、当該セルの中で前記外部パターンとともに前記所定の処理を行う必要のある領域を当該セルの影響範囲として算出する影響範囲算出手段と、
セルのデータ存在領域から当該セルの影響範囲を除外した領域を当該セルの共通データ領域として算出する共通データ領域算出手段と、
前記各セルの共通データ領域については前記所定の処理を一度行うと共に前記影響範囲については当該セルに侵入する前記外部パターンとともに前記所定の処理を行うことにより、前記パターンデータに対する前記所定の処理を行うパターンデータ処理手段とを備えて成ることを特徴とするパターンデータ処理装置。
【請求項５】
前記共通侵入領域算出手段は、
セルが同位階層の他のセルと重複する領域であるセル間重複領域を検出するセル間重複領域検出手段と、
各セルのパターンと各セルの最下位階層に至るまでの全ての下位階層セルのパターンの内、当該セルのセル間重複領域に重複するパターンであるセル間重複パターンを抽出するセル間重複パターン抽出手段と、
各セルに重複する同位階層の他のセルのセル間重複パターンと、当該セルの最上位階層に至るまでの全ての上位階層のセルのパターンのうち当該セルのデータ存在領域に重複するパターンとから成る前記共通侵入領域を算出する共通侵入領域検出手段とを備えて成ることを特徴とする請求項４記載のパターンデータ処理装置。
【請求項６】
前記セル間重複領域検出手段は、各セルと同位階層セルとの間の重複領域をセル間重複領域として検出すると共に、最上位階層セルから最下位階層セルまで順に各セルのセル間重複領域と上位階層の処理で検出した当該セルのパターン展開必要領域のＯＲ領域の内、一階層下位のセルのデータ存在領域と重複する領域を下位階層のセルのパターン展開必要領域として検出し、
前記セル間重複パターン抽出手段は、最下位階層セルから最上位階層セルまで順に、各セルのパターンと下位階層から展開された評価対象パターンを合わせたパターンを当該セルの評価対象パターンとし、当該セルのセル間重複領域に重複する評価対象パターンを当該セルのセル間重複パターンとして抽出すると共に、前記当該セルのパターン展開必要領域に存在する当該セルの評価対象パターンを上位階層に展開し、
前記共通侵入領域検出手段は、最上位階層セルから最下位階層セルまで順に、各セルに重複する同位階層のセルのセル間重複パターンと、当該セルに重複する一階層上位のセルのパターンと、当該セルに重複する一階層上位のセルの共通侵入領域とから成る前記共通侵入領域を算出することを特徴とする請求項５記載のパターンデータ処理装置。
【請求項７】
コンピュータに、階層化された複数のセルを有するパターンデータに対して予め定めた所定の処理を実行させるためのパターンデータ処理用プログラムにおいて、
コンピュータに請求項１乃至３のいずれか一に記載のパターンデータ処理方法を実行させることを特徴とするパターンデータ処理用プログラム。
【請求項８】
コンピュータに請求項１乃至３のいずれか一に記載のパターンデータ処理方法を実行させるためのパターンデータ処理用プログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項１】
階層化された複数のセルを有するパターンデータに対して予め定めた所定の処理を行うパターンデータ処理方法において、
セル毎に外部から当該セルに侵入する外部パターンを検出し、前記外部パターンが当該セルに侵入する領域を共通侵入領域として当該セルに関連付ける共通侵入領域算出ステップと、
セルに関連付けられた前記共通侵入領域に基づいて、前記所定の処理の内容に応じて、当該セルの中で前記外部パターンとともに前記所定の処理を行う必要のある領域を当該セルの影響範囲として算出する影響範囲算出ステップと、
セルのデータ存在領域から当該セルの影響範囲を除外した領域を当該セルの共通データ領域として算出する共通データ領域算出ステップと、
前記各セルの共通データ領域については前記所定の処理を一度行うと共に前記影響範囲については当該セルに侵入する前記外部パターンとともに前記所定の処理を行うことにより、前記パターンデータに対する前記所定の処理を行うパターンデータ処理ステップとを備えて成ることを特徴とするパターンデータ処理方法。
【請求項２】
前記共通侵入領域算出ステップは、
セルが同位階層の他のセルと重複する領域であるセル間重複領域を検出するセル間重複領域検出ステップと、
各セルのパターンと各セルの最下位階層セルに至るまでの全ての下位階層セルのパターンの内、当該セルのセル間重複領域に重複するパターンであるセル間重複パターンを抽出するセル間重複パターン抽出ステップと、
各セルに重複する同位階層の他のセルのセル間重複パターンと、当該セルの最上位階層に至るまでの全ての上位階層のセルのパターンのうち当該セルのデータ存在領域に重複するパターンとから成る前記共通侵入領域を算出する共通侵入領域検出ステップとを備えて成ることを特徴とする請求項１記載のパターンデータ処理方法。
【請求項３】
前記セル間重複領域検出ステップは、各セルと同位階層セルとの間の重複領域をセル間重複領域として検出する処理と、最上位階層セルから最下位階層セルまで順に各セルのセル間重複領域と上位階層の処理で検出した当該セルのパターン展開必要領域のＯＲ領域の内、一階層下位のセルのデータ存在領域と重複する領域を下位階層のセルのパターン展開必要領域として検出する処理であり、
前記セル間重複パターン抽出ステップは、最下位階層セルから最上位階層セルまで順に、各セルのパターンと下位階層から展開された評価対象パターンを合わせたパターンを当該セルの評価対象パターンとし、当該セルのセル間重複領域に重複する評価対象パターンを当該セルのセル間重複パターンとして抽出すると共に、前記当該セルのパターン展開必要領域に存在する当該セルの評価対象パターンを上位階層に展開する処理であり、
前記共通侵入領域検出ステップは、最上位階層セルから最下位階層セルまで順に、各セルに重複する同位階層のセルのセル間重複パターンと、当該セルに重複する一階層上位のセルのパターンと、当該セルに重複する一階層上位のセルの共通侵入領域とから成る前記共通侵入領域を算出する処理であることを特徴とする請求項２記載のパターンデータ処理方法。
【請求項４】
階層化された複数のセルを有するパターンデータに対して予め定めた所定の処理を行うパターンデータ処理装置において、
セル毎に外部から当該セルに侵入する外部パターンを検出し、前記外部パターンが当該セルに侵入する領域を共通侵入領域として当該セルに関連付ける共通侵入領域算出手段と、
セルに関連付けられた前記共通侵入領域に基づいて、前記所定の処理の内容に応じて、当該セルの中で前記外部パターンとともに前記所定の処理を行う必要のある領域を当該セルの影響範囲として算出する影響範囲算出手段と、
セルのデータ存在領域から当該セルの影響範囲を除外した領域を当該セルの共通データ領域として算出する共通データ領域算出手段と、
前記各セルの共通データ領域については前記所定の処理を一度行うと共に前記影響範囲については当該セルに侵入する前記外部パターンとともに前記所定の処理を行うことにより、前記パターンデータに対する前記所定の処理を行うパターンデータ処理手段とを備えて成ることを特徴とするパターンデータ処理装置。
【請求項５】
前記共通侵入領域算出手段は、
セルが同位階層の他のセルと重複する領域であるセル間重複領域を検出するセル間重複領域検出手段と、
各セルのパターンと各セルの最下位階層に至るまでの全ての下位階層セルのパターンの内、当該セルのセル間重複領域に重複するパターンであるセル間重複パターンを抽出するセル間重複パターン抽出手段と、
各セルに重複する同位階層の他のセルのセル間重複パターンと、当該セルの最上位階層に至るまでの全ての上位階層のセルのパターンのうち当該セルのデータ存在領域に重複するパターンとから成る前記共通侵入領域を算出する共通侵入領域検出手段とを備えて成ることを特徴とする請求項４記載のパターンデータ処理装置。
【請求項６】
前記セル間重複領域検出手段は、各セルと同位階層セルとの間の重複領域をセル間重複領域として検出すると共に、最上位階層セルから最下位階層セルまで順に各セルのセル間重複領域と上位階層の処理で検出した当該セルのパターン展開必要領域のＯＲ領域の内、一階層下位のセルのデータ存在領域と重複する領域を下位階層のセルのパターン展開必要領域として検出し、
前記セル間重複パターン抽出手段は、最下位階層セルから最上位階層セルまで順に、各セルのパターンと下位階層から展開された評価対象パターンを合わせたパターンを当該セルの評価対象パターンとし、当該セルのセル間重複領域に重複する評価対象パターンを当該セルのセル間重複パターンとして抽出すると共に、前記当該セルのパターン展開必要領域に存在する当該セルの評価対象パターンを上位階層に展開し、
前記共通侵入領域検出手段は、最上位階層セルから最下位階層セルまで順に、各セルに重複する同位階層のセルのセル間重複パターンと、当該セルに重複する一階層上位のセルのパターンと、当該セルに重複する一階層上位のセルの共通侵入領域とから成る前記共通侵入領域を算出することを特徴とする請求項５記載のパターンデータ処理装置。
【請求項７】
コンピュータに、階層化された複数のセルを有するパターンデータに対して予め定めた所定の処理を実行させるためのパターンデータ処理用プログラムにおいて、
コンピュータに請求項１乃至３のいずれか一に記載のパターンデータ処理方法を実行させることを特徴とするパターンデータ処理用プログラム。
【請求項８】
コンピュータに請求項１乃至３のいずれか一に記載のパターンデータ処理方法を実行させるためのパターンデータ処理用プログラムを記録したコンピュータ読み取り可能な記録媒体。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【公開番号】特開２０１３−６１７５３（Ｐ２０１３−６１７５３Ａ）
【公開日】平成２５年４月４日（２０１３．４．４）
【国際特許分類】
【出願番号】特願２０１１−１９９００２（Ｐ２０１１−１９９００２）
【出願日】平成２３年９月１３日（２０１１．９．１３）
【出願人】（５０４０７１３８４）株式会社ジーダット (8)
【Ｆターム（参考）】
【公開日】平成２５年４月４日（２０１３．４．４）
【国際特許分類】
【出願日】平成２３年９月１３日（２０１１．９．１３）
【出願人】（５０４０７１３８４）株式会社ジーダット (8)
【Ｆターム（参考）】
[ Back to top ]