JPH07249055A - 自動配線装置、及び自動配線方法 - Google Patents

Abstract

(57)【要約】 【目的】 本発明は自動配線装置、及び自動配線方法に
関し、トレースをモデルとした自動配線を行う場合に、
トレースのデータ量を削減し、経路探索時間を短縮する
ことを目的としている。 【構成】 経路探索の始点、終点とならないデータに対
して新規トレースを発生させず、必要なトレースのみを
発生させるトレース計算部１４と、マッピング部１５
と、経路探索を行う経路処理部１６とを設け、経路を決
定する際、基本トレース上に存在しない禁止データ等
が有る場合、新規トレースを発生させないで経路探索を
行う。配線対象外の端子が存在した場合、新規トレー
スを発生させない経路探索を行う。配線対象の端子で
あっても、端子形状内部に基本トレースが存在する場合
は、一時的に新規トレースを発生させないで経路探索を
行うように構成する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、ＬＳＩ、ＶＬＳＩ等の
半導体集積回路、或いはプリント基板の自動配線を行う
自動配線装置等に利用されるものであり、特に、トレー
スをモデルとして自動配線を行う際の自動配線装置、及
び自動配線方法に関する。

【０００２】近年、例えば、ＬＳＩ、ＶＬＳＩ等の半導
体集積回路においては、集積度の向上や、大規模化が進
んでいる。これに伴って、自動配線装置では、基板上に
パターンを形成する配線設計の処理時間が急速に増大し
ている。また、処理するデータ量が増大していることか
ら、必要メモリ量も大幅に増大している。

【０００３】このため、自動配線装置で処理するデータ
量を減らして、自動配線処理の処理時間を短縮し、かつ
必要とするメモリ容量を削減することが要望されてい
た。

【０００４】

【従来の技術】図７は従来技術の説明図であり、Ａ図は
基本トレース、Ｂ図は新規トレースを示す。図７中、５
は基本トレース、６は端子、７はビア（ビアホール）、
８は既配線パターン、１０は新規トレースを示す。

【０００５】従来、ＬＳＩ、ＶＬＳＩ等の半導体集積回
路、或いはプリント基板に対して、自動配線を行う場合
に、例えば、自動配線装置が使用されていた。この自動
配線装置では、各種の方法で自動配線を行っていたが、
その内、トレースをモデルとして経路決定を行うこと
で、自動配線を行う自動配線装置が知られていた。

【０００６】以下、前記トレースをモデルとして自動配
線を行う自動配線装置の例について説明する。なお、以
下の説明では、入力データを基に、物理的な配線パター
ンを発生させることを自動配線という。

【０００７】この場合、配線対象の回路が決まり、必要
な端子や、どの端子間を繋ぐか等は既に決まっていて、
これらのデータ（基本トレース、既配線パターン、端子
等の設計データ）を前記入力データとして自動配線を行
うものである。

【０００８】なお、前記のように、入力データを基に、
物理的な配線パターンをどのようにして発生させるかと
いう問題は、一般的に配線問題とよばれている。ところ
で、前記自動配線装置では、自動配線を行う場合、前記
入力データに含まれる基本トレース等の設計データを基
に配線を行うが、基本トレースだけでは足らない場合、
トレース計算を行って、新規トレースを発生させる。

【０００９】その後、前記基本トレース、及び新規トレ
ースを基に、マッピングを行い、ネットを選択して経路
探索（経路：端子と端子を繋ぐ接続パターン）を行うこ
とで、自動配線を行う。

【００１０】この場合、従来の自動配線装置では、配線
対象（これから引こうとする配線）、及び障害物（既配
線パターン、禁止領域等）となる全てのデータを、トレ
ースで表現していた。以下、基本トレースと、新規トレ
ースについて説明する。

【００１１】 §１：基本トレースの説明・・・図７のＡ図参照 基本トレースは、予め設計規則として定義されたトレー
スであり、自動配線を行う場合は、この基本トレースを
入力データとして処理を行う。

【００１２】図７のＡ図では、トレースモデルの基本ト
レース５を、点線で示してある。この場合、基本トレー
ス５は縦方向と、横方向の点線で示したように設定され
ていて（格子状）、配線パターンを発生させる時に、配
線パターンがどこを通るか（経路）を示している。

【００１３】また、前記基本トレース上には、端子６、
ビア７、既配線パターン８等が存在している。図の矩形
で示した部分は、端子の物理的な大きさを示している。
これらのデータは全て入力データとして与えられる。な
お、基本トレースは、必ずしも等間隔である必要はな
い。

【００１４】 §２：新規トレースの説明・・・図７のＢ図参照 自動配線を行う場合、前記基本トレースを使用して、端
子と端子の間に配線パターンを発生させる。この時、端
子からの引き出し線は、必ず、端子の中心を通ることが
必要である。

【００１５】しかし、実際には、端子のピッチ等が多種
類であり、そのため基本トレースが端子の中心にのらな
いことがある。端子の中心に基本トレースがのらなくて
も、端子からの引き出しパターンは、必ず端子の中心を
通らなければならない。そのため、端子の中心を通るト
レースを新規に発生させることが必要になる。

【００１６】図７のＢ図では、端子６の中心を通る新規
トレース１０を発生させた例を示している。以降、この
新規トレースと、基本トレースを使用して配線を行う。
以上のように、基本的には基本トレース上で配線を行う
が、端子の中心を通る基本トレースがない場合は、前記
のように端子の中心を通る新規トレースを発生させて配
線を行う。

【００１７】

【発明が解決しようとする課題】前記のような従来のも
のにおいては、次のような課題があった。 (1) ：従来の自動配線装置では、配線対象、及び障害物
となる全てのデータを、トレースで表現していたので、
トレースのデータ量が増大する。このため、配線時間が
長くなり、かつ必要とするメモリ容量が増大していた。

【００１８】(2) ：従来のトレースをモデルとした自動
配線方法では、基板上の全てのデータがトレースで表現
されている必要がある。このため、近年のように、様々
なピッチを持つ表面実装部品が多数実装されている基板
においては、その端子を表現するために、元々基板に定
義されていた基本トレース以外に、端子の中心を通る新
規トレースを発生させる必要がある。

【００１９】このため、トレース数が急激に増加する。
これは、予め人手で入力されたプリアサインデータ（既
配線パターン）や禁止データについても同様である。従
って、前記のように、配線時間が長くなり、かつ必要と
するメモリ容量が増大していた。

【００２０】本発明は、このような従来の課題を解決
し、ＬＳＩ、ＶＬＳＩ等の半導体集積回路、或いはプリ
ント基板の自動配線において、トレースをモデルとする
場合に、経路探索の実質的な始点、終点とならないデー
タに対しては、それらのデータを表現するための新規ト
レースを発生させないことにより、トレースのデータ量
を削減し、経路探索時間を大幅に短縮することを目的と
している。

【００２１】また、本発明は、前記自動配線を行うため
のトレースを削減することにより、必要とするメモリ容
量を少なくすることを目的としている。

【００２２】

【課題を解決するための手段】図１は本発明の原理説明
図であり、図１中、１１はメモリ、１２は制御部、１４
はトレース計算部、１５はマッピング部、１６は経路処
理部を示す。

【００２３】本発明は前記の目的を達成するため、ＶＬ
ＳＩ、ＬＳＩ等の半導体集積回路、或いはプリント基板
の自動配線を行う自動配線装置に、設計データ等を格納
したり、配線処理を行う際にワーク用として使用するメ
モリ１１と、全体の制御を行う制御部１２と、基本トレ
ース以外のトレースを発生させるか否かを判断し、必要
ならばトレースを発生させるトレース計算部１４と、マ
ッピング処理を行うマッピング部１５と、トレースを基
に、ネットを選択して経路の探索を行い、探索した結果
のネットを登録する経路処理部１６等を設けた。

【００２４】

【作用】前記構成に基づく本発明の作用を、図１に基づ
いて説明する。前記自動配線装置は、トレースをモデル
として自動配線を行うものであり、前記トレースを用い
て経路決定をする際、次のようにして処理を行う。

【００２５】(1) ：基本トレース上に存在しない既配線
パターンや、禁止データが有る場合、トレース計算部１
４では、新規トレースを発生させないで、実座標のまま
メモリ１１に記憶しておき、マッピング部１５がマッピ
ングを行う。すなわち、基本的に経路探索の始点、終点
とならないデータに対しては、新規トレースを発生させ
ないで、全て実座標のまま記憶しておく。

【００２６】前記経路探索の始点、終点とならないデー
タは、経路探索しているネットの障害物として認識でき
れば良い。そして、障害物を基本トレース上に反映させ
るマッピング処理において、マッピングデータを計算す
る。前記マッピング処理では、計算で求めたマッピング
領域内に存在する全ての基本トレース交点に、障害物と
してのデータを発生させる。

【００２７】このようにすれば、マッピングされたデー
タにより、経路探索しているネットの障害物として認識
できる。また、この処理では、新規トレースを発生させ
ないので、トレースが削減でき、自動配線におけるデー
タ圧縮の効果がある。

【００２８】(2) ：配線対象外の端子がある場合、既配
線パターン、禁止データと同様に、トレース計算部１４
では新規トレースを発生させないで、実座標のままメモ
リ１１に記憶しておき、マッピング部１５がマッピング
を行う。

【００２９】このマッピング処理では、前記のようにマ
ッピングデータの計算を行って、マッピングすべき領域
を求め、このマッピングすべき領域内の基本トレース上
にマッピングされたデータを発生させる。

【００３０】このようにすれば、マッピングされたデー
タにより、経路探索しているネットの障害物として認識
できる。また、この処理では、新規トレースを発生させ
ないので、トレースが削減でき、自動配線におけるデー
タ圧縮の効果がある。

【００３１】(3) ：配線対象の端子であっても、端子形
状内部に基本トレースが存在する場合には、トレース計
算部１４は、一時的に新規トレースを発生させない。そ
して、経路処理部１６が経路探索を行う。

【００３２】このような場合、一時的に新規トレースを
発生させず、端子の中心に一番近い基本トレースを選択
し、前記基本トレースを用いて経路探索を行う。その
後、経路探索が終了したら、新規トレースを発生させ、
それに合わせてパターン形状を多少変更すれば、自動配
線ができる。

【００３３】以上のように、一時的に新規トレースを発
生させずに、基本トレースを使用して経路探索を行うこ
とにより、新規トレースの削減と、処理時間の短縮が可
能になる効果がある。

【００３４】(4) ：基本トレースの間隔がある程度大き
い場合には、マッピングすべき領域内に１つも基本トレ
ースの交点を含まない場合が存在する。このような場合
には、強制的に最寄りの基本格子上にマッピングデータ
を生成する。これは、マッピングすべき領域（データ）
を横切るような違反パターンの発生を禁止するためであ
る。

【００３５】このようにすれば、マッピングすべき領域
内には、新規トレースを発生させることなく、マッピン
グすべき領域を横切る違反パターンの発生を禁止するこ
とができる。また、新規トレースを発生させないので、
自動配線におけるデータの圧縮効果がある。

【００３６】(5) ：以上のように、ＬＳＩ、ＶＬＳＩ等
の半導体集積回路、或いはプリント基板の自動配線にお
いて、トレースをモデルとする場合に、経路探索の実質
的な始点、終点とならないデータに対しては、それらの
データを表現するための新規トレースを発生させないこ
とにより、トレースデータを削減し、経路探索時間を大
幅に短縮することが可能となる。

【００３７】また、前記のように、トレースデータを削
減することにより、必要とするメモリ容量を少なくする
ことが可能となる。

【００３８】

【実施例】以下、本発明の実施例を図面に基づいて説明
する。図２〜図６は、本発明の実施例を示した図であ
り、図２〜図６中、図１、図７と同じものは、同一符号
で示してある。また、１３は入力部、１７は出力部、２
０は端子中心トレースチェック部、２１は端子内部トレ
ースチェック部、２２はトレース発生部、２３はオフグ
リッドデータマッピング部、２４はトレースデータマッ
ピング部、２５は強制マッピング部、２６はネット選択
部、２７は経路探索部、２８はネット登録部、３１はマ
ッピングされた線分、３２はマッピングすべき領域、３
３は配線に使用する基本トレース交点、３４は配線、３
５はマッピングすべきデータ、３６は強制的にマッピン
グされた線分を示す。

【００３９】本実施例は、自動配線装置により、ＬＳ
Ｉ、ＶＬＳＩ等の半導体集積回路、或いはプリント基板
の自動配線を行う例である。この自動配線装置による自
動配線では、できるだけ新規トレースを発生しないで、
すなわちトレースのデータ量を削減して自動配線を行う
ものである。以下、詳細に説明する。

【００４０】§１：自動配線装置の説明・・・図２参照 図２は自動配線装置のブロック図である。以下、図２に
基づいて、本実施例の自動配線装置を説明する。

【００４１】この自動配線装置は、メモリ１１、制御部
１２、入力部１３、トレース計算部１４、マッピング部
１５、経路処理部１６、出力部１７等で構成されてい
る。そして、前記トレース計算部１４には、端子中心ト
レースチェック部２０、端子内部トレースチェック部２
１、トレース発生部２２が設けてある。

【００４２】また、マッピング部１５には、オフグリッ
ドデータマッピング部２３、トレースデータマッピング
部２４、強制マッピング部２５が設けてある。更に、前
記経路処理部１６には、ネット選択部２６、経路探索部
２７、ネット登録部２８が設けてある。前記各部の機能
等は次の通りである。

【００４３】(1) ：メモリ１１は、自動配線処理に必要
な各種のパターンデータ、設計データ等を格納したり、
自動配線処理の途中のデータ等を格納するメモリであ
る。なお、前記各データは、自動配線処理を行う際に予
め用意されたファイル内のデータを読み出して、メモリ
１１に格納する。

【００４４】以降、自動配線装置では、制御部１２の制
御により、メモリ１１内のデータを読み出して自動配線
処理を行う。また、このメモリ１１には、各部が処理し
たデータ（処理途中のデータ）も格納しておく。

【００４５】(2) ：制御部１２は、自動配線装置全体の
制御を行うものである。すなわち、制御部１２は、入力
部１３、トレース計算部１４、マッピング部１５、経路
処理部１６、及び出力部１７に対して、各種の制御を行
い、自動配線処理を行う。

【００４６】(3) ：入力部１３は、制御部１２の制御に
より、処理に必要なデータをメモリ１１から読み出し
て、入力する処理を行うものである。 (4) ：トレース計算部１４は、制御部１２の制御によ
り、基本トレース以外のトレースを発生させるか否かを
判断し、必要ならばトレースを発生させるものである。

【００４７】この場合、端子中心トレースチェック部２
０では、端子の中心を通る基本トレースが存在するか否
かをチェックし、端子内部トレースチェック部２１で
は、端子内部に基本トレースがあるか否かをチェックす
るものである。

【００４８】そして、前記のチェック結果に基づいて、
新規トレースを発生させる必要があると判断した場合に
は、トレース発生部２２が新規トレースを発生させる。
なお、前記処理結果のデータはメモリ１１に格納してお
く。

【００４９】(5) ：マッピング部１５は、トレース上に
存在しないデータに起因する禁止情報等を、新規トレー
スにマッピングする処理を行う。また、そのマッピング
部１５は、新規トレース上のデータに対してマッピング
をしたり、必要な場合には、強制的にマッピングをした
りするものである。

【００５０】この場合、オフグリッドデータマッピング
部２３では、基本トレース上に無いデータに対してマッ
ピングを行い、トレースデータマッピング部２４では、
新規トレース上のデータに対してマッピングを行う。

【００５１】また、前記強制マッピング部２５では、基
本トレースのどこにもマッピングされないデータに対
し、強制的にマッピングを行う。なお、前記処理結果の
データはメモリ１１に格納しておく。

【００５２】(6) ：経路処理部１６は、マッピングした
後、前記トレースを基に、ネットを選択して経路の探索
を行い、探索した結果のネットを登録するものである。
この場合、ネット選択部２６では、必要なネットの選択
を行い、経路探索部２７では、配線パターンの経路をト
レース上で探索し、ネット登録部２８では、探索した結
果のネットの登録を行う。この登録は、メモリ１１内の
データに対して行う。なお、前記処理結果のデータはメ
モリ１１に格納しておく。

【００５３】(7) ：出力部１７は、前記各部で処理した
結果のデータをメモリ１１から読み出して出力するもの
である。 §２：フローチャートによる全体の処理説明・・・図３
参照 図３は自動配線処理フローチャートである。以下、図３
に基づいて、前記自動配線装置における自動配線処理
（全体の処理）を説明する。なお、Ｓ１〜Ｓ１０は各処
理ステップを示す。

【００５４】(1) ：先ず、入力部１３がメモリ１１から
データを読み出してトレース計算部１４へ送る（Ｓ
１）。そして、トレース計算部１４は、入力したデータ
を基に、基本トレース以外のトレースを発生させるか否
かを判断し、必要ならばトレース計算を行って新規トレ
ースを発生させる（Ｓ２）。

【００５５】なお、新規トレースを発生させる基準は、
繰り返し最終（つまり、データが出力部１７から出力さ
れる直前）であれば、端子の中心、そうでなければ、端
子の内部に基本トレースがあるか否かを判断し、前記基
本トレースが無ければ新規トレースを発生させる。

【００５６】この場合、端子の中心に基本トレースが有
るか否かの判断は、端子中心トレースチェック部２０
が、端子の中心に基本トレースが有るか否かをチェック
することで判断する。また、端子内部に基本トレースが
有るか否かの判断は、端子内部トレースチェック部２１
が、端子内部に基本トレースが有るか否かをチェックす
ることで判断する。

【００５７】以上の処理により、最初に入力された基本
トレースと、前記の処理で発生した新規トレースとを合
わせて、経路探索に必要なトレースが揃うことになる。 (2) ：次に、マッピング部１５によりマッピングを行う
（Ｓ３）。この場合、マッピング部１５は、トレース上
に存在しないデータに起因する禁止情報等を、新規トレ
ースにマッピングする処理を行う。また、そのマッピン
グ部１５は、新規トレース上のデータに対してマッピン
グをしたり、必要な場合には、強制的にマッピングをし
たりする。

【００５８】(3) ：次に経路処理部１６は、前記トレー
スを基に、ネットを選択して（Ｓ４）、経路の探索を行
い（Ｓ５）、探索した結果のネットをメモリ１１に登録
する（Ｓ６）。この処理を、全ネットが終了するまで繰
り返して行い（Ｓ７）、前記ネットについて処理が終了
すると、繰り返し終了したか否かを判断する（Ｓ８）。

【００５９】その結果、繰り返し終了していなければ、
繰り返し最終（データが出力部から出力される直前）か
否かを判断する（Ｓ９）。その結果、繰り返し最終でな
ければ、Ｓ４に戻って処理を行い、繰り返し最終であれ
ば、前記Ｓ２に戻って処理を行う。

【００６０】(4) ：前記Ｓ８の処理で、繰り返し終了と
判断した場合には、出力部１７から処理結果を出力し
（Ｓ１０）、処理を終了する。 §３：フローチャートによるトレース計算部部の処理説
明・・・図４参照 図４はトレース計算部の処理フローチャートである。以
下、図４に基づいて、前記自動配線装置におけるトレー
ス計算部の処理を説明する。なお、Ｓ２１〜Ｓ２６は各
処理ステップを示す。

【００６１】先ず、トレース計算部１４では、任意の端
子を選択し（Ｓ２１）、端子終了か否かを判断する（Ｓ
２２）、その結果、端子終了であれば、トレース計算処
理を終了するが、端子終了でなければ繰り返し終了（デ
ータが出力部１７から出力される直前、すなわち、経路
探索の最終）であるか否かを判断する（Ｓ２３）。

【００６２】その結果、繰り返し終了でなければ、端子
内部トレースチェック部２１は、端子の内部に基本トレ
ースがあるか否かを判断し（Ｓ２５）、基本トレースが
あれば、Ｓ２１に戻って処理を行う。しかし、端子の内
部に基本トレースがなければ、端子の中心を通るトレー
スを発生させ（Ｓ２６）、Ｓ２１に戻って処理を行う。

【００６３】また、Ｓ２３の処理で、繰り返し終了であ
ると判断した場合は、端子中心トレースチェック部２０
が、端子の中心を通る基本トレース、或いは新規トレー
スが有るか否かをチェックする（Ｓ２４）。

【００６４】その結果、端子の中心を通る基本トレー
ス、或いは新規トレースが有れば、前記Ｓ２１に戻って
処理を行うが、端子の中心を通る基本トレース、或いは
新規トレースが無ければ、端子の中心を通る新規トレー
スを発生させ（Ｓ２６）、前記Ｓ２１に戻って処理を行
う。

【００６５】§４：既配線パターン、禁止データのマッ
ピング処理の説明・・・図５のＡ図参照 図５のＡ図は、既配線パターン、禁止データのマッピン
グ処理を示した図である。なお、図５のＡ図では、端子
６、ビア７、既配線パターン８が図示のように存在する
（この点は前記従来例と同じ）例を示している。この場
合、既配線パターン８は、基本トレース（図示点線部
分）５上に存在しない例である。

【００６６】この処理では、基本トレース上に存在しな
い既配線パターンや、禁止データが有る場合、新規トレ
ースを発生させないで、実座標のままメモリ１１に記憶
しておき、マッピングを行う。

【００６７】すなわち、基本的に経路探索の始点、終点
とならないデータ（例えば、図５のＡ図に示した既配線
パターン）に対しては、新規トレースを発生させない
で、全て実座標のまま記憶しておく（そのまま記憶して
おく）。

【００６８】前記経路探索の始点、終点とならないデー
タは、経路探索しているネットの障害物として認識でき
れば良い。そして、障害物を基本トレース上に反映させ
るマッピング処理において、マッピングデータを計算す
る。前記マッピング処理では、計算で求めたマッピング
領域内に存在する全ての基本トレース交点に、障害物と
してのデータを発生させる。

【００６９】この場合、マッピング領域の計算式は、
（マッピングしようとしているデータの実サイズ）＋
（経路探索中のネットの線幅／２）＋（設計規則で定義
されたクリアランス）で示される。

【００７０】なお、図５のＡ図の例では、前記マッピン
グしようとしているデータの実サイズは、既配線パター
ン８の実サイズ（線幅）である。前記のようにマッピン
グデータの計算を行って、マッピングすべき領域３２を
求め、このマッピングすべき領域３２内の基本トレース
上にマッピングされた線分３１を引く。

【００７１】このようにすれば、マッピングされた線分
３１により、経路探索しているネットの障害物として認
識できる。また、この処理では、新規トレースを発生さ
せないので、トレースが削減でき、自動配線におけるデ
ータ圧縮の効果がある。

【００７２】§５：配線対象外の端子のマッピング処理
の説明・・・図５のＢ図参照 図５のＢ図は、配線対象外の端子のマッピング処理を示
した図である。なお、図５のＢ図では、配線対象外の端
子６が図示のように存在する例を示している。この場
合、配線対象外の端子６は、基本トレース（図示点線部
分）５上に存在しない例である。

【００７３】この場合も、前記既配線パターン、禁止デ
ータと同様に、新規トレースを発生させないで、実座標
のままメモリ１１に記憶しておき、マッピングを行う。
このマッピング処理では、前記のようにマッピングデー
タの計算を行って、マッピングすべき領域３２を求め、
このマッピングすべき領域３２内の基本トレース上にマ
ッピングされた線分３１を引く（線分データを発生させ
る）。

【００７４】このようにすれば、マッピングされた線分
３１により、経路探索しているネットの障害物として認
識できる。また、この処理では、新規トレースを発生さ
せないので、トレースが削減でき、自動配線におけるデ
ータ圧縮の効果がある。

【００７５】§６：配線対象端子の端子形状内部に基本
トレースが存在する場合の処理の説明・・・図６のＡ図
参照 図６のＡ図は、配線対象端子の経路探索処理の説明図で
ある。なお、図６のＡ図では、配線対象の端子６が図示
のように存在し、かつ、前記端子６の端子形状内部に基
本トレース５が存在する例である。

【００７６】この例は、配線対象の端子を、最寄りの基
本トレース上にマッピングした例である。この場合、最
終的には、端子の中心を通る配線パターンを発生させる
必要がある。

【００７７】従って、全ネットの経路探索において、最
後の１回だけは、端子の中心を通る新規トレースを発生
させて配線する。これは、現在よく用いられている繰り
返し経路探索を行う処理において有効である。以下、詳
細に説明する。

【００７８】この処理では、配線対象の端子であって
も、端子形状内部に基本トレースが存在する場合には、
一時的に新規トレースを発生しないで経路探索を行う。
すなわち、一般的に、端子６の形状は基本トレースの幅
に比べて大きい。従って、端子形状内部には、端子の中
心を通る基本トレースが無くても、それに近い位置の基
本トレースが存在することがある。

【００７９】このような場合、一時的に新規トレースを
発生させず、端子の中心に一番近い基本トレースを選択
（配線に使用する基本トレース交点３３を選択）し、前
記基本トレースを用いて経路探索を行う。その後、経路
探索が終了したら、新規トレースを発生させ、それに合
わせてパターン形状を多少変更すれば、自動配線ができ
る。

【００８０】以上のように、一時的に新規トレースを発
生させずに、基本トレースを使用して経路探索を行うこ
とにより、新規トレースの削減と、処理時間の短縮が可
能になる効果がある。

【００８１】§７：基本トレースのどこにもマッピング
されないデータを表現する場合の処理説明・・・図６の
Ｂ図参照 図６のＢ図は、強制マッピング処理の説明図である。な
お、図６のＢ図では、マッピングすべき領域３２内に、
基本トレースの交点が存在しない例を示している。

【００８２】基本トレースの間隔がある程度大きい場合
には、マッピングすべき領域内に１つも基本格子（縦横
の基本トレースの交点）を含まない場合が存在する。こ
のような場合には、図示のように、強制的に最寄りの基
本格子上にマッピングデータを生成する。これは、マッ
ピングすべき領域（データ）を横切るような違反パター
ンの発生を禁止するためである。

【００８３】この例では、マッピングすべき領域３２内
には、基本トレースの交点が存在しないので、このまま
マッピングを行わないと、経路探索の際、前記マッピン
グすべき領域３２を横切る恐れがあり、このような事態
は避ける必要がある。

【００８４】そこで、本来、マッピングすべき領域３２
内には、新規トレースを発生させることにより、マッピ
ングすべきデータ３５を発生させることが必要である
が、本実施例では、前記マッピングすべきデータ３５を
発生させずに、マッピングすべき領域３２の外側にある
基本トレース上に、強制的に線分をマッピングする。

【００８５】このようにして強制的にマッピングされた
線分３６は、前記マッピングすべき領域３２の外側であ
って、該マッピングすべき領域３２に一番近い位置にあ
る基本トレース上に引く（線分データを発生させる）。

【００８６】この場合、強制的にマッピングされた線分
３６は、マッピングすべき領域３２に対し、図の反対側
に引いても良い、いずれにしても、経路探索の時に、マ
ッピングすべき領域３２を横切ることがないように、前
記強制的にマッピングされた線分３６を発生させる。

【００８７】なお、前記強制的にマッピングされた線分
３６は、基本トレース上でなくても、既に発生済みの新
規トレース上であっても良い。以上の処理により、マッ
ピングすべき領域３２内には、新規トレースを発生させ
ることなく、マッピングすべき領域を横切る違反パター
ンの発生を禁止することができる。また、新規トレース
を発生させないので、自動配線におけるデータの圧縮効
果がある。

【００８８】

【発明の効果】以上説明したように、本発明によれば次
のような効果がある。 (1) ：ＶＬＳＩ、ＬＳＩ等の半導体集積回路、或いはプ
リント基板の自動配線において、トレースをモデルとす
る場合に、経路探索の実質的な始点、終点とならないデ
ータに対しては、それらのデータを表現するための新規
トレースを発生させないことにより、トレースのデータ
量を削減し、経路探索時間を大幅に短縮することができ
る。

【００８９】また、トレースを削減することにより、必
要とするメモリ容量を少なくすることができる。前記効
果の外に、各請求項によれば、次のような効果がある。 (2) ：前記請求項２では、基本的に経路探索の始点、終
点とならないデータに対しては、新規トレースを発生さ
せないで、全て実座標のまま記憶しておく。

【００９０】このようにすれば、マッピングされたデー
タにより、経路探索しているネットの障害物として認識
できると共に、新規トレースを発生させないので、トレ
ースが削減でき、処理の高速化、自動配線におけるデー
タ圧縮の効果がある。

【００９１】(3) ：前記請求項３では、配線対象外の端
子がある場合、新規トレースを発生させないで、実座標
のまま記憶しておき、マッピングを行う。このようにす
れば、マッピングされたデータにより、経路探索してい
るネットの障害物として認識できると共に、新規トレー
スを発生させないので、トレースが削減でき、自動配線
におけるデータ圧縮の効果がある。

【００９２】(4) ：前記請求項４では、一時的に新規ト
レースを発生させずに、基本トレースを使用して経路探
索を行うので、新規トレースの削減と、処理時間の短縮
が可能になる効果がある。

【００９３】(5) ：前記請求項５では、マッピングすべ
き領域内に１つも基本トレースの交点を含まない場合、
強制的に最寄りの基本トレース上にマッピングデータを
生成する。

【００９４】このようにすれば、マッピングすべき領域
内には、新規トレースを発生させることなく、マッピン
グすべき領域を横切る違反パターンの発生を禁止するこ
とができる。また、新規トレースを発生させないので、
自動配線におけるデータの圧縮効果がある。

【図面の簡単な説明】

【図１】本発明の原理説明図である。

【図２】実施例における自動配線装置のブロック図であ
る。

【図３】実施例における自動配線処理フローチャートで
ある。

【図４】実施例におけるトレース計算部の処理フローチ
ャートである。

【図５】実施例の処理説明図１である。

【図６】実施例の処理説明図２である。

【図７】従来技術の説明図である。

【符号の説明】

１１ メモリ １２ 制御部 １４ トレース計算部 １５ マッピング部 １６ 経路処理部

Claims (5)

【特許請求の範囲】
1. 【請求項１】 トレースをモデルとして自動配線を行う
   自動配線装置において、 経路探索の実質的な始点、終点とならないデータに対し
   ては新規トレースを発生させず、その以外の必要なトレ
   ースのみを発生させるトレース計算部（１４）と、 前記トレースを基に、禁止情報等に対してマッピング処
   理を行うマッピング部（１５）と、 前記トレースを基に、ネットを選択して経路探索を行う
   経路処理部（１６）とを有することを特徴とした自動配
   線装置。
2. 【請求項２】 トレースをモデルとして自動配線を行う
   自動配線方法において、 前記トレースを用いて経路を決定する際、 基本トレース上に存在しない既配線パターン、禁止デー
   タが有る場合、新規トレースを発生させないで経路探索
   を行うことを特徴とした自動配線方法。
3. 【請求項３】 トレースをモデルとして自動配線を行う
   自動配線方法において、 前記トレースを用いて経路を決定する際、 配線対象外の端子が存在した場合、新規トレースを発生
   させない経路探索を行うことを特徴とした自動配線方
   法。
4. 【請求項４】 トレースをモデルとして自動配線を行う
   自動配線方法において、 前記トレースを用いて経路を決定する際、 配線対象の端子であっても、端子形状内部に基本トレー
   スが存在する場合には、一時的に新規トレースを発生さ
   せないで経路探索を行うことを特徴とした自動配線方
   法。
5. 【請求項５】 トレースをモデルとして自動配線を行う
   自動配線方法において、 前記トレースを用いて経路を決定する際、 マッピングすべき領域内に、基本トレース上の交点を１
   つも含まない場合、強制的に最寄りの基本トレース上に
   マッピングデータを生成することを特徴とした自動配線
   方法。