張耀文Chang, Yao-Wen臺灣大學:電子工程學研究所江哲維Jiang, Zhe-WeiZhe-WeiJiang2010-07-142018-07-102010-07-142018-07-102009U0001-1208200910114000http://ntur.lib.ntu.edu.tw//handle/246246/189145擺置是實體設計中最重要的步驟之一，並且已經被研究了數十年。雖然擺置是傳統的設計自動化問題，現代設計的挑戰已經大幅改變了擺置問題。因此，在擺置的過程中，通常需要去考慮各種不同的目標。例如，大多數傳統的擺置演算法通常集中注意力在線長最佳化上，因而忽略了實際上的設計問題，如可繞性與效能。此外，為了減低晶片重新設計的成本與解決由製造過程所產生的可靠度問題，在擺置過程完成之後，會需要在晶片上的空白處置入數種額外的元件（如多餘單元與天線二極體）。假如我們能在擺置過程中考慮這些元件，將能夠減少在為這些元件尋找合適位置時的困難。 在這份論文當中，我們提出了數個演算法在產生超大型積體電路擺置的同時，考慮可繞性、效能、與可靠度。這份論文是由一個考慮可靠度的分析式擺置演算法所開始。我們提出了一個新方向/技術，叫作連線重疊移除，來解決基本的可繞性問題。之後，我們將正確的時序目標加入分析式擺置演算法，並且提出了考慮時序的分析式擺置演算法來在擺置過程中對電路時序作最佳化。除了可繞性與時序問題之外，晶片製造過程也對擺置產生了額外的設計困難。因此，為了要修正由晶片製造過程所產生的設計失誤，我們提出了考慮多餘單元的分析式擺置演算法以及一個多階層的多餘單元嵌入演算法以產生高品質的多餘單元分佈。為了減少由製造過程所產生的天線效應所造成的可靠度下降，我們提出了一個考慮二極體的分析式擺置演算法，以降低在之後的設計過程中所面臨的二極體置入的困難。我們更提出了一個同時嵌入二極體/跳線的演算法來解決天線效應修正的問題。Placement is a major step in physical design that has been studied for several decades. Although it is a classical problem, modern design challenges have reshaped this problem. As a result, it is usually desired to consider various objectives during the placement process. For example, most existing placement algorithms focus on wirelength optimization and ignore the real design issues, such as routability and performance. Furthermore, to reduce the re-spin cost induced by post-silicon debugging and solve the reliability issues for the manufacturing process, several types of extra components (e.g., spare cells and antenna diodes) must be inserted into whitespace after the placement is done. If we can consider these components during the placement process, it will then reduce the difficulties of finding available positions for these components.In this dissertation, we propose several novel algorithms for VLSI placement generation to consider routability, performance, and reliability. This dissertation starts from a routability-driven analytical placement with a new direction/technique, called net overlapping removal, to solve the essential routability issue. Then the timing-driven analytical placement, which models the exact timing objective into the analytical formulation, is proposed to optimize the circuit timing during the placement optimization process. Despite of the routability and timing issues, the manufacturing process may also introduce additional design difficulties. Therefore, to fix the design failure caused by the manufacturing process, we propose a spare-cell-aware analytical placement and a multilevel spare cell insertion to generate a better distribution of spare cells. To reduce the reliability degradation caused by the antenna effect during manufacturing, we propose a diode-aware analytical placement to reduce the difficulties faced by the later stage for diode insertion. We further propose a simultaneous diode/jumper insertion algorithm to solve the antenna fixing problem.Table of Contentsbstract (Chinese) vbstract viiist of Tables xiiist of Figures xiiihapter 1. Introduction 1.1 Placement Generation Flow . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Analytical Placement Basics . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.1 Analytical Placement Formulation . . . . . . . . . . . . . . . . . . 4.2.2 WirelengthModels . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2.3 Overlap Reduction Techniques . . . . . . . . . . . . . . . . . . . . 10.2.4 Integration of the Wirelength Models and Overlap Reduction Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22.2.5 Optimization Techniques . . . . . . . . . . . . . . . . . . . . . . . 26.2.6 Example Analytical Placer: NTUplace3 . . . . . . . . . . . . . . . 29.3 Design Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30.3.1 Routability-Driven Placement . . . . . . . . . . . . . . . . . . . . . 30.3.2 Timing-Driven Placement . . . . . . . . . . . . . . . . . . . . . . . 31.3.3 Engineering Change Order . . . . . . . . . . . . . . . . . . . . . . 31.3.4 Reliability Enhancement . . . . . . . . . . . . . . . . . . . . . . . 32.4 Overview of the Dissertation . . . . . . . . . . . . . . . . . . . . . . . . . 32.4.1 Routability-Driven Analytical Placement . . . . . . . . . . . . . . 32.4.2 Timing-Driven Analytical Placement . . . . . . . . . . . . . . . . . 34.4.3 Spare-Cell-Aware Placement . . . . . . . . . . . . . . . . . . . . . 34.4.4 Antenna Fixing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35.5 Organization of the Dissertation . . . . . . . . . . . . . . . . . . . . . . . 35hapter 2. Routability-Driven Analytical Placement 37.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37.2 Routability-Driven Placement . . . . . . . . . . . . . . . . . . . . . . . . 40.2.1 Congestion Estimation. . . . . . . . . . . . . . . . . . . . . . . . . 40.2.2 Routability-Driven Objective . . . . . . . . . . . . . . . . . . . . . 43.2.3 Net Overlapping Removal . . . . . . . . . . . . . . . . . . . . . . . 43.2.4 Macro Porosity Handling . . . . . . . . . . . . . . . . . . . . . . . 44.3 Integration into the Analytical Placement Framework . . . . . . . . . . . 46.3.1 Basic Placement Flow . . . . . . . . . . . . . . . . . . . . . . . . . 46.3.2 Conjugate Gradient Solver with Dynamic Target Utilization Rates 47.3.3 Calculation of Gradient Directions . . . . . . . . . . . . . . . . . . 49.4 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49.4.1 Effectiveness of Routability Optimization . . . . . . . . . . . . . . 50.4.2 Comparison withModern Academic Placers . . . . . . . . . . . . . 51.4.3 Impact ofMacro Porosity Consideration . . . . . . . . . . . . . . . 53hapter 3. Timing-Driven Analytical Placement 56.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56.2 Analytical Placement for Timing Optimization . . . . . . . . . . . . . . . 58.2.1 Lookup-Table-based Delay Model . . . . . . . . . . . . . . . . . . . 58.2.2 Critical Path Decomposition . . . . . . . . . . . . . . . . . . . . . 59.2.3 Path Delay Constraint . . . . . . . . . . . . . . . . . . . . . . . . . 61.2.4 Integration with Analytical Placement Framework . . . . . . . . . 63.3 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64hapter 4. Spare-Cell-Aware Placement 68.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68.2 Multilevel Spare-Cell-Aware Placement . . . . . . . . . . . . . . . . . . . 70.2.1 Cluster Expansion . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.2.2 Density-Constraint Determination . . . . . . . . . . . . . . . . . . 72.2.3 Multilevel Spare Cell Insertion . . . . . . . . . . . . . . . . . . . . 73.2.4 Determination of Optimal Spare Cell Positions . . . . . . . . . . . 75.3 Spare-Cell-AwareMultilevel Analytical Placement . . . . . . . . . . . . . 77.4 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77.4.1 Quality Comparison of Spare Cell Insertion . . . . . . . . . . . . . 78.4.2 HPWL Comparison after Spare Cell Insertion . . . . . . . . . . . . 79hapter 5. Antenna Fixing 85.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85.2 Proposed Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89.3 Diode-Aware Analytical Placement . . . . . . . . . . . . . . . . . . . . . 90.4 Antenna Violation Detection/Fixing . . . . . . . . . . . . . . . . . . . . . 93.4.1 Wire Violation Detection . . . . . . . . . . . . . . . . . . . . . . . 95.4.2 Simultaneous Diode/Jumper Insertion . . . . . . . . . . . . . . . . 98.4.3 Solving The ASDJI Problem . . . . . . . . . . . . . . . . . . . . . 101.4.4 Flow Network Pruning Technique . . . . . . . . . . . . . . . . . . 104.4.5 An Example of Antenna Fixing . . . . . . . . . . . . . . . . . . . . 105.5 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106.5.1 Effectiveness of SDJI Algorithm . . . . . . . . . . . . . . . . . . . 108.5.2 Empirical Runtime Analysis . . . . . . . . . . . . . . . . . . . . . . 113.5.3 Net Delay Impact . . . . . . . . . . . . . . . . . . . . . . . . . . . 113.5.4 Effectiveness of the Pruning Technique . . . . . . . . . . . . . . . . 114hapter 6. Concluding Remarks and Future Work 116.1 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116.2 FutureWork . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117ibliography 119ita 130ublication List 1311488558 bytesapplication/pdfen-US實體設計擺置可繞性可製造性可靠度效能Physical DesignPlacementRoutabilityManufacturabilityReliabilityPerformancethesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/189145/1/ntu-98-F92921104-1.pdf