Leonardo Bautista-Gomez

Anne Benoit

Aurélien Cavelan

Saurabh K Raina

Yves Robert

Hongyang Sun

Coping with Recall and Precision of Soft Error Detectors

Many methods are available to detect silent errors in high-performance computing (HPC) applications. Each method comes with a cost, a recall (fraction of all errors that are actually detected, i.e., false negatives), and a precision (fraction of true errors amongst all detected errors, i.e., false positives). The main contribution of this paper is to characterize the optimal computing pattern for an application: which detector(s) to use, how many detectors of each type to use, together with the length of the work segment that precedes each of them. We first prove that detectors with imperfect precisions offer limited usefulness. Then we focus on detectors with perfect precision, and we conduct a comprehensive complexity analysis of this optimization problem, showing NP-completeness and designing an FPTAS (Fully Polynomial-Time Approximation Scheme). On the practical side, we provide a greedy algorithm, whose performance is shown to be close to the optimal for a realistic set of evaluation scenarios. Extensive simulations illustrate the usefulness of detectors with false negatives, which are available at a lower cost than the guaranteed detectors.

Introduction

Failures in high-performance computing (HPC) systems have become a major issue as the number of components proliferates. Indeed, future exascale platforms are expected to be composed of hundreds of thousands of computing nodes [START_REF] Dongarra | The international exascale software project: a call to cooperative action by the global high-performance community[END_REF]. Even if each individual node provides an optimistic mean time between failures (MTBF) of, say 100 years, the whole platform will experience a failure around every few hours on average, which is shorter than the execution time of most HPC applications. Thus, effective resilient protocols will be essential to achieve efficiency.

The de-facto general-purpose error recovery technique in HPC is checkpointing and rollback recovery [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]. Such protocols employ checkpoints to periodically save the state of a parallel application so that when an error strikes some process, the application can be restored to one of its former states. However, checkpoint/restart assumes instantaneous error detection, and therefore applies to fail-stop errors. Silent errors, a.k.a. silent data corruptions (SDC), constitute another source of failures in HPC, whose threat can no longer be ignored [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 | IBM experiments in soft fails in computer electronics[END_REF][START_REF] Moody | Design, modeling, and evaluation of a scalable multi-level checkpointing system[END_REF]. There are several causes of silent errors, such as cosmic radiation, packaging pollution, among others. In contrast to a fail-stop error whose detection is immediate, a silent error is identified only when the corrupted data leads to an unusual application behavior. Such detection latency raises a new challenge: if the error struck before the last checkpoint, and is detected after that checkpoint, then the checkpoint is corrupted and cannot be used for rollback.

In order to avoid corrupted checkpoints, an effective approach consists in employing some verification mechanism and combining it with checkpointing [START_REF] 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][START_REF] Aupy | On the combination of silent error detection and checkpointing[END_REF]. The simplest protocol with this approach would be to execute a verification procedure before taking each checkpoint. If the Time w1 w2 w3 w1 w2 w3

V * C V1 V2 V * C V1 V2 V * C
Figure 1: A periodic pattern (highlighted in red) with three segments, two partial verifications and a verified checkpoint.

verification succeeds, then one can safely store the checkpoint. Otherwise, it means that an 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, more sophisticated protocols can be designed, by coupling multiple verifications with one checkpoint, or interleaving multiple checkpoints and verifications [START_REF] Aupy | On the combination of silent error detection and checkpointing[END_REF][START_REF] Benoit | Efficient checkpoint/verification patterns[END_REF]. The optimal parameter (e.g., number of verifications per checkpoint) in these protocols would be determined by the relative cost of executing a verification. In practice, not all verification mechanisms are 100% accurate and at the same time admit fast implementations. In fact, guaranteeing accurate and efficient detection of silent errors for scientific applications is one of the hardest challenges towards extreme-scale computing [START_REF] Cappello | Toward exascale resilience[END_REF][START_REF] Cappello | Toward exascale resilience: 2014 update[END_REF]. Indeed, thorough and general-purpose error detection is usually very costly, and often involves expensive techniques, such as 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]. Many applications have developed specific verification mechanisms that leverage detailed knowledge of the physics behind the simulation to determine whether the output of a simulation is corruption-free or not. While such application-specific mechanisms do not detect the totality of SDC affecting the hardware, they can guarantee to detect all the corruptions relevant for the end user, thus they can be called arguably perfect detectors or guaranteed verifications, at least from the user's perspective. For many parallel applications, alternative techniques exist that are capable of detecting silent errors but with lower accuracy. We call these techniques partial verifications. One example is the lightweight SDC detector based on data dynamic monitoring [START_REF] Gomez | Detecting silent data corruption through data dynamic monitoring for scientific applications[END_REF], designed to recognize anomalies in HPC datasets based on physical laws and spatial interpolation. Similar fault filters have also been designed to detect silent errors based on time series predictions [START_REF] Berrocal | Lightweight silent data corruption detection based on runtime data analysis for HPC applications[END_REF]. Although not completely accurate, these partial verification techniques nevertheless cover a substantial number of silent errors, and more importantly, they incur very low overheads. These properties make them attractive candidates for designing more efficient resilient protocols.

Since checkpointing is often expensive in terms of both time and space required, to avoid saving corrupted data, we only keep verified checkpoints by placing a guaranteed verification right before each checkpoint. Such a combination ensures that the checkpoint contains valid data and can be safely written onto stable storage. The execution of the application is partitioned into periodic patterns, i.e., computational chunks that repeat over time, and that are delimited by verified checkpoints, possibly with a sequence of partial verifications in between. Figure 1 shows a periodic pattern with two partial verifications followed by a verified checkpoint.

The error detection accuracy of a partial verification can be characterized by two parameters: recall and precision. The recall, denoted by r, is the ratio between the number of detected errors and the total number of errors that occurred during a computation. The precision, denoted by p, is the ratio between the number of true errors and the total number of errors detected by the verification. For example, a basic spatial based SDC detector [START_REF] Gomez | Detecting silent data corruption through data dynamic monitoring for scientific applications[END_REF] has been shown to have a recall value around 0.5 and a precision value very close to 1, which means that it is capable of detecting half of the errors with almost no false alarm. A guaranteed verification can be considered as a special type of partial verification with recall r * = 1 and precision p * = 1. Each partial verification also has an associated cost V , which is typically much smaller than the cost V * of a guaranteed verification. Note that precision and recall are conflicting objectives as they both are directly related to the allowed prediction error of the detector. If the prediction error is too small, then small changes in data behavior will produce false positives. On the other hand, if the allowed prediction error is too large, important corruption could be absorbed in the error corrupting the execution. Thus, one usually sets a target for one of them (e.g., precision = 0.999) and then measures the recall obtained with such a level of precision. Therefore, although it is hard to know in advance the precision and recall of a given detector for a particular application, it is possible to set a target for either one, and then quickly measure the complementary parameter.

An application can use several types of detectors with different overheads and accuracies. For instance, to detect silent errors in HPC datasets, one has the option of using either a detector based on time series prediction [START_REF] Berrocal | Lightweight silent data corruption detection based on runtime data analysis for HPC applications[END_REF], or a detector using spatial multivariate interpolation [START_REF] Gomez | Detecting silent data corruption through data dynamic monitoring for scientific applications[END_REF]. The first one needs more data to make a prediction, hence comes at a higher cost. However, its accuracy is also better. In the example of Figure 1, the second verification may use a detector whose cost is lower than that of the first one, i.e., V 2 < V 1 , but is expected to have a lower accuracy as well, i.e., r 2 < r 1 and/or p 2 < p 1 . This is due to the fact that less accurate detectors perform a much simpler approximation, leading to more prediction errors.

In this paper, we assume that we have several detector types, whose costs and accuracies may differ. At the end of each segment inside the pattern, any detector can be used. The only constraint is to enforce a guaranteed verification after the last segment. Given the values of C (cost to checkpoint) and V * (cost of guaranteed verification), as well as the cost V (j) , recall r (j) and precision p (j) of each detector type D (j) , the main question is which detector(s) to use? Note that we do not assume that all detectors perform equally on all applications, nor that their efficiency can be easily predicted for each type of application. The only requirement is that the accuracy and cost of those detectors can be measured in a relatively easy way. The objective is to find the optimal pattern that minimizes the expected execution time of the application. Intuitively, including more partial verifications in a pattern allows us to detect more errors earlier in the execution, thereby reducing the waste due to re-execution; but that comes at the price of additional overhead in an error-free execution, and in case of bad precision, of unnecessary rollbacks and recoveries. Therefore, an optimal strategy must seek a good tradeoff between error-induced waste and error-free overhead. The problem is intrinsically combinatorial, because there are many parameters to choose: the length of the pattern, the number of partial verifications, and the type and location of each partial verification within the pattern. Of course, the length of an optimal pattern will also depend on the platform MTBF µ.

Only very specific instances of the problem have received a solution yet. For example, when there is a single segment in the pattern without intermediate verification, the only thing to determine is the size of the segment. In the classical protocol for fail-stop errors (where verification is not needed), the optimal checkpointing period is known to be √ 2µC (where C is the checkpoint time), as 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]. A similar result is known for silent errors when using only verified checkpoints [START_REF] Benoit | Efficient checkpoint/verification patterns[END_REF][START_REF] Benoit | Assessing general-purpose algorithms to cope with fail-stop and silent errors[END_REF], and in this case the optimal period is µ(V * + C). This latter case basically amounts to replacing the cost C of a checkpoint by the cost V * + C of a verified checkpoint. The factor of 2 difference is because a silent error is always detected at the end of the pattern, while a fail-stop error triggers an immediate recovery, which occurs on average in the middle of the pattern. These formulas provide first-order approximation to the length of the optimal pattern in the corresponding scenario, and are valid only if the resilience parameters satisfy C, V * µ. To the best of our knowledge, the only analysis that includes partial verifications is the recent work [START_REF] Cavelan | Assessing the impact of partial verifications against silent data corruptions[END_REF], which deals with patterns that may include one or several detector(s) but all of the same type, and which considers detection recall only. While most applications accept several detector types, there has been no attempt to determine which and how many of these detectors should be used. This paper is the first to investigate the use of different types of partial detectors while taking both recall and precision into consideration.

As in those previous works, we apply first-order approximation to tackle the optimization problem. We first show that a partial detector with imperfect precision plays a limited role in the optimization of a pattern. Then we focus on detectors with perfect precision but imperfect recall, and we prove that the optimization problem is NP-complete. In this case, a detector is most useful when it offers the highest accuracy-to-cost ratio, defined as φ (j) = a (j) b (j) , where a (j) = r (j)

2-r (j) denotes the accuracy of the detector and b (j) = V (j) V * +C the relative cost. Finally, we propose a greedy algorithm and a fully polynomial-time approximation scheme (FPTAS) to solve the problem. Simulation results, based on a wide range of parameters from realistic detectors, corroborate the theoretical study by showing that the detector with the best accuracy-to-cost ratio should be favored. In some particular cases with close accuracy-to-cost ratios, an optimal pattern may use multiple detector types, but the greedy algorithm has been shown to work really well in these scenarios.

The rest of this paper is organized as follows. Section 2 surveys the related work. Section 3 introduces the model, notations and assumptions. Section 4 computes the expected execution time of a given pattern, based on which we derive some key properties of the optimal pattern in Section 5. Section 6 provides a comprehensive complexity analysis. While the optimization problem is shown to be NP-complete, a simple greedy algorithm is presented, and a fully polynomial-time approximation scheme is described. Simulation results are presented in Section 7. Finally, Section 8 provides concluding remarks and hints for future directions.

Related Work

Considerable efforts have been directed at detection techniques to reveal silent errors. Hardware mechanisms, such as ECC memory, can detect and even correct a fraction of errors. Unfortunately, future extreme scale systems are expected to observe an important increase in soft errors because of power constraints at increased system size. Most traditional resilient approaches maintain a single checkpoint. If the checkpoint file contains corrupted data, the application faces an irrecoverable failure and must restart from scratch. This is because error detection latency is ignored in traditional rollback and recovery schemes, which assume instantaneous error detection (therefore mainly targeting fail-stop errors) and are unable to accommodate SDC. This section describes some related work on detecting and handling silent errors.

Checkpoint Versioning

One approach to dealing with silent errors is by maintaining several checkpoints in memory [START_REF] Lu | When is multi-version checkpointing needed?[END_REF]. This multiple-checkpoint approach, however, has three major drawbacks. First, it is very demanding in terms of stable storage: each checkpoint typically represents a copy of a large portion of the memory footprint of the application, which may well correspond to tens or even hundreds of terabytes. Second, the application cannot be recovered from fatal failures: suppose we keep k checkpoints in memory, and a silent error has struck before all of them. Then, all live checkpoints are corrupted, and one would have to re-execute the entire application from scratch. Third, even without memory constraints, we have to determine which checkpoint is the last valid one, which is needed to safely recover the application. However, due to the detection latency, we do not know when the silent error has occurred, hence we cannot identify the last valid checkpoint.

Process Replication

There are few methods that can guarantee a perfect detection recall. Process replication is one of them. The simplest technique is triple modular redundancy and voting [START_REF] Lyons | The use of triple-modular redundancy to improve computer reliability[END_REF]. Elliot et al. [START_REF] Elliott | Combining partial redundancy and checkpointing for HPC[END_REF] propose combining partial redundancy and checkpointing, and confirm the benefit of dual and triple redundancy. Fiala et al. [START_REF] Fiala | Detection and correction of silent data corruption for large-scale high-performance computing[END_REF] apply process replication (each process is equipped with a replica, and messages are quadruplicated) in the RedMPI library for high-performance scientific applications. Ni et al. [START_REF] Ni | ACR: Automatic checkpoint/restart for soft and hard error protection[END_REF] use checkpointing and replication to detect and enable fast recovery of applications from both silent errors and hard errors. However, full process replication is too expensive to be used in extreme scale HPC systems and is usually avoided for this reason.

Application-Specific Techniques

Application-specific information can be very useful to enable ad-hoc solutions, which dramatically decrease the cost of detection. Algorithm-based fault tolerance (ABFT) [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][START_REF] Shantharam | Fault tolerant preconditioned conjugate gradient for sparse linear system solution[END_REF] is a well-known technique, which uses checksums to detect up to a certain number of errors in linear algebra kernels. Unfortunately, ABFT can only protect datasets in linear algebra kernels, and it must be implemented for each different kernel, which incurs a large amount of work for large HPC applications. Other techniques have also been advocated. Benson, Schmit and Schreiber [START_REF] Benson | Silent error detection in numerical time-stepping schemes[END_REF] compare the result of a higher-order scheme with that of a lower-order one to detect errors in the numerical analysis of ODEs and PDEs. Sao and Vuduc [START_REF] Sao | Self-stabilizing iterative solvers[END_REF] investigate self-stabilizing corrections after error detection in the conjugate gradient method. Bridges et al. [START_REF] Bridges | Fault-tolerant iterative methods via selective reliability[END_REF] propose linear solvers to tolerant soft faults using selective reliability. Elliot et al. [START_REF] Elliott | Evaluating the impact of SDC on the GMRES iterative solver[END_REF] design a fault-tolerant GMRES capable of converging despite silent errors. Bronevetsky and de Supinski [START_REF] Bronevetsky | Soft error vulnerability of iterative linear algebra methods[END_REF] provide a comparative study of detection costs for iterative methods.

Analytics-Based Corruption Detection

Recently, several SDC detectors based on data analytics have been proposed, showing promising results. These detectors use several interpolation techniques such as time series prediction [START_REF] Berrocal | Lightweight silent data corruption detection based on runtime data analysis for HPC applications[END_REF] and spatial multivariate interpolation [START_REF] Gomez | Detecting silent data corruption through data dynamic monitoring for scientific applications[END_REF][START_REF] Gomez | Detecting and correcting data corruption in stencil applications through multivariate interpolation[END_REF][START_REF] Gomez | Exploiting Spatial Smoothness in HPC Applications to Detect Silent Data Corruption[END_REF]. Such techniques have the benefit of offering large detection coverage for a negligible overhead. However, these detectors do not guarantee full coverage; they can detect only a certain percentage of corruptions (i.e., partial verification with an imperfect recall). Nonetheless, the accuracy-to-cost ratios of these detectors are high, which makes them interesting alternatives at large scale. Similar detectors have also been designed to detect SDCs in the temperature data of the Orbital Thermal Imaging Spectrometer (OTIS) [START_REF] Ciocca | Application-level fault tolerance in the orbital thermal imaging spectrometer[END_REF]. Most of the research work done in this domain focuses on how to increase the error detection accuracy while keeping low overhead, but there has been no theoretical attempt to find the optimal protocol the applications should use when multiple verification techniques are offered by the runtime.

Optimal Strategies with Guaranteed Verifications

Theoretically, various protocols that couple verification and checkpointing have been studied. Aupy et al. [START_REF] Aupy | On the combination of silent error detection and checkpointing[END_REF] propose and analyze two simple patterns: one with k checkpoints and one verification, and the other with k verifications and one checkpoint. The latter pattern, which needs to maintain only one checkpoint, is also analyzed in [START_REF] Benoit | Assessing general-purpose algorithms to cope with fail-stop and silent errors[END_REF] to accommodate both fail-stop and silent errors. Benoit et al. [START_REF] Benoit | Efficient checkpoint/verification patterns[END_REF] extend the analysis of [START_REF] Aupy | On the combination of silent error detection and checkpointing[END_REF] by including p checkpoints and q verifications that are interleaved to form arbitrary patterns. All of these results assume the use of guaranteed verifications only.

As already mentioned, the only analysis that includes partial verifications in the pattern is the recent work of [START_REF] Cavelan | Assessing the impact of partial verifications against silent data corruptions[END_REF]. However, [START_REF] Cavelan | Assessing the impact of partial verifications against silent data corruptions[END_REF] restricts to a single type of partial verification, and it focuses on verifications with perfect precision. In this paper, we provide the first theoretical analysis that includes partial verifications of different types, and that considers verifications with imperfect precision.

Model

We consider divisible-load applications, where checkpoints and verifications can be inserted anywhere in the execution of the application. The occurrence of silent errors follows a Poisson process with arrival rate λ = 1 µ , where µ denotes the MTBF of the platform. We enforce resilience through the use of a pattern that repeats periodically throughout the execution, as discussed in Section 1. When an error alarm is raised inside the pattern, either by a partial verification or by the guaranteed one, we roll back to the beginning of the pattern and recover from the last checkpoint (taken at the end of the execution of the previous pattern, or initial data for the first pattern). Since the last verification of the pattern is guaranteed, we need to maintain only one checkpoint at any time, and it is always valid. The objective is to find a pattern that minimizes the expected execution time of the application.

Let C denote the cost of checkpointing, R the cost of recovery and V * the cost of guaranteed verification. Furthermore, there are k types of detectors available, and the detector type D (j) , where 1 ≤ j ≤ k, is characterized by its cost V (j) , recall r (j) and precision p (j) . For notational convenience, we also define g (j) = 1 -r (j) (proportion of undetected errors) and let D * be the guaranteed detector with cost V * , recall r * = 1 and precision p * = 1.

A pattern Pattern(W, n, α, D) is defined by its total length W , the number n of segments in the pattern, a vector α = [α 1 , α 2 , . . . , α n ] T containing the proportions of the segment sizes, and a vector D = [D 1 , D 2 , . . . , D n-1 , D * ] T containing the detectors used at the end of each segment. We also define the vector of segment sizes w = [w 1 , w 2 , . . . , w n ] T . Formally, for each segment i, where 1 ≤ i ≤ n, w i is the size of the segment, α i = wi W is the proportion of the segment size in the whole pattern, and D i is the detector used at the end of the segment. We have

n i=1 α i = 1,
and

n i=1 w i = W . If i < n, D i has cost V i ,
recall r i and precision p i (we have D i = D (j) for some type j, 1 ≤ j ≤ k), and D n = D * with cost V * , recall r * = 1 and precision p * = 1. Note that the same detector type D (j) may well be used at the end of several segments. Let g i = 1 -r i denote the probability that the i-th detector of the pattern fails to detect an error (for 1 ≤ i < n), and let g [i,j[ = j-1 k=i g k be the probability that the error remains undetected by detectors D i to D j-1 (for 1 ≤ i < j < n). Similarly, p i represents the probability that the i-th detector does not raise a false alarm when there is no error, and let p [i,j[ = j-1 k=i p k denote the probability that no false alarm is raised by detectors D i to D j-1 . In the example of Figure 1, we have W = w 1 + w 2 + w 3 and n = 3. The first partial verification has cost V 1 , recall r 1 and precision p 1 , and the second one has cost V 2 , recall r 2 and precision p 2 .

Let W base denote the base time of an application without any overhead due to resilience techniques (without loss of generality, we assume unit-speed execution). Suppose the execution is divided into periodic patterns, defined by Pattern(W, n, α, D). Let E(W ) be the expected execution time of the pattern. Then, the expected makespan W final of the application when taking silent errors into account can be bounded as follows:

W base W × E(W ) ≤ W final ≤ W base W × E(W ).
This is because the execution involves W base W full patterns, and terminates by a (possibly) incomplete one. For large jobs, we can approximate the execution time as

W final ≈ E(W ) W × W base . Let H(W ) = E(W )
W -1 denote the execution overhead of the pattern. We obtain W final ≈ W base + H(W ) × W base . Thus, minimizing the expected makespan is equivalent to minimizing the pattern overhead H(W ).

We assume that errors only strike the computations, while verifications and I/O transfers (checkpointing and recovery) are protected and are thus error-free. It has been shown in [START_REF] Benoit | Optimal resilience patterns to cope with fail-stop and silent errors[END_REF] that removing this assumption does not affect the asymptotic behavior of a pattern. We also assume statistical independence of the detectors: if the same detector is applied twice, say at time steps t 1 and t 2 , then its recall and precision are the same for both instances. This is because detectors actually detect the effect of an error on the resulting data, rather than the error itself. When an error is missed the first time at step t 1 , either it dissipates and becomes harmless, or it propagates and corrupts more data. In the latter case, running the detector again after some iterations at step t 2 will actually detect the error within the precision and recall of the detector. Furthermore, to be on the safe side, we never use two detectors in a row. The idea is that after a chunk of computations, output data will be considered as random input when fed to the next detector. Understanding error propagation and correlation requires deep knowledge of the application. In this work, we provide a general-purpose solution, hence we have to rely on the independence hypothesis.

Expected Execution Time of a Pattern

In this section, we compute the expected execution time of a pattern by giving a closed-form formula that is exact up to second-order terms. This is a key result that will be used to derive properties of the optimal pattern in the subsequent analysis.

Consider a given pattern Pattern(W, n, α, D). The following proposition shows the expected execution time of this pattern. Pattern(W,n,α,D) is

Proposition 1. The expected time to execute a pattern

E(W ) = n i=1 W α i + V i p [i,n[ + C + 1 p [1,n[ -1 R + λW R p [1,n[ + W α T M α + α T M v + o(λ), ( 1
)
where v is an n × 1 vector defined by

v = [V 1 , V 2 , . . . , V n ]
T , and M is an n × n matrix defined as

M ij = 1 p [i,n[ for i ≤ j and M ij = g [i,j[ p [j,n[ for i > j.
Proof. Let q i denote the probability that an error occurs in the execution of segment i. We can express the expected execution time of the pattern recursively as follows:

E(W ) = n k=1 (1 -q k ) p [1,n[ C + 1 - n k=1 (1 -q k ) p [1,n[ (R + E(W )) + n i=1   i-1 j=1 j-1 k=1 (1 -q k ) p [1,j[ q j g [j,i[ + i-1 k=1 (1 -q k ) p [1,i[   (w i + V i ). ( 2
)
The first line shows that checkpointing will be taken only if no error has occurred in all the segments and no intermediate detector has raised a false alarm. This happens with probability

n k=1 (1 -q k ) n-1 k=1 p k = n k=1 (1 -q k ) p [1,n[ . (3)
In all the other cases, the application needs to recover from the last checkpoint and then re-computes the entire pattern. The second line shows the expected cost involved in the execution of each segment of the pattern and the associated verification. To better understand it, let us consider the third segment of size w 3 and the verification D 3 right after it, which will be executed only when the following events happen (with the probability of each event in brackets):

• There is a fault in the first segment (q 1 ), which is missed by the first verification (1 -r 1 = g 1 ) and again missed by the second verification (1 -r 2 = g 2 ).

• There is no fault in the first segment (1 -q 1 ), the first verification does not raise a false alarm (p 1 ), and there is a fault in the second segment (q 2 ), which is missed by the second verification (1 -r 2 = g 2 ).

• There is no fault in the first segment (1 -q 1 ), the first verification does not raise a false alarm (p 1 ), there is no fault in the second segment (1 -q 2 ), and the second verification does not raise a false alarm (p 2 ).

Thus, the expected cost involved in the execution of this segment is given by

q 1 g 1 g 2 + (1 -q 1 )p 1 q 2 g 2 + (1 -q 1 )p 1 (1 -q 2 )p 2 (w 3 + V 3 ) = q 1 g [1,3[ + (1 -q 1 )p [1,2[ q 2 g [2,3[ + (1 -q 1 )(1 -q 2 )p [1,3[ (w 3 + V 3 ).
We can generalize this reasoning to express the expected cost to execute the i-th segment of the pattern, which leads to Equation (2). Since errors arrive according to the Poisson process, by definition, we have q i = 1 -e -λwi . Substituting it into the recursive formula and solving for E(W ), we obtain the expected execution time as

E(W ) = C + e λW p [1,n[ -1 R + n i=1   i-1 j=1 e λWj,n -e λWj+1,n g [j,i[ p [j,n[ + e λWi,n p [i,n[   (w i + V i ),
where W i,j = j k=i w k . Approximating e λx = 1 + λx + o(λ) up to the first-order term, we can further simplify the expected execution time as

E(W ) = C + 1 + λW p [1,n[ -1 R + n i=1   i-1 j=1 λw j g [j,i[ p [j,n[ + 1 + λ n j=i w j p [i,n[   (w i + V i ) + o(λ) = n i=1 w i + V i p [i,n[ + C + 1 p [1,n[ -1 R + λW R p [1,n[ + λ n i=1   i-1 j=1 w j g [j,i[ p [j,n[ + n j=i w j p [i,n[   (w i + V i ) + o(λ). Letting F = n i=1 i-1 j=1 wj g [j,i[ p [j,n[ + n j=i wj p [i,n[ (w i + V i )
, we can express it in the following matrix form:

F = w T M w + w T M v,
where M is the following n × n matrix:

M =              1 p [1,n[ 1 p [1,n[ 1 p [1,n[ . . . 1 p [1,n[ g [1,2[ p [1,n[ 1 p [2,n[ 1 p [2,n[ . . . 1 p [2,n[ g [1,3[ p [1,n[ g [2,3[ p [2,n[ 1 p [3,n[ . . . 1 p [3,n[ . . . . . . . . . . . . . . . g [1,n[ p [1,n[ g [2,n[ p [2,n[ g [3,n[ p [3,n[ . . . 1 p [n,n[              .
For instance, when n = 4, we have:

M =         1 p1p2p3 1 p1p2p3 1 p1p2p3 1 p1p2p3 g1 p1p2p3 1 p2p3 1 p2p3 1 p2p3 g1g2 p1p2p3 g2 p2p3 1 p3 1 p3 g1g2g3 p1p2p3 g2g3 p2p3 g3 p3 1        
. Now, by using w = W α, we obtain Equation (1), which completes the proof of the proposition.

Properties of Optimal Pattern

In this section, we characterize the properties of the optimal pattern. First, we derive the optimal length of a pattern (Section 5.1). Then, we show that the optimal pattern does not contain partial detectors with imperfect precision (Section 5.2). By focusing on detectors with perfect precision, we define two key parameters to characterize a pattern (Section 5.3). Finally, we obtain the optimal positions for a give set of partial verifications (Section 5.4).

Optimal Length of a Pattern

We first compute the optimal length W of a pattern Pattern(W, n, α, D) in order to minimize its execution overhead H(W ). Pattern(W,n,α,D) is minimized when its length is

Theorem 1. The execution overhead of a pattern

W * = n i=1 Vi p [i,n[ + C + 1 p [1,n[ -1 R λα T M α . ( 4
)
In that case, the overhead is given by

H(W * ) = 2 λα T M α n i=1 V i p [i,n[ + C + 1 p [1,n[ -1 R + n i=1 1 p [i,n[ -1 α i + o( √ λ). ( 5
)
Proof. From the expected execution time of a pattern given in Equation ( 1), we can derive the overhead as follows:

H(W ) = E(W ) W -1 = n i=1 Vi p [i,n[ + C + 1 p [1,n[ -1 R W + λW α T M α + n i=1 1 p [i,n[ -1 α i + λ R p [1,n[ + α T M v + o(λ). ( 6
)
The optimal pattern length that minimizes the execution overhead can now be computed by balancing the first two terms of the above equation, which gives rise to Equation (4). Now, substituting W * back into Equation ( 6), we can obtain the execution overhead shown in Equation ( 5). Note that when the platform MTBF µ = 1/λ is large in front of the resilience parameters, the last two terms of Equation ( 6) become negligible compared to other dominating terms given in Equation ( 5), so they are absorbed into o( √ λ).

Usefulness of Imprecise Detectors

We now assess the usefulness of partial detectors with imperfect precision. We show that an imprecise partial verification (i.e., with p < 1) is not used in the optimal pattern. The result is valid when the platform MTBF µ = 1/λ is large in front of the resilience parameters, and when the precision values are constants and independent of the error rate λ.

Theorem 2. The optimal pattern contains no detector with imprecise verification.

Proof. We show that given any pattern containing imprecise verifications, we can transform it into one that does not use any imprecise verification and that has a better execution overhead.

Consider a given pattern Pattern(W, n, α, D) that contains imprecise verifications. Theorem 1 gives the optimal length of the pattern as well as the execution overhead in that case. From Equation (5), we observe that the overhead is dominated by the term

n i=1 1 p [i,n[ -1 α i , if
the precisions of all detectors are constants and independent of the error rate λ. Assuming that the size of each segment in the pattern is also a constant fraction of the pattern length, we can improve the overhead by making α i approach 0 for all segment i with p [i,n[ < 1. Suppose segment m is the first segment that satisfies p [m,n[ = 1. Then the execution overhead of the pattern becomes

H = 2 λα T M α n i=1 V i p [i,n[ + C + 1 p [1,n[ -1 R + o( √ λ),
where α = [0, . . . , 0, α m , . . . , α n ] T . Now, by removing the first m -1 detectors while keeping the relative sizes of the remaining segments unchanged, we get a new pattern whose overhead is

H = 2 λα T M α n i=m V i + C + o( √ λ),
where α = [α m , . . . , α n ] T and M is the submatrix of M by removing the first m -1 rows and columns. Clearly, we have H < H since

n i=m V i + C < n i=1 Vi p [i,n[ + C + 1 p [1,n[ -1 R and α T M α = α T M α.
Theorem 2 is valid up to first-order estimations and shows that an imprecise partial verification should not be used when the platform MTBF is large. Intuitively, this is because a low precision induces too much re-execution overhead when the error rate is small, making the verification unworthy. Again, we point out that this result holds when the precision can be considered as a constant, which is true in practice as the accuracy of a detector is independent of the error rate. In fact, many practical fault filters do have almost perfect precision under realistic settings [START_REF] Gomez | Detecting silent data corruption through data dynamic monitoring for scientific applications[END_REF][START_REF] Ciocca | Application-level fault tolerance in the orbital thermal imaging spectrometer[END_REF][START_REF] Ciocca | Determining acceptance tests for application-level fault detection[END_REF]. Still, the result is striking, because it is the opposite of what is observed for predictors, for which recall matters more than precision [START_REF] Aupy | Checkpointing algorithms and fault prediction[END_REF].

In the rest of this paper, we will focus on partial verifications with perfect precision (i.e., p = 1) but imperfect recall (i.e., r < 1).

Two Key Parameters

For a pattern Pattern(W, n, α, D) and assuming that all detectors have perfect precision, the expected execution time of the pattern according to Proposition 1 is given by

E(W ) = W + n i=1 V i + C + λW R + W α T M α + α T M v + o(λ),
where M is an n × n matrix defined by M ij = 1 for i ≤ j and M ij = g [i,j[ for i > j.

To characterize such as pattern, we introduce two key parameters in the following.

o ff = n i=1 V i + C, ( 7
)
and the fraction of re-executed work in case of faults is

f re = α T M α. ( 8
)
According to Theorem 1, we can get the optimal pattern length and execution overhead as

W * = o ff λf re , H(W * ) = 2 λo ff f re + o( √ λ).
The equation above shows that when the platform MTBF µ = 1/λ is large in front of the resilience parameters, the expected execution overhead of the optimal pattern is dominated by 2 √ λo ff f re . The problem is then reduced to the minimization of the product o ff f re . Intuitively, this calls for a tradeoff between fault-free overhead and fault-induced re-execution, as a smaller fault-free overhead o ff tends to induce a larger re-execution fraction f re , and vice versa.

Optimal Positions of Verifications

To fully characterize an optimal pattern, we have to determine its number of segments, as well as the type and position of each partial verification. In this section, we consider a pattern whose number of segments is given together with the types of all partial verifications, that is, the value of o ff (Equation ( 7)) is given. We show how to determine the optimal length of each segment (or equivalently, the optimal position of each verification), so as to minimize the value of f re (Equation ( 8)). The following theorem shows the result. It is the most technically involved contribution of this paper, and its lengthy proof can be found in the appendix.

α * k = 1 U n • 1 -g k-1 g k (1 + g k-1 )(1 + g k ) for 1 ≤ k ≤ n, ( 9
)
with g 0 = g n = 0 and

U n = 1 + n-1 i=1 1 -g i 1 + g i . ( 10
)
In that case, the value of f re is

f * re = 1 2 1 + 1 U n . ( 11
)
Note that when all the partial verifications in the pattern have the same type, i.e., g k = g for all 1 ≤ k < n, we retrieve the result of [START_REF] Cavelan | Assessing the impact of partial verifications against silent data corruptions[END_REF], obtaining

f * re = 1 2 1 + 1+g n(1-g)+2g with α * k = 1 n(1-g)+2g for k = 1, n 1-g n(1-g)+2g for k = 2, . . . , n -1 .
The result shows that when there is only one partial verification in the pattern, i.e., n = 2, the two resulting segments share the same length, i.e., α 1 = α 2 = 1 2 . With two or more partial verifications of the same type, the left-most and the right-most segments, each being adjacent to a guaranteed verification, are longer than all the intermediate segments, which have the same length.

Theorem 3 also shows that, for a given set of partial verifications in a pattern, the minimum value of f re does not depend upon their ordering within the pattern.

Corollary 1. For a given set of partial verifications within a pattern, the minimum fraction of re-executed work f *

re is independent of their ordering.

Complexity

This section builds upon the previous results to provide a comprehensive complexity analysis. We introduce the accuracy-to-cost ratio of a detector and show that it is the key parameter to compute the optimal rational solution (Section 6.1). Then we establish the NP-completeness to determine the optimal integer solution (Section 6.2). On the positive side, we design a simple greedy algorithm whose performance is guaranteed, and sketch the construction of an FPTAS for the problem (Section 6.3).

Accuracy-to-Cost Ratio and Rational Solution

Consider a pattern Pattern(W, n, α, D). Let m j denote the number of partial verifications using detector type D (j) in the pattern (the number of indices i < n such that D i is of type D (j) ), and define m = [m 1 , m 2 , . . . , m k ]. Section 5.1 shows that minimizing the execution overhead of the pattern is equivalent to minimizing the product o ff f re . From Equations ( 7) and ( 11), we have

o ff f re = V * +C 2 f (m), where f (m) = 1 + 1 1 + k j=1 m j a (j)   1 + k j=1 m j b (j)   . ( 12
)
In Equation ( 12), we define a (j) = 1-g (j) 1+g (j) to be the accuracy of detector D (j) and define b (j) = V (j)

V * +C to be the relative cost of D (j) . Furthermore, we define φ (j) = a (j) b (j) to be the accuracy-to-cost ratio of D (j) . We will show that this ratio plays a key role in selecting the best detector(s).

Altogether, minimizing the pattern overhead amounts to finding the solution m = [m 1 , m 2 , . . . , m k ] that minimizes f (m), with m j ∈ N 0 for all 1 ≤ j ≤ k. Indeed, once m is given, Proposition 1 and Theorem 3 completely characterize the optimal pattern, giving its length W , the number of segments n = k j=1 m j + 1, and the locations α of all partial detectors (whose ordering does not matter).

We first derive the optimal solution if we relax the integer constraint on m. A rational solution in this case is denoted by m = [ m1 , m2 , . . . , mk ] with mj ≥ 0 for all 1 ≤ j ≤ k. The optimal value of f ( m) is a lower bound on the optimal integer solution. Lemma 1. Suppose there are k types of detectors sorted in non-increasing order of accuracy-to-cost ratio, i.e., φ (1) ≥ φ (2)

≥ • • • ≥ φ (k) . Then, f * ( m) =    1 φ (1) + 1 -1 φ (1) 2 if φ (1) > 2 2 otherwise .
Proof. First, we prove that the optimal rational solution is achieved when only the detector with the largest accuracy-to-cost ratio φ (1) is used. Specifically, given any rational solution m = [ m1 , m2 , . . . , mk ], we show that there exists a solution m = [ m 1 , 0, . . . , 0], which satisfies f ( m ) ≤ f ( m). We have

f ( m) = 1 + 1 1 + k j=1 mj a (j)   1 + k j=1 mj b (j)   = 1 + 1 1 + a (1) k j=1 mj a (j) a (1)   1 + b (1) k j=1 mj b (j) b (1)   . ( 13
)
Let m 1 = k j=1 mj a (j) a (1) and n 1 =

k j=1 mj b (j) b (1) . Since b (j) b (1) ≥ a (j) a (1) for all 1 ≤ j ≤ k, we get n 1 = k j=1 mj b (j) b (1) ≥ k j=1 mj a (j)
a (1) = m 1 . Hence, Equation ( 13) can be written as (1) m . The following derives the minimum value of f ( m). Differentiating f ( m) with respect to m and solving ∂f ( m) ∂ m = 0, we get

f ( m) = 1 + 1 1 + a (1) m 1 1 + b (1) n 1 = 1 + 1 1 + a (1) m 1 1 + b (1) n 1 m 1 • m 1 ≥ 1 + 1 1 + a (1) m 1 1 + b (1) m 1 = f ( m ). Now, define f ( m) = 1 + 1 1+a (1) m 1 + b
m * = - 1 a (1) + 1 a (1) 1 b (1) - 1 a (1) , ( 14
)
which is positive (hence a potential solution) if φ (1) = a (1) b (1) > 2. Taking the second-order derivative of f ( m), we get

∂ 2 f ( m) ∂ m2 =
2a (1) (a (1) -b (1) ) (a (1) m + 1) 3 , which is positive (hence ensures that the solution is the unique minimum) for all m ∈ [0, ∞) if φ (1) = a (1) b (1) > 1. Thus, when φ (1) > 2, the optimal solution is obtained by substituting m * into f ( m), and we get

f ( m * ) = 1 + 1 1 + a (1) m * 1 + b (1) m * = 1 + 1 φ (1) -1 1 - 1 φ (1) + 1 φ (1) 1 - 1 φ (1) = φ (1) -1 φ (1) + 2 φ (1) -1 φ (1) + 1 φ (1) = 1 φ (1) + 1 - 1 φ (1)

2

.

When φ (1) ≤ 2, the minimum value of f ( m) is achieved at m = 0, which gives f (0) = 2.

Lemma 1 shows that the optimal rational solution is achieved with only one detector, namely, the one with the highest accuracy-to-cost ratio. The optimal integer solution, however, may use more than one detector. The following shows that finding the optimal integer solution is NP-complete.

NP-Completeness

We show that finding the optimal integer solution m is NP-complete, even when all detectors share the same accuracy-to-cost ratio. In particular, we consider the following decision problem.

Definition 2 (Multiple Partial Verifications (MPV))

. Given k detectors with the same accuracyto-cost ratio φ, i.e., a (j) b (j) = φ for all 1 ≤ j ≤ k, and a bound K, is there a solution m that satisfies

1 + 1 1 + k j=1 m j a (j)   1 + k j=1 m j b (j)   ≤ K? ( 15
)
Theorem 4. The MPV problem is NP-complete.

Proof. The MPV problem is obviously in NP. We prove the completeness by a reduction from the Unbounded Subset Sum (USS) problem, which is known to be NP-complete [START_REF] Garey | Computers and Intractability, a Guide to the Theory of NP-Completeness[END_REF]. Given a multiset S = {s 1 , s 2 , . . . , s k } of k positive integers and a positive integer I, the USS problem asks if there exists a subset S ⊆ S whose sum is exactly I, i.e., k j=1 m j s j = I, where m j ∈ N 0 . We can further assume that I/s j is not an integer for 1 ≤ j ≤ k, since otherwise we would have a trivial solution.

Given an instance of the USS problem, we construct an instance of the MPV problem with k detectors. First, choose any φ ∈ 2, (I/s max + 1)

2 + 1 , where s max = max j=1..k s j . Then, let . For each 1 ≤ j ≤ k, define a (j) = s j a and b (j) = s j b. According to the range of φ, we have a (j) < 1 and b (j) < 1 for all

1 ≤ j ≤ k. Finally, let K = 1 φ + 1 -1 φ 2 .
If we use only one detector, say D (j) , then Lemma 1 shows that Equation ( 15) is satisfied with the following unique solution:

m * j = - 1 a (j) + 1 a (j) 1 b (j) - 1 a (j) = 1 s j - 1 a + 1 a 1 b - 1 a = I s j ,
which is not an integer by hypothesis, but achieves the lower bound

1 φ + 1 -1 φ 2
= K. Now, we show that, by using multiple detectors, an integer solution to the MPV instance exists if and only if there is an integer solution to the USS instance.

(⇒) Suppose there is an integer solution

m = [m 1 , m 2 , . . . , m k ] such that k j=1 m j s j = I.
Then, by employing m j partial verifications of detector type D (j) for 1 ≤ j ≤ k, we get

1 + 1 1 + k j=1 m j a (j)   1 + k j=1 m j b (j)   = 1 + 1 1 + a k j=1 m j s j   1 + b k j=1 m j s j   = 1 + 1 1 + aI (1 + bI) = 1 φ + 1 - 1 φ 2 = K.
(⇐) Suppose there is an integer solution m = [m 1 , m 2 , . . . , m k ] to the MPV instance such that

1 + 1 1 + k j=1 m j a (j)   1 + k j=1 m j b (j)   = K.
This implies

1 + 1 1 + a k j=1 m j s j   1 + b k j=1 m j s j   = 1 + 2 1 φ 1 - 1 φ .
Let T = k j=1 m j s j . Solving T from the equation above, we get the following unique solution:

T = - 1 a + 1 a 1 b - 1 a = I.
This completes the proof of the theorem.

Greedy Algorithm and FPTAS

To cope with the NP-completeness of minimizing o ff f re , there is a simple and intuitive greedy algorithm. This greedy algorithm uses only the detector with the highest accuracy-to-cost ratio φ (1) . We compute the optimal rational number of partial verifications m * (from Equation ( 14)) and then round it up if it is not an integer. In Section 7, we show that this algorithm performs quite well in practice.

Interestingly, we can guarantee the performance of this simple algorithm. From Lemma 1, we can assume φ (1) = a (1) b (1) > 2. Since a (1) < 1, we can get b (1) < 1/2. If the optimal fractional solution m * given in Equation ( 14) happens to be an integer, then we get the optimal solution. Otherwise, rounding it to m * increases the objective function f (m) shown in Equation ( 12) by at most a factor of δ = 1 + b (1) < 3/2. According to Equation ( 5), this gives a 3/2-approximation algorithm for minimizing the expected execution overhead (and hence the makespan).

In the following, we show that it is possible to have a fully polynomial-time approximation scheme (FPTAS), which ensures, for any > 0, that the solution is within 1 + times the optimal, and that the running time of the algorithm is polynomial in the input size and 1/ . To develop the FPTAS, we perform the following transformations to the problem.

First, we convert all parameters in Equation ( 12) to integers. Since a (j) = 1-g (j) 1+g (j) = r (j) 2-r (j) ≤ 1 and r (j) is rational, we can write a (j) = pj qj , where p j and q j are positive integers with p j ≤ q j . We assume that C, V * and all the V (j) 's are also integers. Thus, minimizing f (m) is equivalent to minimizing the following function:

F (m) = 1 + L L + k j=1 m j L (j)   C + V * + k j=1 m j V (j)   ,
where L denotes the least common multiple (LCM) of q 1 , q 2 , . . . , q k , and L (j) = pj qj L ≤ L. Clearly, L and all the L (j) 's can be represented by a polynomial function of the original input size.

Next, we compute an upper bound on the number of partial verifications. Observe that j) . This implies that the optimal solution must satisfy m j ≤ C+V * V (j) for all 1 ≤ j ≤ k. Therefore, it follows that

F (0) = 2(C + V * ) and F (m) ≥ C + V * + k j=1 m j V (
k j=1 m j V (j) ≤ k(C + V *
). The bound on m j allows us to transform the unbounded problem to the 0-1 problem by providing log m j additional copies of each item type j with doubling V (j) and L (j) values. This is a standard technique also used in transforming the bounded and unbounded knapsack problems to the 0-1 knapsack problem [START_REF] Kellerer | Knapsack Problems[END_REF]. The total number of items becomes

K = k j=1 (1 + log m j ) = O(k log(C + V * ))
, which stays polynomial in the input size.

Define x = [x 1 , x 2 , . . . , x K ], and let L j and V j be the value and cost of item j, respectively. We can now formulate the optimization problem as follows:

minimize F (x) = 1 + L L + K j=1 x j L j   C + V * + K j=1 x j V j   subject to K j=1 x j V j ≤ k(C + V * ) x j ∈ {0, 1} ∀j = 1, 2, . . . , K
and the size of all parameters is a polynomial function of the input size of the original problem.

To find an FPTAS for the problem above, we adopt the technique used in [START_REF] Cohen | The generalized maximum coverage problem[END_REF] for designing an FPTAS for the Maximum Density Knapsack (MDK) problem described below. Maximum Density Knapsack (MDK): Given a set S = {s 1 , s 2 , . . . , s K } of K items, where each item s j ∈ S has a positive integer profit p j and a positive integer weight w j , a total capacity W , and an initial weight w 0 , the MDK problem is formulated as:

maximize K j=1 x j p j w 0 + K j=1 x j w j subject to K j=1 x j w j ≤ W x j ∈ {0, 1} ∀j = 1, 2, . . . , K
Cohen and Katzir [START_REF] Cohen | The generalized maximum coverage problem[END_REF] give an FPTAS for the MDK problem by using the existing FPTAS for the knapsack problem [START_REF] Kellerer | Knapsack Problems[END_REF]. In particular, their algorithm relies on the property that, for every profit P , a minimum weight solution x is found such that P (x) = K j=1 x j p j ≥ P 1+ , for any > 0. This immediately gives rise to an FPTAS for MDK. We can apply the same technique to construct an FPTAS for minimizing F (x). Let x opt denote the optimal solution. By considering V j as weight and L j as profit, we can run the FPTAS for knapsack and return in polynomial time a solution x that satisfies P (x) ≥ P (xopt) 1+

and W (x) ≤ W (x opt ). By setting carefully the value of as a function of , the solution yields F (x) ≤ (1 + )F (x opt ). The detail is similar to the one presented in [START_REF] Cohen | The generalized maximum coverage problem[END_REF] and is omitted here.

Performance Evaluation

In this section, we assess the benefits of partial detectors and evaluate the performance improvement they can provide. Both Maple-based evaluations using the performance model and realistic simulations using fault-injection are conducted. We consider four scenarios. In the first scenario, we study the optimal algorithm using only a single detector type. In the second scenario, we study the impact of the number of partial verifications on the overhead and the optimal pattern length. The third scenario tackles applications with various datasets that expose a range of recall values for each detector rather than a single value. Finally, in the fourth scenario, we focus on the greedy algorithm and compare its performance with the optimal solution that uses more than one type of partial detectors. The simulator code is available for download at http://graal.ens-lyon.fr/~yrobert/two-level.zip, so that interested readers can experiment with it and build relevant scenarios of their choice.

Simulation Setup

We have chosen realistic parameters that depict a typical future exascale platform. The target platform consists of 10 5 nodes whose individual MTBF is 100 years, which amounts to a platform MTBF of µ = 31536 seconds (i.e., about 8.7 hours). The global size of the memory for an exascale machine is expected to be between 32 PB and 64 PB; divided by the number of nodes (10 5 ), the memory size per node goes from 320 GB to 640 GB. Most HPC applications try to populate 90% of the node memory but only 10% -50% of the memory is checkpointed. That makes the checkpoint size between 30 GB and 300 GB. At exascale, most checkpoints will be done in local non-volatile memory (NVM), which is known to be slower than DRAM. We assume checkpoint throughput between 0.5 GB/s and 1 GB/s. While the results presented in this paper are based on these given parameters, we encourage the readers to validate the model with different architecture characteristics.

Concerning the detectors, we assume that they have an almost perfect precision, otherwise we would not use them, as shown in Section 5.2. Thus, the detectors will be configured to adapt their prediction error in order to minimize the number of false positives (i.e., maximize precision) at the cost of some recall. Previous studies [START_REF] Di | Adaptive impact-driven detection of silent data corruption for HPC applications[END_REF] have shown that such configuration can lead to different levels of recall depending on the prediction method and the dataset behavior. Nevertheless, this large study with over 20 different types of simulations showed some trends in performance and efficacy, and we base our simulation parameters in those results. The first detector D (1) has a throughput of about 200 MB/s/process and a recall of 0.5 [START_REF] Gomez | Detecting silent data corruption through data dynamic monitoring for scientific applications[END_REF][START_REF] Gomez | Exploiting Spatial Smoothness in HPC Applications to Detect Silent Data Corruption[END_REF]. The second one D (2) has a throughput of about 20 MB/s/process and a recall of 0.95 [START_REF] Berrocal | Lightweight silent data corruption detection based on runtime data analysis for HPC applications[END_REF]. If we assume 512 processes per node at exascale, then the node throughput of the detectors becomes 100 GB/s for D (1) and 10 GB/s for D (2) . Finally, we assume a third detector D (3) , which is an optimized version that combines the features of the first two detectors, achieving a recall of 0.8 and a throughput of 50 GB/s. Concerning the perfect detector D * , we assume a throughput of 0.5 GB/s based on the fact that application-specific detectors are usually based on physical properties such as mass or energy conservation, which requires global communications and is therefore more expensive than purely local checks.

The simulator generates errors following an exponential distribution of parameter λ. An experiment goes as follows. We feed the simulator with the description of the platform consisting of the parameters described above. For each pattern, we derive the (near) optimal pattern by computing the pattern length W * , and the optimal number m * and positions α * of verifications, using the formulas from our model. The total amount of work for the application is then set to that of 1000 optimal patterns, i.e., W base = 1000W * . The simulator runs each experiment 1000 times, and the simulated overhead is obtained by averaging the results from the 1000 runs.

Scenario 1: Performance of Different Detectors

In the first scenario, we study the optimal algorithm when using a single detector type. Three detectors D (1) , D (2) and D (3) are used separately, with respective costs and recall values V (1) = 3 seconds, V (2) = 30 seconds, V (3) = 6 seconds and r (1) = 0.5, r (2) = 0.95, r (3) = 0.8. The checkpointing cost and the perfect detector cost with recall r * = 1 are fixed at C = V * = 600 seconds. Table 1 summarizes the characteristics of all detector types including the perfect detector, and presents the predicted performance of the optimal pattern using each detector alone. Recall that the accuracy-to-cost ratio is defined as φ (j) = a (j) b (j) , where a (j) = r (j) 2-r (j) denotes the accuracy of the detector and b (j) = V (j)

V * +C the relative cost. Thanks to the higher accuracy-to-cost ratios, the use of partial verifications yields much better performance compared to the baseline algorithm that uses only guaranteed verification. In particular, D (1) and D (3) , which have the highest accuracy-to-cost ratio, offer about 10% improvement in the execution overhead. This translates to about 1 hour of saving for every 10 hours of execution, which is significant in terms of cost and resource usage. The optimal pattern also employs a larger number m * of partial verifications, due to their lower costs, so that checkpoints can be taken less frequently (i.e., with a larger period W * ).

It is interesting to observe, for D (1) and D (3) , that the product of cost and frequency (number of verifications to use in a pattern) is roughly equal. Indeed, for detectors with the same accuracyto-cost ratio φ, our analysis shows that the cost-frequency product is in fact a constant, and it is

given by V m * = V -1 a + 1 a 1 b -1 a = (V * + C) -1 φ + 1 φ 1 -1 φ .
To validate the predicted performance, we have simulated the execution of the optimal patterns by injecting faults with the specified error rate. The last part of Table 1 shows the simulation results, obtained by averaging the values over 1000 runs for the respective patterns. We can see that the simulated overheads are within 1% of the predicted values for all patterns, which demonstrates the high accuracy of first-order approximation to the performance model. The results also confirm the low checkpointing frequency and high recovery rate of computing patterns that employ partial verifications. Intuitively, a higher recovery rate means that more errors are detected earlier in the execution. The results nicely corroborate the theoretical analysis, and demonstrate the benefit of using low-cost partial verifications for dealing with silent errors.

Since the results for realistic simulations with fault injections are very close to the model's predictions, we will focus on studying the model in the following experiments.

Scenario 2: Impact of Number of Partial Verifications

In the second scenario, we study the impact of the number of partial verifications on the execution overhead and pattern length of the optimal partial verification algorithm.

Figure 2 plots the overhead as well as the optimal pattern length as functions of the number of partial verifications m for each detector. The plots also show the overhead (≈ 39%) and optimal pattern length (≈ 6156 seconds) of the baseline algorithm, represented by m = 0. We can see that the expected overhead is reduced for all three detectors by employing partial verifications. For each detector, the optimal overhead is attained for a particular value of m, corroborating the theoretical study. After this point, it starts rising again due to the fact that forcing too many verifications will eventually cause the error-free overhead to increase. The improvement in overhead over the Figure 2: Expected overhead (a) and optimal length (b) of a pattern against the number of partial verifications when a single type of detector is used for three different detectors. The costs and recalls of the three detectors are V (1) = 3 seconds, V (2) = 30 seconds, V (3) = 6 seconds, and r (1) = 0.5, r (2) = 0.95, r (3) = 0.8. The costs of checkpointing and guaranteed verification are C = V * = 600 seconds. The platform MTBF is µ = 31536 seconds.

baseline algorithm is 9% for detectors D (1) and D (3) (optimal overhead for both is ≈ 30%), and 7% for detector D (2) (optimal overhead is ≈ 32%).

Also, the optimal pattern length increases as more partial verifications are employed inside the pattern. This is because the use of intermediate verifications allows silent errors to be detected earlier in the pattern and thus delays the checkpointing process. Interestingly, the optimal pattern lengths of all three detectors are around 8600 seconds when their respective optimal overheads are reached. This implies that an optimal pattern using partial verifications delays the taking of each checkpoint by ≈ 40 minutes, which corresponds to a saving of ≈ 4 checkpoints/day over the baseline algorithm. Concerning the performance of detectors, we can see that D (1) and D (3) are slightly better than D (2) , due to their higher accuracy-to-cost ratios. However, for m ≤ 2, D (2) is better due to its higher recall, while its performance degrades as more D (2) detectors are employed due to its high cost.

Scenario 3: Impact of Detector Recall

In the third scenario, we consider applications with various datasets that expose a change in the detection recall. Therefore, a range of recall values is possible for each detector rather than a single value.

According to [START_REF] Gomez | Exploiting Spatial Smoothness in HPC Applications to Detect Silent Data Corruption[END_REF][START_REF] Gomez | Detecting and correcting data corruption in stencil applications through multivariate interpolation[END_REF], the recall ranges of the three detectors are r (1) = [0.5, 0.9], r (2) = [0.75, 0.95], and r (3) = [0.8, 0.99], respectively. Given a dataset, we obtain a value of recall for each detector within the range. This is because different datasets might expose different levels of entropy and therefore the detectors might expose different prediction accuracies, hence different recalls. Note that although the recall might be different for different datasets, the work done, hence the detection cost, is the same. We rely upon four different metrics, namely, optimal overhead, optimal pattern length, optimal number of verifications, and accuracy-to-cost-ratio, to assess the impact of recall r on the optimal partial verification algorithm.

Figure 3 compares the performance of the three detectors through the four metrics when there is a change in the detection recall for each detector in its recall range. The plots in Figure 3(a) show variations in the optimal overheads with increasing recall values. As expected, the optimal overheads are reduced for all three detectors, since a higher recall value for the same cost (and same number) of verification reduces the fault-induced re-execution cost (f re ), while keeping the fault-free overhead (o ff ) constant, thus minimizes the product o ff f re (see Section 5.1). This reduction in overhead can also be explained through the plots in Figure 3(d), which show an increase in the accuracy-to-cost ratio of each detector with higher recall values. The detectors D (1) and D (3) have the highest accuracy-to-cost ratio, and when used alone inside the pattern, produce the lowest optimal overheads for their respective recall ranges. This substantiates the theoretical analysis of Lemma 1 in Section 6.1. The detector D (2) , being an expensive verification, has a much lower ratio and thus incurs a higher optimal overhead. Figure 3(b) shows oscillations in the curves representing the optimal pattern length for varying recall values. This can be understood by observing the plot in Figure 3(c), where the optimal number of partial verifications m * for all three detectors follows a staircase function. For example, the optimal m * for detector D (1) goes from 33 to 22 as the recall value increases in the range. This is due to the fact that verifications with higher recalls (or accuracy-to-cost ratios) allow us to achieve lower optimal overhead (as in Figure 3(a)) with fewer verifications. This step-wise reduction in the number of verifications leads to minor oscillations in the optimal pattern length. In particular, it is interesting to observe that in case of detector D (2) , by fixing its recall at r (2) = 0.94 and r (2) = 0.95, the optimal overheads are 31.83% and 31.79% respectively, and the optimal pattern lengths are 8668 and 8490 seconds respectively. Thus, approximately 3 minutes of more execution per pattern can be done by compromising 0.04% of overhead. The reduction in the optimal pattern length for a higher recall value is due to a decrement in m * . Note that both oscillations and staircase effects would disappear if m * was allowed to take rational values.

Scenario 4: Performance of Greedy Algorithm

Finally, in the last scenario, we focus on the greedy algorithm presented in Section 6.3 and compare its performance with the optimal solution that uses more than one type of partial detector with different datasets, while keeping the same values for C, V * and µ.

Table 2: Performance comparison of the greedy algorithm and the optimal solution. In all scenarios, C = V * = 600 seconds, V (1) = 3 seconds, V (3) = 6 seconds. m overhead H diff. from opt. Scenario 1: r (1) = 0.51, r (3) = 0.82, φ (1) ≈ 137, φ (3) ≈ 139 Optimal solution [START_REF] Aupy | On the combination of silent error detection and checkpointing[END_REF][START_REF] Cappello | Toward exascale resilience[END_REF] 29.828% 0% Greedy with D (3) (0, [START_REF] Cappello | Toward exascale resilience: 2014 update[END_REF] 29.829% 0.001% Scenario 2: r (1) = 0.58, r (3) = 0.9, φ (1) ≈ 163, φ (3) ≈ 164 Optimal solution [START_REF] Aupy | On the combination of silent error detection and checkpointing[END_REF][START_REF] Bronevetsky | Soft error vulnerability of iterative linear algebra methods[END_REF] 29.659% 0% Greedy with D (3) (0, [START_REF] Cappello | Toward exascale resilience[END_REF] 29.661% 0.002% Scenario 3: r (1) = 0.64, r (3) = 0.97, φ (1) ≈ 188, φ (3) ≈ 188 Optimal solution [START_REF] Aupy | On the combination of silent error detection and checkpointing[END_REF][START_REF] Bridges | Fault-tolerant iterative methods via selective reliability[END_REF] 29.523% 0% Greedy with D (1) [START_REF] Elliott | Evaluating the impact of SDC on the GMRES iterative solver[END_REF]0) 29.524% 0.001% Greedy with D (3) (0, [START_REF] Bronevetsky | Soft error vulnerability of iterative linear algebra methods[END_REF] 29.525% 0.002%

As in the previous experiment, the recall of each detector is given a range of possible values, and its actual value depends on the dataset. As shown in Figure 3(d), even with the recall ranges, D (2) always has a lower accuracy-to-cost ratio compared to D (1) and D (3) , which share similar ratios. Table 2 presents three scenarios that we have identified, where a combination of D (1) and D (3) constitutes the optimal pattern. In all these scenarios, the greedy algorithm, which uses only the detector with the highest accuracy-to-cost ratio, performs within 0.002% of the optimal solution. The results show that the greedy algorithm performs extremely well under these practical settings, even though the optimal pattern may employ both D (1) and D (3) in the solution.

Conclusion and Future Work

In this paper, we provided a comprehensive analysis of computing patterns that employ different types of partial verifications for detecting silent errors in HPC applications. We demonstrated that detectors with imperfect precision should not be used in such computing patterns. When considering detectors with imperfect recall, we showed that the optimization problem is NP-complete in general, and we proposed both a greedy algorithm and an FPTAS for choosing the number of detectors to be used, as well as their types and locations in the pattern. Extensive simulations based on realistic detector settings showed that the greedy algorithm works well in practice, and confirmed the usefulness of partial detectors to cope with silent errors in exascale systems.

In future work, we plan to investigate detectors with imperfect recall (and possibly imperfect precision) for an application consisting in a set of tasks with precedence constraints, where a detector can be employed only at the end of a task, hence reducing the flexibility in the computational scenario. Also, it would be interesting to combine the use of such detectors with a reasonable use of replication: one may prefer to replicate a small task rather than to use a costly detector for detecting silent data corruptions.

We have α T Aα opt = f opt re α T c = f opt re because c T α = 1. Similarly, we get (α opt ) T Aα opt = f opt re . Hence, we derive that X = α T Aα -f opt re ≥ 0, with equality if and only if α = α opt . Hence the optimal value of f re is achieved for α opt , and is equal to f opt re . In the following, we prove that A is symmetric positive definite (SPD), and that α opt = α * and f opt re = f * re . To avoid ambiguity, we use superscripts like A (n) whenever needed to identify the problem size n (the number of work segments).

From the definition of matrix A, we can rewrite A (n) as:

A (n) = 1 2 J (n) + B (n) ,
where J (n) is the n × n matrix whose entries are all 1, and B (n) is the n × n matrix defined by

B (n) ij = g [i,j[ for i ≤ j.
We start by proving two properties of α * .

Lemma 2. α * is a valid vector, i.e., n k=1 α * k = 1.

Proof. The proof is by induction on n. First, for n = 1 we do have 1+g1 + 1 1+g1 = 1, which is also correct. Assume that this result holds up to n -1. We can express α * (n) as:

α * (n) = U n-1 U n           α * (n-1) 1 α * (n-1) 2
. . .

α * (n-1) n-2 α * (n-1) n-1 0           +          0 0 . . . 0 -g n-1 α * (n) n α * (n) n          . ( 18
)
Therefore, we have:

+ U n-1 U n α * (n-1) n-1 -g n-1 α * (n) n + α * (n) n = U n-1 U n n-1 k=1 α * (n-1) k + α * (n) n (1 -g n-1 ) = U n-1 U n n-1 k=1 α * (n-1) k + 1 U n • 1 -g n-1 1 + g n-1 .
Now, using the inductive hypothesis that n-1 k=1 α * (n-1) k = 1, we get:

n k=1 α * (n) k = 1 U n U n-1 + 1 -g n-1 1 + g n-1 = 1 U n • U n = 1,
which concludes the proof.

Lemma 3. Aα * = f * re c.

Notice that x (n-2) T 1 γ (n-1) is actually the last row of the product B (n-1) γ (n-1) , which, by induction, is 1. Therefore we get:

x (n-1) T γ(n-1) + γ (n)

n = g n-1 + γ (n) n (1 -g 2 n-1 ) = g n-1 + (1 + g n-1 )(1 -g n-1 ) 1 + g n-1 = g n-1 + 1 -g n-1 = 1.
This concludes the proof.

We now prove that A is SPD. This requires several intermediate steps. Proof. To prove that B is nonsingular, we prove by induction on n that B (n) y (n) = 0 (n) has only one solution y (n) = 0 (n) . First, for n = 1 we have y

(1) 1 = 0, which is correct. Then, for n = 2 we have the following equation:

1 g 1 g 1 1 y (2) 1 y (2) 2
= 0 (2) , from which we derive y 2 (1 -g 2 1 ) = 0, hence y (2) = 0 (2) , which is also correct. Now, assume that the result holds up to n -1. We want to solve the general equation:

B (n-1)
x (n-1) x (n-1) T 1 ȳ(n-1) y

(n) n = 0 (n) , ( 21
)
which is equivalent to:

   B (n-2)
x (n-2) x (n-2) g n-1 x (n-2) T 1 g n-1 x (n-2) T g n-1 g n- [START_REF] Aupy | On the combination of silent error detection and checkpointing[END_REF] 1

      ȳ(n-2) y (n) n-1 y (n) n    = 0 (n) , (22)
where ȳ(n-1) and ȳ(n-2) are the truncated vectors containing respectively the first n -1 and n -2 elements of y (n) (for a problem of size n). First, let us expand Equation ( 22) and consider only the last two equations of the system:

x (n-2) T ȳ(n-2) + y (n) n-1 + g n-1 y (n) n = 0 g n-1 x (n-2) T ȳ(n-2) + g n-1 y (n) n-1 + y (n) n = 0.
We can derive that y = 0 back into Equation [START_REF] Ciocca | Determining acceptance tests for application-level fault detection[END_REF], we derive that: B (n-1) ȳ(n-1) = 0 (n-1) .

Using the induction hypothesis for B (n-1) ȳ(n-1) = 0 (n-1) , we have ȳ(n-1) = 0 (n-1) and thus y (n) = 0 (n) , which implies that B (n) is nonsingular. Hence, from Equation [START_REF] Chen | Online-ABFT: An online algorithm based fault tolerance scheme for soft error detection in iterative methods[END_REF], we can get:

α * = 1 U n B -1 c,
which concludes the proof.

Definition 1 .

 1 The fault-free overhead o ff of a pattern Pattern(W, n, α, D) is

Theorem 3 .

 3 Consider a pattern Pattern(W, n, α, D) where W , n, and D are given. The fraction of re-executed work f re is minimized when α = α * , where

a b = φ and -1 a + 1 a 1 b - 1 a

 111 = I, so we can get a = √

Figure 3 :

 3 Figure3: Optimal overhead (a), optimal pattern length (b), optimal number of partial verifications (c), and accuracyto-cost ratio (d) for three different detectors as functions of recall in their respective recall ranges (r(1) = [0.5, 0.9], r(2) = [0.75, 0.95] and r(3) = [0.8, 0.99]).

Lemma 4 .

 4 B is nonsingular and α* = 1 Un B -1 c.

Table 1 :

 1 Characteristics of all detector types and the performance of the optimal pattern using each detector type alone.

		D (1)	D (2)	D (3)	D *
	Cost V (seconds)	3	30	6	600
	Recall r	0.5	0.95	0.8	1
	Accuracy-to-cost ratio φ	133	36	133	2
	Predicted overhead H *	29.872% 31.798% 29.872% 39.014%
	Optimal W * (hours)	2.41	2.38	2.41	1.71
	Optimal m *	33	6	17	0
	Simulated overhead	30.313% 32.537% 30.743% 40.414%
	Ave. # checkpoints (per day)	7.28	7.23	7.25	9.50
	Ave. # recoveries (per day)	2.26	2.25	2.33	1.94

Acknowledgment

We would like to thank the reviewers for their valuable comments and suggestions, which greatly helped improve the quality of this paper. This research was funded in part by the European project SCoRPiO, by the LABEX MILYON (ANR-10-LABX-0070) of Université de Lyon, within the program "Investissements d'Avenir" (ANR-11-IDEX-0007) operated by the French National Research Agency (ANR), by the PIA ELCI project, by the U.S. Department of Energy, Office of Science, Advanced Scientific Computing Research Program, under Contract DE-AC02-06CH11357, by the INRIA-Illinois-ANL-BSC Joint Laboratory on Extreme Scale Computing, and by the Center for Exascale Simulation of Advanced Reactors at Argonne. Yves Robert is with Institut Universitaire de France.

Appendix. Proof of Theorem 3

The goal is to minimize f re = α T M α (Equation ( 8)) subject to the constraint n k=1 α k = 1, which we rewrite as c T α = 1 with c = [1, 1, . . . , 1] T . Hence, we have a quadratic minimization problem under a linear constraint. For convenience, let us replace M by A = M +M T 2 , which gives the same value for f re , and we obtain the symmetric matrix A defined as

for i ≤ j. For instance, when n = 4, we have:

When A is symmetric positive definite (SPD), which we will show later in the proof, there is a unique solution

obtained for

This result is shown as follows. Let a valid vector α be a vector such that c T α = 1. We have c T α opt = f opt re (c T A -1 c) = 1, hence α opt is indeed a valid vector. Then, because A is SPD, we have X = (αα opt ) T A(α -α opt ) ≥ 0 for any valid vector α, and X = 0 if and only if α = α opt . Developing X, we get

Proof. We have A = 1 2 (J + B) and from Lemma 2 Jα * = (

for all n ≥ 1. Equivalently, letting γ = U n α * , we prove by induction on n that B (n) γ (n) = c (n) . First, for n = 1 we have B (1) γ (1) = 1, and for n = 2 we get: (2) . Now, suppose the result holds up to n -1. We can write:

where γ(n-1) is the (n-1)×1 truncated vector containing the first n-1 elements of γ (n) (for a problem of size n), and x (n-1) is an (n-1)×1 vector defined as

For instance, for n = 4 we have

From Equation ( 18), we can derive:

The last line applies the inductive hypothesis B (n-1) γ (n-1) = c (n-1) as well as the property that 1) . Putting this result back into Equation ( 20), we derive that

Using the property x (n-1) T = x (n-2) T 1 g n-1 , we can write:

Lemma 5. A is nonsingular.

Proof. To prove that A is nonsingular, we solve Ay = 0 and show that y = 0. First, we can write:

From Lemma 4, we know that B is nonsingular and B -1 c = U n α * . Therefore, we get:

Summing the components of both sides of Equation ( 23), we obtain:

which implies y = 0 from Equation [START_REF] Daly | A higher order estimate of the optimum checkpoint interval for restart dumps[END_REF], and this concludes the proof that A is nonsingular.

Lemma 6. The last column of B -1 is given by:

Proof. Because we do not need the whole inverse of B, we solve Bz = d, where d = 0 0 • • • 1 T , hence z will be the last column of B -1 . We can write:

where z(n-2) is the truncated vector containing the first n -2 elements of z (n) . Expanding the product, we get the following system of equations:

Since B (n) is nonsingular, there is a unique solution. We can check that z(n-2) = 0 (n-2) , z

1-gn-1 2 is indeed a solution, which concludes the proof.

Remark. The matrix B is an extension of the famous KMS symmetric matrix K [START_REF] Dow | Explicit inverses of Toeplitz and associated matrices[END_REF], where K ij = g j-i for i ≤ j (recall that B ij = g [i,j[ ). The inverse of B turns out to be tridiagonal, just as that of K, and we get:

For instance, when n = 4 we have

-g2

The proof of this result is very similar to the proof of Lemma 6.

Lemma 7. A -1

nn = 2 Un(1+gn-1)+2gn-1 (Un+1)(1-gn-1)(1+gn-1) 2 . Proof. As in the proof of Lemma 6, we compute the last column of A -1 , which we call β, by solving Aβ = d. Because we already solved Bz = d, we have:

Remember that J is the matrix whose entries are all 1. Hence, we have Jβ = ( n i=1 β i ) c. Also, from Lemma 4, we have Bα * = c

Un . Therefore, we can derive:

Summing the components of both sides of Equation ( 24), we get 2

From Lemma 6, we can easily compute

.

Finally, from Equation ( 24), we derive that

which concludes the proof.

Lemma 8. A is symmetric positive definite (SPD).

Proof. Note that by construction, A, J and B are all symmetric matrices. To show that A is positive definite, we show that all its principal minors are strictly positive. Recall that the principal minor of order k of A (n) is the determinant of the submatrix of size k that consists of the first k rows and columns of A (n) . But this submatrix is exactly A (k) , the matrix for the problem of size k, so the result will follow if we show that det A (n) > 0 for all n ≥ 1. We prove by induction on n that det A

For n = 1, Equation ( 25) gives det A (1) = 1, which is correct. Suppose the result holds up to n -1. Since A (n) is nonsingular, using the co-factor method, we get that

Therefore, using the definition of U n and the induction hypothesis for det A (n-1) , we can get:

det

Now, plugging A (n) -1 nn from Lemma 7 into Equation (26), we get:

which shows that Equation (25) holds for det A (n) and completes the proof that A (n) is SPD.

We are almost done! There remains to show that α opt = α * and f opt re = f * re . But Lemma 3 shows that Aα * = f * re c, hence α * = f * re A -1 c and 1 = c T α * = f * re (c T A -1 c), which leads to f opt re = f * re , and finally α opt = α * . This concludes the proof of Theorem 3.