Anne Benoit

Louis-Claude Canon

Redouane Elghazi

Pierre-Cyrille Héam

List and shelf schedules for independent parallel tasks to minimize the energy consumption with discrete or continuous speeds

Scheduling independent tasks on a parallel platform is a widely-studied problem, in particular when the goal is to minimize the total execution time, or makespan (P ||C max problem in Graham's notations). Also, many applications do not consist of sequential tasks, but rather parallel tasks, either rigid, with a fixed degree of parallelism, or moldable, with a variable degree of parallelism (i.e., for which we can decide at the execution on how many processors they are executed). Furthermore, since the energy consumption of data centers is a growing concern, both from an environmental and economical point of view, minimizing the energy consumption of a schedule is a main challenge to be addressed. One can then decide, for each task, on how many processors it is executed, and at which speed the processors are operated, with the goal to minimize the total energy consumption. We further focus on co-schedules, where tasks are partitioned into shelves, and we prove that the problem of minimizing the energy consumption remains NP-complete when static energy is consumed during the whole duration of the application. We are however able to provide an optimal algorithm for the schedule within one shelf, i.e., for a set of tasks that start at the same time.

Several approximation results are derived, both with discrete and continuous speed models, and extensive simulations are performed to show the performance of the proposed algorithms.

Introduction

We consider the problem of scheduling independent tasks. Even though this problem has already been widely studied, in particular when aiming to minimize the total execution time (or makespan) for sequential tasks, there remain avenues for improvement for variants of the problem. Using the Graham notations [START_REF] Graham | Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey[END_REF], the typical problem that is studied is P ||C max , i.e., the goal is to minimize the makespan when scheduling independent sequential tasks on a set of identical processors. The decision version of this problem in its A shorter version of this paper appeared in the proceedings of SBAC-PAD'2021 under the title Shelf schedules for independent moldable tasks to minimize the energy consumption. This version contains revised proofs easier to follow, new theoretical results for continuous speeds, and additional simulation results to evaluate the performance of the algorithms. This work has been supported by the EIPHI Graduate School (contract ANR-17-EURE-0002).

* Corresponding author simplest form is already NP-complete (it is indeed identical to 2-Partition [START_REF] Garey | Computers and Intractability, a Guide to the Theory of NP-Completeness[END_REF] when considering two processors). However, several well-known heuristics lead to very good approximation algorithms, as the classical Longest Processing Time (LPT) heuristic, or even some PTAS or FPTAS algorithms [START_REF] Hochbaum | A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach[END_REF].

The problem becomes more complicated when dealing with parallel tasks. Now, each task i is a parallel task that executes concurrently on p i processors. The greedy list scheduling algorithm that gives priority to longest jobs is then known to be a 2-approximation when tasks are rigid (p i is given and fixed) [START_REF] Garey | Bounds for multiprocessor scheduling with resource constraints[END_REF].

In order to ease the scheduling, it can be useful to group tasks by shelves (or batches, packs, levels, etc.), and then the shelves are scheduled one after the other. All the tasks in a same shelf start their execution at the same time, and the next shelf starts only when all tasks of the previous shelf are done. This is typically referred to as shelf-scheduling or co-scheduling. Of course, one may then waste time, due to idle resources if tasks do not all take the same time. However, such schedules are easy to implement and they also may have some theoretical guarantees. Indeed, the list scheduling that gives priority to longest jobs is known to be a 3-approximation when imposing the use of shelves [START_REF] Turek | Approximate algorithms scheduling parallelizable tasks[END_REF] (recall that it is a 2-approximation without this restriction).

Such co-schedules are also very useful for moldable tasks, i.e., tasks whose degree of parallelism p i can be chosen at execution. For such parallel moldable tasks, an easy way to proceed is to execute tasks sequentially, each task using the whole platform. However, it may be more efficient to group tasks by shelves, since the execution profile of a task may lead to less efficiency when using many processors. While the general problem is NP-hard, Aupy et al. [START_REF] Aupy | Co-scheduling algorithms for highthroughput workload execution[END_REF] propose an optimal polynomial-time algorithm to decide the processor assignment that minimizes the makespan when there are at most two tasks in a shelf.

While most scheduling problems are focusing on makespan minimization, another core problem is the energy consumption. In order to optimize this energy consumption, modern processors can run at different speeds, and their power consumption is then the sum of a static part (the cost for a processor to be turned on) and a dynamic part, which is a strictly convex function of the processor speed. Indeed, the execution of a given amount of work costs more power if a processor runs at 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 a power of s 3 Watts [START_REF] Ishihara | Voltage scheduling problem for dynamically variable voltage processors[END_REF][START_REF] Pruhs | Speed scaling of tasks with precedence constraints[END_REF][START_REF] Chandrakasan | JouleTrack: A Web Based Tool for Software Energy Profiling[END_REF][START_REF] Aydin | Energy-aware partitioning for multiprocessor real-time systems[END_REF][START_REF] Chen | Multiprocessor energy-efficient scheduling for real-time tasks[END_REF], hence it consumes an energy of s 3 × d Joules when operated during d units of time. Faster speeds allow for a faster execution, but they also lead to a much higher (supra-linear) power consumption. A more general model states that the power can be in s α , where 2 ≤ α ≤ 3 [START_REF] Bambagini | Energy-aware scheduling for real-time systems: A survey[END_REF]. While minimizing the makespan helps reducing the energy consumption, which increases with execution time, to the best of our knowledge, no study has been aiming at minimizing the energy consumption for shelf schedules.

For the static energy consumption, it depends on the time during which processors are powered. We consider two models: in the independent model, each processor is independently powered and can be turned off when not computing, hence the static power is paid only while processors are running. However, in the simultaneous model, the platform is turned on as long as one processor is running, hence the static power must also be paid for idle processors.

Our main contributions are the following:

• We formalize the problem of scheduling independent moldable tasks to minimize energy consumption (MinE-Mold problem) with various model variants.

• We prove that the problem can be solved in polynomial time when processors are independently powered, while the problem becomes NP-complete with simultaneously powered processors.

• We establish multiple approximation ratios for both classical list scheduling algorithms, and shelf-based schedules, both with a realistic model where speeds can be chosen in a discrete set, and with the general model where speeds can take any positive real value (continuous speeds).

• We provide an optimal dynamic programming algorithm to minimize the energy consumption of a single shelf, both with the discrete and with the continuous model. The goal is to decide on how many processors to execute each task of the shelf, and at which speed to operate the task.

• We perform an empirical study and we show that, for most instances, a single speed can be used for all tasks without increasing the energy consumption. Also, as expected, shelf-based solutions consume more energy, but they are easier to implement and solutions are derived with a much lower complexity.

A comparison with solutions using continuous speeds highlights that further energy savings could be achieved by carefully choosing the processor's speeds.

We first discuss related work in Section 2. Next, we detail the model (platform, tasks, energy consumption) and schedules, and we introduce the target optimization problems in Section 3. The complexity of the problems is established in Section 4. Approximation ratios for MinE-Mold are derived in Section 5 with discrete speeds and in Section 6 with continuous speeds. Optimal algorithms for a single shelf are provided in Section 7. Finally, a comprehensive empirical study is proposed in Section 8. We conclude and give hints for future research directions in Section 9.

Related work

Although the problem of minimizing the energy consumption of parallel platforms has been extensively studied, few works propose guaranteed scheduling algorithms for moldable tasks. We first cover approximation algorithms for the problem of minimizing the makespan because our approach relies on such results, even though we rather focus on minimizing the energy consumption. We then discuss heuristics proposed for real-time systems, which consider a model slightly different than ours. Finally, we present some examples of moldable task applications.

Makespan minimization.

For the rigid case where the number of processors required by each task is fixed, classical list scheduling algorithms, denoted by ListBased, are widely used in the literature for makespan minimization. Tasks are ordered in a priority list and are then scheduled by order of priority, as presented by Garey and Graham [START_REF] Garey | Bounds for multiprocessor scheduling with resource constraints[END_REF]: any time a processor is idle, the list is scanned in order and the first task that can be executed is started. Another way to say it, the principle of the algorithm is as follows:

when resources are released, we see if a task can be started right now. If it is the case, we start it. If several tasks can be started, we take the one with the highest priority, given by an ordering of the tasks in a list.

ListBased is a 2-approximation for the makespan. More precisely, it is a 2 × max( W p , t max )-approximation, where W p is the average work and t max is the execution time of the longest task. Coffman et al. [START_REF] Coffman | Performance bounds for level-oriented two-dimensional packing algorithms[END_REF] made a landmark paper proving the approximation ratio of several shelf-based algorithms when considering rigid tasks only. They introduce the problem as a two-dimensional packing problem and focus on asymptotic performance bounds for the makespan. They show that the performance bounds of classic bin-packing heuristics Next-Fit Decreasing and First-Fit Decreasing are 3 and 2.7, respectively.

In [START_REF] Krishnamurti | An approximation algorithm for scheduling tasks on varying partition sizes in partitionable multiprocessor systems[END_REF], Krishnamurti et al. study a problem where processors are partitioned, and each task is submitted to one such partition with the objective to minimize the execution time. The number of partitions is bounded, which limits the maximum number of simultaneous tasks.

In [START_REF] Turek | Approximate algorithms scheduling parallelizable tasks[END_REF], Turek et al. study the multi-shelves problem, still for makespan minimization. They first propose an allocation strategy for rigid tasks, and then use this strategy on several "allocation candidates" for the moldable case. This first strategy involves co-schedules, ShelfBased [START_REF] Turek | Approximate algorithms scheduling parallelizable tasks[END_REF]LTF], where rigid tasks are partitioned into shelves, and all the tasks in a same shelf begin their execution at the same time (this is equivalent to Next-Fit Decreasing). Tasks are sorted in order of decreasing execution times. Then, tasks are inserted iteratively in the current shelf until the next task cannot be inserted. At this point, a new shelf is created and the process continues. A possible extension consists in allowing backfilling of previous shelves.

ShelfBased is a 3-approximation for the makespan. More precisely, it is a 2W p + t max -approximation. To deal with moldable tasks, the authors also present an overall design [START_REF] Turek | Approximate algorithms scheduling parallelizable tasks[END_REF]GF] that works as follows. First, a task and a number of processors are selected, and we assume that all tasks will complete before this one.

Then, the number of processor is chosen for all other tasks so that their work is minimized. Finally, this instance is solved as if tasks were rigid (with a fixed number of processors. All pairs of initial task and number of processors are tried. Turek et al. also designed a 2.7-approximation for the multi-shelves problem, with a fixed number of shelves [START_REF] Turek | Scheduling parallelizable tasks: Putting it all on the shelf[END_REF]. However, this algorithm is exponential in the number of shelves.

Aupy et al. go beyond the problem of minimizing the makespan, by tackling the problem of optimizing the power consumption, the makespan and the reliability [START_REF] Aupy | Energy-aware scheduling under reliability and makespan constraints[END_REF]. However, they consider dependent non-parallel tasks, which is a setting completely different from ours, since we focus on parallel tasks. They show that most problems are NP-hard and propose heuristics.

Real-time systems. Finally, several works have been proposed in the context of real-time systems with moldable tasks, power constraints and deadlines. The closest to the problem that we target considers level-based scheduling (similar to shelves) with rigid or moldable tasks [START_REF] Kong | Energy-efficient scheduling for parallel real-time tasks based on level-packing[END_REF]. They propose heuristics that extend bin-packing ones such as First-Fit Decreasing, Best-Fit Decreasing, etc. Most other works related to realtime systems propose heuristics [START_REF] Xu | Energy minimizing for parallel real-time tasks based on level-packing[END_REF][START_REF] Zahaf | Energy-efficient scheduling for moldable real-time tasks on heterogeneous computing platforms[END_REF][START_REF] Litzinger | Scheduling moldable parallel streaming tasks on heterogeneous platforms with frequency scaling[END_REF]. In this paper, we do not consider deadlines and we investigate algorithms with guarantees.

Moldable Tasks. Most distributed algorithms have a time complexity that depends on the number of processors and therefore correspond to moldable tasks. This is the case for very classical algorithms such as the Fast Fourier Transform or the product of matrices by Strassen's method. For a more recent example, one can for instance point out distributed algorithms for generating samples from a large tabular [START_REF] Sanders | Efficient parallel random sampling -vectorized, cache-efficient, and online[END_REF]. In the context of biological applications, E. Saule et al. have shown how to use moldable tasks to tackle the short sequence mapping problem [START_REF] Saule | Optimizing the stretch of independent tasks on a cluster: From sequential tasks to moldable tasks[END_REF]. Other applicative examples of moldable tasks on stream algorithms are developed in [START_REF] Keller | Integrating energy-optimizing scheduling of moldable streaming tasks with design space exploration for multiple core types on configurable platforms[END_REF].

Overall, we are not aware of any paper tackling directly the problem that we consider in this paper, namely the problem of scheduling independent moldable tasks to minimize the energy consumption, under different model variants (shelf-based solutions, discrete and continuous speeds, ...), and hence we were not able to directly compare our proposed approach to any algorithm coming from related work.

Model

We first describe the platform model (Section 3.1), the task model (Section 3.2), the energy model (Section 3.3), before formally defining general schedules, single-speed schedules and co-schedules in Section 3.4.

Finally, we introduce the target optimization problems in Section 3.5. Table 1 summarizes the main notations used throughout the paper.

Platform

The target platform consists in p identical processors, whose frequency can be scaled using DVFS (Dynamic Voltage and Frequency Scaling).

These processors have a static power P stat and a set S = {s 1 , s 2 , . . . , s k } of possible speeds (or frequencies). For convenience, we let s min = s 1 and s max = s k be the minimum and maximum speeds. Indeed, current processors have a set of predefined speeds (or frequencies), which correspond to different voltages that the processor can be subjected to [START_REF] Okuma | Software energy reduction techniques for variable-voltage processors[END_REF] (discrete model).

For the sake of completeness, we also consider the continuous model, where processors may be operated at any speed (S = R * + ). While this model is unrealistic (even though the number of available frequencies tends to be large in modern processors), it is theoretically appealing [START_REF] Bansal | Speed scaling to manage energy and temperature[END_REF]. Also, a study of the problem without a constrained set of speeds allows for a better understanding of how to choose the available speeds during the design of a processor. In our model, we don't consider the possibility of switching frequencies during the execution of a given task as it would never provide better solutions. The reason for that is that, due to the convexity of the function describing the energy consumption, taking the average speed of a task as its constant speed always incurs a lower energy consumption for the same execution time. Two different tasks, however, can be executed at different frequencies even if they are scheduled on a same processor. This remark would not necessarily remain true if we were to remove the full clairvoyance on the execution times of the tasks or if we were to add uncertainty to the energy model.

Tasks

We consider n moldable tasks {T 1 , T 2 , . . . , T n } with respective execution profiles (w i,j ) i∈ 1,n ,j∈ 1,p , where w i,j is the total work required to execute T i on j processors. The work is the total number of elementary operations to be executed by the processors. If executed at a speed of one, the time per processor is then

t i,j = wi,j j .
We assume that:

• ∀i, (t i,j ) j is non-increasing in j (the more processors there are, the less time it will take per processor);

• ∀i, (w i,j ) j is non-decreasing in j (when using more processors, there is more overhead due to the parallelization, which is a common assumption [START_REF] Blazewicz | Approximation algorithms for scheduling independent malleable tasks[END_REF][START_REF] Benoit | Resilient co-scheduling of malleable applications[END_REF]).

The algorithms presented in this paper do not require these two usual assumptions, however having them simply allows us to get better time complexities. For example, in the case where some allocations of processors are not possible for some tasks, the corresponding processing time would be infinite and both assumptions could not hold.

Furthermore, for task T

i (1 ≤ i ≤ n),
• p i is the number of allocated processors;

• s i is the speed of the processors during their execution;

• t i,pi,si = ti,p i si = wi,p i si×pi is the execution time; • a i,pi,si = t i,pi,si × p i = wi,p i si
is the area of the rectangle representing this task.

Energy consumption

The energy consumption consists first of a static part, which corresponds to the power consumed when processors are turned on. The static power is denoted P stat , and the corresponding static energy consumption on each processor is t stat × P stat , where t stat is the duration during which the processor is powered.

There is also a dynamic energy consumption, directly related to the speed s at which the processor operates, and the time t dyn spent computing (which may be equal to or smaller than the time t stat ). Using a general model, the dynamic energy consumption is t dyn × s α [START_REF] Bambagini | Energy-aware scheduling for real-time systems: A survey[END_REF], where α > 1 (in general, 2 ≤ α ≤ 3).

Hence, for task T i , the dynamic energy consumption on each processor is t i,pi,si × s α i (since t dyn = t i,pi,si ), and the total dynamic energy consumption for the task is a i,pi,si × s α i (the same energy is consumed by each of the p i processors operating task T i ).

The case where t stat = t dyn is the independent model, where each processor is independently powered, and hence turned off when it is not computing. We also consider the simultaneous model, where the whole platform remains powered as long as at least one processor is executing (t stat = C max ).

Schedules

Given a computational platform and a set of moldable tasks as described above, a schedule λ is a function that maps each task T i to a tuple (M i , s i , δ i ), where M i is the set of processors assigned to T i (hence the number of processors assigned to the task is p i = |M i |), s i is the speed of these processors to execute T i , and δ i ≥ 0 is the starting time of T i . Moreover, λ must verify the following conditions:

• There exists i such that δ i = 0 (there is a task starting at time 0);

• If tasks T i and T i (1 ≤ i, i ≤ n and i = i ) are such that M i ∩ M i = 0, then [δ i , δ i + t i,pi,si ] ∩ [δ i , δ i + t i ,p i ,s i ] = ∅ (
a processor cannot be used for two different tasks at the same time).

We also have the following aggregated quantities depending on a schedule λ:

• C max (λ) = max i {δ i + t i,pi,si } is the makespan (or total execution time);

• W (λ) = n i=1 w i,pi is the cumulative work;

• T dyn (λ) = n i=1 t i,pi,si is the cumulative execution time of all tasks;

• A dyn (λ) = n i=1 a i,pi,si is the cumulative execution time on all processors;

• A stat (λ) is the cumulative time on all processors during which they are powered. It is either A dyn (λ) in the independent model, or it is p × C max (λ) in the simultaneous model.

We can then express the total energy consumption of a schedule λ as:

E(λ) = n i=1 a i,pi,si × s α i + A stat (λ) × P stat .
If there is no ambiguity on λ, we write C max for C max (λ); and similarly for related quantities (W , T dyn , A dyn , etc.).

Finally, we pay a particular attention to two classes of particular schedules:

• Single-speed schedules are schedules such that all the speeds are equal for all tasks, i.e., for 1 ≤ i ≤ n,

s i = s ∈ S.
• Co-schedules are organized as shelves, as motivated in Section 1. A co-schedule consists of a partition of the tasks into shelves and such that:

-If two tasks are in the same shelf, then they start their execution at the same time;

-If two tasks are not in the same shelf, then one finishes its execution before the other one starts.

Optimization problems

The general problem is MinE-Mold: Given n moldable tasks, their execution profiles (w i,j ), p processors and their speeds S, the goal is to find a schedule that minimizes the total energy consumption. We focus mainly on the case with a set of discrete speeds (discrete model) and simultaneously-powered processors (simultaneous model). Variants with continuous speeds and/or independently-powered processors are referred to by adding Cont or Indep to the problem name (hence, MinE-Mold-Cont-Indep is the problem with both variants, while MinE-Mold-Indep is the problem with discrete speeds and independently-powered processors).

We also consider the variant of the problem with rigid tasks, i.e., when the speed s i and the number of processors per task p i are fixed (MinE-Rig problem), again by default with discrete speeds and the simultaneous model.

Moreover, we add SS to refer to the variant of any problem where the same speed must be selected for each task (see single-speed schedules above). Finally, since we are interested in co-schedules, we consider the more constrained problem with a single shelf, i.e., all tasks must start at time 0 and be executed concurrently. The corresponding problem is MinE-OneShelf: Given a set of n tasks and p processors, the goal is to minimize the energy consumption knowing that all tasks start at time 0 (δ i = 0 for 1 ≤ i ≤ n). Solving this particular problem will help us derive efficient co-schedules for the general MinE-Mold problem. More precisely, a solution to MinE-OneShelf

Problem Processors per task Speeds

Static area A stat Constraint MinE-Mold-Indep Variable p i ∈ N Finite set S A stat = A dyn ∅ MinE-Mold Variable p i ∈ N Finite set S A stat = p × C max ∅ MinE-Rig Fixed p i ∈ N Finite set S A stat = p × C max ∅ MinE-Mold-Cont Variable p i ∈ N Interval A stat = p × C max ∅ MinE-Rig-Cont Fixed p i ∈ N Interval A stat = p × C max ∅ MinE-OneShelf Variable p i ∈ N Finite set S A stat = p × C max n i=1 p i ≤ p
is an assignment ((p i ) i∈ 1,n , (s i ) i∈ 1,n ) such that: • ∀i ∈ 1, n , task T i is executed on p i ≥ 1 processors at speed s i ∈ S;
• n i=1 p i ≤ p (at most p processors are used, since all tasks execute concurrently).

All problems (with the multiple speed variant) are summarized in Table 2.

Problem complexity

We start with the study of the independent model, and we derive that MinE-Mold-Indep can be solved in polynomial time (Section 4.1). However, with the more realistic simultaneous model, we prove that MinE-Mold is NP-complete (Section 4.2).

Optimal algorithm for MinE-Mold-Indep

In the independent model, the platform has multiple nodes that are independently powered, which means that each node can individually be turned down at any point of the execution, and not consume any more energy. Therefore, the total energy consumption is the sum of the individual energy consumption of each task. Hence, for each task, we need to decide on how many processors it should be executed, and at which speed, in order to minimize its energy consumption. Recall that we solely focus on energy optimization, and hence we do not have any constraint on the total time to completion.

Since the (w i,j )'s are non-decreasing in j, we have a i,1,si ≤ a i,pi,si for all 1 ≤ p i ≤ p. Therefore, a i,pi,si is minimized if a single processor is used (independently of the speed that is chosen). Hence, we set p i = 1, i.e., the task is executed on a single processor (its execution time may be long, but other processors will be turned off and less energy will be consumed, since we have independently-powered processors).

We still need to decide at which speed to execute the task on its single processor. Indeed, there is a tradeoff between executing the task fast to reduce the static energy consumption of the task (the area a i,1,si , that decreases with s i ), and running at a slower speed to reduce the dynamic energy consumption, which is in s α i and hence increases with s i . The total energy consumption of the task is a i,1,si × (s α i + P stat ), and a i,1,si = wi,1 si . The goal is therefore to find s i that minimizes s α-1 i + Pstat si . The optimal value of s i (denoted by s opt i ) can then be easily found in O(|S|) if S is a set of discrete speeds, by comparing the values for every possible speed s i ∈ S. In the continuous case, we remark that the

function f : s → s α-1 i + Pstat si is a convex function that reaches its minimum at s opt i = α Pstat α-1 ,

and hence it can be found in O(1).

We can therefore optimize the energy consumption of each task independently, and execute the tasks one after the other. For each task, as shown above, we execute task i on a single processor at speed s opt i . Again, we focus solely on energy optimization, and the time to completion might be very large in this case (a single processor is used). Of course, one can also schedule the tasks on different processors and achieve the same energy consumption with a smaller total execution time since nodes are independently powered. Anyway, the optimal solution to this problem can therefore be found in polynomial time.

In the rest of this paper, unless otherwise stated, we focus on simultaneously powered processors (i.e., A stat = p × C max ). It then becomes crucial to use the whole platform and minimize the execution time, since the platform remains powered during the whole execution.

NP-completeness of MinE-Mold

When moving to the simultaneous model, it becomes crucial to also minimize the total execution time, since the static energy is consumed during the whole execution. We show that the MinE-Mold problem actually is NP-complete, even when a single speed is available. For the continuous case (MinE-Mold-Cont), the problem is also NP-hard, even though we do not know whether it is in NP or not because of the speeds in R * + . Proof. We first prove that the decision problem associated to MinE-Mold is in NP: a certificate is a schedule, i.e., the number of processors and the speed of each task, as well as the starting time of each task, and it is easy to check in polynomial time whether the bound on energy consumption is achieved. However, in the continuous case, the speeds and starting time of tasks might not be in Q, and hence we do not know whether MinE-Mold-Cont is in NP or not.

Theorem 1. The decision problems associated to

To prove the NP-hardness, we do a reduction from the problem of 3-Partition [START_REF] Garey | Computers and Intractability, a Guide to the Theory of NP-Completeness[END_REF]: Given 3n integers {a 1 , . . . , a 3n } whose sum is nB = 3n i=1 a i and with B 4 < a i < B 2 for 1 ≤ i ≤ 3n, does there exist a partition of {1, . . . , 3n} into n subsets S 1 , . . . , S n , such that i∈Sj a i = B for 1 ≤ j ≤ n?

Let I 1 be an instance of 3-Partition. We create an instance I 2 of MinE-Mold (or MinE-Mold-Cont)

with n processors, and 3n tasks that cannot be parallelized, i.e., their execution time is not improved when using more than one processor. Hence, task i (1 ≤ i ≤ 3n) is such that t i,j = a i for 1 ≤ j ≤ n. Furthermore, we have P stat = 2 and α = 3. In the discrete version of the problem, there is a single speed S = {1}. Finally, we set the bound on total energy consumption for I 2 to 3nB.

First, note that it is always better to execute each task on a single processor. Indeed, if a task is executed on more than one processor, it takes the same time to execute but consumes additional energy. Second, in the continuous case, if a single task is considered, it should be executed at speed s opt i = α Pstat α-1 as shown in Section 4.1 for the independent model, which corresponds to a speed of one since P stat = 2 and α = 3. The use of another speed leads to a higher energy consumption for this task. Hence, assuming that each task is executed at speed 1 (both in the discrete and continuous cases), we obtain a dynamic energy consumption of a i for task i, and a total dynamic energy consumption of nB. The static energy consumption depends on the total execution time t, and it is P stat × t × n. If there is no idle time, and hence no waste of static energy, the time t × n also corresponds to the total time spent executing the tasks as in the independent model, which is nB as for the dynamic energy consumption. We are now ready to prove the equivalence of solutions.

If I 1 has a solution, we execute tasks of a same subset S j onto processor j, for 1 ≤ j ≤ n. Each processor completes in time B, and the static energy consumption is 2nB, hence a total energy consumption of 3nB (static energy plus dynamic energy). Therefore, I 2 has a solution.

If I 2 has a solution, we define S j as the set of tasks executed on processor j. Since the energy consumption is not greater than 3nB, each task must be executed at speed 1 on a single processor, otherwise the sum of the energy consumption of each task (as in the independent model) would exceed 3nB, and lead to a contradiction. Indeed, the energy consumption with the simultaneous model is at least as high as the one with the independent model as it may account for extra static energy consumption due to some idle time of processors. Given that each task is executed at speed 1, the total dynamic energy consumption is nB and the static energy consumption cannot exceed 2nB. This means that the total execution time must be such that t ≤ B, and the sum of the a i 's in each subset S j cannot exceed B. Therefore, I 1 has a solution, which concludes the proof.

Approximation ratios with discrete speeds

To solve MinE-Mold, we extend a strategy [START_REF] Turek | Approximate algorithms scheduling parallelizable tasks[END_REF]GF] that transforms a moldable instance into multiple rigid ones by fixing the number of processors (and possibly the speed) of each task. Then, each rigid instance is solved with a heuristic, for example the ones that we mentioned earlier, ListBased (the classical list-based scheduling where no processor is left idle if a task can be started, which is a 2-approximation algorithm for the total execution time, or makespan) or ShelfBased (rigid tasks are partitioned into shelves, and all the tasks in a same shelf begin their execution at the same time, which is a 3-approximation algorithm for makespan).

We thus start by considering the rigid case (MinE-Rig problem) and derive approximation results for energy consumption. Moreover, we first consider a simplified version of the problem where all tasks have the same speed (Section 5.1), before moving to the general case (Section 5.2). By convention, λ opt refers to the optimal schedule that minimizes the energy consumption and λ • to the schedule at speed s • with a guaranteed bound on the energy consumption. Moreover, for a rigid instance, λ * is the schedule with minimum makespan and λ A a schedule with a guaranteed bound on the makespan.

Processors with a single speed (s i = s)

We first consider the case where the speed must be the same for all tasks, i.e., s i = s for 1 ≤ i ≤ n. The energy simplifies as:

E = n i=1 a i,pi,si × s α + A stat × P stat , with α > 1.

Rigid case

We start with the rigid case, which means that, for 1 ≤ i ≤ n, the number of processors p i for task i is fixed. Hence, the workload for task i is also known (w i,pi ). Moreover, for a given schedule λ, all the s i 's are equal to s λ . The tuple λ(i) is hence denoted as (M i , s λ , δ i ).

Given any ρ > 0, we denote by ρλ the schedule associating to each task i the tuple (M i , ρ × s λ , δi ρ ), i.e., the speed is scaled by a factor ρ, and the starting times are adjusted accordingly, without any modification in the processor allocation. One can easily check that ρλ is also a rigid single-speed schedule.

Two schedules λ 1 and λ 2 are equivalent, denoted λ 1 ∼ λ 2 , if there exists ρ > 0 such that

λ 1 = ρλ 2 . The relation ∼ is an equivalence relation. The equivalence class of λ is denoted [λ]. Recall that C max (λ) = Astat(λ) p
is the makespan: it is the total duration during which the whole system is powered. For convenience, we define the following quantity:

K [λ] = s λ × C max (λ).
It is easy to see that this is a constant for the equivalence class of λ; indeed, given any ρ > 0, C max (ρλ) =

Cmax(λ) ρ

, and s ρλ = ρ × s λ . This is used as makespan that is normalized to the speed.

The goal of this section is to prove the following theorem. The idea consists in considering algorithms with a given approximation ratio on the makespan and show how these ratios extend to the energy minimization.

In particular, we consider the same allocation as the one returned by the approximation algorithm but with a speed that minimizes the energy consumption.

Theorem 2. In the rigid single-speed context (MinE-Rig-SS) and assuming that there exists an algorithm A that yields a c-approximation of the optimal makespan, we can compute in polynomial time a schedule consuming at most c times the optimal energy.

Proof. In the rigid case, we have

n i=1 a i,pi,si = n i=1
wi,p i si . The cumulative work W = n i=1 w i,pi is independent of the schedule λ. We can then write the energy consumption of λ as:

E(λ) = W s λ × s α λ + A stat (λ) × P stat (1) = W × s α-1 λ + p × C max (λ) × P stat . ( 2
)
(λ) = s λ A s• × C max (λ A ). Note that if λ * is a single-speed schedule minimizing the makespan, then C max (λ A ) ≤ c × C max (λ * )
because A yields a c-approximation of the optimal makespan. Therefore,

K [λ A ] ≤ c × K [λ * ] (necessarily s λ A ≤ s λ * = s max ). Moreover, for any single-speed schedule λ, K [λ * ] ≤ K [λ]
, otherwise by running λ at speed s max , we would get a schedule with a lower makespan than λ * , which would contradicts the fact that λ * is optimal for the makespan..

min λ∈[λ A ] E(λ • ) = W × s α-1 • + s λ A s • p × C max (λ A ) × P stat Equation (2) = W × s α-1 • + p × K [λ A ] s • × P stat definition of K [λ A ] ≤ W × s α-1 λ opt + p × K [λ A ] s λ opt × P stat optimality of s * [λ A ] ≤ W × s α-1 λ opt + c × p × K [λ * ] s λ opt × P stat K [λ A ] ≤ c × K [λ * ] ≤ W × s α-1 λ opt + c × p × K [λ opt ] s λ opt × P stat K [λ * ] ≤ K [λ opt ] ≤ W × s α-1 λ opt + c × p × C max (λ opt ) × P stat definition of K [λ opt ] ≤ c × W s α-1 λ opt + c × p × C max (λ opt ) × P stat c ≥ 1 ≤ c × E(λ opt ), Equation (2)
thus proving the theorem.

Moldable case

The algorithm for MinE-Mold-SS (Algorithm 1) assumes first that a speed of one is used. First, we select both a task T i and the number of processors p i for this task. Let t max be the longest execution time among all tasks (assuming a speed of one). We assume that this time is achieved with this task (i.e.,

t max = t i ,p i ).
There are np such selections, and we explore them all. For each value of t max (i.e., for each pair (T i , p i )), we select the number of processors of each other task to be associated with the lowest work such that t i,pi ≤ t i ,p i still holds. We then solve the rigid instance obtained by fixing the number of processors for each task with ListBased-SS or ShelfBased-SS, and we select the speed that minimizes the energy for the resulting schedule. The final schedule is the one with minimum energy over the np explored possibilities.

Algorithm 1: Algorithm for MinE-Mold-SS ;

Intuitively, we analyze the approximation ratio of any moldable scheduling algorithm with the following approach based on [32, GF]:

• For a given t max , we bound the cumulative work to be executed assuming any task execution duration is bounded by t max .

• We then bound the maximum makespan achievable with a guaranteed algorithm for MinE-Rig-SS.

• Finally, we bound the maximum total energy consumption during this duration.

We can state the main result of this section.

Theorem 3. We assume that there exists a polynomial-time algorithm A for MinE-Rig-SS that returns a schedule λ A at a speed of one such that

C max (λ A ) ≤ a × W (λ A ) p + b × t max (λ A ) (resp. C max (λ A ) ≤ max a × W (λ A ) p , b × t max (λ A ) ).
In the moldable single-speed context (MinE-Mold-SS), one can compute in polynomial time a schedule λ • that consumes at most a + b (resp. max(a, b)) times the optimal energy.

Proof. The proof is done for

C max (λ A ) ≤ a × W (λ A ) p + b × t max (λ A ).
The other case (maximum of the two terms instead of sum) is similar.

For any task i and any number p i of processors, we denote by λ i,pi the schedule returned by A on the following rigid instance: for all i , p i is the integer in {1, . . . , p} minimizing w i ,p i under the constraint t i ,p i ≤ t i,pi . There are at most np different such schedules and each one can be computed in polynomial time. For each schedule, the selected speed is the one that minimizes the energy consumption. Let λ • be a schedule of (λ i,pi ) i,pi (where each task is running at speed s i,pi ) with minimum energy consumption (i.e., the schedule for which E(λ

• ) = min i,pi E(λ i,pi )).
Let λ opt be a schedule minimizing the energy (for MinE-Mold-SS). Let i opt denote the longest task in the optimal schedule λ opt and p i opt denote the number of processors for this longest task (i.e., t max (λ opt ) = t i opt ,p i opt ). By construction of the λ i,pi , one has W (λ g ) ≤ W (λ opt ) where λ g = λ i opt ,p i opt . By definition, t max (λ g ) = t max (λ opt ). Thus, at a speed of one,

K [λg] = C max (λ g ) ≤ a × W (λg) p + b × t max (λ g ) ≤ a × W (λ opt ) p + b × t max (λ opt ) ≤ (a + b) × C max (λ opt ) = (a + b) × K [λ opt ] .
Finally, remark that a and b are necessarily constants satisfying a + b ≥ 1 because A would provide a schedule better than the optimal otherwise.

We have:

E(λ • ) ≤ E(λ g ) optimality of λ • over all (λ i,pi ) i,pi ≤ E( s λ opt s λg λ g ) optimality of s g ≤ W (λ g ) × s α-1 λ opt + p × K [λg] s λ opt × P stat Equation (2) ≤ W (λ opt ) × s α-1 λ opt + (a + b) × p × K [λ opt ] s λ opt × P stat approximation ratio of A ≤ (a + b) × W (λ opt ) × s α-1 λ opt + (a + b) × p × K [λ opt ] s λ opt × P stat a + b ≥ 1 ≤ (a + b) × E(λ opt ) Equation (2),
which concludes the proof.

It has already been proved that ListBased-SS is an algorithm that outputs a schedule λ at a speed of one such that C max (λ) ≤ max 2 × W (λ) p , 2 × t max (λ) [START_REF] Garey | Bounds for multiprocessor scheduling with resource constraints[END_REF], so by applying Theorem 3 with a maximum and a = 2 and b = 2, we show that ListBased-SS is a 2-approximation algorithm for the energy.

As for ShelfBased-SS, it is an algorithm that outputs a schedule λ such that [START_REF] Turek | Approximate algorithms scheduling parallelizable tasks[END_REF]LTF], so by applying Theorem 3 with a sum and a = 2 and b = 1 [32, LTF], we show that ShelfBased-SS is thus a 3-approximation algorithm for the energy.

C max (λ) ≤ 2 × W (λ) p + t max (λ)

Processors with different speeds for each task

When generalizing to multiple speeds, the approach is close to the one used for the single-speed problem where all tasks are executed at the same speed (see Algorithm 1); the corresponding algorithm is detailed in Algorithm 2. Note that in the case where the speeds of the tasks are already determined, the dynamic area A dyn is equivalent to the work from [START_REF] Turek | Scheduling parallelizable tasks: Putting it all on the shelf[END_REF], which was denoted by W in Theorem 3. ; Theorem 4. We assume that there exists a polynomial-time algorithm A for MinE-Rig-SS that returns a

Algorithm 2: Algorithm for

schedule λ A such that C max (λ A ) ≤ a× A dyn (λ A ) p +b×t max (λ A ) (resp. C max (λ A ) ≤ max a × A dyn (λ A ) p , b × t max (λ A ) )
with 1 ≤ a. In the general moldable context (MinE-Mold), one can compute in polynomial time a schedule λ • that consumes at most a + b (resp. max(a, b + 1)) times the optimal energy.

Proof. We consider in this proof the max case for A. The proof is similar for the sum.

For any task i, any number p i of processors and any speed s i , we consider the following rigid instance:

for all i , we select (p i , s i ) ∈ {1, . . . , p} × S that minimizes the energy consumption of task i, a i ,p i ,s i × s α i + a i ,p i ,s i × P stat where a i ,p i ,s i is the area of the rectangle representing task i, under the constraint t i ,p i ,s i ≤ t i,p ,s . The schedule returned by A for this problem is denoted λ i,p ,si . There are at most np|S| different such schedules and each one can be computed in polynomial time. Let λ • be a schedule among the (λ i,pi,si ) i,pi,si minimizing the energy.

Let λ opt be a schedule minimizing the energy (for MinE-Mold). Let i opt , p i opt and s i opt satisfy t max (λ opt ) = t i opt ,p i opt ,s i opt . For a schedule λ, set E i (λ) = a i,pi,si s α i + a i,pi,si P stat . By construction, one has:

i E i (λ i opt ,p i opt ,s i opt ) ≤ i E i (λ opt ). (3)
To simplify the notation, we denote λ i opt ,p i opt ,s i opt by λ g . Now,

E(λ • ) ≤ E(λ i opt ,p i opt ,s i opt ) = E(λ g ) ≤ i a i,pi,si (λ g ) × s α i + A stat (λ g ) × P stat definition of the energy ≤ i a i,pi,si (λ g ) × s α i + p × C max (λ g ) × P stat definition of A stat ≤ i a i,pi,si (λ g ) × s α i + p × max a × A dyn (λ g ) p , b × t max (λ g ) × P stat approximation ratio of A
Now, by distributivity, we have one of the two following possibilities:

E(λ • ) ≤ i a i,pi,si (λ g ) × s α i + a × A dyn (λ g ) × P stat left-hand side of the max or E(λ • ) ≤ i a i,pi,si (λ g ) × s α i + b × p × t max (λ g ) × P stat right-hand side of the max
We start with the left-hand side of the max:

LHS ∆ = i a i,pi,si (λ g ) × s α i + a × A dyn (λ g ) × P stat ≤ a × ( i a i,pi,si (λ g ) × s α i + A dyn (λ g ) × P stat ) 1 ≤ a ≤ a × i (a i,pi,si (λ g ) × s α i + a i,pi,si (λ g ) × P stat ) definition of A dyn ≤ a × i E i (λ g ) definition of E i ≤ a × i E i (λ opt ) Equation (3) ≤ a × E(λ opt ) E i ≤ E
Now, the right-hand side of the max:

RHS ∆ = i a i,pi,si (λ g ) × s α i + b × p × t max (λ g ) × P stat ≤ i a i,pi,si (λ g ) × s α i + b × p × t max (λ opt ) × P stat t max (λ g ) = t max (λ opt ) ≤ i a i,pi,si (λ g ) × s α i + b × A stat (λ opt ) × P stat p × t max ≤ A stat for any given schedule ≤ i E i (λ g ) + b × A stat (λ opt ) × P stat a i,pi,si (λ g ) × s α i ≤ E i (λ g ) from the definition of E i ≤ i E i (λ g ) + b × E(λ opt ) A stat × P stat ≤ E for any given schedule ≤ i E i (λ opt ) + b × E(λ opt ) Equation (3) ≤ E(λ opt ) + b × E(λ opt ) E i ≤ E ≤ (b + 1) × E(λ opt )
We finally reunite the two sides of the max:

E(λ • ) ≤ max (a × E(λ opt ), (b + 1) × E(λ opt )) ≤ max (a, b + 1) × E(λ opt ),
which concludes the proof.

In this case, the bound is 3 for both ListBased and ShelfBased algorithms.

Approximation ratios with continuous speeds

We propose a theoretical variation of the problem, where instead of choosing the speed in a finite set of speeds S, we can choose any speed in R * + . We call this continuous problem MinE-Mold-Cont and MinE-Rig-Cont, depending on the nature of the tasks. The motivation for this variation is that we can get stronger approximation results through the introduction of continuous speeds. Through this, we hope to get a better understanding of what makes a good processor speed, thus allowing us to better choose the set of speeds S at the creation of a processor.

Rigid case

Similarly to the discrete case, we start by restricting to rigid tasks (MinE-Rig-Cont-SS problem).

Theorem 5. In the rigid single-speed context with continuous speeds (MinE-Rig-Cont-SS) and assuming

that there exists an algorithm A that yields a c-approximation of the optimal makespan, we can compute in polynomial time a schedule consuming at most c 1-1 α times the optimal energy.

Proof. In the rigid case, we have

n i=1 a i,pi,si = n i=1
wi,p i si . The cumulative work W = n i=1 w i,pi is independent of the schedule λ. With a single speed, we can hence write the energy as:

E(λ) = W × s α-1 λ + A stat (λ) × P stat (4) = W × s α-1 λ + p × C max (λ) × P stat . ( 5
)
The problem can be split as two decisions to take:

• The choice of speed s;

• The actual scheduling, i.e., the choice of the time at which we start each task.

To show that these decisions can be taken one after the other, we start with a preliminary lemma comparing the energy consumption of two schedules using the same speed.

Lemma 1. Let λ 1 , λ 2 be two single-speed schedules such that s λ1 = s λ2 . If E(λ 1 ) ≤ E(λ 2 ), then for any ρ > 0, E(ρλ 1 ) ≤ E(ρλ 2 ).

Proof. Using Equation ( 2),

E(λ 2 ) -E(λ 1 ) = p × P stat × (C max (λ 2 ) -C max (λ 1 )).
Furthermore, C max (λ 1 ) = ρ × C max (ρλ 1 ) and C max (λ 2 ) = ρ × C max (ρλ 2 ). It follows that:

E(λ 2 ) -E(λ 1 ) = p × P stat × ρ × (C max (ρλ 2 ) -C max (ρλ 1 )) = ρ × (E(ρλ 2 ) -E(ρλ 1 )),
hence proving the lemma.

Lemma 1 shows that the actual scheduling can be expressed as a two-steps minimization problem: find a schedule λ 0 minimizing the makespan for a given speed. Next, find among [λ 0 ] (using the notations defined in Section 5.1) a schedule (i.e., a speed) minimizing the energy consumption.

For a given schedule λ 0 , we can compute the optimal speed s as the one that minimizes

f (s) = W × s α-1 + p × K [λ0] s × P stat ,
with K [λ] = s λ × C max (λ) as defined in Section 5.1. This optimal value of s is

s opt [λ0] ∆ = α p × K [λ0] (α -1) × W × P stat .
Then, we can write min

λ∈[λ0] E(λ) = C × α K α-1 [λ0] × W , where C = α (p × P stat ) α-1 × ( α √ α -1 + α (α -1) α-1
) is a constant independent of λ 0 .

Consequently, we have

E(λ opt ) = min [λ0] ∼class min λ∈[λ0] E(λ) = min [λ0] ∼class C × α K α-1 [λ0] × W = C × α K α-1 [λ * ] × W .
Now, let A be an algorithm that yields a c-approximation for the makespan. For a given speed, the quantity K [λ A ] is proportional to the makespan, so this algorithm outputs a schedule λ A such that

K [λ A ] ≤ c × K [λ * ] .
By running this schedule with speed

s opt [λ A ] = α p × K [λ0] (α -1) × W × P stat ,
we have a schedule such that

E λ A = C × α K α-1 [λ A ] × W ≤ C × α c × K [λ * ] α-1 × W ≤ c α-1 α × E(λ opt ).
This proves the theorem: an algorithm A, that yields a c-approximation for the makespan and that returns a schedule λ A will yield a c α-1 α -approximation for the energy.

Moldable case

The overall design of the algorithm for MinE-Mold-Cont-SS is similar to the one of the discrete case, see Algorithm 3.

Algorithm 3: Algorithm for

(T i ,p ) • ; 8 Select the speed s • ∆ = α p×K [λ• ]
(α-1)×W × P stat for this schedule ; 9 return the schedule λ • with minimum energy among all computed λ

(T i ,p ) • ;
We can state the main result of this section. Theorem 6. We assume that there exists a polynomial-time algorithm A for MinE-Rig-Cont-SS that returns a schedule λ A at a speed of one such that

C max (λ A ) ≤ a × W (λ A ) p + b × t max (λ A ) (resp. C max (λ A ) ≤ max a × W (λ A ) p , b × t max (λ A ) ).

In the moldable single-speed context with continuous speeds (MinE-Mold-20

Cont-SS), one can compute in polynomial time a schedule λ

• that consumes at most (a + b) 1-1 α (resp. max(a, b) 1-1 α
) times the optimal energy, when running at speed s

• ∆ = α p×K [λ A ] (α-1)×W × P stat .
Proof. We adapt the proof of Theorem 3 to continuous speeds for the case

C max (λ A ) ≤ a × W (λ A ) p + b × t max (λ A ).
The other case (maximum of the two terms instead of sum) is similar.

For any task i and any number p i of processors, we denote by λ i,pi the schedule returned by A on the following rigid instance: for all i , p i is the integer in {1, . . . , p} minimizing w i ,p i under the constraint t i ,p i ≤ t i,pi . There are at most np different such schedules and each one can be computed in polynomial time. For each schedule, the selected speed is the one that minimizes the energy consumption. Let λ • be a schedule of (λ i,pi ) i,pi (where each task is running at speed

s i,pi = α K [λ i,p i ]
(α-1)×W × P stat ) with minimum energy consumption.

Let λ opt be a schedule minimizing the energy (for MinE-Mold-Cont-SS). Let i opt and p i opt denote the task and the number of processors, such that t max (λ opt ) = t i opt ,p i opt in the schedule λ opt that minimizes the energy consumption. By construction of the λ i,pi , one has W (λ g ) ≤ W (λ opt ) where λ g = λ i opt ,p i opt .

As in the rigid context (proof of Theorem 5), we can express the energy for the respective schedules as

E(λ g = C α K α-1 [λg] × W (λ g ) and E(λ opt ) = C α K α-1 [λ opt ] × W (λ opt ) where C = α (p × P stat ) α-1 ×( α √ α -1+ α (α -1) α-1 )
.

Consequently E(λ•) E(λ opt ) ≤ E(λg) E(λ opt ) = α K α-1 [λg ] K α-1 [λ opt ]
. Now, we have

K [λg] ≤ a × W (λ g ) p + b × t max (λ g ) ≤ a × W (λ opt ) p + b × t max (λ opt ) ≤ (a + b) × K [λ opt ]
From that, we finally get

E(λ • ) E(λ opt ) ≤ α (a + b) α-1 ,
which concludes the proof.

Recall that ListBased-SS is an algorithm with a maximum and a = 2 and b = 2 [START_REF] Garey | Bounds for multiprocessor scheduling with resource constraints[END_REF], hence it is a 2 1-1 αapproximation algorithm. ShelfBased-SS, an algorithm with a sum and a = 2 and b = 1 [START_REF] Turek | Approximate algorithms scheduling parallelizable tasks[END_REF]LTF], is thus a 3 1-1 α -approximation algorithm. For α = 3, these approximation ratios become respectively 3 √ 4 ≈ 1.59 and 3 √ 9 ≈ 2.08.

Optimizing for a single shelf

We propose to further optimize co-schedules by designing a polynomial-time algorithm for the MinE-OneShelf problem, i.e., to optimize the execution of a single shelf, both with discrete and continuous speeds. Formally, given a set of n tasks and p processors, the goal is to find an assignment ((p i ), (s i )) 1≤i≤n

that minimizes E = n i=1 p i × t i,dyn × s α i + p i × t i,stat × P stat , where • t i,dyn = t i,pi,si = ti,p i si , and • t i,stat = max 1≤i≤n t i,dyn (simultaneous model).

Preliminaries

Since the static energy spent depends on the total length of the shelf (i.e., max 1≤i≤n t i,pi,si ), the algorithm proceeds by fixing the shelf length to C max , and aims at finding the optimal number of processors and speed for each task, such that the time bound C max is respected and the total energy consumption is minimized.

Hence, for a single processor, given an amount of work w to complete and a length of shelf of C max , we consider the function OptS(w, C max ) that returns the optimal speed such that w s ≤ C max and the energy consumption w × s α-1 + C max × P stat is minimized. Since the energy consumption is an increasing function of s for s ≥ 0, the optimal speed is the smallest speed such that the shelf length is not exceeded. Therefore, in the discrete case by doing a binary search within values of S.

OptS(w, C

Optimal algorithm for MinE-OneShelf (discrete speeds)

We first focus on the discrete case, i.e., S is the set of possible speeds. The idea is to try every possible duration of the shelf: all possible durations are recorded in the set T , and then for a given duration C max ∈ T , we compute the solution for each set of tasks T 1 , . . . , T i , i ∈ 1, n and each number of processors q ∈ 1, p .

Let e i,q be the minimum energy consumed by task T i on q processors, while not exceeding time C max .

It is computed by using the function OptS(t i,q , C max ), since t i,q is the amount of work on one processor if task T i is executed on q processors.

We then proceed with a dynamic programming algorithm, to compute E i,q , the minimum energy consumption for the first i tasks, when using a total of q processors. The goal is to compute E n,p (using all tasks and all processors). E i,q is recursively defined for 1 ≤ i ≤ n and 1 ≤ q ≤ p as:

E i,q = min 1≤k≤q-i+1 E i-1,q-k + e i,k ,
with E 0,q = 0. If there are no tasks left, the energy consumption is null; otherwise we try all possible numbers of processors k for task i, while keeping at least one processor for each of the remaining tasks.

We then take the best possible solution amongst the different possible durations in the set T , and Algorithm 4 provides the corresponding pseudo-code of this dynamic programming algorithm. for q ← 1 to p do 10 s i,q ← OptS(t i,q , C max ) ; 11 if s i,q = None then 12 e i,q ← ∞ ; 13 else 14 e i,q ← qt i,q s α-1 i,q + qC max P stat ;

15 for q ← 0 to p do 16 E 0,q ← 0 ; Proof. Let us prove by induction over i ∈ 0, n that for all q ∈ 1, p , E i,q is the minimum energy consumed to process the i first tasks with q processors.

17 for i ← 1 to n do 18 for q ← i to p do 19 for k ← 1 to q -i + 1 do 20 if E i-1,q-i + e i,k < E i,q then 21 E i,q ← E i-1,q-k + e i
Base case. For all q ∈ 0, p , the energy consumed to handle no task on q processors is 0, meaning that the E 0,q values for q ∈ 0, p are correct.

Inductive step. Let i ∈ 0, n -1 , and we assume that ∀q ∈ 1, p , E i,q is correct. The expression of E i+1,q is min 1≤k≤q-i E i,q-k + e i+1,k . If task T i+1 is given k processors, then the i first tasks will be handled by q -k processors. As the task i + 1 must be given a number of processors k ∈ 1, q -i , the expression gives the correct value for E i+1,q .

It means that E n,p is correct, and therefore that the algorithm is also correct.

The number of total durations is at most np|S|, because we must choose a task, the number of processors allocated for this task, and its speed. The complexity of the algorithm is thus O(n 2 p 3 |S|).

Optimal algorithm for MinE-OneShelf-Cont (continuous speeds)

We now discuss the case of continuous speeds, hence S = R * + . Similarly to the discrete case, the idea is to fix the shelf duration and to solve the problem knowing that the processors will be powered for the duration C max . Because of continuous speeds, we cannot anymore explore all possible times C max , so we fix the duration to C max = 1, and then prove that the optimal assignment is in fact the same for any C max , and the minimum energy is a function of C max . We finally take the value of C max that minimizes the energy consumption, see Algorithm 5 and Theorem 8 for the proof of optimality.

Algorithm 5: Optimal algorithm for MinE-OneShelf-Cont

1 for i ← 1 to n do 2 for q ← 1 to p do 3 s i,q ← OptS(t i,q , 1) ; 4 if s i,q = None then 5 e i,q ← ∞ ; 6 else 7 e i,q ← qt i,q s α-1 i,q + qP stat ; 8 for q ← 0 to p do 9 E 0,q ← 0 ; 10 for i ← 1 to n do 11 for q ← i to p do 12 for k ← 1 to q -i + 1 do 13 if E i-1,q-k + e i,k < E i,q then 14 E i,q ← E i-1,q-k + e i,k ; 15 C max ← α-2 (α -1)( En,p pPstat -1); 16 return En,p-pPstat C α-1 max + pC max P stat ;
Lemma 2. Let E dyn (C max ) be the minimum possible dynamic energy consumption, with the condition that each task must end before C max . Then, for any C max ∈ R * + , we have:

E dyn (C max ) = E dyn (1) C α-1 max .
Proof. Recall that the dynamic energy consumption of an assignment ((p i ), (s i )) 1≤i≤n is

n i=1 p i × t i,pi × s α-1 i . Let t ∈ R * + . If ((p i ), (s i ))
1≤i≤n is an optimal assignment for the case C max = 1, with a total dynamic energy consumption of E dyn (1), then we can consider the same assignment but with all speeds divided by t, to ensure that all tasks meet the deadline C max = t: ((p i ), ( si t )) 1≤i≤n . The corresponding dynamic energy consumption is then

E dyn (1) t α-1 ,
MinE-Rig-Cont-SS c c 1-1 α
Th. 5 (Sec. 6.1)

MinE-Mold-Cont-SS a W p + bt max (a + b) 1-1 α Th. 6 (Sec. 6.2) max(a W p , bt max ) max(a, b) 1-1 α MinE-OneShelf Optimal Th. 7 (Sec. 7.2) MinE-OneShelf-Cont Optimal Th. 8 (Sec. 7.3)
Table 3: Summary of theoretical results from Section 4to Section 7. The base ratio is the approximation ratio on the makespan the base algorithm A.

Conversely, if we have an assignment for the problem with C max = t, with a dynamic energy consumption of E dyn (t), then we take the same assignment but with all speeds multiplied by t to obtain a valid solution to the problem with

C max = 1, hence leading to E dyn (t) ≥ E dyn (1) t α-1 . This concludes the proof of the lemma since E dyn (t) = E dyn (1) t α-1
for any t ∈ R * + .

Theorem 8. MinE-OneShelf-Cont can be solved optimally in polynomial time.

Proof. The proof for a fixed C max is the same as in the proof of Theorem 7, since we use the same dynamic programming algorithm. Then, E n,p = E dyn (1) + p × P stat . From Lemma 2, the optimal energy for a

given

C max is therefore E(C max ) = E dyn (C max ) + E stat (C max ) = En,p-p×Pstat C α-1 max + p × C max × P stat , which is a convex function of C max that reaches its minimum for C max = α-2 (α -1)(
En,p p×Pstat -1). The complexity of the algorithm is O(np 2 ).

The next section empirically assesses the theoretical results summarized in Table 3.

Empirical Study

We first describe the experimental setup in Section 8.1. Then, we explain how instances are generated in Section 8.2. The different heuristics are compared and analyzed in Section 8.3, Also, we further study the impact of P stat in Section 8.4, and the impact of having a set discrete speeds instead of the continuous model in Section 8.5.

Experimental setup

All the algorithms rely on the global mechanism presented in Algorithm 1 (Section 5.1.2 [START_REF] Turek | Approximate algorithms scheduling parallelizable tasks[END_REF]GF]) with a single speed (denoted with the suffix SS) and Algorithm 2 with multiple speeds (without any suffixes). The Algorithm 6: Algorithm ListBased for rigid tasks {(T 1 , p 1 , s 1 ), . . . , (T n , p n , s n )} 22 return the schedule λ; Algorithm 7: Algorithm ShelfBased for rigid tasks {(T 1 , p 1 , s 1 ), . . . , (T n , p n , s n )} 1 Sort the tasks by non increasing execution time so that T 1 has the longest execution time and T n the shortest; core idea is that first we transform a moldable instance into a rigid instance by fixing the number of processors for each task. It is then combined with the strategies presented in Section 2: ListBased and ShelfBased.

1 λ ← Empty schedule; 2 for j ∈ {1, . . . p} do 3 C j ← 0; 4 T ← {T 1 , . . . , T n }; 5 P ← ∅; 6 C current ← 0; 7 while T = ∅ do 8 if ∃T i ∈ T s.t. p i ≤ |P| then 9 i ← min Ti∈T i s.t. p i ≤ |P|;
2 λ ← Empty schedule; 3 C current ← 0; 4 C next ← 0; 5 T ← {T 1 , . . . , T n }; 6 P ← ∅; 7 for T i ∈ T by increasing i do 8 if p i > |P| then 9 C current ← C next ; 10 C next ← C current + t i,
The two algorithms ListBased and ShelfBased are detailed as Algorithms 6 and 7. Moreover, we also implemented two optimization algorithms that can only be applied to an output of • OptiShelf, which optimizes each shelf once each task has been allocated to a shelf using the algorithm from Section 7 (this may change the number of processors used for each task). This optimization keeps the shelf structure, which can be an advantage for instances where this structure is a constraint the final schedule is subject to;

• De-shelf, which takes a ShelfBased solution and starts each task as soon as possible by removing the shelf constraint while keeping the allocations and the order in which the tasks are started.

For both of these optimizations, the energy consumption cannot be worse after the optimization than before.

It is technically possible to combine the two optimizations (running OptiShelf and then De-shelf). We tried it for the sake of completeness, however this did not provide any interesting results as OptiShelf's optimization is heavily based on the shelf structure, while De-shelf removes this shelf structure. Overall, this represents a total of eight heuristics (two list-based, two non-optimized shelf-based, and four optimized versions of shelf-based).

To compare the different heuristics, we implemented them in C++17 compiled with gcc 9.3.0 with optimization option -O3. We rely on Python 3.8.5 to generate the instances and to analyze the results. The code of these experiments can be found on Figshare1 .

Instance generation

The characteristics of the processors were extracted from a realistic platform [START_REF] Moody | Design, modeling, and evaluation of a scalable multi-level checkpointing system[END_REF][START_REF] Benoit | A different re-execution speed can help[END_REF] The number of tasks varies from 20 to 1000, with a step every 20 tasks. The workload was generated with the two following task profiles (half from each type):

• Amdahl's law [START_REF] Amdahl | Validity of the single processor approach to achieving large scale computing capabilities[END_REF][START_REF] Sun | Scheduling parallel tasks under multiple resources: List scheduling vs. pack scheduling[END_REF]:

w i,pi = w i,1 × β + wi,1×(1-β) pi ;
• Power law [START_REF] Prasanna | Generalized multiprocessor scheduling and applications to matrix computations[END_REF][START_REF] Hartstein | On the nature of cache miss behavior: Is it √ 2[END_REF][START_REF] Sun | Scheduling parallel tasks under multiple resources: List scheduling vs. pack scheduling[END_REF]:

w i,pi = wi,1 p β i .
In both cases, w i,1 and β are drawn from a uniform distribution U (0, 1).

Results

In order to evaluate the performance of the various heuristics and show whether they return results close to the optimal, we compare the results with a lower bound that consists in an optimal execution in the MinE-Mold-Indep case (Section 4.1). In that case, the static energy is paid only while a task is executed, and any solution to MinE-Mold will consume at least as much energy as this lower bound. For convenience, the default version of a heuristic is the multiple-speed variant, and we refer to the single-speed variant with the SS suffix. energy consumption of each heuristic with the lower bound (the lower the better), and also the execution time of the C++ implementation of the heuristics. A first remark is that single-speed and multiple-speed variants give very similar results. Indeed, in practice, we could confirm that the multiple-speed heuristics give the same speed to most tasks.

Figures 3 and4 present a similar overview with a larger amount of tasks: n = 5000 tasks per instance.

The difference in energy consumption between ListBased and De-shelf becomes smaller as n increases, while the execution time of the algorithm ListBased becomes much larger due to a higher order of growth. Execution time of the algorithm, in seconds close to 1 for all heuristics, at the price of an increasing execution time.

In terms of energy consumption, the best performing algorithms are ListBased and ListBased-SS (the lowest lines on the left charts). Then De-shelf and De-shelf-SS have a performance that is close to the ones of our best algorithms. Finally ShelfBased, ShelfBased-SS, OptiShelf and OptiShelf-SS have the worst performance among our algorithms (the top lines on the left charts).

In terms of execution time of the algorithms, most of our algorithms give instantaneous results. The exceptions are ListBased, that has a superlinear complexity with respect to the number of tasks, and both OptiShelf and OptiShelf-SS, that have a linear complexity with respect to the number of tasks but with a high constant factor.

As there are many algorithms and plots are overlapping, we then compare them in a more refined study, presenting more precisely how each algorithm behaves, along with the advantages and drawbacks of these algorithms.

Among the base algorithms (ListBased-SS, ListBased, ShelfBased-SS and ShelfBased), we focus on two baseline algorithms:

• the base algorithm with the best output energy: ListBased;

• the base algorithm with the best execution time: ShelfBased-SS.

If we compare these two algorithms, ListBased and ShelfBased-SS, we can see that ListBased provides schedules with a lower energy consumption than ShelfBased-SS, but at the cost of a much larger execution time for the algorithm. When the number of tasks n increases, the difference in terms of execution time increases, while the difference of energy consumption decreases. Note that ListBased could be implemented in a faster way with a segment tree to compute which task can be started, making this operation O(log p) instead of O(n). However, this complex data structure would probably not be included in most implementations. However, we can use the solution delivered by ShelfBased (with a single speed for all tasks), and pass this solution through two possible optimizations: OptiShelf or De-shelf. By comparing the results of the two approaches, we can see that both optimizations increase the quality of the solution, but OptiShelf does it at the cost of a very large increase in the execution time. However, the overhead of De-shelf is small, which leads to solutions of better quality at a small cost.

Finally, we compare ListBased (with multiple speeds) to the optimized ShelfBased-SS (with a single speed) with De-shelf, which we found to be the best optimization for ShelfBased. As we can see on see that, for all of the algorithms we provide, the schedules given for the Transmeta Crusoe are closer to the lower bound. First, this can be explained by the fact that the Transmeta Crusoe is a processor with a very low relative static power (around 7.6 × 10 -4 ) while the relative static power of the Intel Xscale is higher (around 3.9 × 10 -2 ). It means that there is less need to optimize the makespan, thus simplifying the problem. We explore the impact of P stat in Section 8.4. Another explanation can be related to the difference of available speeds between the processors. We explore the impact of available speeds in the Section 8.5

through an empirical study of the continuous case.

Impact of P stat

Figure 7 compares all the proposed algorithms when varying P stat . We can observe that for small values of P stat , even the algorithms that were not so efficient before provide good results. That is because, in this case, the idle time of the processors does not have a high cost in terms of energy consumption. Thus, having a small total amount of work W is more important than having a small makespan C max . Since all the algorithms try at some point to minimize W in the same way, they end up by all providing similar results.

However, when P stat increases, the importance of minimizing the makespan C max increases. The different algorithms provide different performance in terms of makespan, which explains the difference in performance:

ListBased and optimized ShelfBased algorithms provide much better solutions than simple ShelfBased algorithms.

Comparison with the continuous relaxation

Finally, we conduct experiments with the relaxed continuous version of the problem, MinE-Mold-Cont,

where the speed of the processors can be any positive number. The previous lower bound does not apply for this relaxed problem because there is no constraint on the minimum speed. The ratio between the energy consumption achieved by the algorithm and the lower bound can thus be lower than 1. Note that we focus here on single speed variants of the algorithms, where a single continuous speed will hence be chosen.

Figure 8 compares all of the discrete speed algorithms we propose to the algorithm ListBased-Cont we use for the relaxed problem. This algorithm gives a solution with continuous speeds that consumes 15% less energy than the best result we can get with the speeds available for the Intel Xscale. It means that with a better choice of speeds when designing the processor, we can expect a 15% decrease in energy consumption with our algorithms. For the Transmeta Crusoe processor, the energy gap is even bigger: with a better choice of speeds, we can hope to gain more than 80% of energy.

Figure 9 compares the discrete-speed algorithm with the best results (ListBased-SS) to the result we can get with continuous speeds, for different values of P stat . Intuitively, all approaches are close to 1 when they rely on speeds that are close to the discrete speeds of the studied processor: in these cases the speeds used by the continuous speed algorithm are already available in the discrete speed model. When we get further away from these cases, we see that allowing continuous speeds would allow for a much better performance. It means that the design of the static power P stat and the set of available speeds S must be done concordantly.

This design can be helped by theoretical results, such as the ones we provide in this paper, along with simulations such as the ones we provide in this section. When comparing the Intel Xscale, on the left, to the Transmeta Crusoe, on the right, we see that the available speeds for the Intel Xscale correspond well to the effective P stat (the plain line). It is not the case for the Transmeta Crusoe: lower processor speeds would improve the energy consumption.

Intel Xscale Transmeta Crusoe

Conclusion

With the growing concern regarding the energy consumption of current parallel platforms, it is crucial to bound the worst-case performance. This paper is the first to propose such bounds on the energy consumption when scheduling moldable tasks. We highlight the relation between the energy and the completion time (determined by the DVFS mechanism) and rely on the numerous approximation algorithms that have already been proposed to minimize the completion time. This leads to a general mechanism to bound the energy consumption of such existing approximation algorithms for the completion time. In particular, we show that a shelf-based approach is a 3-approximation (resp. 2.08-approximation) algorithm for the energy consumption with discrete speeds (resp. continuous speeds).

We also focus on the optimization of a single shelf by providing a polynomial-time algorithm that can be used to improve existing solutions. Empirical results reveal that such an approach, when combined with a fast optimization post-operation, is beneficial in practice because of its low cost.

To complete this study, we could consider variations of the power model. In particular, we assume that changing frequencies with the DVFS mechanism does not incur any energy cost or delay, which may not be accurate in practice. We additionally assume that the set of available speeds is a constant, while we could consider it a function of the number of processors in use (e.g., when all the processors are used, the highest frequencies might not be usable). Also, we plan to experiment on more recent processors whose range of frequencies suggest that it behaves closer to the continuous model. This involves doing some measurements to obtain detailed data on the power consumption of such processors and processing these measures, while only information on frequencies is publicly available. Finally, the whole model revolves on the premise that the tasks are computationally bound. In the case of memory bound applications, changing the processor speeds does not change the execution time, which is a case that we have not considered yet. The algorithms presented could be adapted to perform on mixes of computationally bound and memory bound applications.

Overall, this paper aims at providing the theoretical foundations to the problem. Since current task systems do not yet have moldable task profiles that can be used, we have focused on classical models that have already been largely considered in the literature. As soon as moldable task profiles are available, it would be very interesting to conduct experiments on real HPC systems.

  MinE-Mold and MinE-Mold-SS are NP-complete, and the decision problems associated to MinE-Mold-Cont and MinE-Mold-Cont-SS are NP-hard.

  max ) = max(s min , w Cmax ) in the continuous case, and OptS(w, C max ) = min s ∈ S | s ≥ w Cmax in the discrete case. In the case no such speed exists (this may happen with discrete speeds), the function returns None. Note that this function can be computed in Θ(1) in the continuous case, and in Θ(log(|S|))

Algorithm 4 : 1 T ← ∅ ; 2 for i ← 1 to n do 3 for q ← 1 to p do 4 for s ∈ S do 5 T 6

 413456 Optimal algorithm for MinE-OneShelf (discrete model) res ← ∞ ; 7 for C max ∈ T do 8 for i ← 1 to n do

9

 9

10 λ 12 Let j ∈ P; 13 C 14 P ← P\{j}; 15 T 17 j 18 C 20 j

 1012131415171820 ← λ ∪ {T i starting at time C current on p i processors from P}; 11 for k ∈ {1, p i } do j ← C current + t i,pi,si ; ← T \{T i }; 16 else ← arg min j∈{1,...,p}\P C j ; current ← C j ; 19 while C current = min j∈{1,...,p}\P C j do ← min j∈{1,...,p}\P C j ; 21 ← P ∪ {j};

pi,si ; 11 P 12 λ

 1112 ← {1, . . . , p}; ← λ ∪ {T i starting at time C current on p i processors from P}; 13 for k ∈ {1, p i } do 14 P ← P\{j}; 15 return the schedule λ;

Figures 1 and 2 Figure 1 :

 21 Figures1 and 2present an overview of the results for all heuristics with n = 500 tasks, respectively on the Intel Xscale platform and on the Transmeta Crusoe platform. We report both the ratio between the

Figure 2 :

 2 Figure 2: Output energy consumption and execution time to compute the solution for all eight heuristics with n = 500 mixed power and Amdahl's tasks and on the Transmeta Crusoe (p = 32 processors with Pstat = 44 57560 , α = 3, S = {0.45, 0.6, 0.8, 0.9, 1}). Each box aggregates 10 measurements.

Figures 5 and 6

 6 Figures 5 and 6 present the scaling with n of all heuristics respectively on the Intel Xscale platform and the Transmeta Crusoe platform. With a large number of tasks, the ratio with the lower bound becomes very

Figure 3 :

 3 Figure 3: Output energy consumption and execution time to compute the solution for all eight heuristics with n = 5000 mixed power and Amdahl's tasks and on the Intel Xscale platform (p = 32 processors with Pstat = 6 155 , α = 3, S = {0.15, 0.4, 0.6, 0.8, 1}). Each box aggregates 10 measurements.

Figure 4 :

 4 Figure 4: Output energy consumption and execution time to compute the solution for all eight heuristics with n = 5000 mixed power and Amdahl's tasks and on the Transmeta Crusoe (p = 32 processors with Pstat = 44 57560 , α = 3, S = {0.45, 0.6, 0.8, 0.9, 1}). Each box aggregates 10 measurements.

Figure 5 :

 5 Figure 5: Output energy and execution time to compute the solution for all algorithms for instances with mixed power and Amdahl's tasks and and on the Intel Xscale platform (p = 32 processors with Pstat = 6 155 , α = 3, S = {0.15, 0.4, 0.6, 0.8, 1}). The output energy is given with a x → log 10 (x -1)-scale.

Figure 6 :

 6 Figure6: Output energy and execution time to compute the solution for all algorithms for instances with mixed power and Amdahl's tasks and and on the Transmeta Crusoe platform (p = 32 processors with Pstat = 44 57560 , α = 3, S = {0.45, 0.6, 0.8, 0.9, 1}). The output energy is given with a x → log 10 (x -1)-scale.

Figures 5 and 6 ,Figure

 6 Figures5 and 6, for very small instances, ListBased still performs better than ShelfBased with De-shelf.However, when n grows larger, ShelfBased with De-shelf quickly performs as well as ListBased, but with a lower time complexity.Overall, by comparing the results we get with the processors Intel Xscale and Transmeta Crusoe, we

  energy found by the algorithm and the computed lower bound

Figure 8 :Figure 9 :

 89 Figure 8: Output energy consumption and execution time to compute the solution for four heuristics with n = 500 mixed power and Amdahl's tasks and p = 32 processors (on the left: with Intel Xscale Pstat = 6 155 , α = 3, and S = {0.15, 0.4, 0.6, 0.8, 1} in the discrete cases; on the right: with Transmeta Crusoe Pstat = 44 57560 , α = 3, and S = {0.45, 0.6, 0.8, 0.9, 1} in the discrete cases). Each box aggregates 10 measurements.

Table 1 :

 1 List of notations.

	Notation Quantity
	p Number of processors
	P stat Static Power
	S Set of available speeds on the processors
	T i Task number i
	w i,j Total work for the execution of task i on j processors
	t i,j,s Execution time of task i on j processors at speed s
	t i,j Execution time of task i on j processors at speed s = 1
	a i,j,s Area of task i on j processors at speed s
	λ A schedule
	p i (λ) Number of processors allocated to task i in schedule λ
	s i (λ) Speed of the processors allocated to task i in schedule λ
	t max (λ) Execution time of the longest task in schedule λ
	C max (λ) Makespan of schedule λ
	W (λ) Sum of the work of all tasks in schedule λ
	T dyn (λ) Sum of the execution times of all tasks in schedule λ
	A dyn (λ) Sum of the areas of all tasks in schedule λ
	A stat (λ) Sum of the times during which processors are powered in schedule λ

Table 2 :

 2 List of problems (multiple speeds).

  MinE-Mold, with multiple speeds 1 for (T i , p , s ) ∈ {T 1 , . . . , T n } × {1, . . . , p} × {s 1 , . . . , s k } do ∈ {T 1 , . . . , T n } do 4 p i , s i ← arg min 1≤j≤p,s∈S a i,j,s × s α + a i,j,s × P stat such that t i,pi,si ≤ t max if it exists; Apply a guaranteed algorithm A on the rigid instance {(T 1 , p 1 , s 1 ), . . . , (T n , p n , s n )} at speed of 1, to get a schedule λ (T i ,p ,s ) • ; 8 return the schedule λ • with minimum energy among all the computed λ (T i ,p i ,s i ) •

	2	t max ← t i ,p ,s ;
	5	p i , s i ← 0, 0 otherwise.
	6	if all p i , s i = 0, 0 then

3

for T i 7

  and hence the optimal solution E dyn (t) is such that E dyn (t) ≤

	Problem	Base ratio (A)	Achieved bound	Result
	MinE-Mold-Indep	opt	opt	Sec. 4.1
	MinE-Rig-SS	c	c	Th. 2 (Sec. 5.1.1)
	MinE-Mold-SS	a W p + bt max	a + b	Th. 3 (Sec. 5.1.2)
		max(a W p , bt max )	max(a, b)
	MinE-Mold	a W p + bt max	a + b	Th. 4 (Sec. 5.2)
		max(a W p , bt max )	max(a, b + 1)
				E dyn (1) t α-1 .

Preprint submitted to ElsevierDecember 23, 2022

https://doi.org/10.6084/m9.figshare.14854395

Acknowledgements:

We would like to thank the anonymous reviewers for their comments and suggestions, which greatly helped improve the paper.