JPH02190977A - 経路探索処理方法 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔概　要〕 計算機による配線経路の自動探索のための迷路法の処理
に関し、 迷路法による経路探索の配線率を向上するように改良し
た経路探索処理方法を目的とし、配線面を所定のセルに
等分割し、所要の該セル間を接続するように専用する該
セルからなる経路を迷路法によるラベル付けを行って探
索する処理において、新たに設定する該経路について、
一方の該セルから出発して他方の該セルに到達するまで
の、他の既設の該経路に無い該セルを経由するごとにラ
ベル値を１づつ増加させ、該既設の経路にある該セルを
経由する場合に、該新設定する経路が該既設の経路を横
切った場合には前記ラベル値に所定の第１の割増値を加
算したラベル値とし、横切らない場合に所定の第２の割
増値を加算した。

ラベル値とし、該他方のセルに到達するときの該ラベル
値が最小の経路を該新設定の経路とし、すべての所要の
該接続について該経路を決定する処理を、所定の経路設
定状態になるまで、第１及び第２の割増値を順次増加し
て繰り返すように構成する。

〔産業上の利用分野〕

本発明は、計算機による配線経路の自動探索のための迷
路法を改良した、経路探索処理方法に関する。

プリント基板等に実装された部品の端子間を接続するプ
リント配線のための経路を決定するための、配線経路の
自動探索は知られているが、実装の高密度化に伴って自
動配線率が低下し、人手による設計工数を増加させる傾
向にあるので、自動配線率の向上が望まれている。

〔従来の技術と発明が解決しようとする課題〕第５図は
迷路法による経路探索におけるラベル付けを説明する図
である。図は配線面を示し、破線で区切られた等大の各
枡をセルとし、所要の２端子のセル間の接続（以下にお
いてネットという）を行うために、両者間に並ぶセルか
らなる経路を探索するものとし、例えば一端のセルＳを
出発点として、隣接するセルにラベル値「ｌ」（図にラ
ベル値を■等で示す）を付し、次に■に隣接するセルに
はラベル値を１増加して■とし、図示のようにラベル付
けを進めて、目標のセルに最小のラベル値で到達する経
路を求める経路とする。なおこの場合に、複数の可能な
経路の何れを採るかは、例えば探索の進行方向で上下左
右の優先順位をどのように定めておくかによって決まる
。

以上のラベル付げにおいて、他の既に選ばれた経路上の
セル（以下において既配線のセルという）及び端子のセ
ルは、配線経路とすることのできない障害物として、ラ
ベル付けから除いてそれらのセルを避けることにより、
可能な場合にはそれらを迂回する経路を得るようにする
。

その結果、例えば第４図（ａ）のような配置の各端子ａ
−ａ’間、ｂ−ｂ’間、ｃ　−ｃ’間をそれぞれ接続す
る経路の探索を迷路法で行うと、端子対の処理順序によ
り結果は異なるものの、例えばｃ　−ｃ’間の経路を先
に決定すると、ａ−ａ’間及びｂ−ｂ″間は配線不可能
になるというようにして、何れにしても前記の方法によ
っては、３端子対すべての配線を完了することができな
い。このために迷路法では、配線の錯綜化と共に自動配
線率が甚だしく低下し、人手による配線設計に依存する
割合が増加するという問題がある。

本発明は、迷路法による経路探索の配線率を向上するよ
うに改良した経路探索処理方法を目的とする。

〔課題を解決するための手段〕

第１図は、本発明の構成を示す処理の流れ図である０図
は配線の経路探索における処理の流れを示し、１〜７は
処理ステップである。

〔作　用〕

配線面を所定のセルに等分割し、所要の該セル間を接続
するように専用する該セルからなる経路を迷路法による
ラベル付けを行って探索する処理のために、処理ステッ
プ１で所要の初期設定を行うと、処理ステップ２で１ネ
ツトを取り出す。

そのネットについて新たに経路を設定するために、処理
ステップ３により、一方の端子のセルから出発して他方
の端子のセルに到達するまでの、他の既設の経路に無い
セルを経由するごとにラベル値を１づつ増加させる。

又、既設の経路にあるセルを経由する場合に、新設定す
る経路が該既設の経路を横切った場合には前記ラベル値
に所定の第１の割増値を加算したラベル値とし、横切ら
ない場合に所定の第２の割増値を加算したラベル値とし
、このようにして他方の端子のセルに最小のラベル値で
到達する経路を新設定の経路とするように処理する。

処理ステップ３による１ネツトの経路探索を、処理ステ
ップ５で識別してすべてのネットについて実行するごと
に、処理ステップ７で前記第１及び第２の割増値を所定
値増加させて、以上の処理を繰り返し、処理ステップ４
で全ネットの配線が完了したことを検出するか、又は処
理ステップ６で所定の終了条件を検出することにより処
理を終了する。

以上の処理方法により、既配線セルと接触又は交差する
場合にも割増値によってコストの大きい経路として設定
する処理を繰り返すことにより、繰り返し処理の間にネ
ット間で相互に影響して、互いにコストの小さい迂回経
路をとるように経路を遷移させるので、実際に可能な経
路を見出すことが可能になり、配線率を向上する。

〔実施例〕

第２図は本発明の実施例における処理の流れを示す図で
ある。

処理ステップ１０において、配線面、接続するセルを指
定するネットリスト等のデータを入力し、第１及び第２
の割増値（以下において割増値ａ及びｂとする）に所定
の初期値を与える。

処理ステップ１１でネットの１つを取り上げて経路探索
処理を開始し、ネットの一方の端子のセルを最初の親セ
ルとして、処理ステップ１２で親セルに隣接する１セル
を定め、処理ステップ１３でそれがネットの他方の端子
の目標セルか識別する。

目標セルでなければ、処理ステップ１４で現在の親セル
のラベル値（初期値を０とする）に＋１したラベル値を
、当セルの仮ラベル値とする。

処理ステップ１５でそのセルが、既配線のセル（但し、
親セルも同じ配線についての既配線セルである場合を除
く）か識別し、既配線のセルであれば処理ステップ１６
で、そのセルを現処理中の配線から見て既配線を越えた
後と越える前の部分に分け、前者の仮ラベル値を前記仮
うベル値十ａ、後者の仮ラベル値を前記仮うベル値十す
とする。

処理ステップ１７で、仮ラベル値をそのセルについて既
に記憶されているラベル値（初期値は適当に大きな値を
設定しておく）と比較し、小さい方のラベル値及びその
親方向（ａセルの方向）をそのセルのラベルとして記憶
する。なお、処理ステップ１５で既配線セルで無かった
場合等は直ちに処理ステップ１７に進む。

以上で１隣接セルのラベル付は処理を終わるので、処理
ステップ１８で別の方向の未処理の隣接セルがあるか識
別し、未処理があれば処理ステップ１２に戻って別の隣
接セルについて前記と同様に処理する。

隣接セルを全て処理した場合は、処理ステップ１９で現
在の親セルのラベル値について、未処理のセルがあるか
識別し、未処理があれば次の親セルを定めて処理ステッ
プ１２に戻り、前記のように新しい親セルについて隣接
セルのラベル付は処理を実行する。

このようにして、あるラベル値の全セルについて、各セ
ルを親セルとする処理を終わると、処理ステップ２０で
親セルにするラベル値を次に大きな値に設定し、その他
の制御情報を再設定して、処理ステップ１２に戻り前記
のように処理を行う。

第３図はａ＝５０．ｂ＝５として、Ｓで示すネットの一
端から以上のようなラベル付けを進めた場合のラベルの
一例を示す図であり、各セルの円内にラベル値を示し、
矢印で親方向を示す。

このようにして処理を進めた結果、−処理ステップ１３
において、目標セルに到達したことを識別すると、その
ネットについて経路が設定されたので、処理ステップ２
１に分岐し、配線完了か、即ちすべてのネットについて
、他のネットとの交差及び接触の無い経路が得られたか
判定し、配線完了であれば経路探索処理を終了する。

配線完了でなければ、処理ステップ２２において全ネッ
トを処理したか識別し、未処理ネットがあれば処理ステ
ップ１１に戻って、次に処理するネットを取り上げ前記
のように処理を始める。

このようにして、全ネットを−通り処理し終わった場合
には、処理ステップ２３に進んで、例えば今回の処理に
よっても全ネットの経路が、その前の処理結果の経路か
ら全く変化しないことを検出し、これを終了条件として
処理を終了する。

前記終了条件になっていない場合には、処理ステップ２
４で割増値ａ及びｂを所定値だけ増加して処理ステップ
１１に戻り、新しいａ、ｂの値による全ネットの処理を
再開する。

以上のようにして、例えばａ＝ｂ＝ｏの初期値で処理を
開始すると、最初は各ネットについて、互いに他のネッ
トを無視した場合の最短経路による経路が決定する。第
４図（ｂ）は（ａ）で示すネットの経路について、その
ようにして設定される結果の一例である。

次に第４図（ｂ）の状態で、例えばａ＝５０．ｂ＝５と
して経路探索を行うと、（Ｃ）のようにａ　−ａ’の経
路がｂ−ｂ’に設定された経路を避けるように選ばれ、
Ｃ−Ｃ”は他の経路と交差しないようになるが、なおａ
−ａ”及びｂ−ｂ’と接触している。

次に例えばａ　＝１００　、　ｂ　＝ｌＯに増加して再
び処理を行うと、第４図回のようにａ−ａ″及びｂ　−
ｂ’の経路がｃ−ｃ’との接触を避けるように選ばれて
、この例ではこの段階で配線を完了する。即ち従来の迷
路法では配線不能となる場合にも配線を完了することが
できる。

〔発明の効果〕

以上の説明から明らかなように本発明によれば、計算機
による配線経路の自動探索のための迷路法の処理におい
て、自動配線率が向上するという著しい工業的効果があ
る。

【図面の簡単な説明】 第１図は本発明の構成を示す処理の流れ図、第２図は本
発明の実施例の処理の流れ図、第３図は本発明のラベル
付けの説明図、第４図は配線例の説明図、 第５図は迷路法のラベル付けの説明図 である。 図において、 １〜７．１０〜２４は処理ステップ 本発明の構成を示す処理の流れ図 第１図 迷路法のラベル付けの説明図 第５図 本発明の実施例の処理の流れ図 第２図

Claims (1)

1. 【特許請求の範囲】 配線面を所定のセルに等分割し、所要の該セル間を接続
   するように専用する該セルからなる経路を迷路法による
   ラベル付けを行って探索する処理において（１〜７）、 新たに設定する該経路について、一方の該セルから出発
   して他方の該セルに到達するまでの、他の既設の該経路
   に無い該セルを経由するごとにラベル値を１づつ増加さ
   せ、 該既設の経路にある該セルを経由する場合に、該新設定
   する経路が該既設の経路を横切った場合には前記ラベル
   値に所定の第１の割増値を加算したラベル値とし、横切
   らない場合に所定の第２の割増値を加算したラベル値と
   し、 該他方のセルに到達するときの該ラベル値が最小の経路
   を該新設定の経路とし（３）、 すべての所要の該接続について該経路を決定する処理を
   、所定の経路設定状態になるまで、第１及び第２の割増
   値を順次増加して繰り返す（４〜７）ことを特徴とする
   経路探索処理方法。