JPH0543149B2 - - Google Patents
Info
- Publication number
- JPH0543149B2 JPH0543149B2 JP61213183A JP21318386A JPH0543149B2 JP H0543149 B2 JPH0543149 B2 JP H0543149B2 JP 61213183 A JP61213183 A JP 61213183A JP 21318386 A JP21318386 A JP 21318386A JP H0543149 B2 JPH0543149 B2 JP H0543149B2
- Authority
- JP
- Japan
- Prior art keywords
- point
- search
- singular
- line
- line segment
- 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.)
- Expired - Lifetime
Links
Description
【発明の詳細な説明】
〔産業上の利用分野〕
本発明は自動配線方法、特に、電気系CADシ
ステムのプリント基板やハイブリツドIC等の
CADで、最適な配線レイアウトの自動配線方法
に関するものである。
ステムのプリント基板やハイブリツドIC等の
CADで、最適な配線レイアウトの自動配線方法
に関するものである。
従来の自動配線方法は、配線経路が存在してい
てもそれが複雑な経路である場合必ず発見すると
は限らないものが多く、確実に経路を見つけ出す
方法としては、メイズ法（Lee，C.V.：An
algorithm for Path Connections and lts
Applications，1RE Trans.Electron.Comput.，
Vol.EC10、pp.346−365（1961）と呼ばれるもの
があるのみである。しかるに、メイズ法は平面上
に波紋を広げるように経路を探索するため他の目
的配線方法に比べ多くの処理時間を要する。
てもそれが複雑な経路である場合必ず発見すると
は限らないものが多く、確実に経路を見つけ出す
方法としては、メイズ法（Lee，C.V.：An
algorithm for Path Connections and lts
Applications，1RE Trans.Electron.Comput.，
Vol.EC10、pp.346−365（1961）と呼ばれるもの
があるのみである。しかるに、メイズ法は平面上
に波紋を広げるように経路を探索するため他の目
的配線方法に比べ多くの処理時間を要する。
一方、リバー法（Tompa，M.：An Optimal
Solution to the Wire−Routing Problem，
Proc.12th AnnualACM Symp.on Theory of
Computing，pp.161−176（1980））は一直線上に
経路探索を行ない必要に応じて探索方向を変更し
ていく方法であり、処理速度が速い。しかもこの
方法は、複数の結線すべきピンの対、すなわちピ
ンペアの結線順位を一括して考慮するため、他の
自動配線方法には見られない効率的な配線手順が
見られる。
Solution to the Wire−Routing Problem，
Proc.12th AnnualACM Symp.on Theory of
Computing，pp.161−176（1980））は一直線上に
経路探索を行ない必要に応じて探索方向を変更し
ていく方法であり、処理速度が速い。しかもこの
方法は、複数の結線すべきピンの対、すなわちピ
ンペアの結線順位を一括して考慮するため、他の
自動配線方法には見られない効率的な配線手順が
見られる。
高速メイズ法（Soukup，J.：Fast Maze
Router，Proc.15th Design Auto mation
Conf.，pp.100−102（1978））等、処理時間の速い
メイズ法も発表されているが、このような効率的
な特性は持つていない。
Router，Proc.15th Design Auto mation
Conf.，pp.100−102（1978））等、処理時間の速い
メイズ法も発表されているが、このような効率的
な特性は持つていない。
次に従来の自動配線方法の内リバー法について
図面を参照して詳細に説明する。第３図は従来の
自動配線方法のリバー法の一例を示すレイアウト
図である。開始点１９から直下に引かれた特異線
２０に沿つて探索線分２１が下方向に進み、障害
２２に出合う。ここで探索線分２１は、進行方向
右手近傍に常に障害が存在するように向きを変
え、その後もこの法則に従つて探索線分２３のよ
うに障害に沿つて進む。探索線分２３が特異線２
４に出会うと優先的に方向を上方に変え探索線分
２５のように探索を進める。探索は終了点２６に
到達した時点で完了し、開始点１９から終了点２
６までの配線経路が探索線分２１，２３，２５に
よつて得られる。
図面を参照して詳細に説明する。第３図は従来の
自動配線方法のリバー法の一例を示すレイアウト
図である。開始点１９から直下に引かれた特異線
２０に沿つて探索線分２１が下方向に進み、障害
２２に出合う。ここで探索線分２１は、進行方向
右手近傍に常に障害が存在するように向きを変
え、その後もこの法則に従つて探索線分２３のよ
うに障害に沿つて進む。探索線分２３が特異線２
４に出会うと優先的に方向を上方に変え探索線分
２５のように探索を進める。探索は終了点２６に
到達した時点で完了し、開始点１９から終了点２
６までの配線経路が探索線分２１，２３，２５に
よつて得られる。
上述した従来の自動配線方法のリバー法は、配
線経路が存在していてもそれが複雑な経路である
場合、メイズ法のように必ず発見するとは限らな
い。
線経路が存在していてもそれが複雑な経路である
場合、メイズ法のように必ず発見するとは限らな
い。
第４図はリバー法における経路発見失敗の一例
を示すレイアウト図である。ピンペアの開始点１
から、探索優先方向が下方になる特異線２に沿つ
て下に降りた探索線分３は、障害４は右手づたい
避けながら障害に沿つて進み、障害５にぶつかつ
て探索線分６のように、さらに探索を進める。探
索線分６が障害５にぶつかり、探索は探索線分９
にひきつがれて進行方向右手近傍に障害があるよ
うに探索し閉ループ点１０に到達する。ここの地
点は既に探索済みであり、ここから同様の探索規
則を実行しても同じ探索の繰り返しになり、障害
５を抜け出る事なく探索は失敗に終わる。
を示すレイアウト図である。ピンペアの開始点１
から、探索優先方向が下方になる特異線２に沿つ
て下に降りた探索線分３は、障害４は右手づたい
避けながら障害に沿つて進み、障害５にぶつかつ
て探索線分６のように、さらに探索を進める。探
索線分６が障害５にぶつかり、探索は探索線分９
にひきつがれて進行方向右手近傍に障害があるよ
うに探索し閉ループ点１０に到達する。ここの地
点は既に探索済みであり、ここから同様の探索規
則を実行しても同じ探索の繰り返しになり、障害
５を抜け出る事なく探索は失敗に終わる。
すなわち従来のリバー法は、特異線２があるた
めに障害から脱出できず配線できないという欠点
があつた。
めに障害から脱出できず配線できないという欠点
があつた。
本発明の自動配線方法は、結線開始点から直下
に基板下辺まで探索を優先的にその線分に沿つて
下方向に行なう第一の特異線を引き結線終了点か
ら直下に基板下辺まで探索を優先的にその線分に
沿つて上方向に行なう第二の特異線を引く特異線
設定段階と、探索点が前記第一の特異線あるいは
第二の特異線上にある場合を除いて前記結線開始
点から配線経路を進行方向に対し右手方向近傍に
障害が存在するように右手づたいに探索を進める
第一の経路探索段階と、前記第一の経路探索段階
で第一の特異線上に探索点があるが故に右手方向
近傍に障害がない場合でもそのまま下方向に探索
を進めるに至つた最新の点を第一の特異点として
記憶し第二の特異線上に探索点があるが故に右手
方向近傍に障害がない場合でもそのまま上方向に
探索を進めるに至つた最新の点を第二の特異点と
して記憶する特異点記憶段階と、前記第一の探索
段階を適用して前記結線開始点と前記結線終了点
が結線できなかつた場合前記結線開始点から前記
第一の特異点までの特異線の特性を無効にし前記
第二の特異線と基板下辺の交わる点から前記第二
の特異点までの特異線の特性を無効にして前記第
一の経路探索段階と同様の探索法則で探索を再開
する第二の経路探索段階とを含んで構成される。
に基板下辺まで探索を優先的にその線分に沿つて
下方向に行なう第一の特異線を引き結線終了点か
ら直下に基板下辺まで探索を優先的にその線分に
沿つて上方向に行なう第二の特異線を引く特異線
設定段階と、探索点が前記第一の特異線あるいは
第二の特異線上にある場合を除いて前記結線開始
点から配線経路を進行方向に対し右手方向近傍に
障害が存在するように右手づたいに探索を進める
第一の経路探索段階と、前記第一の経路探索段階
で第一の特異線上に探索点があるが故に右手方向
近傍に障害がない場合でもそのまま下方向に探索
を進めるに至つた最新の点を第一の特異点として
記憶し第二の特異線上に探索点があるが故に右手
方向近傍に障害がない場合でもそのまま上方向に
探索を進めるに至つた最新の点を第二の特異点と
して記憶する特異点記憶段階と、前記第一の探索
段階を適用して前記結線開始点と前記結線終了点
が結線できなかつた場合前記結線開始点から前記
第一の特異点までの特異線の特性を無効にし前記
第二の特異線と基板下辺の交わる点から前記第二
の特異点までの特異線の特性を無効にして前記第
一の経路探索段階と同様の探索法則で探索を再開
する第二の経路探索段階とを含んで構成される。
次に、本発明の実施例について、図面を参照し
て詳細に説明する。
て詳細に説明する。
第１図は本発明の一実施例を示すレイアウト図
である。ピンペアの開始点１から、探索優先方向
が下方になる特異線２に沿つて下に降りた探索線
３は、障害４を右手づたい避けながら障害に沿つ
て進み、障害５にぶつかつて探索線分６のよう
に、さらに探索を進める。このような探索の最中
に逐次、特異線２をどこまで探索したか特異点と
して記憶しておく。探索線分６が特異線２に出会
うと、優先的に下方向に探索方向を変え探索線分
７に引き継がれ、探索線分７は、障害５にぶつか
る。この時点で、特異線２上の探索がなされた最
新の地点は特異点８である。探索は、探索線分９
にひきつがれて進行方向右手近傍に障害があるよ
うに探索し閉ループ点１０に到達する。
である。ピンペアの開始点１から、探索優先方向
が下方になる特異線２に沿つて下に降りた探索線
３は、障害４を右手づたい避けながら障害に沿つ
て進み、障害５にぶつかつて探索線分６のよう
に、さらに探索を進める。このような探索の最中
に逐次、特異線２をどこまで探索したか特異点と
して記憶しておく。探索線分６が特異線２に出会
うと、優先的に下方向に探索方向を変え探索線分
７に引き継がれ、探索線分７は、障害５にぶつか
る。この時点で、特異線２上の探索がなされた最
新の地点は特異点８である。探索は、探索線分９
にひきつがれて進行方向右手近傍に障害があるよ
うに探索し閉ループ点１０に到達する。
ここの地点は既に探索済みであるが、閉ループ
点１０は開始点１と特異点８との間に位置してい
るので再探索を実行する。再探索は、探索線分
９，７，６と後戻りしながら、閉ループ点１０ま
で戻りそこから再開する。
点１０は開始点１と特異点８との間に位置してい
るので再探索を実行する。再探索は、探索線分
９，７，６と後戻りしながら、閉ループ点１０ま
で戻りそこから再開する。
この閉ループ点１０より再び右手づたいの法則
で進み探索線分６のように探索をする。探索線分
６は、特異線２に出会うがこの地点は開始点１と
特異点８との間に位置しているので、特異線２の
持つ下方向の優先探索の特性は効果を示さず、探
索線分６は右手づたいの法則をそのまま適応して
探索線分１１に引き継がれる。障害５に沿つて探
索は進み、探索線分１２が特異線２に到達する
と、この地点は開始点１と特異点８との間にはな
いので、特異線２の優先方向指定の効果が効き、
探索線分１２は優先的に特異線２に沿つて下方向
に降りる。探索線分１２は、障害１３にぶつかつ
て進行方向右手近傍に障害があるように方向を変
え、探索線分１４として障害１３に沿つて探索を
進める。探索線分１４が、第二の特異線１５に出
会うと優先的に上方向に向きを変更する。探索線
分１４は、障害１６にぶつかり右手づたいに障害
１６に沿つて進み、再び特異線１５に出会う。こ
こで優先的に上方向に向きが変更され、探索線分
１７に引き継がれて特異線１７に沿つて上方向に
進行し、終了点１８に到達して探索を完了する。
で進み探索線分６のように探索をする。探索線分
６は、特異線２に出会うがこの地点は開始点１と
特異点８との間に位置しているので、特異線２の
持つ下方向の優先探索の特性は効果を示さず、探
索線分６は右手づたいの法則をそのまま適応して
探索線分１１に引き継がれる。障害５に沿つて探
索は進み、探索線分１２が特異線２に到達する
と、この地点は開始点１と特異点８との間にはな
いので、特異線２の優先方向指定の効果が効き、
探索線分１２は優先的に特異線２に沿つて下方向
に降りる。探索線分１２は、障害１３にぶつかつ
て進行方向右手近傍に障害があるように方向を変
え、探索線分１４として障害１３に沿つて探索を
進める。探索線分１４が、第二の特異線１５に出
会うと優先的に上方向に向きを変更する。探索線
分１４は、障害１６にぶつかり右手づたいに障害
１６に沿つて進み、再び特異線１５に出会う。こ
こで優先的に上方向に向きが変更され、探索線分
１７に引き継がれて特異線１７に沿つて上方向に
進行し、終了点１８に到達して探索を完了する。
第２図は、第１図の実施例の説明図を流れ図で
示したものである。
示したものである。
本発明の自動配線方法は、リバー法の高速探索
性と効率の良い配線手順という特性を失わず、な
おかつメイズ法のように経路があればかならず発
見するという重要な特性を合わせ持つた方法であ
り、自動配線実行における高配線率が高速に得ら
れるという効果がある。
性と効率の良い配線手順という特性を失わず、な
おかつメイズ法のように経路があればかならず発
見するという重要な特性を合わせ持つた方法であ
り、自動配線実行における高配線率が高速に得ら
れるという効果がある。
第１図は本発明の一実施例を示すレイアウト
図、第２図は第１図に示す自動配線方法の手順を
示すフローチヤート、第３図は従来の一例を示す
レイアウト図、第４図は従来の方法での欠点を説
明するためのレイアウト図である。 １……開始点、２……特異線、３……探索線
分、４〜５……障害、６〜７……探索線分、８…
…特異点、９……探索線分、１０……閉ループ
点、１１〜１２……探索線分、１３……障害、１
４……探索線分、１５……特異線、１６……障
害、１７……探索線分、１８……終了点、１９…
…開始点、２０……特異線、２１……探索線分、
２２……障害、２３……探索線分、２４……特異
線、２５……探索線分、２６……終了点。
図、第２図は第１図に示す自動配線方法の手順を
示すフローチヤート、第３図は従来の一例を示す
レイアウト図、第４図は従来の方法での欠点を説
明するためのレイアウト図である。 １……開始点、２……特異線、３……探索線
分、４〜５……障害、６〜７……探索線分、８…
…特異点、９……探索線分、１０……閉ループ
点、１１〜１２……探索線分、１３……障害、１
４……探索線分、１５……特異線、１６……障
害、１７……探索線分、１８……終了点、１９…
…開始点、２０……特異線、２１……探索線分、
２２……障害、２３……探索線分、２４……特異
線、２５……探索線分、２６……終了点。
Claims (1)
- １ 結線開始点から直下に基板下辺まで探索を優
先的にその線分に沿つて下方向に行なう第一の特
異線を引き結線終了点から直下に基板下辺まで探
索を優先的にその線分に沿つて上方向に行なう第
二の特異線を引く特異線設定段階と、探索点が前
記第一の特異線あるいは第二の特異線上にある場
合を除いて前記結線開始点から配線経路を進行方
向に対し右手方向近傍に障害が存在するように右
手づたいに探索を進める第一の経路探索段階と、
前記第一の経路探索段階で第一の特異線上に探索
点があるが故に右手方向近傍に障害がない場合で
もそのまま下方向に探索を進めるに至つた最新の
点を第一の特異点として記憶し第二の特異線上に
探索点があるが故に右手方向近傍に障害がない場
合でもそのまま上方向に探索を進めるに至つた最
新の点を第二の特異点として記憶する特異点記憶
段階と、前記第一の探索段階を適用して前記結線
開始点と前記結線終了点が結線できなかつた場合
前記結線開始点から前記第一の特異点までの特異
線の特性を無効にし前記第二の特異線と基板下辺
の交わる点から前記第二の特異点までの特異線の
特性を無効にして前記第一の経路探索段階と同様
の探索法則で探索を再開する第二の経路探索段階
とを含むことを特徴とする自動配線方法。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP61213183A JPS6367679A (ja) | 1986-09-09 | 1986-09-09 | 自動配線方法 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP61213183A JPS6367679A (ja) | 1986-09-09 | 1986-09-09 | 自動配線方法 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS6367679A JPS6367679A (ja) | 1988-03-26 |
| JPH0543149B2 true JPH0543149B2 (ja) | 1993-06-30 |
Family
ID=16634918
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP61213183A Granted JPS6367679A (ja) | 1986-09-09 | 1986-09-09 | 自動配線方法 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPS6367679A (ja) |
-
1986
- 1986-09-09 JP JP61213183A patent/JPS6367679A/ja active Granted
Also Published As
| Publication number | Publication date |
|---|---|
| JPS6367679A (ja) | 1988-03-26 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US5615128A (en) | Towards optimal steiner tree routing in the presence of rectilinear obstacles | |
| JP2687879B2 (ja) | 自動配線方法 | |
| JP3335250B2 (ja) | 半導体集積回路の配線方法 | |
| JPH07152802A (ja) | 配線設計方法 | |
| US8918746B1 (en) | Cut mask aware contact enclosure rule for grating and cut patterning solution | |
| JP3608832B2 (ja) | 自動配線方法および自動配線装置 | |
| JPH0543149B2 (ja) | ||
| JP2828026B2 (ja) | 自動配線方法 | |
| CN115270692A (zh) | 基于布线区域生成的总线布线方法 | |
| JP2574996B2 (ja) | 差動電流スイッチ対のルーティング方法 | |
| JP3052561B2 (ja) | 自動配線方法 | |
| JP3560451B2 (ja) | 半導体集積回路のレイアウト方法 | |
| JPH0477949B2 (ja) | ||
| JP3014157B2 (ja) | 自動配線方式 | |
| JPH0652261A (ja) | 自動配線方式 | |
| JPH0544058B2 (ja) | ||
| JPH04239747A (ja) | 集積回路の配線設計方法 | |
| JPH07249065A (ja) | 配線経路探索方法 | |
| JP2982017B2 (ja) | 自動配線処理方法 | |
| JPS63121979A (ja) | 配線経路探索装置 | |
| JPH04289975A (ja) | 配線経路探索方式 | |
| JPH04260965A (ja) | ２点間の径路探索方法 | |
| JPH04117571A (ja) | 配線経路探索方式 | |
| JPH0642256B2 (ja) | 自動配線方式 | |
| JPS62115741A (ja) | 高配線率配線法 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| S531 | Written request for registration of change of domicile |
Free format text: JAPANESE INTERMEDIATE CODE: R313531 |
|
| R350 | Written notification of registration of transfer |
Free format text: JAPANESE INTERMEDIATE CODE: R350 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| EXPY | Cancellation because of completion of term |