Valentin Le Fèvre

Thomas Herault

Yves Robert

Aurelien Bouteiller

Atsushi Hori

George Bosilca

Jack Dongarra

Comparing the performance of rigid, moldable and grid-shaped applications on failure-prone HPC platforms

This paper compares the performance of different approaches to tolerate failures for applications executing on large-scale failure-prone platforms. We study (i) Rigid applications, which use a constant number of processors throughout execution; (ii) Moldable applications, which can use a different number of processors after each restart following a fail-stop error; and (iii) GridShaped applications, which are moldable applications restricted to use rectangular processor grids (such as many dense linear algebra kernels). We start with checkpoint/restart, the de-facto standard approach. For each application type, we compute the optimal number of failures (i.e. that maximizes the yield of the application) to tolerate before relinquishing the current allocation and waiting until a new resource can be allocated, and we determine the optimal yield that can be achieved. For GridShaped applications, we also investigate Application Based Fault Tolerance (ABFT) techniques and perform the same analysis, computing the optimal number of failures to tolerate and the associated yield. We instantiate our performance model with realistic applicative scenarios and make it publicly available for further usage. We show that using spare nodes grants a much better yield than currently used strategies that restart after each failure. Moreover, the yield is similar for Rigid, Moldable and GridShaped applications, while the optimal number of failures to tolerate is very high, even for a short wait time in between allocations. Finally, Moldable applications have the advantage to restart less frequently than Rigid applications.

Introduction

Consider a long-running job that requests N processors from the batch scheduler. Resilience to fail-stop errors 1 is typically provided by a Checkpoint/Restart (C/R) mechanism, the de-facto standard approach for High-Performance Computing (HPC) applications. After each failure on one of the nodes used by the application, the application restarts from the last checkpoint but the number of available processors decreases, assuming the application can continue execution after a failure (e.g., using ULFM [START_REF] Bland | Postfailure recovery of MPI communication capability: Design and rationale[END_REF]). Until which point should the execution proceed before requesting a new allocation with N fresh nodes from the batch scheduler?

The answer depends upon the nature of the application. For a Rigid application, the number of processors must remain constant throughout the execution. The question is then to decide the number F of processors (out of the N available initially) that will be used as spares. With F spares, the application can tolerate F failures. The application always executes with N -F processors: after each failure, then it restarts from the last checkpoint and continues executing with N -F processors, the faulty processor having been replaced by a spare. After F failures, the application stops when the (F + 1)st failure strikes, and relinquishes the current allocation. It then asks for a new allocation with N processors, which takes a wait time, D, to start (as other applications are most likely using the platform concurrently). The optimal value of F obviously depends on the value of D, in addition to the application and resilience parameters. The wait time typically ranges from several hours to several days if the platform is over-subscribed (up to 10 days for large applications on the K-computer [START_REF] Yamamoto | The K computer Operations: Experiences and Statistics[END_REF]). The metric to optimize here is the (expected) application yield, which is the fraction of useful work per second, averaged over the N resources, and computed in steady-state mode (expected value for multiple batch allocations of N resources).

For a Moldable application, the problem is different: here we assume that the application can use a different number of processors after each restart. The application starts executing with N processors; after the first failure, the application recovers from the last checkpoint and is able to continue with only N -1 processors, albeit with a slowdown factor N -1 N . After how many failures F should the application decide to stop2 and accept to produce no progress during D, in order to request a new allocation? Again, the metric to optimize is the application yield.

Finally, consider an application which must have a given shape (or a set of given shapes) in terms of processor layout. Typically, these shapes are dictated by the application algorithm. In this paper, we use the example of a GridShaped application, which is required to execute on a rectangular processor grid whose size can dynamically be chosen. Most dense linear algebra kernels (matrix multiplication, LU, Cholesky and QR factorizations) are GridShaped applications, and perform more efficiently on square processor grids than on elongated rectangle ones. The application starts with a (logical) square p × p grid of N = p 2 processors. After the first failure, execution continues on a p × (p -1) rectangular grid, keeping p -1 processors as spares for the next p -1 failures (Figure 1,b). After p failures, the grid is shrunk again to a (p -1) × (p -1) square grid (see Figure 1(d)), and so on. We address the same question: after how many failures F should the application stop working on a smaller processor grid and request a new allocation, in order to optimize the application yield?

Many GridShaped applications can also be protected from failures by using Algorithm-Based Fault Tolerant techniques (ABFT), instead of Checkpoint/Restart (C/R). ABFT is a widely used approach for linear algebra kernels [START_REF] Huang | Algorithm-Based Fault Tolerance for Matrix Operations[END_REF][START_REF] Bosilca | Algorithm-based fault tolerance applied to high performance computing[END_REF]. We present how we can model ABFT techniques instead of C/R and we perform the same analysis: we compute the optimal number of failures to tolerate before relinquishing the allocation, as well as the associated yield.

Altogether, the major contribution of this paper is to present a detailed performance model and to provide analytical formulas for the expected yield of each application type. We instantiate the model for several applicative scenarios, for which we draw comparisons across application types. Our model is publicly available [START_REF]Simulation Software[END_REF] so that more scenarios can be explored. Notably, the paper quantifies the optimal number of spares for the optimal yield, and the optimal length of a period between two full restarts; it also qualifies how much the yield and total work done within a period are improved by deploying Moldable applications w.r.t. Rigid applications. Finally, for GridShaped applications, the paper compares the use of C/R and ABFT under various frameworks. Our main result is that using spare nodes grants a significantly higher yield for every kind of application, even for short wait times. We also show that the number of failures to tolerate before resubmitting the application is very high, meaning that it is possible that the application never needs to be resubmitted. Finally, we show the advantage of Moldable applications: while the yield obtained is similar for Rigid and Moldable applications, Moldable applications can tolerate more failures and thus restart more rarely than Rigid ones. This means that a Moldable application is more likely to terminate before being resubmitted.

The rest of the paper is organized as follows. Section 2 provides an overview of related work. Section 3 is devoted to formally defining the performance model. Section 4 provides formulas for the yield of Rigid, Moldable and GridShaped applications using the C/R approach, and for the yield of GridShaped applications using the ABFT approach . All these formulas are instantiated through the applicative scenarios in Section 5, to compare the different results. Finally, Section 6 provides final remarks and hints for future work.

Related work

We first survey related work on checkpoint-restart in Section 2.1. Then we discuss previous contributions on Moldable applications in Section 2.2. Finally, we provide a few references for ABFT techniques in Section 2.3

Checkpoint-restart

Checkpoint/restart (C/R) is the most common strategy employed to protect applications from underlying faults and failures on HPC platforms. Generally, C/R periodically outputs snapshots (i.e., checkpoints) of the application global distributed state to some stable storage device. When a failure occurs, the last stored checkpoint is retrieved and used to restart the application.

A widely-used approach for HPC applications is to use a fixed checkpoint period (typically one or a few hours), but it is sub-optimal. Instead, applicationspecific metrics can (and should) be used to determine the optimal checkpoint period. The well-known Young/Daly formula [START_REF] Young | A first order approximation to the optimum checkpoint interval[END_REF][START_REF] Daly | A higher order estimate of the optimum checkpoint interval for restart dumps[END_REF] yields an application optimal checkpoint period, √ 2µC seconds, where C is the time to commit a checkpoint and µ the application Mean Time Between Failures (MTBF) on the platform. We have µ = µ ind N , where N is the number of processors enrolled by the application and µ ind is the MTBF of an individual processor [START_REF]Fault-Tolerance Techniques for High-Performance Computing[END_REF].

The Young/Daly formula minimizes platform waste, defined as the fraction of job execution time that does not contribute to its progress. The two sources of waste are the time spent taking checkpoints (which motivates longer checkpoint periods) and the time needed to recover and re-execute after each failure (which motivates shorter checkpoint periods). The Young/Daly period achieves the optimal trade-off between these sources to minimize the total waste.

Moldable and GridShaped applications

Rigid and Moldable applications have been studied for long in the context of scientific applications. A detailed survey on various application types (Rigid, Moldable, malleable) was conducted in [START_REF] Dutot | Scheduling parallel tasks approximation algorithms[END_REF]. Resizing application to improve performance has been investigated by many authors, including [START_REF] Moreira | Dynamic resource management on distributed systems using reconfigurable applications[END_REF][START_REF] Cirne | Using moldability to improve the performance of supercomputer jobs[END_REF][START_REF] Sudarsan | Dynamic resizing of parallel scientific simulations: A case study using LAMMPS[END_REF][START_REF] Sudarsan | Design and performance of a scheduling framework for resizable parallel applications[END_REF] among others. A related recent study is the design of a MPI prototype for enabling tolerance in Moldable MapReduce applications [START_REF] Guo | Fault tolerant MapReduce-MPI for HPC clusters[END_REF].

The TORQUE/Maui scheduler has been extended to support evolving, malleable, and Moldable parallel jobs [START_REF] Prabhakaranw | Dynamic Resource Management and Job Scheduling for High Performance Computing[END_REF]. In addition, the scheduler may have system-wide spare nodes to replace failed nodes. In contrast, our scheme does not assume a change of behavior from the batch schedulers and resource allocators, but utilizes job-wide spare nodes: a node set including potential spare nodes is allocated and dedicated to a job at the time of scheduling, that can be used by the application to restart within the same job after a failure. At the application level, spare nodes have become common in HPC centers since more than a decade [START_REF] Wang | Proactive processlevel live migration in hpc environments[END_REF]. Recent work aims at sharing spare-nodes across the whole platform to achieve a better global resource utilization [START_REF] Prabhakaran | Efficient fault tolerance through dynamic node replacement[END_REF].

An experimental validation of the feasibility of shrinking application on the fly is provided in [START_REF] Ashraf | Shrink or substitute: Handling process failures in HPC systems using in-situ recovery[END_REF]. In this paper, the authors used an iterative solver application to compared two recovery strategies, shrinking and spare node substitution. They use ULFM, the fault-tolerant extension of MPI that offers the possibility of dynamically resizing the execution after a failure. Finally, in [START_REF] Fang | Towards understanding post-recovery efficiency for shrinking and non-shrinking recovery[END_REF][START_REF] Hori | Sliding substitution of failed nodes[END_REF], the authors studied Moldable and GridShaped applications that continue executing after some failures. They focus on the performance degradation incurred after shrinking or spare node substitution, due to less efficient communications (and in particular collective communications). A major difference with our work is that these studies focus on recovery overhead and do not address overall performance nor yield.

ABFT

ABFT stands for Algorithm-Based Fault Tolerant techniques. It is a widely used approach for linear algebra kernels. Since the pioneering paper of Huang and Abraham [START_REF] Huang | Algorithm-Based Fault Tolerance for Matrix Operations[END_REF], ABFT protection has been successfully applied to dense LU [START_REF] Du | Algorithm-based fault tolerance for dense matrix factorizations[END_REF], LU with partial pivoting [START_REF] Yao | Detection of soft errors in LU decomposition with partial pivoting using algorithm-based fault tolerance[END_REF], Cholesky [START_REF] Hakkarinen | Fail-stop failure algorithm-based fault tolerance for cholesky decomposition[END_REF] and QR [START_REF] Du | Soft error resilient QR factorization for hybrid system with GPGPU[END_REF] factorizations, and more recently to sparse kernels like SpMxV (matrix-vector product) and triangular solve [START_REF] Shantharam | Fault tolerant preconditioned conjugate gradient for sparse linear system solution[END_REF].

In a nutshell, ABFT consists of adding a few checksum vectors as extra columns of each tile, which will be used to reconstruct data lost after a failure. The checksums are maintained by applying the kernel operations to the extra columns, just as if they were matrix elements. The beauty of ABFT is that these checksums can be used to recover from a failure, without any rollback nor re-execution, by reconstructing lost data and proceeding onward. In addition, the failure-free overhead induced by ABFT is usually small, which makes it a good candidate for the design of fault-tolerant linear algebra kernels. We refer to [START_REF] Bosilca | Algorithm-based fault tolerance applied to high performance computing[END_REF][START_REF] Du | Algorithm-based fault tolerance for dense matrix factorizations[END_REF] for recent surveys on the approach. Altogether, we are not aware of any previous study aiming at determining the optimal number of spares as a function of the downtime and resilience parameters, for a general divisible-load application of either type (Rigid,, Moldable or GridShaped).

Performance model

This section reviews the key parameters of the performance model. Some assumptions are made to simplify the computation of the yield. We discuss possible extensions in Section 6.

Application/platform framework

We consider perfectly parallel applications that execute on homogeneous parallel platforms. Without loss of generality, we assume that each processor has unit speed: we only need to know that the total amount of work done by p processors within T seconds requires p q T seconds with q processors.

Mean Time Between Failures (MTBF)

Each processor is subject to failures which are IID (independent and identically distributed) random variables3 following an Exponential probability distribution of mean µ ind , the individual processor MTBF. Then the MTBF of a section of the platform comprised of i processors is given by µ i = µ ind i [START_REF]Fault-Tolerance Techniques for High-Performance Computing[END_REF].

Checkpoints

Processors checkpoint periodically, using the optimal Young/Daly period [START_REF] Young | A first order approximation to the optimum checkpoint interval[END_REF][START_REF] Daly | A higher order estimate of the optimum checkpoint interval for restart dumps[END_REF]: for an application using i processors, this period is √ 2C i µ i , where C i is the time to checkpoint with i processors. We consider two cases to define C i . In both cases, the overall application memory footprint is considered constant at Mem tot , so the size of individual checkpoints is inversely linear with the number of participating/surviving processors. In the first case, the I/O bandwidth is the bottleneck (which is often the case in HPC platforms -it takes only a few processors to saturate the I/O bandwidth); then the checkpoint cost is constant and given by C i = Memtot τio , where τ io is the aggregated I/O bandwidth. In the second case, the processor network card is the bottleneck, and the checkpoint cost is inversely proportional to number of active processors:

C i = Memtot
τxnet×i , where τ xnet is the available network card bandwidth, i.e. the bandwidth available for one and only one processor, and Memtot i the checkpoint size. In this second case, the cost of checkpointing (and recovery) increases when the number of processors decreases, since each processor has to read more and more application data from stable storage: this does not impact Rigid applications, but it may represent an important overhead for Moldable and GridShaped applications.

We denote the recovery time with i processors as R i . For all simulations we use R i = C i , assuming that the read and write bandwidths are identical.

Wait Time

Job schedulers allocate nodes to given applications for a given time. They aim at optimizing multiple criteria, depending on the center policy. These criteria include fairness (balancing the job requests between users or accounts), platform utilization (minimizing the number of resources that are idling), and job makespan (providing the answer as fast as possible). Combined with a high resource utilization (node idleness is usually in the single digit percentage for a typical HPC platform), a job has to wait a Wait Time (D) between its submission and the beginning of its execution.

Job schedulers implement the selection based on the list of submitted jobs, each job defining how many processors it needs and for how long. That definition is, in most cases, unchangeable: an application may use less resources than what it requested, but the account will be billed for the requested resources, and it will not be able to re-dimension the allocation during the execution.

Thus, if after some failures, an application has not enough resources left to efficiently complete, it will have to relinquish the allocation, and request a new one. During the wait time D, the application does not execute any computation to progress towards completion: its yield is zero during D seconds.

Objective.

We consider a long-lasting application that requests a resource allocation with N processors. We aim at deriving the optimal number of failures F that should be tolerated before paying the wait time and requesting a new allocation. We aim at maximizing the yield Y of the application, defined as the fraction of time during the allocation length and wait time where the N resources perform useful work. More precisely, the yield is defined by the following formula: Y = total time spent computing for all processors number of processors × flow time since start of application .

. Of course a spare does not perform useful work when idle, processor do not compute when checkpointing or recovering, re-execution nodes not account for actual work, and no processor is active during wait time. All this explains that the yield will always be smaller than 1. We will derive the value of F that maximizes Y for the three application types using C/R (and both C/R and ABFT for GridShaped applications).

Expected yield

This section is the core of the paper. We compute the expected yield for each application type, Rigid (Section 4.1), Moldable (Section 4.2) and GridShaped (Section 4.3), using the C/R approach, and compare it with ABFT for GridShaped in Section 4.4.

Rigid application

We first consider a Rigid application that can be parallelized at compiletime to use any number of processors but cannot change this number until it reaches termination. There are N processors allocated to the application. We use N -F for execution and keep F as spares. The execution is protected from failures by checkpoints of duration C N -F . Each failure striking the application will incur an in-place restart of duration R N -F , using a spare processor to replace the faulty one. However, when the (F + 1) st failure strikes, the job will have to stop and perform a full restart, waiting for a new allocation of N processors to be granted by the job scheduler.

We define T R as the expected duration of an execution period until the (F + 1) st failure strikes. The first failure is expected to strike after µ N seconds, the second failure µ N -1 seconds after the first one, and so on. We relinquish the allocation after F + 1 failures and wait some time D. As faults can also happen during the checkpoint and the recovery, this means that:

T R = N -F i=N µ i + D. (1)
What is the total amount of work W R computed during a period T R ? During the sub-period of length µ i , there are

µi √ 2C N -F µ N -F checkpoints, each of length C N -F .
The failure hits one of live processors, either a working processor or a spare. In both cases, the number of live processors decreases. if the failure hits a spare, it has no immediate impact on the application, except that the number of available spares decreases. If the failure hits a working processor, which happens with probability N -F i , some work is lost, and a restart is needed. During each sub-period, and weighting the cost by the probability of the failure hitting a working processor during that sub-period, the work lost by each processor by the end of the sub-period is in average [START_REF]Fault-Tolerance Techniques for High-Performance Computing[END_REF] for further details). Each time there is a failure, the next sub-period is thus started by a restart R N -F with probability N -F i+1 , except for the first sub-period which always starts by a restart (it corresponds to reading input data at the beginning of the allocation). All in all, during the sub-period of length µ i with i = N , each processor works during

√ 2C N -F µ N -F 2 • N -F i (see
1 1 + C N -F √ 2C N -F µ N -F • µ i -R N -F • N -F i + 1 - 2C N -F µ N -F 2 • N -F i seconds.
The first fraction corresponds to the proportion of the time that is used for useful computations and not for checkpointing. This fraction is actually:

period time period time+checkpoint time = √ 2C N -F µ N -F √ 2C N -F µ N -F +C N -F
which is equivalent to the former fraction after simplification. Finally, each processor works during

1 1 + C N -F √ 2C N -F µ N -F • µ N -R N -F - 2C N -F µ N -F 2 • N -F i
seconds in the first sub-period of length µ N as it always starts by reading the initial data. There are N -F processors at work, hence, re-arranging terms, we obtain that

W R = N -F 1 + C N -F √ 2C N -F µ N -F • N -F i=N µ i -(R N -F + 2C N -F µ N -F 2 ) • N -F i (2) Indeed, the factor for R N -F is N -F
i+1 for all subperiods except the first one, i.e.

N -F ≤ i ≤ N -1 , which means it is equivalent to N -F i with N -F +1 ≤ i ≤ N . Moreover, N -F
N -F = 1 which is the corresponding factor for the first subperiod, so by summing all the terms we get to

N -F i=N R N -F • N -F i .
During the whole duration T R of the period, in the absence of failures and protection techniques, the application could have used all the N processors to compute continuously. Thus the effective yield with protection for the application during T R is reduced to Y R :

Y R = W R N • T R

Moldable application

We now consider a Moldable application that can use a different number of processors after each restart. The application starts executing with N processors. After the first failure, the application recovers from the last checkpoint and is able to continue with only N -1 processors, after paying the restart cost R N -1 , albeit with a slowdown factor N -1 N of the parallel work per time unit. After F + 1 failures, the application stops, just as it was the case for a Rigid application.

We define T M as the expected duration of an execution period until the (F + 1) st failure strikes. The length of a period is

T M = N -F i=N µ i + D, (3)
the same as for Rigid applications. However, for the total amount of work W M during a period, things are slightly different. To compute the total amount of work W M during a period T M , we proceed as before and consider each sub-period. During the sub-period of length µ i , there are µi √ 2Ciµi checkpoints, each of length C i . There is also a restart R i at the beginning of each sub-period, and the average time lost is

√ 2Ciµi 2
. The probability that the failure strikes a working processor is always 1, because all alive processors are working during each sub-period. Overall, there are i processors at work during the sub-period of length µ i , and each of them actually works during

µ i -R i - √ 2Ciµi 2 1 + Ci √ 2Ciµi
seconds. Altogether, we derive that

W M = N -F i=N i × µ i -R i - √ 2Ciµi 2 1 + Ci √ 2Ciµi (4)
The yield of the Moldable application is then:

Y M = W M N • T M 4.3.
GridShaped application Next, we consider a GridShaped application, defined as a moldable execution which requires a rectangular processor grid. Here we mean a logical grid, i.e. a layout of processes whose communication pattern is organized as a 2D grid, not a physical processor grid where each processor has four neighbors directly connected to it. Indeed, there is little hope to use physical grids today. Some modern architectures have a multi-dimensional torus as physical interconnexion network, but the job scheduler never guarantees that allocated nodes are adjacent, let alone are organized along an actual torus. This means that the actual time to communicate with a logically adjacent processor is variable, depending upon the length of the path that connects them, and also upon the congestion of the links within that path (these links are likely to be shared by other paths). Other architecture communicate through a hierarchical interconnexion switch, hence a 2D processor grid is not meaningful for such architectures. Altogether, this explains that one targets logical process grids, not physical processor grids. Now why do the application needs a process grid? State-the-art linear algebra kernels such as matrix product, LU, QR and Cholesky factorizations, are most efficient when the data is partitioned across a logical grid of processes, preferably a square, or at least a balanced rectangle of processes [START_REF] Petitet | Parallel and distributed scientific computing: A numerical linear algebra problem solving environment designer's perspective[END_REF]. This is because the algorithms are based upon outer-product matrix updates, which are most efficiently implemented on (almost) square grids. Say you start with 64 working processors, arranged as a 8 × 8 process grid. When one processor fails, the squarest grid would be 63 = 9 × 7, and then after a second failure we get 62 = 31 × 2 which is way too elongated to be efficient. After the first failure, it is more efficient to use a 8 × 7 grid and keep 7 spares; then we use spares for the next 7 failures, after which we shrink to a 7 × 7 grid (and keep 7 spares), and so on.

For the analysis, assume that the application starts with a square p × p grid of N = p 2 processors. After the first failure, execution continues on a p × (p -1) rectangular grid, keeping p -1 processors as spares for the next p -1 failures. After p failures, the grid is shrunk again to a (p-1)×(p-1) square grid, and the execution continues on this reduced-size square grid. After how many failures F should the application stop, in order to maximize the application yield?

The derivation of the expected length of a period and of the total work is more complicated for GridShaped than for Rigid and Moldable. To simplify the presentation, we outline the computation of the yield only for values of F of the form 2 , meaning that we stop shrinking and request a new allocation when reaching a square grid of size (p -f ) × (p -f ) for some value of f < p to be determined. Obviously, we could stop after any number of faults F , and the publicly available software [START_REF]Simulation Software[END_REF] shows how to compute the optimal value of F without any restriction.

F = 2pf -f 2 , hence p 2 = F + (p -f )
We start by computing an auxiliary variable: on a (p 1 -1) × p 2 grid with p 1 ≥ p 2 , the expected time to move from p 2 -1 spare nodes to no spare nodes will be denoted by T G (p 1 , p 2 ). It means that the number of computing nodes never changes and is (p 1 -1)p 2 . It always starts with a restart R (p1-1)p2 , because having p 2 -1 spare nodes means that a failure just occurred on one of the p 1 p 2 processors that were working just before that failure, and we had to remove a row from the process grid. As previously this time is the sum of all the intervals between each failure, namely:

T G (p 1 , p 2 ) = (p1-1)p2 i=p1p2-1 µ i .
Going from p 2 processors down to (p -f ) 2 processors thus require a time

T G = µ p 2 + f -1 g=0 T G (p -g, p -g) + T G (p -g, p -g -1) + D.
We simply add the time before the first failure and the wait time to the time needed to move from a grid of size p 2 to (p -1) 2 , to (p -2) 2 , . . . , to (p -f ) 2 .

Similarly, we define the auxiliary variable W G (p 1 , p 2 ) as the parallel work when moving from a (p 1 -1) × p 2 grid with p 2 -1 spare nodes to a (p 1 -1) × p 2 grid with no spare node, where p 1 ≥ p 2 . There are (p 1 -1)p 2 processors working during all sub-periods. Without restart and re-execution, this work is

(p 1 -1)p 2 • (p1-1)p2
i=p1p2-1 µ i . Any failure which hits one of the working processors calls for a restart R (p1-1)p2 and incurs some lost work:

√ 2C (p 1 -1)p 2 2
in average. The first sub-period starts with a restart R (p1-1)p2 ,because the application (distributed on a grid of p 1 × p 2 was previously hit by a failure, except if this is the beginning of a new allocation (which case will be dealt with later on). Then, for all other sub-periods, a restart is taken if one of (p 1 -1)p 2 computing processors was hit by a failure. This means that the sub-period with i processors alive (of length µ i ) starts with a restart R (p1-1)p2 with probability (p1-1)p2 i+1 , for i ≤ p 1 p 2 -2. Similarly, for all sub-periods with i processors alive, we lose the expected compute time

√ 2C (p 1 -1)p 2 µ (p 1 -1)p 2 2
with probability (p1-1)p2 i . Finally, the checkpoint period evolves with the number of processors, just as for Moldable applications. We derive the following formula:

W G (p 1 , p 2 ) = (p1-1)p2 1+ C (p 1 -1)p 2 √ 2C (p 1 -1)p 2 µ (p 1 -1)p 2 × µ p1p2-1 -R (p1-1)p2 - √ 2C (p 1 -1)p 2 µ (p 1 -1)p 2 2
• (p1-1)p2

p1p2-1

+ (p1-1)p2 i=p1p2-2 µ i -R (p1-1)p2 • (p1-1)p2 i+1 - √ 2C (p 1 -1)p 2 µ (p 1 -1)p 2 2
• (p1-1)p2 i Going from p 2 processors down to (p -f ) 2 processors thus corresponds to a total work

W G = p 2 1 + C p 2 √ 2C p 2 µ p 2 • µ p 2 -R p 2 - 2C p 2 µ p 2 2 + f -1 g=0 (W G (p -g, p -g) + W G (p -g, p -g -1))
We use the previously computed function just as we did with the time and we add the work done during the first sub-period on the initial grid of size p 2 (this is the special case for the beginning of an allocation that was mentioned above). Its computation is similar to that of other subperiods.

The yield of the GridShaped application is then:

Y G = W G N • T G
where N = p 2 .

ABFT for GridShaped

Finally, in this section, we investigate the impact of using Algorithm-Based Fault Tolerant techniques, or ABFT, instead of Checkpoint:Restart (C/R). Just as before, we build a performance model that uses first-order approximations. In particular, we do not consider overlapping failures, thereby allowing for a failurefree reconstruction of lost data after a failure. This first-order approximation is accurate up to a few percent, whenever the failure rate is not too high, or more precisely, when the MTBF remains an order of magnitude higher than resilience parameters [START_REF]Fault-Tolerance Techniques for High-Performance Computing[END_REF]. Note that this is the case for state-of-the-art platforms, but may prove otherwise whenever millions of nodes are assembled in the forthcoming years.

Consider a matrix factorization on a p × p grid. The matrix is of size n × n and is partitioned into tiles of size b × b. These tiles are distributed in a 2D block-cyclic fashion across processors. Letting n = pbr, each processor initially holds r 2 tiles. Every set of p consecutive tiles in the matrix is checksummed into a new tile, which is duplicated for resilience. These two new tiles are added to the right border of the matrix and will be distributed in a 2D block-cyclic fashion across processors, just as the original matrix tiles. In other words, we add 2pr 2 new tiles, extending each tile row of the matrix (there are pr such tile rows) with 2r new tiles. Fig. 2 illustrates this scheme: the white area represents the original user matrix of size n × n, split in tiles of size b × b, and distributed over a p × p process grid. The number in each tile represents the rank that hosts a given tile of the matrix. There are two groups of tile-columns of checksums: the light grey ones checksum the right end of the matrix, and the dark grey ones checksum the left part of the matrix. For a bigger matrix, more groups would be added, each group accumulate the sum of p consecutive tile-columns of the matrix. In each group, there are two tile-columns: the checksum and its replica. These new tiles will be treated as regular matrix tiles by the ABFT algorithm, which corresponds to a ratio Now, if a processor crashes, we finish the current step of the factorization on all surviving processors, and then reconstruct the tiles of the crashed processor as follows:

• For each tile lost, there are p -1 other tiles (the ones involved in the same checksum as the lost tile) and at least one checksum tile (maybe two if the crashed processor did not hold any of the two checksum tiles for that lost tile). This is what is needed to enable the reconstruction. We solve a linear system of size b and reconstruct the missing tile for a time proportional to b 3 + pb 2 .

• We do this for the r 2 tiles of the crashed processor, for a total time of O(r 2 (b 3 + pb 2 )τ a ), where τ a is the time to perform a floating-point operation.

Doing so, we reconstruct the same tile as if we had completed the factorization step without failure. Then, there are two cases: the ABFT algorithm relies on a process grid, so the application behaves similarly to a GridShaped application. If spare nodes are available, one of them is selected and inserted within the process grid at the place of the crashed processor, at a cost of communicating O(r 2 b 2 ) matrix coefficients (the amount of data held by the faulty processor). If, on the other hand, there are no spare nodes, we have to start the redistribution of the matrix onto a p × (p -1) grid. The distribution is operated in parallel across the p grid rows. Within a processor row, most of the tiles will have to change owner to keep enforcing a 2D block-cyclic distribution, which implies O( n 2 p ) = O(r 2 pb 2 ) communications as we redistribute everything on every row. Since all rows operate in parallel, the time for the redistribution is O(r 2 pb 2 τ c ), where τ c is the time to communicate a floating point number. Altogether, the total cost to recover from a failure is O(r 2 b 2 (bτ a + p(τ a + τ c ))).

In the following, we compute the expected yield of a linear algebra kernel protected by ABFT. Again, we consider numbers of failures of the form F = 2pf -f 2 so that p 2 = F + (p -f ) 2 . Again, we could stop after any number of faults F , and the publicly available software [START_REF]Simulation Software[END_REF] shows how to do so.

We first compute the expected time between two full restarts:

T ABF T = (p-f ) 2 i=p 2 µ i + D.
As previously, we tolerate failures up to reaching a processor grid size of (pf ) × (p -f ), each inter-arrival time being the MTBF of the platform with the corresponding number of alive processors. Now, we define the auxiliary variable W ABF T (p 1 , p 2 ) as the parallel work when moving from a (p 1 -1) × p 2 grid with p 2 -1 spare nodes to a (p 1 -1) × p 2 grid with no spare node. There are (p 1 -1)p 2 processors working during all sub-periods, just as it was the case for GridShaped applications. A failurefree execution would imply a parallel work of 1 1+ 2 p (p1-1)p2 i=p1p2-1 µ i which is the total time of computation divided by overhead added with the checksum tiles. However, for each failure we need to reconstruct the lost tiles and either pay a redistribution cost (during the first sub-period where we just reduced the size of the grid because we had no spare) or a communication cost to send data to one of the p 2 -1 spare nodes (all other sub-periods where we select a spare). This happens if and only if the failure stroke a working processor just as in the GridShaped case, i.e. with probability (p1-1)p2 i+1 . In the end, since there are (p 1 -1)p 2 processors at work, we get the following formula:

W ABF T (p 1 , p 2 ) = (p 1 -1)p 2 1 + 2 p   µ p1p2-1 -RD p1 + (p1-1)p2 i=p1p2-2 (µ i -RP • (p 1 -1)p 2 i + 1 )   ,
where RP is the cost to replace a faulty processor by a spare, namely

RP = r 2 (b 3 + pb 2 )τ a + r 2 b 2 τ c ,
and RD i is the cost to reistribute data, namely

RD i = r 2 (b 3 + pb 2 )τ a + n 2 i τ c .
To compute these values, we proceed as follows:

• The reconstruction of the lost tiles always takes r 2 (b 3 + pb 2 ) floating-point operations, and the enrollment of the spare requires that it receives r 2 b 2 floating-point values, which directly leads to the value of RP , which is independent of the number of processors;

• However, when we redistribute the tiles to shrink the grid, the time needed increases as the number of processors decreases because each of them has to gather more data: it requires O( n 2 i ) communications when redistributing from a i × j grid of processors to a (i -1) × j grid, or similarly from a j × i grid to a j × (i -1) grid, where j = i or j = i -1. Overall, going from a p × p grid to a (p -f ) × (p -f ) grid corresponds to a total work of W ABF T . At the beginning of the allocation, we need to read the input data, then we wait for the first failure to happen (giving a work of µ p 2 -R p 2 during the first sub-period that we divide by the overhead added by the checksum tiles) and then we use our auxiliary variables to decrease the size of the grid step by step. This leads to the following:

W ABF T = p 2 (µ p 2 -R p 2 ) 1 + 2 p + f -1 i=0 (W ABF T (p -i, p -i)+W ABF T (p -i, p -1 -i)) .
The yield of the application protected with ABFT is then:

Y ABF T = W ABF T N • T ABF T
where N = p 2 .

Applicative scenarios

We consider several applicative scenarios in this section. We start with a platform inspired from existing ones in Section 5.1, then we study the impact of several key parameters in Section 5.2. Finally, we compare ABFT and C/R for a GridShaped application in Section 5.3.

Main scenario

As a main applicative scenario using C/R, we consider a platform with 22,250 nodes (150 2 ), with a node MTBF of 20 years, and an application that would take 2 minutes to checkpoint (at 22,250 nodes). In other words, we let N = 22, 500, µ ind = 20y and C i = C = 120s. These values are inspired from existing platforms: the Titan supercomputer at OLCF [START_REF] Gupta | Failures in large scale systems: Long-term measurement, analysis, and implications[END_REF], for example, holds 18,688 nodes, and experiences a few node failures per day, implying a node MTBF between 18 and 25 years. The filesystem has a bandwidth of 1.4TB/s, and nodes altogether aggregate 100TB of memory, thus a checkpoint that would save 30% of that system should take in the order of 2 minutes to complete. In other words, C i = C = 120 seconds for all i ≤ 18, 688.

Figure 3 shows the yield that can be expected if doing a full restart after an optimal number of failures, as a function of the wait time, for the three kind of applications considered (Rigid, Moldable and GridShaped). We also plot the expected yield when the application experiences a full restart after each failure (NoSpare). First, one sees that the three approaches that avoid paying the cost of a wait time after every failure experience a comparable yield, while the performance of the NoSpare approach quickly degrades to a small efficiency (30% when the wait time is around 14h).

The zoom box to differentiate the Rigid, Moldable and GridShaped yield shows that the Moldable approach has a slightly higher yield than the other ones, but only for a minimal fraction of the yield. This is expected, as the Moldable approach takes advantage of all living processors, while the GridShaped and Rigid approaches sacrifice the computing power of the spare nodes waiting for the next failure. However, the size of the gain is small to the point of being negligible. The GridShaped approach experiences a yield whose behavior changes in steps: it starts with a constant slope, under the Rigid yield, until the wait time reaches 8h at which point both Rigid and GridShaped yields are the same. The slope of GridShaped then becomes smaller, exhibiting a better yield than Rigid and slowly reaching the yield of Moldable. If we extend the wait time, or change the configuration to experience more phase changes (as is done in Section 5.2 below), the yield of GridShaped would reach the same value as the yield of Moldable, at which point the slope of GridShaped would change again and become higher. This phenomenon is explained by the next figures.

Figure 4 shows the number of failures after which the application should do a full restart, to obtain an optimal yield, as a function of the wait time, for the three kind of applications considered. We observe that this optimal is quickly reached: even with long wait times (e.g. 10h), 170 to 250 failures (depending on the method) should be tolerated within the allocation before relinquishing it. This is small compared to the number of nodes: less than 1% of the resource should be dedicated as spares for the Rigid approach, and after losing 1% of the resource, the Moldable approach should request a new allocation. This is remarkable, taking into account the poor yield obtained by the approach that does not tolerate failures within the allocation. Even with a small wait time (assuming the platform would be capable of re-scheduling applications that experience failures in less than 2h), Figure 3 shows that the yield of the NoSpare approach would decrease to 70%. This represents a waste of 30%, which is much higher than the recommended waste of 10% for resilience in the current HPC platforms recommendations [START_REF]Draft CORAL-2 build statement of work[END_REF][START_REF] Cappello | Toward exascale resilience: 2014 update[END_REF]. Comparatively, keeping only 1% of additional resources (within the allocation) would allow to maintain a yield at 90%, for every approach considered.

The GridShaped approach experiences steps that correspond to using all the spares created when redeploying the application over a smaller grid before relinquishing the allocation. As illustrated in Figure 3, the yield evolves in steps, changing the slope of a linear approximation radically when redeploying over a smaller grid. This has for consequence that the maximal yield is always at a slope change point, thus at the frontier of a new grid size. It is still remarkable that even with very small wait times, it is more beneficial to use spares (and thus to lose a full row of processors) than to redeploy immediately. Figure 5 shows the maximal length of an allocation: after such duration, the job will have to fully restart in order to maintain the optimal yield. This figure illustrates the real difference between the Rigid and Moldable approaches: although both approaches are capable of extracting the same yield, the Moldable approach can do so with significantly longer periods between full restarts. This is important when considering real life applications, because this means that the applications using a Moldable approach have a higher chance to complete before the first full restart, and overall will always complete in a lower number of allocations than the Rigid approach.

Finally, Figure 6 shows an upper limit of the duration of the wait time in order to guarantee a given yield for the three applications. In particular, we see that to reach a yield of 90%, an application which would restart its job at each fault would need that restart to be done in less than 6 minutes whereas the Rigid and GridShaped approaches need a full restart in less than 3 hours approximately. This bound goes up to 7 hours for the Moldable approach. In comparison, with a wait time of 1 hour, the yield obtained using NoSpare is only 80%. This shows that, using these parameters, it seems impossible to guarantee the recommended waste of 10% without tolerating (a small) number of failures before rescheduling the job.

Varying key parameters

We performed a full-factorial 4 level design simulation to assess the impact of key parameters. We tried all combinations of MTBF ( 5 Figure 7 shows the yield and the corresponding allocation length for different values of the MTBF, when using the largest application size N = 350×350. The top subfigure is for µ ind = 5 years while the bottom subfigure is for µ ind = 50 years. The checkpoint cost is C i = C = 10 minutes. As expected, the yield increases when the MTBF increases. However, the variation of the allocation length is a bit different. At first, it decreases with the MTBF (for example, with a wait time of 10 hours, it decreases from around 150 days to around 100 days when µ ind decreases from 50 years to 20 years). This is because the optimal number of faults allowed is not much higher when µ ind = 20 years, thus it decreases the overall allocation length. However, when we reach limit behaviours with short node MTBF, the number of failures to tolerate explodes and increases the allocation length. We can also see that the allocation length for GridShaped applications tends to follow that of a Moldable application when µ ind decreases.

Figure 8 shows the optimal number of faults to tolerate for the four different application sizes (with µ ind = 20 years and C i = C = 10 minutes). We can see from this experiment that the number of tolerated failures stays within a small percentage of the total number of processors. In particular, the optimal number of failures allowed for every type of application stays below or equals 2% of the total application size in all the four cases.

Figure 9 aims at showing the impact of the checkpointing cost on the allocation length. The trend is that it does not depend on the checkpointing cost. This can be explained by the fact that the allocation length does not take into account the checkpoint/restart strategy into its computation, only the MTBF and the number of failures allowed. Overall, the impact of the checkpointing cost stays minimal compared to the impact of the wait time or the MTBF.

Finally, Figure 10 describes the yield obtained when using different models for the checkpointing cost: either the checkpoint is constant (independent of the number of processors: left figure) or it is inversely proportional to the number of processors (right figure). As these plots show, the difference between the two models not have a noticeable impact on the yield of the applications. This can be explained as follows: as Figure 8 showed, only a small number of faults is allowed before resubmission, in comparison to the application size.

Changing the number of active processors by a few percentage does not really make a difference for the checkpoint cost, which remains almost the same in both models.

Comparison between C/R and ABFT

In this subsection, we present the results of ABFT and C/R strategies, for a GridShaped application. In order to compare both strategies, we introduce ABFT parameters, and use data from the Titan platform [START_REF] Apex | [END_REF]:

• We use tiles of size 180 × 180, i.e. we let b = 180. We set r = 325; so that a node holds 325 2 = 105625 tiles.

• These values give a total of almost 25.5 GB used by each node, which corresponds to 80% of the memory of a node in Titan.

• Overall, the total memory of the application is 8p 2 r 2 b 2 bytes, so we set the checkpointing cost to be 8p 2 r 2 b 2 1.4×1024 Figure 11 presents the yield obtained by both strategies with either no spare processors (NoSpare and NoSpare-ABFT) or with the optimal number of spare processors (GridShaped for the C/R strategy and ABFT for the ABFT strategy). In Figure 11 , we use N = 150 × 150 and µ ind = 20 years. Unsurprisingly, the ABFT strategy grants a better yield than the C/R strategy with a yield very close to 1, compared to ≈ 0.8 for C/R. This is largely due to the fact that the overhead added by the ABFT is 2 p and so is negligible compared to the checkpoint overhead. Moreover, the reconstruction of the tiles is done in parallel so it does not induce any significant overhead. This can also be seen when we do not use any spare: C/R and ABFT follow the same trend but ABFT is always more efficient than C/R, which exactly shows that the checkpoint overhead is larger than the ABFT overhead, since it is the only source (along with the wait time) of wasted time if F = 0. For a wait time of 10 hours the C/R strategy gives a yield of 0.820 while ABFT grants a better yield of 0.973 (0.364 and 0.426 respectively with no spare processors). We can see on the right figure that the allocation lengths are similar for both strategies. However, for some values, ABFT will have a shorter allocation length, mostly due to the fact that its overhead is small and does not depend on the number of alive processors; hence loosing a few nodes implies a greater slowdown than for the C/R strategy where the checkpointing period is adapted regularly.

The conclusion of this comparative study is that, for a GridShaped application, ABFT uses a very small percentage of spare resources and grants a better yield than classical C/R.

Conclusion

In this paper, we have compared the performance of Rigid, Moldable and GridShaped applications when executed on large-scale failure-prone platforms. We have mainly focused on the C/R approach, because it is the most widely used approach for resilience. For each application type, we have computed the optimal number of faults that should be tolerated before requesting a new allocation, as a function of the wait time. Through realistic applicative scenarios inspired by state-of-the-art platforms, we have shown that the three application types experience an optimal yield when requesting a new allocation after experiencing a number of failures that represents a small percentage of the initial number of resources (hence a small percentage of spares for Rigid applications), and this even for large values of the wait time. On the contrary, the NoSpare strategy, where a new allocation is requested after each failure, sees its yield dramatically decrease when the wait time increases. We also observed that Moldable applications enjoy much longer execution periods in between two re-allocations, thereby decreasing the total execution time as compared to Rigid applications (and GridShaped applications lying in between).

GridShaped applications may also be protected using ABFT, and we have compared the efficiency of C/R and ABFT for a typical dense matrix factorization problem. As expected, using ABFT leads to even better yields than C/R for a wide variety of scenarios, in particular for larger problem sizes for which ABFT scales remarkably well.

Future work will be devoted to exploring more applicative scenarios, and running actual experiments using ULFM [START_REF] Bland | Postfailure recovery of MPI communication capability: Design and rationale[END_REF]. We also intend to extend the model in several directions. On the application side, we aim at dealing with non-perfectly parallel applications but instead with applications whose speedup profile obeys Amdahl's law [START_REF] Amdahl | The validity of the single processor approach to achieving large scale computing capabilities[END_REF]. On the platform side, we aim at adapting the model to heterogeneous platforms and at doing more experiments with different values for the recovery and checkpoint costs as bandwidths are different when reading or writing data. We will also introduce a more refined speedup profile for GridShaped applications, with an execution speed that depends on the grid shape (a square being usually faster than an elongated rectangle). On the resilience side, we will explore the case with different costs for checkpoint and recovery. More importantly, we will address the combination of ABFT and C/R (instead of dealing with either method individually). Such a combination would allow to tolerate for several failures striking within the same computational step: the idea would be to use ABFT to recover from a single failure and to rollback to the last checkpoint only in the case of multiple failures. Such a combination would enable us to go beyond first-order approximations and singlefailure scenarios. Finally, we would like to investigate the case for correlated failures. Even if a theoretical analysis seems out of reach, we could generate failures with models accounting for correlation but optimize for the current model, and check how the correlations affect the results.

Figure 1 :

 1 Figure 1: Example of node failures substituted by spare nodes in a 2-D GridShaped application.

2pr 2 p 2 r 2 = 2 pFigure 2 :

 22 Figure 2: Example of data redundancy and checksuming in an ABFT factorization. Each white square represents a matrix tile; numbers in the square represent the rank on which this tile is hosted; grey tiles represent the checksums and their replica (symbolized by the = arrow). In this case, p = 3, n = 6b.

Figure 3 :

 3 Figure 3: Optimal yield as function of the wait time, for the different types of applications.

Figure 4 :

 4 Figure 4: Optimal number of failures tolerated between two full restarts, as function of the wait time, for the different types of applications.

  years, 10 years, 20 years, 50 years), checkpointing cost (2 minutes, 10 minutes, 30 minutes, 60 minutes)

Figure 5 :

 5 Figure 5: Optimal length of allocations, for the different types of applications.

Figure 6 :

 6 Figure 6: Maximum wait time allowed to reach a target yield.

Figure 8 :Figure 9 :

 89 Figure 8: Optimal number of faults before rescheduling the application for different application sizes.

Figure 10 :Figure 11 :

 1011 Figure 10: Constant checkpoint cost (C i = 60 min) on the left, and increasing checkpoint cost (C i = N i × 60 min) on the right, with µ ind = 5 years and N = 350 × 350.

  4 , using 1.4 TB/s for the I/O bandwidth of the Titan platform. With r and b set as mentioned, we get C i = C ≈

	Yield Number of Failures before Resubmission	0 0.02 0.04 0.06 0.08 0.1 0.12 0.14 0.16 0 10 20 30 40 50 0	0	2 Moldable Rigid GridShaped NoSpare 2 4 4	6 6	8 8 Wait Time (h) 10 0.13 0.135 0.14 0.145 0.15 0.155 0.16 0 2 4 6 8 10 12 14 16 18 20 12 14 16 18 Wait Time (h) 10 12 14 16 18 Rigid Moldable GridShaped NoSpare (a) 50 × 50 Yield	20 20	Yield-Optimal Length of Allocation (days) Number of Failures before Resubmission	0 500 1000 1500 2000 2500 0 50 100 150 200 250 300 350 400	0 0	2 2	4 4	6 6 (b) 150 × 150 8 10 12 8 10 12 14 16 18 20 14 16 18 20 Rigid Moldable Rigid Moldable GridShaped NoSpare Wait Time (h) GridShaped NoSpare
										Wait Time (h)											Wait Time (h)
	Yield Number of Failures before Resubmission	1200 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0 200 400 600 800 1000	0 0	2 Moldable Rigid GridShaped NoSpare 2	4 4	2500 (a) µ ind = 5 years 18 20 0 2 4 6 8 10 12 14 16 18 20 10 12 14 16 0.3168 0.317 0.3172 0.3174 0.3176 0.3178 0.318 0.3182 Wait Time (h) 0 50 100 150 200 250 300 350 400 450 0 Yield-Optimal Length of Allocation (days) 8 8 10 12 14 16 18 20 Rigid Moldable GridShaped NoSpare 500 1000 1500 2000 Number of Failures before Resubmission 0 0 Wait Time (h) (c) 250 × 250 6 Yield 6	2 2	4 4	6 6 (d) 350 × 350 8 10 12 8 10 12 Wait Time (h)	14 GridShaped 16 Rigid Rigid Moldable NoSpare 14 16 Moldable GridShaped NoSpare	18 18	20 20
										Wait Time (h)										Wait Time (h)
												(b) µ ind = 10 years
		0.55												160
	Yield	0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5	0	2 Moldable Rigid GridShaped NoSpare	4	6	Yield	8	10 0.509 0.51 0.511 0.512 0.513 0.514 0.515 0.516 0.517 0.518 0 2 4 6 8 10 12 14 16 18 20 12 14 16 18 Wait Time (h)	20	Yield-Optimal Length of Allocation (days)	0 20 40 60 80 100 120 140	0		2	4	6	8	10	12	14 GridShaped 16 Rigid Moldable NoSpare	18	20
										Wait Time (h)										Wait Time (h)
												(c) µ ind = 20 years
		0.7													250
	Yield	0.1 0.2 0.3 0.4 0.5 0.6	0	2 Moldable Rigid GridShaped NoSpare	4	6	Yield	8	10 0.686 0.687 0.688 0.689 0.69 0.691 0.692 0.693 0.694 0.695 0 2 4 6 8 10 12 14 16 18 20 12 14 16 18 Wait Time (h)	20	Yield-Optimal Length of Allocation (days)	0 50 100 150 200	0		2	4	6	8	10	12	14 GridShaped 16 Rigid Moldable NoSpare	18	20
										Wait Time (h)										Wait Time (h)
				25.5N 1.4×1024 ≈ N 56.3 .	(d) µ ind = 50 years
	• Titan has 18,688 cores for a peak performance of 17.59 PFlop/s. We derive Figure 7: Yield and optimal allocation length of as a function of the wait time with N =
	a performance per core of 987 GFlop/s, i.e. τ a = 350 × 350, and C = 10 minutes.	1 987×1024 3 .
		• Using the same reasoning, we derive that τ c =	1 87.2×1024 3 .

Another limit is induced by the total application memory Memtot . There must remain at least live processors such that Memtot ≤ × Mem ind , where Mem ind is the memory of each processor. We ignore this contraint in the paper but it would be straightforward to take it into account.

In datacenters, failures can actually be correlated in space or in time. But to the best of our knowledge, there is no currently available method to analyze their impact without the IID assumption.

Acknowledgement

This research is partially supported by the NSF (award #1564133). We would like to thank the reviewers for their comments and suggestions.