JPH04290171A - 自動配線方式 - Google Patents
自動配線方式Info
- Publication number
- JPH04290171A JPH04290171A JP3054767A JP5476791A JPH04290171A JP H04290171 A JPH04290171 A JP H04290171A JP 3054767 A JP3054767 A JP 3054767A JP 5476791 A JP5476791 A JP 5476791A JP H04290171 A JPH04290171 A JP H04290171A
- Authority
- JP
- Japan
- Prior art keywords
- cell
- wiring
- destination
- starting point
- labeling
- 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
Landscapes
- Design And Manufacture Of Integrated Circuits (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【０００１】
【産業上の利用分野】本発明は、自動配線方式に関し、
特に配線対象であるプリント基板やＬＳＩチップなどの
配線平面を格子状に分割し、この配線平面でのラベル付
け結果に基づいて、出発点セルと目的点セルとの間に指
定配線長の経路を形成するようにした自動配線方式に関
する。
特に配線対象であるプリント基板やＬＳＩチップなどの
配線平面を格子状に分割し、この配線平面でのラベル付
け結果に基づいて、出発点セルと目的点セルとの間に指
定配線長の経路を形成するようにした自動配線方式に関
する。
【０００２】近年の集積回路技術の進歩にともない、プ
リント基板やＬＳＩ等が高密度化され動作速度も向上し
ており、配線パタ−ンによる信号の遅延が無視できず、
配線設計の際にネット（同電位点）の配線長を指定する
ことが必要になっている。本発明は、このような要請に
応えるための自動配線方式に関する。
リント基板やＬＳＩ等が高密度化され動作速度も向上し
ており、配線パタ−ンによる信号の遅延が無視できず、
配線設計の際にネット（同電位点）の配線長を指定する
ことが必要になっている。本発明は、このような要請に
応えるための自動配線方式に関する。
【０００３】従来、自動配線方式の手法として図７に示
すような、格子状の配線平面を用いた迷路法が用いられ
ている。図において、Ｓ，Ｔは自動配線処理対象のネッ
ト対に対応したセルで、Ｓは出発点セル，Ｔは目的点セ
ルを示している。
すような、格子状の配線平面を用いた迷路法が用いられ
ている。図において、Ｓ，Ｔは自動配線処理対象のネッ
ト対に対応したセルで、Ｓは出発点セル，Ｔは目的点セ
ルを示している。
【０００４】ここで、隣接セルにラベル値を伝えてラベ
ル付けを行なう能力を備えた能動セルは最初Ｓ点のみで
あり、先ずＳ点から、このセルの上下左右に位置する４
つの隣接セルにラベル付け、すなわちＳ点自体のラベル
値（例えば、「０」）に各隣接セルの重み（例えば「１
」）を加算した新たなラベル値をそれぞれの隣接セルに
ふることが行なわれる。なお、図示していないが、既に
配線パタ−ンが設定されている配線済セルにはラベル付
けは行なわれない（図２，図３参照）。
ル付けを行なう能力を備えた能動セルは最初Ｓ点のみで
あり、先ずＳ点から、このセルの上下左右に位置する４
つの隣接セルにラベル付け、すなわちＳ点自体のラベル
値（例えば、「０」）に各隣接セルの重み（例えば「１
」）を加算した新たなラベル値をそれぞれの隣接セルに
ふることが行なわれる。なお、図示していないが、既に
配線パタ−ンが設定されている配線済セルにはラベル付
けは行なわれない（図２，図３参照）。
【０００５】次の２ステップ目では、図７（イ）のよう
に、１ステップ目でラベル付けが行なわれたセル（○印
で囲んだ数字の部分）が能動セルとなって、これらの能
動セルから矢印の方向にラベル付けが行なわれ、当該能
動セルの上下左右に位置する隣接セルに新たなラベル値
がふられる。
に、１ステップ目でラベル付けが行なわれたセル（○印
で囲んだ数字の部分）が能動セルとなって、これらの能
動セルから矢印の方向にラベル付けが行なわれ、当該能
動セルの上下左右に位置する隣接セルに新たなラベル値
がふられる。
【０００６】以下、同じ手順でラベル付けが行なわれ、
目的点セルＴにラベル値がふられたときのラベル状態は
図７（ウ）のようになる。続いて、目的点セルＴから出
発点セルＳに向かってラベル値が小さくなるセルを順次
たどっていく（バックトレース）ことにより両セル間の
経路を、例えば実線のように決定する。
目的点セルＴにラベル値がふられたときのラベル状態は
図７（ウ）のようになる。続いて、目的点セルＴから出
発点セルＳに向かってラベル値が小さくなるセルを順次
たどっていく（バックトレース）ことにより両セル間の
経路を、例えば実線のように決定する。
【０００７】このような迷路法によれば、両セル間を結
ぶことができる経路があれば必ず発見でき、またその経
路は両セル間の最短経路となる。そのため、両セル間の
配線長が指定された場合には、迷路法によりいったん求
めた両セル間の経路を迂回させる必要があった。
ぶことができる経路があれば必ず発見でき、またその経
路は両セル間の最短経路となる。そのため、両セル間の
配線長が指定された場合には、迷路法によりいったん求
めた両セル間の経路を迂回させる必要があった。
【０００８】そして、その実現方式としては図８〜図９
に示すような方式がある。図８の方式では、いったん迷
路法によりいったん求めた最短経路の一部のパターンを
引き延ばしている。すなわち、出発点セルＳから目的点
セルＴまでの最短経路２０１ の一部を迂回させること
により、指定された配線長１６になる経路２０２を求め
ている。
に示すような方式がある。図８の方式では、いったん迷
路法によりいったん求めた最短経路の一部のパターンを
引き延ばしている。すなわち、出発点セルＳから目的点
セルＴまでの最短経路２０１ の一部を迂回させること
により、指定された配線長１６になる経路２０２を求め
ている。
【０００９】図９の方式では、迷路法を用いるに先だっ
て、出発点セルＳおよび目的点セルＴの他にこの両セル
間の通過点となるべき中間セル（丸印の部分）Ｍを、出
発点セルＳからこの通過点を通って目的点セルＴにいた
る経路の長さが１６になるようなすべての位置に設定し
ている。
て、出発点セルＳおよび目的点セルＴの他にこの両セル
間の通過点となるべき中間セル（丸印の部分）Ｍを、出
発点セルＳからこの通過点を通って目的点セルＴにいた
る経路の長さが１６になるようなすべての位置に設定し
ている。
【００１０】そして、出発点セルＳと目的点セルＴとの
間の経路を決定するに際し、両セル間を、出発点セルＳ
から任意の中間セルＭまでの部分、およびこの中間セル
Ｍから目的点セルＴまでの部分に分け、それぞれの部分
について迷路法を用いることにより、例えば実線で示し
た両セル間の経路を求めている。
間の経路を決定するに際し、両セル間を、出発点セルＳ
から任意の中間セルＭまでの部分、およびこの中間セル
Ｍから目的点セルＴまでの部分に分け、それぞれの部分
について迷路法を用いることにより、例えば実線で示し
た両セル間の経路を求めている。
【００１１】
【発明が解決しようとする課題】このような従来の方式
は、いずれも既に生成された配線パターンとの位置関係
などが何ら考慮されていないし、また図８の方式では局
所的な修正を行なっているため、新たに求めた経路が他
のネットの経路探索の障害となったり、既存の配線パタ
ーンのために指定配線長の経路を求めることができない
といったケースが増加し、自動配線による配線率が低下
してその後の手作業による配線処理の割合が増えるとい
う問題点があった。
は、いずれも既に生成された配線パターンとの位置関係
などが何ら考慮されていないし、また図８の方式では局
所的な修正を行なっているため、新たに求めた経路が他
のネットの経路探索の障害となったり、既存の配線パタ
ーンのために指定配線長の経路を求めることができない
といったケースが増加し、自動配線による配線率が低下
してその後の手作業による配線処理の割合が増えるとい
う問題点があった。
【００１２】図１０は、出発点セルＳと目的点セルＴと
の間で、指定配線長（＝２０）の経路を求めることがで
きないケースを示している。なお、太い実線部分は既に
生成された配線パターンであり、２０３ は迷路法で求
めた（配線長が１４の）両セル間の経路を示している。
の間で、指定配線長（＝２０）の経路を求めることがで
きないケースを示している。なお、太い実線部分は既に
生成された配線パターンであり、２０３ は迷路法で求
めた（配線長が１４の）両セル間の経路を示している。
【００１３】そこで、本発明では、指定配線長の経路の
通過点として用いる中間セルを、出発点セルと目的点セ
ルそれぞれからのラベル付けの結果に基づいて求めるこ
とにより、この中間セルの位置を、既に生成された配線
パターンとの位置関係を考慮にいれたものにして、両セ
ル間に指定配線長からなる未使用の経路が存在している
場合には必ず発見し、自動配線による配線率を向上させ
ることを目的とする。
通過点として用いる中間セルを、出発点セルと目的点セ
ルそれぞれからのラベル付けの結果に基づいて求めるこ
とにより、この中間セルの位置を、既に生成された配線
パターンとの位置関係を考慮にいれたものにして、両セ
ル間に指定配線長からなる未使用の経路が存在している
場合には必ず発見し、自動配線による配線率を向上させ
ることを目的とする。
【００１４】
【課題を解決するための手段】本発明は、出発点セルか
らの第１のラベル付けと、目的点セルからの第２のラベ
ル付けによるラベル値のそれぞれをセルごとに加えて加
算ラベル値を求め、この加算ラベル値が指定配線長に対
応した値となっている、任意のセルを中間セルとして選
択し、この中間セルから出発点セルと目的点セルのそれ
ぞれにバックトレースを行なって、その後、それぞれの
バックトレースの結果同士を連結して出発点セルと目的
点セルとの間の経路を形成するようにしたものである。
らの第１のラベル付けと、目的点セルからの第２のラベ
ル付けによるラベル値のそれぞれをセルごとに加えて加
算ラベル値を求め、この加算ラベル値が指定配線長に対
応した値となっている、任意のセルを中間セルとして選
択し、この中間セルから出発点セルと目的点セルのそれ
ぞれにバックトレースを行なって、その後、それぞれの
バックトレースの結果同士を連結して出発点セルと目的
点セルとの間の経路を形成するようにしたものである。
【００１５】図１は、本発明の原理説明図である。図に
おいて、Ｓは出発点セル，Ｔは目的点セル，Ｍは中間セ
ルであり、また丸付きの数字は加算ラベル値（の一部）
を示し、 １０１〜１０４ はバックトレースを示して
いる。
おいて、Ｓは出発点セル，Ｔは目的点セル，Ｍは中間セ
ルであり、また丸付きの数字は加算ラベル値（の一部）
を示し、 １０１〜１０４ はバックトレースを示して
いる。
【００１６】そして、出発点セルＳと目的点セルＴ間の
、指定配線長からなる配線経路を求めるフローは次のよ
うになっている。すなわち、■出発点セルＳ，目的点セ
ルＴの位置および指定配線長を指定し、次のステップに
進む。■出発点セルＳからのラベル付けと、目的点セル
Ｔからのラベル付けを実行し、次のステップに進む。 ■それぞれのラベル付けの結果であるラベル値をセルご
とに加算し、次のステップに進む。■この加算ラベル値
が指定配線長（＝１６）になっている任意のセルを中間
セルＭとして選択し、次のステップに進む。■中間セル
Ｍから出発点セルＳへのバックトレースと、中間セルＭ
から目的点セルＴへのバックトレースを実行し、次のス
テップに進む。このとき、例えば１０３および１０４
のように、各バックトレースの一部に同一のセルを重複
して使用することになる場合にはそのバックトレースの
実行を中止し、中間セルＭとして別のセルを選択してバ
ックトレースを新たに実行する。そして、このバックト
レースの繰り返し処理は中間セルＭとしての資格を持つ
すべてのセルに対して行なうことができる。■中間セル
Ｍから、１０３ および１０４ のような、有効なバッ
クトレースがそれぞれ実行されたかどうかを判断し、「
ＹＥＳ」の場合は次のステップに進み、「ＮＯ」の場
合はステップ■に戻る。■各バックトレースの結果同士
を連結し、これを出発点セルＳと目的点セルＴとの間の
経路とする。といった手順により、指定配線長の経路を
両セル間に設定している。
、指定配線長からなる配線経路を求めるフローは次のよ
うになっている。すなわち、■出発点セルＳ，目的点セ
ルＴの位置および指定配線長を指定し、次のステップに
進む。■出発点セルＳからのラベル付けと、目的点セル
Ｔからのラベル付けを実行し、次のステップに進む。 ■それぞれのラベル付けの結果であるラベル値をセルご
とに加算し、次のステップに進む。■この加算ラベル値
が指定配線長（＝１６）になっている任意のセルを中間
セルＭとして選択し、次のステップに進む。■中間セル
Ｍから出発点セルＳへのバックトレースと、中間セルＭ
から目的点セルＴへのバックトレースを実行し、次のス
テップに進む。このとき、例えば１０３および１０４
のように、各バックトレースの一部に同一のセルを重複
して使用することになる場合にはそのバックトレースの
実行を中止し、中間セルＭとして別のセルを選択してバ
ックトレースを新たに実行する。そして、このバックト
レースの繰り返し処理は中間セルＭとしての資格を持つ
すべてのセルに対して行なうことができる。■中間セル
Ｍから、１０３ および１０４ のような、有効なバッ
クトレースがそれぞれ実行されたかどうかを判断し、「
ＹＥＳ」の場合は次のステップに進み、「ＮＯ」の場
合はステップ■に戻る。■各バックトレースの結果同士
を連結し、これを出発点セルＳと目的点セルＴとの間の
経路とする。といった手順により、指定配線長の経路を
両セル間に設定している。
【００１７】
【作用】このように、中間セルＭとして、出発点セルＳ
からのラベル付けと、目的点セルからのラベル付けを実
行した後のそれぞれのラベル値をセルごとに加えた加算
ラベル値が指定配線長になるセルを用いているため、中
間セルＭから出発点セルＳへのバックトレースの経路長
と、中間セルＭから目的点セルＴへのバックトレースの
経路長とを加算したものは必ず指定配線長となり、指定
配線長の配線経路を（この配線経路が配線平面において
存在可能なものであれば）自動配線によって確実に求め
ることができる。
からのラベル付けと、目的点セルからのラベル付けを実
行した後のそれぞれのラベル値をセルごとに加えた加算
ラベル値が指定配線長になるセルを用いているため、中
間セルＭから出発点セルＳへのバックトレースの経路長
と、中間セルＭから目的点セルＴへのバックトレースの
経路長とを加算したものは必ず指定配線長となり、指定
配線長の配線経路を（この配線経路が配線平面において
存在可能なものであれば）自動配線によって確実に求め
ることができる。
【００１８】
【実施例】以下，図２〜図６を用いて本発明の実施例を
説明する。図において、太い実線は既存の配線パターン
，網掛けは端子、また各セルの数値はラベル値および加
算ラベル値をそれぞれ示している。
説明する。図において、太い実線は既存の配線パターン
，網掛けは端子、また各セルの数値はラベル値および加
算ラベル値をそれぞれ示している。
【００１９】図２は、出発点セルＳ（ラベル値＝０）か
らラベル付けを実行したときの各セルのラベル値を、ま
た図３は、目的点セルＴ（ラベル値＝０）からラベル付
けを実行したときの各セルのラベル値を示したものであ
り、セルＳ，Ｔにはそれぞれ相手側からの１４ステップ
目のラベル付けでラベル値「１４」がふられることがわ
かる。
らラベル付けを実行したときの各セルのラベル値を、ま
た図３は、目的点セルＴ（ラベル値＝０）からラベル付
けを実行したときの各セルのラベル値を示したものであ
り、セルＳ，Ｔにはそれぞれ相手側からの１４ステップ
目のラベル付けでラベル値「１４」がふられることがわ
かる。
【００２０】図４は、図２のラベル値と図３のラベル値
とをセルごとに加算した後の加算ラベル値を示したもの
で、例えば指定配線長が「２０」のときにはこの加算ラ
ベル値が「２０」となっている、任意のセルが中間セル
Ｍとして用いられる。図中、丸で囲った加算ラベル値の
セルの部分である。
とをセルごとに加算した後の加算ラベル値を示したもの
で、例えば指定配線長が「２０」のときにはこの加算ラ
ベル値が「２０」となっている、任意のセルが中間セル
Ｍとして用いられる。図中、丸で囲った加算ラベル値の
セルの部分である。
【００２１】そして、この中間セルＭから選択した任意
の１つのセルから出発点セルＳと目的点セルＴとにそれ
ぞれバックトレースを行ない、その経路を連結すること
により、図５に示すような、配線長が「２０」の配線経
路を求めることができる。なお、括弧で囲った加算ラベ
ル値「２０」のセルの部分は、当該セルから出発点セル
Ｓおよび目的点セルＴそれぞれへのバックトレース（四
角で囲った加算ラベル値のセルの部分）において同じセ
ルが使用されることになり、最終的に配線長が「２０」
の配線経路を形成することができない。したがって、こ
の使用が判明した時点でそのバックトレースを中止し、
次の中間セルＭを選択してあらたなバックトレースを行
なう。
の１つのセルから出発点セルＳと目的点セルＴとにそれ
ぞれバックトレースを行ない、その経路を連結すること
により、図５に示すような、配線長が「２０」の配線経
路を求めることができる。なお、括弧で囲った加算ラベ
ル値「２０」のセルの部分は、当該セルから出発点セル
Ｓおよび目的点セルＴそれぞれへのバックトレース（四
角で囲った加算ラベル値のセルの部分）において同じセ
ルが使用されることになり、最終的に配線長が「２０」
の配線経路を形成することができない。したがって、こ
の使用が判明した時点でそのバックトレースを中止し、
次の中間セルＭを選択してあらたなバックトレースを行
なう。
【００２２】また、中間セルＭから出発点セルＳに対し
ては北，南，東，西の方向の順に優先度をつけたバック
トレースを行ない、中間セルＭから目的点セルＴに対し
ては逆に西，東，南，北の方向の順に優先度をつけたバ
ックトレースを行なうことにより、それぞれのバックト
レースにおいて同一セルを使用してしまうケースをでき
るだけ少なくし、さらに従来の方式（図８参照）のよう
にすぐ隣のセルを使った並行パターンが形成される可能
性を少なくしている。
ては北，南，東，西の方向の順に優先度をつけたバック
トレースを行ない、中間セルＭから目的点セルＴに対し
ては逆に西，東，南，北の方向の順に優先度をつけたバ
ックトレースを行なうことにより、それぞれのバックト
レースにおいて同一セルを使用してしまうケースをでき
るだけ少なくし、さらに従来の方式（図８参照）のよう
にすぐ隣のセルを使った並行パターンが形成される可能
性を少なくしている。
【００２３】また、任意の中間セルＭからのバックトレ
ースの際、まだ選択していない中間セルを発見したとき
にはそのセルを、以後のバックトレースの開始対象から
除外することにより、この開始対象となる中間セルの効
率的な探索を行なっている。
ースの際、まだ選択していない中間セルを発見したとき
にはそのセルを、以後のバックトレースの開始対象から
除外することにより、この開始対象となる中間セルの効
率的な探索を行なっている。
【００２４】また、以上のバックトレースを行なっても
指定配線長の経路を求めることができないときには、図
４をもとにして指定配線長より小さい加算ラベル値のセ
ルを中間セルとして選択し、この中間セルから出発点セ
ルＳおよび目的点セルＴそれぞれへのバックトレースを
同じように行なうことにより、この加算ラベル値の配線
長の経路を探索している。
指定配線長の経路を求めることができないときには、図
４をもとにして指定配線長より小さい加算ラベル値のセ
ルを中間セルとして選択し、この中間セルから出発点セ
ルＳおよび目的点セルＴそれぞれへのバックトレースを
同じように行なうことにより、この加算ラベル値の配線
長の経路を探索している。
【００２５】図６は、本発明の、指定配線長の経路を求
める手順の一例である。すなわち、（１）指定配線長，
ネットリストなどの自動配線用デ−タや、設計ルールな
どを入力し、次のステップに進む。 （２）自動配線の対象ネットを選択、すなわち出発点セ
ルＳと目的点セルＴとを指定し、次のステップに進む。 （３）配線長が指定されているかどうかを判断し、「Ｙ
ＥＳ 」の場合は次のステップに進み、「ＮＯ」の場合
はステップ（１０）に進む。 （４）出発点セルＳからのラベル付けと、目的点セルＴ
からのラベル付けとを実行し、次のステップに進む。 （５）それぞれのラベル付けによるラベル値をセルごと
に加算し、次のステップに進む。 （６）加算ラベル値が指定配線長と一致しているセルの
それぞれを中間セルＭに決定し、次のステップに進む。 （７）中間セルＭの任意の１つを選択し、次のステップ
に進む。 （８）選択した中間セルＭから、出発点セルＳと目的点
セルＴのそれぞれにバックトレースを実行し、次のステ
ップに進む。なお、前記のようにバックトレースが途中
で中止されて次のステップに進むこもある。 （９）指定配線長の経路が決定されたかどうかを判断し
、「ＹＥＳ 」の場合はステップ（１１）に進み、「Ｎ
Ｏ」の場合はステップ（７）に戻る。 （１０）通常の迷路法により、出発点セルＳから目的点
セルＴまでのラベル付けを実行し、続いて目的点セルＴ
から出発点セルＳにバックトレースを実行して両セル間
の経路を求め、次のステップに進む。 （１１）全ネットについての自動配線処理が終了したか
どうかを判断し、「ＹＥＳ 」の場合は次のステップに
進み、「ＮＯ」の場合はステップ（２） に戻る。 （１２）以上の処理により求められた配線パターンを出
力する。といった手順により、自動配線を行なっている
。
める手順の一例である。すなわち、（１）指定配線長，
ネットリストなどの自動配線用デ−タや、設計ルールな
どを入力し、次のステップに進む。 （２）自動配線の対象ネットを選択、すなわち出発点セ
ルＳと目的点セルＴとを指定し、次のステップに進む。 （３）配線長が指定されているかどうかを判断し、「Ｙ
ＥＳ 」の場合は次のステップに進み、「ＮＯ」の場合
はステップ（１０）に進む。 （４）出発点セルＳからのラベル付けと、目的点セルＴ
からのラベル付けとを実行し、次のステップに進む。 （５）それぞれのラベル付けによるラベル値をセルごと
に加算し、次のステップに進む。 （６）加算ラベル値が指定配線長と一致しているセルの
それぞれを中間セルＭに決定し、次のステップに進む。 （７）中間セルＭの任意の１つを選択し、次のステップ
に進む。 （８）選択した中間セルＭから、出発点セルＳと目的点
セルＴのそれぞれにバックトレースを実行し、次のステ
ップに進む。なお、前記のようにバックトレースが途中
で中止されて次のステップに進むこもある。 （９）指定配線長の経路が決定されたかどうかを判断し
、「ＹＥＳ 」の場合はステップ（１１）に進み、「Ｎ
Ｏ」の場合はステップ（７）に戻る。 （１０）通常の迷路法により、出発点セルＳから目的点
セルＴまでのラベル付けを実行し、続いて目的点セルＴ
から出発点セルＳにバックトレースを実行して両セル間
の経路を求め、次のステップに進む。 （１１）全ネットについての自動配線処理が終了したか
どうかを判断し、「ＹＥＳ 」の場合は次のステップに
進み、「ＮＯ」の場合はステップ（２） に戻る。 （１２）以上の処理により求められた配線パターンを出
力する。といった手順により、自動配線を行なっている
。
【００２６】
【発明の効果】本発明は、指定配線長の経路の通過点と
して用いる中間セルを、出発点セルおよび目的点セルか
らのラベル付けによるそれぞれのラベル値をセルごとに
加算した値が指定配線長となるセルの中から選択してい
るので、この中間セルから出発点セルと目的点セルへの
バックトレースはともに必ず可能であり、指定配線長の
経路が存在するときは自動配線により確実に求めること
ができ、配線率の向上を図ることができる。
して用いる中間セルを、出発点セルおよび目的点セルか
らのラベル付けによるそれぞれのラベル値をセルごとに
加算した値が指定配線長となるセルの中から選択してい
るので、この中間セルから出発点セルと目的点セルへの
バックトレースはともに必ず可能であり、指定配線長の
経路が存在するときは自動配線により確実に求めること
ができ、配線率の向上を図ることができる。
【図１】本発明の原理説明図である。
【図２】出発点セルからのラベル付けの状態を示す説明
図である。
図である。
【図３】目的点セルからのラベル付けの状態を示す説明
図である。
図である。
【図４】図２のラベル値と、図３のラベル値とをセルご
とに加算した状態を示す説明図である。
とに加算した状態を示す説明図である。
【図５】本発明の、指定配線長の経路の状態を示す説明
図である。
図である。
【図６】本発明の、指定配線長の経路を決定する手順の
一例である。
一例である。
【図７】従来の、出発点セルと目的点セルとの間の経路
を決定する様子（迷路法）を示す説明図である。
を決定する様子（迷路法）を示す説明図である。
【図８】従来の、出発点セルと目的点セルとの間の、指
定配線長の経路を決定する様子を示す説明図（その１）
である。
定配線長の経路を決定する様子を示す説明図（その１）
である。
【図９】従来の、出発点セルと目的点セルとの間の、指
定配線長の経路を決定する様子を示す説明図（その２）
である。
定配線長の経路を決定する様子を示す説明図（その２）
である。
【図１０】従来の方式では指定配線長の経路を実現でき
ないケースを示す説明図である。
ないケースを示す説明図である。
Ｓ・・・・・出発点セル
Ｔ・・・・・目的点セル
Ｍ・・・・・中間セル
１０１〜 １０４・・バックトレース
Claims (4)
- 【請求項１】 格子状に分割された配線平面でのラベ
ル付けの結果に基づいて、当該配線平面の出発点セルと
目的点セルとの間の経路を決定する自動配線方式におい
て、出発点セルからの第１のラベル付けと、目的点セル
からの第２のラベル付けとを実行し、この第１のラベル
付けと第２のラベル付けによるそれぞれのラベル値をセ
ルごとに加えた加算ラベル値を求め、あらかじめ設定さ
れている指定配線長に対応した加算ラベル値の、任意の
セルを中間セルとして選択し、この中間セルから出発点
セルと目的点セルのそれぞれにバックトレースを行なっ
て、その後、このバックトレースの結果同士を連結する
ことにより、出発点セルから中間セルを通過して目的点
セルにいたる経路を形成するようにしたことを特徴とす
る自動配線方式。 - 【請求項２】 前記バックトレースの途中で、お互い
に、同一のセルを重複して使用するようになる場合には
、そのバックトレースを中止するとともに、中間セルと
他のセルを変更し、この変更後の中間セルからのバック
トレースを新たに行なうようにしたことを特徴とする請
求項１記載の自動配線方式。 - 【請求項３】 前記バックトレースの際の方向の優先
度を、中間セルから出発点セルへのバックトレースと、
中間セルから目的点セルへのバックトレースとで逆にな
るようにしたことを特徴とする請求項１記載の自動配線
方式。 - 【請求項４】 前記指定配線長の経路を求めることが
できないときには、この指定配線長に対応した値より小
さな加算ラベル値の、任意のセルを中間セルとして新た
に選択するようにしたことを特徴とする請求項１記載の
自動配線方式。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP3054767A JP3014157B2 (ja) | 1991-03-19 | 1991-03-19 | 自動配線方式 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP3054767A JP3014157B2 (ja) | 1991-03-19 | 1991-03-19 | 自動配線方式 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH04290171A true JPH04290171A (ja) | 1992-10-14 |
| JP3014157B2 JP3014157B2 (ja) | 2000-02-28 |
Family
ID=12979927
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP3054767A Expired - Fee Related JP3014157B2 (ja) | 1991-03-19 | 1991-03-19 | 自動配線方式 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP3014157B2 (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN107944106A (zh) * | 2017-11-14 | 2018-04-20 | 天津百利越象模具制造有限责任公司 | 一种基于pdms软件的管线布局优化方法 |
-
1991
- 1991-03-19 JP JP3054767A patent/JP3014157B2/ja not_active Expired - Fee Related
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN107944106A (zh) * | 2017-11-14 | 2018-04-20 | 天津百利越象模具制造有限责任公司 | 一种基于pdms软件的管线布局优化方法 |
Also Published As
| Publication number | Publication date |
|---|---|
| JP3014157B2 (ja) | 2000-02-28 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US4615011A (en) | Iterative method for establishing connections and resulting product | |
| KR0153392B1 (ko) | Lsi용 상호접속 배선 설계 방법 | |
| JPH10270563A (ja) | 集積回路の自動概略配線方法 | |
| JPS63225869A (ja) | 配線経路探索方式 | |
| US8065649B2 (en) | Method and apparatus for routing | |
| CN116029254A (zh) | 一种基于路径优化的集成电路版图自动布线方法及系统 | |
| JP3608832B2 (ja) | 自動配線方法および自動配線装置 | |
| JPH04290171A (ja) | 自動配線方式 | |
| US5825659A (en) | Method for local rip-up and reroute of signal paths in an IC design | |
| JP2848097B2 (ja) | 配置設計方式 | |
| JPH04290170A (ja) | ラベル付けを用いた自動配線方式 | |
| JP2986279B2 (ja) | 配線方法およびプリント基板設計システム | |
| JP2000172736A (ja) | 集積回路レイアウト設計装置及び集積回路レイアウト設計方法並びにその制御プログラムを記録した記録媒体 | |
| JP2982017B2 (ja) | 自動配線処理方法 | |
| JP3111970B2 (ja) | 半導体集積回路の自動配線方法 | |
| JP3014736B2 (ja) | プリント配線板の分割配線方法 | |
| JP2536119B2 (ja) | 配線処理方式 | |
| JP2620005B2 (ja) | 配置配線決定方法 | |
| JP3178905B2 (ja) | 自動配線方式 | |
| JPH0683911A (ja) | 配線経路決定方法及びその装置 | |
| JPS62209890A (ja) | 自動配線方法 | |
| JPH04211873A (ja) | 自動配線処理方法 | |
| JPH0642256B2 (ja) | 自動配線方式 | |
| JPS62256172A (ja) | 自動配線方式 | |
| JPH0520789B2 (ja) |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 19991130 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20071217 Year of fee payment: 8 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20081217 Year of fee payment: 9 |
|
| LAPS | Cancellation because of no payment of annual fees |