JPH04177472A - 自動配線方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は自動配線方法、特にプリント基板、ノ・イブリ
ッドＩＣおよびＬＳＩなどのＣＡＤにおいて、最適な配
線レイアウトを行なうための自動配線方法に関する。

〔従来の技術〕

従来、この種の自動配線方法は、結線対象のピンペア群
について、まずピンペアをその間隔の短い順あるいは長
い順に並び変え、その順番に従って経路探索を行ってい
る。そしであるピンペアで経路探索に失敗した場合はそ
の時点でそのピンペアの結線を断念し、次のピンペアの
結線に処理を進めている。

一方、失敗したピンペアを即座に断念しない手法もある
。あるピンペアの経路探索が失敗した場合に、どの様な
状況下で失敗したかを解析し、失敗したピンペアを結線
するためには既に配線されたピンペアの内のどのピンペ
アをひきはがせば失敗したピンペアを配線できる可能性
が高いかを判断する。その可能性の高いピンペアをひき
はがして、経路探索に失敗したピンペアを再度配線し直
し、先程ひきはがしたピンペアを引き直すという配線方
法である。この種の自動配線方法をリップアップルータ
といっている。

例えば、第１３図のように、配線エリア５内に結線対象
のピンペア６．７．８．９．１０．１１の６つのピンペ
アが既に結線されている場合、ピンペア１２を結線でき
ない。そこで、ピンペア６〜１１のどのピンペアをひき
はがすべきか算出する。算出方法は結線できないピンペ
ア１２のピン１３とピン１４とから波紋を広げるように
既配線を探索し、その探索結果から判断する。第１４図
はピン１３から波紋を広げた場合であり、既配線に到達
した位置にＸ印を付けである。また、エリア１５は広げ
た波紋の領域を表す。一方第１５図はピン１４から波紋
を広げた場合であり、既配線に到達した位置に○印をつ
けである。またエリア１６は広げた波紋の領域を表す。

次に、各既配線ごとに次の算出式を計算する。

Ｐ（ｗ）＝ｍｉｎ　（Ａ−ａ、　Ｂ−ｂ）ここで、ｍｉ
ｎ　（）は括弧内の小さい方の値を表す。

また、Ｗは各既配線を識別するための値である。

そして、Ａはその既配線の×の数、Ｂは○の数を表す。

例えば、第１４図と第１５図とからピンペア６のＡとＢ
との値はそれぞれ２と５とになる。

さらに、ａおよびｂはその既配線の端点にある２つのピ
ンが、波紋を広げたエリアに対し同一領域あるいは境界
上であったら０、異なる領域であったら１とする。例え
ば第１４図のピンペア６は、ピン１７がエリア１５内に
あるが、ピン１８はエリア１５外なのでａの値はｌとな
る。一方第１５図におけるピンペア６は、ピン１７もピ
ン１８も共にエリア１６外にあるためｂの値は０となる
。以上の定義からピンペア６の算出式の値は以下のよ・
うに算出される。

Ｐ（６）＝ｍｉｎ　（２−１，５−０）　＝ｍｉｎ　（
１，５）　＝１となる。

以上のような算出を波紋が到達した全既配線に関して行
う。第１３図の６つの既配線に対して同様に算出すると
以下のようになる。

Ｐ（６）＝ｍｉｎ　（２−１，５−０）　＝：ｍｉｎ　
（１，５）　＝ＩＰ（７）＝ｍｉｎ　（７−０，０−０
）　＝ｍｉｎ　（７，Ｏ）　＝ＯＦ（８）＝ｍｉｎ　（
４−１，２−１）　＝ｍｉｎ　（３，１）　＝ＩＰ（９
）＝＝ｍｉｎ　（５−１、３−０）　＝ｍ：ｎ　（４，
３）　＝３Ｐ（１０）ｍｉｎ　（２−０，５−０）　＝
ｍｉｎ　（２，５）　＝２算出値が０のものは、はがし
ても失敗したピンペアを再配線することができないこと
を意味しており、また、算出値が大きい既配線をはがす
程再配線が成功する可能性が高いことを意味する。した
がってこの場合は最大値３を持つピンペア９をはがすべ
きことがわかる。

この結論からピンペア９をはがし、失敗したピンペア１
２を再配線して、ひきばかしたピンペア９を配線し直し
た図が第１６図である。

以上の例では、既配線を一本のみひきはがしたが、失敗
したピンペアを配線し直せなかった場合に算出値の高い
ものから二本、三本と複数まとめて、あるいは順次ひき
はがしていく方法もある。

〔発明が解決しようとする課題〕

上述した従来のリップアップルータの手法は、初期のピ
ンペア結線順は特に限定せず、未結線が発生した段階で
ひきはがす既配線の候補を探すために、効率的なひきは
がしを行うことができないという問題点がある。また、
ひきはがす候補を探す際に、波紋を広げる手順を踏むこ
とから処理速度がかかり、既配線が比較的少ない段階で
は波紋が基板全面に広がる可能性もあり処理時間が膨大
にかかるという問題点もある。さらに、ひきはがした後
に失敗したピンペアの再配線が確実に成功するという保
証もなく、かつ失敗ピンペアが再配線できてもひきはが
したピンペアが復旧できるという保証もない。したがっ
て、処理時間を多く費やした後に結局配線率を上昇させ
るこができないといった局面を発生しやすいという問題
点がある。

さらに、また、ひきはがすべきピンペアを何本にするか
という問題も経験的な要素を導入せざるを得なく、画一
的なアルゴリズムを組むことが難しいという問題点があ
る。そして、ひきはがすべき最適な既配線を算出するた
めにかなりのメモリテーブルを使用するという問題点が
ある。

加えて、一つ一つのピンペアの結線方法が従来の経路探
索を繰返すだけにとどまるため、いくらひきはがしても
結線不能な状態に陥る場合がある。

例えば第２図のような結線を行う場合にピンペアＬ　　
２．３．４の順に配線を試みると、第１１図のようにピ
ンペア３で結線が失敗する。ここで、従来の手法にした
がってピンペア２をひきはがし、ピンペア３を再配線し
た後、再度ピンペア２をひき、次にピンペア４をひこう
とすると、第１２図のように配線に失敗する。このよう
に、従来の方法では直前に結線した配線が配線チャネル
をふさいでしまい、いくらひきはがしても成功に至らな
いという問題点がある。

本発明の目的は、初期のピンペアの結線順と各ピンペア
の経路探索方法とを有機的に関連させ、ひきはがし処理
を効率的に行うと共に、ひきはがす本数をひきはがしア
ルゴリズム自体に内包しつつ、無限ループ処理に陥らぬ
ように再配線成功時に、配線の組替え情報を記憶するポ
インタを与えることで、画一的な自動配線方法を提供す
ることである。

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

本発明の自動配線方法は、与えられた結線対象のピンペ
ア群を配線エリアの任意の方向に近いもの順に並び変え
る前処理と、この前処理により並び変えた順番に前記の
方向に極力沿って経路を探索する第１の処理と、この第
１の処理で経路探索に失敗したとき今まで結線したピン
ペアをひきはがしながら失敗した経路探索を再度実行す
る第２の処理と、この第２の処理による再度の実行でも
失敗した場合に、ひきはがすピンペアの量を次第に増加
させながら経路探索を繰返す第３の処理と、この第３の
処理によりひきはがすピンペアの増加に伴って局所的に
配線の順番を変化させる第４の処理と、この第４の処理
による配線順番の変化により局所的にピンペアの結線が
成功した場合に、順番を入換えた状況を示すポインタを
与える第５の処理と、前記第４の処理により配線の順番
を入換えるときにポインタをトレースしループ状態にな
っている場合は結線を断念する第６の処理とを有するこ
とにより構成される。

〔実施例〕

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

第１図は本発明の一実施例のＳＰＤ形式のフローチャー
トである。第１図のフローチャートのアルゴリズムにし
たがって、特にひきはがしレベルの増加過程と結線順序
の組替え処理とを中心に説明を進める。今、第２図のよ
うなピンペア群が与えられた場合を例に、ピンペア１．
２．３．４の順に結線を試みる（ステップ■、＠〜［相
］）。結線経路の探索は極力下方に沿って行うと（ステ
ップ■〜■、■）、第３図のようにピンペア４で結線が
失敗する（ステップ■、■、ｏ）。ここでピンペア３を
ひきはがしくステップ０．■〜＠）、ピンペア４を配線
した後ピンペア３を再度ひきなおす（ステップ０）。と
ころが、第４図のように再配線に失敗する（ステップ＠
、＠、ｅ）。そこで今度は、ひきはがすレベルを上げて
（ステップｅ。

■）、ピンペア２もひきはがしくステップ■、Ｃ〜＠）
、第５図のようにピンペア１．４．３．２の順番で結線
を試みる（ステップ０）。しかし、ここでもピンペア２
で結線に失敗する（ステップＣ２０）。そこでピンペア
４，３．２の三つのピンペアで結線順を組替え（ステッ
プＯ）、第６図のようにピンペア３．２．４の順番で結
線を行う（ステップ■、［相］〜０）。ここでピンペア
４で結線に失敗するので（ステップ＠、＠、ｅ）、再び
ひきはがすレベルを上げてピンペア１をひきはがしくス
テラ７”＠、＠、［相］、Ｃ〜＠）、第７図のようにピ
ンペア３．２．４．１の順番に結線する（ステップｏ）
。ここでもピンペア１で失敗するので（ステップ＠、＠
）、ピンペア２．４．１，３と順番を組替えて（ステッ
プＯ）、結線し直すと（ステ、ツブＣ２Ｃ〜０）、第８
図のように結線が完了する（ステップ＠、　０−＠ｌ）
。最後に極力下方に向かって結線した配線を整形しくス
テップ■〜■）、第９図のように最終配線形状とする（
ステップ■。

■〜■、■）。

また、無限ループに陥らぬように、ピンペアの組替えに
成功した場合に（ステップ＠、０）、各ピンペアごとに
結線に失敗した原因となったピンペアのポインタを与え
（ステップＱ）、そのポインタにより結線の前後関係を
記憶しておく。このポインタがループ状態になった場合
に（ステップ■、＠）、上記の手順で繰返しても無限ル
ープに陥ってしまうことになるので、処理を中断する判
断を行うことが可能となる（ステップ■）。

第１０図は無限ループを抑止する構造を説明するための
図である。今、Ａ、Ｂ、Ｃという三つのピンペアがあり
、（ａ）のごとく、Ａを結線するとＢが結線できず、Ｂ
を結線するとＣが結線できず、Ｃを結線するとＡが結線
できないといった三つ巴の状態になっていたとする。こ
こでは結線不可能状態を他のピンペアに与える関係を実
線矢印で示しである。初期の結線順番をＡＢＣとすると
、（ｂ）図のごとく、Ｂで結線に失敗する。そこで、結
線順を上記ピンペアの組替え規則に従ってＢＡＣとする
と、（ｃ）図の様にＢの結線が成功するため、ＢからＡ
に向けてＢの失敗原因がＡであることを示すポインタを
与えておく。このポインタを点線の矢印で示しである。

しかしＣで結線を失敗するため、ＣＢＡと結線順序をか
える。（ｄ）図のようにＣの結線は成功しＣからＢへの
失敗原因ポインタを与える。しかしＡで再び結線に失敗
する。

次に（ｅ）図の様に結線順序はＡＣＢと組替えられ、こ
の結線過程でＡからＣへの失敗原因ポインタが与えられ
る。ここでＢが失敗すると、失敗原因ポインタはＢから
ループを成してＢに戻ってくるので、無限ループ処理に
陥ることが判明され、Ｂのピンペアを断念して自動配線
をさらに先に進めて行くことが可能となる。

〔発明の効果〕

以上説明したように本発明の自動配線方法は、経路探索
アルゴリズムとピンペアの結線順序とを有機的に結び付
けており、ひきはがし再配線の処理を効率的に行うこと
が可能で、従来のリップアップルータよりも高速に処理
を行える。また、使用するメモリは従来に比べかなり少
なくてすむ。

さらに従来のリップアップルータで、ひきはがし再配線
を行っても失敗していたピンペア群を、ひきはがしレベ
ルを次第に増やしていく手順と、ひきばかししたピンペ
アを組替えて結線を試みるという手続きとにより結線で
きる可能性を高めるという効果がある。加えて、再配線
試行時に失敗原因ポインタを与えることで、無限ループ
を抑止し、最小限の処理で再配線の試行を停止させるこ
とを可能とする効果がある。

【図面の簡単な説明】

第１図は本発明の一実施例のフローチャート、第２図は
結線すべき四つのピンペアと配線エリアとの一例を示す
図、第３図から第９図までは第１図の実施例を第２図の
結線に適応した場合の処理過程を示す配線図、第１０図
は本発明の無限ループを抑止する機構を説明するための
図、第１１図および第１２図は従来の自動配線方法にお
ける失敗例を示す図、第１３図から第１６図までは従来
のりツブアップ手法のアルゴリズムを説明するための図
である。 １．４，６．〜１２・・・・・・ピンペア、５・・・・
・・配線エリア、１３，１４，１７．１８・・・・・ピ
ン、１５．１６・・・・・・波紋の到達エリア。 代理人　弁理士　　内　原　　　音 第　ｌ　図（ａ−） 第　ｌ　図（ｂ） １９７７（Ｃ） 簗　ｌ　図　（４） ＄１図（ｅ） Ｉｐ　２　）　３　）　４　：ピン父ア　　　第　２　
図第３　圀 第　４　図 第　５　図 第７図 第８　図 第ｑ　図 （Ｃ）爬＃曖：ＢＡＣ 拓　ｌθ　区

Claims (1)

【特許請求の範囲】
1. 　与えられた結線対象のピンペア群を配線エリアの任意
   の方向に近いものに順に並び変える前処理と、この前処
   理により並び変えた順番に前記の方向に極力沿って経路
   を探索する第１の処理と、この第１の処理で経路探索に
   失敗したとき今まで結線したピンペアをひきはがしなが
   ら失敗した経路探索を再度実行する第２の処理と、この
   第２の処理による再度の実行でも失敗した場合に、ひき
   はがすピンペアの量を次第に増加させながら経路探索を
   繰返す第３の処理と、この第３の処理によりひきはがす
   ピンペアの増加に伴って局所的に配線の順番を変化させ
   る第４の処理と、この第４の処理による配線順番の変化
   により局所的にピンペアの結線が成功した場合に、順番
   を入換えた状況を示すポインタを与える第５の処理と、
   前記第４の処理により配線の順番を入換えるときにポイ
   ンタをトレースしループ状態になっている場合は結線を
   断念する第６の処理とを有することを特徴とする自動配
   線方法。