JPH06124321A - 自動配線処理方法 - Google Patents
自動配線処理方法Info
- Publication number
- JPH06124321A JPH06124321A JP4271554A JP27155492A JPH06124321A JP H06124321 A JPH06124321 A JP H06124321A JP 4271554 A JP4271554 A JP 4271554A JP 27155492 A JP27155492 A JP 27155492A JP H06124321 A JPH06124321 A JP H06124321A
- Authority
- JP
- Japan
- Prior art keywords
- terminal
- wiring
- line
- search line
- search
- 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
- Design And Manufacture Of Integrated Circuits (AREA)
Abstract
(57)【要約】 （修正有）
【目的】集積回路等の自動配線処理の際に、ある端子対
の配線が遮られた場合に、再配線により配線率を向上す
る。 【構成】自動配線処理において、ある端子対の配線が出
来ない場合、端子Ｓから探索線ＳＳを、端子Ｔから探索
線ＳＴを生成し、探索線ＳＳ上でスルーホールを置くこ
とが可能な領域の線長ＬＳＳと探索線ＳＴ上でスルーホ
ールを置くことが可能な領域の線長ＬＳＴを求め、閾値
ＬＴよりもＬＳＳが小さいときは端子Ｓに近い位置で探
索線ＳＳと交差する既配線を引き剥し、閾値ＬＴよりも
ＬＳＴが小さいときは端子Ｔに近い位置で探索線ＳＴと
交差する既配線を引き剥し、ＬＳＳとＬＳＴが閾値ＬＴ
よりも大きく、かつＬＳＳがＬＳＴよりも小さいときに
端子Ｓに近い位置で探索線ＳＳと交差する既配線を引き
剥し、ＬＳＳがＬＳＴよりも大きいときは端子Ｔに近い
位置で探索線ＳＴと交差する既配線を引き剥して端子Ｓ
と端子Ｔとを結ぶ配線経路を求め、その再配線処理を行
なう。
の配線が遮られた場合に、再配線により配線率を向上す
る。 【構成】自動配線処理において、ある端子対の配線が出
来ない場合、端子Ｓから探索線ＳＳを、端子Ｔから探索
線ＳＴを生成し、探索線ＳＳ上でスルーホールを置くこ
とが可能な領域の線長ＬＳＳと探索線ＳＴ上でスルーホ
ールを置くことが可能な領域の線長ＬＳＴを求め、閾値
ＬＴよりもＬＳＳが小さいときは端子Ｓに近い位置で探
索線ＳＳと交差する既配線を引き剥し、閾値ＬＴよりも
ＬＳＴが小さいときは端子Ｔに近い位置で探索線ＳＴと
交差する既配線を引き剥し、ＬＳＳとＬＳＴが閾値ＬＴ
よりも大きく、かつＬＳＳがＬＳＴよりも小さいときに
端子Ｓに近い位置で探索線ＳＳと交差する既配線を引き
剥し、ＬＳＳがＬＳＴよりも大きいときは端子Ｔに近い
位置で探索線ＳＴと交差する既配線を引き剥して端子Ｓ
と端子Ｔとを結ぶ配線経路を求め、その再配線処理を行
なう。
Description
【０００１】
【産業上の利用分野】本発明は集積回路やプリント基板
の多層配線領域における自動配線処理方法に関する。
の多層配線領域における自動配線処理方法に関する。
【０００２】
【従来の技術】ある端子対の配線が不可能であった場合
に、既配線を引き剥して配線をやり直すことによって配
線率の向上を狙ったものとしては、ダイナミック・ルー
ター（情報処理学会第25回全国大会、1982年、pp.1301-
1302）がある。これは、迷路法に基づいて端子対間を分
断している既配線を探し出してそれを引き剥すというも
のである。
に、既配線を引き剥して配線をやり直すことによって配
線率の向上を狙ったものとしては、ダイナミック・ルー
ター（情報処理学会第25回全国大会、1982年、pp.1301-
1302）がある。これは、迷路法に基づいて端子対間を分
断している既配線を探し出してそれを引き剥すというも
のである。
【０００３】
【発明が解決しようとする課題】従来のダイナミック・
ルーターによる配線処理方法は、記憶領域を多く必要と
する迷路法に基づいており、大規模回路の配線には適さ
ない。また、多層の配線層については、引き剥すべき既
配線を見い出すための明確な指標を示していないので、
多層構造を持つプリント基板や集積回路には適さない。
ルーターによる配線処理方法は、記憶領域を多く必要と
する迷路法に基づいており、大規模回路の配線には適さ
ない。また、多層の配線層については、引き剥すべき既
配線を見い出すための明確な指標を示していないので、
多層構造を持つプリント基板や集積回路には適さない。
【０００４】
【課題を解決するための手段】本発明は集積回路やプリ
ント基板の多層配線領域における自動配線処理方法にお
いて、第１の端子と第２の端子との間の配線が出来ない
場合、第１の端子から第１の探索線を生成し、第２の端
子から第２の探索線を生成し、第１の探索線上でスルー
ホールを置くことが可能な領域の第１の線長と第２の探
索線上でスルーホールを置くことが可能な領域の第２の
線長を求め、予め定めた閾値よりも第１の線長が小さい
ときは第１の端子に最も近い位置で第１の探索線と交差
する既配線を引き剥し、前記閾値よりも第２の線長が小
さいときは第２の端子に最も近い位置で第２の探索線と
交差する既配線を引き剥し、第１および第２の線長の双
方が前記閾値よりも大きいときは第１の線長と第２の線
長とを比較し、第１の線長が第２の線長よりも小さいと
きは第１の端子に最も近い位置で第１の探索線と交差す
る既配線を引き剥し、第１の線長が第２の線長よりも大
きいときは第２の端子に最も近い位置で第２の探索線と
交差する既配線を引き剥して第１の端子と第２の端子と
を結ぶ配線経路を求め、引き剥した既配線経路の再配線
処理を行なう。
ント基板の多層配線領域における自動配線処理方法にお
いて、第１の端子と第２の端子との間の配線が出来ない
場合、第１の端子から第１の探索線を生成し、第２の端
子から第２の探索線を生成し、第１の探索線上でスルー
ホールを置くことが可能な領域の第１の線長と第２の探
索線上でスルーホールを置くことが可能な領域の第２の
線長を求め、予め定めた閾値よりも第１の線長が小さい
ときは第１の端子に最も近い位置で第１の探索線と交差
する既配線を引き剥し、前記閾値よりも第２の線長が小
さいときは第２の端子に最も近い位置で第２の探索線と
交差する既配線を引き剥し、第１および第２の線長の双
方が前記閾値よりも大きいときは第１の線長と第２の線
長とを比較し、第１の線長が第２の線長よりも小さいと
きは第１の端子に最も近い位置で第１の探索線と交差す
る既配線を引き剥し、第１の線長が第２の線長よりも大
きいときは第２の端子に最も近い位置で第２の探索線と
交差する既配線を引き剥して第１の端子と第２の端子と
を結ぶ配線経路を求め、引き剥した既配線経路の再配線
処理を行なう。
【０００５】
【実施例】次に本発明の一実施例について図面を参照し
て説明する。
て説明する。
【０００６】図１は自動配線処理においてどの既配線を
引き剥すかを決定する過程を示すフローチャートであ
る。集積回路やプリント基板の多層配線領域における自
動配線処理の際に、ある端子対（端子Ｓ、端子Ｔ）の配
線が出来ない場合に、端子Ｓから探索線ＳＳを生成し、
端子Ｔから探索線ＳＴを生成し（ステップＡ）、探索線
ＳＳ上でスルーホールを置くことが可能な領域の線長Ｌ
ＳＳと探索線ＳＴ上でスルーホールを置くことが可能な
領域の線長ＬＳＴを求め（ステップＢ）、ある閾値ＬＴ
よりもＬＳＳが小さいときは端子Ｓに最も近い位置で探
索線ＳＳと交差する既配線を引き剥し（ステップＣ，
Ｇ）、閾値ＬＴよりもＬＳＴが小さいときは端子Ｔに最
も近い位置で探索線ＳＴと交差する既配線を引き剥し
（ステップＤ，Ｈ）、ＬＳＳおよびＬＳＴの双方が閾値
ＬＴよりも大きいときはＬＳＳとＬＳＴとを比較し（ス
テップＥ）、ＬＳＳがＬＳＴよりも小さいときは端子Ｓ
に最も近い位置で探索線ＳＳと交差する既配線を引き剥
し（ステップＩ）、ＬＳＳがＬＳＴよりも大きいときは
端子Ｔに最も近い位置で探索線ＳＴと交差する既配線を
引き剥し（ステップＦ）、端子Ｓと端子Ｔとを結ぶ配線
経路を求め、次に、引き剥した既配線経路の再配線処理
を行なうことにより、未配線を減らし、配線率を向上さ
せる。
引き剥すかを決定する過程を示すフローチャートであ
る。集積回路やプリント基板の多層配線領域における自
動配線処理の際に、ある端子対（端子Ｓ、端子Ｔ）の配
線が出来ない場合に、端子Ｓから探索線ＳＳを生成し、
端子Ｔから探索線ＳＴを生成し（ステップＡ）、探索線
ＳＳ上でスルーホールを置くことが可能な領域の線長Ｌ
ＳＳと探索線ＳＴ上でスルーホールを置くことが可能な
領域の線長ＬＳＴを求め（ステップＢ）、ある閾値ＬＴ
よりもＬＳＳが小さいときは端子Ｓに最も近い位置で探
索線ＳＳと交差する既配線を引き剥し（ステップＣ，
Ｇ）、閾値ＬＴよりもＬＳＴが小さいときは端子Ｔに最
も近い位置で探索線ＳＴと交差する既配線を引き剥し
（ステップＤ，Ｈ）、ＬＳＳおよびＬＳＴの双方が閾値
ＬＴよりも大きいときはＬＳＳとＬＳＴとを比較し（ス
テップＥ）、ＬＳＳがＬＳＴよりも小さいときは端子Ｓ
に最も近い位置で探索線ＳＳと交差する既配線を引き剥
し（ステップＩ）、ＬＳＳがＬＳＴよりも大きいときは
端子Ｔに最も近い位置で探索線ＳＴと交差する既配線を
引き剥し（ステップＦ）、端子Ｓと端子Ｔとを結ぶ配線
経路を求め、次に、引き剥した既配線経路の再配線処理
を行なうことにより、未配線を減らし、配線率を向上さ
せる。
【０００７】具体例により詳述すると、図２には層毎に
配線の方向が決まった２層の配線領域を示しており、既
配線経路１４に遮られて、端子Ｓ１５と端子Ｔ１６とを
接続する配線経路の探索が失敗している。図３は端子Ｓ
１５から探索線ＳＳ２１、端子Ｔから探索線ＳＴ２２を
生成した状況を示す。そして、探索線ＳＳ２１上でスル
ーホールを置くことが可能な領域の線長ＬＳＳと探索線
ＳＴ２２上でスルーホールを置くことが可能な領域の線
長ＬＳＴとを求める。隣接層に障害物や既配線が存在す
るとスルーホールを置くことは出来ない。従って、線長
の単位を格子数（配線の最小ピッチを１格子とする）で
表すとすると、この例では線長ＬＳＳが３格子、線長Ｌ
ＳＴが０格子となる。閾値ＬＴを１格子とすると、線長
ＬＳＴがＬＴよりも小さいという条件を満たすので図１
のステップＤの条件を満たし、端子Ｔ１６に最も近い位
置で探索線ＳＴ２２と交差する既配線を引き剥すことに
なる。図４は端子Ｔ１６に最も近い位置で探索線ＳＴ２
２と交差する既配線を行き剥した状況を示している。そ
して、図５に示す様に、端子Ｓ１５と端子Ｔ１６とを結
ぶ配線経路を求める。次に図６に示す様に、先ほど引き
剥した配線経路をもう一度再配線する。これによって端
子Ｓ１５と端子Ｔ１６とを接続する配線経路と、既配線
の双方の配線が終了する。
配線の方向が決まった２層の配線領域を示しており、既
配線経路１４に遮られて、端子Ｓ１５と端子Ｔ１６とを
接続する配線経路の探索が失敗している。図３は端子Ｓ
１５から探索線ＳＳ２１、端子Ｔから探索線ＳＴ２２を
生成した状況を示す。そして、探索線ＳＳ２１上でスル
ーホールを置くことが可能な領域の線長ＬＳＳと探索線
ＳＴ２２上でスルーホールを置くことが可能な領域の線
長ＬＳＴとを求める。隣接層に障害物や既配線が存在す
るとスルーホールを置くことは出来ない。従って、線長
の単位を格子数（配線の最小ピッチを１格子とする）で
表すとすると、この例では線長ＬＳＳが３格子、線長Ｌ
ＳＴが０格子となる。閾値ＬＴを１格子とすると、線長
ＬＳＴがＬＴよりも小さいという条件を満たすので図１
のステップＤの条件を満たし、端子Ｔ１６に最も近い位
置で探索線ＳＴ２２と交差する既配線を引き剥すことに
なる。図４は端子Ｔ１６に最も近い位置で探索線ＳＴ２
２と交差する既配線を行き剥した状況を示している。そ
して、図５に示す様に、端子Ｓ１５と端子Ｔ１６とを結
ぶ配線経路を求める。次に図６に示す様に、先ほど引き
剥した配線経路をもう一度再配線する。これによって端
子Ｓ１５と端子Ｔ１６とを接続する配線経路と、既配線
の双方の配線が終了する。
【０００８】
【発明の効果】以上説明したように本発明によれば、集
積回路やプリント基板の多層配線領域における自動配線
処理の際に、未配線を減らし、配線率を向上させること
が出来る。
積回路やプリント基板の多層配線領域における自動配線
処理の際に、未配線を減らし、配線率を向上させること
が出来る。
【図１】本発明の一実施例の処理手順を示すフローチャ
ートである。
ートである。
【図２】端子対（端子Ｓ、端子Ｔ）の配線経路がみつか
らず、配線処理が失敗した状況を示した図。
らず、配線処理が失敗した状況を示した図。
【図３】端子Ｓおよび端子Ｔから各各探索線を生成し、
各各の探索線上でスルーホールを置くことが可能な領域
の線長を求めている状況を示した図。
各各の探索線上でスルーホールを置くことが可能な領域
の線長を求めている状況を示した図。
【図４】既配線を取り除いている状況を示した図。
【図５】端子Ｓと端子Ｔとを結ぶ配線経路を求めた状況
を示した図。
を示した図。
【図６】一度引き剥した端子対の配線処理をもう一度行
なっている状況を示した図。
なっている状況を示した図。
１１ 障害物 １２ 端子 １３ スルーホール １４ 既配線経路 １５ 端子Ｓ １６ 端子Ｔ ２１ 探索線ＳＳ ２２ 探索線ＳＴ
Claims (1)
- 【請求項１】 集積回路やプリント基板の多層配線領域
における自動配線処理方法において、第１の端子と第２
の端子との間の配線が出来ない場合、第１の端子から第
１の探索線を生成し、第２の端子から第２の探索線を生
成し、第１の探索線上でスルーホールを置くことが可能
な領域の第１の線長と第２の探索線上でスルーホールを
置くことが可能な領域の第２の線長を求め、予め定めた
閾値よりも第１の線長が小さいときは第１の端子に最も
近い位置で第１の探索線と交差する既配線を引き剥し、
前記閾値よりも第２の線長が小さいときは第２の端子に
最も近い位置で第２の探索線と交差する既配線を引き剥
し、第１および第２の線長の双方が前記閾値よりも大き
いときは第１の線長と第２の線長とを比較し、第１の線
長が第２の線長よりも小さいときは第１の端子に最も近
い位置で第１の探索線と交差する既配線を引き剥し、第
１の線長が第２の線長よりも大きいときは第２の端子に
最も近い位置で第２の探索線と交差する既配線を引き剥
して第１の端子と第２の端子とを結ぶ配線経路を求め、
引き剥した既配線経路の再配線処理を行なうことを特徴
とする自動配線処理方法。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP4271554A JPH06124321A (ja) | 1992-10-09 | 1992-10-09 | 自動配線処理方法 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP4271554A JPH06124321A (ja) | 1992-10-09 | 1992-10-09 | 自動配線処理方法 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH06124321A true JPH06124321A (ja) | 1994-05-06 |
Family
ID=17501694
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP4271554A Withdrawn JPH06124321A (ja) | 1992-10-09 | 1992-10-09 | 自動配線処理方法 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH06124321A (ja) |
Cited By (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5987743A (en) * | 1996-04-25 | 1999-11-23 | Nec Corporation | Automatic wiring device and its wiring method |
| US7284223B2 (en) | 2004-11-29 | 2007-10-16 | Fujitsu Limited | Wiring method, program, and apparatus |
| US7308667B2 (en) | 2004-11-29 | 2007-12-11 | Fujitsu Limited | LSI physical designing method, program, and apparatus |
| US7325218B2 (en) | 2004-11-29 | 2008-01-29 | Fujitsu Limited | Wiring method, program, and apparatus |
-
1992
- 1992-10-09 JP JP4271554A patent/JPH06124321A/ja not_active Withdrawn
Cited By (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5987743A (en) * | 1996-04-25 | 1999-11-23 | Nec Corporation | Automatic wiring device and its wiring method |
| US7284223B2 (en) | 2004-11-29 | 2007-10-16 | Fujitsu Limited | Wiring method, program, and apparatus |
| US7308667B2 (en) | 2004-11-29 | 2007-12-11 | Fujitsu Limited | LSI physical designing method, program, and apparatus |
| US7325218B2 (en) | 2004-11-29 | 2008-01-29 | Fujitsu Limited | Wiring method, program, and apparatus |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH07152802A (ja) | 配線設計方法 | |
| US4768154A (en) | Computer aided printed circuit board wiring | |
| JP2731288B2 (ja) | 多層配線方法 | |
| JPH06124321A (ja) | 自動配線処理方法 | |
| JP2574996B2 (ja) | 差動電流スイッチ対のルーティング方法 | |
| JP2874518B2 (ja) | 半導体装置及びその配線設計方法 | |
| JPH08107264A (ja) | 高密度配線板及びその製造方法 | |
| JP3014157B2 (ja) | 自動配線方式 | |
| JP3052561B2 (ja) | 自動配線方法 | |
| JP3088663B2 (ja) | 多層配線の自動配線方法 | |
| JPH0421074A (ja) | プリント配線板の自動改造処理方法 | |
| JPH05160600A (ja) | プリント板の自動配線方法 | |
| JPH07147324A (ja) | Ｃａｄ装置による自動配置配線処理方法 | |
| JPH0520789B2 (ja) | ||
| JPH05242201A (ja) | 配線層割り付け方法 | |
| JPH05242200A (ja) | 引きはがし再配線処理方式 | |
| JPH06163696A (ja) | 同電位端子のグルーピング方法 | |
| CN120354815A (zh) | 冗余通孔布设方法、相关装置及存储介质 | |
| JPH01292473A (ja) | 配線経路決定法 | |
| JPH06274571A (ja) | プリント板設計支援システムにおける自動配線処理方式 | |
| JPH05250441A (ja) | 配線設計方法 | |
| JP2002366599A (ja) | 平坦化パターン生成方法 | |
| JPH11260817A (ja) | 半導体集積回路の配線方法 | |
| JPH0512382A (ja) | 配線処理方式 | |
| JPS59181085A (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: 20000104 |