domain: spi phys math info

text:
Anthony Bourdelle

Jean-Marc Biannic

Helene Evain

Sabine Moreno

Christelle Pittet

Laurent Burlion

Propellant Sloshing Torque H ∞ -based Observer Design for Enhanced Attitude Control

Keywords: Sloshing, LPV observers, H ∞ control, attitude control

In this paper a control-oriented LPV model of the sloshing torque arising during attitude maneuvers, supported by Computational Fluid Dynamics results, is presented and used for attitude control design. The proposed strategy essentially relies on the design of a robust LPV-based disturbance torque observer with the help of the structured multi-model H ∞ synthesis framework. The estimated torque is then used to improve a satisfying attitude controller initially designed without sloshing. The stability of the parameter-varying closed-loop system is finally proved with parameter-dependent Lyapunov functions.

INTRODUCTION

In any liquid-carrying vehicle, more importantly during acceleration phases, the on-board fluid, as long as it has a free surface, is set in motion by fluid-structure dynamical coupling. This low frequency and badly damped phenomenon that corresponds to the movement of a liquid free surface inside containers [START_REF] Ibrahim | Liquid sloshing dynamics: theory and applications[END_REF]] is referred to as sloshing. According to the vehicle motion, different types of sloshing dynamics arise, such as surface waves, bulk fluid or vortices. As satellites carry a lifespan-defining quantity of liquid propellant consumed by thrusters to perform orbital maneuvers (station-keeping, relocation and de-orbiting), they are subject to sloshing. Therefore satellites experience disturbing forces and torques that affect their pointing accuracy. Slosh dynamics can then compromise the system performance and stability [START_REF] Hoffman | The near rendezvous burn anomaly of december 1998[END_REF]], complicating the controller design. For space applications sloshing dynamics become even more complex as surface tension effects must be considered.

The main solution to mitigate sloshing effects is to divide propellant tanks with baffles and bladders [START_REF] Dodge | Engineering study of flexible baffles for slosh suppression (nasa cr-1880)[END_REF]; [START_REF] Tam | Design and manufacture of the messenger propellant tank assembly[END_REF]], which increases the sloshing frequency and reduces its amplitude. Mass is added to the satellite, and mission costs raise. Time margins can also be applied between aggressive maneuvers in order to allow the propellant to settle down. But this considerably reduces mission availability. Alternatively, smoothed references can be used instead of usual sharp bang-off-bang angular velocity reference profiles [START_REF] Somov | Attitude guidance, navigation and control of land-survey mini-satellites[END_REF]; [START_REF] Liu | Near minimum-time feedback attitude control with multiple saturation constraints for agile satellites[END_REF]]. The sloshing response will then be smoother, but the whole satellite agility may no longer be exploited. Sloshing influence can also be tempered by notch filters [Preumont This study have been co-funded by ONERA and CNES (1997)], which reduce satellites bandwidth (especially as sloshing frequencies are uncertain).

From a control design perspective, the most common way to address sloshing is based on the famous equivalent mechanical model. These models approximate the liquid with a mechanical system and can be treated like flexible modes [START_REF] Mazzini | Flexible Spacecraft Dynamics, Control and Guidance[END_REF]]. Numerous models exist and reproduce a specific kind of sloshing dynamics [START_REF] Abramson | The dynamic behavior of liquids in moving containers, with applications to space vehicle technology[END_REF]; [START_REF] Berry | Experimental study of transient liquid motion in orbiting spacecraft[END_REF]; [START_REF] Vreeburg | Models for liquid impact onboard sloshsat flevo[END_REF]; [START_REF] Sopasakis | Sloshing-aware attitude control of impulsively actuated spacecraft[END_REF]]. Tuning the mechanical parameters (such as mass, spring stiffness and pendulum length) to accurately reproduce the liquid behavior is of crucial importance. For instance [START_REF] Enright | Propellant slosh models for the cassini spacecraft[END_REF] uses Computational Fluid Dynamics (CFD) to evaluate sloshing frequencies in the Cassini probe tanks. The control of spacecraft with multiple propellant sloshing modes represented with pendulums has been addressed in [START_REF] Reyhanoglu | Nonlinear control of a spacecraft with multiple fuel slosh modes[END_REF] with both linear and Lyapunov-based nonlinear feedback controllers. [START_REF] Hervas | Control of a spacecraft with time-varying propellant slosh parameters[END_REF] uses spring-masses and take into account consumption of propellant with time-varying parameters. In de Souza and de Souza (2014) pendulum model parameters are identified by a Kalman filter. Uncertainties in pendulum models can be addressed with robust control, as in [START_REF] Yano | Robust liquid container transfer control for complete sloshing suppression[END_REF]. The main advantage of equivalent mechanical models is their simplicity, which is also their main drawback. These models are based on linearized fluid dynamics models and often valid only for axisymmetric problems (e.g. hemispherical tanks accelerated along their main axis) with small amplitude motion. More importantly, they do not depend on angular speed or acceleration of the spacecraft, which however induce significant large inertial forces acting on the fluid.

Infinite-dimensional models can also be used to represent sloshing, [START_REF] Ardakani | Shallow-water sloshing in vessels undergoing prescribed rigid-body motion in three dimensions[END_REF] proposed threedimensional sloshing equations for prescribed motion of tanks, [START_REF] Petit | Dynamics and solutions to some control problems for water-tank systems[END_REF] considered direct actuation of tank speed or acceleration and Cardoso-Ribeiro et al. (2015) used the Port-Hamiltonian formalism [START_REF] Duindam | Modeling and control of complex physical systems: the port-Hamiltonian approach[END_REF]] to design a controller for slosh mitigation in a fluid-coupled structure. The considered fluid dynamics equations are valid for specific cases, generally shallow waters, i.e. low filling ratio, perfect fluid and negligible tension surface effects. The generalization to Navier-Stokes equations with inertial forces and tension surface is very complex, and far from the Attitude and Orbit Control Systems paradigm, prohibiting the use of controller design and stability analysis tools.

As attitude pointing accuracy and stability requirements are always more stringent, very effective Attitude Control Systems (ACS) are needed and thus the models used for controller design need to evolve. Recent progress have been achieved in the field of Computational Fluid Dynamics and several codes, such as DIVA from Institut de Mécanique des Fluides de Toulouse [START_REF] Lepilliez | On two-phase flow solvers in irregular domains with contact line[END_REF]] and ComFlo from University of Groningen [START_REF] Veldman | The numerical simulation of liquid sloshing on board spacecraft[END_REF]], are now able to accurately compute the fluid behavior in maneuvering spacecraft. Interestingly, CFD can also be used in order to improve simplified models suitable for controller design. Inspired by equivalent mechanical models, a generalization to nonlinear parameter-varying sloshing models along with a CFD-based parameter identification procedure was proposed in [START_REF] Bourdelle | Towards new control design oriented models for fuel sloshing in observation spacecraft[END_REF]]. Based on this work, a reformulation of the slosh effects as an uncertain Linear Parameter Varying (LPV) model is proposed in this paper. This model will then serve as a basis for the robust design of an LPV state observer capable of taking into account model uncertainties to provide a reliable estimate of the sloshing torque. The latter is then used to decouple the satellite dynamics from sloshing and ensure an accurate attitude control with reduced settling time.

The remainder of the paper is organized as follows. First, section 2 recalls some key ingredients on slosh modeling and introduces the aforementioned uncertain LPV model of the liquid-filled satellite. Next, a robust H ∞ -based observer design procedure is detailed in section 3. Then, in section 4, a time-varying implementation of our enhanced attitude control system is presented together with simulation results and a thorough parameter-varying stability analysis. Finally, concluding comments and perspectives are proposed in section 5

NONLINEAR SLOSHING TORQUE MODEL

Using recent developments in Computational Fluid Dynamics solvers, supported by in-situ experiments (such as SloshSat-FLEVO [START_REF] Prins | SLOSHSAT FLEVO -Description of the mini satellite[END_REF]] and Fluidics [START_REF] Mignot | Fluid dynamics in space experiment[END_REF]]) , we propose a new approach by directly modeling the sloshing disruptive efforts instead of the fluid behavior. In the following sections we will consider a satellite attitude maneuver around a single axis, though our reasoning can be generalized to any maneuver.

Sloshing Torque Modeling and Identification

Sloshing dynamics depends on :

-tank filling ratio -gravitational acceleration effects -propellant properties, e.g. density, surface tension -tank geometry and position inside the spacecraft -spacecraft angular speed and acceleration Reaction wheels or Control Moment Gyros are preferred for attitude control, propellant is saved for orbit control which uses thrusters. In the context of this paper we can thus consider a constant filling ratio. Gravitational effects are assumed negligible in front of inertial and capillary forces. The tank is considered rigid and still. Hence, only the dependence to the angular velocity Ω(t) and acceleration Ω(t) have to be taken into account by the sloshing torque model. For clarity reasons, the timedependence will be omitted in the next equations.

In [START_REF] Bourdelle | Towards new control design oriented models for fuel sloshing in observation spacecraft[END_REF] it was proposed to describe the sloshing torque Γ F as the output of a nonlinear second order system with varying frequency and damping ratio :

ΓF + C s (Ω, Ω) ΓF +K s (Ω, Ω)Γ F = -A s (Ω, Ω)Ω -B s (Ω, Ω) Ω (1)
Due to their similarities, we can consider this nonlinear model as a generalization or an abstraction of equivalent mechanical models. The nonlinear properties of this model result from the dependence of A S , B S , C S and K S to (Ω, Ω). These parameters can be identified using CFD results covering angular speed and acceleration ranges.

With numerically computed sloshing torque, it is possible to compute boundaries for the natural frequency ω(Ω, Ω) and the damping ratio ξ(Ω, Ω) in order to constrain C s and K s , which can be written as :

C s (Ω, Ω) = 2ξ(Ω, Ω)ω(Ω, Ω) (2)
K s (Ω, Ω) = ω(Ω, Ω) 2 (3)
The nonlinear coefficients are identified on a set of N small time intervals on which both Ω and Ω are assumed constant and the nonlinear model becomes Linear Time Invariant (LTI). By doing so it is possible to use a constrained least squares method. As a result, N sets {C si , K si , A si , B si } i≤N associated to {Ω i , Ωi ) i≤N are obtained. Standard curve-fitting techniques may then be used to rewrite each parameters as multivariate polynomials of Ω and Ω for example.

This identification procedure has been applied on DIVA data sets courtesy of Institut de Mécanique des Fluides de Toulouse. These data correspond to the Z-axis rotation of a spherical tank with a diameter of 0.585 m and half-filled with hydrazine. The tank is off-center to the axis of rotation, the resulting lever arm is 0.4 m. The rotation follows a bang-off maneuver, i.e. full acceleration for a certain time, then constant speed (square shape acceleration profile). As stated in [START_REF] Bourdelle | Towards new control design oriented models for fuel sloshing in observation spacecraft[END_REF], better results are obtained by proceeding on two different sub-models, for each side of the acceleration discontinuity.

Towards an uncertain LPV model

From Equation 1, a state-space representation of the sloshing torque is :

ΓF ΓF ẋF = 0 1 -K S -C S A F (K S , C S ) Γ F ΓF x F + 0 0 -A S -B S B F (A S , B S ) Ω Ω (4) Γ F = (0 1) x F (5)
where the dependencies to (Ω, Ω) have been omitted for simplicity. The parameters A S , B S , C S and K S are affected by uncertainties, which arise from :

-numerical simulations errors -identification and modelling errors Since such uncertainties are unfortunately poorly known, it is useless to develop any accurate model (based on the Linear Fractional Transformation for example) to take them into account. Then, a basic model that consists of introducing a bounded disturbance w such that ||w|| 2 ≤ w will be used next. Equation 4 thus becomes :

ẋF = A F (K S , C S )x F + B F (A S , B S ) Ω Ω + 0 1 w (6)
Let us consider the LTI state-space representation of the single-axis dynamics of an actuated satellite :

ẋSAT = A SAT x SAT + B SAT (Γ F + Γ P + Γ C ) (7)
θ = C θ x SAT (8)
where Γ P is a non-sloshing disturbing torque, Γ C is the control torque and θ is the satellite attitude. In order to also estimate Γ P we extend the state vector and, without any information, we consider that : ΓP = 0 (9) By further analyzing the identification results, it appeared that B S and C S can be approximated by linear functions respectively of A S and K S :

B S = α AB A S + β AB (10) C S = α KC K S + β KC (11)
Using Equations 5-11 the liquid-filled satellite can be described by the following uncertain LPV system :

ẋ = A(α(t))x + B u Γ C + [0 1 0 . . . 0] T Bw w (12) θ Γ D = C m C z x (13)
where :

α(t) = (α A (t), α K (t)) = (A S [Ω(t), Ω(t)], K S [Ω(t), Ω(t)]) (14)
Γ D = Γ F + Γ P (15) x = [x F x SAT Γ P ] T (16)
Because of reaction wheels limitations which bound the control torque capacity, restricted variations of (Ω(t), Ω(t)) are necessarily considered :

|Ω(t)| ≤ S C Ω (17) | Ω(t)| ≤ S C Ω (18)
where Ω and Ω are the spacecraft maneuver capabilities, and S c a security coefficient (equal to 1.5 for this study). This permits to characterize a narrowed definition domain for A S and K S . Thus, the time-varying vector α(t) takes its values in a polytope P of 15 vertices P i , i ∈ {1, 2, . . . , 15} : α(t) ∈ P := Co{P 1 , P 2 , . . . , P 9 } (19)

The vertices are the extreme values of α(t). Remark 1. Due to the filtering effect of the low-pass actuators, the parametric variations appear only in the A matrix of the system. Note also that the use of α as the system parameter, instead of (Ω, Ω), has the following advantages :

-A(α) is a linear function of α which emphasizes the obvious LPV nature of the system and will simplify both the observer design and stability analysis, -A S , B S , C S and K S do not need to be explicitly written as functions of (Ω, Ω)

3. A ROBUST H ∞ BASED OBSERVER DESIGN
The LPV model of the liquid-filled satellite, given by ( 12) and ( 13), is now used to design a sloshing torque observer robust to model disturbances.

Problem statement

The aim is to enhance attitude control using the estimate of disturbing torques to decouple the satellite from the sloshing dynamics and other perturbations, independently of any existing controller. An LPV observer has then to be designed in order to provide a reliable estimation of the disturbing torque than can next be easily canceled from the control input. This observer is described by :

ẋ = A(α(t))x + B u Γ C + L(α(t))(θ -θ) (20) = (A(α) -L(α)C m ) A Obs x + [B u L(α)] B Obs [Γ C θ] T (21) ΓD = C z x + [0 0] D Obs [Γ C θ] T (22)
where x and ΓD respectively denote the estimation of x and Γ D , and L(α) is the observer gain to be computed. The dynamics of the state error is represented by the system :

(S)      ˙ = A Obs x + B w w, = x - x z = C z = Γ D -ΓD (23) (24) (25)
To ensure an efficient compensation, the estimated disruptive torque needs to be accurate in spite of model disturbances captured by w. It should also take into account the fact that the compensation is realized by actuators whose dynamics introduce rather small but not negligible delays. As is clarified next, this can be achieved by the introduction of a small derivative term in the signal to be estimated.

Tuning process and resolution aspects

Because A(α) is a linear function of α, we can write :

A(α) = A 0 + α A A A + α K A K (26)
We then propose to search a structured observer gain :

L(α) = L 0 + α A L A + α K L K (27)
The system (S) has an affine LPV structure given by ( 26), hence a polytopic model with 15 vertices can be easily deduced :

α = 15 i=1 β i P i , β i ≥ 0 and 15 i=1 β i = 1 (28) S(α) = 15 i=1 β i S(P i ) (29)
As stated by [START_REF] Biannic | Missile autopilot design via a modified lpv synthesis technique[END_REF], this approach is suitable to be addressed by a H ∞ multi-model robust design techniques on the 15 LTI models (S i≤15 ), that corresponds to the LPV system frozen at the vertices P i≤15 . The problem is then to find the gain matrices L 0 , L A and L K such that the observer/error dynamics is quadratically stable over P and ||z|| 2 < ||w|| 2 to ensure robustness to model disturbances.

Thanks to the flexibility of nonsmooth optimization algorithms implemented in the systune routine of the Matlab T M Robust Control Toolbox (see Apkarian andNoll (2006) Apkarian et al. (2014)) it is possible to compute bounded gains L 0 , L A and L K so as to minimize the estimation error as further detailed and to constrain the observer/error dynamics. For implementation purposes, the following constraints have been defined :

• Minimum decay rate : 0.001 rad/s • Minimum damping ratio : 0.7

• Maximum observer frequency : 10 rad/s • Absolute value of gains < 2

In order to compensate delays introduced by the actuators, the output torque z to be estimated is augmented by a derivative term as follows :

z = (Γ D -ΓD ) + E( ΓF -ΓF ) (30
) where the gain E is tuned according to the characteristics of the actuator.

In order to minimize the steady-state estimated torque error, the error signal and the model disturbance are weighted respectively by a low-pass transfer function W z (s) and a constant filter W w (s) = 0.01 :

W z (s) = W z,0 0.1 s + 0.1 , W z,0 = 2.79 (31)
The filter W z (s) is designed such that the transfer between the model disturbance w and the output z is as small as possible given the observer gains constraints, mainly in low-frequency (assuming that the model disturbance is a low-frequency signal). The filter W w (s) is equal to the maximum amplitude of w, note that the value 0.01 is almost ten times higher than the sloshing torque maximum amplitude, which ensures an effective rejection of the model disturbance.

IMPLEMENTATION AND RESULTS

The required attitude control performances are inspired by [START_REF] Pittet | Demeter: A benchmark for robust analysis and control of the attitude of flexible micro satellites[END_REF], that describes a benchmark corresponding to the DEMETER satellite bus :

-Pointing steady-state error < 0.04 deg -Pointing rate steady-state error < 0.1 deg/s -Angular momentum < 0.12 Nms -Control torque < 0.005 Nm

We consider a satellite with an inertia I z = 30 kg.m 2 , controlled by a satisfying Proportional-Derivative controller that respects these constraints in the absence of sloshing :

Γ C = 0.3553δ θ + 6.2845δ Ω (32)
where δ θ is the attitude error and δ Ω is the angular velocity error. In the case of the DEMETER benchmark the velocity is pseudo-derived from the attitude measurement provided by a star tracker. Here, it is given as an additional output of the state observer designed above.

The actuator is a reaction wheel modeled by the following transfer function :

RW S(s) = 1.2s + 0.76 s 2 + 2.4s + 0.76 (33)
To get faster responses we also add the torque guidance profile Γ d in a feed-forward path. The closed-loop system is illustrated by Figure 1.

Quadratic stability of the parameter-varying observer

As stated above, the proposed approach, based on LTI design tools, offers great flexibility but no theoretical guarantee regarding time-varying stability. The latter should then be checked a posteriori. This is achieved here with the help of quadratic Lyapunov functions.

We focus beforehand on the parameter-varying stability analysis of the observer dynamics. This is easily verified, independently of the rate of variation of the parameters, if a symmetric positive definite matrix P Obs > 0 can be found such that : A Obs (α) T P Obs + P Obs A Obs (α) < 0, ∀α ∈ P (34) which, in our context, using ( 28) and ( 29) reduces to 15 Linear Matrix Inequalities (LMI) :

A Obs (P i ) T P Obs + P Obs A Obs (P i ) < 0, i = 1, . . . , 15 (35) Since the observer has 7 states, the above LMI problem exhibits 7 × 8/2 = 28 decision variables and was easily solved using the standard feasp LMI solver available with the Matlab Robust Control Toolbox. It can then be concluded that the observer remains stable for arbitrarily fast variations of the parameters inside the polytope P.

Quadratic stability of the parameter-varying closed-loop

Let us now focus on the parameter-varying closed-loop plant described in Figure 1. As it results from a linear interconnexion of LTI and LPV systems that affinely depends on α, the closed-loop dynamics are described by a matrix A CL (α) ∈ R 13×13 with the same properties.

Simulation results

The parameter-varying observer performances are compared to an observer with a static gain and an observer designed on a rigid model of the spacecraft (that assume ΓD = 0, as we did for Γ P ). The design procedure for these alternative observers is also based on a H ∞ multimodel design technique with the same constraints and filter W w (s). The value of W z,0 in the filter W z (s) (31) is taken such that the H ∞ norm of the weighted transfer from w to z is equal to 1. Thus W z,0 = 2.41 for the static gain observer and W z,0 = 99 for the rigid model observer. Remark 3. The Simulink model used for the simulations does not use the linear approximations ( 11) and ( 10), hence the parameters used by the observers and the ones used by the sloshing torque model are slightly different. Figure 3 shows the torque error, defined as the difference between the estimated torque filtered by the actuator and the actual torque; and figure 2 shows the attitude error. Both figures reveal that the static gain observer and the parameter-varying observer have very good performances, despite the limiting dynamics of the actuator and design constraints. By using these observers to mitigate sloshing effects the attitude error requirement is respected sooner and for a longer time. Without compensation the attitude error is much higher. The rigid model observer, despite a lower torque error overshot, has lower performances and is even less efficient than the P.D. controller alone. Remark 4. The angular velocity error requirement is respected by all of the presented observers, yet the static gain observer and the parameter-varying observer are the most efficient. Remark 5. Despite similar performances, the parametervarying observer is preferred to the static gain observer as it is more robust, indeed its W z,0 and S C threshold values (at which the quadratic stability cannot be verified anymore) are higher.

CONCLUSION AND FUTURE WORK

In this paper we have presented a new way to model sloshing disturbing torque as an LPV system. This model has been successfully exploited to design an LPV torque observer that allows perturbation compensation in order to enhance an already existing satisfying controller, which has been designed without sloshing. This observer has been proven, along with the parameter-varying closed-loop, to be quadratically stable over the parametric domain.

It should be emphasized that the sloshing model used in this paper was identified from data that correspond to an half-filled (worst case scenario) wall less tank which is moreover slightly larger than the one usually fitted to DEMETER satellite. Despite such adverse conditions, the proposed compensation technique succeeded in considerably reducing the attitude error to acceptable values. It is therefore likely that the use of such attitude control systems with enhanced slosh disturbance rejection capacity could permit to reduce tank complexity and mass. However, it should also be noted that the control torque and angular momentum maximum values of the reaction wheels are sometimes exceeded, depending on the sloshing torque model initial conditions. Hence future work will address this issue by using reference governors technique [START_REF] Kolmanovsky | Reference and command governors: A tutorial on their theory and automotive applications[END_REF]] in order to adapt, when necessary, the reference to be tracked. Motivated by interesting simulation results, future work will also focus on stability analysis in the case where the observer parameter α Obs is different from the sloshing torque model parameter α.

Fig. 1 .

 1 Fig. 1. Parameter-varying closed-loop model block diagramThus A CL (α) ∈ Co{A CL (P 1 ), . . . , A CL (P 9 )}. The stability analysis of the closed-loop dynamics follows the same strategy than the observer stability analysis. Since the closed-loop has 13 states, the LMI problem now exhibits 13×14/2 = 91 decision variables. As the problem has been solved, we can conclude that the closed-loop with sloshing torque compensation remains stable for arbitrarily fast variations of the parameters. Remark 2. When the security coefficient S C exceeds a threshold value, quadratic stability cannot be proved anymore. We then have to rely on Parameter-Dependent Lyapunov Functions (PDLF) and a µ-test such as presented in[START_REF] Biannic | Linear parameter varying analysis of switched controllers for attitude control systems[END_REF].

Fig. 2 .

 2 Fig. 2. Performances -attitude error ( • )


Ayham Kassab

Jean-Marc Nicod

Laurent Philippe

Veronika Rehn-Sonigo

Green Power Constrained Scheduling for Sequential Independent Tasks on Identical Parallel Machines

Keywords: Green power, Constrained scheduling, Parallel computing ://theshiftproject.org

Energy consumption is a major aspect to consider when designing large scale high performance computing HPC systems. Integrating renewable energy sources to the power supply of an HPC system is an efficient solution to lower its carbon footprint, but it is one faced by challenges since the power production of most renewable sources is variant while the power consumption of the system varies with the workload. Advanced workload management techniques in combination with powering down idle machines allow to increase the efficiency of this solution. We tackle here the problem of scheduling independent tasks on a multi-machine platform that is exclusively run with green energy. We propose different power constrained scheduling algorithms, and evaluate them through an experimental study on an HPC model that considers the possibility to switch machines on or off.

Introduction

The growing dependency on Information and Communication Technology (ICT) services is pushing service providers to build bigger and more energy consuming ICT structures in order to maintain the quality of their services. Studies estimate that by 2030 ICT will be responsible for about 20% of global electricity consumption 1 and can produce up to the quarter of the CO 2 emissions worldwide [START_REF] Sg Andrae | On global electricity usage of communication technology: trends to 2030[END_REF].

As a result, the energy efficiency of large scale ICT structures has been the focus of many research projects over the last years. Most of these efforts focus on reducing the system's energy consumption. However, even if the energy consumption is reduced, a system still has a carbon footprint as long as it relies on brown energy. Another "greener" approach consists of reducing the carbon footprint by integrating renewable (CO 2 -free) energy sources, such as solar panels, wind turbines or fuel cells, in the system's power supply.

Renewable sources can be used either by signing green energy contracts with an electricity provider or by installing on-site renewable sources which, unlike a green contract, guarantees an exclusively green energy supply. Using on-site renewable energy sources however presents a challenge as both the system's workload and its power supply are intermittent and vary over time. This means that the availability of the power supply does not guarantee to allow the execution of all the submitted computational demands at a certain time. As a consequence the need for new workload and machine management solutions has arisen in order to optimally use the instantaneous available green power. The main challenge is to cope with the available power constraints. In [START_REF] Kassab | Scheduling independent tasks in parallel under power constraints[END_REF], we proved that scheduling independent tasks within a given power envelope on one machine is already NP-hard. On multi-machine platforms, a machine may also be switched on or off to avoid that it consumes static power when idle.

This work tackles the problem of scheduling tasks on a multi-machine HPC platform where the computing power comes from renewable sources. Therefore we consider an available predicted power envelope that varies over time. The parallel computational platform consists of multiple multi-core machines that can be turned on or off separately. The workload is a set of independent sequential tasks. The contributions of the paper are the following:

• We propose and discuss different scheduling heuristics for HPC systems that take power constraints into consideration. We assess their performance in extensive simulations with different workload models.

• We show the impact of the on/off model for the machine management on the scheduling solutions.

• We provide a comparison of the heuristics to use depending on the parameters of the scheduling situation (available power envelope and task characteristics).

The rest of this paper is organized as follows. Studies on scheduling problems in parallel HPC platforms and in systems that run on renewable power are presented in Section 2. The models used in the paper are detailed in Section 3. Section 4 presents the power constraint aware heuristics. In Section 5 we discuss the experimental study and the obtained results. Finally section 6 presents our conclusion and future work.

Related Work

This work addresses HPC systems powered by renewable energy sources as a way to reduce ICT's carbon footprint. Its aim is to find an appropriate scheduling strategies to carry out the workload management process in such systems. Even if our contribution targets parallel architectures of HPC systems, this section focuses on research work that tackles scheduling problems in large scale ICT structures.

The three most common types of large scale ICT structures are data centers, HPC systems and clouds. These systems differ from one another in architecture, IT equipment and types of submitted jobs. Some research works about scheduling in data centers and cloud environments are based on task duplication [START_REF] Ahmad | On exploiting task duplication in parallel program scheduling[END_REF] or virtualization techniques [START_REF] Brey | Using virtualization to improve data center efficiency. the green grid[END_REF] to reduce energy consumption. Mathew et al. have compared and analyzed scheduling strategies used in data centers [START_REF] Mathew | Study and analysis of various task scheduling algorithms in the cloud computing environment[END_REF], some of which may have guarantees of robustness [START_REF] Gandhi | Autoscale: Dynamic, robust capacity management for multi-tier data centers[END_REF] or optimality [AJ + 14]. The addressed problem is multi-objective for which Iturriaga et al. have proposed in 2016 scheduling strategies for green-powered federation of data centers [START_REF] Iturriaga | Multiobjective workflow scheduling in a federation of heterogeneous green-powered data centers[END_REF]. In this context many scheduling criteria are studied as the number of dead line violations (SLA) [START_REF] Nayak | An enhanced deadline constraint based task scheduling mechanism for cloud environment[END_REF] or the request flow [START_REF] Kllapi | Schedule Optimization for Data Processing Flows on the Cloud[END_REF].

In the HPC context, where tasks are compute intensive, the makespan is a decisive criterion. In some cases, as grids or cloud computing environments, HPC systems are considered as heterogeneous platforms. before the extensive use of graphical processor, researchers were already interested in scheduling tasks on heterogeneous parallel platforms [START_REF] Wang | Task matching and scheduling in heterogeneous computing environments using a genetic-algorithm-based approach[END_REF][START_REF] Haluk Topcuoglu | Performance-effective and lowcomplexity task scheduling for heterogeneous computing[END_REF]. In this context, theoretical results are proposed on the complexity of tasks scheduling algorithms [START_REF] Ilavarasan | Low complexity performance effective task scheduling algorithm for heterogeneous computing environments[END_REF]. Some works consider homogeneous platforms [START_REF] Edwin Sh Hou | A genetic algorithm for multiprocessor scheduling[END_REF][START_REF] Walter | Analyzing Various Aspects of Scheduling Independent Jobs on Identical Machines[END_REF] since they are a more relevant model for HPC clusters. We thus also consider such homogeneous systems for the experimental part of our work that target HPC clusters.

The focus of the paper is also on power constraints when scheduling computational tasks. Previous work in this context has payed attention on reducing either power consumption [START_REF] Verma | Power-aware dynamic placement of hpc applications[END_REF][START_REF] Bunde | Power-aware scheduling for makespan and flow[END_REF] or energy consumption [ABRGR15, WKC + 13] of an HPC platform. Minimizing the power or energy consumption in HPC systems is however complex since it is conflicting with the makespan criterion. It leads to multi-objective optimization problems [START_REF] Balaprakash | Multi objective optimization of hpc kernels for performance, power, and energy[END_REF] that are even more difficult to solve than the previous ones and only provide a trade-off [START_REF] Lam | Improved multi-processor scheduling for flow time and energy[END_REF][START_REF] Park | Managing energyperformance tradeoffs for multithreaded applications on multiprocessor architectures[END_REF]. Moreover optimizing the power or energy consumption does not always mean a reduction of the ICT platform because of the rebound effect. [START_REF] Pierson | Green task allocation: taking into account the ecological impact of task allocation in clusters and clouds[END_REF] highlighted that reducing power consumption may lead to increasing the number of tasks to be processed. On the other hand, when considering the energy exclusively coming from renewable sources, the available power at any given time is a more important factor than the total available energy on a time range since the renewable energy is available anyway and theoretically free. In this case, the power production is limited and intermittent. The challenge is to optimize the use of an available power envelope when scheduling tasks as soon as possible and it can also been solved by minimizing the makespan [START_REF] Kassab | Scheduling independent tasks in parallel under power constraints[END_REF][START_REF] Kassab | Assessing the use of genetic algorithms to schedule independent tasks under power constraints[END_REF].

GreenSlot [GHL + 15] manages parallel batch jobs in a data center powered by both a green energy source and the electrical grid. The jobs are divided into critical and non-critical and the scheduler exploits the flexibility of non-critical jobs to produce a schedule matching with the renewable power production. The system is however connected to the grid to avoid deadline violations when the renewable power supply is not high enough. Caux et al. propose a genetic-based algorithm to minimize violations of task due dates in a cloud environment [START_REF] Caux | Smart Datacenter Electrical Load Model for Renewable Sources Management[END_REF], while respecting the renewable power envelope and the resource constraints [START_REF] Caux | It optimization for datacenters under renewable power constraint[END_REF] and without considering the grid power. Lei et al. propose in [LWZ + 16] a genetic algorithm for solving a multi-objective energy-efficient scheduling problem on a data center that is partially powered by renewable energy sources. The proposed algorithm addresses the minimization of both the makespan and the total energy consumption objectives. The work presented here tackles HPC systems solely powered by on-site renewable sources. The objective is not to reduce the energy consumption but rather to minimize the makespan under power availability constraints.

Model

We define here the elements of the studied model.

Power model: as the power provisioning of the platform solely comes from renewable sources, its production is not stable and varies over time. For technical reasons the power has to be maintained at a constant level (setpoint), at least during a time interval. The available power is thus modeled by X time intervals ∆ x of length δ x with an available power of Φ x . This power is shared by all the machines of the platform whose cumulative power consumption during a time interval ∆ x is constrained by the level of available power Φ x .

Task model: we consider a set T = {T 1 , T 2 , . . . , T n } of n tasks T i . According to [SS09, GGT15], the power consumption varies from one task to another depending whether the task intensively computes or not. Each task T i is defined by its processing time p i and its power consumption ϕ i .

Machine model: the platform is a set M = {M 1 , M 2 , . . . , M m } of m machines M j , each with nb cores cores. Since the total available power is variable and constrained, machines are powered off as soon as they become idle or when the available power is too low. Powering on a machine (Son j ) takes a delay T on j during which the power consumption of the machine equals to P on j . When running, a machine consumes at least its static power P stat j . Then, it takes a delay T off j , during which the power consumption of the machine equals to P off j , to switch off the machine (Soff j ). The cores of a machine are available only when this machine is powered on.

T 1 T 2 T 4 T 5 T 3 ∆ 1 ∆ 2 ∆ 3 ∆ 4 ∆ 5 ∆ 6 ∆ 7 ∆ 8

Son1

Soff 1

P stat1

Tasks on M1

Son2

Soff 2

P stat2

Tasks on M2 t Φ(t)

Figure 1: Task scheduling on machines under power constraints Problem definition: the problem tackled here is to statically schedule the tasks on parallel machines under limited power constraints, without preemption, to minimize the total completion time Cmax. Note that, for simplicity reasons, we consider sequential independent tasks in order to have a simple task model without communications nor precedence relations and identical machines. One of the interests of this model is to consider switching machines on and off when the power supply is not high enough to turn on all the machines.

Figure 1 illustrates the case where five tasks are to be run on a platform with dual-core machines. In interval ∆ 1 there is enough power to start machine M 1 and run tasks T 1 and T 2 but not to switch a second machine on. In interval ∆ 2 , as the available power increases, machine M 2 is started but only the tasks T 3 and T 4 can be run within the power envelope. Once machine M 1 is finished with its tasks, it is switched off since the available power does not allow to run tasks on it. Once it is off, the released power allows to run task T 5 on M 2 .

Complexity: in [START_REF] Kassab | Scheduling independent tasks in parallel under power constraints[END_REF] we prove that finding the shortest makespan when scheduling a set of independent sequential tasks on a multi-core machine with power constraints is a NP-Hard problem. Since this problem is an instance of the problem studied here (special case where T on j = P stat j = T off j = 0, ∀1 ≤ i ≤ m) then this problem is also NP-Hard.

Heuristics

In this section we propose heuristics to compute schedules for the studied problem. Two classes of heuristics are proposed, list based heuristics and power envelope partition based heuristics. Both kinds of heuristics use the same task to interval assignment algorithm that also manages the on/off switching of machines.

Task to interval and machine assignment

Algorithm 1: The P laceT ask() function 1 PlaceTask (T i ) Data: Boolean placed, init to false Result: sTime, time when the task is started At the beginning of the run time, all machines are switched off. The decision to switch a machine on or off is based on two factors: the computational demand and the power supply constraints. The task to interval assignment is done by the P laceT ask function. This function is responsible for task to machine allocation, in addition to task to interval assignment, assuming that a machine can be in one of 4 states: on, off , Son (switching on) or Soff (switching off). The function takes one task at a time and schedules it as early as possible on the first suitable machine under the following rules (see Algorithm 1):

2 begin 3 x ← 0 4 while ¬ placed ∧ x ∈ X do 5 machine ← findAvailableMachine(M, ∆x) 6 if machine = nil then 7 placed ← checkPowerAvaibility(∆x, p i , ϕ i ) 8 else 9 machine ← newMachine(M) 10 placed ← checkPowerAvaibility(∆x, T on j , P on j ) ∧ checkPowerAvaibility(∆x + T on j , p i , ϕ i + P stat j ) 11 if ¬ placed then x ← x + 1 12 if machine.state = Soff then
• No preemption nor job migration are allowed, therefore if a task starts executing on a machine, it should finish the execution on the same machine. The checkP owerAvaibility function checks the availability of cores and power during enough time ahead to execute the task.

• If no core is available, a machine must be started, if possible. The function first checks that the power envelope is enough to start the machine then if it is possible to run the task after this boot time with enough power for both the machine static power consumption P stat j and the task power consumption ϕ i .

After placing a task, the scheduler looks for possible optimizations in the start and stop times. Leaving a machine on reduces the delays and energy losses caused by its booting and shutdown while keeping a machine on for too long might lead to unnecessary static power waste. The machine should stay turned on just enough time to finish the execution of all tasks, the issue here is thus how to determine in advance how long that period is before executing the tasks.

• If a task is assigned to a machine in Soff state, performing a shutdown, during the first interval of its execution ∆ start , the shutdown is canceled, and the execution of the task then starts as soon as possible.

• If a task is assigned to a machine that is switching on or is in an "off" state at ∆ start , then a delay is applied while the machine boots, and the execution of that task starts at ∆ start + T on j .

• To avoid unnecessarily reboots of machines, before switching a machine M j to off, the P laceT ask function looks ahead in T off j for a machine switch on, if yes, the machine is kept on. Symmetrically, when switching a machine on, the function looks back for a switch off in T on, if yes, then the machine is kept on.

List based heuristics

List scheduling, one of the most common algorithms in scheduling, can give good solutions within low time complexity for many scheduling problems. A list algorithm consists of two steps: sorting the tasks based on a priority value then allocating the tasks, according to this order, to a resource and schedule it for execution as early as possible. The second step is carried out by the P laceT ask function.

Our problem can be described as an optimization problem whose objective (makespan minimization) lay on a time axis, while the scheduling constraints (the power availability versus the power consumption) lay on a power axis. It is thus a two dimensional problem (time and power dimensions). For this reason we test priorities that consider the time axis, priorities that consider the power axis and priorities that consider both axis simultaneously. The list based heuristics that use those priorities are the following: LPT for Largest Processing Time (p i ) first, LPN for Largest Power Need (ϕ i ) first, LPTPN, for Largest Processing Time times Power Need first (p i × ϕ i ).

The TwoQs heuristic, or Two Queues, is an adaptation of a list heuristic that alternates between two queues, namely LPTPN's queue and LPT's queue. This heuristic exploits the advantages of two priority assignments at the same time, privileging tasks that would have low priority in one queue but might have high priority in the other. The LPP heuristics, for Least Possible Places first, calculates the number of time slots in which it is possible to execute each task, then, it sorts the tasks in the queue starting with the task with the Least Possible Places first. This prioritizes tasks that are harder to schedule regardless of whether it is because they have long processing times p i or high power consumption ϕ i or both. We finally test the case where the task list is not ordered with the Random heuristic.

The list heuristics use a criterion to sort a task. We also propose a genetic algorithm that tries to find the best list order without any criterion. An individual is the order of the task list and the algorithm just evaluates the list orders and mixes them. The genetic algorithm proposed in [START_REF] Kassab | Assessing the use of genetic algorithms to schedule independent tasks under power constraints[END_REF] repeatedly applies genetic operators to modify a set of individuals. The initial population is composed of individuals generated with the list heuristics plus random individuals. First, a selection process is performed to chose individuals from the current population. The fitness of an individual is the Cmax resulting from using the task list order in the schedule. Then, the task list order of chosen individuals are shuffled by applying mutation and crossover operators. Between two generations a selection operator is applied. Several selection, mutation and cross-over operators are evaluated but we only use Order Crossover(OX) with wheel selection here.

Power envelope partition based algorithms

List algorithms place tasks one after another and do not consider grouping tasks to better use the two dimensions of the problem. We present here algorithms that generate power envelope partitions and group tasks in these partitions.

The first proposed approach, called Binary search, tries to power on the least machines as possible to spare energy consumed by Son j and Soff j . It is based on a binary search to find the best schedule. The starting points of the search are time 0 and a schedule that uses only one machine (time horizon). The algorithm then tries to find a solution by reducing the time horizon using a binary search scheme. In a time horizon the algorithm powers a first machine on, schedules as much tasks as possible on it, then powers a second machine on, schedules tasks and so on until either all the tasks are scheduled or a task cannot be scheduled. If all the tasks are scheduled the algorithm reduces the time horizon, else it increases it, using the binary search scheme. Binary search thus provides an acceptably time costly way to determine the point at which a machine is switched off, which corresponds to the minimum time horizon under which all tasks can be executed.

The second approach, called Stripe, tries to group tasks vertically. It first switches a machine on to schedule one task. It starts with the longest task T i to guarantee that the rest of the tasks can fit (on the time axis) in this range as well. Then it schedules as much tasks as possible in the time interval [∆ start , ∆ start , +p i ], where ∆ start is the time where the machine is ready to run tasks, powering on new machines when necessary and possible.

To evaluate the effect of task list orders on the last two approaches BSLPT (Binary Search -LPT), BSLPN, BSLPTPN, BSLPP, BS2Qs, stripeLPT, stripeLPTPN, stripe2Qs and stripeLPP are deployed.

Experiments

In this section we present an experimental study of the proposed heuristics. We have developed a python simulator2 presented in [START_REF] Kassab | Scheduling independent tasks in parallel under power constraints[END_REF] that offers a wide range of experimental setups on the parallel computational platform. The simulator takes as input a set of tasks and the green power production, expressed by a set of intervals of time with the available power level at each interval.

Experimental settings

The platform consists of several identical multi-core machines. We assume that the number of machines available in the platform equals to the length of the task list. This way the availability of machines is guaranteed which exempts the machine as a resource constraint, and we focus on variable green power constraints. Other experiments can be done in the future to consider both constraints at the same time. The number of cores in each machine is nb cores = 4. Based on the values measured in [DGG + 17], the static power consumption of each machine P stat is set to 95 W, the time to switch a machine on T on j = 150 s and the time to switch a machine off T off j = 6 s. The power consumption during the start up and the switch off are set to P on j = 125 W and P off j = 100 W since they are usually higher than the static power consumption.

To carry out our simulations we must produce the data that represents the two main input of the scheduling problem, namely the task list and the power envelope.

A realistic model is used to generate the power envelope that represents the various renewable power supply based on real data. This model [HNP17, HNVP19] provides hourly Φ x values according to a number of wind turbines and an area of solar panels. In order to examine the effect of the power availability on the heuristics' performance, we conduct several tests with increasing maximum power Φ x in each generated set of power envelopes. We start by setting the power generation parameters as follows: solar panels area = 2000 m 2 , pvEff iciency = 0.163, number of wind turbines = 1, and turbineP owerN ominal = 350, where pvEff iciency and turbineP owerN ominal are the efficiency factors of the solar panels and wind turbines respectively. These settings yielded power envelopes with a maximum power Φ of about 350 W, we then multiply the values of these settings by 2, 5 and 10 times to yield a maximum Φ x of around 700, 1750 and 3500 W respectively. The data used in this realistic model is collected every hour, therefore, we partition the power envelope into unified intervals ∆ x with length of δ = 1 time unit = 1/10 hour. Hence each 10 consecutive intervals have the same available power level Φ x . Each power envelope is a list of 10000 intervals.

We use two kind of task data sets for the task processing time p i . The firsts, the hypergamma sets, use the model proposed in [START_REF] Lublin | The workload on parallel supercomputers: modeling the characteristics of rigid jobs[END_REF]. Based on real workloads, the processing time distribution of HPC tasks is modeled using a hyper-gamma law with (α 1 = 4.2, β 1 = 0.94) and (α 2 = 312, β 2 = 0.03). Although realistic, this model is based on workload logs collected from only three sites which limits the experiments to the range of values of these samples. Therefore, to explore a wider set of parameters, we also use an exponential distribution law to generate p i , between p min and p max time units, to produce the synthetic workloads for the exponential sets. Since we did not find any model nor real data for the task power consumption values, we use random generation of ϕ i , between ϕ min and ϕ max , with a uniform law, in both sets.

Evaluation metric

To compare the results of simulations over different data sets with different characteristics we need a metric. Raw makespan values cannot be compared as they depend on the considered set of tasks and intervals. A set of long tasks always gives a longer makespan than a set of shorter ones. Normalizing the makespan values with the processing times is however not sufficient since the schedule also depends on the available power. Therefore, we propose a metric, called NM (normalized metric), that provides a fair comparison regardless of the power envelope. The idea is to compare the distance of the makespan to the best makespan obtained with the same data sets and to normalize this difference to the power envelope size.

NM = out ÷ total

Where out is the sum of the p i × ϕ i area of all the tasks that are scheduled after the best Cmax, and total is the total p i × ϕ i area of the task list. Good schedules have low the NM values and the best have a value of 0. This metric is fair because all heuristics are compared to each other on the same data sets and the result is normalized on both the processing time and the power consumption. We take the average of this metric value for each heuristics over 150 executions.

Results

We conduct two experiments that combines the two kinds of data sets with realistic power envelopes.

Hyper-gamma tasks and realistic power envelopes

In this experiment we use a hyper-Gamma distribution law to generate each task processing time p i that are close to real data. Each task list contains 50 tasks with a range of processing times between 1 and 500 time units (1 t.u. = 6 min). In the absence of actual data for task power consumption, each ϕ i for each task is randomly chosen with a uniform distribution law between 1 power unit and ϕ max . In this experiment ϕ max ranges between 15 and 150 power units, by steps of 15. Figure 2 presents the average value of NM for each heuristic with increasing value of maximum task power consumption ϕ max on the horizontal axis. The maximum available power Φ is 350 W. We notice that with the increase in ϕ max , the performance of most heuristics decreases, especially the heuristics that use LPT to sort the task list (blue lines). We also point out that heuristics that take the task power consumption into consideration when sorting the task list such as twoQs (red lines), LPTPN (green lines) and LPP (brown lines) outperform the LPT based heuristics when the power constraints are strict, which indicates that the power constraints are the most important criterion in this case. The reason is that the available power is not enough to execute all tasks simultaneously, which makes the decision of which task to execute first very important. Figure 3 presents the case where the maximum available power Φ is 3500 W. In this case, the tasks are less concurrent for power due to high level of available power. This problem is thus closer to the classical scheduling problem without power constraints, in which case LPT provides good performance regarding minimizing the makespan. We notice a degradation in the performance of heuristics that take the task power consumption into account such as LPN (purple lines) and LPTPN (green lines).

We point out that the light green dash-dotted line in Figures 2 and3 represents the NM of the tested GA, which uses the Order Crossover (OX) with wheel selection. We notice that this line always has the value of NM = 0. Since the NM value of each heuristics during one simulation is calculated in relation to the best Cmax produced in for simulation, this means that GA always produces the shortest makespan. The difference in performance between GA and the other heuristics increases as power constraints become stricter. On the other hand, when the power envelope provides plenty of power for task execution, all the heuristics that use LPTPN, twoQs, LPT and LPP orders provide a very close performance level to GA for tasks with low power consumption. For tasks with higher power consumption, the performance of stripe based heuristics degrades in comparison to BS and list based heuristics as we notice that LPT, BSLPT, twoQs, BS2Qs and LPP keep the closest distance to GA's performance line. In addition, even list and BS heuristics, that use LPTPN for sorting the task list, provide worse performance when the task power consumption gets higher than 50 t.u. We can then draw the conclusion that in the least strict power constraint case, the GA does not significantly improve solutions provided by LPT, twoQs and LPP for tasks that does not require a lot of power. Indeed the task processing time is a more relevant prioritizing criteria than the task power consumption even for tasks with high power consumption. We finally point out that LPN which only prioritizes the task power consumption does not perform well for the makespan minimization objective, neither does SPT which is designed for flowtime minimization. In fact, other than SPT, all the tested heuristics improve the produced schedule which is found when keeping the task list in its original random order, which proves the necessity for smart workload management in this problem. Tables 1 and 2 present the average computation time of heuristics in both cases where GA is tested. We chose LPT and twoQs orders as a representation of each heuristics class to compare to the tested GA and to LPP. We notice that GA takes much higher computation time to find a schedule. We also point out that the computation time of GA in the case where it performs much better than the other heuristics (Φ max = 350 W) is up to 5 times higher than its computation time in the case where its performance is closer to other heuristics (Φ max = 3500 W). This means that when the scheduling problem is easier (less strict power constraints), the GA reaches its stopping conditions faster (25 iterations without improvement). In general, even fast list based heuristics need ten times the computation times when the power constraints are strict to place all tasks in comparison to their computation time in the (Φ max = 3500 W) case. We finally point out that LPP is the only heuristics that does not show significant difference in computation time between the two cases of power envelope. However, it still takes 10 times longer as any other list based heuristics, due to the process of calculating in how many time slots each task can fit, before sort the task list. This process increases the time complexity of LPP which is however indifferent of the data set characteristics. In general, we notice that the computation time is rational to the length of the schedule. This is logical because the longer the schedule, the more time intervals there are to explored to find it. This is coherent with the observation that both LPP's performance and computation time are consistent with the power envelope variability. Finally we show that list based heuristics can find a schedule 60 % faster than stripe heuristics and up to 99 % faster than binary search heuristics. The tested GA on the other hand is around 18000 times slower than list heuristics while it offers a 0.05 % improvement over the performance of the best list based heuristics. Table 3 presents how many times each heuristics switches a machine on and off on average when Φ max = 3500 W. We notice that when the available power is much higher than the average of task power consumption, the number of on/off operations increases. However, when Φ max = 350 W the available power level is not enough to run more machines even when the task power consumption is at its lowest. In comparison to the average NM results, we notice that the heuristics that perform less on/off operations provide a better value for NM.

Exponential tasks and realistic power envelope

In this experiment we use an exponential distribution law to generate p i values between p min and p max ∈ [10, 100] with a step of 10 t.u. This variation in p max provides more test cases than the simulation using hyper-gamma distribution laws. As for the maximum power consumption we set ϕ max ∈ [15, 150] with a step of 15 power units.

Figure 4 plots the heuristics with the best average NM when the maximum available power Φ is set to 350 W, with increasing value of maximum task power consumption ϕ max on the vertical axis and increasing value of maximum task processing time p max on the horizontal axis.

We can distinguish two main areas on this heat-map figure. When the task power consumption ϕ max ≤ 75 W , LPN heuristics give the best performance in most cases. Unlike its poor performance with hyper-gamma tasks, LPN is able to provide good results in this experiment because of the shorter processing times, in comparison to the average processing time of around 500 t.u. in Experiment 1. The task power consumption becomes more important in this case. The right lower pink corner represents the case where the processing time increases enough to give the stripe heuristics with LPTPN order the edge. The stripe heuristics hence outperforms BS and list heuristics for task sets with long processing times and low power consumption. On the other hand, for tasks with short processing times, BS heuristics outperform both list and stripe heuristics (the left orange column). The second main area is defined by tasks with a power consumption ϕ max > 75 W . In this case the power constraints become too strict and only the heuristics using LPP ordering are able to find the best makespan. Once again, for shorter tasks, BS heuristics outperforms list and stripe heuristics. Figure 5 presents the heuristics with the best average NM when the maximum available power Φ is set to 700 W. We notice that the area where LPTPN based heuristics provide the best performance expands in comparison to the little pink corner from Figure 4. The area covers now the diagonal right half of the heat-map, while the performance of the LPN sorting policy drastically decreases as under less strict power constraints, the task power consumption becomes less relevant against the task processing time. The stripe heuristics using LPTPN order outperforms the list based LPTPN when the task power consumption is closer to their processing time. We conclude that the stripe heuristics performs better with square shaped tasks. The upper left half of the heat-map where tasks have high power consumption and processing times p i ≤ 60 t.u. is mostly dominated by LPP. When the processing time is below 25 t.u., stripeLPP gives the best performance in most of the test cases. We notice a degradation in the performance of BS heuristics in comparison to the case of Φ = 350 W . Furthermore we observe that when power constraints are less strict, lower complexity heuristics such as list algorithms and stripe algorithms provide good solutions. However, in the hard cases of the problem, only more complex algorithms can give the best solution in some test cases. This once more asserts the need for advanced workload management solutions in an HPC system powered solely by renewable power. However, the time complexity of the solution should be taken into account when finding the schedule in these systems. The computation times of the different heuristics in this experiment follow the same ranking given in Tables 1 and2 of Experiment 1.

We point out that in both previous experiments, the tested GA provides the best average NM in all the test cases. Therefore, the results presented in Figures 4 and5 exclude GA from the comparison in order to compare the performance of the rest of the heuristics. The mean values of the NM for the other heuristics on the whole experiments range between a maximum degradation of 60 % (LPT) and a lower one of 6 % (LPN) in the low power case. Surprisingly the Random algorithm did not get the worst mean value with only 24 %. In the high power case, the mean values range between 19 % (BSLPT) and 3.6 % (LPP). These results clearly show that the used heuritics must be adapted to the avalaible power.

Summary

Our results show that choosing the right order to sort the task list depends on the characteristics of both the submitted task list (how much power does the execution of tasks consume ?) and the power envelope (how strict are power constraints ?). When the available power level is not high enough to run all the machines of a platform simultaneously, deploying a good on/off mechanism does not only save static energy consumption, but can also lead to better makespan due to less rebooting delays.

Conclusion

In this paper we present and test several scheduling heuristics to solve the optimization problem of task scheduling on HPC platforms powered solely by renewable energy sources. We develop a scheduler to control the process of switching machines on and off, taking account both time and power costs. We showed the importance of the initial order of the task list to schedule and the necessity for smart workload management in order to optimize the performance of the platform under power constraints.

For future work we plan to use actual HPC workload traces integrating the energy consumption of the tasks to test our approach. We also aim at investigating the use of energy storage into the power management process. This will allow to store unused power and to use it at some later moment to cope with insufficient power production from the intermittent energy sources.

  13 machine.state ← on 14 sTime ← ∆x 15 if machine.state = Soff then 16 machine.state ← on 17 sTime ← ∆x + T off j 18 return sT ime

Figure 2 :

 2 Figure 2: Average NM, Φ max = 350

Figure 3 :

 3 Figure 3: Average NM, Φ max = 3500

Figure 4 :

 4 Figure 4: Best average NM, Φ max = 350.

Figure 5 :

 5 Figure 5: Best average NM, Φ max = 700.

Table 1 :

 1 Computation time Φ max = 350

	Algo	OX	BSLPT stripeLPT LPT
	Time (s) 24674.80 87.08	67	3.39
	Algo	LPP	BS2Qs	stripe2Qs	2Qs
	Time (s) 35.68	89.83	65.34	3.59

Table 2 :

 2 Computation time Φ max = 3500

	Algo	OX	BSLPT stripeLPT LPT
	Time (s) 6157.18 49.04	0.71	0.32
	Algo	LPP	BS2Qs	stripe2Qs	2Qs
	Time (s) 34.59	49.35	0.81	0.35

Table 3 :

 3 Number of on/off, Φ max = 3500

	Algo	OX	Random BS2Qs LPT
	ϕmax = 15	12.5 12.7	12.1	11.9
	ϕmax = 50	12.1 12.3	11.5	11.45
	ϕmax = 100 11.2 11.5	10.25	10.2
	ϕmax = 150 10.2 10.5	2.55	2.5

Source code available at http://github.com/laurentphilippe/greenpower

Acknowledgments

This work was supported in part by the ANR DATAZERO (contract "ANR-15-CE25-0012") project and by the Labex ACTION project (contract "ANR-11-LA BX-01-01"). Computations have been performed on the supercomputer facilities of the Mésocentre de calcul de Franche-Comté -Besançon.