JPH0786406A - 半導体装置の概略配線決定方法 - Google Patents

Abstract

(57)【要約】 【目的】 アナログ回路を含むＬＳＩの自動配線方法に
おいて、短時間でネットの処理手順に依存せず、アナロ
グ回路に対して要求される条件を満足する配線経路を決
定する自動配線方法を提供する。 【構成】 ステップＳ１でチャネルグラフが作成され
る。ステップＳ２でチャネルグラフ上に配された素子と
全ノードとの最短距離をコストに換算したコストテーブ
ルが作成される。ステップＳ３でネット毎の配線経路候
補がリストアップされる。ステップＳ４でネットの処理
順序が決定される。そしてステップＳ５で全ネットを通
じた配線経路が決定される。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、要求仕様の厳しいアナ
ログＬＳＩ（大規模集積回路）やアナログ・デジタル混
載ＬＳＩ、例えば高周波通信用ＬＳＩに適した自動配線
方法に関し、特に概略配線経路を決定する方法に関す
る。

【０００２】

【従来の技術】従来、デジタルＬＳＩ等において、素子
レベルの自動配線をＣＡＤ（ＣｏｍｐｕｔｅｒＡｉｄｅ
ｄ Ｄｅｓｉｇｎ）により行う場合、迷路法等の方法に
より詳細な配線経路を求めていた。

【０００３】この迷路法によると、最終結果の品質が、
同電位の配線要求（以下、ネットと呼ぶ）の処理順序に
より決定されてしまうという問題があった。具体的に
は、決定済みの配線経路の存在がその後に必要な配線経
路の障害になるという問題があった。

【０００４】

【発明が解決しようとする課題】この迷路法を用いて、
アナログＬＳＩやアナログ・デジタル混載ＬＳＩにおい
て、詳細な配線経路を求めようとすると、アナログ回路
に対して厳しく要求される条件（対基板容量、配線寄生
抵抗等）を満足する解（配線経路）が得られるという保
証がないという問題があった。

【０００５】さらに、得られた配線経路が所望の条件
（評価関数）に対して最適なもの（最適解）であるとい
う保証がないという問題があった。

【０００６】最適解を保証するには総当たりで順次解
（候補）を調べる手法をとらざるを得ないが、これには
莫大な時間がかかる。

【０００７】従って本発明の目的は、アナログＬＳＩや
アナログ・デジタル混載ＬＳＩにおいて、迷路法等の方
法により直接詳細な配線経路を求めるのではなく、その
前に、概略配線経路を求め、短時間でネットの処理順序
に依存せず、アナログ回路に対して要求される条件を満
足する解が得られる自動配線方法を提供するものであ
る。

【０００８】

【課題を解決するための手段】本発明の概略配線方法
は、チャネルグラフのチャネル上の全ノードからチャネ
ルグラフ上に配された素子への最短距離を測定する工程
と、前記最短距離を基に、同電位の配線要求を満たす配
線経路を少なくとも１つ探索する工程と、前記探索され
た配線経路を基に、異なる電位の配線要求の処理順序を
決定する工程と、前記決定した順位において、最適な配
線経路の組合わせを選択する工程とを備える。

【０００９】好適な実施例ではまず公知の方法によりチ
ャネルグラフが作成される。そしてチャネルグラグ上の
全ノードから全素子への最短距離をコストに換算したコ
ストテーブルが用意される。次にコストテーブルを参照
して分枝限定法によってネット毎の配線経路候補をリス
トアップする。この配線経路候補数によって配線処理を
行うネットの順番を決定する。ここでは配線経路候補数
の少ない順とする。そして分枝限定法によって全ネット
に対し、配線処理順序が決定したネット順にネット毎に
配線経路候補の中から配線経路を１つ選択することによ
り全ネットの配線経路が決定される。

【００１０】

【作用】上記方法によれば、コストテーブルを参照する
ことにより電気的制約条件を満足するネット毎のすべて
の配線経路候補が効率的に求められる。配線処理を行う
ネットの順番は配線経路候補数の少ない順とするので配
線処理時間が短縮される。そして分枝限定法によって全
ネットを通じて最適な配線経路が決定される。

【００１１】

【実施例】本発明の半導体装置の概略配線決定方法の実
施例を図面を参照して説明する。

【００１２】図１は本発明の半導体装置の概略配線決定
方法の全体的な処理手順を示すフローチャートである。

【００１３】従来のようにして、所望の電気的仕様によ
り回路設計及び各素子のレイアウトが決定すると、ステ
ップＳ１で、公知の方法によりチャネルグラフが作成さ
れる。

【００１４】図２はチャネルグラフを示しており、トラ
ンジスタ、抵抗そしてキャパシタ等の素子１〜６が所望
の電気的仕様を満たし、チップ面積が最小になるような
位置関係で配置されている。そして各素子は配線用端子
１ａ，１ｂ，１ｃ〜６ａ，６ｂ，６ｃを有している。

【００１５】各素子を素子間の配線可能領域を抽象化し
たチャネルＣ１〜Ｃ１８が取り囲んでおり、それらのチ
ャネルは各ノードＮ１〜Ｎ１３により互いに接続されて
いる。さらに各配線用端子１ａ，１ｂ，１ｃ〜６ａ，６
ｂ，６ｃ上にノードＮ１ａ，Ｎ１ｂ，Ｎ１ｃ〜Ｎ６ａ，
Ｎ６ｂ，Ｎ６ｃが設けられ、各配線用端子上のノードか
ら隣接するチャネルに垂線を降ろした位置にはノードＮ
１４〜Ｎ４９が設けられている。なお各チャネルは、そ
の上に設けられたノードにより、さらに複数のチャネル
に分割される。そして各配線用端子上のノードと、これ
に垂直な位置関係にあるチャネル上のノードとを結ぶ図
２に点線で示した経路もチャネルとなる。さらに、例え
ばノードＮ２３から素子３上を通過してチャネルＣ７上
の図示しないノードとを結ぶ経路もチャネルとすること
ができる。

【００１６】なおこのチャネルグラフは、所望の電気的
仕様により決定された配線用端子上のノードの各々か
ら、それらに隣接するノード（上記垂直な位置関係にあ
るチャネル上のノード）までの距離や各ノード間の距離
を基にして決定される。具体的には、ノードＮ１ａから
ノード１４，Ｎ１７及びＮ２０までの距離やノードＮ４
ａからノードＮ３０，Ｎ３５、Ｎ３７までの距離やノー
ドＮ１〜Ｎ１４〜Ｎ２までの距離がコストに換算して決
定されている。

【００１７】次にステップＳ２で、ノードＮ１〜Ｎ４９
からすべての配線用端子上のノードＮ１ａ，Ｎ１ｂ，Ｎ
１ｃ〜Ｎ６ａ，Ｎ６ｂ，Ｎ６ｃへの最短距離を表すコス
トテーブルが作成される。

【００１８】図３はノードＮ１〜Ｎ４９の中のある１つ
のノードのコストテーブルを示している。このテーブル
の左欄の端子名であるｔｅｒｍ１〜１５が配線用端子１
ａ，１ｂ，１ｃ〜６ａ，６ｂ，６ｃ に各々対応してお
り、右欄はノードＮ１〜Ｎ４９の中のある１つのノード
から各ｔｅｒｍ１〜１５上のノードＮ１ａ，Ｎ１ｂ，Ｎ
１ｃ〜Ｎ６ａ，Ｎ６ｂ，Ｎ６ｃへの最短距離をコストに
換算して示している。

【００１９】次にステップＳ３で、作成されたコストテ
ーブルを用いて分枝限定法によってネット毎のすべての
配線経路候補をリストアップする。

【００２０】次にステップＳ４で、リストアップされた
配線経路候補数を参照して配線処理を行うネットの順番
を決定する。ここでは配線経路候補数の少ないネット順
とし、そして配線経路候補数が同じネットが複数ある場
合は配線距離の長いネットを優先する。

【００２１】次にステップＳ５で、分枝限定法によって
全ネットに対し、配線処理順序が決定したネット順にネ
ット毎に配線経路候補の中から配線経路を１つ選択す
る。これにより全ネットの配線経路が決定される。

【００２２】図４に示すフローチャートによって、図１
のステップＳ２で作成されるコストテーブルの作成手順
を説明する。

【００２３】ステップＳ２１で、ノードＮ１〜Ｎ４９の
すべてのコストテーブルの最低コストを初期化して無限
大にする。

【００２４】次にステップＳ２２で、図２のチャネルグ
ラフ作成時に分かっていた配線用端子上のノードから隣
接するノード（垂直な位置関係にあるノード）までの距
離に相当するコストデータをそれらの隣接ノードに通知
する。

【００２５】次にステップＳ２３で、各隣接ノードにお
いて通知されたデータとその隣接ノードのコストテーブ
ルの最低コスト欄に記入済みの既知データとを比較す
る。

【００２６】比較の結果、前者が後者より小さい場合は
ステップＳ２４に進み、その記入済みのデータを通知さ
れたデータに更新する。なお前者が後者より大きい場合
はステップＳ２６にジャンプする。

【００２７】次にステップＳ２５で、その隣接ノードの
更新データを、図２のチャネルグラフ作成時に分かって
いたその隣接ノードと次の隣接ノードとの距離に相当す
るコストデータに加算してその次の隣接ノードに通知す
る。

【００２８】次にステップＳ２６で、通知データがある
か否か判断する。

【００２９】判断の結果、通知データがない場合はこの
プログラムを終了する。

【００３０】まだ通知データがある場合はステップＳ２
３に戻る。

【００３１】図２のチャネルグラフを用いてコストテー
ブルの作成方法を具体的に説明する。

【００３２】ノードＮ１〜Ｎ４９の全てのコストテーブ
ルの最低コストを初期化して無限大にする。（ステップ
Ｓ２１） 例えば配線用端子１ａ上のノードＮ１ａから、これに隣
接するノードＮ１４、Ｎ１７及びＮ２０までの距離に相
当するコストが各々１０、１５そして１５であると、こ
れらのコストデータをノードＮ１４、Ｎ１７及びＮ２０
のすべてに通知する。（ステップＳ２２） これらのコストデータを各々ノードＮ１４、Ｎ１７及び
Ｎ２０のコストテーブルの最低コスト欄に初期化で与え
られたデータ（無限大）と比較する。（ステップＳ２
３） これらのコストデータは初期値であるデータ（無限大）
より小さいので、ノードＮ１４、Ｎ１７及びＮ２０のコ
ストテーブルの配線用端子１ａ上のノードＮ１ａに相当
する端子名ｔｅｒｍ１の最低コストデータを各々１０、
１５そして１５に更新する。（ステップＳ２４） 次に例えばノードＮ２０の更新データ１５をノードＮ２
０から次の隣接ノードＮ２までの距離に相当するコスト
データ例えば５に加算したデータ２０をノードＮ２に通
知する。（ステップＳ２５） 次に各ノードに通知データがあるか否か判断する。（ス
テップＳ２６） 例えばノードＮ２には配線用端子１ａ上のノードＮ１ａ
からノードＮ１７，Ｎ１そしてＮ１４を介した通知デー
タ例えばコストデータ５０もあるので、ステップＳ２３
に戻り、この通知データと既知データである加算データ
２０とを比較する。

【００３３】通知データ５０は既知データ２０より大き
いのでステップＳ２６にジャンプし、ノードＮ２に通知
データがあるか否か判断する。

【００３４】ノードＮ２には例えば配線用端子１ａ上の
ノードＮ１ａからノードＮ１７〜Ｎ５〜Ｎ６〜Ｎ７〜Ｎ
３そしてＮ１５を介したコストデータやノードＮ１ａか
らその他のノードを介したもコストデータ通知される。
そして配線用端子１ａ上のノードＮ１ａからノードＮ２
へのすべての経路に関するコストデータがノードＮ２へ
通知されるまでステップＳ２３〜Ｓ２６を繰り返す。

【００３５】ステップＳ２３での比較の結果これらの通
知データの中で最小となる通知データをノードＮ２のノ
ードＮ１ａへの最低コストデータとしてノードＮ２のコ
ストテーブルのterm１に対応する最低コストデータとし
て記入する。

【００３６】以上のステップを全配線用端子上の全ノー
ドからチャネル上の全ノードＮ１〜Ｎ４９に対して繰り
返し行いノードＮ１〜Ｎ４９のコストテーブルを作成す
る。

【００３７】図５に示すフローチャートによって、図１
のステップＳ３での配線経路候補リストアップの手順を
説明する。このフローチャートはある１つの配線開始端
子から他の１つの配線終了端子にのみ接続する２端子ネ
ットの場合の処理手順を示している。そして配線経路候
補は、配線開始及び終了端子上のノード識別子、両端子
間で通過するノード識別子そして両端子間の全コストデ
ータを含む配線経路情報を備える。

【００３８】ステップＳ３１で配線経路情報を初期化す
る。

【００３９】次にステップＳ３２で、配線開始端子上の
ノードに隣接するあるノードのコストテーブルを参照す
る。

【００４０】次にステップＳ３３で、配線開始端子上の
ノードからその隣接ノードまでの距離に相当するコスト
テーブルの最低コストデータにその隣接ノードから配線
終了端子上のノードまでの距離に相当するコストテーブ
ルの最低コストデータを加算し、加算結果を用いてその
隣接ノードから最短経路で配線終了端子まで接続して
も、対基板容量、配線寄生抵抗の上限で決まる、配線開
始端子から配線終了端子までの配線経路長制約条件を満
足するか判断する。ここでは、制約条件である所定配線
経路長より上記加算結果が短いか否かを判断し、長い場
合は配線経路候補から除外する。そして結果的に、ある
配線経路に対する候補が１つもないと判断された場合
は、配線経路全体に対して解がないということになるの
で、例えば処理を中断し素子を再配置する。

【００４１】なお、配線経路長が短すぎてもＬＳＩの電
気的特性に影響を与えるが、図２のチャネルグラフがそ
の問題を考慮して作成されているので、ここでは配線経
路長が長いことによるＬＳＩの電気的特性への影響を考
慮している。

【００４２】そこで配線経路長制約条件を満足する場合
はステップＳ３４に進み、配線経路情報にそのノード識
別子を追加しそして配線開始端子上のノードからそのノ
ードまでのコストデータを前データに加算する。

【００４３】なお配線経路長制約条件を満足しない場合
はステップＳ３２に戻り配線開始端子上のノードに隣接
する別のノードのコストテーブルを参照する。

【００４４】ステップＳ３４で配線経路情報が追加され
るとステップＳ３５に進み、配線開始端子が配線終了端
子に接続されたか判断する。ここでは各ノードから直接
接続可能な配線用端子上のノードが情報として与えられ
ており、この情報を参照して接続状況を判断する。

【００４５】接続されたと判断された場合はステップＳ
３６に進み、配線開始及び終了端子上のノード識別子、
両端子間で通過するノード識別子及び加算コストデータ
を経路情報として有する配線経路候補をリストアップす
る。そしてプログラムはステップＳ３２に戻り探索ステ
ップを継続し、別の配線経路候補を探索する。

【００４６】ステップＳ３５で、配線開始端子が配線終
了端子に接続されないと判断された場合は、現在処理中
のノードに隣接するノードに対してステップＳ３２から
適用し各ステップの処理を行い、配線開始端子が配線終
了端子に接続されるまで配線経路を探索して、配線経路
候補をリストアップする。

【００４７】上記説明した処理を配線開始端子毎、そし
てそれらの端子に隣接するノード毎に繰り返し行って、
すべての配線開始端子からの配線経路候補を探索する。

【００４８】なお多端子ネットの場合は図５に示した各
処理手順を分解して行う。

【００４９】図５を参照して説明した配線経路候補リス
トアップ処理手順を図２のチャネルグラフを参照して具
体的に説明する。

【００５０】図２において素子１の配線用端子１ａのノ
ードＮ１ａから素子３の配線用端子３ａ上のノードＮ３
ａに接続する２端子ネットを考える。この場合は、ノー
ドＮ１ａからノードＮ２０、Ｎ２，Ｎ１５，Ｎ３そして
Ｎ２３を介してノードＮ３ａに接続する経路が配線経路
候補の１つとして考えられる。

【００５１】そこでまずノードＮ１ａからノードＮ３ａ
までの配線経路情報を初期化する。（ステップＳ３１） 次にノードＮ１ａの隣接ノードであるノードＮ２０のコ
ストテーブルを参照する。（ステップＳ３２） ノードＮ１ａからノード２０までの距離はノードＮ２０
のノードＮ１ａに対する最低コストデータそのものであ
るのでこのデータとノードＮ２０のノードＮ３ａへの最
低コストデータを加算し、加算結果がノードＮ１ａから
ノードＮ３ａまでの配線経路長制約条件を満足するか判
断する。そしてこの場合にはその加算データが条件であ
る所定の長さより短いか否か判断する。（ステップＳ３
３） 短いと判断された場合は、経路情報にノードＮ２０を追
加し、ノードＮ１ａからノードＮ２０までのコストデー
タを初期化されたデータに加算する。（ステップＳ３
４） ここで長いと判断された場合は、ノードＮ２０を介する
経路は配線経路候補から除外して、例えばノードＮ１４
を介した経路を探索するためにノードＮ１４のコストテ
ーブルを参照する。（ステップＳ３２） 経路情報が追加されると、次に配線用端子１ａと３ａの
２端子が接続されたかを判断する。ノードＮ２０から直
接接続可能な配線用端子上のノード情報を参照するとノ
ードＮ２０は配線用端子３ａ上のノードＮ３ａには隣接
しておらず従って直接接続はできないので、ここでは２
端子は接続されていないと判断する。（ステップＳ３
５） そこで、ノードＮ２０に隣接するノードＮ２のコストテ
ーブルを参照する。（ステップＳ３２） 次に上記加算結果にノードＮ２のノード３ａへの最低コ
ストデータをさらに加算し、加算結果がノードＮ１ａか
らノードＮ３ａまでの配線経路長制約条件を満足するか
判断する。（ステップＳ３３） 短いと判断された場合は、経路情報にさらにノードＮ９
を追加し、そしてノードＮ２０、Ｎ２間のコストデータ
を前回加算されたコストデータにさらに加算する。（ス
テップＳ３４） ここで長いと判断された場合は、ノードＮ２０、Ｎ２を
介する経路は配線経路候補から除外して、例えばノード
Ｎ２０、Ｎ２１を介した経路を探索するためにノードＮ
２１のコストテーブルを参照する。（ステップＳ３２） 経路情報が追加されると、次に配線用端子１ａと３ａの
２端子が接続されたかを判断する。ノードＮ２は直接接
続可能配線用端子上のノード情報を参照すると配線用端
子３ａ上のノードＮ３ａには隣接しておらず従って直接
接続はできないので、ここでも２端子は接続されていな
いと判断する。（ステップＳ３５） ステップＳ３２からＳ３５を繰り返して、ノードＮ１
５，Ｎ３を介してＮ２３まで経路探索が進み、ステップ
Ｓ３５で配線用端子１ａと３ａの２端子が接続されたか
を判断すると、ノードＮ２３は直接接続可能配線用端子
上のノード情報を参照すると配線用端子３ａには接続可
能であるので２端子は接続されたと判断する。（ステッ
プＳ３５） そして配線開始及び終了ノードＮ１ａ，Ｎ３ａ、両ノー
ド間で通過するノードＮ２０、Ｎ２，Ｎ１５，Ｎ３そし
てＮ２３及び全加算コストデータを経路情報として有す
る配線経路候補がリストアップされる。

【００５２】以上のようにして配線用端子１ａから３ａ
に接続する配線経路の候補が１つ決定される。

【００５３】図６は図１のステップＳ４で決定されたネ
ットの配線処理順序を基にステップＳ５でネット順に配
線経路を選択するための探索木を示している。ネット順
に配線経路を選択していくときにネットの組み合わせが
レイアウト制約条件（例えば、平行配線禁止、交差配線
禁止等）を満足しないものは切り捨てていく。

【００５４】

【発明の効果】上記詳細に説明したように、各ノードか
ら配線用端子上のノードへの最短距離をコストテーブル
として用意し、このテーブルを参照して配線経路候補を
探索するので配線経路長制約条件を満足しない場合は、
直ちにその配線経路の探索を打ち切る。これにより従来
のような余分な探索による処理時間の増大がなくなる。

【００５５】さらに配線経路候補数によってネットの配
線処理順序を決めるので、この処理順序によって解の品
質は変わらないが、これによっても処理時間を短縮でき
る。

【００５６】さらに配線経路候補の探索及び最終的に配
線経路を決めるときに分枝限定法を採用したので、配線
経路長制約条件を満足する解が存在すれば、最適な解が
得られることが保証される。

【００５７】逆にこの手法で解が得られない場合は、与
えられた配線経路長制約条件を満足する解が存在しない
ことがが保証される。

【図面の簡単な説明】

【図１】本発明のＬＳＩの自動概略配線方法の１実施例
を示すフローチャート。

【図２】概略配線経路を探索する空間となるチャネルグ
ラフの１例を示す図。

【図３】本発明のＬＳＩの自動概略配線方法のコストテ
ーブルを示す図。

【図４】図１に示したコストテーブル作成ステップを示
すフローチャート。

【図５】図１に示した配線経路候補リストアップステッ
プを示すフローチャート。

【図６】図１に示した配線経路選択ステップを説明する
概念図。

【符号の説明】

１〜６ 素子 １ａ，１ｂ，１ｃ〜６ａ，６ｂ、６ｃ 配線用端子 Ｃ１〜Ｃ１８ チャネル Ｎ１〜Ｎ４９ ノード

Claims (3)

【特許請求の範囲】
1. 【請求項１】チャネルグラフのチャネル上の全ノードか
   らチャネルグラフ上に配された素子への最短距離を測定
   する工程と、 前記最短距離を基に、同電位の配線要求を満たす配線経
   路を少なくとも１つ探索する工程と、 前記探索された配線経路を基に、異なる電位の配線要求
   の処理順序を決定する工程と、 前記決定した順序において、最適な配線経路の組合わせ
   を選択する工程とを備えたことを特徴とする概略配線方
   法。
2. 【請求項２】前記最短距離測定工程は、前記素子から最
   短距離測定対象ノードへの各チャネル上に存在するノー
   ド間の距離を累積して前記各チャネルの長さを求め、求
   められた長さの中の最小の長さを前記最短距離とする工
   程を含むことを特徴とする請求項１に記載の概略配線方
   法。
3. 【請求項３】前記配線経路探索工程は、 前記素子から配線すべき素子への各チャネル上に存在す
   るノード間の距離を累積して前記各チャネルの長さを求
   め、求められた長さが前記両素子を最短距離で配線して
   も電気的制約条件を満足するか判断して、前記条件を満
   足するチャネルを配線経路とする工程を含むことを特徴
   とする請求項１又は２に記載の概略配線方法。