JPH0620010A - 自動配線装置および方法 - Google Patents
自動配線装置および方法Info
- Publication number
- JPH0620010A JPH0620010A JP4175254A JP17525492A JPH0620010A JP H0620010 A JPH0620010 A JP H0620010A JP 4175254 A JP4175254 A JP 4175254A JP 17525492 A JP17525492 A JP 17525492A JP H0620010 A JPH0620010 A JP H0620010A
- Authority
- JP
- Japan
- Prior art keywords
- wiring
- intersections
- layer
- layers
- path
- 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.)
- Withdrawn
Links
Landscapes
- Internal Circuitry In Semiconductor Integrated Circuit Devices (AREA)
Abstract
(57)【要約】
【目的】多層プリント基板上やＬＳＩ等の集積回路上の
配線を計算機を用いて自動設計する自動配線装置および
方法に関し，高速かつ高品質な自動配線を可能とするこ
とを目的とする。 【構成】配線コストの計算に用いる負荷係数の初期値お
よび交差数の判定処理に用いる所定値を初期化部11によ
り設定し，径路探索部12により，信号の異なる配線パタ
ーン間の交差を認めた径路探索を行う。そして，交差数
処理部13および負荷係数変更部16により，交差数の最大
値またはそれらの総和と所定値との比較および負荷係数
の変更を行い, 交差数を減少させる径路探索を繰り返
す。その後,層割付部17により交差のある配線パターン
を他の層に割り振る。
配線を計算機を用いて自動設計する自動配線装置および
方法に関し，高速かつ高品質な自動配線を可能とするこ
とを目的とする。 【構成】配線コストの計算に用いる負荷係数の初期値お
よび交差数の判定処理に用いる所定値を初期化部11によ
り設定し，径路探索部12により，信号の異なる配線パタ
ーン間の交差を認めた径路探索を行う。そして，交差数
処理部13および負荷係数変更部16により，交差数の最大
値またはそれらの総和と所定値との比較および負荷係数
の変更を行い, 交差数を減少させる径路探索を繰り返
す。その後,層割付部17により交差のある配線パターン
を他の層に割り振る。
Description
【０００１】
【産業上の利用分野】本発明は，プリント基板上やＬＳ
Ｉ等の集積回路上の配線を計算機を用いて自動設計する
自動配線装置および方法に関する。
Ｉ等の集積回路上の配線を計算機を用いて自動設計する
自動配線装置および方法に関する。
【０００２】近年のプリント基板やＬＳＩ等の実装密度
の高密度化に伴い，ＤＡシステムの高性能化が要求され
ている。レイアウト設計においても，超高密度基板の配
線処理において配線率の低下や処理時間の増大が問題に
なっている。
の高密度化に伴い，ＤＡシステムの高性能化が要求され
ている。レイアウト設計においても，超高密度基板の配
線処理において配線率の低下や処理時間の増大が問題に
なっている。
【０００３】また，そのような基板を用いたシステムの
速度は速いことが要求されており，基板の配線パターン
上を通過する電気信号の伝搬時間が短くなることが要求
されている。そのため配線長が短いパターンやビア数が
少ないパターン等を効率よく自動配線する技術が要求さ
れている。
速度は速いことが要求されており，基板の配線パターン
上を通過する電気信号の伝搬時間が短くなることが要求
されている。そのため配線長が短いパターンやビア数が
少ないパターン等を効率よく自動配線する技術が要求さ
れている。
【０００４】
【従来の技術】高い配線率を実現するための方式とし
て，例えば特開平１−１３７３７３号公報に示されてい
る「自動配線方式」がある。この方式では，配線途中に
おいて信号の異なるパターン間の交差を認め，次第に交
差数を減少させることにより，高い配線率を達成できる
ようにしている。
て，例えば特開平１−１３７３７３号公報に示されてい
る「自動配線方式」がある。この方式では，配線途中に
おいて信号の異なるパターン間の交差を認め，次第に交
差数を減少させることにより，高い配線率を達成できる
ようにしている。
【０００５】すなわち，この方式では，配線パターンの
交差を認めて配線処理を行った後，この交差をなくすよ
うに繰り返し配線処理を行って，全体の配線コストを最
小限にすると共に，自動配線率を向上させることを目的
としている。すなわち，次のような構成を採用してい
る。
交差を認めて配線処理を行った後，この交差をなくすよ
うに繰り返し配線処理を行って，全体の配線コストを最
小限にすると共に，自動配線率を向上させることを目的
としている。すなわち，次のような構成を採用してい
る。
【０００６】所定の負荷係数に対応する径路の交差を含
めた配線コストを算出し，その配線コストの小さい径路
を探索する。この径路探索によって探索された径路で交
差するネットがある場合，その旨を通知することによ
り，当初指定した負荷係数を変更し，その負荷係数に基
づいて配線コストを小さくする径路を繰り返し探索す
る。
めた配線コストを算出し，その配線コストの小さい径路
を探索する。この径路探索によって探索された径路で交
差するネットがある場合，その旨を通知することによ
り，当初指定した負荷係数を変更し，その負荷係数に基
づいて配線コストを小さくする径路を繰り返し探索す
る。
【０００７】
【発明が解決しようとする課題】上記「自動配線方式」
では，信号の異なる配線パターン間の交差を記録する必
要がある。そのため，特に多層基板を処理するときに
は，径路探索時に必要とされる一時的なデータ量が非常
に多くなる。したがって，多層基板を処理するときに
は，何層かを１組にして，それぞれの組ごとに処理を行
う方が現実的である。
では，信号の異なる配線パターン間の交差を記録する必
要がある。そのため，特に多層基板を処理するときに
は，径路探索時に必要とされる一時的なデータ量が非常
に多くなる。したがって，多層基板を処理するときに
は，何層かを１組にして，それぞれの組ごとに処理を行
う方が現実的である。
【０００８】しかし，このようにそれぞれの組毎に処理
すると，配線パターンの最適化はそれぞれの組にまとめ
た層の間でのみ行われるため，全層で配線パターンの質
を評価した場合，配線長やビア数について必ずしも最適
化が行われるとは限らないといった問題があった。
すると，配線パターンの最適化はそれぞれの組にまとめ
た層の間でのみ行われるため，全層で配線パターンの質
を評価した場合，配線長やビア数について必ずしも最適
化が行われるとは限らないといった問題があった。
【０００９】また，上記「自動配線方式」は，他の自動
配線方式に比べて処理時間を要することが多く，特に，
層数が多い場合には処理すべき何層か毎の組が多くなる
ので，全層を処理するために必要となる処理時間も増え
ることになるという問題があった。
配線方式に比べて処理時間を要することが多く，特に，
層数が多い場合には処理すべき何層か毎の組が多くなる
ので，全層を処理するために必要となる処理時間も増え
ることになるという問題があった。
【００１０】本発明は上記問題点の解決を図り，上記自
動配線方式をさらに改良することにより，多層基板の配
線に適した自動配線技術を提供することを目的とする。
動配線方式をさらに改良することにより，多層基板の配
線に適した自動配線技術を提供することを目的とする。
【００１１】
【課題を解決するための手段】図１は本発明の原理説明
図である。処理装置１０は，ＣＰＵおよびメモリなどを
備え，層数および端子座標やネット情報を持つネットリ
ストを基に，配線区間の径路を決定する装置である。
図である。処理装置１０は，ＣＰＵおよびメモリなどを
備え，層数および端子座標やネット情報を持つネットリ
ストを基に，配線区間の径路を決定する装置である。
【００１２】初期化部１１は，配線処理のための初期化
を行う処理手段であって，特に配線コストの計算に用い
る負荷係数の初期値および交差数の判定処理に用いる所
定値を設定する処理を行うものである。径路探索部１２
は，設定された負荷係数に基づき，径路の交差を含む配
線のコストを算出し，この配線コストの小さい径路を探
索する処理手段である。
を行う処理手段であって，特に配線コストの計算に用い
る負荷係数の初期値および交差数の判定処理に用いる所
定値を設定する処理を行うものである。径路探索部１２
は，設定された負荷係数に基づき，径路の交差を含む配
線のコストを算出し，この配線コストの小さい径路を探
索する処理手段である。
【００１３】交差数処理部１３は，交差メッセージ送信
部１４と交差数判定部１５とからなる。交差メッセージ
送信部１４は，径路探索部１２によって探索された径路
において，異なるネット間で交差があれば，その交差数
の最大値または各層における交差数の最大値の総和を交
差数判定部１５に伝える。交差数判定部１５は，交差メ
ッセージ送信部１４により伝えられた交差数の最大値ま
たは各層における交差数の最大値の総和が，初期化部１
１により設定された所定値と比較して小さい場合には，
得られた径路を層割付部１７に送出する。また，大きい
場合には，負荷係数変更部１６に交差数を伝えると共
に，径路探索部１２に径路探索を行うように通知する。
部１４と交差数判定部１５とからなる。交差メッセージ
送信部１４は，径路探索部１２によって探索された径路
において，異なるネット間で交差があれば，その交差数
の最大値または各層における交差数の最大値の総和を交
差数判定部１５に伝える。交差数判定部１５は，交差メ
ッセージ送信部１４により伝えられた交差数の最大値ま
たは各層における交差数の最大値の総和が，初期化部１
１により設定された所定値と比較して小さい場合には，
得られた径路を層割付部１７に送出する。また，大きい
場合には，負荷係数変更部１６に交差数を伝えると共
に，径路探索部１２に径路探索を行うように通知する。
【００１４】負荷係数変更部１６は，交差数の最大値ま
たは各層における交差数の最大値の総和が所定値より大
きい場合に，負荷係数を変更し，径路探索部１２に通知
する処理手段である。
たは各層における交差数の最大値の総和が所定値より大
きい場合に，負荷係数を変更し，径路探索部１２に通知
する処理手段である。
【００１５】層割付部１７は，交差数の最大値または各
層における交差数の最大値の総和が所定値以下になった
ならば，交差があるネットの径路を他の各層に割り付け
る処理を行う処理手段である。
層における交差数の最大値の総和が所定値以下になった
ならば，交差があるネットの径路を他の各層に割り付け
る処理を行う処理手段である。
【００１６】交差数処理部１３の判定により，交差数の
最大値または各層における交差数の最大値の総和が所定
値以下になるまで負荷係数を変更して，径路探索部１２
による径路探索を繰り返す。
最大値または各層における交差数の最大値の総和が所定
値以下になるまで負荷係数を変更して，径路探索部１２
による径路探索を繰り返す。
【００１７】これらは以下のように処理する。配線に使
用可能な層数がＬ（Ｌ≧３）であるとき，Ｌより小さい
ｎの層に対して，負荷係数変更部１６により負荷係数を
変更しながら，信号の異なる配線パターン間の交差を認
めて，配線の径路を探索する。この探索によって得られ
た径路の各層における交差数の最大値をＣi （ｉ＝１，
２，…，ｎ）とするとき，これらの各最大値Ｃi が所定
値以下になるまで，径路探索部１２による探索を繰り返
す。すなわち，所定値をＶとすると，Ｃi ≦Ｖになるま
で配線の径路を探索する。
用可能な層数がＬ（Ｌ≧３）であるとき，Ｌより小さい
ｎの層に対して，負荷係数変更部１６により負荷係数を
変更しながら，信号の異なる配線パターン間の交差を認
めて，配線の径路を探索する。この探索によって得られ
た径路の各層における交差数の最大値をＣi （ｉ＝１，
２，…，ｎ）とするとき，これらの各最大値Ｃi が所定
値以下になるまで，径路探索部１２による探索を繰り返
す。すなわち，所定値をＶとすると，Ｃi ≦Ｖになるま
で配線の径路を探索する。
【００１８】また，最大値Ｃi が個別に所定値以下にな
るだけでなく，探索によって得られた径路の各層におけ
る交差数の最大値Ｃi の総和（Ｃ1 ＋Ｃ2 ＋…＋Ｃn ）
が所定値以下になったかどうかを判定することにより，
その各層における交差数の最大値Ｃi の総和が所定値以
下になるまで，配線の径路を探索する処理を繰り返す。
こうして，配線に使用可能な全層数のうちの何層かに
おいて各層における交差数の最大値の総和が全層数以下
の値になるまで交差数を減少させ，その後に，配線に使
用しなかった残りの層に対し，交差のある配線パターン
を割り振ることにより，配線処理を完了する。
るだけでなく，探索によって得られた径路の各層におけ
る交差数の最大値Ｃi の総和（Ｃ1 ＋Ｃ2 ＋…＋Ｃn ）
が所定値以下になったかどうかを判定することにより，
その各層における交差数の最大値Ｃi の総和が所定値以
下になるまで，配線の径路を探索する処理を繰り返す。
こうして，配線に使用可能な全層数のうちの何層かに
おいて各層における交差数の最大値の総和が全層数以下
の値になるまで交差数を減少させ，その後に，配線に使
用しなかった残りの層に対し，交差のある配線パターン
を割り振ることにより，配線処理を完了する。
【００１９】
【作用】一般に，配線処理は配線が実行されるそれぞれ
の層を格子状に区切って行われる。最終的には，この格
子の中に一つの信号線の配線パターンしか置くことがで
きない。上記特開平１−１３７３７３号公報に示されて
いる「自動配線方式」では，配線の途中の過程において
異なる信号線の配線パターンの交差を認めている。した
がって，配線の途中の過程においては，ある層の一つの
格子には複数の信号線の配線パターンが存在することが
ある。このように一つの格子に存在する異なる信号線の
数を交差数と呼ぶ。
の層を格子状に区切って行われる。最終的には，この格
子の中に一つの信号線の配線パターンしか置くことがで
きない。上記特開平１−１３７３７３号公報に示されて
いる「自動配線方式」では，配線の途中の過程において
異なる信号線の配線パターンの交差を認めている。した
がって，配線の途中の過程においては，ある層の一つの
格子には複数の信号線の配線パターンが存在することが
ある。このように一つの格子に存在する異なる信号線の
数を交差数と呼ぶ。
【００２０】本発明では，配線すべき問題を全層数より
少ない層数で配線する。この配線処理において，例えば
各層における交差数の最大値の総和が全層数以下になる
まで，上記「自動配線方式」を適用する。そして，配線
処理時に対象としなかった残りの層に，可能な限り交差
のある配線パターンを割り振る。具体的には，以下のと
おりである。
少ない層数で配線する。この配線処理において，例えば
各層における交差数の最大値の総和が全層数以下になる
まで，上記「自動配線方式」を適用する。そして，配線
処理時に対象としなかった残りの層に，可能な限り交差
のある配線パターンを割り振る。具体的には，以下のと
おりである。
【００２１】与えられた配線問題に使用可能な層数をＬ
（Ｌ≧３），上記「自動配線方式」を適用する層数をｎ
（ｎ＝１，２，…；ｎ＜Ｌ）とする。上記「自動配線方
式」を適用する各層における交差数の最大値をＣi （ｉ
＝１，２，…，ｎ）とし，このＣi が所定値Ｖ以下とな
るようにする。また，Ｃ1 ＋Ｃ2 ＋…＋Ｃn ≦Ｌなる条
件を満たすまで，上記「自動配線方式」を実行する。こ
の後，交差の残っている（Ｃ1 ＋Ｃ2 ＋…＋Ｃn −ｎ）
本の配線パターンを，配線パターンが存在しない（Ｌ−
ｎ）層に割り振っていき，最終的には全層において交差
のないパターンを得る。
（Ｌ≧３），上記「自動配線方式」を適用する層数をｎ
（ｎ＝１，２，…；ｎ＜Ｌ）とする。上記「自動配線方
式」を適用する各層における交差数の最大値をＣi （ｉ
＝１，２，…，ｎ）とし，このＣi が所定値Ｖ以下とな
るようにする。また，Ｃ1 ＋Ｃ2 ＋…＋Ｃn ≦Ｌなる条
件を満たすまで，上記「自動配線方式」を実行する。こ
の後，交差の残っている（Ｃ1 ＋Ｃ2 ＋…＋Ｃn −ｎ）
本の配線パターンを，配線パターンが存在しない（Ｌ−
ｎ）層に割り振っていき，最終的には全層において交差
のないパターンを得る。
【００２２】以上のように，Ｃ1 ＋Ｃ2 ＋…＋Ｃn ≦Ｌ
の条件を満たすまで配線パターンを最適化する。したが
って，単に配線問題を何層かの組に分けて，上記「自動
配線方式」を適用する場合と比較して，配線パターンは
全層にわたり，最適化されることになる。
の条件を満たすまで配線パターンを最適化する。したが
って，単に配線問題を何層かの組に分けて，上記「自動
配線方式」を適用する場合と比較して，配線パターンは
全層にわたり，最適化されることになる。
【００２３】上記「自動配線方式」について，配線問題
を何層かの組に分けて適用する場合の処理時間を考え
る。組数をｍ，各組における層数をｌi （ｉ＝１，２，
…，ｍ；但し，ｌi ≧０，ｌ1 ＋ｌ2 ＋…＋ｌm ＝Ｌ）
とする。このとき，ある組ｉを処理するのに要する時間
をｔi とすると，全層について配線を終了するのに要す
る時間はｔ1 ＋ｔ2 ＋…＋ｔm となる。一方，本発明に
よる処理時間をＴとし，層数ｌi として配線処理を行な
うと，Ｔ≦ｔi となる。したがって，Ｔ≦ｔ1 ＋ｔ2 ＋
…＋ｔm となるから，本発明は処理時間の点でも有利で
ある。
を何層かの組に分けて適用する場合の処理時間を考え
る。組数をｍ，各組における層数をｌi （ｉ＝１，２，
…，ｍ；但し，ｌi ≧０，ｌ1 ＋ｌ2 ＋…＋ｌm ＝Ｌ）
とする。このとき，ある組ｉを処理するのに要する時間
をｔi とすると，全層について配線を終了するのに要す
る時間はｔ1 ＋ｔ2 ＋…＋ｔm となる。一方，本発明に
よる処理時間をＴとし，層数ｌi として配線処理を行な
うと，Ｔ≦ｔi となる。したがって，Ｔ≦ｔ1 ＋ｔ2 ＋
…＋ｔm となるから，本発明は処理時間の点でも有利で
ある。
【００２４】
【実施例】図２は，本発明の実施例処理フローチャート
である。以下，図２に示す処理〜に従って，図１に
示す各部の処理の例について説明する。
である。以下，図２に示す処理〜に従って，図１に
示す各部の処理の例について説明する。
【００２５】 前処理では，初期化部１１により，与
えられたネットリスト（端子情報やネット情報）を，径
路探索部１２が処理する形式に変換したり，径路探索部
１２が配線コストを計算するために用いる負荷係数の初
期化を行う。また，交差数判定部１５で交差数との比較
に用いる値の設定も行う。
えられたネットリスト（端子情報やネット情報）を，径
路探索部１２が処理する形式に変換したり，径路探索部
１２が配線コストを計算するために用いる負荷係数の初
期化を行う。また，交差数判定部１５で交差数との比較
に用いる値の設定も行う。
【００２６】 径路探索部１２により，現在設定され
ている負荷係数を用いて配線コストを算出し，この配線
コストが小さくなる径路を探索して生成する。 交差メッセージ送信部１４により，径路探索部１２
によって生成された径路において異なるネット間で交差
する交差数の最大値を求め，交差数判定部１５に通知す
る。
ている負荷係数を用いて配線コストを算出し，この配線
コストが小さくなる径路を探索して生成する。 交差メッセージ送信部１４により，径路探索部１２
によって生成された径路において異なるネット間で交差
する交差数の最大値を求め，交差数判定部１５に通知す
る。
【００２７】 交差数判定部１５により，異なるネッ
ト間で交差する交差数の最大値が，所定の設定値以下で
あるかどうかを判定し，この条件が成立すれば，次の層
割付処理に移る。そうでない場合には，負荷係数変更
部１６に交差数を伝え，再び径路探索処理を繰り返
す。
ト間で交差する交差数の最大値が，所定の設定値以下で
あるかどうかを判定し，この条件が成立すれば，次の層
割付処理に移る。そうでない場合には，負荷係数変更
部１６に交差数を伝え，再び径路探索処理を繰り返
す。
【００２８】 負荷係数変更部１６により，交差数判
定部１５から通知された交差数によって配線コストを算
出する基になる負荷係数（径路探索処理で用いる）を
変更するか否かを判定し，その負荷係数を必要に応じて
変更する。
定部１５から通知された交差数によって配線コストを算
出する基になる負荷係数（径路探索処理で用いる）を
変更するか否かを判定し，その負荷係数を必要に応じて
変更する。
【００２９】 層割付部１７により，交差数判定部１
５から受け取った径路で交差があるネットの径路を各層
に割り付ける。割り付けた後で交差が残っていれば，そ
の層のデータを基に新しいネットリストを作成し，これ
を初期化部１１に渡す。また，このとき改変したい層の
配線パターンデータとその層数も渡す。各層に配線パタ
ーンを割り付ける方法として，各層における交差数が均
等になるように割り付ける方法や，交差のない層の数を
最小にするといったような方法が考えられる。全ての層
において交差がなくなれば，次の処理である終了処理
へ移る。
５から受け取った径路で交差があるネットの径路を各層
に割り付ける。割り付けた後で交差が残っていれば，そ
の層のデータを基に新しいネットリストを作成し，これ
を初期化部１１に渡す。また，このとき改変したい層の
配線パターンデータとその層数も渡す。各層に配線パタ
ーンを割り付ける方法として，各層における交差数が均
等になるように割り付ける方法や，交差のない層の数を
最小にするといったような方法が考えられる。全ての層
において交差がなくなれば，次の処理である終了処理
へ移る。
【００３０】 終了処理では，得られた径路の情報を
取り出し，出力する。上記径路探索処理における探索
では，配線途中において信号の異なる配線パターン間の
交差を認める配線を行う。その処理では，例えば上記特
開平１−１３７３７３号公報に示されている「自動配線
方式」の技術を用いる。その具体的な処理内容を図３お
よび図４に示す例に従って説明する。
取り出し，出力する。上記径路探索処理における探索
では，配線途中において信号の異なる配線パターン間の
交差を認める配線を行う。その処理では，例えば上記特
開平１−１３７３７３号公報に示されている「自動配線
方式」の技術を用いる。その具体的な処理内容を図３お
よび図４に示す例に従って説明する。
【００３１】配線パターンの交差には，パターンが十字
状に交わる十字クロスと，径路が平行に重なったオーバ
ラップとがある。十字クロスは，一般には相手の端子を
迂回するなどしなければならないので，回避するのが難
しく，これに対しオーバラップは，いずれかの径路を平
行移動させることにより，容易に回避することができる
場合が多い。
状に交わる十字クロスと，径路が平行に重なったオーバ
ラップとがある。十字クロスは，一般には相手の端子を
迂回するなどしなければならないので，回避するのが難
しく，これに対しオーバラップは，いずれかの径路を平
行移動させることにより，容易に回避することができる
場合が多い。
【００３２】図１に示す径路探索部１２は，設定された
負荷係数のもとで，指定された端子座標間の配線（ネッ
ト）が最小の配線コストとなる径路を探索して求めるも
のであるが，この配線コストは，例えば次式に示すコス
ト関数ｆによって算出される。
負荷係数のもとで，指定された端子座標間の配線（ネッ
ト）が最小の配線コストとなる径路を探索して求めるも
のであるが，この配線コストは，例えば次式に示すコス
ト関数ｆによって算出される。
【００３３】ｆ＝α×配線長＋β×ビア数＋γ×十字ク
ロス数＋δ×オーバラップ数 ここで，α，β，γ，δは，各要素に対する負荷係数を
表し，配線長はネットの総配線長さ（総径路長さ），ビ
ア数は配線層を変えるためのビアホールの数，十字クロ
ス数は径路が十字状に交差する数，オーバラップ数は径
路が平行に重なる数を表す。
ロス数＋δ×オーバラップ数 ここで，α，β，γ，δは，各要素に対する負荷係数を
表し，配線長はネットの総配線長さ（総径路長さ），ビ
ア数は配線層を変えるためのビアホールの数，十字クロ
ス数は径路が十字状に交差する数，オーバラップ数は径
路が平行に重なる数を表す。
【００３４】最初，十字クロスに対する負荷係数γを
０，オーバラップに対する負荷係数δを０に初期化し
て，交差を認めた態様で配線コストを最小とする径路を
探索する。
０，オーバラップに対する負荷係数δを０に初期化し
て，交差を認めた態様で配線コストを最小とする径路を
探索する。
【００３５】例えば，図３の（イ）に示すように，端子
Ａ−Ａ，端子Ｂ−Ｂ，端子Ｃ−Ｃを結ぶ配線（ネット）
ＷA ，ＷB ，ＷC をこの順序で行うものとする。負荷係
数をγ＝０，δ＝０として径路を探索し，上記コスト関
数ｆを計算して，配線コストの最小のものを見つける。
これにより，例えば図３の（ロ）に示すような配線パタ
ーンが得られる。ここでは，配線順序のためネットＷA
が，ネットＷB ，ＷCと十字クロスしており，ネットＷ
C が，ネットＷB と十字クロスしているとみる。φは空
集合であって，十字クロスまたはオーバラップしている
ネットがないことを表している。
Ａ−Ａ，端子Ｂ−Ｂ，端子Ｃ−Ｃを結ぶ配線（ネット）
ＷA ，ＷB ，ＷC をこの順序で行うものとする。負荷係
数をγ＝０，δ＝０として径路を探索し，上記コスト関
数ｆを計算して，配線コストの最小のものを見つける。
これにより，例えば図３の（ロ）に示すような配線パタ
ーンが得られる。ここでは，配線順序のためネットＷA
が，ネットＷB ，ＷCと十字クロスしており，ネットＷ
C が，ネットＷB と十字クロスしているとみる。φは空
集合であって，十字クロスまたはオーバラップしている
ネットがないことを表している。
【００３６】この十字クロスをできるだけ回避するた
め，負荷係数γを正の値（例えばγ＝１）に変更して，
同様に探索を繰り返す。これにより，図４の（イ）に示
すような配線パターンが得られる。この配線では，十字
クロスがなくなっているが，ネットＷB がネットＷA と
オーバラップしている。
め，負荷係数γを正の値（例えばγ＝１）に変更して，
同様に探索を繰り返す。これにより，図４の（イ）に示
すような配線パターンが得られる。この配線では，十字
クロスがなくなっているが，ネットＷB がネットＷA と
オーバラップしている。
【００３７】オーバラップを回避する径路探索を行うた
めに，さらに負荷係数をγ＝１，δ＝１とし，コスト関
数ｆに代入して，配線コストの小さい径路を探索する
と，例えば図４の（ロ）に示すような配線パターンが得
られることになる。
めに，さらに負荷係数をγ＝１，δ＝１とし，コスト関
数ｆに代入して，配線コストの小さい径路を探索する
と，例えば図４の（ロ）に示すような配線パターンが得
られることになる。
【００３８】図４の（ロ）に示すように，交差がない配
線パターンを求めることができれば問題はないが，一般
には交差が残ることになり，その交差をできるだけ少な
くするための径路探索には非常に長い処理時間を要する
ことになる。
線パターンを求めることができれば問題はないが，一般
には交差が残ることになり，その交差をできるだけ少な
くするための径路探索には非常に長い処理時間を要する
ことになる。
【００３９】本発明では，この処理を，層ごとの交差数
の最大値または各層における交差数の最大値の総和が所
定値より小さくなるまで行い，所定値より小さくなった
ならば，未使用層への割付処理に移るので，特に時間の
かかる探索処理部分の削減が可能になる。
の最大値または各層における交差数の最大値の総和が所
定値より小さくなるまで行い，所定値より小さくなった
ならば，未使用層への割付処理に移るので，特に時間の
かかる探索処理部分の削減が可能になる。
【００４０】図５および図６は，本発明を全層４層の問
題に適用した例を示す配線例説明図である。図中の丸は
端子を表す。まず，全層４層のうち，第１層と第２層に
対して，上記径路探索により，交差を認めた配線を行
う。このとき，配線パターンの最適化ではそれぞれの層
における交差数の最大値の和が４になるまで処理するも
のとする。
題に適用した例を示す配線例説明図である。図中の丸は
端子を表す。まず，全層４層のうち，第１層と第２層に
対して，上記径路探索により，交差を認めた配線を行
う。このとき，配線パターンの最適化ではそれぞれの層
における交差数の最大値の和が４になるまで処理するも
のとする。
【００４１】この結果が，図５の（イ）に示す配線パタ
ーンである。なお，同図において，実線の配線パターン
は，第１層における配線パターン，点線の配線パターン
は，第２層における配線パターンを表している。図中の
との箇所に交差が存在する。ここで，例えばＰ１と
Ｐ２の配線パターンを他の２層に割り振ることができれ
ば，配線が未結線なしで完了したことになる。
ーンである。なお，同図において，実線の配線パターン
は，第１層における配線パターン，点線の配線パターン
は，第２層における配線パターンを表している。図中の
との箇所に交差が存在する。ここで，例えばＰ１と
Ｐ２の配線パターンを他の２層に割り振ることができれ
ば，配線が未結線なしで完了したことになる。
【００４２】そこで，図５の（イ）に示す配線パターン
Ｐ１，Ｐ２をそれぞれ第３層，第４層へ移す。これによ
り，第１層および第２層の配線パターンは，図５の
（ロ）に示すように，それぞれ交差がないものになる。
図６の（イ）は，この処理結果による第３層における配
線パターン，図６の（ロ）は，第４層における配線パタ
ーンを示している。
Ｐ１，Ｐ２をそれぞれ第３層，第４層へ移す。これによ
り，第１層および第２層の配線パターンは，図５の
（ロ）に示すように，それぞれ交差がないものになる。
図６の（イ）は，この処理結果による第３層における配
線パターン，図６の（ロ）は，第４層における配線パタ
ーンを示している。
【００４３】すなわち，図５の（ロ）および図６の
（イ），（ロ）に示したものが配線が完了した状態を示
している。全層のうちの何層かに配線した後，その各層
において他の残りの層に割り振る配線パターンは，例え
ば次のような手順で選ぶ。
（イ），（ロ）に示したものが配線が完了した状態を示
している。全層のうちの何層かに配線した後，その各層
において他の残りの層に割り振る配線パターンは，例え
ば次のような手順で選ぶ。
【００４４】(1) 配線パターンが交差するネットの中で
端子数が最小のものを選ぶ。 (2) 端子数が最小のものが複数ある場合には，線長が最
小のものを選ぶ。 (3) 線長が最小のものが複数ある場合には，端子の座標
が原点に一番近いものを選ぶ。または，ｘ座標が最小，
ｙ座標が最小のものといった条件を用いて選ぶことが考
えられる。
端子数が最小のものを選ぶ。 (2) 端子数が最小のものが複数ある場合には，線長が最
小のものを選ぶ。 (3) 線長が最小のものが複数ある場合には，端子の座標
が原点に一番近いものを選ぶ。または，ｘ座標が最小，
ｙ座標が最小のものといった条件を用いて選ぶことが考
えられる。
【００４５】図５の（イ）に示す例では，で交差する
配線パターンについてＰ１の配線パターンが，上記条件
(1) に該当するので選択される。また，で交差する配
線パターンについては，交差するパターンがともに上記
条件(1) を満たすので，次の条件(2) が調べられ，これ
によりＰ２の配線パターンが選択される。
配線パターンについてＰ１の配線パターンが，上記条件
(1) に該当するので選択される。また，で交差する配
線パターンについては，交差するパターンがともに上記
条件(1) を満たすので，次の条件(2) が調べられ，これ
によりＰ２の配線パターンが選択される。
【００４６】
【発明の効果】以上説明したように，本発明によれば，
超高密度多層プリント基板等を自動配線するにあたっ
て，従来方式により数層ずつ処理する場合に比べて，高
速かつ高品質な配線を行うことが可能になる。
超高密度多層プリント基板等を自動配線するにあたっ
て，従来方式により数層ずつ処理する場合に比べて，高
速かつ高品質な配線を行うことが可能になる。
【図１】本発明の原理説明図である。
【図２】本発明の実施例処理フローチャートである。
【図３】本発明の実施例に係る径路探索説明図である。
【図４】本発明の実施例に係る径路探索説明図である。
【図５】本発明の実施例に係る配線例説明図である。
【図６】本発明の実施例に係る配線例説明図である。
１０ 処理装置 １１ 初期化部 １２ 径路探索部 １３ 交差数処理部 １４ 交差メッセージ送信部 １５ 交差数判定部 １６ 負荷係数変更部 １７ 層割付部
Claims (4)
- 【請求項１】 計算機によって配線区間の径路を決定す
る自動配線装置において， 配線コストの計算に用いる負荷係数の初期値および交差
数の判定処理に用いる所定値を設定する初期化部(11)
と， 設定された負荷係数に基づき，径路の交差を含む配線の
コストを算出し，この配線コストの小さい径路を探索す
る径路探索部(12)と， 前記径路探索部によって探索された径路において，異な
るネット間で交差がある場合に，その交差数の最大値ま
たは各層における交差数の最大値の総和と前記初期化部
により設定した交差数の判定処理に用いる所定値とを比
較する交差数処理部(13)と， 交差数の最大値または各層における交差数の最大値の総
和が所定値より大きい場合に，負荷係数を変更し，前記
径路探索部に通知する負荷係数変更部(16)と， 交差数の最大値または各層における交差数の最大値の総
和が所定値以下になったならば，交差があるネットの径
路を他の各層に割り付ける処理を行う層割付部(17)とを
備え， 交差数の最大値または各層における交差数の最大値の総
和が所定値以下になるまで負荷係数を変更して，前記径
路探索部による径路探索を繰り返すようにしたことを特
徴とする自動配線装置。 - 【請求項２】 ３以上の層に対して計算機により配線を
行う自動配線方法において， 配線に使用可能な層数がＬ（Ｌ≧３）であるとき，Ｌよ
り小さいｎの層に対して，信号の異なる配線パターン間
の交差を認めた状態での配線パターンの径路を探索する
処理過程と， 探索によって得られた径路の各層における交差数の最大
値をＣi （ｉ＝１，２，…，ｎ）とするとき，これらの
各最大値Ｃi が所定値以下になったかどうかを判定する
処理過程とを有し， 各層における交差数の最大値Ｃi が所定値以下になるま
で，配線の径路を探索する処理を繰り返すことを特徴と
する自動配線方法。 - 【請求項３】 ３以上の層に対して計算機により配線を
行う自動配線方法において， 配線に使用可能な層数がＬ（Ｌ≧３）であるとき，Ｌよ
り小さいｎの層に対して，信号の異なる配線パターン間
の交差を認めた状態での配線パターンの径路を探索する
処理過程と， 探索によって得られた径路の各層における交差数の最大
値をＣi （ｉ＝１，２，…，ｎ）とするとき，これらの
各最大値Ｃi の総和（Ｃ1 ＋Ｃ2 ＋…＋Ｃn ）が所定値
以下になったかどうかを判定する処理過程とを有し， 各層における交差数の最大値Ｃi の総和が所定値以下に
なるまで，配線の径路を探索する処理を繰り返すことを
特徴とする自動配線方法。 - 【請求項４】 請求項２または請求項３記載の自動配線
方法において， 配線に使用可能な全層数のうちの何層かにおいて各層に
おける交差数の最大値の総和が全層数以下の値になるま
で交差数を減少させ， その後に，配線に使用しなかった残りの層に対し，交差
のある配線パターンを割り振ることにより，配線処理を
完了することを特徴とする自動配線方法。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP4175254A JPH0620010A (ja) | 1992-07-02 | 1992-07-02 | 自動配線装置および方法 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP4175254A JPH0620010A (ja) | 1992-07-02 | 1992-07-02 | 自動配線装置および方法 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH0620010A true JPH0620010A (ja) | 1994-01-28 |
Family
ID=15992952
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP4175254A Withdrawn JPH0620010A (ja) | 1992-07-02 | 1992-07-02 | 自動配線装置および方法 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH0620010A (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2009301351A (ja) * | 2008-06-13 | 2009-12-24 | Fujitsu Ltd | 設計支援プログラム、設計支援装置、および設計支援方法 |
-
1992
- 1992-07-02 JP JP4175254A patent/JPH0620010A/ja not_active Withdrawn
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2009301351A (ja) * | 2008-06-13 | 2009-12-24 | Fujitsu Ltd | 設計支援プログラム、設計支援装置、および設計支援方法 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| EP0067304B1 (en) | Processing array and method for the physical design of very large scale integrated circuits | |
| US4615011A (en) | Iterative method for establishing connections and resulting product | |
| EP0612023B1 (en) | Net diagram routing method | |
| US6480996B1 (en) | System and method for transposing wires in a circuit design | |
| US5790414A (en) | Automatic routing method and automatic routing apparatus | |
| US6086625A (en) | Method and apparatus for designing a circuit by describing logic design information with a hardware description language | |
| US6496968B1 (en) | Hierarchical wiring method for a semiconductor integrated circuit | |
| US6487707B1 (en) | Layout design system of semiconductor ic device, layout design method of semiconductor ic device and computer-readable recording medium on which programs for allowing computer to execute respective means in the system or respective steps in the method are recorded | |
| JPH0620010A (ja) | 自動配線装置および方法 | |
| US6615401B1 (en) | Blocked net buffer insertion | |
| JP3229235B2 (ja) | 配線整形方法及び装置、禁止領域半径決定方法及び装置 | |
| JP3538158B2 (ja) | 自動配線装置 | |
| US7389486B2 (en) | Arc routing system and method | |
| JP2938910B2 (ja) | 三次元配線方法 | |
| JP3123387B2 (ja) | 配線パターン決定方法 | |
| JPH06349947A (ja) | 半導体集積回路装置のマスクパターン設計方法および設計装置 | |
| JPH10283378A (ja) | 部品自動配置方法 | |
| JPS62115574A (ja) | 並列配線方式 | |
| JPH05121546A (ja) | 半導体集積回路のレイアウト方法 | |
| JP3165217B2 (ja) | 半導体論理集積回路におけるレイアウト設計方法および装置 | |
| JPH0450627B2 (ja) | ||
| JPH0327589A (ja) | 多層配線方法 | |
| JPH10256375A (ja) | 集積回路装置のためのセル配置方法 | |
| JP2000012695A (ja) | 集積回路のレイアウト方法および半導体装置の製造方法 | |
| JP2000208633A (ja) | 自動配線装置及び方法 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A300 | Application deemed to be withdrawn because no request for examination was validly filed |
Free format text: JAPANESE INTERMEDIATE CODE: A300 Effective date: 19991005 |