配線設計方法、設計装置及びプログラム
【課題】設計時間の短縮を図ること。
【解決手段】設計装置の記憶装置には、半導体装置を検証ステップの格子にて区画した各領域に含まれるレイアウトパターンの面積がそれぞれ格納されるセル面積テーブルと、移動される検証エリアの位置に対応し、各検証エリアには所定数の領域が含まれ、検証エリアに対してその検証エリアに含まれるレイアウトパターンの占有率が、各検証エリアに対応して格納されるセル占有率テーブルを含む面積ＤＢ３３が記憶される。図形ＤＢ３２にはインスタンスの面積テーブルが含まれる。ＣＰＵは、配置されたインスタンスの面積テーブルに従って編集対象のセル面積テーブルを変更し、そのセル面積テーブルに従ってセル占有率テーブルを更新し、セル占有率テーブルの値によりレイアウトパターンの占有面積をチェックする。
【解決手段】設計装置の記憶装置には、半導体装置を検証ステップの格子にて区画した各領域に含まれるレイアウトパターンの面積がそれぞれ格納されるセル面積テーブルと、移動される検証エリアの位置に対応し、各検証エリアには所定数の領域が含まれ、検証エリアに対してその検証エリアに含まれるレイアウトパターンの占有率が、各検証エリアに対応して格納されるセル占有率テーブルを含む面積ＤＢ３３が記憶される。図形ＤＢ３２にはインスタンスの面積テーブルが含まれる。ＣＰＵは、配置されたインスタンスの面積テーブルに従って編集対象のセル面積テーブルを変更し、そのセル面積テーブルに従ってセル占有率テーブルを更新し、セル占有率テーブルの値によりレイアウトパターンの占有面積をチェックする。
【発明の詳細な説明】
【技術分野】
【０００１】
半導体装置の配線設計方法、設計装置及びプログラムに関するものである。
【背景技術】
【０００２】
近年の半導体装置は素子数の増大や高集積化が進められ、それに伴って配線層の多層配線化が進んでいる。一方、各配線層において、レイアウトパターンの密度に偏り、即ち粗密が生じる。レイアウトパターンの粗密は、上方の配線層に段差を生じさせる。
【０００３】
この結果、表面に近い配線層では、下層の累積的な段差により、上層配線と下層配線を接続するビアの接続不良などの問題が発生する。この問題に対し、化学的機械的研磨（ＣＭＰ:Chemical Mechanical Polishing）に代表される研磨技術によるウェハ表面の平坦化や、ダミーパターンの追加による配線密度差の低減が行われている。
【０００４】
しかし、レイアウトパターンの密度が高い部分では、研磨により必用以上にレイアウトパターンが削れてしまう場合がある。このため、レイアウトパターンの最大密度（占有率）を設定し、半導体装置の設計処理では、図２０に示すように、レイアウトデータにおけるレイアウトパターンの密度を検証している。
【０００５】
まず、ステップ１２１において、レイアウトパターン（図形）を入力する。即ち設計装置は、ユーザが操作するマウスなどの入力手段の情報に従って、レイアウトパターンや素子等のレイアウトパターンのデータを生成し、そのデータをファイル１２６に格納する。ステップ１２２において、設計装置は、全レイアウトパターンの入力が終了したか否かを判断し、終了していない場合にはステップ１２１に移行する。全レイアウトパターンの入力が終了した場合、ステップ１２３に移行し、ファイル１２６のレイアウトデータに対して配線密度の検証を実施する。ステップ１２３において、設計装置は、ファイル１２６に格納したレイアウトデータを読み出し、このレイアウトデータの配線密度を算出する。
【０００６】
この時、設計装置は、図２１に実線で示すように、レイアウトパターンＬ１〜Ｌ７のうち、所定サイズの占有率計算エリア１３１内に含まれるレイアウトパターンの占有面積と、占有率計算エリア１３１から配線密度を算出する。次に、占有率計算エリア１３１を一定のステップ（以下、検証ステップ）で移動させる。移動させた占有率計算エリアを破線で示している。そして、この位置において、配線密度を算出する。同様に、占有率計算エリア１３１を一点鎖線，二点鎖線で示す位置に移動させ、それぞれの位置における配線密度を算出する。図２１では、各占有率計算エリア１３１の位置が判りやすいように図面における上下方向にずらしている。
【０００７】
次に、図２０に示すステップ１２４において、設計装置は、ステップ１２３で算出した配線密度と配線密度のプロセス製造基準とを比較し、密度エラーが発生しているか否かを判断する。密度エラーが発生していない場合には処理を終了し、密度エラーが発生している場合にはステップ１２５に移行する。ステップ１２５において、設計装置は、ファイル１２６から読み出したレイアウトデータを表示装置に表示し、ユーザにより編集されたレイアウトデータをファイル１２６に格納した後、再度密度を検証するべくステップ１２３に移行する。
【０００８】
上記記載の検証フローでは、ステップ１２３における配線密度の検証に半導体装置全体のレイアウトデータが必用である。このため、配線密度の検証の結果、レイアウトデータの一部を修正した場合であっても、半導体装置全体のレイアウトデータに対して検証を行うため、レイアウトデータの検証に多くの時間を費やし、開発期間が増大する。また、レイアウトデータの修正後に行う検証で密度エラーが発生した場合には、レイアウトパターン修正を行った後、再度配線密度の検証を行わなければならない。このため、工程の手戻りが発生し、更に修正ミスなどによって手戻り工数が増加する。図１３に示すように、配線密度の算出において、占有率計算エリア１３１の検証ステップを小さく設定した場合には検証時間が増大し、検証ステップを大きく設定した場合には検証漏れが発生し、後工程からの手戻りが発生する場合がある。
【０００９】
上記記載の問題に対して、例えば、特許文献１は、検証を行おうとするマクロブロックもしくはチップのレイアウト内部に所定のレイアウトデータ率を持つ仮想（ダミー）データを、一時的に前記レイアウトに加え（ステップＳ２）、もしくは前記レイアウトから差し引くことにより、仮想的なレイアウトである仮想レイアウトを形成し、このように作成された仮想レイアウトに対して配線密度の検証を行い（ステップＳ３）、レイアウト完成前に配線密度の分布を求めている。これにより、レイアウトデータの完成前に配線密度の検証をすることができ、マクロブロック単位でも配線密度検証ができるため、開発期間の増大を抑えることができる。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】特開２００３−６７４４１号公報
【発明の概要】
【発明が解決しようとする課題】
【００１１】
しかしながら、上記特許文献１のレイアウト密度検証方法では、仮想データをレイアウトに加え、もしくは差し引き、仮想レイアウトを生成する必用があり、手間がかかるという問題がある。また、仮想データをレイアウトに加え、もしくは差し引くため、仮想データと実際のレイアウトパターンとが相違し、実際のレイアウトパターンの密度検証を行っていない。この結果、密度誤差が生じるおそれがあり、手戻りが発生する場合があり、設計時間を短縮する妨げとなる場合があった。
【００１２】
開示された配線設計方法は、設計時間の短縮を図ることを目的とする。
【課題を解決するための手段】
【００１３】
配線設計方法の一観点によれば、記憶装置には、インスタンスに含まれるレイアウトパターンに対応する面積値が格納されたインスタンス面積テーブルが記憶され、中央処理装置が実行する処理は、インスタンスが配置されたセルのセル面積テーブルを、インスタンス面積テーブルに従って更新するステップと、更新されたセル面積テーブルに基づいてインスタンスが配置されたセルに対応するセル占有率テーブルを更新するステップと、を含む。
【発明の効果】
【００１４】
開示された方法によれば、設計時間の短縮を図ることができる。
【図面の簡単な説明】
【００１５】
【図１】配線設計装置の概略構成図である。
【図２】配線設計処理の概略フロー図である。
【図３】配線設計処理のフロー図である。
【図４】配線設計処理のフロー図である。
【図５】保証占有率の説明図である。
【図６】（ａ）〜（ｃ）は配線設計処理の説明図である。
【図７】（ａ）〜（ｃ）は配線設計処理の説明図である。
【図８】（ａ）〜（ｃ）は配線設計処理の説明図である。
【図９】（ａ）〜（ｃ）は配線設計処理の説明図である。
【図１０】（ａ），（ｂ）は配線設計処理の説明図である。
【図１１】（ａ）〜（ｄ）は配線設計処理の説明図である。
【図１２】（ａ）〜（ｃ）は配線設計処理の説明図である。
【図１３】（ａ）〜（ｄ）は配線設計処理の説明図である。
【図１４】（ａ）〜（ｃ）は配線設計処理の説明図である。
【図１５】（ａ）〜（ｃ）は配線設計処理の説明図である。
【図１６】（ａ）〜（ｃ）は配線設計処理の説明図である。
【図１７】（ａ）〜（ｃ）は配線設計処理の説明図である。
【図１８】（ａ），（ｂ）は配線設計処理の説明図である。
【図１９】（ａ），（ｂ）は配線設計処理の説明図である。
【図２０】従来の配線設計処理のフロー図である。
【図２１】従来の配線設計処理の説明図である。
【発明を実施するための形態】
【００１６】
以下、一実施形態を図１〜図１１に従って説明する。
図１に示すように、半導体装置のレイアウトデータを生成するための設計装置（コンピュータ）１１は一般的なＣＡＤ（Computer Aided Design ）装置からなり、中央処理装置（以下、ＣＰＵという）１２、メモリ１３、記憶装置１４、表示装置１５、入力装置１６、及び、ドライブ装置１７により構成され、それらはバス１８を介して相互に接続されている。
【００１７】
ＣＰＵ１２は、メモリ１３を利用してプログラムを実行し、半導体装置のレイアウト設計等の必要な処理を実現する。プログラムは、ＣＰＵ１２を半導体装置のレイアウトデータを生成する設計装置としての各種手段として機能させるためのものである。メモリ１３には、各種処理を提供するために必要なプログラムとデータが格納され、メモリ１３としては、通常、キャッシュ・メモリ、システム・メモリおよびディスプレイ・メモリを含む。
【００１８】
表示装置１５は、レイアウト表示、パラメータ入力画面等の表示に用いられ、これにはＣＲＴ，ＬＣＤ，ＰＤＰ等が用いられる。入力装置１６は、ユーザからの要求や指示，パターン，パラメータの入力に用いられ、これにはキーボードおよびマウス装置（図示せず）等が用いられる。
【００１９】
コンピュータ１１は、レイアウトデータに基づき半導体装置に形成するレイアウトパターン（図形）を表示装置１５に表示させる。そして、コンピュータ１１は、ユーザが操作する入力装置１６からの信号に従って、表示装置１５上のレイアウトパターンの追加，削除を行うとともに、レイアウトデータに対してパターンデータの追加，削除を行う。
【００２０】
記憶装置１４は、通常、磁気ディスク装置、光ディスク装置、光磁気ディスク装置を含む。この記憶装置１４には、図２〜図４に示す各ステップからなる半導体装置（半導体集積回路装置）のレイアウトデータを生成するためのプログラムデータと、プログラムの実行に必要なデータ、プログラムの実行により生成されるデータが格納される。ＣＰＵ１２は、入力装置１６による指示に応答しているプログラムデータをメモリ１３へ転送し、それを実行する。
【００２１】
ＣＰＵ１２が実行するプログラムデータは、記録媒体１９にて提供される。ドライブ装置１７は、記録媒体１９を駆動し、その記憶内容にアクセスする。ＣＰＵ１２は、ドライブ装置１７を介して記録媒体１９からプログラムデータを読み出し、それを記憶装置１４にインストールする。
【００２２】
記録媒体１９としては、磁気テープ（MT）、メモリカード、フレキシブルディスク、光ディスク（CD-ROM,DVD-ROM,… ）、光磁気ディスク（MO,MD,…）等、任意のコンピュータ読み取り可能な記録媒体を使用することができる。この記録媒体１９に、上述のプログラム，データを格納しておき、必要に応じて、メモリ１３にロードして使用することもできる。
【００２３】
尚、記録媒体１９には、通信媒体を介してアップロード又はダウンロードされたプログラムデータを記録した媒体、ディスク装置を含む。更に、コンピュータによって直接実行可能なプログラムを記録した記録媒体だけでなく、いったん他の記録媒体（ハードディスク等）にインストールすることによって実行可能となるようなプログラムを記録した記録媒体や、暗号化されたり、圧縮されたりしたプログラムを記録した記録媒体も含む。
【００２４】
次に、配線密度を考慮したレイアウト検証方法の概要を、図２のフローチャートに従って説明する。
図１のＣＰＵ１２は、図２に示すステップ２１〜２２の処理を実行することで、半導体装置を形成するためのレイアウトデータ３１を生成する手段と、レイアウトデータ３１に含まれるレイアウトパターンの密度を検証する手段として機能する。このレイアウトデータ３１は図１に示す記憶装置１４に記憶される。なお、レイアウトデータ３１は、他の配線設計装置等により作成されたものであってもよい。
【００２５】
まず、ステップ２１において、ＣＰＵ１２は、図形生成処理を実行する。図形生成処理は、所定形状のレイアウトパターンを入力する入力処理と、入力済のレイアウトパターンの形状を変更する編集処理を含む。ＣＰＵ１２は、図形生成処理において生成したレイアウトパターンの形状やレイアウトパターンを形成する層などの情報を含むレイアウトデータ３１を生成する。レイアウトパターンの入力のために必用な処理と、レイアウトデータ３１に含まれるレイアウトパターンの編集に必用な処理はほぼ同じである。
【００２６】
ＣＰＵ１２は、表示装置１５に、レイアウトデータに基づくレイアウトパターンを表示するとともに、ユーザが操作する入力装置１６からの信号に基づいて、入力中のレイアウトパターンもしくは編集中のレイアウトパターンを表示する。そして、ユーザがレイアウトパターンの入力確定を指示すると、ＣＰＵ１２は、確定されたレイアウトパターンをレイアウトデータ３１に格納する。
【００２７】
この図形生成処理において、ＣＰＵ１２は、図形データベース（図形ＤＢ）３２を参照する。図形ＤＢ３２は、図１に示す記憶装置１４に格納されている。図形ＤＢ３２は、例えばライブラリデータであって、配線等を形成するためのポリゴンデータ、素子の形状を示すデータ、インスタンスの情報（大きさ、含まれるレイアウトパターン、面積テーブル等）、を含む。
【００２８】
例えば、ＣＰＵ１２は、ユーザの指定に従ってポリゴンデータを図形ＤＢ３２から読出し、そのポリゴンデータの頂点を変更することにより所望の配線層のレイアウトパターンを形成する。配線層は、半導体装置を形成するパターンを形成する層である。レイアウトパターンは、所定の配線層に形成するための情報を有している。また、ＣＰＵ１２は、ユーザの指定に従ってインスタンスを図形ＤＢ３２から読み出し、そのインスタンスを配置することにより、インスタンスに含まれるレイアウトパターンを形成する。インスタンスに含まれるレイアウトパターンは、直接的に入力されるレイアウトパターンと同様に、所定の配線層に形成するための情報を有している。なお、パターンを形成する配線層を指定する情報（層情報）は、インスタンスの情報を記憶したライブラリに含まれる場合もある。
【００２９】
更に、ＣＰＵ１２は、この図形入力・編集処理において、処理中（入力中もしくは編集中）のレイアウトパターンに基づいて、面積データベース（面積ＤＢ）３３を更新する。面積ＤＢ３３は、図１に示す記憶装置１４（又はメモリ１３）に格納される。ＣＰＵ１２は、面積ＤＢ３３に基づいて、処理中のレイアウトパターンに係る層について配線密度の検証を実行し、処理中のレイアウトパターンが含まれる検証領域において密度エラー発生しているか否かを判断する。そして、ＣＰＵ１２は、密度エラーが発生している場合にその旨を表示装置１５に表示するとともに、処理中のレイアウトパターンに対する編集制御を行う。つまり、ＣＰＵ１２が図形入力・編集処理を行うステップ２１は、配線密度の検証を行うサブステップ２１ａと、エラー表示・編集制御を行うサブステップ２１ｂとを含む。
【００３０】
密度エラーが発生することなくレイアウトパターンを確定すると、ＣＰＵ１２はステップ２１からステップ２２に移行し、そのステップ２２において、全レイアウトパターンの入力が終了したか否かを判断する。全レイアウトパターンの入力が終了していない場合、ＣＰＵ１２は、ステップ２１に移行し、図形生成処理を実行する。全レイアウトパターンの入力が終了した場合、ＣＰＵ１２は、配線密度を考慮したレイアウト検証を終了する。
【００３１】
次に、上記のステップ２１における図形生成処理の一例を説明する。
まず、図３に示すステップ４１において、ＣＰＵ１２は、図２の面積ＤＢ３３に含まれるセル面積テーブル３５とセル占有率テーブル３６を初期化する。例えば、新たなレイアウトデータを生成する場合、ＣＰＵ１２は、セル面積テーブル３５とセル占有率テーブル３６をそれぞれクリア、つまり各テーブル３５，３６を構成する要素の値を「０」にする。各テーブル３５，３６は、検証ステップに応じたサブテーブルを有している。従って、ステップ４１において、ＣＰＵ１２は、各テーブル３５，３６のサブテーブルを初期化する。
【００３２】
上記したように、レイアウトパターンは、半導体装置の配線層に形成されるため、セル面積テーブル３５及びセル占有率テーブル３６は、配線層に応じた複数のテーブルを含む。更に、所定の領域（検証エリア）におけるレイアウトパターンの密度を検証するために複数の検証ステップが設定されている。従って、セル面積テーブル３５及びセル占有率テーブル３６は、配線層毎に、検証ステップに応じた複数のテーブルを有している。
【００３３】
設計装置１１にはレイアウトデータの配線密度を検証する検証エリアを移動させる複数の検証ステップが設定されている。本実施形態において、設計装置１１には、検証ステップとして、所定値の第１検証ステップと、その第１検証ステップよりも小さな値の第２検証ステップが設定されている。本実施形態において、設定する各検証ステップＸ軸方向及びＹ軸方向の大きさは、本設計装置１１により生成するレイアウトパターンの最小サイズ、即ち入力ステップのＸ軸方向及びＹ軸方向の値に対応している。第１検証ステップはＸ軸方向及びＹ軸方向ともに入力ステップの整数倍（例えば２倍）に設定され、第２検証ステップは入力ステップの等倍（１倍）に設定されている。
【００３４】
ＣＰＵ１２は、大きな値から小さな値へと検証ステップを変更し、レイアウトパターンに対する密度チェック処理等を実行する。即ち、ＣＰＵ１２は、先ず第１検証ステップにて密度チェックを行い、次に、第２検証ステップに変更して密度チェックを行う。この第２検証ステップによる密度チェックにおいて、ＣＰＵ１２は、第１検証ステップにて行った密度チェックの結果に基づいて、密度違反の可能性が高い部分を対象領域とし、この対象領域について第２検証ステップによる密度チェックを行う。即ち、第２検証ステップによる密度チェックを行う領域を予め絞り込むことで、密度チェックに要する処理時間（演算時間）が少なくなり、チェックに要する時間を短縮することができる。
【００３５】
セル面積テーブル３５は、２つの検証ステップに応じたサブテーブル３５ａ，３５ｂを含む（図６，７参照）。即ち、セル面積テーブル３５は、第１検証ステップに対応する第１セル面積テーブル３５ａ（図６（ｂ）参照）と、第２検証ステップに対応する第２セル面積テーブル３５ｂ（図７（ｂ）参照）とを含む。
【００３６】
セル面積テーブル３５（３５ａ、３５ｂ）に格納された値は、各テーブル３５ａ，３５ｂに対応する検証ステップの格子、及びその格子内に生成されたレイアウトパターンの占有面積に対応する。例えば、Ｘ軸及びＹ軸のサイズが入力ステップと等しい格子の面積を「１」とした場合、第１検証ステップはＸ軸方向及びＹ軸方向において入力ステップの２倍に設定されているため、第１検証ステップの格子内に生成されるレイアウトパターンの占有面積は「１」〜「４」うちの何れかとなり、第２検証ステップは入力ステップと等倍に設定されているため、第２検証ステップの格子内に生成されるレイアウトパターンの占有面積は「１」となる。従って、第１検証ステップに対応する第１セル面積テーブル３５ａの各要素は、レイアウトパターンが形成されていない場合の値「０」と、格子内に形成されるレイアウトパターンの占有面積「１」〜「４」の何れかの値となる。第２検証ステップに対応する第２セル面積テーブル３５ｂの各要素は、レイアウトパターンが形成されていない場合の値「０」と、レイアウトパターンが形成されている場合の値「１」の何れかとなる。
【００３７】
同様に、セル占有率テーブル３６は、２つの検証ステップに応じたサブテーブル３６ａ，３６ｂを含む（図６，７参照）。即ち、セル占有率テーブル３６は、第１検証ステップに対応する第１セル占有率テーブル３６ａ（図６（ｃ）参照）と、第２検証ステップに対応する第２セル占有率テーブル３６ｂ（図７（ｃ）参照）とを含む。
【００３８】
セル占有率テーブル３６（３６ａ，３６ｂ）の値は、各値に対応する位置の検証エリアにおいて、その検証エリアの面積と、その検証エリア内に生成されたレイアウトパターンの占有面積との比を示す。例えば、検証エリアの縦横、つまりＸ軸方向及びＹ軸方向のサイズをそれぞれ入力ステップ（第２検証ステップ）の１０倍（第１検証ステップの５倍）に設定する。従って、１００個の格子からなる検証エリアが設定される。そして、検証エリアの総項指数と、検証エリア内においてレイアウトパターンが形成された格子の数との比が、検証エリアの位置に対応する要素の値としてセル占有率テーブル３６（３６ａ，３６ｂ）に格納される。一例として、検証エリアに含まれる１００個の格子のうちの１個にレイアウトパターンを形成した場合、対応するセル占有率テーブル３６ａ，３６ｂの値はそれぞれ「１（％）」となる。別の例として、検証エリアを構成する１００個の格子のうちの５０個にレイアウトパターンを形成した場合、対応するセル占有率テーブル３６ａ，３６ｂの値はそれぞれ「５０（％）」となる。
【００３９】
レイアウトデータのレイアウトパターンと、セル面積テーブル３５（３５ａ，３５ｂ）及びセル占有率テーブル３６（３６ａ，３６ｂ）の関係を図８に従って説明する。
図８（ａ）に示すように、表示装置１５の画面にはレイアウトパターンＰ２（ハッチングを付した部分）が表示されている。このレイアウトパターンＰ２は、設計装置１１には所定の入力ステップに応じた入力格子（図において一点鎖線で示す格子）が設定されている。そして、レイアウトパターンＰ２は、設定された入力格子のうち、図８（ａ）に示す格子６１ａ，６１ｂに形成されている。上記したように、第１検証ステップは入力ステップの２倍に設定されている場合、その第１検証ステップに対応する第１セル面積テーブル３５ａの１つの要素の値は、隣接する４つの格子（図８（ａ）において格子６１ａ，６１ｂ，６１ｃ，６１ｄ）に形成されたレイアウトパターンの占有面積となる。１つの格子に形成されたレイアウトパターンの占有面積を「１」とすると、図８（ａ）に示すレイアウトパターンＰ２の場合、図８（ｂ）に示すように、要素６２の値が「２」となる。
【００４０】
レイアウトデータの密度チェックのために、検証エリアＶＡを設定する。ＣＰＵ１２は、検証エリアＶＡにおいてレイアウトパターンＰ２が占める占有面積の割合（占有率）を算出し、その占有率を検証エリアＶＡの位置に対応して第１セル占有率テーブル３６ａに格納する。例えば、図８（ａ）に示すように、１００個の入力格子（＝横１０×縦１０）に検証エリアＶＡが設定され、この検証エリアＶＡを第１検証ステップにて移動させ、各位置における占有率を算出し、その算出した占有率にて第１セル占有率テーブル３６ａを更新する。例えば、図８（ｂ）に示す検証エリアＶＡに対応して、図８（ｃ）に示す第１セル占有率テーブル３６ａの要素６３の占有率を「２」とする。図８（ａ）に示すレイアウトパターンＰ２の占有面積が影響する部分は、図８（ｃ）の枠６４で囲まれた部分となる。従って、ＣＰＵ１２は、この枠６４内の要素の値を「２」とする。
【００４１】
尚、形成したレイアウトパターンと、第２セル面積テーブル３５ｂ及び第２セル占有率テーブル３６ｂの関係は、上記したように、レイアウトパターンＰ２と第１セル面積テーブル３５ａ及び第１セル占有率テーブル３６ａとの関係と同じであり、ＣＰＵ１２が行う処理も、検証ステップの大きさが異なるだけであるため、説明を省略する。
【００４２】
次に、ステップ４２において、ＣＰＵ１２は、入力装置１６の操作に従ってひとつのレイアウトパターンの入力処理またはレイアウトパターンの編集処理を開始する。また、このステップ４２において、ＣＰＵ１２は、インスタンスの配置・編集処理を行う。例えば、ポリゴンを作成する始点が決定されることによりレイアウトパターンの入力処理を開始し、ポリゴンの頂点が指示されることにより編集処理を開始する。これ以降の処理において、レイアウトパターンを入力することと既存のレイアウトパターンを編集（変形）することに状態に差が生じているが、入力中のレイアウトパターンに対する検証処理（チェック）と、編集中のレイアウトパターンに対する検証処理（チェック）とは同じ内容であるため、以下の説明において、レイアウトパターンの入力に対する処理について説明する。
【００４３】
ステップ４３（トリガ判定工程）において、ＣＰＵ１２は、ステップ４２において、入力中のレイアウトパターンが第１所定の検証ステップ（例えば第１検証ステップ）の判定格子を通過したか否か、又はレイアウトパターンの入力を終了したか否かを判断する。また、ＣＰＵ１２は、このステップ４３において、インスタンスの配置を終了したか否かを判断する。ＣＰＵ１２は、入力レイアウトパターンが格子を通過せず、且つレイアウトパターンの入力が終了されていない場合にステップ４２に移行し、入力レイアウトパターンが判定格子を通過したか又はレイアウトパターンの入力が終了された場合にステップ４４に移行する。また、ＣＰＵ１２は、追加するインスタンスの配置が決定された場合（例えばマウスのボタンが操作されて配置位置がクリックされた場合）にステップ４４に移行する。つまり、ＣＰＵ１２は、入力レイアウトパターンが判定格子を通過すること、又はレイアウトパターンの入力が終了、又はインスタンスの配置することをトリガとして次のステップに移行する。
【００４４】
ステップ４４において、ＣＰＵ１２は、入力中のレイアウトパターンの占有面積を算出する。この時、ＣＰＵ１２は、レイアウトパターンの占有面積を、検証ステップ毎に算出する。
【００４５】
そして、ステップ４５において、ＣＰＵ１２は、ステップ４４において算出したレイアウトパターンの占有面積に基づいて、その時の検証ステップに対応する面積テーブルを更新する。つまり、ＣＰＵ１２は、入力したレイアウトパターンに基づいて、第１セル面積テーブル３５ａ及び第２セル面積テーブル３５ｂを更新する。なお、レイアウトパターンは、形成する配線層を指定して入力される。従って、ＣＰＵ１２は、レイアウトパターンを形成する配線層に対応する第１セル面積テーブル３５ａ及び第２セル面積テーブル３５ｂを更新する。
【００４６】
また、ステップ４５において、ＣＰＵ１２は、配置が決定されたインスタンスの面積テーブル３４を図２の図形ＤＢ３２から読み出し、その面積テーブル３４に応じて編集対象のセルのセル面積テーブル３５を更新する。インスタンスはレイアウトパターンを含み、レイアウトパターンは、パターンを形成する層に応じて設定されている。面積テーブル３４は、配線密度を考慮する必要のある層に対応する面積テーブルを含む。面積テーブル３４には、セル面積テーブルと同様に、各格子に含まれるレイアウトパターンの面積が格納されている。ＣＰＵ１２は、インスタンスの面積テーブル３４の値とセル面積テーブル３５の値とを対応する層毎に合成してセル面積テーブル３５の値を更新する。
【００４７】
ステップ４６において、ＣＰＵ１２は、ステップ４５において更新したセル面積テーブル３５（３５ａ，３５ｂ）の値に基づいて、対象部分の占有率を算出する。次に、ステップ４７において、ＣＰＵ１２は、ステップ４６にて計算した占有率により、検証ステップに対応するセル占有率テーブル３６（３６ａ，３６ｂ）の対象部分の値を更新する。この時、ＣＰＵ１２は、設定された検証ステップに対応するテーブルを対象テーブルとしてその対象テーブルを更新する。即ち、ＣＰＵ１２は、第１検証ステップがその時の検証ステップとして設定されている場合、第１検証ステップに対応する第１セル占有率テーブル３６ａを対象テーブルとし、その対象テーブルを更新する。同様に、ＣＰＵ１２は、第２検証ステップがその時の検証ステップとして設定されている場合、第２検証ステップに対応する第２セル占有率テーブル３６ｂを対象テーブルとし、その対象テーブルを更新する。
【００４８】
ステップ４６における対象部分は、レイアウトパターンの入力によって占有率の値が変化する要素からなる部分、又は処理によって抽出された部分である。例えば、Ｘ軸方向とＹ軸方向のそれぞれにおいて、第１検証ステップを検証エリアのサイズの１／５に設定した場合、１つの格子におけるレイアウトパターンの占有面積の変更が、セル占有率テーブル３６の２５個の要素に影響する。従って、ＣＰＵ１２は、２５個の要素についてそれぞれ占有率を算出する。同様に、第２検証ステップを検証エリアの１／１０に設定した場合、ＣＰＵ１２は、１００個の要素についてそれぞれ占有率を算出する。これらの占有率を算出する領域の大きさは、半導体装置のチップ面積に比べて極めて小さい。従って、半導体装置の全体について占有率を算出する時間に比べて、極めて短い時間で対応する領域の占有率を算出することができる。
【００４９】
第２セル占有率テーブル３６ｂの要素のうち、必ず第１セル占有率テーブル３６ａの要素と同じ値となるものが存在する。これは、要素の値、つまり占有率を算出する検証エリアの位置が同じであることに因る。上記したように、第１セル占有率テーブル３６ａの各要素の値は、第１検証ステップにて検証エリアを移動させ各位置において算出した値であり、第２セル占有率テーブル３６ｂの各要素の値は第２検証ステップにて検証エリアを移動させ各位置において算出した値である。従って、上記のように、第１検証ステップを第２検証ステップの２倍に設定した場合、第２セル占有率テーブル３６ｂを構成する各要素のうち、Ｘ軸方向及びＹ軸方向のそれぞれにおいて、１つ置きに検証エリアの位置が第１セル占有率テーブル３６ａの要素に対応する検証エリアの位置と一致する。そして、検証エリアの位置が一致する要素は、第１セル占有率テーブル３６ａと第２セル占有率テーブル３６ｂの設定により決定される、即ち検証処理を行う時点では判っている。従って、第１セル占有率テーブル３６ａの要素の値を算出することにより、第２セル占有率テーブル３６ｂの一部の要素の値を確定することができ、その分の演算を省略することができる。
【００５０】
図４に示すステップ４８において、ＣＰＵ１２は、ステップ４７において、セル占有率テーブル３６のうち更新された部分の占有率が、占有率の上限値を超えているか否かを判断し、占有率が上限値以下の場合（ＮＯ）はステップ４９に移行し、占有率が上限値を超えている場合（ＹＥＳ）はステップ５３に移行する。占有率の上限値は、製造プロセスの基準値（許容されるレイアウトパターンの密度の最大値）である。
【００５１】
ステップ４９において、ＣＰＵ１２は、更新部分の占有率が、保証占有率を超えているか否かを判断する。そして、ＣＰＵ１２は、占有率が保証占有率以下の場合（ＮＯ）はステップ５０に移行し、占有率が保証占有率を超えている場合（ＹＥＳ）はステップ５４（図３参照）に移行する。
【００５２】
保証占有率は、検証エリアの移動によってレイアウトパターンの占有面積が増減し、この占有面積の増減により変化する占有率が、占有率の上限値を超えないことを保証できる占有率を言う。占有面積の増減は、検証ステップに対応する。従って、保証占有率は、検証ステップに応じて設定されている。本実施形態では、検証ステップとして第１検証ステップ及び第２検証ステップが設定されているため、保証占有率は、第１検証ステップに対応する第１保証占有率と、第２検証ステップに対応する第２保証占有率とが設定されている。
【００５３】
保証占有率を図５に従って説明する。一例として、レイアウトパターンＰ１が形成されている。ＣＰＵ１２は、このレイアウトパターンＰ１に対して、検証エリアＶＡを検証ステップＶＳずつ移動させて各位置における占有率を算出する。この場合において、実線で示す検証エリアＶＡを、破線で示す位置まで移動させる。この時、実線で示す検証エリアＶＡに含まれるレイアウトパターンＰ１の占有面積に対して、破線で示す検証エリアＶＡに含まれるレイアウトパターンの占有面積は、検証エリアＶＡの縦（図５において上下方向）の長さと、検証ステップＶＳとの積の値となる。つまり、検証エリアＶＡにおける占有率は、検証エリアＶＡの横（図５において左右方向であって、検証エリアＶＡを移動させる方向）の長さと、検証ステップＶＳとの比だけ増加することになる。
【００５４】
上記例のように、検証エリアが１００個の格子から構成され、第１検証ステップがその１つの格子のサイズの２倍に設定されている場合、移動によって検証エリアの占有率は、最大２０（％）増加する。このため、占有率の上限値を５０（％）とすると、その最大値を超えないように保証する値、即ち第１保証占有率は３０（％）となる。また、検証エリアが１００個の格子から構成され、第２検証ステップがその１つの格子のサイズと等しく設定されている場合、移動によって検証エリアの占有率は、最大１０（％）増加する。このため、第２保証占有率は４０（％）となる。
【００５５】
従って、所定位置における検証エリアの占有率が保証占有率を超えていない場合、その検証エリアを検証ステップに応じて移動させた位置に於いても、占有率が最大値を超えることはない。つまり、所定の検証エリアにおける占有率を算出することにより、その位置における占有率と検証ステップだけずれた位置における検証エリアの占有率が、占有率の最大値が越えているか否かを判断することができる。
【００５６】
また、第１保証占有率は、第２検証ステップにおいて算出する占有率が上記の上限値を超えないことを保証する。例えば、上記したように第１検証ステップは第２検証ステップの２倍に設定されている。この場合、第２検証ステップに対応する第２セル占有率テーブル３６ｂには、第１検証ステップと第２検証ステップとにおいて検証エリアが一致する位置における占有率と、その位置からＸ軸方向、Ｙ軸方向に第２検証ステップだけ検証エリアを移動させた位置における占有率を含む。これらの位置における占有率の増加は、第２検証ステップにて検証エリアを移動させた時の占有面積の増加分となる。つまり、Ｘ軸方向にのみ検証エリアを移動させた場合、検証エリアの占有率は、最大１０（％）増加する。同様に、Ｙ軸方向にのみ検証エリアを移動させた場合、検証エリアの占有率は、最大１０（％）増加する。そして、Ｘ軸方向とＹ軸方向にそれぞれ検証エリアを移動させた場合、検証エリアの占有率は、最大１９（％）増加する。従って、第１セル占有率テーブル３６ａにおいて、占有率が第１保証占有率（＝３０）を越えていない場合、その占有率を算出した検証エリアの位置からそれぞれ第２検証ステップだけ検証エリアを移動させた位置における占有率は、占有率の上限値を超えないことになる。つまり、占有率が上限値を超えないことを保証することができる。
【００５７】
ステップ５０（エラー判断工程）において、ＣＰＵ１２は、対象領域の占有率が占有率の上限値と等しいか否かを判断し、対象領域の占有率が上限値と等しい場合（ＹＥＳ）にはステップ５１に移行し、等しくない場合（ＮＯ）にはステップ５２に移行する。
【００５８】
ステップ５１（エラー解消工程）において、ＣＰＵ１２は、図形入力禁止エリアを生成する。図形入力禁止エリアは、作業者の操作によるレイアウトパターンの追加を禁止するエリアである。ＣＰＵ１２は、対象領域の占有率に影響を与える範囲に対応して図形入力禁止エリアを生成する。この図形入力禁止エリアにより、所定位置の検証エリアにおける占有密度が、占有率の上限値を超えるのを防ぐ。
【００５９】
ステップ５２において、ＣＰＵ１２は、全図形入力・編集終了か否かを判断する。操作者は、全てのレイアウトパターンを入力し終わるか、又はレイアウトパターンの編集を終了すると、図１に示す入力装置１６により入力又は編集処理の終了を指示する。ＣＰＵ１２は、入力装置１６からの信号に基づいて、終了指示の有無を判断し、終了が指示されている場合（ＹＥＳ）は図形入力・編集処理を終了し、終了が指示されていない場合（ＮＯ）は図３のステップ４２移行し次のレイアウトパターンの入力又はレイアウトパターンの編集を可能とする。
【００６０】
上記のステップ４８において、更新された部分の占有率が上限値を超えている場合（ＹＥＳ）、ＣＰＵ１２はステップ５３に移行する。ステップ５３において、ＣＰＵ１２は、エラー発生箇所までレイアウトパターンの入力を強制的に戻す、又は各データをインスタンスの配置前の状態に戻し、セル面積テーブル３５とセル占有率テーブル３６を更新し、ステップ５０に移行する。エラー発生箇所は、エラーとなるレイアウトパターンを生成した入力確定又は操作の直前において検証処理を終了した箇所を示す。つまり、エラーが発生した場合に、その検証処理の直前の入力や処理による変更をセル面積テーブル３５及びセル占有率テーブル３６から削除することで、エラー発生までに確定したレイアウトパターンの状態を示す。このエラー発生箇所まで入力を戻すことにより、エラー発生を自動的に解消するとともに、エラーの発生を操作者に示すことが可能となる。
【００６１】
上記のステップ４９において、更新部分の占有率が保証占有率を超えている場合（ＹＥＳ）、ＣＰＵ１２は図３に示すステップ５４に移行する。図３に示すステップ５４において、ＣＰＵ１２は、セル占有率テーブル３６の更新箇所内で保証占有率を超えている検証エリア、即ち第１セル占有率テーブル３６ａの要素を抽出する。次に、ステップ５５において、ＣＰＵ１２は、保証占有率・検証ステップを更新する。詳しくは、ＣＰＵ１２は、検証ステップを第１検証ステップから第２検証ステップに変更するとともに、保証占有率を第１保証占有率から第２保証占有率に変更する。そして、ＣＰＵ１２は、ステップ４６に移行する。
【００６２】
ステップ４６において、ＣＰＵ１２は、ステップ５５において抽出した第１セル占有率テーブル３６ａの要素を対象領域とする。そして、ＣＰＵ１２は、ステップ５６において設定した第２検証ステップに対応する第２セル占有率テーブル３６ｂの対象領域に含まれる要素の値を更新する。
【００６３】
次に、入力レイアウトパターンの一例を示して上記の処理を説明する。
図９（ａ）に示すように、レイアウトパターン７１，７２が形成されたレイアウトデータに対して、新たなレイアウトパターンを入力する。尚、図９（ａ）は表示装置１５に表示されたレイアウトデータであり、同図９（ａ）において、レイアウトパターン７３は入力中のレイアウトパターンである。更に、図９（ａ）において、破線は第１検証ステップの格子を示す。
【００６４】
図１のＣＰＵ１２は、入力中のレイアウトパターン７３が格子を通過したと判断し（ステップ４３）、入力中のレイアウトパターン７３の占有面積を算出する（ステップ４４）。このとき、格子７４内のレイアウトパターン７３ａについては、このレイアウトパターン７３が入力格子枠７５を越えた時点で処理されている。従って、ＣＰＵ１２は、格子７６内のレイアウトパターン７３ｂの占有面積を算出する。そして、ＣＰＵ１２は、図９（ｂ）に示すように、第１セル面積テーブル３５ａの要素７７を更新する（ステップ４５）。更に、ＣＰＵ１２は、図１０（ａ）に示すように、第２セル面積テーブル３５ｂの要素（実線で囲まれた要素）を更新する（ステップ４５）。
【００６５】
次に、ＣＰＵ１２は、対象部分の占有率を算出し（ステップ４６）、第１セル占有率テーブル３６ａの対象部分の値を更新する。この場合、図９（ｂ）に示す要素７７の値の更新は、図９（ｃ）に示す枠７８内の要素に影響する。このため、ＣＰＵ１２は、枠７８内の要素を対象部分とし、この対象部分の要素の値を更新する（ステップ４７）。
【００６６】
次に、ＣＰＵ１２は、第１セル占有率テーブル３６ａにおいて、更新部分の占有率が上限値を超えているか否かを判断する（ステップ４８）。図９（ｃ）において、枠７８内の要素が更新されているが、何れの要素の値も上限値（＝５０）を超えていない。従って、ＣＰＵ１２は、更新部分の占有率が第１保証占有率（＝３０）を越えているか否かを判断する（ステップ４９）。図９（ｃ）において、枠７８内の要素が更新されており、枠７９内の要素の値が第１保証占有率を超えている。従って、ＣＰＵ１２は、第１保証占有率を超えている要素が含まれるエリア、つまり図９（ｃ）に示す枠７９を抽出する（ステップ５４）。
【００６７】
次に、ＣＰＵ１２は、保証占有率及び検証ステップを、第１保証占有率と第１検証ステップから第２保証占有率と第２検証ステップに更新する（ステップ５５）。
次に、ＣＰＵ１２は、抽出した枠７９内を対象部分とし、対象部分の占有率を算出する（ステップ４６）。この時、ＣＰＵ１２は、検証ステップを第２検証ステップに設定しているため、ステップ５４において抽出した枠７９に対応する第２セル占有率テーブル３６ｂの部分について、占有率を算出する。図９（ｃ）に示す枠７９に対応する部分は、第２セル占有率テーブル３６ｂにおいて、図１０（ｂ）に示す枠８０に囲まれた部分である。従って、ＣＰＵ１２は、この枠８０内の要素について、占有率を算出する。
【００６８】
即ち、ＣＰＵ１２は、第１保証占有率によって第１セル占有率テーブル３６ａの更新部分から密度エラーが発生する可能性が高い部分を抽出し、抽出した部分についてのみ第２セル占有率テーブル３６ｂの値を更新するようにした。従って、更新部分の全ての占有率が第１保証占有率を超えていない場合、抽出は行われず、第２セル占有率テーブル３６ｂの更新も行われない。このため、更新部分の全ての要素について占有率を算出する場合に比べ、演算に要する時間が短くなる。
【００６９】
この占有率算出において、上記したように、第２セル占有率テーブル３６ｂにおいて、検証エリアの位置が第１セル占有率テーブル３６ａの要素と同じ要素については、第１セル占有率テーブル３６ａの要素の値を複写し、他の要素について第２セル面積テーブル３５ｂに従って占有率を算出する。これによって、抽出した部分の要素の全てについて占有率を算出する場合に比べ、演算に要する時間が短くなる。
【００７０】
上記のように演算に要する時間を短くすることは、レイアウトパターンの入力の応答性を良くする。つまり、ＣＰＵ１２は、レイアウトパターンの入力中に占有率を算出するため、占有率の演算量が多くなる（演算時間が長くなる）と、操作者による入力装置１６の操作から、表示装置１５に対するレイアウトパターンの表示までの時間が長くなる、つまり入力に対する表示の応答性が悪くなる。しかし、本実施形態のように、占有率の演算に要する時間を短くすることで、入力に対する表示の応答性の劣化を抑えることができる。
【００７１】
次に、ＣＰＵ１２は、第２セル占有率テーブル３６ｂにおいて、更新部分の占有率が上限値を超えているか否かを判断する（ステップ４８）。
図１０（ｂ）において、枠８０内の要素のうちの１つの値が「５１」であり、上限値（＝５０）を超えている。つまり、この占有率（＝５１）の要素に対応する検証エリアにおいて、密度エラーが発生している。このため、ＣＰＵ１２は、エラー発生箇所までレイアウトパターンの入力を強制的に戻して各テーブル３５，３６を更新する（ステップ５３）。
【００７２】
図１１（ａ）に示すように、ＣＰＵ１２は、入力中のレイアウトパターンの座標値（表示装置１５に表示するためのレイアウトパターンの終点の座標値）を、入力格子に従って密度エラーが発生している占有率と上限値との差に応じて始点側の座標値に変更したレイアウトパターン７３ｃを生成し、図１１（ｂ），（ｃ）に示す第２セル面積テーブル３５ｂ及び第２セル占有率テーブル３６ｂを更新する。これにより、密度エラーが発生した要素の占有率は、占有率の上限値と等しくなる。このため、ＣＰＵ１２は、密度エラーを解消した要素に対応して図形入力禁止エリアを生成する（ステップ５１）。
【００７３】
図１１（ｃ）に示すように、密度エラーを解消した要素８１の値は、図１１（ｄ）に示す検証エリア８２により算出した占有率である。従って、この検証エリア８２内にレイアウトパターンを追加すると、要素８１の値が大きくなり、密度エラーを発生させる。このため、ＣＰＵ１２は、この検証エリア８２と同じ大きさの図形入力禁止エリアを生成する。この図形入力禁止エリアの生成により、上限値と等しい占有率の要素について、その占有率が上限値を超えることがなくなる、つまり、密度エラーの発生を防止する。
【００７４】
次に、インスタンスの一例を示して上記の処理を説明する。
第１の例として、図１２（ａ）に示すインスタンス９１を、図１２（ｂ）に示すセル９２に配置し（セルを編集）、図１２（ｃ）に示すセル９３を生成する場合について説明する。
【００７５】
インスタンス９１は、ハッチングを付したレイアウトパターン９１ａを含む。同様に、セル９２は、ハッチングを付したレイアウトパターン９２ａ〜９２ｄを含む。なお、インスタンス９１，９２内の実線は格子を示す。
【００７６】
インスタンス９１は、基準点（例えば、インスタンス９１の枠の左下頂点）に従って配置される。図１２（ｃ）に示すように、基準点をセル９２の格子上に配置した場合、セル９３は、インスタンス９１のパターン９１ａと、セル９２のパターン９２ａ〜９２ｄを含む。なお、図１２（ｃ）に示す黒丸は、インスタンス９１の基準点を示す。
【００７７】
インスタンス９１とセル９２は、それぞれ格子に１つのパターンを含む。従って、図１３（ａ）に示すように、インスタンス９１の面積テーブル３４は、レイアウトパターン９１ａに対応する格子に「１」が記憶され、レイアウトパターンを含まない格子に「０」が記憶されている。同様に、図１３（ｂ）に示すように、セル９２の面積テーブル３５ａは、レイアウトパターン９２ａ〜９２ｄに対応する格子に「１」が記憶され、レイアウトパターンを含まない格子に「０」が記憶されている。
【００７８】
図１２（ｃ）に示すように、セル９１をセル９２に配置した場合、ＣＰＵ１２は、図１３（ｃ）に示すように、対応する面積テーブル３４をセル面積テーブル３５ｂに配置する。それぞれの面積テーブルの配置は、それぞれに含まれる面積値を、インスタンス９１とセル９２の重なりに対応させるものである。例えば、インスタンス９１の基準点を、面積テーブル３４の基準点とする。なお、図では、インスタンス９１の面積テーブル３４が重ねられた部分の面積値を示していない。
【００７９】
そして、ＣＰＵ１２は、各格子の面積を合成する。この場合、ＣＰＵ１２は、インスタンス面積テーブル３４の値と、セル面積テーブル３５ａの値とを論理和演算して対応する格子の面積値としてセル面積テーブル３５ａを更新する。重なりのない部分の面積値は更新前の面積テーブル３５ａの値となる。なお、図１３では、更新後のセル面積テーブルに、更新前のセル面積テーブルと同じ符号を付している。
【００８０】
インスタンス９１は、基準点対して、回転、反転が指定され、配置される。
図１４（ａ）は、反転（図において左右方向であって、例えばＹ軸を中心とした反転）したインスタンス９１を配置した例を示す。この場合、上記と同様に、図１４（ｂ）に示すように、反転されたインスタンス面積テーブル３４がセル面積テーブル３５ａに配置し、各面積値を論理和演算し、図１４（ｃ）に示すように、セル面積テーブル３５ａを更新する。
【００８１】
図１５（ａ）は、反転（図において左右方向であって、例えばＹ軸を中心とした反転）したインスタンス９１を、更に基準点周りに回転して配置した例を示す。この場合、上記と同様に、図１５（ｂ）に示すように、反転されたインスタンス面積テーブル３４がセル面積テーブル３５ａに配置し、各面積値を論理和演算し、図１５（ｃ）に示すように、セル面積テーブル３５ａを更新する。
【００８２】
インスタンス９１を配置すると、ＣＰＵ１２は、そのインスタンス９１が配置されたセル９２の面積テーブル３５ａを、インスタンス９１の面積テーブル３４を参照して更新する。そして、ＣＰＵ１２は、更新したセル面積テーブル３５ａに基づいて占有面積を算出してセル占有率テーブル３６ａを更新する。配置したインスタンス９１に対応して占有率を算出する領域は、半導体装置全体に比べて少ないため、短時間で占有率を算出することができ、半導体装置に形成するすべてのインスタンスを配置した後に占有率を算出する方法に比べて設計時間を短縮することができる。
【００８３】
第２の例として、図１６（ａ）に示すインスタンス１０１を、図１６（ｂ）に示すセル１０２に配置し（セルを編集）、図１６（ｃ）に示すセル１０３を生成する場合について説明する。
【００８４】
インスタンス１０１は、ハッチングを付したレイアウトパターン１０１ａ，１０１ｂを含む。同様に、インスタンス１０２は、ハッチングを付したレイアウトパターン１０２ａ〜１０２ｄを含む。なお、インスタンス１０１，１０２内の実線は格子を示す。
【００８５】
インスタンス１０１は、基準点（例えば、インスタンス１０１の枠の左下頂点）に従って配置される。図１６（ｃ）に示すように、基準点をセル１０２の格子内に配置した場合、セル１０３は、インスタンス１０１のパターン１０１ａ，１０１ｂと、セル１０２のパターン１０２ａ〜１０２ｄを含む。なお、図１６（ｃ）に示す黒丸は、インスタンス１０１の基準点を示す。
【００８６】
図１７（ａ）に示す面積テーブル３４は図１６（ａ）に示すインスタンス１０１に対応する面積テーブルである。面積テーブル３４の値は、対応する格子内にレイアウトパターンが含まれるか否かである。面積テーブル３４には、レイアウトパターンを含む格子に対応して「１」が記憶され、レイアウトパターンを含まない格子に対応して「０」が記憶される。
【００８７】
図１のＣＰＵ１２は、面積テーブル３４の基準点を設定する。ＣＰＵ１２は、例えば、面積テーブル３４の基準点を、対応するインスタンス１０１の基準点とする。そして、ＣＰＵ１２は、レイアウトパターンを含む格子の頂点の座標値を算出する。図１７（ｂ）には、算出した座標値の頂点を黒丸にて示されている。例えば、格子を各軸（Ｘ軸及びＹ軸）の１単位とし、基準点を（０，０）とすると、頂点の座標値は、（１，１），（２，１），（１，２），（２，２），（１，３），（２，３）となる。
【００８８】
図１７（ｃ）に示す面積テーブル３５ａは図１６（ｂ）に示すインスタンス１０２に対応する面積テーブルである。面積テーブル３５ａの値は、対応する格子内にレイアウトパターンが含まれるか否かである。面積テーブル３５ａには、レイアウトパターンを含む格子に対応して「１」が記憶され、レイアウトパターンを含まない格子に対応して「０」が記憶される。
【００８９】
次に、ＣＰＵ１２は、図１６（ｃ）に示すインスタンス１０１とセル１０２の配置と同様に、図１８（ａ）に示すように、セル面積テーブル３５ａにインスタンス面積テーブル３４を配置する。そして、ＣＰＵ１２は、セル面積テーブル３５ａの格子に対して、インスタンス面積テーブル３４のレイアウトパターンを含む格子の頂点が含まれるか否かを判断し、頂点が含まれる格子についてはレイアウトパターンを含むとして面積値を「１」としてセル面積テーブル３５ａを更新し、頂点が含まれない格子については更新前の面積値を維持する。その結果、ＣＰＵ１２は、図１８（ｂ）に示すように、面積テーブル３５ａを更新する。
【００９０】
上記のように、セル１０２の格子位置と、そのセル１０２に配置したインスタンス１０１の格子位置が異なる場合、ＣＰＵ１２は、インスタンス１０１に対応する面積テーブル３４のレイアウトパターンを含む格子の頂点を算出し、その頂点を含むセル１０２のセル面積テーブル３５ａについて、面積値を算出してセル面積テーブル３５ａを更新する。このように、セル面積テーブル３５ａを更新することにより、セル１０２に対するインスタンス１０１の配置位置の自由度が高まる、即ち、任意の位置にインスタンス１０１を配置することができ、配線設計を容易に行うことができる。
【００９１】
インスタンス１０１を配置すると、ＣＰＵ１２は、そのインスタンス１０１が配置されたセル１０２の面積テーブル３５ａを、インスタンス１０１の面積テーブル３４を参照して更新する。そして、ＣＰＵ１２は、更新したセル面積テーブル３５ａに基づいて占有面積を算出してセル占有率テーブル３６ａを更新する。配置したインスタンス１０１に対応して占有率を算出する領域は、半導体装置全体に比べて少ないため、短時間で占有率を算出することができ、半導体装置に形成するすべてのインスタンスを配置した後に占有率を算出する方法に比べて設計時間を短縮することができる。
【００９２】
次に、図１６（ｃ）に示すようにインスタンス１０１をセル１０２に配置した場合において面積テーブル３５ａを更新する別の例を説明する。
インスタンス１０１が配置されると、図１のＣＰＵ１２は、配置されたインスタンス１０１の配置状態に応じて、対応する面積テーブル３４の値を変更した面積テーブル３４ａを生成する。ＣＰＵ１２は、インスタンス１０１に対応する面積テーブル３５をずらす方向に応じて各格子の面積値を変更する。
【００９３】
インスタンス１０１の基準点と一致する基準点の面積テーブルを第１の面積テーブルとし、基準点をずらした面積テーブルを第２の面積テーブルとする。ＣＰＵ１２は、第１の面積テーブルに対して、レイアウトパターンを含む格子の頂点の座標値を算出する。次に、ＣＰＵ１２は、第２の面積テーブルの格子のうち、算出した頂点の座標値を含む格子を抽出する。そして、ＣＰＵ１２は、その抽出した格子の面積値を、レイアウトパターンを含む値、即ち「１」に変更する。
【００９４】
例えば、図１７（ａ）に示す面積テーブル３４に対して、ＣＰＵ１２は、図１７（ｂ）に示すように、レイアウトパターンを含む格子の頂点（黒丸で示す頂点）の座標値を算出する。そして、面積テーブル３４を左下方向にずらした場合、各頂点は、それぞれ頂点を左下の頂点とする格子に含まれることになる。従って、ＣＰＵ１２は、それらの頂点を含む６つの格子の面積値を、レイアウトパターンを含むことを示す値「１」に変更した面積テーブル３４ａ（図１９（ａ）参照）する。
【００９５】
上記の処理は、格子を構成する２つの軸（Ｘ軸及びＹ軸）について、面積テーブルをずらした方向と逆の方向に、レイアウトパターンを含むことを示す面積値を拡張することといえる。
【００９６】
次に、ＣＰＵ１２は、図１９（ｂ）に示すように、生成した面積テーブル３４ａ（第２の面積テーブル）を、セル１０２の面積テーブル３５ａに配置し、両面積テーブル３４ａ，３５ａの面積値を合成（論理和演算）して面積テーブル３５ａを更新する。
【００９７】
上記のように、セル１０２の格子位置と、そのセル１０２に配置したインスタンス１０１の格子位置が異なる場合、ＣＰＵ１２は、インスタンス１０１に対応する面積テーブル３４のレイアウトパターンを含む格子の面積値を、セル面積テーブル３５ａの格子に対応して基準点をずらした面積テーブル３４ａを生成し、その面積テーブル３４ａの面積値を参照してセル面積テーブル３５ａを更新する。このように、セル面積テーブル３５ａを更新することにより、セル１０２に対するインスタンス１０１の配置位置の自由度が高まる、即ち、任意の位置にインスタンス１０１を配置することができ、配線設計を容易に行うことができる。
【００９８】
ＣＰＵ１２は、上記のようにしてインスタンスをセルに配置し、セル面積テーブル３５ａ及びセル占有率テーブル３６ａを更新する。そして、ＣＰＵ１２は、更新したセル占有率テーブルの値が上限値を超えているか否かを判断し（図４のステップ４８）、上限値を超えている、つまりエラーの場合にはセル面積テーブル３５ａ及びセル占有率テーブル３６ａをインスタンスの配置前の状態に戻す（図４のステップ５３）。エラーが発生した場合に、その検証処理の直前の入力や処理による変更をセル面積テーブル３５ａ及びセル占有率テーブル３６ａから削除する。このエラー発生箇所まで入力を戻すことにより、エラー発生を自動的に解消するとともに、エラーの発生を操作者に示すことが可能となる。
【００９９】
以上記述したように、本実施の形態によれば、以下の効果を奏する。
（１）設計装置１１の記憶装置１４には、半導体装置を検証ステップの格子にて区画した各領域に含まれるレイアウトパターンの面積がそれぞれ格納されるセル面積テーブル３５と、移動される検証エリアの位置に対応し、各検証エリアには所定数の領域が含まれ、検証エリアに対してその検証エリアに含まれるレイアウトパターンの占有率が、各検証エリアに対応して格納されるセル占有率テーブル３６を含む面積ＤＢ３３が記憶される。図形ＤＢ３２にはインスタンスの面積テーブル３４が含まれる。ＣＰＵ１２は、配置されたインスタンスの面積テーブル３４に従って編集対象のセル面積テーブル３５を変更し、そのセル面積テーブルに従ってセル占有率テーブル３６を更新する。従って、配置したインスタンスに対応して占有率を算出するため、その領域は、半導体装置全体に比べて少なく、短時間で占有率を算出することができ、半導体装置に形成するすべてのレイアウトパターンを入力した後に占有率を算出する方法に比べて設計時間を短縮することができる。
【０１００】
（２）ＣＰＵ１２は、インスタンスの配置位置に応じて、セル面積テーブル３５ａに含まれる格子のうち、面積値を更新する格子を変更するようにした。その結果、セル９２，１０２に対するインスタンス９１，１０１の配置位置の自由度が高まる、即ち、任意の位置にインスタンス９１，１０１を配置することができ、配線設計を容易に行うことができる。
【０１０１】
（３）セル面積テーブル３５及びセル占有率テーブル３６は、それぞれ半導体装置の配線層のうち、密度基準が設定された配線層に対応するテーブルを含む。ＣＰＵ１２は、配置されたインスタンスの面積テーブル３４に対応するテーブルを更新するようにした。その結果、全ての配線層をチェックする場合と比べてチェックに要する時間が短くなり、設計時間を短縮することができる。
【０１０２】
（４）設計装置１１の記憶装置１４には、半導体装置を検証ステップの格子にて区画した各領域に含まれるレイアウトパターンの占有面積がそれぞれ格納されるセル面積テーブル３５と、移動される検証エリアの位置に対応し、各検証エリアには所定数の領域が含まれ、検証エリアに対してその検証エリアに含まれるレイアウトパターンの占有率が、各検証エリアに対応して格納されるセル占有率テーブル３６とが記憶される。ＣＰＵ１２は、レイアウトパターンの入力中において、セル面積テーブル３５及びセル占有率テーブル３６を更新する。従って、入力中のレイアウトパターンに対応して占有率を算出する領域は、半導体装置全体に比べて少ないため、短時間で占有率を算出することができ、半導体装置に形成するすべてのレイアウトパターンを入力した後に占有率を算出する方法に比べて設計時間を短縮することができる。
【０１０３】
（５）設計装置１１には検証ステップとして互いに異なる第１及び第２検証ステップが設定され、セル面積テーブル３５及びセル占有率テーブル３６は、第１及び第２検証ステップに対応してそれぞれ第１及び第２セル面積テーブル３５ａ，３５ｂ，第１及び第２セル占有率テーブル３６ａ，３６ｂから構成される。ＣＰＵ１２は、値が大きな第１検証ステップから値の小さな第２検証ステップへと変更し、ステップ４５では各検証ステップのセル面積テーブル３５ａ，３５ｂを更新し、ステップ４７ではその時の検証ステップに対応するセル占有率テーブル３６ａ，３６ｂを更新する。従って、値の大きな第１検証ステップに対応する第１セル占有率テーブル３６ａを更新した後、値の小さな検証ステップに対応する第２セル占有率テーブル３６ｂを更新することで、第２セル占有率テーブル３６ｂにおいて、占有率が上限値を超えないと判定される部分については占有率の算出を省略することが可能となる、占有率の算出に要する時間を短縮することができる。更に、値が小さな検証ステップに対応する第２セル占有率テーブル３６ｂを更新ことで、小さな領域に対応する占有率が算出され、必用な精度にて占有率を算出することができ、従来に比べて精度の低下を抑えることができる。
【０１０４】
（６）設計装置１１には上限値に応じた保証占有率が設定される。ＣＰＵ１２は、第１検証ステップに対応する第１セル占有率テーブル３６ａを対象テーブルとし、その対象テーブルの占有率を保証占有率と比較し、占有率が保証占有率を超えているエリアを抽出する。そして、ＣＰＵ１２は、検証ステップを第２検証ステップに更新し、第２占有率テーブルを対象テーブルとしてその対象テーブルにおいて先に抽出したエリア内の対象部分について占有率を算出して第２占有率テーブルを更新するようにした。上限値に応じた保証占有率を超える部分は、占有率が上限値を超える確率が高い、即ち密度エラーが発生する候補の部分である。従って、第１セル占有率テーブル３６ａ、第２セル占有率テーブル３６ｂと、順次切り換え、エラー候補の箇所を段階的に絞り込むことで、第２セル占有率テーブル３６ｂにおいて、入力するレイアウトパターンの占有面積が影響する部分の全ての占有率を算出する場合に比べ、第２セル占有率テーブル３６ｂの更新に要する時間が短くなり、設計時間を短縮することができる。
【０１０５】
（７）ＣＰＵ１２は、更新されたセル占有率テーブル３６（３６ａ，３６ｂ）の更新部分の占有率が上限値を超えていると判断した場合にレイアウトパターンの入力を強制的に戻してセル面積テーブル３５及びセル占有率テーブル３６を更新するようにした。そのため、占有率が上限値を超えた密度エラーを自動的に解消することができる。
【０１０６】
（８）ＣＰＵ１２は、入力装置１６からの信号に基づいて、入力中のレイアウトパターンが検証ステップの格子を越えているか否か、及びレイアウトパターンの入力が終了したか否か、を判断し、入力中のレイアウトパターンが前記検証ステップの格子を越えた場合、又はレイアウトパターンの入力が終了した場合にそのレイアウトパターンに占有面積計算、占有率計算を行うようにした。従って、検証ステップの格子に従ってレイアウトパターンの入力中にトリガが発生するため、占有率を算出する対象となるレイアウトパターンの占有面積が検証ステップに応じており、その時の占有率を算出する演算量が少なくなり、レイアウトパターンの入力に対する影響を少なくすることができる、つまり、操作者においてレイアウトパターンを入力するための操作性の劣化を抑えることができる。
【０１０７】
（９）ＣＰＵ１２は、セル占有率テーブル３６の占有率が上限値と等しい場合に、その上限値と等しい占有率に対応するエリアに対して図形入力禁止エリアを生成するようにした。その結果、上限値と等しい占有率の要素について、その占有率が上限値を超えることがなくなる、つまり、密度エラーの発生を防止することができる。
【０１０８】
尚、前記実施形態は、以下の態様に変更してもよい。
・上記実施形態では、セル面積テーブル３５を、レイアウトパターンを形成する領域に対して、１つの領域に形成されたレイアウトパターンの占有面積を格納する第１セル面積テーブル３５ａと、複数の領域に形成されたレイアウトパターンの占有面積を格納する第２セル面積テーブル３５ｂとから構成したが、互いに格納する領域数が異なるｎ個（３つ以上）の面積テーブルにより構成し、配線密度の検証をｎ段階にて実施するようにしてもよい。また、セル占有率テーブル３６を、ｎ個（３つ以上）の占有率テーブルにより構成し、配線密度の検証をｎ段階にて実施するようにしてもよい。
【０１０９】
・上記実施形態では、完成した１Ｃｈｉｐ全体のレイアウトデータやマクロレベルのレイアウトデータに対して、配線密度のプロセス製造基準の高い側だけでなく、低い側も配線密度の検証をしてもよい。
【０１１０】
・上記実施形態では、新たなレイアウトデータを生成する場合について説明したが、追加又は修正が必用なレイアウトデータを編集する場合に適用しても良い。この場合、図３のステップ４１における初期化処理において、ＣＰＵ１２は、記憶装置１４に格納されたレイアウトデータを読み込み、そのレイアウトデータのレイアウトパターンに基づいて、セル面積テーブル３５及びセル占有率テーブル３６の値を設定する。このようにしても、追加又は修正するレイアウトパターンに係る密度チェックを容易に行うことができる。
【０１１１】
・上記実施形態では、占有率が上限値を越えたか否かを判断するようにしたが、下限値を設定し、占有率が下限値を下回ったか否かを判定するようにしてもよい。下限値は、製造プロセスの基準値（必要とするレイアウトパターンの密度の最小値）である。判定結果に基づき、レイアウトパターンが必要な領域にレイアウトパターンを追加することができるようになり、設計後に下限値をチェックする手順と比べて設計時間を短縮することができるようになる。
【０１１２】
上記各実施形態に関し、以下の付記を開示する。
（付記１）
半導体装置のレイアウトデータを生成する設計装置の中央処理装置にて実行される配線設計方法であって、
記憶装置には、インスタンスに含まれるレイアウトパターンに対応する面積値が格納されたインスタンス面積テーブルが記憶され、
前記中央処理装置が実行する処理は、
インスタンスが配置されたセルのセル面積テーブルを、前記インスタンス面積テーブルに従って更新するステップと、
更新されたセル面積テーブルに基づいて前記インスタンスが配置されたセルに対応するセル占有率テーブルを更新するステップと、
を含む、
ことを特徴とする配線設計方法。
（付記２）
前記中央処理装置は、
前記インスタンス面積テーブルの値と、前記セル面積テーブルの値とを論理和演算してセル面積テーブルを更新する、
ことを特徴とする付記１に記載の配線設計方法。
（付記３）
前記中央処理装置は、
前記インスタンスの配置位置に応じて、前記セル面積テーブルに含まれる格子のうち、面積値を更新する格子を変更する、
ことを特徴とする付記２に記載の配線設計方法。
（付記４）
前記中央処理装置は、
前記インスタンス面積テーブルの格子のうち、レイアウトパターンを含む格子の頂点の座標値を算出し、その算出した頂点の座標値を含むセル面積テーブルの格子の面積値を更新する、
ことを特徴とする付記３に記載の配線設計方法。
（付記５）
前記中央処理装置は、
前記インスタンス面積テーブルを、前記インスタンスの配置位置に応じてずらし、そのずらした方向に応じてインスタンス面積テーブルに含まれる格子を拡張した第２の面積テーブルを生成し、その第２の面積テーブルの面積値とセル面積テーブルの面積値とを論理和演算してセル面積テーブルを更新する、
ことを特徴とする付記３に記載の配線設計方法。
（付記６）
前記半導体装置の設計規則に応じて移動させた検証エリアの占有率が設計規則を満足するか否かを検証するステップを含む、
ことを特徴とする付記１〜５のうちの何れか１項に記載の配線設計方法。
（付記７）
前記設計装置には検証ステップとして互いに異なる複数の検証ステップが設定され、
前記面積テーブル及び前記占有率テーブルは、各検証ステップに対応してそれぞれ複数のテーブルを含み、
前記中央処理装置は、
対象とする検証ステップを、大きな検証ステップから小さな検証ステップへと順次変更し、
各検証ステップのセル面積テーブルを更新し、
対象する検証ステップに対応するセル占有率テーブルを更新する、
ことを特徴とする付記１〜６のうちの何れか１項に記載の配線設計方法。
（付記８）
前記セル面積テーブル及び前記セル占有率テーブルは、それぞれ半導体装置の配線層のうち、密度基準が設定された配線層に対応するテーブルを含み、
入力されたインスタンスの面積テーブルに対応するテーブルを更新する、
ことを特徴とする付記１〜７のうちの何れか１項に記載の配線設計方法。
（付記９）
前記中央処理装置が実行する処理は、
更新された前記占有率テーブルの更新部分の占有率が上限値を超えているか否かを判断するステップと、
占有率が上限値を超えていると判断した場合に前記面積テーブル及び前記占有率テーブルをインスタンス配置前の状態に戻すステップと、
を含むこと、を特徴とする付記１〜８のうちの何れか１つに記載の配線設計方法。
（付記１０）
半導体装置のレイアウトデータを生成する設計装置であって、
記憶装置には、インスタンスに含まれるレイアウトパターンに対応する面積値が格納されたインスタンス面積テーブルが記憶され、
前記設計装置の中央処理装置が実行する処理は、
インスタンスが配置されたセルのセル面積テーブルを、前記インスタンス面積テーブルに従って更新するステップと、
更新されたセル面積テーブルに基づいて前記インスタンスが配置されたセルに対応するセル占有率テーブルを更新するステップと、
を含む、
ことを特徴とする設計装置。
（付記１１）
半導体装置のレイアウトデータを生成するために設計装置の中央処理装置が実行するプログラムであって、
記憶装置には、インスタンスに含まれるレイアウトパターンに対応する面積値が格納されたインスタンス面積テーブルが記憶され、
前記中央処理装置が実行する処理は、
インスタンスが配置されたセルのセル面積テーブルを、前記インスタンス面積テーブルに従って更新するステップと、
更新されたセル面積テーブルに基づいて前記インスタンスが配置されたセルに対応するセル占有率テーブルを更新するステップと、
を含む、
ことを特徴とするプログラム。
【符号の説明】
【０１１３】
１１ 設計装置
１２ 中央処理装置（ＣＰＵ）
３４（３４ａ，３４ｂ） インスタンス面積テーブル
３５（３５ａ，３５ｂ） セル面積テーブル
３６（３６ａ，３６ｂ） セル占有率テーブル
【技術分野】
【０００１】
半導体装置の配線設計方法、設計装置及びプログラムに関するものである。
【背景技術】
【０００２】
近年の半導体装置は素子数の増大や高集積化が進められ、それに伴って配線層の多層配線化が進んでいる。一方、各配線層において、レイアウトパターンの密度に偏り、即ち粗密が生じる。レイアウトパターンの粗密は、上方の配線層に段差を生じさせる。
【０００３】
この結果、表面に近い配線層では、下層の累積的な段差により、上層配線と下層配線を接続するビアの接続不良などの問題が発生する。この問題に対し、化学的機械的研磨（ＣＭＰ:Chemical Mechanical Polishing）に代表される研磨技術によるウェハ表面の平坦化や、ダミーパターンの追加による配線密度差の低減が行われている。
【０００４】
しかし、レイアウトパターンの密度が高い部分では、研磨により必用以上にレイアウトパターンが削れてしまう場合がある。このため、レイアウトパターンの最大密度（占有率）を設定し、半導体装置の設計処理では、図２０に示すように、レイアウトデータにおけるレイアウトパターンの密度を検証している。
【０００５】
まず、ステップ１２１において、レイアウトパターン（図形）を入力する。即ち設計装置は、ユーザが操作するマウスなどの入力手段の情報に従って、レイアウトパターンや素子等のレイアウトパターンのデータを生成し、そのデータをファイル１２６に格納する。ステップ１２２において、設計装置は、全レイアウトパターンの入力が終了したか否かを判断し、終了していない場合にはステップ１２１に移行する。全レイアウトパターンの入力が終了した場合、ステップ１２３に移行し、ファイル１２６のレイアウトデータに対して配線密度の検証を実施する。ステップ１２３において、設計装置は、ファイル１２６に格納したレイアウトデータを読み出し、このレイアウトデータの配線密度を算出する。
【０００６】
この時、設計装置は、図２１に実線で示すように、レイアウトパターンＬ１〜Ｌ７のうち、所定サイズの占有率計算エリア１３１内に含まれるレイアウトパターンの占有面積と、占有率計算エリア１３１から配線密度を算出する。次に、占有率計算エリア１３１を一定のステップ（以下、検証ステップ）で移動させる。移動させた占有率計算エリアを破線で示している。そして、この位置において、配線密度を算出する。同様に、占有率計算エリア１３１を一点鎖線，二点鎖線で示す位置に移動させ、それぞれの位置における配線密度を算出する。図２１では、各占有率計算エリア１３１の位置が判りやすいように図面における上下方向にずらしている。
【０００７】
次に、図２０に示すステップ１２４において、設計装置は、ステップ１２３で算出した配線密度と配線密度のプロセス製造基準とを比較し、密度エラーが発生しているか否かを判断する。密度エラーが発生していない場合には処理を終了し、密度エラーが発生している場合にはステップ１２５に移行する。ステップ１２５において、設計装置は、ファイル１２６から読み出したレイアウトデータを表示装置に表示し、ユーザにより編集されたレイアウトデータをファイル１２６に格納した後、再度密度を検証するべくステップ１２３に移行する。
【０００８】
上記記載の検証フローでは、ステップ１２３における配線密度の検証に半導体装置全体のレイアウトデータが必用である。このため、配線密度の検証の結果、レイアウトデータの一部を修正した場合であっても、半導体装置全体のレイアウトデータに対して検証を行うため、レイアウトデータの検証に多くの時間を費やし、開発期間が増大する。また、レイアウトデータの修正後に行う検証で密度エラーが発生した場合には、レイアウトパターン修正を行った後、再度配線密度の検証を行わなければならない。このため、工程の手戻りが発生し、更に修正ミスなどによって手戻り工数が増加する。図１３に示すように、配線密度の算出において、占有率計算エリア１３１の検証ステップを小さく設定した場合には検証時間が増大し、検証ステップを大きく設定した場合には検証漏れが発生し、後工程からの手戻りが発生する場合がある。
【０００９】
上記記載の問題に対して、例えば、特許文献１は、検証を行おうとするマクロブロックもしくはチップのレイアウト内部に所定のレイアウトデータ率を持つ仮想（ダミー）データを、一時的に前記レイアウトに加え（ステップＳ２）、もしくは前記レイアウトから差し引くことにより、仮想的なレイアウトである仮想レイアウトを形成し、このように作成された仮想レイアウトに対して配線密度の検証を行い（ステップＳ３）、レイアウト完成前に配線密度の分布を求めている。これにより、レイアウトデータの完成前に配線密度の検証をすることができ、マクロブロック単位でも配線密度検証ができるため、開発期間の増大を抑えることができる。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】特開２００３−６７４４１号公報
【発明の概要】
【発明が解決しようとする課題】
【００１１】
しかしながら、上記特許文献１のレイアウト密度検証方法では、仮想データをレイアウトに加え、もしくは差し引き、仮想レイアウトを生成する必用があり、手間がかかるという問題がある。また、仮想データをレイアウトに加え、もしくは差し引くため、仮想データと実際のレイアウトパターンとが相違し、実際のレイアウトパターンの密度検証を行っていない。この結果、密度誤差が生じるおそれがあり、手戻りが発生する場合があり、設計時間を短縮する妨げとなる場合があった。
【００１２】
開示された配線設計方法は、設計時間の短縮を図ることを目的とする。
【課題を解決するための手段】
【００１３】
配線設計方法の一観点によれば、記憶装置には、インスタンスに含まれるレイアウトパターンに対応する面積値が格納されたインスタンス面積テーブルが記憶され、中央処理装置が実行する処理は、インスタンスが配置されたセルのセル面積テーブルを、インスタンス面積テーブルに従って更新するステップと、更新されたセル面積テーブルに基づいてインスタンスが配置されたセルに対応するセル占有率テーブルを更新するステップと、を含む。
【発明の効果】
【００１４】
開示された方法によれば、設計時間の短縮を図ることができる。
【図面の簡単な説明】
【００１５】
【図１】配線設計装置の概略構成図である。
【図２】配線設計処理の概略フロー図である。
【図３】配線設計処理のフロー図である。
【図４】配線設計処理のフロー図である。
【図５】保証占有率の説明図である。
【図６】（ａ）〜（ｃ）は配線設計処理の説明図である。
【図７】（ａ）〜（ｃ）は配線設計処理の説明図である。
【図８】（ａ）〜（ｃ）は配線設計処理の説明図である。
【図９】（ａ）〜（ｃ）は配線設計処理の説明図である。
【図１０】（ａ），（ｂ）は配線設計処理の説明図である。
【図１１】（ａ）〜（ｄ）は配線設計処理の説明図である。
【図１２】（ａ）〜（ｃ）は配線設計処理の説明図である。
【図１３】（ａ）〜（ｄ）は配線設計処理の説明図である。
【図１４】（ａ）〜（ｃ）は配線設計処理の説明図である。
【図１５】（ａ）〜（ｃ）は配線設計処理の説明図である。
【図１６】（ａ）〜（ｃ）は配線設計処理の説明図である。
【図１７】（ａ）〜（ｃ）は配線設計処理の説明図である。
【図１８】（ａ），（ｂ）は配線設計処理の説明図である。
【図１９】（ａ），（ｂ）は配線設計処理の説明図である。
【図２０】従来の配線設計処理のフロー図である。
【図２１】従来の配線設計処理の説明図である。
【発明を実施するための形態】
【００１６】
以下、一実施形態を図１〜図１１に従って説明する。
図１に示すように、半導体装置のレイアウトデータを生成するための設計装置（コンピュータ）１１は一般的なＣＡＤ（Computer Aided Design ）装置からなり、中央処理装置（以下、ＣＰＵという）１２、メモリ１３、記憶装置１４、表示装置１５、入力装置１６、及び、ドライブ装置１７により構成され、それらはバス１８を介して相互に接続されている。
【００１７】
ＣＰＵ１２は、メモリ１３を利用してプログラムを実行し、半導体装置のレイアウト設計等の必要な処理を実現する。プログラムは、ＣＰＵ１２を半導体装置のレイアウトデータを生成する設計装置としての各種手段として機能させるためのものである。メモリ１３には、各種処理を提供するために必要なプログラムとデータが格納され、メモリ１３としては、通常、キャッシュ・メモリ、システム・メモリおよびディスプレイ・メモリを含む。
【００１８】
表示装置１５は、レイアウト表示、パラメータ入力画面等の表示に用いられ、これにはＣＲＴ，ＬＣＤ，ＰＤＰ等が用いられる。入力装置１６は、ユーザからの要求や指示，パターン，パラメータの入力に用いられ、これにはキーボードおよびマウス装置（図示せず）等が用いられる。
【００１９】
コンピュータ１１は、レイアウトデータに基づき半導体装置に形成するレイアウトパターン（図形）を表示装置１５に表示させる。そして、コンピュータ１１は、ユーザが操作する入力装置１６からの信号に従って、表示装置１５上のレイアウトパターンの追加，削除を行うとともに、レイアウトデータに対してパターンデータの追加，削除を行う。
【００２０】
記憶装置１４は、通常、磁気ディスク装置、光ディスク装置、光磁気ディスク装置を含む。この記憶装置１４には、図２〜図４に示す各ステップからなる半導体装置（半導体集積回路装置）のレイアウトデータを生成するためのプログラムデータと、プログラムの実行に必要なデータ、プログラムの実行により生成されるデータが格納される。ＣＰＵ１２は、入力装置１６による指示に応答しているプログラムデータをメモリ１３へ転送し、それを実行する。
【００２１】
ＣＰＵ１２が実行するプログラムデータは、記録媒体１９にて提供される。ドライブ装置１７は、記録媒体１９を駆動し、その記憶内容にアクセスする。ＣＰＵ１２は、ドライブ装置１７を介して記録媒体１９からプログラムデータを読み出し、それを記憶装置１４にインストールする。
【００２２】
記録媒体１９としては、磁気テープ（MT）、メモリカード、フレキシブルディスク、光ディスク（CD-ROM,DVD-ROM,… ）、光磁気ディスク（MO,MD,…）等、任意のコンピュータ読み取り可能な記録媒体を使用することができる。この記録媒体１９に、上述のプログラム，データを格納しておき、必要に応じて、メモリ１３にロードして使用することもできる。
【００２３】
尚、記録媒体１９には、通信媒体を介してアップロード又はダウンロードされたプログラムデータを記録した媒体、ディスク装置を含む。更に、コンピュータによって直接実行可能なプログラムを記録した記録媒体だけでなく、いったん他の記録媒体（ハードディスク等）にインストールすることによって実行可能となるようなプログラムを記録した記録媒体や、暗号化されたり、圧縮されたりしたプログラムを記録した記録媒体も含む。
【００２４】
次に、配線密度を考慮したレイアウト検証方法の概要を、図２のフローチャートに従って説明する。
図１のＣＰＵ１２は、図２に示すステップ２１〜２２の処理を実行することで、半導体装置を形成するためのレイアウトデータ３１を生成する手段と、レイアウトデータ３１に含まれるレイアウトパターンの密度を検証する手段として機能する。このレイアウトデータ３１は図１に示す記憶装置１４に記憶される。なお、レイアウトデータ３１は、他の配線設計装置等により作成されたものであってもよい。
【００２５】
まず、ステップ２１において、ＣＰＵ１２は、図形生成処理を実行する。図形生成処理は、所定形状のレイアウトパターンを入力する入力処理と、入力済のレイアウトパターンの形状を変更する編集処理を含む。ＣＰＵ１２は、図形生成処理において生成したレイアウトパターンの形状やレイアウトパターンを形成する層などの情報を含むレイアウトデータ３１を生成する。レイアウトパターンの入力のために必用な処理と、レイアウトデータ３１に含まれるレイアウトパターンの編集に必用な処理はほぼ同じである。
【００２６】
ＣＰＵ１２は、表示装置１５に、レイアウトデータに基づくレイアウトパターンを表示するとともに、ユーザが操作する入力装置１６からの信号に基づいて、入力中のレイアウトパターンもしくは編集中のレイアウトパターンを表示する。そして、ユーザがレイアウトパターンの入力確定を指示すると、ＣＰＵ１２は、確定されたレイアウトパターンをレイアウトデータ３１に格納する。
【００２７】
この図形生成処理において、ＣＰＵ１２は、図形データベース（図形ＤＢ）３２を参照する。図形ＤＢ３２は、図１に示す記憶装置１４に格納されている。図形ＤＢ３２は、例えばライブラリデータであって、配線等を形成するためのポリゴンデータ、素子の形状を示すデータ、インスタンスの情報（大きさ、含まれるレイアウトパターン、面積テーブル等）、を含む。
【００２８】
例えば、ＣＰＵ１２は、ユーザの指定に従ってポリゴンデータを図形ＤＢ３２から読出し、そのポリゴンデータの頂点を変更することにより所望の配線層のレイアウトパターンを形成する。配線層は、半導体装置を形成するパターンを形成する層である。レイアウトパターンは、所定の配線層に形成するための情報を有している。また、ＣＰＵ１２は、ユーザの指定に従ってインスタンスを図形ＤＢ３２から読み出し、そのインスタンスを配置することにより、インスタンスに含まれるレイアウトパターンを形成する。インスタンスに含まれるレイアウトパターンは、直接的に入力されるレイアウトパターンと同様に、所定の配線層に形成するための情報を有している。なお、パターンを形成する配線層を指定する情報（層情報）は、インスタンスの情報を記憶したライブラリに含まれる場合もある。
【００２９】
更に、ＣＰＵ１２は、この図形入力・編集処理において、処理中（入力中もしくは編集中）のレイアウトパターンに基づいて、面積データベース（面積ＤＢ）３３を更新する。面積ＤＢ３３は、図１に示す記憶装置１４（又はメモリ１３）に格納される。ＣＰＵ１２は、面積ＤＢ３３に基づいて、処理中のレイアウトパターンに係る層について配線密度の検証を実行し、処理中のレイアウトパターンが含まれる検証領域において密度エラー発生しているか否かを判断する。そして、ＣＰＵ１２は、密度エラーが発生している場合にその旨を表示装置１５に表示するとともに、処理中のレイアウトパターンに対する編集制御を行う。つまり、ＣＰＵ１２が図形入力・編集処理を行うステップ２１は、配線密度の検証を行うサブステップ２１ａと、エラー表示・編集制御を行うサブステップ２１ｂとを含む。
【００３０】
密度エラーが発生することなくレイアウトパターンを確定すると、ＣＰＵ１２はステップ２１からステップ２２に移行し、そのステップ２２において、全レイアウトパターンの入力が終了したか否かを判断する。全レイアウトパターンの入力が終了していない場合、ＣＰＵ１２は、ステップ２１に移行し、図形生成処理を実行する。全レイアウトパターンの入力が終了した場合、ＣＰＵ１２は、配線密度を考慮したレイアウト検証を終了する。
【００３１】
次に、上記のステップ２１における図形生成処理の一例を説明する。
まず、図３に示すステップ４１において、ＣＰＵ１２は、図２の面積ＤＢ３３に含まれるセル面積テーブル３５とセル占有率テーブル３６を初期化する。例えば、新たなレイアウトデータを生成する場合、ＣＰＵ１２は、セル面積テーブル３５とセル占有率テーブル３６をそれぞれクリア、つまり各テーブル３５，３６を構成する要素の値を「０」にする。各テーブル３５，３６は、検証ステップに応じたサブテーブルを有している。従って、ステップ４１において、ＣＰＵ１２は、各テーブル３５，３６のサブテーブルを初期化する。
【００３２】
上記したように、レイアウトパターンは、半導体装置の配線層に形成されるため、セル面積テーブル３５及びセル占有率テーブル３６は、配線層に応じた複数のテーブルを含む。更に、所定の領域（検証エリア）におけるレイアウトパターンの密度を検証するために複数の検証ステップが設定されている。従って、セル面積テーブル３５及びセル占有率テーブル３６は、配線層毎に、検証ステップに応じた複数のテーブルを有している。
【００３３】
設計装置１１にはレイアウトデータの配線密度を検証する検証エリアを移動させる複数の検証ステップが設定されている。本実施形態において、設計装置１１には、検証ステップとして、所定値の第１検証ステップと、その第１検証ステップよりも小さな値の第２検証ステップが設定されている。本実施形態において、設定する各検証ステップＸ軸方向及びＹ軸方向の大きさは、本設計装置１１により生成するレイアウトパターンの最小サイズ、即ち入力ステップのＸ軸方向及びＹ軸方向の値に対応している。第１検証ステップはＸ軸方向及びＹ軸方向ともに入力ステップの整数倍（例えば２倍）に設定され、第２検証ステップは入力ステップの等倍（１倍）に設定されている。
【００３４】
ＣＰＵ１２は、大きな値から小さな値へと検証ステップを変更し、レイアウトパターンに対する密度チェック処理等を実行する。即ち、ＣＰＵ１２は、先ず第１検証ステップにて密度チェックを行い、次に、第２検証ステップに変更して密度チェックを行う。この第２検証ステップによる密度チェックにおいて、ＣＰＵ１２は、第１検証ステップにて行った密度チェックの結果に基づいて、密度違反の可能性が高い部分を対象領域とし、この対象領域について第２検証ステップによる密度チェックを行う。即ち、第２検証ステップによる密度チェックを行う領域を予め絞り込むことで、密度チェックに要する処理時間（演算時間）が少なくなり、チェックに要する時間を短縮することができる。
【００３５】
セル面積テーブル３５は、２つの検証ステップに応じたサブテーブル３５ａ，３５ｂを含む（図６，７参照）。即ち、セル面積テーブル３５は、第１検証ステップに対応する第１セル面積テーブル３５ａ（図６（ｂ）参照）と、第２検証ステップに対応する第２セル面積テーブル３５ｂ（図７（ｂ）参照）とを含む。
【００３６】
セル面積テーブル３５（３５ａ、３５ｂ）に格納された値は、各テーブル３５ａ，３５ｂに対応する検証ステップの格子、及びその格子内に生成されたレイアウトパターンの占有面積に対応する。例えば、Ｘ軸及びＹ軸のサイズが入力ステップと等しい格子の面積を「１」とした場合、第１検証ステップはＸ軸方向及びＹ軸方向において入力ステップの２倍に設定されているため、第１検証ステップの格子内に生成されるレイアウトパターンの占有面積は「１」〜「４」うちの何れかとなり、第２検証ステップは入力ステップと等倍に設定されているため、第２検証ステップの格子内に生成されるレイアウトパターンの占有面積は「１」となる。従って、第１検証ステップに対応する第１セル面積テーブル３５ａの各要素は、レイアウトパターンが形成されていない場合の値「０」と、格子内に形成されるレイアウトパターンの占有面積「１」〜「４」の何れかの値となる。第２検証ステップに対応する第２セル面積テーブル３５ｂの各要素は、レイアウトパターンが形成されていない場合の値「０」と、レイアウトパターンが形成されている場合の値「１」の何れかとなる。
【００３７】
同様に、セル占有率テーブル３６は、２つの検証ステップに応じたサブテーブル３６ａ，３６ｂを含む（図６，７参照）。即ち、セル占有率テーブル３６は、第１検証ステップに対応する第１セル占有率テーブル３６ａ（図６（ｃ）参照）と、第２検証ステップに対応する第２セル占有率テーブル３６ｂ（図７（ｃ）参照）とを含む。
【００３８】
セル占有率テーブル３６（３６ａ，３６ｂ）の値は、各値に対応する位置の検証エリアにおいて、その検証エリアの面積と、その検証エリア内に生成されたレイアウトパターンの占有面積との比を示す。例えば、検証エリアの縦横、つまりＸ軸方向及びＹ軸方向のサイズをそれぞれ入力ステップ（第２検証ステップ）の１０倍（第１検証ステップの５倍）に設定する。従って、１００個の格子からなる検証エリアが設定される。そして、検証エリアの総項指数と、検証エリア内においてレイアウトパターンが形成された格子の数との比が、検証エリアの位置に対応する要素の値としてセル占有率テーブル３６（３６ａ，３６ｂ）に格納される。一例として、検証エリアに含まれる１００個の格子のうちの１個にレイアウトパターンを形成した場合、対応するセル占有率テーブル３６ａ，３６ｂの値はそれぞれ「１（％）」となる。別の例として、検証エリアを構成する１００個の格子のうちの５０個にレイアウトパターンを形成した場合、対応するセル占有率テーブル３６ａ，３６ｂの値はそれぞれ「５０（％）」となる。
【００３９】
レイアウトデータのレイアウトパターンと、セル面積テーブル３５（３５ａ，３５ｂ）及びセル占有率テーブル３６（３６ａ，３６ｂ）の関係を図８に従って説明する。
図８（ａ）に示すように、表示装置１５の画面にはレイアウトパターンＰ２（ハッチングを付した部分）が表示されている。このレイアウトパターンＰ２は、設計装置１１には所定の入力ステップに応じた入力格子（図において一点鎖線で示す格子）が設定されている。そして、レイアウトパターンＰ２は、設定された入力格子のうち、図８（ａ）に示す格子６１ａ，６１ｂに形成されている。上記したように、第１検証ステップは入力ステップの２倍に設定されている場合、その第１検証ステップに対応する第１セル面積テーブル３５ａの１つの要素の値は、隣接する４つの格子（図８（ａ）において格子６１ａ，６１ｂ，６１ｃ，６１ｄ）に形成されたレイアウトパターンの占有面積となる。１つの格子に形成されたレイアウトパターンの占有面積を「１」とすると、図８（ａ）に示すレイアウトパターンＰ２の場合、図８（ｂ）に示すように、要素６２の値が「２」となる。
【００４０】
レイアウトデータの密度チェックのために、検証エリアＶＡを設定する。ＣＰＵ１２は、検証エリアＶＡにおいてレイアウトパターンＰ２が占める占有面積の割合（占有率）を算出し、その占有率を検証エリアＶＡの位置に対応して第１セル占有率テーブル３６ａに格納する。例えば、図８（ａ）に示すように、１００個の入力格子（＝横１０×縦１０）に検証エリアＶＡが設定され、この検証エリアＶＡを第１検証ステップにて移動させ、各位置における占有率を算出し、その算出した占有率にて第１セル占有率テーブル３６ａを更新する。例えば、図８（ｂ）に示す検証エリアＶＡに対応して、図８（ｃ）に示す第１セル占有率テーブル３６ａの要素６３の占有率を「２」とする。図８（ａ）に示すレイアウトパターンＰ２の占有面積が影響する部分は、図８（ｃ）の枠６４で囲まれた部分となる。従って、ＣＰＵ１２は、この枠６４内の要素の値を「２」とする。
【００４１】
尚、形成したレイアウトパターンと、第２セル面積テーブル３５ｂ及び第２セル占有率テーブル３６ｂの関係は、上記したように、レイアウトパターンＰ２と第１セル面積テーブル３５ａ及び第１セル占有率テーブル３６ａとの関係と同じであり、ＣＰＵ１２が行う処理も、検証ステップの大きさが異なるだけであるため、説明を省略する。
【００４２】
次に、ステップ４２において、ＣＰＵ１２は、入力装置１６の操作に従ってひとつのレイアウトパターンの入力処理またはレイアウトパターンの編集処理を開始する。また、このステップ４２において、ＣＰＵ１２は、インスタンスの配置・編集処理を行う。例えば、ポリゴンを作成する始点が決定されることによりレイアウトパターンの入力処理を開始し、ポリゴンの頂点が指示されることにより編集処理を開始する。これ以降の処理において、レイアウトパターンを入力することと既存のレイアウトパターンを編集（変形）することに状態に差が生じているが、入力中のレイアウトパターンに対する検証処理（チェック）と、編集中のレイアウトパターンに対する検証処理（チェック）とは同じ内容であるため、以下の説明において、レイアウトパターンの入力に対する処理について説明する。
【００４３】
ステップ４３（トリガ判定工程）において、ＣＰＵ１２は、ステップ４２において、入力中のレイアウトパターンが第１所定の検証ステップ（例えば第１検証ステップ）の判定格子を通過したか否か、又はレイアウトパターンの入力を終了したか否かを判断する。また、ＣＰＵ１２は、このステップ４３において、インスタンスの配置を終了したか否かを判断する。ＣＰＵ１２は、入力レイアウトパターンが格子を通過せず、且つレイアウトパターンの入力が終了されていない場合にステップ４２に移行し、入力レイアウトパターンが判定格子を通過したか又はレイアウトパターンの入力が終了された場合にステップ４４に移行する。また、ＣＰＵ１２は、追加するインスタンスの配置が決定された場合（例えばマウスのボタンが操作されて配置位置がクリックされた場合）にステップ４４に移行する。つまり、ＣＰＵ１２は、入力レイアウトパターンが判定格子を通過すること、又はレイアウトパターンの入力が終了、又はインスタンスの配置することをトリガとして次のステップに移行する。
【００４４】
ステップ４４において、ＣＰＵ１２は、入力中のレイアウトパターンの占有面積を算出する。この時、ＣＰＵ１２は、レイアウトパターンの占有面積を、検証ステップ毎に算出する。
【００４５】
そして、ステップ４５において、ＣＰＵ１２は、ステップ４４において算出したレイアウトパターンの占有面積に基づいて、その時の検証ステップに対応する面積テーブルを更新する。つまり、ＣＰＵ１２は、入力したレイアウトパターンに基づいて、第１セル面積テーブル３５ａ及び第２セル面積テーブル３５ｂを更新する。なお、レイアウトパターンは、形成する配線層を指定して入力される。従って、ＣＰＵ１２は、レイアウトパターンを形成する配線層に対応する第１セル面積テーブル３５ａ及び第２セル面積テーブル３５ｂを更新する。
【００４６】
また、ステップ４５において、ＣＰＵ１２は、配置が決定されたインスタンスの面積テーブル３４を図２の図形ＤＢ３２から読み出し、その面積テーブル３４に応じて編集対象のセルのセル面積テーブル３５を更新する。インスタンスはレイアウトパターンを含み、レイアウトパターンは、パターンを形成する層に応じて設定されている。面積テーブル３４は、配線密度を考慮する必要のある層に対応する面積テーブルを含む。面積テーブル３４には、セル面積テーブルと同様に、各格子に含まれるレイアウトパターンの面積が格納されている。ＣＰＵ１２は、インスタンスの面積テーブル３４の値とセル面積テーブル３５の値とを対応する層毎に合成してセル面積テーブル３５の値を更新する。
【００４７】
ステップ４６において、ＣＰＵ１２は、ステップ４５において更新したセル面積テーブル３５（３５ａ，３５ｂ）の値に基づいて、対象部分の占有率を算出する。次に、ステップ４７において、ＣＰＵ１２は、ステップ４６にて計算した占有率により、検証ステップに対応するセル占有率テーブル３６（３６ａ，３６ｂ）の対象部分の値を更新する。この時、ＣＰＵ１２は、設定された検証ステップに対応するテーブルを対象テーブルとしてその対象テーブルを更新する。即ち、ＣＰＵ１２は、第１検証ステップがその時の検証ステップとして設定されている場合、第１検証ステップに対応する第１セル占有率テーブル３６ａを対象テーブルとし、その対象テーブルを更新する。同様に、ＣＰＵ１２は、第２検証ステップがその時の検証ステップとして設定されている場合、第２検証ステップに対応する第２セル占有率テーブル３６ｂを対象テーブルとし、その対象テーブルを更新する。
【００４８】
ステップ４６における対象部分は、レイアウトパターンの入力によって占有率の値が変化する要素からなる部分、又は処理によって抽出された部分である。例えば、Ｘ軸方向とＹ軸方向のそれぞれにおいて、第１検証ステップを検証エリアのサイズの１／５に設定した場合、１つの格子におけるレイアウトパターンの占有面積の変更が、セル占有率テーブル３６の２５個の要素に影響する。従って、ＣＰＵ１２は、２５個の要素についてそれぞれ占有率を算出する。同様に、第２検証ステップを検証エリアの１／１０に設定した場合、ＣＰＵ１２は、１００個の要素についてそれぞれ占有率を算出する。これらの占有率を算出する領域の大きさは、半導体装置のチップ面積に比べて極めて小さい。従って、半導体装置の全体について占有率を算出する時間に比べて、極めて短い時間で対応する領域の占有率を算出することができる。
【００４９】
第２セル占有率テーブル３６ｂの要素のうち、必ず第１セル占有率テーブル３６ａの要素と同じ値となるものが存在する。これは、要素の値、つまり占有率を算出する検証エリアの位置が同じであることに因る。上記したように、第１セル占有率テーブル３６ａの各要素の値は、第１検証ステップにて検証エリアを移動させ各位置において算出した値であり、第２セル占有率テーブル３６ｂの各要素の値は第２検証ステップにて検証エリアを移動させ各位置において算出した値である。従って、上記のように、第１検証ステップを第２検証ステップの２倍に設定した場合、第２セル占有率テーブル３６ｂを構成する各要素のうち、Ｘ軸方向及びＹ軸方向のそれぞれにおいて、１つ置きに検証エリアの位置が第１セル占有率テーブル３６ａの要素に対応する検証エリアの位置と一致する。そして、検証エリアの位置が一致する要素は、第１セル占有率テーブル３６ａと第２セル占有率テーブル３６ｂの設定により決定される、即ち検証処理を行う時点では判っている。従って、第１セル占有率テーブル３６ａの要素の値を算出することにより、第２セル占有率テーブル３６ｂの一部の要素の値を確定することができ、その分の演算を省略することができる。
【００５０】
図４に示すステップ４８において、ＣＰＵ１２は、ステップ４７において、セル占有率テーブル３６のうち更新された部分の占有率が、占有率の上限値を超えているか否かを判断し、占有率が上限値以下の場合（ＮＯ）はステップ４９に移行し、占有率が上限値を超えている場合（ＹＥＳ）はステップ５３に移行する。占有率の上限値は、製造プロセスの基準値（許容されるレイアウトパターンの密度の最大値）である。
【００５１】
ステップ４９において、ＣＰＵ１２は、更新部分の占有率が、保証占有率を超えているか否かを判断する。そして、ＣＰＵ１２は、占有率が保証占有率以下の場合（ＮＯ）はステップ５０に移行し、占有率が保証占有率を超えている場合（ＹＥＳ）はステップ５４（図３参照）に移行する。
【００５２】
保証占有率は、検証エリアの移動によってレイアウトパターンの占有面積が増減し、この占有面積の増減により変化する占有率が、占有率の上限値を超えないことを保証できる占有率を言う。占有面積の増減は、検証ステップに対応する。従って、保証占有率は、検証ステップに応じて設定されている。本実施形態では、検証ステップとして第１検証ステップ及び第２検証ステップが設定されているため、保証占有率は、第１検証ステップに対応する第１保証占有率と、第２検証ステップに対応する第２保証占有率とが設定されている。
【００５３】
保証占有率を図５に従って説明する。一例として、レイアウトパターンＰ１が形成されている。ＣＰＵ１２は、このレイアウトパターンＰ１に対して、検証エリアＶＡを検証ステップＶＳずつ移動させて各位置における占有率を算出する。この場合において、実線で示す検証エリアＶＡを、破線で示す位置まで移動させる。この時、実線で示す検証エリアＶＡに含まれるレイアウトパターンＰ１の占有面積に対して、破線で示す検証エリアＶＡに含まれるレイアウトパターンの占有面積は、検証エリアＶＡの縦（図５において上下方向）の長さと、検証ステップＶＳとの積の値となる。つまり、検証エリアＶＡにおける占有率は、検証エリアＶＡの横（図５において左右方向であって、検証エリアＶＡを移動させる方向）の長さと、検証ステップＶＳとの比だけ増加することになる。
【００５４】
上記例のように、検証エリアが１００個の格子から構成され、第１検証ステップがその１つの格子のサイズの２倍に設定されている場合、移動によって検証エリアの占有率は、最大２０（％）増加する。このため、占有率の上限値を５０（％）とすると、その最大値を超えないように保証する値、即ち第１保証占有率は３０（％）となる。また、検証エリアが１００個の格子から構成され、第２検証ステップがその１つの格子のサイズと等しく設定されている場合、移動によって検証エリアの占有率は、最大１０（％）増加する。このため、第２保証占有率は４０（％）となる。
【００５５】
従って、所定位置における検証エリアの占有率が保証占有率を超えていない場合、その検証エリアを検証ステップに応じて移動させた位置に於いても、占有率が最大値を超えることはない。つまり、所定の検証エリアにおける占有率を算出することにより、その位置における占有率と検証ステップだけずれた位置における検証エリアの占有率が、占有率の最大値が越えているか否かを判断することができる。
【００５６】
また、第１保証占有率は、第２検証ステップにおいて算出する占有率が上記の上限値を超えないことを保証する。例えば、上記したように第１検証ステップは第２検証ステップの２倍に設定されている。この場合、第２検証ステップに対応する第２セル占有率テーブル３６ｂには、第１検証ステップと第２検証ステップとにおいて検証エリアが一致する位置における占有率と、その位置からＸ軸方向、Ｙ軸方向に第２検証ステップだけ検証エリアを移動させた位置における占有率を含む。これらの位置における占有率の増加は、第２検証ステップにて検証エリアを移動させた時の占有面積の増加分となる。つまり、Ｘ軸方向にのみ検証エリアを移動させた場合、検証エリアの占有率は、最大１０（％）増加する。同様に、Ｙ軸方向にのみ検証エリアを移動させた場合、検証エリアの占有率は、最大１０（％）増加する。そして、Ｘ軸方向とＹ軸方向にそれぞれ検証エリアを移動させた場合、検証エリアの占有率は、最大１９（％）増加する。従って、第１セル占有率テーブル３６ａにおいて、占有率が第１保証占有率（＝３０）を越えていない場合、その占有率を算出した検証エリアの位置からそれぞれ第２検証ステップだけ検証エリアを移動させた位置における占有率は、占有率の上限値を超えないことになる。つまり、占有率が上限値を超えないことを保証することができる。
【００５７】
ステップ５０（エラー判断工程）において、ＣＰＵ１２は、対象領域の占有率が占有率の上限値と等しいか否かを判断し、対象領域の占有率が上限値と等しい場合（ＹＥＳ）にはステップ５１に移行し、等しくない場合（ＮＯ）にはステップ５２に移行する。
【００５８】
ステップ５１（エラー解消工程）において、ＣＰＵ１２は、図形入力禁止エリアを生成する。図形入力禁止エリアは、作業者の操作によるレイアウトパターンの追加を禁止するエリアである。ＣＰＵ１２は、対象領域の占有率に影響を与える範囲に対応して図形入力禁止エリアを生成する。この図形入力禁止エリアにより、所定位置の検証エリアにおける占有密度が、占有率の上限値を超えるのを防ぐ。
【００５９】
ステップ５２において、ＣＰＵ１２は、全図形入力・編集終了か否かを判断する。操作者は、全てのレイアウトパターンを入力し終わるか、又はレイアウトパターンの編集を終了すると、図１に示す入力装置１６により入力又は編集処理の終了を指示する。ＣＰＵ１２は、入力装置１６からの信号に基づいて、終了指示の有無を判断し、終了が指示されている場合（ＹＥＳ）は図形入力・編集処理を終了し、終了が指示されていない場合（ＮＯ）は図３のステップ４２移行し次のレイアウトパターンの入力又はレイアウトパターンの編集を可能とする。
【００６０】
上記のステップ４８において、更新された部分の占有率が上限値を超えている場合（ＹＥＳ）、ＣＰＵ１２はステップ５３に移行する。ステップ５３において、ＣＰＵ１２は、エラー発生箇所までレイアウトパターンの入力を強制的に戻す、又は各データをインスタンスの配置前の状態に戻し、セル面積テーブル３５とセル占有率テーブル３６を更新し、ステップ５０に移行する。エラー発生箇所は、エラーとなるレイアウトパターンを生成した入力確定又は操作の直前において検証処理を終了した箇所を示す。つまり、エラーが発生した場合に、その検証処理の直前の入力や処理による変更をセル面積テーブル３５及びセル占有率テーブル３６から削除することで、エラー発生までに確定したレイアウトパターンの状態を示す。このエラー発生箇所まで入力を戻すことにより、エラー発生を自動的に解消するとともに、エラーの発生を操作者に示すことが可能となる。
【００６１】
上記のステップ４９において、更新部分の占有率が保証占有率を超えている場合（ＹＥＳ）、ＣＰＵ１２は図３に示すステップ５４に移行する。図３に示すステップ５４において、ＣＰＵ１２は、セル占有率テーブル３６の更新箇所内で保証占有率を超えている検証エリア、即ち第１セル占有率テーブル３６ａの要素を抽出する。次に、ステップ５５において、ＣＰＵ１２は、保証占有率・検証ステップを更新する。詳しくは、ＣＰＵ１２は、検証ステップを第１検証ステップから第２検証ステップに変更するとともに、保証占有率を第１保証占有率から第２保証占有率に変更する。そして、ＣＰＵ１２は、ステップ４６に移行する。
【００６２】
ステップ４６において、ＣＰＵ１２は、ステップ５５において抽出した第１セル占有率テーブル３６ａの要素を対象領域とする。そして、ＣＰＵ１２は、ステップ５６において設定した第２検証ステップに対応する第２セル占有率テーブル３６ｂの対象領域に含まれる要素の値を更新する。
【００６３】
次に、入力レイアウトパターンの一例を示して上記の処理を説明する。
図９（ａ）に示すように、レイアウトパターン７１，７２が形成されたレイアウトデータに対して、新たなレイアウトパターンを入力する。尚、図９（ａ）は表示装置１５に表示されたレイアウトデータであり、同図９（ａ）において、レイアウトパターン７３は入力中のレイアウトパターンである。更に、図９（ａ）において、破線は第１検証ステップの格子を示す。
【００６４】
図１のＣＰＵ１２は、入力中のレイアウトパターン７３が格子を通過したと判断し（ステップ４３）、入力中のレイアウトパターン７３の占有面積を算出する（ステップ４４）。このとき、格子７４内のレイアウトパターン７３ａについては、このレイアウトパターン７３が入力格子枠７５を越えた時点で処理されている。従って、ＣＰＵ１２は、格子７６内のレイアウトパターン７３ｂの占有面積を算出する。そして、ＣＰＵ１２は、図９（ｂ）に示すように、第１セル面積テーブル３５ａの要素７７を更新する（ステップ４５）。更に、ＣＰＵ１２は、図１０（ａ）に示すように、第２セル面積テーブル３５ｂの要素（実線で囲まれた要素）を更新する（ステップ４５）。
【００６５】
次に、ＣＰＵ１２は、対象部分の占有率を算出し（ステップ４６）、第１セル占有率テーブル３６ａの対象部分の値を更新する。この場合、図９（ｂ）に示す要素７７の値の更新は、図９（ｃ）に示す枠７８内の要素に影響する。このため、ＣＰＵ１２は、枠７８内の要素を対象部分とし、この対象部分の要素の値を更新する（ステップ４７）。
【００６６】
次に、ＣＰＵ１２は、第１セル占有率テーブル３６ａにおいて、更新部分の占有率が上限値を超えているか否かを判断する（ステップ４８）。図９（ｃ）において、枠７８内の要素が更新されているが、何れの要素の値も上限値（＝５０）を超えていない。従って、ＣＰＵ１２は、更新部分の占有率が第１保証占有率（＝３０）を越えているか否かを判断する（ステップ４９）。図９（ｃ）において、枠７８内の要素が更新されており、枠７９内の要素の値が第１保証占有率を超えている。従って、ＣＰＵ１２は、第１保証占有率を超えている要素が含まれるエリア、つまり図９（ｃ）に示す枠７９を抽出する（ステップ５４）。
【００６７】
次に、ＣＰＵ１２は、保証占有率及び検証ステップを、第１保証占有率と第１検証ステップから第２保証占有率と第２検証ステップに更新する（ステップ５５）。
次に、ＣＰＵ１２は、抽出した枠７９内を対象部分とし、対象部分の占有率を算出する（ステップ４６）。この時、ＣＰＵ１２は、検証ステップを第２検証ステップに設定しているため、ステップ５４において抽出した枠７９に対応する第２セル占有率テーブル３６ｂの部分について、占有率を算出する。図９（ｃ）に示す枠７９に対応する部分は、第２セル占有率テーブル３６ｂにおいて、図１０（ｂ）に示す枠８０に囲まれた部分である。従って、ＣＰＵ１２は、この枠８０内の要素について、占有率を算出する。
【００６８】
即ち、ＣＰＵ１２は、第１保証占有率によって第１セル占有率テーブル３６ａの更新部分から密度エラーが発生する可能性が高い部分を抽出し、抽出した部分についてのみ第２セル占有率テーブル３６ｂの値を更新するようにした。従って、更新部分の全ての占有率が第１保証占有率を超えていない場合、抽出は行われず、第２セル占有率テーブル３６ｂの更新も行われない。このため、更新部分の全ての要素について占有率を算出する場合に比べ、演算に要する時間が短くなる。
【００６９】
この占有率算出において、上記したように、第２セル占有率テーブル３６ｂにおいて、検証エリアの位置が第１セル占有率テーブル３６ａの要素と同じ要素については、第１セル占有率テーブル３６ａの要素の値を複写し、他の要素について第２セル面積テーブル３５ｂに従って占有率を算出する。これによって、抽出した部分の要素の全てについて占有率を算出する場合に比べ、演算に要する時間が短くなる。
【００７０】
上記のように演算に要する時間を短くすることは、レイアウトパターンの入力の応答性を良くする。つまり、ＣＰＵ１２は、レイアウトパターンの入力中に占有率を算出するため、占有率の演算量が多くなる（演算時間が長くなる）と、操作者による入力装置１６の操作から、表示装置１５に対するレイアウトパターンの表示までの時間が長くなる、つまり入力に対する表示の応答性が悪くなる。しかし、本実施形態のように、占有率の演算に要する時間を短くすることで、入力に対する表示の応答性の劣化を抑えることができる。
【００７１】
次に、ＣＰＵ１２は、第２セル占有率テーブル３６ｂにおいて、更新部分の占有率が上限値を超えているか否かを判断する（ステップ４８）。
図１０（ｂ）において、枠８０内の要素のうちの１つの値が「５１」であり、上限値（＝５０）を超えている。つまり、この占有率（＝５１）の要素に対応する検証エリアにおいて、密度エラーが発生している。このため、ＣＰＵ１２は、エラー発生箇所までレイアウトパターンの入力を強制的に戻して各テーブル３５，３６を更新する（ステップ５３）。
【００７２】
図１１（ａ）に示すように、ＣＰＵ１２は、入力中のレイアウトパターンの座標値（表示装置１５に表示するためのレイアウトパターンの終点の座標値）を、入力格子に従って密度エラーが発生している占有率と上限値との差に応じて始点側の座標値に変更したレイアウトパターン７３ｃを生成し、図１１（ｂ），（ｃ）に示す第２セル面積テーブル３５ｂ及び第２セル占有率テーブル３６ｂを更新する。これにより、密度エラーが発生した要素の占有率は、占有率の上限値と等しくなる。このため、ＣＰＵ１２は、密度エラーを解消した要素に対応して図形入力禁止エリアを生成する（ステップ５１）。
【００７３】
図１１（ｃ）に示すように、密度エラーを解消した要素８１の値は、図１１（ｄ）に示す検証エリア８２により算出した占有率である。従って、この検証エリア８２内にレイアウトパターンを追加すると、要素８１の値が大きくなり、密度エラーを発生させる。このため、ＣＰＵ１２は、この検証エリア８２と同じ大きさの図形入力禁止エリアを生成する。この図形入力禁止エリアの生成により、上限値と等しい占有率の要素について、その占有率が上限値を超えることがなくなる、つまり、密度エラーの発生を防止する。
【００７４】
次に、インスタンスの一例を示して上記の処理を説明する。
第１の例として、図１２（ａ）に示すインスタンス９１を、図１２（ｂ）に示すセル９２に配置し（セルを編集）、図１２（ｃ）に示すセル９３を生成する場合について説明する。
【００７５】
インスタンス９１は、ハッチングを付したレイアウトパターン９１ａを含む。同様に、セル９２は、ハッチングを付したレイアウトパターン９２ａ〜９２ｄを含む。なお、インスタンス９１，９２内の実線は格子を示す。
【００７６】
インスタンス９１は、基準点（例えば、インスタンス９１の枠の左下頂点）に従って配置される。図１２（ｃ）に示すように、基準点をセル９２の格子上に配置した場合、セル９３は、インスタンス９１のパターン９１ａと、セル９２のパターン９２ａ〜９２ｄを含む。なお、図１２（ｃ）に示す黒丸は、インスタンス９１の基準点を示す。
【００７７】
インスタンス９１とセル９２は、それぞれ格子に１つのパターンを含む。従って、図１３（ａ）に示すように、インスタンス９１の面積テーブル３４は、レイアウトパターン９１ａに対応する格子に「１」が記憶され、レイアウトパターンを含まない格子に「０」が記憶されている。同様に、図１３（ｂ）に示すように、セル９２の面積テーブル３５ａは、レイアウトパターン９２ａ〜９２ｄに対応する格子に「１」が記憶され、レイアウトパターンを含まない格子に「０」が記憶されている。
【００７８】
図１２（ｃ）に示すように、セル９１をセル９２に配置した場合、ＣＰＵ１２は、図１３（ｃ）に示すように、対応する面積テーブル３４をセル面積テーブル３５ｂに配置する。それぞれの面積テーブルの配置は、それぞれに含まれる面積値を、インスタンス９１とセル９２の重なりに対応させるものである。例えば、インスタンス９１の基準点を、面積テーブル３４の基準点とする。なお、図では、インスタンス９１の面積テーブル３４が重ねられた部分の面積値を示していない。
【００７９】
そして、ＣＰＵ１２は、各格子の面積を合成する。この場合、ＣＰＵ１２は、インスタンス面積テーブル３４の値と、セル面積テーブル３５ａの値とを論理和演算して対応する格子の面積値としてセル面積テーブル３５ａを更新する。重なりのない部分の面積値は更新前の面積テーブル３５ａの値となる。なお、図１３では、更新後のセル面積テーブルに、更新前のセル面積テーブルと同じ符号を付している。
【００８０】
インスタンス９１は、基準点対して、回転、反転が指定され、配置される。
図１４（ａ）は、反転（図において左右方向であって、例えばＹ軸を中心とした反転）したインスタンス９１を配置した例を示す。この場合、上記と同様に、図１４（ｂ）に示すように、反転されたインスタンス面積テーブル３４がセル面積テーブル３５ａに配置し、各面積値を論理和演算し、図１４（ｃ）に示すように、セル面積テーブル３５ａを更新する。
【００８１】
図１５（ａ）は、反転（図において左右方向であって、例えばＹ軸を中心とした反転）したインスタンス９１を、更に基準点周りに回転して配置した例を示す。この場合、上記と同様に、図１５（ｂ）に示すように、反転されたインスタンス面積テーブル３４がセル面積テーブル３５ａに配置し、各面積値を論理和演算し、図１５（ｃ）に示すように、セル面積テーブル３５ａを更新する。
【００８２】
インスタンス９１を配置すると、ＣＰＵ１２は、そのインスタンス９１が配置されたセル９２の面積テーブル３５ａを、インスタンス９１の面積テーブル３４を参照して更新する。そして、ＣＰＵ１２は、更新したセル面積テーブル３５ａに基づいて占有面積を算出してセル占有率テーブル３６ａを更新する。配置したインスタンス９１に対応して占有率を算出する領域は、半導体装置全体に比べて少ないため、短時間で占有率を算出することができ、半導体装置に形成するすべてのインスタンスを配置した後に占有率を算出する方法に比べて設計時間を短縮することができる。
【００８３】
第２の例として、図１６（ａ）に示すインスタンス１０１を、図１６（ｂ）に示すセル１０２に配置し（セルを編集）、図１６（ｃ）に示すセル１０３を生成する場合について説明する。
【００８４】
インスタンス１０１は、ハッチングを付したレイアウトパターン１０１ａ，１０１ｂを含む。同様に、インスタンス１０２は、ハッチングを付したレイアウトパターン１０２ａ〜１０２ｄを含む。なお、インスタンス１０１，１０２内の実線は格子を示す。
【００８５】
インスタンス１０１は、基準点（例えば、インスタンス１０１の枠の左下頂点）に従って配置される。図１６（ｃ）に示すように、基準点をセル１０２の格子内に配置した場合、セル１０３は、インスタンス１０１のパターン１０１ａ，１０１ｂと、セル１０２のパターン１０２ａ〜１０２ｄを含む。なお、図１６（ｃ）に示す黒丸は、インスタンス１０１の基準点を示す。
【００８６】
図１７（ａ）に示す面積テーブル３４は図１６（ａ）に示すインスタンス１０１に対応する面積テーブルである。面積テーブル３４の値は、対応する格子内にレイアウトパターンが含まれるか否かである。面積テーブル３４には、レイアウトパターンを含む格子に対応して「１」が記憶され、レイアウトパターンを含まない格子に対応して「０」が記憶される。
【００８７】
図１のＣＰＵ１２は、面積テーブル３４の基準点を設定する。ＣＰＵ１２は、例えば、面積テーブル３４の基準点を、対応するインスタンス１０１の基準点とする。そして、ＣＰＵ１２は、レイアウトパターンを含む格子の頂点の座標値を算出する。図１７（ｂ）には、算出した座標値の頂点を黒丸にて示されている。例えば、格子を各軸（Ｘ軸及びＹ軸）の１単位とし、基準点を（０，０）とすると、頂点の座標値は、（１，１），（２，１），（１，２），（２，２），（１，３），（２，３）となる。
【００８８】
図１７（ｃ）に示す面積テーブル３５ａは図１６（ｂ）に示すインスタンス１０２に対応する面積テーブルである。面積テーブル３５ａの値は、対応する格子内にレイアウトパターンが含まれるか否かである。面積テーブル３５ａには、レイアウトパターンを含む格子に対応して「１」が記憶され、レイアウトパターンを含まない格子に対応して「０」が記憶される。
【００８９】
次に、ＣＰＵ１２は、図１６（ｃ）に示すインスタンス１０１とセル１０２の配置と同様に、図１８（ａ）に示すように、セル面積テーブル３５ａにインスタンス面積テーブル３４を配置する。そして、ＣＰＵ１２は、セル面積テーブル３５ａの格子に対して、インスタンス面積テーブル３４のレイアウトパターンを含む格子の頂点が含まれるか否かを判断し、頂点が含まれる格子についてはレイアウトパターンを含むとして面積値を「１」としてセル面積テーブル３５ａを更新し、頂点が含まれない格子については更新前の面積値を維持する。その結果、ＣＰＵ１２は、図１８（ｂ）に示すように、面積テーブル３５ａを更新する。
【００９０】
上記のように、セル１０２の格子位置と、そのセル１０２に配置したインスタンス１０１の格子位置が異なる場合、ＣＰＵ１２は、インスタンス１０１に対応する面積テーブル３４のレイアウトパターンを含む格子の頂点を算出し、その頂点を含むセル１０２のセル面積テーブル３５ａについて、面積値を算出してセル面積テーブル３５ａを更新する。このように、セル面積テーブル３５ａを更新することにより、セル１０２に対するインスタンス１０１の配置位置の自由度が高まる、即ち、任意の位置にインスタンス１０１を配置することができ、配線設計を容易に行うことができる。
【００９１】
インスタンス１０１を配置すると、ＣＰＵ１２は、そのインスタンス１０１が配置されたセル１０２の面積テーブル３５ａを、インスタンス１０１の面積テーブル３４を参照して更新する。そして、ＣＰＵ１２は、更新したセル面積テーブル３５ａに基づいて占有面積を算出してセル占有率テーブル３６ａを更新する。配置したインスタンス１０１に対応して占有率を算出する領域は、半導体装置全体に比べて少ないため、短時間で占有率を算出することができ、半導体装置に形成するすべてのインスタンスを配置した後に占有率を算出する方法に比べて設計時間を短縮することができる。
【００９２】
次に、図１６（ｃ）に示すようにインスタンス１０１をセル１０２に配置した場合において面積テーブル３５ａを更新する別の例を説明する。
インスタンス１０１が配置されると、図１のＣＰＵ１２は、配置されたインスタンス１０１の配置状態に応じて、対応する面積テーブル３４の値を変更した面積テーブル３４ａを生成する。ＣＰＵ１２は、インスタンス１０１に対応する面積テーブル３５をずらす方向に応じて各格子の面積値を変更する。
【００９３】
インスタンス１０１の基準点と一致する基準点の面積テーブルを第１の面積テーブルとし、基準点をずらした面積テーブルを第２の面積テーブルとする。ＣＰＵ１２は、第１の面積テーブルに対して、レイアウトパターンを含む格子の頂点の座標値を算出する。次に、ＣＰＵ１２は、第２の面積テーブルの格子のうち、算出した頂点の座標値を含む格子を抽出する。そして、ＣＰＵ１２は、その抽出した格子の面積値を、レイアウトパターンを含む値、即ち「１」に変更する。
【００９４】
例えば、図１７（ａ）に示す面積テーブル３４に対して、ＣＰＵ１２は、図１７（ｂ）に示すように、レイアウトパターンを含む格子の頂点（黒丸で示す頂点）の座標値を算出する。そして、面積テーブル３４を左下方向にずらした場合、各頂点は、それぞれ頂点を左下の頂点とする格子に含まれることになる。従って、ＣＰＵ１２は、それらの頂点を含む６つの格子の面積値を、レイアウトパターンを含むことを示す値「１」に変更した面積テーブル３４ａ（図１９（ａ）参照）する。
【００９５】
上記の処理は、格子を構成する２つの軸（Ｘ軸及びＹ軸）について、面積テーブルをずらした方向と逆の方向に、レイアウトパターンを含むことを示す面積値を拡張することといえる。
【００９６】
次に、ＣＰＵ１２は、図１９（ｂ）に示すように、生成した面積テーブル３４ａ（第２の面積テーブル）を、セル１０２の面積テーブル３５ａに配置し、両面積テーブル３４ａ，３５ａの面積値を合成（論理和演算）して面積テーブル３５ａを更新する。
【００９７】
上記のように、セル１０２の格子位置と、そのセル１０２に配置したインスタンス１０１の格子位置が異なる場合、ＣＰＵ１２は、インスタンス１０１に対応する面積テーブル３４のレイアウトパターンを含む格子の面積値を、セル面積テーブル３５ａの格子に対応して基準点をずらした面積テーブル３４ａを生成し、その面積テーブル３４ａの面積値を参照してセル面積テーブル３５ａを更新する。このように、セル面積テーブル３５ａを更新することにより、セル１０２に対するインスタンス１０１の配置位置の自由度が高まる、即ち、任意の位置にインスタンス１０１を配置することができ、配線設計を容易に行うことができる。
【００９８】
ＣＰＵ１２は、上記のようにしてインスタンスをセルに配置し、セル面積テーブル３５ａ及びセル占有率テーブル３６ａを更新する。そして、ＣＰＵ１２は、更新したセル占有率テーブルの値が上限値を超えているか否かを判断し（図４のステップ４８）、上限値を超えている、つまりエラーの場合にはセル面積テーブル３５ａ及びセル占有率テーブル３６ａをインスタンスの配置前の状態に戻す（図４のステップ５３）。エラーが発生した場合に、その検証処理の直前の入力や処理による変更をセル面積テーブル３５ａ及びセル占有率テーブル３６ａから削除する。このエラー発生箇所まで入力を戻すことにより、エラー発生を自動的に解消するとともに、エラーの発生を操作者に示すことが可能となる。
【００９９】
以上記述したように、本実施の形態によれば、以下の効果を奏する。
（１）設計装置１１の記憶装置１４には、半導体装置を検証ステップの格子にて区画した各領域に含まれるレイアウトパターンの面積がそれぞれ格納されるセル面積テーブル３５と、移動される検証エリアの位置に対応し、各検証エリアには所定数の領域が含まれ、検証エリアに対してその検証エリアに含まれるレイアウトパターンの占有率が、各検証エリアに対応して格納されるセル占有率テーブル３６を含む面積ＤＢ３３が記憶される。図形ＤＢ３２にはインスタンスの面積テーブル３４が含まれる。ＣＰＵ１２は、配置されたインスタンスの面積テーブル３４に従って編集対象のセル面積テーブル３５を変更し、そのセル面積テーブルに従ってセル占有率テーブル３６を更新する。従って、配置したインスタンスに対応して占有率を算出するため、その領域は、半導体装置全体に比べて少なく、短時間で占有率を算出することができ、半導体装置に形成するすべてのレイアウトパターンを入力した後に占有率を算出する方法に比べて設計時間を短縮することができる。
【０１００】
（２）ＣＰＵ１２は、インスタンスの配置位置に応じて、セル面積テーブル３５ａに含まれる格子のうち、面積値を更新する格子を変更するようにした。その結果、セル９２，１０２に対するインスタンス９１，１０１の配置位置の自由度が高まる、即ち、任意の位置にインスタンス９１，１０１を配置することができ、配線設計を容易に行うことができる。
【０１０１】
（３）セル面積テーブル３５及びセル占有率テーブル３６は、それぞれ半導体装置の配線層のうち、密度基準が設定された配線層に対応するテーブルを含む。ＣＰＵ１２は、配置されたインスタンスの面積テーブル３４に対応するテーブルを更新するようにした。その結果、全ての配線層をチェックする場合と比べてチェックに要する時間が短くなり、設計時間を短縮することができる。
【０１０２】
（４）設計装置１１の記憶装置１４には、半導体装置を検証ステップの格子にて区画した各領域に含まれるレイアウトパターンの占有面積がそれぞれ格納されるセル面積テーブル３５と、移動される検証エリアの位置に対応し、各検証エリアには所定数の領域が含まれ、検証エリアに対してその検証エリアに含まれるレイアウトパターンの占有率が、各検証エリアに対応して格納されるセル占有率テーブル３６とが記憶される。ＣＰＵ１２は、レイアウトパターンの入力中において、セル面積テーブル３５及びセル占有率テーブル３６を更新する。従って、入力中のレイアウトパターンに対応して占有率を算出する領域は、半導体装置全体に比べて少ないため、短時間で占有率を算出することができ、半導体装置に形成するすべてのレイアウトパターンを入力した後に占有率を算出する方法に比べて設計時間を短縮することができる。
【０１０３】
（５）設計装置１１には検証ステップとして互いに異なる第１及び第２検証ステップが設定され、セル面積テーブル３５及びセル占有率テーブル３６は、第１及び第２検証ステップに対応してそれぞれ第１及び第２セル面積テーブル３５ａ，３５ｂ，第１及び第２セル占有率テーブル３６ａ，３６ｂから構成される。ＣＰＵ１２は、値が大きな第１検証ステップから値の小さな第２検証ステップへと変更し、ステップ４５では各検証ステップのセル面積テーブル３５ａ，３５ｂを更新し、ステップ４７ではその時の検証ステップに対応するセル占有率テーブル３６ａ，３６ｂを更新する。従って、値の大きな第１検証ステップに対応する第１セル占有率テーブル３６ａを更新した後、値の小さな検証ステップに対応する第２セル占有率テーブル３６ｂを更新することで、第２セル占有率テーブル３６ｂにおいて、占有率が上限値を超えないと判定される部分については占有率の算出を省略することが可能となる、占有率の算出に要する時間を短縮することができる。更に、値が小さな検証ステップに対応する第２セル占有率テーブル３６ｂを更新ことで、小さな領域に対応する占有率が算出され、必用な精度にて占有率を算出することができ、従来に比べて精度の低下を抑えることができる。
【０１０４】
（６）設計装置１１には上限値に応じた保証占有率が設定される。ＣＰＵ１２は、第１検証ステップに対応する第１セル占有率テーブル３６ａを対象テーブルとし、その対象テーブルの占有率を保証占有率と比較し、占有率が保証占有率を超えているエリアを抽出する。そして、ＣＰＵ１２は、検証ステップを第２検証ステップに更新し、第２占有率テーブルを対象テーブルとしてその対象テーブルにおいて先に抽出したエリア内の対象部分について占有率を算出して第２占有率テーブルを更新するようにした。上限値に応じた保証占有率を超える部分は、占有率が上限値を超える確率が高い、即ち密度エラーが発生する候補の部分である。従って、第１セル占有率テーブル３６ａ、第２セル占有率テーブル３６ｂと、順次切り換え、エラー候補の箇所を段階的に絞り込むことで、第２セル占有率テーブル３６ｂにおいて、入力するレイアウトパターンの占有面積が影響する部分の全ての占有率を算出する場合に比べ、第２セル占有率テーブル３６ｂの更新に要する時間が短くなり、設計時間を短縮することができる。
【０１０５】
（７）ＣＰＵ１２は、更新されたセル占有率テーブル３６（３６ａ，３６ｂ）の更新部分の占有率が上限値を超えていると判断した場合にレイアウトパターンの入力を強制的に戻してセル面積テーブル３５及びセル占有率テーブル３６を更新するようにした。そのため、占有率が上限値を超えた密度エラーを自動的に解消することができる。
【０１０６】
（８）ＣＰＵ１２は、入力装置１６からの信号に基づいて、入力中のレイアウトパターンが検証ステップの格子を越えているか否か、及びレイアウトパターンの入力が終了したか否か、を判断し、入力中のレイアウトパターンが前記検証ステップの格子を越えた場合、又はレイアウトパターンの入力が終了した場合にそのレイアウトパターンに占有面積計算、占有率計算を行うようにした。従って、検証ステップの格子に従ってレイアウトパターンの入力中にトリガが発生するため、占有率を算出する対象となるレイアウトパターンの占有面積が検証ステップに応じており、その時の占有率を算出する演算量が少なくなり、レイアウトパターンの入力に対する影響を少なくすることができる、つまり、操作者においてレイアウトパターンを入力するための操作性の劣化を抑えることができる。
【０１０７】
（９）ＣＰＵ１２は、セル占有率テーブル３６の占有率が上限値と等しい場合に、その上限値と等しい占有率に対応するエリアに対して図形入力禁止エリアを生成するようにした。その結果、上限値と等しい占有率の要素について、その占有率が上限値を超えることがなくなる、つまり、密度エラーの発生を防止することができる。
【０１０８】
尚、前記実施形態は、以下の態様に変更してもよい。
・上記実施形態では、セル面積テーブル３５を、レイアウトパターンを形成する領域に対して、１つの領域に形成されたレイアウトパターンの占有面積を格納する第１セル面積テーブル３５ａと、複数の領域に形成されたレイアウトパターンの占有面積を格納する第２セル面積テーブル３５ｂとから構成したが、互いに格納する領域数が異なるｎ個（３つ以上）の面積テーブルにより構成し、配線密度の検証をｎ段階にて実施するようにしてもよい。また、セル占有率テーブル３６を、ｎ個（３つ以上）の占有率テーブルにより構成し、配線密度の検証をｎ段階にて実施するようにしてもよい。
【０１０９】
・上記実施形態では、完成した１Ｃｈｉｐ全体のレイアウトデータやマクロレベルのレイアウトデータに対して、配線密度のプロセス製造基準の高い側だけでなく、低い側も配線密度の検証をしてもよい。
【０１１０】
・上記実施形態では、新たなレイアウトデータを生成する場合について説明したが、追加又は修正が必用なレイアウトデータを編集する場合に適用しても良い。この場合、図３のステップ４１における初期化処理において、ＣＰＵ１２は、記憶装置１４に格納されたレイアウトデータを読み込み、そのレイアウトデータのレイアウトパターンに基づいて、セル面積テーブル３５及びセル占有率テーブル３６の値を設定する。このようにしても、追加又は修正するレイアウトパターンに係る密度チェックを容易に行うことができる。
【０１１１】
・上記実施形態では、占有率が上限値を越えたか否かを判断するようにしたが、下限値を設定し、占有率が下限値を下回ったか否かを判定するようにしてもよい。下限値は、製造プロセスの基準値（必要とするレイアウトパターンの密度の最小値）である。判定結果に基づき、レイアウトパターンが必要な領域にレイアウトパターンを追加することができるようになり、設計後に下限値をチェックする手順と比べて設計時間を短縮することができるようになる。
【０１１２】
上記各実施形態に関し、以下の付記を開示する。
（付記１）
半導体装置のレイアウトデータを生成する設計装置の中央処理装置にて実行される配線設計方法であって、
記憶装置には、インスタンスに含まれるレイアウトパターンに対応する面積値が格納されたインスタンス面積テーブルが記憶され、
前記中央処理装置が実行する処理は、
インスタンスが配置されたセルのセル面積テーブルを、前記インスタンス面積テーブルに従って更新するステップと、
更新されたセル面積テーブルに基づいて前記インスタンスが配置されたセルに対応するセル占有率テーブルを更新するステップと、
を含む、
ことを特徴とする配線設計方法。
（付記２）
前記中央処理装置は、
前記インスタンス面積テーブルの値と、前記セル面積テーブルの値とを論理和演算してセル面積テーブルを更新する、
ことを特徴とする付記１に記載の配線設計方法。
（付記３）
前記中央処理装置は、
前記インスタンスの配置位置に応じて、前記セル面積テーブルに含まれる格子のうち、面積値を更新する格子を変更する、
ことを特徴とする付記２に記載の配線設計方法。
（付記４）
前記中央処理装置は、
前記インスタンス面積テーブルの格子のうち、レイアウトパターンを含む格子の頂点の座標値を算出し、その算出した頂点の座標値を含むセル面積テーブルの格子の面積値を更新する、
ことを特徴とする付記３に記載の配線設計方法。
（付記５）
前記中央処理装置は、
前記インスタンス面積テーブルを、前記インスタンスの配置位置に応じてずらし、そのずらした方向に応じてインスタンス面積テーブルに含まれる格子を拡張した第２の面積テーブルを生成し、その第２の面積テーブルの面積値とセル面積テーブルの面積値とを論理和演算してセル面積テーブルを更新する、
ことを特徴とする付記３に記載の配線設計方法。
（付記６）
前記半導体装置の設計規則に応じて移動させた検証エリアの占有率が設計規則を満足するか否かを検証するステップを含む、
ことを特徴とする付記１〜５のうちの何れか１項に記載の配線設計方法。
（付記７）
前記設計装置には検証ステップとして互いに異なる複数の検証ステップが設定され、
前記面積テーブル及び前記占有率テーブルは、各検証ステップに対応してそれぞれ複数のテーブルを含み、
前記中央処理装置は、
対象とする検証ステップを、大きな検証ステップから小さな検証ステップへと順次変更し、
各検証ステップのセル面積テーブルを更新し、
対象する検証ステップに対応するセル占有率テーブルを更新する、
ことを特徴とする付記１〜６のうちの何れか１項に記載の配線設計方法。
（付記８）
前記セル面積テーブル及び前記セル占有率テーブルは、それぞれ半導体装置の配線層のうち、密度基準が設定された配線層に対応するテーブルを含み、
入力されたインスタンスの面積テーブルに対応するテーブルを更新する、
ことを特徴とする付記１〜７のうちの何れか１項に記載の配線設計方法。
（付記９）
前記中央処理装置が実行する処理は、
更新された前記占有率テーブルの更新部分の占有率が上限値を超えているか否かを判断するステップと、
占有率が上限値を超えていると判断した場合に前記面積テーブル及び前記占有率テーブルをインスタンス配置前の状態に戻すステップと、
を含むこと、を特徴とする付記１〜８のうちの何れか１つに記載の配線設計方法。
（付記１０）
半導体装置のレイアウトデータを生成する設計装置であって、
記憶装置には、インスタンスに含まれるレイアウトパターンに対応する面積値が格納されたインスタンス面積テーブルが記憶され、
前記設計装置の中央処理装置が実行する処理は、
インスタンスが配置されたセルのセル面積テーブルを、前記インスタンス面積テーブルに従って更新するステップと、
更新されたセル面積テーブルに基づいて前記インスタンスが配置されたセルに対応するセル占有率テーブルを更新するステップと、
を含む、
ことを特徴とする設計装置。
（付記１１）
半導体装置のレイアウトデータを生成するために設計装置の中央処理装置が実行するプログラムであって、
記憶装置には、インスタンスに含まれるレイアウトパターンに対応する面積値が格納されたインスタンス面積テーブルが記憶され、
前記中央処理装置が実行する処理は、
インスタンスが配置されたセルのセル面積テーブルを、前記インスタンス面積テーブルに従って更新するステップと、
更新されたセル面積テーブルに基づいて前記インスタンスが配置されたセルに対応するセル占有率テーブルを更新するステップと、
を含む、
ことを特徴とするプログラム。
【符号の説明】
【０１１３】
１１ 設計装置
１２ 中央処理装置（ＣＰＵ）
３４（３４ａ，３４ｂ） インスタンス面積テーブル
３５（３５ａ，３５ｂ） セル面積テーブル
３６（３６ａ，３６ｂ） セル占有率テーブル
【特許請求の範囲】
【請求項１】
半導体装置のレイアウトデータを生成する設計装置の中央処理装置にて実行される配線設計方法であって、
記憶装置には、インスタンスに含まれるレイアウトパターンに対応する面積値が格納されたインスタンス面積テーブルが記憶され、
前記中央処理装置が実行する処理は、
インスタンスが配置されたセルのセル面積テーブルを、前記インスタンス面積テーブルに従って更新するステップと、
更新されたセル面積テーブルに基づいて前記インスタンスが配置されたセルに対応するセル占有率テーブルを更新するステップと、
を含む、
ことを特徴とする配線設計方法。
【請求項２】
前記中央処理装置は、
前記インスタンス面積テーブルの値と、前記セル面積テーブルの値とを論理和演算してセル面積テーブルを更新する、
ことを特徴とする請求項１に記載の配線設計方法。
【請求項３】
前記中央処理装置は、
前記インスタンスの配置位置に応じて、前記セル面積テーブルに含まれる格子のうち、面積値を更新する格子を変更する、
ことを特徴とする請求項２に記載の配線設計方法。
【請求項４】
半導体装置のレイアウトデータを生成する設計装置であって、
記憶装置には、インスタンスに含まれるレイアウトパターンに対応する面積値が格納されたインスタンス面積テーブルが記憶され、
前記設計装置の中央処理装置が実行する処理は、
インスタンスが配置されたセルのセル面積テーブルを、前記インスタンス面積テーブルに従って更新するステップと、
更新されたセル面積テーブルに基づいて前記インスタンスが配置されたセルに対応するセル占有率テーブルを更新するステップと、
を含む、
ことを特徴とする設計装置。
【請求項５】
半導体装置のレイアウトデータを生成するために設計装置の中央処理装置が実行するプログラムであって、
記憶装置には、インスタンスに含まれるレイアウトパターンに対応する面積値が格納されたインスタンス面積テーブルが記憶され、
前記中央処理装置が実行する処理は、
インスタンスが配置されたセルのセル面積テーブルを、前記インスタンス面積テーブルに従って更新するステップと、
更新されたセル面積テーブルに基づいて前記インスタンスが配置されたセルに対応するセル占有率テーブルを更新するステップと、
を含む、
ことを特徴とするプログラム。
【請求項１】
半導体装置のレイアウトデータを生成する設計装置の中央処理装置にて実行される配線設計方法であって、
記憶装置には、インスタンスに含まれるレイアウトパターンに対応する面積値が格納されたインスタンス面積テーブルが記憶され、
前記中央処理装置が実行する処理は、
インスタンスが配置されたセルのセル面積テーブルを、前記インスタンス面積テーブルに従って更新するステップと、
更新されたセル面積テーブルに基づいて前記インスタンスが配置されたセルに対応するセル占有率テーブルを更新するステップと、
を含む、
ことを特徴とする配線設計方法。
【請求項２】
前記中央処理装置は、
前記インスタンス面積テーブルの値と、前記セル面積テーブルの値とを論理和演算してセル面積テーブルを更新する、
ことを特徴とする請求項１に記載の配線設計方法。
【請求項３】
前記中央処理装置は、
前記インスタンスの配置位置に応じて、前記セル面積テーブルに含まれる格子のうち、面積値を更新する格子を変更する、
ことを特徴とする請求項２に記載の配線設計方法。
【請求項４】
半導体装置のレイアウトデータを生成する設計装置であって、
記憶装置には、インスタンスに含まれるレイアウトパターンに対応する面積値が格納されたインスタンス面積テーブルが記憶され、
前記設計装置の中央処理装置が実行する処理は、
インスタンスが配置されたセルのセル面積テーブルを、前記インスタンス面積テーブルに従って更新するステップと、
更新されたセル面積テーブルに基づいて前記インスタンスが配置されたセルに対応するセル占有率テーブルを更新するステップと、
を含む、
ことを特徴とする設計装置。
【請求項５】
半導体装置のレイアウトデータを生成するために設計装置の中央処理装置が実行するプログラムであって、
記憶装置には、インスタンスに含まれるレイアウトパターンに対応する面積値が格納されたインスタンス面積テーブルが記憶され、
前記中央処理装置が実行する処理は、
インスタンスが配置されたセルのセル面積テーブルを、前記インスタンス面積テーブルに従って更新するステップと、
更新されたセル面積テーブルに基づいて前記インスタンスが配置されたセルに対応するセル占有率テーブルを更新するステップと、
を含む、
ことを特徴とするプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【公開番号】特開２０１１−１８１０５（Ｐ２０１１−１８１０５Ａ）
【公開日】平成２３年１月２７日（２０１１．１．２７）
【国際特許分類】
【出願番号】特願２００９−１６０６０１（Ｐ２００９−１６０６０１）
【出願日】平成２１年７月７日（２００９．７．７）
【出願人】（３０８０１４３４１）富士通セミコンダクター株式会社 (2,507)
【Ｆターム（参考）】
【公開日】平成２３年１月２７日（２０１１．１．２７）
【国際特許分類】
【出願日】平成２１年７月７日（２００９．７．７）
【出願人】（３０８０１４３４１）富士通セミコンダクター株式会社 (2,507)
【Ｆターム（参考）】
[ Back to top ]