JP2858566B2

JP2858566B2 - 自動配線方法

Info

Publication number: JP2858566B2
Application number: JP8215640A
Authority: JP
Inventors: 信康油井; 博義山崎
Original assignee: Nippon Electric Co Ltd
Current assignee: NEC Corp
Priority date: 1996-08-15
Filing date: 1996-08-15
Publication date: 1999-02-17
Anticipated expiration: 2016-08-15
Also published as: JPH1063697A; US6011912A

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明はレイアウト設計方法
に関するものである。

【０００２】

【従来の技術】従来の技術について図面を参照して説明
する。図１２は本発明の配線モデルである。配線領域５
１を、細い破線５２で区切られた矩形領域に分割する。
この矩形領域を格子点といい、また格子点の縦あるいは
横方向の連なりを配線トラックという。四角形５３，５
４，５５は端子である。また領域の境界部５６は領域５
１の外に繋がるある種の端子であり、仮想端子という。

【０００３】接続すべき端子の組をネットといい、ネッ
トの配線経路は格子点の並びとして表現される。例えば
端子５３と端子５４からなるネットの配線は５７と５
８、端子５５と仮想端子５６からなるネットの配線は５
９である。５７，５８，５９のような線分を配線セグメ
ントという。網掛けのある格子点６０は配線禁止領域で
ある。

【０００４】本モデルは複数の配線層を許す。図では第
１層の配線５７，５９を太い実線で、第２層の配線５８
を太い破線で示している。複数の層の配線を含む格子点
にはそれらを繋ぐスルーホールが設けられるが、図面上
では省略されている。

【０００５】図１３は従来の技術を説明するためのフロ
ーチャートである。おおまかに分けて仮経路探索処理と
経路確定処理を行なう。

【０００６】最初に初期設定を行ない（ステップ６
１）、全ネットについて、最も近い２端子間の配線経路
を個別に求める。端子が複数ある場合でも最も近い２端
子のみ経路を求める（ステップ６２）。この時、配線中
のネット以外のネットの配線は障害物とみなさず、それ
らとの間にショートやスペーシングの違反が生じること
を気にしていないため、求めた配線経路を仮経路とい
う。また、以下ではこのようにネットの配線間に違反が
生じた状態を衝突という。仮経路は経路確定処理時に変
更される場合がある。

【０００７】全ネットについて仮経路を求めたら、その
経路の形状に応じてネットに対しコストづけを行ない、
コストの昇順にネットを待ち行列に挿入する（ステップ
６３）。通常、配線長が短くスルーホールが少ないネッ
トわほど待ち行列の前の方に列べられる。

【０００８】これより待ち行列から１ネットずつ取り出
して経路確定処理を行なう。まず待ち行列を確認し、空
ならば全ネットの配線が完了しているので終了する（ス
テップ６４）。完了していなければ待ち行列先頭のネッ
トを取り出し（ステップ６５）、そのネットの仮配線が
他の確定済の配線と衝突していなければ、その経路を確
定する（ステップ６６，６７）。

【０００９】ステップ６７で経路を確定しても、端子が
二つ以上あるネット（多端子ネット）ではまだ接続され
ていない端子が存在する。もしまだ接続されていない端
子があるなら、確定した経路も一つの大きな端子とみな
した上で、最も近い２端子間の仮経路を求め（ステップ
７１）、ステップ６２と同様に待ち行列に入れる（ステ
ップ７２）。そしてステップ６４に戻る。

【００１０】ステップ６６で、もし他の確定済の配線と
衝突していたら、今度は確定済の配線との衝突を許さず
に、最も近い２端子間の仮経路を求め（ステップ６
９）、待ち行列に入れる（ステップ７０）。そしてステ
ップ６４に戻る。

【００１１】ステップ６９でもし衝突を許さない配線経
路が発見できないならば、このネットは引き剥し再配線
や手動による修正によらなければ配線することができな
い。以上を実現する従来技術を説明した文献として、Ｉ
ＥＥＥＴＲＡＮＳＡＣＴＩＯＮＳＯＮＣＯＭＰＵ
ＴＥＲ−ＡＩＤＥＤＤＥＳＩＧＮ，ＶＯＬ．ＣＡＤ−
６，ＮＯ．６，ＮＯＶＥＭＢＥＲ１９８７に記載の
“ＡＤｅｔａｉｌｅｄＲｏｕｔｅｒＢａｓｅｄｏ
ｎＩｎｃｒｅｍｅｎｔａｌＲｏｕｔｉｎｇＭｏｄｉ
ｆｉｃａｔｉｏｎｓ：Ｍｉｇｈｔｙ”がある。なお、ネ
ットを配線する順番決めで配線長制約を考慮するように
したものとして、特開平５−１０１１４７号公報の方法
があるが、これは配線率の向上を実現するものではな
い。

【００１２】

【発明が解決しようとする課題】第１の問題点は、仮配
線の配線長が短いものやスルーホール数が少ないものか
らネットの経路確定を行なっていくと、迂回、折れ曲が
り配線が生じる場合があるということである。以下、図
１４を参照してその理由を説明する。尚、ここでは配線
層は２層からなり、網のかかった領域７３は第１層の配
線禁止領域であるとする。

【００１３】従来の方法では配線しようとするネットを
個別にしか扱っていないため、図１４（ａ）のように仮
経路に衝突７４が起こったネットを、確定する順番に不
都合が生じる場合がある。以下では、従来手法で用いる
コスト値は格子点間（あるいは格子点と仮想端子間）の
長さを１とした時の、仮配線長であるものとして説明す
る。するとこの例では、ネット７５のコストは５、ネッ
ト７６のコストは７と計算され、ネット７５の方がコス
トが小さかったため、ネット７５を確定してから７６を
確定する。７６を確定する時点では７５を避けて配線し
なければならないので、図１４（ｂ）のように迂回配線
による配線長と折れ曲がりの増加が起こるのである。し
かしこの例では、７６を先に確定していれば迂回配線な
しで配線することができるのである。

【００１４】第２の問題点は、上記した第１の問題点の
結果として、未配線（引き剥し再配線などの手法によら
なければ配線を完了することができない配線のことをい
う。）が生じやすくなることである。以下、図１５を参
照してその理由を説明する。ここでも配線層は２層から
なり、網のかかった領域７７，７８は第１層の配線禁止
領域であるとする。

【００１５】図１５（ａ）の衝突７９が起こっている仮
配線について、従来の方法でコストづけを行なうと、例
えばネット８０が５、ネット８１が５、ネット８２が７
となり、配線を確定する順序は８０，８１，８２になっ
たとする。この順番では、８２を確定しようとした時に
は図１５（ｂ）のように既に１層も２層も他の配線によ
って塞がれてしまっている。よってこの配線はどのよう
に他のネットを回避しても引ききれず、未配線となって
しまう。

【００１６】さらに、未配線が生じると、引き剥し再配
線や人手による配線の修正が必要となり、自動レイアウ
トによって意図した集積度が得られなかったり、修正に
よる処理時間の増大を招いたりする。

【００１７】

【課題を解決するための手段】本発明は、単に仮配線の
配線長やスルーホール数をもとにネットの確定順序を決
定するだけではなく、ネットの衝突が起こった場合は、
衝突を回避しやすいネットを後から確定するようにネッ
トを順序づけるようにすることを特徴とする。本発明に
よれば、ＬＳＩおよびプリント基板のレイアウト設計に
おいて、データ入力装置にて配線レイアウト設計情報の
データを入力し、前記配線レイアウト設計情報を記憶手
段にて記憶し、該記憶手段にて記憶された前記配線レイ
アウト設計情報を参照しながら仮配線手段にて全ネット
の仮配線を行ない、前記配線順序決定手段にてそれらの
仮経路の確定順序を計算してから、配線経路確定手段に
てその順に従って確定処理を行ない、前記仮配線にネッ
トの重なり等が生じた場合、それを回避しやすいネット
を後から確定するようにネットを順序づけることを特徴
とする自動配線方法が得られる。

【００１８】さらに、本発明によれば、前記配線レイア
ウト設計情報として、デザインルール情報、ネットリス
ト情報、端子情報、禁止情報、既配線情報、及び仮配線
情報を用い、前記記憶手段が、前記デザインルール情報
を記憶するデザインルール情報記憶部と、前記ネットリ
スト情報を記憶するネットリスト情報記憶部と、端子情
報を記憶する端子情報記憶部と、禁止情報を記憶する禁
止情報記憶部と、既配線情報を記憶する既配線情報記憶
部と、仮配線情報を記憶する仮配線情報記憶部を具備し
て構成されていることを特徴とする自動配線方法が得ら
れる。

【００１９】さらに、本発明によれば、前記データ入力
装置から与えられたデザインルール情報、ネットリスト
情報、端子情報、禁止情報、並びに既配線情報を参照し
ながら、前記仮配線手段により全ネットの仮配線を行な
った後、前記配線順序決定手段を用いてネットを処理す
る順番を決め、ネットにまったく衝突がなければ、前記
配線経路確定手段にて配線が短いネットから処理して経
路を確定し、衝突箇所が見つかった場合は、それら衝突
したネットを比較し、より衝突を回避しやすいと判断さ
れたネットが先に配線されるようになっている場合は、
待ち行列先頭のネットを取り出し中での相対位置を入れ
換えて、そのネットを後回しにし、相対位置を入れ換え
てそのネットを後回しにすることを特徴とする自動配線
方法が得られる。さらに、本発明によれば、多端子ネ
ットの新たな仮配線を行なった場合は、前記配線順序確
定手段を適用して待ち行列の適切な位置にこのネットを
挿入し、もし他の確定済の配線と衝突していた場合は、
今度は確定済の配線との衝突を許さずに、最も近い２端
子間の仮経路を求め、待ち行列に入れることを特徴とす
る自動配線方法が得られる。

【００２０】さらに、本発明によれば、前記ネットの重
なり回避の判断基準として、重なりの生じた配線セグメ
ントの両端の形状を用いることを特徴とする自動配線方
法が得られる。

【００２１】さらに、本発明によれば、前記ネットの重
なり回避の判断基準として、重なりの生じた配線セグメ
ントの長さを用いることを特徴とする自動配線方法が得
られる。

【００２２】さらに、本発明によれば、前記ネットの重
なり回避の判断基準として、重なりの生じた配線セグメ
ントまでの端子からの配線長を用いることを特徴とする
自動配線方法が得られる。

【００２３】さらに、本発明によれば、前記ネットの重
なり回避の判断基準として、重なりの生じた配線セグメ
ントを並行移動して回避できる幅を用いることを特徴と
する自動配線方法が得られる。

【００２４】さらに、本発明によれば、前記ネットの重
なり回避の判断基準として、重なりの生じた配線セグメ
ントの両端の形状、重なりの生じた配線セグメントの長
さ、重なりの生じた配線セグメントまでの端子からの配
線長、及び重なりの生じた配線セグメントを並行移動し
て回避できる幅の任意の組み合わせを用いることを特徴
とする自動配線方法が得られる。

【００２５】

【発明の実施の形態】以下、本発明の一実施の形態につ
いて図面を参照して説明する。図１は、本発明の一実施
の形態を示すブロック図である。

【００２６】本実施の形態は、データ入力装置１と、自
動配線装置２と、記憶装置３と、データ出力装置４とか
ら構成される。自動配線装置２は、仮配線手段５と、配
線順序決定手段６と、配線経路確定手段７とを備える。
記憶装置３は、デザインルール情報記憶部８と、ネット
リスト情報記憶部９と、端子情報記憶部１０と、禁止情
報記憶部１１と、既配線情報記憶部１２、及び一時的な
記憶装置としての仮配線情報記憶部１３とを備えてい
る。

【００２７】次に、図１および図２を用いて、本実施の
形態の動作について説明する。データ入力装置１から与
えられたデザインルール情報、ネットリスト情報、端子
情報、禁止情報、ならびに既配線情報を参照しながら、
仮配線手段５により全ネットの仮配線を行なう（ステッ
プ１５）。ここでは他のネットの仮配線を障害物として
考慮していないので、仮配線はショート等の違反を起こ
している場合がある。

【００２８】次に、配線順序決定手段６を用いてネット
を処理する順番を決め、全ネットを待ち行列に入れる
（ステップ１６）。まず待ち行列を確認し、空ならば全
ネットの配線が完了しているので終了する（ステップ１
７でＹＥＳ）。完了していなければ、待ち行列先頭のネ
ットを取り出し（ステップ１８）、配線経路確定手段７
にて経路確定処理を行う。ネットにまったく衝突がなけ
れば、従来と同様に配線経路確定手段７にて配線が短い
ネットから処理して経路を確定する（ステップ１７，１
８，１９，２０）。ステップ１９で衝突箇所が見つかっ
た場合は、それら衝突したネットを比較する。もし、よ
り衝突を回避しやすいと判断されたネットが先に配線さ
れるようになっている場合は、ネットの待ち行列中での
相対位置を入れ換えて、そのネットを後回しにする。

【００２９】相対位置を入れ換える列を示す。待ち行列
を表した図３（ａ）において、衝突したネットの組２
７，２８を見つけ出したとする。現在は待ち行列の先頭
２６よりにネット２７が、それより後ろにネット２８が
列んでいる。どちらがより衝突を回避しやすいかを判定
したところ、それがネット２７だったなら、ネット２８
を先に、ネット２７を後から確定するため、同図（ｂ）
のようにこれらを入れ換えれば、処理する順序を逆にす
ることができる。

【００３０】実際には３本以上のネットが互いに衝突し
あっている場合があるが、これらの順序を入れ換えるに
は、トポロジカルソートのようなアルゴリズムを用いれ
ばよい。ただし多端子ネットの新たな仮配線を行なった
場合は、また配線順序確定手段６を適用して待ち行列の
適切な位置にこのネットを挿入する（ステップ２４，２
５）。

【００３１】又、ステップ１９で、もし他の確定済の配
線と衝突していたら、今度は確定済の配線との衝突を許
さずに、最も近い２端子間の仮経路を求め（ステップ２
２）、待ち行列に入れ（ステップ２３）、そしてステッ
プ１７に戻る。この時はデザインルールを守って配線す
るため、他の配線との衝突は起こらない。ステップ１７
に戻る。

【００３２】本発明では、衝突回避のしやすさの判断基
準に以下を用いる。第１の判断基準は衝突を起こした配
線セグメントの両端の形状であり、第２の判断基準は衝
突を起こした破線セグメントの長さであり、第３の判断
基準は衝突を起こした配線セグメントまでの端子からの
配線長であり、第４の判断基準は衝突を起こした配線セ
クメントを並行移動して回避できる幅であり、第５の判
断基準は前記第１〜第４の判断基準の組み合わせであ
る。

【００３３】これらの第１〜第５の判断基準について以
下の実施例で詳細に説明する。尚、本発明はチャネルル
ータと違って完全な解を見つけるものではない。チャネ
ルルータは、配線領域と複数のネットが与えられた時
に、グラフ理論の手法等を用いてこれらネットの端子間
を重なりなしに配線する方法であるが、扱うモデルの制
限が強いため、本発明で対象としているような配線問題
には適用できない。

【００３４】

【実施例】衝突を起こした配線セグメントの両端の形状
から順序を判断する実施例（以下、第１の実施例と呼
ぶ）を説明する。

【００３５】まず衝突したセグメントを見つけ出し、そ
れぞれの配線パタンを調べる。配線セグメントの形状と
優先順位の関係をまとめると、以下のようになる。それ
ぞれのパタンの例を図４に示す。丸印がついているセグ
メントが他のネットと衝突を起こしたセグメントであ
る。この分類は一例であり、より細かな分類を適用する
ことも可能である。

【００３６】第１として、配線セグメントの両端が、端
子であるため固定されている場合（同図（ａ））であ
る。第２として、配線セグメントの一方の端が端子であ
るため固定されており、もう一方が、そのセグメントが
属するネットの仮配線または確定済配線である場合（同
図（ｂ））である。第３として、配線セグメントの両端
が、そのセグメントが属すネットの仮配線または確定済
配線であり、かつ、そのセグメントをスライドすること
ができない場合（同図（ｃ））である。第４として、配
線セグメントの両端が、そのセグメントが属すネットの
仮配線または確定済配線であり、かつ、そのセグメント
をスライドすることができる場合（同図（ｄ））であ
る。

【００３７】ここでスライドとは、図５のように、ネッ
トの総配線長を変えることなく、また配線セグメント間
の接続を切ることなく、配線セグメントを並行移動する
操作をいう。

【００３８】この優先順位は、配線セグメントを動かし
て衝突を回避した時に、使用するトラックの数が増加し
たり、配線長が増加したりする可能性の高いものの順に
なっている。特に１は、（ここではＸＹルールに従うも
のとすると）他のネットとの衝突を回避するには必ず折
れ曲がり数、使用するトラック数、配線長の増加が起こ
るので、できるだけ回避を行なわずにこのまま直線で配
線した方がよい。

【００３９】よって、衝突を起こした配線セグメントの
パタンを比較し、上のパタンに属するものほど先に確定
するよう順序づける。なお、同じパタンに属したもの同
士の順序づけは、この実施例では変更しない。

【００４０】この判定基準を使用すると、以下のような
例を解決することができる。図６（ａ）の仮配線は、従
来の手法ではネットを３０，３１の順に確定するため図
１４（ｂ）のように迂回配線されるが、本方法によれ
ば、３０は衝突箇所２９のセグメントをスライドできる
（パタン４）のに対し、縦１本のみの配線からなる３１
は両端が仮想端子になっている（パタン１）ことから、
３１の方が優先されるように確定順序が入れ換えられ
る。その結果、図６（ｂ）のように迂回、折れ曲がりな
しで配線を確定することができる。

【００４１】次に図７（ａ）に示す仮配線を例にとる
と、従来の方法ではネットを３３，３４，３５の順に確
定しようとするため、図１５（ｂ）のように未配線が生
じるが、本方法によれば、前の例と同様に確定順序が３
３，３５，３４のように入れ換えられるため、図７
（ｂ）のように未配線を残さず配線可能である。

【００４２】さらに、高集積化の激しい今日の配線問題
では、これまでの例のように配線領域に余裕はなく、高
い配線密度が要求されている。このような配線問題で
は、ある迂回配線が、また別の箇所の迂回配線の原因と
なって迂回による配線長や折れ曲がりの増加が生じる。
このようにして配線領域が混雑すると、後に確定される
ネットが通るための配線領域がなくなり、未配線が生じ
ることがある。

【００４３】図８はその一例である。同図（ａ）は仮配
線、（ｂ）は従来の方法による配線を表す。ここではネ
ット３７，３８，３９，４０，４１の順にネットを確定
したため、迂回、折れ曲がり配線３８，３９，４０と、
これを原因とする未配線４１が共に生じてしまってい
る。本方法によれば、同図（ｃ）のように迂回、折れ曲
がり配線なしで全ネットを配線可能である。

【００４４】次に、衝突を起こした配線セグメントの長
さから順序を判断する実施例（以下、第２の実施例と呼
ぶ）を説明する。図９（ａ）の仮配線は、いずれも衝突
した配線セグメントをスライドさせることができる形状
をしているので、実施例１の基準では順番は変されな
い。

【００４５】ところが、この例では配線長が短いネット
４３，４４の順に確定すると、同図（ｂ）のように迂回
が生じてしまう。スライドさせようとしても、その位置
に他ネットの端子や配線禁止等が存在したため、実際に
はスライドできなかったからである。さらに、通常長い
配線を確定させる頃には、既に多くの短い配線が確定さ
れているので、長い配線を迂回や折れ曲がりなしにスラ
イドさせることはより困難となる。

【００４６】このように長い配線セグメントが衝突を起
こした場合には、現在の衝突を避けて配線しようとした
時に迂回が必要になったり、多くの折れ曲がりが必要に
なったりする可能性が高くなるので、衝突した配線セグ
メントの長さが長いものを先に、短いものを後に順序づ
ける。同図（ａ）では、衝突した配線セグメントの長さ
はネット４３が１、ネット４４が５であるから、４４は
先に確定し、同図（ｃ）の結果を得ることができる。

【００４７】次に、衝突を起こした配線セグメントまで
の端子からの配線長をもとに順序を判断する実施例（以
下、第３の実施例と呼ぶ）を説明する。図１０（ａ）の
仮配線は配線長が等しいが、ネット４６を先に確定する
と、同図（ｂ）のように迂回が生じてしまう。一般に端
子の近辺は混雑が生じやすく、配線を引き回すのが難し
いため、先に配線しておかないと他のネットを回避して
配線しにくい。

【００４８】よって、衝突したセグメントの両端につい
て、端点から（仮想）端子までの配線長を求め、その短
い方の値を衝突したネット同士で比較する。その結果端
子までの配線長が短い方を先に、長い方を後から順序づ
ける。

【００４９】同図（ａ）では、衝突した配線セグメント
から端子までの配線長はネット４６が２、ネット４７が
１であるから、４７を先に確定し、同図（ｃ）の結果を
得ることができる。

【００５０】次に、上記した第１の実施例に加え、衝突
を起こした配線セグメントを並行移動して回避できる幅
も考慮して順序を判断する実施例（以下、第４の実施例
と呼ぶ）を説明する。

【００５１】図１１（ａ）の仮配線は、やはりいずれも
衝突した配線セグメントをスライドさせることができる
形状をしているので、実施例１の基準では順番は変更さ
れない。しかし、配線長が短いネット４９，５０の順に
確定すると、同図（ｂ）のように迂回配線が生じてしま
う。

【００５２】このような迂回や折れ曲がりが生じること
を少なくするには、配線セグメントをスライドさせるこ
とによって、本当に衝突を回避できるかどうかを見積も
ることが有効である。その一つの方法は、スライドした
いセグメントの両端に繋がる配線の長さの合計（以下ス
ライド幅という）が短い方を先に、長い方を後から確定
することである。スライド幅が短いということは、スラ
イドの移動先の候補が少ないと考えられるからである。

【００５３】この例では、ネット４９のスライド幅が
５、ネット５０のスライド幅が３である。よってスライ
ド幅が短いネット５０を先に確定し、同図（ｃ）の結果
を得ることができる。

【００５４】これまでの実施例は（第４の実施例を除
き）それぞれを独立に扱ってきたが、実際の問題におい
てはこれらの判断基準を組み合わせることが有効であ
る。例えば、まず実施例１の基準で順序づけできるかを
判定し、もしそれだけで順序づけできないのなら、実施
例２，３，４それぞれの配線長の値Ｌ₂，Ｌ₃，Ｌ₄に
重みＷ₂，Ｗ₃，Ｗ₄を掛けて合計した以下の数１に示
す値をネットごとに求め、比較した値がより小さいネッ
トを先に確定するよう順序づけすればよい。（ここでＬ
₄は衝突したセグメントがどちらもスライド可能でなけ
れば０である。）

【００５５】

【数１】長さを評価する時には、一定値以上の場合あるいは以下
の場合にペナルティを与えるような実施方法も考えられ
る。

【００５６】なお、これまでは２層を前提に説明した
が、本発明は３層以上の問題にも拡張できる。また本文
では第１層を横方向配線に、第２層を縦方向配線に用い
る、いわゆるＸＹルールに従った経路を用いて説明して
きたが、ＸＹルールに従わない場合にも本発明は拡張可
能である。

【００５７】

【発明の効果】以上説明したように、本発明によるレイ
アウト方法では、複数のネットの衝突状態を考慮して配
線の確定順序を決めることにより、余分な迂回配線によ
る配線長の増加と折れ曲がりを減少させることができ
る。

【００５８】このことにより後から確定する配線が使用
できる配線トラックの自由度が上がるため、未配線とな
るネットを減少し、自動配線による配線率を向上させる
ことができる。

【００５９】以上のことから自動配線の高集積化とＴＡ
Ｔの短縮という効果が得られる。

【図面の簡単な説明】

【図１】本発明の一実施の形態を示したブロック図であ
る。

【図２】本発明の一実施の形態における自動配線処理を
説明するフローチャート図である。

【図３】本発明の一実施の形態における待ち行列に関す
る図である。

【図４】本発明の実施例で判断に用いる配線パタンの図
である。

【図５】配線セグメントのスライドの図である。

【図６】第１の実施例を示した一レイアウト図である。

【図７】第１の実施例を示した他のレイアウト図であ
る。

【図８】第１の実施例を示したさらに他のレイアウト図
である。

【図９】第２の実施例を示したレイアウト図である。

【図１０】第３の実施例を示したレイアウト図である。

【図１１】第４の実施例を示したレイアウト図である。

【図１２】配線問題のモデルを示したレイアウト図であ
る。

【図１３】従来の一実施の形態における自動配線処理を
説明するフローチャート図である。

【図１４】従来の一問題点を説明するためのレイアウト
図である。

【図１５】従来の他の問題点を説明するためのレイアウ
ト図である。

【符号の説明】

１データ入力装置２自動配線装置３記憶装置４データ出力装置５仮配線手段６配線順序決定手段７配線経路確定手段８デザインルール情報記憶部９ネットリスト情報記憶部１０端子情報記憶部１１禁止情報記憶部１２既配線情報記憶部１３仮配線情報記憶部

───────────────────────────────────────────────────── フロントページの続き (58)調査した分野(Int.Cl.⁶，ＤＢ名) G06F 17/50 ＪＩＣＳＴファイル（ＪＯＩＳ)

Claims

(57)【特許請求の範囲】

【請求項１】ＬＳＩおよびプリント基板のレイアウト
設計において、データ入力装置にて配線レイアウト設計
情報のデータを入力し、前記配線レイアウト設計情報を
記憶手段にて記憶し、該記憶手段にて記憶された前記配
線レイアウト設計情報を参照しながら仮配線手段にて全
ネットの仮配線を行ない、前記配線順序決定手段にてそ
れらの仮経路の確定順序を計算してから、配線経路確定
手段にてその順に従って確定処理を行ない、前記仮配線
にネットの重なり等が生じた場合、それを回避しやすい
ネットを後から確定するようにネットを順序づけること
を特徴とする自動配線方法。
【請求項２】前記配線レイアウト設計情報として、デ
ザインルール情報、ネットリスト情報、端子情報、禁止
情報、既配線情報、及び仮配線情報を用い、前記記憶手
段が、前記デザインルール情報を記憶するデザインルー
ル情報記憶部と、前記ネットリスト情報を記憶するネッ
トリスト情報記憶部と、端子情報を記憶する端子情報記
憶部と、禁止情報を記憶する禁止情報記憶部と、既配線
情報を記憶する既配線情報記憶部と、仮配線情報を記憶
する仮配線情報記憶部を具備して構成されていることを
特徴とする請求項１記載の自動配線方法。
【請求項３】前記データ入力装置から与えられたデザ
インルール情報、ネットリスト情報、端子情報、禁止情
報、並びに既配線情報を参照しながら、前記仮配線手段
により全ネットの仮配線を行なった後、前記配線順序決
定手段を用いてネットを処理する順番を決め、ネットに
まったく衝突がなければ、前記配線経路確定手段にて配
線が短いネットから処理して経路を確定し、衝突箇所が
見つかった場合は、それら衝突したネットを比較し、よ
り衝突を回避しやすいと判断されたネットが先に配線さ
れるようになっている場合は、待ち行列先頭のネットを
取り出し中での相対位置を入れ換えて、そのネットを後
回しにし、相対位置を入れ換えてそのネットを後回しに
することを特徴とする請求項１又は２記載の自動配線方
法。
【請求項４】多端子ネットの新たな仮配線を行なった
場合は、前記配線順序確定手段を適用して待ち行列の適
切な位置にこのネットを挿入し、もし他の確定済の配線
と衝突していた場合は、今度は確定済の配線との衝突を
許さずに、最も近い２端子間の仮経路を求め、待ち行列
に入れることを特徴とする請求項１乃至３のいずれか一
つに記載の自動配線方法。
【請求項５】前記ネットの重なり回避の判断基準とし
て、重なりの生じた配線セグメントの両端の形状を用い
ることを特徴とする請求項１乃至４のいずれか一つに記
載の自動配線方法。
【請求項６】前記ネットの重なり回避の判断基準とし
て、重なりの生じた配線セグメントの長さを用いること
を特徴とする請求項１乃至４のいずれか一つに記載の自
動配線方法。
【請求項７】前記ネットの重なり回避の判断基準とし
て、重なりの生じた配線セグメントまでの端子からの配
線長を用いることを特徴とする請求項１乃至４のいずれ
か一つに記載の自動配線方法。
【請求項８】前記ネットの重なり回避の判断基準とし
て、重なりの生じた配線セグメントを並行移動して回避
できる幅を用いることを特徴とする請求項１乃至４のい
ずれか一つに記載の自動配線方法。
【請求項９】前記ネットの重なり回避の判断基準とし
て、重なりの生じた配線セグメントの両端の形状、重な
りの生じた配線セグメントの長さ、重なりの生じた配線
セグメントまでの端子からの配線長、及び重なりの生じ
た配線セグメントを並行移動して回避できる幅の任意の
組み合わせを用いることを特徴とする請求項１乃至４の
いずれか一つに記載の自動配線方法。