(57)【要約】【課題】基板面上の配線のルートの位置を、基板面に相当する仮想平面を用いて演算処理装置により短時間で自動的に決定することができる自動配線設計方法を実現する。【解決手段】自動配線設計方法は、基板面に相当する仮想平面上において、ルート決定対象配線が通過すべき仮通過点を設定する仮通過点設定ステップと、仮通過点と、始点、終点および当該仮通過点とは異なる他の仮通過点のうち当該仮通過点を挟む２点と、で形成される三角形を設定する三角形設定ステップと、この三角形の内側に位置しなおかつ仮通過点に最も近接して位置する障害物の近傍の点を、ルート決定対象配線が通過すべき本通過点として確定する確定ステップと、を備え、本通過点を通過するルートをルート決定対象配線の最適ルートの位置として決定する。【選択図】図１
2009015366.tif 000002
【特許請求の範囲】
【請求項１】
基板面上の配線のルートの位置を、前記基板面に相当する仮想平面を用いて演算処理装置により決定する自動配線設計方法であって、前記仮想平面上において、始点および終点の位置のみが確定されたルート決定対象配線についての、前記始点と前記終点との間における最適ルートの位置を決定する自動配線設計方法において、
前記仮想平面上において、前記ルート決定対象配線が少なくとも通過すべきおよその位置を仮通過点として設定する仮通過点設定ステップと、
前記仮通過点と、前記始点、前記終点および当該仮通過点とは異なる他の前記仮通過点のうち当該仮通過点を挟む２点と、で形成される三角形を設定する三角形設定ステップと、
配線設計上の障害となり得る障害物であって前記三角形の内側に位置しなおかつ前記仮通過点に最も近接して位置する障害物の近傍の点を、ルート決定対象配線が通過すべき本通過点として確定する確定ステップと、
を備え、
前記本通過点を通過するルートを前記ルート決定対象配線の最適ルートの位置として決定することを特徴とする自動配線設計方法。
【請求項２】
前記本通過点と前記障害物との間のクリアランスを確保するよう、該本通過点の位置を補正するクリアランス確保ステップをさらに備える請求項１に記載の自動配線設計方法。
【請求項３】
前記障害物は、前記ルート決定対象の配線とは異なる他の既存配線の端子である請求項１に記載の自動配線設計方法。
【請求項４】
基板面上の配線の最適ルートを、前記基板面に相当する仮想平面上において複数のセグメントをつなぎ合わせて構成されるルートとして演算処理装置により決定する自動配線設計方法であって、前記仮想平面上において、所定のライン上のいずれかの位置に終端することについて確定されているルート決定対象配線について、最適ルートを決定する自動配線設計方法において、
前記仮想平面上において、前記ルート決定対象配線が終端すべき前記所定のライン上に仮終点を設定する仮終点設定ステップであって、前記仮終点を含むセグメントである終端セグメントが前記所定のラインと直交するよう、前記仮終点を設定するステップと、
前記終端セグメントの近傍に位置する、配線設計上の障害となり得る障害物との間におけるクリアランスを検査する検査ステップと、
前記検査ステップにおける検査の結果、クリアランスが確保される場合は、前記仮終点の位置を、前記ルート決定対象配線の終点として確定する終点確定ステップと、
を備えることを特徴とする自動配線設計方法。
【請求項５】
前記検査ステップにおける検査の結果、クリアランスが確保されない場合は、当該終端セグメントの前記仮終点とは反対側の端点と、クリアランスを確保することができる屈曲点と、を結ぶ新たなセグメントを、前記ルート決定対象配線の最適ルートの一部として設定するセグメント確定ステップと、
前記所定のライン上に新たなる仮終点を設定するさらなる仮終点設定ステップであって、前記新たなる仮終点と前記屈曲点を結ぶセグメントである新たなる終端セグメントが前記所定のラインと直交するよう、前記新たなる仮終点を設定するステップと、
をさらに備え、
前記新たなる終端セグメントについて、前記検査ステップをさらに実行する請求項４に記載の自動配線設計方法。
【請求項６】
前記障害物は、前記ルート決定対象の配線とは異なる他の既存配線の端子である請求項４に記載の自動配線設計方法。
【請求項７】
前記所定のラインは、前記ルート決定対象配線をＴジャンクション接続形式で接続するための配線である請求項４に記載の自動配線設計方法。
【請求項８】
前記所定のラインは、めっき引き出し線である前記ルート決定対象配線が引き出される基板のエッジである請求項４に記載の自動配線設計方法。
【請求項９】
基板面上のめっき引き出し線のルートの位置を、前記基板面に相当する仮想平面を用いて演算処理装置により決定する自動配線設計方法であって、
前記仮想平面上において、予め決定されためっき引き出し線の始点から、基板のエッジまで仮ルートを設定する仮設定ステップと、
前記仮ルートと、他の既存配線との交差回数をカウントするカウントステップと、
前記交差回数が奇数の場合、前記仮ルートを、前記他の既存配線の両端の端子を通過する仮ルートに置き換える置換ステップであって、置き換えられた前記仮ルートについては再度、前記カウントステップによるカウント処理が実行されるステップと、
前記交差回数が偶数の場合、前記始点と、前記他の配線の屈曲点と、前記仮ルートの基板のエッジとの交点と、を結ぶさらなる仮ルートを設定するさらなる仮設定ステップと、
前記さらなる仮ルートのうち、前記始点と前記交点との距離が短い方を修正対象ルートとして設定する設定ステップと、
前記修正対象ルートを、配線設計上の障害となり得る障害物に対して所定のクリアランスを確保する最適なルートに修正する修正ステップであって、ルート修正の基準となった前記障害物のうち前記基板のエッジに最も近い障害物の近傍の前記最適ルート上の点から、前記基板のエッジに対して直交するルートを設定するステップと、
を備えることを特徴とする自動配線設計方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、基板面上の配線のルートの位置を、基板面に相当する仮想平面を用いて演算処理装置により決定する自動配線設計方法に関する。
【背景技術】
【０００２】
例えばＬＳＩやＰＣＢなどの半導体集積回路について、基板上に存在する障害物と交差することなく自動的に配線する自動配線方法の代表的なものとして、迷路探索法と呼ばれる方法がある（例えば、特許文献１〜４参照）。この迷路探索法では、基板上において、配線のルートを、障害物とのクリアランスを保つように、かつ、障害物に対しては９０度の方向に、場合によっては４５度の方向に迂回させることで当該障害物と交差しないように設定する。このような設定手法を実現できるのは、ＬＳＩやＰＣＢなどにおいては障害物の配置位置や形状がある程度の規則性を有しているという、ＬＳＩやＰＣＢに特有の配線的特徴に起因するものである。
【０００３】
ＰＢＧＡやＥＢＧＡなどの半導体パッケージの基板上には、プレーン（Ｐｌａｎｅ）、ゲート（Ｇａｔｅ）、マーク（Ｍａｒｋ）、パッケージ内部品もしくは他の配線などといったような、配線にとっては障害物となり得るものが多数存在し、その障害物の形状、配置位置あるいは配置角度も多種多様である。また、配線の始点もしくは終点となるべきビア（Ｖｉａ）、ボール（ｂａｌｌ）、ボンディングパッド（Ｂ／Ｐ）、あるいはフリップチップパッド（Ｆ／Ｃ）などの位置も様々である。このため、半導体パッケージの配線設計においては、基板上において、障害物を回避する際には９０度や４５度に限られない任意の角度方向に配線のルートを迂回させる必要がある。つまり、従来からＬＳＩやＰＣＢなどにおける自動配線に用いられてきた迷路探索法では、半導体パッケージの場合には対応できない。
【０００４】
このような事情から、半導体パッケージの配線設計においては、設計者自身が、例えばＣＡＤシステムを用いて仮想平面上で半導体パッケージの配線ルートを自らの技量や経験や勘を頼りに試行錯誤しながら設計するのが一般的である。
【０００５】
これに対し、基板上における配線の最適ルートを、基板上における他の配線と交差しないよう、自動的に決定する自動配線決定方法がある（例えば、特許文献５参照）。この方法では、まず、配線の始点および終点となる２点間を検査直線で結び、この検査直線が他の配線と交差する場合には、始点に最も近い位置に存在する当該他の配線の各端点のうちのいずれかの端点と上記始点とを結ぶ直線部分を、最適ルートの候補を構成するセグメントとして確定する。そしてこのとき、上記候補の確定に用いた当該端点を、新たな始点として再設定する。さらに、当該新たな始点と終点との間に新たに結んだ検査直線に基づいて、上記の各処理を繰り返し実行し、セグメントから構成されるルート候補を生成する。最終的には、このように生成されたルート候補から最適ルートを確定する。
【０００６】
また、基板上の配線のルートを、基板上における障害物と交差しないよう、自動的に決定する自動配線決定方法がある（例えば、特許文献６参照）。この方法では、配線の始点および終点となるべき２点間を結ぶ直線上に障害物が存在するとき、この障害物に接する、始点からの直線ルートと、この障害物に接する、終点からの直線ルートと、を少なくとも含んだ仮ルートをまず設定する。特にこの仮ルートは、配線の始点および終点となるべき２点間を結ぶ直線上に障害物が複数存在する場合においては、２つの障害物のみに接しかつ当該２つの障害物以外の障害物とは交差しない直線ルートをさらに含んで設定される。なお、この２つの障害物に接する直線ルートは、２つの障害物間ごとに設定される。設定された複数の仮ルートのうち、配線の始点から終点までの間の距離が最短となる仮ルートを、配線の最適なルートとして確定する。
【０００７】
また、基板上における各パッド部からそれぞれの結線先である各ビア部への最適な配線の位置を設計するにあたり、配線の向きが、ある一部分において大方の方向とはほぼ逆向きとなるような傾向があっても、演算処理により自動的に配線の位置を決定することが可能な自動配線決定装置がある（例えば、特許文献７参照）。この装置は、各パッド部と各パッド部のそれぞれの結線先である各ビア部とを直線で結んだ各仮配線のうち、２つの仮配線が形成する交点を解消するよう、当該交点を形成する一方の仮配線を、もう一方の仮配線の結線先であるビア部の周りに迂回させ、これを暫定配線として確定する第１の交点解消処理を、各仮配線が形成する交点の全てについて、パッド部に近い交点から順次実行する第１の交点解消手段と、この第１の交点解消手段による第１の交点解消処理の完了後、各暫定配線同士が形成する交点もしくは暫定配線と仮配線とが形成する交点を解消するよう、当該交点を形成する一方の暫定配線もしくは仮配線を、もう一方の暫定配線もしくは仮配線の結線先であるビア部の周りに迂回させ、これを最適な配線として確定する第２の交点解消処理を、各暫定配線同士が形成する交点および暫定配線と仮配線とが形成する交点の全てについて、パッド部に近い交点から順次実行する第２の交点解消手段と、を備える。
【０００８】
【特許文献１】特開平１１−１６１６９４号公報
【特許文献２】特開２００１−３５０８１３号公報
【特許文献３】特開２００１−０４４２８８号公報
【特許文献４】特開平１０−２０９２８８号公報
【特許文献５】特開２００７−０７９７３８号公報
【特許文献６】特開２００６−３３１０１７号公報
【特許文献７】特開２００６−２６８４６２号公報
【発明の開示】
【発明が解決しようとする課題】
【０００９】
基板面上の配線の最適ルートの位置を、基板面に相当する仮想平面を用いて演算処理装置により決定する自動配線設計方法もしくは装置である特許文献５〜７に記載された発明は、ルート決定対象である配線（以下、「ルート決定対象配線」と称する。）の始点および終点となる２点の端子の、仮想平面上の配置位置について、設計データ上既に確定されている場合に、適用することができる。
【００１０】
しかしながら、演算処理装置を用いて自動的に設計するにしても、「仮想平面上の少なくともこの辺りには配線のルートが通過するようにしたい」といったような設計者の要望を配線設計に反映させたいような場合がある。
【００１１】
また、めっき引き出し線の位置を決定する場合や、ルート決定対象配線をＴジャンクション接続形式で接続する場合など、設計データ上、ルート決定対象配線の終点の端子の位置が不確定の場合もある。
【００１２】
配線設計上の上述のような「曖昧さ」は、演算処理装置を用いて自動設計する上述の従来例では十分に対応することができず、柔軟さに欠ける。また、設計者自身がＣＡＤシステムを用いて仮想平面上で設計する場合には、上述の「曖昧さ」に対応することはできるものの、非常に時間がかかる。
【００１３】
従って本発明の目的は、上記問題に鑑み、基板面上の配線のルートの位置を、基板面に相当する仮想平面を用いて演算処理装置により短時間で自動的に決定することができる自動配線設計方法を提供することにある。
【課題を解決するための手段】
【００１４】
上記目的を実現するために、本発明の第１の態様によれば、始点および終点の位置のみが確定されたルート決定対象配線についての、始点と終点との間における最適ルートの位置を、演算処理装置により決定する自動配線設計方法は、仮想平面上において、ルート決定対象配線が少なくとも通過すべきおよその位置を仮通過点として設定する仮通過点設定ステップと、仮通過点と、始点、終点および当該仮通過点とは異なる他の仮通過点のうち当該仮通過点を挟む２点と、で形成される三角形を設定する三角形設定ステップと、配線設計上の障害となり得る障害物であって上記三角形の内側に位置しなおかつ仮通過点に最も近接して位置する障害物の近傍の点を、ルート決定対象配線が通過すべき本通過点として確定する確定ステップと、を備え、本通過点を通過するルートをルート決定対象配線の最適ルートの位置として決定する。
【００１５】
また、本発明の第２の態様によれば、基板面上の配線の最適ルートを、この基板面に相当する仮想平面上において複数のセグメントをつなぎ合わせて構成されるルートとして演算処理装置により決定する自動配線設計方法であって、仮想平面上において、所定のライン上のいずれかの位置に終端することについて確定されているルート決定対象配線について、最適ルートを決定する自動配線設計方法は、仮想平面上において、ルート決定対象配線が終端すべき所定のライン上に仮終点を設定する仮終点設定ステップであって、仮終点を含むセグメントである終端セグメントが所定のラインと直交するよう、仮終点を設定するステップと、終端セグメントの近傍に位置する、配線設計上の障害となり得る障害物との間におけるクリアランスを検査する検査ステップと、検査ステップにおける検査の結果、クリアランスが確保される場合は、仮終点の位置を、ルート決定対象配線の終点として確定する終点確定ステップと、を備える。
【００１６】
また、本発明の第３の態様によれば、基板面上のめっき引き出し線のルートの位置を、基板面に相当する仮想平面を用いて演算処理装置により決定する自動配線設計方法は、基板面に相当する仮想平面上において、予め決定されためっき引き出し線の始点から、基板のエッジまで仮ルートを設定する仮設定ステップと、仮ルートと、他の既存配線との交差回数をカウントするカウントステップと、交差回数が奇数の場合、仮ルートを、他の既存配線の両端の端子を通過する仮ルートに置き換える置換ステップであって、置き換えられた仮ルートについては再度、カウントステップによるカウント処理が実行されるステップと、交差回数が偶数の場合、始点と、他の配線の屈曲点と、仮ルートの基板のエッジとの交点と、を結ぶさらなる仮ルートを設定するさらなる仮設定ステップと、このさらなる仮ルートのうち、始点と上記交点との距離が短い方を修正対象ルートとして設定する設定ステップと、修正対象ルートを、配線設計上の障害となり得る障害物に対して所定のクリアランスを確保する最適なルートに修正する修正ステップであって、ルート修正の基準となった障害物のうち基板のエッジに最も近い障害物の近傍の最適ルート上の点から、基板のエッジに対して直交するルートを設定するステップと、を備える。
【００１７】
なお、本発明の第１〜第３の態様による自動配線設計方法の各ステップは、コンピュータ等の演算処理装置が実行することができるコンピュータプログラムの形式で実現できる。以上の処理を実施する装置や、以上の処理をコンピュータに実行させるコンピュータプログラムを作成することは、以下の説明を理解した当業者には容易に実施できる事項である。また、以上の処理をコンピュータにより実行させるコンピュータプログラムを記録媒体に格納するという事項も当業者には自明である。
【発明の効果】
【００１８】
本発明によれば、基板面上の配線のルートの位置を、基板面に相当する仮想平面を用いて演算処理装置により短時間で自動的に決定することができる。本発明によれば、ＬＳＩやＰＣＢなどの半導体集積回路はもちろん、ＰＢＧＡやＥＢＧＡなどの半導体パッケージ、あるいはＭＣＭ／ＳＩＰなどの配線基板においても、演算処理装置を用いて自動的に配線のルートを決定することができる。本発明を配線基板の配線設計に適用すれば、従来のように設計者自らの技量、経験、勘などに左右されることなく、所望の配線ルートを短時間で容易に設計することができる。例えば、従来、試行錯誤しながらの手動による配線設計では数日程度を要していたところが、本発明によれば、数時間程度以下で所望の配線ルートを自動的に設計することができる。このような設計時間の短縮および設計者の負担の軽減の結果、製品の製造コストも低減できる。最適な配線ルートは、配線距離が短いので経済的であり、製造容易であり、そして製造時における製品不良の発生率も低い。また、電気的にも安定した特性を示す。
【００１９】
本発明の第１の態様によれば、「仮想平面上の少なくともこの辺りには配線のルートが通過するようにしたい」といったような設計者の要望を反映させた配線設計を、演算処理装置を用いて短時間で自動的に実行することができる。
【００２０】
本発明の第２の態様によれば、めっき引き出し線の位置を決定する場合や、ルート決定対象配線をＴジャンクション接続形式で接続する場合など、設計データ上、ルート決定対象配線の終点の端子の位置が不確定である配線設計であっても、演算処理装置を用いて短時間で自動的に実行することができる。
【００２１】
本発明の第３の態様によれば、従来より行われている配線設計手法である他の配線をずらしながらめっき引き出し線の配線ルートを見つけていくいわゆる「自動プッシュ（Ｐｕｓｈ）」方法によるでも、めっき引き出し線の基板のエッジ上の適正な位置を見つけ出すことができる。
【発明を実施するための最良の形態】
【００２２】
本発明の第１の実施例による自動配線設計方法では、基板面に相当する仮想平面上において、始点Ｓおよび終点Ｅの位置のみが確定されたルート決定対象配線についての、始点と終点との間における最適ルートの位置を、コンピュータ等の演算処理装置を用いて決定する。図１は、本発明の第１の実施例による自動配線設計方法の動作フローを示すフローチャートである。また、図２〜５は、本発明の第１の実施例による自動配線設計方法に基づく配線ルート決定の具体例を示す図である。なお、図２〜５においては、配線の端子を丸印で表し、これら端子間を結ぶ配線を実線で表す。
【００２３】
ここでは、一具体例として、図２に示すように、仮想平面上において、ルート決定対象配線の始点Ｓおよび終点Ｅの位置のみが確定されている場合を考える。図２〜５では、始点Ｓと終点Ｅとの間の設計データ上の接続関係を、図中点線で示されるラッツ（Ｒａｔｓ）Ｒで表している。
【００２４】
まず、仮通過点設定ステップＳ１０１において、コンピュータ等の演算処理装置は、基板面に相当する仮想平面上において、ルート決定対象配線が少なくとも通過すべきおよその位置を仮通過点として設定する。この仮通過点は、仮想平面上の少なくともこの辺りには配線のルートが通過するようにしたいおおよその位置であればよい。例えば、図３に示すように、設計者は、ルート決定対象配線が点Ｐ１および点Ｐ２辺りを通るように希望したときは、その情報を演算処理装置に入力する。
【００２５】
次いで、三角形設定ステップＳ１０２において、仮通過点と、始点、終点およびクリアランス検査対象の仮通過点とは異なる他の仮通過点のうち当該仮通過点を挟む２点と、で形成される三角形を設定する。例えば、図４に示すように、仮通過点Ｐ１と、仮通過点Ｐ１を挟む始点Ｓおよび仮通過点Ｐ２とで構成される三角形Ｓ−Ｐ１−Ｐ２が設定される。また、仮通過点Ｐ２と、仮通過点Ｐ２を挟む仮通過点Ｐ１および終点Ｅとで構成される三角形Ｐ１−Ｐ２−Ｅが設定される。
【００２６】
次いで、確定ステップＳ１０３において、配線設計上の障害となり得る障害物であって三角形設定ステップＳ１０２において設定した三角形の内側に位置しなおかつ前記仮通過点に最も近接して位置する障害物の近傍の点を、ルート決定対象配線が通過すべき本通過点として確定する。例えば、障害物がルート決定対象の配線とは異なる他の既存配線の端子である図５の例では、点Ｔ１およびＴ２を、ルート決定対象配線が通過すべき本通過点として確定する。なお、図５に示す例では、本通過点Ｔ１およびＴ２を、障害物である各配線Ｗ１およびＷ２の端子上に示した。その後の演算処理によりルート決定対象配線のルートが決定したら、そのルートについて、各配線Ｗ１およびＷ２の端子との間のクリアランスを確保するための処理として、本通過点Ｔ１およびＴ２と障害物である各配線Ｗ１およびＷ２の端子との間のクリアランスを確保するよう、本通過点Ｔ１およびＴ２の位置を補正する。
【００２７】
以上の処理により、仮想平面上の少なくともこの辺りには配線のルートが通過するようにしたい」という曖昧であった位置情報が、コンピュータ等の演算処理装置により処理可能なデータとして確定されたことになる。したがって、このデータを用いれば、公知の自動配線設計方法に従って、本通過点を通過するルートを前記ルート決定対象配線の最適ルートの位置として演算処理装置を用いて自動的に決定することができる。図６〜８は、本発明の第１の実施例による自動配線設計方法に基づいて図５のように決定された本通過点を通過する配線ルートの決定の具体例を示す図である。この具体例では、障害物がルート決定対象の配線とは異なる他の既存配線であるので、上記特許文献５すなわち特開２００７−０７９７３８号公報に記載された発明を用いて、最適ルートを見つけ出す。なお、障害物が、既存配線以外のものであるときは、例えば上記特許文献６すなわち特開２００６−３３１０１７号公報に記載された発明を用いて、最適ルートを見つけ出せばよい。また、基板上における各パッド部からそれぞれの結線先である各ビア部への最適な配線の位置を設計するにあたり、配線の向きが、ある一部分において大方の方向とはほぼ逆向きとなるような傾向がある場合には、例えば上記特許文献７すなわち特開２００６−２６８４６２号公報に記載された発明を用いて、最適ルートを見つけ出せばよい。
【００２８】
図５のように決定された本通過点については、図６に示すように、始点Ｓから点Ａ、本通過点Ｔ１および点Ｃを通って終点Ｅに至るルートと、始点Ｓから点Ｂ、本通過点Ｔ１および点Ｃを通って終点Ｅに至るルートと、の２つのルートが候補として挙がる。この候補のうち、例えば最短のルートを選択すると図７に示すようなルートが得られる。選択されたルートについて、隣接する他の既存配線とのクリアランスを確保するよう補正すると、図８に示すようなルートが確定される。例えば本通過点Ｔ１およびＴ２は、各配線Ｗ１およびＷ２との間のクリアランスを確保することができる点Ｕ１およびＵ２の位置に補正される。
【００２９】
本発明の第２の実施例による自動配線設計方法では、基板面に相当する仮想平面上において、所定のライン上のいずれかの位置に終端することについて確定されているルート決定対象配線についての最適ルートの位置を、コンピュータ等の演算処理装置を用いて決定する。ここで、所定のラインとは、ルート決定対象配線をＴジャンクション接続形式で接続するための配線、あるいは、めっき引き出し線であるルート決定対象配線が引き出される基板のエッジである。この自動配線設計方法では、基板面に相当する仮想平面上の配線の最適ルートは、複数のセグメントをつなぎ合わせで構成される。
【００３０】
図９は、本発明の第２の実施例による自動配線設計方法の動作フローを示すフローチャートである。また、図１０〜１３は、本発明の第２の実施例による自動配線設計方法に基づく配線ルート決定の具体例を示す図である。なお、図１０〜１３においては、配線の端子を丸印で表し、これら端子間を結ぶ配線を実線で表す。
【００３１】
ここでは、一具体例として、図１０に示すように、仮想平面上において、ルート決定対象配線の始点Ｓの位置が確定されており、ルート決定対象配線の終点Ｅについては、配線Ｗ１上のいずれかの点にＴジャンクション接続形式で接続されることのみが確定されている場合を考える。図１０〜１３では、始点Ｓと終点Ｅとの間の設計データ上の接続関係を、図中点線で示されるラッツ（Ｒａｔｓ）Ｒで表している。
【００３２】
まず、仮終点設定ステップＳ２０１において、基板面に相当する仮想平面上において、ルート決定対象配線が終端すべき前記所定のライン上に仮終点を設定する。この仮終点設定ステップＳ２０１では、仮終点を含むセグメントである終端セグメントが所定のラインと直交するよう、仮終点を設定する。図１０に示す例に本発明を適用すると、図１１に示すように、終端セグメントＭが配線Ｗ１と直行するような位置に仮終点Ｅ’が設定される。
【００３３】
次いで、検査ステップＳ２０２において、終端セグメントの近傍に位置する、配線設計上の障害となり得る障害物との間におけるクリアランスを検査する。図１１に示す例では、終端セグメントＭの近傍に位置する、障害物である既存配線Ｗ２の端子Ｑとの間におけるクリアランスを検査する。
【００３４】
検査ステップＳ２０２における検査の結果、クリアランスが確保されていると判定された場合は、終点確定ステップＳ２０３において、このときの仮終点の位置を、ルート決定対象配線の終点として確定する。例えば、図１１に示す場合において、終端セグメントＭと、終端セグメントＭの近傍に位置する既存配線Ｗ２の端子Ｑとの間におけるクリアランスが確保されている場合は、このときの仮終点Ｅ’の位置を、ルート決定対象配線の終点として確定する。この場合、図１１において太線の実線で示した状態のルートが確定する。このルートについて、他の既存配線との間のクリアランスを確保するように補正を行うと、図１２に示すような最適ルートが得られる。
【００３５】
一方、検査ステップＳ２０２における検査の結果、クリアランスが確保されていないと判定された場合は、セグメント確定ステップＳ２０４において、当該終端セグメントの仮終点とは反対側の端点と、クリアランスを確保することができる屈曲点と、を結ぶ新たなセグメントを、ルート決定対象配線の最適ルートの一部として設定する。例えば、図１１に示す場合において、終端セグメントＭと、終端セグメントＭの近傍に位置する既存配線Ｗ２の端子Ｑとの間におけるクリアランスが確保されていない場合は、図１３に示すように、図１１の場合における終端セグメントＭの仮終点Ｅ’とは反対側の端点Ｙと、クリアランスを確保することができる屈曲点Ｖと、を結ぶ新たなセグメントＮを、ルート決定対象配線の最適ルートの一部として設定する。
【００３６】
次いで、さらなる仮終点設定ステップＳ２０５において、所定のライン上に新たなる仮終点を設定する。さらなる仮終点設定ステップＳ２０５では、この新たなる仮終点とセグメント確定ステップＳ２０４における屈曲点を結ぶセグメントである新たなる終端セグメントが所定のラインと直交するよう、新たなる仮終点を設定する。その後、検査ステップＳ２０２へ戻る。図１３に示す例では、配線Ｗ１に新たなる仮終点Ｅ”を設定する。新たなる仮終点Ｅ”は、仮終点Ｅ”とセグメント確定ステップＳ２０４における屈曲点Ｖを結ぶセグメントである新たなる終端セグメントＭ”が所定のラインと直交するように、設定する。その後、検査ステップＳ２０２へ戻り、新たなる終端セグメントＭ”についてクリアランス検査を実行する。例えば、図１３に示す場合において、新たなる終端セグメントＭ”と、新たなる終端セグメントＭ”の近傍に位置する既存配線Ｗ２の端子Ｑとの間におけるクリアランスが確保されている場合は、このときの新たなる仮終点Ｅ”の位置を、ルート決定対象配線の終点として確定する。この場合、図１３において太線の実線で示した状態のルートが確定する。その後、このルートについて、他の既存配線との間のクリアランスを確保するように補正を行うと最適ルートが得られる。
【００３７】
本発明の第３の実施例による自動配線設計方法では、基板面に相当する仮想平面上において、基板面上のめっき引き出し線のルートの位置を、基板面に相当する仮想平面を用いて演算処理装置により決定する。
【００３８】
図１４は、本発明の第３の実施例による自動配線設計方法の動作フローを示すフローチャートである。また、図１５〜１８は、本発明の第３の実施例による自動配線設計方法に基づく配線ルート決定の具体例を示す図である。なお、図１５〜１８においては、配線の端子を丸印で表し、これら端子間を結ぶ既存配線Ｗを実線で表す。また、基板のエッジＦを一点鎖線で表す。また、障害物については斜線部で表す。
【００３９】
まず、仮設定ステップＳ３０１において、基板面に相当する仮想平面上において、予め決定されためっき引き出し線の始点から、基板のエッジまで仮ルート（仮ラッツ）を設定する。図１５に示す例では、めっき引き出し線の始点Ｓが図示のように予め決定されており、仮ルートＸは図中点線で表されるように設定される。
【００４０】
次いで、カウントステップＳ３０２において、仮ルートと、他の既存配線との交差回数をカウントする。図１５に示す例では、仮ルートと既存配線Ｗとは３回交差する。
【００４１】
カウントステップＳ３０２でカウントされた交差回数が奇数の場合は、置換ステップＳ３０３において、仮ルートを、他の既存配線の両端の端子を通過する仮ルートに置き換え、カウントステップＳ３０２へ戻る。
【００４２】
カウントステップＳ３０２でカウントされた交差回数が偶数の場合は、さらなる仮設定ステップＳ３０４において、始点と、他の配線の屈曲点と、仮ルートの基板のエッジとの交点と、を結ぶさらなる仮ルートを設定すると、図１５の仮ルートＸは、図１６に示すように、仮ルートＸ１および仮ルートＸ２に置き換えられる。
【００４３】
次いで、設定ステップＳ３０５において、さらなる仮設定ステップＳ３０４において設定されたさらなる仮ルートのうち、始点と、仮ルートの基板のエッジとの交点と、の距離が短い方を修正対象ルートとして設定する。図１６の例では、例えば図１７に示しように仮ルートＸ２が修正対象ルートＧとして設定される。
【００４４】
次いで、修正ステップＳ３０６において、修正対象ルートを、配線設計上の障害となり得る障害物に対して所定のクリアランスを確保する最適なルートに修正する。このとき、ルート修正の基準となった障害物のうち基板のエッジに最も近い障害物の近傍の最適ルート上の点から、基板のエッジに対して直交するルートを設定する。図１７に示す例では、障害物に対して所定のクリアランスを確保するための基準線として補助線Ｈを引き、補助線Ｈ上で、既存配線および／または障害物と修正対象ルートＧとのクリアランスを検査する。このとき、図１７に示すように、ルート修正の基準となった障害物のうち基板のエッジＦに最も近い障害物Ｏの近傍の最適ルート上の点から、基板のエッジＦに対して直交するルートを設定する。これにより、めっき引き出し線の最適ルートが、図１７において太線の実線で示した状態のルートで確定する。その後、このルートについて、他の既存配線との間のクリアランスを確保するように補正を行うと、図１８において太い実線で示されるような最適ルートが得られる。
【００４５】
上述した本実施例による自動配線設計方法は、コンピュータにより実現される。図１９は、記録媒体に格納されたプログラムにより動作するコンピュータの構成を示すブロック図である。
【００４６】
本発明による自動配線設計処理をコンピュータに実行させるプログラムは、図１９に示すように、記憶媒体（フレキシブルディスク、ＣＤ−ＲＯＭ等の外部記憶媒体）１１０に格納されており、例えば、次に説明するような構成によるコンピュータにインストールされて自動配線設計装置として動作する。
【００４７】
ＣＰＵ１１１は、自動配線設計装置全体を制御する。このＣＰＵ１１１に、バス１１２を介してＲＯＭ１１３、ＲＡＭ１１４、ＨＤ（ハードディスク装置）１１５、マウスやキーボード等の入力装置１１６、外部記憶媒体ドライブ装置１１７およびＬＣＤ、ＣＲＴ、プラズマディスプレイ、有機ＥＬ等の表示装置１１８が接続されている。ＣＰＵ１１１の制御プログラムはＲＯＭ１１３に格納されている。
【００４８】
本発明による自動配線設計処理を実行するプログラム（自動配線設計処理プログラム）は、記憶媒体１１０からＨＤ１１５にインストール（記憶）される。また、ＲＡＭ１１４には、自動配線設計処理をＣＰＵ１１１が実行する際の作業領域や、自動配線設計処理を実行するプログラムの一部が記憶される領域が確保されている。また、ＨＤ１１５には、入力データ、最終データ、さらにＯＳ（オペレーティングシステム）等が予め記憶される。
【００４９】
まず、コンピュータの電源を投入すると、ＣＰＵ１１１がＲＯＭ１１０から制御プログラムを読み出し、さらにＨＤ１１５からＯＳを読み込み、ＯＳを起動させる。これによりコンピュータは自動配線設計処理プログラムを記憶媒体１１０からインストール可能な状態となる。
【００５０】
次に、記憶媒体１１０を外部記憶媒体ドライブ装置１１７に装着し、入力装置１１６から制御コマンドをＣＰＵ１１１に入力し、記憶媒体１１０に格納された自動配線設計処理プログラムを読み取ってＨＤ１１５等に記憶する。つまり自動配線設計処理プログラムがコンピュータにインストールされる。
【００５１】
その後は、自動配線設計処理プログラムを起動させると、コンピュータは自動配線設計装置として動作する。オペレータは、表示装置１１８に表示される対話形式による作業内容と手順に従って、入力装置１１６を操作することで、上述した自動配線設計処理を実行することができる。処理の結果得られた「配線の最適ルートに関するデータ」は、例えば、ＨＤ１１５に記憶しておいて後日利用できるようにしたり、あるいは、処理結果を表示装置１１８に視覚的に表示するのに用いてもよい。
【００５２】
なお、図１９のコンピュータでは、記憶媒体１１０に記憶されたプログラムをＨＤ１１５にインストールするようにしたが、これに限らず、ＬＡＮ等の情報伝送媒体を介して、コンピュータにインストールされてもよいし、コンピュータに内蔵のＨＤ１１５に予めインストールされておいてもよい。
【産業上の利用可能性】
【００５３】
本発明は、ＬＳＩやＰＣＢなどの半導体集積回路はもちろん、ＰＢＧＡやＥＢＧＡなどの半導体パッケージ、あるいはＭＣＭ／ＳＩＰなどの配線基板における、演算処理装置を用いた自動配線設計処理に適用することができる。
【００５４】
本発明を配線基板の配線設計に適用すれば、従来のように設計者自らの技量、経験、勘などに左右されることなく、所望の配線ルートを短時間で容易に設計することができる。例えば、従来、試行錯誤しながらの手動による配線設計では数日程度を要していたところが、本発明によれば、数時間程度以下で所望の配線ルートを自動的に設計することができる。このような設計時間の短縮および設計者の負担の軽減の結果、製品の製造コストも低減できる。最適な配線ルートは、配線距離が短いので経済的であり、製造容易であり、そして製造時における製品不良の発生率も低い。また、電気的にも安定した特性を示す。
【図面の簡単な説明】
【００５５】
【図１】本発明の第１の実施例による自動配線設計方法の動作フローを示すフローチャートである。
【図２】本発明の第１の実施例による自動配線設計方法に基づく配線ルート決定の具体例を示す図（その１）である。
【図３】本発明の第１の実施例による自動配線設計方法に基づく配線ルート決定の具体例を示す図（その２）である。
【図４】本発明の第１の実施例による自動配線設計方法に基づく配線ルート決定の具体例を示す図（その３）である。
【図５】本発明の第１の実施例による自動配線設計方法に基づく配線ルート決定の具体例を示す図（その４）である。
【図６】本発明の第１の実施例による自動配線設計方法に基づいて図５のように決定された本通過点を通過する配線ルートの決定の具体例を示す図（その１）である。
【図７】本発明の第１の実施例による自動配線設計方法に基づいて図５のように決定された本通過点を通過する配線ルートの決定の具体例を示す図（その２）である。
【図８】本発明の第１の実施例による自動配線設計方法に基づいて図５のように決定された本通過点を通過する配線ルートの決定の具体例を示す図（その３）である。
【図９】本発明の第２の実施例による自動配線設計方法の動作フローを示すフローチャートである。
【図１０】。本発明の第２の実施例による自動配線設計方法に基づく配線ルート決定の具体例を示す図（その１）である。
【図１１】本発明の第２の実施例による自動配線設計方法に基づく配線ルート決定の具体例を示す図（その２）である。
【図１２】本発明の第２の実施例による自動配線設計方法に基づく配線ルート決定の具体例を示す図（その３）である。
【図１３】本発明の第２の実施例による自動配線設計方法に基づく配線ルート決定の具体例を示す図（その４）である。
【図１４】本発明の第３の実施例による自動配線設計方法の動作フローを示すフローチャートである。
【図１５】本発明の第３の実施例による自動配線設計方法に基づく配線ルート決定の具体例を示す図（その１）である。
【図１６】本発明の第３の実施例による自動配線設計方法に基づく配線ルート決定の具体例を示す図（その２）である。
【図１７】本発明の第３の実施例による自動配線設計方法に基づく配線ルート決定の具体例を示す図（その３）である。
【図１８】本発明の第３の実施例による自動配線設計方法に基づく配線ルート決定の具体例を示す図（その４）である。
【図１９】記録媒体に格納されたプログラムにより動作するコンピュータの構成を示すブロック図である。
【符号の説明】
【００５６】
１１０    記録媒体
１１１    ＣＰＵ
１１２    バス
１１３    ＲＯＭ
１１４    ＲＡＭ
１１５    ハードディスク装置
１１６    入力装置
１１７    外部記憶媒体ドライブ装置
１１８    表示装置
【図１】
2009015366.tif 000003
【図２】
2009015366.tif 000004
【図３】
2009015366.tif 000005
【図４】
2009015366.tif 000006
【図５】
2009015366.tif 000007
【図６】
2009015366.tif 000008
【図７】
2009015366.tif 000009
【図８】
2009015366.tif 000010
【図９】
2009015366.tif 000011
【図１０】
2009015366.tif 000012
【図１１】
2009015366.tif 000013
【図１２】
2009015366.tif 000014
【図１３】
2009015366.tif 000015
【図１４】
2009015366.tif 000016
【図１５】
2009015366.tif 000017
【図１６】
2009015366.tif 000018
【図１７】
2009015366.tif 000019
【図１８】
2009015366.tif 000020
【図１９】
2009015366.tif 000021