(57)【特許請求の範囲】
【請求項１】
回路レイアウトに関連する一群の局所ルーティング領域にわたるルーティング可能性推定を計算するための方法であって、
選択機構が、ルートオーバーフローに関連する第１の局所ルーティング領域を選択することであって、それぞれの局所ルーティング領域は、該回路レイアウトの領域内のルーティング層に対するいくつかのルートオーバーフローの推定に関連付けられ、該第１の局所ルーティング領域は、方向ｄにおけるｋ以上のルートのオーバーフローに関連するオーバーフロールーティング層を含み、それぞれのルーティング層は、好ましい方向Ｄに関連付けられ、Ｒ個のルートのオーバーフローまたはＣ個のルートの過剰容量のいずれかに関連付けられる、ことと、
識別機構が、第２の局所ルーティング領域を識別することであって、該第２の局所ルーティング領域は、該オーバーフロールーティング層における該オーバーフローに対応するための該方向ｄにおける過剰容量を有し、該第１の局所ルーティング領域の該オーバーフロールーティング層と該第２の局所ルーティング領域との間に過剰経路が存在し、該過剰経路は、該方向ｄに直交する、ことと、
転送機構が、該オーバーフロールーティング層から、該第２の局所ルーティング領域へ、オーバーフロー値ｋを転送することと、
計算機構が、グローバルオーバーフローコストおよび隣接するオーバーフローコストの関数として、グローバルルーティング可能性推定を計算することであって、該隣接するオーバーフローコストは、隣接するオーバーフロー局所ルーティング領域からなるクラスタのオーバーフローコストである、ことと
を含む、方法。
【請求項２】
前記方向ｄにおけるｋ以上のルートのオーバーフローに関連する前記第１の局所ルーティング領域のオーバーフロールーティング層から、第２の局所ルーティング領域へ、オーバーフロー値ｋを転送することは、
前記転送機構が、前記好ましい方向ｄにおける少なくともＣ＝ｋのルートの過剰容量に関連する受信ルーティング層を備える、第２の局所ルーティング領域について第１の検索を実施することと、
該第１の検索が成功しない場合、該転送機構が、好ましくない方向
【数１】
0005403834.tif 000036
における少なくともＣ＝ｎ＊ｋのルートの過剰容量に関連する受信ルーティング層を備える、第２の局所ルーティング領域について第２の検索を実施することであって、ｎは、ルーティング層の前記好ましくない方向におけるルートに対応するように使用される、いくつかのトラックを表す、好ましくない方向の因数である、ことと、
該第２の局所ルーティング領域が見出された場合、該転送機構が、前記オーバーフロー値Ｃを該第２の局所ルーティング領域の受信層に転送することと
を含み、該好ましくない方向
【数２】
0005403834.tif 000037
は、前記好ましい方向ｄに直交する、請求項１に記載の方法。
【請求項３】
前記第２の局所ルーティング領域を検索することは、前記好ましいルーティング方向を使用する層上のｋ以上のルートの過剰容量に関連する、いくつかの隣接する局所ルーティング領域を通って、前記第１の局所ルーティング領域から前記第２の局所ルーティング領域まで経路が存在することを確認することを含む、請求項２に記載の方法。
【請求項４】
前記オーバーフロー値Ｃを、前記第２の局所ルーティング領域の前記受信層に転送することは、
前記転送機構が、前記第１の局所ルーティング領域の前記オーバーフロールーティング層からｋオーバーフロー値を減算することと、
該転送機構が、前記第１の局所ルーティング領域と前記第２の局所ルーティング領域との間の、前記隣接する局所ルーティング領域の前記好ましいルーティング方向層に、ｋオーバーフロー値を加算することと、
該転送機構が、前記第２の局所ルーティング領域の前記受信ルーティング層に、Ｃオーバーフロー値を加算することと
を含む、請求項３に記載の方法。
【請求項５】
一群の局所ルーティング領域にわたる前記グローバルオーバーフローコストを計算することは、全局所ルーティング領域の全層ｉにわたるオーバーフローの和の関数ｆとして、前記コストを計算する
【数３】
0005403834.tif 000038
ことを含む、請求項１に記載の方法。
【請求項６】
前記隣接するオーバーフローコストを計算することは、ルートオーバーフローを伴う、隣接する局所ルーティング領域のいくつかのクラスタｊにわたる前記コストの和を計算することを含み、クラスタのコストｇは、該クラスタ内の局所ルーティング領域の数および該クラスタにわたる前記オーバーフローの和の関数
【数４】
0005403834.tif 000039
である、請求項１に記載の方法。
【請求項７】
局所ルーティング領域は、対応する方向Ｄ＝ｄを伴う、第１のルーティング層におけるオーバーフローおよび過剰容量の推定に関連し、かつ、対応する方向
【数５】
0005403834.tif 000040
を伴う、第２のルーティング層におけるオーバーフローおよび過剰容量の推定に関連し、前記方向
【数６】
0005403834.tif 000041
は、前記方向ｄに直交する、請求項１に記載の方法。
【請求項８】
局所ルーティング領域内の層でのオーバーフローの推定は、変数ＯＶの正の値によって表され、該局所ルーティング領域内の前記層での過剰容量の推定は、変数ＯＶの負の値によって表される、請求項７に記載の方法。
【請求項９】
命令を格納するコンピュータ読み取り可能格納媒体であって、該命令は、コンピュータによって実行されると、該コンピュータに、回路レイアウトに関連する一群の局所ルーティング領域にわたるルーティング可能性推定を計算するための方法を実施させ、該方法は、
ルートオーバーフローに関連する第１の局所ルーティング領域を選択することであって、それぞれの局所ルーティング領域は、該回路レイアウトの領域内のルーティング層に対するいくつかのルートオーバーフローの推定に関連付けられ、該第１の局所ルーティング領域は、方向ｄにおけるｋ以上のルートのオーバーフローに関連するオーバーフロールーティング層を含み、それぞれのルーティング層は、好ましい方向Ｄに関連付けられ、Ｒ個のルートのオーバーフローまたはＣ個のルートの過剰容量のいずれかに関連付けられる、ことと、
第２の局所ルーティング領域を識別することであって、該第２の局所ルーティング領域は、該オーバーフロールーティング層における該オーバーフローに対応するための該方向ｄにおける過剰容量を有し、該第１の局所ルーティング領域の該オーバーフロールーティング層と該第２の局所ルーティング領域との間に過剰経路が存在し、該過剰経路は、該方向ｄに直交する、ことと、
該オーバーフロールーティング層から、該第２の局所ルーティング領域へ、オーバーフロー値ｋを転送することと、
グローバルオーバーフローコストおよび隣接するオーバーフローコストの関数として、グローバルルーティング可能性推定を計算することであって、該隣接するオーバーフローコストは、隣接するオーバーフロー局所ルーティング領域からなるクラスタのオーバーフローコストである、ことと
を含む、コンピュータ読み取り可能格納媒体。
【請求項１０】
前記方向ｄにおけるｋ以上のルートのオーバーフローに関連する前記第１の局所ルーティング領域のオーバーフロールーティング層から、第２の局所ルーティング領域へ、オーバーフロー値ｋを転送することは、
前記好ましい方向ｄにおける少なくともＣ＝ｋのルートの過剰容量に関連する受信ルーティング層を備える、第２の局所ルーティング領域について第１の検索を実施することと、
該第１の検索が成功しない場合、好ましくない方向
【数７】
0005403834.tif 000042
における少なくともＣ＝ｎ＊ｋのルートの過剰容量に関連する受信ルーティング層を備える、第２の局所ルーティング領域について第２の検索を実施することであって、ｎは、ルーティング層の前記好ましくない方向におけるルートに対応するように使用される、いくつかのトラックを表す、好ましくない方向の因数である、ことと、
該第２の局所ルーティング領域が見出された場合、前記オーバーフロー値Ｃを該第２の局所ルーティング領域の受信層に転送することと
を含み、該好ましくない方向
【数８】
0005403834.tif 000043
は、前記好ましい方向ｄに直交する、請求項９に記載のコンピュータ読み取り可能格納媒体。
【請求項１１】
前記第２の局所ルーティング領域を検索することは、前記好ましいルーティング方向を使用する層上のｋ以上のルートの過剰容量に関連する、いくつかの隣接する局所ルーティング領域を通って、前記第１の局所ルーティング領域から前記第２の局所ルーティング領域まで経路が存在することを確認することを含む、請求項１０に記載のコンピュータ読み取り可能格納媒体。
【請求項１２】
前記オーバーフロー値Ｃを、前記第２の局所ルーティング領域の前記受信層に転送することは、
前記第１の局所ルーティング領域の前記オーバーフロールーティング層からｋオーバーフロー値を減算することと、
前記第１の局所ルーティング領域と前記第２の局所ルーティング領域との間の、前記隣接する局所ルーティング領域の前記好ましいルーティング方向層に、ｋオーバーフロー値を加算することと、
前記第２の局所ルーティング領域の前記受信ルーティング層に、Ｃオーバーフロー値を加算することと
を含む、請求項１１に記載のコンピュータ読み取り可能格納媒体。
【請求項１３】
一群の局所ルーティング領域にわたる前記グローバルオーバーフローコストを計算することは、全局所ルーティング領域の全層ｉにわたるオーバーフローの和の関数ｆとして、前記コストを計算する
【数９】
0005403834.tif 000044
ことを含む、請求項９に記載のコンピュータ読み取り可能格納媒体。
【請求項１４】
前記隣接するオーバーフローコストを計算することは、ルートオーバーフローを伴う、隣接する局所ルーティング領域のいくつかのクラスタｊにわたる前記コストの和を計算することを含み、クラスタのコストｇは、該クラスタ内の局所ルーティング領域の数および該クラスタにわたる前記オーバーフローの和の関数
【数１０】
0005403834.tif 000045
である、請求項９に記載のコンピュータ読み取り可能格納媒体。
【請求項１５】
局所ルーティング領域は、対応する方向Ｄ＝ｄを伴う、第１のルーティング層におけるオーバーフローおよび過剰容量の推定に関連し、かつ、対応する方向
【数１１】
0005403834.tif 000046
を伴う、第２のルーティング層におけるオーバーフローおよび過剰容量の推定に関連し、前記方向
【数１２】
0005403834.tif 000047
は、前記方向ｄに直交する、請求項９に記載のコンピュータ読み取り可能格納媒体。
【請求項１６】
局所ルーティング領域内の層でのオーバーフローの推定は、変数ＯＶの正の値によって表され、該局所ルーティング領域内の前記層での過剰容量の推定は、変数ＯＶの負の値によって表される、請求項１５に記載のコンピュータ読み取り可能格納媒体。
【請求項１７】
回路レイアウトに関連する一群の局所ルーティング領域にわたるルーティング可能性推定を計算するための装置であって、
ルートオーバーフローに関連する第１の局所ルーティング領域を選択するように構成される選択機構であって、それぞれの局所ルーティング領域は、該回路レイアウトの領域内のルーティング層に対するいくつかのルートオーバーフローの推定に関連付けられ、該第１の局所ルーティング領域は、方向ｄにおけるｋ以上のルートのオーバーフローに関連するオーバーフロールーティング層を含み、それぞれのルーティング層は、好ましい方向Ｄに関連付けられ、Ｒ個のルートのオーバーフローまたはＣ個のルートの過剰容量のいずれかに関連付けられる、選択機構と、
第２の局所ルーティング領域を識別するように構成される識別機構であって、該第２の局所ルーティング領域は、該オーバーフロールーティング層における該オーバーフローに対応するための該方向ｄにおける過剰容量を有し、該第１の局所ルーティング領域の該オーバーフロールーティング層と該第２の局所ルーティング領域との間に過剰経路が存在し、該過剰経路は、該方向ｄに直交する、識別機構と、
該オーバーフロールーティング層から、該第２の局所ルーティング領域へ、オーバーフロー値ｋを転送するように構成される転送機構と、
グローバルオーバーフローコストおよび隣接するオーバーフローコストの関数として、グローバルルーティング可能性推定を計算するように構成される計算機構であって、該隣接するオーバーフローコストは、隣接するオーバーフロー局所ルーティング領域からなるクラスタのオーバーフローコストである、計算機構と
を備える、装置。
【請求項１８】
前記方向ｄにおけるｋ以上のルートのオーバーフローに関連する前記第１の局所ルーティング領域のオーバーフロールーティング層から、第２の局所ルーティング領域へ、オーバーフロー値ｋを転送している間に、前記転送機構は、
前記好ましい方向ｄにおける少なくともＣ＝ｋのルートの過剰容量に関連する受信ルーティング層を備える、第２の局所ルーティング領域について第１の検索を実施することと、
該第１の検索が成功しない場合、好ましくない方向
【数１３】
0005403834.tif 000048
における少なくともＣ＝ｎ＊ｋのルートの過剰容量に関連する受信ルーティング層を備える、第２の局所ルーティング領域について第２の検索を実施することであって、ｎは、ルーティング層の前記好ましくない方向におけるルートに対応するように使用される、いくつかのトラックを表す、好ましくない方向の因数である、ことと、
該第２の局所ルーティング領域が見出された場合、前記オーバーフロー値Ｃを該第２の局所ルーティング領域の受信層に転送することと
を実行するように構成され、
該好ましくない方向
【数１４】
0005403834.tif 000049
は、前記好ましい方向ｄに直交する、請求項１７に記載の装置。
【請求項１９】
前記第２の局所ルーティング領域を検索している間に、前記転送機構は、前記好ましいルーティング方向を使用する層上のｋ以上のルートの過剰容量に関連する、いくつかの隣接する局所ルーティング領域を通って、前記第１の局所ルーティング領域から前記第２の局所ルーティング領域まで経路が存在することを確認するように構成される、請求項１８に記載の装置。
【請求項２０】
前記オーバーフロー値Ｃを、前記第２の局所ルーティング領域の前記受信層に転送している間に、前記転送機構は、
前記第１の局所ルーティング領域の前記オーバーフロールーティング層からｋオーバーフロー値を減算することと、
前記第１の局所ルーティング領域と前記第２の局所ルーティング領域との間の、前記隣接する局所ルーティング領域の前記好ましいルーティング方向層に、ｋオーバーフロー値を加算することと、
前記第２の局所ルーティング領域の前記受信ルーティング層に、Ｃオーバーフロー値を加算することと
を実行するように構成される、請求項１９に記載の装置。
【請求項２１】
一群の局所ルーティング領域にわたる前記グローバルオーバーフローコストを計算している間に、前記計算機構は、全局所ルーティング領域の全層ｉにわたるオーバーフローの和の関数ｆとして、前記コストを計算する
【数１５】
0005403834.tif 000050
ように構成される、請求項１７に記載の装置。
【請求項２２】
前記隣接するオーバーフローコストを計算している間に、前記計算機構は、ルートオーバーフローを伴う、隣接する局所ルーティング領域のいくつかのクラスタｊにわたる前記コストの和を計算するように構成され、クラスタのコストｇは、該クラスタ内の局所ルーティング領域の数および該クラスタにわたる前記オーバーフローの和の関数
【数１６】
0005403834.tif 000051
である、請求項１７に記載の装置。
【請求項２３】
局所ルーティング領域は、対応する方向Ｄ＝ｄを伴う、第１のルーティング層におけるオーバーフローおよび過剰容量の推定に関連し、かつ、対応する方向
【数１７】
0005403834.tif 000052
を伴う、第２のルーティング層におけるオーバーフローおよび過剰容量の推定に関連し、前記方向
【数１８】
0005403834.tif 000053
は、前記方向ｄに直交する、請求項１７に記載の装置。
【請求項２４】
局所ルーティング領域内の層でのオーバーフローの推定は、変数ＯＶの正の値によって表され、該局所ルーティング領域内の前記層での過剰容量の推定は、変数ＯＶの負の値によって表される、請求項２３に記載の装置。
【請求項２５】
前記転送機構は、詳細ルータのルーティング能力をエミュレートする、請求項１７に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、概して、回路設計のフロアプランのためのルーティング可能性推定を計算するための技法に関する。より具体的には、本発明は、超過密の局所ルーティング領域から、未過密の局所ルーティング領域へ、ルートオーバーフロー値を再配分して、フロアプラン上のルーティング可能性の推定を計算するシステムに関する。
【背景技術】
【０００２】
回路設計のフロアプランに対して詳細ルーティング操作を実施することは、完了に数日かかり得る、高価な過程である。さらに悪いことに、詳細ルーティング操作は、必ずしも成功が保証されていない。詳細ルーティングは、したがって、数種の設計を検討してルーティング可能性を評価する際に使用すべき実際的な過程ではない。
【０００３】
回路設計の所与のフロアプランの初回通過のルーティングツールとして、グローバルルータが一般的に使用される。フロアプランを一群の局所ルーティング領域として分析し、さらに局所ルーティング領域の間にルートを配置することによって、フロアプラン全体にルートを配置する。グローバルルータの手順では、グローバルルートソリューションを作成し、これが、その後、詳細ルータに渡されて、ルーティングタスクを完了する。グローバルルートソリューションが、いくつかの局所ルーティング領域に関連する、ルートオーバーフローを含むことは一般的である。残念ながら、これらのルートオーバーフローは、以降の詳細ルーティング作業によって解決される場合も、されない場合もある。
【０００４】
詳細ルータが必ずしも成功するとは限らないことを考慮して、グローバルルータは、所与のフロアプランの単純なルーティング可能性分析も実施することによって、技術者が、詳細ルータによるルーティング操作の完了可能性を予測することを可能にする。ルーティング可能性の分析が成功すると、技術者は、フロアプランが詳細ルータによって処理される前に、フロアプランのルーティング可能性を最適化することを可能にして、したがって、いくつかの詳細ルーティング作業が無駄になることを防止することができることから、その成功は重要である。ルーティング可能性の分析に一般的に使用される方法は、グローバルルーティング操作後に、ルートのオーバーフローを有する局所ルーティング領域のパーセントを確認するステップを含む。この分析において、オーバーフローは、局所ルーティング領域の全体容量に比較して、使用可能なトラックに対する過剰な要求として定義される。典型的に、オーバーフローのパーセントが、フロアプランで２％を超える場合、そのフロアプランは、ルーティング不可能と見なされる。設計のルーティング可能性を推定するための本方法は、しばしば誤検出につながることがあり、さらに、検出漏れにつながる可能性もあることから、正確ではない。さらに、本方法は、詳細ルータの能力および制限を考慮しないことから、フロアプランのルーティング可能性に対するその分析には限界がある。
【発明の概要】
【課題を解決するための手段】
【０００５】
本発明の一実施形態は、回路のレイアウトに関連する、一群の局所ルーティング領域にわたるルーティング可能性推定を計算するシステムを提供する。本システムは、まず、ルートオーバーフローに関連する第１の局所ルーティング領域を選択し、それぞれの局所ルーティング領域は、回路レイアウトの領域内のルーティング層に対して詳細ルータが経験するであろう、いくつかのルートオーバーフローの推定に関連付けられる。さらに、それぞれのルーティング層は、好ましい方向変数Ｄに関連付けられ、ＲのルートのオーバーフローまたはＣのルートの過剰能力のいずれかに関連付けられる。次に、システムは、第１の局所ルーティング領域のオーバーフロールーティング層から、方向ｄにおけるｋ以上のルートのオーバーフローを処理する容量を有する、第２の局所ルーティング領域へ、方向ｄにおけるオーバーフロー値ｋを転送する。最後に、システムは、グローバルオーバーフローコストおよび隣接するオーバーフローコストの関数として、グローバルルーティング可能性推定を計算する。
【０００６】
一部の実施形態において、第１の局所ルーティング領域のオーバーフローしているルーティング層から、第２の局所ルーティング領域へ、オーバーフロー値ｋを転送するステップは、十分な過剰容量を有する第２の局所ルーティング領域を検索するステップが関与する。この過程の間、システムは、まず、好ましい方向ｄにおける少なくともＣ＝ｋのルートの過剰容量に関連する受信ルーティング層を有する、第２の局所ルーティング領域について第１の検索を実施する。第１の検索が成功しない場合、システムは、好ましくない方向
【０００７】
【化１】
0005403834.tif 000002
における少なくともＣ＝ｎ＊ｋのルートの過剰容量に関連する受信ルーティング層を有する、第２の局所ルーティング領域について第２の検索を実施する。変数ｎは、ルーティング層の好ましくない方向におけるルートに対応するように使用される、いくつかのトラックを表す、好ましくない方向の因数である。第２の局所ルーティング領域が見出された場合、システムは、オーバーフロー値Ｃを第２の局所ルーティング領域の受信層へ転送する。
【０００８】
一部の実施形態において、システムは、第１の局所ルーティング領域に対する、好ましい方向Ｄ＝ｄを伴うオーバーフロールーティング層から、好ましくない方向
【０００９】
【化２】
0005403834.tif 000003
および少なくともＣ＝ｎ＊ｋのルートの組み合わされた過剰容量に関連する、１つ以上のルーティング層を有する第２の局所ルーティング領域へ、オーバーフロー値ｋを転送する。
【００１０】
一部の実施形態において、システムが、第２の局所ルーティング領域を検索する時、システムは、好ましい方向のｋ以上のルートの過剰容量に関連する、いくつかの隣接する局所ルーティング領域を通って、第１の局部領域から第２の局部領域まで経路が存在することを確認する。
【００１１】
一部の実施形態において、システムが、第２の局所ルーティング領域を検索する時、検索機能は、詳細ルータの検索ウィンドウに関連する能力をエミュレートする。
【００１２】
一部の実施形態において、システムは、まず、第１の局所ルーティング領域のオーバーフロールーティング層から、オーバーフロー値ｋを減算することによって、オーバーフロー値Ｃを第２の局所ルーティング領域の受信層へ転送する。次に、システムは、第１の局所ルーティング領域と第２の局所ルーティング領域との間の隣接する局所ルーティング領域に、オーバーフロー値ｋを加算する。最後に、システムは、第２の局所ルーティング領域の受信ルーティング層に、オーバーフロー値Ｃを加算する。
【００１３】
一部の実施形態において、一群の局所ルーティング領域にわたるグローバルルーティング可能性推定を計算するステップは、グローバルオーバーフローコストおよび隣接するオーバーフローコストの和を計算するステップが関与する。
【００１４】
【数１】
0005403834.tif 000004
一部の実施形態において、一群の局所ルーティング領域にわたるグローバルオーバーフローコストを計算するステップは、各局所ルーティング領域の各層ｉにわたるオーバーフローの和の関数ｆとして、コストを計算するステップを含む。
【００１５】
【数２】
0005403834.tif 000005
一部の実施形態において、隣接するオーバーフローコストを計算するステップは、隣接する局所ルーティング領域のいくつかのクラスタｊにわたるコストの和を計算するステップを含み、クラスタのコストｇは、前記クラスタ内の局所ルーティング領域の数および前記クラスタにわたる前記オーバーフローの和の関数である。
【００１６】
【数３】
0005403834.tif 000006
一部の実施形態において、好ましくない方向
【００１７】
【化３】
0005403834.tif 000007
は、好ましい方向ｄに直交する。
【００１８】
一部の実施形態において、局所ルーティング領域は、対応する方向Ｄ＝ｄを伴う、第１のルーティング層内のオーバーフローおよび過剰容量の推定に関連し、対応する方向
【００１９】
【化４】
0005403834.tif 000008
を伴う、第２のルーティング層内のオーバーフローおよび過剰容量の推定を含む。
【００２０】
一部の実施形態において、局所ルーティング領域内の層でのオーバーフローの推定は、変数ＯＶの正の値によって表され、局所ルーティング領域内の層での過剰容量の推定は、変数ＯＶの負の値によって表される。
【図面の簡単な説明】
【００２１】
【図１】図１は、本発明の実施形態に従い、ルーティング可能性推定システムを示す。
【図２】図２は、本発明の実施形態に従い、ルーティング可能性推定を使用する設計レイアウト過程の利点を示す、対照的なフローチャートを示す。
【図３】図３Ａ−３Ｂは、本発明の実施形態に従い、局所ルーティング領域を示す。
【図４】図４は、本発明の実施形態に従い、いくつかの局所ルーティング領域を備える、例示的な迷路を示す。
【図５】図５Ａ−５Ｄは、本発明の実施形態に従い、好ましい方向を使用することによって、受信ルーティング層にオーバーフロー値を転送することによる例示的な結果を示す。
【図６】図６Ａ−６Ｄは、本発明の実施形態に従い、好ましい方向および好ましくない方向を使用することによって、受信ルーティング層にオーバーフロー値を移転することによる例示的な結果を示す。
【図７】図７は、本発明の実施形態に従い、例示的なルーティング可能性推定ディスプレイを示す。
【図８】図８は、本発明の実施形態に従い、グローバルルーティング可能性推定を計算するための過程を示すフローチャートを示す。
【図９】図９は、本発明の実施形態に従い、方向ｄにおけるＣ＞ｋのルートの過剰容量を備える、受信局所ルーティング領域を選択するための過程を示すフローチャートを示す。
【図１０】図１０は、本発明の実施形態に従い、受信局所ルーティング領域へ、オーバーフロー値Ｃを転送するための過程を示すフローチャートを示す。
【図１１】図１１は、本発明の実施形態に従い、グローバルルーティング可能性推定を計算するための過程を示すフローチャートを示す。
【発明を実施するための形態】
【００２２】
以下の説明は、いずれの当業者も、本発明を行い、使用できるようにするために提示され、特定の用途およびその要件の文脈において提供される。開示される実施形態に対する種々の修正は、当業者に容易に明らかとなり、本明細書に定義される一般的原理は、本発明の趣旨および範囲から逸脱することなく、他の実施形態ならびに用途に適用され得る。したがって、本発明は、示される実施形態に限定されないが、本明細書に開示する原則および特徴に従う最大範囲に一致するものである。
【００２３】
本詳細な説明に記載するデータ構造およびコードは、通常、コンピュータシステムによって使用するためのコードおよび／またはデータを記憶できる任意の素子または媒体であり得る、コンピュータ読み取り可能記憶媒体に記憶される。コンピュータ読み取り可能記憶媒体は、揮発性メモリ、非揮発性メモリ、ディスクドライブ、磁気テープ、ＣＤ（コンパクトディスク）、ＤＶＤ（デジタル多用途ディスクまたはデジタルビデオディスク）、または現在知られているか、または今後開発されるコンピュータ読み取り可能媒体を記憶できる他の媒体を含むが、これらに限定されない。
【００２４】
詳細な説明の節に記載する方法および過程は、コードおよび／またはデータとして具体化され得、上述のとおりコンピュータ読み取り可能記憶媒体に記憶され得る。コンピュータシステムが、コンピュータ読み取り可能記憶媒体上に記憶されるコードおよび／またはデータを読み出して実行するとき、コンピュータシステムは、データ構造として具体化され、コンピュータ読み取り可能記憶媒体内に記憶される方法および過程を実行する。
【００２５】
さらに、以下に説明される方法および過程は、ハードウェアモジュールに含まれてもよい。例えば、該ハードウェアモジュールは、アプリケーション特有の集積回路（ＡＳＩＣ）チップ、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、および現在知られているか、または今後開発される他のプログラマブル論理素子を含み得るが、これらに限定されない。ハードウェアモジュールが起動されると、ハードウェアモジュールは、ハードウェアモジュール内に含まれる方法および過程を実行する。
【００２６】
（概説）
回路設計の詳細ルーティングは高価な過程であり、回路のフロアプランがルーティング可能であることを必ずしも保証しない。したがって、フロアプラン上に詳細ルーティングを実施しようとする前に、設計のルーティング可能性を予測して、フロアプランがルーティング可能であるかどうかを決定することが重要である。本発明の実施形態は、一群の局所ルーティング領域のグローバルルーティング操作から抽出される、ルートオーバーフロー情報に基づいて、回路設計のフロアプランに対するルーティング可能性推定を計算するシステムを提供する。（フロアプランに関連する、一群の局所ルーティング領域は、本開示の以下の説明では「迷路」と称されることに注意されたい）。
【００２７】
本システムは、それぞれの局所ルーティング領域を使用して、水平方向または縦方向に関連する、いくつかのルートオーバーフロー（または、反対に、ルートの過剰容量）を特定する。本システムは、まず、超過密な局所ルーティング領域から、未過密な局所ルーティング領域へ、ルートオーバーフロー値を分散しようとすることによって、回路設計のフロアプランに対するルーティング可能性推定を計算する。本システムは、迷路全体で物理的にルートを移動するのではなく、設計規則検証（ＤＲＣ）推定を計算する前に、このような移動の結果を計算する。
【００２８】
（ルーティング可能性推定システム）
図１は、本発明の実施形態に従い、ルーティング可能性推定システム１００を示す。ルーティング可能性推定システム１００は、グローバルルータ１０４と、ルーティング可能性推定ユニット１０６と、詳細ルータ１０８と、ネットワーク１０２と、を含む。ネットワーク１０２は、任意の種類の有線または無線通信チャネルを含むことができる。本発明の一実施形態において、ネットワーク１０２は、インターネットを含む。
【００２９】
グローバルルータ１０４は、計算能力を備える任意のノードと、ネットワーク１０２を通じて、ルーティング可能性推定ユニット１０６および詳細ルータ１０８と通信するための通信機構と、を含むことができる。グローバルルータ１０４によって、ユーザ１１６は、一群の標準セルを、回路レイアウトのフロアプランに配置および相互接続することが可能になる。まず、これらの標準セルは、それらのフロアプランの位置に基づいて、一群の局所ルーティング領域に割り当てられる。次に、グローバルルータ１０４は、これらの局所ルーティング領域間の相互接続をルーティングしようとする。グローバルルータ１０４が、局所ルーティング領域間の相互接続をルーティングしようとした後、グローバルルータ１０４は、オーバーフロー情報１１０を、ルーティング可能性推定ユニット１０６へ転送する。これに応じて、グローバルルータ１０４は、ルーティング可能性推定ユニット１０６から、ルーティング可能性推定１１２を受信する。ルートオーバーフローによるコストが、事前に定義された閾値を上回る場合、ユーザ１１６は、任意の報告されたオーバーフローを軽減するように、フロアプランおよび／または標準セルの配置を変更することができる。そうでなければ、ルートオーバーフローユニット１０４は、グローバルルート１１４を詳細ルータ１０８へ転送する。
【００３０】
ルーティング可能性推定ユニット１０６は、計算能力を備える任意のノードと、ネットワーク１０２を通じて、グローバルルータ１０４と通信するための通信機構と、を含むことができる。ルーティング可能性推定ユニット１０６は、グローバルルータ１０４からオーバーフロー情報１１０を受信し、フロアプランのルーティング可能性を推定する手段として、局所ルーティング領域全体でオーバーフローを再配分する、一連の操作を開始する。次に、ルーティング可能性推定ユニット１０６は、ルーティング可能性推定１１２を計算し、ルーティング可能性推定１１２をグローバルルータ１０４へ転送する。
【００３１】
詳細ルータ１０８は、計算機能を備える任意のノードと、ネットワーク１０２を通じて、グローバルルータ１０４と通信するための通信機構と、を含むことができる。詳細ルータ１０８は、グローバルルータ１０４からグローバルルーティング１１４を受信し、局所ルーティング領域間の相互接続をルーティングするように、かつ、局所ルーティング領域内の標準セル間の相互接続をルーティングするように、一連の操作を実施する。
【００３２】
ユーザ１１６〜１１８は、ルーティング可能性システム１００と相互作用することができる、個人、個人群、組織、組織群、コンピュータシステム、コンピュータシステム群、または任意の他のエンティティであり得る。
【００３３】
本発明の異なる実施形態は、異なる構成を使用することができ、ルーティング可能性推定システム１００に図説される構成に限定されないことに注意されたい。本発明の一部の実施形態において、グローバルルータ１０４は、ルーティング可能性推定ユニット１０６および／または詳細ルータ１０８を含む。
【００３４】
図２は、本発明の実施形態に従い、ルーティング可能性推定を使用する、設計レイアウト過程の利点を示す対照的なフローチャートを示す。図２Ａは、ルーティング可能性推定を使用しない設計レイアウト過程２００を示すフローチャートを示す。この過程において、ユーザは、まず、回路レイアウトのフロアプランを生成し（操作２０２）、グローバルルータを使用して、局所ルーティング領域間の相互接続をルーティングする（操作２０４）。次に、ユーザは、詳細ルータを使用して、局所ルーティング領域間、および局所ルーティング領域内の標準セル間の相互接続をルーティングして、回路レイアウトを作成する（操作２０６）。ユーザは、詳細ルータが、フロアプランのルーティングに成功したかどうかを決定することが必要である（操作２０８）。詳細ルータの成功または失敗は、詳細ルーティング後に、設計に存在する設計規則エラー（ＤＲＣエラー）の程度（数）によって決定される。詳細ルータが、フロアプランのルーティングに失敗した場合、ユーザは、フロアプランを変更し（操作２１０）、操作２０４に戻って、グローバルルーティングおよび詳細ルーティングをもう一度実施する。詳細ルータが、フロアプランを回路レイアウトにルーティングすることに成功した場合、ユーザは、回路レイアウト上で設計規則検証（ＤＲＣ）を実施し（操作２１２）、テープアウトを開始する（操作２１６）前に、最後のいくつかのＤＲＣエラーを手動で修正する（操作２１４）。
【００３５】
詳細ルータは、典型的に、その操作を完了するまでに数日かかるので、したがって、失敗した詳細ルーティングの試行はいずれも、何日かの損失不利益がある。ルーティング不可能なフロアプランに関連する損失不利益を軽減するように、本発明の実施形態は、ユーザが、フロアプランが詳細ルータによってルーティングされ得るかどうかを決定することを可能にする操作として、ルーティング可能性推定を採用する。
【００３６】
図２Ｂは、ルーティング可能性推定を使用する設計レイアウト過程２２０を示すフローチャートを示す。この過程において、ユーザは、まず、回路レイアウトのフロアプランを生成し（操作２２２）、グローバルルータを使用して、局所ルーティング領域間の相互接続をルーティングする（操作２２４）。図２Ａとは異なり、ユーザは、詳細ルーティングを実施しようとする前に、引き続き、ルーティング可能性推定を使用して、発生するであろういくつかのＤＲＣ違反を予測する（操作２２６）。ルーティング可能性推定ユニットは、その入力として、グローバルルータ１０４からオーバーフロー情報を受理し、ルーティング可能性推定を計算する。次に、ユーザは、ルーティング可能性推定に基づいて、フロアプランがルーティング可能であるかどうかを決定することが必要である（操作２２８）。ユーザが、オーバーフロールートが多すぎることから、設計はルーティング可能ではないと決定した場合、ユーザは、フロアプランを変更し（操作２３０）、操作２２４に戻って、グローバルルーティングおよびルーティング可能性推定をもう一度実施する。そうでなければ、ユーザは、詳細ルータを使用するように進み、回路レイアウトを作成する（操作２３２）。詳細ルータは、グローバルルータからのグローバルルーティング出力を受理し、局所ルーティング領域間、および局所ルーティング領域内の標準セル間の相互接続をルーティングして、回路レイアウトを作成する。次に、ユーザは、回路レイアウト上で設計規則検証（ＤＲＣ）を実施し（操作２３４）、テープアウトを開始する（操作２３８）前に、最後のいくつかのＤＲＣエラーを手動で修正する（操作２３６）。
【００３７】
ルーティング可能性推定は、典型的に、ルーティング可能な回路のフロアプランが生成されるまで、詳細ルーティングの実施という高価な操作を先送りする、その操作を完了するまでに何分か（１時間未満）かかる。この結果、ルーティング可能性推定によって、ユーザは、フロアプランを生成する間の反復過程あたり何日か分、有効な回路フロアプランを生成するために必要な時間を削減することが可能になる。
【００３８】
（局所ルーティング領域）
図３Ａは、本発明の実施形態に従い、局所ルーティング領域３００を示す。局所ルーティング領域３００は、いくつかのルーティング層を備える。それぞれのルーティング層３０２は、オーバーフロー３０４と、好ましい方向３０６と、を含む。負のオーバーフロー値ｒは、それぞれのルーティング層に関連するｒのルートの過剰容量を示し、正のオーバーフロー値ｒは、それぞれのルーティング層に関連するｒのルートのオーバーフローを示す。好ましい方向３０６は、ルートが、オーバーフロー上に過剰なコストを被ることなく従うことができる、ルーティング層の方向ｄを示す。ルートが、好ましくない方向
【００３９】
【化５】
0005403834.tif 000009
（好ましい方向ｄに直交する）に従う場合、オーバーフローは、単一のルーティングトラックに関連するコストではなく、ｎのルーティングトラックのコスト分増加する。好ましくない方向に関連するコストｎは、本開示の以下では、好ましくない方向の因数と称され、ルーティング層の好ましくない方向におけるルートに対応するように使用される、いくつかのトラックを表す。コストｎは、それぞれのルーティング層の容量に依存し得る。
【００４０】
図３Ｂは、局所ルーティング領域３１０を示し、これは、本発明の実施形態に従い、局所ルーティング領域の簡素化された図である。局所ルーティング領域３１０は、説明を簡素化するために、本開示の以下において使用されることに注意されたい。局所ルーティング領域３１０は、２つのルーティング層を含む。水平方向ルーティング層３１２は、好ましい水平方向のルーティング方向に関連付けられる。同様に、縦方向ルーティング層３１４は、好ましい縦方向のルーティング方向に関連付けられる。水平方向ルーティング層３１２は、オーバーフロー３１６に関連付けられ、縦方向ルーティング層３１４は、オーバーフロー３１８に関連付けられる。局所ルーティング領域３００に類似して、負のオーバーフロー値ｒは、ｒのルートの過剰容量を表し、正のオーバーフロー値ｒは、ｒのルートのオーバーフローを表す。
【００４１】
図４は、本発明の実施形態に従い、いくつかの局所ルーティング領域４０２を備える、例示的な迷路４００を示す。図説の目的において、迷路４００は、好ましい水平方向を伴う層０のルート４０４を含み、かつ、好ましい縦方向を伴う層１のルート４０６を含む。層０のルート４０４は、局所ルーティング領域Ａ１からＣ１までの間の好ましい方向のルートを使用し、かつ、局所ルーティング領域Ａ０とＡ１との間で好ましくない方向のルート４０８を使用する。好ましくない方向のルート４０８は、局所ルーティング領域Ａ０およびＡ１が、縦方向ルーティング層（この場合、層１）内のルートに対して過剰容量を有さない場合に、存在する。
【００４２】
同様に、層１のルート４０６は、局所ルーティング領域Ｄ１からＤ３までの間の好ましい方向のルートを使用し、かつ、局所ルーティング領域Ｃ１とＤ１との間で好ましくない方向のルート４１０を使用する。好ましくない方向のルート４１０は、局所ルーティング領域Ｃ１およびＤ１が、水平方向のルーティング層（この場合、層０）内のルートに対して過剰容量を有さない場合に、存在する。
【００４３】
（グローバルルーティング可能性推定の計算）
本発明の実施形態は、まず、ルートオーバーフロー値を、ルートの過剰容量に関連する局所ルーティング領域へ転送することによって、グローバルルーティング可能性推定を計算するためのシステムを提供する。これらの実施形態の一部の変形において、システムは、詳細ルータの能力のうちの一部をエミュレートすることによって、ルートオーバーフロー値を転送する。
【００４４】
図５Ａは、本発明の実施形態に従い、局所ルーティング領域の好ましい方向を使用することによって、受信ルーティング層へオーバーフロー値を転送することによる例示的な結果を示す。図５Ａは、オーバーフロー縦方向ルーティング層を有する局所ルーティング領域Ｃ１を備える迷路５００を示し、対応するルートは、図５Ｂに示される。
【００４５】
局所ルーティング領域Ｃ１の縦方向ルーティング層は、３つのオーバーフロールートを有するが、図５Ｂは、局所ルーティング領域Ｃ１のオーバーフロー層から転送される、１つのオーバーフロールートだけを示すことに注意されたい。本開示の以下では、一度に、オーバーフロールーティング層から、１つのオーバーフロー値を転送するための例だけを提供する。しかしながら、本明細書に開示される操作は、２つ以上のオーバーフロー値を転送することにも適用され得る。
【００４６】
図５Ａは、局所ルーティング領域Ｃ１に関連するルートウィンドウ５０２を備える迷路５００も示す。ルートウィンドウは、ルートのオーバーフローを備える局所ルーティング領域のそれぞれのルーティング層に対して、ルートオーバーフローを受信するために使用され得る、局所ルーティング領域の範囲を指定する。この実施例において、ルートウィンドウは、事前に決定されたサイズの５つの局所ルーティング領域に設定される。局所ルーティング領域Ｃ１の縦方向ルーティング層に関連するルートウィンドウ５０２の場合は、ユニットＡ１からＥ１までに及ぶ、水平方向のウィンドウである。
【００４７】
局所ルーティング領域Ｃ１の縦方向ルーティング層からルートオーバーフローを転送するための過程は、オーバーフロールーティング層と受信ルーティング層との間に経路が存在するように、縦方向ルーティング層内に過剰容量を有する最近接の局所ルーティング領域を検索することによって、開始する。まず、隣接する領域Ｂ１およびＤ１が検討される。局所ルーティング領域Ｂ１は、縦方向ルーティング層内に過剰容量を確かに有するが、しかしながら、領域Ｂ１への水平方向の経路が存在しないため、領域Ｃ１の縦方向ルーティング層から領域Ｂ１の縦方向ルーティング層へ経路が存在しないことに注意されたい（領域Ｂ１の水平方向ルーティング層は、負のオーバーフローを有さないので、したがって、ルートの過剰容量を有さない）。局所ルーティング領域Ｄ１は、領域Ｄ１の縦方向ルーティング層は、ルートの過剰容量を有さないため、縦方向層内のルートオーバーフローを受信する対象ではない。
【００４８】
次に、局所ルーティング領域Ａ１およびＥ１を検討する。局所ルーティング領域Ｂ１に類似して、局所ルーティング領域Ａ１は、縦方向ルーティング層において過剰容量を確かに有するが、しかしながら、領域Ａ１およびＢ１の水平方向ルーティング層は、ルートの過剰容量を有さないため、領域Ｃ１の縦方向ルーティング層から領域Ａ１の縦方向ルーティング層へ経路が存在しない。しかしながら、局所ルーティング領域Ｅ１は、縦方向ルーティング層内に過剰容量を有するため、局所ルーティング領域Ｅ１は、領域Ｃ１からのルートオーバーフローを受信する最近接の対象であり、局所ルーティング領域Ｃ１、Ｄ１、およびＥ１の水平方向ルーティング層は、ルートの過剰容量も有するため、領域Ｃ１の縦方向ルーティング層から領域Ｅ１の縦方向ルーティング層まで経路が存在する。
【００４９】
一部の実施形態において、システムが、好ましいルーティング方向ｄに関連する受信ルーティング層を検索する時、システムは、対象の受信局所ルーティング領域の方向ｄに関連する全ルーティング層を考慮する。これによって、好ましい方向ｄにｒのルートの組み合わされた過剰容量に関連する、ｌルーティング層を備える局所ルーティング領域は、方向ｄにおけるｒのルートの過剰容量に関連する、単一のルーティング層のように動作することが可能である。
【００５０】
図５Ｃは、局所ルーティング領域Ｃ１の縦方向ルーティング層から、局所ルーティング領域Ｅ１の縦方向ルーティング層へ、ルートオーバーフローが転送された後、最終のオーバーフローを有する迷路５００を示す。図５Ｃの迷路５００は、調整された加重推定を太字で示し、これは、局所ルーティング領域Ｃ１およびＥ１の縦方向ルーティング層の間でとられる経路を明確に表すことに注意されたい。領域Ｃ１の縦方向ルーティング層から、領域Ｅ１の縦方向ルーティング層へ、オーバーフロー値を転送する過程は、次のように進む。まず、オーバーフロールーティング層（この場合、局所ルーティング領域Ｃ１の縦方向ルーティング層）のオーバーフローは、１の値だけ減分される。次に、水平方向経路は、局所ルーティング領域Ｃ１とＥ１との間で使用されることになる。したがって、局所ルーティング領域Ｃ１、Ｄ１およびＥ１の水平方向ルーティング層のオーバーフローは、それぞれ、１の値だけ増分される。最後に、局所ルーティング領域Ｅ１の縦方向ルーティング層は、１の値だけ増分されて、転送を完了する。
【００５１】
図５Ｄは、局所ルーティング領域Ｃ１およびＥ１の縦方向ルーティング層の間の調整されたルートを表す迷路５００を示す。具体的には、局所ルーティング領域Ｃ１の縦方向ルーティング層内のルート（破線で図示）は、局所ルーティング領域Ｃ１からＥ１までにわたる水平方向ルーティング層を通じてルーティングされ（直線で図示）、局所ルーティング領域Ｅ１の縦方向ルーティング層内のルートで終了する。最終的に調整されたルートは、それぞれのルーティング層に対して好ましい方向だけを使用することに注意されたい（つまり、縦方向のルートは、縦方向ルーティング層に存在し、水平方向のルートは、水平方向ルーティング層に存在する）。図６により示される次の実施例は、ソリューションが、ルーティング層の好ましくない方向に依存する場合を示す。
【００５２】
システムが、所望のルーティング方向に関連するルーティング層内にルートの過剰容量を有する局所ルーティング領域を見出さない場合は必ず、システムは、所望のルーティング方向に直交する方向に関連するルーティング層内にｎのルートの過剰容量を有する局所ルーティング領域について第２の検索を開始する。この実施例では、好ましくない方向の因数ｎは、３の値に設定される。
【００５３】
本発明の一部の実施形態において、ルートウィンドウの特徴および能力は、エミュレートされている詳細ルータによって使用される対応する検索ウィンドウの特徴および能力によって決定される。これらの特徴および能力は、それぞれのルートウィンドウの配置および／または寸法を決定するための任意の手順、それぞれのルートウィンドウに関連する受信局所ルーティング領域および／または受信ルーティング層を選択するための任意の検索手順、ならびにオーバーフロー局所ルーティング領域から、それぞれのルートウィンドウに関連する受信局所ルーティング領域の受信ルーティング層へ、オーバーフロー値を転送するための任意の手順を含むが、これらに限定されない。
【００５４】
図６は、本発明の実施形態に従い、好ましい方向および好ましくない方向を使用することによって、受信ルーティング層にオーバーフロー値を転送することによる例示的な結果を示す。図６Ａは、縦方向にオーバーフロールーティング層を有する局所ルーティング領域Ｃ１を備える迷路６００を示し、対応するルートは、図６Ｂに示される。
【００５５】
図６Ａは、局所ルーティング領域Ｃ１に関連するルートウィンドウ６０２を備える迷路６００も示す。ルートウィンドウ６０２は、ここでも、事前に決定されたサイズの５つの局所ルーティング領域に設定される。迷路５００の実施例に類似して、ルートウィンドウ６０２は、局所ルーティング領域Ｃ１の縦方向ルーティング層に関連付けられ、領域Ａ１からＥ１までに及ぶ水平方向のウィンドウである。
【００５６】
ここでも、局所ルーティング領域Ｃ１の縦方向ルーティング層からルートオーバーフローを転送するための過程は、オーバーフロールーティング層と受信ルーティング層との間に経路が存在するように、縦方向ルーティング層内に過剰容量を有する最近接の局所ルーティング領域を検索することによって、開始する。まず、隣接する局所ルーティング領域Ｂ１およびＤ１が検討される。どちらも縦方向ルーティング層内に過剰容量を有さないので、局所ルーティング領域Ｂ１およびＤ１は、適切な対象ではない。次に、局所ルーティング領域Ａ１およびＥ１が検討される。しかしながら、どちらも縦方向ルーティング層内に過剰容量を有さないため、適切な対象ではない。
【００５７】
この時点で、縦方向ルーティング層内の過剰容量に関連する局所ルーティング領域を識別することなく、ルートウィンドウ６０２の限界に到達している。局所ルーティング領域Ｃ１の縦方向ルーティング層からルートオーバーフローを転送するための過程は、水平方向ルーティング層内のｎのルートの過剰容量を有する最近接のルーティング層を検索することによって、継続する。まず、局所ルーティング領域Ｃ１に対する水平方向ルーティング層が検討される。この層は、ｎ＝３のルートの容量が要求されるが、２しか利用可能でないため、水平方向ルーティング方向内の縦方向ルートに対応するために十分な過剰容量を有さない。次に、隣接する局所ルーティング領域Ｂ１およびＤ１が再検討される。局所ルーティング領域Ｂ１およびＤ１のどちらも、水平方向ルーティング層内に４以上のルートの過剰容量を有するため、適切な対象であり、さらに、領域Ｃ１の水平方向ルーティング層は、ルートの過剰容量も有するため、領域Ｃ１の縦方向ルーティング層から領域Ｂ１の水平方向ルーティング層まで経路が存在する。この実施例は、最近接の対象として、局所ルーティング領域Ｂ１を選択する。
【００５８】
一部の実施形態において、システムが、好ましくないルーティング方向
【００５９】
【化６】
0005403834.tif 000010
に関連する受信ルーティング層を検索する時、システムは、対象の受信局所ルーティング領域の方向
【００６０】
【化７】
0005403834.tif 000011
に関連する各ルーティング層を考慮する。これによって、好ましくない方向
【００６１】
【化８】
0005403834.tif 000012
におけるｒのルートの組み合わされた過剰容量に関連する、ｌルーティング層を有する局所ルーティング領域は、方向
【００６２】
【化９】
0005403834.tif 000013
におけるｒのルートの過剰容量に関連する、単一のルーティング層のように動作することが可能になる。
【００６３】
図６Ｃは、局所ルーティング領域Ｃ１の水平方向ルーティング層から、局所ルーティング領域Ｂ１の縦方向ルーティング層へ、ルートオーバーフローが転送された後の最終のオーバーフローを有する迷路６００を示す。図６Ｃの迷路６００は、調整された加重推定を太字で示し、これは、局所ルーティング領域Ｃ１の縦方向ルーティング層と、局所ルーティング領域Ｂ１の水平方向ルーティング層との間でとられる経路を明確に表すことに注意されたい。領域Ｃ１の縦方向ルーティング層から、領域Ｂ１の水平方向ルーティング層へ、オーバーフロー値を転送する過程は、次のように進む。まず、オーバーフロールーティング層（この場合、局所ルーティング領域Ｃ１の縦方向ルーティング層）のオーバーフローは、１の値だけ減分される。次に、水平方向の経路は、局所ルーティング領域Ｃ１を通じて、局所ルーティング領域Ｂ１の水平方向ルーティング層に到達するように使用される。したがって、局所ルーティング領域Ｃ１の水平方向ルーティング層のオーバーフローは、１の値だけ増分される。最後に、局所ルーティング領域Ｂ１の水平方向ルーティング層は、ｎ＝３の値だけ増分されて、縦方向のルートに対応し、転送を完了する。
【００６４】
図６Ｄは、局所ルーティング領域Ｃ１の縦方向ルーティング層と、局所ルーティング領域Ｂ１の水平方向ルーティング層との間の調整された経路を表す迷路６００を示す。具体的には、局所ルーティング領域Ｃ１の縦方向ルーティング層内のルート（破線で図示）は、局所ルーティング領域Ｃ１を交差する水平方向ルーティング層を通じてルーティングされ（水平方向の直線で図示）、局所ルーティング領域Ｂ１の水平方向ルーティング層内の縦方向のルート（ルート６０４、縦方向の直線で図示）で終了する。局所ルーティング領域Ｃ１の縦方向ルーティング層からオーバーフロールートを転送する過程は、ルート６０４により図示されるように、局所ルーティング領域Ｂ１の水平方向ルーティング層の好ましくない方向に依存せざるを得ないことに注意されたい。
【００６５】
図７は、本発明の実施形態に従い、例示的なルーティング可能性推定ディスプレイ７００を示す。ルーティング可能性推定ディスプレイ７００は、フロアプランディスプレイ７０２と、オーバーフローインジケータ７０４と、ルーティング可能性推定７０６と、を含む。フロアプランディスプレイ７０２は、ルーティングされるフロアプランを示し、このディスプレイ上には、０を超えるオーバーフローを有する局所ルーティング領域に関連する、フロアプランの配置上のいくつかのオーバーフローインジケータ７０４を含む。ルーティング可能性推定ディスプレイ７００は、ルーティング可能性推定７０６も表示し、これは、詳細ルーティング過程がフロアプラン上で実施された後、設計規則検証（ＤＲＣ）によって発生するであろう、いくつかの違反の予測である。
【００６６】
図８は、本発明の実施形態に従い、グローバルルーティング可能性推定を計算するための過程を示すフローチャートを示す。システムは、方向ｄにおけるｋのオーバーフロールートに関連するオーバーフロー局所ルーティング領域を選択することによって開始する（操作８０２）。次に、システムは、方向ｄにおけるＣ＞ｋのルートの過剰容量に関連する受信局所ルーティング領域を選択する（操作８０４）。システムは、オーバーフロー局所ルーティング領域から、受信局所ルーティング領域へ、オーバーフロー値を転送することによって、継続する（操作８０６）。システムが、オーバーフロー局所ルーティング領域から、オーバーフロー値を転送するステップを完了した後、システムは、グローバルオーバーフローコストおよび隣接するオーバーフローコストの関数として、グローバルルーティング可能性推定を計算する（操作８０８）。グローバルオーバーフローコストは、迷路の全局所ルーティング領域の全層にわたるルートオーバーフロー値に関連付けられる。隣接するオーバーフローコストは、迷路全体の、オーバーフロー局所ルーティング領域のクラスタあたりのルートオーバーフローの数、およびそれぞれのクラスタのサイズに関連付けられる。
【００６７】
図９は、本発明の実施形態に従い、図８の操作８０４時に拡大する、方向ｄにおけるＣ＞ｋのルートの過剰容量を有する、受信局所ルーティング領域を選択するための過程を示すフローチャートを示す。システムは、オーバーフロー局所ルーティング領域に最近接である、好ましい方向ｄを伴うルーティング層内のＣ＞ｋのルートの過剰容量に関連する局所ルーティング領域を検索することによって、開始する（操作９０２）。次に、システムは、局所ルーティング領域が見出されたかどうかを決定する（操作９０４）。操作９０２によって、局所ルーティング領域が見出された場合、システムは、変数Ｃを値ｋに設定し（操作９０５）、操作９１０に進んで、局所ルーティング領域を選択する。そうでなければ、システムは、オーバーフロー局所ルーティング領域に最近接である、好ましい方向
【００６８】
【化１０】
0005403834.tif 000014
を伴うルーティング層のＣ＞ｎ＊ｋのルートの過剰容量に関連する局所ルーティング領域のための第２の検索を実施し（操作９０６）、ｎは事前に決定された好ましくない方向の因数である。システムは、ここでも、局所ルーティング領域が見出されたかどうかを決定する（操作９０８）。操作９０６によって、局所ルーティング領域が見出された場合、システムは、変数Ｃをｎ＊ｋに設定し（操作９０９）、局所ルーティング領域を選択する（操作９１０）。そうでなければ、システムは、検索の失敗を報告する（操作９１２）。
【００６９】
操作９０２または操作９０６のいずれかによって実施される検索は、オーバーフロー局所ルーティング領域から、ｋ以上のルートの過剰容量を有するいくつかの隣接する局所ルーティング領域を通って、選択された局所ルーティング領域の受信ルーティング層まで経路が存在する時、受信局所ルーティング領域として、局所ルーティング領域を選択するだけであることに注意されたい。
【００７０】
図１０は、本発明の実施形態に従い、オーバーフロー局所ルーティング領域から、図８の操作８０６時に拡大する、受信局所ルーティング領域へ、オーバーフロー値Ｃを転送するための過程を示すフローチャートを示す。システムは、オーバーフロールーティング領域のオーバーフロールーティング層から、オーバーフロー値ｋを減算することによって、開始する（操作１００２）。次に、システムは、オーバーフロー局所ルーティング領域と受信局所ルーティング領域との間の隣接する局所ルーティング領域に、オーバーフロー値ｋを加算する（操作１００４）。最後に、システムは、受信局所ルーティング領域の受信層に、オーバーフロー値Ｃを加算する（操作１００６）。
【００７１】
方向ｄが受信ルーティング層の好ましい方向に関連する場合、Ｃはｋに設定され、方向ｄが受信ルーティング層の好ましくない方向に関連する場合、Ｃはｎ＊ｋに設定されることに注意されたい。また、操作１００４において、隣接する局所ルーティング領域を通る水平方向の転送は、隣接する局所ルーティング領域の水平方向ルーティング層に値ｋを加算することにも注意されたい。同様に、隣接する局所ルーティング領域を通る縦方向の転送は、隣接する局所ルーティング領域の縦方向ルーティング層に値ｋを加算することにも注意されたい。
【００７２】
図１１は、本発明の実施形態に従い、図８の操作８０８時に拡大する、グローバルルーティング可能性推定を計算するための過程を示すフローチャートを示す。システムは、全局所ルーティング領域の全層ｉにわたるオーバーフローの和の関数ｆとして、グローバルオーバーフローコストを計算することによって、開始する（操作１１０２）。
【００７３】
【数４】
0005403834.tif 000015
システムは、ルートオーバーフローを有する隣接する局所ルーティング領域のいくつかのクラスタｊにわたるコストの和として、隣接するオーバーフローコストを計算することによって継続し、クラスタのコストｇは、クラスタ内の局所ルーティング領域の数およびクラスタ全体のオーバーフローの和の関数である（操作１１０４）。
【００７４】
【数５】
0005403834.tif 000016
最後に、システムは、グローバルオーバーフローコストおよび隣接するオーバーフローコストの関数ｈとして、一群の局所ルーティング領域にわたるグローバルルーティング可能性推定を計算する（操作１１０６）。
【００７５】
【数６】
0005403834.tif 000017
本発明の一実施形態において、関数ｈは、一次演算である。本実施形態の変形において、関数ｈは、加算演算である。本発明の実施形態は、関数ｆ、ｇ、およびｈによって実施される計算を適合することによって、多様な回路構造および組立技術のためのグローバルルーティング可能性推定計算を調整することができる。
【００７６】
本願明細書は、例えば、以下の項目も提供する。
（項目１）
回路レイアウトに関連する一群の局所ルーティング領域にわたるルーティング可能性推定を計算するための方法であって、
ルートオーバーフローに関連する第１の局所ルーティング領域を選択することであって、それぞれの局所ルーティング領域は、該回路レイアウトの領域内のルーティング層に対するいくつかのルートオーバーフローの推定に関連付けられ、それぞれのルーティング層は、好ましい方向Ｄに関連付けられ、Ｒ個のルートのオーバーフローまたはＣ個のルートの過剰能力のいずれかに関連付けられる、ことと、
方向ｄにおけるｋ以上のルートのオーバーフローに関連する、該第１の局所ルーティング領域のオーバーフロールーティング層から、第２の局所ルーティング領域へ、オーバーフロー値ｋを転送することと、
グローバルオーバーフローコストおよび隣接するオーバーフローコストの関数として、グローバルルーティング可能性推定を計算することと
を含む、方法。
（項目２）
前記方向ｄにおけるｋ以上のルートのオーバーフローに関連する前記第１の局所ルーティング領域のオーバーフロールーティング層から、第２の局所ルーティング領域へ、オーバーフロー値ｋを転送することは、
前記好ましい方向ｄにおける少なくともＣ＝ｋのルートの過剰容量に関連する受信ルーティング層を備える、第２の局所ルーティング領域について第１の検索を実施することと、
該第１の検索が成功しない場合、好ましくない方向
【化１１】
0005403834.tif 000018
における少なくともＣ＝ｎ＊ｋの過剰容量に関連する受信ルーティング層を備える、第２の局所ルーティング領域について第２の検索を実施することであって、ｎは、ルーティング層の前記好ましくない方向におけるルートに対応するように使用される、いくつかのトラックを表す、好ましくない方向の因数である、ことと、
該第２の局所ルーティング領域が見出された場合、前記オーバーフロー値Ｃを該第２の局所ルーティング領域の受信層に転送することと
を含み、該好ましくない方向
【化１２】
0005403834.tif 000019
は、好ましい方向ｄに直交する、項目１に記載の方法。
（項目３）
前記第２の局所ルーティング領域を検索することは、前記好ましいルーティング方向を使用する層上のｋ以上のルートの過剰容量に関連する、いくつかの隣接する局所ルーティング領域を通って、前記第１の局所領域から前記第２の局所領域まで経路が存在することを確認することを含む、項目２に記載の方法。
（項目４）
前記オーバーフロー値Ｃを、前記第２の局所ルーティング領域の前記受信層に転送することは、
前記第１の局所ルーティング領域の前記オーバーフロールーティング層からｋオーバーフロー値を減算することと、
前記第１の局所ルーティング領域と前記第２の局所ルーティング領域との間の、前記隣接する局所ルーティング領域の前記好ましいルーティング方向層に、ｋオーバーフロー値を加算することと、
前記第２の局所ルーティング領域の前記受信ルーティング層に、Ｃオーバーフロー値を加算することと
を含む、項目３に記載の方法。
（項目５）
一群の局所ルーティング領域にわたる前記グローバルオーバーフローコストを計算することは、全局所ルーティング領域の全層ｉにわたるオーバーフローの和の関数ｆとして、前記コストを計算する
【数７】
0005403834.tif 000020
ことを含む、項目１に記載の方法。
（項目６）
前記隣接するオーバーフローコストを計算することは、ルートオーバーフローを伴う、隣接する局所ルーティング領域のいくつかのクラスタｊにわたる前記コストの和を計算することを含み、クラスタのコストｇは、該クラスタ内の局所ルーティング領域の数および該クラスタにわたる前記オーバーフローの和の関数
【数８】
0005403834.tif 000021
である、項目１に記載の方法。
（項目７）
局所ルーティング領域は、対応する方向Ｄ＝ｄを伴う、第１のルーティング層におけるオーバーフローおよび過剰容量の推定に関連し、かつ、対応する方向
【化１３】
0005403834.tif 000022
を伴う、第２のルーティング層におけるオーバーフローおよび過剰容量の推定に関連し、前記方向
【化１４】
0005403834.tif 000023
は、前記方向ｄに直交する、項目１に記載の方法。
（項目８）
局所ルーティング領域内の層でのオーバーフローの推定は、変数ＯＶの正の値によって表され、該局所ルーティング領域内の前記層での過剰容量の推定は、変数ＯＶの負の値によって表される、項目７に記載の方法。
（項目９）
命令を格納するコンピュータ読み取り可能格納媒体であって、該命令は、コンピュータによって実行されると、該コンピュータに、回路レイアウトに関連する一群の局所ルーティング領域にわたるルーティング可能性推定を計算するための方法を実施させ、該方法は、
ルートオーバーフローに関連する、第１の局所ルーティング領域を選択することであって、それぞれの局所ルーティング領域は、該回路レイアウトの領域内のルーティング層に対するいくつかの多数のルートオーバーフローの推定に関連付けられ、それぞれのルーティング層は、好ましい方向Ｄに関連付けられ、かつ、Ｒ個のルートのオーバーフロー、またはＣ個のルートの過剰能力のいずれかに関連付けられる、ことと、
方向ｄにおけるｋ以上のルートのオーバーフローに関連する、該第１の局所ルーティング領域のオーバーフロールーティング層から、第２の局所ルーティング領域へ、オーバーフロー値ｋを転送することと、
グローバルオーバーフローコストおよび隣接するオーバーフローコストの関数として、グローバルルーティング可能性推定を計算することと
を含む、コンピュータ読み取り可能格納媒体。
（項目１０）
前記方向ｄにおけるｋ以上のルートのオーバーフローに関連する、前記第１の局所ルーティング領域のオーバーフロールーティング層から、第２の局所ルーティング領域へ、オーバーフロー値ｋを転送することは、
前記好ましい方向ｄにおける少なくともＣ＝ｋのルートの過剰容量に関連する受信ルーティング層を備える、第２の局所ルーティング領域について第１の検索を実施することと、
前記第１の検索が成功しない場合、好ましくない方向
【化１５】
0005403834.tif 000024
における少なくともＣ＝ｎ＊ｋの過剰容量に関連する受信ルーティング層を備える、第２の局所ルーティング領域について第２の検索を実施することであって、ｎは、ルーティング層の好ましくない方向におけるルートに対応するように使用される、いくつかのトラックを表す、好ましくない方向の因数である、ことと、
前記第２の局所ルーティング領域が見出された場合、前記オーバーフロー値Ｃを前記第２の局所ルーティング領域の前記受信層に転送することと、
を含み、該好ましくない方向
【化１６】
0005403834.tif 000025
は、好ましい方向ｄに直交する、項目９に記載のコンピュータ読み取り可能格納媒体。
（項目１１）
前記第２の局所ルーティング領域を検索することは、前記好ましいルーティング方向を使用する層上のｋ以上のルートの過剰容量に関連する、いくつかの隣接する局所ルーティング領域を通って、前記第１の局所領域から前記第２の局所領域まで経路が存在することを確認することを含む、項目１０に記載のコンピュータ読み取り可能格納媒体。
（項目１２）
前記オーバーフロー値Ｃを、前記第２の局所ルーティング領域の前記受信層に転送することは、
前記第１の局所ルーティング領域の前記オーバーフロールーティング層からオーバーフロー値ｋを減算することと、
前記第１の局所ルーティング領域と前記第２の局所ルーティング領域との間の、前記隣接する局所ルーティング領域の前記好ましいルーティング方向層に、ｋオーバーフロー値を加算することと、
前記第２の局所ルーティング領域の前記受信ルーティング層に、Ｃオーバーフロー値を加算することと
を含む、項目１１に記載のコンピュータ読み取り可能格納媒体。
（項目１３）
一群の局所ルーティング領域にわたる前記グローバルオーバーフローコストを計算することは、全局所ルーティング領域の全層ｉにわたるオーバーフローの和の関数ｆとして、前記コストを計算する
【数９】
0005403834.tif 000026
ことを含む、項目９に記載のコンピュータ読み取り可能格納媒体。
（項目１４）
前記隣接するオーバーフローコストを計算することは、ルートオーバーフローを伴う、隣接する局所ルーティング領域のいくつかのクラスタｊにわたる前記コストの和を計算することを含み、クラスタのコストｇは、前記クラスタ内の局所ルーティング領域の数および前記クラスタにわたる前記オーバーフローの和の関数
【数１０】
0005403834.tif 000027
である、項目９に記載のコンピュータ読み取り可能格納媒体。
（項目１５）
局所ルーティング領域は、対応する方向Ｄ＝ｄを伴う、第１のルーティング層におけるオーバーフローおよび過剰容量の推定に関連し、かつ、対応する方向
【化１７】
0005403834.tif 000028
を伴う、第２のルーティング層におけるオーバーフローおよび過剰容量の推定に関連し、前記方向
【化１８】
0005403834.tif 000029
は、方向ｄに直交する、項目９に記載のコンピュータ読み取り可能格納媒体。
（項目１６）
局所ルーティング領域内の層でのオーバーフローの前記推定は、変数ＯＶの正の値によって表され、前記局所ルーティング領域内の前記層での過剰容量の前記推定は、変数ＯＶの負の値によって表される、項目１５に記載のコンピュータ読み取り可能格納媒体。
（項目１７）
回路レイアウトに関連する、一群のルーティング領域にわたるルーティング可能性推定を計算するための装置であって、
ルーティングオーバーフローに関連する、第１の局所ルーティング領域を選択するように構成される、選択機構であって、それぞれの局所ルーティング領域は、該回路レイアウトの領域内のルーティング層に対するいくつかのルートオーバーフローの推定に関連付けられ、それぞれのルーティング層は、好ましい方向Ｄに関連付けられ、かつ、Ｒのルートのオーバーフロー、またはＣのルートの過剰容量のいずれかに関連付けられる、選択機構と、
方向ｄにおけるｋ以上のルートのオーバーフローに関連する、該第１の局所ルーティング領域のオーバーフロールーティング層から、第２の局所ルーティング領域へ、オーバーフロー値ｋを転送するように構成される、転送機構と、
グローバルオーバーフローコストおよび隣接するオーバーフローコストとの関数として、グローバルルーティング可能性推定を計算するように構成される、計算機構と
を備える、装置。
（項目１８）
前記方向ｄにおけるｋ以上のルートのオーバーフローに関連する、前記第１の局所ルーティング領域のオーバーフロー配線層から、第２の局所ルーティング領域へ、オーバーフロー値ｋを転送している間に、前記転送機構は、
前記好ましい方向ｄにおける少なくともＣ＝ｋのルートの過剰容量に関連する受信ルーティング層を備える、第２の局所ルーティング領域について第１検索を実施し、
前記第１の検索が成功しない場合、好ましくない方向
【化１９】
0005403834.tif 000030
における少なくともＣ＝ｎ＊ｋの過剰容量に関連する受信ルーティング層を備える、第２の局所ルーティング領域について第２の検索を実施し、ｎは、ルーティング層の好ましくない方向におけるルートに対応するように使用される、いくつかのトラックを表す、好ましくない方向の因数であり、
前記第２の局所ルーティング領域が見出された場合、前記オーバーフロー値Ｃを前記第２の局所ルーティング領域の前記受信層に転送するように構成され、
前記好ましくない方向
【化２０】
0005403834.tif 000031
は、好ましい方向ｄに直交する、項目１７に記載の装置。
（項目１９）
前記第２の局所ルーティング領域を検索している間に、前記転送機構は、前記好ましい配線方向を使用する層上のｋ以上のルートの過剰容量に関連する、いくつかの隣接する局所ルーティング領域を通って、前記第１の局所領域から前記第２の局所領域まで経路が存在することを確認するように構成される、項目１８に記載の装置。
（項目２０）
前記オーバーフロー値Ｃを、前記第２の局所ルーティング領域の前記受信層に転送している間に、前記転送機構は、
前記第１の局所ルーティング領域の前記オーバーフロールーティング層からオーバーフロー値ｋを減算し、
前記第１の局所ルーティング領域と前記第２の局所ルーティング領域との間の、前記隣接する局所ルーティング領域の前記好ましい配線方向層に、オーバーフロー値ｋを加算し、
前記第２の局所ルーティング領域の前記受信配線層に、オーバーフロー値Ｃを加算するように構成される、項目１９に記載の装置。
（項目２１）
一群の局所ルーティング領域にわたる前記グローバルオーバーフローコストを計算している間に、前記計算機構は、全局所ルーティング領域の全層ｉにわたるオーバーフローの和の関数ｆとして、前記コストを計算する
【数１１】
0005403834.tif 000032
ように構成される、項目１７に記載の装置。
（項目２２）
前記隣接するオーバーフローコストを計算している間に、前記計算機構は、ルートオーバーフローを伴う、隣接する局所ルーティング領域のいくつかのクラスタｊにわたる前記コストの和を計算するように構成され、クラスタのコストｇは、前記クラスタ内の局所ルーティング領域の数および前記クラスタにわたる前記オーバーフローの和の関数
【数１２】
0005403834.tif 000033
である、項目１７に記載の装置。
（項目２３）
局所ルーティング領域は、対応する方向Ｄ＝ｄを伴う、第１のルーティング層におけるオーバーフローおよび過剰容量の推定に関連し、対応する方向
【化２１】
0005403834.tif 000034
を伴う、第２のルーティング層におけるオーバーフローおよび過剰容量の推定に関連し、前記方向
【化２２】
0005403834.tif 000035
は、方向ｄに直交する、項目１７に記載の装置。
（項目２４）
局所ルーティング領域内の層でのオーバーフローの前記推定は、変数ＯＶの正の値によって表され、前記局所ルーティング領域内の前記層での過剰容量の前記推定は、変数ＯＶの負の値によって表される、項目２３に記載の装置。
（項目２５）
前記選択機構は、詳細ルータの検索ウィンドウに関連する能力をエミュレートし、前記転送機構は、詳細ルータのルーティング能力をエミュレートする、項目１７に記載の装置。
本発明の実施形態の前述の説明は、図示および説明目的のためだけに提示されてきた。これらは、本発明を網羅する、または本発明を開示される形態に制限することは意図されない。したがって、実践する当業者に、多くの修正および変形が明らかとなるであろう。さらに、上記の開示は、本発明を制限することは意図されない。本発明の範囲は、添付の特許請求の範囲によって定義される。
【図１】
0005403834.tif 000054
【図２】
0005403834.tif 000055
【図３】
0005403834.tif 000056
【図４】
0005403834.tif 000057
【図５】
0005403834.tif 000058
【図６】
0005403834.tif 000059
【図７】
0005403834.tif 000060
【図８】
0005403834.tif 000061
【図９】
0005403834.tif 000062
【図１０】
0005403834.tif 000063
【図１１】
0005403834.tif 000064