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