JPH0476777A - セル自動配置方法 - Google Patents
セル自動配置方法Info
- Publication number
- JPH0476777A JPH0476777A JP2189461A JP18946190A JPH0476777A JP H0476777 A JPH0476777 A JP H0476777A JP 2189461 A JP2189461 A JP 2189461A JP 18946190 A JP18946190 A JP 18946190A JP H0476777 A JPH0476777 A JP H0476777A
- Authority
- JP
- Japan
- Prior art keywords
- cell
- cells
- area
- areas
- grating
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
［発明の目的コ
（産業上の利用分野）
この発明は、半導体基板上にセルを自動的に配置するセ
ル自動配置方法に関する。
ル自動配置方法に関する。
（従来の技術）
半導体集積回路は、論理機能や記憶機能を有するセルを
チップ内に配置し、各回路の入出力端子間を配線するこ
とにより、所望の回路動作を得るものである。
チップ内に配置し、各回路の入出力端子間を配線するこ
とにより、所望の回路動作を得るものである。
第２図は、−船釣なゲートアレイ方式による半導体集積
回路チップの平面図である。チップ上は、セルの配置さ
れた領域２１、セル間の配線専用の領域２２、および周
辺に設けられた人出カ用回路の配置される領域２３によ
り構成されている。
回路チップの平面図である。チップ上は、セルの配置さ
れた領域２１、セル間の配線専用の領域２２、および周
辺に設けられた人出カ用回路の配置される領域２３によ
り構成されている。
このような半導体集積回路において、計算機を用いた自
動配置処理によりセルの配置処理を行う際には、通常、
仮想配線長を最小化し、配線混雑度を均一化するように
行う。
動配置処理によりセルの配置処理を行う際には、通常、
仮想配線長を最小化し、配線混雑度を均一化するように
行う。
従来の自動配置処理方法は、まず、チップ上を複数の格
子領域に分割する。１つの格子領域に配置されているあ
る１つのセルを選択して他の格子領域に移動する、ある
いは２つの格子領域から１つづつセルを選択して配置位
置を交換する。このような処理を繰り返すことにより、
配置状態を改良している。
子領域に分割する。１つの格子領域に配置されているあ
る１つのセルを選択して他の格子領域に移動する、ある
いは２つの格子領域から１つづつセルを選択して配置位
置を交換する。このような処理を繰り返すことにより、
配置状態を改良している。
セルの移動あるいは交換を行う方法として、各セルの形
状や大きさのばらつきにより生じる、セル同志の重なり
あるいはセル面積の総和が格子領域内のセル配置可能面
積よりも大きくなることを、−時的に許して改良を進め
る方法がある。また、移動あるいは交換してもセル同志
の重なりが生しないセルに限定して改良を進める方法も
ある。
状や大きさのばらつきにより生じる、セル同志の重なり
あるいはセル面積の総和が格子領域内のセル配置可能面
積よりも大きくなることを、−時的に許して改良を進め
る方法がある。また、移動あるいは交換してもセル同志
の重なりが生しないセルに限定して改良を進める方法も
ある。
重なりか生しないセルに限定する方法は、移動あるいは
交換対象となるセルが限定されるため、配置改良の自由
度が限定されて改良が進みにくい。
交換対象となるセルが限定されるため、配置改良の自由
度が限定されて改良が進みにくい。
このため、重なりを一時的に許して改良を進める方法が
用いられることが多い。
用いられることが多い。
重なりを一時的に許した方法によって収束した改良結果
の一例を、第３図（Ａ）に示す。
の一例を、第３図（Ａ）に示す。
１〜７の番号が付されたＱ印はセル１〜７であり、実線
は各セル間の配線要求を示すものとする。
は各セル間の配線要求を示すものとする。
また、チップ上は格子領域１１〜１９に分割されており
、各格子領域には最終的に１つのセルだけしか割り当て
ることができないものとする。
、各格子領域には最終的に１つのセルだけしか割り当て
ることができないものとする。
格子領域１８に２つのセル５，７が割り当てられたまま
改良が収束している。このため、どちらか一方のセルを
空の格子領域１１〜１３へ移動させる後処理が必要とな
る。後処理の結果、例えば、第３図（Ｂ）のようなセル
配置結果になってしまつ０ 本来、第４図のようなセル配置が最適であり、配置方法
によっては同図のような配置か可能なはずである。
改良が収束している。このため、どちらか一方のセルを
空の格子領域１１〜１３へ移動させる後処理が必要とな
る。後処理の結果、例えば、第３図（Ｂ）のようなセル
配置結果になってしまつ０ 本来、第４図のようなセル配置が最適であり、配置方法
によっては同図のような配置か可能なはずである。
しかしながら、後処理によってセルの重なりを除去する
観点からセルの移動、交換を行なう場合は、第３図（Ａ
）における重なりの生じていないセル１〜４，６の移動
も含めた大局的な配置状態の変更が難しい。このため、
第４図のような最適なセル配置結果を得難く、最終的に
は第３図（Ｂ）のようなセル配置結果になり、改良段階
では予想しなかった格子領域１２から格子領域１８への
配線要求が発生してしまう。
観点からセルの移動、交換を行なう場合は、第３図（Ａ
）における重なりの生じていないセル１〜４，６の移動
も含めた大局的な配置状態の変更が難しい。このため、
第４図のような最適なセル配置結果を得難く、最終的に
は第３図（Ｂ）のようなセル配置結果になり、改良段階
では予想しなかった格子領域１２から格子領域１８への
配線要求が発生してしまう。
（発明が解決しようとする課題）
以上のように、重なりが生じないセルに限定して改良を
進める方法では、配置改良の自由度が限定され、改良が
進みにくいという欠点があった。
進める方法では、配置改良の自由度が限定され、改良が
進みにくいという欠点があった。
また、セルの重なりを許した方法では、局所的に過剰に
セルが割り当てられてしまう不均衡を最終段階で除去す
る後処理が必要であり、この後処理の結果、困難な配線
要求が発生するという問題があった。
セルが割り当てられてしまう不均衡を最終段階で除去す
る後処理が必要であり、この後処理の結果、困難な配線
要求が発生するという問題があった。
そこでこの発明は、このような問題点を解決するために
なされたものであり、その目的とするところは、セルか
局所的に過剰に割り当てられること無く、全ての格子領
域に均等に配置されることにより、最適な配線状態にで
きるセル自動配置方法を提供することにある。
なされたものであり、その目的とするところは、セルか
局所的に過剰に割り当てられること無く、全ての格子領
域に均等に配置されることにより、最適な配線状態にで
きるセル自動配置方法を提供することにある。
［発明の構成］
（課題を解決するための手段）
上記目的を達成するため、この発明は、半導体基板上の
セル配置可能領域を複数の格子領域に分割し、この格子
領域に配置されているセルを格子領域間で移動あるいは
交換を繰り返してセルの配置改良を行なう際に、前記格
子領域内のセル配置可能面積に対する格子領域に配置さ
れるセル面積の総和の比が、前記格子領域間で均一化す
るようにセルの移動あるいは交換を行うように構成され
ている。
セル配置可能領域を複数の格子領域に分割し、この格子
領域に配置されているセルを格子領域間で移動あるいは
交換を繰り返してセルの配置改良を行なう際に、前記格
子領域内のセル配置可能面積に対する格子領域に配置さ
れるセル面積の総和の比が、前記格子領域間で均一化す
るようにセルの移動あるいは交換を行うように構成され
ている。
（作用）
上記構成によって、この発明は、半導体基板上のセル配
置可能領域を複数の格子領域に分割する。セル配置可能
領域に初期配置された複数のセルから１つをランダムに
選択する。選択したセルを、このセルが所属する移動元
格子領域から移動すべき移動先格子領域へ移動させる。
置可能領域を複数の格子領域に分割する。セル配置可能
領域に初期配置された複数のセルから１つをランダムに
選択する。選択したセルを、このセルが所属する移動元
格子領域から移動すべき移動先格子領域へ移動させる。
この後、移動元格子領域に配置されているセルの充填率
と、移動先格子領域のセル充填率とを求める。
と、移動先格子領域のセル充填率とを求める。
移動元格子領域のセル充填率の方が大きい場合は、他の
セルをランダムに選択し、同様な処理を繰り返す。移動
先格子領域のセル充填率の方が大きい場合は、移動元格
子領域のセル充填率との差の半分に相当する面積のセル
集合を、移動先格子領域に配置されているセルの中から
選出する。そして、選出したセル集合を移動元格子領域
へ移動させる。このように、１：Ｎ（Ｎ≧Ｏ）のセル数
比でセル集合を交換させることにより、移動元および移
動先格子領域のセル充填率を均一化するようにしている
。
セルをランダムに選択し、同様な処理を繰り返す。移動
先格子領域のセル充填率の方が大きい場合は、移動元格
子領域のセル充填率との差の半分に相当する面積のセル
集合を、移動先格子領域に配置されているセルの中から
選出する。そして、選出したセル集合を移動元格子領域
へ移動させる。このように、１：Ｎ（Ｎ≧Ｏ）のセル数
比でセル集合を交換させることにより、移動元および移
動先格子領域のセル充填率を均一化するようにしている
。
（実施例）
以下、図面を参照してこの発明の詳細な説明する。
第１−図は、この発明のセル自動配置方法の処理手順を
示すフローチャートである。
示すフローチャートである。
先ず、半導体基板上のセル配置可能領域を複数の格子領
域に分割し、セルの初期配置を行（１配置状態を決定す
る（ステ・ツブＳｌ）。
域に分割し、セルの初期配置を行（１配置状態を決定す
る（ステ・ツブＳｌ）。
次に、決定された配置状態を登録する（ステ・ツブＳ２
）。
）。
この配置状態が満足すべき改良状態に収束したか否かを
判定する（ステ・ツブＳ３）。この結果、満足条件に収
束したと判定した場合は処理を終了し、満足条件に収束
しない場合は改良処理を続行し次のステップへ進む。
判定する（ステ・ツブＳ３）。この結果、満足条件に収
束したと判定した場合は処理を終了し、満足条件に収束
しない場合は改良処理を続行し次のステップへ進む。
配置されている複数のセルの中から、１つのセルをラン
ダムに選択する（ステ・ンプＳ４）。
ダムに選択する（ステ・ンプＳ４）。
選択された１つのセルが所属している所属格子領域（移
動元格子領域）Ｇｌを計算によって求める（ステップＳ
５）。
動元格子領域）Ｇｌを計算によって求める（ステップＳ
５）。
さらに、配置状態が改良される様にこのセルの移動すべ
き移動先格子領域Ｇ２を計算によって求める（ステップ
Ｓ６）。
き移動先格子領域Ｇ２を計算によって求める（ステップ
Ｓ６）。
求められた移動先格子領域Ｇ２へ、このセルを移動する
（ステップＳ７）。
（ステップＳ７）。
移動後、移動元格子領域Ｇ１と移動先格子領域Ｇ２のセ
ル配置可能面積に対する、配置されているセル群のセル
充填率ＤＩ、Ｄ２をそれぞれ副筒する（ステップＳ８、
Ｓ９）。
ル配置可能面積に対する、配置されているセル群のセル
充填率ＤＩ、Ｄ２をそれぞれ副筒する（ステップＳ８、
Ｓ９）。
次に、これらのセル充填率ＤＩ、Ｄ２の差に相当するセ
ル面積総和Ｓを計算する（ステップ５１０）。
ル面積総和Ｓを計算する（ステップ５１０）。
この面積総和Ｓの符号が正でない場合は、ステップＳ２
へ戻り、同様に改良処理を繰り返す（ステップＳ１１肯
定）。すなわち、この場合は、セル充填率Ｄ１とＤ２と
の差が、セル移動前に比べて小さくなったため、セル充
填率が均一化されたと判断する。
へ戻り、同様に改良処理を繰り返す（ステップＳ１１肯
定）。すなわち、この場合は、セル充填率Ｄ１とＤ２と
の差が、セル移動前に比べて小さくなったため、セル充
填率が均一化されたと判断する。
一方、面積総和Ｓの符号が正の場合は、面積総和Ｓの半
分に相当する面積に最も近くなるセル集合Ｃを、移動先
格子領域Ｇ２に配置されて０る複数のセルの中から作成
する（ステ・ツブＳｌｌ否定、ステップ１２）。このセ
ル集合Ｃを作成する際１こは、移動元格子領域Ｇ１へ移
動させること番こより、改良効果の高くなるセルから順
に選出してグルプ化する。改良効果の高くなるセルを選
出する番こは、セルを移動させるべき最良の格子領域を
求める関数（目的関数）を用いて選出する。
分に相当する面積に最も近くなるセル集合Ｃを、移動先
格子領域Ｇ２に配置されて０る複数のセルの中から作成
する（ステ・ツブＳｌｌ否定、ステップ１２）。このセ
ル集合Ｃを作成する際１こは、移動元格子領域Ｇ１へ移
動させること番こより、改良効果の高くなるセルから順
に選出してグルプ化する。改良効果の高くなるセルを選
出する番こは、セルを移動させるべき最良の格子領域を
求める関数（目的関数）を用いて選出する。
セル集合Ｃが作成されると、これを移動元格子領域Ｇ１
へ移動する（ステップ８１３）。
へ移動する（ステップ８１３）。
すなわち、面積総和Ｓの符号が正の場合は、移動元格子
領域Ｇ１内の１つのセルを移動先格子領域Ｇ２へ移動さ
せたことにより、セル充填率Ｄ２とＤｌとの差が移動前
に比べて大きくなったと考えられる。このため、大きく
なった充填率の半分に相当する面積となる複数のセルを
、移動先格子領域Ｇ２から移動元格子領域Ｇ１へ戻して
０る。
領域Ｇ１内の１つのセルを移動先格子領域Ｇ２へ移動さ
せたことにより、セル充填率Ｄ２とＤｌとの差が移動前
に比べて大きくなったと考えられる。このため、大きく
なった充填率の半分に相当する面積となる複数のセルを
、移動先格子領域Ｇ２から移動元格子領域Ｇ１へ戻して
０る。
これにより、セル充填率が均一化される。
セル集合Ｃを移動元格子領域Ｇ１へ移動した後、改良判
定を行なう（ステップ５１４）。
定を行なう（ステップ５１４）。
この結果、改良された場合には、ステップＳ２へ戻り同
様に改良処理を続ける（ステップＳ１４肯定）。改悪さ
れた場合は、ランダムに選択された１つのセルおよびセ
ル集合Ｃを移動したことによって得られた新装置状態を
捨て１、ステップＳ３へ戻り新たに同様な改良処理を続
ける（ステップＳ１４否定）。
様に改良処理を続ける（ステップＳ１４肯定）。改悪さ
れた場合は、ランダムに選択された１つのセルおよびセ
ル集合Ｃを移動したことによって得られた新装置状態を
捨て１、ステップＳ３へ戻り新たに同様な改良処理を続
ける（ステップＳ１４否定）。
このような処理を、何度も繰り返すことにより、全ての
格子領域のセル充填率を均一化する。
格子領域のセル充填率を均一化する。
このように、この発明によれば、分割された格子領域の
セル配置可能面積に対する、セル面積の総和の比が均一
化するように、ｌ：Ｎ（Ｎ２２）のセル数比でセルの移
動あるいは交換を行っている。このため、局所的に過剰
なセルを割り当てることがなく、改良時点の配置状態を
最終的な配置状態に反映させることが可能となる。また
、移動あるいは交換対象となるセルの形状に制約がない
ため、改良が進みやすい。
セル配置可能面積に対する、セル面積の総和の比が均一
化するように、ｌ：Ｎ（Ｎ２２）のセル数比でセルの移
動あるいは交換を行っている。このため、局所的に過剰
なセルを割り当てることがなく、改良時点の配置状態を
最終的な配置状態に反映させることが可能となる。また
、移動あるいは交換対象となるセルの形状に制約がない
ため、改良が進みやすい。
［発明の効果］
以上述べた様に、この発明のセル自動配置方法では、１
つのセルを移動すべき格子領域へ移動した後、セル充填
率か均一化されるようにセル集合を移動元領域へ戻すよ
うにした。これにより、セルが局所的に過剰に割り当て
られることが無くなり、全ての格子領域に均等に配置す
ることが可能となる。また、この結果、最適な配置状態
にすることができる。
つのセルを移動すべき格子領域へ移動した後、セル充填
率か均一化されるようにセル集合を移動元領域へ戻すよ
うにした。これにより、セルが局所的に過剰に割り当て
られることが無くなり、全ての格子領域に均等に配置す
ることが可能となる。また、この結果、最適な配置状態
にすることができる。
第１図はこの発明のセル自動配置方法の処理手順を示す
フローチャート、第２図は従来の一般的なゲートアレイ
方式による半導体集積回路チップの平面図、第３図は従
来のセル自動配置方法によるセル配置状態を示すセル配
置可能領域の平面図、第４図は最適なセル配置状態の一
例を示すセル配置可能領域の平面図である。 Ｇ１・・・移動元格子領域 Ｇ２・・・移動先格子領
域ＤＩ、Ｄ２・・・セル充填率 Ｓ・・・セル面積総和
Ｃ・・セル集合 １〜７・・セル１１〜１９
・・・格子領域
フローチャート、第２図は従来の一般的なゲートアレイ
方式による半導体集積回路チップの平面図、第３図は従
来のセル自動配置方法によるセル配置状態を示すセル配
置可能領域の平面図、第４図は最適なセル配置状態の一
例を示すセル配置可能領域の平面図である。 Ｇ１・・・移動元格子領域 Ｇ２・・・移動先格子領
域ＤＩ、Ｄ２・・・セル充填率 Ｓ・・・セル面積総和
Ｃ・・セル集合 １〜７・・セル１１〜１９
・・・格子領域
Claims (1)
- 【特許請求の範囲】 半導体基板上のセル配置可能領域を複数の格子領域に分
割し、この格子領域に配置されているセルを格子領域間
で移動あるいは交換を繰り返してセルの配置改良を行な
う際に、 前記格子領域内のセル配置可能面積に対する格子領域に
配置されるセル面積の総和の比が、前記格子領域間で均
一化するようにセルの移動あるいは交換を行うことを特
徴とするセル自動配置方法。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2189461A JP2937428B2 (ja) | 1990-07-19 | 1990-07-19 | セル自動配置方法 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2189461A JP2937428B2 (ja) | 1990-07-19 | 1990-07-19 | セル自動配置方法 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH0476777A true JPH0476777A (ja) | 1992-03-11 |
| JP2937428B2 JP2937428B2 (ja) | 1999-08-23 |
Family
ID=16241657
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2189461A Expired - Lifetime JP2937428B2 (ja) | 1990-07-19 | 1990-07-19 | セル自動配置方法 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP2937428B2 (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH06348782A (ja) * | 1993-06-14 | 1994-12-22 | Nec Corp | プリント基板設計システム用回路入力エディタ |
-
1990
- 1990-07-19 JP JP2189461A patent/JP2937428B2/ja not_active Expired - Lifetime
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH06348782A (ja) * | 1993-06-14 | 1994-12-22 | Nec Corp | プリント基板設計システム用回路入力エディタ |
Also Published As
| Publication number | Publication date |
|---|---|
| JP2937428B2 (ja) | 1999-08-23 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US4686629A (en) | Logic cell placement method in computer-aided-customization of universal arrays and resulting integrated circuit | |
| JP2831703B2 (ja) | 自動フロアプラン演算装置 | |
| US5898597A (en) | Integrated circuit floor plan optimization system | |
| US6230306B1 (en) | Method and apparatus for minimization of process defects while routing | |
| CA1275508C (en) | Hierarchical top-down method for physical vlsi-chip design | |
| US6175950B1 (en) | Method and apparatus for hierarchical global routing descend | |
| US6253363B1 (en) | Net routing using basis element decomposition | |
| JP3220250B2 (ja) | セル自動配置方法 | |
| CN113128152A (zh) | 基于时序的多裸片fpga的网表分割方法 | |
| US5796625A (en) | Physical design automation system and process for designing integrated circuit chip using simulated annealing with "chessboard and jiggle" optimization | |
| JPH0476777A (ja) | セル自動配置方法 | |
| US6269469B1 (en) | Method and apparatus for parallel routing locking mechanism | |
| JP2664465B2 (ja) | 半導体装置のセル配置方法 | |
| JP2000100951A (ja) | 半導体集積回路の設計方法及び設計装置 | |
| JP2734180B2 (ja) | 集積回路の設計方法 | |
| JP2965259B2 (ja) | 半導体集積回路の配置方法 | |
| JPH0443665A (ja) | 半導体装置及びその製造方法 | |
| JPS63260150A (ja) | 集積回路の配置設計方法 | |
| JPH0442571A (ja) | 半導体集積回路装置における集積回路素子の配置方法 | |
| JP2851079B2 (ja) | 半導体集積回路の製造方法 | |
| JP2604469B2 (ja) | 半導体集積回路装置及びその構成方法 | |
| JPH05304209A (ja) | 配線設計用ｃａｄ装置 | |
| JP3068492B2 (ja) | 自動配置配線方法 | |
| JPS6062136A (ja) | Ｌｓｉ設計のセル配置方法 | |
| JP2005136178A (ja) | 半導体集積回路の電源配線レイアウト方法、電源配線レイアウトプログラム、および電源配線レイアウト装置 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090611 Year of fee payment: 10 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090611 Year of fee payment: 10 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100611 Year of fee payment: 11 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100611 Year of fee payment: 11 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110611 Year of fee payment: 12 |
|
| EXPY | Cancellation because of completion of term | ||
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110611 Year of fee payment: 12 |