JP3433025B2 - モジュール配置方法 - Google Patents

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】この発明は、計算機を用いた
大規模ＬＳＩ設計の際のモジュール配置方法に係り、複
数のハードマクロセルと複数の論理階層の一般セルが混
在する大規模システムを設計するモジュール配置方法に
関する。

【０００２】

【従来の技術】従来のフロアプラン手法（モジュール配
置手法）においては、大規模システムのＬＳＩを設計す
るにあたり、特に、次の２つの点を考慮する必要があ
る。

【０００３】考慮すべき第１の点は、半導体集積回路の
微細化により、チップ当たりの搭載可能な回路規模が増
大し、マイクロプロセッサやメモリ、ＤＡ／ＡＤコンバ
ータ、コントロールロジック等、極めて多く種類の大き
さ又は形状の異なるモジュールを扱わなければならない
ことである。こうした大規模システムを１チップ上に最
適にレイアウトするためには、これら性質、大きさや形
状の異なるモジュールを同時に扱うことのできる機能が
必要である。

【０００４】しかしながら、第１の点に関しては、従来
のフロアプラン手法では、一般セルからなるソフトモジ
ュールの配置位置や形状を最適化するだけのものであっ
たり、形状の決まったモジュールを最小面積で配置する
だけでものであったりするなど、上記の設計要求を満た
すものではなく、必ず人手が介入する必要があった。

【０００５】次に考慮すべき第２の点は、配線構造の微
細化に伴い、配線抵抗成分に起因するティレイが回路全
体のディレイに対して大きな割合を占めるようになって
きたことである。これにより、レイアウトによって決定
される各ネットの配線ＲＣディレイが、チップ全体の動
作速度を大きく左右するようになってきた。特に、モジ
ュール間をまたがる配線は、各モジュールをどのように
配置するかによって配線の経路や長さが大きく変化する
ので、モジュール間をまたがる信号経路は、大きな配線
ＲＣディレイが生じやすく、クリティカルパスとなる危
険性が高い。

【０００６】したがって、大規模システムＬＳＩの論理
設計を行うに際して、回路のパフォーマンスを最適化す
るためには、レイアウト後の性能を的確に予測する必要
がある。すなわち、論理設計の早い段階から、レイアウ
ト後の配線ＲＣディレイを見積もりつつ、論理設計を進
める設計手法を行わなければならない。

【０００７】ところが、第２の点に関しては、従来のフ
ロアプラン手法にあっては、全てのモジュール内の論理
設計がゲートのレベルまで完了していないと適用するこ
とは難しかった。したがって、従来の手法を用いたので
は、大規模な回路全体の論理設計を完了して初めてモジ
ュール配置ができる段階に至ることとなる。これでは、
通常の配置処理を実行することと大差なく、レイアウト
設計後に不良個所が発見された場合や、回路変更があっ
た場合には、再び回路全体の論理設計からやり直さなけ
ればならなかった。

【０００８】このように、従来の論理設計又はそれより
も上流の設計段階とレイアウト設計との間を何度も繰り
返し行う設計フローであるので、大規模システムの設計
に適用した場合、設計期間の指数関数的増大を招くばか
りでなく、チップ設計のコストが急速に増大する危険性
があった。

【０００９】

【発明が解決しようとする課題】上述のように、従来の
モジュール配置手法にあっては、形状や性質等の異なる
多様なモジュールを一括して扱えなかったり、全てのモ
ジュール内部の論理設計の詳細が決まっている必要があ
るなどの制約事項が多く、今後の大規模システムＬＳＩ
設計で要求される回路構成を適切に扱えなかったり、論
理設計とレイアウト設計のモジュール単位での並行設計
ができないなどの問題がある。従って、論理設計とレイ
アウト設計を常に回路全体を対象に、設計仕様を満たす
まで何度も繰り返し行わなければならず、非常に多くの
設計期間を要するばかりか、設計コストは増大の一途を
辿ることになる。

【００１０】本発明は、上述の問題点に鑑みなされたも
のであり、その目的は、多数のハードマクロセルと一般
セルが混在するような大規模システムＬＳＩ設計に対し
て、それぞれのモジュールが異なる論理設計段階であっ
ても、モジュール面積や形状を見積もって、人手を介す
ることなく高品質なモジュールの自動配置を実現し、論
理設計に対してより正確なチップの性能予測値を得るこ
とのできるモジュール配置方法を提供することにある。

【００１１】

【課題を解決するための手段】本発明の第１の解決手段
によると、モジュール配置の対象となる回路を複数のモ
ジュールに分割することにより論理階層の第０階層のモ
ジュールとして定義し、前記回路の論理階層構造に基づ
いて前記第０階層より下位の第１階層からなる複数の要
素に分割して第１階層のモジュールとして定義し、さら
に必要に応じて前記第１階層の一部又は全てのモジュー
ルを前記第１階層より下位の第２階層からなる複数の要
素に各々分割してそれぞれ第２階層モジュールとして定
義し、上記分割を前記第０階層の各モジュール毎に必要
に応じてＮ回繰り返して第Ｎ階層のモジュールとして定
義するモジュール分割処理手順と、前記モジュールをノ
ードとして定義し、各階層における各モジュール間のＸ
方向及びＹ方向の隣接関係を前記ノード間を接続するエ
ッジによりＸ方向隣接関係グラフおよびＹ方向隣接関係
グラフとしてそれぞれ表現し、第ｎ階層（ｎは、０〜
（Ｎ−１）の整数）のＸ方向隣接関係グラフおよびＹ方
向隣接関係グラフにおける各ノードが第（ｎ＋１）階層
のＸ方向隣接関係グラフおよびＹ方向隣接関係グラフに
それぞれ対応付けられた多重構造のＸＹ隣接関係グラフ
を作成して、前記回路の全ての要素のモジュール配置を
作成するモジュール配置処理手順と、前記ＸＹ隣接関係
グラフの一部又は全てを変更することで新たなモジュー
ル配置を作成するモジュール配置変更処理手順とを備え
たモジュール配置方法を提供する。

【００１２】また、本発明の第２の解決手段によると、
ネットに関する情報を読み込む入力処理手順と、前記入
力処理手順により入力された前記情報の論理階層構造又
は設計者の指示に従って、モジュール配置の対象となる
回路を複数のモジュールに分割することにより論理階層
の第０階層のモジュールとして定義し、前記回路の論理
階層構造に基づいて前記第０階層より下位の第１階層か
らなる複数の要素に分割して第１階層のモジュールとし
て定義し、さらに必要に応じて前記第１階層の一部又は
全てのモジュールを前記第１階層より下位の第２階層か
らなる複数の要素に各々分割してそれぞれ第２階層モジ
ュールとして定義し、上記分割を前記第０階層の各モジ
ュール毎に必要に応じてＮ回繰り返して第Ｎ階層のモジ
ュールとして定義することにより、前記回路を複数のモ
ジュールに分割するモジュール分割処理手順と、前記モ
ジュールをノードとして定義し、各階層における各モジ
ュール間のＸ方向及びＹ方向の隣接関係を前記ノード間
を接続するエッジによりＸ方向隣接関係グラフおよびＹ
方向隣接関係グラフとしてそれぞれ表現し、第ｎ階層
（ｎは、０〜（Ｎ−１）の整数）のＸ方向隣接関係グラ
フおよびＹ方向隣接関係グラフにおける各ノードが第
（ｎ＋１）階層のＸ方向隣接関係グラフおよびＹ方向隣
接関係グラフにそれぞれ対応付けられた多重構造のＸＹ
隣接関係グラフを作成して、前記回路の全ての要素のモ
ジュール配置を作成することにより、前記モジュール分
割処理手順により作成したモジュールを初期的にチップ
上に並べてＸＹ隣接関係グラフを作成するモジュール配
置処理手順と、前記モジュール配置処理手順により初期
的に作成したモジュール初期配置を前記ＸＹ隣接関係グ
ラフの一部又は全てを変更することで新たなモジュール
配置を作成するモジュール配置変更処理手順と、前記モ
ジュール配置変更処理手順を繰り返し実行して所定のモ
ジュール配置結果に収束させる収束処理手順とを備えた
モジュール配置方法を提供する。

【００１３】

【００１４】本発明によれば、ハードマクロとソフトモ
ジュールとが混在する大規模システムに対しても、全て
のモジュールを一括して最適に配置できるばかりか、各
モジュール内部の論理設計の進行度合いにとらわれるこ
となくモジュール配置を実行することができる。従っ
て、論理設計の回路最適化のために、配線ＲＣディレイ
を含めた正確なレイアウト後の性能予測値を得ることが
できる。しかも、作成したモジュール配置結果を後段の
配置処理に対して制約として与えるので、モジュール配
置時の結果を確実に配置配線処理に反映させることもで
きる。

【００１５】

【発明の実施の形態】図１に、本発明に係るモジュール
配置方法の全体の処理のフローチャートを示す。図１に
おいて、ステップＰ１は、ネットリストとモジュールや
セルのライブラリ情報を読み込む入力処理である（デー
タ入力）。ステップＰ２は、入力されたネットに関する
情報の論理階層構造や設計者の指示に従って、ネットを
複数のサブグループ、即ち、モジュールに分割するモジ
ュール分割処理（データ構造作成処理）である。本発明
の実施の形態では、ステップＰ２において作成したモジ
ュールを単位として、データ構造を作成し、配置処理を
行う。ステップＰ３は、上記ステップＰ２で作成したモ
ジュールを初期的にチップ上に並べて、それをＸＹ隣接
関係グラフで表現するモジュール初期配置処理（ＸＹ隣
接関係グラフ作成処理）である。ステップＰ４は、ステ
ップＰ３で初期的に作成したモジュール配置を変更する
モジュール配置変更処理（ＸＹ隣接関係グラフ更新処
理）である。ステップＰ５は、ステップＰ４で新たに作
成したモジュール配置結果を評価する処理であり、チッ
プを全体的又は部分的に評価する。ステップＰ６は、変
更前の配置よりもよい結果が得られたときに、その配置
結果を保存する処理である。ステップＰ７は、ステップ
Ｐ４からステップＰ７までを繰り返して行なったとき
に、モジュール配置改善処理が収束したかどうかを判定
する処理である。ステップＰ８は、最終的に得られた結
果を後段のレイアウト設計に反映させるためにレイアウ
トの制約情報を作成するレイアウト制約情報生成処理で
ある。ステップＰ８において作成される制約情報は、各
モジュールに含まれるセルの位置、向き、配置してよい
チップ上の範囲などである。

【００１６】以下に、図１に示した本発明の処理に従っ
て、主要なプロセスの内容を詳細に説明する。まず、図
１のステップＰ１で扱う入力ネット情報の形としては、
ＡＮＤ、ＯＲ、インバータ、フリップフロップ等のゲー
トを用いた記述であるゲートレベル記述だけでなく、レ
ジスタトランスファレベル（以下、ＲＴＬという。）記
述であってもよい。ＲＴＬ記述とは、回路内部の接続関
係に触れずに、特に入力条件、レジスタ間のデータ転送
及び演算等の基本動作により全体の動作を表現した記述
である。すなわち、全てのモジュールがゲートに展開さ
れている必要はなく、ＲＴＬのみであっても、ＲＴＬと
ゲートレベルとの混在又は全てがゲートレベル等であっ
てもよい。本発明では、如何なるフェーズで設計された
ネットリストであっても処理対象として扱うことができ
る。

【００１７】たとえば、図１ステップＰ１において、Ｒ
ＴＬのモジュールが入力ネットに存在している場合に
は、モジュールのゲート数を経験的あるいは簡易的にゲ
ート割り当てを行なうことで必要なゲート数を算出し、
このゲート数から当該モジュールのサイズを算定する。
このモジュールの形状は、自由形状としてもよいし、上
記で算出した面積に基づき幅高さをあらかじめ固定とし
て、モジュール配置処理を行なってもよい。モジュール
配置では、自由形状であればソフトモジュールとして扱
い、また、モジュールの形状を固定した場合にはハード
モジュールとして扱う。

【００１８】次に、図１のステップＰ２のモジュール初
期配置処理に関して説明する。図２は、モジュール分割
処理（データ構造作成処理）（ステップＰ２）において
ネットを分割して作成したモジュールの説明図である。
図２に示した例は、ＡＮＤ、ＯＲ、インバータ等の一般
セル又はランダムセルからなるネットのサブグループを
ソフトモジュールＳ１，Ｓ２，Ｓ３とし、一方、ＲＯ
Ｍ、ＲＡＭ等のハードマクロセルからなるネットのサブ
グループをハードモジュールＨ１，Ｈ２として定義した
ものである。なお、一般セルは、例えば、縦及び横の長
さについてのアスペクト比が自由に設計できるのに対し
て、ハードモジュールはある程度固定される。また、ハ
ードマクロセルと一般セル又はランダムセルを混在させ
たモジュールをソフトモジュールとして定義することが
できる。この場合、混在させたモジュールをソフトモジ
ュールとし、一方、ハードマクロセルのみから構成され
るモジュールをハードモジュールとして定義することが
できる。この他、モジュールの構成の仕方は自由であ
り、適宜定義することができる。

【００１９】このようにして作成したモジュールを高速
に配置するために、次のようなデータ構造が用いられ
る。

【００２０】生成したモジュール間にＸＹそれぞれの方
向に関する隣接関係グラフを構築する。さらに、モジュ
ール内部を必要に応じて複数のサブモジュール単位に分
割し、これらサブモジュール間についても類似の構造を
持ったＸＹ隣接関係グラフを作成する。すなわち、任意
のモジュールは、その部分集合である下位のモジュール
から構成されるような階層構造を持たせ、それぞれの階
層内でモジュール間のＸＹ隣接関係をグラフ表現してお
く。このように、本発明では、モジュール内の全ての要
素の位置関係を表現するために、同じ構造を持った隣接
関係グラフを多重構造で表現する手法をとる。

【００２１】ここで、任意の階層のＸＹ隣接関係グラフ
上のあるモジュールのサブモジュールに関するＸＹ隣接
関係グラフを、当該隣接関係グラフの下位のＸＹ隣接関
係グラフと呼ぶ。反対に、任意のＸＹ隣接関係グラフが
属する上位のモジュールに関するＸＹ隣接関係グラフ
は、当該隣接関係グラフの上位のＸＹ隣接関係グラフと
呼ぶ。本実施の形態で用いる任意の階層のＸＹ隣接関係
グラフから見て、１つ下の階層のＸＹ隣接関係グラフ
は、最大で当該階層のモジュール数分だけ存在する。ま
た、任意の階層のＸＹ隣接関係グラフは、必ず一つ上の
階層の唯一のモジュールに対応付けた構造となってい
る。

【００２２】こうした構成にすることで、上位としては
ＲＴＬに至る最も上位の設計階層から、下位としてはゲ
ートに至るモジュールまでを混在させて扱うことができ
る。このようにして、モジュール毎に設計の進み度合い
が違っていても、所定の階層のモジュールについて、論
理設計の進み度合いに応じたモジュール配置を行なうこ
とができる。論理設計が完了したモジュールに関して
は、ゲートレベルの正確な性能を見積もることができ、
また、途中まで論理設計が完了したモジュールに関して
は、その時点での論理設計情報を基にした可能な限り正
確な性能を見積もることができる。これらの情報を再び
論理設計にフィードバックすることで、より高品質な論
理設計を行なうことが可能となる。

【００２３】図３は、図２に示した分割後のモジュール
をチップ上に初期的に並べた配置図を示している。

【００２４】また、図４に、図３の配置状態を表現した
ＸＹ隣接関係グラフを示す。ＸＹ隣接関係グラフのノー
ドは、モジュールを表していて、２つのノードを結ぶエ
ッジは、モジュール間にＸＹ隣接関係が存在しているこ
とを意味している。２つのノードＳ１，Ｓ２に対してＸ
又はＹ方向の隣接関係グラフのエッジが張られていると
いうことは、モジュールＳ１，Ｓ２がＸ又はＹ方向の隣
接して置かれている状況を表現している。反対に、エッ
ジが張られていないノード間については、隣接関係が無
いことを表している。

【００２５】図４（ａ）に示されるように、第１階層Ｘ
方向隣接関係グラフに描かれているノードＰＬはチップ
の左辺を表し、ノードＰＲはチップの右辺を表す。ま
た、ノードＰＴは、チップの上辺を、また、ノードＰＲ
はチップの右辺をそれぞれ表す。また、ノードＰＬ及び
ＰＴは、ＸＹ隣接関係グラフの始点を代表するために設
けた仮想的なノードである。同様にして、ノードＰＲ及
びＰＢは、ＸＹ隣接関係グラフの終点を代表する仮想的
なノードである。各ノードには、モジュールの幅・高さ
に相当する値を重みとして持たせてある。従って、チッ
プの幅及び高さは、ＸＹ隣接関係グラフをそれぞれＰＬ
からＰＲ及びＰＴからＰＢに至る最長経路探索を行なう
ことで、その最長パス長から知ることができる。個々の
モジュールの座標は、ＸＹ隣接関係グラフのＸＹそれぞ
れの始点からの距離を求めれば、容易に知ることができ
る。

【００２６】例えば、図４（ａ）に示されるように、Ｘ
隣接関係グラフについて見ると、チップ左辺から右辺に
至るグラフ上のパスとしては、ノードＰＬ→モジュール
Ｈ１→Ｓ１→Ｓ２→ノードＰＲというパスと、ノードＰ
Ｌ→モジュールＨ２→Ｓ３→ノードＰＲという２つのパ
スがある。両者の何れか長い方がチップの幅に対応す
る。また、図４（ｂ）にＹ隣接関係グラフを示す。この
ように、チップを上辺から下辺に至るグラフ上のパスと
して、ノードＰＴ→モジュールＨ１→Ｈ２→ノードＰＢ
というパスと、ノードＰＴ→モジュールＳ１→Ｓ３→ノ
ードＰＢ、ノードＰＴ→モジュールＳ２→Ｓ３→ノード
ＰＢという３つのパスがある。

【００２７】図５に図４の下位階層について表現したＸ
Ｙ隣接グラフを示す。サブモジュール内のＸＹ隣接関係
グラフも図４と同様の構造である。図５（ａ）及び
（ｂ）に示した例では、ハードモジュールＨ１とＨ２に
対して、それぞれ下位のＸＹ隣接関係グラフを定義して
ある。サブモジュールのＸＹ隣接関係グラフのノードＰ
Ｌ′は、ハードモジュールＨ１又はＨ２の左辺を代表し
ており、ノードＰＲ′は右辺を表す。同様にノードＰ
Ｔ′及びＰＢ′は、それぞれ上辺及び下辺を表す。上位
モジュールの幅及び高さは、サブモジュールに関するＸ
Ｙ隣接関係グラフの始点ＰＬ′からＰＲ′及びＰＢ′か
らＰＴ′に至るそれぞれの最長パス長で定義される。

【００２８】図３に示されるように、ハードモジュール
Ｈ１中には、サブモジュールｈ１１〜ｈ１４が含まれ、
ＸＹ隣接関係グラフは、図５（ａ）のようになる。ハー
ドモジュールについても、同様に、ＸＹ隣接関係グラフ
は図５（ｂ）のようになる。

【００２９】つぎに、図３及び図４に示した例を用い
て、図１におけるステップＰ４に示した新たなモジュー
ル配置の作成方法に関して説明する。

【００３０】図６に、新たなモジュール配置の作成につ
いての説明図を示す。この実施の形態では、前述のＸＹ
隣接関係グラフの構造で表現したモジュールの配置結果
を、モジュール間に張られたエッジを張り変えることで
実現する。例えば、図６（ａ）に示すようにグラフのエ
ッジを張り替えることで、モジュールＳ１とＳ２の位置
関係を交換して付け替えを行なう。グラフのエッジの付
け替えを行なう際には、グラフにサイクルを発生させな
いことを制約とする。同様に、サブグループに関する配
置の変更は、サブグループ間に張られたエッジの付け替
えを行なうことで実現する。

【００３１】エッジの張り替えは、例えば、動作速度、
配線難易度、混雑度、ユーティリティ、充填率、マクロ
の位置等を考慮して、適当なモジュール配置結果となる
ように行われる。様々なモジュール配置結果についてシ
ミュレーションを実行することにより、張り替えられた
モジュールの配置結果を解析し、適当であるか否か判断
する。

【００３２】このようにして得られた新しいモジュール
配置結果に対するチップサイズは、まず、最も下位のＸ
Ｙ隣接関係グラフから順にＸＹ最長パス長を求めて上位
モジュールの幅と高さを計算し直し、順次、上位にＸＹ
隣接関係グラフの最長パス長を求め直すことで再計算す
る。このとき、任意の階層のサブモジュール位置は、上
位にＸＹ隣接関係グラフの対応するモジュールの座標か
らのオフセットとして求められるので、最上位のＸＹ隣
接関係グラフについての最長パス長計算が完了すれば、
全てのモジュールの座標が確定する。

【００３３】全てのモジュール及びセルの新しい位置を
確定できれば、モジュールの配置位置からモジュール内
のセルが持つ端子の座標を知ることができる。この端子
座標を使って、配線経路予想を行なえば、クリティカル
パスのディレイを正確に予測することができ、新しい配
置結果の評価ができる。

【００３４】この例では、図６（ｂ）に示されるよう
に、モジュールＳ１とＳ２が入れ替わった新たなモジュ
ール配置が作成された。

【００３５】上述の一連の処理、すなわち、全て又は一
部のＸＹ隣接関係グラフの変更による新しい配置結果の
作成とその評価を必要なだけ繰り返し行ない、最も優れ
た配置結果を保存しておくことで、最適な配置プランが
得られる。

【００３６】次に、本発明をコンピュータ上に実現し、
大規模ＬＳＩのモジュール配置に適用した結果を示す。
まず、図７は、従来技術における力学的手法を実データ
に適用した場合のモジュール配置図の一例を示す。図中
枠で示した部分はハードモジュール、また、メッシュの
部分はソフトモジュールをそれぞれ示す。力学的手法と
は、モジュール間の接続本数から引力を定義し、モジュ
ール間の重なりから斥力を定義して、両者の力学的なバ
ランスを求めることでモジュール配置を実現するもので
ある。図７が示すように、モジュール間の重なりを完全
には除去できないばかりか、同一階層のハードマクロセ
ルを規則的に配置することはできない。従って、従来の
モジュール配置結果からレイアウト結果を予測したり、
あるいは、この結果を配置配線等の後段のレイアウトフ
ローにつなげようとした場合、人手を介して最終的なモ
ジュール配置プランを決めなければならない。

【００３７】図８に、本発明に係るモジュール配置方法
を実データに適用した場合のモジュール配置図の一例を
示す。本発明を適用した結果では、図８に示すように、
モジュール間の重なりが生じることはなく、しかも、ハ
ードマクロセルを規則的に配置することができ、従来よ
りも高品質なモジュール配置結果が得られる。また、ハ
ードモジュール中にはサブモジュールが規則的に配置さ
れている。従って、モジュール配置に人手を介入させる
必要な少く、この結果から直接レイアウト後の性能を高
い精度で見積もることが可能である。

【００３８】

【発明の効果】以上のように、本発明によれば、ＲＯ
Ｍ、ＲＡＭ、マイクロプロセッサ、ＦＰＵなどの多数の
ハードマクロセルを含んだ大規模システムＬＳＩであっ
ても、人手を介することなく、高品質なモジュール配置
を実現することができる。また、本発明によると全ての
モジュールの論理設計が完了する前の段階から、モジュ
ール配置を実行することができるので、論理設計でレイ
アウト後の正確な性能予測値を知ることができ、より高
品質な論理設計が可能となる。さらに、本発明は、論理
設計とレイアウト設計との設計の繰り返しを少なくし、
設計期間の指数関数的な増加及び設計コストの増大を避
けるために非常に有効である。

【図面の簡単な説明】

【図１】本発明に係るモジュール配置方法の全体の処理
手順のフローチャート。

【図２】モジュール分割処理（データ構造作成処理）
（ステップＰ２）においてネットを分割して作成したモ
ジュールの説明図。

【図３】分割後のモジュールをチップ上に初期的に並べ
た配置図。

【図４】図３の配置状態を表現したＸＹ隣接関係グラ
フ。

【図５】図４に下位階層について表現したＸＹ隣接グラ
フ。

【図６】新たなモジュール配置の作成についての説明
図。

【図７】従来技術における力学的手法を実データに適用
した場合のモジュール配置図。

【図８】本発明に係るモジュール配置方法を実データに
適用した場合のモジュール配置図。

【符号の説明】

Ｈ１，Ｈ２ ハードモジュール Ｓ１，Ｓ２，Ｓ３ ソフトモジュール Ｐ２ モジュール分割 Ｐ３ モジュール初期配置 Ｐ４ モジュール配置変更 Ｐ８ レイアウト制約情報生成

───────────────────────────────────────────────────── フロントページの続き (58)調査した分野(Int.Cl.⁷，ＤＢ名) H01L 21/82 G06F 17/50 H01L 27/04

Claims (8)

(57)【特許請求の範囲】
1. 【請求項１】モジュール配置の対象となる回路を複数の
   モジュールに分割することにより論理階層の第０階層の
   モジュールとして定義し、前記回路の論理階層構造に基
   づいて前記第０階層より下位の第１階層からなる複数の
   要素に分割して第１階層のモジュールとして定義し、さ
   らに必要に応じて前記第１階層の一部又は全てのモジュ
   ールを前記第１階層より下位の第２階層からなる複数の
   要素に各々分割してそれぞれ第２階層モジュールとして
   定義し、上記分割を前記第０階層の各モジュール毎に必
   要に応じてＮ回繰り返して第Ｎ階層のモジュールとして
   定義するモジュール分割処理手順と、 前記モジュールをノードとして定義し、各階層における
   各モジュール間のＸ方向及びＹ方向の隣接関係を前記ノ
   ード間を接続するエッジによりＸ方向隣接関係グラフお
   よびＹ方向隣接関係グラフとしてそれぞれ表現し、第ｎ
   階層（ｎは、０〜（Ｎ−１）の整数）のＸ方向隣接関係
   グラフおよびＹ方向隣接関係グラフにおける各ノードが
   第（ｎ＋１）階層のＸ方向隣接関係グラフおよびＹ方向
   隣接関係グラフにそれぞれ対応付けられた多重構造のＸ
   Ｙ隣接関係グラフを作成して、前記回路の全ての要素の
   モジュール配置を作成するモジュール配置処理手順と、 前記ＸＹ隣接関係グラフの一部又は全てを変更すること
   で新たなモジュール配置を作成するモジュール配置変更
   処理手順とを備えたモジュール配置方法。
2. 【請求項２】ネットに関する情報を読み込む入力処理手
   順と、 前記入力処理手順により入力された前記情報の論理階層
   構造又は設計者の指示に従って、モジュール配置の対象
   となる回路を複数のモジュールに分割することにより論
   理階層の第０階層のモジュールとして定義し、前記回路
   の論理階層構造に基づいて前記第０階層より下位の第１
   階層からなる複数の要素に分割して第１階層のモジュー
   ルとして定義し、さらに必要に応じて前記第１階層の一
   部又は全てのモジュールを前記第１階層より下位の第２
   階層からなる複数の要素に各々分割してそれぞれ第２階
   層モジュールとして定義し、上記分割を前記第０階層の
   各モジュール毎に必要に応じてＮ回繰り返して第Ｎ階層
   のモジュールとして定義することにより、前記回路を複
   数のモジュールに分割するモジュール分割処理手順と、 前記モジュールをノードとして定義し、各階層における
   各モジュール間のＸ方向及びＹ方向の隣接関係を前記ノ
   ード間を接続するエッジによりＸ方向隣接関係グラフお
   よびＹ方向隣接関係グラフとしてそれぞれ表現し、第ｎ
   階層（ｎは、０〜（Ｎ−１）の整数）のＸ方向隣接関係
   グラフおよびＹ方向隣接関係グラフにおける各ノードが
   第（ｎ＋１）階層のＸ方向隣接関係グラフおよびＹ方向
   隣接関係グラフにそれぞれ対応付けられた多重構造のＸ
   Ｙ隣接関係グラフを作成して、前記回路の全ての要素の
   モジュール配置を作成することにより、前記モジュール
   分割処理手順により作成したモジュールを初期的にチッ
   プ上に並べてＸＹ隣接関係グラフを作成するモジュール
   配置処理手順と、 前記モジュール配置処理手順により初期的に作成したモ
   ジュール初期配置を前記ＸＹ隣接関係グラフの一部又は
   全てを変更することで新たなモジュール配置を作成する
   モジュール配置変更処理手順と、 前記モジュール配置変更処理手順を繰り返し実行して所
   定のモジュール配置結果に収束させる収束処理手順とを
   備えたモジュール配置方法。
3. 【請求項３】前記収束処理手順により最終的に得られた
   前記所定のモジュール配置結果に基づき各モジュールに
   含まれるセルの位置、向き、又は、配置してよいチップ
   上の範囲等のレイアウト制約情報を生成する制約情報生
   成処理手順をさらに備えたことを特徴とする請求項２に
   記載のモジュール配置方法。
4. 【請求項４】前記ノードにはモジュールの幅又は高さを
   重みとして付加しておき、 前記Ｘ方向又はＹ方向の隣接関係グラフにおいて、それ
   ぞれＸ方向又はＹ方向の最長パスの重みの総和を、前記
   ＸＹ隣接関係グラフが属する上位階層のモジュールに対
   応する前記Ｘ方向又はＹ方向隣接関係グラフのノードの
   重みとすることを特徴とする請求項１乃至３のいずれか
   に記載のモジュール配置方法。
5. 【請求項５】前記モジュール配置変更処理手順におい
   て、 任意の階層のＸ方向又はＹ方向の隣接関係グラフのエッ
   ジの付け替え又は発生又は消去を行うことにより、前記
   ＸＹ隣接関係グラフ上に定義したモジュール配置位置を
   変更することを特徴とする請求項１乃至４のいずれかに
   記載のモジュール配置方法。
6. 【請求項６】前記モジュール配置変更処理手順におい
   て、 前記ＸＹ隣接関係グラフのエッジの付け替え又は発生又
   は消去を行った後に、 前記隣接関係グラフのＸ方向又はＹ方向の最長パスの重
   みの総和を再計算し、 前記ＸＹ隣接関係グラフが属する前記上位階層モジュー
   ルのＸＹ隣接関係グラフ上の対応するノードの重みを更
   新し、 さらに、前記ノードの重みを更新した全てのＸＹ隣接関
   係グラフ及び前記変更が影響する全てのＸＹ隣接関係グ
   ラフについてノードの重みを更新することを特徴とする
   請求項１乃至５のいずれかに記載のモジュール配置方
   法。
7. 【請求項７】前記モジュール配置処理手順を実行した
   後、 前記新たなモジュール配置の結果を、モジュール毎の配
   置位置及び幅高さの情報に基づいて、前記回路上におけ
   るセル又はセルグループ単位の配置位置又は配置領域情
   報を作成して配置処理手順に対する制約とする制約情報
   生成処理手順をさらに備えたことを特徴とする請求項１
   乃至６のいずれかに記載のモジュール配置方法。
8. 【請求項８】前記モジュール配置処理手順は、 ゲートレベル記述及び／又はレジスタトランスファレベ
   ル記述を用いて、ソフトモジュール及び／又はハードモ
   ジュールにより配置することを特徴とする請求項１乃至
   ７のいずれかに記載のモジュール配置方法。