JPH0620008A - レイアウトデータの論理演算方式 - Google Patents

Abstract

(57)【要約】 【目的】読出したレイアウトデータの形状を検証するた
めの、所要メモリ容量が少なく、且つ効率的な論理演算
方式を提供する。 【構成】図形データベース９０より読出し、マスク処理
工程ごとに分類されたレイアウトデータに含まれる頂点
を抽出し、頂点に点番号を与え、２つの頂点を連結した
辺に辺番号を与え頂点を格納する（ステップ１０１およ
び１０２）。次いで頂点をｘ軸方向にソートし、点番号
及び順位を格納する（ステップ１０３）。各順位に対応
する座標値で境界を想定して、その１つを順に選び、境
界上の頂点及び辺を取り出し、ｙ軸方向にソートして点
番号、辺番号、並びに順位を格納する（ステップ１０４
〜１０６）。隣接した２つの境界で、データを格納した
かを調べて（ステップ１０７）、格納している場合は論
理演算を行ない（ステップ１０８）、格納していない場
合は、ステップ１０４に戻る。ステップ１０８にて論理
演算終了後、すべての境界を選択したかを調べ（ステッ
プ１０９）、選択していない場合は、ステップ１０４に
戻り、選択している場合は処理を終了する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明はレイアウトデータの論理
演算方式に関し、特にスリット法によるレイアウトデー
タの論理演算方式に関する。

【０００２】

【従来の技術】従来のレイアウトデータの論理演算方式
としては、下記参考文献（１），（２），（３）および
（４）に見られるように、タッチング法、スリット法及
びビットマップ法がある。

【０００３】タッチング法は、図６（ａ）に示すよう
に、すべての多角形をそれに外接する方形２０１の左下
のｘおよびｙ座標でソートしておき、これをソート順に
取出しながら外接方形のｘ方向区間に辺をもつ多角形区
間でのみ論理演算を行う手法である。スリット法は、図
６（ｂ）に示すように、すべての多角形の頂点のｘ座標
でスリット２０２と呼ぶ領域に分割し、すべて水平及び
斜め辺をそのｘ座標で分割しながらスリット別に分割辺
２０３の集合を作成し、各スリット独立に異なる向きの
辺の組を抽出して論理演算を行う手法である。また、ビ
ットマップ法は、図７に示すように、すべての多角形の
頂点のｘおよびｙ座標でｘｙ平面全体を格子２０４に分
割し、各格子にパターン実体が存在する２０５か否２０
６かのビットをたて、そのビットマップにより論理演算
をおこ行う手法である。以上、タッチング法、スリット
法およびビットマップ法については、文献（２）の該当
部分を引用し、図７は文献（４）に掲載されている図を
参考にしている。なお、説明の都合上図番を変更し、注
釈を加えた箇所がある。 参考文献 （１）川西、西出、増田：”ＬＳＩマスクパターンの図
形処理の一算法”、信学論（Ａ）、Ｊ６３−Ａ，９，ｐ
ｐ．６１１−６１８ （２）築添、小澤、酒見、三浦、石井：”ＶＬＳＩマス
クデータに対する論理演算と交点計算を同時処理するパ
ターン論理演算手法”、信学論（Ｄ）、Ｊ６９−Ｄ，
６，ｐｐ．９７５−９８３（昭６１−０６） （３）坂本、野村、小野寺、田丸：”ＬＳＩレイアウト
デザインチェックに使用する図形演算ハードウェアエン
ジンのシステム設計”、信学論（Ａ）、Ｊ７１−Ａ，１
０，ｐｐ．１８６１−１８６９ （４）ＬＳＩハンドブック、電子通信学会編 オーム社

【発明が解決しようとする課題】前述したように、従来
のスリット法においては外角形の辺を用い、各スリット
ごとに、そのｘ座標ですべての辺を分割しながら分割辺
の集合を作成し、その中から異なる向きの辺の組を抽出
して論理演算を行なっている。このため、各スリット内
では交点をもつ辺が存在しないことが論理演算を行なう
上で必要であり、入力データに斜め辺がひとつでも含ま
れていると、スリット内で交点をもつ可能性があるた
め、各スリット上の端点以外には交点のない辺にする前
処理が必要になり処理煩雑になる。またすべての分割辺
を主メモリ上に持つことになり、各分割辺を与える情報
量により大きなメモリ容量を必要とするという欠点があ
る。

【０００４】

【課題を解決するための手段】本発明のレイアウトデー
タの論理演算方式は、予め作成された図形データとして
データベース上に格納されているレイアウトデータを読
出して、マスク工程（以下、マスク層と云う）ごとに分
類し、同一マスク層に属するレイアウトデータに含まれ
る全ての頂点を抽出する第１のステップと、前記第１の
ステップにおいて抽出された頂点に一連の番号を振り当
て、また２つの頂点の連結により定義される辺に対して
も、前記番号とは別に一連の番号を振り当てて、所定の
メモリに格納する第２のステップと、前記第１のステッ
プにおいて抽出して番号を振り当てた頂点をｘ軸方向に
ソートし、各頂点の番号（以下、点番号と云う）と順位
とを所定のメモリ領域に格納する第３のステップと、前
記第３のステップにおいて格納されたそれぞれの順位に
対応する座標値でｙ軸に平行な直線である境界を想定
し、当該順位の低い方（ｘ座標の小さい方）より順番
に、対応する境界を１つづつ選び出す第４のステップ
と、前記第４のステップにおいて選択された境界上に存
在する頂点の点番号及び境界と交わる辺の番号（以下、
辺番号と云う）を全て抽出して、所定のメモリ領域に格
納する第５のステップと、前記第５のステップにおいて
抽出された頂点及び辺をｙ軸方向にソートし、各頂点の
点番号または各辺の辺番号ならびに順位を所定のメモリ
領域に格納する第６のステップと、前記第６のステップ
の処理終了後に、隣接する２つの境界でデータを格納し
たか否かを調べる第７のステップと、前記第６のステッ
プにおいて、隣接する２つの境界でデータを格納してい
る場合に、１つのスリットの両境界での頂点及び辺の番
号、ならびに順位のデータを比較照合することによっ
て、レイアウトデータの論理演算を行う第８のステップ
と、前記第８のステップの処理終了後に、前記第４のス
テップから第８のステップまでの処理について、前記第
３のステップにおいて想定された全ての境界が選択され
たか否かを調べる第９のステップとを有し、前記第７の
ステップにおいて隣接する２つの境界でデータを格納し
ていない場合、ならびに第９のステップにおいて全ての
境界を選択していない場合に、第４のステップに戻るこ
とを特徴としている。

【０００５】

【実施例】次に、本発明について図面を参照して説明す
る。

【０００６】図１は、本発明の一実施例の処理手順を示
すフローチャートである。また、図２（ａ），（ｂ）お
よび（ｃ）は、異なるレイアウトデータに対して、本発
明を実施した場合のレイアウトデータの変換図であり、
それぞれ入力パターン、ＡＮＤ演算後のパターンを示し
ている。そして、図３（ａ），（ｂ）および（ｃ）も、
同様に異なるレイアウトデータに対して、本発明の実施
した場合のレイアウトデータの変換図であり、それぞれ
入力パターン、ＡＮＤ演算後のパターンおよびＯＲ演算
後のパターンを示しているが、この場合は、中央に重な
りを持つ２つの矩形パターンが斜めに配置されている例
である。なお、図２（ａ），（ｂ）および（ｃ）におい
て、１３〜１５はスリットを示し、２０，２２，２４お
よび２６は矩形Ａの頂点、２１，２３，２５および２７
は矩形Ａの辺を示しており、３０，３３，３５および３
７は矩形Ｂの辺を示している。同様に、図３（ａ），
（ｂ），および（ｃ）においては、４０，４２，４４お
よび４６は矩形Ｃの頂点、４１，４３，４５および４７
は矩形Ｃの辺を示しており、５０，５２，５４，および
５６は矩形Ｄの頂点、５１，５３，５５および５７は矩
形の辺を示している。さらに、図４は、本実施例におけ
る頂点データ格納用メモリブロックの概念図である。

【０００７】図１において、図形データベース９０より
レイアウト設計後のレイアウトデータが読出され、マス
ク層（マスク作成工程ごとにレイアウトデータを分類し
たもの）ごとに分類され、同一のマスク層に属するレイ
アウトデータに含まれる、すべての頂点が抽出される
（ステップ１０１）。前記ステップ１０１で抽出した頂
点に一連の番号を振り当て、また２つの頂点で決まる辺
にも番号を振り当てて、所定のメモリ領域に格納する
（ステップ１０２）。次にスリットの境界を決めるた
め、メモリに格納したすべての頂点をｘ軸方向にソート
し、頂点の番号（以後、点番号とする）ならびに順位を
所定のメモリ領域に格納する（ステップ１０３）。前記
ステップ１０３で格納して各々の順位のうち、低い方
（ｘ座標の小さい方）から順に、対応する境界をひとつ
づつ選び出す（ステップ１０４）。前記ステップ１０４
で選んだ境界、つまりｙ軸に平行な直線上に、存在する
頂点の点番号、及び境界と交わる辺の番号（以後、辺番
号とする）をすべて抽出して、所定のメモリ領域に格納
する（ステップ１０５）。前記ステップ１０５で抽出し
た頂点及び辺をｙ軸方向にソートし、点番号または辺番
号ならびに順位を所定のメモリ領域に格納する（ステッ
プ１０６）。前記ステップ１０６の処理が終わると、隣
接した２つの境界でデータを格納したかを調べる（ステ
ップ１０７）。ステップ１０７において格納されていな
い場合は、次の境界を選ぶためステップ１０４に処理を
戻す。また、格納されている場合は、ひとつのスリット
の両境界での頂点及び辺の位置関係がわかっているの
で、このスリットの論理演算を行なう（ステップ１０
８）。そして、最後に、すべての境界選択したかどうか
を調べ（ステップ１０９）、選択していなければ、次の
境界を選べためステップ１０４に処理を戻し、選択して
いれば、処理を終了する。

【０００８】図２（ａ）は、一部分の重なった２つの矩
形パターンの例であり、入力パターンを示している。こ
れを入力パターンとして、図１のフローチャートに合わ
せて処理を行なう。スリット１４の境界２において、図
１におけるステップ１０１からステップ１０６までを介
して、頂点及び辺が、上から頂点３０、辺２１、頂点３
６及び辺２５の順にならび格納されている。また、ステ
ップ１０４に戻り、再びステップ１０６の処理により、
境界３において、頂点及び辺が辺３１、頂点２２、辺３
５及び頂点２４の順にならび格納されている。次いで、
ステップ１０８にて、スリット１４の両境界である境界
２及び境界３のデータを比較照合し、スリット１４のパ
ターンの論理演算を行なう。

【０００９】まず、境界２でのならびから、辺２１と辺
３７（頂点３０及び頂点３６の連結）が交点６０を持つ
こと、矩形Ａ及び矩形Ｂは交点６０から頂点３６までの
範囲で重なりを持つことがわかる。辺２１と辺３７、及
び境界２のｘ座標より交点の座標を計算し、所定のメモ
リに格納する。また辺２１および辺３７につながる頂点
との連結を更新し、辺２１及び辺３７の辺番号を変更す
る。

【００１０】次に、境界３では、辺２３（頂点２２及び
頂点２４の連結）と辺３５が交点６１（図２（Ｃ）参
照）を持つこと、矩形Ａ及び矩形Ｂは頂点２２から交点
６１までの範囲で重なりを持つことがわかる。同様に交
点の座標を計算し、関係する頂点との連結を更新し、辺
番号を変更する。

【００１１】こうして、ステップ１０４よりステップ１
０９にいたる処理を繰り返し、スリット１３、１４及び
１５の境界１、２、３及び４での、頂点及び辺のならび
を比較照合した図２（ａ）の論理演算終了後の出力パタ
ーンが、図２（ｂ）及び図２（ｃ）である。図２（ｂ）
は矩形Ａ及び矩形Ｂの重なり合った部分を抽出する演算
（ＡＮＤ処理）後のパターンを、また図２（ｃ）は矩形
Ａ及び矩形Ｂの外形を抽出する演算（ＯＲ処理）後のパ
ターンを、それぞれ示している。

【００１２】次に、図３（ａ）は、中央に重なりを持つ
２つ矩形のパターンが斜めに配置された例である。ステ
ップ１０１からステップ１０６までを介して、スリット
１６の境界８において、頂点及び辺が、頂点４２、辺４
７、辺５１及び辺５７の順にならび格納されている。一
方、ステップ１０４に戻り、ステップ１０６の処理によ
り、境界９においては、頂点及び辺が、辺５１、辺５
５、辺４３及び頂点４６の順にならび格納されている。
次いで、ステップ１０８にて、ステップ１６の両境界で
ある境界８及び境界９のデータを比較照合し、スリット
１６のパターンの論理演算を行なう。

【００１３】例えば、境界８において前から３番目にな
らんでいた辺５１が、境界９においては先頭になってい
る。また、境界８において辺５１より前にならんでいた
頂点４２（境界９においては辺４３）及び辺４７が、境
界９においては辺５１の後になっている。これから、辺
５１は辺４３及び辺４７と、それぞれ交点７０及び交点
７１を持つことがわかる。同様に考え、辺５５は辺４３
及び４７と、それぞれ交点７２及び交点７３を持つ。こ
れら交点７０、７１、７２及び７３の座標を、それぞれ
が関係する辺より算出し、おのおのの交点につながって
いる辺番号を更新後、所定のメモリに格納する。こうし
て、ステップ１０４よりステップ１０９にいたる処理を
繰り返し、境界５〜境界１２での頂点及び辺のならびを
比較照合後、矩形Ｃまたは矩形Ｄの各頂点及び交点を順
にたどることで、論理演算後の出力パターンを得ること
ができる。

【００１４】図３（ａ）の論理演算後の出力パターン
を、図３（ｂ）及び図３（ｃ）に示す。また、図４は頂
点データ格納用メモリブロックの概念図である。このメ
モリブロックは、読出したレイアウトデータに含まれる
頂点の格納用ブロック８４と、論理演算により見つかっ
た交点格納用ブロック８５の２つのブロックに大別され
る。構造は、頂点及び交点の属するレイアウトデータ番
号格納部８０、頂点及び交点の点番号格納部８１、座標
値格納部８２及び連結ポインタ格納部８３の４つの格納
部より成る。この点番号格納部８１は省略することもで
きる。点番号格納部８１は、頂点番号格納部８１−１及
び交点番号格納部８１−２より成る。座標値格納部８２
は、ｘ座標格納部８２−１及びｙ座標格納部８２−２よ
り成る。また、連結ポインタ格納部８３は、そと頂点及
び交点を終点とする辺の始点の点番号を各納する前端点
連結ポインタ格納部８３−１、その頂点及び交点を始点
とする辺の終点の点番号を格納する後端点連結ポインタ
格納部８３−２、及び補助用連結ポインタ格納部８３−
３より成る。このメモリブロック上では、辺は２つの端
点の点番号の連結として連結ポインタ格納部８３に格納
される。辺の削除及び新たな交点が発生した場合の辺の
追加及び更新は、連結ポインタ格納部８３に格納されて
いる点番号を書き替えることで実行される。

【００１５】上記実施例では、スリットの境界を決める
ためメモリに格納したすべての頂点をｘ軸方向にソート
した後、頂点番号ならびに順位のデータを所定のメモリ
領域に格納し、順位の低いほうから順に対応する境界を
選び出し、選んだ境界、つまりｙ軸に平行な直線上に、
存在する頂点番号及び境界と交わる辺番号をすべて抽出
して、所定のメモリ領域に格納したのち論理演算を行な
うフローを用いているが、図５に示すように、スリット
の境界を決めるためメモリに格納したすべての頂点をｙ
軸方向にソートした後、頂点番号ならびに順位のデータ
を所定のメモリ領域に格納し、順位の低いほうから順に
対応する境界を選び出し、選んだ境界、つまりｘ軸に平
行な直線上に、存在する頂点番号及び境界と交わる辺番
号をすべて抽出して、所定のメモリに格納したのち論理
演算を行なった場合においても、同様の出力パターンを
得ることができる。

【００１６】

【発明の効果】以上説明したように、本発明はひとつの
スリットを定義する境界線上に存在する頂点及び辺を、
点で表される集合としてその位置関係を損なわないよう
に格納し、レイアウトデータの論理演算を行なっている
ので、斜め辺が存在すると端点以外に交点を持たないよ
うにする前処理を必要としない。また本発明を実施する
には、頂点または交点の座標値及び頂点の連結情報だけ
でよく、従来のスリット法のように、大容量のメモリを
必要としないという効果があり、さらに頂点及び辺のな
らびを調べるだけで、交点の検出及びパターンの重なり
の認識を行なえるので、高速で効率良い論理演算を行な
えるという効果がある。

【図面の簡単な説明】

【図１】本発明の一実施例のフローチャートを示す図で
ある。

【図２】本発明の一実施例によるレイアウトデータの変
換図である。

【図３】本発明の一実施例による、ｙ軸に平行な境界を
用いたレイアウトデータの変換図である。

【図４】本発明の一実施例の頂点データ格納用メモリの
概念図である。

【図５】本発明の一実施例による、ｘ軸に平行な境界を
用いたレイアウトデータの変換図である。

【図６】従来の技術を説明する概念図である。

【図７】従来の技術を説明する概念図である。

【符号の説明】

１〜４、５〜１２ 境界 １３〜１５、１６ スリット ２０、２２、２４、２６ 矩形Ａの頂点 ２１、２３、２５、２７ 矩形Ａの辺 ３０、３２、３４、３６ 矩形Ｂの頂点 ３１、３３、３５、３７ 矩形Ｂの辺 ４０、４２、４４、４６ 矩形Ｃの頂点 ４１、４３、４５、４７ 矩形Ｃの辺 ５０、５２、５４、５６ 矩形Ｄの頂点 ５１、５３、５５、５７ 矩形Ｄの辺 ６０、６１ 矩形Ａと矩形Ｂとの交点 ７０〜７３ 矩形Ｃと矩形Ｄとの交点 ８０ レイアウトデータ番号格納部 ８１ 点番号格納部 ８１−１ 頂点番号格納部 ８１−２ 交点番号格納部 ８２ 座標値格納部 ８２−１ ｘ座標格納部 ８２−２ ｙ座標格納部 ８３ 連結ポインタ格納部 ８３−１ 前端点ポインタ格納部 ８３−２ 後端点ポインタ格納部 ８３−３ 補助連結ポインタ格納部 ８４ 頂点格納用メモリブロック ８５ 交点格納用メモリブロック ９０ 図形データベース １０１ 図形データベース９０からレイアウトデータ
を読出し、マスク層ごとに分類し、含まれる頂点の抽
出″行なうステップ １０２ 頂点及び辺に一連の番号を振り当て、所定の
メモリ領域への格納を行なうステップ １０３ 番号を振り当てた頂点をｘ軸方向にソート
し、各頂点の番号と順位を所定のメモリ領域に格納する
ステップ １０４ 各々の順位に対応する頂点の座標値で、ｙ軸
に平行な直線である境界を想定し、そのひとつを順に選
びだすステップ １０５ 境界上に存在する、番号を振り当てた頂点及
び辺をすべて取り出して所定のメモリ領域に格納するス
テップ １０６ 格納した頂点及び辺をｙ軸方向にソートし、
各頂点及び辺の番号ならびに順位を所定のメモリ領域に
格納するステップ １０７ 頂点及び辺の番号ならびに順位のデータを、
境界が隣接する２つの位置で、用意できたか判断するス
テップ １０８ 頂点及び辺の番号ならびに順位のデータを比
較照合することによって、レイアウトデータの論理演算
を行なうステップ １０９ すべての境界が選ばれるまで処理を繰り返す
ステップ ２００ レイアウトデータＰ₁ ２０１ レイアウトデータＰ₁ の外接方形 ２０２ スリット ２０３ 分割辺 ２０４ レイアウトデータの頂点座標で分割された一
つの格子 ２０５ パターン実体を持つ格子 ２０６ パターン実体を持たない格子

Claims (1)

【特許請求の範囲】
1. 【請求項１】 予め作成された図形データとしてデータ
   ベース上に格納されているレウアウトデータを読出し
   て、マスク工程（以下、マスク層と云う）ごとに分類
   し、同一マスク層に属するレウイウトデータに含まれる
   全ての頂点を抽出する第１のステップと、 前記第１のステップにおいて抽出された頂点に一連の番
   号を振り当て、また２つの頂点の連結により定義される
   辺に対しても、前記番号とは別に一連の番号を振り当て
   て、所定のメモリに格納する第２のステップと、 前記第１のステップにおいて抽出して番号を振り当てた
   頂点をｘ軸方向にソートし、各頂点の番号（以下、点番
   号と云う）と順位とを所定のメモリ領域に格納する第３
   のステップと、 前記第３のステップにおいて格納されたそれぞれの順位
   に対応する座標値でｙ軸に平行な直線である境界を想定
   し、当該順位の低い方（ｘ座標の小さい方）より順番
   に、対応する境界を１つづつ選び出す第４のステップ
   と、 前記第４のステップにおいて選択された境界上に存在す
   る頂点の点番号及び境界と交わる辺の番号（以下、辺番
   号と云う）を全て抽出して、所定のメモリ領域に格納す
   る第５のステップと、 前記第５のステップにおいて抽出された頂点及び辺をｙ
   軸方向にソートし、各頂点の点番号または各辺の辺番号
   ならびに順位を所定のメモリ領域に格納する第６のステ
   ップと、 前記第６のステップの処理終了後に、隣接する２つの境
   界でデータを格納したか否かを調べる第７のステップ
   と、 前記第６のステップにおいて、隣接する２つの境界でデ
   ータを格納している場合に、１つのスリットの両境界で
   の頂点及び辺の番号、ならびに順位のデータを比較照合
   することによって、レイアウトデータの論理演算を行う
   第８のステップと、 前記第８のステップの処理終了後に、前記第４のステッ
   プから第８のステップまでの処理について、前記第３の
   ステップにおいて想定された全ての境界が選択されたか
   否かを調べる第９のステップと、 を有し、前記第７のステップにおいて隣接する２つの境
   界でデータを格納していない場合、ならびに第９のステ
   ップにおいて全ての境界を選択していない場合に、第４
   のステップに戻ることを特徴とするレイアウトデータの
   論理演算方式。