Keywords: Modèles énergétiques, complexité, optimisation bi-critère, algorithmes, ordonnancement

Minimisation de l'énergie d'un ordonnancement: modèles et algorithmes Résumé : Considérons un graphe de tâches devant être exécutées sur un ensemble de processeurs. Supposons l'ordonnancement déjà donné, par exemple on peut imaginer une liste de tâches devant être exécutées sur chaque processeur. Notre but est de minimiser la consommation d'énergie, sans dépasser une limite de temps. Alors qu'il n'est pas possible de changer le processeur qui va calculer une tâche, il est possible de changer la vitesse de calcul de ce processeur sur cette tâche. Plutôt que de considérer une approche locale qui consisterait à boucher les trous, nous considérons le problème de manière globale et étudions l'impact sur la complexité du problème de quatre modèles de variation de vitesse. Dans le modèle où toutes les vitesses réelles sont disponibles (vitesses continues), nous donnnons une formule close pour les arbres et les graphes série-parallèle, puis nous transformons le problème en un problème de programmation géométrique dans le cas général des graphes acycliques dirigés. Nous montrons que les modèles classiques de variation de vitesse avec des modes discrets rendent ce problème NP-complet, même si les modes sont distribués de manière régulière (un cas très important en pratique que nous analysons sous le nom de modèle incrémental). Au contraire, le modèle de VDD-hopping est un problème ayant une solution polynomiale. Pour finir, nous donnons un algorithme d'approximation pour le modèle incrémental, que nous étendons au cas général de variation de vitesses à modes discrets.

Introduction

The energy consumption of computational platforms has recently become a critical problem, both for economic and environmental reasons [START_REF] Mills | The internet begins with coal[END_REF]. As an example, the Earth Simulator requires about 12 MW (Mega Watts) of peak power, and PetaFlop systems may require 100 MW of power, nearly the output of a small power plant (300 MW). At $100 per MW.Hour, peak operation of a PetaFlop machine may thus cost $10,000 per hour [START_REF] Ge | Performance-constrained distributed DVS scheduling for scientific applications on power-aware clusters[END_REF]. Current estimates state that cooling costs $1 to $3 per watt of heat dissipated [START_REF] Skadron | Temperature-aware microarchitecture: modeling and implementation[END_REF]. This is just one of the many economical reasons why energy-aware scheduling has proved to be an important issue in the past decade, even without considering battery-powered systems such as laptops and embedded systems. As an example, the Green500 list (www.green500.org) provides rankings of the most energy-efficient supercomputers in the world, therefore raising even more awareness about power consumption.

To help reduce energy dissipation, processors can run at different speeds. Their power consumption is the sum of a static part (the cost for a processor to be turned on) and a dynamic part, which is a strictly convex function of the processor speed, so that the execution of a given amount of work costs more power if a processor runs in a higher mode [START_REF] Hotta | Profile-based optimization of power performance by using dynamic voltage scaling on a pc cluster[END_REF]. More precisely, a processor running at speed s dissipates s 3 watts [START_REF] Ishihara | Voltage scheduling problem for dynamically variable voltage processors[END_REF][START_REF] Pruhs | Speed scaling of tasks with precedence constraints[END_REF][START_REF] Chandrakasan | JouleTrack: A Web Based Tool for Software Energy Profiling[END_REF][START_REF] Aydin | Energy-aware partitioning for multiprocessor real-time systems[END_REF][START_REF] Chen | Multiprocessor energy-efficient scheduling for real-time tasks[END_REF] per time-unit, hence consumes s 3 × d joules when operated during d units of time. Faster speeds allow for a faster execution, but they also lead to a much higher (supra-linear) power consumption.

Energy-aware scheduling aims at minimizing the energy consumed during the execution of the target application. Obviously, it makes sense only if it is coupled with some performance bound to achieve, otherwise, the optimal solution always is to run each processor at the slowest possible speed.

In this paper, we investigate energy-aware scheduling strategies for executing a task graph on a set of processors. The main originality is that we assume that the mapping of the task graph is given, say by an ordered list of tasks to execute on each processor. There are many situations in which this problem is important, such as optimizing for legacy applications, or accounting for affinities between tasks and resources, or even when tasks are pre-allocated [START_REF] Rayward-Smith | Scheduling parallel programs assuming preallocation[END_REF], for example for security reasons. In such situations, assume that a list-schedule has been computed for the task graph, and that its execution time should not exceed a deadline D. We do not have the freedom to change the assignment of a given task, but we can change its speed to reduce energy consumption, provided that the deadline D is not exceeded after the speed change. Rather than using a local approach such as backfilling [START_REF] Wang | Towards Energy Aware Scheduling for Precedence Constrained Parallel Tasks in a Cluster with DVFS[END_REF][START_REF] Prathipati | Energy efficient scheduling techniques for real-time embedded systems[END_REF], which only reclaims gaps in the schedule, we consider the problem as a whole, and we assess the impact of several speed variation models on its complexity. More precisely, we investigate the following models: Continuous model. Processors can have arbitrary speeds, and can vary them continuously: this model is unrealistic (any possible value of the speed, say √ e π , cannot be obtained) but it is theoretically appealing [START_REF] Bansal | Speed scaling to manage energy and temperature[END_REF]. A maximum speed, s max , cannot be exceeded.

Discrete model. Processors have a discrete number of predefined speeds (or frequencies), which correspond to different voltages that the processor can be subjected to [START_REF] Okuma | Software energy reduction techniques for variablevoltage processors[END_REF]. Switching frequencies is not allowed during the execution of a given task, but two different tasks scheduled on a same processor can be executed at different frequencies.

Vdd-Hopping model. This model is similar to the Discrete one, except that switching modes during the execution of a given task is allowed: any rational speed can be simulated, by simply switching, at the appropriate time during the execution of a task, between two consecutive modes [START_REF] Miermont | A Power Supply Selector for Energy-and Area-Efficient Local Dynamic Voltage Scaling[END_REF].

Incremental model. In this variant of the Discrete model, we introduce a value δ that corresponds the minimum permissible speed increment, induced by the minimum voltage increment that can be achieved when controlling the processor CPU. This new model aims at capturing a realistic version of the Discrete model, where the different modes are spread regularly instead of arbitrarily chosen.

Our main contributions are the following. For the Continuous model, we give a closed-form formula for trees and series-parallel graphs, and we cast the problem into a geometric programming problem [START_REF] Boyd | Convex Optimization[END_REF] for general DAGs. For the Vdd-Hopping model, we show that the optimal solution for general DAGs can be computed in polynomial time, using a (rational) linear program. Finally, for the Discrete and Incremental models, we show that the problem is NP-complete. Furthermore, we provide approximation algorithms which rely on the polynomial algorithm for the Vdd-Hopping model, and we compare their solution with the optimal Continuous solution.

The paper is organized as follows. We start with a survey of related literature in Section 2. We then provide the formal description of the framework and of the energy models in Section 3, together with a simple example to illustrate the different models. The next two sections constitute the heart of the paper: in Section 4, we provide analytical formulas for continuous speeds, and the formulation into the convex optimization problem. In Section 5, we assess the complexity of the problem with all the discrete models: Discrete, Vdd-Hopping and Incremental, and we discuss approximation algorithms. Finally we conclude in Section 6.

Related work

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 [START_REF] Lee | Run-time voltage hopping for low-power real-time systems[END_REF][START_REF] Lahiri | Battery-driven system design: a new frontier in low power design[END_REF][START_REF] Grosse | Methods for power optimization in SOC-based data flow systems[END_REF]. The dynamic voltage and frequency scaling (DVFS) technique has been extensively studied, since it may lead to efficient energy/performance trade-offs [START_REF] Jejurikar | Leakage aware dynamic voltage scaling for realtime embedded systems[END_REF][START_REF] Ge | Performance-constrained distributed DVS scheduling for scientific applications on power-aware clusters[END_REF][START_REF] Bansal | Speed scaling to manage energy and temperature[END_REF][START_REF] Chen | Energy-Efficient Scheduling for Real-Time Systems on Dynamic Voltage Scaling (DVS) Platforms[END_REF][START_REF] Kim | Power Aware Scheduling of Bag-of-Tasks Applications with Deadline Constraints on DVS-enabled Clusters[END_REF][START_REF] Yang | On-Line and Off-Line DVS for Fixed Priority with Preemption Threshold Scheduling[END_REF][START_REF] Wang | Towards Energy Aware Scheduling for Precedence Constrained Parallel Tasks in a Cluster with DVFS[END_REF]. Current microprocessors (for instance, from AMD [START_REF]AMD processors[END_REF] and Intel [START_REF]Intel XScale technology[END_REF]) 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.

DVFS and optimization problems

When dealing with energy consumption, the most usual optimization function consists in minimizing the energy consumption, while ensuring a deadline on the execution time (i.e., a real-time constraint), as discussed in the following papers.

In [START_REF] Okuma | Software energy reduction techniques for variablevoltage processors[END_REF], Okuma et al. demonstrate that voltage scaling is far more effective than the shutdown approach, which simply stops the power supply when the system is inactive. Their target processor employs just a few discretely variable voltages. De Langen and Juurlink [START_REF] Langen | Leakage-aware multiprocessor scheduling[END_REF] discuss leakageaware scheduling heuristics which investigate both DVS and processor shutdown, since static power consumption due to leakage current is expected to increase significantly. Chen et al. [START_REF] Chen | Reducing power with performance constraints for parallel sparse applications[END_REF] consider parallel sparse applications, and they show that when scheduling applications modeled by a directed acyclic graph with a well-identified critical path, it is possible to lower the voltage during non-critical execution of tasks, with no impact on the execution time. Similarly, Wang et al. [START_REF] Wang | Towards Energy Aware Scheduling for Precedence Constrained Parallel Tasks in a Cluster with DVFS[END_REF] study the slack time for non-critical jobs, they extend their execution time and thus reduce the energy consumption without increasing the total execution time. Kim et al. [START_REF] Kim | Power Aware Scheduling of Bag-of-Tasks Applications with Deadline Constraints on DVS-enabled Clusters[END_REF] provide power-aware scheduling algorithms for bag-of-tasks applications with deadline constraints, based on dynamic voltage scaling. Their goal is to minimize power consumption as well as to meet the deadlines specified by application users.

For real-time embedded systems, slack reclamation techniques are used. Lee and Sakurai [START_REF] Lee | Run-time voltage hopping for low-power real-time systems[END_REF] show how to exploit slack time arising from workload variation, thanks to a software feedback control of supply voltage. Prathipati [START_REF] Prathipati | Energy efficient scheduling techniques for real-time embedded systems[END_REF] discusses techniques to take advantage of run-time variations in the execution time of tasks; it determines the minimum voltage under which each task can be executed, while guaranteeing the deadlines of each task. Then, experiments are conducted on the Intel StrongArm SA-1100 processor, which has eleven different frequencies, and the Intel PXA250 XScale embedded processor with four frequencies. In [START_REF] Xu | Minimizing expected energy consumption in real-time systems through dynamic voltage scaling[END_REF], the goal of Xu et al. is to schedule a set of independent tasks, given a worst case execution cycle (WCEC) for each task, and a global deadline, while accounting for time and energy penalties when the processor frequency is changing. The frequency of the processor can be lowered when some slack is obtained dynamically, typically when a task runs faster than its WCEC. Yang and Lin [START_REF] Yang | On-Line and Off-Line DVS for Fixed Priority with Preemption Threshold Scheduling[END_REF] discuss algorithms with preemption, using DVS techniques; substantial energy can be saved using these algorithms, which succeed to claim the static and dynamic slack time, with little overhead.

Since an increasing number of systems are powered by batteries, maximizing battery life also is an important optimization problem. Battery-efficient systems can be obtained with similar techniques of dynamic voltage and frequency scaling, as described by Lahiri et al. in [START_REF] Lahiri | Battery-driven system design: a new frontier in low power design[END_REF]. Another optimization criterion is the energy-delay product, since it accounts for a trade-off between performance and energy consumption, as for instance discussed by Gonzalez and Horowitz in [START_REF] Gonzalez | Energy dissipation in general purpose microprocessors[END_REF]. We do not discuss further these latter optimization problems, since our goal is to minimize the energy consumption, with a fixed deadline.

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 [START_REF] Wang | Towards Energy Aware Scheduling for Precedence Constrained Parallel Tasks in a Cluster with DVFS[END_REF], 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.

Energy models

Several energy models are considered in the literature, and they can all be categorized in one of the four models investigated in this paper, i.e., Continuous, Discrete, Vdd-Hopping or Incremental.

The Continuous model is used mainly for theoretical studies. For instance, Yao et al. [START_REF] Yao | A scheduling model for reduced CPU energy[END_REF], followed by Bansal et al. [START_REF] Bansal | Speed scaling to manage energy and temperature[END_REF], aim at scheduling a collection of tasks (with release time, deadline and amount of work), and the solution is the time at which each task is scheduled, but also, the speed at which the task is executed. In these papers, the speed can take any value, hence following the Continuous model.

We believe that the most widely used model is the Discrete one. Indeed, processors have currently only a few discrete number of possible frequencies [START_REF]AMD processors[END_REF][START_REF]Intel XScale technology[END_REF][START_REF] Okuma | Software energy reduction techniques for variablevoltage processors[END_REF][START_REF] Prathipati | Energy efficient scheduling techniques for real-time embedded systems[END_REF]. Therefore, most of the papers discussed above follow this model. Some studies exploit the continuous model to determine the smallest frequency required to run a task, and then choose the closest upper discrete value, as for instance [START_REF] Prathipati | Energy efficient scheduling techniques for real-time embedded systems[END_REF] and [START_REF] Zhang | Task scheduling and voltage selection for energy minimization[END_REF].

Recently, a new local dynamic voltage scaling architecture has been developed, based on the Vdd-Hopping model [START_REF] Miermont | A Power Supply Selector for Energy-and Area-Efficient Local Dynamic Voltage Scaling[END_REF][START_REF] Beigne | An asynchronous power aware and adaptive NoC based circuit[END_REF][START_REF] Beigne | A Localized Power Control mixing hopping and Super Cut-Off techniques within a GALS NoC[END_REF]. It was shown in [START_REF] Lee | Run-time voltage hopping for low-power real-time systems[END_REF] that significant power can be saved by using two distinct voltages, and architectures using this principle have been developed (see for instance [START_REF] Kawaguchi | An LSI for VDD-Hopping and MPEG4 System Based on the Chip[END_REF]). Compared to traditional power converters, a new design with no needs for large passives or costly technological options has been validated in a STMicroelectronics CMOS 65nm low-power technology [START_REF] Miermont | A Power Supply Selector for Energy-and Area-Efficient Local Dynamic Voltage Scaling[END_REF].

To the best of our knowledge, this paper introduces the Incremental model for the first time. The main rationale is that future technologies may well have an increased number of possible frequencies, and these will follow a regular pattern. For instance, note that the SA-1100 processor, considered in [START_REF] Prathipati | Energy efficient scheduling techniques for real-time embedded systems[END_REF], has eleven frequencies which are equidistant, i.e., they follow the Incremental model. Lee and Sakurai [START_REF] Lee | Run-time voltage hopping for low-power real-time systems[END_REF] exploit discrete levels of clock frequency as f , f /2, f /3, ..., where f is the master (i.e., the higher) system clock frequency. This model is closer to the Discrete model, although it exhibits a regular pattern similarly to the Incremental model.

Our work is the first attempt to compare these different models: on the one hand, we assess the impact of the model on the problem complexity (polynomial vs NP-hard), and on the other hand, we provide approximation algorithms building upon these results. The closest work to ours is the paper by Zhang et al. [START_REF] Zhang | Task scheduling and voltage selection for energy minimization[END_REF], in which the authors also consider the mapping of directed acyclic graphs, and compare the Discrete and the Continuous models. We go beyond their work in this paper, with an exhaustive complexity study, closed-form formulas for the continuous model, and the comparison with the Vdd-Hopping and Incremental models.

Framework

First we detail the optimization problem in Section 3.1. Then we describe the four energy models in Section 3.2. Finally, we illustrate the models and motivate the problem with an example in Section 3.3.

Optimization problem

Consider an application task graph G = (V, E), with n = |V | tasks denoted as V = {T 1 , T 2 , . . . , T n }, and where the set E denotes the precedence edges between tasks. Task T i has a cost w i for 1 ≤ i ≤ n. We assume that the tasks in G have been allocated onto a parallel platform made up of identical processors. We define the execution graph generated by this allocation as the graph G = (V, E), with the following augmented set of edges:

• E ⊆ E: if an edge exists in the precedence graph, it also exists in the execution graph;

• if T 1 and T 2 are executed successively, in this order, on the same processor, then (T 1 , T 2 ) ∈ E.

The goal is to the minimize the energy consumed during the execution while enforcing a deadline D on the execution time. We formalize the optimization problem in the simpler case where each task is executed at constant speed. This strategy is optimal for the Continuous model (by a convexity argument) and for the Discrete and Incremental models (by definition). For the Vdd-Hopping model, we reformulate the problem in Section 5.1. Let d i be the duration of the execution of task T i , t i its completion time, and s i the speed at which it is executed. We obtain the following formulation of the MinEnergy(G, D) problem, given an execution graph G = (V, E) and a deadline D; the s i values are variables, whose values are constrained by the energy model (see Section 3.2).

Minimize

n i=1 s 3 i × d i subject to (i) w i = s i × d i for each task T i ∈ V (ii) t i + d j ≤ t j for each edge (T i , T j ) ∈ E (iii) t i ≤ D for each task T i ∈ V (1)
Constraint (i) states that the whole task can be executed in time d i using speed s i . Constraint (ii) accounts for all dependencies, and constraint (iii) ensures that the execution time does not exceed the deadline D. The energy consumed throughout the execution is the objective function. It is the sum, for each task, of the energy consumed by this task, as we detail in the next section. Note that d i = w i /s i , and therefore the objective function can also be expressed as

n i=1 s 2 i × w i .

Energy models

In all models, when a processor operates at speed s during d time-units, the corresponding consumed energy is s 3 ×d, which is the dynamic part of the energy consumption, following the classical models of the literature [START_REF] Ishihara | Voltage scheduling problem for dynamically variable voltage processors[END_REF][START_REF] Pruhs | Speed scaling of tasks with precedence constraints[END_REF][START_REF] Chandrakasan | JouleTrack: A Web Based Tool for Software Energy Profiling[END_REF][START_REF] Aydin | Energy-aware partitioning for multiprocessor real-time systems[END_REF][START_REF] Chen | Multiprocessor energy-efficient scheduling for real-time tasks[END_REF]. Note that we do not take static energy into account, because all processors are up and alive during the whole execution. We now detail the possible speed values in each energy model, which should be added as a constraint in Equation ( 1).

• In the Continuous model, processors can have arbitrary speeds, from 0 to a maximum value s max , and a processor can change its speed at any time during execution. • In the Discrete model, processors have a set of possible speed values, or modes, denoted as s 1 , ..., s m . There is no assumption on the range and distribution of these modes. The speed of a processor cannot change during the computation of a task, but it can change from task to task. • In the Vdd-Hopping model, a processor can run at different speeds s 1 , ..., s m , as in the previous model, but it can also change its speed during a computation. The energy consumed during the execution of one task is the sum, on each time interval with constant speed s, of the energy consumed during this interval at speed s. • In the Incremental model, we introduce a value δ that corresponds to the minimum permissible speed (i.e., voltage) increment. That means that possible speed values are obtained as s = s min + i × δ, where i is an integer such that 0 ≤ i ≤ smax -smin δ . Admissible speeds lie in the interval [s min , s max ]. This new model aims at capturing a realistic version of the Discrete model, where the different modes are spread regularly between s 1 = s min and s m = s max , instead of being arbitrarily chosen. It is intended as the modern counterpart of a potentiometer knob!

Example

Consider an application with four tasks of costs w 1 = 3, w 2 = 2, w 3 = 1 and w 4 = 2, and one precedence constraint T 1 → T 3 . We assume that T 1 and T 2 are allocated, in this order, onto processor P 1 , while T 3 and T 4 are allocated, in this order, on processor P 2 . The resulting execution graph G is given in Figure 1, with two precedence constraints added to the initial task graph. The deadline on the execution time is D = 1.5.

We set the maximum speed to s max = 6 for the Continuous model. For the Discrete and Vdd-Hopping models, we use the set of speeds s

(d) 1 = 2, s (d) 2 = 5 and s (d) 3 = 6.
Finally, for the Incremental model, we set δ = 2, s min = 2 and s max = 6, so that possible speeds are s

(i) 1 = 2, s (i)
2 = 4 and s (i) 3 = 6. We aim at finding the optimal execution speed s i for each task T i (1 ≤ i ≤ 4), i.e., the values of s i which minimize the energy consumption.

With the Continuous model, the optimal speeds are non rational values, and we obtain

s 1 = 2 3 (3 + 35 1/3 ) ≃ 4.18; s 2 = s 1 × 2 35 1/3 ≃ 2.56; s 3 = s 4 = s 1 × 3 35 1/3 ≃ 3.83.
Note that all speeds are lower than the maximum s max . These values are obtained thanks to the formulas derived in Section 4. The energy consumption is then , and with this solution, it is equal to the deadline D (actually, both processors reach the deadline, otherwise we could slow down the execution of one task).

E (c) opt = 4 i=1 w i × s 2 i = 3.
For the Discrete model, if we execute all tasks at speed s = 5, which turns out to be optimal:

E (d) opt = 3 × 36 + (2 + 1) × 4 + 2 × 25 = 170. Note that E (d) opt > E (c)
opt , i.e., the optimal energy consumption with the Discrete model is much higher than the one achieved with the Continuous model. Indeed, in this case, even though the first processor executes during 3/6 + 2/2 = D time units, the second processor remains idle since 3/6 + 1/2 + 2/5 = 1.4 < D. The problem turns out to be NP-hard (see Section 5.2), and the solution has been found by performing an exhaustive search.

With the Vdd-Hopping model, we set s 1 = s 2 during time 1/5 (i.e., the second processor executes during time 3/5 + 1/5 + 0.5 + 1/5 = 1.5 = D, and all the work for T 4 is done: 2 × 0.5 + 5 × 1/5 = 2 = w 4 ). This set of speeds turns out to be optimal (i.e., it is the optimal solution of the linear program introduced in Section 5.1), with an energy consumption

E (v) opt = (3/5 + 2/30 + 1/5 + 1/5) × 5 3 + (5/6 + 0.5) × 2 3 = 144. As expected, E (c) opt ≤ E (v) opt ≤ E (d)
opt , i.e., the Vdd-Hopping solution stands between the optimal Continuous solution, and the more constrained Discrete solution.

For the Incremental model, the reasoning is similar to the Discrete case, and the optimal solution is obtained by an exhaustive search: all tasks should be executed at speed s

(i) 2 = 4, with an energy consumption E (i) opt = 8 × 4 2 = 128 > E (c)
opt . It turns out to be better than Discrete and Vdd-Hopping, since it has different discrete values of energy which are more appropriate for this example.

The Continuous model

With the Continuous model, processor speeds can take any value between 0 and s max . First we prove that, with this model, the processors do not change their speed during the execution of a task (Section 4.1). Then, we derive in Section 4.2 the optimal speed values for special execution graph structures, expressed as closed form algebraic formulas, and we show that these values may be irrational (as already illustrated in the example in Section 3.3). Finally, we formulate the problem for general DAGs as a convex optimization program in Section 4.3.

Preliminary lemma

Lemma 1 (constant speed per task) With the Continuous model, each task is executed at constant speed, i.e., a processor does not change its speed during the execution of a task.

Proof. Suppose that in the optimal solution, there is a task whose speed changes during the execution. Consider the first time-step at which the change occurs: the computation begins at speed s from time t to time t ′ , and then continues at speed s ′ until time t ′′ . The total energy consumption for this task in the time interval [t;

t ′′ ] is E = (t ′ -t) × s 3 + (t ′′ -t ′ ) × (s ′ ) 3 . Moreover, the amount of work done for this task is W = (t ′ -t) × s + (t ′′ -t ′ ) × s ′ .
If we run the task during the whole interval [t; t ′′ ] at constant speed W/(t ′′t), the same amount of work is done within the same time. However, the energy consumption during this interval of time is now E ′ = (t ′′t) × (W/(t ′′t)) 3 . By convexity of the function x → x 3 , we obtain E ′ < E since t < t ′ < t ′′ . This contradicts the hypothesis of optimality of the first solution, which concludes the proof. ⊓ ⊔

Special execution graphs

Independent tasks

Consider the problem of minimizing the energy of n independent tasks (i.e., each task is mapped onto a distinct processor, and there are no precedence constraints in the execution graph), while enforcing a deadline D.

Proposition 1 (independent tasks) When G is composed of independent tasks {T 1 , . . . , T n }, the optimal solution to MinEnergy(G, D) is obtained when each task

T i (1 ≤ i ≤ n) is computed at speed s i = wi D .
If there is a task T i such that s i > s max , then the problem has no solution. Proof. For task T i , the speed s i corresponds to the slowest speed at which the processor can execute the task, so that the deadline is not exceeded. If s i > s max , the corresponding processor will never be able to complete its execution before the deadline, therefore there is no solution. To conclude the proof, we note that any other solution would have higher values of s i because of the deadline constraint, and hence a higher energy consumption. Therefore, this solution is optimal.

⊓ ⊔

Linear chain of tasks

This case corresponds for instance to n independent tasks {T 1 , . . . , T n } executed onto a single processor. The execution graph is then a linear chain (order of execution of the tasks), with

T i → T i+1 , for 1 ≤ i < n.

Proposition 2 (linear chain)

When G is a linear chain of tasks, the optimal solution to MinEnergy(G, D) is obtained when each task is executed at speed s = W D , with W = n i=1 w i . If s > s max , then there is no solution.

Proof. Suppose that in the optimal solution, tasks T i and T j are such that s i < s j . The total energy consumption is E opt . We define s such that the execution of both tasks running at speed s takes the same amount of time than in the optimal solution, i.e., (w i + w j )/s = w i /s i + w j /s j : s = (wi+wj ) wisj +wj si × s i s j . Note that s i < s < s j (it is the barycenter of two points with positive mass). We consider a solution such that the speed of task T k , for 1 ≤ k ≤ n, with k = i and k = j, is the same as in the optimal solution, and the speed of tasks T i and T j is s. By definition of s, the execution time has not been modified. The energy consumption of this solution is E, where

E opt -E = w i s 2 i + w j s 2 j -(w i + w j )s 2 , i.e.
, the difference of energy with the optimal solution is only impacted by tasks T i and T j , for which the speed has been modified. By convexity of the function x → x 2 , we obtain E opt > E, which contradicts its optimality. Therefore, in the optimal solution, all tasks have the same execution speed. Moreover, the energy consumption is minimized when the speed is as low as possible, while the deadline is not exceeded. Therefore, the execution speed of all tasks is s = W/D.

⊓ ⊔

Corollary 1 A linear chain with n tasks is equivalent to a single task of cost W = n i=1 w i .

Indeed, in the optimal solution, the n tasks are executed at the same speed, and they can be replaced by a single task of cost W , which is executed at the same speed and consumes the same amount of energy.

Fork and join graphs

Let V = {T 1 , . . . , T n }. We consider either a fork graph

G = (V ∪ {T 0 }, E), with E = {(T 0 , T i ), T i ∈ V }, or a join graph G = (V ∪ {T 0 }, E), with E = {(T i , T 0 ), T i ∈ V }.
T 0 is either the source of the fork or the sink of the join.

Theorem 1 (fork and join graphs) When G is a fork (resp. join) execution graph with n + 1 tasks T 0 , T 1 , . . . , T n , the optimal solution to MinEnergy(G, D) is the following:

• the execution speed of the source (resp. sink)

T 0 is s 0 = n i=1 w 3 i 1 3 + w 0 D ;
• for the other tasks T i , 1 ≤ i ≤ n, we have

s i = s 0 × w i ( n i=1 w 3 i ) 1 3 if s 0 ≤ s max .
Otherwise, T 0 should be executed at speed s 0 = s max , and the other speeds are s i = wi D ′ , with D ′ = D -w0 smax , if they do not exceed s max (Proposition 1 for independent tasks). Otherwise there is no solution.

If no speed exceeds s max , the corresponding energy consumption is

minE(G, D) = ( n i=1 w 3 i ) 1 3 + w 0 3 D 2 .
Proof. Let t 0 = w0 s0 . Then, the source or the sink requires a time t 0 for execution. For 1 ≤ i ≤ n, task T i must be executed within a time Dt 0 so that the deadline is respected. Given t 0 , we can compute the speed s i for task T i using Theorem 1, since the tasks are independent:

s i = wi D-t0 = w i • s0 s0D-w0
. The objective is therefore to minimize n i=0 w i s 2 i , which is a function of s 0 :

n i=0 w i s 2 i = w 0 s 2 0 + n i=1 w 3 i • s 2 0 (s 0 D -w 0 ) 2 = s 2 0 w 0 + n i=1 w 3 i (s 0 D -w 0 ) 2 = f (s 0 ). Let W 3 = n i=1 w 3 i .
In order to find the value of s 0 which minimizes this function, we study the function f (x), for x > 0.

f ′ (x) = 2x w 0 + W3 (xD-w0) 2 -2D • x 2 • W3 (xD-w0) 3 , and therefore f ′ (x) = 0 for x = (W 1 3
3 + w 0 )/D. We conclude that the optimal speed for task T 0 is s

0 = ( n i=1 w 3 i ) 1 3 +w0 D , if s 0 ≤ s max .
Otherwise, T 0 should be executed at the maximum speed s 0 = s max , since it is the bottleneck task. In any case, for 1 ≤ i ≤ n, the optimal speed for task T i is s i = w i s0 s0D-w0 . Finally, we compute the exact expression of minE(G, D) = f (s 0 ), when s 0 ≤ s max :

f (s 0 ) = s 2 0 w 0 + W 3 (s 0 D -w 0 ) 2 = W 1 3 3 + w 0 D 2 W 3 W 2/3 3 + w 0 = W 1 3 3 + w 0 3 D 2 ,
which concludes the proof. ⊓ ⊔ Corollary 2 (equivalent tasks for speed) Consider a fork or join graph with tasks T i , 0 ≤ i ≤ n, and a deadline D, and assume that the speeds in the optimal solution to MinEnergy(G, D) do not exceed s max . Then, these speeds are the same as in the optimal solution for n + 1 independent tasks T ′ 0 , T ′ 1 , . . . , T ′ n , where w ′ 0 = n i=1 w 3 i 1 3 + w 0 , and, for

1 ≤ i ≤ n, w ′ i = w ′ 0 • wi ( n i=1 w 3 i ) 1 3
.

Corollary 3 (equivalent task for energy) Consider a fork or join graph G and a deadline D, and assume that the speeds in the optimal solution to MinEnergy(G, D) do not exceed s max . We say that the graph G is equivalent to the graph G (eq) , consisting of a single task T + w 0 , because the minimum energy consumption of both graphs are identical: minE(G, D)=minE(G (eq) , D).

Trees

We extend the results on a fork graph for a tree G = (V, E) with |V | = n + 1 tasks. Let T 0 be the root of the tree; it has k children tasks, which are each themselves the root of a tree. A tree can therefore be seen as a fork graph, where the tasks of the fork are trees.

The previous results for fork graphs naturally lead to an algorithm that peels off branches of the tree, starting with the leaves, and replaces each fork subgraph in the tree, composed of a root T 0 and k children, by one task (as in Corollary 3) which becomes the unique child of T 0 's parent in the tree. We say that this task is equivalent to the fork graph, since the optimal energy consumption will be the same. The computation of the equivalent cost of this task is done thanks to a call to the eq procedure, while the tree procedure computes the solution to MinEnergy(G, D) (see Algorithm 1). Note that the algorithm computes the minimum energy for a tree, but it does not return the speeds at which each task must be executed. However, the algorithm returns the speed of the root task, and it is then straightforward to compute the speed of each children of the root task, and so on.

Theorem 2 (tree graphs) When G is a tree rooted in T 0 (T 0 ∈ V , where V is the set of tasks), the optimal solution to MinEnergy(G, D) can be computed in polynomial time O(|V | 2 ).

Proof. Let G be a tree graph rooted in T 0 . The optimal solution to MinEnergy(G, D) is obtained with a call to tree (G, T 0 , D), and we prove its optimality recursively on the depth of the tree. Similarly to the case of the fork graphs, we reduce the tree to an equivalent task which, if executed alone within a deadline D, consumes exactly the same amount of energy. The procedure eq is the procedure which reduces a tree to its equivalent task (see Algorithm 1).

If the tree has depth 0, then it is a single task, eq (G, T 0 ) returns the equivalent cost w 0 , and the optimal execution speed is w0 D (see Proposition 1). There is a solution if and only if this speed is not greater than s max , and then the corresponding energy consumption is

w 3 0 D 2 ,
as returned by the algorithm.

Assume now that for any tree of depth i < p, eq computes its equivalent cost, and tree returns its optimal energy consumption. We consider a tree G of depth p rooted in T 0 : G = T 0 ∪ {G i }, where each subgraph G i is a tree, rooted in T i , of maximum depth p -1. As in the case of forks, we know that each subtree G i has a deadline Dx, where x = w0 s0 , and s 0 is the speed at which task T 0 is executed. By induction hypothesis, we suppose that each graph G i is equivalent to a single task, T ′ i , of cost w ′ i (as computed by the procedure eq). We can then use the results obtained on forks to compute w (eq) 0 (see proof of Theorem 1):

w (eq) 0 = i (w ′ i ) 3 1 3 + w 0 .
Finally the tree is equivalent to one task of cost w (eq) 0

, and if w (eq) 0

D

≤ s max , the energy consumption is

w (eq) 0 3 D 2
, and no speed exceeds s max . Note that the speed of a task is always greater than the speed of its successors. Therefore, if w (eq) 0

D

> s max , we execute the root of the tree at speed s max and then process each subtree G i independently. Of course, there is no solution if w0 smax > D, and otherwise we perform the recursive calls to tree to process each subtree independently. Their deadline is then D -w0 smax . To study the time complexity of this algorithm, first note that when calling tree (G, T 0 , D), there might be at most |V | recursive calls to tree, once at each node of the tree. Without accounting for the recursive calls, the tree procedure performs one call to the eq procedure, which computes the cost of the equivalent task. This eq procedure takes a time O(|V |), since we have to consider the |V | tasks, and we add the costs one by one. Therefore, the overall complexity is in O(|V | 2 ). ⊓ ⊔

Series-parallel graphs

We can further generalize our results to series-parallel graphs (SPGs), which are built from a sequence of compositions (parallel or series) of smaller-size SPGs. The smallest SPG consists of two nodes connected by an edge (such a graph is called an elementary SPG). The first node is the source, while the second one is the sink of the SPG. When composing two SGPs in series, we merge the sink of the first SPG with the source of the second one. For a parallel composition, the two sources are merged, as well as the two sinks, as illustrated in Figure 2. We can extend the results for tree graphs to SPGs, by replacing step by step the SPGs by an equivalent task (procedure cost in Algorithm 2): we can compute the equivalent cost for a series or parallel composition.

However, since it is no longer true that the speed of a task is always larger than the speed of its successor (as was the case in a tree), we have not been able to find a recursive property on the tasks that should be set to s max , when one of the speeds obtained with the previous method exceeds s max . The problem of computing a closed form for a SPG with a finite value of s max remains open. Still, we have the following result when s max = +∞: (eq(G i , T i )) Proof. Let G be a series-parallel graph. The optimal solution to MinEnergy(G, D) is obtained with a call to SPG (G, D), and we prove its optimality recursively. Similarly to trees, the main idea is to peel the graph off, and to transform it until there remains only a single equivalent task which, if executed alone within a deadline D, would consume exactly the same amount of energy. The procedure cost is the procedure which reduces a tree to its equivalent task (see Algorithm 2). The proof is done by induction on the number of compositions required to build the graph G, p. If p = 0, G is an elementary SPG consisting in two tasks, the source T 0 and the sink T 1 . It is therefore a linear chain, and therefore equivalent to a single task whose cost is the sum of both costs, w 0 + w 1 (see Corollary 1 for linear chains). The procedure cost returns therefore the correct equivalent cost, and SPG returns the minimum energy consumption.

3   1 3 + w 0 ; end end T src A T snk T ′ src B T ′ snk (a) Two SPGs before composition. A (T src ; T ′ src ) (T snk ; T ′ snk ) B (b) Parallel composition. T src A (T snk ; T ′ src ) B T ′ snk (c) Series composition.
Let us assume that the procedures return the correct equivalent cost and minimum energy consumption for any SPG consisting of i < p compositions. We consider a SPG G, with p compositions. By definition, G is a composition of two smaller-size SPGs, G 1 and G 2 , and both of these SPGs have strictly fewer than p compositions. We consider G ′ 1 and G ′ 2 , which are identical to G 1 and G 2 , except that the cost of their source and sink tasks are set to 0 (these costs are handled separately), and we can reduce both of these SPGs to an equivalent task, of respective costs w ′ 1 and w ′ 2 , by induction hypothesis. There are two cases: • If G is a series composition, then after the reduction of G ′ 1 and G ′ 2 , we have a linear chain in which we consider the source T 0 of G 1 , the sink T 1 of G 1 (which is also the source of G 2 ), and the sink T 2 of G 2 . The equivalent cost is therefore w 0 + w ′ 1 + w 1 + w ′ 2 + w 2 , thanks to Corollary 1 for linear chains.

• If G is a parallel composition, the resulting graph is a fork-join graph, and we can use Corollaries 1 and 3 to compute the cost of the equivalent task, accounting for the source T 0 and the sink T 1 :

w 0 + (w ′ 1 ) 3 + (w ′ 2 ) 3 1 3 + w 1 .
Once the cost of the equivalent task of the SPG has been computed with the call to cost (G), the optimal energy consumption is

(cost(G)) 3 D 2 .
Contrarily to the case of tree graphs, since we never need to call the SPG procedure again because there is no constraint on s max , the time complexity of the algorithm is the complexity of the cost procedure. There is exactly one call to cost for each composition, and the number of compositions in the SPG is in O(|V |). All operations in cost can be done in O(1), hence a complexity in O(|V |). ⊓ ⊔

General DAGs

For arbitrary execution graphs, we can rewrite the MinEnergy(G, D) problem as follows:

Minimize

n i=1 u -2 i × w i subject to (i) t i + w j × u j ≤ t j for each edge (T i , T j ) ∈ E (ii) t i ≤ D for each task T i ∈ V (iii) u i ≥ 1 smax for each task T i ∈ V (2)
Here, u i = 1/s i is the inverse of the speed to execute task T i . We now have a convex optimization problem to solve, with linear constraints in the non-negative variables u i and t i . In fact, the objective function is a posynomial, so we have a geometric programming problem (see [6, Section 4.5]) for which efficient numerical schemes exist. However, as illustrated on simple fork graphs, the optimal speeds are not expected to be rational numbers but instead arbitrarily complex expressions (we have the cubic root of the sum of cubes for forks, and nested expressions of this form for trees). From a computational complexity point of view, we do not know how to encode such numbers in polynomial size of the input (the rational task weights and the execution ; end procedure cost (series-parallel graph G) begin Let T 0 be the source of G and T 1 its sink; if G is composed of only two tasks, T 0 and T 1 then return

w 0 + w 1 ; else /* G is a composition of two SPGs G 1 and G 2 . */ For i = 1, 2, let G ′ i = G i
where the cost of source and sink tasks is set to 0;

w ′ 1 = cost(G ′ 1 ); w ′ 2 = cost(G ′ 2 ); if G is a series composition then
Let T 0 be the source of G 1 , T 1 be its sink, and T 2 be the sink of G 2 ; return w 0 + w ′ 1 + w 1 + w ′ 2 + w 2 ; else /* It is a parallel composition. */ Let T 0 be the source of G, and T 1 be its sink;

return w 0 + (w ′ 1 ) 3 + (w ′ 2 ) 3 1 3 + w 1 ; end end end deadline)
. Still, we can always solve the problem numerically and get fixed-size numbers which are good approximations of the optimal values.

In the following, we show that the total power consumption of any optimal schedule is constant throughout execution. While this important property does not help to design an optimal solution, it shows that a schedule with large variations in its power consumption is likely to waste a lot of energy.

We need a few notations before stating the result. Consider a schedule for a graph G = (V, E) with n tasks. Task T i is executed at constant speed s i (see Lemma 1) and during interval [b i , c i ]: T i begins its execution at time b i and completes it at time c i . The total power consumption P (t) of the schedule at time t is defined as the sum of the power consumed by all tasks executing at time t:

P (t) = 1≤i≤n, t∈[bi,ci] s 3 i .
Theorem 4 Consider an instance of Continuous, and an optimal schedule for this instance, such that no speed is equal to s max . Then the total power consumption of the schedule throughout execution is constant.

Proof. We prove this theorem by induction on the number of tasks of the graph. First we prove a preliminary result:

Lemma 2 Consider a graph G = (V, E) with n ≥ 2 tasks, and any optimal schedule of deadline D. Let t 1 be the earliest completion time of a task in the schedule. Similarly, let t 2 be the latest starting time of a task in the schedule. Then, either G is composed of independent tasks, or 0 < t 1 ≤ t 2 < D.

Proof. Task T i is executed at speed s i and during interval [b i , c i ]. We have t 1 = min 1≤i≤n c i and t 2 = max 1≤i≤n b i . Clearly, 0 ≤ t 1 , t 2 ≤ D by definition of the schedule. Suppose that t 2 < t 1 . Let T 1 be a task that ends at time t 1 , and T 2 one that starts at time t 2 . Then:

• ∄T ∈ V, (T 1 , T ) ∈ E (otherwise, T would start after t 2 ), therefore, t 1 = D;

• ∄T ∈ V, (T, T 2 ) ∈ E (otherwise, T would finish before t 1 ); therefore t 2 = 0. This also means that all tasks start at time 0 and end at time D. Therefore, G is only composed of independent tasks.

⊓ ⊔

Back to the proof of the theorem, we consider first the case of a graph with only one task. In an optimal schedule, the task is executed in time D, and at constant speed (Lemma 1), hence with constant power consumption.

Suppose now that the property is true for all DAGs with at most n -1 tasks. Let G be a DAG with n tasks. If G is exactly composed of n independent tasks, then we know that the power consumption of G is constant (because all task speeds are constant). Otherwise, let t 1 be the earliest completion time, and t 2 the latest starting time of a task in the optimal schedule. Thanks to Lemma 2, we have 0 < t 1 ≤ t 2 < D.

Suppose first that t 1 = t 2 = t 0 . There are three kinds of tasks: those beginning at time 0 and ending at time t 0 (set S 1 ), those beginning at time t 0 and ending at time D (set S 2 ), and finally those beginning at time 0 and ending at time D (set S 3 ). Tasks in S 3 execute during the whole schedule duration, at constant speed, hence their contribution to the total power consumption P (t) is the same at each time-step t. Therefore, we can suppress them from the schedule without loss of generality. Next we determine the value of t 0 . Let A 1 = Ti∈S1 w 3 i , and A 2 = Ti∈S2 w 3 i . The energy consumption between 0 and t 0 is A1 t 2 0 , and between t 0 and D, it is A2 (D-t0) 2 . The optimal energy consumption is obtained with

t 0 = A 1 3 1 A 1 3 1 +A 1 3 2
. Then, the total power consumption of the optimal schedule is the same in both intervals, hence at each time-step: we derive that

P (t) = A 1 3 1 +A 1 3 2 D 3
, which is constant.

Suppose now that t 1 < t 2 . For each task T i , let w ′ i be the number of operations executed before t 1 , and w ′′ i the number of operations executed after t 1 (with w ′ i + w ′′ i = w i ). Let G ′ be the DAG G with execution costs w ′ i , and G ′′ be the DAG G with execution costs w ′′ i . The tasks with a cost equal to 0 are removed from the DAGs. Then, both G ′ and G ′′ have strictly fewer than n tasks. We can therefore apply the induction hypothesis. We derive that the power consumption in both DAGs is constant. Since we did not change the speeds of the tasks, the total power consumption P (t) in G is the same as in G ′ if t < t 1 , hence a constant. Similarly, the total power consumption P (t) in G is the same as in G ′′ if t > t 1 , hence a constant. Considering the same partitioning with t 2 instead of t 1 , we show that the total power consumption P (t) is a constant before t 2 , and also a constant after t 2 . But t 1 < t 2 , and the intervals [0, t 2 ] and [t 1 , D] overlap. Altogether, the total power consumption is the same constant throughout [0, D], which concludes the proof.

⊓ ⊔

Discrete models

In this section, we present complexity results on the three energy models with a finite number of possible speeds. The only polynomial instance is for the Vdd-Hopping model, for which we write a linear program in Section 5.1. Then, we give NP-completeness results in Section 5.2, and approximation results in Section 5.3, for the Discrete and Incremental models. Proof. Let G be the execution graph of an application with n tasks, and D a deadline. Let s 1 , ..., s m be the set of possible processor speeds. We use the following rational variables: for 1 ≤ i ≤ n and 1 ≤ j ≤ m, b i is the starting time of the execution of task T i , and α (i,j) is the time spent at speed s j for executing task T i . There are n + n × m = n(m + 1) such variables. Note that the total execution time of task T i is m j=1 α (i,j) . The constraints are: • ∀1 ≤ i ≤ n, b i ≥ 0: starting times of all tasks are non-negative numbers;

The Vdd-Hopping model

• ∀1 ≤ i ≤ n, b i + m j=1 α (i,j) ≤ D: the deadline is not exceeded by any task; • ∀1 ≤ i, i ′ ≤ n such that T i → T i ′ , t i + m j=1 α (i,j) ≤ t i ′ : a task cannot start before its predecessor has completed its execution; • ∀1 ≤ i ≤ n, m j=1 α (i,j) × s j ≥ w i : task T i is completely executed. The objective function is then min n i=1 m j=1 α (i,j) s 3
j . The size of this linear program is clearly polynomial in the size of the instance, all n(m + 1) variables are rational, and therefore it can be solved in polynomial time [START_REF] Schrijver | Combinatorial Optimization: Polyhedra and Efficiency[END_REF].

⊓ ⊔

NP-completeness results

Theorem 6 With the Incremental model (and hence the Discrete model), MinEnergy(G, D) is NP-complete.

Proof. We consider the associated decision problem: given an execution graph, a deadline, and a bound on the energy consumption, can we find an execution speed for each task such that the deadline and the bound on energy are respected? The problem is clearly in NP: given the execution speed of each task, computing the execution time and the energy consumption can be done in polynomial time.

To establish the completeness, we use a reduction from 2-Partition [START_REF] Garey | Computers and Intractability; A Guide to the Theory of NP-Completeness[END_REF]. We consider an instance I 1 of 2-Partition: given n strictly positive integers a 1 , . . . , a n , does there exist a subset I of {1, . . . , n} such that i∈I a i = i / ∈I a i ? Let T = 1 2 n i=1 a i . We build the following instance I 2 of our problem: the execution graph is a linear chain with n tasks, where:

• task T i has size w i = a i ;

• the processor can run at m = 2 different speeds;

• s 1 = 1 and s 2 = 2, (i.e., s min = 1, s max = 2, δ = 1);

• L = 3T /2;

• E = 5T . Clearly, the size of I 2 is polynomial in the size of I 1 .

Suppose first that instance I 1 has a solution I. For all i ∈ I, T i is executed at speed 1, otherwise it is executed at speed 2. The execution time is then i∈I a i + i / ∈I a i /2 = 3 2 T = D, and the energy consumption is E = i∈I a i + i / ∈I a i × 2 2 = 5T = E. Both bounds are respected, and therefore the execution speeds are a solution to I 2 .

Suppose now that I 2 has a solution. Since we consider the Discrete and Incremental models, each task run either at speed 1, or at speed 2. Let I = {i | T i is executed at speed 1}. Note that we have i / ∈I a i = 2T -i∈I a i . The execution time is D ′ = i∈I a i + i / ∈I a i /2 = T + ( i∈I a i )/2. Since the deadline is not exceeded, D ′ ≤ D = 3T /2, and therefore i∈I a i ≤ T .

For the energy consumption of the solution of I 2 , we have

E ′ = i∈I a i + i / ∈I a i × 2 2 = 2T + 3 i / ∈I a i . Since E ′ ≤ E = 5T
, we obtain 3 i / ∈I a i ≤ 3T , and hence i / ∈I a i ≤ T . Since i∈I a i + i / ∈I a i = 2T , we conclude that i∈I a i = i / ∈I a i = T , and therefore I 1 has a solution. This concludes the proof. ⊓ ⊔

Approximation results

Here we explain, for the Incremental and Discrete models, how the solution to the NP-hard problem can be approximated. Note that, given an execution graph and a deadline, the optimal energy consumption with the Continuous model is always lower than that with the other models, which are more constrained.

Theorem 7 With the Incremental model, for any integer K > 0, the MinEnergy(G, D) problem can be approximated within a factor (1 + δ smin ) 2 (1 + 1 K ) 2 , in a time polynomial in the size of the instance and in K.

Proof. Consider an instance I inc of the problem with the Incremental model. The execution graph G has n tasks, D is the deadline, δ is the minimum permissible speed increment, and s min , s max are the speed bounds. Moreover, let K > 0 be an integer, and let E inc be the optimal value of the energy consumption for this instance I inc .

We construct the following instance I vdd with the Vdd-Hopping model: the execution graph and the deadline are the same as in instance I inc , and the speeds can take the values

s min × 1 + 1 K i 0≤i≤N ,
where N is such that s max is not exceeded: N = (ln(s max )ln(s min ))/ ln 1 + 1

K

. As N is asymptotically of order O(K ln(s max )), the number of possible speeds in I vdd , and hence the size of I vdd , is polynomial in the size of I inc and K.

Next, we solve I vdd in polynomial time thanks to Theorem 5. For each task T i , let s (vdd) i be the average speed of T i in this solution: if the execution time of the task in the solution is d i , then s In order to prove that this algorithm is an approximation of the optimal solution, we need to prove that E algo ≤ (1 + δ smin ) 2 (1 + .

Next, we bound E vdd thanks to the optimal solution with the Continuous model, E con . Let I con be the instance where the execution graph G, the deadline D, the speeds s min and s max are the same as in instance I inc , but now admissible speeds take any value between s min and s max . Let s (con) i be the optimal continuous speed for task T i , and let 0 ≤ u ≤ N be the value such that:

s min × 1 + 1 K u ≤ s (con) i ≤ s min × 1 + 1 K u+1 = s * i .
In order to bound the energy consumption for I vdd , we assume that T i runs at speed s * i , instead of s (vdd) i . The solution with these speeds is a solution to I vdd , and its energy consumption is E * ≥ E vdd . From the previous inequalities, we deduce that s * i ≤ s (con) i × 1 + 1 K , and by summing over all tasks,

E vdd ≤ E * = i w i (s * i ) 2 ≤ i w i s (con) i × 1 + 1 K 2 ≤ E con × 1 + 1 K 2 ≤ E inc × 1 + 1 K 2 . ⊓ ⊔ RR n°7598
Proposition 3

• For any integer δ > 0, any instance of MinEnergy(G, D) with the Continuous model can be approximated within a factor (1 + δ smin ) 2 in the Incremental model with speed increment δ.

• For any integer K > 0, any instance of MinEnergy(G, D) with the Discrete model can be approximated within a factor (1 + α s1 ) 2 (1 + 1 K ) 2 , with α = max 1≤i<m {s i+1s i }, in a time polynomial in the size of the instance and in K.

Proof. For the first part, let s (con) i be the optimal continuous speed for task T i in instance I con ; E con is the optimal energy consumption. For any task T i , let s i be the speed of I inc such that s iδ < s con i ≤ s i . Then, s (con) i ≤ s i × 1 + δ smin . Let E be the energy with speeds s i .

E con ≤ E × 1 + δ smin 2
. Let E inc be the optimal energy of I inc . Then,

E con ≤ E inc × 1 + δ smin 2 .
For the second part, we use the same algorithm as in Theorem 7. The same proof leads to the approximation ratio with α instead of δ.

⊓ ⊔

Conclusion

In this paper, we have assessed the tractability of a classical scheduling problem, with task preallocation, under various energy models. We have given several results related to Continuous speeds. However, while these are of conceptual importance, they cannot be achieved with physical devices, and we have analyzed several models enforcing a bounded number of achievable speeds, a.k.a. modes. In the classical Discrete model that arises from DVFS techniques, admissible speeds can be irregularly distributed, which motivates the Vdd-Hopping approach that mixes two consecutive modes optimally. While computing optimal speeds is NP-hard with discrete modes, it has polynomial complexity when mixing speeds. Intuitively, the Vdd-Hopping approach allows for smoothing out the discrete nature of the modes. An alternate (and simpler in practice) solution to Vdd-Hopping is the Incremental model, where one sticks with unique speeds during task execution as in the Discrete model, but where consecutive modes are regularly spaced. Such a model can be made arbitrarily efficient, according to our approximation results. Altogether, this paper has laid the theoretical foundations for a comparative study of energy models. In the recent years, we have observed an increased concern for green computing, and a rapidly growing number of approaches. It will be very interesting to see which energy-saving technological solutions will be implemented in forthcoming future processor chips!

(d) 2 = 5 ,

 25 we obtain an energy E = 8 × 5 2 = 200. A better solution is obtained with s 1 = s (d) 3 = 6, s 2 = s 3 = s

(d) 2 = 5 ; 4 Figure 1 :

 2541 Figure 1: Execution graph for the example.

Figure 2 :

 2 Figure 2: Composition of series-parallel graphs (SPGs).

Algorithm 2 :

 2 Solution to MinEnergy(G, D) for series-parallel graphs. procedure SPG (series-parallel graph G, deadline D)

Theorem 5

 5 With the Vdd-Hopping model, MinEnergy(G, D) can be solved in polynomial time.

=

  w i /d i ; E vdd is the optimal energy consumption obtained with these speeds. Let s(algo) i = min u {s min + u × δ | u × δ ≥ s (vdd) i} be the smallest speed in I inc which is larger than s(vdd) i. There exists such a speed since, because of the values chosen for I vdd , s(vdd) i ≤ s max .The values s (algo) i can be computed in time polynomial in the size of I inc and K. Let E algo be the energy consumption obtained with these values.

Algorithm 1 :

 1 Solution to MinEnergy(G, D) for trees. procedure tree (tree G, root T 0 , deadline D) beginLet w=eq (tree G, root T 0 );

	if w D ≤ s max then return w 3 D 2 ; else
	if w0 smax > D then return Error:No Solution;
	else
	/* T 0 is executed at speed s max */
	return w 0 × s 2 max + Gi subtree rooted in Ti∈children(T0) tree G i , T i , D -	w 0 s max	;
	end
	end
	end
	procedure eq (tree G, root T 0 )
	begin
	if children(T 0 )=∅ then return w 0 ;
	else
		
	return	
		Gi subtree rooted in Ti∈children(T0)

  1 K ) 2 × E inc . For each task T i , s

	Since s min ≤ s	(vdd) i	, we derive that s	(algo) i	≤ s	(vdd) i	(algo) i smin ). Summing over all tasks, we get -δ ≤ s (vdd) i (algo) i ≤ s × (1 + δ	.
	E algo =	(algo) i	2	≤	i	w i s	(vdd) i	× (1 +	δ s min	)	2	≤ E vdd × 1 +	s min δ	2

i w i s

RR n°7598


D Miclet
email: denis.miclet@cemagref.fr

; E Piron

; S Venel

; S Villette

Mass flow control for manure spreader

Keywords: Manure spreader, mass flow control, longitudinal flow rate curve

The objectives of this work were to improve the performances of the manure spreaders used by farmers. The principal aim of this paper is to show the chosen way to improve longitudinal distribution of this machinery. A prototype was developed and evaluated in Cemagref at Montoldre. The method consists in controlling the speed of the scraper conveyor regarding the height of the gate during the hopper unloading. The gate is able to follow the product profile. It is technically based on an electronic and automatic adaptation of the scrapper conveyor speed in regard with the alimentation section of the beaters and the spreader velocity into the field. For each product, the longitudinal flow rate result is improved according to the EN13080 Standard. Using this technique, the percentage of time spent in the tolerance zone is almost doubled compared to tests without control for the composted products and the longitudinal variation coefficient divided by 2 or 3 depending on the types of products.

Introduction

In agriculture, manure, compost, or sewage sludge are generally applied with manure spreaders. These ones are used in farming because of their simplicity, their important transported volume and their general versatility. Today, they are more and more equipped with modern devices which are ergonomic and easy to adjust, designed to make them more efficient in regard with the applied rates. This feature requires the installation of an electrohydraulic system, especially on the driving circuit of the scraper conveyor. The majority of scraper conveyors is currently driven by hydraulic power. The most advanced feature are piloting by electronic and computer which allow a specific function (Proportional Flow rate in regard with the spreader speed), which uses the control of the scraper conveyor with respect to the spreader speed.

All these functions have a major interest and are really necessary to optimize the spreading with this agricultural machinery. Without these functions, it's impossible to obtain the target rate at each point of the field. However, to ensure a correct running of these devices during spreading, the mass flow criteria must be under control: this is not the case for the majority of spreaders. The current devices can solve problems of slowing or slippage of the tractor. But they don't solve defaults related to density heterogeneities or spreader filling. Moreover, they are not able to adjust the machine settings in function of the applied product.

The mass flow curves recorded on machines equipped with modern electronics show some defects. One of the most significant problems with this type of spreader is the variation of the delivered flow rate during the discharge especially at the beginning and at the end of the hopper unloading. Then, this default involves rate heterogeneity into the field.

Last years, many studies and several devices have been developed to control continuously the mass flow. In particular, the control by the consumed torque on the beaters, the global weighing of the spreader or the weighing of a part of the product just in front of the beaters. Actually, No devices provide entire satisfaction in term of mass flow control.

A correct control of manure application should be based on the coupling of two different devices. The first one is used to solve the defaults at the beginning and at the end of hopper unloading. The second one is used to weigh the product and provide continuously a correct value for the manure volumetric mass to be spread. The aim of this work is to propose a technical solution combining the use of mechanical adaptations on the spreader and some electronic developments to obtain a greater regularity of the flow rate during the discharge. This method, patented in 2006 by the Cemagref (Piron and Miclet, 2006), has been commercialised by a French society: "Agrotronix". It is technically based on an electronic and automatic adaptation of the scrapper conveyor speed in regard with the alimentation section of the beaters and the spreader velocity into the field. This system is adjusted according to the product density, which is continuously measured by several sensors. Firstly, the device regularises the shape of the flow rate curve providing a maximum range of time with a good stability, and secondly, the absolute value of this regular flow rate curve is adapted to obtain the objective rate.

Materials and methods

In this study, a base of manure spreader has been used. The selected machine is equipped with two vertical beaters and a scraper conveyor driven by hydraulic. The storage capacity was 6.15 m 3 with hopper dimensions of 3.57m length, 1.43m width and 1.3m height. A scraper conveyor takes place at the bottom of the hopper to displace products through the spreading systems. A flow-control gate was placed on the hopper, 0.8 meter far from the vertical beaters.

The proposition of flow rate control

The variations of the delivered flow rate during the discharge fit with the section variations of the product in front of the beaters. This section is equal to the multiplication of the hopper width by the height of the product. The width of the hopper is constant during the discharge so the only variable parameter changing the product section is the height of product.

Based on this observation, a mass flow control is possible during the hopper unloading by enslaving the scraper conveyor speed (V (t)) to the height of the product in front of the beaters (H (t)) knowing the height of the flow-control gate. Then, the conveyor speed is written as follows:

) ( 1 ) ( ) ( 1 ) ( ) ( ) ( 1 ) ( ) ( ) ( t H Const t H t L t t F t S t t F t V × ≈ × × ≈ × = µ µ ) (t µ : Product density -(kg.m -3 )
) (t S : Section -multiplication of the hopper width (L(t)) by the height of the product

(H(t)) -(m 2 ) ) (t F : Flow rate -(kg/s)
This solution is not new and is already present on some "rate proportional to speed" devices used on sewage sludge application where the value of flow rate is setting by the height of the door. For manure, this adjustment is impossible without wrenching the gate because of the important manure cohesion.

To improve the control working, the system must take into account a chronological delay concerning the gate heights to change the scraper conveyor speed only when the measured volume of product is really just in front of the beaters. In this way, the conveyor speed is modified at the right time. Then, the conveyor speed is written as follows: Following the manure profile, the gate generates a flat upper surface in the hopper. Consequently, a good measurement of the product section is guaranteed and the optimal speed of scraper conveyor can be applied by electronic.

( ) 1 ( ) 1 1 ( ) ( ) ( ) ( ) ( ) ( ) ( ) dx dx dx F t F t V t Const t S t t t L t H t t H t t µ µ = × ≈ × ≈ × - × - - ) (
This adaptation of the gate height to the product height has a significant effect against manure crumbling into the spreader in direction of the beaters. Until now, the product density is considered as constant even if this criterion is not fixed in the reality. The product density can change (i) during spreading, (ii) from one hopper loading to another (iii) but also from one product to another. The longitudinal curve is close to the theoretical longitudinal distribution curve but an offset is still present between both curves (Fig

1.b)
To improve the results, a second regulation level has to be considered. The spreader weighing is necessary to adapt the volumetric mass factor continuously. Then, the conveyor speed is written as follows:

) ( ) ( 1 ) ( 1 ) ( ) ( ) ( dx dx t t S t Const t t S t t F t V - × × ≈ - × = µ µ
A first weight measurement is necessary just after spreader loading. It allows the volumetric mass calculation of the product taking into account the spreader volume. Then, this weighing measurement does not require a high sampling frequency (0.1 Hz is sufficient). The structure of the machine was equipped with load cells. In this case, the mass information is not used for a closed loop control, but is simply used to continuously calibrate the product density (Fig. 2a). Similar satisfying devices are already used on fertiliser spreaders. They can continuously adjust the product density during spreading.

Mechanical and electronic adaptation of sensors on the spreader

Some adaptations are done to place sensors on the spreader. All these sensors are plugged on a computer unit (Fig 3.a). This unit is the brain of the system: all sensor signals are read by the unit and all electrical orders are sent by it.

Volumetric flow rate control

The system requires three sensors to ensure the global functioning of the volumetric flow rate:

-One angle sensor with analog output to measure the gate height, -One numeric encoder to measure the scraper conveyor speed, -An inductive sensor to measure the spreader speed.

Depending on the type and the configuration of the spreader, other sensors can be installed to obtain similar results.

Gate height control

The opening gate control was based on the continuous measurement of forces induced by the product on the gate (Fig 4.a). Two main solutions were possible: the use of force transducers directly integrated into the gate or the use of inductive sensors included into a mechanical frame placed on the gate bottom. The second solution was chosen because the system was cheaper and more robust to work with products as manure (Fig 4 .c andd).

The developed system uses two inductive sensors. Using these sensors, the gate can be positioned at fixed positions, otherwise the gate would only go up or down without providing regular measurements of the height of product during the hopper unloading. The sensors send a binary signal value depending on the force applied by the product on the gate. The use of two inductive sensors allows the same control than the one obtained using force transducers (Fig 4 .b): -When only one sensor is active: No action on the gate and therefore the scraper conveyor speed stays constant, -When both sensors are active: the gate goes up and the scraper conveyor speed decreases, -When both sensors are inactive: the gate goes down and the scraper conveyor speed increases.

Product density calibration: The weight measurement of the spreader

The density calibration is possible by the strain gages addition on the spreader mechanic frame. With this type of weighing, the delivered signal accuracy is enough to know the mass of applied product. The mass difference is calculated between two instants spaced of 10 seconds. The mechanical noise generated during the spreader displacement in the field is not a major problem because the signal is filtered on a significant period. In this case, the mass information of load cells is not used for closed loop control but only for a continuous density calibration.

The installation requires three strain gages placed on the spreader frame at each support point: two on the wheels axis and one on the coupling (Fig. 5). This weighing system can be placed on a spreader without any modifications: the developed device doesn't require a dual mechanical frame (which is very costly) to insert the load transducer.

Data analysis

The basis for the analysis of all sets of experiments was the European Standard EN13080. For this, load cells are placed under the spreader and the tractor to weight continuously the total mass of the tractor, the spreader and the product during the hopper unloading. This measurement is achieved in static at a frequency of 2 Hz. Then, the mass flow is calculated, and filtered with a low pass (Fig 6 .a).

The Figure 6.b represents a curve commonly obtained with a manure spreader according to the standard EN13080. Several parameters can be calculated from this flow rate curve. The first parameter is the characteristic flow rate. It corresponds to the highest average flow rate occurring during 30% of the unloading time of the spreader. From this characteristic flow rate is defined a tolerance zone which is between ±15% of the characteristic flow rate. The percentage of the unloading time during which the flow rate is in the tolerance zone is calculated and defined as the stretch within the tolerance zone. The longitudinal coefficient of variation is calculated on the average flow. It translates the flow rate variability during the spreader unloading.

To satisfy the EN13080 standard, the longitudinal CV must be lower than 40% and the stretch within the tolerance zone must be higher than 35%.

Results

Three different products were used to evaluate the flow rate control of the spreader: a feedlot manure with straw, a compost of feedlot manure and a co-compost of green wastes mixed with fermentable domestic wastes. For each product, two measurements of the flow rate were done according to EN13080 Standard. The first plot at the left in Fig. 7 All the presented plots were obtained with the first stage of the flow rate control. The control of the mass flow during the hopper unloading was performed by enslaving the scraper conveyor speed to the height of the product on beaters with knowledge of the height of the flow-control gate. The continuous measurement of the flow rate was not installed for these tests. The product is considered constant for each spreader unloading. Since a mass measurement was done just after each spreader loading, the calculation of the product volumetric mass is easy, taking into account the spreader volume. For the three measures without scraper conveyor control, there is always a little time range with a constant flow rate. This is the area where there is no product crumbling. The rest of the time corresponds to areas where the flow rate increases (at the beginning of the spreader unloading) or where the flow rate decreases (at the end of the spreader unloading).

Longitudinal flow rate records

For the three measurements with the scraper conveyor speed control, the longitudinal flow rate curves present a rectangular shape as expected. The areas which show problems without electronic are removed. It only remains variability on the results; this noise is higher for the manure than for the compost or the co-compost. Indeed, composted products are homogenized, with more regular particle shapes, and are less ejected by the beaters in package, at the opposite of manure with straw which presents a great variability.

The noise is more important for results with electronic because the distance between the gate and the beaters is very important on our experimental spreader (0.8 meter).

Traditionally, the gate prevents crumbling in the hopper before the gate. In our case, due to experimental specific spreader geometry, there isn't any device to avoid product crumbling in the interval between the gate and the beaters. This phenomena is particularly visible for the composted product.

Results synthesis

Co-compost Compost of manure Manure

The table 1 summarizes all the calculated data according to the protocol of the EN 13080 standard for longitudinal point of view. That is, in particular the stretch within the tolerance zone, the longitudinal CV, the total unloading time and the density of three products used for the six longitudinal distributions.

In terms of standard respect, for trials without scraper conveyor speed activation, the stretch within the tolerance zone is very difficult to reach. For the longitudinal CV, it is the same, results don't satisfy the standard. All the Longitudinal CVs are higher than 40% and all the stretch within the tolerance zone are limit.

For measurements with scraper conveyor under control in regard with the gate height, the performance levels are significantly improved. The results of stretch within the tolerance zone and the longitudinal CV fully satisfy the EN13080 standard. The percentage of time spent in the tolerance zone is almost doubled compared to tests without control for the composted products. Indeed, the period of flow rate decreasing which appears in the second part of the spreader unloading is corrected by increasing the scraper conveyor speed. The volumetric discharge is also almost constant.

The worst result (but satisfying the standard) is for the manure. In this case, the product heterogeneity induces a lot of flow rate variation (which penalizes the standard criteria). Despite the product variability, the longitudinal CV is less important than 40% thanks to the speed correction of the scraper conveyor.

Thanks to the presented control, the longitudinal CV is divided by 2 or 3 depending on the types of products.

For the three products, the unloading time is reduced by one third using the proposed control over the tests without control. This phenomenon is due to the variable speed of progress of the scraper conveyor. Indeed, the flow rate decreasing encountered during the second part of the spreader conveyor is compensated and thus reduced by this principle.

Conclusion

This study showed gains thanks to the developed control which consists in automatically compensate the scraper conveyor in regard with the product section which feeds the beaters. Some real measurements of longitudinal distribution curves show improvements to expect from an application using the proposed control. Three very different products were tested alternately with and without control of the scraper conveyor. The automatic manure profile tracking was done by sensor adding on the gate. The tests were performed according to EN 13080 standard, which calculates two criteria in order to characterize the longitudinal distribution: the stretch within the tolerance zone and the longitudinal CV. Results are significantly improved by the process control. For our spreader, the percentage of time spent in the zone of tolerance is multiplied by two and the longitudinal CV is divided by three. Long period of regular decreasing flow are fully avoid using the proposed regulation. These curves are much more rectangular for each fertiliser tested.

:

  Manure height taking into account the distance between the gate and the beaters (m) For manures, the technical solution consists in adding a first regulation level. Continuously during spreading, this first control must enslave the height of the gate at the height of the product just in front of the beaters. With this technique, for a desired rate, the scraper conveyor speeds up when the door height increases and slows down when the gate height reduces (Fig. 1.a).

Fig 1 :

 1 Fig 1: Description of the first stage of the flow rate control. (a) Adaptation of the gate height to the height of product (during all the hopper unloading) (b) Consequence on the distribution curve.

Fig 2 :

 2 Fig 2: Description of the total flow rate control. (a) Schematic description of the control system (b) Consequence on the distribution curve.

Fig 3 :

 3 Fig 3: Description of the volumetric flow rate control. (a) Schematic draw of the system (b) Photography of sensors which are used on the spreader

Fig 4 :

 4 Fig 4: Description of the gate control. (a) Description of the gate and electronic adaptation (b)Table of hydraulic jack order for the gate control (c) Real mechanical gate adaptation (d) A view of the inductive sensor used

Fig 5 :

 5 Fig 5: Description of the weighing measure installed on the manure spreader. (a) Schematic draw of the weighing system (b) A view of used sensor for the spreader weighing

Fig 6 :

 6 Fig 6: Description of the weight measurement device installed on the manure spreader. (a) Schematic draw of the measurement protocol (b) Example of longitudinal distribution curve

  .a, Fig 8.a and Fig 9.a shows the longitudinal flow result obtained with the spreader without flow rate control. In the other side, the plot in Fig. 7.b, Fig 8.b and Fig 9.b shows the longitudinal flow rate result obtained with the spreader with the developed flow rate control.

Fig 7 :

 7 Fig 7: Measure of longitudinal flow rate according to standard EN13080 for manure (a) without flow rate control (b) with the flow rate control

Table 1 :

 1 results synthesis of longitudinal flow rate measurement according the EN13080 Standard for 6 tests with three products (comparison between a normal spreader and the same spreader equipped with a flow rate control):

		Without flow rate	With flow rate	Without flow rate	With flow rate	Without flow rate	With flow rate
		control	control	control	control	control	control
	Stretch within tolerance zone (The standard is satisfy if > 35%)	36.1	43.7	38.8	66.3	39.8	67.2
	Longitudinal CV (%) (The standard is satisfy if < 40%)	58.7	27.1	45.6	27.5	60	18
	Unloading time (s)	329.4	211.9	308.2	208.5	332.9	215.6
	volumetric mass (kg/m³)	690	738	663	620	648	675

Acknowledgements

The authors would like to thank Olivier LEKEUX, Pierre Hervé LECOCQ, Henri Cherasse and Guy Brenon for their involvement in developing this device.