(57)【要約】【課題】配線リソースを有効活用し、収束時間を短縮すること。【解決手段】レイアウト方法は、格子状に区切られた半導体集積回路上の複数の端子組における配線経路を求めるための方法であって、複数の端子組における各端子間を配線可能な領域である複数の矩形領域について、各矩形領域内で端子間を格子単位に配線する際の最短配線経路の数を算出し、最短配線経路の数に基づいて、複数の矩形領域ごとに局所的に配線が集中する度合である配線集中度を算出し、配線集中度に基づき、複数の矩形領域に対応する各端子組における配線の優先度を決定する。【選択図】図３
2012093824.tif 000002
【特許請求の範囲】
【請求項１】
格子状に区切られた半導体集積回路上の複数の端子組における配線経路を求めるためのレイアウト方法であって、
前記複数の端子組における各端子間を配線可能な領域である複数の配線領域について、各配線領域内で前記端子間を格子単位に配線する際の最短配線経路の数を算出し、
前記最短配線経路の数に基づいて、前記複数の配線領域ごとに局所的に配線が集中する度合である配線集中度を算出し、
前記配線集中度に基づき、前記複数の配線領域に対応する各端子組における配線の優先度を決定するレイアウト方法。
【請求項２】
前記複数の配線領域ごとに、対応する端子組を前記最短配線経路の配線長を用いてタイミング検証してタイミング余裕度を算出し、
前記配線集中度及び前記タイミング余裕度に基づき、前記複数の配線領域に対応する各端子組における配線の優先度を決定する
ことを特徴とする請求項１に記載のレイアウト方法。
【請求項３】
各配線領域内の格子ごとに、前記最短配線経路の数のうち当該格子を通過する経路数の比率である格子通過確率を算出し、
前記格子通過確率に基づき、各配線領域内の格子ごとに配線が通過可能か否かを判定し、
前記配線が通過可能と判定された格子数を各配線領域内の行単位及び列単位で集計した場合の最小値を、前記複数の配線領域ごとの前記配線集中度として算出する
ことを特徴とする請求項１又は２に記載のレイアウト方法。
【請求項４】
前記格子通過確率に基づき前記半導体集積回路上の配線禁止領域を特定し、
前記複数の端子組のうち、対応する配線領域内の全ての最短配線経路が前記特定された配線禁止領域を通過する場合、当該配線禁止領域の外周を含めて当該端子組における迂回配線検討領域を特定し、
前記特定された迂回配線検討領域に基づき、前記優先度が低い端子組における迂回配線経路を特定し、
前記特定した迂回配線経路を通過する場合のタイミング検証を実施する
ことを特徴とする請求項３に記載のレイアウト方法。
【請求項５】
前記決定された配線の優先度が低い端子組について、対応する配線領域内の全ての最短配線経路が前記特定された配線禁止領域を通過する場合、当該配線禁止領域の外周を含めて当該端子組における迂回配線検討領域を特定する
ことを特徴とする請求項４に記載のレイアウト方法。
【請求項６】
前記特定した迂回配線経路を通過するようにバッファを挿入し、
前記バッファが挿入された迂回配線経路によりＣＴＳ（Clock Tree Synthesis）及び詳細配線処理を実施させる
ことを特徴とする請求項４又は５に記載のレイアウト方法。
【請求項７】
格子状に区切られた半導体集積回路上の複数の端子組における配線経路を求めるためのレイアウトシステムであって、
前記複数の端子組における各端子間を配線可能な領域である複数の配線領域について、各配線領域内で前記端子間を格子単位に配線する際の最短配線経路の数を算出する最短配線経路数算出手段と、
前記最短配線経路の数に基づいて、前記複数の配線領域ごとに局所的に配線が集中する度合である配線集中度を算出する配線集中度算出手段と、
前記配線集中度に基づき、前記複数の配線領域に対応する各端子組における配線の優先度を決定する優先度決定手段と、
を備えるレイアウトシステム。
【請求項８】
前記複数の配線領域ごとに、対応する端子組を前記最短配線経路の配線長を用いてタイミング検証してタイミング余裕度を算出するタイミング余裕度を算出する算出手段をさらに備え、
前記優先度決定手段は、前記配線集中度及び前記タイミング余裕度に基づき、前記複数の配線領域に対応する各端子組における配線の優先度を決定する
ことを特徴とする請求項７に記載のレイアウトシステム。
【請求項９】
前記配線集中度算出手段は、
各配線領域内の格子ごとに、前記最短配線経路の数のうち当該格子を通過する経路数の比率である格子通過確率を算出し、
前記格子通過確率に基づき、各配線領域内の格子ごとに配線が通過可能か否かを判定し、
前記配線が通過可能と判定された格子数を各配線領域内の行単位及び列単位で集計した場合の最小値を、前記複数の配線領域ごとの前記配線集中度として算出する
ことを特徴とする請求項７又は８に記載のレイアウトシステム。
【請求項１０】
前記格子通過確率に基づき前記半導体集積回路上の配線禁止領域を特定し、
前記複数の端子組のうち、対応する配線領域内の全ての最短配線経路が前記特定された配線禁止領域を通過する場合、当該配線禁止領域の外周を含めて当該端子組における迂回配線検討領域を特定し、
前記特定された迂回配線検討領域に基づき、前記優先度が低い端子組における迂回配線経路を特定する迂回配線経路特定手段と、
前記特定した迂回配線経路を通過する場合のタイミング検証を実施するタイミング検証手段と、
をさらに備えることを特徴とする請求項９に記載のレイアウトシステム。
【請求項１１】
前記迂回配線経路特定手段は、
前記決定された配線の優先度が低い端子組について、対応する配線領域内の全ての最短配線経路が前記特定された配線禁止領域を通過する場合、当該配線禁止領域の外周を含めて当該端子組における迂回配線検討領域を特定する
ことを特徴とする請求項１０に記載のレイアウトシステム。
【請求項１２】
前記迂回配線経路特定手段は、前記特定した迂回配線経路を通過するようにバッファを挿入し、
前記レイアウトシステムは、
前記バッファが挿入された迂回配線経路によりＣＴＳ（Clock Tree Synthesis）及び詳細配線処理を実施させるＣＴＳ詳細配線処理手段
をさらに備えることを特徴とする請求項１０又は１１に記載のレイアウトシステム。
【請求項１３】
格子状に区切られた半導体集積回路上の複数の端子組における配線経路を求めるための処理をコンピュータに実行させるレイアウトプログラムであって、
前記複数の端子組における各端子間を配線可能な領域である複数の配線領域について、各配線領域内で前記端子間を格子単位に配線する際の最短配線経路の数を算出する最短配線経路数算出処理と、
前記最短配線経路の数に基づいて、前記複数の配線領域ごとに局所的に配線が集中する度合である配線集中度を算出する配線集中度算出処理と、
前記配線集中度に基づき、前記複数の配線領域に対応する各端子組における配線の優先度を決定する優先度決定処理と、
を含むレイアウトプログラム。
【請求項１４】
前記複数の配線領域ごとに、対応する端子組を前記最短配線経路の配線長を用いてタイミング検証してタイミング余裕度を算出するタイミング余裕度を算出する算出処理をさらに含み、
前記優先度決定処理は、前記配線集中度及び前記タイミング余裕度に基づき、前記複数の配線領域に対応する各端子組における配線の優先度を決定する
ことを特徴とする請求項１３に記載のレイアウトプログラム。
【請求項１５】
前記配線集中度算出処理は、
各配線領域内の格子ごとに、前記最短配線経路の数のうち当該格子を通過する経路数の比率である格子通過確率を算出し、
前記格子通過確率に基づき、各配線領域内の格子ごとに配線が通過可能か否かを判定し、
前記配線が通過可能と判定された格子数を各配線領域内の行単位及び列単位で集計した場合の最小値を、前記複数の配線領域ごとの前記配線集中度として算出する
ことを特徴とする請求項１３又は１４に記載のレイアウトプログラム。
【請求項１６】
前記格子通過確率に基づき前記半導体集積回路上の配線禁止領域を特定し、
前記複数の端子組のうち、対応する配線領域内の全ての最短配線経路が前記特定された配線禁止領域を通過する場合、当該配線禁止領域の外周を含めて当該端子組における迂回配線検討領域を特定し、
前記特定された迂回配線検討領域に基づき、前記優先度が低い端子組における迂回配線経路を特定する迂回配線経路特定処理と、
前記特定した迂回配線経路を通過する場合のタイミング検証を実施するタイミング検証処理と、
をさらに含むことを特徴とする請求項１５に記載のレイアウトプログラム。
【請求項１７】
前記迂回配線経路特定処理は、
前記決定された配線の優先度が低い端子組について、対応する配線領域内の全ての最短配線経路が前記特定された配線禁止領域を通過する場合、当該配線禁止領域の外周を含めて当該端子組における迂回配線検討領域を特定する
ことを特徴とする請求項１６に記載のレイアウトプログラム。
【請求項１８】
前記迂回配線経路特定処理は、前記特定した迂回配線経路を通過するようにバッファを挿入し、
前記レイアウトプログラムは、
前記バッファが挿入された迂回配線経路によりＣＴＳ（Clock Tree Synthesis）及び詳細配線処理を実施させるＣＴＳ詳細配線処理
をさらに含むことを特徴とする請求項１６又は１７に記載のレイアウトプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、レイアウト方法、システム及びプログラムに関し、特に、半導体集積回路上の複数の端子組における配線経路を求めるためのレイアウト方法、システム及びプログラムに関する。
【背景技術】
【０００２】
集積回路の自動概略配線分野において、ＬＳＩ（Large Scale Integration）の高集積化、高速化に伴い、局所的に配線が集中する部分において、概略配線と実配線との見積もり誤差により再配線を行うケースが多発するため、概略配線の見積もり精度向上の要求（必要性）が高まってきた。
【０００３】
特許文献１には、詳細配線処理で未配線を低減することを目的とする集積回路の自動概略配線方法に関する技術が開示されている。特許文献１にかかる自動概略配線方法は、概略配線で格子境界の配線容量（配線混雑度）とグリッド使用率を用いて詳細配線処理で未配線が発生するかを予測し、見積もり精度を向上させるフローが構成されている。
【０００４】
図１２は、特許文献１にかかる概略配線処理とその後の配線可能判断処理の流れを示すフローチャートである。ステップＳ５５では、各格子の利用可能グリッド数と既に決定している概略経路に対する見積もりグリッド使用数から格子内のグリッド使用率を計算する。ここで、特許文献１における各種用語の定義を説明する。「格子」とは、単位配線領域である。「格子境界」とは、互いに隣接する格子と格子との境界である。「配線トラック」とは、配線することが可能な通路である。「配線混雑度」とは、格子境界を配線があと何本通過できるかを示す値である。「グリッド」とは、各格子内の上下方向の配線トラックと左右方向の配線トラックとが交差する交差点である。「利用可能グリッド数」とは、ある格子内で配線禁止領域を除いて利用可能なグリッド数である。「見積もりグリッド使用数」とは、通過経路ごとに「配線トラック×通過経路数」により求まる値の総和である。「グリッド使用率」とは、格子内の「見積もり使用グリッド数」と格子内の「利用可能グリッド数」との比により求まる値である。
【０００５】
図１３は、特許文献１にかかる見積もりグリッド使用数とグリッド使用率計算例を示す図である。ここで、図１３に示す例では、左右方向に５本の配線トラックが存在し、上下方向に５本の配線トラックが存在しているものとする。そして、格子の上側と右側の格子境界を通過する通過経路１を２本通過し、格子の左側と右側の格子境界を通過する通過経路２を１本通過し、格子の左側と下側の格子境界を通過する通過経路３を１本通過している。
【０００６】
この例では、通過経路毎の見積もり使用グリッド数は、次のように求めることができる。
通過経路１：（５／２＋５／２）×２＝１０
通過経路２：５×１＝５
通過経路３：（５／２＋５／２）×１＝５
【０００７】
従って、格子内の見積もり使用グリッド数は、１０＋５＋５＝２０と求まる。そして、特許文献１の段落００４５に示すように格子内の利用可能グリッド数が１８、図１３に示すように格子内の見積もり使用グリッド数が２０の場合、グリッド使用率は、２０／１８＝１．１１と求まる。そのため、格子内の見積もり使用グリッド数が格子内の利用可能グリッド数を超えている場合（すなわち、グリッド使用率が１より大きい場合）には、配線できないと判断することができる。
【０００８】
図１２に戻って、ステップＳ５６では、距離のコスト、格子境界の配線混雑度のコスト、グリッド使用率のコスト、その他折れ曲がりのコストなどに基づいて、コストが最小である経路を決定する。そして、ステップＳ５４〜Ｓ５６を未配線ネットがなくなるまで繰り返す（Ｓ５７）。すなわち、ステップＳ５４〜Ｓ５７の組合せは、配線容量ばかりでなく、利用可能グリッド数をも考慮に入れて（配線混雑度ばかりでなく、グリッド使用率にも基づいて）、未配線ネットがなくなるまでコストが最小である経路を決定するステップとして動作する。
【０００９】
ステップＳ６３は、ステップＳ６１でＮＯと判断されたときに実行される。ステップＳ６３では、見積もりグリッド使用数が利用可能グリッド数を超えている格子が存在するか否かを判断する。換言すれば、グリッド使用率が１を超えている格子が存在するか否かを判断する。ここで、見積もりグリッド使用数が利用可能グリッド数を超えている（グリッド使用率が１を超えている）格子を通過するネットを引き剥がし（Ｓ６４）、ステップＳ５４に戻る。一方、見積もりグリッド使用数が利用可能グリッド数を超えている（グリッド使用率が１を超えている）格子が存在しないなら、概略配線処理を終了する。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】特開平１０−２７０５６３号公報
【発明の概要】
【発明が解決しようとする課題】
【００１１】
特許文献１では、端子組当たりの配線経路を１経路に固定して、グリッド使用率を求めている。そのため、その端子組により利用可能グリッド数を超えていた場合は、固定された配線経路を引き剥がして、配線経路を新たな経路に変えて、再計算を行う必要がある。そして、新たな配線経路に変えたことにより、別な格子が利用可能グリッド数を超える場合があり得るため、収束に時間がかかるという問題がある。その理由としては、複数の異なる分割格子を通過する配線経路が考えられる始点端子と終点端子を結ぶ配線の場合でも、端子組当たりの配線経路は決められた１経路のみに対して配線容量とグリッド使用率を求めるためである。
【課題を解決するための手段】
【００１２】
本発明の第１の態様にかかるレイアウト方法は、格子状に区切られた半導体集積回路上の複数の端子組における配線経路を求めるためのレイアウト方法であって、前記複数の端子組における各端子間を配線可能な領域である複数の配線領域について、各配線領域内で前記端子間を格子単位に配線する際の最短配線経路の数を算出し、前記最短配線経路の数に基づいて、前記複数の配線領域ごとに局所的に配線が集中する度合である配線集中度を算出し、前記配線集中度に基づき、前記複数の配線領域に対応する各端子組における配線の優先度を決定する。
【００１３】
本発明の第２の態様にかかるレイアウトシステムは、格子状に区切られた半導体集積回路上の複数の端子組における配線経路を求めるためのレイアウトシステムであって、前記複数の端子組における各端子間を配線可能な領域である複数の配線領域について、各配線領域内で前記端子間を格子単位に配線する際の最短配線経路の数を算出する最短配線経路数算出手段と、前記最短配線経路の数に基づいて、前記複数の配線領域ごとに局所的に配線が集中する度合である配線集中度を算出する配線集中度算出手段と、前記配線集中度に基づき、前記複数の配線領域に対応する各端子組における配線の優先度を決定する優先度決定手段と、を備える。
【００１４】
本発明の第３の態様にかかるレイアウトプログラムは、格子状に区切られた半導体集積回路上の複数の端子組における配線経路を求めるための処理をコンピュータに実行させるレイアウトプログラムであって、前記複数の端子組における各端子間を配線可能な領域である複数の配線領域について、各配線領域内で前記端子間を格子単位に配線する際の最短配線経路の数を算出する最短配線経路数算出処理と、前記最短配線経路の数に基づいて、前記複数の配線領域ごとに局所的に配線が集中する度合である配線集中度を算出する配線集中度算出処理と、前記配線集中度に基づき、前記複数の配線領域に対応する各端子組における配線の優先度を決定する優先度決定処理と、を含む。
【００１５】
上述した本発明の第１乃至第３の態様により、概略配線処理において、局所的に配線が集中する配線領域を特定し、配線領域が極端に狭くタイミング的に余裕のない端子組を優先して配線指定することが可能となる。そのため、実配線（詳細配線処理）時に、タイミング的に余裕のある端子組より、タイミング的に余裕のない端子組を優先的に配線することになる。よって、タイミング的に余裕のある端子組を先に配線してしまうことにより生じる配線リソースの無駄な消費を低減することができる。
【発明の効果】
【００１６】
本発明により、配線リソースを有効活用し、収束時間を短縮するためのレイアウト方法、システム及びプログラムを提供することができる。
【図面の簡単な説明】
【００１７】
【図１】本発明の実施の形態１にかかる半導体集積回路のレイアウトシステムの構成を示すブロック図である。
【図２】本発明の実施の形態１にかかる半導体集積回路のレイアウト装置の構成を示すブロック図である。
【図３】本発明の実施の形態１にかかる半導体集積回路のレイアウト方法の処理の流れを示すフローチャートである。
【図４】本発明の実施の形態１にかかる半導体集積回路の基本セルの端子配置の例を示す図である。
【図５】本発明の実施の形態１にかかる半導体集積回路の一矩形領域におけるグリッド使用確率の例を示す図である。
【図６】本発明の実施の形態１にかかる半導体集積回路の一矩形領域におけるグリッド使用確率の例を示す図である。
【図７】本発明の実施の形態１にかかる半導体集積回路の複数の矩形領域におけるグリッド使用確率の例を示す図である。
【図８】本発明の実施の形態１にかかる最小配線可能グリッド重み付け係数の例を示す図である。
【図９】本発明の実施の形態１にかかる優先配線順位の例を示す図である。
【図１０】本発明の実施の形態２にかかる半導体集積回路のレイアウト方法の処理の流れを示すフローチャートである。
【図１１】本発明の実施の形態２にかかる半導体集積回路の複数の矩形領域におけるグリッド使用確率の例を示す図である。
【図１２】関連技術にかかる概略配線処理とその後の配線可能判断処理の流れを示すフローチャートである。
【図１３】関連技術にかかる見積もりグリッド使用数とグリッド使用率計算例を示す図である。
【発明を実施するための形態】
【００１８】
以下では、本発明を適用した具体的な実施の形態について、図面を参照しながら詳細に説明する。各図面において、同一要素には同一の符号が付されており、説明の明確化のため、必要に応じて重複説明は省略する。
【００１９】
＜発明の実施の形態１＞
図１は、本発明の実施の形態１にかかる半導体集積回路の設計ツールを実施するためのレイアウトシステム１００の構成を示すブロック図である。レイアウトシステム１００は、本発明の実施の形態１にかかる半導体集積回路のレイアウト方法を実施する情報システムの一例である。レイアウトシステム１００は、ネットワーク１０３を介して接続されるサーバ装置１０１と、コンピュータ装置１０４ａ、１０４ｂ、・・・、１０４ｎとを備えるコンピュータシステムである。ネットワーク１０３は、インターネット、イントラネット、公衆網、専用線等の通信ネットワークである。
【００２０】
サーバ装置１０１は、記憶装置１０２を含むコンピュータ装置である。尚、サーバ装置１０１のその他の構成及び動作は、公知なものであるため、図示及び詳細な説明を省略する。記憶装置１０２には、少なくともレイアウトプログラム１０２１が格納されている。記憶装置１０２は、例えば、ハードディスクドライブ、フラッシュメモリ等の記憶媒体又は不揮発性の記憶装置でもよいし、ＤＲＡＭ（Dynamic Random Access Memory）等の揮発性の記憶装置であってもよい。サーバ装置１０１は、ネットワーク１０３を介してクライアント端末であるコンピュータ装置１０４ａ乃至１０４ｎと接続される。サーバ装置１０１は、コンピュータ装置１０４ａ乃至１０４ｎのいずれかからの要求に応じて、記憶装置１０２に格納されたレイアウトプログラム１０２１を、ネットワーク１０３を介して要求元へ提供する。レイアウトプログラム１０２１には、本発明の実施の形態１にかかる半導体集積回路の設計ツールが記録されている。また、記憶装置１０２には、図示しない構成として、論理素子のライブラリ並びにタイミング制約、ネットリスト、遅延情報及びタイミング解析結果のデータが格納されている。
【００２１】
コンピュータ装置１０４ａ乃至１０４ｎは、サーバ装置１０１からレイアウトプログラム１０２１を取得し、内蔵する記憶装置（不図示）に記憶して実行することにより、本発明の実施の形態１にかかる半導体集積回路のレイアウト処理を実現するコンピュータ装置である。コンピュータ装置１０４ａ乃至１０４ｎは、例えば、エンジニアリングワークステーション等である。
【００２２】
尚、本発明の実施の形態１は、図１に示したレイアウトシステム１００のようなコンピュータシステムに限定されない。例えば、本発明の実施の形態１にかかるレイアウトシステム１００は、単一のコンピュータ装置により実現しても構わない。その場合、例えば、コンピュータ装置１０４ａに予めレイアウトプログラム１０２１を内蔵することで実現可能である。
【００２３】
図２は、本発明の実施の形態１にかかる半導体集積回路のレイアウト方法を一台のコンピュータ装置により実施するレイアウト装置１０のハードウェア構成を示すブロック図である。レイアウト装置１０は、ＣＰＵ（Central Processing Unit）１１０と、ＲＡＭ（Random Access Memory）１２０と、ＲＯＭ（Read Only Memory）１３０と、ＩＦ（InterFace）部１４０と、ハードディスク１５０とを備えるコンピュータ装置である。また、ハードディスク１５０は、不揮発性記憶装置であり、ＯＳ（Operating System）１５１及びレイアウトプログラム１５２を格納する。尚、ハードディスク１５０には、図示しない構成として、論理素子のライブラリ並びにタイミング制約、ネットリスト、遅延情報及びタイミング解析結果のデータが格納されている。
【００２４】
ＣＰＵ１１０は、レイアウト装置１０における各種処理、ＲＡＭ１２０、ＲＯＭ１３０、ＩＦ部１４０及びハードディスク１５０へのアクセス等を制御する制御装置である。ＩＦ部１４０は、レイアウト装置１０の外部とのデータの入出力を行う。レイアウト装置１０は、ＣＰＵ１１０がハードディスク１５０に格納されたＯＳ１５１及びレイアウトプログラム１５２等を読み込み、実行する。これにより、レイアウト装置１０は、半導体集積回路のレイアウト処理として実現する。
【００２５】
本発明の実施の形態１にかかる半導体集積回路のレイアウト方法は、半導体集積回路上の複数の端子組における配線経路を求めるための方法である。例えば、半導体集積回路上に複数の基本セルやマクロセルを配置し、それらのセル間を接続するための配線経路を求める。ここで、基本セルやマクロセルには、他のセルと配線で接続するための端子を有する。つまり、複数のセル間を接続するために、各セルの端子同士を配線して接続することとなる。その際の配線経路を求める対象となる端子の組合せを端子組と呼ぶものとする。尚、端子組をネットと呼んでも良い。端子組は、配線経路の始点となる始点端子と終点となる終点端子の２つの端子の組合せである。但し、始点端子と終点端子は、入れ替わったものであっても端子組としては区別しないものとする。
【００２６】
図３は、本発明の実施の形態１にかかる半導体集積回路のレイアウト方法の処理の流れを示すフローチャートである。尚、以下の説明では、説明の便宜上、上述したレイアウト装置１０を用いたものとして説明する。その際、ＲＡＭ１２０又はハードディスク１５０には、配置情報ＨＤ１０、グリッド情報ＨＤ２０、グリッド使用確率情報ＨＤ３０、タイミング検証結果ＨＤ４０及び優先配線情報ＨＤ５０が格納領域として確保されているものとする。
【００２７】
まず、レイアウト装置１０は、半導体集積回路上に基本セルやマクロセルの配置を行う（Ｓ１０００）。つまり、基本セルやマクロセルに含まれる複数の端子が、半導体集積回路上のどのグリッド位置に配置されたかが定まる。
【００２８】
次に、レイアウト装置１０は、マンハッタン長領域を選定する（Ｓ１１００）。つまり、ステップＳ１０００により複数の端子のグリッド位置が定まるため、始点端子と終点端子からなる端子組の位置関係も定まることとなる。ここで、端子組における各端子間をグリッド単位に矩形で囲んだ矩形領域を、マンハッタン長領域と呼ぶものとする。マンハッタン長領域は、基本セルやマクロセルの端子間を最短距離すなわちマンハッタン距離で配線できる領域である。続いて、レイアウト装置１０は、マンハッタン長領域のグリッド間隔を求め、グリッド情報ＨＤ２０に格納する。ここで、図４を用いて、グリッド間隔の算出について説明する。
【００２９】
図４は、本発明の実施の形態１にかかる半導体集積回路の基本セルの端子配置の例を示す図である。図４には、始点端子座標Ａ０及び終点端子座標Ａ１によりマンハッタン長領域ＡＲＥＡ＿Ａ、始点端子座標Ｂ０及び終点端子座標Ｂ１によりマンハッタン長領域ＡＲＥＡ＿Ｂ、始点端子座標Ｃ０及び終点端子座標Ｃ１によりマンハッタン長領域ＡＲＥＡ＿Ｃ、始点端子座標Ｄ０及び終点端子座標Ｄ１によりマンハッタン長領域ＡＲＥＡ＿Ｄ及び始点端子座標Ｅ０及び終点端子座標Ｅ１によりマンハッタン長領域ＡＲＥＡ＿Ｅが定まることを示す。尚、マンハッタン長領域ＡＲＥＡ＿Ｅには、利用可能グリッドとして座標Ｅ２〜Ｅ５が含まれるものとする。
【００３０】
尚、ここでは説明の便宜上、各端子位置は、グリッド単位で表現できるものとする。そのため、本発明の実施の形態１にかかる「利用可能グリッド」は、単に、端子が配置されていないグリッドを指すものとする。そのため、端子位置及びグリッド位置は、座標により特定するものとする。
【００３１】
ここで、代表してマンハッタン長領域ＡＲＥＡ＿Ｅにおけるグリッド間隔を求める。マンハッタン長領域ＡＲＥＡ＿Ｅは、始点端子座標Ｅ０（３，５）と終点端子座標Ｅ１（４，３）とをマンハッタン距離、つまりグリッド単位に最短配線距離で配線した場合に取り得る利用可能グリッドを含む領域である。このとき、レイアウト装置１０は、列方向つまりＸ座標のグリッド間隔を、４−３＝１として算出する。同様に、レイアウト装置１０は、行方向つまりＹ座標のグリッド間隔を、５−３＝２として算出する。そして、レイアウト装置１０は、Ｘ座標のグリッド間隔"１"とＹ座標のグリッド間隔"２"とをマンハッタン長領域ＡＲＥＡ＿Ｅに関連付けてグリッド情報ＨＤ２０へ格納する。同様に、レイアウト装置１０は、他のマンハッタン長領域ＡＲＥＡ＿Ａ〜Ｄについてもグリッド間隔を算出し、グリッド情報ＨＤ２０へ格納する。
【００３２】
続いて、レイアウト装置１０は、グリッド使用確率を算出する（Ｓ１２００）。具体的には、まず、レイアウト装置１０は、マンハッタン長領域ごとにグリッド情報ＨＤ２０からグリッド間隔を読み出し、グリッド間隔を用いて、マンハッタン長領域当たりの最短ルート数を以下の式（１）により算出する。
最短ルート数  ＝  （（Ｘ座標のグリッド間隔  ＋  Ｙ座標のグリッド間隔）！）／（Ｘ座標のグリッド間隔！  ×  Ｙ座標のグリッド間隔！）      ・・・（１）
尚、"！"は、数式記号で階乗計算（ｎ！  ＝  ｎ  ×  （ｎ−１）  ×  （ｎ−２）・・・×２×１。但し、ｎは自然数。また、０！＝１）を表す。
【００３３】
次に、レイアウト装置１０は、マンハッタン長領域内の各グリッドについて、当該グリッドを通過する配線通過ルート数を以下の式（２）により算出する。あるグリッドにおける配線通過ルート数とは、始点端子から当該グリッドまでの最短ルート数と、当該グリッドから終点端子までの最短ルート数との積で求まる値である。また、各最短ルート数の算出には、前述した式（１）を用いることができる。
配線通過ルート数  ＝  （始点端子から当該グリッドまでの最短ルート数）  ×  （当該グリッドから終点端子までの最短ルート数）      ・・・（２）
【００３４】
そして、レイアウト装置１０は、最短ルート数と配線通過ルート数とを用いてグリッド使用確率を以下の式（３）により算出する。
グリッド使用確率  ＝  （配線通過ルート数  ／  （最短ルート数  ×  配線層係数））      ・・・（３）
但し、始点端子と終点端子のグリッド使用確率を１００％とする。その後、レイアウト装置１０は、算出したグリッド使用確率をグリッドに関連付けてグリッド使用確率情報ＨＤ３０に格納する。
【００３５】
言い換えると、レイアウト装置１０は、各矩形領域内で端子間をグリッド単位に配線する際の最短配線経路の数を算出する。ここで、最短配線経路は、始点端子から終点端子までをグリッド単位で接続した場合の配線経路である。つまり、最短配線経路は、上述した最短ルートを指す。そして、レイアウト装置１０は、各矩形領域内のグリッドごとに、最短配線経路の数のうち当該グリッドを通過する経路数の比率であるグリッド通過確率を算出する。ここで、当該グリッドを通過する経路数とは、上述した配線通過ルート数を指す。また、グリッド通過確率は、上述したグリッド使用確率又は後述する総グリッド使用確率を指す。
【００３６】
ここで、例として、座標Ｅ４（４，４）におけるグリッド使用確率を算出する過程を示す。まず、座標Ｅ４が属するマンハッタン長領域ＡＲＥＡ＿Ｅにおける最短ルートを算出する。マンハッタン長領域ＡＲＥＡ＿ＥにおけるＸ座標のグリッド間隔"１"とＹ座標のグリッド間隔"２"とを式（１）に適用すると、以下の式（１Ａ）となる。
最短ルート数  ＝  （（１＋２）！）／（１！×２！）＝６／２＝３      ・・・（１Ａ）
つまり、始点端子座標Ｅ０と終点端子座標Ｅ１との最短配線距離は、３通りあることを示す。
【００３７】
次に、座標Ｅ４における配線通過ルート数を算出する。具体的には、まず、始点端子座標Ｅ０と座標Ｅ４との最短ルート数を、式（１）を用いて算出すると、以下の式（１Ｂ）となる。
最短ルート数  ＝  （（１＋１）！）／（１！×１！）＝２／１＝２      ・・・（１Ｂ）
【００３８】
同様に、座標Ｅ４と終点端子座標Ｅ１との最短ルート数を、式（１）を用いて算出すると、以下の式（１Ｃ）となる。
最短ルート数  ＝  （（０＋１）！）／（０！×１！）＝１／１＝１      ・・・（１Ｃ）
【００３９】
そして、式（１Ｂ）及び式（１Ｃ）の値を式（２）に適用すると、マンハッタン長領域ＡＲＥＡ＿Ｅにおける座標Ｅ４の配線通過ルート数は、以下の式（２Ａ）となる。
配線通過ルート数  ＝  ２×１＝２      ・・・（２Ａ）
【００４０】
続いて、式（１Ａ）及び式（２Ａ）の値を式（３）に適用すると、マンハッタン長領域ＡＲＥＡ＿Ｅにおける座標Ｅ４のグリッド使用確率は、以下の式（３Ａ）となる。
グリッド使用確率  ＝  （２／（３×１））×１００＝６７％      ・・・（３Ａ）
尚、ここでは、配線層係数を"１"であるものとする。
【００４１】
同様にして、マンハッタン長領域ＡＲＥＡ＿Ｅにおける座標Ｅ２、Ｅ３及びＥ５のグリッド使用確率を算出することができる。尚、始点端子及び終点端子のグリッド使用確率は、１００％とする。つまり、マンハッタン長領域ＡＲＥＡ＿Ｅにおける始点端子座標Ｅ０及び終点端子座標Ｅ１のグリッド使用確率は、１００％となる。図５は、本発明の実施の形態１にかかるマンハッタン長領域ＡＲＥＡ＿Ｅにおける各グリッドのグリッド使用確率の例を示す図である。
【００４２】
また、同様にして、レイアウト装置１０は、マンハッタン長領域ＡＲＥＡ＿Ａ〜ＡＲＥＡ＿Ｄにおける各グリッドのグリッド使用確率も求める。図６は、本発明の実施の形態１にかかるマンハッタン長領域ＡＲＥＡ＿Ｂにおける各グリッドのグリッド使用確率の例を示す図である。ここで、座標Ｅ３、Ｅ４、Ｅ５及びＥ１は、マンハッタン長領域ＡＲＥＡ＿Ｅ及びＡＲＥＡ＿Ｂの両方に属する。しかし、この段階では、それぞれのマンハッタン長領域におけるグリッド使用確率を算出する。例えば、座標Ｅ４のグリッド使用確率は、図５では"６７％"であり、図６では"４０％"である。
【００４３】
続いて、レイアウト装置１０は、総グリッド使用確率を算出する（Ｓ１３００）。具体的には、レイアウト装置１０は、ステップＳ１２００で算出したマンハッタン長領域ごとの各グリッドのグリッド使用確率をグリッド単位で集計して、つまり同一の座標について総和を求めて、総グリッド使用確率を算出する。そして、レイアウト装置１０は、総グリッド使用確率を各グリッドに関連付けてグリッド使用確率情報ＨＤ３０に格納する。
【００４４】
図７は、本発明の実施の形態１にかかる半導体集積回路の複数のマンハッタン長領域におけるグリッド使用確率の例を示す図である。例えば、マンハッタン長領域ＡＲＥＡ＿Ｅ及びＡＲＥＡ＿Ｂの両方に属する座標Ｅ４の総グリッド使用確率は、マンハッタン長領域ＡＲＥＡ＿Ｅ及びＡＲＥＡ＿Ｂのそれぞれにおけるグリッド使用確率の総和である"１０７％"であることを示す。
【００４５】
その後、レイアウト装置１０は、配線集中度を算出する（Ｓ１４００）。ここで、配線集中度とは、矩形領域内で局所的に配線が集中する度合であるものとする。すなわち、配線集中度は、矩形領域内全体の配線混雑度ではない。
【００４６】
言い換えると、レイアウト装置１０は、最短配線経路の数に基づいて、複数の矩形領域ごとに配線集中度を算出する。より詳細には、レイアウト装置１０は、グリッド通過確率に基づき、各矩形領域内のグリッドごとに配線が通過可能か否かを判定し、配線が通過可能と判定されたグリッド数を各矩形領域内の行単位及び列単位で集計した場合の最小値を、複数の矩形領域ごとの配線集中度として算出する。
【００４７】
具体的には、まず、レイアウト装置１０は、マンハッタン長領域ごとに、各グリッドの総グリッド使用確率をグリッド使用確率情報ＨＤ３０から読み出す。そして、レイアウト装置１０は、読み出した総グリッド使用確率が所定の閾値である行列グリッド使用確率閾値未満であるか否かを判定する。すなわち、当該グリッドに配線をする場合の混雑度合が許容範囲であるか否かを判定する。つまり、当該グリッドに配線が通過可能か否かを判定する。
【００４８】
次に、レイアウト装置１０は、各マンハッタン長領域について、行単位及び列単位で行列グリッド使用確率閾値未満であるグリッド数を集計する。但し、集計の対象となるマンハッタン長領域における始点端子又は終点端子であるグリッドについては、総グリッド使用確率に関わらず、行列グリッド使用確率閾値未満であるグリッドとしてカウントする。始点端子及び終点端子であるグリッドは、当該マンハッタン長領域で必ず配線に使用されるためである。例えば、図７において、座標Ｅ１は、総グリッド使用確率が"１６０％"であるため、マンハッタン長領域ＡＲＥＡ＿Ｂにおいては、行列グリッド使用確率閾値未満であるグリッドとしてはカウントされない。一方、終点端子座標Ｅ１は、マンハッタン長領域ＡＲＥＡ＿Ｅにおいては、終点端子であるため、行列グリッド使用確率閾値未満であるグリッドとみなしてカウントされる。
【００４９】
続いて、レイアウト装置１０は、行単位及び列単位で集計したグリッド数のうち最小値を最小配線可能グリッド数として選択する。ここで、最小配線可能グリッド数は、配線集中度の一例である。そして、レイアウト装置１０は、選択した最小配線可能グリッド数をマンハッタン長領域に関連付けてグリッド使用確率情報ＨＤ３０に格納する。
【００５０】
ここで、例として、マンハッタン長領域ＡＲＥＡ＿Ｅにおける最小配線可能グリッド数を算出する過程を示す。ここでは、行列グリッド使用確率閾値を"１５０％"とする。まず、レイアウト装置１０は、グリッド使用確率情報ＨＤ３０からマンハッタン長領域ＡＲＥＡ＿Ｅに属する座標Ｅ０〜Ｅ５の総グリッド使用確率を読み出す。ここでは、以下の式（４）のようになる。
（Ｅ５、Ｅ３、Ｅ０、Ｅ１、Ｅ４、Ｅ２）＝（８７％、１３３％、１００％、１６０％、１０７％、３３％）      ・・・（４）
この内、行列グリッド使用確率閾値である１５０％未満であるグリッド座標は、Ｅ５、Ｅ３、Ｅ０、Ｅ４、Ｅ２となる。ここで、Ｅ１は、行列グリッド使用確率閾値以上であるが、終点端子であるため、行列グリッド使用確率閾値未満であるグリッドとみなされる。そのため、マンハッタン長領域ＡＲＥＡ＿Ｅについては、座標Ｅ０〜Ｅ５の全てが配線可能と判定される。尚、マンハッタン長領域ＡＲＥＡ＿Ｂにおいては、マンハッタン長領域ＡＲＥＡ＿Ｅと重複する座標Ｅ３、Ｅ４、Ｅ５及びＥ１が配線不可能と判定される。そして、行単位及び列単位に該当するグリッドを集計すると、以下のようになる。
第３行：２
第４行：２
第５行：２
第３列：３
第４列：３
そのため、マンハッタン長領域ＡＲＥＡ＿Ｅの最小配線可能グリッド数は、"２"となる。同様にして、レイアウト装置１０は、マンハッタン長領域ＡＲＥＡ＿Ａ〜ＡＲＥＡ＿Ｄにおける各グリッドの最小配線可能グリッド数も求める。
【００５１】
つまり、まず、マンハッタン長領域のうち、行単位又は列単位という局所的な領域について個別に配線集中度を求める。ここでは、配線可能なグリッドが少ない場合に、配線集中度が高いものとみなしている。そして、それらの中で最も配線集中度が高いものを当該マンハッタン長領域における配線集中度として選択する。そのため、仮に、行単位及び列単位のうち大半の配線集中度が低いとしても、一つでも配線集中度が高いものがある場合には、当該マンハッタン長領域自体の配線集中度が高いものとすることができる。つまり、単に、マンハッタン長領域内の配線混雑度を平均したものと比べて、局所的に配線が集中している度合を表現することができる。
【００５２】
尚、局所的な領域としては、行単位又は列単位以外であっても構わない。例えば、マンハッタン長領域ＡＲＥＡ＿Ｅの場合、始点端子座標Ｅ０と終点端子座標Ｅ１を除き、Ｅ２及びＥ３を第１のグリッド群、Ｅ４及びＥ５を第２のグリッド群として分類し、グリッド群ごとに配線可能グリッド数を算出し、それらの最小値を最小配線可能グリッド数としてもよい。
【００５３】
そして、レイアウト装置１０は、タイミング検証を行う（Ｓ１５００）。すなわち、レイアウト装置１０は、複数の矩形領域ごとに、対応する端子組を最短配線経路の配線長を用いてタイミング検証してタイミング余裕度を算出する。具体的には、レイアウト装置１０は、配置情報ＨＤ１０から基本セルの配置情報を読み出し、配線長を概略配線長であるマンハッタン距離としてタイミング検証を実施する。そして、レイアウト装置１０は、タイミング検証結果をタイミング検証結果ＨＤ４０に格納する。ここで、タイミング検証結果には、タイミング制約（セットアップ／ホールド）違反の有無やマンハッタン長領域ごとのタイミング制約に対するタイミングの余裕を示す値であるタイミング余裕度を含むものとする。
【００５４】
その後、レイアウト装置１０は、タイミング検証結果を判定する（Ｓ１６００）。すなわち、レイアウト装置１０は、タイミング検証結果ＨＤ４０からタイミング検証結果を読み出し、タイミング制約を満たしているか否かを判定する。タイミング制約を満たしていないと判定した場合、つまり、タイミング制約違反があると判定した場合、ステップＳ１０００へ進む。
【００５５】
全てのマンハッタン長領域についてタイミング制約を満たしていると判定した場合、レイアウト装置１０は、マンハッタン長領域のうち優先配線を指定する（Ｓ１７００）。具体的には、まず、レイアウト装置１０は、タイミング検証結果ＨＤ４０からタイミング検証結果を読み出し、タイミング余裕度がタイミング余裕閾値未満か否かを判定する。タイミング余裕閾値未満であると判定した場合、レイアウト装置１０は、グリッド使用確率情報ＨＤ３０から最小配線可能グリッド数を読み出し、読み出した最小配線可能グリッド数に対応する最小配線可能グリッド重み付け係数を優先配線情報ＨＤ５０から読み出す。
【００５６】
ここで、優先配線情報ＨＤ５０には、最小配線可能グリッド数と最小配線可能グリッド重み付け係数との対応テーブルが予め定義されているものとする。図８は、本発明の実施の形態１にかかる最小配線可能グリッド重み付け係数の例を示す図である。例えば、マンハッタン長領域ＡＲＥＡ＿Ｅの最小配線可能グリッド数は、"２"であるため、最小配線可能グリッド重み付け係数は、"０．７５"となる。
【００５７】
そして、レイアウト装置１０は、タイミング余裕度と最小配線可能グリッド重み付け係数とを用いて、以下の式（５）により配線余裕度を算出する。
配線余裕度  ＝  タイミング余裕度  ×  最小配線可能グリッド重み付け係数      ・・・（５）
【００５８】
ここで、例として、マンハッタン長領域ＡＲＥＡ＿Ａにおける配線余裕度を算出する過程を示す。ここでは、マンハッタン長領域ＡＲＥＡ＿Ａにおけるタイミング余裕度を"０．５２"とする。また、マンハッタン長領域ＡＲＥＡ＿Ａにおける最小配線可能グリッド数は、"１"である。そして、優先配線指定するか否かを判定するためのタイミング余裕閾値を"１．０"とする。この場合、レイアウト装置１０は、マンハッタン長領域ＡＲＥＡ＿Ａのタイミング余裕度がタイミング余裕閾値未満であると判定し、グリッド使用確率情報ＨＤ３０からマンハッタン長領域ＡＲＥＡ＿Ａの最小配線可能グリッド数を読み出す。そして、優先配線情報ＨＤ５０から最小配線可能グリッド重み付け係数"０．７０"を読み出す。そして、レイアウト装置１０は、タイミング余裕度"０．５２"と最小配線可能グリッド重み付け係数"０．７０"とを式（５）に適用すると、マンハッタン長領域ＡＲＥＡ＿Ａの配線余裕度は、以下の式（５Ａ）となる。
配線余裕度  ＝  ０．５２  ×  ０．７０  ＝  ０．３６４０      ・・・（５Ａ）
【００５９】
レイアウト装置１０は、全てのマンハッタン長領域について配線余裕度を求める。そして、配線余裕度の小さい領域から順に配線するように優先配線情報として優先配線情報ＨＤ５０に格納する。図９は、本発明の実施の形態１にかかる優先配線順位の例を示す図である。
【００６０】
言い換えると、レイアウト装置１０は、配線集中度に基づき、複数の矩形領域に対応する各端子組における配線の優先度を決定する。そして、レイアウト装置１０は、配線集中度及びタイミング余裕度に基づき、複数の矩形領域に対応する各端子組における配線の優先度を決定する。
【００６１】
その後、レイアウト装置１０は、ＣＴＳ（Clock Tree Synthesis）及び詳細配線処理を行う（Ｓ３０００）。すなわち、レイアウト装置１０は、グリッド使用確率情報ＨＤ３０に格納されたグリッド使用確率と、優先配線情報ＨＤ５０に格納された配線優先情報に基づいて、ＣＴＳ及び詳細配線処理を行う。
【００６２】
以上のことから、本発明の実施の形態１により、概略配線処理において、局所的に配線が集中する矩形領域を特定し、配線領域が極端に狭くタイミング的に余裕のない端子組を優先して配線指定することが可能となる。そのため、実配線（詳細配線処理）時に、タイミング的に余裕のある端子組より、タイミング的に余裕のない端子組を優先的に配線することになる。よって、タイミング的に余裕のある端子組を先に配線してしまうことにより生じる配線リソースの無駄な消費を低減することができる。そのため、未配線や新たなタイミングエラーやクロストークエラー発生を抑制する効果がある。
【００６３】
＜発明の実施の形態２＞
本発明の実施の形態２では、タイミング的に余裕のある端子組について、最短配線経路ではなく、敢えて迂回した配線経路を採用することで、その後の詳細配線処理によるタイミングエラーを回避し、配線経路を選択し直す回数を軽減させることで、収束を早めるものである。
【００６４】
本発明の実施の形態２にかかるレイアウト方法は、グリッド通過確率に基づき半導体集積回路上の配線禁止領域を特定し、複数の端子組のうち、対応する矩形領域内の全ての最短配線経路が特定された配線禁止領域を通過する場合、当該配線禁止領域の外周を含めて当該端子組における迂回配線検討領域を特定し、特定された迂回配線検討領域に基づき、前記優先度が低い端子組における迂回配線経路を特定し、特定した迂回配線経路を通過する場合のタイミング検証を実施するものである。
【００６５】
また、本発明の実施の形態２にかかるレイアウト方法は、決定された配線の優先度が低い端子組について、対応する矩形領域内の全ての最短配線経路が前記特定された配線禁止領域を通過する場合、当該配線禁止領域の外周を含めて当該端子組における迂回配線検討領域を特定するようにするとよい。つまり、上述した本発明の実施の形態１に改良を加えることが望ましい。
【００６６】
さらに、本発明の実施の形態２にかかるレイアウト方法は、特定した迂回配線経路を通過するようにバッファを挿入し、バッファが挿入された迂回配線経路によりＣＴＳ及び詳細配線処理を実施させることが望ましい。これにより、ＣＴＳ及び詳細配線処理の収束効率が高まる。
【００６７】
図１０は、本発明の実施の形態２にかかる半導体集積回路のレイアウト方法の処理の流れを示すフローチャートである。尚、図３のフローチャートと同等の処理については、同一の符号を付し、詳細な説明を省略する。そのため、以下では、本発明の実施の形態２に特有の処理を中心に説明する。尚、ＲＡＭ１２０又はハードディスク１５０には、配置情報ＨＤ１０、グリッド情報ＨＤ２０、グリッド使用確率情報ＨＤ３０、タイミング検証結果ＨＤ４０及び優先配線情報ＨＤ５０に加え、迂回配線情報ＨＤ６０が格納領域としてさらに確保されているものとする。
【００６８】
まず、ステップＳ１６００により全てのマンハッタン長領域についてタイミング制約を満たしていると判定した場合、レイアウト装置１０は、迂回配線を指定する（Ｓ２０００）。具体的には、レイアウト装置１０は、タイミング検証結果ＨＤ４０からタイミング検証結果を読み出し、タイミング余裕度がタイミング余裕閾値以上であるか否かを判定する。タイミング余裕閾値以上であると判定した場合、迂回配線するマンハッタン長領域として迂回配線情報ＨＤ６０に格納する。つまり、配線の優先度が低い端子組を迂回配線するマンハッタン長領域とする。
【００６９】
次に、レイアウト装置１０は、迂回配線経路を策定する（Ｓ２１００）。具体的には、まず、レイアウト装置１０は、半導体集積回路上の各グリッドについて、グリッド使用確率情報ＨＤ３０に格納された総グリッド使用確率が所定の閾値である配線混雑閾値以上であるか否かを判定する。次に、レイアウト装置１０は、配線混雑閾値以上であるグリッドによる定まる最小の矩形領域を配線禁止領域として特定する。このとき、レイアウト装置１０は、特定された配線禁止領域を迂回配線情報ＨＤ６０に格納してもよい。
【００７０】
そして、レイアウト装置１０は、迂回配線情報ＨＤ６０に格納された迂回配線するマンハッタン長領域について、当該マンハッタン長領域における全ての最短配線経路が、特定された配線禁止領域を通過するか否かを判定する。全ての最短配線経路が配線禁止領域を通過すると判定した場合、レイアウト装置１０は、配線禁止領域の１グリッド外側を含めた領域を迂回配線禁止外周領域として特定する。このとき、レイアウト装置１０は、迂回配線禁止外周領域を迂回配線情報ＨＤ６０に格納してもよい。そして、レイアウト装置１０は、迂回配線禁止外周領域と当該マンハッタン長領域とを含めて迂回配線検討領域を特定する。このとき、レイアウト装置１０は、迂回配線検討領域を迂回配線情報ＨＤ６０に格納してもよい。
【００７１】
その後、レイアウト装置１０は、特定された迂回配線検討領域から配線禁止領域を通過せずに終点端子まで配線可能な配線経路のうち、配線の折れ曲がり数や使用するグリッド数が最小になる経路を迂回配線経路として選択する。そして、レイアウト装置１０は、迂回配線経路上にある迂回配線検討領域の頂点に、配線を誘導するための導きバッファを挿入する。
【００７２】
図１１は、本発明の実施の形態２にかかる半導体集積回路の複数の矩形領域におけるグリッド使用確率の例を示す図である。ここでは、マンハッタン長領域ＡＲＥＡ＿Ｆが迂回配線するマンハッタン長領域であるものとする。マンハッタン長領域ＡＲＥＡ＿Ｆは、始点端子座標Ｆ０（１，５）と終点端子座標Ｆ１（７，２）とにより定まる矩形領域である。
【００７３】
また、配線混雑閾値を"１５０％"とする。このとき、配線混雑閾値以上であるグリッドは、（３，２）、（３，３）、（４，３）、（４，４）、（５，４）、（５，５）、（６，５）、（６，６）となる。そのため、配線禁止領域ＡＲＥＡ＿Ｘは、（３，２）、（６，２）、（３，６）、（６，６）を頂点とする矩形領域となる。さらに、配線禁止領域ＡＲＥＡ＿Ｘの１グリッド外側を含めた迂回配線禁止外周領域ＡＲＥＡ＿ＦＯＲＢは、（２，１）、（７，１）、（２，７）、（７，７）を頂点とする矩形領域となる。そして、迂回配線禁止外周領域ＡＲＥＡ＿ＦＯＲＢとマンハッタン長領域ＡＲＥＡ＿Ｆとを含めた最小の矩形領域である迂回配線検討領域ＡＲＥＡ＿ＦＮは、（１，１）、（７，１）、（１，７）、（７，７）を頂点とする矩形領域となる。
【００７４】
そして、レイアウト装置１０は、迂回配線検討領域ＡＲＥＡ＿ＦＮから配線禁止領域ＡＲＥＡ＿Ｘを通過せずに始点端子座標Ｆ０と終点端子座標Ｆ１とを配線する経路を求める。ここでは、（１，５）〜（１，７）〜（７，７）〜（７，２）と、（１，５）〜（１，１）〜（７，１）〜（７，２）という２経路が求められる。当該２経路で使用するグリッド数は、それぞれ１３グリッドと１１グリッドとなる。そこで、よりグリッド数の少ない（１，５）〜（１，１）〜（７，１）〜（７，２）を迂回配線経路とする。さらに、レイアウト装置１０は、迂回配線検討領域内で迂回配線経路の頂点である座標ＦＢ０（１，１）と座標ＦＢ１（７，１）に導きバッファを挿入する。
【００７５】
その後、レイアウト装置１０は、ステップＳ１５００と同様に、タイミング検証を行う（Ｓ２２００）。但し、レイアウト装置１０は、ステップＳ２１００で選択した迂回配線経路を考慮してタイミング検証を行い、タイミング検証結果をタイミング検証結果ＨＤ４０に格納する。
【００７６】
また、レイアウト装置１０は、ステップＳ１６００と同様に、タイミング検証結果を判定する（Ｓ２３００）。すなわち、レイアウト装置１０は、タイミング検証結果ＨＤ４０からタイミング検証結果を読み出し、タイミング制約を満たしているか否かを判定する。タイミング制約を満たしていないと判定した場合、つまり、タイミング制約違反があると判定した場合、ステップＳ１０００へ進む。
【００７７】
全てのマンハッタン長領域についてタイミング制約を満たしていると判定した場合、レイアウト装置１０は、ＣＴＳ及び詳細配線処理を行う（Ｓ３０００）。このとき、レイアウト装置１０は、グリッド使用確率情報ＨＤ３０に格納されたグリッド使用確率と、ステップＳ２１００により選択された迂回配線経路と挿入された導きバッファとに基づいて、ＣＴＳ及び詳細配線処理を行う。
【００７８】
以上のことから、本発明の実施の形態２により、概略配線処理において、局所的に配線が集中する矩形領域を特定し、タイミング的に余裕のある端子組については、当該矩形領域を迂回する経路を策定することが可能となる。そのため、実配線（詳細配線処理）時にタイミング的に余裕のある配線を局所的に混雑している箇所を迂回して配線させることとなる。よって、タイミング的に余裕のない配線がタイミング的に余裕のある配線によって配線リソースが消費されてしまうというケースを低減することができる。そのため、未配線や新たなタイミングエラーやクロストークエラー発生を抑制する効果がある。
【００７９】
＜その他の発明の実施の形態＞
本発明は、大規模集積回路（ＬＳＩ）や、論理回路を設計開発する計算機援用設計（ＣＡＤ）に関し、特に、ＬＳＩチップ上に部品セルを、全体での配線長などが最小になるように自動配置及び配線する方法の中の、集積回路チップの各ネットの配線経路を決定する集積回路の自動概略配線方法に関するものである。
【００８０】
本発明の実施の形態１は、半導体集積回路を設計開発する計算機援用設計（ＣＡＤ）に関し、特に、ＬＳＩのチップに基本セルやマクロセルを全体での配線長などが最小になるようなレイアウト方法において、配線ごとにマンハッタン長領域内の最短ルート数を求め、配線ごとにマンハッタン長領域内の各グリッドを通過するルート数を求め、マンハッタン長領域内の最短ルート数と各グリッドを通過するルート数からグリッド使用確率を求める手段と、各グリッドのグリッド使用確率から、配線ごとに配線に使用できるグリッド数を求める手段と、分割したマンハッタン長領域の最短配線長でタイミング検証した結果のタイミング余裕度と配線に使用できるグリッド数から配線余裕度を求める手段と、配線余裕度をもとに優先配線指定する手段とを有するレイアウト方法ということもできる。
【００８１】
または、本発明の実施の形態１は、ピンペアのピンとピンを囲む最短矩形内の配線経路の組合せと配線リソースから配線集中度を求め、配線集中度とタイミング余裕度から配線順序を決定するレイアウト方法ということもできる。
【００８２】
特許文献１等では、実配線時に、タイミング的に余裕のない配線より、タイミング的に余裕のある配線が先に配線されることによって、配線リソースが消費されてしまう場合がある。それに対して、本発明の実施の形態１及び２では、概略配線処理で予め、局所的に配線が集中する領域で、配線領域が極端に狭くタイミング的に余裕のない配線を優先して配線指定することが可能となり、実配線時にタイミング的に余裕のない配線より、タイミング的に余裕のある配線が先に配線されることによって、配線リソースが消費されてしまうことを低減できる。
【００８３】
また、本発明の実施の形態２は、実施の形態１に加え、グリッドの使用確率と配線余裕度をもとに迂回配線指定する手段と、迂回配線指定した配線をグリッドの使用確率と分割したマンハッタン長領域から迂回配線検討領域を求める手段と、迂回配線検討領域から迂回配線経路を選択する手段と、選択した迂回配線経路で迂回配線検討領域の頂点に導きバッファを挿入する手段と、導きバッファを挿入した迂回経路に従ってＣＴＳ・詳細配線処理を実施する手段と、を有するレイアウト手法ということもできる。
【００８４】
または、本発明の実施の形態２は、配線領域をマンハッタン長領域に分割する手段と、分割したマンハッタン長領域内の最短ルート数を求める手段と、分割したマンハッタン長領域内の各グリッドを通過するルート数を求める手段と、分割したマンハッタン長領域内の最短ルート数と各グリッドを通過するルート数からグリッド使用確率を求める手段と、分割したマンハッタン長領域内の各グリッドのグリッド使用確率から配線に使用できるグリッド数を求める手段と、分割したマンハッタン長領域の最短配線長でタイミング検証した結果のタイミング余裕度と配線に使用できるグリッド数から配線余裕度を求める手段と、を有するレイアウト手法であってもよい。
【００８５】
または、本発明の実施の形態２は、前記最短矩形内の配線リソースが不足している場合、タイミング余裕度の大きなものから最短矩形を含む領域を広げ、矩形の交点にリピータを挿入するレイアウト手法であってもよい。
【００８６】
いずれにしても、概略配線処理で予め、局所的に配線が集中する領域で、タイミング的に余裕のある配線の迂回経路を策定することが可能となり、実配線時にタイミング的に余裕のある配線を局所的に混雑している箇所を迂回して配線させることで、タイミング的に余裕のない配線がタイミング的に余裕のある配線によって配線リソースが消費されてしまうことが低減できる。
【００８７】
尚、本発明の実施形態１及び２にかかる「グリッド」の代わりに、グリッド間の配線を用いて実施しても良い。または、グリッドと異なる格子状に区切られた点を用いて実施しても良い。さらに、本発明の実施形態１及び２にかかる「矩形領域」の代わりに、端子組における各端子間を配線可能な領域である配線領域を用いて実施しても良い。そして、配線領域は、複数の矩形領域を複数重ね合わせた領域或いは配線禁止領域等で欠けや抜けの領域があっても良い。
【００８８】
これらの場合、本発明の対象は、格子状に区切られた半導体集積回路といえる。そして、上述した本発明の実施形態１及び２におけるグリッド単位、グリッド数及びグリッド通過確率を、格子単位、格子数及び格子通過確率とそれぞれ言い換えることができる。
【００８９】
さらに、本発明は上述した実施の形態のみに限定されるものではなく、既に述べた本発明の要旨を逸脱しない範囲において種々の変更が可能であることは勿論である。本発明は、上述したように、任意の処理を、ＣＰＵ（Central Processing Unit）にコンピュータプログラムを実行させることにより実現することも可能である。この場合、コンピュータプログラムは、様々なタイプの非一時的なコンピュータ可読媒体（non-transitory computer readable medium）を用いて格納され、コンピュータに供給することができる。非一時的なコンピュータ可読媒体は、様々なタイプの実体のある記録媒体（tangible storage medium）を含む。非一時的なコンピュータ可読媒体の例は、磁気記録媒体（例えばフレキシブルディスク、磁気テープ、ハードディスクドライブ）、光磁気記録媒体（例えば光磁気ディスク）、ＣＤ−ＲＯＭ（Read Only Memory）、ＣＤ−Ｒ、ＣＤ−Ｒ／Ｗ、ＤＶＤ（Digital Versatile Disc）、ＢＤ(Blu-ray(登録商標) Disc)、半導体メモリ（例えば、マスクＲＯＭ、ＰＲＯＭ（Programmable ROM）、ＥＰＲＯＭ（Erasable PROM）、フラッシュＲＯＭ、ＲＡＭ（Random Access Memory））を含む。また、コンピュータプログラムは、様々なタイプの一時的なコンピュータ可読媒体（transitory computer readable medium）によってコンピュータに供給されてもよい。一時的なコンピュータ可読媒体の例は、電気信号、光信号、及び電磁波を含む。一時的なコンピュータ可読媒体は、電線及び光ファイバ等の有線通信路、又は無線通信路を介して、プログラムをコンピュータに供給できる。
【符号の説明】
【００９０】
１００  レイアウトシステム
１０１  サーバ装置
１０２  記憶装置
１０２１  レイアウトプログラム
１０３  ネットワーク
１０４ａ  コンピュータ装置
１０４ｂ  コンピュータ装置
１０４ｎ  コンピュータ装置
１０  レイアウト装置
１１０  ＣＰＵ
１２０  ＲＡＭ
１３０  ＲＯＭ
１４０  ＩＦ部
１５０  ハードディスク
１５１  ＯＳ
１５２  レイアウトプログラム
ＨＤ１０  配置情報
ＨＤ２０  グリッド情報
ＨＤ３０  グリッド使用確率情報
ＨＤ４０  タイミング検証結果
ＨＤ５０  優先配線情報
ＨＤ６０  迂回配線情報
ＡＲＥＡ＿Ａ  マンハッタン長領域
ＡＲＥＡ＿Ｂ  マンハッタン長領域
ＡＲＥＡ＿Ｃ  マンハッタン長領域
ＡＲＥＡ＿Ｄ  マンハッタン長領域
ＡＲＥＡ＿Ｅ  マンハッタン長領域
ＡＲＥＡ＿Ｆ  マンハッタン長領域
ＡＲＥＡ＿Ｘ  配線禁止領域
ＡＲＥＡ＿ＦＯＲＢ  迂回配線禁止外周領域
ＡＲＥＡ＿ＦＮ  迂回配線検討領域
Ａ０  始点端子座標
Ａ１  終点端子座標
Ｂ０  始点端子座標
Ｂ１  終点端子座標
Ｃ０  始点端子座標
Ｃ１  終点端子座標
Ｄ０  始点端子座標
Ｄ１  終点端子座標
Ｅ０  始点端子座標
Ｅ１  終点端子座標
Ｅ２  座標
Ｅ３  座標
Ｅ４  座標
Ｅ５  座標
Ｆ０  始点端子座標
Ｆ１  終点端子座標
ＦＢ０  座標
ＦＢ１  座標
【図１】
2012093824.tif 000003
【図２】
2012093824.tif 000004
【図３】
2012093824.tif 000005
【図４】
2012093824.tif 000006
【図５】
2012093824.tif 000007
【図６】
2012093824.tif 000008
【図７】
2012093824.tif 000009
【図８】
2012093824.tif 000010
【図９】
2012093824.tif 000011
【図１０】
2012093824.tif 000012
【図１１】
2012093824.tif 000013
【図１２】
2012093824.tif 000014
【図１３】
2012093824.tif 000015