以統計分析的熱效應與時序效能為限制之電路最佳化

Statistical Thermal- and Timing-Constrained Circuit Optimization

林翠薏(Tsui-Yee Ling)

指導教授 ： 張耀文

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

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

摘要

製程變異已成為奈米電路設計的可信度與連線延遲的嚴峻考驗。此外，極劇上升的功耗值與電路合成密度將導致極高的操作環境溫度。溫度，如同電致遷移與電壓，將會嚴重影響到連線的延遲與可信度。考慮製程變異，我們提出了第一個利用統計分析的方法，在符合時序與熱效應良率的條件下，使用邏輯閘與佈線形狀調整技術，最佳化電路的總面積。我們將問題轉換成二次圓錐規劃，並且利用內點法快速解出答案。實驗結果顯示我們的統計方法能找到符合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.

並列關鍵字

Statistical ； Thermal ； Timing ； Circuit ； Optimization

參考文獻

[1] A. Agarwal, D. Blaauw, V. Zolotov, and S. Vrudhula, Computation and Refinement of Statistical Bounds on Circuit Delay," In Proceeding of Design Automation Conference, page 348-353, June 2003.

[2] A. Agarwal, D. Blaauw, and V. Zolotov, Statistical Timing Analysis for Intra-Die Process Variations with Spatial Correlations," In Proceeding of International Conference on Computer-Aided Design, page 900-907, November 2003.

[3] K. Agarwal, D. Sylvester, D. Blaauw, F. Liu, S. Nassif, and S. Vrudhula, Variational Delay Metrics for Interconnect Timing Analysis," In Proceeding of Design Automation Conference, page 381-384, June 2004.

[5] K. Banerjee, M. Pedram, and H. Ajami, Analysis and Optimization of Thermal Issues in High-Performance VLSI," In Proceeding of International Symposium on Physical Design, page 230-237, April 2001.

[7] J. R. Black, Electromigration-a Brief Survey and Some Recent Results, IEEE Transaction on Electron Devices, page 338-347, 1969.