Yishu Du

Loris Marchal

Aupy Guillaume Pallez

Yves Robert
email: yves.robert@ens-lyon.fr.

Optimal Checkpointing Strategies for Iterative Applications

Keywords: Iterative application, checkpoint strategy, fail-stop error, resilience. !

This work provides an optimal checkpointing strategy to protect iterative applications from fail-stop errors. We consider a general framework, where the application repeats the same execution pattern by executing consecutive iterations, and where each iteration is composed of several tasks. These tasks have different execution lengths and different checkpoint costs. Assume that there are n tasks and that task a i , where 0 ≤ i < n, has execution time t i and checkpoint cost c i . A naive strategy would checkpoint after each task. Another naive strategy would checkpoint at the end of each iteration. A strategy inspired by the Young/Daly formula would work for √ 2µcave seconds, where µ is the application MTBF and cave is the average checkpoint time, and checkpoint at the end of the current task (and repeat). Another strategy, also inspired by the Young/Daly formula, would select the task a min with smallest checkpoint cost c min and would checkpoint after every p th instance of that task, leading to a checkpointing period pT , where T = n-1 i=0 a i is the time per iteration. One would choose the period so that pT ≈ √ 2µc min to obey the Young/Daly formula. All these naive and Young/Daly strategies are suboptimal. Our main contribution is to show that the optimal checkpoint strategy is globally periodic, and to design a dynamic programming algorithm that computes the optimal checkpointing pattern. This pattern may well checkpoint many different tasks, and this across many different iterations. We show through simulations, both from synthetic and real-life application scenarios, that the optimal strategy outperforms the naive and Young/Daly strategies.

INTRODUCTION

Deploying scientific applications at large scale requires fault-tolerant mechanisms. State-of-the-art supercomputers such as Fugaku, Summit, or Sierra (respectively ranked 1st, 2nd, and 3rd in the TOP500 ranking [46]) are now embedding millions of cores (with a peak at 10.6M for Sunway TaihuLight (4th)). These very large systems are prone to failures: even if each of their cores has a very low probability of failure, the failure probability of the whole system is much higher. More precisely, assume that the Mean Time Between Failure (MTBF) of each computing resource is around 10 years, which means that such a resource should experience an error only every ten years on average, and which explains why computing resources are individually very reliable. When running a simulation code on 100,000 of these resources in parallel, the MTBF is reduced to only 50 minutes [START_REF]Fault-Tolerance Techniques for High-Performance Computing, Computer Communications and Networks[END_REF]: on average one node of the computing platform crashes every 50 minutes. With one million of such resources, the MTBF gets as small as five minutes, while codes deployed on such extreme-scale platforms usually last for hours or days. As the demand for computing power increases, failures cannot be ignored anymore, and faulttolerant mechanisms must be deployed.

The classical way of dealing with failures in extremescale computing systems consists of Checkpoint/Rollback mechanisms. A checkpoint of the application is taken period-ically, that is, the state of the application (usually the whole content of its memory) is written onto reliable storage. Whenever one of the computing resources experiences a failure, the application pauses and restarts from the last valid checkpoint. Several studies have focused on the crucial question of the optimal checkpointing period, defined as the time between two consecutive checkpoints. On the one hand, if checkpoints are taken too often, time is wasted in costly I/O operations. On the other hand, if checkpoints are too infrequent, time will be wasted in recomputing large portions of the application after each failure. Interestingly, reliability was already a question in the early days of computing: in the 70s, Young has proposed a first-order approximation of the optimal time between two checkpoints that minimizes the expected duration of the whole computation [START_REF] Young | A first order approximation to the optimum checkpoint interval[END_REF]. Young's approximation has then be refined by Daly thirty years later [START_REF] Daly | A higher order estimate of the optimum checkpoint interval for restart dumps[END_REF]. The Young/Daly approach assumes that a checkpoint can be taken anytime during the computation, and that the time needed to take a checkpoint is constant (which corresponds to a constant size of the data to save).

When designing checkpoint/restart strategies for taskbased workflows, it is natural to take checkpoint between the completion of some task and the beginning of its successor. This way, the checkpoint mechanism can be provided by the workflow management system without having to modify the code of each task. However, this restricts the time-steps at which checkpoints can be taken and makes the optimization problem of selecting the best checkpoint times more difficult. Furthermore, the data to checkpoint, is now the output of the tasks and may have different sizes for different tasks of the workflow.

In this paper, we focus on designing optimal checkpoint strategies for iterative workflows expressed as pipelined linear workflows: we consider workflows made of a large number of iterations, each iteration being a linear chain of parallel tasks. The typical example is an application consisting of an outer loop "While convergence is not met, do", and where the loop body includes a sequence of large parallel operations. The objective is to find which task outputs should be saved on stable storage in order to minimize the expected duration of the whole computation.

To the best of our knowledge, this is an open problem, despite the practical importance and ubiquity of pipelined linear workflows in High-Performance Computing (HPC). Indeed, the simple case of a unique linear chain of tasks (a pipelined linear workflow with a single iteration) has been solved by Toueg et al. [START_REF] Toueg | On the optimum checkpoint selection problem[END_REF] using a dynamic programming algorithm. On the contrary, the problem for workflows with general directed graphs has been shown #P-complete 1 [START_REF] Han | Checkpointing workflows for fail-stop errors[END_REF].

The study for pipelined linear workflows (a linear chain with several iterations) is challenging, and the main contribution of this paper is to provide a complete answer:

• We prove that there exists an optimal checkpointing strategy which is periodic. It consists in a pattern of task outputs to checkpoint, where this pattern spans over a set of iterations of bounded size. This pattern is repeated over and over throughout the execution.

• We provide a dynamic programming algorithm which is polynomial in the number of operations included in the outer loop to compute the optimal periodic checkpoint pattern. The complexity of the algorithm does not depend on the number of iterations of the outer loop. This pattern may well checkpoint many different tasks, and this across many different iterations.

• We conduct an extensive set of simulations to compare the optimal strategy to four natural competitor strategies: the first checkpoints after each task, the second after each iteration, while the last two are extensions of the Young/Daly formula for iterative applications.

Our simulations with both synthetic and real-life workflow instances demonstrate that our optimal strategy provide improvement over the simpler competitors. The rest of the paper is organized as follows. Section 2 reviews related work. Section 3 presents a detailed model for the problem and states the objective function. Section 4 outlines the optimal checkpoint strategy. Section 5 reports a comprehensive set of experimental results, based upon both synthetic workflows and on workflows arising from two real-life applications. Finally, Section 6 provides concluding remarks and directions for future work.

RELATED WORK

We survey related work in this section. We start with checkpointing in Section 2.1. Then we discuss iterative applications with cyclic tasks in Section 2.2. We end with faulttolerance methods for iterative applications in Section 2.3.

Checkpointing

Checkpoint-restart is one of the most used strategy to deal with fail-stop errors, and several variants of this policy 1. #P-complete problems are at least as hard as NP-complete problems have been studied, see [START_REF]Fault-Tolerance Techniques for High-Performance Computing, Computer Communications and Networks[END_REF] for an overview. The natural strategy is to checkpoint periodically, and one must decide how often to checkpoint, i.e., must derive the optimal checkpointing period. An optimal strategy is defined as a strategy that minimizes the expectation of the execution time of the application. For a divisible-load application, given the checkpointing cost C and platform MTBF µ, the classical formula due to 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] states that the optimal checkpointing period is P Y D = √ 2µC.

Going beyond divisible-load applications, some works have studied linear workflows, i.e., applications that can be expressed as a linear chain of (parallel) tasks. Checkpointing is only possible right after the completion of a task, and the problem is to determine which tasks should be checkpointed. This problem has been solved by Toueg and Babaoglu [START_REF] Toueg | On the optimum checkpoint selection problem[END_REF] using a dynamic programming algorithm. We stress that this latter approach is not suited to iterative applications. Indeed, consider an iterative application with a large number of iterations, say N iter = 10, 000 iterations, and assume that n = 10 (10 tasks per iteration). One solution to find an optimal checkpointing strategy could be: (i) unroll the loop and build a linear chain of n × N iter = 100, 000 tasks; (ii) apply the algorithm of [START_REF] Toueg | On the optimum checkpoint selection problem[END_REF] to this huge chain and return the optimal solution. However, the cost of this algorithm is quadratic in the value of N iter . Worse, if we reexecute the same application for N iter = 20, 000 iterations, we have to recompute the optimal solution from scratch. On the contrary, our approach provides a generic and compact solution that does not depend upon the value of N iter .

Recently, the results of [START_REF] Toueg | On the optimum checkpoint selection problem[END_REF] have been extended to deal with linear chains whose tasks do not have constant execution times but instead obey some probability distributions [START_REF] Du | Robustness of the Young/Daly formula for stochastic iterative applications[END_REF]. As pointed out above, for general workflows, deciding which tasks to checkpoint has been shown #Pcomplete [START_REF] Han | Checkpointing workflows for fail-stop errors[END_REF], but the results of [3] show that if the graph is scheduled in a sequential manner (linearized), then one can derive an optimal checkpointing strategy. In this paper, we focus on pipelined linear workflows, i.e., on applications expressed as a linear chain of tasks that repeats iteratively.

Iterative applications

Iterative methods are popular for solving large sparse linear systems, which have a wide range of applications in several scientific and industrial problems. There are many classic iterative methods including stationary iterative methods like the Jacobi method [START_REF] Saad | Iterative methods for sparse linear systems[END_REF], the Gauss-Seidel method [START_REF] Saad | Iterative methods for sparse linear systems[END_REF] and the Successive Overrelaxation method (SOR) [START_REF] Stanley | Convergence rates of iterative treatments of partial differential equations[END_REF][START_REF] Young | Iterative methods for solving partial difference equations of elliptic type[END_REF], and non-stationary iterative methods like Krylov subspace methods, including Generalized Minimal Residual method (GMRES) [START_REF] Saad | Gmres: A generalized minimal residual algorithm for solving nonsymmetric linear systems[END_REF], Bi-conjugate Gradient Stabilized method (BiCGSTAB) [START_REF] Martin | Variants of bicgstab for matrices with complex spectrum[END_REF], Generalized Conjugate Residual method (GCR) [START_REF] Stanley C Eisenstat | Variational iterative methods for nonsymmetric systems of linear equations[END_REF], together with their ABFT (algorithm-based fault-tolerance) variants [1,2,[START_REF] Langou | Recovery patterns for iterative methods in a parallel unstable environment[END_REF].

Krylov subspace methods fit perfectly our model: the outer iteration corresponds to an iteration of the application in our model, while the inner iterations in each increasing Krylov subspace correspond to the tasks in our model. We report experiments with the GCR algorithm in the Web Supplementary Material (WSM).

The class of iterative applications goes well beyond sparse linear solvers. Uncertainty Quantification (UQ) workflows explore a parameter space in an iterative fashion [START_REF] William | Verification and validation in scientific computing[END_REF][START_REF] Christopher | A comprehensive framework for verification, validation, and uncertainty quantification in scientific computing[END_REF]. This class also encompasses many image and video processing software which operate a chain of computations kernels (each being a task) on a sequence of data sets (each corresponding to an iteration). Examples include image analysis [START_REF] Sertel | Computer-aided prognosis of neuroblastoma on whole-slide images: Classification of stromal development[END_REF], video processing [START_REF] Guirado | Optimizing latency under throughput requirements for streaming applications on cluster execution[END_REF], motion detection [START_REF] Knobe | Scheduling constrained dynamic applications on clusters[END_REF], signal processing [START_REF] Choudhary | implementation and evaluation of parallel pipelined STAP on parallel computers[END_REF][START_REF] Timothy | Investigating the Use of GPU-Accelerated Nodes for SAR Image Formation[END_REF], databases [START_REF] Chekuri | Scheduling problems in parallel query optimization, Pods[END_REF], molecular biology [START_REF] Rowe | The discovery net system for high throughput bioinformatics[END_REF], medical imaging [START_REF] Guirado | Exploiting throughput for pipeline execution in streaming image processing applications[END_REF], and various scientific data analyses, including particle physics [START_REF] Deelman | Grid resource management[END_REF], earthquake [START_REF] Kim | A knowledge-based approach to interactive workflow composition[END_REF], weather and environmental data analyses [START_REF] Rowe | The discovery net system for high throughput bioinformatics[END_REF].

Fault-tolerance methods for iterative applications

The literature devoted to the study of fault-tolerance methods for iterative linear solvers can be divided into two categories, depending upon whether the focus is on soft errors or on fail-stop errors.

There are some works dealing with soft errors. Chen presented online-ABFT in [START_REF]Online-abft: An online algorithm based fault tolerance scheme for soft error detection in iterative methods[END_REF], a technique that can detect soft errors in the specific Krylov subspace iterative methods by leveraging the orthogonality relationship of two vectors in the middle of the program execution. For general iterative methods, Tao et al. [START_REF] Tao | New-sum: A novel online abft scheme for general iterative methods[END_REF] presented a new online-ABFT approach to detect and recover soft errors by combining a novel checksum-based encoding scheme with a checkpoint/rollback scheme. According to the specific properties of GMRES algorithm, Bridges et al. [5] and Elliott et al. [START_REF] Elliott | Evaluating the impact of sdc on the gmres iterative solver[END_REF] proposed the FT-GMRES algorithm using selective reliability. Similarly, Sao and Vuduc [START_REF] Sao | Self-stabilizing iterative solvers[END_REF] proposed the self-stabilizing conjugate gradient method (CG) in view of the special properties of CG algorithm: they check that orthogonality is preserved by recomputing scalar products that should be zero and restarting whenever a threshold is exceeded. Ozturk et al. [START_REF] Muhammed Emin Ozturk | Handling soft errors in krylov subspace methods by exploiting their numerical properties[END_REF] proposed a decreasing energy norm based on the mathematical properties to detect soft errors leading to silent data corruption (SDC) for GMRES, CG and Conjugate Residual method (CR).

There are some works dealing with fail-stop errors. To reduce the fault tolerance overhead incurred by checkpointing, Chen [START_REF] Chen | Algorithm-based recovery for iterative methods without checkpointing[END_REF] proposed a recovery method for iterative methods without checkpointing based on the specific properties of iterative methods. Tao et al. [START_REF] Tao | Improving performance of iterative methods by lossy checkponting[END_REF] improved the checkpointing performance for iterative methods under a novel lossy checkpointing scheme. Langou et al. [START_REF] Langou | Recovery patterns for iterative methods in a parallel unstable environment[END_REF] presented a lossy approach which is a checkpoint-free fault tolerant scheme for parallel iterative methods. The iterative method is restarted with a new vector which is a new approximate solution recovered from a fail-stop error by using the data of the non-failed processors. Agullo et al. [1,2] extended this approach by computing a well-suited initial guess which is defined by interpolating the lost entries of the current iterate vector available on surviving nodes, in order to restart the Krylov method. Pachajoa et al. [START_REF] Pachajoa | Extending and evaluating fault-tolerant preconditioned conjugate gradient methods[END_REF] compared the exact state reconstruction (ESR) approach based on the method proposed by Chen [START_REF] Chen | Algorithm-based recovery for iterative methods without checkpointing[END_REF] with the heuristic linear interpolation (LI) approach by Langou et al. [START_REF] Langou | Recovery patterns for iterative methods in a parallel unstable environment[END_REF] and Agullo et al. [1,2]. They later extended the ESR approach for protecting the PCG method against multiple and simultaneous node failures [START_REF] Pachajoa | How to make the preconditioned conjugate gradient method resilient against multiple node failures[END_REF][START_REF] Pachajoa | Algorithm-based checkpoint-recovery for the conjugate gradient method[END_REF]. Altogether, faulttolerance methods proposed to mitigate the impact of failstop errors in iterative applications are application-specific, and can only be applied to a particular class of iterative algorithms. Moreover, their performance highly depends upon specific properties of the algorithms, and, for instance, considerably vary from one Krylov method to another. The main contribution of this work is to provide a general-purpose approach to deal with fail-stop errors in iterative applications. Our optimal checkpointing strategy is agnostic of any specific property of the target iterative application. Instead, it abstracts the iterative application as a chain of cyclic tasks, and provides the optimal periodic checkpoint pattern based only upon generic information such as task durations and checkpoint costs.

MODEL

In this section, we detail the application and platform models. Then we define checkpoint strategies and formally state the optimization objective. See Table 1 for a summary of main notations.

Application model

We consider an iterative application A. Each iteration of the application consists of n parallel tasks a i , where 0 ≤ i < n, task a i has length t i and memory footprint M i . We define the length of an iteration as T = n-1 i=0 t i . The tasks are executed consecutively: let i[n] denote the remainder of the integer division of i by n (modulo operation); then a task a i is always followed by a task a i+1 [n] . We assume that the application executes for a long time and consider an unbounded number of iterations (but we use 1, 000 iterations in the experiments). For short we write A = (a 0 , . . . , a n-1 ) ∞ . As stated before, we execute tasks one after the other. The first executed task is a 0 , followed by a 1 , and so on. The n th task is a n-1 and the (n + 1)st task is a 0 again. In general, the k th task is a k-1 [n] . Note that we index tasks from 0 to use the modulo operation, hence this shift when counting executed tasks.

We assume that the tasks of the application can be checkpointed at the end of their execution. We consider a general model where the checkpoint time of task a i is c i and its recovery time is r i . We refer to c i and r i as operations of type i. We do not assume that c i = r i ; instead, we simply assume monotone I/O costs: for all i, j, c i ≥ c j =⇒ r i ≥ r j .

(

Essentially this assumption states that if a task is longer to checkpoint than another one, then restarting from this checkpoint is also longer. This is coherent with the fact that checkpoint and recovery costs are often closely related, and are a function of the volume of data to save. Furthermore, this assumption is general enough to account for different read and write bandwidths.

We assume that all task parameters (execution time, checkpoint, recovery) are known. This is a natural assumption for iterative applications which repeat each task a large number of times and can determine their characteristics either through an analytical model or by repetitive sampling. However, to assess the robustness of the approach, we also report experiments using stochastic execution times derived from a Normal probability distribution.

Platform model

We consider a parallel platform whose nodes are subject to fail-stop errors, or failures. A failure, such as a node crash, interrupts the execution of the node and provokes the loss of its whole memory. Consider a parallel application running on several nodes: when one of these nodes is struck by a failure, the state of the application is lost, and execution must restart from scratch, unless a fault-tolerance mechanism has been deployed.

The classical technique to deal with failures consists of using a checkpoint-restart mechanism: the state of the application is periodically checkpointed, which means that all participating nodes take a checkpoint simultaneously: this is the standard coordinated checkpointing protocol which is routinely used on large-scale platforms [7], where each node writes its share of application data to stable storage (checkpoint of duration C). When a failure occurs, the platform is unavailable during a downtime D, which is the time to enroll a spare processor which will replace the faulty processor [START_REF] Daly | A higher order estimate of the optimum checkpoint interval for restart dumps[END_REF][START_REF]Fault-Tolerance Techniques for High-Performance Computing, Computer Communications and Networks[END_REF]. Then all application nodes (including the spare) recover from the last valid checkpoint in a coordinated manner, reading the checkpoint file from stable storage (recovery of duration R). Then the execution is resumed from that point on, rather than starting again from scratch.

We assume that the iterative application experiences failures whose inter-arrival times follow an Exponential distribution Exp(λ) of parameter λ > 0, whose PDF (Probability Density Function) is f (x) = λe -λx for x ≥ 0. The MTBF is µ = 1 λ and corresponds to the MTBF of individual processors divided by the total number of processors enrolled in the application [START_REF]Fault-Tolerance Techniques for High-Performance Computing, Computer Communications and Networks[END_REF]. As stated in the introduction, even if each node has an MTBF of several years, large-scale parallel platforms are composed of so many nodes that they will experience several failures per day [6,[START_REF] Ferreira | Evaluating the Viability of Process Replication Reliability for Exascale Systems[END_REF]. Hence, a parallel applications using a significant fraction of the platform will typically experience a failure every few days.

The key for an efficient checkpointing policy is to decide how often to checkpoint. 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] derived the well-known Young/Daly formula P YD = √ 2µC for the optimal checkpointing period, where µ is the application MTBF and C is the checkpoint duration, as defined above.

Schedule

Informally, a schedule defines which tasks are checkpointed. A priori, there is no reason for a schedule to enforce a regular pattern of checkpoints that repeats over time. In other words, a schedule can be aperiodic. However, one major contribution of this work is to show that periodic schedules are optimal, and to exhibit the optimal period as the output of a polynomial-time algorithm. We need a few definitions before stating the objective function to be minimized by optimal schedules. First we identify a schedule with the list of the tasks that it checkpoints:

Definition 1 (Schedule). A schedule S is an infinite increasing sequence S = (m 1 , m 2 , . . . ) which represents the list of checkpointed tasks: the m th i task (i.e., task number m i ) is checkpointed, and the tasks whose number does not belong to the list are not checkpointed.

In other words, checkpoint number i in the schedule takes place at the end of task number m i . The cost to checkpoint that task m i is c mi-1[n] (because of the index shift noted above). Without loss of generality, we assume that the schedule checkpoints infinitely many tasks, i.e., lim i→∞ m i = ∞. Indeed, consider any task in the application: eventually there must be a checkpoint after that task, otherwise the expected execution time from that task on is not bounded, because the fault-rate λ is nonzero.

A schedule S can be viewed as a succession of task chunks between two consecutive checkpoints. We use the following notations for the i th chunk between checkpoint number i -1 (or the beginning of the execution if i = 1) and checkpoint number i:

• The length of the tasks in the chunk is

W S i = mi j=mi-1+1 t j-1[n]
• The checkpoint cost at the end of the chunk is the cost of checkpoint number i, namely

C S i = c mi-1[n]
• The recovery cost when re-executing the chunk is the cost of recovering from checkpoint number i -1, namely

R S i-1 = r mi-1-1[n] When i = 1 (first chunk), we let m 0 = 0, and R S 0 denotes the cost of reading input data. Time a 0 a 1 a 2 a 0 W S 1 = a 0 + a 1 + a 2 + a 0 C S 1 = c 0 a 1 a 2 failure D R S 1 = r 0 a 1 a 2 W S 2 C S 2 a 0 a 1 • • •

Objective function

Intuitively, a good schedule will minimize the slowdown during the execution. This slowdown comes from two sources of overhead: the checkpoints that are inserted, and the time lost due to failures. When a failure strikes during execution, the work executed since the last checkpoint is lost; there is a downtime, followed by a recovery, and then the re-execution of the work that has been lost due to the failure. Altogether, the overhead is not deterministic and varies from one execution to the other, hence we aim at minimizing the slowdown in expectation. Given a schedule S, we rely on a well-known formula to compute the expected execution time of a chunk. Indeed, the expected execution time E λ (w, c, r) to execute w consecutive seconds of work followed by a checkpoint of size c with a recovery of size r is given by [27]

E λ (w, c, r) = 1 λ + D e λr e λ(w+c) -1 (2)
The expected time to execute the chunk number i is thus

E λ (W S i , C S i , R S i-1 ). Hence the expected time to execute the first i chunks is i j=1 E λ (W S j , C S j , R S j-1 ),
The slowdown incurred for the first i chunks (i.e., up to checkpoint number i) is therefore

SD i (S) = i j=1 E λ (W S j , C S j , R S j-1 ) mi j=1 t j-1[n] (3)
In Equation ( 3), the numerator is the expected time to execute the first i chunks, while the denominator is the duration of the tasks up to checkpoint number i, which corresponds to the resilience-free and failure-free execution.

Unfortunately, there is no reason that lim i→∞ SD i (S) would exist. However, we can use the upper limit of SD i (S) to define the slowdown of schedule S: Definition 2 (Slowdown). The slowdown SD of a schedule is:

SD(S) = lim i→∞ SD i (S) (4)
We know that this upper limit is bounded for some schedules. Consider for instance the schedule S that checkpoint all tasks: m i = i for all i ≥ 1. This schedule repeats the same pattern of checkpoints every iteration, so that its slowdown is

SD(S) = SD n (S) T = n-1 j=0 1 λ + D e λr j-1[n] e λ(tj +cj ) -1
T Recall that T is the length of an iteration. We are now ready to define an optimal schedule: Definition 3 (Optimal schedule). A schedule is optimal if its slowdown SD(S) is minimal over all possible schedules. Note that the definition does not assume that there exists a unique optimal schedule. A major contribution of this paper is to show that there exists an optimal schedule which is periodic, i.e., which repeats the same pattern of checkpoints after some point (see below for the formal definition). This important result will allow us to consider only a finite number of candidate schedules, and to design a polynomial-time algorithm to find an optimal schedule.

a 0 a 1 Init a 2 a 0 a 1 a 2 a 0 a 1 a 2 • • • Period a 2 a 0 a 1 a 2 a 0 a 1 a 2 • • • Period a 2 a 0 a 1 • • • Period Figure 2:
A periodic schedule where the period is repeated over time.

Periodic schedules

Periodic schedules are natural schedules that can be expressed in a compact form. As already mentioned, after some possible initialization phase, a periodic schedule repeats the same sequence of checkpoints over and over. Here is the formal definition:

Definition 4 (Periodic schedules). A schedule (m 1 , m 2 , . . . ) is periodic if there exists two indices i 0 and k 0 such that for all i > i 0 , m i -m i-1 = m i+k0 -m i+k0-1 .
An example of periodic schedule is given in Figure 2. Intuitively, the schedule enters its steady state after checkpoint number i 0 (with possibly i 0 = 0): the period starts right after task number m i0 , and then repeats the same sequence of k 0 checkpoints: the first checkpoint of the period is taken after m i0+1 -m i0 tasks, the second one after m i0+2 -m i0+1 tasks, until the last checkpoint of the period, that of task number m i0+k0 . Then the period repeats indefinitely.

For a periodic schedule, the limit lim i→∞ SD i (S) always exists, and is given by the slowdown incurrred during each (infinitely repeating) period. Specifically, given i 0 and k 0 in Definition 4, we see from Equation (3) that this slowdown becomes:

i0+k0 i=i0+1 E λ (W S i , C S i , R S i-1
)

m i 0 +k 0 j=mi 0 +1 t j-1[n]
We prove this result formally below. The major results of this work are the following two theorems, which we prove in Section 4 below. Theorem 1. There exists a periodic schedule that is optimal. Theorem 2. We can compute an optimal periodic schedule in polynomial time.

Proof sketch:

The proof has several steps. First we prove that there exists an optimal periodic schedule, i.e., a periodic schedule whose slowdown is minimal. Then we show how to bound the length of the period of this schedule. Once this is done, we have a finite number of periods to look for, and we exhibit a dynamic programming algorithm that determines the optimal period in polynomial time, independently of the number of iterations.

OPTIMAL CHECKPOINT STRATEGY

In this section, we present several theoretical results and prove Theorems 1 and 2. Specifically, we start by showing that we can indeed focus on periodic algorithms (Theorem 1) in Section 4.3. Then in Section 4.4, we show that we can compute an optimal periodic schedule in polynomial time (Theorem 2).

Beforehand, we introduce the definition of a pattern which is at the heart of periodic algorithms (Section 4.1), and we present several important properties of patterns in Section 4.2.

Paths and patterns

Definition 5 (Checkpoint Paths). A Checkpoint Path

(P = (i 0 , [m 1 , . . . , m k P ])) is a sequence of m k P tasks b 0 , . . . , b m k P -1 such that: 1) for 0 ≤ i ≤ m k P -1, b i = a i0+i[n] ; 2) for 1 ≤ j ≤ k P , b mj -1 is checkpointed. Thus the path starts at task b 0 = a i0 and includes m k P tasks, up to task b m k P -1 = a i0+m k P -1[n]
. The path includes k P checkpoints, including the checkpoint of its last task. The m th i task of the pattern is checkpointed, for 1 ≤ i ≤ k P . See Figure 3 for an illustration.

We use the following notations for a path P : for 1 ≤ i ≤ k P , we define

W P i = mi-1 j=mi-1 t i0+j[n] (with the special case m 0 = 0), C P i = c i0+mi-1[n] , R P i = r i0+mi-1[n]
(with the special case:

R P 0 = r i0-1[n]
). We define the length ( ) of a checkpoint path (P ) = k P i=1 W P i and its expected execution time, or cost (C ):

C(P ) = k P i=1 E λ W P i , C P i , R P i-1 = 1 λ + D k P i=1 e λR P i-1 e λ(W P i +C P i ) -1 P = (i0, [m1, . . . , mk P ]) ai 0 ai 0+1 ........ ai 0+m1-1[n] ci 0 +m1-1[n] .............. ........ ai 0+mkP -1[n] C P mk P W P 1 = ai 0 + • • • + ai 0+m1-1[n] W P kP Figure 3: Sequence of operations of a checkpoint path P = (i 0 , [m 1 , . . . , m k P ]
). Its length is the sum of its useful work (white boxes). Its cost corresponds to its expected execution time if a checkpoint was taken right before its start.

Definition 6 (Patterns

). A Checkpoint Pattern is a check- point path P = (i 0 , [m 1 , . . . , m k P ]) such that m k P = 0[n].
Note, for pattern P , its length is (P ) =

m k P
n T , where T = n-1 i=0 t i . Such patterns are basic blocks to define periodic schedules. We detail this relation below in Section 4.3.

Definition 7 (Slowdown of a path (or pattern)). The slowdown of a path is defined as: SD(P ) = C(P ) (P ) .

Pattern properties

Using these definitions, we show the following result:

Theorem 3. Given a schedule S of slowdown SD(S), there exists a pattern P such that SD(P) ≤ SD(S). Following the proof: Theorem 3 aims at showing the existence of a pattern whose slowdown is at most that of any algorithm (hence including optimal algorithms). To do so, we construct a sequence of patterns whose slowdown converges to the requested slowdown (Lemma 1) based on sequences taken from the algorithm S. In addition, we impose that this sequence satisfies a size property, i.e. that each element of this sequence contains at most n checkpoints (Corollary 1). This then helps to find a pattern whose slowdown is exactly that of S.

We start by proving a series of results.

Lemma 1. Given a schedule S, there exists a sequence of patterns (P r ) such that, for all r ∈ N, SD(P r ) ≤ SD(S) + 1/r.

Proof. Consider a schedule S = (m i ) i∈N of finite slowdown SD(S). There exists a checkpoint type i 0 which is taken an infinite number of times. We denote by σ i0 the function such that, for all i, σ i0 (i) is the i th occurence of checkpoint c i0 in the schedule S (we set σ i0 (0) = 0).

In the following, we partition the schedule into paths:

     M 1 = (0, [m 1 , . . . , m σi 0 (1) ]) M i = (i 0 + 1[n], [(m σi 0 (i-1)+1 -m σi 0 (i-1) ), . . . , (m σi 0 (i) -m σi 0 (i-1) )]) (∀i > 1)
Intuitively, M 1 is the beginning of the schedule until the first checkpoint of type i 0 . Then M 2 is the pattern starting right after and extending up to the second checkpoint of type i 0 , and so on. In the definition of M i , checkpoint indices are shifted to account for the location where the path starts. See Figure 4 for an illustration. By construction, each

M i is indeed a pattern, except for M 1 , which is only a path if i 0 = n -1.
We now study the slowdown SD σi 0 (i) up to the i th check- point of type i 0 , i.e., the slowdown of the first i segments. We have

SD σi 0 (i) = i k=1 σi 0 (k) j=σi 0 (k-1)+1 E λ (W S j , C S j , R S j-1 ) i k=1 m σ i 0 (k) j=m σ i 0 (k-1)+1 t j-1[n] = i k=1 C(M k ) i k=1 (M k ) = i k=1 α i,k • SD(M k ) (5)
where

α i,k = (M k ) i j=1 (Mj ) . Hence i k=1 α i,k = 1
, and we have expressed SD σi 0 (i) as a weighted average of the path slowdowns SD(M k ).

By definition of lim we have:

• lim i→∞ SD σi 0 (i) (S) ≤ lim i→∞ SD i (S) = SD(S); P: a i0+1 a i P begin a i+1 • • • a i P 1 a i+1 • • • a i0 P end P 1 : a i+1 • • • a i P 1 P 2 : a i+1 • • • a i0 P end a i0+1 a i P begin
Figure 5: From a pattern P with two identical checkpoints, c i , to its decomposition into P 1 and P 2 .

• For all r, there exists i r such that ∀i > i r ,

SD σi 0 (i) (S) ≤ lim i→∞ SD σi 0 (i) (S) + 1 r ≤ SD(S) + 1 r .
Using Equation (5), we obtain:

i k=1 α i,k SD(M k ) ≤ SD(S) + 1 r
Since this is a weighted average, it means that there exists k r , where 1 ≤ k r ≤ i such that SD(M kr ) ≤ SD(S) + 1 r . If k r = 1, or if k r = 1 and i 0 = n -1, we have found the desired pattern by letting P r = M kr . Otherwise, we redo the same proof using the truncated schedule S where we delete the first i 0 + 1 tasks. Then S is a valid schedule for a rotation of the original application, namely for the application A = (a i0+1[n] , . . . , a i0 ) ∞ , and it has same slowdown as S. The path M i of S is the same as the path M i+1 of S for all i, hence all the paths of S are patterns. We then derive the result just as above.

Lemma 2. For all pattern P , there exists a pattern P such that:

1) SD( P) ≤ SD(P); 2) P contains at most n checkpoints.

Proof. We show this result by induction on the number of checkpoints in P . Assume P = (i 0 , [m 1 , . . . , m k ]), with k > n. Then there exists i 1 < i 2 such that:

i 0 + m i1 [n] = i 0 + m i2 [n] (i.
e. the m th i1 and m th i2 tasks of the pattern are identical and equal to a i0+mi 1 -1[n] ).

We now consider the two patterns:

P 1 = (i 0 + m i1 [n], [m i1+1 -m i1 , . . . , m i2 -m i1 ]); P 2 = (i 0 + m i2 [n], [m i2+1 -m i2 , . . . , m k -m i2 , m 1 + (m k -m i2 ), . . . , m i1 + (m k -m i2 )])
Here, we have decomposed the original pattern into three paths, P begin (up to the m th i1 task), P 1 (from the next task up to the m th i2 task) and P end (from the next task up to the end of the pattern). Now, P 2 is simply the concatenation of P end followed by P begin . See Figure 5 for an illustration.

We immediately have: SD(P) = (P 1 ) (P 1 ) + (P 2 ) SD(P 1 ) + (P 2 ) (P 1 ) + (P 2 )

• SD(P 2 )

Because this is a weighted average, then min(SD(P 1 ), SD(P 2 )) ≤ SD(P). Each of these patterns has fewer checkpoints than the initial pattern, which concludes the proof.

Corollary 1. Given a schedule S, there exists a sequence of patterns ( Pr ) for all r ≥ 1 such that:

1) For all r, Pr contains at most n checkpoints; 2) SD( Pr ) ≤ SD(S) + 1/r.

This corollary is a direct consequence of Lemma 1, for the existence of a sequence that satisfies the slowdown constraint, and of Lemma 2, for transforming this sequence into a sequence of patterns that include at most n checkpoints.

Following the proof: At this point, we have constructed a sequence of patterns, whose slowdown converges towards SD(S). It remains to show the existence of a pattern that reaches the limit. In order to do so, we show that if the number of checkpoints in a pattern is bounded, then the length of the pattern has to be bounded too, otherwise its slowdown would diverge. This is the result shown in Lemma 3. Lemma 3. Given M and k, if P is a pattern with at most k checkpoints and SD(P) ≤ M , then there exists a constant W M,k such that (P) ≤ W M,k .

Proof. Given a pattern P with k checkpoints, and of length (P) = W , we let W P 1 , W P 2 , . . . , W P k denote the work between its checkpoints. By definition, k i=1 W P i = (P). Hence there exists i 1 such that W P i1 ≥ 1 k (P). We are now interested in the slowdown of the pattern:

SD(P) = k i=1 E λ (W P i , C P i , R P i-1 ) (P) ≥ E λ (W P i1 , C P i1 , R P i1-1 ) (P) ≥ E λ (W P i1 , 0, 0) (P) = 1 λ + D e λW P i 1 -1 (P) ≥ 1 λ + D e λ k (P) -1 (P) But e λ k
x -1 x tends to infinity when x tends to infinity; hence, because SD(P) ≤ M , we have that (P) is bounded by a function of M and k. Hence the result.

Proof of Theorem 3. We now conclude the proof of Theorem 3. From Corollary 1, we have a sequence of patterns ( Pr ) with at most n checkpoints and of slowdown SD( Pr ) ≤ SD(S) + 1/r ≤ 2SD(S).

From Lemma 3, there exists an upper bound such that, for all r, ( Pr ) ≤ W . We show that there is only a bounded number of patterns that satisfy this property:

• Since the length of a pattern is a multiple of T = n-1 i=0 t i , there are at most K = W T possible lengths.

• For a length kT , 1 ≤ k ≤ K, there are kn possible checkpoint locations and at most n checkpoints, hence at most kn n patterns. Hence in total, the number of possible patterns is upper bounded by K Kn n . The set {SD( Pr )|r ≥ 1} is finite and admits a minimum S min . Let r 0 be one index achieving the minimum: S min = SD( Pr0 ).

Finally, we show that S min ≤ SD(S): indeed, otherwise there would exist r such that S min > SD(S) + 1 r and we would have SD( Pr0 ) > SD( Pr ), thereby contradicting the minimality. Hence the result.

Periodic schedules

Using the properties of patterns, we are ready to derive Theorem 1. We start by rewriting the definition of periodic schedules using patterns. Indeed, the values i 0 and k 0 from Definition 4 allow us to define a pattern that is repeated all throughout the execution. We then select the pattern of minimal length that occurs as early as possible:

Definition 8 (Pattern of a periodic schedule). Given a periodic schedule S = (m 1 , m 2 , . . . ). Let (k 0 , i 0 ) be the smallest pair (for the lexicographic order) that satisfies: for all i > i 0 ,

m i -m i-1 = m i+k0 -m i+k0-1 , and m i0+k0 -m i0 = 0[n].
We say that

P S = (m i0 [n], [m i0+1 -m i0 , . . . , m i0+k0 -m i0 ])
is the pattern of the schedule.

The lexicographic order means that we select first a pattern of minimal length, and in case of a tie, the pattern that starts as early as possible.

Theorem 4 (Slowdown of a periodic schedule). Given a periodic schedule S, its slowdown is equal to the slowdown of its pattern.

Proof. Given a periodic schedule S, let

P S = (m i0 [n], [m i0+1 -m i0 , . . . , m i0+k0 -m i0 ])
be its pattern. We study the function SD i (S) by decomposing the schedule up to its i th checkpoint into three parts: a first part, up to the beginning of the pattern, i.e. up to checkpoint number i 0 , then a number k = i-mi 0 k0 of repeating patterns, then a final part (whose length is smaller than (P S ). The first and final part become negligible as i tends to infinity, hence

SD(S) = lim i→∞ SD i (S) = C(P S ) (P S ) = SD(P S )
Proof of Theorem 1. Finally, putting everything together, we obtain the final result: Theorem 3 states that there exists a pattern P whose slowdown is smaller or equal to that of an optimal schedule. In addition, Theorem 4 states that a periodic schedule whose pattern is P has a slowdown equal to that of P , hence it is optimal.

Finding the optimal pattern

In this section, we show how to compute the pattern of an optimal periodic algorithm. In the following, we say that a pattern P = (i 0 , [m 1 , m 2 , . . . , m k0 ]) is an optimal pattern, if it has minimal slowdown.

Bounding the length

Following the proof: In Lemma 3, we have shown that it was possible to bound the length of an optimal pattern, which was helpful to prove the existence of an optimal pattern. In order to derive an optimal solution, we want to use a dynamic program whose complexity depends on the number of tasks in a pattern. Unfortunately, the previous bound may lead to a number of tasks in the pattern which is not polynomially bounded. We now show how one can get a tighter bound (Theorem 5). At the end of this section, we discuss the size of this bound as a function of the problem instance.

In this section we make intensive use of the following slowdown function:

f (w, c, r) = E λ (w, c, r) w = 1 λ
+ D e λr e λ(w+c) -1 w (6) Note that we implicitly used the slowdown function when we defined the slowdown of a schedule. We have the following properties: Lemma 4. We have the following properties of the slowdown function:

1) w → f (w, c, r) has a unique minimum w c , is decreasing in the interval [0, w c ] and is increasing in the interval

[w c , ∞) 2) c → f (w, c, r) (resp. r → f (w, c, r)) are increasing functions of c (resp. r).
Proof. 2) is obvious. 1) is the result of [4, Theorem 1]. Note that a first-order approximation of w c is the well-known Young/Daly formula w c = 2c λ [START_REF] Daly | A higher order estimate of the optimum checkpoint interval for restart dumps[END_REF][START_REF] Young | A first order approximation to the optimum checkpoint interval[END_REF]. While one might want to use w c to minimize f , this is only possible for divisible applications. Here, we can checkpoint only at the end of a task, and the amount of work w can only be the sum of some task durations.

Consider a path starting after a checkpoint c i (hence with a recovery r i ), and ending in a checkpoint c j . The amount of computation w between these two checkpoints is necessarily of the form

W i,j (k) = W i,j + k × T, for some k ∈ N,

where

(i) T is the length of the iterations (T = n-1 =0 t ), and (ii) W i,j is the length between the end of task a i and the end of task a j (possibly of the next iteration), i.e.: W i,j = j =i+1 t (case j > i), or W i,j = T -W j,i (case j < i), or W i,j = T (case j = i). Additionally, k → W i,j (k) is an increasing function, hence for all pairs (r i , c j ), there exists k i,j that minimizes the function k → f (W i,j (k), c j , r i ). Let W i,j = W i,j (k i,j ). Because f (w, c j , r i ) is decreasing for w < w cj , we have W i,j -T < w cj (otherwise W i,j -T would be a better solution). Finally, we denote

M = max i w ci + T.
Then, M ≥ max i,j W i,j , and by construction, we have the following property for M :

Lemma 5. For all i, j, k 1 , k 2 such that W i,j + k 1 • T ≥ W i,j + k 2 • T ≥ M , f (W i,j + k 1 • T, c j , r i ) > f (W i,j + k 2 • T, c j , r i ).
Finally, we let k = M /T (7) denote the number of iterations that take place during time M . We are ready to bound the length between two successive checkpoints within an optimal pattern: Lemma 6. Given an optimal pattern, (i 0 , [m 1 , m 2 , . . . , m k0 ]), then for all

1 ≤ i ≤ k 0 , m i -m i-1 ≤ 2M (using m 0 = 0).
Following the proof: In order to show this result, we show that if the length between two consecutive checkpoints was larger than the bound, then we could add an intermediate checkpoint and create a pattern of smaller slowdown.

Proof. We start by a preliminary property that we use in the following: we show that if the length between two checkpoints is too high, then we can create a pattern of better slowdown by incorporating a checkpoint in the oversized interval.

Given a pattern P = (i 0 , [m 1 , m 2 , . . . , m k0 ]), and given a transformation of this pattern into a pattern P of equal length with an extra checkpoint of cost C (and recovery R) located between the (i -1) th and the i th checkpoint of P , after W units of work, one can verify that

SD(P ) -SD(P ) = E λ W P i , C P i , R P i-1 -E λ W, C, R P i-1 -E λ W P i -W, C P i , R (P ) = W P i (P ) f W P i , C P i , R P i-1 - W (P ) f W, C, R P i-1 - W P i -W (P ) f W P i -W, C P i , R (8)
Indeed, (P ) = (P ), and all inter-checkpoint intervals are identical (and have an equal cost) in P and P , except for the interval inside which the extra checkpoint has been added. We can now prove the result. We show the result by contradiction: assume there exists i ≤ k 0 such that m im i-1 > 2M . We denote by i

1 = i 0 + m i-1 -1[n] and i 2 = i 0 + m i -1[n]
• Assume first that c i2 ≥ c i1 . By monotony, r i2 ≥ r i1 . We create the pattern P such that we add to P an additional checkpoint after the task of type i 1 at the location m i-1 + n • k (which indeed corresponds to a task of type i 1 ). Then, using the properties of the slowdown function f , and because

W P i > T • k , we know that: f T • k , C P i-1 , R P i-1 ≤ f T • k , C P i , R P i-1 (growth) < f W P i , C P i , R P i-1 (shape of f ) Similarly, W P i > W P i -T • k ≥ M , then we have: f W P i -T • k , C P i , R P i-1 ≤ f W P i , C P i , R P i-1
Finally, plugging back these values into Equation (8), we obtain that P has a better slowdown than P , contradicting the optimality.

• Assume now that c i2 ≤ c i1 . By monotony, r i2 ≤ r i1 . With a similar demonstration, we show that by including a checkpoint of size c i2 at location m in • k (which indeed corresponds to a task of type i 2 ), leads to the same result. Theorem 5. There exists an optimal pattern P whose length satisfies (P ) ≤ 2nM , and which includes at most 2n 2 (k + 1) tasks.

Proof. From Lemma 2, we know that there exists an optimal pattern with at most n checkpoints. Using Lemma 6 which gives a bound on the inter-checkpoint time, we obtain the bound on the length. Thanks to Equation 7, we know that a length of M corresponds to at most k + 1 iterations (of n tasks each), which leads to the bound on the number of tasks.

We now need to check that k is polynomial in the size of the input. The size of the input is O(n max i log t i ), or equivalently O(n log T ), because the n values t i are encoded in binary. Here we make the natural assumption that c i = O(T ) and r i = O(T ) for 0 ≤ i ≤ n, meaning that the largest checkpoint/recovery is not longer than a whole iteration 2 . Recall that w ci ≈ 2ci λ [START_REF] Daly | A higher order estimate of the optimum checkpoint interval for restart dumps[END_REF][START_REF] Young | A first order approximation to the optimum checkpoint interval[END_REF], hence

M = O( maxi ci λ + T ) and k = O 1 √ λT + 1 . We obtain a polynomial value k = O(n log T ) as soon as µ = 1 λ = O(T (n log T ) 2
). This requires that the application MTBF is not too large in front of the iteration length, which makes full sense because otherwise we would not checkpoint more than very rarely, once every many iterations. In Section 4.4.2, we present a dynamic programming algorithm to compute an optimal pattern, whose complexity is polynomial in n and k . This complexity is indeed polynomial in the size of the instance under the very natural assumptions that we made.

Computing an optimal pattern

In the previous section, we have shown the existence of an optimal pattern of polynomial length. Here, we show how one can compute an optimal pattern through a dynamic programming algorithm. This dynamic programming algorithm relies upon the previous results:

• We study patterns P of length at most 2nM (thanks to Theorem 5), and we know that an optimal pattern of this length contains a polynomial number of tasks;

• We consider different initial tasks in the pattern (i 0 ∈ {0, . . . , n -1}); • We use the fact that there can be at most n checkpoints in the optimal pattern (thanks to Lemma 2).

The following lemma characterizes the minimal cost of a checkpoint path.

Lemma 7 (Minimum cost of a path). The minimal expected execution time (or cost) of a checkpoint path (i) of tasks, (ii) whose first task is a i0+1[n] , (iii) with at most b checkpoints, (iv)

2. Technically, we can relax the assumption to c i , r i = O(T n ) without increasing the problem size. where the k -1 first tasks are not checkpointed and, (v) where the last task is checkpointed, is given by;

C min (i 0 , k, , b) = min      C min (i 0 , k + 1, , b); E λ ( k i=1 t i0+i[n] , C i0+k[n] , R i0 ) + C min (i 0 + k[n], 1, -k, b -1) (9
) when > 0 and b > 0, and where we consider the following initialisation cases:

(a) C min (i 0 , + 1, , b) = 0 if = 0 ∞ otherwise (b) C(i 0 , k, > 0, 0) = ∞.
Please refer to Figure 6 for a graphical representation of

C(i 0 , k, , b).
Proof. The result is proven recursively. We start with the initialisation cases. When no checkpoint is allowed (b = 0, case (b)), it is not even possible to checkpoint the last task (as required by condition (v), so the cost is infinite. The case k = + 1 leads to tasks not being checkpointed (condition (iv)), which contradicts the fact that the last task is checkpointed (condition (v)), except when the number of tasks is zero: in this case, we assume that no task is performed in this path and no checkpoint is taken.

We now move to the general case. Considering a path that verifies the condition of the lemma, we distinguish two cases:

(i) The k th task is not checkpointed, which leads to the first k tasks not being checkpointed, hence the minimum cost is C min (i 0 , k + 1, , b); (ii) The k th task is checkpointed. The cost of the first part k -1 tasks not checkpointed followed by this k th task and its checkpoint is given by

E λ ( k i=1 t i0+i[n] , C i0+k[n] , R i0
). The cost of the rest of the path is recursively expressed as the minimal cost of a path of lengthk that starts after task i 0 + k[n] with b -1 checkpoints. We then select the case that leads to the minimal expected execution time.

Thanks to Lemma 6, we know that in an optimal pattern, there are at most 2n(k + 1) tasks between two checkpoints. So we can safely restrict our search space to k = 1 . . . 2n(k + 1) and consider that the cost for larger values of k is infinite. Hence, the previous recursive definition of the cost is applied to the design of the dynamic programming algorithm (Algorithm 1).

Algorithm 1 Finding the minimum slowdown of a pattern of size at most 2n 2 (k + 1)

1: procedure PATTERN(k , n) 2: maxK ← 2n(k + 1) 3: for i0 = 0 to n -1 do
Initialization of ProgDyn

for i0 = 0 to n -1 do Precompute k i=1 t i 0 +i[n]
13:

W [i0, 1] ← t i 0 +1[n]
14:

for k = 2 to 2n 2 (k + 1) do 15: W [i0, k] ← W [i0, k -1] + t i 0 +k[n]
16:

for = 1 to 2n 2 (k + 1) do Computing the ProgDyn 17:

for i0 = 0 to n -1 do 18:
for k = min(maxK -1, ) downto 1 do 19:

for b = 1 to n do 20:

Cmin(i0, k, , b) ← min(Cmin(i0, k + 1, , b), E λ (W [i0, k], C i 0 +k[n] , Ri 0 ) + Cmin(i0 + k[n], 1, -k, b -1)) 21: SD = ∞
Computing the minimal slowdown.

22:

T = n i=1 ti 23:
for i0 = 0 to n -1 do

24:

for m = 1 to 2n(k + 1) do 25:

SDtemp = Cmin(io, 1, mn, n)/mT 26:
if SDtemp < SD then 27:

SD ← SDtemp

28:

return SD Theorem 6. PATTERN(k , n) (Algorithm 1) returns the slowdown of the pattern of an optimal periodic schedule with time complexity O((k ) 2 n 5 ).

Proof. We use the fact that there exists an optimal periodic schedule whose pattern includes a number m × n of tasks with m ≤ 2n(k + 1) and uses at most n checkpoints (see Theorem 5). Algorithm 1 computes the minimum cost of all patterns including at most this number of tasks, then computes the minimum cost of a pattern whose number of tasks is a multiple of n. The slowdown that we look for is indeed this cost. The complexity of the algorithm derives from the loop nest necessary to recursively compute C min .

SIMULATION RESULTS

In this section, we describe the experiments conducted to compare the proposed optimal checkpointing strategy with simpler heuristics. We perform simulations on three application scenarios: two from real-life applications (neuroscience and sparse linear solver), and one using synthetic parameters. However, due to lack of space, the description of the sparse linear solver (a Krylov Subspace method called GCR [START_REF] Stanley C Eisenstat | Variational iterative methods for nonsymmetric systems of linear equations[END_REF]), together with the corresponding results, are available in the Web Supplementary Material (WSM). The experimental methodology is presented in Section 5.1. The results for the neuroscience application are detailed in Section 5.2 . The results for the synthetic application are detailed in Section 5.3.

Experimental methodology

We detail here the applications, the algorithms used in the simulations and the various settings. All algorithms have been implemented in MATLAB and R. The corresponding code is publicly available at [START_REF] Du | Code for simulations[END_REF].

Neuroscience application

For the first application scenario, we extracted data from a representative neuroscience application, Spatially Localized Atlas Network Tiles (SLANT) [START_REF] Huo | 3D whole brain segmentation using spatially localized atlas network tiles[END_REF]. This is an iterative application composed of N = 10 3 iterations, and each iteration has n = 7 tasks. These tasks are described in Table 2, with parameters taken from [START_REF] Gainaru | Profiles of upcoming hpc applications and their impact on reservation strategies[END_REF]. Table 2 reports the mean and standard deviation of the task execution times, which obey a Normal probability distribution. The Pearson correlation of the different tasks was studied in [START_REF] Gainaru | Profiles of upcoming hpc applications and their impact on reservation strategies[END_REF], which showed that the tasks are not correlated except for tasks a 0 and a 1 which are proportional. For the first set of experiments in Section 5.2.1, we consider that the tasks are deterministic (as assumed throughout this work) and use mean values as execution times (t i = µ i ). However, for the second set of experiments in Section 5.2.4, we assess the robustness of our approach and independently draw execution times from the Normal distributions for tasks a 0 , a 2 , a 3 , a 4 , a 5 , a 6 , while a 1 is set to be equal to 3.4 × a 0 due to its high correlation with a 0 . We use a downtime D = 5. Table 2: Tasks of the neuroscience application.

Synthetic application

The second application scenario is randomly generated. We consider an iterative application composed of N = 10 For this application scenario, we set checkpoint times as c i = ηt i , where η is the proportion of checkpoint time to the execution time of each task. We use r = c for the recovery time and a fixed downtime D = 5, and we conduct experiments with η = 0.1. In the WSM, we report results for another instantiation of checkpoint times, which are then taken in UNIFORM [START_REF]Online-abft: An online algorithm based fault tolerance scheme for soft error detection in iterative methods[END_REF]100], independently of the task running times.

Failure scenarios

We consider a wide range of failure rates. To allow for consistent comparisons of results across different iterative processes, we fix the probability that a failure occurs during each iteration, which we denote as p fail , and then simulate the corresponding failure rate. Formally, for a given p fail value, we compute the failure rate λ such that p fail = 1e -λT , where T is the execution time per iteration with n tasks. We conduct experiments for five p fail values: 10 -3 , 10 -2 , 10 -1 , 10 -0.5 and 10 -0.1 . For each application, these different values of p fail allow us to quantify the risk faced during execution. For example, p fail = 10 -2 means one failure will occur every 100 iterations on average. The risk is highest for p fail = 10 -0.1 which corresponds to 1 failure per 1.26 iterations on average, while the risk is lowest for p fail = 10 -3 which corresponds to 1 failure per 1, 000 iterations on average.

Table 3 provides the correspondence between p fail and actual MTBF values for the neuroscience application. The base time (without checkpoint nor failure) for one iteration of the neuroscience application is 7, 157 seconds, or almost 2 hours. Thus 1, 000 iterations will last 83 days approximately. For instance we observe that p fail = 10 -1 corresponds to one failure every 19.9 hours, which is typical of several largescale HPC machines that experience around one failure per day. Smaller values of p fail correspond to platforms with fewer failures, one per week or less. Larger values of p fail represent more failure-prone platforms, with a failure every few hours. Altogether, varying the value of p fail enables to explore a wide range of scenarios.

For the synthetic application, task execution times are defined up to a constant factor: we can envision an arbitrary unit of length, ranging from seconds to hours. Then the value of p fail is more representative of the failure rate than the MTBF, whose calculation would need to fix the execution unit. On the contrary, using p fail enables to directly quantify the risk faced by the application in terms of a failure probability per iteration. p fail 10 -3 10 -2 10 -1 10 -0.5 10 -0.1 MTBF 82.8 days 8.3 days 19.9 hours 6.3 hours 2.5 hours Table 3: MTBF for the neuroscience application.

For each experiment, the simulations are performed on 100 randomly generated instances {I 1 , . . . , I 100 }. For all i, an instance I i is a pair (S i , F i ), where S i (resp. F i ) is the application (resp. failure) scenario associated to the instance. For the neuro-science application, S i corresponds to the values presented in the previous tables, while for the synthetic application scenario, S i is randomly generated as described above.

Reference strategies

We consider four reference strategies. The first two strategies are quite natural: (i) CKPTEACHITER consists in checkpointing at the end of each iteration, that is, a checkpoint is taken after the last task a n-1 of each iteration; and (ii) CKPTEACHTASK consists in checkpointing after every task a i of every iteration.

The other two strategies are extensions of the Young/Daly approach for divisible applications where one can checkpoint at any time-step with constant cost c: then the optimal period is to checkpoint every w c = 2c λ seconds (see Lemma 4). For an iterative application, the corresponding approach is to work for w c seconds and to checkpoint at the end of the current task (and repeat). The difficulty is that c is not well-defined here, because the tasks have different checkpoint costs. With n tasks of checkpoint costs c i , 0 ≤ i < n, we take the average cost c ave = 0≤i<n ci n and denote the previous strategy using c = c ave as CKPTYDAVE 3 . Finally, the fourth strategy CKPTYDPER is a periodic extension of Young/Daly approach: it chooses the task of an iteration with minimum checkpoint size c min . Only the result of this task will (possibly) be checkpointed. Then it uses the Young-Daly formula to compute how many iterations to include in between two checkpoints, namely max 1, round wc min T .

Presenting results

We report median values in all experiments, and in the scalability analysis we use boxplots. The color chart is the following: red for CKPTEACHITER, green for CKPTEACH-TASK, blue for CKPTYDAVE and purple for CKPTYDPER.

Results for the neuroscience application

Comparison of the strategies

In Figure 7, the makespan of each reference strategy is normalized by the optimal makespan (obtained with Algorithm 1, hence the lower the better. This presentation allows us to directly quantify the performance overhead incurred by each strategy with respect to the optimal approach. Checkpointing after each task, as done by CKPTEACHTASK, gives worst performance when p fail is small (very few failures). Its performance improves significantly when the number of failures increases. This behavior is expected as it is a consequence of the very high number of checkpoints that are taken. On the contrary, the Young-Daly inspired heuristics (CKPTYDPER and CKPTYDAVE) gives almost optimal results when there are very few failures, and they get worse when the number of failures increases. Again, this behavior is expected: with very few failures, if the frequency of checkpointing is of the same order of magnitude as in the optimal solution, the fact that the checkpointing decision that is taken is not optimal has little impact, because the checkpoint overhead is very low. With numerous failures, CKPTYDPER, which is limited to at most one checkpoint per iteration, does not checkpoint often enough, and the loss in work when there is a failure gets too expensive; but CKPTYDAVE can checkpoint more frequently, and its 3. We have also experimented with two variants using c = c min = min 0≤i<n c i , and c = cmax = max 0≤i<n c i . Results are quite similar. performance degrades less severely, only because it happens to checkpoint some tasks of high checkpoint cost.

Finally CKPTEACHITER is probably the less interesting strategy as its performance is always worse than CKPTYD-PER and CKPTYDAVE. As p fail increases, its performance first improves and then gets worse: when p fail is very small, (i) it does not choose the task with smallest checkpoint size and (ii) it checkpoints too often compared to CKPTYDPER and CKPTYDAVE which would allow to checkpoint after several iterations and not just one; conversely, when p fail is very large, checkpointing once after each iteration is not enough, thus the relative cost of the CKPTEACHITER strategy increases. It is still interesting to see that the difference with CKPTYDPER remains always small, while the difference with CKPTYDAVE gets large for frequent failures. It seems that finding the smallest checkpoint size is not critical, while finding the best checkpoint frequency is more important.

For all strategies, when the frequency of failures reaches its maximal value p fail = 10 -0.1 (approximately 4 failures every 5 iterations), then all greedy heuristics perform poorly, and the optimal solution provides significant gains, even over CKPTYDAVE which is the best competitor overall.

Absolute overhead

In Figure 8, we provide absolute values for the overhead of the strategies of Figure 7, for two values of p fail . The time spent for regular periodic checkpointing, or failurefree overhead, is represented in green; it is highest for CKPTEACHTASK, as expected. The failure-induced overhead (downtime, recovery and re-execution) is represented in red; it is higher for CKPTEACHITER and CKPTYDPER. The details of the overheads are interesting: the optimal strategy is really able to trade-off checkpointing and failures; it spends roughly three times less checkpointing than the second best strategy CKPTYDAVE, for a similar failureinduced time. As observed in Figure 8, with p fail = 10 -1 , the cumulated overhead (green and red) ranges from 3.37% to 8.25%, while for p fail = 10 -0.5 , it ranges from 8.64% to 18.73% .

Scalability

In Figure 9, we study the scalability of the approach by varying the number of iterations from 10 to 1, 000. We see that the variance is high at first but the performance of each strategy stabilizes from 100 iterations on.

Robustness

In Figure 10, we study the robustness of the approach in front of variations in task execution times, which we draw from their Normal distributions as stated in Section 5.1.1. The results of CKPTEACHITER, CKPTEACHTASK and CKP-TYDPER are similar with those in Figure 7, with deterministic execution times. However, the results of CKPTYDAVE, which decides on the fly when to checkpoint, become better and close to the optimal strategy when p fail gets smaller.

Results for the synthetic application

Results for the synthetic application scenario are reported in Figures 11 and12, with two values of n. When n increases from 10 to 20, CKPTEACHITER and CKPTYDPER are closer to the optimal strategy when p fail is small (for 10 -3 and 10 -2 ), but further away when p fail is large (for 10 -1 , 10 -0.5 and 10 -0.1 ); on the contrary, CKPTYDAVE is closer to the optimal strategy for all p fail values. Altogether, the results are quite similar to those obtained with the neuroscience application.

Impact of the checkpoint time

In the above experiment, we set checkpoint times as c i = ηt i , where η is the coefficient of proportionality of checkpoint time over execution time for each task, and we conducted experiments with fixed η = 0.1. Here, we vary the value of η to study the impact of the checkpoint cost on the results. We conduct experiments with η ∈ {0.01, 0.05, 0.10, 0.15, 0.20}, thereby covering a wide range of scenarios (respectively low, balanced and high checkpointing cost). Lower checkpoint costs can be achieved with state-of-the-art in-memory or hierarchical checkpoint protocols [START_REF] Nicolae | VeloC: Towards High Performance Adaptive Asynchronous Checkpointing at Large Scale[END_REF], while larger checkpoint costs correspond to traditional protocols that save application data on remote disks. In Figure 13, we provide performance overhead with different values of η for the synthetic application with n = 10 when p fail = 10 -0.5 . This figure shows that CKPTEACHTASK and CKPTYDAVE heuristics benefits from a small η: their performance gets close to optimal when the checkpoint cost becomes negligible. On the contrary, CKPTEACHITER and CKPTYDPER heuristics have slightly worse performance compared to the optimal when η is reduced. For more details, please refer to the WSM.

Execution time of the dynamic programming algorithm

In Table 4, we report the execution time of the dynamic programming algorithm for all application scenarios. For the neuroscience application, the execution time is always below one minute. For the synthetic application, the execution time sharply increases when n doubles from 10 to 20, and reaches up to 10 minutes for p fail = 10 -3 . Table 5, explains why: the number of tasks in the optimal period, estimated by the upper bound of Theorem 5, becomes huge, while the actual number of tasks actually occurring in the optimal pattern is much lower. The bound of Theorem 5 is overly pessimistic, which increases the execution time of the dynamic programming algorithm. While 10 minutes for the algorithm is negligible in front of the 83 days of the application base time, one could easily decide to use CKPTYDPER, the best reference strategy, instead of the optimal approach. Indeed, for p fail ≤ 10 -2 , their overheads are of the same order.

p fail 10 -3 10 -2 10 -1 10 -0.5 Table 5: Number of tasks from the bound of Theorem 5 and in the optimal pattern for the neuroscience application.

Summary

Bar plots of the absolute overheads for all six applications variants and five values of p fail are provided in the WSM. In summary, no reference heuristic is able to give close-tooptimal makespan for every value of p fail : CKPTYDPER is better with very few failures, while CKPTEACHTASK and CKPTYDAVE are better when there are many failures. For these extreme scenarios, using the ad-hoc greedy heuristic is a good solution to trade-off the complexity of finding the solution with the gain in performance. However, in intermediary scenarios, the best reference heuristic can still increase the time to solution by 10% compared to the optimal one, showing the importance of computing the correct solution! Finally, when checkpoint costs can be kept very low, e.g. owing to checkpoint libraries such as VeloC [START_REF] Nicolae | VeloC: Towards High Performance Adaptive Asynchronous Checkpointing at Large Scale[END_REF], our experiments show that it is safe to use any heuristic that checkpoints sufficiently often, such as CKPTEACHTASK or CKPTYDAVE, because their performance gets close to the optimal solution. Altogether, the best competitors are CKPTYDPER and CKPTYDAVE, but none of them is always superior to the other, while our proposed optimal scheme enables us to carefully optimize the checkpoint pattern for all problem instances. As for the relevance to exascale HPC scenarios, consider for instance the synthetic application (see Figures 22 and23 of the WSM). When p fail is low (10 -3 to 10 -1 ), all methods are good, except CKPTEACHTASK whose checkpoint overhead is prohibitive. When p fail increases to 10 -0.5 , the overheads of CKPTEACHITER and CKPTYDPER are twice larger than that of CKPTYDAVE, while CKPTEACHTASK achieves intermediate results. Finally, for the highest value p fail = 10 -0.1 , the best competitor is CKPTEACHTASK, followed by CKPTYDAVE, but the difference with the optimal solution gets much larger for all methods. How realistic is the latter value p fail = 10 -0.1 for a future exascale HPC application running on 1 million cores, each with individual MTBF of 10 years? the application will experience a crash every 5 minutes; if an iteration lasts 4 minutes, this corresponds precisely to p fail = 10 -0.1 .

CONCLUSION

In this work, we have investigated checkpointing strategies for iterative applications. Each iteration is composed of a chain of tasks, and these tasks have different lengths and different checkpoint costs. Simple approaches would checkpoint either every task, or the last task at the end of each iteration. An approach inspired by the Young/Daly formula works for P Y D seconds, where P Y D comes from the Young/Daly formula with a checkpoint cost averaged over all tasks, and then checkpoints as soon as possible (and repeats). Another approach inspired by the Young/Daly formula selects the task with lowest checkpoint cost and checkpoints every p th instance of that task, where p is computed so that the period length approximately obeys the formula. But what is the optimal strategy? The main contributions of this paper are threefold: (i) we have shown that there exists a periodic strategy that is optimal; (ii) we have provided a dynamic-programming algorithm that computes the optimal period; and (iii) we have shown through a set of experiments that the gains over the other approaches are significant, and that the optimal strategy is the only one achieving a robust solution for all problem instances cases. Given the importance of iterative applications in HPC, we expect that these contributions will greatly improve the deployment of resilient solutions at scale. Future work will be devoted to dealing with iterative applications whose iterations are composed of a Directed Acyclic Graph (DAG) of tasks, not just a linear chain. Such applications are ubiquitous in real-time systems. However, the mere fact that several tasks may execute concurrently on the platform raises very complicated challenges [START_REF] Han | Checkpointing workflows for fail-stop errors[END_REF][START_REF] Han | A Generic Approach to Scheduling and Checkpointing Workflows[END_REF], and most likely only heuristic (suboptimal) algorithms will be obtained.

WEB SUPPLEMENTARY MATERIAL Optimal Checkpointing Strategies for Iterative Applications

Yishu Du, Loris Marchal, Guillaume Pallez (Aupy) and Yves Robert !

THE GCR APPLICATION

The second real-life application scenario is GCR, a Krylov Subspace method [2] solving the m-dimensional sparse linear system Ax = b. Each iteration of the method is divided into n sub-iterations, whose computational and memory requirements increase from one sub-iteration to the next. The common way to control the number of iterative steps within an acceptable range is to adopt a restart strategy [5][6][7], that is, to fix a small value n (usually much less than m, such as 10, 20, etc.). If the last n-th sub-iteration does not lead to convergence, then the approximate solution x n is used as the initial value of a new iteration, and the GCR method is restarted. The process is repeated until a satisfactory approximate solution is found, as detailed in Algorithm 1.

Algorithm 1 GCR(n)

1: x 0 , r 0 = Ax 0b, p 0 = P -1 r 0 , q 0 = Ap 0 2: for k = 1, 2, . . . , until convergence do 3:

for i = 0, 1, . . . , n -1 do 4: β= (r i ,q i ) (q i ,q i ) 4m -1 5:

x i+1 = x i + βp i 2m 6: for l = 0, 1, . . . , i do 12:

r i+1 = r i + βq i 2m 7: if r i+1 ≤ ε then 8:
α l = (ẽ,q l ) (q l ,q l ) (i + 1)(4m -1)

13:

p i+1 = e + i l=0
α l p l m + (i + 1)m 14: We consider an iterative application composed of N = 10 3 iterations, and each iteration (outer loop k) has either n = 10 or n = 20 tasks. Each task corresponds to one sub-iteration of the loop on i. The number of non-zero elements of sparse matrix A is denoted as nz(A). We assume that m = 100000, nz(A) = 27m, and the preconditioner matrix P is a diagonal matrix in the simulation. We pick (somewhat arbitrarily) 27 because it is the size of a 3 × 3 × 3 cube for a neighborhood of interactions, so the matrix has 27 diagonals (3D-stencil for Jacobi or Gauss-Seidel, typically). The number of floating-point operations for task i is f i = (6m -1)i + 19m -4 + 2nz(A), see Table 1.

q i+1 = ẽ + i l=0 α l q l m + (i + 1)m 15: [x 0 , r 0 , p 0 , q 0 ] ← [x n , r n , p n , q n ] • Yishu
We use incremental checkpointing [1,3] for GCR(n). The vectors that need to be saved if we checkpoint after task i and the corresponding size c i of the checkpoint are detailed in Table 1. Similarly, the vectors that need to be recovered if we experiment a failure task a i and the corresponding size r i of the recovery are also detailed in Table 1. We observe that c i remains constant and small for all i, owing to the incremental checkpointing technique. Of course, the larger i, the more vectors to recover, and r i is increasing. Since the checkpoint cost of each task is constant, the CKPTYDPER heuristic chooses the task with minimum recovery size r min . Only the result of this task will (possibly) be checkpointed. Then it also uses the Young-Daly formula to compute how many iterations to include in between two checkpoints, namely max 1, round wc T . We consider here that the computing platform has unit speed s = 1, so that t i = f i /s = f i . In order to test different scenarios for the relative cost of checkpoint compared to computations, we define the Communicationto-Computation Ratio (CCR) as ratio between the cost of communicating one byte to the cost of computing one flop. With the choice s = 1, the CCR is exactly the inverse of the bandwidth. Hence, from the size of the memory to checkpoint M i , we compute the time for a checkpoint: (6m -1)(n -2) + 19m -4 + 2nz(A) p n-1 , q n-1 , r n-1 , x n-1 4m p 0 , . . . , p n-1 , q 0 , . . . , q n-1 , r n-1 , x n-1 (2n + 2)m a n-1 (6m -1)(n -1) + 19m -4 + 2nz(A) p 0 , q 0 , r 0 , x 0 4m p 0 , q 0 , r 0 , x 0 4m

c i = M i × CCR. Similarly, we let r i = M i × CCR,
i a 0 19m -4 + 2nz(A) p 1 , q 1 , r 1 , x 1 4m p 0 , p 1 , q 0 , q 1 , r 1 , x 1 6m a 1 (6m -1) + 19m -4 + 2nz(A) p 2 , q 2 , r 2 , x 2 4m p 0 , p 1 , p 2 , q 0 , q 1 , q 2 ,
Table 1: Tasks composing the GCR application. When the CCR increases, CKPTEACHITER and CKPTY-DPER are further away from the optimal strategy when p fail is small (for 10 -3 and 10 -2 ), while both strategies are closer to the optimal strategy when p fail is large (for 10 -1 , 10 -0.5 and 10 -0.1 ); CKPTEACHTASK and CKPTYDAVE are further away from the optimal strategy for all p fail values.

In addition, when n increases from 10 to 20, CKPTEA-CHITER, CKPTYDPER and CKPTYDAVE are closer to the optimal strategy, while CKPTEACHTASK keeps a high overhead (with a ratio up to 1.5 to the optimal.

ADDITIONAL EXPERIMENTS WITH SYNTHETIC APPLICATIONS

Impact of Communication-to-Computation Ratio (CCR)

An important factor that influences the performance of checkpointing strategies, and more precisely of the checkpointing and recovery overheads, is the data-intensiveness of the application. For the synthetic application, in order to test the impact of the correlation between checkpoint costs and task running times on the strategies, we let the checkpoint time move from dependent to independent of the task running time (see Figures 11 and12).

Impact of checkpoint time

In section, we vary the checkpointing cost of each task in order to study its influence on the results. We have two settings for the checkpointing cost. First, we consider that the checkpointing time is proportional to the task execution time, as assumed in the main paper: C i = ηt i . We have previously considered η = 0.1, and we conduct here experiments with η ∈ {0.01, 0.05, 0.10, 0.15, 0.20} thereby covering a wide range of scenarios (respectively low, balanced and high checkpointing cost). Lower checkpoint costs can be achieved with state-of-the-art in-memory or hierarchical checkpoint protocols [4], while larger checkpoint costs correspond to traditional protocols that save application data on remote disks. Second, as in the previous section of this supplementary material, we set checkpoint times taken uniformly at random in some interval. We now set checkpoint times taken in UNIFORM[100η, 1000η] to also cover wider range of scenarios (recall that the average task length is 550 seconds).

Results for varying the value of η are reported in Figures 13 to 17 with the five p fail values and the two checkpoint settings (proportional or uniform).

We first observe that the distribution of checkpoint times (proportional to the task execution time or uniform) has very little impact of the results. However, the heuristics do behave very differently when varying checkpoint time, and their behavior also depends on the failure probability.

When p fail is small (10 -3 or 10 -2 ), we note that the CKPTEACHITER heuristic (in red) performs worse and further away from the optimal strategy when η gets larger; for larger values of p fail , its performance is slightly improved when η gets larger.

The performance of the CKPTEACHTASK (in green) heuristic becomes worse and further away from the optimal strategy when η gets larger for all p fail values.

When p fail is very small (10 -3 ), the performance CKP-TYDAVE heuristic (in blue) is quite close with the optimal strategy for all values of η; when p fail is small (10 -2 or 10 -1 ), it is improved when η gets smaller. Finally, when p fail is large (10 -0.5 or 10 -0.1 ), the performance of CKPTYDAVE slightly varies with η, but it is almost optimal for small values of η.

The performance of the CKPTYDPER heuristic (in purple) is very close to the optimal strategy when p fail is small (10 -3 or 10 -2 ). For larger failure probabilities, its performance is improved when η gets larger.

Overall, heuristics CKPTEACHTASK and CKPTYDAVE benefits from a very small checkpoint time: when the overhead due to checkpointing is negligible, these heuristics reach an optimal makespan.

ABSOLUTE OVERHEAD FOR ALL SCENARIOS

Figure 1 :

 1 Figure 1: Notations drawn in a schedule for an application with n = 3 tasks.

Figure 4 :

 4 Figure 4: Partitioning the schedule into patterns around the checkpoints c 2 (yellow).

Figure 6 :

 6 Figure 6: Illustration of the minimum expected execution time C min (i 0 , k, , b) of a series of tasks as characterized by Lemma 7.

9 : 10 : 11 :

 91011 Cmin(i0, min(maxK , + 1), , b) ← ∞ for k = 1 to min(maxK , ) do Cmin(i0, k, , 0) ← ∞ 12:

Figure 7 :

 7 Figure 7: Normalized performance overhead with different failure probabilities (neuroscience).

p fail = 10 - 1 p fail = 10 -Figure 8 :

 101108 Figure 8: Bar plots for absolute overhead (neuroscience).

Figure 9 :Figure 10 :

 910 Figure 9: Box plots for normalized performance overhead: varying the number of iterations (neuroscience, p fail = 10 -0.5 ).

Figure 11 :

 11 Figure 11: Normalized performance overhead with different failure probabilities (synthetic, n = 10).

Figure 12 :

 12 Figure 12: Normalized performance overhead with different failure probabilities (synthetic, n = 20).

Figure 13 :

 13 Figure 13: Performance overhead with different values of η for the synthetic application with n = 10, c i = ηt i and p fail = 10 -0.5 .

Figure 2 :

 2 Figure 2: Performance overhead with different failure probabilities for GCR(n), with n=10 and CCR = 0.2.

Figure 3 :

 3 Figure 3: Performance overhead with different failure probabilities for GCR(n), with n=10 and CCR = 1.

Figure 4 :

 4 Figure 4: Performance overhead with different failure probabilities for GCR(n), with n=10 and CCR = 5.

Figure 5 :Figure 6 :Figure 7 :

 567 Figure 5: Performance overhead with different failure probabilities for GCR(n), with n=10 and CCR = 10.

Figure 8 :Figure 9 :Figure 10 :

 8910 Figure 8: Performance overhead with different failure probabilities for GCR(n), with n=20 and CCR = 1.

Figure 11 :

 11 Figure 11: Performance overhead with different failure probabilities for the synthetic application with n = 10 and c i drawn in UNIFORM[10, 100].

Figure 12 :

 12 Figure 12: Performance overhead with different failure probabilities for the synthetic application with n = 20 and c i drawn in UNIFORM[10, 100].

Figure 13 :Figure 14 :

 1314 Figure 13: Performance overhead with different values of η for the synthetic application with n = 10 and p fail = 10 -3 .

Figure 15 :

 15 Figure 15: Performance overhead with different values of η for the synthetic application with n = 10 and p fail = 10 -1 .

Figure 16 :Figure 17 :

 1617 Figure 16: Performance overhead with different values of η for the synthetic application with n = 10 and p fail = 10 -0.5 .

p fail = 10 - 3 p 2 p fail = 10 - 1 p 5 p fail = 10 -Figure 18 :

 103210151018 Figure 18: Bar plots for absolute overhead (neuroscience).

p fail = 10 - 3 p 2 p fail = 10 - 1 p 5 p fail = 10 -Figure 19 :

 103210151019 Figure 19: Bar plots for absolute overhead (GCR, n = 10 and CCR = 0.1).

p fail = 10 - 3 p 2 p fail = 10 - 1 p 5 p fail = 10 -Figure 20 :

 103210151020 Figure 20: Bar plots for absolute overhead (GCR, n = 10 and CCR = 1).

p fail = 10 - 3 p 2 p fail = 10 - 1 p 5 p fail = 10 -Figure 21 :

 103210151021 Figure 21: Bar plots for absolute overhead (GCR, n = 10 and CCR = 10).

p fail = 10 - 3 p 2 p fail = 10 - 1 p 5 p fail = 10 -Figure 22 :

 103210151022 Figure 22: Bar plots for absolute overhead (synthetic, n = 10 and c i = 0.1 * t i ).

p fail = 10 - 3 p 2 p fail = 10 - 1 p 5 p fail = 10 -Figure 23 :

 103210151023 Figure 23: Bar plots for absolute overhead (synthetic, n = 10 and c i drawn in UNIFORM[10, 100].

Table 1 :

 1 Summary of main notations.

	Application

Table 4 :

 4 Execution time (seconds) of the dynamic programming algorithm.

	Neuroscience Synthetic, n = 10 Synthetic, n = 20	5.46 27.49 550.89	0.88 5.16 95.49	0.21 1.27 46.75	0.21 1.25 43.37	10 -0.1 0.22 1.33 46.07
	p fail Neuroscience: Bound Neuroscience: Optimal pattern Synthetic, n = 10: Bound Synthetic, n = 10: Optimal pattern Synthetic, n = 20: Bound Synthetic, n = 20: Optimal pattern	10 -3 980 14 1800 150 5600 200	10 -2 392 7 800 50 2400 180	10 -1 196 7 400 50 1600 20	10 -0.5 196 7 400 20 1600 20	10 -0.1 196 7 400 10 1600 20

  Du is with Tongji University, Shanghai, China. Loris Marchal and Yves Robert are with LIP, École Normale Supérieure de Lyon, CNRS & Inria, France. Guillaume Pallez (Aupy) is with Inria & Université de Bordeaux, France. Yishu Du is also with LIP, ENS Lyon. Yves Robert is also with University of Tennessee Knoxville, USA. Contact: Yves.Robert@ens-lyon.fr.

  where the size of the memory to recover is M i . Results for the GCR application are reported in Figures 1 to 10, with two values of n and five values of CCR.

	Task	Floating point operations f i	Vectors to checkpoint	M i	Vectors to recover	M
			We {0.1, 0.2, 1, 5, 10}, thereby covering a wide range conducted experiments with CCR ∈ of scenarios (respectively low, balanced and high communication cost).

Acknowledgments

We would like to thank the reviewers for their comments and suggestions, which greatly helped improve the final version of the paper.

BIOGRAPHIES