(57)【特許請求の範囲】
【請求項１】
コンピュータを、
設計対象回路のレイアウト領域を区切って分割された部分領域ごとの配線のエッジ長に基づいて、前記レイアウト領域に配置されたセル間の配線経路を探索する探索手段、
前記探索手段によって探索された配線経路が経由する部分領域ごとの配線密度およびエッジ長を算出する第１の算出手段、
前記第１の算出手段によって算出された前記部分領域の配線密度に基づいて、前記部分領域の配線密度が、予め設定された配線密度に関する制限値以上であるか否かを判断する判断手段、
前記判断手段によって前記配線密度に関する制限値未満と判断された場合、前記第１の算出手段によって算出された前記部分領域のエッジ長と、予め設定されたエッジ長に関する制限値とに基づいて、前記部分領域の空き領域に挿入するダミー配線の寸法を算出する第２の算出手段、
前記第２の算出手段によって算出された前記寸法のダミー配線を前記部分領域の空き領域に挿入する挿入手段、
前記挿入手段によって前記ダミー配線が挿入された挿入結果を出力する出力手段、
として機能させることを特徴とするレイアウト設計プログラム。
【請求項２】
前記コンピュータを、
特定の部分領域まで探索された場合、前記特定の部分領域に隣接する部分領域のうち探索済みの部分領域を除く部分領域の配線のエッジ長を取得する取得手段、
前記取得手段によって取得された取得結果に基づいて、前記特定の部分領域の探索先の部分領域を決定する決定手段として機能させることを特徴とする請求項１に記載のレイアウト設計プログラム。
【請求項３】
前記探索手段は、
さらに、前記部分領域ごとの配線の配線密度に基づいて、前記セル間の配線経路を探索することを特徴とする請求項１または２に記載のレイアウト設計プログラム。
【請求項４】
請求項１〜３のいずれか一つに記載のレイアウト設計プログラムを記録したコンピュータに読み取り可能な記録媒体。
【請求項５】
設計対象回路のレイアウト領域を区切って分割された部分領域ごとの配線のエッジ長に基づいて、前記レイアウト領域に配置されたセル間の配線経路を探索する探索手段と、
前記探索手段によって探索された配線経路が経由する部分領域ごとの配線密度およびエッジ長を算出する第１の算出手段と、
前記第１の算出手段によって算出された前記部分領域の配線密度に基づいて、前記部分領域の配線密度が、予め設定された配線密度に関する制限値以上であるか否かを判断する判断手段と、
前記判断手段によって前記配線密度に関する制限値未満と判断された場合、前記第１の算出手段によって算出された前記部分領域のエッジ長と、予め設定されたエッジ長に関する制限値とに基づいて、前記部分領域の空き領域に挿入するダミー配線の寸法を算出する第２の算出手段と、
前記第２の算出手段によって算出された前記寸法のダミー配線を前記部分領域の空き領域に挿入する挿入手段と、
前記挿入手段によって前記ダミー配線が挿入された挿入結果を出力する出力手段と、
を備えたことを特徴とするレイアウト設計装置。
【請求項６】
設計対象回路のレイアウト領域を区切って分割された部分領域ごとの配線のエッジ長に基づいて、前記レイアウト領域に配置されたセル間の配線経路を探索する探索工程と、
前記探索工程によって探索された配線経路が経由する部分領域ごとの配線密度およびエッジ長を算出する第１の算出工程と、
前記第１の算出工程によって算出された前記部分領域の配線密度に基づいて、前記部分領域の配線密度が、予め設定された配線密度に関する制限値以上であるか否かを判断する判断工程と、
前記判断工程によって前記配線密度に関する制限値未満と判断された場合、前記第１の算出工程によって算出された前記部分領域のエッジ長と、予め設定されたエッジ長に関する制限値とに基づいて、前記部分領域の空き領域に挿入するダミー配線の寸法を算出する第２の算出工程と、
前記第２の算出工程によって算出された前記寸法のダミー配線を前記部分領域の空き領域に挿入する挿入工程と、
前記挿入工程によって前記ダミー配線が挿入された挿入結果を出力する出力工程と、
を含んだことを特徴とするレイアウト設計方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、ＣＭＰ（Ｃｈｅｍｉｃａｌ  Ｍｅｃｈａｎｉｃａｌ  Ｐｌａｎａｒｉｚａｔｉｏｎ）技術による層間絶縁膜の平坦性を考慮した半導体デバイスのレイアウト設計プログラム、該プログラムを記録した記録媒体、レイアウト設計装置、およびレイアウト設計方法に関する。
【背景技術】
【０００２】
近年、半導体デバイスの微細化や多層配線化にともなって各層での平坦性が求められている。具体的には、半導体デバイス製造における配線工程において銅メッキなどが施された基板表面上を、ＣＭＰ技術などにより研磨して均一に平坦化させることが品質向上の点で重要となっている。
【０００３】
一般に、研磨後の平坦性は、配線の配線密度に依存することが知られている。そこで、配線後のレイアウト領域をメッシュ状に区切って、配線密度の低いメッシュにダミー配線を挿入することにより、レイアウト領域全体での配線密度の均一性を確保する技術が開示されている（たとえば、下記非特許文献１参照。）。
【０００４】
具体的には、例えば、下記非特許文献２に記載されている計算式を用いて、メッシュに挿入するダミー配線の配線密度およびエッジ長を求める。このあと、複数種類のダミー配線を保持するライブラリから、求めた配線密度およびエッジ長に応じたダミー配線を抽出し、メッシュの空き領域に挿入する。これにより、各メッシュの配線密度およびエッジ長を一定値以内に抑え、研磨後における基板表面の平坦性を向上させる。
【０００５】
【非特許文献１】Ｓｕｂａｒｎａ  Ｓｉｎｈａ，Ｊｉａｎｆｅｎｇ  Ｌｕｏ  ａｎｄ  Ｃｈａｒｌｅｓ  Ｃｈｉａｎｇ  「Ｍｏｄｅｌ  Ｂａｓｅｄ  Ｌａｙｏｕｔ  Ｐａｔｔｅｒｎ  Ｄｅｐｅｎｄｅｎｔ  Ｍｅｔａｌ  Ｆｉｌｌｉｎｇ  Ａｌｇｏｒｉｔｈｍ  ｆｏｒ  Ｉｍｐｒｏｖｅｄ  Ｃｈｉｐ  Ｓｕｒｆａｃｅ  Ｕｎｉｆｏｒｍｉｔｙ  ｉｎ  ｔｈｅ  Ｃｏｐｐｅｒ  Ｐｒｏｃｅｓｓ」  Ｊａｎ．２３．２００７  ＩＥＥＥ
【非特許文献２】Ｊ．Ｌｕｏ，Ｑ．Ｓｕ，Ｃ．Ｃｈｉａｎｇ  ａｎｄ  Ｊ．Ｋａｗａ  「Ａ  Ｌａｙｏｕｔ  Ｄｅｐｅｎｄｅｎｔ  Ｆｕｌｌ−Ｃｈｉｐ  Ｃｏｐｐｅｒ  Ｅｌｅｃｔｒｏｐｌａｔｉｎｇ  Ｔｏｐｏｇｒａｐｈｙ  Ｍｏｄｅｌ，ＩＣＣＡＤ  ２００５」
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、上述した従来技術によれば、エッジ長の均一性を考慮した配線のレイアウトがおこなわれていないため、配線後における各メッシュの配線のエッジ長が大きくばらついてしまう場合がある。これにより、研磨後の基板表面の凹凸が増大し、半導体デバイスの性能劣化を招いてしまうという問題があった。
【０００７】
また、非特許文献１に記載されているように、配線後において、各メッシュの配線密度およびエッジ長を均一化させるために、ダミー配線を挿入することも考えられる。しかし、配線後の様々な配線パターンを考慮したダミー配線を保持するライブラリを作成する必要がある。このため、ライブラリ作成にかかる作業負担が増大するとともに、メモリの記憶内容が増大してしまうという問題があった。
【０００８】
一方で、代表的な形状のダミー配線だけを保持することも考えられるが、例えば、配線密度が極端に小さく、エッジ長が極端に大きい場合など、配線後のメッシュの配線密度およびエッジ長が想定外のものとなった場合には、適切なダミー配線を挿入することができず、結果的に配線密度およびエッジ長を均一化することができないという問題があった。
【０００９】
この発明は、上述した従来技術による問題点を解消するため、配線の配線密度およびエッジ長を均一化することにより、研磨後の基板表面の平坦性を向上させるレイアウト設計プログラム、該プログラムを記録した記録媒体、レイアウト設計装置、およびレイアウト設計方法を提供することを目的とする。
【課題を解決するための手段】
【００１０】
上述した課題を解決し、目的を達成するため、このレイアウト設計プログラム、該プログラムを記録した記録媒体、レイアウト設計装置、およびレイアウト設計方法は、設計対象回路のレイアウト領域を区切って分割された部分領域ごとの配線のエッジ長に基づいて、前記レイアウト領域に配置されたセル間の配線経路を探索し、探索された探索結果を出力することを要件とする。
【００１１】
このレイアウト設計プログラム、該プログラムを記録した記録媒体、レイアウト設計装置、およびレイアウト設計方法によれば、部分領域の配線のエッジ長を考慮した配線経路を探索することにより、配線後におけるレイアウト領域全体における配線のエッジ長のばらつきを抑えることができる。
【００１２】
また、このレイアウト設計プログラム、該プログラムを記録した記録媒体、レイアウト設計装置、およびレイアウト設計方法は、特定の部分領域まで探索された場合、前記特定の部分領域に隣接する部分領域のうち、探索済みの部分領域を除く他の部分領域の配線のエッジ長を取得し、取得された取得結果に基づいて、前記特定の部分領域の探索先の部分領域を決定することとしてもよい。
【００１３】
また、このレイアウト設計プログラム、該プログラムを記録した記録媒体、レイアウト設計装置、およびレイアウト設計方法は、取得された配線のエッジ長が最小となる部分領域を前記探索先の部分領域に決定することとしてもよい。
【００１４】
これらのレイアウト設計プログラム、該プログラムを記録した記録媒体、レイアウト設計装置、およびレイアウト設計方法によれば、探索途中の任意の部分領域において、配線の配線密度が最小となる部分領域を探索先の部分領域に決定することにより、各部分領域の配線の配線密度の最大値を抑えることができる。
【００１５】
また、このレイアウト設計プログラム、該プログラムを記録した記録媒体、レイアウト設計装置、およびレイアウト設計方法は、デザインルールに従って探索された前記セル間の配線経路候補を取得し、取得された配線経路候補の中から、当該配線経路候補が経由する全ての部分領域の配線のエッジ長が最小となる配線経路候補を前記セル間の配線経路に決定することとしてもよい。
【００１６】
このレイアウト設計プログラム、該プログラムを記録した記録媒体、レイアウト設計装置、およびレイアウト設計方法によれば、デザインルールを満たす配線経路候補が複数存在する場合、配線のエッジ長の累積値が最小となる配線経路候補を配線経路に決定することにより、各部分領域の配線の配線密度の最大値を抑えることができる。
【００１７】
また、このレイアウト設計プログラム、該プログラムを記録した記録媒体、レイアウト設計装置、およびレイアウト設計方法は、さらに、前記部分領域ごとの配線の配線密度に基づいて、前記セル間の配線経路を探索することとしてもよい。
【００１８】
このレイアウト設計プログラム、該プログラムを記録した記録媒体、レイアウト設計装置、およびレイアウト設計方法によれば、各部分領域の配線の配線密度を考慮した配線経路を探索することにより、配線後におけるレイアウト領域全体における配線の配線密度のばらつきを抑えることができる。
【００１９】
また、このレイアウト設計プログラム、該プログラムを記録した記録媒体、レイアウト設計装置、およびレイアウト設計方法は、探索された配線経路が経由する部分領域ごとの配線密度およびエッジ長を算出し、算出された配線密度に基づいて、前記部分領域の配線密度が、予め設定された配線密度に関する制限値以上であるか否かを判断し、算出されたエッジ長に基づいて、前記配線密度に関する制限値未満と判断された部分領域の空き領域にダミー配線を挿入し、前記ダミー配線が挿入された挿入結果を出力することとしてもよい。
【００２０】
また、このレイアウト設計プログラム、該プログラムを記録した記録媒体、レイアウト設計装置、およびレイアウト設計方法は、前記配線密度に関する制限値未満と判断された部分領域の前記配線密度に関する制限値に達していない未達の配線密度に基づいて、前記ダミー配線の寸法を算出することとしてもよい。
【００２１】
これらのレイアウト設計プログラム、該プログラムを記録した記録媒体、レイアウト設計装置、およびレイアウト設計方法によれば、配線後において配線の配線密度が小さい部分領域に、電気信号の伝達とは無関係のダミー配線を挿入することにより、各部分領域の配線の配線密度の最小値を抑えることができる。
【００２２】
また、このレイアウト設計プログラム、該プログラムを記録した記録媒体、レイアウト設計装置、およびレイアウト設計方法は、前記配線密度に関する制限値未満と判断された部分領域のエッジ長が、予め設定されたエッジ長に関する制限値以上であるか否かを判断し、判断された判断結果に基づいて、前記ダミー配線の寸法を算出し、算出された寸法のダミー配線を前記空き領域に挿入することとしてもよい。
【００２３】
また、このレイアウト設計プログラム、該プログラムを記録した記録媒体、レイアウト設計装置、およびレイアウト設計方法は、前記配線密度に関する制限値未満と判断された部分領域の前記エッジ長に関する制限値に達していない未達のエッジ長に基づいて、前記ダミー配線の寸法を算出することとしてもよい。
【００２４】
これらのレイアウト設計プログラム、該プログラムを記録した記録媒体、レイアウト設計装置、およびレイアウト設計方法によれば、エッジ長に関する制限値に達していない未達のエッジ長を考慮した寸法のダミー配線を挿入することにより、各部分領域の配線のエッジ長の最小値を抑えることができる。
【００２５】
また、このレイアウト設計プログラム、該プログラムを記録した記録媒体、レイアウト設計装置、およびレイアウト設計方法は、前記ダミー配線の寸法の指定を受け付け、前記ダミー配線が挿入された結果、前記部分領域の配線密度が前記配線密度に関する制限値以上となったか否かを判断し、前記制限値未満と判断された場合、前記空き領域に挿入済みのダミー配線に替えて、寸法が指定されたダミー配線を前記空き領域に挿入することとしてもよい。
【００２６】
このレイアウト設計プログラム、該プログラムを記録した記録媒体、レイアウト設計装置、およびレイアウト設計方法によれば、任意の寸法のダミー配線を挿入することができる。
【発明の効果】
【００２７】
このレイアウト設計プログラム、該プログラムを記録した記録媒体、レイアウト設計装置、およびレイアウト設計方法によれば、配線の配線密度およびエッジ長を均一化することにより、研磨後の基板表面の平坦性を向上させることができるという効果を奏する。
【発明を実施するための最良の形態】
【００２８】
以下に添付図面を参照して、このレイアウト設計プログラム、該プログラムを記録した記録媒体、レイアウト設計装置、およびレイアウト設計方法の好適な実施の形態を詳細に説明する。
【００２９】
（レイアウト設計装置のハードウェア構成）
まず、本実施の形態にかかるレイアウト設計装置のハードウェア構成について説明する。図１は、本実施の形態にかかるレイアウト設計装置のハードウェア構成を示す説明図である。
【００３０】
図１において、レイアウト設計装置１００は、コンピュータ本体１１０と、入力装置１２０と、出力装置１３０と、から構成されており、不図示のルータやモデムを介してＬＡＮ，ＷＡＮやインターネットなどのネットワーク１４０に接続可能である。
【００３１】
コンピュータ本体１１０は、ＣＰＵ，メモリ，インターフェースを有する。ＣＰＵは、レイアウト設計装置１００の全体の制御を司る。メモリは、ＲＯＭ，ＲＡＭ，ＨＤ，光ディスク１１１，フラッシュメモリから構成される。メモリはＣＰＵのワークエリアとして使用される。
【００３２】
また、メモリには各種プログラムが格納されており、ＣＰＵからの命令に応じてロードされる。ＨＤおよび光ディスク１１１はディスクドライブによりデータのリード／ライトが制御される。また、光ディスク１１１およびフラッシュメモリはコンピュータ本体１１０に対し着脱自在である。インターフェースは、入力装置１２０からの入力、出力装置１３０への出力、ネットワーク１４０に対する送受信の制御をおこなう。
【００３３】
また、入力装置１２０としては、キーボード１２１、マウス１２２、スキャナ１２３などがある。キーボード１２１は、文字、数字、各種指示などの入力のためのキーを備え、データの入力をおこなう。また、タッチパネル式であってもよい。マウス１２２は、カーソルの移動や範囲選択、あるいはウィンドウの移動やサイズの変更などをおこなう。スキャナ１２３は、画像を光学的に読み取る。読み取られた画像は画像データとして取り込まれ、コンピュータ本体１１０内のメモリに格納される。なお、スキャナ１２３にＯＣＲ機能を持たせてもよい。
【００３４】
また、出力装置１３０としては、ディスプレイ１３１、スピーカ１３２、プリンタ１３３などがある。ディスプレイ１３１は、カーソル、アイコンあるいはツールボックスをはじめ、文書、画像、機能情報などのデータを表示する。また、スピーカ１３２は、効果音や読み上げ音などの音声を出力する。また、プリンタ１３３は、画像データや文書データを印刷する。
【００３５】
（本実施の形態の概要）
つぎに、本実施の形態の概要について説明する。一般に、半導体デバイス製造における配線工程では、銅メッキなどが施された基板表面上をＣＭＰ技術によって研磨することにより、多層配線プロセスの各層を平坦化させている。このとき、配線の配線密度の分布がレイアウト全体にわたって均一であるほうが望ましい。
【００３６】
なぜなら、配線の配線密度の分布が不均一になると、配線メタルと絶縁体の材質の違いにより、研磨後の基板表面の凹凸が増大してしまうためである。従来においては、電気信号の伝達とは無関係のダミー配線をレイアウト上の空き領域に挿入することにより、配線密度を均一化する手法がとられている。
【００３７】
しかし、配線の配線密度が均一化されたとしても、基板表面を十分に平坦化することができない。なぜなら、研磨後の平坦性は、配線の配線密度だけでなく配線のエッジ長にも依存しており、エッジ長の分布が不均一となってしまった場合には、上記同様に基板表面の凹凸が増大してしまう。
【００３８】
ここで、従来の問題点を具体的に説明する。図２は、半導体集積回路の一例を示す説明図である。図２において、半導体集積回路２００は、複数の部分領域（例えば、部分領域２１０）に分割されている。具体的には、半導体集積回路２００をメッシュ状に区切ることにより、１辺の長さがＸ［μｍ］の正方領域に分割されている。
【００３９】
ここで、部分領域２１０を例に挙げると、部分領域２１０には、配線幅がｐ［μｍ］の配線Ｗ１，Ｗ２が形成されている。このとき、部分領域２１０のエッジ長（２１０中の太線部分）は、配線Ｗ１のエッジ長：２Ｘ［μｍ］と、配線Ｗ２のエッジ長：（ｐ＋２ｑ）［μｍ］とを加算した値：（２Ｘ＋ｐ＋２ｑ）［μｍ］である。
【００４０】
このように、部分領域の配線の配線密度およびエッジ長は、その部分領域内の配線パターンに応じてそれぞれ異なる。例えば、部分領域の１辺の長さに比べて配線幅の小さい配線が複数形成される場合には、他の部分領域に比べて配線のエッジ長は大きくなる傾向にある。一方で、配線幅の大きい配線が形成される場合には、他の部分領域に比べて配線のエッジ長は小さくなる傾向にある。
【００４１】
図３は、従来の問題点を示す説明図である。図３において、部分領域３１０，３２０および３３０の断面図が示されている。なお、これら断面図は、例えば、図２に示した半導体集積回路２００を点線Ｉ−Ｉ’に沿って垂直に切断したときの断面図である。図３に示すように、各部分領域３１０，３２０および３３０には、それぞれ異なる配線パターンの配線が形成されている。
【００４２】
このため、部分領域３１０〜３３０の配線のエッジ長はそれぞれ異なるものとなっている。具体的には、部分領域３１０の配線のエッジ長はＰ［μｍ］であり、部分領域３２０の配線のエッジ長はＱ［μｍ］であり、部分領域３３０の配線のエッジ長はＲ［μｍ］である。ただし、Ｐ＞Ｑ＞Ｒとする。なお、部分領域３１０〜３３０の配線の配線密度は、５０［％］で均一化されている。
【００４３】
このとき、研磨後の基板表面の凹凸は、各部分領域３１０〜３３０で異なるものとなっている。ここでは、部分領域３２０の基板表面が最も平坦化されている。すなわち、部分領域３１０〜３３０の配線の配線密度が均一化された場合であっても、配線のエッジ長の違いにより研磨後の基板表面の凹凸が変化している。
【００４４】
この結果、例えば、凹部では、配線メタルの削りすぎによる配線抵抗の増大化を招いてしまい、回路性能を悪化させる場合がある。また、凸部では、余分に残った配線メタルが焦点ずれの原因となり、配線幅のばらつきが増大してしまう場合がある。
【００４５】
そこで、本実施の形態では、まず、配線のレイアウトを決定するときに、各部分領域の配線の配線密度およびエッジ長の最大値を制限する。さらに、配線のレイアウト後において、配線の配線密度が小さい部分領域にダミー配線を挿入することにより、各部分領域の配線の配線密度およびエッジ長の最小値を制限する。これにより、各部分領域の配線の配線密度およびエッジ長を一定の範囲内に抑え、研磨後の基板表面の凹凸差を低減させる。
【００４６】
（レイアウト設計装置の機能的構成）
つぎに、レイアウト設計装置１００の機能的構成について説明する。図４は、本実施の形態にかかるレイアウト設計装置の機能的構成を示すブロック図である。図４において、レイアウト設計装置１００は、探索部４０１と、取得部４０２と、決定部４０３と、出力部４０４と、算出部４０５と、判断部４０６と、挿入部４０７と、指定部４０８と、を備えている。
【００４７】
これら各機能４０１〜４０８は、レイアウト設計装置１００の記憶部に記憶された当該機能４０１〜４０８に関するプログラムをＣＰＵに実行させることにより、または、入出力Ｉ／Ｆにより、当該機能を実現することができる。また、各機能４０１〜４０８からの出力データは上記記憶部に保持される。また、図４中矢印で示した接続先の機能は、接続元の機能からの出力データを記憶部から読み込んで、当該機能に関するプログラムをＣＰＵに実行させるものとする。
【００４８】
まず、探索部４０１は、設計対象回路のレイアウト領域を区切って分割された部分領域ごとの配線のエッジ長に基づいて、レイアウト領域に配置されたセル間の配線経路を探索する機能を有する。ここで、配線のエッジ長とは、配線の周囲長である。
【００４９】
具体的には、例えば、まず、設計対象回路に関する回路情報に基づいて、設計対象回路のレイアウト領域をメッシュ状に区切って複数の部分領域に分割する。回路情報は、設計対象回路（例えば、図２に示した半導体集積回路２００）のネットリストやフロアプラン情報を含む電子データである。
【００５０】
この回路情報は、不図示の外部装置から取得することとしてもよく、また、ユーザの操作入力、不図示のデータベースやライブラリからの抽出によって取得することとしてもよい。また、分割する部分領域の形状や寸法などは、例えば、図１に示したキーボード１２１やマウス１２２などをユーザが操作することで任意に設定可能である。
【００５１】
複数の部分領域に分割された結果、探索部４０１は、レイアウト領域に配置されている複数のセルの中から配線接続対象となるセル群を抽出し、それらセル間の配線経路を探索する。このとき、部分領域ごとの配線のエッジ長を判断して、接続元のセルから接続先のセルまでの配線経路を探索する。
【００５２】
なお、探索部４０１による探索処理は配線接続対象となるセル群が未抽出となるまで繰り返し実行される。このため、各部分領域の配線のエッジ長は、配線経路が探索されるごとに変化することとなる。つまり、探索部４０１は、逐次変化する部分領域ごとの配線のエッジ長を判断して、配線接続対象となるセル間の配線経路を探索することとなる。
【００５３】
取得部４０２は、特定の部分領域まで探索された場合、特定の部分領域に隣接する部分領域のうち、探索済みの部分領域を除く他の部分領域（以下、「隣接領域」という）の配線のエッジ長を取得する機能を有する。特定の部分領域とは、例えば、探索途中に経由する任意の部分領域であってもよく、また、接続元のセルが配置されている部分領域であってもよい。
【００５４】
具体的には、例えば、任意の配線アルゴリズムを用いて配線経路を探索途中に経由する部分領域である。より具体的には、例えば、配線の配線長や混雑度に関する規定やデザインルールに従って、セル間の配線経路を探索途中に経由する部分領域である。なお、デザインルールとは、配線のレイアウトがプロセス設計ルールに合っているか否かをチェックするための規定である。
【００５５】
また、隣接領域の配線のエッジ長は、例えば、後述する算出部４０５によって、特定の部分領域まで探索されたときに算出される。あるいは、セル間の配線経路が探索された場合に、その都度、部分領域ごとの配線のエッジ長が算出されることとしてもよい。算出部４０５によって算出された算出結果は、例えば、ＲＯＭやＲＡＭなどのメモリに記憶される。そして、取得部４０２により、特定の部分領域まで探索された場合に、隣接領域の配線のエッジ長がメモリから読み出される。
【００５６】
決定部４０３は、取得部４０２によって取得された取得結果に基づいて、特定の部分領域の探索先の部分領域を決定する機能を有する。具体的には、例えば、取得部４０２によって取得された配線のエッジ長が最小となる部分領域を探索先の部分領域に決定することとしてもよい。
【００５７】
これにより、各部分領域の配線のエッジ長の最大値を抑えることができ、レイアウト領域全体における配線のエッジ長のばらつきを低減させることができる。なお、隣接領域に接続先のセルが配置されている部分領域が含まれている場合には、その部分領域を探索先の部分領域に決定することとしてもよい。
【００５８】
また、取得部４０２は、デザインルールに従って探索されたセル間の配線経路候補を取得することとしてもよい。具体的には、例えば、プロセス設計ルールなどを考慮したセル間の配線経路候補を予め探索し、その探索結果を取得部４０２によって取得する。
【００５９】
この場合、決定部４０３は、取得部４０２によって取得された配線経路候補の中から、当該配線経路候補が経由する全ての部分領域の配線のエッジ長が最小となる配線経路候補をセル間の配線経路に決定することとしてもよい。つまり、配線経路候補が複数存在する場合に、各配線経路候補の経路上に位置する部分領域の配線のエッジ長の累積値が最小となる配線経路候補をセル間の配線経路に決定する。
【００６０】
また、探索部４０１は、部分領域ごとの配線の配線密度に基づいて、セル間の配線経路を探索することとしてもよい。ここで、配線の配線密度とは、例えば、部分領域の表面積に対する該部分領域に形成されている配線の表面積の割合である。具体的には、例えば、取得部４０２により、特定の部分領域まで探索された場合に、隣接領域の配線の配線密度を取得する。隣接領域の配線の配線密度は、例えば、上述した配線のエッジ長と同様に、後述する算出部４０５によって算出される。
【００６１】
この場合、決定部４０３は、取得部４０２によって取得された配線の配線密度が最小となる部分領域を探索先の部分領域に決定することとしてもよい。これにより、各部分領域の配線の配線密度の最大値を抑えることができ、レイアウト領域全体における配線の配線密度のばらつきを低減させることができる。
【００６２】
また、決定部４０３は、取得部４０２によって取得された配線経路候補の中から、当該配線経路候補が経由する全ての部分領域の配線の配線密度が最小となる配線経路候補をセル間の配線経路に決定することとしてもよい。つまり、配線経路候補が複数存在する場合に、各配線経路候補の経路上に位置する部分領域の配線の配線密度の累積値が最小となる配線経路候補をセル間の配線経路に決定する。
【００６３】
また、取得部４０２は、部分領域ごとの配線コストを取得することとしてもよい。配線コストは、例えば、部分領域ごとの配線の配線密度、エッジ長、配線長、混雑度およびデザインルールなどに基づいて算出される配線の困難性を表わす指標である。具体的には、例えば、配線コストが高いほど配線の困難性が高く、配線コストが低いほど配線の容易性が高いことを意味している。
【００６４】
配線コストの算定ルールは、任意に設定可能である。例えば、配線の配線密度が予め設定された閾値以上の場合に「ｊ」を加算し、デザインルールに違反する場合に「ｋ」を加算するなどの算定ルールを設定することができる。この場合、決定部４０３は、例えば、取得部４０２によって取得された部分領域ごとの配線コストが最小となる部分領域を探索先の部分領域に決定することとしてもよい。
【００６５】
ここで、配線コストに基づいて、探索先の部分領域を決定する処理の具体例について説明する。図５は、配線経路の一例を示す説明図である。図５において、レイアウト領域５００には、配線接続対象となるセル間の配線経路Ｒが示されている。この配線経路Ｒは、接続元のセルが配置されている部分領域５１０から接続先のセルが配置されている部分領域５２０までの経路である。
【００６６】
また、レイアウト領域５００には、部分領域ごとの配線コストを表わす数値が示されている。ここでは、決定部４０３は、部分領域５１０から部分領域５２０に辿り着くまでに経由する各部分領域において、その各部分領域の隣接領域のうち配線コストが最小となる部分領域を探索先の部分領域に決定する。
【００６７】
ここで、探索途中に経由する部分領域５３０を例に挙げると、隣接領域５４０，５５０，５６０のうち、配線コストが最小となる部分領域５６０を探索先の部分領域に決定している。このように、探索途中の各部分領域において配線コストが最小となる部分領域を探索先の部分領域に決定することにより、部分領域５１０から部分領域５２０までの配線経路Ｒが探索される。
【００６８】
出力部４０４は、探索部４０１によって探索された探索結果を出力する機能を有する。具体的には、例えば、レイアウト領域に配置されている配線接続対象となるセル間の配線経路が探索された探索結果を表わすレイアウト情報などを出力することとしてもよい。出力部４０４による出力形式は、ディスプレイ１３１での画面表示、プリンタ１３３での印刷出力、メモリへのデータ出力（保存）、外部のコンピュータ装置への送信のいずれであってもよい。
【００６９】
算出部４０５は、探索部４０１によって探索された配線経路が経由する部分領域ごとの配線密度およびエッジ長を算出する機能を有する。具体的には、例えば、探索部４０１によって探索された探索結果を表わすレイアウト情報に基づいて、部分領域ごとの配線密度およびエッジ長を算出することができる。レイアウト情報とは、例えば、ＧＤＳＩＩデータなどのマスクパターンを記述するためのバイナリ形式の電子データである。
【００７０】
判断部４０６は、算出部４０５によって算出された配線密度に基づいて、部分領域の配線密度が、予め設定された配線密度に関する制限値以上であるか否かを判断する機能を有する。配線密度に関する制限値は、例えば、ＣＭＰシミュレーション結果や過去の実測値（凹凸の高低差など）から判断され、図１に示したキーボード１２１やマウス１２２などをユーザが操作することで任意に設定可能である。
【００７１】
この制限値は、特定の数値または範囲のいずれであってもよい。配線密度に関する制限値として特定の範囲が設定されている場合には、判断部４０６は、部分領域の配線密度が、予め設定された配線密度に関する制限範囲内であるか否かを判断することとなる。さらに、この制限値は、特定の範囲とともに目標値を設定することとしてもよい。具体的には、例えば、制限値Ａ［％］は、「範囲：４０≦Ａ≦８０、目標値：Ａ＝７０」のように設定することとしてもよい。
【００７２】
ここで、算出部４０５による算出結果の具体例を説明する。図６は、算出結果の一例を示す説明図である。ここでは、設計対象回路のレイアウト領域をｎ個の部分領域に分割した場合を例に挙げて説明する。図６において、算出結果６００は、部分領域Ａ−１〜Ａ−ｎごとに、配線情報６００−１〜６００−ｎを有している。
【００７３】
具体的には、配線情報６００−１〜６００−ｎは、部分領域Ａ−１〜Ａ−ｎごとに、部分領域ＩＤ、配線の配線密度およびエッジ長を表わす情報を有している。部分領域ＩＤは、各部分領域Ａ−１〜Ａ−ｎを識別するための情報である。配線密度は、各部分領域Ａ−１〜Ａ−ｎの配線の配線密度を表わす情報である。エッジ長は、各部分領域Ａ−１〜Ａ−ｎの配線のエッジ長を表わす情報である。
【００７４】
ここで、配線情報６００−ｉを例に挙げると、部分領域Ａ−ｉの配線の配線密度は５０［％］であり、配線のエッジ長は２００［μｍ］である。このとき、例えば、配線の配線密度に関する制限値が７０［％］に設定されている場合、判断部４０６は、部分領域Ａ−ｉの配線密度は制限値未満であると判断する。
【００７５】
挿入部４０７は、算出部４０５によって算出されたエッジ長に基づいて、判断部４０６によって配線密度に関する制限値未満と判断された部分領域の空き領域にダミー配線を挿入する機能を有する。ダミー配線とは、電気信号の伝達とは無関係のダミーのメタル配線である。ダミー配線の形状は、任意に設定可能であり、例えば、長方形、三角形、円形などであってもよい。
【００７６】
具体的には、算出部４０５は、配線密度に関する制限値未満と判断された部分領域（以下、「挿入対象領域」という）の該制限値に達していない未達の配線密度に基づいて、ダミー配線の寸法を算出する。より具体的には、例えば、挿入対象領域の配線密度が予め設定された範囲の下限値未満と判断された場合、挿入対象領域の配線密度が予め設定された目標値となる配線密度のダミー配線の寸法を算出する。
【００７７】
そして、挿入部４０７は、算出部４０５によって算出された寸法のダミー配線を挿入対象領域の空き領域に挿入する。これにより、各部分領域の配線の配線密度の最小値を抑えることができ、レイアウト領域全体における配線の配線密度のばらつきを低減させることができる。
【００７８】
また、ダミー配線の寸法を算出する際に、挿入対象領域の配線のエッジ長を考慮することとしてもよい。具体的には、判断部４０６は、挿入対象領域のエッジ長が、予め設定されたエッジ長に関する制限値以上であるか否かを判断する。エッジ長に関する制限値は、上述した配線密度に関する制限値と同様に、例えば、図１に示したキーボード１２１やマウス１２２などをユーザが操作することで任意に設定可能である。
【００７９】
そして、算出部４０５は、判断部４０６によって判断された判断結果に基づいて、ダミー配線の寸法を算出する。具体的には、例えば、判断部４０６によってエッジ長に関する制限値未満と判断された部分領域の当該エッジ長に関する制限値に達していない未達のエッジ長に基づいて、ダミー配線の寸法を算出することとしてもよい。
【００８０】
より具体的には、例えば、挿入対象領域のエッジ長が予め設定された範囲の下限値未満と判断された場合、挿入対象領域のエッジ長が予め設定された目標値となるエッジ長のダミー配線の寸法を算出する。そして、挿入部４０７は、算出部４０５によって算出された寸法のダミー配線を挿入対象領域の空き領域に挿入する。これにより、各部分領域の配線のエッジ長の最小値を抑えることができ、レイアウト領域全体における配線のエッジ長のばらつきを低減させることができる。
【００８１】
なお、ダミー配線の寸法を算出するときに、配線のエッジ長に関する制限値よりも配線の配線密度に関する制限値を優先することとしてもよい。具体的には、例えば、エッジ長に関する制限値を満たす寸法が算出された結果、配線密度に関する制限値を超えてしまう場合には、配線密度に関する制限値を満たす範囲内でかつ可能な限りエッジ長の制限値を満たす寸法を新たに算出する。一方で、例えば、配線密度に関する制限値を満たす寸法が算出された結果、エッジ長に関する制限値を超える場合には、配線密度に関する制限値を優先して寸法の再計算はおこなわないこととしてもよい。
【００８２】
ここで、ダミー配線の寸法を算出する処理の具体例について説明する。以下、図６に示した配線情報６００−ｉを用いて、部分領域Ａ−ｉに挿入されるダミー配線の寸法を算出する。図７は、部分領域の一例を示す説明図である。図７において、部分領域Ａ−ｉは、１辺の長さが４０［μｍ］の正方領域（全面積：１６００［μｍ２］）である。
【００８３】
また、部分領域Ａ−ｉの配線の配線密度は５０［％］であり、エッジ長は２００［μｍ］である（配線情報６００−ｉ参照）。このとき、各部分領域の配線密度に関する制限値Ａ［％］が「４０≦Ａ≦８０」に、エッジ長に関する制限値Ｂ［μｍ］が「１０００≦Ｂ≦４０００」に設定されているとする。
【００８４】
また、制限値Ａの目標値が７０［％］に、制限値Ｂの目標値が２０００［μｍ］に設定されている。なお、この目標値は、配線密度およびエッジ長の最適値を表わすものであり、必ずしも満たすべき数値ではない。さらに、ダミー配線Ｄ１の形状が長方形（辺の長さ：ｘ［μｍ］，ｙ［μｍ］）に限定されており、１辺の最小寸法（０．５［μｍ］）および最小の変更寸法（０．１［μｍ］）が予め設定されている。
【００８５】
まず、配線情報６００−ｉに基づいて、制限値Ａ，Ｂの範囲内となる増加分の配線密度およびエッジ長と、制限値Ａ，Ｂの目標値までの配線密度およびエッジ長とを算出する。ここで、ダミー配線Ｄ１を挿入することによって増加する配線密度をａ［％］、エッジ長をｂ［μｍ］とする。この場合、制限値Ａの範囲内となる増加分の配線密度は「０≦ａ≦３０」であり、制限値Ｂの範囲内となる増加分のエッジ長は「８００≦ｂ≦３８００」となる。
【００８６】
また、制限値Ａの目標値までの配線密度は２０［％］（３２０［μｍ２］）であり、制限値Ｂの目標値までのエッジ長は１８００［μｍ］である。そして、これら目標値までの配線密度およびエッジ長に基づいて、部分領域Ａ−ｉの配線の配線密度およびエッジ長が目標値となる最適なダミー配線Ｄ１の寸法および個数を算出する。
【００８７】
例えば、まず、ダミー配線Ｄ１の１辺の長さを『ｘ＝０．７［μｍ］』に固定して、もう一辺の長さｙ［μｍ］を適切に決定する。このとき、制限値Ａの目標値までの配線密度（３２０［μｍ２］）と制限値Ｂの目標値までのエッジ長（１８００［μｍ］）との比率に基づいて、ｙ［μｍ］の数値を決定することとしてもよい。
【００８８】
具体的には、下記式（１）に示すように、ダミー配線Ｄ１の表面積（０．７×ｙ［μｍ２］）とダミー配線Ｄ１のエッジ長（２×（０．７＋ｙ）［μｍ］）との比率が、制限値Ａの目標値までの配線密度と制限値Ｂの目標値までのエッジ長との比率となるｙ［μｍ］の数値を算出する。
【００８９】
３２０／１８００＝（０．７×ｙ）／２×（０．７＋ｙ）…（１）
【００９０】
上記式（１）を用いてダミー配線Ｄ１の１辺の長さｙ［μｍ］を算出すると、「ｙ≒０．７」となる。この結果、ダミー配線Ｄ１の寸法が『ｘ＝０．７，ｙ＝０．７』と決定される。さらに、制限値Ａの目標値までの配線密度（３２０［μｍ２］）をダミー配線Ｄ１の表面積（０．４９［μｍ２］）で割り算することにより、ダミー配線の個数を算出することができる。ここでは、ダミー配線Ｄ１の個数は、６５３［個］（３２０／０．４９≒６５３）となる。
【００９１】
なお、ダミー配線Ｄ１の固定する１辺の長さは、予め設定されている数値群（例えば、「０．５，０．６，０．７，０．８，…」）の中から任意に選択することとしてもよい。また、ダミー配線Ｄ１の形状を、選択された数値を１辺の長さとする正方形に限定することとしてもよい。さらに、ダミー配線Ｄ１の配線幅が限定されている場合には、ダミー配線Ｄ１の１辺を、その配線幅に固定することとしてもよい。
【００９２】
このあと、挿入部４０７により、算出部４０５によって算出された寸法のダミー配線Ｄ１を挿入対象領域の空き領域に挿入する。このとき、個々のダミー配線Ｄ１が重なり合わないように、かつ、隣接しないように挿入する。具体的には、例えば、設計対象回路に関する幾何データ構造やビットマップなどを用いて、ダミー配線Ｄ１の挿入位置を正確に判断する。
【００９３】
ここで、挿入部４０７による挿入処理の具体例について説明する。図８は、挿入処理の概要を示す説明図である。図８において、挿入対象領域８００がメッシュ状に区切られている。まず、探索部４０１の探索結果に基づいて、挿入対象領域８００に形成されている配線の配線位置を特定し、特定された配線位置を塗りつぶす（１）。
【００９４】
このあと、デザインルールなどに従って最低限必要となる配線とダミー配線との間の最低必要間隔位置を特定し、特定された最低必要間隔位置を塗りつぶす（２）。このあと、既に塗りつぶされた領域を除く空き領域のうち、ダミー配線を挿入する挿入位置を特定し、特定された挿入位置を塗りつぶす（３）。
【００９５】
このとき、個々のダミー配線が重ならないように挿入位置を特定する。最後に、挿入部４０７は、上記（１）〜（３）の処理結果を表わすビットマップデータに基づいて、挿入対象領域８００の空き領域にダミー配線を挿入する。
【００９６】
図４の説明に戻り、判断部４０６は、挿入部４０７によってダミー配線が挿入された結果、挿入対象領域の配線密度が、配線密度に関する制限値以上となったか否かを判断する機能を有する。具体的には、例えば、算出部４０５によってダミー配線挿入後の挿入対象領域の配線密度を算出し、その算出結果が配線密度に関する制限値以上となったか否かを判断する。
【００９７】
このとき、算出部４０５は、判断部４０６によって制限値未満と判断された場合、挿入済みのダミー配線の寸法とは異なる寸法を新たに算出することとしてもよい。この場合、挿入部４０７は、挿入済みのダミー配線に替えて、算出部４０５によって新たに算出された寸法のダミー配線を挿入対象領域の空き領域に挿入することとしてもよい。
【００９８】
このように、判断部４０６によって配線密度に関する制限値以上と判断されるまで、算出部４０５、挿入部４０７および判断部４０６による一連の処理を繰り返し実行することとしてもよい。また、ダミー配線が挿入された結果、判断部４０６によって配線密度に関する制限値未満と判断された場合、ダミー配線の寸法をユーザが任意に変更することができるようにしてもよい。
【００９９】
具体的には、指定部４０８は、ダミー配線の寸法の指定を受け付ける機能を有する。具体的には、例えば、図１に示したキーボード１２１やマウス１２２などをユーザが操作することでダミー配線の寸法を任意に指定することができる。この場合、挿入部４０７は、判断部４０６によって制限値未満と判断された場合、挿入済みのダミー配線に替えて、指定部４０８によって指定された寸法のダミー配線を挿入対象領域の空き領域に挿入することとしてもよい。
【０１００】
さらに、判断部４０６は、算出部４０５によって算出された寸法、または、指定部４０８によって指定された寸法のダミー配線が、挿入対象領域の空き領域に挿入可能か否かを判断することとしてもよい。具体的には、例えば、図８に示したビットマップデータに基づいて、ダミー配線の挿入位置の有無を判断する。このとき、判断部４０６によって挿入不能と判断された場合、算出部４０５によって新たな寸法を算出してもよく、また、指定部４０８によってユーザからの寸法の指定を受け付けてもよい。
【０１０１】
また、出力部４０４は、挿入部４０７によってダミー配線が挿入された挿入結果を出力する機能を有する。具体的には、例えば、挿入対象領域の空き領域にダミー配線が挿入された挿入結果を表わすレイアウト情報（ＧＤＳＩＩデータなど）を出力する。
【０１０２】
ここで、ユーザからの寸法の指定を受け付ける画面例について説明する。図９および図１０は、ディスプレイに表示される画面例を示す説明図である。図９において、ディスプレイ１３１には、挿入対象領域９１０に挿入されるダミー配線９２０の寸法を変更する変更画面９００が表示されている。また、ボックス９３０には、予め設定された目標値に達していない未達の配線密度およびエッジ長が示されている。
【０１０３】
変更画面９００において、カーソルＣを移動させてボタンＢ１，Ｂ２のいずれかをクリックすることにより、ダミー配線９２０の寸法を変更するか否かを選択することができる。具体的には、カーソルＣを移動させてボタンＢ１をクリックすると、図１０に示す変更画面１０００に移行する。また、カーソルＣを移動させてボタンＢ２をクリックすると、寸法の指定操作が終了する。
【０１０４】
変更画面１０００において、カーソルＣを移動させてボタンＢ３をクリックすると、ダミー配線９２０の形状（長方形、三角形、円形など）を選択することができる。ここでは、長方形が選択されている。また、カーソルＣを移動させてボタンＢ４をクリックすると、ダミー配線９２０の寸法を入力することができる。
【０１０５】
ここでは、ダミー配線９２０の各辺の長さ（ｘ［μｍ］，ｙ［μｍ］）を入力することができる。具体的には、カーソルＣをボックス１０１０，１０２０に移動させてクリックし、任意の数値を入力する。このとき、ユーザは、例えば、図９に示したボックス９３０の表示内容を参照して、入力する数値を決定することができる。
【０１０６】
そして、ボックス１０１０または／およびボックス１０２０に数値が入力されると、入力された数値に応じて、ダミー配線９２０の寸法が変化するとともに、ボックス１０３０，１０４０に表示されているダミー配線９２０に関する配線密度（表面積）およびエッジ長の数値が変化する。
【０１０７】
なお、カーソルＣを移動させてボタンＢ５をクリックすると、ダミー配線９２０の形状および寸法が、選択された形状や入力された数値に応じて決定される。また、ボタンＢ６をクリックすると、図９に示した変更画面９００に戻る。このように、ユーザは、変更画面９００，１０００を操作することにより、挿入対象領域９１０に挿入するダミー配線９２０の形状および寸法を任意に指定することができる。
【０１０８】
なお、本実施の形態では、挿入対象領域の配線の配線密度およびエッジ長に応じて、配線ダミーの寸法を算出することとしたが、これに限らない。具体的には、例えば、代表的なダミー配線の寸法を予めライブラリに記憶することとしてもよい。この場合、挿入対象領域の配線の配線密度およびエッジ長に応じたダミー配線の寸法をライブラリから抽出し、抽出された寸法のダミー配線を挿入対象領域の空き領域に挿入する。
【０１０９】
さらに、ダミー配線が挿入された結果、挿入対象領域の配線密度が未だ配線密度に関する制限値に達していない場合には、挿入済みのダミー配線の寸法をもとに新たなダミー配線の寸法を算出することとしてもよい。これにより、ダミー配線の寸法を算出する処理にかかる計算量を削減することができる。
【０１１０】
（レイアウト設計装置のレイアウト設計処理手順）
つぎに、本実施の形態にかかるレイアウト設計装置１００のレイアウト設計処理手順について説明する。図１１は、レイアウト設計装置のレイアウト設計処理手順の一例を示すフローチャートである。図１１のフローチャートにおいて、まず、設計対象回路に関する回路情報が入力されたか否かを判断する（ステップＳ１１０１）。
【０１１１】
ここで、回路情報が入力されるのを待って（ステップＳ１１０１：Ｎｏ）、入力された場合（ステップＳ１１０１：Ｙｅｓ）、探索部４０１により、入力された回路情報に基づいて、設計対象回路のレイアウト領域を区切って分割された部分領域ごとの配線のエッジ長に基づいて、レイアウト領域に配置されたセル間の配線経路を探索する探索処理を実行する（ステップＳ１１０２）。
【０１１２】
このあと、挿入部４０７により、挿入対象領域の空き領域にダミー配線を挿入する挿入処理を実行する（ステップＳ１１０３）。最後に、出力部４０４により、設計対象回路に関するレイアウト情報を出力して（ステップＳ１１０４）、本フローチャートによる一連の処理を終了する。
【０１１３】
これによれば、部分領域の配線のエッジ長を考慮した配線経路を探索することにより、配線後におけるレイアウト領域全体における配線のエッジ長のばらつきを抑えることができる。さらに、配線後において配線の配線密度が小さい部分領域に、ダミー配線を挿入することにより、レイアウト領域全体における配線の配線密度のばらつきを抑えることができる。
【０１１４】
つぎに、図１１に示したステップＳ１１０２の探索処理の処理手順について説明する。図１２は、探索処理の処理手順の一例を示すフローチャートである。図１２のフローチャートにおいて、まず、探索部４０１により、任意の配線アルゴリズムを用いて、設計対象回路のレイアウト領域に配置されたセル間の配線経路の探索を開始する（ステップＳ１２０１）。
【０１１５】
このあと、特定の部分領域まで探索されたか否かを判断する（ステップＳ１２０２）。ここで、特定の部分領域まで探索されるのを待って（ステップＳ１２０２：Ｎｏ）、探索された場合（ステップＳ１２０２：Ｙｅｓ）、取得部４０２により、特定の部分領域に隣接する部分領域のうち探索済みの部分領域を除く部分領域の配線のエッジ長を取得する（ステップＳ１２０３）。
【０１１６】
そして、決定部４０３により、取得部４０２によって取得された取得結果に基づいて、配線のエッジ長が最小となる部分領域を、特定の部分領域の探索先の部分領域に決定する（ステップＳ１２０４）。このあと、配線経路の探索が終了したか否かを判断して（ステップＳ１２０５）、終了した場合（ステップＳ１２０５：Ｙｅｓ）、図１１に示したステップＳ１１０３に移行する。一方、終了していない場合は（ステップＳ１２０５：Ｎｏ）、ステップＳ１２０１に戻る。
【０１１７】
これによれば、探索途中の任意の部分領域において、配線の配線密度が最小となる部分領域を探索先の部分領域に決定することにより、各部分領域の配線の配線密度の最大値を抑えることができる。
【０１１８】
つぎに、図１１に示したステップＳ１１０３の挿入処理の処理手順について説明する。図１３は、挿入処理の処理手順の一例を示すフローチャートである。図１３のフローチャートにおいて、まず、算出部４０５により、ステップＳ１１０２において探索された配線経路が経由する部分領域ごとの配線密度およびエッジ長を算出する（ステップＳ１３０１）。
【０１１９】
このあと、判断部４０６により、ステップＳ１３０１において算出された配線密度に基づいて、部分領域の配線密度が、予め設定された配線密度に関する制限値以上であるか否かを判断する（ステップＳ１３０２）。
【０１２０】
ここで、制限値未満であると判断された場合（ステップＳ１３０２：Ｎｏ）、算出部４０５により、挿入対象領域の配線密度に関する制限値に達していない未達の配線密度に基づいて、ダミー配線の寸法を算出する（ステップＳ１３０３）。
【０１２１】
このあと、挿入部４０７により、ステップＳ１３０３において算出された寸法のダミー配線を挿入対象領域の空き領域に挿入して（ステップＳ１３０４）、図１１に示したステップＳ１１０４に移行する。また、ステップＳ１３０３において、算出部４０５により、さらに、挿入対象領域のエッジ長に関する制限値に達していない未達のエッジ長に基づいて、ダミー配線の寸法を算出することとしてもよい。
【０１２２】
これによれば、配線後において配線の配線密度が小さい部分領域にダミー配線を挿入することにより、各部分領域の配線の配線密度の最小値を抑えることができる。さらに、エッジ長に関する制限値に達していない未達のエッジ長を考慮した寸法のダミー配線を挿入することにより、各部分領域の配線のエッジ長の最小値を抑えることができる。
【０１２３】
以上説明したように、本実施の形態によれば、配線の配線密度およびエッジ長を均一化することにより、研磨後の基板表面の平坦性を向上させることができる。これにより、半導体デバイスの歩留まりを向上させ、高品質な半導体デバイスを早期に提供することができる。
【０１２４】
また、配線後の様々な配線の配線密度およびエッジ長を考慮したダミー配線の寸法を記憶するライブラリが不要となるため、ライブラリ作成にかかる作業負担およびメモリの記憶量を削減することができる。
【０１２５】
なお、本実施の形態で説明したレイアウト設計方法は、予め用意されたプログラムをパーソナル・コンピュータやワークステーションなどのコンピュータで実行することにより実現することができる。このプログラムは、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤなどのコンピュータで読み取り可能な記録媒体に記録され、コンピュータによって記録媒体から読み出されることによって実行される。またこのプログラムは、インターネットなどのネットワークを介して配布することが可能な伝送媒体であってもよい。
【０１２６】
また、本実施の形態で説明したレイアウト設計装置１００は、スタンダードセルやストラクチャードＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ  Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）などの特定用途向けＩＣ（以下、単に「ＡＳＩＣ」と称す）やＦＰＧＡなどのＰＬＤ（Ｐｒｏｇｒａｍｍａｂｌｅ  Ｌｏｇｉｃ  Ｄｅｖｉｃｅ）によっても実現することができる。具体的には、たとえば、上述したレイアウト設計装置１００の機能４０１〜４０８をＨＤＬ記述によって機能定義し、そのＨＤＬ記述を論理合成してＡＳＩＣやＰＬＤに与えることにより、レイアウト設計装置１００を製造することができる。
【０１２７】
上述した実施の形態に関し、さらに以下の付記を開示する。
【０１２８】
（付記１）コンピュータを、
設計対象回路のレイアウト領域を区切って分割された部分領域ごとの配線のエッジ長に基づいて、前記レイアウト領域に配置されたセル間の配線経路を探索する探索手段、
前記探索手段によって探索された探索結果を出力する出力手段、
として機能させることを特徴とするレイアウト設計プログラム。
【０１２９】
（付記２）前記コンピュータを、
特定の部分領域まで探索された場合、前記特定の部分領域に隣接する部分領域のうち、探索済みの部分領域を除く他の部分領域の配線のエッジ長を取得する取得手段、
前記取得手段によって取得された取得結果に基づいて、前記特定の部分領域の探索先の部分領域を決定する決定手段として機能させることを特徴とする付記１に記載のレイアウト設計プログラム。
【０１３０】
（付記３）前記決定手段は、
前記取得手段によって取得された配線のエッジ長が最小となる部分領域を前記探索先の部分領域に決定することを特徴とする付記２に記載のレイアウト設計プログラム。
【０１３１】
（付記４）前記取得手段は、
デザインルールに従って探索された前記セル間の配線経路候補を取得し、
前記決定手段は、
前記取得手段によって取得された配線経路候補の中から、当該配線経路候補が経由する全ての部分領域の配線のエッジ長が最小となる配線経路候補を前記セル間の配線経路に決定することを特徴とする付記２に記載のレイアウト設計プログラム。
【０１３２】
（付記５）前記探索手段は、
さらに、前記部分領域ごとの配線の配線密度に基づいて、前記セル間の配線経路を探索することを特徴とする付記１〜４のいずれか一つに記載のレイアウト設計プログラム。
【０１３３】
（付記６）前記コンピュータを、
前記探索手段によって探索された配線経路が経由する部分領域ごとの配線密度およびエッジ長を算出する算出手段、
前記算出手段によって算出された配線密度に基づいて、前記部分領域の配線密度が、予め設定された配線密度に関する制限値以上であるか否かを判断する判断手段、
前記算出手段によって算出されたエッジ長に基づいて、前記判断手段によって前記配線密度に関する制限値未満と判断された部分領域の空き領域にダミー配線を挿入する挿入手段として機能させ、
前記出力手段は、
前記挿入手段によって前記ダミー配線が挿入された挿入結果を出力することを特徴とする付記１〜５のいずれか一つに記載のレイアウト設計プログラム。
【０１３４】
（付記７）前記判断手段は、
前記配線密度に関する制限値未満と判断された部分領域のエッジ長が、予め設定されたエッジ長に関する制限値以上であるか否かを判断し、
前記算出手段は、
前記判断手段によって判断された判断結果に基づいて、前記ダミー配線の寸法を算出し、
前記挿入手段は、
前記算出手段によって算出された寸法のダミー配線を前記空き領域に挿入することを特徴とする付記６に記載のレイアウト設計プログラム。
【０１３５】
（付記８）前記算出手段は、
前記配線密度に関する制限値未満と判断された部分領域の前記エッジ長に関する制限値に達していない未達のエッジ長に基づいて、前記ダミー配線の寸法を算出することを特徴とする付記７に記載のレイアウト設計プログラム。
【０１３６】
（付記９）前記算出手段は、
前記配線密度に関する制限値未満と判断された部分領域の前記配線密度に関する制限値に達していない未達の配線密度に基づいて、前記ダミー配線の寸法を算出することを特徴とする付記７または８に記載のレイアウト設計プログラム。
【０１３７】
（付記１０）前記コンピュータを、
前記ダミー配線の寸法の指定を受け付ける指定手段として機能させ、
前記判断手段は、
前記挿入手段によって前記ダミー配線が挿入された結果、前記部分領域の配線密度が前記配線密度に関する制限値以上となったか否かを判断し、
前記挿入手段は、
前記判断手段によって制限値未満と判断された場合、前記空き領域に挿入済みのダミー配線に替えて、前記指定手段によって指定された寸法のダミー配線を前記空き領域に挿入することを特徴とする付記６〜９のいずれか一つに記載のレイアウト設計プログラム。
【０１３８】
（付記１１）付記１〜１０のいずれか一つに記載のレイアウト設計プログラムを記録したコンピュータに読み取り可能な記録媒体。
【０１３９】
（付記１２）設計対象回路のレイアウト領域を区切って分割された部分領域ごとの配線のエッジ長に基づいて、前記レイアウト領域に配置されたセル間の配線経路を探索する探索手段と、
前記探索手段によって探索された探索結果を出力する出力手段と、
を備えたことを特徴とするレイアウト設計装置。
【０１４０】
（付記１３）設計対象回路のレイアウト領域を区切って分割された部分領域ごとの配線のエッジ長に基づいて、前記レイアウト領域に配置されたセル間の配線経路を探索する探索工程と、
前記探索工程によって探索された探索結果を出力する出力工程と、
を含んだことを特徴とするレイアウト設計方法。
【図面の簡単な説明】
【０１４１】
【図１】本実施の形態にかかるレイアウト設計装置のハードウェア構成を示す説明図である。
【図２】半導体集積回路の一例を示す説明図である。
【図３】従来の問題点を示す説明図である。
【図４】本実施の形態にかかるレイアウト設計装置の機能的構成を示すブロック図である。
【図５】配線経路の一例を示す説明図である。
【図６】算出結果の一例を示す説明図である。
【図７】部分領域の一例を示す説明図である。
【図８】挿入処理の概要を示す説明図である。
【図９】ディスプレイに表示される画面例を示す説明図（その１）である。
【図１０】ディスプレイに表示される画面例を示す説明図（その２）である。
【図１１】レイアウト設計装置のレイアウト設計処理手順の一例を示すフローチャートである。
【図１２】探索処理の処理手順の一例を示すフローチャートである。
【図１３】挿入処理の処理手順の一例を示すフローチャートである。
【符号の説明】
【０１４２】
１００  レイアウト設計装置
２００  半導体集積回路
２１０，３１０，３２０，３３０  部分領域
４０１  探索部
４０２  取得部
４０３  決定部
４０４  出力部
４０５  算出部
４０６  判断部
４０７  挿入部
４０８  指定部
５００  レイアウト領域
６００  算出結果
６００−１〜６００−ｎ  配線情報
９００，１０００  変更画面
９２０，Ｄ１  ダミー配線
９３０，１０１０，１０２０，１０３０，１０４０  ボックス
【図１】
0005262065.tif 000002
【図２】
0005262065.tif 000003
【図３】
0005262065.tif 000004
【図４】
0005262065.tif 000005
【図５】
0005262065.tif 000006
【図６】
0005262065.tif 000007
【図７】
0005262065.tif 000008
【図８】
0005262065.tif 000009
【図９】
0005262065.tif 000010
【図１０】
0005262065.tif 000011
【図１１】
0005262065.tif 000012
【図１２】
0005262065.tif 000013
【図１３】
0005262065.tif 000014