(57)【要約】【課題】計算の処理速度が速く且つ計算精度が高い配線困難度の計算方法を提供する。【解決手段】ネットリストの各セルに対し、より多くのネット数で相互接続されるもの同士を逐次的にグループピングすることで階層的クラスタリングを行い（Ｓ１）、前記ネットリストの各ネットを、そのネットに接続された全てのセルを一括して含むグループが第ｎ階層の各グループのなかに存在し且つ第（ｎ−１）階層の各グループのなかに存在しない場合に第ｎ階層に属させることで、階層的クラスタリングの各階層の何れかに属させ（Ｓ２）、前記ネットリストの各ネットの配線長の見積値を、そのネットの属する階層が下位であるほど小さい値に設定し（Ｓ３）、その設定に基づき前記ネットリストの各ネットの配線長の見積値を合計して前記ネットリストの総配線長の見積値を計算し（Ｓ４）、その計算結果を前記ネットリストの回路規模で割って前記ネットリストの配線難易度を計算する（Ｓ５）。【選択図】図１
2009020786.tif 000002
【特許請求の範囲】
【請求項１】
（ａ）複数のセルがネットにより接続されてなるネットリストの前記各セルに対し、より多くのネット数で相互接続されるもの同士を逐次的にグループピングすることで、階層的クラスタリングを行う工程と、
（ｂ）前記ネットリストの各ネットを、そのネットに接続された全ての前記セルを一括して含むグループが第ｎ階層の各グループのなかには存在し且つ第（ｎ−１）階層の各グループのなかには存在しない場合に、第ｎ階層に属させることで、前記工程（ａ）の階層的クラスタリングの各階層の何れかに属させる工程と、
（ｃ）前記ネットリストの各ネットの配線長の見積値を、そのネットの属する階層が下位であるほど小さい値に設定する工程と、
（ｄ）前記工程（ｃ）の見積値の設定に基づき前記ネットリストの各ネットの配線長の見積値を合計して、前記ネットリストの総配線長の見積値を計算する工程と、
（ｅ）前記ネットリストの前記総配線長の見積値を前記ネットリストの回路規模で割って前記ネットリストの配線難易度を計算する工程と、
を備えることを特徴とするネットリストの配線難易度計算方法。
【請求項２】
前記工程（ｃ）で設定する前記各ネットの前記配線長の見積値は、そのネットの属する階層の各グループの平均サイズの平方根であることを特徴とする請求項１に記載のネットリストの配線難易度計算方法。
【請求項３】
前記工程（ｅ）で用いる前記ネットリストの回路規模は、前記ネットリスト中の各セルの面積の総和であることを特徴とする請求項１に記載のネットリストの配線難易度計算方法。
【請求項４】
前記工程（ｃ）において、前記ネットリストの各ネットの配線長の見積値を、そのネットの属する階層が下位であるほど小さい値に設定すると共にそのネットのファンアウト数が小さいほど小さい値に設定することを特徴とする請求項１に記載のネットリストの配線難易度計算方法。
【請求項５】
前記工程（ｃ）において、第ｎ階層に属するネットの配線長の見積値として、第ｎ階層の各グループの平均サイズの平方根にファンアウト係数を乗じたものを用いることを特徴とする請求項４に記載のネットリストの配線難易度計算方法。
【請求項６】
前記工程（ａ）−（ｅ）の実施後に前記ネットリストのネットの接続状態が部分的に変更された場合の、そのネットリストの配線難易度を計算する方法であって、
（ｆ）前記工程（ｅ）の実施後のネットリストのネットの接続状態を部分的に変更する工程と、
（ｇ）前記工程（ａ）での階層的クラスタリングにおける最上位階層以外の各階層の各グループのうち、接続状態の変更された全てのネットおよびそれら各ネットに接続した全てのセルを一括してまたは部分ずつ含むグループを選択する工程と、
（ｇ）選択された前記グループに含まれる下位階層の各グループのグループピングを解除した後、選択された前記グループに含まれる各セルおよび各ネットに対して前記工程（ａ）−（ｃ）を実施することで、選択された前記グループに含まれる全てのネットの配線長の見積値を再設定する工程と、
（ｈ）選択された前記グループに含まれる各ネットに対しては、前記工程（ｇ）で再設定された配線長の見積値を使用し、選択された前記グループに含まれない各ネットに対しては、既に設定されている配線長の見積値を使用して、前記工程（ｄ）および（ｅ）を実施することで、前記工程（ｆ）でネットの接続状態の変更された前記ネットリストの配線難易度を計算する工程と、
を備えることを特徴とする請求項１に記載のネットリストの配線難易度計算方法。
【請求項７】
前記工程（ｆ）では、接続状態の変更された全てのネットおよびそれら各ネットに接続した全てのセルを含むグループのうち、より低い階層のグループを選択することを特徴とする請求項６に記載のネットリストの配線難易度計算方法。
【請求項８】
前記セルは、機能ブロックまたはＬＳＩチップであることを特徴とする請求項１ないし７の何れかに記載のネットリストの配線難易度計算方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットリストの配線難易度を計算する方法に関する。
【背景技術】
【０００２】
従来のＬＳＩの設計フローでは、ＲＴＬ設計、論理合成、レイアウト設計、そのレイアウト設計の設計結果に基づく配線難易度の計算、そしてその配線難易度の計算結果に基づく配線難易度の判定という順番で各処理が行われている。そしてその配線難易度の判定の結果、配線難易度が基準値よりも高い場合は、ＲＴＬ設計を修正し、その修正したＲＴＬ設計に基づき再び始めから上記の各処理が行われ、最終的に配線難易度が基準値よりも低くなるまで上記の各処理が繰り返される。
【０００３】
その際に使用される配線難易度の計算方法としては、高速配置配線による計算方法（例えば特許文献１）が知られている。この計算方法は、レイアウト設計ツールに標準的に装備された高速配置配線エンジンを用いて、論理合成の結果得られるネットリストに基づきレイアウト設計をし、そのレイアウト設計に基づき配線難易度を計算している。
【０００４】
また他の配線難易度の計算方法として、ファンアウト数による計算方法が知られている。この計算方法は、ファンアウト数（接続する入力ピン数）が多いネットほど配線長が長くなり配線難となるという考えに基づく計算方法であり、論理合成の結果得られるネットリストに対し、１ネット当たりのファンアウト数の平均値を配線難易度として用いている。
【０００５】
【特許文献１】特開２００５−３１６６４７号公報
【非特許文献１】Charles J. Alpert, Jen-Hsin Huang, Andrew B. Kahng, "Multilevel Circuit Partitioning",Proceedings of Design Automation Conference, pp.530-533, 1997.
【発明の開示】
【発明が解決しようとする課題】
【０００６】
上記の高速配置配線による計算方法では、計算精度は良いが、計算の処理速度が遅いという問題点がある。
【０００７】
他方、上記のファンアウト数による計算方法では、計算の処理速度は速いが、計算精度が悪いという問題点がある。
【０００８】
この発明は、上記のような問題点を解決するためになされたものであり、速い処理速度で且つ高い計算精度で配線困難度を計算できる配線難易度計算方法を提供することを目的としている。
【課題を解決するための手段】
【０００９】
上記課題を解決する為に、本発明の第１の形態は、（ａ）複数のセルがネットにより接続されてなるネットリストの前記各セルに対し、より多くのネット数で相互接続されるもの同士を逐次的にグループピングすることで、階層的クラスタリングを行う工程と、（ｂ）前記ネットリストの各ネットを、そのネットに接続された全ての前記セルを一括して含むグループが第ｎ階層の各グループのなかには存在し且つ第（ｎ−１）階層の各グループのなかには存在しない場合に、第ｎ階層に属させることで、前記工程（ａ）の階層的クラスタリングの各階層の何れかに属させる工程と、（ｃ）前記ネットリストの各ネットの配線長の見積値を、そのネットの属する階層が下位であるほど小さい値に設定する工程と、（ｄ）前記工程（ｃ）の見積値の設定に基づき前記ネットリストの各ネットの配線長の見積値を合計して、前記ネットリストの総配線長の見積値を計算する工程と、（ｅ）前記ネットリストの前記総配線長の見積値を前記ネットリストの回路規模で割って前記ネットリストの配線難易度を計算する工程と、を備えるものである。
【発明の効果】
【００１０】
本発明の第１の形態によれば、ネットリストの各セルに対し、より多くのネット数で相互接続されるもの同士（即ち互いに近くに配置される傾向の強いもの同士）を逐次的にグループピングすることで階層的クラスタリングを行い、前記ネットリストの各ネットを、そのネットに接続された全てのセルを一括して含むグループが第ｎ階層の各グループのなかには存在し且つ第（ｎ−１）階層の各グループのなかには存在しない場合に第ｎ階層に属させることで、前記階層的クラスタリングの各階層の何れかに属させ、前記ネットリストの各ネットの配線長の見積値を、そのネットの属する階層が下位であるほど小さい値に設定するので、互いに近くに配置される傾向の強いセル間のネットの配線長の見積値には小さな値を設定できる。これにより、各ネットの配線長の見積値に実際の配線長に近い値を設定できるので、高い計算精度で配線困難度を計算できる。またネットリストを用いて配線困難度を計算するので、速い処理速度で配線困難度を計算できる。
【発明を実施するための最良の形態】
【００１１】
実施の形態１．
この実施の形態に係るネットリストの配線難易度計算方法は、回路のＲＴＬ設計および論理合成によって作成されたネットリストを用いて、レイアウト設計前に、回路の配線難易度の計算を行うものである。
【００１２】
まず概要を説明すると、この実施の形態に係るネットリストの配線難易度計算方法では、図２の様に、ネットリストＮＲの各セルＣに対してセルＣ間の接続強度に基づき階層的クラスタリングを実施し、各階層毎にネットＮの配線長の見積値を異なる値に設定し、全階層に渡って各ネットＮの配線長の見積値を合計して総配線長を計算し、この総配線長を用いて配線難易度を計算する。このとき、下位階層のネットＮほど配線長の見積値が小さい値になる様に各ネットＮに配線長の見積値を設定する。また階層的クラスタリングでは、互いにより多数のネットＮにより相互接続するもの同士が同一グループになる様にグルーピングする。
【００１３】
配線難易度（レイアウト難易度）は、単位面積あたりの配線長（即ち総配線長／ネットリスト回路規模）の大小で判定される。この値が所定の基準値よりも大きい場合は、配線困難と判定され、ＲＴＬ設計や論理合成に戻ってネットリストＮＲを改善することになる。
【００１４】
この様にこのネットリストの配線難易度計算方法では、レイアウト設計前にネットリストＮＲを用いて回路の配線難易度を計算し、配線困難であればネットリストＮＲを改善することで、処理時間の掛かるレイアウト設計を何度も経ないで済み（図１２参照）、設計フロー全体の期間を短縮できる利点がある。また合成ツール（論理合成や高位合成ツール）により、ネットリストＮＲの配線難易度を考慮しながら、配線難易度の低いネットリストＮＲを生成する処理を行うことによっても、同様の効果が期待できる。
【００１５】
以下、この実施の形態に係るネットリストの配線難易度計算方法の詳細を、図１に基づき説明する。
【００１６】
まずステップＳ１で、図２の様に、論理合成の結果得られるネットリスト（即ち回路中の各セルＣがネットＮにより接続されてなるネットリスト）の各セルＣに対し、より多くのネット数で相互接続されるもの同士を逐次的にグループピングすることで、階層的クラスタリング（階層的グルーピング）を行う。
【００１７】
より詳細には、ネットリストＮＲの各セルＣをメンバーとして、各セルＣを例えば少数（例えば２つ）毎にグループピングすることで、第１階層の各グループＧ１を形成する。その際、より多くのネット数で相互接続されるセルＣ同士を優先的に、且つ各グループＧ１のサイズ（各グループＧ１内の各セルＣの面積の総和）が均一になる様に、グルーピングする。そして第１階層の各グループＧ１をメンバーとして、各グループＧ１を例えば少数（例えば２つ）毎にグループピングすることで、第２階層の各グループＧ２を形成する。その際も、より多くのネット数で相互接続されるグループＧ１同士を優先的に、且つ各グループＧ２のサイズ（各グループＧ２内の各セルＣの面積の総和）が均一になる様に、グルーピングする。一般に第ｎ階層の各グループＧｎをメンバーとして、各グループＧｎを例えば少数毎にグループピングすることで、第（ｎ＋１）階層の各グループＧ（ｎ＋１）を形成する。その際、より多くのネット数で相互接続されるグループＧｎ同士を優先的に、且つ各グループＧ（ｎ＋１）のサイズ（各グループＧ（ｎ＋１）内の各セルＣの面積の総和）が均一になる様に、グルーピングする。そしてこの様なグルーピングを、最終的に１つのグループになるまで上記の様に逐次的に繰り返すことで、階層的クラスタリングを行う。尚、グルーピングの手法としては、既存の手法が複数知られている（たとえば非特許文献１）。
【００１８】
次にステップＳ２で、ネットリストＮＲの各ネットＮを、そのネットＮに接続された全てのセルＣを一括して含むグループが第ｎ階層の各グループＧｎのなかには存在し且つ第（ｎ−１）階層の各グループＧ（ｎ−１）のなかには存在しない場合に、第ｎ階層に属させることで、ステップＳ１の階層的クラスタリングの各階層の何れかに属させる。これによりここでは、図２の各ネットＮのうち、図３に抽出された各ネットＮが第１階層に属するネットＮ１とされ、図４に抽出された各ネットＮが第２階層に属するネットＮ２とされ、図５に抽出された各ネットＮが第３階層に属するネットＮ３とされる。
【００１９】
次にステップＳ３で、ネットリストＮＲの各ネットＮの配線長の見積値ｈを、そのネットＮの属する階層が下位であるほど小さい値に設定する。ここでは例えば、各ネットＮの配線長の見積値ｈとして、そのネットＮの属する階層の各グループＧの平均サイズ（即ち各グループＧ内の各セルＣの面積Ｓの総和（セル数×Ｓ）の平均値）の平方根を用いる。この場合、各ネットＮ１の配線長の見積値ｈ１は、各グループＧ１内のセル数は平均２個なので、ｈ１＝（２Ｓ）1/2≒１．４×Ｓ1/2となる。またネットＮ２の配線長の見積値ｈ２は、各グループＧ２内のセル数は平均４個なので、ｈ２＝（４Ｓ）1/2 ＝２×Ｓ1/2 となる。またネットＮ３の配線長の見積値ｈ３は、各グループＧ３内のセル数は１６個なので、ｈ３＝（１６Ｓ）1/2 ＝４×Ｓ1/2 となる。
【００２０】
次にステップＳ４で、ネットリストＮＲの各ネットＮの配線長の見積値ｈを合計して、ネットリストＮＲの総配線長の見積値Ｈを計算する。ここでは、見積値Ｈは、Ｈ＝（ネットＮ１の個数）×ｈ１＋（ネットＮ２の個数）×ｈ２＋（ネットＮ３の個数）×ｈ３となる。
【００２１】
次にステップＳ５で、ネットリストＮＲの総配線長の見積値ＨをネットリストＮＲの回路規模Ｒで割ってネットリストＮＲの配線難易度Ｐ（＝Ｈ／Ｒ）を計算する。ここでは例えば、ネットリストＮＲの回路規模Ｒとして、ネットリストＮＲ中の各セルＣの面積Ｓの総和（即ちネットリストＮＲ中の全セル数×Ｓ）を用いる。この様にして、このネットロストの配線難易度計算方法では、ネットリストを用いて配線難易度Ｐが計算される。尚、この様にして計算された配線難易度Ｐは、回路に応じて設定された基準値と比較され、その基準値との大小関係に応じて配線難易度が判定される。
【００２２】
次にこのネットリストの配線難易度計算方法とファンアウト数による計算方法（従来の配線難易度計算方法）との比較を検討する。図６および図７の各ネットリストＮＲａ，ＮＲｂはそれぞれ、セル数＝４、ネット数＝６およびファンアウト数の合計＝７は同じで、ネットＮの接続状態だけが異なり、一見してネットリストＮＲｂの方がネットリストＮＲａよりも配線が困難であることが分かる。
【００２３】
ネットリストＮＲａの場合は、このネットリストの配線難易度計算方法では、第１階層に属するネットＮ１のネット数＝５、第２階層に属するネットＮ２のネット数＝１、ネットＮ１の配線長の見積値ｈ１＝１．４×Ｓ1/2、ネットＮ２の配線長の見積値ｈ２＝２×Ｓ1/2となるので、ネットリストＮＲａの配線難易度Ｐ１ａ＝（５×１．４×Ｓ1/2＋１×２×Ｓ1/2）／（４×Ｓ）＝８×Ｓ1/2／（４×Ｓ）となる。他方、ファンアウト数による計算方法では、ファンアウト数の合計＝７なので、ネットリストＮＲａの配線難易度Ｐ２ａ＝平均ファンアウト数（＝ファンアウト数／ネット数）＝７／６となる。
【００２４】
他方、ネットリストＮＲｂの場合は、このネットリストの配線難易度計算方法では、第１階層に属するネットＮ１のネット数＝２、第２階層に属するネットＮ２のネット数＝４、ネットＮ１の配線長の見積値ｈ１＝１．４×Ｓ1/2、ネットＮ２の配線長の見積値ｈ２＝２×Ｓ1/2となるので、ネットリストＮＲｂの配線難易度Ｐ１ｂ＝（２×１．４×Ｓ1/2＋４×２×Ｓ1/2）／（４×Ｓ）＝１０．８×Ｓ1/2／（４×Ｓ）となる。他方、ファンアウト数による計算方法では、ファンアウト数の合計＝７なので、ネットリストＮＲｂの配線難易度Ｐ２ｂ＝平均ファンアウト数（＝ファンアウト数／ネット数）＝７／６となる。
【００２５】
これらの結果から、このネットリストの配線難易度計算方法では、Ｐ１ａ＜Ｐ１ｂとなり、ネットリストＮＲｂの方がネットリストＮＲａよりも配線困難であると判定されるので、適切に配線難易度が判定されるが、ファンアウト数による計算方法では、Ｐ２ａ＝Ｐ２ｂとなり、配線難易度が同じと判定され、適切に配線難易度が判定されない。この事から、このネットリストの配線難易度計算方法は、ファンアウト数による計算方法よりも、配線困難度の計算の精度が高いと言える。
【００２６】
この原因を考察すると、このネットリストの配線難易度計算方法では、セルＣ間の接続強度（即ちセルＣ間のネット数）に基づき階層的クラスタリングを行う。このとき、セルＣ間の接続強度の強い（即ちセルＣ間のネット数の多い）セル同士は同一グループにされる。これは、セルＣ間の接続強度の強いセル同士は、配置配線プログラムにより、互いに近くに配置される傾向があるからである。即ち、同一グループ内に含まれるネットＮは、異なるグループ間を接続するネットＮよりも、配置配線プログラムにより配線長が短く設定される傾向がある。
【００２７】
このネットリストの配線難易度計算方法では、この傾向を考慮して、同一グループ内に含まれるネット（即ち下位階層に属するネット）Ｎの配線長の見積値ｈを、異なるグループ間を接続するネット（即ち上位階層に属するネット）Ｎの配線長の見積値ｈよりも小さな値に設定することで、セルＣ間の接続強度を考慮して配線難易度を計算するのに対し、ファンアウト数による計算方法では、セルＣ間の接続強度を考慮しないで配線難易度を計算するので、このネットリストの配線難易度計算方法の方が、ファンアウト数による計算方法よりも、配線困難度の計算の精度が高くなっている。
【００２８】
次にこのネットリストの配線難易度計算方法と高速配置配線による計算方法との比較を検討する。このネットリストの配線難易度計算方法では、ネットリストＮＲを用いることで、レイアウト設計前に回路の配線難易度の計算を行うので、レイアウト設計の設計結果を用いる、高速配置配線による計算方法よりも、計算の処理速度は当然速くなる。
【００２９】
以上の様に説明したネットリストの配線難易度計算方法によれば、ネットリストＮＲの各セルＣに対し、より多くのネット数で相互接続されるもの同士（即ち互いに近くに配置される傾向の強いもの同士）を逐次的にグループピングすることで階層的クラスタリングを行い、ネットリストＮＲの各ネットＮを、そのネットＮに接続された全てのセルＣを一括して含むグループＧが第ｎ階層の各グループＧｎのなかには存在し且つ第（ｎ−１）階層の各グループＧ（ｎ−１）のなかには存在しない場合に、第ｎ階層に属させることで、階層的クラスタリングの各階層の何れかに属させ、ネットリストＮＲの各ネットＮの配線長の見積値ｈを、そのネットＮの属する階層が下位であるほど小さい値に設定するので、互いに近くに配置される傾向の強いセル間のネットの配線長の見積値には小さい値を設定できる。これにより、各ネットＮの配線長の見積値に実際の配線長に近い値を設定できるので、高い計算精度で配線困難度を計算できる。またネットリストＮＲを用いて配線困難度を計算するので、速い処理速度で配線困難度を計算できる。
【００３０】
また各ネットＮの配線長の見積値ｈは、そのネットＮの属する階層の各グループＧ内の各セルＣの面積の総和の平均値の平方根であるので、簡単な式で、各ネットＮの配線長の見積値ｈを、そのネットＮの属する階層が下位であるほど小さい値に設定できる。
【００３１】
実施の形態２．
この実施の形態に係るネットリストの配線難易度計算方法は、実施の形態１において、ネットリストＮＲの各ネットＮの配線長の見積値ｈを、そのネットＮの属する階層が下位であるほど小さい値に設定すると共にそのネットＮのファンアウト数が小さいほど小さい値に設定する様にしたものである。具体的には例えば、第ｎ階層に属するネットＮの配線長の見積値ｈとして、第ｎ階層の各グループＧｎの平均サイズ（即ち各グループＧ内の各セルＣの面積Ｓの総和の平均値）の平方根にファンアウト係数を乗じたものを用いる。ここで、ファンアウト係数とは、ファンアウト数毎に定義された実数値であり、ファンアウト数が大きいほど大きな値となる。このファンアウト係数としては、実際の回路を配置配線した結果から統計的に値を得てテーブル形式で保存したものを用いる。尚、上記の説明以外の処理は、実施の形態１と同じなので、説明を省略する。
【００３２】
以上の様に説明したネットリストの配線難易度計算方法によれば、ネットリストＮＲの各ネットＮの配線長の見積値ｈを、そのネットＮの属する階層が下位であるほど小さい値に設定すると共にそのネットＮのファンアウト数が小さいほど小さい値に設定するので、セルＣ間の接続強度だけでなくファンアウト数も考慮でき、より計算精度良く配線困難度を計算できる。
【００３３】
また第ｎ階層に属するネットＮの配線長の見積値ｈとして、第ｎ階層の各グループＧｎの平均サイズの平方根にファンアウト係数を乗じたものを用いるので、簡単な式で、セル間の接続強度だけでなくファンアウト数も考慮できる。
【００３４】
実施の形態３．
この実施の形態に係るネットリストの配線難易度計算方法は、実施の形態１において、ステップＳ１−Ｓ５の実施後にネットリストＮＲのネットＮの接続状態が部分的に変更された場合の、そのネットリストＮＲの配線難易度Ｐを計算する方法である。以下、この実施の形態に係るネットリストの配線難易度計算方法を、図８に基づき説明する。
【００３５】
まずステップＳ６で、ステップＳ１−Ｓ５の実施後のネットリストＮＲのネットＮの接続状態が部分的に変更される。ここでは例えば、ネットリストＮＲの一部のネットＮｂ１，Ｎｂ２，Ｎｂ３（図９）が削除され、その代わりに、図１０の様にセルＣ１，Ｃ２間およびセルＣ３，Ｃ４間にそれぞれ各ネットＮａ１，Ｎａ２が新たに接続される。
【００３６】
次にステップＳ７で、ネットリストＮＲにおける最上位階層以外の各階層の各グループＧのうち、接続状態の変更された全てのネットＮａ１，Ｎａ２およびそれら各ネットに接続した全てのセルＣ１，Ｃ２，Ｃ３，Ｃ４を一括して含むグループＧを選択する。その際ここでは、その全てのネットＮａ１，Ｎａ２およびその全てのセルＣ１，Ｃ２，Ｃ３，Ｃ４を一括して含むグループＧのうち、最も低い階層（より低い階層）のグループ（ここでは第２階層のグループＧ２ｓ）を選択する。
【００３７】
尚、ここでは、ネットリストＮＲの一部（局所的に集中した一カ所）のみでネットＮの接続状態が変更されたので、接続状態の変更された全てのネットＮａ１，Ｎａ２およびそれら各ネットに接続した全てのセルＣ１，Ｃ２，Ｃ３，Ｃ４を含むグループＧとして、それら全てのネットＮａ１，Ｎａ２およびそれら全てのセルＣ１，Ｃ２，Ｃ３，Ｃ４を一括して含むグループＧ２ｓを選択するが、ネットリストＮＲの複数カ所（互いに空間的に離れた複数カ所）でネットＮの接続状態が変更された場合は、接続状態の変更された全てのネットＮａおよびそれら各ネットに接続した全てのセルＣを含むグループＧとして、それら全てのネットＮａおよびそれら全てのセルＣの部分ずつ（各カ所毎）を含む複数のグループＧを選択しても構わない。この様にすることで、それら全てのネットＮａおよびそれら全てのセルＣを一括して含むグループＧよりも低い階層のグループＧを選択でき、その方が後の処理を軽減できる。尚、この様に部分ずつ含むグループＧを選択する場合も、上記同様、最も低い階層（より低い階層）のグループＧを選択することが望ましい。
【００３８】
次にステップＳ８で、選択されたグループＧ２ｓに含まれる下位階層の各グループ（ここではＧ１ａ，Ｇ１ｂ（図９））のグループピングを解除し、そのグループＧ２ｓに含まれる全てのセル（ここではＣ１，Ｃ２，Ｃ３，Ｃ４）および全てのネット（ここではＮａ１，Ｎａ２）に対してステップＳ１−Ｓ３を実施して、グループＧ２ｓに含まれる全てのネットＮａ１，Ｎａ２の配線長の見積値ｈを再設定する。尚、ここでは、そのネットＮに接続する全てのセルＣが同一グループＧに含まれる場合に、そのネットＮは前記同一グループＧに含まれるものとするが、そうする代わりに、そのネットＮに接続するセルＣの１つが或るグループＧに含まれる場合は、そのネットＮは前記或るグループＧに含まれるとしてもよい。
【００３９】
より詳細には、ステップＳ８では、先ず、グループＧ２ｓに含まれる全てのセルＣ１，Ｃ２，Ｃ３，Ｃ４に対してのみ、変更後のネットＮの接続状態に基づき、ステップＳ１を実施して階層的クラスタリングを行う。これにより、例えば図１１の様に、各セルＣ１，Ｃ２が第１階層のグループＧ１ｃとして新たにグルーピングされ、各セルＣ２，Ｃ４が第１階層のグループＧ１ｄとして新たにグルーピングされる。そして、グループＧ２ｓに含まれる各ネットＮａ１，Ｎａ２を、ステップＳ２と同様にして、階層的クラスタリングの各階層の何れかに属させる。ここでは、各ネットＮａ１，Ｎａ２は例えば第１階層に属される。そして、ステップＳ３と同様にして、グループＧ２ｓに含まれる各ネットＮａ１，Ｎａ２の配線長の見積値ｈを設定する。ここでは、各ネットＮａ１，Ｎａ２にはそれぞれ、第１階層に属するので見積値ｈ１（≒１．４×Ｓ1/2）が設定される。
【００４０】
次にステップＳ９で、選択されたグループＧ２ｓに含まれる各ネットＮａ１，Ｎａ２に対しては、ステップＳ８で再設定された配線長の見積値ｈを使用し、グループＧ２ｓに含まれない各ネットＮに対しては既に設定されている配線長の見積値ｈを使用して、ステップＳ４と同様にして、ネットＮの接続状態の変更後のネットリストＮＲの配線難易度Ｐを計算する。
【００４１】
以上の様に説明したネットリストの配線難易度計算方法によれば、ネットリストＮＲの一部のネットＮの接続状態が変更された場合に、その変更部分を一括して含むグループＧのうちの最も低い階層のグループ（ここではＧ２ｓ）だけにステップＳ１−Ｓ３を実施し、そのグループＧ２ｓに含まれるネットに対してだけ配線長の見積値ｈを再設定し、そのグループＧ２ｓに含まれないネットＮに対しては既に設定されている配線長の見積値ｈを使用するので、変更後のネットリストＮＲ全体にステップＳ１−Ｓ３を実施せずに済み、より速い処理速度で配線難易度を計算できる。
【００４２】
実施の形態４．
実施の形態１−３では、ネットリストＮＲとしてセル単位のネットリストを用いたが、加算器やセレクタ等の機能ブロック単位のネットリストや、ＬＳＩチップ単位のネットリストを用いても構わない。即ちセルは機能ブロックやＬＳＩチップであってもよい。そうした場合も同様の効果を得る。
【産業上の利用可能性】
【００４３】
本発明は、主として大規模のデジタルＬＳＩ全般のＲＴＬ設計、高位合成、論理設計、論理合成等に適用可能である。設計（合成）の中間結果であるネットリストに対して本発明を適用して配線難易度を計算し、配線難易度が高い場合には設計（合成）をやり直して配線難易度の低いネットリストを得ることが可能である。
【図面の簡単な説明】
【００４４】
【図１】実施の形態１に係るネットリストの配線難易度計算方法のフローチャートである。
【図２】実施の形態１における階層的クラスタリングの一例を示した図である。
【図３】実施の形態１における第１階層の各グループＧ１および第１階層に属するネットＮ１を抽出した図（即ち第１階層ネットリストを示した図）である。
【図４】実施の形態１における第２階層の各グループＧ２および第２階層に属するネットＮ２を抽出した図（即ち第２階層ネットリストを示した図）である。
【図５】実施の形態１における第３階層の各グループＧ３および第３階層に属するネットＮ３を抽出した図（即ち第３階層ネットリストを示した図）である。
【図６】ネットリストの一例を示した図である。
【図７】図６のネットリストとセル数、ネット数、ファンアウト数が同じである他のネットリストの一例を示した図である。
【図８】実施の形態３に係るネットリストの配線難易度計算方法のフローチャートである。
【図９】実施の形態３におけるネットの接続状態の変更前のネットリストの一例を示した図である。
【図１０】図９のネットリストの一部のネットＮｂ１，Ｎｂ２，Ｎｂ３の接続状態が削除された状態を示した図である。
【図１１】図１０のネットリストに新たなネットＮａ１，Ｎａ２が接続された状態を示した図である。
【図１２】実施の形態１に係るネットリストの配線難易度計算方法を用いた場合のＬＳＩの設計フロー全体の概略の流れを示した図である。
【符号の説明】
【００４５】
ＮＲ，ＮＲａ，ＮＲｂ  ネットリスト、Ｎ  ネット、Ｎｂ１，Ｎｂ２  変更前のネット、Ｎａ１，Ｎａ２，Ｎａ３  変更後のネット、Ｃ，Ｃ１，Ｃ２，Ｃ３，Ｃ４  セル、Ｇ  グループ、Ｇ１  第１階層のグループ、Ｇ２  第２階層のグループ、Ｇ３  第３階層のグループ、Ｇ２ｓ  第２階層の選択されたグループ、Ｇ１ａ，Ｇ１ｂ  第１階層の新たに設定されたグループ。
【図１】
2009020786.tif 000003
【図２】
2009020786.tif 000004
【図３】
2009020786.tif 000005
【図４】
2009020786.tif 000006
【図５】
2009020786.tif 000007
【図６】
2009020786.tif 000008
【図７】
2009020786.tif 000009
【図８】
2009020786.tif 000010
【図９】
2009020786.tif 000011
【図１０】
2009020786.tif 000012
【図１１】
2009020786.tif 000013
【図１２】
2009020786.tif 000014