(57)【要約】【課題】回路をレイアウト配置した際のサイズ等を少ない計算量で高速に推定することが可能なレイアウト推定技術を提供する。【解決手段】回路ブロックと配線からなる入力回路を搭載するために必要とされる回路配置領域の大きさを推定するレイアウト推定方法において、すべての回路ブロックのうちの一部を選択し、回路配置領域の底辺から上辺まで、回路配置領域の縦方向に一列に連接して配列される一群の回路ブロック、及び前記回路配置領域の左辺から右辺まで、前記回路配置領域の横方向に一列に連接して配列される一群の回路ブロックに配分する第１のステップと、縦方向骨格ブロックの高さの総和を回路配置領域の高さとし、横方向骨格ブロックの幅の総和を回路配置領域の幅として、回路配置領域の大きさを推定する第２のステップとを有す。【選択図】        図２
2005209120.tif 000002
【特許請求の範囲】
【請求項１】
複数の回路ブロック、及び各回路ブロックの間を連結する配線で構成される入力回路を方形の回路配置領域に最密充填する場合において、入力回路を搭載するために必要とされる前記回路配置領域の大きさを推定するレイアウト推定方法であって、
すべての前記回路ブロックのうちの一部を選択し、前記回路配置領域の底辺から上辺まで、前記回路配置領域の縦方向に一列に連接して配列される一群の回路ブロック（以下、これらの回路ブロックを「縦方向骨格ブロック」という。）、及び前記回路配置領域の左辺から右辺まで、前記回路配置領域の横方向に一列に連接して配列される一群の回路ブロック（以下、これらの回路ブロックを「横方向骨格ブロック」という。）に配分する第１のステップと、
前記縦方向骨格ブロックの高さの総和を前記回路配置領域の高さとし、前記横方向骨格ブロックの幅の総和を前記回路配置領域の幅として、前記回路配置領域の大きさを推定する第２のステップと、
を備えていることを特徴とするレイアウト推定方法。
【請求項２】
前記縦方向骨格ブロックであり且つ前記横方向骨格ブロックでもある骨格ブロック（以下、「交点骨格ブロック」という。）により構成されるクラスタを交点骨格クラスタ、
前記縦方向骨格ブロックのうち前記交点骨格ブロックを除くものから構成される１又は複数のクラスタを縦方向骨格クラスタ、
前記横方向骨格ブロックのうち前記交点骨格ブロックを除くものから構成される１又は複数のクラスタを横方向骨格クラスタ、
及び、前記縦方向骨格ブロックでも横方向骨格ブロックでもない回路ブロックで構成され、前記縦方向骨格クラスタ及び前記横方向骨格クラスタによって区画された２以上のクラスタを基本クラスタ
とすると、
前記第１のステップにおいて、横方向に連接するクラスタ列の幅の最大値と最小値との差が所定の閾値以下であり、且つ、縦方向に連接するクラスタ列の高さの最大値と最小値との差が所定の閾値以下であるように、前記縦方向骨格ブロック及び前記横方向骨格ブロックの配分を行うことを特徴とする請求項１記載のレイアウト推定方法。
【請求項３】
前記回路ブロック配分手段は、
一の前記縦方向骨格クラスタに属するすべての回路ブロックの高さの総和を縦方向骨格クラスタの高さとし、その縦方向骨格クラスタに属するすべての回路ブロックの幅の平均値を縦方向骨格クラスタの幅として演算し、
一の前記横方向骨格クラスタに属するすべての回路ブロックの幅の総和を横方向骨格クラスタの幅とし、その横方向骨格クラスタに属するすべての回路ブロックの高さの平均値を横方向骨格クラスタの高さとして演算し、
前記交点骨格クラスタ及び一の前記基本クラスタに属するすべての回路ブロックの面積の総和の平方根を当該クラスタの高さ及び幅として演算することにより、
前記横方向に連接するクラスタ列に属する各クラスタの幅の総和、及び前記縦方向に連接するクラスタ列に属する各クラスタの高さの総和を演算することを特徴とする請求項２記載のレイアウト推定方法。
【請求項４】
前記クラスタのうち、あるクラスタＰに属する回路ブロックｘに連結する配線のうち、他のクラスタＱに属する回路ブロックに連結するものの数を「回路ブロックｘとクラスタＱとの結合数」とし、また、クラスタＰに属するすべての回路ブロックｘについて回路ブロックｘとクラスタＱとの結合数を加えたものを「クラスタＰとクラスタＱとの結合数」とし、クラスタＰとクラスタＱとの結合数をすべての一対のクラスタＰ，Ｑの組み合わせについて加えたものを「全結合数」とする場合、
前記第１のステップにおいて、横方向に連接するクラスタ列の幅の最大値と最小値との差が所定の閾値以下であり、且つ、縦方向に連接するクラスタ列の高さの最大値と最小値との差が所定の閾値以下であるという条件下において、全結合数が極小となるように、前記縦方向骨格ブロック及び前記横方向骨格ブロックの配分を行うことを特徴とする請求項２又は３に記載のレイアウト推定方法。
【請求項５】
前記第１のステップにおいて、すべての回路ブロックを２つの縦方向骨格クラスタ、２つの横方向骨格クラスタ、１つの交点骨格クラスタ、及び４つの基本クラスタに配分するものとし、
（１）最初にすべての回路ブロックを４つの基本クラスタに配分し、
（２）すべての回路ブロックのうち、自己が属するクラスタ以外のクラスタとの結合数の総和が大きいものから所定の数の回路ブロックを、前記交点骨格ブロックに配分し、
（３）各基本クラスタに属する各回路ブロックのうち、縦方向骨格クラスタを挟んで相対する基本クラスタとの結合数が最大のものを当該縦方向骨格クラスタに移し、各基本クラスタに属する各回路ブロックのうち、横方向骨格クラスタを挟んで相対する基本クラスタとの結合数が最大のものを当該横方向骨格クラスタに移す操作を、横方向に連接するクラスタ列の幅の最大値と最小値との差が所定の閾値以下で、且つ、縦方向に連接するクラスタ列の高さの最大値と最小値との差が所定の閾値以下となるまで反復して行うこと
を特徴とする請求項４記載のレイアウト推定方法。
【請求項６】
前記回路配置領域において、交点骨格クラスタ、縦方向骨格クラスタ、横方向骨格クラスタ、及び基本クラスタのそれぞれのクラスタに属する回路ブロックが、各クラスタの中心位置に存在するものとしたときの配線の長さの総和を演算し、この総和を全配線長として推定する第３の過程を備えていることを特徴とする請求項２記載のレイアウト推定方法。
【請求項７】
複数の回路ブロック、及び各回路ブロックの間を連結する配線で構成される入力回路を方形の回路配置領域に最密充填する場合において、入力回路を搭載するために必要とされる前記回路配置領域の大きさを推定するレイアウト推定装置であって、
入力回路を構成する回路ブロックの形状及びサイズに関する情報（以下、「回路ブロック情報」という。）及び各回路ブロック間を結合する配線の情報（以下、「配線情報」という。）が格納された回路情報記憶手段と、
前記回路情報記憶手段に格納されたすべての前記回路ブロック情報のうちの一部を選択し、前記回路配置領域の底辺から上辺まで、前記回路配置領域の縦方向に一列に連接して配列される一群の回路ブロック（縦方向骨格ブロック）、及び前記回路配置領域の左辺から右辺まで、前記回路配置領域の横方向に一列に連接して配列される一群の回路ブロック（横方向骨格ブロック）に配分する回路ブロック配分手段と、
前記各縦方向骨格ブロックの回路ブロック情報から、前記各縦方向骨格ブロックの高さの総和を前記回路配置領域の高さとして算出し、前記各横方向骨格ブロックの回路ブロック情報から、前記横方向骨格ブロックの幅の総和を前記回路配置領域の幅として算出する領域サイズ推定手段と、
を備えていることを特徴とするレイアウト推定装置。
【請求項８】
前記縦方向骨格ブロックであり且つ前記横方向骨格ブロックでもある骨格ブロック（交点骨格ブロック）により構成されるクラスタを交点骨格クラスタ、
前記縦方向骨格ブロックのうち前記交点骨格ブロックを除くものから構成される１又は複数のクラスタを縦方向骨格クラスタ、
前記横方向骨格ブロックのうち前記交点骨格ブロックを除くものから構成される１又は複数のクラスタを横方向骨格クラスタ、
及び、前記縦方向骨格ブロックでも横方向骨格ブロックでもない回路ブロックで構成され、前記縦方向骨格クラスタ及び前記横方向骨格クラスタによって区画された２以上のクラスタを基本クラスタ
とすると、
前記回路ブロック配分手段は、横方向に連接するクラスタ列の幅の最大値と最小値との差が所定の閾値以下であり、且つ、縦方向に連接するクラスタ列の高さの最大値と最小値との差が所定の閾値以下であるように、前記縦方向骨格ブロック及び前記横方向骨格ブロックの配分を行うことを特徴とする請求項７記載のレイアウト推定装置。
【請求項９】
前記回路ブロック配分手段は、
一の前記縦方向骨格クラスタに属するすべての回路ブロックの高さの総和を縦方向骨格クラスタの高さとし、その縦方向骨格クラスタに属するすべての回路ブロックの幅の平均値を縦方向骨格クラスタの幅として演算し、
一の前記横方向骨格クラスタに属するすべての回路ブロックの幅の総和を横方向骨格クラスタの幅とし、その横方向骨格クラスタに属するすべての回路ブロックの高さの平均値を横方向骨格クラスタの高さとして演算し、
前記交点骨格クラスタ及び一の前記基本クラスタに属するすべての回路ブロックの面積の総和の平方根を当該クラスタの高さ及び幅として演算するクラスタサイズ演算手段と、
前記横方向に連接するクラスタ列（以下、「横クラスタ列」という。）に属する各クラスタの幅の総和（以下、「横クラスタ列の幅」という。）を演算する横クラスタ幅演算手段と、
前記縦方向に連接するクラスタ列（以下、「縦クラスタ列」という。）に属する各クラスタの高さの総和（以下、「縦クラスタ列の高さ」という。）を演算する縦クラスタ高演算手段と、
前記横クラスタ幅演算手段が算出する各横クラスタ列の幅のうち最大値と最小値との差が所定の閾値以下であり、且つ、前記縦クラスタ高演算手段が算出する各縦クラスタ列の高さのうち最大値と最小値との差が所定の閾値以下となるように、前記縦方向骨格ブロック及び前記横方向骨格ブロックの配分を行う配分調節手段と、
を備えていることを特徴とする請求項８記載のレイアウト推定装置。
【請求項１０】
前記クラスタのうち、あるクラスタＰに属する回路ブロックｘに連結する配線のうち、他のクラスタＱに属する回路ブロックに連結するものの数を「回路ブロックｘとクラスタＱとの結合数」とし、また、クラスタＰに属するすべての回路ブロックｘについて回路ブロックｘとクラスタＱとの結合数を加えたものを「クラスタＰとクラスタＱとの結合数」とし、クラスタＰとクラスタＱとの結合数をすべての一対のクラスタＰ，Ｑの組み合わせについて加えたものを「全結合数」とする場合、
前記配分調節手段は、前記横クラスタ幅演算手段が算出する各横クラスタ列の幅のうち最大値と最小値との差が所定の閾値以下であり、且つ、前記縦クラスタ高演算手段が算出する各縦クラスタ列の高さのうち最大値と最小値との差が所定の閾値以下であるという条件下において、全結合数が極小となるように、前記縦方向骨格ブロック及び前記横方向骨格ブロックの配分を行うことを特徴とする請求項８又は９に記載のレイアウト推定装置。
【請求項１１】
前記回路ブロック配分手段は、
すべての回路ブロックを４つの基本クラスタに配分する初期配分手段と、
すべての回路ブロックのうち、自己が属するクラスタ以外のクラスタとの結合数の総和が大きいものから所定の数の回路ブロックを、前記交点骨格ブロックに配分する交点骨格ブロック配分手段と、
を備えており、
前記配分調節手段は、各基本クラスタに属する各回路ブロックのうち、縦方向骨格クラスタを挟んで相対する基本クラスタとの結合数が最大のものを当該縦方向骨格クラスタに移し、各基本クラスタに属する各回路ブロックのうち、横方向骨格クラスタを挟んで相対する基本クラスタとの結合数が最大のものを当該横方向骨格クラスタに移す操作を、横方向に連接するクラスタ列の幅の最大値と最小値との差が所定の閾値以下で、且つ、縦方向に連接するクラスタ列の高さの最大値と最小値との差が所定の閾値以下となるまで反復して行うこと
を特徴とする請求項１０記載のレイアウト推定装置。
【請求項１２】
前記回路配置領域において、交点骨格クラスタ、縦方向骨格クラスタ、横方向骨格クラスタ、及び基本クラスタのそれぞれのクラスタに属する回路ブロックが、各クラスタの中心位置に存在するものとしたときの配線の長さの総和を演算する全配線長推定手段を備えていることを特徴とする請求項８記載のレイアウト推定装置。
【請求項１３】
複数の回路ブロック、及び各回路ブロックの間を連結する配線で構成される入力回路を方形の回路配置領域に最密充填する場合において、入力回路を搭載するために必要とされる前記回路配置領域の大きさを推定するためのレイアウト推定プログラムであって、
すべての前記回路ブロックのうちの一部を選択し、前記回路配置領域の底辺から上辺まで、前記回路配置領域の縦方向に一列に連接して配列される一群の回路ブロック（縦方向骨格ブロック）、及び前記回路配置領域の左辺から右辺まで、前記回路配置領域の横方向に一列に連接して配列される一群の回路ブロック（横方向骨格ブロック）に配分する第１のステップと、
前記縦方向骨格ブロックの高さの総和を前記回路配置領域の高さとし、前記横方向骨格ブロックの幅の総和を前記回路配置領域の幅として、前記回路配置領域の大きさを推定する第２のステップと、
をコンピュータに実行させることを特徴とするレイアウト推定プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、半導体集積回路やプリント基板回路の回路設計において、回路を物理的に配置した際のレイアウト・サイズ等を少ない計算量で推定するためのレイアウト推定技術に関する。
【背景技術】
【０００２】
半導体集積回路の設計やプリント基板回路の設計においては、複数の回路ブロックで構成された回路をできる限り小さい領域に搭載するとともに、配線長を短くしてタイミングを保証するため、回路ブロックの配置設計が重要である。このような配置設計の技術については、従来からフロアプランとして多くの研究がなされている。
【０００３】
図７は半導体集積回路の設計の流れを示したものである。まず、設計目標となる回路についてのアルゴリズム設計が行われ（Ｓ１０１）、次いでアルゴリズムに基づいてアーキテクチャ設計が行われる（Ｓ１０２）。次に、設計されたアーキテクチャに基づき論理設計が行われる（Ｓ１０３）。この段階で、回路ブロックのサイズや回路ブロック間の配線が具体的に定まる。そこで、これらの回路ブロックを最適な配置をすべく、フロアプランが行われる（Ｓ１０４）。そして、最後に、フロアプランに基づいてレイアウト設計が行われる（Ｓ１０５）。なお、図７は、基本的な設計の流れを表した図である。実際には、より複雑な工程により回路設計はなされるが、ここでは説明のため簡略化している。また、アーキテクチャ設計が終了した段階で、使用する回路ブロックは限られてくるので、場合によっては論理設計の前にフロアプランが行われる場合もある。
【０００４】
従来のフロアプランに関する技術としては、例えば、特許文献１及び非特許文献１に記載されたシーケンス・ペア（sequence-pair）表現を用いた方法や、さらに非特許文献２に記載されたような超階層制約（super hierarchical constraints）の概念を用いた方法が公知である。
【特許文献１】特開平９−１０８９３４号広報
【非特許文献１】H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani, "VLSI module placement based on rectangle-packing by the sequence pair", IEEE Transaction on Computer Aided Design of Integrated Circuits and Systems, Vol.15, No.12, pp.1518-1524, 1996.
【非特許文献２】S.Nakatake, Y.Kubo and Y.Kajitani, "Consistent Floorplanning with Superhierarchical Constraints", Trans. on Computer-Aided Design of IC's and Systems, Vol.21, No.1, pp.42-49, 2002.
【発明の開示】
【発明が解決しようとする課題】
【０００５】
フロアプランは、基本的には与えられた形状の回路ブロックを与えられた形状の領域内にできるだけ最密充填となるように配置する。この場合、回路ブロックの数が多くなると、回路ブロックの配置の仕方は増大する。従って、最適解を求めるためには多くの計算時間が必要となる。
【０００６】
ところで、近年、特に半導体集積回路が微細化し、ディープ・サブミクロンへとスケーリングしてきている。このように回路が微細化してくると、特に配線がタイミング、ノイズ、信頼性に与える影響が顕在化する。そこで、できる限り回路ブロックが最密充填配置され、かつ配線長ができる限り短くなる回路設計が必要とされる。従って、アーキテクチャ設計の段階から、ある程度の回路の物理的サイズを考慮した設計が要求される。すなわち、アーキテクチャ設計段階でのフロアプランの技術が要求される。
【０００７】
一方、システムＬＳＩの高位設計では、チップの性能仕様を満たすように、最適なハードウェア／ソフトウェア分割やコンポーネントの選択が行われる。これらの分割や選択の最適化における評価基準の一つとして、チップ面積が用いられる。この評価基準に従って、多数のハードウェア候補から最適なものを選び出す。そのため、一つの候補が与えられたときに、それに対応するチップ面積を高速に計算することができる技術が必要とされる。
【０００８】
しかしながら、アーキテクチャ設計段階では、回路ブロックの選択肢が多く、最適な回路ブロックの配置を求めるためには、回路ブロックの配置の仕方に加えて、回路ブロックの選択の仕方が不確定要素として加わる。そのため、従来のフロアプランの方法を使用すると、計算量が飛躍的に多くなり、実用的ではない。
【０００９】
そこで、本発明は、回路をレイアウト配置した際のサイズ等を少ない計算量で高速に推定することが可能なレイアウト推定技術を提供することにある。
【課題を解決するための手段】
【００１０】
上記目的を達成するために、本発明においては、骨格ブロックの概念を導入するとともに、フロアプランの抽象化を行う。そこで、まずこれらの事項について説明する。
【００１１】
〔１〕骨格ブロック
互いに配線で連結された１８個の回路ブロック１，２，…，９，ａ，…，ｉを、四角形のチップに、配線長がなるべく短くなるように最密充填することを考える。ここで、各回路ブロックは、４つのクラスタＡ，Ｂ，Ｃ，Ｄに次のように区分されているものとする。
Ａ＝｛１，２，３，４｝
Ｂ＝｛５，６，７，ａ，ｂ｝
Ｃ＝｛８，９，ｃ，ｄ｝
Ｄ＝｛ｅ，ｆ，ｇ，ｈ，ｉ｝
【００１２】
クラスタＡはチップの左上、クラスタＢはチップの右上、クラスタＣはチップの左下、クラスタＤはチップの右下に配置するものとする。またこの配置によって、各クラスタは壊れないものとする。このような条件下で、各回路ブロックをチップに充填すると、例えば、図１のようになる。図１において、このチップの幅は、横方向の回路ブロックの列３−４−ａ−ｂ−ｇで決まる。また、チップの高さは、縦方向の回路ブロックの列２−５−ａ−ｃ−ｅで決まる。
【００１３】
次に、クラスタＢに属する回路ブロックａの位置について考える。回路ブロックａは、クラスタＣの回路ブロック９，ｃ及びクラスタＤの回路ブロックｆと結合している。従って、配線長をできるだけ短くするためには、回路ブロックａは、クラスタＣ，Ｄに近接した位置にあるべきである。以上のようなことから、チップのレイアウトはある特定の回路ブロックに注目すればよいことがわかる。
【００１４】
これらの回路ブロックを骨格ブロック（pillar block）という。図１においては、骨格ブロックを太線の四角形で示している。また、本明細書では、縦方向の骨格ブロック２，５，ａ，ｃ，ｅを縦方向骨格ブロック、横方向の骨格ブロック３，４，ａ，ｂ，ｇを横方向骨格ブロックと呼ぶことにする。
【００１５】
また、このような、骨格ブロックを用いて回路ブロック配置の概略構造を求めることをフロアプランの抽象化という。
【００１６】
なお、ある回路ブロックｘが、クラスタＰ（Ｐ∈｛Ａ、Ｂ，Ｃ，Ｄ｝）に属する何れかの回路ブロックと連結している配線の数を結合数（incident value）といい、I(x,P)と記す。例えば、図１において、I(a,A)=0, I(a,B)=1, I(a,C)=2, I(a,D)=1である。
【００１７】
〔２〕本発明の構成
本発明のレイアウト推定方法は、複数の回路ブロック、及び各回路ブロックの間を連結する配線で構成される入力回路を方形の回路配置領域に最密充填する場合において、入力回路を搭載するために必要とされる前記回路配置領域の大きさを推定するレイアウト推定方法であって、すべての前記回路ブロックのうちの一部を選択し、前記回路配置領域の底辺から上辺まで、前記回路配置領域の縦方向に一列に連接して配列される一群の回路ブロック（以下、これらの回路ブロックを「縦方向骨格ブロック」という。）、及び前記回路配置領域の左辺から右辺まで、前記回路配置領域の横方向に一列に連接して配列される一群の回路ブロック（以下、これらの回路ブロックを「横方向骨格ブロック」という。）に配分する第１のステップと、前記縦方向骨格ブロックの高さの総和を前記回路配置領域の高さとし、前記横方向骨格ブロックの幅の総和を前記回路配置領域の幅として、前記回路配置領域の大きさを推定する第２のステップとを備えていることを特徴とする。
【００１８】
このように、本発明では、全回路ブロックから選択された特定の回路ブロック、すなわち、縦方向骨格ブロック及び横方向骨格ブロックのみに着目した。これらの縦方向骨格ブロックの高さの和は、回路配置領域に最密充填したときの回路配置領域の高さを代表する。また、これらの横方向骨格ブロックの幅の和は、回路配置領域に最密充填したときの回路配置領域の幅を代表する。そこで、縦方向骨格ブロックの高さの総和を回路配置領域の高さと推定し、横方向骨格ブロックの幅の総和を回路配置領域の幅と推定することで、回路配置領域の大きさを推定する。これにより、すべての回路ブロックの配置を計算しなくても、およそのレイアウト・サイズの推定が可能である。
【００１９】
また、本発明において、前記縦方向骨格ブロックであり且つ前記横方向骨格ブロックでもある骨格ブロック（以下、「交点骨格ブロック」という。）により構成されるクラスタを交点骨格クラスタ、前記縦方向骨格ブロックのうち前記交点骨格ブロックを除くものから構成される１又は複数のクラスタを縦方向骨格クラスタ、前記横方向骨格ブロックのうち前記交点骨格ブロックを除くものから構成される１又は複数のクラスタを横方向骨格クラスタ、及び、前記縦方向骨格ブロックでも横方向骨格ブロックでもない回路ブロックで構成され、前記縦方向骨格クラスタ及び前記横方向骨格クラスタによって区画された２以上のクラスタを基本クラスタとすると、前記第１のステップにおいて、横方向に連接するクラスタ列の幅の最大値と最小値との差が所定の閾値以下であり、且つ、縦方向に連接するクラスタ列の高さの最大値と最小値との差が所定の閾値以下であるように、前記縦方向骨格ブロック及び前記横方向骨格ブロックの配分を行うことができる。
【００２０】
このような配分条件を均等条件とよぶ。均等条件を課すことによって、縦方向骨格ブロックの高さの和が、回路配置領域のおよその高さを表すことが保証される。また、横方向骨格ブロックの高さの和が、回路配置領域のおよその幅を表すことが保証される。
【００２１】
ここで、「横方向に連接するクラスタ列」とは、横１列に連接する基本クラスタと縦方向骨格クラスタとから構成されるクラスタ列、又は横１列に連接する横方向骨格クラスタと交点骨格クラスタとから構成される列をいう。また、「縦方向に連接するクラスタ列」とは、縦１列に連接する基本クラスタと横方向骨格クラスタとから構成されるクラスタ列、又は縦１列に連接する縦方向骨格クラスタと交点骨格クラスタとから構成される列をいう。
【００２２】
また、本発明において、前記回路ブロック配分手段は、ａ．一の前記縦方向骨格クラスタに属するすべての回路ブロックの高さの総和を縦方向骨格クラスタの高さとし、その縦方向骨格クラスタに属するすべての回路ブロックの幅の平均値を縦方向骨格クラスタの幅として演算し、ｂ．一の前記横方向骨格クラスタに属するすべての回路ブロックの幅の総和を横方向骨格クラスタの幅とし、その横方向骨格クラスタに属するすべての回路ブロックの高さの平均値を横方向骨格クラスタの高さとして演算し、ｃ．前記交点骨格クラスタ及び一の前記基本クラスタに属するすべての回路ブロックの面積の総和の平方根を当該クラスタの高さ及び幅として演算することにより、前記横方向に連接するクラスタ列に属する各クラスタの幅の総和、及び前記縦方向に連接するクラスタ列に属する各クラスタの高さの総和を演算することができる。
【００２３】
このように、縦方向骨格クラスタの幅、横方向骨格クラスタの高さ、並びに前記交点骨格クラスタ及び前記基本クラスタの幅及び高さを平均化された値で代表し、およその幅又は高さを推算することによって、各クラスタ内における回路ブロックの配置は考慮する必要がなくなる。また、回路ブロック数が多ければ、統計的に、上記平均化された値は各クラスタの幅又は高さの実際の値に近くなると考えられる。従って、少ない計算量で各クラスタの幅及び高さを推定することが可能となる。
【００２４】
また、本発明において、前記クラスタのうち、あるクラスタＰに属する回路ブロックｘに連結する配線のうち、他のクラスタＱに属する回路ブロックに連結するものの数を「回路ブロックｘとクラスタＱとの結合数」とし、また、クラスタＰに属するすべての回路ブロックｘについて回路ブロックｘとクラスタＱとの結合数を加えたものを「クラスタＰとクラスタＱとの結合数」とし、クラスタＰとクラスタＱとの結合数をすべての一対のクラスタＰ，Ｑの組み合わせについて加えたものを「全結合数」とする場合、前記第１のステップにおいて、横方向に連接するクラスタ列の幅の最大値と最小値との差が所定の閾値以下であり、且つ、縦方向に連接するクラスタ列の高さの最大値と最小値との差が所定の閾値以下であるという条件下において、全結合数が極小となるように、前記縦方向骨格ブロック及び前記横方向骨格ブロックの配分を行うことができる。
【００２５】
このように、均等条件に加えて、全結合数の極小化条件を課すことによって、各クラスタ間の配線数を短くすることができる。このことは、回路全体における配線長が短くなることを意味する。従って、より最適化された物理配置におけるレイアウト面積を推定することが可能となる。
【００２６】
ここで、「クラスタ」とは、交点骨格クラスタ、縦方向骨格クラスタ、横方向骨格クラスタ、又は基本クラスタの何れかのクラスタをいう。
【００２７】
また、本発明において、前記第１のステップにおいて、すべての回路ブロックを２つの縦方向骨格クラスタ、２つの横方向骨格クラスタ、１つの交点骨格クラスタ、及び４つの基本クラスタに配分するものとし、
（１）最初にすべての回路ブロックを４つの基本クラスタに配分し、
（２）すべての回路ブロックのうち、自己が属するクラスタ以外のクラスタとの結合数の総和が大きいものから所定の数の回路ブロックを、前記交点骨格ブロックに配分し、
（３）各基本クラスタに属する各回路ブロックのうち、縦方向骨格クラスタを挟んで相対する基本クラスタとの結合数が最大のものを当該縦方向骨格クラスタに移し、各基本クラスタに属する各回路ブロックのうち、横方向骨格クラスタを挟んで相対する基本クラスタとの結合数が最大のものを当該横方向骨格クラスタに移す操作を、横方向に連接するクラスタ列の幅の最大値と最小値との差が所定の閾値以下で、且つ、縦方向に連接するクラスタ列の高さの最大値と最小値との差が所定の閾値以下となるまで反復して行うことができる。
【００２８】
これにより、均等条件を満たし、かつ全結合数の極小化条件を満たすように、各クラスタに各回路ブロックを配分することができる。
【００２９】
また、本発明において、前記回路配置領域において、交点骨格クラスタ、縦方向骨格クラスタ、横方向骨格クラスタ、及び基本クラスタのそれぞれのクラスタに属する回路ブロックが、各クラスタの中心位置に存在するものとしたときの配線の長さの総和を演算し、この総和を全配線長として推定する第３の過程を備えた構成とすることができる。
【００３０】
これにより、配線長のおよその値を推定することができる。従って、この配線長をもとに、合理的な手法で回路の消費電力を概算することが可能となる。
【００３１】
本発明に係るレイアウト推定装置は、複数の回路ブロック、及び各回路ブロックの間を連結する配線で構成される入力回路を方形の回路配置領域に最密充填する場合において、入力回路を搭載するために必要とされる前記回路配置領域の大きさを推定するレイアウト推定装置であって、入力回路を構成する回路ブロックの形状及びサイズに関する情報（以下、「回路ブロック情報」という。）及び各回路ブロック間を結合する配線の情報（以下、「配線情報」という。）が格納された回路情報記憶手段と、前記回路情報記憶手段に格納されたすべての前記回路ブロック情報のうちの一部を選択し、前記回路配置領域の底辺から上辺まで、前記回路配置領域の縦方向に一列に連接して配列される一群の回路ブロック（縦方向骨格ブロック）、及び前記回路配置領域の左辺から右辺まで、前記回路配置領域の横方向に一列に連接して配列される一群の回路ブロック（横方向骨格ブロック）に配分する回路ブロック配分手段と、前記各縦方向骨格ブロックの回路ブロック情報から、前記各縦方向骨格ブロックの高さの総和を前記回路配置領域の高さとして算出し、前記各横方向骨格ブロックの回路ブロック情報から、前記横方向骨格ブロックの幅の総和を前記回路配置領域の幅として算出する領域サイズ推定手段とを備えていることを特徴とする。
【００３２】
この構成により、回路ブロック配分手段により特定の回路ブロックが縦方向骨格ブロック及び横方向骨格ブロックに配分される。領域サイズ推定手段は、この縦方向骨格ブロック及び横方向骨格ブロックの高さ及び幅に基づいて回路配置領域のサイズを推定することができる。
【００３３】
また、本発明において、前記縦方向骨格ブロックであり且つ前記横方向骨格ブロックでもある骨格ブロック（交点骨格ブロック）により構成されるクラスタを交点骨格クラスタ、前記縦方向骨格ブロックのうち前記交点骨格ブロックを除くものから構成される１又は複数のクラスタを縦方向骨格クラスタ、前記横方向骨格ブロックのうち前記交点骨格ブロックを除くものから構成される１又は複数のクラスタを横方向骨格クラスタ、及び、前記縦方向骨格ブロックでも横方向骨格ブロックでもない回路ブロックで構成され、前記縦方向骨格クラスタ及び前記横方向骨格クラスタによって区画された２以上のクラスタを基本クラスタとすると、前記回路ブロック配分手段は、横方向に連接するクラスタ列の幅の最大値と最小値との差が所定の閾値以下であり、且つ、縦方向に連接するクラスタ列の高さの最大値と最小値との差が所定の閾値以下であるように、前記縦方向骨格ブロック及び前記横方向骨格ブロックの配分を行うことができる。
【００３４】
この構成により、回路ブロック配分手段が配分する縦方向骨格ブロック及び横方向骨格ブロックの高さ及び幅が、最密充填された回路配置領域のおよその高さ及び幅を表すことが保証される。
【００３５】
また、本発明において、前記回路ブロック配分手段は、一の前記縦方向骨格クラスタに属するすべての回路ブロックの高さの総和を縦方向骨格クラスタの高さとし、その縦方向骨格クラスタに属するすべての回路ブロックの幅の平均値を縦方向骨格クラスタの幅として演算し、一の前記横方向骨格クラスタに属するすべての回路ブロックの幅の総和を横方向骨格クラスタの幅とし、その横方向骨格クラスタに属するすべての回路ブロックの高さの平均値を横方向骨格クラスタの高さとして演算し、前記交点骨格クラスタ及び一の前記基本クラスタに属するすべての回路ブロックの面積の総和の平方根を当該クラスタの高さ及び幅として演算するクラスタサイズ演算手段と、前記横方向に連接するクラスタ列（以下、「横クラスタ列」という。）に属する各クラスタの幅の総和（以下、「横クラスタ列の幅」という。）を演算する横クラスタ幅演算手段と、前記縦方向に連接するクラスタ列（以下、「縦クラスタ列」という。）に属する各クラスタの高さの総和（以下、「縦クラスタ列の高さ」という。）を演算する縦クラスタ高演算手段と、前記横クラスタ幅演算手段が算出する各横クラスタ列の幅のうち最大値と最小値との差が所定の閾値以下であり、且つ、前記縦クラスタ高演算手段が算出する各縦クラスタ列の高さのうち最大値と最小値との差が所定の閾値以下となるように、前記縦方向骨格ブロック及び前記横方向骨格ブロックの配分を行う配分調節手段とを備えた構成とすることができる。
【００３６】
また、本発明において、前記クラスタのうち、あるクラスタＰに属する回路ブロックｘに連結する配線のうち、他のクラスタＱに属する回路ブロックに連結するものの数を「回路ブロックｘとクラスタＱとの結合数」とし、また、クラスタＰに属するすべての回路ブロックｘについて回路ブロックｘとクラスタＱとの結合数を加えたものを「クラスタＰとクラスタＱとの結合数」とし、クラスタＰとクラスタＱとの結合数をすべての一対のクラスタＰ，Ｑの組み合わせについて加えたものを「全結合数」とする場合、前記配分調節手段は、前記横クラスタ幅演算手段が算出する各横クラスタ列の幅のうち最大値と最小値との差が所定の閾値以下であり、且つ、前記縦クラスタ高演算手段が算出する各縦クラスタ列の高さのうち最大値と最小値との差が所定の閾値以下であるという条件下において、全結合数が極小となるように、前記縦方向骨格ブロック及び前記横方向骨格ブロックの配分を行うように構成することができる。
【００３７】
また、本発明において、前記回路ブロック配分手段は、すべての回路ブロックを４つの基本クラスタに配分する初期配分手段と、すべての回路ブロックのうち、自己が属するクラスタ以外のクラスタとの結合数の総和が大きいものから所定の数の回路ブロックを、前記交点骨格ブロックに配分する交点骨格ブロック配分手段とを備えており、前記配分調節手段は、各基本クラスタに属する各回路ブロックのうち、縦方向骨格クラスタを挟んで相対する基本クラスタとの結合数が最大のものを当該縦方向骨格クラスタに移し、各基本クラスタに属する各回路ブロックのうち、横方向骨格クラスタを挟んで相対する基本クラスタとの結合数が最大のものを当該横方向骨格クラスタに移す操作を、横方向に連接するクラスタ列の幅の最大値と最小値との差が所定の閾値以下で、且つ、縦方向に連接するクラスタ列の高さの最大値と最小値との差が所定の閾値以下となるまで反復して行うようにすることができる。
【００３８】
また、本発明において、前記回路配置領域において、交点骨格クラスタ、縦方向骨格クラスタ、横方向骨格クラスタ、及び基本クラスタのそれぞれのクラスタに属する回路ブロックが、各クラスタの中心位置に存在するものとしたときの配線の長さの総和を演算する全配線長推定手段を備えた構成とすることができる。
【００３９】
また、本発明に係るレイアウト推定プログラムは、複数の回路ブロック、及び各回路ブロックの間を連結する配線で構成される入力回路を方形の回路配置領域に最密充填する場合において、入力回路を搭載するために必要とされる前記回路配置領域の大きさを推定するためのレイアウト推定プログラムであって、すべての前記回路ブロックのうちの一部を選択し、前記回路配置領域の底辺から上辺まで、前記回路配置領域の縦方向に一列に連接して配列される一群の回路ブロック（縦方向骨格ブロック）、及び前記回路配置領域の左辺から右辺まで、前記回路配置領域の横方向に一列に連接して配列される一群の回路ブロック（横方向骨格ブロック）に配分する第１のステップと、前記縦方向骨格ブロックの高さの総和を前記回路配置領域の高さとし、前記横方向骨格ブロックの幅の総和を前記回路配置領域の幅として、前記回路配置領域の大きさを推定する第２のステップとをコンピュータに実行させることを特徴とする。
【発明の効果】
【００４０】
以上のように、本発明によれば、大規模な回路（多数の回路ブロックを含む回路）に対して、詳細なブロック配置を行うことなくして、レイアウトの面積又は配線長の近似値を知ることが可能となる。すなわち、少ない計算量で高速におよそのレイアウト・サイズ等の推定が可能である。
【００４１】
また、基本クラスタに含まれる回路ブロックは、面積のみが決定していて幅と高さが決定していないソフトブロックでもよい。従って、レイアウトが未決定の回路ブロックを多数含むような場合であっても、本発明の方法を適用することが可能である。すなわち、例えば、アーキテクチャ設計段階におけるレイアウト推定方法として適用することができる。
【００４２】
すなわち、システムＬＳＩの高位設計等において、最適なアーキテクチャを検索する際に、実際のブロック配置を行わないで、チップの面積と配線長の近似値を知ることができる。従って、より優れたアーキテクチャ設計が可能となる。
【００４３】
さらに、基本クラスタや骨格クラスタ（縦方向、横方向、及び交点骨格クラスタ）の構造は、取り扱うＬＳＩの種類に従って変更することができる。そして、かかる変更を適用しても、本発明の手法をそのまま適用することができる。
【発明を実施するための最良の形態】
【００４４】
以下、本発明を実施するための最良の形態について、図面を参照しながら説明する。
【実施例１】
【００４５】
図２は本発明の実施例１に係るレイアウト推定装置の構成を表す図である。図２において、レイアウト推定装置１には、回路情報を入力する入力装置２，及び入力された回路情報を表示したり推定により得られる回路配置の概略構造を表示したりするための出力装置３が接続されている。
【００４６】
レイアウト推定装置１は、回路情報記憶手段４、回路ブロック配分手段５、領域サイズ推定手段６、及び全配線長推定手段１７を有する。回路情報記憶手段４は、入力装置２から入力される回路ブロック情報及び配線情報を記憶する。回路ブロック配分手段５は、回路情報記憶手段４に格納された回路ブロック情報から一部を選択し、縦方向骨格ブロック、及び横方向骨格ブロックに配分する。領域サイズ推定手段６は、各縦方向骨格ブロックの回路ブロック情報から、各縦方向骨格ブロックの高さの総和を回路配置領域の高さとして算出し、各横方向骨格ブロックの回路ブロック情報から、横方向骨格ブロックの幅の総和を回路配置領域の幅として算出する。算出された回路配置領域の高さと幅に関する情報は、出力装置３に出力される。全配線長推定手段１７は、すべての回路ブロック間を連結する配線長の推定値を演算するものである。全配線長推定手段１７については、後に説明する。
【００４７】
回路ブロック配分手段５は、初期配分手段７、クラスタ記憶手段８、交点骨格ブロック配分手段９、結合数演算手段１０、ブロックリスト生成手段１１、ブロックリスト記憶手段１２、配分調節手段１３、クラスタサイズ演算手段１４、横クラスタ幅演算手段１５、及び縦クラスタ高演算手段１６を有する。
【００４８】
初期配分手段７は、回路情報記憶手段４に格納された回路ブロック情報を読み出して、すべての回路ブロックを４つの基本クラスタＡ，Ｂ，Ｃ，Ｄに配分する。ここで、クラスタＡ，Ｂ，Ｃ，Ｄは、図１に示したように、それぞれ、回路配置領域の左上、右上、左下、右下の区画に位置する。クラスタ記憶手段８は、図３に示した相対的な位置関係にある９個のクラスタＣ１１，Ｃ１２，Ｃ１３，Ｃ２１，Ｃ２２，Ｃ２３，Ｃ３１，Ｃ３２，Ｃ３３を格納する。図３において、Ｃ２１，Ｃ２３は縦方向骨格クラスタ、Ｃ１２，Ｃ３２は横方向骨格クラスタ、Ｃ２２は交点骨格クラスタ、Ｃ１１，Ｃ３１，Ｃ１３，Ｃ３３は基本クラスタという。初期配分手段７は、基本クラスタＡ，Ｂ，Ｃ，Ｄを、それぞれ、基本クラスタＣ１１，Ｃ３１，Ｃ１３，Ｃ３３に格納する。
【００４９】
交点骨格ブロック配分手段９は、すべての回路ブロックのうち、他のクラスタとの結合数の総和が多いものから順に所定の数Ｎ（Ｃ２２）個の回路ブロックを選択し、交点骨格クラスタに移す。結合数演算手段１０は、指定された回路ブロックと指定されたクラスタとの結合数を演算する。ブロックリスト生成手段１１は、クラスタ記憶手段８に記憶された各クラスタについて、そのクラスタに属する回路ブロックを、他のそれぞれのクラスタとの結合数が多い順に並べたリスト（以下、「ブロックリスト」という。）を生成し、ブロックリスト記憶手段１２に格納する。配分調節手段１３は、ブロックリスト記憶手段１２に格納されたブロックリストを参照しながら、クラスタ記憶手段８に格納された各クラスタの回路ブロックの配分の修正を行う。
【００５０】
ここで、各クラスタの配分の修正は、以下の（数１）の条件のもとで行われる。
【００５１】
【数１】
2005209120.tif 000003
【００５２】
クラスタサイズ演算手段１４は、クラスタの幅及び高さを演算する。横クラスタ幅演算手段１５は、横クラスタ列の幅を演算する。縦クラスタ高演算手段１６は、縦クラスタ列の高さを演算する。
【００５３】
以上のように構成された本発明に係るレイアウト推定装置について、以下、そのレイアウト推定方法を説明する。
【００５４】
図４は本発明の実施例１に係るレイアウト推定方法の流れを表すフローチャートである。
【００５５】
まず、最初に、回路情報が入力装置２から入力される。この回路情報は、各回路ブロックのサイズ情報と各回路ブロック間の結合情報からなる。これらの回路情報は、回路情報記憶手段４に記憶される。
【００５６】
そして、初期配分手段７は、回路情報記憶手段４から回路ブロックの情報を読み出して、これらの回路ブロックを４つのクラスタＡ，Ｂ，Ｃ，Ｄに配分する（Ｓ１）。そして、クラスタＡの回路ブロックは、クラスタ記憶手段８の基本クラスタＣ１１の記憶領域へ、クラスタＢの回路ブロックは、クラスタ記憶手段８の基本クラスタＣ３１の記憶領域へ、クラスタＣの回路ブロックは、クラスタ記憶手段８の基本クラスタＣ１３の記憶領域へ、クラスタＤの回路ブロックは、クラスタ記憶手段８の基本クラスタＣ３３の記憶領域へ、それぞれ格納される。また、このとき、クラスタ記憶手段８の横方向骨格クラスタＣ１２，Ｃ３２、縦方向骨格クラスタＣ２１，Ｃ２３及び交点骨格クラスタＣ２２の記憶領域はクリアされる（Ｓ２）。
【００５７】
次に、交点骨格ブロック配分手段９は、結合数演算手段１０に格納された基本クラスタＣ１１，Ｃ３１，Ｃ１３，Ｃ３３の回路ブロックの一部を、交点骨格クラスタＣ２２へ移す（Ｓ３）。この移動は、次のようにして行われる。
【００５８】
図５は交点骨格ブロックの配分処理を表すフローチャートである。まず、交点骨格ブロック配分手段９は、クラスタ記憶手段８に格納されたすべての回路ブロックを読み出し、結合数演算手段１０により、（数２）の結合数I(x)を演算する（Ｓ２０）。
【００５９】
【数２】
2005209120.tif 000004
【００６０】
ここで、I(x)は、クラスタＰに属するブロックｘの結合数I(x,Q)のうち、クラスタＰ以外のクラスタとの結合数の和を表す。
【００６１】
次に、交点骨格ブロック配分手段９は、すべての回路ブロックのうち、I(x)の大きい順にＮ（Ｃ２２）個の回路ブロックを選択し、これを、クラスタ記憶手段８内の各基本クラスタから交点骨格クラスタに移動する。
【００６２】
以上の処理によって、自己が属するクラスタ以外のクラスタとの結合数の大きい回路ブロックは、中央の交点骨格ブロックに集められる。従って、全体の配線長は短くなる方向に向かう。
【００６３】
図４に戻って、ブロックリスト生成手段１１は、結合数演算手段１０により各回路ブロックの結合数を計算しながら、８個のブロックリストLAB, LAC, LBA, LBD, LCA, LCD, LDB, LDCを生成する（Ｓ４）。ここで、ブロックリストLPQは、クラスタＰに属する回路ブロックのリストであって、I(x,Q) （x∈P）が大きい順に並べられたリストである。ブロックリスト生成手段１１は、生成した８個のブロックリストを、ブロックリスト記憶手段１２に格納する。
【００６４】
次に、配分調節手段１３は、ループ回数を表すカウンタｋＨ，ｋＷを０に初期化する（Ｓ５）。
【００６５】
そして、クラスタサイズ演算手段１４は、交点骨格クラスタＣ２２及び基本クラスタＣ１１，Ｃ３１，Ｃ１３，Ｃ３３のサイズを、（数３）により算出する。また、縦方向骨格クラスタＣ２１，Ｃ２３の幅，高さを（数４）により算出する。また、横方向骨格クラスタＣ１２，Ｃ３２の幅，高さを（数５）により算出する。
【００６６】
【数３】
2005209120.tif 000005
【００６７】
【数４】
2005209120.tif 000006
【００６８】
【数５】
2005209120.tif 000007
【００６９】
ここで、W(Cij),H(Cij)は、それぞれ、クラスタCijの幅，高さを表す。W(x),H(x)は、それぞれ、回路ブロックxの幅，高さを表す。A(Cij),A(x)は、それぞれ、クラスタCijの面積，回路ブロックｘの面積を表す。N(Cij)は、それぞれ、クラスタCijに含まれる回路ブロックの数を表す。
【００７０】
（数３）は、交点骨格クラスタＣ２２及び基本クラスタＣ１１，Ｃ３１，Ｃ１３，Ｃ３３は正方形で近似していることを表している。（数４）は、縦方向骨格クラスタＣ２１，Ｃ２３は、長方形で近似し、その幅は当該クラスタに含まれる回路ブロックの幅の平均値で近似することを表している。（数５）は、横方向骨格クラスタＣ１２，Ｃ３２は、長方形で近似し、その高さは当該クラスタに含まれる回路ブロックの高さの平均値で近似することを表している。
【００７１】
横クラスタ幅演算手段１５は、各横クラスタ列Ｃ１１-Ｃ２１-Ｃ３１，Ｃ１２-Ｃ２２-Ｃ３２，Ｃ１３-Ｃ２３-Ｃ３３の幅Ｗ１，Ｗ２，Ｗ３を演算する。また、縦クラスタ高演算手段１６は、各縦クラスタ列Ｃ１１-Ｃ１２-Ｃ１３，Ｃ２１-Ｃ２２-Ｃ２３，Ｃ３１-Ｃ３２-Ｃ３３の高さＨ１，Ｈ２，Ｈ３を演算する（Ｓ６）。ここで、幅Ｗｊ及び高さＨｉは（数６）で表される。
【００７２】
【数６】
2005209120.tif 000008
【００７３】
次に、配分調節手段１３は、max(H1,H2,H3)-min(H1,H2,H3)が閾値δH以下となり、且つmax(W1,W2,W3)-min(W1,W2,W3)が閾値δW以下となったかどうかを判定する（Ｓ７）。この条件を満たしていない場合には、クラスタの修正処理（EXPAND_H2W2）が行われる（Ｓ８）。
【００７４】
図６はクラスタの修正処理（EXPAND_H2W2）の処理の流れを表す図である。図６において、「MOVE_BLOCK from LAB to C21」と記載された処理は、リストLABの先頭の回路ブロックをクラスタC21へ移すとともに、リストLAB及びリストLACから当該回路ブロックを削除する処理である。他のMOVE_BLOCK操作も同様である。
【００７５】
図６の処理により、縦クラスタ列又は横クラスタ列のうち、もっとも出っ張ったものに属する回路ブロックが、縦方向骨格クラスタ又は横方向骨格クラスタに移される。また、基本クラスタから骨格クラスタへ移される回路ブロックは、その骨格ブロックを挟んで対峙する基本クラスタとの結合数が大きい回路ブロックが優先的に移される。従って、この回路ブロックの移動によって回路全体の結合数は減少に向かうため、配線長が短くなる方向に収束する。
【００７６】
なお、基本クラスタから縦方向骨格クラスタへ回路ブロックが移された場合には、ループ・カウンタｋＨが１だけ増加され（Ｓ３９）、基本クラスタから横方向骨格クラスタへ回路ブロックが移された場合には、ループ・カウンタｋＷが１だけ増加される（Ｓ４０）。
【００７７】
以上のクラスタの修正処理が終わると、図４に戻って、配分調節手段１３は、反復回数kHが閾値K_Hを超えたかどうかを判定する（Ｓ９）。kH>K_Hの場合には、閾値δHを２倍の値に設定し、kHを０に初期化して（Ｓ１０）、再びステップＳ６に戻る。
【００７８】
ステップＳ９でkH≦K_Hの場合、配分調節手段１３は、反復回数kWが閾値K_Wを超えたかどうかを判定する（Ｓ１１）。kW>K_Wの場合には、閾値δWを２倍の値に設定し、kWを０に初期化して（Ｓ１２）、再びステップＳ６に戻る。ステップＳ１１でkW≦K_Wの場合、ステップＳ６に戻る。
【００７９】
一方、上記ステップＳ７において、max(H1,H2,H3)-min(H1,H2,H3)が閾値δH以下となり、且つmax(W1,W2,W3)-min(W1,W2,W3)が閾値δW以下であった場合には、骨格クラスタの配分が正常に終了したことになる。このとき、回路配置領域の高さ及び幅の推定値は、Ｈ２，Ｗ２に確定する。
【００８０】
そこで、次に、全配線長推定手段１７は、クラスタ記憶手段８に格納された回路ブロック情報に基づいて、全配線長の推定を行う（Ｓ１３）。この場合、全配線長推定手段１７は、回路配置領域において、交点骨格クラスタＣ２２、縦方向骨格クラスタＣ２１，Ｃ２３、横方向骨格クラスタＣ１２，Ｃ３２、及び基本クラスタＣ１１，Ｃ３１，Ｃ１３，Ｃ３３のそれぞれのクラスタに属する回路ブロックが、各クラスタの中心位置に存在するものとしたときの配線の長さの総和で近似することにより、全配線長の概略的な近似値を算出する。
【００８１】
そして、最後に、出力装置３は、回路配置領域の高さ及び幅の推定値Ｈ２，Ｗ２を出力し（Ｓ１４）、全配線長の概略的な近似値を出力して（Ｓ１５）、処理を終了する。
【００８２】
以上の処理によって、均等条件を充足し、かつ、全結合数の極小化条件を満たすように、各クラスタに各回路ブロックを配分することができる。そして、その結果として得られる回路配置領域の高さ及び幅の推定値Ｈ２，Ｗ２から、回路のレイアウト・サイズの概算値を知ることができる。
【００８３】
さらに、上記処理によって得られる全配線長の概算値とレイアウト面積とから、１ゲート当たりの消費電力を推算することができる。そして、全回路ブロックのゲート数の情報、並びにスケジュール（単位時間当たりのスイッチング回数）に関する情報があれば、回路の消費電力を推算することも可能である。
【００８４】
なお、上記実施例は、レイアウト推定装置１をハードウェア的に構成し実現した例について説明した。しかし、本発明に係るレイアウト推定装置は、ハードウェアに限らず、プログラムにより構成し、コンピュータに読み込ませて実行することにより、コンピュータとプログラムが協働して本発明に係るレイアウト推定装置を実現するような構成とすることもできる。
【図面の簡単な説明】
【００８５】
【図１】回路ブロックをチップに充填した状態の一例を表す図である。
【図２】本発明の実施例１に係るレイアウト推定装置の構成を表す図である。
【図３】縦方向骨格クラスタ、横方向骨格クラスタ、交点骨格クラスタ、及び基本クラスタの相対的な位置関係を表す図である。
【図４】本発明の実施例１に係るレイアウト推定方法の流れを表すフローチャートである。
【図５】交点骨格ブロックの配分処理を表すフローチャートである。
【図６】クラスタの修正処理（EXPAND_H2W2）の処理の流れを表す図である。
【図７】半導体集積回路の設計の流れを示したものである。
【符号の説明】
【００８６】
１  レイアウト推定装置
２  入力装置
３  出力装置
４  回路情報記憶手段
５  回路ブロック配分手段
６  領域サイズ推定手段
７  初期配分手段
８  クラスタ記憶手段
９  交点骨格ブロック配分手段
１０  結合数演算手段
１１  ブロックリスト生成手段
１２  ブロックリスト記憶手段
１３  配分調節手段
１４  クラスタサイズ演算手段
１５  横クラスタ幅演算手段
１６  縦クラスタ高演算手段
１７  全配線長演算手段
【図１】
2005209120.tif 000009
【図２】
2005209120.tif 000010
【図３】
2005209120.tif 000011
【図４】
2005209120.tif 000012
【図５】
2005209120.tif 000013
【図６】
2005209120.tif 000014
【図７】
2005209120.tif 000015