跳到主要內容

臺灣博碩士論文加值系統

(35.168.110.128) 您好!臺灣時間:2022/08/16 05:07
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:游逸平
研究生(外文):Yi-Ping You
論文名稱:低功率之編譯器及作業系統最佳化技術
論文名稱(外文):Compiler and OS Optimizations for Low Power
指導教授:李政崑
指導教授(外文):Jenq Kuen Lee
學位類別:碩士
校院名稱:國立清華大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:英文
論文頁數:77
中文關鍵詞:嵌入式系統低功率編譯器低功率作業系統漏電消秏可變電壓排程
外文關鍵詞:Embedded SystemsCompiler for Low PowerPower-Aware Operating SystemsLeakage Power ConsmuptionVariable Voltage Schedulings
相關次數:
  • 被引用被引用:0
  • 點閱點閱:193
  • 評分評分:
  • 下載下載:24
  • 收藏至我的研究室書目清單書目收藏:1
對系統設計者而言,減少電力消耗是一項艱鋸的工作。一般可攜帶式系統(如筆記型電腦、手持式裝置)都是消耗電池的電力,因此減少電力消秏即意味著延長電池壽命。在這篇論文中,我提出兩套減少耗能的軟體技術:編譯器技術和作業系統技術。
在編譯器技術方面,我提出一套考量管路硬體架構的資料流分析方法,此方法用來估計某硬體元件在程式中某執行點的活動狀態,以減少未使用元件的漏電消秏。由於切斷某元件電源的時間長短與程式中的分支有關,因此我提出三種針對電源切斷指令的排程機制:Basic_Blk_Sched、MIN_Path_Sched及AVG_Path_Sched。另外,我也將此方法結合到SUIF及MachSUIF編譯器系統中以證實此方法的有效性,我的實驗平台為以具有電源切斷機制的Alpha 21264處理器為平台的模擬器Wattch,實驗結果顯示我們的方法相對於時脈切斷機制,對浮點運算元件可減少82%的電源消耗,而對整體元件而言亦可減少9.9%的電源消秏。
在作業系統方面,我將重點放在即時系統下可變動電壓之處理器的排程問題。我提出一套以知名的EDF (Earliest Deadline First)為基礎的保留表排程演算法以及六套用來決定處理器電壓的演算法。我的實驗是以一套工作集CNC(Computerized Numberical Control)為應用的模擬平台,實驗結果顯示我的可動電壓排程方法相較一般固定電壓排程方法可減少62%的電源消秏。

Reducing power consumption is a crucial challenge to system designers. Portable systems, such as laptop computers and handheld devices, draw power from batteries, so reducing power consumption prolongs battery life. In this thesis, we promote two software techniques for power reduction: the compiler and the operation system solutions.
In the compiler approach, a data-flow analysis framework which estimates the component activities at fixed points of programs with the consideration of pipelines of architectures is proposed to reduce leakage power consumption of useless components. As the duration of power gating on components on given program routines is related to program branches, three scheduling mechanisms for power-gating instructions, called Basic_Blk_Sched, MIN_Path_Sched, and AVG_Path_Sched, are presented and discussed. In addition, we describe a prototype implementation of our approach in SUIF and MachSUIF, a compiler system, to validate the effectiveness. We build the experimental architecture, which is compatible with the DEC Alpha 21264 processor and employs power gating mechanism, within the Wattch simulation environment. The experiments show that our approach reduces average 82% of power consumption for floating-point units and average 9.9% for total power consumption against the clock gating mechanism.
In the operating system approach, we focus the issue on scheduling problems for variable voltage processors in real-time systems. A reservation list scheduling algorithm based on the well-known EDF (Earliest Deadline First) and six decision algorithms which help to decide the voltage of processors are proposed. Also, simulation results of our scheduling polices on a CNC (Computerized Numberical Control) machine controller, a task set, are presented. The simulation results show that our variable voltage scheduling policies is about 62% power reduction against the fixed voltage systems.

Acknowledgements i
Abstract ii
Contents iv
List of Figures vi
List of Tables viii
1 Introduction 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . 1
1.2 Thesis Overview . . . . . . . . . . . . . . . . . 5
1.2.1 The Compiler Approach . . . . . . . . . . . 5
1.2.2 The Operating System Approach . . . . . . . 6
2 The Compiler Approach 8
2.1 Overview . . . . . . . . . . . . . . . . . . . . 8
2.2 Machine Architecture . . . . . . . . . . . . . . 9
2.3 Component-Activity Data-Flow Analysis . . . . . . 11
2.4 Leakage Power Reduction . . . . . . . . . . . . . 17
2.4.1 Cost Model . . . . . . . . . . . . . . . . 17
2.4.2 Scheduling Policies for Power Gating . . . 18
2.5 Experimental Results . . . . . . . . . . . . . . 22
2.5.1 Platform . . . . . . . . . . . . . . . . . 22
2.5.2 Results . . . . . . . . . . . . . . . . . . 24
2.6 Conclusions . . . . . . . . . . . . . . . . . . . 28
3 The Operating System Approach 29
3.1 Overview . . . . . . . . . . . . . . . . . . . . 29
3.2 Preliminaries . . . . . . . . . . . . . . . . . . 30
3.2.1 Task Model . . . . . . . . . . . . . . . . 30
3.2.2 Power Model . . . . . . . . . . . . . . . . 30
3.2.3 Variable Voltage Model . . . . . . . . . . 31
3.3 Variable Voltage Scheduling . . . . . . . . . . . 32
3.3.1 Scheduling Algorithm . . . . . . . . . . . 32
3.3.2 Slack Computation . . . . . . . . . . . . . 34
3.3.3 Decision Algorithm . . . . . . . . . . . . 35
3.4 Running Examples . . . . . . . . . . . . . . . . 38
3.5 Experiments and Discussion . . . . . . . . . . . 43
4 Related Work 48
4.1 The Compiler Approach . . . . . . . . . . . . . . 48
4.2 The Operating System Approach . . . . . . . . . . 49
5 Conclusion 50
5.1 Summary . . . . . . . . . . . . . . . . . . . . . 50
5.2 Future Work . . . . . . . . . . . . . . . . . . . 52
Bibliography 54

[1] Al Aburto, collections of common benchmarks of FAQ of comp.benchmarks
USENET newsgroup, ftp site: ftp.nosc.mail/pub/aburto.
[2] A. Aho, R. Sethi, J. Ullman, Compilers Principles, Techniques, and Tools,
Addison-Wesley, 1985. Compiler
[3] M. Alidina, J. Monteiro, S. Devadas, A. Ghosh and M. Papaefthymiou,
"Precomputation-Based Sequential Logic Optimization for Low Power," Proc.
of ICCAD-94, pp. 74-81, 1994.
[4] S. Baruah, G. Koren, D. Mao, B. Mishra, A. Raghunathan, L. Rosier, D. hasha
and F. Wang. "On the competitiveness of on-line real-time task scheduling",
Proc. of the 12th Real-Time Systems Symposium, San Antonio, Texas, pp. 106-
115, December 1991.
[5] Luca Benini and G. De Micheli, "State Assignment for Low Power Dissipation,"
IEEE Journal of Solid State Circuits, Vol. 30, No. 3, pp. 258-268, March 1995.
[6] Nikolaos Bellas, Ibrahim N. Hajj, and Constantine D. Polychronopoulos, "Ar-
chitectural and Compiler Techniques for Energy Reduction in High-Performance
Microprocessors," IEEE Transactions on Very Large Scale Integration (VLSI)
Systems, pp. 317-326, June 2000.
[7] D. Brooks, V. Tiwari, and M. Martonosi, "Wattch: a Framework for
Architectural-Level Power Analysis and Optimizations," Proc. 27th. Interna-
tional Symposium on Computer Architecture, pp. 83-94, June 2000.
[8] D. Burger and T. M. Austin, "The SimpleScalar Tool Set, Version 2.0," Com-
puter Architecture News, pp. 13-25, June 1997.
[9] J. Adam Butts and Gurindar S. Sohi, "A Static Power Model for Architects,"
Proceedings of the 33rd Annual IEEE/ACM International Symposium on Mi-
croarchitecture, pp. 191-201, December 2000.
[10] A.P. Chandrakasan, S. Sheng, and R.W. Brodersen, "Low-Power CMOS Digital
Design," IEEE Journal of Solid-State Circuits, Vol. 27, No.4, pp. 473-484, April
1992.
[11] Jui-Ming Chang, Massoud Pedram, "Register Allocation and Binding for Low
Power," Proceedings of Design Automaton Conference, San Francisco, USA, June
1995.
[12] Compaq Computer Corporation, Alpha 21264 Microprocessor Hardware Refer-
ence Manual, EC-RJRZA-TE, (July 1999).
[13] V. De and S. Borkar, "Technology and design challenges for low power and
high performance," Proc. of Int. Symp. Low Power Electronics and Design, pp.
163-168, 1999.
[14] M. R. Garey and D.S. Johnson, "Computer and Intractability: A Guide to the
theory of NP-Completeness," W. H. Freeman & Co., New York, NY, 1979.
[15] G. Hachtel, M. Hermida, A. Pardo, M. Poncino and F. Somenzi, "Re-Encoding
Sequential Circuits to Reduce Power Dissipation," Proc. of ICCAD' 94, pp. 70-
73, 1994.
[16] G. Hadjiyiannis, S. Hanono and S. Devadas. "HHD97: An Instruction Set De-
scription Language for Retargetability," Design Automation Conference, June
1997.
[17] Inki Hong, Darko Dirovski, et.al., "Power Optimization of Variable Voltage Core-
Based Systems," Proc. of 35th DAC, pp. 176-181, 1998.
[18] I. Hong, M. Potkonjak, and M. Srivastava, "On-Line Scheduling of Hard Real-
Time Tasks on Variable Voltage Processor," Proc. of the International Confer-
ence on Computer-Aided Design (ICCAD'98), Nov. 1998.
[19] I. Hong, G. Qu, M. Potkonjak, and M. B. Srivastava, "Synthesis techniques
for low-power hard real-time systems on variable-voltage processors," Proc. of
Real-Time Systems Symposium, pp. 178-187, 1998.
[20] M. Horowitz, T. Indermaur, and R. Gonzalez, "Low-Power Digital Design,"
Proceedings of the 1994 IEEE Symposium on Low Power Electronics, pp. 8-11.
[21] Intel corporation, "Pentium III Processor for the SC242 at 450 MHz to 1.13 GHz
Datasheet," pp. 26-30.
[22] T. ISHIHARA, and H. YASUURA, "Voltage Scheduling Problem for Dynam-
ically Variable Voltage Processors," Proc. of International Symposium on Low
Power Electronics and Design (ISLPED'98), August 1998.
[23] J. T. Kao and A. P. Chandrakasan, "Dual-threshold voltage techniques for low-
power digital circuits," IEEEJournal of Solid-state circuits, 35(7):1009-1018,
July 2000.
[24] S. Kaxiras, Z.Hu and M.Martonosi, "Cache Decay: Exploiting Generational
Behavior to Reduce Cache Leakage Power," Proc. of the Int'l Symposium on
Computer Architecture, pp.240-251, 2001.
[25] N. Kim, M. Ryu, S. Hong, M. Saksena, C.-H. Choi, and H. Shin, "Visual As-
sessment of a Real-Time System Design: A Case Study on a CNC Controler,"
Real-Time Systems Symposium, 1996., 17th IEEE, pp.300-310, 1996.
[26] Chingren Lee, Jenq Kuen Lee, TingTing Hwang, and Shi-Chun Tsai, "Compiler
Optimization on Instruction Scheduling for Low Power," Proceedings of the 13th
International Symposium on Systems Synthesis, pp. 55 - 60, September 2000.
[27] Mike Tien-Chien Lee, Vivek Tiwari, Sharad Malik, Masahiro Fujita, "Power
Analysis and Minimization Techniques for Embedded DSP Software," IEEE
Transactions on VLSI Systems, March 1997, Vol. 5, no. 1, pp. 123-133.
[28] C. L. Liu and J. Layland, "Scheduling Algorithms for Multiprogramming in a
Hard Read-Time Environment," Journal of the ACM, vol. 20, pp. 46-61, 1973.
[29] A. Manzak and C. Chakrabarti, "Variable Voltage Task Scheduling for Mini-
mizing Energy or Minimizing Power," Proc. of the International Conference on
Acoustics, Speech and Signal Processing, June 2000.
[30] D. Mosse, H. Aydin, B. Childers, and R. Melhem, "Compiler-Assisted Dynamic
Power-Aware Scheduling for Real-Time Applications," COLP (Workshop on
Compiler and OS for Low Power), Philadelphia, Oct 19, 2000.
[31] Won Namgoong, Mengchen Yu, and Teresa Meng, "A High-Efficiency Variable-
Voltage CMOS Dynamic DC-DC Switching Regulator," IEEE International
Solid-State Circuits Conference, pp. 380-381, 1997.
[32] T. Pering, T. Burd, R. Brodersen, "The Simulation and Evaluation of Dynamic
Voltage Scaling Algorithms," Low Power Electronics and Design, 1998. Proceed-
ings. 1998 International Symposium on, pp.76-81, May 1998.
[33] M.D. Powell, S-H. Yang, B. Falsa, K. Roy, and T.N. Vijaykumar, "Gated-Vdd:
a Circuit Technique to Reduce Leakage in Deep-Submicron Cache Memories,"
ACM/IEEE International Symposium on Low Power Electronics and Design
(ISLPED), 2000.
[34] S. C. Prasad and K. Roy, "Circuit Activity Driven Multilevel Logic Optimization
for Low Power Reliable Operation," Proceedings of the EDAC'93 EURO-ASIC ,
pp. 368-372, Feb., 1993.
[35] J. M. Rabaey and M. Pedram, Low Power Design Methodologies. Norwell, MA:
Kluwer, 1996.
[36] K. Roy and S. C. Prasad, "SYCLOP: Synthesis of CMOS Logic for Low Power
Applications," Proceedings of the ICCD, pp. 464-467, 1992.
[37] K. Roy, "Leakage Power reduction in Low-Voltage CMOS Designs," IEEE In-
ternational Conference on Circuits and Systems, Vol. 2, pp. 167-173, 1998.
[38] Michael D. Smith, "The SUIF Machine Library", Division of of Engineering and
Applied Science, Harvard University, March 1998.
[39] Wei-Kuan Shih, Jane W. S. Liu, and Jen-Yao. Chung. Algorithms for scheduling
imprecise computations with timing constraints, SIAM J. on Computing, Vol. 20,
No. 3. 1991.
[40] Wei-Kuan Shih, Jane W. S. Liu, On-line Algorithm for Scheduling Imprecise
Computations, SIAM J. on Computing, Oct(1996). pp. 1105-1121.
[41] Y. Shin and K. Choi, "Power conscious fxed priority scheduling for hard real-
time systems," Proc. Design Automation Conference (DAC), pp.134-139, June
1999.
[42] Stanford Compiler Group, "The SUIF Library", Stanford Compiler Group, Stan-
ford, March 1995.
[43] Ching-Long Su and Alvin M. Despain, "Cache Designs for Energy Efficiency,"
Proceedings of the 28th Annual Hawaii International Conference on System Sci-
ences, pp. 306 -315, 1995.
[44] V. Swaminathan and K. Chakrabarty, "Real-time task scheduling for energy-
aware embedded systems," IEEE Real-Time Systems Symposium W ork In
P rogress Sessions, 2000.
[45] V. Tiwari, R. Donnelly, S. Malik, and R. Gonzalez, "Dynamic Power Manage-
ment for Microprocessors: A Case Study," Proceedings of the 10th International
Conference on VLSI Design, pp. 185-192, 1997.
[46] V. Tiwari, D. Singh, S. Rajgopal, G. Mehta, R. Patel, and F. Baez, "Reducing
Power in High-Performance Microprocessors," Proceedings of the Design Au-
tomaton Conference, pp. 732-737, 1998.
[47] Scott Thompson, Paul Packan, and Mark Bohr, "MOS Scaling: Transistor Chal-
lenges for the 21st Century," Portland Technology Development, Intel Corp. Intel
Technology Journal, Q3 1998.
[48] C.Y. Tsui, M. Pedram, and A.M. Despain, "Technology Decomposition and
Mapping Targeting Low Power Dissipation," Proc. of 30th Design Automaton
Conf., pp.68-73, June 1993.
[49] F. Yao, A. Demers, and S. Shenker, "A scheduling model for reduced CPU en-
ergy," Foundations of Computer Science, 1995. Proceedings., 36th Annual Sym-
posium on, pp.374 -382, June 1995.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top