JPH01293472A - Ｃａｄによる回路基板の配線経路探索方法 - Google Patents
Ｃａｄによる回路基板の配線経路探索方法Info
- Publication number
- JPH01293472A JPH01293472A JP63124125A JP12412588A JPH01293472A JP H01293472 A JPH01293472 A JP H01293472A JP 63124125 A JP63124125 A JP 63124125A JP 12412588 A JP12412588 A JP 12412588A JP H01293472 A JPH01293472 A JP H01293472A
- Authority
- JP
- Japan
- Prior art keywords
- wiring
- route
- idle line
- processing
- empty line
- 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 (1)
- 【特許請求の範囲】 配線可能な空ライン領域と配線不能な障害物領域とに区
分された配線走行軸が回路基板上に複数本、主配線方向
に平行して縦列配列され、 始点位置を含む空ライン領域から上下方向に探索を開始
して当該空ライン領域に隣接する上下方向の空ライン領
域を各空ライン領域に追番を付加しつつ順次に探索し、 終点位置を含む空ライン領域に到達したのならば径路探
索処理を完了し、 各空ライン領域に付加された追番に従って始点位置から
終点位置への配線径路を決定するように構成されたＣＡ
Ｄによる回路基板の配線径路探索方式。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP63124125A JPH0652532B2 (ja) | 1988-05-20 | 1988-05-20 | Ｃａｄによる回路基板の配線経路探索方法 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP63124125A JPH0652532B2 (ja) | 1988-05-20 | 1988-05-20 | Ｃａｄによる回路基板の配線経路探索方法 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH01293472A true JPH01293472A (ja) | 1989-11-27 |
| JPH0652532B2 JPH0652532B2 (ja) | 1994-07-06 |
Family
ID=14877546
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP63124125A Expired - Fee Related JPH0652532B2 (ja) | 1988-05-20 | 1988-05-20 | Ｃａｄによる回路基板の配線経路探索方法 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH0652532B2 (ja) |
-
1988
- 1988-05-20 JP JP63124125A patent/JPH0652532B2/ja not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| JPH0652532B2 (ja) | 1994-07-06 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH0550780B2 (ja) | ||
| JPH04241072A (ja) | 配線経路探索装置及び配線経路探索方法 | |
| JPH0786883B2 (ja) | 網図または諭理回路図自動生成方法およびそのシステム | |
| US5825659A (en) | Method for local rip-up and reroute of signal paths in an IC design | |
| US5394337A (en) | Method for wire routing of a semiconductor integrated circuit and apparatus for implementing the same | |
| JP2536189B2 (ja) | 自動配線方法 | |
| JPH0652532B2 (ja) | Ｃａｄによる回路基板の配線経路探索方法 | |
| JP3208014B2 (ja) | 配線経路調査装置および配線経路調査方法 | |
| JPS5846173B2 (ja) | 論理配線設計方式 | |
| JPH0327474A (ja) | 半導体集積回路用ネットリストの修正方法 | |
| JPS6140674A (ja) | 経路探索処理システム | |
| JP3006156B2 (ja) | 自動配線方式 | |
| JP2752530B2 (ja) | 自動配線方法およびそのための装置 | |
| JP2938910B2 (ja) | 三次元配線方法 | |
| JP3006244B2 (ja) | 自動配線方式 | |
| JPS63314846A (ja) | 一層配線方式 | |
| JPS62209890A (ja) | 自動配線方法 | |
| JPS62115574A (ja) | 並列配線方式 | |
| JPH0645446A (ja) | 配置配線方法 | |
| JPS59188772A (ja) | 経路探索処理方式 | |
| JPS63239963A (ja) | 配線径路決定方法 | |
| JPH01305474A (ja) | 未配線区間配線支援方法 | |
| JPH02126368A (ja) | 接続経路探索方法 | |
| JPH04199279A (ja) | 素子間配線設計方法および素子間配線設計装置 | |
| JPH04290171A (ja) | 自動配線方式 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| LAPS | Cancellation because of no payment of annual fees |