JPH04113473A

JPH04113473A - 素子間配線方法及び装置

Info

Publication number: JPH04113473A
Application number: JP2232325A
Authority: JP
Inventors: Hiroshi Date; 博伊達; Terumine Hayashi; 林　照峯
Original assignee: Hitachi Ltd
Current assignee: Hitachi Ltd
Priority date: 1990-09-04
Filing date: 1990-09-04
Publication date: 1992-04-14

Abstract

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

Description

【発明の詳細な説明】〔産業上の利用分野〕本発明は、ＬＳＩやプリント基板における相関関係を有
する複数の回路モジュールや回路素子の端子間を配線す
るための素子間配線方法及び装置に関する。

〔従来の技術〕

従来における素子間の配線方法の中で最も強力なものは
、り一著［パス接続アルゴリズムとその応用Ｊ　（Ｃ，
Ｙ、Ｌｅｅ：、Ａｎ　Ａｌｇｏｒｉｔｈｍ　ｆｏｒ　Ｐ
ａｔｈ　Ｃｏｎｎｅｃｔｉｏｎａｎｄ　Ｉｔｓ　Ａｐｐ
ｌｉｃａｔｉｏｎｓ、ＩＲＥ　Ｔｒａｎｓ、ｖｏｌ、　
ＥＣ−１０，ｐｐ。

３５６−３６５（１９６１）、）に記述されている迷路
法と呼ばれている方法である。この方法は、１素子毎に
、始点から終点へ経路探索しマーク付けする前進探索、
終点から始点へバックトレースする後退探索、マークク
リアという３段階の４処理からなる。この方法、の特徴
は、対象とする素子間の配線経路が存在すれば必ず求ま
るという点である。しかしこの迷路法の初期のものは逐
次処理を対象にした方法であったため、計算時間がかか
り、大規模な問題に対しては使用するメモリ量が多すぎ
、適用することが困難であった。これらの問題点を克服
するために、（１）始点終点同時に経路探索を行う方法
、（２）配線領域公開による並列化、（３）ピンペアグ
ループ分けによる並列化、（４）前進探索に置けるウェ
ーブフロン１〜」二の経路探索の並列化等の試みがなさ
れてきた。（１）に属する方法としては、Ｊ、５ｏｕｋ
ｕｐ。

”ＧＬＯＢＡＬ　ＲＯＵＴＥＲ”　　（Ｊ、ｏｆ　Ｄｉ
ｇｊ、ｔａｌ　Ｓｙｓｔｅｍｓ、ＩＶ、１゜ｐｐ、５９
−６９．１９８０．及び浅野哲夫、′並列グローバル・
ルータ”　（情処学論、　２３，４．ｐｐ、４４３−４
５０．１９８２−０７）に示されたものがある。（２）
に属する方法としては、上記Ｊ、５ｏｕｋｕｐの論文に
示されたものがある。

（３）に属する方法としては、進藤達也他２名、並列配
線法″（昭和６０信学会情報・システム部門全天、５３
−２．）　、緑用博子他２名、″画像処理システムＴＩ
Ｐ−３での配線処理″（昭６０信学会情報・システム部
門全天、）、及び緑用博子他２名、“ＴＩＰ−３におけ
る並列配線”　（昭６１前情処前大、３Ｌｌ−６，）に
示されたものがある。（４）に属する方法としては、橘
昌良他４名、″並列ルーティングプロセッサの試作研究
″（情処学論、２７，６＋ｐｐ。

６３９−６４７．１９８６−０６）、に、５ｕｚｕｋｉ
、ｅｔ　ａｌ、、”Ａ　ＨａｒｄｗａｒｅＭａｚｅ　　
Ｒｏｕｔｅｒ　　ｗｉｔｈ　　Ａｐｐｌ］ｃａｔｊ、ｏ
ｎ　　ｔｏ　　Ｉｎｔｅｒａｃｔｊ、ｖｅＲｉｐ−Ｕｐ
　ａｎｄ　Ｒｅｒｏｕｔｅ”（ＩＥＥＥ　Ｔｒａｎｓ、
Ｃｏｍｐｕｔ、−Ａｊ、ｄｅｄＤｅｓ、Ｉｎｔｅｇｒａ
ｔｅｄ　Ｃｊ、ｒｃｕｉｔｓ　＆　５ｙｓｔ、、ＣＡＤ
−５，４，ｐｐ。

４６６−４７６．１９８６−１０）　＋及び特開昭６３
−１５３６７号に示されたものがある。これらの中で最
も並列度の高いものは（２）の領域分割による並列配線
方法である。

そのほかに、大規模な配線処理を複数のプロセッサを用
いて行うために、配線領域を分割し、分割された各領域
にプロセッサを割り当て個々の領域に関して独立に配線
を行う方法が提案されており、特開昭６１−１２５０４
２号、特開昭６２−２３１３０号、特開昭６２−１１５
５７４号に示されたものがある。

〔発明が解決しようとする課題〕

上記の領域分割型配線方法に関する従来技術には、次の
問題点がある。（１）領域を分割して並列に各領域を配
線する場合、配線経路が各領域にまたがるようなものは
求まらない可能性がある。（２）配線経路は、配線する
面上に格子（配線の幅はその辺より小とする）を設定し
、隣接する格子を順次つないで形成されるが、従来技術
ではこの各格子を処理の単位としているので、大規模問
題に適用する場合メモリが不足することがある。

本発明の目的は、配線領域を分割しても素子間の配線経
路が存在すれば必ずそれを見つけることができ、大規模
な問題に対してもメモリの節約ができる素子間配線方法
及びこの方法を用いた素子間配線装置を提供することに
ある。

〔課題を解決するための手段〕

上記の目的は、配線領域を分割し、分割した領域毎に、
他分割領域との境界上にある境界格子で既に配線に用い
られたものあるいは配線が禁止されたちの以外の配線可
能境界格子を取り出し、それらを隣接関係によって配線
可能境界格子群に分割し、さらに当該分割領域内の配線
可能格子で上記配線可能境界格子群に隣接するものを付
加し、さらにその結果得られた各格子群に上記配線可能
格子で隣接するものを付加するという処理を各格子溝同
時に繰り返すことにより当該分割領域を小領域に分割し
、次にこの小領域の各々を節点とし、小領域間に隣接関
係があればその小領域対応の点の間に枝を有するグラフ
を作成する。そして接続すべき２つの素子（各々１つの
格子で代表）が分割された小領域のどれに含まれている
かを判定し、それらの小領域間の経路を上記グラフの接
続関係から探索して概略配線経路とし、最後にこの概略
配線経路上にある各小領域単位に並列に詳細配線を施す
ことによって達成される。

〔作　用〕

最初に素子間配線装置は、設計データ入力部から配線領
域の概略や禁止領域、配線可能領域などの配線状況情報
、そしてどの素子とどの素子を結線するのかを示した接
続要求情報を格子の状況、接続関係の情報として入力し
ておく。次に予め指定された分割数に配線領域を分割し
、各分割領域毎に並列処理を行えば各処理を行うプロセ
ッサのメモリは小さくてよく、並列化による高速化もは
かれる。続いて各分割領域毎に、前記入力を用いて担当
プロセッサが境界格子を配線可能境界格子群へ分割する
と、その各格子群毎にプロセッサを割り当てて小領域へ
の配線可能格子の分割が行え、またその分割処理に伴っ
て小領域毎の隣接関係が分かるので、それを用いて前述
のグラフを作成できる。このようにして作成されたグラ
フを用いて概略配線経路を求めれば、それは小領域を単
位とする経路探索であって、通常小領域の個数は格子の
数よりもずっと少ないから経路探索は高速に小メモリ容
量を用いて実行できる。こうして得た概略配線経路の各
小領域内での格子単位の経路決定は従来技術で行え、こ
れを各小領域で並列実行すれば、この処理も小容量メモ
リで高速に実行できる。しかも本方法によれば、接続し
ようとする素子間に経路が存在するならば、必ず概略経
路が見つかり、従って必ず配線経路が求められる。

〔実施例〕

以下、本発明の一実施例を図面を用いて説明する。第１
図は、本発明による素子間配線装置の機能構成の一実施
例を示したブロック図、第２図は同装置のハードウェア
構成を示すブロック図である。第２図において、ＣＰＵ
２１は全体の動作を統括する処理装置、プロセッサ（Ｐ
Ｅ）２２ａ〜２２ｄ、２３ａ〜２３ｈは各処理段階で並
列処理を行う処理装置で、これらは階層的に接続され、
各共有メモリ２０．２４ａ〜２４ｄ、２５と接続されて
いる。

以下、第１図を中心に各処理部１０．１２〜１６を順次
説明する。まず第１図の設計データ入力部１０から配線
領域の既配線領域や禁止領域、配線可能領域などの配線
状況情報、そしてどの素子とどの素子を結線するのかを
示した接続要求情報を本装置１１へ入力し、これを配線
状況テーブル及び配線テーブルとして共有メモリ２５へ
設定する。ここで配線領域第３図に示すように多数の格
子（小さい四角形）に分けて管理するものとし、既配線
かまたは配線が禁止されている格子は斜線を付したもの
とする。これに対応した、前記の配線状況テーブルは、
第４図（ａ）に示したように、第３図の各格子に番号を
つけておき、その番号毎に状態フラグを対応させたもの
である。そして状態フラグは、当該格子が配線に既使用
か禁止されているか（第３図斜線のついた格子）、それ
以外の配線可能格子かを示すものとする。また配線要求
テーブルは、第４図（ｂ）に示すように、接続する配線
を信号で表し、その配線の両端の格子番号（ここに素子
が配置される）を対応させたものである。なおこれらテ
ーブルは初期設定時から、配線が決定される毎に使用格
子が既使用へ、当該配線要求がすみ（または削除）の状
態に更新される。

以上の各テーブルへの入力が終わると、本装置１１の配
線領域分割部１２が起動し、第５図に示すように、配線
領域３０を分割（こごでは４等分）し、分割領域３１ａ
〜３１ｄとする。この場合、分割領域間は１格子幅の共
通の境界領域３２と考え、この境界領域はその境界の両
側の分割領域に含まれるものとする。従って分割領域３
１ａ〜３１ｄは第６図に示すように隣接領域との共通の
境界領域を持っている。

この分割が終わると、各分割領域３１ａ〜３１ｄに第２
図のプロセッサ２２ａ〜２２ｄを割り付け、かつ各分割
領域に含まれる格子点についての配線状況テーブル及び
配線要求テーブルの内容を、それぞれ共有メモリ２４ａ
〜２４ｄヘロードする。ここで分割領域の数とＣＰＵ２
１の下のプロセッサの数は等しく４個としたが、プロセ
ッサ数が小さいと・きはその分を時分割処理し、論理的
に第２図の構成となるようにすればよい。

こうして第１図の領域分割部１２の処理が終わると、各
分割領域３１ａ〜３１ｄごとにプロセッサ２２ａ〜２２
ｄが並列に動作して境界上格子統括部１３の処理が行わ
れる。第７図（ａ）は分割領域３１ａの境界格子の部分
を詳しく示しており、斜線を付していない格子が配線可
能境界格子とする。統括部１３の処理は、これらの配線
可能境界格子を隣接関係によって第７図（ｂ）のような
格子群Ｓ１からＳ３、Ｒ１−Ｒ４に分ける。ここで隣接
関係というのは、直接隣接し、たとき、あるいは間にい
くつかの格子があって順に隣接したものをたどっていく
と行きつくことのできる２つの格子は隣接関係にあるも
のとし、・これは一般に平面の時も同じである。今の場
合は配線可能境界格子は直接上に並んでいて、間に使用
禁止の格子があると隣接関係がなくなり、別の格子群と
なる。

境界上で格子群への分割が終わると、各格子群にプロセ
ッサが、例えば第７図（ｂ）の格子群ＳＬ。

・・・の各々にプロセッサ２３ａ、・・・というように
割り当てられ、次の配線可能領域分割部１４による処理
が行われる。この場合も、例えば第７図（ａ）の格子群
Ｓ１〜Ｒ４の７個に対して、利用できるプロセッサ２３
ａ〜２３ｈが不足しているときは時分割による。

各プロセッサ２３ａ、・・・では、同時に、迷路法の波
を発生させる方法と同様にして当該分割領域内の各格子
に格子群の番号８１〜Ｒ４を割り当てていく。

そして各格子群から発生した波がぶつかり進行できなく
なった時点で処理を止め、この処理をすべての波が進行
できなくなるまで行う。第８図は本処理の例を示したも
ので、先の分割領域３１ａの内、配線禁止領域は同図（
ａ）の斜線部分、配線可能領域は斜線のない部分とする
。このとき、境界上の空き格子群Ｓ１〜Ｒ４から迷路法
と同様に波を発生させて分割領域３１ａの配線領域を小
領域に分割したものが第８図（ｂ）に示されている。こ
の小領域への分割の結果は、第４図（ａ）の配線状況テ
ーブルの各配線可能格子のフラグに、その格子が属する
小領域の番号を記入することで記憶される。ここで各小
領域にはそのもとになった境界上の格子群と同じ番号Ｓ
〕〜Ｒ４を付けるものとする。この処理において、プロ
セッサ２２ａ〜２２ｄは、プロセッサ２３ａ〜２３ｈの
小領域への分割処理中に、どの波とどの波が衝突したの
かをチエツクしてそれをＣＰＵ２１に知らせ、ＣＰＵ２
１はメモリ２０上に設けた格子群接続関係テーブルに各
格子群の波がどの格子群の波とぶつかったかという情報
を用いて作成した平面グラフの情報を書き込む。これは
第９図に示すように、各格子群（従って小領域）を節点
とする平面グラフで、ぶつかりのあった格子群間の枝の
番号と、その両側の節点を示す領域番号（小領域の番号
ＳＬ、　Ｓ２．・・・等）と、その枝に相当する２つの
小領域の間の接続部分にある格子の数（接続格子数）と
が、各校ごとに記録されたテーブルである。このグラフ
の今までの具体例について示したものが第１０図及び第
１１図に示されている。

各分割領域８１．・・・に分割されたとすると、それら
の接続関係は第１１図のように平面グラフとなる。

次の配線経路決定部１５の処理では、処理１５ａにより
配線すべき素子が無いと判断されるまで以下の処理を繰
り返す。

配線対象素子設定部１５ｂでは、配線要求のある素子（
格子）の１対を第４図（ｂ）の配線要求テーブルから取
り出し、続いてそれらの素子（格子）が属する小領域を
第４図（ａ）の配線状況テーブルから検索する。

概略配線経路決定部１５ｃでは、第８図に示すように配
線対象素子設定部１．５ｂにおいて検索された２つの素
子の属する小領域間を結ぶところの、小領域を単位とし
た概略配線経路を決定する。配線経路決定部１５のここ
までの処理はＣＰＵ２１により実行される。第１０図の
例で、接続しようとする素子（格子）が小領域Ｒ２とＴ
１にあったとすると（第１１図の二重丸で示した節点）
、この概略配線経路の決定は第１１図の平面グラフで、
節点Ｒ２とＴ１を結ぶ最短距離を求める問題として、周
知の方法で解くことができる。この結果、第１１図の場
合は節点Ｒ２−Ｒ１，−８Ｌ−８２−Ｔ２−Ｕｌ−ＴＩ
が概略配線経路となる。この経路を全体の配線領域３０
（第５図参照）上で示したのが第１２図である。

この図は第１０図の分割領域３１ａ〜３１ｄを全部合わ
せて示しており、小領域Ｔｌ、Ｒ２内の接続すべき素子
はｅＳ、ｅＥで示されている。概略経路はこの素子ｅｓ
、ｅＥを結ぶ実線である。概略配線経路決定部１５ｃで
は、この経路が小領域の境界を通る位置に中継端子ｅ１
〜ｅ１２を設定して処理を終わる。

詳細配線経路決定部１５ｄでは、第２図のプロセッサ２
３ａ〜２３ｈのいくつかが概略配線経路上の各小領域を
割り当てられ、その小領域毎に概略配線経路決定部１５
ｃで設けた中継端子間を並列動作により配線する。配線
方法は従来技術と同じで、例えば第１２図の小領域Ｕ１
を割り当てられたプロセッサは、端子ｅ２とｅ２と０３
間のＵｌ内の配線を行う。

配線可能領域更新部１５ｅでは、詳細配線経路決定部１
．５ｄにおいて既配線となった格子を使用禁止とする。

これは第４図（ａ）の配線状況テーブルで使用された格
子の状態フラグを更新してその格子を配線禁止とするこ
とにより行われる。また概略経路上の小領域間の境界に
並ぶ格子数も配線により１つ減るから、グラフを表す第
９図の接続関係テーブルの該当する接続枝番号の接続格
子数を１減らすという更新処理を行う。この結果、新し
く配線された配線可能な各小領域は、第１３図のように
小さくなる。また、第１２図の中継端子ｅ８の部分の縦
方向の幅は１格子の幅とすると、素子ｅＳ−ｅＥ間の配
線により小領域Ｓ１と８２間は第１３図に示すように隣
接しなくなる。このことは上記第９図の接続関係テーブ
ルの更新処理の結果、小領域Ｓ１と８２を結ぶ枝の接続
格子数がＯとなったことから判定できるから、この枝を
接続関係テーブルから除去して、第１１図のグラフのＳ
Ｌ、８２間の枝をなくしておく。このようにして次の素
子間の設定へと戻る。

〔発明の効果〕

本発明によれば、大規模な配線領域における素子間経路
探索を高速に実行でき、必要なメモリ容量も小さくでき
るから、質の高いＬＳＩやプリント基板のレイアウトが
確実にかつ効率よく得られるという効果がある。

【図面の簡単な説明】

第１図は本発明による素子間配線装置の機能構成の一実
施例を示すブロック図、第２図は同装置のハードウェア
構成例を示すブロック図、第３図は格子状配線領域の説
明図、第４図は配線状況テーブル及び配線要求テーブル
の説明図、第５図及び第６図は本発明における領域分割
方法の説明図、第７図は本発明における境界上の配線可
能格子の統括方法の説明図、第８図は本発明における配
線可能領域の分割方法の説明図、第９図は配線可能格子
群接続関係テーブルの説明図、第１０図及び第１１図は
平面グラフの説明図、第１２図は概略配線経路決定方法
の説明図、第１３図は配線可能領域及び平面グラフ更新
方法の説明図である。１２・・・領域分割部、１３・・・境界上格子統括部、
１４・・・配線可能領域分割部、１５・・・配線経路決
定部、１５ｃ・・・概略配線経路決定部、１５ｅ・・・
配線可能領域更新部、２０　、２４ａ　〜２４ｃ　、　
２５−共有メモリ、２１−ＣＰ　Ｕ、２２ａ〜２２ｄ、
　２３ａ〜２３ｈ・・・プロセッサ、３０・・・配置線
領域、３１ａ〜３１ｄ・・・分割領域、４０・・・境界
領域、Ｒ１−Ｒ４゜８１〜８３．ＴＬ　Ｔ２．Ｕｌ、　
Ｕ２・；小領域、ｅ１〜ｅ１２・・・中継端子。代理人弁理士　　秋　本　正　実Ｃて゛・・１１．５．１２．、・・

Claims

【特許請求の範囲】

１．配線面を格子に分け、２つの素子の位置に指定され
た２つの格子の間を縦方向または横方向に隣接した格子
の系列により接続することによって配線経路を定める素
子間配線方法において、上記格子の各々が予め配線用と
して使用禁止に指定されているかあるいは既に配線用に
使用されて使用禁止となっているか否かを示す第１のテ
ーブルと、配線を必要とする２つの素子位置に対応する
格子対を格納した第２テーブルとを設け、上記配線面を
その各々が１格子幅の格子列からなる境界領域で区切ら
れかつ該境界領域は区切られた双方の領域で共有される
ように分割して複数の分割領域とする第１の処理と、該
分割領域の各々において、上記境界領域上の格子で上記
第１テーブルで使用禁止に指定されていない配線可能格
子を取り出し、該格子を隣接関係で到達可能な格子群に
分割する第２の処理と、上記分割領域の各々において、
当該分割領域内の上記配線可能格子を上記格子群の各々
に隣接関係で順次付加することにより上記格子群の個数
に等しい小領域に分割する第３の処理と、上記分割領域
毎に生成された小領域を同一格子群から生成されたもの
は同一小領域として合成し、その後各小領域を節点とし
２つの小領域が隣接する格子をもつとき該当節点間に枝
を有するところの平面グラフを生成する第４の処理と、
上記第２テーブルを参照して配線の必要な１対の格子を
取り出し、該格子の各々が属する上記小領域対応の節点
間を結ぶ経路を上記平面グラフ上で探索して概略配線経
路を求め、さらに該経路が通過する上記小領域間の境界
領域に中継格子を定める第５の処理と、上記配線経路を
形成する小領域の各々において上記中継格子間の詳細配
線を定める第６の処理と、該処理によって配線に使用さ
れた格子を上記第１テーブル上で使用禁止とし、上記配
線により不要となった格子点の対を上記第２テーブルか
ら除去し、かつ上記配線により隣接する上記配線可能格
子を有さない小領域間の枝が上記平面グラフにあればこ
れを除去するところの第７の処理とを行うことを特徴と
する素子間配線方法。
２．前記第５の処理、第６の処理、及び第７の処理を前
記第２テーブルに配線を必要とする格子対がなくなるま
で繰り返し実行することを特徴とする請求項１記載の素
子間配線方法。
３．配線面を格子に分け、２つの素子の位置に指定され
た２つの格子の間を縦方向または横方向に隣接した格子
の系列により接続することによって配線経路を定める素
子間配線装置において、上記格子の各々が予め配線用と
して使用禁止に指定されているかあるいは既に配線用に
使用されて使用禁止となっているか否かを示す第１のテ
ーブルと、配線を必要とする２つの素子位置に対応する
格子対を格納した第２テーブルと、上記配線面をその各
々が１格子幅の格子列からなる境界領域で区切られかつ
該境界領域は区切られた双方の領域で共有されるように
分割して複数の分割領域とする第１の処理手段と、該分
割領域の各々において、上記境界領域上の格子で上記第
１テーブルで使用禁止に指定されていない配線可能格子
を取り出し、該格子を隣接関係で到達可能な格子群に分
割する第２の処理手段と、上記分割領域の各々において
当該分割領域内の上記配線可能格子を上記格子群の各々
に隣接関係で順次付加することにより上記格子群の個数
に等しい小領域に分割する第３の処理手段と、上記分割
領域毎に生成された小領域を同一格子群から生成された
ものは同一小領域として合成し、その後各小領域を節点
とし２つの小領域が隣接する格子をもつとき該当節点間
に枝を有するところの平面グラフを生成する第４の処理
手段と、上記第２テーブルを参照して配線の必要な１対
の格子を取り出し、該格子の各々が属する上記小領域対
応の節点間を結ぶ経路を上記平面グラフ上で探索して概
略配線経路を求め、さらに該経路が通過する上記小領域
間の境界領域に中継格子を定める第５の処理手段と、上
記配線経路を形成する小領域の各々において上記中継格
子間の詳細配線を定める第６の処理手段と、該第６の処
理手段による処理によって配線に使用された格子を上記
第１テーブル上で使用禁止とし、上記配線により不要と
なった格子点の対を上記第２テーブルから除去し、かつ
上記配線により隣接する上記配線可能格子を有さない小
領域間の枝が上記平面グラフにあればこれを除去すると
ころの第７の処理手段とを備えたことを特徴とする素子
間配線装置。
４．前記第２の処理手段は、前記分割領域の各々に１つ
のプロセッサを割り当てて構成されたことを特徴とする
請求項３記載の素子間配線装置。
５．前記第３の処理手段と第６の処理手段の一方または
双方は、前記小領域の各々に１つのプロセッサを割り当
てて構成されたことを特徴とする請求項３記載の素子間
配線装置。