A Robust and Design Flow Compatible Standard Cell Sizing Method for VLSI Circuit Performance Optimization

在超大型積體電路的設計流程中，電路最佳化是相當重要的一個步驟，尤其對於要求高效能或低功耗的電路設計而言。一直以來，元件尺寸最佳化的技術在電路時序、功率消耗及面積的取捨中提供了一個非常有效的方式。一些現有的演算法使用基於元件尺寸連續的最佳化方法來解決元件尺寸調整的問題，並且假設元件尺寸可以是一個範圍區間內的任意值。但當我們在實際情況中使用離散分布的標準元件庫時，一個元件的尺寸選擇是非常有限的，並且元件的尺寸分布相當鬆散。尺寸連續的調整方法這時就面臨到必須將連續解用逼近法近似到離散元件尺寸的狀況，這個步驟經常導致電路違反時序要求。 在這篇論文中，我們使用動態規劃尋找最佳解的方式來解決離散的元件尺寸最佳化問題。我們將元件尺寸選擇一致性的條件鬆弛，使得動態規劃可以應用在電路對應的有向圖上，並且我們在動態規劃局部解合併的過程中運用了加速的合併技術。我們根據動態規劃得到的結果來決定元件的尺寸，並且解決尺寸選擇不一致的問題。最後，我們使用一個以敏感度作為導引的啟發式演算法進行電路面積及功率消耗的極小化，並且更進一步的改善電路的時序延遲。 實驗結果顯示，在我們的最佳化流程中使用窮盡搜尋動態規劃的方式，最佳化結果優於商用軟體產生的結果。使用加速的合併技術，也可達到接近的時序結果並且減少面積以及功率的消耗。In the VLSI circuit design flow, circuit optimization is a very important step especially for high performance and low power IC designs. The gate sizing technique has always been an effective method in delay, power dissipation and area trade-offs. Some existing methods use continuous approach to solve the gate sizing problem, which is based on the assumption that gate sizes can be any value within a certain range. Unfortunately, when using existing discrete standard cell libraries in real situation, the sizes available of a gate type are limited and sparsely distributed. Continuous methods thus suffers from rounding the continuous result back to discrete cell size, and often results in timing violations. In this thesis, we provide a method to solve the discrete gate sizing problem by a dynamic programming solution searching method with a relaxation-restriction flow. The dynamic programming solution search can be applied to a directed acyclic graph with solution consistency relaxation. A speed-up solution merging technique is used in dynamic programming solution searching process. We determine the gate sizes following the dynamic programming solution while handling the inconsistency of reconvergence paths. Finally, a sensitivity guided heuristic algorithm is performed to reduce the area/power and further improves the circuit timing delay. Experimental results show that our optimization results can beat the results generated by commercial tool when exhausted dynamic programming search is applied. With the speed-up solution merging technique applied, the optimization results can achieve comparable circuit delay while improving area and power dissipation.口試委員會審定書 i 誌謝 ii 摘要 iii ABSTRACT iv CONTENTS v LIST OF FIGURES vii LIST OF TABLES ix Chapter 1 Introduction 1 1.1 Introduction 1 1.2 Our Contributions 3 1.3 Overview of the Optimization Flow 4 1.4 Thesis Organization 6 Chapter 2 Preliminaries 7 2.1 Standard Cell Library 7 2.2 Cost Models 10 2.2.1 Area and Power Models 10 2.2.2 Timing Models 12 2.3 Static Timing Analysis 17 2.3.1 Static Timing Analysis Steps 17 2.3.2 Static Timing Analysis Computation 19 Chapter 3 Dynamic Programming Size Selection 21 3.1 Problem Formulation 23 3.2 Consistency Relaxation 25 3.2.1 Construction of Dynamic Programming 25 3.2.2 Partial Solution and Solution Curve 28 3.2.3 Solution Merging Operation 29 3.3 Inconsistence Recovery 33 3.3.1 Gate Size Assignment Algorithm 33 3.3.2 Inconsistent Assignment Resolving 35 3.4 Iterative Refinement 37 Chapter 4 Sensitivity Guided Refinement Iteration 38 4.1 Sensitivity Guided Area Reduction 40 4.1.1 Sensitivity Selections 40 4.1.2 Area Reduction Algorithm 41 4.2 Critical Timing Refinement 43 Chapter 5 Experimental Results 44 5.1 Exhausted Dynamic Programming Results 44 5.2 Circuit Optimization Results 46 Chapter 6 Conclusion 52 Bibliography 5