JPH07319951A

JPH07319951A - 自動配線方法

Info

Publication number: JPH07319951A
Application number: JP6134917A
Authority: JP
Inventors: Akio Ishizuka; 昭夫石塚
Original assignee: NEC Corp
Current assignee: NEC Corp
Priority date: 1994-05-26
Filing date: 1994-05-26
Publication date: 1995-12-08
Anticipated expiration: 2012-12-08
Also published as: US5757089A; JP2687879B2; KR950034687A; KR0148299B1

Abstract

(57)【要約】【目的】自動配線処理において、端子付近を他ネットの
配線が通ることによって配線が妨害される問題を無くし
て配線率を高める自動配線方法の提供。【構成】ネットの配線経路を求める際に配線経路の形状
によって決まるコスト値が最も小さくなるような配線経
路を求める自動配線方法において、他のネットの未配線
の端子から所定の範囲内を通る配線経路に対してコスト
値が大きくなるようなコスト関数を用いることを特徴と
する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は集積回路の配線設計方法
に関し、特にコスト関数を用いて最適な経路を求める自
動配線方法に関する。

【０００２】

【従来の技術】集積回路の配線設計においては、複数の
ネットを一括して配線する方法と１ネットずつ配線する
方法があるが、後者の方法では、先に配線したネットの
配線が後から配線するネットの障害となり、後のネット
が配線できなくなることがある。この問題を以下に詳述
する。

【０００３】まず、集積回路の配線設計における基本概
念を説明すると、端子とは、機能素子（例えばＮＡＮＤ
ゲート、インバータ等）において、信号が入出力される
位置をいう。また、ネットとは、互いに配線で結ぶべき
一組の端子集合をいう。配線をチップ上に効率良く配置
するために、一般に、配線が配置されるべき位置（「配
線格子」という）を予め定めておく方法が用いられ、通
常、配線格子はチップ上一定間隔で水平及び垂直方向に
並置される。そして、集積回路において、所望の機能を
実現するためには、例えば数千個の機能素子又は機能ブ
ロックと、これらの機能素子又は機能ブロックを相互に
接続するネットが必要となる。

【０００４】迷路法は、基本的に２点間の可能な経路を
しらみつぶし的に探索する方法であり、チップ上におい
て、例えば数千のネットについて１つずつ順番に配線し
ていく。より詳細には、迷路法は、一のネットに対し
て、それぞれの端子から一配線格子以内の距離にあり配
線が到達できる全ての格子点（配線格子の交点）を列挙
する。ここで、配線が到達できる格子点は、その位置に
おいて配線禁止や、他のネットの端子等が存在しないも
のに限られる。複数の端子から到達できる格子点が存在
しない場合、先に列挙した到達可能な格子点から更に１
配線格子分だけ先に進む。

【０００５】ある格子点に２つの端子から到達できた場
合、各々の端子からその格子点までの経路を辿ることに
より２つの端子を接続する配線経路が得られる。そし
て、２つの端子間の配線経路が得られた場合、この２つ
の端子を結ぶ配線経路を１つの端子と見做して、この端
子と残りの端子間の配線経路を探索する処理が行なわれ
る。

【０００６】図６を参照して、迷路法による配線例を具
体的に説明する。同図において、端子201と端子202は迷
路法で相互に配線された端子を示す。図中太い実線211
は第２金属層配線、破線206、210は第１金属層配線、×
印は、第１、第２金属層の間を接続するスルーホールを
それぞれ表している。

【０００７】迷路法は、前記の如く、ネットの配線を一
つずつ順番に行なうため、先に配線したネットの配線が
他のネットの配線を妨げることがしばしば生じる。図６
において、端子201と端子202を結ぶ第２層配線が、他の
ネットの端子203（第１層に存在する）の真上を通過し
ており、端子203に配線を接続することができなくなっ
ている。このように、あるネットの配線が他のネットの
配線を妨げるという問題の多くは、端子の近傍をネット
が通ることにより生じている。

【０００８】従来、上記問題を解決する方法として、配
線前の端子付近に配線禁止領域を設定し、他のネットが
端子の近くを通ることを防ぐ方法がある。この種の方法
として、例えば特開平3-274751号公報には、配線しよう
とする端子以外の端子から引き出された勢力範囲を配線
禁止領域とする方法が開示されている。なお、同公報に
よれば、チップ全体を小さな矩形領域に分割して配線が
為され、端子付近に設定する勢力範囲の長さをパラメー
タ（例えば矩形領域の一辺に対する割合％）とし、パラ
メータ値はパラメータ決定部から配線処理部に与えられ
る。

【０００９】ここに、配線禁止領域とは、例えば機能素
子又は機能ブロックの中で所望の論理を実現するための
配線、及び機能素子（ブロック）に対する電源、接地を
与える配線等、配線上必須の配線領域をいい、他のネッ
トが該領域を通過する事は禁止される。

【００１０】前記公報記載の配線方法によれば、あるネ
ット（これを「ネットＡ」という）を配線する際に、ネ
ットＡ以外のネットの端子について、未だ配線されてい
ない端子に着目し、その未配線の端子から所定の範囲内
において、ネットＡの配線が通らないように配線禁止領
域を設定する。この処理をネットＡ以外の全てのネット
について行った後に、ネットＡの配線を行う。

【００１１】ネットＡの配線経路としては、上記の配線
禁止領域を通らない経路が探索される。このような経路
が見つからない場合には、ネットＡは未配線となる。な
お、未配線となったネットの配線処理については様々な
方法がある。例えば、端子付近の配線禁止領域をより狭
く設定し直してから再びネットＡの配線を試みるとか、
あるいは他のネットの配線を先に行い、後で再びネット
Ａの配線を試行する等の方法がある。ネットＡの配線が
完了したら、次のネットに関して同様の処理を行う。こ
の処理を全てのネットについて繰り返す。

【００１２】

【発明が解決しようとする課題】しかしながら、前記従
来の方法の場合、端子の付近に配線禁止領域を設定する
ため、配線は、他ネットの配線禁止領域が設定された端
子近傍を全く通ることができず、結果として、配線を大
きく遠回りさせる等の迂回配線が発生したり、沢山のビ
アを用いること等により、質の悪い経路が発生されると
いう問題がある。そして、一つ一つの配線経路の形状が
悪いと最終的に全ネットの配線が収容しきれなくなる事
が多い。

【００１３】また、前記従来の方法では、端子からの配
線経路が決まる前に予め端子に配線禁止領域を設定しな
ければならず、端子から配線が引き出せることを保証す
るために配線禁止領域は広めに設定する場合が多く、こ
のため、迂回配線やビア数の増大が生じる他、配線禁止
領域が広めに設定された端子に接続されるネットでは使
用されない部分にまで他ネットの配線を禁じてしまう場
合があり、その結果、未配線が生じる割合が高くなると
いう問題がある。その際、配線禁止領域を小さく設定し
てから再び配線をやり直すことになり、配線時間の長大
化という問題も生じる。

【００１４】そこで、本発明は、前記問題点を解消し、
端子の付近を他ネットの配線が通ることと配線の形状を
悪くすることのトレードオフを計ることによって配線長
を長くすることなく、他のネットの配線が端子からの配
線の引き出しを妨げることを低減し、より短い配線長で
高い配線率を達成可能な、自動配線の配線コスト決定方
法及び自動配線方法の提供を目的としている。

【００１５】

【課題を解決するための手段】上記目的を達成するため
に、本発明は、一のネットの配線経路の配線コスト計算
において、他のネットに属する未配線の端子に対して、
該端子からの距離に依存して、前記一のネットの配線経
路のコスト値を可変に割り付けることを特徴とする自動
配線の配線コストの決定方法を提供する。本発明におい
て、端子から遠ざかるにつれてコストの重みが小さくさ
れる。

【００１６】また、本発明は、別の視点において、ネッ
トの配線経路を求める際に配線経路の形状によって決ま
るコスト値が最も小さくなるような配線経路を求める自
動配線方法において、他のネットの未配線の端子から所
定の範囲内を通る配線経路に対してコスト値が大きくな
るようなコスト関数を用いることを特徴とする自動配線
方法を提供する。

【００１７】さらに、本発明の自動配線方法は、その処
理の好ましい態様として、(a)全てのネットについて該
ネットの未配線の端子から所定の範囲内に端子保護コス
トを設定する工程と、(b)未配線のネットがあるか否か
を判定し、未配線のネットが無い場合には配線を終了す
ると共に、未配線のネットが存在する限り次の各工程
(c)〜(f)を順次繰返すよう制御する工程と、(c)配線対
象の一のネットについて該ネットの未配線の端子に設定
された端子保護コストを解除する工程と、(d)コスト関
数を最小とする配線経路を探索する工程と、最小コスト
配線経路の探索が成功した場合において、(e)確定した
ネットの配線経路を記録する工程と、(f)配線したネッ
トについて該ネットの未配線の端子から所定の範囲内に
端子保護コストを設定する工程と、上記各工程から成る
ものである。

【００１８】

【作用】本発明の自動配線の配線コスト決定方法によれ
ば、端子からの距離に依存した端子保護コストを設けた
ことにより、ネットの配線が端子への配線を妨げること
を防止するための配線禁止領域を設けるという従来の配
線方法に比べて、同等以上の配線完了率を達成しなが
ら、従来方法よりも短い配線長で、ビア数も少なく配線
できる。

【００１９】また、本発明の自動配線方法は、端子から
の距離に依存したコスト関数に基づき、配線全体のコス
トが小さくなる場合には端子保護領域にも配線を引き込
むように配線経路が選択される事により、高い配線完了
率を確保すると共に、従来方法よりも短い配線長で、且
つビア数の少ない、質の高い配線を可能とし、配線面積
も少なくて済む。そして、本発明の自動配線方法によれ
ば、より短い配線長で高い配線完了率を達成し、配線処
理を効率化することにより配線時間を短縮化する。

【００２０】

【実施例】本発明について図面を参照して以下に説明す
る。

【００２１】

【実施例１】図１は本発明の自動配線方法の構成を示し
た図である。図２はその動作を示すフローチャートであ
る。図１に示すように、本発明の自動配線方法は、端子
保護コスト設定部１、配線処理部２、配線経路コスト計
算部３、端子保護コスト削除部４の４つの処理ブロック
から構成される。

【００２２】配線処理部２は、コスト最小経路の求める
処理で、コスト付き迷路法などを用いる。コスト付き迷
路法としては、例えば、文献、シンとサンジョバンニ・
ヴィンセンテルリ著（HYUNCHUL SHIN and ALBERTO SANG
IOVANNI-VINCENTELLI）、『ＡＤetailed Ｒouter Ｂas
ed on Ｉncremental Ｒouting Ｍodifications：Ｍight
y』、ＩＥＥＥＴransactions on Ｃomputer-Ａided Ｄ
esign，Ｖol. ＣＡＤ-6，Ｎo.6，November，1987，第94
2〜955頁に記載されている方法等、公知のものが用いら
れる。配線処理部２では、迷路法以外にもコスト付きの
線分探索法等も用いることができる。なお、線分探索法
とは、接続すべき両端からｘ，ｙ方向に順次線分を発生
させ、始点からの線分と終点からの線分が交わった時
に、その点から逆方向に辿って経路を決定する方法であ
る。

【００２３】迷路法としては、決められた配線格子の上
しか配線を通さないいわゆるグリッド配線と、配線格子
を定めずにデザインルールで決められた配線間隔を守っ
て配線するいわゆるグリッドレス配線の２種類があり、
いずれの方法を用いても構わない。以下では、配線格子
を用いたグリッド配線を想定して、実施例を説明する。

【００２４】配線処理部２では、経路を１ステップ求め
るごとにその経路のコストを配線経路コスト計算部３を
用いて計算し、経路の総コストに加算していく。１ステ
ップとは、迷路法配線では１格子進むことで、線分探索
法では１回折れ曲がって線分を発生することに相当す
る。配線処理は、端子間を結ぶ様々な配線経路の中で、
経路上のコストの総和が最小になる経路を探索する。

【００２５】配線経路のコストとしては、各層毎及び進
む方向毎の１格子進むコスト、ビアを設置して配線層を
変更する毎に加えられるコスト、端子保護コストの設定
された格子上を進むコストなどがある。

【００２６】端子保護コスト設定部１では、未だ配線が
接続していない端子を見付けてその端子の近傍に保護コ
ストを設定する。ここで、端子の近傍（あるいは付近）
とは、端子から所定の方向、所定の配線層で、予め定め
られた所定の設定値以内の距離にある配線格子点を意味
する。

【００２７】端子保護コストの設定とは、格子点に対し
て、端子からの距離に応じたコードを割り当てることで
ある。例えば、図３において、第１配線層にある端子10
が位置する垂直方向配線格子上の第２配線層の格子で垂
直方向に１格子以内にある格子にはコードＡを割り当
て、同じく垂直方向に５格子以内にある格子にはコード
Ｂを割り当てる。

【００２８】格子点のコードは配線経路コスト計算部３
で参照され、配線が、コードＡの格子を通過するときに
は、例えばコスト100を加算し、コードＢの格子を通過
するときにはコスト５を加算する、という具合に用い
る。

【００２９】端子の非常に近くを通る配線は、端子から
配線を引き出すのを妨害する可能性が非常に高いため大
きなコストを与え、やや近くを通る配線は妨害の可能性
が低いため小さなコストを与える。コストは累積される
ため、コードＢの格子を３箇所通る配線はコードＢのコ
ストの３倍が加算される。

【００３０】ネットＡの配線を行う時は、ネットＡの端
子近傍の保護コストは邪魔になるので、保護コストを外
さなければならない。端子保護コスト削除部４はネット
の配線を行う前にそのネットの端子に関わる保護コスト
を外す処理を行う。ネットＡの配線処理を行い、なおネ
ットＡに未配線の端子がある場合には再び端子保護コス
トが設定される。

【００３１】次に図２のフローチャートを参照して、本
発明に係る自動配線方法の処理を説明する。なお、図２
のステップ101、107は図１の端子保護コスト設定部１で
処理され、ステップ103は端子保護コスト削除部２で処
理される。また、ステップ104〜106、108は配線処理部
３で処理され、ステップ104におけるコスト計算は配線
経路コスト計算部４で処理される。

【００３２】まず、全てのネットの未配線の端子の付近
に端子保護コストを設定する（ステップ101）。

【００３３】次にステップ102から108までの処理を未配
線のネットがある限り繰り返す。ステップ102で未配線
のネットがあるか否かを判定し、未配線のネットがなけ
れば終了する（ステップ109）。

【００３４】一つのネットの配線をするに当たり、まず
配線するネットの端子に関する端子保護コストを削除す
る（ステップ103）。これはそのネット自身の配線を行
う際には、配線経路が端子へ近づくのを妨げる必要はな
いためである。

【００３５】次にコスト付き迷路法などの配線方法を用
いてコスト最小の経路を探索する（ステップ104）。こ
のとき、端子保護コストの設定されている領域を配線が
通る場合は、その領域を通過する距離（格子数など）、
保護コストの種類に応じてコストを加算する。

【００３６】端子が配線禁止や他ネットの配線で囲まれ
ている場合などは配線経路が見つからないことがある
が、その場合には未配線の処理を行う（ステップ10
8）。ステップ108の未配線の処理としては、他ネットの
配線を取り外してから、配線対象のネットを配線すると
いう引剥し配線法等がある。引剥し配線法では、配線対
象のネット（「ネットＡ」という）に対して、ネットＡ
の配線を妨げている他のネットあるいはネット群Ｂを全
て引剥し、その後にネットＡの配線を行なう。この場
合、ネットＡに対する障害は除かれているため、ネット
Ａの配線は確実に行なえる。なお、ネットＡがネットＢ
の配線の障害となることを回避すべく、ネットＡを配線
する際には、ネットＢに所定の端子保護コストを設定し
ておき、ネットＡの配線が完了した後に、ネットＢの配
線が行なわれる。

【００３７】配線経路が見つかった場合は、配線経路を
記録する（ステップ106）。

【００３８】最後に次のネットの配線のために現在のネ
ットのうち配線し残した端子、即ち未配線の端子につい
て端子保護コストを設定する（ステップ107）。端子数
が２つのネットについては、ステップ102〜106の処理で
配線が完了し、互いに接続された端子は同電位となる
が、３つ以上の端子を有するネットについては、ステッ
プ102〜106の処理を複数回繰り返して配線処理が完了す
ることになる。従って、ステップ106の処理終了後にお
いて、ネットの配線が完了していない場合には、ネット
の未配線端子に対して端子保護コストを設定する。この
ネットの配線が完了していれば端子保護コストの設定は
行われない。

【００３９】

【実施例の作用効果】次に、具体的な配線例を用いて、
本発明の実施例の効果を説明する。ある配線領域に関し
て、（Ａ）端子保護を設定しないで配線をする、（Ｂ）
端子保護のために配線禁止を設定して配線する、（Ｃ）
端子保護のため端子保護コストを設定して配線する、の
各方法について比較する。（Ｃ）が本発明の方法に対応
し、（Ｂ）は特開平3-274751号公報に開示されている方
法に対応している。

【００４０】表１に比較結果を掲げる。表１に示すよう
に、端子保護を行わない配線（Ａ）では３本のネットが
配線できなかった。これは他ネットの２層配線が１層端
子の上を通ったため端子に配線が接続出来なくなったた
めである。配線長の比較を行うため、未配線ネットは最
後に他のネットとの重なりを許して配線した。

【００４１】端子の保護を行う方法（Ｂ）、（Ｃ）では
いずれも未配線はなかった。しかしながら、表１に示す
ように、方法（Ｃ）は方法（Ｂ）よりも配線長が短く、
ビア数が少ない。このような比較結果が出た理由を図
４、図５の実際の配線結果を用いて説明する。

【００４２】図４は、従来方法（Ｂ）による配線結果で
あり、図５は本発明の方法（Ｃ）による配線結果であ
る。図４及び図５において、太い実線は第２金属層配
線、破線は第１金属層配線、×印は、第１、第２金属層
の間を接続するスルーホールをそれぞれ表しており、配
線206、209は既に配線済みの配線を表している。

【００４３】図４を参照して、従来方法（Ｂ）の配線を
説明する。図４において、着目するのは、端子201と端
子202を結ぶネット（「ネットＮ」という）である。こ
のネットの配線時には、まだ端子203には配線が接続さ
れていないため、端子203の近傍に端子保護のための配
線禁止領域204が設定されている。配線禁止領域204は端
子203の配線引き出し方向（即ち縦方向）に数格子分だ
け設定されている。このためネットＮの配線経路とし
て、図示のように、配線経路205が選ばれる。配線経路2
05は配線禁止領域204を避けるため、最端距離よりも２
格子分長い経路になっている。

【００４４】一方、図５では、同じく未配線の端子203
から所定範囲内にある領域207（「端子保護領域」とも
いう）に端子保護のコストが設定される。即ち、図５に
示す本発明の配線方法では、端子保護のコストは配線長
２格子分より小さい値が設定されている。例えば、配線
長１格子分のコストを４とし、端子保護のコストを１格
子について５とする。即ち、第１金属層にある端子203
に対する端子保護のコストとして、端子203の位置から
垂直方向に２格子以内にある第２金属層の格子に対して
大きさ５のコストを設定している。

【００４５】すると、２格子分長い配線（コストは８）
をするよりも、端子保護領域207に１格子分入り込んで
配線する方が総コストが３だけ小さいため、208の経路
がネットＮの経路として選ばれる。仮に、端子保護領域
207の内部に２格子分だけ入り込むものとすると、総コ
ストは、図４の配線経路206よりも２だけ大きくなるた
め、このような経路は採用されない。

【００４６】図４の配線経路と図５の配線経路を比較す
ると、両者は、ビア数が等しく、ともに端子203の近傍
を避けて配線されているが、図５の経路208の方が配線
長が、図４の配線経路206よりも２格子だけ短く、図５
の経路の方が良好な配線経路であるといえる。

【００４７】一般に配線長が短く、ビア数が少ない方が
良好な配線経路とされる。なぜならば、配線長が短けれ
ば短いほど、全てのネットの配線を小さな面積内に収め
ることができるため、集積回路の面積を小さくすること
ができるためである。

【００４８】配線方法（Ａ）が最も配線長が短く、ビア
数が少ないが、これは未配線で残った３本のネットに関
しては他のネットとの重なりを許して配線したもので、
実際には製造に用いることのできない結果である。

【００４９】すなわち、本発明の自動配線方法は端子を
保護するコストを用いることにより未配線のない配線を
行うことができると共に、従来の配線方法（Ｂ）のよう
に配線長、及びビア数を極度に大きくすることがないと
いう効果がある。

【００５０】以上、本発明を、配線格子を用いた迷路法
の実施態様に即して説明したが、本発明は、これらの態
様にのみ限定されるものではなく、本発明の原理に準ず
る各種態様を含むものである。例えば本発明は前記の如
く、クリッドレス配線、線分探索法等にも同様にして適
用可能でる。

【００５１】

【表１】

【００５２】

【発明の効果】以上説明したように、本発明の配線コス
ト決定方法は、端子の周りに配線禁止を設けて他ネット
の配線が端子への配線を妨げることを防止する従来の配
線方法に比べて、同等以上の配線完了率を達成しなが
ら、ビア数も少なく配線できるという効果を奏する。

【００５３】また、本発明の自動配線方法によれば、端
子からの距離に依存したコスト関数に基づき、配線全体
のコストが小さくなる場合には端子保護領域にも配線を
引き込むように経路が選択される事により、高い配線完
了率を確保すると共に、従来方法よりも短い配線長で、
且つビア数の少ない、質の高い配線を可能とし、配線面
積が少なくて済むという効果を奏する。さらに、請求項
４に規定される本発明の自動配線方法によれば、上記効
果に加えて、配線処理を効率化して配線時間の短縮化を
達成する。

【図面の簡単な説明】

【図１】本発明の一実施例の構成を表すブロック図であ
る。

【図２】本発明の一実施例の動作を表すフローチャート
である。

【図３】本発明における端子保護コストの設定例を示す
図である。

【図４】従来の方法による配線結果を示した図である。

【図５】本発明の一実施例による配線結果を示した図で
ある。

【図６】従来の迷路法による配線の一例を示す図であ
る。

【符号の説明】

１端子保護コスト設定部２配線処理部３配線経路コスト計算部４端子保護コスト削除部 10 端子 101〜109 フローチャート中の処理 200 機能ブロック 201、202、203 端子 204 配線禁止領域 207 端子保護コスト領域 205、206、208、209 配線経路

Claims

【特許請求の範囲】

【請求項１】一のネットの配線経路の配線コスト計算に
おいて、他のネットに属する未配線の端子に対して、該
端子からの距離に依存して、前記一のネットの配線経路
のコスト値を可変に割り付けることを特徴とする自動配
線の配線コストの決定方法。
【請求項２】前記端子から遠ざかるにつれて前記コスト
の重みを小さくした請求項１記載の自動配線の配線コス
トの決定方法。
【請求項３】ネットの配線経路を求める際に配線経路の
形状によって決まるコスト値が最も小さくなるような配
線経路を求める自動配線方法において、他のネットの未
配線の端子から所定の範囲内を通る配線経路に対してコ
スト値が大きくなるようなコスト関数を用いることを特
徴とする自動配線方法。
【請求項４】(a)全てのネットについて該ネットの未配
線の端子から所定の範囲内に端子保護コストを設定する
工程と、 (b)未配線のネットがあるか否かを判定し、未配線のネ
ットが無い場合には配線を終了すると共に、未配線のネ
ットが存在する限り次の各工程(c)〜(f)を順次繰返すよ
う制御する工程と、 (c)配線対象の一のネットについて該ネットの未配線の
端子に設定された端子保護コストを解除する工程と、 (d)コスト関数を最小とする配線経路を探索する工程
と、最小コスト配線経路の探索が成功した場合において、 (e)確定したネットの配線経路を記録する工程と、 (f)配線したネットについて該ネットの未配線の端子か
ら所定の範囲内に端子保護コストを設定する工程と、上記各工程から成る自動配線方法。
【請求項５】前記工程(d)において最小コストの配線経
路の探索が失敗した場合において、該配線経路を妨げる
配線を取外して再配線を行なう請求項４記載の自動配線
方法。
【請求項６】前記端子保護コストの設定が、端子からの
距離に依存して値が可変される符号値を配線経路に割り
当てることから成る請求項４記載の自動配線方法。