JPH06204338A - 半導体集積回路の配線方法 - Google Patents

Abstract

(57)【要約】 【目的】大規模半導体集積回路の自動配線処理方法に適
応し、処理時間の短縮，計算機の使用メモリの最小化を
計ること。 【構成】配線の通過経路の概略を決定する概略配線方法
と、その結果に従って、実際の配線敷設位置を決定する
詳細配線方法とを有する半導体集積回路の配線処理方法
であって、その概略配線処理方法が、半導体集積回路チ
ップ上の全配線領域を対象とした全体概略配線１０３，
その結果に従って半導体集積回路チップ上の部分領域に
対して行なわれる部分領域概略配線１０６等より構成さ
れる。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は半導体集積回路の配線方
法に関し、特に計算機を使用して行う自動配線処理に有
効な配線処理方法に関する。

【０００２】

【従来の技術】この種の半導体集積回路の配線処理方法
としては、迷路探索法やラインサーチ法など種々のもの
が発表されているが、近年半導体集積回路の大規模化に
伴い、その配線領域の面積増大化，配線層の多層化がな
されてきており、半導体集積回路チップ上の配線領域全
面を前記方法のみによって一括で処理することは、処理
時間や計算機の使用メモリの増大を招き、困難になりつ
つある。

【０００３】従来、この種の問題を解決するために、半
導体集積回路チップ上の配線領域を複数の部分領域に分
割し、この部分領域内を前記手法の一括処理対象領域と
する方法がある。この処理方法によると、図８にフロー
チャートを示す通り、実際に配線処理を実行する前に、
入力データ８０の概略配線用矩形生成８１，概略配線８
２といわれる処理手順を設け、大体の配線通過領域を決
定した後、その結果を基に詳細配線処理といわれる処理
手順８３，８４，８５の手順で、前記迷路配線法やライ
ンサーチ法といった処理手順を各部分領域毎に繰り返し
実行することにより、全配線領域の配線を処理する方法
が開発されている。

【０００４】以下、このような概略配線方法，詳細配線
方法について、図面を参照して説明する。図９が半導体
集積回路チップ上の配線領域をシンボリックに表わした
平面図で、図中点線で区切られた矩形の１つ１つが、概
略配線時に配線経路を割り当てるための領域である。以
下、図示の通り、列方向にａ，ｂ，ｃ，…，行方向に
１，２，３，…，と付け、各矩形領域を（ａ，１），
（ｂ，２），…，等と呼ぶ。

【０００５】すなわち、概略配線処理８２においては、
半導体集積回路チップ上の全配線領域を対象として、ど
の矩形領域を使用して各配線を敷設するかの決定を行
う。この配線経路決定に際しては、各矩形領域の配線密
度を極力均等にすること、各配線が通過する矩形領域の
数を極力少くすること等、いくつかの事前に設定された
諸条件を最大限満足することを目的に決定していく。

【０００６】本処理結果について、端子Ａと端子Ｂの間
の配線に対して例示したのが図中の斜線部であり、この
配線は（ａ，１），（ｂ，１），（ｃ，１），（ｃ，
２），…を使用して配線される様に決定されたことを示
している。この様な経路決定が全ての配線に対して行な
われる。

【０００７】次に詳細配線処理について説明する。詳細
配線処理では半導体集積回路チップ上の配線領域を分割
して、その部分領域に対して、前記迷路探索法等を利用
して実際の配線を敷設していく。この領域分割の際、各
部分領域において、境界に位置する概略配線用の矩形領
域を隣りの部分領域と共有する様に分割する。この分割
方法を例示したのが、図中ｈ，ｉ，ｊと８，９，１０と
であり、以下詳細配線では、この分割された（ｈ，
８），（ｉ，４），…の部分領域毎に繰り返し実行され
る。

【０００８】各部分領域における詳細配線８４では、概
略配線８２によってその部分領域内の矩形に割り当てら
れている配線の敷設位置の決定をその部分領域の内部で
のみ行なっていき、隣接する部分領域の配線が終了して
いれば、その部分領域へ抜けていく配線については、共
有する概略配線用の矩形領域内で接続され、終了してい
なければ、この部分領域の配線処理では、各配線が割り
当てられている共有矩形領域の任意の位置まで引き出し
ておき、その隣接する部分配線領域での配線処理の際
に、同配線が接続される様に処理される。

【０００９】

【発明が解決しようとする課題】この従来の配線方法に
よると、概略配線時の配線経路割り当てのための各矩形
領域を細かく設定すれば、全配線領域にわたる配線経路
決定を詳細に行なうことになるので、より最適化された
概略配線結果が得られるので、詳細配線処理での負担は
軽減される。

【００１０】しかし、このことは、概略配線時に検討を
しなければならない矩形領域の数が増大することを意味
するので、概略配線時の処理時間やプログラムの使用す
るメモリ空間などが増大する。

【００１１】また、逆に各矩形領域を大きく設定すれ
ば、概略配線の負担は軽減されるが、詳細配線において
経路探索を行なわなければならない部分領域が広くなる
ことを意味するので、詳細配線時の処理時間やプログラ
ムの使用するメモリ空間等が増大する。

【００１２】すなわち、この従来の配線方法では、概略
配線用の矩形や詳細配線用の分割領域の大きさ等の設定
が処理効率向上のために重要であるが、近年のさらなる
半導体集積回路の大規模化に伴い、この従来の方法にお
いても、処理時間及び使用メモリの増大に直面してい
る。

【００１３】本発明の目的は、前記問題点が解決され、
処理時間が短縮でき、使用メモリも増大せずに済むよう
にした半導体集積回路の配線方法を提供することにあ
る。

【００１４】

【課題を解決するための手段】本発明の構成は、半導体
集積回路のチップ上に配置された機能ブロック間の配線
を接続する半導体集積回路の配線方法において、前記配
線の通過経路を大まかに決定するため、前記半導体集積
回路のチップ上の全配線領域にわたって処理を行う概略
配線処理方法と、前記概略配線処理方法の結果に基づい
て前記半導体集積回路のチップ上の配線領域の部分領域
に対して前記概略配線処理方法より詳細に配線敷設位置
の決定を行う配線処理方法とを備えたことを特徴とす
る。

【００１５】

【実施例】次に、本発明について図面を参照して説明す
る図１は本発明の一実施例の半導体集積回路の配線方法
を示すフロー図である。

【００１６】図１において、本実施例では、本処理シス
テムの入力データ１０１に、回路接続情報，配置位置情
報や設計ルール等の処理システムが必要とするすべての
情報が含まれており、全体概略配線１０３，部分領域概
略配線１０６，詳細配線１０８等が示されている。

【００１７】本処理システムでは、全体概略配線用矩形
生成１０２に続く全体概略配線１０３によって半導体集
積回路チップ上の全配線領域に対して、部分領域概略配
線領域分割１０４，矩形生成１０５を行って最も粗い概
略配線を終了し、次に部分領域概略配線１０６によっ
て、全体概略配線１０３より詳細な概略配線をチップ上
の適当に分割された部分領域毎に繰り返し実行し（処理
１０７）、詳細配線１０８で実際の配線敷設位置を決定
して処理を終了する。

【００１８】次に、本処理について、具体的に各処理工
程の作業分担と処理手順を、半導体集積回路のチップ上
の配線領域をシンボリックに表わした図２を使用して説
明する。図２の全体が半導体集積回路チップ上の全配線
領域を示しており、一例として、端子Ａと端子Ｂを結線
する配線を用いて具体的に説明する。

【００１９】本処理システムでは、初めに全体概略配線
用の矩形領域を図１の全体概略配線用矩形生成１０２の
処理によって、全配線領域をメッシュ状に分割すること
により生成する。このメッシュを具体的に示したのが、
図２の点線であり、以下図示の通り列方向にａ，ｂ，
ｃ，…，行方向に１，２，３，…，と付け、各分割領域
を（ａ，１），（ｂ，２），…，等と呼ぶことにする。

【００２０】次に、図１の全体概略配線１０３によっ
て、半導体集積回路のどの矩形領域を通過して配線をす
るかを決定する。この処理結果を端子ＡとＢを結線する
配線に対して例示したのが、図３で、図中の斜線を付し
た矩形領域が選ばれたことを示している。

【００２１】次に、部分領域概略配線用領域分割１０４
の処理により、部分処理概略配線用の領域分割を行う。
本処理を例示したのが図４で、列方向にｈ，ｉ，ｊ，行
方向に８，９，１０の分割を行い、（ｈ，８），（ｈ，
９），…，（ｊ，１０）の９つの部分領域に分割された
ことを示している。本処理では、各分割領域間での整合
性をとるために、隣接する部分領域で、全体概略配線用
の矩形領域が共有される様に分割される。

【００２２】次に、図１の部分領域概略配線用矩形生成
１０５の処理により、部分領域概略配線用の矩形を生成
する。本処理では、全体概略配線用の矩形より小さな矩
形を生成することにより、次の部分領域概略配線によ
り、全体概略配線より、詳細に配線割り当てができるよ
うにする。本処理を例示したのが図５で、この図５は分
割領域（ｈ，８）の拡大図であり、図２〜図４と同一添
字は同じものを表わしている。図中一点鎖線で表わした
ものが、本処理での分割領域を示しており、列方向にａ
１，ａ２，…，行方向に１１，１２，…，に分割してい
ることを示している。

【００２３】次に各分割領域毎に、部分領域概略配線１
０６を繰り返し、分割領域概略配線を実行する。ここで
は、（ｈ，８）の分割領域を用いて本処理を具体的に説
明する。本処理においては、図１の全体概略配線１０３
によって（ｈ，８）の領域に割り当てられている全配線
に対して処理１０５で分割して、（ａ１，１１），（ａ
２，１１），…，等の矩形に対して通過配線の割り当て
を行う。この割り当て処理は全体概略配線１０３によっ
て割り当てられている（ａ，１），（ｂ，２），…，等
の全体概略配線用矩形に包含されている部分領域概略配
線用矩形に割り当てる様に実行され、端子Ａ，Ｂ間の配
線の様に、各分割領域にまたがって結線されるべき配線
の場合、隣接する部分概略配線用分割領域の概略配線が
終了していなければ共有する全体概略配線用矩形領域内
の任意の部分領域概略配線用矩形の割り当てまでを行
い、概略配線が終了していれば、その割り当てられてい
る部分概略配線用の矩形に接続される様に割り当てが行
なわれる。

【００２４】本処理を、端子Ａ，Ｂ間の配線に対して例
示したのが、図６で右下がりの斜線部が全体概略配線に
よって割り当てられた矩形を示し、左下がりの斜線部が
部分領域概略配線によって割り当てられた矩形を示して
いる。このように端子Ａの点を出発する配線は、（ａ
２，１２），（ａ３，１２），（ａ３，１３），…，と
割り当てられ、隣接する部分領域の概略配線が施されて
いないので、（ｃ４，３３）まで割り当てられて終了し
ている。

【００２５】この様にして、全配線領域に対して部分領
域概略配線が終了すると、この部分領域概略配線の結果
に基づき、図１の詳細配線１０８によって、従来と同様
の方法によって具体的な配線敷設位置を決定することに
より、半導体集積回路の配線処理を終了する。

【００２６】以上のように、本実施例の配線処理方法に
おいては、半導体集積回路チップ上の全配線領域に対し
て概略配線を実行し、その処理結果を基に、適当に分割
した部分領域毎に、より詳細な概略配線を実施すること
により、よって階層的に概略配線を行う手段を有してい
る。

【００２７】次に、図７を参照して、本発明の他の実施
例の配線方法を説明する。図７において、本発明の他の
実施例は、部分概略配線処理が各部分領域毎に処理され
るという特徴を利用して、部分概略配線処理の並列処理
化を行なっている。

【００２８】ここで、第１の計算機７０と第２の計算機
９０とが用意される。第１の計算機７０では、まず全体
概略配線用矩形生成７２，全体概略配線７３，部分領域
概略配線用領域分割７４，部分領域概略配線用矩形生成
７５と順次図１と同様な処理を行う。

【００２９】さて、次の部分領域概略配線処理依頼７６
を第２の計算機９０に対して行い、第２の計算機９０で
は部分領域概略配線９１，終了報告９２を第１の計算機
７０に対して行う。第１の計算機７０では、部分領域概
略配線７７を行い、全領域が終了するまで繰り返す（処
理７８）。最後に、詳細配線７９を行って、終了する。

【００３０】このように、本実施例においては、計算機
を複数使用して部分概略配線処理を並列化することによ
り、さらに高速処理化を達成することができる。

【００３１】

【発明の効果】以上説明したように、本発明は、半導体
集積回路チップ上の全配線領域に対して概略配線を実行
し、その処理結果を基に、適当に分割した部分領域毎
に、より詳細な概略配線を実施することによって、階層
的に概略配線を行う手段を有しているので、以下の説明
の通り、処理時間の短縮，プログラムの使用メモリの最
小化を計れる。

【００３２】迷路探索法によって配線経路を決定する処
理方法の場合に、全配線領域を一括して迷路探索法によ
り配線を実行する場合、従来の方法によって概略配線を
施し、迷路探索法により詳細配線を実行する場合と、本
発明によって全体概略配線，部分領域概略配線を施し、
迷路探索法により詳細配線を実行する場合とについて、
処理時間及びメモリ使用量の概略を見る。

【００３３】迷路探索法においては、半導体集積回路の
配線領域に対して水平方向，垂直方向にメッシュ状に配
線用の格子（配線格子）を設定し、この縦横の格子の交
点（格子点）に対して各配線の通過の可否を判断して前
記配線格子上に配線を割り当てることにより、配線経路
を決定する。従って、その処理時間は、入力処理，出力
処理等を除き、主に線格子点数ｒの２乗と総配線本数Ｐ
に依存し、Ｐ×（ｒの２乗）のオーダを持つことにな
る。また、処理中のメモリ量も各格子点毎に配線通過の
可・不可を持つため、ｒの２乗に依存する。

【００３４】また、ここでは簡単化のため、概略配線に
おいても概略配線用の矩形領域に対する配線経路の割り
当てを迷路探索法と同様な手法で行うこととし、違いは
１つの概略配線用の矩形領域に対して複数の配線を割り
当て得ることと考えて、配線数をＰ，矩形数をｎの２乗
としたとき、処理時間はＰ×（ｎの２乗）、メモリ使用
量はｎの２乗に依存するものと考える。

【００３５】初めに、全配線領域に対して一括して迷路
探索法で処理する場合、半導体集積回路の総配線本数を
Ｐ，水平方向配線格子ｒ本，垂直方向配線格子ｒ本，総
格子点数ｒの２乗個とすると、一格子の探索に要する時
間をｔ，格子点当りのメモリ使用量をａとした場合、処
理時間Ｔｍ，最大使用メモリＭｍは、次式となる。

【００３６】 Ｔｍ＝Ｐ×ｔ×（ｒの２乗） Ｍｍ＝ａ×（ｒの２乗） 従来方式の概略配線処理のときは、詳細配線用の部分領
域として半導体集積回路の配線領域をｍ×ｍと分割し、
簡単化のため、この部分領域と概略配線用矩形を同一化
させた場合を考える。

【００３７】概略配線処理では、概略配線用矩形がｍの
２乗個あるので、概略配線用矩形当りのメモリ使用量を
ｂとすると、処理時間Ｔｕ１，使用メモリＭｕ１は、次
式となる。

【００３８】 Ｔｕ１＝Ｐ×ｔ×（ｍの２乗） Ｍｕ１＝ｂ×（ｍの２乗） また、詳細配線処理では、詳細配線用の部分領域に含ま
れる格子数がｒ／ｍ本，格子点が（ｒの２乗）／（ｍの
２乗）個、また、概略配線によってある部分領域に割り
当てられる配線の平均本数は面積に比例して、Ｐ／（ｍ
の２乗）本となるので、処理時間Ｔｕ２，使用メモリＭ
ｕ２は、次式となる。

【００３９】

【００４０】詳細配線用部分領域が、（ｍの２乗）個あ
るので、総処理時間は、次式となる。

【００４１】

【００４２】ここで、この式はｍ＝ｒの平方根のとき最
小となり、次式となる。

【００４３】Ｔｕ＝２Ｐｔｒ このとき、最大使用メモリＭｕは、次式となる。

【００４４】Ｍｕ＝ｍａｘ（Ｍｕ１，Ｍｕ２）＝ｍａｘ
（ｂｒ，ａｒ） 本発明の実施例による配線方法の場合、部分概略配線用
の領域としてｎ×ｎに分割し、さらに、ｍ×ｍに分割し
て詳細配線用部分領域にすると、同様の計算方法によ
り、全体概略配線用矩形当りのメモリ使用量をＣとする
と、全体概略配線の処理時間Ｔｐ１，メモリ量Ｍｐ１
は、次式となる。

【００４５】

【００４６】部分概略配線用矩形当りのメモリ使用量を
ｄとすると、部分概略配線時の処理時間Ｔｐ２，メモリ
使用量Ｍｐ２は、次式となる。

【００４７】

【００４８】このように、一括迷路探索法の場合“ｒの
２乗”、従来方法の場合“ｒ”、本発明の実施例の場合
ｒの２／３乗に従って、処理時間，最大使用メモリが増
加していくことがわかる。ここで、ｒは半導体集積回路
上の配線格子数を表わしているので、本発明の効果は、
配線格子数が大きいとき、すなわち大規模な半導体集積
回路ほど、適応の効果が著しいことを示している。

【図面の簡単な説明】

【図１】本発明の一実施例の半導体集積回路の配線方法
を示すフロー図である。

【図２】本発明の一実施例の全体概略配線用矩形領域を
示す半導体集積回路をシンボリックに示す平面図であ
る。

【図３】本発明の一実施例の全体概略配線の処理例を示
す半導体集積回路をシンボリックに示す平面図である。

【図４】本発明の一実施例の部分概略配線実行用の分割
領域を示す半導体集積回路をシンボリックに示す平面図
である。

【図５】本発明の一実施例の部分概略配線用矩形領域を
拡大してシンボリックに示す平面図である。

【図６】本発明の一実施例の部分概略配線の処理例を拡
大してシンボリックに示す平面図である。

【図７】本発明の他の実施例を示すフロー図である。

【図８】従来の半導体集積回路の配線方法を示すフロー
図である。

【図９】図８の従来の配線方法を示す半導体集積回路の
平面図である。

【符号の説明】

８０，１０１ 入力データ ７２，８１，１０２ 矩形生成 ７３，８２，１０３ 全体概略配線 ７４，８３，１０４ 領域分割 ７５，１０５ 部分矩形生成 ７７，９１，１０６ 部分概略配線 ７８，８５，１０７ 処理 ７９，８４，１０８ 詳細配線 Ａ，Ｂ 端子 ７０，９０ 計算機 ７６ 処理依頼 ９２ 終了報告

Claims (2)

【特許請求の範囲】
1. 【請求項１】 半導体集積回路のチップ上に配置された
   機能ブロック間の配線を接続する半導体集積回路の配線
   方法において、前記配線の通過経路を大まかに決定する
   ため、前記半導体集積回路のチップ上の全配線領域にわ
   たって処理を行う概略配線処理方法と、前記概略配線処
   理方法の結果に基づいて前記半導体集積回路のチップ上
   の配線領域の部分領域に対して前記概略配線処理方法よ
   り詳細に配線敷設位置の決定を行う配線処理方法とを備
   えたことを特徴とする半導体集積回路の配線方法。
2. 【請求項２】 詳細配線処理方法が、複数の計算機の並
   列処理で行われる請求項１に記載の半導体集積回路の配
   線方法。