JPS6197786A - Ｃａｄによる階層的配置決定システム - Google Patents
Ｃａｄによる階層的配置決定システムInfo
- Publication number
- JPS6197786A JPS6197786A JP59219027A JP21902784A JPS6197786A JP S6197786 A JPS6197786 A JP S6197786A JP 59219027 A JP59219027 A JP 59219027A JP 21902784 A JP21902784 A JP 21902784A JP S6197786 A JPS6197786 A JP S6197786A
- Authority
- JP
- Japan
- Prior art keywords
- group
- arrangement
- block
- blocks
- determining
- 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.)
- Pending
Links
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
発明の目的
産業上の利用分野
本発明は、ＣＡＤによる配置決定システムに関するもの
である。
である。
従来の技術
］ンピューターを使用して行うプリント板や１、Ｓ■等
の自動実装設計は、一般に、まず部品等のブロックの配
置を決定し９次に配置が決定されたブロック相互間の配
線経路を決定するという段階を経て行われる。
の自動実装設計は、一般に、まず部品等のブロックの配
置を決定し９次に配置が決定されたブロック相互間の配
線経路を決定するという段階を経て行われる。
プリント配線板や半導体基板等ブロックが配置される空
間は、一般に、格子状に区切られており。
間は、一般に、格子状に区切られており。
ブロックの大きさくブロック・サイズ）に応じてこれら
格子状空間の何個かがそのブロックを配置するために割
当てられる。このブロックの配置の決定にあたっては、
ブロック・→ノ゛イズやブロック相互間の配線数等を表
示するブロック間接続情報に基づき、何等かの最適化が
行われる。この最適化の指標として、一般に、ブロック
間の総配線長や、配線密度の均一性、あるいはこれらを
合成したもの等が使用されている。
格子状空間の何個かがそのブロックを配置するために割
当てられる。このブロックの配置の決定にあたっては、
ブロック・→ノ゛イズやブロック相互間の配線数等を表
示するブロック間接続情報に基づき、何等かの最適化が
行われる。この最適化の指標として、一般に、ブロック
間の総配線長や、配線密度の均一性、あるいはこれらを
合成したもの等が使用されている。
発明が解決しようとする問題点
最近１部品の小型化や半導体基板の大型化等技術の急激
な進歩に伴って配置すべきブロックの故が著しく増加し
、最適配置を決定するための時間も究めて長くかかると
いう問題が生じている。
な進歩に伴って配置すべきブロックの故が著しく増加し
、最適配置を決定するための時間も究めて長くかかると
いう問題が生じている。
発明の構成
問題点を解決するための手段
上記従来技術の問題点を解決する本発明の配置決定シス
テムは、ブロック間接続情報に基づき。
テムは、ブロック間接続情報に基づき。
接続関係の密なブロック相互を同一の群に所属させるよ
うに全ブロックを所定数の群に分ける手段と、各群の配
置を決定する手段と１群に所属する複数のブロックに対
し群内配置を決定する手段とを備え、ブロックの配置を
階層的に短時間で決定するように構成されている。
うに全ブロックを所定数の群に分ける手段と、各群の配
置を決定する手段と１群に所属する複数のブロックに対
し群内配置を決定する手段とを備え、ブロックの配置を
階層的に短時間で決定するように構成されている。
以下２本発明の作用を実施例によって詳細に説明する。
実施例
第１図は２本発明の一実施例の構成を示す機能ブロック
図である。本実施例のシステムは、複数ブロック間の接
続線数を表示するブロック間接続情弗が入力される人力
部１２人力されたブロック間接続情報に基づき、接続関
係の密なブロック相互を同一の群に所属させるように全
ブロックを所定数の群に分ける群分は部２．各群の配置
を決定する群配置決定部３５群内の複数のプロ・ツクに
対し群内配置を決定する群内配置決定部４．比出力５及
び記憶部６を備えている。
図である。本実施例のシステムは、複数ブロック間の接
続線数を表示するブロック間接続情弗が入力される人力
部１２人力されたブロック間接続情報に基づき、接続関
係の密なブロック相互を同一の群に所属させるように全
ブロックを所定数の群に分ける群分は部２．各群の配置
を決定する群配置決定部３５群内の複数のプロ・ツクに
対し群内配置を決定する群内配置決定部４．比出力５及
び記憶部６を備えている。
本システムの動作が開始されると、まず２人力部１にブ
ロック間接続情報が入力される。
ロック間接続情報が入力される。
このブロック間接続情報は１例えば、第２図に示すよう
に、ブロック名、ブロック・サイズ、接続相手ブロック
名、各接続相手に対する配線数から構成されている。
に、ブロック名、ブロック・サイズ、接続相手ブロック
名、各接続相手に対する配線数から構成されている。
人力部１は、入力されたブロック間接続情報を記憶部６
に書込んだ後１群分け２に制御を渡す。
に書込んだ後１群分け２に制御を渡す。
群分は部２は、記憶部６に書込まれている群数指定情報
と、入力部１が書込んだブロック間接続情報とに基づき
１群分は処理を開始する。この群分は処理は、接続関係
の密なブロック相互を同一の群に所属させるように、全
プロ・ツクを指定された数の群に分けるように行われる
。
と、入力部１が書込んだブロック間接続情報とに基づき
１群分は処理を開始する。この群分は処理は、接続関係
の密なブロック相互を同一の群に所属させるように、全
プロ・ツクを指定された数の群に分けるように行われる
。
すなわち１群ｉと群ｊ相互間の接続関係の密接度ＣＶ、
、Ｊは２次式で与えられる。
、Ｊは２次式で与えられる。
ＣＶ、、ｊ
＝ｆ（Ｓｉ） ・Ｃ４，ｊ ／ （Ｔｉ −ｃ、、、
）＋ｆ（Ｓ、） ・Ｃ，、、／ （Ｔｊ −Ｃｉ、
ｊ ＞・・・・ （１） ただし、ｆ （Ｓｉ）、ｆ （Ｓｊ）はそれぞれブ
ロックｉとｊ のブロック・サイズに依存する関数、Ｃ
，、ｊはブロックｉと１間の配線数、Ｔ、。
）＋ｆ（Ｓ、） ・Ｃ，、、／ （Ｔｊ −Ｃｉ、
ｊ ＞・・・・ （１） ただし、ｆ （Ｓｉ）、ｆ （Ｓｊ）はそれぞれブ
ロックｉとｊ のブロック・サイズに依存する関数、Ｃ
，、ｊはブロックｉと１間の配線数、Ｔ、。
Ｔ、はそれぞれブロックｉとｊの他のブロックに対する
配線数の総和である。
配線数の総和である。
例えば、記憶部６に書込まれているブロック間接続情報
が、第３図に示すように、ブロック１とブロック２が３
本の配線で接続され、プロ・ツク２とブロック３が５本
の配線で接続され、ブロック３とブロック４が３木の配
線で接続され、ブロック４とブロック１が４木の配線で
接続され・・・というようなものであったとする。この
場合。
が、第３図に示すように、ブロック１とブロック２が３
本の配線で接続され、プロ・ツク２とブロック３が５本
の配線で接続され、ブロック３とブロック４が３木の配
線で接続され、ブロック４とブロック１が４木の配線で
接続され・・・というようなものであったとする。この
場合。
Ｔ、＝９．’ｒｚ ＝９＋ Ｔｉ ＝１０．Ｔ４＝８゜
また、Ｃ＋、ｚ ＝３．Ｃ＋、：＋ ＝２．Ｃｚ、＊
＝５．Ｃ＋、Ａ＝ ４． Ｃ２，４＝ １ 、 Ｃ
３，４＝ ３ となる。
また、Ｃ＋、ｚ ＝３．Ｃ＋、：＋ ＝２．Ｃｚ、＊
＝５．Ｃ＋、Ａ＝ ４． Ｃ２，４＝ １ 、 Ｃ
３，４＝ ３ となる。
ここで、簡単のため、 ｆ （Ｓｉ ） ＝ （（
Ｓ２ ） ＝ｒ （Ｓ３ ） ＝ｆ （Ｓ４ ）
ｌ とすると。
Ｓ２ ） ＝ｒ （Ｓ３ ） ＝ｆ （Ｓ４ ）
ｌ とすると。
ＣＶｌ、２ ＝ １ 、ＣＶｌ、３＝ ０・５４
、 ＣＶｚ、、：１＝ ２．２５ 、 ＣＶ＋
、ｊ ＝ １．８０ 、 ＣＶ２，４ ＝ ０
．２７ 、 ＣＶ、、、 ＝ １．０３となる。
、 ＣＶｚ、、：１＝ ２．２５ 、 ＣＶ＋
、ｊ ＝ １．８０ 、 ＣＶ２，４ ＝ ０
．２７ 、 ＣＶ、、、 ＝ １．０３となる。
従って、接続関係の密接度ＣＶ、、、が最大となるブロ
ック２と３が１個の群にまとめられる。この結果、４個
のブロックが、プロ・ツクｌのみから成る第１の群、ブ
ロック２と３から成る第２の群及びブロック４のみから
成る第３の群に群分けされる。指定されている群数が２
であれば、上記３個の群に対して、上述の群分けを繰り
返し、最終的な２個の群を得る。上記群分けの手法の更
に詳細については、１９７２年に開催された第９回Ｄｅ
ｓｉｇｎ Ａｕｔｏｍａｔｉｏｎ Ｃ，ｏｎｆｅｒｅｎ
ｃ、ｅ において、 Ｉ’ｌ、Ｍ。
ック２と３が１個の群にまとめられる。この結果、４個
のブロックが、プロ・ツクｌのみから成る第１の群、ブ
ロック２と３から成る第２の群及びブロック４のみから
成る第３の群に群分けされる。指定されている群数が２
であれば、上記３個の群に対して、上述の群分けを繰り
返し、最終的な２個の群を得る。上記群分けの手法の更
に詳細については、１９７２年に開催された第９回Ｄｅ
ｓｉｇｎ Ａｕｔｏｍａｔｉｏｎ Ｃ，ｏｎｆｅｒｅｎ
ｃ、ｅ において、 Ｉ’ｌ、Ｍ。
５ｃｈｕ ［ｅｒが発表した。 ＣｌｕＳｔｅｒｉｎ
ｇ ａｎｄ ｌ、ｉｎｅａｒＰｌａｃｅｍｅｎｔ”と題
する論文を参照されたい。
ｇ ａｎｄ ｌ、ｉｎｅａｒＰｌａｃｅｍｅｎｔ”と題
する論文を参照されたい。
群分は部２は、上記群分けの結果を、第４図に例示する
ように２群名、構成プロ・ツク名、接続相手群名及び各
接続相手群に対する配′！ｊＡ数等から成るテーブルと
して記憶部４に格納したのち１群配置決定ブロック３に
制御を渡す。
ように２群名、構成プロ・ツク名、接続相手群名及び各
接続相手群に対する配′！ｊＡ数等から成るテーブルと
して記憶部４に格納したのち１群配置決定ブロック３に
制御を渡す。
群配置決定部３は、記憶部６に記憶されている基板上の
配置可能位置情報に基づき、所定数の群に対し基板上の
配置を決定する。この群配置の決定に際しては、従来方
式によるブロック配置の決定の際と同様に、適宜な最適
化が行われる。
配置可能位置情報に基づき、所定数の群に対し基板上の
配置を決定する。この群配置の決定に際しては、従来方
式によるブロック配置の決定の際と同様に、適宜な最適
化が行われる。
簡単のため、上記最適化の指標が群間総配線長の最小化
のみにあるものとする。更に、簡曵のため１群分けされ
た各群が第５図（Ａ）に例示するように、同一サイズの
４個の群ａ、ｂ、ｃ及びｄから成り、各群間には図中の
数字で表示される配線数の接続が行われるものとする。
のみにあるものとする。更に、簡曵のため１群分けされ
た各群が第５図（Ａ）に例示するように、同一サイズの
４個の群ａ、ｂ、ｃ及びｄから成り、各群間には図中の
数字で表示される配線数の接続が行われるものとする。
また、上記４個の群に対して９、同図（Ｂ）に示すよう
な格子状の４個の基板上の配置可能位置（１，１）、
（２，１）、 （２，１）及び（２，２）が用意さ
れているものとする。斜め方向に隣接する格子間の距離
は、上下、左右に隣接する格子間の距離よりも大きくな
る。従って、第５図に示すように、配線数の少ない群相
互が対角線の位置にくるように各群を配置すれば１、群
間総配線長は最小になる。
な格子状の４個の基板上の配置可能位置（１，１）、
（２，１）、 （２，１）及び（２，２）が用意さ
れているものとする。斜め方向に隣接する格子間の距離
は、上下、左右に隣接する格子間の距離よりも大きくな
る。従って、第５図に示すように、配線数の少ない群相
互が対角線の位置にくるように各群を配置すれば１、群
間総配線長は最小になる。
上記群間配線長を最小にする処理に際しては。
１９７７年に開催された第１４回 Ｄｅｓｉｇｎ Ａ＋
＋ｔｏｍａｔｉｏｎ Ｃｏｎｆｅｒｅｎｃｅ におい
て、 Ｍ、Ａ、Ｒｒｅｕｅｒが発表した＋ ＡＣｌａ
ｓｓ ｏｆ Ｍｉｎ Ｃｕｔ Ｐｌａｃｅｍｅｎｔ
ＡＩｇｏｒｉｓｍ”と題するする論文に記載されたカッ
トライン法等が使用される。
＋ｔｏｍａｔｉｏｎ Ｃｏｎｆｅｒｅｎｃｅ におい
て、 Ｍ、Ａ、Ｒｒｅｕｅｒが発表した＋ ＡＣｌａ
ｓｓ ｏｆ Ｍｉｎ Ｃｕｔ Ｐｌａｃｅｍｅｎｔ
ＡＩｇｏｒｉｓｍ”と題するする論文に記載されたカッ
トライン法等が使用される。
群配置決定部は、上述のようにして群の配置を決定する
と、第４図のテーブルに決定した群配置を追加し２群内
配置決定部４に制御を渡す。
と、第４図のテーブルに決定した群配置を追加し２群内
配置決定部４に制御を渡す。
群内配置決定部４は、記憶部６のテーブルを参照し、複
数のブロックから構成されている群について、各ブロッ
クの群内配置を決定する。この際。
数のブロックから構成されている群について、各ブロッ
クの群内配置を決定する。この際。
上記群配置決定の際と同様に、適宜な最適化がおこなわ
れる。群内配置決定部４は、決定した群内配置を第４図
のテーブルに追加し、出力部５に制御を渡す。
れる。群内配置決定部４は、決定した群内配置を第４図
のテーブルに追加し、出力部５に制御を渡す。
出力部５は、第４図のテーブルに群配置と群内配置が付
加された最終的なブロック配置情報を記憶部６から読出
し、出力する。
加された最終的なブロック配置情報を記憶部６から読出
し、出力する。
群の配置や１群内のブロックの配置の決定に際して総配
線長や、配線密度の均−性等を最適配置の指標とする代
りに、所望の電気的特性に近づけるための適宜な指標１
例えば群間やブロック間の伝播遅延時間を均一化するう
えでの配線長の均−性等を最適配置の指標としてもよい
。
線長や、配線密度の均−性等を最適配置の指標とする代
りに、所望の電気的特性に近づけるための適宜な指標１
例えば群間やブロック間の伝播遅延時間を均一化するう
えでの配線長の均−性等を最適配置の指標としてもよい
。
発明の効果
以上詳細に説明したように２本発明の配置決定システム
は、接続関係の密なブロック相互を同一の群に所属させ
るように全ブロックを所定数の群に分ける手段と、各群
の配置を決定する手段と。
は、接続関係の密なブロック相互を同一の群に所属させ
るように全ブロックを所定数の群に分ける手段と、各群
の配置を決定する手段と。
群に所属する複数のブロックに対し群内配置を決定する
手段とを備えることにより、ブロックの配置を階層的に
決定するように構成されているので。
手段とを備えることにより、ブロックの配置を階層的に
決定するように構成されているので。
最適配置を決定するための時間を大幅に短縮できるとい
う効果が奏される。
う効果が奏される。
第１図は本発明の一実施例のシステムの機能ブロック関
、第２図、第３図は第１図の入力部１に人力されるブロ
ック間接続（ｆｉ ＩＩの一例を示す図。 第４図は第１図の群分は部２によって作成された群分は
情報の一例を示す図、第５図は第１図の群配置決定部３
による群配置決定方法の一例を説明するための概念図で
ある。 １・・人力部、２・・群分は部、３・・群配置決定部、
４・・群内配置決定部、５・・出力部。 ６・・記憶部。 菩３ 図
、第２図、第３図は第１図の入力部１に人力されるブロ
ック間接続（ｆｉ ＩＩの一例を示す図。 第４図は第１図の群分は部２によって作成された群分は
情報の一例を示す図、第５図は第１図の群配置決定部３
による群配置決定方法の一例を説明するための概念図で
ある。 １・・人力部、２・・群分は部、３・・群配置決定部、
４・・群内配置決定部、５・・出力部。 ６・・記憶部。 菩３ 図
Claims (1)
- 【特許請求の範囲】 複数ブロック間の接続線数を表示するブロック間接続情
報が入力される入力手段と、 該入力されたブロック間接続情報に基づき、接続関係の
密なブロック相互を同一の群に所属させるように、全ブ
ロックを所定数の群に分ける群分け手段と、 該各群の配置を決定する群装置決定手段と、群内の複数
のブロックに対し群内配置を決定する群内配置決定手段
とを備えたことを特徴とするＣＡＤによる階層的配置決
定システム。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP59219027A JPS6197786A (ja) | 1984-10-18 | 1984-10-18 | Ｃａｄによる階層的配置決定システム |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP59219027A JPS6197786A (ja) | 1984-10-18 | 1984-10-18 | Ｃａｄによる階層的配置決定システム |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPS6197786A true JPS6197786A (ja) | 1986-05-16 |
Family
ID=16729103
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP59219027A Pending JPS6197786A (ja) | 1984-10-18 | 1984-10-18 | Ｃａｄによる階層的配置決定システム |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPS6197786A (ja) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH02143376A (ja) * | 1988-11-25 | 1990-06-01 | Agency Of Ind Science & Technol | 機器レイアウト方法 |
| JP2010140474A (ja) * | 2008-12-09 | 2010-06-24 | Internatl Business Mach Corp <Ibm> | 集積回路（ｉｃ）のレイアウト図および配線図を作り出すシステムならびにフラット配置済みレイアウトを作り出すための方法およびコンピュータ・プログラム製品（カスタム・マクロの高速ルーティング） |
Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS53120333A (en) * | 1977-03-30 | 1978-10-20 | Sharp Corp | Parts arrangement method of printed circuit substrate |
| JPS57128952A (en) * | 1981-02-02 | 1982-08-10 | Sharp Corp | Method for arranging functional block in lsi design |
| JPS59145541A (ja) * | 1983-02-09 | 1984-08-21 | Hitachi Ltd | Ｌｓｉレイアウト処理方法 |
-
1984
- 1984-10-18 JP JP59219027A patent/JPS6197786A/ja active Pending
Patent Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS53120333A (en) * | 1977-03-30 | 1978-10-20 | Sharp Corp | Parts arrangement method of printed circuit substrate |
| JPS57128952A (en) * | 1981-02-02 | 1982-08-10 | Sharp Corp | Method for arranging functional block in lsi design |
| JPS59145541A (ja) * | 1983-02-09 | 1984-08-21 | Hitachi Ltd | Ｌｓｉレイアウト処理方法 |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH02143376A (ja) * | 1988-11-25 | 1990-06-01 | Agency Of Ind Science & Technol | 機器レイアウト方法 |
| JP2010140474A (ja) * | 2008-12-09 | 2010-06-24 | Internatl Business Mach Corp <Ibm> | 集積回路（ｉｃ）のレイアウト図および配線図を作り出すシステムならびにフラット配置済みレイアウトを作り出すための方法およびコンピュータ・プログラム製品（カスタム・マクロの高速ルーティング） |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US4577276A (en) | Placement of components on circuit substrates | |
| US3567914A (en) | Automated manufacturing system | |
| Wise | Compact layouts of banyan/FFT networks | |
| JPH03180976A (ja) | 入出力端子割付方法 | |
| JPH0750817B2 (ja) | 配線相互接続構造体 | |
| US4535388A (en) | High density wired module | |
| US5151868A (en) | Signal line terminal allocation method | |
| JPS6197786A (ja) | Ｃａｄによる階層的配置決定システム | |
| JPS63107041A (ja) | レイアウト設計における配置改良方法 | |
| JPH0951193A (ja) | 実装部品振り分け方法及び実装設備 | |
| KR20010024944A (ko) | 전자 소자 및 장치의 설계 및 제조 방법 | |
| JPS6231501B2 (ja) | ||
| Tanaka et al. | An integrated computer aided design system for gate array masterslices: Part 2 The layout design system Mars-M3 | |
| JPH0442571A (ja) | 半導体集積回路装置における集積回路素子の配置方法 | |
| JPS6331192A (ja) | プリント板の配線方法 | |
| JPS6355783B2 (ja) | ||
| KASHIWABARA et al. | Permutation layout with limited between-pins congestion | |
| JPS62122145A (ja) | マスタスライス方式ｌｓｉ | |
| JPH01274266A (ja) | コンピュータ・システム | |
| JPS62273751A (ja) | 集積回路 | |
| JPH05120378A (ja) | 集積回路の予測配線長計算法 | |
| JPH02127772A (ja) | 配線処理方式 | |
| JPS62243400A (ja) | 素子割付方式 | |
| JPH09179778A (ja) | メモリインタリーブ方法および装置 | |
| JPH0258172A (ja) | 論理回路図面分割システム |