JPH03154363A - 階層的配置処理方式 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は階層的配置処理方式に関し、特にＬＳｌ　　（
Ｌａｒｇｅ−３ｃａｌｅ　　Ｉｎｔｅｇｒａｔｅｄ　　
ｃｉｒｃｕ［ｔ）、プリント基板等のマクロブロック内
のブロック配置処理を含む階層的配置処理方式に関する
。

〔従来の技術〕

従来、この種の階層的配置処理方式では、マクロブロッ
ク内に配置されるブロックがマクロブロックの外部端子
と接続していない場合には既配置のブロックの端子との
接続関係と既装置のブロックの配置位置とに基づいてブ
ロックを配置しているが、外部端子との接続がありかつ
外部端子位置が全く決まっていない場合、あるいはマク
ロブロックの中心位置等を外部端子位置と仮定している
場合には、外部端子位置を考慮できないために外部端子
との接続関係を除き、既装置のブロックの端子との接続
関係と既装置のブロックの配置位置とからブロックを配
置していた。

〔発明が解決しようとする課題〕

上述した従来の階層的配置処理方式では、外部端子との
接続がありかつ外部端子位置が全く決まっていない場合
、あるいはマクロブロックの中心位置等を外部端子位置
と仮定している場合には、以下のような欠点がある。

（１）　　マクロブロック内にブロックを配置するとき
に外部端子と接続していても外部端子位置を考°慮でき
ないので、マクロブロック内の既装置のブロックの端子
との接続関係と既装置のブロックの配置位置とを基にブ
ロックの配置位置を決めることになり、その結果、例え
ば第３図に示すように、ブロック６．７．８および９が
マクロブロック１の中央部に集中して配置され、配線処
理時に局所的に配線領域が不足したり、外部端子とブロ
ックとの間の配線長が長くなったりする。

（２）　マクロブロック間の配線処理時にマクロブロッ
クの外部端子との配線経路を決定できないので、マクロ
プロ７りを展開してマクロブロック内の接続関係および
配置位置も参照しなければならず、処理時間が増大する
。

本発明の目的は、上述の点に鑑み、マクロブロック内の
ブロックの配置処理に先立ってマクロブロックの外部端
子位置を決定して、ブロックがマクロブロックの中央部
に集中して配置されることを回避するとともに、マクロ
ブロックを展開してマクロブロック内の接続関係および
配置位置を参照する処理を不要にするようにした階層的
配置処理方式を提供することにある。

（課題を解決するための手段〕 本発明の階層的配置処理方式は、ＬＳｔ、プリント基板
等のマクロブロック内のブロックの配置処理を含む階層
的配置処理方式において、マクロブロックの中心位置を
求める中心位置計算手段と、マクロブロックの外部端子
の各々と接続している他のブロックの端子ある□し：は
入出力パッドの位置より重心位置を求める重心位置層＋
算手段と、前記中心位置計算手段により求められたマク
ロブロックの中心位置と前記重心位置計算手段により求
められた重心位置とを結んだ直線がマクロブロックの周
囲辺と交叉する点を外部端子位置とする外部端子位置決
定手段と、マクロテロツク内に配置されるブロックがマ
クロテロツク内 していない場合にはマクロブロック内の既装置のブロッ
クの端子との接続関係と既装置のブロックの配置位置と
を基にしで°ｉミロツク配置しマクロブロック内に配置
されるブロックがマクロブロックの外部端子と接続して
いる場合にはマクロテロツク内の既装置のブロックめ端
子および外部端子との接続関係とマクロテロツク内の既
装置のブロックおよび外部端子の配置位置とを基にして
ブロックを配置するブロック配置手段とを有する。

（作用〕 本発明の階層的配置処理方式では、中心位置計算手段が
マクロブロックの中心位置を求め、重心位置計算手段が
マクロブロックの外部端子の各々と接続している他のブ
ロックの端子あるいは入出力パッドの位置より重心位置
を求め、外部端子位置決定手段が中心位置計算手段によ
り求められたマクロブロックの中心位置と重心位置計算
手段により求められた重心位置とを結んだ直線がマクロ
ブロックの周囲辺と交叉する点を外部端子位置とし、ブ
ロック配置手段がマクロテロツク内に配置されるブロッ
クがマクロブロックの外部端子と接続していない場合に
はマクロブロック内の既装置のブロックの端子との接続
関係と既装置のブロックの配置位置とを基にしてブロッ
クを配置しマクロブロック内に配置されるブロックがマ
クロブロックの外部端子と接続している場合にはマクロ
ブロック内の既装置のブロックの端子および外部端子と
の接続関係とマクロブロック内の既装置のプロックおよ
び外部端子の配置位置とを基にしてブロックを配置する
。

〔実施例〕

次に、本発明について図面を参照して詳細に説明する。

第１図は、本発明の一実施例に係る階層的配置処理方式
における処理手順を示す流れ図である。

本実施例の階層的配置処理方式は、マクロブロックおよ
びマクロブロックに属さないブロックの配置を行う第１
ステツプと、マクロブロックの中心位置を計算する第２
ステツプと、マクロブロックの外部端子に対する接続関
係の重心位置を計算する第３ステツプと、求められた中
心位置と重心位置とを結ぶ直線を求める第４ステツプと
、直線とマクロブロックの周囲辺との交点を求めて重心
位置に最も近い交点を外部端子位置とする第５ステツプ
と、外部端子位置が全て決定したか否かを判断する第６
ステツプと、マクロブロック内に配置するブロックが外
部端子と接続しているか否かを判断する第７ステツプと
、外部端子および既配置のブロックの端子との接続関係
と外部端子および既配置のブロックの配置位置とを基に
ブロックの配置位置を求める第８ステツプと、既配置の
ブロックの端子との接続関係と既配置のブロックの配置
位置とを基にブロックの配置位置を求める第９ステツプ
と、ブロックが全て配置されたか否かを判断する第１Ｏ
ステツプと、全てのマクロブロックに対して処理をした
か否かを判断する第１１ステツプとから構成されている
。ここで、第２ステツプは中心位置計算手段１１０を、
第３ステツプは重心位置計算手段１２０を、第４ステツ
プおよび第５ステツプは外部端子位置決定手段１３０を
、第７ステツプ、第８ステツプおよび第９ステツプはブ
ロック配置手段１４０をそれぞれ構成している。

なお、本実施例の階層的配置処理方式は、第１図に示す
流れ図に従ってプログラムを作成してコンピュータで自
動処理することにより実現することもできるし、ハード
ウェア化して動作させることにより実現することもでき
る。そして、それら各々の方法で実現される結果が同一
になることは明白である。

次に、このように構成された本実施例の階層的配置処理
方式の動作についてステップを遷って説明する。

（第１ステツプ）　マクロブロックおよびマクロブロッ
クに属さないブロックを配置する。このとき、マクロブ
ロックが１つも無ければ処理を終了する。

（第２ステツプ）　マクロブロックの中心位置を計算す
る。

（第３ステツプ）　マクロブロックの外部端子の各々に
対して接続されている既配置のブロックの端子あるいは
人出力バンドの位置から重心位置を計算する。

（第４ステツプ）　第２ステツプで求めたマクロブロッ
クの中心位置と第３ステツプで求めた外部端子に対する
接続関係の重心位置とを結ぶ直線を求める。

（第５ステツプ）　第４ステツプで求めた直線とマクロ
ブロックの周囲辺との交点を全て求め、第３ステツプで
求めた重心位置に最も近い交点を外部端子位置と決定す
る。

（第６ステツプ）　マクロブロックの全ての外部端子位
置が決まるまで第３ステツプから第５ステツプまでを繰
り返し、全ての外部端子位置が決まったならば第７ステ
ツプ以降のマクロブロック内の配置処理に移る。

（第７ステツプ）　配置しようとするブロックの接続関
係に基づいて外部端子と接続しているか否かを判定し、
外部端子と接続していれば第８ステツプに進み、接続し
ていなければ第９ステツプに進む。

（第８ステツプ）　第５ステツプで位置が決定された外
部端子および既配置のブロックの端子との接続関係と外
部端子および既配置のブロックの配置位置とに基づいて
ブロックの配置位置を求め、第１０ステツプに進む。

（第９ステツプ）　既配置のブロックの端子との接続関
係と既配置のブロックの配置位置とに基づいてブロック
の配置位置を求める。

（第１０ステツプ）　全てのブロックが配置されるまで
第７ステツプから第９ステツプまでを繰り返す。

（第１１ステツプ）　全てのマクロブロックについて第
２ステツプから第１０ステツプまでを繰り返して、処理
を終了する。

次に、本実施例の階層的配置処理方式の具体的な適用例
を第２図（Ａ）および（Ｂ）を参照しながら説明する。

第２図（Ａ）は、第５ステツプ終了後のマクロブロック
１０外部端子位置の決定状態を示す図である。

第２図（Ｂ）は、第２図（Ａ）に示した外部端子位置の
決まったマクロブロックｌの内部のブロックの配置状態
を示す図である。

いま、第１ステツプで、マクロブロック１とマクロブロ
ックｌに属さないブロック２．３．４および５とが第２
図（Ａ）に示すように配置されたとする。

次に、第２ステツプで、マクロブロック１の中心位置５
１が求められる。

続いて、第３ステツプで、マクロブロック１の外部端子
１１に対する接続関係の重心位置が求められるが、この
ときに外部端子１１に接続しているのが人出力パッド４
２だけだとすると、重心位置は入出力パッド４２の位置
となる。

次に、第４ステツプで、第２ステツプで求められた中心
位置５１と第３ステツプで求められた重心位置４２とを
結んだ直線が求められる。

続いて、第５ステツプで、第４ステツプで求められた直
線とマクロブロック１の周囲辺との交点１１セよびｌＦ
が求められる。このときに重心位置４２に最も近い交点
は交点１１なので、この位置が外部端子１１の位置と決
定される。

１つの端子（または人出力パッド）２１．２２および２
４としか接続していない他の外部端子１２．１３および
１５についても、外部端子１１の場合と同様にして、外
部端子位置がそれぞれ求まる。

次に、２つの端子２３および２４と接続している外部端
子１４については、第３ステツプで接続しているブロッ
ク４および５の端子２３および２４の接続関係の重心位
置５２が求められる。この後は、１つの端子との接続の
場合と同様に、中心位置５１と重心位置５２とを結んだ
直線とマクロブロックｌの周囲辺との交点より外部端子
１４の位置が決定される。

このようにして、全ての外部端子１１．１２゜１３．１
４および１５の位置が決まったならば、次にマクロブロ
ックｌ内のブロックの配置処理に移る。このとき、第２
図（Ｂ）に示す外部端子１１．１２．１３．１４および
１５の位置だけが求められている。なお、マクロブロッ
クｌ内には、４つのブロック６．７．８お゛よび９を配
置するものとする。

いま、ブロック６を配置す今場合、既配置のブロックは
ないので、ブロック６に接続される外部端子１１および
１２との接続関係と外部端子１１および１２の配置位置
とを基にブロック６の配置位置が求められる。

次に、ブロック７を配置する場合、接続されるのはブロ
ック６および９と外部端子１３とであるが、このときに
ブロック９は未配置なので、ブロック６の端子２７およ
び外部端子１３との接続関係とブロック６および外部端
子１３の配置位置とを基にブロック７の配置位置が求め
られる。

続いて、ブロック８を配置する場合、既配置のブロック
６および７との接続関係はないので、接続される外部端
子１４および１５との接続関係と外部端子１４および１
５の配置位置とを基にブロック８の配置位置が求められ
る。

最後に、ブロック９を配置する場合、外部端子との接続
関係はないので、既配置のプロ７り６゜７および８の端
子２７．２８および３２との接続関係と既配置のブロン
クロ、７および８の配置位置とを基にブロック９の配置
位置が求められる。

全てのブロック６．７．８および９の配置位置の決定後
に改良配置処理を行えばより良好な配宜結果を得られる
であろうが、本実施例の階層的配面処理方式では改良配
置処理方法を特に限定していないのでその説明は省略す
る。

以上で第２図（Ａ）および（Ｂ）を参照した本実施例の
階層的配置処理方式の通用例についての説明を終了する
が、この例は単なる一具体例でしかなく、本発明の通用
がこのような態様に限定されるものでないことはいうま
でもない０例えば、ブロック２．　３．　４および５の
いずれもがマクロブロックであってもよいし、プロフク
ロ、７．８および９についても同様にマクロブロックで
あってもよい、また、マクロブロックやブロックが矩形
である必要もない。

（発明の効果〕 以上説明したように本発明は、マクロブロック内にブロ
ックを配置する前にマクロブロックの外部端子と接続し
ている他のブロックの端子あるいは入出力バンドの位置
を考慮してマクロブロックの周囲辺上に外部端子位置を
決定することにより、マクロブロック内のブロックの配
置処理において既配置のブロックの端子および外部端子
との接続関係と既配置のブロックおよび外部端子の配置
位置とを基にブロックの配置位置を決定することができ
、ブロックがマクロブロックの中央部に集中して配置さ
れることを有効に回避することができ、各ブロック間に
配線領域を確保することができるという効果がある。

また、マクロブロック間の配線処理についてもマクロブ
ロックの外部端子との配線経路を容易に決定でき、マク
ロブロックを展開してマクロブロック内の接続関係およ
び配置位置を参照する処理を省くことができ、処理時間
を短縮することができるという効果がある。

【図面の簡単な説明】

第１図は本発明の一実施例に係る階層的配置処理方式に
おける処理手順を示す流れ図、第２図（Ａ）は本実施例
の階層的配置処理方式によりマクロブロックの外部端子
位置を決定した状態を示す図、 第２図（Ｂ）は第２図（Ａ＞で外部端子位置の決定した
マクロブロック内にブロックを配置した結果を示す図、 第３図は従来の階層的配置処理方式によってマクロブロ
ック内にブロックを配置した結果を示す図である。 図において、 ｌ・・・・・マクロブロック、 ２〜９・・・ブロック、 １１−１５・外部端子、 ２１〜３４・端子、 ４１〜４７・入出力バンド、 ５１・・・・中心位置、 ５２・・・・重心位置、 ６１〜６５，７１．７２・接続関係、 １１０・・・中心位置計算手段、 １２０・・・重心位置計算手段、 １３０・・・外部端子位置決定手段、 １４０・・・ブロック配置手段である。

Claims (1)

1. 【特許請求の範囲】 ＬＳＩ，プリント基板等のマクロブロック内のブロック
   の配置処理を含む階層的配置処理方式において、 マクロブロックの中心位置を求める中心位置計算手段と
   、 マクロブロックの外部端子の各々と接続している他のブ
   ロックの端子あるいは入出力パッドの位置より重心位置
   を求める重心位置計算手段と、前記中心位置計算手段に
   より求められたマクロブロックの中心位置と前記重心位
   置計算手段により求められた重心位置とを結んだ直線が
   マクロブロックの周囲辺と交叉する点を外部端子位置と
   する外部端子位置決定手段と、 マクロブロック内に配置されるブロックがマクロブロッ
   クの外部端子と接続していない場合にはマクロブロック
   内の既配置のブロックの端子との接続関係と既配置のブ
   ロックの配置位置とを基にしてブロックを配置しマクロ
   ブロック内に配置されるブロックがマクロブロックの外
   部端子と接続している場合にはマクロブロック内の既配
   置のブロックの端子および外部端子との接続関係とマク
   ロブロック内の既配置のブロックおよび外部端子の配置
   位置とを基にしてブロックを配置するブロック配置手段
   と を有することを特徴とする階層的配置処理方式。