(57)【要約】【課題】本発明は、設計ルールのエラーが発生したビアの再配置処理の高速化を実現した複数の配線及び複数のビアを回路設計する方法及びその設計装置を提供する。【解決手段】ＣＡＤシステムで配置済みの複数の配線図形及び複数のビア図形に対し、設計ルールを満たす外郭図形を作成し、この外郭図形の重なりで設計エラーの発生を検出し、設計エラー発生の外郭図形同士でグループを形成し、グループ内の外郭図形による包絡図形Ｅを作成する。該包絡図形の範囲内で、設計エラー発生のビア図形Ｖ２を、配置済みの配線Ｅ１〜Ｅ３にできるだけ影響を与えないで、移動方向Ｄ９に沿って移動させ、配置設計条件Ａ１、Ａ２を満たす位置に再配置する。該移動の結果、設計エラーとなるビア図形Ｖ３を包絡図形の範囲内で移動方向Ｄ１０に沿って移動させる。【選択図】図９
2007287023.tif 000002
【特許請求の範囲】
【請求項１】
複数の配線及び複数のビアを配線基板に配置設計する配線設計方法において、
配置された前記配線に係る配線図形及び前記ビアに係るビア図形について、前記配線及び前記ビアの配置設計条件を示す距離に基づいた拡大オフセットによって外郭図形を作成するステップと、
前記配置設計条件を満たさない当該ビア図形を、他の配線図形及び他のビア図形について作成された前記外郭図形に重ならない位置に移動又は変更させて配置するステップと、
を有することを特徴とする配線設計方法。
【請求項２】
作成された前記外郭図形から抽出された外郭線に基づいて抽出図形を作成し、該抽出図形に対して前記当該ビア図形の半径に基づいた縮小オフセットを行うことによって配置可能境界図形を作成するステップを有し、
前記移動ステップにおいて、前記当該ビア図形の中心を前記配置可能境界図形の範囲内の位置に移動配置させることを特徴とする請求項１に記載の配線設計方法。
【請求項３】
指定された当該ビア図形を中心とし、該ビア図形と隣接する他のビア図形との距離を半径とする検索範囲で前記配線図形を検索するステップを有し、
検索できた前記検索範囲内に含まれ又は交差する前記配線図形の前記外郭図形に基づいて前記抽出図形を作成し、該抽出図形に対して前記当該ビア図形の半径に基づいた縮小オフセットを行うことによって前記配置可能境界図形を作成し、
前記当該ビア図形の中心を前記配置可能境界図形の範囲内の位置に移動配置させることを特徴とする請求項２に記載の配線設計方法。
【請求項４】
前記配置可能境界図形に複数の頂点が存在する場合、当該ビア図形が最初に配置された位置に最も近い前記頂点に当該ビア図形の中心を移動させることを特徴とする請求項３に記載の配線設計方法。
【請求項５】
作成された複数の前記外郭図形のうちで、少なくとも一部が重なる該外郭図形のグループを形成するステップと、
前記グループ形成された少なくとも２以上の前記外郭図形に対する包絡図形を作成するステップと、
前記包絡図形の範囲内で、前記配置設計条件を満たさない前記当該ビア図形を移動させるステップと、
を有することを特徴とする請求項１に記載の配線設計方法。
【請求項６】
前記移動ステップにおいて、前記当該ビア図形を移動したとき、前記包絡図形内の他の配線図形又は他のビア図形との間で前記配置設計条件を満たさない場合に、該他の配線図形又は他のビア図形に係る前記外形図形を前記包絡図形の範囲内で変更又は移動させることを特徴とする請求項５に記載された配線設計方法。
【請求項７】
複数の配線及び複数のビアを配線基板に配置設計する配線設計装置において、
前記配線及び前記ビアに係る前記配線基板上での配置設計条件を格納した記憶手段と、
配線に係る配線図形及びビアに係るビア図形を、配置指示に従って画面上に表示する配置処理手段と、
配置された前記配線図形及び前記ビア図形について、該当する前記配線及び前記ビアの配置設計条件を示す距離を前記記憶手段から読み出し、該距離に基づいた拡大オフセットによって外郭図形を作成する外郭図形作成手段と、
前記配置設計条件をみたさない当該ビア図形を、他の配線図形及び他のビア図形について作成された前記外郭図形に重ならない位置に変更又は移動させて配置する図形移動手段と、
を備えたことを特徴とする配線設計装置。
【請求項８】
作成された前記外形図形から抽出された外郭線に基づいて抽出図形を作成し、該抽出図形に対して前記当該ビア図形の半径に基づいた縮小オフセットによって配置可能境界図形を作成する境界図形作成手段を備え、
前記図形移動手段は、前記当該ビア図形の中心を前記配置可能境界図形の範囲内の位置に変更又は移動配置させることを特徴とする請求項７に記載の配線設計装置。
【請求項９】
指定された当該ビア図形と隣接する他のビア図形との距離を演算し、当該ビア図形を中心とし、前記距離を半径とする検索範囲を設定し、該検索範囲内で前記配線図形を検索する検索手段を備え、
前記境界図形作成手段は、検索できた前記検索範囲内に含まれ又は交差する前記配線図形の前記外郭図形から抽出された外郭線に基づいて抽出図形を作成し、該抽出図形に対して前記当該ビア図形の半径に基づいた縮小オフセットによって前記配置可能境界図形を作成することを特徴とする請求項８に記載の配線設計装置。
【請求項１０】
作成された複数の前記外郭図形のうちで、少なくとも一部が重なる該外郭図形のグループを形成するグループ形成手段と、
前記グループ形成された少なくとも２以上の前記外郭図形に対する包絡図形を作成する包絡図形作成手段と、を備え、
前記移動手段は、前記包絡図形の範囲内で、前記前記ビア図形を移動させたとき、前記包絡図形内の他の配線図形又は他のビア図形が前記配置設計条件を満たさない場合に、該他の配線図形又は他のビア図形に係る前記外形図形を前記包絡図形の範囲内で移動させることを特徴とする請求項７に記載された配線設計装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、半導体パッケージの配線基板やプリント配線基板などに複数の配線及び／又は複数のビアを配置設計する配線設計方法及びその設計装置に関し、特に、配線及びビアに対する設計ルールを満足することが保証できる領域を設定し、基板面上に既に配置された配線及びビアに影響を与えることなく、該領域内の配線及びビアの変更又は再配置を高速処理できる配線設計方法及びその設計装置に関する。
【背景技術】
【０００２】
半導体集積回路（ＬＳＩ）の半導体パッケージの配線基板や、プリント回路基板（ＰＣＢ）などにおいては、配線の各セグメントは直線状の線分で形成され、これら各セグメントが９０度もしくは４５度の方向に連なるようにして配線を設計するのが一般的である。ＬＳＩの配線基板や、ＰＣＢなどでは、配線周辺部のスペースに比較的余裕があり、配線にとって邪魔になる障害物の配置位置や形状がある程度の規則性を有しているという配線的特徴から、多層配線基板やＰＣＢなどの配線設計については、コンピュータによる設計処理が可能となるような設計ルール化が容易であり、既に、コンピュータ設計処理の手法が、いくつか提案されている。
【０００３】
例えば、ＬＳＩ配線やＰＣＢのための自動配線手法の代表的なものとして、迷路探索法と呼ばれる手法がある。この迷路探索法では、基板上において、配線のルートを、障害物とのクリアランスを保つように、かつ、障害物に対しては９０度の方向に、場合によっては４５度の方向に迂回させることで当該障害物と交差しないように設定する。
【０００４】
これに対し、ＰＢＧＡやＥＢＧＡなどの半導体集積回路実装パッケージ（以下、単に「半導体パッケージ」と称する。）では、その基板上には、プレーン（Ｐｌａｎｅ）、ゲート（Ｇａｔｅ）、マーク（Ｍａｒｋ）、パッケージ内部品もしくは他の配線などといったような、配線にとって障害物となり得るものが多数存在し、その障害物の形状、配置位置、或いは、配置角度も多種多様である。
【０００５】
また、配線の始点又は終点となるべきビア（Ｖｉａ）、ボール（ｂａｌｌ）、ボンディングパッド（Ｂ／Ｐ）、或いは、フリップチップパッド（Ｆ／Ｃ）などの位置も様々であり、配線の周辺部に十分なスペースを確保できないことも多い。それ故、半導体パッケージの配線設計においては、半導体パッケージの基板面上において任意の角度方向に配線することが多い。半導体パッケージの配線設計においては、設計者自身が、例えば、ＣＡＤシステムを用いて、仮想平面上で半導体パッケージの配線のルートを、自らの技量や経験や勘を頼りに試行錯誤しながら、配線設計が行われるのが一般的である。
【０００６】
半導体パッケージの配線設計方法として、例えば、ＣＡＤシステムを用いて、例えば、ビアの周辺部に設計ルールに基づいた円弧を発生させ、この円弧の接線に基づき配線を結合していくことで、設計ルールを満たした配線形状を自動演算処理により生成する自動配線方法が提案されている。
【０００７】
また、例えば、自動演算処理によらず、手動で経路概略を作成し、半導体素子以外の半導体素子を障害物とみなした場合に最適な経路を決定する半自動配線方法も提案されている。また、例えば、特定の角度方向の配線を実現する半導体パッケージの配線設計方法も提案されている。
【０００８】
以上の他に、コンピュータを使用した自動配線では配線経路が見つからない場合が発生して、未配線が発生し、或いは、配線長が必要以上に長くなってしまうという問題を解決する半導体集積回路の設計装置及び設計方法が提案されている（例えば、特許文献１を参照）。この設計方法を適用したＣＡＤシステムでは、配線に関する設計ルールを満足し、配線長及び未配線が少ない配線をより短時間で設計することができる。
【０００９】
このＣＡＤシステムは、半導体基板上に配置された素子間を接続するための配線を、ビア同士の最小間隔を定めた設計ルールを無視した状態で、各配線の方向に応じた配線層を用いて設計している。設計された配線中で、前記最小間隔より狭い間隔で配置されている各ビアを検出し、検出されたビアの１つずつを対象ビアとして順次選択し、選択されたビアにより接続されている配線同士を、他の配線と交差することなく、いずれか一方の側の配線層に形成することが可能であるか否かを判定する。その判定の結果、可能であれば該当する配線同士をその配線層に形成するとともに、対象ビアを削除するよう配線の設計を変更する。
【００１０】
【特許文献１】特開平１０−６５００７号公報
【発明の開示】
【発明が解決しようとする課題】
【００１１】
以上のように、特許文献１によって提案された半導体集積回路の設計装置及び設計方法では、半導体パッケージやＰＣＢの設計を行う場合、ビアは設計ルールを満たすように、その配置が決定され、設計ルールを満たさない場合には、ビアの配置位置を移動し、或いは、配線層を移動させることで、配線の交差を解消するようにしている。
【００１２】
そして、全ての設計ルールにエラーがあるビアについて、配線上に障害物があるかどうかが調べられ、障害物が無い場合には、配線層を移動することでビアを削除する。全ての設計ルールにエラーが移動できない場合には、その配線処理を終了させる。ここで、設計ルールを満たそうとするには、手動によるビア配置の変更処理が必要となる。
【００１３】
ところで、この提案された半導体集積回路の設計装置及び設計方法における配線処理では、設計ルールにエラーがある一つのビアのみに注目しているため、実際には、ビアを配置できるスペースが有る場合でも、配線処理を終了してしまうことがあった。例えば、障害物により配線層を変更できず、一層のみで交差しない配線の経路を決定しなければならないような場合が有り得る。
【００１４】
この例では、ある配線上においてはビアが設計ルールを満たせないが、その両側の配線に挟まれているために、該ビアを移動できず、かつ、その両側もビアを移動できないことが有り得る。このビアの移動方向を限定されない場合でも、注目している配線の両側で移動できないときには、このビアを移動させることができない。そのため、上述の半導体集積回路の設計装置及び設計方法には、これらの問題があるため、手動によるビア又は配線の移動、変更が必要となり、設計の効率を向上できず、処理の高速化を図ることができない。
【００１５】
そこで、本発明は、複数の配線及び／又は複数のビアを回路基板に配置設計するとき、配線及びビアに関する設計ルールを満たすことを確保できる領域を作成することにより、該領域内だけで、設計ルールのエラーが発生したビアの再配置処理を行えばよく、該領域外の配置に影響を与えないようにして、配置処理の高速化を実現した配線設計方法及びその設計装置を提供することを目的とする。
【課題を解決するための手段】
【００１６】
以上の課題を解決するため、本発明による複数の配線及び複数のビアを配線基板に配置設計する配線設計方法では、配置された前記配線に係る配線図形及び前記ビアに係るビア図形について、前記配線及び前記ビアの配置設計条件を示す距離に基づいた拡大オフセットによって外郭図形を作成するステップと、前記配置設計条件を満たさない当該ビア図形を、他の配線図形及び他のビア図形について作成された前記外郭図形に重ならない位置に移動又は変更させて配置するステップと、を有する。
【００１７】
そして、作成された前記外郭図形から抽出された外郭線に基づいて抽出図形を作成し、該抽出図形に対して前記当該ビア図形の半径に基づいた縮小オフセットを行うことによって配置可能境界図形を作成するステップを有し、前記移動ステップにおいて、前記当該配線図形の中心線又は前記当該ビア図形の中心を前記配置可能境界図形の範囲内の位置に移動配置させることを特徴とした。
【００１８】
さらに、指定された当該ビア図形を中心とし、該ビア図形と隣接する他のビア図形との距離を半径とする検索範囲で前記配線図形を検索するステップを有し、検索できた前記検索範囲内に含まれ又は交差する前記配線図形の前記外郭図形に基づいて前記抽出図形を作成し、該抽出図形に対して前記当該ビア図形の半径に基づいた縮小オフセットを行うことによって前記配置可能境界図形を作成し、前記当該ビア図形の中心を前記配置可能境界図形の範囲内の位置に移動配置させることとし、前記配置可能境界図形に複数の頂点が存在する場合、当該ビア図形が最初に配置された位置に最も近い前記頂点に当該ビア図形の中心を移動させることとした。
【００１９】
また、本発明の他の配線設計方法では、作成された複数の前記外郭図形のうちで、少なくとも一部が重なる該外郭図形のグループを形成するステップと、前記グループ形成された少なくとも２以上の前記外郭図形に対する包絡図形を作成するステップと、前記包絡図形の範囲内で、前記配置設計条件を満たさない前記当該ビア図形を移動させるステップとを有することとし、さらに、前記移動ステップにおいて、前記当該ビア図形を移動したとき、前記包絡図形内の他の配線図形又は他のビア図形との間で前記配置設計条件を満たさない場合に、該他の配線図形又は他のビア図形に係る前記外形図形を前記包絡図形の範囲内で変更又は移動させることとした。
【００２０】
また、本発明による複数の配線及び複数のビアを配線基板に配置設計する配線設計装置においては、前記配線及び前記ビアに係る前記回路基板上での配置設計条件を格納した記憶手段と、配線に係る配線図形及びビアに係るビア図形を、配置指示に従って画面上に表示する配置処理手段と、配置された前記配線図形及び前記ビア図形について、該当する前記配線及び前記ビアの配置設計条件を示す距離を前記記憶手段から読み出し、該距離に基づいた拡大オフセットによって外郭図形を作成する外郭図形作成手段と、前記配置設計条件をみたさない当該ビア図形を、他の配線図形及び他のビア図形について作成された前記外郭図形に重ならない位置に変更又は移動させて配置する図形移動手段と、を備えた。
【００２１】
そして、作成された前記外形図形から抽出された外郭線に基づいて抽出図形を作成し、該抽出図形に対して前記当該ビア図形の半径に基づいた縮小オフセットによって配置可能境界図形を作成する境界図形作成手段を備え、前記図形移動手段は、前記当該ビア図形の中心を前記配置可能境界図形の範囲内の位置に変更又は移動配置させることとした。
【００２２】
さらに、指定された当該ビア図形と隣接する他のビア図形との距離を演算し、当該ビア図形を中心とし、前記距離を半径とする検索範囲を設定し、該検索範囲内で前記配線図形を検索する検索手段を備え、前記境界図形作成手段は、検索できた前記検索範囲内に含まれ又は交差する前記配線図形の前記外郭図形から抽出された外郭線に基づいて抽出図形を作成し、該抽出図形に対して前記当該ビア図形の半径に基づいた縮小オフセットによって前記配置可能境界図形を作成することとした。
【００２３】
また、本発明による他の配線設計装置においては、作成された複数の前記外郭図形のうちで、少なくとも一部が重なる該外郭図形のグループを形成するグループ形成手段と、前記グループ形成された少なくとも２以上の前記外郭図形に対する包絡図形を作成する包絡図形作成手段と、を備え、前記移動手段は、前記包絡図形の範囲内で、前記配線図形又は前記ビア図形を移動させ、前記配線図形又は前記ビア図形を移動したとき、前記包絡図形内の他の配線図形又は他のビア図形が前記配置設計条件を満たさない場合に、該他の配線図形又は他のビア図形に係る前記外形図形を前記包絡図形の範囲内で移動させることとした。
【発明の効果】
【００２４】
以上のように、本発明の配線設計方法及びその設計装置によれば、ＣＡＤシステムによる配置済みの配線図形及びビア図形の夫々について、設計ルールを満たす外郭図形を作成し、この外郭図形に基づいて設計エラーの発生を検出し、設計エラーが発生している外郭図形同士でグループを形成し、このグループ形成された外郭図形による包絡図形を作成するようにしたので、この包絡図形の範囲内で、配置済みの配線にできるだけ影響を与えることなく、ビア及び配線を設計することができ、複数のビアに関する再配置が自動的に実行される。そして、配置済みの配線に対する再計算の必要が無く、高速な配置計算を行うことができる。
【００２５】
また、本発明の別の配線設計方法及びその設計装置によれば、ＣＡＤシステムによる配置済みの配線図形及びビア図形の夫々について、設計エラーが発生しているビア図形を中心にして配線検索範囲を設定し、この検索範囲に含まれる配線図形に係る外郭図形に基づいて設計ルールを満たすビアに関する配置可能境界図形を作成するようにしたので、設計エラーが発生したビア図形について、設計ルールを満たす再配置の位置を、この配置可能境界図形の範囲内において簡単に決定することができ、ビア再配置処理の自動化を図ることが容易となる。
【発明を実施するための最良の形態】
【００２６】
次に、本発明による配線設計方法及びその設計装置の実施形態について、添付した図を参照して説明するが、本発明の効果をより明確にするため、既に提案されている配線設計手法について、図１及び図２に示された具体例を参照しながら、以下に説明する。
【００２７】
図１は、配線設計を行うことができるＣＡＤシステムの表示装置に映し出された配線設計時の画面を表している。図１に示された画面例は、基板上に、障害物Ｃ１乃至Ｃ３が存在する場合であって、これらの障害物の間に、３本の配線と３個のビアを配置する設計状態が表示されている。３本の配線が配線図形Ｗ１乃至Ｗ３として、また、３個のビアがビア図形Ｖ１乃至Ｖ３としてそれぞれ表示され、配置されている。
【００２８】
これまでのＣＡＤシステムでは、グリッド間隔を、隣接するグリッドに配線同士又は配線とビアとのみが配置可能な大きさに設定した上で配線が行われる。この場合、隣接するグリッド上にビア同士を並べて配置すると、ビアとビアとが接近し過ぎて、ビアのセパレーションに関する設計ルールを満たさなくなる。このため、このＣＡＤシステムでは、特にこの様なビアのセパレーションに関する設計ルールを一旦無視して、隣接するグリッド上でも、ビアを並べて配置することを許可して配線が行われる。
【００２９】
この状態が、図１に示されている。配線図形Ｗ１乃至Ｗ３が障害物Ｃ１乃至Ｃ３を回避して配線され、それらの配線に関連してビア図形Ｖ１乃至Ｖ３が配置されている。しかし、ここでは、ビアのセパレーションに関する設計ルールが無視されて配置されているため、例えば、ビア図形Ｖ２に関する設計ルール、即ち、配置設計条件範囲Ａ１が、隣接する他のビア図形Ｖ１とビア図形Ｖ３の一部に重なっている。なお、実線で示された配置設計条件範囲Ａ１は、ビアとビア間の設計ルールの範囲を表し、破線で示された配置設計条件範囲Ａ２は、ビアと配線間の設計ルールの範囲を表している。
【００３０】
図１に示した例の場合では、ビア図形Ｖ２に係る配置設計条件範囲Ａ１がビア図形Ｖ１とビア図形Ｖ３の一部に重なって、設計ルールを満たしていない。そして、ビア図形Ｖ２に係る配置設計条件範囲Ａ２について見ると、配線図形Ｗ３とは重なってなく、配線図形Ｗ１と重なった部分があり、設計ルールを満たしていない。
【００３１】
そこで、配線工程終了後、セパレーションに関する設計ルールに違反しているビアについて検出する。この設計ルールに違反しているビア図形の削除が行われた後、再度、セパレーションに関する設計ルールを満たしていないビア図形を検出する。図１に示された例では、その様なビア図形は存在しないが、この様なビア図形が存在する場合には、そのビアに相互に接続されている配線について、いずれか一方の配線を他方の配線と同一の配線層に変更できるかどうかが調べられる。
【００３２】
一方の配線を他方の配線と同一の配線層に変更できる場合には、その配線の配線層を変更するとともに、両配線を接続するビアを削除する。このビアが削除された後においても、未だ設計ルールを満たしていないビアがある場合には、そのビアについて、設計ルールを満たす位置まで移動可能かどうかが調べられる。ここで、移動可能な場合には、当該ビアを、その位置まで移動させることにより、設計ルールの違反を除去する。
【００３３】
図１に示された具体例を用いて、設計ルールを満たしていないビアが移動可能かどうかを調べる様子が、図２に示される。図２では、ビア図形Ｖ２が設計ルールを満たしていない場合の例が示されている。図示された矢印Ｄ１乃至Ｄ８のように、ビア図形Ｖ２が、グリッドを中心として、８方向に、設計ルールを満たしている位置まで移動可能か否かが調べられる。
【００３４】
設計ルールを満たしている位置まで移動可能か否かを調べるとき、８方向としたのは、設計配置されるビアの形状が、８角形であり、配線も直線的に配置されていることが多いためであり、その辺毎に行われることが都合よいためである。例えば、ビアが円形である場合には、８方向であっても、任意の方向であってもよい。
【００３５】
図２に示すように、ビア図形Ｖ２は、配線図形Ｗ１、Ｗ３について、そして、ビア図形Ｖ１、Ｖ３について、設計ルールを満たしていない状況にある。ビア図形Ｖ１、Ｖ３は、現時点では、障害物Ｃ１乃至Ｃ３のために移動させることができない。さらに、ここでは、他層へのビアの移動も行えないものとする。この様な状況下で、ビア図形Ｖ２が設計ルールを満たしていないことを解消するために、移動方向Ｄ１乃至Ｄ８に従って、設計ルールを満たすか否かが調べられる。
【００３６】
しかし、図２に示される配置関係の下で、８方向で、設計ルールを満たすか否かが調べられるが、障害物を越えてビアを配置することができない場合には、設計ルールを満たす位置を求めることができない。そこで、これまでのＣＡＤシステムでは、このビアについて、設計ルールを満たす配置を手動で、ビア配置を行わなければならない。この手動によってビア配置を行うことは、作業者自らの技量や経験や勘を頼りに試行錯誤しながら、配線設計が行われることになり、配線及びビアの配置設計の自動化に問題があった。
【００３７】
そこで、本発明では、設計ルールを満たしていないビアに係る再配置の手動作業を必要としない、ビア配線及びビアの配置設計の自動化を図るため、配線図形及びビア図形に基づいて、設計ルールを満たすことが確保される領域を作成するようにし、該領域外の配線済み配線に影響を与えず、ビアの再配置を容易に実行できるようにした。
【００３８】
以下に、本発明による複数の配線及び／又は複数のビアを配線基板に配置設計する配線設計方法及びその設計装置について、第１実施形態と第２実施形態とに分けて説明する。
【００３９】
〔第１実施形態〕
第１実施形態の配線設計手法では、設計ルールを満たすことが確保される領域として、先ず、配置済みの配線図形及びビア図形の夫々について、設計ルールを満たす外郭図形を作成し、この外郭図形に基づいて設計エラーの発生を検出し、設計エラーが発生している外郭図形同士でグループを形成し、このグループ形成された外郭図形による包絡図形を作成するようにした。この包絡図形の範囲内であれば、ビアの再配置のために移動を簡単に行うことができる。
【００４０】
第１実施形態の配線設計手法は、ＣＡＤシステムを基礎とした配線設計装置で実現される。本実施形態の配線設計装置の概略ブロック構成が、図３に示される。この配線設計装置は、制御部２を有する配線設計制御装置１、入力手段３、表示装置４、設計ルールを格納した記憶手段５、ＣＡＤデータを格納した記憶手段６を備えている。なお、設計ルールとＣＡＤデータは、共通の記憶手段に格納されてもよい。
【００４１】
配線設計制御装置１の内部に備えられた制御部２は、配線設計処理部２０、ビア配置設計処理部２１、ビア移動処理部２２、配線変更処理部２３、外郭図形作成部２４、設計エラー検出部２５、そして包絡図形作成部２６で構成されている。配線設計処理部２０、ビア配置設計処理部２１、ビア移動処理部２２及び配線変更処理部２３は、ＣＡＤシステムに元々備えられた機能を奏するものである。
【００４２】
次に、第１実施形態の配線設計手法について、図４及び図５のフローチャートと、図６乃至図８の表示装置４における画面例を参照しながら、以下に説明する。
【００４３】
図４のフローチャートに従うと、先ず、図１に示される画面例のように、配線設計処理部２０が、配線図形Ｗ１乃至Ｗ３について、障害物Ｃ１乃至Ｃ３を回避させながら配置し、表示装置４の画面に表示する（ステップＳ１）。次いで、ビア配置設計処理部２１が、配置した配線図形Ｗ１乃至Ｗ３に関連付けてビア図形Ｖ１乃至Ｖ３を配置する（ステップＳ２）。
【００４４】
次に、外郭図形作成部２４は、配置された配線図形Ｗ１乃至Ｗ３と、ビア図形Ｖ１乃至Ｖ３の夫々について、記憶手段５から読み出した当該配線及び当該ビアに係る設計ルールを読み出し、該設計ルールを満たす距離ｒ１、ｒ２に基づいて、配線図形Ｗ１乃至Ｗ２とビア図形Ｖ１乃至Ｖ３の外形線について拡大オフセットを実行し、夫々の外郭図形Ｆ１乃至Ｆ３を作成する（ステップＳ３）。
【００４５】
図６に、配線図形Ｗ１と、これに接続されるビア図形Ｖ１とについて、外郭図形Ｆ１を作成した例を示めした。配線図形Ｗ１に関しては、該図形の外形線が最小限の設計ルールによる配置設計条件である距離ｒ１で拡大オフセットされ、ビア図形Ｖ１に関しては、該図形の外形線が最小限の設計ルールによる配置設計条件である距離ｒ２で拡大オフセットされ、外郭図形Ｆ１が作成される。ここで、ビア図形Ｖ１が円形でなく、多角形を有する場合には、ビア図形Ｖ１に係る外郭図形も多角形状となる。
【００４６】
図６の外郭図形Ｆ１は、代表的に作成の様子を示したものであり、他の配線図形及び他のビア図形についても、同様の手法により、外郭図形Ｆ２、Ｆ３が作成される。図１に示された画面例の場合について、外郭図形Ｆ１乃至Ｆ３が作成された様子が、画面の表示例として図７に示されている。
【００４７】
ここで、設計エラー検出部２５は、作成された複数の外郭図形に基づいて、配置済みの配線及びビアが設計ルールを満たしてしるか否かを検査する（ステップＳ４）。図７に示されるように、隣り合う外郭図形Ｆ１とＦ２、Ｆ２とＦ３に互いに重なりが発生している場合に、設計ルールが満たされていないとされる。
【００４８】
先ず、例えば、外郭図形Ｆ１に注目し、他の外郭図形Ｆ２との間で、ビア部分が互いに重なっていることが検出されると（ステップＳ４のＮ）、包絡図形作成部２６は、外郭図形が重なっているもの同士でグループ形成を行う（ステップＳ５）。次いで、全てのビアについて、設計ルールを満たしているか否かの処理がされたかが判断される（ステップＳ６）。
【００４９】
図７の例に従えば、次の外郭図形Ｆ２に注目すると、他の外郭図形Ｆ３との間で、ビア部分が互いに重なっていることが検出されるので、ステップＳ５において、外郭図形Ｆ３をグループに追加処理を行う。そこで、包絡図形作成部２６は、このグループ形成された複数の外郭図形に基づいた包絡線による包絡図形Ｅを作成する（ステップＳ５）。
【００５０】
一方、図７の例では、設計ルールを満たした外郭図形が存在しないが、ステップＳ４において、設計ルールを満たしている、即ち、隣り合う外郭図形Ｆ１とＦ２、Ｆ２とＦ３におけるビア部分が互いに重なっていない場合には（ステップＳ４のＹ）、包絡線によるグループへの追加処理を行う必要が無いので、ステップＳ５の処理工程を経ずに、ステップＳ６に移行する。設計ルールを満たしている状態においては、図６に示されるように、外郭図形が単独に存在することになる。
【００５１】
ここで、図７に示されるように、外郭図形Ｆ１乃至Ｆ３による包絡図形Ｅが作成されると、次に、図５に示されるフローチャートに従って、包絡図形Ｅ内の設計エラーを検出して、ビア配置の再設計と、配線の再設計とが行われる。
【００５２】
先ず、設計エラー検出部２５は、包絡図形Ｅに含まれる複数の外郭図形における重なりをチェックする（ステップＳ１１）。そして、この重なり部分が多い外郭図形に係るビア図形について、設計ルールのエラーがあるか否かを判断する（ステップＳ１２）。例えば、図８に示されるように、ビア図形Ｖ２には、配置設計条件範囲Ａ１に関して、ビア図形Ｖ１とＶ３とに対して設計エラーが発生しており、そして、配置設計条件範囲Ａ２に関して、配線図形Ｗ１に対して設計エラーが発生していることが検出される。
【００５３】
ここで、ビア図形Ｖ２について、設計エラーがあると判断された場合には（ステップＳ１２のＹ）、ビア移動処理部２２は、ビア図形Ｖ２を、ビア図形Ｖ２に係る配線図形Ｗ２上に沿って移動させる。ここで、ビア図形Ｖ２は、ビアに関する設計ルールである配置設計条件範囲Ａ１及びＡ２を満たす位置に移動される。この移動処理の様子が、図９に示されている。
【００５４】
図９では、ビア図形Ｖ２の移動方向が、矢印Ｄ９で示されている。ここで、ビア図形の中心が配線図形上にあることを条件としているため、ビア図形は、配線図形に沿って移動されるものとしている。例えば、図９に示されるように、矢印Ｄ９の方向に、ビア図形Ｖ２が移動されると、ビア図形Ｖ１に対しては、配置設計条件範囲Ａ１、Ａ２が一応満たされる。しかし、ビア図形Ｖ３に対しては、設計エラーが発生する。
【００５５】
そのため、設計エラー検出部２５がこのビア図形Ｖ３に対する設計エラーを検出すると、ビア移動処理部２２は、図９に示されるように、ビア図形Ｖ２に係る配置設計条件範囲Ａ１の外側に位置するように、ビア図形Ｖ３を配線図形Ｗ３に沿って矢印Ｄ１０の方向に移動させる処理を実行する（ステップＳ１３）。なお、ビア図形Ｖ２の移動するだけで、包絡図形内のビア図形のいずれもが設計ルールを満たす場合には、他のビア図形の移動は行われない。
【００５６】
ところで、図９に示されるように、ビア図形Ｖ２の再配置の影響を受けて、ビア図形Ｖ３を移動させた結果、今度は、ビア図形Ｖ３に設計ルールのエラーが発生する。そこで、ビア移動処理部２２は、ビア図形Ｖ３を、包絡図形Ｅの範囲内で、配置設計条件範囲Ａ１及びＡ２を満足する位置に移動させる。この場合、ビア図形の中心が配線図形上に位置させるという原則は崩れる。
【００５７】
この原則を維持するために、作業者によって、入力手段３から配線図形Ｗ３の変更処理が指示されると、配線図形Ｗ３をビア図形Ｖ３の中心を通るように変更され、配線の再設計が実行される（ステップＳ１４）。ここで、設計エラー検出部２５が、包絡図形内において設計エラーを検出した場合に、当該図形について、その表示色を他と異ならせ、又は、図形表示を点滅させるなど、強調表示すると、作業者に設計エラーが発生したことを報知することができる。或いは、音や、音声により報知してもよい。この報知により、作業者が配置処理の状況を把握することができ、配線図形を再設計する必要性を認識できる。
【００５８】
次いで、処理の対象となった包絡図形内の重なりについて全てチェックが終了していない場合には（ステップＳ１５のＮ）、ステップＳ１１に戻って、ビア配置の再設計処理と、配線の再設計処理が実行される。図７及び図８に示された例の場合には、形成グループが一つであったが、実際の配線設計の場合には、複数の形成グループが作成されるので、これら全てのグループについて、上述したステップＳ１１からステップＳ１５までの処理が繰り返して実行される（ステップＳ１６）。
【００５９】
以上に説明した第１実施形態の処理手順によれば、ＣＡＤシステムによる配置済みの配線図形及びビア図形の夫々について、設計ルールを満たす外郭図形を作成し、この外郭図形に基づいて設計エラーの発生を検出し、設計エラーが発生している外郭図形同士でグループを形成し、このグループ形成された外郭図形による包絡図形を作成するようにしたので、この包絡図形の範囲内で、配置済みの配線にできるだけ影響を与えることなく、ビア及び配線を設計することができ、複数のビアに関する再配置を自動的に実行される。そして、配置済みの配線に対する再計算の必要が無く、高速な配置計算を行うことができる。
【００６０】
〔第２実施形態〕
第１実施形態の配線設計手法では、ビア及び配線に係る設計ルールを確保できる領域として、ビア図形及び配線図形に係る外郭図形に基づいて包絡図形を作成するようにしたが、第２実施形態の配線設計手法では、ビア及び配線に係る設計ルールを確保できる領域として、ビア図形及び配線図形に係る外郭図形から抽出された外郭線に基づいて抽出図形を作成し、該抽出図形に対して当該ビア図形の半径に基づいた縮小オフセットを行うことによって配置可能境界図形を作成することとした。
【００６１】
第２実施形態の配線設計手法がＣＡＤシステムを基礎とした配線設計装置で実現されることは、第１実施形態の場合と同様であり、本実施形態の配線設計装置の概略ブロック構成が、図１０に示される。この配線設計装置は、制御部２を有する配線設計制御装置１、入力手段３、表示装置４、設計ルールを格納した記憶手段５、ＣＡＤデータを格納した記憶手段６を備えている。なお、設計ルールとＣＡＤデータは、共通の記憶手段に格納されてもよい。
【００６２】
配線設計制御装置１の内部に備えられた制御部２が、配線設計処理部２０、ビア配置設計処理部２１、ビア移動処理部２２、配線変更処理部２３、外郭図形作成部２４、設計エラー検出部２５を有している点では、図３に示された第１実施形態の場合と同様であるが、包絡図形作成部２６の代わりに、検索範囲設定部２７、ビア再配置可能領域作成部２８、そしてビア再配置決定部２９を備えている。
【００６３】
次に、第２実施形態の配線設計手法について、図１１のフローチャートと、図１２乃至図１５の表示装置４における画面例を参照しながら、以下に説明する。図１２乃至図１５に示された画面例では、複数の配線と複数のビアとが配置済であるが、複数のビアのうちの一つのビアに関して設計ルールのエラーが発生しており、当該ビアを設計ルールを満たすように移動して再配置する場合を例にしている。
【００６４】
第２実施形態の配線設計手法では、ビア図形及び配線図形の配置設計工程は、第１実施形態の場合と同様である。図１１のフローチャートに従うと、先ず、図１２に示される画面例のように、配線設計処理部２０が、配線図形Ｗ１１、Ｗ２１、Ｗ３１、・・・について、障害物（図１２では、図示を省略）を回避させながら配置し、表示装置４の画面に表示する（ステップＳ１）。次いで、ビア配置設計処理部２１が、ビア図形Ｖ１１、Ｖ２１、・・・を配置する（ステップＳ２）。
【００６５】
次に、外郭図形作成部２４は、配置された配線図形Ｗ１１、Ｗ２１、Ｗ３１、・・・と、ビア図形Ｖ１１、Ｖ２１、・・・の夫々について、記憶手段５から読み出した当該配線及び当該ビアに係る設計ルールを読み出し、該設計ルールを満たす距離ｒ１、ｒ２に基づいて、配線図形とビア図形の外形線について拡大オフセットを実行し、夫々の外郭図形Ｆ１１、Ｆ２１、Ｆ３１、・・・を作成する（ステップＳ３）。
【００６６】
ここで、図１２の例では、ビア図形Ｖ２１に設計ルールのエラーが発生しているので、設計エラー検出部２５は、該ビア図形Ｖ２１に係る外郭図形を削除する。そして、検索範囲設定部２７が、ビア図形Ｖ２１を中心にして、当該ビア図形に隣接する他のビア図形との距離を半径とした検索範囲を指定する（ステップＳ２１）。図１２において、この検索範囲が、実線の円で示されている。なお、この検索範囲を表示装置４の画面にも表示することができる。
【００６７】
そこで、検索範囲設定部２５は、指定した検索範囲内の領域に含まれるか、又は交差している配線図形を検索する（ステップＳ２２）。図１２の例に拠れば、この検索範囲内の領域に含まれ、又は交差する配線図形として、配線図形Ｗ１１、Ｗ２１、Ｗ３１が検索される対象となる。そこで、この検索範囲内に配線データがあるか否かが判断される（ステップＳ２３）。なお、検索範囲内に配線データが存在しない場合には（ステップＳ２３のＮ）、ビア再配置処理を終了する。
【００６８】
ここで、検索範囲内に配線データがあると判断された場合には（ステップＳ２３のＹ）、設計エラーが発生しているビア図形Ｖ２１を挟む配線図形Ｗ２１とＷ３１に係る外郭図形Ｆ２１とＦ３１とに基づいて、設計ルール保持境界線を作成する（ステップＳ２４）。
【００６９】
この設計ルール保持境界線の作成の様子が、図１３に示されている。先ず、外郭図形Ｆ２１と３１とに関して、ビア図形Ｖ２１が存在する側の外形線に含まれる各線分を一方向のベクトルで表す。円弧が含まれている場合には、円弧の始点と終点を直線で結び、線分と同様に扱う。外郭図形Ｆ２１に関して、ベクトルｖ２１、ｖ２２、ｖ２３、・・・と表せ、外郭図形Ｆ３１に関して、ベクトルｖ３１、ｖ３２、ｖ３３、・・・と表せるものとする。
【００７０】
ここで、各ベクトルから見て、ビア図形Ｖ２１の中心Ｐ１が一定に見える箇所を、注目する線分として抽出する。図１２の場合には、例えば、ベクトルｖ２１から見て、中心Ｐ１は左側にあるので、この場合、中心Ｐ１がベクトルの左側にある線分、円弧だけを取り出す。同様にして、外郭図形Ｆ３１についても、ベクトルｖ３２から見て、中心Ｐ１の右側にある線分、円弧だけを取り出す。そこで、取り出された線分、円弧を注目領域における設計ルール保持境界線とする。この様にして作成された設計ルール保持境界線が、図１４に示されている。図１４に示された例では、この設計ルール保持境界線として、Ｆ２１及びＦ３１で示される。
【００７１】
この様にして取り出された両側の線分、円弧の全ての組に対して、指定した設計ルールを満たす線分・円弧の組を選択するが、全ての組み合わせで、設計ルール以上の間隔になる組が見つからなければ、この領域内には、設計ルールを満たすビアを配置することができないことを意味する。なお、線分・円弧の各終端が一点で接続している場合には、それらの端点を接続し、線分・円弧をそれぞれ結んだ両端点が離れているときには、該両端点間を直線で結び、これらの線分・円弧で作成された領域を、ビア図形配置の検索領域とし、設計ルール保持境界線となる。
【００７２】
次いで、ステップＳ２４において、設計ルール保持境界線が作成されると、ビア再配置可能領域作成部２８は、この設計ルール保持境界線に基づいて、ビア配置可能領域に係るビア配置検索範囲を示す図形とする（ステップＳ２５）。そして、このビア配置検索範囲図形に基づいて、ビア図形の中心を再配置のための移動させる範囲を限定するビア配置可能境界線を作成する（ステップＳ２６）。
【００７３】
ここで、設計ルール保持境界線は、近接する配線図形の外形線から設計ルールで指定された距離だけ内方にオフセットされた線である。そのため、この線上にビア図形の外形線が接するように配置した場合には、指定された設計ルールを満たしたビアの配置が可能になる。それ故、設計ルール保持境界線について、当該ビア図形の半径を距離とする内方へのオフセットを行い、ビア配置可能境界図形を作成すれば、この図形の外形線、即ち、境界線の内側のどこに、ビア図形の中心を配置しても、当該ビアは、設計ルールを満たすことになる。
【００７４】
図１４に示されるように、ビア配置可能領域作成部２８によって作成された配置可能境界図形ＦＯが、設計ルール保持境界線Ｆ２１とＦ３１で囲まれる領域内に表示される。そこで、ビア再配置決定部２９は、作成された配置可能境界図形ＦＯに基づいて、ビア図形Ｖ２１について、設計ルールを満たす位置に再配置が可能な境界線上の頂点を検索する（ステップＳ２７）。なお、図１４の例では、配置可能境界図形ＦＯが作成できた場合が示されているが、配線図形Ｗ２１とＷ３１との配置間隔が元々狭い場合には、この配置可能境界図形は作成されないので、このときには、ビア再配置決定部２９は、ビア再配置の処理を実行しない。
【００７５】
ビア再配置決定部２９は、作成された配置可能境界図形ＦＯに基づいて、ビア図形２１の再配置を実行する。ところで、前述したように、ビア図形Ｖ２１については、配置可能境界図形ＦＯの範囲内のどこでも再配置可能であるが、自動的にビアの再配置を実行できるように、配置可能境界図形ＦＯの外形線上に形成された複数の頂点を再配置候補とし、当該ビア図形の最初の中心位置に最も近い箇所にある頂点を選択して、ビア図形の再配置位置と決定することとした。
【００７６】
そこで、ステップＳ２７において、図１４の例であれば、配置可能境界図形ＦＯにおけるビア配置可能な頂点ｐ１乃至ｐ５が再配置候補として検出され、頂点ｐ１から順に頂点ｐ５について、ビア図形Ｖ２の現在位置との距離が演算される。そして、ビア再配置決定部２９は、現在のビア図形Ｖ２１の中心位置に最も近い箇所にある再配置候補をビアの移動先として、頂点ｐ２を選定し、ビア図形Ｖ２１の移動先に決定する（ステップＳ２８）。さらに、図１５に示されるように、ビア移動処理部２２は、決定された移動先である頂点ｐ２に移動処理を実行する。この頂点ｐ２が、再配置後のビア図形Ｖ２１の中心Ｐ２となる。
【００７７】
なお、ステップ２７において、各頂点と当該ビア図形との距離を演算し、ステップＳ２８において、この演算された距離に基づいて最も近い位置にある頂点を選定するようにしたが、この手法の代わりに、境界線上の再配置可能な頂点毎に、当該ビア図形の中心を逐一移動させ、その都度、ビア配置可能かをチェックし、該頂点では配置できない場合には、次に近い位置にある頂点でチェックを繰り返すこともできる。これらの頂点の集合の中でビアを配置できない場合には、自動では、ビア再配置を決定できないものとして、ビア再配置処理を終了する。
【００７８】
以上に説明した第２実施形態の処理手順によれば、ＣＡＤシステムによる配置済みの配線図形及びビア図形の夫々について、設計ルールを満たす外郭図形を作成し、この外郭図形に基づいて設計エラーの発生を検出し、設計エラーが発生しているビア図形を中心にして配線検索範囲を設定し、この検索範囲に含まれる配線図形に係る外郭図形に基づいて設計ルールを満たすビアに関する配置可能境界図形を作成するようにしたので、設計エラーが発生したビア図形について、設計ルールを満たす再配置の位置を、この配置可能境界図形の範囲内において簡単に決定することができ、ビア再配置処理の自動化を図ることが容易となる。
【図面の簡単な説明】
【００７９】
【図１】半導体パッケージにおける集積回路の設計例を説明する図である。
【図２】設計エラーが発生したビアの移動修正を説明する図である。
【図３】本発明の第１実施形態による配線設計方法を実現するための配線設計装置の概略構成を説明する図である。
【図４】包絡線を作成するための処理手順を説明するフローチャートである。
【図５】包絡線内に発生している設計エラーを解消する処理手順を説明するフローチャートである。
【図６】第１実施形態において、基本となる設計された配線及びビアに関する設計ルールを満足する領域を説明する図である。
【図７】第１実施形態を適用する場合、複数の配線及びビアが近接配置された場合における設計ルールを満足する領域と包絡線について説明する図である。
【図８】図７に示された包絡線内において、設計ルールが満足されない状態が発生していることを説明する図である。
【図９】第１実施形態における配線設計方法を適用し場合における設計エラーを解消する手法を説明する図である。
【図１０】本発明の第２実施形態による配線設計方法を実現するための配線設計装置の概略構成を説明する図である。
【図１１】図９のフローチャートにおけるビア配置の再設計工程に関する詳細な処理手順を説明するフローチャートである。
【図１２】設計例に検索範囲を設定した状態を説明する図である。
【図１３】設計ルール保持境界線を作成する処理について説明する図である。
【図１４】ビア配置可能領域の境界線の作成について説明する図である。
【図１５】ビア配置可能領域の境界線に従ってビアを移動は位置した状態を説明する図である。
【符号の説明】
【００８０】
１    配線設計制御装置
２    制御部
２０    配線設計処理部
２１    ビア配置設計処理部
２２    ビア移動処理部
２３    配線変更処理部
２４    外郭図形作成部
２５    設計エラー検出部
２６    包絡図形作成部
２７    検索範囲設定部
２８    ビア再配置可能領域作成部
２９    ビア再配置決定部
３    入力手段
４    表示装置
５、６    記憶手段
Ａ１、Ａ２    配置設計条件範囲
Ｃ１〜Ｃ３    障害物図形
Ｄ１〜Ｄ１０    移動方向
Ｅ    包絡図形
Ｆ１〜Ｆ３、Ｆ１１〜Ｆ３１    外郭図形
ＦＯ    配置可能境界図形
ｐ１〜ｐ５    頂点
ｒ１、ｒ２    距離
Ｖ１〜Ｖ３、Ｖ１１、Ｖ２１、Ｖ２２    ビア図形
Ｗ１〜Ｗ３、Ｗ１１〜Ｗ３１    配線図形
【図１】
2007287023.tif 000003
【図２】
2007287023.tif 000004
【図３】
2007287023.tif 000005
【図４】
2007287023.tif 000006
【図５】
2007287023.tif 000007
【図６】
2007287023.tif 000008
【図７】
2007287023.tif 000009
【図８】
2007287023.tif 000010
【図９】
2007287023.tif 000011
【図１０】
2007287023.tif 000012
【図１１】
2007287023.tif 000013
【図１２】
2007287023.tif 000014
【図１３】
2007287023.tif 000015
【図１４】
2007287023.tif 000016
【図１５】
2007287023.tif 000017