JPH02128459A - Ｌｓｉの素子ブロック配置方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 ［産業上の利用分野コ 本発明はＬＳＩの素子ブロック配置方法、特にＬＳＩ基
板上にそれぞれ所定の面積を有する複数個の素子ブロッ
クを配置するＬＳＩの素子ブロック配置方法に関する。

［従来の技術］ ＬＳＩの多様化にともない、複数個の不均一な形状のブ
ロックを所望のチップ枠内に配置しなければならず、Ｌ
ＳＩ設計時におけるブロック配置方法は重要な役割を果
たしている。

この様なブロック配置方法として、「大きさの異なるブ
ロック配置の一手法（力学モデルに基づく概略配置とコ
ンパクションによる位置決定）：小野寺他、電子情報通
信学会ＶＬＤ８７−６２Ｊがある。

該ブロック配置方法は、各ブロック間の結線条件を吸引
力とし、各ブロック間の重なり面積を反光力とし、配置
ブロックに前記吸引力及び前記反発力を作用させる力学
モデルからブロック配置を行なうものである。

［発明が解決しようとする課題］ しかしながら、従来のブロック配置方法は、予め各ブロ
ックの矩形形状が与えられており、固定形状であるので
、所望のチップ枠内に収めるためには各ブロックの移動
のみでは限界があった。

更に、チップ枠内に全てのブロックを収めるためには、
各ブロック間の結線数等の接続条件を最優先することが
難しいという問題点があった。

本発明は、上記問題点を解決することを課題としており
、各ブロック間の結線数等の接続条件を最優先し、所望
のチップ枠内に全てのブロックを収めることのできる設
計自由度の高いブロック配置方法を提供することを目的
とする。

［課題を解決するための手段］ 上記目的を達成するために、本発明は、ＬＳＩ基板上に
それぞれ所定の面積を有する複数個の素子ブロックを配
置するＬＳＩの素子ブロック配置方法において、各素子
ブロックを各素子ブロック間の結線数等の接続条件に基
づいて面積を無視した基本格子に配置する基本格子配置
工程と、全ての素子ブロックに所望面積の正方外形を与
える正方外形仮決め工程と、各ブロックの正方外形に基
づいて、各ブロックが互いに重ならないように各素子ブ
ロックを離すブロック離し工程Ａと、前記離し工程で生
じた各ブロック間の隙を詰めるブロック詰め工程と、前
記詰め工程で決定された外枠のＸ軸方向及びＹ軸方向の
辺の長さと、所望チップ枠のＸ軸方向及びＹ軸方向の辺
の長さとを比較し、大きい比の軸方向を縮小方向とし、
縮小率を算出する縮小率・縮小方向算出工程と、各ブロ
ック間の前記縮小方向の有向グラフ、及び非縮小方向の
有向グラフを生成する有向グラフ生成工程と、前記縮小
方向に最も突出したブロックを探索し、該ブロックから
前記縮小方向の有向グラフを辿り縮小方向の辺の長さに
影響を及ぼす肥大ブロック群を抽出する肥大ブロック群
抽出工程と、前記抽出された肥大ブロック群の縮小方向
の各辺を前記縮小率で縮小するとともに、非縮小方向の
辺を同一面積となるように拡大するブロック形状調整工
程と、前記ブロック形状調整工程で発生したブロック間
の重なりを非縮小方向の有向グラフを辿りながら取り除
くブロック離し工程Ｂと、からなり、前記外枠が所望チ
ップ枠の大きさとなるまで、前記ブロック詰め工程、縮
小率・縮小方向算出工程、有向グラフ生成工程、肥大ブ
ロック群抽出工程、及びブロック形状調整工程及びブロ
ック離し工程Ｂを繰り返すものである。

［作用コ 本発明によるブロック配置方法は、各ブロックの形状を
変形するので、全ブロックの配置を単純なアルゴリズム
で所望のチップ枠内に収めることができ、トップダウン
的レイアウト設計に有効である。

［実施例〕 以下、本発明の好適な一実施例を図面に基づいて説明す
る。

第１図は、本実施例の配置手順を示すフローチヤード図
である。

同図に示されるように、本発明は、基本格子配置工程（
Ｓ　１０）と、正方外形仮決め工程（Ｓ２０）と、ブロ
ック離し工程Ａ（Ｓ３０）と、ブロック詰め工程（Ｓ　
４０）と、縮小率・縮小方向算出工程（Ｓ　５０）と、
終了判定工程（Ｓ　６０）と、有向グラフ生成工程（Ｓ
　７０）と、肥大ブロック群抽出工程（Ｓ　８０）と、
ブロック形状調整工程（Ｓ　９０）と、ブロック離し工
程Ｂ（Ｓ１００）からなっている。

まず、前記基本格子配置工程（Ｓ　１０）は、各素子ブ
ロックを各素子ブロック間の結線数等の接続条件に基づ
いて面積を無視した基本格子に配置を行なうものであり
、第２図（Ａ）に示すように、各ブロックの基準点を格
子状に配置する。

そして、正方外形仮決め工程（Ｓ　２０）にて、第２図
（Ｂ）に示されるように前記基準点に対して、全ての素
子ブロックに所望面積の正方外形を与える。

次に、ブロック離し工程Ａ（Ｓ３０）は、各ブ０ツクの
正方外形に基づいて、各ブロックが互いに重ならないよ
うように、各素子ブロックを離す工程である。すなわち
、第１列のブロックの各最右辺より左側に第ｉ＋１列の
ブロックが存在する場合は、該当ブロックを最右辺の位
置まで移動する。例えば、第２図（Ｃ）に示すように、
ブロックＤの最右辺より左側に第２列のブロックＥが存
在するので、ブロックＥをブロックＤの最右辺に移動す
る。

そして、各ブロックの行方向に対しても同様にブロック
離し作業を行ない、第２図（Ｄ）のように、全ブロック
の重なりを除去する。

ここで、前記型なりを除去するために、各ブロック毎に
移動するので、各ブロック間に不必要な空きが生じる。

次に、ブロック詰め工程（Ｓ　４０）にて、前記ブロッ
ク離し工程（Ｓ　３０）で生じた各ブロック間の隙を詰
める。各素子ブロックをＸ方向及びＹ方向に平行移動し
て、第２図（Ｅ）に示すように各素子ブロックを詰める
。

そして、縮小率を算出する縮小率・縮小方向算出工程（
Ｓ　５０）にて、前記詰め工程（Ｓ　４０）で決定され
た外枠のＸ軸方向及びＹ軸方向の辺の長さと、所望チッ
プ枠のＸ軸方向及びＹ軸方向の辺の長さとを比較し、大
きい比の軸方向を縮小方向として出力する。例えば、第
３図（Ａ）において、前記ブロック詰め工程（Ｓ　４０
）にて決定された外枠のＸ軸方向の辺の長さが５０ＳＹ
軸方向の辺の長さが４６でり、所望のチップ枠の大きさ
をそれぞれ４５．４０とするとき、Ｘ軸方向の縮小率は
４５１５０＝０．９０となり、Ｙ軸方向の縮小率は４２
／４　Ｂ岬０．９１となる。このときの縮小方向は、縮
小率の高いＸ軸方向が選択される。

次に、終了判定工程（Ｓ　６０）は、前記両縮小率が０
．９９〜１．１の間となったときに、所望のチップ枠内
にブロック配置がなされたとして処理を打ち切るもので
ある。

従って、前記縮小処理判断工程（Ｓ　６０）にて、前記
縮小率が前記範囲外にあるときは、以下の手順で各ブロ
ックの縮小処理を行なう。

まず、有向グツ生成工程（Ｓ　７０）にて、前記縮小率
・縮小方向算出工程（Ｓ５０）にて選択された前記縮小
方向の有向グラフ、及び非縮小方向の有向グラフを生成
する。ここで、該有向グラフは、それぞれ軸方向の隣接
関係を示すグラフである。すなわち、第３図（Ａ）に示
されたブロック配置図に基づいたＸ軸方向（縮小方向）
の有向グラフは第４図（Ａ）　、Ｙ軸方向（非縮小方向
）の有向グラフは第４図（Ｂ）に示すようになる。

次に、肥大ブロック群抽出工程（Ｓ　８０）にて、前記
縮小方向に最も突出したブロックを探索し、該ブロック
から前記有向グラフを辿り縮小方向の辺の長さに影響を
及ぼす肥大ブロック群を抽出する。ここで、第３図（Ａ
）の例では、縮小方向即ちＸ軸方向に突出したブロック
はＣであり、該ブロックＣの配置に影響しているブロッ
クは、前記有向グラフを辿ると、ブロックＡ、Ｂ、Ｄ、
Ｅとなり、抽出される肥大ブロック群は、Ａ、Ｂ、Ｃ。

Ｄ、　　Ｅとなる。

次に、ブロック形状調整工程（Ｓ　９０）にて、前記抽
出された肥大ブロック群の縮小方向の各辺を前記縮小率
で縮小するとともに、非縮小方向の辺を同一面積となる
ように拡大する。すなわち、前記抽出された肥大ブロッ
ク群Ａ、Ｂ、Ｃ，Ｄ。

Ｅに対して、Ｘ軸方向の各辺を０．　９倍し、Ｙ軸方向
の辺の長さは、前記縮小されたＸ軸方向の辺の長さと、
予め与えられている各面積とから算出する。従って、第
３図（Ａ）に示されるブロック配置に対して、ブロック
形状調整工程（Ｓ　９０）を施せば、第３図（Ｂ）に示
すようになる。

そして、前記ブロック形状調整工程（Ｓ　９０）にて発
生したブロック間の重なりを非縮小方向の有向グラフ（
第４図（Ｂ））を辿りながら取り除＜（Ｓ１００）。す
なわち、形状調整工程（Ｓ９０）では非縮小方向（Ｙ軸
方向）のみにブロックの重なりが発生するので、非縮小
方向の離し作業を行えば、ブロックの重なりを確実に除
去することができる。

その後、ブロック枠が所望のチップ枠の大きさとなるま
で各工程（Ｓ　４０）〜（Ｓ　１００）を繰り返す。

また、終了判定工程（Ｓ　６０）にて、所望の比率とな
らなくても、前回の縮小率と比較して、改善効果が現れ
なければ、そこで終了する。

従って、本実施例によれば、各素子ブロックの縦横比を
変更するので、従来の固定形状ブロックの配置時より外
枠を小さくできるという利点を有する。

本発明における基本格子配置は、ペアリンキング法、ク
ラスタ成長法等の任意のものを使用することが可能とな
る。

［発明の効果］ 以上説明したように、本発明に係るＬＳＩの素子ブロッ
ク配置方法によれば、所望チップ枠内に全てのブロック
を収めることが可能となり、トップダウン的レイアウト
設計に非常に有効である。

また、結線数等の接続条件にて決まる初期配置結果（基
本格子配置結果）の相対位置関係を極力守ることができ
るので、ブロック間の配線経路の長さを短小にすること
ができる。

【図面の簡単な説明】

第１図は本発明に係るＬＳＩの素子ブロック配置方法の
概略手順図、 第２図及び第３図は本発明方法の適用した素子ブロック
配置状態の説明図、 第４図は本実施例による有向グラフの説明図である。

Claims (1)

1. 【特許請求の範囲】 ＬＳＩ基板上にそれぞれ所定の面積を有する複数個の素
   子ブロックを配置するＬＳＩの素子ブロック配置方法に
   おいて、 各素子ブロックを各素子ブロック間の結線数等の接続条
   件に基づいて面積を無視した基本格子に配置する基本格
   子配置工程と、 全ての素子ブロックに所望面積の圧力外形を与える正方
   外形仮決め工程と、 各ブロックの正方外形に基づいて、各ブロックが互いに
   重ならないように各素子ブロックを離すブロック離し工
   程Ａと、 前記離し工程Ａで生じた各ブロック間の隙を詰めるブロ
   ック詰め工程と、 前記詰め工程で決定された外枠のＸ軸方向及びＹ軸方向
   の辺の長さと、所望チップ枠のＸ軸方向及びＹ軸方向の
   辺の長さとを比較し、大きい比の軸方向を縮小方向とし
   、縮小率を算出する縮小率・縮小方向算出工程と、 各ブロック間の前記縮小方向の有向グラフ、及び非縮小
   方向の有向グラフを生成する有向グラフ生成工程と、 前記縮小方向に最も突出したブロックを探索し、該ブロ
   ックから前記縮小方向の有向グラフを辿り縮小方向の辺
   の長さに影響を及ぼす肥大ブロック群を抽出する肥大ブ
   ロック群抽出工程と、 前記抽出された肥大ブロック群の縮小方向の各辺を前記
   縮小率で縮小するとともに、非縮小方向の辺を同一面積
   となるように拡大するブロック形状調整工程と、 前記ブロック形状調整工程で発生したブロック間の重な
   りを非縮小方向の有向グラフを辿りながら取り除くブロ
   ック離し工程Ｂと、 からなり、前記外枠が所望チップ枠の大きさとなるまで
   、前記ブロック詰め工程、縮小率・縮小方向算出工程、
   有向グラフ生成工程、肥大ブロック群抽出工程、ブロッ
   ク形状調整工程及びブロック離し工程Ｂを繰り返すこと
   を特徴とするＬＳＩの素子ブロック配置方法。