跳到主要內容

臺灣博碩士論文加值系統

(44.211.31.134) 您好!臺灣時間:2024/07/25 19:23
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:洪士斌
研究生(外文):Shih-Pin Hung
論文名稱:同時調整標準單元設計的元件尺寸及臨界電壓之演算法
論文名稱(外文):Simultaneous Gate Sizing and Multiple-Vt Assignment for Cell-Based Design
指導教授:陳中平陳中平引用關係
指導教授(外文):Chung-Ping Chen
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:電子工程學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2009
畢業學年度:98
語文別:英文
論文頁數:54
中文關鍵詞:元件尺寸最佳化臨界電壓最佳化降低功率消耗拉格朗日鬆弛法標準單元設計
外文關鍵詞:Gate SizingMultiple-Vt AssignmentPower ReductionLagrangian RelaxationCell-Based Design
相關次數:
  • 被引用被引用:0
  • 點閱點閱:181
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
電路最佳化在高效能以及低功率消耗積體電路設計中是非常重要的一個步驟。它對於電路最終的時序、功率消耗以及面積有相當大的影響。在標準單元設計中,元件尺寸及臨界電壓最佳化非常適合用來達成電路設計者對於時序及功率消耗的要求。雖然已經有很多元件尺寸最佳化的方法被提出來,但是大部分的方法都假設元件尺寸是連續的變數,也就是說元件尺寸可以是一個限制在某個範圍內的任意值。然而,在實際的標準單元庫中,可以選擇的元件尺寸大小以及臨界電壓都是非常有限的,使得先求出連續解再用逼近法近似的方法經常導致電路違反時序要求。因此,我們提出一個新的演算法可以直接處理離散的元件尺寸以及臨界電壓。我們把這個問題轉成一個數學規劃問題,最佳化目標為電路的功率消耗,並且能滿足時序的要求。利用拉格朗日鬆弛法,這個數學規劃問題可以被大幅的簡化。然後再利用我們提出的啟發式演算法解決這個問題。實驗結果顯示,比起用連續的方法求解再逼近,我們提出的方法平均可以降低35.5%的漏電功率消耗以及9.1%的總功率消耗,而執行速度能快55倍。
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.
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
[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.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top