JPH11121626A - 概略経路決定方法および概略経路決定方式 - Google Patents

Abstract

(57)【要約】 【課題】 遅延制約を満たしていないパス上のネットに
対して、層毎の遅延値を考慮するとともに配線の混雑度
をも考慮した概略配線経路の探索を行う。 【解決手段】 複数の配線層を有するチップの各セル間
を接続するネットの接続情報および遅延制約が予め記憶
された情報記憶部１０と、上記チップを格子状に細かく
区切って、上記複数の配線層における各格子の境界につ
いて、通すことのできるネットの容量を予め定め、情報
記憶部１０に記憶された情報を基に、各セル間を接続す
るネットの概略経路を、上記遅延制約を満たし、かつ、
経由する格子のそれぞれの境界における実際に配された
ネットの数がそれぞれの境界に設定されている容量を超
えないように決定する配線処理部２０とを有する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、多層の配線層を持
つＬＳＩ（Large Scale integrated circuit）などの半
導体集積回路を構成するチップの各セル間を接続するネ
ットの概略経路を決める概略経路決定方法および概略経
路決定方式に関する。

【０００２】

【従来の技術】半導体集積回路のレイアウト設計におい
て自動的にセル間の配線を行う自動配線手法として、特
開平8-123843号公報に開示されているような自動配置配
線方法がある。図８に、その公報に開示されている自動
配線システムの概略構成を示す。

【０００３】図８において、自動配線システムは、計算
機１０１、ネットリストデータ１０２、セルレイアウト
データ１０３、および配線遅延パラメータ１０４から成
る。計算機１０１は、遅延制約入力部１１１、セル配置
部１１２、セル間配線部１１３、配線遅延計算部１１
４、制約条件判断部１１５および配線変更部１１６を有
する。

【０００４】遅延制約入力部１１１は、ネットリストの
ノード毎に遅延制約を与えるもので、回路図エディタに
より制約を与えるノードを直接指定するか、または、遅
延シミュレータとリンクして遅延時間がある閾値以上で
あるパスのノードを自動的に返すような処理を行う。セ
ル配置部１１２は、ネットリストデータ１０２に使用さ
れているセルのセルレイアウトデータ１０３を与えられ
た範囲で配置する。

【０００５】セル間配線部１１３は、ネットリストデー
タ１０２の接続情報から接続配線を生成する。配線遅延
計算部１１４は、例えば各配線層のある配線幅の単位長
あたりの配線容量として与えられた配線遅延パラメータ
１０４を用いて配線遅延時間の計算を行う。制約条件判
断部１１５は、各ノードが制約を満たしているかを判断
する。配線変更部１１６は、制約を満たさないと判断さ
れたノードについて配線層の変更を行う。

【０００６】上述の自動配線システムでは、例えば３層
の配線層を有する半導体集積回路のレイアウト設計を行
う場合、まず、セル配置部１１２がセルを与えられた範
囲で配置し、セル間配線部１１３がそれらセル間の配線
を生成する。この配線生成の際、配線層の選択は下層の
配線を優先する。例えば、第１層（最下層）の配線を優
先して行い、第１層の配線密度が増して、遅延制約を満
たす配線が第１層ではできなくなったときに第２層を使
用し、さらに第２層でできなくなったときに第３層を使
用するというように下層から順に使用する。この場合、
全体の配線結果は第１層、第２層、第３層の順で使用頻
度が高くなる。また、遅延制約入力部１１１から遅延制
約の与えられたノードを先行して配線することにより、
遅延制約の与えられたノードはできるだけ他の配線によ
る空間的な障害のない状態で、最短距離に近い配線を生
成することができる。

【０００７】セル間の配線が生成されると、続いて、制
約条件判断部１１５が各ノードが制約を満たしているか
を判断する。制約を満たす場合は、そこで配線処理が終
了し、満たさない場合には、配線層変更部１１６が制約
を満たさないと判断されたノードについて配線層の変更
を行う。

【０００８】上記の自動配線方法の他、特開平5-143692
号公報に開示されているような、概略配線処理時の変更
や詳細配線処理によって「遅延の厳しいパス」が遅延制
約を違反することのないようにした概略経路決定方式も
ある。この方式の概略構成を図９に示す。

【０００９】図９において、概略経路決定方式の概略構
成は、情報入力部２０１、遅延解析部２０２、違反ネッ
ト抽出部２０３、最適遅延値配線層抽出部２０４、違反
ネット概略配線処理部２０５と、これを統括的に制御す
る制御部２００からなる。

【００１０】情報入力部２０１は、処理対象のＬＳＩお
よびプリント基板等（処理対象基板）について、ブロッ
クの配置を示すブロック配置情報、ブロック間の論理接
続関係を示すブロック間論理接続情報、下地とブロック
とに関する物理情報である下地・ブロック物理情報、下
地とブロックとに関する遅延情報である下地・ブロック
遅延情報をそれぞれ入力する。

【００１１】遅延解析部２０２は、下地・ブロック物理
情報に基づいて、処理対象基板の各配線層を縦方向配線
層と横方向配線層との２つに分類し、それぞれについて
遅延値が最も大きな配線層を求める。さらに、遅延解析
部２０２は、ブロック配置情報とブロック間論理接続情
報とに基づいて、処理対象基板の各ネットの仮想配線長
の縦方向長および横方向長を求める。そして、遅延が最
大の配線層における仮想配線長条件での各パスの遅延解
析を行う。

【００１２】違反ネット抽出部２０３は、遅延解析部２
０２による遅延解析において遅延制約を違反するパスを
抽出し、違反パスを構成するネットを示す違反ネット情
報を作成する。最適遅延値配線層抽出部２０４は、違反
ネット抽出部２０３によって抽出された違反パスが仮想
配線長条件での遅延解析で遅延制約を満たす配線層を求
める。違反ネット概略配線処理部２０５は、違反ネット
抽出部２０３によって求められた違反ネット情報により
示されるネットについて、仮想配線長と等しくなるよう
な概略経路を求め、その概略経路を最適遅延値配線層抽
出部２０４によって求められた縦方向配線および横方向
配線に割り当てるとともに、この概略経路の割り当てが
後に変更対象とされないように固定的なものとして設定
する。

【００１３】上述の概略経路決定方式では、まずネット
リストと遅延制約情報に基づいて遅延が最大の層で概略
経路が求められ、違反しているネットに対して概略配線
の層を遅延値が小さい層に割り当て直して概略経路が求
められる。これのより、遅延制約の厳しいパスを構成す
るネットの経路に関しては、概略配線処理の段階で配線
の割り当てと経路の長さとを遅延制約を違反しないよう
に固定的に設定することが可能になる。

【００１４】

【発明が解決しようとする課題】しかしながら、上述し
た従来の手法には、以下のような問題がある。

【００１５】高速ＬＳＩにおいては、層によって配線ピ
ッチや厚さが異なるため、同一配線長であっても使用す
る層により遅延時間が異なり、場合によっては、２倍以
上もの遅延時間の差が生じることがある。そのため、ク
リティカルパス上のネットについては、配線長を最短に
するだけでなく、使用する層を考慮して配線を行う必要
がある。

【００１６】特開平8-123843号公報に開示された自動配
置配線方法においては、遅延制約のあるノードの配線を
できるだけ最短距離で配線でき、制約を満たさない配線
については上層の配線に乗り換えて遅延制約を満たし易
くすることができるようになっているが、使用する層の
配線状態を考慮した配線は行われていない。このよう
に、下層だけで配線し、遅延制約にひっかかった配線に
ついて上層へ移行する方法では、上層に何があるか不明
のまま配線が行われてしまうため、例えば上層に電源パ
スなどがある場合には、配線を移行することはできない
という問題が生じる。

【００１７】特開平5-143692号公報に開示された概略経
路決定処理方式においては、概略配線処理の段階で配線
の割り当てと経路の長さとを遅延制約を違反しないよう
に設定することができるが、層の再割り当てを行う際は
概略経路を変更せずに層のみが変更され、変更された層
の配線の混雑度を考慮した概略経路の探索は行われてい
ない。このように配線の混雑度を考慮して概略経路を求
めていないものでは、詳細配線処理で配線ができなくな
る場合がある。

【００１８】本発明は、上記各問題を解決し、遅延制約
を満たしていないパス上のネットに対して、層毎の遅延
値を考慮するとともに配線の混雑度をも考慮した概略経
路の探索を行い、全てのパスが遅延制約を満たすよう
に、正確な遅延見積もりで概略経路を求めることができ
る概略経路決定方法および概略経路決定方式を提供する
ことにある。

【００１９】

【課題を解決するための手段】上記目的を達成するた
め、本発明の概略経路決定方法は、半導体集積回路を構
成するチップの各セル間を接続するネットの概略経路を
決める概略経路決定方法において、前記チップを格子状
に細かく区切り、各格子の境界について、通すことので
きるネットの容量を予め設定し、前記各セル間を接続す
るネットの概略経路を、予め設定されている遅延制約を
満たし、かつ、ネットが経由する格子のそれぞれの境界
における実際に配されたネットの数がそれぞれの境界に
設定されている容量を超えないように決定することを特
徴とする。

【００２０】また、本発明の概略経路決定方法は、半導
体集積回路を構成するチップの各セル間を接続するネッ
トの概略経路を決める概略経路決定方法において、前記
チップを格子状に細かく区切って、前記チップを構成す
る複数の配線層のそれぞれにおける各格子の境界につい
て、通すことのできるネットの容量を予め設定し、前記
複数の配線層の優先順位として用いるそれぞれの層のコ
ストと、ネットの経路長を制限するオーバーフローコス
トとをそれぞれ所定の値に設定して、ネットが経由する
前記格子のそれぞれの境界におけるネットのオーバーフ
ロー数と、ネットが経由する配線層におけるネットの配
線長とから、以下の式より求まるネットコストが最小と
なる経路を前記各セル間を接続するネットについてそれ
ぞれ探索し、 ネットコスト＝（オーバーフロー数）×（オーバーフロ
ーコスト）＋Σ｛（各層の配線長）×（各層のコス
ト）｝

【００２１】予め設定された遅延制約を満たしていない
ネットがある場合は、該ネットについて、ネットの経路
長が短くなるように前記オーバーフローコストを小さく
するとともに上層の優先順位が高くなるように前記複数
の層のうちの上層のコストを小さくして、前記式にて求
まるネットコストが最小となる経路を再探索し、オーバ
ーフローしているネットがある場合には、該ネットにつ
いて、ネットの経路長が長くなるように前記オーバーフ
ローコストを大きくして、前記式にて求まるネットコス
トが最小となる経路を再探索することを特徴とする。

【００２２】上記の場合、遅延制約を満たしていないネ
ットがある場合に、違反した遅延が大きいものほどオー
バーフローコストと上層のコストが小さくなるように設
定することを特徴とする概略経路決定方法。なるように
設定するようにしてもよい。

【００２３】また、特定のネットに対して、前記複数の
配線層のうちの上層のコストを他のネットの上層のコス
トより小さく設定して、前記式にて求まるネットコスト
が最小となる経路を探索するようにしてもよい。

【００２４】本発明の概略経路決定方式は、半導体集積
回路を構成するチップの各セル間を接続するネットの接
続情報および遅延制約が予め記憶された情報記憶手段
と、前記チップを格子状に細かく区切って、前記チップ
を構成する複数の配線層における各格子の境界につい
て、通すことのできるネットの容量を予め定め、前記情
報記憶手段に記憶された情報を基に、前記各セル間を接
続するネットの概略経路を、前記遅延制約を満たし、か
つ、ネットが経由する格子のそれぞれの境界における実
際に配されたネットの数がそれぞれの境界に設定されて
いる容量を超えないように決定する配線処理手段とを有
することを特徴とする。

【００２５】上記の場合、前記情報記憶手段は、前記複
数の配線層の優先順位として用いるそれぞれの層のコス
トとネットの経路長を制限するオーバーフローコストと
をそれぞれ所定の値に設定したデフォルトコストと、前
記遅延制約を違反した場合に設定される経路探索コスト
であって、違反遅延に応じて前記デフォルトコストより
もネットの経路長が短くなるようにオーバーフローコス
トを小さくするとともに上層の優先順位が高くなるよう
に上層のコストを小さくした少なくとも１つの経路探索
コストと、が予め記憶されており、前記配線処理手段
は、前記複数の配線層における各格子の境界について、
通すことのできるネットの容量を予め設定し、ネットが
経由する格子のそれぞれの境界について、その境界に設
定された容量から実際に配されたネットの数を差し引い
た残りの容量を算出する容量計算手段と、前記各セル間
のネットの概略経路を探索する経路探索手段と、前記経
路探索手段で探索されたネットの経路の遅延を計算する
遅延計算手段と、前記容量計算手段および遅延計算手段
における計算結果に基づいて、前記経路探索手段で探索
された各ネットの経路について、算出オーバーフローし
ていないか、前記遅延制約を違反していないかの判定を
行う違反ネット判定手段と、前記違反ネット判定手段で
前記遅延制約を満していないと判定されたネットについ
て、その違反遅延に応じた経路探索コストを前記記憶手
段に記憶された経路探索コストから決定し、前記違反ネ
ット判定手段でオーバーフローしていると判定された場
合に、前記記憶手段に記憶されたデフォルトコストおよ
び前記経路探索コストのオーバーフローコストをそれぞ
れ増加する経路探索コスト決定手段と、を有し、前記経
路探索手段が、前記記憶手段に記憶されたデフォルトコ
ストを用いて以下の式にて求まるネットコストが最小と
なる経路を探索し、 ネットコスト＝（オーバーフロー数）×（オーバーフロ
ーコスト）＋Σ｛（各層の配線長）×（各層のコス
ト）｝ 前記違反ネット判定手段で遅延制約を満していないと判
定されたネットについては、前記経路探索コスト決定手
段で設定された経路検索コストを用いて前記式にて求ま
るネットコストが最小となる経路を再探索し、前記違反
ネット判定手段でオーバーフローしていると判定された
場合は、前記経路探索コスト決定手段にてオーバーフロ
ーコストが増加されたデフォルトコストおよび経路探索
コストを用いて前記式にて求まるネットコストが最小と
なる経路を再探索するように構成してもよい。

【００２６】また、前記記憶手段に予め記憶された経路
探索コストは、違反遅延の大きいネットほどオーバーフ
ローコストと上層のコストが小さくなるように設定され
ているようにしてもよい。

【００２７】さらに、特定のネットに対して、前記複数
の配線層のうちの上層のコストを他のネットの上層のコ
ストより小さく設定した第２のデフォルトコストが前記
情報記憶手段に予め記憶され、前記経路探索手段が、前
記特定のネットの概略経路を、前記第２のデフォルトコ
ストを用いて前記式にて求まるネットコストが最小とな
る経路を探索することにより求めるようにしてもよい。

【００２８】（作用）上記のとおりの本発明において
は、格子の境界毎に通すことのできるネットの容量が設
定され、その容量を超えないようにネットの経路が求め
られるので、配線の混雑度を考慮したネットの概略経路
が求められる。したがって、従来の手法のように上層に
電源パスなどがあるために配線を上層に移行することが
できなかったり、配線の混雑度を考慮して概略経路を求
めていないために詳細配線ができなくなってしまうとい
った問題は生じない。

【００２９】また、本発明では、デフォルトコストを用
いて以下の式にて求まるネットコストが最小となる経路
を探索し、 ネットコスト＝（オーバーフロー数）×（オーバーフロ
ーコスト）＋Σ｛（各層の配線長）×（各層のコス
ト）｝ 遅延違反ネットについては、その違反遅延に応じてデフ
ォルトコストよりもオーバーフローコストと上層のコス
トが小さく設定された経路探索コストを用いて上記式に
て求まるネットコストが最小となる経路が再探索され、
オーバーフローしている場合は、デフォルトコストおよ
び経路探索コストのオーバーフローコストをそれぞれ増
加して前記式にて求まるネットコストが最小となる経路
が再探索される。この遅延違反ネットの経路の再探索で
は、オーバーフローコストを小さくしたことにより最短
経路が探索され、さらに上層のコストを小さくしたこと
により遅延制約の小さい上層が優先して使用される。オ
ーバーフローしていれば、オーバーフローコストを増加
して経路の再探索が行われるので、探索される経路は、
オーバーフローコストを増加した分、経路長が長くな
る。すなわち、迂回経路が探索されることになる。この
ように本発明では、遅延違反ネットついては遅延制約の
小さい上層を使用して最短経路が探索され、オーバーフ
ローしている場合は、迂回路が探索されるので、各層毎
の遅延値を考慮するとともに配線の混雑度をも考慮した
概略配線経路の探索が行われる。

【００３０】また、本発明では、違反遅延の大きいネッ
トほどオーバーフローコストと上層のコストが小さくな
るように経路探索コストが設定されるので、違反遅延の
大きいネットほど上層を優先的に使用されるとともに、
より最短距離で経路が探索されることになる。これによ
り、遅延制約を満たしていないパス上のネットに対し
て、層毎の遅延値を考慮した概略配線経路の探索が可能
になり、遅延制約の厳しいネット、厳しくないネットで
層の使い分けが可能になる。

【００３１】

【発明の実施の形態】次に、本発明の実施形態について
図面を参照して説明する。

【００３２】図１は、本発明の概略経路決定方式の概略
構成を示すブロック図である。この方式は、各層毎の遅
延値を考慮するとともに配線の混雑度をも考慮した概略
経路の探索を行い、全てのパスが遅延制約を満たすよう
な正確な遅延見積もりで配線を行うようにしたもので、
その構成は、各セルに関する配置配線情報が記憶された
情報記憶部１０と、セル間の配線を行う配線処理部２０
と、配線結果を出力する配線結果出力部３０とからな
る。

【００３３】情報記憶部１０は、セルの接続情報である
ネットリスト１１、セルに関する、内部配線や接続端子
の位置、数などの情報が記憶されたセル情報ファイル１
２、セルの配置に関する情報が記憶された配置情報ファ
イル１３、遅延制約に関する情報が記憶された遅延制約
情報ファイル１４を有する。

【００３４】配線処理部２０は、上述の情報記憶部１０
の各情報に基づいてセルの配置、概略配線処理および詳
細配線処理を行うもので、概略格子容量計算部２１、経
路探索部２２、遅延計算部２３、違反ネット判定部２
４、経路探索コスト決定部２５の複数の処理部からな
る。

【００３５】概略格子容量計算部２１は、配線の混雑度
を考慮するためのものである。この概略格子容量計算部
２１は、例えば図２に示すように、チップを水平方向お
よび垂直方向に細かく区切り（格子状に区切る）、それ
ぞれの格子の境界について、通すことのできる配線の本
数（容量）を予め設定する。そして、ネットが経由する
格子のそれぞれの境界について、境界に設定された容量
から実際に配されたネットの数を差し引いた残りの容量
を算出する。この容量の算出では、例えば、境界の容量
を７本に設定した場合、その境界に実際に配された配線
が３本ある場合は、その境界の残りの容量は４本にな
る。ここで、実際に配された配線には、電源パスやセル
の内部配線など予め使用することが決まっている配線も
含まれる。例えば図３に示すように、格子４０の境界Ａ
に対して７本の配線４１を配することができるように設
定され、その境界Ａに電源パス４２が配されている場合
は、電源パス４２と重なる部分（配線禁止部分）は配線
することができないので、その分が差し引かれた本数が
その境界Ａの残りの容量として算出される。ここでは、
電源パスやセルの内部配線などの配線禁止部分に関する
情報は予め情報記憶部１０に記憶しておき、概略格子容
量計算部２１が情報記憶部１０に記憶されている配線禁
止領域を基に容量を算出する。そして、実際に配された
配線の本数（フロー）が境界に設定された配線の本数を
超える場合（オーバーフロー）は、その境界は配線でき
ないと判断し、超えていない場合は、その境界には配線
を通す余裕があると判断する。なお、チップを水平方向
および垂直方向に細かく区切る格子の望ましい大きさ
は、具体的には、チップを水平方向および垂直方向に区
切ることができる配線トラックの数でいうと、水平方向
および垂直方向ともに、１５〜２０本間隔で区切った大
きさであるが、この大きさは特に限定されるものではな
い。

【００３６】経路探索部２２は、セル間のネットの概略
経路を探索する。この経路探索部２２による経路探索で
は、ネット毎の配線経路のコスト（ネットコスト）を、 ネットコスト＝（オーバーフロー数）×（オーバーフローコスト） ＋Σ｛（各層の配線長）×（各層のコスト）｝ ……（１） で計算し、最小コストとなる経路を探索する。ここで、
オーバーフローコストは、各ネットの経路に位置する格
子のそれぞれの境界におけるオーバーフロー数に乗じら
れる係数で、この値が小さいほど経路長が短くなる。層
のコストは、各ネットの経路となっている各層の配線長
に乗じられる係数で、この値が小さい層ほど優先して使
用される。ここでは、これらオーバーフローコストおよ
び各層のコストをデフォルト値に設定したデフォルトコ
スト、およびオーバーフローコストおよび各層のコスト
を違反遅延量に応じて設定した経路探索コスト（遅延制
約違反ネットに対して設定されるコスト）を、予め情報
記憶部１０に記憶しておき、経路探索部２２が、後述す
るように、まずデフォルトコスト（オーバーフローコス
トおよび各層のコストの基準値）で各ネットの経路探索
を行い、その後に遅延制約違反したネットについて、そ
の違反遅延に応じた経路探索コストで再度経路の探索を
行う。

【００３７】遅延計算部２３は、経路探索部２２にて探
索された各ネットの経路の遅延を計算する。違反ネット
判定部２４は、経路探索部２２にて探索された各ネット
の経路について、オーバーフローしていないか、遅延制
約違反していないかのチェックを行い、いずれかに該当
したネットを違反ネットとして判定する。

【００３８】経路探索コスト決定部２５は、違反ネット
判定部２４にて遅延制約違反とされたネットの経路につ
いて、その違反遅延に応じた経路探索コストを決定す
る。具体的には、経路探索コスト決定部２５が遅延計算
部２３にて計算された遅延結果に応じて、情報記憶部１
０に記憶された各経路探索コストのうちから経路探索コ
ストを決定する。また、経路探索コスト決定部２５は、
オーバーフローしている場合は、情報記憶部１０に記憶
されているデフォルトコストおよび経路探索コストにつ
いて、それぞれオーバーフローコストを増加する。

【００３９】上述の経路探索部２２は、違反ネット判定
部２４で遅延制約を満していないと判定されたネットに
ついては、経路探索コスト決定部２５で設定された経路
検索コストを用いて上述の式１にて求まるネットコスト
が最小となる経路を再探索し、違反ネット判定部２４で
オーバーフローしていると判定された場合は、経路探索
コスト決定部２５でオーバーフローコストを増加された
デフォルトコストおよび経路探索コストを用いて上述の
式１にて求まるネットコストが最小となる経路を再探索
する。

【００４０】次に、上述の概略経路決定方式において行
われる経路の探索処理手順について図４を参照して説明
する。

【００４１】まず、概略格子容量計算部２１が、与えら
れている情報（例えば電源パスなどの初期配線の情報な
ど）に基づいて、各格子の境界の容量を算出する（ステ
ップＳ１０）。続いて、経路探索部２２が、各ネットの
経路について、情報記憶部１０に用意されているデフォ
ルトコストで経路の探索を行い、上述の式１にて求まる
最小コストの経路を探索する（ステップＳ１１）。

【００４２】経路探索部２２によって経路探索が行われ
て初期経路が求められると、続いて、遅延計算部２２が
各ネットの経路の遅延を計算する（ステップＳ１２）。
そして、その遅延計算結果に基づいて、違反ネット判定
部２４が遅延制約を満たしていないネットがあるかの判
断を行う（ステップＳ１３）。遅延制約違反したネット
がある場合は、経路探索コスト決定部２５がその違反ネ
ットに対してその違反遅延に応じた経路探索コストを決
定し、経路探索部２２が、その決定された経路探索コス
トで遅延制約違反したネットの経路を再検索する（ステ
ップＳ１４）。このときの経路再検索においても、上述
の式１にて求まる最小コストの経路が探索される。

【００４３】上述のステップＳ１４において、遅延制約
違反したネットがない場合は、続いて違反ネット判定部
２４がオーバーフローしているネットがあるかの判断を
行う（ステップＳ１５）。オーバーフローしているネッ
トがある場合は、経路探索コスト決定部２５が情報記憶
部１０に記憶されているデフォルトコストおよび経路探
索コストのオーバーフローコストをそれぞれ増加し、再
びステップＳ１１へ戻る（ステップＳ１５）。オーバー
フローしているネットがない場合は、処理を終了する。

【００４４】以下、上述の経路探索処理をより具体的な
例を挙げて説明する。

【００４５】ここでは、図５に示すようにチップ５０を
水平方向および垂直方向に細かく区切った格子５１を設
定し、水平方向の配線については第１層、第３層を用
い、垂直方向の配線については第２層を用いている。境
界Ａ、Ｂに予め設定されている容量は、ともに第１層で
３本、第３層で１本である。ネットリストには３つのネ
ットＡ、Ｂ、Ｃに関する情報が用意されており、経路探
索部２２によって図５に示したような初期経路（予め設
定されたデフォルトコストで求められた経路）が設定さ
れている。ここでは、経路探索に用いられるコストとし
ては、図６に示すようなデフォルトコスト、違反遅延１
ｎｓ未満コスト、違反遅延１ｎｓ以上コストが予め設定
されている。さらに、ここでは、図４に示したステップ
Ｓ１１〜Ｓ１６の処理を何回繰り返すかを指定する指定
改善回数として、２０回が設定されている。なお、以下
の説明では、図示されたネットについて、水平方向につ
いては、実線が第１層に配線された経路を示し、破線が
第３層に配線された経路を示す。

【００４６】まず、初期配線に基づいて各格子の境界の
容量を計算して初期経路が決定されるが、この図５に示
した例では、上述の図４に示したステップＳ１０、Ｓ１
１の処理についてはすでに行われて、初期経路が探索さ
れた状態になっているので、ここではステップＳ１２以
降の処理について説明する。

【００４７】ネットＡ，Ｂ，Ｃに関する初期経路が探索
されると、各ネットＡ，Ｂ，Ｃについてそれぞれ順番に
上述の図４に示したステップＳ１２〜Ｓ１６の処理を行
う。ここでは、ステップＳ１２の処理において、ネット
Ａは遅延制約を満たし、ネットＢは０．５ｎｓの違反、
ネットＣは２ｎｓの違反をするものとして説明する。

【００４８】まず、ネットＡについてステップＳ１２〜
Ｓ１４の処理を行う。このネットＡは遅延制約を満たし
ているので、その経路は図５に示した経路のままとす
る。

【００４９】続いて、ネットＢについてステップＳ１２
〜Ｓ１４の処理を行う。このネットＢは０．５ｎｓの遅
延違反をしているので、ステップＳ１４の処理によっ
て、経路探索コストとして違反遅延１ｎｓ未満コストが
決定され、そのコストに基づいて再度経路の探索が行わ
れる（引き剥がし再配線）。この経路探索では、上述の
式１より、 ネットＢのコスト＝０（オーバーフロー数）×２（オー
バーフローコスト）＋３（第３層の配線長）×５（第３
層のコスト）＋２（第２層の配線長）×５（第２層のコ
スト） で与えられる最小コスト経路が探索される。ここで、オ
ーバーフロー数は、第３層の境界Ａ，Ｂにおける現時点
でのオーバーフロー数の和である。また、各層の配線長
は探索されるネットの経路の各層における現時点での配
線長で、ここでは配線長を経路が通る格子の数（経路が
またがっている格子の数）で表わしている。この経路探
索では、図７（ａ）に示すように、水平方向の配線が第
１層から第３層に移行された経路が探索される。経路が
探索されると、この経路についての遅延が計算され、遅
延制約を満たさなければその違反遅延に応じた経路探索
コストで再び経路探索が行われる。ここでは、遅延制約
を満たしたものとし、次のネットＣについての処理に進
む。

【００５０】ネットＣは２ｎｓの違反をしているので、
ステップＳ１４の処理によって、経路探索コストとして
違反遅延１ｎｓ以上コストが決定され、そのコストに基
づいて再度経路の探索が行われる（引き剥がし再配
線）。この経路探索では、上述のネットＢの場合と同
様、式１より、 ネットＣのコスト＝２（オーバーフロー数）×１（オー
バーフローコスト）＋３（第３層の配線長）×２（第３
層のコスト） で与えられる最小コスト経路が探索される。ここで、オ
ーバーフロー数はネットの経由する各境界Ａ，Ｂにおけ
るオーバーフロー数の和である。ここでは、第３層の境
界Ａ，Ｂの容量はともに１本であり、上述したようにす
でにネットＢの経路がこれら境界Ａ，Ｂを通るように配
線されているため、ネットＣの経路がそれら境界Ａ，Ｂ
を通るように配線されると、各境界Ａ，Ｂではそれぞれ
１本のオーバーフローが生じ、これら境界Ａ，Ｂにおけ
る現時点でのオーバーフロー数の和は２となる。この経
路探索では、例えば、図７（ｂ）に示すように、水平方
向の配線が第１層から第３層に移行された経路が探索さ
れる。経路が探索されると、この経路についての遅延が
計算され、遅延制約を満たさなければその違反遅延に応
じた経路探索コストで再び経路探索が行われる。ここで
は、遅延制約を満たしたものとし、各ネットＡ〜Ｃにつ
いて次のステップＳ１５、Ｓ１６の処理を順次行う。

【００５１】この時点におけるネットＡに関する経路
は、第１層の境界Ａ，Ｂを通るように配線されている
（図７（ｂ）参照）。第１層の境界Ａ，Ｂにおける容量
は３本で、これら境界Ａ，ＢにはネットＡ以外のネット
は配線されていない。したがって、このネットＡはオー
バーフローしていないことになり、ネットＡの経路はそ
のまま変更なしとなる。

【００５２】ネットＢに関する経路は、図７（ｂ）に示
すように第３層の境界Ａ，Ｂを通るように配線されてい
る。この第３層の境界Ａ，Ｂの容量はともに１本であ
り、この第３層の境界Ａ，ＢにはネットＢの他にネット
Ｃに関する経路が配線されている。したがって、ネット
Ｂの経路では第３層の境界Ａ，Ｂにおいてそれぞれ１本
のオーバーフローが生じることとなり、ネットＢはオー
バーフローしていると判断される。オーバーフローと判
断されると、ステップＳ１６の処理において、デフォル
トコストおよび各違反遅延に応じて設定された経路探索
コストのオーバーフローコストが、例えば２倍に増幅さ
れ、再びステップＳ１１において、その新たに設定され
たデフォルトコストでネットＢについての経路の探索が
行われる。この経路探索では、例えば図７（ｃ）に示す
ように、水平方向の配線が第３層の境界Ｃ、Ｄを通る経
路が探索される。そしてステップＳ１２〜Ｓ１５の処理
が続いて行われ、検索された経路が遅延制約を満たさな
い場合には、ステップＳ１６の処理にて新たに設定され
た経路探索コストで再度経路の探索をするといった処理
が行われる。このネットＢに対する経路の探索は、遅延
制約を満たし、オーバーフローもしていないと判断され
るまで行われる。

【００５３】ネットＢに対する経路が、遅延制約を満た
し、オーバーフローもしていないと判断されると、続い
てネットＣについてオーバーフローしているかの判断が
行われる。ネットＣに関する経路は第３層の境界Ａ，Ｂ
を通るように配線されたものとなっている（図７（ｂ）
参照）。第３層の境界Ａ，Ｂにおける容量は１本であ
り、ネットＢについては上述の処理で新たな経路が探索
されているため、これら境界Ａ，Ｂには現時点でネット
Ｃ以外のネットは配線されていないことになる。したが
って、ネットＣはオーバーフローしていないことにな
り、ネットＣの経路はそのまま変更なしとなる。なお、
他のネットの経路が境界Ｃ、Ｄに存在してオーバーフロ
ーとなる場合には、上述のネットＢのように、オーバー
フローコストが増幅されたデフォルトコストで新たな経
路が探索される。そして、その経路が遅延制約違反の場
合には、オーバーフローコストが増幅された経路探索コ
ストを用いて経路の再探索が行われる。

【００５４】上述のようにして各ネットＡ〜Ｃの経路
（概略経路）が求められると、その求めた概略経路を守
って詳細配線が行われる。なお、上述した各ネットＡ〜
Ｃの経路探索の順序は特に限定するものではなく、設計
に応じて決定されるものである。

【００５５】また、本形態では、全ネットについてデフ
ォルトコストで初期経路を求めているが、これに限定さ
れるものではない。例えば、特定のネット（例えばブロ
ック間ネットのように遅延が大きいネット）に対しての
み、上層のコストをデフォルトコストのそれより小さく
した指定コストで経路探索を行うようにしてもよい。こ
の場合の経路探索も上述の式１により求まる最小コスト
の経路が探索される。

【００５６】

【発明の効果】以上説明したように構成される本発明に
よれば、遅延制約を満たしていないパス上のネットに対
して、各層毎の遅延値を考慮するとともに配線の混雑度
をも考慮して概略経路の探索が行われ、また、遅延制約
の厳しいネット、厳しくないネットで層の使い分けが行
われるので、全てのパスが遅延制約を満すような正確な
遅延見積もりで配線を行うことができる。

【図面の簡単な説明】

【図１】本発明の概略経路決定方式の概略構成を示すブ
ロック図である。

【図２】チップを格子状に区切った一例を示す図であ
る。

【図３】配線が電源パスと重なった例を示す図である。

【図４】図１に示した概略経路決定方式において行われ
る経路の探索処理手順を示すフローチャートである。

【図５】初期経路の一例を示す図である。

【図６】デフォルトコスト、違反遅延１ｎｓ未満コス
ト、違反遅延１ｎｓ以上コストの一例を示す図である。

【図７】（ａ）〜（ｃ）は各経路探索処理において探索
された経路の一例を示す図である。

【図８】特開平8-123843号公報に開示されている自動配
線システムの概略構成を示すブロック図である。

【図９】特開平5-143692号公報に開示されている概略経
路決定方式の概略構成を示すブロック図である。

【符号の説明】

１０ 情報記憶部 １１ ネットリスト １２ セル情報ファイル １３ 配置情報ファイル １４ 遅延制約情報ファイル ２０ 配線処理部 ２１ 概略格子容量計算部 ２２ 経路探索部 ２３ 遅延計算部 ２４ 違反ネット判定部 ２５ 経路探索コスト決定部 ３０ 配線結果出力部

Claims (8)

【特許請求の範囲】
1. 【請求項１】 半導体集積回路を構成するチップの各セ
   ル間を接続するネットの概略経路を決める概略経路決定
   方法において、 前記チップを格子状に細かく区切り、各格子の境界につ
   いて、通すことのできるネットの容量を予め設定し、 前記各セル間を接続するネットの概略経路を、予め設定
   されている遅延制約を満たし、かつ、ネットが経由する
   格子のそれぞれの境界における実際に配されたネットの
   数がそれぞれの境界に設定されている容量を超えないよ
   うに決定することを特徴とする概略経路決定方法。
2. 【請求項２】 半導体集積回路を構成するチップの各セ
   ル間を接続するネットの概略経路を決める概略経路決定
   方法において、 前記チップを格子状に細かく区切って、前記チップを構
   成する複数の配線層のそれぞれにおける各格子の境界に
   ついて、通すことのできるネットの容量を予め設定し、 前記複数の配線層の優先順位として用いるそれぞれの層
   のコストと、ネットの経路長を制限するオーバーフロー
   コストとをそれぞれ所定の値に設定して、ネットが経由
   する前記格子のそれぞれの境界におけるネットのオーバ
   ーフロー数と、ネットが経由する配線層におけるネット
   の配線長とから、以下の式より求まるネットコストが最
   小となる経路を前記各セル間を接続するネットについて
   それぞれ探索し、 ネットコスト＝（オーバーフロー数）×（オーバーフロ
   ーコスト）＋Σ｛（各層の配線長）×（各層のコス
   ト）｝ 予め設定された遅延制約を満たしていないネットがある
   場合は、該ネットについて、ネットの経路長が短くなる
   ように前記オーバーフローコストを小さくするとともに
   上層の優先順位が高くなるように前記複数の層のうちの
   上層のコストを小さくして、前記式にて求まるネットコ
   ストが最小となる経路を再探索し、 オーバーフローしているネットがある場合には、該ネッ
   トについて、ネットの経路長が長くなるように前記オー
   バーフローコストを大きくして、前記式にて求まるネッ
   トコストが最小となる経路を再探索することを特徴とす
   る概略経路決定方法。
3. 【請求項３】 請求項２に記載の概略経路決定方法にお
   いて、 遅延制約を満たしていないネットがある場合に、違反し
   た遅延が大きいものほどオーバーフローコストと上層の
   コストが小さくなるように設定することを特徴とする概
   略経路決定方法。
4. 【請求項４】 請求項２に記載の概略経路決定方法にお
   いて、 特定のネットに対して、前記複数の配線層のうちの上層
   のコストを他のネットの上層のコストより小さく設定し
   て、前記式にて求まるネットコストが最小となる経路を
   探索することを特徴とする概略経路決定方法。
5. 【請求項５】 半導体集積回路を構成するチップの各セ
   ル間を接続するネットの接続情報および遅延制約が予め
   記憶された情報記憶手段と、 前記チップを格子状に細かく区切って、前記チップを構
   成する複数の配線層における各格子の境界について、通
   すことのできるネットの容量を予め定め、前記情報記憶
   手段に記憶された情報を基に、前記各セル間を接続する
   ネットの概略経路を、前記遅延制約を満たし、かつ、ネ
   ットが経由する格子のそれぞれの境界における実際に配
   されたネットの数がそれぞれの境界に設定されている容
   量を超えないように決定する配線処理手段とを有するこ
   とを特徴とする概略経路決定方式。
6. 【請求項６】 請求項５に記載の概略経路決定方式にお
   いて、 前記情報記憶手段は、 前記複数の配線層の優先順位として用いるそれぞれの層
   のコストとネットの経路長を制限するオーバーフローコ
   ストとをそれぞれ所定の値に設定したデフォルトコスト
   と、 前記遅延制約を違反した場合に設定される経路探索コス
   トであって、違反遅延に応じて前記デフォルトコストよ
   りもネットの経路長が短くなるようにオーバーフローコ
   ストを小さくするとともに上層の優先順位が高くなるよ
   うに上層のコストを小さくした少なくとも１つの経路探
   索コストと、が予め記憶されており、 前記配線処理手段は、 前記複数の配線層における各格子の境界について、通す
   ことのできるネットの容量を予め設定し、ネットが経由
   する格子のそれぞれの境界について、その境界に設定さ
   れた容量から実際に配されたネットの数を差し引いた残
   りの容量を算出する容量計算手段と、 前記各セル間のネットの概略経路を探索する経路探索手
   段と、 前記経路探索手段で探索されたネットの経路の遅延を計
   算する遅延計算手段と、 前記容量計算手段および遅延計算手段における計算結果
   に基づいて、前記経路探索手段で探索された各ネットの
   経路について、算出オーバーフローしていないか、前記
   遅延制約を違反していないかの判定を行う違反ネット判
   定手段と、 前記違反ネット判定手段で前記遅延制約を満していない
   と判定されたネットについて、その違反遅延に応じた経
   路探索コストを前記記憶手段に記憶された経路探索コス
   トから決定し、前記違反ネット判定手段でオーバーフロ
   ーしていると判定された場合に、前記記憶手段に記憶さ
   れたデフォルトコストおよび前記経路探索コストのオー
   バーフローコストをそれぞれ増加する経路探索コスト決
   定手段と、を有し、 前記経路探索手段が、 前記記憶手段に記憶されたデフォルトコストを用いて以
   下の式にて求まるネットコストが最小となる経路を探索
   し、 ネットコスト＝（オーバーフロー数）×（オーバーフロ
   ーコスト）＋Σ｛（各層の配線長）×（各層のコス
   ト）｝ 前記違反ネット判定手段で遅延制約を満していないと判
   定されたネットについては、前記経路探索コスト決定手
   段で設定された経路検索コストを用いて前記式にて求ま
   るネットコストが最小となる経路を再探索し、違反ネッ
   ト判定手段でオーバーフローしていると判定された場合
   は、前記経路探索コスト決定手段にてオーバーフローコ
   ストが増加されたデフォルトコストおよび経路探索コス
   トを用いて前記式にて求まるネットコストが最小となる
   経路を再探索することを特徴とする概略経路決定方式。
7. 【請求項７】 請求項６に記載の概略経路決定方式にお
   いて、 前記記憶手段に予め記憶された経路探索コストは、違反
   遅延の大きいネットほどオーバーフローコストと上層の
   コストが小さくなるように設定されていることを特徴と
   する概略経路決定方式。
8. 【請求項８】 請求項６に記載の概略経路決定方式にお
   いて、 特定のネットに対して、前記複数の配線層のうちの上層
   のコストを他のネットの上層のコストより小さく設定し
   た第２のデフォルトコストが前記情報記憶手段に予め記
   憶され、 前記経路探索手段が、前記特定のネットの概略経路を、
   前記第２のデフォルトコストを用いて前記式にて求まる
   ネットコストが最小となる経路を探索することにより求
   めることを特徴とする概略経路決定方式。