考慮效能與製造性之現代化超大型積體電路平面規劃與置放

Modern VLSI Floorplanning and Placement Considering Performance and Manufacturability

陳東傑(Tung-Chieh Chen)

指導教授 ： 張耀文

國立臺灣大學/電機資訊學院/電子工程學研究所/博士(2008年)

https://doi.org/10.6342/NTU.2008.01235

摘要

隨著奈米積體電路技術的進步，設計複雜度以爆炸性的成長。現代化的晶片設計通常含有數百萬個電晶體，而含有數十億電晶體的設計也逐漸量產普及。對於這些龐大且複雜的設計，平面規劃和置放系統的重要性益增；因為平面規劃和置放決定了晶片上所有元件的位置，而這些元件的位置影響著晶片的線長、可繞度、時序、可製造性等。因此，發展新的平面規劃和置放演算法是迫切所需的。
由於目前晶片上廣泛地重複使用智慧財產模組和嵌入式記憶體，晶片中通常含有大量的大型巨集模組。而且在現代化的晶片中，大型巨集模組的數量遽增。在現代化的設計中，一個晶片可能含有數百個巨集模組，而且晶片可能有超過百分之七十的面積都被巨型模組佔據。因為這些巨集模組影響到其他元件的位置，對於線長和可繞度都有直接的影響，以致於擺放巨集模組成為晶片實體設計一大難題。
儘管晶片可以完成繞線，若晶片沒有滿足效能要求（如時序規格或是電源消耗需求），則晶片可能還是無法使用。其中，時序的要求特別重要，也因此現代化的晶片需要插入大量的緩衝器。緩衝器插入不但可能造成標準單元的大量移動，也可能造成繞線上的困難。如果緩衝器插入沒有被事先預估，則晶片就可能無法達到要求的設計規格。
此外，為了提昇晶片製造良率，在設計階段就必須考慮到可製造性。尤其是化學機械研磨後的金屬厚度變異，是探討可製造性中最要重的議題之一；這是因為金屬厚度差異可能會增加電阻，造成晶片效能下降，也可能因為晶片表面不平坦，造成晶片製造曝光成像誤差過大，也可能因為金屬密度分佈不均勻，造成其他各種系統性的變異性。
在這篇論文中，我們提出了全新的平面規劃和置放演算法，來因應上述所提提到的現代化積體電路設計上的挑戰：(1)複雜度；(2)大型巨集模組；(3)效能；(4)可製造性。
為了應付設計複雜度快速的成長，我們發展了有效率的平面規劃和置放演算法。對於超大型平面規劃，我們提出一全新以連接線為導向的多階層平面規劃架構──IMF。IMF是以V型多階層的方式，先從上至下分割電路，再由下至上整合電路。IMF不但能迅速地處理大型電路，也可以有效地最佳化線長。對於超大型置放問題，我們提出一個基於多階層架構，同時考慮線長、預先放置模組、以及單元密度限制的高品質解析式置放器NTUplace3。這個置放器使用高斯平滑法和階層平滑法來處理預先置放模組，並且使用動態步伐控制的共厄梯度搜尋法加速置放。
為了應付大型巨集模組，我們提出了一多重堆積樹 (MP-tree) 表示法。基於二元樹，MP-tree可以非常快速且有效的在多種限制下置放巨集模組。給定一全域置放，MP-tree會最佳化巨集模組位置，最小化模組偏移，並最大化中間標準單元置放與繞線的區域。
為了達到晶片設計的效能與時序需求，我們提出了一個整合緩衝器規劃的非線性置放架構。由於考慮了標準單元密度，緩衝器可以適當的插入至所需的空間；由於考慮了繞線擁擠程度，緩衝器插入不會造成晶片可繞度的下降。
為了提升可製造性，並降低化學機械研磨後的晶片厚度差異，我們提出了以金屬密度驅動的置放演算法。基於我們的非線性解析式置放架構，在置放的過程中，使用機率繞線模型來估計繞線密度。然後，金屬密度和厚度以一個可預測性化學機械研磨模型來計算取得。接著根據金屬密度圖來調整標準單元置放位置，有效的降低金屬密度變異。

關鍵字

超大型積體電路 ； 實體設計 ； 平面規劃 ； 置放 ； 多階層架構 ； 可製造性

並列摘要

As nanometer integrated circuit (IC) technologies advance, design complexity is growing at a dramatic speed. Modern chip designs often consist of millions of transistors and designs with billions of transistors are already in production. For such large and complex designs, floorplanning and placement systems become more and more important because it determines the positions of all components, which greatly affect the chip wirelength, routability, timing, manufacturability, etc. Therefore, it is desirable to develop new floorplanning and placement algorithms.

Due to the wide use of Intellectual Property (IP) modules and embedded memories, a modern chip often consists of a significant number of large hard macros. The number of large macros in a modern design is dramatically increasing. Consequently, a modern chip may consist of hundreds of hard macros, and a larger portion of the chip area, say more than 70\%, may be occupied by hard macros. As a result, placing hard macros becomes a very tough task, because the large macros affect the positions of other components very much; both wirelength and routability are greatly affected.

Even if a chip is routable, the chip may be still useless because it does not meet the performance requirement, such as timing or power consumption. The timing requirement is especially important, and therefore a modern chip requires extensive buffer insertion. However, inserting a large number of buffers may cause dramatic cell migration and routing hotspots. If buffering is not controlled well, it may fail to meet the design specification.

To achieving high-yielding designs, manufacturability also needs to be considered in the design stage, which is called design for manufacturability (DFM). The topography (thickness) variation after chemical-mechanical planarization/polishing (CMP) is one of the most important DFM issues, because topography variation may cause performance degradation due to increase resistance, printability issues due to non-uniform surface, and other systematic variations due to non-uniform metal density distribution.

In this dissertation, floorplanning and placement algorithms are proposed to conquer all aforementioned modern VLSI design challenges, (1) complexity, (2) large macros, (3) performance, and (4) manufacturability.

To handle the growing design complexity, efficient floorplanning and placement algorithms are developed. For large-scale floorplanning, a new interconnect-driven multilevel floorplanning framework (IMF) is proposed. IMF works in the "V-shaped" manner: top-down uncoarsening (partitioning) followed by bottom-up coarsening (merging). IMF not only scales well as the circuit size increases but also optimizes wirelength effectively. For large-scale placement, a high-quality analytical placement algorithm is proposed to consider wirelength, preplaced blocks, and density constraints based on the log-sum-exp wirelength model and the multilevel framework. To handle preplaced blocks, a two-stage smoothing technique, Gaussian smoothing followed by level smoothing, is applied to facilitate block spreading during global placement. The conjugate gradient method with dynamic step-size control is further used to speed up the placement.

To handle large macros, a multi-packing tree (MP-tree) representation for macro placement is proposed. Based on binary trees, the MP-tree is very efficient, effective, and flexible for handling macro placement with various constraints. Given a global placement, our MP-tree-based macro placer optimizes macro positions, minimizes the macro displacement from the initial macro positions, and maximizes the area of the chip center for standard-cell placement and routing.

To meet the chip performance and timing constraints, the first integrated nonlinear placement framework with porosity and congestion aware buffer planning is proposed. Placement with buffer porosity awareness can allocate space for inserting these buffers, and buffering with congestion awareness can improve the routability.

To increase manufacturability and reduce the topography variation after CMP, a metal-density driven placement algorithm is proposed. Based on our analytical placement framework, a probabilistic routing model is used to estimate the wire density during the placement. Then, the metal density and thickness are predicted by a predictive CMP model, and spreading forces are adjusted according to the metal density map to reduce the metal density variation.

並列關鍵字

Floorplanning ； Manufacturability ； Multilevel Framework ； Physical Design ； Placement ； VLSI

參考文獻

[5] ISPD 2005 Placement Contest. http://www.sigda.org/ispd2005/contest.htm.

[6] ISPD 2006 Placement Contest. http://www.sigda.org/ispd2006/contest.html.

[9] mGP: Multilevel Global Placement. http://ballade.cs.ucla.edu/mGP/.

[15] S. Adya and I. Markov. Fixed-outline floorplanning: Enabling hierarchical design. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 11(6):1120-1135, Dec. 2003.

[17] S. N. Adya and I. L. Markov. Combinatorial techniques for mixed-size placement. ACM Transactions on Design Automation of Electronics Systems, 10(5), Jan. 2005.