JPH09246391A

JPH09246391A - 配線設計方法および配線設計装置

Info

Publication number: JPH09246391A
Application number: JP8049295A
Authority: JP
Inventors: Takayuki Yamauchi; 貴行山内
Original assignee: Sharp Corp
Current assignee: Sharp Corp
Priority date: 1996-03-06
Filing date: 1996-03-06
Publication date: 1997-09-19
Also published as: US5926397A

Abstract

(57)【要約】【課題】ＬＳＩ等の設計において、配線長を短くし、
かつ必要最低限の遅延調整素子を用いて遅延制御を実現
する。【解決手段】信号の供給源・供給先となるセルを配置
し（Ｓ１）、供給源と各供給先との間の経路上に必要最
低限の中継点を生成し（Ｓ３）、その経路に配線を施す
（Ｓ５）。配線の寄生成分（配線容量および配線抵抗）
を抽出し（Ｓ７）、その寄生成分に応じて中継点に挿入
する遅延調整素子（セル）を決定する（Ｓ８）。この決
定は、遅延調整素子のサイズが最小となるように行われ
る。決定された遅延調整素子を中継点に挿入する（Ｓ
９）。これにより、配線前に設けた中継点に挿入する遅
延調整素子のサイズを配線完了後に決定しているので、
全てのレイアウト（配置・配線）の結果の影響を考慮し
た遅延制御を、再配線を行うことなく実現することがで
きる。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、半導体集積回路、
プリント配線基板などの配線が施される電子回路部品の
設計において、信号伝搬遅延を制御しうる配線設計方法
および配線設計装置に関するものである。

【０００２】

【従来の技術】論理回路においては、信号伝搬遅延が適
切に制御されないと、回路動作を高速化することができ
ない。その典型的な例が、同期式回路におけるクロック
スキューの問題である。同期式回路では、クロック信号
が複数の素子の動作を同期させるが、クロック信号の供
給源から複数の供給先への信号伝搬遅延がそれぞれの供
給経路で異なる場合には、その差すなわちクロックスキ
ューにより回路の動作速度が低下したり、回路の正常な
動作が妨げられたりする。

【０００３】このような問題に対し、特開平６−２１５
０７１号公報には、配線長を制御するクロック配線設計
装置が開示されている。この装置は、図１６に示すよう
に、クロック信号の供給源となるクロックドライバ１０
１から供給先となる各ブロック１０２〜１０５までの配
線長が等しくなるように配線を決定している。

【０００４】一方、特開平６−８９９３８号公報には、
クロック信号の各供給経路における遅延時間差を吸収す
るように遅延時間を調整する方法が開示されている。こ
の方法では、図１７に示すように、クロック信号の供給
源１１１と、論理回路領域１１２に設けられた供給先と
なる各論理回路１１３〜１１６との間に、駆動能力を備
えた遅延調整回路１１７…が設けられている。また、こ
の方法では、予め設定された複数の遅延調整回路１１７
…から、シミュレーションにより遅延時間のずれがなく
なるような遅延調整回路１１７を特定するようになって
いる。

【０００５】ところで、従来は、例えば、図１８に示す
ような手順で回路設計が行われていた。

【０００６】まず、各セルを所望の位置に配置し（Ｓ１
０１）、遅延制御の対称となる信号について、信号の供
給源とセルとの間に配線を施す（Ｓ１０２）。次いで、
その他の配線必要な箇所に配線を施し（Ｓ１０３）、配
線の寄生成分を抽出する（Ｓ１０４）。さらに、配線が
完了した状態での信号遅延が設計通りに制御されている
か、信号のタイミングを検証する（Ｓ１０５）。ここ
で、タイミングの遅延が設計通りに制御されていない場
合は、抽出された寄生成分に基づいて配線が修正され
（Ｓ１０６）、再び寄生成分を抽出する（Ｓ１０４）。

【０００７】

【発明が解決しようとする課題】ところが、上記前者の
装置では、各配線長を等しくするために、ブロック１０
２への配線のように迂回する配線が必要となる。それゆ
え、電子回路部品の面積や消費電力が増加するという問
題がある。また、ＬＳＩ等においては、素子の微細化が
進んでいるため、配線抵抗や配線容量の影響が増大して
いる。したがって、配線抵抗や配線容量を考慮した遅延
モデルでは、配線長を等しくするだけでは正しく遅延を
制御することができない。さらに、他の配線結果によ
り、遅延の制御対象となる配線の容量が変化して遅延時
間が変わるとき、その誤差を調整することができない。

【０００８】一方、後者の方法では、予め設けられた複
数の遅延調整回路１１７…から最適な遅延調整回路１１
７を選択するので、他の配線結果の影響を考慮すること
ができる。しかしながら、遅延調整回路１１７と論理回
路１１３〜１１６とを別の領域に設けるため、それらの
間の配線が長くなり、配線に要する面積と配線容量が増
加するという問題がある。配線容量が多いほど駆動能力
の高い遅延調整回路１１７が必要となるため、配線容量
と遅延調整回路１１７の両者の負荷容量の影響により消
費電力の増加を招く。

【０００９】加えて、後者の方法では、上記のように、
固定化された複数の遅延調整回路１１７…から最適の遅
延調整回路１１７を選択するようになっているので、使
用されない遅延調整回路１１７…は無駄になってしま
う。複数の論理回路１１３〜１１６の個々に対し、選択
可能なように複数の遅延調整回路１１７…が設けられる
ので、論理回路が増加するほど無駄になる遅延調整回路
１１７…が多くなる。しかも、１つの遅延調整回路１１
７から複数の論理回路にクロック信号を供給する場合、
その間の経路における遅延時間差を調整することができ
ない。

【００１０】また、前記のような手順による回路設計で
は、一旦配線を行ってから、遅延制御が所望通りとなる
ように配線を修正する処理を繰り返して行う。したがっ
て、設計に手間がかかり、効率があまり良くなかった。

【００１１】本発明は、上記の事情に鑑みてなされたも
のであって、配線の前に寄生成分等の配線の影響を考慮
することにより、配線長を短くし、かつ必要最低限の遅
延調整回路を用いて遅延制御を実現することを目的とし
ている。

【００１２】

【課題を解決するための手段】本発明の第１の配線設計
方法または第１の配線設計装置は、上記の課題を解決す
るために、信号の供給源および供給先となる素子を配置
し、配置された供給源の素子と各供給先の素子との間に
配線を施す方法または装置において、（１）配置された
供給源の素子から供給先の素子へ至る配線予定経路を決
定するとともに、その経路に施されるべき配線の配線抵
抗および配線容量の予測に基づいて上記経路の途中に中
継点を設定し、（２）配線前に各配線予定経路における
信号の遅延時間を調整する遅延調整素子を挿入するため
の領域を調整すべき遅延時間に応じた大きさに上記中継
点に確保するという、（１）および（２）の各工程また
は各手段を備えていることを特徴としている。

【００１３】第１の配線設計方法または装置では、配線
予定経路上に中継点が設定され、その中継点に遅延調整
素子の配置用の領域が確保された後に配線が行われる。
これにより、配線後の配線抵抗および配線容量が中継点
の設定時における予測と異なる場合、遅延調整素子の大
きさを配線後の配線抵抗および配線容量に応じて設定す
ることにより、素子の再配置または素子間の再配線を行
うことなく、配線抵抗および配線容量の配線前後の差に
よる影響をなくすことができる。それゆえ、配線前に設
定した配線における遅延時間を配線後にも維持すること
ができる。

【００１４】上記の第１の配線設計方法または装置は、
好ましくは、（１）の工程または手段が、配線予定経路
上に中継点の候補位置を設定し、各候補位置について目
標とする遅延制御の達成度合いを評価するとともに最良
の評価が得られた候補位置を中継点として選出する工程
または手段を有している。これにより、遅延時間の短縮
や各経路間の遅延時間を等しくするといった特定の目標
について遅延制御を行うことができる。また、遅延制御
の評価の高い有効な中継点が選出されるので、中継点の
数が必要最小限に制限される。

【００１５】また、最良の評価が得られた候補位置が複
数存在する場合、中継点の大きさが最小になる候補位置
を中継点として選出すれば、遅延調整素子の挿入用に確
保される領域が小さくなる。

【００１６】上記の第１の配線設計方法または装置は、
好ましくは、素子の配置結果に基づいて配線密度を算出
し、（２）の工程または手段が、遅延調整素子の配置用
の領域を配線密度に応じた大きさに確保する。これによ
り、配線密度により決まる配線間の容量を考慮した大き
さの領域を確保することができる。それゆえ、配線間の
容量に基づく遅延時間を領域の大きさに反映させること
ができる。

【００１７】上記の第１の配線設計方法または装置は、
好ましくは、（１）の工程または手段が、供給先の素子
を特定の属性に基づいてグループ化し、供給源の素子と
各グループとの間に配線予定経路を決定する。これによ
り、配線数が多くなっても、供給先の素子がグループ化
されているので、供給先の素子単位で中継点を決定する
場合に比べて中継点の決定数を少なくすることができ
る。

【００１８】また、上記のグループ化において、１つの
グループの負荷容量が許容値を越えないように制限すれ
ば、グループ内での配線長を短く抑えることができる。

【００１９】本発明の第２の配線設計方法または第２の
配線設計装置は、上記の課題を解決するために、信号の
供給源および供給先となる素子を配置し、配置された供
給源の素子と各供給先の素子との間に配線を施す方法ま
たは装置において、（１）配置された供給源の素子から
供給先の素子へ至る配線予定経路を決定するとともに、
その経路に施されるべき配線の配線抵抗および配線容量
の予測に基づいて上記経路の途中に中継点を設定し、
（２）配線前に各配線予定経路における信号の遅延時間
を調整する遅延調整素子を挿入するための領域を調整す
べき遅延時間に応じた大きさに上記中継点に確保し、
（３）配線後の配線容量および配線抵抗を抽出し、
（４）抽出された配線容量および配線抵抗に基づいて、
与えられた信号遅延時間の制約を満たし得る遅延調整素
子を決定して上記中継点に挿入するという、（１）ない
し（４）の各工程または各手段を備えていることを特徴
としている。

【００２０】第２の配線設計方法または装置では、遅延
調整素子のパラメータを配線後の配線抵抗および配線容
量に応じた値に設定することにより、配線後に抽出され
た配線容量および配線抵抗に基づいて、与えられた信号
遅延時間の制約を満たし得る遅延調整素子を決定するの
で、配線抵抗および配線容量が中継点の設定時における
予測と異なっても、素子や配線のレイアウトを変更する
ことなく、配線抵抗および配線容量の配線前後の差によ
る影響をなくすことができる。それゆえ、配線前に設定
した配線における遅延時間を配線後にも維持することが
できる。

【００２１】上記の第２の配線設計方法または装置は、
好ましくは、（１）の工程または手段が、抽出された配
線抵抗および配線容量に基づき、各中継点について目標
とする遅延制御の達成度合いを評価し、各中継点につい
ての最良の評価に基づいて遅延調整素子の大きさを設定
する。これにより、遅延時間の短縮や各経路間の遅延時
間を等しくするといった特定の目標について最も望まし
い遅延制御を行うことができる。

【００２２】

【発明の実施の形態】本発明の実施の一形態について図
１ないし図１５に基づいて説明すれば、以下の通りであ
る。

【００２３】本実施の形態に係る配線設計装置は、図５
に示すように、配線系１と、中継点挿入系２とを備えて
いる。配線系１は、セル（素子）の配置からセル間の配
線までを担う一方、中継点挿入系２は、仮配線の段階で
中継点を設定し、その中継点に適当な遅延調整素子を挿
入することにより遅延制御を担う。

【００２４】上記のセルは、信号の供給源となる供給源
セルと、信号の供給先となる供給先セルとである。供給
源セルは、クロックなどの同期信号を発生する回路素子
であり、供給先セルは、同期信号に基づいて動作するフ
リップフロップなどの最小の単位の回路素子である。

【００２５】また、本配線設計装置は、データベース３
・４と、入力部５と、制御部６とを備えている。

【００２６】データベース３は、配置・配線処理を行う
ために必要なレイアウト情報を全て格納している。その
情報は、配置・配線対象となるセルの接続情報、配線情
報、配線の容量や抵抗に関する情報などである。

【００２７】データベース４は、信号伝搬遅延制御を行
うために必要な情報を全て格納している。その情報は、
遅延制御対象となる信号、目的とする制御方式に関する
情報、供給先セルのグループ化に関する情報、中継点の
位置やサイズに関する情報、供給先の遅延値の情報など
である。これらの情報は、入力部５を介して予めデータ
ベース４に入力されている。

【００２８】制御部６は、配線系１および中継点挿入系
２における後述する各部による処理の実行や、その各部
とデータベース３・４との間のデータの入出力を制御す
るようになっている。

【００２９】配線系１は、配置部１１、配線密度算出部
１２、配線部１３および寄生成分抽出部１４を備えてい
る。

【００３０】配置部１１は、信号の供給源となるセルと
信号の供給先となるセルとを予め定められた配置・接続
情報に基づいて配置するようになっている。配置部１１
は、ＳＡ（Simmulated Annealing）法、二次計画法、Mi
n-Cut 法、ペア交換法などの既存の手法を用いてセルの
配置を行う。

【００３１】配線密度算出部１２は、配置部１１により
配置されたセル間に上記の配置・接続情報に基づいて配
線可能領域において仮の配線を行い、配線可能領域の各
ブロックを通過する配線密度を算出するようになってい
る。

【００３２】大規模ＬＳＩの配線工程においては、大ま
かな配線経路を概略配線により決定し、その配線経路に
おいて他の配線や素子との間の設計規則を満たすように
最終的な配線経路を決定する二段階配線手法がよく用い
られる。上記概略配線では、全体を格子状の領域に分割
し、各配線がどの領域を通過するかが決定される。配線
密度算出部１２は、この手法を用いることにより、領域
の大きさに対して通過する配線の本数を求めるようにな
っている。

【００３３】配線部１３は、後述する中継点領域確保部
２６により中継点を挿入するための領域が確保される
と、配置・接続情報に基づいてセル間の配線を行うよう
になっている。

【００３４】寄生成分抽出部１４は、配線後の寄生容量
（配線抵抗や配線容量）を抽出するようになっている。

【００３５】中継点挿入系２は、中継点生成部２１、供
給先グループ化部２２、コスト算出部２３、遅延計算部
２４、サイズ算出部２５、中継点領域確保部２６および
中継点セル挿入部２７を備えている。

【００３６】中継点生成部２１は、供給先グループ化部
２２、コスト算出部２３、遅延計算部２４およびサイズ
算出部２５の処理結果に基づいて、配線密度算出部１２
による仮の配線において、最適な遅延値を与える中継点
を予想して生成するようになっている。具体的には、次
のような処理を行う。

【００３７】（21-1）供給源セルから、供給先グループ
化部２２により後述のように形成された供給先セルのグ
ループまでの経路を決定する。（21-2）中継点の挿入候補位置を生成する。（21-3）生成した挿入候補位置から遅延制御に有効な箇
所を選択し、その箇所に挿入する中継点を決定する。

【００３８】供給先グループ化部２２は、供給先のセル
を、分布状態、遅延制御条件などの特定の条件（属性）
に基づいてグループ化するようになっている。グループ
化は、例えば、図６（ａ）ないし（ｃ）に示すように行
われる。

【００３９】まず、図６（ａ）に示すように、１つの供
給源セルｕと、複数の供給先セルｖ…とが配置された領
域において、１つの供給先セルｖを取り出す。この供給
先セルｖすなわち抽出セルｐを核としてグループＧ_iを
形成する。図６（ｂ）に示すように、他のグループにつ
いても、抽出セルｐを核として同様にグループＧ_iを形
成する。グループ化が完了すると、各供給先セルｖ…
は、図６（ｃ）に示すように、グループｇ₁・ｇ₂…と
してグループ単位で扱われるようになる。

【００４０】上記の供給先セルｖの取り出し方として
は、次のような方法があり、供給先セルｖ…の分布状態
に応じて適当な方法を用いる。

【００４１】（22-1）供給源セルｕに最も近い供給先セ
ルｖを選ぶ方法この方法では、供給先セルｖ…が供給源セルｕに近い領
域に片寄って分布している場合、供給源セルｕに最も近
い供給先セルｖを取り出す。これにより、この供給先セ
ルｖの周辺に配置されている供給先セルｖ…、すなわち
配線遅延の影響が小さい供給先セルｖ…が優先的にグル
ープ化される。この結果、供給源セルｕから離れた位置
で分散している供給先セルｖ…が供給源セルｕに近いグ
ループと異なるグループを形成しやすくなる。

【００４２】（22-2）供給源セルｕに最も遠い供給先セ
ルｖを選ぶ方法この方法では、供給先セルｖ…が供給源セルｕに遠い領
域に片寄って分布している場合、供給源セルｕに最も遠
い供給先セルｖを取り出す。これにより、この供給先セ
ルｖの周辺に配置されている供給先セルｖ…、すなわち
配線遅延の影響が大きい供給先セルｖ…が優先的にグル
ープ化される。この結果、供給源セルｕから離れた位置
で互いに近接している供給先セルｖ…が同じグループを
形成しやすくなる。

【００４３】（22-3）乱数を用いて供給先セルｖを選ぶ
方法この方法では、供給先セルｖ…が供給源セルｕに対しほ
ぼ均一に分布している場合、乱数を用いて供給先セルｖ
を取り出す。これにより、グループの位置が部分的に集
中せず、図６（ａ）に示すように、グループ化された供
給先セルｖ…を包含する最小矩形Ｒ_iで表されるグルー
プの領域の大きさのばらつきが少なくなる。

【００４４】（22-4）遅延制御条件に従って供給先セル
ｖを選ぶ方法この方法では、すでに形成されたグループとの遅延時間
の差が最も少なくなる要求のある特定の供給先セルｖを
取り出す。これにより、遅延時間の差が少なくなるグル
ープが優先して形成される。

【００４５】このように、セルの分布状態や遅延制御条
件に応じて最適なセル抽出方法を用いることにより、セ
ルの配置方法に依存せずに効果的な遅延制御が可能にな
る。

【００４６】コスト算出部２３は、中継点生成部２１に
より生成された中継点の挿入候補位置から遅延制御に有
効な箇所を選択するために、次のようなコスト式を用い
て各候補位置を評価するようになっている。コスト式
は、目的とする遅延制御の達成度合いを表し、コスト式
の演算結果であるコスト値が小さいほど、その候補位置
の評価が高くなる。

【００４７】なお、以下の各コスト式においては、供給
源セルからグループへの最大の遅延値をｄ_max、最小の
遅延値をｄ_min、Ｆをコスト値、α・β・γを定数、Ｓ
を中継点のサイズの総和としている。

【００４８】（23-1）Ｆ＝ｄ_max−ｄ_min このコスト式によれば、全ての供給先セル間の遅延時間
の差を小さくすることができる。

【００４９】（23-2）Ｆ＝（ｄ_max−ｄ_min）×ｄ_min このコスト式によれば、全ての供給先セル間の遅延時間
の差を小さくし、かつ遅延時間を小さくすることができ
る。

【００５０】（23-3）Ｆ＝α×（ｄ_max−ｄ_min）＋β×ｄ_min このコスト式によれば、遅延時間を等しくするという要
求と、遅延時間を小さくするという要求に優先順位があ
る場合、αおよびβを適宜設定することにより、いずれ
かをどの程度優先させるかを重み付けすることができ
る。例えば、αの値を大きくしβの値を小さくすれば、
遅延時間のばらつきをなくすことが優先されるが、ばら
つきが同じであれば遅延時間を小さくすることができ
る。

【００５１】（23-4）Ｆ＝α×（ｄ_max−ｄ_min）＋β
×ｄ_min＋γ×Ｓこのコスト式によれば、（23-3）のコスト式に加えて中
継点の設定数を制御することができる。γを大きくすれ
ば、中継点のサイズの総和を小さくするという要求を優
先させ、中継点が無制限に決定されるという不都合を防
止することができる。

【００５２】その他、特定の供給先セル間の遅延時間の
みを用いたコスト式を定めて、必要のある供給先セル間
の制御条件を考慮することもできる。例えば、特定の供
給先セル間の遅延時間の差のみを小さくしたい場合に
は、その遅延時間差を含むコスト式を用いれば、より少
ない中継点で遅延を制御することができる。

【００５３】このように、コスト式の定義を適宜設定す
ることにより、種々の条件に対する遅延制御が可能にな
る。

【００５４】遅延計算部２４は、コスト式の演算に用い
るための遅延時間を計算するようになっている。サイズ
算出部２５は、コスト式の演算に用いるための中継点の
サイズまたは中継点に挿入される遅延調整素子のサイズ
を算出するようになっている。

【００５５】中継点領域確保部２６は、中継点生成部２
１により生成された中継点に後述する遅延調整素子を挿
入するための領域を確保するようになっている。領域の
大きさは、調整すべき遅延時間に応じた面積に設定され
るが、具体的には、後述のようにして各中継点について
求められたサイズに、配線後の遅延調整のための余裕が
加えられている。また、中継点領域確保部２６は、領域
がすでに他のセルで占められている場合には、そのセル
を移動させて遅延調整素子の挿入が可能となるように領
域を確保する。

【００５６】中継点セル挿入部２７は、最終的に中継点
に挿入する遅延調整素子（セル）が決定すると、そのセ
ルを中継点に挿入するようになっている。

【００５７】上記のように構成される配線設計装置によ
る遅延制御の手順を図１ないし図４のフローチャートを
参照して説明する。

【００５８】まず、配置部１１により供給源セルおよび
供給先セルの配置が行われ（Ｓ１）、配線密度算出部１
２により、仮の配線が施されるとともに、その配線につ
いての配線密度が算出される（Ｓ２）。配線密度により
配線間の容量が異なることから、ここで配線密度を求め
ておくことにより、中継点領域確保部２６が確保する領
域をその容量を考慮した必要最小限の大きさに確保する
ことができる。

【００５９】次いで、中継点生成部２１により、供給源
セルと供給先セルとの間の配線経路が決定され、併せ
て、供給先グループ化部２２、コスト算出部２３、遅延
計算部２４およびサイズ算出部２５に基づいて配線経路
において中継点が生成される（Ｓ３）。中継点が生成さ
れると、中継点領域確保部２６により、生成された中継
点に遅延調整素子を挿入するための領域が確保される
（Ｓ４）。

【００６０】その後、配線部１１により、遅延制御の対
象となる信号についての配線が中継点の生成において決
定された配線経路にしたがって行われ（Ｓ５）、続いて
残りの配線も行われる（Ｓ６）。配線が完了すると、寄
生成分抽出部１４により配線容量や配線抵抗が寄生成分
として抽出される（Ｓ７）。

【００６１】さらに、上記の寄生成分とデータベース３
に格納された供給経路情報とにより、中継点に挿入する
遅延制御素子（セル）のパラメータを決定する（Ｓ
８）。そして、そのパラメータを持つ遅延制御素子をデ
ータベース４に設けられたライブラリから選んで、中継
点に挿入する（Ｓ９）。

【００６２】ところで、前記のＳ３における中継点の生
成は、図２に示すフローチャートの手順で行われる。

【００６３】最初に、供給先グループ化部２２により、
供給先セルのグループ化が行われる（Ｓ１１）。する
と、中継点生成部２１により、供給源セルから確定した
グループまでの経路が決定され（Ｓ１２）、中継点を挿
入する候補位置が生成されて（Ｓ１３）、さらに中継点
が決定される（Ｓ１４）。

【００６４】上記のＳ１１におけるグループ化の処理
は、具体的には、図３のフローチャートの手順で行われ
る。その手順を図６を用いながら詳細に説明する。

【００６５】まず、全要素（供給先セル）の集合をＤと
し、ｉ番目のグループをＧ_iで表し、ｉを１に初期化し
ておくことにより、１番目のグループから順にグループ
を形成する（Ｓ２１）。この状態で、図６（ａ）に示す
ように、前述のような方法でＤから要素を１つ取り出し
てｐとすることで（Ｓ２２）、Ｄからｐを除き、Ｇ_ｉに
グループの核となるｐを加える（Ｓ２３）。

【００６６】次いで、Ｄの各要素についてＧ_ｉとの距
離を求め、Ｇ_iに属するいずれかの要素との距離が最短
となる要素をｑとして取り出す（Ｓ２４）。このとき、
図６（ａ）にて破線で囲まれた構成途中のＧ_iに最も近
いｑが選ばれる。そして、Ｇ_iに属する全要素とこのｑ
とを包含する最小矩形Ｒ_iを求める（Ｓ２５）。このと
き、Ｒ_iの周囲長をＬとしておく。

【００６７】続いて、グループＧ_iの負荷容量を算出す
る（Ｓ２６）。配線密度が高い箇所では配線間隔が狭い
ために単位長さ当たりの配線容量が増加し、配線密度が
低い箇所では単位長さ当たりの配線容量が減少するの
で、ここで、以前に求めておいた配線密度を用いて単位
長さ当たりの配線容量を決定する。そして、その配線容
量を加えて負荷容量を算出する。

【００６８】さらに、Ｇ_iの負荷容量が予め定められた
許容値を越えるか否かを判定し（Ｓ２７）、越える場合
は、Ｄが空であるか否かを確認する（Ｓ２８）。許容値
は、例えば、グループ内の配線を行うときに、グループ
の大きさがグループ内での配線遅延の影響を無視できる
ような値に設定されている。

【００６９】そして、図６（ｂ）に示すように、Ｄが空
である場合は、グループの構築を終え、全てのグループ
の位置を決めて（Ｓ２９）、処理を完了する。ここで、
グループの位置は、図６（ｃ）に示すように、グループ
内の各要素の負荷を重さと見なしたときの重心位置とし
ている。

【００７０】また、Ｓ２７において、Ｇ_iの負荷容量が
許容値を越えない場合は、ｑをＧ_iに加え、Ｄからｑを
除いて（Ｓ３０）、処理をＳ２４に戻す。一方、Ｓ２８
において、Ｄが空でない場合は、次のグループの構築に
移行するためにｉをｉ＋１として（Ｓ３１）、処理をＳ
２２に戻す。

【００７１】上記のように、遅延時間の精度上無視でき
る供給先セルの集合をグループに分けることにより、後
の中継点挿入処理の効率化を図ることができる。また、
負荷容量の許容値によってグループの大きさが制限され
るので、グループ内の配線長が短く抑えられる。これに
より、グループ内に限定すれば、配線長をそろえる従来
の制御方法も配線長があまり増大しないので有効な方法
となる。さらに、グループ内で正確な制御を行う場合に
は、グループ化と従来の配線長制御技術とを組み合わせ
ることも可能である。

【００７２】前記のＳ１３における中継点挿入候補位置
生成の処理は、具体的には、次のようにして行われる。
まず、図７に示すように、供給源セルｕから各グループ
ｇ₁〜ｇ₄までの経路を×で表される分岐点により配線
セグメントＷ…に分割する。すなわち、配線セグメント
Ｗは、供給源セルｕと分岐点との間の経路および分岐点
とグループｇ₁〜ｇ₄との間の経路になる。また、図８
（ａ）に示すように、配線セグメントＷの両端点のう
ち、供給源セルｕに近い方を始点とし、他方を終点とす
る。

【００７３】次いで、各配線セグメントＷ…上における
始点から終点までの間に、始点からの距離が単位長さ毎
（０，１，２，…）に候補位置を生成する。例えば、図
８（ｂ）に示すように、配線セグメントＷの始点・終点
間の距離が２である場合、距離０、距離１および距離２
の位置に、■で示すように候補位置が生成される。ただ
し、距離０の場合は、始点の直後に候補位置が生成さ
れ、距離２の場合は、終点の直前に候補位置が生成され
る。

【００７４】上記のＳ１４における中継点決定の処理
は、具体的には、図４（ａ）（ｂ）のフローチャートの
手順で行われる。

【００７５】まず、図４（ａ）に示すように、上記のよ
うにして生成された候補位置に挿入すべき中継点を中継
点挿入候補（中継点挿入候補位置）から選択する（Ｓ４
１）。ここでは、図４（ｂ）に示すように、各候補につ
いて遅延時間を算出し（Ｓ５１）、その遅延時間に基づ
いて、中継点のサイズを決定するとともに、前述のコス
ト式を用いてコスト値を算出する（Ｓ５２）。そして、
コスト値が最小となる候補を中継点として選び（Ｓ５
３）、その候補とコスト値とを次の処理に返す。

【００７６】次いで、前回選ばれた候補に対しコスト値
が減少しているか否かを判定し（Ｓ４２）、減少してい
る選択された候補を中継点とする（Ｓ４３）。続いて、
中継点が最大数を越えるまでに定められたか否かが判定
され（Ｓ４４）、最大数を越えていない場合は、中継点
挿入候補がなくなったか否かが判定される（Ｓ４５）。
ここで、中継点挿入候補がなくなれば、全ての中継点が
出力されたことになり（Ｓ４６）、処理が完了する。

【００７７】また、Ｓ４２の処理において、コスト値が
減少しなかった場合は、これ以上のコスト値の減少がな
いと考えられるので、処理がＳ４６に移行する。Ｓ４４
の処理において、中継点が予め定められた最大数を越え
た場合も、同様に処理がＳ４６に移行する。さらに、Ｓ
４５の処理において、中継点挿入候補がまだあれば、処
理がＳ４１に戻る。

【００７８】ここで、上記のＳ５１における遅延時間の
算出の具体的な方法について説明する。

【００７９】配線は、抵抗成分と容量成分とからなる等
価回路で表すことができる。ここで、πモデルを用いれ
ば、図９（ａ）に示す長さが１の配線は、図９（ｂ）に
示すように、全配線容量が２分割されて両端に接続さ
れ、その容量間が全配線抵抗で接続される等価回路に置
き換えられる。この等価回路では、長さ１当たりの配線
容量を０．２とし、長さ１当たりの配線抵抗を２５０と
している。

【００８０】単位長さ当たりの配線抵抗は、ほぼ配線の
幅に反比例し、単位長さ当たりの配線容量は、ほぼ配線
の幅に比例する。すなわち、配線幅を変化させる手段を
設けても、ある程度遅延時間を変化させることができ
る。したがって、配線幅を変化させる場合も遅延制御が
可能であるが、ここでは、説明の便宜上、配線幅を一定
としている。

【００８１】図１０（ａ）に示すように、配線の途中に
バッファセルｂｓが設けられた場合、バッファセルｂｓ
は、ゲートアレイなどにおいてトランジスタで構成さ
れ、トランジスタにより大きさ（サイズ）が決まる。ま
た、バッファセルｂｓのサイズと抵抗値とは反比例の関
係にある。したがって、抵抗および容量により遅延計算
を行うモデルにおいて、バッファセルｂｓは、図１０
（ｂ）に示すように、その負荷容量Ｃ_Bとサイズｓによ
って変化する抵抗とで表される。その抵抗は、１０００
をサイズｓ（１≦ｓ≦１０）で除した値とする。なお、
１０００という値は、ｓ＝１のときの抵抗値である。

【００８２】なお、バッファセルｂｓの負荷容量が配線
容量に対して十分小さい場合は、その負荷容量Ｃ_Bを無
視してもよい。また、バッファセルｂｓの内部遅延Ｄが
微小である場合も同様に無視できる。以降の説明では、
簡略化のために、バッファセルｂｓの負荷容量Ｃ_Bと内
部遅延Ｄを無視するが、無視しない場合においても、無
視する場合と同等の効果が得られる。

【００８３】次に、抵抗および容量の等価回路を用いた
遅延計算の一例について説明する。

【００８４】図１１（ａ）に示すように、Elmoreのモデ
ルでは、点Ａ・Ｂの間の遅延時間ｄ_abは、両点間の抵抗
ＲとＢ点における負荷容量Ｃとの積で表される。例え
ば、図１１（ｂ）に示すような、長さＬの配線の終端で
ある点Ｂ以降の負荷容量が０．１の配線は、上記のモデ
ルを適用すれば、図１１（ｃ）に示すように等価的に置
き換えられる。この等価回路において、点Ｂにおける全
負荷容量は、点Ｂ以降の負荷容量（０．１）と点Ｂにお
ける配線容量（０．１×Ｌ）とを加えた値になる。

【００８５】したがって、この配線の等価回路における
遅延時間ｄ_abは、ｄ_ab＝Ｒ×Ｃ＝（２５０×Ｌ）×（０．１×Ｌ＋０．１）と計算される。ここで、Ｌ＝１、Ｌ＝５の場合は、それ
ぞれ５０、７５０となる。

【００８６】一方、図１２（ａ）に示すように、途中の
点Ｐ（点Ａ・Ｐ間の距離がＬ₁となり、点Ｐ・Ｂ間の距
離がＬ₂となる点）にバッファセルｂｓが挿入された配
線は、図１２（ｂ）に示す等価回路で表される。この等
価回路における点Ａ・Ｐ間の遅延時間ｄ_apと点Ｐ・Ｂ間
の遅延時間ｄ_pbとは、それぞれ、ｄ_ap＝（２５０×Ｌ₁）×（０．１×Ｌ₁）ｄ_pb＝（１０００／ｓ）×（０．１×Ｌ₂×２＋０．
１）＋（２５０×Ｌ₂）×（０．１×Ｌ₂＋０．１）と計算される。

【００８７】ここで、Ｌ₁＝３、Ｌ₂＝２、ｓ＝５のと
き、ｄ_ap＝２２５、ｄ_pb＝２５０となる。したがって、
点Ａ・Ｂ間の遅延時間ｄ_abは、ｄ_ab＝ｄ_ap＋ｄ_pb＝２２５＋２５０＝４７５となる。

【００８８】上記のように、長さ５の配線においてバッ
ファセルｂｓを挿入しない場合は、遅延時間が７５０で
あったが、始点（点Ａ）から長さ３の位置にバッファセ
ルｂｓを挿入することで遅延時間を４７５に短縮するこ
とができる。すなわち、バッファセルｂｓの挿入は、遅
延時間を制御する作用があるので、バッファセルｂｓを
遅延調整素子として利用することができる。

【００８９】続いて、前述の手順による中継点決定の具
体例について説明する。

【００９０】図１３（ａ）に示す例では、供給源セルｕ
と、グループｇ₁〜ｇ₄とを有し、分岐点ｂ₁・ｂ₂が
設けられており、各配線セグメント上に中継点挿入候補
ｐ₁〜ｐ₂₀が生成されている。図１３（ａ）に示す状態
は、第１回目の中継点挿入候補の選択を示しているの
で、中継点は挿入されていない。

【００９１】このような構成において、各候補ｐ₁〜ｐ
₂₀について、それぞれを中継点とした場合の供給源セル
ｕから各グループｇ₁〜ｇ₄までの遅延時間を上記の方
法により算出する。この計算の結果では、表１に示すよ
うに、候補ｐ₃・ｐ₄についてのコスト値が最小とな
る。また、これらの候補ｐ₃・ｐ₄を中継点として定め
る場合、その中継点のサイズｓは、候補ｐ₃で３．６９
となり、候補ｐ₄で２．１１となり、候補ｐ₄の方が小
さくなる。したがって、図１３（ｂ）に示すように、候
補ｐ₄が中継点として選ばれる。

【００９２】なお、表１のコスト値は、前述の（23-2）
のコスト式に基づいて算出されている。

【００９３】

【表１】

【００９４】候補ｐ₄についての計算を詳細に説明す
る。以下の計算においては、長さ１当たりの配線容量を
０．２（＝０．１＋０．１）とし、長さ１当たりの配線
抵抗を２５０とし、ｇ₁〜ｇ₄の負荷容量を０．１とす
する。

【００９５】ｕ−ｂ₁間の遅延時間ｄ_ub1は、ｂ₁以降
の負荷容量が０．２×５＋０．１＋０．１であることか
ら、ｄ_ub1＝２５０×２×（０．２×２／２＋０．２×５＋０．１＋０．１）＝５００×１．４＝７００と計算される。また、ｂ₁−ｇ₁間の遅延時間ｄ_b1g1、
ｂ₁−ｇ₂間の遅延時間ｄ_b1g2は、それぞれ、ｄ_b1g1＝２５０×２×（０．２×２／２＋０．１）＝５００×０．３＝１５０ｄ_b1g2＝２５０×３×（０．２×３／２＋０．１）＝７５０×０．４＝３００と計算される。

【００９６】したがって、ｕ−ｇ₁間の遅延時間
ｄ_ug1、ｂ₁−ｇ₂間の遅延時間ｄ_ug2は、それぞれ、ｄ_ug1＝７００＋１５０＝８５０ｄ_ug2＝７００＋３００＝１０００一方、ｕ−ｐ₄間の遅延時間ｄ_up4は、ｄ_up4＝２５０×３×（０．２×３／２）＝７５０×
０．３＝２２５と計算される。また、ｐ₄−ｂ₂間の遅延時間ｄ
_p4b2は、ｐ₄に前述のバッファセルが挿入されると考え
られ、さらにｂ₂以降の負荷容量が０．２×４＋０．１
＋０．１であることから、ｄ_p4b2＝（１０００／ｓ）×（０．２×４＋０．１＋０．１）＝（１０００／ｓ）×１．０＝１０００／ｓと計算される。

【００９７】ｂ₂−ｇ₃間の遅延時間ｄ_b2g3、ｂ₂−ｇ
₄間の遅延時間ｄ_b2g4は、それぞれ、ｄ_b2g3＝２５０×２×（０．２×２／２＋０．１）＝５００×０．３＝１５０ｄ_b2g4＝２５０×２×（０．２×２／２＋０．１）＝５００×０．３＝１５０と計算される。

【００９８】したがって、ｕ−ｇ₃間の遅延時間
ｄ_ug3、ｕ−ｇ₄間の遅延時間ｄ_ug4は、それぞれ、ｄ_ug3＝２２５＋１０００／ｓ＋１５０＝３７５＋１０
００／ｓｄ_ug4＝２２５＋１０００／ｓ＋１５０＝３７５＋１０
００／ｓ上記のように計算された遅延時間からｓを求めるには、
次の計算を行う。

【００９９】ｓの範囲が１≦ｓ≦１０に特定されている
ので、遅延時間ｄ_ug3・ｄ_ug4＝ｄとすれば、４７５≦
ｄ≦１３７５となり、（23-2）のコスト式は、次のよう
に分類される。（Ａ）８５０≦ｄ≦１０００の場合この範囲において、ｄ_max＝１０００、ｄ_min＝８５０
であるので、コスト値Ｆは、Ｆ＝（１０００−８５０）×８５０＝１２７５００となる。（Ｂ）４７５≦ｄ＜８５０の場合この範囲において、ｄ_max＝１０００であるので、コス
ト値Ｆは、Ｆ＝（１０００−ｄ）×ｄ＞１２７５００となる。この式は、上に凸となり、軸がｄ＝５００であ
る放物線を表している。このため、コスト値Ｆは、ｄが
軸から遠い８５０付近で最も小さくなる。（Ｃ）１０００＜ｄ≦１３７５の場合この範囲において、ｄ_min＝８５０であるので、コスト
値Ｆは、Ｆ＝（ｄ−８５０）×８５０＞（１０００−８５０）×８５０＝１２７５００となる。

【０１００】したがって、（Ａ）の場合、コスト値が最
小となる。この場合のｓは、８５０≦３７５＋１０００／ｓ≦１０００を満たす範囲で、最小遅延時間ｄ_minとの差が最も小さ
くなるように定められるので、３７５＋１０００／ｓ＝
８５０を満たす値、すなわち２．１１となる。

【０１０１】次に、中継点となった候補ｐ₄を除く候補
ｐ₁〜ｐ₃・ｐ₅〜ｐ₂₀について、上記の場合と同様に
して遅延時間を計算する。この計算の結果では、表２に
示すように、候補ｐ₁₅についてのコスト値が最小とな
り、この候補ｐ₁₅についての中継点のサイズｓは１．３
３となる。ここで、コスト値が０となるため、次回の中
継点挿入候補の選択では、コスト値が減少することはな
い。したがって、図４（ａ）のＳ４２の判定を経て、最
終的には候補ｐ₄・ｐ₁₅が中継点として出力される。

【０１０２】

【表２】

【０１０３】前述のＳ８（図１）の処理において、中継
点に挿入するセルのパラメータは、具体的には、次のよ
うに決定される。なお、寄生成分抽出部１４により抽出
された寄生成分（配線容量および配線抵抗）が中継点決
定時の予測値と同じ場合には、中継点決定時に求めた中
継点のサイズをセルのパラメータとして用いる。

【０１０４】図１４に、配線容量が中継点決定時の予測
値と異なる場合を例示する。この場合、配線における分
岐点ｂ₁および中継点ｐ₄の付近の２か所で、単位長さ
当たりの配線容量が０．２（予測値）から０．３に増加
している。ただし、配線抵抗および各グループの容量は
変化していない。また、中継点ｐ₄・ｐ₁₅に挿入する挿
入セルのサイズをそれぞれｓ₁、ｓ₂とする。

【０１０５】上記例における供給源セルｕから各グルー
プｇ₁〜ｇ₄までの経路の遅延時間ｄ₁〜ｄ₄は、ｄ₁＝６７５＋３００／ｓｄ₂＝９１２．５ｄ₃＝４３７．５＋１０００／ｓ₁ ｄ₄＝４３７．５＋１０００／ｓ₁ と計算される。

【０１０６】ここで、前述の（23-2）のコスト式を用い
て、コスト値Ｆを最小にするｓ₁、ｓ₂を求めると、ｓ
₁＝２．１０、ｓ₂＝１．２６となる。このとき、コス
ト値が０となり、各グループｇ₁〜ｇ₄についての遅延
時間は全て９１２．５となる。

【０１０７】このようにしてサイズが決定された挿入セ
ルを中継点ｐ₄・ｐ₁₅に挿入することにより、配線容量
が予想値と異なっても、設計通りに遅延制御を行うこと
ができる。

【０１０８】また、配線抵抗が変化した場合も、同様な
方法で、各グループｇ₁〜ｇ₄についての遅延時間を計
算し、コスト値を最小（または最大）にする挿入セルの
サイズを求めることにより、設計通りに遅延制御が可能
になる。あるいは、最小のコスト値を得るためのコスト
式に代えて、最大の計算値が最も高い評価を与える評価
式を導入すれば、その計算結果である評価値を最大値に
する挿入セルのサイズを求めることにより、設計通りに
遅延制御が可能になる。

【０１０９】なお、配線抵抗が一定の場合でも評価式を
導入する場合、図４（ａ）（ｂ）に示す処理において
は、コスト値が評価値に代わり、Ｓ４２の処理で評価値
が増加したか否かを判定し、Ｓ５３の処理で評価値最大
の候補を選ぶことになる。

【０１１０】以上述べたように、本実施の形態に係る方
法および装置によれば、配線前に設けた中継点（挿入セ
ル）のサイズを配線完了後に決定しているので、全ての
レイアウト（配置・配線）の結果の影響を考慮した遅延
制御を、図１５に示すように、再配線を行うことなく実
現することができる。

【０１１１】また、バッファセル（遅延制御素子）を設
けることにより遅延制御を行うので、配線の迂回を減少
させることができる。

【０１１２】また、遅延制御を行う中継点（バッファセ
ル）を制御対象となる供給先セルと分離せずに配置する
ので、これらの間の配線の増大を抑えることができる。

【０１１３】さらに、配線密度を予め求めておくことに
より、その配線密度に基づいて、中継点における領域確
保の処理において配線密度を利用して領域に必要な最小
限の大きさを求めることができ、中継点のサイズの小型
化を図ることができる。また、配線密度をグループ化の
処理におけるグループの負荷容量の計算に利用すること
ができる。

【０１１４】

【発明の効果】以上のように、本発明の請求項１に係る
配線設計方法は、配置工程により配置された供給源の素
子から供給先の素子へ至る配線予定経路を決定し、その
経路に施されるべき配線の配線抵抗および配線容量の予
測に基づいて上記経路の途中に中継点を設定する設定工
程と、配線工程の前に各配線予定経路における信号の遅
延時間を調整する遅延調整素子を挿入するための領域を
調整すべき遅延時間に応じた大きさに上記中継点に確保
する領域確保工程とを備えている構成である。

【０１１５】このように、予め上記の領域を確保してお
くことにより、配線後の配線抵抗および配線容量が中継
点の設定時における予測と異なる場合、遅延調整素子の
大きさを配線後の配線抵抗および配線容量に応じて設定
することで、素子の再配置または素子間の再配線を行う
ことなく、配線抵抗および配線容量の配線前後の差によ
る影響をなくすことができる。それゆえ、配線前に設定
した配線における遅延時間を配線後にも維持することが
できる。また、遅延制御のために設けられる中継点を供
給先の素子と分離して設ける必要がなくなるので、それ
らの間の配線の短縮化が可能になる。したがって、配線
設計の効率化だけでなく、設計された配線回路の面積お
よび消費電力の削減を図ることができるという効果を奏
する。

【０１１６】本発明の請求項２に係る配線設計方法は、
請求項１に係る配線設計方法における上記設定工程が、
配線予定経路上に中継点の候補位置を設定する候補設定
工程と、各候補位置について目標とする遅延制御の達成
度合いを評価し、最良の評価が得られた候補位置を中継
点として選出する選出工程とを有する構成である。

【０１１７】これにより、遅延時間の短縮や各経路間の
遅延時間を等しくするといった詳細な項目について遅延
制御を行うことができる。また、中継点の数を制限する
ことができる。したがって、より自由度が高く、かつ消
費電力の少ない配線設計を実現することができるという
効果を奏する。

【０１１８】本発明の請求項３に係る配線設計方法は、
請求項２に係る配線設計方法における上記選出工程が、
最良の評価が得られた複数の候補位置から中継点の大き
さが最小になる候補位置を中継点として選出するので、
遅延調整素子の挿入用に確保される領域が小さくなる。
したがって、中継点の占有面積を小さくすることができ
るという効果を奏する。

【０１１９】本発明の請求項４に係る配線設計方法は、
請求項１に係る配線設計方法に加えて、配置工程による
素子の配置結果に基づいて配線密度を算出する密度算出
工程を備え、上記領域確保工程が、算出された配線密度
に応じた大きさの領域を確保するので、配線密度により
決まる配線間の容量を考慮した大きさの領域を確保する
ことができ、配線間の容量に基づく遅延時間を領域の大
きさに反映させることができる。したがって、必要最小
限の大きさの領域を確保することができるという効果を
奏する。

【０１２０】本発明の請求項５に係る配線設計方法は、
請求項１に係る配線設計方法における上記設定工程が、
供給先の素子を特定の属性に基づいて分類するグループ
化工程を有し、供給源の素子と各グループとの間に配線
予定経路を決定するので、配線数が多くなっても、素子
がグループ化されることにより、素子単位で中継点を決
定する場合に比べて中継点の決定数を少なくすることが
できる。したがって、中継点決定の処理の効率化を図る
ことができるという効果を奏する。

【０１２１】本発明の請求項６に係る配線設計方法は、
請求項５に係る配線設計方法における上記グループ化工
程が、１つのグループの負荷容量が許容値を越えないよ
うに制限するので、グループ内での配線長を短く抑える
ことができる。それゆえ、グループの大きさを配線遅延
の影響が無視できる程度に制限することなどが可能にな
る。したがって、遅延制御の効率化を図ることができ
る。

【０１２２】本発明の請求項７に係る配線設計方法は、
配置工程により配置された供給源の素子から供給先の素
子へ至る配線予定経路を決定し、その経路に施されるべ
き配線の配線抵抗および配線容量の予測に基づいて上記
経路の途中に中継点を設定する設定工程と、配線工程の
前に各配線予定経路における信号の遅延時間を調整する
遅延調整素子を挿入するための領域を調整すべき遅延時
間に応じた大きさに上記中継点に確保する領域確保工程
と、上記配線工程により施された配線についての配線容
量および配線抵抗を抽出する抽出工程と、抽出された配
線容量および配線抵抗に基づいて、与えられた信号遅延
時間の制約を満たし得る遅延調整素子を決定して上記中
継点に挿入する挿入工程とを備えている構成である。

【０１２３】これにより、配線抵抗および配線容量が中
継点の設定時における予測と異なっても、素子や配線の
レイアウトを変更することなく、配線抵抗および配線容
量の配線前後の差による影響をなくすことができる。そ
れゆえ、配線前に設定した配線における遅延時間を配線
後にも維持することができる。また、遅延調整素子を挿
入することにより遅延時間が制御されるので、配線の迂
回が減少して信号伝搬経路全体の容量が減少する。さら
に、遅延制御のために中継点に挿入される遅延制御素子
を供給先の素子と分離する必要がなくなるので、それら
の間の配線の短縮化が可能になる。したがって、配線設
計の効率化だけでなく、設計された配線の消費電力およ
び配線面積の削減を図ることができるという効果を奏す
る。

【０１２４】本発明の請求項８に係る配線設計方法は、
請求項７に係る配線設計方法における上記挿入工程が、
抽出された配線抵抗および配線容量に基づき、各中継点
について目標とする遅延制御の達成度合いを評価し、各
中継点についての最良の評価に基づいて遅延調整素子の
大きさを設定するので、遅延時間の短縮や各経路間の遅
延時間を等しくするといった特定の目標について最も望
ましい遅延制御を行うことができるという効果を奏す
る。

【０１２５】本発明の請求項９に係る配線設計装置は、
配置手段により配置された供給源の素子から供給先の素
子へ至る配線予定経路を決定し、その経路に施されるべ
き配線の配線抵抗および配線容量の予測に基づいて上記
経路の途中に中継点を設定する設定手段と、配線前に各
配線予定経路における信号の遅延時間を調整する遅延調
整素子を挿入するための領域を調整すべき遅延時間に応
じた大きさに上記中継点に確保する領域確保手段とを備
えている構成であるので、請求項１に係る配線設計方法
と同様、配線設計の効率化を図ることができるという効
果を奏する。

【０１２６】本発明の請求項１０に係る配線設計装置
は、請求項９に係る配線設計装置における上記設定手段
が、配線予定経路上に中継点の候補位置を設定し、各候
補位置について目標とする遅延制御の達成度合いを評価
し、最良の評価が得られた候補位置を中継点として選出
する構成であるので、請求項２に係る配線設計方法と同
様、より自由度が高く、かつ消費電力の少ない配線設計
を実現することができるという効果を奏する。

【０１２７】本発明の請求項１１に係る配線設計装置
は、請求項１０に係る配線設計装置における上記設定手
段が、最良の評価が得られた複数の候補位置から中継点
の大きさが最小になる候補位置を中継点として選出する
ので、請求項３に係る配線設計方法と同様、中継点の占
有面積を小さくすることができるという効果を奏する。

【０１２８】本発明の請求項１２に係る配線設計装置
は、請求項９に係る配線設計装置に加えて、上記配置手
段による素子の配置結果に基づいて配線密度を算出する
密度算出手段を備え、上記領域確保手段が、算出された
配線密度に応じた大きさの領域を確保するので、請求項
４に係る配線設計方法と同様、必要最小限の大きさの領
域を確保することができるという効果を奏する。

【０１２９】本発明の請求項１３に係る配線設計装置
は、請求項９に係る配線設計装置における上記設定手段
が、供給先の素子を特定の属性に基づいてグループ化
し、供給源の素子と各グループとの間に配線予定経路を
決定するので、請求項５に係る配線設計方法と同様、中
継点決定の処理の効率化を図ることができるという効果
を奏する。

【０１３０】本発明の請求項１４に係る配線設計装置
は、請求項１３に係る配線設計装置における上記設定手
段が、グループ化において、１つのグループの負荷容量
が許容値を越えないように制限するので、請求項６に係
る配線設計方法と同様、遅延制御の効率化を図ることが
できるという効果を奏する。

【０１３１】本発明の請求項１５に係る配線設計装置
は、配置手段により配置された供給源の素子から供給先
の素子へ至る配線予定経路を決定し、その経路に施され
るべき配線の配線抵抗および配線容量の予測に基づいて
上記経路の途中に中継点を設定する設定手段と、配線前
に各配線予定経路における信号の遅延時間を調整する遅
延調整素子を挿入するための領域を調整すべき遅延時間
に応じた大きさに上記中継点に確保する領域確保手段
と、配線手段により施された配線についての配線容量お
よび配線抵抗を抽出する抽出手段と、抽出された配線容
量および配線抵抗に基づいて、与えられた信号遅延時間
の制約を満たし得る遅延調整素子を決定して上記中継点
に挿入する挿入手段とを備えている構成であるので、請
求項７に係る配線設計方法と同様、配線設計の効率化だ
けでなく、消費電力および配線面積の削減を図ることが
できるという効果を奏する。

【０１３２】本発明の請求項１６に係る配線設計装置
は、請求項１５に係る配線設計装置における上記挿入手
段が、抽出された配線抵抗および配線容量に基づき、各
中継点について目標とする遅延制御の達成度合いを評価
し、各中継点についての最良の評価に基づいて遅延調整
素子の大きさを設定するので、請求項８に係る配線設計
方法と同様、特定の目標について最も望ましい遅延制御
を行うことができるという効果を奏する。

【図面の簡単な説明】

【図１】本発明の実施の一形態に係る配線設計装置にお
いて遅延制御を含む配線レイアウト処理の手順を示すフ
ローチャートである。

【図２】図１の一連の処理における中継点生成処理の手
順を示すフローチャートである。

【図３】図２の一連の処理におけるグループ化処理の手
順を示すフローチャートである。

【図４】図２の一連の手順における中継点決定処理の手
順およびこの処理における中継点選択処理の手順を示す
フローチャートである。

【図５】上記配線設計装置の構成を示すブロック図であ
る。

【図６】供給先セルが図３のグループ化処理によりグル
ープ化される様子を示す説明図である。

【図７】供給源セルと各グループとの間に配線が施され
た状態を示す説明図である。

【図８】配線セグメントおよび配線セグメントにおける
中継点候補位置を示す説明図である。

【図９】単位長の配線およびその配線の遅延モデルを示
す回路図である。

【図１０】バッファセルが設けられた単位長の配線およ
びその配線の遅延モデルを示す回路図である。

【図１１】配線における抵抗および容量による遅延モデ
ル、長さＬの配線およびこの配線に上記遅延モデルを適
用した例を示す回路図である。

【図１２】バッファセルが設けられた配線における抵抗
および容量による遅延モデルを示す回路図である。

【図１３】図４の中継点決定処理による中継点の決定の
具体例を示す説明図である。

【図１４】図４の中継点決定処理による中継点の決定の
他の具体例を示す説明図である。

【図１５】図１の処理を用いて完成した配線レイアウト
を示す説明図である。

【図１６】従来の配線レイアウトを示す説明図である。

【図１７】従来の他の配線レイアウトを示す説明図であ
る。

【図１８】従来の配線レイアウト処理の手順を示すフロ
ーチャートである。

【符号の説明】

３・４データベース１１配置部（配置手段）１２配線密度算出部（密度算出手段）１３配線部（配線手段）１４寄生成分抽出部（抽出手段）２１中継点生成部（中継点設定手段）２２供給先グループ化部２３コスト算出部２５サイズ算出部２６中継点領域確保部（領域確保手段）２７中継点セル挿入部（挿入手段）ｕ供給源セル（供給源の素子）ｖ供給先セル（供給先の素子）ｂｓバッファセル（遅延制御素子）

Claims

【特許請求の範囲】

【請求項１】信号の供給源および供給先となる素子を配
置する配置工程と、配置された供給源の素子と各供給先
の素子との間に配線を施す配線工程とを備えた配線設計
方法において、配置された供給源の素子から供給先の素子へ至る配線予
定経路を決定し、その経路に施されるべき配線の配線抵
抗および配線容量の予測に基づいて上記経路の途中に中
継点を設定する設定工程と、上記配線工程の前に各配線予定経路における信号の遅延
時間を調整する遅延調整素子を挿入するための領域を調
整すべき遅延時間に応じた大きさに上記中継点に確保す
る領域確保工程とを備えていることを特徴とする配線設
計方法。
【請求項２】上記設定工程は、配線予定経路上に中継点
の候補位置を設定する候補設定工程と、各候補位置につ
いて目標とする遅延制御の達成度合いを評価し、最良の
評価が得られた候補位置を中継点として選出する選出工
程とを有することを特徴とする請求項１に記載の配線設
計方法。
【請求項３】上記選出工程は、最良の評価が得られた複
数の候補位置から中継点の大きさが最小になる候補位置
を中継点として選出することを特徴とする請求項２に記
載の配線設計方法。
【請求項４】上記配置工程による素子の配置結果に基づ
いて配線密度を算出する密度算出工程をさらに備え、上記領域確保工程が、算出された配線密度に応じた大き
さの領域を確保することを特徴とする請求項１に記載の
配線設計方法。
【請求項５】上記設定工程は、供給先の素子を特定の属
性に基づいて分類するグループ化工程を有し、供給源の
素子と各グループとの間に配線予定経路を決定すること
を特徴とする請求項１に記載の配線設計方法。
【請求項６】上記グループ化工程において、１つのグル
ープの負荷容量が許容値を越えないように制限すること
を特徴とする請求項５に記載の配線設計方法。
【請求項７】信号の供給源および供給先となる素子を配
置する配置工程と、配置された供給源の素子と各供給先
の素子との間に配線を施す配線工程とを備えた配線設計
方法において、配置された供給源の素子から供給先の素子へ至る配線予
定経路を決定し、その経路に施されるべき配線の配線抵
抗および配線容量の予測に基づいて上記経路の途中に中
継点を設定する設定工程と、上記配線工程の前に各配線予定経路における信号の遅延
時間を調整する遅延調整素子を挿入するための領域を調
整すべき遅延時間に応じた大きさに上記中継点に確保す
る領域確保工程と、上記配線工程により施された配線についての配線容量お
よび配線抵抗を抽出する抽出工程と、抽出された配線容量および配線抵抗に基づいて、与えら
れた信号遅延時間の制約を満たし得る遅延調整素子を決
定して上記中継点に挿入する挿入工程とを備えているこ
とを特徴とする配線設計方法。
【請求項８】上記挿入工程は、抽出された配線抵抗およ
び配線容量に基づき、各中継点について目標とする遅延
制御の達成度合いを評価し、各中継点についての最良の
評価に基づいて遅延調整素子の大きさを設定することを
特徴とする請求項７に記載の配線設計方法。
【請求項９】信号の供給源および供給先となる素子を配
置する配置手段と、配置された供給源の素子と各供給先
の素子との間に配線を施す配線手段とを備えた配線設計
装置において、配置された供給源の素子から供給先の素子へ至る配線予
定経路を決定し、その経路に施されるべき配線の配線抵
抗および配線容量の予測に基づいて上記経路の途中に中
継点を設定する設定手段と、配線前に各配線予定経路における信号の遅延時間を調整
する遅延調整素子を挿入するための領域を調整すべき遅
延時間に応じた大きさに上記中継点に確保する領域確保
手段とを備えていることを特徴とする配線設計装置。
【請求項１０】上記設定手段は、配線予定経路上に中継
点の候補位置を設定し、各候補位置について目標とする
遅延制御の達成度合いを評価し、最良の評価が得られた
候補位置を中継点として選出することを特徴とする請求
項９に記載の配線設計装置。
【請求項１１】上記設定手段は、最良の評価が得られた
候補位置が複数存在する場合、中継点の大きさが最小に
なる候補位置を中継点として選出することを特徴とする
請求項１０に記載の配線設計装置。
【請求項１２】上記配置手段による素子の配置結果に基
づいて配線密度を算出する密度算出手段をさらに備え、領域確保手段が、算出された配線密度に応じた大きさの
領域を確保することを特徴とする請求項９に記載の配線
設計装置。
【請求項１３】上記設定手段は、供給先の素子を特定の
属性に基づいてグループ化し、供給源の素子と各グルー
プとの間に配線予定経路を決定することを特徴とする請
求項９に記載の配線設計装置。
【請求項１４】上記設定手段は、グループ化において、
１つのグループの負荷容量が許容値を越えないように制
限することを特徴とする請求項１３に記載の配線設計装
置。
【請求項１５】信号の供給源および供給先となる素子を
配置する配置手段と、配置された供給源の素子と各供給
先の素子との間に配線を施す配線手段とを備えた配線設
計装置において、上記配置手段により配置された供給源の素子から供給先
の素子へ至る配線予定経路を決定し、その経路に施され
るべき配線の配線抵抗および配線容量の予測に基づいて
上記経路の途中に中継点を設定する設定手段と、配線前に各配線予定経路における信号の遅延時間を調整
する遅延調整素子を挿入するための領域を調整すべき遅
延時間に応じた大きさに上記中継点に確保する領域確保
手段と、上記配線手段により施された配線についての配線容量お
よび配線抵抗を抽出する抽出手段と、抽出された配線容量および配線抵抗に基づいて、与えら
れた信号遅延時間の制約を満たし得る遅延調整素子を決
定して上記中継点に挿入する挿入手段とを備えているこ
とを特徴とする配線設計装置。
【請求項１６】上記挿入手段は、抽出された配線抵抗お
よび配線容量に基づき、各中継点について目標とする遅
延制御の達成度合いを評価し、各中継点についての最良
の評価に基づいて遅延調整素子の大きさを設定すること
を特徴とする請求項１５に記載の配線設計装置。