以同步調整元件大小及連線線寬達到統計分析方法下的電路最佳化

Statistical Circuit Optimization using Simultaneous Gate and Wire Sizing

林依潔(I-Jye Lin)

指導教授 ： 張耀文

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

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

摘要

在現今製程日漸縮小情況下，製程變異已成為奈米電路設計的連線延遲與的可信度嚴峻考驗。為了控制製程變異帶來的影響，使用統計分析的最佳化技術(statistical optimization)已經成為提升良率常用的方法。在文獻上，使用二次圓錐規劃(second-order conic programming)以及拉式釋限法(Lagrangian relaxation)都可以達到透過調整元件大小的電路最佳化。然而有關連線的製程變異並不常被提出討論。在本論文中，我們將提出第一個在考慮執行時間、熱能以及功率的限制下，以同步調整元件大小及連線線寬(gate and wire sizing)達到統計分析方法下的電路最佳化。我們使用了二次圓錐規劃以及拉式釋限法兩種方法來處理統計分析方法下的電路最佳化，並且研究比較了兩種方法優缺點。我們的研究顯示，二次圓錐規劃在適用彈性、準確度以及處理問題大小上都有嚴苛的限制，特別當連線被納入考量時，其限制尤其明顯。實驗結果顯示，以拉式釋限法為基礎的演算法比起以二次圓錐規劃為基礎的演算法所得結果可以省下33%的面積，並且可以加速執行速度560倍。這個結果表示出在處理多限制下以同步調整元件大小及連線線寬以達到統計分析的電路最佳化問題，拉式釋限法是一個比較好的方法。

關鍵字

調整元件大小 ； 實體設計 ； 調整連線線寬大小 ； 製程變異良率模擬

並列摘要

Due to the technology scaling down, process variation has become a crucial challenge on both interconnect delay and reliability. To handle the process variation, statistical optimization has emerged as a popular technique for yield improvement. Both second-order conic programming (SOCP) and Lagrangian relaxation (LR) have been proposed in the literature for statistical circuit optimization by gate sizing. However, not much work is on interconnect variation. In this thesis, we present the first work to use statistical methods to optimize the circuit area under timing, thermal, and power constraints by simultaneous gate and interconnect sizing. We apply both SOCP and LR to handle statistical circuit optimization and conduct comparative studies on these two methods. Our studies show significant limitations of SOCP in its flexibility, accuracy, and scalability for statistical circuit optimization, especially for interconnects. Compared with SOCP, experimental results show that the LR-based algorithm can achieve much better solution quality by reducing 33% area and obtain a 560X speedup over SOCP. The results demonstrate that LR is a better technique for multi-constrained statistical circuit optimization by both gate and wire sizing.

並列關鍵字

Gate Sizing ； Physical Design ； Wire Sizing ； Variability

參考文獻

[14] I-J. Lin and Y.-W. Chang, “An Efficient Algorithm for Statistical Circuit

[1] K. Agarwal, D. Sylvester, D. Blaauw, F. Liu, S. Nassif, and S. Vrudhula,

“Variational Delay Metrics for Interconnect Timing Analysis,” Proc. DAC,

[2] R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory, Algorithms,

and Applications, Prentice Hall, 1993.