張耀文臺灣大學：電機工程學研究所林翠薏Ling, Tsui-YeeTsui-YeeLing2007-11-262018-07-062007-11-262018-07-062006http://ntur.lib.ntu.edu.tw//handle/246246/53028製程變異已成為奈米電路設計的可信度與連線延遲的嚴峻考驗。此外，極劇上升的功耗值與電路合成密度將導致極高的操作環境溫度。溫度，如同電致遷移與電壓，將會嚴重影響到連線的延遲與可信度。考慮製程變異，我們提出了第一個利用統計分析的方法，在符合時序與熱效應良率的條件下，使用邏輯閘與佈線形狀調整技術，最佳化電路的總面積。我們將問題轉換成二次圓錐規劃，並且利用內點法快速解出答案。實驗結果顯示我們的統計方法能找到符合70.0%，84.1%， 99.9%良率條件限制的解答，並且平均上能分別減少44.03%，33.25%，21.74%電路總面積。除此之外，執行時間與電路大小的對數曲線顯示了，利用內點法來解二次圓錐規劃的問題可以得到一個接近線性的實際時間複雜O(N^0.9)， N代表電路大小。更值得一題的是，我們解二次圓錐規劃的時間複雜度比起過去研究提出的理論值O(N^1.3)還要來得更好。Process Variation has become a crucial challenge on both interconnect delay and reliability of nanometer integrated circuit designs. Furthermore, the dramatic increase of ower consumption and integration density has led to high operating temperature. Temperature, as well as electromigration (EM) and power, also significantly affects the delay and reliability of interconnects. Considering process variation, we present the firrst work to use statistical methods to optimize the circuit area under timing and thermal yield constraints by sizing both wires and gates. We model the problem as a second-order conic program (SOCP) and solve it with the interior-point optimization method. Experimental results show that our statistical algorithm can find solutions that satisfy all constraints and on average improves the circuit areas by respective 44.03%, 33.25%, and 21.74% with 70.0%, 84.1%, and 99.9% yields after wire and gate sizing. Further, the log-log curve of the runtime shows that our empirical time complexity is only about O(N^0.9) for solving SOCPs by the interior-point method, which is sublinear to the circuit size, N. In particular, our empirical time complexity is even better than the previously reported O(N^1.3) bound, showing our efficient implementation.Abstract (Chinese) i Abstract ii Acknowledgements iii List of Tables vi List of Figures vii Chapter 1. Introduction 1 1.1 Previous Works 2 1.2 Our Contributions 3 1.3 Organization of the Thesis 5 Chapter 2. Preliminaries 6 2.1 Second-Order Conic Programming (SOCP) 6 2.2 Thermal Model 8 2.3 Variation Model of Performance Parameters 10 2.3.1 Variability of the Physical Parameters considering Correlations 10 2.3.2 Variations of Performance Parameters 12 Chapter 3. Deterministic Interconnect Optimization 14 3.1 Problem Description 14 3.1.1 Influence of Self-Heating on EM 14 3.1.2 Temperature-Dependent Delay 16 3.2 Deterministic Formulation of the Interconnect Optimization 16 3.2.1 EM Constraint 17 3.2.2 Timing Constraint 19 3.2.3 Power Constraint 21 3.2.4 Deterministic Problem Formulation 21 Chapter 4. Statistical Thermal-Driven Optimization Using SOCP 23 4.1 Statistical Problem Formulation 23 4.2 Parametric Yield Formulation using SOCP 25 4.3 Simultaneous Gate and Wire Sizing Optimization 29 4.4 Implementation 30 4.4.1 Data Structures 30 4.4.2 Time Complexity 30 Chapter 5. Experiment Results 36 Chapter 6. Conclusions and Future Work 45 6.1 Conclusions 45 6.2 Future Work 45 Bibliography 47491201 bytesapplication/pdfen-US以統計分析熱效應時序效能電路最佳化StatisticalThermalTimingCircuitOptimizationthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/53028/1/ntu-95-R93921040-1.pdf