JPS6367679A - 自動配線方法 - Google Patents
自動配線方法Info
- Publication number
- JPS6367679A JPS6367679A JP61213183A JP21318386A JPS6367679A JP S6367679 A JPS6367679 A JP S6367679A JP 61213183 A JP61213183 A JP 61213183A JP 21318386 A JP21318386 A JP 21318386A JP S6367679 A JPS6367679 A JP S6367679A
- Authority
- JP
- Japan
- Prior art keywords
- search
- point
- searching
- segment
- singular
- 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
- 238000000034 method Methods 0.000 title claims abstract description 32
- RZVAJINKPMORJF-UHFFFAOYSA-N Acetaminophen Chemical compound CC(=O)NC1=CC=C(O)C=C1 RZVAJINKPMORJF-UHFFFAOYSA-N 0.000 abstract 1
- 238000010586 diagram Methods 0.000 description 4
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
〔産業上の利用分野〕
本発明は自動配線方法、特に、電気系ＣＡＤシステムの
プリント基板やハイブリッドＩＣ等のＣＡＤで、最適な
配線レイアクトの自動配線方法に関するものである。
プリント基板やハイブリッドＩＣ等のＣＡＤで、最適な
配線レイアクトの自動配線方法に関するものである。
従来の自動配線方法は、配線経路が存在していてもそｊ
、が複雑な経路である場合必ず５見するとは限らないも
のが多く、確実に経路？見つけ出す方法としては、メイ
ズ法（Ｌｅｅ、Ｃ，Ｖ、：Ａｎ ａｌｇｏ −ｒｉｔｈ
ｍ ｆｏｒ Ｐａｔｈ Ｃｏｎｎｅｃｔｉｏｎｓ ａｎ
ｄ ＩｔｓＡｐｐｌｉｃａｔｉｏｎｓ、ＩＲＥ Ｔｒａ
ｎｓ、Ｅｌｅｃｔｒｏｎ、Ｃｏ −ｍｐｕｔ、、Ｖｏｌ
、ＥＣｌ０．ｐｐ、３４６−３６５（１９６１）と呼ば
詐るものがおるのみである。しかるに、ノイズ法は平面
上に波紋を広げるように経路を探索するため他の自動配
線方法に比べ多くの処理時間を要する。
、が複雑な経路である場合必ず５見するとは限らないも
のが多く、確実に経路？見つけ出す方法としては、メイ
ズ法（Ｌｅｅ、Ｃ，Ｖ、：Ａｎ ａｌｇｏ −ｒｉｔｈ
ｍ ｆｏｒ Ｐａｔｈ Ｃｏｎｎｅｃｔｉｏｎｓ ａｎ
ｄ ＩｔｓＡｐｐｌｉｃａｔｉｏｎｓ、ＩＲＥ Ｔｒａ
ｎｓ、Ｅｌｅｃｔｒｏｎ、Ｃｏ −ｍｐｕｔ、、Ｖｏｌ
、ＥＣｌ０．ｐｐ、３４６−３６５（１９６１）と呼ば
詐るものがおるのみである。しかるに、ノイズ法は平面
上に波紋を広げるように経路を探索するため他の自動配
線方法に比べ多くの処理時間を要する。
Ｐｒｏｃ、１２ｔｈ Ａｎｎｕａｌ ＡＣＭ Ｓｙ
ｍｐ、ｏｎ Ｔｈ−ｅｏｒｙ ｏｆ Ｃｏｍｐｕｔｉ
ｎｇ、ｐｐ、１６１−１７６（１９８０））は−直線上
に経路探索を行ない必要に応じて探索方向を変更してい
く方法であり、処理速度が速い。しかもこの方法は、複
数の結線すべきピンの対、すなわちピンベアの結線順位
を一括して考慮するｔめ、他の自動配線方法には見らｆ
′Ｌ、ない効率的な配線手順が見られる。
ｍｐ、ｏｎ Ｔｈ−ｅｏｒｙ ｏｆ Ｃｏｍｐｕｔｉ
ｎｇ、ｐｐ、１６１−１７６（１９８０））は−直線上
に経路探索を行ない必要に応じて探索方向を変更してい
く方法であり、処理速度が速い。しかもこの方法は、複
数の結線すべきピンの対、すなわちピンベアの結線順位
を一括して考慮するｔめ、他の自動配線方法には見らｆ
′Ｌ、ない効率的な配線手順が見られる。
高速メイズ法（Ｓｏｕｋｕｐ、Ｊ、：Ｆａｓｔ Ｍａｚ
ｅＲｏｕｔｅｒ、Ｐｒｏｃ、１５ｔｈ Ｄｅｓｉｇｎ
Ａｕｔ。
ｅＲｏｕｔｅｒ、Ｐｒｏｃ、１５ｔｈ Ｄｅｓｉｇｎ
Ａｕｔ。
ｍａｔｉｏｎ Ｃｏｎｆ、、ｐｐ、１００−１０２（
１９７８））等、処理時間の速いメイズ法も発表さｎて
いるが、このような効率的な特性は持っていない。
１９７８））等、処理時間の速いメイズ法も発表さｎて
いるが、このような効率的な特性は持っていない。
次に従来の自動配線方法の内リバー法について図面を参
照して詳細に説明する。第３図は従来の自動配線方法の
リバー法の一例を示すレイアウト図である。開始点１９
から直下に引かれた特異線２０に沿って探索線分２１が
下方向に進み、障害２２に出合う。ここで探索線分２１
は、進行方向右手近傍に常に障害が存在するように向き
を変え、その後もこの法則に従って探索線分２３のよう
に障害に沿って進む。探索線分２３が特異線２４に出会
うと優先的に方向を上方に変え探索線分２５のように探
索を進める。探索は終了点２６に到達し九時点で完了し
、開始点１９から終了点２６までの配線経路が探索線分
２１，２３．２５によって得ら詐る。
照して詳細に説明する。第３図は従来の自動配線方法の
リバー法の一例を示すレイアウト図である。開始点１９
から直下に引かれた特異線２０に沿って探索線分２１が
下方向に進み、障害２２に出合う。ここで探索線分２１
は、進行方向右手近傍に常に障害が存在するように向き
を変え、その後もこの法則に従って探索線分２３のよう
に障害に沿って進む。探索線分２３が特異線２４に出会
うと優先的に方向を上方に変え探索線分２５のように探
索を進める。探索は終了点２６に到達し九時点で完了し
、開始点１９から終了点２６までの配線経路が探索線分
２１，２３．２５によって得ら詐る。
上述した従来の自動配線方法のリノ（−法は、配線経路
が存在していてもそれが複雑な経路である場合、ノイズ
法のように必ず発見するとは限らない０ 第４図はリバー法における経路発見失敗の一例を示すレ
イアクト図である。ピンペアの開始点１から、探索優先
方向が下方になる特異線２に沿って下に降りた探索線分
３は、障害４を右手づたい避けながら障害に沿って進み
、障害５にぶつかって探索線分６のように、嘔らに探索
を進める。探索線分６が障害５にぶつかシ、探索は探索
線分９にひきつが扛て進行方向右手近傍に障害がおるよ
うに探索し閉ループ点１０に到達する。ここの地点は既
に探索済みであシ、こＣから同様の探索規則を芙行して
も同じ探索の繰り返しにな、す、障害５を抜は出る事な
く探索は失敗り終わる。
が存在していてもそれが複雑な経路である場合、ノイズ
法のように必ず発見するとは限らない０ 第４図はリバー法における経路発見失敗の一例を示すレ
イアクト図である。ピンペアの開始点１から、探索優先
方向が下方になる特異線２に沿って下に降りた探索線分
３は、障害４を右手づたい避けながら障害に沿って進み
、障害５にぶつかって探索線分６のように、嘔らに探索
を進める。探索線分６が障害５にぶつかシ、探索は探索
線分９にひきつが扛て進行方向右手近傍に障害がおるよ
うに探索し閉ループ点１０に到達する。ここの地点は既
に探索済みであシ、こＣから同様の探索規則を芙行して
も同じ探索の繰り返しにな、す、障害５を抜は出る事な
く探索は失敗り終わる。
すなわち従来のリバー法は、特異線２があるために障害
から脱出できず配線できないという欠点があった。
から脱出できず配線できないという欠点があった。
本発明の自動配線方法は、結線開始点から直下に基板下
辺まで探索を優先的にその線分に沿って下方向に行なう
第一の特異線を引き結線終了点から直下に基板下辺まで
探索を優先的にその線分に沿って上方向に行なう第二の
特異線を引く特異線設定段階と、探索点が前記第一の特
異線あるいは第二の特異線上にある場合を除いて前記結
線開始点から配線経路を進行方向に対し右手方向近傍に
障害が存在するように右手づたいに探索を進める第一の
経路探索段階と、前記第一の経路探索段階で第一の特異
線上に探索点があるが故に右手方向近傍に障害がない場
合でもそのまま下方向に探索を進めるに至った最新の点
を第一の特異点として記憶し第二の特異線上に探索点が
あるが故に右手方向近傍に障害がない場合でもそのまま
上方向に探索を進めるに至った最新の点を第二の特異点
として記憶する特異点記憶段階と、前記第一の探索段階
を適用して前記結線開始点と前記結線終了点が結線でき
なかった場合前記結線開始点から前記第一の特異点まで
の特異線の特性を無効にし前記第二の特異線と基板下辺
の交わる点から前記第二の特異点までの特異線の特性を
無効にして前記第一の経路探索段階と同様の探索法則で
探索を再開する第二の経路探索段階とを含んで構成ざｎ
る。
辺まで探索を優先的にその線分に沿って下方向に行なう
第一の特異線を引き結線終了点から直下に基板下辺まで
探索を優先的にその線分に沿って上方向に行なう第二の
特異線を引く特異線設定段階と、探索点が前記第一の特
異線あるいは第二の特異線上にある場合を除いて前記結
線開始点から配線経路を進行方向に対し右手方向近傍に
障害が存在するように右手づたいに探索を進める第一の
経路探索段階と、前記第一の経路探索段階で第一の特異
線上に探索点があるが故に右手方向近傍に障害がない場
合でもそのまま下方向に探索を進めるに至った最新の点
を第一の特異点として記憶し第二の特異線上に探索点が
あるが故に右手方向近傍に障害がない場合でもそのまま
上方向に探索を進めるに至った最新の点を第二の特異点
として記憶する特異点記憶段階と、前記第一の探索段階
を適用して前記結線開始点と前記結線終了点が結線でき
なかった場合前記結線開始点から前記第一の特異点まで
の特異線の特性を無効にし前記第二の特異線と基板下辺
の交わる点から前記第二の特異点までの特異線の特性を
無効にして前記第一の経路探索段階と同様の探索法則で
探索を再開する第二の経路探索段階とを含んで構成ざｎ
る。
次に、本発明の実施例について、図面を参照して詳細に
・説明する。
・説明する。
第１図は本発明の一実施例を示すレイアウト図である。
ビンベアの開始点１から、探索優先方向が下方になる特
異線２に沿って下に降夛た探索線分３は、障害４を右手
づたい避けながら障害に沿って進み、障害５にぶつかっ
て探索線分６のように、さらに探索を進める。このよう
な探索の最中に逐次、特異線２１にどこまで探索したか
特異点として記憶しておく。探索線分６が特異線２に出
会うと、優先的に下方向に探索方向を変え探索線分７に
引き継がれ、探索線分７は、障害５にぶつかる。この時
点で、′特異線２上の探索がなされた最新の地点は特異
点８である。探索は、探索線分９にひきつがれて進行方
向右手近傍に障害があるように探索し閉ループ点１０に
到達する。
異線２に沿って下に降夛た探索線分３は、障害４を右手
づたい避けながら障害に沿って進み、障害５にぶつかっ
て探索線分６のように、さらに探索を進める。このよう
な探索の最中に逐次、特異線２１にどこまで探索したか
特異点として記憶しておく。探索線分６が特異線２に出
会うと、優先的に下方向に探索方向を変え探索線分７に
引き継がれ、探索線分７は、障害５にぶつかる。この時
点で、′特異線２上の探索がなされた最新の地点は特異
点８である。探索は、探索線分９にひきつがれて進行方
向右手近傍に障害があるように探索し閉ループ点１０に
到達する。
ここの地点は既に探索済みであるが、閉ループ点１０は
開始点１と特異点８との間に位置しているので再探索？
実行する。再探索は、探索線分９゜７．６と後戻りしな
がら、閉ループ点１０まで戻りそこから再開する。
開始点１と特異点８との間に位置しているので再探索？
実行する。再探索は、探索線分９゜７．６と後戻りしな
がら、閉ループ点１０まで戻りそこから再開する。
この閉ループ点１０よシ再び右手づたいの法則で進み探
索線分６のように探索をする。探索線分６は、特異線２
に出会うがこの地点は開始点１と特異点８との間に位置
しているので、特異線２の持つ下方向の優先探索の特性
は効果を示さず、探索線分６は右手づたいの法則をその
まま適応して探索線分１１に引き継がれる。障害５に沿
って探索は進み、探索線分１２が特異線２に到達すると
、この地点は開始点１と特異点８との間にはないので、
４！ＩＦ異線２の優先方向指定の効果が効き、探索線分
１２は優先的に特異線２に沿って下方向に降ｐる。探索
線分１２Ｆｉ、障害１３にぶつかって進行方向右手近傍
に障害があるように方向を変え、探索線分１４として障
害１３に沿って探索を進める。探索線分１４が、第二の
特異線１５に出会うと優先的に上方向に向きを変更する
。探索線分１４は、障害１６にぶつかり右手づたいに障
害１６に沿って進み、再び特異線１５に出会う。ここで
優先的に上方向に向きが変更さ詐、探索線分１７に引き
継がｎて特異線１７に沿って上方向に進行し、終了点１
８に到達して探索を完了する。
索線分６のように探索をする。探索線分６は、特異線２
に出会うがこの地点は開始点１と特異点８との間に位置
しているので、特異線２の持つ下方向の優先探索の特性
は効果を示さず、探索線分６は右手づたいの法則をその
まま適応して探索線分１１に引き継がれる。障害５に沿
って探索は進み、探索線分１２が特異線２に到達すると
、この地点は開始点１と特異点８との間にはないので、
４！ＩＦ異線２の優先方向指定の効果が効き、探索線分
１２は優先的に特異線２に沿って下方向に降ｐる。探索
線分１２Ｆｉ、障害１３にぶつかって進行方向右手近傍
に障害があるように方向を変え、探索線分１４として障
害１３に沿って探索を進める。探索線分１４が、第二の
特異線１５に出会うと優先的に上方向に向きを変更する
。探索線分１４は、障害１６にぶつかり右手づたいに障
害１６に沿って進み、再び特異線１５に出会う。ここで
優先的に上方向に向きが変更さ詐、探索線分１７に引き
継がｎて特異線１７に沿って上方向に進行し、終了点１
８に到達して探索を完了する。
第２図は、第１図の実施例の説明図を流ｊ、図で示した
ものである。
ものである。
本発明の自動配線方法は、リバー法の高速探索性と効率
の良い配線手順という特性を失わず、なおかつメイズ法
のよりに経路があればかならず発見するという重要な特
性を合わせ持った方法であフ、自動配線実行における高
配線率が高速に得られるという効果がある。
の良い配線手順という特性を失わず、なおかつメイズ法
のよりに経路があればかならず発見するという重要な特
性を合わせ持った方法であフ、自動配線実行における高
配線率が高速に得られるという効果がある。
第１図は本発明の一実施例を示すレイアクト図、第２図
は第１図に示す自動配線方法の手順？示す７°−７・−
１・第３図＄９（Ｄ−例を示す′イト・・・・・開始点
、２・−・・・・特異線、３・・・・・・探索線分、４
〜５・・・・・・障害、６〜７・・・・・・探索線分、
８・・・・・・特異点、９・・・・・・探索線分、１０
・・・・・・閉ループ点、１１〜１２・・・・・−探索
線分、１３・・・・・・障害、１４・・・・・・探索線
分、１５・・・・・・特異線、１６・・・・・・障害、
１７・・・・・・探索線分、１８・・・・・・終了点、
１９・・・・・・開始点、２０・・・・・・特異線、２
１・・・・・・探索線分、２２・・・・・・障害、２３
・・・・・・探索線分、２４・・・・・・特異線、２５
・・・・・・探索線分、２６・・・・・・終了点。 、 ）・ 代理人 弁理士 内 原 晋 ゝ−２−
は第１図に示す自動配線方法の手順？示す７°−７・−
１・第３図＄９（Ｄ−例を示す′イト・・・・・開始点
、２・−・・・・特異線、３・・・・・・探索線分、４
〜５・・・・・・障害、６〜７・・・・・・探索線分、
８・・・・・・特異点、９・・・・・・探索線分、１０
・・・・・・閉ループ点、１１〜１２・・・・・−探索
線分、１３・・・・・・障害、１４・・・・・・探索線
分、１５・・・・・・特異線、１６・・・・・・障害、
１７・・・・・・探索線分、１８・・・・・・終了点、
１９・・・・・・開始点、２０・・・・・・特異線、２
１・・・・・・探索線分、２２・・・・・・障害、２３
・・・・・・探索線分、２４・・・・・・特異線、２５
・・・・・・探索線分、２６・・・・・・終了点。 、 ）・ 代理人 弁理士 内 原 晋 ゝ−２−
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 true JPS6367679A (ja) | 1988-03-26 |
| JPH0543149B2 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 |
|---|---|
| JPH0543149B2 (ja) | 1993-06-30 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US5615128A (en) | Towards optimal steiner tree routing in the presence of rectilinear obstacles | |
| JP3608832B2 (ja) | 自動配線方法および自動配線装置 | |
| JPS6367679A (ja) | 自動配線方法 | |
| JP2574996B2 (ja) | 差動電流スイッチ対のルーティング方法 | |
| JPH0477949B2 (ja) | ||
| JPH0544058B2 (ja) | ||
| JPS63204301A (ja) | Ｎｃ実装機の実装経路の決定方法 | |
| JP3014157B2 (ja) | 自動配線方式 | |
| JP3560451B2 (ja) | 半導体集積回路のレイアウト方法 | |
| JPH0460774A (ja) | 自動配線方式 | |
| JPH0652260A (ja) | 自動配線方法 | |
| JPH06325132A (ja) | 自動配線方法 | |
| JPH04289975A (ja) | 配線経路探索方式 | |
| JP2982017B2 (ja) | 自動配線処理方法 | |
| JPH04141779A (ja) | 配線経路探索方式 | |
| JPH0748221B2 (ja) | 経路探索処理方法 | |
| JPS63121979A (ja) | 配線経路探索装置 | |
| JPH0652261A (ja) | 自動配線方式 | |
| JPH01321563A (ja) | 配線経路探索方式 | |
| JPH0540806A (ja) | 表面実装部品の自動配線方法 | |
| JPH04117571A (ja) | 配線経路探索方式 | |
| JPH08202753A (ja) | 回路図の配線自動修正方法 | |
| JPH03142858A (ja) | Ｉｃ内配線方法 | |
| JPH07152814A (ja) | 空線分による経路探索方法 | |
| JPH04275679A (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 |