JPH10283390A

JPH10283390A - データ圧縮方法

Info

Publication number: JPH10283390A
Application number: JP9090396A
Authority: JP
Inventors: Yutaka Sato; 佐藤　　裕
Original assignee: Sony Corp
Current assignee: Sony Corp
Priority date: 1997-04-09
Filing date: 1997-04-09
Publication date: 1998-10-23

Abstract

(57)【要約】【課題】ＬＳＩレイアウトデータのデータサイズを効
率良く削減することにより、データハンドリングの高効
率化、及び、コンピュータのメモリ節約によるスラッシ
ングの回避を含めた処理効率向上を可能とする。【解決手段】所定領域内における図形配置を示すデー
タに対するデータ圧縮方法であって、前記図形の形状毎
にその形状を識別するためのインデックスを与え（Ｓ１
０８、Ｓ１１１、Ｓ１１４）、このインデックスと前記
所定領域内における図形の始点位置座標とを用いて前記
データを表現する（Ｓ１１６）。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、データサイズを削
減するためのデータ圧縮方法に係わり、特にＬＳＩ（La
rge Scale Integrated Circuit）レイアウトデータのデ
ータ圧縮方法に関するものである。

【０００２】

【従来の技術】一般に、ＬＳＩのレイアウト設計工程に
おいては、チップ内の素子や配線の配置を、ストリーム
フォーマット（あるいはＧＤＳIIフォーマット）と呼ば
れる形式のＬＳＩレイアウトデータによって表現するこ
とが多い。ところで、チップ内の素子や配線の配置は、
これを図形形状によって表現した際に、矩形で表現され
る図形が多く、さらに、ほとんどの図形がＸ，Ｙ軸に平
行である、といった特性がある。

【０００３】したがって、従来のＬＳＩレイアウトデー
タでは、これらの図形形状を、各図形形状の頂点の座標
値によって表現するようになっている。例えば、図８に
示す二つの矩形Ｇ、Ｈを表現する場合に、従来のＬＳＩ
レイアウトデータでは、Ｇ）；（０，０）（０，２）（１，２）（１，０）（０，０）Ｈ）；（２，３）（２，５）（３，５）（３，３）（２，３）といった座標列で表現するようになっている。

【０００４】

【発明が解決しようとする課題】しかしながら、上述の
座標列を用いたＬＳＩレイアウトデータでは、ＬＳＩの
高密度化が進んだ場合に、データ処理の効率が低下して
しまうという問題が生じてしまう。つまり、従来のＬＳ
Ｉレイアウトデータでは、ＬＳＩの高密度化に伴って、
そのデータサイズが膨大になり、データの入出力やデー
タ構造体からのデータ検索などのデータハンドリング
に、多くの時間を必要とするようになる。また、現在一
般的となっている仮想メモリ方式を採用したコンピュー
タ（例えば、ＣＡＤ装置等）でデータ処理を行う場合に
は、データサイズ膨大化によってメモリ使用量が実装メ
モリサイズの２倍程度になってしまうと、スラッシング
という現象が発生してしまい、その処理効率が極端に低
下してしまう。

【０００５】そこで、本発明は、データサイズを効率良
く削減することにより、データハンドリングの高効率
化、及び、コンピュータのメモリ節約によるスラッシン
グの回避を含めた処理効率向上を可能とするデータ圧縮
方法を提供することを目的とする。

【０００６】

【課題を解決するための手段】本発明は、上記目的を達
成するために案出されたデータ圧縮方法である。すなわ
ち、本発明のデータ圧縮方法は、所定領域内における図
形配置を示すデータに対するデータ圧縮方法であって、
前記図形の形状毎に該形状を識別するためのインデック
スを与え、このインデックスと、前記所定領域内におけ
る図形の始点位置座標とを用いて、前記データを表現す
ることを特徴とする。

【０００７】上記手順によるデータ圧縮方法によれば、
所定領域内における図形配置を示すデータにおいて、異
なる位置に配置された同一形状の図形があった場合に、
これらの図形に同一のインデックスを与えるとともに、
これらの図形を、そのインデックスと各図形の始点位置
座標を用いて表現する。したがって、例えば各図形を頂
点座標の座標列で表現する場合に比べて、データサイズ
が削減される。

【０００８】また、本発明のデータ圧縮方法は、前記イ
ンデックスを与える際に、このインデックスを与える図
形の形状を、その形状における頂点座標間の変移量を用
いて定義してもよい。

【０００９】これにより、各図形の形状が、頂点座標間
の変移量によって表現されるので、頂点座標の座標列で
表現する場合に比べて、ＸＹ軸に平行な線分のみによる
図形の場合、各頂点毎にＸまたはＹいずれかの値のみで
よくなる。また、変移量であるため、値そのものが小さ
くなり情報量が減るため、データサイズが削減されるよ
うになる。

【００１０】また、本発明のデータ圧縮方法は、前記所
定領域が複数の層からなる場合に、同一形状の図形であ
っても配置される層が異なればそれぞれに異なるインデ
ックスを与えるようにしてもよい。

【００１１】これにより、層の区別も仮想的に図形形状
の情報とすることで配置に関する指示が後述のセルの配
置と同様に取り扱うことができる。

【００１２】また、本発明のデータ圧縮方法は、複数の
図形の集合であるセルの配置を一つの図形形状と見な
し、各セル毎に、かつ、そのローテーション情報（例え
ば、回転角度、鏡像化有無、倍率など）毎にインデック
スを与えてもよい。

【００１３】これにより、例えばＬＳＩレイアウトデー
タにおいて多用されるセル引用であっても、ローテーシ
ョンを含めたセルを一つの図形形状と見なしてインデッ
クスが与えられるので、各セル引用をセル名と各ローテ
ーション情報で表現する場合に比べて、データサイズが
削減される。

【００１４】また、本発明のデータ圧縮方法として、前
記所定領域内で同一形状の図形が一定のパターンで複数
配置される場合には、この一定のパターンにもインデッ
クスを与え、そのインデックスと前記同一形状に与えた
インデックスとを組み合わせて、前記データを表現して
もよい。

【００１５】これにより、一定のパターンで複数配置さ
れる図形があった場合には、これらの図形が、その形状
に対応するインデックスと、一定のパターンに与えられ
たインデックスと、その一定のパターンの始点位置座標
とによって表現できるようになり、より一層データサイ
ズが削減される。

【００１６】

【発明の実施の形態】以下、本発明に係わるデータ圧縮
方法について説明する。ただし、ここでは、ＬＳＩレイ
アウトデータに対するデータ圧縮方法を例に挙げて説明
する。

【００１７】先ず、本実施の形態のデータ圧縮方法の概
要について説明する。このデータ圧縮方法は、チップ内
の素子や配線を示す図形の形状毎に、その形状を識別す
るためのインデックス（以下、INDEX とする）を与え、
その素子や配線の配置を示すＬＳＩレイアウトデータ
を、前記INDEX と、各図形の始点位置座標とを用いて表
現することにより、ＬＳＩレイアウトデータのデータサ
イズの削減を行うようになっている。

【００１８】例えば、図８に示す二つの矩形Ｇ、Ｈを表
現する場合に、このデータ圧縮方法によって圧縮された
ＬＳＩレイアウトデータでは、各矩形の形状が同一であ
るので、これらの矩形を、 INDEX ；１形状タイプ；矩形，Ｗ（width)＝１，Ｈ（height）＝２と定義することで、Ｇ）；INDEX ＝＃１，（０，０）Ｈ）；INDEX ＝＃１，（２，３）といったように表現する。これは、ＬＳＩレイアウトデ
ータの中には、同一形状の図形の出現確率が高いという
経験的事実に着目した結果である。なお、ここでは、矩
形を例に挙げて説明したが、矩形だけではなく任意の多
角形やいわゆるパス図形、あるいはセル引用といったＬ
ＳＩレイアウトデータ中の全ての情報が該当する。

【００１９】次に、本実施の形態のデータ圧縮方法の詳
細について、図面を参照しながら説明する。図１は、本
実施の形態のデータ圧縮方法の手順を示すフローチャー
トであり、図２は、本実施の形態のデータ圧縮方法によ
って圧縮されたＬＳＩレイアウトデータのデータ構成の
概略を示す説明図である。ただし、本実施の形態のデー
タ圧縮方法は、ＬＳＩレイアウトデータを入出力するた
めの入出力インターフェース（Ｉ／Ｆ）、ＣＰＵ（Cent
ral Processing Unit ）等の圧縮処理実行手段、及びＲ
ＡＭ（Random Access Memory）等のワークエリアを備え
るコンピュータにおいて実行されるものとする。

【００２０】ここで、先ず、本実施の形態のデータ圧縮
方法によって圧縮されたＬＳＩレイアウトデータのデー
タ構成について、図２を参照しながら説明する。圧縮後
のＬＳＩレイアウトデータは、シンタックス（構文）の
項に示すように、先頭に位置するヘッダー情報と、この
ヘッダー情報以降、一般にセルと呼ばれる図形の集合に
関する情報で、必要に応じて繰り返されるセル情報とか
ら構成されている。

【００２１】ヘッダー情報は、作成年月日及びバージョ
ンナンバーに関する情報からなるものである。セル情報
は、シンタックス内において、「bigin 」で始まり「en
d 」で終了するものであり、セル名INDEX と、インスタ
ンス（instance）情報とからなるものである。

【００２２】このセル情報のうち、セル名INDEX は、こ
のセル名INDEX とセル名からなるセル名情報に登録され
ているINDEX である。一方、インスタンス情報は、詳細
を後述するオフセット量、形状INDEX 、配列INDEX とい
った、ＬＳＩレイアウトデータ内の図形の形状や配置位
置を特定する情報からなるものである。なお、圧縮前の
ＬＳＩレイアウトデータにプロパティ情報が付加されて
いる場合には、そのプロパティ情報をインスタンス情報
内に保持すればよい。

【００２３】このようなデータ構成のＬＳＩレイアウト
データを得るために、本実施の形態では、図１のフロー
チャートに示すように手順に従って、データ圧縮を行う
ようになっている。先ず、コンピュータの入出力Ｉ／Ｆ
に、圧縮前のＬＳＩレイアウトデータを入力する（ステ
ップ１０１、以下ステップをＳと略す）。そして、入力
したデータがヘッダー情報であれば（Ｓ１０２）、圧縮
処理実行手段は、そのヘッダー情報をワークエリアに登
録しておく（Ｓ１０３）。

【００２４】また、入力したデータがセルの開始または
終了を示す情報であれば（Ｓ１０４）、その情報をワー
クエリアに登録しておく（Ｓ１０５）。また、入力した
データがセル名であれば（Ｓ１０６）、セル名情報を検
索あるいは新規追加登録し（Ｓ１０７）、そのセル名を
示すセル名INDEX を、ワークエリアにインスタンス情報
の一つとして登録しておく（Ｓ１０８）。

【００２５】また、入力したデータが図形またはセル引
用を示すものであれば（Ｓ１０９）、形状情報を検索あ
るいは新規追加登録し（Ｓ１１０）、その図形またはロ
ーテーション情報を含めたセル引用を指し示すオフセッ
ト量と形状INDEX とを、ワークエリアにインスタンス情
報の一つとして登録しておく（Ｓ１１１）。さらに、図
形に配列情報があった場合には（Ｓ１１２）、その配列
情報を検索あるいは新規追加登録し（Ｓ１１３）、その
配列情報を指し示す配列INDEX を、ワークエリアにイン
スタンス情報の一つとして登録しておく（Ｓ１１４）。

【００２６】そして、入出力Ｉ／Ｆに入力したＬＳＩレ
イアウトデータがＥＯＦ（end of file)となるまでこれ
らの処理を繰り返す（Ｓ１１５）。ＥＯＦとなったら、
圧縮処理実行手段は、ワークエリアに登録しておいた各
種情報を、上述したデータ構成に従って再構成し、圧縮
後のＬＳＩレイアウトデータとして入出力Ｉ／Ｆから出
力する（Ｓ１１６）。

【００２７】ここで、上述したデータ圧縮方法を、ＬＳ
Ｉレイアウトデータ内の具体的な図形形状に適用した場
合について、図３を参照しながら説明する。なお、以下
の説明において、ＬＳＩレイアウトデータは、複数の層
（Layer;以下、レイヤーと称す）から構成されているも
のとする。

【００２８】〔矩形の場合〕図３（ａ）に示すような、
レイヤー＝１内に存在する矩形に対して、圧縮処理実行
手段は、その矩形データの左下頂点座標と右上頂点座標
とからＷとＨを抽出し、ワークエリア内の形状情報（図
３（ｂ）参照）に、同じレイヤーで、かつ、同じ形状の
矩形があるか否かを検索する。既に同じ矩形があれば、
その矩形の形状INDEX を取得する。一方、同じ矩形がな
ければ、ワークエリアに必要な情報（レイヤー，Ｗ，
Ｈ）を登録して、新たな形状INDEX を割り当てた後、そ
の形状INDEX を取得する。取得した形状INDEX と左下座
標値とは、ワークエリア内にインスタンス情報として登
録しておく。それを簡単に示したものが図３（ｃ）であ
る。このように、左下座標値、すなわち矩形の始点位置
座票は、オフセット量として登録される。この結果、矩
形がオフセット量と形状INDEX で表現される。

【００２９】〔Ｘ軸に平行な台形（Ｘtrap台形）の場
合〕図３（ｄ）に示すようなＸtrap台形の場合には、Ｘ
軸に平行な２辺のうち、Ｙ座標値が小さいほうの辺Ｗか
らＨ，dx1 ，dx2 を抽出し、ワークエリア内の形状情報
に、同じレイヤーで、かつ、同じ形状のＸtrap台形があ
るか否かを検索する。既に同じＸtrap台形があれば、そ
のＸtrap台形の形状INDEX を取得する。一方、同じＸtr
ap台形がなければ、ワークエリアに必要な情報を登録し
て、新たな形状INDEX を割り当てた後、その形状INDEX
を取得する。取得した形状INDEX とＷの最小座標値と
は、ワークエリア内にインスタンス情報として登録して
おく。Ｗの最小座標値は、オフセット量として登録し、
Ｘtrap台形の始点とする。この結果、Ｘtrap台形がオフ
セット量と形状INDEX で表現される。

【００３０】〔Ｙ軸に平行な台形（Ｙtrap台形）の場
合〕図３（ｅ）に示すようなＹtrap台形の場合には、Ｙ
軸に平行な２辺のうち、Ｘ座標値が小さいほうの辺Ｈか
らＷ，dy1 ，dy2 を抽出し、ワークエリア内の形状情報
に、同じレイヤーで、かつ、同じ形状のＹtrap台形があ
るか否かを検索する。既に同じＹtrap台形があれば、そ
のＹtrap台形の形状INDEX を取得する。一方、同じＹtr
ap台形がなければ、ワークエリアに必要な情報を登録し
て、新たな形状INDEX を割り当てた後、その形状INDEX
を取得する。取得した形状INDEX とＨの最小座標値と
は、ワークエリア内にインスタンス情報として登録して
おく。Ｈの最小座標値は、オフセット量として登録し、
Ｙtrap台形の始点とする。この結果、Ｙtrap台形がオフ
セット量と形状INDEX で表現される。

【００３１】〔辺が全てＸ軸またはＹ軸に平行な多角形
（xytype＝０の多角形) の場合〕図３（ｆ）に示すよう
なxytype＝０の多角形の場合には、頂点座標値のＹ最小
検索、次いでＸ最小検索の結果、該当する頂点を「１」
とし、時計回りに頂点座標をソートする。このような正
規化を行うと、この多角形の形状は、頂点「１」を始点
とし、頂点「２」のＹ座標y2から始まりynで終わる（頂
点数−１）個のＸとＹとの交互の座標列で表現できる。
そのような性質を利用し、レイヤーと座標列を抽出し、
ワークエリア内の形状情報に、同じレイヤーで、かつ、
同じ形状の多角形があるか否かを検索する。既に同じ多
角形があれば、その多角形の形状INDEX を取得する。一
方、同じ多角形がなければ、ワークエリアに必要な情報
を登録して、新たな形状INDEX を割り当てた後、その形
状INDEX を取得する。取得した形状INDEX と頂点「１」
の座標値とは、ワークエリア内にインスタンス情報とし
て登録しておく。頂点「１」の座標値は、オフセット量
として登録し、多角形の始点とする。この結果、辺が全
てＸＹ軸に平行な多角形がオフセット量と形状INDEX で
表現される。

【００３２】〔辺が１つでもＸ軸またはＹ軸に平行でな
い多角形（xytype＝１の多角形) の場合〕図３（ｇ）に
示すようなxytype＝１の多角形の場合には、頂点座標値
のＹ最小検索、次いでＸ最小検索の結果、該当する頂点
を「１」とし、時計回りに頂点座標をソートする。この
ような正規化を行った後、頂点「２」のＸＹ座標x2，y2
から始まる（頂点数−１）個のＸＹ座標列を抽出し、ワ
ークエリア内の形状情報に、同じレイヤーで、かつ、同
じ形状の多角形があるか否かを検索する。既に同じ多角
形があれば、その多角形の形状INDEX を取得する。一
方、同じ多角形がなければ、ワークエリアに必要な情報
を登録し、形状INDEX を取得する。取得した形状INDEX
は、ワークエリア内にインスタンス情報として登録して
おく。この結果、xytype＝１の多角形がオフセット量と
形状INDEX で表現される。

【００３３】〔辺が全てＸ軸またはＹ軸に平行で最初の
辺が水平のパス（xytype＝０のパス) の場合〕図３
（ｈ）に示すようなxytype＝０のパスの場合には、最初
の辺のＸ最小の頂点を「１」とし、その座標値をワーク
エリア内のインスタンス情報に図形の始点（オフセット
量）として登録する。その後、頂点「１」の座標値を
（０，０）にオフセットし、ほかの頂点座標も合わせて
オフセットする。その結果、このパスの形状は、頂点
「２」のＸ座標x2から始まるＸとＹとの交互の座標列で
表現できる。そして、ワークエリア内の形状情報に、同
じレイヤーで、かつ、同じ形状のパスがあるか否かを検
索する。既に同じパスがあれば、そのパスの形状INDEX
を取得する。一方、同じパスがなければ、ワークエリア
に必要な情報を登録し、形状INDEX を取得する。取得し
た形状INDEX と頂点「１」の座標値とは、ワークエリア
内にインスタンス情報として登録しておく。この結果、
xytype＝０のパスがオフセット量と形状INDEX で表現さ
れる。

【００３４】〔辺が全てＸ軸またはＹ軸に平行で最初の
辺が垂直のパス（xytype＝１のパス) の場合〕図３
（ｉ）に示すようなxytype＝１のパスの場合には、最初
の辺のＹ最小の頂点を「１」とし、その座標値をワーク
エリア内のインスタンス情報に図形の始点（オフセット
量）として登録する。その後、頂点「１」の座標値を
（０，０）にオフセットし、ほかの頂点座標も合わせて
オフセットする。その結果、このパスの形状は、頂点
「２」のＹ座標y2から始まるＸとＹとの交互の座標列で
表現できる。そして、ワークエリア内の形状情報に、同
じレイヤーで、かつ、同じ形状のパスがあるか否かを検
索する。既に同じパスがあれば、そのパスの形状INDEX
を取得する。一方、同じパスがなければ、ワークエリア
に必要な情報を登録し、形状INDEX を取得する。取得し
た形状INDEX と頂点「１」の座標値とは、ワークエリア
内にインスタンス情報として登録しておく。この結果、
xytype＝１のパスがオフセット量と形状INDEX で表現さ
れる。

【００３５】〔辺が１つでもＸ軸またはＹ軸に平行でな
いパス（xytype＝２のパス) の場合〕図３（ｊ）に示す
ようなxytype＝２のパスの場合には、最初の辺の最初の
頂点を「１」とし、その座標値をワークエリア内のイン
スタンス情報に図形の始点（オフセット量）として登録
する。その後、頂点「１」の座標値を（０，０）にオフ
セットし、ほかの頂点座標も合わせてオフセットする。
そして、頂点「２」から始まるＸＹ座標列を抽出し、ワ
ークエリア内の形状情報に、同じレイヤー、同じWidth
、かつ、同じ形状のパスがあるか否かを検索する。既
に同じパスがあれば、そのパスの形状INDEX を取得す
る。一方、同じパスがなければ、ワークエリアに必要な
情報を登録し、形状INDEX を取得する。取得した形状IN
DEX と頂点「１」の座標値とは、ワークエリア内にイン
スタンス情報として登録しておく。この結果、xytype＝
２のパスがオフセット量と形状INDEX で表現される。

【００３６】〔セル引用の場合〕図３（ｋ）に示すよう
なセル引用の場合には、最初にセル引用座標値を抽出
し、その座標値をワークエリア内のインスタンス情報に
オフセット量として登録する。次いで、引用セル名、ロ
ーテーション（Reflect ，Angle ，Mag)、配列（Nx，N
y，Dx，Dy）を抽出し、それぞれについて、セル名情
報、ローテーション情報、配列情報を検索し、セル名IN
DEX 、ローテーションINDEX 、配列INDEX を取得する。
そして、ワークエリア内に、セル名INDEX とローテーシ
ョンINDEX との組み合わせで同じものがあるか否かを検
索する。既に同じ情報があればその情報の形状INDEX を
取得し、同じ情報がなければ、ワークエリアに必要な情
報を登録し、形状INDEX を新たに割り当てた後、その形
状INDEX を取得する。取得した形状INDEX と配列INDEX
は、ワークエリア内にインスタンス情報として登録して
おく。この結果、セル引用がオフセット量と形状INDEX
と配列INDEX とで表現される。セル名情報、ローテーシ
ョン情報、配列情報の検索とINDEX 取得は、形状情報と
同様に行われる。

【００３７】以上のように、本実施の形態のデータ圧縮
方法では、ＬＳＩレイアウトデータ内の図形の形状（例
えば矩形、台形、多角形、あるいはパスの形状）を、各
形状における頂点座標間の変移量を用いて定義し、その
結果をインスタンス情報として登録するようになってい
る。また、このデータ圧縮方法では、ＬＳＩレイアウト
データが複数のレイヤーから構成されている場合に、同
一形状の図形であっても配置されるレイヤーが異なれ
ば、それぞれを異なる形状INDEX とするようになってい
る。つまり、層の区別も仮想的に図形形状の情報とする
ことで、配置に関する指示がセルの配置と同様に取り扱
うことができる。さらに、このデータ圧縮方法では、セ
ル引用の場合であっても、セルの配置を一つの図形形状
と見なし、各セル毎に形状INDEX を割り当てるようにな
っている。

【００３８】ここで、上述したデータ圧縮方法によって
データ圧縮を行った後のＬＳＩレイアウトデータの具体
例について説明する。図４は、圧縮後のＬＳＩレイアウ
トデータをダンプした例である。なお、ここでは、説明
を簡単にするために、図形は矩形とセル引用のみとし、
セル引用においては単純なローテーション及び配列とし
た。また、図５は、図４に示したＬＳＩレイアウトデー
タを図示化した例である。

【００３９】図４に示すＬＳＩレイアウトデータのう
ち、インスタンス情報中の（Ａ）は、始点位置がオフセ
ット（３，１０）であり、配列INDEX ＝＃１より１×１
の配列、形状INDEX ＝＃１よりＷ＝１０、Ｈ＝５の矩形
を表現している。これを図示化すると、図５に示す矩形
Ａとなる。図４のインスタンス情報中の（Ｂ）は、始点
位置がオフセット（１５，１０）であり、配列INDEX ＝
＃２より２×２でＸＹとも間隔６の配列、形状INDEX ＝
＃２よりＷ＝５、Ｈ＝５の矩形を表現している。これを
図示化すると、図５に示す矩形Ｂとなる。図４のインス
タンス情報中の（Ｃ）は、始点位置がオフセット（５，
０）であり、配列INDEX ＝＃１より１×１の配列、形状
INDEX ＝＃３より、セル名INDEX＃２（Ｂ）、ローテー
ションINDEX ＃１（Reflect=０，Angle=０，Mag=１．
０）のセルを表現している。これを図示化すると、図５
に示すセル引用Ｃとなる。図４のインスタンス情報中の
（Ｄ）、（Ｅ）、（Ｆ）は、（Ａ）の場合と同様であ
る。

【００４０】次に、上述したデータ圧縮方法の手順に加
えて、繰り返し情報の抽出を行う場合について、図６の
フローチャートを参照しながら説明する。なお、繰り返
し情報とは、セル引用の場合の配列情報と同様に、同一
形状の図形が一定のパターンで複数配置されている場合
に、その配置パターンを定義するための情報である。

【００４１】例えば、オフセット量以外の情報が全て同
一であるインスタンス情報が２つ以上あった場合に、入
出力Ｉ／Ｆに入力されたＬＳＩレイアウトデータがＥＯ
Ｆとなったら（Ｓ２１５）、続いて、圧縮処理実行手段
は、繰り返し情報の抽出を行う（Ｓ２１６）。繰り返し
情報は、Ｘ方向繰り返し回数Nxと、Ｙ方向繰り返し回数
Nyと、Ｘ方向繰り返し間隔Dxと、Ｙ方向繰り返し間隔Dy
とからなる情報で、例えばある図形が１つだけ配置され
ている場合に、（１，１，０，０）のように抽出され
る。

【００４２】繰り返し情報を抽出すると、圧縮処理実行
手段は、ワークエリア内の配列情報（図７（ａ）参照）
に、抽出した繰り返し情報と同じ繰り返し情報（Nx，N
y，Dx，Dy）があるか否かを検索する。既に同じ繰り返
し情報があれば、その配列INDEX を取得する。一方、同
じ繰り返し情報がなければ、抽出した繰り返し情報を登
録して、新たな配列INDEX を割り当てた後、その配列IN
DEX を取得する（Ｓ２１７）。取得した配列INDEX は、
所定のフォーマットでインスタンス情報として登録して
おく（Ｓ２１８）。そして、圧縮処理実行手段は、ワー
クエリアに登録しておいた各種情報を再構成し、圧縮後
のＬＳＩレイアウトデータとして入出力Ｉ／Ｆから出力
する（Ｓ２１９）。

【００４３】このように、オフセット量以外の情報が全
て同一であるインスタンス情報が２つ以上あった場合に
は、形状INDEX と配列INDEX とを組み合わせることによ
り、インスタンス情報を効率的に表現することができ
る。例えば、図７（ｂ）に示すようなオフセット量及び
形状INDEX で特定できる図形があった場合に、形状INDE
X と配列INDEX とを組み合わせると、図７（ｃ）に示す
ように表現することができる。

【００４４】以上のように、本実施の形態のデータ圧縮
方法は、ＬＳＩレイアウトデータの中には同一形状の図
形の出現確率が高いという経験的事実に着目し、ＬＳＩ
レイアウトデータ中において、異なる位置に配置された
同一形状の図形があった場合に、これらの図形に同一の
INDEX を与えるとともに、これらの図形を、そのINDEX
と、各図形の始点位置座標、すなわちオフセット量とを
用いて表現するようになっている。したがって、このデ
ータ圧縮方法を用いてＬＳＩレイアウトデータに対する
データ圧縮を行えば、従来のように各図形を頂点座標の
座標列で表現する場合に比べて、データサイズを削減す
ることができるようになる。これにより、ＬＳＩの高密
度化が進んでも、そのデータサイズが膨大になってしま
うのを抑えることができるようになり、データハンドリ
ングに多くの時間を費やしたり、スラッシングによりコ
ンピュータの処理効率が低下してしまうことを防止する
ことが可能になる。

【００４５】また、ＬＳＩレイアウトデータの中には矩
形で表現される図形が多く、ほとんどの図形がＸ，Ｙ軸
に平行であるといった特性を鑑み、本実施の形態のデー
タ圧縮方法は、各図形の形状INDEX を、その形状におけ
る頂点座標間の変移量（例えば、矩形であればをＷと
Ｈ）用いて定義するようになっている。これにより、従
来のように各図形の形状を頂点座標の座標列で表現する
場合に比べて、ＸＹ軸に平行な線分のみによる図形の場
合、各頂点毎にＸまたはＹいずれかの値のみでよくな
る。また、変移量であるため、値そのものが小さくなり
情報量が減るため、データサイズを削減することができ
るようになる。

【００４６】また、通常、ＬＳＩレイアウトデータが複
数のレイヤーから構成されているといった特性を鑑み、
本実施の形態のデータ圧縮方法は、同一形状の図形であ
っても配置されるレイヤーが異なれば、それぞれに異な
る形状INDEX を与えるようになっている。これにより、
層の区別も仮想的に図形形状の情報とすることで、配置
に関する指示がセルの配置と同様に取り扱うことができ
る。

【００４７】また、ＬＳＩレイアウトデータではセル引
用が多用されるといった特性を鑑み、本実施の形態のデ
ータ圧縮方法は、複数の図形の集合であるセルの配置を
一つの図形形状と見なし、各セル毎にセル名INDEX 、ロ
ーテーションINDEX といったINDEX を与えるようになっ
ている。これにより、各セルの配置も一つの図形形状と
同様に扱うことが可能となり、結果として従来よりもデ
ータサイズを削減することができるようになる。

【００４８】また、ＬＳＩレイアウトデータの中には同
一形状の図形の出現確率が高いといった特性を鑑み、本
実施の形態のデータ圧縮方法は、同一形状の図形が一定
のパターンで複数配置される場合には、この一定のパタ
ーンにも配列INDEX を与えるようになっている。これに
より、一定のパターンで複数配置される図形があった場
合には、これらの図形がオフセット量、形状INDEX 、及
び配列INDEX によって表現できるようになり、より一層
のデータサイズの削減が可能となる。これは、セル引用
の場合についても同様である。

【００４９】このような本実施の形態によるデータ圧縮
方法を、０．２５μｍルールの実際のＡＳＩＣ（アプリ
ケーションスペシフィックＩＣ）回路パターンに適用し
た結果、ストリームフォーマット（ＧＤＳIIフォーマッ
ト）でデータサイズが１００ＭＢであり、約１００００
種の図形で構成され、さらに矩形図形とその他の図形と
の存在比が８：２であるＬＳＩレイアウトデータに対し
て、そのデータサイズを約４０ＭＢに圧縮することがで
きた。つまり、この場合には、本実施の形態のデータ圧
縮方法によって４０％程度の圧縮率を得ることができ、
これにより、データハンドリングに要する時間が圧縮前
の約２０min から約８min になり、さらにコンピュータ
のメモリ使用量も６０％程度節約できるようになった。

【００５０】また、本実施の形態によるデータ圧縮方法
を、０．２５μｍルールの実際のＳＲＡＭ回路パターン
に適用した結果、ストリームフォーマット（ＧＤＳIIフ
ォーマット）でデータサイズが３０ＭＢであり、約２０
０００種の図形で構成され、さらに矩形図形とその他の
図形との存在比が６：４であるＬＳＩレイアウトデータ
に対して、そのデータサイズを約１０ＭＢに圧縮するこ
とができた。つまり、この場合には、本実施の形態のデ
ータ圧縮方法によって３３％程度の圧縮率を得ることが
でき、これにより、データハンドリングに要する時間が
圧縮前の約７min から約３min になり、さらにコンピュ
ータのメモリ使用量も６７％程度節約できるようになっ
た。

【００５１】なお、本実施の形態では、ＬＳＩレイアウ
トデータに対するデータ圧縮方法を例に挙げて説明した
が、本発明はこれに限定されるものではない。例えば、
図形のレイアウトを示す画像データなど、所定領域内に
おける図形配置を示すデータであれば、ＬＳＩレイアウ
トデータ以外であっても適用可能である。

【００５２】

【発明の効果】以上に説明したように、本発明のデータ
圧縮方法は、図形形状毎のインデックスと、各図形の始
点位置座標とによって、図形配置を示すデータを表現す
るようになっている。したがって、このデータ圧縮方法
を用いれば、従来のように各図形を頂点座標の座標列で
表現する場合に比べて、データサイズを削減することが
できるようになる。これにより、図形配置を示すデータ
のデータサイズが膨大になってしまうのを抑えることが
できるようになり、データハンドリングの高効率化、コ
ンピュータのメモリ節約によるスラッシングの回避を含
めた処理効率向上が可能となるという効果を奏する。

【図面の簡単な説明】

【図１】本発明に係わるデータ圧縮方法の実施の形態の
一例を示すフローチャートである。

【図２】本発明に係わるデータ圧縮方法によって圧縮さ
れたＬＳＩレイアウトデータのデータ構成の概略を示す
説明図である。

【図３】本発明に係わるデータ圧縮方法をＬＳＩレイア
ウトデータ内の図形に適用した場合の具体例を示す説明
図であり、（ａ）は矩形に適用した場合の図、（ｂ）は
ワークエリア内の形状情報を示す図、（ｃ）はワークエ
リア内にインスタンス情報を示す図、（ｄ）はＸtrap台
形に適用した場合の図、（ｅ）はＹtrap台形に適用した
場合の図、（ｆ）はxytype＝０の多角形に適用した場合
の図、（ｇ）はxytype＝１の多角形に適用した場合の
図、（ｈ）はxytype＝０のパスに適用した場合の図、
（ｉ）はxytype＝１のパスに適用した場合の図、（ｊ）
はxytype＝２のパスに適用した場合の図、（ｋ）はセル
引用に適用した場合の図である。

【図４】圧縮後のＬＳＩレイアウトデータをダンプした
例の説明図である。

【図５】図４のＬＳＩレイアウトデータを図示化した例
の説明図である。

【図６】本発明に係わるデータ圧縮方法の他の実施の形
態を示すフローチャートである。

【図７】図６に示すデータ圧縮方法を実行する際のワー
クエリア内の情報の具体例を示す説明図であり、（ａ）
は配列情報を示す図、（ｂ）はインスタンス情報を示す
図（その１）、（ｃ）はインスタンス情報を示す図（そ
の２）である。

【図８】ＬＳＩレイアウトデータによって配置が特定さ
れる矩形の一例を示す説明図である。

【符号の説明】

Ｓ１０６セル名抽出Ｓ１０７セル名情報の検
索、追加登録Ｓ１０８インスタンス情報にセル名INDEX を登録Ｓ１０９形状情報抽出Ｓ１１０形状情報の検
索、追加登録Ｓ１１１インスタンス情報にOffset、形状INDEX を登
録Ｓ１１２配列情報、ローテーション情報抽出Ｓ１１３配列情報、ローテーション情報の検索、追加
登録Ｓ１１４インスタンス情報に配列INDEX 、形状情報に
ローテーションINDEXを登録

Claims

【特許請求の範囲】

【請求項１】所定領域内における図形配置を示すデー
タに対するデータ圧縮方法であって、前記図形の形状毎に該形状を識別するためのインデック
スを与え、該インデックスと、前記所定領域内における
図形の始点位置座標とを用いて、前記データを表現する
ことを特徴とするデータ圧縮方法。
【請求項２】前記インデックスを与える際に、該イン
デックスを与える図形の形状を該形状における頂点座標
間の変移量を用いて定義することを特徴とする請求項１
記載のデータ圧縮方法。
【請求項３】前記所定領域が複数の層からなる場合
に、同一形状の図形であっても配置される層が異なれば
それぞれに異なるインデックスを与えることを特徴とす
る請求項１記載のデータ圧縮方法。
【請求項４】複数の図形の集合であるセルの配置を一
つの図形形状と見なし、各セル毎に、かつ、そのローテ
ーション情報毎にインデックスを与えることを特徴とす
る請求項１記載のデータ圧縮方法。
【請求項５】前記所定領域内で同一形状の図形が一定
のパターンで複数配置される場合には、該一定のパター
ンにもインデックスを与え、該インデックスと前記同一
形状に与えたインデックスとを組み合わせて、前記デー
タを表現することを特徴とする請求項１記載のデータ圧
縮方法。