We consider a task graph to be executed on a set of processors. We assume that the mapping is given, say by an ordered list of tasks to execute on each processor, and we aim at optimizing the energy consumption while enforcing a prescribed bound on the execution time. While it is not possible to change the allocation of a task, it is possible to change its speed. Rather than using a local approach such as backfilling, we consider the problem as a whole and study the impact of several speed variation models on its complexity. For continuous speeds, we give a closed-form formula for trees and series-parallel graphs, and we cast the problem into a geometric programming problem for general directed acyclic graphs. We show that the classical dynamic voltage and frequency scaling (DVFS) model with discrete modes leads to a NP-complete problem, even if the modes are regularly distributed (an important particular case in practice, which we analyze as the incremental model). On the contrary, the VDD-hopping model leads to a polynomial solution. Finally, we provide an approximation algorithm for the incremental model, which we extend for the general DVFS model.
Reducing the energy consumption of computational platforms is an important research topic, and many techniques at the process, circuit design, and micro-architectural levels have been proposed @cite_11 @cite_14 @cite_31 . The dynamic voltage and frequency scaling (DVFS) technique has been extensively studied, since it may lead to efficient energy performance trade-offs @cite_8 @cite_13 @cite_27 @cite_9 @cite_28 @cite_0 @cite_26 . Current microprocessors (for instance, from AMD @cite_18 and Intel @cite_29 ) allow the speed to be set dynamically. Indeed, by lowering supply voltage, hence processor clock frequency, it is possible to achieve important reductions in power consumption, without necessarily increasing the execution time. We first discuss different optimization problems that arise in this context. Then we review energy models.
@cite_18 @cite_14 @cite_26 @cite_8 @cite_28 @cite_9 @cite_29 @cite_0 @cite_27 @cite_31 @cite_13 @cite_11
1894651528 2133039052 2008093830 2095504329
Dynamic voltage and frequency scaling (DVFS) is a commonly-used power-management technique where the clock frequency of a processor is decreased to allow a corresponding reduction in the supply voltage. This reduces power consumption, which can lead to significant reduction in the energy required for a computation, particularly for memory-bound workloads. However, recent developments in processor and memory technology have resulted in the saturation of processor clock frequencies, larger static power consumption, smaller dynamic power range and better idle sleep modes. Each of these developments limit the potential energy savings resulting from DVFS. We analyse this trend by examining the potential of DVFS across three platforms with recent generations of AMD processors. We find that while DVFS is effective on the older platforms, it actually increases energy usage on the most recent platform, even for highly memory-bound workloads. When peak performance is unnecessary, Dynamic Voltage Scaling (DVS) can be used to reduce the dynamic power consumption of embedded multiprocessors. In future technologies, however, static power consumption due to leakage current is expected to increase significantly. Then it will be more effective to limit the number of processors employed (i.e., turn some of them off), or to use a combination of DVS and processor shutdown. In this paper, leakage-aware scheduling heuristics are presented that determine the best trade-off between these three techniques: DVS, processor shutdown, and finding the optimal number of processors. Experimental results obtained using a public benchmark set of task graphs and real parallel applications show that our approach reduces the total energy consumption by up to 46 for tight deadlines (1.5× the critical path length) and by up to 73 for loose deadlines (8× the critical path length) compared to an approach that only employs DVS. We also compare the energy consumed by our scheduling algorithms to two absolute lower bounds, one for the case where all processors continuously run at the same frequency, and one for the case where the processors can run at different frequencies and these frequencies may change over time. The results show that the energy reduction achieved by our best approach is close to these theoretical limits. Dynamic voltage and frequency scaling (DVFS) has been widely used for energy reduction in the modern processors. How to select the optimal frequency that minimizes energy dissipation for the given performance constraint at runtime is a nontrivial problem. The problem becomes more complicated if temperature needs to be constrained (or minimized) simultaneously. The temperature, performance and energy have different nonlinear relationships with frequency voltage scaling ratio and this relationship is closely related to the characteristics of hardware and applications. In this paper, we design a reinforcement learning algorithm to tackle the problem of simultaneous temperature, performance and energy management. The proposed approach allows continuous tradeoff among these three quality measurement of a computer system. It also enables us to set two of the measurements as constraints and optimize the third one. The proposed approach is validated on an Intel Core 2 processor running Linux system. Applying classical dynamic voltage scaling (DVS) techniques to real-time systems running on processors with discrete voltage frequency modes causes a waste of computational resources. In fact, whenever the ideal speed level computed by the DVS algorithm is not available in the system, to guarantee the feasibility of the task set, the processor speed must be set to the nearest level greater than the optimal one, thus underutilizing the system. Whenever the task set allows a certain degree of flexibility in specifying timing constraints, rate adaptation techniques can be adopted to balance performance (which is a function of task rates) versus energy consumption (which is a function of the processor speed). In this paper, we propose a new method that combines discrete DVS management with elastic scheduling to fully exploit the available computational resources. Depending on the application requirements, the algorithm can be set to improve performance or reduce energy consumption, so enhancing the flexibility of the system. A reclaiming mechanism is also used to take advantage of early completions. To make the proposed approach usable in real-world applications, the task model is enhanced to consider some of the real CPU characteristics, such as discrete voltage frequency levels, switching overhead, task execution times nonlinear with the frequency, and tasks with different power consumption. Implementation issues and experimental results for the proposed algorithm are also discussed