JPS59189471A - 配線経路探索システム - Google Patents
配線経路探索システムInfo
- Publication number
- JPS59189471A JPS59189471A JP58064778A JP6477883A JPS59189471A JP S59189471 A JPS59189471 A JP S59189471A JP 58064778 A JP58064778 A JP 58064778A JP 6477883 A JP6477883 A JP 6477883A JP S59189471 A JPS59189471 A JP S59189471A
- Authority
- JP
- Japan
- Prior art keywords
- route
- wiring
- point
- memory map
- 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.)
- Pending
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F30/00—Computer-aided design [CAD]
- G06F30/30—Circuit design
- G06F30/39—Circuit design at the physical level
- G06F30/394—Routing
Landscapes
- Engineering & Computer Science (AREA)
- Computer Hardware Design (AREA)
- Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Evolutionary Computation (AREA)
- Geometry (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
発明の属する技術分野
本発明は論理回路図の配線設計における配線経路探索シ
ステムに関する。
ステムに関する。
従来技術
従来、この種の配線経路探索は優先順位決定処理によっ
て決定された順にビン間の経路探索がプログラムで行な
われている。経路が見つからない場合には既配線を一つ
ずつ移動して経路探索の試行をくり返している。このよ
うな方法は非常に多数の試行を行なうだめ、多量のコン
ピュータ時間を要する。したがって、一定のくシ返しで
見つからない場合には接続子と発生させることにより飛
越し表示を行なっている。
て決定された順にビン間の経路探索がプログラムで行な
われている。経路が見つからない場合には既配線を一つ
ずつ移動して経路探索の試行をくり返している。このよ
うな方法は非常に多数の試行を行なうだめ、多量のコン
ピュータ時間を要する。したがって、一定のくシ返しで
見つからない場合には接続子と発生させることにより飛
越し表示を行なっている。
発明の目的
本発明の目的は論理回路図の配線経路探索において、＞
ＦＬ用コンピュータとソフトウェアでは多量のコンピュ
ータ時間を要していた点を解決し、短時間で配線経路を
探索する配線経路探索システムを提供することにある。
ＦＬ用コンピュータとソフトウェアでは多量のコンピュ
ータ時間を要していた点を解決し、短時間で配線経路を
探索する配線経路探索システムを提供することにある。
発明の構成
本発明のシステムは、与えられた２点間の配線経路を探
索する経路探索処理部と、 配線できなかった場合に既に配線された経路を
゛移動させる経路変更処理部と、 探索、変更のくシ返し制御およびデータの入出力を行な
う配線制御部と、 配線格子の占有状態を記憶するメモリ・マツプと、経路
情報を記憶する経路データ記憶部とを含む。
索する経路探索処理部と、 配線できなかった場合に既に配線された経路を
゛移動させる経路変更処理部と、 探索、変更のくシ返し制御およびデータの入出力を行な
う配線制御部と、 配線格子の占有状態を記憶するメモリ・マツプと、経路
情報を記憶する経路データ記憶部とを含む。
実施例
次に本発明について図面を参照して詳細に説明する。
第１図を参照すると、本発明の一実施例は配線制御部３
、配線経路探索部５、配線経路変更部６、およびメモリ
マツプ７から構成されている。
、配線経路探索部５、配線経路変更部６、およびメモリ
マツプ７から構成されている。
次にこの実施例の動作を詳細に説明する。
まず、配線制御部３は障害データを入力しメモリ・マツ
プ７上に禁止領域として展開する。次に配線制御部３は
配線の優先順位付けが行なわれている接続データを順次
人力して経路探索処理部５に渡す。
プ７上に禁止領域として展開する。次に配線制御部３は
配線の優先順位付けが行なわれている接続データを順次
人力して経路探索処理部５に渡す。
経路探索処理部５では与えられた２点間の接続データに
対し何種類かの限定したパターンによりメモリ・マツプ
上に探索して最も折れ曲りが少なくかつ既配線との交差
の少ない経路を探す。経路が見つからなかった場合には
経路変更処理部６により既配線の変更が行なわれる。こ
の配線変更処理は、まず経路探索処理部５で障害となっ
た既配経路上の障害点が格納され、経路変更処理部では
障害点からのトレースが行われ、既配線の始点・終点が
求められるとともにこの配線が取り消され求められた経
路がメモリ・マツプ上に展開される。
対し何種類かの限定したパターンによりメモリ・マツプ
上に探索して最も折れ曲りが少なくかつ既配線との交差
の少ない経路を探す。経路が見つからなかった場合には
経路変更処理部６により既配線の変更が行なわれる。こ
の配線変更処理は、まず経路探索処理部５で障害となっ
た既配経路上の障害点が格納され、経路変更処理部では
障害点からのトレースが行われ、既配線の始点・終点が
求められるとともにこの配線が取り消され求められた経
路がメモリ・マツプ上に展開される。
次に取シ消された接続データに対し隣接した領域で経路
探索がやり直され、経路が見つからなかった場合には他
の既配線の変更が試みられる。
探索がやり直され、経路が見つからなかった場合には他
の既配線の変更が試みられる。
配線変更処理が最後壕でくり返されても経路が′見つか
らない場合には接続子の発生を行ない飛越し表示とする
。
らない場合には接続子の発生を行ない飛越し表示とする
。
以上の処理は接続データの入力がなくなるまでくり返さ
れ、全部終了した時点で配線制御部３はメモリ・マツプ
のトレースを行ない配線経路データを抽出して田力を行
なう。
れ、全部終了した時点で配線制御部３はメモリ・マツプ
のトレースを行ない配線経路データを抽出して田力を行
なう。
続いて第２図を用いて経路探索処理部５の１例を説明す
る。与えられた２点間のデータに対し第２図に示すよう
な基本パターンが定義されており、単純なパターンから
順次探索が行なわれる。同一パターン内では第２図（ｂ
）で示されるように矢印の方向へ斜線部の範囲内で探索
が行なわれる。経路が見つかると既配線との交差数を記
憶しておき、引き続き探索が行なわれる。次に経路が見
つかると交差数の少ない方が選ばれる。
る。与えられた２点間のデータに対し第２図に示すよう
な基本パターンが定義されており、単純なパターンから
順次探索が行なわれる。同一パターン内では第２図（ｂ
）で示されるように矢印の方向へ斜線部の範囲内で探索
が行なわれる。経路が見つかると既配線との交差数を記
憶しておき、引き続き探索が行なわれる。次に経路が見
つかると交差数の少ない方が選ばれる。
１パターンでの経路の探索は斜線の範囲内全部が終了す
るか、斜線部の接続を除いた経路ですでに交差数が記憶
されている交差数より多くなった時点で終了し、経路が
見つかっていればメモリ・マツプ上に経路が展開され探
索処理は終了する。
るか、斜線部の接続を除いた経路ですでに交差数が記憶
されている交差数より多くなった時点で終了し、経路が
見つかっていればメモリ・マツプ上に経路が展開され探
索処理は終了する。
経路が見つからない場合には次のパターンによシ探索が
進められる。
進められる。
次に第３図を用いて経路変更処理部６の１例を説明する
。第３図（ａ）において■〜■間の配線を行なう場合に
は既配線経路性）〜■との障害点（３）が与えられると
、既配線をトレースすることより始点■終点（５）が求
められる。始点■および終点■がスタックに格納され、
メモリマツプ上から配線経路（４）〜■が削除される。
。第３図（ａ）において■〜■間の配線を行なう場合に
は既配線経路性）〜■との障害点（３）が与えられると
、既配線をトレースすることより始点■終点（５）が求
められる。始点■および終点■がスタックに格納され、
メモリマツプ上から配線経路（４）〜■が削除される。
続いて経路探宛部により経路■〜りが探索されメモリ・
マツプに展開される。ここで経路が見つからない場合に
は次の障害点からの既配線経路の削除がくり返される。
マツプに展開される。ここで経路が見つからない場合に
は次の障害点からの既配線経路の削除がくり返される。
経路■〜■が見つかると、スタックに格納”されている
始点終点データが取シ出されて、＠接した経路（′Ｇ）
〜■を同様の処理でスタックに格納して（（１）〜（５
）の経路を挿入して行く。隣接した障害経路がなくなる
までこの処理はくり返される。
始点終点データが取シ出されて、＠接した経路（′Ｇ）
〜■を同様の処理でスタックに格納して（（１）〜（５
）の経路を挿入して行く。隣接した障害経路がなくなる
までこの処理はくり返される。
本発明には配線経路探索処理システムにより配線経路を
短時間で簡単に求めることができるという効果がある。
短時間で簡単に求めることができるという効果がある。
第１図は本発明の一実施例を示す図、第２図はは本発明
における配線経路パターンの１例を示す図および第３図
は配線経路変更処理部での１例を示す図である。 第１図にお匠て、１・・・・・・接続情報データ、２・
・・・・・障害情報データ、３・・・・・・配線制御部
、４・・・・・・配線経路帽着データ、訃・輪・・配線
経路探索部、６・・・・・・配線経路変更部、７・・・
・・・メモリ・マンプ部始轡 終よ （ａｒ） φｈｓ （ｂ）（Ｉ））′ （Ｃ） 第３図
における配線経路パターンの１例を示す図および第３図
は配線経路変更処理部での１例を示す図である。 第１図にお匠て、１・・・・・・接続情報データ、２・
・・・・・障害情報データ、３・・・・・・配線制御部
、４・・・・・・配線経路帽着データ、訃・輪・・配線
経路探索部、６・・・・・・配線経路変更部、７・・・
・・・メモリ・マンプ部始轡 終よ （ａｒ） φｈｓ （ｂ）（Ｉ））′ （Ｃ） 第３図
Claims (1)
- 【特許請求の範囲】 論理回路図の配線経路を何種類かの限定された接続パタ
ーンで探索する経路探索処理部と、探索された経路デー
タを記憶する経路データ記憶部と、 配線できなかった場合に既配線経路を移動するための配
線変更処理部と、 経路探索と変更処理の実行を制御する経路探索制御部と
を含むことを特徴とする配線経路探索システム。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP58064778A JPS59189471A (ja) | 1983-04-13 | 1983-04-13 | 配線経路探索システム |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP58064778A JPS59189471A (ja) | 1983-04-13 | 1983-04-13 | 配線経路探索システム |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPS59189471A true JPS59189471A (ja) | 1984-10-27 |
Family
ID=13268002
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP58064778A Pending JPS59189471A (ja) | 1983-04-13 | 1983-04-13 | 配線経路探索システム |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPS59189471A (ja) |
Cited By (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS61196374A (ja) * | 1985-02-27 | 1986-08-30 | Fujitsu Ltd | 回路図自動生成方法 |
| US4642890A (en) * | 1985-10-31 | 1987-02-17 | At&T Technologies, Inc. | Method for routing circuit boards |
| US4752887A (en) * | 1985-03-01 | 1988-06-21 | Nec Corporation | Routing method for use in wiring design |
| JPH03167669A (ja) * | 1989-11-28 | 1991-07-19 | Nec Corp | 自動配線設計装置 |
-
1983
- 1983-04-13 JP JP58064778A patent/JPS59189471A/ja active Pending
Cited By (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS61196374A (ja) * | 1985-02-27 | 1986-08-30 | Fujitsu Ltd | 回路図自動生成方法 |
| US4752887A (en) * | 1985-03-01 | 1988-06-21 | Nec Corporation | Routing method for use in wiring design |
| US4642890A (en) * | 1985-10-31 | 1987-02-17 | At&T Technologies, Inc. | Method for routing circuit boards |
| JPH03167669A (ja) * | 1989-11-28 | 1991-07-19 | Nec Corp | 自動配線設計装置 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US4758953A (en) | Method for generating logic circuit data | |
| EP0612020B1 (en) | Method for placement of nodes in a graph based diagram | |
| JPH0736123B2 (ja) | 設備群制御方法 | |
| JPS59189471A (ja) | 配線経路探索システム | |
| JPH0421910B2 (ja) | ||
| EP0302547B1 (en) | Device for executing a search in a topological representation of a geographical interconnection network. | |
| JP2897541B2 (ja) | 閉図形抽出方法 | |
| JP2005084993A (ja) | 故障診断支援装置 | |
| JPS59108105A (ja) | 最短ル−ト検索方式 | |
| JP3293640B2 (ja) | 回路データ接続追跡システム | |
| Rose | Computer aided design of printed wiring boards | |
| JP2722684B2 (ja) | ファイルシステムの検索装置 | |
| JPS63133274A (ja) | 配線処理方式 | |
| JP2734107B2 (ja) | 画像データの芯線化処理方法 | |
| JPH04288593A (ja) | 画像表示装置 | |
| JPH07104876B2 (ja) | 設計支援方法及び設計支援装置 | |
| CN119090107A (zh) | 设备调度方法、装置、电子设备及计算机可读存储介质 | |
| JPS59188772A (ja) | 経路探索処理方式 | |
| JPH04369081A (ja) | 自動配線方法およびそのための装置 | |
| JPH05151292A (ja) | 経路探索処理方法 | |
| JPH02244382A (ja) | Ｃａｄにおける回路チェック方法 | |
| JPS63155740A (ja) | 配線処理方式 | |
| JPS6155780A (ja) | 経路探索システム | |
| JPS62239273A (ja) | 階層的パターンレイアウト方法 | |
| JPH05250410A (ja) | 階層シンボル修正システム |