Sofiane Khadraoui

Micky Rakotondrabe

Philippe Lutz

Interval force/position modeling and control of a microgripper composed of two collaborative piezoelectric actuators and its automation

Keywords: Collaborative piezoelectric actuators, Interval modeling and control, Force/Position signals, Robust controller, Parametric uncertainties, Microgrippers, Automated pick-and-place tasks

This paper deals with the modeling and control of a microgripper devoted to micromanipulation and microassembly applications and tasks. Based on two collaborative piezoelectric actuators, the microgripper is typified by a high sensitivity to the environment, in particular a high sensitivity to the properties of the manipulated objects. This sensitivity makes the behavior of the microgripper variable and uncertain versus the environment and consequently makes the tasks lose performances. A possible way to overstep that problem is to model the microgripper behavior and its dependency with the environment as perfect as possible and then calculate a controller from this. However, such model is complex to handle and the yielded controllers are often very complex for implementation. In this paper, we propose to use interval models to describe the behavior of the piezoelectric actuators that compose the microgripper. Then a controllers synthesis consisting in combining interval techniques and classical control theory is proposed. Both the position and the force raised in the microgripper are considered. The main advantages of the proposed technique are: 1) ease and natural way to model the uncertainties, 2) the robustness of the synthesized controllers, 3) and the derivation of low order controllers that are easier for implementation relative to those of classical robust control techniques. Finally, the paper presents the application of the controlled microgripper to an automated pick-transport-and-place task of micro-objects. This automated task demonstrates the efficiency of the control technique in micromanipulation and microassembly applications.

INTRODUCTION

Pick-and-place tasks are common in micromanipulation, microassembly and micrograsping applications. A pick-and-place of small objects (objects having sizes less than one millimeter) generally includes three principal subtasks: grasping the object, moving it from its initial location to a desired one, and releasing it at this desired location. While micromanipulation and microassembly applications require a micrometric or submicrometric resolution and accuracy, the elementary pick and place operations should be performed with the same performances. To reach such severe accuracy, actuators fabricated on the basis of smart materials are often employed because of their capability to replace hinges by flexure techniques and consequently to highly improve the positioning resolution. In fact, mechanical clearances in hinges drastically decrease the resolution. Piezoelectric materials are one of the most appreciated smart materials thanks to their favorable properties: high bandwidth (more than the kiloHertz Automatic Control and Micro-Mechatronic Systems Department, AS2M FEMTO-ST Institute, UMR CNRS 6174 / UFC / ENSMM / UTBM 24 rue Alain Savary, Besançon 25000, France. Corresponding author: mrakoton@femto-st.fr is possible), high resolution (tens of nanometers can be obtained) and high force density. Furthermore, the fact that the power supply of piezoelectric materials is electrical makes their design and control easy. Finally, piezoelectric devices can be used as a sensor or as an actuator.

Piezoelectric microgrippers are one of the well-known devices utilized in microrobotics and microassembly applications for handling and manipulating micro-objects. A piezoelectric microgripper is generally made up of two collaborative piezoelectric actuators with cantilevered structures. Each cantilever can be bent independently by applying an electrical voltage. The bendings of the two actuators can be afterwards used to manipulate, to pick and to move small objects. Various prototypes of piezoelectric microgrippers have been developed to grasp objects with different shapes and characteristics [START_REF] Haddab | A microgripper using smart piezoelectric actuators[END_REF][START_REF] Agnus | Overview of microgrippers and design of a micromanipulation station based on a mmoc microgripper[END_REF][START_REF] Menciassi | Force feedback-based microinstrument for measuring tissue properties and pulse in microsurgery[END_REF][START_REF] Rakotondrabe | Development and Force/Position Control of a New Hybrid Thermo-Piezoelectric microGripper dedicated to micromanipulation tasks[END_REF]. When using piezoelectric microgrippers, many factors may result in a difficulty to achieve the desired performances: 1) the manipulated object itself affects the dynamics of the actuators [START_REF] Eppinger | On dynamic models of robot force control[END_REF], 2) small systems like microgrippers are very sensitive to the environment, in particular to the surrounding vibration and to any thermal variation, 3) and nonlinearities (hysteresis and creep) that typify piezoelectric actuators make difficult the achievement of good accuracy [START_REF] Rakotondrabe | Complete open loop control of hysteretic, creeped and oscillating piezoelectric cantilever[END_REF]. It is therefore essential to control the actuators of the piezoelectric microgripper in order to reach the severe performances required in micromanipulation and microassembly applications.

For the success of manipulation of micro-objects, it is recognized that both the positioning and the manipulation force are controlled during the tasks. When using piezoelectric microgripper, this can be achieved by controlling on position one of the two actuators while controlling on force the second one in order to maintain the object and to avoid any damage of the actuator or of the object [START_REF] Rakotondrabe | Development and Force/Position Control of a New Hybrid Thermo-Piezoelectric microGripper dedicated to micromanipulation tasks[END_REF][START_REF] Rakotondrabe | Modelling and robust position/force control of a piezoelectric microgripper[END_REF]. The above mentionned characteristics (nonlinearities, sensitivity to the environment,...) make however very challenging the control of piezoelectric microgrippers. Additionally to these, the lack of convenient sensors for the micro-world in general compromises the efficiency of the controllers since additional uncertainties from the sensors raise.

The control of uncertain systems is traditionally accomplished by means of robust control laws such as H ∞ and µ-synthesis. The robustness of these approaches has been proven in several applications (SISO and MIMO systems), including in micromanipulation based on microgrippers [START_REF] Rakotondrabe | Development and Force/Position Control of a New Hybrid Thermo-Piezoelectric microGripper dedicated to micromanipulation tasks[END_REF][START_REF] Rakotondrabe | Modelling and robust position/force control of a piezoelectric microgripper[END_REF]. However the major limitation of such robust control approaches is the derivation of high orders controllers which are not convenient for embedded microsystems [START_REF] Khadraoui | Interval Modeling and Robust Control of Piezoelectric Microactuators[END_REF]. In fact, the complexity of high orders controllers makes them hardly implementable in embedded calculators employed in embedded microsystems. In this paper, we propose an approach based on interval analysis to control piezoelectric microgrippers. The approach consists in modeling the piezoelectric microgripper as an uncertain system where the uncertain parameters are assumed to be bounded by intervals. These bounded uncertain parameters are implicitly linked to the nonlinearities of the piezoelectric actuators, the sensitivity of the microgripper to the object characteristics and to the environment, as well as to the uncertainties raised by the limitated performances of the sensors. The main advantages of this approach is the ease and the natural way to model the uncertain parameters.

Interval analysis has been already introduced in control engineering for modeling, for stability analysis and for control design in uncertain systems. In [START_REF] Keel | Control system design for parametric uncertainty[END_REF], the modeling of systems with parametric uncertainties using a transfer function with interval parameters has been addressed. The robust stability analysis of systems subjected to uncertain parameters has also been discussed in many works [START_REF] Jaulin | Applied Interval Analysis[END_REF][START_REF] V L Kharitonov | Asymptotic stability of an equilibrium position of a family of systems of linear differential equations[END_REF][START_REF] Walter | Guaranteed characterization of stability domains via set inversion[END_REF][START_REF] Smaginaa | Using interval arithmetic for robust state feedback design[END_REF][START_REF] Chen | Robust controller design for interval process systems[END_REF]. Other works dealing with the robustness on performances can be found in [START_REF] Khadraoui | Interval Modeling and Robust Control of Piezoelectric Microactuators[END_REF][START_REF] Rakotondrabe | Performances inclusion for stable interval systems[END_REF][START_REF] Li | Interval Model Control of Consumable Double-Electrode Gas Metal Arc Welding Process[END_REF][START_REF] Chen | A two-degrees-of-freedom design methodology for interval process systems[END_REF][START_REF] Bondia | A geometric approach to robust performance of parametric uncertain systems[END_REF]. In particular, the work in [START_REF] Rakotondrabe | Performances inclusion for stable interval systems[END_REF] presented an interesting result on the inclusion of performances of interval systems. In a simple way, this result can be used to design a robust controller ensuring some desired performances specifications. In our pre-vious work [START_REF] Khadraoui | Interval Modeling and Robust Control of Piezoelectric Microactuators[END_REF], we demonstrated that interval tools could be of a great interest in the modeling and control of systems working at the micro-scale where the effect of uncertainties on the systems performances is significant. In this paper, the modeling and the robust controllers design for microgrippers by using interval techniques is proposed. Both the force and the displacement in the microgrippers are considered. While the modeling consists in using intervals to bound the uncertain parameters, the controllers synthesis is based on the performances inclusion theorem [START_REF] Rakotondrabe | Performances inclusion for stable interval systems[END_REF]. On the one hand, the interval modeling permits an ease and natural way to describe the uncertain parameters by employing a lower and upper bounds. On the other hand, the advantage of the proposed controllers synthesis relative to classical techniques [START_REF] Rakotondrabe | Development and Force/Position Control of a New Hybrid Thermo-Piezoelectric microGripper dedicated to micromanipulation tasks[END_REF][START_REF] Rakotondrabe | Modelling and robust position/force control of a piezoelectric microgripper[END_REF] is the derivation of low orders controllers that are more convenient for implementation and for real time applications.

The remainder of this paper is organized as follows. In section II, we briefly give some preliminaries on interval arithmetic, interval systems and on the performances inclusion theorem [START_REF] Rakotondrabe | Performances inclusion for stable interval systems[END_REF] that will be used further. In section III, the piezoelectric microgripper to be used and its actuators are presented. Afterwards, in section IV, we present the interval modeling of the microgripper. This is composed of: the position (deflection) modeling of one actuator, and the force modeling of the second actuator. In section V, the design of a robust controller for the position and the design of a robust controller for force are detailed. The proposed synthesis technique is based on the performances inclusion theorem. Sections VI is devoted to the application of the designed controllers on positioning tasks with consideration of the graspping (manipulation) force. Finally, in section-VII, we apply all the above results to an example of automated pick-and-place task. All along the paper, experimental results validate the efficiency of the proposed method.

BRIEF PRELIMINARIES ON INTERVAL ANALYSIS

Basic Terms and Concepts on intervals

More details on preliminaries given here can be found in [START_REF] Jaulin | Applied Interval Analysis[END_REF] or [START_REF] Moore | Interval Analysis[END_REF].

A (closed) interval number denoted by [x] is a set of real numbers defined as follows:

[x] = [x -, x + ] = x ∈ R/x -≤ x ≤ x + (1)
where x -and x + are the left and right endpoints of [x] respectively.

[x] is said degenerate if x -= x + . By convention, a degenerate interval [a, a] can be defined with the real a.

The width of an interval [x] is given by w

([x]) = x + - x -, the midpoint of [x] is given by mid([x]) = x + +x - 2 and the radius of [x] is defined by rad([x]) = x + -x - 2 .
The elementary mathematical operations can be extended to intervals. Let [x] = [x -, x + ] and [y] = [y -, y + ] be two intervals and let • ∈ {+, -, * , /} be a law. These basic mathematical operations are summarized in Table 1 and give as below:

[x] • [y] = {x • y |x ∈ [x], y ∈ [y] } (2)
Table 1: Arithmetic operations on intervals [START_REF] Jaulin | Applied Interval Analysis[END_REF][START_REF] Moore | Interval Analysis[END_REF].

Operation Definition + [x] + [y] = [x -+ y -, x + + y + ] - [x] -[y] = [x --y + , x + -y -] * [x] * [y] = [min{x - * y -, x + * y -, x - * y + , x + * y + }, max{x - * y -, x + * y -, x - * y + , x + * y + }] / [x]/[y] = [x] * [1/y + , 1/y -], 0 / ∈ [y]
2.2. Interval systems Definition 1: Parametric uncertain systems can be modeled by interval systems. A SISO interval system that defines a family of systems is denoted [G](s, [p], [q]) and is described by a transfer function with interval parameters as follows:

[G](s, [p], [q]) = m ∑ j=0 [q j ]s j n ∑ i=0 [p i ]s i =        m ∑ j=0 p j s j n ∑ i=0 p i s i p i ∈ [p - i , p + i ], p j ∈ [p - j , p + j ]        (3) Such as: [q] = [[q 0 ], ..., [q m ]] and [p] = [[p 0 ], ..., [p n ]] are boxes (i.e.

vectors of interval numbers).

The following theorem, called performances inclusion theorem, states the inclusion of performances of two interval systems and is due to [START_REF] Rakotondrabe | Performances inclusion for stable interval systems[END_REF]. Consider two interval systems having the same structure, i.e. having the same degrees of polynomials:

[G 1 ] (s) = m ∑ j=0 b 1 j s j n ∑ i=0 [a 1i ] s i and [G 2 (s)] = m ∑ j=0 b 2 j • s j n ∑ i=0 [a 2i ] • s i Theorem 1: (Performances inclusion theorem) i f [b 1 j ] ⊆ [b 2 j ] ∀ j = 0, ..., m [a 1i ] ⊆ [a 2i ] ∀i = 0, ..., n ⇒    [g 1 ](t) ⊆ [g 2 ](t) ∀t [ρ] ([G 1 ] ( jω)) ⊆ [ρ] ([G 2 ] ( jω)) [ϕ] ([G 1 ] ( jω)) ⊆ [ϕ] ([G 2 ] ( jω)) ∀ω
where [g i ](t) is the (time) impulse response of system

[G i ](s), [ρ] ([G i ] ( jω)) is its magnitude and [ϕ] ([G i ] ( jω))
is its phase.

Proof: See [START_REF] Rakotondrabe | Performances inclusion for stable interval systems[END_REF]. Theorem 1 states that if each interval parameter in [G 1 ] (s) is included in its corresponding parameter in [G 2 ] (s), then the time response (impulse response, step response, etc.) of [G 1 ] (s) will be bounded by that of [G 2 ] (s). The same inclusion holds for the frequency response (Bode, Nyquist, Black-Nichols). In other words, the performance of the system [G 1 ] (s) will be bounded by the performance of the system [G 2 ] (s).

PRESENTATION OF THE PIEZOELECTRIC MICROGRIPPER

In this section, we present the developed microgripper used in this paper. The microgripper is made up of two similar unimorph piezoelectric cantilevers, also called piezocantilevers. Each actuator can be actuated independently. A unimorph piezocantilever is made up of one piezoelectric layer and one non-piezoelectric (or passive) layer glued themselves. When a voltage is applied to the piezoelectric layer, it contracts or expands depending on the direction of the electrical field. This results in a global deflection of the whole cantilever. The resulting deflection can be used to precisely position a small object that is in contact with the actuated cantilever. Here, the piezocantilevers have a PZT-PIC151 (lead zirconate titanate) piezoelectric layer and a copper material based passive layer. They have thicknesses of 200 µm and of 100 µm respectively. Sizes of each actuator (piezocantilever) are approximately length × width × thickness = 18 mm × 2 mm × 0.3 mm. Fig. 1 pictures some of the developed piezocantilevers.

The microgripper is obtained by glueing two piezocantilevers on a double-sided PCB (Printed Circuit Boards) as pictured in Fig. 2-a. The conductive adhesive "EPO-TEK H22" is used as the glue. This facilitates the electrical connection between the piezocantilevers and the PCB.

Fig. 2-b presents a photography of the developed microgripper. In the figure, x is the axis of the gap between both actuators and y is the perpendicular axis. Both actuators can bend along the x axis.

Considering the ranges of deflection of both piezocantilevers, the gap between their tips is chosen to be 350 µm. This allows to manipulate objects of different sizes. It is also possible to fix an end-effector at the tip of each actuator in order to easily manipulate objects with different shapes. When positive or negative voltages are applied to the piezocantilevers, the microgripper closes or opens around its initial position allowing the grasping and releasing of an object initially placed within the gap. However, in order to correctly success pick-and-place tasks, it is recommended that one piezocantilever is controlled on position (deflection) and the other one is controlled on ma-nipulation force. In the next sections, we separately give a model and design two controllers for the control of the position and force. In other words, each piezocantilever is independently modeled and controlled: one in position and the second one in force. In the last sections of the paper, both controllers that are independently designed will be employed to perform an automated pick-and-place tasks.

INTERVAL MODELING OF THE MICROGRIPPER

Let U δ (resp. U F ) be the input voltage applied to the piezocantilever controlled on position (resp. on force). Furthermore, the output position (deflection) and the manipulation force are denoted by δ and F respectively. Two approaches are possible to model a microgripper. The first approach is based on the use of one single model that relates the two input voltages (U δ and U F ) and the two outputs (position δ and manipulation force F) as schematized in Fig. 3-a. This multivariable model describes more accurately the microgripper behavior as the coupling between the variables are taken into account. It is therefore possible to find a multivariable controller that can ensure some robust performance requirements for the closed-loop system. However, this approach raises many difficulties due to the fact that it requires to exactly know the properties of the manipulated objects and the interferences between the two actuators. Indeed, for each manipulated object, a characterization and modeling of the microgripper is required. The second approach consists in modeling independently each actuator of the microgripper [START_REF] Rakotondrabe | Modelling and robust position/force control of a piezoelectric microgripper[END_REF] (see Fig. 3-b) such that one actuator is modeled on deflection while the second one is modeled on force. The main advantage of this approach is the derivation of simpler models, more precisely the derivation of two single-inputsingle-output (SISO) systems which are easier to handle. In this approach, the couplings between variables are considered as external disturbances or internal uncertainties that should be taken into account during the controllers synthesis. This latter approach will be used in the paper.

Interval modeling of the voltage-deflection relation-

ship Notice that all fabricated piezocantilevers (and therefore the two actuators that constitute our microgripper) are similar. Let us therefore assume that the initial models of the two piezocantilevers, linking the input voltage U i and the output deflection δ i (where the subscript i = {1, 2} indicates the first or the second actuator), have the same structure. To process, let us consider Fig. 4 where a piezocantilever bends along the x axis when it is subjected to an electrical voltage. The linear relationship linking the input U i and the output δ i of the piezocantilever is [START_REF] Rakotondrabe | Quadrilateral modeling and robust control of a nonlinear piezoelectric cantilever[END_REF]: where G i is a transfer function and s the Laplace variable. The linear model in (4) does not reflect the real behavior of the actuator. This model does not account for the nonlinearities typifying the piezoecantilevers and for the behavior variation due to the environment changes. This model is consequently uncertain. To complete this model, we propose to introduce intervals to bounds the model uncertainties. Let us first identify the parameters (which are not interval parameters) of ( 4) for each actuator of the microgripper. For that, a step voltage U i = 40V is first applied to each piezocantilever, then the resulting output deflection δ i is measured. The identification of the parameters is performed using the System Identification Toolbox of Matlab and the output error method [START_REF] Ljung | System identification toolbox user's guide[END_REF]. In this particular application, a second order model has been chosen because the first resonant mode is assumed here to be sufficient. We obtain:

δ i = G i (s)U i (4)
G 1 (s) =
1.421 × 10 -4 s + 1 4.88 × 10 -8 s 2 + 4.33 × 10 -6 s + 0.822

G 2 (s) =
1.399 × 10 -4 s + 1 6.6 × 10 -8 s 2 + 4.91 × 10 -6 s + 0.93 [START_REF] Eppinger | On dynamic models of robot force control[END_REF] Let us now derive the interval model, [G δ ](s), which relates the input voltage U i and the output deflection δ i . The aim is to have one model that encloses the two previous models G 1 (s) and G 2 (s). For that, we consider each parameter in G 1 (s) and the corresponding parameter in G 2 (s) as endpoints of the interval parameter in [G δ ](s). We obtain:

[G δ ](s) = Num δ (s) Den δ (s) (6)
where

       Num δ (s) = [1.
Now, we propose to extend the interval parameters in [START_REF] Rakotondrabe | Modelling and robust position/force control of a piezoelectric microgripper[END_REF] such that we are sure to really bound the two models. Furthermore, in such a way, we increase the range of the modeled uncertainties and then increase the chance to include by other sources (nonlinearities, variation due to the environment, ...). It is worth to notice that if the intervals are too large, finding a suitable controller may not be possible. A compromise should be done between the widths of interval parameters and the existence of a controller. Based on the idea of trial-error, we find that 10% of extension of each interval parameter width is a good compromise for the example in this paper. Thus, the final interval model to be used for the controller design and that relates the deflection and the voltage has the following polynomials: Remark 1: The voltage-deflection model described by [START_REF] Rakotondrabe | Complete open loop control of hysteretic, creeped and oscillating piezoelectric cantilever[END_REF] will be utilized for the piezocantilever controlled on position. This piezocantilever can be any of the set of piezocantilevers since all of them have a model enclosed by the interval model. For the microgripper, this piezocantilever controlled on position can be the left actuator or the right one. The voltage-force model which will be derived in the next subsection is also valid for both piezocantilevers of the microgripper. To conclude, if the left (resp. right) piezocantilever is selected as a position actuator, the right (resp. left) piezocantilever should be utilized as the force actuator. The voltage-deflection model in ( 6) and the voltage-force model of the next subsection are valid for both actuators.

       Num δ (s) = [1.

Interval modeling of the voltage-force relationship

Let Fig. 5 presents a piezocantilever manipulating an object with a force F. The variables considered in Fig. 5 are: • F is the force applied by the piezocantilever to the micro-object; • δ represents the deflection at the tip of the piezocantilever. Notice that the subscript i is removed for the sake of simplification of notation; • and U is the voltage applied to the piezocantilever.

When the piezocantilever is in contact with the object, the static relationship that relates the force F, the deflection δ and the applied voltage U is given as follows [START_REF] Rakotondrabe | Modelling and robust position/force control of a piezoelectric microgripper[END_REF] [23] [START_REF] Pons | Emerging actuator technologies: a micromechatronic approach[END_REF]:

δ = d p U -s p F (9)
where s p > 0 is the elastic coefficient of the piezocantilever and d p is the piezoelectric constant.

It has been demonstrated in [START_REF] Haddab | A microgripper using smart piezoelectric actuators[END_REF] that the dynamics D(s) of the voltage-deflection (U, δ ) transfer function and the dynamics of the voltage-force (F, δ ) transfer function are equal. Consequently, introducing the dynamics D(s) in (9) yields:

δ = (d p U -s p F)D(s) (10)
such that D(s = 0) = 1. The term d p D(s) is the transfer function that relates the deflection δ of the piezocantilever and the applied input voltage U which is the similar to (4), i.e. G(s) = d p D(s).

According to [START_REF] Rakotondrabe | Modelling and H ∞ force control of a nonlinear piezoelectric cantilever[END_REF], the deflection δ can also be expressed as function of the force F and the object characteristics as follows:

δ ≈ s o F (11)
where s o > 0 is the compliance of the manipulated object. Notice that ( 11) is valid when no gap exists between the piezocantilever and the object at the initial condition, i.e. at U = 0. If a gap exists before the manipulation, it is always possible to achieve this condition by applying a variable change [START_REF] Rakotondrabe | Modelling and H ∞ force control of a nonlinear piezoelectric cantilever[END_REF].

Combining [START_REF] Jaulin | Applied Interval Analysis[END_REF] and ( 11), the force applied to the object can be deduced:

F = d p s o D(s) + s p U = G F (s)U (12)
From ( 12), it is demonstrated that the behavior of a piezoelectric actuator manipulating an object depends on the stiffness ( 1s o ) of the object. Any change of manipulated object results in a significant change in the behavior of the actuator. This is why in micromanipulation and microassembly applications based on microgrippers, the performances are strongly affected by the environment. To consider this variablity, we propose to also use intervals to model and to bound the compliance s o :

[s o ] = [s - o , s + o ] (13)
where the left bound s - o represents the compliance of the most rigid object while the right bound s + o indicates the compliance of the most flexible object.

Remark 2: It is important to account these objects properties if the objective is the modeling and the control of the force. If these object properties are not conveniently considered, the performances of the manipulation system or even the stability will be lost. In this paper, we have proposed to account the compliances of the different objects by bounding them with one interval (see equation ( 13)). Consequently, we have only one model (interval model) valuable for the actuator and for any object within the set (interval). To identify the values of the compliance interval in equation ( 13), it suffices to use the compliance of the most flexible object and the compliance of the most rigid object. As soon as a controller from that model is found, the performances (and therefore the stability) will be ensured for any object with property within this set. The main limitation of the method is that when the interval compliance in equation ( 13) is too large, it may be difficult to find a controller that will ensure the performances for the whole set. In this case, an extension of the proposed method into interval adaptive control method can be proposed.

After introducing [s o ] in [START_REF] Walter | Guaranteed characterization of stability domains via set inversion[END_REF], we have:

F = d p [s o ] D(s) + s p U (14)
The model in ( 14) is with point parameters, except the compliance parameter which is interval. The model is therefore valuable for a set of objects but only with one piezocantilever. If we want to extend the validity of the model for a set of piezocantilevers, we also replace the dynamics D(s) and the parameters s p and d p into intervals. This has already been introduced in the previous subsection during the position modeling. Thus, [START_REF] Chen | Robust controller design for interval process systems[END_REF] becomes:

[F] = [d p ] [s o ] [D](s) + [s p ] U = [G F ](s)U (15)
Let us first characterize and define the interval of the elastic coefficient [s p ]. The derivation of such an interval [s p ] is based on the identification of the compliances s p i , i = 1, 2 of both piezocantilevers of the microgripper. To identify the compliance of a piezocantilever, a known mass m is first placed at its tip then the resulting deflection δ is measured. Using the mass m and the measured deflection δ , the compliance can be derived s p = δ m•g , where g is the terrestrial gravitational constant. In this application, a standard mass of m = 20mg has been used, which leads to the following compliances:

s p 1 = δ 1 m•g = 1.
3µm/mN and s p 2 = δ 2 m•g = 1.3µm/mN. As we can see, the coefficients obtained are equal, which means that the compliance is a degenerate interval:

[s p ] = s p = [1.3, 1.3]µm/mN = 1.3µm/mN (16)
The piezoelectric constant [d p ] and the dynamics [D](s) can directly be deduced from the model [G](s) in [START_REF] Khadraoui | Interval Modeling and Robust Control of Piezoelectric Microactuators[END_REF]. Since [G](s) = [d p ][D](s), we obtain from (8):

[d p ] = [1.0752, 1.2166] (17)
and

[D](s) = [1.3968, 1.4232] × 10 -4 s + 1 [5.1266, 8.2388] × 10 -8 s 2 + [4.593, 6.044] × 10 -6 s + 1 (18)
In this paper, we use two objects. The most elastic object is made based on polystyrene material while the most rigid object is a CMS resistance (see Fig. 6).

After identifying their compliances, the following interval parameter is obtained:

[s o ] = [1.93, 3.738] µm/mN (19)
Finally, the interval model [START_REF] Rakotondrabe | Performances inclusion for stable interval systems[END_REF] becomes:

[G F ](s) = Num F (s) Den F (s) (20)

CONTROLLER DESIGN USING INTERVAL ANALYSIS

In the previous section, two interval models have been derived: 1) the interval model that relates the input voltage (denoted U δ in the sequel) and the deflection δ (see ( 6)), 2) and the interval model that relates the input voltage (denoted U F in the sequel) and the manipulation force F (see [START_REF] Moore | Interval Analysis[END_REF]). These models can be indifferently used for the left or the right piezocantilever of the microgripper. In this section, the first model is utilized to design a controller for the position, while the second model is used to design another controller for the force. The uncertainties are defined thanks to the interval parameters of the models and if the controllers exist, they will be robust face to these uncertainties. In this paper, each controller is designed on the basis of the performances inclusion theorem reminded in Theorem 1.

Controller design for the deflection

Consider the scheme pictured in Fig. 7-a, in which the deflection of the actuator is enslaved by a controller C δ (s). In the figure, δ c represents the reference input. Fig. 7-b shows the corresponding block diagram that will be used for the synthesis, where [G δ ](s) is the interval model to be controlled.

The objective is to design a robust controller that ensures the following closed-loop performances specifications for any piezocantilever having a model lying in the interval model [G δ ](s):

• closed-loop behavior with very small overshoot, • settling time: t r ≤ 20 ms, • bounded steady state error: |ε| ≤ 1%.

A major advantage of the utilized technique here is that we can impose the structure of the controller, i.e. we can , where K p and K i are the proportional and the integral gains respectively. This choice is motivated by its simple structure (low order, only two parameters to be calculated) and its ability to ensure zero statical (steady-state) error thanks to the integral action. In general, when synthesizing a controller from an interval model [G δ ](s), an interval controller is yielded. The reason is that interval tools and techniques yield interval solutions. Let us therefore rewrite the controller as the following interval controller:

[C δ ](s) = [K p ]s + [K i ] s (22)
where [K p] and [K i ] are the interval proportional and integral gains respectively. The interval controller [C δ ](s) itself is not implementable but any point controller C(s) inside this (C(s) ∈ [C δ ](s)) will be and will satisfy the performances.

It is worth to mention that PI controller structure is very common in many applications and there are many methods to tune its parameters. An advantage of the technique dealt in this paper to tune PI controllers is the robustness face to uncertainties defined by intervals.

Let us first compute the closed-loop system using the interval model [G δ ](s) given in [START_REF] Rakotondrabe | Complete open loop control of hysteretic, creeped and oscillating piezoelectric cantilever[END_REF] and the PI controller [C δ ](s) [START_REF] Ljung | System identification toolbox user's guide[END_REF]. We obtain:

[H cl ](s) = 1 1 [G δ ][C δ ] + 1 = Num cl (s) Den cl (s) (23)
with:

                       Num cl (s) = [K p ] [K i ] [1.399, 1.421] × 10 -4 s 2 + [K p ] [K i ] + [1.399, 1.421] × 10 -4 s + 1 Den cl (s) = 1 [K i ] [
[K i ]
+ [1.399, 1.421] × 10 -4 s + 1 (24) Let us also transcribe the above specified performances for the closed-loop system into an interval transfer function denoted [H r ](s) and called interval reference model. A first order system can sufficiently approximate such performances:

[H r ](s) = [K e ] (1 + [τ]s) ( 25
)
where [K e ] and [τ] are calculated from the desired steady state error and settling time respectively as follows:

[τ] = 0, t r 3 = [0, 0.007] [K e ] = [1 -|ε| , 1 + -|ε|] = [0.99, 1.01] ( 26
)
The computation of the controller parameters [K p ] and [K i ] is based on the performances inclusion theorem (Theorem 1). The objective here is to find suitable values of [K p ] and [K i ] such that the closed-loop system [H cl ](s) satisfies the specified performances in [H r ](s). According to theorem Theorem 1, this problem can be formulated as follows: find the parameters [K p ] and [K i ] such that each parameter of [H cl ](s) is enclosed by the counterpart parameter in the interval reference model [H r ](s). This latter problem is however not well-posed if [H cl ](s) and [H r ](s) do not have the same structure, i.e. if their numerators (resp. denominators) do not have the same polynomial degree. In our case, the problem is not well-posed since [H cl ](s) has two zeros and three poles (see [START_REF] Pons | Emerging actuator technologies: a micromechatronic approach[END_REF]) while [H r ](s) does not have a zero and has only one pole (see [START_REF] Rakotondrabe | Nonlinear modelling and estimation of force in a piezoelectric cantilever[END_REF]). To render this problem well-posed, we propose to add two zeros and two poles to the interval reference model [H r ](s). These additional zeros and poles should be very quick (far away from the imaginary axis) compared to the actual zeros and poles of [H r ](s) in order to not affect the desired settling time t r . Finally, we propose to use the following structure for the interval reference model:

[H r ](s) = [K e ] 1 + [τ] 10 s 2 (1 + [τ]s) 1 + [τ] 10 s 2 ( 27
)
which can be rewritten as follows:

[H r ](s) = 0.01[τ] 2 s 2 + 0.2[τ]s + 1 0.01[τ] 3 [K e ] s 3 + 0.21[τ] 2 [K e ] s 2 + 1.2[τ] [K e ] s + 1 [K e ]
(28) Applying the performances inclusion theorem in Theorem 1, the problem consists in finding [K p ] and [START_REF] Rakotondrabe | Modelling and H ∞ force control of a nonlinear piezoelectric cantilever[END_REF] and [H r ](s) defined by [START_REF] Rakotondrabe | Combining self-sensing with an Unkown-Input-Observer to estimate the displacement, the force and the state in piezoelectric cantilevered actuator[END_REF]. This problem is equivalent to finding [K p ] and [K i ] such that:

[K i ] such that [H cl (s)] ⊆ [H r ](s), with [H cl ](s) defined by
                                               [K p ] [K i ] [1.399, 1.421] × 10 -4 ⊆ 0.01[τ] 2 [K p ] [K i ] + [1.399, 1.421] × 10 -4 ⊆ 0.2[τ] 1 [K i ] [4.88, 6.6] × 10 -8 ⊆ 0.01[τ] 3 [K e ] 1 [K i ] [4.33, 4.91] × 10 -6 + [K p ][1.399, 1.421] × 10 -4 ⊆ 0.21[τ] 2 [K e ] ([Kp]+[0.822,0.93]) [K i ] + [1.399, 1.421] × 10 -4 ⊆ 1.2[τ] [K e ] 1 ⊆ 1 [K e ]
(29) Remark that the steady state error is always null ([H cl ](s = 0) = 1) thanks to the presence of the integral action in the controller. This can also be verified using the last inclusion of (29: 1 [K e ] = 1 [0.99,1.01] = [0.99, 1.01] ⊇ 1. The problem of finding [K p ] and [K i ] will therefore be done with the remaining inclusions of (29). The problem is a set inversion problem, i.e. finding a solution of set of points or of intervals in functions. A set inversion problem can be solved using interval tools and techniques. For instance, the SIVIA algorithm (set inversion via interval analysis) [START_REF] Jaulin | Set inversion via interval analysis for nonlinear bounded-error estimation[END_REF] can be employed to solve the above problem (29). The algorithm requires an initial box (initial vector of intervals) and an accuracy of computation. After the application of this algorithm with an initial box

[K po ] × [K io ] = [0.1, 0.6] × [0,
500], we obtain results shown in Fig. 8. In this figure, the area S c corresponds to the solution of parameters

[K p ] × [K i ] of the controller [C δ ](s)
for which the desired closed-loop performances specifications are met. The controller being interval, it cannot be directly implementable. However, any arbitrary choice of parameter values K p and K i within the solution S c provide an implementable controller C δ (s) = K p s+K i s that is guaranteed to ensure the performances. In this example, we choose the following controller to be implemented for the position control: Remark 3: If no controller can be found during the synthesis, the following steps are proposed.

C δ (s) = 0.2s + 200 s (30)
• 1) Restart the computation of the controller using other initial boxes

[K po ] × [K io ].
It is possible that the initial box previously used did not contain the solution S c . • 2) If the problem is still not feasible even after trying different initial boxes, it is possible that the imposed structure of the controller is not appropriate for solving the problem. The actual controller structure (in this example, a PI-structure) should be changed into a higher order structure.

• 3) It is also possible that the specified performances specifications were too severe. In such a case, a relaxation of the specifications is recommended before recalculating a controller.

Controller design for the force

In the force control design, we use the scheme pictured in Fig. 9-a. In this figure, F c represents the reference of the closed-loop system and C F (s) the controller to be computed. Due to the lack of convenient force sensor, we propose to employ a force observer devoted to piezocantilevers. The force observer as we proposed and demonstrated in [START_REF] Rakotondrabe | Force estimation in a piezoelectric cantilever using the inversedynamics-based UIO technique[END_REF][START_REF] Rakotondrabe | Combining self-sensing with an Unkown-Input-Observer to estimate the displacement, the force and the state in piezoelectric cantilevered actuator[END_REF] is independent from the object characteristics. Furthermore, the force observer is 'closed loop'. The technique, called uknown input observer based on the inverse dynamics, consists in considering the force as an unknown input disturbance and then estimating this latter by inverse dynamics. The convergence of the estimate force has been demonstrated and a set of experimental results have confirmed the observer technique. The observer has at its inputs the input voltage U F and the measured deflection δ . Fig. 9-b presents the block diagram of the feedback control. The model which will be used for the controller synthesis is the interval model [G F ](s) defined in [START_REF] Moore | Interval Analysis[END_REF]. The use of this interval model allows us to find to a robust controller for a set of piezocantilevers, including the two piezoecantilevers of the microgripper, and also for a set of manipulated objects having compliances within the interval defined in [START_REF] Bondia | A geometric approach to robust performance of parametric uncertain systems[END_REF]. The following closed-loop performances specifications are considered for the force control:

• negligible overshoot;

• settling time: t r ≤ 8 ms;

• and bounded steady state error: |ε| ≤ 1%.

Remark 4:

We have chosen a faster settling time for the force control compared to that of the deflection. This permits to be sure that the object is always maintained between the two piezocantilevers of the microgripper during a pick-and-place task. Indeed, when a deflection reference is applied to one of the actuators, the other actuator must react faster in order to avoid a release of the manipulated object.

For the controller C F (s), a proportional-integral (PI) structure is also chosen. The controller has been calculated using exactly the same procedcure than in the previous subsection concerning the deflection controller. A solution set S c corresponding to the parameters [K p ] × [K i ] was first obtained. Then, we choose from this set point parameters K p = 0.2 and K i = 1500 for the implemented controller. We obtain: C F (s) = 0.2s + 1500 s (31)

CONTROL OF THE MICROGRIPPER

The previous section was devoted to the design and calculation of two controllers C δ (s) and C F (s) for the control of the position and force, respectively. If C δ (s) (resp. C F (s)) is applied to the left piezocantilever of the microgripper, C F (s) (resp. C δ (s) ) must be applied to the right piezocantilever. In this section, the two designed controllers are implemented and applied to both actuators of the microgripper. Experimental tests are carried out to demonstrate their efficiency for position and force regulations when manipulating an object. For that one actuator is controlled on position, while the second one is controlled on force. Two objects are successively manipulated: a flexible object (polystyrene) and a rigid object (CMS resistance). Fig. 10 shows the setup used for the experiments. The setup is composed of:

• the microgripper with its two piezocantilevers;

• two optical sensors (Keyence LK2420) with a resolution of 10nm and an accuracy of 0.1µm. The two sensors are used to measure the deflections of the two piezocantilevers;

• a dSPACE board and a computer with Matlab/Simulink used to acquire in real-time data from the sensors, to generate the control signals U δ and U F , to implement the controllers C δ (s) and C F (s), and to implement the force observer as well. The refresh time of the dSPACE-board and of the Matlab/Simulink is set to 0.2ms. This value is sufficiently small to account for the dynamics of the piezoelectric actuators;

• and two high voltage amplifiers ±200 V that amplify the signals from the dPSACE/computer to supply the two actuators. In this subsection, the aim is to characterize the performances on the deflection when the manipulation force is varied.

First, we use the CMS resistance as the manipulated object (rigid object). The deflection and force are initially null. Then, a deflection step reference δ c = 20 µm is applied to the piezocantilever controlled on deflection. Afterwards, a series of constant force reference F c is applied to the other actuator and the effect of this force on the first actuator is observed. Fig. 12 pictures the results. At the time we apply the deflection reference of δ c = 20 µm (at t ≈ 0.45s), an effect is observed on the force response and is afterwards quickly rejected. During the series of steps for the force reference F c , an effect is also observed on the deflection but is still quickly rejected. To evaluate the obtained closed-loop performances, a zoom is taken from a deflection and force step responses in Fig. 12. The zoom are shown in Fig. 13. As we can see, the specifications were satisfied. Indeed, the overshoots and static errors are neglected, whereas settling times obtained are 14.4 ms and 4.1 ms for the deflection response and force response respectively. Now, we consider the polystyrene (flexible object) as the manipulated object. The same experimental procedure than with the rigid object is followed. The experimental results are presented in Fig. 14 and the zoom on the step responses are presented in Fig. 15. Once again, the specifications are satisfied with the flexible object in term of tracking performances and disturbance rejection. Indeed, the experimental settling times are 16.3 ms and 4.1 ms for the deflection and force control respectively while the overshoots and static errors are close to zero.

Regulation of the force

In this subsection, we characterize the behavior on the force when a deflection variation occurs. The two previous objects (CMS resistance rigid object, and the polystyrene flexible object) are still used. The experimental procedure is as follows. Initially we have δ = 0 and F = 0. Then, a force step reference of 5mN is applied to the actuator con- trolled on force. Afterwards, a series of variations of the deflection reference is applied to the other actuator. The effect of this deflection variations on the force behavior is finally observed and analyzed. The experimental results are presented in Fig. 16 for the rigid object and in Fig. 17 for the flexible object. From these figures, it is observed that any deflection variation has an effect on the force but this effect is quickly rejected thanks to the force controller C F (s). Furthermore, we see that the specifications in terms of overshoot, steady state error and settling time have been satisfied. Indeed, the overshoot and steady state error are neglected with both manipulated objects, while th experimental settling times are:

• about 13.7 ms and 3.8 ms for the deflection and for the force respectively, when manipulating the CMS resistance rigid object, • 16.9 ms and 3.2 ms for the deflection and for the force respectively, when manipulating the polystyrene flexible object.

To summarize, the calculated controllers C δ (s) and C F (s) have ensured the specified performances for the two piezoecantilevers of the microgripper for any manipulated object (rigid or flexible) with property defined in the interval compliance in [START_REF] Bondia | A geometric approach to robust performance of parametric uncertain systems[END_REF]. The experimental results in Fig. 12, Fig. 13, Fig. 14, Fig. 15, Fig. 16 and Fig. 17 to the couplings (effect of the force of one actuator on the deflection of the other actuator, or conversely). But as expected, these peaks are quickly rejected and the deflection or the force comes back to the reference in order to maintain the accuracy.

COMPLETE AUTOMATED PICK-AND-PLACE TASK

The objective of this section is to perform an automated pick-and-place task with the controlled microgripper. The task consists in picking, transporting and positioning a small object from an initial location to another desired location. The pick-and-place operation is carried out with a wire (object) having a diameter of 250 µm. For that, the following procedure is proposed.

• Initially, the wire is located between the two actuators of the microgripper. There is no contact between them and the wire because its diameter is smaller than the gap between the two actuators. Without loss of generality, we assume that the position of the object (wire) is in the center of the microgripper. Thus, the remaining distance between the object and each actuator is approximately 50 µm. If the initial position of the object is not known, a visual detection method (camera-microscope-visual calculation) can for example be employed.

• Then, a deflection reference is applied to one actuator and a force reference is applied to the other actuator of the microgripper. These references allow us to bring both actuators to be in a slight contact with the wire. To avoid any sudden shock at the moment of the contact however, these two reference signals are chosen to be a ramp with a limit value as shown in Fig. 18. The amplitude of the force reference is set to F c = 1 mN in order to obtain a very slight contact with the wire. The reference for the deflection is set to 50µm. This corresponds to the above mentioned distance between the object and the actuator. The actuators of the microgripper are in contact with the wire if the deflection and force reach their specified reference values with the following steady state errors: ε δ = 0.1 µm and ε F = 0.3 mN. These steady state errors were chosen according to the accuracy of the deflection sensor and of the force observer. Fig. 19-a shows the two piezocantilevers approaching towards the wire. • When the approach operation is completed, the grasping (picking) operation is now realized. In the grasping task, a step reference input F c = 5 µm is applied to the actuator controlled in force, while the reference deflection of the other actuator is still left equal to δ c = 50 µm (see Fig. 19-b). • The operation after the grasping of the object is to perform the transport of the object. To this end, the grasping force is maintained constant (F c = 5mN) while the deflection reference is set equal to the desired final position. For instance, we choose in this application the following series of deflection reference: first δ c = 60µm, then δ c = 50µm and finally δ c = 40µm. Fig. 19-c shows a photography of the transport task. • Once the object arrives at its desired location, both the force and deflection references are reset to zero δ c = 0 and F c = 0 (see Fig. 19-d). This allows to open the microgripper and to release the manipulated wire at the final position.

The experimental results that correspond to the pickand-place task are presented in Fig. 20. This figure demonstrates that the pick-and-place task has been successfully performed. The robustness of the computed controllers has also been demonstrated thanks to these experimental results. This robustness consists in maintaining the performances although the uncertainties and the external disturbances. These results are promising for micromanipulation and microassembly applications.

CONCLUSION

This paper presented the modeling, control and automation of a piezoelectric microgripper based on two collab- orative piezoelectric cantilever actuators and devoted to pick-and-place tasks in micromanipulation and microassembly applications. Both the position and force are considered during the modeling and control. It has been shown that interval techniques can be used to model uncertainties characterizing the actuators of the microgripper. The main advantage of interval modeling is the ease and natural way to bound any uncertain parameter. Afterwards, two controllers have been designed for the position and force control by using the performances inclusion theorem. The proposed approach allowed to derive robust and low order controllers. Finally, calculated controllers and the microgripper were used to perform successfully an automated pick-and-place task of small object. The experimental results validated the efficiency of the proposed approach and demonstrated its interest for the control of microgrippers used in automated micromanipulation or microassembly applications.

Fig 1 :

 1 Fig 1: Photography of unimorph piezocantilevers.

Fig 2 :

 2 Fig 2: a: structure of the microgripper using piezocantilevers. b: prototype of the piezoelectric microgripper.

Fig 3 :

 3 Fig 3: a: microgripper modeled by a multivariable system. b: microgripper modeled by two independent monovariable systems.

Fig 4 :

 4 Fig 4: Piezoelectric actuator under electrical excitation.

  399, 1.421] × 10 -4 s + 1 Den δ (s) = [4.88, 6.6] × 10 -8 s 2 +[4.33, 4.91] × 10 -6 s + [0.822, 0.93]

  3968, 1.4232] × 10 -4 s + 1 Den δ (s) = [4.768, 6.772] × 10 -8 s 2 +[4.272, 4.968] × 10 -6 s + [0.8112, 0.9408] (8)

Fig 5 :

 5 Fig 5: Piezoelectric actuator manipulating an object.

Fig 6 :

 6 Fig 6: Manipulated objects: a flexible object (polystyrene) and a rigid (CMS resistance) object.

Fig 7 :

 7 Fig 7: (a): deflection control of the piezoelectric actuator. (b): equivalent block diagram used for the controller synthesis.

Fig 8 :

 8 Fig 8: Solution set of parameters [K p ] × [K i ] of the controller that ensures the specified performances.

Fig 9 :

 9 Fig 9: (a): force control of a piezoelectric actuator. (b): equivalent block diagram used for the synthesis.

Fig 10 :

 10 Fig 10: Setup for the experiments.

Fig. 11

 11 Fig. 11 depicts a diagram for the control of the whole microgripper.

Fig 11 :

 11 Fig 11: Principle of the microgripper control.

Fig 12 :

 12 Fig 12: Regulation of the deflection using the CMS resistance. a: deflection reponse. b: force response.

Fig 13 :

 13 Fig 13: a: zoom on a deflection response. b: zoom on a force response.

Fig 14 :

 14 Fig 14: Regulation of the deflection using the flexible object (polystyrene). a: deflection reponse. b: force response.

  demonstrate this fact. The peaks pictures in Fig.12, Fig.14, Fig.16and Fig.17

  correspond

Fig 15 :

 15 Fig 15: a: zoom on the deflection response. b: zoom on the force response.

Fig 16 :

 16 Fig 16: Regulation of the force using the CMS resistance. a: deflection response. b: force response.

Fig 17 :

 17 Fig 17: Regulation of the force using the polystyrene object. a: deflection response. b: force response.

Fig 18 :

 18 Fig 18: Reference in ramp until a wanted value.

Fig 19 :

 19 Fig 19: a: approach of the actuators. b: grasping the manipulated wire. c: manipulation of the wire. d: release of the wire.

  4.88, 6.6] × 10 -8 s 3

	+ 1 [K i ] [4.33, 4.91] × 10 -6 + [K p ][1.399, 1.421] × 10 -4 s 2
	+	([Kp]+[0.822,0.93])

ACKNOWLEDGMENTS

This work has been supported by the Labex ACTION project (contract "ANR-11-LABX-01-01").


Abdallah Ben Othman

Jean-Marc Nicod

Laurent Philippe

Veronika Rehn Sonigo
email: .sonigo]@femto-st.fr

Veronika Rehn-Sonigo

Abdallah Benothman

Optimal energy

Keywords: Scheduling, workflow applications, energy minimization, fault tolerance, throughput maximization, polynomial complexity

come

Introduction

In this paper we focus on workflow applications described as Directed Acyclic Graphs (DAGs). An application is mapped on a set of distributed machines and a flow of instances has to be processed. This is the case of systems that continuously input raw data to which several processing stages or tasks must be applied to obtain a final result [START_REF] Subhlok | Optimal mapping of sequences of data parallel tasks[END_REF]. Another example are configurable production systems [START_REF] Tanaka | Development of desktop machining microfactory[END_REF][START_REF] Descourvières | Towards automatic control for microfactories[END_REF]. The system is designed as a collaborative platform of distributed machines. Each machine collaborates with others by performing all the instances of at least one task of the DAG. Illustrations of these contexts are a flow of images generated by a camera that must be processed in several stages or a production flow with several succeeding tasks. The considered tasks are of different types that represent the different processing procedures (e.g., filters, analysis, assembly and so on). When the data processing in the application is substantial, several computers or production cells must be used to be able to process the entire input flow and the problem of scheduling the tasks on the resources becomes complex due to the heterogeneity of the processing times on the resources [START_REF] Rehn-Sonigo | Multi-criteria Mapping and Scheduling of Workflow Applications onto Heterogeneous Platforms[END_REF]. The complexity of the problem may be lowered by considering that each machine only executes one task type thus avoiding costly context changes and cases where a machine executes parts of several tasks [START_REF] Diakité | Assessing new approaches to schedule a batch of identical intree-shaped workflows on a heterogeneous platform[END_REF]. Then the initial problem becomes a mapping problem where task types must be mapped onto machines and the objective function is to find the best possible throughput, i.e., to maximize the number of instances processed per time unit [START_REF] Benoit | Mapping workflow applications with types on heterogeneous specialized platforms[END_REF]. Note that the objective function used in this paper is the period minimizationthe time between two consecutive outputs. The period is the inverse of the throughput, which amounts to the same but is more widely used in workflow system optimization.

This paper adresses the problem of using a dedicated system that continuously executes the same DAG of tasks onto different instances with transient failures that sometimes destroy one instance. In this context the objective is to provide the lowest period for the system output. Application flow execution as image processing may be very energy consuming for large images. In the workflow all execution steps however do not have the same execution cost. Lowering the execution speed of the less loaded resources can substantially reduce the global energy consumption. We thus propose two polynomial algorithms based on a greedy approach that either reach the objective of period minimization for a fixed energy consumption or reach the objective of energy minimization for a fixed period. Furthermore we prove the optimality of both the two approaches. For cases where one of the constraints is not compliant with the optimal solution, we propose an adaptation of our algorithms that provides the Pareto front which links the two optimal solutions -the lowest energy consumption with an optimal period and the lowest period with the optimal energy consumption.

The paper is organized as follows: Section 2 discusses related work. In Section 3 we give a formal definition of the problem. In Section 4 we present and prove several lemmas that are used in Section 5 to define the proposed algorithms. Then, in Section 6, we present the result of the algorithm implementation, in the shape of a Pareto front, for cases where the constraints do not allow to reach the optimal solutions. We conclude the article in Section 7.

Related Work

Nowadays more and more attention is payed to energy consumption for financial and environmental reasons. This tendency has also reached the distributed computing domain [START_REF] Costa | The green-net framework: Energy efficiency in large scale distributed systems[END_REF][START_REF] Niemi | Improving energy-efficiency of grid computing clusters[END_REF][START_REF] Benoit | Performance and energy optimization of concurrent pipelined applications[END_REF]. In the case of flow applications where the global throughput is directed by the lower throughput of the graph, it is not always necessary that all machines run at maximum speed [START_REF] Benoit | Energy-aware mappings of series-parallel workflows onto chip multiprocessors[END_REF]. Several papers define an energy model based on power consumption modes where the processing ca-pabilities depend on the supplied voltage [START_REF] Aydin | Energy-aware partitioning for multiprocessor real-time systems[END_REF][START_REF] Chen | Multiprocessor energy-efficient scheduling for real-time tasks with different power characteristics[END_REF]. Then voltage scaling is used to slow down some of the machines -and as a consequence energy sparedwithout affecting the global throughput [START_REF] Benoit | Power-aware replica placement and update strategies in tree networks[END_REF]. It is thus worth to find the lowest possible speed for each machine for a given throughput or, on the opposite, the best reachable throughput for a given energy consumption.

On the other hand in distributed environments such as GRIDs or microfactories, the risk of task failures cannot be ignored, in particular for long running and communication intensive applications like flow applications. The failures may append for numerous reasons such as network or computing errors, network contention, task complexity and so on. Numerous works on reliability and energy focus on the problem of Dynamic Voltage and Frequency Scaling (DVFS) which leads to more errors when the frequency is scaled down [START_REF] Degalahal | Soft errors issues in low-power caches[END_REF]. This assumption however only lays on the assumption that with low voltage the processor becomes more likely to be pone to errors. Defining a global error model for an entire distributed system however is not so simple as these systems are composed of so many elements, each with their own failure model. For instance, [START_REF] Zhang | Optimal speed scaling algorithms under speed change constraints[END_REF] uses a model where the reliability of the processor is directly related to the number and span of speed changes. Increasing the speed of computations or/and the processing load can also lead to less reliable systems as it is shown on real HPC in-production systems [START_REF] Schroeder | A large-scale study of failures in high-performance computing systems, Dependable and Secure Computing[END_REF], or to DRAM errors [START_REF] Schroeder | Dram errors in the wild: a large-scale field study[END_REF]. [START_REF] Nightingale | Cycles, cells and platters: an empirical analysisof hardware failures on a million consumer pcs[END_REF], analyzing a large database of failure in PC systems, suggests that "one can minimize the likelihood of failure over a given time period by operating at the slowest CPU speed sufficient to achieve desired performance". Based on this observation, we assume in this paper that optimizing the energy consumption of the system by decreasing its speed leads to decrease the fault rate in addition to period minimization. In this context we propose two algorithms that minimize either the energy consumption for an optimal period or find the lowest period for a minimal energy consumption. Note that the antagonism between reliability and machine speed induces the complexity of the problem and, in particular, the properties set in section 4.

Framework

In this section we formally define the application, platform and energy models and our optimization objective.

Application Model

We consider a workflow application that is running during infinite or long time. The application is modeled as a directed acyclic graph (DAG) G(T, D), with T = {T 1 , . . . , T n } the tasks of the application and D ⊂ T × T the dependencies between the tasks (see Figure 1). Data sets enter the graph at the source task and traverse the graph from one task to another before producing a final result at the sink task. A weight w i is associated to each task T i that corresponds to the amount of work to be done to perform the task.

Platform and Execution Model

The platform is modeled as a set M = {M 1 , . . . , M p } of p machines fully interconnected. Each machine has input and output communication buffers to store temporary data. We assume that the communication times are shorter than the computation times so that, thanks to the data buffering, the former are covered by computations and thus can be neglected.

The tasks are statically allocated to machines according to an allocation function a such that a(i) = u, i.e., all data instances that enter task T i are performed by machine M u . Note that in this work we assume that the mapping is already defined thanks to mapping algorithms as defined in [START_REF] Benoit | Mapping workflow applications with types on heterogeneous specialized platforms[END_REF] and we concentrate on period and energy optimization of a given mapping.

A machine M u runs at different speed levels l u (l u ∈ {0, 1, 2, . . . , max(l u )}) with an associated slow down factor α lu u ∈ [1, +∞). Note that M u runs at its highest speed, noted s u , for level l u = 0. The system configuration L is given by vector L = (l 1 , l 2 , . . . , l u , . . . , l p ) that describes the speed level of each machine.

Tasks are subject to transient failures. In case of failure, the current data is lost and the task starts to process the next data. The failure rate is defined for each task as the percentage of failures. For a task T i , allocated to machine M u , we assume that the failure rate f lu i depends on the task and on the machine speed level l u . We also assume that the failure rate increases with the machine speed:

f lu i < f l u
i with l u > l u . It comes that if machine M u performs x lu i input data sets with task T i , it outputs (1-f lu i )x lu i data sets due to failures. Considering L, the configuration of the platform, it is possible to compute x lu i backwards for each data output of the application. If task T i has only one outgoing edge (T i , T j ) within the DAG, x lu i =

x lu j 1-f lu i (see Figure 2 for an example). If the task T i has several outgoing edges (T i , T j ) within the DAG, x lu i = (Ti,Tj )∈D

x lu j 1-f lu i .
Thus x lu i is the average number of data sets that machine M u has to perform with task T i so as to output at least one result data set out of the system.

Example of the Platform and Execution Model

To clarify the above stated platform and execution model, we consider the application given in Figure 2. To keep the example simple, we suppose that task T i is mapped onto machine M u with i = u and that each machine runs at is lowest speed level. Hence task T 1 is mapped onto machine M 1 which is running at a level l 1 . The failure rate of task T 1 accordingly depends on l 1 and we have f l1 1 = 1/6. The same holds for the other tasks. Figure 3: The acceleration of machine M 2 implies a higher number of input data sets at the application entry.

We suppose to have the failure rates indicated in Figure 2. We can now compute the necessary amount of data sets that each task needs as input to be able to produce at least one result out of the system (x out = 1). As indicated earlier, the computation is done backwards and we get

x l4 4 = 1 1-f l 4 4
x out = 1.5.

We now suppose that machine M 2 has two possible speed levels l 2 and l 2 , where l 2 is the accelerated level (l 2 < l 2 ). The associated failure rate for level l 2 is f l 2 2 = 2/5. If machine M 2 switches to level l 2 , the x lu i values have to be recomputed in consequence and you can see the new configuration in Figure 3.

Throughput/Period Model

We define the platform throughput as the number of data outputs per time unit. We define the period of the platform as the inverse of the throughput: the period defines the maximum duration between the output of two consecutive data outputs. As we already know both the number of tasks that have to be performed to output at least one data set and the mapping of tasks to machines, we can compute the period of each machine of the platform. The task period p lu i is the time to perform x lu i instances of each task T i mapped onto machine M u :

p lu i = x lu i × wi×α lu u su
. Then the machine period p lu u on M u is:

p lu u = Ti|a(i)=u p lu i = Ti|a(i)=u x lu i × w i × α lu u s u
The application period on the platform is the longest period over all machines in configuration L:

P (L) = max Mu∈M (p lu u )
We define the critical machine M c as the machine with the longest period that determines the application period, i.e., P (L) = p lc c . We denote M c (L) one critical machine of the configuration L.

Energy Model

The energy consumption E(L) of the platform in configuration L is the sum of the energy consumption E L (u) of each machine M u that performs at least one task of the graph. The energy

E L (u) = E L stat (u) + E L dyn (u) is the sum of E L stat (u)
, the static part of energy consumed when machine M u is in service, and E L dyn (u), the dynamic part of energy consumed when the machine performs its tasks [START_REF] Benoit | Performance and energy optimization of concurrent pipelined applications[END_REF].

E L stat (u) only depends on the duration of the platform usage. The static energy needed to output one data out of the system is thus E L stat (u) = ε u ×P (L) where ε u is the static energy consumption per time unit, P (L) is the period of the application (or the duration between two consecutive outputs) and L is the configuration of the system.

On the other hand, the dynamic part of the energy depends on the machine speed when it performs tasks. Several models are defined in the literature for the dynamic energy consumption of a machine. It is usually represented by a polynomial of at least second degree as in [START_REF] Ishihara | Voltage scheduling problem for dynamically variable voltage processors[END_REF][START_REF] Bansal | Speed scaling to manage energy and temperature[END_REF] or a more general strictly convex and increasing function g of the machine speed as in [START_REF] Aydin | Energy-aware partitioning for multiprocessor real-time systems[END_REF] and [START_REF] Zhang | Optimal speed scaling algorithms under speed change constraints[END_REF]. As in [START_REF] Bansal | Speed scaling to manage energy and temperature[END_REF] we assume here that the energy consumed on machine M u at speed s depends on C en × s βu where β u > 1 and C en > 0. As the speed of machine M u is su α lu u the dynamic energy consumed during one period by machine M u is the sum of the energy consumed to perform all the tasks needed for that period is given by equation 1.

E L dyn (u) = Ti|u=a(i) C en × s u α lu u βu × p lu i (1)

Optimization Objectives

In this paper, we are interested in two objectives. First, we aim at minimizing the period and minimizing the energy consumption for the optimal period. Second, we optimize the energy consumption of our platform while minimizing the period for the optimal energy consumption.

System Properties

In this section we state some important properties for the changing of the system configuration L and we first exhibit the relation between two system configurations L and L . The period of a machine M u in system configuration L can be expressed through the task periods in system configuration L. Based on the platform model, we know that a machine period is the sum of all its task periods, and we can deduce the following relation:

p l u u = Ti|a(i)=u x l u i × w i α l u u s u = Ti|a(i)=u x l u i α l u u x lu i α lu u × p lu i (2)
We now consider the influence of slowing down or accelerating machines.

Lemma 1. When a group of machines is accelerated, the amount of work to output one data set increases.

Proof. Let L and L be two system configurations with l u l u for each machine M u ∈ M , i.e., L has some accelerated machines in comparison to configuration L. We aim at proving that ∀T i ∈ T, x lu i x l u i with a(i) = u. That means the amount of input data sets for task T i is more important in configuration L .

Let M u ∈ M be an accelerated machine whose configuration is set to l u . As l u < l u , by definition of our model,

f lu i < f l u i for all tasks T i ∈ T with a(i) = u and so 1 1 -f lu i < 1 1 -f l u i
. From the definition of the computation of

x lu i , the previous expression implies that the value of x l u i increases on M u . Moreover since these values are computed backwards (Cf. Figure 2 in Section 3.3), this incrementation recursively modifies the x lv j by backwards following the dependency constraints in the group of machines. The global workload of each machine M v , where a(j) = v, thus increases.

Lemma 2. When a group of machines is accelerated, it cannot decrease the period of the other machines.

Proof. Let L and L be two system configurations with l v l v , ∀M v ∈ M , i.e., L has some accelerated machines compared to L. Let M u be a machine with l u = l u . We aim at proving that p lu u p l u u . First, with Lemma 1, we know that for all tasks the amount of work is more important in L than in L: x lu i x l u i , ∀t i ∈ T . Next, we know that if l u = l u , the acceleration coefficient α is also the same:

α lu u = α l u
u . Hence we have:

∀t i ∈ T s.t. u = a(i) : α lu u x lu i α l u u x l u i
and we get:

∀t i ∈ T s.t. u = a(i) : p lu i α l u u x lu i α lu u x lu i × p lu i
This holds true for all task periods and we can deduce the machine period by summing up over all task periods of a machine M u and with Eq. 2, we prove that the machine period of M u is smaller in configuration L than in L :

p lu u = Ti∈T |a(i)=u p lu i Ti∈T |a(i)=u α l u u x l u i α lu u x lu i × p lu i = p l u u
Corollary 1. The acceleration of another machine than the critical machine cannot decrease the application period.

Proof. Let L and L be two system configurations with l v l v , ∀M v ∈ M , i.e., L has some accelerated machines. Let M c be the critical machine such that p lc c = P (L) and l c = l c . With Lemma 2, we know that the machine period of machine M c is lower (or equal) in L than in L :

p lc c p l c c
. By definition, we deduce that the period of configuration L is lower than the maximum period in L :

P (L) p l c c = max Mu∈M (p l u u ) = P (L )
Lemma 3. The acceleration of a machine cannot decrease the dynamic energy of any machine.

Proof. Let L and L be two system configurations with l u l u , ∀M u ∈ M , i.e., L has some accelerated machines. We aim at proving that for all machines the dynamic energy is smaller in L than in L :

∀M u ∈ M, E L dyn (u) E L dyn (u)
. By definition we have 1 α l u u α lu u and β u > 1 so ∀T i ∈ T we can write:

1 (α lu u ) βu-1 1 (α l u
u ) βu-1 By using the three positive constants C en , w i and s u and by using Lemma 1, 0 < x lu i x l u i , ∀T i ∈ T with a(i) = u, we obtain:

C en s u α lu u βu x lu i w i α lu u s u C en s u α l u u βu x l u i w i α l u u s u C en s u α lu u βu p lu i C en s u α l u u βu p l u i Ti|a(i)=u C en s u α lu u βu p lu i Ti|a(i)=u C en s u α l u u βu p l u i
With Equation 1we have E L dyn (u) E L dyn (u). Lemma 4. If the application period does not decrease, machine acceleration always increases the energy consumption of the application.

Proof. Let L and L be two system configurations with l v l v , ∀M v ∈ M , i.e., L has some accelerated machines. Let M u be a machine with l u < l u . Thus P (L) P (L ) and the following inequality on the static energy of the two system configurations holds: ∀M u ∈ M : ε u ×P (L) ε u ×P (L ). Moreover with Lemma 3 we know that for all machines the sum of the task energy consumption is smaller in L than in L :

∀M u ∈ M : E L dyn (u) E L dyn (u)
Thus we deduce that the total energy consumption of a machine M u behaves the same way as both the static and the dynamic part hold the inequality:

∀M u ∈ M : ε u × P (L) + E L dyn (u) ε u × P (L ) + E L dyn (u) E L (u) E L (u)
Hence we conclude that E(L) E(L ).

Algorithms

In this section, we present two algorithms. The first algorithm OptP er(L) finds a system configuration with the optimal period and the minimal energyconsumption for this period. The second one, OptEner(L), finds a system configuration with the optimal energy-consumption and the minimal period for this consumption.

Algorithm OptPer

The algorithm OptP er(L) (see Algorithm 1) returns the optimal system configuration resulting from a given system configuration, i.e., the system configuration with the optimal period and the minimal energy consumption for the optimal period. The algorithm starts from an initial configuration L where each machine is set at its maximal slow down level. Then, at each step, the algorithm speeds up the machine M c (L) by reducing its level l c by one. The new configuration is noted L. If the new system configuration period P ( L) is better than the current best period, it is stored in L as the new best system configuration. Then a new critical machine M c ( L) is identified and the algorithm passes to the next step.

Otherwise or if the slow level of M c ( L) is null ( l c = 0) the algorithm finishes. The number of steps needed to finish this algorithm takes polynomial time. Indeed, in the worst case, the algorithm iterates p × LM AX times, with LM AX = max u (max(l u )) a constant which does not depend on the problem size. At each step, the computation of the necessary amount of the data sets for all of the tasks takes O(n) operations and the complexity of algorithm 1 is

O(p × n).
Algorithm 1: OptP er(L) To prove the optimality of the period returned by this algorithm we first set Lemma 5 and its corollary 2. For that we first define A(L) as the set of system configurations resulting from all possible machine accelerations from the system configuration L. Let L and L be two system configurations.

Mc ← critical machine of L 1 L ← L 2 lc ← lc -1 3 Mc ← critical machine of L

∀L, L :

L ∈ A(L) ⇔ ∀u : l u l u (3)
For example, if L = (2, 1):

A(L) = {(2, 1)
, (1, 1), (0, 1), (2, 0), (1, 0), (0, 0)}

We recall that M c (L) is one of the critical machines of the configuration L, i.e., one of the slowest machines of the configuration L. Lemma 5. Let us consider a configuration L and a subset of system configurations L in A(L) where l c = l c with M c a critical machine of the configuration L. Then the period P (L) is smaller than any period P (L ):

∀L ∈ A(L) | l c = l c ⇒ P (L) P (L ) (4)
Proof. From the definition of function A(L) in equation 3 we know that:

∀L ∈ A(L) ⇒ l u l u
And from Corollary 1 we know that if the critical machine is not accelerated, the period cannot decrease. By association we get that for all system configurations L in A(L) with l c = l c the period of configuration L is higher or equal than the period of the configuration L.

As a consequence of Lemma 5, only the configurations in A(L) that the speed level of a critical machine M c ( L) can provide a better period for the system. We formalize this property in the following corollary:

Corollary 2. The only configuration that is able to decrease the period of the system from a configuration L is to accelerate a critical machine.

Note that speeding up the critical machine by one level does not always lead to a better period for two reasons. First because speeding up a critical machine does not always lead to improve its own period. This acceleration is however an imposed condition to improve the application period in some cases. Second because there may be several critical machines at the same time, i.e., machines that have the same period, and we must speed up all of them before improving the application period.

Theorem 1. OptP er(L) finds the optimal system configuration L * with the optimal period in A(L), i.e.:

L * = OptP er(L), ∀L ∈ A(L) ⇒ P (L * ) P (L ).

Proof. First we note that, based on the definition of the system period P (L) given in Section 3, the order in which the machines are accelerated to reach a configuration L from a configuration L does not impact P (L ). The period P (L ) only depends on the configuration L , so on the (l 1 , l 2 , . . . , l p ) values. Now we consider a sequence of configurations S = L 1 , L 2 , . . . , L k with k = |A(L)| such that L 1 = L is the initial configuration of the algorithm where all the machines are set to their lowest speed level and L 2 , . . . , L k ∈ A(L 1 ). The optimal configuration L * can be defined as:

L * = argmin L f ∈S (P (L f ))
Let L a and L b two system configurations such that the configuration L a is obtained by speeding up one machine from the configuration L b . From Lemma 5 we know that having P (L a ) < P (L b ) implies that the critical machine M c (L b ) has necessarily been speeded up to obtain L a .

As the order in which each machine is accelerated to reach a given configuration L f from the initial configuration L does not impact the period value P (L f ), we can reorder the sequence S in a new sequence S . S is reorganized such that L 1 = L is the first configuration of the sequence and then each configuration L x is obtained from configuration L x-1 by accelerating one of its critical machines M c (L x-1 ) is placed just after L x . All other configurations are placed after. This reordering of the sequence does not change the optimal value L * . ∀u : l u l * u . By using Lemma 3 we deduce that the energy consumed by each configuration L with P (L * ) = P (L ) is at least as high as the consumption E * = E(L * ) E(L ) and then that E(OptP er(L)) = E(L * ) is optimal.

Algorithm OptEner

From the previous algorithm, it is possible to define another greedy algorithm, OptEner(L) Algorithm 2), based on the same approach that finds a configuration L * with an optimal (lowest) energy consumption and with a minimal period for this energy consumption. Note that the energy consumption, as defined in the framework model, is composed of a static part and a dynamic part. In some cases where the period is too large, the speed of the machines is thus so low that the static part of the energy consumption becomes predominant. It is then possible to increase the speed of the machine while decreasing the energy consumption. On the other hand, if we increase too much the speed of the machines, above the optimal value, the energy starts increasing. Then the OptEner(L) algorithm finds a system configuration whose energy consumption is optimal. As the speed of the machines is increased accordingly, OptEner(L) is also a configuration with the minimal associated period. Note that this algorithm also works to compute the minimal energy consumption for a given period. We assume that the complexity of Algorithm 2 is O(p × n) considering the same arguments used to compute the complexity of Algorithm 1.

Algorithm 2: OptEner(L)

Mc ← critical machine 1 L ← L 2 lc ← lc -1 3 Mc ← critical machine 4 while ( lc > 0) do 5 if E( L) < E(L) ∨ 6 (E( L) = E(L)) ∧ (P ( L) P (L)) then 7 L ← L 8 Mc ← Mc 9 lc ← lc -1 10 Mc ← critical machine of L 11 return L 12
The algorithm starts from L, the initial configuration where each machine is set at its lowest speed level. Step by step, the algorithm looks for configurations where the energy is decreased compared to the current configuration or if the energy is not decreased at least the period is. The algorithm iterates until the critical machine cannot be accelerated anymore, i.e., when the critical machine has reached its highest speed level.

To prove the optimality of the algorithm we prove first that OptEner(L) finds the system configuration with the optimal energy consumption and then we prove that OptEner(L) finds the minimal period. Before these proofs, we set Lemma 6: Lemma 6. Let L be a configuration in A(L) and M c be a critical machine of configuration L such that the slowdown level for M c is the same in L as in L , then the energy consumption of L is lower than the energy consumption of L :

∀L ∈ A(L) : l c = l c ⇒ E(L) E(L )
Proof. We know, from the definition of function A(L), that each slowdown level l u of a machine M u in L is higher or equal than in L with L ∈ A(L). And, considering Corollary 1, we know that the application period with the system configuration L is lower or equal than any other system configuration L in A(L) where l c = l c (M c = M c (L)). Thus, by association, we show:

∀L ∈ A(L) : M c = M c (L) and l c = l c ⇒ P (L) P (L )
Moreover, from Lemma 4, if the slowest machine is not accelerated then the energy consumption of the system cannot decrease:

∀L, L : (∀u s.t. 1 u p, l u l u ∧ P (L) P (L )) ⇒ E(L) E(L )
Thus we find that the energy consumption in L is lower than in every system configuration L in A(L) when l c = l c .

Theorem 3. OptEner(L) finds the system configuration L * with the optimal energy consumption E * = E(L * ) in A(L):

L * = OptEner(L), ∀L ∈ A(L) ⇒ E(L * ) E(L )
Proof. Let L be a system configuration and let M c be a critical machine of configuration L. By using Lemma 6 we assess that the only way to lower the energy consumption is to accelerate the critical machine. The remainder of the proof is very similar to the proof of the OptP er(L) optimality. First we state that the order in which the machines are accelerated to reach a configuration L from a configuration L does not impact the energy value. Indeed the energy consumed by a machine M u only depends on energy constants (C en and β u ), on its speed level (α lu u ) and its period (p lu i ). Then we consider the sequence of configurations S = L 1 , L 2 , . . . , L k such that k = |A(L)| and L = L 1 is the initial configuration where each machine configuration is set at its maximal slowdown level. We can thus assume that L 2 , . . . , L k ∈ A(L 1 ). We sort these configurations in a new sequence S where critical machines are accelerated first. S is reorganized as mentioned before, i.e., L 1 = L is the first configuration of the sequence and then each configuration L x is obtained from configuration L x-1 by accelerating one of its critical machines. All other configurations are placed after. L 1 , . . . , L a is the sequence obtained by OptEner(L) step by step. As L a is the last configuration where a critical machine can be accelerated, we have l c = 0 in L a . Obviously all configurations that are ordered after L a are configurations where the critical machines have not been accelerated and these machines cannot have a better period. From Lemma 4 we deduce that these configurations are more energy consuming than configuration L a : ∀f, a < f k :

E(L a ) E(L f )
We recall that the configuration sequence L 1 , . . . , L a is explored by the OptEner algorithm. Thanks to the condition on line 6 the algorithm only records the best of the covered configurations and thus finds the configuration with the lowest optimal energy consumption.

Theorem 4. OptEner finds the system configuration with the minimal period for the optimal energy consumption.

Proof. We have already shown, in the proof of Theorem 1, that the order in which we consider the machine accelerations does not impact the period value of a given configuration. We also know, from Lemma 3, that a machine acceleration can only decrease the energy consumption of the application if its period is lowered. Let E * be the optimal energy consumption.

As for Theorem 2, we consider the sequence S where the configurations that accelerate critical machines come first in the same order as explored by the algorithm (until l c = 0). The other configurations are placed at the end of the sequence. The shape of the sequence is:

S = L 1 , . . . , L * , . . . , L a , . . . , L k
From the previous proof (Theorem 3) we know that the optimal energy consumption is reached in this sequence at first for L * and that configurations after L a do not have an optimal energy consumption. Then we just have to consider the cases between L * and L a . These cases are examined by the algorithm OptEner step by step. The algorithm does not finish when it finds the optimal energy consumption with L * but continues until it reaches the maximum speed level for a critical machine for the first time. This case occurs with L a . Thanks to the condition on line 6 of Algorithm 2 we guarantee that, in this interval, if a period improvement is possible then it returns this best configuration.

Sub-optimal cases tied by constraints

In some cases the period or the energy may be constrained by external factors, as a limited output throughput or as limited available energy in embedded systems for example. In these cases, the optimal values computed by our algorithms are not reachable and a multi-criteria computation must be done to find either the best corresponding energy or period values. In this case the proposed algorithms can be easily adapted by introducing a new condition in the "if condition" of the algorithms. This condition allows to change the L configuration only if the new configuration L does not violate the constraint. It is then interesting to explore different constraints to get the pareto front that gives the best solutions for each configuration between the two optimal solutions.

For illustration we have computed the pareto front for a specific configuration given in Table 1. The platform configuration (see Table 1a) is composed of five machines M u (1 u 5) with the same initial speed s u (in computing units per second) and 10 speed levels l u so that the slowdown factor α lu u ranges between 1 and 2. The value of β u is either set to 2 or 3. The considered application has five tasks. The associated weight w i (in computing units) and failure rate f lu i are given in Table 1b. The failure rate ranges between 0.01% and 10% and depends on l u . In Figure 4 we plot the period obtained under energy constraints. About forty values of energy are taken between the optimal energy value (2881.26 W h) and the energy corresponding to the lowest -optimal -period (3417.62 W h). Note that the computed results are so close that they shape thick lines. Each line corresponds to the optimal configuration for the critical machine considering a range of energy values. The solid line gives the Pareto front obtained for this platform and this application. The Pareto front contains only 11 solutions. Each of them corresponds to a configuration given by our algorithm to guarantee the lowest period for a given energy level that has not to be exceeded to perform one output out of the system (see Table 2). Note that two Pareto solutions -(32.4637, 3304.99) and (32.4642, 3235.26) -are very close but the corresponding lines do not overlap as Figure 4 gives the impression. Figure 5 gives the details of this area.

Conclusion

In this paper we tackle the problem of energy saving in the case of DAG shaped workflow applications executed on distributed unreliable platforms. We assume that the energy consumption and the fault rate decreases when the machines are slowed down. Given an initial mapping of the tasks onto the machines 4 we propose two algorithms and prove their optimality. The first algorithm minimizes the application period and finds the lowest global energy consumption for that period. The second algorithm optimizes the energy consumption of the system and finds the lowest period for that energy consumption.

In practical systems the energy consumption and the execution period are however often opposed criteria and reducing one of them usually leads to increase the other one. For this reason there is a need to find configurations that balance these criteria. For that we have modified the algorithms and introduced constraints values for both the energy and the period.

In the current work the failure rate of the tasks is a consequence of the speed of the machines. As lowering the task period leads to more faults there is a need to improve the reliability of the system. Improving the system quality implies to find a trade-off between energy, speed and faults. As future work we will consider the problem of optimizing the three criteria of energy, failures and throughput to identify the best configurations of the system given different objectives of improving the reliability, maximizing the speed and lowering the energy consumption. We plan to use multi-criteria techniques and explore different fault models to find good configurations. Due to the complexity of the tri-criteria problem we plan to develop heuristics that give efficient results for each of the three objectives in practical cases.

Figure 1 :

 1 Figure 1: Illustrating task graph

Figure 2 :

 2 Figure 2: Example for the backward computation of the necessary amount of data sets for each task in a linear application, taking into account the failure rates.

4 while ( lc > 0) do 5 if 6 L ← L 7 Mc ← Mc 8 lc ← lc - 1 9Mc ← critical machine of L 10 return L 11

 4567811011 P ( L) < P (L) then

Figure 4 :

 4 Figure 4: Example of a Pareto front for sub-optimal platform configurations

Table 1 :

 1 Illustrated configuration parameters

	Machine Mu su	lu	α lu u	βu	Task Ti wi	fi
		0	3	[1,9] [1,2]	3		0	69 [0.13%,9.24%]
		1	3	[1,9] [1,2]	2		1	31	[0.4%,9.26%]
		2	3	[1,9] [1,2]	3		2	19 [0.51%,7.23%]
		3	3	[1,9] [1,2]	3		3	80 [0.29%,8.91%]
		4	3	[1,9] [1,2]	2		4	54 [0.54%,9.85%]
		(a) Platform configuration		(b) Application
		3500
								pareto front
						period under energy constraint
		3400
	energy consumption in Wh	3000 3100 3200 3300
		2900
		2800
		30	32	34		36	38	40	42	44
					period in seconds

Table 2 :

 2 Figure 5: Zoom in the Pareto front for periods in the interval of 32.463 s and 32.465 s period (s) 31.6122 32.4637 32.4642 32.9058 34.1930 35.9612 energy (Wh) 3417.62 3304.99 3235.26 3101.17 3058.26 3020.72 period (s) 36.5210 38.7897 41.2347 43.3722 43.6949 energy (Wh) 2950.99 2908.08 2902.72 2897.35 2881.26 List of the 11 points belonging to the Pareto front presented in Figure

		3450
					pareto front
				period under energy constraint
	energy consumption in Wh	3250 3300 3350 3400
		3200
		32.463	32.4635	32.464	32.4645	32.465
				period in seconds

Let L a be the last configuration of the sequence S that is obtained by accelerating a critical machine. Then:

Indeed only non critical machines are accelerated after step a and from Lemma 2 we know that this will not decrease the system period.

Here L 1 , . . . , L a is the sequence obtained by OptP step by step. Thanks to the condition on line 6 in Algorithm 1, OptP er(L) takes the best configuration from this sequence. As a consequence:

Then, from Equations 5 and 6, we deduce:

Additionally to the optimal period algorithm OptP er(L) also finds the configuration that is the less energy consuming.

Theorem 2. OptP er(L) finds the system configuration with the minimal energyconsumption E * for the optimal period.

Proof. First we can remark that the static energy consumption of the machines only depends on the system configuration period P (L) and thus is the same as long as the system keeps the same period. This is in particular true for the optimal period L * so that the proof can be limited to the study of the optimality of dynamic energy consumption.

Then, as for the period computation, we can note that the energy consumption definition does not depend on the order in which the configurations are used to reach a target configuration. We can arrange the configuration sequence in any order.

We consider again the sequence S of configurations where the configurations are ordered in such a way that we accelerate critical machines first until L * and then we put the other configurations after. As defined within the proof of the previous theorem, let L a be the last configuration of the sequence S that is obtained by accelerating a critical machine. We have S = L 1 , . . . , L a , . . . , L k with k = |A(L)| and L = L 1 the initial configuration where each machine configuration is set at its maximal slowdown level. Now each configuration in the sub-sequence L a+1 , . . . , L k is a sub-optimal configuration so it is not considered in the following as we are only concerned by configurations which are potentially optimal. In L 1 , . . . , L * we also have sub-optimal configurations that are not considered either. As a result we just have to look at configurations L in L * , . . . , L a whose period is minimal (P (L * ) = P (L )).

By definition L * is the first configuration that reaches an optimal period in S so that an other configuration L in S with an optimal period is such that