JPH0426148B2 - - Google Patents

Description

【発明の詳細な説明】 (A) 発明の技術分野 本発明は、配線ルート最適化決定処理方法、特
に、プリント板上の両面に形成される配線格子に
沿つて配線ルートを決定する処理に当たつて、一
旦仮決定された配線ルートを更に非所望な位置に
もうけられるビア（ViA−スルー・ホール）を削
除した上で、先にルートが見出せずに決定できな
かつた配線ルートを決定できるようにした配線ル
ート最適化決定処理方法に関するものである。

(B) 技術の背景と問題点 従来からプリント板上にもうける配線ルートを
決定するに当たつて、第６図図示の如き形で、配
線ルート探索処理部を利用し、配線ルートを決定
することが行われている。なお第６図において、
１は配線ルート探索処理部、２は配線結果格納メ
モリ、３は配線処理情報入力部を表している。即
ち、配線処理情報入力部３から所望の情報を入力
し、配線ルート探索処理部１によつて配線ルート
を決定してゆき、得られた配線ルートは配線結果
格納メモリ２に格納される。

この状況について、第５図を参照しつつ説明す
る。図において、４はプリント板、５はプリント
板４の表裏両面に形成される配線格子であつて決
定されるべき配線ルートが当該配線格子に沿うよ
うにして決定されるもの、５−１は格子点、６は
ICピン、７はプリント板上に形成されるビア、
８はプリント板の例えば表面側に形成された配線
ルート、９はプリント板の裏面側に形成された配
線ルートを表している。

第６図図示の配線ルート探索処理部１における
処理については第２図を参照しつつ後述される
が、例えば第５図図示のICピン６ＡからICピン
６Ｂに至る配線ルートを決定するに当たつて、例
えばプリント板の表面側においては図示Ｘ軸方向
にのみ（１格子分のＹ軸方向の延びについては許
容している）延びる配線ルート８を与え、プリン
ト板の裏面側においては図示Ｙ軸方向にのみ（１
格子分のＸ軸方向に延びについては許容してい
る）伸びる配線ルート９を与えるようにし、両者
配線ルート８と９との結合に当たつてはプリント
板４上にビア７をもうけて結合するようにしてい
る。勿論、上記ICピン６Ａと６Ｂとの間の配線
ルートの決定に当たつてはプリント板４の例えば
表面のみを利用してＸ軸方向とＹ軸方向との両方
に延びるルートにて決定してもよいが、この決定
を許すと、第５図図示ICピン６Ｃと６Ｄとの間
の配線ルート８と非所望に交差してしまうことが
ある。このために、Ｘ軸方向に延びる配線ルート
８とＹ軸方向に延びる配線ルート９とをビア７に
よつて結合するようにし、上記交差をさけるよう
にしている。

第６図図示の配線ルート探索処理部１は第５図
を参照して説明した如く配線ルートを決定してゆ
くが、第５図図示のICピン６Ｅと６Ｃとの間を
結ぶ配線ルート８と９との場合のように、他のＸ
軸方向に延びる配線ルートによつて交差されるこ
とがないような場合には、わざわざビア７をもう
けてプリント板の表・裏両面を利用しなければな
らない理由がない。

(C) 発明の目的と構成 本発明は、上記の点を解決することを目的とし
ており、第５図図示の如く一旦決定された配線ル
ートについて今一度再検討を加え、非所望に存在
するビアを省略しかつこれによつてそれまでルー
ト決定し得なかつた配線ルートを新しく決定でき
れば決定しようとすることを目的としている。そ
してそのため、本発明の配線ルート最適化決定処
理方法は、プリント板の一方の面に形成される配
線格子における格子点に対応して当該格子点に関
連する配線パターン情報をもつと共に上記プリン
ト板の他方の面に形成される配線格子における格
子点に対応して当該格子点に関連する配線パター
ン情報をもつ記憶装置をそなえ、上記格子点の少
なくとも１つをスタート点としかつ上記格子点の
少なくとも他の１つをエンド点とする配線ルート
を決定する配線ルート探索処理部を用いて上記配
線格子を通る配線ルートを決定してゆく配線ルー
ト処理システムにおいて、 上記配線ルート探索処理部が上記プリント板上
の１つの面に関して実質上一次元探索を行う一次
元探索条件状態モードと上記プリント板上の１つ
の面に関して二次元探索を行う二次元探索条件状
態モードとを選択することができるよう構成され
ると共に、 上記配線ルート探索処理部を上記一次元探索条
件状態モードに設定した上で得られた配線ルート
についての上記配線パターン情報が格納されてい
る記憶装置と、 当該記憶装置上で得られている１つの配線ルー
トを処理対象として当該処理対象の配線ルートを
仮消去した上で当該処理対象の配線ルートについ
てのスタート点とエンド点とを与える配線ルート
削除処理部と、 上記配線ルート探索処理部が、上記二次元探索
条件状態モードの下で、上記配線ルート削除処理
部による仮消去が行われた結果を用いて探索処理
を行つた、その処理結果の配線パターン情報が格
納される配線結果メモリとがもうけられてなり、 上記配線ルート探索処理部は、上記一次元探索
条件状態モードの下で処理を実行して、上記一次
元探索条件状態モードに設定した上で得られた配
線ルートについての上記配線パターン情報が格納
される記憶装置に当該情報を格納し、次いで、上
記二次元探索条件状態モードの下で、上記配線ル
ート削除処理部による処理を実行せしめ、当該配
線ルート削除処理部による仮消去が行われた結果
を用いて探索処理を行つて、その処理結果の配線
パターン情報を上記配線結果メモリに格納するよ
うにした ことを特徴としている。以下、図面を参照しつつ
説明する。

(D) 発明の実施例 第１図は本発明の方法を実行する一実施例構
成、第２図は第１図に示す配線ルート探索処理部
における処理を説明する説明図、第３図および第
４図は同じく配線ルート探索処理部における処理
を具体的に表すフローチヤートを示している。ま
た第５図は本発明の前提問題を説明する説明図、
第６図は従来の方法を説明する説明図を示してい
る。

第１図において、図中の符号１，２は第６図に
対応し、１０は仮配線処理メモリであつて例えば
第６図図示の如き処理を実行することによつて第
６図図示の配線結果格納メモリ２に得られた情報
が格子点情報として格納されているもの、１１は
配線ルート削除処理部を表している。なお図示の
配線ルート探索処理部１は、第５図および第６図
を参照して説明した如く、プリント板の例えば表
面でＸ軸方向に延びる配線ルートを、また裏面で
Ｙ軸方向に延びる配線ルートを決定する所の一次
元探索条件状態での探索機能をもつと共に、プリ
ント板の表面のみあるいは裏面のみでＸ軸方向と
Ｙ軸方向とのいずれの方向にも延びることのでき
る二次元探索条件状態での探索機能をもつてい
る。そしてモード切り替えによつて切り替え得る
ようになつていると考えてよい。

以下本発明を説明するに先立つて、図示配線ル
ート探索処理部１における処理について説明して
おく。

第５図図示の格子点５−１，５−１…に対応し
て第２図Ａ図示の如く「格子点情報」がメモリ上
に格納されている。なお第２図Ａ図示のメモリは
第１図図示の仮配線処理メモリ１０と同じもので
あると考えてよい。一般に座標（xi、yi）をもつ
格子点に対応する格子点情報としては次のような
ものが記述されていると考えてよい。

即ち、情報の種類として、 (a) 後述する如く配線ルート探索のために番号付
けを波及せしめてゆくことが許されるか否かを
指示する「番号付可能格子」情報、 (b) 配線ルート探索のためのスタート点あるいは
エンド点（ICピンの位置など）であることを
指示する「ルート探索スタート又はエンド格子
点」情報、 (c) 配線ルートを通すことが禁止されることを指
示する「障害物格子点」情報 が用意され、夫々の情報のデータとして、 (d) 上記(a)の情報に対応して、空き状態にあるこ
とを示すデータか又は波及されてきた番号が記
述され、 (e) 上記(b)の情報に対応して、スタート点Ｓであ
るか、スタート点の隣点SNであるか、エンド
点Ｅであるか、エンド点の隣点ENであるかが
記述され、 (f) 上記(c)の情報に対応して、障害物の多重度が
記述され、 ている。更に当該格子点がビアを形成することに
ついて禁止されているか否かそして禁止されてい
ればその多重度が与えられている。

今第１図図示の配線ルート探索処理部１が上述
の二次元探索を許しているモードにあるものとす
ると、配線ルートの探索は第２図Ｂおよび第２図
Ｃに示す如く行われる。

最初に第２図Ｂ図示の如く、配線ルートのスタ
ート点Ｓが図示の如く座標（０、０）であり、エ
ンド点Ｅが座標（７、０）であり、障害物格子点
が座標（４、０）にあるなどの情報が、第２図Ａ
図示のメモリ１０上に格納される（又は格納され
ている）。あわせて、座標（１、０）、（０、１）、
（−１、０）、（０、−１）がスタート点の隣点SN
であることや、座標（８、０）、（７、１）、（６、
０）、（７、−１）がエンド点の隣点ENであるこ
とが格納される。

この状態の下で、メモリａ１２上に上記格子点
SNに関する格子点情報を集める。そして、１つ
の格子点SN（例えば座標（１、０））に着目し、
当該格子点に隣接する二次元方向（但し１つの方
向は波及源方向であるので省略）について座標
（２、０）、（１、１）、（１、−１）に該当する格子
点の格子点情報をメモリｂ１３上に集めると共に
当該格子点の「番号付可能格子」情報に対して番
号「１」を与える。また同様に格子点SN（座標
（０、１））に着目し、座標（１、１）、（０、２）、
（−１、１）に該当する格子点についての格子点
情報をメモリｂ１３上に集めると共に番号「１」
を与える。以下同様にして、格子点SNの隣に番
号「１」が波及し終わつたら、次にメモリｂ１３
の内容をメモリａ１２に転送し、番号「１」が波
及している格子点の隣をメモリｂ１３上に集める
ことによつて番号「２」を与えるようにする。即
ち、第２図Ｂ図示の如く、番号「１」、「２」、
「３」…を順次波及せしめてゆく。このとき、座
標（４、０）の場合のように障害物格子点が存在
すると、それをさけるようにして波及を行つてゆ
く。このような波及を行つてゆく間に第２図Ｂ図
示の如く格子点ENに達するとそこまでで波及処
理を停止する。上記第２図Ｂを参照して説明した
説明においてはプリント板４の表面についての波
及のみを考慮しているが、実際には各格子点にビ
アをもうけることが許容されていれば当該格子点
から裏面に波及を行つてゆくようにされる。

上述の如く波及が行われてゆきエンド点に達す
ると、今度は配線ルート決定が上記波及ルートを
逆にたどることによつて行われる。即ち、第２図
Ｂ図示の場合では例えば図示矢印Ｒの如く逆にた
どつてスタート点Ｓに達し、配線ルートを当該矢
印Ｒに沿うように決定し、当該ルートが通る各格
子点に対応する格子点情報中に当該ルート上にあ
ることを指示する。

第３図は上記波及に対応するフローチヤートを
示し、第４図は上記波及ルートを逆にたどる処理
に対応するフローチヤートを示している。図中の
「メモリｃ」は第２図Ａ図示のメモリ１０を示し、
「メモリａ」は第２図Ｃ図示のメモリ１２を示し、
「メモリｂ」は第２図Ｃ図示のメモリ１３を示し
ている。また「Ｘ層である」とはプリント板４の
１つの面を示し、「Ｘ層でない」とはプリント板
４の他の面を示している。更に図中「Ｘ＋１」と
は注目している格子点のＸ座標値「Ｘ」に対して
１つの右の格子点、「Ｘ−１」とは同じくＸ座標
値「Ｘ」に対して１つ左の格子点、「Ｙ＋１」と
は注目している格子点のＹ座標値「Ｙ」に対して
１つ上の格子点、「Ｙ−１」とは同じくＹ座標値
「Ｙ」に対して１つ下の格子点、「反対面」とは注
目している格子点と同じ差標値（Ｘ、Ｙ）をもち
かつプリント板の反対面上の格子点を示してい
る。

第３図および第４図図示の場合には、本発明に
いう一次元探索および二次元探索が行われる処理
に対応するフローチヤートを示している。

上述の如く第１図図示の配線ルート探索処理部
における処理が行われるが、第１図図示の仮配線
処理メモリ１０上には第６図図示の場合と同様に
配線ルート探索処理部１が一次元探索条件状態の
下で決定した配線ルートが格納されており、第１
図図示の処理時には当該配線ルート探索処理部１
が二次元探索条件状態の下で処理するようにされ
る。

第１図図示のメモリ１０から、既に仮決定され
ている配線ルートが配線ルート探索処理部１に供
給されるが、このとき処理対象とされる１つの上
記仮決定されている配線ルートが配線ルート削除
処理部１１において削除され、当該削除された配
線ルートのスタート点Ｓとエンド点Ｅとが与えら
れる。そして、この状態で、配線ルート探索処理
部１が二次元探索条件状態の下で探索を行う。こ
の結果、例えば第５図図示のICピン６ＥからIC
ピン６Ｃに至る配線ルートなどについてはビア７
が省略されることになるであろう。この結果はメ
モリ２に格納される。そして次の配線ルート削除
を行つてのルート決定に当たつては、当該先に得
られた結果を利用するようにされる。勿論、上記
二次元探索を行つても何んら変更がない場合もあ
るが、一般には数多くの非所望なビアが省略され
る。そして、この結果を利用することによつて、
第６図図示の処理のみの場合において配線ルート
を決定できなかつたルートについても、所望のル
ートを決定することが可能となる。

(E) 発明の効果 以上説明した如く、本発明によれば、第６図図
示の処理のみの場合において生じている非所望な
位置のビアを省略することが可能となる。また決
定できなかつたルートをも決定することが可能と
なる。言うまでもなく、本発明においては、配線
パターンをいわば簡易な形で一旦得ておき、その
上で、より好ましい形に修正できるものはそれを
修正するようにしている。このため、最初から最
も好ましい形に配線パターンを決定してゆこうと
する処理にくらべて、処理が簡単になり、かつ修
正できない所は修正しないままに置くことができ
ることから厳格な判断処理を必要としない利点を
もつている。

【図面の簡単な説明】

第１図は本発明の方法を実行する一実施例構
成、第２図は第１図に示す配線ルート探索処理部
における処理を説明する説明図、第３図および第
４図は同じく配線ルート探索処理部における処理
を具体的に表すフローチヤートを示している。ま
た第５図は本発明の前提問題を説明する説明図、
第６図は従来の方法を説明する説明図を示してい
る。 図中の符号１は配線ルート探索処理部、２は配
線結果格納メモリ、１０は仮配線処理メモリ、１
１は配線ルート削除処理部を表す。

Claims (1)

1. 【特許請求の範囲】 １ プリント板の一方の面に形成される配線格子
   における格子点に対応して当該格子点に関連する
   配線パターン情報をもつと共に上記プリント板の
   他方の面に形成される配線格子における格子点に
   対応して当該格子点に関連する配線パターン情報
   をもつ記憶装置をそなえ、上記格子点の少なくと
   も１つをスタート点としかつ上記格子点の少なく
   とも他の１つをエンド点とする配線ルートを決定
   する配線ルート探索処理部を用いて上記配線格子
   を通る配線ルートを決定してゆく配線ルート処理
   システムにおいて、 上記配線ルート探索処理部が上記プリント板上
   の１つの面に関して実質上一次元探索を行う一次
   元探索条件状態モードと上記プリント板上の１つ
   の面に関して二次元探索を行う二次元探索条件状
   態モードとを選択することができるよう構成され
   ると共に、 上記配線ルート探索処理部を上記一次元探索条
   件状態モードに設定した上で得られた配線ルート
   についての上記配線パターン情報が格納されてい
   る記憶装置と、 当該記憶装置上で得られている１つの配線ルー
   トを処理対象として当該処理対象の配線ルートを
   仮消去した上で当該処理対象の配線ルートについ
   てのスタート点とエンド点とを与える配線ルート
   削除処理部と、 上記配線ルート探索処理部が、上記二次元探索
   条件状態モードの下で、上記配線ルート削除処理
   部による仮消去が行われた結果を用いて探索処理
   を行つた、その処理結果の配線パターン情報が格
   納される配線結果メモリとがもうけられてなり、 上記配線ルート探索処理部は、上記一次元探索
   条件状態モードの下で処理を実行して、上記一次
   元探索条件状態モードに設定した上で得られた配
   線ルートについての上記配線パターン情報が格納
   される記憶装置に当該情報を格納し、次いで、上
   記二次元探索条件状態モードの下で、上記配線ル
   ート削除処理部による処理を実行せしめ、当該配
   線ルート削除処理部による仮消去が行われた結果
   を用いて探索処理を行つて、その処理結果の配線
   パターン情報を上記配線結果メモリに格納するよ
   うにした ことを特徴とする配線ルート最適化決定処理方
   法。