(57)【要約】【課題】単層配線で安価に、半導体チップのパッドとパッケージのピンとの間の接続を自動的に決定することができるパッケージピンの割り付け方法を提供する。【解決手段】複数のパッドの各々を出発地として複数の飛行体を出発させ、複数の飛行体のそれぞれが、自らの飛行速度を、現在飛行中の飛行体群の重心に近づき、飛行体群の重心の移動速度に近づき、かつ、飛行体群に含まれる他の飛行体のいずれか、もしくは、複数の飛行体の現在までの飛行経路のいずれかとの距離が所定値以下になった場合には、他の飛行体もしくは飛行経路のいずれかから離れるように調整しながら対応するパッケージピンまでの接続経路を決定し、かつ、自らの飛行方向の所定角度範囲内に、複数のパッケージピンのうち、飛行体群に含まれる他の飛行体のいずれも到着しておらず、かつ、自分自身から最も遠くに配置されているパッケージピンを到着地として選択し、それぞれの出発地のパッドに対応するパッケージピンとして割り付ける。【選択図】図１１
2008040801.tif 000002
【特許請求の範囲】
【請求項１】
半導体集積回路チップの少なくとも１つの辺に沿って配置された複数のパッドのそれぞれから、該少なくとも１つの辺の外側に前記複数のパッドのそれぞれに対応して配置された複数のパッケージピンまでの接続経路を決定し、前記複数のパッドのそれぞれに対応するパッケージピンを割り付ける方法において、
前記複数のパッドのそれぞれを出発地として出発する複数の飛行体を想定し、該複数の飛行体を各々対応する出発地から出発させ、
該複数の飛行体のそれぞれが、自らの飛行速度を、
（１）自らが、前記複数の飛行体の内の現在飛行しているものからなる飛行体群の重心に近づき、
（２）前記飛行体群の重心の移動速度に近づき、かつ、
（３）前記飛行体群に含まれる他の飛行体のいずれか、もしくは、前記複数の飛行体の現在までの飛行経路のいずれかとの距離が所定値以下になった場合には、該他の飛行体もしくは飛行経路のいずれかから離れる
ように調整しながら前記対応するパッケージピンまでの接続経路を決定し、かつ、
自らの飛行方向の所定角度範囲内にある前記複数のパッケージピンのうち、前記複数の飛行体に含まれる他の飛行体のいずれも到着しておらず、かつ、自分自身から最も遠くに配置されている到着可能なパッケージピンを到着地として選択し、
前記複数の飛行体のそれぞれの到着地として選択されたパッケージピンを、前記複数の飛行体のそれぞれの出発地のパッドに対応するパッケージピンとして割り付けることを特徴とするパッケージピンの割り付け方法。
【請求項２】
前記飛行体の出発以前に、あらかじめ、前記複数のパッドの一部に対するパッケージピンの割付が行われており、
前記飛行体の飛行速度の調整における前記複数の飛行体の現在までの飛行経路が、前記一部のパッドと該一部のパッドに割り付けられたパッケージピンとの間の接続経路を含むことを特徴とする請求項１記載のパッケージピンの割り付け方法。
【請求項３】
前記複数の飛行体が、前記半導体集積回路チップの隣りあう２つの辺のそれぞれに沿って配置された複数のパッドの両方から出発した飛行体を含み、
前記飛行体の飛行速度の調整において、調整の対象とする飛行体が出発したパッドが配置された辺と同一の辺に配置されたパッドから出発した飛行体を、異なる辺に配置されたパッドから出発した飛行体よりも重視して、前記飛行体群の重心とその移動速度を求めることを特徴とする請求項１または２記載のパッケージピンの割り付け方法。
【請求項４】
前記対象とする飛行体が、前記隣りあう２つの辺の延長線に囲まれた領域に侵入したときには、前記飛行体群の重心とその移動速度を、前記隣りあう２つの辺に配置されたパッドから出発した飛行体を同等に考慮して求めることを特徴とする請求項３記載のパッケージピンの割り付け方法。
【請求項５】
前記複数の飛行体のそれぞれが出発する時に、自らの出発地であるパッドが配置された前記半導体集積回路チップの辺に垂直な方向に所定の飛行速度で出発することを特徴とする請求項１ないし４のいずれかに記載のパッケージピンの割り付け方法。
【請求項６】
前記複数の飛行体のそれぞれが、前記（１）、（２）、（３）に加えて、出発後の時間の経過につれて、自らが出発したパッドから近い方の辺の一方の端部に向かう所定速度のベクトルが与えられ、自らの前記飛行速度を調整することを特徴とする請求項５記載のパッケージピンの割り付け方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、半導体集積回路チップ（以下、半導体チップという）の各々のＩＯパッド（入出力パッド）（以下、パッドという）から、それらに各々対応するパッケージのピン（端子）までの接続経路を決定し、各々のパッドに対応するパッケージピンを割り付ける方法に関するものである。
【背景技術】
【０００２】
半導体チップをパッケージに封止する場合、半導体チップのパッドと、そのパッケージのピン（例えば、ＰＧＡ：Pin Grid Arrayの場合はピン、ＢＧＡ：Ball Grid Arrayの場合はボール。以下、説明の都合上、パッケージのピンもしくはパッケージピンと表現するが、その場合のピン（端子）は、上記ＰＧＡ等のピンはもちろん、ＢＧＡ等のボールも含むものとする。）との間が配線（ボンディングワイヤもしくは配線基板上の配線）によって接続される。
【０００３】
従来、半導体チップのパッドと、パッケージのピンとの間を接続する先行技術文献として、例えば特許文献１、２などが知られている。
【０００４】
特許文献１は、ＡＳＩＣ（Application Specific Integrated Circuit：特定用途向けＩＣ（集積回路））等の半導体パッケージの設計段階におけるピンアサイン業務の支援を行う半導体ピンアサイン支援システムに関するものである。
【０００５】
例えば、同文献には、半導体パッケージの設計段階におけるピンアサイン業務の支援を行う半導体ピンアサイン支援方法であって、上記半導体パッケージのボール間ピッチ、パッド径、およびボール列をもとに予定のプリント基板において配線がピン間を通せるか否かを判定する工程を備えたことを特徴とする半導体ピンアサイン支援方法が開示されている。
【０００６】
また、特許文献２は、半導体チップに設けられたボンディングパッドと、半導体パッケージに設けられたピン（端子）との間で最適な配線の経路を設計する配線設計装置、配線判定装置およびこれらの方法に関するものである。
【０００７】
例えば、同文献には、１つの面上に設けられた複数の点［シンク要素］のいずれかと、前記面上に設けられたシンク要素以外の複数の点［ソース要素］のいずれかとの間を、前記面上を通る経路で接続する配線を設計する配線設計方法であって、ドローネの三角形分割法により、シンク要素およびソース要素を頂点とする複数の仮想的な三角形を前記面上に作成し、作成した三角形の内、それぞれソース要素のいずれかを頂点とする三角形に頂点として含まれるシンク要素を最低のレベル（レベル１）に分類し、レベルＫ（Ｋ＝１以上の整数）のシンク要素のいずれかを頂点とする三角形の他の頂点の内、レベルＫ，（Ｋ−１）以外のシンク要素をレベル（Ｋ＋１）に分類し、シンク要素のいずれかと、この点に対応するソース要素のいずれかとの間をそれぞれ接続する複数の配線の経路を、これらの配線それぞれが、作成した三角形の内、配線が通過する三角形に頂点として含まれるシンク要素のレベルが最低になるように設計する配線設計方法が開示されている。
【０００８】
上記特許文献１、２に開示の従来技術では、いずれも多数の配線候補（候補経路）を作成し、一定の評価基準に従って、成績の悪い候補経路を削除していくというアルゴリズムが採用されている。
【０００９】
【特許文献１】特開２００５−２５９０３６号公報
【特許文献２】特開平１１−２７２７１６号公報
【発明の開示】
【発明が解決しようとする課題】
【００１０】
一般的に、２点間の配線を行う場合、その２点間の場所（位置）が決定されれば、例えばダイクストラ法等の最短経路探索法を利用して、２点間の配線を効率的に行うことができる。
【００１１】
しかし、上記半導体チップのパッドとパッケージのピンとの間の配線では、まず、半導体チップの特定のパッド、例えば電源、グランド、差動信号等の特殊な信号とパッケージのピンとの間の割り付けを優先的に行う必要がある。従って、計算量が膨大になる上、配線同士の交差が発生する可能性も高くなる。配線の交差を解消するには、人手で配線の接続経路を修正するか、交差を可能とするために多層配線を行う必要があるが、配線層が多くなると生産コストが上昇するという問題がある。
【００１２】
本発明の目的は、前記従来技術に基づく問題点を解消し、単層配線で安価に、半導体チップのパッドとパッケージのピンとの間の接続を自動的に決定することができるパッケージピンの割り付け方法を提供することにある。
【課題を解決するための手段】
【００１３】
上記目的を達成するために、本発明は、半導体集積回路チップの少なくとも１つの辺に沿って配置された複数のパッドのそれぞれから、該少なくとも１つの辺の外側に前記複数のパッドのそれぞれに対応して配置された複数のパッケージピンまでの接続経路を決定し、前記複数のパッドのそれぞれに対応するパッケージピンを割り付ける方法において、
前記複数のパッドのそれぞれを出発地として出発する複数の飛行体を想定し、該複数の飛行体を各々対応する出発地から出発させ、
該複数の飛行体のそれぞれが、自らの飛行速度を、
（１）自らが、前記複数の飛行体の内の現在飛行しているものからなる飛行体群の重心に近づき、
（２）前記飛行体群の重心の移動速度に近づき、かつ、
（３）前記飛行体群に含まれる他の飛行体のいずれか、もしくは、前記複数の飛行体の現在までの飛行経路のいずれかとの距離が所定値以下になった場合には、該他の飛行体もしくは飛行経路のいずれかから離れる
ように調整しながら前記対応するパッケージピンまでの接続経路を決定し、かつ、
自らの飛行方向の所定角度範囲内にある前記複数のパッケージピンのうち、前記複数の飛行体に含まれる他の飛行体のいずれも到着しておらず、かつ、自分自身から最も遠くに配置されている到着可能なパッケージピンを到着地として選択し、
前記複数の飛行体のそれぞれの到着地として選択されたパッケージピンを、前記複数の飛行体のそれぞれの出発地のパッドに対応するパッケージピンとして割り付けることを特徴とするパッケージピンの割り付け方法を提供するものである。
【００１４】
ここで、前記飛行体の出発以前に、あらかじめ、前記複数のパッドの一部に対するパッケージピンの割付が行われており、
前記飛行体の飛行速度の調整における前記複数の飛行体の現在までの飛行経路が、前記一部のパッドと該一部のパッドに割り付けられたパッケージピンとの間の接続経路を含むことが好ましい。
【００１５】
また、前記複数の飛行体が、前記半導体集積回路チップの隣りあう２つの辺のそれぞれに沿って配置された複数のパッドの両方から出発した飛行体を含み、
前記飛行体の飛行速度の調整において、調整の対象とする飛行体が出発したパッドが配置された辺と同一の辺に配置されたパッドから出発した飛行体を、異なる辺に配置されたパッドから出発した飛行体よりも重視して、前記飛行体群の重心とその移動速度を求めることが好ましい。
【００１６】
また、前記対象とする飛行体が、前記隣りあう２つの辺の延長線に囲まれた領域に侵入したときには、前記飛行体群の重心とその移動速度を、前記隣りあう２つの辺に配置されたパッドから出発した飛行体を同等に考慮して求めることが好ましい。
【００１７】
また、前記複数の飛行体のそれぞれが出発する時に、自らの出発地であるパッドが配置された前記半導体集積回路チップの辺に垂直な方向に所定の飛行速度で出発することが好ましい。
【００１８】
また、前記複数の飛行体のそれぞれが、前記（１）、（２）、（３）に加えて、出発後の時間の経過につれて、自らが出発したパッドから近い方の辺の一方の端部に向かう所定速度のベクトルが与えられ、自らの前記飛行速度を調整することが好ましい。
【発明の効果】
【００１９】
本発明によれば、半導体集積回路チップのパッドと、パッケージのピンとの間の接続経路を自動的に決定し、各々のパッドに対応するパッケージピンを自動的に割り付けることができる。すなわち、プリント基板や差動配線等に由来する制約条件を考慮したピンの割り付けを行うことができ、単層基板であっても交差しない配線を少ない計算量で得ることができる。また、多層配線を避けることができるため、生産コストを安く抑えることができる。
【発明を実施するための最良の形態】
【００２０】
以下に、添付の図面に示す好適実施形態に基づいて、本発明のパッケージピンの割り付け方法を詳細に説明する。
【００２１】
本発明のパッケージピンの割り付け方法は、後述するＢｏｉｄ（Bird-andrOID）モデルを適用して、半導体チップの少なくとも１つの辺に沿って配置された複数のパッドのそれぞれから、その少なくとも１つの辺の外側に複数のパッドのそれぞれに対応して配置された複数のパッケージピンまでの接続経路を自動的に決定し、複数のパッドのそれぞれに対応するパッケージのピンを自動的に割り付けるものである。
【００２２】
ここで、本発明の基礎となるＢｏｉｄモデルについて説明する。
【００２３】
近年、複雑系の研究が進められている。例えば、鳥の群れの運動を計算機でシミュレート（模擬）することは、従来の方法では不可能であった。しかし、以下の１〜３の条件（ルール）で鳥の群れの動きをシミュレートできることが証明されている。
【００２４】
すなわち、下記１〜３の条件を満足するように、複数の鳥からなる仲間の鳥の群れに含まれる各々の鳥を動作させる。
１．仲間の鳥の群れがいる方向（重心）に向かって飛行する（図１参照）。
２．仲間の鳥の群れと飛行速度および飛行方向を合わせる（図２参照）。
３．仲間の鳥の群れのうちの他のいずれかの鳥に近づきすぎたら離れる（図３参照）。
【００２５】
ここで、図１〜３において、二等辺三角形は鳥をモデル化したものである。白抜きの二等辺三角形１０は、上記１〜３の条件を適用して動作する対象の鳥の１つを表す。また、所定半径の円内（図１〜３では、その上下の図示が省略されている）の斜線付の二等辺三角形１２は、対象の鳥の仲間の鳥の群れを表す。なお、仲間の鳥の群れが含まれる範囲は、所定半径の円内に限らず、必要に応じて適宜決定することができる。
【００２６】
図１において、ポイントＡは、仲間の鳥の群れの重心を表す。この重心は、仲間の鳥の群れに含まれる全ての鳥（図１の場合には４羽の鳥）１２の位置から算出され、図１中、矢印で示すベクトルが発生される。対象の鳥１０は、矢印のベクトルに従い、重心に向かって所定の速度（速さおよび方向）で飛行する。なお、対象の鳥１０が、重心に向かって飛行する速度は、必要（重心の移動速度等）に応じて適宜決定することができる。
【００２７】
図２において、二等辺三角形の先端部分から延びる実線は、鳥の飛行速度を表す飛行ベクトルである。線の向きが鳥の飛行方向を表し、その長さが鳥の飛行する速さを表す。仲間の全ての鳥（図２の場合には６羽）１２の飛行ベクトルから、その飛行速度の平均値が算出され、図２中、矢印で示すベクトルが発生される。対象の鳥１０は、矢印のベクトルに従い、自分自身の飛行ベクトルを修正する。対象の鳥１０を表す二等辺三角形の先端部分から延びる点線が、修正後の対象の鳥の飛行ベクトルとなる。
【００２８】
図３において、対象の鳥１０は、その左側の鳥１２に近づきすぎであると仮定する。近づきすぎかどうかの判断基準（距離）は、必要に応じて適宜決定することができる。近づきすぎであると判断すると、仲間の全ての鳥（図３の場合には３羽）１２の位置から、仲間の全ての鳥１２と近づきすぎとならない位置が算出され、図３中、矢印で示すベクトルが発生される。対象の鳥１０は、矢印で示すベクトルに従い、仲間の全ての鳥１２から離れる方向へ所定速度で飛行する。なお、離れる時の対象の鳥１０の飛行速度は、必要に応じて適宜決定することができる。
【００２９】
ここで、図４を参照して、２羽の鳥が近づきすぎである場合の動作を説明する。図４中、左下の第１の鳥１４が、飛行ベクトルａで示される飛行速度で右上の第２の鳥１６の方へ向かって飛行する場合を考える。
【００３０】
この場合、第１の鳥１４と第２の鳥１６との間の距離Ｌが、近づきすぎであると判断する基準値を超えた時に、第１の鳥１４が、第２の鳥１６から離れる方向は飛行ベクトルａの反対方向である。また、離れる強さ（反発力）は、２つの鳥１４、１６の間の距離Ｌと反比例する。何ら限定されるわけではないが、例えば２羽の鳥１４、１６の距離の絶対値｜Ｌ｜が、判断の基準値の最小単位となった時の反発力を最大とし、パッドピッチに等しい時に反発力が最小となるように設定することができる。
【００３１】
上記１〜３の条件に従うシミュレーションモデルをＢｏｉｄモデルという。Ｂｏｉｄモデルについては、例えばインターネット＜ＵＲＬ：http://www.1101.com/morikawa/2001-06-25.html＞［平成１８年５月１６日検索］において説明されている。
【００３２】
前述の通り、本発明では、基本的に、このＢｏｉｄモデルを、半導体チップの各々のパッドから対応するパッケージのピン（端子）までの接続経路を自動的に決定し、それぞれ対応するパッケージピンを自動的に割り付ける作業に適用する。パッケージピンの割り付け作業は、１つの辺について実施するだけでも良いが、好ましくは２辺、より好ましくは３辺、最も好ましくは全ての辺（４辺）について実施することである。
【００３３】
また、既に述べた通り、本発明のいうパッケージのピン（パッケージピン）はパッケージの端子のことである。本発明では、ＰＧＡの場合のピンはもちろん、ＢＧＡの場合のボール（半田ボール等）も含めて、以下、ピンと表現する。説明を簡単にするため、電源およびグランドについては、パッケージのピンの割り付けが既に終了しているものとする。すなわち、以下、信号配線のみについて説明する。
【００３４】
半導体チップの各々の辺（４辺）に配置された複数のパッドのそれぞれを出発地として出発（飛行）する複数の飛行体を想定する。そして、これら複数の飛行体を各々対応する辺の出発地となるパッドから出発させる。この時、前述のＢｏｉｄモデルの１〜３の条件は、下記の通りとなる。また、本発明では、Ｂｏｉｄモデルの３つの条件に、さらに、以下の４〜１０の条件を追加する。
【００３５】
１．複数の飛行体の内の現在飛行しているものからなる飛行体群の重心に近づく方向に移動する（飛行方向を変える）（図１参照）。
【００３６】
２．飛行体群の重心の移動速度に近づくように飛行速度を合わせる（図２参照）。
【００３７】
３．飛行体群に含まれる他の飛行体のいずれか、もしくは、複数の飛行体の現在までの飛行経路のいずれかとの距離が所定値以下になった場合には、他の飛行体もしくは飛行経路のいずれかから離れる方向に移動する（図３参照）。ここで、複数の飛行体の現在までの飛行経路は、例えば電源、グランド、差動信号、その他の通常の信号等の一部のパッドとその一部のパッドに割り付けられたパッケージピンとの間の接続経路を含む。
【００３８】
４．複数の飛行体のそれぞれは、出発する時に、初期状態として、自分自身の出発地であるパッドが配置された半導体チップの辺（自分自身が配置されている辺）に垂直な方向に所定の飛行速度で出発する（図５参照）。
【００３９】
５．複数の飛行体のそれぞれには、上記条件１〜３に加えて、出発後の時間の経過につれて、自分自身が出発したパッドから近い方の一方の端部に向かう所定速度のベクトル１８が与えられ、自分自身の飛行速度を調整する（図６参照）。このベクトル１８によって、複数の飛行体のそれぞれの飛行する方向は、出発地の辺に対して垂直な方向から、そのパッドに近い方の辺の端部側へ向かって、辺に対して平行に徐々に変化する。
【００４０】
６．差動信号は、ペア（出発地が隣接していれば、到着地として選択されるパッケージピンも隣接させる）である等の条件を設定し、基本的にはＢｏｉｄモデルを適用することなく、優先的に接続経路とその到着地を決定する（図７参照）。
【００４１】
７．プリント基板や、その他の制約により、出発地のパッド、および、到着地のパッケージピンがあらかじめ決められている優先信号の場合、基本的にはＢｏｉｄモデルを適用することなく、その条件を設定し、優先的に両者の間の接続経路を決定する（図８参照）。
【００４２】
８．各々の飛行体は、上記の電源、グランド、差動信号、優先信号などの飛行経路（接続経路）に加えて、他の飛行体の飛行経路と交差しないように、Ｂｏｉｄモデルを適用して、自分自身の飛行経路（接続経路）を決定する（図９参照）。
【００４３】
９．条件７、６の順に、優先信号の接続経路と、差動信号の接続経路および到着地を優先的に決定する。その後、所定の一定時間毎に、半導体チップの各辺の中央部側から両端部側へ向かって、１辺当たり２つずつ（１、２、３、…の順序で）飛行体を順次飛行させる（図１０参照）。
【００４４】
１０．複数の飛行体のそれぞれは、自分自身の飛行方向の所定角度範囲内にある複数のパッケージピンのうち、複数の飛行体に含まれる他の飛行体のいずれも到着しておらず、かつ、自分自身から最も遠くに配置されている着陸可能なパッケージピンを到着地として選択する。そして、複数の飛行体のそれぞれの到着地として選択されたパッケージピンを、複数の飛行体のそれぞれの出発地のパッドに対応するパッケージピンとして割り付ける。
【００４５】
上記１〜１０の条件に従い、複数の飛行体のそれぞれが、自らの飛行速度を調整しながら飛行し、複数の飛行体のそれぞれの出発地であるパッドに対応するパッケージピンまでの接続経路と、到着地であるパッケージピンを決定する。
【００４６】
以下、図１１に示すフローチャートを参照しながら、本実施形態によるパッケージピンの割り付け方法の各工程について具体的に説明する。
【００４７】
まず、条件９に従って、条件７、６の順に飛行体を飛行させる。
【００４８】
すなわち、条件７に従い、優先信号について、Ｂｏｉｄモデルを適用することなく、それ以外の手法により、あらかじめ決定されている出発地のパッドから到着地のパッケージピンまでの接続経路を優先的に決定する（ステップＳ１）。
【００４９】
なお、条件７において、Ｂｏｉｄモデルを適用して接続経路を決定することも可能である。その場合、例えば図１２に示すように、その出発地のパッド２０と到着地のパッケージピン２２、点線で示す飛行範囲等の制約条件を設定し、その出発地のパッド２０から対象の飛行体だけを飛行させて、到着地のパッケージピン２２までの接続経路を決定する。また、Ｂｏｉｄモデル以外の手法は、２点間を接続する各種の手法がいずれも適用可能である。
【００５０】
続いて、条件６に従い、差動信号などの特別な条件の設定を必要とする出発地のパッドについて、Ｂｏｉｄモデルを適用することなく、それ以外の手法により、その接続経路と到着地のパッケージピンを決定する（ステップＳ２）。
【００５１】
なお、図７に示すように、差動信号の配線がＯＫ（良好）かＮＧ（不良）かの判断は、差動信号を入力として使用するマクロセルが要求するスキュー（２つの配線間の遅延差）の値によって決定される。スキューを満たすか否かは、両者の配線長差と信号伝播速度等から求めることが可能である。また、条件６においても、Ｂｏｉｄモデルはもちろん、２点間を接続する各種の手法がいずれも適用可能である。
【００５２】
続いて、上記信号以外の信号について、各辺のパッドから飛行体を飛行させる（ステップＳ３）。ステップＳ３は、以下に述べるステップＳ４〜Ｓ８によって構成される。
【００５３】
すなわち、条件９に従い、図１０に示すように、上記以外の全ての出発地のパッドについて、所定の一定時間毎に、半導体チップの各辺の中央部側から両端部側へ向かって、１辺当たり２つずつ飛行体を順次飛行させる（ステップＳ４）。
【００５４】
この場合、図１３に示すように、半導体チップ２４の各辺（４辺）を、その中央部から２分し、図１３中、点線の楕円で囲まれた８つのグループ２６に分割する。各々のグループ２６に含まれる各々の飛行体は、条件９に従い、所定の一定時間毎に、各辺の中央部側から、その両端部側へ向かって１つずつ順に出発する。つまり、所定の一定時間毎に、各辺の中央部側から２つずつ、全ての辺では合計８つの飛行体が同時に出発する。
【００５５】
各辺から飛行体が出発する場合、条件４、５に従って出発する。
【００５６】
すなわち、各々の飛行体は、条件４に従い、図５に示すように、初期状態として、各辺の各々の出発地のパッドの位置から、そのパッドが配置されている辺に垂直な方向に所定の飛行速度で出発する（ステップＳ５）。
【００５７】
また、各々の飛行体は、条件５に従い、図６に示すように、出発後の時間の経過につれて、自分自身が出発したパッドから近い方の一方の端部に向かう所定速度のベクトル１８が与えられ、自分自身の飛行速度および飛行方向を調整する（ステップＳ５）。例えば、図６に示す例の場合、上辺の中央部よりも右側に配置された出発地のパッドから出発した飛行体には、その辺の右端へ向かうベクトルが与えられる。その逆に、左側の飛行体は、その辺の左端へ向かうベクトルが与えられる。
【００５８】
続いて、各々の飛行体は、条件１〜３に従い、Ｂｏｉｄモデルを適用して、その飛行速度を自ら調整しながら到着地を目指して飛行し、その飛行経路（接続経路）を決定する（ステップＳ６）。
【００５９】
この時、各々の飛行体は、条件８に従い、障害物（本実施形態の場合、飛行体群に含まれる他の飛行体のいずれか、もしくは、複数の飛行体の他のいずれかの飛行体の現在までの飛行経路のいずれか）と交差しないように、障害物との距離が所定値以下になった場合、その障害物から離れるように飛行する（ステップＳ７）。なお、飛行体が障害物から離れる場合、条件３に従って回避行動をとる。
【００６０】
所定の時間の後には、図１３に示す８つのグループ毎に１つの飛行体の群れ（飛行体群）、すなわち、全体で８つの飛行体群が構成される。この場合、各々のグループにおいて、全ての出発地のパッドから出発した飛行体の全てが同時に飛行している場合もあり得るし、全ての飛行体が出発する前に、それ以前に出発した飛行体の接続経路と到着地が既に決定している場合もあり得る。
【００６１】
続いて、各々の飛行体は、条件１０に従い、自分自身の飛行方向の所定角度範囲内にある複数のパッケージピンのうち、複数の飛行体に含まれる他の飛行体のいずれも到着しておらず、かつ、自分自身から最も遠くに配置されている到着可能なパッケージピンを到着地として選択して着陸する（ステップＳ８）。
【００６２】
例えば、図１４に示すように、飛行体２８が、矢印の方向に飛行していると仮定する。この時、この飛行体２８の飛行方向に対して、図１４中、点線で示すように、所定の一定角度範囲内のパッケージピンに到着する等の制約条件を設定する。この場合、到着地となり得るパッケージピンは、６つに限定されるが、現在の飛行体の位置から最も遠い位置の到着地の３つの斜線付のパッケージピン３０、３１、３２は既に割り当てられているので、その手前の網掛けのパッケージピン３４が到着地として選択される。
【００６３】
上記ステップＳ６〜Ｓ８までの動作は、以下に述べるデッドロックが発生した場合を除いて、基本的に、複数の飛行体のそれぞれの接続経路と到着地のパッケージピンが決定するまで繰り返し行われる。
【００６４】
ここで、複数の飛行体（飛行体群）が、半導体チップの隣りあう２つの辺のそれぞれに沿って配置された複数のパッドの両方から出発した飛行体を含む場合を考える。
【００６５】
例えば、半導体チップの右辺のパッドから出発した飛行体が、上辺のパッドから出発した飛行体のグループに侵入した場合、両者を含めて新たな飛行体のグループと見なし、飛行体の飛行速度の調整においては、例えば調整の対象とする飛行体が出発したパッドが配置された辺と同一の辺に配置されたパッドから出発した飛行体を、異なる辺に配置されたパッドから出発した飛行体よりも重視して、飛行体群の重心とその移動速度を求める。
【００６６】
また、図１５に示すように、対象とする飛行体が、隣りあう２つの辺（図１５の場合、上辺と右辺）の延長線に囲まれた領域に侵入した場合、同様に両者を含めて新たな飛行体のグループと見なす。そして、例えば飛行体群の重心とその移動速度を、隣りあう２つの辺に配置されたパッドから出発した飛行体を同等に考慮して求める。この時、デッドロックが生じる場合には、各辺に対して優先度を設定するなどしても良い。
【００６７】
上記のようにして、各々のグループの各々の飛行体は、自分の出発地のパッドから出発し、所定の経路を通って所定の到着地のパッケージピンに到着する。そして、出発地と到着地との間の全ての接続経路が決定した場合（ステップＳ９で‘Ｙｅｓ’）には、処理を終了する。一方、デッドロックが生じて配線不能となった場合（ステップＳ９で‘Ｎｏ’）には、前のステップＳ３へ戻って上記動作を繰り返し行う。
【００６８】
その結果、ステップＳ９において、最終的に、‘Ｙｅｓ’となった場合には、全ての出発地のパッドと、その到着地となるパッケージピンと、両者の間の接続経路が自動的に決定される。
【００６９】
上記１〜１０の条件に従って、半導体チップのパッドと、パッケージのピンとの間の接続経路を決定し、各々のパッドに対応するパッケージピンを割り付けることができる。すなわち、プリント基板や差動配線等に由来する制約条件を考慮したピンの割り付けを行うことができ、単層基板であっても交差しない配線を少ない計算量で得ることができる。また、多層配線を避けることができるため、生産コストを安く抑えることができる。
【００７０】
なお、上記実施形態では、各辺において、その中央部から両端部へ向かって同時に２つの飛行体、全辺で同時に８つの飛行体を出発させている。本発明は、これに限定されず、例えば各辺において１つの飛行体、全辺で４つの飛行体を出発させても良いし、あるいは、各辺において同時に３つ以上の飛行体を出発させても良いし、あるいは、全辺で全てのパッドから同時に飛行体を出発させても良い。
【００７１】
また、上記実施形態では、電源、グランドについてパッケージピンの割り付けが終了しているものとして説明した。また、優先信号や差動信号などの特殊な扱いを必要とする信号が含まれる場合を例に挙げて説明した。しかし、本発明は、これに限定されず、電源、グランドについても、Ｂｏｉｄモデルを適用してパッケージピンの割り当てを行っても良い。また、特殊な扱いが必要な信号がない場合、そのための工程を省くことができる。
【００７２】
また、各々の飛行体の飛行速度は、例えばシミュレーションの処理速度に相当するものである。従って、その速度は必要に応じて適宜決定されるべきものである。同様に、飛行体同士の距離が近づきすぎかどうかの判断基準は、例えばパッドピッチやパッケージピンピッチなどに応じて適宜決定されるべきものである。従って、飛行体同士の距離が近づきすぎかどうかの判断基準は、半導体チップとパッケージに応じて決定すれば良い。
【００７３】
本発明は、基本的に以上のようなものである。
以上、本発明のパッケージピンの割り付け方法について詳細に説明したが、本発明は上記実施形態に限定されず、本発明の主旨を逸脱しない範囲において、種々の改良や変更をしてもよいのはもちろんである。
【図面の簡単な説明】
【００７４】
【図１】Ｂｏｉｄモデルの第１の条件を表す概念図である。
【図２】Ｂｏｉｄモデルの第２の条件を表す概念図である。
【図３】Ｂｏｉｄモデルの第３の条件を表す概念図である。
【図４】２羽の鳥が近づきすぎた場合の動作を説明する概念図である。
【図５】本発明において、飛行体が飛行した時の動作を表す概念図である。
【図６】本発明において、飛行体が飛行した後に与えられるベクトルを表す概念図である。
【図７】本発明において、差動信号の制約条件を表す概念図である。
【図８】本発明において、優先信号の制約条件を表す概念図である。
【図９】本発明において、飛行経路が交差した状態を表す概念図である。
【図１０】本発明において、飛行体が出発する順序を表す概念図である。
【図１１】本発明のパッケージピンの割り当て方法の各工程を表すフローチャートである。
【図１２】本発明において、優先信号の接続経路を決定するための制約条件を表す概念図である。
【図１３】本発明において、半導体チップの各辺を２分して８つのグループに分割した状態を表す概念図である。
【図１４】本発明において、到着地のパッケージピンを選択する時の制約条件を表す概念図である。
【図１５】本発明において、対象とする飛行体が、隣りあう２つの辺の延長線に囲まれた領域に侵入した場合の状態を表す概念図である。
【符号の説明】
【００７５】
１０、１２  二等辺三角形
１４、１６  鳥
１８  ベクトル
２０  パッド
２２、３０、３１、３２、３４  パッケージピン
２４  半導体チップ
２６  グループ
２８  飛行体
【図１】
2008040801.tif 000003
【図２】
2008040801.tif 000004
【図３】
2008040801.tif 000005
【図４】
2008040801.tif 000006
【図５】
2008040801.tif 000007
【図６】
2008040801.tif 000008
【図７】
2008040801.tif 000009
【図８】
2008040801.tif 000010
【図９】
2008040801.tif 000011
【図１０】
2008040801.tif 000012
【図１１】
2008040801.tif 000013
【図１２】
2008040801.tif 000014
【図１３】
2008040801.tif 000015
【図１４】
2008040801.tif 000016
【図１５】
2008040801.tif 000017