(57)【要約】【課題】ビアの中心を迂回することなく交差を解消して配線を決定する配線決定装置等を提供すること。【解決手段】配線設計データ１０２に基づきパッド部とビア部を直線の仮配線で結び、回避対象ビア部及び回避対象配線を決定する回避対象決定部３２と、回避対象ビア部の略中心を通過する２本の補助線を掃引する補助線掃引部３３と、２本の補助線が形成する象限に対し、回避対象配線でない仮配線の、パッド部等の始点が存在する始点象限を決定する開始象限決定部３４と、回避対象ビア部の略中心から所定のクリアランスを設けて第１の回避点を決定し、始点象限と接しない他方の補助線上に、回避対象ビア部の略中心から所定のクリアランスを設けて第２の回避点を決定するクリアランス決定部３５と、始点、回避点及びビア部、を結線する結線部３６と、を有することを特徴とする。【選択図】図１
2009140221.tif 000002
【特許請求の範囲】
【請求項１】
パッド部とビア部の位置情報、互いに結線するパッド部とビア部の組を指定する配線設計データを記憶した記憶手段と、ユーザの操作を入力する入力手段と、前記記憶手段から配線設計データを読み出し前記配線設計データに基づきパッド部とビア部を直線の仮配線で結ぶ仮配線部と、を有する配線決定装置であって、
第１の仮配線と第２の仮配線との交点と第１の仮配線が結ぶ第１のビア部までの距離と、前記交点と第２の仮配線が結ぶ第２のビア部までの距離、に基づき回避対象の回避対象ビア部及び回避対象配線を決定する回避対象決定部と、
前記回避対象ビア部の略中心を通過する２本の補助線を掃引する補助線掃引部と、
前記２本の補助線が形成する象限に対し、前記回避対象配線でない仮配線の、パッド部等の始点が存在する始点象限を決定する開始象限決定部と、
前記始点象限のうち前記回避対象配線より前記始点側の領域が接する前記補助線上に、前記回避対象ビア部の略中心から所定のクリアランスを設けて第１の回避点を決定し、前記始点象限と接しない他方の前記補助線上に、前記回避対象ビア部の略中心から所定のクリアランスを設けて第２の回避点を決定するクリアランス決定部と、
前記始点、前記第１の回避点、前記第２の回避点、及び、前記回避対象ビア部でない方の第１又は第２のビア部、を前記始点から順に結線する結線部と、
を有することを特徴とする配線決定装置。
【請求項２】
前記クリアランス決定部は、前記回避対象ビア部の略中心に対し第１の回避点の反対側の前記補助線上に、第３の回避点を決定し、
前記結線部は、前記始点、前記第１の回避点、前記第２の回避点、第３の回避点、及び、前記回避対象ビア部でない方の第１又は第２のビア部、を始点から順に結線する、
ことを特徴とする請求項１記載の配線決定装置。
【請求項３】
パッド部からビア部までの配線を決定する配線決定装置の配線決定方法であって、
入力手段からユーザの操作を入力するステップと、
仮配線部が、パッド部とビア部の位置情報、互いに結線するパッド部とビア部の組を指定する配線設計データを記憶した記憶手段から配線設計データを読み出し、前記配線設計データに基づきパッド部とビア部を直線の仮配線で結ぶステップと、
回避対象決定部が、第１の仮配線と第２の仮配線との交点と第１の仮配線が結ぶ第１のビア部までの距離と、前記交点と第２の仮配線が結ぶ第２のビア部までの距離、に基づき回避対象の回避対象ビア部及び回避対象配線を決定するステップと、
補助線掃引部が、前記回避対象ビア部の略中心を通過する２本の補助線を掃引するステップと、
開始象限決定部が、前記２本の補助線が形成する象限に対し、前記回避対象配線でない仮配線の、パッド部等の始点が存在する始点象限を決定するステップと、
クリアランス決定部が、前記始点象限のうち前記回避対象配線より前記始点側の領域が接する前記補助線上に、前記回避対象ビア部の略中心から所定のクリアランスを設けて第１の回避点を決定し、前記始点象限と接しない他方の前記補助線上に、前記回避対象ビア部の略中心から所定のクリアランスを設けて第２の回避点を決定するステップと、
結線部が、前記始点、前記第１の回避点、前記第２の回避点、及び、前記回避対象ビア部でない方の第１又は第２のビア部、を始点から順に結線するステップと、
を有することを特徴とする配線決定方法。
【請求項４】
コンピュータを、
入力手段から入力されたユーザの操作に基づき、パッド部とビア部の位置情報、互いに結線するパッド部とビア部の組を指定する配線設計データを記憶した記憶手段から配線設計データを読み出し、前記配線設計データに基づきパッド部とビア部を直線の仮配線で結ぶ仮配線部と、
第１の仮配線と第２の仮配線との交点と第１の仮配線が結ぶ第１のビア部までの距離と、前記交点と第２の仮配線が結ぶ第２のビア部までの距離、に基づき回避対象の回避対象ビア部及び回避対象配線を決定する回避対象決定部と、
前記回避対象ビア部の略中心を通過する２本の補助線を掃引する補助線掃引部と、
前記２本の補助線が形成する象限に対し、前記回避対象配線でない仮配線の、パッド部等の始点が存在する始点象限を決定する開始象限決定部と、
前記始点象限のうち前記回避対象配線より前記始点側の領域が接する前記補助線上に、前記回避対象ビア部の略中心から所定のクリアランスを設けて第１の回避点を決定し、前記始点象限と接しない他方の前記補助線上に、前記回避対象ビア部の略中心から所定のクリアランスを設けて第２の回避点を決定するクリアランス決定部と、
前記始点、前記第１の回避点、前記第２の回避点、及び、前記回避対象ビア部でない方の第１又は第２のビア部、を始点から順に結線する結線部と、
として機能させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、基板上における複数のパッド部と複数のビア部をそれぞれ結線する配線決定装置等に関し、特に、配線同士の交差を、配線にビア部を迂回させて解消する配線決定装置、配線決定方法及びプログラムに関する。
【背景技術】
【０００２】
半導体パッケージにおいては、ビア部とパッド部又はビア部とビア部を、配線同士が交差せず、かつ、配線間にクリアランスが確保されるように接続する必要がある（以下、設計ルールという）。従来、このような設計は、設計者がＣＡＤシステム上で設計ルールに従うように試行錯誤しながら行っているが、設計者が自らの経験と勘を頼りに、ＣＡＤシステムを操作しながら半導体パッケージの配線を設計すると最適な配線を実現するには多大なる労力および時間を要してしまう。
【０００３】
そこで、交差を自動的に解消することができる配線決定方法が用いられるようになってきた（例えば、特許文献１参照。）。特許文献１には、順向配線（パッド部から周辺部に設けられたビア部へ向かってほぼ同一方向に配線が向く配線）でなく非順向配線（配線が大方の方向とはほぼ逆向きとなる迂回ルートを有する配線）を適用しても、設計ルールに従う配線パターンを生成する配線決定装置が記載されている。非順向配線は、外観が美しいだけでなく、製造コスト削減や電気抵抗の低減などにつながることが多く、また、温度変化や湿度変化などの外的環境要因による基板の歪みの発生を抑制しやすいとされている。
【０００４】
図１２は、従来の配線決定方法の一例を示す図である。図１２（ａ）はパッドＰ１〜Ｐ５とビアＶ１〜Ｖ５を仮配線Ｗ１〜Ｗ５により接続した配線の初期状態を示す。仮配線Ｗ１〜Ｗ５が互いに交差しているのでこれを順番に解消する。
【０００５】
仮配線Ｗ１とＷ２との交差を解消する場合を説明する。仮配線Ｗ１と仮配線Ｗ２は交点Ｑ１で交差し、交点Ｑ１とビアＶ１の距離と、交点Ｑ１とビアＶ５の距離を比較すると、後者の方が長い。特許文献１では交点までの距離が長い仮配線を迂回することで、迂回の結果生じる配線全体の長さの増加を抑制している。したがって、仮配線Ｗ１を、仮配線Ｗ２の結線先であるビアＶ１を通過する暫定配線Ｗ‘５に置き換える（図１２（ｂ））。
【０００６】
次に、仮配線Ｗ４とＷ５の交差を解消する。仮配線Ｗ４と仮配線Ｗ５は交点Ｑ２で交差し、交点Ｑ２とビアＶ３の距離と、交点Ｑ２とビアＶ２の距離を比較すると、前者の方が長い。したがって、仮配線Ｗ４を、仮配線Ｗ５の結線先であるビアＶ２を通過する暫定配線Ｗ‘４に置き換える（図１２（ｃ））。
【０００７】
次に、仮配線Ｗ３とＷ５の交差を解消する。仮配線Ｗ３と仮配線Ｗ５は交点Ｑ３で交差し、交点Ｑ３とビアＶ４の距離と、交点Ｑ３とビアＶ２の距離を比較すると、前者の方が長い。したがって、仮配線Ｗ３を、仮配線Ｗ５の結線先であるビアＶ２を通過する暫定配線Ｗ‘３に置き換える（図１２（ｄ））。
【０００８】
次に、暫定配線Ｗ‘１とＷ’４の交差を解消する。暫定配線Ｗ‘１と暫定配線Ｗ’４は交点Ｑ４で交差し、交点Ｑ４とビアＶ３の距離と、交点Ｑ４とビアＶ５の距離を比較すると、後者の方が長い。したがって、暫定配線Ｗ‘１を、暫定配線Ｗ’４の結線先であるビアＶ３を通過する暫定配線Ｗ“１に置き換える。また、このとき暫定配線Ｗ”１がパッドＰ１と結線するようビアＶ３とＶ１を暫定配線Ｗ“１で結線する（図１２（ｅ））。
【０００９】
次に、暫定配線Ｗ“１とＷ’３の交差を解消する。暫定配線Ｗ”１と暫定配線Ｗ’３は交点Ｑ５で交差し、交点Ｑ５とビアＶ４の距離と、交点Ｑ５とビアＶ５の距離を比較すると、後者の方が長い。したがって、暫定配線Ｗ“１を、暫定配線Ｗ’３の結線先であるビアＶ４を通過する暫定配線Ｗ’’’１に置き換える（図１２（ｆ））。
【００１０】
以上の処理により、図１２（ｈ）に示すように、暫定配線がビアの中央部で交差するようにして配線の交差を解消することができる。
【特許文献１】特開２００６−２６８４６２号公報
【発明の開示】
【発明が解決しようとする課題】
【００１１】
特許文献１記載の配線決定方法では、図１２（ｈ）までの処理の後クリアランスを確保するため、例えばビアＶ２に結線された暫定配線Ｗ‘３、Ｗ’４、Ｗ５をビアＶ２からずらす処理を行う。しかしながら、図１２（ｇ）に示すように、同じビアＶ２の中心を複数の暫定配線が迂回しているため、その頂点座標が一致してしまい、そもそも暫定配線同士の交差が発生しているか否かの判断が困難になるという問題がある。
【００１２】
本発明は、上記課題に鑑み、ビアの中心を迂回することなく交差を解消して配線を決定する配線決定装置、配線決定方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１３】
本発明は、上記課題に鑑み、パッド部とビア部の位置情報、互いに結線するパッド部とビア部の組を指定する配線設計データを記憶した記憶手段と、ユーザの操作を入力する入力手段と、前記記憶手段から配線設計データを読み出し前記配線設計データに基づきパッド部とビア部を直線の仮配線で結ぶ仮配線部と、を有する配線決定装置であって、第１の仮配線と第２の仮配線との交点と第１の仮配線が結ぶ第１のビア部までの距離と、交点と第２の仮配線が結ぶ第２のビア部までの距離、に基づき回避対象の回避対象ビア部及び回避対象配線を決定する回避対象決定部と、回避対象ビア部の略中心を通過する２本の補助線を掃引する補助線掃引部と、２本の補助線が形成する象限に対し、回避対象配線でない仮配線の、パッド部等の始点が存在する始点象限を決定する開始象限決定部と、始点象限のうち回避対象配線より始点側の領域が接する補助線上に、回避対象ビア部の略中心から所定のクリアランスを設けて第１の回避点を決定し、始点象限と接しない他方の補助線上に、回避対象ビア部の略中心から所定のクリアランスを設けて第２の回避点を決定するクリアランス決定部と、始点、第１の回避点、第２の回避点、及び、回避対象ビア部でない方の第１又は第２のビア部、を始点から順に結線する結線部と、を有することを特徴とする。
【００１４】
本発明によれば、回避対象ビア部の略中心から所定のクリアランスを設けて回避対象ビアを迂回するので、ビアの中心を迂回することなく交差を解消することができる。
【００１５】
また、本発明の一形態において、クリアランス決定部は、回避対象ビア部の略中心に対し第１の回避点の反対側の補助線上に、第３の回避点を決定し、結線部は、始点、第１の回避点、第２の回避点、第３の回避点、及び、回避対象ビア部でない方の第１又は第２のビア部、を始点から順に結線する、ことを特徴とする。
【００１６】
本発明によれば、回避対象ビアの周りを周回するように配線を迂回させることができるので、迂回させた配線がさらに交差することを低減できる。
【発明の効果】
【００１７】
ビアの中心を迂回することなく交差を解消して配線を決定する配線決定装置、配線決定方法及びプログラムを提供することができる。
【発明を実施するための最良の形態】
【００１８】
以下、本発明を実施するための最良の形態について、図面を参照しながら説明する。
図１は、本実施形態の配線決定方法の概略を説明する図を、図２は手順を説明するフローチャート図を示す。
【００１９】
ビアＶ１は仮配線Ｗ１により不図示のビア又はパッドと結線されており、ビアＶ２は仮配線Ｗ２により不図示のビア又はパッドと結線されている。本実施形態の配線決定方法の手順は次のようになる。
Ｓ１．配線設計データ１０２を入力する。
Ｓ２．交差があるか否かを判定し、交差がなくなるまで以降のステップを繰り返し実行する。
Ｓ１０．交点Ｑ１とビアＶ１との距離と、交点Ｑ１とビアＶ２の距離を比較し、距離が長い方の仮配線Ｗ２を迂回させる。
Ｓ２０．回避の対象となるビアＶ１に水平・垂直な補助線を引く。
Ｓ３０．仮配線Ｗ２の開始座標の、補助線に対する象限を取得する。
Ｓ４０．迂回するビアＶ１からクリアランスを保つ、補助線上の３つの所定位置（以下、回避点という）を定める。
Ｓ５０．仮配線Ｗ１の始点から３つの回避点を順に結び、最後に終点まで結線する。
【００２０】
図１（ａ）を例にすると、まず配線決定装置１００は、交点Ｑ１とビアＶ１との距離と、交点Ｑ１とビアＶ２の距離を比較し、後者の方が長いので仮配線Ｗ２を迂回させることを決定する（Ｓ１０）。
【００２１】
そして、配線決定装置１００は、図１（ｂ）に示すように、回避の対象となるビアＶ１に水平・垂直な補助線を引く（Ｓ２０）。水平・垂直な補助線は例えば基板の各辺に平行な線であるが、基板の辺と補助線になす角があってもよい。
【００２２】
また、仮配線Ｗ２の開始座標は第３象限にあり、仮配線Ｗ１と交差しないためには仮配線Ｗ１よりも開始座標側を迂回する必要があることがわかる（Ｓ３０）。したがって、回避対象の仮配線Ｗ１より始点側の領域（図１（ｂ）の斜線部）が接する補助線上、すなわち、第２象限と第３象限を区切る補助線の所定位置と仮配線Ｗ２の始点を結線すればよい。
【００２３】
次に、ビアＶ１から補助線上の３つの回避点Ｋ１〜Ｋ３を決定する（Ｓ４０）。Ｋ１〜Ｋ３の番号は結線する順番を示す。すなわち、図１（ｂ）では第２象限と第３象限を区切る補助線に回避点Ｋ１を設け、第２象限と第１象限を区切る補助線に回避点Ｋ２を設ける。回避点Ｋ１〜Ｋ３は、ビアＶ１から等距離とすることで美しい配線とすることができるが、必ずしも等距離でなくてもよい。
【００２４】
そして、仮配線Ｗ１の始点から３つの回避点Ｋ１〜Ｋ３を順に結び、最後にビアＶ２まで結線することで、図１（ｃ）に示すように仮配線Ｗ１とＷ２の交差を回避することができる（Ｓ５０）。
【００２５】
本実施形態の配線決定方法によれば、交差を解消する際、ビアの中心を通過して迂回するステップがないため、ビア上での仮配線又は暫定配線の交差判定を不要とすることができる。また、補助線を引くことにより暫定配線の頂点座標を取得しやすくなる。
【００２６】
〔配線決定装置１００の構成〕
図３は、配線決定装置１００の構成図を示す。配線決定装置１００はコンピュータとして構成される。ＣＰＵ２０は、配線決定装置１００の全体を制御する制御部であり、入力部５０から入力される入力情報に応じて配線決定装置１００の各部に命令を発信してシステム全体の動作を制御する。ＲＯＭ３０には、配線決定装置１００の設計動作プログラム１０１が記憶されている。ＲＡＭ４０は、各種データを一時記憶しＣＰＵ２０のワークエリアとして用いられる。配線動作プログラム１０１は、フロッピー（登録商標）ディスク（以下、ＦＤ）９０などの外部記憶媒体に記憶して配布されてもよく、不図示のサーバからネットワークを介して配布されてもよい。
【００２７】
入力部５０は、キーボードやマウスなどユーザが配線決定装置１００を操作するために用いられ、入力部５０から入力された入力情報はＣＰＵ２０に送出される。ハードディスク７０は、各レイヤー毎に配線設計された配線設計データ１０２をファイル等に格納して記憶している。ディスプレイ６０は、配線設計データ１０２を図１のような描画情報にして表示し、また、ユーザがマウス等で選択する操作メニューを表示する。
【００２８】
ドライブ装置８０は、ハードディスク７０を駆動するほかにＦＤ９０やＣＤ−ＲＯＭなどの外部記憶媒体を駆動する。入出力インターフェース（Ｉ／Ｏ）９は、ＣＰＵ２０と入力部５０や各種出力部との命令やデータの交換を行う。入出力インターフェース９には、ドライブ装置８０を接続してもよいしプリンタなどを接続してもよい。
【００２９】
ＣＰＵ２０は、ＲＯＭ３０に記憶された配線動作プログラム１０１をＲＡＭ４０に読み出して実行し、入力部５０から入力された入力情報に応じて仮想平面上で配線設計を行い、その結果をディスプレイ６０に表示する。また、配線設計データ１０２は、ハードディスク７０やＦＤ９０等に格納される。
【００３０】
図４は、配線決定装置１００の機能ブロック図を示す。図４の機能ブロックは、ＣＰＵ２０が設計動作プログラム１０１を実行することで実現される。ＣＰＵ２０が配線動作プログラム１０１を実行し、ユーザが配線決定の操作を入力部５０から入力すると、まず、仮配線部３１が配線設計データ１０２を読み出し、配線設計データ１０２に指定された対応関係に従いパッド部とビア部をそれぞれ直線の仮配線で結ぶ。
【００３１】
ついで、回避対象決定部３２は配線設計データ１０２から回避対象点を決定する。図１で説明したように、回避対象点は、交点からビアまでの距離が短い仮配線が接続されたビアである。
【００３２】
補助線掃引部３３は、回避対象点に水平・垂直な補助線を引く。これにより回避対象点を中心に４つの象限が得られる。なお、４つでなく３つの象限、又は、５以上の象限に区分してもよいし、補助線同士がなす角度は均等でも不均等でもよい。
【００３３】
開始象限決定部３４は、迂回する仮配線又は暫定配線の開始座標が４つの象限のどこにあるかを検出し、また、該象限において、迂回される配線（置き換えられない配線）に対する開始座標側の領域を検出する。開始座標は、仮配線又は暫定配線がパッドから一直線である場合はパッドであり、頂点（回避点Ｋ１〜Ｋ３のいずれか）を有する場合は、交点Ｑから見て始点側の最初の頂点である。
【００３４】
そして、クリアランス決定部３５は迂回するビアから所定のクリアランス離れた補助線上に回避点Ｋ１〜Ｋ３を決定する。クリアランスは予め定められているか、ユーザが入力部５０から入力することができる。クリアランスが少ないほど配線全体の長さの増加を抑制でき配線を密にしやすいが、最も少ないクリアランスを含め２〜３段階程度のクリアランスを定めておくことで、複数の配線が同じビアを迂回することが容易になる。
【００３５】
そして、結線部３６は、迂回する仮配線又は暫定配線の開始座標、回避点Ｋ１〜Ｋ３、及び、迂回する仮配線又は暫定配線が接続するビアを順に接続して、交差を解消する。
【００３６】
〔実施例〕
図５及び図６は、交差を解消する過程の配線の遷移を示す図である。図５（ａ）に示すように、仮配線部３１は、パッドＰ１とビアＶ５、パッドＰ２とビアＶ１、パッドＰ３とビアＶ４、パッドＰ４とビアＶ３、パッドＰ５とビアＶ２を、それぞれ仮配線Ｗ１〜Ｗ５で結線した。なお、交差はパッドに近い交点から順に解消する。
【００３７】
・仮配線Ｗ１とＷ２の交差を解消する（図５（ａ）（ｂ））
回避対象決定部３２は、交点Ｑ１とビアＶ５との距離と、交点Ｑ１とビアＶ１の距離を比較し、前者の方が長いので仮配線Ｗ１を迂回させることを決定し、また、回避対象をビアＶ１に決定する。
【００３８】
補助線掃引部３３はビアＶ１の中心を通過する水平・垂直な補助線を引く。
開始象限決定部３４は、仮配線Ｗ１の開始座標の、補助線に対する象限を取得する。仮配線Ｗ１の開始座標はパッドＰ１であるので第４象限が取得される。また、第４象限のうち、仮配線Ｗ２に対しパッドＰ１側の領域を検出する。
【００３９】
クリアランス決定部３５は、補助線上に回避点Ｋ１〜Ｋ３を定める。仮配線Ｗ２に対するパッドＰ１側の領域から、回避点Ｋ１は第４象限と第３象限の境に、回避点Ｋ２は第３象限と第２象限の境に、回避点Ｋ３は第２象限と第１象限の境に、定められる。
【００４０】
結線部３６は、パッドＰ１から回避点Ｋ１、Ｋ２、Ｋ３を順に結線し、最終的に終点であるビアＶ５まで結線し、仮配線Ｗ１を暫定配線Ｗ‘１に置き換える。
【００４１】
・仮配線Ｗ４とＷ５の交差を解消する（図５（ｂ）（ｃ））
回避対象決定部３２は、交点Ｑ２とビアＶ３との距離と、交点Ｑ２とビアＶ２の距離を比較し、前者の方が長いので仮配線Ｗ４を迂回させることを決定し、また、回避対象をビアＶ２に決定する。
【００４２】
補助線掃引部３３はビアＶ２の中心を通過する水平・垂直な補助線を引く。
開始象限決定部３４は、仮配線Ｗ４の開始座標の、補助線に対する象限を取得する。仮配線Ｗ４の開始座標はパッドＰ４であるので第４象限が取得される。また、第４象限のうち、仮配線Ｗ５に対しパッドＰ４側の領域を検出する。
【００４３】
クリアランス決定部３５は、補助線上に回避点Ｋ１〜Ｋ３を定める。仮配線Ｗ５に対するパッドＰ４側の領域から、回避点Ｋ１は第４象限と第３象限の境に、回避点Ｋ２は第３象限と第２象限の境に、回避点Ｋ３は第２象限と第１象限の境に、定められる。このクリアランスは、後にビアＶ４を迂回する配線がある可能性を考慮して、中程度のクリアランスである。
【００４４】
結線部３６は、パッドＰ４から回避点Ｋ１、Ｋ２、Ｋ３を順に結線し、最終的に終点であるビアＶ３まで結線し、仮配線Ｗ４を暫定配線Ｗ‘４に置き換える。
【００４５】
・仮配線Ｗ３と暫定配線Ｗ’４の交差を解消する（図５（ｃ）図６（ａ））
回避対象決定部３２は、交点Ｑ３とビアＶ４との距離と、交点Ｑ３とビアＶ２の頂点（図５（ｂ）の回避点Ｋ１）との距離を比較し、前者の方が長いので仮配線Ｗ３を迂回させることを決定し、また、回避対象をビアＶ２に決定する。
【００４６】
補助線掃引部３３はビアＶ２の中心を通過する水平・垂直な補助線を引く。
開始象限決定部３４は、仮配線Ｗ３の開始座標の、補助線に対する象限を取得する。仮配線Ｗ３の開始座標はパッドＰ３であるので第４象限が取得される。また、第４象限のうち、暫定配線Ｗ’４に対しパッドＰ３側の領域を検出する。
【００４７】
クリアランス決定部３５は、補助線上に回避点Ｋ１〜Ｋ３を定める。暫定配線Ｗ’４に対するパッドＰ３側の領域から、回避点Ｋ１は第４象限と第３象限の境に、回避点Ｋ２は第３象限と第２象限の境に、回避点Ｋ３は第２象限と第１象限の境に、定められる。
【００４８】
結線部３６は、パッドＰ３から回避点Ｋ１、Ｋ２、Ｋ３を順に結線し、最終的に終点であるビアＶ４まで結線し、仮配線Ｗ３を暫定配線Ｗ‘３に置き換える。
【００４９】
・暫定配線Ｗ’３とＷ’４の交差を解消する（図６（ａ）図６（ｂ））
回避対象決定部３２は、交点Ｑ４とビアＶ３との距離と、交点Ｑ４とビアＶ４の距離を比較し、前者の方が長いので暫定配線Ｗ‘４を迂回させることを決定し、また、回避対象をビアＶ４に決定する。
【００５０】
補助線掃引部３３はビアＶ４の中心を通過する水平・垂直な補助線を引く。
開始象限決定部３４は、暫定配線Ｗ‘４の開始座標の、補助線に対する象限を取得する。このように配線が頂点を有する場合、開始座標は交点Ｑ４から見て始点側の最初の頂点である。したがって、暫定配線Ｗ’４の開始座標は図５（ｂ）の回避点Ｋ３となる。開始象限決定部３４は、暫定配線Ｗ‘４の開始座標を第３象限として取得する。また、第３象限のうち、暫定配線Ｗ’３に対し図５（ｂ）の回避点Ｋ３側の領域を検出する。
【００５１】
クリアランス決定部３５は、補助線上に回避点Ｋ１〜Ｋ３を定める。暫定配線Ｗ’３に対する図５（ｂ）の回避点Ｋ３側の領域から、回避点Ｋ１は第３象限と第４象限の境に、回避点Ｋ２は第４象限と第１象限の境に、回避点Ｋ３は第１象限と第２象限の境に、定められる。
【００５２】
結線部３６は、図５（ｂ）の回避点Ｋ３から図６（ａ）の回避点Ｋ１、Ｋ２、Ｋ３を順に結線し、最終的に終点であるビアＶ３まで結線し、暫定配線Ｗ‘４を暫定配線Ｗ“４に置き換える。
【００５３】
・暫定配線Ｗ“４とＷ’１の交差を解消する（図６（ｂ）図６（ｃ））
回避対象決定部３２は、交点Ｑ５とビアＶ５との距離と、交点Ｑ５とビアＶ３の距離を比較し、前者の方が長いので暫定配線Ｗ‘１を迂回させることを決定し、また、回避対象をビアＶ３に決定する。
【００５４】
補助線掃引部３３はビアＶ３の中心を通過する水平・垂直な補助線を引く。
開始象限決定部３４は、暫定配線Ｗ’１の開始座標の、補助線に対する象限を取得する。このように配線が頂点を有する場合、開始座標は交点Ｑ５から見て始点側の最初の頂点である。したがって、暫定配線Ｗ’１の開始座標は図５（ａ）の回避点Ｋ３となる。開始象限決定部３４は、暫定配線Ｗ’１の開始座標を第３象限として取得する。また、第３象限のうち、暫定配線Ｗ”４に対し図５（ａ）の回避点Ｋ３側の領域を検出する。
【００５５】
クリアランス決定部３５は、補助線上に回避点Ｋ１〜Ｋ３を定める。暫定配線Ｗ”４に対する図５（ａ）の回避点Ｋ３側の領域から、回避点Ｋ１は第３象限と第２象限の境に、回避点Ｋ２は第２象限と第１象限の境に、回避点Ｋ３は第１象限と第４象限の境に、定められる。
【００５６】
結線部３６は、図５（ａ）の回避点Ｋ３から図６（ｂ）の回避点Ｋ１、Ｋ２、Ｋ３を順に結線し、最終的に終点であるビアＶ５まで結線し、暫定配線Ｗ‘１を暫定配線Ｗ“１に置き換える。
【００５７】
図６（ｃ）に示すように以上の処理により、配線設計データ１０２から配線の交差を解消することができた。
【００５８】
〔不要な頂点の削除〕
ところで、交差を解消していくとそれまでは交差の解消に有効だった頂点が不要となる場合がある。不要な頂点は以降の交差の解消を阻害することにもなるため不要な頂点は削除することが望ましいので、不要な頂点の削除について説明する。なお、回避方法は図５，６にて説明したので詳細は省略する。
【００５９】
まず、図７（ａ）の交点Ｑ１の交差を解消する。交点Ｑ１からビアＶ５の交点Ｑ１からビアＶ１までの距離を比較すると前者の方が長いので、仮配線Ｗ１を迂回させる。このため、ビアＶ１に補助線を引き補助線上の回避点Ｋ１〜Ｋ３（図示せず）を結線して得られる暫定配線Ｗ’１に仮配線Ｗ１を置き換える。これにより図７（ｂ）のように交点Ｑ１の交差が解消される。
【００６０】
次に、交点Ｑ２の交差を解消する。交点Ｑ２からビアＶ２と交点Ｑ２からビアＶ３までの距離を比較すると前者の方が長いので、仮配線Ｗ４を迂回させる。このため、図７（ｃ）に示すように、ビアＶ３に補助線を引き補助線上の回避点Ｋ１〜Ｋ３（図示せず）を結線して得られる暫定配線Ｗ’４に仮配線Ｗ４を置き換える。これにより図８（ａ）のように交点Ｑ２の交差が解消される。
【００６１】
これで仮配線Ｗ１〜Ｗ５同士の交差は解消されたので、ここまでの１つのラウンドとすれば、不要な頂点を削除する。しかしながら、１ラウンドが終了した時点では不要な頂点はない。
【００６２】
次に、交点Ｑ３の交差を解消する。交点Ｑ３からビアＶ４と交点Ｑ３からビアＶ３までの距離を比較すると前者の方が長いので、仮配線Ｗ３を迂回させる。このため、図８（ｂ）に示すように、ビアＶ３に補助線を引き補助線上の回避点Ｋ１〜Ｋ３（図示せず）を結線して得られる暫定配線Ｗ’３に仮配線Ｗ３を置き換える。なお、ビアＶ３には既に回避点Ｋ１〜Ｋ３の頂点が設けられているので、今回の回避点は所定のクリアランスを隔てて設ける。これにより図８（ｃ）のように交点Ｑ２の交差が解消される。
【００６３】
次に、交点Ｑ４の交差を解消する。交点Ｑ４からビアＶ２と交点Ｑ４からビアＶ４までの距離を比較すると前者の方が長いので、暫定配線Ｗ’４を迂回させる。このため、図９（ａ）に示すように、ビアＶ４に補助線を引き補助線上の回避点Ｋ１〜Ｋ３（図示せず）を結線して得られる暫定配線Ｗ’’４に暫定配線Ｗ’４を置き換える。これにより図９（ｂ）のように交点Ｑ４の交差が解消される。
【００６４】
次に、交点Ｑ５の交差を解消する。交点Ｑ５からビアＶ５と交点Ｑ５からビアＶ４の頂点Ｋ１までの距離を比較すると前者の方が長いので、暫定配線Ｗ’１を迂回させる。このため、図９（ｃ）に示すように、ビアＶ４に補助線を引き補助線上の回避点Ｋ１〜Ｋ３（図示せず）を結線して得られる暫定配線Ｗ’’１に暫定配線Ｗ’１を置き換える。なお、ビアＶ４には既に回避点Ｋ１〜Ｋ３の頂点が設けられているので、今回の回避点は所定のクリアランスを隔てて設ける。これにより図１０（ａ）のように交点Ｑ５の交差が解消される。
【００６５】
これで暫定配線同士の交差の解消が１回分終了したいので、ここまでで２ラウンド目が終了したことになる。図１０（ｂ）に示すように交差の解消の結果、ビアＶ１に不要な頂点が残ったので、これを削除する。不要な頂点とは例えば鋭角（９０度未満）のなす角の配線の頂点である。不要な頂点の削除により図１０（ｃ）の配線が得られる。
【００６６】
次に、交点Ｑ６の交差を解消する。交点Ｑ６からビアＶ５と交点Ｑ６からビアＶ４の頂点まで（頂点間の線分）の距離を比較すると前者の方が長いので、暫定配線Ｗ’’１を迂回させる。このため、図１１（ａ）に示すように、ビアＶ２に補助線を引き補助線上の回避点Ｋ１〜Ｋ３（図示せず）を結線して得られる暫定配線Ｗ‘’’１に暫定配線Ｗ’’１を置き換える。これにより図１１（ｂ）のように交点Ｑ４の交差が解消される。
【００６７】
ここまでで第３ラウンドが終了する。図１１（ｂ）を見るとビアＶ４に不要な頂点があるのでこれを削除する。不要な頂点の削除により図１１（ｃ）の配線が得られる。また、図１１（ｃ）には交点がないので処理を終了する。
【００６８】
以上説明したように、本実施形態の配線決定方法によれば、配線の交差を解消する際、ビアの中心を通過して迂回するステップがないため、ビア上での仮配線又は暫定配線の交差判定を不要とすることができる。
【図面の簡単な説明】
【００６９】
【図１】配線決定方法の概略を説明する図である。
【図２】配線決定方法の手順を説明するフローチャート図である。
【図３】配線決定装置の構成図の一例である。
【図４】配線決定装置の機能ブロック図の一例である。
【図５】交差を解消する過程の配線の遷移を示す図である。
【図６】交差を解消する過程の配線の遷移を示す図である。
【図７】交差を解消する過程の配線の遷移お及び交差を解消する過程で生じる不要な頂点の一例を示す図である。
【図８】交差を解消する過程の配線の遷移お及び交差を解消する過程で生じる不要な頂点の一例を示す図である。
【図９】交差を解消する過程の配線の遷移お及び交差を解消する過程で生じる不要な頂点の一例を示す図である。
【図１０】交差を解消する過程の配線の遷移お及び交差を解消する過程で生じる不要な頂点の一例を示す図である。
【図１１】交差を解消する過程の配線の遷移お及び交差を解消する過程で生じる不要な頂点の一例を示す図である。
【図１２】従来の配線決定方法の一例を示す図である。
【符号の説明】
【００７０】
２０      ＣＰＵ
３１      仮配線部
３２      回避対象決定部
３３      補助線掃引部
３４      開始象限決定部
３５      クリアランス決定部
３６      結線部
５０      入力部
１００    配線決定装置
１０１    設計動作プログラム
１０２    配線設計データ
【図１】
2009140221.tif 000003
【図２】
2009140221.tif 000004
【図３】
2009140221.tif 000005
【図４】
2009140221.tif 000006
【図５】
2009140221.tif 000007
【図６】
2009140221.tif 000008
【図７】
2009140221.tif 000009
【図８】
2009140221.tif 000010
【図９】
2009140221.tif 000011
【図１０】
2009140221.tif 000012
【図１１】
2009140221.tif 000013
【図１２】
2009140221.tif 000014