(57)【要約】【課題】ＬＳＩのレイアウト設計において，タイミング改善と再レイアウトの繰り返しを抑え，設計期間の短縮を図る。【解決手段】論理回路を構成する論理セルを初期配置する初期配置ステップと，配置から得られた配線長に，一定長のマージンをつけて，タイミング改善する，配置ベース回路最適化ステップと，前記一定長のマージンに対応した配置変更制限を計算する配置変更制限計算ステップと，修正された論理回路の論理セル配置を改善する際に，前記配置変更制限に基づいた配置変更制限を持った配置改善を行うインクリメンタル配置ステップとを備えている。【選択図】図１
2005197558.tif 000002
【特許請求の範囲】
【請求項１】
論理回路の自動レイアウト方法であって，
論理回路を構成する論理セルを初期配置する初期配置ステップと，
配置から得られた配線長に，一定長のマージンをつけて，タイミング改善する，配置ベース回路最適化ステップと，前記一定長のマージンに対応した配置変更制限を計算する配置変更制限計算ステップと，修正された論理回路の論理セル配置を改善する際に，前記配置変更制限に基づいた配置変更制限を持った配置改善を行うインクリメンタル配置ステップと
を備えたことを特徴とする半導体集積回路の自動レイアウト方法。
【請求項２】
配置ベース回路最適化ステップで，一定長のマージンを４Ｌに設定した場合に，配置変更制限計算ステップにおいて，配置変更制限を初期配置ステップで決定した配置位置からマンハッタン距離２Ｌ（移動可能距離）とし，インクリメンタル配置ステップにおいて，移動可能距離範囲内で，論理セルを順次移動することで配置改善を行うことを特徴とする
請求項１記載の半導体集積回路の自動レイアウト方法。
【請求項３】
配置ベース回路最適化ステップで，一定長のマージンを４Ｌに設定した場合に，配置変更制限計算ステップにおいて，配置変更制限を交換可能セル探索距離として１Ｌに設定し，インクリメンタル配置ステップにおいて，初期配置ステップで決定した配置位置から互いに交換可能セル探索距離以内のセル同士を順次交換していくことで配置改善を行うことを特徴とする
請求項１記載の半導体集積回路の自動レイアウト方法。
【請求項４】
配置ベース回路最適化ステップで，一定長のマージンを４Ｌに設定した場合に，配置変更制限計算ステップにおいて，配置変更制限を交換可能セル探索距離および移動可能距離として１Ｌに設定し，インクリメンタル配置ステップにおいて，初期配置ステップで決定した配置位置から互いに交換可能セル探索距離以内のセル同士を交換する操作と，初期配置ステップで決定した配置位置から移動可能距離の範囲で，論理セルを移動する操作を任意の組み合わせで順次実行することで配置改善を行うことを特徴とする
請求項１記載の半導体集積回路の自動レイアウト方法。
【請求項５】
配置変更制限計算ステップにおいて，論理セルに接続されている配線に応じたコストを論理セルごとに計算する，論理セルコスト計算ステップと，コスト値に応じて論理セルを複数のグループに分割する，論理セルグループ分割ステップと，インクリメンタル配置ステップで設定する移動可能距離を，最もコスト値が大きいグループを２Ｌとして，コスト値が小さいグループになる程に，２Ｌより小さくする，移動可能距離再設定ステップを備えていることを特徴とする
請求項２記載の半導体集積回路の自動レイアウト方法。
【請求項６】
配置変更制限計算ステップにおいて，論理セルに接続されている配線に応じたコストを論理セルごとに計算する，論理セルコスト計算ステップと，コスト値に応じて論理セルを複数のグループに分割する，論理セルグループ分割ステップと，インクリメンタル配置ステップで設定する交換可能探索距離を，最もコスト値が大きいグループを１Ｌとして，コスト値が小さいグループになる程に，１Ｌより小さくする，交換可能探索距離再設定ステップを備えていることを特徴とする
請求項３記載の半導体集積回路の自動レイアウト方法。
【請求項７】
配置変更制限計算ステップにおいて，論理セルに接続されている配線に応じたコストを論理セルごとに計算する，論理セルコスト計算ステップと，コスト値に応じて論理セルを複数のグループに分割する，論理セルグループ分割ステップと，インクリメンタル配置ステップで設定する，移動可能距離および交換可能探索距離を，最もコスト値が大きいグループを１Ｌとして，コスト値が小さいグループになる程に，１Ｌより小さくする，探索移動距離再設定ステップを備えていることを特徴とする
請求項４記載の半導体集積回路の自動レイアウト方法。
【請求項８】
配置変更制限計算ステップの後に，論理セルに接続されている配線に応じたコストを論理セルごとに計算する，論理セルコスト計算ステップと，コスト値に応じて論理セルを複数のグループに分割する，論理セルグループ分割ステップと，小さなコスト値を持つグループ程，インクリメンタル配置ステップで，配置改善対象セルになる確率を小さく設定する，改善対象確率設定ステップとを備えていることを特徴とする
請求項２，３および４記載の半導体集積回路の自動レイアウト方法。
【請求項９】
論理セルコスト計算ステップにおいて，配線に接続する論理セルピン数に反比例する値を配線のコスト値とし，論理セルに接続される配線のコストの総和を論理セルのコスト値とする，
請求項５，６，７および８記載の半導体集積回路の自動レイアウト方法。
【請求項１０】
配置変更制限計算ステップにおいて，タイミング解析により各配線のタイミング余裕値を計算するタイミング余裕度計算ステップと，タイミング余裕値から配線長余裕値を計算する配線長余裕度計算ステップと，各配線が持つ配線長余裕度計算から，インクリメンタル配置ステップで用いる配置変更制限を計算する，余裕度配置変更制限計算ステップを備えていることを特徴とする
請求項１記載の半導体集積回路の自動レイアウト方法。
【請求項１１】
論理回路の自動的レイアウト方法であって，
論理回路を構成する論理セルを初期配置する初期配置ステップと，
配置から得られた配線長に，一定長のマージンをつけて，タイミング改善する，配置ベース回路最適化ステップと，配置ベース回路最適化ステップで変更された回路量が一定値を超えている場合は，前記一定長のマージンに基づいた配置変更制限を緩和する，配置変更制限緩和ステップと，修正された論理回路の論理セル配置を改善する際に，前記配置変更制限に基づいた配置改善を行うインクリメンタル配置ステップと，
緩和された配置変更制限を用いた配置改善を行った場合は，配置ベース回路最適化ステップに戻る終了条件判定ステップを備えたことを特徴とする半導体集積回路の自動レイアウト方法。
【請求項１２】
論理回路の自動的レイアウト方法であって，
論理回路を構成する論理セルを初期配置する初期配置ステップと，配置から得られた配線長に，一定長のマージンをつけて，タイミング改善する，配置ベース回路最適化ステップと，前記一定長のマージンに対応した配置変更制限を計算する配置変更制限計算ステップと，修正された論理回路の論理セル配置を改善する際に，前記配置変更制限に基づいた配置改善を行うインクリメンタル配置ステップと，インクリメンタル配置ステップで実現した配置品質を判定し，一定基準以下である場合は，配置変更制限を緩和して，インクリメンタル配置ステップへ戻り，そうでない場合は，条件判定ステップへ進む，配置品質判定ステップと，
緩和された配置変更制限を用いた配置改善を行った場合は，配置ベース回路最適化ステップに戻る終了条件判定ステップを備えたことを特徴とする半導体集積回路の自動レイアウト方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は，半導体集積回路のレイアウト設計において，タイミング収束をスムーズにする論理セル配置改善方法に関する。
【背景技術】
【０００２】
微細技術の進展に伴い，レイアウト設計後にタイミング設計が完了しない，タイミングクロジャー問題が発生している。その問題に対処する方法としては，レイアウト設計段階で回路を最適化する方法が提案されている（例えば、非特許文献１）。
【０００３】
これらの手法の問題点は，レイアウト情報に基づいて回路修正が実施されるが，改善した後の回路の正確なタイミング情報は，改善した回路を再レイアウトしないと分からないために，修正した回路を再レイアウトした時点で新たなタイミングバイオレーションが発生する危険があり，回路修正，再レイアウトを何度も繰り返す必要があることである。この繰り返しを防ぐ(あるいは少なくする)方法も提案されている（例えば、特許文献１）。特許文献１では，回路修正する時点でタイミングバイオレーションを起こしていないが，タイミングマージンが小さい箇所を予め余分に改善しておくことで，前記繰り返しを防止する。
【非特許文献１】（L.N.Kannan, P.R.Suaris, and H.Fang, "A methodology and algorithms for post-placement delay optimization," Proc. 31st Design Automation Conference,1994），（M.Murofushi, T.Ishioka, M.Murakata, T.Mitsuhashi, "Layout Driven Re-synthesis for Low Power Consumption LSIs," in Prop.34th Design Automation Conference,1997）
【特許文献１】特開平１０−２８４６１２号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら，従来の技術では，回路修正時に余分に直す量と再レイアウト方法との間には，関連性がないために，余分に修正しておけば，それだけ，再レイアウト時の変動に耐えやすい。ということに過ぎず，前記繰り返しを完全に無くすることはおろか，繰り返しを収束させる保証がない。これは，余裕を持って多くの回路を修正すると，回路変更量が大きくなり，その分再レイアウトで，レイアウトが大きく変更されるために，再レイアウト方法と余分に修正しておく回路量には密接な関連があるためである。
【０００５】
本発明の目的は，回路改善，再レイアウトの繰り返しを完全に無くす，或いは繰り返しの収束を保証する自動レイアウト方法を提供することである。
【課題を解決するための手段】
【０００６】
この問題を解決するために，本発明における自動レイアウト方法は，論理回路を構成する論理セルを初期配置する初期配置ステップと，配置から得られた配線長に，一定長のマージンをつけて，タイミング改善する，配置ベース回路最適化ステップと，前記一定長のマージンに対応した配置変更制限を計算する配置変更制限計算ステップと，修正された論理回路の論理セル配置を改善する際に，前記配置変更制限に基づいた配置変更制限を持った配置改善を行う，インクリメンタル配置ステップとを備えている。
【発明の効果】
【０００７】
本発明によれば、再レイアウト方法を限定することで再レイアウト時の配線変動の上限を規定し，その規定された変動を考慮したタイミング改善が実施されるので，再レイアウト後にタイミングバイオレーションが発生しない。そのために，タイミング改善，再レイアウトを繰り返し行なうことがなくなるために，設計期間を短縮することができる。
【発明を実施するための最良の形態】
【０００８】
以下に，本発明の実施の形態について，予め用意された標準（スタンダード）セルに回路をマッピングして実現するセルベース設計手法を例に，図面を用いて説明する。
【０００９】
なお，本発明はこの実施の形態に何等限定されるものではなく，要旨を逸脱しない範囲においては種々なる形態で実施しえる。
【００１０】
（第１の実施形態）
本発明の実施形態１に係るレイアウト方法について，図１に示すフローチャートを参照しながら説明する。
【００１１】
まず，ステップＳＴ１１において、論理合成機能を用いて，ＲＴレベル回路から，指定されたタイミング制約を満たす論理回路へ変換する。合成された論理回路は，スタンダードセルをマッピング（インスタンス化）して実現した論理セルにより構成される。
【００１２】
次に，ステップＳＴ１２において，前記論理セルを初期配置する。
【００１３】
次に，ステップＳＴ１３において，配置情報から得られる配線情報と，スタンダードセルの遅延情報を用いて，タイミング制約を満たしているか判定し，満たしている場合はステップＳＴ１６へ進み，もし満たしていない場合はステップＳＴ１４へ進む。
【００１４】
ステップＳＴ１４では，初期配置結果から得られる配線情報に，４Ｌのマージンを設定して，タイミング最適化を実施する。タイミング最適化方法としては，（L.N.Kannan, P.R.Suaris, and H.Fang, "A methodology and algorithms for post-placement delay optimization," Proc. 31st Design Automation Conference,1994）や（M.Murofushi, T.Ishioka, M.Murakata, T.Mitsuhashi, "Layout Driven Re-synthesis for Low Power Consumption LSIs," in Prop.34th Design Automation Conference,1997）の手法を用いることで容易に実施することが出来る。
【００１５】
ここでは，説明を簡単にするために，推定配線長は，配線を囲む矩形の半周囲長と同値として扱うことにするが，推定配線長を半周囲長と同値でなく，半周囲長に基づいた計算式を用いて計算することも可能であり，その場合は，レイアウト情報から得られた半周囲長にマージン値４Ｌを加えて計算することになる。図２は配線を囲む矩形の半周囲長の例を示した図である。
【００１６】
ステップＳＴ１４が終了した状態では，論理回路修正に伴い，論理セル同士が重なったり，論理セル同士の間隔が大きく開いたり，と，ステップＳＴ１２で実施した初期配置が乱れた状態に成っている。図３は，ステップＳＴ１４が終了した時点の論理セル配置の一例を示した図である。図３では，論理回路の修正により，論理にマッピングされたスタンダードセルが変更されて，論理セルがオーバーラップしたり，必要以上に論理セル同士の間隔がある領域が存在し，論理セル配置が乱れている。
【００１７】
ステップＳＴ１５で，乱れた論理セル配置を改善する。配置改善方法としては，論理セルを１つずつ移動する方法で行なう。ステップＳＴ１２の初期配置位置からマンハッタン距離が２Ｌの範囲を移動可能範囲として，論理セルの移動を行なう。この際，移動前後で，ステップＳＴ１２で用いた配置評価式を計算し，シミュレーティッドアニーリング等の最適手法を用いて，配置改善を行なう。図４は，論理セルＣの移動可能範囲を示した図であり，図からマンハッタン距離が２Ｌのひし形領域が移動可能範囲となることがわかる。
【００１８】
図５に示すように，各論理セルの移動可能範囲を２Ｌにした場合は，配線の囲む矩形領域の半周囲長の増加は４Ｌ以内にとどまる。
【００１９】
なお，ステップＳＴ１４で，新たに論理セルが追加された場合は，ステップＳＴ１４内で仮配置を行い配置位置を初期配置位置として，ステップＳＴ１５は実行する。
【００２０】
最後にステップＳＴ１６で論理セル間の配線を実行する。
【００２１】
以上説明したように，各論理セルの移動可能範囲を２Ｌに制限することで，ステップＳＴ１３で予め考慮したマージンの範囲である，半周囲長の増減が４Ｌに抑えられる。その結果，タイミング最適化とレイアウトを何度も繰り返すことなく，タイミング収束することが可能となり，半導体集積回路の設計期間を短縮することができる。
【００２２】
（第１の実施形態の変形例）
第１の実施形態の変形例が，第１の実施形態と異なる点は，ステップＳＴ１５で２つの論理セルの位置を交換する点である。
【００２３】
交換は，ステップＳＴ１２で得た初期配置で互いのマンハッタン距離が１Ｌの範囲（以降この範囲を移動可能セル探索範囲とする）にあるものを交換可能セル組として，順次交換することで実施される。
【００２４】
図６は，交換可能セルが，位置交換された場合に，同論理セルが初期配置位置から移動する距離を説明した図である。各論理セルは，交換可能セル探索範囲内の論理セルとは位置交換可能であり，図６は，Ｃｉ，Ｃｊは，互いの距離が最も遠い１Ｌの交換可能セル組の１つである。論理セルＣｉが，交換可能セル探索範囲境界（図中の丸の位置）の論理セルと交換された後に，論理セルＣｊと交換された場合が，論理セルＣｊが初期配置から最も遠くに移動される場合であり，その場合の移動距離は，２Ｌとなる。
【００２５】
図７は，複数の論理セルに繋がった配線の囲む領域の半周囲長の増加を説明した図である。図６で説明したように，各論理セルは最大２Ｌ移動する可能性があるので，図５の場合と同様に，配線を囲む矩形領域の半周囲長の増加は４Ｌにとどまる。
【００２６】
以上，説明したように，論理セル同士を位置交換する際に，マンハッタン距離が１Ｌ以内の論理セル同士に制限することで，ステップＳＴ１３で予め考慮したマージンの範囲である，半周囲長の増減が４Ｌに抑えられる。その結果，タイミング最適化とレイアウトを何度も繰り返すことなく，タイミング収束することが可能となり，半導体集積回路の設計期間を短縮することができる。
【００２７】
さらに，第１の実施形態の変形例では，一回の操作で２つの論理セルの位置を変更することが可能であるために，１つの論理セルを順々に移動させて改善する第１の実施形態より，配置改善される速度が速い。
【００２８】
なお，ステップＳＴ１５では，２つの論理セルの位置を交換する操作に加えて，第１の実施形態で説明した，１つの論理セルの位置を移動する操作を実行してもよい。この場合は，第１の実施形態で説明した移動可能範囲は，２Ｌではなく，１Ｌにする必要がある。
【００２９】
図８は，移動可能範囲を１Ｌにする必要があることを説明する図である。
【００３０】
論理セルＣｉが，２Ｌの範囲で移動できる場合は，図に示した位置まで移動することができる。論理セルＣｉは，交換可能セルである論理セルＣｊと，位置交換すると，論理セルＣｊは，初期配置の位置から２Ｌ以上の位置まで移動してしまう。移動可能領域は，交換セル探索領域と同じである必要があり，マンハッタン距離１Ｌの範囲である必要がある。
【００３１】
２つの操作を組み合わせて配置改善する場合は，１つの操作だけを用いて配置改善する場合より，多くのパターンの配置状態を作り出すことができるため，より最適な配置を実現することが可能となる。
【００３２】
（第２の実施形態）
本発明の実施形態２に係るレイアウト方法について、図９に示すフローチャートを用いて説明する。
【００３３】
図９中のＳＴ１１，ＳＴ１２，ＳＴ１３，ＳＴ１４，ＳＴ１６は，実施形態１と同様のステップである。
【００３４】
ステップＳＴ１４までは，実施形態１と同様の処理を行なう。
【００３５】
次に，ステップＳＴ２１の各セルの交換可能セルを抽出（生成）する。ステップＳＴ２１の処理フローは，図１０に示すフローチャートを用いて説明する。
【００３６】
まず，ステップＳＴ１０１で，修正された論理セル毎に，数１に示すコストを計算する。
【００３７】
【数１】
2005197558.tif 000003
【００３８】
数１のＰｉは，論理セルＣｉのピン数であり，Ｎｐｉは，論理セルＣｉに接続された配線Ｎｉに繋がるセル数である。
【００３９】
コスト計算式によると，多くの配線に接続されている論理セルほどコスト値が高い。すなわち，論理セルの位置を変更した場合に影響を受ける配線数が多いほど，コスト値が高くなる。また，１つの配線に着目すると，複数の論理セルに繋がった配線ほどコスト値が低い。これは，多くの論理セルに繋がった配線ほど，配線長決定において１つの論理セル位置の重要度が低くなるためである。例えば，接続セル２つまでは，どのセルが移動しても配線長の変動がある（図１１）が，それ以上になると徐々に配線長の変動しない場合（図１２）が発生する。図１２は，配線を囲む矩形領域を決定しているのは２つの論理セルだけであるので，その他の論理セルの位置が変更されても，配線を囲む矩形領域が変化しない可能性がある。このように，一般的に，配線に接続された論理セルが多くなるほど，１つの論理セルの位置移動による，配線長変動確率は低くなる。
【００４０】
このように，数１では，位置変更によって配線長影響確率が大きい論理セルほど，コスト値が大きくなるように，コスト計算される。
【００４１】
次に，ステップＳＴ１０２で，論理セルをコスト値の順番でＮ分割して，Ｎ種類のグループに分割する。Ｎは任意の整数で，使用プロセスや回路特徴にあわせて決定するものであるが，ここでは，説明を簡単にするために，Ｎを２として説明を進める。
【００４２】
次に，ステップＳＴ１０３で，コスト値の小さいグループの交換可能セル探索範囲をＬとし，コスト値の大きいグループの交換可能セル探索範囲をα×Ｌとする。αは０以上１以下の任意実数で，使用プロセスや回路特徴にあわせて決定するのものであるが，ここでは，説明を簡単にするために，αを０．５として説明を進める。
【００４３】
次に，ステップＳＴ１０４で，ステップＳＴ１０３で，互いに交換可能セル探索範囲に含まれるセル同士を交換可能セルにする。ここでの例の場合は，交換可能セル探索範囲がＬと０．５Ｌの２種類あるので，最大移動範囲は，セル毎に異なり，２Ｌ（交換可能セル探索範囲がＬ同士の場合），１．５Ｌ（交換可能セル探索範囲が１Ｌと０．５Ｌの場合），Ｌ（交換可能セル探索範囲が０．５Ｌ同士の場合）の３種類となる。
【００４４】
次に，ステップＳＴ２２において，交換可能セル情報に基づいて，ステップＳＴ１２で用いた評価式を，シミュレーティッドアニーリング等の最適化手法で最小化する。
【００４５】
最後に，第１の実施形態と同様に，ステップＳＴ１６で，論理セル間の配線を実行する。
【００４６】
以上説明したように，数１のコスト計算式を用いて，交換可能セルを決定しているので，配線変動の影響が大きいセルの位置移動範囲が抑制されて，論理セル配置が改善される。そのために，全体の配線変動が抑制されて，結果としてタイミングマージンを持った回路を実現することができる。
【００４７】
なお，ここでは，２つの論理セルを交換する場合で説明したが，交換可能セル探索範囲をそのまま移動可能範囲とすることで，第１の実施形態のように，１つの論理セルを移動する場合にも容易に適用できる。
【００４８】
（第２の実施形態の変形例１）
第２の実施形態の変形例１が，第２の実施形態と異なる点は，第２の実施形態では，ステップＳＴ２１で論理セル毎に計算したコスト値によってグループ分けし，グループ毎に交換可能セル探索範囲を決定したのに対して，第２の実施形態の変形例１では，グループ毎に交換対象選択確率を決定することである。
【００４９】
第２の実施形態におけるステップＳＴ２２では，交換対象セルの選択確率（Ｐ）は全論理セルが同値（Ｐ＝１／セル総数）であるために，無作為に論理セルが選択されて改善されていくが，第２の実施形態の変形例１では，第２の実施形態におけるステップＳＴ１０２で決定したグループ毎に，論理セル選択確率を変更する（コスト値の大きいグループの選択確率はコスト値の小さいグループの選択確率より小さくする）。
【００５０】
例えば，コスト値の小さいグループは選択確率をＰのままとし，コスト値の大きいグループを０．５Ｐとすることで実現する。
【００５１】
以上説明したように，数１のコストを用いて，位置変更セルの選択確率を決定しているので，優先的に配線変動の影響の小さい論理セルを用いて，論理セル配置が改善される。そのために，全体の配線変動が抑制されて，タイミングマージンを持った回路を実現することができる。
【００５２】
なお，ここでは，２つの論理セルを交換する場合で説明したが，１つの論理セルを移動する場合も同様の方法で適用できる。
【００５３】
（第２の実施形態の変形例２）
第２の実施形態の変形例２が，第２の実施形態と異なる点は，第２の実施形態では，ステップＳＴ２１でセル毎に計算したコスト値によってグループ分けし，グループ毎に交換可能セル探索範囲を決定したのに対して，第２の実施形態の変形例２では，各配線の余裕値に基づいて，論理セル固有の交換可能セル探索範囲を決定することである。第２の実施形態では，交換可能セル探索範囲が１Ｌを超えないのに対して，第２の実施形態の変形例２では，１Ｌを超える場合が存在する。
【００５４】
数２は，論理セルＣｉの交換可能セル探索範囲Ｒｉの計算式を示している。
【００５５】
【数２】
2005197558.tif 000004
【００５６】
ΔＬｉは，ステップＳＴ１３の回路修正結果から計算できる各配線の余裕値であり，ＭＩＮはΔＬｉの内の最小値である。
【００５７】
ステップＳＴ１３では，各配線に対して４Ｌのマージンを設定しているので，各配線には最低４Ｌの余裕値はある。配線によっては，回路修正前から一定（例えばＬｓ）の余裕がある場合があり，その場合は，ステップＳＴ１３で４Ｌのマージンを設定したことで，Ｌｓ＋４Ｌの余裕値になり，Ｒｉは（Ｌｓ＋４Ｌ）／４となる。
【００５８】
以上説明したように，数２により，論理セルに接続される配線の最も小さい余裕が，４Ｌより大きい場合は，その論理セルの交換可能探索範囲が広がるので，ステップＳＴ２２の最適化での探索空間が広がり，より最適な論理セル配置を実現することが出来る。
【００５９】
なお，ここでは，２つの論理セルを交換する場合で説明したが，交換可能セル探索範囲をそのまま移動可能範囲とすることで，第１の実施形態のように，１つの論理セルを移動する場合にも容易に適用できる。
【００６０】
（第３の実施形態）
本発明の実施形態３に係るレイアウト方法について、図１３に示すフローチャートを用いて説明する。
【００６１】
図１３中のＳＴ１１，ＳＴ１２，ＳＴ１３，ＳＴ１４，ＳＴ１５，ＳＴ１６は，実施形態１と同様のステップである。
【００６２】
まず，ステップＳＴ１４までは，実施形態１と同様の処理を行なう。
【００６３】
次に，ステップＳＴ３１で，ステップＳＴ１４で修正した論理回路の回路変更量を計算し，変更量が一定値を超えている場合は，ステップＳＴ３２に進み，交換可能セル探索範囲１Ｌを１Ｌ＋ΔＬに置き換える。超えていない場合は，ステップＳＴ１５へ進む。ここでΔＬは，正の値である。
【００６４】
回路修正量としては，論理セル面積増減の絶対値の総和等を用いることで容易に表現できる。
【００６５】
次にステップＳＴ１５で，実施形態１と同様の論理セルの配置改善処理を行なう。
【００６６】
ステップＳＴ３２で交換可能セル探索範囲１Ｌを１Ｌ＋ΔＬに置き換えているために，ステップＳＴ１４で考慮しているマージン４Ｌを超えた配線長変動が発生する場合がある。そのために，ステップＳＴ３３で交換可能セル探索範囲１Ｌを置き換えたかを判定し，置き換えた場合は，ステップＳＴ１３から再度やり直す。交換可能セル探索範囲１Ｌを置き換えていない場合は，ステップＳＴ１６で論理セル間の配線を行なう。
【００６７】
論理回路の修正量が多い場合は，ステップＳＴ１２で行なった初期配置からの乱れが大きい。特に配線密度の最適性が著しく低下している場合等は，一時的にタイミングエラーが発生しても，論理セル配置を改善しないと，ステップＳＴ１６の論理セル間配線が完了しない。
【００６８】
以上説明したように，第３の実施形態では，論理回路修正量が大きいために，初期論理セル配置が大きく変更された場合は，一時的にタイミングエラーを発生させても，論理セルの配置改善が行なわれるようになるので，確実に配線ステップまで完了して，レイアウトを完成させることが出来る。
【００６９】
（第３の実施形態の変形例）
第３の実施形態の変形例が，第３の実施形態と異なる点は，第３の実施形態では，ステップＳＴ１４で修正した回路修正量に基づいて，制約１Ｌを緩和するステップＳＴ３２を実行しているのに対して，第３の実施形態の変形例では，ステップＳＴ１５の論理セルの配置改善が十分でない（評価値が最適でない）場合に，交換可能セル探索範囲１Ｌを緩和するステップＳＴ３２が実行される点である。
【００７０】
本発明の実施形態３の変形例に係るレイアウト方法について、図１４に示すフローチャートを用いて説明する。
【００７１】
図１４中のＳＴ１１，ＳＴ１２，ＳＴ１３，ＳＴ１４，ＳＴ１５，ＳＴ１６は，実施形態１と同様のステップであり，ＳＴ３１，ＳＴ３２，ＳＴ３３は，実施形態３と同様のステップである。
【００７２】
まず，ステップＳＴ１４まで，実施形態１と同様の処理を行なう。
【００７３】
次にステップＳＴ３４で，ステップＳＴ１５の最終結果である配置評価値を評価し，十分小さい場合はステップＳＴ３３へ進み，そうでない場合は，ステップＳＴ３２に進む。
【００７４】
ステップＳＴ３２に進んだ場合は，第３の実施形態と同様に，交換可能セル探索範囲１Ｌを１Ｌ＋ΔＬに置き換えて，ステップ１３からやり直す。
【００７５】
ステップＳＴ３３に進んだ場合は，第３の実施形態と同様に，交換可能セル探索範囲１Ｌを置き換えたかを判定し，置き換えた場合は，ステップＳＴ１３から再度やり直す。交換可能セル探索範囲１Ｌを置き換えていない場合は，ステップＳＴ１６でスタンダードセル間の配線を行なう。
【００７６】
配置改善ステップＳＴ１４で，配置の最適性が低い場合，特に配線密度の最適性が著しく低下している場合等は，一時的にタイミングエラーが発生しても，論理セルの配置を改善しないと，ステップＳＴ１６のスタンダードセル間配線が完了しない。
【００７７】
以上説明したように，第３の実施形態の変形例では，十分な配置改善が行なわれない場合は，一時的にタイミングエラーが発生しても，配置改善が行なわれるようになるので，確実に配線ステップまで完了して，レイアウトを完成させることが出来る。
【産業上の利用可能性】
【００７８】
本発明にかかる半導体集積回路のレイアウト設計方法は、レイアウト配置変更制限を計算する配置変更制限計算ステップを有し、レイアウト修正を早期に収束させるレイアウト設計方法として有用である。
【図面の簡単な説明】
【００７９】
【図１】本発明の第１の実施形態の処理フローを示す図
【図２】配線を囲む矩形領域の半周囲長を示す図
【図３】論理セル配置の粗密を示す図
【図４】論理セル移動可能範囲を示す図
【図５】論理セルを移動した場合の配線長変動を示す図
【図６】論理セル交換可能セル探索範囲を示す図
【図７】論理セルを交換した場合の配線長変動を示す図
【図８】論理セルを移動，交換した場合の配線長変動を示す図
【図９】本発明の第２の実施形態の処理フローを示す図
【図１０】交換可能セルの抽出処理フローを示す図
【図１１】コスト計算式を示す図
【図１２】配線を囲む矩形領域を決定している論理セルを示す図
【図１３】本発明の第３の実施形態の処理フローを示す図
【図１４】本発明の第３の実施形態の変形例の処理フローを示す図
【符号の説明】
【００８０】
ＳＴ１１  論理合成ステップ
ＳＴ１２  初期配置ステップ
ＳＴ１３  タイミング判定ステップ
ＳＴ１４  回路最適化ステップ
ＳＴ１５  インクリメンタル配置ステップ
ＳＴ１６  配線実行ステップ
【図１】
2005197558.tif 000005
【図２】
2005197558.tif 000006
【図３】
2005197558.tif 000007
【図４】
2005197558.tif 000008
【図５】
2005197558.tif 000009
【図６】
2005197558.tif 000010
【図７】
2005197558.tif 000011
【図８】
2005197558.tif 000012
【図９】
2005197558.tif 000013
【図１０】
2005197558.tif 000014
【図１１】
2005197558.tif 000015
【図１２】
2005197558.tif 000016
【図１３】
2005197558.tif 000017
【図１４】
2005197558.tif 000018