JPH01106264A - 配線経路探索方式 - Google Patents
配線経路探索方式Info
- Publication number
- JPH01106264A JPH01106264A JP62264247A JP26424787A JPH01106264A JP H01106264 A JPH01106264 A JP H01106264A JP 62264247 A JP62264247 A JP 62264247A JP 26424787 A JP26424787 A JP 26424787A JP H01106264 A JPH01106264 A JP H01106264A
- Authority
- JP
- Japan
- Prior art keywords
- wiring
- route
- points
- point
- length
- 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
- 238000000034 method Methods 0.000 claims abstract description 38
- 239000000919 ceramic Substances 0.000 claims description 3
- 239000000284 extract Substances 0.000 abstract 1
- 238000010586 diagram Methods 0.000 description 3
- 230000000694 effects Effects 0.000 description 3
- 238000007796 conventional method Methods 0.000 description 1
- 230000010365 information processing Effects 0.000 description 1
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
〔産業上の利用分野〕
本発明はプリント配線板、セラミック配線板。
集積回路等の配線設計に用いられる配線経路探索方式に
関する。
関する。
プリント配線板等の配線設計において結線すべき２点間
（配線区間と呼ぶ）の配線経路を決定する従来の配線経
路探索方式としては、迷路法や線分探索法などが知られ
ており、何れの方式も本質的になるべ（短い経路を採用
する特性を持っている（例えば、昭和５６年３月２０日
に情報処理学会より発行された「論理装置のＣＡＤＪ第
４３頁〜第５０頁、３．３．２ ｒ配線」参照）。
（配線区間と呼ぶ）の配線経路を決定する従来の配線経
路探索方式としては、迷路法や線分探索法などが知られ
ており、何れの方式も本質的になるべ（短い経路を採用
する特性を持っている（例えば、昭和５６年３月２０日
に情報処理学会より発行された「論理装置のＣＡＤＪ第
４３頁〜第５０頁、３．３．２ ｒ配線」参照）。
上述した従来の配線経路探索方式は、配線区間の配線経
路の決定において、配線経路の探索を可能な限り短い配
線長が得られるように行なっているため、配線遅延時間
を問題とする配線設計には必ずしも適するとは限らない
。即ち、他の配線区間の配線遅延時間との関係などから
、配線区間を最短ではなく成る程度遠回りしてでもその
配線区間の配線遅延時間を所定値内に収める設計を行な
う場合が近年益々増大しているが、このような配線設計
には従来方式は使用できない。
路の決定において、配線経路の探索を可能な限り短い配
線長が得られるように行なっているため、配線遅延時間
を問題とする配線設計には必ずしも適するとは限らない
。即ち、他の配線区間の配線遅延時間との関係などから
、配線区間を最短ではなく成る程度遠回りしてでもその
配線区間の配線遅延時間を所定値内に収める設計を行な
う場合が近年益々増大しているが、このような配線設計
には従来方式は使用できない。
本発明はこのような事情に鑑みて為されたものであり、
その目的は、配線区間の配線長がほぼ指定された配線長
になるような配線経路を決定することができる配線経路
探索方式を提供することにある。
その目的は、配線区間の配線長がほぼ指定された配線長
になるような配線経路を決定することができる配線経路
探索方式を提供することにある。
本発明は上記目的を達成するために、
プリント配線板、セラミック配線板、集積回路等の配線
設計での結線すべき配線区間の配線経路を決定する配線
経路探索方式において、結線すべき２点各々から探索可
能であり且つ結線すべき２点それぞれから独立に計算し
た最短の配線長の和が予め指定された配線長に等しい点
を配線経路が途中で経由する経由点の候補として探索し
、 該探索された一つ以上の経由点の候補それぞれについて
、結線すべき一方の点と経由点との間の最短の配線経路
を求めると共に、該求めた配線経路を配線禁止区域にし
て結線すべき他方の点と経由点との間の配線経路を求め
、該求めた二つの配線経路を併せた経路を配線経路の候
補とし、該配線経路の候補の中から一つの配線経路を選
択するように構成される。
設計での結線すべき配線区間の配線経路を決定する配線
経路探索方式において、結線すべき２点各々から探索可
能であり且つ結線すべき２点それぞれから独立に計算し
た最短の配線長の和が予め指定された配線長に等しい点
を配線経路が途中で経由する経由点の候補として探索し
、 該探索された一つ以上の経由点の候補それぞれについて
、結線すべき一方の点と経由点との間の最短の配線経路
を求めると共に、該求めた配線経路を配線禁止区域にし
て結線すべき他方の点と経由点との間の配線経路を求め
、該求めた二つの配線経路を併せた経路を配線経路の候
補とし、該配線経路の候補の中から一つの配線経路を選
択するように構成される。
〔作用〕 。
先ず、結線すべき２点それぞれから探索可能な最短の配
線長の和が予め指定された配線長に等しい点である経路
点を求め、次にこの経由点と結線すべき一方の点との間
の最短の配線経路を求め、次にこの求めた配線経路を配
線禁止区域にして結線すべき他方の点と経由点との間の
配線経路を求め、この求めた二つの配線経路を併せた経
路を配線経路の候補としたので、結線すべき２点間の配
線長をほぼ指定長とすることができる。また、複数の配
ｖＡ経路の候補が得られた場合、最も配線長の短いもの
を選択することにより、指定長に等しい或いは最も近い
配線経路を得ることができる。
線長の和が予め指定された配線長に等しい点である経路
点を求め、次にこの経由点と結線すべき一方の点との間
の最短の配線経路を求め、次にこの求めた配線経路を配
線禁止区域にして結線すべき他方の点と経由点との間の
配線経路を求め、この求めた二つの配線経路を併せた経
路を配線経路の候補としたので、結線すべき２点間の配
線長をほぼ指定長とすることができる。また、複数の配
ｖＡ経路の候補が得られた場合、最も配線長の短いもの
を選択することにより、指定長に等しい或いは最も近い
配線経路を得ることができる。
次に本発明の実施例について図面を参照して説明する。
第２図は本発明を実施する装置の一例を示すブロック図
であり、処理装置１と、メモリ２と、ＣＲＴ等の表示値
Ｗｔ、３と、この表示制御を行なう表示制御袋Ｗ４と、
磁気ディスク装置などの補助記憶装置５と、これを制御
する補助記憶制御ｌ装置６と、キーボード７と、これを
制御するキーボード制御装置８とを含んでいる。所定の
機能を果たすように設計された電気回路の設計情報（Ｉ
Ｉ能素子などブロックの配置情報、配線区間を特定する
情報、およびその配線区間に配線長を指定する場合には
その配線長の情報などを含む）は、補助記憶装置５に記
憶されており、配線処理を開始させる指示をキーボード
７から与えると、処理装置１は補助記憶装置５から設計
情報を読込んでメモリ２に格納すると共に、その設計情
報で表される電気回路のイメージを表示制御装置４によ
って表示装置３に表示させる。その後、処理装置ｌは第
１図に示す流れに従って、配線経路の決定を行ない、逐
次決定された配線経路はメモリ２に格納されると共に、
表示装置３にイメージとして表示される。
であり、処理装置１と、メモリ２と、ＣＲＴ等の表示値
Ｗｔ、３と、この表示制御を行なう表示制御袋Ｗ４と、
磁気ディスク装置などの補助記憶装置５と、これを制御
する補助記憶制御ｌ装置６と、キーボード７と、これを
制御するキーボード制御装置８とを含んでいる。所定の
機能を果たすように設計された電気回路の設計情報（Ｉ
Ｉ能素子などブロックの配置情報、配線区間を特定する
情報、およびその配線区間に配線長を指定する場合には
その配線長の情報などを含む）は、補助記憶装置５に記
憶されており、配線処理を開始させる指示をキーボード
７から与えると、処理装置１は補助記憶装置５から設計
情報を読込んでメモリ２に格納すると共に、その設計情
報で表される電気回路のイメージを表示制御装置４によ
って表示装置３に表示させる。その後、処理装置ｌは第
１図に示す流れに従って、配線経路の決定を行ない、逐
次決定された配線経路はメモリ２に格納されると共に、
表示装置３にイメージとして表示される。
以下、第１図を参照して本実施例の動作を説明する；
先ず、処理装置１はメモリ２に格納された設計情報を参
照し、未処理の配線区間が有るか否かを判定する（処理
Ｓ １−１）。無ければ配線経路探索処理を終了し、有
れば、未処理の配線区間を一つ取り出しく処理Ｓ １−
２）、その配線区間に対し配線長が指定されているか否
かを判定する（処理Ｓ １−３）。
照し、未処理の配線区間が有るか否かを判定する（処理
Ｓ １−１）。無ければ配線経路探索処理を終了し、有
れば、未処理の配線区間を一つ取り出しく処理Ｓ １−
２）、その配線区間に対し配線長が指定されているか否
かを判定する（処理Ｓ １−３）。
配線長の指定が無ければ、処理５１−７にて従来の迷路
法などを使用して、上記の取り出した配線区間に対しで
配線経路探索を行ない、配線経路を決定する。決定した
配線経路に関する情報はメモリ２に蓄積され、また表示
装置３に配線経路のイメージが表示される。そして、処
理５１−１に戻る。
法などを使用して、上記の取り出した配線区間に対しで
配線経路探索を行ない、配線経路を決定する。決定した
配線経路に関する情報はメモリ２に蓄積され、また表示
装置３に配線経路のイメージが表示される。そして、処
理５１−１に戻る。
他方、処理５１−３で配線長の指定があると判定された
場合、処理５１−４〜処理５１−６により、処理５１−
２で取り出された配線区間の配線経路を決定する。この
ときの動作−は、理解を容易にするために第３図の簡単
な例を用いて説明する。なお、第３図は、１２ Ｘ １
２の配線格子のうち、Ｘ印を付けた符号すの部分が配線
禁止格子となっている状態において、Δを付けた符号Ｃ
１，Ｃ２の２点を配線区間の結線すべき点とし、この配
線区間を１８格子長で配線する場合を示している。
場合、処理５１−４〜処理５１−６により、処理５１−
２で取り出された配線区間の配線経路を決定する。この
ときの動作−は、理解を容易にするために第３図の簡単
な例を用いて説明する。なお、第３図は、１２ Ｘ １
２の配線格子のうち、Ｘ印を付けた符号すの部分が配線
禁止格子となっている状態において、Δを付けた符号Ｃ
１，Ｃ２の２点を配線区間の結線すべき点とし、この配
線区間を１８格子長で配線する場合を示している。
先ず、処理Ｓ Ｌ−４では、配線区間の結線すべき２点
Ｃ１，Ｃ２各々から探索可能であり且つ結線すべき２点
ＣＩ、Ｃ２それぞれから独立に計算した最短の配線長の
和が指定の配線長に等しい点を全て求め、これらを経由
点の候補とする。第３図では、ｂの配線禁止格子と点Ｃ
Ｉ、Ｃ２を除く配線格子が空配線格子であるが、符号ｆ
の空配線格子は点Ｃ１，Ｃ２の何れからも配線不可能な
配線格子であり、従って残りの空配線格子が探索領域と
なる。そして、冬空配線格子までの点ｃｌ、ｃ２からの
最短の配線長の和ｄは第３図の配線格子中に付した値と
なり、指定された１８格子長となる点すなわち候補とな
る経由点は同図のハツチングを施した合計７個の点とな
る。
Ｃ１，Ｃ２各々から探索可能であり且つ結線すべき２点
ＣＩ、Ｃ２それぞれから独立に計算した最短の配線長の
和が指定の配線長に等しい点を全て求め、これらを経由
点の候補とする。第３図では、ｂの配線禁止格子と点Ｃ
Ｉ、Ｃ２を除く配線格子が空配線格子であるが、符号ｆ
の空配線格子は点Ｃ１，Ｃ２の何れからも配線不可能な
配線格子であり、従って残りの空配線格子が探索領域と
なる。そして、冬空配線格子までの点ｃｌ、ｃ２からの
最短の配線長の和ｄは第３図の配線格子中に付した値と
なり、指定された１８格子長となる点すなわち候補とな
る経由点は同図のハツチングを施した合計７個の点とな
る。
候補の経由点を全て求め終わると、それらはメモリ２に
一時的に格納され、処理３１−５−１を経て処理Ｓ １
−５−２へ進み、未処理の経路点が一つ取り出される。
一時的に格納され、処理３１−５−１を経て処理Ｓ １
−５−２へ進み、未処理の経路点が一つ取り出される。
そして、この取り出した経由点と配線区間の結線すべき
一方の点例えば点ｃ１とによって構成される配線区間に
対して例えば迷路法を使用した経路探索を行ない、探索
した配線経路をその経由点の候補配線経路としてメモリ
２に一時的に格納する（処理Ｓ １−５−３）。例えば
、第３図の符号ｅ１で示す経由点が処理された場合、符
号ｇ１で示す配線経路（配線長は５格子）が候補配線経
路として記憶される。
一方の点例えば点ｃ１とによって構成される配線区間に
対して例えば迷路法を使用した経路探索を行ない、探索
した配線経路をその経由点の候補配線経路としてメモリ
２に一時的に格納する（処理Ｓ １−５−３）。例えば
、第３図の符号ｅ１で示す経由点が処理された場合、符
号ｇ１で示す配線経路（配線長は５格子）が候補配線経
路として記憶される。
次に、配線区間の結線すべきもう一方の点ｃ２と経由点
によって構成される配線区間に対して迷路法などにより
経路探索を行ない、探索した配線経路をその経由点の候
補配線経路としてメモリ２に一時的に格納する（処理Ｓ
１−５−４）。このときの探索では、処理Ｓ １−５
−３で探索された候補配線経路上の配線格子を配線禁止
格子とした上で行なわれる。従って、第３図の符号ｅ１
で示す経由点が処理された場合、符号ｇ２で示す配線経
路（配線長は１３格子）が候補配線経路として見つかる
。しかし、例えば符号ｅ２の如き経由点については処理
Ｓ １−５−３で探索された配線経路が配線禁止格子と
なることによって処理Ｓ Ｌ−５−４の探索は失敗に終
わることになる。また、経由点ｅ１の場合は、処理Ｓ
Ｌ−５−４で探索された配線経路ｇ２の配線長は処理５
１−４で経路点を求めた際に計算した最短の長さに一致
するが、・符号ｅ３の如き経由点では、処理Ｓ Ｌ−５
−３で探索された候補配線経路の影響で処理Ｓ １−５
−４で探索される候補配線経路の長さは処理５１−４で
計算したときの長さより長くなる。
によって構成される配線区間に対して迷路法などにより
経路探索を行ない、探索した配線経路をその経由点の候
補配線経路としてメモリ２に一時的に格納する（処理Ｓ
１−５−４）。このときの探索では、処理Ｓ １−５
−３で探索された候補配線経路上の配線格子を配線禁止
格子とした上で行なわれる。従って、第３図の符号ｅ１
で示す経由点が処理された場合、符号ｇ２で示す配線経
路（配線長は１３格子）が候補配線経路として見つかる
。しかし、例えば符号ｅ２の如き経由点については処理
Ｓ １−５−３で探索された配線経路が配線禁止格子と
なることによって処理Ｓ Ｌ−５−４の探索は失敗に終
わることになる。また、経由点ｅ１の場合は、処理Ｓ
Ｌ−５−４で探索された配線経路ｇ２の配線長は処理５
１−４で経路点を求めた際に計算した最短の長さに一致
するが、・符号ｅ３の如き経由点では、処理Ｓ Ｌ−５
−３で探索された候補配線経路の影響で処理Ｓ １−５
−４で探索される候補配線経路の長さは処理５１−４で
計算したときの長さより長くなる。
さて、一つの経由点について処理Ｓ １−５−３． Ｓ
Ｌ−５−４により候補配線経路の探索処理を終了する
と、処理Ｓ １−５−１で未処理の経由点が有るか否か
を判定し、有れば上述した処理Ｓ Ｌ−５−２，Ｓ Ｌ
−５−３，３１−５−４を行ない、無ければ処理Ｓ Ｌ
−６を行なう。
Ｌ−５−４により候補配線経路の探索処理を終了する
と、処理Ｓ １−５−１で未処理の経由点が有るか否か
を判定し、有れば上述した処理Ｓ Ｌ−５−２，Ｓ Ｌ
−５−３，３１−５−４を行ない、無ければ処理Ｓ Ｌ
−６を行なう。
処理５１−６では、メモリ２に一時的に格納されたそれ
ぞれの経由率の候補配線経路の内から一つの経由点の候
補配線経路を選択し、これを処理５１−２で取り出した
配線区間に対する配線経路とする。コノとき、処理Ｓ
１−５−３と処理Ｓ １−５−４との双方で候補配線経
路が見つかった経由点について全体の配線長を各経由点
間で比較し、その配線長が最も短い配線経路を選択する
ことにより、指定長に等しい或いは一番近い長さの配線
経路を得るものであるｉ第３図の場合、符号ｇｌと符号
ｇ２とで示される配線経路を併せた経路（配線長は１８
格子）が点ｃｌ、ｃ２間の配線区間に対する配線経路と
して決定される。この決定された配線経路に関する情報
はメモリ２に蓄積され、また表示装置３に配線経路のイ
メージが表示される。そして、処理Ｓ Ｌ−１に戻って
上述した処理を未処理の配線区間が無くなるまで繰返す
。
ぞれの経由率の候補配線経路の内から一つの経由点の候
補配線経路を選択し、これを処理５１−２で取り出した
配線区間に対する配線経路とする。コノとき、処理Ｓ
１−５−３と処理Ｓ １−５−４との双方で候補配線経
路が見つかった経由点について全体の配線長を各経由点
間で比較し、その配線長が最も短い配線経路を選択する
ことにより、指定長に等しい或いは一番近い長さの配線
経路を得るものであるｉ第３図の場合、符号ｇｌと符号
ｇ２とで示される配線経路を併せた経路（配線長は１８
格子）が点ｃｌ、ｃ２間の配線区間に対する配線経路と
して決定される。この決定された配線経路に関する情報
はメモリ２に蓄積され、また表示装置３に配線経路のイ
メージが表示される。そして、処理Ｓ Ｌ−１に戻って
上述した処理を未処理の配線区間が無くなるまで繰返す
。
以上説明したように、本発明によれば、配線区間の配線
長がほぼ指定された配線長になるような配線経路を決定
することができ、配線遅延時間を問題とする配線設計を
効率良〈実施することができる効果がある。
長がほぼ指定された配線長になるような配線経路を決定
することができ、配線遅延時間を問題とする配線設計を
効率良〈実施することができる効果がある。
第１図は本発明の配線経路探索方式の一実施例を示す流
れ図、 第２図は本発明を実施する装置の一例を示すブロック図
および、 第３図は本発明の実施例における配線経路探索の様子を
示す図である。 図において、 ａ・・・配線格子 ｂ・・・配線禁止格子 ＣＩ、Ｃ２・・・配線区間の結線すべき点ｄ・・・結線
すべき２点ＣＩ、Ｃ２それぞれからの可能な最短の配線
長の和 ｅ１〜ｅ３・・・経由点 ｆ・・・結線すべき２点ｃｌ、ｃ２のいずれからも配線
不可能な点 ｇｌ、ｇ２・・・配線長が１８格子である配線経路本発
明を実施する装置の一クリを示すフ゛ロック図第２図
れ図、 第２図は本発明を実施する装置の一例を示すブロック図
および、 第３図は本発明の実施例における配線経路探索の様子を
示す図である。 図において、 ａ・・・配線格子 ｂ・・・配線禁止格子 ＣＩ、Ｃ２・・・配線区間の結線すべき点ｄ・・・結線
すべき２点ＣＩ、Ｃ２それぞれからの可能な最短の配線
長の和 ｅ１〜ｅ３・・・経由点 ｆ・・・結線すべき２点ｃｌ、ｃ２のいずれからも配線
不可能な点 ｇｌ、ｇ２・・・配線長が１８格子である配線経路本発
明を実施する装置の一クリを示すフ゛ロック図第２図
Claims (1)
- 【特許請求の範囲】 プリント配線板、セラミック配線板、集積回路等の配線
設計での結線すべき配線区間の配線経路を決定する配線
経路探索方式において、 結線すべき２点各々から探索可能であり且つ結線すべき
２点それぞれから独立に計算した最短の配線長の和が予
め指定された配線長に等しい点を配線経路が途中で経由
する経由点の候補として探索し、 該探索された一つ以上の経由点の候補それぞれについて
、結線すべき一方の点と経由点との間の最短の配線経路
を求めると共に、該求めた配線経路を配線禁止区域にし
て結線すべき他方の点と経由点との間の配線経路を求め
、該求めた二つの配線経路を併せた経路を配線経路の候
補とし、該配線経路の候補の中から一つの配線経路を選
択することを特徴とする配線経路探索方式。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP62264247A JPH01106264A (ja) | 1987-10-20 | 1987-10-20 | 配線経路探索方式 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP62264247A JPH01106264A (ja) | 1987-10-20 | 1987-10-20 | 配線経路探索方式 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH01106264A true JPH01106264A (ja) | 1989-04-24 |
Family
ID=17400527
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP62264247A Pending JPH01106264A (ja) | 1987-10-20 | 1987-10-20 | 配線経路探索方式 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH01106264A (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH04151772A (ja) * | 1990-10-16 | 1992-05-25 | Nec Corp | 対話自動配線方式 |
-
1987
- 1987-10-20 JP JP62264247A patent/JPH01106264A/ja active Pending
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH04151772A (ja) * | 1990-10-16 | 1992-05-25 | Nec Corp | 対話自動配線方式 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| DE69933422D1 (de) | System und Verfahren zur Routenführung mit einem Navigationsanwendungsprogram | |
| CN113711142B (zh) | 调试辅助装置、调试辅助方法、记录介质 | |
| JPH0456988A (ja) | 図中文字表示装置 | |
| JPH01106264A (ja) | 配線経路探索方式 | |
| JPS6089274A (ja) | ベクトルマスク制御システム | |
| JP2553200B2 (ja) | 情報処理装置 | |
| JP2001282574A (ja) | 処理時間情報を含む図式表現プログラムの表現方法 | |
| JPS62550B2 (ja) | ||
| JPS61120205A (ja) | 工程歩進処理方式 | |
| JPS63141131A (ja) | パイプライン制御方式 | |
| JPS6126692B2 (ja) | ||
| JPS60181837A (ja) | エクスキユ−ト命令処理方式 | |
| JPH0531193B2 (ja) | ||
| Hartsfield | The splitting number of the complete graph in the projective plane | |
| JP2560693B2 (ja) | デ−タフロ−型計算機のプログラムリンク方式 | |
| JPH04320577A (ja) | 概略経路決定処理方式 | |
| JPH05334399A (ja) | 回路配置修正システム | |
| JPH01134673A (ja) | ブロック図のデータ表示処理装置 | |
| JPH05265752A (ja) | 複数ジャンプ処理方法および装置 | |
| SU849218A1 (ru) | Устройство дл отладки программ | |
| JPS60114909A (ja) | 論理演算装置 | |
| JPH04291463A (ja) | データ変換装置 | |
| JP2007017332A (ja) | 車載情報端末 | |
| JPS63155740A (ja) | 配線処理方式 | |
| JPS6361330A (ja) | マイクロプログラム制御装置 |