(57)【特許請求の範囲】
【請求項１】
第１のブロック変形部とブロック位置決定部と配線混雑度算定部と第２のブロック変形部とを備えるフロアプラン生成装置によって集積回路のフロアプランを生成する集積回路のフロアプラン生成方法であって、
前記第１のブロック変形部が、ブロックの配置をおこなうフロアプラン領域内に配置されたブロック形状の変形をおこなう第１のブロック変形工程と、
前記ブロック位置決定部が、前記第１のブロック変形工程に基いて変形したブロックの移動をおこなうとともに、その位置を決定するブロック位置決定工程と、
前記配線混雑度算定部が、前記フロアプラン領域を小領域に分割する分割工程と、
前記配線混雑度算定部が、前記小領域ごとに前記ブロック間の配線混雑度を算定する配線混雑度算定工程と、
前記第２のブロック変形部が、前記配線混雑度算定工程により算定された配線混雑度に基いて、配線混雑が生じている小領域の配線混雑度が緩和されるように、かつ、変形後のブロック面積が変形前のブロック面積と同一となるように、当該小領域と重なるブロックの形状を変形する第２のブロック形状変形工程と、
を含むことを特徴とする集積回路のフロアプラン生成方法。
【請求項２】
第１のブロック変形部と第１のブロック位置決定部と配線混雑度算定部と第２のブロック変形部と第２のブロック位置決定部とを備えるフロアプラン生成装置によって集積回路のフロアプランを生成する集積回路のフロアプラン生成方法であって、
前記第１のブロック変形部が、ブロックの配置をおこなうフロアプラン領域内に配置されたブロック形状の変形をおこなう第１のブロック変形工程と、
前記第１のブロック位置決定部が、前記第１のブロック変形工程に基いて変形したブロックの移動をおこなうとともに、その位置を決定するブロック位置決定工程と、
前記配線混雑度算定部が、前記フロアプラン領域を小領域に分割する分割工程と、
前記配線混雑度算定部が、前記小領域ごとに前記ブロック間の配線混雑度を算定する配線混雑度算定工程と、
前記第２のブロック変形部が、前記配線混雑度算定工程により算定された配線混雑度に基いて、配線混雑が生じている小領域の配線混雑度が緩和されるように、かつ、変形後のブロック面積が変形前のブロック面積と同一となるように、当該小領域と重なるブロックの形状を変形する第２のブロック形状変形工程と、
前記第２のブロック位置決定部が、前記配線混雑度算定工程により算定された配線混雑度に基いて、配線混雑が生じている小領域の配線混雑度が緩和されるように、当該小領域と重なるブロックの移動をおこなうとともに、その位置を決定する第２のブロック位置決定工程と、
を含むことを特徴とする集積回路のフロアプラン生成方法。
【請求項３】
ブロックの配置をおこなうフロアプラン領域内で、ブロックの配置をおこなう初期フロアプラン算定部と、
前記初期フロアプラン算定部により配置されたブロックの形状を変形する第１の形状変形処理部と、
この変形したブロックの位置を移動するブロック移動処理部と、
前記フロアプラン領域を小領域に分割するとともに、前記小領域ごとに前記ブロック間の配線混雑度を算定する配線混雑度算定部と、
前記配線混雑度算定部により算定された配線混雑度に基いて、配線混雑が生じている小領域の配線混雑度が緩和されるように、かつ、変形後のブロック面積が変形前のブロック面積と同一となるように、当該小領域と重なるブロックの形状を変形する第２のブロック形状変形処理部と、
を備えることを特徴とする集積回路のフロアプラン生成装置。
【請求項４】
集積回路のフロアプランを生成する集積回路のフロアプラン生成方法をコンピュータに実行させる集積回路のフロアプラン生成プログラムであって、
前記コンピュータが、ブロックの配置をおこなうフロアプラン領域内に配置されたブロック形状の変形をおこなう第１のブロック変形工程と、
前記コンピュータが、前記第１のブロック変形工程に基いて変形したブロックの移動をおこなうとともに、その位置を決定するブロック位置決定工程と、
前記コンピュータが、前記フロアプラン領域を小領域に分割する分割工程と、
前記コンピュータが、前記小領域ごとに前記ブロック間の配線混雑度を算定する配線混雑度算定工程と、
前記コンピュータが、前記配線混雑度算定工程により算定された配線混雑度に基いて、配線混雑が生じている小領域の配線混雑度が緩和されるように、かつ、変形後のブロック面積が変形前のブロック面積と同一となるように、当該小領域と重なるブロックの形状を変形する第２のブロック形状変形工程と、
をコンピュータに実行させることを特徴とする集積回路のフロアプラン生成プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、ＣＡＤ（Computer Aided Design）などを使用したＬＳＩレイアウト設計のフロアプランに関し、特にブロック間の配線混雑度に応じた配線領域を効率的に確保することができる半導体集積回路のフロアプラン生成装置、フロアプラン生成方法およびその方法をコンピュータに実行させるためのプログラムに関する。
【０００２】
【従来の技術】
近年、ＬＳＩの集積度の向上や１チップに搭載可能な回路が大規模化するにともない、このＬＳＩを対象とするレイアウト設計（セルの配置や配線）に要する設計期間が長くなる傾向となっている。また、レイアウト設計後の修正が必要となった際にはチップ全体を再設計しなければならないため、このようなレイアウト設計の長期化を防止する対策の１つとして階層化設計によるＬＳＩレイアウト設計が行われている。
【０００３】
この階層化設計の場合、複数のセルをグループ化したものを１個のブロックとし、このブロックと他のブロックとが重ならないように、ブロックの形状および位置を決めてフロアプラン領域に配置させるとともに、ブロック内に存在している複数のセルの配置をおこなう。そして、セルの配置を行った後に、ブロック単位でブロック間およびセル間の配線をおこなうようにしている。
【０００４】
このような階層化設計によるレイアウト設計の場合、予め対象となる回路を複数のブロックにグループ化して分割することにより、回路全体を小規模な回路として扱うことができ、これによって、レイアウト設計に要する時間を短縮することができる。
【０００５】
ところで、ブロック間を接続する配線は、ブロック内のセルを接続する配線に比べて長くなるという傾向がある。そして、このようにブロック間で長い配線が存在すると、電気的な遅延が生じたり、ＬＳＩチップ自体のパフォーマンスが低下してしまう恐れがあるため、特に配線長さを考慮しない階層化設計の場合にも同様の問題が生じる。
【０００６】
上述したような理由から、現在ではブロック間の配線長さを考慮したＦＤ法（Force  Directed）によるフロアプランの生成法が提案されている（従来技術１）。このＦＤ法は、フロアプラン領域に配置するブロックの位置と形状を１度に決める方法であり、例えば１個所にブロックの重なりなどがある場合には、その重なりを修復した後、再度全体のブロック位置を決め直す手法である。また、このＦＤ法ではブロック間の配線長（ユークリッド距離）に基いて、該配線長のそれぞれを２乗して算出した「配線長の２乗の総和」が最小となるように、ブロックの位置と形状を決定する手法が採用されている。
【０００７】
ところが、かかる従来技術１の場合にはブロック間の配線長さを考慮しただけの手法であり、配線の混雑度（配線密度）については何ら考慮されていない。このため、例えばメモリなど大規模なブロックの周辺部は、そのブロックを迂回する配線があることから混雑が生じることがあるが、このような局所的な配線混雑を解消することができない。
【０００８】
そして、配線混雑度を（密度）考慮したフロアプラン生成方法として特開平１０−３４０９５８号公報（従来技術２）にはブロックの配置後にブロック間を概略的に配線して配線混雑度を見積もることにより、配線が混雑する部分を特定し、配置の改良をおこなうべき領域（配線可能な配線本数を超えている領域）を算出して、その領域内で配線混雑度が高い部分にあるブロックを拡大して膨らませ、次いで、その膨らませたサイズで、その領域内のみ再び重なりのないフロアプランを行った後、最終的に膨らませたブロックのサイズを元のサイズに戻す方法が開示されている。この方法によると、ブロック間で配線が混雑している領域の配線混雑度を平均化させることができる。
【０００９】
【発明が解決しようとする課題】
しかしながら、この従来技術２では指定した領域内のフロアプランを行う際、一旦ブロックのサイズを拡大するため、この操作により領域内を占めるブロック面積が大きくなり、ブロックのサイズを拡大する以前には配線が混雑していなかった領域が新たに混雑するという問題が生ずる。
【００１０】
また、重なりの無かったブロックに重なりが生じてしまう可能性もあり、指定した領域内のみの再フロアプランでは重なりがなく、且つ、配線の本数が減少したフロアプランが生成されるとは限らない。さらに、指定した領域外ではブロックの形状および位置が変化しないため、指定領域の内と外とを接続する配線長さは、設定した配線長さよりも長くなるという問題が生ずる。
【００１１】
さらに、上述した従来技術１，２に対する課題以外に、既存のフロアプラン生成方法にあっては、例えば、設計者の意図によりフロアプラン領域内の指定位置（近傍）に特定のブロックを配置させたいという要望があった場合でも、ブロックを指定位置に配置させるという手法はないため、このような特定のブロックを指定位置に配置するときには手動により、その作業をおこなわなければならないという問題が生ずる。
【００１２】
また、ブロックの種類として同一の論理の繰り返しなどにより、内部のセルやネットリストが同一であるブロックが存在（２個以上）する場合がある。このような場合においても従来では、ブロック内のレイアウトを１個毎のブロックを対象として、その都度変形や移動処理を行っていたためレイアウトに時間が掛かっていた。このことから、種類が同一であるブロックが複数存在する場合に対するレイアウト設計時間の短縮化を図ることができるフロアプラン生成方法の実現が望まれている。
【００１３】
本発明は、上述した従来技術による問題点を解決するためになされたものであり、ブロックの重なりがなくなるうえ、ブロック間の配線混雑度を効率的に確保することができ、ＬＳＩレイアウト設計に要する期間の短縮を図ることのできるフロアプラン生成方法、フロアプラン生成装置およびフロアプラン生成プログラムを提供することを目的とする。
【００１４】
【課題を解決するための手段】
上述した課題を解決し、目的を達成するために本発明は、第１のブロック変形部とブロック位置決定部と配線混雑度算定部と第２のブロック変形部とを備えるフロアプラン生成装置によって集積回路のフロアプランを生成する集積回路のフロアプラン生成方法であって、前記第１のブロック変形部が、ブロックの配置をおこなうフロアプラン領域内に配置されたブロック形状の変形をおこなう第１のブロック変形工程と、前記ブロック位置決定部が、前記第１のブロック変形工程に基いて変形したブロックの移動をおこなうとともに、その位置を決定するブロック位置決定工程と、前記配線混雑度算定部が、前記フロアプラン領域を小領域に分割する分割工程と、前記配線混雑度算定部が、前記小領域ごとに前記ブロック間の配線混雑度を算定する配線混雑度算定工程と、前記第２のブロック変形部が、前記配線混雑度算定工程により算定された配線混雑度に基いて、配線混雑が生じている小領域の配線混雑度が緩和されるように、かつ、変形後のブロック面積が変形前のブロック面積と同一となるように、当該小領域と重なるブロックの形状を変形する第２のブロック形状変形工程と、を含むことを特徴とする。
【００１５】
この発明によれば、フロアプラン領域を小領域に分割し、この小領域内での配線混雑度を見積もるとともに、算定された配線の混雑度に応じて配線混雑が生じている小領域の配線混雑度が緩和されるように、かつ、変形後のブロック面積が変形前のブロック面積と同一となるように、当該小領域と重なるブロックの形状を変形するようにしたので、このブロック形状の変形によりブロックの重なりがなくなるうえ、配線の混雑度に応じた配線領域を確保することができる。
【００１６】
【発明の実施の形態】
以下に添付図面を参照して、この発明に係る半導体集積回路のフロアプラン生成方法の好適な実施の形態を詳細に説明する。なお、本実施の形態ではＬＳＩのレイアウト設計に適用するフロアプラン生成方法を示すこととする。
【００１７】
（実施の形態１）
まず、本実施の形態１に係るフロアプランの生成方法について説明する。図１は本実施の形態１の集積回路のフロアプラン生成方法に適用するフロアプラン生成装置の構成を示す機能ブロック図を示している。また、図２は本実施の形態１にかかるフロアプラン生成方法のフローチャートであり、図３（a）〜（c）はかかるフロアプラン生成方法の処理手順（工程）を補足説明するための説明図である。
【００１８】
すなわち、図１に示すように、フロアプラン生成装置１００は、配線混雑解消処理部１６０、ＦＤ処理部１４０、制御部１５０、入力部１１０、表示制御部１２０、表示部１３０を備えている。このうち、ＦＤ処理部１４０は初期フロアプラン算定部１４１、形状変形処理部１４２、移動処理部１４３とを有し、配線混雑解消処理部１６０は配線混雑算定部１６１、形状変形処理部１６２、移動処理部１６３とを有している。
【００１９】
ＦＤ処理部１４０は、既存のフロアプラン生成方法であるＦＤ法に基くフロアプランを生成するための処理部であり、初期フロアプラン算定部１４１はブロックの面積を点とみなす初期のフロアプランを算定する。形状変形処理部１４２は、フロアプラン領域内で重なりのあるブロックの形状を変形する処理を行う。移動処理部１４３は、重なりのあるブロックを移動して位置を決める処理を行う。このＦＤ処理部１４０による処理データは制御部１５０に入力される。
【００２０】
配線混雑解消処理部１６０は、フロアプラン領域内に配置されるブロック間での配線混雑度を解消する処理機能を備えており、この配線混雑度解消処理部１６０を構成する配線混雑算定部１６１により、所定の小領域内での配線混雑度が算定される。
【００２１】
形状変形処理部１６２は、配線混雑算定部１６１により算定された配線混雑度に基づきブロックの形状変形をおこなう処理部である。後述するように、この場合の形状変形は、元のブロック面積に合わせる形状変形である。
【００２２】
移動処理部１６３は、配線混雑算定部１６１により算定された配線混雑度に基づきブロックの移動をおこなう処理部である。後述するように、この場合のブロック移動は、配線が混雑している所定の小領域との重なりを減少させる移動処理である。
【００２３】
入力部１１０は、レイアウト設計による処理の指示や表示部上のレイアウト画面を見てレイアウト場所を指定するなど人手により行う装置で、この入力部１１０としてはキーボードやマウスが使用される。
【００２４】
制御部１５０は、ＦＤ処理部１４０および配線混雑解消処理部１６０からのブロックの形状変形データや移動データが入力され、これら処理データに基づき、フロアプラン生成装置１００としての全体制御をおこなうコントローラとしての機能を備えている。
【００２５】
表示部１３０は、表示制御部１２０を介して制御部１５０により指示された表示画面が表示される。具体的には、フロアプラン領域を表す画面やフロアプラン生成装置１００によるレイアウト設計画面を表示する。この表示部１３０にはディスプレイ（ＣＲＴ）などが使用される。
【００２６】
ここで、本実施の形態１の特徴は配線の混雑度に応じてブロックの形状を変形させ、このブロック形状の変形により配線の混雑している配線領域を確保することにある。ここで、本発明は既存のＦＤ法によるフロアプラン生成方法を元にして、ブロック間の配線混雑度を解消する点に着目したものである。このため、ステップＳ２０１〜ステップＳ２０４はＦＤ法についての説明である。前述したように、このＦＤ法によるフロアプランはブロック間の配線長さを考慮するとともに、ブロック間での重なりがないようにブロック配置がなされたフロアプランである。
【００２７】
以下、ＦＤ法のフロアプラン生成方法の概略を含めて、実施の形態１の詳細を、図２のフローチャートおよび図３（ａ）〜（ｃ）を参照して説明する。まず、図２に示すように最初にブロックを点（ブロックの面積を０と仮定する。）とみなす初期フロアプランの計算を行う（ステップＳ２０１）。
【００２８】
次いで、フロアプラン領域内で重なっているブロックが存在していた場合には、このブロックの重なりを解消するための、ブロック形状の変形を行う（ステップＳ２０２）。この場合の形状変形とは、重なり合うブロック同士の形状を変形させて重なり面積を徐々（１回毎）に減らしていく変形工程である。また、一回毎にブロックを変形させる距離（大きさ）はごく僅かであり、その変形量は予め選定されている。
【００２９】
次いで、ブロックの重なりに基いてブロック同士間で反発力を発生させ、その反発力を利用して、重なったブロックを徐々に離隔させることにより、その位置を決定するブロックの重なりに基づく位置決定をおこなう（ステップＳ２０３）。この場合のブロックを１回毎に離隔させる距離もごく僅かな移動量として予め選定されている。
【００３０】
以下、終了条件を満たしているか否かの判定を行う（ステップＳ２０４）。ここで、終了条件にはブロックの重なりがほとんど無くなったなど、重なり面積に関する条件など種々の条件を設定することができる。そして、終了条件を満たしている場合には（ステップＳ２０４肯定）、次いでステップＳ２０５に移行する。
【００３１】
この一方、終了条件を満たしていない場合には（ステップＳ２０４否定）、再度ステップＳ２０２に戻り、ブロックの重なりに基いた形状変形を行う。実際には、ステップＳ２０２による１回毎の形状変形およびステップＳ２０３による移動量はごく僅かであるため、ブロックの重なりが解消するまでステップＳ２０２〜ステップＳ２０４をループさせることになる。
【００３２】
そして、以降ステップＳ２０５〜ステップＳ２０９は本実施の形態１の特徴部分である。まず、フロアプランの全領域を小領域に分割するフロアプラン領域の分割を行う（ステップＳ２０５）。図３（ａ）ではフロアプラン領域を細線により分割し、細分化した複数の小領域上に複数のセルをグループ化して１個にまとめたブロックが配置された状態を表している。このように、フロアプラン領域を細分化するのは、細部の区域（小領域）において配線経路や配線の混雑度を詳細に見積もる（判定する）ためである。
【００３３】
次いで、各小領域を対象として配線経路と配線混雑度の計算を行い（ステップＳ２０６）、計算により算出された配線の混雑度に基いてブロックの形状変形を行う（ステップＳ２０７）。すなわち、ステップＳ２０６ではＦＤ法によるフロアプランで配置されたブロック間に対して概略的に配線をおこない、小領域単位で配線混雑度を見積もることにより、配線が混雑する部分（小領域）を特定するとともに、ブロック配置の改良（変形）を行うべき領域を算出する。また、ステップＳ２０７では見積もりにより算出された配線可能な配線本数に対し、小領域内で実存する配線の本数または見積もり本数が違反している小領域を対象として、ブロック形状を変形させる処理を行う。具体的には、配線混雑が生じている小領域からブロックを変形により離隔させることにより配線混雑度を緩和させている。
【００３４】
すなわち、図３（ａ）に示すように、例えば、小領域内に３本程度の配線数（配線経路）が配線可能な見積もり値として設定されている場合を考えると、３本以上（例えば、４本）の配線が小領域Ｘに存在する場合は、この小領域Ｘは見積もり本数が違反している混雑部であると判断する。そして、この場合には配線混雑度に基いて、変形を行うブロック（各辺）の移動量（大きさ）と向きを決定する。具体的には、同図（ａ）に示すように混雑部を避けるべくブロックを一時的に、その代表点Ｐに向けて圧縮させながら小さくする変形をおこなう。
【００３５】
また、図３（ｂ）に示すブロック（実線部）は、辺の移動による形状変形で大きさが元のサイズよりも小さくなった状態を示している。そして、このままでは最初のブロックと変形したブロックとの面積が異なるため、元のブロック面積と同一となるように、この変形したブロックに対して縦横の辺部を同じ比率で拡大する処理（矢印方向）をおこなうようにしている。この場合、ブロックの拡大は縦横の辺部を同じ比率で互いに補填しながらおこなうため、いずれか一方の辺部が突出して周囲のブロックに重なることはない。
【００３６】
図３（ｃ）は上述したブロック形状の変形により、新しくなったブロックの位置を表す図であり、ブロックの変形により小領域Ｘの配線混雑が減少し、配線領域が確保されていることがわかる。
【００３７】
そして、上述したように、ブロックの形状を配線混雑度に基いて変形させた後、次いで、ブロックの重なりに基いた形状変形を行う（ステップＳ２０８）。つまり、図３（ｃ）に示すように変形したブロックは初期のブロック形状に比べて横長になるため、このブロックが他のブロックと重なる場合には、再度ブロック形状の変形を行う必要がある。この工程は、前述したようにブロック同士の形状を変形させて重なり面積を徐々に減らしていく処理である。
【００３８】
次いで、ブロックの重なりに基いた、ブロックの位置決定を行う（ステップＳ２０９）。この工程も前述したと同様、ブロックが重なっていたら離隔させて、最終的にブロック位置の決定を行う工程である。
【００３９】
以下、終了条件２を満たしているか否かの判定を行う（ステップＳ２１０）。その結果、終了条件を満たしている場合には（ステップＳ２１０肯定）、処理を終了し、終了条件を満たしていない場合には（ステップＳ２１０否定）、再度（ステップＳ２０６）に戻り、配線経路と配線混雑度の計算を行う。実際には、Ｓ２０６による配線混雑度による形状変形およびステップＳ２０７による位置決定は微量なものであるため、ブロックの重なりが解消するまでステップＳ２０６〜ステップＳ２１０をループさせる。ここで、終了条件２とは、終了条件１と同様にブロックの重なり面積の条件や、新たに配線または配線見積もりが違反している本数などを利用した種々の条件を設定する。なお、終了条件１と終了条件２とは同一となる場合もある。
【００４０】
上述したように、本実施の形態１では、フロアプラン領域を小領域に分割し、この小領域内での配線混雑度を見積もるとともに、算定された配線の混雑度に応じてブロックの形状を重なりがないように変形させるようにしたので、このブロック形状の変形により配線の混雑度に応じた配線領域を確保することができる。
【００４１】
（実施の形態２）
次に、本実施の形態２にかかるフロアプランの生成方法について説明する。図４は本実施の形態２にかかるフロアプラン生成方法のフローチャートであり、図５はかかるフロアプラン生成方法の処理手順（工程）を補足説明するための説明図である。ここで、本実施の形態２の特徴は実施の形態１が配線の混雑度に応じてブロックの形状を変形させていたのに対して、この実施の形態２では配線の混雑度に応じてブロックを移動させることにより配線の混雑している配線領域を確保し、配線混雑度に基くブロックの位置決定を行うことにある。以下、その詳細について実施の形態１と相違する特徴部分を中心に図４のフローチャートおよび図５を参照して説明する。
【００４２】
すなわち、図４に示すように前述したステップＳ２０１〜ステップＳ２０４によるＦＤ法に基づくフロアプランをおこなった後、フロアプランの全領域を小領域に分割するフロアプラン領域の分割を行い（ステップＳ２０５）、次いで、小領域における配線経路と配線混雑度の計算を行う（ステップＳ２０６）。
【００４３】
そして、本実施の形態２ではステップＳ２０６の配線混雑度の計算を行う工程に次いで、ブロックの重なりに基いたブロックの形状変形を行う（ステップＳ４０１）。この工程は、前述したと同様、重なっているブロック同士の重なり面積を徐々に減らしていく工程である。
【００４４】
次いで、配線の混雑混雑度に基くブロックの移動による位置決定を行う（ステップＳ４０２）。すなわち、図５（ａ）に示すように、小領域Ｘが配線または見積もりが違反している領域であると判断された場合、この小領域Ｘとブロックとの重なりが減少するようにブロックの移動を行う。この場合、配線混雑度に基いて、ブロック（各辺）の移動量（大きさ）と向きが決定される。具体的には、同図（ｂ）に示すように混雑部である小領域Ｘを避けるべくブロックをフロアプラン領域の上側に向けて移動する。
【００４５】
そして、移動したブロックに対してブロックの重なりに基いた、ブロックの位置決定を行う（ステップＳ４０３）。この工程は前述したと同様、ブロックが重なっていたら離隔させる工程である。
【００４６】
以下、終了条件２を満たしているか否かの判定を行う（ステップＳ２１０）。その結果、終了条件を満たしていない場合には（ステップＳ２１０否定）、再度ステップＳ２０６に戻り、ブロックの重なりが解消するまでステップＳ２０６〜ステップＳ２１０をループさせる処理を行う。
【００４７】
上述したように、本実施の形態２では、配線の混雑度に応じてブロックを移動させることにより配線の混雑している配線領域を確保し、配線混雑度による位置決定を行うので、このブロックの移動により配線の混雑度に応じて適した配線領域を確保することができる。また、本実施の形態２の場合、配線混雑度に基いてブロックは移動するだけであり、前述した実施の形態１によるブロックの形状変形はおこなわない。このため、配線混雑度に基いたブロックの形状変形にともなう縦横の辺部を同比率で圧縮させたり、拡大する処理をおこなう必要がないことから、レイアウト設計時間の短縮を図ることができる。
【００４８】
（実施の形態３）
次に、本実施の形態３にかかるフロアプランの生成方法について説明する。図６は本実施の形態３にかかるフロアプラン生成方法のフローチャートであり、図７はかかるフロアプラン生成方法の処理手順（工程）を補足説明するための説明図である。これら、図６，７を参照して本実施の形態３の詳細について説明する。
【００４９】
ここで、本実施の形態３の特徴は前述した実施の形態１，２を組み合わせたものであり配線混雑度に応じてブロック形状の変形および移動をおこなうことに特徴がある。以下、実施の形態１，２と相違する実施の形態３の特徴部分を中心に説明する。
【００５０】
すなわち、図６に示すようにＦＤ法に基づくフロアプランを行った後、前述したステップＳ２０５〜ステップＳ２０７と同様、フロアプランの全領域を小領域に分割するフロアプラン領域の分割を行い（ステップＳ２０５）、次いで、小領域における配線経路と配線混雑度の計算を行い（ステップＳ２０６）、配線混雑度に基いたブロックの形状変形を行い（ステップＳ２０７）、ブロックの重なりに基いた形状変形を行う（ステップＳ２０８）。
【００５１】
具体的には、各小領域で配線可能な本数を見積もりにより算出し、この配線または見積もりが違反している本数を基にして、その領域との重なりが減少するようにブロックの形状を変形させる。以上のように、本実施の形態３では第一段階としてブロックの形状変形によりブロックの形状を設定する。
【００５２】
そして、次に配線混雑度に基づくブロックの位置決定を行い（ステップＳ６０１）、次いで、移動したブロックに対してブロックの重なりに基いた、ブロックの位置決定を行う（ステップＳ２０９）。この工程は前述したと同様、ブロックが重なっていたら離隔させる工程である。
【００５３】
具体的には、各小領域で配線可能な本数を見積もりにより算出し、この配線または見積もりが違反している本数を基にして、その領域との重なりが減少するようにブロックの移動を行う。つまり、この工程が本実施の形態３の第二段階でありブロックの移動によりブロックの位置を設定している。本実施の形態３によると、図７（ａ）（ｂ）に示すようにブロックの形状を変形させる工程と、この変形したブロックを移動させる工程とを少しづつ交互に繰り返して行うので、先の実施の形態１，２で示したブロックの形状変形や移動だけでは小領域Ｘの配線混雑度の解消ができない場合などの際に、有効に対応することができる。
【００５４】
上述したように、本実施の形態３では、配線の混雑度に応じてブロックの形状を変形させる工程と、この変形したブロックを移動させる工程とを少しづつ繰り返しておこなうので、このようなブロックの形状変形および移動により配線の混雑度に応じた配線領域を効率的に確保することができる。
【００５５】
（実施の形態４）
次に、本実施の形態４にかかるフロアプランの生成方法について説明する。図８は本実施の形態４にかかるフロアプラン生成方法のフローチャートであり、図９はかかるフロアプラン生成方法の処理手順（工程）を補足説明するための説明図である。これら、図８，９を参照して本実施の形態４の詳細について説明する。
【００５６】
ここで、本実施の形態４の特徴は変形移動により、現在でのブロックの位置と、予め設計者により指定されたブロックの位置との距離が閾値以下となるようにしたことに特徴がある。ここで、現在でのブロックの位置とは、前述した実施の形態１〜３の方法により設定されるとともに、フロアプラン領域内に配置されているブロックの位置（最終的に配置された位置）を示している。
【００５７】
まず、フロアプラン領域内で位置が指定されたブロックを１個選択する（ステップＳ８０１）。前述したように、この位置が指定されたブロックとは、予め設計者がフロアプラン領域の中で、配置させる場所を指定している特定のブロックを示している。次いで、位置が指定されたブロックの現在の位置（代表点Ｐ２）とそのブロックの指定された位置（代表点Ｐ１）の距離Ｌを計算する（ステップＳ８０２）。
【００５８】
ここで、図９（ａ）では位置が指定されたブロックの現在の位置とそのブロックの指定された位置はそれぞれ代表点Ｐ１，Ｐ２で表しているため、計算により算出される距離はＬとする。次いで、距離Ｌが設定した閾値Ｎを超えているか否かの判定を行う（ステップＳ８０３）。この判定により、距離Ｌが閾値Ｎを超えている場合には（ステップＳ８０３肯定）、図９（ｂ）に示すように指定位置（代表点Ｐ１の位置）に向けて現在のブロックを移動させる（ステップＳ８０４）。具体的には、算出された距離Ｌが閾値Ｎよりも大きい場合には、反発力が設定され、この反発力によりブロックを指定された位置（近傍位置）に移動するものとなる。以下、位置が指定されたブロック全てについて調査して、位置が指定されたブロック全てについての調べが終了した時点で処理が完了となる。
【００５９】
一方、距離Ｌが設定した閾値Ｎを超えているか否かの判定により（ステップＳ８０３）、選択したブロックに関し移動した距離Ｌが閾値Ｎを超えていない場合には（ステップＳ８０３否定）、このブロックを指定位置に移動する処理はおこなわない。
【００６０】
上述してきたように、本実施の形態４では予め設計者がフロアプラン領域内で指定した特定のブロック位置と現在のブロック位置との距離が閾値より大きく離れすぎている場合には、この離れたブロックを指定された位置に移動させるフロアプランを行うので、ブロックの移動距離を閾値以下とすることができ、設計者が意図する特定の位置またはその近傍付近に特定のブロックを自動的に配置することができる。
【００６１】
（実施の形態５）
次に、本実施の形態５に係るフロアプランの生成方法について説明する。図１０は本実施の形態５に係るフロアプラン生成方法のフローチャートであり、図１１，１２はかかるフロアプラン生成方法の処理手順（工程）を補足説明するための説明図である。以下、これら図１０〜１２を参照して本実施の形態５の詳細について説明する。フロアプラン領域内に同種類（セル・ネットリストが同じ）のブロックが少なくても２個以上ある場合に適用する。
【００６２】
ここで、本実施の形態５の特徴はブロック内のセルの機能およびネットリストが同一であるなど、同種類のブロックが少なくとも２個以上ある場合には、一方のブロック形状の変形に合わせて、他方のブロック形状の変形を行うことを特徴とする。
【００６３】
まず、フロアプラン領域内で他のブロックＢと重なりのあるブロックＡを選択する（ステップＳ９０１）。次いで、ブロックＡと同種類のブロックを選択する（ステップＳ９０２）。ここで、同種類のブロックとはセルの種類（機能）やネットリストが同じものを示しており、図１１（ａ）ではブロックＡ´で表している。
【００６４】
次いで、ブロックＡの変形により、ブロックＡ´の代表点から遠ざかるブロックＡ´の２辺が、それぞれ他のブロックＣ，Ｄと重なっているか否かの判定を行う（ステップＳ９０３）。この判定により、ブロックＡ´の２辺が、それぞれ他のブロックＣ，Ｄ（図１２参照）と重なっていない場合には（ステップＳ９０３否定）、ブロックＡと同種類のブロックをすべて調べ（ステップＳ９０４）、ブロックＡおよび、このブロックＡと同種類のブロックＡ´すべてのブロック形状の変形を行う（ステップＳ９０５）。
【００６５】
つまり、図１１（ａ）に示すようにブロックＢとの重なりを解消すべくブロックＡの変形を行う場合、このブロックＡと同種類であるブロックＡ´の変形も同時に行う。具体的には、図１１（ｂ）に示すようにブロックＡとブロックＢとの重なりに基いて、ブロックＡとブロックＡ´のそれぞれの高さ寸法を小さくする。
【００６６】
そして、このままでは最初のブロックＡ，Ａ´（点線のブロック）と形状を変形したブロックＡ，Ａ´（実線のブロック）との面積が異なるため、元のブロック面積と同一となるように、この変形したブロックに対して縦横の辺部を同じ比率で拡大する処理を行う。以下、フロアプラン領域内で他のブロックと重なりのあるブロックを対象として全て調べ（ステップＳ９０６）、該当するブロックを全て調べたら処理を終了する。
【００６７】
ここで、図１２は本実施の形態５を適用しない例の説明図を示している。すなわち、図１２ではブロックＡと同種類のブロックＡ´が存在し、ブロックＡとブロックＢとが重なっており、ブロックＡ´の近傍には他のブロックＣ，Ｄが配置されている状態を示している。このため、同図に示すようにブロックＡの変形にともなって、ブロックＡ´の変形を行った場合には、このブロックＡ´と他のブロックＣ，Ｄとが重なるという不具合が発生する。具体的には、ブロックＡ´の代表点から遠ざかる２辺が他のブロックＣ，Ｄと重なる（ステップＳ９０３肯定）。したがって、この場合のようにブロックＡ´の形状変形により、このブロックＡ´が周囲のブロックの何れかと重なる場合には、ブロックＡおよびブロックＡ´両者の形状変形はおこなわない。
【００６８】
上述したように、本実施の形態５では、ブロック内のセルの機能およびネットリストが同一であるなど、同種類のブロックが少なくとも２個以上ある場合には、一方のブロック形状の変形に合わせて、他方のブロック形状の変形を行うようにしたので、ブロックの種類が同一のものについては、ブロック内のレイアウトを１回で行うことができレイアウト設計期間の短縮化を図ることができる。
【００６９】
図１３（ａ）〜（ｄ）は実施の形態１〜５の実施に基づくフロアプラン生成方法によりブロックの形状および位置が決定される様子を示す説明図である。すなわち、図１３（ａ）では複数の小領域に分割されたフロアプラン領域を示し、図１３（ｂ）ではＦＤ法によるブロック同士の重なりのないフロアプランを示している。ここで、図１３（ｂ）中、指定位置は設計者により予め指定された特定ブロックの代表点を示しており、この指定位置と現在配置されているブロックの代表点との距離は閾値以下となるように配置されている。また、図１３（ｃ）は配線経路または配線見積もり値を元にした各ブロックの形状変形およびブロックの移動状態を示しており、図１３（ｄ）では最終的にフロアプラン領域内に配置された重なりのないブロックが配置されたフロアプランを表している。
【００７０】
（実施の形態６）
本実施の形態６では、上記実施の形態１〜５に示したフロアプラン生成方法と同様の機能を有するフロアプラン生成方法を実行するプログラム（コンピュータシステム）ついて説明する。
【００７１】
図１４に示すコンピュータシステム１８０は、本体部１８１、この本体部１８１からの指示により表示画面１８０ａに画像等の情報を表示するディスプレイ１８２、このコンピュータシステム１８０に種々の情報を入力するためのキーボード１８３、ディプレイ１８２の表示画面１８０ａ上の任意の位置を指定するマウス１８４、ローカルエリアネットワーク（ＬＡＮ）１８６または広域エリアネットワーク（ＷＡＮ）に接続するＬＡＮインターフェース、インターネットなどの公衆回線１８７に接続するモデム１８５が備えられている。
【００７２】
ここで、ＬＡＮ１８６は、ほかのコンピュータシステム（ＰＣ）１９１、サーバ１９２、プリンタ１９３等とコンピュータシステム１８０とを接続している。また、図１５に示すように、本体部１８１は、ＣＰＵ３０１、ＲＡＭ３０２、ＲＯＭ３０３、ハードディスクドライブ（ＨＤＤ）３０４、ＣＤ−ＲＯＭドライブ３０５、フロッピー（登録商標）ディスクドライブ３０６、Ｉ／Ｏインターフェース３０７およびＬＡＮインターフェース３０８を備えている。
【００７３】
このコンピュータシステム１８０においてフロアプラン生成方法を実行する場合、フロッピーディスク１８８、ＣＤ−ＲＯＭ１８９、ＤＶＤディスク、光磁気ディスク、ＩＣカード等の可搬型記憶媒体、モデム１８５およびＬＡＮインターフェースを利用し回線を介して接続されたサーバ１９２のデータベース、あるいは、ほかのコンピュータシステム（ＰＣ）１９１のデータベースに格納等の記憶媒体に記憶されたモデル構築プログラムをコンピュータシステム１８０にインストールする。インストールされたモデル構築プログラムは、ＨＤＤ３０４に記憶され、ＲＡＭ３０２、ＲＯＭ３０３などを利用してＣＰＵ３０１により実行される。
【００７４】
ここで、記憶媒体とは、ＣＤ−ＲＯＭ１８９、フロッピーディスク１８８、ＤＶＤディスク、光磁気ディスク、ＩＣカード等の可搬型記憶媒体やコンピュータシステム１８０の内外に備えられたハードディスク３０４等の記憶装置のほか、ＬＡＮ１８６を介して接続されたインストール元のモデル構築プログラムを保持するサーバ１９２のデータベース、あるいは、ほかのコンピュータシステム１９１並びにそのデータベースや、さらに公衆回線１８７上の伝送媒体をも含むものである。
【００７５】
上述してきたように、前記実施の形態１〜５に示したフロアプラン生成方法が有する構成をソフトウェアによるフロアプラン生成方法プログラムとしてコンピュータシステム１８０上で実行することで、実施の形態１〜５に示したフロアプラン生成方法と同様の効果を、一般的なコンピュータシステムを用いて実現することができる。
【００７６】
（付記１）ブロックの配置をおこなうフロアプラン領域内に配置されたブロック形状の変形をおこなう第１のブロック変形工程と、
前記第１のブロック変形工程に基いて変形したブロックの移動をおこなうとともに、その位置を決定するブロック位置決定工程と、
前記フロアプラン領域を小領域に分割する分割工程と、
前記ブロック間の配線混雑度を算定する配線混雑度算定工程と、
該配線混雑度算定工程により算定された配線混雑度に基いて、前記ブロックの形状を変形する第２のブロック形状変形工程と、
を含むことを特徴とする集積回路のフロアプラン生成方法。
（付記２）前記配線混雑度算定工程により算定された配線混雑度に基いて、前記ブロックを移動するブロック移動工程をさらに含むことを特徴とする付記１に記載の集積回路のフロアプラン生成方法。
（付記３）フロアプラン領域内に配置するブロックの形状を変形する第１のブロック変形工程と、
この変形したブロックの位置を移動して決定するブロック位置決定工程と、
前記フロアプラン領域を小領域に分割する分割工程と、
前記ブロック間の配線混雑度を算定する配線混雑度算定工程と、
前記配線混雑度に基いて前記ブロックを移動するブロック移動工程と、
を含むことを特徴とする半導体集積回路のフロアプラン生成方法。
（付記４）前記フロアプラン領域内で、その指定位置が予め指定された特定のブロックは、その指定位置の近傍に配置することを特徴とする付記１、２または３に記載の集積回路のフロアプラン生成方法。
（付記５）前記第１のブロック変形工程は、ブロック同士の重なり面積を減らしていく処理であることを特徴とする付記１〜４のいずれか一つに記載のフロアプラン生成方法。
（付記６）前記第２のブロック変形工程は、変形前のブロック面積と変形後のブロック面積とを保持する処理であることを特徴とする付記１〜５のいずれか一つに記載のフロアプラン生成方法。
（付記７）前記ブロック位置決定工程は、ブロック同士の重なり発生時には、これらブロックを反発力により互いに離隔させる処理であることを特徴とする付記１〜６のいずれか一つに記載のフロアプラン生成方法。
（付記８）ブロック内のセルの機能およびネットリストが同一であるなど、同種類のブロックが少なくとも２個以上ある場合には、一方のブロック形状の変形に合わせて、他方のブロック形状の変形を行うことを特徴とする付記１〜７のいずれか一つに記載のフロアプラン生成方法。
（付記９）前記他方のブロックの形状変形にともない、該ブロックが周囲に配置されたブロックの何れかと重なる場合には、前記一方のブロックおよび他方のブロックの両者の形状変形はおこなわないことを特徴とする付記８に記載のフロアプラン生成方法。
（付記１０）ブロックの配置をおこなうフロアプラン領域内で、ブロックの配置をおこなう初期フロアプラン算定部と、
前記初期フロアプラン算定部により配置されたブロックの形状を変形する第1の形状変形処理部と、
この変形したブロックの位置を移動するブロック移動処理部と、
前記ブロック間の配線混雑度を算定する配線混雑度算定部と、
該配線混雑度算定部により算定された配線混雑度に基いて、前記ブロックの形状を変形する第２のブロック形状変形処理部と、
を含むことを特徴とする集積回路のフロアプラン生成装置。
（付記１１）ブロックの配置をおこなうフロアプラン領域内に配置されたブロック形状の変形をおこなう第１のブロック変形工程と、
前記第１のブロック変形工程に基いて変形したブロックの移動をおこなうとともに、その位置を決定するブロック位置決定工程と、
前記フロアプラン領域を小領域に分割する分割工程と、
前記ブロック間の配線混雑度を算定する配線混雑度算定工程と、
該配線混雑度算定工程により算定された配線混雑度に基いて、前記ブロックの形状を変形する第２のブロック形状変形工程と、
を含むことを特徴とする集積回路のフロアプラン生成プログラム。
【００７７】
【発明の効果】
以上説明したように、本発明によれば、配線混雑度に基いてブロックの形状を変形し、またブロックの移動を行うので、各配線混雑度に応じた配線領域を広く効率的に確保することができるうえ、ブロック間の重なりを防止でき、これによって、ＬＳＩレイアウト設計に要する期間の短縮を図ることができるという効果を奏する。
【００７８】
また、本発明によれば、予め設計者がフロアプラン領域内で指定した特定のブロック位置と現在のブロック位置との距離が閾値より大きく離れすぎている場合には、この離れたブロックを指定された位置に移動させるフロアプランを行うので、ブロックの移動距離を閾値以下とすることができ、設計者が意図する特定の位置またはその近傍付近に特定のブロックを配置することができるという効果を奏する。
【００７９】
さらに、本発明によれば、ブロック内のセルの機能およびネットリストが同一であるなど、同種類のブロックが少なくとも２個以上ある場合には、一方のブロック形状の変形に合わせて、他方のブロック形状の変形を行うようにしたので、ブロックの種類が同一のものについては、ブロック内のレイアウトを１回で行うことができレイアウト設計の効率化およびレイアウト設計期間の短縮化を図ることができるという効果を奏する。
【図面の簡単な説明】
【図１】フロアプラン生成方法が適用されるフロアプラン生成装置の概略構成図である。
【図２】実施の形態１にかかるフロアプラン生成手順を示すフローチャートである。
【図３】図２に示したブロック形状を変形するフロアプラン生成手順の説明図である。
【図４】実施の形態２にかかるフロアプラン生成手順を示すフローチャートである。
【図５】図４に示したブロックを移動するフロアプラン生成手順の説明図である。
【図６】実施の形態３にかかるフロアプラン生成手順を示すフローチャートである。
【図７】図６に示したブロックの形状変形と移動を行うフロアプラン生成手順の説明図である。
【図８】実施の形態４にかかるフロアプラン生成手順を示すフローチャートである。
【図９】図８に示したブロックを指定された位置に移動させるフロアプラン生成手順の説明図である。
【図１０】実施の形態５にかかるフロアプラン生成手順を示すフローチャートである。
【図１１】図１０に示した同種類のブロック形状を保持する形状変形を行うフロアプラン生成手順の説明図である。
【図１２】同種類のブロック形状の形状変形を行わないフロアプラン生成手順の説明図である。
【図１３】フロアプラン生成手段によりブロックの形状・位置が決定する様子を示す説明図である。
【図１４】本実施の形態にかかるコンピュータシステムを説明するための説明図である。
【図１５】図１４に示した本体部の構成を示す説明図である。
【符号の説明】
Ａ，Ａ´  ブロック
Ｂ，Ｃ，Ｄ  ブロック
１００  フロアプラン生成装置
１１０  入力部
１２０  表示制御部
１３０  表示部
１４０  ＦＤ処理部
１４１  初期フロアプラン算定部
１４２  形状変形処理部
１４３  移動処理部
１６０  配線混雑解消処理部
１６１  配線混雑算定部
１６２  形状変形処理部
１６３  移動処理部
１８０  コンピュータシステム
１８０ａ  表示画面
１８１  本体部
１８２  ディスプレイ
１８３  キーボード
１８４  マウス
１８５  モデム
１８６  ローカルエリアネットワーク（ＬＡＮ）
１８７  公衆回線
１８９  ＣＤ−ＲＯＭ
１９１  コンピュータシステム（ＰＣ）
１９２  サーバ
１９３  プリンタ
３０１  ＣＰＵ
３０２  ＲＡＭ
３０３  ＲＯＭ
３０４  ハードディスクドライブ（ＨＤＤ）
３０５  ＣＤ−ＲＯＭドライブ
３０６  フロッピーディスクドライブ
３０７  Ｉ／Ｏインターフェース
３０８  ＬＡＮインターフェース
【図１】
0004068376.tif 000002
【図２】
0004068376.tif 000003
【図３】
0004068376.tif 000004
【図４】
0004068376.tif 000005
【図５】
0004068376.tif 000006
【図６】
0004068376.tif 000007
【図７】
0004068376.tif 000008
【図８】
0004068376.tif 000009
【図９】
0004068376.tif 000010
【図１０】
0004068376.tif 000011
【図１１】
0004068376.tif 000012
【図１２】
0004068376.tif 000013
【図１３】
0004068376.tif 000014
【図１４】
0004068376.tif 000015
【図１５】
0004068376.tif 000016