臺灣博碩士論文加值系統

隨著製程技術進步,製程變異成為功率以及時序分析方式的一個障礙。而統計時序分析成為眾多處理設計不確定性的一種技術。統計時序分析中需要最大計算量是一種稱為緊密機率 (Tightness Probability)的技術。這種技術能將兩個隨機變數在機率上的大小表示出來。但是由於訊號相互獨立的這項假設導致計算上顯著的誤差。我們說明了緊密機率是如何被不同的計算方式影響,並且提出解決方案。我們並進一步延伸我們的研究至如何用定性 (Deterministic)與統計的方式最小化FPGA的功率消耗。 FPGA因為有可重配置性(Reconfigurability)與快速上市的特性而廣泛地被運用在 IC設計上。但是因為功率與面積的因素導致它不適合手持式與低功率等產品。有許多的低功率技術不斷地被提出,像是具有彈性輸入個數的LUT、電源下降、基體偏壓、低漏電流靜態隨機存取記憶體、功率閘控和雙臨界電壓。在此研究中,適應性電源與適應性基體偏壓被運用在同時降低動態與靜態功率。這些方法將會運用在後晶片(Post-silicon)最佳化。如果製程變異並不顯著或是無法獲得,我們就可採用幾何規劃的定性方式來降低功率消耗。對於統計最佳化而言,因為漏電流有著指數的數學形式,所以難以化為凸型最佳化。在這種情況下,如果時序沒有過於嚴苛,則時序與功率被逼近為線性規劃並且可被有效率地解出。

As technology scales, process variation impedes the accuracy of conventional power and delay analysis. Statistical static timing analysis (SSTA) is one of the reactions to cope with the design uncertainty. The computation of tightness probability is one of the most important elements in SSTA. Given two random variables, it calculates the probability that the value of one is greater than that of the other. However, it suffers from significant computational error due to the signal independence assumption. We show how tightness probability is affected by different computation orders, and propose a solution to it. We further extend our work to FPGA power minimization under deterministic and statistical timing constraints. FPGA is widely used in IC design due to its re-configurability and fast time-to-market capability. However, the power and area issues make it not suitable for hand-held and other low power devices. Many techniques are proposed to reduce FPGA power consumption, such as .flexible LUT sizes, supply voltage scaling, body biasing, low leakage SRAM, power gating, and dual threshold voltage. In this work, adaptive supply voltage and adaptive body biasing are applied to reduce power, including both dynamic and leakage power. They are then adopted in a post-silicon optimization. If the process variation is not significant or not available, the deterministic optimization, which can be formulated as geometric programming in a convex form, can be applied. For statistical optimization, leakage power is in exponential form and is hard to formulate in convex optimization. In this case, timing and power are approximated with linear programming and can be solved efficiently with small approximation error if the timing constraint is not too tight.

口試委員審定書 i
Acknowledgements iii
摘要 iv
Abstract v
List of Figures xi
List of Tables xiii
1 Introduction 1
1.1 Tightness Probability and Power Minimization ............. 2
1.2 Main Results and Contribution ..................... 3
1.3 Thesis Organization............................ 4
2 Preliminaries and Definitions 5
2.1 Process Variation and Design Issues ................... 5
2.2 Statistical Timing Analysis and Optimization ............. 8
2.2.1 Statistical Static Timing Analysis ................ 8
2.2.2 Statistical Optimization under Timing Constraints ...... 9
3 Tightness Probability Computation 14
3.1 Definition of Tightness Probability ................... 15
3.2 Exponential Blow-Up of Permutation .................. 16
3.3 Approaches for Calculating Tightness Probability ........... 17
3.3.1 Computing with Independence Assumption . . ......... 17
3.3.2 Calculate Tightness Probability at The Last Maximum Operation................................ 19
3.4 Proposed Methods ............................ 20
3.4.1 Linear Regression Method .................... 20
3.4.2 ρ-error and μ-error ........................ 21
3.4.3 Tightness Probability of The Last Maximum Operation .... 24
3.5 Experimental Results ........................... 25
3.5.1 Linear Regression Method .................... 25
3.5.2 ρ-error and μ-error ........................ 26
3.5.3 Tightness Probability of The Last Maximum Operation .... 30
3.5.4 Comparison ............................ 31
4 FPGA Power Minimization 33
4.1 Power Issue ................................ 34
4.2 Models ................................... 36
4.2.1 Power Models ........................... 37
4.2.2 Approximated Statistical Power Model ............. 39
4.2.3 Timing Models .......................... 41
4.2.4 Parameters Extraction of Power and Timing models ...... 42
4.3 Deterministic Power Minimization.................... 45
4.3.1 Geometric Program........................ 46
4.3.2 Objective Function ........................ 49
4.3.3 Timing Constraints ........................ 50
4.4 Statistical Power Minimization...................... 52
4.4.1 Timing Constraints ........................ 52
4.4.2 Optimization Problem ...................... 53
4.5 Experimental Results ........................... 54
4.5.1 Deterministic Power Minimization ................ 54
4.5.2 Statistical Power Minimization ................. 56
5 Conclusions and Future Work 71
Bibliography 74

[1] ITRS reports. Available from http://www.itrs.net/reports.html.
[2] A. Srivastava, D. Sylvester, and D. Blaauw. Statistical Analysis and Optimization for VLSI: Timing and Power. Springer Publishers, New York, 2005.
[3] C. Visweswariah, K. Ravindran, K. Kalafala, S. G. Walker, and S. Narayan. First-order incremental block-based statistical timing analysis. In Design Automation Conference, pages 331–336, 2004.
[4] J. A. G. Jess, K. Kalafala, S. R. Naidu, R. H. J. M. Otten, and C. Visweswariah. Statistical timing for parametric yield prediction of digital integrated circuits. In Design Automation Conference, pages 932–937, 2003.
[5] H. Chang, V. Zolotov, S. Narayan, and C. Visweswariah. Gate sizing using incremental parameterized statistical timing analysis. In IEEE International Conference on Computer-Aided Design, pages 1029–1036, 2005.
[6] T. Ishihara and H. Yasuura. Voltage scheduling problem for dynamically variable voltage processors. In International Symposium on Low Power Electronics and Design, pages 197–202, 1998.
[7] R. Gonzalez, B. Gordon, and M. Horowitz. Supply and threshold voltage scaling for low power CMOS. IEEE J. Solid-State Circuits, 32:1210–1216, August 1997.
[8] T. Kuroda et al. A 0.9-V, 150-MHz, 10-mW, 4 mm2, 2-D discrete cosine transform core processor with variable threshold-voltage (VT) scheme. IEEE J. Solid-State Circuits, 31:1770–1779, November 1996.
[9] A. Srivastava, D. Sylvester, and D. Blaauw. Statistical optimization of leakage power considering process variations using dual-Vth and sizing. In Design Automation Conference, pages 773–778, 2004.
[10] M. Mani, A. Devgan, and M. Orshansky. An efficient algorithm for statistical minimization of total power under timing yield constraints. In Design Automation Conference, pages 309–314, 2005.
[11] Haitham Hindi. A tutorial on convex optimization II: Duality and interior point methods. In American Control Conference, 2006.
[12] S. Borkar, T. Karnik, S. Narendra, J. Tschanz, A. Keshavarzi, and V. De. Parameter variations and impact on circuits and microarchitecture. In Design Automation Conference, pages 338–342, 2003.
[13] TSMC advanced technology overview. Available from http://www.tsmc.com/download/.
[14] L. Cheng, J. Xiong, and L. He. Non-linear statistical static timing analysis for non-Gaussian variation sources. In Design Automation Conference, pages 250–255, 2007.
[15] M. Orshansky and K. Keutzer. A general probabilistic framework for worst case timing analysis. In Design Automation Conference, pages 556–561, 2002.
[16] H. Chang and S. S. Sapatnekar. Statistical timing analysis considering spatial correlations using a single PERT-like traversal. In IEEE International Conference on Computer-Aided Design, pages 621–625, 2003.
[17] A. Agarwal, D. Blaauw, and Zolotov. Statistical timing analysis for intra-die process variations with spatial correlations. In IEEE International Conference on Computer-Aided Design, pages 900–907, 2003.
[18] Y. Z., A. J. Strojwas, X. Li, and L. T. Pileggi. Correlation-aware statistical timing analysis with non-gaussian delay distributions. In Design Automation Conference, pages 77–82, 2005.
[19] A. Devgan and C. Kashyap. Block-based static timing analysis with uncertainty. In IEEE International Conference on Computer-Aided Design, pages 607–614, 2003.
[20] S. Boyd, S.-J. Kim, D. Patil, and M. Horowitz. A heuristic method for statistical digital circuit sizing. Proceedings of SPIE, 6156.
[21] S. H. Choi, B. C. Paul, and K. Roy. Novel sizing algorithm for yield improvement under process variation in nanometer technology. In Design Automation Conference, pages 454–459, 2004.
[22] M. Mani, A. K. Singh, and M. Orshansky. Joint design-time and post-silicon minimization of parametric yield loss using adjustable robust optimization. In IEEE International Conference on Computer-Aided Design, pages 19–26, 2006.
[23] J. M. Hammersley and D. C. Handscomb. Monte Carlo Methods. Methuen’s monographs, London, 1964.
[24] C. E. Clark. The greatest of a finite set of random variables. 9:145–162, March-April 1961.
[25] Richard P. Stanley. Enumerative combinatorics. Cambridge University Press, New York, 1994.
[26] R. A. Johnson and D. W. Wichern. Applied Multivariate Statistical Analysis. Prentice-Hall, Upper Saddle River, New York, 5th edition, 2002.
[27] C. Daniel and F. S. Wood. Fitting Equations to Data: Computer Analysis of Multifactor Data. John Wiley, New York, 2nd edition, 1980.
[28] SAS. Available from http://www.sas.com/.
[29] The MOSEK optimization software. Available form http://www.mosek.com.
[30] Neil H.E. Weste and David Harris. CMOS VLSI Design: A Circuits and Systems Perspective. Addison-Wesley, 75 Arlington St., Suite 3000, Boston, MA, 3rd edition, 2004.
[31] P. Ko et al. BSIM3 for analog and digital circuit simulation. In IEEE Symposium VLSI Tech. CAD, pages 400–429, 1993.
[32] Z. H. Liu et al. Threshold voltage model for deep-submicrometer MOSFETs. IEEE Tran. Electron Devices, 40.
[33] A. Keshavarzi, S. Ma, S. Narendra, B. Bloechel, K. Mistry, T. Ghani, S. Borkar, and V. De. Effectiveness of reverse body bias for leakage control in scaled dual Vt CMOS ICs. In International Symposium on Low Power Electronics and Design.
[34] S. M. Martin, K. Flautner, T. Mudge, and D. Blaauw. Combined dynamic voltage scaling and adaptive body biasing for lower power microprocessors under dynamic workloads. In IEEE International Conference on Computer-Aided Design, pages 721–725, 2002.
[35] P. W. Cook, D. L. Critchlow, and L. M. Terman. Comparison of MOSFET logic circuits. IEEE J. Solid-State Circuits, 8:348–355, October 1973.
[36] S. Mutoh, T. Douseki, Y. Matsuya, T. Aoki, S. Shigematsu, and J. Yamada. 1-V power supply high-speed digital circuit technology with multithreshold-voltage CMOS. IEEE J. Solid-State Circuits, 30:847–854, August 1995.
[37] James T. Kao and Anantha P. Chandrakasan. Dual-threshold voltage techniques for low-power digital circuits. IEEE J. Solid-State Circuits, 35:1009– 1018, July 2000.
[38] Benton H. Calhoun and Anantha P. Chandrakasan. Ultra-dynamic voltage scaling (UDVS) using sub-threshold operation and local voltage dithering. IEEE J. Solid-State Circuits, 4:238–245, January 2006.
[39] Liqiong Wei, Kaushik Roy, and Cheng-Kok Koh. Power minimization by simultaneous dual Vth assignment and gate-sizing. In Custom Integrated Circuits Conference, pages 413–416, May 2000.
[40] Yan Meng, Timothy Sherwood, and Ryan Kastner. Leakage power reduction of embedded memories on FPGAs through location assignment. In Design Automation Conference, pages 612–617, 2006.
[41] Mingoo Seok, Scott Hanson, Dennis Sylvester, and David Blaauw. Analysis and optimization of sleep modes in subthreshold circuit design. In Design Automation Conference, pages 694–699, 2007.
[42] M. Horiguchi, T. Sakata, and K. Itoh. Switched-source-impedance CMOS circuit for low standby subthreshold current giga-scale LSIs. IEEE J. Solid-State Circuits, 28:1131–1135, November 1993.
[43] Fei Li, Yan Lin, Lei He, and Jason Cong. Low-power FPGA using pre-defined dual-Vdd/dual-Vt fabrics. In International Symposium on Field Programmable Gate Arrays, pages 42–50, 2004.
[44] Li, F., Yan Lin, and Lei He. FPGA power reduction using configurable dual Vdd. In Design Automation Conference, pages 735–740, 2004.
[45] A. Gayasen, Y. Tsai, N. Vijaykrishnan, M. Kandemir, M.J. Irwin, and T. Tuan. Reducing leakage energy in FPGAs using region-constrained placement. In International Symposium on Field Programmable Gate Arrays, pages 51–58, 2004.
[46] Georges Nabaa, Navid Azizi, and Farid N. Najm. An adaptive FPGA architecture with process variation compensation and reduced leakage. In Design Automation Conference, pages 624–629, 2006.
[47] L. Cheng, P. Wong, F. Li, Y. Lin, and L. He. Device and architecture co-optimization for FPGA power reduction. In Design Automation Conference, pages 915–920, 2005.
[48] Jason H. Anderson and Farid N. Najm. Low-power programmable routing circuitry for FPGAs. In International Symposium on Field Programmable Gate Arrays, pages 602–609, 2004.
[49] J. W. Tschanz et al. Dynamic sleep transistor and body bias for active leakage power control of microprocessors. IEEE J. Solid-State Circuits, 38:1838–1845, November 2003.
[50] M. Nomura et al. Delay and power monitoring schemes for minimizing power consumption by means of supply and threshold voltage control in active and standby modes. IEEE J. Solid-State Circuits, 4:805–814, April 2006.
[51] W. Zhao and Y. Cao. New generation of predictive technology model for sub-45nm design exploration. In International Symposium on Quality Electronic Design, pages 585–590, 2006.
[52] CVX: Matlab software for disciplined convex programming. Available from http://www.stanford.edu/ boyd/cvx.
[53] Haitham Hindi. A tutorial on convex optimization. In American Control Conference, pages 3252– 3265, 2004.
[54] ABC: A system for sequential synthesis and verification. Available from http://www.eecs.berkeley.edu/ alanmi/abc/.
[55] B. N Lee, Li-C. Wang, and M. S. Abadir. Refined statistical static timing analysis through learning spatial delay correlations. In Design Automation Conference, pages 149–154, 2006.
[56] A. Andrei, M. Schmiz, P. Eles, Z. Peng, and B. M. Al-Hashimi. Overhead-conscious voltage selection for dynamic and leakage energy reduction of time-constrained systems. In Design, Automation and Test in Europe Conference and Exhibition, pages 518–523, 2004.