JPH0743737B2 - 配線経路決定方法 - Google Patents

Description

【発明の詳細な説明】 〈産業上の利用分野〉 本発明は、CAD等を使用して自動的に最適配線経路を決
定する場合に有効な配線経路決定方法に関する。

〈従来の技術〉 高密度集積回路やプリント配線基板等の回路設計におい
ては、集積密度を高めるために、多点間を結線する配線
距離をできるだけ短くすることが要求される。

従来の配線経路の決定方法として、迷路法や線分探索法
等が知られている。たとえば、迷路法では、配線可能領
域を格子状に分割し、各格子に一定の重みを与えて重み
値が最小となる最適の配線経路を決定する。

〈発明が解決しようとする課題〉 ところが、従来の決定方法では、次の問題がある。たと
えば、第７図において、符号Ｗ、Ｘ、Ｙ、Ｚで示す各配
線禁止領域が予め設定され、かつ、符号CC′およびBB′
で示す各点を結ぶ配線経路が既に実線のごとく決定され
ているものとする。この状態で、次に、符号AA′で示す
両点を結線するには、同図の破線で示す経路によって結
線せざるを得ない。すなわち、従来のアルゴリズムで
は、配線可能領域を一定単位幅で縦横に予め分割し、配
線禁止領域間に挟まれたところ（この例ではＷ−Ｘ間）
を複数の配線経路が通る場合には、配線経路を順次一単
位幅ずつずらせて配列する。このため、既にCC′、BB′
の配線経路が存在する間にAA′の配線経路を割り込むか
たちでの解を得ることができない。したがって、破線で
示すような迂回路とならざるを得なくなる。そのため、
従来の多点間の配線経路の決定方法では、全体の配線長
を短くするのに自ら限界があった。

本発明は、このような事情に鑑みてなされたものであっ
て、従来よりも配線経路の決定に柔軟性をもたせ、多点
間配線において全体としての配線距離を可及的に短くな
るように決定できるようにすることを目的とする。

〈課題を解決するための手段〉 本発明は、上記の目的を達成するために、次の構成を採
る。

すなわち、本発明の配線経路決定方法では、まず、配線
禁止領域間に存在する配線可能領域を前記配線禁止領域
の境界線と見なして、配線禁止領域と前記境界線とから
なる座標系を構成する。

次に、結線すべき始点から終点までの間で、境界線上に
存在する分岐点の内から接続可能な分岐点を順次候補点
として選出し、始点から選出した各候補点に至るまでの
距離を積算し、かつ、既設の配線経路との交差を調べて
既設線路と交差する場合には前記積算値に予め設定した
交差の重みを付加しつつ、重み付けされた積算値の最小
値を与える経路を検索する。そして、終点に到達した時
点の積算値の最小値を与える経路を配線経路として決定
するようにしている。

〈作用〉 上記構成によれば、従来のように配線可能領域を予め一
定単位幅で分割して配線経路を決定するのではなくて、
配線禁止領域間に存在する配線可能領域を配線禁止領域
の境界線と見なして配線禁止領域と境界線のみからなる
座標系を構成し、この座標系上で配線経路を決定するの
で、配線禁止領域間に挟まれた間を複数の配線経路が通
る場合でも、既設の配線経路が存在する間に割り込むか
たちで新たな配線経路を解として得ることができる。

しかも、境界線上の分岐点の内から候補点を選出して始
点から候補点まで距離を積算しつつ既設の配線経路との
交差を調べ、既設線路と交差する場合には積算値に所定
の交差の重みを付加するようにしているので、回路設計
の許容度に応じて交差の重み付け値を適宜調整すること
で、配線経路の交差を避けて迂回させるか、スルーホー
ルによるものとするかの選択を自由に行える。

このため、多点間を結線する上で常に最適の配線経路を
決定することができる。

〈実施例〉 第１図は基板上に設けられる配線禁止領域と各接続点間
を結線される配線経路との関係を示す平面図である。本
発明の配線経路決定方法の説明上、この実施例では、符
号Ｗ、Ｘ、Ｙ、Ｚで示す各配線禁止領域が予め設定さ
れ、かつ、符号CC′およびBB′で示す各点を結ぶ配線経
路が既に実線のごとく決定されているものとする。

この状態で、符号AA′で示す両点を新たに結線するに
は、まず、第２図に示すように、配線禁止領域Ｗ〜Ｚ間
に存在する配線可能領域Ｖを配線禁止領域Ｗ〜Ｚの境界
線Ｌと見なして、配線禁止領域Ｗ〜Ｚと境界線Ｌのみか
らなる座標系を構成する。したがって、境界線Ｌ上に
は、配線禁止領域Ｗ〜Ｚの存在により符号〜までの
各分岐点が存在することになる。

次に、この座標系を利用してAA′の両接続点間を最短距
離で結線するための検索手順を第３図に示すフローチャ
ートを参照して説明する。なお、以下の説明において、
「データファイル」とは、始点Ａからあらゆる方向に配
線経路を検索する途中で、境界線上に存在する分岐点の
内から接続可能なものとして順次選出される候補点の座
標並びに始点から候補点に至る距離の積算値を含むデー
タが登録されたものを意味する。

まず、Ａ点を始点、Ａ′点を終点とみなして、両点Ａ、
Ａ′の座標をデータファイルに登録し（ステップs1）、
また、始点Ａの距離の積算値として“0"を与えてこれら
を初期値とする（ステップs2）。次に、データファイル
から始点Ａからの距離の積算値が最小の経路を取り出し
（ステップs3）、この経路の先端座標（最初は始点Ａに
一致する）が終点Ａ′の座標と一致しているか否かを判
別する（ステップs4）。最初は不一致であるから、続い
て、始点Ａから接続可能な分岐点（本例ではと）を
候補点として選出し、また、その候補点の数ｎ（＝２）
を調べてデータファイルに登録する（ステップs5）。そ
して、始点Ａから一つの候補点たとえばまでの積算値
（本例ではＡ−間の積算値は“4"）を求める（ステッ
プs8）。また、このステップ８では、既設の配線経路と
の交差を調べ、既設線路と交差する場合には上記の積算
値に予め設定した交差の重みを付加する。本例では既設
線路との交差はないから、上記の積算値“4"をデータフ
ァイルに登録した後、候補点数ｎを一つ減らし（ステッ
プs9）、ステップs6に戻る。候補点数ｎが０でなけれ
ば、まだ候補点が残っているので、引き続いて始点Ａか
ら他の候補点までの積算値（本例ではＡ−間の積算
値は“2"）を求め（ステップs8）、この積算値“2"をフ
ァイルに登録した後、候補点数ｎを一つ減らし（ステッ
プs9）、ステップs6に戻る。この状態において、データ
ファイルに登録された経路と積算値の各データは、第４
図（ａ）に示すようになる。

この状態で候補点数ｎが０となるから、ステップs3に戻
り、データファイルから重みが最小の経路を取り出す。
ここでは、Ａ−の経路の積算値が最小であるから、こ
の経路のデータが取り出される。続いて、このＡ−の
経路の先端座標（分岐点の座標）が終点Ａ′の座標と
一致しているか否かを判別する（ステップs4）。この段
階では不一致となるから、続いて、分岐点から接続可
能な次の候補点（本例ではよ）およびその候補点の
数ｎ（＝２）をデータファイルに登録する（ステップs
5）。次に、始点Ａから分岐点を経由して選出した一
つの候補点たとえばに至る距離の積算値（本例ではＡ
−−の経路の積算値は“10"）を求め、この積算値
“10"をデータファイルに登録した後、候補点数ｎを一
つ減らし（ステップs9）、ステップs6に戻る。候補点数
ｎが０でなければ、まだ候補点が残っているので、引き
続いて始点Ａから分岐点を経由して他の候補点に至
る距離の積算値（Ａ−−の経路の積算値は“9"）を
求め（ステップs8）、この積算値“9"をファイルに登録
した後、候補点数ｎを一つ減らし（ステップs9）、ステ
ップs6に戻る。この状態において、データファイルに登
録された経路と積算値の各データは、第４図（ｂ）に示
すようになる。

この状態では候補点数ｎが０となるから、ステップs3に
戻り、データファイルから積算値が最小の経路を取り出
す。ここでは、Ａ−の経路の積算値が最小であるか
ら、Ａ−の経路のデータが取り出される。続いて、こ
のＡ−経路の先端座標（分岐点の座標）が終点Ａ′
の座標と一致しているか否かを判別する（ステップs
4）。この段階では不一致となるから、続いて、分岐点
から接続可能な次の候補点（本例ではのみ）および
その候補点の数ｎ（＝１）をデータファイルに登録する
（ステップs5）。そして、始点Ａから分岐点を経由し
て候補点に至る距離の積算値（Ａ−−の経路の積
算値は“20"）をデータファイルに登録した後、候補点
数ｎを一つ減らし（ステップs9）、ステップs6に戻る。
この状態において、データファイルに登録された経路と
重みの各データは、第４図（ｃ）に示すようになる。

引き続いて、ステップs3に戻り、データファイルから重
みが最小の経路を取り出す。ここでは、Ａ−−の経
路の重みを最小となるから、このＡ−−経路のデー
タが取り出される。

このようにして、上記のステップs3〜ステップs9までを
繰り返して、積算値の最小値を与える経路を検索し、検
索した経路の先端座標が終点と一致したときに、その時
点で積算値の最小値を与える経路を配線経路として決定
する（ステップs10）。

ステップs8における既設線路との交差の有無は、次のよ
うにして判断する。

各分岐点〜に対して、予め８方向に接続情報を与え
ておく。たとえば、分岐点、については、第５図
（ａ）、（ｂ）にそれぞれ示すように、各分岐点、
を中心として接続される他の分岐点の情報を付加する。
そして、第２図において、既設の配線経路がＢ−−
−Ｂ′であり、新たに配線する経路がＡ−−−−
Ａ′である場合には、既設の線路に対して新たに配線す
る線路が重複する部分の合流点と分岐点とを調べる。す
なわち、第６図に示すように、Ｂ〜Ｂ′の線路に対して
Ａ〜Ａ′の線路の合流点はであり、分岐点はであ
る。そして、合流点において、Ｂ−線路を中心に見
た場合に−線路は右側に位置する。一方、分岐点
において、−Ｂ′線路を中心に見た場合に−Ａ′線
路は右側に位置する。すなわち、同一側にあるから両線
路は交差しないことが分かる。ちなみに、新たな配線経
路の一部が−−−線路として存在する場合に
は、分岐点において−Ｂ′線路を中心に見て−
線路は左側に位置するから合流点と分岐点で存在側
が異なるので、両線路が交差することが分かる。

既設線路との交差を回避したい場合には、ステップs8に
おいて、交差の重みを大きく設定すれば積算値も大きく
なるので、ステップs3における配線経路の候補から外
れ、交差しない別の経路が検索されることになる。した
がって、交差の重み付け値を回路設計の許容度に応じて
適宜調整することで、交差を避けて配線経路を迂回させ
るか、スルーホールを採用するかの選択を自由に行うこ
とができる。

〈発明の効果〉 本発明によれば、従来のような配線経路の決定の際の制
限が緩和され、配線禁止領域間に挟まれた間に既設の配
線経路が存在する場合でも、両配線経路の間に割り込む
かたちで新たな配線経路を決定することができる。この
ため、全体としての配線距離を可及的に短くできる。し
かも、回路設計の許容度に応じて交差の重み付け値を適
宜設定することで、配線経路の交差を避けて迂回させる
か、スルーホールによるものとするかの調整が自由に行
える。したがって、多点間を結線する上で、常に最適の
配線経路を決定することが可能となる。

【図面の簡単な説明】

第１図ないし第６図は本発明の実施例をそれぞれ示すも
ので、第１図は基板上に設けられる配線禁止領域と各接
続点間を結線される配線経路との関係を示す平面図、第
２図は配線経路決定の際に構成される座標系の説明図、
第３図は配線経路検索手順のフローチャート、第４図は
配線経路の探索途中データの内容を示す説明図、第５図
は座標系の各分岐点に設定される分岐情報の説明図、第
６図は既設配線経路との交差の有無の判別手法の説明図
である。 また、第７図は従来の配線経路決定方法を説明するため
の基板上に設けられる配線禁止領域と各接続点間を結線
される配線経路との関係を示す平面図である。 Ｗ〜Ｚ…配線禁止領域、Ｖ…配線可能領域、Ｌ…境界
線、〜…分岐点、Ａ…始点、Ａ′…終点。

Claims (1)

【特許請求の範囲】
1. 【請求項１】配線禁止領域間に存在する配線可能領域を
   前記配線禁止領域の境界線と見なして、配線禁止領域と
   前記境界線とからなる座標系を構成し、 次に、結線すべき始点から終点までの間で、境界線上に
   存在する分岐点の内から接続可能な分岐点を順次候補点
   として選出し、始点から選出した各候補点に至るまでの
   距離を積算し、かつ、既設の配線経路との交差を調べて
   既設線路と交差する場合には前記積算値に予め設定した
   交差の重みを付加しつつ、重み付けされた積算値の最小
   値を与える経路を検索し、 終点に到達した時点の積算値の最小値を与える経路を配
   線経路として決定することを特徴とする配線経路決定方
   法。