Anne Benoit

Aurélien Cavelan

Valentin Le Fèvre

Yves Robert

Hongyang Sun

A different re-execution speed can help

Keywords: resilience, silent errors, speeds, re-execution, checkpointing, verification

We consider divisible load scientific applications executing on large-scale platforms subject to silent errors. While the goal is usually to complete the execution as fast as possible in expectation, another major concern is energy consumption. The use of dynamic voltage and frequency scaling (DVFS) can help save energy, but at the price of performance degradation. Consider the execution model where a set of K different speeds is given, and whenever a failure occurs, a different re-execution speed may be used. Can this help? We address the following bi-criteria problem: how to compute the optimal checkpointing period to minimize energy consumption while bounding the degradation in performance. We solve this bi-criteria problem by providing a closed-form solution for the checkpointing period, and demonstrate via a comprehensive set of simulations that a different re-execution speed can indeed help.

I. INTRODUCTION

This paper investigates whether changing speed for reexecution, after a silent error has been detected, can help save energy while matching a prescribed performance bound. We revisit the well-known formula by Young [START_REF] Young | A first order approximation to the optimum checkpoint interval[END_REF] and Daly [START_REF] Daly | A higher order estimate of the optimum checkpoint interval for restart dumps[END_REF] to compute the optimal periodic checkpointing interval. We extend their formula to this bi-criteria energy/performance problem, where the application can be executed, or re-executed, using a set of K different speeds.

The motivation for this work is twofold. The first concern is that large-scale platforms are increasingly subject to errors. The frequent striking of silent errors (or SDCs, for Silent Data Corruptions) has been recently identified as one of the major challenges for exascale [START_REF] Cappello | Toward exascale resilience: 2014 update[END_REF]. There are several causes of silent errors, such as cosmic radiation, packaging pollution, among others. In contrast to a fail-stop error whose detection is immediate, a silent error is identified only when the corrupted data leads to an unusual application behavior. Such a detection latency raises a new challenge: if the error struck before the last checkpoint, and is detected after that checkpoint, then the checkpoint is corrupted and cannot be used for rollback. In order to avoid corrupted checkpoints, an effective approach consists in employing some verification mechanism and combining it with checkpointing [START_REF] Benoit | Efficient checkpoint/verification patterns[END_REF], [START_REF] Benoit | Optimal resilience patterns to cope with fail-stop and silent errors[END_REF]. This verification mechanism can be general-purpose (e.g., based on replication [START_REF] Fiala | Detection and correction of silent data corruption for large-scale high-performance computing[END_REF] or even triplication [START_REF] Lyons | The use of triple-modular redundancy to improve computer reliability[END_REF]) or application-specific (e.g., based on Algorithm-based fault tolerance (ABFT) [START_REF] Bosilca | Algorithm-based fault tolerance applied to high performance computing[END_REF], on approximate re-execution for ODE and PDE solvers [START_REF] Benson | Silent error detection in numerical time-stepping schemes[END_REF], or on orthogonality checks for Krylov-based sparse solvers [START_REF] Chen | Online-ABFT: An online algorithm based fault tolerance scheme for soft error detection in iterative methods[END_REF], [START_REF] Sao | Self-stabilizing iterative solvers[END_REF]).

We address silent errors by taking verified checkpoints, which correspond to performing a verification just before each checkpoint. Note that this approach is agnostic of the nature of the verification mechanism. If the verification succeeds, then one can safely store the checkpoint. If the verification fails, it means that a silent error has struck since the last checkpoint, which was duly verified, and one can safely recover from that checkpoint to resume the execution of the application. It is not difficult to compute the optimal checkpointing period T with silent errors and verified checkpoints. For fail-stop errors, the Young/Daly formula writes T = 2C/λ, where C is the time to checkpoint and λ the error rate (hence the platform MTBF is µ = 1/λ). For silent errors, the formula becomes T = (V + C)/λ, where V is the time to verify. We simply replace C by V + C in the formula, and the missing factor 2 can be explained as follows (see Figure 1): fail-stop errors are detected, on average, at half the period, while silent errors are always detected at the end of the period (by the verification mechanism). For a given T , the expected re-execution time is T /2 for fail-stop errors and T for silent errors, so the optimal period is shorter for silent errors (see [START_REF] Hérault | Fault-Tolerance Techniques for High-Performance Computing, Computer Communications and Networks[END_REF] for details).

Time V σ1 C W σ1 V σ1 C W σ1 V σ1 C (a) Without error Time V σ1 C ? σ1 R W σ2 V σ2 C W σ1 V σ1 C Fail-stop error (b) With a fail-stop error Time V σ1 C W σ1 V σ1 R W σ2 V σ2 C W σ1 V σ1 C

Silent error Detection

(c) With a silent error Figure 1. A periodic checkpointing pattern (highlighted in red) first executed at speed σ 1 and re-executed at speed σ 2 = 2σ 1 in case of error. The first figure shows the execution without any error, so only the first speed is used.

The second figure shows that the execution is stopped immediately when a fail-stop error strikes, in which case the pattern is re-executed at speed σ 2 after a recovery. The third figure shows that the execution continues after a silent error strikes, and it is detected by the verification at the end of the pattern. In this case, the pattern is also re-executed at speed σ 2 after a recovery.

The second concern is energy consumption. The power requirement of current petascale platforms is that of a small town, hence measures must be taken to reduce the energy consumption of future platforms [START_REF] Cappello | Toward exascale resilience: 2014 update[END_REF]. A popular technique is dynamic voltage and frequency scaling (DVFS): modern processors can run at different speeds, and lower speeds induce bigger savings in energy consumption. In a nutshell, this is because the dynamic power consumed when computing at speed σ is proportional to σ 3 [START_REF] Yao | A scheduling model for reduced CPU energy[END_REF], [START_REF] Bansal | Speed scaling to manage energy and temperature[END_REF], while execution time is proportional to 1/σ. As a result, computing energy (which is the product of time and power) is proportional to σ 2 . However, static power must also be accounted for, and it is paid throughout the duration of the execution, which calls for a shorter execution (at higher speeds). Overall, there are trade-offs to be found, but in most practical settings, using lower speeds reduces the global energy consumption. Unfortunately, using lower speeds also increases execution time, and a realistic approach calls for minimizing energy while guaranteeing a performance bound.

Altogether, we face a challenging problem: given a platform subject to silent errors striking at rate λ, given the cost C of a checkpoint and the cost V of a verification, and given a set S = {s 1 , s 2 , . . . , s K } of K possible speeds, what is the optimal length of the execution period T ? More precisely, because we allow the use of different speeds, what is the optimal amount of work W within a pattern, and what are the optimal speeds σ 1 , σ 2 ∈ S to use? Here, we allow the first execution at a speed σ 1 and all following possible re-executions (in case of error) at speed σ 2 . As mentioned above, optimality is defined as minimizing energy subject to a performance bound ρ, thus the target optimization problem BICRIT is formally stated as

MINIMIZE E(W, σ 1 , σ 2 ) W S.T. T (W, σ 1 , σ 2 ) W ≤ ρ, (1)
where E(W, σ 1 , σ 2 ) is the expected energy consumed to execute W units of work at speed σ 1 , with eventual re-executions at speed σ 2 , thus E(W,σ1,σ2)

W

is the expectation of the energy consumed per work unit. Similarly, T (W,σ1,σ2) W is the expected execution time per work unit, and ρ is a performance bound, or admissible degradation factor.

The main contribution of this paper is to solve this difficult optimization problem. We are able to extend the Young/Daly formula and to provide a closed-form analytical expression for the optimal solution, up to first-order approximation. We show that using different speeds can indeed induce significant savings in energy, both through theoretical analysis and via a comprehensive set of simulations conducted with realistic parameters. Finally, we explore how to extend this work to deal with both fail-stop and silent errors by reporting our preliminary findings. An interesting particular case is the following: when the platform is subject to fail-stop errors only, and the re-execution speed is twice the initial speed, the optimal checkpointing period is not in the order of the square root of platform MTBF, a striking novelty! Due to lack of space, further related work is discussed in the companion research report [START_REF] Benoit | A different re-execution speed can help[END_REF]. We simply point out that this paper is the first (to the best of our knowledge) to tackle the bi-criteria problem for HPC applications using different reexecution speeds (our previous work [START_REF] Aupy | Energy-aware checkpointing of divisible tasks with soft or hard deadlines[END_REF] deals with real-time tasks, which are assumed to be re-executed only once).

The rest of the paper is organized as follows. Section II introduces the model and notations. Section III presents our main contributions and shows how to determine the optimal pattern. Simulation results are provided in Section IV. We consider extensions (with fail-stop errors) in Section V. Finally, Section VI provides concluding remarks and future directions.

II. MODEL

We consider a divisible load application executing on a platform subject to silent errors. The execution is partitioned into periodic patterns that repeat over time. Each pattern consists of a computational chunk of W units of work followed by a verification and a checkpoint (see Figure 1). The size of the chunk W can be freely determined (this is what we mean by a divisible load application; we can insert verifications and checkpoints at any time step during the computation).

A. Parameters

The application executes on a large scale platform with the following parameters:

• Silent errors follow an exponential distribution of parameter λ, hence the platform MTBF is µ = 1/λ. The probability of an error striking during T time units is then p(T ) = 1 -e -λT . • The platform can be operated under a set S = {s 1 , s 2 , . . . , s K } of K possible speeds (each speed is the aggregated speed of all processors in the platform). • Without errors, the time to execute W units of work at speed σ ∈ S is W σ , and the energy consumed is W σ (P idle + P cpu (σ)). Here, P idle is the static power consumed when the platform is on (even idle), and P cpu (σ) = κσ 3 is the dynamic power spent by operating the platform at speed σ [START_REF] Yao | A scheduling model for reduced CPU energy[END_REF], [START_REF] Bansal | Speed scaling to manage energy and temperature[END_REF].

• The time to checkpoint is C and the time to recover is R.

The corresponding energy consumptions are C(P idle + P io ) and R(P idle + P io ), where P io is the dynamic power spent by I/O transfers. • The time to perform a verification at speed σ is V σ and the corresponding energy consumption is V σ (P idle + P cpu (σ)). We assume that all speeds in S are within normal operational range (i.e., without overscaling or underscaling), so the error rate λ is not affected by the choice of the speed.

B. Execution model

We consider the following execution model:

• The first execution is done at speed σ 1 , which is freely chosen from S. • At the end of the pattern, we verify the result. If it is correct, we can safely checkpoint. Otherwise, if the verification detects an error, we recover from the last checkpoint (or from the initial data for the first pattern), and re-execute the pattern. This re-execution, and all the subsequent re-executions if needed till success, are all done at speed σ 2 , which is also freely chosen from S. For a pattern of size W , let T (W, σ 1 , σ 2 ) be the expected time to execute the pattern in this model, and let E(W, σ 1 , σ 2 ) be the corresponding expected energy consumption.

C. Optimization problem BICRIT

Let W base denote the total amount of work of the application. Also, let T total and E total denote, respectively, the expected makespan and expected energy consumption of the application when executed using periodic patterns. For a pattern size W , there are approximately Wbase W patterns (for a long-lasting application), with each pattern having an expected execution time of T (W, σ 1 , σ 2 ). Hence, we have

T total ≈ T (W,σ1,σ2) W • W base and E total ≈ E(W,σ1,σ2) W • W base .
Minimizing the expected makespan of the application is therefore equivalent to minimizing the time overhead

T (W,σ1,σ2) W
of a single pattern and, similarly, minimizing the expected energy consumption is equivalent to minimizing the energy overhead E(W,σ1,σ2) W . The optimization problem BICRIT is to minimize the expected energy consumption (or equivalently the energy overhead) of the application subject to a bound on the expected makespan (or equivalently the makespan overhead), as presented formally in Equation (1).

III. OPTIMAL PATTERN SIZE AND SPEEDS

In this section, we compute the optimal pattern size W and speed pair (σ 1 , σ 2 ) for the BICRIT problem. We first compute T (W, σ, σ), i.e., the expected time to execute the pattern with a single speed σ.

Proposition 1. For the BICRIT problem with a single speed,

T (W, σ, σ) = C + e λW σ W + V σ + e λW σ -1 R.
Proof. The recursive equation to compute T (W, σ, σ) writes:

T (W, σ, σ) = W + V σ + p(W/σ) (R + T (W, σ, σ)) + (1 -p(W/σ))C,
where p(W/σ) = 1 -e -λW σ . The reasoning is as follows: • We always execute W units of work followed by the verification, in time W +V σ ; • With probability p(W/σ), a silent error occurred and is detected, in which case we recover and start anew; • Otherwise, with probability 1 -p(W/σ), we simply checkpoint after a successful execution. Solving this equation leads to the expected execution time.

We are now ready to compute T (W, σ 1 , σ 2 ), the expected time to execute the pattern with two speeds. Proposition 2. For the BICRIT problem,

T (W, σ 1 , σ 2 ) = C + W +V σ 1 + 1-e -λW σ 1 e λW σ 2 R+ W +V σ 2 .
Proof. With a similar reasoning as in the preceding proof, the recursive equation to compute T (W, σ 1 , σ 2 ) writes:

T (W, σ 1 , σ 2 ) = W + V σ 1 + p(W/σ 1 ) (R + T (W, σ 2 , σ 2 )) + (1 -p(W/σ 1 ))C,
where p(W/σ 1 ) = 1 -e -λW σ 1 . Plugging back the expression of T (W, σ 2 , σ 2 ) from Proposition 2 and rearranging terms, we readily obtain the expression of T (W, σ 1 , σ 2 ) as claimed.

The following shows the expected energy consumption to execute the pattern with two speeds. Proposition 3. For the BICRIT problem,

E(W, σ 1 , σ 2 ) = C + 1 -e -λW σ 1 e λW σ 2 R (P io + P idle ) + W + V σ 1 (κσ 3 1 + P idle ) + W + V σ 2 (1 -e -λW σ 1 )e λW σ 2 (κσ 3 2 + P idle ).
Proof. The power spent during checkpoint or recovery is P io + P idle , and that spent during computation and verification at speed σ is P cpu (σ) + P idle = κσ 3 + P idle . Hence, from Proposition 2, we get the expression of E(W, σ 1 , σ 2 ).

Formally, the BICRIT problem writes:

min σ1,σ2 min W E(W, σ 1 , σ 2 ) W s.t. T (W, σ 1 , σ 2 ) W ≤ ρ.
In order to get a closed-form expression for the optimal value of W , we first derive the following first-order approximation formulas, using Taylor expansion e λW = 1+λW +O(λ 2 W 2 ):

T (W, σ 1 , σ 2 ) W = 1 σ 1 + λW σ 1 σ 2 + λR σ 1 + λV σ 1 σ 2 + C + V /σ 1 W + O(λ 2 W ). (2)
E(W, σ 1 , σ 2 ) W = κσ 3 1 + P idle σ 1 + λW σ 1 σ 2 (κσ 3 2 + P idle ) + λR σ 1 (P io + P idle ) + λV σ 1 σ 2 (κσ 3 1 + P idle ) + C(P io +P idle )+V (κσ 3 1 + P idle )/σ 1 W + O(λ 2 W ). (3)
Both Equations ( 2) and (3) are of the form x + y W + zW + O(λ 2 W ), where x, y and z are positive constants. Such an expression is minimized when W = y z = Θ(λ -1/2 ), a result similar to the Young/Daly formula and which shows the accuracy of the first-order approximation via Taylor expansion, since λW = Θ(λ 1/2 ) tends to 0 with λ. Here, because we consider Equations ( 2) and ( 3) simultaneously, we have to resort to a case study to determine the optimal solution. Theorem 1. Given σ 1 , σ 2 and ρ, consider the equation

aW 2 + bW + c = 0, where a = λ σ1σ2 , b = 1 σ1 + λ R σ1 + V σ1σ2 -ρ and c = C + V σ1 .
• If there is no positive solution to the equation, i.e., b > -2 √ ac, then BICRIT has no solution. • Otherwise, let W 1 and W 2 be the two solutions of the equation with W 1 ≤ W 2 (at least W 2 is positive and possibly W 1 = W 2 ). Then, the optimal pattern size is

W opt = min(max(W 1 , W e ), W 2 ), (4)
where

W e = C(P io + P idle ) + V σ1 (κσ 3 1 + P idle ) λ σ1σ2 (κσ 3 2 + P idle ) . (5)
Proof. Neglecting lower-order terms, Equation ( 3) is minimized when W = W e given by Equation ( 5). However, this minimum value may well lead to a time overhead exceeding ρ. Enforcing T (W,σ1,σ2) W ≤ ρ is equivalent to having aW 2 + bW + c ≤ 0, where a, b and c are given in Theorem 1. Either this latter expression has no positive solution, in which case BICRIT has no solution, or W must lie within the interval

W 1 = -b- √ b 2 -4ac 2a ; W 2 = -b+ √ b 2 -4ac 2a
(where at least W 2 is positive). Because the energy overhead is a convex function of W , we deduce that W opt = min(max(W 1 , W e ), W 2 )).

For any speed pair (s i , s j ), with 1 ≤ i, j ≤ K, we define ρ i,j to be the minimum performance bound for which the BICRIT problem with σ 1 = s i and σ 2 = s j admits a solution. From the analysis of Theorem 1, we get that ρ i,j is obtained when b = -2 √ ac, which leads to

ρ i,j = 1 s i + 2 C + V s i λ s i s j + λ R s i + V s i s j . (6)
Hence, to solve the BICRIT problem for any given performance bound ρ, we can use the following simple procedure:

1) For each speed pair (s i , s j ), compute ρ i,j from Equation [START_REF] Benson | Silent error detection in numerical time-stepping schemes[END_REF], and discard those pairs with ρ < ρ i,j ; 2) For each remaining speed pair (σ 1 , σ 2 ), compute W opt from Equation ( 4), and the energy overhead

E(Wopt,σ1,σ2) Wopt
from Equation (3). 3) Select the best speed pair (σ * 1 , σ * 2 ) that minimizes the energy overhead above. This procedure takes O(K 2 ) time to run, where K is the total number of available speeds. Since K is usually small (e.g., 5) and can be considered as a constant, the optimal solution to the BICRIT problem can be computed in constant time.

IV. SIMULATIONS

In this section, we conduct simulations to evaluate our model. Section IV-A describes the parameters used in the simulations. Section IV-B investigates whether using a different re-execution speed can indeed help save energy. Section IV-C shows the impact of different parameters on the optimal solution and the associated energy overhead.

A. Simulation setup

This section describes the parameters used in the simulations. First, the recovery time is set to be the same as the checkpointing time, i.e., R = C, which is reasonable because a read operation (i.e., recovery) takes the same amount of time as a write operation (i.e., checkpointing) [START_REF] Quaglia | A cost model for selecting checkpoint positions in time warp parallel simulation[END_REF]. Also, the verification time at full speed is set to be the same as the cost of a local checkpoint (i.e., memory copy), as a complete verification checks all the data in memory. The parameters λ, C and V are set according to the real values of four platforms [START_REF] Moody | Design, modeling, and evaluation of a scalable multi-level checkpointing system[END_REF], which are reported in Table I. The power parameters P cpu , P io , P idle , as well as the set S of available speeds, are determined by the processor used. Table II gives the values of these parameters for two processors reported in [START_REF] Rizvandi | Multiple frequency selection in DVFS-enabled processors to minimize energy consumption[END_REF]. Simulations are then conducted based on eight virtual configurations, each of which combines one platform and one processor type. In the simulations, the default value of P io is set to be equivalent to the power used when the CPU runs at the lowest speed, and the performance bound is set as ρ = 3. All of these parameters as well as the values of C, V and λ will be varied in the simulations to evaluate their impact on performance.

B. A different re-execution speed does help

Does using two different speeds indeed help reduce the energy overhead compared to using one speed alone? This section provides affirmative answer to the question above with concrete examples. Specifically, the following tables present the results for the Hera/XScale configuration (similar results are also observed on other platform/processor configurations [START_REF] Benoit | A different re-execution speed can help[END_REF]), with a different bound ρ for every table. For each initial speed σ 1 , the best second speed σ 2 that gives the smallest energy overhead while satisfying the bound ρ is reported, with the corresponding W opt and energy overhead. The overall best speed pair is highlighted in bold. From these tables, we see that in many cases the best solution is composed of two different speeds. In fact, it is possible, for a well-chosen ρ, to have almost any speed pair as the optimal solution (except the pairs with very low speeds). This is because, as ρ decreases, the number of speed pairs that satisfy the performance bound also decreases. Hence, if the energy increases with (σ 1 , σ 2 ), then for any speed pair we could find values of ρ such that it gives the best solution. However, as the speed becomes too slow, the energy will increase as we are likely to have more errors and hence reexecutions. This is shown in the first table, where ρ is big enough such that the pair (0.15, 0.15) gives a feasible solution but has a higher energy overhead than (0.4, 0.4), which is the optimal speed pair. It turns out, in this configuration, that all speed pairs except the ones containing 0.15 can be the optimal solution, depending on the value of ρ specified. This is confirmed by the simulations shown in the next section.

C. Impact of various parameters

This section evaluates the impact of various parameters on the behaviors of the optimal pattern and the associated energy overhead for the Atlas/Crusoe configuration. Due to lack of space, the results for the other platform/processor configurations are omitted here and can be found in the companion research report [START_REF] Benoit | A different re-execution speed can help[END_REF].

1) Impact of C and V : Figure 2 shows that, as the checkpointing time C is increased, the optimal pattern size W also increases till it is constrained by the performance bound, in which case the execution speeds are adapted (first σ 2 and then σ 1 ) to prevent the energy overhead (as well as the pattern size) from growing too fast. In this configuration, the optimal speed pair starts at (0.45, 0.45) when C is small and reaches (0.45, 0.8) when C is increased to 5000 seconds. Compared to the optimal solution that uses only one speed (shown in dotted line), using two speeds achieves up to 35% improvement in the energy overhead. Similar savings are also observed when the verification time V (with respect to the maximum speed) is varied, and the results are shown in Figure 3. In this case, the optimal speed pair stabilizes at (0.6, 0.45) when V is increased to 5000 seconds.

2) Impact of λ and ρ: Figure 4 shows the evolution of the optimal solution as a function of the error rate λ. The optimal pattern size W reduces with increasing λ while the execution speeds increase (first σ 2 and then σ 1 till both reach the maximum value), so that errors can be detected earlier (due to decreased W ) and sooner (due to increased speeds) in the computation. To satisfy a stricter performance bound, i.e., as ρ is reduced, the speeds increase in a similar fashion, as shown in Figure 5. However, for a fixed error rate λ, the optimal pattern size increases with increased σ 1 and decreases with σ 2 , as dictated by Equation [START_REF] Benoit | Efficient checkpoint/verification patterns[END_REF]. In both experiments, we can see that using two execution speeds allows the application to checkpoint less frequently while providing significant energy savings over its one-speed counterpart.

3) Impact of P idle and P io : Figures 6 and7 show, respectively, the impact of the idle power P idle and dynamic I/O power P io on the performance of the optimal solution. In both cases, the optimal energy overhead as well as the pattern size increase with the power consumption. However, the execution speeds increase (σ 1 first and then σ 2 ) with P idle but are not affected by P io . This is because increasing the speeds helps counterbalance the increase in energy overhead as P idle becomes larger (see Equation ( 3)), which is not true for the I/O power since its dominating term does not contain P io . Furthermore, since the optimal re-execution speed σ 2 is (almost always) the same as the initial speed σ 1 , the same performance can be achieved by using one speed alone.

4) Summary:

Overall, the simulations presented in this section demonstrate the benefit of using two execution speeds for the BICRIT problem. The results show that, under various parameter settings, up to 35% of the energy consumption can be saved by using a different re-execution speed while meeting a prescribed performance constraint.

V. EXTENSIONS

In this section, we show how to compute T (W, σ 1 , σ 2 ) and E(W, σ 1 , σ 2 ) when the platform is subject to both fail-stop and silent errors. Unfortunately, the first-order approximation is valid only when σ 2 is not too large with respect to σ 1 , and we are no longer able to provide a general closed-form solution to the BICRIT problem.

A. Dealing with fail-stop and silent errors

Suppose that the platform is subject to two (independent) error sources: in addition to silent errors, whose rate is now denoted as λ s , there are also fail-stop errors (such as process crashes) striking with rate λ f . The probability of having a fail-stop error during T units of time is p f (T ) = 1 -e -λ f T (and that of a silent error remains p s (T ) = 1 -e -λ s T ). We assume that fail-stop errors can occur during computation and verification, but not during checkpointing and recovery. Also, a fail-stop error is detected immediately after striking, so that the time lost since the last checkpoint when executing at speed σ gets smaller on average than W +V σ (see Figure 1(b)). In fact, we can compute its expectation, as shown in the proposition below, which derives T (W, σ 1 , σ 2 ) with two error sources.

T (W, σ 1 , σ 2 ) = C + 1 -e -λ f (W +V )+λ s W σ 1 e λ f (W +V )+λ s W σ 2 R + 1 -e -λ f (W +V )+λ s W σ 1 e λ s W σ 2 V σ 2 1 λ f 1 -e -λ f (W +V ) σ 1 + 1 λ f 1 -e -λ f (W +V )+λ s W σ 1 e λ s W σ 2 e λ f (W +V ) σ 2 -1 .
Proof. The analysis becomes more involved with two error sources. The following gives the recursive equation for computing the expected execution time T (W, σ 1 , σ 2 ):

T (W, σ 1 , σ 2 ) = p f ( W +V σ 1 ) T lost (W +V, σ 1 )+R+T (W, σ 2 , σ 2 ) + 1 -p f ( W +V σ 1 ) W +V σ 1 + p s ( W σ 1 )(R + T (W, σ 2 , σ 2 )) + 1 -p s ( W σ 1 ) C . (7)
Here is the case analysis:

• If a fail-stop error occurs, we lose in expectation T lost (W+ V, σ 1 ) time. Then, we recover and re-execute at speed σ 2 .

• Otherwise, we retrieve the former case analysis with silent errors only (see Propositions 1 and 2). From [START_REF] Hérault | Fault-Tolerance Techniques for High-Performance Computing, Computer Communications and Networks[END_REF], we get that T lost (W +V, σ) = 1 λ f -(W +V )/σ e λ f (W +V )/σ -1

. Solving Equation [START_REF] Bosilca | Algorithm-based fault tolerance applied to high performance computing[END_REF] and rearranging terms lead to the expression of T (W, σ 1 , σ 2 ) as claimed.

The following proposition shows the expected energy consumption E(W, σ 1 , σ 2 ) with two error sources. The proof is similar to that of Proposition 4 and is omitted.

E(W, σ 1 , σ 2 ) = C(P io + P idle ) + 1 -e -λ f (W +V )+λ s W σ 1 e λ f (W +V )+λ s W σ 2 R(P io + P idle ) + 1 -e -λ f (W +V )+λ s W σ 1 e λ s W σ 2 V σ 2 (κσ 3 2 + P idle ) + 1 λ f 1-e -λ f (W +V )+λ s W σ 1 e λ s W σ 2 e λ f (W +V ) σ 2 -1 κσ 3 2 +P idle + 1 λ f 1 -e -λ f (W +V ) σ 1 κσ 3 1 + P idle .

B. Limits of the first-order approximation

Let λ = 1/µ denote the total error rate when accounting from both error sources, and suppose f fraction of the total number of errors are fail-stop and the remaining s = 1 -f fraction are silent. Then, the arrival rates of fail-stop and silent errors are λ f = f λ and λ s = sλ, respectively. After some tedious manipulations, we can derive, from Propositions 4 and 5, first-order approximations for the time and energy overheads, as shown in the following proposition. Proposition 6. With fail-stop and silent errors,

T (W, σ1, σ2) W = C + V /σ1 W + (f + s) σ1σ2 - f 2σ 2 1 λW + (f + s)λ(R + V /σ2) +1-f λV /σ1 σ1 + O(λ 2 W ). (8) E(W, σ1, σ2) W = C(Pio + Pidle) + V (κσ 3 1 + Pidle)/σ1 W + (f + s)(κσ 3 2 + Pidle) σ1σ2 - f (κσ 3 1 + Pidle) 2σ 2 1 λW + (f + s)λ R(Pio + Pidle) + V (κσ 3 2 + Pidle)/σ2 σ1 + (1 -f λV /σ1)(κσ 3 1 + Pidle) σ1 + O(λ 2 W ). (9)
Consider Equation [START_REF] Cappello | Toward exascale resilience: 2014 update[END_REF] and compare it to Equation (2): it still is of the form x + y W + zW + O(λ 2 W ), where x and y are positive constants, but now the sign of z = (f +s)λ σ1σ2 -f λ 2σ 2 1 depends on the ratio σ2 σ1 . If σ2 σ1 < 2(1 + s f ), then z is positive and Equation ( 8) is minimized when W = y z = Θ(λ -1/2 ), just as with silent errors only. But if σ2 σ1 > 2(1 + s f ), then z becomes negative and the time overhead is a strictly decreasing function of W . The minimum would then be achieved for arbitrarily large pattern size W . This is not allowed because, for the Taylor expansion to be valid, we need λW = ε(λ) where ε is a function s.t. lim λ→0 ε(λ) = 0. There is an interesting case limit when σ2 σ1 = 2(1 + s f ), which we will discuss in Section V-C.

Looking at Equation ( 9), we get a similar result: the firstorder approximation leads to a valid solution only when z > 0, which leads to the constraint σ2 σ1 < 2(1 + s f )

κσ 3 2 +Pidle κσ 3 1 +Pidle .
For the sake of simplification, assume that P idle = 0. The latter condition then translates into σ2 σ1 > 2(1

+ s f ) -1/2 .
Altogether, the first-order approximation will lead to a solution to the BICRIT problem if and only if

2(1 + s f ) -1/2 < σ 2 σ 1 < 2(1 + s f ).
While the interval defined by the above condition is never empty, it bounds the ratio σ2 σ1 , thereby limiting the applicability of the first-order approximation.

C. Second-order approximation

Since the first-order approximation has shown its limits, we could envision resorting to the second-order approximation. Unfortunately, despite all our efforts, the second-order approximation cannot help solve the BICRIT problem in the general case. However, the approach enables us to derive the optimal checkpointing period when σ 2 = 2σ 1 with the optimization of expected execution time.

As the issue is caused by fail-stop errors, for the sake of simplification, we assume that s = 0 (hence f = 1, which means no silent errors, only fail-stop errors).

Theorem 2. When considering only fail-stop errors with rate λ, the optimal pattern size W to minimize the time overhead T (W,σ,2σ) W is

W opt = 3 12C λ 2 σ.
This result is really striking: it is the first resilience framework (to the best of our knowledge) in which the optimal checkpointing size W opt is not in the order of the square root of MTBF; instead of having W opt = Θ(λ -1/2 ) as in Young/Daly's formula, we have W opt = Θ(λ -2/3 ) when we re-execute twice faster. We stress that this result is not directly related to the BICRIT problem, but applies to the classical optimization problem of finding the best checkpointing period to minimize the expected execution time.

Proof. We start by deriving the second-order expression of the time overhead given below: Proposition 7. With fail-stop errors only,

T (W, σ 1 , σ 2 ) W = 1 σ 1 + C W + 1 σ 1 σ 2 - 1 2σ 2 1 λW + λR σ 1 + 1 6σ 3 1 - 1 2σ 2 1 σ 2 + 1 2σ 1 σ 2 2 λ 2 W 2 + O(λ 3 W 2 ). (10)
The proof of Proposition 7 is straightforward. We use it with σ 1 = σ and σ 2 = 2σ. The coefficient of W becomes zero in Equation ( 10), and we derive T (W,σ,2σ)

W = 1 σ + C W + λ 2 W 2 24σ 3 + λR σ
while neglecting low-order terms. When differentiating, we see that this expression is minimized for W opt = 3 12C λ 2 σ. VI. CONCLUSION Silent errors and energy consumption are two major challenges towards exascale computing. In this paper, we have shown that using two different speeds (one for the first execution, and one for re-executions due to errors) can lead to significant energy savings while satisfying a performance constraint. For silent errors, we have extended the classical formula of Young/Daly for a divisible load application; by deriving a first-order approximation of the expected execution time and energy consumption, we have obtained a general, closed-form solution to get both the optimal speed pair and the associated optimal checkpointing period. Extensive simulations confirm that having a second speed can indeed help, with up to 35% savings in energy, and that many speed pairs can be potential candidates for the optimal solution, depending on the tightness of the performance bound. All these results shed a new light on the optimal checkpointing period for platforms whose processor speeds can be adjusted through DVFS.

Further work will aim at complementing our initial study for both silent and fail-stop errors. With both error sources, the first-order approximation is valid only when the second speed is not too large with respect to the first one, otherwise we are no longer able to provide a general closed-form solution.

In particular, we have derived a striking result with fail-stop errors when re-execution is twice faster: in this case, the optimal checkpointing period is (surprisingly) in the order of Θ(λ -2/3 ) instead of Θ(λ -1/2 ) as in the Young/Daly formula. It seems that new methods are needed to capture the general case with two error sources and arbitrary speed pairs.

Figure 2 .Figure 3 .

 23 Figure 2. The optimal solution (speed pair, pattern size, and energy overhead) as a function of the checkpointing time C in Atlas/Crusoe configuration.

Figure 4 .Proposition 4 .

 44 Figure 4. The optimal solution (speed pair, pattern size, and energy overhead) as a function of the error rate λ in Atlas/Crusoe configuration.

Proposition 5 .

 5 With fail-stop and silent errors,

Figure 5 .Figure 6 .Figure 7 .

 567 Figure 5. The optimal solution (speed pair, pattern size, and energy overhead) as a function of the performance bound ρ in Atlas/Crusoe configuration.

Table I .

 I Platform parameters (verification time is w.r.t. full speed).

	Platform	λ (error/second)	C (second)	V (second)
	Hera		3.38e-6	300	15.4
	Atlas		7.78e-6	439	9.1
	Coastal		2.01e-6	1051	4.5
	Coastal SSD		2.01e-6	2500	180.0
		Table II. Processor parameters.
	Processor		Normalized speeds	P (σ) (mW)
	Intel Xscale		0.15, 0.4, 0.6, 0.8, 1	1550σ 3 + 60
	Transmeta Crusoe	0.45, 0.6, 0.8, 0.9, 1	5756σ 3 + 4.4

Acknowledgments: This research was funded in part by the European project SCoRPiO, by the LABEX MILYON (ANR-10-LABX-0070) of Université de Lyon, within the program "Investissements d'Avenir" (ANR-11-IDEX-0007) operated by the French National Research Agency (ANR), and by the PIA ELCI project. Yves Robert is with Institut Universitaire de France.