(57)【特許請求の範囲】
【請求項１】
記憶装置を有するコンピュータで実行され、複数の端子群を含むパッケージにおいて配線開始端子から終端端子に向かって順次にネットを発生する、多端子ネット自動発生方法であって、
（ａ）前記配線開始端子を含む第１の端子群とその次の第２の端子群との間の結線データを初期データとして前記記憶装置に記憶し、前記記憶装置から前記コンピュータに入力するステップと、
（ｂ）前記コンピュータで、前記パッケージ上の部品を対象としてドローネの三角形分割処理を実行するステップと、
（ｃ）前記コンピュータで、前記第１の端子群と、前記第２の端子群の次に位置する第３の端子群とを対象として、前記第２の端子群を無視して２端子ネット発生処理を実行するステップと、
（ｄ）前記コンピュータで、前記初期データと前記２端子ネット発生処理の結果とを合成することにより暫定ネットを発生するステップと、
（ｅ）前記コンピュータで、当該パッケージの設計ルールを満たすように前記暫定ネットを修正して前記記憶装置に書き込むステップとを含み、
前記ステップ（ｅ）は、
前記ドローネの三角形分割処理で生成された全三角形分割辺上の交差経路を決定するステップと、
各三角形分割辺について交差経路の容量が超過していないかどうかを調べるステップと、
前記交差経路の容量が超過していた場合に、当該三角形分割辺の端点にある部品を、当該三角形分割辺上において前記部品の最も近くを通過する他の経路上の関連部品と入れ替えるステップとを含む、
多端子ネット自動発生方法。
【請求項２】
記憶装置を有するコンピュータで実行され、複数の端子群を含むパッケージにおいて配線開始端子から終端端子に向かって順次にネットを発生する、多端子ネット自動発生方法であって、
（ａ）前記配線開始端子を含む第１の端子群とその次の第２の端子群との間の結線データを初期データとして前記記憶装置に記憶し、前記記憶装置から前記コンピュータに入力するステップと、
（ｂ）前記コンピュータで、前記パッケージ上の部品を対象としてドローネの三角形分割処理を実行するステップと、
（ｃ）前記コンピュータで、前記第１の端子群と、前記第２の端子群の次に位置する第３の端子群とを対象として、前記第２の端子群を無視して２端子ネット発生処理を実行するステップと、
（ｄ）前記コンピュータで、前記初期データと前記２端子ネット発生処理の結果とを合成することにより暫定ネットを発生するステップと、
（ｅ）前記コンピュータで、当該パッケージの設計ルールを満たすように前記暫定ネットを修正して前記記憶装置に書き込むステップとを含み、
前記ステップ（ｅ）は、
前記ドローネの三角形分割処理で生成された全三角形分割辺上の交差経路を決定するステップと、
各三角形分割辺について交差経路の容量が超過していないかどうかを調べるステップと、
前記交差経路の容量が超過していた場合に、当該三角形分割辺の端点にあり且つネットが割り当てられていない部品を、当該三角形分割辺上において前記部品の最も近くを通過する経路上の関連部品と入れ替えるステップとを含む、
多端子ネット自動発生方法。
【請求項３】
前記交差経路の容量が超過していた場合に、当該三角形分割辺の端点にある部品がピン交換可能かどうかを調べるステップを含む、請求項１又は２に記載の方法。
【請求項４】
複数の端子群を含むパッケージにおいて配線開始端子から終端端子に向かって順次にネットを発生する、多端子ネット自動発生装置であって、
（ａ）前記配線開始端子を含む第１の端子群とその次の第２の端子群との間の結線データを初期データとして入力する手段と、
（ｂ）前記パッケージ上の部品を対象としてドローネの三角形分割処理を実行する手段と、
（ｃ）前記第１の端子群と、前記第２の端子群の次に位置する第３の端子群とを対象として、前記第２の端子群を無視して２端子ネット発生処理を実行する手段と、
（ｄ）前記初期データと前記２端子ネット発生処理の結果とを合成することにより暫定ネットを発生する手段と、、
（ｅ）当該パッケージの設計ルールを満たすように前記暫定ネットを修正する手段とを含み、
前記手段（ｅ）は、
前記ドローネの三角形分割処理で生成された全三角形分割辺上の交差経路を決定する手段と、
各三角形分割辺について交差経路の容量が超過していないかどうかを調べる手段と、
前記交差経路の容量が超過していた場合に、当該三角形分割辺の端点にある部品を、当該三角形分割辺上において前記部品の最も近くを通過する他の経路上の関連部品と入れ替える手段とを含む、
多端子ネット自動発生装置
【請求項５】
複数の端子群を含むパッケージにおいて配線開始端子から終端端子に向かって順次にネットを発生する、多端子ネット自動発生装置であって、
（ａ）前記配線開始端子を含む第１の端子群とその次の第２の端子群との間の結線データを初期データとして入力する手段と、
（ｂ）前記パッケージ上の部品を対象としてドローネの三角形分割処理を実行する手段と、
（ｃ）前記第１の端子群と、前記第２の端子群の次に位置する第３の端子群とを対象として、前記第２の端子群を無視して２端子ネット発生処理を実行する手段と、
（ｄ）前記初期データと前記２端子ネット発生処理の結果とを合成することにより暫定ネットを発生する手段と、、
（ｅ）当該パッケージの設計ルールを満たすように前記暫定ネットを修正する手段とを含み、
前記手段（ｅ）は、
前記ドローネの三角形分割処理で生成された全三角形分割辺上の交差経路を決定する手段と、
各三角形分割辺について交差経路の容量が超過していないかどうかを調べる手段と、
前記交差経路の容量が超過していた場合に、当該三角形分割辺の端点にあり且つネットが割り当てられていない部品を、当該三角形分割辺上において前記部品の最も近くを通過する経路上の関連部品と入れ替える手段とを含む、
多端子ネット自動発生装置
【請求項６】
前記交差経路の容量が超過していた場合に、当該三角形分割辺の端点にある部品がピン交換可能かどうかを調べる手段を含む、請求項４又は５に記載の装置。
【請求項７】
請求項１乃至３のいずれかに記載の方法を実行するためのプログラムを記憶したプログラム記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、半導体チップなどのパッケージにおける多端子ネットの自動発生に関するものであり、特に、シングルチップパッケージにおいて結線可能で且つ冗長経路を含まない一筆書きの多端子ネットを自動的に発生する技術に関する。
【０００２】
【従来の技術】
ＣＰＵ、ＡＳＩＣに代表されるチップパッケージ部品は、実装技術の進歩により目覚しい高速化・高密度化が実現されてきている。これは近年の電子機器製品の高性能化・小型化に最も影響を及ぼしている要素技術の一つである。しかしながら今日の製品の多様化や製品のライフサイクルの短縮により、製品開発の現場において高性能な自動設計システム類は欠く事の出来ない必須のツールとなっている。
【０００３】
そのような自動設計の一つにチップパッケージ内の配線処理がある。この配線処理には、決められた結線指示情報（ネット）に基き各配線経路を導き出すネット配線処理と、配線可能な結線指示情報自体を発生しながら配線経路を導くネット発生処理があるが、本発明は後者の処理に適用されるものである。
【０００４】
パッケージ配線は一般に中央に配置されたベアチップ（チップ本体）側の端子（ボンディングパッド）群から、外周に整列配置されたピン群（あるいはビアと呼ばれる層間接続部品）に向かって放射状に配線が施される。その配線パターンの条件として、
・結線が可能であること。
・総配線長が極力短くなること。
・設計ルール（配線間隔、部品との間隔等）を満たすこと。
・冗長経路を含まないこと。
が上げられる。
【０００５】
上述のようなパッケージ配線を実現するための既存技術として２端子のネット発生アルゴリズムというものが存在する。それは結線対象を二つの端子群（ソース及びシンク）に分け、各群で任意の要素をダイクストラ法等の最短経路探索法を用いて仮接続し、そこで生成した経路と他の経路との交差を解消することで最終的に全結線対象に対して配線可能なネットが生成される、というものである。例えば、日本国特許第２９３８４３１号には、チップ上のパッドの配置、パッケージのピン配置、パッドとピンとの対応関係等を示すデザイン情報を読み込み、解析して配線問題を作成し、更に、パッドとピンとをソース要素とシンク要素とに分類し、互いに配線されるパッドとピンとに同じ識別番号を連続的に付与した上で、ソース要素及びシンク要素に対してドローネの三角形分割法を適用することにより、ソース／シンク要素等を頂点とする仮想的な三角形を作成し、それらの三角形を用いてピンをレベル分類し、三角形の辺と配線とが交差するかを判定し、交差すると判定した辺の間を接続して配線の経路を導出し、配線設計の結果を出力するようにした技術が開示されている。
【０００６】
また、特開平１１−２９６５６０号公報には、上述の日本国特許と同様にデザイン情報を読み込み、解析して配線問題を作成し、半導体パッケージのボンディングパッド及びピンを互いに対応づけた上で、経路の監視に用いる監視辺を任意のシンク要素及び配線禁止領域の間に作成し、次に、ダイクストラ法等により配線経路の探索を交差を許して行い、監視辺と交差する場合には候補経路の長さを係数により重み付けした評価値を算出し、評価値が最低の値を取る候補経路を部分経路として選択し、最後に配線結果を出力するようにした技術が開示されている。
【０００７】
【発明が解決しようとする課題】
一般のシングルチップパッケージの配線とは、基板中央に配置されたベアチップの周囲に配置されているワイヤボンディングパッドから外周方向に配置されたピン部品（ビアを含む）へ向かって放射状に配線が施されるものである。前述の２端子ネット発生アルゴリズムはワイヤボンディングパッド群（ソース）とピン部品群（シンク）で結線対象を２分類して処理されるものである。しかし、実際のチップパッケージ設計においては、チップの製造上の理由から、ソースからシンクに向かった経路をさらにパッケージ外周のメッキ端子にまで引き出す必要があるものが少なくなく、ここまでを全て自動化しようとした場合（３端子以上のネット自動発生）、現状の最短経路探索と交差解消の組み合わせを拡張しても、交差経路の対象によって頻繁に経路探索処理が発生する（処理時間の増大）、結線解が導ける保証が無い、といった困難が予想される。従って現場の設計者はこのメッキ端子までのリード線の引き出し作業について、ほとんど手作業で行っている。
【０００８】
図１に示す簡単な例で説明する。図１において、Ａ〜Ｆは、出力端子（パッド）群と入力端子（メッキ端子）群との間にあるピン等の部品を示しており、矢印付きの実線１〜６は、出力端子群からそれらの部品を介して入力端子群に至る経路を示している。２端子ネットの自動発生を単純に２回繰り返すことによって３端子ネットを構成すると、部品ＣＦ間の配線容量が１００％であった場合、部品Ｄを通過する経路が導けなくなる（ネットが発生できない）。そうすると、部品ＣＦ間に起因する全ネットを見直し、配線可能なネットに修正する必要があるが、最適なネット修正方法の定義、経路探索の必要性、経路探索における冗長回路（回り込み）の発生の制御、経路の評価、といった問題が出てくる。更に、ネットを修正後、ネット付き配線処理を行うことになるが、十分にネットを検討しないと、結線解を導ける保証がなく、また、結線解を見ながら処理を繰り返すことになるため、初めから手作業でやった方が速い。当然、手作業ということになると、設計者に負担がかかることになる。
【０００９】
従って本発明の目的は、配線可能で且つ冗長経路を含まない多端子ネットを、経路探索処理なしに高速に導出することにある。
【００１０】
本発明の他の目的は、前記多端子ネットを高速に導出するための多端子ネット自動発生方法を提供することにある。
【００１１】
本発明の他の目的は、前記多端子ネットを高速に導出するための多端子ネット自動発生装置を提供することにある。
【００１２】
本発明の他の目的は、前記多端子ネットを高速に導出するための多端子ネット自動発生方法を実行するプログラムを記憶したプログラム記憶媒体を提供することにある。
【００１３】
【課題を解決するための手段】
本発明によれば、Ｎ端子（Ｎは３以上の整数）のネットを自動発生する場合、パッケージの所与の設計ルールを満たした（Ｎ−１）端子の結線データを初期データとして入力し、次に配線開始点の端子群と、ネット発生対象であるＮ端子目の端子群とを対象として、中間の端子群を無視して２端子ネット発生処理を実行する。そして初期データと、２端子ネット発生処理の実行結果とを合成することにより暫定ネットを発生し、この暫定ネットをパッケージの設計ルールを満たすように修正する。これによりＮ端子のネットが自動的に発生される。上記の（Ｎ−１）が３以上の場合は、初期データとして入力される結線データを本発明に従って発生する必要がある。
【００１４】
従って、本発明の第１の態様は、複数の端子群を含むパッケージにおいて配線開始端子から終端端子に向かって順次にネットを発生する、多端子ネット自動発生方法であって、
（ａ）前記配線開始端子を含む第１の端子群とその次の第２の端子群との間の結線データを初期データとして入力するステップと、
（ｂ）前記第１の端子群と、前記第２の端子群の次に位置する第３の端子群とを対象として、前記第２の端子群を無視して２端子ネット発生処理を実行するステップと、
（ｃ）前記初期データと前記２端子ネット発生処理の結果とを合成することにより暫定ネットを発生するステップと、
（ｄ）当該パッケージの設計ルールを満たすように前記暫定ネットを修正するステップと、
を含み、４端子以上の多端子ネットの場合は、前記（ｄ）のステップで修正された暫定ネットを前記初期データとして入力して、第４の端子群以降に対して、前記（ｂ）〜（ｄ）のステップを繰り返すことを特徴としている。
【００１５】
本発明の第２の態様は、複数の端子群を含むパッケージにおいて配線開始端子から終端端子に向かって順次にネットを発生する、多端子ネット自動発生装置であって、
（ａ）前記配線開始端子を含む第１の端子群とその次の第２の端子群との間の結線データを初期データとして入力する手段と、
（ｂ）前記第１の端子群と、前記第２の端子群の次に位置する第３の端子群とを対象として、前記第２の端子群を無視して２端子ネット発生処理を実行する手段と、
（ｃ）前記初期データと前記２端子ネット発生処理の結果とを合成することにより暫定ネットを発生する手段と、、
（ｄ）当該パッケージの設計ルールを満たすように前記暫定ネットを修正する手段とを含み、
４端子以上の多端子ネットの場合は、前記（ｄ）の手段で修正された暫定ネットを前記初期データとして入力して、第４の端子群以降に対して、前記（ｂ）の手段による２端子ネット発生処理、前記（ｃ）の手段による暫定ネットの発生及び前記（ｄ）の手段による暫定ネットの修正を繰り返し実行することを特徴としている。
【００１６】
本発明の第３の態様は、第１の態様における多端子ネットの自動発生方法を実行するためのプログラムを記憶したプログラム記憶媒体である。
【００１７】
【発明の実施の形態】
以下、図面を参照しながら、本発明の好適な実施形態について説明する。以下では、パッケージの内側（パッド）から外側（メッキ端子）に向けて３端子ネットを発生する例を説明するが、ネットの発生は外側から内側に向けてもよく、また４端子以上のネット発生の場合は、以下に説明するプロセスを繰り返すだけでよい。
【００１８】
図２は、本発明を実施するためのコンピュータネットワーク１の構成を例示する図である。図示のように、コンピュータネットワーク１は、ｎ台のクライアントコンピュータ１０、通信回線１８およびサーバコンピュータ２０から構成される（但し、図１はｎ＝１の場合を例示）。通信回線１８は、データ通信が可能なＬＡＮ、データ専用回線、ＩＳＤＮ回線あるいは電話回線等あって、クライアントコンピュータ１０とサーバコンピュータ２０との間でデータを伝送する。
【００１９】
図３は、図２に示したクライアントコンピュータ１０とサーバコンピュータ２０との間の機能分担を例示する図である。図３の例では、コンピュータネットワーク１において、クライアントコンピュータ１０は、半導体チップの設計を行なうＣＡＤソフトウェア１２０を実行し、サーバコンピュータ２０は、半導体チップパッケージにおいて多端子ネットを自動的に発生する配線設計ソフトウェア３を実行する。なお、本発明にかかる多端子ネットの自動発生は、図３に例示した構成の他、同一のコンピュータが、ＣＡＤソフトウェア１２０と配線設計ソフトウェア３とを実行する構成によっても実現されうる。
【００２０】
クライアントコンピュータ１０は、図２に示すように、コンピュータ本体１００、ＣＲＴ表示装置あるいは液晶表示装置等のディスプレイ装置１０２、入力装置１０４、プリンタ装置およびプロッタ装置等を含む出力装置１１０、ハードディスク装置あるいは光磁気（ＭＯ）ディスク装置等の記憶装置１１２、および、通信装置１１４から構成される。
【００２１】
入力装置１０４は、キーボード１０６およびマウス１０８等を含み、ユーザの操作に応じて半導体回路の設計あるいは設計変更に必要な情報、および、半導体パッケージのピン配置に関する情報を受け入れ、コンピュータ本体１００に対して出力する。
【００２２】
記憶装置１１２は、図３に示したＣＡＤソフトウェア１２０、入力装置１０４を介して入力された情報、ＣＡＤソフトウェア１２０により設計された半導体回路を示す情報、設計した半導体回路を実際の半導体チップとして実現した場合の回路配置情報、サーバコンピュータ２０から伝送されてきた配線情報等のデータを記憶し、記憶したデータを、要求に応じてコンピュータ本体１００に対して出力する。
【００２３】
通信装置１１４は、イ−サネットアダプタ、トークンリングアダプタ、ＦＤＤＩ、ＴＡあるいはモデム等であって、コンピュータ本体１００の制御に従って、通信回線１８を介して、クライアントコンピュータ１０とサーバコンピュータ２０との間のデータ伝送を行なう。
【００２４】
コンピュータ本体１００は、ＣＰＵ、メモリおよびこれらの周辺回路等から構成され、いわゆるパーソナルコンピュータあるいはワークステーションとしての機能を有し、クライアントコンピュータ１０の各構成部分を制御する。また、コンピュータ本体１００は、図２に示したＣＡＤソフトウェア１２０を記憶装置１１２からメモリにロードして実行し、以下の各処理を行なう。
【００２５】
コンピュータ本体１００は、入力装置１０４を介して入力された半導体回路の設計に必要な情報に基づいて半導体回路を設計し、さらに、設計した半導体回路の回路配置およびボンディングパッドの配置を設計し、ディスプレイ装置１０２、出力装置１１０および記憶装置１１２に対して出力する。
【００２６】
また、コンピュータ本体１００は、サーバコンピュータ２０による多端子ネット発生のために、固有の部品番号によってそれぞれ識別される多数の部品（ボンディングパッド、ピン、ビア、メッキ端子等）の情報を含む部品情報と、ネットを発生すべきパッケージの設計ルールと、初期ネット情報とをサーバコンピュータ２０に伝送する。詳細については後で説明するが、初期ネット情報は、配線開始端子（パッド）から中間端子（ピン又はビア）にかけての２端子ネットを定義するもので、例えば、前述の日本国特許第２９３８４３１号又は特開平１１２９６５６０号公報に記載の公知の手法で得ることができる。
【００２７】
また、コンピュータ本体１００は、サーバコンピュータ２０から入力された配線結果をディスプレイ装置１０２等に表示してユーザに示す。
【００２８】
サーバコンピュータ２０は、図２に示すように、コンピュータ本体２００、記憶装置２０２および通信装置２０４から構成される。
【００２９】
記憶装置２０２は、図３に示した配線設計ソフトウェア３、クライアントコンピュータ１０から受け取った情報、及び配線結果等を示すデータを記憶し、記憶したデータを、要求に応じてコンピュータ本体２００に対して出力する。
【００３０】
通信装置２０４は、通信装置１１４と同様に、コンピュータ本体２００の制御に従って、通信回線１８を介して、クライアントコンピュータ１０とサーバコンピュータ２０との間のデータ伝送を行なう。
【００３１】
コンピュータ本体２００は、コンピュータ本体１００と同様にＣＰＵ、メモリおよびこれらの周辺回路等から構成され、サーバコンピュータ２０の各構成部分を制御する。
【００３２】
また、コンピュータ本体２００は、図３に示した配線設計ソフトウェア３を記憶装置２０２からメモリにロードして実行し、以下に説明するように、クライアントコンピュータ１０側から伝送されてきた情報に基づいて、多端子ネットを自動的に発生し、それを配線結果としてクライアントコンピュータ１０に対して出力する。
【００３３】
以下、多端子ネットを自動的に発生するためにサーバコンピュータ２０において実行される配線設計ソフトウェア３の処理を説明する。なお、本明細書では、前述のボンディングパッド、ピン、ビア及びメッキ端子をまとめて「端子」と呼び、更に、パッケージ上の配線禁止領域も含めて「部品」と呼ぶことにする。配線禁止領域とは、パッケージ上に配置されたチップの下部領域のように、配線が禁止されている領域のことであり、クライアントコンピュータ１０からの部品情報により指定される。
【００３４】
本発明は以下のようなデータ構造を各ネット情報毎に定義するものである。
（１）結線端子群（Ｎ１）
（２）結線端子群がもつ階層レベル値の中で最小の値（Ｎ２）
（３）結線端子群がもつ階層レベル値の中で最大の値（Ｎ３）
（４）配線の並びの順序を表す値（Ｎ４）
データＮ１は、クライアントコンピュータ１０から入力された初期ネット情報により示される結線端子群がそのまま登録される。データＮ２は各結線端子が持つ階層レベル値の中で最小の値を、Ｎ３は最大の値を保持する。データＮ４は後の処理で定義される。データＮ２及びＮ３の階層レベル並びにデータＮ４の配線の並びの順序については後で説明する。
【００３５】
本発明に従う多端子ネット自動発生の全体的な流れを図４に示す。図４のプロセスは、多端子ネットの発生に必要な初期情報がクライアントコンピュータ１０から入力されると開始される。前述のように、この初期情報は、部品番号により識別される各種端子の情報を含む部品情報、パッド−ピン間の２端子ネットデータ及びパッケージの設計ルールを含む。部品情報は、部品番号の他に、当該部品あるいは端子がピン交換可能かどうかを示す属性を含む。ピン交換については後で説明する。
【００３６】
最初のステップ４０１では、パッケージ上の各部品を対象にドローネの三角形分割処理（Ｄｅｌａｕｎａｙ  ｔｒｉａｎｇｕｌａｔｉｏｎ）が実行される。これは、パッケージの全配線面を、パッドやピンなどの部品構成点を頂点とする三角形で表現するもので、各三角形分割辺上の通過経路を決定するのに使用される。ドローネの三角形分割自体は、前記の日本国特許第２９３８４３１号にも記載されているように公知の技術である。
【００３７】
パッド、ピン及びメッキ端子を対象にしたドローネの三角形分割の簡単な例を図５に示す。一般に、パッドは、パッケージの中央に位置するチップ（図示せず）の周りに並んでおり、ピンは、パッドの外側において複数の行（図示の例では３行）に並んでおり、メッキ端子は、パッケージの外周に並んでいる。ドローネの三角形分割では、一番内側のパッドと一番外側のメッキ端子とを直接結ぶ分割辺はないことに注意されたい。各端子に付されている数字０、１、２・・・は配線の並びの順序を示すもので、同じ番号を持ったパッド及びピンが結線されることを示している。この情報は、クライアントコンピュータ１０から入力された２端子ネットデータから得られる。一番外側にあるメッキ端子は、これからネットを発生されるので、配線の並びの順序を示す番号はこの時点ではまだ与えられていない（ただし、固有の部品番号は与えられている）。配線設計ソフトウェア３は、ドローネの三角形分割処理により、各部品毎に、それが他のどの部品との間に分割辺を有するかという情報を得る。
【００３８】
ドローネの三角形分割が終わると、ステップ４０２に進んで、部品の階層化を行う。この階層化により、配線面上のすべての部品が、基底部品（本実施形態ではパッド）から遠ざかるほど大きな階層レベル値を持つようなデータが構成される。これは、前記の日本国特許第２９３８４３１号に記載の手法で以下のようにして実行できる。
【００３９】
図６は、図４に示した階層化（レベリング）処理４０２を示すフローチャートである。図６に示すように、最初のステップ６０１において、配線設計ソフトウェア３は、結線すべき端子を記憶するためのデータ構造を有するＦＩＦＯ形式の空のキューを作成し、各端子の階層レベルを初期化し（パッドはレベル０、その他はレベル−１）、そしてレベル０のパッドをキュー要素としてその配線の並びの順（図５参照）にキューに入れる。
【００４０】
ステップ６０２において、配線設計ソフトウェア３は、キューが空か否かを判断する。キューが空の場合にはレベリング処理を終了し、空でなければ次のステップ６０３に進んで、キューから要素（Ｐとする）を１つ取り出し、レベリング処理の対象とする。最初に取り出されるのは、図５に示した番号が０のパッドを表す要素である。
【００４１】
ステップ６０４において、配線設計ソフトウェア３は、前のステップ６０３で取り出された要素Ｐを端点とする分割辺（三角形分割処理で得られた情報により特定できる）の内、まだレベリングされていない分割辺（未処理の分割辺Ｅ）があるか否かを判断する。配線設計ソフトウェア３は、未処理の分割辺Ｅがある場合にはステップ６０５に進み、ない場合には、ステップ６０６でその要素をキューから除いた後、ステップ６０２に戻る。
【００４２】
ステップ６０５において、配線設計ソフトウェア３は、ステップ６０３で取り出された要素すなわちレベリングの対象となっている要素Ｐと、他のもう一つの要素（Ｒとする）を両端とする未処理の分割辺Ｅの１つを取り出す。
【００４３】
ステップ６０７において、配線設計ソフトウェア３は、分割辺Ｅに端点として含まれる要素Ｒが既にレベリングされているか否か、つまり、要素Ｒのレベルが不定値（−１）でないか否かを判断する。配線設計ソフトウェア３は、要素Ｒがレベリングされている（レベル値が−１でない）場合にはステップ６０４に戻り、レベリングされていない（レベル値が−１）場合にはステップ６０８に進む。
【００４４】
ステップ６０８において、配線設計ソフトウェア３は、ステップ６０５で取り出された分割辺Ｅの端点の要素Ｒを、要素Ｐのレベル（Ｐ）よりも、一つ高いレベル（Ｐ＋１；Ｒ）にレベリングし、分割辺Ｅと、分割辺Ｅの指標値（両端の要素Ｐ、Ｒのレベルの値の和；Ｐ＋Ｒ＝２Ｐ＋１）とを対応付けて記憶する。さらに、配線設計ソフトウェア３は、その両端の要素がレベリングされた分割辺Ｅを未処理から処理済みに分類変更する。
【００４５】
ステップ６０９において、配線設計ソフトウェア３は、レベルを設定した要素Ｒをキューに入れた後、ステップ６０４に戻る。
【００４６】
以上のプロセスをすべてのキュー要素に対して繰り返すことにより、配線面上の全部品の階層レベル値が得られる。図６の例では、ＦＩＦＯ形式のキューを用いた階層化を行っているが、要素をリストの形で保持するようにしてもよい。その場合、階層レベル０の要素の後に階層レベル１、２・・の要素が順に追加されていくことになる。リストを用いた場合は、図６のステップ６０２及び６０６は不要であり、ステップ６０４からＮＯのパスに出ると、リスト中の次の要素が取り出されることになる。
【００４７】
図４に戻って、以上のようなレベリングすなわち階層化が終わると、次のステップ４０３に進んで、３端子の暫定ネットを発生する。一般に、チップパッケージの配線とは、配線方向が一様（中央から外周に向かう、あるいは外周から中央に向かう）で、迂回等の冗長経路が含まれないものである必要がある。これを上述の階層レベル及び配線の並びに置き換えて考えると、配線方向が階層レベル０から増加方向で、各階層レベルを同じ並びで一度しか通過しない、ということとなる。もし同じ階層レベルを複数回通過すれば冗長な回り込み経路が発生するということになり、パッケージ配線としては不適当なものになる。
【００４８】
これはＮ端子のネット発生においても同様なことが言える。すなわちＮ端子目のネット発生で生成される経路（上記の例では、ピンとメッキ端子の間））においても、各階層レベル１、２、・・上の配線の並びと階層レベル０上の並びとが等しいものである必要がある。これを考慮して、まず、階層レベル０のパッドと階層レベルｎのメッキ端子を対象とした２端子ネット発生を、従来の技術のところで説明したような既存のアルゴリズムで行う。但しこれは中間端子（ピン）群を無視して行う。このネット発生においては各階層レベルを同じ配線の並びで一様に経路が通過することが重要な点である。すなわち同じ配線の並びを保った場合（冗長経路を含まずに）、パッドとメッキ端子の間でどのようなネットが構成できるかが重要で、途中経路で設計ルールを満たす必要はない。したがってこの処理は、設計ルール（配線幅、部品との間隙）を無視、あるいは大幅に緩め、最短経路法と交差解消によるネット発生を行う。
【００４９】
図７に示す簡単な例で説明すると、３端子ネットの発生の場合、配線開始部品となる端子（パッド）群Ａ１、Ａ２、Ａ３から終端部品となる端子（メッキ端子）群Ｃ１、Ｃ２、Ｃ３に対して２端子ネット発生を行い、Ａ１−Ｃ１、Ａ２−Ｃ２、Ａ３−Ｃ３のネットを生成する。このとき、配線開始端子群と中間端子（ピン）群との間におけるＡ１−Ｂ１、Ａ２−Ｂ２、Ａ３−Ｂ３の２端子ネットデータ（初期データとしてクライアントコンピュータ１０から与えられている）は無視する。最後に、こうして得られた２端子ネットＡｉ−Ｃｉと予め与えられているネットＡｉ−Ｂｉを合成することにより、３端子の暫定ネットＡｉ−Ｂｉ−Ｃｉを発生する（ｉ＝１、２、３）。前述のように、暫定ネットを構成する端子Ａｉ、Ｂｉ及びＣｉの配線の並びの順序を示す番号は同じである。言い換えれば、メッキ端子Ｃｉに対しては、このときＡｉ及びＢｉと同じ番号が与えられる。これにより、前述のデータ構造（ＮＥＴ）におけるデータＮ１〜Ｎ４が適宜更新される。
【００５０】
上述の２端子ネット発生で、中間端子群Ｂｉからのネット発生を行わない理由は、もし中間端子群から終端端子群に向けてネットを発生すると、その発生経路によっては、結線解に迂回経路が含まれる可能性があるからである。２端子ネット発生に際して設計ルールを緩めるのも同様な理由からである。
【００５１】
暫定ネットの発生が終わると、ステップ４０４に進んで、全三角形分割辺上の交差経路を決定する。図８に示す簡単な例で説明すると、３端子の暫定ネットでは、同じ配線並び番号を持ったパッド、ピン（又はビア）及びメッキ端子が結線されるが、この結線は、各三角形分割辺において、配線の並びの順序を保つように行われる。例えば、レベル１における番号１及び５のピンの間の分割辺には、番号が２、３及び４の経路が通過（交差）し、従って配線の並びの順序１〜５が保たれている。言い換えれば、特定の三角形分割辺の両端にある端子の配線並び番号をｉ及びｊとすれば、ステップ４０４は、この三角形分割辺上の交差経路として、番号ｉ＋１、ｉ＋２・・ｊ−１の経路を決定する。配線設計ソフトウェア３は、これをすべての三角形分割辺で行った後、暫定ネットが設計ルールを満たしているかどうかをチェックするために、ステップ４０５以降に進む。
【００５２】
配線設計ソフトウェア３は、ステップ４０５ですべての三角形分割辺を調査対象とし、次のステップ４０６でそれらの三角形分割辺を順次に取り出し、ステップ４０７でその三角形分割辺における交差経路の容量が設計ルールをオーバーしていないかどうかを調べる。例えば、設計ルールが交差経路を３本まで許している場合、ステップ４０４で決定された交差経路が２本であれば、ステップ４０７での判断結果はＯＫとなり、ステップ４１１に進むが、もし交差経路が４本であったなら、設計ルールを満たすために、すなわち当該三角形分割辺上の交差経路を３本以下にするために、ステップ４０８に進んで、その両端にある部品がピン交換可能かどうかを調べる。前述のように、クライアントコンピュータから入力される部品情報は、各部品がピン交換可能かどうかを示す属性情報を含んでおり、配線設計ソフトウェア３はこの属性情報を見てステップ４０８の判断を行う。
【００５３】
もしピン交換可能であれば、ステップ４０９に進み、さもなければステップ４１１に進む。ステップ４０９は、容量を超えた経路が通過する三角形分割辺上で、その両端の部品にネットが割り当てられている場合には、関連する二つの部品を交換することによりネット端子を入れ替え、また容量を超えた経路が通過する三角形分割辺上で、その両端の部品の一方又は両方にネットが割り当てられていない場合には、新規割り当てを行う。
【００５４】
ピン交換及び新規割り当ての例をそれぞれ図９及び図１０に示す。図９のピン交換の例では、部品ＣＦ間の容量（通過可能経路数）が３であるにもかかわらず、４本の経路２〜５が通過しているので、まずステップ４０８で部品Ｃ及びＦがピン交換可能属性を持っているかどうかを調べる。この例では、部品Ｆだけがピン交換可能属性を持っていたとする。部品Ｆはネット（経路６）を割り当てられているので、他の部品と交換可能かどうかを調べるため、部品ＣＦ間の三角形分割辺上において部品Ｆの最も近くを通る経路で、Ｆと同じグループ（例えばピングループ）に属する部品が同じくピン交換可能属性を持っているかどうかを調べる。図９の例では、経路５の部品Ｅがピン交換可能属性を持っているので、次にＥとＦを入れ替えることで冗長経路が発生しないかどうかを調べる。もし冗長経路が発生しなければ、ＥとＦを交換した後、ステップ４１０に進む。冗長経路の発生については後で説明する。
【００５５】
図１０の新規割り当ての例では、容量を超えた経路が通過する三角形分割辺の一端にある部品Ａにネットが割り当てられていない。この場合、部品Ａがピン交換可能属性を持っているかどうかをステップ４０８で調べ、もし持っていれば、この三角形分割辺上において部品Ａの最も近くを通る経路で、Ａと同じグループに属する部品が同じくピン交換可能属性を持っているかどうかを調べる。図１０の例では、Ａと同じグループの部品Ｂがピン交換可能属性を持っているので、ＡとＢを入れ替えることで冗長経路が発生しないかどうかを調べ、もし発生しなければ、ＡとＢを交換した後、ステップ４１０に進む。
【００５６】
図９のピン交換及び図１０の新規割り当てのいずれにおいても、二つの部品が入れ替えられているので、それに応じて前述のデータＮ１〜Ｎ４を適宜更新する必要がある。
【００５７】
次に図１１を参照して、冗長経路発生の抑制について説明する。図１１のＡでは、部品ＡＤ間の三角形分割辺上で容量オーバーになっているので、部品ＢとＤの入れ替えを試みる。そして階層レベル（Ｘ＋１）上の経路の並びを調べる。ところが、図１１のＢに示すように、部品ＢとＤを入れ替えると、階層レベル（Ｘ＋１）において経路の並びが５−６−７から６−５−７に変わっており、並びの順序が維持されないので、この交換は許されない。図１１Ｂの現象は、経路６が一旦階層レベル（Ｘ＋１）を横切った後、再び部品Ｂのところで同じ階層レベル（Ｘ＋１）に戻ることで生じている。ステップ４０９では、このような冗長経路が発生しないように、ピン交換又は新規割り当てが行われる。
【００５８】
ステップ４１０では、暫定ネットが修正されたことを示すネット修正フラグが「ＴＲＵＥ」にセットされる。
【００５９】
ステップ４１１では、配線容量が未調査の三角形分割辺があるかどうかを調べ、もしあればステップ４０６に戻り、さもなければステップ４１２に進んで、ネット修正フラグの状態を調べる。フラグが「ＴＲＵＥ」にセットされていると、ステップ４０５に戻って、すべての三角形分割辺を調べ直す。ネット修正フラグが「ＴＲＵＥ」にセットされていなければ、いかなるネット修正も行われなかったことを示しているので、図４のプロセスは終了する。
【００６０】
最後に、図４のステップ４０３における暫定ネットの発生で、ネットが割り当て可能でありながら、いずれのＮＥＴデータにも属していないため、配線並び番号で初期化されない部品が存在する可能性があるので、その対処方法について説明しておく。
【００６１】
多端子ネットの自動発生では、暫定ネットの発生に続く経路同定処理において配線の並び順による初期化は必須であるので、上述のような部品もある番号で初期化する必要がある。そのような場合として、その部品がもつ三角形分割辺の端点のもつ値を収集して仮の値を自身に割り当てることが可能である。
【００６２】
例えば、図１２に示す部品Ｐの初期化には、Ｐの周囲のＫ、Ｌ、Ｍ、Ｎの階層レベル及び初期値を収集する。特にＰの属する階層レベル（図示の例ではレベル２）の辺Ｒ２で接続された初期値（Ｍ：５、Ｎ：１１）を優先的に扱い、Ｐに割り当てられる最も最適な値を算出する。図１２におけるＰには”８”が最適だと算出できる（中間値）。
【００６３】
図１３において、配線開始点となる部品Ｋが配線面における階層レベル２に存在している場合、階層レベル０の辺Ｒ０を横切る経路を持たないため、Ｋの属するネットのデータＮ４（配線並び番号）は初期化されない。しかしここに番号を与えないと静的経路同定方法を適用できない。そこで以下の方法でＫの属するネットのデータＮ４を決定する。
【００６４】
まず最初の暫定ネットによる静的経路同定法を適用する前に、部品Ｋの属する全結線端子を前述のネットが割り当てられていない部品と同じような扱いで仮の番号を割り当て、最初の静的経路同定方法を適用する。この暫定ネットによる経路導出によってえられた経路でＫの属するネットの結線端子の周囲にどのような経路が通過しているかを調べる。Ｋの属するネットの結線端子の中で最も階層レベルが低いもの、すなわちＫをはさんで通過する経路が１２番及び１３番の経路である場合、１３番以上の番号を持つネットを、番号を一つずつ繰り下げ、Ｋのネットを新たに１３番として定義する。以降ＫのデータＮ４は１３として処理を進める。割り当てる番号が決まったら、それを基に、全ネット要素列に対して新規挿入及び再ソーティングを動的に行う。
【００６５】
本発明の多端子ネット自動発生技術を実際に３端子ネットの発生に適用してみたところ、ネット発生後の自動配線も含めて、約１０分で処理が完了した。熟練設計者が手で配線設計した場合は８時間以上を要し、従って前に述べた本発明の目的が十分に達成されていることがわかる。
【００６６】
以上、本発明の良好な実施形態について詳細に説明してきたが、もちろん本発明はそのような実施形態に限定されるものではなく、様々な変更や修正が可能であることは言うまでもない。例えば、前述の実施形態では、３端子ネットを発生していたが、４端子ネットの場合は、実施形態で発生した３端子ネットの情報を初期データとして入力すればよい。あとのプロセスは図４に示した通りである。
【図面の簡単な説明】
【図１】従来の２端子ネット発生技術を多端子ネットの発生に使用した場合の問題を示す図。
【図２】本発明が実施されるコンピュータネットワークの構成を例示する図。
【図３】図２に示したクライアントコンピュータとサーバコンピュータとの間の機能分担を例示する図。
【図４】本発明に従う多端子ネット自動発生のプロセスを示すフローチャート。
【図５】図４における三角形分割処理によって得られたドローネの三角形を例示する図。
【図６】図４における階層化処理を示すフローチャート。
【図７】本発明に従って暫定ネットを発生するときの様子を示す図。
【図８】三角形分割辺上における交差経路の決定を示す図。
【図９】設計ルールを満たすためにピン交換により暫定ネットを修正する様子を示す図。
【図１０】設計ルールを満たすために、新規割り当てにより暫定ネットを修正する様子を示す図。
【図１１】冗長経路発生の様子を示す図。
【図１２】暫定ネットの発生で割り当てが行われなかった部品に対して配線並び番号を割り当てる一手法を示す図。
【図１３】暫定ネットの発生で割り当てが行われなかった部品に対して配線並び番号を割り当てる他の手法を示す図。
【図１】
0003548070.tif 000002
【図２】
0003548070.tif 000003
【図３】
0003548070.tif 000004
【図４】
0003548070.tif 000005
【図５】
0003548070.tif 000006
【図６】
0003548070.tif 000007
【図７】
0003548070.tif 000008
【図８】
0003548070.tif 000009
【図９】
0003548070.tif 000010
【図１０】
0003548070.tif 000011
【図１１】
0003548070.tif 000012
【図１２】
0003548070.tif 000013
【図１３】
0003548070.tif 000014