(57)【特許請求の範囲】
【請求項１】
二分木生成手段とパッキング手段とを含むコンピュータが実行するマクロ配置の方法であって、
前記二分木生成手段が、Ｋ個のブランチノードとＫ＋１個のパッキングサブツリーとを有するＫレベルのマルチパッキング二分木を生成する工程と、
前記パッキング手段が、前記Ｋ＋１個のパッキングサブツリーがそれぞれ有する一群のマクロを配置領域にパッキングする工程と、
を含み、
前記Ｋ個のブランチノードは前記Ｋレベルにそれぞれ対応し、
前記Ｋ＋１個のパッキングサブツリーのそれぞれは前記Ｋ個のブランチノードのいずれか１つに対応し、
前記の各パッキングサブツリーのマクロは配置領域の一つの方向に、配置領域の一つの端に、または配置領域の一つのコーナーにパックされ、各パッキングサブツリーに対応する前記方向、端、またはコーナーは他と異なることを特徴とするマクロ配置の方法。
【請求項２】
マルチパッキングツリー（ＭＰＴ）マクロ配置器であって、
ＬＥＦ／ＤＥＦフォーマットで入力ファイルを読み取る手段と、
Ｋ個のブランチノードと、一群のマクロをそれぞれが有するＫ＋１個のパッキングサブツリーとを有するＫレベルのマルチパッキング二分木を生成する手段と、
前記Ｋ＋１個のパッキングサブツリーがそれぞれ有する一群のマクロを配置領域にパッキングする手段と、
前記マクロのパッキング結果に基づき、前記Ｋレベルのマルチパッキング二分木を最適化する手段と、
ＤＥＦフォーマットで出力ファイルを生成する手段と、
を含み、
前記Ｋ個のブランチノードは前記Ｋレベルにそれぞれ対応し、
前記Ｋ＋１個のパッキングサブツリーのそれぞれは前記Ｋ個のブランチノードのいずれか１つに対応し、
前記の各パッキングサブツリーのマクロは配置領域の一つの方向に、配置領域の一つの端に、または配置領域の一つのコーナーにパックされ、各パッキングサブツリーに対応する前記方向、端、またはコーナーは他と異なることを特徴とするマクロ配置器。
【請求項３】
更に、前記マクロのパッキング後、マクロ間の間隔を調整する手段を含むことを特徴とする請求項２に記載のマクロ配置器。
【請求項４】
更に、前記入力ファイルを読み取った後に、同一群の設計序列中の同じ高さ／ 幅を有する前記マクロをクラスタ化する手段と、前記出力ファイルを生成する前に、前記マクロをクラスタ分離する手段と、を含むことを特徴とする請求項２に記載のマクロ配置器。
【請求項５】
前記最適化する手段は、焼きなましループの繰り返しからなり、
前記焼きなましループの繰り返しは、前記マルチパッキングツリーを摂動する工程と、前記マルチパッキングツリーで前記マクロをパッキングする工程と、パッキングのマクロ配置を評価する工程と、前記マクロ配置を受け入れるか、却下する工程と、からなることを特徴とする請求項４に記載のマクロ配置器。
【請求項６】
前記焼きなましループは、更に、与えられたマクロ配置制限に従い、前記マルチパッキングツリーの構造を修正する工程を含むことを特徴とする請求項５に記載のマクロ配置器。
【請求項７】
入力ファイルを読み取る手段と出力ファイルを生成する手段と第１のマクロ配置器と請求項４に記載されたマクロ配置器とを含むコンピュータが実行する多尺寸混合配置設計方法であって、
前記入力ファイルを読み取る手段が、ＬＥＦ／ＤＥＦフォーマットで初期入力ファイルを読み取る工程と、
前記第１のマクロ配置器が、準備段階のマクロ配置を実行する工程と、
前記請求項４に記載されたマクロ配置器が、詳細なマクロ配置を実行する工程と、
前記出力ファイルを生成する手段が、ＤＥＦフォーマットで最終的な出力ファイルを生成する工程と、を含むことを特徴とする設計方法。
【請求項８】
前記コンピュータは標準セル配置を実行する手段を更に含み、
更に、前記標準セル配置を実行する手段がＤＥＦフォーマットで最終的な出力ファイルを生成する前に標準セル配置を実行する工程を含むことを特徴とする請求項７に記載の設計方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、集積回路の多尺寸混合設計、すなわち混合サイズ設計に関するものであって、特に、パッキングベースのマクロ配置に関するものである。
【背景技術】
【０００２】
知的財産(intellectual property；IP)モジュールと内蔵メモリの使用により、現代のVLSIチップは多数のマクロを含む。複数のマクロと標準セルとの多尺寸混合配置は異なる応用分野において一般的になり、様々な刊行物で多くの多尺寸混合配置アルゴリズムが開示されている。
【０００３】
第一種の多尺寸混合配置アルゴリズムはマクロと標準セルを同時に配置し、通常、マクロ方向を考慮せず、且つ、強大なマクロリーガライザー（macro legalizer）を必要とし、マクロ／セルが適当に分布されていない時の重畳を除去する。C.−C. Chang 等は、2003年に、「Proceedings of ACM/IEEE Asia South Pacific Design Automation Conference」中で、 焼きなまし(simulated annealing)によるマルチレベル配置器(multilevel placer)mPG−MSを開示し、一層ずつ大きいマクロから小さいマクロに順に固定する。A. Khatkhate等は、2004年に「Proceedings of ACM International Symposium on Physical Design」で、最少切割(min−cut)式配置器、“風水”（Feng Shui）を開示し、この小部分切割 (fractional cut)方式は、標準セルとマクロを同時に考慮し、水平切割線は列との境界で整列しない。この他、数種の分析方式が提出され、多尺寸混合配置を達成する。
【０００４】
A. B. Kahng等により、2004年に「IEEE/ACM International Conference on Computer−Aided Design」でAPlaceが開示され、非線形プログラミング(non−linear programming)に基づき、鐘形(bell−shaped)のポテンシャル関数(potential function)により、マクロの高さ/幅を考慮して、マクロとセルを均一に分布する全体配置を決定する。T. Chan等により、2005年に「Proceedings of ACM International Symposium on Physical Design」でmPLが開示され、一般化された力の方向 (generalized force−directed)により配置を行う。B. Yao等により、2005年に「Proceedings of ACM International Symposium on Physical Design」でUPlaceが開示され、二次計画法(quadratic programming)、及び、離散コサイン変換方法により、マクロ/セルを適当に配置し、且つ、ゾーン微調整(zone refinement)を使用する。
【０００５】
第二種の配置方法は、平面計画(floor planning)と配置技術を結合し、2004年に「IEEE/ACM International Conference on Computer−Aided Design」で開示された最少切割平面配置器(floor  placer)Capoを一例とし、必要時、最少切割平面配置の実行時に、固定輪郭(fixed−outline)平面計画により、マクロの使用可能位置を探し、平面計画配置の嵌入配置工程中、マクロの配置方向が考慮でき、正当な方案が容易に探し出せる。
【０００６】
第三種の配置方法は、多尺寸混合配置を二段階に分け、それぞれ、マクロ配置と標準セル配置であり、マクロの位置を先に決定し、標準セルをその残りの領域に配置する。S. N. Adyaが、2005年に「ACM Transactions on Design Automation of Electronic Systems」でこの組み合わせ技術を開示し、標準セル配置器により最初の配置を得て、この最初の配置結果により、標準セルを数個のソフトマクロ(soft macro)に分け、その後、固定輪郭平面計画により、無重畳(overlap−free)マクロ配置を探す。その後、マクロの位置を固定し、標準セル配置器は標準セルを新たにその他の空間で配置する。その他の形式と比較すると、無重畳のマクロ配置を獲得するので、二段階の多尺寸混合配置は有効な配置方案の保有を保証し、よって、信頼性がある。更に、マクロ方向と配置の制限条件、例えば、プレ配置マクロ (pre−placed macro)と配置障害(placement blockage)等が容易に処理される。
【０００７】
【非特許文献１】C.−C. Chang 等、「Proceedings of ACM/IEEE Asia South Pacific Design Automation Conference」
【非特許文献２】A. Khatkhate等「Proceedings of ACM International Symposium on Physical Design」
【非特許文献３】A. B. Kahng等「IEEE/ACM International Conference on Computer−Aided Design」
【非特許文献４】T. Chan等「Proceedings of ACM International Symposium on Physical Design」
【非特許文献５】B. Yao等「Proceedings of ACM International Symposium on Physical Design」
【非特許文献６】「IEEE/ACM International Conference on Computer−Aided Design」
【非特許文献７】S. N. Adya「ACM Transactions on Design Automation of Electronic Systems」
【発明の開示】
【発明が解決しようとする課題】
【０００８】
本発明は、パッキングベースのマクロ配置方法とそれを用いた半導体チップを提供し、上述の状況を改善することを目的とする。
【課題を解決するための手段】
【００１２】
Kレベル（K個のレベル）の二進数マルチパッキング二分木（binary multi−packing tree）の具体例は、Kブランチノード（k個のブランチノード）とK＋1パッキングサブツリー（K＋1個のパッキングサブツリー）を有する。Kブランチノードはそれぞれ一つのレベルに対応する。K＋1パッキングサブツリーはそれぞれ一群のマクロを有し、ノードの一つに対応する。
【００１３】
マクロ配置の方法の具体例は、前述のKレベルマルチパッキング二分木を生成し、各配置領域で、各パッキングサブツリーのマクロをパッキングする工程からなる。
【００１４】
マルチパッキングツリー（MPT） マクロ配置器（macro placer）の具体例は、ＬＥＦ／ＤＥＦフォーマットで入力ファイルを読み取る手段と、Ｋ個のブランチノードと、一群のマクロをそれぞれが有するＫ＋１個のパッキングサブツリーとを有するＫレベルのマルチパッキング二分木を生成する手段と、前記Ｋ＋１個のパッキングサブツリーがそれぞれ有する一群のマクロを配置領域にパッキングする手段と、前記マクロのパッキング結果に基づき、前記Ｋレベルのマルチパッキング二分木を最適化する手段と、ＤＥＦフォーマットで出力ファイルを生成する手段と、を含む。前記Ｋ個のブランチノードは前記Ｋレベルにそれぞれ対応し、前記Ｋ＋１個のパッキングサブツリーのそれぞれは前記Ｋ個のブランチノードのいずれか１つに対応する。
【００１５】
多尺寸配置設計（混合サイズの配置設計）の工程の具体例は、入力ファイルを読み取る手段と出力ファイルを生成する手段と第１のマクロ配置器と請求項４に記載されたマクロ配置器とを含むコンピュータが実行する多尺寸混合配置設計方法であって、前記入力ファイルを読み取る手段が、ＬＥＦ／ＤＥＦフォーマットで初期入力ファイルを読み取る工程と、前記第１のマクロ配置器が、準備段階のマクロ配置を実行する工程と、前記請求項４に記載されたマクロ配置器が、詳細なマクロ配置を実行する工程と、前記出力ファイルを生成する手段が、ＤＥＦフォーマットで最終的な出力ファイルを生成する工程と、を含む。
【００１６】
マクロ配置を評価するコスト機能の具体例は、マクロ配置の領域の少なくとも一つのパラメータ、真ネットと偽ネットの総線長、準備段階のマクロ配置からの総マクロ移動、マクロ配置の重畳長さ、及び、マクロ配置の厚さ、を含む。
【００１７】
本発明は、マルチパッキングツリー（MPT）ベースのマクロ配置器（macro placer）を提供し、マクロを配置領域の境界付近に配置し、標準セルのために中心を留保する。MPTマクロ配置器は、MPTを対応するマクロ配置に変換するのに必要な線形時間だけを要し、よって、二分木（binary tree）の操作とパッキングは非常に速い。その結果、マクロ配置の方策は焼きなまし（simulated annealing）により効果的に調査される。パッキング技術は、更に、領域縮小化にも効率的かつ効果的で、MPTベースのマクロ配置器は、大きいマクロと多数のマクロにより、多尺寸混合配置問題を解決する。マクロ方向とマクロ間の配置が考慮されるので、MPTベースのマクロ配置器は公知の多尺寸混合配置器より更に短い線長になり、且つ、密集を緩和する。MPTベースのマクロ配置器は、様々な配置制限、例えば、プレ配置ブロック、コーナーブロック、配置障害（placement blockage）等下でも容易に正常に作動することができる。MPTベースマイクロ配置器は最先端の標準セル配置器と結合し、二段階の多尺寸混合工程に基づき、好ましい多尺寸混合配置の方案（solution）を得ることができる。
【発明の効果】
【００１８】
本発明のマルチパッキングツリーマクロ配置器は巨大なマクロ、及び、大量のマクロの多尺寸混合配置を実行することができ、マクロ方向とマクロ間の間隔は既に考慮されているので、マルチパッキングマクロ配置器は公知の多尺寸混合配置器より短い線長を生成し、且つ、過度に密集せず、マルチパッキングマクロ配置器は異なる配置制限条件（プレ配置ブロック、コーナーブロック、配置障害）下で容易に正常作動する。また、マルチパッキングツリーマクロ配置器は最新の標準セル配置器と結合して、二段階の多尺寸混合配置工程に基づいて、好ましい多尺寸混合配置の方案を得ることができる。
【発明を実施するための最良の形態】
【００１９】
図１は多尺寸（すなわち異なるサイズの）混合配置のフローチャートである。本発明の設計戦略（strategy）による特徴の一つは、マクロをチップの周辺に配置し、チップ中央を標準セルに留保することである。マクロは通常大きく、且つ、マクロ中にルーティング障害（routing blockage）を有するので、マクロがチップの中央に配置される場合、ルーティングに大きく影響する。公知の平面計画技術は全てのマクロを一コーナーにパックするので、マクロ配置問題に直接適用できない。この問題を解決するため、新しいパッキングツリー表示法に基づき、新しいマルチパッキングツリー平面計画表示法を提供し、マクロをチップ周辺に配置する。
【００２０】
パッキングツリー（Packing−tree）は平面計画（floorplan）を非切割（non−slicing）、或いは、切割（slicing）する二分木（バイナリーツリー）である。パッキングツリーの各ノードはマクロブロックに対応する。パッキングツリーのパッキングは四種ある。左下、左上、右上、右下（BL、TL、TR、BR）パッキングで、それぞれ、左下、左上、右上、右下のコーナーに向かって複数のブロックをパックする。
【００２１】
図２はパッキングツリーと対応する四種のパッキング配置を示す図である。(xcorner, ycorner)はコーナーの座標で、(xi, yi)はブロックbiの左下の座標で、且つ、wi (hi)はブロックbiの幅と高さとすると、パッキングツリーの根座標（root cordinate）は、
左下パッキング（BL−packing）では、(cx, cy)；
左上パッキング（TL−packing）では、 (cx, cy − hroot)；
右上パッキング（TR−packing）では、 (cx − wroot, cy − hroot)；及び
右下パッキング（BR−packing）では、 (cx − wroot, cy)。
【００２２】
ノードnjがniの右チャイルド（右の子）の場合、ブロックbjは、
左下パッキングでは、右側最低の相隣ブロックで、且つ、xj = xi ＋ wi ；
左上パッキングでは、右側最高の相隣ブロックで、且つ、xj = xi ＋ wi ；
右上パッキングでは、左側最高の相隣ブロックで、且つ、xj = xi − wj ；
右下パッキングでは、左側最低の相隣ブロックで、且つ、xj = xi − wj 。
【００２３】
ノードnjがniの左チャイルド（左の子）の場合、ブロックbjのx軸座標は、以下のように定義される。
左下パッキングでは、xj = xi ；
左上パッキングでは、xj = xi ；
右上パッキングでは、xj = xi ＋ wi − wj ；
右下パッキングでは、xj = xi ＋ wi − wj 。
【００２４】
左下と右下（BLとBR）パッキングにとって、ブロックbjはbiの上にあり、左上と右上（TLとT）パッキングにとって、ブロックbjはブロックbiの下にある。したがって、一つのパッキングツリーが与えられると、全てのブロックのx軸座標は、ツリーを線形時間でいちど処理（traverse）することにより決定される。更に、y軸座標は、輪郭データ構造により償却一定時間で、既知の方法と同様にして計算される(2000年「Proceedings of the ACM/IEEE Design Automation Conference」の第 458−463ページのA new representation for non−slicing floor plansを参照)。よって、パッキングツリーを対応する配置に転換する複雑度は償却線形時間である。注意すべきことは、B*−tree平面計画は左下のパッキングツリーで表示される。
【００２５】
マルチパッキングツリーは、幾つかの異なるコーナーに位置する異なるパッキング型のパッキングツリーを結合したものである。一般のマルチパッキングツリーの例が図３で示され、マルチパッキングツリーは、K幹ノード（K個のstem  nodes）を有し、K＋1パッキングサブツリー（K＋1個のpacking sub−trees）を結合している。便宜上、及び、分かりやすい実施のために、右向き幹（stem）が使用されて複数のパッキングサブツリーを結合し、且つ、サブパッキングツリーの順番はパッキングサブツリーの親ノードのレベルにより決定される。ツリー処理の深さ優先探索(depth−first search；DFS)順序がツリーパッキングに用いられるので、レベルが低くなるほど、サブツリーのパッキングが早くなる。二つのパッキングサブツリーの親が同じである場合、左チャイルドに位置するパッキングサブツリーがまずパッキングされる。一般のマルチパッキングツリーはいかなる直線的平面計画領域もモデル化し、各パッキングサブツリーは一つの凸面のコーナーのパックを実行する。
【００２６】
同様に、マルチパッキングツリーの深さ優先探索（DFS）により、ブロックのX軸座標を決定する。Y軸座標を計算するため、下方輪郭と上方輪郭を固定し、下方輪郭と上方輪郭はそれぞれ、直線的領域の下側と上側により決定される。全ての左下と右下のパッキングツリーは下方輪郭データ構造を使用し、全ての左上と右上のパッキングツリーは上方輪郭データ構造を使用する。図４は、左下（BL）パッキングツリーと右下（BR）パッキングツリーを有するマルチパッキングツリーのパッキングの例を示す図である。輪郭により先にパッキングされたブロックの空間が留保されるので、相同の輪郭データ構造を使用するパッキングツリーは無重畳配置を生成する。これにより、左下／右下パッキングツリーは、左上／右上のパッキングツリーとだけ重畳する可能性がある。しかし、この種の配置方法は実現可能なものではないので放棄される。
【００２７】
一般の長方形のVLSIチップ領域は、通常、四つのパッキングサブツリーを有するマルチパッキングツリーにより処理し、その範例が図５Aで示される。対応するマクロ配置を得るため、マルチパッキングツリーは根n0から深さ優先探索（DFS順序）により処理される。n0が幹ノードであるので、処理せずそのまま工程を継続し、n0の左側チャイルドn3は左下パッキングツリーの根で、ブロックb3は左下コーナーに配置される。ノード n3は左側チャイルドがないので、n4を処理し、以下同様である。この範例中、パッキングサブツリーは、左下、左上、右上、右下（BL、TL、TR、BR）パッキングツリーの順に処理され、全ノードの処理後、図５Bで示されるマクロ配置が得られる。
【００２８】
問題のサイズを縮小させるためマクロクラスタリングが用いられる。同一群の設計序列中の同じ高さ／幅を有する複数のマクロはクラスタ化される。これらのマクロは一般に密接な関連を有し、マクロのクラスタリングは領域を効果的に使用するだけでなく、密接に関連するマクロを緊密に配置する。浪費される領域がない時、クラスタ寸法だけが考慮される。図６は四ブロックのクラスタの例で、クラスタマトリックスの三つの可能な尺寸、1×4、2×2及び4×1を示す。
【００２９】
クラスタ分離時、ブロックは現在のクラスタマトリクスにより配置される。分岐限定法（branch and bound）により配置コストに従ってブロックの最適順序を決定する。
【００３０】
ユーザーにより配置障害が定義され、障害と重畳するマクロがなくなる。パッキングの間、新しいマクロブロックが追加され、障害と重畳しないか確認する。重畳する場合、ブロックのY軸座標が重畳しない位置にシフトされる。図７を範例とすると、新しいブロックb2を追加すると、配置障害と重畳するので、ブロックb2は上にシフトされ、重畳の発生を回避し、輪郭もブロックb2の位置に基づき更新される。プレ配置マクロが配置障害とみなされ、よって、対応するノードはマルチパッキングツリー中に生成されず、これにより、プレ配置マクロの位置を確保する。
【００３１】
コーナーマクロが以下で説明される。アナログブロックは通常、コーナーにコーナーマクロとして固定される。コーナーブロックに対応するノードはパッキングサブツリーの根として固定される。よって、コーナーマクロはコーナーに固定される。
【００３２】
直線的マクロ（rectilinear macro）が以下で説明される。ツリーベース平面計画に対し、公知の方法（G.−M. Wu, Y.−C. Chang, and Y.−W. Chang等による、2003年「ACM Trans. on Design Automation of Electronic Systems」の188−202ページで発表されたRectilinear block placement using B*−trees)が採用されて、直線的マクロを処理する。直線的マクロは数個の長方形ブロックに切割され、ツリートポロジー (tree topology)に従って位置制限(LC)を生成し、パッキング実行時、ミスアラインメント(misalignment)の状況が修正されて、長方形ブロック形状を維持する。図８で示されるように、直線的ブロック（rectilinear block）は三つの長方形ブロックに切割され、且つ、ノードn1、n2及びn3は位置制限の関係を維持する。
【００３３】
マルチパッキングツリーの演算は以下のようであり、マルチパッキングツリーは下記の演算により摂動（perturb）されもう一つのマルチパッキングツリーを得る。
演算１：ブロック（クラスタ）を旋転させる
演算２：クラスタのサイズ変更する
演算３：パッキングサブツリーのノードをもう一つの場所に移動させる
演算４：一つ、或いは、二つのパッキングサブツリー中の二ノードを交換する
演算５：二パッキングサブツリーを交換する
【００３４】
演算１で、ブロック（クラスタ）はツリーノードに回転させ、演算２で、クラスタのクラスタリング尺寸が変化する。演算１と２はマルチパッキングツリー構造に影響しない。演算３で、ノードはパッキングサブツリーから選択され、同一の、或いは、別のパッキングサブツリーの別の場所へ移動させる。演算４で、二ノードは一（二）パッキングサブツリーから選択され、交換される。演算５で、二パッキングサブツリーが交換され、二パッキングサブツリー交換のパッキング順序を交換する。注意すべきことは、マルチパッキングツリーの幹構造は固定であり、あらゆるタイプの操作にも影響されないことである。
【００３５】
マクロ配置の評価が以下で説明される。マクロ配置結果の品質を見分けるため、マクロ配置Fのコストが以下のように定義される。
Φ＝αA＋βW＋γD＋δO＋εT
Aはマクロ配置領域、Wは総線長、Dは総マクロ移動、Oは垂直重畳長さを示し、且つ、α、β、γ及びδは使用者が定義する重みパラメータ(weighting parameter)である。マクロ配置領域、線長、垂直重畳長さは以下のパラグラフで示される。
【００３６】
マクロ配置領域は下方輪郭以下の面積に上方輪郭以上の面積を加えたもので、図９Aで示されるように、輪郭は粗い点線で示され、対応するマクロ配置面積は図９Bで示される。マクロ配置面積最小化はマクロにより包囲される島状の標準セル領域の大量生成を防ぐことができ、マクロブロック上に多くのルーティング障害があるので、この種の領域からチップ中央へのルーティングは非常に難しい。更に、この種の領域中の標準セルは標準セルに接続し、チップ中央に配置させるのに長いルーティング経路を必要とし、タイミングが悪くなる。
【００３７】
線長については、配置時、マクロだけが考慮されるので、回路のネットリストは直接使用できず、設計序列が用いられ、同一設計序列群中のマクロブロック間に偽ネットを生成し、これにより、総線長の最小化は同一設計序列中のマクロブロックを緊密に維持する。
【００３８】
マクロ配置は全体配置結果により導引され、全体配置は完全にエラーなしである必要が無く、既知のマクロの位置が摘出された後、マクロ移動が費用函数の負指標として加えられ、最小のマクロ移動の最適マクロ配置を得ることができる。
【００３９】
マルチパッキングツリー表示法は上方と下方のパッキングサブツリー間で重畳がないことを保証するが、上方輪郭と下方輪郭間は垂直な重畳がある可能性があり、垂直な重畳は費用函数の負指標に加えられ、焼きなましを導引して重畳がない配置方案を探し出す。
【００４０】
図１０はマクロ配置の工程を示す図で、LEF／DEFファイルが読み取られた後、相同の設計序列に位置し、且つ、相同の高さと幅を有するマクロがまずクラスタ化される。クラスタ寸法は最も方形に近い尺寸を初期値とし、最後の尺寸は焼きなましの最適過程中で選定される。
【００４１】
その後、所与の数のパッキングサブツリーを有するマルチパッキングツリーが生成され、各マクロ／クラスタはパッキングサブツリーのノードに対応する。初期のマクロ位置が与えられる場合、初期のパッキングサブツリーはマクロの最も近いコーナーに従って、所属するノードに割り当てられる。そうでなければ、所属するノードの初期のパッキングサブツリーはランダムに設定され、各パッキングサブツリーは完全な二分木として初期化される。
【００４２】
焼きなまし（simulated annealing）が用いられ、最適なマクロ配置を探す。上述の操作により、マルチパッキングツリーが摂動（perturb）され、もう一つのマルチパッキングツリーを得る。摂動後、設計者はツリー構造を修正して既存のマクロ配置制限条件を満足させ、マルチパッキングツリーをパックし、マクロ配置を評価し、マクロ配置品質の差異と焼きなましの現行温度により、新しい配置方案が受け入れられるか決定し、その後、マルチパッキングツリーは再度摂動され、配置方案が充分によいか、更に好ましい配置方法が出現しなくなるまで焼きなましが継続され、その後、全部ブロック／クラスタの位置が決定される。
【００４３】
全ブロック／クラスタの位置決定後、クラスタ内のブロックの位置はクラスタのマトリクス尺寸により計算される。
【００４４】
最後に、マクロ間の間隔が修正される。二マクロ間の間隔がマクロ間の元の間隔より高い場合、マクロ間の間隔は追加され、そうでなければ、元の間隔が縮小されてマクロ配置面積を更に小さくし、マクロの方向も水平、或いは、垂直の反転により決定され、大部分のピンはチップの中心に接近し、その後、全マクロの状態が固定され、最終のマクロ配置が出力される。
【００４５】
二組のテスト回路（ベンチマーク）が使用され、多尺寸混合マクロ配置に対し比較検証を実行した。テスト回路はそれぞれ、S. N. Adyaが2005年に「ACM Transactions on Design Automation of Electronic Systems」で提出したファラデー(Faraday) 、及び、五種の最近の大型実際設計でなるmchipである。表Iはファラデー(Faraday) ベンチマークの統計データで、注意すべきことは、DMA回路はマクロがないので、比較検証を実施せず、各デジタル信号処理 (DSP)及び縮小命令セットコンピュータ(RISC)回路中にそれぞれ二個、及び、７個のマクロを有し、これらのテスト回路中、マクロの面積は総チップ面積の6.96％から41.99％を占める。
【００４６】
表 I
0004474404.tif 000002
【００４７】
表IIは、“風水”5.1、Capo9.4、Capoと組合わせた本発明のマルチパッキングツリー配置器、mPL5、APlace2.0、及び、Aplaceと組合わせた本発明のマルチパッキングツリー配置器のファラデー・ベンチマークでのルーティング結果である。最新の商用ルータが用いられ、全配置方案に対しルーティングが実行される。全配置器は、２GBRAMを有する3.2GHzのPentium（登録商標） 4のLinuxワークステーション上で実行される。半週線長HPWL(half perimeter wirelength)とルーティング線長WL(routing wirelength)がデータベースユニット(database unit)により報告され、Violはルーティング方案の違反数である。マクロの数量が少ないので、マルチパッキングツリー配置器は数秒で完成し、マクロ配置の単独実行時間は報告されず、表II中の*マークは配置の結果が多くの重畳を有することや、或いは、ブロックが配置領域外にあり、且つ、認可されないことを示し、表II中のNRは受け入れられる配置がないので、配置結果が無いことを示す。
【００４８】
表 II
0004474404.tif 000003
【００４９】
これらの結果から分かるように、最小切割工程の配置器“風水”は多くのマクロ／セルをチップ領域外にする結果を生成する。mPL5は多尺寸混合配置器であるといっていないが、mPL5は多尺寸混合マクロ、及び、標準セルを有するIBM−MS/IBM−MSw Pinsテスト回路に対し高品質の配置方案を生成する。これにより、mPL5のファラデー(Faraday)テスト回路に対する配置結果は参考として実行した。mPL5は受け入れられる配置方案を探し出すが、その品質は理想的でない。この他、APlaceはDSP1、RISC1とRISC2の間で多くの重畳を生成し、且つ、認証されない。よって、全面配置方案の半週線長だけが報告される。最小切割の平面計画配置器Capoは認証配置方案を探し、且つ、半週線長は“風水”とmPL5に比べてよい。
【００５０】
本発明の実施例によるマルチパッキングツリーマクロ配置器の二段階の多尺寸混合配置方法を使用し、全回路に対し受け入れられる配置方案を探し出すことができ、単独でCapoを使用するのと比べて、Capoと組合わせたマルチパッキングツリーマクロ配置器は平均で半週線長を８％、及び、ルーティング線長は１２％縮小する。特に、APlaceと組合わせたマルチパッキングツリーマクロ配置器は全回路に対し有効な配置方案を生成し、且つ、その品質は全多尺寸混合配置器よりも優れ、mPL5、“風水”とCapoと比較すると、半週線長は、それぞれ、63％、35％、15％短縮し、mPL5、“風水”とCapoを比較すると、ルーティング線長は、それぞれ、62％、68％、15％短縮する。同時に分かるのは、マクロの面積が増加する時、本発明の実施例のマルチパッキングツリーマクロ配置器の配置工程を使用すると、半週線長の短縮成果が更に顕著であることで、線長の短縮効果は表IIIで示され、マルチパッキングツリーマクロ配置器の功能を説明する。
【００５１】
表 III
0004474404.tif 000004
【００５２】
表IVはmchipテスト回路の統計データであり、セルの数量は、540kから1320kで、且つ、マクロの数量は50から380で、Capoだけが多くのマクロの多尺寸混合配置に対し受け入れられる高品質の配置方案を決定することが出来ることが分かり、よって、Capoだけに対しマクロ配置の比較を実行し、実験はデュアルオプテロン 2.6GHz機器の上で実行され、それぞれ、マルチパッキングツリーマクロ配置器、及び、Capoによりマクロの位置を決定する。その後、マクロの位置を固定し、標準セルは、商用の 未収駆動(congestion−driven)の配置器により快速プロトタイピングモード(fast prototyping mode)で配置され、商用ルーターは全面ルーティングを実行し、公平な比較のため、標準セルは相同の配置器により配置を実行する。
【００５３】
表 IV
0004474404.tif 000005
【００５４】
表Vは半週線長（HPWL）、ルーティング線長（WL）、グローバルルーティングセル（GRC）オーバーフロー、及び、最大オーバーフローを示し、GRCオーバーフローは全面ルーティングセルがオーバーフローを有する比率であり、その値が高いほど、配置上の障害が多い。最大オーバーフローは、最大オーバーフローを有する全面ルーティングセルに割り当てられる最大トラック数を提供する。表V中のNRは、Capo中のセグメントエラーのために配置結果が獲得できないことを示す。
【００５５】
表 V
0004474404.tif 000006
【００５６】
5組のmchipテスト回路にとって、マルチパッキングツリーマクロ配置器はCapoのマクロ配置より更に好ましい線長（半週線長とルーティング線長）を獲得することができ、且つ、mchip 5テスト回路にとって、Capoの使用時、セグメントエラーが生じ、配置方案が見つからず、更に、Capoの配置結果は多くのGCRオーバーフロー、及び、最大オーバーフローを生成し、マルチパッキングツリーマクロ配置器より、更に多くのセル配置とルーティング実行時間を必要とする。
【００５７】
本発明は、マルチパッキングマクロ配置器を提供し、マクロ配置を配置領域の境界付近にし、中央領域を標準セルに＜保留＞留保する。このマルチパッキングツリーマクロ配置器は、マルチパッキングツリーを対応するマクロ配置に転換するのに償却線形時間（amortized linear time）だけ必要なので、演算上、及び、二分木でパッキングを実行するのは迅速であり、焼きなまし（simulated annealing）により効果的にマクロ配置方案を探し出す。マルチパッキングツリーマクロ配置器は巨大なマクロ、及び、大量のマクロの多尺寸混合配置を実行することができる。マクロ方向とマクロ間の間隔は既に考慮されているので、マルチパッキングマクロ配置器は公知の多尺寸混合配置器より短い線長を生成し、且つ、密集を抑制する。マルチパッキングマクロ配置器は異なる配置制限条件（プレ配置ブロック、コーナーブロック、配置障害）下で容易に正常作動する。マルチパッキングツリーマクロ配置器は最新の標準セル配置器と結合して、二段階の多尺寸混合配置工程に基づいて、好ましい多尺寸混合配置方案を得ることができる。
【００５８】
本発明では好ましい実施例を前述の通り開示したが、これらは決して本発明を限定するものではなく、当該技術を熟知する者なら誰でも、本発明の精神と領域を脱しない範囲内で各種の変動や潤色を加えることができ、従って本発明の保護範囲は、特許請求の範囲で指定した内容を基準として変更や類似を含み最大限に広く解釈されるべきである。
【図面の簡単な説明】
【００５９】
【図１】多尺寸混合装置の工程図である。
【図２】パッキングツリーと四種のパッキングを示す図である。
【図３】一般的なマルチパッキングツリーを示す図である。
【図４】左下（BL）パッキングツリーと右下（BR）パッキングツリーを有するマルチパッキングツリーのパッキングの例を示す図である。
【図５Ａ】四つのパッキングサブツリーを有するマルチパッキングツリーを示す図である。
【図５Ｂ】四つのパッキングサブツリーを有するマルチパッキングツリーで、全ノードの処理後のマクロ配置を示す図である。
【図６】クラスタマトリクスの三種の尺寸を示す図である。
【図７】配置障害を処理する工程を示す図である。
【図８】直線ブロックを複数の長方形ブロックに切割したことを示す図である。
【図９Ａ】マクロ配置結果と上／下輪郭を示す図である。
【図９Ｂ】図９Aに対応するマクロ配置面積を示す図である。
【図１０】マクロ配置の工程図である。
【符号の説明】
【００６０】
n0、n1、n2、n3、nk〜ノード；
b0、b1、b2、b3、bk〜ブロック；
T0、T1、T2、T3、Tk〜パッキングサブツリー。
【図１】
0004474404.tif 000007
【図２】
0004474404.tif 000008
【図３】
0004474404.tif 000009
【図４】
0004474404.tif 000010
【図５Ａ】
0004474404.tif 000011
【図５Ｂ】
0004474404.tif 000012
【図６】
0004474404.tif 000013
【図７】
0004474404.tif 000014
【図８】
0004474404.tif 000015
【図９Ａ】
0004474404.tif 000016
【図９Ｂ】
0004474404.tif 000017
【図１０】
0004474404.tif 000018