(57)【特許請求の範囲】
【請求項１】
配置領域内にブロックを配置する配置方法において、
配置領域内にブロックを配置するステップと、
上記配置した状態で重なっているブロックを抽出して当該ブロックの重なっている辺を離れる方向に所定量を移動した後、ブロック形状を、相似形状を維持したまま、面積を元に等しく戻して変形する第１のステップと、
上記面積を元に戻した状態で、ブロックが重なっているときに、当該重なるブロックの中心を結ぶ線分上で、当該ブロックの中心が相互に離れ、重なりが少なくなるように所定の移動量を算出し、当該算出した移動量で上記配置領域外にでたときは外から内の方向へブロックの中心を移動する移動量を算出する第２のステップと、
上記算出した移動量をもとに、上記配置領域内で配線長が最小となるブロックの配置を計算する第３のステップと
を設け、上記第１から第３のステップを繰り返し上記配置領域内に配線長が最小のブロックを配置する配置方法。
【請求項２】
上記算出した移動量をもとに、上記配置領域内で配線長が最小となるブロックの配置の計算として、所定の式に、重なるブロックの接続関係、移動量を代入して上記配置領域内で配線長が最小となるブロックの配置を計算する請求項１記載の配置方法。
【請求項３】
上記配置領域内で配線が混雑するブロックとブロックの間について、当該ブロックとブロックの相対する辺を近づけて間を狭くした状態で、上記第１から第３のステップを実行した後に当該辺を元に戻すことを繰り返し、配線が混雑するブロックとブロックの間を確保する請求項１あるいは請求項２記載の配置方法。
【請求項４】
配置領域内にブロックを配置する配置プログラムにおいて、
配置領域内にブロックを配置する手段と、
上記配置した状態で重なっているブロックを抽出して当該ブロックの重なっている辺を離れる方向に所定量を移動し、ブロック形状を、相似形状を維持したまま、面積を元に等しく戻して変形する第１の手段と、
上記面積を元に戻した状態で、ブロックが重なっているときに、当該重なるブロックの中心を結ぶ線分上で、当該ブロックの中心が相互に離れ、重なりが少なくなるように所定の移動量を算出し、当該算出した移動量で上記配置領域外にでたときは外から内の方向へブロックの中心を移動する移動量を算出する第２の手段と、
上記算出した移動量をもとに、上記配置領域内で配線長が最小となるブロックの配置を計算する第３の手段と
を設け、上記第１から第３の手段を繰り返し上記配置領域内に配線長が最小のブロックを配置する、ように機能させるための配置プログラム。
【請求項５】
配置領域内にブロックを配置する手段と、
上記配置した状態で重なっているブロックを抽出して当該ブロックの重なっている辺を離れる方向に所定量を移動し、ブロック形状を、相似形状を維持したまま、面積を元に等しく戻して変形する第１の手段と、
上記面積を元に戻した状態で、ブロックが重なっているときに、当該重なるブロックの中心を結ぶ線分上で、当該ブロックの中心が相互に離れ、重なりが少なくなるように所定の移動量を算出し、当該算出した移動量で上記配置領域外にでたときは外から内の方向へブロックの中心を移動する移動量を算出する第２の手段と、
上記算出した移動量をもとに、上記配置領域内で配線長が最小となるブロックの配置を計算する第３の手段と
を設け、上記第１から第３の手段を繰り返し上記配置領域内に配線長が最小のブロックを配置する、ように機能するプログラムを記録したコンピュータ読取可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、配置領域内にブロックを配置する配置方法、配置プログラムおよび記録媒体に関するものである。
【０００２】
【従来の技術】
最近の製造技術の進歩により、ＬＳＩの集積度の向上や回路の大規模化が著しく、ＬＳＩ設計をフラットに行うことが困難になってきている。この問題を解決する回路設計法の１つとして、階層化設計によるレイアウトがある。階層化設計には、まず回路をブロックと呼ばれる部分回路に分割し、次に、フロアプランと呼ばれる、ブロックの配置と形状の決定を行い、最後にブロックごとにレイアウトを行う、という設計手法である。この設計手法により、回路を小さな部分回路に分割することが可能となる。ＬＳＩ設計では、まず、論理合成で与えられた回路をセルと呼ばれる回路素子の基本単位とセル間を接続するネットとに分割し、レイアウトで回路をブロックに分割してフロアプランする。次に、ブロック内にセルを配置し、最後にセル間を接続する。
【０００３】
この際、ＬＳＩ設計では、遅延が最小となる設計方法がＬＳＩ設計者から強く求められている。その理由としては、テクノロジの微細化により配線遅延が素子遅延に比べて相対的に大きくなり、配線遅延の影響が無視できなくなっていることである。長い配線が存在すると、それによって大きな遅延が生じ、ＬＳＩのパフォーマンスが低下してしまう上、配線資源の浪費にもつながってしまう。そのため、長い配線を短くすることがハイパフォーマンスなＬＳＩ設計には重要となっている。特に、テクノロジの微細化が進んでいる今日では、フロアプランで配線遅延を最適化することが重要となっている。
【０００４】
従来のフロアプランの１手法としてＦＤ法（Force Directed法）があり、これは、配線長の２乗の和が最小となるブロック配置を求める手法である。このＦＤ法では、ブロックを点、つまり面積を０とみなしてブロック配置を行う。そのため、ブロックが重なって配置されている可能性がある。そこで、ＦＤ法では、重なったブロックが離れるように反発力を発生させ、その反発力を利用してブロックの重なりが最小のブロック配置を求めるようにしていた。
【０００５】
【発明が解決しようとする課題】
このため、従来の上述のＦＤ法では、下記の問題などがある。
（１）  ブロックが配置領域の外に出てしまう可能性がある。
【０００６】
（２）  あるブロックが配置領域の枠に接している固定ブロックや禁止領域にと重なっている場合、配置領域の外に出てしまう可能性がある。
（３）  隣接するブロックが同じブロックは、初期配置で同じ座標に配置されると、以降同じ反発力が発生し、その結果、同じ座標へ配置されてしまう可能性がある。
【０００７】
（４）  配線長のみの最適化を行うために、ブロックの形状の最適化が行われない。
（５）  ブロック間を接続するネットは、ブロックが配置されていない領域に配線されるため、配線が混雑している領域では全ての配線ができない可能性がある。
【０００８】
本発明は、これらの問題を解決するため、ＬＳＩの階層化設計のフロアプランにおいて、配線長が最小となるように、ブロックの形状と配置を自動決定することを目的としている。
【０００９】
【課題を解決するための手段】
図１を参照して課題を解決するための手段を説明する。
図１において、処理装置１は、配置領域内のブロックの配線長を最小かつブロックが重ならないように配置するものであって、ここでは、ブロック配置手段２、ブロック形状計算手段３、反発力計算手段４、およびブロック再配置手段５などから構成されるものである。
【００１０】
ブロック配置手段２は、配置領域内に配線長が最小となるようにブロック（ブロックの中心）を配置するものである。
ブロック形状計算手段３は、重なっているブロックを抽出してブロックの辺を離れる方向に所定量を移動した後、面積を元に等しく戻したりなどすものである。
【００１１】
反発力計算手段４は、ブロックが重なっているときに重なりが少なくなる方向にブロックの中心を移動する所定の移動量を算出したり、算出した移動量で配置領域外にでたときは外から内の方向へブロックの中心を移動する移動量を算出したりなどするものである。
【００１２】
ブロック再配置手段５は、移動量をもとに、配置領域内で配線長が最小となるブロックの配置を計算したりなどするものである。
次に、動作を説明する。
【００１３】
処理装置１を構成するブロック配置手段２が配置領域内に配線長が最小となる位置にブロック（ブロックの中心）を配置し、ブロック形状計算手段３が配置した状態で重なっているブロックを抽出して当該ブロックの重なっている辺を離れる方向に所定量を移動した後、面積を元に等しく戻して形状を変形し、反発力計算手段４が更にブロックが重なっているときに重なりが少なくなる方向にブロックの中心を移動する所定の移動量を算出し、算出した移動量で配置領域外にでたときは外から内の方向へブロックの中心を移動する移動量を算出し、ブロック再配置手段５が算出した移動量をもとに配置領域内で配線長が最小となるブロックの配置を計算することを繰り返し、配置領域内に配線長が最小のブロックを配置するようにしている。
【００１４】
この際、面積を元に等しく戻してとして、面積を相似形で元に等しく戻すようにしている。
また、面積をもとに戻した状態で、ブロックが重なっているときに重なりが少なくなる方向に当該ブロックの中心を移動として、重なるブロックの中心を結ぶ線分上で相互に離れるように所定の移動量を算出したり、あるいはブロックの中心の移動によって配置領域外にでたときは内の方向の移動量を算出したり、あるいは配置領域の辺に斜めに外にでたときは反射する内の方向に移動量を算出したりするようにしている。
【００１５】
従って、ＬＳＩの階層化設計のフロアプランにおいて、配線長が最小となるように、ブロックの形状と配置を自動決定することが可能となる。
【００１６】
【発明の実施の形態】
次に、図１から図１４を用いて本発明の実施の形態および動作を順次詳細に説明する。
【００１７】
図１は、本発明のシステム構成図を示す。
図１において、処理装置１は、プログラムに従い各種処理を実行するものであって、ここでは、ブロック配置手段２、ブロック形状計算手段３、反発力計算手段４、およびブロック再配置手段５などから構成されるものである。
【００１８】
ブロック配置手段２は、配置領域内に配線長が最小となるようにブロック（ブロックの中心）を配置するものである。
ブロック形状計算手段３は、配置領域内で重なっているブロックを抽出してブロックの重なっている辺を離れる方向に所定量を移動した後、相似形で面積を元に等しく戻すものである。これにより、ブロックの形状が重なりが少なくなる方向に徐々に変形されることとなる。
【００１９】
反発力計算手段４は、ブロック形状計算手段３によってブロックの形状を変えてもまだブロックが重なっているときに、重なりが少なくなる方向にブロックの中心を移動させる所定の移動量を算出したり、算出した移動量でブロックが配置領域外にでたときは外から内の方向へブロックの中心を移動する移動量を算出したりなどするものである。これにより、ブロックの中心を重なりが少なくなる方向に徐々に移動させることとなる。
【００２０】
ブロック再配置手段５は、反発力計算手段４によって計算されたブロックの中心の移動量などをもとに、配置領域内で配線長が最小となるブロックの配置を計算するものである。そして、ブロック形状計算手段３、反発力計算手段４および当該ブロック再配置手段５の処理を順番に繰り返すことにより（後述する図２参照）、配置領域内でブロックの形状を変形、ブロックの中心を移動して重なりのなくかつ配線長の最小のブロックの配置を計算して決定することが可能となる。
【００２１】
表示装置６は、各種データや計算結果などを表示するものである。
入力装置７は、データや各種指示を入力するものであって、マウスやキーボードなどである。
【００２２】
データベース８は、各種データを検索し易く格納したものであって、ここでは、配置領域、各ブロックなどの情報や配置結果などを格納するものである。
次に、図２のフローチャートに順番に従い、図１の構成の全体の動作を詳細に説明する。
【００２３】
図２は、本発明の動作説明フローチャート（全体）を示す。
図２において、Ｓ１は、配線長が最小のブロック配置を計算する。これは、指定された配置領域内に、指定されたブロック（サイズ、結線情報）を配線長が最小となるブロックの位置を計算する。この際、ブロックは中心の座標で表し、サイズは零（あるいは小さな所定サイズ）と仮定して配線長が最小となるブロック位置を計算する。
【００２４】
Ｓ２は、ブロック形状を計算する。これは、後述する図３のフローチャートを用いて詳述するように、Ｓ１あるいはＳ４で配置領域内に配線長が最小となるように配置されたブロック（第１回目はＳ１、第２回目以降はＳ４）について、ブロックの形状をもとに重なっているブロックを抽出し、抽出した重なっているブロックの辺を重なりが少なくなる方向に移動させた後、相似形で元の面積と同じブロックの形状に変形する。同様に、全ての重なっているブロックについて繰り返す。
【００２５】
Ｓ３は、反発力を計算する。これは、後述する図５のフローチャートを用いて詳述するように、Ｓ２でブロック形状の計算結果をもとに、重なっているブロックを全て抽出し、重なっているブロックが離れる方向に当該ブロックの中心を移動させ、移動後に配置領域のそとにでたときは内方向の移動量を計算などする。同様に、全ての重なるブロックについて繰り返す。
【００２６】
Ｓ４は、反発力をもとにした配線長が最小のブロック配置を計算する。これは、後述する図７のフローチャートを用いて詳述するように、ブロック配置計算式にＳ３の結果を代入して配線長が最小となるブロック配置を計算する。そして、所定回数（例えば１００回）繰り返すまでＳ２に戻り繰り返す。
【００２７】
また、Ｓ１１、Ｓ１２は、Ｓ２のときに、Ｓ１あるいはＳ４で配線長が最小となるブロック位置をそのまま取り込んでブロック形状計算を行うのではなく、ブロック間に配線が混雑した場合に、図９の（ｂ）に示すように、当該ブロックの面積を大きくして両ブロックの間隔を狭くして既述したＳ２、Ｓ３、Ｓ４の計算を行い、計算後に両ブロックの間隔を元に戻して、当該両ブロックの間隔を広く確保し、配線が可能にするための操作である。
【００２８】
Ｓ５は、Ｓ２、Ｓ３、Ｓ４を所定回数繰り返し（例えば１００回）たか判別する。ＹＥＳの場合には、終了し、Ｓ３の結果を出力する。一方、ＮＯの場合には、Ｓ２に戻り繰り返す。
【００２９】
以上によって、配置領域に配線長が最小となるブロック配置を行い（Ｓ１）、重なるブロックについて重なりが少なくなる方向に形状変更を行い（Ｓ２）、更に重なるときにブロックの中心を重なりが少なくなる方向に移動し（Ｓ３）、これら結果をもとに配線長が最小となるブロック再配置を行うことを繰り返すことにより、配置領域内に重なりがなくなるように、あるいは重なりが少なくなるようにブロック配置を自動的に行うことが可能となる。以下順次詳細に説明する。
【００３０】
図３は、本発明の動作説明フローチャート（Ｓ２）を示す。これは、既述した図２のＳ２の詳細フローチャートであって、配置領域内で重なるブロックの形状を重なりが少なくなる方向に変形して面積を等しくするものである。
【００３１】
図３において、Ｓ２１は、重なっているブロックを抽出する。これは、配線長が最小となるブロック位置にあるブロックについて、配置領域内で重なっているブロックを全て抽出する。
【００３２】
Ｓ２２は、辺を中心に向かって重なりが少なくなるように移動する。これは、例えば後述する図４の（ａ）の斜線を引いたＡ（ｉ、ｊ）の部分が少なくなるように、図４の（ｂ）の辺を矢印で示す中心に向かって重なりが少なくなる方向に移動させ、図４の（ｃ）に示すようにする。
【００３３】
Ｓ２３は、面積を最初と等しくする。これは、相似形で面積を最初と等しく、かつ中心を合わせて相似形で移動（元のブロックの中心間の距離Ｌ０は変えないで）する。
【００３４】
以上によって、配置領域内で重なっているブロックは重なりが少なくなる方向に形状が変形されることとなる（例えば図４の（ａ）のブロックが図４の（ｄ）のブロックのように中心間距離を等しくして重なりが無くなるように面積を最初と等しくして変形されることとなる）。
【００３５】
図４は、本発明の説明図（Ｓ２）を示す。
図４の（ａ）は、配置領域内のブロックの重なりの状態を示す（図３のＳ２１）。この状態では、図示のように、ブロックの斜線の部分が重なっている。
【００３６】
図４の（ｂ）は、矢印でブロックの辺を重なりが少なくなる移動方向を示す。
図４の（ｃ）は、ブロックの辺を重なりが少なくなる方向に移動した後の状態を示す。
【００３７】
図４の（ｄ）は、図４の（ｃ）の状態で、相似形で面積を等しく拡大した後の状態を示す。図示の状態では、ブロックが重なりがなくなるように面積を等しくして変形されたこととなる（ブロックの中心間の距離Ｌ０は、図４の（ａ）の最小の距離Ｌ０と等しい）。
【００３８】
以上のように、配置領域内で重なっているブロックを抽出し、ブロックの辺を重なりが少なくなる方向に移動させた後、相似形で元の面積に戻してブロックの形状を重なりが少なくなる形状に変形することにより、ブロック間の距離を同じにしてブロック間の重なりをなくす、あるいは少なくすることが可能となる。
【００３９】
次に、図４の（ａ），（ｂ），（ｃ），（ｄ）および図中の記号を用いて数式的に図示のようにして重なりが無くなる、あるいは少なくなる方向に形状を変形するコンピュータシステムを利用した数式処理について詳細に説明する。
【００４０】
（１）  図４の（ａ）に示すように、ブロックｉ，ｊが重なっている時、ブロックｉ、ｊのＸ方向の重なりＸ（ｉ，ｊ），Ｙ方向の重なりＹ（ｉ，ｊ）、重なりの面積Ａ（ｉ，ｊ）を下式でそれぞれ求める。
【００４１】
X(i,j)=max(min(xi+wi/2, xj+wj/2)-max(xi-wi/2,xj-wj/2),0)
Y(i,j)=max(min(yi+hi/2, yj+hj/2)-max(yi-hi/2,yj-hj/2),0)
A(i,j)=X(i,j)・Y(i,j)
ここで
・(xi,yi)はブロックｉの中心座標
・wiはブロックｉの幅
・hiはブロックｉの高さ
をそれぞれ表す。
【００４２】
（２）  図４の（ｂ）に示すように、ｊが占める領域との重なりを持つｉの辺を、ブロックの中心に向かって移動する。ｊとの重なりによるｉの右辺、左辺、上辺、下辺の移動量をそれぞれＭｒ（ｊ−ｉ），Ｍｌ（ｊ−ｉ），Ｍｔ（ｊ−ｉ），Ｍｂ（ｊ−ｉ）とし、下式でそれぞれ求める。ここで、Ａ（ｉ，ｊ）はブロックｉとブロックｊとが重なった領域の面積を表し、αは定数である。
【００４３】
Mr(j-i)=α・A(i,j)(wi/(wihi+wjhj))
Ml(j-i)=α・A(i,j)(wi/(wihi+wjhj))
Mt(j-i)=α・A(i,j)(hi/(wihi+wjhj))
Mb(j-i)=α・A(i,j)(hi/(wihi+wjhj))
全てのブロックとの重なりを調べて、ｉの各辺の移動量Ｍｒ（ｉ），Ｍｌ（ｉ），Ｍｔ（ｉ），Ｍｂ（ｉ）を決定する。
【００４４】
0003953740.tif 000002
ここで、Aiは自身以外の全てを表す。
【００４５】
（３）  図４の（ｃ）に示すように、次に、辺を移動したブロックを拡大する。辺の移動により、ブロック幅はｗｉからｗｉ−Ｍｒ（ｉ）−Ｍｌ（ｉ）へ、高さはｈｉからｈｉ−Ｍｔ（ｉ）−Ｍｂ（ｉ）へと変わっている。ブロックの面積を維持するため、ｉの高さと幅を
(wihi/((wi-Mr(i)-Ml(i))(hi-Mt(i)-Mb(i)))1/2倍
し、整理して変更後の幅ｗｉ’，高さｈｉ’として下式を得る(図４の（ｄ））。
【００４６】
wi'=((wi-Mr(i)-Ml(i))w(i)h(i)/(hi-Mt(i)-Mb(i)))1/2
hi'=((hi-Mt(i)-Mb(i))w(i)h(i)/(wi-Mr(i)-Ml(i)))1/2
以上の式および手順によって、重なっているブロックの重なりを無くすあるいは重なりを少なくする方向に辺を移動した後、面積を相似形で元の面積と等しくすることをコンピュータシステムを利用して計算することが可能となる。
【００４７】
図５および図６は、本発明の説明図（Ｓ３）を示す。これらは、既述した図２のＳ３の詳細説明図であって、反発力を計算するものである。
図５の（ａ）は、フローチャートを示す。
【００４８】
図５の（ａ）において、Ｓ３１は、ブロック形状計算結果を取り込む。これは、既述した図３のＳ２３の計算結果（上述した図４の（ｄ）の計算結果）を取り込む。即ち、重なるブロックについて、ブロックの中心を移動させないで、辺を重なりが少なくなる方向に移動した後に相似形で元の面積と等しくしたときの計算結果を取り込む。
【００４９】
Ｓ３２は、ブロックの中心が離れる方向へ重なりが少なくなる移動量（方向と距離）を計算する。これは、例えば後述する図５の（ｂ）の矢印に示すように、重なるブロックの中心が離れる方向へ重なりが少なくなる移動量（方向と距離）を計算する。
【００５０】
Ｓ３３は、ブロックが配置領域から出ているか判別する。ＹＥＳの場合には、Ｓ３４で、配置領域の外から中への移動量を計算する(例えば後述する図６の（ｃ）の左側のブロックの矢印で示すような移動量を計算する）。一方、ＮＯの場合には、終了する。
【００５１】
以上によって、重なるブロックについて、ブロックの中心が離れる方向に移動量（方向と距離）を計算することが可能となる。この際、移動して配置領域の外に出た場合には、配置領域の中に戻るように例えば図６の（ｃ），（ｄ）の矢印で示す移動量を計算することが可能となる。
【００５２】
図５の（ｂ）は、中心を移動させるための反発力の計算方法の説明図を示す。ブロックが図示のように重なっていた場合には、ブロックの中心を結ぶ線分上で、重なりが少なくなるように離れる方向に図示の矢印の移動量を計算で求める。
【００５３】
図６の（ｃ）は、移動した結果、ブロックが配置領域の外に出た場合の移動量の算出の例を示す。左側のブロックは、配置領域の左の辺から外に一部が出てしまったので、配置領域の中に戻る図示矢印の方向の移動量を計算する。また、右上のブロックは、左と下の両方向に移動しないと配置領域の中に戻らないので、図示の矢印の合成の方向の移動量を計算する。
【００５４】
図６の（ｄ−１）は、配置領域の辺に接している禁止領域／固定ブロック内にブロックが入ってしまった場合を示す。
図６の（ｄ−２）は、図６の（ｄ−１）の状態の場合には、禁止領域／固定ブロックの中心を配置領域の辺に仮中心として移動し、当該禁止領域／固定ブロックの外かつ配置領域の中に戻す方向に移動量を計算する。
【００５５】
以上の図５の（ｂ）、図６の（ｃ）、（ｄ）のように、配置領域外に出た場合あるいは禁止領域／固定ブロック内に入ってしまったときに、配置領域の中あるいは配置領域の中かつ禁止領域／固定ブロック外に戻るように移動量を計算することが可能となる。
【００５６】
図７および図８は、本発明の説明図（Ｓ４）を示す。これは、既述した図２のＳ４の反発力を元にした配線長が最小のブロック配置を計算する説明である。
図７の（ａ）は、フローチャートを示す。
【００５７】
図７の（ａ）において、Ｓ４１は、ブロック配置計算式にＣとｄを設定する。これは、配線長が最小のブロック位置を計算するための、後述する図８の計算式中のＣとｄに、重なるブロックの接続関係をそれぞれ設定する。
【００５８】
Ｓ４２は、Ｓ３の結果の取り込みを行う。これは、既述した図２のＳ３の結果（重なるブロックの中心を重なりが少なくなる方向への移動量）の取り込みを行う。
【００５９】
Ｓ４３は、移動量をｅに設定する。これは、Ｓ４２で取り込んだ重なるブロックの中心の移動量ｅを、後述する図８の計算式中のｅ（移動量）に設定する。
Ｓ４４は、配線長が最小となるブロック配置計算式を解いてｐを求める。これは、Ｓ４１、Ｓ４３で後述する図８のブロック配置計算式にＣ，ｄ，ｅをそれぞれ設定し、解いてｐ（ブロック位置あるいはブロックの中心座標）を求める。この際、配線長はデータベース８内に蓄積されているデータを使って計算する。
【００６０】
以上によって、既述したＳ３の重なるブロックの中心を重なりが少なくなる方向への移動量をもとに配線長が最小となるブロック配置を計算することが可能となる。
【００６１】
図７の（ｂ）は、配置領域内にブロック＃１、＃２、＃３の３つと、固定ブロックが１つある場合の例を示す。この場合の配線長が最小となるブロック配置を解く行列式は、後述する図８のように表記される。
【００６２】
図８は、図７の（ｂ）のブロック＃１、＃２．＃３の３つと、固定ブロックが１つある場合の配線長が最小となるブロック位置を計算する式の行列による表現の例を示す。ここでは、Ｃ、ｄ（接続関係）は既述した図７の（ａ）のＳ４１で設定し、ｅ（移動量、既述した図２のＳ３で求めた移動量）は既述した図７の（ａ）のＳ４３で設定し、解であるｐ（座標）は既述した図７の（ａ）のＳ４４で求めるものである。
【００６３】
ここで、移動量ｅには、図示の下記のものがある。
（１）ブロック同士による移動量（例えば既述した図５の（ｂ）の矢印の移動量）
（２）配置領域の外から中への移動量（例えば既述した図６の（ｃ）の矢印の移動量）
（３）同じ座標のブロックによる移動量（例えばブロックが複数重なったときに異なる位置に配置するための移動量）
図９は、本発明の説明図を示す。これは、配線が混雑している領域のブロック間について、ブロックの面積を拡大してブロック間を狭くして、既述した図２のＳ２からＳ４の処理を実行した後にブロックの面積を元に戻してブロック間を広げて確保し、配線が確実に配置可能にするための処理であって、既述した図２のＳ１１とＳ１２の処理を説明するものである。
【００６４】
図９の（ａ）は、配置領域内で配線が混雑した領域（楕円で示す領域）の例を示す。
図９の（ｂ）は、図９の（ａ）の楕円で示す領域に面するブロック間の辺を近づけて狭くした状態を示す。この状態は、既述した図２のＳ１１でブロックの面積を拡大した例に対応し、ブロック間の間隔が狭くなっている。この状態で、既述した図２のＳ２、Ｓ３、Ｓ４の処理を実行した後に、Ｓ１２で元の図９の（ａ）の状態のブロックに戻して配線領域を広く確保することが可能となる。
【００６５】
図１０は、本発明の説明図（Ｓ２）を示す。これは、既述した図２のＳ２の他の実施例の動作の説明図である。
図１０の（ａ）は、フローチャートを示す。
【００６６】
図１０の（ａ）において、Ｓ５１は、重なっているブロックを抽出する。これは、配置領域内で重なっているブロックを抽出する。
Ｓ５２は、同じ種類のブロックが存在するか判別する。ＹＥＳの場合には、同じ種類のブロック（例えば形状が同じブロック）が複数個存在すると判明したので、Ｓ５３、Ｓ５４のブロックの辺の移動や面積を元に戻す処理をスキップし、当該ブロックの形状を変えないでそのままにしておく。一方、ＮＯの場合には、同じ種類のブロックが存在しないと判明したので、Ｓ５３で既述したように重なっているブロックの辺を中心に向かって重なりが少なくなるように移動し（図１０の（ｂ）参照）、Ｓ５４で面積を最初と等しくする。
【００６７】
以上によって、配置領域内で重なっている同じ種類のブロックは形状が変形されることなくそのままとし、重なりの相手のブロックの辺についてのみ重なりが少なくなるように移動した後、元の面積に相似形で戻すことにより、同じ種類のブロックをそのままのこし当該ブロックの内部配置の処理を削減することが可能となる。
【００６８】
図１０の（ｂ）は、種類が同じブロックｉ，ｊの形状を不変とした例を示す。図示のように、配置領域内で重なるブロックのうち、形状が同じブロックｉ，ｊについて図１０の（ａ）のＳ５３の辺の移動およびＳ５４の面積を最初と等しくしてブロックの形状を重なりが少なくなるように変形する処理をスキップし、重なっている相手のブロックのみＳ５３、Ｓ５４の処理を行い当該ブロックの形状の変形を行い重なりを少なくなるようにする。これにより、同じ種類のブロックをそのまま残し、同じ種類のブロック内の配置処理を迅速に行うことが可能となる。
【００６９】
図１１は、本発明の説明図（Ｓ２）を示す。これは、既述した図２のＳ２の他の実施例の動作の説明図である。
図１１の（ａ）は、フローチャートを示す。
【００７０】
図１１の（ａ）において、Ｓ６１は、重なっているブロックを抽出する。これは、配置領域内で重なっているブロックを抽出する。
Ｓ６２は、同じ種類の全てのブロックの辺を、中心に向かって重なりが少なくなるように移動する。これは、後述する図１１の（ｂ）に示すように、重なっている種類が同じブロックｉ，ｊについて、全て同一に辺を中心に向かって重なりが少なくなるように移動する（種類が同じブロックｉ、ｊでそれぞれ移動が異なるときは全てのブロックで最適な移動を行う（例えば全ての移動量をマージした移動を行う））。
【００７１】
Ｓ６３は、面積を最初と等しくする。
以上によって、配置領域内で重なっている同じ種類のブロックは全て同一の辺について同一の移動をした後、元の面積に相似形で戻すことにより、同じ種類のブロックは全て同じ変形処理を施して変形後の全て同じ形状とし、各ブロックの内部配置の処理を削減することが可能となる。
【００７２】
図１１の（ｂ）は、種類が同じブロックｉ，ｊの形状変形を同じとした例を示す。図示のように、配置領域内で重なるブロックのうち、形状が同じブロックｉ，ｊについて図１１の（ａ）のＳ６２の全て同じ辺の移動およびＳ６３の面積を最初と等しくしてブロックの形状を重なりが少なくなるように全て同じ変形する処理を行うことにより、同じ種類のブロックを全て同じ変形を施して同じ形状とすることにより、当該同じ種類のブロック内の配置処理を迅速に行うことが可能となる。
【００７３】
図１２および図１３は、本発明の説明図（Ｓ４）を示す。これらは、図１３の配置領域内のブロック＃１、＃２間の接続の強さを変更した例を示す。
図１２の（ａ）は、既述したブロック配置計算式の例を示す。このブロック配置計算式は、後述する図１３の（ａ）の配置領域内にブロック＃１、＃２、＃３の３つのブロックを配置し、配線長を最小とする各ブロックの中心（座標ｐ）を解く式である。
【００７４】
図１２の（ｂ）は、図１３の(ｂ)に示すブロック＃１，＃２の接続を変更したときに接続関係ｃを変更して設定した例を示す。ここでは、接続関係ｃのうちの、図中の
・Ｕ’の１箇所
・Ｖ’の２箇所
について、Ｕ，Ｖからそれぞれ変更する。変更した後のブロック配置計算式を解いて座標ｐ（ｘ１，ｘ２，ｘ３）を求めると、ブロック＃１、＃２、＃３のそれぞれの中心座標を求めることが可能となる。尚、他の値の設定は、既述した図８のブロック配置計算式および図７の（ａ）のフローチャートを参照。
【００７５】
図１３の（ａ）は、配置領域内にブロック＃１、＃２、＃３を配置し、ブロック＃１とブロック＃２が重なっている様子を示す。
図１３の（ｂ）は、既述した図１２の（ｂ）で接続関係ｃ中でＵ，ＶをＵ’，Ｖ’にブロック＃１、＃２の中心の移動に対応した値を設定し、解いてその座標ｐ（ｘ１，ｘ２，ｘ３）を求めた様子を示す。
【００７６】
以上のように、配置領域内で重なっているブロックの中心を移動した場合に、図１２の(ｂ)に示すようにブロック配置計算式中の該当パラメタを変更して解くことにより、重なりが少なくなる方向にブロックを移動した後の配線長を制約として与えられた値以下とするブロックの位置を再計算することが可能となる。
【００７７】
図１４は、本発明の説明図を示す。これは、ブロックｉとブロックｊの間にブロック以外の例えばセルが存在する場合に、本願発明を適用できるようにするための前処理の例を示す。
【００７８】
図１４の（ａ）、（ｂ）は、フローチャートを示す。
図１４の（ａ）、（ｂ）において、Ｓ７１は、ブロックを抽出する。これは、配置領域内に配置する全てのブロックを抽出する。
【００７９】
Ｓ７２は、図１４の（ｂ）のＳ８１からＳ８５を実行する。
Ｓ８１は、隣接するセルまたはブロックを抽出する。これは、例えば後述する図１４の（ｃ）に示すようなブロック−セル−セル−ブロックが接続されてた場合に、これらを順次抽出する。
【００８０】
Ｓ８２は、抽出したのはブロックか判別する。ＹＥＳの場合には、Ｓ８３でリストに追加し、Ｓ８４に進む。一方、ＮＯの場合には、Ｓ８５で再帰的にＳ８１、Ｓ８２を実行し、ブロックが抽出されるまでセルの先を順次繰り返し辿り、ブロックが抽出されたときにＳ８２のＹＥＳとなり、Ｓ８４に進む。
【００８１】
Ｓ８４は、隣接するセルまたはブロックをすべて抽出済みか判別する。ＹＥＳの場合には、復帰してＳ７２に戻り、次のＳ７３に進む。一方、ＮＯの場合には、Ｓ８１に戻り、次のブロックあるいはセルの抽出、Ｓ８２などを繰り返す。
【００８２】
以上のＳ８１からＳ８４によって、配置領域内のブロックのみがリストに追加され、セルは削除されることとなる。
Ｓ７３は、リスト中のすべてのブロックの組に対してネットを生成する。これにより、配置領域内のブロックのみを抽出(セルを削除）して後述する図１４の(ｃ)に示すようなセルを削除してスキップしたブロックのネットが作成されることとなる。そして、既述した図１から図１３によってブロックの形状変更（図２のＳ２）、ブロックの中心移動（図２のＳ３）、および配線長が最小のブロック配置を計算して決定（図２のＳ４）し、その後にセルを戻して配線長が最小のブロック配置およびセル配置することが可能となる。
【００８３】
図１４の（ｃ）は、配置領域内にブロックとセルが接続されている例を示す。
図１４の（ｄ）は、セルを削除した例を示す。これは、図１４の（ｃ）のブロックとセルが接続された状態で、図１４の（ａ）および（ｂ）のフローチャートにより、セルを削除したブロックｉ，ｊのリストを作成し、これらリスト中のブロックｉ，ｊについて、既述した図１から図１３の処理を実行することで、ブロック間にセルがあっても本願発明が適用できるようにしたものである。そして、本願発明を適用して配線長を最小にして重なりを無くしあるいは重なりを少なくしたブロックにセルを元の位置に戻して配置領域内にブロックとセルの混合した配置を実現できるようにしたものである。
【００８４】
（付記１）
配置領域内にブロックを配置する配置方法において、
配置領域内にブロックを配置するステップと、
上記配置した状態で重なっているブロックを抽出して当該ブロックの重なっている辺を離れる方向に所定量を移動した後、面積を元に等しく戻して形状を変形する第１のステップと、
上記面積をもとに戻した状態で、ブロックが重なっているときに重なりが少なくなる方向に当該ブロックの中心を移動する所定の移動量を算出し、当該算出した移動量で上記配置領域外にでたときは外から内の方向へブロックの中心を移動する移動量を算出する第２のステップと、
上記算出した移動量をもとに、上記配置領域内で配線長が最小となるブロックの配置を計算する第３のステップと
を設け、上記第１から第３のステップを繰り返し上記配置領域内に配線長が最小のブロックを配置する配置方法。
【００８５】
（付記２）
上記面積を元に等しく戻してとして、面積を相似形で元に等しく戻した請求項１記載の配置方法。
【００８６】
（付記３）
上記面積をもとに戻した状態で、ブロックが重なっているときに重なりが少なくなる方向に当該ブロックの中心を移動として、当該重なるブロックの中心を結ぶ線分上で相互に離れるように所定の移動量を算出、あるいはブロックの中心の移動によって上記配置領域外にでたときは内の方向に移動、あるいは上記配置領域の辺に斜めに外にでたときは反射する内の方向に移動する請求項１記載の配置方法。
【００８７】
（付記４）
上記算出した移動量をもとに、上記配置領域内で配線長が最小となるブロックの配置の計算として、所定の式に、重なるブロックの接続関係、移動量を代入して上記配置領域内で配線長が最小となるブロックの配置を計算する請求項１記載の配置方法。
【００８８】
（付記５）
上記配置領域内で配線が混雑するブロックとブロックの間について、当該ブロックとブロックの相対する辺を近づけて間を狭くした状態で、上記第１から第３のステップを実行した後に当該辺を元に戻すことを繰り返し、配線が混雑するブロックとブロックの間を確保する請求項１から請求項４のいずれかに記載の配置方法。
【００８９】
（付記６）
上記配置領域内に種類が同一のブロックが存在する場合に、両ブロックの形状を不変とし、ブロック内の配置処理を削減する請求項１から請求項５のいずれかに記載の配置方法。
【００９０】
（付記７）
上記配置領域内に種類が同一のブロックが存在する場合に、両ブロックの形状の変形を同一とし、ブロック内の配置処理を削減する請求項１から請求項５のいずれかに記載の配置方法。
【００９１】
（付記８）
ブロックとブロックの間にセルが存在する場合に、間に存在するセルを除去して上記第１から第３のステップを繰り返して処理を終了した後に、削除したセルを付加して戻す請求項１から請求項７のいずれかに記載の配置方法。
【００９２】
（付記９）
配置領域内にブロックを配置する配置プログラムにおいて、
配置領域内にブロックを配置する手段と、
上記配置した状態で重なっているブロックを抽出して当該ブロックの重なっている辺を離れる方向に所定量を移動した後、面積を元に等しく戻して形状を変形する第１の手段と、
上記面積をもとに戻した状態で、ブロックが重なっているときに重なりが少なくなる方向に当該ブロックの中心を移動する所定の移動量を算出し、当該算出した移動量で上記配置領域外にでたときは外から内の方向へブロックの中心を移動する移動量を算出する第２の手段と、
上記算出した移動量をもとに、上記配置領域内で配線長が最小となるブロックの配置を計算する第３の手段と
を設け、上記第１から第３の手段を繰り返し上記配置領域内に配線長が最小のブロックを配置する、ように機能させるための配置プログラム。
【００９３】
（付記１０）
配置領域内にブロックを配置する手段と、
上記配置した状態で重なっているブロックを抽出して当該ブロックの重なっている辺を離れる方向に所定量を移動した後、面積を元に等しく戻して形状を変形する第１の手段と、
上記面積をもとに戻した状態で、ブロックが重なっているときに重なりが少なくなる方向に当該ブロックの中心を移動する所定の移動量を算出し、当該算出した移動量で上記配置領域外にでたときは外から内の方向へブロックの中心を移動する移動量を算出する第２の手段と、
上記算出した移動量をもとに、上記配置領域内で配線長が最小となるブロックの配置を計算する第３の手段と
を設け、上記第１から第３の手段を繰り返し上記配置領域内に配線長が最小のブロックを配置する、ように機能するプログラムを記録したコンピュータ読取可能な記録媒体。
【００９４】
（付記１１）
配置領域内にブロックを配置する配置装置において、
配置領域内にブロックを配置する手段と、
上記配置した状態で重なっているブロックを抽出して当該ブロックの重なっている辺を離れる方向に所定量を移動した後、面積を元に等しく戻して形状を変形する第１の手段と、
上記面積をもとに戻した状態で、ブロックが重なっているときに重なりが少なくなる方向に当該ブロックの中心を移動する所定の移動量を算出し、当該算出した移動量で上記配置領域外にでたときは外から内の方向へブロックの中心を移動する移動量を算出する第２の手段と、
上記算出した移動量をもとに、上記配置領域内で配線長が最小となるブロックの配置を計算する第３の手段と
を設け、上記第１から第３の手段を繰り返し上記配置領域内に配線長が最小のブロックを配置することを特徴とする配置装置。
【００９５】
【発明の効果】
以上説明したように、本発明によれば、配置領域内で重なっているブロックを抽出して重なりが少なくなる方向にブロックの辺を移動して元の面積に戻すおよびブロックの重なりが少なくなる方向にブロックの中心を移動させた後、配線長を最小とするブロックの配置を再計算することを繰り返す構成を採用しているため、ＬＳＩの階層化設計のフロアプランにおいて、配線長が最小となるように、ブロックの形状と配置を自動決定することが可能となる。これらにより、
（１）配置領域内で重なりのないブロックの配置をコンピュータを使って決定することが可能となる。
【００９６】
（２）得られるブロック配置は配置領域の内側に収まっており、他のブロックや禁止領域との重なりをなくすことができる。
（３）  ブロック形状が可変の場合、最適なブロックの形状を得ることができる。
【００９７】
（４）ブロック形状が同じ種類の場合には、配置領域内で形状変化させないか、あるいは変化されても同じ形状に変化させることにより、同じブロック形状を保持させて当該同じブロック内の素子などの配置を簡易にすることができる。
【００９８】
（５）配置領域内にブロック以外にセルが混在しても、ブロックのみを抽出してブロック形状および位置を最適に配置した後に、セルを元の位置に配置し、セルがブロック内に散在しても本願発明を適用することができる。
【図面の簡単な説明】
【図１】本発明のシステム構成図である。
【図２】本発明の動作説明フローチャート（全体）である。
【図３】本発明の動作説明フローチャート（Ｓ２）である。
【図４】本発明の説明図（Ｓ２）である。
【図５】本発明の説明図（Ｓ３）である。
【図６】本発明の説明図（Ｓ３）である。
【図７】本発明の説明図（Ｓ４）である。
【図８】本発明の説明図（Ｓ４）である。
【図９】本発明の説明図である。
【図１０】本発明の説明図（Ｓ２）である。
【図１１】本発明の説明図（Ｓ２）である。
【図１２】本発明の説明図（Ｓ４）である。
【図１３】本発明の説明図（Ｓ４）である。
【図１４】本発明の説明図である。
【符号の説明】
１：処理装置
２：ブロック配置手段
３：ブロック形状計算手段
４：反発力計算手段
５：ブロック再配置手段
６：表示装置
７：入力装置
８：データベース
【図１】
0003953740.tif 000003
【図２】
0003953740.tif 000004
【図３】
0003953740.tif 000005
【図４】
0003953740.tif 000006
【図５】
0003953740.tif 000007
【図６】
0003953740.tif 000008
【図７】
0003953740.tif 000009
【図８】
0003953740.tif 000010
【図９】
0003953740.tif 000011
【図１０】
0003953740.tif 000012
【図１１】
0003953740.tif 000013
【図１２】
0003953740.tif 000014
【図１３】
0003953740.tif 000015
【図１４】
0003953740.tif 000016