JPH0567178A - 自動配線処理方法 - Google Patents

Abstract

(57)【要約】 【目的】 配線処理を高速にし、かつ配線の性能を向上
することを目的とする。 【構成】 基板上における配線の混雑度を見積もり、配
線の混雑度が高い部分では配線が成功し易いように基板
上を区切るための領域を所定値より大きく取り、配線の
混雑度が低い部分では配線の処理時間が最小となるよう
に基板上を区切るための領域を所定値より小さく取り、
これら大きさの異なる領域毎に配線を行い、基板全体の
配線を完了する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明はＬＳＩやプリント配線板
の自動配線処理における自動配線処理方法に関する。

【０００２】

【従来の技術】従来、この種の自動配線処理方法は「設
計自動化４６−５，“ゲート敷き詰め型ゲートアレイの
自動配線” 第３３〜４０項，（株）東芝 ＵＬＳＩ研
究所，１９８９．２．２０」に開示されるものがある。
これは、配線しようとする半導体基板を一様の大きさの
領域に区切り、区切られた領域毎に配線を行い、最終的
に半導体基板全体の配線処理を完了する方法である。

【０００３】かかる方法には、次のような特徴がある。
まず、配線処理は配線の組み合わせの最適化であること
から、半導体基板を小領域に区切って部分的に配線する
ことにより、配線処理が容易となり、その上データ量も
少なくなるため扱い易い。また、半導体基板を区切る領
域の大きさによって、全ての領域が配線し終えるまでの
処理時間が変化する。

【０００４】図１６にこの特性を示す。図１６におい
て、横軸が半導体基板を区切る領域の大きさであり、縦
軸がその大きさで一様に半導体基板を区切った場合に全
ての領域を配線し終えるまでの処理時間である。図１６
に示すように、領域がある大きさの場合に処理時間が最
小となる。これは、領域が比較的小さい場合には、半導
体基板を区切るための領域数が多くなり各々の領域の配
線のためのデータ作成に要する時間がオーバーヘッドと
なり処理時間が増加する。

【０００５】また、領域が比較的大きい場合には、実際
の配線処理を行うために要する時間が増加する。このこ
とから、すべての領域が配線し終えるまでの処理時間が
最小となる大きさに半導体基板を区切るための領域を設
定すれば、高速配線が可能となる。

【０００６】然るに、配線処理においては処理時間が少
ないことだけでなく、配線の性能が良いことも要求され
る。配線の性能とは、異なるネット（接続要求）の交差
数や接触数（配線のショート数）または正常な配線がで
きなかったネットの本数（未配線ネット数）等で表され
る配線の失敗数や失敗の割合の少なさで示される。従っ
て、配線の失敗数や失敗の割合が少ない配線処理ほど性
能が良いとされる。この配線の性能も半導体基板を区切
るための領域の大きさにより変化する。

【０００７】図１７にこの特性を示す。図１７におい
て、横軸が半導体基板を区切るための領域の大きさであ
り、縦軸がその大きさで一様に半導体基板を区切った場
合に、すべての領域を配線し終えるまでに生じた配線の
ショート数である。図１７に示すように、領域が大きく
なるほど配線のショート数は減少していく。これは、配
線の領域が小さい場合は配線の経路に自由度が少ないた
め比較的に配線が失敗し易く、配線の領域が大きい場合
は配線の自由度が多くなるため比較的に配線が成功し易
いという理由による。

【０００８】これを、図１８乃至図２１により説明す
る。図１８は配線の領域が小さい場合であり、配線すべ
きネットが２本ある。ＡおよびＢは端子を示している。
図１８中で斜線で示した部分はあらかじめ配線ができな
い部分として登録されている配線禁止領域である。

【０００９】図１８を配線した結果が図１９である。図
１９の実線が示すように１本目のネット（Ａ−Ａ）は配
線に成功し、２本目のネット（Ｂ−Ｂ）は配線に失敗し
ている。つまり、配線のショートが生じている。これに
対し、図２０は図１８の領域よりも大きく領域を取った
場合であり、配線禁止領域の周りに配線可能な余裕がで
きている。このため、図２１に示すように、配線が２本
とも成功している。

【００１０】このように、配線する領域内において、配
線禁止領域が占める割合が多かったり、配線するネット
が多数あるとその部分の配線の混雑度が増加する。つま
り、配線領域が小さいと配線の自由度が少なくなるた
め、配線が失敗し易くなり、配線領域が大きいと配線の
自由度が多くなり、混雑度が緩和される場合があるの
で、配線が成功し易くなる。

【００１１】従来の、半導体基板を一定の大きさの領域
で格子状に区切り、区切った領域毎に配線を行っていく
という方法には、次のような問題がある。

【００１２】まず、半導体基板を小領域に区切り、区切
った領域内でのみ配線処理を行っているため、もともと
区切られた領域内の配線の混雑度が高いと配線の失敗が
多くなる。ここで云う配線の失敗とは、異なるネット
（接続要求）の交差数や接触数（配線のショート数）、
または正常な配線ができなかったネットの本数（未配線
ネット数）等で示される値である。

【００１３】これを簡単な図で説明する。図２２は半導
体基板を一定の大きさで格子状に区切った場合の図であ
る。同図において斜線で示した箇所が配線が混雑すると
予測される部分であり、領域７〜９内に配線が混雑する
と予測される部分が含まれている。

【００１４】図２３は領域７〜９を拡大した図である。
領域７，９において配線が混雑すると予測される部分
は、区切られた領域全体の１／４程度を占めている。こ
のような場合、実際の配線処理を行うことによって領域
内全体に配線の混雑が拡散するため配線の失敗は少なく
なる。しかし、領域８のように配線が混雑すると予測さ
れる部分が区切られた領域全体の大部分を占めるような
場合には、配線の混雑は拡散されず配線の失敗は多くな
る。

【００１５】ところで、接続要求のある端子間を配線す
る場合は、接続要求のある端子間を逐次配線処理し、全
体の配線を行う。配線処理は、配線経路を決定する概略
配線処理および最終的な配線の位置を決定する詳細配線
処理からなる。

【００１６】図２４は接続要求のある端子の分布を示
し、同一番号は互いに接続要求のある端子である。

【００１７】図２５に示すように、概略配線処理では、
チップ上あるいはプリント配線板上で接続要求のある端
子同志を結ぶための経路を求める。経路の探索は全体の
仮想的な配線長を最小とするか、あるいは配線の混雑度
をチップ全体でなるべく均一にすること等を目的として
行われる。

【００１８】図２６に示すように、概略配線結果に基づ
き実際の配線の位置を決定する詳細配線処理を実行す
る。詳細配線処理では、設計違反規則を守るように各端
子間を結ぶ配線の位置を決定する。つまり、概略配線で
予め決定した概略の配線経路を基に、各配線が設計違反
規則を守るようにチップ上での各配線の物理的な位置が
決定されていた。

【００１９】

【発明が解決しようとする課題】然し乍ら、上述した従
来の自動配線処理方法においては、半導体基板を一定の
大きさの領域で一様に区切って配線するので、領域の大
きさを配線処理時間が最小になるように小さく設定する
と、高速な配線処理が可能になる反面、その領域が小さ
すぎると配線のショートを生じ易くなり、配線性能が低
下する。逆に、領域の大きさを配線のショートが生じ難
くなるように大きく設定した場合、その領域が大きすぎ
ると、処理時間が増加するという問題点があった。

【００２０】また、半導体基板上の配線の混雑を考慮せ
ずに、単純に一定の大きさの領域に格子状に区切って配
線すると、区切られた領域内の大部分を配線の混雑が予
測される部分が占めるような場合には、配線の失敗が増
加するという問題点があった。

【００２１】さらに、配線処理は接続要求のある各端子
間を単一の計算機を用いて逐次接続するので、回路規模
の増大に伴い配線の処理時間が増大するという問題点が
あった。

【００２２】本発明の目的は、上述した問題点に鑑み、
配線処理が高速で、配線の失敗が少なく、かつ配線の性
能が向上できる自動配線処理方法を提供するものであ
る。

【００２３】

【課題を解決するための手段】上述した目的を達成する
ため、第１の発明は、基板上における配線の混雑度を見
積もり、配線の混雑度が高い部分では配線が成功し易い
ように基板上を区切るための領域を所定値より大きく取
り、配線の混雑度が低い部分では配線の処理時間が最小
となるように基板上を区切るための領域を所定値より小
さく取り、これら大きさの異なる領域毎に配線を行い、
基板全体の配線を完了するものである。

【００２４】また、第２の発明は、基板上の配線が混雑
する部分を予測し、混雑すると予測された部分の占める
割合が各領域で均一になるように、基板上を区切るため
の領域の大きさや位置を設定し、設定した領域毎に配線
を行い、基板全体の配線を完了するものである。

【００２５】さらに、第３の発明は、基板上を複数の領
域に順次分割し、各分割領域間を横切る配線を各分割領
域の境界毎にそれぞれ異なるコンピュータで並列的に処
理し、予め定めた分割領域数あるいは分割領域サイズに
達したら各分割領域内部の配線をそれぞれ異なるコンピ
ュータで並列的に処理するものである。

【００２６】

【作用】第１の発明においては、見積もられた配線の混
雑度により、混雑する部分を含むように基板を区切るた
めの領域の大きさを設定し、大きさの異なる領域毎に配
線を行うので、配線処理の高速化が可能になると共に、
配線の性能が向上する。

【００２７】また、第２の発明においては、配線の混雑
が予測された部分が比較的大きな場合に、混雑する部分
の占める割合が各領域で均一になるように、半導体基板
を区切るための領域の大きさや位置を設定して領域毎に
配線を行うので、配線の失敗を少なくすることができ
る。

【００２８】さらに、第３の発明においては、配線を複
数のコンピュータで並列的に処理するので、処理時間の
短縮が図れる。

【００２９】

【実施例】

第１の発明 以下、第１の発明に係わる自動配線処理方法を図１乃至
図３に基づいて説明する。

【００３０】図１は自動配線処理方法を説明するフロー
チャ−トである。同図によれば、まず、配線に必要な半
導体基板（以下、チップという）のデータを入力する
（ステップｓ１）。ここで、図２は入力されたチップの
モデルを示し、３はチップ、４はＩ／Ｏセル、５は機能
セル列である。

【００３１】次に、チップ３上のどの部分で配線が混雑
するか見積もる（ステップｓ２）。見積もり方法として
は、チップ３上を細かく格子状に区切り、その格子内を
通る配線本数と配線禁止領域との比を概算する。また、
一度チップ３全体の配線を終了した後、配線の失敗した
箇所を修正するため再度配線をやり直すような場合に
は、１回目の配線の結果生じた配線のショート数の分布
を混雑度として用いても良い。

【００３２】そして、図３に示すように、上記混雑度を
基にしてチップ３上に配線のための領域６を設定する
（ステップｓ３）。このとき、配線のための領域６は配
線が混雑していると見積もられた位置に対しては、その
位置を含み配線のショートが生じ難いように所定値（配
線のショート数の特性と、処理時間の特性とのトレード
オフにより決定され、配線のショ−ト数をより少なく
し、かつ配線の処理時間をより少なくするようにあらか
じめ設定されている値）より大きく設定され、配線が混
雑していないと見積もられた位置に対しては、その位置
を含み配線処理時間が少なくなるように所定値より小さ
く設定される。

【００３３】図３に示すデータはチップ３の中心部の配
線の混雑度が高い場合であり、点線で囲まれた斜線部の
領域が配線のための領域となる。即ち、チップ３の中心
部に対しては配線のショ−トが生じないように配線のた
めの領域が大きくとられ、チップ３の周辺部に対しては
配線処理時間が少なくなるように配線のための領域が小
さくとられている。

【００３４】なお、ここで、配線のための領域６の設定
は、見積もられた混雑度に対して予め定めておいた複数
種類の配線のための領域の大きさを割り付けることによ
り行っても良い。

【００３５】次いで、区切られた領域６毎の配線処理が
行われる（ステップｓ４）。ここで、ステップｓ３にお
いて配線のための領域６の大きさが最適化されているの
で、配線のショート数が少ない配線結果が高速に得られ
る。

【００３６】そして、各領域６の配線結果がまとめられ
（ステップｓ５）、チップ３全体の配線結果が出力され
る（ステップｓ６）。

【００３７】第２の発明 次に、第２の発明を詳細に説明する。

【００３８】図４は、第２の発明の処理手順を示すフロ
ーチャートである。

【００３９】まず、配線に必要なデータを入力する（ス
テップｓ１１）。なお、入力されるチップデータのモデ
ルは図２と同様なものである。

【００４０】次に、チップ３上のどの部分で配線が混雑
するかを予測する（ステップｓ１２）。予測方法として
は、第１の発明のステップｓ２における方法と同様な方
法で良い。

【００４１】さらに、チップ３上にチップ３を区切るた
めの領域の初期設定が行われる。ここでは、図５に示す
ようにチップ３全体を一定の大きさの領域で格子状に区
切っている（ステップｓ１３）。

【００４２】そして、配線が混雑すると予測された部分
に対して、ステップｓ１３で設定した領域の位置調整を
行う（ステップｓ１４）。この位置調整は、ステップｓ
１３で設定した領域内に占める、配線の混雑が予測され
る部分の割合が減少する方向に領域の位置を変更、およ
び新たに領域を設定することにより行われる。

【００４３】図６は、図５で示した領域の位置調整を行
った結果を示している。配線の混雑が予測された部分が
大部分を占める領域８は、図６において上方に位置が変
更され、新たに領域８’が領域８の下方に設定されてい
る。このとき、領域８あるいは領域８’と初期設定され
た一定の大きさの領域とによって重なりが生ずるが、ス
テップｓ１５による処理によって重なり部分は消去され
る。

【００４４】ステップｓ１４の処理により領域８，８’
内において配線の混雑が予測される部分の占める割合を
減少させることができるため、実際の配線処理において
配線の混雑が拡散し失敗の少ない配線が可能となる。

【００４５】なお、初期設定後に行う領域の位置調整
は、配線の混雑が予測される部分の領域内に占める割合
が減少する方向であれば上下左右どの方向でもよい。

【００４６】この後、設定された領域毎の配線処理を行
う（ステップｓ１５）。このとき、ステップｓ１４にお
ける領域の位置調整により、図６で示したように領域の
重なりが生ずる場合があるが、配線処理を後で行う領域
において重なった部分の配線結果を消去してから配線処
理を行えばよい。

【００４７】最後に、各領域の配線結果がまとめられ、
チップ３全体の配線結果として出力される（ステップｓ
１６）。

【００４８】なお、領域の初期設定を行わず、配線の混
雑すると予想される部分の、各領域に占める割合が均一
になるように、半導体基板を区切るための領域を図７の
ように直接設定する方法もある。

【００４９】第３の発明 次に、第３の発明の自動配線処理方法に係る具体例を図
８により述べる。

【００５０】図８は並列配線処理方法の説明図である。
なお、同図において、ＣＰＵｉ（ｉ＝1 ，2 ，3 ，4 ）
はそれぞれプロセッサを表す。各プロセッサＣＰＵｉは
マルチプロセッサ構成の計算機のプロセッサであっても
良いし、バス上に接続された各計算機のプロセッサであ
っても良い。また、１はチップ（またはプリント配線
板）を表し、２ｉ（ｉ＝1 ，2 ，3 ，4 ，5 ，6 ）はチ
ップ１上に仮想的に設定した分割線を表す。

【００５１】まず、チップ１上に仮想的な分割線２₁ を
設定し、領域を分割する。

【００５２】次に、分割線２₁ で分けられた分割領域間
を結ぶ配線に着目し、隣接する分割領域間を横切る配線
情報を一つのプロセッサに割り当て、配線処理を施す。
配線情報としては、互いに接続すべき端子のチップ１上
での位置情報およびこれら各端子間を接続する際に利用
出来ない領域である配線禁止領域の情報等が含まれる
（図８ａ）。

【００５３】次いで、分割線２₂ を設定し、領域をさら
に細分化する。そして、分割線２₂ で分割される各分割
領域を横切る配線をプロセッサＣＰＵ₁ およびＣＰＵ₂
により並列に処理する（図８ｂ）。

【００５４】以下同様に、分割線２₃ ，２₄ ，２₅ ，２
₆ を設定し、予め定めた分割領域サイズとなるまで各分
割領域を横切る配線をプロセッサＣＰＵ₁ ，ＣＰＵ₂ ，
…により並列に配線処理する。以上の処理が完了する
と、異なる分割領域間を結ぶ配線はすべて完了する（図
８ｃ，図８ｄ）。

【００５５】最後に、各分割領域内部の配線をプロセッ
サＣＰＵ₁ ，ＣＰＵ₂ ，…により並列に実行する（図８
ｅ）。このとき、各分割領域内の配線は互いに独立に扱
う事が出来るため、プロセッサ数を増やせばその分だけ
並列度が高まり、処理時間が短縮される。

【００５６】さらに、上述の配線処理方法を図９乃至図
１４により詳述する。図９はチップ１上の接続要求のあ
る端子の分布を表し、同じ番号を持つものは互いに接続
要求のある端子を表す。また、図中、太線は新たに施さ
れた配線を表し、点線はすでに施されている配線を表し
ている。

【００５７】まず、チップ１上に分割線２₁ を設定し、
領域を１_-1，１_-2の２つの領域に分割する。分割線２₁
を横切る端子対１−１，２−２，３−３，４−４を一つ
のプロセッサに割り当て、配線処理を実行する（図１
０）。

【００５８】次いで、分割線２₂ を設定し、分割領域１
_-1，１_-2をそれぞれ１_-11 ，１_-12 ，１_-21 ，１_-22 に
分割する。各分割領域１_-11 ，１_-12 間を結ぶ端子５−
５および１_-21 ，１_-22 間を結ぶ端子６−６に関する情
報をそれぞれ異なるプロセッサＣＰＵ₁ ，ＣＰＵ₂ に割
り当て並列に配線処理を施す（図１１）。

【００５９】同様にして、分割線２₃ ，２₄ ，２₅ ，２
₆ を設定し、予め決められた分割領域数あるいは分割領
域サイズになるまで各分割線を横切る配線を並列に処理
する（図１２，図１３）。

【００６０】最後に、各分割領域内部に閉じられた配線
１３−１３，１４−１４，１５−１５を各領域毎に並列
に配線処理を施し、全体の配線を完了する（図１４）。

【００６１】次に、かかる配線処理方法による配線の速
度向上比、つまり並列化率を求める。但し、配線の逐次
処理の比率が５％、４つの領域に分割され、分割された
領域と同数のプロセッサを使用し、各分割領域境界を横
切る配線および処理の最終段階における各分割領域内の
配線が並列に処理され、端子はチップ全面に均一に分布
するものとする。

【００６２】即ち、第１回目の分割線を横切る配線は全
配線の５％程度なので、この配線を処理するには、全体
の配線を処理するときの５％程度の処理時間で済む。次
の段階では２つの分割線があるが、これら２つの分割線
を横切る配線の処理は並列的に処理されるため、処理時
間は１つの分割線を横切る配線処理の時間となる。

【００６３】分割線を横切る配線を処理する時間は、最
初の分割で２つの領域に分けられるので、各領域内には
全配線の４７．５％に相当する分が存在する。その領域
を分割線で２つの領域に分けるので、分割線を横切る配
線数は４７．５％の５％となり、全配線に対しては、
２．３７％になる。最後に４つの各分割領域内の配線を
並列に処理する。このとき、一つの分割領域内の配線に
掛かる時間は、分割領域内の配線が全配線の（４７．５
ー２．３７）／２なので、２２．５６％となる。

【００６４】従って、３段階に分け、かつ各段階で並列
に処理した場合の処理時間は５．０＋２．３７＋２２．
５６＝３０．０となり、逐次処理による配線方法での処
理時間の３０％で済む。よって、４つのプロセッサを用
いて並列に処理することにより３．３倍の高速化が図れ
る。

【００６５】さらに、図１５は逐次処理の比率が５％お
よび１０％におけるプロセッサ数と速度向上比との関係
図であり、プロセッサ数の増大に伴い高並列度が達成さ
れ、処理時間が短縮されることが分かる。

【００６６】

【発明の効果】以上説明したように、第１の発明によれ
ば、見積もられた配線の混雑度により、混雑する部分を
含むように基板上を区切るための領域の大きさを設定
し、大きさの異なる領域毎に配線を行うので、配線のシ
ョート等の失敗が少ない配線結果を短時間に得ることが
でき、効率的な配線処理ができる。

【００６７】また、第２の発明によれば、配線の混雑が
予測される部分の占める割合が均一になるように、半導
体基板を区切るための領域の大きさや位置を設定し、設
定した領域毎に配線を行うので、配線のショート等の失
敗が少ない配線結果を得ることができる。

【００６８】さらに、第３の発明によれば、配線を複数
のコンピュータで並列的に処理するので、処理時間が短
縮できる。

【図面の簡単な説明】

【図１】第１の発明の配線処理方法のフローチャ−トで
ある。

【図２】第１の発明のチップのモデルを示す図である。

【図３】第１の発明の配線のために区切られた領域を示
す図である。

【図４】第２の発明の自動配線処理方法のフローチャー
トである。

【図５】第２の発明の初期設定後の配線領域を示す図で
ある。

【図６】第２の発明の位置調整後の配線領域を示す図で
ある。

【図７】第２の発明の他の実施例による配線領域を示す
図である。

【図８】第３の発明の他の配線処理方法を説明する図で
ある。

【図９】第３の発明の接続要求のある端子の分布図であ
る。

【図１０】第３の発明のチップ上を配線領域で区切った
状態を示す図である。

【図１１】第３の発明のチップ上を配線領域で区切った
状態を示す図である。

【図１２】第３の発明のチップ上を配線領域で区切った
状態を示す図である。

【図１３】第３の発明のチップ上を配線領域で区切った
状態を示す図である。

【図１４】第３の発明のチップ上を配線領域で区切った
状態を示す図である。

【図１５】プロセッサ数と速度向上比との関係図であ
る。

【図１６】配線領域の大きさと配線処理時間との関係を
示す特性図である。

【図１７】配線領域の大きさと配線のショート数との関
係を示す特性図である。

【図１８】従来の配線例を説明する図である。

【図１９】従来の配線例を説明する図である。

【図２０】従来の配線例を説明する図である。

【図２１】従来の配線例を説明する図である。

【図２２】従来の、一定の大きさで区切られた領域を示
す図である。

【図２３】図２２で示した領域７〜９の拡大図である。

【図２４】従来の接続要求のある端子の分布図である。

【図２５】従来の配線例を説明する図である。

【図２６】従来の配線例を説明する図である。

【符号の説明】

１，３ チップ ２₁ ，２₂ ，２₃ ，２₄ ，２₅，２₆ 分割線 ４ Ｉ／Ｏセル ５ 機能セル列 ６，７，８，８´，９ 領域

Claims (3)

【特許請求の範囲】
1. 【請求項１】 基板上における配線の混雑度を見積も
   り、配線の混雑度が所定値より高い部分では配線が成功
   し易いように基板上を区切るための領域を所定値より大
   きく取り、配線の混雑度が所定値より低い部分では配線
   の処理時間が最小となるように基板上を区切るための領
   域を所定値より小さく取り、これら大きさの異なる領域
   毎に配線を行い、基板全体の配線を完了することを特徴
   とする自動配線処理方法。
2. 【請求項２】 基板上の配線が混雑する部分を予測し、
   混雑すると予測された部分の占める割合が各領域で均一
   になるように、基板上を区切るための領域の大きさや位
   置を設定し、設定した領域毎に配線を行い、基板全体の
   配線を完了することを特徴とする自動配線処理方法。
3. 【請求項３】 基板上を複数の領域に順次分割し、各分
   割領域間を横切る配線を各分割領域の境界毎にそれぞれ
   異なるコンピュータで並列的に処理し、予め定めた分割
   領域数あるいは分割領域サイズに達したら各分割領域内
   部の配線をそれぞれ異なるコンピュータで並列的に処理
   することを特徴とする自動配線処理方法。