youssra
Get Complete Project Material File(s) Now! »
Chapter 2 Related Work
Significant amount of research has been done in the field of DVFS. A large number of algorithms have been designed which can be broadly classified into three categories. This classification was made by Yuan et al in [55] as follows: (i) real-time DVFS (RT-DVFS) : RT-DVFS algorithms are designed for real-time systems and aim at saving energy while maintaining hard real-time constraints. They scale the CPU frequency based on the worst case execution times of the real-time application. Most of the RT-DVFS algorithms differ in their techniques to utilize the static slack available due to the low CPU utilization of the application or dynamic slack available due to the actual execution time being much lesser than the worst case execution time of the real-time application.(ii) General Purpose DVFS (GP-DVFS) : GP-DVFS algorithms designed for general purpose systems aim at saving energy without degrading performance and are mostly suited for besteffort applications. This class of algorithms scale CPU frequency based on the workload prediction which in turn depends on the average CPU utilization. GP DVFS algorithms are based on two techniques – prediction and speed setting. Prediction involves predicting the future workload while speed setting involves deciding the speed at which to run. These are interval based schedulers where the prediction and speed setting decisions are made for every interval so as to minimise the idle time in that interval. (iii) Stastistical DVFS : Both GP-DVFS and RT-DVFS algorithms are not suited for multimedia applications as their run time demand varies. The interval based approach of GPDVFS algorithms may not satisfy the timing constraints whereas the worst case approach based RT-DVFS algorithms might not be that energy efficient. Thus, for multimedia applications, Statistical DVFS algorithms have been designed to deal with run time demand variations. The core idea of Statistical DVFS is to change the CPU speed based on the demand distributions of the applications. These algorithms involve either online or off line profiling of the applications to get the probability distribution of the cycle demand of the applications and make scheduling and frequency scaling decisions based on that.In the rest of the chapter, we will review the DVFS algorithms which have been implemented on real hardware platforms as well as on simulated platforms in the above mentioned three categories. We have an overlapping problem space with the algorithms that have been implemented in real-time, so we are going to compare and contrast only with them. But at the same time, we will also review the algorithms that have just been simulated for completeness.
GP-DVFS
The concept of DVFS was introduced by Weiser in [51]. He devised three interval based schedulers PAST, FUTURE and OPT which differ in their prediction technique. In PAST,the workload of the current interval is assumed to be same as that of the previous interval,in OPT, the exact workload is known for the entire duration and in FUTURE, the workload is known for a small interval in the future. As can be understood, OPT and FUTURE algorithms are impractical as the future workload can never be predicted. Nevertheless, this ground breaking paper led the way for the multitude of DVFS research which took place in the coming decades. They evaluated these algorithms by analysing the traces collected by running applications on UNIX based workstations. Govilet al. [23] developed a few more dynamic clock scaling algorithms with different prediction and speed-setting techniques. They developed six new algorithms, where each algorithm employ different techniques to predict the future workload. For example, in FLAT, prediction is done based on global average of the computational load, in LONG SHORT it is based on the mean of the global and local average of the workload, while in AGED AVERAGES, weighted average is considered, in CYCLE, cyclic behaviour of CPU utilization is considered, in PATTERN, prediction is done on the basis of pattern matching with a previous occurrence, whereas in PEAK, prediction is based on the expected value of the utilization,considering narrow peaks in its pattern. The speed setting policy involved reducing the frequency, when the utilization is low and the CPU is idle and increasing it, when the utilization is high and the CPU is active. They used the same traces as Weiser to evaluate their algorithms and found that PEAK performed the best.Both Weiser and Govil considered only the CPU power consumption and its linear relationship with the CPU frequency. On the contrary, Martin in [40] studied the relation between system level performance and CPU frequency scaling. He took into account non linear relation between the total system power and the CPU frequency, non ideal properties of the batteries, and the memory bandwidth to evaluate the performance of the clock scaling algorithms. He modified Weiser’s PAST algorithm taking into account the above mentioned non-ideal characteristics and evaluated the algorithm using the same traces as Weiser did.He concluded that reduction of the energy consumption is a system level problem, and all the above mentioned factors should be considered for devising a clock scaling algorithm.
1 Introduction
1.1 Limitations of Past Real-Time DVFS Research
1.2 Research Contributions
1.3 Thesis Organization
2 Related Work
2.1 GP-DVFS
2.2 RT-DVFS
2.3 Statistical DVFS
2.4 Summary
3 Algorithms
3.1 Schedulers for Independent Underloaded task-sets
3.1.1 Base-EDF
3.1.2 Static-EDF
3.1.3 CC-EDF
3.1.4 LA-EDF
3.1.5 Snowdon-min
3.1.6 DRA
3.1.7 DRA-OTE
3.1.8 AGR1
3.1.9 AGR2
3.2 Schedulers for Dependent Underloaded task-sets
3.2.1 EUA
3.2.2 HS
3.2.3 DS
3.2.4 USFI EDF
3.3 Schedulers for Overloaded task-sets
3.3.1 REUA
4 Extending ChronOS with DVFS support
4.1 ChronOS
4.1.1 Introduction
4.1.2 ChronOS real-time Scheduler
4.1.3 Scheduling Events
4.1.4 System Calls provided by ChronOS
4.2 Adding DVFS support to ChronOS
4.2.1 The CPUfreq Subsystem
4.2.2 Changing the frequency using CPUfreq module
4.2.3 Working of the CPUfreq module
4.2.4 Integration of CPUfreq subsytem with ChronOS
4.2.5 Implementation of the RT-DVFS Schedulers
4.2.6 Modification of the real-time data structure for RT-DVFS support
4.2.6.1 Additional fields for RT-DVFS support
5 Experimental Methodology
5.1 Platform Specifications
5.2 Test Application
5.2.1 Modification to the Test Application for RT-DVFS
5.3 Real-time Measurements
5.4 Power Measurements
5.4.1 Performance and Idle states of CPU
5.4.2 System Power Measurements
5.4.3 Normalized and Actual CPU power measurement
5.4.4 Calculation of Normalized CPU Energy consumption
5.4.5 Calculation of Actual CPU Power
6 Experiments
6.1 Energy consumption results on Intel I5 laptop for schedulers designed for independent task-sets
6.1.1 Varying the CPU utilization at constant ACET
6.1.2 Varying ACET at a constant CPU utilization
6.1.3 DSR results on Intel I5 laptop
6.2 Energy and DSR results for the schedulers designed for dependent task-sets
6.3 Energy consumption results on the AMD Zacate Board
6.4 System Power results on the AMD Zacate Board
6.5 Energy and DSR results for the schedulers designed for dependent task-sets .
7 Conclusions and Future Work
7.1 Conclusions
7.2 Future Work
7.2.1 DVFS in CMPs
7.2.2 Considering Real world Applications
7.2.3 DVFS with DPM
7.2.4 DVFS with Procrastination Scheduling
7.2.5 Reducing Dynamic Power Consumption of other devices
Bibliography
