(57)【要約】【課題】  演算処理で自動的に配線の位置を決定できる自動配線決定処理を実現する。【解決手段】  自動配線決定装置１は、各パッド部と各ビア部とを結ぶ各仮配線のうちの２つが形成する交点と対応の各ビア部との間の各距離を判定し、この距離が長い仮配線を上記距離が短い仮配線の対応のビア部の周りに迂回させて暫定配線とする第１の交点解消処理を、各仮配線が形成する交点の全てについて順次実行する第１の交点解消手段１１と、各暫定配線同士もしくは暫定配線と仮配線とが形成する交点と当該暫定配線もしくは当該仮配線の対応のビア部との間の各距離を判定し、この距離が長い暫定配線もしくは仮配線を上記距離が短い暫定配線もしくは仮配線の対応のビア部の周りに迂回させて最適な配線とする第２の交点解消処理を、各暫定配線同士が形成する交点および暫定配線と仮配線とが形成する交点の全てについて順次実行する第２の交点解消手段１２と、を備える。【選択図】      図１
2006268462.tif 000002
【特許請求の範囲】
【請求項１】
基板上における各パッド部からそれぞれの結線先である各ビア部への最適な配線の位置を、演算処理により自動的に決定する自動配線決定装置であって、
各前記パッド部と各該パッド部のそれぞれの結線先である各前記ビア部とを直線で結んだ各仮配線のうち、２つの前記仮配線が形成する交点を解消するよう、当該交点を形成する一方の前記仮配線を、もう一方の前記仮配線の結線先である前記ビア部の周りに迂回させ、これを暫定配線として確定する第１の交点解消処理を、各前記仮配線が形成する交点の全てについて、前記パッド部に近い前記交点から順次実行する第１の交点解消手段と、
該第１の交点解消手段による前記第１の交点解消処理の完了後、各前記暫定配線同士が形成する交点もしくは前記暫定配線と前記仮配線とが形成する交点を解消するよう、当該交点を形成する一方の前記暫定配線もしくは前記仮配線を、もう一方の前記暫定配線もしくは前記仮配線の結線先である前記ビア部の周りに迂回させ、これを新たなる暫定配線として確定する第２の交点解消処理を、各前記暫定配線同士が形成する交点および前記暫定配線と前記仮配線とが形成する交点の全てについて、前記パッド部に近い前記交点から順次実行する第２の交点解消手段と、を備え、
前記第２の交点解消手段による前記第２の交点解消処理により全ての交点が解消された時点における前記仮配線および／または前記暫定配線を、前記最適な配線として確定することを特徴とする自動配線決定装置。
【請求項２】
基板上における各パッド部からそれぞれの結線先である各ビア部への最適な配線の位置を、演算処理により自動的に決定する自動配線決定装置であって、
各前記パッド部と各該パッド部のそれぞれの結線先である各前記ビア部とを直線で結んだ各仮配線のうち、２つの前記仮配線が形成する交点と、前記２つの仮配線のそれぞれの結線先である各前記ビア部と、の間の各距離の長短を判定し、前記距離が長い方の前記仮配線を、当該交点を解消するよう、前記距離が短い方の前記仮配線の結線先である前記ビア部の周りに迂回させ、これを暫定配線として確定する第１の交点解消処理を、各前記仮配線が形成する交点の全てについて、前記パッド部に近い前記交点から順次実行する第１の交点解消手段と、
該第１の交点解消手段による前記の処理の完了後、各前記暫定配線同士が形成する交点もしくは前記暫定配線と前記仮配線とが形成する交点と、当該暫定配線もしくは当該仮配線の結線先である前記ビア部と、の間の各距離の長短を判定し、前記距離が長い方の前記暫定配線もしくは前記仮配線を、当該交点を解消するよう、前記距離が短い方の前記暫定配線もしくは前記仮配線の結線先である前記ビア部の周りに迂回させ、これを新たなる暫定配線として確定する第２の交点解消処理を、各前記暫定配線同士が形成する交点および前記暫定配線と前記仮配線とが形成する交点の全てについて、前記パッド部に近い前記交点から順次実行する第２の交点解消手段と、を備え、
前記第２の交点解消手段による前記第２の交点解消処理により全ての交点が解消された時点における前記仮配線および／または前記暫定配線を、前記最適な配線として確定することを特徴とする自動配線決定装置。
【請求項３】
前記第１の交点解消手段は、
前記距離が長い方の前記仮配線を当該ビア部の周りに迂回させることにより生成されることになる前記暫定配線が、当該ビア部と該ビア部に隣接する形成物とに対してクリアランスを確保できるか否かを判定する第１の判定手段を有し、
前記第１の交点解消手段は、
前記第１の判定手段が当該暫定配線のままでは前記クリアランスを確保できないと判定した場合は、当該暫定配線に代えて、前記距離が短い方の前記仮配線を、前記距離が長い方の前記仮配線の結線先である前記ビア部の周りに迂回させ、これを新たなる暫定配線として確定し直す請求項２に記載の自動配線決定装置。
【請求項４】
前記第１の交点解消手段は、
迂回すべきとされた前記ビア部に結線された前記距離が短い方の前記仮配線と、該仮配線以外の仮配線と、の交点の数をカウントするカウント手段と、
前記距離が長い方の前記仮配線を当該ビア部の周りに迂回させることにより生成されることになる前記暫定配線が、当該ビア部と該ビア部に隣接する形成物との間のクリアランスを確保できるか否かを、該カウント手段によりカウントされた交点の数に基づいて判定する第２の判定手段と、を有し、
前記第１の交点解消手段は、
前記第２の判定手段が当該暫定配線のままでは前記クリアランスを確保できないと判定した場合は、当該暫定配線に代えて、前記距離が短い方の前記仮配線を、前記距離が長い方の前記仮配線の結線先である前記ビア部の周りに迂回させ、これを新たなる暫定配線として確定し直す請求項２に記載の自動配線決定装置。
【請求項５】
前記第１の交点解消手段は、前記暫定配線を、迂回すべきとされた前記ビア部上を通るように仮配置し、
前記第２の交点解消手段は、仮配置された前記暫定配線について前記第２の交点解消処理を実行して確定された前記暫定配線を、迂回すべきとされた前記ビア部上を通るように仮配置する請求項１または２に記載の自動配線決定装置。
【請求項６】
前記第２の交点解消手段による前記第２の交点解消処理により全ての交点が解消された時点における、前記仮配線および／または仮配置された前記暫定配線が、隣接する形成物に対してクリアランスを確保するよう、前記仮配線および／または仮配置された前記暫定配線の識別情報に基づいて、前記仮配線および／または仮配置された前記暫定配線を当該ビア部からずらして本配置して、前記最適な配線の位置を決定する決定手段をさらに備える請求項５に記載の自動配線決定装置。
【請求項７】
基板上における各パッド部からそれぞれの結線先である各ビア部への最適な配線の位置を自動的に決定する自動配線決定処理をコンピュータに実行させるためのコンピュータプログラムであって、
各前記パッド部と各該パッド部のそれぞれの結線先である各前記ビア部とを直線で結んだ各仮配線のうち、２つの前記仮配線が形成する交点を解消するよう、当該交点を形成する一方の前記仮配線を、もう一方の前記仮配線の結線先である前記ビア部の周りに迂回させ、これを暫定配線として確定する第１の交点解消処理を、各前記仮配線が形成する交点の全てについて、前記パッド部に近い前記交点から順次実行する第１の交点解消ステップと、
該第１の交点解消ステップにおける前記の処理の完了後、各前記暫定配線同士が形成する交点もしくは前記暫定配線と前記仮配線とが形成する交点を解消するよう、当該交点を形成する一方の前記暫定配線もしくは前記仮配線を、もう一方の前記暫定配線もしくは前記仮配線の結線先である前記ビア部の周りに迂回させ、これを新たなる配線として確定する第２の交点解消処理を、各前記暫定配線同士が形成する交点および前記暫定配線と前記仮配線とが形成する交点の全てについて、前記パッド部に近い前記交点から順次実行する第２の交点解消ステップと、を備え、
前記第２の交点解消ステップにおける前記の第２の交点解消処理により全ての交点が解消された時点における前記仮配線および／または前記暫定配線を、前記最適な配線として確定することを特徴とする自動配線決定処理をコンピュータに実行させるためのコンピュータプログラム。
【請求項８】
基板上における各パッド部からそれぞれの結線先である各ビア部への最適な配線の位置を自動的に決定する自動配線決定処理をコンピュータに実行させるためのコンピュータプログラムであって、
各前記パッド部と各該パッド部のそれぞれの結線先である各前記ビア部とを直線で結んだ各仮配線のうち、２つの前記仮配線が形成する交点と、前記２つの仮配線のそれぞれの結線先である各前記ビア部と、の間の各距離の長短を判定し、前記距離が長い方の前記仮配線を、当該交点を解消するよう、前記距離が短い方の前記仮配線の結線先である前記ビア部の周りに迂回させ、これを暫定配線として確定する第１の交点解消処理を、各前記仮配線が形成する交点の全てについて、前記パッド部に近い前記交点から順次実行する第１の交点解消ステップと、
該第１の交点解消ステップにおける前記の処理の完了後、各前記暫定配線同士が形成する交点もしくは前記暫定配線と前記仮配線とが形成する交点と、当該暫定配線もしくは当該仮配線の結線先である前記ビア部と、の間の各距離の長短を判定し、前記距離が長い方の前記暫定配線もしくは前記仮配線を、当該交点を解消するよう、前記距離が短い方の前記暫定配線もしくは前記仮配線の結線先である前記ビア部の周りに迂回させ、これを新たなる暫定配線として確定する第２の交点解消処理を、各前記暫定配線同士が形成する交点および前記暫定配線と前記仮配線とが形成する交点の全てについて、前記パッド部に近い前記交点から順次実行する第２の交点解消ステップと、を備え、
前記第２の交点解消ステップにおける前記の第２の交点解消処理により全ての交点が解消された時点における前記仮配線および／または前記暫定配線を、前記最適な配線として確定することを特徴とする自動配線決定処理をコンピュータに実行させるためのコンピュータプログラム。
【請求項９】
前記第１の交点解消ステップは、
前記距離が長い方の前記仮配線を当該ビア部の周りに迂回させることにより生成されることになる前記暫定配線が、当該ビア部と該ビア部に隣接する形成物とに対してクリアランスを確保できるか否かを判定する第１の判定ステップを有し、
前記第１の交点解消ステップは、
前記第１の判定ステップにおいて当該暫定配線のままでは前記クリアランスを確保できないと判定された場合は、当該暫定配線に代えて、前記距離が短い方の前記仮配線を、前記距離が長い方の前記仮配線の結線先である前記ビア部の周りに迂回させ、これを新たなる暫定配線として確定し直す請求項８に記載の自動配線決定処理をコンピュータに実行させるためのコンピュータプログラム。
【請求項１０】
前記第１の交点解消ステップは、
迂回すべきとされた前記ビア部に結線された前記距離が短い方の前記仮配線と、該仮配線以外の仮配線と、の交点の数をカウントするカウントステップと、
前記距離が長い方の前記仮配線を当該ビア部の周りに迂回させることにより生成されることになる前記暫定配線が、当該ビア部と該ビア部に隣接する形成物との間のクリアランスを確保できるか否かを、該カウントステップにおいてカウントされた交点の数に基づいて判定する第２の判定ステップと、を有し、
前記第１の交点解消ステップは、
前記第２の判定ステップにおいて当該暫定配線のままでは前記クリアランスを確保できないと判定された場合は、当該暫定配線に代えて、前記距離が短い方の前記仮配線を、前記距離が長い方の前記仮配線の結線先である前記ビア部の周りに迂回させ、これを新たなる暫定配線として確定し直す請求項８に記載の自動配線決定処理をコンピュータに実行させるためのコンピュータプログラム。
【請求項１１】
前記第１の交点解消ステップでは、前記暫定配線を、迂回すべきとされた前記ビア部上を通るように仮配置し、
前記第２の交点解消ステップでは、仮配置された前記暫定配線について前記第２の交点解消処理を実行して確定された前記暫定配線を、迂回すべきとされた前記ビア部上を通るように仮配置する請求項７または８に記載の自動配線決定処理をコンピュータに実行させるためのコンピュータプログラム。
【請求項１２】
前記第２の交点解消ステップにおける前記第２の交点解消処理により全ての交点が解消された時点における、前記仮配線および／または仮配置された前記暫定配線が、隣接する形成物に対してクリアランスを確保するよう、前記仮配線および／または仮配置された前記暫定配線の識別情報に基づいて、前記仮配線および／または仮配置された前記暫定配線を当該ビア部からずらして本配置して、前記最適な配線の位置を決定する決定ステップをさらに備える請求項１１に記載の自動配線決定処理をコンピュータに実行させるためのコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、基板上における各パッド部からそれぞれの結線先である各ビア部への最適な配線の位置を、演算処理により自動的に決定する自動配線決定装置およびこの自動配線決定処理をコンピュータに実行させるためのコンピュータプログラムに関する。
【背景技術】
【０００２】
ＰＢＧＡやＥＢＧＡなどの半導体パッケージにおいては、半導体チップの電極端子と電気的に接続されるパッド部（例えばボンディングパッド、フリップチップパッド）とその周囲に設けられたビア部（ランド）との間あるいはビア部どうしの間を配線によりそれぞれ接続する。半導体パッケージにおける配線は、ビア部と配線との間および配線間等のクリアランス（ライン＆スペース）を確保し、かつ、不必要な配線の交差（クロス）がないようにするといった設計ルールを最低限満足する必要がある。設計者は例えばＣＡＤシステムを用いて仮想平面上で半導体パッケージの配線ルートを試行錯誤しながら設計するのが一般的である。
【０００３】
図３６は、半導体パッケージにおいて配線すべきネットを例示する図である。以降、添付される図面においては配線が図示される場合は、その配線は基板上における配線の少なくとも一部について図示するものとする。また、図３７は、本明細書に添付された図面において表されるビア部、パッド部および配線すべきネットの凡例を説明する図である。以降、ビア部、パッド部および／または配線すべきネットに関する図面については、図３７の凡例が適用されるものとする。
【０００４】
半導体パッケージにおいては、基板中央部に設けられた半導体チップに接続されるパッド部から、周辺部に設けられたビア部へ向かって、配線が設けられる。図３６には、一例として、１列に並んだパッド部（ボンディングパッド）から、それぞれの結線先である各ビア部へ配線すべきネットが直線（いわゆる「ｒａｔｓ」）で表示されている。半導体パッケージにおける配線は、ビア部と配線との間および配線間等のクリアランスを確保し、かつ、不必要な配線の交差がないようにしなければならない。図３６に示す一例では配線の交差が生じているので、配線設計するにあたっては、この交差を解消しなければならない。
【０００５】
上述のような交差を自動的に解消することができる配線パターン設計方法として、本出願人は、ラフ配線工程により配線ルートのみを先行して決めておき、次いで配線成形工程により実際の設計ルールに照らし合わせて、クリアランスを見ながら均等に配線する方法を提案している（例えば、特許文献１参照）。この方法は、所定の補助線を設定した上で、パッド部からビア部へ向かう方向に、補助線を用いて配線を順次決定していくものである。図３８は、図３６に示されたネットの交差を、特開２００２−０８３００６号公報に記載された技術を用いて解消した配線設計結果を例示する図である。図中点線は補助線を示す。通常、半導体パッケージにおいては、基板中央部に設けられた半導体チップに接続されるパッド部から周辺部に設けられたビア部へ向かって配線が設けられるので、配線が向かう方向は図３８に示すようにほぼ同一方向に向く傾向がある。本明細書では、このような配線方向を「順方向」と呼び、略順方向に向く配線を「順行配線」と呼ぶ。このような順行配線を、コンピュータによる演算処理により実現することは比較的容易である。
【０００６】
半導体パッケージにおける配線が上記のような設計ルールを最低限満足して設計されたものであれば、一応の目標は達成されたといえる。しかしながら実際は、設計ルールを満足するのみではなく、配線パターンがある程度バランスよく整然と並んでいる、いわゆる「美しい配線」も要求されることが多い。なぜなら「美しい配線」にすることにより、製造コスト削減や電気抵抗の低減などにつながることが多いからである。また、バランスよく配線することにより、温度変化や湿度変化などの外的環境要因による基板の歪みの発生を抑制することもできる。
【０００７】
図３９は、図３６に示されたネットの交差を、交差解消後の配線がバランスよく配置されるように配線ルートを設計した場合を例示する図である。図３９に示すように、配線を適切に迂回させることができれば、図３８の場合に比べて、格段にバランスのよい配線を実現することができる。上述のように、半導体パッケージにおける配線は「順行配線」となるのが一般的である。しかし実際は、図３９に示すような、配線の向きが、ある一部分において、大方の方向とはほぼ逆向きとなる「ビア部の周りを迂回するようなルート（単に「迂回ルート」と称する。）」が存在することは、製造コスト削減、電気抵抗の低減、および基板の歪みの発声の抑制などの種々の観点から、むしろ有利である場合が多い。また、迂回ルートを許容すればクリアランスエラーを削減することができる配線の存在の可能性も大きくなり、設計する際のゆとりになる。本明細書では、上記のような大方の方向とはほぼ逆向きとなる上記のような迂回ルートを有する配線を、「非順行配線（ｒｅｔｒｏｇｒａｄｅ  ｗｉｒｉｎｇ）」と呼ぶ。
【０００８】
図４０は、非順行配線の一例を例示する図である。この図に示すように、非順行配線では、配線が激しく蛇行している箇所が存在し得るので、コンピュータ処理を用いた配線設計の自動化は難しい。したがって、現在のところ、設計者が経験と勘を頼りに手動で非順行配線の配線設計を行っている。設計者はＣＡＤ／ＣＡＭシステムを用いて、ディスプレイを見ながら、実際に配線をしながら試行錯誤的に修正していくといったやり方で、設計ルールを満たしかつ配線ルートの交差のない最適な配線ルートを手動で設計するので、設計の品質や設計に要する時間は、設計者の技量、経験、勘などに大きく左右される。
【０００９】
非順行配線の設計において、設計者の負担を軽減し、かつ安定した品質の配線設計を実現するために、非順行配線についての配線方法が提案されている（例えば、非特許文献１参照）。図４１は、非特許文献１に記載された技術による、非順行配線の生成原理を示す図である。本明細書では、以降、文字Ｖに１や２などの数字が付いたものはビアの識別符号を表し、文字Ｂに１や２などの数字が付いたものはパッド部の識別符号を表し、文字Ｗ、Ｗ’、Ｗ”、Ｗ”’、ｗ、ｗ’もしくはｗ”に１や２などの数字が付いたものは配線の識別符号を表すものとする。また、文字ＱもしくはＱ’に１や２などの数字が付いたものは配線同士の交点の識別符号を表すものとする。
【００１０】
ここで一例として、図４１（ａ）に示すように、パッド部Ｂ１とビア部Ｖ１とを結ぶ配線Ｗ１と、パッド部Ｂ２とビア部Ｖ２とを結ぶ配線Ｗ２と、が交点Ｑ１で交差（クロス）する場合を考える。
【００１１】
非特許文献１に記載の技術によれば、まず、２つの配線Ｗ１およびＷ２が形成する交点Ｑ１と、２つの配線Ｗ１のそれぞれの結線先である各ビア部Ｖ１およびＶ２と、の間の各距離の長短を判定する。図４１（ａ）に示す例では、交点Ｑ１とビア部Ｖ２との間の距離の方が、交点Ｑ１とビア部Ｖ１との間の距離よりも長い。図４１（ｂ）に示すように、上記距離が長い方の配線Ｗ２を、当該交点Ｑ１を解消するよう、上記距離が短い方の配線Ｗ１の結線先であるビア部Ｖ１の周りに迂回させ、これを新たなる配線Ｗ’ ２とする。こうして、図４１（ｃ）に示すような、非順行配線が生成される。
【００１２】
このように、上記距離が短い方の配線を上記距離が長い方の配線の結線先であるビア部の周りに迂回させるのではなく、上記距離が長い方の配線を上記距離が短い方の配線の結線先であるビア部の周りに迂回させるのは、迂回の結果生じる配線全体の長さの増加を、前者に比べて後者の方が抑制することができるからである。
【００１３】
【特許文献１】特開２００２−０８３００６号公報
【非特許文献１】タル・ダヤン（Ｔａｌ  Ｄａｙａｎ）著、「ラバーバンド・ベースド・トポロジカル・ルータ（Ｒｕｂｂｅｒ−Ｂａｎｄ  Ｂａｓｅｄ  Ｔｏｐｏｌｏｇｉｃａｌ  Ｒｏｕｔｅｒ）」、（米国）、カリフォルニア大学サンタクルズ校（Ｕｎｉｖｅｒｓｉｔｙ  ｏｆ  Ｃａｌｉｆｏｒｎｉａ  Ｓａｎｔａ  Ｃｒｕｚ）、１９９７年６月、コンピュータ工学専攻における博士号取得のために必須の論文（Ａ  ｄｉｓｓｅｒｔａｔｉｏｎ  ｓｕｂｍｉｔｔｅｄ  ｉｎ  ｐａｒｔｉａｌ  ｓａｔｉｓｆａｃｔｉｏｎ  ｏｆ  ｔｈｅ  ｒｅｑｕｉｒｅｍｅｎｔｓ  ｆｏｒ  ｔｈｅ  ｄｅｇｒｅｅ  ｏｆ  ｄｏｃｔｏｒ  ｏｆ  ｐｈｉｌｏｓｏｐｈｙ  ｉｎ  ｃｏｍｐｕｔｅｒ  ｅｎｇｉｎｅｅｒｉｎｇ）
【発明の開示】
【発明が解決しようとする課題】
【００１４】
非特許文献１に記載された技術は、非順行配線の設計をある程度ルール化するものであるが、図４０に示すような複雑な配線に対しては適用することは困難である。なぜならば、迂回させた配線がさらに他の配線と交差することが十分考えられ、非特許文献１に記載された技術は、このような問題を解決するまでには至っていないからである。つまり、非順行配線の配線設計の自動化は未だなされていないのが現状といえる。結局のところ、設計者は、自らの経験と勘を頼りに、ＣＡＤシステムを実際に操作しながら仮想平面上で半導体パッケージの配線ルートを試行錯誤しながら設計しなければならない。試行錯誤しながらの手動による配線設計では、要求される配線の内容が複雑になるほど、最適な配線を実現するには多大なる労力および時間を要し、難易度も増す。さらに、完成品の品質のバラツキも大きくなる。実際のところ、試行錯誤しながらの手動による非順行配線の設計は１〜３週間程度を要し、それ以上の日数を配線設計に割り当てることは非経済的であることから、ある程度の設計結果が得られれば「大体この程度で良いだろう」と妥協しているのが現状である。
【００１５】
従って本発明の目的は、上記問題に鑑み、基板上における各パッド部からそれぞれの結線先である各ビア部への最適な配線の位置を設計するにあたり、配線の向きが、ある一部分において大方の方向とはほぼ逆向きとなるような傾向があっても、演算処理により自動的に配線の位置を決定することができる自動配線決定装置およびその自動配線決定処理をコンピュータに実行させるためのコンピュータプログラムを提供することにある。
【課題を解決するための手段】
【００１６】
上記目的を実現するために、本発明においては、基板上における各パッド部からそれぞれの結線先である各ビア部への最適な配線の位置を、演算処理により自動的に決定する自動配線決定装置は、各パッド部と各パッド部のそれぞれの結線先である各ビア部とを直線で結んだ各仮配線のうち、２つの仮配線が形成する交点を解消するよう、当該交点を形成する一方の仮配線を、もう一方の仮配線の結線先であるビア部の周りに迂回させ、これを暫定配線として確定する第１の交点解消処理を、各仮配線が形成する交点の全てについて、パッド部に近い交点から順次実行する第１の交点解消手段と、この第１の交点解消手段による第１の交点解消処理の完了後、各暫定配線同士が形成する交点もしくは暫定配線と仮配線とが形成する交点を解消するよう、当該交点を形成する一方の暫定配線もしくは仮配線を、もう一方の暫定配線もしくは仮配線の結線先であるビア部の周りに迂回させ、これを最適な配線として確定する第２の交点解消処理を、各暫定配線同士が形成する交点および暫定配線と仮配線とが形成する交点の全てについて、パッド部に近い交点から順次実行する第２の交点解消手段と、を備える。この自動配線決定装置における第１の交点解消手段および第２の交点解消手段は、コンピュータなどの演算処理装置および／またはコンピュータ等の演算処理装置が実行することができるコンピュータプログラムで実現される。
【００１７】
図１は、本発明による自動配線決定装置の原理ブロック図である。以降、異なる図面において同じ参照番号が付されたものは同じ機能を有する構成要素であることを意味するものとする。
【００１８】
基板上における各パッド部からそれぞれの結線先である各ビア部への最適な配線の位置を、演算処理により自動的に決定する自動配線決定装置１は、
各パッド部と各パッド部のそれぞれの結線先である各ビア部とを直線で結んだ各仮配線のうち、２つの仮配線が形成する交点と、２つの仮配線のそれぞれの結線先である各ビア部と、の間の各距離の長短を判定し、この距離が長い方の仮配線を、当該交点を解消するよう、上記距離が短い方の仮配線の結線先であるビア部の周りに迂回させ、これを暫定配線として確定する第１の交点解消処理を、各仮配線が形成する交点の全てについて、パッド部に近い交点から順次実行する第１の交点解消手段１１と、
この第１の交点解消手段１１による前記の処理の完了後、各暫定配線同士が形成する交点もしくは暫定配線と仮配線とが形成する交点と、当該暫定配線もしくは当該仮配線の結線先であるビア部と、の間の各距離の長短を判定し、この距離が長い方の暫定配線もしくは仮配線を、当該交点を解消するよう、上記距離が短い方の暫定配線もしくは仮配線の結線先であるビア部の周りに迂回させ、これを新たなる暫定配線として確定する第２の交点解消処理を、各暫定配線同士が形成する交点および暫定配線と仮配線とが形成する交点の全てについて、パッド部に近い交点から順次実行する第２の交点解消手段１２と、を備える。そして、第２の交点解消手段１２による前記第２の交点解消処理により全ての交点が解消された時点における前記仮配線および／または前記暫定配線を、前記最適な配線として確定する。
【００１９】
第１の交点解消手段１１は、上記距離が長い方の仮配線を当該ビア部の周りに迂回させることにより生成されることになる暫定配線が、当該ビア部とこのビア部に隣接する形成物とに対してクリアランスを確保できるか否かを判定する第１の判定手段２１を有する。第１の交点解消手段１１は、第１の判定手段２１が、当該暫定配線のままでは前記のクリアランスを確保できないと判定した場合は、当該暫定配線に代えて、上記距離が短い方の仮配線を、上記距離が長い方の仮配線の結線先であるビア部の周りに迂回させ、これを新たなる暫定配線として確定し直す。
【００２０】
第１の交点解消手段１１は、迂回すべきとされたビア部に結線された上記距離が短い方の仮配線と、この仮配線以外の仮配線と、の交点の数をカウントするカウント手段２２と、上記距離が長い方の仮配線を当該ビア部の周りに迂回させることにより生成されることになる暫定配線が、当該ビア部とこのビア部に隣接する形成物との間のクリアランスを確保できるか否かを、カウント手段２２によりカウントされた交点の数に基づいて判定する第２の判定手段２３と、を有する。第１の交点解消手段１１は、第２の判定手段２３が当該暫定配線のままではクリアランスを確保できないと判定した場合は、当該暫定配線に代えて、上記距離が短い方の仮配線を、上記距離が長い方の仮配線の結線先であるビア部の周りに迂回させ、これを新たなる暫定配線として確定し直す。
【００２１】
なお、自動配線決定装置１における第１の交点解消手段１１、第２の交点解消手段１２、第１の判定手段２１、カウント手段２２よび第２の判定手段２３は、コンピュータ等の演算処理装置が実行することができるソフトウェア形式であるコンピュータプログラム実現される。以上の処理を実施する装置や、以上の処理をコンピュータに実行させるためのコンピュータプログラムを作成することは、以下の説明を理解した当業者には実施できる事項である。また、以上の処理をコンピュータに実行させるためのコンピュータプログラムを記録媒体に格納するという事項も当業者には自明である。
【発明の効果】
【００２２】
本発明によれば、基板上における各パッド部からそれぞれの結線先である各ビア部への最適な配線の位置を設計するにあたり、配線の向きが、ある一部分において大方の方向とはほぼ逆向きとなるような傾向があっても、コンピュータなどを用いた演算処理により自動的に配線の位置を決定することができる。すなわち、コンピュータによる演算処理が可能となるように非順行配線の設計がルール化され、設計者の負担を軽減し、かつ安定した品質の配線設計が実現される。
【００２３】
本発明によれば、従来のように設計者自らの技量、経験、勘などに左右されることなく、配線バランスのよい安定した品質の非順行配線に係る配線ルートを短時間で容易に設計することができる。例えば、従来、試行錯誤しながらの手動による配線設計によれば１〜３週間程度を要していたものが、本発明によれば２〜３日で自動的に演算処理結果を得ることができる。従来のような試行錯誤しながらの手動による設計を行わずに済むので、要求される配線の内容が複雑になったとしても、高品質でバランスのよい配線ルートを短時間で実現することができる。このような設計時間の短縮および設計者の負担の軽減の結果、半導体パッケージの製造コストも低減できる。
【００２４】
バランスのよい配線パターンは、バランスの悪いものに比べ、配線距離が短いので経済的であり、製造容易であり、そして製造時における製品エラーの発生率も低い。また、電気的にも安定した性質を示す。さらには、バランスよく配線されることによって、例えば熱による基板の変形が生じてもその変形はほぼ均等なものとなるので、短絡や断線等の配線エラーも生じにくい。またさらには、ある程度の規則性を有して整然と配線されている半導体パッケージのほうが見た目にも美しいので、半導体パッケージの完成品の販売政策上有利である。
【発明を実施するための最良の形態】
【００２５】
図２は、本発明の実施例による自動配線決定方法の動作フローを示すフローチャートである。
【００２６】
まず、ステップＳ１０１では、基板上に配置される各パッド部と各パッド部のそれぞれの結線先である各ビア部とを仮想平面上に想定し、該仮想平面上において、各パッド部と各パッド部のそれぞれの接続先である各ビア部とを直線（ｒａｔｓ）で結び、これを仮配線とする。
【００２７】
次に、ステップＳ１０２において、ステップＳ１０１で生成された各仮配線のうち、２つの仮配線が形成する交点と、２つの仮配線のそれぞれの結線先である各ビア部と、の間の各距離の長短を判定する。なお、他のどの仮配線とも交差しない仮配線が存在することも当然あり得ることであり、このような場合は本処理は実行されない。
【００２８】
次いで、ステップＳ１０３において、ステップＳ１０２で判別された交点とビア部との距離が長い方の仮配線を、当該交点を解消するよう、上記距離が短い方の仮配線の結線先であるビア部の周りに迂回させ、これを暫定配線として確定する。
【００２９】
本明細書では、上記ステップＳ１０２およびＳ１０３の処理をまとめて「第１の交点解消処理」と称する。この第１の交点解消処理は、各仮配線が形成する交点の全てについて、パッド部に近い交点から順次、実行される。このため、ステップＳ１０４では、各仮配線が形成する交点の全てについて、第１の交点解消処理が完了したか否かが判定される。
【００３０】
第１の交点解消処理が完了すると、仮配線同士の交差による交点は全て解消され、他の仮配線と交差していた仮配線は、全て暫定配線に置き換えられたことになる。一方、他のどの仮配線とも交差しない仮配線は、暫定配線への置き換えはなく、仮配線のままである。つまり、第１の交点解消処理の完了時点において存在している仮配線は、他のどの仮配線とも交差しない仮配線であり、暫定配線への置き換えはない。
【００３１】
上記の第１の交点解消処理によって生成された暫定配線の交差の有無については、同様に生成された他の暫定配線と交差する場合、第１の交点解消処理とは無関係であった仮配線と交差する場合、あるいは他のどの暫定配線および仮配線とも交差しない場合がある。次のステップＳ１０５からＳ１０７の処理は、暫定配線同士の交差および暫定配線と仮配線との交差を解消し、存在し得る全ての交点を解消するためのものである。
【００３２】
第１の交点解消処理が完了すると、次のステップＳ１０５において、各暫定配線同士が形成する交点もしくは暫定配線と仮配線とが形成する交点と、当該暫定配線もしくは当該仮配線の結線先であるビア部と、の間の各距離の長短を判定する。
【００３３】
次いで、ステップＳ１０５において、ステップＳ１０４で判別された交点とビア部との距離が長い方の暫定配線もしくは仮配線を、当該交点を解消するよう、上記距離が短い方の暫定配線もしくは仮配線の結線先であるビア部の周りに迂回させ、これを新たなる暫定配線として確定する。
【００３４】
本明細書では、ステップＳ１０５およびＳ１０６の処理をまとめて「第２の交点解消処理」と称する。この第２の交点解消処理は、各暫定配線同士が形成する交点および暫定配線と仮配線とが形成する交点の全てについて、パッド部に近い交点から順次、実行される。このため、ステップＳ１０７では、各暫定配線同士が形成する交点および暫定配線と仮配線とが形成する交点の全てについて、第２の交点解消処理が完了したか否かが判定される。
【００３５】
第２の交点解消処理が完了すると、暫定配線同士が形成する交点、および、暫定配線と仮配線とが形成する交点は全て解消されたことになる。つまり、第２の交点解消処理の完了時点において存在している仮配線および暫定配線については、他の仮配線もしくは暫定配線との交点はもはや存在しないことから、ステップＳ１０８において、これら各配線を最適な配線として確定する。
【００３６】
本発明の実施例による自動配線決定処理におけるステップＳ１０１〜Ｓ１０８の各処理は、コンピュータ等の演算処理装置により実行される。なお、ステップＳ１０１を実行する前に、設計データ、クリアランスに関するルール、各パッド部の座標、形状、大きさおよび向き、各ビア部の座標、形状、大きさおよび向き、基板情報、ならびに、半導体チップのチップパッドからパッド部への配線、などに関する種々のデータを、演算処理装置に予め入力しておくのが好ましい。上記演算処理装置は、入力された上記データを用いてステップＳ１０１から処理を開始する。ステップＳ１０１〜Ｓ１０８を経て、基板上における各パッド部からそれぞれの結線先である各ビア部への最適な配線の位置が、演算処理により自動的に決定される。
【００３７】
図３は、本発明の実施例の自動配線決定装置による最適な配線の生成の第１の具体例を説明する図である。
【００３８】
ここでは一例として、図３（ａ）に示すように、パッド部Ｂ３とビア部Ｖ３とを結ぶ仮配線Ｗ３が、パッド部Ｂ１とビア部Ｖ１とを結ぶ仮配線Ｗ１およびパッド部Ｂ２とビア部Ｖ２とを結ぶ仮配線Ｗ２と、それぞれ交点Ｑ１およびＱ２において交差（クロス）する場合を考える。本具体例では特に、仮配線Ｗ１の方が仮配線Ｗ２よりも長いものとする。
【００３９】
第１の交点解消処理は、各仮配線が形成する交点の全てについて、パッド部に近い交点から順次、実行される。図３（ａ）に示す例では、交点Ｑ２よりも交点Ｑ１の方が、パッド部Ｂ１、Ｂ２およびＢ３に近い位置にあるので、第１の交点解消処理は、交点Ｑ１、交点Ｑ２の順に実行されることになる。
【００４０】
交点Ｑ１について第１の交点解消処理を実行すると次の通りである。図３（ａ）において、仮配線Ｗ２と仮配線Ｗ３とが形成する交点Ｑ１と仮配線Ｗ２および仮配線Ｗ３のそれぞれの結線先である各ビア部Ｖ２およびＶ３との間の距離Ｑ１Ｖ２およびＱ１Ｖ３の長短を判定する。図３（ａ）に示す例では、交点Ｑ１とビア部Ｖ３との間の距離Ｑ１Ｖ３の方が、交点Ｑ１とビア部Ｖ２との間の距離Ｑ１Ｖ２よりも長い。したがって、長い方の距離Ｑ１Ｖ３に係る仮配線Ｗ３を、当該交点Ｑ１での交差を解消するよう、短い方の距離Ｑ１Ｖ２に係る仮配線Ｗ１の結線先であるビア部Ｖ２の周りに迂回させる。このとき得られる配線を暫定配線Ｗ’３として確定する。つまり、図３（ａ）に示すパッド部Ｂ３とビア部Ｖ３とを結ぶ仮配線Ｗ３は、第１の交点解消処理により、図３（ｂ）に示すようなパッド部Ｂ３とビア部Ｖ３とを結ぶ暫定配線Ｗ’３に置き換えられたことになる。
【００４１】
図３（ｂ）の状態では、仮配線同士が形成する交点は全て解消されている。したがって、この時点で第１の交点解消処理は完了し、第２の交点解消処理を開始する。図３（ｂ）に示すように、暫定配線Ｗ’３は、仮配線Ｗ１に対して交点Ｑ３で交差している。そこで、暫定配線Ｗ’３と仮配線Ｗ１とが形成する交点Ｑ３と暫定配線Ｗ’３および仮配線Ｗ１のそれぞれの結線先である各ビア部Ｖ３およびＶ１との間の距離Ｑ３Ｖ３およびＱ３Ｖ１の長短を判定する。図３（ｂ）に示す例では、交点Ｑ３とビア部Ｖ１との間の距離Ｑ３Ｖ１の方が、交点Ｑ３とビア部Ｖ３との間の距離Ｑ３Ｖ３よりも長い。したがって、長い方の距離Ｑ３Ｖ１に係る仮配線Ｗ１を、当該交点Ｑ３での交差を解消するよう、短い方の距離Ｑ３Ｖ３に係る暫定配線Ｗ’３の結線先であるビア部Ｖ３の周りに迂回させる。このとき得られる配線を新たなる暫定配線Ｗ’１として確定する。つまり、図３（ｂ）に示すパッド部Ｂ１とビア部Ｖ１とを結ぶ仮配線Ｗ１は、第２の交点解消処理により、図３（ｃ）に示すようなパッド部Ｂ１とビア部Ｖ１とを結ぶ暫定配線Ｗ’１に置き換えられたことになる。
【００４２】
図３（ｃ）の状態では、仮配線同士、暫定配線同士、ならびに暫定配線と仮配線とが形成する交点は全て解消されている。したがって、この時点で第２の交点解消処理は完了し、暫定配線Ｗ’１、仮配線Ｗ２および暫定配線Ｗ’３は、最適な配線として確定される。こうして、図３（ｃ）に示すような、非順行配線が生成される。
【００４３】
図４および５は、本発明の実施例の自動配線決定装置による最適な配線の生成の第２の具体例を説明する図である。
【００４４】
ここで一例として、図４（ａ）に示すように、パッド部Ｂ３とビア部Ｖ３とを結ぶ仮配線Ｗ３が、パッド部Ｂ１とビア部Ｖ１とを結ぶ仮配線Ｗ１およびパッド部Ｂ２とビア部Ｖ２とを結ぶ仮配線Ｗ２と、それぞれ交点Ｑ１およびＱ２において交差（クロス）する場合を考える。本具体例では特に、仮配線Ｗ２の方が仮配線Ｗ１よりも長いものとする。
【００４５】
図４（ａ）に示す例では、交点Ｑ２よりも交点Ｑ１の方が、パッド部Ｂ１、Ｂ２およびＢ３に近い位置にあるので、第１の交点解消処理は、交点Ｑ１、交点Ｑ２の順に実行されることになる。
【００４６】
まず、交点Ｑ１について第１の交点解消処理を実行すると次の通りである。図４（ａ）において、仮配線Ｗ２と仮配線Ｗ３とが形成する交点Ｑ１と仮配線Ｗ２および仮配線Ｗ３のそれぞれの結線先である各ビア部Ｖ２およびＶ３との間の距離Ｑ１Ｖ２およびＱ１Ｖ３の長短を判定する。図４（ａ）に示す例では、交点Ｑ１とビア部Ｖ２との間の距離Ｑ１Ｖ２の方が、交点Ｑ１とビア部Ｖ３との間の距離Ｑ１Ｖ３よりも長い。したがって、長い方の距離Ｑ１Ｖ２に係る仮配線Ｗ２を、当該交点Ｑ１での交差を解消するよう、短い方の距離Ｑ１Ｖ３に係る仮配線Ｗ３の結線先であるビア部Ｖ３の周りに迂回させる。このとき得られる配線を暫定配線Ｗ’２として確定する。つまり、図４（ａ）に示すパッド部Ｂ２とビア部Ｖ２とを結ぶ仮配線Ｗ２は、第１の交点解消処理により、図４（ｂ）に示すようなパッド部Ｂ２とビア部Ｖ２とを結ぶ暫定配線Ｗ’２に置き換えられたことになる。
【００４７】
次に、交点Ｑ２について第１の交点解消処理を実行すると次の通りである。図４（ｂ）において、仮配線Ｗ１と仮配線Ｗ３とが形成する交点Ｑ２と仮配線Ｗ１および仮配線Ｗ３のそれぞれの結線先である各ビア部Ｖ１およびＶ３との間の距離Ｑ２Ｖ１およびＱ２Ｖ３の長短を判定する。図４（ｂ）に示す例では、交点Ｑ２とビア部Ｖ３との間の距離Ｑ２Ｖ３の方が、交点Ｑ２とビア部Ｖ１との間の距離Ｑ２Ｖ１よりも長い。したがって、長い方の距離Ｑ２Ｖ３に係る仮配線Ｗ３を、当該交点Ｑ２での交差を解消するよう、短い方の距離Ｑ２Ｖ１に係る仮配線Ｗ１の結線先であるビア部Ｖ１の周りに迂回させる。このとき得られる配線を暫定配線Ｗ’３として確定する。つまり、図４（ｂ）に示すパッド部Ｂ３とビア部Ｖ３とを結ぶ仮配線Ｗ３は、第１の交点解消処理により、図４（ｃ）に示すようなパッド部Ｂ３とビア部Ｖ３とを結ぶ暫定配線Ｗ’３に置き換えられたことになる。
【００４８】
図４（ｃ）の状態では、仮配線同士が形成する交点は全て解消されている。したがって、この時点で第１の交点解消処理は完了し、第２の交点解消処理を開始する。
【００４９】
図４（ｃ）に示す暫定配線Ｗ’２は、仮配線Ｗ１に対して交点Ｑ３で交差している。そこで、暫定配線Ｗ’２と仮配線Ｗ１とが形成する交点Ｑ３と暫定配線Ｗ’２および仮配線Ｗ１のそれぞれの結線先である各ビア部Ｖ２およびＶ１との間の距離Ｑ３Ｖ２およびＱ３Ｖ１の長短を判定する。図４（ｃ）に示す例では、交点Ｑ３とビア部Ｖ２との間の距離Ｑ３Ｖ２の方が、交点Ｑ３とビア部Ｖ１との間の距離Ｑ３Ｖ１よりも長い。したがって、長い方の距離Ｑ３Ｖ２に係る暫定配線Ｗ’２を、当該交点Ｑ３での交差を解消するよう、短い方の距離Ｑ３Ｖ１に係る仮配線Ｗ１の結線先であるビア部Ｖ１の周りに迂回させる。このとき得られる配線を新たなる暫定配線Ｗ”２として確定する。つまり、図４（ｃ）に示すパッド部Ｂ２とビア部Ｖ２とを結ぶ暫定配線Ｗ’２は、第２の交点解消処理により、図５（ａ）に示すようなパッド部Ｂ２とビア部Ｖ２とを結ぶ暫定配線Ｗ”２に置き換えられたことになる。
【００５０】
図５（ａ）の状態では、仮配線同士、暫定配線同士、ならびに暫定配線と仮配線とが形成する交点は全て解消されている。したがって、この時点で第２の交点解消処理は完了し、仮配線Ｗ１、暫定配線Ｗ”２および暫定配線Ｗ’３を、最適な配線として確定する。なお、図５（ａ）の状態では、暫定配線Ｗ”２と、隣接するビア部Ｖ１およびＶ２の各々ならびに暫定配線Ｗ’３と、の間に十分なクリアランスが確保されていないような場合は、図５（ｂ）に示すように、暫定配線Ｗ”２を配線Ｗ”’２に変換するとともに、暫定配線Ｗ’３を配線Ｗ”３に変換し、これらを最適な配線として確定してもよい。こうして、図５（ａ）もしくは（ｂ）に示すような、非順行配線が生成される。
【００５１】
図６〜１４は、本発明の実施例の自動配線決定装置による最適な配線の生成の第１の具体例を説明する図である。
【００５２】
ここでは一例として、図６に示すように、仮配線Ｗ１〜Ｗ５が交点Ｑ１〜Ｑ７において交差（クロス）する場合を考える。
【００５３】
図６に示す例では、パッド部Ｂ１〜Ｂ５に対して、交点Ｑ１、Ｑ２、Ｑ３、Ｑ４、Ｑ５、Ｑ６、Ｑ７の順に近い位置にあるので、まず交点Ｑ１について第１の交点解消処理は実行されることになる。
【００５４】
交点Ｑ１について第１の交点解消処理を実行すると次の通りである。図６において、仮配線Ｗ１と仮配線Ｗ２とが形成する交点Ｑ１と仮配線Ｗ１および仮配線Ｗ２のそれぞれの結線先である各ビア部Ｖ１およびＶ２との間の距離Ｑ１Ｖ１およびＱ１Ｖ２の長短を判定する。図６に示す例では、交点Ｑ１とビア部Ｖ１との間の距離Ｑ１Ｖ１の方が、交点Ｑ１とビア部Ｖ２との間の距離Ｑ１Ｖ２よりも長い。したがって、長い方の距離Ｑ１Ｖ１に係る仮配線Ｗ１を、当該交点Ｑ１での交差を解消するよう、短い方の距離Ｑ１Ｖ２に係る仮配線Ｗ２の結線先であるビア部Ｖ２の周りに迂回させる。このとき得られる配線を暫定配線Ｗ’１として確定する。つまり、図６に示すパッド部Ｂ１とビア部Ｖ１とを結ぶ仮配線Ｗ１は、第１の交点解消処理により、図７に示すようなパッド部Ｂ１とビア部Ｖ１とを結ぶ暫定配線Ｗ’１に置き換えられたことになる。ところで、交点Ｑ１についての第１の交点解消処理の実行により生成された暫定配線Ｗ’１は、仮配線Ｗ４およびＷ３と、それぞれ交点Ｑ８および９と交差することになる。しかし本発明では、仮配線同士が形成する交点が第１の交点解消処理により全て解消された後に、暫定配線上の交点の解消を第２の交点解消処理により実現するので、暫定配線Ｗ’１上の交点Ｑ８およびＱ９についてはこの時点では処理しない。
【００５５】
図７において、第１の交差解消処理の処理対象となる次なる交点は、仮配線Ｗ４と仮配線Ｗ５とが形成する交点Ｑ５である。まず、仮配線Ｗ４と仮配線Ｗ５とが形成する交点Ｑ５と仮配線Ｗ４および仮配線Ｗ５のそれぞれの結線先である各ビア部Ｖ４およびＶ５との間の距離Ｑ５Ｖ４およびＱ５Ｖ５の長短を判定する。図７に示す例では、交点Ｑ５とビア部Ｖ４との間の距離Ｑ５Ｖ４の方が、交点Ｑ５とビア部Ｖ５との間の距離Ｑ５Ｖ５よりも長い。したがって、長い方の距離Ｑ５Ｖ４に係る仮配線Ｗ４を、交点Ｑ５での交差を解消するよう、短い方の距離Ｑ５Ｖ５に係る仮配線Ｗ５の結線先であるビア部Ｖ５の周りに迂回させる。このとき得られる配線を暫定配線Ｗ’４として確定する。つまり、図７に示すパッド部Ｂ４とビア部Ｖ４とを結ぶ仮配線Ｗ４は、第１の交点解消処理により、図８に示すようなパッド部Ｂ４とビア部Ｖ４とを結ぶ暫定配線Ｗ’４に置き換えられたことになる。
【００５６】
図８において、第１の交差解消処理の処理対象となる次なる交点は、仮配線Ｗ３と仮配線Ｗ５とが形成する交点Ｑ６である。まず、仮配線Ｗ３と仮配線Ｗ５とが形成する交点Ｑ６と仮配線Ｗ３および仮配線Ｗ５のそれぞれの結線先である各ビア部Ｖ３およびＶ５との間の距離Ｑ６Ｖ３およびＱ６Ｖ５の長短を判定する。図８に示す例では、交点Ｑ６とビア部Ｖ３との間の距離Ｑ６Ｖ３の方が、交点Ｑ６とビア部Ｖ５との間の距離Ｑ６Ｖ５よりも長い。したがって、長い方の距離Ｑ６Ｖ３に係る仮配線Ｗ３を、交点Ｑ６での交差を解消するよう、短い方の距離Ｑ６Ｖ５に係る仮配線Ｗ５の結線先であるビア部Ｖ５の周りに迂回させる。このとき得られる配線を暫定配線Ｗ’３として確定する。つまり、図８に示すパッド部Ｂ３とビア部Ｖ３とを結ぶ仮配線Ｗ３は、第１の交点解消処理により、図９に示すようなパッド部Ｂ３とビア部Ｖ３とを結ぶ暫定配線Ｗ’３に置き換えられたことになる。
【００５７】
図９の状態では、仮配線同士が形成する交点は全て解消されている。したがって、この時点で第１の交点解消処理は完了し、第２の交点解消処理を開始する。なお、交点Ｑ１１を有する暫定配線Ｗ’１は、ビア部５との間のクリアランスが確保できていないので、図１０のように、暫定配線”１に置き換え、その上で第２の交点解消処理を実行する。
【００５８】
図１０に示す例では、パッド部Ｂ１〜Ｂ５に対して、交点Ｑ１４、Ｑ１５、Ｑ１６の順に近い位置にあるので、交点Ｑ１４について第２の交点解消処理が実行される。
【００５９】
交点Ｑ１４について第２の交点解消処理を実行すると次の通りである。図１０において、暫定配線Ｗ’３は、暫定配線Ｗ’４に対してＱ１４で交差している。そこで、暫定配線Ｗ’３と暫定配線Ｗ’４とが形成する交点Ｑ１４と暫定配線Ｗ’３および暫定配線Ｗ’４のそれぞれの結線先である各ビア部Ｖ３およびＶ４との間の距離Ｑ１４Ｖ３およびＱ１４Ｖ４の長短を判定する。図１０に示す例では、交点Ｑ１４とビア部Ｖ４との間の距離Ｑ１４Ｖ４の方が、交点Ｑ１４とビア部Ｖ３との間の距離Ｑ１４Ｖ３よりも長い。したがって、長い方の距離Ｑ１４Ｖ４に係る暫定配線Ｗ’４を、交点Ｑ１４での交差を解消するよう、短い方の距離Ｑ１４Ｖ３に係る暫定配線Ｗ’３の結線先であるビア部Ｖ３の周りに迂回させる。このとき得られる配線を新たなる暫定配線Ｗ”４として確定する。つまり、図１０に示すパッド部Ｂ４とビア部Ｖ４とを結ぶ暫定配線Ｗ’４は、第２の交点解消処理により、図１１に示すようなパッド部Ｂ４とビア部Ｖ４とを結ぶ暫定配線Ｗ”４に置き換えられたことになる。
【００６０】
図１１の状態では、パッド部Ｂ１〜Ｂ５に対して、交点Ｑ１６、Ｑ１７の順に近い位置にあるので、交点Ｑ１６について第２の交点解消処理が実行される。
【００６１】
交点Ｑ１６について第２の交点解消処理を実行すると次の通りである。図１１において、暫定配線Ｗ”１は、暫定配線Ｗ’３に対してＱ１６で交差している。そこで、暫定配線Ｗ”１と暫定配線Ｗ’３とが形成する交点Ｑ１６と暫定配線Ｗ”１および暫定配線Ｗ’３のそれぞれの結線先である各ビア部Ｖ１およびＶ３との間の距離Ｑ１６Ｖ１およびＱ１６Ｖ３の長短を判定する。図１１に示す例では、交点Ｑ１６とビア部Ｖ１との間の距離Ｑ１６Ｖ１の方が、交点Ｑ１６とビア部Ｖ３との間の距離Ｑ１６Ｖ３よりも長い。したがって、長い方の距離Ｑ１６Ｖ１に係る暫定配線Ｗ”１を、交点Ｑ１６での交差を解消するよう、短い方の距離Ｑ１６Ｖ３に係る暫定配線Ｗ’３の結線先であるビア部Ｖ３の周りに迂回させる。このとき得られる配線を新たなる暫定配線Ｗ”’１として確定する。つまり、図１１に示すパッド部Ｂ１とビア部Ｖ１とを結ぶ暫定配線Ｗ”１は、第２の交点解消処理により、図１２に示すようなパッド部Ｂ１とビア部Ｖ１とを結ぶ暫定配線Ｗ”’１に置き換えられたことになる。
【００６２】
図１２の状態では、交点Ｑ１８のみが暫定配線同士の交点として存在する。交点Ｑ１８について第２の交点解消処理を実行すると次の通りである。図１２において、暫定配線Ｗ”’１は、暫定配線Ｗ’４に対してＱ１８で交差している。そこで、暫定配線Ｗ”’１と暫定配線Ｗ’４とが形成する交点Ｑ１８と暫定配線Ｗ”’１および暫定配線Ｗ’４のそれぞれの結線先である各ビア部Ｖ１およびＶ４との間の距離Ｑ１８Ｖ１およびＱ１８Ｖ４の長短を判定する。図１２に示す例では、交点Ｑ１８とビア部Ｖ１との間の距離Ｑ１８Ｖ１の方が、交点Ｑ１８とビア部Ｖ４との間の距離Ｑ１８Ｖ４よりも長い。したがって、長い方の距離Ｑ１８Ｖ１に係る暫定配線Ｗ”’１を、交点Ｑ１８での交差を解消するよう、短い方の距離Ｑ１８Ｖ４に係る暫定配線’４の結線先であるビア部Ｖ４の周りに迂回させる。このとき得られる配線を新たなる暫定配線Ｗ６として確定する。つまり、図１２に示すパッド部Ｂ１とビア部Ｖ１とを結ぶ暫定配線Ｗ”’１は、第２の交点解消処理により、図１３に示すようなパッド部Ｂ１とビア部Ｖ１とを結ぶ暫定配線Ｗ６に置き換えられたことになる。
【００６３】
図１３の状態では、パッド部Ｂ１〜Ｂ５に対して、交点Ｑ１９、Ｑ２０の順に近い位置にあるので、交点Ｑ１９について第２の交点解消処理が実行される。
【００６４】
交点Ｑ１９について第２の交点解消処理を実行すると次の通りである。図１３において、暫定配線Ｗ６は、暫定配線Ｗ”４に対してＱ１９で交差している。そこで、暫定配線Ｗ６と暫定配線Ｗ”４とが形成する交点Ｑ１９と暫定配線Ｗ６および暫定配線Ｗ”４のそれぞれの結線先である各ビア部Ｖ１およびＶ４との間の距離Ｑ１９Ｖ１およびＱ１９Ｖ４の長短を判定する。図１３に示す例では、交点Ｑ１９とビア部Ｖ１との間の距離Ｑ１９Ｖ１の方が、交点Ｑ１９とビア部Ｖ４との間の距離Ｑ１９Ｖ４よりも長い。したがって、長い方の距離Ｑ１９Ｖ１に係る暫定配線Ｗ６を、交点Ｑ１９での交差を解消するよう、短い方の距離Ｑ１９Ｖ４に係る暫定配線Ｗ’４の結線先であるビア部Ｖ４の周りに迂回させる。このとき得られる配線を新たなる暫定配線Ｗ’６として確定する。つまり、図１３に示すパッド部Ｂ１とビア部Ｖ１とを結ぶ暫定配線Ｗ６は、第２の交点解消処理により、図１４に示すようなパッド部Ｂ１とビア部Ｖ１とを結ぶ暫定配線Ｗ’６に置き換えられたことになる。
【００６５】
図１４の状態では、仮配線同士、暫定配線同士、ならびに暫定配線と仮配線とが形成する交点は全て解消されている。したがって、この時点で第２の交点解消処理は完了し、暫定配線Ｗ’６、仮配線Ｗ２、暫定配線Ｗ’３、暫定配線Ｗ”４および仮配線Ｗ５を、最適な配線として確定する。こうして、図１４に示すような非順行配線が生成される。
【００６６】
続いて、本発明の実施例の第１から第３の変形例について説明する。
【００６７】
第１の変形例は、第１の交点解消処理において生成された暫定配線が、迂回先のビア部と例えば他のビア部、ゲート、マークもしくはパッド部などの種々の形成物との間に配置される際に、十分なクリアランスを確保できないという問題を解決するものである。図１５は、本発明の実施例において、第１の交点解消処理により生成された暫定配線では十分なクリアランスを確保することができない場合を説明する図である。ここで一例として、図１５（ａ）に示すように、仮配線Ｗ３が、仮配線Ｗ１およびＷ２に対してそれぞれ交点Ｑ１およびＱ２において交差（クロス）する場合を考える。
【００６８】
図１５（ａ）に示す例では、パッド部Ｂ１〜Ｂ４に対して、交点Ｑ１、Ｑ２、の順に近い位置にあるので、交点Ｑ１について第１の交点解消処理は実行されることになる。
【００６９】
交点Ｑ１について第１の交点解消処理を実行すると次の通りである。図１５（ａ）において、仮配線Ｗ２と仮配線Ｗ３とが形成する交点Ｑ１と仮配線Ｗ２および仮配線Ｗ３のそれぞれの結線先である各ビア部Ｖ２およびＶ３との間の距離Ｑ１Ｖ２およびＱ１Ｖ３の長短を判定する。この例では、距離Ｑ１Ｖ３の方が距離Ｑ１Ｖ２よりも長いので、図１５（ｂ）に示すように、長い方の距離Ｑ１Ｖ３に係る仮配線Ｗ３を、交点Ｑ１での交差を解消するよう、短い方の距離Ｑ１Ｖ２に係る仮配線Ｗ２の結線先であるビア部Ｖ２の周りに迂回させ、この配線を暫定配線Ｗ’３として確定する。これにより、暫定配線Ｗ’３は、ビア部２とビア部４との間に配置されることになる。しかし、ビア部２とビア部４との間の距離が短い場合は、暫定配線Ｗ’３は、迂回対象のビア部Ｖ２とこのビア部Ｖ２に隣接する形成物であるビア部Ｖ４とに対して十分なクリアランスを確保することができない。
【００７０】
そこでこの問題を解決するために、第１の変形例では、第１の交点解消処理において、上述のように距離が長い方の仮配線を当該ビア部の周りに迂回させることにより生成されることになる暫定配線が、当該ビア部と該ビア部に隣接する形成物との間のクリアランスを確保できるか否かを判定する。このとき、当該暫定配線のままでは十分なクリアランスを確保できないと判定された場合は、当該暫定配線に代えて、距離が短い方の仮配線を、距離が長い方の仮配線の結線先であるビア部の周りに迂回させ、これを新たなる暫定配線として確定し直す。図１６および１７は、本発明の実施例における第１の変形例を説明する図である。ここでは一例として、図１５（ａ）と同様に、すなわち図１６（ａ）に示すように、仮配線Ｗ３が、仮配線Ｗ１およびＷ２に対してそれぞれ交点Ｑ１およびＱ２において交差（クロス）する場合を考える。
【００７１】
図１５（ｂ）に示すような距離が長い方の仮配線を当該ビア部の周りに迂回させることにより生成されることになる暫定配線Ｗ’３が、ビア部Ｖ２およびビア部Ｖ４に対して十分なクリアランスを確保できるか否かを判定したところ、暫定配線Ｗ’３のままでは十分なクリアランスを確保できないと判定された場合は、暫定配線Ｗ’３に代えて、図１６（ｂ）に示すように、短い方の距離Ｑ１Ｖ２に係る仮配線Ｗ２を、交点Ｑ１での交差を解消するよう、長い方の距離Ｑ１Ｖ３に係る仮配線Ｗ３の結線先であるビア部Ｖ３の周りに迂回させ、この配線を新たなる暫定配線Ｗ’２として確定し直す。これにより仮配線同士が形成する交点は全て解消するので、第１の交点解消手段を完了する。この後、第２の交点解消処理において暫定配線Ｗ’２上の交点Ｑ４を解消すると、図１７に示すような暫定配線Ｗ’１、暫定配線Ｗ’２、仮配線Ｗ３および仮配線Ｗ４が最適な配線として確定される。
【００７２】
第２の変形例は、第１の交点解消処理において生成された暫定配線のうち複数の暫定配線が、迂回先のビア部と例えば他のビア部、ゲート、マークもしくはパッド部などの形成物との間に配置されることによって、十分なクリアランスを確保できなくなるという問題を解決するものである。図１８〜２０は、本発明の実施例における第２の変形例を説明する図である。ここでは一例として、図１８に示すように、仮配線Ｗ１〜Ｗ６が交点Ｑ１〜Ｑ７において交差（クロス）する場合を考える。
【００７３】
図１８に示す例では、パッド部Ｂ１〜Ｂ６に対して、交点Ｑ１、Ｑ２、Ｑ３、Ｑ４、Ｑ５、Ｑ６、Ｑ７の順に近い位置にある。交点Ｑ１、交点Ｑ２の順に第１の交点解消処理は実行されると、図１９に示すような暫定配線Ｗ’２および暫定配線Ｗ’３が順次生成される。このとき、暫定配線Ｗ２および暫定配線Ｗ’３は、ビア部１とビア部６との間に配置されることになる。しかし、ビア部１とビア部６との間に暫定配線が複数配置されてしまうことになり、その結果、ビア部１、暫定配線Ｗ’２、暫定配線Ｗ’３およびビア部６のそれぞれの間のクリアランスが確保できなくなる。交点Ｑ２を解消するための暫定配線Ｗ’３を生成したところこのようなクリアランス問題が発生した後において、再度、交点Ｑ２を解消するための第１の交点解消処理をやりなおすのは効率が悪い。そこでこの問題を解決するために、第２の変形例では、第１の交点解消処理において、まず、迂回すべきとされたビア部に結線された距離が短い方の仮配線と、該仮配線以外の仮配線と、の交点の数をカウントする。そして、距離が長い方の仮配線を当該ビア部の周りに迂回させることにより生成されることになる暫定配線が、当該ビア部とこのビア部に隣接する形成物との間のクリアランスを確保できるか否かを、カウントされた交点の数に基づいて判定する。該カウント数に基づき、当該暫定配線のままではクリアランスを確保できないと判定した場合は、当該暫定配線に代えて、距離が短い方の仮配線を、距離が長い方の仮配線の結線先であるビア部の周りに迂回させ、これを新たなる暫定配線として確定し直す。
【００７４】
図１８に示す例では、暫定配線Ｗ’２および暫定配線Ｗ’３の両方とも仮配線Ｗ１を迂回するために生成されたものである。したがって、仮配線Ｗ１の、他の仮配線との交点の数をカウントする。図１８に示す例では、仮配線Ｗ１上の交点の数は４である。カウントした交点が数が多いことは、第１の交点解消処理において仮配線Ｗ１を迂回の対象とすることになる仮配線が複数存在する可能性が高いことを意味する。したがって、カウントした交点の数がある閾値よりも高い場合は、カウントした交点に係る仮配線自体を、迂回させる。図１９に示す例では、仮配線Ｗ１を、仮配線Ｗ２の結線先であるビア部Ｖ２の周りに迂回させ、この配線を、図２０に示すような新たなる暫定配線ｗ’１として確定する。以後の処理は上述した通りであるので説明は省略する。
【００７５】
第２の変形例では、このクリアランス問題が解決できるまで、新たなる暫定配線を上述のように繰り返し求めていくことになるが、それでもなお、該クリアラス問題を解決できない場合は、設計思想そのものに何らかの問題があるということである。この場合は、例えばパッド部やビア部などの配置そのものに修正を加えてから再度、設計データ自体を生成し直せばよい。
【００７６】
上述した本実施例による自動配線決定装置は、コンピュータなどの演算処理装置を用いて実現される。図２１は、記録媒体に格納された自動配線決定処理を実行するためのコンピュータプログラムにより動作する本発明の実施例の自動配線決定装置の構成を示すブロック図である。
【００７７】
そのコンピュータによって実行させるコンピュータプログラムは、図２１に示すように、記憶媒体（フレキシブルディスク、ＣＤ−ＲＯＭ等の外部記憶媒体）５０に格納されており、一例として、次に説明するような構成によるコンピュータにインストールされてＣＡＤ装置（自動配線決定装置）として動作する。
【００７８】
ＣＰＵ５１は、自動配線決定装置全体を制御する。このＣＰＵ５１に、バス５２を介してＲＯＭ５３、ＲＡＭ５４、ＨＤ（ハードディスク装置）５５、マウスやキーボード等の入力装置５６、外部記憶媒体ドライブ装置５７およびＬＣＤ、ＣＲＴ等の表示装置５８が接続されている。ＣＰＵ５１の制御プログラムはＲＯＭ５３に格納されている。
【００７９】
本発明の実施例による自動配線決定処理を実行するコンピュータプログラム（以下、単に「自動配線決定処理プログラム」と称する。）は、記憶媒体５０からＨＤ５５にインストール（記憶）される。また、ＲＡＭ５４には、自動配線決定処理をＣＰＵ５１が実行する際の作業領域や、自動配線決定処理プログラムの一部が記憶される領域が確保されている。また、ＨＤ５５には、入力データ、最終データ、さらにＯＳ（オペレーティングシステム）等が予め記憶される。
【００８０】
まず、コンピュータの電源を投入すると、ＣＰＵ５１がＲＯＭ５０から制御プログラムを読み出し、さらにＨＤ５５からＯＳを読み込み、ＯＳを起動させる。これによりコンピュータは自動配線決定処理プログラムを記憶媒体５０からインストール可能な状態となる。
【００８１】
次に、記憶媒体５０を外部記憶媒体ドライブ装置５７に装着し、入力装置５６から制御コマンドをＣＰＵ５１に入力し、記憶媒体５０に格納された自動配線決定処理プログラムを読み取ってＨＤ５５等に記憶する。つまり自動配線決定処理プログラムをコンピュータにインストールする。
【００８２】
その後は、自動配線決定処理プログラムを起動させると、コンピュータは自動配線決定装置として動作する。オペレータは、自動配線決定処理プログラムが表示装置５８に表示する対話形式による所定の手順に従って、入力装置５６を操作することで、上述した自動配線決定処理を開始することができる。自動演算処理の結果得られた最適な配線に関するデータは、配線基板製造装置でそのまま利用することができ、またあるいは、ＨＤ５５に記憶したり、外部記憶媒体ドライブ装置５７を介して記憶媒体５０に一旦記録してもよい。
【００８３】
なお、図２１のコンピュータでは、記憶媒体５０に記憶されたプログラムをＨＤ５５にインストールするようにしたが、これに限らず、ＬＡＮ等の情報伝送媒体を介して、コンピュータにインストールされてもよいし、予めコンピュータに内蔵のＨＤ５５に格納されていてもよい。
【００８４】
次に、本発明による自動配線決定装置におけるコンピュータ処理の具体例を、第３の変形例として説明する。図６〜１４を参照して説明した例では、仮配線もしくは暫定配線を迂回させる際はクリアランスを確保することを前提として説明してきた。しかし、クリアランスを確保するための処理を、暫定配線を生成する度に実行すると、演算量が多くなってしまうことになる。第３の変形例は、自動配線決定処理全体の演算量を低減するものである。
【００８５】
図２２〜３５は、本発明の実施例における第３の変形例を説明する図である。ここでは、図６〜１４で既に示した具体例に第３の変形例を適用した場合について説明するものであり、特に図２２は図６と同じ図面である。
【００８６】
図７に示した暫定配線Ｗ’１は、図６に示した仮配線Ｗ１を、ビアＶ２の周りに迂回させて生成したものである。そこで、第３の変形例では、図２３に示すように、暫定配線Ｗ’１を、迂回すべきとされたビア部Ｖ２上を通るように仮配置する。
【００８７】
図８に示した暫定配線Ｗ’４は、図７に示した仮配線Ｗ４を、ビアＶ５の周りに迂回させて生成したものである。そこで、第３の変形例では、図２４に示すように、暫定配線Ｗ’４を、迂回すべきとされたビア部Ｖ５上を通るように仮配置する。
【００８８】
図９に示した暫定配線Ｗ’３は、図８に示した仮配線Ｗ３を、ビアＶ５の周りに迂回させて生成したものである。そこで、第３の変形例では、図２５に示すように、暫定配線Ｗ’３を、迂回すべきとされたビア部Ｖ５上を通るように仮配置する。
【００８９】
図１０に示した暫定配線Ｗ”１は、図９に示した暫定配線Ｗ’１を、ビアＶ５の周りに迂回させて生成したものである。そこで、第３の変形例では、図２６に示すように、暫定配線Ｗ”１を、迂回すべきとされたビア部Ｖ５上を通るように仮配置する。
【００９０】
図１３に示した暫定配線Ｗ６は、図１２に示した暫定配線Ｗ”’１を、ビアＶ４の周りに迂回させて生成したものである。そこで、第３の変形例では、図２７に示すように、暫定配線Ｗ６を、迂回すべきとされたビア部Ｖ４上を通るように仮配置する。
【００９１】
図２７の状態では、第２の交点解消処理が完了して、仮配線同士、暫定配線同士、ならびに暫定配線と仮配線とが形成する交点は全て解消されている。しかし、ビア部Ｖ２〜Ｖ５上には仮配線および暫定配線が仮配置されたままであり、さらには、ビア部Ｖ５とビア部Ｖ３との間には暫定配線Ｗ’３および暫定配線Ｗ”４が重複して存在する。すなわち、図２７の状態では、ビア部、仮配線部、暫定配線部のそれぞれの間のクリアランスは未だ確保されていない。そこで、次にこのクリアランスを確保するための処理を実行する。すなわち、第２の交点解消処理により全ての交点が解消された時点における、仮配線および／または仮配置された暫定配線が、隣接する形成物に対してクリアランスを確保するよう、仮配線および／または仮配置された暫定配線の識別情報に基づいて、仮配線および／または仮配置された暫定配線を当該ビア部からずらして本配置し、これを最適な配線として決定する処理である。このような処理を、本明細書では「本配置処理」と称する。
【００９２】
上記本配置処理は、バッド部およびビア部それぞれが並ぶ列ごとに順次実行される。このため、本配置処理を実行する前に、基板中央部に設けられた半導体チップに接続されるパッド部から、周辺部に設けられたビア部へ向かって、パッド部が並ぶ列を基準にして、それぞれが略平行となるように列ごとに予めグループ分けしておく。図２８の点線で示すように、パッド部が並ぶ列を補助線Ａ１、ビア部Ｖ１の列を補助線Ａ２、ビア部Ｖ２およびビア部Ｖ５が並ぶ列を補助線Ａ３、ビア部Ｖ３の列を補助線Ａ４、ビア部Ｖ４の列を補助線Ａ５といったように、パッド部およびビア部を各補助線で示される列にそれぞれグループ分けする。仮配置された仮配線および／または暫定配線間におけるクリアランスを確保するための本配置処理は、ビア部が存在する各補助線において、まずパッド部からビア部への方向すなわち順方向に順次実行していき、その後、順方向とは逆の方向すなわち非順行方向に順次実行していく。
【００９３】
図２８の状態では、パッド部Ｂ１〜Ｂ５が位置する補助線Ａ１に最も近くに位置する補助線は、ビア部Ｖ１が位置する補助線Ａ２である。しかし、ビア部Ｖ１に結線される暫定配線Ｗ６は該ビア部付近では非順行方向に配線されているので、この補助線Ａ２については本配置処理を実行しない。
【００９４】
補助線Ａ２の次に補助線Ａ１の近くに位置する補助線は、ビア部Ｖ２およびビア部Ｖ５が位置する補助線Ａ３である。ビア部Ｖ２上には、順方向に配線された暫定配線Ｗ６および仮配線Ｗ２が位置し、ビア部Ｖ５上には、順方向に配線された暫定配線Ｗ’３、暫定配線Ｗ”４および仮配線Ｗ５が位置する。そこで、まず補助線Ａ３について本配置処理を実行する。
【００９５】
図２８に示すように、補助線Ａ３上のビア部Ｖ２上には暫定配線Ｗ６および仮配線Ｗ２が位置するが、配線ルールを規定する設計データ内の識別情報から、ビア部Ｖ２に結線されるべきは仮配線Ｗ２であって暫定配線Ｗ６ではないことがわかるので、暫定配線Ｗ６を、ビア部Ｖ２および仮配線Ｗ２とのクリアランスが確保できる位置まで、該ビア部Ｖ２上の位置からずらす。なお、暫定配線Ｗ６の結線元であるパッド部Ｂ１と仮配線Ｗ２の結線元であるパッド部Ｂ２とは図２８に示す順に配列されていること、および、各配線が交差することはないこと、が設計ルールで規定されているので、暫定配線Ｗ６をずらす方向は図２９に示す方向となり、暫定配線ｗ１に置き換えられる。
【００９６】
また、図２８に示すように、補助線Ａ３上のビア部Ｖ５上には暫定配線Ｗ’３、暫定配線Ｗ”４および仮配線Ｗ５が位置するが、ビア部Ｖ５に結線されるべきは仮配線Ｗ５であって暫定配線Ｗ’３および暫定配線Ｗ”４ではないことがわかるので、暫定配線Ｗ’３および暫定配線Ｗ”４を、ビア部Ｖ５およびそれぞれの暫定配線および仮配線とのクリアランスが確保できる位置まで、該ビア部Ｖ５上の位置からずらす。なお、暫定配線Ｗ’３の結線元であるパッド部Ｂ３と暫定配線Ｗ”４の結線元であるパッド部Ｂ４と仮配線Ｗ５の結線元であるパッド部Ｂ５とは図２８に示す順に配列されていること、および、各配線が交差することはないこと、が設計ルールで規定されているので、暫定配線Ｗ’３および暫定配線Ｗ”４をずらす方向は図２９に示す方向となり、暫定配線Ｗ’３および暫定配線Ｗ”４は暫定配線ｗ３および暫定配線ｗ４にそれぞれ置き換えられる。
【００９７】
図２８に示すように暫定配線Ｗ６はビア部Ｖ４上に仮配置されていたので、暫定配線ｗ１を図３０に示すように暫定配線ｗ’１を介してビア部Ｖ４と結線する。また、図２８に示すように暫定配線Ｗ’３はビア部Ｖ３上に仮配置されていたので、暫定配線ｗ３を図３０に示すように暫定配線ｗ’３を介してビア部Ｖ３と結線する。暫定配線ｗ３と暫定配線ｗ’３とで図３１に示すような暫定配線Ｗ’３が得られる。また、図２８に示すように暫定配線Ｗ”４はビア部Ｖ３上に仮配置されていたので、暫定配線ｗ４を図３０に示すように暫定配線ｗ’４を介してビア部Ｖ３と結線する。
【００９８】
図３０に示すように、補助線Ａ３の順方向側に位置する補助線は、ビア部Ｖ３が位置する補助線Ａ４である。ビア部Ｖ３上には、順方向に配線された暫定配線ｗ’３および暫定配線ｗ’４が位置する。配線ルールを規定する設計データ内の識別情報から、ビア部Ｖ３に結線されるべきは暫定配線Ｗ’３すなわち暫定配線ｗ’３であって暫定配線ｗ’４ではないことがわかるので、暫定配線ｗ’４を、ビア部Ｖ３および暫定配線Ｗ’３すなわち暫定配線ｗ’３とのクリアランスが確保できる位置まで、該ビア部Ｖ３上の位置からずらす。各配線の識別情報を含む設計データから、暫定配線ｗ’４をずらす方向は図３１に示す方向となる。ずらした配線をビア部Ｖ４まで延長したものが、図３１に暫定配線ｗ”４として示されている。暫定配線ｗ４と暫定配線ｗ”４とで図３２に示すような暫定配線Ｗ”４が得られる。
【００９９】
図３１に示すように、補助線Ａ４の順方向側に位置する補助線は、ビア部Ｖ４が位置する補助線Ａ５である。ビア部Ｖ４上には、順方向に配線された暫定配線ｗ’１および暫定配線ｗ”４が位置する。配線ルールを規定する設計データ内の識別情報から、ビア部Ｖ４に結線されるべきは暫定配線Ｗ”４すなわち暫定配線ｗ”４であって、暫定配線ｗ’１ではないことがわかるので、暫定配線ｗ’１を、ビア部Ｖ４および暫定配線Ｗ’４すなわち暫定配線ｗ”４とのクリアランスが確保できる位置まで、該ビア部Ｖ４上の位置からずらす。各配線の識別情報を含む設計データから、暫定配線ｗ’１をずらす方向は図３２に示す方向となり、暫定配線ｗ’１は暫定配線ｗ”１に置き換えられる。
【０１００】
ビア部が存在する補助線は、補助線Ａ５の順方向側には存在していない。したがって順方向に配線されるべき配線ルートの位置はこの時点で確定したということになる。そこで次に、順方向とは逆の方向すなわち非順行方向に、本配置処理を補助線毎に順次実行していく。
【０１０１】
図３２に示すように、補助線Ａ５の非順行方向側に位置する、ビア部が存在する補助線は、補助線Ａ２である。順方向に配線された暫定配線ｗ”１を、補助線Ａ２上のビア部Ｖ４を迂回させてビア部Ｖ１へ向けて非順行方向に延長して配線する。迂回の際、図３３に示すように、ビア部Ｖ１との間に、距離Ｃ１Ｖ４、距離Ｃ２Ｖ４および距離Ｃ３Ｖ４のクリアランスが確保できるよう、配線する。これにより、図３４に示すような暫定配線Ｗ６が得られる。
【０１０２】
図３４に示す暫定配線Ｗ６は、暫定配線Ｗ”４との間でクリアランスを確保できていないので、図３５に示すようにその位置を調整し、暫定配線Ｗ’６を得る。つまり、図３４に示すパッド部Ｂ１とビア部Ｖ１とを結ぶ暫定配線Ｗ６は、図３５に示すようなパッド部Ｂ１とビア部Ｖ１とを結ぶ暫定配線Ｗ’６に置き換えられたことになる。
【０１０３】
図３５の状態では、仮配線同士、暫定配線同士、ならびに暫定配線と仮配線とが形成する交点は全て解消されているので、暫定配線Ｗ’６、仮配線Ｗ２、暫定配線Ｗ’３、暫定配線Ｗ”４および仮配線Ｗ５を、非順行配線を有する最適な配線として確定する。
【０１０４】
このように第３の変形例によれば、上述の実施例ならびに第１および第２の変形例における自動配線決定処理全体の演算量を低減することができる。
【産業上の利用可能性】
【０１０５】
本発明によれば、基板上における各パッド部からそれぞれの結線先である各ビア部への最適な配線の位置を設計するにあたり、配線の向きが、ある一部分において大方の方向とはほぼ逆向きとなるような傾向があっても、コンピュータなどを用いた演算処理により自動的に配線の位置を決定することができる。
【０１０６】
例えば、ＭＣＭ（Ｍｕｌｔｉ−Ｃｈｉｐ  Ｍｏｄｕｌｅ）、ＨＤＳ（Ｈｉｇｈ  Ｄｅｎｓｉｔｙ  Ｓｕｂｓｔｒａｔｅ）、あるいはＳＩＰ（Ｓｙｓｔｅｍ  ｉｎ  Ｐａｃｋａｇｅ）などのような、配線の向きがある一部分において大方の方向とはほぼ逆向きとなるような非順行配線が存在し得る配線基板に対しても、バランスのよい配線の設計をコンピュータ等の演算処理装置を用いて自動化することができる。コンピュータによる演算処理により、従来のように設計者自らの技量、経験、勘などに左右されることなく、配線バランスのよい安定した品質の非順行配線に係る配線ルートを短時間で容易に設計することができる。例えば、従来、試行錯誤しながらの手動による配線設計によれば１〜３週間程度を要していたものが、本発明によれば２〜３日で自動的に演算処理結果を得ることができる。このような設計時間の短縮および設計者の負担の軽減の結果、半導体パッケージの製造コストも低減できる。
【０１０７】
バランスのよい配線パターンは、バランスの悪いものに比べ、配線距離が短いので経済的であり、製造容易であり、そして製造時における製品エラーの発生率も低い。また、電気的にも安定した性質を示す。さらには、バランスよく配線されることによって、例えば熱による基板の変形が生じてもその変形はほぼ均等なものとなるので、短絡や断線等の配線エラーも生じにくい。またさらには、ある程度の規則性を有して整然と配線されている半導体パッケージのほうが見た目にも美しいので、半導体パッケージの完成品の販売政策上有利である。
【図面の簡単な説明】
【０１０８】
【図１】本発明による自動配線決定装置の原理ブロック図である。
【図２】本発明の実施例による自動配線決定方法の動作フローを示すフローチャートである。
【図３】本発明の実施例の自動配線決定装置による最適な配線の生成の第１の具体例を説明する図である。
【図４】本発明の実施例の自動配線決定装置による最適な配線の生成の第２の具体例を説明する図（その１）である。
【図５】本発明の実施例の自動配線決定装置による最適な配線の生成の第２の具体例を説明する図（その２）である。
【図６】本発明の実施例の自動配線決定装置による最適な配線の生成の第３の具体例を説明する図（その１）である。
【図７】本発明の実施例の自動配線決定装置による最適な配線の生成の第３の具体例を説明する図（その２）である。
【図８】本発明の実施例の自動配線決定装置による最適な配線の生成の第３の具体例を説明する図（その３）である。
【図９】本発明の実施例の自動配線決定装置による最適な配線の生成の第３の具体例を説明する図（その４）である。
【図１０】本発明の実施例の自動配線決定装置による最適な配線の生成の第３の具体例を説明する図（その５）である。
【図１１】本発明の実施例の自動配線決定装置による最適な配線の生成の第３の具体例を説明する図（その６）である。
【図１２】本発明の実施例の自動配線決定装置による最適な配線の生成の第３の具体例を説明する図（その７）である。
【図１３】本発明の実施例の自動配線決定装置による最適な配線の生成の第３の具体例を説明する図（その８）である。
【図１４】本発明の実施例の自動配線決定装置による最適な配線の生成の第３の具体例を説明する図（その９）である。
【図１５】本発明の実施例において、第１の交点解消処理により生成された暫定配線では十分なクリアランスを確保することができない場合を説明する図である。
【図１６】本発明の実施例における第１の変形例を説明する図（その１）である。
【図１７】本発明の実施例における第１の変形例を説明する図（その２）である。
【図１８】本発明の実施例における第２の変形例を説明する図（その１）である。
【図１９】本発明の実施例における第２の変形例を説明する図（その２）である。
【図２０】本発明の実施例における第２の変形例を説明する図（その３）である。
【図２１】記録媒体に格納された自動配線決定処理を実行するためのコンピュータプログラムにより動作する本発明の実施例の自動配線決定装置の構成を示すブロック図である。
【図２２】本発明の実施例における第３の変形例を説明する図（その１）である。
【図２３】本発明の実施例における第３の変形例を説明する図（その２）である。
【図２４】本発明の実施例における第３の変形例を説明する図（その３）である。
【図２５】本発明の実施例における第３の変形例を説明する図（その４）である。
【図２６】本発明の実施例における第３の変形例を説明する図（その５）である。
【図２７】本発明の実施例における第３の変形例を説明する図（その６）である。
【図２８】本発明の実施例における第３の変形例を説明する図（その７）である。
【図２９】本発明の実施例における第３の変形例を説明する図（その８）である。
【図３０】本発明の実施例における第３の変形例を説明する図（その９）である。
【図３１】本発明の実施例における第３の変形例を説明する図（その１０）である。
【図３２】本発明の実施例における第３の変形例を説明する図（その１１）である。
【図３３】本発明の実施例における第３の変形例を説明する図（その１２）である。
【図３４】本発明の実施例における第３の変形例を説明する図（その１３）である。
【図３５】本発明の実施例における第３の変形例を説明する図（その１４）である。
【図３６】半導体パッケージにおいて配線すべきネットを例示する図である。
【図３７】本明細書に添付された図面において表されるビア部、パッド部および配線すべきネットの凡例を説明する図である。
【図３８】図３６に示されたネットの交差を、特開２００２−０８３００６号公報に記載された技術を用いて解消した配線設計結果を例示する図である。
【図３９】図３６に示されたネットの交差を、交差解消後の配線がバランスよく配置されるように配線ルートを設計した場合を例示する図である。
【図４０】非順行配線の一例を例示する図である。
【図４１】非特許文献１に記載された技術による、非順行配線の生成原理を示す図である。
【符号の説明】
【０１０９】
１    自動配線決定装置
１１    第１の交点解消手段
１２    第２の交点解消手段
２１    第１の判定手段
２２    カウント手段
２３    第２の判定手段
【図１】
2006268462.tif 000003
【図２】
2006268462.tif 000004
【図３】
2006268462.tif 000005
【図４】
2006268462.tif 000006
【図５】
2006268462.tif 000007
【図６】
2006268462.tif 000008
【図７】
2006268462.tif 000009
【図８】
2006268462.tif 000010
【図９】
2006268462.tif 000011
【図１０】
2006268462.tif 000012
【図１１】
2006268462.tif 000013
【図１２】
2006268462.tif 000014
【図１３】
2006268462.tif 000015
【図１４】
2006268462.tif 000016
【図１５】
2006268462.tif 000017
【図１６】
2006268462.tif 000018
【図１７】
2006268462.tif 000019
【図１８】
2006268462.tif 000020
【図１９】
2006268462.tif 000021
【図２０】
2006268462.tif 000022
【図２１】
2006268462.tif 000023
【図２２】
2006268462.tif 000024
【図２３】
2006268462.tif 000025
【図２４】
2006268462.tif 000026
【図２５】
2006268462.tif 000027
【図２６】
2006268462.tif 000028
【図２７】
2006268462.tif 000029
【図２８】
2006268462.tif 000030
【図２９】
2006268462.tif 000031
【図３０】
2006268462.tif 000032
【図３１】
2006268462.tif 000033
【図３２】
2006268462.tif 000034
【図３３】
2006268462.tif 000035
【図３４】
2006268462.tif 000036
【図３５】
2006268462.tif 000037
【図３６】
2006268462.tif 000038
【図３７】
2006268462.tif 000039
【図３８】
2006268462.tif 000040
【図３９】
2006268462.tif 000041
【図４０】
2006268462.tif 000042
【図４１】
2006268462.tif 000043