JPH01320582A - ノードの相互接続方法 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 Ａ、産業上の利用分野 本発明はチップ上のノードを相互接続する方法を説明す
るものであり、詳細にいえば、任意のデバイスのノード
を相互接続する方法を説明するものである。詳細にいえ
ば、本発明はノードを相互接続すべきネットの出発帯域
を生成することを含むものである。出発帯域はネットの
ノードを相互接続するための全パスの部分集合であり、
２本以上の最短長パスを使用してネットの任意の２つの
ノードを接続できる場合に、冗長なパスを含んでいる。

次いで、パス空間に対する需要と供給を比較する関数で
ある評点が最も低い冗長パスが、冗長パスがなくなるま
で、順次除去される。

Ｂ、従来技術 大域配線、は回路チップの物理的設計にきわめて重要な
役割を果たすものであって、特定のトラックを指定せず
に、ワイヤのネットワークの概略の経路を生成するもの
である（下記参照）。その後、この配線に対して、トラ
ックの詳細な割当てが行なわれる。この２段階の方法は
、カード、基板及びその他のパッケージにも適用可能で
ある。

多くの大域配線プログラムを、これらがネットの再構成
に用いるアルゴリズムにおいて、「セグメント・ムーバ
」さして記述することができる。

ネットの経路を再指定するには、プログラムはまず、移
動の対象として、１つの特定のセグメント（「列」また
は「行」に沿って延びているワイヤの直線部分）を識別
する。通常、チップ上において、ワイヤのトラフィック
の経路は、１枚または複数枚のプレーンにおいては垂直
に、またほかのプレーンにおいては水平に指定される。

１列」という語は垂直方向の平行ワイヤ・チャネルの集
合体を規定し、「行」という語は水平方向の平行ワイヤ
・チャネルの集合体を規定するものである。

したがって、セグメントは移動される可能性のあるもの
として識別された後、ほかの平行な列または行に再配置
され、次いでワイヤのほかの部分が移動されたセグメン
トをネットのほかの部分に再接続するために、調節され
る。最後に、新しい構成を以前のものと比較し、１つだ
けが保存される。

ワイヤの接続に関連する調整は、比較的単純な態様で処
理される。このことは計算時間を短くしておくのに役立
つものであるが、ワイヤがきわめて長い、最適でない解
決策をもたらすものである。

ワイヤ・セグメントを移動して、よりよい経路を見出す
大域経路指定アルゴリズムは、成功しない多くの移動を
試みなければならない。１つのネットの１回だけの見直
しで、いくつかのセグメントのいくつのかの異なる位置
への再配置を考慮することがあるので、計算量はきわめ
て多くなる。工程の初期には、セグメントの満足のいく
再配置位置を見つけだすのはさほど困難ではない。しか
しながら、「余分の」配線空間が比較的少ない、設計工
程の終り近くでは、移動を成功させることはきわめて困
難となる。セグメント移動プログラムは評点が最も低い
（下記参照）多くの移動を試みなければ、受は入れられ
る評点を、最終的に発見することはできない。これらの
プログラムは、簡単な設計については迅速に回答を発見
するが、難しい設計の場合、計算時間はかなり多いもの
となる。

このようなセグメント・ムーバの１つが、第８回設計オ
ートメ−シロン・ワークショッフ会報（Ｐｒｏｃｅｅｄ
ｉｎｇｓ　ｏｆ　ｔｈｅ　Ｅｉｇｈｔｈ　Ｄｅｓｉｇｎ
　ＡｕｔｏｍａｔｉｏｎｌＪｏｒｋｓｈｏｐ　）、１９
７１年、ｐ１）、１５５−１６９のアキヒロ・ハシモト
（Ａｋｉｈｉｒｏ　Ｈａｓｈｉｍｏｔｏ）及びジェーム
ズ・ステイーブンス（ｂａｍｅｓ　５ｔｅｖｅｎｓ）に
よる「大アパーチャ内のチャネルの割当てを最適化する
ことによるワイヤの経路指定（ＷｉｒｅＲｏｕｔｉｎｇ
　ｂｙ　Ｏｐｔｉｍｉｚｉｎｇ　Ｃｈａｎｎｅｌ　Ａｓ
ｓｉｇｎｍｅｎｔｗｉｔｈｉｎ　Ｌａｒｇｅ　Ａｐｅｒ
ｔｕｒｅｓ）　Ｊという論文に記載されている。ハシモ
ト及びステイーブンスは数本の平行「チャネル」を含ん
でいる「空間」を定義しているが、この場合、各チャネ
ルが保持できるワイヤは１本だ＋ｊである。彼らは最初
、他のネットとの幅内を無視１．て（下記参照）、空間
の中心を通１７て、各ネットの最適な経路指定を行なっ
た。

次いで、問題となるすべての領域が除去されるまで、彼
らはセグメントを過密となっている空間から、過密では
ない近傍の空間へ移動させた。

入城経路指定のもう１つの一般的な手法は、メイズ・ラ
ンナ法によるものである。メイズ・ランナ・アルゴリズ
ム、は、少なくとも電子計算機に関するＩＲＥ会報（Ｉ
ＲＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎＥｌｅｅｔｒｏ
ｎｉｅ　Ｃｏｍｐｕｔｅｒｓ）　＋１１９６１年９月、
ｐｐ。

３４Ｆ３−３６５にＣ，Ｙ、　リー（１、ｅｅ）が「バ
ス接続のためのアルゴリズム、及びその応用（ΔｎΔＩ
ｇｏｒｉｔｈｍ　ｆｏｒ　Ｐａｔｈ　Ｃｏｎｎｅｃｔｉ
ｏｎｓ　ａｎｄ　ＩｔｓＡｐｐｌｉｃａｔｉｏｎ　）　
Ｊを発表してから、経路指定の問題に広く使用されてい
る。もう１つのメイズ・ランナ手法である、第６回設計
オートメーション・ソークシＦＪ　ツブ会報（Ｐｒｏｃ
ｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　ＳｉｘｔｈＤｅｓｉｇ
ｎ　Ａｕｔｏｍａｔｉｏｒ＋　１Ｊｏｒｋｓｈｏｐ）　
、ｐＩ）　、　　２５−４■のＲ，ｌ−、ノチコック（
Ｉｔ　ｉｌ；ｃｈｅｏｅｋ　）のｒ’、ｂル状配線及び
セル状モデリング手法（Ｃｅ　ｉ　ＩＩＩ　ｌａｒＷｉ
ｒｉｎｇ　ａｎｄ　Ｃｅ１ｌｕｌａｒ　）４ｏｄｅｌｉ
ｎｇＴｅｃｈｎｉｑｕｅ）　Ｊは１各セルが数本のワイ
ヤを含むことのできる直交セルのアレイにお１プるメイ
ズ・ラン＋を説明している。第１０回設計オートメ−シ
リン・ワークショップ会報（Ｐｒｏｃｅｅｄｉｎｇｓ　
ｏｆ　ｔｈｅ　Ｔｅｎｔｈ　ＤｅｓｉｇｎΔｕｔｏｍａ
ｔｉｏｎ　Ｗｏｒｋｓｈｏｐ）　Ｎ　Ｙ）　Ｉ）、４４
−４８．１９７３年のＪ、Ｃ，フォスタ（Ｆｏｓｔｅｒ
　）の「多層プリント配線バックブレーンのための経路
指定プログラム（Ａ　Ｒｏｕｔｅｒ　ｆｏｒ　Ｍｕｌｔ
ｉｌａｙｅｒ　Ｐｒ１ｎｔｅｄυｉｒｉｎｇ　Ｂａｅｋ
ｐｌａｎｅｓ）　Ｊは、数本のｌ・ラックのそれぞれの
チャネルを介して経路指定し、配線を名ブレーン上の弔
−の方向に制約し、バイア（下記参照）及びトラックの
両方を各接続部に利用できるようにするメイズ・ランナ
を記載している。「階層経路指定について（Ｏｎ　Ｈｉ
ｅｒａｒｃｈｉｃａｌＲｏｕｔｉｎｇ）　Ｊ　、ジャー
ナル・オブ・ディジタル・システムズ（ｂｏｕｒｎａｌ
　ｏｆ　Ｄｉｇｉｔａｌ　Ｓｙｓｔｅｍｓ）、Ｖｏｌ、
５、Ｎｏ、３．１９８１年９月、にＪ。

ソーカップ（Ｓｏｕｋｕｐ　）及びＪ、Ｃ，ｏイル（Ｒ
ｏｙｌｅ）が発表した「ルーズ・ルータ」など、入城配
線のためのメイズ・ランナの各種の改変形が開発されて
いる。

経路指定の主要な方法としてメイズ・ランナ・アルゴリ
ズムを使用した大域配線プログラムには、多くの問題が
ある。最大の問題は、多くのビンを有するネットの経路
指定が困難なことである。基本的なメイズ・ランナが扱
えるのは、２点間の接続だけである。ピンが３本以」二
のネットはいくつかの接続に分けなければならないが、
経路指定を開始する前に、ネットの最善の分解方法を見
出せないということである。第２の問題は解決策を網羅
的に探索しなければならないことであるが、これはメイ
ズ・ランナの利点の１つと考えられることがしばしばあ
るものである。網羅的な探索には、特に接続すべき点が
広く広がっている場合には、相当な時間がかかる。多く
のメイズ・ランナの改変形が、計算時間と記憶空間を節
約するためだけに導入されている。さらに、このアルゴ
リズムでは、多くのバイアがあり、ワイヤ長がイ」加さ
れたメンタの経゛路を導入するのが容易である。これら
のメンタ経路は作業の初期において、混雑評点を改善す
ると考えられるが、慎重に管理しない限り、作業の後期
において困難を引き起こすものである。

第３の問題はほとんどのメイズ・ランナの付加的な特性
である。すなわち、経路指定を行なオ）なければならな
い最初の結線には、競合する混雑が存在しないが、これ
は他の結線の経路指定が行なわれていないからである。

結線の経路指定が多くなるにしたがって、混雑が増加し
、付加的なネットの経路１旨定を行なう際に、重要な要
因となる。経路指定の対象となる最後の結線にはしばし
ば、競合するきわめて多くの混雑の問題が生じ、これは
複雑な設計を成功させることをほとんど不可能とするも
のである。この付加方法は、最後の結線を犠牲にして、
最初の結線を援助するものであるが、結線を整理して、
これらのすべてを経路指定できるようにする方法はない
。ネットの最初の経路指定を行ない、ネットの再経路指
定を行なう（メイズ・ランナ・プログラムがこれを行な
う場合）アルゴリズム１つだけでは、ノイズ・ランナ・
プログラムは限定されたものとなる。作業中に手順及び
評点パラメータを変更すると、この制限を軽減できるが
、完全に解決できるものではない。

チップのための大域配線プログラムをバーリントンのＩ
ＢＭバーリントンのチームが開発した。

このプログラムはＩＢＭテクニカル・レポートＴＲ１９
、０５２２（ＩＢＭ　Ｔｅｃｈｎｉｃａｌ　Ｒｅｐｏｒ
ｔ　ＴＲ１９，０５２２）のＪ、Ｂ、ヒクソン・ジュニ
ア（Ｈｉｃｋｓｏｎ、　Ｊｒ、）　、Ｐ、　Ｈ，バーゲ
ロン（Ｂｅｒｇｅｒｏｎ　）及びＪ、Ｗ、ソーノイルド
ソン（Ｔｈｏｒｖａ　１ｄｓｏｎ　）による「バーリン
トンの大域配線プログラム（Ｂｕｒｌｉｎｇｔｏｎ’ｓ
　Ｇｌｏｂａｌ　ＷｉｒｉｎｇＰｒｏｇｒａｍ）　Ｊ　
、１９８１年９月で説明されている。

大域配線方法の要約を含む、このチップの物理設計シス
テムの概要は、電子設計オートメーシ日ソに関するヨー
ロッパ会議会報（Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆｔｈｅ
　Ｅｕｒｏｐｅａｎ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｅ
ｌｅｃｔｒｏｎｉｃ　ＤｅｓｉｇｎＡｕｔｏｍａｔｉｏ
ｎ）　Ｊ　、ｐ１）　、　５４−５８．１９８１年９月
、のに、Ｗ、ラリア（Ｌａｌｌｉｅｒ）　、Ｊ　、　Ｂ
　。

ヒクソン・ジュニア、及びＲ，に、ジャクソン（ｂａｃ
ｋｓｏｎ　）による「ゲート・アレイ・チップの自動レ
イアウト・システム（Ａ　Ｓｙｓｔｅｍ　ｆｏｒΔｕｔ
ｏｍａｔｉｃ　Ｌａｙｏｕｔ　ｏｆ　Ｇａｔｅ　Ａｒｒ
ａｙ　Ｃｈｉｐｓ）　Ｊで発表されている。バーリント
ンで開発されたプログラムは、上記で概略を示した「セ
グメント・ムーバ」の概念に基づいたものである。電気
通信総合研究所会報（Ｒｅｖｉｅｗ　ｏｆ　ｔｈｅ　Ｅ
ｌｅｃｔｒｉｃａｌＣｏｍｍｕｎｉｃａｔｉｏｎ　Ｌａ
ｂｏｒａｔｏｒｉｅｓ）　）第２５巻１第５−６号、１
９７７年５−６月、に掲載された日本電気のヨシ・スギ
ャマ（Ｙｏｓｈｉ　Ｓｕｇｉｙａｍａ）　、カズヒロ・
ウエダ（Ｋａｚｕｈｉｒｏ　Ｕｅｄａ）　、ケンジ・カ
シ（Ｋｅｎｊｉ　Ｋａｎｉ）　、及びマサノリ・テラモ
ト（Ｍａｓａｎｏｒｉ　Ｔｅｒａｍｏｔｏ）の「マルチ
チップＬＳＩ経路指定プログラムＣＯＭ　Ｐ　Ａ　Ｓ　
（Ａ　Ｍｕｌｔｉｃｈｉｐ　ＬＳＩＲｏｕｔｉｎｇ　Ｐ
ｒｏｇｒａｍ　ＣＯＭＡＳ）　Ｊは、他の大域配線シス
テムを説明したものである。混雑の他に、このプログラ
ムはネット経路再指定を行なう場合の電気的特性による
長さの制約を考慮したものである。

再経路指定すべきネットは、混雑したチャネルを通るも
の、または長いネットのいずれかから選択される。

すべてのネットの経路指定を行なった後、ネットの経路
再指定を行なうには、配線構造を阻害することを余儀な
くされる。経路の再指定を続けると、領域に割り振られ
るワイヤの量は、利用できる配線空間の量ときわめて近
くなる。すべてのネットのワイヤは、段階的に「完成度
」、「滑らかさ」及び「精度」の面での品質が高まった
構造にまとめられる。この構造は部分的には「偶然」に
よるものであり、また部分的には個々の設計の特徴によ
るものである。構造が阻害された場合、あるいはプログ
ラムを若干条件を変えて再度実行した場合、偶然による
これらの構造面での態様は、きわめて異なったものにな
るであろうが、個々の設計に固有なものはほぼ同じもの
となろう。構造が完全なものになればなるほど、ネット
の移動を評価する既存のモードによる「トラフィック・
ジャム」または完全な停止が生じるまで、変更に対する
抵抗が高まり、１回も移動を行なえなくなる。

すべての大域配線の手順は適切な解決策をもたらせるよ
うに、この抵抗を解決するのに役立つ機能を含んでいな
ければならない。これらは「トラフィック・ジャム」機
構と呼ばれることがある。

（「自然選択による設計（Ｄｅｓｆｇｎ　ｂｙ　Ｎａｔ
ｕｒａｌＳｅｌｅｃｔｉｏｎ）　Ｊ　、Ｂ、ダンハム（
Ｄｕｎｈａｍ）　、Ｄ、フリッシャル（Ｆｒｉｄｓｈａ
１）　、Ｒ，フリッシャル（Ｆｒ　１ｄｓｈａ　Ｉ　）
及びＪ−Ｈ−ノース（Ｈｏｒｔｈ）　、Ｉ　８Ｍリサー
チ・レポートＲＣ−４７６（ＩＢＭＲｅｓｅａｒｃｈ　
Ｒｅｐｏｒｔ　ＲＣ−４７６）、１９６１年、参照。）
大域配線におけるネットの経路再指定の初期の段階で、
個々の問題の解決に必要な構造によって、その最善の形
態を発見できるように、偶然形成された構造を細分する
のは、避けられないところである。これらの初期の段階
に適したトラフィック・ジャム機構は、豆を一杯に入れ
たふるいを振って、豆を孔から落としてやることに類似
している。

ＩＢＭ社内では、数種類の大域配線プログラムが作成さ
れている。第１４回設計オートメーション会議会報（Ｐ
ｒｏｅｅｅｒｊｉｎｇｓ　ｏｆ　ｔｈｅ　Ｆｏｕｒｔｅ
ｅｎｔｌＩＤｅｓｉｇｎ　　Ａｕｔｏｍａｔｉｏｎ　　
Ｃｏｎｆｅｒｅｎｃｅ）　　Ｎ　　ｒｌ　　１）、　　
２　９　８　−３０２．１９７７年、のに、Ａ、チェノ
（Ｃｈｅｎ）、Ｍ、フォイア（Ｆｅｕｅｒ）　、Ｋ、　
Ｈ，コーカー二。

（Ｋｈｏｋｈａｎｉ）　、Ｎ、ナン（Ｒａｎ）及びＳ６
シユ、ミツ）　（Ｓｅｈｍｉｄｔ）による「チップ・レ
イアウトの問題：自動配線手順（Ｔｈｅ　Ｃｈｉｐ　Ｌ
ａｙｏｕｔ　Ｐｒｏｂｌｅｍ：　ＡｎＡｕｔｏｍａｔｉ
ｃ　Ｗｉｒｉｎｇ　Ｐｒｏｃｅｄｕｒｅ）　Ｊは大域配
線を説明したものであって、この自動配線プログラムが
１９７２年に完成したと述べている。このプログラムの
詳細な説明は、１９７４年７月２２日付けのＩＢＭテク
ニカル・レポートＴＲ２２，１７９ｆ３　（ＩＢＭ　Ｔ
ｅｃｈｎｉｃａｌ　Ｒｅｐｏｒｔ　ＴＲ２２，１７９６
）のクオ・アン・チェノ（Ｋｕｏ　Ａｎ　Ｃｈｅｒｔ）
の「配線可能度分析プログラムＩＩ　（ＷＡＰ　　ＴＩ
）　：基本アルゴリズム及びユーザの手引き（ＩＪｉｒ
ａｂｉｌｉｔｙ　ＡｎａｌｙｓｉｓＰｒｏｇｒａｍ　Ｉ
Ｉ　（ＷＡＰ　ＩＩ）：　Ｂａ５ｉｃ　Ａｌｇｏｒｉｔ
ｈｍ　ａｎｄＵｓｅｒ’ｓ　Ｇｕｉｄｅ）　Ｊに収めら
れている。後者のレポートにおいて、チェノはプログラ
ムの初期のバージョンがワイヤを移動させるものである
が、彼の新しいアルゴリズムはそうではない古述べてい
る。チェノは混雑を無視し、「スタイナ・ツリー」法に
よって、すべてのネットの最初の経路指定を行なった。

ネットの再構成は接続の対象となるレフタンブルの包囲
点を定義し、接続の対象となるすべての点を垂直及び水
平の両方向で貫通してレフタンブルを横切るワイヤを挿
入し、次いで必須の部分だけが残るようになるまで、ル
ープ中の最も費用のかさむ部分を除去する。チェノの方
法と本発明の以下の相違点はすべて本発明に有利なもの
であるから、本発明で提示される手法を使用して、はる
かに困難なワイヤの経路指定の問題を解決することがで
きる。（１）個々のネットの最初の経路指定において、
チェノは本発明が行なっているように、最初の領域構成
をもたらして、除去工程での将来の選択の幅を最大限の
ものとすることを行なっていない。（２）最初の領域構
成を重畳させておらス、シたがってセグメントごとに徐
々に除去していくことができない。（３）問題点を隔離
し、オーバーフローを除去するボックス法は、チェノの
手法の一部ではない。これらの相違は、チェノの方法で
の選択が早すぎるもので、かつ恣意的な態様で行なわれ
るものであって、これによりある意、味で望ましくない
、解決が困難な構造を構築することを意味している。ボ
ックス法（問題のある領域に対して新しい最大限の選択
の幅をもたらす）がないことは、構造に当初恣意的に構
築されたものの再調整を行なえる範囲がきわめて限定さ
れたものであることを意味する。

Ｃ０発明が解決しようとする問題点 本発明の目的は、冗長バスの除去による大域配線方法を
提供することである。

Ｄ１問題点を解決するための手段 本発明は多数のネットのノードを互いに接続する方法を
説明する。この方法はネットのおのおのに対して出発帯
域を生成することからなっている。

出発帯域は各ネットのノードを相互に接続するために使
用される任意のセットのバスであるが、任意の所定のネ
ットの任意の２つのノードを相互接続するために、２本
以上の最短の長さのバスを使用できる場合に、冗長なバ
スを含むものである。

本方法の次の段階は、上述の出発帯域によって作成され
たバス空間に対する累積需要を決定することである。次
いで、ネットが上記のものから選択され、多数の冗長バ
スが選択されたネットから選択される。次いで、上記で
求められた累積需要が、上記で選択された冗長バスが使
用する領域で利用できるバス空間の供給と比較される。

次いで、少なくとも上記の比較の関数である評点によっ
て、評点を決定する。次いで、上記で選択されたネット
に対する出発帯域から、冗長バスが削除される。

なお、この冗長バスは上記の選択されたバスのうち最も
評点が低いものである。この工程は、すべての冗長バス
が各ネットの出発帯域から除去されるまで、他のネット
及びバスの選択時にも繰り返される。この工程が繰り返
されるたびに、この工程を以前に反復したときに削除さ
れたバスを含めずに、累積需要が再計算される。最後に
、上記において、バス空間が得られるのに削除されなか
ったバスを使用して、各ネットのノードが互いに接続さ
れる。

しかしながら、上記の工程を使用して、すべての冗長パ
スが除去された場合、及びバス空間に対する需要が依然
供給を上回っている場合には、以下で説明する方法を使
用する。まず、バス空間に対する需要が供給を超えてい
る領域を選択する。

次いで、拡張帯域が各部分集合に対して生成される。次
に、部分集合とは、選択された領域内のネットの部分を
指し、選択された領域の残りのバスと周辺の交差部で点
として形成されたノードを含んでいる。残りのバスとい
う語は、上記で述べた冗長バスの削除後に残っているバ
スを指す。拡張帯域とは、各部分集合のノードを相互接
続するのに使用されたバスの集合であり、冗長パスを含
んでいる。次に、拡張帯域に対して選択された領域に必
要なバス空間に対する累積需要が決定される。

次いで、選択された領域で、部分集合が選択される。次
に、選択された部分集合に対する拡張帯域の多数の冗長
パスが選択される。次いで、バス空間に対する需要が、
選択された領域で利用できるバス空間の供給と比較され
る。次いで、上記で選択された冗長パスのおのおのに対
する評点が決定される。この評点は少なくとも、上述の
比較の関数である。次に、バスを選択された冗長パスか
ら削除する。なお、このバスは上記で決定された評点が
最も低いものである。この工程は、領域の拡張帯域のお
のおのに冗長パスがなくなるまで、繰り返される。バス
が削除されたとき、この工程を繰り返すたびに、バス空
間に対する累積需要を再計算しなければならないことを
忘れてはならない。

次に、ワイヤ空間に対する需要が供給を上回っている、
他の選択された領域に対して、上記の工程を繰り返す。

最後に、削除されない残っているバスにバス空間が利用
できる場合に、各ネットのノードを削除されないバスと
接続する。

Ｅ５実施例 チップ、カード、または基板の論理設計においては、い
くつかの回路ノードを中間ワイヤによって、互いに接続
する必要がある。１つの回路のノードが第２の回路のノ
ードに、また第３の回路のノードに連結される。他のノ
ードが上述の３つのノードに接続されないものと仮定す
ると、３点の「ネット」が論理的に指定される。性能の
要件以外に、チップの論理ステートメントは使用すべき
各種゛の回路タイプ、たとえば２３０の３ウェイＯＲ，
５６０の４ウエイＡＮＤなどをすべて指定するものであ
る。個々の回路のそれぞれには、独自の名前または番号
、ならびに必要なすべての固有なノードの結線、すなわ
ちネットの詳細なリストが与えられる。

物理設計は物理的レイアウトのための青写真であって、
すべての基本回路が正確に配置され（この工程を「プレ
ースメント」と呼ぶ）、また必要なすべてのネットの結
線が正確に配置される（この工程を「ワイヤ経路指定」
と呼ぶ）。「プレースメント」及び「ワイヤ経路指定」
はすべて、使用されるテクノロジに適用されるいわゆる
「基本原則」にしたがって行なわれる。

たとえば、特定のテクノロジにおける所定の配線プレー
ンには、平行なワイヤの間の最短距離が常に指定される
。

ワイヤ経路指定は通常、次の２段階の工程に分割される
。１）「大域配線経路指定」と、２）「精密埋込み」で
ある。大域配線経路指定はある配線プレーンから他のも
のへの個々のトラック、または個々の転移点を指定せず
に、すべてのネットに対する概略の経路指定を行なうも
のである。

精密埋込みは正確な物理位置を、あらゆるワイヤ及び中
間転移ノードに与えるものである。

本明細書記載の本発明は、大域配線経路指定の新規の方
法であって、チップ、カード、及び基板のほとんどすべ
ての物理設計の基本となるものである。

本発明の好ましい実施例をチップの配線に関して説明す
るが、本発明が他の用途、たとえば電話ネットワーク、
パイプライン・ネットワークの設定、あるいは代替バス
を使用して、多数のノードの相互接続を行なえるあらゆ
る場合に適用できることがわかろう。

第１図には、回路チップ１０が示されており、これは列
Ｃ１ないしＣ１５及び行Ｒ」ないしＲ１５に分割され′
Ｃいるので、各行が数本の水平ワイヤに対するワイヤ空
間を有し、名列が数本の垂直ワイヤに対するワイ（−空
間をイｆしている。より一般的な用途においては、ワイ
ヤ空間の等刷物を「バス空間」と呼ぶ。一般に、列が１
枚また（ｉ複数枚のブレーン内にあるのに対し、行はチ
ップの他のブレーン内にある。バスをあるブレーンから
他のブレーンに経路指定するには、列を行に相互接続す
るのにバイアが使用される。第２図はトラック１；３を
打する行Ｒｎ（１≦ｎ≦！５）または列Ｃｒ１（１≦ｎ
≦１５）の拡大図であって、これに対して個々のワイヤ
が最終的に割り当てられる。

列七行の交差部を「セル」と呼ぶ（第１図の３５参照）
。各セルは回路全体、回路の一部、あるいはいくつかの
回路の部分を含むことができる。入城配線が始まる前に
、すべての回路の位置が判明する。本発明の理解を容易
とするために、ネットという語を、本実施例においては
、導電バスによって互いに接続される点の集合であると
定義する。

ネット・はノードを相互接続するために使用されるセグ
メントまたはバスを含むこともできる。ネットの入城配
線は、ネットの点（下記参照）を含んでいるすべてのセ
ルを、ワイヤの共通ネットワークに接続することからな
っている。ワイヤは正確なトラックの割当てを決定せず
に、列と行に沿って配置される。入城配線の最終結果で
は、任意の列または行の任意の点に割り当てられたワイ
ヤが、適合するもの以」二であってはならない。

配線領域のこのモデル（第１図）はきわめて融通性が高
いものである。たとえば、すべての列及び行が同じ容量
を持っている必要はない。縁部の列及び行は、たとえば
、これらが入出力回路を含んでいる場合には、他の列及
び行とまったく異なっていてもかまわない。大城配線中
に容量を動的に変更できることは、可変幅配線ペイを有
しているある種のテクノロジには強力な設計手順となる
。

また、チップの全領域をＲＡＭ　（ランダム・アクセス
・メモリ）などの事前設計のものに専用とすることもで
きる。Ｒ，Ａ　Ｍにカバーされるセル内の配線空間のモ
デルは、必要げ応じ、ゼロに設定し、入城配線がこの領
域を通らないように経路指定することができる。モデル
は詳細な配線手法と合致し、入城配線の解決策を詳細な
配線プログラムが容易に処理できるものでなければなら
ない。

本発明の入城配線手順は、各ネットに対して出発「帯域
」を定義することから始まる。ネットの帯域は、このネ
ットに現在認められているすべての経路指定の和集合に
よって定義される。出発帯域は特定のネットのすべての
ノードを相互接続するための全セグメントの部分集合で
あって、この部分集合のすべてのセグメントは（１）除
去不能であって、問題のネットのあらゆる最小バスの一
部であるセグメントか、（２）除去可能で、すべてが問
題のネットの少なくとも１本の最小バスの一部であるが
、そのネットのあらゆる最小バスの一部ではないセグメ
ントのいずれかである。

最小バスという語は通常、最も長さの短いバスであるが
、最も好ましいバスを決定する際に、線の長さ以外の基
準が関与することが、当分野の技術者には明らかであろ
う。最小バスによって、取り組むあらゆる問題に対して
、最も好ましいバスを指す。好ましいバスは、たとえば
、最もコストのかからないバスである。出発帯域は通常
、認められているすべての最短の経路を含んでおり、平
行度を最小とし、かつ不必要なセグメントを排除する。

最短経路（最短バス）とは、対応するネットのノードを
相互接続するのに、長さが最も短いワイヤを使用するこ
とを意味する。最も短いもの以外のものを使用した場合
、バスは最短ではなくなる。認められるという語は、チ
ップ設計者が帯域に含めると決定した経路を指す。この
決定は予期される各種のオーバーフロー状態に基づいて
いなければならない。

「平行度」の概念を考察する。それぞれがレフタンブル
の角にある４つのノードを接続するものと想定する。こ
れら４つのノードを相互に接続するには、２つが平行な
３つのライン・セグメントが必要なことは明らかである
。もちろん、平行なセグメントが正方形でないレフタン
ブルの短い辺にあれば、ネットは短くなるであろう。同
じ垂直列にある２つのノードを接続するものと想定する
。

単純なライン・セグメントで充分であろう。頂部ノード
から水平に右に進み、底部ノードのレベ゛ルまで垂直に
下り、底部ノードに向かって水平に左へ進む迂回経路を
求める場合、平行な水平なラインの両方がネットの全長
に加えられるものとなる。

第３Ａ図はサンプルのネット、及びその出発帯域３０を
示している。円はネットの点（ノード）（３５）を表わ
し、各ライン（３６）は最終的な経路の一部として使用
されることのあるワイヤを表わす。したがって、第３Ａ
図は認められるすべての最短経路（パス）を示すもので
あって、これラバ点（ノード）３５を互いに接続するた
めに使用されるものである。最短の経路を使用するとい
うことは、不必要な平行度も不必要なセグメントもない
ことを意味する。ネットの再構成処理は（以下で説明す
る）主として減算的なものであって、出発帯域から始ま
り、各ネットに残される経路が１つだけになるまで、ネ
ットの帯域の削除が行なわれる。再構成段階の際の任意
の特定のネットの評価は、他のすべての重畳ネットの現
行の帯域を考慮するものである。特に混雑した点に集中
する方法を以下に説明する。

本発明の大域配線の最初の入力の１つは、各ネットに対
して接続しなければならない点またはセルのリストであ
る。本発明では、各ネットの出発帯域を作成する。きわ
めて単純なネットはその出発帯域として定義された最終
経路を有しており、これらの帯域の定義は変わらない。

ネットの点３５を相互接続する経路ないしパスの例が、
第３Ａ図に太い線で示されている。他に許容される経路
ないしパスのないこのパスが、第３Ｂ図の下部の３２と
いうボックスでより明確に示されている。第３Ｂ図には
、セグメント３４も示されている。これらのセグメント
はパスの一部であり、２つのノード、２つのバイア、ま
たは１つのノードと１つのバイアを互いに接続するため
に使用される。バイア３３も第３Ｂ図に示されている。

バイアはチップの異なるブレーンにあるセグメントを互
いに接続するのに使用される。３２という符号はセグメ
ントを示すのにも使用されているが、この符号は詳細に
いえば、除去不能なセグメントを示すものであって、こ
れが第３Ａ図のあらゆる最小バスの一部であるセグメン
トであることを意味している。

符号３４で示されている除去可能パスは、このセグメン
トが第３Ａ図の少なくとも１つの最小パスの一部である
ことを意味する。「経路指定」、「経路」及び「パス」
という語が、本明細書において互いに入れ替えて使用で
きることにも留意されたい。はとんどのネットはより多
くの可能性を含んでいる出発帯域を有しており、後の処
理では各ネットに対するこれらの経路指定の１つ以外が
省かれる。

ネットの２つの点は、これらの点が対向する角にあるレ
フタンブル（第３Ａ図の３７または３８参照）である出
発帯域、または、点が１つの列または行（第３Ａ図の３
９参照）にある場合には、単一のラインを有することが
できる。第３Ａ図の３０のように３つ以上の点を有する
ネットは、レフタンブルとラインを組み合わせたもので
あってもかまわない。「ハイブリッド帯域」という出発
帯域の特別な場合は、２つの辺（第４図の４５参照）が
最終経路の必須の部分であるが、他の２つの辺の間のパ
スには選択肢があるレフタンブルを有している。ハイブ
リッド帯域を第４図に示す。

以下の検討において、「レフタンブル」とは経路指定に
多くのオプションを有している正規の帯域を指し、ハイ
ブリッド帯域の例外事項は必ず注記されるものである。

各ネットの出発帯域は、ネットの点を接続する際に使用
できるすべての最短の経路の和集合であることが理想的
である。しかしながら、ネットによっては、すべての最
短経路が第４図に示すハイブリッド帯域におけるように
、認められる経路でないものもある。最短経路は完成し
た回路の性能に望ましいものである。最短経路は混雑の
問題もより迅速に解決する。ネット内の平行度を、各出
発帯域の作成時に最小限としなければならないが、場合
によっては、最短のものでない経路も可能である。しか
しながら、帯域が開始時に最小のものでない場合でも、
本発明で使用されるプログラムは適切に作動し、その最
終的な解決策として、最小構成を選択できる。

出発帯域の作成には、いくつかの任意の選択が必要であ
る。レフタンブルを決定するネットは水平及び垂直両方
の経路を有する出発帯域を画定するが、実際には、関連
する考慮事項によっては、いずれかの方向を選択するこ
ともできる。たとえば、チップによっては垂直チャネル
が、水平チャネルよりも少ないものもある。それ故、垂
直方向のオーバーフローを避けるために、苦労すること
になる。選択は長さ、予期される混雑、及びチップ上の
位置などの妥当な要因に基づくものである。

しかしながら、これらの出発帯域には常に若干の任意性
があるが、これは開始時には、どの選択がチップ全体の
設計に最善のものとなるかがわからないからである。選
択にはどの経路が出発帯域に認められるか、あるいは含
まれるかを決定することが含まれている。この任意性が
さほど有害でないのは、不完全な出発帯域の影響を後で
解決するさまざまな機会があるからである。

ネットに出発帯域を定義する際には、関連する要因を考
慮する。水平ブレーンでのトラフィックの方が速い場合
には、これに留意する。また、あるブレーンから他のブ
レーンへの必要な転移（バイア）にも留意する。垂直ラ
インの経路指定が行なわれるブレーンＡ上の２つのノー
ドが、レフタンブルの対向する角にあるものと想定する
。水平セグメント１つと垂直セグメント２つを必要とす
る最終的な解決策を考えた場合、導入されるバイアは２
つだけとなる。一方、垂直セグメント１つと水平セグメ
ント２つを必要とする解決策を求める場合には、４つの
バイアが必要となる。それ故、好ましい出発帯域の構成
は、代替手法のラインの長さがさほど長くない場合でも
、単純な水平ラインを含むすべての解決策を選択できる
ようにすることである。

「帯域ｊの例を挙げる。第５図には、５つの列（Ｃ６−
ＣＩＯ）、ならびに６つの行（Ｒ８−Ｒ１３）が示され
ている。ノード３５Ａは列Ｃ６、行ＲＩＯにある。ノー
ド〜３５Ｂは列Ｃ８、行Ｒ８にある。ノード３５Ｃは列
Ｃｌ０１行Ｒ１３にある。「帯域」は簡単にいえば、第
５図に示すようなものであって、各列及び各行にライン
が割り当てられ、３つのノードを接続するのに考えられ
るすべての経路を示している。本明細書で「出発帯域」
と呼んでいるものを得るために、帯域内の何本かのライ
ンを第８図に示すように除去する。

行Ｒ８及びＲ９は完全に除去され、行Ｒ１１、Ｒ１２及
びＲ１３は部分的に除去され、列Ｃ６、Ｃ７、及びＣ９
は完全に除去され、列ＣＩＯの一部が除去される。当分
野の技術者には、（列Ｃ９を除いて）除去された部分が
いずれも問題のネットの最小ワイヤ経路にないと思われ
ることが明らかであろう。第７図は他の「出発帯域」を
示したものである。

第７図は行Ｒ１１とＲ１２が全部除去されており、列Ｃ
９の一部が復元されている点で、第６図と異なっている
。当分野の技術者に明らかなとおり、第６図または第７
図はいずれも、第５図に示した「帯域」の「出発帯域」
として使用できるものである。第８図は「出発帯域」と
することのできる第３の帯域を示している。

この図では、第７図で除去された行Ｒ１１とＲ１２が復
元されている。したがって、当技術分野の技術者には、
「出発帯域」が最小解決策に入らないと思われるすべて
の列のライン及び行のラインを除去するものであること
が明らかであろう。

これらのすべての図においては、列Ｃ６及びＣ７、なら
びに行Ｒ８及びＲ９がなくなっている。少なくとも、行
Ｒ１１及びＲ１２の一部、ならびに行Ｃ９の一部が、第
６図、第７−及び第８図に示した３つの「出発帯域」と
考えられるものからなくなっている。

ワイヤの経路指定を行なうには、解決すべき問題に対し
て「出発帯域」となるものを、３つの候補から正確に選
択しなければならないことが、当分野の技術者には明ら
かとなろう。ある候補を他のものから選択することにな
る状況のいくつかの例を挙げる。

垂直方向の作業空間（すなわち、列方向の）が水平な行
よりもはるかに少ないチップで作業を行なっているもの
とする。この場合に選択できるのは、第７図に示した出
発帯域であるが、これは（「除去」工程の説明を行なう
場合に明らかとなるように）垂直面での選択の幅を最大
としようと考えるからである。しかしながら、配線に使
用できる領域の垂直及び水平方向での差が問題にはなら
ないが、あるプレーンから次のプレーンへの転移（いわ
ゆる「バイア」によって行なわれる）の数を少なくした
いと考えているものとする。３つのノード３５Ａ１３５
Ｂ及び３５Ｃが、「プレーン１」に直接到達しており、
これが垂直ラインが通っているプレーンでもあるものと
する。水平ラインは「プレーン２」を通る。「プレーン
ｌ」と「プレーン２」の間の接続には、各点で、「バイ
ア」が必要である。

第９図には、第７図または第８図からの「除去」（追っ
て検討する）によって行なわれる経路指定が示されてい
る。第９図は３つの円（行Ｒ１３と列Ｃ１０の交点、行
Ｒ１３と列Ｃ９の交点、及び行ＲＩＯと列Ｃ９の交点）
を示している。３つの円の各々は、図示のワイヤの経路
術′定を行なうために追加された「バイア」を示してい
る。第９図に示す経路は、当分野の技術者には明らかな
ように、第７図及び第８図に示した出発帯域から除去を
行なうことによって達成できるが、第６図のものでは達
成できない。それ故、出発帯域が第７図または第８図の
いずれかに示したものであれば、３個の追加バイアを必
要とする解が必要となる。

ただし、ここでの出発帯域は第６図に示すものであると
する。第１０図は第６図から達成できる経路を示してい
る。

第１０図は２つの円（行Ｒ１１と列Ｃ１０の交点にある
ものと、行Ｒ１１と列Ｃ８の交点にあるもの）を示して
いる。第１０図に示した経路指定に必要な追加のバイア
が２個だけであることが、明らかであろう。さらに、第
６図から得られる経路に３個以上の追加バイアが必要な
いのに対し、第９図に示す経路指定（第７図または第８
図に示した出発帯域のいずれかから達成される）には３
個の追加バイアが必要なことも明らかであろう。

問題のチップについて、バイアの総数を少なくすること
がきわめて有利な場合には、第６図に示す出発帯域を選
ぶことができる。

第６図に示す出発帯域を実際に選択したものとする。図
示のラインには（１）除去不能なものと、（２）除去可
能なものの２つのカテゴリがある。

列Ｃ６から列Ｃ８までの行ＲＩＯにあるセグメントは除
去不能であり、行Ｒ８から行Ｒ１０までの列Ｃ８にある
ものも除去不能である。図示の他のセグメントは、問題
のセグメントを省いても、経路指定が行なえるという意
味で、すべて除去可能である。

「除去」工程は、ネットを不連続なものとせずに、それ
以上セグメントを除去できないところまで、除去可能な
セグメントを除去することである。

本発明の除去工程独自の特徴は、これを行なう方法にあ
る。学習例として第６図に示す出発帯域を使用して、こ
の方法を説明する。

問題とな゛っているすべてのネットについて、出発帯域
が得られたものとする。すべての出発帯域のラインのす
べてが、すべての列及び行に存在しているものとする。

すべての出発帯域を「オーバーレー」したという。例と
して、列（Ｃ６−ＣＩＯ）の各々に対して、１０本の垂
直チャネルが利用でき、行（Ｒ８−Ｒ１３）の各々に対
して、１１本の水平チャネルが利用できるものとする。

オーバーレー工程がすべての出発帯域全体のすべてのワ
イヤに対して行なわれる。行と列の各交点を「レフタン
ブル」と呼ぶ。図示の領域に、６つの行と５つの列があ
るので、図示の例では３０個のレフタンブルがあること
になる。各レフタンブルについて、水平方向の需要と水
平方向の利用可能度の比較値、ならびに垂直方向の需要
と垂直方向の利用可能度の比較値の２つの値を計算する
ものとする。

行Ｒ１１と列Ｃ８を表わすレフタンブルは、１５本のワ
イヤに対する垂直方向の需要と、１８本のワイヤに対す
る水平方向の需要を有している。すナワチ、オーバーフ
ー工程で、垂直及び水平方向のワイヤがすべて追加され
た後、問題のボックスに当たるワイヤが、垂直方向には
１５本、水平方向には１８本存在する。垂直方向に１０
本、水平方向に１１本のワイヤのための空間しかないの
で、検ス；１しているレフタンブルには、垂直方向に５
、水平方向に７のオーバーフローが生じることが明らか
となろう。これを第１１図に示した構成で表わすものと
する。

オーバー１ノー工程の後、第６図に示す出発帯域に対す
る除去可能ラインを含んでいるボックスについて、第１
２図に示すオーバーフロー状況が生じたものとする。

頂部の水平ライン（行１３）を除去するか、あるいは底
部のライン（行Ｊ、０）を除去するかの決定をくださな
ければならないものとする。選択を評価するのに各種の
方法を使用できることが、当分野の技術者には明らかで
あろうが、例として、垂直または水平のオーバーフロー
のうち大きい方を少なくすることを考えるものとする。

列Ｃ９と行ＲＩＯの交点を表わすボックスが含んでいる
メーバーフローは１０である。そこで、列Ｃ８から列Ｃ
ＩＯまでの行ＲＩＯの水平セグメント、ならびに行ＲＩ
Ｏから行Ｒ，１１までの列ＣＩＯの垂直セグメントを除
去することにする。列Ｃ８から列Ｃ１０までの列Ｒｉ　
Ｏの水平なセグメント、及び行ＲＩＯから行Ｒ１１まで
の列ＣＩＯの垂直なセグメントを通るあらゆるバスが除
去されるが、これはこのようなバスの評点が、第１２図
の帯域のあらゆるバスのうちで最も低いからである。

行ＲＩＯの列Ｃ８から列ＣＩＯまでの３つのボックスの
左から右への評点は更新されて、■−６、Ｈ−３；Ｖ−
３、Ｈ−９；　Ｖ−１、Ｈ−５となる。

ただし、これは上述の除去を行なった後に残る評点であ
る。

ここで、問題となっているネットからしばらく離れ、他
のネットに対する他の出発帯域からの除去を行なう。除
去の計画を立てる何らかの妥当な方針によって、問題の
ネットに戻るものとする。

ラインが他のネットから除去されているのであるから、
ボックスの評点は低くなる。第１３図に示す状況に遭遇
したものとする。

行Ｒ１３の列Ｃ８からＣ１０までの水平セグメント、な
らびに列Ｃ８の行Ｒ１２からＲ，１３までの垂直セグメ
ントを除去するか、あるいは行Ｒ１１の列Ｃ８からＣ１
０までの水平セグメント、ならびに列Ｃ１０の行Ｒ１１
からＲ１２までの垂直セグメントを除去するかの選択を
、本発明のプログラムが指定するものとする。前述の最
大の単一オーバーフローの基準によって、行Ｒ１３と列
Ｃ８の交点を表わすボックス内の垂直オーバーフローは
、−５から−４に減少する。それ故、上述の２種類の除
去のうち前者を行なう。すなわち、行Ｒ１３の列Ｃ８か
らＣ１０までの垂直セグメント、及び列Ｃ８の行Ｒ１２
からＲ１３までの水平セグメントを除去する。

他のネットからセグメントを除去したと仮定して、最後
に、問題のネットに戻ってきた場合、第１４図に示した
状況に遭遇する。

行Ｒ１２と列Ｃ９の交点を表わすボックスに含まれるオ
ーバーフローが−１であるから、ここで、行Ｒ１２の列
Ｃ８から０１０までの水平セグメントと、列Ｃ８の行Ｒ
１１からＲ１２までの垂直セグメントを除去する。この
ネットには、第１０図に示す経路が残る。除去すべきセ
グメントの妥当な選択を行なうための方法を調整し、各
種の要望に適したものとできることは、当分野の技術者
にとって明らかなものであろうが、この検討は本発明の
範囲を超えるものである。条件によっては、たとえば、
垂直オーバーフローが水平のものよりも重大なものであ
ると考えられることなどがある。

また、内部の水平セグメントを除去してから、外部のも
のを除去することを選ぶこともできる。すなわち、行Ｒ
１２を除去してから、行Ｒ１３またはＲＩＯのいずれか
を除去することができるが、このようなプログラムの調
整はすべて本発明の範囲内のものである。

オーバーフローの状態を決定するにあたり、−般に、セ
ルの縁部のワイヤの交差を数えるが、セルの中心で数え
ることもできる。それぞれの場所において利用できる配
線空間の数は、入城配線を開始する前に決定される。す
べてのネットの最初の経路指定が行なわれると、これら
の点を通過するワイヤの本数が判明する。本発明では次
いで、利用できる空間（「供給」）を、通過するワイヤ
の本数（「需要」）と比較し、ワイヤの全体的な構成の
どこを修正しなければならないかを決定する。

すべてのネットに対して、出発帯域を定義してから、そ
の累積配線需要を決定する。帯域が単一の接続ワイヤか
らなっている場合、ワイヤが通過する大域セルの各々を
、このワイヤに充分な配線空間に対する需要について評
価する。帯域がレフタンブルで構成されている場合には
、レフタンブルを通って水平方向に平行に延びている数
本のワイヤと、レフタンブルを通って垂直方向に平行に
延びている数本のワイヤを、ネットが有しているかのよ
うにして、その帯域の需要を計算する。レフタンブル内
の大域セルの各々は、ネットのための垂直及び水平両方
のワイヤを含んでいる。はとんどのネットの帯域は、レ
フタンブルとワイヤ・セグメントの両方を含んでいるの
で、一方の影響を受けるセルの評点もあれば、他方の影
響を受けるものもある。場合によっては、上述したよう
に、「バイア」やバスの角を数えることも役に立つ。

設計のための混雑値を、各セルの供給値から需要値を差
し引くことによって生成できる。需要が供給を上回って
いる領域は負の結果を宵しており、オーバーフロー状態
を示す。垂直及び水平のオーバーフローを分析すること
によって、領域によっては１つのブレーンでのみ混雑を
生じることが明らかになった。混雑の測定値は設計者に
とって、大域配線工程を制御するのに役立つものであり
、またさまざまな処置を制御するため、プログラムによ
って内部で使用されるものである。以下の説明で、すべ
ての出発帯域にオーバーレーを行なった後の評点を示す
図を含め、完全な問題の解に関するコンピュータの実行
結果を示す。本発明のすべての基本的な特徴を示す。

評点方法の変形の１つは「確定」需要と「オプション」
需要を別個に処理するものである。すなわち、帯域内の
ワイヤの中には選択肢を持っておらず、したがってこれ
らの需要は「確定」しているといわれる。他のワイヤは
選択肢を持っており、「オプション」であるといわれる
。バス内のすべてのセルについてペナルティの重みを累
計する際にこれを考慮することによって、経路指定法で
もっと難しい混雑の問題に取り組めるようになる。選択
を行なった場合、オプションの需要のカウントが減り、
いくつかの確定需要のカウントが増加する。

「除去」工程 「除去」工程は各ネットに対して経路が１つだけ残るよ
うになるまで、ネットから余分なバスを除去するもので
ある。最初の評点が完了すると、多くの領域に激しい混
雑が生じることがある。これは−時的な状況に過ぎず、
また多くのネットが複数のバスを有しているのであるか
ら、若干人工的なものである。本発明は余分なバスを有
するネットを、おそらくはネットを通る各バスに対し異
なる順位を使用して、処理する。ネットの余分なバスと
は、最終的な経路指定で、最終的のどのバスを選択する
かということに関して、依然複数の選択を行なうことの
できるネットを指す。各ネットを調べて、その冗長バス
のうちどれが混雑の問題に最も寄与するかを明らかにし
、次いで、そのバスを除去する。２つ以上のバスの評点
が、同程度に低い場合には、どれを除去するかの決定が
延期されることがしばしばあり、したがって、他のネッ
トに関する決定が考慮されることになる。同様に、考え
られる経路指定が多くあって、きわめて融通性の高いネ
ットについてのすべての決定は、より制約が高いネット
がその最善のバスを選択するまで、延期されることにな
る。バスまたはバスの一部が除去された場合には、影響
を受けるセルの評点が更新される。

バス、またはバスの一部の評価は、バスに沿った各セル
のオーバーフロー状況を考慮しなければならない。需要
を供給から差し引くことによって、オー／＜−フローが
計算される。オーバーフローの値を累計するだけでは、
他のバスとの比較の良好な基盤をもたらされないので、
一連のペナルティ値、ないし重みが使用される。入城配
線中にさまざまな理由で、重みを変更できるが、通常、
オーバーフローがきわめて多い場合には、高いペナルテ
ィが、少ない場合には、低いペナルティが与えられ、供
給がほぼ適切な場合には、ペナルティはさらに低くなり
、供給が需要を大幅に上回っている場合には、何のペナ
ルティも与えられない。評点が付けられるのが特定のバ
スであるから、ネットの帯域がセルを通る垂直及び水平
両方向のバスを有していたとしても、セルを通るライン
に課されるペナルティは、その水平方向または垂直方向
のいずれかにおける寄与度に応じたものであって、両方
についてではない。バスに対する総合評点はバイア及び
その他の要因についてのペナルティを含むことができる
。バスに与えられる総合評点は、他のバスの評点と直接
比較できるものであるから、最も低い評点を簡単に識別
できる。

ペナルティの加重計算を最小限とし、帯域定義データを
単純化する除去力法の変形の１つを、以下で説明する。

矩形の各帯域の出発帯域は、垂直または水平方向の両方
にではなく、一方のみに平行なワイヤを含んでいる（下
記の［水平／垂直方向のバイアス」参照）。除去で評点
が付けられるのは端部（上端及び下端、または左端と右
端）にある平行バスだけであるから、バスを除去すると
、レフタンブルは小さくなる。これは一連の操作でレフ
タンブルを細分することのある手法よりもプログラムが
はるかに容易なものであり、またより高速に実行できる
。ハイブリッド帯域の中間から最小バスを除去しても、
帯域が通常のレフタンブルと同じように細分されないの
は、ハイブリッド帯域の辺の２つが最終構成で保持され
なければならないからである。ハイブリッド帯域は考慮
されるすべての可能性を容易に有することができ、帯域
を横切る余分な平行バスは、ブックキーピングをさほど
複雑とせずに、除去される。

最初の除去工程後に残る経路が、最終的な配線の解を満
たすこともある。これが回路の性能がら考えて理想的な
ものであるのは、すべての経路が最短のものとなるから
である。しかしながら、あらゆる複雑な設計で、これを
期待することはできない。このようになったとすれば、
おそらく余分な配線空間があるからであり、設計は非常
に容易となる。最初の除去が「簡単な」混雑の問題を処
理し、解決するのには何らかのネットへのワイヤの長さ
を長くする以外にない「難しい」混雑の問題を、チップ
」二の他の部分に残すものと考えられる。

ネットのすべての領域において、ネットのすべてについ
ての最初の除去手順が完了すると、本発明の重点は、他
のオーバーフローの領域を直接取り上げることに移る。

これはネットの帯域のいくつかを再作成しく以下で説明
する）、次いで除去手順を再度使用して、これらのネッ
トに対する新しい経路を見つけだすことを含んでいる。

「ボックスむ刑１−９−個月 本発明には設計上の問題点に集中する優れた能力がある
。「ボックス」を隣接したセルの任意の集合を中心とし
て作成することができ、これが通常は、問題の領域を中
心としてレフタンブルを作成する。ボックスは重要なオ
ーバーフローを１つ、いくつかのオーバーフロー、ある
いはその他の任意の需要と供給の状況を含むことができ
る。ボックス内の領域が、再経路指定が行なわれる場所
である。再経路指定を容易とするために含められる間ぶ
のないセルの数に応じて、ボックスを「太き（」も、「
小さく」もできる。ボックスを使用して小さな領域に集
中することは、プログラムが行なわなければならない作
業の量を限定し、これは実行時間を短くするのに役立つ
。ボックスはきわめて強力で、柔軟性のある概念であり
、さまざまな用途がある。

ボックス外の領域にある帯域は一定に保たれ、変更され
ない。対象となる領域を分離することにより、完全にボ
ックス内にある拡張帯域の新しいセットが作成でき、か
つボックスによって獲得されたオーバーフローを直接対
象として、新たな除去工程を行なうことができる。これ
は変更が外部の領域に影響を及ぼさないことを確実とす
るものである。ボックスの手法を使用して、混雑の問題
を２つの近傍の場所の間のものだけに限定することがで
き、また解決工程を定常的に前進させるととができる。

ボックスが定義されると、このボックスの領域を通過す
るすべてのネットを、再経路指定に考えられる候補とし
て識別することができるようになる。再経路指定の初期
の段階で最も適切な変形の１つは、オーバーフローに直
接寄与するネットだけを識別することである。上述の出
発帯域の作成と同様な、ただしボックス内の部分だけに
作用する手順で、これらのすべてのネットに対して、内
部拡張帯域を作成する。ワイヤが帯域に入る部分はネッ
トの一次接続点となるから、ボックス内のあらゆる再経
路指定はボックス外の配線との接続を、ボックス外の配
線の変更を必要とせずに、保つことになる。ボックス内
に作成された拡張帯域は通常、問題のネットの当初の帯
域の構成とは異なっており、通常付加的なバスを考慮す
ることを認めるものである。このような拡張帯域がすべ
て作成されると、プログラムは総需要を再計算し、除去
手順を行なって、ボックス内の新しい経路を見つけだす
。

最初の除去の直後に作成され、初期に定義されるボック
スは一般に小さいものであるから、最小限のワイヤの追
加、及び最小限の付加的な計算によって、問題を解決す
ることができる。小さなボックスでは解決が困難な問題
は、その後大きなボックスによって処理される。大きな
ボックスはより広範にわたる再経路指定を可能とするの
で、難しい問題を解決することができる。必要な場合を
除き、大きなボックスが使用されないのは、これが多く
の計算を必要とし、かつワイヤの長さを長くする傾向が
あるからである。

水平／垂直　向のバイアス 追加ワイヤをあまり多くせずに問題を解決し、かつ屈曲
が多い片巻きバスを回避するために、帯域の作成では、
再経路指定を故意に制約する。追加ワイヤとはネットの
非最短経路を指す。制約が工程の初期の段階で有用なの
は、導入するワイヤが多すぎると、後で改善するのが困
難になるからである。問題のある領域の中には水平プレ
ーンのみに、あるいは垂直プレーンのみにオーバーフロ
”−を含んでいるものがある。このような場合には、１
つのプレーンのみに力を傾注するのが、きわめて効果的
である。１つのボックスの内部では、たとえば、多数の
平行なワイヤを有しているが、垂直なワイヤが縁部に沿
った２本だけである矩形の帯域を作成できる。これは水
平のオーバーフローの問題を解くのに適したものである
。他のプレーンに力を置くと、同じレフタンブルが垂直
方向には多数のワイヤを有し、水平方向には頂部と底部
とだけにワイヤを有するようになる。

ボックスの中には、両方のプレーンにオーバーフローの
問題を存しているものがある。これらの問題を再経路指
定を制約して解くことも、長い片巻きバスを避けるのに
役立つものである。まず、ボックスが水平な平行度に集
中し、次いで垂直の平行度に集中するという一連の操作
を実行することができる。他の手法は、ボックス内の新
しい帯域のいくつかに水平な平行度を与え、他のものに
垂直な平行度を与えるというものである。

帯域の拡張 経路指定が進行すると、問題領域の中に、特に問題があ
るものがあることが判明する。これらの領域においては
、一般に最短バスのみを含んでいる正規の帯域の生成よ
りも多くの、再経路指定の可能性をもたらすことによっ
て、オーバーフローを解決できることがある。この場合
、拡張帯域はレフタンブルを単に拡張しただけのものを
含むこともあれば、ラインをレフタンブルに変形したも
のを含むこともある。帯域の拡張量を選択し、ボックス
のサイズ、水平または垂直方向のバイア、問題解決の段
階、チップの位置、及びその他の要因に合致させること
ができる。

周辺のゼロの処理 場合によっては、オーバーフローがゼロ（供給マイナス
需要＝０）で包囲されているので、小さなボックス内で
再経路指定を成功させるのが不可能なことがある。これ
らの場合には、ボックスの縁部において周辺のゼロを処
理し、オーバーフローを防ぐ経路の再指定を行なうため
の余地を作ることが必要となる。これは、ボックスを追
加ワイヤのための余裕を持っているいくつかのセルを含
むのに充分な大きさとし、かつゼロに寄与するネット及
びオーバーフローに寄与するネットとに対して帯域を再
設定することによって行なわれる。

尖青貝 本発明の概念は、チップの設計に利用されているコンピ
ュータ・ソフトウェアで実施されている。

ここで、複雑で、きわめて難しいチップの設計に対して
、大域ワイヤ経路指定を解決するために使用される、一
連の完全な操作を説明する。実際のコンピュータの印刷
出力が、以下のさまざまな図面の基礎となっている。第
１５図には、各垂直列に利用できるワイヤ空間が示され
ている。たとえば、列２７には１９本のワイヤに充分な
ワイヤ空間がある（５０参照）。第１６図には、各水平
行に利用できるワイヤ空間が示されており、そのほとん
どは２２本のワイヤ（′：：充分な空間ｋ　ｆｆ　Ｌ−
７−いる（６０参照）。この問題の場合、３４Ｘ３４の
セルのアレイを使用する。第１７図には、ネットのすべ
ての当初の出発帯域にオーバーレーを行なった後の垂直
オーバーフローが示されている。第１８図には、ノット
の当初の出発大域にオーバー１ノーを行なった後の水平
オーバーフローが示されている。水平オーバーフローが
垂直のものよりもはるかに多いのは、出発帯域の構成が
水平方向での選択の幅を最大とし、ネットの大多数に必
要なバイアの数を最小としようとしているからである（
以下で説明する）。第１９図には、除去工程後の垂直オ
ーバーフローが示されている。第２０図には、除去工程
後の水平オーバーフローが示されている。

解のこの段階で、水平オーバーフローが垂直オーバーフ
ローよりもかなり少ないのは、上述のように、ネットの
出発帯域の形成時に水平側が重視されたからである。第
２１図には、コンピュータによって生成された、オーバ
ーフローを包囲するボックスのいくつかが示されている
。さまざまな数字（たとえば、３６．４Ｂ、７９など）
は問題のボックスの名前の役目を果たし、その内部のセ
ルの位置を識別している。第２２図には、ボックスの内
部に拡張帯域を形成したことによって作成された垂直オ
ーバーフローが示されている。第２３図には、ボックス
内部の拡張帯域によって生じた水平オーバーフローが示
されている。当初の除去工程後の垂直オーバーフローが
、水平オーバーフローよりもはるかに多いので、プログ
ラムはボックス内部で行なわれる除去に関し、垂直方向
の選択肢を最大のものとする。第２４図には、ボックス
内部での除去後の垂直オーバーフローが示されている。

図示のように、この段階は垂直オーバーフローを、６９
２から３９１に減らしている。第２５図には、ボックス
内部での除去後の水平オーバーフローが示されている。

最初重視したのが、垂直オーバーフローの除去であるか
ら、ここでは何の改善も記録されていない。達成された
新しい位置は、実行前のオーバーフローの位置とは大幅
に異なっている。新しいボックスが形成され、処理が繰
り返されて、垂直及び水平のオーバーフローが減少する
。第２６図及び第２７図は、結果として得られたオーバ
ーフローが垂直側で２７９に、また水平側で１８６に減
ったことを示している。次いで、ボックスの操作が水平
側を重視して実行される。

第２８図及び第２９図はその結果を示すもので、水平オ
ーバーフローは９５に減っている。処理の目標を変更す
るという方法は通常、このように大規模な問題を解くと
きには効果的なやり方であるが、これは位置を連続的に
変えることによって、基本最適化機構が最高の効率で作
動できるようになるからである。ボックスの中には、第
３０図の例に示すように、プログラムを後で実行する事
によって形成されるものもある。目標を変えていくとい
うやり方を、さまざまな方法で拡張することができる。

最も効果的なものの１つは、−１または−２という普遍
的なバイアスをすべての位置に導入するという方法を使
用することである。したがって、本発明を実施するため
に使用されるプログラムは、０のセルを、それが−１で
あるかのようにして処理する。新たに大量の計算が行な
われ、位置を微妙に変化させる。バイアスを実施した後
、バイアスなしで実行すると、オーバーフローを除去す
る新しい機会が見つかる。第３１図及び第′３２図は、
−１または−２のバイアスを施してから、新たにバイア
スを施すことによって得られるオーバーフローを示して
いる。用いられる唯一のアルゴリズムが、本発明で提示
されるものであって、これが目標シフト法を簡単に採用
できるものであることに、留意すべきである。

ここで検討しているコンピュータの作動の詳細を示す図
についての説明を続ける前に、２つの類比を行なうと、
上述の目標シフト法が理解しやすくなろう。春に、太陽
が毎日はぼ同じ場所から昇り、毎日はぼ同一の軌道をた
どるので、氷の塊が岩の割れ目に残っている。氷を遮っ
ている周囲の岩は位置を変えない。太陽の全体的な軌道
が変わるか、あるいは周囲の岩が若干位置を変えれば、
太陽の融解力によって氷が溶け、消え去る。前に、ふる
いに入れた豆について述べた。しばらくすると、豆はさ
まざまな孔の上で、集合体のグループを形成するように
なり、この集合体が個々の豆が孔から落ちるのを妨げる
。ふるい、つまり全体を揺すると、このような集合体の
多くがばらばらになり、豆は孔から下へ落下するように
なる。問題を最も効果的に解決するには、本質的に静的
な状態を維持してはならない。

上述の方法を使用した操作をさらに続ける。その結果得
られるオーバーフローの値を、第３３図及び第３４図に
示す。この方法が可能なかぎり、不必要な平行度を導入
することなく、オーバーフローを除去するように構成さ
れていることに留意されたい。たとえば、オーバーフロ
ーがアンダーフローに包囲されており、この時点までど
のネットに対しても、まわりくどい経路指定が行なわれ
ていない場合には、この手法に抗して、僅かな数のオー
バーフローが存在していると、少数のネットに若干まわ
りくどいバスが設けられ（かなりのアンダーフローをも
たらす）、すべてのオーバーフローが比較的簡単に除去
されることになる。第３５図はプログラムをさらに実行
することによって形成される若干のボックスを示してい
る。

問題をシフトする他の方法は、基礎となる評点を変更し
、オーバーフローに対する処理を強化することである。

仮に、すべての１をＯに下げると、−２のペナルティが
課され、すべての−１をゼロに上げると、＋５のボーナ
スが与えられ、すべての−２を−１に上げると、＋７の
ボーナスが与えられるというようになる。動きのいくつ
かが成功し、他のものは失敗することになる。大規模な
問題を解く初期の段階では、オーバーフローの処理をあ
まり強力に行なわないことが重要である。

このことによって、望ましくない位置が生じることがあ
るからである。しかしながら、後で、オーバーフローが
きわめて限定され、かなりのアンダーフローが生じた場
合には、い（つかのペナルティを減らし、いくつかのボ
ーナスを増やすことによって、新しい移動を促進するこ
とができる。もちろん、これはすべて、本発明の方法を
使用することによって、簡単に溝たされるものである。

第３６図及び第３７図は調整した評点を使用してボック
スを実行した後で到達する水平及び垂直方向の位置を表
わしている。この時点で、３６の垂直のオーバーフロー
と、１７の水平のオーバーフローがある。

この時点で、プログラムは、オーバーフローを回避する
ためにワイヤの長さを追加できる一連のセグメント移動
を行なって、残っているオーバーフローを処理した。強
調しておかなければならないのは、このような方法がき
わめて初期の段階で問題に適用された場合、効果がなく
、効果があるのが、終了間際であることが証明されたが
、これは本発明記載の方法が上述した後で扱いやすい位
置を達成するからだということである。垂直オーバーフ
ロー０、及び水平オーバーフロー０の最終位置が自動的
に達成される。

第３８図ないし第４４図は、上述のすべての操作を簡潔
にまとめたものである。本発明方法からセグメント移動
操作への転移が、第４２図に示されている。指摘してお
かなければならないのは、本発明を実施したソフトウェ
アの現況では、これを何回にもオ）たって不必要に実行
しなければならないということである。これは修正でき
るもの、であり、基本的な発明に影響を及ぼすものでは
ない。

すべての操ｆ′ＩＥｌま１９８７年１１月１５日、１日
で行なわれた。ソフトウェアの現在の状態では複数回実
行しなければならないが、比較的明確な制御機能を導入
することによって、操作全体を単純なものとすることが
できる。第４５図及び第４６は、垂直及び水平方向のオ
ーバーフローのない最終位置を示すものである。

本明細書で取り上げた問題には、約５０００個のネット
と、２４０００個を超えるノードがあった。第４７図は
５０００個のネットのうちの１つ（ネッ）＃１６４）に
対する出発帯域を示している。これは第１７図及び第１
８図に示した合計に寄′ｊ、したものである。第４８図
は除去工程が完了した後のネットを示している。これは
第１９図及び第２０図に示した最終合計に寄与したもの
である。第４９図はネット＃１６４に対応する最終の経
路指定を示している。第４９図において、付加的なバイ
アが最終的に導入されてはいるが、この最終的な経路指
定に不必要な平行度が存在しないことに留意されたい。

第５０図、第５１図、及び第５２図は同じネッ）３４０
９に対する３つの段階を示したものであり、第５３図、
第５４図、及び第５５図は同じネット１９８５に対する
３つの段階を示したものである。「ｐ」は異なるネット
におけるノードを表わす。また、ネット３４０９につい
ては、追加のバイアが導入されてはいるが、ラインの最
小長さの増加は生じていない（第５２図）。ネッ）１９
８５については、きわめて僅かな平行度が生じている（
第５５図）。いくつかのネットについては、追加のバイ
ア及びワイヤ長の追加（非最短ワイヤ長）が導入されて
いる。しかしながら、きわめて多いネットについては、
もちろん、最終除去工程から最終経路指定までの間に何
の変化もない。ここに示した３つのネットはロフトのう
ちで典型的なものである。本発明の方法が問題全体に対
してオーバーフローを完全に除去できるだけでなく、個
々のネットに対して効率のよい経路指定も行なえること
が理解されよう。

第５６Ａ図は選択された領域６０を示しており、この領
域においては、出発帯域を作成し、これらの出発帯域か
ら冗長なバスを削除した後でも、バス空間に対する需要
が供給を上回っている。また、バス５４と、ノード５３
Ａ、５３Ｂ及び５３Ｃを含むサブネットも示されている
。ノード５３Ｂは選択された領域６０に入るネットのノ
ードであり、ノード５３Ａ及び５３Ｃはバス５４と、選
択された領域の周縁との交点の点として形成されたノー
ドである。

第５６Ｂ図には、ノード５３Ａ、５３Ｂ及び５３Ｃを含
むサブネットに対する拡張帯域５５及び選択された領域
が示されている。拡張帯域がらのバスの削除については
、上述した。

Ｆ０発明の効果 」−記のように、本発明はノードを相互に接続すべきネ
ットに対して出発帯域を生成する事によって、入城配線
を最適化する方法を提供するものである。

【図面の簡単な説明】 第１図は１５行；１５列の回路チップの略図である。 第２Ａ図及び第２Ｂ図はそれぞれ、回路チップの行及び
列の略図である。行は３つのワイヤ空間を有するものと
して示されており、列は３つのワイヤ空間を有するもの
として示されている。 第３Ａ図はサンプルのネット及びその出発帯域の略図で
あり、第３Ｂ図は出発帯域のバスの１つの略図である。 第４図は垂直方向の冗長バスが、水平方向の冗長バスよ
りも多い出発帯域の略図である。 第５図は３つのノードを有する帯域の略図である。 第６図は出発帯域の略図である。最短長のバスのみが出
発帯域に使用されていることに留意されたい。 第７図は第５図のノードを相互接続するために考えられ
る第２の出発帯域の略図である。 第８図は第５図の対応するノードを相互接続するために
考えられる第３の出発帯域の略図である。 第９図は第７図または第８図からバスを削除した後に残
るバスの略図である。 第１０図は出発帯域から冗長バスを削除した後ニ残るバ
スの略図である。同心円の３対のバスのいくつかは、こ
のバスの経路を指定するのに必要なバイアを表わす。 第１１図は垂直に５のオーバーフローを、また水平に７
のオーバーフローを有しているセルの略図である。 第１２図は垂直及び水平それぞれのオーバーフローを示
す、セルのアレイの略図である。このアレイは第６図の
出発帯域が使用するワイヤ空間に対応している。 第１３図はＲＩＯを通るバスを除去した第１２図を更新
した図であって、若干の冗長バスを除去したことによっ
て更新されたワイヤ空間に対する需要と、その供給を示
すものである。 第１４図はＲ１３を通るバスを除去した第１２図を更新
した図であって、他の冗長バスを除去したことによって
更新されたワイヤ空間に対する需要と、その供給を示す
ものである。 第１５図はチップの垂直列で利用できるワイヤ空間の略
図である。 第１６図はチップの水平行で利用できるワイヤ菟間の略
図である。 第１７図はワイヤ空間に対する累積需要と、利用可能な
ワイヤ空間の供給との比較によってもたらされる垂直オ
ーバーフローの図である。 第１８図はワイヤ空間に対する累積需要と、利用可能な
ワイヤ空間の供給との比較によってもたらされる水平オ
ーバーフローの図である。 第１９図は出発帯域から冗長バスを削除した後の垂直オ
ーバーフローの図である。 第２０図は出発帯域から冗長バスを削除した後の水平オ
ーバーフローの図である。 第２１図はワイヤ空間に対する需要が供給を超えている
選択された領域を示す図である。 第２２図は拡張帯域を生成することによって作成された
垂直オーバーフローを示す図である。これらのオーバー
フローはワイヤ空間に対する需要と、利用可能なワイヤ
空間の供給との比較によってもたらされるものである。 第２３図は拡張帯域を生成することによって作成された
水平オーバーフローを示す図である。これらのオーバー
フローはワイヤ空間に対する需要と、利用可能なワイヤ
空間の供給との比較によってもたらされるものである。 第２４図は拡張帯域から冗長バスを削除した後の垂直オ
ーバーフローの図である。 第２５図は拡張帯域から冗長バスを削除した後の水平オ
ーバーフローの図である。 第２６図及び第２７図はそれぞれ、拡張帯域から冗長バ
スを削除したことによってもたらされる垂直及び水平オ
ーバーフローの図である。 第２８図及び第２９図はそれぞれ、問題解決の後期の段
階で拡張帯域から冗長バスを削除したことによってもた
らされる垂直及び水平オーバーフローの図である。 第３０図は拡張帯域が生成された付加領域を示す図であ
る。 第３１図及び第３２図はそれぞれ、バイアスを１本また
は２本取り除いた後、新しいバイアスを配置した際の垂
直及び水平オーバーフローの図である。 第３３図及び第３４図は本発明の方法を数回反復した後
に得られる垂直及び水平オーバーフローの図である。 第３５図は拡張帯域を生成した若干の領域を示す図であ
る。 第３６図及び第３７図はそれぞれ、拡張帯域から冗長バ
スを削除した後に生じる垂直及び水平オーバーフローの
図である。 第３８図ないし第４４図は本発明の方法を数回繰り返し
て得られる結果を要約した図である。 第４５図及び第４６図はそれぞれ、垂直及び水平オーバ
ーフローが本発明の方法を使用することによって、実際
に０まで減少したことを示す図である。 第４７図はこの好ましい実施例に使用される出発帯域の
１つを示す図である。 第４８図は第４７図の出発帯域から冗長ワイヤ・バスを
削除したワイヤ・バスを示す図である。 第４９図は第４７図の出発帯域に使用される最終ワイヤ
・バスを示す図である。 第５０図、第５１図及び第５２図はそれぞれ、第２のネ
ットを使用しｌ；第４７図、第４８図及び第４９図に対
応した図である。 第５３図、第５４図及び第５５図はそれぞれ、第３のネ
ットの第４７図、第４８図及び第４９図選択された領域
の拡張帯域も示している。 １０・・・・回路チップ、１３・・・・トラック、１５
・・・・セル、３０・・・・出発帯域、３３・・・・バ
イア、３４・・・・セグメント、３５．５３Ａ、５３Ｂ
、５３Ｃ・・・・ノード、５４・・・・バス、６０・・
・・領域。 Ｃｎ　１　＜、　ｎ　＜−１５ りづＣ６Ｃ７Ｃ３Ｃ９ＣＩＯ ４干 シＩ　Ｃ６Ｃ７Ｃ８Ｃ９Ｃ１０ クリ　Ｃ６Ｃ７Ｃ８Ｃ９Ｃ１０ 行 クリ　Ｃ６Ｃ７Ｃ８Ｃ９Ｃ１０ 列　８ ？Ｉ　　　Ｃ８Ｃ９Ｃ１０ 列　　　Ｃ［３Ｃ９ＣＩＯ ？Ｊ　　　　ＣＢ　　　Ｃ９ＣＩＯ ＦＩＧ、＋５　　　　垂直ライン１２手＋１用又パ！ｂ
総、ワイヤ空０　　オーへ°゛−フロー　セ！し、卒先
、オーツぐ一フロー評、赤、′ＦＩＧ１６　　　　　　
水平ライシｌ：利用７゛きろ続、ワイヤ空ｒ２０２１２
２２３２１１２５２６２７２８２９３０３１３２３３３
’１ＦＩＧ、　１７　　　　　　肖りン成前の垂直舅゛
−へ−フロー丹り・ｊ：　　ｌ　２３　ｋ　５６７８９
１０１１１２１３１４１５１６１７１８５８３　オーへ
゛′−フロー　ヤル、　　　株、オーツぐ一フし一棋１
点、　−一４３＋９２０２＋　２２２３２１ｉ　２５２
６２７２８２９３（１３＋　３２３３３４ＦＩＧ、　（
９除敷工程後の悸直： ２３５　　オーム′−フロー・セし、締、寸−）く°−
フυ−詳、帆ヤーノぐ−フ℃ス　− １７１１３１９２０２１２２２３２ｆｔ　２５２６２７
２８２９３０３１３２３３３’１間　　−６９２ ＦＩＧ、２０　　　除去工程後の水平オーツ６８　　　
オー／ぐ一フロー・セ１し、　　糸厄、オーツぐ゛−フ
ロー　υト・替、Ｋｏ−フロー ＋７　ｉａ　＋９２０２＋　２２２ヰ２１４２５２６２
７２８２９３０３＋　３２３３３’１ＦＩＧ、２２　　
　　拡張帯域生べ後め垂直オーツζ−フロー３６１　　
　オーツ（−フロー　七ル、　総、オーツく′−フロー
詳１吉、　−−２２３３２０２１２２２３２４２５２６
２７２８２９３０３１３２３３３’１ＦＩＧ、２Ｂ　　
　　拡張榮域生代後の水平オー）＜′〜ヅロー１９２０
２＋　２２２３２１＋　２５２６２７２８２９３０３１
３２３３３４ＦＩＧ、２４　　　　　　　　、を窄イ乍
終了…今力垂に、オークＩ　　ｌ　　２　３　　ｋ　　
５　６　７　８　９１０１１１２１３１’１Ｔ５１６１
７１７３　　寸−７ζ４−フロー　セ１し、蛙、寸−ノ
ぐ−フロー　詳７占、　−−ノぐ−２０−一 ”１８１りｚａ　２ｔ　２２２３２！ｌ　２５２６２７
２８２９３０３１３２３３３’１・　−３９１ ＦＩＧ、２５　　　拡張量Ｊ詠：すらｈ除友フ５　　寸
−ノぐ゛−−フロー　　＋−）し２　　郭ゑオーツぐ一
フロー　評、（掩め）ｋ手オー７＜゛−フロー １７１８１９２０２１２２２３２４２５２６２７２８２
９３０３１３２３３３’＋緊　　−−１９８ ＦＩＧ、２６　　　扛Ｊ長帯」或からめ脈も後の乗置オ
ー１６１　オーバーフロー・セ）し、総、オーツぐ−フ
ロー詳、帆−ノぐ−フロ− １７１８１９２０２＋　２２２３２ｔＩ２５２６２７２
８２９３０３１３２３３３’ｔＦＩＧ、２７　　　摸作
終了時の水平材−７０オーツ＜“−フロー・セ１し、締
、オーツく・−フし一柄嗜ノぐ−フセー １７　１８　１９　２０　２１　２２　２３　２１＋　
　２５　２６　２７　２８　２９　３０　３１　３２　
３３　３＋４テ、　　−−１８６ ＦＩＧ、２８　　　イ菓作終了時の垂直オー２．−　グ
弓、　　　＋　　　２　３　４　５　６　７　８　９１
０１１　１２１３１４１５１６１フイゴ １６９　寸−べ゛−フロー　セ１１．　、　　軛、ｔ−
ノ、−フロー評点、　　　−１ぐ一フロー １８１９２０２１２２２３２４２５２６２７２ａ　２９
３０３１３２３３３１４ＦＩＧ、２９　　　　操作終了
時め水牢寸−ノ５１　　寸−ノ、′−フロー・セ１し、
　化オー７、−フロー誇、壱。 １、：′−フロー ７　ｉａ　１９２０２１２２２３２１４２５２６２７２
８２９３０３１３２３３３ｂ一９５ ＦＩＧ、３１　　　Ｊ巣作終４了時−の重重」−ノく′
−フ１コー９２オーツぐ−フロー・セル、　締、オーツ
ぐ゛−フロー済−１帆　　−−１３７ＦＩＧ、３２　　
　揉イキ終了時の水＋寸。 ４８１寸−バ′−フロー　セし、　畦、オーツぐ゛−フ
ロー評九１−　ノぐ”−フ　ロー ２０２１２２２３２１＋　２５２６２７２８２９３０３
１３２３３３１４ＦＩＧ、３３　　　　す菓イ乍終了時
め垂０５３　寸−ノぐ一フロー・セＩし、　　来も、叶
−ノ＜′−２０−言１寸−ノく°−フロー ｉ　１６１７１８１９２０２１２２２３２４２５２６２
７２８２９３０３１３２３３３１１厚１番、　−一７６ ＦＩＧ、３４　　　掃作終了時の水平−−＋　１５１６ ２７　　寸−ノに一フロー・セ＋１．．喉レオーノぐ゛
−セｊゝ坪点・オーツに−フロー １７１８　（９２０２１２２２３２１４２５２６２７２
８２９３０３１３２３３３に−−１＋０ ＦＩＧ、３６　　　ネット０オーツ〈°−１３１１ｔ−
パーフロー・セノし、　　締、オーツぐ−フロー３−−
徒の垂直オーベ°−フロー ＋ｓ　＋６１７　＊ａ　１９２０２１２２２３２１１２
５２６２７２８２９３０３１３２３３３１１乎定　−−
３６ −Ｑ（ 刑ぢへ 、）７１　　駐 へへ ：＋：＋１ ハ　　ハ よ 、） ＦＩＧ、４４ ＦＩＧ、４７ ３　６　９１２＋５１８２１２１＋２７３０３３ＦＩＧ
、４５　　　　操作終了時の垂直オーｌミ゛−フロ１７ ０　　オーツぐ−フロー　セノし、総オーへ°−フロー
誤、気ロー １８１９２０２１２２２３２１１２５２６２７２８２９
３０３１３２３３３’１ＦＩＧ、４６　　　　　　　．
５へλ　イ′Ｙ　絆　了　ｎ寺　の　水平　１−−ノく
・−行り＋１：Ｉ２３’＋５６フ８９１０　Ｉｆ　１２
　＋３１’４ｊ５１６１７１０　　寸−ベーフロ−（＝
Ｌ、　　総＾オーへ゛−）０−　整Ｌ・占・　　　０−
フロー １８１９２０２１２２２３２１４２５２６２７２８２９
３０３１３２３３３１゜ＦＩＧ、４８ ＦｉＧ。４つ ＦＩＧ、５０ ＦＩＧ、５１ ＋１ＥＴ　　−３に０９ ＦＩＧ、５３ ＮＥＴり　１９８５ ＦＩＧ、５４ ｔ１εＴ−１９８５ ３６９＋２　１５　１８２１　２＋４２７３０３３ＦＩ
Ｇ、５５ Ｌ　　　　　　　　、Ｊ Ｌ　　　　　　　　　Ｊ

Claims (1)

1. 【特許請求の範囲】 複数のネットのおのおののノードを相互接続するための
   方法において、（ａ）形成すべき上記ノードの各ネット
   毎に初期領域を形成する段階であって、該初期領域は、
   上記各ネットのすべてのノードを相互接続するための全
   セグメントの部分集合であって、そのとき該部分集合の
   あらゆるセグメントは、（ａ１）上記ネットのあらゆる
   最小経路の一部である除去不能セグメントであるか、ま
   たは（ａ２）除去可能セグメントであって、該あらゆる
   除去可能セグメントは上記ネットの少なくとも１つの最
   小経路の一部であるけれども上記ネットのあらゆる最小
   経路の一部である訳ではないような段階と、 （ｂ）上記段階（ａ）で形成された全ての初期領域によ
   って作成される経路スペースのための累加的な需要を決
   定する段階と、 （ｃ）上記複数のネットの１つのネットを選択する段階
   と、 （ｄ）上記段階（ｃ）で選択された上記ネットのための
   初期領域の複数の冗長経路を選択する段階と、 （ｅ）上記段階（ｂ）で決定された上記需要を、上記段
   階（ｄ）で選択された複数の冗長経路によって使用され
   る領域中の利用可能な経路スペースの供給量と比較する
   段階と、 （ｆ）少なくとも上記段階（ｅ）の比較の関数であるス
   コアを上記複数の冗長経路のおのおの毎に決定する段階
   と、 （ｇ）上記段階（ｃ）で選択された上記ネットの初期領
   域から、上記段階（ｄ）で選択されたどれかの経路で最
   悪のスコアをもつような冗長経路を削除する段階と、 （ｈ）上記全てのネットの各初期領域から全ての冗長経
   路が除去されるまで上記段階（ｃ）乃至段階（ｇ）を反
   復し、そのとき上記累加的な需要は、その前の反復の段
   階（ｇ）で削除された経路を含めることなく再計算され
   るような段階と、 （ｉ）上記段階（ｈ）で残っている利用可能な経路スペ
   ースと経路を使用して各ネットのノードを相互接続する
   段階を有する、 ノードの相互接続方法。