請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/22861
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 陳中平(Chung-Ping Chen) | |
dc.contributor.author | Shih-Pin Hung | en |
dc.contributor.author | 洪士斌 | zh_TW |
dc.date.accessioned | 2021-06-08T04:31:05Z | - |
dc.date.copyright | 2009-12-29 | |
dc.date.issued | 2009 | |
dc.date.submitted | 2009-11-15 | |
dc.identifier.citation | [1] J. P. Fishburn and A. E. Dunlop, “TILOS: A posynomial approach to transistor sizing,” Proceedings of IEEE/ACM International Conference on Computer Aided Design, pp. 326–328, 1985.
[2] C. P. Chen, C. C. N. Chu, and D. F. Wong, “Fast and exact simultaneous gate and wire sizing by Lagrangian relaxation,” IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, vol. 18, pp. 1014–1025, July 1999. [3] H. Tennakoon and C. Sechen, “Gate sizing using Lagrangian relaxation combined with a fast gradient-based pre-processing step,” Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pp. 395–402,2002. [4] H. Tennakoon and C. Sechen, “Efficient and accurate gate sizing with piecewise convex delay models,”Proceedings of ACM/IEEE Design Automation Conference, pp. 807–812, 2005. [5] S. P. Boyd, S. J. Kim, D. D. Patil, and M. A. Horowitz, “Digital circuit optimization via geometric programming,” Operations Research, vol. 53, pp. 899–932, Nov.-Dec. 2005. [6] F. Beeftink, P. Kudva, D. Kung, and L. Stok, “Gate-size selection for standard cell libraries,” Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pp. 545–550, 1998. [7] O. Coudert, “Gate sizing for constrained delay/power/area optimization,”IEEE Transactions on Very Large Scale Integration Systems, vol. 5, pp. 465–472, Dec. 1997. [8] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms. The MIT Press, 2nd ed., 2001. [9] S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge University Press, 2004. [10] M. S. Bazaraa, H. D. Sherali, and C. M. Shetty, Nonlinear Programming: Theory and Algorithms. Wiley-Interscience, 3rd ed., 2006. [11] K. Kasamsetty, M. Ketkar, and S. S. Sapatnekar, “A new class of convex functions for delay modeling and its application to the transistor sizing problem,”IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 19, pp. 779–788, July 2000. [12] M. Ketkar, K. Kasamsetty, and S. Sapatnekar, “Convex delay models for transistor sizing,” Proceedings of ACM/IEEE Design Automation Conference, pp. 655–660, 2000. [13] C. Lawrence, J. L. Zhou, and A. L. Tits, “User’s guide for CFSQP version 2.5: A c code for solving (large scale) constrained nonlinear (minimax) optimization problems, generating iterates satisfying all inequality constraints,” tech. rep., Electrical Engineering Department and Institute for Systems Research, University of Maryland, 1997. [14] C. Zhu, R. Byrd, and J. Nocedal, “L-BFGS-B: FORTRAN routines for large scale bound constrained optimization,” ACM Transactions on Mathematical Software, vol. 23, no. 4, pp. 550–560, 1997. [15] J. Nocedal and S. Wright, Numerical Optimization. Springer, 2nd ed., 2006. [16] UMC 0.13um Standard Cell library. http://freelibrary.faraday-tech.com. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/22861 | - |
dc.description.abstract | 電路最佳化在高效能以及低功率消耗積體電路設計中是非常重要的一個步驟。它對於電路最終的時序、功率消耗以及面積有相當大的影響。在標準單元設計中,元件尺寸及臨界電壓最佳化非常適合用來達成電路設計者對於時序及功率消耗的要求。雖然已經有很多元件尺寸最佳化的方法被提出來,但是大部分的方法都假設元件尺寸是連續的變數,也就是說元件尺寸可以是一個限制在某個範圍內的任意值。然而,在實際的標準單元庫中,可以選擇的元件尺寸大小以及臨界電壓都是非常有限的,使得先求出連續解再用逼近法近似的方法經常導致電路違反時序要求。因此,我們提出一個新的演算法可以直接處理離散的元件尺寸以及臨界電壓。我們把這個問題轉成一個數學規劃問題,最佳化目標為電路的功率消耗,並且能滿足時序的要求。利用拉格朗日鬆弛法,這個數學規劃問題可以被大幅的簡化。然後再利用我們提出的啟發式演算法解決這個問題。實驗結果顯示,比起用連續的方法求解再逼近,我們提出的方法平均可以降低35.5%的漏電功率消耗以及9.1%的總功率消耗,而執行速度能快55倍。 | zh_TW |
dc.description.abstract | Circuit optimization is a very important step in high performance and low power IC design. It has a significant impact on the delay, power dissipation and area of the final circuit. Gate sizing and multiple-Vt assignment are common and useful ways to meet power and timing budgets for cell-based design. There exist some gate sizing techniques, however, most of them handle continuous gate sizing problem which is based on the assumption that gate sizes can be any value within certain range. In realistic standard cell libraries, available gate sizes and threshold voltages are sparse, which makes the nearest rounding approach inapplicable as large timing violations may be introduced. As a result, we propose a novel algorithm which directly handles discrete gate sizes and threshold voltages. We formulate the optimization into a mathematical program with total power cost and timing constraint. The formulation can be greatly simplified based on Lagrangian relaxation. Then we adopt a heuristic algorithm which solves the mathematical program without domain transformation. Experimental results demonstrate that compared to the continuous approach, we achieve average leakage power savings of 35.5% and average total power savings of 9.1% with 55× faster runtime. | en |
dc.description.provenance | Made available in DSpace on 2021-06-08T04:31:05Z (GMT). No. of bitstreams: 1 ntu-98-R96943078-1.pdf: 781744 bytes, checksum: 587bd2a1dd1ececbe332259820e9ca0d (MD5) Previous issue date: 2009 | en |
dc.description.tableofcontents | Abstract (Chinese) i
Abstract ii List of Figures v List of Tables vii List of Algorithms ix 1 Introduction 1 1.1 Our Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Organization of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . 4 2 Preliminaries 5 2.1 Standard Cell Library . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 Cost Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2.1 Area and Power Models . . . . . . . . . . . . . . . . . . . . . 8 2.2.2 Timing Models . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.3 Static Timing Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.4 Convex Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3 Continuous Optimization Algorithm 19 3.1 Algorithm Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.2 Posynomial Delay and Power Approximations . . . . . . . . . . . . . 20 3.3 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.4 Lagrangian Relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.4.1 Simplification of LRS/λ . . . . . . . . . . . . . . . . . . . . . 26 3.4.2 Solving LDP . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.5 Algorithm Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 4 Discrete Optimization Algorithm 32 4.1 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.2 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4.2.1 Solving DLRS/λ . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.2.2 Solving DLDP . . . . . . . . . . . . . . . . . . . . . . . . . . 38 5 Experimental Results 39 5.1 Posynomial Fitting Results . . . . . . . . . . . . . . . . . . . . . . . . 39 5.2 Circuit Optimization Results . . . . . . . . . . . . . . . . . . . . . . . 41 6 Conclusions 50 Bibliography 52 | |
dc.language.iso | en | |
dc.title | 同時調整標準單元設計的元件尺寸及臨界電壓之演算法 | zh_TW |
dc.title | Simultaneous Gate Sizing and Multiple-Vt Assignment for Cell-Based Design | en |
dc.type | Thesis | |
dc.date.schoolyear | 98-1 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 盧奕璋(Yi-Chang Lu),林智仁(Chih-Jen Lin) | |
dc.subject.keyword | 元件尺寸最佳化,臨界電壓最佳化,降低功率消耗,拉格朗日鬆弛法,標準單元設計, | zh_TW |
dc.subject.keyword | Gate Sizing,Multiple-Vt Assignment,Power Reduction,Lagrangian Relaxation,Cell-Based Design, | en |
dc.relation.page | 54 | |
dc.rights.note | 未授權 | |
dc.date.accepted | 2009-11-16 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 電子工程學研究所 | zh_TW |
顯示於系所單位: | 電子工程學研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-98-1.pdf 目前未授權公開取用 | 763.42 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。