JPH11204648A - 配線経路決定方法および遅延推定方法 - Google Patents
配線経路決定方法および遅延推定方法Info
- Publication number
- JPH11204648A JPH11204648A JP10004381A JP438198A JPH11204648A JP H11204648 A JPH11204648 A JP H11204648A JP 10004381 A JP10004381 A JP 10004381A JP 438198 A JP438198 A JP 438198A JP H11204648 A JPH11204648 A JP H11204648A
- Authority
- JP
- Japan
- Prior art keywords
- wiring
- capacity
- path
- graph
- estimating
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F30/00—Computer-aided design [CAD]
- G06F30/30—Circuit design
- G06F30/32—Circuit design at the digital level
- G06F30/33—Design verification, e.g. functional simulation or model checking
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F30/00—Computer-aided design [CAD]
- G06F30/30—Circuit design
- G06F30/32—Circuit design at the digital level
- G06F30/33—Design verification, e.g. functional simulation or model checking
- G06F30/3308—Design verification, e.g. functional simulation or model checking using simulation
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F30/00—Computer-aided design [CAD]
- G06F30/30—Circuit design
- G06F30/39—Circuit design at the physical level
- G06F30/394—Routing
Landscapes
- Engineering & Computer Science (AREA)
- Computer Hardware Design (AREA)
- Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Evolutionary Computation (AREA)
- Geometry (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Computer Networks & Wireless Communication (AREA)
- Design And Manufacture Of Integrated Circuits (AREA)
Abstract
(57)【要約】
【課題】 概略配線において、隣接配線の影響を考慮し
て配線容量を推定し、タイミングエラーがないよう配線
経路を決定する。 【解決手段】 対象とする集積回路から配線グラフを作
成し、この配線グラフ上で各辺に設定した通過コストを
基にセル間配線が通過する配線経路を初期決定する（Ｓ
２１）。配線グラフの各辺について当該辺を通過するセ
ル間配線の本数を配線混雑度として求め（Ｓ２２）、こ
の配線混雑度から、隣接配線の影響を考慮した各配線経
路の配線容量を推定する（Ｓ２３）。遅延を推定してタ
イミングエラーの有無を検証し（Ｓ２４，Ｓ２５）、前
記集積回路が所定のタイミング制約を満たさないとき
は、配線容量を各辺の通過コストに反映させた上で配線
経路を再決定する（Ｓ２６）。または配線層の割り当て
を変更（Ｓ３１）したり、配線間距離を拡張（Ｓ４１）
して、タイミング制約を満たすようにする。
て配線容量を推定し、タイミングエラーがないよう配線
経路を決定する。 【解決手段】 対象とする集積回路から配線グラフを作
成し、この配線グラフ上で各辺に設定した通過コストを
基にセル間配線が通過する配線経路を初期決定する（Ｓ
２１）。配線グラフの各辺について当該辺を通過するセ
ル間配線の本数を配線混雑度として求め（Ｓ２２）、こ
の配線混雑度から、隣接配線の影響を考慮した各配線経
路の配線容量を推定する（Ｓ２３）。遅延を推定してタ
イミングエラーの有無を検証し（Ｓ２４，Ｓ２５）、前
記集積回路が所定のタイミング制約を満たさないとき
は、配線容量を各辺の通過コストに反映させた上で配線
経路を再決定する（Ｓ２６）。または配線層の割り当て
を変更（Ｓ３１）したり、配線間距離を拡張（Ｓ４１）
して、タイミング制約を満たすようにする。
Description
【０００１】
【発明の属する技術分野】本発明は、集積回路のレイア
ウト設計技術に属するものであり、特にＡＳＩＣ等のセ
ミカスタムＬＳＩの概略配線における配線経路決定およ
び遅延推定を行う方法に属する。
ウト設計技術に属するものであり、特にＡＳＩＣ等のセ
ミカスタムＬＳＩの概略配線における配線経路決定およ
び遅延推定を行う方法に属する。
【０００２】
【従来の技術】 近年、半導体集積回路の
製造技術において、トランジスタおよび配線の微細化が
進展している。微細化の進展に伴い、トランジスタ自体
の遅延時間は減少する傾向にあるが、配線の微細化に起
因して隣接配線間の容量が増加するため、セルの出力負
荷容量は必ずしも減少せず、このため、集積回路全体の
遅延において、配線容量に依存する割合が相対的に増加
する傾向にある。
製造技術において、トランジスタおよび配線の微細化が
進展している。微細化の進展に伴い、トランジスタ自体
の遅延時間は減少する傾向にあるが、配線の微細化に起
因して隣接配線間の容量が増加するため、セルの出力負
荷容量は必ずしも減少せず、このため、集積回路全体の
遅延において、配線容量に依存する割合が相対的に増加
する傾向にある。
【０００３】そこで、近年の集積回路のレイアウト設計
では、動作タイミングを保証するために、隣接配線を考
慮した配線容量を精度良く見積もり、タイミング制約を
満たす配線経路を確実に決定する方法が必要になってい
る。
では、動作タイミングを保証するために、隣接配線を考
慮した配線容量を精度良く見積もり、タイミング制約を
満たす配線経路を確実に決定する方法が必要になってい
る。
【０００４】従来の配線経路決定方法としては、以下の
ようなものがあった。
ようなものがあった。
【０００５】第１の従来例としては、詳細配線によって
配線図形が生成され、配線が細部に至るまで決定された
後、配線毎に、隣接する配線図形を探索し、隣接配線間
に生じる配線容量を計算する方法があった（特開平６−
１２０３４３号公報参照）。
配線図形が生成され、配線が細部に至るまで決定された
後、配線毎に、隣接する配線図形を探索し、隣接配線間
に生じる配線容量を計算する方法があった（特開平６−
１２０３４３号公報参照）。
【０００６】第２の従来例としては、概略配線工程にお
いて、各配線の遅延時間を、単位長さ当たりの配線容量
（以下「単位容量」と略記する）が最大である配線層に
割り当てられた場合の配線容量と仮想配線長とを用いて
推定した上で、タイミング違反ネットを抽出し、このネ
ットを、タイミング制約を満たすよう他の配線層に割り
当てる方法があった（特開平５−１４３６９２号公報参
照）。
いて、各配線の遅延時間を、単位長さ当たりの配線容量
（以下「単位容量」と略記する）が最大である配線層に
割り当てられた場合の配線容量と仮想配線長とを用いて
推定した上で、タイミング違反ネットを抽出し、このネ
ットを、タイミング制約を満たすよう他の配線層に割り
当てる方法があった（特開平５−１４３６９２号公報参
照）。
【０００７】
【発明が解決しようとする課題】ところが、従来の配線
経路決定方法には、以下のような問題があった。
経路決定方法には、以下のような問題があった。
【０００８】まず前記第１の従来例によると、詳細配線
によって配線図形が細部に至るまで完全に生成された後
に隣接配線の影響を考慮して配線容量を計算するため、
タイミングエラーが存在するときに、配線の修正によっ
てタイミングエラーをなくすことはきわめて困難であっ
た。すなわち、配線の修正のために扱うデータ量が膨大
であり、処理時間が長くかかるとともに、場合によって
は、計算処理が収束せずに配線の修正が不可能であると
いうことが生じた。
によって配線図形が細部に至るまで完全に生成された後
に隣接配線の影響を考慮して配線容量を計算するため、
タイミングエラーが存在するときに、配線の修正によっ
てタイミングエラーをなくすことはきわめて困難であっ
た。すなわち、配線の修正のために扱うデータ量が膨大
であり、処理時間が長くかかるとともに、場合によって
は、計算処理が収束せずに配線の修正が不可能であると
いうことが生じた。
【０００９】また前記第２の従来例によると、違反ネッ
ト抽出において、配線は単位容量が最大である配線層に
割り当てられるものと仮定するため、配線容量推定が過
大になりがちであった。また、配線容量の推定に隣接配
線の存在が全く考慮されていないため、概略配線工程で
はタイミング違反がない場合であっても、詳細配線後
に、隣接配線の存在によってタイミングエラーが生じる
場合が多く、タイミングエラーをなくす修正のために、
ネットリストまで変更しなければならないという問題が
あった。
ト抽出において、配線は単位容量が最大である配線層に
割り当てられるものと仮定するため、配線容量推定が過
大になりがちであった。また、配線容量の推定に隣接配
線の存在が全く考慮されていないため、概略配線工程で
はタイミング違反がない場合であっても、詳細配線後
に、隣接配線の存在によってタイミングエラーが生じる
場合が多く、タイミングエラーをなくす修正のために、
ネットリストまで変更しなければならないという問題が
あった。
【００１０】前記の問題に鑑み、本発明は、概略配線に
おいて、隣接配線の影響を考慮して配線容量を推定した
上で、タイミングエラーがないように配線経路を決定す
る配線経路決定方法を提供することを課題とする。
おいて、隣接配線の影響を考慮して配線容量を推定した
上で、タイミングエラーがないように配線経路を決定す
る配線経路決定方法を提供することを課題とする。
【００１１】
【課題を解決するための手段】前記の課題を解決するた
めに、本発明は、概略配線において配線の混雑度から配
線の隣接する確率を予測するという点に新たに着目し
て、予測された隣接配線の確率から配線容量を推定して
遅延計算すると同時に、得られた遅延情報からタイミン
グ違反ネットの配線経路を決定するものである。
めに、本発明は、概略配線において配線の混雑度から配
線の隣接する確率を予測するという点に新たに着目し
て、予測された隣接配線の確率から配線容量を推定して
遅延計算すると同時に、得られた遅延情報からタイミン
グ違反ネットの配線経路を決定するものである。
【００１２】具体的に、請求項１の発明が講じた解決手
段は、セルレベルで設計された集積回路について、配置
されたセル間の配線経路を決定する配線経路決定方法と
して、集積回路の配線領域を複数の部分領域に分割し、
各部分領域に属するセル端子を一の頂点で表すとともに
隣接する頂点を辺で結ぶ配線グラフを作成し、この配線
グラフ上で、各辺に設定した通過コストを基に、セル間
配線が通過する配線経路を初期決定する概略配線工程
と、前記配線グラフの各辺について、当該辺を通過する
セル間配線の本数を配線混雑度として求める配線混雑度
推定工程と、前記配線グラフの各辺について、前記配線
混雑度推定工程において求めた配線混雑度から配線間距
離を求め、この配線間距離から配線容量を求めて、この
各辺の配線容量を基に、前記概略配線工程において初期
決定した各配線経路の配線容量を、当該配線経路を構成
する辺の配線容量を和することによって推定する配線容
量推定工程とを備え、前記配線容量推定工程において推
定した各配線経路の配線容量を基にして、各配線経路の
遅延時間を推定し、推定した遅延時間を基に、前記集積
回路が所定のタイミング制約を満たすよう、配線経路を
決定するものである。
段は、セルレベルで設計された集積回路について、配置
されたセル間の配線経路を決定する配線経路決定方法と
して、集積回路の配線領域を複数の部分領域に分割し、
各部分領域に属するセル端子を一の頂点で表すとともに
隣接する頂点を辺で結ぶ配線グラフを作成し、この配線
グラフ上で、各辺に設定した通過コストを基に、セル間
配線が通過する配線経路を初期決定する概略配線工程
と、前記配線グラフの各辺について、当該辺を通過する
セル間配線の本数を配線混雑度として求める配線混雑度
推定工程と、前記配線グラフの各辺について、前記配線
混雑度推定工程において求めた配線混雑度から配線間距
離を求め、この配線間距離から配線容量を求めて、この
各辺の配線容量を基に、前記概略配線工程において初期
決定した各配線経路の配線容量を、当該配線経路を構成
する辺の配線容量を和することによって推定する配線容
量推定工程とを備え、前記配線容量推定工程において推
定した各配線経路の配線容量を基にして、各配線経路の
遅延時間を推定し、推定した遅延時間を基に、前記集積
回路が所定のタイミング制約を満たすよう、配線経路を
決定するものである。
【００１３】請求項１の発明によると、概略配線工程に
おいて対象とする集積回路から作成した配線グラフにつ
いて、配線混雑度推定工程において、各辺を通過するセ
ル間配線の本数を配線混雑度として求める。そして配線
容量推定工程において、各辺の配線混雑度から配線間距
離を求め、この配線間距離から配線容量を求めて、前記
概略配線工程において初期決定した各配線経路の配線容
量を推定する。この配線容量を基に各配線経路の遅延時
間を推定し、推定した遅延時間を基に、前記集積回路が
所定のタイミング制約を満たすよう配線経路を決定する
ため、概略配線での経路探索結果から、配線混雑度によ
って隣接配線の影響を考慮して配線容量を推定した上
で、タイミングエラーがないように配線経路を決定する
ことができる。したがって、概略配線における経路探索
の際にタイミングエラーをある程度予測し回避すること
ができるので、膨大な配線図形の変更を伴う詳細配線後
のレイアウト変更を大幅に減らすことができる。
おいて対象とする集積回路から作成した配線グラフにつ
いて、配線混雑度推定工程において、各辺を通過するセ
ル間配線の本数を配線混雑度として求める。そして配線
容量推定工程において、各辺の配線混雑度から配線間距
離を求め、この配線間距離から配線容量を求めて、前記
概略配線工程において初期決定した各配線経路の配線容
量を推定する。この配線容量を基に各配線経路の遅延時
間を推定し、推定した遅延時間を基に、前記集積回路が
所定のタイミング制約を満たすよう配線経路を決定する
ため、概略配線での経路探索結果から、配線混雑度によ
って隣接配線の影響を考慮して配線容量を推定した上
で、タイミングエラーがないように配線経路を決定する
ことができる。したがって、概略配線における経路探索
の際にタイミングエラーをある程度予測し回避すること
ができるので、膨大な配線図形の変更を伴う詳細配線後
のレイアウト変更を大幅に減らすことができる。
【００１４】そして、請求項２の発明では、前記請求項
１の配線経路決定方法は、前記集積回路が所定のタイミ
ング制約を満たさないとき、前記配線グラフの各辺に設
定した通過コストに、前記配線容量推定工程において求
めた当該辺の配線容量をパラメータとして加え、前記配
線グラフ上で、各辺に設定した通過コストを基に、セル
間配線が通過する配線経路を再度決定する再概略配線工
程を実行するものとする。
１の配線経路決定方法は、前記集積回路が所定のタイミ
ング制約を満たさないとき、前記配線グラフの各辺に設
定した通過コストに、前記配線容量推定工程において求
めた当該辺の配線容量をパラメータとして加え、前記配
線グラフ上で、各辺に設定した通過コストを基に、セル
間配線が通過する配線経路を再度決定する再概略配線工
程を実行するものとする。
【００１５】請求項２の発明によると、再概略配線工程
において、タイミングエラーを起こす配線経路につい
て、配線容量がより小さい迂回経路が探索されるので、
タイミングエラーを効率よく回避することができる。
において、タイミングエラーを起こす配線経路につい
て、配線容量がより小さい迂回経路が探索されるので、
タイミングエラーを効率よく回避することができる。
【００１６】また、請求項３の発明では、前記請求項１
の配線経路決定方法において、前記配線グラフは、隣接
する各頂点間において、配線に使用可能な配線層にそれ
ぞれ対応する複数の辺が設定されたものであり、前記集
積回路が所定のタイミング制約を満たさないとき、タイ
ミング制約を満たさない配線経路を構成する辺を、同一
の頂点間を結び、かつ、単位容量がより小さい配線層に
対応する辺に変更する配線層変更工程を実行するものと
する。
の配線経路決定方法において、前記配線グラフは、隣接
する各頂点間において、配線に使用可能な配線層にそれ
ぞれ対応する複数の辺が設定されたものであり、前記集
積回路が所定のタイミング制約を満たさないとき、タイ
ミング制約を満たさない配線経路を構成する辺を、同一
の頂点間を結び、かつ、単位容量がより小さい配線層に
対応する辺に変更する配線層変更工程を実行するものと
する。
【００１７】請求項３の発明によると、配線層変更工程
において、タイミングエラーを起こす配線経路につい
て、単位容量がより小さい配線層が割り当てられるの
で、タイミングエラーを効率よく回避することができ
る。
において、タイミングエラーを起こす配線経路につい
て、単位容量がより小さい配線層が割り当てられるの
で、タイミングエラーを効率よく回避することができ
る。
【００１８】さらに、請求項４の発明では、前記請求項
１の配線経路決定方法は、前記集積回路が所定のタイミ
ング制約を満たさないとき、タイミング制約を満たさな
い配線経路について、この配線経路の配線と隣接配線と
の距離を、他の配線間距離よりも長く設定する配線間距
離拡張工程を実行するものとする。
１の配線経路決定方法は、前記集積回路が所定のタイミ
ング制約を満たさないとき、タイミング制約を満たさな
い配線経路について、この配線経路の配線と隣接配線と
の距離を、他の配線間距離よりも長く設定する配線間距
離拡張工程を実行するものとする。
【００１９】請求項４の発明によると、配線間距離拡張
工程において、タイミングエラーを起こす配線経路につ
いて、隣接配線との距離を他の配線間距離よりも長く設
定して配線容量をより小さくするので、タイミングエラ
ーを効率よく回避することができる。
工程において、タイミングエラーを起こす配線経路につ
いて、隣接配線との距離を他の配線間距離よりも長く設
定して配線容量をより小さくするので、タイミングエラ
ーを効率よく回避することができる。
【００２０】また、請求項５の発明が講じた解決手段
は、請求項１の配線経路決定方法に用いられる遅延推定
方法であり、セルレベルで設計された集積回路につい
て、配置されたセル間の配線遅延を推定する遅延推定方
法として、集積回路の配線領域を複数の部分領域に分割
し、各部分領域に属するセル端子を一の頂点で表すとと
もに隣接する頂点を辺で結ぶ配線グラフを作成し、この
配線グラフ上で、各辺に設定した通過コストを基に、セ
ル間配線が通過する配線経路を決定する概略配線工程
と、前記配線グラフの各辺について、当該辺を通過する
セル間配線の本数を配線混雑度として求める配線混雑度
推定工程と、前記配線グラフの各辺について、前記配線
混雑度推定工程において求めた配線混雑度から配線間距
離を求め、この配線間距離から配線容量を求めて、この
各辺の配線容量を基に、前記概略配線工程において決定
した各配線経路の配線容量を、当該配線経路を構成する
辺の配線容量を和することによって推定する配線容量推
定工程とを備え、前記配線容量推定工程において推定し
た各配線経路の配線容量を基にして、前記集積回路の遅
延を推定するものである。
は、請求項１の配線経路決定方法に用いられる遅延推定
方法であり、セルレベルで設計された集積回路につい
て、配置されたセル間の配線遅延を推定する遅延推定方
法として、集積回路の配線領域を複数の部分領域に分割
し、各部分領域に属するセル端子を一の頂点で表すとと
もに隣接する頂点を辺で結ぶ配線グラフを作成し、この
配線グラフ上で、各辺に設定した通過コストを基に、セ
ル間配線が通過する配線経路を決定する概略配線工程
と、前記配線グラフの各辺について、当該辺を通過する
セル間配線の本数を配線混雑度として求める配線混雑度
推定工程と、前記配線グラフの各辺について、前記配線
混雑度推定工程において求めた配線混雑度から配線間距
離を求め、この配線間距離から配線容量を求めて、この
各辺の配線容量を基に、前記概略配線工程において決定
した各配線経路の配線容量を、当該配線経路を構成する
辺の配線容量を和することによって推定する配線容量推
定工程とを備え、前記配線容量推定工程において推定し
た各配線経路の配線容量を基にして、前記集積回路の遅
延を推定するものである。
【００２１】請求項５の発明によると、概略配線工程に
おいて対象とする集積回路から作成した配線グラフにつ
いて、配線混雑度推定工程において、各辺を通過するセ
ル間配線の本数を配線混雑度として求める。そして配線
容量推定工程において、各辺の配線混雑度から配線間距
離を求め、この配線間距離から配線容量を求めて、前記
概略配線工程において初期決定した各配線経路の配線容
量を推定する。この配線容量を基に前記集積回路の遅延
を推定するため、概略配線での経路探索結果から、配線
混雑度によって隣接配線の影響を考慮して配線容量を推
定した上で、遅延推定を行うことができる。
おいて対象とする集積回路から作成した配線グラフにつ
いて、配線混雑度推定工程において、各辺を通過するセ
ル間配線の本数を配線混雑度として求める。そして配線
容量推定工程において、各辺の配線混雑度から配線間距
離を求め、この配線間距離から配線容量を求めて、前記
概略配線工程において初期決定した各配線経路の配線容
量を推定する。この配線容量を基に前記集積回路の遅延
を推定するため、概略配線での経路探索結果から、配線
混雑度によって隣接配線の影響を考慮して配線容量を推
定した上で、遅延推定を行うことができる。
【００２２】また、請求項６の発明では、前記請求項５
の遅延推定方法における配線グラフは、隣接する各頂点
間において、配線に使用可能な配線層にそれぞれ対応す
る複数の辺が設定されたものとする。
の遅延推定方法における配線グラフは、隣接する各頂点
間において、配線に使用可能な配線層にそれぞれ対応す
る複数の辺が設定されたものとする。
【００２３】
【発明の実施の形態】以下、本発明の一実施形態につい
て、図面を参照しながら説明する。
て、図面を参照しながら説明する。
【００２４】図１は集積回路のレイアウト設計における
処理の流れを示すフローチャートである。図１におい
て、Ｓ１１は対象とする集積回路について、各セルの接
続関係を記述するネットリストを作成するネットリスト
作成工程、Ｓ１２はネットリスト作成工程Ｓ１１におい
て作成したネットリストに記述された各セルを配置する
セル配置工程、Ｓ１３はセル配置工程Ｓ１２において配
置したセル間の配線経路を決定する配線経路決定工程、
Ｓ１４は詳細配線を行い配線図形を生成する詳細配線工
程、Ｓ１５は詳細配線工程Ｓ１４において生成した配線
図形から配線間の容量を計算する配線容量計算工程、Ｓ
１６は集積回路の遅延時間を計算する遅延時間計算工程
である。またＳ１７はタイミングエラーの有無を検証す
る工程であり、工程Ｓ１７においてタイミングエラーが
あると判断したときは、ネットリスト作成工程Ｓ１１ま
で戻って、レイアウト設計を始めからやりなおす。
処理の流れを示すフローチャートである。図１におい
て、Ｓ１１は対象とする集積回路について、各セルの接
続関係を記述するネットリストを作成するネットリスト
作成工程、Ｓ１２はネットリスト作成工程Ｓ１１におい
て作成したネットリストに記述された各セルを配置する
セル配置工程、Ｓ１３はセル配置工程Ｓ１２において配
置したセル間の配線経路を決定する配線経路決定工程、
Ｓ１４は詳細配線を行い配線図形を生成する詳細配線工
程、Ｓ１５は詳細配線工程Ｓ１４において生成した配線
図形から配線間の容量を計算する配線容量計算工程、Ｓ
１６は集積回路の遅延時間を計算する遅延時間計算工程
である。またＳ１７はタイミングエラーの有無を検証す
る工程であり、工程Ｓ１７においてタイミングエラーが
あると判断したときは、ネットリスト作成工程Ｓ１１ま
で戻って、レイアウト設計を始めからやりなおす。
【００２５】本発明の一実施形態に係る配線経路決定方
法は、図１に示す集積回路のレイアウト設計における配
線経路決定工程Ｓ１３を実行するものである。
法は、図１に示す集積回路のレイアウト設計における配
線経路決定工程Ｓ１３を実行するものである。
【００２６】図２は図１に示す集積回路のレイアウト設
計における配線経路決定工程Ｓ１３の処理の流れを示す
フローチャートであり、本実施形態に係る配線経路決定
方法を示すものである。図２において、Ｓ２１はセル間
配線が通過する配線経路を探索し、初期決定する概略配
線工程、Ｓ２２は配線混雑度を推定する配線混雑度推定
工程、Ｓ２３は工程Ｓ２２において求めた配線混雑度に
基づいて、各配線経路の配線容量を求める配線容量推定
工程、Ｓ２４は各配線経路の遅延時間を推定する遅延推
定工程、Ｓ２５はタイミングエラーの有無を検証する工
程、Ｓ２６は工程Ｓ２５において所定のタイミング制約
を満たさない配線経路があると判断したとき、セル間配
線が通過する配線経路を再度決定する再概略配線工程で
ある。なお、図２において一点鎖線で示した配線層変更
工程Ｓ３１および配線間距離拡張工程Ｓ４１については
後述する。
計における配線経路決定工程Ｓ１３の処理の流れを示す
フローチャートであり、本実施形態に係る配線経路決定
方法を示すものである。図２において、Ｓ２１はセル間
配線が通過する配線経路を探索し、初期決定する概略配
線工程、Ｓ２２は配線混雑度を推定する配線混雑度推定
工程、Ｓ２３は工程Ｓ２２において求めた配線混雑度に
基づいて、各配線経路の配線容量を求める配線容量推定
工程、Ｓ２４は各配線経路の遅延時間を推定する遅延推
定工程、Ｓ２５はタイミングエラーの有無を検証する工
程、Ｓ２６は工程Ｓ２５において所定のタイミング制約
を満たさない配線経路があると判断したとき、セル間配
線が通過する配線経路を再度決定する再概略配線工程で
ある。なお、図２において一点鎖線で示した配線層変更
工程Ｓ３１および配線間距離拡張工程Ｓ４１については
後述する。
【００２７】なお、図２に示す配線経路決定工程Ｓ１３
において、概略配線工程Ｓ２１以外の工程を省略する
と、従来の集積回路のレイアウト設計における処理の流
れと同様になる。また、概略配線工程Ｓ２１、配線混雑
度推定工程Ｓ２２、配線容量推定工程Ｓ２３および遅延
推定工程Ｓ２４によって、本実施形態に係る遅延推定方
法が構成されている。
において、概略配線工程Ｓ２１以外の工程を省略する
と、従来の集積回路のレイアウト設計における処理の流
れと同様になる。また、概略配線工程Ｓ２１、配線混雑
度推定工程Ｓ２２、配線容量推定工程Ｓ２３および遅延
推定工程Ｓ２４によって、本実施形態に係る遅延推定方
法が構成されている。
【００２８】本実施形態に係る配線経路決定方法および
遅延推定方法について、集積回路のレイアウト設計全体
と絡めて、具体的に説明する。
遅延推定方法について、集積回路のレイアウト設計全体
と絡めて、具体的に説明する。
【００２９】まず最初に、ネットリスト作成工程Ｓ１１
において、対象とするセルレベルで設計された集積回路
について、論理素子を含むセル間の接続関係を表現する
ネットリストを作成する。次にセル配置工程Ｓ１２にお
いて、ネットリスト作成工程Ｓ１１で作成したネットリ
ストに含まれるセルをレイアウト上に配置して、レイア
ウト図を作成する。
において、対象とするセルレベルで設計された集積回路
について、論理素子を含むセル間の接続関係を表現する
ネットリストを作成する。次にセル配置工程Ｓ１２にお
いて、ネットリスト作成工程Ｓ１１で作成したネットリ
ストに含まれるセルをレイアウト上に配置して、レイア
ウト図を作成する。
【００３０】以下、セル配置工程Ｓ１２で作成したレイ
アウト図に対して、配線経路決定工程Ｓ１３を実行す
る。
アウト図に対して、配線経路決定工程Ｓ１３を実行す
る。
【００３１】概略配線工程Ｓ２１において、まず、セル
配置工程Ｓ１２で作成したレイアウト図から配線グラフ
を作成する。図３は対象とする集積回路のレイアウト図
の一例であり、１０はチップ、１１はセル、１２はマク
ロセル、１３はボンディングパッドである。図３に示す
レイアウト図において、配線領域を分割線２１によって
複数の部分領域２２に分割する。そして図４のような、
各部分領域２２を頂点３１で表すとともに隣接する頂点
３１を辺３２で結ぶ配線グラフを作成する。図４に示す
ような配線グラフにおいて、頂点３１は対応する部分領
域２２に属するセル端子を表現するものとし、各セル端
子を接続する配線の経路すなわちセル間の配線経路は、
辺３２の組合せによって表現するものとする。
配置工程Ｓ１２で作成したレイアウト図から配線グラフ
を作成する。図３は対象とする集積回路のレイアウト図
の一例であり、１０はチップ、１１はセル、１２はマク
ロセル、１３はボンディングパッドである。図３に示す
レイアウト図において、配線領域を分割線２１によって
複数の部分領域２２に分割する。そして図４のような、
各部分領域２２を頂点３１で表すとともに隣接する頂点
３１を辺３２で結ぶ配線グラフを作成する。図４に示す
ような配線グラフにおいて、頂点３１は対応する部分領
域２２に属するセル端子を表現するものとし、各セル端
子を接続する配線の経路すなわちセル間の配線経路は、
辺３２の組合せによって表現するものとする。
【００３２】各辺３２には、配線長、配線方向および通
過配線本数をパラメータとした通過コストを設定する。
そして、各セル間配線が通過する配線経路は、当該配線
経路を構成する各辺３２の通過コストの総和が最小にな
るように、初期決定される。本実施形態では、例えば次
式で表される通過コストを各辺３２に設定するものとす
る。 通過コスト＝（配線長）×（配線方向係数）＋（通過配
線本数）
過配線本数をパラメータとした通過コストを設定する。
そして、各セル間配線が通過する配線経路は、当該配線
経路を構成する各辺３２の通過コストの総和が最小にな
るように、初期決定される。本実施形態では、例えば次
式で表される通過コストを各辺３２に設定するものとす
る。 通過コスト＝（配線長）×（配線方向係数）＋（通過配
線本数）
【００３３】上式において（配線長）は、当該辺がまた
がる部分領域２２の縦横の長さから決定される辺の長さ
で与えられる。また（配線方向係数）は、配線方向によ
って割り当てられる配線層が異なるため、各配線層にお
ける単位容量の違いを配線方向に応じて通過コストに反
映させるための係数である。例えば、垂直方向の配線層
の単位容量が水平方向の配線層の単位容量の１．２倍で
あるとき、（配線方向係数）として、水平方向の辺３２
の通過コストには１．０を、垂直方向の辺３２の通過コ
ストには１．２を設定する。なお、各方向において配線
層が複数ある場合は、各配線層の単位容量を平均した値
を基にして（配線方向係数）を設定する。また（通過配
線本数）は、配線経路探索の結果において各辺３２を通
過する配線の本数によって与える。
がる部分領域２２の縦横の長さから決定される辺の長さ
で与えられる。また（配線方向係数）は、配線方向によ
って割り当てられる配線層が異なるため、各配線層にお
ける単位容量の違いを配線方向に応じて通過コストに反
映させるための係数である。例えば、垂直方向の配線層
の単位容量が水平方向の配線層の単位容量の１．２倍で
あるとき、（配線方向係数）として、水平方向の辺３２
の通過コストには１．０を、垂直方向の辺３２の通過コ
ストには１．２を設定する。なお、各方向において配線
層が複数ある場合は、各配線層の単位容量を平均した値
を基にして（配線方向係数）を設定する。また（通過配
線本数）は、配線経路探索の結果において各辺３２を通
過する配線の本数によって与える。
【００３４】図４において、頂点ｖ１と頂点ｖ２を接続
する配線経路は、通過コストの総和が最小になるよう
に、例えば辺ｅ１，ｅ２，ｅ３の組み合わせからなるも
のと初期決定される。
する配線経路は、通過コストの総和が最小になるよう
に、例えば辺ｅ１，ｅ２，ｅ３の組み合わせからなるも
のと初期決定される。
【００３５】配線混雑度推定工程Ｓ２２において、概略
配線工程Ｓ２１における配線経路の初期決定の結果か
ら、各辺３２を通過するセル間配線の本数を、当該辺３
２についての配線混雑度として求める。そして配線容量
推定工程Ｓ２３において、配線グラフの各辺について、
配線混雑度推定工程Ｓ２２において求めた配線混雑度と
各部分領域２２の寸法とから、隣接配線間の平均距離を
求め、各配線経路における配線容量を推定する。
配線工程Ｓ２１における配線経路の初期決定の結果か
ら、各辺３２を通過するセル間配線の本数を、当該辺３
２についての配線混雑度として求める。そして配線容量
推定工程Ｓ２３において、配線グラフの各辺について、
配線混雑度推定工程Ｓ２２において求めた配線混雑度と
各部分領域２２の寸法とから、隣接配線間の平均距離を
求め、各配線経路における配線容量を推定する。
【００３６】図４の配線グラフにおいて、水平方向の配
線を表現する辺ｅ１を例にとると、辺ｅ１の配線混雑度
をｎ１とし、辺ｅ１に係る配線領域の垂直方向の長さを
Ｌ１とすると、辺ｅ１に係る配線間の平均距離はＬ１／
ｎ１となる。このようにして求めた配線間の平均距離を
基にして、図５に示すような予め表形式で記憶した配線
間距離と配線容量との関係から、各辺３２について配線
容量を設定する。そして各配線経路の配線容量を、各辺
３２に設定した配線容量の総和によって推定する。例え
ば、辺ｅ１，ｅ２，ｅ３からなる頂点ｖ１，ｖ２間の配
線経路の配線容量は、辺ｅ１，ｅ２，ｅ３それぞれの配
線容量を足しあわせることによって推定する。
線を表現する辺ｅ１を例にとると、辺ｅ１の配線混雑度
をｎ１とし、辺ｅ１に係る配線領域の垂直方向の長さを
Ｌ１とすると、辺ｅ１に係る配線間の平均距離はＬ１／
ｎ１となる。このようにして求めた配線間の平均距離を
基にして、図５に示すような予め表形式で記憶した配線
間距離と配線容量との関係から、各辺３２について配線
容量を設定する。そして各配線経路の配線容量を、各辺
３２に設定した配線容量の総和によって推定する。例え
ば、辺ｅ１，ｅ２，ｅ３からなる頂点ｖ１，ｖ２間の配
線経路の配線容量は、辺ｅ１，ｅ２，ｅ３それぞれの配
線容量を足しあわせることによって推定する。
【００３７】配線容量推定工程Ｓ２３において推定した
各配線経路の配線容量を用いて、遅延推定工程Ｓ２４に
おいて遅延計算を行い、工程Ｓ２５においてタイミング
エラーの有無を検証する。工程Ｓ２５においてタイミン
グエラーがあると判断したとき、配線経路を再度決定す
る再概略配線工程Ｓ２６を実行する。
各配線経路の配線容量を用いて、遅延推定工程Ｓ２４に
おいて遅延計算を行い、工程Ｓ２５においてタイミング
エラーの有無を検証する。工程Ｓ２５においてタイミン
グエラーがあると判断したとき、配線経路を再度決定す
る再概略配線工程Ｓ２６を実行する。
【００３８】再概略配線工程Ｓ２６では、前述の概略配
線工程Ｓ２１と同様に、配線グラフにおいて、各辺に設
定した通過コストを基に、セル間配線が通過する配線経
路を決定するが、配線容量推定工程Ｓ２３において求め
た各辺の配線容量を通過コストにパラメータとして加え
た上で、配線経路を決定するものとする。これにより、
経路探索の際に、配線容量がより小さくなるような配線
経路が選択される。
線工程Ｓ２１と同様に、配線グラフにおいて、各辺に設
定した通過コストを基に、セル間配線が通過する配線経
路を決定するが、配線容量推定工程Ｓ２３において求め
た各辺の配線容量を通過コストにパラメータとして加え
た上で、配線経路を決定するものとする。これにより、
経路探索の際に、配線容量がより小さくなるような配線
経路が選択される。
【００３９】再概略配線工程Ｓ２６によって新たな配線
経路が決定されると、配線混雑度推定工程Ｓ２２に戻
り、以下、タイミングエラーがなくなるまで工程Ｓ２２
〜Ｓ２６を繰り返し実行する。タイミングエラーがない
配線経路が決定されると、配線経路決定工程Ｓ１３を終
了する。
経路が決定されると、配線混雑度推定工程Ｓ２２に戻
り、以下、タイミングエラーがなくなるまで工程Ｓ２２
〜Ｓ２６を繰り返し実行する。タイミングエラーがない
配線経路が決定されると、配線経路決定工程Ｓ１３を終
了する。
【００４０】その後、図１に戻り、詳細配線工程Ｓ１４
において詳細配線を行い配線図形を生成し、配線容量計
算工程Ｓ１５において配線図形から配線容量を計算し、
さらに遅延時間計算工程Ｓ１６において遅延計算を実行
する。そして工程Ｓ１７において、タイミングエラーの
有無を検証する。ここで、タイミングエラーがあるとき
は、従来と同様にネットリスト作成工程Ｓ１１に戻って
元のネットリストを変更することになるが、本実施形態
では、配線経路決定工程Ｓ１３において、概略配線にお
いて配線容量を考慮した配線経路探索が実行されている
ので、タイミングエラーの数は従来よりも大幅に削減さ
れる。
において詳細配線を行い配線図形を生成し、配線容量計
算工程Ｓ１５において配線図形から配線容量を計算し、
さらに遅延時間計算工程Ｓ１６において遅延計算を実行
する。そして工程Ｓ１７において、タイミングエラーの
有無を検証する。ここで、タイミングエラーがあるとき
は、従来と同様にネットリスト作成工程Ｓ１１に戻って
元のネットリストを変更することになるが、本実施形態
では、配線経路決定工程Ｓ１３において、概略配線にお
いて配線容量を考慮した配線経路探索が実行されている
ので、タイミングエラーの数は従来よりも大幅に削減さ
れる。
【００４１】以上のように本実施形態によると、概略配
線工程Ｓ２１における経路探索結果から、配線容量推定
工程Ｓ２３において、配線混雑度推定工程Ｓ２２で求め
た配線混雑度によって隣接配線の影響を考慮して配線容
量を推定した上で、タイミングエラーがないように配線
経路を決定する。したがって、概略配線における経路探
索の際にタイミングエラーをある程度予測し回避するこ
とができるので、膨大な配線図形の変更を伴う詳細配線
後のレイアウト変更を大幅に減らすことができる。
線工程Ｓ２１における経路探索結果から、配線容量推定
工程Ｓ２３において、配線混雑度推定工程Ｓ２２で求め
た配線混雑度によって隣接配線の影響を考慮して配線容
量を推定した上で、タイミングエラーがないように配線
経路を決定する。したがって、概略配線における経路探
索の際にタイミングエラーをある程度予測し回避するこ
とができるので、膨大な配線図形の変更を伴う詳細配線
後のレイアウト変更を大幅に減らすことができる。
【００４２】また、再概略配線工程Ｓ２６において、タ
イミングエラーを起こす配線経路について、配線容量が
より小さい迂回経路が探索されるので、タイミングエラ
ーを効率よく回避することができる。
イミングエラーを起こす配線経路について、配線容量が
より小さい迂回経路が探索されるので、タイミングエラ
ーを効率よく回避することができる。
【００４３】（配線層変更工程Ｓ３１）また、配線グラ
フについて、隣接する頂点間において、使用可能な配線
層にそれぞれ対応させて複数の辺３２を設けてもかまわ
ない。
フについて、隣接する頂点間において、使用可能な配線
層にそれぞれ対応させて複数の辺３２を設けてもかまわ
ない。
【００４４】図６は概略配線工程Ｓ２１において作成す
る配線グラフの他の例を示す図である。図６において、
図４の配線グラフと異なるのは、各頂点３１を接続する
辺３２を、配線に使用可能な配線層にそれぞれ対応する
よう、複数本設けた点である。図６に示す配線グラフは
４層配線を前提としており、垂直および水平方向におい
て、それぞれ配線層の数が２であるものとしている。
る配線グラフの他の例を示す図である。図６において、
図４の配線グラフと異なるのは、各頂点３１を接続する
辺３２を、配線に使用可能な配線層にそれぞれ対応する
よう、複数本設けた点である。図６に示す配線グラフは
４層配線を前提としており、垂直および水平方向におい
て、それぞれ配線層の数が２であるものとしている。
【００４５】各辺３２には、配線長、配線層および通過
配線本数をパラメータとした通過コストを設定する。例
えば、次式で表される通過コストを各辺３２に設定する
ものとする。 通過コスト＝（配線長）×（配線層の単位容量）＋（通
過配線本数）
配線本数をパラメータとした通過コストを設定する。例
えば、次式で表される通過コストを各辺３２に設定する
ものとする。 通過コスト＝（配線長）×（配線層の単位容量）＋（通
過配線本数）
【００４６】上式において（配線長）は、当該辺がまた
がる部分領域２２の縦横の長さから決定される辺の長さ
で与えられる。また（配線層の単位容量）は、各辺３２
が対応する配線層の単位容量を与える。また（通過配線
本数）は、配線経路探索の結果において各辺３２を通過
する配線の本数によって与える。経路探索の結果、最も
通過コストの小さな配線経路が探索される。
がる部分領域２２の縦横の長さから決定される辺の長さ
で与えられる。また（配線層の単位容量）は、各辺３２
が対応する配線層の単位容量を与える。また（通過配線
本数）は、配線経路探索の結果において各辺３２を通過
する配線の本数によって与える。経路探索の結果、最も
通過コストの小さな配線経路が探索される。
【００４７】工程Ｓ２５においてタイミングエラーがあ
ると判断したとき、タイミング制約を満たさない配線経
路を構成する辺を、同一の頂点間を結び、かつ、単位容
量がより小さい配線層に対応する辺に変更する配線層変
更工程Ｓ３１を実行する。これにより、配線容量が小さ
くなるように配線層が選択された概略配線経路が選択さ
れるので、タイミングエラーを効率よく回避することが
できる。
ると判断したとき、タイミング制約を満たさない配線経
路を構成する辺を、同一の頂点間を結び、かつ、単位容
量がより小さい配線層に対応する辺に変更する配線層変
更工程Ｓ３１を実行する。これにより、配線容量が小さ
くなるように配線層が選択された概略配線経路が選択さ
れるので、タイミングエラーを効率よく回避することが
できる。
【００４８】なお、配線層変更工程Ｓ３１は、図２に示
すように再概略配線工程Ｓ２６の代わりに実行してもよ
いし、再概略配線工程Ｓ２６と併せて実行してもかまわ
ない。また例えば工程Ｓ２５においてタイミングエラー
があると判断したときに、まず配線層変更工程Ｓ３１を
実行し、これによりタイミングエラーが回避できないと
きに再概略配線工程Ｓ２６を実行するようにしてもよ
い。
すように再概略配線工程Ｓ２６の代わりに実行してもよ
いし、再概略配線工程Ｓ２６と併せて実行してもかまわ
ない。また例えば工程Ｓ２５においてタイミングエラー
があると判断したときに、まず配線層変更工程Ｓ３１を
実行し、これによりタイミングエラーが回避できないと
きに再概略配線工程Ｓ２６を実行するようにしてもよ
い。
【００４９】（配線間距離拡張工程Ｓ４１）また工程Ｓ
２５においてタイミングエラーがあると判断したとき、
所定のタイミング制約を満たさない配線経路について、
この配線と隣接配線との距離を、他の配線間距離よりも
長く設定する配線間距離拡張工程Ｓ４１を実行してもよ
い。
２５においてタイミングエラーがあると判断したとき、
所定のタイミング制約を満たさない配線経路について、
この配線と隣接配線との距離を、他の配線間距離よりも
長く設定する配線間距離拡張工程Ｓ４１を実行してもよ
い。
【００５０】すなわち配線間距離拡張工程Ｓ４１におい
て、図７に示すように、タイミング制約を満たさない配
線経路の配線４１とこの配線４１と隣接する配線４２と
の間隔を、通常の配線４２，４３同士の間隔Ｄ１よりも
大きい間隔Ｄ２に変更する。
て、図７に示すように、タイミング制約を満たさない配
線経路の配線４１とこの配線４１と隣接する配線４２と
の間隔を、通常の配線４２，４３同士の間隔Ｄ１よりも
大きい間隔Ｄ２に変更する。
【００５１】遅延推定工程Ｓ２４において、タイミング
制約を満たさない配線経路については、図５に示す配線
間距離と配線容量との関係を基に、配線間距離拡張工程
Ｓ４１で変更した配線間距離に応じて推定した配線容量
を用いて、遅延計算を実行する。
制約を満たさない配線経路については、図５に示す配線
間距離と配線容量との関係を基に、配線間距離拡張工程
Ｓ４１で変更した配線間距離に応じて推定した配線容量
を用いて、遅延計算を実行する。
【００５２】詳細配線工程Ｓ１４では、配線間距離拡張
工程Ｓ４１で変更した配線間距離に従って詳細配線を行
い、配線図形を生成する。隣接配線との距離が拡げられ
たことによって、当該配線の配線容量が小さくなるの
で、タイミング違反が解消される。
工程Ｓ４１で変更した配線間距離に従って詳細配線を行
い、配線図形を生成する。隣接配線との距離が拡げられ
たことによって、当該配線の配線容量が小さくなるの
で、タイミング違反が解消される。
【００５３】以上のように、配線間距離拡張工程Ｓ４１
において、タイミングエラーを起こす配線経路につい
て、隣接配線との距離を他の配線間距離よりも長く設定
して配線容量をより小さくするので、タイミングエラー
を効率よく回避することができる。
において、タイミングエラーを起こす配線経路につい
て、隣接配線との距離を他の配線間距離よりも長く設定
して配線容量をより小さくするので、タイミングエラー
を効率よく回避することができる。
【００５４】なお、配線間距離拡張工程Ｓ４１も配線層
変更工程Ｓ３１と同様に、図２に示すように再概略配線
工程Ｓ２６の代わりに実行してもよいし、再概略配線工
程Ｓ２６と併せて実行してもかまわない。また例えば工
程Ｓ２５においてタイミングエラーがあると判断したと
きに、まず配線間距離拡張工程Ｓ４１を実行し、これに
よりタイミングエラーが回避できないときに再概略配線
工程Ｓ２６を実行するようにしてもよい。
変更工程Ｓ３１と同様に、図２に示すように再概略配線
工程Ｓ２６の代わりに実行してもよいし、再概略配線工
程Ｓ２６と併せて実行してもかまわない。また例えば工
程Ｓ２５においてタイミングエラーがあると判断したと
きに、まず配線間距離拡張工程Ｓ４１を実行し、これに
よりタイミングエラーが回避できないときに再概略配線
工程Ｓ２６を実行するようにしてもよい。
【００５５】
【発明の効果】以上のように本発明によると、概略配線
における経路探索結果から、配線混雑度によって隣接配
線の影響を考慮して配線容量を推定した上で、タイミン
グエラーがないように配線経路を決定するため、概略配
線における経路探索の際にタイミングエラーをある程度
予測し回避することができるので、膨大な配線図形の変
更を伴う詳細配線後のレイアウト変更を大幅に減らすこ
とができる。
における経路探索結果から、配線混雑度によって隣接配
線の影響を考慮して配線容量を推定した上で、タイミン
グエラーがないように配線経路を決定するため、概略配
線における経路探索の際にタイミングエラーをある程度
予測し回避することができるので、膨大な配線図形の変
更を伴う詳細配線後のレイアウト変更を大幅に減らすこ
とができる。
【００５６】また、タイミングエラーを起こす配線経路
について、配線容量がより小さい迂回経路を探索した
り、単位容量がより小さい配線層を割り当てたり、また
は、隣接配線との距離を他の配線間距離よりも長く設定
したりすることによって、タイミングエラーを効率よく
回避することができる。
について、配線容量がより小さい迂回経路を探索した
り、単位容量がより小さい配線層を割り当てたり、また
は、隣接配線との距離を他の配線間距離よりも長く設定
したりすることによって、タイミングエラーを効率よく
回避することができる。
【図１】集積回路のレイアウト設計における処理の流れ
を示すフローチャートである。
を示すフローチャートである。
【図２】図１に示す集積回路のレイアウト設計における
配線経路決定工程Ｓ１３すなわち本発明の一実施形態に
係る配線経路決定方法を示すフローチャートである。
配線経路決定工程Ｓ１３すなわち本発明の一実施形態に
係る配線経路決定方法を示すフローチャートである。
【図３】集積回路のレイアウト図において、配線領域を
部分領域に分割した結果を示す図である。
部分領域に分割した結果を示す図である。
【図４】図３のレイアウト図から作成した配線グラフで
ある。
ある。
【図５】配線間距離と配線容量との関係を表形式で示す
図である。
図である。
【図６】配線グラフの他の例である。
【図７】配線間距離の拡張を示す図である。
１１ セル １２ マクロセル ２２ 部分領域 ３１，ｖ１，ｖ２ 頂点 ３２，ｅ１，ｅ２，ｅ３ 辺 ４１，４２，４３ 配線 Ｓ２１ 概略配線工程 Ｓ２２ 配線混雑度推定工程 Ｓ２３ 配線容量推定工程 Ｓ２６ 再概略配線工程 Ｓ３１ 配線層変更工程 Ｓ４１ 配線間距離拡張工程
───────────────────────────────────────────────────── フロントページの続き (51)Int.Cl.6 識別記号 ＦＩ Ｈ０１Ｌ 21/82 Ｃ
Claims (6)
- 【請求項１】 セルレベルで設計された集積回路につい
て、配置されたセル間の配線経路を決定する配線経路決
定方法であって、 集積回路の配線領域を複数の部分領域に分割し、各部分
領域に属するセル端子を一の頂点で表すとともに隣接す
る頂点を辺で結ぶ配線グラフを作成し、この配線グラフ
上で、各辺に設定した通過コストを基に、セル間配線が
通過する配線経路を初期決定する概略配線工程と、 前記配線グラフの各辺について、当該辺を通過するセル
間配線の本数を配線混雑度として求める配線混雑度推定
工程と、 前記配線グラフの各辺について、前記配線混雑度推定工
程において求めた配線混雑度から配線間距離を求め、こ
の配線間距離から配線容量を求めて、この各辺の配線容
量を基に、前記概略配線工程において初期決定した各配
線経路の配線容量を、当該配線経路を構成する辺の配線
容量を和することによって推定する配線容量推定工程と
を備え、 前記配線容量推定工程において推定した各配線経路の配
線容量を基にして、各配線経路の遅延時間を推定し、推
定した遅延時間を基に、前記集積回路が所定のタイミン
グ制約を満たすよう、配線経路を決定することを特徴と
する配線経路決定方法。 - 【請求項２】 請求項１記載の配線経路決定方法におい
て、 前記集積回路が所定のタイミング制約を満たさないと
き、 前記配線グラフの各辺に設定した通過コストに、前記配
線容量推定工程において求めた当該辺の配線容量をパラ
メータとして加え、前記配線グラフ上で、各辺に設定し
た通過コストを基に、セル間配線が通過する配線経路を
再度決定する再概略配線工程を実行することを特徴とす
る配線経路決定方法。 - 【請求項３】 請求項１記載の配線経路決定方法におい
て、 前記配線グラフは、隣接する各頂点間において、配線に
使用可能な配線層にそれぞれ対応する複数の辺が設定さ
れたものであり、 前記集積回路が所定のタイミング制約を満たさないと
き、 タイミング制約を満たさない配線経路を構成する辺を、
同一の頂点間を結び、かつ、単位容量がより小さい配線
層に対応する辺に変更する配線層変更工程を実行するこ
とを特徴とする配線経路決定方法。 - 【請求項４】 請求項１記載の配線経路決定方法におい
て、 前記集積回路が所定のタイミング制約を満たさないと
き、 タイミング制約を満たさない配線経路について、この配
線経路の配線と隣接配線との距離を、他の配線間距離よ
りも長く設定する配線間距離拡張工程を実行することを
特徴とする配線経路決定方法。 - 【請求項５】 セルレベルで設計された集積回路につい
て、配置されたセル間の配線遅延を推定する遅延推定方
法であって、 集積回路の配線領域を複数の部分領域に分割し、各部分
領域に属するセル端子を一の頂点で表すとともに隣接す
る頂点を辺で結ぶ配線グラフを作成し、この配線グラフ
上で、各辺に設定した通過コストを基に、セル間配線が
通過する配線経路を決定する概略配線工程と、 前記配線グラフの各辺について、当該辺を通過するセル
間配線の本数を配線混雑度として求める配線混雑度推定
工程と、 前記配線グラフの各辺について、前記配線混雑度推定工
程において求めた配線混雑度から配線間距離を求め、こ
の配線間距離から配線容量を求めて、この各辺の配線容
量を基に、前記概略配線工程において決定した各配線経
路の配線容量を、当該配線経路を構成する辺の配線容量
を和することによって推定する配線容量推定工程とを備
え、 前記配線容量推定工程において推定した各配線経路の配
線容量を基にして、前記集積回路の遅延を推定すること
を特徴とする遅延推定方法。 - 【請求項６】 請求項５記載の遅延推定方法において、 前記配線グラフは、隣接する各頂点間において、配線に
使用可能な配線層にそれぞれ対応する複数の辺が設定さ
れたものであることを特徴とする遅延推定方法。
Priority Applications (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP00438198A JP4037944B2 (ja) | 1998-01-13 | 1998-01-13 | 配線経路決定方法および遅延推定方法 |
| US09/227,858 US6292928B1 (en) | 1998-01-13 | 1999-01-11 | Line path determining method and delay estimating method |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP00438198A JP4037944B2 (ja) | 1998-01-13 | 1998-01-13 | 配線経路決定方法および遅延推定方法 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH11204648A true JPH11204648A (ja) | 1999-07-30 |
| JP4037944B2 JP4037944B2 (ja) | 2008-01-23 |
Family
ID=11582790
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP00438198A Expired - Fee Related JP4037944B2 (ja) | 1998-01-13 | 1998-01-13 | 配線経路決定方法および遅延推定方法 |
Country Status (2)
| Country | Link |
|---|---|
| US (1) | US6292928B1 (ja) |
| JP (1) | JP4037944B2 (ja) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6581195B2 (en) | 2000-11-09 | 2003-06-17 | Mitsubishi Denki Kabushiki Kaisha | Method and apparatus for extracting parasitic element of semiconductor circuit |
| CN111709205A (zh) * | 2020-05-29 | 2020-09-25 | 成都华微电子科技有限公司 | Fpga布线方法 |
Families Citing this family (10)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6523158B1 (en) * | 1999-10-12 | 2003-02-18 | Nec Corporation | Wiring designing method for semiconductor integrated circuit |
| JP4015807B2 (ja) * | 2000-11-28 | 2007-11-28 | Ｎｅｃエレクトロニクス株式会社 | タイミングドリブンレイアウト手法 |
| US7139992B2 (en) * | 2000-12-01 | 2006-11-21 | Sun Microsystems, Inc. | Short path search using tiles and piecewise linear cost propagation |
| US20020104061A1 (en) * | 2000-12-01 | 2002-08-01 | Sun Microsystems, Inc. | Systems and methods for linear minimal convolution |
| US6782520B1 (en) * | 2001-08-13 | 2004-08-24 | Cadence Design Systems, Inc. | IC layout system having separate trial and detailed routing phases |
| JP2003167935A (ja) * | 2001-12-03 | 2003-06-13 | Fujitsu Ltd | 配線経路決定装置、グループ決定装置、配線経路決定プログラム、およびグループ決定プログラム |
| US6792587B2 (en) * | 2002-01-28 | 2004-09-14 | Sun Microsystems, Inc. | 2.5-D graph for multi-layer routing |
| US6883156B1 (en) * | 2002-05-31 | 2005-04-19 | Mips Technologies, Inc. | Apparatus and method for relative position annotation of standard cell components to facilitate datapath design |
| US8635577B2 (en) * | 2012-06-01 | 2014-01-21 | International Business Machines Corporation | Timing refinement re-routing |
| US11080457B1 (en) * | 2020-03-18 | 2021-08-03 | Cadence Design Systems, Inc. | Layer assignment and routing based on resistance or capacitance characteristic |
Family Cites Families (11)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5402357A (en) | 1990-12-20 | 1995-03-28 | Vlsi Technology, Inc. | System and method for synthesizing logic circuits with timing constraints |
| JPH05143692A (ja) | 1991-11-25 | 1993-06-11 | Nec Corp | 概略経路決定処理方式 |
| JPH06120343A (ja) | 1992-10-08 | 1994-04-28 | Fujitsu Ltd | 配線容量演算装置及び配線容量算出方法 |
| US5461576A (en) | 1993-09-01 | 1995-10-24 | Arcsys, Inc. | Electronic design automation tool for the design of a semiconductor integrated circuit chip |
| US5629860A (en) * | 1994-05-16 | 1997-05-13 | Motorola, Inc. | Method for determining timing delays associated with placement and routing of an integrated circuit |
| JP3299842B2 (ja) * | 1994-05-19 | 2002-07-08 | 富士通株式会社 | 半導体集積回路の配置配線方法および装置 |
| US5774371A (en) * | 1994-08-03 | 1998-06-30 | Matsushita Electric Industrial Co., Ltd. | Semiconductor integrated circuit and layout designing method for the same |
| TW330342B (en) * | 1995-11-21 | 1998-04-21 | Matsushita Electric Industrial Co Ltd | Compacting method, compacting assembly, layout method, layout assembly, rough layout method and assembly |
| US5798936A (en) * | 1996-06-21 | 1998-08-25 | Avant| Corporation | Congestion-driven placement method and computer-implemented integrated-circuit design tool |
| US5987086A (en) * | 1996-11-01 | 1999-11-16 | Motorola Inc. | Automatic layout standard cell routing |
| US5984510A (en) * | 1996-11-01 | 1999-11-16 | Motorola Inc. | Automatic synthesis of standard cell layouts |
-
1998
- 1998-01-13 JP JP00438198A patent/JP4037944B2/ja not_active Expired - Fee Related
-
1999
- 1999-01-11 US US09/227,858 patent/US6292928B1/en not_active Expired - Fee Related
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6581195B2 (en) | 2000-11-09 | 2003-06-17 | Mitsubishi Denki Kabushiki Kaisha | Method and apparatus for extracting parasitic element of semiconductor circuit |
| CN111709205A (zh) * | 2020-05-29 | 2020-09-25 | 成都华微电子科技有限公司 | Fpga布线方法 |
Also Published As
| Publication number | Publication date |
|---|---|
| JP4037944B2 (ja) | 2008-01-23 |
| US6292928B1 (en) | 2001-09-18 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US6415422B1 (en) | Method and system for performing capacitance estimations on an integrated circuit design routed by a global routing tool | |
| JP3461443B2 (ja) | 半導体装置、半導体装置の設計方法、記録媒体および半導体装置の設計支援装置 | |
| JP4938696B2 (ja) | 半導体装置の設計プログラムおよび半導体装置の設計システム | |
| US20070256045A1 (en) | V-shaped multilevel full-chip gridless routing | |
| JP4037944B2 (ja) | 配線経路決定方法および遅延推定方法 | |
| JPH10270563A (ja) | 集積回路の自動概略配線方法 | |
| US7216325B2 (en) | Semiconductor device, routing method and manufacturing method of semiconductor device | |
| US7966597B2 (en) | Method and system for routing of integrated circuit design | |
| US6584607B2 (en) | Method of performing timing-driven layout | |
| CN101681391B (zh) | 用于计算详细可布线性估计的方法和装置 | |
| US6567954B1 (en) | Placement and routing method in two dimensions in one plane for semiconductor integrated circuit | |
| US20070022400A1 (en) | Method, program, and apparatus for designing layout of semiconductor integrated circuit | |
| JP2002259485A (ja) | Ｌｓｉ設計工程におけるｌｃｒ抽出方法及びｌｃｒ抽出を行うコンピュータプログラム | |
| JP2000172738A (ja) | Ｌｓｉの自動レイアウト方法 | |
| US8336001B2 (en) | Method for improving yield rate using redundant wire insertion | |
| JP3548398B2 (ja) | 概略経路決定方法および概略経路決定方式 | |
| JP2904270B2 (ja) | クロストークエラー抑制方式 | |
| JP5035434B2 (ja) | 半導体装置の設計支援プログラムおよび半導体装置の設計システム | |
| US6845346B1 (en) | Iterative method of parasitics estimation for integrated circuit designs | |
| JP3017170B2 (ja) | 半導体集積回路のレイアウト設計方法 | |
| JP3127877B2 (ja) | 配線容量算出装置 | |
| JPH10135339A (ja) | 自動配置配線方法 | |
| JP3544893B2 (ja) | 遅延制約を考慮したｌｓｉ配置方法およびシステム | |
| JP2005107556A (ja) | 半導体集積回路の配線処理方法 | |
| JP2002342401A (ja) | 半導体集積回路の自動配線装置とその配線方法及びコンピュータプログラム |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A621 | Written request for application examination |
Free format text: JAPANESE INTERMEDIATE CODE: A621 Effective date: 20040721 |
|
| A977 | Report on retrieval |
Free format text: JAPANESE INTERMEDIATE CODE: A971007 Effective date: 20050916 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20071009 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20071102 |
|
| R150 | Certificate of patent or registration of utility model |
Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20101109 Year of fee payment: 3 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20111109 Year of fee payment: 4 |
|
| LAPS | Cancellation because of no payment of annual fees |