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