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.
In this paper, the application is a task graph (directed acyclic graph), and we assume that the mapping, i.e., an ordered list of tasks to execute on each processor, is given. Hence, our problem is closely related to slack reclamation techniques, but instead on focusing on non-critical tasks as for instance in @cite_26 , we consider the problem as a whole. Our contribution is to perform an exhaustive complexity study for different energy models. In the next paragraph, we discuss related work on each energy model.
@cite_26
2028313909 2173032108 1507209274 2085836112
While much work has addressed energy-efficient scheduling for sequential tasks where each task can run on only one processor at a time, little work has been done for parallel tasks where an individual task can be executed by multiple processors simultaneously. In this paper, we develop energy minimizing algorithms for parallel task systems with timing guarantees. For parallel tasks executed by a fixed number of processors, we first propose several heuristic algorithms based on level-packing for task scheduling, and then present a polynomial-time complexity energy minimizing algorithm which is optimal for any given level-packed task schedule. For parallel tasks that can run on a variable number of processors, we propose another polynomial-time complexity algorithm to determine the number of processors executing each task, task schedule and frequency assignment. To the best of our knowledge, this is the first work that addresses energy-efficient scheduling for parallel real-time tasks. Our simulation result shows that the proposed approach can significantly reduce the system energy consumption. We study an energy conservation problem where a variable-speed processor is equipped with a sleep state. Executing jobs at high speeds and then setting the processor asleep is an approach that can lead to further energy savings compared to standard dynamic speed scaling. We consider classical deadline-based scheduling, i.e. each job is specified by a release time, a deadline and a processing volume. For general convex power functions, [12] devised an offline 2-approximation algorithm. Roughly speaking, the algorithm schedules jobs at a critical speed Scrit that yields the smallest energy consumption while jobs are processed. For power functions P(s) = sα + γ, where s is the processor speed, [11] gave an (αα + 2)-competitive online algorithm. We investigate the offline setting of speed scaling with a sleep state. First we prove NP-hardness of the optimization problem. Additionally, we develop lower bounds, for general convex power functions: No algorithm that constructs Scrit-schedules, which execute jobs at speeds of at least scrit, can achieve an approximation factor smaller than 2. Furthermore, no algorithm that minimizes the energy expended for processing jobs can attain an approximation ratio smaller than 2. We then present an algorithmic framework for designing good approximation algorithms. For general convex power functions, we derive an approximation factor of 4 3. For power functions P(s) = βsα + γ, we obtain an approximation of 137 117 < 1.171. We finally show that our framework yields the best approximation guarantees for the class of Scrit-schedules. For general convex power functions, we give another 2-approximation algorithm. For functions P(s) = βsα + γ, we present tight upper and lower bounds on the best possible approximation factor. The ratio is exactly eW−1(−e−1−1 e) (eW−1(−e−1−1 e) + 1) < 1.211, where W--1 is the lower branch of the Lambert W function. We study the unsplittable flow on a path problem (UFP), which arises naturally in many applications such as bandwidth allocation, job scheduling, and caching. Here we are given a path with nonnegative edge capacities and a set of tasks, which are characterized by a subpath, a demand, and a profit. The goal is to find the most profitable subset of tasks whose total demand does not violate the edge capacities. Not surprisingly, this problem has received a lot of attention in the research community. If the demand of each task is at most a small enough fraction δ of the capacity along its subpath (δ-small tasks), then it has been known for a long time [, ICALP 2003] how to compute a solution of value arbitrarily close to the optimum via LP rounding. However, much remains unknown for the complementary case, that is, when the demand of each task is at least some fraction δ > 0 of the smallest capacity of its subpath (δ-large tasks). For this setting a constant factor approximation, improving on an earlier logarithmic approximation, was found only recently [, FOCS 2011]. In this paper we present a PTAS for δ-large tasks, for any constant δ > 0. Key to this result is a complex geometrically inspired dynamic program. Each task is represented as a segment underneath the capacity curve, and we identify a proper maze-like structure so that each corridor of the maze is crossed by only O(1) tasks in the optimal solution. The maze has a tree topology, which guides our dynamic program. Our result implies a 2 + e approximation for UFP, for any constant e > 0, improving on the previously best 7 + e approximation by We remark that our improved approximation algorithm matches the best known approximation ratio for the considerably easier special case of uniform edge capacities. We consider the problem of speed scaling to conserve energy in a multiprocessor setting where there are precedence constraints between tasks, and where the performance measure is the makespan. That is, we consider an energy bounded version of the classic problem Pm|prec|Cmax . We extend the standard 3-field notation and denote this problem as Sm|prec, energy|Cmax . We show that, without loss of generality, one need only consider constant power schedules. We then show how to reduce this problem to the problem Qm|prec|Cmax to obtain a poly-log(m)-approximation algorithm.