臺灣博碩士論文加值系統

在數位電路系統，利用功率管理機制所能節省的能量消耗取決於休眠時間的長短。以往功率管理機制在暫存器轉移階層以下階層實現。然而，調整設計的彈性將受限於實現的階層。我們提出在較早的設計階段規劃功率管理機制的概念。因此，可節省的能量消耗將可增加。我們提出的方法從演算法階層開始進行功率管理導向的硬體分割演算法。使用了基因演算法及反覆改進啟發式演算法來探索適合功率管理的硬體分割。實驗結果顯示使用提出的演算法所得到的結果與利用窮盡式演算法相近。

In digital systems, the amount of energy can be saved by power management depending on the length available idle time. Transitionally power management is considered and implemented at register-transfer level. However, the level of flexibility for changing the design is limited. We propose to move the power-management planning to an earlier design stage. Thus, the energy saving can be maximized. The proposed approach starts from algorithmic level to perform power-management oriented hardware partitioning. The hybrid genetic and iterative heuristic can explore for near-to-optimal cases under practical conditions. Experimental results show that our fast exploration is very close to the exhaustive approach.

Chapter 1 Introduction 1
1.1 Sources of power consumption 2
1.2 Dynamic power management 3
1.3 Partitioning of VLSI circuits and systems 7
1.3.1 Iterative improvement 8
1.3.2 Simulated annealing 9
1.3.3 Tabu search 10
1.3.4 Genetic algorithm 10
1.4 Motivation 11
1.5 Contributions 13
1.6 Thesis organization 13
Chapter 2 Literature Survey 14
2.1 Power-management aware methodology in high-level synthesis 14
2.2 Power-management aware partitioning 16
Chapter 3 Proposed Algorithm 20
3.1 Preliminary 20
3.2 Procedures 21
3.3 Parsing and extraction stage 22
3.4 Scheduling stage 25
3.5 Assignment stage 29
3.6 Partitioning stage 30
3.6.1 Problem definitions 31
3.6.2 Genetic algorithm 34
3.6.3 Iterative improvement algorithm 38
Chapter 4 Experimental Results 40
4.1 Test cases 40
4.2 Power and timing model 40
4.3 Evaluative function 41
4.4 Experimental results and discussion 44
4.5 Verification 52
Chapter 5 Conclusions and Future Works 55
5.1 Conclusions 55
5.2 Future works 56
References 57

[1]Http://www.tsmc.com
[2]L. Benini and G. De Micheli, “System-Level Power Optimization: Techniques and Tools,” ACM Trans. Design Automation of Electronic Systems, Vol. 5, Issue 2, pp. 115-192, Apr. 2000.
[3]L. Benini, A. Bogliolo, and G. De Micheli, “A survey of design techniques for system-level dynamic power management, ” IEEE Transactions on VLSI systems, Vol. 8, Issue 3, pp. 299-316, June 2000.
[4]Y.-H. Lu and G. De Micheli, “Comparing System-Level Power Management Policies,” IEEE Design and Test, Vol. 18, Issue 2, pp. 10-19, Mar. 2001.
[5]L. Benini, G. Paleologo, A. Bogliolo, and G. De Micheli, “Policy optimization for dynamic power management,” IEEE Trans. Computer-Aided Design, Vol. 18, Issue 6, pp. 813-833, June 1999.
[6]L. Benini, A. Bogliolo, and G. D. Micheli. “Dynamic power management of electronic systems,” in International Conference on Computer-Aided Design, pp. 696–702, 1998.
[7]Microsoft. (1997) On now: The evolution of the PC platform. [Online] http://www.microsoft.com/hwdev/pcfuture/OnNOW.htm.
[8]Intel, Microsoft, and Toshiba. (1996) Advanced configuration and power interface specification. [Online] http://www.intel.com/ial/powermgm/specs.html.
[9]F. M. Johnnes, “Partitioning of VLSI circuits and systems,” in Proceedings of the 33rd ACM/IEEE Design Automation Conference, pp. 83–87, June 1996.
[10]H. Vaishnav and M. Pedram, “Delay optimal partitioning targeting low power VLSI circuits,” in International Conference on Computer Aided Design, pp. 216-222, Nov. 1995.
[11]F. Vahid and D. G. Gajski, “Specification partitioning for system design,” in Proceeding Design Automation Conference, pp. 219-224, June 1992.
[12]V. Srinivasan, S. Govindarajan, and R. Vemuri, “Fine-Grained and Coarse-Grained Behavioral Partitioning With Effective Utilization of Memory and Design Space Exploration for Multi-FPGA Architectures,” IEEE Trans. on Very Large Scale Integration (VLSI) Systems, Vol. 9, No. 1, pp. 140–158, Feb. 2001.
[13]C. J. Alpert and A. B. Kahng, “Recent directions in netlist partitioning: a survey,” Integration, the VLSI Journal, vol. 19, issue 1-2, pp. 1-81, August 1995.
[14]B. W. Kernighan and S. Lin, “An efficient heuristic procedure for partitioning graphs,” Bell Systems Technology J, Vol. 49, No. 2, pp. 292-370, Feb. 1970.
[15]C. M. Fiduccia and R. M. Mattheyses, “A linear-time heuristic for improving network partitions,” in Proceedings of 19th Design Automation Conference, pp.175-181, June 1982.
[16]S. Kirkpatrick, C. D. Gelatt, Jr., and M. P. Vecchi, “Optimization by simulated annealing,” Science 220, Vol. 220. No. 4598, pp. 671-680, May 1983.
[17]F. Glover. Tabu search - part i. ORSA Journal on Computing, Vol.1, No.3, pp.190-206, 1989.
[18]A. Stammermann et al. “System level optimization and design space exploration for low power,” in Proceedings of the 14th International Symposium on System Synthesis, pp.142-146, 2001.
[19]F. Vahid, “Techniques for minimizing and balancing I/O during functional partitioning,” IEEE Trans. Computer-Aided Design, Vol.18, No.1, pp. 69-75, Jan. 1999.
[20]J. Monteiro, S. Devadas, P. Ashar, and A. Mauskar, “Scheduling Technique to Enable Power Management,” in Proceedings of Design Automation Conference, pp.349-352, 1996.
[21]D. Dal, D. Kutagulla, A. Nunez, and N. Mansouri. “Power Islands: A High-Level Synthesis Technique for Reducing Spurious Switching Activity and Leakage,” in Proceeding of IEEE International Midwest Symposium on Circuits and Systems, Vol.2, pp. 1875-1879, Aug. 2005.
[22]G. Lakshminarayana, A. Raghunathan, N.K. JHA, and S. Dey. “Power management in high level synthesis,” IEEE Trans. Very Large Scale Integrated System, Vol. 7, Issue 1, pp. 7-15, 1999.
[23]E. Hwang, F. Vahid, Y. C. Hsu, “FSMD Functional Partitioning for Low Power,” in Proceedings of Design Automation and Test in Europe, pp.22-28, Mar. 1999.
[24]H. Farrahi and M. Sarrafzadeh, “Geo_Part: A System Partitioning Algorithm to Maximize Sleep Time,” Digest of the Technical Papers of the International Conference on Computer-Aided Design, 1995, San Jose, CA.
[25]P Ghafari, E Mirhadi, M Anis, A Areibi, M Elmasry, “A low-power partitioning methodology by maximizing sleep time and minimizing cut nets,” in Proceedings of System-on-Chip for Real-Time Applications, pp.368- 371, July 2005.
[26]A. Farrahi, G. Tellez, and M. Sarrafzadeh, “Exploiting Sleep Mode for Memory Partitions and Other Applications,” VLSI Design, Vol. 7, No. 3, pp. 271-287,1995.
[27]K. S. Chung, T. Kim and C. I. Liu, “Behavioral-level partitioning for low power design in control-dominated application,” in Proceedings of the 10th Great Lakes symposium on VLSI, pp. 156-161, 2000.
[28]L. Benini, P. Vuillod, G. De Micheli and C. Coelho, “Synthesis of Low-Power Selectively-Clocked Systems from High-Level Specification,” In Proceeding of International Symposium on System Synthesis, pp. 57-63, Nov. 1996.
[29]A. Farrahi, C. Chen, A. Srivastava, G. Tellez and M. Sarrafzadeh, “Activity-Driven Clock Design,” IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, Vol. 20, No. 6, pp. 705-714, Jun. 2001.
[30]J. M. Rabaey, “Digital integrated circuits: a design perspective,” Prentice-Hall, Inc., Upper Saddle River, NJ, 1996.
[31]K. Roy and S. Prasad, “Low-Power CMOS VLSI Circuit Design,” John Wiley &Sons, Inc, 2000.
[32]G. De Micheli, “Synthesis and optimization of digital circuits,” McGrawHill, New York, 1994.
[33]M. Wall, “Galib: a C++ library of genetic algorithm components,” Mass. Inst. Technol., Tech. Rep., Aug. 1996.