JPH0887531A - レイアウト検証装置 - Google Patents

Abstract

(57)【要約】 【目的】 座標点間の最短距離の検証を正確かつ能率的
に行えるレイアウト検証装置を得る。 【構成】 レイアウトデータ１の領域を格子状に分割
し、各格子領域に存在するデータを格子分割データ６と
して格納する格子分割部５、各格子領域内で検証対象の
座標点対（基準点およびそれに対する対象点）を抽出
し、基準点から対象点までの距離を算出して、最小の距
離をもつ対象点を最短点とし、その最小距離が基準点か
ら境界までの距離より大きい場合に、隣接する格子領域
を検証範囲に加える検証範囲設定部８、および検証範囲
設定部８で設定された検証対象領域において抽出された
基準点と最短点との距離を検証する最短点検証部９を備
えている。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】この発明は、ＬＳＩのレイアウト
設計工程においてレイアウトデータの検証を行うレイア
ウト検証装置に関し、特に、レイアウトデータ領域内で
重ね合わされた図形データを接続する接続点等の座標点
間の距離を検証するものである。

【０００２】

【従来の技術】従来から、データ量が膨大なレイアウト
データを扱う場合、処理の高速化を目的として、データ
領域を格子状に分割し、検証を行う範囲を狭くする方法
が行われている。図１５は、従来のレイアウト検証装置
を示すブロック図であり、１はレイアウトデータ、２は
レイアウトデータ１および後述する包含関係検証部７で
抽出されたデータの包含関係を入力して設計基準や回路
構成を検証するレイアウト検証部で、検証結果はリポー
トファイル３およびＣＲＴなどの表示部４に出力され
る。５はレイアウトデータ領域を格子状（２次元配列）
に分割し、検証すべきデータ（図形データおよびそれに
包含される座標点データ）がどの格子領域に存在するか
を調べて格子分割データ６として格納する格子分割部、
７は各格子領域における図形データと座標点データの包
含関係を抽出する包含関係検証部である。

【０００３】次に、動作について図１６のフローチャー
トを参照しながら説明する。まず、検証対象のデータ領
域を格子状に分割する（Ｓ１）。次に、分割された格子
領域毎に図形データと座標点データとの包含関係を抽出
して格子分割データとして格納する（Ｓ２）。図１７
は、検証対象のデータ領域に存在する図形データおよび
それに包含される座標点データの例を示す図であり、例
えば、図形ａには座標点アおよび座標点イが包含されて
いる。図１８は、図１７で示したデータ領域を格子状に
分割した例を示しており、斜線部は座標点が存在する格
子である。それぞれの格子領域のデータは図１９に示す
ような格子分割データとして格納される。これは、各格
子領域に存在する図形データおよび座標点データを調
べ、各格子領域を２次元配列とみなして各配列に各デー
タを格納したものである。例えば配列（３，１）には図
形ｃが存在するが座標点は存在しないので（３，１）＝
ｃとなる。また配列（４，２）には、図形ｃおよび図形
ｄが存在し、かつ図形ｃに包含される座標点オが存在す
るので、（４，２）＝（ｃ，ｄ，オ）となる。

【０００４】次に、例えば左上の格子領域を検証対象と
して（Ｓ３）、その領域内に存在するデータを上記Ｓ２
において格納した格子分割データから検索する（Ｓ
４）。該当するデータがあれば（Ｓ５でＹＥＳのと
き）、その領域内の図形データと座標点データとを抽出
し（Ｓ６）、それらの包含関係に対する検証処理を行う
（Ｓ７）。次に、例えば隣の格子領域を次の検証対象と
して（Ｓ８）、未検証の格子領域があれば（Ｓ９でＹＥ
Ｓのとき）、Ｓ４にもどって上記の処理を繰り返す。上
記Ｓ５で該当するデータがない場合は（Ｓ５でＮＯのと
き）、Ｓ８に進み、次の検証対象に対する処理を行う。
以上の処理を繰り返し、すべての格子領域に対して検証
を行ったならば（Ｓ９でＮＯのとき）、処理を終了す
る。以上により、図形データと座標点データとの包含関
係の検証処理は、斜線部分の格子領域ごとに個別に行わ
れる。

【０００５】

【発明が解決しようとする課題】上記のような従来のレ
イアウト検証装置においては、データ領域を格子状に分
割して図形データと座標点データとの包含関係を検証す
ることを目的としている。ところで、レイアウト設計に
おいては座標点間の距離を一定以上に保つ必要がある。
そこで、その座標点間距離が所定の値以上であるか否か
を検証する目的で、従来装置の格子分割方式を採用した
場合には、ある基準となる座標点（基準点）とその基準
点との距離が最小である他の座標点（最短点）とを分割
した格子領域ごとに抽出するので、１つの基準点に対す
る実際の最短点が同一格子領域ではなく隣接する格子領
域内にある場合に、真の最短点を抽出することができな
いといった問題点があった。また、データの分布密度に
合ったレイアウトデータ領域の分割数が不明なので、分
割の仕方によって処理時間がかかってしまう等の問題点
があった。

【０００６】この発明は、上述のような課題を解決する
ためになされたもので、第１の目的は、基準点に対して
正確に最短点を抽出し、高性能の座標点間距離の検証が
行えるレイアウト検証装置を得るものである。また、第
２の目的は、高速に処理できるレイアウト検証装置を得
るものである。

【０００７】

【課題を解決するための手段】この発明に係るレイアウ
ト検証装置においては、レイアウトデータの領域を検証
単位としての格子に分割する手段、分割されたそれぞれ
の検証単位を検証対象領域として基準点およびこの基準
点に対する対象点を抽出し、それら座標点間距離を算出
する手段、算出された座標点間距離のうち最小の距離を
もつ対象点を該基準点に対する最短点とする手段、上記
基準点からこの基準点が存在する検証単位の境界（格子
の４辺および４頂点）までの距離を算出する手段、上記
基準点とこの基準点に対する最短点との距離（最短距
離）を上記基準点から境界までの距離と比較する手段、
および、上記比較の結果、上記境界までの距離が上記最
短距離未満であれば、その境界の方向に隣接する検証単
位を上記検証対象領域に加えてできる領域を新たな検証
対象領域とする手段を備えたものである。

【０００８】また、基準点に対して、この基準点が含ま
れる検証単位内に対象点が存在しない場合、上記検証単
位に隣接するすべての検証単位を検証対象領域に加える
ようにしたものである。

【０００９】また、座標点の分布密度（単位面積あたり
の座標点のデータ数）に対して処理速度の高速化に最適
な格子１辺のサイズをモデルデータとして保持する手
段、検証対象のレイアウトデータ領域全体に存在する座
標点の分布密度を算出する手段、算出された分布密度に
合った最適な格子１辺のサイズを上記モデルデータから
抽出する手段、および求められた格子の１辺のサイズを
もとに上記レイアウトデータ領域を分割する手段を備え
たものである。

【００１０】また、任意にサンプリングした複数の検証
単位のそれぞれに存在する座標点の数を求める手段、求
められた座標点の数の平均値を算出する手段、算出され
た平均値と予め定められた規定値とを比較する手段、お
よび比較の結果、平均値が規定値未満になるまでデータ
領域の分割数を増やす手段を備えたものである。

【００１１】

【作用】上記のように構成されたレイアウト検証装置に
おいては、検証対象領域である検証単位内において、あ
る基準点とその基準点に対する対象点との距離の最小値
（最短距離）が、該基準点からその検証単位の境界まで
の距離よりも大きい場合に、該境界の方向に隣接する検
証単位が検証対象領域に加えられる。

【００１２】また、ある基準点に対して、この基準点が
含まれる検証単位内に対象点が存在しない場合、上記検
証単位に隣接するすべての検証単位が検証対象領域に加
えられる。

【００１３】また、算出された座標点の分布密度（単位
面積あたりの座標点のデータ数）に対して、処理速度の
高速化に最適な格子１辺のサイズがモデルデータをもと
に抽出され、格子の１辺がそのサイズになるようにレイ
アウトデータ領域が分割される。

【００１４】また、任意にサンプリングした複数の検証
単位に存在する座標点数の平均値が予め定められた規定
値未満になるまでデータ領域の分割数が増やされる。

【００１５】

【実施例】

実施例１．図１はこの発明の一実施例によるレイアウト
検証装置を示すブロック図で、１〜６は図１５に示した
従来装置のものと同一または相当部分である。８は格子
分割データ６から検索したデータをもとに検証対象領域
を設定する検証範囲設定部、９は検証範囲設定部８で設
定された検証対象領域において、ある基準点とそれに対
する最短点との距離が所定の距離以上をたもっているか
否かの検証を行う最短点検証部である。

【００１６】次に、動作について図２のフローチャート
を参照しながら説明する。図３はデータ領域の例であ
り、以降、図中の×印は基準点、・印は対象点を表す。
これら座標点は、データ領域内で重ね合わされた図形デ
ータの接続点等である。まず、従来と同様にデータ領域
を格子状に分割して各格子領域に該当するレイアウトデ
ータ（格子分割データ）を格納し、検証対象の格子領域
を設定して検証を始める（Ｓ１〜Ｓ３）。図４は図３の
データ領域を格子分割した図であり、１つの格子領域内
に基準点のみ存在する場合、基準点および対象点が存在
する場合、対象点のみ存在する場合、およびどちらも存
在しない場合がある。最初に、１つの格子領域を検証範
囲として（Ｔ１）、その検証範囲内で基準点を検索する
（Ｔ２）。基準点が存在すれば（Ｔ３でＹＥＳのと
き）、その検証範囲内に存在する他の座標点を対象点と
して抽出する（Ｔ４）。対象点が存在すれば（Ｔ５でＹ
ＥＳのとき）、基準点とそれぞれの対象点との距離を求
め、距離が最小となる対象点を最短点とする（Ｔ６）。

【００１７】次に、基準点から検証範囲の境界までの距
離を算出する（Ｔ７）。この境界とは、検証範囲である
４つの辺および４つの頂点のことである。そして、算出
された各距離と、Ｔ６で求めた最短点までの距離とを比
較する（Ｔ８）。算出されたすべての距離が最短点の距
離よりも大きい時、つまり、最短点までの距離が最短の
距離である時（Ｔ９でＹＥＳのと）、検証範囲内の最短
点を該基準点に対する最短点と決定して、距離の検証を
行う（Ｔ１０）。続いて、次の格子領域を検証範囲とし
て（Ｔ１１）、格子領域が存在すれば（Ｔ１２でＹＥＳ
のとき）Ｔ４にもどって処理を続ける。すべての格子領
域について検証を行った場合は（Ｔ１２でＮＯのとき）
処理を終了する。

【００１８】Ｔ９で算出された距離の中で最短点までの
距離よりも小さいものがある時（Ｔ９でＮＯのとき）、
その境界の方向の格子領域を検証範囲に加えて（Ｔ１
３）、新しい検証範囲でＴ２にもどって処理を続ける。
図５は、１つの基準点から格子領域内の最短点までの距
離ａが、境界（左辺）までの距離ｂより大きい場合を示
した図で、左方向の格子領域を検証範囲に加えている。
その格子領域内の座標点を対象点として抽出し、基準点
からその対象点までの距離ｃが距離ａよりも小さけれ
ば、その対象点が最短点となる。また図６は、基準点か
ら上方向、左方向、および左上方向のそれぞれの境界ま
での距離が、最短点までの距離よりも小さい場合を示し
た図で、その場合は上記３方向に隣接する格子領域を検
証範囲に加えている。その３つの格子領域内に存在する
すべての座標点を対象点として抽出し、基準点からの距
離が最も小さいものを最短点とする。

【００１９】上記Ｔ３で基準点が存在しない場合は（Ｔ
３でＮＯのとき）、Ｔ１１に進んで次の格子領域を検証
対象とする。上記Ｔ５で対象点が存在しない場合は（Ｔ
５でＮＯのとき）、検証範囲の周辺に隣接する格子領域
を検索範囲に加える（Ｔ１４）。図７は基準点のみ存在
し、対象点が存在しない格子領域の場合を示した図で、
その格子領域に隣接する格子領域を検証範囲に加え、加
えられた格子領域内の座標点を該基準点に対する対象点
として抽出する。ただし、検証範囲である格子領域の位
置によって隣接する格子領域が異なる。図８（ａ）〜図
８（ｃ）は隣接する格子領域を検証範囲に加える方法を
示したものである。図８（ａ）は、基準点が存在する検
証範囲のすべての境界方向に格子領域が存在する場合
で、４つの辺および４つの頂点の合計８方向に隣接する
格子領域（斜線部）が加えられている。また図８（ｂ）
は、基準点が存在する検証範囲がデータ領域の角の部分
に存在する場合で、２つの辺および１つの頂点の合計３
方向に隣接する格子領域が加えられる。また図８（ｃ）
は、基準点が存在する検証範囲がデータ領域の端の線上
に存在する場合で、３つの辺および２つの頂点の合計５
方向に隣接する格子領域が加えられる。その後、新しく
設定された検証範囲でＴ２にもどり、処理を続ける。以
上のように、データ領域を格子状に分割して高速処理を
行うとともに、座標点データの存在する位置によって隣
接する格子領域を検証範囲を加えることによって実際の
座標点位置に合った正確な検証が行える。

【００２０】実施例２．なお、実施例１においてはデー
タ領域を格子状に分割する場合の分割数について特定は
しなかったが、一般に、図９に示すように、分割数を多
くして検証範囲を狭くすると対象点の数が減少し、処理
速度が速くなるが、検証範囲を狭めすぎると、対象点が
検証範囲内に存在する確率が減ったり、検証範囲内の最
短点の信頼性が低下する、すなわち、当初設定した検証
範囲内で抽出した最短点が真の最短点とは異なる可能性
が高くなるため、検証範囲を拡大しなければならず、逆
に処理速度が遅くなるといった現象が起きる。本実施例
２では、処理速度を速くするのに最適な分割数を求める
方法について述べる。図１０はこの発明の実施例２によ
るレイアウト検証装置を示すブロック図で、１〜９は図
１に示した装置のものと同一または相当部分である。１
０はレイアウト検証部から得たデータの分布状態とモデ
ルデータ１１とから最適な格子分割数を決定する格子分
割数決定部である。格子分割部５は決定された分割数と
なるようにデータ領域を分割する。

【００２１】次に、動作について図１１のフローチャー
トを参照しながら説明する。まず、レイアウトデータよ
りデータ領域を得て（Ｕ１）、その中に含まれるデータ
数を得る（Ｕ２）。次に、データ領域の面積とデータ数
より、データの分布密度を求める（Ｕ３）。例えば、た
て２００×よこ３００のデータ領域内に２５４個のデー
タが存在する場合は、分布密度＝２５４／（２００×３
００）＝０．００４２・・・となる。次に、分布密度と
モデルデータとを比較し、モデルデータをもとに最適格
子数を求める（Ｕ４）。モデルデータは、まず、例え
ば、たて１００×よこ１００の領域の中に５０のデータ
が存在する格子（分布密度０．００５）に対して、格子
１辺のサイズを変化させて処理速度を検証し、最適なサ
イズを抽出する。次に、分布密度を変化させて同様に最
適な格子１辺のサイズを抽出する。このようにして得ら
れたモデルデータの例を図１２に示す。先程の例では、
分布密度＝０．００４２であったのでモデルデータより
格子１辺のサイズ＝１００と決定される。これにより、
格子数＝（２００×３００）／１００＝２×３＝６が求
められる。以上により、処理速度を高速にするのに最適
な格子数でデータ領域を分割し、高速にレイアウト検証
が行える。

【００２２】実施例３．なお、上記実施例２では、処理
速度を高速にするのに最適な格子分割数をモデルデータ
を用いて決定する例を示したが、１つの格子領域内のデ
ータ数が予め定められた規定値未満になるまで分割を行
い、該規定値未満になった時点での分割数を最適な格子
分割数として決定するようにしても、同様に処理の高速
化を実現できる。図１３は、本実施例３によるレイアウ
ト検証装置を示すブロック図である。図において、１〜
１０は実施例１および２で示したものと同一または相当
部分である。１２は格子分割データ６から無作為に複数
の格子領域を選択するサンプリングデータ抽出部であ
り、格子分割数決定部１０はサンプリングデータ抽出部
１２で抽出された格子領域内に存在するデータ数の平均
値がある規定値未満になるまで格子分割数を増やし、該
規定値未満になった時点の分割数を最適な格子分割数と
する。

【００２３】次に、動作について図１４のフローチャー
トを参照しながら説明する。本実施例３においても、上
記実施例２と同様、処理の高速化に最適な格子分割数を
得る方法についてのみ述べる。まず、従来と同様、デー
タ領域をある分割数をもって格子状に分割し、格子分割
データ６を格納する（Ｓ１〜Ｓ２）。次に、無作為に複
数の格子領域を選定し（Ｖ１）、それら格子領域に存在
するデータ数を格子分割データ６から得る（Ｖ２）。Ｖ
２の処理で得たデータ数の平均値を求め（Ｖ３）、規定
値と比較する（Ｖ４）。平均値が規定値以上であれば
（Ｖ５でＹＥＳのとき）、格子分割数を増やし（Ｖ
６）、その分割数をもってＳ１にもどる。平均値が規定
値未満になれば（Ｖ５でＮＯのとき）、その時点での分
割数を最適な格子分割数として処理を終了する。以上に
より、予めモデルデータを準備および格納する必要がな
く、容易にレイアウト検証処理の高速化を実現できる。

【００２４】

【発明の効果】この発明は、以上説明したように構成さ
れているので、以下に示すような効果を奏する。

【００２５】検証範囲である格子領域における基準点と
その基準点に対する最短点との距離が、該基準点から境
界までの距離より大きい場合は、隣接する格子領域を検
証範囲に加えるので、真の最短点を確実に抽出して、正
確なレイアウト検証が行える。

【００２６】また、検証範囲である格子領域内で基準点
に対する対象点が存在しない場合は、周辺の格子領域を
検証範囲に加えるので、格子分割方式がもたらす検証範
囲の狭小化による弊害が解消される。

【００２７】また、検証処理の高速化に最適な格子分割
数をモデルデータをもとに決定するようにしたので、処
理の高速化が実現できる。

【００２８】また、無作為にサンプリングした複数の格
子領域のデータ数の平均値が規定値未満になるまで分割
数を増やし、規定値未満になった時点での格子分割数を
最適な分割数とするようにしたので、容易に処理の高速
化を実現できる。

【図面の簡単な説明】

【図１】 この発明の実施例１であるレイアウト検証装
置を示すブロック図である。

【図２】 この発明の実施例１によるレイアウト検証装
置の処理の流れを示すフローチャートである。

【図３】 データ領域内のデータの分布例を示す図であ
る。

【図４】 データ領域を格子状に分割した例を示す図で
ある。

【図５】 この発明の実施例１において最短点を求める
方法を説明する図である。

【図６】 この発明の実施例１において、最短点との距
離によって周辺の格子領域を検証範囲に加える例を示す
図である。

【図７】 この発明の実施例１において、対象座標点対
が存在しない場合に周辺の格子領域を検証範囲に加える
例を示す図である。

【図８】 検証範囲の位置によって検証範囲に加える周
辺の格子領域が異なることを示す図である。

【図９】 格子分割数と処理速度の関係を示す図であ
る。

【図１０】 この発明の実施例２であるレイアウト検証
装置を示すブロック図である。

【図１１】 この発明の実施例２による処理の流れを示
すフローチャートである。

【図１２】 この発明の実施例２において用いられるモ
デルデータ例を示す図である。

【図１３】 この発明の実施例３であるレイアウト検証
装置を示すブロック図である。

【図１４】 この発明の実施例３による処理の流れを示
すフローチャートである。

【図１５】 従来のレイアウト検証装置を示すブロック
図である。

【図１６】 従来装置による処理の流れを示すフローチ
ャートである。

【図１７】 図形データおよび座標点データの例を示す
図である。

【図１８】 図形データと座標点データとの包含関係を
示す図である。

【図１９】 格子分割データの構造を示す図である。

【符号の説明】

１ レイアウトデータ、２ レイアウト検証部、５ 格
子分割部、６ 格子分割データ、８ 検証範囲設定部、
９ 最短点検証部、１０ 格子分割数決定部、１１ モ
デルデータ、１２ サンプリングデータ抽出部。

Claims (4)

【特許請求の範囲】
1. 【請求項１】 レイアウトデータ内に含まれる座標点を
   検索し、上記座標点のうちの１点を基準点、およびその
   基準点との距離を検証する他の座標点を上記基準点に対
   する対象点として抽出するレイアウト検証装置におい
   て、 上記レイアウトデータの領域を検証単位としての格子に
   分割する手段、分割されたそれぞれの検証単位を検証対
   象領域として上記基準点および上記対象点を抽出し、そ
   れら座標点間距離を算出する手段、算出された座標点間
   距離のうち最小の距離をもつ対象点を該基準点に対する
   最短点とする手段、上記基準点からこの基準点が存在す
   る検証単位の境界（格子の４辺および４頂点）までの距
   離を算出する手段、上記基準点とこの基準点に対する最
   短点との距離（最短距離）を上記基準点から境界までの
   距離と比較する手段、および、上記比較の結果、上記基
   準点から境界までの距離が上記最短距離未満であれば、
   その境界の方向に隣接する検証単位を上記検証対象領域
   に加えてできる領域を新たな検証対象領域とする手段を
   備え、上記基準点に対する対象点を上記新たな検証対象
   領域から抽出するようにしたことを特徴とするレイアウ
   ト検証装置。
2. 【請求項２】 基準点に対して、この基準点が含まれる
   検証単位内に対象点が存在しない場合、上記検証単位に
   隣接するすべての検証単位を検証対象領域に加えるよう
   にしたことを特徴とする請求項１記載のレイアウト検証
   装置。
3. 【請求項３】 座標点の分布密度（単位面積あたりの座
   標点のデータ数）に対して処理速度の高速化に最適な格
   子１辺のサイズをモデルデータとして保持する手段、検
   証対象のレイアウトデータ領域全体に存在する座標点の
   分布密度を算出する手段、算出された分布密度に合った
   最適な格子１辺のサイズを上記モデルデータから抽出す
   る手段、および求められた格子の１辺のサイズをもとに
   上記レイアウトデータ領域を分割する手段を備えたこと
   を特徴とする請求項１または２に記載のレイアウト検証
   装置。
4. 【請求項４】 任意にサンプリングした複数の検証単位
   のそれぞれに存在する座標点の数を求める手段、求めら
   れた座標点の数の平均値を算出する手段、算出された上
   記平均値と予め定められた規定値とを比較する手段、お
   よび比較の結果、平均値が規定値未満になるまでデータ
   領域の分割数を増やす手段を備えたことを特徴とする請
   求項１または２に記載のレイアウト検証装置。