(57)【特許請求の範囲】
【請求項１】
コンピュータにより自動的に配線を求める自動配線装置において，
配線情報に従って，始点から終点にいたる配線経路を探索する経路探索手段と，
正方格子上の各点の探索で求めた配線経路においてビアを必要とする格子点にビアを設定する正方格子ビア設定手段と，
正方格子上の任意の点をＡとして，正方格子上の格子点であり，該格子点Ａを含み千鳥パターンとなる点をグループ１として，グループ１の探索で，ビアを必要とする格子点にビアを設定するビアグループ１設定手段と，
前記グループ１に含まれる点に対して，正方格子上で隣接し，１つ格子点のずれた千鳥パターンとなる点をグループ２として，グループ２の探索で，ビアを必要とする格子点にビアを設定するビアグループ２設定手段と，
ビアと線分の間隔および２つのビアどうしの間隔の関係が制約条件を満たしているかいないかを判定する制約条件判定手段とを備え，
前記経路探索手段は，正方格子点の探索で求めた配線経路上に配置されたビアが，前記制約条件を満たさない場合に，前記制約条件を満たさないビアが配置された格子点を含むグループ１の格子点について経路探索し，最適配線経路となる格子点にビアを設定し，該グループ１から設定したビアが前記制約条件を満たしていれば，求めた最適配線経路を出力し，グループ１の格子点の探索で制約条件を満たすビアがみつからない場合には，グループ２の格子点について経路探索し，最適配線経路となる格子点にビアを設定し，該グループ２から設定したビアが前記制約条件を満たしていれば，求めた最適配線経路を出力するものであることを特徴とする自動配線装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は，計算機を利用して配線を決定する自動配線装置に関するものである。
【０００２】
プリント基板等の配線設計はＣＡＤ等のコンピュータプログラムにより計算機を利用し，自動的に配線経路を求めている。配線経路は配線の制約条件（配線どうしの間隔，配線とビアの間隔，ビアどうしの間隔等）を満足する必要がある。そして，実装密度の向上により，適切な配線を効率的に求める自動配線装置が必要とされている。
【０００３】
【従来の技術】
図９は従来の技術の説明図である。
図９ (a)，図９ (b)において，
１１１はビアＡである。
【０００４】
１１２はビアＢである。
１１３は線分であって，配線である。
１１４は裏の配線であって，ビアＡ（１１１）とビアＢ（１１２）を接続する線分である。
【０００５】
ビアＡ（１１１）と線分１１３の間の距離をＬ１とする。
ビアＢ（１１２）と線分１１３の間の距離をＬ２とする。
ビアＡ（１１１）とビアＢ（１１２）の間の距離をＬ３とする。
【０００６】
ビアと線分の間の距離Ｌ１，Ｌ２は，ビアと線分の距離についての制約条件を満たしているとする。ビアに対してはさらに制約条件があり，線分とビアの間隔を２倍にしたものよりもビアどうしの間隔が大きくなければならないというものがある。即ち，図９ (a)において，Ｌ３＞２×Ｌ１，およびＬ３＞２×Ｌ２でなければならないというものである。図９ (a)はＬ３＝２×Ｌ１およびＬ３＝２×Ｌ２であるので，この条件を満たしていない。
【０００７】
図９ (b)は，Ｌ３＞２×Ｌ１およびＬ３＞２×Ｌ２であるので，この条件を満たしているものである。
図９ (c)は正方格子上に千鳥パターンで配置したビアの例である。
【０００８】
１１５は配線の線分である。
上記のビアどうしの間隔に対する制約条件を満たすようにするため，従来の自動配線装置は，経路探索において発生させるビアの位置は，図９ (c)のように正方格子上で千鳥パターンに発生するようにしている。このような位置のビアで求めたビア位置はビアどうしの間隔に対する制約条件を自動的に満足させるものである。
【０００９】
【発明が解決しようとする課題】
図１０は発明が解決しようとする課題の説明図である。
図１０ (a)はビアの配置がビアの配置間隔の条件を満たしていない場合である。
【００１０】
１１１はビアＡであって，正方格子上に配置されているものである。
１１２はビアＢであって，正方格子上に配置されているものである。
１１３は線分である。
【００１１】
ビアＡ（１１１）と線分１１３の間隔およびビアＢ（１１２）と線分１１３の間隔に対するビアＡ（１１１）とビアＢ（１１２）の間隔が前述の制約条件を満たしていない。
【００１２】
図１０ (b)はビアＡを含む千鳥パターンのビアを表す。
図１０において，ビアＣ，ビアＤ，ビアＥはビアＡを含む千鳥パターン上のビアである。１１６は表面が配線禁止領域とされていて，ビアを配置できない領域である。
【００１３】
図１０ (b)において，ビアＡに対して最も条件の良いビア（最短経路のビア）はビアＥであるが，表面が配線禁止領域１１６のためにビアＥを配置できない。そのため最適配線経路を求めることができない。
【００１４】
図１０ (c)は，ビアＡを含む千鳥パターンの位置にないビアにより配線した状態を示す。
図１０ (c)において，ビアＦはビアＡを含む千鳥パターンのビアグループからはずれた位置のビアである。そして，ビアＡとビアＦにより最適経路が与えられるとする。そして，ビアＡとビアＦの間隔はそれぞれのビア（ビアＡ，ビアＦ）と線分１１３との間隔に対するビアＡとビアＦの間隔の制約条件を満足している。
【００１５】
上記のように，従来の自動配線では，一通りの千鳥パターンのビアグループにしかビアを配置することができなかったので，図１０ (c)のように千鳥パターンのビアグループ以外の位置のビアで最適経路を求めることができる場合でも，実際には配線経路を求めることができなかった。
【００１６】
本発明は，ビアを正方格子上のどのような位置にとっても自動配線できる自動配線装置を提供することを目的とする。
【００１７】
【課題を解決するための手段】
本発明は，コンピュータにより自動的に配線を求める自動配線装置において，配線情報に従って，始点から終点にいたる配線経路を探索する経路探索手段と，正方格子上の各点の探索で求めた配線経路においてビアを必要とする格子点にビアを設定する正方格子ビア設定手段と，正方格子上の任意の点をＡとして，正方格子上の格子点であり，該格子点Ａを含み千鳥パターンとなる点をグループ１として，グループ１の探索で，ビアを必要とする格子点にビアを設定するビアグループ１設定手段と，前記グループ１に含まれる点に対して，正方格子上で隣接し，１つ格子点のずれた千鳥パターンとなる点をグループ２として，グループ２の探索で，ビアを必要とする格子点にビアを設定するビアグループ２設定手段と，ビアと線分の間隔および２つのビアどうしの間隔の関係が制約条件を満たしているかいないかを判定する制約条件判定手段とを備え，前記経路探索手段は，正方格子点の探索で求めた配線経路上に配置されたビアが，前記制約条件を満たさない場合に，前記制約条件を満たさないビアが配置された格子点を含むグループ１の格子点について経路探索し，最適配線経路となる格子点にビアを設定し，該グループ１から設定したビアが前記制約条件を満たしていれば，求めた最適配線経路を出力し，グループ１の格子点の探索で制約条件を満たすビアがみつからない場合には，グループ２の格子点について経路探索し，最適配線経路となる格子点にビアを設定し，該グループ２から設定したビアが前記制約条件を満たしていれば，求めた最適配線経路を出力する構成をもつ。
【００１８】
図１は本発明の基本構成を示す図である。
図１ (a)は，装置構成である。
図１ (a)において，
１は自動配線装置である。
【００１９】
２は経路探索手段であって，始点から終点にいたる最適経路を求める経路探索をするものである。
３は正方格子ビア設定手段であって，正方格子上の任意の位置にビアを発生するものである。
【００２０】
４はビアグループ１設定手段であって，正方格子上のビアグループ１にビアを発生するものである。例えば，正方格子上において，千鳥パターン１でビアを発生させるものである。
【００２１】
５はビアグループ２設定手段であって，正方格子上のビアグループ１と異なるビアグループ２にビアを設定するものである。ビアグループ２は，例えば千鳥パターンであり，千鳥パターン１に対して，正方格子上で１つ格子点のずれた千鳥パターン２である。
【００２２】
６は制約条件判定手段であって，ビアどうしの間隔が制約条件を満たしているか，あるいは満たしていないかを判定するものである。
図１ (b)は図１(a) の構成の動作のフローチャートである。
【００２３】
図１ (b)を説明する前に，図２，図３により本発明の基本構成を概念的に説明する。
図２は本発明のビアグループの例であって，千鳥パターンの例を示す。
【００２４】
図２において，○は正方格子上に配置されるビアを表す。番号１のビアは千鳥パターン１のビアグループ１である。番号２のビアは千鳥パターン２のビアグループ２である。
【００２５】
以下，ビアグループ１は千鳥パターン１であり，ビアグループ２は千鳥パターン２である場合を例として，本発明を説明する。
図３は本発明の基本構成の動作説明である。
【００２６】
図３ (a)において，２１はビアＡである。２２はビアＢである。２３は線分であって，ビアＡに接続される線分である。２４は線分であって，ビアＡとビアＢの間に配線されているものである。２５は線分であって，ビアＢに接続されるものである。図３ (a)はビアＡとビアＢがビア間隔の制約条件を満たしていない。
【００２７】
図３ (b)はビアグループ１（千鳥パターン１）のビアの配置を示す。
図３ (b)において，ビアＡ（２１），ビアＣ，ビアＤ，ビアＥは，千鳥パターン１のビアである。３０は表面が配線禁止領域である領域である。
【００２８】
ビアＥは最適経路を与えるビアであるが，表面が配線禁止領域３０のために，ビアＥを配置できない。そのため，千鳥パターン１では最適経路が求まらないことを示す。
【００２９】
図３ (c)はビアグループ１と異なるビアグループ２（千鳥パターン２）によりビアを求める場合を示す。
ビアＦ（２８），ビアＧ，ビアＨ，ビアＩは千鳥パターン２のビアグループである。ビアＦは最適経路を与えるものである。２９は裏の配線であって，ビアＡ（２１）とビアＦ（２８）を裏で接続する配線である。
【００３０】
千鳥パターン１で最適経路のビアが求まらなかったので，千鳥パターン２によりビアを求める。その結果，ビアＦ（２８）により最適経路を求めることができる。
【００３１】
従来の自動配線装置では，千鳥パターン１上のビアしか取ることができなかったので，ビアＥが取れない時には配線経路が求まらなかった。そのような場合にも，本発明によれば，千鳥パターン２のビアにより最適経路を求めることができる。
【００３２】
図１ (b)により，図１ (a)の本発明の基本構成の動作を説明する。
Ｓ１  任意の正方格子上のビア位置で経路探索をする（例えば，図３のビアＡに対してビアＢを求める）。
【００３３】
Ｓ２，Ｓ３  ビアどうしの間隔の制約条件を判定する。制約条件を満たしていれば処理を終了する。満たしていなければＳ４の処理をする。
Ｓ４  Ｓ１で求めたビアがビアどうしの間隔の制約条件を満たしていなかったのでビアグループ１で経路探索をする。
【００３４】
Ｓ５，Ｓ６  最適経路が求まったか判定する。求まれば，処理を終了する。求まらなければＳ７の処理をする。
Ｓ７  ビアグループ１のビアで最適経路が求まらなかったので，ビアグループ２で経路探索をする。
【００３５】
本発明によれば，ビアを正方格子上の任意位置のビアにより配線を求めることができる。そして，正方格子上のビアが制約条件を満たさない時にのみ，ビアグループ１で最適経路を求めることができる。さらに，ビアグループ１で最適経路が求まらなかった時にはビアグループ２で経路探索ができるので，配線自由度が高くなり最適配線を能率的に求めることができる。
【００３６】
【発明の実施の形態】
図４は本発明の装置構成の実施の形態である。
図４において，
４１は正方格子ビア設定部であって，正方格子上にビアを発生するものである。
【００３７】
４２はビアグループ１設定手段であって，正方格子上に千鳥パターン１にビアを発生するものである。
４３はビアグループ２設定手段であって，正方格子上に千鳥パターン２にビアを発生するものである。
【００３８】
４４は経路探索部であって，配線情報に従って配線経路（始点と終点）を求めるものである。
４５は制約条件判定部であって，求めた配線経路についてビアどうしの間隔，線分どうしの間隔等が所定の制約条件を満たしているか，いないかを判定するものである。
【００３９】
４６は経路情報保持部であって，配線するための配線情報（経路探索の始点，終点等）を保持するものである。
５１は配線データ保持装置であって，部品の形状，大きさ等のデータ，線分の種類，幅等のデータを保持するものである。
【００４０】
５３は部品データ保持部であって，部品の形状，大きさ等のデータを保持するものである。
５４は線分データ保持部であって，線分の幅，種類等のデータを保持するものである。
【００４１】
８９は出力装置である。
９０は入力装置である。
図４の構成の動作を説明する。
【００４２】
配線情報が入力装置９０により与えられ，経路情報保持部４６に保持される。経路探索部４４は部品データ，配線データおよび配線情報に従って，配線経路を求める。その時，ビアが必要な時は正方格子ビア設定部４１により必要な位置にビアを設定する。そして，経路探索部４４は経路探索をして最適経路を求める。制約条件判定部４５は求めた最適経路のビアが制約条件をみたしているか，あるいは満たしていないかを判定する。制約条件を満たしていれば，求めた最適経路を出力する。また，正方格子上に取ったビアがビアどうしの間隔の制約条件を満足していなければ，ビアグループ１設定手段４２は，千鳥パターン１にビアを配置し，配線経路を求める。そして，経路探索部４４は，千鳥パターン１のビアにより最適経路を求める。そして，最適経路が求まれば最適経路を出力する。千鳥パターン１で最適経路が求まらない時は，ビアグループ２設定手段４３は千鳥パターン２にビアを配置する。そして，経路探索部４４は千鳥パターン２のビアにより最適配線経路を求める。最適経路が求まれば，その配線を出力する。千鳥パターン２で最適経路が求まらなければ，対象とする経路を求める処理を終了する。そして，次の配線の経路探索をする。
【００４３】
図５は本発明のシステム構成の実施の形態である。
図５において，
６１はコンピュータである。
【００４４】
６２はＣＰＵである。
６３はメモリである。
６４はメモリにロードされた自動配線プログラムを表す。
【００４５】
６５はメモリにロードされた部品データを表す。
６６はメモリにロードされた線分データを表す。
６７は配線情報であって，メモリにロードされた配線情報を表す。
【００４６】
８０は記憶媒体であって，自動配線プログラムを記憶したものであり，フロッピーディスク等の磁気記憶媒体，ＣＤＲＯＭ等の光記憶媒体，あるいはその他の試験プログラムを記憶することのできる記憶媒体である。
【００４７】
８１は自動配線プログラムである。
８２は正方格子設定プログラムである。
８３はビアグループ１設定プログラムである。
【００４８】
８４はビアグループ２設定プログラムである。
８５は経路探索プログラムである。
８６は制約条件プログラムであって，制約条件を判定するプログラムである。
【００４９】
８７は記憶媒体ドライブ装置であって，記憶媒体８０に記憶されている試験プログラムをコンピュータ６１にロードするものである。
９０は入力装置であって，配線情報等を入力するキーボード，マウスあるいは配線情報を記憶する磁気ディスク装置等の外部記憶装置である。
【００５０】
９１はディスプレイであって，配線等を表示出力するものである。
９２はプリンタであって，配線等を印刷出力するものである。
９４は外部記憶装置であって，磁気ディスク装置等であり，求めた配線を保持するものである。
【００５１】
図６は本発明の装置構成の実施の形態のフローチャートである。
Ｓ１  正方格子上にビアを設定する。
Ｓ２  配線をする。
【００５２】
Ｓ３，Ｓ４  ビアの間隔が制約条件を満たしているか判定する。満足していれば求めた配線を出力し，処理を終了する。満足していなければＳ５の処理を行う。
【００５３】
Ｓ５  千鳥グループ１のビアを設定する。
Ｓ６  千鳥グループ１のビアにより配線する。
Ｓ７  経路が求まったか判定する。求まれば配線を出力し，処理を終了する。求まらなければＳ８の処理をする。
【００５４】
Ｓ８  ビアグループ２（千鳥パターン２）にビアを設定する。
Ｓ９  配線する。経路が求まれば配線を出力して処理を終了する。求まらなければ処理を終了する。
【００５５】
図７，図８により本発明で求めた配線の実施の形態を説明する。
図７において，
２１はビアＡである。
【００５６】
２２はビアＢである。
２３は線分である。
２９はビアＡとビアＢを結ぶ裏の配線である。
【００５７】
図７ (a)は正方格子上に求めたビアで配線が求まり，かつビアＡとビアＢの間隔が規定を満足しているものである。
図７ (b)は正方格子上に求めたビアで配線が求まったが，ビアＡとビアＢの間隔が制約条件を満足していないものである。このような場合には，次に千鳥パターン１のビアで経路探索をする（図７ (c)参照）。
【００５８】
図７ (c)はグループ１設定部（千鳥パターン１）のビアで経路が求まった例である。
図８はビアグループ１（千鳥パターン１）とビアグループ２（千鳥パターン２）で経路が求まった例である。
【００５９】
図８において，
２１はビアＡであって，千鳥パターン１のビアである。
２２はビアＢであって，千鳥パターン２のビアである。
【００６０】
２３は線分である。
２９はビアＡとビアＢを結ぶ裏の配線である。
２２１はビアＣであって，ビアグループ２のビアである。
【００６１】
２２２はビアＤであって，ビアグループ２のビアである。
２２３は線分である。
２２９は裏の配線であって，ビアＣとビアＤを結ぶ線分である。
【００６２】
図８は千鳥パターン１のビアでビアＡとビアＢにより一部の配線が求まった。しかし，千鳥パターン１のビアでは求まらなかった配線があったので，さらに千鳥パターン２のビアで経路探索し，ビアＣとビアＤにより配線経路が求まった例を示す。
【００６３】
【発明の効果】
本発明によれば，正方格子上の任意の位置ビアを配置して経路探索ができ，さらにビアグループ１とビアグループ２でも経路探索できるので，配線自由度が高くなり最適配線を能率的に求めることができる。
【図面の簡単な説明】
【図１】本発明の基本構成を示す図である。
【図２】本発明のビアグループの例を示す図である。
【図３】本発明の基本構成の動作説明図である。
【図４】本発明の装置構成の実施の形態を示す図である。
【図５】本発明のシステム構成の実施の形態を示す図である。
【図６】本発明の実施の形態のフローチャートを示す図である。
【図７】本発明の実施の形態を示す図である。
【図８】本発明の実施の形態を示す図である。
【図９】従来の技術の説明図である。
【図１０】発明が解決しようとする課題の説明図である。
【符号の説明】
１：自動配線装置
２：経路探索手段
３：正方格子ビア設定手段
４：ビアグループ１設定手段
５：ビアグループ２設定手段
６：制約条件判定手段
【図１】
0003569433.tif 000002
【図２】
0003569433.tif 000003
【図３】
0003569433.tif 000004
【図４】
0003569433.tif 000005
【図５】
0003569433.tif 000006
【図６】
0003569433.tif 000007
【図７】
0003569433.tif 000008
【図８】
0003569433.tif 000009
【図９】
0003569433.tif 000010
【図１０】
0003569433.tif 000011