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

Description

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

〔産業上の利用分野〕

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

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

〔従来の技術と発明が解決しようとする課題〕

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

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

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

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

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

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

〔作用〕

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

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

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

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

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

〔実施例〕

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

〔発明の効果〕

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

【図面の簡単な説明】

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

───────────────────────────────────────────────────── フロントページの続き (72)発明者 澁谷 利行 神奈川県川崎市中原区上小田中1015番地 富士通株式会社内 (72)発明者 三渡 秀樹 神奈川県川崎市中原区上小田中1015番地 富士通株式会社内 (56)参考文献 特開 昭61−208238（ＪＰ，Ａ)

Claims (1)

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