Amdahl Meets

Young / Daly

Aurélien Cavelan

Jiafan Li

Yves Robert

Hongyang Sun

When

Keywords: resilience, fail-stop errors, silent errors, optimal checkpointing period, optimal processor allocation, Amdahl's law

This paper investigates the optimal number of processors to execute a parallel job, whose speedup profile obeys Amdahl's law, on a large-scale platform subject to fail-stop and silent errors. We combine the traditional checkpointing and rollback recovery strategies with verification mechanisms to cope with both error sources. We provide an exact formula to express the execution overhead incurred by a periodic checkpointing pattern of length T and with P processors, and we give first-order approximations for the optimal values T * and P * as a function of the individual processor failure rate λind. A striking result is that P * is of the order λ -1/4 ind if the checkpointing cost grows linearly with the number of processors, and of the order λ -1/3 ind if the checkpointing cost stays bounded for any P . We conduct an extensive set of simulations to support the theoretical study. The results confirm the accuracy of first-order approximation under a wide range of parameter settings.

I. INTRODUCTION

Consider a typical HPC (High Performance Computing) application that will run for days or even weeks on a parallel platform, and whose sequential time is non-negligible. What is the optimal number of processors to execute this application so as to minimize its total execution time? Assume that the application speedup profile obeys Amdahl's law [START_REF] Amdahl | The validity of the single processor approach to achieving large scale computing capabilities[END_REF]: a fraction α of the work is sequential, while the remaining 1-α fraction is perfectly parallel. The speedup with P processors is then

S(P ) = 1 α + 1-α P . (1)
While S(P ) is bounded above by 1/α, it is a strictly increasing function of P , which means that one should enroll as many processors as possible to minimize execution time. However, this reasoning only holds for error-free execution. With 100,000+ nodes in current petascale platforms, and even more computing resources when entering the exascale era, resilience becomes a challenge [START_REF] Cappello | Toward exascale resilience: 2014 update[END_REF]. Even if each node provides an individual MTBF (Mean Time Between Failures) of, say, one century, a machine with 100,000 such nodes will encounter a failure every 9 hours on average, which is smaller than the execution time of many HPC applications. Furthermore, a one-century MTBF per node is an optimistic figure, given that each node may be composed of tens or even hundreds of cores. Moreover, several types of errors need to be considered when computing at scale. In addition to the classical fail-stop errors (such as hardware failures), silent errors (or SDC, for Silent Data Corruptions) constitute another threat [START_REF] O'gorman | The effect of cosmic rays on the soft error rate of a DRAM at ground level[END_REF], [START_REF] Ziegler | Cosmic ray soft error rates of 16-Mb DRAM memory chips[END_REF], [START_REF] Moody | Design, modeling, and evaluation of a scalable multi-level checkpointing system[END_REF]. This phenomenon is not so well understood, but has been recently identified as one of the major challenges towards exascale [START_REF] Cappello | Toward exascale resilience: 2014 update[END_REF].

While checkpoint/restart [START_REF] Chandy | Distributed snapshots: Determining global states of distributed systems[END_REF], [START_REF] Elnozahy | A survey of rollback-recovery protocols in message-passing systems[END_REF], [START_REF] Hérault | Fault-Tolerance Techniques for High-Performance Computing, Computer Communications and Networks[END_REF] is the de-facto recovery technique for dealing with fail-stop errors, there is no widely adopted general-purpose technique to cope with silent errors. In contrast to a fail-stop error whose detection is immediate, a silent error is identified only when the corrupted data leads to an unusual application behavior. Such a detection latency raises a new challenge: if the error struck before the last checkpoint, and is detected after that checkpoint, then the checkpoint is corrupted and cannot be used for rollback. In order to avoid corrupted checkpoints, an effective approach consists in employing some verification mechanism and combining it with checkpointing. Such a verification mechanism can be general-purpose (e.g., based on replication [START_REF] Fiala | Detection and correction of silent data corruption for large-scale high-performance computing[END_REF] or even triplication [START_REF] Lyons | The use of triple-modular redundancy to improve computer reliability[END_REF]) or application-specific [START_REF] Bosilca | Algorithm-based fault tolerance applied to high performance computing[END_REF], [START_REF] Benson | Silent error detection in numerical time-stepping schemes[END_REF], [START_REF] Chen | Online-ABFT: An online algorithm based fault tolerance scheme for soft error detection in iterative methods[END_REF], [START_REF] Sao | Self-stabilizing iterative solvers[END_REF].

We address both fail-stop and silent errors by using verified checkpoints, which corresponds to performing a verification just before taking each checkpoint. Note that this approach is agnostic of the nature of the verification mechanism. If the verification succeeds, then one can safely store the checkpoint. Otherwise, it means that a silent error has struck since the last checkpoint, which was duly verified, and one can safely recover from that checkpoint to resume the execution of the application. Of course, if a fail-stop error strikes, we can also safely recover from the last checkpoint, just as in the classical checkpoint and rollback recovery method. We refer to this protocol as the VC protocol, and it basically amounts to replacing the cost C of a checkpoint by the cost V + C of a verification followed by a checkpoint. However, because we deal with two sources of errors, one detected immediately and the other only when we reach the verification, the analysis of the optimal checkpointing strategy is more involved.

This paper shows that on failure-prone platforms, it is no longer true that enrolling more processors will always decrease the (expected) execution time of a parallel application. First, more processors means more failures: if the failure rate of an individual processor is λ ind (and its MTBF is µ ind = 1/λ ind ), then the failure rate for a platform with P processors is P λ ind (and its MTBF is µ ind /P ) [START_REF] Hérault | Fault-Tolerance Techniques for High-Performance Computing, Computer Communications and Networks[END_REF]Proposition 1.2]. Second, the cost of checkpointing may well increase linearly with P [START_REF] Elnozahy | Checkpointing for peta-scale systems: a look into the future of practical rollback-recovery[END_REF], [START_REF] Zheng | Reliability-aware speedup models for parallel applications with coordinated checkpointing/restart[END_REF], because of the synchronization needed among the processors in order to take a coherent snapshot of the global application state. The intuition is that at some point adding more resources will be an overkill, for failures and resilience operations to handle them will become too frequent for the application to make any progress. These considerations raise the following fundamental question: What is the optimal number of processors to execute a parallel application on a failure-prone platform? Surprisingly, this question has never received a quantitative answer, although some experimental study has been reported [START_REF] Jin | Optimizing HPC fault-tolerant environment: An analytical approach[END_REF], [START_REF] Zheng | Reliability-aware speedup models for parallel applications with coordinated checkpointing/restart[END_REF]. The major contribution of this paper is to answer this question by providing a detailed analysis on the performance of the VC protocol in the presence of both fail-stop and silent errors. In particular, we consider a periodic checkpointing pattern PATTERN(T, P ), which consists of a work chunk of duration T and executed with P processors, followed by a verification and then by a checkpoint (see Figure 1). We give first-order approximations for the optimal values T * and P * as a function of the individual processor failure rate λ ind . A striking result is that, as long as the sequential fraction α of the application is a non-negligible constant, P * is of the order λ -1/4 ind if the checkpointing cost grows linearly with the number of processors, and of the order λ -1/3 ind if the checkpointing cost stays bounded for any P . The corresponding values of T * in these two cases are of the orders λ -1/2 ind and λ -1/3 ind , respectively. The results nicely extend 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] by characterizing the optimal number of resources to enroll. These first-order bounds are well corroborated and validated by our simulation study conducted using real platform parameters.

The main contributions of this paper are the following:

• The derivation of an exact analytical formula for the expected execution time of a pattern in the presence of both fail-stop and silent errors, where fail-stop errors can strike at any time (while silent errors only strike during computations); • The determination of the optimal pattern length and processor count, up to the first-order term. Given error rates and checkpoint/verification costs, we compute both the optimal pattern length and optimal number of processors to enroll. To the best of our knowledge, this is the first analytical characterization of the optimal degree of parallelism for executing a parallel application whose speedup obeys Amdahl's law; • An extensive set of simulations with data collected from real platforms. The results confirm the accuracy of the performance model and validity of first-order approximation under a wide range of parameter settings and resilience scenarios.

Due to lack of space, we refer to the companion research report [START_REF] Cavelan | When Amdahl meets Young/Daly[END_REF] for a discussion of related work on checkpointing protocols and silent error detection. Several authors have investigated the optimal number of processors to enroll when running a parallel application on a failure-prone platform. Zheng et al. [START_REF] Zheng | Reliability-aware speedup models for parallel applications with coordinated checkpointing/restart[END_REF] address this problem for fail-stop errors and provide a formula to compute the speedup of an application obeying Amdhal's law and running with P processors. Also for fail-stop errors, Jin et al. [START_REF] Jin | Optimizing HPC fault-tolerant environment: An analytical approach[END_REF] use an iterative relaxation procedure to compute the optimal number of resources for a perfectly parallel job. These two important works are the most closely related to ours. In comparison, the main differences with our work are: (i) we account for both fail-stop and silent errors (instead of only fail-stop errors); (ii) we consider several relevant scenarios for checkpointing costs (instead of only linearly growing costs); (iii) we analytically characterize both the optimal number of processors and optimal checkpointing period as a function of the individual processor failure rate, the speedup profile and the checkpoint/verification cost (instead of using numerical procedures); and (iv) our formulas are exact up to first-order term and account for errors in checkpointing.

The rest of the paper is organized as follows. Section II introduces the models and notations. Section III presents all our analytical results, followed by the presentation of the simulation results in Section IV. Finally, Section V provides concluding remarks and hints for future directions.

II. MODELS AND NOTATIONS

This section presents the analytical models for evaluating the performance of resilience algorithms. Table I summarizes the list of main notations used in the paper. Failure model. We incorporate both hardware faults and silent data corruptions, which are also known as fail-stop errors and silent errors in the literature. Since the two types of errors are caused by different sources on realistic systems, we assume that they are independent and that both arrivals follow exponential distributions. Let λ ind = 1/µ ind denote the reciprocal of the MTBF µ ind of each individual processor by accounting for both types of errors, and suppose f fraction of the total number of errors are fail-stop and the remaining s = 1 -f fraction are silent. Then, the arrival rates of failstop and silent errors when using P processors are given by λ f P = f λ ind P and λ s P = sλ ind P , respectively [START_REF] Hérault | Fault-Tolerance Techniques for High-Performance Computing, Computer Communications and Networks[END_REF]. Thus, the probability of encountering at least one fail-stop error during a computation of time T is q f P (T ) = 1 -e -λ f P T and that of encountering at least one silent error during the same computation is q s P (T ) = 1 -e -λ s P T . Application model. We consider HPC applications that are long-lasting even when executed on a large number of processors. Suppose an application has a total amount of computation (or work) W total and a speedup function S(P ) when executed on P processors without considering failures. In this paper, we consider the speedup function obeying Amdahl's law as given in Equation [START_REF] Amdahl | The validity of the single processor approach to achieving large scale computing capabilities[END_REF]. For convenience, we define H(P ) = 1 S(P ) = α+ 1-α P to be the execution overhead of the application, where α denotes the fraction of the application that is inherently sequential and cannot be parallelized. The makespan (total execution time) W final of the application in an error-free execution is therefore given by W final = Wtotal S(P ) = H(P )W total . Resilience model. To enforce resilience, a standard protocol is by checkpointing the status of the application periodically, thus creating periodic checkpointing patterns as illustrated in Figure 1. To cope with silent errors, an additional error detection (or verification) mechanism is performed just before taking each checkpoint [START_REF] Widener | Canaries in a coal mine: Using application-level checkpoints to detect memory failures[END_REF], [START_REF] Benoit | Optimal resilience patterns to cope with fail-stop and silent errors[END_REF]. If a fail-stop error strikes inside a pattern, the computation is interrupted immediately, while a silent error, if strikes, is only detected at the end of the pattern by the verification. In both cases, we roll back to the beginning of the pattern and recover from the last checkpoint, thus avoiding restarting the application from scratch. Note that a fail-stop error could strike after a silent error within the same pattern but before the verification is reached. In this case, the silent error is masked by the fail-stop error and need not be detected, since a recovery is nevertheless required. Formally, we characterize a periodic checkpointing pattern, denoted as PATTERN(T, P ), by the following two parameters.

• T : length (or period) of the pattern, i.e., amount of time to do useful computation before taking each checkpoint; • P : number of processors allocated to the application. The cost of checkpointing clearly depends upon the protocol and storage type, hence we adopt a quite general formula to account for the checkpointing time in this paper. Specifically, we use C P = a + b/P + cP to model the time to save a checkpoint on P processors. Here, a + b/P represents the I/O overhead to write the application's memory footprint M to the storage system. For in-memory checkpointing [START_REF] Zheng | FTC-Charm++: an in-memory checkpoint-based fault tolerant runtime for Charm++ and MPI[END_REF], a + b/P is a communication time with latency a and b/P = M/(τ net P ), where τ net is the network bandwidth (each processor stores M/P data items). For coordinated checkpointing to stable storage, there are two cases: if the storage system's bandwidth is the I/O bottleneck, a = β + M/τ io and b = 0, where β is a start-up time and τ io is the I/O bandwidth; otherwise, if the network is the I/O bottleneck, we retrieve the same formula as for in-memory checkpointing. Finally, cP represents the message passing overhead that grows linearly with the number of processors, in order for all processors to reach a global consistent state [START_REF] Elnozahy | Checkpointing for peta-scale systems: a look into the future of practical rollback-recovery[END_REF], [START_REF] Zheng | Reliability-aware speedup models for parallel applications with coordinated checkpointing/restart[END_REF].

The recovery cost is assumed to be the same as the checkpointing cost, i.e., R P = C P , because it involves the same I/O operations. To perform a verification, we assume the use of error detectors. Since a verification is only done in memory, its cost can be modeled as V P = v + u/P . Here, v is a start-up latency, and u/P is the time needed to verify the application data distributed across P processors. Finally, a constant downtime D is required after each fail-stop error in order to replace or repair a failed processor.

In our analysis, fail-stop errors can strike at any time during the execution of an application, including verifications, checkpointing and recoveries. However, silent errors can only strike the computations, since otherwise they cannot be detected. Hence, we assume that I/O operations and verifications are protected from silent errors (e.g., by using expensive redundancy or replication techniques). Finally, no error of any kind can strike during downtime.

Optimization objective. The objective is to minimize the expected total execution time (or makespan) of an application. Since the application is divided into periodic checkpointing patterns defined by PATTERN(T, P ), the amount of work done in a pattern is W pattern = T • S(P ). For long-lasting applications, the total number of patterns in the application can be approximated as Wtotal Wpattern = Wtotal T •S(P ) . Let E(PATTERN) denote the expected execution time of the pattern. The expected makespan E(W final ) of the application is then given by

E(W final ) ≈ E(PATTERN) Wtotal T •S(P ) . Now, define S(PATTERN) = T •S(P )
E(PATTERN) to be the expected speedup of the pattern, and define

H(PATTERN) = 1 S(PATTERN) = E(PATTERN)
T H(P ) to be the expected execution overhead of the pattern. The expected makespan of the application can therefore be written as

E(W final ) ≈ Wtotal S(PATTERN) = H(PATTERN)W total .
We observe that the optimal expected makespan is obtained by maximizing the expected speedup or minimizing the expected execution overhead of a periodic checkpointing pattern. In the next section, we will focus on such a pattern PATTERN(T, P ), and find its optimal length T and processor count P .

III. OPTIMAL PERIODIC CHECKPOINTING PATTERN

In this section, we analytically determine the optimal periodic checkpointing pattern using first-order approximation, and derive explicit formulas for the checkpointing period T and processor allocation P . We validate the first-order solution in Section IV by showing its close proximity to the optimal numerical solution.

A. Expected execution time of a pattern

We start by computing the expected execution time of a pattern when the parameters T and P are given.

Proposition 1. The expected execution time of a given pattern PATTERN(T, P ) is

E(PATTERN) = 1 λ f P + D e λ f P C P 1 -e λ s P T + e λ f P R P e λ f P (C P +T +V P )+λ s P T -1 . (2)
Proof. To successfully execute a pattern PATTERN(T, P ), we need to complete the pattern length T , the verification V P and the checkpoint C P . Hence, according to the linearity of expectation, we have

E(PATTERN) = E(T +V P +C P ) = E(T +V P )+E(C P ) . ( 3
)
We first compute E(C P ), the expected time to successfully store a checkpoint subject to fail-stop errors. During checkpointing, there is a probability q f P (C P ) that a fail-stop error strikes. If that happens, we need to perform a recovery from the last checkpoint after a downtime, and then re-execute both T and V P before re-executing C P again. If there is no error, we just need to pay the checkpointing cost C P . Therefore, we can express E(C P ) as

E(C P ) = q f P (C P ) E lost (C P ) + D + E(R P ) +E(T + V P ) + E(C P )) + 1 -q f P (C P ) C P , (4
) where E(R P ) denotes the expected time to perform a recovery, and E lost (C P ) denotes the expected time lost executing C P if a fail-stop error strikes. More generally, we can define E lost (W ) to be the expected time lost for any execution of length W , and it can be computed as follows:

E lost (W ) = ∞ 0 tP(X = t|X < W )dt = W 0 tλ f P e -λ f P t dt P(X < W )
, where P(X = t) denotes the probability that a fail-stop error strikes exactly at time t. By definition, we have P(X < W ) = q f P (W ) = 1-e -λ f P W . Integrating by parts, we get E lost (W ) =

1 λ f P -W e λ f P W -1
. Now, substituting q f P (C P ) and E lost (C P ) into Equation ( 4), we can get

E(C P ) = e λ f P C P -1 1
λ f P + D + E(R P ) + E(T + V P ) .
Now, we compute E(R P ), the expected time to successfully perform a recovery subject to fail-stop errors. Unlike checkpointing, a recovery is always done at the beginning of a pattern. With probability q f P (R P ), it fails due to a fail-stop error and we have to try again after a downtime. Otherwise, we just need to pay the recovery cost R P . Therefore, we have E(R P ) = q f P (R P ) E lost (R P ) + D + E (R P ) + 1q f P (R P ) R P , which leads to E(R P ) = 1 λ f P +D e λ f P R P -1 . In order to compute E(PATTERN), and according to Equation (3), we need to compute E(T + V P ). Recall that failstop errors can strike at any time during the execution, while silent errors only strike during computations. When a fail-stop error strikes, which happens with probability q f P (T + V P ), we do not need to account for silent errors, since the application is stopped immediately and we need to re-execute T + V P anyway, following a downtime and a recovery. Otherwise, with probability 1-q f P (T +V P ), there is no fail-stop error, and only in this case, we check for silent errors. With probability q s P (T ), a silent error strikes (and is detected by the verification), and we need to perform a recovery and re-execute T + V P . Otherwise, the execution is complete. Overall, we have E(T +V P ) = q f P (T +V P ) E lost (T +V P )+D+E(R P )+E(T +V P ) + 1-q f P (T +V P ) T +V P +q s P (T ) E(R P ) + E(T +V P ) .

Plugging q f P (T +V P ), q s P (T ) and E lost (T +V P ) into the above equation, and solving for E(T + V P ), we get E(T + V P ) = e λ s P T e λ f P (T +V P ) -1 1

λ f P + D + e λ s P (T +V P ) T + V P + e λ f P (T +V P )+λ s P (T ) -1 E(R P ).
Finally, plugging E(T + V P ), E(C P ) and E(R P ) back into Equation ( 3), we find that

E(PATTERN) = 1 λ f P + D e λ f P C P +λ s P T e λ f P (T +V P ) -1 + e λ f P C P -1 + e λ f P R P -1 e λ f P (T +V P +C P )+λ s P (T ) -1 ,
which simplifies to the expression shown in Equation (2).

To find the optimal pattern, one needs to search for values of T and P that minimize the expected execution overhead H(PATTERN) of a pattern based on the expected execution time E(PATTERN) computed above. However, due to the complex expression given by Equation ( 2), an analytical solution is difficult to find, and one has to rely on numerical methods to approximate the optimal solution. In the following, we will use first-order approximation to derive explicit formulas for the optimal checkpointing period and processor allocation. The simulation results in Section IV show that first-order approximation offers very close estimates to the optimal solution.

B. Limitation of First-Order Approximation

Before deriving the optimal pattern parameters, we first investigate the limitation of first-order approximation by bounding the maximum orders of T and P that can be approximated by the approach. Suppose P and T satisfy P = Θ(λ -x ind ) and T = Θ(λ -y ind ), where x, y > 0. Since λ P C P = λ ind P (a + b/P + cP ) and λ P V P = λ ind P (v + u/P ), let λ P (C P + V P ) = λ ind P (d + h/P + cP ) with d = a + v and h = b + u. Hence λ P (C P + V P ) = Θ (λ ind ), where = 1 -2x if c = 0, = 1 -x if c = 0 and d = 0, and = 1 if c = d = 0. Also, λ P T = Θ(λ 1-x-y ind ). Therefore, in order to accurately estimate e λ P C P , e λ P V P and e λ P T using Taylor series expansion (as shown in the next section), we need > 0 and 1 -x -y > 0, which translates to

x < δ, where δ = 1/2 if c = 0 1 if c = 0 , (5)
y < 1 -x . (6)
Inequalities ( 5) and ( 6) specify, respectively, the maximum order on the number of processors and, for a fixed processor count, the maximum order on the checkpointing period. The first-order results obtained within these bounds offer valid approximation to the optimal solution as long as the MTBF µ ind = 1/λ ind of an individual processor is sufficiently large (e.g., in the order of years, which is true for modern processors). Beyond these bounds, unfortunately, the first-order analysis will no longer be applicable.

C. Optimal Checkpointing Period for Fixed Processor Count

In this section, we derive the optimal checkpointing period when the application is run with a fixed number of processors. The result extends the classical formula given by Young [START_REF] Young | A first order approximation to the optimum checkpoint interval[END_REF] and Daly [START_REF] Daly | A higher order estimate of the optimum checkpoint interval for restart dumps[END_REF] for fail-stop errors only.

Theorem 1. Given a processor allocation P = Θ(λ -x ind ) with x < δ as shown in Inequality ( 5), the optimal checkpointing period of a pattern is

T * P = V P + C P λ f P 2 + λ s P . (7)
The expected execution overhead (ignoring lower-order terms) in this case is given by H (T * P , P ) = H(P ) 1 + 2

λ f P 2 + λ s P (V P + C P ) . ( 8
)
Proof. For a fixed P = Θ(λ -x ind ) with x < δ, we can consider C P , R P , V P as constants, which are smaller in magnitude compared to the platform MTBFs 1/λ f P and 1/λ s P . Applying Taylor series to expand e z = 1+z + z 2 2 up to the second-order term, we rewrite the expected execution time E(PATTERN) of a pattern (Equation ( 2)) as follows (ignoring lower-order terms):

E(PATTERN) = T + V P + C P + λ f P 2 + λ s P T 2 + λ f P T (V P + C P + R P + D) + λ s P T (V P + R P ) + λ f P C P C P 2 + R P + V P + D + λ f P V P (V P + R P + D) .
The expected execution overhead of the pattern is computed as H(T, P ) = H(P )

(V P +C P )(1+O(λ ind )) T + λ f P 2 + λ s P T + 1 + O(λ ind ) , where = 1 -2x if c = 0 and = 1 -x otherwise. Since P = Θ(λ -x ind
) is fixed and x < δ, we have > 0 and hence the term O(λ ind ) becomes negligible (in front of 1) when λ ind is sufficiently small (e.g., tends to 0). Given a processor count P , the optimal expected overhead is achieved by setting ∂H(T,P ) ∂T = H(P ) -V P +C P T 2 + λ f P 2 +λ s P = 0, which gives rise to the optimal checkpointing period T * P as shown in Equation [START_REF] Chandy | Distributed snapshots: Determining global states of distributed systems[END_REF]. Now, substituting T * P back in H(T, P ) leads to the expected execution overhead shown in Equation [START_REF] Chen | Online-ABFT: An online algorithm based fault tolerance scheme for soft error detection in iterative methods[END_REF].

Theorem 1 shows that, for a given processor count P = Θ(λ -x ind ) with x < δ as specified by Inequality (5), the optimal checkpointing period satisfies T * P = O(λ -y ind ), where

y =      1/2 if c = 0 (1 -x)/2 if c = 0 and d = 0 1/2 -x if c = 0 and d = 0
.

In all cases, we get y < 1 -x as specified by Inequality (6), thus validating the accuracy of the first-order approximation. Note that, in the case of c = 0 and d = 0, we also need x < 1/2 in order to have y > 0. This additional constraint on the order of P is required to derive the first-order approximation for the optimal checkpointing period as given in Equation [START_REF] Chandy | Distributed snapshots: Determining global states of distributed systems[END_REF].

D. Optimal Processor Allocation and Pattern Parameters

We now optimize the number of allocated processors to an application. We discuss different cases based on the characteristic of the error-free overhead H(P ), as well as on the scalability of checkpointing and verification costs, which have the general form C P = a + b/P + cP and V P = v + u/P . In the following analysis, we assume that all the parameters a, b, c, v, u and the sequential fraction α are constants and independent of the error rate λ ind .

1) H(P ) = α + 1-α P and C P = cP + o(P ), α, c = 0: This case corresponds to the application having a constant sequential fraction and a checkpointing cost that grows linearly with the number of processors (the verification cost has no impact in this scenario): Theorem 2. Suppose the application has a constant sequential fraction α > 0, and a checkpointing cost C P = cP +o(P ). The optimal number of processors and the corresponding optimal checkpointing period of a pattern are

P * = 1 c f 2 + s λ ind 1/4 1 -α 2α 1/2 , (9)
T * = c f 2 + s λ ind 1/2 . ( 10
)
The expected execution overhead (ignoring lower-order terms) in this case is

H(T * , P * ) = α + 2 4α 2 (1 -α) 2 c f 2 + s λ ind 1/4 . (11)
Proof. Substituting H(P ) = α +

= 2α c f 2 + s λ ind -1-α P 2 + o(λ 1/ 2
ind ) = 0. Keeping only the dominating term, the equation above leads to the optimal processor allocation P * as shown in Equation [START_REF] Daly | A higher order estimate of the optimum checkpoint interval for restart dumps[END_REF]. Now, substituting P * back into T * P and H (T * P , P ) and simplifying, we obtain the optimal checkpointing period T * and optimal expected execution overhead H(T * , P * ) as shown in Equations [START_REF] Elnozahy | Checkpointing for peta-scale systems: a look into the future of practical rollback-recovery[END_REF] and [START_REF] Elnozahy | A survey of rollback-recovery protocols in message-passing systems[END_REF], respectively.

2) H(P ) = α + 1-α P and C P + V P = d + o(1), α, d = 0: This case corresponds to the application having a constant sequential fraction, and a constant checkpointing (and verification) cost. Theorem 3. Suppose the application has a constant sequential fraction α > 0, and a checkpointing and verification cost C P + V P = d + o(1). The optimal number of processors and the corresponding optimal checkpointing period of a pattern are

P * = 1 d f 2 + s λ ind 1/3 1 -α α 2/3 , (12)
T * = d 2 f 2 + s λ ind 1/3 α 1 -α 1/3 . ( 13
)
The expected execution overhead (ignoring lower-order terms) in this case is

H(T * , P * ) = α + 3 α 2 (1 -α)d f 2 + s λ ind 1/3 . (14)
Proof. When H(P ) = α + 1-α P and C P + V P = d + o(1), we get from Equation ( 8) the expected execution overhead

H (T * P , P ) = α + 2α d f 2 + s λ ind P + 1-α P + o(λ 1/2 ind P 1/2
). Again, the overhead is minimized by setting

∂H(T * P ,P ) ∂P = 0, which gives α d f 2 + s λind P -1-α P 2 + o(λ 1/2
ind P -1/2 ) = 0. Solving the equation above while focusing on the dominating term gives the optimal P * as shown in Equation [START_REF] Fiala | Detection and correction of silent data corruption for large-scale high-performance computing[END_REF]. Substituting P * back into T * P and H (T * P , P ), we get the optimal T * and H(T * , P * ) as shown in Equations ( 13) and [START_REF] Jin | Optimizing HPC fault-tolerant environment: An analytical approach[END_REF].

3) H(P ) = α + 1-α P and C P + V P = h P , α, h = 0: This case corresponds to the application having a constant sequential fraction, and a checkpointing (and verification) cost that decreases linearly with the number of processors.

Recall in this case that the number of processors satisfies P = Θ(λ -x ind ) with x < 1/2 for the first-order approximation to be valid. Subject to this bound, the expected execution overhead as shown in Equation ( 8) becomes H(T * P , P ) = α + 1-α P 1 + 2 h f 2 + s λ ind , which decreases monotonically as the number of allocated processors P increases up to the order of λ -1/2 ind . Asymptotically, the overhead satisfies H(T * P , P ) = α + Θ (λ x ind ) for x < 1/2. Hence, it is better to enroll as many processors as possible in this case, as long as P is within the approximation bound of O(λ -1/2 ind ). Intuitively, the costs of both checkpointing and verification reduce with the processor count, which enables to place both resilience operators more frequently with smaller checkpointing period to compensate for the increased error rate. Numerical simulations conducted in Section IV show that the optimal number of processors P * is nevertheless bounded in this case with a value beyond O(λ

-1/2 ind ).
4) H(P ) = 1 P : In this case, the application has a perfectly linear speedup function. Again, the expected execution overhead decreases monotonically with the number of allocated processors, and the following gives the expression of H(T * P , P ) in different cases (with lower-order terms ignored):

H(T * P , P ) =          1 P + 2 c f 2 + s λ ind if c = 0 1 P + 2 d f 2 + s λind P if c = 0, d = 0 1 P 1 + 2 h f 2 + s λ ind if c = 0, d = 0 .
In all the cases above, the overhead is asymptotically bounded by Θ (λ x ind ) for x < 1/2, except in the second case (i.e., c = 0, d = 0) where x < 1. Numerical simulations conducted in Section IV show that the optimal processor count P * happens around x = 1/2 and x = 1 for case 1 and case 2, respectively, whereas it is unbounded for the last case, due to the combination of diminishing resilience cost and perfect application speedup.

E. Discussions

Consider a (standard) application that is not perfectly parallel (i.e., α = 0). Theorems 2 and 3 show the impact of the checkpointing cost on the optimal degree of parallelism. When this cost grows linearly with P (e.g., with coordinated checkpointing on stable storage [START_REF] Chandy | Distributed snapshots: Determining global states of distributed systems[END_REF]), Theorem 2 states that the optimal number of processors is P * = Θ(λ -1/4 ind ). In that case, the optimal period has length T * = Θ(λ

-1/2 ind ).
But when this cost remains bounded (e.g., with in-memory checkpointing [START_REF] Zheng | FTC-Charm++: an in-memory checkpoint-based fault tolerant runtime for Charm++ and MPI[END_REF]), then Theorem 3 shows that the optimal solution has both increased parallelism P * = Θ(λ -1/3 ind ) and smaller period T * = Θ(λ -1/3 ind ). These two cases represent most practical checkpointing protocols implemented in today's fault-tolerant systems. To the best of our knowledge, the results are the first to analytically establish the relationship between P * and T * as a function of the resource MTBF µ ind = 1/λ ind .

Finally, we point out that when both checkpointing and verification costs reduce with P (which is rarely the case in practice), first-order approximation has its limitation and can no longer be used to derive the optimal number of processors and optimal checkpointing period. In this case, one can resort to higher-order approximations or numerical methods to compute the optimal pattern parameters, which are still bounded due to the sequential fraction.

IV. EXPERIMENTS

In this section, we conduct simulations to support the analytical study and to demonstrate the accuracy of firstorder approximation under different parameter settings and resilience scenarios. The simulation code is publicly available at http://perso.ens-lyon.fr/aurelien.cavelan/simu.zip.

A. Simulation Settings

We consider four real platforms that were used to evaluate the Scalable Checkpoint/Restart (SCR) library [START_REF] Moody | Design, modeling, and evaluation of a scalable multi-level checkpointing system[END_REF]. Measurements of the platform parameters are provided, including error rates of different sources and various checkpointing costs on a specified number of processors (where each processor has a dual quad-core chip). Following [START_REF] Benoit | Optimal resilience patterns to cope with fail-stop and silent errors[END_REF], the verification cost is set to be the same as that of an in-memory checkpoint, assuming the entire memory footprint needs to be inspected in order to accurately detect silent errors. Table II presents the main parameters of the four platforms. The downtime is set to one hour, i.e., D = 3600s (a repair-based restoration value, see the discussion in Section IV-B5), and the sequential fraction of the application is set to be α = 0.1. These values as well as the individual error rate λ ind will be varied in the simulations to assess their impacts on the performance of the optimal pattern. We envision six resilience scenarios, as shown in Table III, depending on the scalability of the checkpointing and verification overheads discussed in Section II. Altogether, these scenarios cover a wide range of resilience protocols, represented by different checkpointing mechanisms and error detection algorithms. For each scenario, we can compute the resilience parameters (i.e., a, b, c, v, u) based on the values of C P and V P as well as the number of processors given in Table II, and then project the corresponding overheads on any number of processors. The optimal pattern under each scenario can be derived using the first-order analysis presented in Section III. Specifically, for a constant α > 0, scenarios 1 and 2 correspond to case 1 C P = cP + o(P ) , scenarios 3, 4 and 5 correspond to case 2 C P + V P = d + o(1) , and scenario 6 corresponds to case 3 C P + V P = h/P . To assess the accuracy of the first-order approximation, we also compare the performance of the first-order solution with that of the optimal solution obtained using numerical methods such as the one considered in [START_REF] Jin | Optimizing HPC fault-tolerant environment: An analytical approach[END_REF].

Once the pattern parameters are determined, fail-stop and silent errors are injected into the simulator as two independent Poisson processes according to the error rates shown in Table II. The result of each experiment is obtained by averaging over 500 simulation runs, each of which lasts at least 500 patterns. The expected execution overhead of the pattern is computed as the average ratio of the application's execution time with faults and its fault-free execution time.

B. Simulation Results

1) Performance of optimal patterns in different scenarios: Figure 2 shows the performance of the optimal patterns in different resilience scenarios when the sequential fraction of the application is fixed at α = 0.1. We can see that, on all the four platforms, the first-order solution provides a very good approximation to the optimal solution in terms of both checkpointing period and processor allocation, under the first four scenarios (the most realistic ones in practical systems). The execution overheads (≈ 0.11) predicted by the firstorder formulas (Theorems 2 and 3) are almost identical to the optimal overheads and the ones obtained by simulations. The results confirm the validity of first-order approximations in these scenarios.

In scenario 5, the resilience cost is dominated by the verification overhead, which although is a constant has a relatively small value. This significantly increases the optimal processor count and hence the corresponding error rates, thus compromising the accuracy of the first-order approximation (up to 5% in execution overhead), since the lower-order terms start to become non-negligible. In fact, due to the small constant overhead, scenario 5 closely resembles scenario 6, in which case first-order analysis can no longer predict the optimal pattern parameters (thus only the results of numerical methods are shown). Figure 2 shows that the optimal pattern parameters in scenario 6 are indeed in the same orders as those of scenario 5 but with higher processor counts and smaller checkpointing periods.

2) Impact of processor allocation: We study how the number of allocated processors impacts the optimal checkpointing period and the resulting execution overhead under different resilience scenarios. Figure 3 shows the simulation results for the Hera platform (the results are similar for the other platforms). Since the resilience overhead is dominated by the checkpointing cost, the pattern behaviors are mainly influenced by the form of C P , as demonstrated by the almost overlapping curves between the scenarios that share the same C P values. In all scenarios, the checkpointing period decreases with the number of processors (Figure 3(a)), which is needed to compensate for the increased error rates. The execution overhead, on the other hand, first improves with the number of processors due to increased parallelism and then degrades due to more errors striking (Figure 3(b)). The optimal processor counts, as we have seen in Figure 2, tend to be higher for scenarios in which the checkpointing cost C P does not increase (or even decreases) with P . Figure 3(c) shows the difference in execution overhead between the first-order solution and the optimal numerical solution. The difference, for the concerned range of processors, is always within 0.2%, validating once again the accuracy of first-order approximation.

3) Impact of sequential fraction α: Figure 4 shows the impact of the sequential fraction α on the performance of the optimal patterns in scenarios 1, 3 and 5 (from now on, scenarios 2, 4 and 6 are ignored because they have similar performance as scenarios 1, 3 and 5, respectively). We can see that, as α decreases, more processors are enrolled so that the application can benefit from Amdahl's law to achieve lower execution overheads (or equivalently higher speedups). The checkpointing periods, on the other hand, decrease with α due to increased processor count, except in scenario 1 where the optimal period barely changes with the number of processors (see Theorem 1 and Figure 3(a)). As more processors are used, the first-order approximation of P * starts to deviate from the optimal value, but the first-order overhead H * , as shown in Figure 4(c), remains in close proximity to the optimal overhead up to α = 0.0001. Also, compared to the other scenarios, scenario 5 starts to show a better overhead as α becomes smaller, because of its smaller checkpointing cost. However, even when α = 0, the optimal processor allocation is upper bounded by 10 6 in all three scenarios with an overhead strictly above 10 -5 . This is in clear contrast to the error-free execution, where an infinity number of processors can be used to achieve (nearly) null overhead.

4) Impact of error rate λ ind : This experiment assesses the impact of the individual error rate λ ind on the performance of the optimal pattern, in particular on the asymptotic behaviors of the processor allocations and checkpointing periods under different scenarios. Figure 5 shows that, as the processors become more reliable (i.e., as λ ind decreases), the optimal pattern is able to both accommodate more processors and use larger checkpointing periods. The results confirm our analytical study that P * and T * are in the orders of λ -1/4 ind and λ -1/2 ind , respectively, under scenario 1, and are both in the order of λ -1/3 ind under scenarios 3 and 5. Moreover, the firstorder approximation becomes more accurate with decreased λ ind , and the execution overheads tend to the theoretical lower bound of 0.1 for all three scenarios. Figure 6 further shows the behaviors of the optimal patterns when the application is perfectly parallel (i.e., α = 0). Recall that this case does not admit a solution under firstorder approximation. Numerical analysis suggests that, under scenario 1, the optimal solution satisfies P * ≈ Θ(λ (c) Figure 3. Optimal checkpointing period T * P (from Theorem 1) and simulated execution overhead for different number of processors P on platform Hera.

-1/2 ind ), T * ≈ Θ(λ -1/2 ind ),

Simulated execution overhead

Scenario 1 (first-order) Scenario 1 (optimal) Scenario 3 (first-order) Scenario 3 (optimal) Scenario 5 (first-order) Scenario 5 (optimal) (c) Figure 4. Optimal checkpointing period T * and number of processors P * (from Theorems 2 and 3, and from numerical solution), as well as the simulated execution overhead under different sequential fraction α on platform Hera. whether repair-based or replacement-based (migration to a spare processor) restoration is used, downtime can range from a few minutes to several hours [START_REF] Jin | Optimizing HPC fault-tolerant environment: An analytical approach[END_REF]. In this experiment, we vary the downtime from 0 to 3 hours. Figures 7 shows the simulation results when α = 0.1 (the companion research report [START_REF] Cavelan | When Amdahl meets Young/Daly[END_REF] also contains results for smaller values of α with similar observations). Since D does not appear in the formulas of P * and T * (given in Theorems 2 and 3) due to the use of first-order approximation, the optimal pattern obtained by the first-order analysis does not vary with D, while the optimal processor count obtained by the numerical solution decreases with increased downtime. This shows that the optimal pattern parameters are indeed influenced by the downtime. However, the simulated execution overheads in both cases stay close for the first-order solution and the optimal solution, because even a 3-hour downtime is nevertheless much smaller compared to the platform MTBF (in the order of days).

V. CONCLUSION

In this paper, we considered the optimal processor allocation problem for executing a parallel job on a large-scale platform subject to fail-stop and silent errors. We have provided the exact expression for the expected execution time of a pattern, and closed-form first-order approximation formulas to compute the optimal checkpointing period T * and optimal number of processors P * . These formulas are functions of several parameters: the individual processor failure rate λ ind , the sequential fraction of the application α, as well as the checkpointing and verification costs C P and V P . For the latter costs, we have envisioned a comprehensive set of scenarios that are representative of the most important fault-tolerant protocols. To the best of our knowledge, these results are the first that analytically establish the relationship between P * and T * as a function of the resource MTBF µ ind = 1/λ ind , and they offer new insights into the relationships of Amdhal's law and the Young/Daly approximation formula. Also, they provide the first (and direct) characterization of the optimal number of resources to enroll, with given error rates, resilience costs and application speedup profile. We have conducted an extensive set of simulations to support the theoretical study, whose outcome confirms the accuracy of first-order approximation under a wide range of parameter settings.

Further work will be devoted to exploring jobs with different speedup profiles, weak vs. strong scalability issues, and multi-level resilience protocols. All these questions raise important but challenging optimization problems. On a global perspective, we strongly believe that going beyond simulations and providing analytical solutions to these problems would be a major step to understanding the potential and limits of parallelism at extreme scale and in failure-prone environments. (c) Figure 5. Optimal checkpointing period T * and number of processors P * (from Theorems 2 and 3, and from numerical solution), as well as the simulated overhead under different values of λ ind and when α = 0.1 on platform Hera. Optimal number of processor P * Scenario 1 (optimal, α = 0) Scenario 3 (optimal, α = 0) Scenario 5 (optimal, α = 0) P = λ -1/2 P = λ -1 Simulated execution overhead Scenario 1 (optimal, α = 0) Scenario 3 (optimal, α = 0) Scenario 5 (optimal, α = 0) H = λ 1/2 H = λ (c) Figure 6. Optimal checkpointing period T * and number of processors P * (from numerical solution), as well as the simulated execution overhead under different values of λ ind and when α = 0 on platform Hera. (c) Figure 7. Optimal checkpointing period T * and number of processors P * (from Theorems 2 and 3, and from numerical solution), as well as the simulated execution overhead under different downtime D and when α = 0.1 on platform Hera.

Figure 2 .

 2 Figure 2. Performance of the optimal patterns in different resilience scenarios on four platforms when the sequential fraction is fixed at α = 0.1.

Table I .

 I List of Notations.

	Application parameters
	PATTERN(T, P )	Periodic checkpointing pattern
	T	Length (or period) of pattern
	P	Number of allocated processors
	S(P )	Speedup function w/o failure
	H(P ) = 1/S(P )	Execution overhead w/o failure
	E(PATTERN) or E(T, P )	Expected exec. time of a pattern
	S(PATTERN) or S(T, P )	Expected speedup of a pattern
	H(PATTERN) or H(T, P ) Expected exec. overhead of a pattern
	Resilience parameters
	λind = 1/µind	Error rate of an individual processor
	λ f P = f λindP λ s P = sλindP	Fail-stop error rate on P processors Silent error rate on P processors
	CP = a + b/P + cP	Checkpointing cost on P processors
	RP = a + b/P + cP	Recovery cost on P processors
	VP = v + u/P	Verification cost on P processors
	D	Downtime after a fail-stop error

Table II .

 II Platform parameters.

	Platform	Hera	Atlas	Coastal Coastal SSD
	λind	1.69e-8 1.62e-8 2.34e-9	2.34e-9
	f	0.2188	0.0625	0.1667	0.1667
	s	0.7812	0.9375	0.8333	0.8333
	P	512	1024	2048	2048
	CP	300s	439s	1051s	2500s
	VP	15.4s	9.1s	4.5s	180s

Table III .

 III Different resilience scenarios.

	Scenario	1	2	3	4	5	6
	CP , RP	cP	cP	a	a	b/P	b/P
	VP	v	u/P	v	u/P	v	u/P

  and H * ≈ Θ(λ Finally, we evaluate the impact of downtime D on the pattern performance. Depending on

	Optimal checkpointing period T * P	0 10000 20000 30000 40000 50000 60000 70000 80000	(a) and 5, we have P 200 400 600 800 1000 1200 1400 (b) Number of processors P Scenario 1 Scenario 2 Scenario 3 Scenario 4 Scenario 5 Scenario 6 200 400 600 800 1000 1200 1400 Number of processors P 0.10 0.11 0.12 0.13 0.14 0.15 0.16 Simulated execution overhead Scenario 1 Scenario 2 Scenario 3 Scenario 4 Scenario 5 Scenario 6	Overhead difference from optimal solution	0 0.02% 0.04% 0.06% 0.08% 0.10% 0.12% 0.14% 0.16% 0.18%	1/2 ind ), and under scenarios 3 Number of processors P 200 400 600 800 1000 1200 1400 Scenario 1 Scenario 2 Scenario 3 Scenario 4 Scenario 5 Scenario 6

* ≈ Θ(λ -1 ind ), T * ≈ O(1)

, and H * ≈ Θ(λ ind ). 5) Impact of downtime D: