請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/37275
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 張耀文 | |
dc.contributor.author | I-Jye Lin | en |
dc.contributor.author | 林依潔 | zh_TW |
dc.date.accessioned | 2021-06-13T15:23:08Z | - |
dc.date.available | 2008-07-30 | |
dc.date.copyright | 2008-07-30 | |
dc.date.issued | 2008 | |
dc.date.submitted | 2008-07-21 | |
dc.identifier.citation | [1] K. Agarwal, D. Sylvester, D. Blaauw, F. Liu, S. Nassif, and S. Vrudhula,
“Variational Delay Metrics for Interconnect Timing Analysis,” Proc. DAC, pp. 381-384, Jun. 2004. [2] R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice Hall, 1993. [3] K. Banerjee, A. Mehrotra, A. Sangiovanni-Vincentelli, and C. Hu, “On Thermal Effects in Deep Sub-micron VLSI Interconnects,” Proc. DAC, pp. 885-891, Jun. 1999. [4] K. Banerjee, M. Pedram, and H. Ajami, “Analysis and Optimization of Thermal Issues in High-performance VLSI,” Proc. ISPD, pp. 230-237, Apr. 2001. [5] J. R. Black, “Electromigration-a Brief Survey and Some Recent Results,” IEEE Trans. Electron Devices, pp. 338-347, 1969. [6] S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge, 2004. [7] J. Chern, J. Huang, L. Arledge, P. Li, and P. Yang, “Multilevel Metal Capacitance Models for CAD Design Synthesis Systems,” IEEE Electron Devices Letters, pp. 32-34, Jan. 1992. [8] C.-P. Chen, C. C. N. Chu, and D. F. Wong, “Fast and Exact Simultaneous Gate and Wire Sizing by Lagrangian Relaxation,” Proc. ICCAD, pp. 617-624,Nov. 1998. [9] S. H. Choi, B. C. Paul and K. Roy, “Novel Sizing Algorithm for Yield Improvement under Process Variarion in Nanometer Technology,” Proc. DAC, pp. 454-459, Jun. 2004. [10] A. Davoodi and A.r Srivastava, “Variability driven gate sizing for binning yield optimization”, Proc. DAC, pp. 959-964 , Jul. 2006. [11] F. S. Hillier and G. J. Lieberman, Introduction to Operations Research, 5th ed., McGraw Hill, 1990. [12] H.-R. Jiang, J.-Y. Jou ,and Y.-W. Chang, “Noise-constrained Performance Optimization by Simultaneous Gate and Wire Sizing based on Lagrangian Relaxation,” Proc. DAC, pp. 90-95, Jun. 1999. [13] I-J. Lin, T.-Y. Ling, and Y.-W. Chang, “Statistical Circuit Optimization Considering Device and Interconnect Process Variations, ” Proc. SLIP, pp. 47-54, Mar. 2007. [14] I-J. Lin and Y.-W. Chang, “An Efficient Algorithm for Statistical Circuit Optimization Using Lagrangian Relaxation, ” Proc. ICCAD, pp. 119-124, Nov. 2007. [15] Y. Liu, S. Nassif, L. Pileggi, and A. J. Strojwas, “Impact of Interconnect Variations on the Clock Skew of a Gigahertz Microprocessor, ” Proc. DAC., pp. 168-171, Jun. 2000. [16] M. Mani and M. Orshansky, “A New Statistical Optimization Algorithm for Gate Sizing,” Proc. ICCD, pp. 272-277, Sep. 2004. [17] M. Mani, A. Devgan, and M. Orshansky, “An Efficient Algorithm for Statistical Minimization of Total Power under Timing Yield Constraints,” Proc. DAC, pp. 309-314, Jun. 2005. [18] M. Mani, A. K. Singh, and M. Orshansky “Joint Design-Time and Post-Silicon Minimization of Parametric Yield Loss using Adjustable Robust Optimization,” Proc. ICCAD, pp. 19-26 , Nov. 2006. [19] MOSEK tool http://www.mosek.com/documentation.htm#manuals [20] J. Singh, Z.-Q. Luo and S. Sapatnekar, “A Geometric Programming-based Worst-Case Gate Sizing Method Incorporating Spatial Correlation,” IEEE Trans. Computer-Aided Design, vol. 27, pp. 295-308, Feb 2008. [21] A. Srivastava, D. Sylvester, and D. Blaauw, Statistical Analysis and Optimization for VLSI: Timing and Power, Michigan, 2005. [22] C. Visweswariah, “Statistical Analysis and Optimization in the Presence of Gate and Interconnect Delay Variations,” Proc. SLIP, pp. 37, Mar. 2006. [23] W. L. Winston, Operations Research : Applications and Algorithms, Thomson, 1994. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/37275 | - |
dc.description.abstract | 在現今製程日漸縮小情況下,製程變異已成為奈米電路設計的連線延遲與的可信度嚴峻考驗。為了控制製程變異帶來的影響,使用統計分析的最佳化技術(statistical optimization)已經成為提升良率常用的方法。在文獻上,使用二次圓錐規劃(second-order conic programming)以及拉式釋限法(Lagrangian relaxation)都可以達到透過調整元件大小的電路最佳化。然而有關連線的製程變異並不常被提出討論。在本論文中,我們將提出第一個在考慮執行時間、熱能以及功率的限制下,以同步調整元件大小及連線線寬(gate and wire sizing)達到統計分析方法下的電路最佳化。我們使用了二次圓錐規劃以及拉式釋限法兩種方法來處理統計分析方法下的電路最佳化,並且研究比較了兩種方法優缺點。我們的研究顯示,二次圓錐規劃在適用彈性、準確度以及處理問題大小上都有嚴苛的限制,特別當連線被納入考量時,其限制尤其明顯。實驗結果顯示,以拉式釋限法為基礎的演算法比起以二次圓錐規劃為基礎的演算法所得結果可以省下33%的面積,並且可以加速執行速度560倍。這個結果表示出在處理多限制下以同步調整元件大小及連線線寬以達到統計分析的電路最佳化問題,拉式釋限法是一個比較好的方法。 | zh_TW |
dc.description.abstract | 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. | en |
dc.description.provenance | Made available in DSpace on 2021-06-13T15:23:08Z (GMT). No. of bitstreams: 1 ntu-97-F93921045-1.pdf: 684593 bytes, checksum: 4bc0a40a93781d25a4d59888033c6ddb (MD5) Previous issue date: 2008 | en |
dc.description.tableofcontents | Table of Contents
Acknowledgements i Abstract (Chinese) ii Abstract (Chinese) iii Abstract iv List of Tables viii List of Figures ix Chapter 1. Introduction 1 1.1 Previous Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Our Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3 Organization of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Chapter 2. Problem Description 8 2.1 Timing Constraint . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2 Thermal Constraint . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2.1 Temperature-Dependent Delay . . . . . . . . . . . . . . . . . . . . 13 2.3 Power Constraint . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 Chapter 3. Variation Model of Performance Parameters 15 Chapter 4. Algorithms for Statistical Circuit Optimization 16 4.1 Second-Order Conic Programming (SOCP) . . . . . . . . . . . . . . . . . 18 4.1.1 SOCP Transformation . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.1.2 Problems in the Transformation . . . . . . . . . . . . . . . . . . . 21 4.2 Lagrangian Relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.2.1 Lagrangian Relaxation Subproblem . . . . . . . . . . . . . . . . . 28 4.2.2 Lagrangian Dual Problem . . . . . . . . . . . . . . . . . . . . . . . 32 Chapter 5. Experiment Results 35 Chapter 6. Conclusions & Extension 44 6.1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 6.2 Extension . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 Bibliography 46 | |
dc.language.iso | en | |
dc.title | 以同步調整元件大小及連線線寬達到統計分析方法下的電路最佳化 | zh_TW |
dc.title | Statistical Circuit Optimization using Simultaneous Gate and Wire Sizing | en |
dc.type | Thesis | |
dc.date.schoolyear | 96-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 徐爵民,黃婷婷,周景揚,魏慶隆,李鎮宜 | |
dc.subject.keyword | 調整元件大小,實體設計,調整連,線線寬大小,製程變異,良,率,模擬, | zh_TW |
dc.subject.keyword | Gate Sizing,Physical Design,Wire Sizing,Variability, | en |
dc.relation.page | 60 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2008-07-23 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 電子工程學研究所 | zh_TW |
顯示於系所單位: | 電子工程學研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-97-1.pdf 目前未授權公開取用 | 668.55 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。