Guillaume Aupy

Anne Benoit

Paul Renaud-Goud

Yves Robert

Energy-aware algorithms for task graph scheduling, replica placement and checkpoint strategies

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]. To reduce energy consumption, processors can run at different speeds. Faster speeds allow for a faster execution, but they also lead to a much higher (superlinear) power consumption. Energy-aware scheduling aims at minimizing the energy consumed during the execution of the target application, both for computations and for communications. The price to pay for a lower energy consumption usually is a much larger execution time, so the energy-aware approach makes better sense when coupled with some prescribed performance bound. In other words, we have a bi-criteria optimization problem, with one objective being energy minimization, and the other being performance-related.

In this chapter, we discuss several problems related to data centers, for which energy consumption is a crucial matter. Indeed, statistics showed that in 2012, some data centers consume more electricity than 250 000 european houses. If the cloud was a country, it would be ranked as the fifth world-wide rank in terms of demands in electricity, and the need is expected to be multiplied by three before 2020. We focus mainly on the energy consumption of processors, although a lot of electricity is now devoted to cooling the machines, and also for network communications.

Energy models are introduced in Section 2. Depending on the different research areas, several different energy models are considered, but they all share the 1 same core assumption: there is a static energy consumption, which is independent on the speed at which a processor is running, and a dynamic energy consumption, which increases superlinearly with the speed. The most common models for speeds are either to use continuous speeds in a given interval, or to consider a set of discrete speeds (the latter being more realistic for actual processors). We discuss further variants of the discrete model: in the VDD-hopping model, the speed of a task can be changed during execution, hence allowing to simulate the continuous case; the incremental model is similar to the discrete model with the additional assumption that the different speeds are spaced regularly. Finally, we propose a literature survey on energy models, and we provide an example to compare models.

The first case study is about task graph scheduling (see Section 3). 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 speeds leads to an NP-complete problem, even if the speeds 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.

Then in Section 4, we discuss a variant of the replica placement problem aiming at an efficient power management. We study optimal strategies to place replicas in tree networks, with the double objective to minimize the total cost of the servers, and/or to optimize power consumption. The client requests are known beforehand, and some servers are assumed to pre-exist in the tree. Without power consumption constraints, the total cost is an arbitrary function of the number of existing servers that are reused, and of the number of new servers. Whenever creating and operating a new server has higher cost than reusing an existing one (which is a very natural assumption), cost optimal strategies have to trade-off between reusing resources and load-balancing requests on new servers. We provide an optimal dynamic programming algorithm that returns the optimal cost, thereby extending known results from Wu, Lin and Liu [START_REF] Wu | Optimal replica placement in hierarchical Data Grids with locality assurance[END_REF][START_REF] Liu | Optimal placement of replicas in data grid environments with locality assurance[END_REF] without pre-existing servers. With power consumption constraints, we assume that servers operate under a set of M different speeds depending upon the number of requests that they have to process. In practice, M is a small number, typically 2 or 3, depending upon the number of allowed voltages [START_REF]Intel XScale technology[END_REF][START_REF] Hotta | Profile-based optimization of power performance by using dynamic voltage scaling on a pc cluster[END_REF]. Power consumption includes a static part, proportional to the total number of servers, and a dynamic part, proportional to a constant exponent of the server speed, which depends upon the model for power. The cost function becomes a more complicated function that takes into account reuse and creation as before, but also upgrading or downgrading an existing server from one speed to another. We show that with an arbitrary number of speeds, the power minimization problem is NP-complete, even without cost constraint, and without static power. Still, we provide an optimal dynamic programming algorithm that returns the minimal power, given a threshold value on the total cost; it has exponential complexity in the number of speeds M , and its practical usefulness is limited to small values of M . However, experiments conducted with this algorithm show that it can process large trees in reasonable time, despite its worst-case complexity.

The last case study investigates checkpointing strategies (see Section 5). Nowadays, high performance computing is facing a major challenge with the increasing frequency of failures [START_REF] Dongarra | The international exascale software project: a call to cooperative action by the global high-performance community[END_REF]. There is a need to use fault tolerance or resilience mechanisms to ensure the efficient progress and correct termination of the applications in the presence of failures. A well-established method to deal with failures is checkpointing: a checkpoint is taken at the end of the execution of each chunk of work. During the checkpoint, we check for the accuracy of the result; if the result is not correct, due to a transient failure (such as a memory error or software error), the chunk is re-executed. This model with transient failures is one of the most used in the literature, see for instance [START_REF] Zhu | The effects of energy management on reliability in real-time embedded systems[END_REF][START_REF] Degalahal | Soft errors issues in low-power caches[END_REF]. In this section, we aim at minimizing the energy consumption when executing a divisible workload under a bound on the total execution time, while resilience is provided through checkpointing. We discuss several variants of this multi-criteria problem. Given the workload, we need to decide how many chunks to use, what are the sizes of these chunks, and at which speed each chunk is executed (under the continuous model). Furthermore, since a failure may occur during the execution of a chunk, we also need to decide at which speed a chunk should be re-executed in the event of a failure. The goal is to minimize the expectation of the total energy consumption, while enforcing a deadline on the execution time, that should be met either in expectation (soft deadline), or in the worst case (hard deadline). For each problem instance, we propose either an exact solution, or a function that can be optimized numerically.

Finally, we provide concluding remarks in Section 6.

As already mentioned, 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 the leakage power) 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 speed [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 realtime 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 (superlinear) power consumption.

In this section, we survey different models for dynamic energy consumption, taken from the literature. These models are categorized as follows:

CONTINUOUS model. Processors can have arbitrary speeds, and can vary them continuously within the interval [s min , s max ]. 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]. In the CONTINUOUS model, a processor can change its speed at any time during execution. DISCRETE model. Processors have a discrete number of predefined speeds, which correspond to different voltages and frequencies that the processor can be subjected to [START_REF] Okuma | Software energy reduction techniques for variable-voltage processors[END_REF]. These speeds are denoted as s 1 , ..., s m . Switching speeds is not allowed during the execution of a given task, but two different tasks scheduled on a same processor can be executed at different speeds.

VDD-HOPPING model. This model is similar to the DISCRETE one, with a set of different speeds s 1 , ..., s m , except that switching speeds 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 speeds [START_REF] Miermont | A Power Supply Selector for Energy-and Area-Efficient Local Dynamic Voltage Scaling[END_REF]. In the VDD-HOPPING model, 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.

INCREMENTAL model. In this variant of the DISCRETE model, there is a value δ that corresponds to the minimum permissible speed increment, induced by the minimum voltage increment that can be achieved when controlling the processor CPU. Hence, possible speed values are obtained as s = s min + i × δ, where i is an integer such that 0 ≤ i ≤ smax -s min After the literature survey in Section 2.1, we provide a simple example in Section 2.2, in order to illustrate the different models.

Literature survey

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 real-time 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 of 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 variable-voltage 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 leakage-aware scheduling heuristics that 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; the goal is to determine 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 energydelay 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].

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 variable-voltage 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].

The INCREMENTAL model was introduced in [START_REF] Aupy | Reclaiming the energy of a schedule: models and algorithms[END_REF]. 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 that 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.

Example

Energy-aware scheduling aims at minimizing the energy consumed during the execution of the target application. Obviously, it makes better sense only if it is coupled with some performance bound to achieve. For instance, whenever static energy can be neglected, the optimal solution always is to run each processor at the slowest possible speed. In the following, we do neglect static energy and discuss how to minimize dynamic energy consumption when executing a small task graph onto processors.

Consider an application with four tasks of costs w 1 = 3, w 2 = 2, w 3 = 1 and w 4 = 2, and three precedence constraints, as shown in Figure 1. 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 deadline on the execution time is D = 1.5.

We set the minimum and maximum speeds to s min = 0 and s max = 6 for the CONTINUOUS model. For the DISCRETE and VDD-HOPPING models, we use the set of speeds s 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 that minimize the energy consumption.

With the CONTINUOUS model, the optimal speeds are non rational values, and we obtain: , 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).

s 1 = 2 3 (3 + 35
For the DISCRETE model, if we execute all tasks at speed s

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 3.3.2), and the solution was found by performing an exhaustive search.

With the VDD-HOPPING model, we set s 1 = s (d) 2

= 5; for the other tasks, we run part of the time at speed 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 3.3.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 that are more appropriate for this example.

Minimizing the energy of a schedule

In this section, 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. We give the main complexity results without proofs (refer to [START_REF] Aupy | Reclaiming the energy of a schedule: models and algorithms[END_REF] for details).

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 DIS-CRETE and INCREMENTAL models (by definition). For the VDD-HOPPING model, we reformulate the problem in Section 3.3.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:

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 .

The CONTINUOUS model

With the CONTINUOUS model, processor speeds can take any value between s min and s max . We assume for simplicity that s min = 0, i.e., there is no minimum speed. First we prove that, with this model, the processors do not change their speed during the execution of a task:

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.

We derive in Section 3.2.1 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 2.2). Finally, we formulate the problem for general DAGs as a convex optimization program in Section 3.2.2.

Special execution graphs

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 = w i D .
If there is a task T i such that s i > s max , then the problem has no solution.

Consider now the problem with a 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.

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.

Finally, consider 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 = w i D , with D = D -w 0 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 .
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 • w i ( n i=1 w 3 i ) 1 3
.

Corollary 3 (equivalent tasks 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 (eq) 0

of weight w

(eq) 0 = n i=1 w 3 i 1 3
+w 0 , because the minimum energy consumption of both graphs are identical: minE(G, D)=minE(G (eq) , D).

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 [10, 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 deadline). Still, we can always solve the problem numerically and get fixed-size numbers that are good approximations of the optimal values.

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 3.3.1. Then, we give NP-completeness and approximation results in Section 3.3.2, for the DIS-CRETE 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; • ∀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 and approximation results

Theorem 3. With the INCREMENTAL model (and hence the

DISCRETE model), MINENERGY(G, D) is NP-complete.
Next 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.

+ δ s min ) 2 (1 + 1 K ) 2
, in a time polynomial in the size of the instance and in K.

Proposition 3.

• For any integer δ > 0, any instance of MINENERGY(G, D) with the CON-TINUOUS model can be approximated within a factor (1 + δ s min ) 2 in the INCREMENTAL model with speed increment δ.

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

Final remarks

In this section, 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. 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 speeds optimally. While computing optimal speeds is NP-hard with discrete speeds, it has polynomial complexity when mixing speeds. Intuitively, the VDD-HOPPING approach allows for smoothing out the discrete nature of the speeds. 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 speeds are regularly spaced. Such a model can be made arbitrarily efficient, according to our approximation results. Altogether, these results have laid the theoretical foundations for a comparative study of energy models.

Replica placement

In this section, we revisit the well-known replica placement problem in tree networks [START_REF] Cidon | Optimal allocation of electronic content[END_REF][START_REF] Wu | Optimal replica placement in hierarchical Data Grids with locality assurance[END_REF][START_REF] Benoit | Replica placement and access policies in tree networks[END_REF], with two new objectives: reusing pre-existing replicas, and enforcing an efficient power management. In a nutshell, the replica placement problem is the following: we are given a tree-shaped network where clients are periodically issuing requests to be satisfied by servers. The clients are known (both their position in the tree and their number of requests), while the number and location of the servers are to be determined. A client is a leaf node of the tree, and its requests can be served by one internal node. Note that the distribution tree (clients and nodes) is fixed in the approach. This key assumption is quite natural for a broad spectrum of applications, such as electronic, ISP, or VOD service delivery (see [START_REF] Kalpakis | Optimal placement of replicas in trees with read, write, and storage costs[END_REF][START_REF] Cidon | Optimal allocation of electronic content[END_REF][START_REF] Liu | Optimal placement of replicas in data grid environments with locality assurance[END_REF] and additional references in [START_REF] Wu | Optimal replica placement in hierarchical Data Grids with locality assurance[END_REF]). The root server has the original copy of the database but cannot serve all clients directly, so a distribution tree is deployed to provide a hierarchical and distributed access to replicas of the original data.

In the original problem, there is no replica before execution; when a node is equipped with a replica, it can process a number of requests, up to its capacity limit. Nodes equipped with a replica, also called servers, serve all the clients located in their subtree (so that the root, if equipped with a replica, can serve any client). The rule of the game is to assign replicas to nodes so that the total number of replicas is minimized. This problem is well understood: it can be solved in time O(N 2 ) (dynamic programming algorithm of [START_REF] Cidon | Optimal allocation of electronic content[END_REF]), or even in time O(N log N ) (optimized greedy algorithm of [START_REF] Wu | Optimal replica placement in hierarchical Data Grids with locality assurance[END_REF]), where N is the number of nodes.

We study in this section a more realistic model of the replica placement problem, for a dynamic setting and accounting for the energy consumption. The first contribution is to tackle the replica placement problem when the tree is equipped with pre-existing replicas before execution. This extension is a first step towards dealing with dynamic replica management: if the number and location of client requests evolve over time, the number and location of replicas must evolve accordingly, and one must decide how to perform a configuration change (at what cost?) and when (how frequently reconfigurations should occur?).

Another contribution of this section is to extend replica placement algorithms to cope with power consumption constraints. Minimizing the total power consumed by the servers has recently become a very important objective, both for economic and environmental reasons [START_REF] Mills | The internet begins with coal[END_REF]. To help reduce power dissipation, processors equipped with Dynamic Voltage and Frequency Scaling technique are used, and we assume that they follow the DISCRETE model. An important result of this section is that minimizing power consumption is an NP-complete problem, independently of the incurred cost (in terms of new and pre-existing servers) of the solution. In fact, this result holds true even without pre-existing replicas, and without static power: balancing server speeds across the tree already is a hard combinatorial problem.

The cost of the best power-efficient solution may indeed be prohibitive, which calls for a bi-criteria approach: minimizing power consumption while enforcing a threshold cost that cannot be exceeded. We investigate the case where there is only a fixed number of speeds and show that there are polynomial-time algorithms capable of optimizing power for a bounded cost, even with pre-existing replicas, with static power and with a complex cost function. This result has a great practical significance, because state-of-the-art processors can only be operated with a restricted number of voltage levels, hence with a few speeds [START_REF]Intel XScale technology[END_REF][START_REF] Hotta | Profile-based optimization of power performance by using dynamic voltage scaling on a pc cluster[END_REF].

Finally, we run simulations to show the practical utility of our algorithms, de-spite their high worst-case complexity. We illustrate the impact of taking preexisting servers into account, and how power can be saved thanks to the optimal bi-criteria algorithm. The rest of the section is organized as follows. Section 4.1 is devoted to a detailed presentation of the target optimization problems, and provides a summary of new complexity results. The next two sections are devoted to the proofs of these results: Section 4.2 deals with computing the optimal cost of a solution, with pre-existing replicas in the tree, while Section 4.3 addresses all power-oriented problems. We report the simulation results in Section 4.4. Finally, we state some concluding remarks in Section 4.5.

Framework

This section is devoted to a precise statement of the problem. We start with the general problem without power consumption constraints, and next we recall the DISCRETE model of power consumption. Then we state the objective functions (with or without power), and the associated optimization problems. Finally we give a summary of all complexity results that we provide in the section.

Replica servers

We consider a distribution tree whose nodes are partitioned into a set of clients C, and a set of N nodes, N . The clients are leaf nodes of the tree, while N is the set of internal nodes. Each client i ∈ C (leaf of the tree) is sending r i requests per time unit to a database object. Internal nodes equipped with a replica (also called servers) will process all requests from clients in their subtree. An internal node j ∈ N may have already been provided with a replica, and we let E ⊆ N be the set of pre-existing servers. Servers in E will be either reused or deleted in the solution. Note that it would be easy to allow client-server nodes which play both the rule of a client and of a node (possibly a server), by dividing such a node into two distinct nodes in the tree.

Without power consumption constraints, the problem is to find a solution, i.e., a set of servers capable of handling all requests, that minimizes some cost function. We formally define a valid solution before detailing its cost. We start with some notations. Let r be the root of the tree. If j ∈ N , then children j ⊆ N ∪ C is the set of children of node j, and subtree j ⊆ N ∪ C is the subtree rooted in j, excluding j. A solution is a set R ⊆ N of servers. Each client i is assigned a single server server i ∈ R that is responsible for processing all its r i requests, and this server is restricted to be the first ancestor of i (i.e., the first node in the unique path that leads from i up to the root r) equipped with a server (hence the name closest for the request service policy). Such a server must exist in R for each client. In addition, all servers are identical and have a limited capacity, i.e., they can process a maximum number W of requests. Let req j be the number of requests processed by j ∈ R. The capacity constraint writes

∀j ∈ R, req j = i∈C | j=serveri r i ≤ W. (3)
Now for the cost function, because all servers are identical, the cost of operating a server can be normalized to 1. When introducing a new server, there is an additional cost create, so that running a new server costs 1 + create while reusing a server in E only costs 1. There is also a deletion cost delete associated to deleting each server in E that is not reused in the solution. Let E = |E| be the number of pre-existing servers. Let R = |R| be the total number of servers in the solution, and e = |R ∩ E| be the number of reused servers. Altogether, the cost is

cost(R) = R + (R -e) × create + (E -e) × delete. (4)
This cost function is quite general. Because of the create and delete costs, priority is always given to reusing pre-existing servers. If create + 2 × delete < 1, priority is given to minimizing the total number of servers R: indeed, if this condition holds, it is always advantageous to replace two pre-existing servers by a new one (if capacities permit).

With power consumption

With power consumption constraints, we assume that servers may operate under a set M = {W 1 , . . . , W M } of different speeds, depending upon the number of requests that they have to process per time unit. Here speeds are indexed according to increasing values, and W M = W , the maximal capacity. If a server j ∈ R processes req j requests, with W i-1 < req j ≤ W i , then it is operated at speed W i , and we let speed(j) = i. The power consumption of a server j ∈ R obeys the DISCRETE model P(j) = P (static) + W 3 speed(j) . The total power consumption P(R) of the solution is the sum of the power consumption of all server nodes:

P(R) = j∈R P(j) = R × P (static) + j∈R W 3 speed(j) . (5)
With different power speeds, it is natural to refine the cost function, and to include a cost for changing the speed of a pre-existing server (upgrading it to a higher speed, or downgrading it to a lower speed). In the most detailed model, we would introduce create i , the cost for creating a new server operated at speed W i , changed i,i , the cost for changing the speed of a pre-existing server from W i to W i , and delete i , the cost for deleting a pre-existing server operated at speed W i .

Note that it is reasonable to let changed i,i = 0 (no change); values of changed i,i with i < i correspond to upgrade costs, while values with i < i correspond to downgrade costs. In accordance with these new cost parameters, given a solution R, we count the number of servers as follows:

• n i , the number of new servers operated at speed W i ;

• e i,i , the number of reused pre-existing servers whose operation speeds have changed from W i to W i ; and • k i , the number of pre-existing server operated at speed W i that have not been reused. The cost of the solution R with a total of R =

M i=1 n i + M i=1 M i =1 e i,i servers becomes: cost(R) = R + M i=1 create i × n i + M i=1 delete i × k i + M i=1 M i =1 changed i,i × e i,i . (6)
Of course, this complicated cost function can be simplified to make the model more tractable; for instance all creation costs create i can be set identical, all deletion costs delete i can be set identical, all upgrade and downgrade values changed i,i can be set identical, and the latter can even be neglected.

Objective functions

Without power consumption constraints, the objective is to minimize the cost, as defined by Equation (4). We distinguish two optimization problems, either with pre-existing replicas in the tree or without:

• MINCOST-NOPRE, the classical cost optimization problem [START_REF] Cidon | Optimal allocation of electronic content[END_REF] without pre-existing replicas. Indeed, in that case, Equation ( 4) reduces to finding a solution with the minimal number of servers. • MINCOST-WITHPRE, the cost optimization problem with pre-existing replicas. With power consumption constraints, the first optimization problem is MIN-POWER, which stands for minimizing power consumption, independently of the incurred cost. But the cost of the best power-efficient solution may indeed be prohibitive, which calls for a bi-criteria approach: MINPOWER-BOUNDEDCOST is the problem to minimize power consumption while enforcing a threshold cost that cannot be exceeded. This bi-criteria problem can be declined in two versions, without pre-existing replicas (MINPOWER-BOUNDEDCOST-NOPRE) and with pre-existing replicas (MINPOWER-BOUNDEDCOST-WITHPRE).

Summary of results

In this section, we prove the following complexity results for a tree with N nodes: Theorem 5. MINCOST-WITHPRE can be solved in polynomial time with a dynamic programming algorithm whose worst case complexity is O(N 5 ). Theorem 6. MINPOWER is NP-complete.

Theorem 7. With a constant number M of speeds, both versions of MINPOWER-BOUNDEDCOST can be solved in polynomial time with a dynamic programming algorithm. The complexity of this algorithm is O(N 2M +1 ) for MINPOWER-BOUNDEDCOST-NOPRE and O(N 2M 2 +2M +1 ) for MINPOWER-BOUNDEDCOST-WITHPRE.

Note that MINPOWER remains NP-complete without pre-existing replicas, and without static power: the proof of Theorem 6 (see Section 4.3.2) shows that balancing server speeds across the tree already is a hard combinatorial problem. On the contrary, with a fixed number of speeds, there are polynomial-time algorithms capable of optimizing power for a bounded cost, even with pre-existing replicas, with static power and with a complex cost function. These algorithms can be viewed as pseudo-polynomial solutions to the MINPOWER-BOUNDEDCOST problems.

Complexity results: update strategies

In this section, we focus on the MINCOST-WITHPRE problem: we need to update the set of replicas in a tree, given a set of pre-existing servers, so as to minimize the cost function.

In Section 4.2.1, we show on an illustrative example that the strategies need to trade-off between reusing resources and load-balancing requests on new servers: the greedy algorithm proposed in [START_REF] Wu | Optimal replica placement in hierarchical Data Grids with locality assurance[END_REF] for the MINCOST-NOPRE problem is no longer optimal. We provide in Section 4.2.2 a dynamic programming algorithm that returns the optimal solution in polynomial time, and we prove its correctness.

Running example

We consider the example of Figure 2(a). There is one pre-existing replica in the tree at node B, and we need to decide whether to reuse it or not. For taking decisions locally at node A, the trade-off is the following: • either we remove server B and place a new server at node C, hence having only 4 requests going up in the tree from node A;

• either we keep the replica at node B and add one at node A or C, thereby having no traversing request any more.

The choice cannot be made locally, since it depends upon the remainder of the tree: if the root r has two client requests, then it was better to keep the pre-existing server B. However, if it has four requests, two new servers are needed to satisfy all requests, and one can then remove server B which becomes useless (i.e., keep one server at node C and one server at node r).

From this example, it seems very difficult to design a greedy strategy to minimize the solution cost, while accounting for pre-existing replicas. We propose in the next section a dynamic programming algorithm that solves the MINCOST-WITHPRE problem.

Dynamic programming algorithm

Let W be the total number of requests that a server can handle, and r i the number of requests issued by client i ∈ C.

At each node j ∈ N , we fill a table of maximum size (E + 1) × (N -E + 1) which indicates, for exactly 0 ≤ e ≤ E existing servers and 0 ≤ n ≤ N -E new servers in the subtree rooted in j (excluding j), the solution which leads to the minimum number of requests that have not been processed in the subtree. This solution for (e, n) values at node j is characterized by the minimum number of requests that is obtained, minr j (e,n) , and by the number of requests processed at each node j ∈ subtree j , req j (e,n) (j ). Note that each entry of the table has a maximum size O(N ) (in particular, this size is reached at the root of the tree). The req variables ensure that it is possible to reconstruct the solution once the traversal of the tree is complete.

First, tables are initialized to default values (no solution). We set minr j (e,n) = W + 1 to indicate that there is no solution, because in any valid solution, we have minr j (e,n) ≤ W . The main algorithm then fills the tables while performing a bottom-up traversal of the tree, and the solution can be found within the table of the root node. Initially, we fill the table for nodes j which have only client nodes: minr j (0,0) = i∈children j ∩C r i , and minr j (k,l) = W + 1 for k > 0 or l > 0. There are no nodes in the subtree of j, thus no req variables to set. The variable client(j) keeps track of the number of requests directly issued by a client at node j. Also, recall that the decision whether to place a replica at node j or not is not accounted for in the table of j, but when processing the parent of node j.

Then, for a node j ∈ N , we perform the same initialization, before processing children nodes one by one. To process child i of node j, first, we copy the current table of node j into a temporary one, with values tminr and treq. Note that the table is initially almost empty, but this copy is required since we process children one after the other, and when we merge the k th children node of j, the table of j already contains information from the merge with the previous k-1 children nodes. Then, for 0 ≤ e ≤ E and 0 ≤ n ≤ N -E, we need to compute the new minr j (e,n) , and to update the req j (e,n) values. We try all combinations with e existing replicas and n new replicas in the temporary table (i.e., information about children already processed), e -e existing replicas and n -n new replicas in the subtree of child i. We furthermore try solutions with a replica placed at node i, and we account for it in the value of e if i ∈ E (i.e., for a given value e , we place only e -e -1 replica in the subtree of i, plus one on i); otherwise we account for it in the value of n. Each time we find a solution which is better than the one previously in the table (in terms of minr), we copy the values of req from the temporary table and the table of i, in order to retain all the information about the current best solution. The key of the algorithm resides in the fact that during this merging process, the optimal solution will always be one which lets the minimum of requests pass through the subtree (see Lemma 2).

The solution to the replica placement problem with pre-existing servers MINCOST-WITHPRE is computed by scanning all solutions in order to return a valid one of minimum cost. To prove that the algorithm returns an optimal solution, we show first that the solutions that are discarded while filling the tables, never lead to a better solution than the one that is finally returned: Lemma 2. Consider a subtree rooted at node j ∈ N . If an optimal solution uses e pre-existing servers and places n new servers in this subtree, then there exists an optimal solution of same cost, for which the placement of these servers minimizes the number of requests traversing j.

Proof. Let R opt be the set of replicas in the optimal solution with (e, n) servers (i.e., e pre-existing and n new in subtree j ). We denote by rmin the minimum number of requests that must traverse j in a solution using (e, n) servers, and by R loc the corresponding (local) placement of replicas in subtree j .

If R opt is such that more than rmin requests are traversing node j, we can build a new global solution which is similar to R opt , except for the subtree rooted in j for which we use the placement of R loc . The cost of the new solution is identical to the cost of R opt , therefore it is an optimal solution. It is still a valid solution, since R loc is a valid solution and there are less requests than before to handle in the remaining of the tree (only rmin requests traversing node j).

This proves that there exists an optimal solution which minimizes the number of requests traversing each node, given a number of pre-existing and new servers.

The algorithm computes all local optimal solutions for all values (e, n). During the merge procedure, we try all possible numbers of pre-existing and new servers in each subtree, and we minimize the number of traversing requests, thus finding an optimal local solution. Thanks to Lemma 2, we know that there is a global optimal solution which builds upon these local optimal solutions.

We can show that the execution time of this algorithm is in O(N × (N -E + 1) 2 × (E + 1) 2 ), where N is the total number of nodes, and E is the number of pre-existing nodes. This corresponds to the N calls to the merging procedure. The algorithm is therefore of polynomial complexity, at most O(N 5 ) for a tree with N nodes. This concludes the proof of Theorem 5. For a formalization of the algorithm and the details about its execution time, please refer to [START_REF] Benoit | Power-aware replica placement and update strategies in tree networks[END_REF].

Complexity results with power

In this section, we tackle the MINPOWER and MINPOWER-BOUNDEDCOST problems. First in Section 4.3.1, we use an example to show why minimizing the number of requests traversing the root of a subtree is no longer optimal, and we illustrate the difficulty to take local decisions even when restricting to the simpler mono-criterion MINPOWER problem. Then in Section 4.3.2, we prove the NP-completeness of the latter problem with an arbitrary number of speeds (Theorem 6). However, we propose a pseudo-polynomial algorithm to solve the problem in Section 4.3.3. This algorithm turns out to be polynomial when the number of speeds is constant, hence usable in a realistic setting with two or three speeds (Theorem 7).

Running example

Consider the example of Figure 2(b). There are two speeds, W 1 = 7 and W 2 = 10, and we focus on the power minimization problem. We assume that the power consumption of a node running at speed W i is 400 + W 3 i , for i = 1, 2 (400 is the static power). We consider the subtree rooted in A. Several decisions can be taken locally:

• place a server at node A, running at speed W 2 , hence minimizing the number of traversing requests. Another solution without traversing requests is to have two servers, one at node B and one at node C, both running at speed W 1 , but this would lead to a higher power consumption, since 800 + 2 × 7 3 > 400 + 10 3 ;

• place a server running at speed W 1 at node C, thus having 3 requests going through node A.

The choice cannot be made greedily, since it depends upon the rest of the tree: if the root r has four client requests, then it is better to let some requests through (one server at node C), since it optimizes power consumption. However, if it has ten requests, it is necessary to have no request going through A, otherwise node r is not able to process all its requests.

From this example, it seems very hard to design a greedy strategy to minimize the power consumption. Similarly, if we would like to reuse the algorithm of Section 4.2 to solve the MINPOWER-BOUNDEDCOST-WITHPRE bi-criteria problem, we would need to account for speeds. Indeed, the best solution of subtree A with one server is no longer always the one that minimizes the number of requests (in this case, placing one server on node A), since it can be better for power consumption to let three requests traverse node A and balance the load upper in the tree.

We prove in the next section the NP-completeness of the problem, when the number of speeds is arbitrary. However, we can adapt the dynamic programming algorithm, which becomes exponential in the number of speeds, but hence remains polynomial for a constant number of speeds (see Section 4.3.3).

NP-completeness of MINPOWER

In this section, we prove Theorem 6, i.e., the NP-completeness of the MINPOWER problem, even with no static power, when there is an arbitrary number of speeds.

Proof of Theorem 6. We consider the associated decision problem: given a total power consumption P, is there a solution that does not consume more than P?

First, the problem is clearly in NP: given a solution, i.e., a set of servers, and the speed of each server, it is easy to check in polynomial time that no capacity constraint is exceeded, and that the power consumption meets the bound.

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 2 , . . . , a n , does there exist a subset I of {1, . . . , n} such that i∈I a i = i / ∈I a i ? Let S = n i=1 a i ; we assume that S is even (otherwise there is no solution). We build an instance I 2 of our problem where each server has n + 2 speeds. We assume that the a i 's are sorted in increasing order, i.e., a 1 ≤ • • • ≤ a n . The speeds are then, in increasing order:

• W 1 = K; • ∀1 ≤ i ≤ n, W i+1 = K + a i × X; • W n+2 = K + S × X;
where the values of K and X will be determined later.

We furthermore set that there is no static power, and the power consumption for a server running at capacity W i is therefore P i = W 3 i . The idea is to have K large and X small, so that we have an upper bound on the power consumed by a server running at capacity W i+1 , for 1 ≤ i ≤ n:

W 3 i+1 = (K + a i × X) 3 ≤ K 3 + a i + 1 n . (7)
To ensure that Equation ( 7) is satisfied, we set

X = 1 3 × K 2 ,
and then we have

(K + a i × X) 3 = K 3 (1 + a i
3K 3 ) 3 , with K > S and therefore

a i 3K 3 < 1.
We set x i = a i 3K 3 , and we want to ensure that:

(1 + x i ) 3 ≤ 1 + 3 × x i + 1 n × K 3 . (8)
To do so, we study the function

f (x) = (1 + x) 3 -(1 + 3 × x) -5x 2 ,
and we show that f (x) ≤ 0 for x ≤ 1 2 (thanks to the term in -5x 2 ). We have f (0) = 0, and f (x) = 3(1 + x) 2 -3 -10x. We have f (0) = 0, and f (x) = 6(1 + x) -10. For x ≤ 1 2 , f (x) < 0. We deduce that f (x) is non increasing for x ≤ 1 2 , and since f (0) = 0, f (x) is negative for x ≤ 1 2 . Finally, f (x) is non increasing for x ≤ 1 2 , and since f (0) = 0, we have

(1 + x) 3 < (1 + 3 × x) + 5x 2 for x ≤ 1 2 . Equation (8) is therefore satisfied if 5x 2 i ≤ 1 n×K 3 , i.e., K 3 ≥ 5a 2 i ×n 3 2 . This condition is satisfied for K = n × S 2 ,
and we then have x i < 1 2 , which ensures that the previous reasoning was correct. Finally, with these values of K and X, Equation ( 7) is satisfied.

Then, the distribution tree is the following: the root node r has one client with K + S 2 × X requests, and n children A 1 , . . . , A n . Each node A i has a client with a i × X requests, and a children node B i which has K requests. Figure 3 illustrates the instance of the reduction.

Finally, we ask if we can find a placement of replicas with a maximum power consumption of:

P max = (K + S × X) 3 + n × K 3 + S 2 + n -1 n .
Clearly, the size of I 2 is polynomial in the size of I 1 , since K and X are of polynomial size. We now show that I 1 has a solution if and only if I 2 does.

Let us assume first that I 1 has a solution, I. The solution for I 2 is then as follows: there is one server at the root, running at capacity W n+2 . Then, for i ∈ I, we place a server at node A i running at capacity W 1+i , while for i / ∈ I, we place a server at node B i running at capacity W 1 . It is easy to check that all capacity constraints are satisfied for nodes A i and B i . At the root of the tree, there are K + S 2 × X + i / ∈I a i × X, which sums up to K + S × X. The total power consumption is then P = (K + S × X) 3 + i∈I (K + a i × X) 3 + i / ∈I K 3 . Thanks to Equation ( 7), P ≤ (K + S × X) 3

+ i∈I K 3 + a i + 1 n + i / ∈I K 3 , and finally, P ≤ (K + S × X) 3 + n × K 3 + i∈I a i + n-1
n . Since I is a solution to 2-Partition, we have P ≤ P max . Finally, I 2 has a solution.

Suppose now that I 2 has a solution. There is a server at the root node r, which runs at speed W n+2 , since this is the only way to handle its K + S 2 × X requests. This server has a power consumption of (K +S ×X) 3 . Then, there cannot be more than n other servers. Indeed, if there were n + 1 servers, running at the smallest speed W 1 , their power consumption would be (n + 1)K 3 , which is strictly greater than n × K 3 + S 2 + 1. Therefore, the power consumption would exceed P max . So, there are at most n extra servers.

Consider that there exists i ∈ {1, . . . , n} such that there is no server, neither on A i nor on B i . Then, the number of requests at node r is at least 2K; however, 2K > W n+2 , so the server cannot handle all these requests. Therefore, for each i ∈ {1, . . . , n}, there is exactly one server either on A i or on B i . We define the set I as the indices for which there is a server at node A i in the solution. Now we show that I is a solution to I 1 , the original instance of 2-Partition.

First, if we sum up the requests at the root node, we have:

K + S 2 × X + i / ∈I a i × X ≤ K + S × X.
Therefore, i / ∈I a i ≤ S 2 . Now, if we consider the power consumption of the solution, we have:

(K + S × X) 3 + i∈I (K + a i × X) 3 + i / ∈I K 3 ≤ P max .
Let us assume that i∈I a i > S 2 . Since the a i are integers, we have i∈I

a i ≥ S 2 + 1. It is easy to see that (K + a i × X) 3 > K 3 + a i . Finally, i∈I (K + a i × X) 3 + i / ∈I K 3 ≥ n × K 3 + i∈I a i ≥ n × K 3 + S 2 + 1.
This implies that the total power consumption is greater than P max , which leads to a contradiction, and therefore i∈I a i ≤ S 2 . We conclude that i / ∈I a i = i∈I a i = S 2 , and so the solution I is a 2-Partition for instance I 1 . This concludes the proof.

A pseudo-polynomial algorithm for MINPOWER-BOUNDEDCOST

In this section, we sketch how to adapt the algorithm of Section 4.2 to account for power consumption. As illustrated in the example of Section 4.3.1, the current algorithm may lead to a non-optimal solution for the power consumption if used only with the higher speed for servers. Therefore, we refine it and compute, in each subtree, the optimal solution with, for 1 ≤ j, j ≤ M ,

• exactly n j new servers running at speed W j ;

• exactly e j,j pre-existing servers whose operation speeds have changed from W j to W j .

Recall that we previously had only two parameters, N the number of new servers, and E the number of pre-existing servers, thus leading to a total of (N -E + 1) 2 × (E + 1) 2 iterations for the merging. Now, the number of iterations is (N -E + 1) 2M × (E + 1) 2M 2 , since we have 2 × M loops of maximum size N -E + 1 over the n j and n j , and 2 × M 2 loops of maximum size E + 1 over the e j,j and e j,j .

The new algorithm is similar, except that during the merge procedure, we must consider the type of the current node that we are processing (existing or not), and furthermore set it to all possible speeds: we therefore add a loop of size M . The principle is similar, except that we need to have larger tables at each node, and to iterate over all parameters. The complexity of the N calls to this procedure is now in

O(N × M × (N -E + 1) 2M × (E + 1) 2M 2 ).
Of course, we need also to update the initialization and main procedures to account for the increasing number of parameters. For the algorithm, first we compute all costs, accounting for the cost of changing speeds, and then we scan all solutions, and return one whose cost is not greater than the threshold, and which minimizes the power consumption. The most time-consuming part of the algorithm is still the call to the merging procedure, hence a complexity in

O(N × M × (N -E + 1) 2M × (E + 1) 2M 2 ).
With a constant number of capacities, this algorithm is polynomial, which proves Theorem 7. For instance, with M = 2, the worst case complexity is O(N 13 ). Without pre-existing servers, this complexity is reduced to O(N 5 ).

Simulations

In this section, we compare our algorithms with the algorithms of [START_REF] Wu | Optimal replica placement in hierarchical Data Grids with locality assurance[END_REF], which do not account for pre-existing servers and for power consumption. First in Section 4.4.1, we focus on the impact of pre-existing servers. Then we consider the power consumption minimization criterion in Section 4.4.2. Note that experiments have been run sequentially on an Intel Xeon 5250 processor.

Impact of pre-existing servers

In this set of experiments, we randomly build a set of distribution trees with N = 100 internal nodes of maximum capacity W = 10. Each internal node has between 6 and 9 children, and clients are distributed randomly throughout the tree: each internal node has a client with a probability 0.5, and this client has between 1 and 6 requests.

In the first experiment, we draw 200 random trees without any existing replica in them. Then we randomly add 0 ≤ E ≤ 100 pre-existing servers in each tree. Finally, we execute both the greedy algorithm (GR) of [START_REF] Wu | Optimal replica placement in hierarchical Data Grids with locality assurance[END_REF], and the algorithm of Section 4.2 (DP) on each tree, and since both algorithms return a solution with the minimum number of replicas, the cost of the solution is directly related to the number of pre-existing replicas that are reused. Figure 4(a) shows the average number of pre-existing servers that are reused in each solution over the 200 trees, for each value of the number E of pre-existing servers. When the tree has a very small (E ≈ 0) or very large (E ≈ N ) number of pre-existing replicas, both algorithms return the same solution. Still, DP achieves an average reuse of 4.13 more servers than GR, and it can reuse up to 15 more servers.

In a second experiment, we study the behavior of the algorithms in a dynamic setting, with 20 update steps. At each step, starting from the current solution, we update the number of requests per client and recompute an optimal solution with both algorithms, starting from the servers that were placed at the previous step. Initially, there are no pre-existing servers, and at each step, both algorithms obtain a different solution. However, they always reach the same total number of servers since they have the same requests; but after the first step, they may have a different set of pre-existing servers. Similarly to Experiment 1, the simulation is conducted on 200 distinct trees, and results are averaged over all trees. In Figure 5 (left), at each step, we compare the number of existing replicas in the solutions found by the two algorithms, and hence the cost of the solutions. We plot the cumulative number of servers that have been reused so far (hence accounting for all previous steps). As expected, the DP algorithm makes a better reuse of pre-existing replicas. Figure 5 (right) compares, at each step, the number of pre-existing servers reused by DP and by GR. We count the average number of steps (over 20) at which each value is reached. It occasionally happens that the greedy algorithm performs a better reuse, because it is not starting from the same set of pre-existing servers, but overall this experiment confirms the better reuse of the dynamic programming algorithm, even when the algorithms are applied on successive steps. Note however that taking pre-existing replicas into account has an impact on the execution time of the algorithm: in these experiments, GR runs in less than one second per tree, while DP takes around forty seconds per tree. Also, we point out that the shape of the trees does not seem to modify the results: we present in [START_REF] Benoit | Power-aware replica placement and update strategies in tree networks[END_REF] similar results with trees where each node has between 2 and 4 children.

With power consumption

To study the practical applicability of the bi-criteria algorithm (DP) for the MINPOWER-BOUNDEDCOST problem (see Section 4.3.3), we have implemented it with two speeds W 1 = 5 and W 2 = 10, and compared it with the algorithm in [START_REF] Wu | Optimal replica placement in hierarchical Data Grids with locality assurance[END_REF]; this algorithm does not account for power minimization, but minimizes the value of the maximal capacity W when given a cost bound. More precisely, in the experiment we try all values 5 ≤ W ≤ 10, and compute the corresponding cost and power consumption. To be fair, when a server has 5 requests or less, we operate it under the first speed W 1 . Given a bound on the cost, we keep the solution that minimizes the power consumption. We call GR this version of the algorithm in [START_REF] Wu | Optimal replica placement in hierarchical Data Grids with locality assurance[END_REF] modified for power as explained above.

We randomly build 100 trees with 50 nodes each, and we select 5 nodes as pre-existing servers. Clients have between 1 and 5 requests, so that a solution with replicas in the first speed can always be found. The cost function is such that, for any i, i ∈ {1, 2}, create i = 0.1, delete i = 0.01 and changed i,i = 0.001. The power consumed by a server in speed i is

P i = 1 10 W 3 1 + W 3 i .
In Figure 4(b), we plot the inverse of the power of a solution, given a bound on the cost (the higher the better). If the algorithm fails to find a solution for a tree, the value is 0, and we average the inverse of the power over the 100 trees, for both algorithms. For intermediate cost values, our algorithm is much better than the version of [START_REF] Wu | Optimal replica placement in hierarchical Data Grids with locality assurance[END_REF] in terms of power consumption: GR consumes in average more than 30% more power than DP, when the cost bound is between 29 and 34.

Here again, it takes more time to obtain the optimal solution with DP than to run the greedy algorithm several times: GR runs in around one second per tree, while DP takes around five minutes per tree. Also, we have performed some more experiments with slightly different parameters, but got no significant differences, as is shown in [START_REF] Benoit | Power-aware replica placement and update strategies in tree networks[END_REF], in particular with no pre-existing replicas at all.

Running time of the algorithms

Recall that the theoretical complexity of GR is of order O(N log N ) (without power and without pre-existing servers), while DP is of order O(N 5 ), both for the version with power (two speeds) but without pre-existing servers, and for the version without power but with pre-existing servers. In practice, the execution times of GR are always very small (a few milliseconds). For DP, we have plotted its execution time as a function of N (see [START_REF] Benoit | Power-aware replica placement and update strategies in tree networks[END_REF]). Run time measurements show that the experimental values have a shape in N 5 , which confirms the theoretical complexity. Moreover, our DP algorithms run in less than N 5 microseconds for reasonable values of N , which allows the use of these algorithms in practical situations.

Indeed, without power, we are able to process trees with 500 nodes and 125 pre-existing servers in 30 minutes; with power and no pre-existing server, we can process trees with 300 nodes in one hour. The algorithm with power and preexisting servers is the most time-consuming: it takes around one hour to process a tree with 70 nodes and 10 pre-existing servers.

Concluding remarks

In this section, we have addressed the problem of updating the placement of replicas in a tree network. We have provided an optimal dynamic programming algorithm whose cost is at most O(N 5 ), where N is the number of nodes in the tree. This complexity may seem high for very large problem sizes, but our implementation of the algorithm is capable of managing trees with up to 500 nodes in half an hour, which is reasonable for a large spectrum of applications (e.g., such as database updates during the night).

The optimal placement update algorithm is a first step towards dealing with dynamic replica management. When client requests evolve over time, the placement of the replicas must be updated at regular intervals, and the overall cost is a tradeoff between two extreme strategies: (i) "lazy" updates, where there is an update only when the current placement is no longer valid; the update cost is minimized, but changes in request volume and location since the last placement may well lead to poor resource usage; and (ii) systematic updates, where there is an update every time step; this leads to an optimized resource usage but encompasses a high update cost. Clearly, the rates and amplitudes of the variations of the number of requests issued by each client in the tree are very important to decide for a good update interval. Still, establishing the cost of an update is a key result to guide such a decision. When un-frequent updates are called for, or when resources have a high cost, the best solution is likely to use our optimal but expensive algorithm. On the contrary, with frequent updates or low-cost servers, we may prefer to resort to faster (but sub-optimal) update heuristics.

Our main contribution is to have provided the theoretical foundations for a single step reconfiguration, whose complexity is important to guide the design of lower-cost heuristics. Also, we have done a first attempt to take power consumption into account, in addition to usual performance-related objectives. Power consumption has become a very important concern, both for economic and environmental reasons, and it is important to account for it when designing replica placement strategies.

Even though the optimal algorithms have a high worst-case complexity, we have successfully implemented all of them, including the most time-consuming scheme capable of optimizing power while enforcing a bounded cost that includes pre-existing servers. We were able to process trees with a reasonable number of nodes.

As future work, we plan to design polynomial-time heuristics with a lower complexity than the optimal solution. The idea would be to perform some local optimizations to better load-balance the number of requests per replica, with the goal of minimizing the power consumption. These heuristics should be tuned for dedicated applications, and should (hopefully!) build upon the fundamental results (complexity and algorithms) that we have provided in this section. Finally, it would be interesting to add more parameters in the model, such as the cost of routing, or the introduction of quality of service constraints.

Checkpointing strategies

In this section, we give a motivating example of the use of the CONTINUOUS energy model introduced in Section 2. We aim at minimizing the energy consumption when executing a divisible workload under a bound on the total execution time, while resilience is provided through checkpointing. We discuss several variants of this multi-criteria problem. Given the workload W , we need to decide how many chunks to use, what are the sizes of these chunks, and at which speed each chunk is executed. Furthermore, since a failure may occur during the execution of a chunk, we also need to decide at which speed a chunk should be re-executed in the event of a failure. Using more chunks leads to a higher checkpoint cost, but smaller chunks imply less computation loss (and less re-execution) when a failure occurs. We assume that a chunk can fail only once, i.e., we re-execute each chunk at most once. Indeed, the probability that a fault would strike during both the first execution and the re-execution is negligible. The accuracy of this assumption is discussed in [START_REF] Aupy | Energyaware checkpointing of divisible tasks with soft or hard deadlines[END_REF].

Due to the probabilistic nature of failure hits, it is natural to study the expectation E(E) of the energy consumption, because it represents the average cost over many executions. As for the bound D on execution time (the deadline), there are two relevant scenarios: either we enforce that this bound is a soft deadline to be met in expectation, or we enforce that this bound is a hard deadline to be met in the worst case. The former scenario corresponds to flexible environment where task deadlines can be viewed as average response times [START_REF] Buttazzo | Soft Real-Time Systems: Predictability vs. Efficiency[END_REF], while the latter scenario corresponds to real-time environments where task deadlines are always strictly enforced [START_REF] Stankovic | Deadline Scheduling for Real-Time Systems: EDF and Related Algorithms[END_REF]. In both scenarios, we have to determine the number of chunks, their sizes, and the speed at which to execute (and possibly re-execute) every chunk. The different models are then compared through an extensive set of experiments.

Framework

First we formalize this important multi-objective problem. The general problem consists of finding n, the number of chunks, as well as the speeds for the execution and the re-execution of each chunk, both for soft and hard deadlines. We identify and discuss two important sub-cases that help tackling the most general problem instance: (i) a single chunk (the task is atomic); and (ii) re-execution speed is always identical to the first execution speed. The main notations are as follows: W is the total amount of work; s is the processor speed for first execution; σ is the processor speed for re-execution; T C is the checkpointing time; and E C is the energy spent for checkpointing.

Model

Consider first the case of a single chunk (or atomic task) of size W , denoted as SINGLECHUNK. We execute this chunk on a processor that can run at several speeds. We assume continuous speeds, i.e., the speed of execution can take an arbitrary positive real value. The execution is subject to failure, and resilience is provided through the use of checkpointing. The overhead induced by checkpointing is twofold: execution time T C , and energy consumption E C .

We assume that failures strike with uniform distribution, hence the probability that a failure occurs during an execution is linearly proportional to the length of this execution. Consider the first execution of a task of size W executed at speed s: the execution time is T exec = W/s + T C , hence the failure probability is P fail = λT exec = λ(W/s+T C ), where λ is the instantaneous failure rate. If there is indeed a failure, we re-execute the task at speed σ (which may or may not differ from s); the re-execution time is then T reexec = W/σ + T C so that the expected execution time is

E(T ) = T exec + P fail T reexec = (W/s + T C ) + λ(W/s + T C )(W/σ + T C ) . (9)
Similarly, the worst-case execution time is

T wc = T exec + T reexec = (W/s + T C ) + (W/σ + T C ) . (10)
Remember that we assume success after re-execution, so we do not account for second and more re-executions. Along the same line, we could spare the checkpoint after re-executing the last task in a series of tasks, but this unduly complicates the analysis. In [START_REF] Aupy | Energyaware checkpointing of divisible tasks with soft or hard deadlines[END_REF], we show that this model with only a single re-execution is accurate up to second order terms when compared to the model with an arbitrary number of failures that follows an Exponential distribution of parameter λ.

What is the expected energy consumed during execution? The energy consumed during the first execution at speed s is W s 2 + E C , where E C is the energy consumed during a checkpoint. The energy consumed during the second execution at speed σ is W σ 2 + E C , and this execution takes place with probability P fail = λT exec = λ(W/s + T C ), as before. Hence the expectation of the energy consumed is

E(E) = (W s 2 +E C )+λ (W/s+T C ) W σ 2 +E C . (11)
With multiple chunks (MULTIPLECHUNKS model), the execution times (worst case or expected) are the sum of the execution times for each chunk, and the expected energy is the sum of the expected energy for each chunk (by linearity of expectations).

We point out that the failure model is coherent with respect to chunking. Indeed, assume that a divisible task of weight W is split into two chunks of weights w 1 and w 2 (where w 1 +w 2 = W ). Then the probability of failure for the first chunk is P 1 fail = λ(w 1 /s + T C ) and that for the second chunk is P 2 fail = λ(w 2 /s + T C ). The probability of failure P fail = λ(W/s + T C ) with a single chunk differs from the probability of failure with two chunks only because of the extra checkpoint that is taken; if T C = 0, they coincide exactly. If T C > 0, there is an additional risk to use two chunks, because the execution lasts longer by a duration T C . Of course this is the price to pay for a shorter re-execution time in case of failure: Equation [START_REF] Benoit | Power-aware replica placement and update strategies in tree networks[END_REF] shows that the expected re-execution time is P fail T reexec , which is quadratic in W . There is a trade-off between having many small chunks (many T C 's to pay, but small re-execution cost) and a few larger chunks (fewer T C 's, but increased re-execution cost).

Optimization problems

The optimization problem is stated as follows: given a deadline D and a divisible task whose total computational load is W , the problem is to partition the task into n chunks of size w i , where n i=1 w i = W , and choose for each chunk an execution speed s i and a re-execution speed σ i in order to minimize the expected energy consumption:

E(E) = n i=1 (w i s 2 i + E C ) + λ w i s i + T C w i σ 2 i + E C ,
subject to the constraint that the deadline is met either in expectation or in the worst case:

EXPECTED-DEADLINE E(T ) = n i=1 w i s i +T C +λ w i s i +T C w i σ i +T C ≤ D HARD-DEADLINE T wc = n i=1 w i s i + T C + w i σ i + T C ≤ D
The unknowns are the number of chunks n, the sizes of these chunks w i , the speeds for the first execution s i and the speeds for the second execution σ i . We consider two variants of the problem, depending upon re-execution speeds:

• SINGLESPEED: in this simpler variant, the re-execution speed is always the same as the speed chosen for the first execution. We then have to determine a single speed for each chunk: σ i = s i for all i.

• MULTIPLESPEEDS: in this more general variant, the re-execution speed is freely chosen, and there are two different speeds to determine for each chunk.

We also consider the variant with a single chunk (SINGLECHUNK), i.e., the task is atomic and we only need to decide for its execution speed (in the SINGLE-SPEED model), or for its execution and re-execution speeds (in the MULTIPLE-SPEEDS model). We start the study in section 5.2 with this simpler problem.

With a single chunk

In this section, we consider the SINGLECHUNK model: given a non-divisible workload W and a deadline D, find the values of s and σ that minimize

E(E) = (W s 2 + E C ) + λ W s + T C W σ 2 + E C ,
subject to

E(T ) = W s + T C + λ W s + T C W σ + T C ≤ D
in the EXPECTED-DEADLINE model, and subject to

W s + T C + W σ + T C ≤ D
in the HARD-DEADLINE model. We first deal with the SINGLESPEED model, where we enforce σ = s, before moving on to the MULTIPLESPEEDS model. Note that the formal proofs of this section can be found in [START_REF] Aupy | Energyaware checkpointing of divisible tasks with soft or hard deadlines[END_REF].

SINGLESPEED model

In this section, we express E(E) as functions of the speed s. That is,

E(E)(s) = (W s 2 +E C )(1+λ(W/s+T C )).
The following result is valid for both EXPECTED-DEADLINE and HARD-DEADLINE models. Lemma 4. For any D, if T C + λT 2 C ≥ D, then there is no solution. Otherwise, the constraint on the execution time can be rewritten as s ∈ (s 0 , +∞(, where

s 0 = W 1 + 2λT C + √ 4λD + 1 2(D -T C (1 + λT C )) . ( 12
)
Proposition 4. In the SINGLESPEED model, it is possible to numerically compute the optimal solution for SINGLECHUNK as follows:

1. If T C + λT 2 C ≥ D, then there is no solution;

2. Else, the optimal speed is max(s 0 , s ).

HARD-DEADLINE

MULTIPLESPEEDS model

In this section, we consider the general MULTIPLESPEEDS model. We use the following notations:

E(E)(s, σ) = (W s 2 + E C ) + λ(W/s + T C )(W σ 2 + E C ).

EXPECTED-DEADLINE:

The execution time in the MULTIPLESPEEDS EXPECTED-DEADLINE model can be written as

E(T )(s, σ) = (W/s + T C ) + λ(W/s + T C )(W/σ + T C ).
We start by giving a useful property, namely that the deadline is always tight in the MULTIPLESPEEDS EXPECTED-DEADLINE model: Lemma 6. In the MULTIPLESPEEDS EXPECTED-DEADLINE model, in order to minimize the energy consumption, the deadline should be tight.

This lemma allows us to express σ as a function of s:

σ = λW D W s +T C -(1 + λT C ) .
Also we reduce the bi-criteria problem to the minimization problem of the singlevariable function:

s → W s 2 +E C +λ W s + T C   W   λW D W s +T C -(1 + λT C )   2 + E C   , (13)
which can be solved numerically.

HARD-DEADLINE:

In this model we have similar results as with EXPECTED-DEADLINE. The constraint on the execution time writes:

W s + T C + W σ + T C ≤ D.
Lemma 7. In the MULTIPLESPEEDS EXPECTED-DEADLINE model, in order to minimize the energy consumption, the deadline should be tight.

This lemma allows us to express σ as a function of s:

σ = W (D -2T C )s -W s
Finally, we reduce the bi-criteria problem to the minimization problem of the single-variable function:

s → W s 2 + E C + λ W s + T C W W (D -2T C )s -W s 2 + E C , (14)
which can be solved numerically.

Several chunks

In this section, we deal with the general problem of a divisible task of size W that can be split into an arbitrary number of chunks. We divide the task into n chunks of size w i such that n i=1 w i = W . Each chunk is executed once at speed s i , and re-executed (if necessary) at speed σ i . The problem is to find the values of n, w i , s i and σ i that minimize

E(E) = i w i s 2 i +E C + λ i w i s i +T C w i σ 2 i +E C , subject to i w i s i + T C + λ i w i s i + T C w i σ i + T C ≤ D
in the EXPECTED-DEADLINE model, and subject to

i w i s i + T C + i w i σ i + T C ≤ D
in the HARD-DEADLINE model. We first deal with the SINGLESPEED model, where we enforce σ i = s i , before dealing with the MULTIPLESPEEDS model. Note that the formal proofs of this section can be found in [START_REF] Aupy | Energyaware checkpointing of divisible tasks with soft or hard deadlines[END_REF].

Single speed model EXPECTED-DEADLINE:

In this section, we deal with the SINGLESPEED EXPECTED-DEADLINE model and consider that for all i, σ i = s i . Then:

E(T )(∪ i (w i , s i , s i )) = i w i s i +T C +λ i w i s i +T C 2 E(E)(∪ i (w i , s i , s i )) = i w i s 2 i +E C 1+λ w i s i +T C
Theorem 8. In the optimal solution to the problem with the SINGLESPEED EXPECTED-DEADLINE model, all n chunks are of equal size W/n and executed at the same speed s.

Thanks to this result, we know that the problem with n chunks can be rewritten as follows: find s such that

n W ns + T C + nλ W ns + T C 2 = W s + nT C + λ n W s + nT C 2 ≤ D in order to minimize n W n s 2 +E C +nλ W ns +T C W n s 2 +E C = W s 2 +nE C 1+ λ n W s +nT C .
One can see that this reduces to the SINGLECHUNK problem with the SINGLE-SPEED model (Section 5.2.1) up to the following parameter changes:

• λ ← λ n • T C ← nT C • E C ← nE C
If the number of chunks n is given, we can express the minimum speed such that there is a solution with n chunks:

s 0 (n) = W 1 + 2λT C + 4 λD n + 1 2(D -nT C (1 + λT C )) . ( 15
)
We can verify that when D ≤ nT C (1 + λn), there is no solution, hence obtaining an upper bound on n. Therefore, the two variables problem (with unknowns n and s) can be solved numerically.

HARD-DEADLINE:

In the HARD-DEADLINE model, all results still hold, they are even easier to prove since we do not need to introduce a second speed. Theorem 9. In the optimal solution to the problem with the SINGLESPEED HARD-DEADLINE model, all n chunks are of equal size W/n and executed at the same speed s.

Multiple speeds model EXPECTED-DEADLINE:

In this section, we still deal with the problem of a divisible task of size W that we can split into an arbitrary number of chunks, but using the more general MULTIPLESPEEDS model. We start by proving that all re-execution speeds are equal: Lemma 8. In the MULTIPLESPEEDS model, all re-execution speeds are equal in the optimal solution: ∃σ, ∀i, σ i = σ, and the deadline is tight.

We can now redefine

E(T )(∪ i (w i , s i , σ i )) = T (∪ i (w i , s i ), σ) E(E)(∪ i (w i , s i , σ i )) = E(∪ i (w i , s i ), σ)
Theorem 10. In the MULTIPLESPEEDS model, all chunks have the same size w i = W n , and are executed at the same speed s, in the optimal solution.

Thanks to this result, we know that the n chunks problem can be rewritten as follows: find s such that

• W s + nT C + λ n W s + nT C W σ + nT C = D • in order to minimize W s 2 + nE C + λ n W s + nT C W σ 2 + nE C
One can see that this reduces to the SINGLECHUNK MULTIPLESPEEDS EXPECTED-DEADLINE task problem where:

• λ ← λ n • T C ← nT C • E C ← nE C
and allows us to write the problem to solve as a two-parameter function:

(n, s) → W s 2 +nE C + λ n W s +nT C   W   λ n W D W s +nT C -(1+λT C )   2 +nE C   , (16)
which can be minimized numerically.

HARD-DEADLINE:

In this section, the constraint on the execution time can be written as:

i w i s i + T C + w i σ i + T C ≤ D.
Lemma 9. In the MULTIPLESPEEDS HARD-DEADLINE model with divisible chunk, the deadline should be tight.

Lemma 10. In the optimal solution, for all i, j, λ

w i s i + T C σ 3 i = λ w j s j + T C σ 3 j . Lemma 11.
If we enforce the condition that the execution speeds of the chunks are all equal, and that the re-execution speeds of the chunks are all equal, then all chunks should have same size in the optimal solution.

We have not been able to prove a stronger result than Lemma 11. However we conjecture the following result: Conjecture 1. In the optimal solution of MULTIPLESPEEDS HARD-DEADLINE, the re-execution speeds are identical, the deadline is tight. The re-execution speed is equal to σ = W (D-2nT C )s-W s. Furthermore the chunks should have the same size W n and should be executed at the same speed s. This conjecture reduces the problem to the SINGLECHUNK MULTIPLESPEEDS problem where

• λ ← λ n • T C ← nT C • E C ← nE C
and allows us to write the problem to solve as a two-parameter function:

(n, s) → W s 2 +nE C + λ n W s +nT C W W (D-2nT C )s-W s 2 +nE C (17)
which can be solved numerically.

W: 0.2 W: 1 W: 5 W: 10 q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q qq q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q qq q q q q qq q q q q q q q q q q q q q q qq qq q q q q q q qq q q qq q q q q q qq qq q q q q q q q q q q qq q q q q q q q q q q q qq q qq q q q q qq q q q q q q qq q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q qq q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q qq q q q q q q q q q q qq qq q q q q qq q q qq qq q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q qqq q q q q q q q q q q qq q q q q q q q q q q q q q q q qq q q q q q qq q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q qq q q q q qq q q q q q q q q q q q q q q qq q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q 0.25 Model (/SCSS) q q q q q q SCMSed SCMShd MCSSed MCSShd MCMSed MCMShd

Simulations

Simulation settings

We performed a large set of simulations in order to illustrate the differences between all the models studied in this paper, and to show to which extent each additional degree of freedom improves the results, i.e., allowing for multiple speeds instead of a single speed, or for multiple smaller chunks instead of a single large chunk. All these simulations are conducted under both constraint types, expected and hard deadlines. We envision reasonable settings by varying parameters within the following ranges:

• W D ∈ [0.2, 10]; • T C D ∈ [10 -4 , 10 -2 ]; • E C ∈ [10 -3 , 10 3 ]; • λ ∈ [10 -8 , 1].
In addition, we set the deadline to 1. Note that since we study W D and T C D instead W: 0.2 W: 1 W: 5 W: 10 q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q qq q q q q q q qq q q qq q q q q q q q q qq q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q qq q q q q q q q qq qq q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q 0.25 Then the next observation is that for EXPECTED-DEADLINE, with a small λ (< 10 -2 ), MULTIPLECHUNKS or MULTIPLESPEEDS models do not improve the energy ratio. This is due to the fact that, in both expressions for energy and for execution time, the re-execution term is negligible relative to the execution one, since it has a weighting factor λ. However, when λ increases, if the energy of a checkpoint is small relative to the total work (which is the general case), we can see a huge improvement (between 25% and 75% energy saving) with MULTIPLECHUNKS.

On the contrary, as expected, for small λ's, re-executing at a different speed has a huge impact for HARD-DEADLINE, where we can gain up to 75% energy when the failure rate is low. We can indeed run at around half speed during the first execution (leading to the 1/2 2 = 25% saving), and at a high speed for the second one, because the very low failure probability avoids the explosion of the expected energy consumption. For both MULTIPLECHUNKS and SINGLECHUNK, this saving ratio increases with λ (the energy consumed by the second execution cannot be neglected any more, and both executions need to be more balanced), the latter being more sensitive to λ. But the former is the only configuration where T C has a significant impact: its performance decreases with T C ; still it remains strictly better than SINGLECHUNK MULTIPLESPEEDS.

Comparison between EXPECTED-DEADLINE and HARD-DEADLINE

As before, the value of W/D does not change the energy ratios up to translations of E C . As expected, the difference between the EXPECTED-DEADLINE and HARD-DEADLINE models is very important for the SINGLESPEED variant: when the energy of the re-execution is negligible (because of the failure rate parameter), it would be better to spend as little time as possible doing the re-execution in order to have a speed as slow as possible for the first execution, however we are limited in the SINGLESPEED HARD-DEADLINE model by the fact that the re-execution time is fully taken into account (its speed is the same as the first execution, and there is no parameter λ to render it negligible).

Furthermore, when λ is minimum, MULTIPLESPEEDS consumes the same energy for EXPECTED-DEADLINE and for HARD-DEADLINE. Indeed, as expected, the λ in the energy function makes it possible for the re-execution speed to be maximal: it has little impact on the energy, and it is optimal for the execution time; this way we can focus on slowing down the first execution of each chunk. For HARD-DEADLINE, we already run the first execution at half speed, thus we cannot save more energy, even considering EXPECTED-DEADLINE instead. When λ increases, speeds of HARD-DEADLINE cannot be lowered but the expected execution time decreases, making room for a downgrade of the speeds in the EXPECTED-DEADLINE problems.

Concluding remarks

In this section, we have studied the energy consumption of a divisible computational workload on volatile platforms under the CONTINUOUS speed model. In particular, we have studied the expected energy consumption under different deadline constraints: a soft deadline (a deadline for the expected execution time), and a hard deadline (a deadline for the worst case execution time).

As stated in Section 2, the CONTINUOUS speed model is theoretically appealing, and allowed us to show mathematically, for all cases but one, that when using the MULTIPLECHUNKS model, then (i) every chunk should be equally sized; (ii) every execution speed should be equal; and (iii) every re-execution speed should also be equal. This problem remains open in the MULTIPLESPEEDS HARD-DEADLINE variant.

Through a set of extensive simulations we have shown the following: (i) when the fault parameter λ is small, for EXPECTED-DEADLINE constraints, the SIN-GLECHUNK SINGLESPEED model leads to almost optimal energy consumption. This is not true for the HARD-DEADLINE model, which accounts equally for execution and re-execution, thereby leading to higher energy consumption. Therefore, for the HARD-DEADLINE model and for small values of λ, the model of choice should be the SINGLECHUNK MULTIPLESPEEDS model, and that is not intuitive. When the fault parameter rate λ increases, using a single chunk is no longer energy-efficient, and one should focus on the MULTIPLECHUNKS MULTI-PLESPEEDS model for both deadline types.

An interesting direction for future work is to extend this study to the case of an application workflow: instead of dealing with a single divisible task, we would deal with a DAG of tasks, that could be either divisible (checkpoints can take place anytime) or atomic (checkpoints can only take place at the end of the execution of some tasks). Again, we can envision both soft or hard constraints on the execution time, and we can keep the same model with a single re-execution per chunk/task, at the same speed or possibly at a different speed. Deriving complexity results and heuristics to solve this difficult problem is likely to be very challenging, but could have a dramatic impact to reduce the energy consumption of many scientific applications.

Conclusion

In this chapter, we have discussed several energy-aware algorithms aiming at decreasing the energy consumption in data centers. We have started with a description of various energy models, ranking from the most theoretical model of continuous speeds to the more realistic discrete model. Indeed, processor speeds can be changed thanks to the DVFS technique (Dynamic Voltage and Frequency Scaling), hence decreasing energy consumption when running at a lower speed. Of course, performance should not be sacrificed for energy, and a bound on the performance should always be enforced.

We have first illustrated these models on a task graph scheduling problem where we can reclaim the energy of a schedule by running some non-critical tasks at a lower speed. Depending upon the model, the complexity of the problem varies: while several optimality results can be obtained with continuous speeds, the problem with discrete speeds is NP-hard. Through this study, we have laid the theoretical foundations for a comparative study of energy models.

We have then targeted a problem typical of data centers, namely the replica placement problem. The root server has the original copy of the database but cannot serve all clients directly, so a distribution tree is deployed to provide the clients with a hierarchical and distributed access to replicas of the original data. The problem is to decide where to place replicas, and where to serve each client. We have provided an optimal dynamic programming algorithm that works in a dynamic setting: we assume that client requests can evolve over time, and hence some replicas are already placed in the network. It is more efficient to re-use some of these replicas if possible. We have also added a criterion of power consumption to the problem, and proved the NP-completeness of this problem with a discrete energy model. In addition, some practical solutions have been proposed.

Finally, a rising concern in data centers, apart from energy consumption, is higher failure rate. We have therefore discussed checkpointing strategies, in the case of a divisible workload. Two deadline constraints have been studied: a hard deadline scenario corresponding to real-time environments where task deadlines are always strictly enforced, and a soft deadline scenario corresponding to a more flexible environment, where an average response time must be enforced. We have conducted this study under the continuous model, which enabled us to derive theoretical results: we proved that every chunk should be equally sized, and that every speed should be equal. In case of failure, we re-execute a chunk, and all re-execution speeds should also be equal.

δ.

  Admissible speeds lie in the interval [s min , s max ]. This model aims at capturing a realistic version of the DISCRETE model, where the different speeds 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.

4 Figure 1 :

 41 Figure 1: Execution graph for the example.

5 ,

 5 we obtain an energy E = 8 × 5 2 = 200. A better solution is obtained with s 1 = s which turns out to be optimal:

5 ,

 5 and part of the time at speed s (d) 1 = 2 in order to use the idle time and lower the energy consumption. T 2 is executed at speed s 2 30 (i.e., the first processor executes during time 3/5+5/6+2/30 = 1.5 = D, and all the work for T 2 is done:2 × 5/6 + 5 × 2/30 = 2 = w 2 ). T 3 is executed at speed s(d) 2 (during time 1/5), and finally T 4 is executed at speed s (d) 1 during time 0.5 and at speed s

3. 3 . 1

 31 The VDD-HOPPING model Theorem 2. With the VDD-HOPPING model, MINENERGY(G, D) can be solved in polynomial time.

Theorem 4 .

 4 With the INCREMENTAL model, for any integer K > 0, the MINENERGY(G, D) problem can be approximated within a factor (1

  (a) Reusing pre-existing replicas. (b) Minimizing power consumption.

Figure 2 :

 2 Figure 2: Examples

Figure 3 :

 3 Figure 3: Illustration of the NP-completeness proof.

3 :

 3 Power minimization.

Figure 4 :Figure 5 :

 45 Figure 4: Experiments 1 and 3.

Lemma 3 .

 3 E(E) is convex on R + . It admits a unique minimum s which can be computed numerically.EXPECTED-DEADLINE:In the SINGLESPEED EXPECTED-DEADLINE model, we denote E(T )(s) = (W/s + T C )(1 + λ(W/s + T C )) the constraint on the execution time.

:Proposition 5 .

 5 In the HARD-DEADLINE model, the bound on the execution time can be written as 2 W s + T C ≤ D. Lemma 5. In the SINGLESPEED HARD-DEADLINE model, for any D, if 2T C ≥ D, then there is no solution. Otherwise, the constraint on the execution time can be rewritten as s ∈ Let s be the solution indicated in Lemma 3. In the SINGLESPEED HARD-DEADLINE model if 2T C ≥ D, then there is no solution. Otherwise, the minimum is reached when s = max s , W D 2 -T C .

Figure 6 :

 6 Figure 6: Comparison with single chunk single speed.

Figure

  Figure Comparison hard deadline versus expected deadline.

We use the Maple software to solve numerically the different minimization problems. Results are showed from two perspectives: on the one hand (Figure 6), for a given constraint (HARD-DEADLINE or EXPECTED-DEADLINE), we normalize all variants according to SINGLESPEED SINGLECHUNK, under the considered constraint. For instance, on the plots, the energy consumed by MULTI-PLECHUNKS MULTIPLESPEEDS (denoted as MCMS) for HARD-DEADLINE is divided by the energy consumed by SINGLECHUNK SINGLESPEED (denoted as SCSS) for HARD-DEADLINE, while the energy of MULTIPLECHUNKS SINGLE-SPEED (denoted as MCSS) for EXPECTED-DEADLINE is normalized by the energy of SINGLECHUNK SINGLESPEED for EXPECTED-DEADLINE.

On the other hand (Figure 7), we study the impact of the constraint hardness on the energy consumption. For each solution form (SINGLESPEED or MULTIPLE-SPEEDS, and SINGLECHUNK or MULTIPLECHUNKS), we plot the ratio energy consumed for EXPECTED-DEADLINE over energy consumed for HARD-DEADLINE.

Note that for each figure, we plot for each function different values that depend on the different values of T C /D (hence the vertical intervals for points where T C /D has an impact). In addition, the lower the value of T C /D, the lower the Through these three case studies, we have demonstrated the importance and the complexity of proposing energy-aware solutions to problems that occur in data centers. We have provided a first step towards energy-efficient data centers by first discussing energy models, and then designing energy-efficient algorithms for some typical problems. Several research directions have been opened.