(57)【要約】【課題】半導体集積回路の自動レイアウト設計において、必要な領域に対しては配線混雑の緩和を行い、かつ、不必要な面積増大を抑制する。【解決手段】単位領域当たりのネットの数の上限をネット密度制約として設定する（ST105）。ネット密度制約を満たすようにセルを配置する（ST106）。セル配置工程（ST106）では、仮配置されたセルのレイアウトに対し、単位領域に存在する端子を抽出する。そして、抽出した端子に接続されるネットをネットリストを参照して抽出する。抽出したネットの数が前記ネット密度制約を満たすようにセルの配置を変更する。【選択図】図2
2012215974.tif 000002
【特許請求の範囲】
【請求項１】
半導体集積回路の自動レイアウト設計方法であって、
単位領域当たりのネットの数の上限をネット密度制約として設定するネット密度設定工程と、
前記ネット密度設定工程で設定された前記ネット密度制約を満たすようにセルを配置するセル配置工程と、を備える
ことを特徴とする半導体集積回路の自動レイアウト設計方法。
【請求項２】
請求項1に記載の半導体集積回路の自動レイアウト設計方法において、
前記セル配置工程の前に、セルを仮配置するセル仮配置工程を備え、
前記セル配置工程は、
前記セル仮配置工程で仮配置されたセルのレイアウトに対し、単位領域に存在する端子を抽出する端子抽出工程と、
前記抽出された端子に接続されるネットをネットリストを参照して抽出するネット抽出工程と、
前記抽出したネットの数が前記ネット密度制約を満たすようにセルの配置を変更するセル配置変更工程と、を備える
ことを特徴とする半導体集積回路の自動レイアウト設計方法。
【請求項３】
請求項2に記載の半導体集積回路の自動レイアウト設計方法において、
前記セル仮配置工程の後、前記セル配置工程の前に、仮配線を行う仮配線工程を備え、
前記ネット抽出工程では、前記単位領域を通過する通過ネットも含めてネットを抽出する
ことを特徴とする半導体集積回路の自動レイアウト設計方法。
【請求項４】
請求項2に記載の半導体集積回路の自動レイアウト設計方法であって、
前記単位領域内の端子に接続されないで前記単位領域を通過する通過ネットの数の上限を通過ネット制約として設定する通過ネット制約設定工程をさらに備え、
前記セル配置工程は、さらに、前記通過ネットの数をカウントする工程を備え、
前記セル配置変更工程では、さらに、前記通過ネットの数が前記通過ネット制約を満たすようにセルの配置を変更する
ことを特徴とする半導体集積回路の自動レイアウト設計方法。
【請求項５】
半導体集積回路の自動レイアウト設計方法であって、
単位領域当たりのネットの数の上限をネット密度制約として設定するネット密度設定工程と、
前記ネット密度設定工程で設定された前記ネット密度制約を満たすようにセルを配置するセル配置工程と、を備える
ことを特徴とする半導体集積回路の自動レイアウト設計方法。
【請求項６】
半導体集積回路の自動レイアウト設計装置であって、
単位領域当たりのネットの数の上限をネット密度制約として設定する制約設定部と、
前記制約設定部で設定された前記ネット密度制約を満たすようにセルを配置するレイアウト処理部と、を備える
ことを特徴とする半導体集積回路の自動レイアウト設計装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、半導体集積回路の設計工程のなかで主としてフロアプランから配線までを行うレイアウト設計に関し、これを自動的に行う半導体集積回路の自動レイアウト装置に関する。例えば、いわゆるEDA（Electronic Design Automation）ツールに関する。
【背景技術】
【０００２】
半導体チップの開発において、チップの小型化およびコスト削減が求められている。チップを小型集積化していく傾向にあるなかで、単純に自動レイアウト装置を使用した自動配線を実行してみると、配線混雑が生じて必要な配線が引けない問題に直面することがしばしば生じる。
【０００３】
従来、配線未収束が生じた場合の調整方法が提案されている（例えば、特許文献1、特許文献2）。特許文献1（特開2007-305699号公報）では、例えばDRAMの自動配線において、同一のネットを構成するピンをサブ幹線で接続しておき、このサブ幹線とメイン幹線とを接続することが提案されている。これにより、引き込み線の数を減らすことができる。
しかし、この方法を適用できるのは、DRAMのように、同一のネットを構成するピンを効果的にグループ化できる場合に限られるのであって、広く半導体集積回路のレイアウト設計に適用できない。
【０００４】
特許文献2には、端子密度の値を調整することで配線混雑を回避する方法が開示されている。
この方法を簡単に説明する。
図18において、半導体チップ10（図18A）と、この半導体チップ10の部分拡大図（図18B）と、を示す。
半導体チップ10は、チップ内に予め固定された複数のハードマクロ12を有し、さらに、外周部に複数のI/Oバッファ11を有している。そして、自動レイアウトの対象領域13に機能セルが配置される。
図18Bには、自動レイアウトの対象領域13のなかの領域R1を抜き出して、その拡大図を合わせて示している。領域R1において、3つの機能セル（Cell 1、Cell 2、Cell 3）が配置されており、さらに、領域R1には、端子がT1からT13まで合計13個の端子が存在する。そして、対象領域13に対して自動レイアウトを行った結果、13個の端子（T1からT13）のうち、端子T4と端子T11とが配線混雑のために結線できなかったとする。
【０００５】
なお、図18Bにおいて、配線層は二層であって、一層目の配線には右上から左下の斜線を付し、二層目の配線には左上から右下の斜線を付している。一層目と二層目とが繋がっている端子（例えば、端子T3、端子T9）にはVIAが存在するが、図示は省略している。
【０００６】
ここで、特許文献2では、あらかじめ端子密度の上限を設定しておく。そして、自動レイアウトを行ってみて配線混雑が生じることが分かった場合には、端子密度が前記設定値以下になるようにセルの配置を変更する。
例えば、端子密度の上限を10に設定したとする。
図18に示される領域R1の面積が単位面積であるとして、図18Bの状態では端子密度が13になっているので、端子密度が10以下になるように配置をやり直す。その結果、図19のようになったとする。すなわち、Cell 3の位置をずらして、単位面積あたりの端子数が10以下になるようにする。この状態で配線を行うと、図19Bのように、総ての端子が結線される。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開2007-305699号公報
【特許文献２】特開2008-90456号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、特許文献2の方法では、不必要にチップ面積が増大するという問題が生じる。これを図20、図21を参照して説明する。図20Aに示される半導体チップ１０において、領域R1とは異なる領域である領域R2に注目するとする。図20Cに示される領域R2において、端子数は、端子T1から端子T13までの13個であるが、総て問題なく結線されている。
しかし、前述したように単位面積当たりの端子密度の上限を10に設定しているので、端子密度が10以下になるように領域R1と同じように領域R2においてもセルの再配置が行われてしまう。例えば、図20Cに示される領域R2の面積を単位面積とすると、図21Aに示される半導体チップ10における領域R2は、図21Cに示すように、領域R2においてもセル4の位置がずらされて端子密度が10以下になるようにされる。領域R2についてはセルをもっと密集させて配置してもよいにも関わらず、不必要な再配置が行われたために面積が広がってしまっている。その結果、チップ10全体としても余計なスペースが多数生じることになり、チップ面積がかなり増大してしまう。
【課題を解決するための手段】
【０００９】
本発明の半導体集積回路の自動レイアウト設計方法は、
単位領域当たりのネットの数の上限をネット密度制約として設定するネット密度設定工程と、
前記ネット密度設定工程で設定された前記ネット密度制約を満たすようにセルを配置するセル配置工程と、を備える
ことを特徴とする。
【００１０】
本発明の半導体集積回路の自動レイアウト設計装置は、
単位領域当たりのネットの数の上限をネット密度制約として設定する制約設定部と、
前記制約設定部で設定された前記ネット密度制約を満たすようにセルを配置するレイアウト処理部と、を備える
ことを特徴とする。
【発明の効果】
【００１１】
本発明では、配線が収束できるか否かは、端子数というよりもネット数にこそ左右されるものと考え、ネット数に着目する。
そして、ネット密度が設定値以下になるようにセル配置を行うようにしている。
これにより、必要な領域に対しては配線混雑の緩和を行い、かつ、不必要な面積増大を抑制し、最適なレイアウトを提供することができる。
【図面の簡単な説明】
【００１２】
【図１】自動レイアウト装置の全体機能ブロック図。
【図２】自動レイアウト処理の手順を示すフローチャート。
【図３】セルを仮配置した状態の一例を示す図。
【図４】ネット密度制約を設定入力するための入力画面の一例を示す図。
【図５】ネットの数え方を説明するための図。
【図６】ネットの数え方を説明するための図。
【図７】ネットの数え方を説明するための図。
【図８】セルの再配置を実行する詳細手順を示すフローチャート。
【図９】領域R1のネットを抽出したテーブル。
【図１０】セル再配置の結果の一例を示す図。
【図１１】領域R2のネットを抽出したテーブル。
【図１２】通過ネットの例を示す図。
【図１３】第2実施形態において、通過ネットも含めてネット数をカウントするように設定できる入力画面の例を示す図。
【図１４】第2実施形態におけるセル再配置の手順を示すフローチャート。
【図１５】第3実施形態において、ネット密度制約204に加えて、通過ネットの上限を設定する入力枠206を設けた入力画面の例を示す図。
【図１６】第3実施形態における自動レイアウト処理の手順を示すフローチャート。
【図１７】第3実施形態において、自動レイアウト処理の手順を示すフローチャート。
【図１８】背景技術において、半導体チップと、この半導体チップ10の部分拡大図と、を示す図。
【図１９】背景技術において、セル再配置の結果を示す図。
【図２０】従来技術の問題点を説明するための図。
【図２１】従来技術の問題点を説明するための図。
【発明を実施するための形態】
【００１３】
以下、図面を参照して本発明の実施の形態について説明する。
（第1実施形態）
本発明の半導体集積回路の自動レイアウト装置にかかる第1実施形態を説明する。
図1は、自動レイアウト装置の全体機能ブロック図である。
自動レイアウト装置100は、入力部101と、表示部102と、出力部103と、本体装置110と、を備え、これは一般的なパーソナルコンピュータによって実現できるものである。
【００１４】
本体装置110は、メモリとCPUとを有し、自動レイアウトプログラムを読み込むことで各機能部としての機能を実現する。
本体装置110は、データ格納部120と、制約設定部130と、レイアウト処理部140と、制約判定部150と、を備える。
【００１５】
データ格納部120には、機能セルライブラリ121と、ネットリスト122と、デザインルール123と、が格納される。
機能セルライブラリ121には、各種の機能セルが格納されている。ここで、機能セルとしては、プリミティブセルや基本セルなどとも称されるAND回路、OR回路、インバータ回路などの基本的なマクロセルであってもよい。あるいは、機能セルとしては、RAM（random access memory）やROM（read only memory）などのメガセルであってもよい。
ネットリスト122とは、回路の接続状態を表現したデータであり、論理回路設計の結果である。
デザインルール123は、半導体集積回路の製造プロセスにおいて認可されている半導体素子寸法や、配線金属の幅や間隔などを規定した設計規定である。
さらには、本実施形態では、制約設定部130で設定される制約もデザインルールに加えられる。
【００１６】
制約設定部130は、単位面積当たりのネット数の上限値を制約条件として設定する。このような制約条件は、入力部101からユーザによって適宜入力されるものである。制約条件の詳細については後述する。
【００１７】
レイアウト処理部140は、ネットリスト122およびデザインルール123に基づいて機能セルの配置を行う。さらに、レイアウト処理部140は、その他、フロアプラン、電源配線、クロックツリー合成、配線を行う。
【００１８】
制約判定部150は、レイアウト処理部140によって行われた機能セルの配置が制約条件を満たしているかどうかを判定する。制約条件が満たされていない場合、制約判定部150は、レイアウト処理部140に再配置を指令する。制約条件が満たされている場合、制約判定部150はその旨をレイアウト処理部140に伝える。すると、レイアウト処理部140は、セル配置の後工程であるクロックツリー合成（CTS：clock tree synthesis）および配線処理を実行する。このようにして作成されたレイアウトデータは出力部103から出力される。
【００１９】
第1実施形態による自動レイアウトの各処理工程を参照しながら説明する。
図2は、自動レイアウト処理の手順を示すフローチャートである。
まず、ST100において、レイアウト処理部140は、データ格納部120の機能セルライブラリ121、ネットリスト122、および、デザインルール123を読み込む。そして、読み込んだデータに基づいて、フロアプラン、電源配線を行う（ST101）。これにより、I/Oバッファやハードマクロの配置位置を決定し、機能セルの配置領域を決定する。さらに、電源ラインの付加を行う。
【００２０】
次に、ST102において、機能セルの仮配置を行う。
例えば、読み込んだデータに基づいて、概略配線を行って配線遅延およびセル遅延を算出しつつ、タイミング制約等も考慮しながらタイミング収束が図れるように各機能セルの配置位置を仮決めする。
このようなセル配置はレイアウト処理部140によって実行される。
この仮配置（ST102）により、図3のように機能セルが配置されたとする。
ここで、図3Aは、半導体回路チップの全体レイアウト図である。
図3Bは、図3A中の領域R1を抜き出して拡大した図である。
図3Cは、図3A中の領域R2を抜き出して拡大した図である。
ここでは、わかりやすいように、仮想的に詳細配線まで行ったとした場合の配線の様子を合わせて示しているが、仮配置（ST102）では、詳細配線まで行う必要はない。
【００２１】
続いて、ST103において、仮配置（ST102）された機能セルの配置領域内で配線が未収束になる混雑領域が有るか否かを判断する。
例えば、図3B中では、端子T4と端子T11とがこのままでは配線不可能であり、配線未収束になってしまう。
したがって、領域R1は混雑領域である。
【００２２】
ここで、混雑領域の有無を判断するに当たっては様々な方法が考えられる。例えば、仮想的に詳細配線を行ってみてもよい。あるいは、単位面積当たりの端子数をカウントして、端子数が所定数以上（例えば10以上）である場合には混雑領域であると判定してもよい。
ここでは、一例として、単位面積当たりの端子数が10以上である領域に対しては、混雑領域である、と判定することとする。
単位面積当たりの端子数が10以上である領域を混雑領域とすると、領域R1に加えて、領域R2も混雑領域となる。
【００２３】
混雑領域がある場合（ST103：YES）、例えば、表示部102の画面において、図3Aのレイアウト図上で混雑領域R1と混雑領域R2とを表示し、ユーザに混雑領域を提示する（ST104）。
【００２４】
さて、混雑領域は配線が未収束になる恐れがあるので、ユーザとしては、配線が適切に収束するようにセルの再配置を実行させなければならない。
ここで、本第1実施形態では、再配置を実行する際の制約条件として、ネット密度を用いる。すなわち、単位面積当たりのネット数が所定値以下になるようにセルの再配置を実行させる。
図4は、ネット密度制約を設定入力するための入力画面200の一例である。
入力画面200において、エリア名201、範囲202、単位面積203、および、ネット密度204を入力できるようになっている。
【００２５】
あるいは、コマンドを打ち込むようにしてもよい。例えば、ネット密度制約を設定する領域を、座標（ｘ、ｙ）＝（2134、1234）で、縦横幅が1000×1000であるエリア1であるとする。
そして、このエリア1において、縦横幅100×100の単位面積当たりにネット数の上限が1000になるようにする。このようにエリア1に対してネット密度制約を設定する場合、次のような入力コマンドが一例として挙げられる。
【００２６】
領域の設定にあたっては、
set region -name <設定領域名> -loc <x座標> <y座標> -width <横幅値> -height <縦幅値>
の順で入力することとし、
具体的には、
set region -name area1 -loc 2134 1234 -width 1000 -height 1000 
とする。
【００２７】
単位面積の設定にあたっては、
set areaUnit <width> <height> -name <設定領域名>
の順で入力することとし、
具体的には、
set areaUnit 100 100 -name area1
とする。
【００２８】
そして、ネット密度制約の設定にあたっては、
set placeNetDensity <ネット数> -name <設定領域名>
の順で入力することとし、
具体的には、
set placeNetDensity 1000 -name area1
とする。
【００２９】
本実施形態では、ネット密度制約を設定する点に特徴を有するところ、半導体集積回路の設計分野では広く使用されている用語ではあるが、ここで"ネット"という用語について簡単に補足を加えておく。
【００３０】
回路設計者によって、設計対象の回路で処理したいアルゴリズムが動作レベル記述言語で記述される。この動作記述に基づいてデータフロー情報が作成される。
データフロー情報から論理合成によって、クラスタ（論理ブロック）に分けられる。そして、クラスタ情報およびクラスタ同士の接続情報がＲＴＬ（レジスタ転送レベル、Register transfer level）のようなハードウエア記述言語に変換され、これが回路接続情報を有するネットリストなる。
ここに、ネットとは、クラスタ（論理ブロック）間のつながりのことである。
ネットリストを具体的な集積回路に落とし込むと、ネットは端子間を繋ぐ配線という形で具体化されることになる。
【００３１】
さらに、ネットの数え方について補足を加える。
図5において、領域R3には、Cell 1、Cell 2およびCell 3が配置されている。
Cell 1は、端子T1と、端子T2と、端子T3と、を有する。
Cell 2は、端子T4と、端子T5と、を有する。
Cell 3は、端子T6と、端子T7と、を有する。
すなわち、この領域R3の端子数は"7つ"である。
ここで、端子数が7であるからといってネット数も7になるとは限らない。
【００３２】
領域R3に配置された機能セルを論理ブロックのレベルに戻してみると、図6のようになる。Cell 1は論理ブロックB1に対応し、Cell 2は論理ブロックB2に対応し、Cell 3は論理ブロックB3に対応する、とする。
ここで、論理ブロックB1の端子T3と、論理ブロックB2の端子T5と、論理ブロックB3の端子T6と、に注目する。
論理ブロックB3の出力は、端子T6から出て、論理ブロックB1の端子T3と、論理ブロックB2の端子T5と、に入力される。
この場合、端子T6と端子T3との間の信号は、端子T6と端子T5との間の信号に同じであり、ネットとしてみると、同じ論理ブロックB3に繋がるネットである。
したがって、端子T6と端子T3とを繋ぐネットと、端子T6と端子T5とを繋ぐネットとは、同じネットとして数える。
【００３３】
実際のレイアウト設計の段階でネット数を数えるにあたっては、図5や図6のような配線が存在しない段階でネットをカウントすることになる。したがって、図7のように、対象領域内にある端子を抽出し、さらに、各端子が繋がるネットをネットリストから抽出する。すると、端子T3と端子T5と端子T6とに繋がるネットは同じであるので、この対象領域には、合計でネットが5つあることになる。
【００３４】
さて、ST105でネット密度の設定を行う。例えば、入力部101を操作してユーザがネット密度の上限を入力する。設定値は、制約設定部130によりデザインルール123に加えられる。ここでは、ネット密度制約を"9"に設定したとする。
【００３５】
このネット密度制約のもとでセルの再配置を実行する（ST106）。
セル再配置の手順を説明する。
図8は、セルの再配置（ST106）を実行する詳細手順を示すフローチャートである。
セルの再配置にあたって、単位領域ごとにネット密度を求める（ST200）。なお、単位面積を有する領域を単位領域と称する。
ネット密度を求めるにあたり（ST200）、具体的には、仮配置された配置領域内に対して単位領域内の端子を抽出し（ST201）、抽出された端子に接続するネットを抽出する（ST202）。そして、抽出したネットの数をカウントする（ST203）。この工程は、図7で説明した手順である。
【００３６】
これを図3の領域R1に適用すると、図9のようになり、単位面積当たりのネット数が10である。
【００３７】
このように求められたネット数と設定されたネット密度制約とを対比する（ST204）。このような対比は制約判定部150により実行される。
ここで現在の状態では、ネット数（10本）がネット密度制約（9本）を超えている（ST204：NO）。
このような場合には、この単位領域のセル配置を変更して（ST205）、ネット密度制約を満たすまでネット密度の算出（ST200）とセル配置の変更（ST205）とを繰り返す。この結果、図10Bに示すようになったとする。Cell 3の位置がずらされることによりネット密度が緩和され、これにより総ての端子が結線されている。単位面積あたりのネット密度も9となり、ネット密度の制約も満たす（ST204：YES）。
【００３８】
ネット密度制約を満たしたところで（ST204：YES）、対象領域内のすべての単位領域について検証したか判断する（ST206）。まだ、検証していない単位領域がある場合には（ST206：NO）、別の単位領域に移動し、ネット密度の算出（ST200）とセル配置の変更（ST205）とを行う。
【００３９】
ここで、例えば、図3の領域R2に移動したとする。領域R2のネット数をカウントすると図11のようになる。ネット数としては9本であり、これはネット密度制約を満たす（ST204：YES）。したがって、領域R2についてはセル配置の変更（ST205）を行わない。
【００４０】
対象領域内のすべての単位領域について検証が済んだ場合（ST206：YES）、セルの再配置が終了する。
【００４１】
これでセルの配置が決定したことになるので、あとは、クロックツリー合成（ST107）と詳細配線（ST108）を行う。
また、ST102の仮配置のあと、混雑領域が無ければ（ST103：NO）、クロックツリー合成（ST107）にジャンプする。この場合は、仮配置（ST102）によって混雑領域が無いようにセルを配置できているので、セル再配置（ST106）を行う必要がないからである。
クロックツリー合成（ST107）においては、単位面積あたりのネット本数がネット密度制約を満たすようにする。
配線を行ってみて（ST108）、すべての端子に配線ができ、配線が収束した場合（ST109：YES）、自動レイアウトが終了する。
なお、配線が収束しなかった場合（ST109：NO）には、再びセルの仮配置（ST102）に戻ってやり直す。
【００４２】
このような第1実施形態によれば、次の効果を奏する。
従来は、端子密度が設定値以下になるようにセルの配置を調整していた。この方法で確かに配線未収束という事態は無くなるが、図21を参照して説明したように、配線が十分に可能な領域に対してもセル占有率を下げるような再配置を行ってしまう場合があった。
この点、本実施形態では、端子数ではなく、単位面積当たりのネット数（ネット密度）に注目している。そして、ネット密度が設定値以下になるようにセル配置を行うようにしている。これにより、領域R1のように配線が混雑して配線未収束に陥る可能性がある領域に対しては配線混雑を緩和するようにセルの再配置を実行する一方、領域R2のように端子数が多くても配線が十分に収束できる領域に対しては不必要な再配置を行わない。
配線が収束できるか否かは、端子数というよりもネット数に左右されるものと考えられる。したがって、単純に単位領域あたりの端子数を抽出だけでなく、本実施形態ではさらにそれら端子に接続されるネットを抽出する工程（ST202）と、ネットの数をカウントする工程（ST203）と、を行うこととしている。これにより、必要な領域に対しては配線混雑の緩和を行い、かつ、不必要な面積増大を抑制し、最適な自動レイアウトを提供することができる。
【００４３】
（第2実施形態）
次に、本発明の第2実施形態について説明する。
第2実施形態の基本的構成は第1実施形態と同様であるが、領域を通過する配線についてもカウントの対象とする点に特徴を有する。
【００４４】
第1実施形態においてネットの数をカウントするにあたっては、対象領域内に存在する端子に繋がるネットを抽出してカウントした。
ここで、実際の回路構成では、対象領域内の端子に繋がるわけではないが、対象領域を通過する配線も存在することがあり、このような配線を引くためは対象領域内の配線層が使用されることになってしまう。したがって、配線が混雑するか否か（配線が収束するか否か）を検証するにあたっては領域を通過するネットについても考えることが好ましい。
【００４５】
例えば、図12のように、領域R2とともに、領域R2の左右の領域である領域R21と領域R22とを合わせて考える。
このとき、通過ネット1から通過ネット4は、領域R2内の端子に繋がるわけではないが、領域R2を間にして離れた領域にある端子を繋ぐために領域R2を通過する（もしくは通過する可能性が高い）。
このような通過配線が増えてしまうと、領域R2内の配線スペースが無くなり、配線未収束になる恐れがある。
【００４６】
そこで、第2実施形態では、対象領域を通過するネットも含めてネット数をカウントするようにする。第2実施形態においては、図13に示す入力画面で、対象領域を通過するネットも含めてネット数をカウントするように設定できる入力枠205が設けられている。ネット密度設定工程（ST105）では、この入力枠205をONにし、通過ネットもカウントするように設定する。
【００４７】
図14は、第2実施形態におけるセル再配置の手順を示すフローチャートである。
第1実施形態（図8）と異なる点は、ネット密度を求めるにあたり（ST300）、まず仮配線を行う点である（ST301）。
通過ネットを見積もるためには仮配線が必要である。そして、対象領域のネット数を通過ネットも含めてカウントする。例えば図12の例でいうと、4つの通過ネットを含めて、領域R2のネット数は12である。これは、ネット密度制約である"9"を超えているので（ST204：NO）、この場合、セルの配置を変更する（ST205）。
ネット密度制約を満たすまでネット密度の算出（ST300）とセル配置の変更（ST205）とを繰り返す。その他の工程は、第1実施形態と同じである。
【００４８】
このような第2実施形態によれば、第1実施形態の効果に加え、さらに領域を通過するネットについてもカウント対象とする。
これにより、配線混雑を回避するためのセルの再配置をより適切に実行することができる。
【００４９】
（第3実施形態）
次に、本発明の第3実施形態について説明する。
第3実施形態の基本的構成は第1実施形態と同様であるが、領域内のネット密度の制約に加えて、通過配線数についても制約を設定する点に特徴を有する。
第2実施形態において対象領域を通過する通過ネットも含めてネット数をカウントした。
これに対し、第3実施形態では、通過ネットに対して別個の制約条件を設けることとする。例えば、図15の入力画面において、ネット密度制約204に加えて、通過ネットの上限を設定する入力枠206を設ける。
【００５０】
図16は、第3実施形態における自動レイアウト処理の手順を示すフローチャートである。第1実施形態と異なる点は、制約設定において、ネット密度を設定（ST105）することに加えて通過ネット本数を設定（ST1051）する点である。
【００５１】
さらに、このような制約を満たすようにセルの再配置を行うところ（ST400）、第3実施形態におけるセルの再配置（ST400）を説明する。
図17のフローチャートにおいて、第1実施形態（図8）と異なる点は、ネット密度を求めるにあたり（ST500）、まず仮配線を行う点である（ST501）。
通過ネットを見積もるためには仮配線が必要である。そして、対象領域のネット数を通過ネットも含めてカウントする（ST501）。次に、ST501でカウントされたネットのうち、端子に接続しているものを抽出する。これが対象領域内の端子に接続されるネットであり、第3実施形態ではこの本数をネット密度とする。
【００５２】
さらに、ST501でカウントされたネットのうち、端子に繋がっていないネットを抽出する。これが対象領域を通過するネットであり、第3実施形態ではこの本数を通過ネット数とする。
【００５３】
次に、ST204においては、ST503でカウントしたネット数（ネット密度）がネット密度制約を満たすか判定する。
ST2041において、ST504でカウントした通過ネット数が通過ネット数の設定値（ST1051）以下になっているか判定する。ST204およびST2041を満たすまでセル配置の変更（ST205）を繰り返す。
【００５４】
対象領域内のすべての領域がST204およびST2041の条件を満たしたところで、次にクロックツリー合成（ST107）および配線（ST108）を行う。
クロックツリー合成（ST107）においては、単位面積あたりのネット本数がネット密度制約を満たすようにする。さらに、配線（ST108）を行うにあたっては、通過ネット本数が通過ネット数の設定値以下になるように配線を行う。
【００５５】
このような第3実施形態によれば、第1実施形態の効果に加え、さらに、領域を通過するネットについても制約条件以下とする。これにより、配線混雑を回避するためのセルの再配置をより適切に実行することができる。
【００５６】
（変形例）
上記実施形態、例えば、第1実施形態を示す図２においては、セルを仮配置（ST102）した後、ST103において混雑領域がありと判断した場合（ST103：YES）にネット密度を考慮してセルの再配置（ST106）を行なう場合を例示した。
これに限らず、セルの仮配置（ST102）においてネット密度を考慮しながら仮配置を行なうようにしてもよい。この場合、セルの仮配置（ST102）よりも以前に、単位領域当たりのネットの数の上限をネット密度として設定し、該ネット密度を満たすようにセル仮配置を実行する。セルを仮配置した後、すべての機能セルについて制約を満たすように配置できたか否かを判定し、制約を満たすように配置できていなければセルの再配置を実行する。ネット密度を満たすように配置できていれば、クロックツリーの合成、配線、と工程を進めていく。さらに、クロックツリーの合成時（ST107）にもネット密度を考慮しながら合成するようにしてもよい。
【００５７】
混雑領域の有無を判断するステップ（ST103）は、セル仮配置（ST102）の直後のみならず、クロックツリー合成（ST107）の後や配線処理（ST108）の後にも実行するようにしてもよい。混雑領域の有無を判断するステップ（ST103）は、レイアウト処理のどの段階でも実行できるものであり、必要に応じて適宜挿入すればよい。そして、混雑領域が有ることが判定された場合には、セルの仮配置（ST102）まで戻るようにする。
混雑領域が有るままで配線処理まで行うことは結局は無駄な処理になってしまうところ、こまめに混雑領域の有無を判定することによってより効率的に処理フローのループを回すことができる。
【００５８】
上記実施形態では、配線が収束しなかったときには（ST109：NO）セルの仮配置（ST102）まで戻る場合を例示したが、混雑領域の混雑の程度に応じてどのステップまで戻るかを適切に判断するようにしてもよい。すなわち、配線が収束しなかった場合（ST109：NO）、混雑領域の混雑の程度に応じて、セルの仮配置（ST102）まで戻るようにしてもよく、または、クロックツリー合成（ST107）まで戻るようにしてもよく、あるいは、配線処理（ST108）まで戻るようにしてもよい。
【００５９】
なお、本発明は上記実施の形態に限られたものではなく、趣旨を逸脱しない範囲で適宜変更することが可能である。
【符号の説明】
【００６０】
10…半導体チップ、12…ハードマクロ、13…レイアウト対象領域、100…自動レイアウト装置、101…入力部、102…表示部、103…出力部、110…本体装置、120…データ格納部、121…機能セルライブラリ、122…ネットリスト、123…デザインルール、130…制約設定部、140…レイアウト処理部、150…制約判定部、200…入力画面。
【図１】
2012215974.tif 000003
【図２】
2012215974.tif 000004
【図３】
2012215974.tif 000005
【図４】
2012215974.tif 000006
【図５】
2012215974.tif 000007
【図６】
2012215974.tif 000008
【図７】
2012215974.tif 000009
【図８】
2012215974.tif 000010
【図９】
2012215974.tif 000011
【図１０】
2012215974.tif 000012
【図１１】
2012215974.tif 000013
【図１２】
2012215974.tif 000014
【図１３】
2012215974.tif 000015
【図１４】
2012215974.tif 000016
【図１５】
2012215974.tif 000017
【図１６】
2012215974.tif 000018
【図１７】
2012215974.tif 000019
【図１８】
2012215974.tif 000020
【図１９】
2012215974.tif 000021
【図２０】
2012215974.tif 000022
【図２１】
2012215974.tif 000023