Ismail Assayad

Alain Girault

Hamoudi Kalla

Tradeoff exploration between reliability, power consumption, and execution time for embedded systems The TSH tricriteria scheduling heuristic

Keywords: Embedded systems, multicriteria optimization, reliability, power consumption, DVFS, multiprocessor scheduling, Pareto front

For autonomous critical real-time embedded systems (e.g., satellite), guaranteeing a very high level of reliability is as important as keeping the power consumption as low as possible. We propose an off-line scheduling heuristic which, from a given software application graph and a given multiprocessor architecture (homogeneous and fully connected), produces a static multiprocessor schedule that optimizes three criteria: its length (crucial for real-time systems), its reliability (crucial for dependable systems), and its power consumption (crucial for autonomous systems). Our tricriteria scheduling heuristic, called TSH, uses the active replication of the operations and the data-dependencies to increase the reliability, and uses dynamic voltage and frequency scaling to lower the power consumption. We demonstrate the soundness of TSH. We also provide extensive simulation results to show how TSH behaves in practice: Firstly, we run TSH on a single instance to provide the whole Pareto front in 3D; Secondly, we compare TSH versus the ECS heuristic (Energy-Conscious Scheduling) from the literature; And thirdly, we compare TSH versus an optimal Mixed Linear Integer Program.

Introduction

Motivations

Autonomous critical real-time embedded applications are commonly found in embedded devices such as satellite systems. Because they are real-time systems, their execution time must be as low as possible to guarantee that the system interacts with its environment in a timely way. Because they are critical, their reliability must be as close as 1 as possible, typically above 1 -10 -9 . And because they are autonomous, their power consumption must be as low as possible. The main problem when addressing these issues is that they are antagonistic. Intuitively, lowering the probability of failure requires some form of redundancy, meaning more computing load. This is antagonistic to achieving the lowest possible execution time. In the same manner, lowering the power consumption is usually achieved by lowering the voltage and frequency operating point of the processors, which means that the same software function will take more time to execute. Finally, lowering the voltage and frequency operating point also has an impact of the failure rate of processors, because lower voltage leads to smaller critical energy, hence the system becomes sensitive to lower energy particles. As a result, the failure probability increases. These three antogonisms make the problem very challenging.

In order to offer the best compromises between these three measures, we present an off-line scheduling heuristic that, from a given software application graph and a given multiprocessor architecture, produces a static multiprocessor schedule that optimizes three criteria: its schedule length (crucial for real-time systems), its reliability (crucial for dependable systems), and its power consumption (crucial for autonomous systems). We target homogeneous distributed architecture, such as multicore processors. Our tricriteria scheduling heuristic uses the active replication of the operations and the data-dependencies to increase the reliability, and uses dynamic voltage and frequency scaling (DVFS) to lower the power consumption.

Multicriteria optimization

Let us address the issues raised by multicriteria optimization. Figure 1 illustrates the particular case of two criteria, Z 1 and Z 2 , that must be minimized. For the clarity of the presentation, we stick here to two criteria but this discussion extends naturally to any number of criteria. In Figure 1, each point x 1 to x 7 represents a solution, that is, a different tradeoff between the two criteria. The points x 1 , x 2 , x 3 , x 4 , and x 5 are called Pareto optima [START_REF] Billaut | Multicriteria Scheduling: Theory, Models and Algorithms[END_REF]. Among those solutions, the points x 2 , x 3 , and x 4 are called strong Pareto optima (no other point is strictly better on all criteria) while the points x 1 and x 5 are called weak Pareto optima (no other point is better on all criteria, possibly not strictly). The set of all Pareto optima is called the Pareto front.

First criterion Z 1 x 4

x 6

x 7 Z 1 (x 6 )

x 5 Second criterion Z 2 x 3

x 1 x 2 Z 2 (x 6 ) Fig. 1 Pareto front for a bicriteria minimization problem.

It is fundamental to understand that no solution among the points x 2 , x 3 , and x 4 (the strong Pareto optima) can be said to be the best one. Indeed, those three solutions are non-comparable, so choosing among them can only be done by the user, depending on the precise requirements of his/her application. But such a user-dependent choice can only be made if we are able to compute the whole Pareto front. If we compute only a single solution, then obviously no choice is possible. This is why we advocate producing, for a given problem instance, the whole Pareto front rather than a single solution. Since we have three criteria, it will be a surface in the 3D space (execution time,reliability,power consumption). Now, several approaches exist to tackle bicriteria optimization problems (these methods extend naturally to multicriteria) [START_REF] Billaut | Multicriteria Scheduling: Theory, Models and Algorithms[END_REF]:

1. Aggregation of the two criteria into a single one, so as to transform the problem into a classical single criterion optimization one. 2. Hierarchization of the criteria, which allows the total ordering of the criteria, and then the solving of the problem by optimizing one criterion at a time. 3. Interaction with the user, in order to guide the search for a Pareto optimum. [START_REF] Benoit | Reliability and performance optimization of pipelined real-time systems[END_REF]. Transformation of one criterion into a constraint, which allows the solving of the problem by optimizing the other criterion under the constraint of the first one.

Any multicriteria optimization method that aggregates the criteria (for instance with a linear combination of all the criteria) can only produce one point of the Pareto front, leaving no choice to the user between several tradeoffs. Of course, such a method could be run several times (for instance by changing the coefficients of the linear combination), but there is no way to control what part of the Pareto front will be produced by doing so and the Pareto front is likely to be far from complete.

Similarly, any multicriteria optimization method that hierarchizes the criteria can only produce one point of the Pareto front. For instance, in the case of Figure 1, we could first minimize Z 1 and obtain the subset {x 4 , x 5 } of solutions, and then minimize Z 2 among the solutions in {x 4 , x 5 }, thereby obtaining the point x 4 . Alternatively, we could first minimize Z 2 and then Z 1 , thereby obtaining the point x 2 . In both cases, only one point of the Pareto front is obtained.

Finally, we do not want to consider the third class of methods (interaction with the user) because it too would produce a single point of the Pareto front, and also because we want to provide a stand alone multicriteria optimization method.

Contrary to the three first classes of methods, the transformation approach allows one to produce the whole Pareto front, for instance by choosing to take the Z 1 criterion as a constraint, by fixing its maximum value, by minimizing Z 2 under the constraint that Z 1 remains below this value, and by iterating this process with different maximum values of Z 1 so as to produce each time a new point of the Pareto front. This is why the proposed method follows this approach.

Contributions and outline

The main contribution of this paper is TSH, the first tricriteria scheduling heuristic able to produce, starting from an application algorithm graph and an architecture graph, a Pareto front in the space (schedule length,reliability,power consumption), and taking into account the impact of voltage on the failure probability. Thanks to the use of active replication, TSH is able to provide any required level of reliability. TSH is an extension of our previous bicriteria (schedule length,reliability) heuristic called BSH [START_REF] Girault | A novel bicriteria scheduling heuristics providing a guaranteed global system failure rate[END_REF]. The tricriteria extension presented in this paper is necessary because of the crucial impact of the voltage on the failure probability.

We first present in Section 2 an overview of TSH. Then, in Section 3 we introduce the models that we used, regarding the target architecture, the software application that must be scheduled on it, the execution characteristics of the software elements onto the processing elements, the failure hypothesis, and the power consumption. TSH itself is presented in details in Section 4. In particular, we prove the soundness of TSH by demonstrating that the produced schedules always meet the desired constraint on the reliability and on the power consumption. Then, in Section 5, we define a mixed integer linear programming model (MILP) for our scheduling problem, in order to compute the optimal Pareto front. Section 6 presents our simulation results, including the comparison with the Energy-Conscious Scheduling heuristic (ECS [START_REF] Lee | Minimizing energy consumption for precedence-constrained applications using dynamic voltage scaling[END_REF]), and with the optimal Pareto front in the case of small problem instances. Finally, we review the related work in Section 7 and we provide concluding remarks in Section 8.

Principle of the method and overview

The approach we have chosen to produce the whole Pareto front involves (i) transforming all the criteria except one into as many constraints, then (ii) minimizing the last remaining criterion under those constraints, and (iii) iterating this process with new values of the constraints.

Figure 2 illustrates the particular case of two criteria Z 1 and Z 2 . To obtain the Pareto front, Z 1 is transformed into a constraint, with its first value set to K 1 1 = +∞. The first run involves minimizing Z 2 under the constraint Z 1 < +∞, which produces the Pareto point x 1 . For the second run, the constraint is set to the value of x 1 , that is

K 2 1 = Z 1 (x 1 ): we therefore minimize Z 2 under the constraint Z 1 < K 2 1
, which produces the Pareto point x 2 , and so on. This process converges provided that the number of Pareto optima is bounded. Otherwise it suffices to slice the interval [0, +∞) into a finite number of contiguous sub-intervals of the form [K i+1

1 , K i 1 ], resulting in one point for each such interval. That way, the grain of the Pareto front can be improved by reducing the size of the intervals, at the cost of more iterations of the method. Note that each point obtained in this way is not necessarily a point of the Pareto front since it may be dominated by other points.

K 1 1 = +∞ x 4 x 2 x 3 x 5 K 4 1 K 3 1 Z 2 x 1 K 2 1 Z 1
Fig. 2 Transformation method to produce the Pareto front. Now, the application algorithm graphs we are dealing with are large (tens to hundreds of operations, each operation being a software block), thereby making infeasible exact scheduling methods, or even approximated methods with backtracking, such as branch-and-bound. We therefore chose to use list scheduling heuristics, first introduced in [START_REF] Hu | Parallel sequencing and assembly line problems[END_REF], and which have demonstrated their good performances for scheduling large graphs [START_REF]Handbook of Scheduling[END_REF]. We propose in this paper a tricriteria list scheduling heuristic, called TSH, adapted from [START_REF] Girault | A novel bicriteria scheduling heuristics providing a guaranteed global system failure rate[END_REF]. TSH improves on [START_REF] Girault | A novel bicriteria scheduling heuristics providing a guaranteed global system failure rate[END_REF] by working with three criteria, the schedule length, the reliability, and the power consumption.

Using list scheduling to minimize a criterion Z 2 under the constraint that another criterion Z 1 remains below some threshold K i 1 (as in Figure 2), requires that Z 1 be an invariant measure, not a varying one. For instance, the energy is a strictly increasing function of the schedule, in the mathematical sense: if S ′ is a prefix schedule of S, then the energy consumed by S is strictly greater than the energy consumed by S ′ . Hence, the energy is not an invariant measure; more precisely it is additive. Figure 3(a) illustrates this fact. The operations are scheduled in the order 1, 2, and so on. Up to the operation number 6, the energy criterion is satisfied: ∀1 ≤ i ≤ 6, E(S (i) ) ≤ E obj , where S (i) is the partial schedule at iteration (i). But there is no way to prevent S (7) from failing to satisfy the criterion, because whatever the operation scheduled at iteration [START_REF]IBM ILOG CPLEX Optimizer[END_REF], E(S (7) ) > E obj . And with list scheduling, it is not possible to backtrack. As a consequence, using the energy as a constraint (i.e., Z 1 = E) and the schedule length as a criterion to be minimized (i.e., Z 2 = L) is bound to fail. Indeed, the fact that all the scheduling decisions made at the stage of any intermediary schedule S ′ meet the constraint E(S ′ ) < K cannot guarantee that the final schedule S will meet the constraint E(S) < K. In contrast, the power consumption is an invariant measure (being the energy divided by the time), and this is why we take the power consumption as a criterion instead of the energy consumption (see Section 3.5).

The reliability too is not an invariant measure, because the contribution of each scheduled operation i is a probability in [0, 1], which is multiplied to the reliability of the partial schedule computed so far, R(S (i-1) ). The consequence is a "so far so good" situation, which results in a "funnel" effect on the replication level of the operations. This is illustrated by Figure 3(b): up to operation 4, the replication level is 1 because this choice minimizes the increase in the schedule length, and the reliability objective is satisfied: R(S i ) > R obj for i ≤ 4. But at this point, it is not possible to schedule operation 5 with no replication, and at the same time satisfy the reliability objective. However, replicating this operation on all the processors of the target architecture (say 4 for the sake of the example) results in a probability very close to 1, therefore allowing the reliability to decrease only very slightly (Figure 3(b) shows an horizontal line for R(S) after the fifth operation, but actually it decreases very slightly). This is why we take instead, as a criterion, the global system failure rate per time unit (GSFR), first defined in [START_REF] Girault | A novel bicriteria scheduling heuristics providing a guaranteed global system failure rate[END_REF]. By construction, the GSFR is an invariant measure of the schedule's reliability (see Section 4.1).

For these reasons, each run of our tricriteria scheduling heuristic TSH minimizes the schedule length under the double constraint that the power consumption and the GSFR remain below some thresholds, noted respectively P obj and Λ obj . By running TSH with decreasing values of P obj and Λ obj , starting with (+∞, +∞), we are able to produce the Pareto front in the 3D space (length,GSFR,power). This Pareto front shows the existing tradeoffs between the three criteria, allowing the user to choose the solution that best meets his/her application needs. Finally, our method for producing a Pareto front could work with any other scheduling heuristic minimizing the schedule length under the constraints of both the reliability and the power.

Models

Application algorithm graph

Embedded real-time systems are reactive, and therefore consist of some algorithm executed periodically, triggered by a periodic execution clock. We follow the periodic task model of [START_REF] Kopetz | Real-Time Systems: Design Principles for Distributed Embedded Applications[END_REF], shown in Figure 4(b). Our model is therefore that of a synchronous application algorithm graph Alg, which is repeated infinitely in order to take into account the reactivity of the modeled system, that is, its reaction to external stimuli produced by its environment. In other words, the body of the periodic loop of Figure 4(b) is captured by the Alg graph. Alg is an acyclic oriented graph (X , D) (See Figure 4(a)). Its nodes (the set X ) are software blocks called operations. Each arc of Alg (the set D) is a data-dependency between two operations. If X ⊲ Y is a data-dependency, then X is a predecessor of Y , while Y is a successor of X. The set of predecessors of X is noted pred(X) while its set of successors is noted succ(X). X is also called the source of the data-dependency X ⊲ Y , and Y is its destination.

I 1 I 2 G O 1 I 3 C A F B D E O 2 (a)
Operations with no predecessor are called input operations (I 1 , I 2 , and I 3 in Figure 4(a)); they capture the "Read Inputs" phase of the periodic execution loop, each one being a call to a sensor driver. Operations with no successor are called output operations (O 1 and O 2 ); they capture the "Update Outputs" phase, each one being a call to an actuator driver. The other operations (A to G) capture the "Compute" phase and have no side effect.

Architecture model

We assume that the architecture is an homogeneous and fully connected multi-processor one. It is represented by an architecture graph Arc, which is a non-oriented bipartite graph (P, L, A) whose set of nodes is P ∪L and whose set of edges is A (see Figure 5). P is the set of processors and L is the set of communication links. A processor is composed of a computing unit, to execute operations, and one or more communication units, to send or receive data to/from communication links. Typically, communication units are DMAs, which present the advantage of sending data in parallel with the processor. A point-to-point communication link is composed of a sequential memory that allows it to transmit data from one processor to another. Each edge of Arc (the set A) always connects one processor and one communication link. Here we assume that the Arc graph is complete, that is, there exists a communication link between any two processors.

P 4 P 1 L 12 P 2 L 23 L 13 P 3 L 34 L 24
L 14 Fig. 5 An example of a distributed memory architecture graph Arc with four processors, P 1 to P 4 , and six communication links, L 12 to L 34 .

Execution characteristics

Along with the algorithm graph Alg and the architecture graph Arc, we are also given a function Exenom : (X ×P)∪(D×L) → R + giving the nominal worst-case execution time (WCET) of each operation onto each processor and the worst-case communication time (WCCT) of each data-dependency onto each communication link. An intra-processor communication takes no time to execute. Since the architecture is homogeneous, the WCET of a given operation is identical on all processors (similarly for the WCCT of a given data-dependency). We call Exenom the nominal WCET because we will see in Section 3.5 that the actual WCET varies according to the voltage / frequency operating point of the processor.

The WCET analysis is the topic of much work [START_REF] Wilhelm | The determination of worst-case execution times -overview of the methods and survey of tools[END_REF]. Knowing the execution characteristics is not a critical assumption since WCET analysis has been applied with success to real-life processors actually used in embedded systems, with branch prediction, caches, and pipelines. In particular, it has been applied to one of the most critical embedded system that exists, the Airbus A380 avionics software [START_REF] Colin | Worst case execution time analysis for a processor with branch prediction[END_REF][START_REF] Theiling | Fast and precise WCET prediction by separate cache and path analyses[END_REF] running on the Motorola MPC755 processor [START_REF] Ferdinand | Reliable and precise WCET determination for a real-life processor[END_REF][START_REF] Souyris | Computing the worst case execution time of an avionics program by abstract interpretation[END_REF].

Static schedules

The graphs Alg and Arc are the specification of the system. Its implementation involves finding a multiprocessor schedule of Alg onto Arc. This consists of four functions: the two spatial allocation functions Ω O and Ω L give respectively, for each operation of and each data-dependency of Alg, the subset of processors and of communication links of Arc that will execute it; and the two temporal allocation functions Θ O and Θ L give respectively the starting date of each operation and each data-dependency on its processor or its communication link:

Ω O : X → 2 P and Θ O : X × P → R + Ω L : D → 2 L and Θ L : D × L → R +
In this work we only deal with static schedules, for which the functions Θ O and Θ L are static, and our schedules are computed off-line; i.e., the start time of each operation (resp. each data-dependency) on its processor (resp. its communication link) is statically known. A static schedule is without replication if for each operation X and each data-dependency D, we have |Ω O (X)| = 1 and |Ω L (D)| = 1. In contrast, a schedule is with (active) replication if for some operation X or data-dependency D, we have

|Ω O (X)| ≥ 2 or |Ω L (D)| ≥ 2. The number |Ω O (X)| (resp. |Ω L (D)|) is called the replication factor of X (resp. of D).
A schedule is partial if not all the operations and data-dependencies of Alg have been scheduled, but all the operations that are scheduled are such that all their predecessors are also scheduled. Finally, the length of a schedule is the max of the termination times of the last operation scheduled on each of the processors of Arc (in the literature, it is also called the makespan). For a schedule S, we note it L(S):

L(S) = max P ∈P " max X:P ∈ΩO(X) Θ O (X, P ) + Exenom(X, P ) « (1)
In the sequel, we will write X ∈ P instead of X : P ∈ Ω O (X) for the sake of simplicity. We will also number the processors from 1 to |P| and use their number in index, for instance p j (and similarly for the communication links).

Voltage, frequency, and power consumption

The maximum supply voltage is noted Vmax and the corresponding highest operating frequency is noted fmax. The WCET of any given operation is computed with the processor operating at fmax and Vmax (and similarly for the WCCT of the datadependencies). Because the circuit delay is almost linearly related to 1/V [START_REF] Burd | Energy efficient CMOS micro-processor design[END_REF], there is a linear relationship between the supply voltage V and the operating frequency f . From now on, we will assume that the operating frequencies are normalized, that is, fmax = 1 and any other frequency f is in the interval (0, 1). Accordingly, we define in Eq (2) a new function Exe that gives the execution time of the operation or data-dependency X placed onto the hardware component C, be it a processor or a communication link, which is running at frequency f . In other words, f is taken as a scaling factor:

Exe(X, C, f ) = Exenom(X, C)/f (2)
The power consumption P of a single operation or data-dependency placed on a single hardware component is computed according to the classical model found for instance in [START_REF] Luo | Simultaneous dynamic voltage scaling of processors and communication links in real-time distributed embedded systems[END_REF][START_REF] Zhu | The effects of energy management on reliability in real-time embedded systems[END_REF]:

P = Ps + h(P ind + P d ) P d = C ef V 2 f ( 3
)
where Ps is the static power (power to maintain basic circuits and to keep the clock running), h is equal to 1 when the circuit is active and 0 when it is inactive, P ind is the frequency independent active power (the power portion that is independent of the voltage and the frequency; it becomes 0 when the system is put to sleep, but the cost of doing so is very expensive [START_REF] Elnozahy | Energy-efficient server clusters[END_REF]), P d is the frequency dependent active power (the processor dynamic power and any power that depends on the voltage or the frequency), C ef is the switch capacitance, V is the supply voltage, and f is the operating frequency. C ef is assumed to be constant for all operations; this is a simplifying assumption since one would normally need to take into account the actual switching activity of each operation to compute accurately the consumed energy. However, such an accurate computation is infeasible for the application sizes we consider here.

For processors, this model is widely accepted for average size applications, where C ef can be assumed to be constant for the whole application [START_REF] Zhu | The effects of energy management on reliability in real-time embedded systems[END_REF]. For communication links on a multicore platform, this model is also relevant, as communication links are specialized processing elements [START_REF] Luo | Simultaneous dynamic voltage scaling of processors and communication links in real-time distributed embedded systems[END_REF]. Of course, the coefficients in Eq (3) should be distinct for processors and communication links. We use the following notations: coefficient processors links frequency independent active power

P p ind P ℓ ind switch capacitance C p ef C ℓ ef
Since the architecture is homogeneous, each processor (resp. communication link) has an identical value P p ind (resp. P ℓ ind ) and similarly an identical value C p ef (resp. C ℓ ef ). In contrast, since the voltage and frequency varies, each processor p j has (potentially) a distinct value P j d . We do not apply to the communication links so their voltage and frequency remains constant, respectively equal to V ℓ and f ℓ .

For a multiprocessor schedule S, we cannot apply directly Eq (3) because each processor is potentially operating at a different V and f , which vary over time. Instead, we must compute the total energy E(S) consumed by S, and then divide by the schedule length L(S):

P (S) = E(S)/L(S) (4)
We compute E(S) with Eq (5) below, by summing the contribution of each processor and of each communication link:

E(S) = |P| X j=1 0 @ P p ind •L(S) + X oi∈pj P j d Exe(o i , p j , f i,j ) 1 A + |L| X k=1 0 @ P ℓ ind •L(S) + X di∈ℓ k P k d Exe(d i , ℓ k , f ℓ ) 1 A (5)
The first sum over |P| accounts for the processors while the second sum over |L| accounts for the communication links. Whether a processor is active or idle, it always consumes at least P p ind watts, hence the first term P p ind •L(S). The second term sums the contributions of all the operations o i executed by processor p j : when the processor is executing o i at the voltage V i,j and the frequency f i,j , the additional energy consumed is the product of the active power P j d by o i 's execution time. The description is similar for the communication links. E(S) can be rewritten as Eq [START_REF] Colin | Worst case execution time analysis for a processor with branch prediction[END_REF]:

E(S) = |P|•P p ind •L(S) + C p ef |P| X j=1 0 @ X oi∈pj V 2 i,j f i,j Exe(o i , p j , f i,j ) 1 A + |L|•P ℓ ind •L(S) + C ℓ ef |L| X k=1 0 @ X di∈ℓ k V 2 ℓ f ℓ Exe(d i , ℓ k , f ℓ ) 1 A (6)

Failure hypothesis

Both processors and communication links can fail, and they are fail-silent (a behavior that can be achieved at a reasonable cost [START_REF] Baleani | Fault-tolerant platforms for automotive safety-critical applications[END_REF]). Classically, we adopt the failure model of Shatz and Wang [START_REF] Shatz | Models and algorithms for reliability-oriented task-allocation in redundant distributed-computer systems[END_REF]: failures are transient and the maximal duration of a failure is such that it affects only the current operation executing onto the faulty processor, and not the subsequent operations (same for the communication links); this is the "hot" failure model. The occurrence of failures on a processor (same for a communication link) follows a Poisson law with a constant parameter λ, called its failure rate per time unit. Modern fail-silent processors can have a failure rate around 10 -6 /hr [START_REF] Baleani | Fault-tolerant platforms for automotive safety-critical applications[END_REF]. Failures are transient. Those are the most common failures in modern embedded systems, all the more when processor voltage is lowered to reduce the energy consumption, because even very low energy particles are likely to create a critical charge leading to a transient failure [START_REF] Zhu | The effects of energy management on reliability in real-time embedded systems[END_REF]. Besides, failure occurrences are assumed to be statistically independent events. For hardware faults, this hypothesis is reasonable, but this would not be the case for software faults [START_REF] Knight | An experimental evaluation of the assumption of independence in multi-version programming[END_REF].

The reliability of a system is defined as the probability that it operates correctly during a given time interval [START_REF] Avizienis | Basic concepts and taxonomy of dependable and secure computing[END_REF]. According to our model, the reliability of the processor P (resp. the communication link L) during the duration d is R = e -λd . Conversely, the probability of failure of the processor P (resp. the communication link L) during the duration d is F = 1 -R = 1 -e -λd . Hence, the reliability of the operation or data-dependency X placed onto the hardware component C (be it a processor or a communication link) is: R(X, C) = e -λC Exe(X,C,f )

From now on, the function R will either be used with two variables as in Eq [START_REF]IBM ILOG CPLEX Optimizer[END_REF], or with only one variable to denote the reliability of a schedule (or a part of a schedule).

Since the architecture is homogeneous, the failure rate per time unit is identical for each processor (noted λp) and similarly for each communication link (noted λ ℓ ). 0 Figure 6 shows a simple schedule S where operations X and Z are placed onto P 1 , operation Y onto processor P 2 , and the data-dependency X ⊲ Y is placed onto the link L 12 . We detail below the contribution of each hardware component to the consumed energy according to Eq (6):

L (V 3 , f 3 ) L 12 Y P 2 (C p ef ,P p ind ) P 1 (C p ef ,P p ind ) (C ℓ ef ,P ℓ ind ) X ⊲ Y X (V 1 , f 1 ) Z (V 2 , f 2 ) time
-On P 1 : E(P 1 ) = P p ind •L + C p ef " V 2 1 f 1 Exe(X, P 1 , f 1 ) + V 2 2 f 2 Exe(Z, P 1 , f 2 )
" .

-On P 2 :

E(P 2 ) = P p ind •L + C p ef V 2 3 f 3 Exe(Y, P 2 , f 3 ). -On L 12 : E(L 12 ) = P ℓ ind •L + C ℓ ef V 2 ℓ f ℓ Exe(X ⊲ Y, L 12 , f ℓ ).
3.7 Summary of the assumptions 1. The algorithm graph Alg is a single clocked synchronous data flow graph. This is reasonable for automatic control software found in numerous embedded systems. Such systems are commonly called "periodic sampled systems". 2. The distributed memory architecture Arc is homogeneous and fully connected. This is reasonable since more and more embedded processors are many-core ones.

3. The switch capacitances C p ef and C ℓ ef are constant, respectively for all processors and all operations, and for all communication links and all data dependencies. This is a simplification since the switch capacitance depends on the operations actually executed by the processor. However, for the size of applications we consider, taking an average constant value is reasonable. 4. Hardware elements are fail-silent. Fail silence can be achieved at a reasonable cost, for instance with a dual lock-step processor [START_REF] Baleani | Fault-tolerant platforms for automotive safety-critical applications[END_REF]. 5. Failures are transient and their duration is such that it affects only the current operation executing onto the faulty processor, and not the subsequent operations (same for the communication links). Single event upsets (SEUs), which are the most common failures affecting hardware elements, fall in this category. 6. Failure occurrences are statistically independent events. For hardware faults, this hypothesis is reasonable, but this would not be the case for software faults [START_REF] Knight | An experimental evaluation of the assumption of independence in multi-version programming[END_REF]. 7. The occurrence of failures on a hardware element follows a Poisson law with a constant parameter λ. Over the life, λ changes according to a "bathtub" curve, with a "flat" portion in the middle. Thanks to this flat portion, a constant λ can be reasonably assumed for the processors usually deployed in safety critical systems.

4 The tricriteria scheduling algorithm TSH 4.1 Global system failure rate (GSFR) As we have demonstrated in Section 2, we must use the global system failure rate (GSFR) instead of the system's reliability as a criterion. The GSFR is the failure rate per time unit of the obtained multiprocessor schedule, seen as if it were a single operation scheduled onto a single processor [START_REF] Girault | A novel bicriteria scheduling heuristics providing a guaranteed global system failure rate[END_REF]. The GSFR of a static schedule S, noted Λ(S), is computed by Eq (8):

Λ(S) = -log R(S) U (S) (8)
Eq (8) uses the reliability R(S), which, in the case of a static schedule S without replication, is simply the product of the reliability of each operation and data dependency of S (by definition of the reliability, Section 3.6):

R(S) = Y (oi,pj )∈S R(o i , p j ) • Y (di,ℓ k )∈S R(d i , ℓ k ) (9)
Eq (8) also uses the total processor utilization U (S) instead of the schedule length L(S), so that the GSFR can be computed compositionally:

U (S) = X (oi,pj )∈S Exe(o i , p j , f i,j ) + X (di,ℓ k )∈S Exe(d i , ℓ k , f ℓ ) (10)
Thanks to Eqs (8), [START_REF] Elnozahy | Energy-efficient server clusters[END_REF], and (10), the GSFR is invariant: for any schedules S 1 and S 2 such that S = S 1 • S 2 , where "•" is the concatenation of schedules, if Λ(S 1 ) ≤ K and Λ(S 2 ) ≤ K, then Λ(S) ≤ K (Proposition 5.1 in [START_REF] Girault | A novel bicriteria scheduling heuristics providing a guaranteed global system failure rate[END_REF]).

Finally, it is very easy to translate a reliability objective R obj into a GSFR objective Λ obj : one just needs to apply the formula Λ obj = -log R obj /D, where D is the mission duration. This shows how to use the GSFR criterion in practice.

Decreasing the power consumption

Two operation parameters of a chip can be modified to lower the power consumption: the frequency and the voltage. We assume that each processor can be operated with a finite set of supply voltages, noted V. We thus have V = {V 0 , V 1 , . . . , Vmax}. To each supply voltage V corresponds an operating frequency f . We choose not to modify the operating frequency and the supply voltage of the communication links.

We assume that the cache size is adapted to the application, therefore ensuring that the execution time of an application is linearly related to the frequency [START_REF] Melhem | The interplay of power management and fault recovery in real-time systems[END_REF] (i.e., the execution time is doubled when frequency is halved).

To lower the energy consumption of a chip, we use Dynamic Voltage and Frequency Scaling (DVFS), which lowers the voltage and increases proportionally the cycle period. However, DVFS has an impact of the failure rate [START_REF] Zhu | The effects of energy management on reliability in real-time embedded systems[END_REF]. Indeed, lower voltage leads to smaller critical energy, hence the system becomes sensitive to lower energy particles. As a result, the fault probability increases both due to the longer execution time and to the lower energy: the voltage-dependent failure rate λ(f ) is:

λ(f ) = λ 0 •10 b(1-f ) 1-f min (11)
where λ 0 is the nominal failure rate per time unit, b > 0 is a constant, f is the frequency scaling factor, and f min is the lowest operating frequency. At f min and V min , the failure rate is maximal:

λmax = λ(f min ) = λ 0 •10 b .
We apply DVFS to the processors and we assume that the voltage switch time can be neglected compared to the WCET of the operations. To take into account the voltage in the schedule, we modify the spatial allocation function Ω O to give the supply voltage of the processor for each operation: Ω O : X → Q, where Q is the domain of the sets of pairs p, v ∈ P × V.

To compute the number of elements in Q, we count the number of sets of pairs p, v for each element of 2 P except the empty set. Each element E ∈ 2 P accounts for |V| |E| elements in Q. Take for example P = {p 1 , p 2 , p 3 , p 4 } and V = {v 1 , v 2 , v 3 }. Each of the 4 singletons of 2 P accounts for 3 1 = 3 elements, each of the 6 doubletons accounts for 3 2 = 9 elements, each of the 4 triplets accounts for 3 3 = 27 elements, and finally the only quadruplet accounts for 3 4 = 81 elements. The total is therefore 255 = 4 4 -1 elements. For instance, { p 1 , v 2 , p 3 , v 3 , p 4 , v 1 } is a triplet of Q, meaning that the concerned operation o is replicated three times, namely on p 1 at voltage v 2 , on p 3 at voltage v 3 , and on p 4 at voltage v 1 . In the general case, it can be shown that |Q| = (|V| + 1) |P| -1.

Decreasing the GSFR

According to Eq [START_REF] Dogan | Matching and scheduling algorithms for minimizing execution time and failure probability of applications in heterogeneous computing[END_REF], decreasing the GSFR is equivalent to increasing the reliability. Several techniques can be used to increase the reliability of a system. Their common point is to include some form of redundancy (this is because the target architecture Arc, with the failure rates of its components, is fixed) [START_REF] Gärtner | Fundamentals of fault-tolerant distributed computing in asynchronous environments[END_REF]. We have chosen the active replication of the operations and the data-dependencies, which consists in executing several copies of a same operation onto as many distinct processors (resp. data-dependencies onto communication links). Adding more replicas increases the reliability, but also, in general, the schedule length: in this sense, we say that the two criteria, length and reliability, are antagonistic.

To compute the GSFR of a static schedule with replication, we use Reliability Block-Diagrams (RBD) [START_REF] Balaban | Some effects of redundancy on system reliability[END_REF][START_REF] Lloyd | Reliability: Management, Methods, and Mathematics[END_REF]. An RBD is an acyclic oriented graph (N, E), where each node of N is a block representing an element of the system, and each arc of E is a causality link between two blocks. Two particular connection points are its source S and its destination D. An RBD is operational if and only if there exists at least one operational path from S to D. A path is operational if and only if all the blocks in this path are operational. The probability that a block be operational is its reliability. By construction, the probability that an RBD be operational is thus the reliability of the system it represents.

In our case, the system is the multiprocessor static schedule, possibly partial, of Alg onto Arc. Each block represents an operation X placed onto a processor P i or a data-dependency X ⊲ Y placed onto a communication link L j . The reliability of a block is therefore computed according to Eq [START_REF]IBM ILOG CPLEX Optimizer[END_REF].

Computing the reliability in this way requires the occurrences of the failures to be statistically independent events. Without this hypothesis, the fact that some blocks belong to several paths from S to D makes the reliability computation infeasible. At each iteration of the scheduling heuristic, we compute the RBD of the partial schedule obtained so far, then we compute the reliability based on this RBD, and finally we compute the GSFR of the partial schedule with Eq [START_REF] Dogan | Matching and scheduling algorithms for minimizing execution time and failure probability of applications in heterogeneous computing[END_REF].

Finally, computing the reliability of an RBD with replications is, in general, exponential in the size of the schedule. To avoid this problem, we insert routing operations so that the RBD of any partial schedule is always serial-parallel (i.e., a sequence of parallel macro-blocks), hence making the GSFR computation linear [START_REF] Girault | A novel bicriteria scheduling heuristics providing a guaranteed global system failure rate[END_REF]. The idea is that, for each data dependency X ⊲ Y such that it has been decided to replicate X k times and Y ℓ times, a routing operation R will collect all the data sent by the k replicas of X and send it to the ℓ replicas of Y (see Figure 7). This scheme, known as "replication for reliability" [START_REF] Girault | Reliability versus performance for critical applications[END_REF], has a drawback in terms of schedule length, because the routing operation R cannot complete before it has received the data sent by all the replicas of X. However, it has been shown in [START_REF] Girault | A novel bicriteria scheduling heuristics providing a guaranteed global system failure rate[END_REF] that, on average, the overhead of inserting routing operations on the schedule length is less than 4%.

R Y

ℓ X 1 X k Y 1 . . . . . .

Principle of the scheduling heuristic TSH

To obtain the Pareto front in the space (length,GSFR,power), we predefine a virtual grid in the objective plane (GSFR,power), and for each cell of the grid we solve one different single objective problem constrained to this cell, by using the scheduling heuristic TSH presented below. The single objective is the schedule length that TSH aims at minimizing.

TSH is a ready list scheduling heuristic. It takes as input an algorithm graph Alg, a homogeneous architecture graph Arc, the function Exe giving the WCETs and WCCTs, and two constraints Λ obj and P obj . It produces as output a static multiprocessor schedule S of Alg onto Arc, such that the GSFR of S is smaller than Λ obj , the power consumption is smaller than P obj , and such that its length is as small as possible. TSH uses active replication of operations to meet the Λ obj constraint, dynamic voltage scaling to meet the P obj constraint, and the power-efficient schedule pressure as a cost function to minimize the schedule length.

Besides, TSH inserts routing operations to make sure that the RBD of any partial schedule is serial-parallel (otherwise, computing the reliability is exponential in the size of the schedule -see Section 4.3).

TSH works with two lists of operations of Alg: the ready operations O sched . For the ease of notation, we sometimes write P (n) for P `S(n) ´, and similarly for the schedule length L, the energy E, or the GSFR Λ.

power-efficient schedule pressure

The power-efficient schedule pressure is a variant of the schedule pressure cost function [START_REF] Grandpierre | Optimized rapid prototyping for real-time embedded heterogeneous multiprocessors[END_REF], which tries to minimize the length of the critical path of the algorithm graph by exploiting the scheduling margin of each operation. The schedule pressure σ is computed for each ready operation o i and each processor p j by Eq [START_REF] Girault | A novel bicriteria scheduling heuristics providing a guaranteed global system failure rate[END_REF]:

σ (n) (o i , p j ) = ET S (n) (o i , p j ) + LT E (n) (o i ) -CP L (n) ( 12
)
where CP L (n) is the critical path length of the partial schedule at step (n) composed of the already scheduled operations, ET S (n) (o i , p j ) is the earliest time at which the operation o i can start its execution on the processor p j , and LT E (n) (o i ) is the latest start time from end of o i , defined to be the length of the longest path from o i to Alg's output operations; this path contains the "future" operations of o i . When computing LT E (n) (o i ), since the future operations of o i are not scheduled yet, we do not know their actual voltage, and therefore neither what their execution time will be (this will only be known when these future operations will be actually scheduled). Hence, for each future operation, we compute its average WCET for all existing supply voltages. Eq [START_REF] Girault | Reliability versus performance for critical applications[END_REF] generalizes the schedule pressure to a set of processors:

σ (n) (o i , P k ) = ET S (n) (o i , P k ) + LT E (n) (o i ) -CP L (n) (13) ET S (n) (o i , P k ) = max pj ∈P k ET S (n) (o i , p j )
Then, we consider the schedule length as a criterion to be minimized, and the energy increase and the GSFR as two constraints to be met: for each ready operation

o i ∈ O (n)
ready , the power-efficient schedule pressure of Eq [START_REF] Grandpierre | Optimized rapid prototyping for real-time embedded heterogeneous multiprocessors[END_REF] computes the best subset

Q (n) best (o i ) of pairs processor, voltage to execute o i : Q (n) best (o i ) = Q j such that: σ (n) (o i , Q j ) = min Q k ∈Q  σ (n) (o i , Q k ) | `E(n+1) -E (n) ´≤ P obj `L(n+1) -L (n) ∧ Λ B (o i , Q k ) ≤ Λ obj ff ( 14
)
where Q is the set of all subsets of pairs p, v such that p ∈ P and v ∈ V (see Section 4.2), Λ B (o i , Q k ) is the GSFR of the parallel macro-block that contains the replicas of o i on all the processors of Q k1 , and `E(n+1) -E (n) ´is the energy increase due to the scheduling of o i on all the processors of Q k at their respective voltages, where E (n+1) and E (n) are computed by Eq (6), E (n) begin the energy before scheduling o i and E (n+1) after. Finally, when computing Λ B (o i , Q k ), the failure rate of each processor is computed by Eq [START_REF] Gärtner | Fundamentals of fault-tolerant distributed computing in asynchronous environments[END_REF] according to its voltage in Q k . Finally, the constraint on the energy consumption `E(n+1) -E (n) ´≤ P obj `L(n+1) -L (n) ´is equivalent to a constraint on the power consumption, `E(n+1) -E (n) ´/`L (n+1) -L (n) ´≤ P obj , but without the potential division by zero.

The local constraint on the current macro-block of the RBD, Λ B (o i , Q k ) ≤ Λ obj , guarantees that the global constraint on the schedule at iteration (n + 1), Λ (n+1) ≤ Λ obj , is met. This will be formally established by Proposition 1 (see Section 4.7).

Similarly, we would like the local constraint on the energy increase due to

o i , `E(n+1) -E (n) ´≤ P obj `L(n+1) -L (n)
´, to guarantee that the global constraint at iteration (n + 1) on the full schedule P (n+1) ≤ P obj is met. Unfortunately, we can show a counter example for this. Consider the case when the operation o i scheduled at iteration (n) does not increase the schedule length, because it fits in a slack at the end of the previous schedule: n) . In contrast, the total energy always increases strictly because of o i : `E(n+1) -E (n) ´> 0. It follows that, whatever the choice of processors, voltage, and frequency for o i , it is impossible to schedule it such that the energy increase constraint `E(n+1) -E (n) ´≤ P obj `L(n+1) -L (n) ´be met.

L (n+1) = L (

Over-estimation of the energy consumption

To prevent this and to guarantee the invariance property of P , we over-estimate the power consumption, by computing the consumed energy as if all the ending slacks were "filled" by an operation executed at (fover, Vover). We choose the largest frequency and voltage (fover, Vover) such that:

`E(n+1) -E (n) ´≤ P obj `L(n+1) -L (n) ´(15)
We start with (fmax, Vmax). If the Condition ( 15) is not met, then we select the next highest operating frequency, and so on until Condition ( 15) is met. Thanks to this over-estimation, even if the next scheduled operation fits in a slack and does not increase the length, we are sure that it will not increase the power-consumption either. This is illustrated in Figure 8.

Formally, we now compute the total energy consumed by the schedule S with Eq (16) instead of Eq [START_REF] Colin | Worst case execution time analysis for a processor with branch prediction[END_REF]. We call E + the over-estimated energy consumption:

E + (S) = |P|•P p ind •L(S) + C p ef |P| X j=1 0 @ X oi∈pj V 2 i,j f i,j Exe(o i , p j , f i,j ) + V 2 over `L(S)-M j ´1 A + |L|•P ℓ ind •L(S) + C ℓ ef |L| X k=1 0 @ X di∈ℓ k V 2 ℓ f ℓ Exe(d i , ℓ k , f ℓ ) 1 A (16)
where, L(S) -M j is the slack available at the end of processor p j , for all processor p j ∈ P, M j = maxo i ∈pj `st(o i , p j ) + Exe(o i , p j , f i,j ) ´is the completion time of the last operation scheduled on p j , and for all operation o i scheduled on p j , st(o i , p j ) is the start time of o i on p j . Compared to Eq (6), we see that the over-estimating term V 2 over `L(S) -M j ´has been added.

P 2 P d P d P d X ⊲ Y time      Y (V 3 , f 3 ) X (V 1 , f 1 ) Z    (V 2 , f 2 )
over-estimation

P over P 1 (C p ef ,P p ind ) L 12
Fig. 8 Over-estimation of the energy consumption.

Accordingly, we now compute the power-efficient schedule pressure with Eq (17) instead of Eq [START_REF] Grandpierre | Optimized rapid prototyping for real-time embedded heterogeneous multiprocessors[END_REF]:

Q (n) best (o i ) = Q j such that: σ (n) (o i , Q j ) = min Q k ∈Q  σ (n) (o i , Q k ) | `E(n+1) + -E (n) + ´≤ P obj `L(n+1) -L (n) ∧ Λ B (o i , Q k ) ≤ Λ obj ff (17)
Once we have computed, for each ready operation

o i of O (n)
ready , the best subset of pairs processor, voltage to execute o i , with the power-efficient schedule pressure of Eq [START_REF] Kopetz | Real-Time Systems: Design Principles for Distributed Embedded Applications[END_REF], we compute the most urgent of these operations with Eq [START_REF] Lee | Minimizing energy consumption for precedence-constrained applications using dynamic voltage scaling[END_REF]:

ourg = o i ∈ O (n) ready s.t. σ (n) `oi , Q (n) best (o i ) ´= max oj ∈O (n) ready  σ (n) `oj , Q (n) best (o j ) ´ff (18)
Finally, we schedule this most urgent operation ourg on the processors of the set Q (n) best (ourg), and we end the current iteration (n) by updating the lists of scheduled and ready operations. Firstly, the newly scheduled operation ourg is added to the list of scheduled operations:

O (n+1) sched := O (n)
sched ∪ {ourg}. Secondly, ourg is removed from the list of ready operations, which is also augmented with all the successors of ourg that happen to have all their predecessors in the new list of scheduled operations:

O (n+1) ready := O (n) ready -{ourg} ∪ {o ′ ∈ succ(ourg) | pred(o ′ ) ⊆ O (n+1) sched }.

Soundness of TSH

The soundness of TSH is is based on two propositions. The first one establishes that the schedules produced by TSH meet their GSFR constraint. Its proof can be found in [START_REF] Girault | A novel bicriteria scheduling heuristics providing a guaranteed global system failure rate[END_REF]: Proposition 1 Let S be a multiprocessor schedule of Alg onto Arc. If each operation o of Alg has been scheduled according to Eqs [START_REF] Kopetz | Real-Time Systems: Design Principles for Distributed Embedded Applications[END_REF] and [START_REF] Lee | Minimizing energy consumption for precedence-constrained applications using dynamic voltage scaling[END_REF] such that the reliability is computed with Eq (8), then the GSFR Λ(S) is less than Λ obj .

The second proposition establishes that the schedules produced by TSH meet their power consumption constraint: Proposition 2 Let S be a multiprocessor schedule of Alg onto Arc. If each operation o of Alg has been scheduled according to Eqs ( 17) and ( 18) such that the energy consumption is computed with Eq (16), then the total power consumption P (S) is less than P obj .

Proof First, we observe that, for any non empty schedule S, P (S) ≤ P obj is equivalent to E(S) ≤ P obj L(S). Moreover, since E(S) ≤ E + (S), it is sufficient to prove the inequality of Eq [START_REF]Handbook of Scheduling[END_REF]:

E + (S) ≤ P obj L(S) (19)
We prove Eq [START_REF]Handbook of Scheduling[END_REF] by induction on the scheduling iteration (n). The induction hypothesis [H] is on the energy consumed by the partial schedule S (n) :

E (n) + ≤ P obj L (n) [H]
[H] is satisfied for the initial empty schedule S (0) because E

+ = 0 and L (0) = 0. Let ourg be the operation chosen by Eq [START_REF] Lee | Minimizing energy consumption for precedence-constrained applications using dynamic voltage scaling[END_REF] at iteration (n) to be scheduled on all the processors of the set Q (n) best (ourg). According to Eq [START_REF] Kopetz | Real-Time Systems: Design Principles for Distributed Embedded Applications[END_REF], we have:

`E(n+1) + -E (n) + ´≤ P obj `L(n+1) -L (n) ⇐⇒ E (n+1) + ≤ E (n) + + P obj `L(n+1) -L (n) Thanks
to [H], we thus have:

E (n+1) + ≤ P obj L (n) + P obj `L(n+1) -L (n) ⇐⇒ E (n+1) + ≤ P obj L (n+1)
As a conclusion, [H] holds for the schedule S (n+1) . ✷

The TSH algorithm

The TSH scheduling heuristic is shown in Figure 9. Initially, O

sched is empty and

O (0)
ready is the list of operations without any predecessors. At the end of each iteration (n), these lists are updated according to the data-dependencies of Alg.

At each iteration (n), one operation o

i of the list O (n)
ready is selected to be scheduled.

For this, we select at the micro-steps ➀ and ➁, for each ready operation o i , the best subset of processors Q (n) best (o i ) to replicate and schedule o i , such that the GSFR of the resulting partial schedule is less than Λ obj and the power consumption is less than P obj ; at this point, each processor is selected with a voltage. Then, among those best pairs

o i , Q (n)
best (o i ) , we select at the micro-step ➂ the one having the biggest power-efficient schedule pressure value, i.e., the most urgent pair ourg,

Q (n) best (ourg) .
In Section 6, we will present a complete set of simulation results, first involving TSH alone, then comparing TSH with a multicriteria heuristic from the literature, and finally comparing TSH with an optimal Mixed Linear Integer Program.

Algorithm TSH: input: Alg, Arc, Exe, Λ obj , and P obj ; output: a multi-processor static schedule of Alg on Arc that minimizes the length and satisfies Λ obj and P obj , or a failure message; begin Compute the set Q of all subsets of pairs processor, voltage ; O

o i ∈ O (n) ready , compute σ (n) (o i , Q k ) for each Q k ∈ Q. ➁ For each ready operation o i , select the best subset Q (n) best (o i ) ∈ Q such that: σ (n) (o i , Q j ) = min Q k ∈Q  σ (n) (o i , Q k ) | `E(n+1) + -E (n) + ´≤ P obj `L(n+1) -L (n) ∧ Λ B (o i , Q k ) ≤ Λ obj ff ➂ Select the most urgent ready operation ourg among all o i of O (n)
ready such that:

σ (n) `ourg, Q (n) best (ourg) ´= max o j ∈O (n) ready  σ (n) `oj , Q (n) best (o j ) ´ff ➃ Schedule each replica of ourg on each processor of Q (n)
best (ourg) and at the voltage specified in

Q (n) best (ourg); ➄ if (Q (n+1) (ourg) = ∅) then
return "fail to satisfy the constraints"; exit; /* the user can modify Λ obj or P obj and re-run TSH */ ➅ Update the lists of ready and scheduled operations:

O (n+1) sched := O (n) sched ∪ {ourg}; O (n+1) ready := O (n) ready -{ourg} ∪ {o ′ ∈ succ(ourg) | pred(o ′ ) ⊆ O (n+1) sched }; ➆ n := n + 1;
end while end Fig. 9 The TSH tricriteria scheduling heuristic.

Mixed Integer Linear Programming approach

In this section, we define a mixed integer linear programming model (MILP) for our scheduling problem. Our goal is to compare the optimal results obtained by our MILP program with those achieved by TSH on small Alg graphs. Comparisons will be shown in Section 6.4.

For each operation t i of Alg, let s ik ∈ R + be the starting execution time of its k-th replica:

∀i, s ik ≥ 0 ( 20
)
Let p ik ∈ N be the processor index where the k-th replica of operation t i is to be executed. The value 0 indicates that no processor is selected:

∀i, p ik ∈ {0, . . . , |P|} (21)
Let x ikℓ be 1 if the k-th replica of operation t i is assigned to processor number ℓ, and 0 otherwise: ∀i, ∀k, ∀ℓ, x ikℓ ∈ {0, 1}

∀i, ∀k,

X ℓ x ikℓ = 1 (23)
The constraints [START_REF] Pop | Scheduling and voltage scaling for energy/reliability trade-offs in fault-tolerant time-triggered embedded systems[END_REF] link the mapping variables x with the processors indices p:

∀i, ∀k, p ik = X ℓ ℓ x ikℓ (24)
Let x ikℓm be 1 if the k-th replica of operation t i is assigned to processor number ℓ and runs with frequency m, and 0 otherwise: ∀i, ∀k, ∀ℓ, ∀m,

x ikℓm ∈ {0, 1} (25)
∀i, ∀k, ∀ℓ,

X m x ikℓm = x ikℓ (26)
We can then define W as the schedule length of Alg on Arc (the makespan):

∀i, ∀k,

s ik + X k,ℓ,m x ikℓm Exe(t i , P ℓ , fm) ≤ W (27)
Let U be the total utilization of the processors of Arc:

U = X i,k X ℓ,m
Exe(t ik , P ℓ , fm)

The two global objectives Λ obj and R obj are related by the reliability formula:

Λ obj U = -log(R obj ) (29)
In order to model the non-overlapping of operations and to reflect the fact that the multiprocessor schedule must enforce the precedence of the Alg graph, we define two sets of binary variables σ ikjk ′ and ε ikjk ′ such that:

-for each i, j, σ ikjk ′ is equal to 1 if the k-th replica of operation t i ends before the k ′ -th replica of operation t j starts, and 0 otherwise:

∀i, ∀j, ∀k, ∀k ′ , σ ikjk ′ ∈ {0, 1} (30)
-for each i, j, ε ikjk ′ is equal to 1 if the index of the processor of the replica of operation t i is strictly less that the processor index of the replica of operation t j , and 0 otherwise:

∀i, ∀j, ∀k, ∀k ′ , ε ikjk ′ ∈ {0, 1} (31)
we have used the same random graph generator as in [START_REF] Girault | A novel bicriteria scheduling heuristics providing a guaranteed global system failure rate[END_REF]. The nominal failure rate per time unit (i.e., the λ 0 of Eq [START_REF] Gärtner | Fundamentals of fault-tolerant distributed computing in asynchronous environments[END_REF]) of all the processors is λp = 10 -5 ; the nominal failure rate per time unit of all the links is λ ℓ = 5.10 -4 ; the set of supply voltages is V = {0.25, 0.50, 0.75, 1.0} (scaling factor).

The virtual grid of the Pareto front is defined such that both high and small values of P obj and Λ obj are covered within a reasonable grid size. Hence, the values of P obj and Λ obj , from the less to the most constrained, are selected from two sets of values: P obj ∈ {3.0, 2.8, 2.6, . . . 1.0} and Λ obj ∈ {8.10 -1 , 4.10 -1 , 8.10 -2 , . . . 4.10 -14 }. TSH being a heuristic, changing the parameters of this grid could change locally some points of the Pareto front, but not its overall shape. Figures 10 and 11 connect the set of non-dominated Pareto optima (the surface obtained in this way is only depicted for a better visual understanding; by no means do we assume that points interpolated in this way are themselves Pareto optima, only the computed dots are). The figures show an increase of the schedule length for points with decreasing power consumptions and/or failure rates. The "cuts" observed at the top and the left of the plots are due to low power constraints and/or low failure rates constraints.

Figures 10 and11 exposes to the designer a choice of several tradeoffs between the execution time, the power consumption, and the reliability level. For instance, in Figure 11, we see that, to obtain a GSFR of 10 -10 with a power consumption of 1.5 V , then we must accept a schedule three times longer than if we impose no constraint on the GSFR nor the power. We also see that, by providing a 4 processor architecture (Figure 11), we can obtain schedules with a shorter execution length than with only 3 processors, even though we impose identical constraints to the GSFR and the power (Figure 10): with 4 processors the schedule length is in the range [66, 374] time units, while with 3 processors it is in the range [88, 437] time units. 6.2 Impact of the power consumption and of the GSFR on the length Figure 12(a) shows how the schedule length varies in function of the required power consumption, with Λ obj set to 10 -5 . This curve is averaged over 30 randomly generated Alg graphs. We can see that the average schedule length increases when the constraint P obj on the power consumption decreases. This was expected since the two criteria, schedule length and power consumption, are antagonistic. shows how the schedule length varies in function of the required GSFR, with P obj set to 2.5 watt. Again, this curve is averaged over 30 randomly generated Alg graphs. We can see that the average schedule length increases when the constraint Λ obj on the GSFR decreases. Again, this is expected because the two criteria, schedule length and GSFR, are antagonistic.

Comparison with ECS

We have compared the performance of TSH with the algorithm proposed in [START_REF] Lee | Minimizing energy consumption for precedence-constrained applications using dynamic voltage scaling[END_REF], called ECS (Energy-Conscious Scheduling heuristic). ECS is a bicriteria scheduling heuristic that takes as input a DAG of tasks and a set of p fully connected, heterogeneous, DVFS enabled, processors. The power consumption model is the same as ours, but the energy consumed by an application does not take into account the energy consumed by the inter-tasks data-dependencies on the communication links. The cost function used by ECS sums two terms, one for the energy and one for the schedule length (aggregation method). Since ECS is not tricriteria, we proceed as follows:

1. We first invoke ECS on a given instance (an Alg graph and an Arc graph). We then compute the overall reliability R ECS , the total energy E ECS , the schedule length L ECS , and the total utilization U ECS of the schedule produced by ECS. 2. We use these values to compute the objectives required to run TSH: Λ obj = -log(R ECS )/U ECS and P obj = E ECS /L ECS . And finally. we invoke TSH with these values of the objectives.

We have plotted in Figures 13,[START_REF] Grandpierre | Optimized rapid prototyping for real-time embedded heterogeneous multiprocessors[END_REF], and 15, respectively the average schedule length, the average energy consumption, and the average reliability of the schedules computed by ECS and by TSH. The values have been averaged over 50 randomly generated Alg of size N varying between 10 and 100 operations. The Arc graph has P = 6 processors, and the nominal failure rate per time unit of all the processors is λp = 10 -5 ; the nominal failure rate per time unit of all the links is λ ℓ = 5.10 -4 . Our experimental results (Figures 13, 14 and 15) show that TSH performs systematically better than ECS. This is a very good result.

MILP and TSH simulation results

For the evaluation of MILP approach, we used an algorithm graph Alg of 5 operations and an architecture graph Arc consisting of 3 fully connected processors. The execution times of the operations were assigned randomly within 10 to 30 time units. In this simulation, we assumed that the communication links were reliable.

The nominal failure rate per time unit of the processors is λp = 10 -5 . The set of processor frequencies is set to {0.25, 0.5, 0.75, 1}. The decreasing values of P obj and Λ obj are selected from two sets of values: P obj ∈ {3.0, 2.8, 2.6, . . . 1.0} and Λ obj ∈ {8.10 -1 , 4.10 -1 , 8.10 -2 , . . . 4.10 -9 }.

We have used the CLPEX ILOG solver [START_REF]IBM ILOG CPLEX Optimizer[END_REF], version 11.2, on an Intel Core-2 Duo CPU E7500 2.93GHz computer with 2 GB of RAM. Even with an Alg graph of 7 operations, a run of MILP can take more than 40 hours without finding the optimal value. This is why we have limited the Alg graph to 5 operations and the Arc graph to 3 processors. The processing time of TSH is, as expected, much shorter than that of the MILP: in the order of one second for TSH versus between a few seconds and 40 minutes for the MILP. The Pareto fronts generated by MILP and TSH are shown in Figure 16, where the colored surface corresponds to MILP results while the uncolored one corresponds to TSH. For small values of P obj and Λ obj (i.e., when the multicriteria problem is highly constrained), the TSH surface is significantly above the MILP one. For large values of P obj and Λ obj (i.e., when the multicriteria problem is not so constrained), the two surfaces are almost glued one to the other. The average overhead of the schedule length achieved by TSH versus the length achieved by the MILP is only 15.6 % (the exact approximation ratio is 1.1563051). This shows that TSH performs very well compared to the optimal result obtained by the MILP.

Related work

Many solutions exist in the literature to optimize the schedule length and the energy consumption (e.g., [START_REF] Pering | The simulation and evaluation of dynamic voltage scaling algorithms[END_REF]), or to optimize the schedule length and the reliability (e.g., [START_REF] Dogan | Matching and scheduling algorithms for minimizing execution time and failure probability of applications in heterogeneous computing[END_REF][START_REF] Girault | Reliability versus performance for critical applications[END_REF][START_REF] Benoit | Reliability and performance optimization of pipelined real-time systems[END_REF]), but very few tackle the problem of optimizing the three criteria (length,reliability,energy). The closest to our work are [START_REF] Zhu | The effects of energy management on reliability in real-time embedded systems[END_REF][START_REF] Pop | Scheduling and voltage scaling for energy/reliability trade-offs in fault-tolerant time-triggered embedded systems[END_REF].

Zhu et al. have studied the impact of the supply voltage on the failure rate [START_REF] Zhu | The effects of energy management on reliability in real-time embedded systems[END_REF], in a passive redundancy framework (primary backup approach). They use DVFS to lower the energy consumption and they study the tradeoff between the energy consumption and the "performability" (defined as the probability of finishing the application correctly within its deadline in the presence of faults). A lower frequency implies a higher execution time and therefore less slack time for scheduling backup replicas, meaning a lower performability. However, their input problem is not a multiprocessor scheduling one since they study the system as a single monolithic operation executed on a single processor. Thanks to this simpler setting, they are able to provide an analytical solution based on the probability of failure, the WCET, the voltage, and the frequency.

Pop et al. have addressed the (length,reliability,energy) tricriteria optimization problem on an heterogeneous architecture [START_REF] Pop | Scheduling and voltage scaling for energy/reliability trade-offs in fault-tolerant time-triggered embedded systems[END_REF]. Both length and reliability are taken as a constraint, respectively with a given upper and lower bound. These two criteria are not invariant measures, and we have demonstrated in Section 2 that such a method cannot always guarantee that the constraints are met. Indeed, their experimental results show that the reliability decreases with the number of processors, therefore making it impossible to meet an arbitrary reliability constraint. Secondly, they assume that the user will specify the number of processor failures to be tolerated in order to satisfy the desired reliability constraint. Thirdly, they assume that all the communications take place through a reliable bus. For these three reasons, it is not possible to compare TSH with their method.

Conclusion

We have presented a new off-line tricriteria scheduling heuristic, called TSH, which takes as input an application graph (a DAG of operations) and a multiprocessor architecture (homogeneous and fully connected), and produces a static multiprocessor schedule that optimizes three criteria: its length, its global system failure rate (GSFR), and its power consumption. TSH uses the active replication of the operations and the data-dependencies to increase the reliability, and uses dynamic voltage and frequency scaling to lower the power consumption.

Since the three criteria of this optimization problem are antagonistic with each other, there is no best solution in general. This is why we use the notion of Pareto optima. To address this issue, both the power and the GSFR are taken as constraints, and TSH attempts to minimize the schedule length while satisfying these constraints. By running TSH with several values of these constraints, we are able to produce a set of non-dominated Pareto solutions, the Pareto front, which is a surface in the 3D space (length,GSFR,power). This surface exposes the existing tradeoffs between the three antagonistic criteria, allowing the user to choose the solution that best meets his/her application needs.

Transforming two criteria into constraints and minimizing the third criterion is a natural approach order to produce Pareto fronts. However, some care must be taken when doing so. As we have demonstrated, each criterion that is transformed into a constraint must be an invariant measure of the schedule, not a varying one. For this reason, the two constraints imposed to TSH are the power consumption (instead of the energy consumption) and the global system failure rate (instead of the reliability).

TSH is an extension of our previous bicriteria (length,reliability) heuristic BSH [START_REF] Girault | A novel bicriteria scheduling heuristics providing a guaranteed global system failure rate[END_REF]. Studying the three criteria together makes sense because of the impact of the voltage on the failure probability. Indeed, lower voltage leads to smaller critical energy, hence the system becomes sensitive to lower energy particles. As a result, the fault probability increases both due to the longer execution time and to the lower energy.

To the best of our knowledge, this is the first reported method that allows the user to produce the Pareto front in the 3D space (length,GSFR,power). This advance comes at the price of several assumptions: the architecture is assumed to be homogeneous and fully connected, the processors are assumed to be fail-silent and their failures are assumed to be statistically independent, the power switching time is neglected, and the failure model is assumed to be exponential. In the future, we shall work on relaxing those assumptions.

Fig. 3

 3 Fig.3(a) Why the consumed energy is not an invariant measure; (b) Why the reliability is not an invariant measure and illustration of the funnel effect on the replication level of the operations.

Fig. 4

 4 Fig. 4 (a) An example of algorithm graph Alg: I 1 , I 2 , and I 3 are input operations, O 1 and O 2 are output operations, A-G are regular operations; (b) Program model of a periodic real-time task.

Fig. 6 A

 6 Fig. 6 A simple schedule of length L.

Fig. 7 A

 7 Fig. 7 A routing operation between k replicas of X and ℓ replicas of Y .

  sched . The superscript (n) denotes the current iteration of the scheduling algorithm. One operation is scheduled at each iteration (n). Initially, O (0) sched is empty while O (0) ready contains the input operations of Alg, i.e., all the operations without any predecessor. At any iteration (n), all the operations in O (n) ready are such that all their predecessors are in O (n)

➀

  For each ready operation

Fig. 10

 10 Fig. 10 Pareto front generated for an instance with 30 operations and 3 processors.

Fig. 11

 11 Fig. 11 Pareto front generated for an instance with 30 operations and 4 processors.

Fig. 12 (

 12 Fig. 12 (a) Average schedule length in function of the power; (b) In function of the GSFR.

Figure 12 (

 12 Figure 12(b) shows how the schedule length varies in function of the required GSFR, with P obj set to 2.5 watt. Again, this curve is averaged over 30 randomly generated Alg graphs. We can see that the average schedule length increases when the constraint Λ obj on the GSFR decreases. Again, this is expected because the two criteria, schedule length and GSFR, are antagonistic.

Fig. 13

 13 Fig. 13 Average schedule length generated by ECS and TSH.

Fig. 14

 14 Fig. 14 Average energy consumption generated by ECS and TSH.

Fig. 15

 15 Fig. 15 Average reliability generated by ECS and TSH.

Fig. 16

 16 Fig. 16 Pareto generated by the MILP and by TSH for an Alg graph of 5 operations scheduled onto an Arc graph of 3 processors.

Because Λ B (o i , Q k )is not the GSFR of the partial schedule S (n+1) but only of the macroblock of o i , it does not bear the superscript (n + 1).

These two variables σ and ε must satisfy the following constraints: ∀i = j, ∀k, ∀k ′ , s jk ′ -s ik -X ℓ,m

x ikℓm Exe(t i , P ℓ , fm) -U σ ikjk ′ + U ≥ 0 (32)

We define the time order on operations in terms of the σ variables in (32), and similarly we define the processors indices order on operations in terms of the ε variables in (33) where |P| is the number of processors in Arc. By (34), we ensure that operations do not overlap on a processor. By (35), we ensure that an operation cannot be scheduled both before and after another operation. Similarly, by (36), an operation cannot be placed both on a higher and on a lower processor index than another operation. Finally, (37) enforces the task precedence constraints. Let Y iK be a binary variable equal to 1 if the replication level for operation t i is K, with 1 ≤ K ≤ Rmax, and 0 otherwise. Here, Rmax is the maximal allowed replication level for the operations:

We constrain the power and the reliability of Alg on Arc in (40) and (41) respectively. Here, RB iK is the reliability of the operation i when replicated exactly K times on processors identified by the set L composed of K processor indices, with frequencies identified by the set M composed of K frequency values:

x ikℓm Exe(t ik , P ℓ , fm) f 3 m ≤ P obj W (40)

Based on these definitions, the formulation of the MILP is to minimize the execution length W under the constraints specified by Eqs [START_REF] Lloyd | Reliability: Management, Methods, and Mathematics[END_REF] to (41). This formulation is a bilinear programming where the bilinearities arise because of the reliability constraints. We have linearized this model by simply introducing a new set of variables which replace the bilinear terms.

In Section 6.4, we compare, on a given instance, the schedules obtained with this MILP and with TSH.

6 Simulation results

Examples of Pareto fronts produced by TSH

The aim of our first simulations is to produce Pareto fronts. Figures 10 and11 show the Pareto fronts produced by TSH for a randomly generated Alg graph of 30 operations, and a fully connected and homogeneous Arc graph of respectively 3 and 4 processors;