(57)【要約】【課題】配線の混雑をより確実に緩和することができる自動配置配線方法を提供する。【解決手段】ハードマクロ３、４の配置、プリミティブセル５、６、７、８の配置及び配線のレイアウトを自動で行う自動配置配線方法において、ハードマクロ３、４及びプリミティブセル５、６、７、８の配置及び配線のレイアウトを行った後、配線混雑部を抽出し、プリミティブセル６を移動することにより、配線混雑部の配線の混雑を緩和するように構成した。【選択図】図１０
2010050244.tif 000002
【特許請求の範囲】
【請求項１】
ハードマクロの配置、プリミティブセルの配置及び配線のレイアウトを自動で行う自動配置配線方法において、
前記ハードマクロ及び前記プリミティブセルの配置及び配線のレイアウトを行った後、
配線混雑部を抽出し、前記プリミティブセルを移動することにより、前記配線混雑部の配線の混雑を緩和する自動配置配線方法。
【請求項２】
所定範囲の領域である処理領域の配線リソース量が、前記処理領域にレイアウトする配線の配線リソース量より少ない場合に、前記処理領域を前記配線混雑部として抽出する請求項１に記載の自動配置配線方法。
【請求項３】
前記処理領域内にレイアウトされた配線が前記プリミティブセルの入力端子に接続する場合に、当該配線の本数をカウントし、前記プリミティブセルの出力端子に接続する配線の本数よりも、カウントした前記配線の本数の方が多い場合に、前記プリミティブセルを移動させるセルである移動対象セルとして設定し、
前記処理領域内にレイアウトされた配線が前記プリミティブセルの出力端子に接続する場合に、当該配線の本数をカウントし、前記プリミティブセルの入力端子に接続する配線の本数よりも、カウントした前記配線の本数の方が多い場合に、前記プリミティブセルを前記移動対象セルとして設定する請求項２に記載の自動配置配線方法。
【請求項４】
前記プリミティブセルがクロックネットワークに含まれる場合には、当該プリミティブセルを前記移動対象セルとして設定しない請求項３に記載の自動配置配線方法。
【請求項５】
前記移動対象セルとして設定された前記プリミティブセルを所望の移動先に仮移動させ、前記仮移動に伴って、当該プリミティブセルに接続する配線を仮レイアウトした後、タイミング解析を行って、タイミングエラーが発生した場合には、当該プリミティブセルを前記移動対象セルから除外する請求項３又は４に記載の自動配置配線方法。
【請求項６】
前記移動対象セルに接続する配線が接続する他のプリミティブセルの一番近い空き領域を移動先として設定する請求項３乃至５の何れか一項に記載の自動配置配線方法。
【請求項７】
前記処理領域は、複数の前記ハードマクロに囲まれたスリット状の領域である請求項２乃至６の何れか一項に記載の自動配置配線方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、自動配置配線方法に関し、特に、ＣＡＤによるＬＳＩ開発に用いられる自動配置配線方法に関する。
【背景技術】
【０００２】
一般に、ＬＳＩ（Ｌａｒｇｅ  Ｓｃａｌｅ  Ｉｎｔｅｇｒａｔｉｏｎ）の開発におけるレイアウト工程では、まず、フロアプランにおいて、ハードマクロ配置及び電源配線が行われる。次いで、空き領域にプリミティブセル（以下、単に、セルと称する。）の配置、概略配線、詳細配線という手順で、作業が進められる。しかし、セルの配置を行う際、ハードマクロやセルの配置によって配線が混雑する部分（以下、配線混雑部と称する。）が発生する。そのため、詳細配線時の配線性に影響を与え、詳細配線時において配線をレイアウトしきれない場合がある。詳細配線における配線性を確保するため、配線混雑部の配線の混雑を緩和する方法が求められている。
【０００３】
例えば、特許文献１には、ハードマクロの配置を移動させることにより、配線混雑部の配線の混雑を緩和する技術が記載されている。
図１４を参照しながら、特許文献１の動作を説明する。
図１４に、従来技術の自動配置配線方法を説明するフローチャートを示す。
【０００４】
図１４に示すように、従来の自動配置配線方法においては、まず、複数の機能ブロックを配置する（ステップＳ５０１）。
次いで、機能ブロック間を接続する配線パターンを生成する（ステップＳ５０２）。具体的には、接続情報に基づいて設計基準を満たした格子上に機能ブロック間を接続する配線をレイアウトする。
次に、ステップＳ５０２において配線パターンを生成した結果、全ての配線をレイアウトしたか否かを判断する（ステップＳ５０３）。
【０００５】
ステップＳ５０３において、全ての配線をレイアウトした場合には（ステップＳ５０３；Ｙｅｓ）、本処理を終了する。
ステップＳ５０３において、未だレイアウトされていない配線が残っている場合には（ステップＳ５０３；Ｎｏ）、ステップＳ５０２においてレイアウトした配線を引き剥がして再度レイアウトする（ステップＳ５０４）。
【０００６】
次に、ステップＳ５０４において配線パターンを生成した結果、全ての配線をレイアウトしたか否かを判断する（ステップＳ５０５）。
ステップＳ５０５において、全ての配線をレイアウトした場合には（ステップＳ５０５；Ｙｅｓ）、本処理を終了する。
ステップＳ５０５において、未だレイアウトされていない配線が残っている場合には（ステップＳ５０５；Ｎｏ）、設計基準を満たした格子に関わらず、設計基準を満たすように機能ブロック間を接続する配線パターン（非格子型配線）を生成する（ステップＳ５０６）。
【０００７】
次に、ステップＳ５０６において配線パターンを生成した結果、配線間フリンジ容量によって遅延時間が大きくなると予想される配線混雑領域を抽出し、当該配線混雑領域の配線の混雑を緩和する処理を行って（ステップＳ５０７）、本処理を終了する。
【０００８】
次に、ステップＳ５０７の処理について、図１５に示すフローチャートを参照しながら説明する。ここで、ステップＳ５０２及びステップＳ５０４において、設計基準を満たした格子上に配線がレイアウトされた領域を格子型配線領域とする。また、ステップＳ５０６において、設計基準を満たした格子に関わらずに配線がレイアウトされた領域を非格子型配線領域とする。また、非格子型配線領域以外の領域であって、ハードマクロ（以下、単に、マクロと称する。）が配置されていない領域を疎領域とする。
まず、全ての非格子型配線領域の面積と、全ての疎領域の面積とを算出し、目標面積縮小率を設定する（ステップＳ６０１）。ここで、目標面積縮小率とは、非格子型配線領域の面積を縮小させる程度を表す率である。なお、説明の便宜上、目標面積縮小率は、非格子型配線領域を格子型配線領域に修正することによって達成される、非格子型配線領域の面積の縮小率とする。
【０００９】
次に、非格子型配線領域のうち最も面積の大きい最大非格子型配線領域と、疎領域のうち最も面積の大きい最大疎領域とを抽出する（ステップＳ６０２）。
次いで、ステップＳ６０２において抽出した最大非格子型配線領域から最も近い位置にあるマクロを指定マクロとして指定する（ステップＳ６０３）。
【００１０】
次に、ステップＳ６０３において指定した指定マクロの周囲領域を設定する（ステップＳ６０４）。
次いで、ステップＳ６０４で設定した周囲領域を８分割して分割領域を生成し、分割領域の各々に指定マクロを移動させる配置位置を設定する（ステップＳ６０５）。
次に、各分割領域に指定マクロの他のマクロが存在するか否かを判断し（ステップＳ６０６）、他のマクロが存在しない分割領域に指定マクロを移動する（ステップＳ６０７）。
【００１１】
次に、ステップＳ６０７における指定マクロの移動によって生じる空き領域を使って、設計基準を満たした格子上に最大非格子型配線領域の配線をレイアウトしなおし、最大非格子型配線領域を格子型配線領域に修正する（ステップＳ６０８）。
次に、全ての非格子型配線領域の面積を算出し、ステップＳ６０１において算出した非格子型配線領域の面積と比較し、ステップＳ６０２において設定した目標面積縮小率を満足するか否かを判断する（ステップＳ６０９）。
【００１２】
ステップＳ６０９において、目標面積縮小率を満足したい場合には（ステップＳ６０９；Ｎｏ）、ステップＳ６０２に進む。
ステップＳ６０９において、目標面積縮小率を満足する場合には（ステップＳ６０９；Ｙｅｓ）、本処理を終了する。
【特許文献１】特開２００１−３０８１８８号公報
【発明の開示】
【発明が解決しようとする課題】
【００１３】
しかしながら、特許文献１に記載の従来技術では、配線の混雑を緩和するため、ハードマクロを移動させる。しかし、ハードマクロの移動先の配線の混雑度が移動前より高い場合、配線の混雑を緩和することができないという問題がある。
【課題を解決するための手段】
【００１４】
本発明の第１の態様にかかる自動配置配線方法は、ハードマクロの配置、プリミティブセルの配置及び配線のレイアウトを自動で行う自動配置配線方法であって、前記ハードマクロ及び前記プリミティブセルの配置及び配線のレイアウトを行った後、配線混雑部を抽出し、前記プリミティブセルを移動することにより、前記配線混雑部の配線の混雑を緩和する。
【００１５】
本発明の第１の態様においては、プリミティブセルを移動させることにより配線混雑部の配線の混雑を緩和する。そのため、ハードマクロの位置を移動させる必要がなく、フロアプランに影響を与えずに、配線の混雑を緩和することができる。
【００１６】
また、ハードマクロの位置を移動させると、移動先が配線混雑部となってしまう可能性があるが、本発明の第１の態様では、ハードマクロの位置を移動させずに済むため、配線の混雑をより確実に緩和することができる。
【発明の効果】
【００１７】
本発明により、配線の混雑をより確実に緩和することができる。
【発明を実施するための最良の形態】
【００１８】
以下に、本発明を適用可能な実施の形態を説明する。なお、本発明は、以下の実施の形態に限定されるものではない。
実施の形態１．
図１に、本発明の実施の形態１にかかる自動配置配線方法が用いられる自動配置配線システム１００のブロック図を示す。
自動配置配線システム１００は、図１に示すように、サーバ１、サーバ１とネットワークＮを介して接続される複数のコンピュータ装置２などを有している。
【００１９】
サーバ１は、制御部１１、記録媒体１２などを有している。記録媒体１２は、サーバ１を制御するための各種プログラム（図示省略）及びデータ（図示省略）などを格納している。また、記録媒体１２は、例えば、ＣＡＤ設計ツール（回路エディタやレイアウトエディタ等）１２１などを格納している。そして、制御部１１は、記録媒体１２に格納されている各種プログラムを実行することにより、ＣＡＤ設計ツール１２１をコンピュータ装置２に提供する。
【００２０】
コンピュータ装置２は、制御部２１、記録媒体２２などを有している。記録媒体２２は、コンピュータ装置２を制御するための各種プログラム（図示省略）及びデータ（図示省略）などを格納している。そして、制御部２１は、記録媒体２２に格納されている各種プログラムを実行することにより、サーバ１からＣＡＤ設計ツール１２１をダウンロードする。ダウンロードされたＣＡＤ設計ツール１２１は、コンピュータ２の記録媒体２２或いはメモリ（図示省略）などに格納される。そして、制御部２１が当該ＣＡＤ設計ツール１２１を実行することにより、ＬＳＩの回路図の設計が行われる。また、記録媒体２２は、後述する移動対象セルリスト２２１を格納している。
【００２１】
図２は、自動配置配線システム１００において用いられる本発明の実施の形態１にかかる自動配置配線方法を示すフローチャートである。
図２に示すように、まず、フロアプランにおいて、ハードマクロの配置や電源配線のレイアウトを行う（ステップＳ１）。
【００２２】
次に、ＣＡＤ設計ツール１２１に含まれる自動配置ツールを用いて、セルの初期配置を行う（ステップＳ２）。
【００２３】
次に、ステップＳ２のセルの初期配置結果に対してタイミング解析を行って、セル配置位置の改善を行う（ステップＳ３）。
【００２４】
次に、配線が混雑する部分（以下、配線混雑部と称する。）の抽出を行って、配線混雑部における配線の混雑の緩和を行う（ステップＳ４）。
【００２５】
次に、ステップＳ４の処理によって確定したセルの配置結果を用いて、ＣＴＳ（Ｃｌｏｃｋ  Ｔｒｅｅ  Ｓｙｎｔｈｅｓｉｓ）を行う（ステップＳ５）。ＣＴＳとは、クロックのネットワークに対してバッファを介したツリー状の構造へセルの配置を変換することである。
【００２６】
次に、セル間を接続する配線経路を決めるため、配線のレイアウトを行う（ステップＳ６）。
【００２７】
次に、ステップＳ６のレイアウト結果に対して、静的タイミング解析（ＳＴＡ：Ｓｔａｔｉｃ  Ｔｉｍｉｎｇ  Ａｎａｌｙｓｉｓ）を行って（ステップＳ７）、本処理を終了する。
【００２８】
次に、ステップＳ４における処理について、図３を参照しながら説明する。
まず、ユーザにより処理領域を指定する（ステップＳ１０１）。ここで、処理領域の指定は、レイアウト図面上の座標値を指定することによって行う。また、処理領域とは、ハードマクロに挟まれた狭いスリット状の領域である。
【００２９】
次に、処理領域にレイアウト可能な配線の配線リソースの計算を行う（ステップＳ１０２）。ここで、計算結果の配線リソース量をＸとする。
【００３０】
次に、現在の配置状態において処理領域内にレイアウトすべき配線の配線リソースの計算を行う（ステップＳ１０３）。ここで、計算結果の配線リソース量をＹとする。
【００３１】
次に、配線リソース量Ｘが配線リソース量Ｙより少ないか否かを判断する（ステップＳ１０４）。
ステップＳ１０４において、配線リソース量Ｘが配線リソース量Ｙより多い場合には（ステップＳ１０４；Ｎｏ）、本処理を終了し、ステップＳ５に進む。
ステップＳ１０４において、配線リソース量Ｘが配線リソース量Ｙより少ない場合には（ステップＳ１０４；Ｙｅｓ）、処理領域内において配線リソースを消費している配線に接続するセルの中から移動するセル（以下、移動対象セルと称する。）を決める（ステップＳ１０５）。
【００３２】
次に、移動可能なセルがあるか否かを判断する（ステップＳ１０６）。
ステップＳ１０６において、移動可能なセルがない場合には（ステップＳ１０６；Ｎｏ）、本処理を終了し、ステップＳ５に進む。
ステップＳ１０６において、移動可能なセルがある場合には（ステップＳ１０６；Ｙｅｓ）、セルの移動を行って（ステップＳ１０７）、ステップＳ１０３に戻る。
【００３３】
次に、ステップＳ１０５の処理について、図４、図５を参照しながら説明する。
まず、処理領域内にレイアウトされている配線が移動対象セルの入力端子と出力端子の何れに接続しているかを判断する（ステップＳ２０１）。
ステップＳ２０１において、処理領域内にレイアウトされている配線が移動対象セルの入力端子に接続している場合（ステップＳ２０１；入力端子）、当該入力端子に接続している配線が処理領域内の配線リソースを使用しているか否かを判断する（ステップＳ２０２）。
ステップＳ２０２において、当該入力端子に接続している配線が処理領域内の配線リソースを使用していない場合には（ステップＳ２０２；Ｎｏ）、当該入力端子に接続している他の配線についてステップＳ２０２の処理を行う。当該入力端子に接続している配線全てについてステップＳ２０２の処理を行った結果、当該入力端子に接続している配線の全てが処理領域内の配線リソースを使用していない場合には（ステップＳ２０２；Ｎｏ）、本処理を終了し、ステップＳ１０６に進む。
ステップＳ２０２において、当該入力端子に接続している配線が処理領域内の配線リソースを使用している場合には（ステップＳ２０２；Ｙｅｓ）、処理領域内の配線リソースを使用している配線として本数をカウントする（ステップＳ２０３）。当該入力端子に接続している配線全てについてステップＳ２０２及びステップＳ２０３の処理を行ったら、ステップＳ２０４に進む。
【００３４】
次に、ステップＳ２０３においてカウントした本数が、移動対象セルの出力端子に接続している配線（以下、出力配線と称する。）の本数より多いか否かを判断する（ステップＳ２０４）。
ステップＳ２０４において、ステップＳ２０３においてカウントした本数が、出力配線の本数より少ない場合には（ステップＳ２０４；Ｎｏ）、ステップＳ２１１に進む。
ステップＳ２０４において、ステップＳ２０３においてカウントした本数が、出力配線の本数より多い場合には（ステップＳ２０４；Ｙｅｓ）、ステップＳ２０８に進む。
【００３５】
一方、ステップＳ２０１において、処理領域内にレイアウトされている配線が移動対象セルの出力端子に接続している場合（ステップＳ２０１；出力端子）、当該出力端子に接続している配線が処理領域内の配線リソースを使用しているか否かを判断する（ステップＳ２０５）。
ステップＳ２０５において、当該出力端子に接続している配線が処理領域内の配線リソースを使用していない場合には（ステップＳ２０５；Ｎｏ）、当該出力端子に接続している他の配線についてステップＳ２０５の処理を行う。当該出力端子に接続している配線全てについてステップＳ２０５の処理を行った結果、当該出力端子に接続している配線の全てが処理領域内の配線リソースを使用していない場合には（ステップＳ２０５；Ｎｏ）、本処理を終了し、ステップＳ１０６に進む。
ステップＳ２０５において、当該出力端子に接続している配線が処理領域内の配線リソースを使用している場合には（ステップＳ２０５；Ｙｅｓ）、処理領域内の配線リソースを使用している配線として本数をカウントする（ステップＳ２０６）。当該出力端子に接続している配線全てについてステップＳ２０５及びステップＳ２０６の処理を行ったら、ステップＳ２０７に進む。
【００３６】
次に、ステップＳ２０６においてカウントした本数が、移動対象セルの入力端子に接続している配線（以下、入力配線と称する。）の本数より多いか否かを判断する（ステップＳ２０７）。
ステップＳ２０７において、ステップＳ２０６においてカウントした本数が、入力配線の本数より少ない場合には（ステップＳ２０７；Ｎｏ）、ステップＳ２１１に進む。
ステップＳ２０７において、ステップＳ２０６においてカウントした本数が、入力配線の本数より多い場合には（ステップＳ２０７；Ｙｅｓ）、移動対象セルの属性を調べ、移動対象セルの属性が移動禁止か移動可かを判断する（ステップＳ２０８）。
【００３７】
ステップＳ２０８において、移動対象セルの属性が移動禁止である場合（ステップＳ２０８；Ｎｏ）、ステップＳ２１１に進む。
ステップＳ２０８において、移動対象セルの属性が移動可である場合（ステップＳ２０８；Ｙｅｓ）、当該セルがクロックのネットワークに含まれているか否かを判断する（ステップＳ２０９）。
【００３８】
ステップＳ２０９において、移動対象セルがクロックのネットワークに含まれている場合には（ステップＳ２０９；Ｙｅｓ）ステップＳ２１１に進む。
ステップＳ２０９において、移動対象セルがクロックのネットワークに含まれていない場合には（ステップＳ２０９；Ｎｏ）、記録媒体２２の移動対象セルリスト２２１に当該セルを記憶する（ステップＳ２１０）。
【００３９】
次に、移動対象セルリスト２２１に記憶されている複数の移動対象セルのうち一の移動対象セルについて、移動先を検索する（ステップＳ２１１）。
【００４０】
次に、ステップＳ２１１において検索された移動先に移動対象セルを仮移動させる（ステップＳ２１２）。
【００４１】
次に、仮移動した移動対象セルに対して配線を仮レイアウトする（ステップＳ２１３）。
【００４２】
次に、ステップＳ２１３において仮レイアウトされた配線について、タイミング解析を行って（ステップＳ２１４）、タイミングエラーの有無を判断する（ステップＳ２１５）。
ステップＳ２１５において、タイミングエラーがある場合には（ステップＳ２１５；Ｙｅｓ）、当該移動対象セルを移動対象セルリスト２２１から削除する（ステップＳ２１６）。
ステップＳ２１５において、タイミングエラーがない場合には（ステップＳ２１５；Ｎｏ）、当該移動対象セルを移動可として設定する（ステップＳ２１７）。移動対象セルリスト２２１に格納された移動対象セルの全てに対してステップＳ２１１〜ステップＳ２１５、ステップＳ２１６又はステップＳ２１７の処理を行った場合には、ステップＳ２１８に進む。
【００４３】
次に、移動対象セルリスト２２１を移動距離でソートし（ステップＳ２１８）、移動対象セルを決める処理を終了する。
【００４４】
次に、ステップＳ２１１の処理について、図６、図７を参照しながら説明する。
まず、処理領域内にレイアウトされている配線が、当該移動対象セルの入力配線か、出力配線か、入力配線及び出力配線の両方か、を判断する（ステップＳ３０１）。
【００４５】
ステップＳ３０１において、処理領域内にレイアウトされている配線が、当該移動対象セルの入力配線である場合（ステップＳ３０１；入力）、当該入力配線に接続される他のセルが処理領域内に配置されているか否かを判断する（ステップＳ３０２）。
【００４６】
ステップＳ３０２において、当該入力配線に接続される他のセルが処理領域内に配置されていない場合には（ステップＳ３０２；Ｎｏ）、ステップＳ３０６に進む。
ステップＳ３０２において、当該入力配線に接続される他のセルが処理領域内に配置されている場合には（ステップＳ３０２；Ｙｅｓ）、当該他のセルの移動可否判定処理を行い（ステップＳ３０３）、移動可か否かを判断する（ステップＳ３０４）。
【００４７】
ステップＳ３０４において、当該他のセルの移動が可である場合（ステップＳ３０４；Ｙｅｓ）、当該他のセルを仮移動し、配線の仮レイアウトを行う（ステップＳ３０５）。
【００４８】
次に、当該他のセルに一番近い空き領域を移動対象セルの移動先に設定し（ステップＳ３０６）、本処理を終了して、ステップＳ２１２に進む。
【００４９】
ステップＳ３０４において、当該他のセルの移動が不可である場合（ステップＳ３０４；Ｎｏ）、移動対象セルの移動先を現在位置に設定し（ステップＳ３０７）、本処理を終了して、ステップＳ２１２に進む。
【００５０】
ステップＳ３０１において、処理領域内にレイアウトされている配線が、当該移動対象セルの入力配線及び出力配線の両方である場合（ステップＳ３０１；両方）、当該入力配線及び当該出力配線に接続される他のセルが処理領域内に配置されているか否かを判断する（ステップＳ３０８）。
【００５１】
ステップＳ３０８において、当該入力配線及び当該出力配線に接続される他のセルが処理領域内に配置されていない場合には（ステップＳ３０８；Ｎｏ）、当該他のセルに一番近い空き領域を移動対象セルの移動先に設定し（ステップＳ３０９）、本処理を終了して、ステップＳ２１２に進む。
ステップＳ３０８において、当該入力配線及び当該出力配線に接続される他のセルが処理領域内に配置されている場合には（ステップＳ３０８；Ｙｅｓ）、移動対象セルの移動先を現在位置に設定し（ステップＳ３１０）、本処理を終了して、ステップＳ２１２に進む。
【００５２】
ステップＳ３０１において、処理領域内にレイアウトされている配線が、当該移動対象セルの出力配線である場合（ステップＳ３０１；出力）、当該出力配線に接続される他のセルが処理領域内に配置されているか否かを判断する（ステップＳ３１１）。
【００５３】
ステップＳ３１１において、当該出力配線に接続される他のセルが処理領域内に配置されていない場合には（ステップＳ３１１；Ｎｏ）、ステップＳ３１５に進む。
ステップＳ３１１において、当該出力配線に接続される他のセルが処理領域内に配置されている場合には（ステップＳ３１１；Ｙｅｓ）、当該他のセルの移動可否判定処理を行い（ステップＳ３１２）、移動可か否かを判断する（ステップＳ３１３）。
【００５４】
ステップＳ３１３において、当該他のセルの移動が可である場合（ステップＳ３１３；Ｙｅｓ）、他のセルを仮移動し、配線の仮レイアウトを行う（ステップＳ３１４）。
【００５５】
次に、当該他のセルに一番近い空き領域を移動対象セルの移動先に設定し（ステップＳ３１５）、本処理を終了して、ステップＳ２１２に進む。
【００５６】
ステップＳ３１３において、当該他のセルの移動が不可である場合（ステップＳ３１３；Ｎｏ）、移動対象セルの移動先を現在位置に設定し（ステップＳ３１６）、本処理を終了して、ステップＳ２１２に進む。
【００５７】
次に、ステップＳ３０３及びステップＳ３１２の移動可否判定処理について、図８、図９を参照しながら説明する。
まず、処理領域内にレイアウトされている配線が当該他のセルの入力端子と出力端子の何れに接続しているかを判断する（ステップＳ４０１）。
ステップＳ４０１において、処理領域内にレイアウトされている配線が当該他のセルの入力端子に接続している場合（ステップＳ４０１；入力端子）、当該入力端子に接続している配線が処理領域内の配線リソースを使用しているか否かを判断する（ステップＳ４０２）。
ステップＳ４０２において、当該入力端子に接続している配線が処理領域内の配線リソースを使用していない場合には（ステップＳ４０２；Ｎｏ）、当該入力端子に接続している他の配線についてステップＳ４０２の処理を行う。当該入力端子に接続している配線全てについてステップＳ４０２の処理を行った結果、当該入力端子に接続している配線の全てが処理領域内の配線リソースを使用していない場合には（ステップＳ４０２；Ｎｏ）、本処理を終了し、ステップＳ３０４又はステップＳ３１３に進む。
ステップＳ４０２において、当該入力端子に接続している配線が処理領域内の配線リソースを使用している場合には（ステップＳ４０２；Ｙｅｓ）、処理領域内の配線リソースを使用している配線として本数をカウントする（ステップＳ４０３）。当該入力端子に接続している配線全てについてステップＳ４０２及びステップＳ４０３の処理を行ったら、ステップＳ４０４に進む。
【００５８】
次に、ステップＳ４０３においてカウントした本数が、当該他のセルの出力端子に接続している配線（出力配線）の本数より多いか否かを判断する（ステップＳ４０４）。
ステップＳ４０４において、ステップＳ４０３においてカウントした本数が、当該他のセルの出力端子に接続している配線の本数より少ない場合には（ステップＳ４０４；Ｎｏ）、当該他のセルを移動不可として設定する（ステップＳ４０５）。
ステップＳ４０４において、ステップＳ４０３においてカウントした本数が、当該他のセルの出力端子に接続している配線の本数より多い場合には（ステップＳ４０４；Ｙｅｓ）、ステップＳ４０９に進む。
【００５９】
一方、ステップＳ４０１において、処理領域内にレイアウトされている配線が当該他のセルの出力端子に接続している場合（ステップＳ４０１；出力端子）、当該出力端子に接続している配線が処理領域内の配線リソースを使用しているか否かを判断する（ステップＳ４０６）。
ステップＳ４０６において、当該出力端子に接続している配線が処理領域内の配線リソースを使用していない場合には（ステップＳ４０６；Ｎｏ）、当該出力端子に接続している他の配線についてステップＳ４０６の処理を行う。当該出力端子に接続している配線全てについてステップＳ４０６の処理を行った結果、当該出力端子に接続している配線の全てが処理領域内の配線リソースを使用していない場合には（ステップＳ４０６；Ｎｏ）、本処理を終了し、ステップＳ３０４又はステップＳ３１３に進む。
ステップＳ４０６において、当該出力端子に接続している配線が処理領域内の配線リソースを使用している場合には（ステップＳ４０６；Ｙｅｓ）、処理領域内の配線リソースを使用している配線として本数をカウントする（ステップＳ４０７）。当該出力端子に接続している配線全てについてステップＳ４０６及びステップＳ４０７の処理を行ったら、ステップＳ４０８に進む。
【００６０】
次に、ステップＳ４０７においてカウントした本数が、当該他のセルの入力端子に接続している配線（入力配線）の本数より多いか否かを判断する（ステップＳ４０８）。
ステップＳ４０８において、ステップＳ４０７においてカウントした本数が、当該他のセルの入力端子に接続している配線の本数より少ない場合には（ステップＳ４０８；Ｎｏ）、ステップＳ４１６に進む。
ステップＳ４０８において、ステップＳ４０７においてカウントした本数が、当該他のセルの入力端子に接続している配線の本数より多い場合には（ステップＳ４０８；Ｙｅｓ）、当該他のセルの属性を調べ、当該他のセルの属性が移動禁止か移動可かを判断する（ステップＳ４０９）。
【００６１】
ステップＳ４０９において、当該他のセルの属性が移動禁止である場合（ステップＳ４０９；Ｎｏ）、ステップＳ４１６に進む。
ステップＳ４０９において、当該他のセルの属性が移動可である場合（ステップＳ４０９；Ｙｅｓ）、当該他のセルがクロックのネットワークに含まれているか否かを判断する（ステップＳ４１０）。
【００６２】
ステップＳ４１０において、当該他のセルがクロックのネットワークに含まれている場合には（ステップＳ４１０；Ｙｅｓ）ステップＳ４１６に進む。
ステップＳ４１０において、当該他のセルがクロックのネットワークに含まれていない場合には（ステップＳ４１０；Ｎｏ）、移動先を検索する（ステップＳ４１１）。
【００６３】
次に、ステップＳ４１１において検索された移動先に当該他のセルを仮移動させる（ステップＳ４１２）。
【００６４】
次に、仮移動した当該他のセルに対して配線を仮レイアウトする（ステップＳ４１３）。
【００６５】
次に、ステップＳ４１３において仮レイアウトされた配線について、タイミング解析を行って（ステップＳ４１４）、タイミングエラーの有無を判断する（ステップＳ４１５）。
ステップＳ４１５において、タイミングエラーがある場合には（ステップＳ４１５；Ｙｅｓ）、当該他のセルを移動不可として設定する（ステップＳ４１６）。
ステップＳ４１５において、タイミングエラーがない場合には（ステップＳ４１５；Ｎｏ）、当該他のセルを移動可として設定する（ステップＳ４１７）。
【００６６】
上述したように、本発明では、配線リソースに着目し、セル（プリミティブセル）を移動する。これにより、ハードマクロの位置を変更せずに配線リソースを確保することができる。具体的には、混雑領域の配線リソースを使用している配線に接続するセルの中から移動可能なセルを図３のステップＳ３１３の処理によって決定し、移動可能なセルの有無を図３のステップＳ３１４の処理によって判断する。移動可能なセルがない場合には処理を終了し、移動可能なセルがある場合には、図３のステップＳ３１５の処理で当該セルを移動し、配線リソースの確保を実現する。
【００６７】
本発明の実施の形態にかかる自動配置配線方法によって、配線リソースが確保されるメカニズムについて図１０〜図１３を参照しながら説明する。
図１０（ａ）及び図１１（ａ）は、本実施形態にかかる自動配置配線方法による配線リソースの確保前の配線図である。また、図１０（ｂ）及び図１１（ｂ）は、本実施形態にかかる自動配置配線方法による配線リソースの確保後の配線図である。図１２は、配線グリッドを用いて、図１０の配線リソースの変化を示す配線図である。図１３は、配線グリッドを用いて、図１１の配線リソースの変化を示す配線図である。
また、図１０、図１２に示すＬＳＩは、ハードマクロ３、４、セル５、６、７、８を有している。また、ハードマクロ３とハードマクロ４との間にはスリット状の処理領域９が形成されている。
また、図１１、図１３に示すＬＳＩは、ハードマクロ３、４、セル５、６、７を有している。また、ハードマクロ３とハードマクロ４との間にはスリット状の処理領域９が形成されている。
また、図１２、図１３では、配線グリッドＧ１は配線上にある配線グリッドであり、配線グリッドＧ２はセル上にある配線グリッドである。
【００６８】
図１０（ａ）では、セル５、７が処理領域９の紙面向かって左側に配置されており、セル６、セル８が処理領域９の紙面向かって右側に配置されている。また、セル５とセル７はそれぞれセル６に並列に接続している。また、セル６とセル８とは直列に接続している。したがって、処理領域９内には、セル５とセル６を接続する配線と、セル７とセル６とを接続する配線との２本の配線がレイアウトされている。
そこで、図１０（ｂ）に示すように、セル６を処理領域９の左側に移動させる。これにより、処理領域９内にレイアウトされる配線は、セル６とセル８を接続する配線のみとなる。したがって、処理領域９内にレイアウトされる配線の本数を低減することができ、処理領域９内の配線リソースを確保することができる。
【００６９】
図１１（ａ）では、セル５が処理領域９の紙面向かって左側に配置されており、セル６が処理領域９内に配置されており、セル７が処理領域９の紙面向かって右側に配置されている。また、セル５とセル６とは直列に接続されており、セル６とセル７とは直列に接続されている。したがって、処理領域９内には、セル５とセル６を接続する配線と、セル６とセル７とを接続する配線との２本の配線がレイアウトされている。
そこで、図１１（ｂ）に示すように、セル６を処理領域９の右側に移動させる。これにより、処理領域９内にレイアウトされる配線は、セル５とセル６をセル属する配線のみとなる。したがって、処理領域９内にレイアウトされる配線の本数を低減することができ、処理領域９内の配線リソースを確保することができる。
【００７０】
ここで、配線リソースは配線グリッドの交点数で表すことができる。以下の数式（１）から配線グリッド交点数を求めることができる。
G=Σ(W/RL)×(H/RL)    ・・・・・・（１）
数式（１）において、Ｌ＝１である。また、Ｇは配線グリッド交点数、Ｗは処理領域９の幅、Ｈは処理領域９の高さ、ＲＬはＬ層の配線間隔である。
【００７１】
セルの移動により確保される配線リソースは、増加した使用可能な配線グリッド交点数で表すことができ、以下の数式（２）により表される。
Gspace=Gcell+Gwire-Gusewire    ・・・・・・（２）
数式（２）において、Ｇｓｐａｃｅは増加する使用可能な配線グリッド交点数、Ｇｃｅｌｌはセルが移動することにより利用可能になる配線グリッド交点数、Ｇｗｉｒｅは移動するセルに接続していた配線が使用する配線グリッド交点数、Ｇｕｓｅｗｉｒｅはセルの移動後に当該セルに接続する配線が処理領域９内で使用している配線グリッド交点数である。
【００７２】
図１２（ａ）に示すように、図１０（ａ）において処理領域９内にレイアウトされた配線が消費する配線グリッド交点数は２２個である。また、図１２（ｂ）に示すように、図１０（ｂ）において処理領域９内にレイアウトされた配線が消費する配線グリッド交点数は１１個である。また、図１０では、処理領域９内にセルは存在しないため、移動するセルにより利用可能になる配線グリッド交点数は０個である。したがって、数式（２）より、Ｇｓｐａｃｅ＝０＋２２−１１＝１１である。よって、増加する使用可能な配線グリッド交点数は１１個となり、専有されていた配線グリッド交点数が５０％減少した。
【００７３】
図１３（ａ）に示すように、図１１（ａ）において処理領域９内にレイアウトされた配線が消費する配線グリッド交点数は８個である。また、図１３（ｂ）に示すように、図１１（ｂ）において処理領域９内にレイアウトされた配線が消費する配線グリッド交点数は１１個である。また、移動するセルにより利用可能になる配線グリッド交点数は９個である。したがって、数式（２）より、Ｇｓｐａｃｅ＝９＋８−１１＝６である。よって、増加する使用可能な配線グリッド交点数は６個となり、専有されていた配線グリッド交点数が３５％減少した。
【００７４】
以上、説明したように、本発明の実施の形態１にかかる自動配置配線方法によれば、セルを移動させることにより配線混雑部の配線の混雑を緩和する。そのため、ハードマクロの位置を移動させる必要がなく、フロアプランに影響を与えずに、配線の混雑を緩和することができる。
【００７５】
また、ハードマクロの位置を移動させると、移動先が配線混雑部となってしまう可能性があるが、本発明の第１の態様では、ハードマクロの位置を移動させずに済むため、配線の混雑をより確実に緩和することができる。
【００７６】
また、複数のハードマクロに囲まれたスリット状の領域である処理領域の配線リソース量が、当該処理領域にレイアウトする配線の配線リソース量より少ない場合に、当該処理領域を前記配線混雑部として抽出する。そのため、配線リソースの確保を必要最小限に抑えることができる。また、スリット状の処理領域を可能な限りセルの配置領域として利用することができる。
【００７７】
また、セルがクロックネットワークに含まれる場合には、当該セルを移動対象セルとして設定しない。そのため、クロックネットワークに影響を与えずに、配線の混雑を緩和することができる。
【００７８】
また、移動対象セルとして設定されたセルを所望の移動先に仮移動させ、当該仮移動に伴って、セルに接続する配線を仮レイアウトした後、タイミング解析を行って、タイミングエラーが発生した場合には、当該セルを移動対象セルから除外する。したがって、セルを移動させることによって配線の混雑を緩和しても、タイミングエラーが発生することがない。
【００７９】
また、処理領域内にレイアウトされた配線がセルの入力端子に接続する場合に、当該配線の本数をカウントし、当該セルの出力端子に接続する配線の本数よりも、カウントした配線の本数の方が多い場合に、セルを移動対象セルとして設定する。また、処理領域内にレイアウトされた配線がセルの出力端子に接続する場合に、当該配線の本数をカウントし、当該セルの入力端子に接続する配線の本数よりも、カウントした配線の本数の方が多い場合に、セルを移動対象セルとして設定する。図１２に示すように、処理領域内にレイアウトされた配線が接続するセルの入力配線と出力配線との本数が異なる場合は、当該セルを移動させることにより、処理領域内の配線リソースを確保することができる。
また、この場合、当該配線が接続する他のセルの一番近くの空き領域に移動対象セルを移動させることにより、より確実に、処理領域内の配線リソースを確保することができる。
【図面の簡単な説明】
【００８０】
【図１】本発明の実施の形態１にかかる自動配置配線方法を使用する自動配置配線システムの一例を示すブロック図である。
【図２】本発明の実施の形態１にかかる自動配置配線方法を示すフローチャートである。
【図３】図２におけるステップＳ４の処理を説明するフローチャートである。
【図４】図３におけるステップＳ１０５の処理を説明するフローチャートである。
【図５】図３におけるステップＳ１０５の処理を説明するフローチャートである。
【図６】図５におけるステップＳ２１１の処理を説明するフローチャートである。
【図７】図５におけるステップＳ２１１の処理を説明するフローチャートである。
【図８】図６におけるステップＳ３０３及びステップＳ３１２の移動可否判定処理を説明するフローチャートである。
【図９】図６におけるステップＳ３０３及びステップＳ３１２の移動可否判定処理を説明するフローチャートである。
【図１０】本発明の実施の形態１にかかる自動配置配線方法によって、配線リソースが確保されるメカニズムについて説明する図である。
【図１１】本発明の実施の形態１にかかる自動配置配線方法によって、配線リソースが確保されるメカニズムについて説明する図である。
【図１２】本発明の実施の形態１にかかる自動配置配線方法によって、配線リソースが確保されるメカニズムについて説明する図である。
【図１３】本発明の実施の形態１にかかる自動配置配線方法によって、配線リソースが確保されるメカニズムについて説明する図である。
【図１４】従来の自動配置配線方法を説明するフローチャートである。
【図１５】図１４のステップＳ５０７の処理を説明するフローチャートである。
【符号の説明】
【００８１】
３、４  ハードマクロ
５、６、７、８  セル（プリミティブセル）
９  処理領域
【図１】
2010050244.tif 000003
【図２】
2010050244.tif 000004
【図３】
2010050244.tif 000005
【図４】
2010050244.tif 000006
【図５】
2010050244.tif 000007
【図６】
2010050244.tif 000008
【図７】
2010050244.tif 000009
【図８】
2010050244.tif 000010
【図９】
2010050244.tif 000011
【図１０】
2010050244.tif 000012
【図１１】
2010050244.tif 000013
【図１２】
2010050244.tif 000014
【図１３】
2010050244.tif 000015
【図１４】
2010050244.tif 000016
【図１５】
2010050244.tif 000017