JPS61208845A - 階層的配置処理方式 - Google Patents
階層的配置処理方式Info
- Publication number
- JPS61208845A JPS61208845A JP60050920A JP5092085A JPS61208845A JP S61208845 A JPS61208845 A JP S61208845A JP 60050920 A JP60050920 A JP 60050920A JP 5092085 A JP5092085 A JP 5092085A JP S61208845 A JPS61208845 A JP S61208845A
- Authority
- JP
- Japan
- Prior art keywords
- group
- block
- blocks
- exchange
- disposing
- 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
Classifications
-
- H—ELECTRICITY
- H10—SEMICONDUCTOR DEVICES; ELECTRIC SOLID-STATE DEVICES NOT OTHERWISE PROVIDED FOR
- H10D—INORGANIC ELECTRIC SEMICONDUCTOR DEVICES
- H10D84/00—Integrated devices formed in or on semiconductor substrates that comprise only semiconducting layers, e.g. on Si wafers or on GaAs-on-Si wafers
- H10D84/01—Manufacture or treatment
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F30/00—Computer-aided design [CAD]
- G06F30/30—Circuit design
- G06F30/39—Circuit design at the physical level
- G06F30/392—Floor-planning or layout, e.g. partitioning or placement
Landscapes
- Engineering & Computer Science (AREA)
- Computer Hardware Design (AREA)
- Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Architecture (AREA)
- Evolutionary Computation (AREA)
- Geometry (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Structure Of Printed Boards (AREA)
- Semiconductor Integrated Circuits (AREA)
- Design And Manufacture Of Integrated Circuits (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
（技術分野）
本発明は、階層的配置処理方式に関し、特にＬＳＩ、プ
リント基板等の中に収容するブロックの階層的配置処理
方式に関するものである。
リント基板等の中に収容するブロックの階層的配置処理
方式に関するものである。
（従来技術）
従来、この種の配置処理方式は、交換対象ブロック選択
手段、交換結果良否判定手段、交換手段、配置情報記憶
手段および制御手段から構成されていた。この配置改良
処理はまず、交換対象ブロック選択手段により、交換対
象ブロックのうち任意の２個あるいはα個（α≧３）が
選択され、次に交換結果良否判定手段により、選択され
たペア間での交換結果が評価さｎ、さらに該交換が有効
であると判定された場合には交換手段により該ペア間が
交換され、その結果が配置情報記憶手段に格納されてい
た。以上かられかるように、交換対象ブロックのベアの
選択には非常に多くの組み合わせが存在するため、これ
らの配置改良処理では、より良い解を得るために、非常
に多数回のくり返し処理を行うことを余儀なくされてい
た。一般にそｎらの計算複雑度は、Ｑ（ｋｎ２） 以
上（ｋ：くり返し回数、ｎ：交換対象ブロック数）であ
ると言われている。
手段、交換結果良否判定手段、交換手段、配置情報記憶
手段および制御手段から構成されていた。この配置改良
処理はまず、交換対象ブロック選択手段により、交換対
象ブロックのうち任意の２個あるいはα個（α≧３）が
選択され、次に交換結果良否判定手段により、選択され
たペア間での交換結果が評価さｎ、さらに該交換が有効
であると判定された場合には交換手段により該ペア間が
交換され、その結果が配置情報記憶手段に格納されてい
た。以上かられかるように、交換対象ブロックのベアの
選択には非常に多くの組み合わせが存在するため、これ
らの配置改良処理では、より良い解を得るために、非常
に多数回のくり返し処理を行うことを余儀なくされてい
た。一般にそｎらの計算複雑度は、Ｑ（ｋｎ２） 以
上（ｋ：くり返し回数、ｎ：交換対象ブロック数）であ
ると言われている。
しかるに、近年の技術の急速な進歩によす、ｌＬＳＩあ
るいはプリント基板内に収容できるブロック数は飛躍的
に増大してきた。従って、交換対象ブロック数の増加に
つｎて、配置改良処理に要する処理時間も、また、指数
関数的に増大し、実時間内での処理が難しくなるという
欠点があった。
るいはプリント基板内に収容できるブロック数は飛躍的
に増大してきた。従って、交換対象ブロック数の増加に
つｎて、配置改良処理に要する処理時間も、また、指数
関数的に増大し、実時間内での処理が難しくなるという
欠点があった。
（発明の目的）
本発明の目的は、従来の配置改良処理方式における欠点
を除去すると共に入力ブロックのグループ化手段、グル
ープ領域決定手段及びグループ内に属するブロック情報
を格納する階層情報記憶手段、グループ領域記憶手段を
付加することにより、短い処理時間でより良い配置改良
結果を得る階層的配置処理方式を提供することにある。
を除去すると共に入力ブロックのグループ化手段、グル
ープ領域決定手段及びグループ内に属するブロック情報
を格納する階層情報記憶手段、グループ領域記憶手段を
付加することにより、短い処理時間でより良い配置改良
結果を得る階層的配置処理方式を提供することにある。
（発明の構成）
本発明によれば、ＬＳＩ、プリント基板の中に収容し、
かつ配置単位となるブロックを配置する配置処理方式に
おいて、全入力ブロックを指定のグループ数になるまで
分割するグループ化手段と、ＬＳ Ｉ、プリント基板等
の下地基板上でのグループの配置領域を決定するグルー
プ領域決定手段と、該グループ内に属するブロック情報
を格納する階層情報記憶手段と、各グループの配置領域
を格納するグループ領域記憶手段と、配置改良処理実行
時に同一グループ内のブロック交換対象として選択する
交換対象ブロック選択手段と、選択さｎたブロックの交
換の可否を判定する交換結果良否判定手段と、前記ブロ
ックの交換を行う交換手段とを含むことを特徴とする階
層的配置改良方式が得られる。
かつ配置単位となるブロックを配置する配置処理方式に
おいて、全入力ブロックを指定のグループ数になるまで
分割するグループ化手段と、ＬＳ Ｉ、プリント基板等
の下地基板上でのグループの配置領域を決定するグルー
プ領域決定手段と、該グループ内に属するブロック情報
を格納する階層情報記憶手段と、各グループの配置領域
を格納するグループ領域記憶手段と、配置改良処理実行
時に同一グループ内のブロック交換対象として選択する
交換対象ブロック選択手段と、選択さｎたブロックの交
換の可否を判定する交換結果良否判定手段と、前記ブロ
ックの交換を行う交換手段とを含むことを特徴とする階
層的配置改良方式が得られる。
（実施例）
次に、本発明について図面を参照して詳細に説明する。
図面は本発明の一実施例を示す。第１図において、本実
施例はＬＳＩ、プリント基板の中に収容し、かつ配置単
位となるブロックを配置する配置処理方式において、全
入力ブロックを指定のグループ数になるまで分割するグ
ループ化手段２と、ＬＳＩ、プリント基板等の下地基板
上でのグループの配置領域を決定するグループ領域決定
手段３と、該グループ内に属するブロック情報を格納す
る階層情報記憶手段１１と、各グループの配置領域を格
納するグループ領域記憶手段１２と、配置改良処理実行
時に同一グループ内のブロックを交換対象として選択す
る交換対象ブロック選択手段５と、選択さルたブロック
の交換の可否を判定する交換結果良否判定手段６と、前
記ブロックの交換を行う交換手段７とを含む。
施例はＬＳＩ、プリント基板の中に収容し、かつ配置単
位となるブロックを配置する配置処理方式において、全
入力ブロックを指定のグループ数になるまで分割するグ
ループ化手段２と、ＬＳＩ、プリント基板等の下地基板
上でのグループの配置領域を決定するグループ領域決定
手段３と、該グループ内に属するブロック情報を格納す
る階層情報記憶手段１１と、各グループの配置領域を格
納するグループ領域記憶手段１２と、配置改良処理実行
時に同一グループ内のブロックを交換対象として選択す
る交換対象ブロック選択手段５と、選択さルたブロック
の交換の可否を判定する交換結果良否判定手段６と、前
記ブロックの交換を行う交換手段７とを含む。
情報入力手段１は必要なデータを全て、入力し、それら
を以後使用しやすい形に変換して、配置情報記憶手段１
３に格納する。このデータの内容は、ブロック接続情報
、ブロック外形情報、下地情報等である。このデータの
格納が終了すると、制御手段２１は、グループ化手段２
に制御を渡す。グループ化手段は配置情報記憶手段１３
内のブロック接続情報をもとに、全体を予め決めらｎた
数のグループに分割する。この際、１つのグループ内に
は、できるだけその接続関係の強いブロックがまとまる
ような考慮をはらう。この結果は、階層情報記憶手段１
１に格納される。
を以後使用しやすい形に変換して、配置情報記憶手段１
３に格納する。このデータの内容は、ブロック接続情報
、ブロック外形情報、下地情報等である。このデータの
格納が終了すると、制御手段２１は、グループ化手段２
に制御を渡す。グループ化手段は配置情報記憶手段１３
内のブロック接続情報をもとに、全体を予め決めらｎた
数のグループに分割する。この際、１つのグループ内に
は、できるだけその接続関係の強いブロックがまとまる
ような考慮をはらう。この結果は、階層情報記憶手段１
１に格納される。
続いて、制御手段２１はグループ領域決定手段３に制御
を渡し、今得らｎたグループ化の情報及び配置情報記憶
手段１３内にあるブロック外形情報をもとに、各グルー
プのＬＳＩ又はプリント基板上での領域を決定する。こ
の際、グループ間の接続ができるだけ短くなるような領
域決定の方法を用いる。この結果はグループ領域記憶手
段１２に格納さｎる。
を渡し、今得らｎたグループ化の情報及び配置情報記憶
手段１３内にあるブロック外形情報をもとに、各グルー
プのＬＳＩ又はプリント基板上での領域を決定する。こ
の際、グループ間の接続ができるだけ短くなるような領
域決定の方法を用いる。この結果はグループ領域記憶手
段１２に格納さｎる。
次に、今まで得られた情報をもとに、初期配置手段４は
ブロックの初期配置を決定し、各ブロックの配置結果、
その属するグループ領域内で、できるだけ総線長が短く
なるような考慮を払い、その配置結果全配置情報記憶手
段１３に格納する。
ブロックの初期配置を決定し、各ブロックの配置結果、
その属するグループ領域内で、できるだけ総線長が短く
なるような考慮を払い、その配置結果全配置情報記憶手
段１３に格納する。
次に配置改良処理部はまず、制御手段２１により交換対
象ブロック選択手段５に制御を渡す。この選択手段５は
階層情報記憶手段１１のもとにあるグループに含ま几る
ブロックを２個あるいはα個（α≧３）選択する。この
選択基準は、任意に選んだり、先に選んだブロックの接
続関係から求めた重心付近にあるブロックを次に選んだ
ゆする。
象ブロック選択手段５に制御を渡す。この選択手段５は
階層情報記憶手段１１のもとにあるグループに含ま几る
ブロックを２個あるいはα個（α≧３）選択する。この
選択基準は、任意に選んだり、先に選んだブロックの接
続関係から求めた重心付近にあるブロックを次に選んだ
ゆする。
次に、交換結果良否判定手段６は今選択さまたブロック
のペアを交換した結果を判定する。判定基準は、いくつ
かのバリエーションがあるが、通常は、総配腺長最小化
が用いらＣる。この段階で否となった場合には、制御手
段２１により制御を交換対象ブロック選択手段５に戻し
、新たなブロックのペアを選択する。又、良となりた場
合には、制御手段２１により制御を交換手段７に渡す。
のペアを交換した結果を判定する。判定基準は、いくつ
かのバリエーションがあるが、通常は、総配腺長最小化
が用いらＣる。この段階で否となった場合には、制御手
段２１により制御を交換対象ブロック選択手段５に戻し
、新たなブロックのペアを選択する。又、良となりた場
合には、制御手段２１により制御を交換手段７に渡す。
ここでは、配置情報記憶手段１３内にあるブロックの配
置結果を、交換結果と置換する。
置結果を、交換結果と置換する。
この後、制御手段２１は、核グループ内ブロックの組み
合わせが全部終了したか否か判定し、否か判定し、否の
場合には、次の組み合わせを求めるため、交換対象ブロ
ック選択手段５に制御を戻、す。終了した場きには、次
に全グループに対して以上の繰り返し処理を終了したか
否か判定し、否の場合は、同様に交換対象ブロック選択
手段５に制御を戻す、全グループに対して上記処理が終
了した場合に初めて情報出力手段８に制御を渡し、今ま
でに得らｎた配置結果を配置情報記憶手段１３から読み
出し、そｎを外部に出力する。
合わせが全部終了したか否か判定し、否か判定し、否の
場合には、次の組み合わせを求めるため、交換対象ブロ
ック選択手段５に制御を戻、す。終了した場きには、次
に全グループに対して以上の繰り返し処理を終了したか
否か判定し、否の場合は、同様に交換対象ブロック選択
手段５に制御を戻す、全グループに対して上記処理が終
了した場合に初めて情報出力手段８に制御を渡し、今ま
でに得らｎた配置結果を配置情報記憶手段１３から読み
出し、そｎを外部に出力する。
本実施例においては配置改良処理部の計算複雑度を０（
ｋＮ２）とすると（ｋ：くり返し回数、Ｎ：配置対象ブ
ロック数）従来方式の配置改良処理部に要する計算時間
は０（ｋＮ）であるのに対し、全体をｍ個のグループに
グループ化したとすると計算時間は、 ０（ｋｎ）（但し、ｎ＝−ＬＮ） となり、従来方式に比し、大幅な減少が期待できる。
ｋＮ２）とすると（ｋ：くり返し回数、Ｎ：配置対象ブ
ロック数）従来方式の配置改良処理部に要する計算時間
は０（ｋＮ）であるのに対し、全体をｍ個のグループに
グループ化したとすると計算時間は、 ０（ｋｎ）（但し、ｎ＝−ＬＮ） となり、従来方式に比し、大幅な減少が期待できる。
（発明の効果）
本発明は、以上説明したように、グループ化手段、グル
ープ領域決定手段、階層情報記憶手段、グループ領域記
憶手段を付加することにより、グループ単位の配置改良
処理を可能にし、処理時間を大幅に短縮できる等の効果
がある。
ープ領域決定手段、階層情報記憶手段、グループ領域記
憶手段を付加することにより、グループ単位の配置改良
処理を可能にし、処理時間を大幅に短縮できる等の効果
がある。
図面は、本発明の一実施例を示す構成図である。
１・・・・・・情報入力、２・・・・・・グループ化手
段、３・・・・・・グループ領域決定手段、４・・・・
・・初物配置手段、５・・・・・・交換対象ブロック選
択手段、６・・・・・・交換結果良否判定手段、７・・
・・・・交換手段、８・・・・・・情報出力手段、１１
・・・・・・階層情報記憶手段、１２・・・・・・グル
ープ領域記憶手段、１３・・・・・・配置情報記憶手段
、２１・・・・・・制御手段。 ｒパフζ−−゛−。 代理人 弁理士 内 原 晋 （、。 ″、−・、、：′、・
段、３・・・・・・グループ領域決定手段、４・・・・
・・初物配置手段、５・・・・・・交換対象ブロック選
択手段、６・・・・・・交換結果良否判定手段、７・・
・・・・交換手段、８・・・・・・情報出力手段、１１
・・・・・・階層情報記憶手段、１２・・・・・・グル
ープ領域記憶手段、１３・・・・・・配置情報記憶手段
、２１・・・・・・制御手段。 ｒパフζ−−゛−。 代理人 弁理士 内 原 晋 （、。 ″、−・、、：′、・
Claims (1)
- ＬＳＩ、プリント基板等の中に収容し、かつ配置単位と
なるブロックを配置する配置処理方式において、全入力
ブロックを指定のグループ数になるまで分割するグルー
プ化手段と、ＬＳＩ、プリント基板等の下地基板上での
グループの配置領域を決定するグループ領域決定手段と
、該グループ内に属するブロック情報を格納する階層情
報記憶手段と、各グループの配置領域を格納するグルー
プ領域記憶手段と、配置改良処理実行時に同一グループ
内のブロックを交換対象として選択する交換対象ブロッ
ク選択手段と、選択されたブロックの交換の可否を判定
する交換結果良否判定手段と、前記ブロックの交換を行
う交換手段とを含むことを特徴とする階層的配置処理方
式。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP60050920A JPH0665222B2 (ja) | 1985-03-14 | 1985-03-14 | 階層的配置処理方式 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP60050920A JPH0665222B2 (ja) | 1985-03-14 | 1985-03-14 | 階層的配置処理方式 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS61208845A true JPS61208845A (ja) | 1986-09-17 |
| JPH0665222B2 JPH0665222B2 (ja) | 1994-08-22 |
Family
ID=12872229
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP60050920A Expired - Lifetime JPH0665222B2 (ja) | 1985-03-14 | 1985-03-14 | 階層的配置処理方式 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH0665222B2 (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH02143376A (ja) * | 1988-11-25 | 1990-06-01 | Agency Of Ind Science & Technol | 機器レイアウト方法 |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS59132144A (ja) * | 1983-01-19 | 1984-07-30 | Hitachi Ltd | 半導体集積回路装置の製造方法 |
| JPS59145541A (ja) * | 1983-02-09 | 1984-08-21 | Hitachi Ltd | Ｌｓｉレイアウト処理方法 |
-
1985
- 1985-03-14 JP JP60050920A patent/JPH0665222B2/ja not_active Expired - Lifetime
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS59132144A (ja) * | 1983-01-19 | 1984-07-30 | Hitachi Ltd | 半導体集積回路装置の製造方法 |
| JPS59145541A (ja) * | 1983-02-09 | 1984-08-21 | Hitachi Ltd | Ｌｓｉレイアウト処理方法 |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH02143376A (ja) * | 1988-11-25 | 1990-06-01 | Agency Of Ind Science & Technol | 機器レイアウト方法 |
Also Published As
| Publication number | Publication date |
|---|---|
| JPH0665222B2 (ja) | 1994-08-22 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US5144563A (en) | Method and apparatus for optimizing element placement and method and apparatus for deciding the optimal element placement | |
| EP0403826B1 (en) | Minimizing the interconnection cost of electronically linked objects | |
| US5113352A (en) | Integrating the logical and physical design of electronically linked objects | |
| Savage et al. | Parallelism in graph-partitioning | |
| JPH0587867B2 (ja) | ||
| US20020100008A1 (en) | Method for min-cut and ratio min-cut partitioning | |
| US5757653A (en) | Method and apparatus for dynamically varying net rules | |
| JPH0665222B2 (ja) | 階層的配置処理方式 | |
| JPS5846173B2 (ja) | 論理配線設計方式 | |
| JP2536640B2 (ja) | 配線処理方式 | |
| JPS63181348A (ja) | Ｌｓｉのレイアウト設計装置 | |
| JPH06266801A (ja) | フロアプランを考慮した論理合成方法 | |
| JPH03121569A (ja) | 部品配置位置決定システム | |
| JP2536119B2 (ja) | 配線処理方式 | |
| JPS62115574A (ja) | 並列配線方式 | |
| Matsuda et al. | LAMBDA: A Quick, Low Cost Layout Design System for Master-Slice LSIs | |
| JP2729061B2 (ja) | シミュレーション装置のゼロ遅延演算処理方式 | |
| JPH04359377A (ja) | 配線層割付方式 | |
| JPH06266800A (ja) | フロアプランを考慮した論理合成方法 | |
| JPH0239376A (ja) | 論理回路合成装置 | |
| JPH01260581A (ja) | 図形処理方法 | |
| JPH06105756B2 (ja) | 配置決定方法 | |
| JPH05282400A (ja) | 汎用ｒｏｍ部マスクパターン自動生成方法 | |
| Alaimo | A" graphics window" to a data base for electronic system design | |
| JPH03256130A (ja) | 割込要因検索方式 |