(57)【要約】【課題】適切な配置配線必要面積を求めて自動配置配線を行う。【解決手段】ネットリストＮ１に基づいて自動配置配線を行う際に、セル及び配線が占有する面積を格子数として求める。面積から格子数への変換は格子使用率計算用テーブルＴ１に基づいて行われる。セルが使用する格子数及び配線が使用する格子数の合計を、格子使用率の上限値及び単位面積当たりの格子数で除して配置配線領域に必要な面積を求める。予想した面積に配置配線が不可能であったという事態を回避することができ、かつ不必要に広く配置配線領域を確保する必要もなく、従って徒に集積度を低下させることもない。【選択図】図１
2005100459.tif 000002
【特許請求の範囲】
【請求項１】
集積回路を構成するセル及び前記セルの間を接続する配線を配置配線領域において配置する自動配置配線装置であって、
前記配置配線領域は格子を単位として捉えられ、
前記セルの一覧及び前記配線の接続情報がネットリストに含まれ、
前記セルが前記格子を占有する数を示すセル格子使用数と、前記配線の単位長あたりの格子数Ｌｇと、単位面積あたりの格子数Ｓｇと、前記配置配線領域の占有する格子数に対して前記セル及び前記配線が占有する格子数の割合を示す格子使用率ＧＵの上限値ＧＵlimitとがテーブルに格納され、
前記配置配線領域に必要な面積Ｓ0を出力する配置配線必要面積予測手段と、
前記セルの一覧及び前記セル格子使用数から、前記セルが使用する格子数の合計ＧＰを出力するセル使用格子数算出手段と、
前記配線の接続情報及び前記格子数Ｌｇから、前記配線が使用する格子数の合計ＧＲを出力するセル間配線使用格子数算出手段と、
前記配置配線領域における格子使用率ＧＵとして（ＧＰ＋ＧＲ）／Ｓ0／Ｓｇを出力する格子使用率算出手段と、
前記格子使用率ＧＵを前記上限値ＧＵlimitと比較し、前記面積Ｓ0の適否を判定する処理継続判定手段と
を備え、
適と判定された前記面積Ｓ0を有する前記配置配線領域において前記配線を配置する自動配置配線装置。
【請求項２】
前記ネットリストに基づいて前記セルの自動配置を行い、前記セルの前記自動配置によって得られた前記セルの配置に基づいて前記配線の長さＬを設定する自動配置手段
を更に備え、
前記セル間配線使用格子数算出手段は、前記配線の接続情報に代わる前記長さＬ及び前記格子数Ｌｇから、前記配線が使用する格子数の合計ＧＲを求める、請求項１記載の自動配置配線装置。
【請求項３】
前記セルの前記自動配置によって得られた前記セルの配置に基づいて前記配線の自動配線を行い、前記配線の長さＬを設定する自動配線手段
を更に備える、請求項２記載の自動配置配線装置。
【請求項４】
集積回路を構成するセル及び前記セルの間を接続する配線を配置配線領域において配置する自動配置配線装置であって、
前記配置配線領域は格子を単位として捉えられ、
前記セルの一覧がネットリストに含まれ、
前記セルが前記格子を占有する数を示すセル格子使用数と、前記配線の単位長あたりの格子数Ｌｇと、単位面積あたりの格子数Ｓｇと、前記配置配線領域の占有する格子数に対して前記セル及び前記配線が占有する格子数の割合を示す格子使用率ＧＵの上限値ＧＵlimitとがテーブルに格納され、
前記配置配線領域に必要な面積Ｓ0が設定され、
前記セルの一覧に基づいた前記セルの自動配置と、前記配置配線領域の分割とを行う自動配置手段と、
分割された前記配置配線領域の各々において、前記セルの一覧及び前記セル格子使用数から、前記セルが使用する格子数の合計ＧＰを出力するセル使用格子数算出手段と、
分割された前記配置配線領域の各々において、前記セルの前記自動配置によって得られた前記配線の長さＬ及び前記格子数Ｌｇから、前記配線が使用する格子数の合計ＧＲを出力するセル間配線使用格子数算出手段と、
分割された前記配置配線領域の各々において、前記分割された配置配線領域における格子使用率ＧＵとして（ＧＰ＋ＧＲ）／Ｓ0／Ｓｇを出力する格子使用率算出手段と、
分割された前記配置配線領域の各々において、前記格子使用率ＧＵを前記上限値ＧＵlimitと比較し、前記分割された領域における前記セルの配置の適否を判定する配置配線可能性判定手段と
を備え、
前記セルの配置が適と判定された場合に前記面積Ｓ0を有する前記配置配線領域において前記配線を配置する自動配置配線装置。
【請求項５】
集積回路を構成するセル及び前記セルの間を接続する配線を配置配線領域において配置する自動配置配線装置であって、
前記配置配線領域は格子を単位として捉えられ、
前記セルの一覧がネットリストに含まれ、
前記セルが前記格子を占有する数を示すセル格子使用数と、前記配線の単位長あたりの格子数Ｌｇと、単位面積あたりの格子数Ｓｇと、前記配置配線領域の占有する格子数に対して前記セル及び前記配線が占有する格子数の割合を示す格子使用率ＧＵの上限値ＧＵlimitとがテーブルに格納され、
前記配置配線領域に必要な面積Ｓ0が設定され、
前記面積Ｓ0を有する前記配置配線領域において前記セルの一覧に基づいて前記セルの自動配置が行われ、
前記面積Ｓ0を有する前記配置配線領域において前記セルの前記自動配置に基づいて自動配線を行い、配置配線領域を分割する自動配線手段と、
分割された配置配線領域の各々において、前記セルの一覧及び前記セル格子使用数から、前記セルが使用する格子数の合計ＧＰを出力するセル使用格子数算出手段と、
分割された配置配線領域の各々において、前記自動配線によって得られた前記配線の長さＬ及び前記格子数Ｌｇから、前記配線が使用する格子数の合計ＧＲを出力するセル間配線使用格子数算出手段と、
分割された前記配置配線領域の各々において、前記分割された配置配線領域における格子使用率ＧＵとして（ＧＰ＋ＧＲ）／Ｓ0／Ｓｇを出力する格子使用率算出手段と、
分割された前記配置配線領域の各々において、前記格子使用率ＧＵを前記上限値ＧＵlimit と比較し、前記分割された領域における前記セルの配置の適否を判定する配置配線可能性判定手段と
を備える自動配置配線装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、半導体集積回路を設計するための自動配置配線装置に関するものである。
【背景技術】
【０００２】
図１３は従来の自動配置配線装置の動作を示すフローチャートである。まずステップＸ１において論理回路から抽出したネットリスト（セル及びセル間の接続情報）Ｎ１を元に、配置配線に必要な領域（配置配線領域）の面積（配置配線必要面積）を予測する。配置配線に必要な面積は過去の結果から統計データＸ４が求められており、これに基づいて配置配線に必要な面積の予測が行われる。
【０００３】
そしてこのように必要な面積が予測されてから、ステップＸ２においてセルの自動配置、ステップＸ３においてセル間配線の自動配線が、当該面積を有する配置配線領域で行われる。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
以上のように、従来の自動配置配線装置は、配置配線に必要な面積の予測に、離散的に、かつ経験的に作成した過去の統計データを使用するため、高精度な面積予測を行うことが困難である。
【０００５】
また、セルの自動配置及びセル間の自動配線を、セル及びセル間の接続情報であるネットリストＮ１にのみ基づいて行っているため、局所的にセル配置、セル間配線が混雑してしまうことがあった。
【０００６】
また、ステップＸ３の自動配線を実行した後でないと、ステップＸ１で予想した面積に自動配置配線が可能であるか否かの判断ができないため、予想した面積に配置配線が不可能であった場合には再度自動配置配線処理を行わなければならないなど、いわゆる手戻りが大きくなるという問題があった。
【０００７】
手戻りを大きくしないためにはステップＸ１で予想する面積を大きくすれば良いが、これを徒に大きくすることは集積度を低下させることとなる。
【０００８】
この発明は上記問題を解決するためになされたもので、適切な配置配線必要面積を求めて自動配置配線を行う技術を提供することを目的としている。
【課題を解決するための手段】
【０００９】
この発明のうち請求項１にかかるものは、集積回路を構成するセル及び前記セルの間を接続する配線を配置配線領域において配置する自動配置配線装置である。ここで前記配置配線領域は格子を単位として捉えられる。そして前記セルの一覧及び前記配線の接続情報がネットリストに含まれる。また前記セルが前記格子を占有する数を示すセル格子使用数と、前記配線の単位長あたりの格子数Ｌｇと、単位面積あたりの格子数Ｓｇと、前記配置配線領域の占有する格子数に対して前記セル及び前記配線が占有する格子数の割合を示す格子使用率ＧＵの上限値ＧＵlimitとがテーブルに格納される。そして前記配置配線領域に必要な面積Ｓ0を出力する配置配線必要面積予測手段と、前記セルの一覧及び前記セル格子使用数から、前記セルが使用する格子数の合計ＧＰを出力するセル使用格子数算出手段と、前記配線の接続情報及び前記格子数Ｌｇから、前記配線が使用する格子数の合計ＧＲを出力するセル間配線使用格子数算出手段と、前記配置配線領域における格子使用率ＧＵとして（ＧＰ＋ＧＲ）／Ｓ0／Ｓｇを出力する格子使用率算出手段と、前記格子使用率ＧＵを前記上限値ＧＵlimitと比較し、前記面積Ｓ0の適否を判定する処理継続判定手段とを備え、適と判定された前記面積Ｓ0を有する前記配置配線領域において前記配線を配置する。
【００１０】
この発明のうち請求項２にかかるものは請求項１記載の自動配置配線装置であって、前記ネットリストに基づいて前記セルの自動配置を行い、前記セルの前記自動配置によって得られた前記セルの配置に基づいて前記配線の長さＬを設定する自動配置手段を更に備える。そして、前記セル間配線使用格子数算出手段は、前記配線の接続情報に代わる前記長さＬ及び前記格子数Ｌｇから、前記配線が使用する格子数の合計ＧＲを求める。
【００１１】
この発明のうち請求項３にかかるものは請求項２記載の自動配置配線装置であって、前記セルの前記自動配置によって得られた前記セルの配置に基づいて前記配線の自動配線を行い、前記配線の長さＬを設定する自動配線手段を更に備える。
【００１２】
この発明のうち請求項４にかかるものは、集積回路を構成するセル及び前記セルの間を接続する配線を配置配線領域において配置する自動配置配線装置である。ここで前記配置配線領域は格子を単位として捉えられる。また前記セルの一覧がネットリストに含まれる。また前記セルが前記格子を占有する数を示すセル格子使用数と、前記配線の単位長あたりの格子数Ｌｇと、単位面積あたりの格子数Ｓｇと、前記配置配線領域の占有する格子数に対して前記セル及び前記配線が占有する格子数の割合を示す格子使用率ＧＵの上限値ＧＵlimitとがテーブルに格納される。そして前記配置配線領域に必要な面積Ｓ0が設定される。そして前記セルの一覧に基づいた前記セルの自動配置と、前記配置配線領域の分割とを行う自動配置手段と、分割された前記配置配線領域の各々において、前記セルの一覧及び前記セル格子使用数から、前記セルが使用する格子数の合計ＧＰを出力するセル使用格子数算出手段と、分割された前記配置配線領域の各々において、前記セルの前記自動配置によって得られた前記配線の長さＬ及び前記格子数Ｌｇから、前記配線が使用する格子数の合計ＧＲを出力するセル間配線使用格子数算出手段と、分割された前記配置配線領域の各々において、前記分割された配置配線領域における格子使用率ＧＵとして（ＧＰ＋ＧＲ）／Ｓ0／Ｓｇを出力する格子使用率算出手段と、分割された前記配置配線領域の各々において、前記格子使用率ＧＵを前記上限値ＧＵlimitと比較し、前記分割された領域における前記セルの配置の適否を判定する配置配線可能性判定手段とを備え、前記セルの配置が適と判定された場合に前記面積Ｓ0を有する前記配置配線領域において前記配線を配置する。
【００１３】
この発明のうち請求項５にかかるものは、集積回路を構成するセル及び前記セルの間を接続する配線を配置配線領域において配置する自動配置配線装置である。ここで前記配置配線領域は格子を単位として捉えられる。また前記セルの一覧がネットリストに含まれる。また前記セルが前記格子を占有する数を示すセル格子使用数と、前記配線の単位長あたりの格子数Ｌｇと、単位面積あたりの格子数Ｓｇと、前記配置配線領域の占有する格子数に対して前記セル及び前記配線が占有する格子数の割合を示す格子使用率ＧＵの上限値ＧＵlimitとがテーブルに格納される。また前記面積Ｓ0を有する前記配置配線領域において前記セルの一覧に基づいて前記セルの自動配置が行われる。前記面積Ｓ0を有する前記配置配線領域において前記セルの前記自動配置に基づいて自動配線を行い、配置配線領域を分割する自動配線手段と、分割された配置配線領域の各々において、前記セルの一覧及び前記セル格子使用数から、前記セルが使用する格子数の合計ＧＰを出力するセル使用格子数算出手段と、分割された配置配線領域の各々において、前記自動配線によって得られた前記配線の長さＬ及び前記格子数Ｌｇから、前記配線が使用する格子数の合計ＧＲを出力するセル間配線使用格子数算出手段と、分割された前記配置配線領域の各々において、前記分割された配置配線領域における格子使用率ＧＵとして（ＧＰ＋ＧＲ）／Ｓ0／Ｓｇを出力する格子使用率算出手段と、分割された前記配置配線領域の各々において、前記格子使用率ＧＵを前記上限値ＧＵlimitと比較し、前記分割された領域における前記セルの配置の適否を判定する配置配線可能性判定手段とを備える。
【発明の効果】
【００１４】
この発明のうち請求項１にかかる自動配置配線装置においては、予め設定された配置配線必要面積の適否が、自動配置前に判定される。
【００１５】
この発明のうち請求項２にかかる自動配置配線装置においては、予め設定された配置配線必要面積の適否が、自動配線前に判定される。
【００１６】
この発明のうち請求項３にかかる自動配置配線装置においては、予め設定された配置配線必要面積の適否が判定される。
【００１７】
この発明のうち請求項４及び請求項５にかかる自動配置配線装置においては、配置配線領域が分割され、分割された配置配線領域の各々における格子使用率ＧＵが上限値ＧＵlimitと比較される。
【００１８】
この発明のうち請求項１及び請求項２にかかる自動配置配線装置によれば、適切な配置配線必要面積を設定する手戻りが軽減される。
【００１９】
この発明のうち請求項３にかかる自動配置配線装置によれば、配置配線領域に配置配線が不可能であるという事態を回避することができる。
【００２０】
この発明のうち請求項４にかかる自動配置配線装置によれば、局所的な混雑を招来することなく平均してセルの配置を行い、なおかつ適切な配置配線領域面積を求めることができる。
【００２１】
この発明のうち請求項５にかかる自動配置配線装置によれば、局所的な混雑を招来することなく平均して配線の配置を行い、なおかつ適切な配置配線領域面積を求めることができる。
【発明を実施するための最良の形態】
【００２２】
実施の形態１：
図１は、この発明の実施の形態１を示す構成図である。この発明にかかる自動配置配線装置１００は、ネットリストＮ１及び格子使用率計算用テーブルＴ１を入力し、セルのレイアウト結果Ｌ１を出力する。格子使用率計算用テーブルＴ１は、単位面積あたりの格子数Ｓｇ、単位配線長あたりの格子数Ｌｇ、格子使用率の上限値ＧＵlimit 、回路を構成する際に用いる個々のセルが使用する格子数ｇｐ（ｉ）を格納するテーブルである。
【００２３】
図２は実施の形態１の動作を示すフローチャートである。ステップＸ２０は従来のステップＸ１に該当するステップであり、その中にステップＸ１１ａ，Ｘ１２１ａ，Ｘ１５ａが含まれている。
【００２４】
まずステップＸ１１ａでセルが使用する格子数が算出される。ネットリストが与えられた時、ネットリストＮ１に記述されているセルの一覧を元に、テーブルＴ１に記述されたセルが使用する格子数ｇｐ（ｉ）を参照しながら、回路を構成するセルが使用する格子数の合計ＧＰが求められる。
【００２５】
表１に、格子使用率計算用テーブルＴ１の格納する内容を例示する。
【００２６】
【表１】
2005100459.tif 000003
【００２７】
図３は表１の内容を説明する平面図である。格子は破線で表され、１．０μｍ×１．０μｍの大きさを単位としている。従って表１にいうように単位面積当たりの格子数は１．０であり、単位配線長あたりの格子数も１．０である。セルＣ１，Ｃ２の使用する格子は○で示され、それぞれ２０個，２５個使用されている。格子使用率の上限値とは、配置配線必要面積が有する格子の数に対し、どの程度迄の格子数をセル及び配線に用いることができるかを示す。
【００２８】
例えば図３の例に即してステップＸ１１ａを説明すると、セルＣ１，Ｃ２のそれぞれが使用する格子数がそれぞれ
ｇｐ（１）＝２０，ｇｐ（２）＝２５
であるから、セルが使用する格子数の合計ＧＰは、
ＧＰ＝Σｇｐ（ｉ）＝ｇｐ（１）＋ｇｐ（２）＝２０＋２５＝４５（格子）
と求められる。
【００２９】
次いでステップＸ１２ａにおいて、セル間配線が使用する格子数が算出される。ネットリストＮ１に記述されているセル間の接続情報を基に、テーブルＴ１に記述された単位配線長あたりの格子数Ｌｇを参照しながら、回路を構成するセル間の配線が使用する格子数の合計ＧＲ１を算出する。ネットリストＮ１には、セル間接続数毎に、信号ｊに対する配線長Ｌ１（ｊ）が格納されている。よってセル間の配線が使用する格子数の合計ＧＲ１は、
ＧＲ１＝Ｌｇ×ΣＬ１（ｊ）（格子）
と求められる。
【００３０】
次ぎにステップＸ１５ａにおいて、格子使用率ＧＵが上限値ＧＵlimit になるように、配置配線必要面積Ｓ0 を以下のように算出する。
【００３１】
Ｓ0 ＝（ＧＰ＋ＧＲ１）／ＧＵlimit ／Ｓｇ
ここで上限値ＧＵlimit 及び単位面積あたりの格子数ＳｇはテーブルＴ１から与えられる。
【００３２】
このようにして求められた配置配線必要面積Ｓ0を有する配置配線領域において自動配置配線を行えば、格子使用率ＧＵが当然上限値ＧＵlimitとなるので、予想した面積に配置配線が不可能であったという事態を回避することができ、かつ不必要に広く配置配線領域を確保する必要もなく、従って徒に集積度を低下させることもない。
【００３３】
ステップＸ２０の後は接続子Ｊ１に進むが、接続子Ｊ１から従来のステップＸ２に進むことができる。
【００３４】
上記の説明においてはステップＸ１１ａ，Ｘ１２ａ，Ｘ１５ａを全て処理工程として捉えて説明したが、これらをそれぞれ処理手段と捉えることも本実施の形態を逸脱するものではない。即ち、ネットリストＮ１からセル一覧を、テーブルＴ１からｇｐ（ｉ）を、それぞれ入力してＧＰを出力するセル使用格子数算出手段と、ネットリストＮ１からセル間接続情報を、テーブルＴ１からＬｇを、それぞれ入力してＧＲ１を出力するセル間配線使用格子数算出手段と、テーブルＴ１からＳｇ及びＧＵlimit を、セル使用格子数算出手段からＧＰを、セル間配線使用格子数算出手段からＧＲ１を、それぞれ入力して配置配線必要面積Ｓ0 を出力する配置配線必要面積算出手段とを備える自動配置配線装置は本実施の形態において開示されているものである。
【００３５】
実施の形態２：
図４は、この発明の実施の形態２の動作を示すフローチャートである。ステップＸ１１ｂにおいて、実施の形態１のステップＸ１１ａと同様にしてセル使用格子数ＧＰを求める。その一方、従来と同様にステップＸ２においてセルの自動配置が行われる。この結果、セル間の配線長Ｌ２（ｊ）が信号ｊ毎に求められる。このような自動配置後であって、自動配線前の配線長はマンハッタン距離ＭＮ、あるいはトランクスタイナ木ＴＳを用いて算出することができる。セル配置が行われた後でこれらを求めることもできるし、セル概略配置の段階で求めても良い。
【００３６】
このようにして求められた配線長Ｌ２（ｊ）を用いて、セル間の配線が使用する格子数の合計ＧＲ２は、実施の形態１のステップＸ１２ａと同様にしてステップＸ１２ｂにおいて
ＧＲ２＝Ｌｇ×ΣＬ２（ｊ）（格子）
と求められる。その後、ステップＸ１５ｂにおいては実施の形態１と同様にして、格子使用率ＧＵが上限値ＧＵlimit になるように、配置配線必要面積Ｓ0 を以下のように算出する。
【００３７】
Ｓ0 ＝（ＧＰ＋ＧＲ２）／ＧＵlimit ／Ｓｇ
接続子Ｊ２の前には従来のステップＸ１を実行することができる。その場合には配置配線必要面積Ｓ0 が更新されることになる。或いは従来のステップＸ１を実行する事なく、接続子Ｊ２から直ちに自動配置配線の処理が行われることとしても良い。また、接続子Ｊ３の後には従来のステップＸ３へ進むことができる。
【００３８】
表２はこの発明で得られた配置配線必要面積と、従来の手法によって予測された配置配線面積との比較結果を例示する比較表である。ここではＳＯＧ（全面素子形成型ゲートアレイ）の８種類の回路について比較している。
【００３９】
【表２】
2005100459.tif 000004
【００４０】
表２において、Ｓａ及びＳｂはそれぞれＧＵlimit を０．５とした場合の実施の形態１及び実施の形態２において得られる配置配線必要面積Ｓ0 を示している。また、Ｓｃは従来手法の一例として、過去の統計データから配置配線領域面積に対するセル総面積の比率αを得て、以下の式を用いて算出した値である。
【００４１】
Ｓｃ＝セル総面積／α
但し、回路Ａ、Ｂ、Ｃ、Ｄの配置配線はセル間配線に第１層及び第２層配線を用いており、回路Ｅ、Ｆ、Ｇ、Ｈの配置配線はセル間配線に第１層、第２層及び第３層配線を用いるため、αの値は前者において０．４を、後者において０．６を採用した。
【００４２】
表２において、Ｓは配置配線限界時における面積の実測値である。従来手法による配置配線面積Ｓｃは、実測値−７５．００％〜＋６３．３３％の範囲（誤差幅１３８．３３％）で大きな誤差が発生するのに比し、この発明によると実施の形態１による場合で一３５．１４％〜＋３２．８６％（誤差幅６８．００％）、実施の形態２による場合で−２８．０７％〜＋１５．２３％（誤差幅４３．３０％）の誤差で予測可能である。以上の結果から、この発明を使用することにより、従来手法よりも、２倍から３倍以上、高精度に配置配線面積を予測することが可能であることが判る。
【００４３】
上記の説明においてはステップＸ２，Ｘ１１ｂ，Ｘ１２ｂ，Ｘ１５ｂを全て処理工程として捉えて説明したが、これらをそれぞれ処理手段と捉えることも本実施の形態を逸脱するものではない。即ち、ネットリストＮ１に基づいて自動配置を行い、配線長Ｌ２（ｊ）をマンハッタン距離ＭＮ、あるいはトランクスタイナ木ＴＳを用いて算出する自動配置手段と、ネットリストＮ１からセル一覧を、テーブルＴ１からｇｐ（ｉ）を、それぞれ入力してＧＰを出力するセル使用格子数算出手段と、自動配置手段からＬ２（ｊ）を、セル使用格子数算出手段からＧＰを、テーブルＴ１からＬｇを、それぞれ入力してＧＲ２を出力するセル間配線使用格子数算出手段と、テーブルＴ１からＳｇ及びＧＵlimit を、セル使用格子数算出手段からＧＰを、セル間配線使用格子数算出手段からＧＲ２を、それぞれ入力して配置配線必要面積Ｓ0 を出力する配置配線必要面積算出手段とを備える自動配置配線装置は本実施の形態において開示されているものである。
【００４４】
実施の形態３：
図５は、この発明の実施の形態３の動作を示すフローチャートである。接続子Ｊ４の前には従来のステップＸ１，Ｘ２を実行し、セルの自動配置までを実行しておくことができる。その場合には配置配線必要面積Ｓ0 が更新されることになる。或いは従来のステップＸ１を実行する事なく、ステップＸ２のみを実行していても良い。
【００４５】
ステップＸ１１ｃにおいて、実施の形態１のステップＸ１１ａと同様にしてセル使用格子数ＧＰを求める。その一方、従来と同様にステップＸ３においてセルの自動配線が行われる。
【００４６】
ステップＸ３において全配線長Ｌが求められる。全配線長Ｌは、セル間配線が行われた後でこれらを求めることもできるし、セル間概略配線の段階で求めても良い。図３の例に即すると、セル間配線Ｗ１，Ｗ２はそれぞれ長さが１１．０μｍ，１０．０μｍであって
Ｌ＝１１．０＋１０．０＝２１．０（μｍ）
となる。
【００４７】
その後セル間の配線が使用する格子数の合計ＧＲ３は、実施の形態１のステップＸ１２ａと同様にしてステップＸ１２ｃにおいて
ＧＲ３＝Ｌ×Ｌｇ＝２１．０×１．０＝２１（格子）
と求められる。その後、ステップＸ１５ｃにおいては実施の形態１と同様にして、格子使用率ＧＵが上限値ＧＵlimit になるように、配置配線必要面積Ｓ0 を以下のように算出する。
【００４８】
Ｓ0 ＝（ＧＰ＋ＧＲ３）／ＧＵlimit ／Ｓｇ
接続子Ｊ５の後は自動配置配線処理を停止するステップを設けることができる。
【００４９】
上記のようにして配置配線必要面積Ｓ0 を求めても第１及び実施の形態２と同様の効果が得られることはいうまでもない。
【００５０】
上記の説明においてはステップＸ３，Ｘ１１ｃ，Ｘ１２ｃ，Ｘ１５ｃを全て処理工程として捉えて説明したが、これらをそれぞれ処理手段と捉えることも本実施の形態を逸脱するものではない。即ち、セルの自動配置の結果に基づいて自動配線を行い、配線長Ｌを算出する自動配線手段と、ネットリストＮ１からセル一覧を、テーブルＴ１からｇｐ（ｉ）を、それぞれ入力してＧＰを出力するセル使用格子数算出手段と、自動配線手段からＬを、セル使用格子数算出手段からＧＰを、テーブルＴ１からＬｇを、それぞれ入力してＧＲ３を出力するセル間配線使用格子数算出手段と、テーブルＴ１からＳｇ及びＧＵlimit を、セル使用格子数算出手段からＧＰを、セル間配線使用格子数算出手段からＧＲ３を、それぞれ入力して配置配線必要面積Ｓ0 を出力する配置配線必要面積算出手段とを備える自動配置配線装置は本実施の形態において開示されているものである。
【００５１】
実施の形態４：
図６は、この発明の実施の形態４の動作を示すフローチャートである。従来の技術と同様に、ステップＸ１において配置配線必要面積Ｓ0 を、ネットリストＮ１におけるセル一覧及びセル間接続情報、並びに統計データＸ４から求める。
【００５２】
その後、ステップＸ１１ａ，Ｘ１２ａにおいて、実施の形態１と同様にしてセルが使用する格子数の合計ＧＰ及びセル間の配線が使用する格子数の合計ＧＲ１を求める。そしてステップＸ１３ａにおいては以下の式により、格子使用率ＧＵが計算される。
【００５３】
ＧＵ＝（ＧＰ＋ＧＲ１）／ＧＭ，ＧＭ＝Ｓ0 ×Ｓｇ
ここで単位面積あたりの格子数ＳｇはテーブルＴ１から与えられる。図３の例に即して説明する。図３に示された格子の全てが配置配線領域であるとすると、  ＧＭ＝（１２．０×１２．０）×１．０＝１４４（格子）
ＧＵ＝（４５＋２１）／１４４＝０．４５８
と求められる。
【００５４】
格子使用率の上限値ＧＵlimit は、配置配線処理の性能に応じて一定に定められる。そしてステップＸ１８ａにおいては、上式で求められた格子使用率ＧＵと、上限値ＧＵlimit とを比較することにより、回路の配置配線が可能であるか否かを判定する。ＧＵlimit を０．５とすると、上記の例ではＧＵ＜ＧＵlimit であるため、配置配線が可能であると判断される。そして接続子Ｊ６へと処理が進む。この後は従来のステップＸ２、Ｘ３を実行することができる。
【００５５】
もしもＧＵ＞ＧＵlimit であればステップＸ１に戻って配置配線必要面積Ｓ0 を再度設定する。このように、セルの自動配置を行う以前に配置配線必要面積を正しく求めることができるので、従来のようにいわゆる手戻りが大きくなるという問題が回避されるのみならず、不必要に広く配置配線領域を確保する必要もなく、従って徒に集積度を低下させることもない。
【００５６】
上記の説明においてはステップＸ１，Ｘ１１ａ，Ｘ１２ａ，Ｘ１３ａ，Ｘ１８ａを全て処理工程として捉えて説明したが、これらをそれぞれ処理手段と捉えることも本実施の形態を逸脱するものではない。即ち、ネットリストＮ１からセル一覧及びセル間接続情報を、統計データＸ４から過去のデータを、それぞれ入力して配置配線必要面積Ｓ0 を出力する配置配線必要面積予測手段と、ネットリストＮ１からセル一覧を、テーブルＴ１からｇｐ（ｉ）を、それぞれ入力してＧＰを出力するセル使用格子数算出手段と、ネットリストＮ１からセル間接続情報を、テーブルＴ１からＬｇを、それぞれ入力してＧＲ１を出力するセル間配線使用格子数算出手段と、テーブルＴ１からＳｇを、セル使用格子数算出手段からＧＰを、セル間配線使用格子数算出手段からＧＲ１を、それぞれ入力してＧＵを出力する格子使用率算出手段と、格子使用率算出手段からＧＵを、テーブルＴ１から上限値ＧＵlimit を、それぞれ入力して配置配線必要面積Ｓ0 が適切であるか否かを判定する処理継続判定手段とを備える自動配置配線装置は本実施の形態において開示されているものである。
【００５７】
実施の形態５：
図７は、この発明の実施の形態５の動作を示すフローチャートである。接続子Ｊ７以前において既に配置配線必要面積Ｓ0 が求められている。例えば従来のステップＸ１を実行しておくことができる。
【００５８】
ステップＸ２，Ｘ１１ｂ，Ｘ１２ｂの実行については実施の形態２と同様である。その後実施の形態４と同様にして、ステップＸ１３ｂにおいて
ＧＵ＝（ＧＰ＋ＧＲ２）／ＧＭ
から格子使用率ＧＵを求め、ステップＸ１８ｂにおいてＧＵと上限値ＧＵlimit とを比較することにより、回路の配置配線が可能であるか否かを判定する。
【００５９】
もしもＧＵ＞ＧＵlimit であればステップＸ１に戻るなどして、配置配線必要面積Ｓ0 を再度設定する。別途再設定のための工程を設けても良い。ＧＵ＜ＧＵlimit であれば接続子Ｊ８に進む。接続子Ｊ８の後は例えば従来のステップＸ３を実行することができる。
【００６０】
このように、セルの自動配線を行う以前に配置配線必要面積を正しく求めることができるので、従来のようにいわゆる手戻りが大きくなるという問題が回避されるのみならず、不必要に広く配置配線領域を確保する必要もなく、従って徒に集積度を低下させることもない。
【００６１】
上記の説明においてはステップＸ２，Ｘ１１ｂ，Ｘ１２ｂ，Ｘ１３ｂ，Ｘ１８ｂを全て処理工程として捉えて説明したが、これらをそれぞれ処理手段と捉えることも本実施の形態を逸脱するものではない。即ち、配置配線必要面積Ｓ0 を有する配置配線領域においてセルの自動配置を行い、配線長Ｌ２（ｊ）をマンハッタン距離ＭＮ、あるいはトランクスタイナ木ＴＳを用いて算出する自動配置手段と、ネットリストＮ１からセル一覧を、テーブルＴ１からｇｐ（ｉ）を、それぞれ入力してＧＰを出力するセル使用格子数算出手段と、自動配置手段から配線長Ｌ２（ｊ）を、テーブルＴ１からＬｇを、それぞれ入力してＧＲ２を出力するセル間配線使用格子数算出手段と、テーブルＴ１からＳｇを、セル使用格子数算出手段からＧＰを、セル間配線使用格子数算出手段からＧＲ２を、それぞれ入力してＧＵを出力する格子使用率算出手段と、格子使用率算出手段からＧＵを、テーブルＴ１から上限値ＧＵlimit を、それぞれ入力して配置配線必要面積Ｓ0 が適切であるか否かを判定する処理継続判定手段とを備える自動配置配線装置は本実施の形態において開示されているものである。
【００６２】
実施の形態６：
図８は、この発明の実施の形態６の動作を示すフローチャートである。接続子Ｊ９以前において既に配置配線必要面積Ｓ0 が求められている。例えば従来のステップＸ１を実行しておくことができる。そして既にセルの自動配置が行われている。例えば従来のステップＸ２を実行しておくことができる。
【００６３】
ステップＸ３，Ｘ１１ｃ，Ｘ１２ｃの実行については実施の形態３と同様である。その後実施の形態４と同様にして、ステップＸ１３ｃにおいて
ＧＵ＝（ＧＰ＋ＧＲ３）／ＧＭ
から格子使用率ＧＵを求め、ステップＸ１８ｃにおいてＧＵと上限値ＧＵlimitとを比較することにより、回路の配置配線が可能であるか否かを判定する。
【００６４】
もしもＧＵ＞ＧＵlimit であればステップＸ１に戻るなどして、配置配線必要面積Ｓ0 を再度設定する。別途再設定のための工程を設けても良い。ＧＵ＜ＧＵlimit であれば接続子Ｊ１０に進む。接続子Ｊ１０の後は自動配置配線処理を停止するステップを設けることができる。
【００６５】
このようにして配置配線必要面積を正しく求めることができるので、不必要に広く配置配線領域を確保する必要がなく、従って徒に集積度を低下させることもない。
【００６６】
上記の説明においてはステップＸ３，Ｘ１１ｃ，Ｘ１２ｃ，Ｘ１３ｃ，Ｘ１８ｃを全て処理工程として捉えて説明したが、これらをそれぞれ処理手段と捉えることも本実施の形態を逸脱するものではない。即ち、配置配線必要面積Ｓ0 を有する配置配線領域におけるセルの自動配置の結果に基づいて自動配線を行い、配線長Ｌを算出する自動配線手段と、ネットリストＮ１からセル一覧を、テーブルＴ１からｇｐ（ｉ）を、それぞれ入力してＧＰを出力するセル使用格子数算出手段と、自動配線手段から配線長Ｌを、テーブルＴ１からＬｇを、それぞれ入力してＧＲ３を出力するセル間配線使用格子数算出手段と、テーブルＴ１からＳｇを、セル使用格子数算出手段からＧＰを、セル間配線使用格子数算出手段からＧＲ３を、それぞれ入力してＧＵを出力する格子使用率算出手段と、格子使用率算出手段からＧＵを、テーブルＴ１から上限値ＧＵlimit を、それぞれ入力して配置配線必要面積Ｓ0 が適切であるか否かを判定する処理継続判定手段とを備える自動配置配線装置は本実施の形態において開示されているものである。
【００６７】
実施の形態７：
図９は、この発明の実施の形態７の動作を示すフローチャートである。接続子Ｊ１１以前において既に配置配線必要面積Ｓ0 が求められている。例えば従来のステップＸ１を実行しておくことができる。
【００６８】
ステップＸ２１はステップＸ１６を含んでいる。ステップＸ２１においては従来の技術のステップＸ２と同様に自動配置が行われると共に配置配線領域の分割が行われ、ステップＸ１６によって分割された配置配線領域の各々における格子使用率が考慮される。
【００６９】
図１０（ａ）は従来手法によるセルの自動配置結果を例示している。配置配線領域全体としては格子使用率はその上限値を越えていなくても、破線で示された領域でセルが密集しており、望ましくない。そこで、同図（ｂ）のように配置配線領域を分割し、分割された領域のそれぞれにおいて格子使用率がその上限値を越えないように設定する。
【００７０】
具体的には、分割された領域のそれぞれにおいて、ステップＸ１１ｂ乃至ステップＸ１３ｂにおいて実施の形態５と同様に、格子使用率ＧＵが算出される。その後、ステップＸ１４ｂにおいてステップＸ１８ｂと同様に、格子使用率ＧＵと上限値ＧＵlimit とを比較することにより、回路の配置配線が可能であるか否かを判定する。ここで回路の配置配線が可能でなければ、ステップＸ２１において、配置配線領域の分割或いは自動配置がやり直される。
【００７１】
ステップＸ１４ｂにおいて回路の配置配線が可能であると判定された場合には、ステップＸ１６を介してステップＸ２１の処理が終了し、ステップＸ１８ｄへ進む。ステップＸ１８ｄは配置配線領域の全体において格子使用率ＧＵが上限値ＧＵlimit を越えていないかを判断する。もしも越えていれば配置配線必要面積Ｓ0 を再度設定する必要がある。もしも越えていなければ接続子Ｊ１２へ進む。接続子Ｊ１２からは従来のステップＸ３へと進むことができる。
【００７２】
但し、分割された配置配線領域の各々においてＧＵ＜ＧＵlimitであれば、配置配線領域全体においてもＧＵ＜ＧＵlimitとなるので、ステップＸ１８ｄは確認的なものである。
【００７３】
以上の様に実施の形態７によれば局所的な混雑を招来することなく平均してセルを配置し、なおかつ適切な配置配線領域面積を求めることができる。
【００７４】
上記の説明においてはステップＸ２１（Ｘ１６を含む），Ｘ１１ｂ，Ｘ１２ｂ，Ｘ１３ｂ，Ｘ１４ｂ，Ｘ１８ｄを全て処理工程として捉えて説明したが、これらをそれぞれ処理手段と捉えることも本実施の形態を逸脱するものではない。即ち、ネットリストＮ１に基づいて自動配置を行い、配置配線領域を分割する自動配置手段と、分割された配置配線領域毎にＧＰを出力するセル使用格子数算出手段と、分割された配置配線領域毎にＧＲ２を出力するセル間配線使用格子数算出手段と、分割された配置配線領域毎にＧＵを出力する格子使用率算出手段と、分割された配置配線領域の面積が適切であるか否かを判定する配置配線可能性判定手段と、配置配線領域全体として配置配線必要面積Ｓ0 が適切であるか否かを判定する処理継続判定手段とを備える自動配置配線装置は本実施の形態において開示されているものである。
【００７５】
実施の形態８：
図１１は、この発明の実施の形態８の動作を示すフローチャートである。接続子Ｊ１３以前において既に配置配線必要面積Ｓ0 が求められている。例えば従来のステップＸ１を実行しておくことができる。そして既にセルの自動配置が行われている。例えば従来のステップＸ２を実行しておくことができる。
【００７６】
ステップＸ３１はステップＸ１７を含んでいる。ステップＸ３１においては従来の技術のステップＸ３と同様に自動配線が行われると共に配置配線領域の分割が行われ、ステップＸ１７によって分割された配置配線領域の各々における格子使用率が考慮される。
【００７７】
図１２（ａ）は従来手法による自動配置配線結果を例示している。配置配線領域全体としては格子使用率はその上限値を越えていなくても、破線で示された領域で配線が密集しており、望ましくない。そこで、同図（ｂ）のように配置配線領域を分割し、分割された領域のそれぞれにおいて格子使用率がその上限値を越えないように設定する。
【００７８】
具体的には、分割された領域のそれぞれにおいて、ステップＸ１１ｃ乃至ステップＸ１３ｃにおいて実施の形態６と同様に、格子使用率ＧＵが算出される。その後、ステップＸ１４ｃにおいてステップＸ１８ｃと同様に、格子使用率ＧＵと上限値ＧＵlimit とを比較することにより、回路の配置配線が可能であるか否かを判定する。ここで回路の配置配線が可能でなければ、ステップＸ３１において、配置配線領域の分割或いは自動配置がやり直される。
【００７９】
ステップＸ１４ｃにおいて回路の配置配線が可能であると判定された場合には、ステップＸ１７を介してステップＸ３１の処理が終了し、ステップＸ１８ｅへ進む。ステップＸ１８ｅは配置配線領域の全体において格子使用率ＧＵが上限値ＧＵlimit を越えていないかを判断する。もしも越えていれば配置配線必要面積Ｓ0 を再度設定する必要がある。もしも越えていなければ接続子Ｊ１４へ進む。接続子Ｊ１４の後は自動配置配線処理を停止するステップを設けることができる。
【００８０】
但し、分割された配置配線領域の各々においてＧＵ＜ＧＵlimitであれば、配置配線領域全体においてもＧＵ＜ＧＵlimitとなるので、ステップＸ１８ｅは確認的なものである。
【００８１】
以上の様に実施の形態８によれば局所的な混雑を招来することなく平均して配線を行い、なおかつ適切な配置配線領域面積を求めることができる。
【００８２】
上記の説明においてはステップＸ３１（Ｘ１７を含む），Ｘ１１ｃ，Ｘ１２ｃ，Ｘ１３ｃ，Ｘ１４ｃ，Ｘ１８ｅを全て処理工程として捉えて説明したが、これらをそれぞれ処理手段と捉えることも本実施の形態を逸脱するものではない。即ち、セルの自動配置に基づいて自動配線を行い、配置配線領域を分割する自動配線手段と、分割された配置配線領域毎にＧＰを出力するセル使用格子数算出手段と、分割された配置配線領域毎にＧＲ３を出力するセル間配線使用格子数算出手段と、分割された配置配線領域毎にＧＵを出力する格子使用率算出手段と、分割された配置配線領域の面積が適切であるか否かを判定する配置配線可能性判定手段と、配置配線領域全体として配置配線必要面積Ｓ0 が適切であるか否かを判定する処理継続判定手段とを備える自動配置配線装置は本実施の形態において開示されているものである。
【００８３】
変形例：
上記に示した各実施の形態を組み合わせることもできる。例えば接続子Ｊ１と接続子Ｊ７とを接続したフローチャートに従って処理を進めることもできるし、接続子Ｊ１と接続子Ｊ２とを接続したフローチャートに従って処理を進めることもできる。その他、各接続子を互いに接続することにより、セルの自動配置及び自動配線がなされれば、そのような接続によって得られるフローチャートに従った処理も本願の包含するところである。
【００８４】
また、上記実施の形態に則って自動配置配線を行って得られた半導体集積回路は、集積度を低下させることなく、上限値を越えない格子使用率で形成されるので適切な面積を持つ配置配線領域において形成される。
【図面の簡単な説明】
【００８５】
【図１】この発明の実施の形態１を示す構成図である。
【図２】この発明の実施の形態１の動作を示すフローチャートである。
【図３】表１の内容を説明する平面図である。
【図４】この発明の実施の形態２の動作を示すフローチャートである。
【図５】この発明の実施の形態３の動作を示すフローチャートである。
【図６】この発明の実施の形態４の動作を示すフローチャートである。
【図７】この発明の実施の形態５の動作を示すフローチャートである。
【図８】この発明の実施の形態６の動作を示すフローチャートである。
【図９】この発明の実施の形態７の動作を示すフローチャートである。
【図１０】この発明の実施の形態７を説明する平面図である。
【図１１】この発明の実施の形態８の動作を示すフローチャートである。
【図１２】この発明の実施の形態８を説明する平面図である。
【図１３】従来の技術を示すフローチャートである。
【符号の説明】
【００８６】
１００  自動配置配線装置、Ｎ１  ネットリスト、Ｔ１  格子使用率計算用テーブル、Ｃ１，Ｃ２  セル、Ｗ１，Ｗ２  配線。
【図１】
2005100459.tif 000005
【図２】
2005100459.tif 000006
【図３】
2005100459.tif 000007
【図４】
2005100459.tif 000008
【図５】
2005100459.tif 000009
【図６】
2005100459.tif 000010
【図７】
2005100459.tif 000011
【図８】
2005100459.tif 000012
【図９】
2005100459.tif 000013
【図１０】
2005100459.tif 000014
【図１１】
2005100459.tif 000015
【図１２】
2005100459.tif 000016
【図１３】
2005100459.tif 000017