JPH026102B2 - - Google Patents
Info
- Publication number
- JPH026102B2 JPH026102B2 JP56033375A JP3337581A JPH026102B2 JP H026102 B2 JPH026102 B2 JP H026102B2 JP 56033375 A JP56033375 A JP 56033375A JP 3337581 A JP3337581 A JP 3337581A JP H026102 B2 JPH026102 B2 JP H026102B2
- Authority
- JP
- Japan
- Prior art keywords
- wiring
- route
- data
- register
- search area
- 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
Landscapes
- Internal Circuitry In Semiconductor Integrated Circuit Devices (AREA)
Description
【発明の詳細な説明】
この発明はプリント基板又はLSIチツプ上で、
部品の配置が与えられた時、部品のピン間の結線
を指定された径路の範囲内で誤りなく自動的に配
線を発見し、格納する配線径路発見装置に関する
ものである。
部品の配置が与えられた時、部品のピン間の結線
を指定された径路の範囲内で誤りなく自動的に配
線を発見し、格納する配線径路発見装置に関する
ものである。
従来、部品のピン間の結線を行なう場合は、ピ
ン間に存在する径路を試行錯誤的にプログラムで
発見する方法か、又は、ピンからピンへのすべて
の配線径路パターンを完全に人が与える方法のい
ずれかをとつている。ピン間に存在する径路をプ
ログラムで発見する方法は径路が１つ見つかれ
ば、径路探索は終了する方法である。〔文献
Rubin、F.、“Chapter6、”in Design
Automation of Digital Syatems、Vol.1、M.A.
Breuer、Ed.、Prentice−Hall、1972.を参照〕。
そのため、複数個の可能な径路がある場合、その
内の特定な径路を指定して求めることはできな
い。ピンからピンへのすべての配線径路パターン
を完全に人が与える方法は、人が与えるという操
作があるために、誤りのある配線径路パターン又
は結線ミスが生じる可能性が十分にあり、信頼性
の高い設計を行なうことが困難である。
ン間に存在する径路を試行錯誤的にプログラムで
発見する方法か、又は、ピンからピンへのすべて
の配線径路パターンを完全に人が与える方法のい
ずれかをとつている。ピン間に存在する径路をプ
ログラムで発見する方法は径路が１つ見つかれ
ば、径路探索は終了する方法である。〔文献
Rubin、F.、“Chapter6、”in Design
Automation of Digital Syatems、Vol.1、M.A.
Breuer、Ed.、Prentice−Hall、1972.を参照〕。
そのため、複数個の可能な径路がある場合、その
内の特定な径路を指定して求めることはできな
い。ピンからピンへのすべての配線径路パターン
を完全に人が与える方法は、人が与えるという操
作があるために、誤りのある配線径路パターン又
は結線ミスが生じる可能性が十分にあり、信頼性
の高い設計を行なうことが困難である。
本発明の目的は、以上の点を鑑み、人が通した
い配線径路の点データを与え、その点データを通
る配線径路を実際に探すのは人間ではなく、装置
であるという方式をとることによつて、迅速に、
かつ誤りなく、所望の配線径路を発見することで
ある。
い配線径路の点データを与え、その点データを通
る配線径路を実際に探すのは人間ではなく、装置
であるという方式をとることによつて、迅速に、
かつ誤りなく、所望の配線径路を発見することで
ある。
以下、本発明の原理を詳細に説明する。第１図
は本発明の原理を示すブロツクフローである。ブ
ロツク１において結線を行なうべき部品ピンと配
線径路として通したい基板上の点データを認識す
る。今、部品ピンをＡとＢとし、径路として指定
する点をCi（ｉ＝１、２、……、ｎ）とする。Ａ、
Ｂ、Ciの基板上の座標値を（Ax、Ay）、（Bx、
By）、（Ci x、Ci y）とする。ブロツク２において、
座標値（Ax、Ay）、（Bx、By）、（Ci x、Ci y）（ｉ＝
１、２、…、ｎ）をもとに、配線径路探索の領域
を計算する。まづ、座標値（Ax、Ay）と（C1 x、
C1 y）とで決まる長方形の領域をD1、座標値
（C1 x、C1 y）と（C2 x、C2 y）とで決まる長方形の
領域をD2、以下、座標値（Ci x、Ci y）と（Cx i+1、
Cy i+1）とで決まる長方形の領域をDi+1（ｉ＝１、
２、…、ｎ−１）とする。最後に、座標値（Co x、
Co y）と（Bx、By）とで決まる長方形の領域を
Do+1とする。Di（ｉ＝１、２、…、ｎ＋１）を配
線径路探索領域という。第２図は配線径路探索領
域の一例である。部品１′のピン３′と部品２′の
ピン４′とを結ぶ際に、点５′〜７′を指定したと
き、斜線を付した部分８′〜１１′が計算された配
線径路探索領域である。第１図に戻り、ブロツク
３においては、ブロツク２で求まつた配線径路探
索領域内で、結線を行なうべき部品ピン間を結ぶ
配線径路を探索する。この探索は探索アルゴリズ
ムを内蔵した装置により、行なわれる。ブロツク
４では配線径路が発見されたか否かを判定し、配
線径路が発見されたならば、ブロツク５におい
て、その径路を格納し、配線径路が発見されなか
つたならば、ブロツク６において、径路発見不可
能の表示を行なう。結線すべき部品ピンを認識し
ていること、配線径路の領域を点列をもとに計算
して配線径路探索領域を限定していることの２つ
の事実をもとに、径路探索の発見を探索アルゴリ
ズムを内蔵した装置で行なうために、誤りがな
く、かつ迅速に、通したい配線径路の発見が可能
である。
は本発明の原理を示すブロツクフローである。ブ
ロツク１において結線を行なうべき部品ピンと配
線径路として通したい基板上の点データを認識す
る。今、部品ピンをＡとＢとし、径路として指定
する点をCi（ｉ＝１、２、……、ｎ）とする。Ａ、
Ｂ、Ciの基板上の座標値を（Ax、Ay）、（Bx、
By）、（Ci x、Ci y）とする。ブロツク２において、
座標値（Ax、Ay）、（Bx、By）、（Ci x、Ci y）（ｉ＝
１、２、…、ｎ）をもとに、配線径路探索の領域
を計算する。まづ、座標値（Ax、Ay）と（C1 x、
C1 y）とで決まる長方形の領域をD1、座標値
（C1 x、C1 y）と（C2 x、C2 y）とで決まる長方形の
領域をD2、以下、座標値（Ci x、Ci y）と（Cx i+1、
Cy i+1）とで決まる長方形の領域をDi+1（ｉ＝１、
２、…、ｎ−１）とする。最後に、座標値（Co x、
Co y）と（Bx、By）とで決まる長方形の領域を
Do+1とする。Di（ｉ＝１、２、…、ｎ＋１）を配
線径路探索領域という。第２図は配線径路探索領
域の一例である。部品１′のピン３′と部品２′の
ピン４′とを結ぶ際に、点５′〜７′を指定したと
き、斜線を付した部分８′〜１１′が計算された配
線径路探索領域である。第１図に戻り、ブロツク
３においては、ブロツク２で求まつた配線径路探
索領域内で、結線を行なうべき部品ピン間を結ぶ
配線径路を探索する。この探索は探索アルゴリズ
ムを内蔵した装置により、行なわれる。ブロツク
４では配線径路が発見されたか否かを判定し、配
線径路が発見されたならば、ブロツク５におい
て、その径路を格納し、配線径路が発見されなか
つたならば、ブロツク６において、径路発見不可
能の表示を行なう。結線すべき部品ピンを認識し
ていること、配線径路の領域を点列をもとに計算
して配線径路探索領域を限定していることの２つ
の事実をもとに、径路探索の発見を探索アルゴリ
ズムを内蔵した装置で行なうために、誤りがな
く、かつ迅速に、通したい配線径路の発見が可能
である。
以下、本発明の一実施例を図面を用いて説明す
る。第３図は本発明の一実施例の回路ブロツク図
であり、記憶装置１０、入出力装置２０、制御装
置３０、探索装置４０、および格納装置５０とか
ら構成される。記憶装置１０は、結線データ記憶
装置１１、部品構造データ記憶装置１２と基板構
造データ記憶装置１３および所望のデータ要素を
格納するレジスタ１４，１５，１６とからなる。
レジスタ１４には結線すべき部品ピンデータが格
納される。入出力装置２０は入出力制御装置２１
とレジスタ２２とからなる。通したい配線径路の
点データは入出力制御装置２１により読取り、レ
ジスタ２２に格納される。制御装置３０は高速メ
モリ３１、制御回路３２、同期回路３３、探索領
域計算装置３３、およびレジスタ３５〜３７から
なる。高速メモリ３１はレジスタ１５とレジスタ
１６を通して部品構造データ記憶装置１２と基板
構造データ記憶装置１３にあるデータを格納す
る。制御回路３２は、レジスタ１４とレジスタ２
２に格納されたデータを制御してレジスタ３６に
格納する。探索領域計算装置３４は高速メモリの
データをレジスタ３５を介して読みとり、レジス
タ３６のデータとともに、配線径路の探索領域を
計算する。探索領域計算装置は、同期回路３３に
よつて発生された同期クロツクに従つて、レジス
タ３６に格納されたデータを１個づつ読みとり、
最も新しく読みとつたデータ（Xi、Yi）と、１つ
前に読みとつたデータ（Xi-1、Yi-1）によつて決
まる長方形の領域を計算する。この長方形領域の
座標値は(1)式によつて与えられる。
る。第３図は本発明の一実施例の回路ブロツク図
であり、記憶装置１０、入出力装置２０、制御装
置３０、探索装置４０、および格納装置５０とか
ら構成される。記憶装置１０は、結線データ記憶
装置１１、部品構造データ記憶装置１２と基板構
造データ記憶装置１３および所望のデータ要素を
格納するレジスタ１４，１５，１６とからなる。
レジスタ１４には結線すべき部品ピンデータが格
納される。入出力装置２０は入出力制御装置２１
とレジスタ２２とからなる。通したい配線径路の
点データは入出力制御装置２１により読取り、レ
ジスタ２２に格納される。制御装置３０は高速メ
モリ３１、制御回路３２、同期回路３３、探索領
域計算装置３３、およびレジスタ３５〜３７から
なる。高速メモリ３１はレジスタ１５とレジスタ
１６を通して部品構造データ記憶装置１２と基板
構造データ記憶装置１３にあるデータを格納す
る。制御回路３２は、レジスタ１４とレジスタ２
２に格納されたデータを制御してレジスタ３６に
格納する。探索領域計算装置３４は高速メモリの
データをレジスタ３５を介して読みとり、レジス
タ３６のデータとともに、配線径路の探索領域を
計算する。探索領域計算装置は、同期回路３３に
よつて発生された同期クロツクに従つて、レジス
タ３６に格納されたデータを１個づつ読みとり、
最も新しく読みとつたデータ（Xi、Yi）と、１つ
前に読みとつたデータ（Xi-1、Yi-1）によつて決
まる長方形の領域を計算する。この長方形領域の
座標値は(1)式によつて与えられる。
左下Ｘ座標値＝Min（Xi-1、Xi）
左下Ｙ座標値＝Min（Yi-1、Yi）
右上Ｘ座標値＝Max（Xi-1、Xi）
右上Ｙ座標値＝Max（Yi-1、Yi） (1)
計算された探索領域は、レジスタ３７に格納さ
れる。探索装置４０は径路探索装置４１とレジス
タ４２，４３とからなる。制御装置３０によつて
計算された、レジスタ３７に格納されている径路
探索領域のデータを参照し、径路探索装置４１
は、結線すべき部品ピン間の径路探索の発見を行
なう。径路探索装置は１点から１点へ到る径路を
探索するもので、もし複数個の可能な径路があれ
ば、その内で長さが最小となるものを見つける。
径路探索装置の一実施例としては特開昭50−
129887号に開示された方式を用いることができ
る。すなわち、遅延回路と検知回路で構成された
電気回路網上で、ステツプ信号で伝搬過程をたど
ることによつて、径路を発見することが可能であ
る。部品ピン間の径路発見が成功した場合は、レ
ジスタ４２に“１”を格納し、レジスタ４３に配
線径路のデータを格納する。径路発見が不成功の
場合は、レジスタ４２に“０”を格納する。格納
装置５０は判定回路５１と径路格納装置５２とレ
ジスタ５３とからなる。レジスタ４２のデータが
“０”の場合は、判定回路５１はレジスタ５３に
“０”を格納する。レジスタ４２のデータが“１”
の場合は、判定回路はレジスタ５３に“１”を格
納し、径路格納装置５２はレジスタ４３のデータ
を判定回路５１を通して受け取り、格納する。以
上の例に限らず要は通したい径路を点列で与える
ことにより、配線径路探索領域を発生させ、この
領域内で径路探索を行なうことによつて、本発明
は容易に実施される。
れる。探索装置４０は径路探索装置４１とレジス
タ４２，４３とからなる。制御装置３０によつて
計算された、レジスタ３７に格納されている径路
探索領域のデータを参照し、径路探索装置４１
は、結線すべき部品ピン間の径路探索の発見を行
なう。径路探索装置は１点から１点へ到る径路を
探索するもので、もし複数個の可能な径路があれ
ば、その内で長さが最小となるものを見つける。
径路探索装置の一実施例としては特開昭50−
129887号に開示された方式を用いることができ
る。すなわち、遅延回路と検知回路で構成された
電気回路網上で、ステツプ信号で伝搬過程をたど
ることによつて、径路を発見することが可能であ
る。部品ピン間の径路発見が成功した場合は、レ
ジスタ４２に“１”を格納し、レジスタ４３に配
線径路のデータを格納する。径路発見が不成功の
場合は、レジスタ４２に“０”を格納する。格納
装置５０は判定回路５１と径路格納装置５２とレ
ジスタ５３とからなる。レジスタ４２のデータが
“０”の場合は、判定回路５１はレジスタ５３に
“０”を格納する。レジスタ４２のデータが“１”
の場合は、判定回路はレジスタ５３に“１”を格
納し、径路格納装置５２はレジスタ４３のデータ
を判定回路５１を通して受け取り、格納する。以
上の例に限らず要は通したい径路を点列で与える
ことにより、配線径路探索領域を発生させ、この
領域内で径路探索を行なうことによつて、本発明
は容易に実施される。
第１図は本発明の原理を示すブロツク図、第２
図は配線径路探索領域の一例を示す図、第３図は
本発明の一実施例の回路ブロツク図である。図に
おいては１１は結線データ記憶装置、１２は部品
構造データ記憶装置、１３は基盤構造データ記憶
装置、２１は入出力制御装置、３１は高速メモ
リ、３２は制御回路、３３は同期回路、３４は探
索領域計算装置、４１は径路探索装置、５１は判
定回路、５２は径路格納装置、１４乃至１６，２
２，３５乃至３７，４２乃至４３および５３はレ
ジスタをそれぞれ示す。
図は配線径路探索領域の一例を示す図、第３図は
本発明の一実施例の回路ブロツク図である。図に
おいては１１は結線データ記憶装置、１２は部品
構造データ記憶装置、１３は基盤構造データ記憶
装置、２１は入出力制御装置、３１は高速メモ
リ、３２は制御回路、３３は同期回路、３４は探
索領域計算装置、４１は径路探索装置、５１は判
定回路、５２は径路格納装置、１４乃至１６，２
２，３５乃至３７，４２乃至４３および５３はレ
ジスタをそれぞれ示す。
Claims (1)
- １ あらかじめ与えられた結線データと部品構造
データと基板構造データとを格納した記憶装置
と、配線が通る径路の範囲を指定した点データを
入力する入出力装置と、前記の２つの装置から読
み出されたデータをもとに配線径路探索領域を計
算する径路探索領域計算装置と配線径路探索領域
のもとで部品のピンと他の部品のピンとを結ぶ配
線径路を探す径路探索装置と、配線径路を格納す
る格納装置を有し、与えられた結線データと部品
構造データと基板構造データをもとに入力された
配線が通る径路の範囲において、誤りなく配線の
径路を発見し、格納するようにしたことを特徴と
する配線径路発見装置。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP56033375A JPS57148390A (en) | 1981-03-09 | 1981-03-09 | Device for discovering wiring route |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP56033375A JPS57148390A (en) | 1981-03-09 | 1981-03-09 | Device for discovering wiring route |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS57148390A JPS57148390A (en) | 1982-09-13 |
| JPH026102B2 true JPH026102B2 (ja) | 1990-02-07 |
Family
ID=12384834
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP56033375A Granted JPS57148390A (en) | 1981-03-09 | 1981-03-09 | Device for discovering wiring route |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPS57148390A (ja) |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS61102090A (ja) * | 1984-10-25 | 1986-05-20 | 富士通株式会社 | プリント板の配線方式 |
Family Cites Families (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS5842621B2 (ja) * | 1976-10-18 | 1983-09-21 | 日本電信電話株式会社 | 配線径路決定装置 |
-
1981
- 1981-03-09 JP JP56033375A patent/JPS57148390A/ja active Granted
Also Published As
| Publication number | Publication date |
|---|---|
| JPS57148390A (en) | 1982-09-13 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH026102B2 (ja) | ||
| JPH0644595B2 (ja) | 配線処理方式 | |
| JP3014157B2 (ja) | 自動配線方式 | |
| JP3144785B2 (ja) | 信号遅延時間計算方法 | |
| JP2829075B2 (ja) | スルーホール生成方法 | |
| JPH03262144A (ja) | 半導体集積回路の配線方式 | |
| JP2914025B2 (ja) | Ｌｓｉの自動配置配線処理方法 | |
| JPH03231372A (ja) | 自動配線方法 | |
| JPH06266801A (ja) | フロアプランを考慮した論理合成方法 | |
| JPH04238576A (ja) | 遅延シミュレーション方式 | |
| JP2876596B2 (ja) | 配線処理方式 | |
| JPH0696156A (ja) | 遅延時間計算装置 | |
| JPH118308A (ja) | 遅延時間計算方法 | |
| JPH08129487A (ja) | プログラムシーケンス制御回路 | |
| JPH04260965A (ja) | ２点間の径路探索方法 | |
| JPH04142673A (ja) | 配線経路探索装置 | |
| JPH0498853A (ja) | 集積回路自動配線システム | |
| JPH01234980A (ja) | 配線経路表示装置 | |
| JPH01120672A (ja) | 回路接続情報生成方式 | |
| JPH01305474A (ja) | 未配線区間配線支援方法 | |
| JPH01288971A (ja) | 論理回路のパストレース処理方式 | |
| JPH02238573A (ja) | 配線経路探索装置 | |
| JPH05742B2 (ja) | ||
| JPS635794B2 (ja) | ||
| JPH02222072A (ja) | 多層同時配線方法 |