臺灣博碩士論文加值系統

在需仰賴電池為主要供電來源的手持裝置中，節省能源是一個相當重要的課題，其中DVFS是一種低功耗的機制，可以在系統正在運行的情況下節省能源。在過去的研究中，我們提出MAR-CSE等式用來描述處理器的頻率與記憶體存取率之間的關係，使其將能源消耗保持在最小狀況。
然而MAR-CSE等式並不能應付所有的情況，甚至導致多餘的能源消耗。舉例來說，在一固定的時間區間內記憶體存取率與總被執行的指令數皆為低的情況下，MAR-CSE等式會誤判並且將處理器的頻率提高。然而此時提高頻率並不會大幅提升程式的效能，反而提升能源消耗。
這論文中，我們提出一個基於MAR-CSE等式並且利用CPU使用率來輔助判斷頻率的DVFS演算法，我們利用MiBench這套測量程式以及一些在Linux中常用的指令求出切換頻率或決策頻率的機制來調整處理器的頻率。在實作測試中，我們利用Linux中CPUfreq governor的架構來實作我們的演算法，並且利用EDP作為評估的指標。

Saving energy is an important target for portable devices which are powered by batteries. Among low power mechanisms, DVFS is an efficient method which can reduce energy consumption while tasks are running. In our previous studies, we found a relationship between the memory access rate and the frequency which minimizes the energy consumption. We have proposed an equation named MAR-CSE which represents this relationship and is used to perform dynamic frequency selection.
However, the MAR-CSE equation cannot handle all the cases. It may cause the energy consumption to be increased inversely. For example, if both of the memory access rate and the number of instruction executed are low, the system will scale up the frequency according to the MAR-CSE equation. This may not be correct, because the system could be in an I/O state. A low frequency will be more suitable for this case.
In this thesis, we improve our MAR-CSE-based DVFS algorithm. The CPU utilization is considered in the algorithm. We use the MiBench benchmarks and some utility programs in Linux to find the thresholds which can distinguish among I/O bound, memory bound, and CPU bound according to the memory access rate and the CPU utilization information. We have implemented the algorithm in the Linux kernel based on the CPUfreq subsystem, a processor power management architecture for Linux. The EDP metric is used to prove our algorithm is good at energy saving and low performance loss.

摘　要 ii
ABSTRACT iii
誌謝 v
Table of Content vi
List of Tables viii
Table of Figures ix
Chapter 1 INTRODUCTION 1
1.1 Motivation and Objectives 1
1.2 MAR-CSE Equation 1
1.3 Problem of the MAR-CSE Method 1
1.4 Contributions 2
1.5 Thesis Structure 3
Chapter 2 RELATED WORKS 4
2.1 Memory Access Rate 4
2.2 Information of CPU 5
2.3 EDP Metric 5
Chapter 3 PROBLEMS OF THE MAR-CSE METHOD 7
3.1 MAR-CSE Equation 7
3.2 CPU Utilization 9
3.3 Problems of the MAR-CSE Method 9
Chapter 4 DISCUSSIONS OF CONDITIONS 13
4.1 Separating the Records 13
4.2 X-Y Scatter Diagram 14
4.3 Program Behavior Property Regions 16
Chapter 5 ALGORITHMS 20
Chapter 6 IMPLEMENTATIONS 22
Chapter 7 EXPERIMENTS 24
7.1 Experiment Setup 24
7.2 Comparisons 24
7.3 Experiments Result 24
Chapter 8 CONCLUSIONS 27
REFERENCES 28
APPENDIEX A The Thresholds of Executed Instructions in 200ms 31
APPENDIEX B The Records of Benchmarks 33

[1]NI LabVIEW ：http://www.ni.com/labview/zht/
[2]NI DAQ：http://www.ni.com/dataacquisition/zht/
[3]Wen-Yew Liang, Shih-Chang Chen, Yang-Lang Chang, Jyh-Perng Fang, “Memory-Aware Dynamic Voltage and Frequency Prediction for Portable Devices”, Embedded and Real-Time Computing Systems and Applications, RTCSA ''08. 14th IEEE, 2008.
[4]Mark Horowitz, Thomas Indermaur, and Ricardo Gonzalez, “Low-Power Digital Design”, IEEE Symposium on Low Power Electronics, 1994
[5]Wen-Chang Chung and Wen-Yew Liang, "The Study and Implementation of Operating System Porting for Android " Communication of Institute of Information and Computing Machinery, Vol. 12, No. 3, pp. 35-48, 2009.
[6]Xia Zhao, Yao Guo, Xiangqun Chen, “Transaction-Based Adaptive Dynamic Voltage Scaling for Interactive Applications”, ISLPED ''09 Proceedings of the 14th ACM/IEEE international symposium on Low power electronics and design, 2009
[7]Margaret Martonosi, David Brooks, Pradip Bose “Modeling and analyzing CPU power and performance: Metrics, methods, and abstractions” Tutorials Program - SIGMETRICS 2001 / Performance, 2001
[8]Canturk Isci, Gilberto Contreras and Margaret Martonosi ,“Live, Runtime Phase Monitoring and Prediction on Real Systems”, MICRO 39 Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, 2006.
[9]Wen-Yew Liang and Po-Ting Lai, "Design and Implementation of a Critical Speed-based DVFS Mechanism for the Android Operating System," in Proc. of the 5th International Conference on Embedded and Multimedia Computing (EMC-10), Cebu, Philippines, Aug 2010, pp. 11-13.
[10]Mohamed Shalan and Dina El-Sissy, “Online Power Management using DVFS for RTOS”, the 4th International Design and Test Workshop (IDT), 2009.
[11]Venkatesh Pallipadi and Alexey Starikovskiy, “The Ondemand Governor”, Proceedings of the Linux Symposium, volume 2, July 2006, pp. 215–230.
[12]David C. Snowdon, Stefan M. Petters, and Gernot Heiser, ” Accurate On-line Prediction of Processor and Memory Energy Usage Under Voltage Scaling”, Proceedings of the 7th ACM & IEEE international conference on Embedded software, September 30–October 3, 2007.
[13]Jinuk Choi and Hojung Cha, “A Processor Power Management Scheme for Handheld Systems Considering Off-Chip Contributions”, IEEE Transactions on Industrial Informatics, 2010.
[14]Leo Singleton, Christian Poellabauer, and Karsten Schwan,” Monitoring of Cache Miss Rates for Accurate Dynamic Voltage and Frequency Scaling”, the 12th Annual Multimedia Computing and Networking Conference, 2005.
[15]Miroslav Vasic, Oscar Garcia, Pedro Alou, Jesus A. Oliver, Jose A. Cobos, “Trade-off between energy savings and execution time applying DVS to a microprocessor”, CIPS 5th International Conference on Integrated Power Electronics Systems, 2008.
[16]Gang Qu, “What is the Limit of Energy Saving by Dynamic Voltage Scaling”, International Conference on Computer Aided Design, 2001.
[17]Zhang YuHua, Qian LongHua,Lv Qiang, Qian Peide, Guo Shengchao, “A Practical Dynamic Frequency Scaling Solution to DPM in Embedded Linux Systems”, Journal of Computers, Vol 4, No 8, 2009, pp. 787-793
[18]Guthaus M.R, Ringenberg J.S, Ernst D, Austin T.M, Mudge T, Brown R.B, “Mibench: A free commercially representative embedded benchmark suite ”, IEEE International Workshop on Workload Characterization, 2001.
[19]Robert Schöne and Daniel Hackenberg, “On-line analysis of hardware performance events for workload characterization and processor frequency scaling decisions”, ICPE Proceeding of the second joint WOSP/SIPEW international conference on Performance engineering, 2011.
[20]Wen-Yew Liang, Yen-Lin Chen, and Ming-Feng Chang, “A Memory-aware Energy Saving Algorithm with Performance Consideration for Battery-enable Embedded Systems”, The 15th IEEE Symposium on Consumer Electronics, 2011.
[21]Florian Kluge, Sascha Uhrig, J¨ org Mische, Benjamin Satzger, Theo Ungerer, “Dynamic Workload Prediction for Soft Real-Time Applications”, IEEE 10th International Conference on Computer and Information Technology (CIT), 2010.
[22]Xia Zhao, Yao Guo, and Xiangqun Chen, “Transaction-Based Adaptive Dynamic Voltage Scaling for Interactive Applications”, Proceedings of the 14th ACM/IEEE international symposium on Low power electronics and design , ISLPED, 2009.
[23]D. Rajan, R. Zuck, and C. Poellabauer, “A dual speed approach to workload-aware voltage scaling,” Technical Report TR-2006-05, University of Notre Dame.