Characterization of iron and manganese precipitates

from an in situ ground water treatment plant.

E Mettler, Mustapha Abdelmoula, E. Hoehn, R Schoenenberger, P Weidler,

U. von Gunten

To cite this version:

E

  Mettler, Mustapha Abdelmoula, E. Hoehn, R Schoenenberger, P Weidler, et al.. Characterization of iron and manganese precipitates from an in situ ground water treatment plant.. Ground Water Monitoring and Remediation, 2001, 39 (6), pp.921-30. hal-01946075


Malek Zaibi

Habib Cherif

Gérard Champenois
email: gerard.champenois@univ-poitiers.fr

Bruno Sareni

Xavier Roboam

Jamel Belhadj

Sizing methodology based on design of experiments for freshwater and electricity production from multi-source renewable energy systems

Keywords:

come

Introduction

Around the world, large-scale development of renewable energy technologies is giving new opportunities to regions that lack fresh water and electricity. Even regions rich in fossil energy are beginning to worry about energy efficiency, long-term sustainability and environmental friendliness [START_REF] Aleisa | Ecological-economic modeling to optimize a desalination policy: case study of an arid rentier state[END_REF]. Today, many papers deal with systems for generating electrical energy from renewable energies: development of structures and their optimal sizing based on environmental and/or economical considerations [START_REF] Kanchev | Emission reduction and economical optimization of an urban microgrid operation including dispatched PV-based active generators[END_REF][START_REF] Mereia | Optimization of an off-grid hybrid PV-Wind-Diesel system with different battery technologies using genetic algorithm[END_REF]. In this regard, it is necessary to select and configure the optimal life cycle calibration of all hybrid renewable energy systems to operate at minimum economic and energy costs (embodied energy) while maintaining reliability of the system. From electrical energy, often the reverse osmosis process is used, because the need is to supply booster pumps and to fill tanks [START_REF] Ghaffour | Renewable energy-driven desalination technologies: a comprehensive review on challenges and potential applications of integrated systems[END_REF][START_REF] Gökçek | Technical and economic evaluation of freshwater production from a wind-powered small-scale seawater reverse osmosis system (WP-SWRO)[END_REF]. But intermittent renewable sources require the establishment of storage elements and/or mixing several sources. Many papers have already been published in this context. A study in Australia shows, when the distribution network is present, adding a wind turbine, PV and not using batteries reduces the financial cost of water production [START_REF] Fornarelli | Selecting an economically suitable and sustainable solution for a renewable energy-powered water desalination system: a rural Australian case study[END_REF]. Another in Iran, on a remote site not really favorable for the wind turbine, shows that it is more profitable to use only PV with batteries [START_REF] Maleki | Weather forecasting for optimization of a hybrid solar-wind-powered reverse osmosis water desalination system using a novel optimizer approach[END_REF]. Thus, the context of the site is a very important factor in the choice of the structure of the freshwater production system.

Regarding the design, sizing and optimization of the power systems based on renewable energy sources, several approaches are proposed using different indicators and configurations. For hybrid wind-solar power systems, linear programming techniques [START_REF] De Souza Ribeiro | Isolated microgrids with renewable hybrid generation: the case of Lençóis Island[END_REF][START_REF] Long | Configuration optimization and analysis of a large scale PV/Wind system[END_REF], pattern search based on SMCS (Sequential Monte Carlo Simulation) [START_REF] Arabali | Stochastic performance assessment and sizing for a hybrid power system of solar/wind/energy storage[END_REF], particle swarm optimization algorithm [START_REF] Ma | Multi-objective optimal configuration method for a standalone wind-solar-battery hybrid power system[END_REF], bees algorithm [START_REF] Maleki | Design and optimization of autonomous solar-wind-reverse osmosis desalination systems coupling battery and hydrogen energy storage by an improved bee algorithm[END_REF] have been applied under economic and technical indicators. An optimal sizing using a linear programming of photovoltaic power plants based on the optimal participation in electricity markets has been developed in Ref. [START_REF] De Ibarra | Co-optimization of storage system sizing and control strategy for intelligent photovoltaic power plants market integration[END_REF]. In Ref. [START_REF] Dahmani | Optimization and reliability evaluation of an offshore wind farm architecture[END_REF], a method employs the genetic algorithm to reduce the total cost of an offshore wind farm by optimizing its architectural design. A recent paper compares several optimization approaches for reverse osmosis water desalination system with solar and wind hybrid energy [START_REF] Peng | Optimization of a hybrid system for solar-wind-based water desalination by reverse osmosis: comparison of approaches[END_REF]. A robust solution method proposed in Ref. [START_REF] Mayhorn | Multi-time scale coordination of distributed energy resources in isolated power systems[END_REF] used DIgSILENT Power Factory software for optimally coordinating a mix of distributed energy resources in the presence of high wind penetration to simultaneously minimize operating costs and maximize the utilization of wind turbine generation.

Many sizing optimization publications optimize life cycle cost [1-7,9-13] and take into account weather conditions (wind speed, solar radiation and temperature) for one year [START_REF] Gökçek | Technical and economic evaluation of freshwater production from a wind-powered small-scale seawater reverse osmosis system (WP-SWRO)[END_REF][START_REF] Fornarelli | Selecting an economically suitable and sustainable solution for a renewable energy-powered water desalination system: a rural Australian case study[END_REF][START_REF] Maleki | Weather forecasting for optimization of a hybrid solar-wind-powered reverse osmosis water desalination system using a novel optimizer approach[END_REF][START_REF] Maleki | Design and optimization of autonomous solar-wind-reverse osmosis desalination systems coupling battery and hydrogen energy storage by an improved bee algorithm[END_REF][START_REF] Layadi | Modeling and design optimization of an autonomous multisource system under a permanent power-supply constraint[END_REF][START_REF] Abbes | Life cycle cost, embodied energy and loss of power supply probability for the optimal design of hybrid power systems[END_REF]. In this paper, modeling is done on the amount of embodied energy (EE) for the life cycle of each element of the system, from meteorological records (wind speed, solar radiation, and temperature) over a year and for isolated sites. Sizing optimization is always done using optimization algorithms that require a high CPU time for the implementation of the optimization algorithms that depends on the modeling used to represent the operation of the system. Some authors use a dynamic simulator including the physical equations of each element, weather data and load equations. The resolution is done with a computing step of several minutes or hours. Thus, one year data resolution represents several thousand computation loops for one parameter vector. So, global optimization can take a CPU time of several days if the system is a bit complex. The goal of this paper is to propose a new modeling based on meta-models that replaces the dynamic simulator with an equation vector that links the outputs with the parameter vector in the optimization process. The quality of the meta-models becomes a crucial point for the quality of the results and it is also important to minimize the time to establish these meta-models. Early experiments have shown that the Design Of Experiments (DOE) approach can give good results. The application of the DOE method in several areas has been discussed by many authors [START_REF] Myers | Response Surface Methodology: Process and Product Optimization using Designed Experiments[END_REF][START_REF] Maussion | Design of Experiments in electrical engineering: applications in control and modeling[END_REF], but only a very few attempts have been made to integrate the DOE in systemic design. In a recent study, a modeling approach is presented by Ref. [START_REF] Layadi | Modeling and design optimization of an autonomous multisource system under a permanent power-supply constraint[END_REF] to size an autonomous multi-source system with battery storage and a diesel generator. It is also used in Ref. [START_REF] Zaibi | A hybrid spline metamodel for photovoltaic/wind/battery energy systems[END_REF] for a photovoltaic/wind/Battery energy system with storage to investigate a meta-model by hybrid spline interpolation. This study contributes to integrate a sizing methodology with DOE to optimize a freshwater and electricity production by multi-source renewable energy systems located in remote areas.

This paper gathers the papers already made in this area by the same authors by presenting the complete study with the results obtained and which integrates a new modeling of the reverse osmosis unit with its motor pump for a salinity of the water: 6 g/l (brackish water from southern Tunisia (see Appendix A)). This last model uses only one parameter, which is the cubic meter per day (CMD), to limit the number of parameters in order to reduce the complexity of the system. The paper is organized as follows: after the Introduction, Section 2 describes the system with its modeling, presents the methodology to realize the optimization by implementing a dynamic simulator or meta-models. Section 3 shows the results and discusses the results obtained. The paper ends with a conclusion, one appendix and the bibliographic references.

Description and methodology

System description

Architecture

The electricity acquired from photovoltaic panels (PV) wind turbines (WT) will be used to feed the motor-pumps of a hydraulic process (water pumping and reverse osmosis desalination unit) and other electrical house loads. The system has two types of storage: battery energy storage and hydraulic storage in water tanks (brackish water storage and freshwater storage). The global architecture of the system, shown in Fig. 1, corresponds to the application described for the isolated areas. The different subsystems are coupled to the DC bus with different converters (DC/DC, AC/DC or DC/AC).

The hydraulic loads are composed of a first motor-pump 1 used to pump brackish water from well and to store it in a first tank and a second motor-pump supplied by the brackish water (6 g/l (see Appendix A)) to the Reverse Osmosis (RO) desalination unit to produce freshwater. This freshwater is stored in a second tank without pumping.

Power and water flow models

This part is devoted to the power and water flow models of the investigated system. In the context of optimizing the size of the system, it is important to specify all energy models with significant expressions to reduce the running time of the optimization program. For all renewable energy generator, the maximum power is taken account in the

= ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ P t η η C ρA V t ( ) 1 2 ( ) WT sc g p opt WT wind , 3 (1)
with η sc , η g static converter efficiency, generator efficiency, C p,opt optimal wind turbine power coefficient (i.e. corresponding to a perfect maximum point tracker), ρ air density (kg/m 3 ), A WT wind turbine swept area (m 2 ), V wind (t) wind speed versus time (m/s)).

2.1.2.2. Photovoltaic generator model. The optimal photovoltaic generator power (with MPPT) versus time P PV (t) (W) is proportional to the panel area A PV (m 2 ) and the solar irradiation versus time I r (t) (W/ m 2 ), and depends on total efficiency versus time η t (t) [START_REF] Hofierka | Assessment of photovoltaic potential in urban areas using open-source solar radiation tools[END_REF][START_REF] Liu | Photovoltaic dc building module based bipv system: concept and design considerations[END_REF]:

= ⋅ ⋅ P t η t A I t ( ) ( ) ( ) PV t PV r (2) with = ⋅ ⋅ ⋅ -⋅ - η t η η η β T t NOCT ( ) (1 ( ( ) ) t r p c s c c ( 3
)
with η r polycrystalline solar PV efficiency (value taken: 13%), η pc aging factor, η sc static converter efficiency, β coefficient of the temperature of the PV cells (0.004 to 0.006(°C -1 ), NOCT nominal operating cell temperature, T c (t) temperature of the PV cells versus time (°C). with the expression of T c [START_REF] Lasnier | Photovoltaic Engineering Handbook[END_REF]:

= + ⋅ - + ⋅ - T t I t T t ( ) 30 0.0175 ( ( ) 300) 1.14 ( ( ) 25) c r a (4)
T a (t) ambient temperature versus time (°C).

Electrical battery model.

For the integration of the battery in the dynamic simulator, the most simple model is a constant internal voltage E 0 with a constant internal resistance r Bat [START_REF] Copetti | Lead/acid batteries for photovoltaic applications. Test results and modelling[END_REF]:

= - ⋅ V t E r I t ( ) ( ) Bat Bat Bat 0 (5) = ⋅ P t V t I t ( ) ( ) ( ) Bat Bat Bat ( 6
)
where I Bat (t) and P Bat (t) are the battery current and power versus time (t).

The state of charge evolution versus time SOC(t) of the battery depends on the battery current versus time I Bat (t):

= - + ⋅ ⋅ SOC t SOC t t η I t t C ( ) ( Δ ) ( ) Δ Cou Bat n ( 7
)
where Δt (h) denotes the sampling step, C n : nominal battery capacity (Ah), η Cou : Coulomb efficiency for charge-discharge. Taking account the battery lifetime implies the SOC to stay into two technological limits; high and low according the following equations:

≤ ≤ SOC SOC t SOC ( ) min max (8)
with SOC min , SOC max minimal and maximal states of charge respectively.

2.1.2.4. Drawing water pump. Centrifugal pumps, with induction motor, are commonly used for pumping water from well. In this case, the motor-pump 1 is powered by three-phase power at fixed frequency for obtaining fixed speed, because the load law pressure (P r ) vs flow rate (Q 1 ) is almost constant and a variable speed would lead to a less energy efficiency. The design parameter is the electric power P 1 consumed by the motor-pump 1. So, it is necessary to develop a equation linking the flow rate Q 1 with the electric power P 1 .

From GRUNDFOS manufacturer pump datasheets and with the specifications of the hydraulic system, the range of pumps CRN 3 is the good choice. With the help of WinCAPS software [START_REF]Wincaps Software[END_REF][START_REF]Pumps software review[END_REF], it allows us to calculate different operating points depending on the hydraulic load for the different pump sizes. Fig. 2 shows hydraulic data (pressure vs flow rate) for five sizes of the CRN3 pump type. The intersection of these five curves with the hydraulic load curve gives the five operating points (A to E). WinCAPS software also allows calculating the electric power of these five operating points. With "curve fitting tool" of Matlab, a polynomial model (fourth degree) can depict these five operating points. Fig. 3 shows the characteristic of the flow rate Q 1 according to the electric power P 1 (t) of the motor-pump 1 (computing data and polynomial model). This curve is valid only for fixed hydraulic load by extrapolation from real pumps. The polynomial equation is as follows:

= ⋅ + ⋅ + ⋅ + ⋅ + Q a P a P a P a P a 1 4 1 4 3 1 3 2 1 2 1 1 0 (9)
where a i(i=0..4) :

(

a 0 = -3 m 3 /h, a 1 = 1.5E-02 m 3 /h/W, a 2 = -1.5E-05 m 3 /h/W 2 , a 3 = 8E-09 m 3 /h/W 3 , a 4 = -1.6E-12 m 3 / h/W 4 ).
2.1.2.5. Water pumping and its desalination system. Freshwater production is achieved by using reverse osmosis (RO) membrane from the brackish water of tank 1. So the motor-pump P 2 allows boosting the permeate (fresh) water flow which is collected in the tank 2 (see Fig. 1). In optimization goal, it is necessary to minimize the number of sizing parameters. So, a new compact model of the RO with the pump P 2 is developed in this paper requiring only one design parameter. The reverse osmosis (RO) membrane needs high pressure for the good operating of the RO. This pressure must exceed the osmotic pressure of the brackish water. The characteristic pressure/flow rate of the pump must be appropriate to the size of the RO membrane with the best energy efficiency. Thus, the size of the RO membrane was retained as the unique design parameter. This size, noted CMD (Cubic Meters per Day) in the paper, is defined as the nominal production capacity of freshwater per day (m 3 /d). Hydraulic load made by the RO membrane leads to a large variability of the pressure vs flow rate. Thus, the motorpump P 2 , thanks to variable speed, can modulate the flow rate and hence the consumed electric power. With the help of WinCAPS software for pumps and ROSA software [START_REF]FilmTec releases ROSA Version 6.0[END_REF][START_REF] Qaderi | Prediction of the groundwater remediation costs for drinking use based on quality of water resource, using artificial neural network[END_REF] for RO membrane (Filmtec), they allow us to calculate the hydraulic characteristics depending on the size for both and the speed for pumps. Fig. 4 shows hydraulic characteristic (pressure vs flow rate) for two sizes of the reverse osmosis membrane (CMD1 and CMD2) with the same pump CRN10-18 operating for two frequencies (40 Hz and 50 Hz). The intersection of the four curves leads to the operating points (CMD1-40, CMD1-50 and CMD2-40, CMD2-50).

Like for the pump 1, to optimize the size of the studied system, an equation between the size of the RO membrane (CMD), the flow rate (Q 2 ) and the electric power (P 2 ) has to be found. With WinCAPS and ROSA softwares, different combinations of pump-RO membrane can be defined with a good energy efficiency on a large scale by means of variable speed motor. Thus, Table 1 shows the selected combinations. Fig. 5 shows the results of these four combinations with the power supply frequency varying from 30 Hz to 50 Hz.

With "Surface Fitting Tool" of Matlab, a custom model ( 10) can depict these four pump-RO membrane combinations. Fig. 5 shows the

Table 1

Some configurations using moto-pumps "CRN" of Grunfos and RO membrane "BW30" of Filmtec.

with the recovery rate R r and the flow rate Q 2 , the freshwater flow Q 2p and the concentrate flow Q 2r are calculated by the following relationships:

⎧ ⎨ ⎩ = ⋅ = - Q R Q Q Q Q . p r r p 2 2 2 2 2 (13)
Consequently, with the Eqs. ( 10) to ( 13), we obtain the relation of the freshwater production Q 2p as function of the power P 2 and the size of the RO membrane as follows:

= ⋅ ⋅ + ⋅ - Q P C M D (3.
2.1.2.6. Water tanks. In system, two storage tanks are used: one for storing the brackish water filled by the drawing pump 1, and a second for the freshwater produced by the desalination process (RO membrane + pump 2). The capacities of water tanks 1 and 2 depend on the surface area and height of the tanks. In the optimization process, the tank heights remain constant, and the surface areas will be considered as the design parameters. In dynamic operation, the storage capacity is proportional to the water level in the tank. For the tanks 1 and 2, these levels are noted L 1 and L 2 , respectively. In dynamic operation, the level L 1 (t) is determined by the flow rates of the two pumps as follows:

⎧ ⎨ ⎩ = - + - ⋅ L t L t t Q t Q t S t ( ) ( Δ ) ( ) ( ) Δ 1 1 1 2 1 ( 15
)
In dynamic operation, the level L 2 (t) is determined by the permeate water flow Q 2p (t) from the RO membrane and the water consumed Q load-hydrau (t) as follows:

⎧ ⎨ ⎩ = - + - ⋅ - L t L t t Q t Q t S t ( ) ( Δ ) ( ) ( ) Δ p l o a dh y d r a u 2 2 2 2 (16)
with Δt: sampling time step (h) and S 1 , S 2 : surface areas of tank 1 and tank 2 respectively.

2.1.2.7. Freshwater and electricity loads. Electricity and freshwater consumption correspond to a family home. The electrical demand is defined over one week and repeated each week with seasonal modulation [START_REF] Abbes | Life cycle cost, embodied energy and loss of power supply probability for the optimal design of hybrid power systems[END_REF]. Fig. 6 shows the electrical power demand for a typical week. Freshwater demand is defined over one day and repeated each day [START_REF] Abbes | Life cycle cost, embodied energy and loss of power supply probability for the optimal design of hybrid power systems[END_REF]. Fig. 7 shows the water flow demand for a typical day.

Resolution system

In order to optimize the sizing of all the parameters of this system, it is necessary to solve the system in a real environment for one year, using a dynamic simulator. Weather profiles: wind speed (V wind ), solar irradiation (I r ) and ambient temperature (T a ) must be known. The resolution system uses recording data from a typical region (North Tunisia) during one year with a acquisition time of half an hour. Before starting the optimization problem, the following paragraph defines two performance indicators (LPSP E and LPSP H ) that are used in the criteria to be optimized and also in the constraints by limiting their values.

Performance indicators 2.2.1.1. Loss of electric Power Supply Probability (LPSP E ).

= ⋅ ∑ ⋅ ∑ ⋅ = = - LPSP δP t P t (%) 100 | | Δ Δ E i T i i T load elec i 1 1 s s ( 17
)
with δP i : electric power not delivered by the source to the load at the time i during Δt, -P load elec i : electric power consumed by the load at the time i during Δt, Δt: sampling time step (h). : hydraulic failure when the tank 2 is empty during Δt.

Loss of hydraulic Power Supply Probability (LPSP H ).

= ⋅ ∑ ⋅ ∑ ⋅ = - ≤ = - LPSP Q t Q t (%) 100 [ Δ] Δ H i T load hydrau i L i T load hydrau i 1 0 1 s i s 2 (18)

Dynamic simulator

For each design parameter, it is necessary to calculate the powers evolution's involved (P PV (t), P WT (t), P Bat (t)), the state of the battery (SOC(t)), the water levels in each tank (L 1 (t), L 2 (t)), the power of the motor-pumps (P 1 (t), P 2 (t)) and the satisfaction or not to supply the electrical and hydraulic loads with a energy management. The energy management of such system constitutes itself a difficult issue which can characteristic of the flow rate Q 2 according to the electric power P 2 of the motor-pump 2 (real data and the custom model). This curve is valid only for the optimal pump-RO membrane combinations from RO Filmtec membranes and real Danfos pumps supplied at variable frequency between 30 Hz and 50 Hz. The equation linking the RO membrane (CMD), the flow rate (Q 2 ) and the electric power (P 2 ) is as follows: be solved using optimal control methods. In this paper, a simple (rule based) but quite efficient energy management strategy developed in previous works [START_REF] Zaibi | Smart power management of a hybrid photovoltaic/wind stand-alone system coupling battery storage and hydraulic network[END_REF] has been used. Fig. 8 shows the simplified principle of the management of the operation of the two motor-pumps 1 (P 1 ) and 2 (P 2 ) and the supply of the electric charge (P load-elec ) according to the SOC(t) of the battery compared to the SOC u and the water levels in the tanks (at the levels L 1,min and L 2,u ). For more information, readers can refer to the paper [START_REF] Zaibi | Smart power management of a hybrid photovoltaic/wind stand-alone system coupling battery storage and hydraulic network[END_REF]. For this purpose, a dynamic simulator (see Fig. 9) calculates the state of the system (all the variables listed above) and the system indicators (LPSP E , LPSP H , min(L 1 )) over a year, with a sampling step, according to meteorological data (wind speed, irradiation, temperature) [START_REF] Abbes | Life cycle cost, embodied energy and loss of power supply probability for the optimal design of hybrid power systems[END_REF].

Meta-models synthesis process

In order to speed up the optimization system, meta-models are used to model the system in its specific environment. For this, the metamodeling by design of experiments (DOE) is efficient. The first step consists in creating a database of the outputs according to the inputs. This database is created with the dynamic simulator for simulated experiments. In order to avoid a huge database, the latin hypercube sampling (LHS) method is used to obtain only 5000 points [START_REF] Olsson | On Latin hypercube sampling for structural reliability analysis[END_REF] (with nine inputs, which are the decision variables displayed in Table 2).

Secondly, the goal is to find the best equation for each output according to the inputs in accordance with experiments. Thus, the "Model-Based Calibration" toolbox is used with equations of the Bspline form.

The meta-modeling process is summarized in Fig. 10 where x i denotes the decision variables, y i the dynamic simulator outputs and  y i the meta-model outputs. The expressions are as follows: .

    ⎧ ⎨ ⎪ ⎩ ⎪ = = = x A A C P CMD S S
i P V W T n u u i H E i H E 1 1 2 2 1 1 (19)

Optimization principle

The goal consists in doing the co-optimization of the system sizing with an energy management. This involves two optimization nested loops. Firstly, the size of each element composing the photovoltaic/ wind system for the production of electricity and freshwater has to be determined: PV and wind turbine surfaces, nominal power of pumps, volume of tanks, battery capacity and RO membrane capacity. Secondly, for sharing energy storage between the battery and the freshwater tank, two intermediate levels of storage (one in the battery (SOC u ) and the second in the freshwater tank (L 2u )) are used by the energy management. This consists reserving enough in both storages for anticipating the lacking phases of renewable energy. To optimize the total embodied energy (EE) of the system throughout its life cycle, it is necessary to define the cost model (MJ) of each element used. The next part gives these relations.

Embodied energy modeling

For the studied system (based on renewable energy), embodied energy is mainly consumed during elements manufacturing, on-site construction and decommissioning at end of life. Embodied energy consumed during the lifetime (maintenance) is relatively low, but taken account in the paper. The following paragraphs show the relationships of the EE of each element of the studied system in terms of their design parameter.

2.3.1.1. Wind turbine. The embodied energy of wind turbine EE WT (MJ) is based on the swept area of the rotor A WT (m 2 ). The analytic relationship, coming from Ref. [START_REF] Cherif | Environmental life cycle analysis of a water pumping and desalination process powered by intermittent renewable energy sources[END_REF], is as follows:

= ⋅ + EE A 2360 1875.
WT WT [START_REF] Maussion | Design of Experiments in electrical engineering: applications in control and modeling[END_REF] 2.3.1.2. Photovoltaic panels. The embodied energy of PV panel EE PV (MJ) is based on their surface area A PV (m 2 ). The analytic relationship, coming from Ref. [START_REF] Cherif | Environmental life cycle analysis of a water pumping and desalination process powered by intermittent renewable energy sources[END_REF], is as follows:

= ⋅ - EE A 3863 47.
PV PV [START_REF] Zaibi | A hybrid spline metamodel for photovoltaic/wind/battery energy systems[END_REF] 2.3.1.3. Battery. The embodied energy of battery EE BAT (MJ) is based on its storage capacity C n (Ah) for the battery voltage of 12 V. The analytic relationship, coming from Ref. [START_REF] Abbes | Life cycle cost, embodied energy and loss of power supply probability for the optimal design of hybrid power systems[END_REF], is as follows:

= ⋅ ⋅ EE N C 60 BAT r n ( 22
)
with N r : number of battery replacement during the life cycle of the system.

2.3.1.4. Pumps. The embodied energy of motor-pumps EE MP (MJ) is based on their nominal electric power P 1n (kW) and P 2n (kW). The total for the two pumps with their supply converter, the analytic relationship coming from Ref. [START_REF] Cherif | Environmental life cycle analysis of a water pumping and desalination process powered by intermittent renewable energy sources[END_REF] is as follows:

= ⋅ + ⋅ + ⋅ + EE P P P P 283 684 2200 ( ) MP n n CV CV 1 2 1 2 (23)
with P CV 1 , P CV 2 : nominal power of supply converters feeding respectively the motor-pumps P 1 and P 2 expressed in (kW). Note: the nominal electric power of the motor-pump 2 is linked to the RO membrane sizing, thus P 2n is equal to P 2,max (Eq. ( 11)).

2.3.1.5. Tanks. The embodied energy of tanks EE ST (MJ) is based on their surface area S 1 and S 2 (m 2 ) and their height h 1 and h 2 (with h 1 = h 2 = h = 2 m). The analytic relationship for the two tanks, coming from Ref. [START_REF] Cherif | Environmental life cycle analysis of a water pumping and desalination process powered by intermittent renewable energy sources[END_REF] is as follows:

= ⋅ ⋅ + EE h S S 371 ( ). ST 1 2 (24)
2.3.1.6. Reverse osmosis membrane. The embodied energy of RO membrane EE OI (MJ) is based on its flow rate per day CMD (m 3 /d).

The analytic relationship of the RO membrane, taking account of the maintenance during all the life cycle, coming from Ref. [START_REF] Cherif | Environmental life cycle analysis of a water pumping and desalination process powered by intermittent renewable energy sources[END_REF] is as follows:

= ⋅ EE C M D 5224 . OI (25)

Optimization problem

In order to speed up the CPU time of the simulations performed over one year, a sampling time of 1/6 h is used. This "high" value may lead, in some configuration cases, to negative levels of water in the brackish water tank 1. Instead of reducing this time step which would implies a significant increase of the CPU time, a constraint is added into the optimization problem ensuring min(L 1 ) > 0.

2.3.2.1. Definition. The optimization problem has three objectives to be minimized: LPSP E , LPSP H and EE under three constraints: LPSP E and LPSP H less than 5% and the tank 1 never empty translated by min (L 1 ) > 0, with nine decision variables x i (system parameters). The optimization problem may be expressed by the following equations: Optimization criteria:

⎧ ⎨ ⎩ = = = x F x EE F x LPSP F x LPSP min ( ) ( ) ( ) i i i E i H 1 2 3 (26)
Constraints:

= ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ ≤ G x g g g ( ) 0 i 1 2 3 (27)
with g 1 = LPSP E -5%;g 2 = LPSP H -5; g 3 = -min(L 1 ).

2.3.2.2. Algorithm. Genetic algorithms are well suited for solving this kind of problem. NSGA-II is classically used for multiobjective and constrained optimization cases [START_REF] Srinivas | Multiobjective function optimization using non-dominated sorting genetic algorithms[END_REF][START_REF] Hozouri | On the use of pumped storage for wind energy maximization in transmission-constrained power systems[END_REF]. In the following, the chosen parameters of the NSGA-II algorithm are two hundred individuals and five hundred generations.

Optimization process

The system performance must be evaluated over long periods of time to take seasonal features and correlations of renewable energies into account. Two solutions are developed in this paper in order to optimize the studied system. First, the dynamic simulator is used for evaluations the constraints and criteria used by the NSGA-II algorithm. The simulator is run with all sampling points of one year (52,560 samples: 1 sample per 10 min). Secondly, a meta-model is used for formulate the outputs of the studied system byparameterized equations for the decision variables. The sizing process by means of optimization is shown by Fig. 11.

Results and discussions

Meta-model results

With the DOE carried out with the dynamic simulator, the three indicators

= = ∼ ∼ ∼ ∼ y LPSP y LPSP , E H 1 2 and = ∼ ∼ y L min( ) 3 1
defined in Fig. 10 are shown in Fig. 12. The red color cross clouds are the results of the dynamic simulator with 5,000 samplings (LHS) for the nine design parameters in the range given in Table 2. The dashed black line on each figure represent the best meta-model obtained with "model-based calibration" toolbox of Matlab. Globally, the meta-model curve is in the average of the point cloud for the useful zones (LPSP≥0 and L 1,min ≥0). We also see that the point cloud for the LPSP E has a very low variance around its mean unlike the other two indicators.

Sizing results

The evolution of the dissatisfaction levels of the electric and hydraulic demands LPSP E and LPSP H according to the total embodied energy EE over a 20-year life period is shown in Fig. 13 (EE/LPSP E , EE/ LPSP H and LPSP E /LPSP H representations). This figure compares the three Pareto optimal solutions achieved from the meta-models optimization (noted by green color cross) and from the accurate solutions achieved by the dynamic simulator in the optimization loop (noted by For the results with the meta-models, the indicators LPSP E and LPSP H have been recalculated with the dynamic simulator from the solutions of the sizing achieved with the NSGA-II algorithm (noted in Fig. 13: meta-model (recalculated solutions)). The figure shows only the solutions that respect the constraints (i.e. LPSP E < 5%, LPSP H < 5% and min(L 1 ) > 0). We note a good match of solutions for the three Pareto diagrams. The results in the design space are shown in Fig. 14. The decision variables have globally comparable values. For example, taking in both cases the embodied energy of 8.4E+05MJ, LPSP E = 1.75% and LPSP H = 1.84%. Table 3 presents the obtained parameters for both models. This table shows the small difference between the parameters achieved by the dynamic simulator and those achieved by the meta-models. This shows the quality of the meta-model approximation even for this kind of complex system comprising two forms of storage (battery and water tank) and two kinds of loads (electricity and freshwater).

The results in the design space are shown in Fig. 14. The decision variables have globally comparable values. For example, taking in both cases the embodied energy of 8.4E+05MJ, LPSP E = 1.75% and LPSP H = 1.84%. Table 3 presents the obtained parameters for both models. This table shows the small difference between the parameters achieved by the dynamic simulator and those achieved by the metamodels. This shows the quality of the meta-model approximation even for this kind of complex system comprising two forms of storage (battery and water tank) and two kinds of loads (electricity and freshwater).

CPU times results

Table 4 shows the CPU time when the optimization is done using the dynamic simulator with all meteorological data and when the optimization is done using only the meta-models obtained with the processing explained in the paper in accordance with the same criteria and constraints.

Discussions

Sizing results

The results of Figs. 13 and 14 show that it is possible to have LPSP E and LPSP H almost zero but at the cost of a significant investment. An investment reduction of 30% leads to an increase of LPSP E and LPSP H of only 5%. The influence of the investment relates exclusively to PV and wind turbine surfaces and battery capacity. All the sizing of the hydraulic part and the control parameters remain insensitive to these investment variations, which is remarkable. It is the sizing of the battery that is the most sensitive, which triples value on the studied range. For PV and wind turbines, the variations are approximately proportional to the investments.

The percentage of relative error in Table 3 shows differences between the design parameters obtained with the meta-model of less than 4%, except the size of the tanks that have a greater difference. This is due to a greater dispersion of the optimal points of the real LPSP H compared to the optimal points obtained by the meta-model; see in Fig. 12.

CPU times

The difference is made on the convergence time of the optimization algorithm. Three days are required with the dynamic simulator in the loop of the optimization algorithm and few minutes with the metamodels because for the dynamic simulator 52,560 samples are needed to calculate one optimization point, while for the meta-model-models the algorithm solves the equations once. Obviously, it is necessary to add one day to realize the database by DOE and the search of the metamodels from this database with a good representativeness.

Conclusions

This paper presents a methodology for the optimal sizing of a system for the production of fresh water and electricity, for an isolated site, with brackish water well, renewable energies and double storage in a battery and in water tanks (brackish water and fresh water). This approach is applied to the embodied energy (EE) used over the total life cycle of the system. The hydraulic equations are extrapolated from the manufacturers catalogs of pump and reverse osmotic (RO) membrane. For the well pump, its flow is linked to the electrical power. The whole of the RO-based desalination unit, the freshwater flow rate was modeled according to the surface of the RO membrane and the electric power of the pump. Using meta-models in the optimization process saves CPU time with results similar to using a dynamic simulator (a few minutes for the first and several days for the second). The optimization results show that the cost of energy investment (EE) is strongly related to the dissatisfaction of the production of water and electricity (LPSP H Fig. 14. Evolution of the decision variables on the optimal fronts of two simulation approaches: dynamic simulator and meta-model. (For interpretation of the references to color in this figure, the reader is referred to the web version of this article.)

Fig. 1 .

 1 Fig. 1. The global system architecture.

Fig. 2 .Fig. 3 .

 23 Fig. 2. Pressure vs flow Q 1 rate for CRN 3 (GRUNDFOS-pumps) and the hydraulic load.

Fig. 4 .

 4 Fig. 4. Pressure vs flow rate Q 2 for CRN10-18 (GRUNDFOS-pump) at variable speed and two reverse osmosis membranes (CMD1 and CMD2).

Fig. 5 .

 5 Fig. 5. Flow rate Q 2 vs electric power P 2 for four CRN pump-RO membrane combinations in variable power supply frequency and the Q 2 vs P 2 model (10).

:

  flow of consumed water at the time i during Δt,

Fig. 6 .

 6 Fig. 6. Weekly electrical power consumption profile.

Fig. 7 .

 7 Fig. 7. Daily freshwater consumption profile.

Fig. 9 .

 9 Fig. 9. Dynamic simulator with energy management.

Fig. 8 .

 8 Fig. 8. Simplified management algorithm.

Fig. 10 .

 10 Fig. 10. Meta-modeling process.

Fig.

  Fig. Block diagram of the optimization process: (a) with Dynamic simulator, (b) with meta-modeling.

Fig. 12 .Fig. 13 .

 1213 Fig. 12. Meta-model points for monitoring system indicators. (For interpretation of the references to color in this figure, the reader is referred to the web version of this article.)

Table 2

 2 Exploration range of decision variables.

	Parameter	Minimum value	Maximum value
	A PV (m 2 )	20	100
	A WT (m 2 )	80	160
	C n (Ah)	200	1400
	P 1 (W)	1500	2500
	CMD (m 3 /day)	10	40
	S 1 (m 2 )	1	2 0
	S 2 (m 2 )	20	200
	L 2,u (m)	0.3	1.9
	SOC U (%)	60	100

Table 3

 3 Decision variables for EE = 8.4E+05MJ, LPSP E = 1.75% and LPSP H = 1.84%, with the dynamic simulator and with the meta-model.

	Parameter	Dynamic simulator	Meta-model	Relative error
	A PV (m 2 )	61	58.7	-3.8%
	A WT (m 2 )	123.3	127	+3%
	C n (Ah)	649.1	673	-3.7%
	P 1 (W)	1926	1944	+0.9%
	CMD (m 3 /day)	16.7	16.1	-3.6%
	S 2 (m 2 )	52.3	43.3	-18.8%
	S 1 (m 2 )	5.6	4.7	-16%
	L 2,u (m)	1.9	1.65	-13%
	SOC U (%)	92.1	89	-3.4%

Table 4

 4 CPU time NSGA-II optimization by using dynamic simulator or using the metamodels (with Processor AMD FX(tm), 8 cores, 4 GHz).

	Parameter	Value
	Number of parameters	9
	Number of criteria	3
	Number of constraints	3
	Number of run	01
	CPU time using the dynamic simulator	72 h (3 days)
	CPU time using the meta-models	0.22 h (13 min)

Acknowledgment

The authors would like to thank the CMCU UTIQUE Program for financial support. This work was supported by the Tunisian Ministry of High Education and Research under Grant LSE-ENIT-LR 11ES15.


Baptiste Goupille-Lescar
email: baptiste.goupillelescar@thalesgroup.com

Eric Lenormand
email: eric.lenormand@thalesgroup.com

Nikos Parlavantzas
email: nikos.parlavantzas@irisa.fr

Christine Morin
email: christine.morin@inria.fr

Communication-Aware Prediction-Based Online Scheduling in High-Performance Real-Time Embedded Systems

Keywords: Embedded systems, Real-time, Scheduling, Dynamic resource management

Current high-end, data-intensive real-time embedded sensor applications (e.g., radar, optronics) require very specific computing platforms. The nature of such applications and the environment in which they are deployed impose numerous constraints, including realtime constraints, and computing throughput and latency needs. Static application placement is traditionally used to deal with these constraints. However, this approach fails to provide adaptation capabilities in an environment in constant evolution. Through the study of an industrial radar use-case, our work aims at mitigating the aforementioned limitations by proposing a low-latency online resource manager derived from techniques used in large-scale systems, such as cloud and grid environments. The resource manager introduced in this paper is able to dynamically allocate resources to fulfill requests coming from several sensors, making the most of the computing platform while providing guaranties on non-functional properties and Quality of Service (QoS) levels. Thanks to the load prediction implemented in the manager, we are able to achieve a 83% load increase before overloading the platform while managing to reduce ten times the incurred QoS penalty. Further methods to reduce the impact of the overload are as well as possible future improvements are proposed and discussed.

Introduction

Nowadays, with the increasing demand for high-performance computing and smart sensing, highend embedded system designers are facing an increasing number of challenges. Indeed, the targeted platforms must respect a great number of non-functional constraints, such as Size, Weight and Power (SWaP), real-time computing and cost constraints. Currently, most embedded systems meet these constraints by the use of dedicated components and static resource allocation approaches based on worst-case scenarios. This method, coupled with the emergence of workloads integrating hard, soft real-time and best-effort applications and the increase of their variability, results in massive over-provisioning and under-utilization of resources. Moreover, while this method allows the design of efficient and reliable systems, it nearly eliminates their adaptation and evolution capabilities by preventing the deployment of highly variable or opportunistic applications for smart sensing. To address these limitations, this paper proposes a smart resource management system, able to fulfill low-latency run-time requests for application execution while providing non-functional guarantees. Timing properties are considered in this paper, while other properties such as heat dissipation, will be addressed in future work. To achieve high performance gains while guaranteeing timing properties, our contribution is inspired by large-scale resource managers found in cloud or grid infrastructures, making the most of application profiling to enable high-level predictability, low mapping latency as well as high resource utilization. This work is supported by several industrial usecases, including an Active Electronically Scanned Array (AESA) radar use-case, which is detailed in this paper. To fit the targeted context, a complete simulation framework has been implemented. The results obtained through simulations show that our mapping method results in improvements in both performance and predictability of the system. This paper is organized as follows: Section 2 provides a quick description of the motivating use-case context. In Section 3, related research from both the embedded and large-scale systems communities are presented. Section 4 describes the models and methods used in our approach. In Section 5 the simulation framework created is explained and simulation results are analyzed. Section 6 introduces future work and discusses several open questions. Finally, Section 7 draws some conclusions and perspectives.

Use-Case Specific Context

Our use-case deals with optimizing the computing resource utilization of a multi-function electronicallysteered surface radar and has been characterized with the support of domain experts. This equipment can typically be installed on the ground vehicles or on some surface ships such as frigates, with the mission of detecting, tracking and identifying objects of interest. This is done by illuminating narrow angular sectors by one or more sequences of known signals (waveforms) and processing the returned echoes captured on a large number of receivers. Such an observation is commonly referred as "dwell". Dwells can be of several types, depending on their objective (e.g., scanning an unknown sector, tracking a known target) and make use of different waveforms, each with its known duration. The radar antenna is constantly kept busy and scans the whole radar angular range by successively sending signals with the appropriate waveforms. The processing of received echoes is traditionally split into two distinct phases:

-A front-end one that applies fixed filtering functions on the digitized received channels. It processes a massive bandwidth of input data, and selects a limited set of points of interest by using appropriate detection thresholds. This phase is highly computation-intensive and computing times are deterministic. -A back-end phase whose goal is to extract operational information (e.g., position, speed, trajectory, nature of target) from the detection results. Among functions executed in the back-end are the extraction, which delivers so-called "plots" that characterize one or more targets in precise directions of space, and tracking, which consolidates plots issued by extraction and builds trajectories of targets.

Considering the regularity of the front-end workload, a near-optimal mapping (i.e., resource allocation) can be found at design-time and used during run-time processing. Thus, front-end tasks are not targeted by this study as their high predictability limits the potential performance gain from the integration of dynamic elements. On the contrary, static design-time mapping methods loose efficiency when applied to functions with data-dependent complexities, which is the case for Functions like extraction have a largely variable computational cost, depending on the type of dwell as well as the number and configurations of targets that must be discriminated from the front-end detection. The actual run-time of each extraction is only known at the end of its execution. However, this cost is bounded by known minimum/maximum values related to each dwell type.

The computing platform used for back-end processing must fit within a specific SWaP budget. In our case, the targeted computing platform consists of 4 racks each one hosting several boards with several processing elements and a shared memory. All these elements are linked together by an Ethernet network using a star topology with one central router connected with the routers present in each rack. In addition to SWaP constraints, processing latencies matter, as observing and tracking targets needs to be kept in pace with their kinematics. The combination of variable computation times (and data transfer), constrained platform and real-time computing renders design-time mapping policies inefficient and drives the need for agile methods. Another goal of the introduction of online resource management in traditionally static systems is to serve as an enabler for the implementation of new applications with varying resource demand or unknown completion time.

To add adaptation capabilities to the system, we experiment with a resource management functionality that receives sporadic sequences of requests, each corresponding to a dwell that will be input to one of the 4 radar antennas. The trigger (see Fig. 1) represents the moment at which the data will be available for the back-end (e.g. extraction) applications, after waveform emission/reception and front-end processing. The resource manager allocates the different back-end computation and communication activities of the dwell application onto the platform resources so that they can be executed before their deadline. For reasons discussed later, this placement decision Map is taken just before the trigger reception. After having been placed, an application's execution effectively starts only when all its dependencies are met and the targeted processing elements are free, which ideally happens at T = trigger. It then executes for a time depending on the data content before sending the results and freeing the occupied computing and communication resources. Furthermore, note that the processing of separate dwells (addressing different regions in space) can be done independently from each other.

Their execution is mandatory, every request must be fulfilled, and is non-preemptive. As of now, the resource management system is only seen as an executant and does not have the opportunity to reject or terminate an application. Once a request has been received, the associated application is executed in its entirety.

Related Work

As we are addressing high-performance computing problems in an embedded environment, the following related work is divided into two parts: studies targeting embedded systems with SWaP and timing constraints and studies addressing the placement of similar application models on largescale systems.

Embedded Systems

We first take a look at works that consider similar computing platforms with timing constraints. In our study, as in numerous embedded systems design problems, the real-time execution of applications is a major concern. A great number of published works aim at providing timing guaranties for hard real-time applications. Works aiming at aeronautic or automotive certification reject dynamic methods and focus on single-processor architectures, as in [15] or [START_REF] Nasri | Offline equivalence: A non-preemptive scheduling technique for resourceconstrained embedded real-time systems (outstanding paper)[END_REF], to maximize the system's predictability. In recent years, there has been a growing interest in both multi-processor architectures and mixed-criticality workloads. This led to numerous publications [START_REF] Baruah | Towards the design of certifiable mixed-criticality systems[END_REF] and several European research projects [1] [2]. However these studies, such as [START_REF] Giannopoulou | Scheduling of mixed-criticality applications on resource-sharing multicore systems[END_REF] or [START_REF] Ren | Mixed-criticality scheduling on multiprocessors using task grouping[END_REF], only address design-time schedulability analysis.

In [START_REF] Quan | A hierarchical run-time adaptive resource allocation framework for largescale mpsoc systems[END_REF], run-time adaptation consists in mapping long-lasting jobs onto a multi-processor systemon-chip architecture by making use of configurations elaborated at design-time. However, in our case the run-time management system operates in a non-periodic context by taking very frequent mapping decisions for computing jobs with a very limited duration. Similarly, the authors of [START_REF] Gadioli | Application autotuning to support runtime adaptivity in multicore architectures[END_REF] use design-time exploration results to dynamically adapt the application run-time setting depending on the context. While both these works show promising results, our workload's temporal behavior makes it impossible to adapt the resource allocated to an application once it started. The fact that all applications of our use-case are short-lived and must meet their deadline makes it impossible to modify the set of resources they are deployed on after the applications have started their execution.

Large-Scale Systems

While studies in the embedded community essentially focus on real-time control workloads or signal/video processing applications, our use-case's workload is much closer to workflows encountered in large-scale systems, such as cloud computing. With the democratization of cloud computing and an increasing need for efficient scientific simulations, more and more works address the scheduling of workflows in HPC systems [START_REF] Liu | A survey of data-intensive scientific workflow management[END_REF]. These workflows are often materialized as Directed Acyclic Graphs (DAGs) for which computing and communication resources are allocated until their completion. Among the numerous publications, two main categories of resource management systems can be identified:

-Purely dynamic approaches with close to no prior knowledge of the applications and relying on cloud elasticity to compensate for QoS run-time variation by allocating/releasing and/or migrating Virtual Machines (VMs) [27] [7]. -Static methods relying on exhaustive or evolutionary algorithms to find an optimal placement before executing the application. Commonly used methods include genetic, ant colony and Min-Min algorithm variations [START_REF] Tang | Budget-constraint stochastic task scheduling on heterogeneous cloud systems[END_REF] [23] [START_REF] Kousalya | Workflow Scheduling Algorithms and Approaches[END_REF] [6] [START_REF] Braun | A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems[END_REF].

While both of these approaches have merits and can achieve great results in cloud or grid computing, none are directly applicable to our use-case for several reasons. First, due to the arrival rate of requests, a placement solution must be found in a few milliseconds, which prevents us from using, for example, genetic or particle swarm algorithms. Furthermore, while some methods using online model derivation, such as [8] can show great results, they are only applicable to long-lasting applications. Then, the use-case's applications being non-preemptive and the resources not being virtual makes it impossible to rely on migration or virtual machine re-dimension mechanisms.

A fair number of studies try to incorporate predictability via the use of priorities or isolation mechanisms, as in [START_REF] Khemka | Utility maximizing dynamic resource management in an oversubscribed energy-constrained heterogeneous computing system[END_REF] [START_REF] Lucier | Efficient online scheduling for deadline-sensitive jobs[END_REF]. Unfortunately, due to the ever-changing nature of cloud environments, most "real-time" cloud resource managers react to deadline misses and do not prevent them. Thus, while no management system is actually able to provide hard real-time guaranties, there exist few satisfying solutions able to accurately provide soft real-time guaranties when targeting data streaming. However, while it is manageable to obtain these timing properties inside a cloud environment, it is noticeably more difficult to do so when considering communications with users as data have to go through heavy software stacks as well as non-deterministic communication protocols [START_REF] Garca-Valls | Challenges in real-time virtualization and predictable cloud computing[END_REF]. In [START_REF] Cai | A delay-based dynamic scheduling algorithm for bag-of-task workflows with stochastic task execution times in clouds[END_REF], while the authors use similar workload and resource reservation mechanisms to ours, they only target bag of tasks applications, for which they have control over the parallelism level, do not consider SWaP constraints and can potentially reserve an infinite number of VMs.

Finally, while the problem has already been addressed for single processor systems [START_REF] Megow | Models and algorithms for stochastic online scheduling[END_REF], only few works actually target non-preemptive resource allocation for stochastic workloads on multi-processor platforms [START_REF] Skutella | Unrelated machine scheduling with stochastic processing times[END_REF] [START_REF] Gupta | Stochastic load balancing on unrelated machines[END_REF]. Moreover, they are purely mathematical approaches and totally abstract the computing platform by considering a set of identical unrelated machines.

To conclude, while a significant number of works seem to address a similar problem, the specificity of the considered use-case applications and the computing platform makes it impossible to simply adapt existing solutions.

Our Approach

In this section we first describe the overall functioning of our resource manager, consisting of the mapper and predictor components. Afterwards, this section describes the proposed mapping heuristic. Our final objective being to maximize the QoS provided to the radar's operator, a QoSaware extension of our method is finally introduced.

Mapping Process

The overall mapping process is shown Fig. 2 which serves as a guideline for this section. As explained in Section 2, the resource manager receives requests from the radar every few milliseconds (1 in Fig. 2). Each of these requests contains the type of application to execute, its identifier, its priority, the input and output memories and the time at which the data will be available in the input memory. The application's type defines its structure (i.e., directed acyclic graph) and profiling data, such as computing time and input and output data volume for which only minimal and maximal values are known. Note that priorities are only partially correlated to the application's type because they are dynamically attributed depending on the context (e.g., threat level of a target).

It is necessary to find a valid mapping solution for these requests before the data is available to reduce latency as well as to avoid congestion in the input memory. Furthermore, only probabilistic execution times of each computation and communication activity are known when evaluating Fig. 2: Simplified model view placement possibilities. Thus, unlike numerous approaches present in the literature, it is necessary to take a decision based not on the current state of resources but on an estimation of their future availability. To this extend, the Mapper interacts with the load Predictor (2 )(3 ) to find a suitable placement for both communication and computation activities of the application (i.e., nodes of the DAG). Once a decision has been made, the application's activities are sent to their respective hosts [START_REF] Braun | A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems[END_REF]. They are executed on the platform using data from the radar (5 ) to determine their actual execution timings. Finally, monitoring signals from the platform ( 6) are then exploited to update the load prediction model.

Prediction Model

Computing time predictions are handled by our Predictor module. Its role consists in keeping an up-to-date simplified overview of the platform's processors, links and memories state as well as queued activities to provide the Mapper with execution time predictions. Keeping in mind that a valid mapping solution must be found in a few milliseconds, the simulation of the actual computing platform in its entirety is far too computationally intensive to consider in detail while looking for a run-time solution. Indeed, since the platform comprises multiple shared resources (memories, communication links), estimating the impact of the deployment of an application on all the applications already running (or queued) represents a significant amount of computation, impossible to terminate in a few milliseconds on an embedded platform. Thus, the Predictor maintains a simplified model of the real architecture containing every resource (processors, memories, links) as well as the activities queued for execution in each of these resources. The execution time predictions are made without taking into account some of the resource access conflicts happening in the actual platform. The architecture model inside the predictor is kept up-to-date using both the Mapper 's placement decisions in addition to the platform's monitoring signals. The interactions between Mapper, Platform and Predictor can be seen as a MAPE (Monitoring, Analysis, Planning and Execution) control loop often found in large-scale systems management systems. Some adjustments are necessary to this loop as, while it is possible to take a mapping decision at the time a request is received, it may be profitable to wait for a more precise prediction since the application's first activity will only be executed tens or hundreds of milliseconds later, when the data is available. The earlier a decision is taken, the less accurate the execution time prediction is as we would be making predictions on top of predictions since execution timings of an application depend on estimations of other applications' end times. On the contrary, taking a decision at the last minute means a reduced time to evaluate possible solutions. Thus, a trade-off must be found between the number of possible mappings we can evaluate versus the accuracy of these evaluations to find the best possible solution.

It is important to note that it is possible to make some assumptions on the system's evolution thanks to its quite regular request submission pattern; it would be impossible to anticipate its behavior if it was completely random. The system receives aperiodic sequences of mapping requests with an average interval between them in the range of a few milliseconds. Indeed, the rate at which the mapper receives requests is correlated with the radar antennas emission rate and, in practical use-cases, the antennas operate close to their maximum capabilities at all times. As mentioned before, their execution times can greatly vary depending on the data to process which can not be known before execution. In summary, we are faced with a system whose dynamic behavior enables short term predictions ranging from a few milliseconds to tens of milliseconds.

Proposed Mapping Heuristics

The considered application model is as follows: Each application is seen as a directed acyclic graph AP P = (A, D, prio, trigger, dl, input, output) having a priority prio, a memory input at which necessary data will be available at t = trigger and the memory output in which the results have to be stored before the deadline dl. A represents a set of computing activities linked by execution order constraints, or dependencies D. An Activity A n = (vol compmax , vol compmin , vol inmax , vol inmin , vol outmax , vol outmin , α) has minimum/maximum values of the number of instructions to execute (vol comp ), the data input vol in and output vol out volumes as well as a memory access ratio α. The memory access ratio α of a computing node determines the minimum memory bandwidth needed by a target processor to perform the computation of this activity at maximum speed. For an application to be schedulable, we assume that ∀AP P, T max < (deadline -trigger), T max being the sum of maximum computation times of the activities part of the critical path of AP P . In other words, applications have slack, meaning most of them can be slightly delayed and still respect their timing constraints.

Concerning the architecture, reasoning is made on the architecture model maintained by the predictor and defined as follows. The platform P F = (P, M, L) is seen as a set of processors P , memories M and links L. Each processor P n possess a computing capacity expressed in instructions per second in addition to its type, each memory M n a maximum bandwidth and each link L n a maximum throughput expressed in Bytes per second. At run-time the architecture runs several applications. Processors (resp. communication links) can only serve one computation (resp. communication) at a time. Memories on the contrary potentially share their bandwidth between different computations and communications, which may result in slowing down some of them in case of excessive demands.

Static mapping This mapping strategy is used as a reference for comparison with dynamic strategies shown below. In this context, processors are allocated to successive requests in each rack on a systematic round-robin basis, without considering the computing cost or priority of each requested activity.

Prediction-Based Load Balancing This dynamic strategy consists in allocating at run-time the best communication path and computing elements in the machine, by taking account of an estimated load status of the different resources of the architecture. Its objective is to minimize the end time of the next request to be executed. This is done by investigating all sets of processors SP n ⊂ P able to host the different computation activities to execute. For each of them, since an application request carries information on input and output memories, it is possible to identify and generate an adequate set of communication activities to transfer data from the input memory to computing activities hosts' memories and, finally, to the output memory. From this set of activity sets, the mapper then estimates for each of them the worst-case completion times of the application request according to the architecture resources used and their estimated current workload. The predictor is used there, providing for each resource an estimation of the completion time of its last queued activity, or the indication that it has no activity still running. This is then used to evaluate the completion time of the new candidate activity request, and elect the hosting processor and associated communication path that achieves the earliest predicted completion time. To estimate the worst-case execution time of a computing activity on a processor, this processor's frequency and the maximum possible number of instructions for this type of activity are used. Concerning communication time predictions, it is necessary to take the maximum availability of links on the path in addition to the input and output memories bandwidths. Then, an estimated worst-case communication time is computed using the maximum data volume for this activity and the lowest available bandwidth on the path. Note that in our test bench, the possibility is left to choose to off-load a request of a busy rack to a less busy neighbour rack, when the additional cost of moving data to and from the receiving rack compensates advantageously for long potential delays in the original rack.

QoS-Aware Load Balancing This strategy is an extension of the previous prediction-based load balancing whose goal was the reduction of application latencies. While the latter allocates the earliest finishing resources to individual requests, this strategy now aims at optimizing a QoS indicator based on the global cost of exceeding deadlines. As mentioned before, the activity requests are of different types with different priorities, and thus a variable degree of flexibility can be left to miss deadlines. This is an alternative to the hard deadline model. This alternative fits better our radar context, which runs activities at variable computing costs and variable requirements on reactivity; as an example, activities related to tracking targets are expected to complete soon enough to avoid loosing the target, while others operate in a human time scale.

Each type of activity has a penalty factor proportional to the extent of the deadline miss, and null if the deadline is met. The goal is now to keep the accumulated penalty as low as possible while executing the same workload on the same computing platform. Then the QoS-based strategy now considers a sequence of n activity requests of potentially different types (and priorities), sorted in trigger time order. We call R 0 the request in the queue with the earliest trigger time and R n the n th requests in the queue. While the execution order (i.e. trigger time) isn't impacted, the objective is now to determine if the best mapping found should be used for the next request R 0 or a later, more critical one.

selects the best host processor P 0 for R 0 and estimates its potential deadline miss and resulting penalty Q R0/P0 -∀0 < i <= n select the best host processor P i for R i with P 0 removed from the list of candidate processors and estimates the potential deadline miss of R i and resulting penalty

Q Ri/Pi -if Q Ri/Pi + Q R0/P0 > Q Ri/P0 + Q R0/
Pi and if R i has a larger priority than R 0 , processor P i is allocated to R 0 , leaving P 0 free else processor P 0 is allocated to R 0 This resource allocation strategy can be seen as an extension of the first load-balancing method as its behaviour will deviate from the non QoS-aware one only when predicting significant penalty overheads.

Evaluation

To evaluate the proposed mapping heuristics a simulation framework has been created mostly because the objective is to evaluate the resource management policies themselves, which would be too time consuming if one had to develop and integrate real-time software for each candidate computing platforms. A modular approach has been adopted, allowing us to calibrate the simulation with actual data while having some freedom in the testing done. This section first describes the created simulation environment before discussing some interesting results.

Simulation Framework

The simulation environment, realized for this study using the Ptolemy II Framework [START_REF]System Design, Modeling, and Simulation using Ptolemy II. Ptolemy.org[END_REF], is divided into three main components:

a request generation module the resource management system a computing platform simulator Request Generation A request generation module has been developed to reproduce representative radar scenarios. It emulates the radar management system request submission pattern and generated requests possess properties close to actual ones. As such, it generates dwell requests as if feeding 4 antennas. The type of dwells and the request released dates are randomized to a certain extend, but in a reproducible way. The generator also includes parameters allowing us to represent the complexity of the environment observed by each antenna by manipulating the probability distribution of actual instruction and communication data volumes of dwells treated by this antenna. These volumes are sent directly to the simulator (see Vol Fig. 2) and aren't known by the resource manager which has only knowledge of the request type, min/max volume values, trigger time, deadline and priority.

Resource Manager

The resource manager represents the core of our work and encompasses both the mapper and predictor module. It contains the implementation of the proposed mapping algorithms and, for comparison purposes, the implementation of a standard static round-robin placement algorithm in addition to the proposed dynamic methods. Moreover, it keeps track of every missed deadline and assigns a penalty to each application execution calculated as follow: penalty n = prio n * (end time n -deadline n ) if end time n > deadline n or 0 otherwise. The applications' priorities being correlated to the operational interest of a dwell, the sum of suffered penalties during a run represents a relevant estimation of a mapping strategy's impact on the QoS provided to the user while running a scenario.

Platform Simulator To both implement the full MAPE loop and evaluate the proposed methods, an execution environment was required. In order to have more control over it and flexibility on testing parameters, a computing platform simulator has been designed. However, to retain meaningful evaluation results and feedback to the predictor, this simulator has been modeled on an actual platform. Moreover, to accurately simulate the activities' execution, their memory access volume as well as interference (i.e. resource access conflicts) with other running activities are represented. Both the platform simulator and the interference model have been validated by domain experts.

To obtain the following results, the considered platform contains 4 racks linked via an Ethernet switch, each one hosting 6 dual-processor boards with one shared memory per board. Inside a rack, all boards communicate also via an Ethernet switch. Note that each rack receives input data from the front-end of one antenna which is stored in an input memory and must send results to a fixed output memory.

Results Analysis

We now compare the performance of different mapping methods in several operational scenarios as well as the influence of anticipation delay (i.e. the time between the decision taking process and the application deployment) on the quality of results produced. We first identify the four operational scenarios used in the following experiments:

-SCE 1 where all antennas share an equal, average load.

-SCE 2 representing a classic shore surveillance scenario with one antenna (pointing towards the coastline) illuminating a high-complexity environment with a very high number of detections, its 2 neighbors harboring average load and the last antenna treating only few detections. -SCE 3 where 2 antennas face numerous detections and the other 2 an average amount.

-SCE 4, where all antennas have to treat an important quantity of detections.

While SCE 1 and SCE 4 are mostly used as reference points, the second scenario SCE 2 presents a real operational interest as it represents a traditionally problematic case.

Each result presented below comes from the average of 10 simulation runs with different random seed values. During each run 2000 requests are generated, each request containing 1 computing activity and 1 to 2 communication activities, which translates in an average of 5000 activities mapped per run. Fig. 3 shows the average observed latencies of deployed applications while using a standard roundrobin static mapping method. As it is clearly visible in SCE 2 and SCE 3, using a pre-determined mapping prevents online resource sharing and can cause a great load unbalance between computing racks. On the other hand, when using the dynamic load-balancing approach described in 4.3.2 (see Fig. 4) we can see that resource sharing has been efficiently carried out, narrowing the gap between computing racks load in both SCE 2 and SCE 3. Moreover, we can observe a global latency reduction anywhere between 18% and 32% across all scenarios. This is due to the fact that our mapping method avoids random latency spikes that can happen while using a static mapping method. These spikes can be caused by the execution of a heavy activity on a pre-determined processor which is possibly already busy executing another expensive activity, effectively leading to an increased queuing time. Additionally, the execution time gains provided by the proposed predictive mapping system are only partly due to the resource sharing between racks as, when preventing the inter-rack migration of activities 10 to 20% execution time reduction was still observed. While looking at the QoS provided by both static and predictive methods in Table .1, one can notice an even greater difference in terms of perceived QoS. In the Static Mapping column we can observe that, even in a average load scenario (SCE 1 ), a few latency spikes cause some deadline misses, generating some QoS penalties. While the Load-Balancing method consistently maintains 0 deadline misses.

In SCE 2 and SCE 3 massive differences can be seen in provided QoS with the load balancing method, only missing 3.6 to 28.2 deadlines and the static method between 136.6 and 284 on average. This represent a more than ten times average QoS improvement under the most realistic operational scenarios.

Finally, in SCE 4 where all racks are overloaded, around one fourth of the deadlines are missed with the static mapping and one eleventh with the dynamic method. Note that these show as well that the use of an efficient load-balancing helps mitigating the effects of an overload. While the load prediction method misses only three times fewer deadlines, it receives only less than 10% the amount of QoS penalty suffered by the static mapping. Fig. 5 shows the impact of computing load of applications on the amount of QoS penalty received for different mapping methods on one computing rack. The computation load is normalized on the computation volume at which the first deadline misses (due to latency spikes) are observed while using the static method. It is possible to observe a steep increase in penalty for all mapping Fig. 5: Impact of Computation Load on the Quality of Result methods around at around three times this load. At this point we reach the maximum capacity of the computing platform and enter a global overload state. As every application must be executed, numerous computing activities will accumulate inside processors' execution queue and be executed well after their deadlines, generating high penalty.

However, when using a dynamic load-balancing technique, the computing volume at which an overload state is entered differs vastly from the one at which the static method overloads. Even when not taking into account random latency spikes happening for volumes from 1 to 1.5, a constant increase in observed penalty can be noticed for the static mapping from 1.5 onward. On the other hand, when using load-balancing or QoS-aware mapping methods, the first deadline misses and received penalty only appear at the 2.75 mark. This is a straight 83% increase in the computation volume that the platform can absorb before encountering any QoS issue. The QoS-aware mapping method introduced in 4.3.3 shows results close to the first load balancing mapping with an average penalty reduction close to 10%. Moreover, both the QoS-aware and the load-balancing methods tend to mitigate the QoS impact of an overload as they consistently suffer a lower QoS penalty than the static round-robin technique.

As discussed before, the moment at which an application placement decision is taken can greatly influence the quality of load prediction used to take this decision and, thus, impact the quality of produced mapping. This is especially true when operating close to the platform's maximal load. For example, when using a 2.5 volume in SCE 3, the average number of missed deadlines can vary from 0 to 38 depending on the anticipation with which the decision is taken. An ideal anticipation of 0 means that the mapping decision is taken instantly at trigger time and yields perfect results when not in an overload state. On the contrary, placing an application as soon as its execution request is received (between 100 to 300 ms before its execution) often yields noticeably inferior results due to more approximate predictions on the platform's future state. The results presented above were obtained using a 10ms anticipation time which provides near optimal results while being a realistic mapping decision delay.

Discussion

The results presented in the previous section are encouraging and prove the potential gains of QoS-aware dynamic resource manager for the specialized and demanding systems that are multifunction radars. However, while this work's context seems very specific, the presented predictive load balancing mechanism could be adapted to other domains with similar needs such as highperformance automotive computing platforms. For example, for high performance sensors, this technique could be used to dynamically select the proper algorithms variant that fits best the current observed situation, while maintaining real-time objectives. Moreover, while they operate at completely different scales, cloud environment processing business workflows share some of our use-case constraints [START_REF] Xu | Near-optimal dynamic priority scheduling strategy for instance-intensive business workflows in cloud computing[END_REF] and could benefit from an online predictive mapping method.

In addition, this approach opens important opportunities of improvement. First of all, the realized resource management system currently stands in a passive position due to its lack of control over incoming requests and its obligation to execute each of them. Thus, it can only increase the computing load supported by the computing platform before reaching an overload state, with no means to prevent it. Two solutions can be envisaged to address this issue. The first one is the implementation of an admission control unit discarding low priority applications to make room for high priority ones when anticipating an overload. The other envisaged solution is a second control loop between the resource manager and the radar manager. This loop would receive regular updates of the platform state to help determine which type of waveform it could process efficiently as well as to exploit free computing opportunities by launching context-aware useful functions and, thus, enhance the QoS provided to the operator.

While the results of the QoS-aware mapping method are encouraging, one anticipates that its efficiency will largely depend on the relevant weighting of priorities and deadline penalty factors. These parameters being characterized by the radar management system, future work will include the investigation of the influence of these factors when using real-life workloads. Moreover, the computing time prediction algorithms used in the predictor are limited by the worst-case approach used. We are currently exploring a mixed-critical stochastic approach aiming at providing an even better trade-off between QoS provided and predictability of the systems.

To explore these ideas, the simulator presented in this paper is being extended by adding support for heterogeneous processing elements as well as the generation of more complex and diverse workloads. This will allow us to finely tune the prediction model to improve the QoS-aware mapping method presented above as well as to profile the mapping algorithms on the target platform. These profiling data are crucial as they will determine the computing volume limit of the envisaged mapping heuristics. This will directly influence the size and complexity of application graphs that can be considered for further tests. In addition to that, several other QoS metrics, both radar specific (false alarm rate) and generic (processor slack time minimization), are investigated to further improve the mapping results' quality.

Finally, as a centralized resource manager is currently in use, the computing platform's scaling might be an issue. As a fully distributed resources management system is hardly conceivable in the studied use-case, a hierarchical manager composed of both a central unit and locally distributed manager will be considered. Such systems have already been successfully implemented in dynamic large-scale environments such as clouds [START_REF] Wang | Dynamically hierarchical resource-allocation algorithm in cloud computing environment[END_REF].

Conclusion

In this paper we presented a dynamic mapping method for real-time application execution on a heavily-constrained embedded architecture. This method was tested on an AESA radar usecase using a custom simulator. We showed that this approach allows us to obtain lower execution latencies than current mapping solutions while maintaining high predictability and allowing gradual performance degradation in overload scenarios.

Fig. 1 :

 1 Fig. 1: Application execution timeline

Fig. 3 :Fig. 4 :

 34 Fig. 3: Latency Using Static mapping

Table 1 :

 1 QoS results.

	Static Mapping Load-Balancing
	SCE 1 penalty 3.21	0
	nb miss 23	0
	SCE 2 penalty 69.67	0.17
	nb miss 136.6	3.6
	SCE 3 penalty 172.36	2.37
	nb miss 284	28.2
	SCE 4 penalty 342.06	31.8
	nb miss 507.4	175

Acknowledgments

This work was made possible thanks to the support of the Surface Radar Business Line of Thales.