Guillaume Aupy

Yves Robert

Dounia Zaidouni

Checkpointing strategies with prediction windows

Keywords: Fault-tolerance, checkpointing, prediction, algorithms, model, exascale

This paper deals with the impact of fault prediction techniques on checkpointing strategies. We suppose that the fault-prediction system provides prediction windows instead of exact predictions, which dramatically complicates the analysis of the checkpointing strategies. We propose a new approach based upon two periodic modes, a regular mode outside prediction windows, and a proactive mode inside prediction windows, whenever the size of these windows is large enough. We are able to compute the best period for any size of the prediction windows, thereby deriving the scheduling strategy that minimizes platform waste. In addition, the results of this analytical evaluation are nicely corroborated by a comprehensive set of simulations, which demonstrate the validity of the model and the accuracy of the approach.

Protocoles de checkpoint et intervalles de prédiction de fautes

Résumé : Ce travail considère l'impact des techniques de prédiction de fautes sur les stratégies de protocoles de sauvegarde de points de reprise (checkpoints) et de redémarrage. Nous supposons que le système de prédiction de faute fournit, en plus de ses caractéristiques, rappel (taux de pannes prévues sur nombre total de pannes) et précision (taux de vraies pannes parmi le nombre total de pannes annoncées), des intervalles dans lesquels les fautes risquent d'arriver plutôt qu'une date exacte, ce qui complique énormément l'analyse des stratégies de checkpoint. Nous proposons une nouvelle approche qui se base sur deux modes périodiques, le mode régulier (en dehors des fenêtres de prédiction), et le mode proactif (à l'intérieur des fenêtres de prédiction), quand ces fenêtres sont suffisamment larges. Nous sommes capables de calculer la période optimale pour n'importe quelle taille de fenêtre de prédiction, dérivant ainsi la stratégie d'ordonnancement optimale pour minimiser les pertes. Enfin, ces résultats théoriques sont corroborés par un ensemble complet de simulations, ce qui démontre la validité du modèle et la précision de notre approche.

Mots-clés : Tolérance aux pannes, checkpoint, prédiction, algorithmes, modèle, exascale [START_REF] Young | A first order approximation to the optimum checkpoint interval[END_REF]

Introduction

In this paper, we assess the impact of fault prediction techniques on checkpointing strategies. We assume to have jobs executing on a platform subject to faults, and we let µ be the mean time between faults (MTBF) of the platform. In the absence of fault prediction, the standard approach is to take periodic checkpoints, each of length C, every period of duration T . In steady-state utilization of the platform, the value T opt of T that minimizes the expected waste of resource usage due to checkpointing is easily approximated as T opt = √ 2µC + C, or T opt = 2(µ + R)C + C (where R is the duration of the recovery). The former expression is the well-known Young's formula [START_REF] Young | A first order approximation to the optimum checkpoint interval[END_REF], while the latter is due to Daly [START_REF] Daly | A higher order estimate of the optimum checkpoint interval for restart dumps[END_REF].

Assume now that some fault prediction system is available. Such a system is characterized by two critical parameters, its recall r, which is the fraction of faults that are indeed predicted, and its precision p, which is the fraction of predictions that are correct (i.e., correspond to actual faults). In the simple case where predictions are exact-date predictions, several recent papers [START_REF] Gainaru | Fault prediction under the microscope -a closer look into hpc systems[END_REF][START_REF] Aupy | Checkpointing algorithms and fault prediction[END_REF] have independently shown that the optimal checkpointing period becomes T opt = 2µC 1 -r . This latter expression is valid only when µ is large enough and can be seen as an extension of Young's formula where µ is replaced by µ 1-r : faults are replaced by non-predicted faults, and the overhead due to false predictions is negligible. A more accurate expression for the optimal checkpointing period is available in [START_REF] Aupy | Checkpointing algorithms and fault prediction[END_REF].

This paper deals with the realistic case (see [START_REF] Yu | Practical online failure prediction for Blue Gene/P: Period-based vs event-driven[END_REF][START_REF] Liang | Failure prediction in IBM BlueGene/L event logs[END_REF] and Section 5) where the predictor system does not provide exact dates for predicted events, but instead provides prediction windows. A prediction window is a time interval of length I during which the predicted event is likely to happen. Intuitively, one is more at risk during such an interval than in the absence of any prediction, hence the need to checkpoint more frequently. But with which period? And what is the size of the prediction window above which it proves worthwhile to use a different (smaller) checkpointing period?

The main objective of this paper is to provide a quantitative answer to these questions. Our key contributions are the following: (i) The design of several checkpointing policies that account for the different sizes of prediction windows; (ii) The analytical characterization of the best policy for each set of parameters; and (iii) The validation of the theoretical results via extensive simulations, for both Exponential and Weibull failure distributions. It turns out that the analysis of the waste is dramatically more complicated than when using exact-date predictions [START_REF] Gainaru | Fault prediction under the microscope -a closer look into hpc systems[END_REF][START_REF] Aupy | Checkpointing algorithms and fault prediction[END_REF].

The rest of the paper is organized as follows. First we detail the framework in Section 2. In Section 3 we describe the new checkpointing policies with prediction windows, and show how to compute the optimal checkpointing periods that minimize the platform waste. Section 4 is devoted to simulations. Section 5 provides a brief overview of related work. Finally, we present concluding remarks in Section 6.

Framework

Checkpointing strategy

We consider a platform subject to faults. Our work is agnostic of the granularity of the platform, which may consist either of a single processor, or of several processors that work concurrently and use coordinated checkpointing. Checkpoints are taken at regular intervals, or periods, of length T . We denote by C the duration of a checkpoint; by construction, we must enforce that C ≤ T . Useful work is done only during T -C units of time for every period of length T , if no fault occurs. Hence the waste due to checkpointing in a fault-free execution is Waste = C T . In the following, the waste always denote the fraction of time that the platform is not doing useful work.

When a fault strikes the platform, the application is lacking some resource for a certain period of time of length D, the downtime. The downtime accounts for software rejuvenation (i.e., rebooting [START_REF] Kolettis | Software rejuvenation: Analysis, module and applications[END_REF][START_REF] Castelli | Proactive management of software aging[END_REF]) or for the replacement of the failed hardware component by a spare one. Then, the application recovers from the last checkpoint. R denotes the duration of this recovery time.

Fault predictor

A fault predictor is a mechanism that is able to predict that some faults will take place, within some time-interval window. In this paper, we assume that the predictor is able to generate its predictions early enough so that a proactive checkpoint can indeed be taken before or during the event. A first proactive checkpoint will typically be taken just before the beginning of the prediction window, and possibly several other ones will be taken inside the prediction window, if its size I is large enough.

Proactive checkpoints may have a different length C p than regular checkpoints of length C. In fact there are many scenarios. On the one hand, we may well have C p > C in scenarios where regular checkpoints are taken at timesteps where the application memory footprint is minimal [START_REF] Hong | On the choice of checkpoint interval using memory usage profile and adaptive time series analysis[END_REF]; on the contrary, proactive checkpoints are taken according to predictions that can take place at arbitrary instants. On the other hand, we may have C p < C in other scenarios [START_REF] Zheng | A practical failure prediction with location and lead time for Blue Gene/P[END_REF], e.g., when the prediction is localized to a particular resource subset, hence allowing for a smaller volume of checkpointed data. To keep full generality, we deal with two checkpoint sizes in this paper: C for periodic checkpoints, and C p for proactive checkpoints (those taken upon predictions).

The accuracy of the fault predictor is characterized by two quantities, the recall and the precision. The recall r is the fraction of faults that are predicted while the precision p is the fraction of fault predictions that are correct. Traditionally, one defines three types of events: (i) True positive events are faults that the predictor has been able to predict (let True P be their number); (ii) False positive events are fault predictions that did not materialize as actual faults (let False P be their number); and (iii) False negative events are faults that were not predicted (let False N be their number). With these definitions, we have r = True P True P +False N and p = True P True P +False P . In the literature, the lead time is the interval between the date at which the prediction is made available, and the predicted date of failure (or, more precisely, the beginning of the prediction window). However, because we do RR n°8239 not consider pro-active actions with different durations (they all have length C p ), we point out that the distribution of these lead times is irrelevant to our problem. Indeed, either we have the time to take a proactive action before the failure strikes or not. Therefore, if a failure strikes less than C p seconds after the prediction is made available, the prediction was useless. In other words, predicted failures that come too early to enable any proactive action should be classified as unpredicted faults, leading to a smaller value of the predictor recall and to a shorten prediction window. Therefore, in the following, we consider, without loss of generality, that all predictions are made available C p seconds before the beginning of the prediction window.

Fault rates

The key parameter is µ, the mean time between faults (MTBF) of the platform. If the platform is made of N components whose individual MTBF is µ ind , then µ = µ ind N . This result is true regardless of the fault distribution law [START_REF] Aupy | Checkpointing algorithms and fault prediction[END_REF]. In addition to µ, the platform MTBF, let µ P be the mean time between predicted events (both true positive and false positive), and let µ N P be the mean time between unpredicted faults (false negative). Finally, we define the mean time between events as µ e (including all three event types). The relationships between µ, µ P , µ N P , and µ e are the following:

• Rate of unpredicted faults: 1

µ N P = 1-r µ , since 1 -r is the fraction of faults that are unpredicted;

• Rate of predicted faults: r µ = p µ P , since r is the fraction of faults that are predicted, and p is the fraction of fault predictions that are correct;

• Rate of events: 1 µe = 1 µ P + 1 µ N P , since events are either predictions (true or false), or unpredicted faults.

Checkpointing strategies

In this section, we introduce the new checkpointing strategies, and we determine the waste that they induce. We then proceed to computing the optimal period for each strategy.

Description of the different strategies

We consider the following general scheme:

1. While no fault prediction is available, checkpoints are taken periodically with period T ; 2. When a fault is predicted, we decide whether to take the prediction into account or not. This decision is randomly taken: with probability q, we trust the predictor and take the prediction into account, and, with probability 1 -q, we ignore the prediction; 3. If we decide to trust the predictor, we use various strategies, depending upon the length I of the prediction window. Before describing the different strategies in the situation (3), we point out that the rationale for not always trusting the predictor is to avoid taking useless RR n°8239 checkpoints too frequently. Intuitively, the precision p of the predictor must be above a given threshold for its usage to be worthwhile. In other words, if we decide to checkpoint just before a predicted event, either we will save time by avoiding a costly re-execution if the event does correspond to an actual fault, or we will lose time by unduly performing an extra checkpoint. We need a larger proportion of the former cases, i.e., a good precision, for the predictor to be really useful. Now, to describe the strategies used when we trust a prediction (situation (3)), we define two modes for the scheduling algorithm: Regular: This is the mode used when no fault prediction is available, or when a prediction is available but we decide to ignore it (with probability 1 -q). In regular mode, we use periodic checkpointing with period T R . Intuitively, T R corresponds to the checkpointing period T of Section 2.1. Proactive: This is the mode used when a fault prediction is available and we decide to trust it, a decision taken with probability q. Consider such a trusted prediction made with the prediction window [t 0 , t 0 + I]. Several strategies can be envisioned: (1) Instant, for Instantaneous-The first strategy is to ignore the time-window and to execute the same algorithm as if the predictor had given an exact date prediction at time t 0 . The algorithm interrupts the current period (of scheduled length T R ), checkpoints during the interval [t 0 -C p , t 0 ], and then returns to regular mode: at time t 0 , it resumes the work needed to complete the interrupted period of the regular mode.

(2) NoCkptI, for No checkpoint during prediction window-The second strategy is intended for a short prediction window: instead of ignoring it, we acknowledge it, but make the decision not to checkpoint during it. As in the first strategy, the algorithm interrupts the current period (of scheduled length T R ), and checkpoints during the interval [t 0 -C p , t 0 ]. But here, we return to regular mode only at time t 0 + I, where we resume the work needed to complete the interrupted period of the regular mode. During the whole length of the time-window, we execute work without checkpointing, at the risk of losing work if a fault indeed strikes. But for a small value of I, it may not be worthwhile to checkpoint during the prediction window (if at all possible, since there is no choice if I < C p ).

(3) WithCkptI, for With checkpoints during prediction window-The third strategy is intended for a longer prediction window and assumes that C p ≤ I: the algorithm interrupts the current period (of scheduled length T R ), and checkpoints during the interval [t 0 -C p , t 0 ], but now also decides to take several checkpoints during the prediction window. The period T P of these checkpoints in proactive mode will presumably be shorter than T R , to take into account the higher fault probability. In the following, we analytically compute the optimal number of such periods. But we take at least one period here, hence one checkpoint, which implies C p ≤ I. We return to regular mode either right after the fault strikes within the time window [t 0 , t 0 + I], or at time t 0 + I if no actual fault happens within this window. Then, we resume the work needed to complete the interrupted period of the regular mode. The third strategy is the most complex to describe, and the complete behavior of the corresponding scheduling algorithm is shown in Algorithm 1.

Note that, for all strategies, we insert some additional work for the particular case where there is not enough time to take a checkpoint before entering proactive mode (because a checkpoint for the regular mode is currently on-going).

We account for this work as idle time in the expression of the waste, to ease the analysis. Our expression of the waste is thus an upper bound.

Algorithm 1: WithCkptI.

Strategy WithCkptI

In this section we evaluate the execution time under heuristic WithCkptI.

To do so, we partition the whole execution into time intervals defined by the presence or absence of events. An interval starts and ends with either the completion of a checkpoint or of a recovery (after a failure). To ease the analysis, we make a simplifying hypothesis: we assume that at most one event, failure or prediction, occurs within any interval of length T R + I + C p . In particular, this implies that a prediction or an unpredicted fault always take place during the regular mode. We list below the four types of intervals, and evaluate their respective average length, together with the average work completed during each of them (see Table 1 for a summary):

1. Two consecutive regular checkpoints with no intermediate events.

The time elapsed between the completion of the two checkpoints is exactly T R , and the work done is exactly T R -C. 2. Unpredicted fault. Recall that, because of the simplifying hypothesis, the fault happens in regular mode. Because instants where the fault strikes and where the last checkpoint was taken are independent, on average the fault strikes at time T R /2. A downtime of length D and a recovery of length R occur before the interval completes. There is no work done. 3. False prediction. Recall that it happens in regular mode. There are two cases: (a) Taken into account. This happens with probability q. The interval lasts T R + C p + I, since we take a proactive checkpoint and spend the time I in proactive mode. The work done is (T R -C) + (I -I TP C p ). (b) Not taken into account. This happens with probability 1-q. The interval lasts T R and the work done is T R -C. Considering both cases with their probabilities, the average time spent is equal to: q(T R + C p + I) + (1 -q)T R = T R + q(C p + I). The average work done is: q(T R -C + I -I TP C p ) + (1 -q)(T R -Cr) = T R -C + q(I -I TP C p ). 4. True prediction. Recall that it happens in regular mode. There are two cases: (a) Taken into account. Let E (f ) I be the average time at which a fault occurs within the prediction window (the time at which the fault strikes is certainly correlated to the starting time of the prediction window; E (f ) I may not be equal to I/2). Up to time E (f ) I , we work and checkpoint in proactive mode, with period T P . In addition, we take a proactive checkpoint right before the start of the prediction window. Then we spend the time E The time interval has duration T R /2 + D + R, and there is no work done. Overall the time spent is q(T R +C p +E (f )

I +D +R)+(1-q)(T R /2+D +R),
and the work done is q(T R -C + (

E (f ) I TP -1)(T P -C p )) + (1 -q)0.
So far, we have evaluated the length, and the work done, for each of the interval types. We now estimate the expectation of the number of intervals of each type. Consider the intervals defined by an event whose mean time between occurrences is λ. On average, during a time T , there will be T /λ such intervals. Due to

RR n°8239

Mode Number of intervals Time spent Work done (1) 1 presents the estimation of the number of intervals of each type.

w 1 T R T R -C (2) w 2 = TimeFinal µNP T R /2 + D + R 0 (3) w 3 = (1-p)TimeFinal µP T R + q(I + C p ) T R -C + q(I -I TP C p ) (4) w 4 = pTimeFinal µP q(T R + E (f ) I + C p ) q T R -C + E (f ) I TP -1 (T P -C p ) +(1 -q)T R /2 + D + R
We want to estimate the total execution time. To estimate the time spent within intervals of a given type, we multiply the expectation of the number of intervals of that type by the expectation of the time spent in each of them. Of course, multiplying expectations is correct only if the corresponding random variables are independent. Nevertheless, we hope that this will lead us to a good approximation of the expected execution time. We will assess the quality of the approximation through simulations in Section 4. With our assumptions we have:

Time Final = w 1 × T R + w 2 T R 2 + D + R + w 3 (T R + q(I + C p )) + w 4 q(T R + E (f ) I + C p ) + (1 -q) T R 2 + D + R (1)
We use the same line of reasoning to compute the overall amount of work done, that must be equal, by definition, to Time base , the execution time of the application without any overhead:

Time base = w 1 (T R -C) + w 2 × 0 + w 3 T R -C + q I - I T P C p + w 4 q T R -C + E (f ) I T P -1 (T P -C p ) (2)
This equation gives the value of w 1 as a function of the other parameters.

Looking at Equations ( 1) and ( 2), and at the values of w 2 , w 3 , and w 4 , we remark that Time Final can be rewritten as a function of q, as follows:

Time Final = αTime base + βTime Final + qγTime Final , that is Time Final = α 1-β-qγ
Time base , where neither α, nor β, nor γ depend on q. With a simple differentiation of Time Final with respect to q, we obtain that Time Final is either increasing or decreasing with q, depending on the sign of γ. Consequently, in an optimal solution, either q = 0 or q = 1. This (somewhat unexpected) conclusion is that the predictor should sometimes be always trusted, and sometimes never, but no in-between value for q will do a better job. Thus we can now focus on the two functions Time Final , the one when q = 0 (Time {0} Final ), and the one when q = 1 (Time {1} Final ). From Table 1 and Equations ( 1) and ( 2), one can easily see that

Time {0} Final = T R T R -C Time base + Time {0} Final µ T R 2 + D + R , i.e., that RR n°8239 1 - C T R 1 - T R /2 + D + R µ Time {0} Final = Time base (3)
This is exactly the equation from [START_REF] Aupy | Checkpointing algorithms and fault prediction[END_REF] in the case of exact-date predictions that are never taken into account (a good sanity check!). When q = 1, we have:

Time {1} Final = Time base T R T R -C - Time {1} Final µ P T R T R -C (T R -C)+(1-p) I - I T P C p +p E (f ) I T P -1 (T P -C p ) + Time {1} Final µ N P T R 2 + D + R + (1 -p)Time {1} Final µ P (T R + I + C p ) + pTime {1} Final µ P T R + C p + E (f ) I + D + R
After a little rewriting we obtain:

Time base Time {1} Final = r pµ 1 - C p T P (1 -p)I + p E (f ) I -T P + 1 - C T R 1 - 1 pµ p(D + R) + rC p + (1-r)p T R 2 + r (1-p)I +pE (f ) I
Finally, the waste is equal by definition to Time Final -Time base Time Final

. Therefore, we have:

Waste = 1 - r pµ 1 - C p T P (1 -p)I + p E (f ) I -T P -1- C T R 1- 1 pµ p(D + R)+rC p +(1-r)p T R 2 +r (1-p)I +pE (f ) I (4)

Waste minimization

When q = 0, the optimal period can readily be computed from Equation (3) and we derive that the optimal period is 2(µ -(D + R))C. This defines a periodic policy we call RFO, for Refined First-Order approximation. We now minimize the waste of the strategy where q = 1. In order to compute the optimal value for T P , we identify the fraction of the waste in Equation ( 4) that depends on T P . We can rewrite Equation (4) as:

Waste {1} = α + r pµ (1 -p) I + pE (f ) I C p T P + pT P
where α does not depend on T P . The waste is thus minimized when T P is equal to

T extr P = (1-p)I+pE (f ) I Cp p
. Note that we always have to enforce that T extr P is larger than C p and does not exceed I, and we may have to round its values accordingly in some extreme cases.

In order to compute the optimal value for T R , we identify the fraction of the waste in Equation ( 4) that depends on T R . We can rewrite Equation (4) as:

Waste {1} = β + C T R 1- 1 pµ p(D+R)+r C p +(1-p) I +pE (f ) I + 1-r µ T R 2 (5)
where β does not depend on T R because T opt P does not depend on T R . Therefore,

Waste {1} is minimized when T R is equal to T extr R = 2C pµ -p(D + R) + r C p + (1 -p) I + pE (f ) I p(1 -r) (6)
Recall that we must always enforce that T extr R is always greater than C. One can note that when r = 0, this means that none of the prediction predicts an actual fault, and we obtain the same period than without a predictor. Finally, if we assume that, on average, fault strikes at the middle of the prediction window, i.e., E

(f ) I = I
2 , we obtain simplified values:

T extr P = (2 -p)IC p p and T extr R = 2C pµ -p(D + R) + r C p + 1 -p 2 I p(1 -r)

Strategy NoCkptI

In this section we evaluate the execution time under heuristic NoCkptI. The analysis is rather similar to that of WithCkptI, the only differences being, obviously, in the presence of true and false predictions:

3. False prediction. There are two cases: (a) Taken into account. This happens with probability q. The interval lasts T R + C p + I, since we take a proactive checkpoint and spend the time I in proactive mode (here, working without checkpointing). The work done is (T R -C) + I. (b) Not taken into account. This happens with probability 1-q. The interval lasts T R and the work done is T R -C. Considering both cases with their probabilities, the average time spent is equal to: The time interval has duration T R /2 + D + R, and there is no work done.

q(T R + C p + I) + (1 -q)T R = T R + q(C p + I). The average work done is: q(T R -C + I) + (1 -q)(T R -Cr) = T R -C + qI.

RR n°8239

Mode Number of intervals Time spent Work done (1)

w 1 T R T R -C (2) w 2 = Time Final µ N P T R /2 + D + R 0 (3) w 3 = (1-p)Time Final µ P T R + q(I + C p ) T R -C + qI (4) w 4 = pTime Final µ P q(T R + E (f ) I + C p ) q (T R -C) +(1 -q)T R /2 + D + R Table 2: Summary of the different types of interval for NoCkptI.
Overall the time spent is q(T R +C p +E (f )

I +D +R)+(1-q)(T R /2+D +R),
and the work done is q(T R -C) + (1 -q)0. So far, we have evaluated the length, and the work done, for each of the interval types. We now estimate the expectation of the number of intervals of each type as we did for WithCkptI. Table 2 presents the estimation of the number of intervals of each type.

We estimate the total execution time as for WithCkptI. The formula is the exact same function of w 1 , w 2 , w 3 , and w 4 (but the values of there four parameters will change as the average work done during some of the types of intervals changes):

Time Final = w 1 × T R + w 2 T R 2 + D + R + w 3 (T R + q(I + C p )) + w 4 q(T R + E (f ) I + C p ) + (1 -q) T R 2 + D + R (7)
We use the same line of reasoning as previously to compute the overall amount of work done:

Time base = w 1 (T R -C) + w 2 × 0 + w 3 (T R -C + qI) + w 4 (q (T R -C)) (8)
This equation gives the value of w 1 as a function of the other parameters. As for WithCkptI, one can easily show that in an optimal solution, either q = 0 or q = 1. Thus we can now focus on the two functions Time Final , the one when q = 0 (Time {0} Final ), and the one when q = 1 (Time

{1}

Final ). From Table 2 and Equations ( 7) and ( 8), one can easily see that

Time {0} Final = T R T R -C Time base + Time {0} Final µ T R 2 + D + R , i.e., that 1 - C T R 1 - T R /2 + D + R µ Time {0} Final = Time base (9)
This is exactly the equation from [START_REF] Aupy | Checkpointing algorithms and fault prediction[END_REF] in the case of exact-date predictions that are never taken into account, what we had already retrieved with WithCkptI RR n°8239

(same sanity check!). When q = 1, we have:

Time {1} Final = Time base T R T R -C - Time {1} Final µ P T R T R -C ((T R -C) + (1 -p)I) + Time {1} Final µ N P T R 2 + D + R + (1 -p)Time {1} Final µ P (T R + I + C p ) + pTime {1} Final µ P T R + C p + E (f ) I + D + R
After a little rewriting we obtain:

Time base Time {1} Final = r pµ (1 -p)I + 1 - C T R 1- 1 pµ p(D + R)+rC p +(1-r)p T R 2 +r (1-p)I +pE (f ) I
Finally, the waste is equal by definition to Time Final -Time base Time Final

. Therefore, we have:

Waste = 1 - r pµ (1 -p)I -1- C T R 1- 1 pµ p(D + R)+rC p +(1-r)p T R 2 +r (1 -p)I +pE (f ) I (10)

Waste minimization

When q = 0, the optimal value for T R is obviously the same than the one we computed for WithCkptI in the case q = 0. We now minimize the waste of the strategy where q = 1. In order to compute the optimal value for T R , we identify the fraction of the waste in Equation ( 10) that depends on T R . We can rewrite Equation [START_REF] Zheng | A practical failure prediction with location and lead time for Blue Gene/P[END_REF] as:

Waste {1} = β+ C T R 1- 1 pµ p(D+R) + r C p + (1-p) I + pE (f ) I + 1-r µ T R 2
where β does not depend on T R . This equation is identical to Equation ( 5) and therefore the value of T R that minimizes the waste is T extr R , the value given by Equation (6).

Strategy Instant

In this section we evaluate the execution time under heuristic Instant. The analysis is very similar to that of NoCkptI. Indeed, we only focus to the differences between the performance of Instant and WithCkptI. The differences happening, obviously, only in the presence of true and false predictions:

3. False prediction. There are two cases: (a) Taken into account. This happens with probability q. The interval lasts T R + C p , since we fallback to regular mode as soon as the proactive checkpoints completes. The work done is T R -C. (b) Not taken into account. This happens with probability 1-q. The interval lasts T R and the work done is T R -C. Considering both cases with their probabilities, the average time spent is equal to: be the average time at which a fault occurs within the prediction window. We take a proactive checkpoint right before the start of the prediction window. Then we fallback to the regular mode. After a time E (f ) I the fault strikes. Depending on the size I of the prediction window, and of when the prediction started after the completion of the last regular checkpoint three scenarios can happen. Either the fault strikes while the heuristic is still trying to complete the work of size T R -C, or it strikes while the heuristic is trying to take the regular checkpoint after that work, or it strikes after that regular checkpoint was completed. We overestimate the time lost by assuming that we are in one of the two former cases, because these are the cases that maximizes the amount of work destroyed by a strike. (In some way, this is equivalent to assuming that I is very small with respect to T R .) The predicted fault and the completion time of the last regular checkpoint are independent events. Therefore, on average the fault strikes at time T R /2. After the fault strikes, the downtime and the recovery we complete the period struck by the fault. Then, the interval lasts T R +C p +E The time interval has duration T R /2 + D + R, and there is no work done. Overall the time spent is q(T R +C p +E (f )

Mode Number of intervals Time spent Work done (1) w 1 T R T R -C (2) w 2 = Time Final µ N P T R /2 + D + R 0 (3) w 3 = (1-p)Time Final µ P T R + qC p T R -C (4) w 4 = pTime Final µ P q(T R + E (f ) I + C p ) q (T R -C) +(1 -q)T R /2 + D + R
q(T R + C p ) + (1 -q)T R = T R + qC p . The average work done is: q(T R -C) + (1 -q)(T R -Cr) = T R -C.
I +D +R)+(1-q)(T R /2+D +R),
and the work done is q(T R -C). So far, we have evaluated the length, and the work done, for each of the interval types. We estimate the expectation of the number of intervals of each type as we did for WithCkptI and for NoCkptI. Table 3 presents the estimation of the number of intervals of each type.

RR n°8239

We estimate the total execution time as for WithCkptI and NoCkptI:

Time Final = w 1 × T R + w 2 T R 2 + D + R + w 3 (T R + qC p ) + w 4 q(T R + E (f ) I + C p ) + (1 -q) T R 2 + D + R (11)
We use the same line of reasoning as previously to compute the overall amount of work done:

Time base = w 1 (T R -C) + w 2 × 0 + w 3 (T R -C) + w 4 (q (T R -C)) (12)
This equation gives the value of w 1 as a function of the other parameters.

As with WithCkptI and NoCkptI, one can easily show that in an optimal solution, either q = 0 or q = 1. Thus we can now focus on the two functions Time Final , the one when q = 0 (Time

{0}

Final ), and the one when q = 1 (Time

{1}

Final ). From Table 3 and Equations ( 11) and ( 12), one can easily see that

Time {0} Final = T R T R -C Time base + Time {0} Final µ T R 2 + D + R , i.e., that 1 - C T R 1 - T R /2 + D + R µ Time {0} Final = Time base (13)
This is exactly the equation from [START_REF] Aupy | Checkpointing algorithms and fault prediction[END_REF] in the case of exact-date predictions that are never taken into account, what we had already remarked with WithCkptI and NoCkptI (yet another good sanity check!). When q = 1, we have:

Time {1} Final = Time base T R T R -C - Time {1} Final µ P T R + Time {1} Final µ N P T R 2 + D + R + (1 -p)Time {1} Final µ P (T R + C p ) + pTime {1} Final µ P T R + C p + E (f ) I + D + R
After a little rewriting we obtain:

Time base Time {1} Final = 1 - C T R 1- 1 pµ p(D + R)+rC p +(1-r)p T R 2 +prE (f ) I
Finally, the waste is equal by definition to Time Final -Time base Time Final

. Therefore, we have:

Waste = 1 -1- C T R 1- 1 pµ p(D + R)+rC p +(1-r)p T R 2 +prE (f ) I (14)

Waste minimization

When q = 0, the optimal value for T R is obviously the same than the one we computed for WithCkptI and for NoCkptI in the case q = 0. We now minimize the waste of the strategy where q = 1. In order to compute the optimal value for T R , we identify the fraction of the waste in Equation ( 14) that depends on T R . We can rewrite Equation ( 14) as:

Waste {1} = β + C T R 1- 1 pµ p(D+R) + rC p + prE (f ) I + 1-r µ T R 2
where β does not depend on T R . Therefore, the value of T R that minimizes the waste is T extr R , where

T extr R = 2C pµ -p(D + R) + rC p + prE (f ) I p(1 -r)
Again, recall that we must always enforce that T extr R is always greater than C. Finally, if we assume that, on average, fault strikes at the middle of the prediction window, i.e., E

(f ) I = I
2 , we have:

T extr R = 2C pµ -p(D + R) + rC p + pr I 2 p(1 -r)

Simulation results

We start by presenting the simulation framework (Section 4.1). Then we report results using the characteristics of two fault predictors from the literature (Section 4.2).

Simulation framework

In order to validate the model, we have instantiated it with several scenarios. The experiments use parameters that are representative of current and forthcoming large-scale platforms [START_REF] Cappello | Preventive migration vs. preventive checkpointing for extreme scale supercomputers[END_REF][START_REF] Ferreira | Evaluating the Viability of Process Replication Reliability for Exascale Systems[END_REF]. We take C = R = 600 seconds, and D = 60 seconds. We consider three scenarios where proactive checkpoints are (i) exactly as expensive as periodic checkpoints (C p = C); (ii) ten times cheaper (C p = 0.1C); and (iii) two times more expensive (C p = 2C). The individual (processor) MTBF is µ ind = 125 years, and the total number of processors N varies from N = 2 16 = 16, 384 to N = 2 19 = 524, 288, so that the platform MTBF µ varies from µ = 4, 010 min (about 2.8 days) down to µ = 125 min (about 2 hours). For instance the Jaguar platform, with N = 45, 208 processors, is reported to have experienced about one fault per day [START_REF] Zheng | A scalable double in-memory checkpoint and restart scheme towards exascale[END_REF], which leads to µ ind = 45,208 365 ≈ 125 years. The application size is set to Time base = 10, 000 years/N.

We use Maple to analytically compute and plot the optimal value of the waste for the three prediction-aware policies, Instant, NoCkptI, and WithCkptI, for the prediction-ignoring policy RFO (corresponding to the case q = 0), and for the reference heuristic Daly (Daly's [START_REF] Daly | A higher order estimate of the optimum checkpoint interval for restart dumps[END_REF] periodic policy). In order to check the accuracy of our model, we have compared the analytical results with results obtained with a discrete-event simulator. The simulation engine generates a random trace of faults, parameterized either by an Exponential fault distribution or by Weibull distribution laws with shape parameter 0.5 or 0.7. Note that Exponential faults are widely used for theoretical studies, while Weibull faults are representative of the behavior of real-world platforms [START_REF] Heath | Improving cluster availability using workstation validation[END_REF][START_REF] Schroeder | A large-scale study of failures in highperformance computing systems[END_REF][START_REF] Heien | Modeling and tolerating heterogeneous failures in large parallel systems[END_REF]. In both cases, the distribution is scaled so that its expectation corresponds to the platform MTBF µ. With probability r, we decide if a fault is predicted or not. The simulation engine also generates a random trace of false predictions, whose distribution is identical to that of the first trace (in Figures 8 through 13, we also consider the case where false predictions are generated according to a uniform distribution; results are quite similar). This second distribution is scaled so that its expectation is equal to µ P 1-p = pµ r(1-p) , the inter-arrival time of false predictions. Finally, both traces are merged to produce the final trace including all events (true predictions, false predictions, and non predicted faults). Each reported value is the average over 100 randomly generated instances.

In the simulations, we compare the five checkpointing strategies listed above. To assess the quality of each strategy, we compare it with its BestPeriod counterpart, defined as the same strategy but using the best possible period T R . This latter period is computed via a brute-force numerical search for the optimal period. Altogether, there are four BestPeriod heuristics, one for each of the three variants with prediction, and one for the case where we ignore predictions, which corresponds to both Daly and RFO. Altogether we have a rich set of nine heuristics, which enables us to comprehensively assess the actual quality of the proposed strategies. Note that for computer algebra plots, obviously we do not need BestPeriod heuristics, since each period is already chosen optimally from the equations.

We experiment with two predictors from the literature: one accurate predictor with high recall and precision [START_REF] Yu | Practical online failure prediction for Blue Gene/P: Period-based vs event-driven[END_REF], namely with p = 0.82 and r = 0.85, and another predictor with more limited recall and precision [START_REF] Zheng | A practical failure prediction with location and lead time for Blue Gene/P[END_REF], namely with p = 0.4 and r = 0.7. In both cases, we use five different prediction windows, of size I = 300, 600, 900, 1200, and 3000 seconds. Figures 2 through 7 show the average waste degradation of the nine heuristics for both predictors, as a function of the number of processors N . We draw the plots as a function of the number of processors N rather than of the platform MTBF µ = µ ind /N , because it is more natural to see the waste increase with larger platforms; however, this work is agnostic of the granularity of the processors and intrinsically focuses on the impact of the MTBF on the waste.

Analysis of the results

We start with a preliminary remark: when the graphs for Instant and With-CkptI cannot be seen in the figures, this is because their performance is identical to that of NoCkptI, and their respective graphs are superposed.

We first compare the analytical results, plotted by the Maple curves, to the simulations results. There is a good correspondence between the analytical curves and the simulations, especially those using an Exponential distribution of failures. However, the larger the platform (or the smaller the MTBF), the less realistic our assumption that no two events happen during an interval of length T R + I + C p , and the analytical models become less accurate for predictionaware heuristics. Therefore, the analytical results are overly pessimistic in the most failure-prone platforms. Also, recall that an exponential law is a Weibull law of shape parameter 1. Therefore, the further the distribution of failures is from an exponential law, the larger the difference between analytical results and RR n°8239 simulated ones. However, in all cases, the analytical results are able to predict the general trends.

A second assessment of the quality of our analysis comes from the BestPeriod variants of our heuristics. When predictions are not taken into account, Daly, and to a lesser extent RFO, are not close to the optimal period given by BestPeriod (a similar observation was made in [START_REF] Bougeret | Checkpointing strategies for parallel jobs[END_REF]). This gap increases when the distribution is further apart from an Exponential distribution. However, prediction-aware heuristics are very close to BestPeriod in almost all configurations. The only exception is with heuristics Instant when C p = 2C, the total number of processors N is equal to either 2 18 and 2 19 , and I is large. However, when I = 3000 and N = 2 19 , the platform MTBF is approximately equal to 6C p which renders our hypothesis and analysis invalid. The difference in this case between Instant and its BestPeriod should therefore not come as a surprise.

To better understand why close-to-optimal periods are obtained by predictionaware heuristics (while this is not the case without predictions), we plot the waste as a function of the period T R for RFO and the prediction-aware heuristics (Figures 14 through 17). On these figures one can see that, whatever the configuration, periodic checkpointing policies (ignoring predictions) have welldefined global optimum. (One should nevertheless remark that the performance is almost constant in the neighborhood of the optimal period which explains why policies using different periods can obtain in practice similar performance, as in [START_REF] Bouguerra | A flexible checkpoint/restart model in distributed systems[END_REF].) For prediction-aware heuristics, however, the behavior is quite different and two scenarios are possible. In the first one, once the optimum is reached, the waste very slowly increases to reach an asymptotic value which is close to the optimum waste (e.g., when the platform MTBF is large and failures follow an exponential distribution). Therefore, any period chosen close to the optimal one, or greater than it, will deliver good quality performance. In the second scenario, the waste decreases until the period becomes larger than the application size, and the waste stays constant. In other words, in these configurations, periodic checkpointing is unnecessary, only proactive actions matter! This striking result can be explained as follows: a significant fraction of the failures are predicted, and thus taken care of, by proactive checkpoints. The impact of unpredicted failures is mitigated by the proactive measures taken for false predictions. To further mitigate the impact of unpredicted faults, the period T R should be significantly shorter than the mean-time between proactive checkpoints, which would induce a lot of waste due to unnecessary checkpoints if the mean-time between unpredicted faults is large with respect to the mean-time between predictions. This greatly restrict the scenarios for which the periodic checkpointing can lead to a significant decrease of the waste.

When the prediction window I is shorter than the duration C p of a proactive checkpoint, there is no difference between NoCkptI and WithCkptI. When I is small but greater than C p (say, when I is around 2C p ), WithCkptI spends most of the prediction window taking a proactive checkpoint and NoCkptI is more efficient. When I becomes "large" with respect to C p , WithCkptI can become more efficient than NoCkptI, but becomes significantly more efficient only if the proactive checkpoints are significantly shorter than regular ones. Instant can hardly be seen in the graphs as its performance is most of the time equivalent to that of NoCkptI.

Figures 18 through 21 show the influence of the size of the prediction window I on the performance of the heuristics. As expected, the smaller the prediction window, the more efficient the prediction-aware heuristics. Also, the smaller the number of processors (or the larger the platform MTBF), the larger the impact of the size of the prediction window. A surprising result is that taking prediction into account is not always beneficial! The analytical results predict that prediction-aware heuristics would achieve worse performance than periodic policies in our settings, as soon as the platform includes 2 18 processors. In simulations, results are not so extreme. For the largest platforms considered, using predictions has almost no impact on performance. But when the prediction window is very large, taking predictions into account can indeed be detrimental. These observations can be explained as follows. When the platform includes 2 19 processors, the platform MTBF is equal to 7500 s. Therefore, any interval of duration 3000 has a 40% chance to include a failure: a prediction window of 3000 is not very informative, unless the precision and recall of the predictor are almost equal to 1 (which is never the case in practice). Since the predictor brings almost no knowledge, trusting it may be detrimental. When comparing the performance of, say, NoCkptI for the two predictors, one can see that when failures follow a Weibull distribution with shape parameter k = 0.7, I = 600, and N = 2 18 , NoCkptI achieves better performance than RFO when r = 0.85 and p = 0.82, but worse when p = 0.4 and r = 0.7. The latter predictor generates more false predictions -each one inducing an unnecessary proactive checkpoint-and misses more actual failures -each one destroying some work. The drawbacks of trusting the predictor outweigh the advantages. If failures are few and apart, almost any predictor will be beneficial. When the platform MTBF is small with respect to the cost of proactive checkpoints, only almost perfect predictors will be worth using. For each set of predictor characteristics, there is a threshold for the platform MTBF under which predictions will be useless or detrimental, but above which predictions will be beneficial. In order to compare the impact of the heuristics ignoring predictions to those using them, we report job execution times in Table 4. For the strategies with prediction, we compute the gain (expressed in percentage) over Daly, the reference strategy without prediction. We first remark that RFO achieves lower makespans than Daly with gains ranging from 1% with 2 16 processors to 18% with 2 19 processors. Overall, the gain due to the predictions decreases when the size of the prediction window increases, and increases with the platform size. This gain is obviously closely related to the characteristics of the predictor.

When I = 300, the three strategies are identical. When I increases, NoCkptI achieves slightly better results than Instant. For low values of I, WithCkptI is the worst prediction-aware heuristics. But when I becomes large and if the predictor is efficient, then WithCkptI becomes the heuristics of choice (I = 3000, p = 0.82, and r = 0.85).

The reductions in the application executions times due to the predictor can be very significant. With p = 0.85 and r = 0.82 and I = 3000, we save 25% of the total time with N = 2 19 , and 13% with N = 2 16 using strategy WithCkptI. With I = 300, we save up to 45% with N = 2 19 , and 18% with N = 2 16 using any strategy (though NoCkptI is slightly better than Instant). Then, with p = 0.4 and r = 0.7, we still save 33% of the execution time when I = 300 and N = 2 19 , and 14% with N = 2 16 . The gain gets smaller with I = 3000 and N = 2 16 but remains non negligible since we can save 8%. When I = 3000 and N = 2 19 , however, the best solution is to ignore predictions and simply use RFO (we fall-back to the case q = 0). If we now consider a Weibull law with shape parameter 0.5 instead of 0.7, keeping all other parameters identical (I = 3000, N = 2 19 , p = 0.4 and r = 0.7), then the heuristics of choice is WithCkptI and the gain with respect to Daly is 57.9%.

Related work

Considerable research has been conducted on fault prediction using different models (system log analysis [START_REF] Yu | Practical online failure prediction for Blue Gene/P: Period-based vs event-driven[END_REF], event-driven approach [START_REF] Gainaru | Taming of the shrew: Modeling the normal and faulty behavior of large-scale HPC systems[END_REF][START_REF] Yu | Practical online failure prediction for Blue Gene/P: Period-based vs event-driven[END_REF][START_REF] Zheng | A practical failure prediction with location and lead time for Blue Gene/P[END_REF], support vector machines [START_REF] Liang | Failure prediction in IBM BlueGene/L event logs[END_REF][START_REF] Fulp | Predicting computer system failures using support vector machines[END_REF]), nearest neighbors [START_REF] Liang | Failure prediction in IBM BlueGene/L event logs[END_REF], . . . ). In this section we give a brief overview of the results obtained by predictors. We focus on their results rather than on their methods of prediction. The authors of [START_REF] Zheng | A practical failure prediction with location and lead time for Blue Gene/P[END_REF] introduce the lead time, that is the time between the prediction and the actual fault. This time should be sufficient to take proactive actions. They are also able to give the location of the fault. While this has a negative impact on the precision (see the low value of p in Table 6), they state that it has a positive impact on the checkpointing time (from 1500 seconds to 120 seconds). The authors of [START_REF] Yu | Practical online failure prediction for Blue Gene/P: Period-based vs event-driven[END_REF] also consider a lead time, and introduce a prediction window when the predicted fault should happen. The authors of [START_REF] Liang | Failure prediction in IBM BlueGene/L event logs[END_REF] window sizes. They also consider a lead time, but do not state its value. These two latter studies motivate this work, even though [START_REF] Yu | Practical online failure prediction for Blue Gene/P: Period-based vs event-driven[END_REF] does not provide the size of their prediction window. Unfortunately, much of the work done on prediction does not provide information that could be really useful for the design of efficient algorithms. These informations are those stated above, namely the lead time and the size of the prediction window, but other information that could be useful would be: (i) the distribution of the faults in the prediction window; (ii) the precision as a function of the recall (see our analysis); and (iii) the precision and recall as functions of the prediction window (what happens with a larger prediction window).

While many studies on fault prediction focus on the conception of the predictor, most of them consider that the proactive action should simply be a checkpoint or a migration right in time before the fault. However, in their paper [START_REF] Li | Fault-aware runtime strategies for high-performance computing[END_REF], Li et al. consider the mathematical problem to determine when and how to migrate. In order to be able to use migration, they stated that at every time, 2% of the resources are available. This allowed them to conceive a Knapsack-based heuristic. Thanks to their algorithm, they were able to save 30% of the execution time compared to an heuristic that does not take the reliability into account, with a precision and recall of 70%, and with a maximum load of 0.7.

In the simpler case where predictions are exact-date predictions, Gainaru et al [START_REF] Gainaru | Fault prediction under the microscope -a closer look into hpc systems[END_REF] have shown that the optimal checkpointing period becomes T opt = 2µC 1 -r , but their analysis is valid only if µ is very large in front of the other parameters. Our previous work [START_REF] Aupy | Checkpointing algorithms and fault prediction[END_REF] has refined the results of [START_REF] Gainaru | Fault prediction under the microscope -a closer look into hpc systems[END_REF], focusing on a more accurate analysis of fault prediction with exact dates, and providing a detailed study on the impact of recall and precision on the waste. As shown in Section 3, the analysis of the waste is dramatically more complicated when using prediction windows than when using exact-date predictions. To the best of our knowledge, this work is the first to focus on the mathematical aspect of fault prediction with prediction windows, and to provide a model and a detailed analysis of the waste due to all three types of events (true and false predictions and unpredicted failures).

Conclusion

In this work, we have studied the impact of prediction windows on checkpointing strategies. We have designed several heuristics that decide whether to trust these predictions, and when it is worth taking preventive checkpoints. We have been able to derive a comprehensive set of results and conclusions:

• We have introduced an analytical model to capture the waste incurred by each strategy, and provided for each optimization problem a closed-form formula giving its optimal solution. Contrarily to the cases without prediction, or with exact-date predictions, the computation of the waste requires a sophisticated analysis of the various events, including the time spent irregular or proactive modes.

• The simulations fully validate the model, and the brute-force computation of the optimal period guarantees that our prediction-aware strategies are always very close to the optimal. This holds true both for Exponential and Weibull failure distributions.

• The model is quite accurate and its validity goes beyond the conservative assumption that requires a single event per time interval; even more surprising, the accuracy of the model for prediction-aware strategies is much better than for the case without predictions, where Daly can be far from the optimal period in the case of Weibull failure distributions.

• Both the analytical computations and the simulations enable to characterize when prediction is useful, and which strategy performs better, given the key parameters of the system: recall r, precision p, size of the prediction window I, size of proactive checkpoints C p versus regular checkpoints C, and platform MTBF µ.

Altogether, the analytical model and the comprehensive results provided in this work enable to fully assess the impact of fault prediction with time-windows on optimal checkpointing strategies. Future work will be devoted to refine the assessment of the usefulness of prediction with trace-based failure and prediction logs from current large-scale supercomputers.

Figure 1 :

 1 Figure 1: Outline of Algorithm 1 (strategy WithCkptI).

  in proactive mode, and we have a downtime and a recovery. Hence, such an interval lastsT R + C p + E (f ) I + D + Ron average. The total work done during the interval is T R -C + x(T P -C p ) where x is the expectation of the number of proactive checkpoints successfully taken during the prediction window. Here, x ≈ E (f ) I TP -1. (b) Not taken into account. On average the fault occurs at time T R /2.

4 .

 4 True prediction. There are two cases: (a) Taken into account. Let E (f ) I be the average time at which a fault occurs within the prediction window. We take a proactive checkpoint right before the start of the prediction window. Then we spend the time E (f ) I in proactive mode working without checkpointing, and we have a downtime and a recovery. Hence, such an interval lasts T R + C p +E (f ) I +D+R on average. The total work done during the interval is T R -C. (b) Not taken into account. On average the fault occurs at time T R /2.

4 .

 4 True prediction. There are two cases: (a) Taken into account. Let E (f ) I

  average. The total work done during the interval is T R -C. (b) Not taken into account. On average the fault occurs at time T R /2.

Figure 2 :

 2 Figure 2: Waste for the different heuristics, with p = 0.82, r = 0.85, C p = C, and with a trace of false predictions parametrized by a distribution identical to the distribution of the trace of failures.

Figure 3 :

 3 Figure 3: Waste for the different heuristics, with p = 0.82, r = 0.85, C p = 0.1C, and with a trace of false predictions parametrized by a distribution identical to the distribution of the trace of failures.

Figure 4 :

 4 Figure 4: Waste for the different heuristics, with p = 0.82, r = 0.85, C p = 2C, and with a trace of false predictions parametrized by a distribution identical to the distribution of the trace of failures.

Figure 5 :

 5 Figure 5: Waste for the different heuristics, with p = 0.4, r = 0.7, C p = C, and with a trace of false predictions parametrized by a distribution identical to the distribution of the trace of failures.

Figure 6 :

 6 Figure 6: Waste for the different heuristics, with p = 0.4, r = 0.7, C p = 0.1C, and with a trace of false predictions parametrized by a distribution identical to the distribution of the trace of failures.

Figure 7 :

 7 Figure 7: Waste for the different heuristics, with p = 0.4, r = 0.7, C p = 2C, and with a trace of false predictions parametrized by a distribution identical to the distribution of the trace of failures.

Figure 8 :

 8 Figure 8: Waste for the different heuristics, with p = 0.82, r = 0.85, C p = C, and with a trace of false predictions parametrized by a uniform distribution.

Figure 9 :

 9 Figure 9: Waste for the different heuristics, with p = 0.82, r = 0.85, C p = 0.1C, and with a trace of false predictions parametrized by a uniform distribution.

Figure 10 :

 10 Figure 10: Waste for the different heuristics, with p = 0.82, r = 0.85, C p = 2C, and with a trace of false predictions parametrized by a uniform distribution.

Figure 11 :

 11 Figure 11: Waste for the different heuristics, with p = 0.4, r = 0.7, C p = C, and with a trace of false predictions parametrized by a uniform distribution.

Figure 12 :

 12 Figure 12: Waste for the different heuristics, with p = 0.4, r = 0.7, C p = 0.1C, and with a trace of false predictions parametrized by a uniform distribution.

Figure 13 : 5 Figure 14 : 5 Figure 15 : 5 Figure 16 : 5 Figure 17 :

 13514515516517 Figure 13: Waste for the different heuristics, with p = 0.4, r = 0.7, C p = 2C, and with a trace of false predictions parametrized by a uniform distribution.

5 Figure 18 : 5 Figure 19 :

 518519 Figure 18: Waste as function of the prediction window I for the different heuristics, with p = 0.82, r = 0.85, C p = C, and with a platform of 2 16 processors.

Figure 20 :

 20 Figure 20: Waste as function of the prediction window I for the different heuristics, with p = 0.4, r = 0.7, C p = C, and with a platform of 2 16 processors.

Figure 21 :

 21 Figure 21: Waste as function of the prediction window I for the different heuristics, with p = 0.4, r = 0.7, C p = C, and with a platform of 2 19 processors.

  Let t C be the date of the last checkpoint under regular mode to start no later than t -C p ;

	1 if fault happens then
	2	After downtime, execute recovery;
	3	Enter regular mode;
	4 if in proactive mode for a time greater than or equal to I then
	5	Switch to regular mode
	6 if Prediction made with interval [t, t + I] and prediction taken into
	account then
	7
	8	if t C + C < t -C p then (enough time for an extra checkpoint)
	9	Take a checkpoint starting at time t -C p
	10	else (no time for the extra checkpoint)
	11	Work in the time interval [t C + C, t]
	14 while in regular mode and no predictions are made and no faults happen
	do
	15	Work for a time T R -W reg -C and then checkpoint;
	16	W reg ← 0;
	17 while in proactive mode and no faults happen do
	18	Work for a time T P -C p and then checkpoint;

12

W reg ← max (0, t -C p -(t C + C)) ;

13 Switch to proactive mode at time t;

Table 1 :

 1 Summary of the different types of interval for WithCkptI.the simplifying hypothesis, intervals of different types never overlap. Table

Table 3 :

 3 Summary of the different types of interval for Instant.

Table 4 :

 4 Job execution times (in days) under the different checkpointing policies, when failures follow a Weibull distribution of shape parameter 0.7. Gains are reported with respect to Daly.

		I = 300 s	I = 1200 s	I = 3000 s
		2 16 procs	2 19 procs	2 16 procs	2 19 procs	2 16 procs	2 19 procs
	Daly	125.7	185.0	125.7	185.0	125.7	185.0
	RFO	120.1 (4%) 114.8 (38%) 120.1 (4%) 114.8 (38%) 120.1 (4%) 114.8 (38%)
				p = 0.82, r = 0.85
	NoCkptI	77.4 (38%) 44.9 (76%)	81.8 (35%) 60.7 (67%)	90.0 (28%) 71.5 (61%)
	WithCkptI 77.4 (38%) 44.9 (76%)	83.6 (33%) 64.4 (65%)	89.8 (29%) 66.2 (64%)
	Instant	77.4 (38%) 45.2 (76%)	82.0 (35%) 60.8 (67%)	89.7 (29%) 70.6 (62%)
				p = 0.4, r = 0.7
	NoCkptI	84.4 (33%) 58.3 (68%)	89.1 (29%) 76.8 (58%)	97.9 (22%) 83.7 (55%)
	WithCkptI 84.4 (33%) 58.3 (68%)	93.8 (25%) 75.4 (59%)	97.8 (22%) 77.7 (58%)
	Instant	84.5 (33%) 59.6 (68%)	89.4 (29%) 76.64 (58%) 97.7 (22%) 81.9 (56%)

Table 5 :

 5 Job execution times (in days) under the different checkpointing policies, when failures follow a Weibull distribution of shape parameter 0.5. Gains are reported with respect to Daly.

Table 6 :

 6 study the impact of different prediction techniques with different prediction Comparative study of different parameters returned by some predictors.

	Paper Lead Time Precision Recall Prediction Window
	[10]	300 s	40 %	70%	-
	[10]	600 s	35 %	60%	-
	[5]	2h	64.8 %	65.2% yes (size unknown)
	[5]	0 min	82.3 %	85.4 % yes (size unknown)
	[19]	32 s	93 %	43 %	-
	[20]	NA	70 %	75 %	-
	[6]	NA	20 %	30 %	1h
	[6]	NA	30 %	75 %	4h
	[6]	NA	40 %	90 %	6h
	[6]	NA	50 %	30 %	6h
	[6]	NA	60 %	85%	12h

RR n°8239

Acknowledgments. The authors are with Université de Lyon, France. Y. Robert is with the Institut Universitaire de France. This work was supported in part by the ANR RESCUE project.