JPH03180978A - 迷路法によるプリント基板の配線処理方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 （産業上の利用分野） 本発明は迷路法によるプリント基板の配線処理方式に関
し、特に迷路法が適用される範囲を拡大し、かつ効率の
よい配線経路探索を行うことができるプリント基板の配
線処理方式に関する。

（従来の技術） 従来、この種の配線処理方式は、配線領域全体を設計の
法則に従って一定の配線間隔で格子状に分割し、その格
子をセルマツプと呼ばれるデータ構造にまとめてコンピ
ュータ上の記憶領域に表現し、その表現上で順次経路探
索を行ってい友。

ここで、セルマツプと呼ばれるものは、格子上の１点を
１つのセルと呼ばれる記憶単位に対応させた二次元の配
列である。そして１セル当夛８〜１２ビット程度の大き
さで、対応する格子点が配線可能かどうか、會たどちら
の方向から探索してきたかなどの状態を表現する。

迷路法では、二つのセルとセルの間の経路を探索すると
き、一方のセルから出発して配線可能々隣接セルを順次
探索していって、他方のセルに到達するまでの配線可能
なセルの系列を求めるが、セルマツプを用いることによ
って隣接セルへの探索が効率よく簡単にできる。

第９図に迷路法による経路探索の一例を示す。

同図（ａ）は、迷路法の拡散処理の例を示し、同図（ｂ
）は、同図（＆）の拡散処理にょう求められる経路のう
ち、パックトレース（またはパックトラック）処理によ
って、実際に配線すべき経路を求める方法の一例を示す
。

第９図中の斜線を施した部分は配線禁止領域であう％Ｓ
はソースセル、Ｔはターゲットセルである。

同図（ａ）に示すように、拡敵処理は、ソースセルに隣
接する図中の上下左右のセルに％１＃をマークする。さ
らに　％　１Ｎのマークを付したセルの上下左右の空き
セルに％２Ｎをマークする。

さらに％２１のマークを付したセルの上下左右の空きセ
ルに％８＃をマークする。このようにしてマークを付し
たセルがターゲットセルに隣接するまで繰返す。

パックトラック処理は、同図（ｂ）の図中の矢印に示す
ように、ターゲットセルから％４′２％８ｆ　％２Ｉ　
％１ｒ、ンースセルというように逆にたどっていくこと
によって実際に配線すべき配線経路を求めることができ
る。

（発明が解決しようとする課題） 上述した従来の迷路法による配線処理方式は、配線経路
探索時に、隣接セルを１つずつ順次探索するので、配線
可能領域が広範囲にわたる場合、効率が悪いとｂう欠点
がある。また、プリント基板全体を一定の格子に分割す
る必要があるので、一定の格子に分割でき逢いプリント
基板については迷路法の適用ができないという欠点があ
る。

本発明の目的はこのような欠点を解消し、配線領域を矩
形領域に分割することにより格子分割ができないプリン
ト基板でも迷路法が適用することができ、また経路探索
が効率的でしかも順次探索を必要とせず、非接触領域に
ついて並列して同時に探索できるような迷路法によるプ
リント基板の配線処理方式を提供することにある。

（課題を解決するための手段） 前記の目的を達成するため本発明の迷路法によるプリン
ト基板の配線処理方式は、Ｘ軸方向、Ｙ軸方向のうち、
いずれかの方向を配線優先方向とし、前記配線優先方向
に沿って配線処理を行うべき配線領域を帯状に分割し、
分割した帯状領域のそれぞれの領域内において、たがい
に接触しない矩形領域に分割し、前記配線領域内の前記
矩形領域の相互間で配線可能なもの同士をリング状にリ
ンクして記憶する記憶手段１，２と、前記記憶手段に記
憶された配線可能領域を参照して配線ができるかどうか
を予測し、配線ができると予測されるリング状のリンク
が複数個ある場合は、迷路法による配線経路の探索を複
数のリング状のリンクについて同時に並行して行う配線
経路探索手段と、前記配線経路探索手段によって求めら
れた配線経路を配線禁止領域として、前記記憶手段の記
憶内容を更新する手段を有し、前記配線経路探索手段に
よる経路探索を繰や返して処理する方式とする。

（実施例） 次に、本発明の実施例について図面を参照して説明する
。

第１図は、本発明の一実施例の配線処理方式の手順例を
示すフローチャートである。

第１図の例は、処理の対象とするプリント基板を２層基
板とし、処理の優先方向をＹ方向（図中縦方向）として
いる。

第２図〜第５図は、第１図の実流量にかけるステップｌ
（手段１）の説明図である。

プリント基板の配線可能領域は、まず禁止領域を避けて
矩形領域に分割するが、第２図はこの配゛凍可能矩形領
域に分割した状態を示している。

ステップ１（手段１）にかいては、第２図に示すように
、ブリｙ）基板の配線可能領域から図中斜線で表わした
禁止領域を取除き、残った部分を図中に点線で表わした
ように区切って、優先配線方向であるＹ軸方向で、まず
帯状領域（以下、スロットという。）に分割する。

ここでスロットのＸ座標の列をスロットヘッダとする。

各スロットヘッダの構成例を第８図に示す。

そこで第２図のＸ座標Ｘｏ　、Ｘｔ　、Ｘｓ　、Ｘｓ、
ｘ、　、ｘ、　、ｘ、　、ｘ、によって区切られたスロ
ットを識別するためのスロットヘッダは第４図のように
なる。

スロットは、各スロット内で接触しない矩形領域に分割
する。

第２図においては各スロットを矩形領域１１．１２．１
３．１４．１５．１８．１７．１８．１９．２０に分割
する。これら各矩形領域をデータとして記憶する構造例
を第５図に示す。

第５図の例では、データは、領域ＩＤ、層番号、領域左
下座標、領域右下座標、上側スロットポインタ、下側ス
ロットポインタ、リンクポインタの順に格納されている
。

第６図、第７図、お文び第８図は、第１図におけるステ
ップ２（手段２）の説明図である。

ステップ２（手段２）では、矩形領域間で配線可能な矩
形領域をリンクポインタで結び、矩形領域データの更新
を容易にするためのスロットポインタをはる。

第６図は、たがいに接触する矩形領域をリンクポインタ
でリング状に結んだ図である。図中、矢印は、リンクポ
インタのポイント方向を表わしている。そして同一リン
グの矩形領域にのみ同一のインデックス（以下、ＩＤと
いう。）をセットする。

第６図では、第２図で少々くとも１ケ所が接する矩形領
域１１．１２．１４．１６．１５．１ｉから１１へリン
クポインタで結んでリングを形威し、これらの矩形領域
のＩＤを１とする。

また、第２図でたがいに接触する矩形領域１８．２０．
１９から１８へリンクポインタで結んでリングを形成し
、これらの矩形領域のＩＤを２とする。

會た、第２図で独立している矩形領域１７のみでリング
を形成しＩＤを８とする。

第７図は、矩形領域の接触判定を高速に行うためのデー
タのスロットポインタのはシ方を示した図である。

第７図において、３０はスロットヘッダである。

スロットヘッダ３０の内容は第４図に示すものである。

スロットヘッダ３０に続く矩形領域は、Ｙ座標が大きい
（＠２図で各スロット中の最上部にある）矩形領域１１
．１２．１４．１６．１Ｂ、２０である。したがってこ
れらの矩形領域の上側（Ｙ座標の大きい測）のスロット
ポインタはすべて行先は空き（ＮＵＬＬ）である。

第７図において、各矩形領域から出ている矢印を付した
線は、上側スロットポインタ（Ｙ座標の大きい側のポイ
ンタ）、あるいは下側スロットポインタ（Ｙ座標の小さ
い側のポインタ）のポイント方向を示している。

下側（Ｙ座標の小さい側）のスロットポインタのポイン
ト方向は同一スロットの下側（ｙ座標の（９） 小さい側）の矩形領域１３．１５．１７．１９のそれぞ
れに向い、矩形領域１１および２０にはその下側には同
一スロット内の矩形領域が々いので下側スロットポイン
タの行先は空き（ＮＵＬＬ）となる。會た、第７図中の
下側の矩形領域１３．１５．１７，１９にあっては、第
２図に示すように、図中の上側が配線禁止領域となって
いるのでそれぞれの矩形領域の上側スロットポインタの
行先は空き（ＮＵＬＬ）であり、下側スロットポインタ
の行先は、同一スロット内のそれぞれの上側の矩形領域
１２．１４．１８．１８に向う。

第８図は、２つの領域が接触するかどうかの判定方法を
示す説明図である。甘たこの判定は、結線すべきビンベ
アのンースとターゲットのピン（あるいはンースセルと
ターゲットセル）の探索開始領域を求める手段（第１図
のステップ４、すなわち第８の手段）でもある。

第８図（＆）の場合は、同じ層にあり、互いに接する矩
形領域が、その接している長さｔが配線の太さに等しい
か、それより大であれば、その２（１０） つの領域間に配線可能状態に接触しているものと判定す
る。

第８図（ｂ）の場合、上下の隣接する層間で、互いに対
向する部分に、−上下層間を電気的に接続する経路■が
完全に含！れている。この状態もｌた配線可能状態に接
触しているものと判定する。

そこで、第１図のステップ８にかいて結線すべきビンベ
アを選び、ステップ４において、ソースセルに接触する
矩形領域とターゲットセルに接触する矩形領域のうち同
じＩＤをもつ矩形領域が存在すれば、配線経路が存在し
、同一のＩＤをもつ矩形領域が存在し女、かった９、ソ
ースセル、あるいはターゲットセルに接触する矩形領域
が存在しない場合は、配線経路は存在しない。このよう
に判定することによって、選んだ結線ピンベアの配線が
可能であるかどうかは瞬時に予測できる。

手段３によって求めた、同−ＩＤによってリング状にリ
ンクポインタで結ばれた各矩形領域を１つのセルとみな
して従来の迷路法によりターゲットとなる矩形領域に接
触するまで経路探索を行う（１１） （第２図のステップ５．６）。

このような方法によってノースピンからターゲットピン
への経路が含まれる配線可能領域の列が求められる（ス
テップ７）。

その列の各矩形領域内で接触部分同士を結べば、実際の
配線経路が求められる（ステップ８）。

こうして求められた配線経路を禁止領域として配線の存
在したスロットのみを対象に、手段１と同様の方法で記
憶内容を更新（ステップ９）することによう、全ピンベ
アを結線することができる。

さらに、上述のように１つのピンベアについて配線経路
を求めている最中に、他のビンベアについて調べ、その
ビンベアに接触する矩形領域が、現在経路探索に使用し
ている矩形領域のＩＤと異なるＩＤを持っていれば配線
経路は互いに干渉したいので、複数のビンベアの経路探
索を同時に並行して行うことができる。

（発明の効果） 以上説明したように本発明は、配線領域を矩形領域に分
割することにより、従来格子分割ができ（１２） ないため迷路法が適用することができなかったプリント
基板に、迷路法を適用することができるという効果があ
る。

また、リング状にリンクされた矩形領域だけを経路探索
の対象とするため、経路が存在し邊い場合は、探索処理
を行うことなく結果が直ちに判り、効率内々探索が可能
と欧る。さらに、接触領域をリンクすることによう１非
接触領域での配線を完全に独立させることができるので
、これらの独立した配線の経路探索を並列に行うことが
できるという効果がある。

【図面の簡単な説明】

第１図は、本発明の一実施例の手順例を示す７０−チャ
ートである。 第２図は、第１図のステップ１にかいて配線領域を矩形
領域に分割する方法を示す説明図である。 第８図は、ＩＪ２図の各スロットに対応するデータの構
造例を示す説明図である。 第４図は、第２図のスロットに対するスロットヘッダの
データの具体的を示す説明図である。 （１Ｂ） 第６図は、第２図の各矩形領域のデータ構造例を示す説
明図である。 第６図は、第１図のステップ２にかいて各矩形領域をリ
ンクする状況を示す説明図である。 第７図は、第２図の各矩形領域をスクットポインタによ
シ関連づける状況を示す説明図である。 第８図は、隣接する矩形領域の接触判定を行う方法を示
す説明図である。 第９図は、一般の迷路法による経路探索方法を示す説明
図である。 １〜９・・・配線処理手順のステップ １１〜２０・・・矩形領域 ３０・・・スロットヘッダ Ｓ−・・ソースセル Ｔ・・・ターゲットセル ｘ、　−Ｘ、　・・・Ｘ座標

Claims (1)

【特許請求の範囲】
1. プリント基板の配線処理方式において、Ｘ軸方向、Ｙ軸
   方向のうち、いずれかの方向を配線優先方向とし、前記
   配線優先方向に沿つて配線処理を行うべき配線領域を帯
   状に分割し、分割した帯状領域のそれぞれの領域内にお
   いて、たがいに接触しない矩形領域に分割し、前記配線
   領域内の前記矩形領域の相互間で配線可能なもの同士を
   リング状にリンクして記憶する記憶手段と、前記記憶手
   段に記憶された配線可能領域を参照して配線ができるか
   どうかを予測し、配線ができると予測されるリング状の
   リンクが複数個ある場合は、迷路法による配線経路の探
   索を複数のリング状のリンクについて同時に並行して行
   うことができる配線経路探索手段と、前記配線経路探索
   手段によつて求められた配線経路を配線禁止領域として
   、前記記憶手段の記憶内容を更新する手段を有し、前記
   配線経路探索手段による経路探索を繰り返して処理する
   ことを特徴とする迷路法によるプリント基板の配線処理
   方式。