JPS63308676A - 木構造を用いたフロアプラン処理方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔概　要〕 与えられたブロック間の結線関係を基に、各枝の分岐点
がブロックの集合を表わす多分木を構成し、その木構造
の各階層を上から下へ順次並列に処理することにより、
ブロック間の結線関係を可及的に反映したフロアプラン
を高速に行う。

〔産業上の利用分野〕

本発明は、木構造を用いたフロアプラン処理方式に関す
る。

大規模集積回路ではチップ上に多数の回路が搭載される
が、どの回路をどの位置へ配設するかの決定がフロアプ
ランであり、これは回路全体を機能別に纏めて複数個の
ブロックに区分し、該ブロックを単位として配設位置を
決定する。

〔従来の技術〕

従来のフロアプランでは、与えられたそれぞれの機能ブ
ロックのＬＳＩチップ上での位置を、ブロック間の結線
関係により決定する。フロアプランを行う従来の手法と
しては、スライシングによる手法がある。これは第１４
図に示すように、与えられたブロックの集合を二つの集
合１．２に分け、さらにそれぞれの集合を３と４．５と
６の二つに分割しという二分割を進めることによってフ
ロアプランを行う手法である。この時の分割の様子は第
１５図に示すような二分木を用いて表すことができる。

この木の根Ｒはチップ、中間点（ノード）１．２．　・
・・・・・はブロックの集合、先端（葉）？、８，９．
・・・・・・はブロック（回路を機能的に纏めたもの）
に相当する。

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

上述したスライシング手法による従来のフロアプランで
は、二分木のような簡単な構造にデータを当てはめるこ
とにより、処理の高速化を図ることができる反面、構造
を簡単化するためにブロック間の結線関係を必ずしも反
映するとは限らないという欠点がある。

本発明はこの点を改善しようとするものである。

〔問題点を解決するための手段〕

本発明では、ブロック間の結線関係をできるだけ反映す
るために、ブロックの集合を２つ以上５つ以下に分割す
るという操作を繰り返し、２つ以上の分岐を許した木構
造にデータを割当てることを最初に行う。そして、次に
木構造の各階層にある分岐点に相当するデータをそれぞ
れ並列に処理することにより、高速化を図る。

第１図で説明すると、まず最初に、与えられたブロック
の集合を、ブロック間の結線関係を基に図示のような木
構造に割り当てる。この時、技の分岐は２以上５以下に
限定する。根はチップに相当し、葉はそれぞれブロック
に相当し、そして各分岐点はブロックの集合を表す、こ
＼ではチップはまずブロックの集合１，２．３に３分割
される。

次にこの木の各階層にある分岐点に相当するブロックの
集合を、それぞれ並列計算機の各プロセッサに割り当て
て並列に処理する。こ＼ではブロックの集合１はブロッ
クの集合４．５．’６に、ブロックの集合３はブロック
の集合７．８に、・・・・・・それぞれ区分される。あ
る階層ですべてのブロックの集合の処理が終ると、次に
そのすぐ下の階層のブロックの各集合をそれぞれプロセ
ッサに割り当てて同様に処理を行う、このようにして各
階層毎に並列に処理を行い、木の葉であるブロックＡ。

Ｄ、　Ｅ、・・・・・・まで階層を下っていき、フロア
プランを行う、この時、各プロセッサは自分が担当して
いるブロックの集合間の結線関係及び、自分が担当して
いるブロックの集合と他のプロセッサが担当しているブ
ロックの集合との結線関係を知っており、これらの結線
関係を基に自分の担当するブロックの位置を決定する。

〔作用〕

以上のような木構造を基に、並列処理を行なうと、ブロ
ック相互の結線関係を可及的に反映したフロアプランの
高速処理を行なうことができる。

〔実施例〕

第２図に、与えられるブロックのデータの例を示す、こ
れを元に木構造を構成した例が第３図である。この時、
各点１，２．・・・・・・、７はブロックの集合を表し
、葉のＡ、Ｂ、・・・・・・、Ｐはブロックである。各
ブロック集合に含まれる要素であるブロックは、枝をた
どることにより判る。また、これら集合間の結線関係は
第２図より判るが、特に示すと第４図のようになる。即
ち、ブロックの集合１はブロックＡ、Ｄ、Ｅ、Ｆからな
り、ブロックの集合２はブロックＧ、Ｂとブロックの集
合４からなり、該ブロックの集合４はブロックＨ，Ｋ。

Ｌからなる。またブロックの集合３はブロックの集合５
．６からなり、ブロックの集合６はブロックＣ，Ｉ、Ｍ
からなり、ブロックの集合５はブロックＯ，Ｐとブロッ
クの集合７からなり、該集合７はブロックＪ、Ｎからな
る。なおこれらのブロックの集合に対しては、他の纏め
方もある０以上までが、与えられたデータより、木構造
とブロックの位置決定に必要なデータを作成する過程を
示している。

次に第５図にブロック及び、ブロックの集合の位置を決
定する過程の例を示す、まず最初に、１つのプロセッサ
により結線関係を元にブロックの集合１．２．３の位置
関係を決定する。次に第３図に示す°ような階層ｌにあ
るブロックの集合１゜２．３をそれぞれプロセッサに割
り当て、合計３個のプロセッサを用いて同時に処理を行
う。集合■においては、ブロックＡ、Ｄ、Ｅ、Ｆの位置
を結線関係を元に決定する。この時、ブロックＡが集合
２．３と結線関係があることをプロセッサは知っていて
、Ａは図に示すような位置に置かれる。

集合２においてはブロックＢ、Ｇとブロックの集合４が
、また集合３においてはブロックの集合５゜６が同様に
処理される。さらに階Ｊｉｉ２においてブロックの集合
４．５．６がそれぞれのプロセッサにおいて処理され、
次の階層３においてブロックの集合７が処理されて、最
終結果であるフロアプランが得られる。

第６図に木構造を作成する要領を示す。これはブロック
と線のそれぞれについて重みを求める処理とこの重みを
基にブロックの集合を作成する処理からなり、各処理の
詳細を第７図と第８図に示す。また、ブロック集合の位
置決定要領を第９図に示す。

第１０図にブロック形状データを示す、ブロック形状デ
ータは、各ブロック毎に当該ブロックの面積と縦横比を
示している。また第１１図に結線データを示す。これは
各結線１．２．・・・・・・ｎ毎に、接続するブロック
の数１＋、・・・・・・と接続ブロック番号１１．１２
．・・・・・・１２１．・・・・・・を示している。

また第１２図にブロック接続関係データを示し、これは
各ブロック１，２．・・・・・・ｎ毎に接続相手のブロ
ック番号１１．１２．・・・・・・１ｎ１、その結線名
１１．１２．・・・・・・１ｎ１、及び接続相手のブロ
ック数ｎｌ、・・・・・・を示している。第１３図はブ
ロック集合データで、これは各ブロック集合毎に、その
要素名１１，１２．・・・・・・１ｅ１．・・・・・・
とその要素数ｅｌ、・・・・・・を示している。これら
のブロックデータを基に第３図の木構造を作り、第５図
のブロック集合及びブロックの配置を行なうことができ
る０例えばブロック集合１の面積は、このブロック集合
に含まれるブロックＡ、Ｄ、Ｅ、Ｆの面積の和として求
めることができ、チップ上の位置（本例では左上）は他
のブロック集合２．３に含まれるブロックとの接続関係
により決めることができる。

〔発明の効果〕

以上述べたように本発明によれば、二つ以上の分岐を許
した本構造を用いて各ブロックの位置を決定することに
より、ブロック間の結線関係を可及的に反映することが
でき、また、木構造の各階層にある点で表されたブロッ
クの集合をそれぞれ並列に処理することにより、処理の
高速化を図ることができる。

【図面の簡単な説明】

第１図は本発明の原理説明図、 第２図はブロック間の結線関係の説明図、第３図は第２
図のデータの木構造を示す図、第４図は第２図のブロッ
クの集合間の結線関係を示す図、 第５図は位置決定過程の説明図、 第６図は木構造の作成法を示すフローチャート、第７図
はブロックと線の重みの求め方を示すフローチャート、 第８図はブロックの集合の求め方を示すフローチャート
、 第９図はブロック集合の位置決定方法を示すフローチャ
ート、 第１０図はブロック形状データの説明図、第１１図は結
線データの説明図、 第１２図はブロック接続関係の説明図、第１３図はブロ
ック集合データの説明図、第１４図は従来のフロアプラ
ンの説明図、第１５図は従来の二分木の構造図である。

Claims (1)

【特許請求の範囲】
1. 与えられたブロック（Ａ、Ｄ、Ｅ、・・・・・・）間の
   結線関係を基に、各枝の分岐点がブロックの集合を表わ
   す多分木を構成し、各分岐点のブロックの集合（１、２
   、３、・・・・・・）を各階層でそれぞれ並列に処理し
   、これを多分木の根から葉側へ順に処理してフロアプラ
   ンを行うことを特徴とする木構造を用いたフロアプラン
   処理方式。