(57)【要約】数学的トポロジーソリューションを利用して集積回路（ＩＣ）パッケージ相互接続ルーティングを決定する自動化方法およびシステムが開示される。グローバルトポロジーソリューションが決定され、単数の理想的なＩＣパッケージルーティングソリューションを提供する。トポロジーグローバルルーティングは、複数の最適化を詳細なルーティングの前に実行させる、問題の数学的抽象化を提供する。電気的ルーティングセグメント幅および必要とされるクリアランスの予備的な無視は、グローバルトポロジーソリューションを迅速に決定させる。グローバルトポロジーソリューションは、必要な設計パラメータと関連して利用されて、最適な幾何学的ルーティングソリューションを決定する。ガイドポイントが幾何学的ルーティングソリューションを用いて決定される。
2004531833.tif 000002
【特許請求の範囲】
【請求項１】
相互接続ルーティングソリューションを決定する方法であって、
グローバルトポロジーソリューションを決定する工程であって、該グローバルトポロジーソリューションを決定する工程は、
マトリクスグラフおよびリンググラフを生成する工程と、
該マトリクスグラフおよびリンググラフを初期化する工程と、
予めルーティングされた電子ルーティングセグメントを該マトリクスグラフにおける対応するノードにグラフ化し、該対応するノードを該リンググラフにおける近傍のノードにリンクさせる工程と、
ルーティングされていない電子ルーティングセグメントを、該マトリクスグラフにおいて最内周から最外周に位置する対応するノードに連続的にグラフ化し、生成された該対応するノードを、該リンググラフにおける各リングについて、近傍のノードにリンクさせる工程と、
電子ルーティングセグメントの対応するノードへのグラフ化のたびに、該リンググラフの各リング内のノードを平衡させる工程とを包含する、グローバルトポロジーソリューションを決定する工程と、
該グローバルトポロジーソリューションに基づいて幾何学的ルーティングソリューションを決定する工程であって、該グローバルトポロジーソリューションに基づいて幾何学的ルーティングソリューションを決定する工程は、
オーバーロード状態が存在するか否かを決定する工程と、
ピン交換および未使用のボールパッドジャンピングなどの技術を用いて、オーバーロード状態を補正する工程と、
各ノードの位置をガイドポイントとして記録する工程とを包含する、グローバルトポロジーソリューションに基づいて幾何学的ルーティングソリューションを決定する工程と、
該幾何学的ソリューションに従って、電子ルーティングセグメントをプロットする工程と
を包含する、方法。
【請求項２】
相互接続ルーティングソリューションを決定するシステムであって、
グローバルトポロジーソリューションを決定する手段であって、該グローバルトポロジーソリューションを決定する手段は、
マトリクスグラフおよびリンググラフを生成する手段と、
該マトリクスグラフおよびリンググラフを初期化する手段と、
予めルーティングされた電子ルーティングセグメントを該マトリクスグラフにおける対応するノードにグラフ化し、該対応するノードを該リンググラフにおける近傍のノードにリンクさせる手段と、
ルーティングされていない電子ルーティングセグメントを、該マトリクスグラフにおいて最内周から最外周に位置する対応するノードに連続的にグラフ化し、生成された該対応するノードを、該リンググラフにおける各リングについて、近傍のノードにリンクさせる手段と、
電子ルーティングセグメントの対応するノードへのグラフ化のたびに、該リンググラフの各リング内のノードを平衡させる手段とを含む、グローバルトポロジーソリューションを決定する手段と、
該グローバルトポロジーソリューションに基づいて幾何学的ルーティングソリューションを決定する手段であって、該グローバルトポロジーソリューションに基づいて幾何学的ルーティングソリューションを決定する手段は、
オーバーロード状態が存在するか否かを決定する手段と、
ピン交換および未使用のボールパッドジャンピングなどの技術を用いて、オーバーロード状態を補正する手段と、
各ノードの位置をガイドポイントとして記録する手段を含む、グローバルトポロジーソリューションに基づいて幾何学的ルーティングソリューションを決定する手段と、
該幾何学的ソリューションに従って、電子ルーティングセグメントをプロットする手段と
を含む、システム。
【請求項３】
１つ以上のプロセッサに工程のシーケンスを行わせるプログラムされた命令のセットが実行されるコンピュータ使用可能媒体であって、該工程は、
グローバルトポロジーソリューションを決定する工程であって、該グローバルトポロジーソリューションを決定する工程は、
マトリクスグラフおよびリンググラフを生成する工程と、
該マトリクスグラフおよびリンググラフを初期化する工程と、
予めルーティングされた電子ルーティングセグメントを該マトリクスグラフにおける対応するノードにグラフ化し、該対応するノードを該リンググラフにおける近傍のノードにリンクさせる工程と、
ルーティングされていない電子ルーティングセグメントを、該マトリクスグラフにおいて最内周から最外周に位置する対応するノードに連続的にグラフ化し、生成された該対応するノードを、該リンググラフにおける各リングについて、近傍のノードにリンクさせる工程と、
電子ルーティングセグメントの対応するノードへのグラフ化のたびに、該リンググラフの各リング内のノードを平衡させる工程とを包含する、グローバルトポロジーソリューションを決定する工程と、
該グローバルトポロジーソリューションに基づいて幾何学的ルーティングソリューションを決定する工程であって、該グローバルトポロジーソリューションに基づいて幾何学的ルーティングソリューションを決定する工程は、
オーバーロード状態が存在するか否かを決定する工程と、
ピン交換および未使用のボールパッドジャンピングなどの技術を用いて、オーバーロード状態を補正する工程と、
各ノードの位置をガイドポイントとして記録する工程とを包含する、グローバルトポロジーソリューションに基づいて幾何学的ルーティングソリューションを決定する工程と、
該幾何学的ソリューションに従って、電子ルーティングセグメントをプロットする工程と
を包含する、コンピュータ使用可能媒体。
【請求項４】
相互接続ルーティングソリューションを決定する方法であって、
グローバルトポロジーソリューションを決定する工程と
該グローバルトポロジーソリューションに基づいて幾何学的ルーティングソリューションを決定する工程と、
該幾何学的ソリューションに従って、電子ルーティングセグメントをプロットする工程と
を包含する、方法。
【請求項５】
前記グローバルトポロジーソリューションを決定する工程は、マトリクスグラフおよびリンググラフを生成する工程をさらに包含する、請求項４に記載の方法。
【請求項６】
前記グローバルトポロジーソリューションを決定する工程は、前記マトリクスグラフおよびリンググラフを初期化する工程をさらに包含する、請求項５に記載の方法。
【請求項７】
前記グローバルトポロジーソリューションを決定する工程は、予めルーティングされた電子ルーティングセグメントを該マトリクスグラフにおける対応するノードにグラフ化し、該対応するノードを該リンググラフにおける近傍のノードにリンクさせる工程をさらに包含する、請求項６に記載の方法。
【請求項８】
前記グローバルトポロジーソリューションを決定する工程は、ルーティングされていない電子ルーティングセグメントを前記マトリクスグラフにおける第１のリングに位置する対応するノードにグラフ化し、該対応するノードを該リンググラフにおける近傍のノードにリンクさせる工程さらに包含する、請求項７に記載の方法。
【請求項９】
前記グローバルトポロジーソリューションを決定する工程は、ルーティングされていない電子ルーティングセグメントを、前記マトリクスグラフにおける次のリングに位置する対応するノードに連続的にグラフ化し、該対応するノードを、該リンググラフにおける近傍のノードにリンクさせる工程をさらに包含する、請求項８に記載の方法。
【請求項１０】
前記グローバルトポロジーソリューションを決定する工程は、電子ルーティングセグメントの対応するノードへのグラフ化のたびに、該リンググラフの各リング内のノードを平衡させる工程をさらに包含する、請求項９に記載の方法。
【請求項１１】
前記グローバルトポロジーソリューションに基づいて幾何学的ルーティングソリューションを決定する工程は、オーバーロード状態が存在するか否かを決定する工程をさらに包含する、請求項１０に記載の方法。
【請求項１２】
前記トポロジーソリューションを決定する工程は、前記幾何学的ソリューションを決定する工程の前に、ピン交換および未使用のボールパッドジャンピングなどの技術を用いて、オーバーロード状態を補正する工程をさらに包含する、請求項１０に記載の方法。
【請求項１３】
前記グローバルトポロジーソリューションを決定する工程は、前記幾何学的ソリューションを決定する工程の前に、オーバーロード状態についてユーザに警告する工程をさらに包含する、請求項１０に記載の方法。
【請求項１４】
前記オーバーロード状態を補正する工程は、前記幾何学的ソリューションを決定する工程の前に、電子ルーティングトラックを該グローバルトポロジーソリューションから取り除く工程をさらに包含する、請求項１３に記載の方法。
【請求項１５】
前記グローバルトポロジーソリューションに基づいて幾何学的ルーティングソリューションを決定する工程は、各ノードの位置をガイドポイントとして記録する工程をさらに包含する、請求項１２に記載の方法。
【請求項１６】
相互接続ルーティングソリューションを決定するシステムであって、
グローバルトポロジーソリューションを決定する手段と、
該グローバルトポロジーソリューションに基づいて幾何学的ルーティングソリューションを決定する手段と、
該幾何学的ソリューションに従って、電子ルーティングセグメントをプロットする手段と
を含む、システム。
【請求項１７】
１つ以上のプロセッサに工程のシーケンスを行わせるプログラムされた命令のセットが実行されるコンピュータ使用可能媒体であって、該工程は、
グローバルトポロジーソリューションを決定する工程と、
該グローバルトポロジーソリューションに基づいて幾何学的ルーティングソリューションを決定する工程と、
該幾何学的ソリューションに従って、電子ルーティングセグメントをプロットする工程と
を包含する、コンピュータ使用可能媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、集積回路（ＩＣ）パッケージ相互接続ルーティングを決定するシステムおよび方法に関する。
【背景技術】
【０００２】
設計者の新しいＩＣの性能を改善しようとする努力に伴い、回路の大きさの最小化は、根底の目的であり続けている。ＩＣ設計における近年の開発は、ＩＣの電力、速度および性能を劇的に増大させた。ＩＣ電力、速度および性能が増大するにつれて、各ＩＣが相互接続される入力出力端子の数もまた、増大した。
【０００３】
通常、集積回路（ＩＣ）は、プリント回路基板（ＰＣＢ）上に導入され得る前に、「パッケージ」内に配置される。ＩＣパッケージ相互接続は、ＩＣダイ上の端子とパッケージ上のパッドとの間の電気的トラックを設計するプロセスである。電気的設計自動化（ＥＤＡ）ツールを利用して、人間の設計者は、ＩＣダイからネットデータを、そして、ＰＣＢパッケージからフットプリントデータを取得する。そして、設計者は、このデータを利用して、ＩＣダイを基板に接続するために、パッケージ内に電気的トラックを設計する。一旦、これらの接続が行われると、パッケージピンと接続される。
【０００４】
ほんの数年前は、ほとんどのパッケージは、数ダースまたは多くとも数百のパッドを有するのみであった。これらのパッドと接続するために必要となるルーティングは、特別に困難でもなく、時間を消費もしない。現在のボールグリッドアレイ（ＢＧＡ）パッケージは、通常、数百または数千のパッドを有する。一万を超えるパッドを有するものもある。以前は数時間を有したタスクは、今や、数日または数週間かかり得る。従って、自動化ソリューションが必要とされる。
【０００５】
１つのアプローチは、設計者がＩＣパッケージにおける各相互接続ワイヤを手動で決定する必要がある設計ツールを利用することである。ＩＣパッケージの複雑性が増大するにつれて、そのようなソリューションは、明らかに欠点を有する。別のアプローチは、「Ｒａｄｉａｌ  Ｒｏｕｔｅｒ」（Ｒ）の名の下に売買されるパッケージ化規定自動ルータを含む、Ｚｕｋｅｎ（Ｒ）による「Ａｄｖａｎｃｅｄ  ＩＣ  Ｐａｃｋａｇｉｎｇ（Ｒ）」等の設計ツールを利用することである。これらのルータは、パッケージ化規定アルゴリズムによる全角自動ルーティングを利用する。これらのルータは、従来の水平／垂直ルーティングではなく、ＢＧＡおよびＣＳＰに固有の問題を解決するダイレクトラインオブサイトアプローチを利用する。Ｉｎｎｏｖｅｄａ（Ｒ）は、「ＰｏｗｅｒＢＧＡ」（Ｒ）の名の下に売買されるパッケージ設計法を有する。これらのツールは、「ＢＧＡルートウィザード」を呼ばれる選択的ルータを有する。これらの製品は、Ｚｕｋｅｎ  Ｒａｄｉａｌ  Ｒｏｕｔｅｒと同様の設計であると思われる。これらの他のアプローチは単純な設計に適しているが、複雑なＩＣ用のルーティング法を提供するのは困難である。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
従って、極めて複雑なＩＣパッケージ用の最適なルーティング法を提供する自動化システムおよび方法の提供が、非常に望ましい。
【課題を解決するための手段】
【０００７】
（発明の要旨）
自動化ＩＣパッケージルーティングシステムおよび方法は存在するが、複雑なＩＣ設計にルーティングを提供する自動化システムまたは方法は存在しない。特に、大規模多層ボールグリッドアレイ（ＢＧＡ）設計を利用して、ＩＣパッケージ用のルーティング法を提供する自動化システムまたは方法は存在しない。従って、複雑なＩＣ設計用の自動化ＩＣパッケージルーティングのシステムおよび方法の提供が望まれる。本発明の１つの実施形態では、トポロジーグローバルルーティングを利用して、最適なＩＣパッケージルーティング法を決定する。本発明の実施形態では、大規模ボールグリッドアレイ（ＢＧＡ）設計用のＩＣパッケージ相互接続のための最適なソリューションを自動的に決定するシステムおよび方法を提供する。
【０００８】
トポロジーグローバルルーティングは、多重の最適化を詳細なルーティングの前に実行し得る、問題の数学的抽象化を提供する。ＩＰパッケージ相互接続の特別な場合では、アルゴリズムは、他の方法で近似的なソリューションを発見し得るよりも短い時間で、最適なソリューションを発見し得る。
【発明を実施するための最良の形態】
【０００９】
（好ましい実施形態の説明）
添付の図面を必要に応じて参照して、好ましい実施形態がここで説明される。
【００１０】
図１は、ルーティングされる前のＩＣパッケージ１０１の例を示す。ＩＣ回路は、ＩＣ回路ボールパッド１０３と共にパッケージの中心に配置され、ＩＣパッケージボールパッド１３０、１４０、１５０、１６０（全体で１０４）に囲まれる。図１に示されるＩＣパッケージ１０１の例は、外側の端の周りにＩＣパッケージボールパッド１０４の４つのリングを有し、中心にＩＣ回路ボールパッド１０３の６×６マトリクスを有する。３つの固体リング１０５は、「電力リング」と呼ばれる。ＩＣの複数の端子は、電力リング１０５に接続され得るが、そのような接続を作るためにトポロジーソリューションの決定を必要としない。図１はまた、結合パッド１０６と呼ばれる、小型矩形パッドで構成される４つの円弧を示す。ＩＣ回路は、ＩＣ回路ボールパッド１０３の各々にルーティングされるＩ／Ｏ端子を有する。これらのＩＣ回路ボールパッド１０３は、ＩＣ用の端子として作用し、様々な結合パッド１０６および電力リング１０５に電気的に接続される。いくつかのボールパッド１０３は、同一の結合パッド１０６と電気的に接続され得、いくつかのボールパッド１０３は、複数の結合パッド１０６に接続され得る。
【００１１】
結合パッド１０６間の電気的トラックをＩＣパッケージボールパッド１０４にルーティングする際に、１つのアプローチは、従来のユークリッド幾何を用いる。すなわち、任意の位置がデカルト座標の対として一意に特定され得る。電気的ルーティングトラック１２９は、結合パッド１０６間でＩＣパッケージボールパッド１０４にルーティングされる。トポロジーグローバルルーティングは、グローバルトポロジーソリューションが発見された後まで、デカルト座標の計算を遅延させる。ルーティングの他のアプローチでは、結合パッド１０６から対応するボールパッド１０４までの可能なルーティングソリューションの複数の可能な幾何学的ソリューションを決定するステップを含む。これらの他のソリューションは、複数の幾何学的ソリューションのうちの最適なソリューションを決定する。逆に、グリーバルトポロジーソリューションを決定することによって、本発明の実施形態は、第１に唯一の可能なトポロジーソリューションを決定し、次に、トポロジーソリューションを最適な幾何学的ソリューションに変換する。
【００１２】
図２は、ボールパッド１０３のＩＣ回路６×６マトリクスの外側の端を囲むＩＣパッケージボールパッド１０４の拡大図である。本発明の実施形態は、結合パッド１０６から対応するＩＣパッケージボールパッド１０４へ電気的トラック１２９をルーティングするために、最適なソリューションを決定する努力を行う。本発明の実施形態は、第１に、設計を「境界」１１５により分離される「領域」１１０へ分割する。「境界」１１５は、他のボールパッド１０４と接続される、ボールパッド１０４、または、他の電気的トラック１２９を参照し得る。領域１１０は、ＩＣパッケージボールパッド１０４間のチャンネルを参照する。各接続に対して、本発明の実施形態により利用されるグローバルルータは、ＩＣボールパッドグリッドアレイ１０４を介して、各結合パッド電気的トラック１２９に対して取られる様々な経路を構成するソリューションのセットを決定する。
【００１３】
本発明の好ましい実施形態は、ボールパッドフィールドを介して、トポロジー経路１２９（図４）を決定する。他のルーティングアプローチにより利用される幾何学的経路と対照的に、トポロジー経路１２９は、ゼロ幅およびゼロクリアランス（clearance)トラックを有すると考慮され得る。トポロジー状態が、幾何学的状態よりもずっと少ない情報を含むので、グリーバルルータは、幾何学的ルータが可能なよりもずっと高速で経路を選択し得る。
【００１４】
図６は、グローバルトポロジールーティングソリューションの生成に関連するステップのフローチャートである。ステップ６０１において、マトリクスグラフ３００が生成される。図３は、ＩＣパッケージ１０１の生成されるマトリクスグラフ３００の例の一部分を示す。図３において、マトリクスグラフは、各ボールパッド１０４をノードで示す。各ノードは、北、東、南および西に各ボールパッドを接続する４つのリンク１２０を有する。このマトリクスグラフ３００は、様々なボールパッド１０４からその隣のノードへの電気的トラック１２９のルーティングを案内するために利用される。ステップ６０２は、リンググラフの生成を含む。この例では、リンググラフは、マトリクスグラフ３００と正確に対応するリンググラフである、各ルーティング層上の各ボールパッドリング１３０、１４０、１５０、１６０に対して、好ましい実施形態はリンググラフを生成する。図３において、リンググラフは、各ボールパッドリング１３０、１４０、１５０、１６０に対して生成される。リンググラフ３３０、３４０、３５０、３６０は、図３に示される。図３に示されるリンググラフは、ボールパッド１０４か、または、ノード１３７、１４７、１５７、１６７（全体では、１０７）のようなそれらのバイアと共にロードされる。各ノード１０７は、電気的トラック１２９がリンググラフ３３０、３４０、３５０、３６０を横断する、マトリクスグラフ３００の点を表わす。これらのノード１０７はまた、ボールパッド１０４と一致する。各ノード１０７は、右回りまたは左回りの隣と接続する２つのリンク１２０を有する。また、マトリクスグラフ内の対応するノードとのリンク１２０を有する。最終的に、リンググラフ内の各ノード１０７は、最初は空である「イン」および「アウト」と呼ばれる２つのリンク１２０を有する。各ノード１０７に対する「イン」および「アウト」は、システムのメモリに格納され、電気的トラック１２９のルーティングがリンググラフ（３３０、３４０、３５０、３６０）に入りかつそこから出る位置を示す。
【００１５】
ステップ６０３は、マトリクスグラフ３００およびリンググラフ４００の両方を初期化させる。一旦、グラフがボールパッド１０４により初期化されると、本発明の実施形態は、グローバルトポロジーソリューションを決定するために準備される。ステップ６０４において、本発明の第１の実施形態は、任意の予めルーティングされた接続を加える。これらの予めルーティングされた接続は、ＩＣパッケージ１０１の設計に応じて変化し得ない特定の位置に配置される。ステップ６０５では、システムは、リング（１３０、１４０、１５０、１６０）を横断する位置と対応するリンググラフ（３３０、３４０、３５０、３６０）のノード１３７ａを生成する。ステップ６０６において、システムは、新規ノード１３７ａをその右回りおよび左回りの隣とリンクさせる。例えば、図４において、予めルーティングされる接続電気的トラック１２９が、ボールパッド１０４に作られる。図４に示されるように、ノード１３７ａは、リンググラフ３３０において生成され、右回り１３７ｓおよび左回り１３７ｎ隣とリンクされる。ステップ６０７において、システムは、「イン」および「アウト」リンクを近傍のリンググラフにセットする。与えられる例では、「イン」は、リンググラフ３３０の入口にリンクされ、「アウト」は、近傍のリンググラフ３４０にリンクされる。
【００１６】
次に、ステップ６０８においてルーティングされていない接続がグラフにされる。まず、第１のリング１３０内でボールパッド１０４との接続を必要とする結合パッド１０６が接続される。次に、他の結合パッド１０６の全てが、第１のリング１３０に接続される。一旦、結合パッドの全てが、第１のリング１３０に接続されると、例えば、システムは、本ソリューションを最適化するようにノード１３７を平行させる。ノードを平衡させるために、システムは、ノード１３７ｎ、１３７ａ、１３７ｓの対の間のローディングを計算する。ノード１３７ｎ、１３７ａ、１３７ｓの対の間のローディングは、ノード間の全体の距離から、全ての境界の幅の総和をマイナスし、境界の間に要求されるクリアランスの総和をマイナスしたものである。システムは、可能であるときはいつでも接続を移動させることによって、ノードの対の間のローディングを改善する。
【００１７】
適切なノードは、近傍のノード１３７にリンクされ、各ノード１３７の「イン」および「アウト」がセットされる。
【００１８】
各残りのリング１４０、１５０、１６０に対して、このプロセスが繰り返される。次のリング１４０などに対して接続がプロットされ、最内週のリング（１４０）から最外側のリング（１６０）へ作用する。この態様では、最も効果的なルーティングプロットは、リング１３０、１４０、１５０、１６０に位置する結合パッド１０６とボールパッド１０４との間の各接続に対して決定される。トポロジーソリューションのグラフ化の間、電気的トラック１２９は、ノード１０７（すなわち、１３７、１４７、１５７、１６７）を平衡させる時を除き、幅を有さないし、任意のクリアランスを必要とするとも考えられないと判断される。この態様では、システムは、最適なルーティングソリューションを決定することに集中する。さらに、トポロジーソリューションは、幾何学的状態よりも少ない情報を含むので、本発明と一貫したグローバルルータは、幾何学的ルータよりもずっと高速で経路を選択し得る。いくつかの電気的トラック１２９のルーティングは、ボールパッド１０４の間の制限された空間に関わらず、ボールパッド１０４ノードを介してプロットされ得る。本システムは、各次のリングへのさらなる接続が必要とされない限り、電気的トラック１２９のグラフ化を続ける。システムは、次に、ステップ６０９に進む。ステップ６０９において、システムは、さらなるアルゴリズムを用いて、さらにノード１０７（すなわち、１３７、１４７、１５７、１６７）を平衡させ、ルーティング設計を最適化する。
【００１９】
図４は、最初のグローバルトポロジールーティング法の一部分を示す。図４に示されるように、電気的トラック１２９は、リング１３０、１４０、１５０、１６０内の各ボールパッド１０４にプロットされる。ノード１０７（すなわち、１３７、１４７、１５７、１６７）は、最初のソリューションで生成される。尚、このとき、本ソリューションは、同一の領域１１０を介してプロットされるいくつかの電気的トラック１２９を含み得るか、または、ボールパッド１０４を横断するが電気的に接続されない。本方法論ではこの点で、システムおよび方法は、これらの重なりに関連しない。本システムおよび方法は、各リンググラフ３３０、３４０、３５０、３６０を横断するような各ノード１０７（すなわち、１３７、１４７、１５７、１６７）、および、他のノード１０７（すなわち、１３７、１４７、１５７、１６７）へのリンクに関連する。
【００２０】
ここで、本発明の実施形態は、ルーティング幅および必要とされるクリアランス距離を考慮する。ここで、グローバルトポロジーソリューションが決定されたので、システムは、幾何学的ソリューションの生成を試みる。ステップ６０９において、本発明の実施形態は、ノード１０７（すなわち、１３７、１４７、１５７、１６７）間の距離と、ノード１０７（すなわち、１３７、１４７、１５７、１６７）間に実際に必要とされるクリアランスを計算する。各ノード１０７（すなわち、１３７、１４７、１５７、１６７）は、ボールパッド１０４またはバイアのどちらかであり得る。全体として、ノード１０７（すなわち、１３７、１４７、１５７、１６７）、ボールパッド（１０４）、および実際の電気的トラック１２９は、境界１１５として示される。ステップ６１０において、オーバーロード条件の存在が決定される。オーバーロード条件は、ノード（すなわち、１３７ｎ、１３７ａ、１３７ｓ）の対のローディングが負である場合に存在する。境界１１５の総和が領域の次元を超過する場合に、別の方法を置き、オーバーロード条件が存在する。
【００２１】
境界１１５間の任意のチャンネル（領域１１０として示される）が、オーバーロードされると判断される場合、本システムおよび方法は、ピン交換、任意の未使用のボールパッド１０４を超えたジャンピング、ならびに、本システムおよび方法に利用可能な他の方法を利用して、ステップ６１１においてオーバーロード条件の補正を試みる。
【００２２】
本発明の実施形態が、適切な幾何学的ソリューションを発見し得ない場合、ステップ６１２において詳細な警告メッセージをユーザのためのログファイルに書き出す。システムは、ステップ６１３に進み、ルーティング可能でないとして電気的トラック１２９をマークし、グラフからそれを除去する。
【００２３】
一旦、各ノード１０７（すなわち、１３７、１４７、１５７、１６７）間の電気的トラック１２９のための全ての必要とされるエッチングトラックと十分に適合する（少なくとも理論的には）利用可能な空間が存在すると、システムは、ステップ６１３において、位置を各ノード１０７（すなわち、１３７、１４７、１５７、１６７）に割り当てる。図５は、グローバルトポロジーソリューションから導き出される最適化幾何学的ソリューションを示す。図５に示されるように、電気的トラック１２９は再ルーティングされて、ボールパッド１０４の間の経路を案内するように、各電気的トラック１２９の実際の経路をより正確に示す。
【００２４】
最終的に、ステップ６１４において、各ノード１０７（すなわち、１３７、１４７、１５７、１６７）の割り当てられた位置は、「ガイドポイント」としてデータベースに記録される。詳細なルータが、後で、ルーティング時にコーナーとしてこれらの「ガイドポイント」を利用する。
【００２５】
図７は、本発明の様々な実施形態による相互接続ルーティングソリューションを決定するステップを実行することができるシステムを示す。本発明の実施形態では、本発明を実施するために必要となる命令のシーケンスの実行が、単一のコンピュータ７００により実行される。本発明の他の実施形態によると、通信リンク７１５に接続される２つ以上のコンピュータシステム７００は、別のものとの組み合わせで、本発明を実施するために必要とされる命令のシーケンスを実行し得る。本発明を不必要に不明瞭にすることを避けるために、１つのコンピュータシステム７００のみの説明が、以下に示される。しかし、任意の数のコンピュータシステム７００が本発明を実施するために利用され得ることが理解されるべきである。
【００２６】
本発明の実施形態に従ったコンピュータシステム７００は、ここで、図７を参照して説明される。図７は本発明の実施形態に従ったコンピュータシステム７００の機能的コンポーネントのブロック図である。本明細書中で利用されるように、用語コンピュータシステム７００は、１つ以上のプログラムを格納し、かつ、独立して実行し得る任意のコンピュータ（例えば、パーソナルコンピュータ、サーバコンピュータ、ポータブルラップトップコンピュータ、またはパーソナルデータアシスタント（「ＰＤＡ」））を説明するように広く利用される。
【００２７】
各コンピュータシステム７００は、バス７０６に接続される通信インターフェイス７１４を含み得る。通信インターフェイス７１４は、コンピュータシステム７００間に２通りの通信を提供する。各コンピュータシステム７００の通信インターフェイス７１４は、命令、メッセージおよびデータを含む様々なタイプの情報を表わすデータストリームを含む電気的、電磁気的、または光学信号を送信および受信する。通信リンク７１５は、１つのコンピュータシステム７００を別のコンピュータシステム７００とリンクさせる。通信リンク７１５は、ＬＡＮであり得、この場合、通信インターフェイス７１４は、ＬＡＮカードであり得る。もしくは、通信リンク７１５は、ＰＳＴＮであり得、この場合、通信インターフェイス７１４は、統合サービスデジタルネットワーク（ＩＳＤＮ）カードまたはモデムであり得る。またさらに、通信リンク７１５は、無線ネットワークであってもよい。
【００２８】
コンピュータシステム７００は、各通信リンク７１５および通信インターフェイス７１４を介して、プログラム（すなわち、アプリケーション）コードを含むメッセージ、データおよび命令を送信および受信し得る。受信したプログラムコードは、受信される各プロセッサ（単数または複数）７０７により実行され得、および／または、後での実行のために格納デバイス７１０もしくは他の関連する不揮発性媒体に格納され得る。この態様では、コンピュータシステム７００は、搬送波の形式で、メッセージ、データおよび／またはプログラムコードを受信し得る。
【００２９】
ある実施形態において、コンピュータシステム７００は、データ記憶システム７３１と連動して動作する。ここで、データ記憶システム７３１は、コンピュータシステム７００により容易にアクセスされるデータベース７３２を含む。別の実施形態では、データベース７３２は、別のコンピュータシステム７００上（例えば、メモリチップおよび／またはハードディスク）に格納され得る。さらに別の実施形態では、データベース７３２は、１つ以上のフロッピー（Ｒ）ディスク、ＣＤ−ＲＯＭ、または、コンピュータが読み出し得る任意の他の媒体からコンピュータシステム７００により読み出され得る。別の実施形態では、コンピュータシステム７００は、既に議論されたように様々な媒体に格納される、２つ以上のデータベース７３２とアクセスし得る。
【００３０】
コンピュータシステム７００は、バス７０６または命令、メッセージおよびデータ、全体的には情報と通信する他の通信メカニズム、ならびに、情報を処理するためにバス７０６と接続される１つ以上のプロセッサ７０７を備える。コンピュータシステム７００はまた、ランダムアクセスメモリ（ＲＡＭ）または他のダイナミック記憶デバイス等のメインメモリ７０８を備え、メインメモリは、プロセッサ（単数または複数）７０７により実行されるダイナミックデータおよび命令を格納するためにバス７０６に接続される。メインメモリ７０８はまた、一時的データ、すなわち、プロセッサ（単数または複数）７０７による命令の実行の間の変数または他の中間情報を格納するために利用され得る。
【００３１】
コンピュータシステム７００は、リードオンリーメモリ（ＲＯＭ）７０９、あるいは、プロセッサ（単数または複数）７０７のスタティックデータおよび命令を格納するために、バス７０６と接続される他のスタティック記憶デバイスをさらに含み得る。磁気ディスクまたは光ディスク等の記憶デバイス７１０はまた、プロセッサ（単数または複数）７０７のデータおよび命令を格納するために提供され得、かつ、バス７０６と接続され得る。
【００３２】
コンピュータシステム７００は、ユーザに情報を表示するために、カソードレイチューブ（ＣＲＴ）（これに制限されない）等の表示デバイス７１１に、バス７０６を介して接続され得る。英数字および他のキーを含む入力デバイス７１２は、プロセッサ（単数または複数）７０７と情報およびコマンド選択を通信するためにバス７０６に接続される。別のタイプのユーザ入力デバイスは、プロセッサ（単数または複数）７０７と方向情報およびコマンド選択を通信し、かつ、ディスプレイ７１１上のカーソルの動きを制御するために、マウス、トラックボール、フィンガーパッド、または、カーソル方向キー等の（これらに制限されない）カーソル制御７１３を含み得る。
【００３３】
本発明の実施形態によると、各コンピュータシステム７００は、メインメモリ７０８に含まれる１つ以上の命令の１つ以上のシーケンスを実行する各プロセッサ（単数または複数）７０７による特定の動作を実行する。そのような命令は、ＲＯＭ７０９または記憶デバイス７１０などの別のコンピュータ利用可能媒体から、メインメモリ７０８へ読み出され得る。メインメモリ７０８に含まれる命令のシーケンスの実行は、プロセッサ（単数または複数）７０７に本明細書中に記載されるプロセスを実行させる。別の実施形態では、有線（ｈａｒｄ−ｗｉｒｅｄ）回路が本発明を実装するソフトウェア命令の代わり、または、組み合わせで利用され得る。従って、本発明の実施形態は、ハードウェア回路および／またはソフトウェアの任意の特定の組み合わせに制限されない。
【００３４】
本明細書中で利用される用語「コンピュータ利用可能媒体」は、情報を提供し、プロセッサ（単数または複数）７０７により利用可能である任意の媒体を示す。そのような媒体は、不揮発性、揮発性および伝達媒体を含む（それらに制限されない）多くの形式を取り得る。不揮発性媒体、すなわち、電力がなくても情報を残し得る媒体は、ＲＯＭ７０９を含む。揮発性媒体、すなわち、電力がないと情報を残すことができない媒体は、メインメモリ７０８を含む。送信媒体は、バス７０６を含むワイヤを含む、同軸ケーブル、銅線および光ファイバを含む。送信媒体はまた、搬送波、すわなち、周波数、振幅または位相等が情報信号を送信するために変調され得る電磁波の形式を取り得る。さらに、送信媒体は、無線波および赤外線データ通信の間に発生する等の、音波または光波の形式を取り得る。
【００３５】
コンピュータ利用可能媒体の様々な形式は、実行のための１つ以上の命令の１つ以上のシーケンスをプロセッサ（単数または複数）７０７に提供する際に関係し得る。例えば、命令は、最初に外部のコンピュータシステム７００（示されない）の磁気ディスク上に提供され得る。外部のコンピュータシステム７００は、命令をダイナミックメモリにロードし、モデムを利用して、それらを電話線を介して送信する。ローカルコンピュータシステム７００に接続されるモデムは、電話線上で命令を受信し得、赤外線送信器を利用して、電話線を介して送信された命令信号を対応する赤外線信号に変換する。バス７０６に接続される赤外線検知器（示されない）は、赤外線信号を受信し得、その命令をバス７０６上に配置する。バス７０６は、メインメモリ７０８に命令を搬送し得、メインメモリ７０８から、その後プロセッサ（単数および複数）７０７は、命令を取り出し、かつ、実行する。メインメモリ７０８が受信する命令は、プロセッサ（単数または複数）７０７による実行の前後のどちらかに、選択的に格納デバイス７１０に格納され得る。
【００３６】
以上の説明において、本発明は、その特定の実施形態を参照して示された。しかし、様々な改変および変更が、本発明のより広範な意図および範囲を逸脱することなくなされ得ることは明らかである。例えば、本明細書中に示されたプロセフロー図に示されるプロセスアクションの特定の順序および組み合わせは、単なる例であり、本発明は、異なるまたはさらなるプロセスアクション、あるいは、プロセスアクションの異なる組み合わせまたは順序を用いて実行され得ることが、読者に理解される。従って、明細書または図面は、制限的な意味ではなく説明とみなされるべきである。
【００３７】
本発明の好ましい実施形態が本明細書中で説明されたが、本発明の概念および範囲内における多くの改変が可能である。そのような改変は、本明細書中に示される実施形態の説明を精読することで、当業者に明らかになる。
【図面の簡単な説明】
【００３８】
【図１】図１は、ルーティングされる前のＩＣパッケージの例を示す。
【図２】図２は、ＢＧＡ設計に利用されるボールグリッドアレイの境界および領域の拡大図を示す。
【図３】図３は、本発明の実施形態により生成されるマトリクスグラフを示す。ここで、各ボールパッドはノードであり、この特定の例では、リンググラフがマトリクスグラフに一致する。
【図４】図４は、本発明の実施形態により生成される最初のトポロジーソリューションを示す。
【図５】図５は、本発明の実施形態により生成される可能な最適なソリューションを示す。
【図６】図６は、集積回路（ＩＣ）パッケージ相互接続ルーティングを決定する方法を含むステップのフローチャートを示す。
【図７】図７は、相互接続ルーティング法を決定するシステムを示す。
【図６】
2004531833.tif 000003
【図７】
2004531833.tif 000004
【国際公開パンフレット】
2004531833.tif 000005
2004531833.tif 000006
2004531833.tif 000007
2004531833.tif 000008
2004531833.tif 000009
2004531833.tif 000010
2004531833.tif 000011
2004531833.tif 000012
2004531833.tif 000013
2004531833.tif 000014
2004531833.tif 000015
2004531833.tif 000016
2004531833.tif 000017
2004531833.tif 000018
2004531833.tif 000019
2004531833.tif 000020
2004531833.tif 000021
2004531833.tif 000022
2004531833.tif 000023
2004531833.tif 000024
2004531833.tif 000025
2004531833.tif 000026
【国際調査報告】
2004531833.tif 000027
2004531833.tif 000028