JPH0460774A

JPH0460774A - 自動配線方式

Info

Publication number: JPH0460774A
Application number: JP2169770A
Authority: JP
Inventors: So Yamauchi; 山内　宗
Original assignee: NEC Corp
Current assignee: NEC Corp
Priority date: 1990-06-29
Filing date: 1990-06-29
Publication date: 1992-02-26

Abstract

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

Description

【発明の詳細な説明】〔産業上の利用分野〕本発明は、集積回路やプリント基板の自動配線方式に関
するものである。

〔従来の技術〕

従来の自動配線方式としては、「線分探索法」を改善し
た「改良線分探索法」というものが知られている。これ
は、障害物の角から集積回路のデザイン・ルールを満た
す距離だけ離れた位置にコーナー・ポイントというもの
を生成し、そのコーナー・ポイントを通るエスケープ・
ラインを生成する。エスケープ・ラインを生成する際に
は、エスケープ・ラインがデザイン・ルールを満たすよ
うにその長さを定める。すなわち、コーナー・ポイント
からエスケープ・ラインを伸ばしていき、障害物に近付
く許容範囲にまでたどりついたら、そこで伸ばすのを止
める。次に、配線を行う端子Ｓ、端子りの双方から、線
（探索線と呼ぶ）を生成する。そして、端子Ｓから生成
された探索線と交わるエスケープ・ラインを列挙して、
新たな探索線とするという操作を、端子Ｓに由来する探
索線が端子りに由来する探索線にたどりつくまで繰り返
し、たどりついたら探索線を逆方向に追跡することで配
線経路を完成させるという方式である。

この従来技術については、１９８８年電子情報通信学会
技報「ヒープ探索木を用いた改良線分探索法コに詳述さ
れている。

また、「改良線分探索法」を多層配線に対応させ、さら
に、並列処理を可能にすることによって、配線速度を向
上させている「並列線分探索法」というものもある（特
願平１−２６７８０８号明細書）。これは、並列処理す
る計算機の台数をＮ台とすると、各配線層毎に配線方向
に合わせて配’ＩＡ　ｅＭ域をＮ分割し、各計算機は、
自分の担当する配線領域に含まれる障害物および、障害
物自体は隣の領域に存在するが、デザイン・ルールによ
ってその障害物が与える影響が自分の領域に及ふところ
の障害物の属性、位置を記憶する。そして、それらの障
害物に伴うコーナー・ポイントの生成、エスケープ・ラ
インの生成を各々の計算機が並列に行う。次に、接続す
る端子（端子Ｓ、端子Ｄ）を含む領域を担当する計算機
が、それらの端子から探索線を生成し、端子Ｓから生成
された探索線の位置、長さを他のすべての計算機に送る
。端子りから生成された探索線は、その探索線を生成し
た計算機のエスケープ・ラインの集合に加えておく。各
計算機は、送られて来た探索線に関する情報に基ついて
、その探索線と交差するエスケープ・ラインが自分の担
当する領域に存在するかを調べ、列挙し、それらを新た
な探索線として、それらの位置、長さを他のすべての計
算機に送るという処理を、繰り返す。そして、列挙した
エスケープ・ラインの中に、端子りから生成された探索
線が含まれていたら、配線経路をみつけたことになる。

そして、交差しているエスケープ・ラインを端子りの側
から、端子Ｓの側へ逆向きに追跡（バック・トレースと
呼ぶ）することにより、経路を完成させる。

このハック・トレースは、それぞれのエスケープ・ライ
ンを受は持つ計算機によって行われる。

〔発明が解決しようとする課題］「改良線分探索法」は、基本的には１対１のピンペアを
配線するためのアルゴリズムであり、複数の端子で構成
されるネットを配線するには端子の封缶に順番に配線し
なければならず、総配線長も長くなってしまう。

「並列線分探索法」においても、複数端子で構成される
ネットの配線については「改良線分探索法」と同じ問題
が残ったままである。

本発明の目的は、このような欠点を除去し、集積回路や
プリント基板の配線に際して総配線長を短くできる自動
配線方式を従供することにある。

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

本発明は、多層構造を持つ集積回路やプリント基板の自
動配線処理の際に、障害物についてはその角からデザイ
ン・ルールを満たす距離だけ離れた位置にコーナー・ポ
イントを生成し、そのコーナー・ポイントを基準として
そのコーナー・ポイントが属する層の配線方向に従って
、障害物を回避するエスケープ・ラインを生成し、それ
らのエスケープ・ラインの中から端子間を接続するため
の経路を探索する自動配線方式において、複数の端子を
配線する際に、まず、それらの端子の内の適当なピンペ
アを選んで配線し、その結果、新たに生成された配線経
路を構成する端子やスルーホールをターゲットとして、
次に配線する端子から探索線を伸ばして配線を行うこと
を繰り返して複数の端子を配線することを特徴としてい
る。

（作用）本発明においては、多層構造を持つ集積回路やプリント
基板の自動配線処理の際に、障害物についてはその角か
らデザイン・ルールを満たす距離だけ離れた位置にコー
ナー・ポイントを生成する。

コーナー・ポイントを基準としてそれが属する層の配線
方向に従って、障害物を回避するエスケープ・ラインを
生成する。複数の端子を配線する際に、まず、それらの
端子の内の適当なピンペアを選び（ソース側端子Ｓとし
、ターゲット側端子りとする）、それらの端子から、絵
、横に探索線を生成する。端子Ｓがら生成された探索線
は、探索キューに蓄える。端子りから生成された探索線
は、エスケープ・ラインの集合に加えておく。

次に、探索キューの中の探索線と交差するエスケープ・
ラインを列挙し、それらを新たな探索線として探索キュ
ーに蓄える。列挙したエスケープ・ラインの中に、端子
りから生成された探索線が含まれていたら、配線経路を
みつけたことになる。

そして、交差しているエスケープ・ラインを端子りの側
から、端子Ｓの側へ逆向きに追跡（ハック・トレースと
呼ぶ）することにより、経路を完成させる。

次に、３つめ以降の端子を配線する際には、最初のピン
ペアの配線によって新たに生成された配線経路を構成す
る端子やスルーホールをターゲット側の端子、次に配線
する端子をソース側の端子と考える。配線経路を構成す
る端子やスルーホールから生成した探索線はエスケープ
・ラインの集合に加え、次に配線する端子から生成した
探索線は探索線として探索キューに蓄える。それらの探
索線と交差するエスケープ・ラインを探索しながら、配
線経路を求める方法は、最初のビンベアの時と同しであ
る。配線経路を構成する端子やスルーホールから生成し
た探索線にたどりついたら配線経路がみつかったことに
なる。そして、複数の端子で構成されたネットの配線を
し、１ネット分が終わったらそのネットを構成する配線
経路は新たな障害物となるので、それらの周辺のコーナ
ー・ポイント、エスケープ・ラインを更新し、その後で
次のネットの配線へと進む。

このように、本発明では、複数の端子で構成されたネッ
ト配線する際に、配線が済んだピンベアの配線経路を構
成する端子やスルーホールから探索線を生成して、次に
配線する端子から生成した探索線のターゲットとするこ
とにより、従来の「改良線分探索力」や「並列線分探索
法」をそのまま用いる場合よりも、複数端子で構成され
たネットの総配線長を短くすることが可能となり、より
実用に通するようになるという効果がある。

〔実施例〕

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

第１図から第８図は、本発明の一実施例を説明するため
の図である。すなわち、第１図から第８図は、２層の配
線層における配線の様子を図示したものである。また、
簡単のために障害物は第１層と第２層の両方の層にまた
がっであるものとしている。

第１図では、前処理の様子を示す。ここで示している例
は、４端子Ａ、　Ｂ、　Ｃ，Ｄすなわち端子１４、１５
．１６．１７で構成されたネットを２層の配線領域に配
線するものである。まず、障害物１１に関する情報に基
づき、それらの障害物１１の角からデザイン・ルールの
許容範囲だけ離れた位置にコーナー・ポイントＣＰ　（
Ｃｏｒｎｅｒ　Ｐｏ１ｎｔ）すなわちコーナー・ポイン
ト１２を生成する。そして、生成したコーナー・ポイン
ト１２が障害物からデザイン・ルールの許容範囲以上離
れた位置にあるかどうかを調べ、それを守っていないコ
ーナー・ポイント１２は取り除く。次に、コーナー・ポ
イント１２からエスケープ・ラインＥ　Ｌ　（Ｅｓｃａ
ｐｅ　Ｌｉｎｅ）すなわちエスケープ・ライン１３を生
成する。これは、コーナー・ポイント１２からその層の
配線方向に沿って線を伸ばした時に最初にぶつかる障害
物１１からデザイン・ルールの許容範囲だけ離れた位置
まで伸ばして生成する。そして、最初のピンペア（端子
１４、端子１５）を配線するために、それらの端子１４
、端子１５から探索線（Ｓｅａｒｃｈ　Ｌｉｎｅ）１８
を生成する。

これは、端子の存在する層、およびその隣（上、下）の
層の同一座標の点から、その層の配線方向に沿って障害
物からデザイン・ルールの許容範囲だけ離れた点まで線
を伸ばして探索線１８とする。

端子１４から生成された探索線１８は探索キューに入れ
られ、端子１５から生成された探索線１８はエスケープ
・ラインのキューに蓄える。そして、端子１４から生成
された探索線１８と交差するエスケープ・ライン１３を
探し、それらのエスケープ・ライン１３をキューに蓄え
る。そして、キューに蓄えたエスケープ・ライン１３の
集合（集合Ｐとする）の中に、端子１５から生成された
ものがあるかどうかを調べ、もし無い場合には、集合Ｐ
に含まれるエスケープ・ライン１３と交差するエスケー
プ・ライン１３の探索をするという作業を端子１５から
生成されたエスケープ・ライン１３にたどりつくまで繰
り返す。このようにして配線経路２１をみつけた様子を
第２図に示す。

次に、３つめの端子１６と最初のピンペア（端子１４、
端子１５）との間の配線をするために、新たに生成され
た配線経路２１を構成する端子１４、端子１５、スルー
ホール（Ｔｈｒｏｕｇｈ　Ｈｏ１ｅ）３１からターゲッ
ト側の探索線１８を生成し、端子１６からソース側の探
索線１８を生成する（第３図参照）。そして、最初のピ
ンペア（端子１４、端子１５）の配線の時と同様に、ソ
ース側の探索線１８と交差するエスケープ・ライン１３
を探索してターゲット側の探索線までたどりつく。こう
して最初のピンペア（端子１４、端子１５）を結ぶ配線
経路２１へ端子１６を結ぶ配線経路２１が完成する（第
４図参照）。

このようにして端子工４、端子１５、端子１６を結ふ配
線経路２１ができる。そして、この配線経路２１を構成
する端子１４、端子１５、端子１６、スルーホール３１
から探索線を同様に生成して４つめの端子１７の配線を
する様子を第５図、第６図に示す。４個の端子１４、端
子１５、端子１６、端子１７を結ぶ配線経路２１は、第
７図のように完成する。

新たに生成された経路２１は、新たな障害物となるので
、それらの周辺のエスケープ・ライン１３、コーナー・
ポイント１２を更新する必要がある（第８図）。まず、
配線経路２１の周辺の配線禁止領域に含まれるコーナー
・ポイント１２とそのコーナー・ポイント１２から生成
されたエスケープ・ライン１３を取り除き、配線禁止領
域（デザイン・ルールを満たす距離だけ離れていない領
域）にエスケープ・ライン１３は含まれているが、その
基となるコーナー・ポイント１２自体は配線禁止領域外
である場合には、そのコーナー・ポイント１２からエス
ケープ・ライン１３を生成し直す。また、配線経路２１
の周りにも、コーナー・ポイント１２とエスケープ・ラ
イン１３を生成する。

そして、配線領域のエスケープ・ライン１３、コーナー
・ポイント１２の更新が終わったら、次のネットの配線
を行う、ということを繰り返す。

〔発明の効果〕

以上説明したように本発明では、複数の端子で構成され
たネット配線する際に、配線が済んだピンペアの配線経
路を構成する端子やスルーホールから探索線を生成して
、次に配線する端子から生成した探索線のターゲットと
することにより、従来の「改良線分探索力Ｊや「並列線
分探索法」をそのまま用いる場合よりも、複数端子で構
成されたネットの総配線長を短くすることが可能となり
、より実用に適するようになるという効果がある。

【図面の簡単な説明】

第１図は、前処理で障害物の周辺にコーナー・ポイント
ＣＰ、エスケープ・ラインＥＬを生成し、端子からは探
索線を生成した様子を示した図、第２図は、みつけた配
線経路を完成した様子を示した図、第３図は、３つめの端子から探索線を生成した様子を示
した図、第４図は、３つめの端子と最初のピンペアとの間の配線
経路が完成したところを示した図、第５図は、４つめの
端子から探索線を生成した様子を示した図、第６図は、４つめの端子と最初のピンペアとの間の配線
経路が完成したところを示した図、第７図は、４端子の
ネットの配線が終わった様子を示した図、第８図は、配線経路の周りのコーナー・ポイン）ＣＰ、
エスケープ・ラインＥＬが更新された様子を示した図で
ある。１１・・・・・障害物１２・・・・・コーナー・ポイント１３・・・・・エスケープ・ライン１４・・・・・端子Ａ１５・・・・・端子Ｂ１６・・・・・端子Ｃ１７・・・・・端子Ｄ１８・・・・・探索線２１・・・・・配線経路３１・・・・・スルーホール

Claims

【特許請求の範囲】

（１）多層構造を持つ集積回路やプリント基板の自動配
線処理の際に、障害物についてはその角からデザイン・
ルールを満たす距離だけ離れた位置にコーナー・ポイン
トを生成し、そのコーナー・ポイントを基準としてその
コーナー・ポイントが属する層の配線方向に従って、障
害物を回避するエスケープ・ラインを生成し、それらの
エスケープ・ラインの中から端子間を接続するための経
路を探索する自動配線方式において、複数の端子を配線する際に、まず、それらの端子の内の
適当なピンペアを選んで配線し、その結果、新たに生成された配線経路を構成する端子や
スルーホールをターゲットとして、次に配線する端子か
ら探索線を伸ばして配線を行うことを繰り返して複数の
端子を配線することを特徴とする自動配線方式。