Anne Benoit

Yves Robert

Aurélien Cavelan

Hongyang Sun

Assessing general-purpose algorithms to cope with fail-stop and silent errors

Keywords: Algorithms, Design, Experimentation HPC, resilience, checkpoint, verification, failures, fail-stop error, silent data corruption, silent error

In this paper, we combine the traditional checkpointing and rollback recovery strategies with verification mechanisms to address both fail-stop and silent errors. The objective is to minimize either makespan or energy consumption. While DVFS is a popular approach for reducing the energy consumption, using lower speeds/voltages can increase the number of errors, thereby complicating the problem. We consider an application workflow whose dependence graph is a chain of tasks, and we study three execution scenarios: (i) a single speed is used during the whole execution; (ii) a second, possibly higher speed is used for any potential re-execution; (iii) different pairs of speeds can be used throughout the execution. For each scenario, we determine the optimal checkpointing and verification locations (and the optimal speeds for the third scenario) to minimize either objective. The different execution scenarios are then assessed and compared through an extensive set of experiments.

INTRODUCTION

For HPC applications, scale is a major opportunity. Massive parallelism with 100,000+ nodes is the most viable path to achieving sustained petascale performance. Future platforms will enrol even more computing resources to enter the exascale era.

Unfortunately, scale is also a major threat. Resilience is the first challenge. 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 in 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 is composed of several hundreds of cores. Worse, several types of errors need to be considered when computing at scale. In addition to classical fail-stop errors (such as hardware failures), silent errors (a.k.a silent data corruptions) constitute another threat that cannot be ignored any longer [START_REF] O'gorman | The effect of cosmic rays on the soft error rate of a DRAM at ground level[END_REF]Ziegler et al. 1996a;Ziegler et al. 1996b;[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].

Another challenge is energy consumption. The power requirement of current petascale platforms is that of a small town, hence measures must be taken to reduce the energy consumption of future platforms. A widely-used strategy is to use DVFS techniques: modern processors can run at different speeds, and lower speeds induce big savings in energy consumption. In a nutshell, this is because the dynamic power consumed when computing at speed s is proportional to s 3 , while execution time is proportional to 1/s. As a result, computing energy (which is time times power) is proportional to s 2 . However, static power must be accounted for, and it is paid throughout the duration of the execution, which calls for a shorter execution (at higher speed). Overall there are tradeoffs to be found, but in most practical settings, using lower speeds reduces global energy consumption.

To further complicate the picture, energy savings have an impact on resilience. Obviously, the longer the execution, the higher the expected number of errors, hence using a lower speed to save energy may well induce extra time and overhead to cope with more errors throughout execution. Even worse (again!), lower speeds are usually obtained via lower voltages, which themselves induce higher error rates and further increase the latter overhead.

In this paper, we introduce a model that addresses both challenges: resilience and energy-consumption. In addition, we address both fail-stop and silent errors, which, to the best of our knowledge, has only been achieved before through costly replication techniques [START_REF] Ni | ACR: Automatic Checkpoint/Restart for Soft and Hard Error Protection[END_REF]]. While checkpoint/restart [START_REF] Chandy | Distributed Snapshots: Determining Global States of Distributed Systems[END_REF][START_REF] Mootaz) Elnozahy | A survey of rollbackrecovery protocols in message-passing systems[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. The problem with silent errors is detection latency: contrarily to a fail-stop error whose detection is immediate, a silent error is identified only when the corrupted data is activated and/or leads to an unusual application behavior. However, checkpoint and rollback recovery assumes instantaneous error detection, and this raises a new difficulty: if the error stroke before the last checkpoint, and is detected after that checkpoint, then the checkpoint is corrupted and cannot be used to restore the application. To solve this problem, one may envision to keep several checkpoints in memory, and to restore the application from the last valid checkpoint, thereby rolling back to the last correct state of the application [START_REF] Lu | When is Multi-version Checkpointing Needed?[END_REF]]. This multiple-checkpoint approach has three major drawbacks. First, it is very demanding in terms of stable storage: each checkpoint typically represents a copy of the entire memory footprint of the application, which may well correspond to several terabytes. The second drawback is the possibility of fatal failures. Indeed, if we keep k checkpoints in memory, the approach assumes that the error that is currently detected did not strike before all the checkpoints still kept in memory, which would be fatal: in that latter case, all live checkpoints are corrupted, and one would have to re-execute the entire application from scratch. The probability of a fatal failure is evaluated in [START_REF] Aupy | On the combination of silent error detection and checkpointing[END_REF] for various error distribution laws and values of k. The third drawback of the approach is the most serious, and applies even without memory constraints, i.e., if we could store an infinite number of checkpoints in storage. The critical question is to determine which checkpoint is the last valid one. We need this information to safely recover from that point on. However, because of the detection latency, we do not know when the silent error has indeed occurred, hence we cannot identify the last valid checkpoint, unless some verification system is enforced.

We introduce such a verification system in this paper. This approach is agnostic of the nature of this verification mechanism (checksum, error correcting code, coherence tests, etc.). It is also fully general-purpose, although application-specific information, if available, can always be used to decrease the cost of verification: see the overview of related work in Section 2 for examples. In this context, the simplest protocol is to take only verified checkpoints (VC). This corresponds to performing a verification just before taking each checkpoint. If the verification succeeds, then one can safely store the checkpoint. If the verification fails, then 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 also safely recover from the last checkpoint, just as in the classical checkpoint and rollback recovery method. This VC-ONLY protocol 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 strategy is more involved. We extend both the classical bound by Young [START_REF] Young | A first order approximation to the optimum checkpoint interval[END_REF]] or Daly [START_REF] Daly | A higher order estimate of the optimum checkpoint interval for restart dumps[END_REF]], and the dynamic programming algorithm of Toueg and Babaoglu [START_REF] Toueg | On the Optimum Checkpoint Selection Problem[END_REF], to deal with these error sources.

While taking checkpoints without verifications seems a bad idea (because of the memory cost, and of the risk of saving corrupted data), taking a verification without checkpointing may be interesting. Indeed, if silent errors are frequent enough, it is worth verifying the data in between two (verified) checkpoints, so as to detect a possible silent error earlier in the execution, and thereby re-executing less work. We refer to this protocol as VC+V that allows for both verified checkpoints and isolated verifications.

One major objective of this paper is to study VC+V algorithms coupling verification and checkpointing, and to analytically determine the best balance of verifications between checkpoints so as to minimize either makespan (total execution time) or energy consumption. To achieve this ambitious goal, we restrict to a simplified, yet realistic, application framework. We consider application workflows that consist of a number of parallel tasks that execute on the platform, and that exchange data at the end of their executions. In other words, the task graph is a linear chain, and each task (except maybe the first one and the last one) reads data from its predecessor and produces data for its successor. This scenario corresponds to a high-performance computing application whose workflow is partitioned into a succession of (typically large) tightly-coupled computational kernels, each of them being identified as a task by the model. At the end of each task, we have the opportunity either to perform a verification of the task output or to perform a verification followed by a checkpoint.

In addition, we have to select a speed for each execution of each task. We envision three different execution scenarios. In the simple SINGLESPEED scenario, a unique speed s is available throughout execution. In the intermediate REEXECSPEED scenario, the same speed s is used for the first execution of each task, but another speed σ is available for re-execution after a fail-stop or silent error. Here, the first speed s can be considered as the regular speed, while the second speed σ corresponds to an adjusted speed to either speed up or to slow down the re-execution after an error strikes, depending on the optimization objective. Finally, in the advanced MULTISPEED scenario, two different speeds s i and σ i can be used to execute the tasks in between two consecutive checkpoints (which we call a task segment). Each speed s i or σ i can be freely chosen among a set of K discrete speeds. Note that these speeds may well vary from one segment to another. For each execution scenario, we provide an optimal dynamic programming algorithm to determine the best locations of checkpoints and verifications (and for the MULTISPEED scenario we also provide the corresponding optimal pair of speeds for each segment).

The main contributions of this paper are the following: -We introduce a general-purpose model to deal with both fail-stop and silent errors, combining checkpoints with a verification mechanism. -We consider three execution scenarios, first with a single speed, then in case of reexecution, and finally with several discrete speeds that can freely change after each checkpoint. -For the three execution scenarios and for both makespan and energy objectives, we consider two approaches, one using verified checkpoints only and the other one using additional isolated verifications. We provide a dynamic programming algorithm that determines the best locations of checkpoints and verifications across a chain of tasks for each scenario/approach/objective combination. -For both makespan and energy objectives, we derive the optimal checkpointing and verification periods for the divisible load application model, where checkpoints and verifications can be placed at any point in execution of the application.

-We conduct an extensive set of simulations to support the theory and to assess the performance of each algorithm. The rest of the paper is organized as follows. Section 2 provides an overview of related work. Section 3 is devoted to formally defining the framework and all model parameters. The next three sections deal with the main algorithmic contributions: for all three execution scenarios, we design optimal algorithms for the VC-ONLY approach, and then for the VC+V approach, targeting either time or energy minimization. Then in Section 7, we report on a comprehensive set of experiments to assess the impact of each scenario and approach. Finally, we outline main conclusions and directions for future work in Section 8.

RELATED WORK

Fail-stop errors

The de-facto general-purpose error recovery technique in high performance computing is checkpoint and rollback recovery [START_REF] Chandy | Distributed Snapshots: Determining Global States of Distributed Systems[END_REF][START_REF] Mootaz) Elnozahy | A survey of rollbackrecovery 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 back to one of its former states. There are several families of checkpointing protocols, but they share a common feature: each checkpoint forms a consistent recovery line, i.e., when an error is detected, one can rollback to the last checkpoint and resume execution, after a downtime and a recovery time.

Many models are available to understand the behavior of checkpoint/restart [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][START_REF] Ozaki | Distribution-free checkpoint placement algorithms based on min-max principle[END_REF][START_REF] Bougeret | Checkpointing strategies for parallel jobs[END_REF]. For a divisible load application where checkpoints can be inserted at any point in execution for a nominal cost C, there exist well-known formulas due to Young [START_REF] Young | A first order approximation to the optimum checkpoint interval[END_REF]] and Daly [START_REF] Daly | A higher order estimate of the optimum checkpoint interval for restart dumps[END_REF]] to determine the optimal checkpointing period. For an application composed of a linear chain of tasks, which is also the subject of this paper, the problem of finding the optimal checkpoint strategy, i.e., of determining which tasks to checkpoint, in order to minimize the expected execution time, has been solved by [START_REF] Toueg | On the Optimum Checkpoint Selection Problem[END_REF], using a dynamic programming algorithm.

One major contribution of this paper is to extend both the Young/Daly formulas [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]] and the result of Toueg and Babaoglu [START_REF] Toueg | On the Optimum Checkpoint Selection Problem[END_REF] to deal with silent errors in addition to fail-stop errors, and with several discrete speeds instead of a single one.

Silent errors

Most traditional approaches maintain a single checkpoint. If the checkpoint file includes errors, 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 failures) and are unable to accommodate silent errors. We focus in this section on related work about silent errors. A comprehensive list of techniques and references is provided by Lu, Zheng and Chien [START_REF] Lu | When is Multi-version Checkpointing Needed?[END_REF].

Considerable efforts have been directed at error-checking to reveal silent errors. Error detection is usually very costly. Hardware mechanisms, such as ECC memory, can detect and even correct a fraction of errors, but in practice they are complemented with software techniques. The simplest technique is triple modular redundancy and voting [START_REF] Lyons | The use of triple-modular redundancy to improve computer reliability[END_REF], which induces a highly costly verification. For highperformance scientific applications, process replication (each process is equipped with a replica, and messages are quadruplicated) is proposed in the RedMPI library [START_REF] Fiala | Detection and correction of silent data corruption for large-scale high-performance computing[END_REF]. Elliot et al. [START_REF] Elliott | Combining partial redundancy and checkpointing for HPC[END_REF]] combine partial redundancy and checkpointing, and confirm the benefit of dual and triple redundancy. The drawback is that twice the number of processing resources is required (for dual redundancy). As already mentioned, an approach based on checkpointing and replication is proposed in [START_REF] Ni | ACR: Automatic Checkpoint/Restart for Soft and Hard Error Protection[END_REF], in order to detect and enable fast recovery of applications from both silent errors and hard errors.

Application-specific information can be very useful to enable ad-hoc solutions, which dramatically decrease the cost of detection. Many techniques have been advocated. They include memory scrubbing [START_REF] Hwang | Cosmic rays don't strike twice: understanding the nature of DRAM errors and the implications for system design[END_REF]] and ABFT techniques [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], such as coding for the sparse-matrix vector multiplication kernel [START_REF] Shantharam | Fault Tolerant Preconditioned Conjugate Gradient for Sparse Linear System Solution[END_REF], and coupling a higher-order with a lower-order scheme for PDEs [START_REF] Benson | Silent error detection in numerical timestepping schemes[END_REF]]. These methods can only detect an error but do not correct it. Self-stabilizing corrections after error detection in the conjugate gradient method are investigated by [START_REF] Sao | Self-stabilizing Iterative Solvers[END_REF]. [START_REF] Heroux | Fault-tolerant iterative methods via selective reliability[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.

A nice instantiation of the checkpoint and verification mechanism that we study in this paper is provided by Chen [START_REF] Chen | Online-ABFT: An online algorithm based fault tolerance scheme for soft error detection in iterative methods[END_REF]], who deals with sparse iterative solvers. Consider a simple method such as the PCG, the Preconditioned Conjugate Gradient method: Chen's approach performs a periodic verification every d iterations, and a periodic checkpoint every d × c iterations, which is a particular case of the VC+V approach with equi-distance verifications. For PCG, the verification amounts to checking the orthogonality of two vectors and to recomputing and checking the residual. The cost of the verification is small in front of the cost of an iteration, especially when the preconditioner requires much more flops than a sparse matrix-vector product.

As already mentioned, our work is agnostic of the underlying error-detection technique and takes the cost of verification as an input parameter to the model.

Energy model and error rate

Modern processors are equipped with dynamic voltage and frequency scaling (DVFS) capability. The total power consumption is the sum of the static/idle power and the dynamic power, which is proportional to the cube of the processing speed s [START_REF] Yao | A Scheduling Model for Reduced CPU Energy[END_REF][START_REF] Bansal | Speed Scaling to Manage Energy and Temperature[END_REF]], i.e., P (s) = P idle + β • s 3 , where β > 0. A widely used reliability model assumes that radiation-induced transient faults (soft errors) follow a Poisson process with an average arrival rate λ. The impact of DVFS on the error rate is, however, not completely clear.

On the one hand, lowering the voltage/frequency is believed to have an adverse effect on the system reliability [START_REF] Dixit | The impact of new technology on soft error rates[END_REF][START_REF] Dakai Zhu | The Effects of Energy Management on Reliability in Realtime Embedded Systems[END_REF]]. In particular, many papers (e.g., [START_REF] Dakai Zhu | The Effects of Energy Management on Reliability in Realtime Embedded Systems[END_REF][START_REF] Zhao | Reliability-Aware Dynamic Voltage Scaling for Energy-Constrained Real-Time Embedded Systems[END_REF][START_REF] Aupy | Energy-aware scheduling under reliability and makespan constraints[END_REF][START_REF] Das | Combined DVFS and Mapping Exploration for Lifetime and Soft-error Susceptibility Improvement in MPSoCs[END_REF]) have assumed the following exponential error rate model:

λ(s) = λ 0 • 10 d(smax-s) smax-s min , (1)
where λ 0 denotes the average error rate at the maximum speed s max , d > 0 is a constant indicating the sensitivity of error rate to voltage/frequency scaling, and s min is the minimum speed. This model suggests that the error rate increases exponentially with decreased processing speed, which is a result of decreasing the voltage/frequency and hence lowering the circuit's critical charge (i.e., the minimum charge required to cause an error in the circuit).

On the other hand, the failure rates of computing nodes have also been observed to increase with temperature [START_REF] Patterson | The effect of data center temperature on energy efficiency[END_REF][START_REF] Wu-Chun Feng | Making a Case for Efficient Supercomputing[END_REF][START_REF] Hsu | A Power-Aware Run-Time System for High-Performance Computing[END_REF][START_REF] Sarood | A 'Cool' Way of Improving the Reliability of HPC Machines[END_REF], which generally increases together with the processing speed (voltage/frequency). As a rule of thumb, Arrenhius' equation when applied to microelec- Energy needed to recover from task T i tronic devices suggests that the error rate doubles for every 10 • C increase in the temperature [START_REF] Wu-Chun Feng | Making a Case for Efficient Supercomputing[END_REF]]. In general, the mean time between failure (MTBF) of a processor, which is the reciprocal of failure rate, can be expressed as [START_REF] Sarood | A 'Cool' Way of Improving the Reliability of HPC Machines[END_REF]]:

M T BF = 1 λ = A • e -b•T ,
where A and b are thermal constants, and T denotes the temperature of the processor. Under the reasonable assumption that higher operating voltage/frequency leads to higher temperature, this model suggests that the error rate increases with increased processing speed.

Clearly, the two models above draw contradictory conclusions on the impact of DVFS on error rates. In practice, the impact of the first model may be more evident, as the temperature dependency in some systems has been observed to be linear (or even not exist) instead of being exponential [START_REF] El-Sayed | Temperature Management in Data Centers: Why Some (Might) Like It Hot[END_REF]. Generally speaking, the processing speed should have a composite effect on the average error rate by taking both voltage level and temperature into account. In the experimental section of this paper (Section 7), we adopt a tradeoff model and modify Equation (1) to include the impact of temperature.

FRAMEWORK

In this section we introduce all model parameters. For reference, main notations are summarized in Table I. We start with a description of the application workflows. Then we present parameters related to energy consumption. Next we detail the resilient model to deal with fail-stop and silent errors. We conclude by presenting the various execution scenarios.

Application workflows

We consider application workflows whose task graph is a linear chain

T 1 → T 2 • • • → T n .
Here n is the number of tasks, and each task T i is weighted by its computational cost w i . We target a platform with p identical processors. Each task is a parallel task that is executed on the whole platform. A fundamental characteristic of the application model is that it allows to view the platform as a single (albeit very powerful) macro-processor, thereby providing a tractable abstraction of the problem.

Energy consumption

When computing (including verification), we use DVFS to change the speed of the processors, and assume a set S = {s 1 , s 2 , . . . , s K } of K discrete computing speeds. During checkpointing and recovery, we assume a dedicated (constant) power consumption. Altogether, the total power consumption of the macro-processor is p times the power consumption of each individual resource. It is decomposed into three different components: -P idle , the static power dissipated when the platform is on (even idle); -P cpu (s), the dynamic power spent by operating the CPU at speed s; -P io , the dynamic power spent by I/O transfers (checkpoints and recoveries).

Assume w.l.o.g. that there is no overlap between CPU operations and I/O transfers. Then the total energy consumed during the execution of the application can be expressed as

Energy = P idle (T cpu + T io ) + K i=1 P cpu (s i )T cpu (s i ) + P io T io where T cpu (s i ) is the time spent on computing at speed s i , T cpu = K i=1 T cpu (s i )
is the total time spent on computing, and T io is the total time spent on I/O transfers.

The time to compute tasks T i to T j at speed s is T i,j (s) = 1 s j k=i w i and the corresponding energy is E i,j (s) = T i,j (s)(P idle + P cpu (s)).

Resilience

We assume that errors only strike during computations, and not during I/O transfers (checkpoints and recoveries) nor verifications. We consider two types of errors: fail-stop and silent.

To cope with fail-stop errors, we use checkpointing, and to cope with silent errors, an additional verification mechanism is used. The time to checkpoint (the output of) task T i is C i , the time to recover from (the checkpoint of) task T i is R i , and the time to verify (the output of) task T i at speed s is V i (s). We assume that both fail-stop errors and silent errors follow an exponential distribution with average rates λ F (s) and λ S (s), respectively, where s denotes the current computing speed. Given an error rate λ, let p(λ, L) = 1 -e -λL denote the probability that a error strikes during an execution of length L. For convenience, we define p F i,j (s) = p(λ F (s), T i,j (s)) to be the probability that a fail-stop error strikes when executing from T i to T j , and define p S i,j (s) = p(λ S (s), T i,j (s)) similarly for silent errors.

Resilience also has a cost in terms of energy consumption. Specifically, the energy to checkpoint task

T i is E C i = C i (P idle + P io ), to recover from task T i is E R i = R i (P idle +P io ), and to verify task T i at speed s is E V i (s) = V i (s)(P idle + P cpu (s)).

Execution scenarios

We consider three different execution scenarios:

SINGLESPEED A single speed s is used during the whole execution (K = 1).

REEXECSPEED There are two speeds, s for the first execution of each task, and σ for any potential re-execution (K = 2). MULTISPEED We are given K discrete speeds, where K is arbitrary. The workflow chain is cut into subchains called segments and delimited by checkpoints. For each of these segments, we can freely choose the speed of the first execution, and the (possibly different) speed for any ulterior execution, among the K speeds. Note that these speeds may well vary from one segment to another.

Optimization problems

For each execution scenario, we deal with four problems: TIME-VC-ONLY Minimize total execution time (or makespan) using the VC-ONLY approach. TIME-VC+V Minimize total execution time (or makespan) using the VC+V approach. ENERGY-VC-ONLY Minimize total energy consumption using the VC-ONLY approach. ENERGY-VC+V Minimize total energy consumption using the VC+V approach.

For the SINGLESPEED and REEXECSPEED scenarios, we have to decide the optimal locations of the checkpoints (VC-ONLY) and of the verifications (VC+V). For the MULTISPEED scenario, we further have to select a pair of speeds (first execution and re-execution) for each segment.

SINGLESPEED SCENARIO

In this scenario, we are given a single processing speed s. We investigate the VC-ONLY and VC+V approaches. For each approach, we present an optimal polynomial-time dynamic programming algorithm.

VC-ONLY: Using verified checkpoints only

In this approach, we only place verified checkpoints. We aimed at finding the best positions for checkpoints in order to minimize the total execution time (TIME-VC-ONLY) or the total energy consumption (ENERGY-VC-ONLY). PROOF. We define T ime C (j, s) to be the optimal expected time to successfully execute tasks T 1 , . . . , T j , where T j has a verified checkpoint, and there are possibly other verified checkpoints from T 1 to T j-1 . Note that we always verify and checkpoint the last task T n to save the final result, so the goal is to find T ime C (n, s).

To compute T ime C (j, s), we formulate the following dynamic program by trying all possible locations for the last checkpoint before T j (see Figure 1):

T ime C (j, s) = min 0≤i<j {T ime C (i, s) + T C (i + 1, j, s)} + C j ,
where T C (i, j, s) is the expected time to successfully execute the tasks T i to T j , provided that T i-1 and T j are both verified and checkpointed, and while no other task in between is verified nor checkpointed. Note that we also account for the checkpointing cost C j for task T j , which is not included in the definition of T C . To initialize the dynamic program, we define T ime C (0, s) = 0. In the following, we show how to compute T C (i, j, s) for each (i, j) pair with i ≤ j. We start by considering only silent errors and use the notation T S C (i, j, s) for that purpose. Silent errors can occur at any time during the computation but we only detect them after all tasks have been executed. Thus, we always have to pay T i,j (s)+V j (s), the time to execute from task T i to T j at speed s and to verify T j . If the verification fails, which happens with probability p S i,j (s), a silent error has occurred and we have to recover from T i-1 and start anew. For convenience, we assume that there is a virtual task T 0 that is always verified and checkpointed, with a recovery cost R 0 = 0. Mathematically, we can express T S C (i, j, s) as

0 1 2 i V C i+1 j V C T ime C (i, s) T C (i + 1, j, s) + Cj
T S C (i, j, s) = T i,j (s) + V j (s) + p S i,j (s) R i-1 + T S C (i, j, s) ,
which simplifies to

T S C (i, j, s) = e λ S (s)Ti,j (s) (T i,j (s) + V j (s)) + (e λ S (s)Ti,j (s) -1)R i-1 .
Things are different when accounting for fail-stop errors, because the application will stop immediately when a fail-stop error occurs, even in the middle of the computation. Let T losti,j (s) denote the expected time lost during the execution from T i to T j if a fail-stop error strikes, and it can be expressed as

T losti,j (s) = ∞ 0 xP(X = x|X < T i,j (s))dx = 1 P(X < T i,j (s)) Ti,j (s) 0 xλ F (s)e -λ F (s)x dx ,
where P(X = x) denotes the probability that a fail-stop error strikes at time x. By definition, we have P(X < T i,j (s)) = 1 -e -λ F (s) Ti,j (s) . Integrating by parts, we can get

T losti,j (s) = 1 λ F (s) - T i,j (s) e λ F (s)Ti,j (s) -1 . (2)
Therefore, the expected execution time T F C (i, j, s) when considering only fail-stop errors is given by

T F C (i, j, s) = p F i,j (s) T losti,j (s) + R i-1 + T F C (i, j, s) + 1 -p F i,j (s) T i,j (s) ,
which simplifies to

T F C (i, j, s) = (e λ F (s)Ti,j (s) -1) 1 λ F (s) + R i-1 .
We now account for both fail-stop and silent errors, and use the notation T SF C (i, j, s) for that purpose. To this end, we consider fail-stop errors first. If the application stops, then we do not need to perform a verification since we must do a recovery anyway. If no fail-stop error strikes during the execution, we proceed with the verification and check for silent errors. Therefore,

T SF C (i, j, s) = p F i,j (s) T losti,j (s) + R i-1 + T SF C (i, j, s) + 1 -p F i,j (s) T i,j (s) + V j (s) + p S i,j (s) R i-1 + T SF C (i, j, s) .
When plugging p F i,j (s), p S i,j (s) and T losti,j (s) into the above equation, we get

T SF C (i, j, s) = e λ S (s)Ti,j (s) e λ F (s)Ti,j (s) -1 λ F (s) + V j (s) + e (λ F (s)+λ S (s))Ti,j (s) -1 R i-1 . (3)
By setting T C (i, j, s) = T SF C (i, j, s), we can now compute T ime C (j, s) for all j = 1, • • • , n. For the complexity, the computation of T SF C (i, j, s) for all (i, j) pairs with i ≤ j takes O(n 2 ) time. The computation of the dynamic programming table for T ime C (j, s) also takes O(n 2 ) time, as T ime C (j, s) depends on at most j other entries in the same table, which are already computed. Therefore, the overall complexity is O(n 2 ), and this concludes the proof.

Theorem 4.1 extends the result of Toueg and Babaoglu [START_REF] Toueg | On the Optimum Checkpoint Selection Problem[END_REF] to a linear chain of tasks subject to both fail-stop and silent errors. For the sake of comparing with the case of a divisible load application, we extend Young/Daly's 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]] as follows.

PROPOSITION 4.2. For a divisible load application subject to both fail-stop and silent errors, a first-order approximation of the optimal checkpointing period to minimize the expected execution time is

T time V CO (s) = 2(V (s) + C) λ F (s) + 2λ S (s)
, where V (s) is the verification cost at speed s, λ F (s) is the rate of fail-stop errors at speed s, λ S (s) is the rate of silent errors at speed s, and C is the checkpointing cost.

PROOF. In the presence of fail-stop errors only, Young/Daly's 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] gives the optimal checkpointing period 2C λ F (s) if we process the application with speed s. With both fail-stop and silent errors, let T (s) denote the period. According to Equation (3), the expected execution time for a segment between two consecutive checkpoints (accounting for the cost of the checkpoint itself) is given by

T ime(T (s)) = e λ S (s)T (s) e λ F (s)T (s) -1 λ F (s) + V (s) + e (λ F (s)+λ S (s))T (s) -1 R + C , (4)
and we are interested in the value of T (s) that minimizes the overhead T ime(T (s))

T (s)
compared to the error-free and checkpoint-free execution time T (s). Using Taylor expansion to approximate e λT ≈ 1 + λT + λ 2 T 2 2 up to the second term, we get the following first-order approximation for the overhead:

T ime(T (s)) T (s) = λ F (s) 2 + λ S (s) T (s) + V (s) + C T (s) + 1 + λ S (s)V (s) + (λ F (s) + λ S (s))R .
Differentiating the above expression with respect to T (s), we find that both fail-stop and silent errors. We stress that, as in Young/Daly's formula, this result is a first-order approximation, which is valid only if all resilience parameters C, R and V (s) are small in front of both MTBF values, namely 1/λ F (s) for fail-stop errors and 1/λ S (s) for silent errors.

T time V CO (s) = 2(V (s)+C) λ F (s)+2λ S (
In Section 7, we compare the makespan derived from this formula with the performance of the VC-ONLY algorithm. With a chain of tasks, we have less flexibility for checkpointing than with a divisible load application, and it is interesting to numerically evaluate the difference due to the application framework. PROOF. The proof is similar to that of the TIME-VC-ONLY problem presented in Section 4.1.1. Here, we replace T ime C (j, s) with Energy C (j, s), which is the optimal expected energy to successfully execute the tasks T 1 to T j . Instead of T SF C (i, j, s), we use E SF C (i, j, s) to denote the total expected energy to successfully execute all the tasks from T i to T j without any checkpoint and verification in between, while T i-1 and T j are both verified and checkpointed. The goal is to find Energy C (n, s) and the corresponding dynamic program is formulated as:

Energy C (j, s) = min 0≤i<j {Energy C (i, s) + E SF C (i + 1, j, s)} + E C j .
Previously we used T losti,j (s) to denote the expected time lost when a fail-stop error occurs. Now, we use E losti,j (s) = T losti,j (s) (P cpu (s) + P idle ) to denote the expected energy lost when a fail-stop error stroke during the execution from task T i to task T j . Therefore, we can express E SF C (i, j, s) as follows:

E SF C (i, j, s) = p F i,j (s) E losti,j (s) + E R i-1 + E SF C (i, j, s) + 1 -p F i,j (s) E i,j (s) + E V j (s) + p S i,j (s) E R i-1 + E SF C (i, j, s) ,
which simplifies to E SF C (i, j, s) = (P idle + P cpu (s)) e λ S (s)Ti,j (s) e λ F (s)Ti,j (s) -1

λ F (s) + V j (s) + e (λ F (s)+λ S (s))Ti,j (s) -1 E R i-1 . (5)
Clearly, the time complexity is the same as that of the makespan minimization algorithm (in Theorem 4.1). Proposition 4.3 extends the dynamic programming algorithm of Toueg and Babaoglu to account for energy consumption. Now, for consistency, we present the optimal checkpointing period that minimizes the total energy consumption in the case of a divisible load application. PROPOSITION 4.4. For a divisible load application subject to both fail-stop and silent errors, a first-order approximation of the optimal checkpointing period to minimize the expected energy consumption is

T energy V CO (s) = 2(V (s) + C e (s)) λ F (s) + 2λ S (s) , (6)
where V (s) is the verification cost at speed s, λ F (s) is the rate of fail-stop errors at speed s, λ S (s) is the rate of silent errors at speed s. Here, C e (s) is defined as C e (s) = C(P idle +Pio) s) , where C is the checkpointing cost, P idle is the static idle power, P cpu (s) is the dynamic CPU power at speed s, and P io is the dynamic I/O power.

P idle +Pcpu(
PROOF. The proof is similar to that of Proposition 4.2. In the presence of both fail-stop and silent errors, let T (s) denote the checkpointing period and let E(s) = T (s)(P idle + P cpu (s)) denote the error-free and checkpoint-free energy consumption in the period. According to Equation ( 5), the expected energy consumption for a segment between two consecutive checkpoints (accounting for the cost of the checkpoint itself) is given by:

Energy(T (s)) = (P idle + P cpu (s)) e λ S (s)T (s) e λ F (s)T (s) -1 λ F (s) + V (s) + e (λ F (s)+λ S (s))T (s) -1 (P idle + P io )R + (P idle + P io )C ,
which can be rewritten as

Energy(T (s)) = (P idle + P cpu (s)) F (T (s)) ,
where F (T (s)) is similar to T ime(T (s)) in Equation ( 4), but with C replaced by C e (s) = C(P idle +Pio)

P idle +Pcpu(s) and R replaced by R e (s) = R(P idle +Pio) P idle +Pcpu(s) as follows:

F (T (s)) = e λ S (s)T (s) e λ F (s)T (s) -1 λ F (s) + V (s) + e (λ F (s)+λ S (s))T (s) -1 R e (s) + C e (s)
.

Again, we are interested in the value of T (s) that minimizes the overhead

Energy(T (s)) E(s) = F (T (s)) T (s) .
Using the same approach as in Proposition 4.2, we can get the following first-order approximation to the overhead:

F (T (s)) T (s) = λ F (s) 2 + λ S (s) T (s) + V (s) + C e (s) T (s) + 1 + λ S (s)V (s) + (λ F (s) + λ S (s))R e (s) .
Differentiating the above expression with respect to T (s), we find that T energy V CO (s) = 2(V (s)+Ce(s)) λ F (s)+2λ S (s) minimizes the overhead. This result is analogous to what we have in Proposition 4.2 and extends Young/Daly's formula to cover energy consumption in the presence of both fail-stop and silent errors.

VC+V: Using verified checkpoints and single verifications

In this approach, we can place additional verifications between two checkpoints, which allows to detect silent errors before reaching the next checkpoint, and hence to avoid wasted execution by performing early recoveries. We aim at finding the best positions for checkpoints and verifications in order to minimize the total execution time (TIME-VC+V) or the total energy consumption (ENERGY-VC+V). For both objectives, adding extra verifications between two checkpoints adds an extra step in the algorithm, which results in a higher complexity.

Assessing general-purpose algorithms to cope with fail-stop and silent errors 1:13 4.2.1. TIME-VC+V: MINIMIZING MAKESPAN THEOREM 4.5. For the SINGLESPEED scenario, the TIME-VC+V problem can be solved by a dynamic programming algorithm in O(n 3 ) time.

PROOF. In the TIME-VC-ONLY problem, we were only allowed to place verified checkpoints. Here, we can add single verifications that are not associated with a checkpoint. The main idea is to replace T C in the dynamic program of Theorem 4.1 by another expression T ime V (i, j, s), which denotes the optimal expected time to successfully execute from task T i to task T j (and to verify it), provided that T i-1 has a verified checkpoint and only single verifications are allowed within tasks T i , . . . , T j-1 . Furthermore, we use T ime V C (j, s) to denote the optimal expected time to successfully execute the first j tasks, where T j has a verified checkpoint, and there are possibly other verified checkpoints and single verifications before T j . The goal is to find T ime V C (n, s). The dynamic program to compute T ime V C (j, s) can be formulated as (see Figure 2): In particular, we try all possible locations for the last checkpoint before T j , and for each location T i , we compute the optimal expected time T ime V (i + 1, j, s) to execute tasks T i+1 to T j with only single verifications in between. We also account for the checkpointing time C j , which is not included in the definition of T ime V . By initializing the dynamic program with T ime V C (0, s) = 0, we can then compute the optimal solution as in the TIME-VC-ONLY problem.

T ime V C (j, s) = min 0≤i<j {T ime V C (i, s) + T ime V (i + 1, j, s)} + C j . 0 1 2 i V C i+1 j V C T ime V C (i, s) T ime V (i + 1, j, s) + Cj
It remains to compute T ime V (i, j, s) for each (i, j) pair with i ≤ j. To this end, we formulate another dynamic program by trying all possible locations for the last single verification before T j (see Figure 3):

T ime V (i, j, s) = min i-1≤l<j {T ime V (i, l, s) + T V (l + 1, j, i -1, s)} ,
where T V (i, j, l c , s) is the expected time to successfully execute all the tasks from T i to T j (and to verify T j ), knowing that if an error strikes, we can recover from T lc , the last task before T i to have a verified checkpoint.

i-1 V C i l V l+1 j V T ime V (i, l, s) T V (l + 1, j, i -1, s)
Fig. 3. Illustration of the dynamic programming formulation for T ime V (i, j, s).

First, we show how to compute T V (i, j, l c , s). When accounting for only silent errors (with notation T S V ), we always execute from task T i to task T j and then verify T j . In case of failure, we recover from T lc and redo the entire computation from T lc+1 to T j , which contains a single verification after T i-1 and possibly other single verifications between T lc+1 and T i-2 . Hence, we have

T S V (i, j, l c , s) = T i,j (s) + V j (s) + p S i,j (s) R lc + T ime V (l c + 1, i -1, s) + T S V (i, j, l c , s) ,
which simplifies to

T S V (i, j, l c , s) = e λ S (s)Ti,j (s) (T i,j (s) + V j (s)) + (e λ S (s)Ti,j (s) -1) (R lc + T ime V (l c + 1, i -1, s)) .
When there are only fail-stop errors, we do not need to perform any single verification, and hence the problem becomes simply the TIME-VC-ONLY problem. When accounting for both silent and fail-stop errors (with notation T SF V ), we apply the same method as in the proof of Theorem 4.1. Specifically, if a fail-stop error strikes between two verifications, we directly perform a recovery; otherwise we check for silent errors:

T SF V (i, j, l c , s) = p F i,j (s) T losti,j (s) + R lc + T ime V (l c + 1, i -1, s) + T SF V (i, j, l c , s) +(1 -p F i,j (s)) T i,j (s) + V j (s) + p S i,j (s) R lc + T ime V (l c + 1, i -1, s) + T SF V (i, j, l c , s) .
When plugging p F i,j , p S i,j and T losti,j into the above equation, we get T SF V (i, j, l c , s) = e λ S (s)Ti,j (s) e λ F (s)Ti,j (s) -1 λ F (s) + V j (s)

+ (e (λ F (s)+λ S (s))Ti,j (s) -1) (R lc + T ime V (l c + 1, i -1, s)) .

Note that T V (i, j, l c , s) depends on the value of T ime V (l c + 1, i -1, s), except when l c + 1 = i, in which case we initialize T ime V (i, i -1, s) = 0. Hence, in the dynamic program, T ime V (i, j, s) can be expressed as a function of T ime V (i, l, s) for all

l = i -1, • • • , j -1.
Finally, the complexity is dominated by the computation of the second dynamic programming table for T ime V (i, j, s), which contains O(n 2 ) entries and each entry depends on at most n other entries that are already computed. Hence, the overall complexity of the algorithm is O(n 3 ), and this concludes the proof. Now, for the sake of comparing with a divisible load application, we assume that the verification pattern between two consecutive checkpoints is also periodic. The following result extends Proposition 4.2 by showing the optimal verification period. PROPOSITION 4.6. For a divisible load application subject to both fail-stop and silent errors, a first-order approximation of the optimal verification period to minimize the expected execution time is

T time V CV (s) = 2(V (s) + C/ k * ) k * λ F (s) + ( k * + 1)λ S (s)
.

Here, k * denotes the optimal number of verifications between two consecutive checkpoints and it is equal to either max(1, k * ) or k * , where k * ∈ (0, c a ) is the unique solution to the following equation:

2d ak * + b + c k * = c (k * ) 2 -a , ( 7
)
with a = 2V (s)(λ F (s) + λ S (s)), b = 2C(λ F (s) + λ S (s)) + 2V (s)λ S (s), c = 2Cλ S (s) and d = V (s)(λ S (s)+λ F (s)) 2 .
PROOF. Let T (s) denote the verification period and k the number of verifications between two consecutive checkpoints. For convenience, we refer to a segment between two consecutive verifications a V-segment and a segment between two consecutive checkpoints a C-segment. Let p F (s) = 1 -e -λ F (s)T (s) denote the probability that a fail-stop error strikes when executing a V-segment, and let p S (s) = 1 -e -λ S (s)T (s) denote the corresponding probability for silent errors. The probability that neither type of error occurs during the execution of a V-segment is then given by q(s) = (1-P F (s))(1-P S (s)) = e -(λ F (s)+λ S (s))T (s) . The expected execution time for a C-segment can be expressed recursively by enumerating the failure possibilities for all V-segments inside it as follows:

T ime(T (s), k) = k i=1 q(s) i-1 p F (s) (i -1) • (T (s) + V (s)) + T lost (s) + R + T ime(T (s), k) +(1 -p F (s))p S (s) i • (T (s) + V (s)) + R + T ime(T (s), k) +q(s) k k • (T (s) + V (s)) + C , (8)
where T lost (s) is the expected time lost during the execution of a V-segment, knowing that a fail-stop error has struck. According to Equation (2), we have

T lost (s) = 1 λ F (s) - T (s) e λ F (s)T (s)-1 . Let h = k i=1 i • q(s) i-1 , and q(s)h = k i=1 i • q(s) i , so we have (1 -q(s))h = k i=1 q(s) i-1 -kq(s) k = 1-q(s) k 1-q(s) -kq(s) k , hence h = 1-q(s) k (1-q(s)) 2 -kq(s) k 1-q(s) . Substituting h
and T lost (s) into Equation ( 8) and simplifying it, we get

T ime(T (s), k) = 1 -q(s) k 1 -q(s) p F (s) + (1 -p F (s))p S (s) (R + T ime(T (s), k)) + (1 -q(s) k )p F (s) 1 -q(s) 1 λ F (s) - T (s) e λ F (s)T (s)-1 + q(s) k C +(T (s) + V (s)) p F (s)(q(s) -q(s) k ) + (1 -p F (s))p S (s)(1 -q(s) k ) (1 -q(s)) 2 - (k -1)p F (s)q(s) k + k(1 -p F (s))p S (s)q(s) k 1 -q(s) = (1 -q(s) k )(R + T ime(T (s), k)) + (1 -p F (s))(1 -q(s) k ) 1 -q(s) (T (s) + V (s)) + (1 -q(s) k )p F (s) 1 -q(s) 1 λ F (s) - T (s) e λ F (s)T (s)-1 + q(s) k C , which leads to T ime(T (s), k) = q(s) -k -1 1 -q(s) (1 -p F (s))(T (s) + V (s)) +p F (s) 1 λ F (s) - T (s) e λ F (s)T (s)-1 + (q(s) -k -1)R + C . (9)
Applying Taylor expansion to Equation ( 9) by approximating e λT ≈ 1 + λT

+ λ 2 T 2 2 and e kλT -1 1 -e -λT ≈ kλT 1 + kλT 2 λT 1 -λT 2 ≈ k 1 + (k + 1)λT 2 ,
we can approximate, up to the first-order term, the overhead of executing a C-segment as

T ime(T (s), k) kT (s) = kλ F (s) + (k + 1)λ S (s) 2 T (s) + V (s) + C/k T (s) +1 + (k + 1)λ S (s) + (k -1)λ F (s) 2 V (s) + (λ F (s) + λ S (s))R . ( 10
)
Differentiating Equation ( 10) with respect to T (s), we find that

T time V CV (s) = 2(V (s)+C/k) kλ F (s)+(k+1)λ S (s) minimizes the overhead. Now, substituting T time V CV (s) back into Equation (10), we get T ime(T (s), k) kT (s) = ak + b + c k + dk + e , (11)
where a = 2V (s)(λ

F (s) + λ S (s)), b = 2C(λ F (s) + λ S (s)) + 2V (s)λ S (s), c = 2Cλ S (s), d = V (s)(λ S (s)+λ F (s))
2 and e = 1 + (λ F (s) + λ S (s))R + V (s)(λ S (s)-λ F (s))

2

. Differentiating Equation ( 11) with respect to k, we find that the optimal k * satisfies Equation ( 7), which has a unique solution in (0, c a ) that can be solved numerically. As the number of verifications in a C-segment must be an integer, the optimal strategy uses either max(1, k * ) or k * , whichever leads to a smaller value for the overhead T ime(T (s),k) kT (s)

. Let us consider an example. Suppose λ F (s) = 0.001, λ S (s) = 0.002, C = R = 20 and V (s) = 1. The optimal value of k * should satisfy 0.003 0.006k * + 0.124 + 0.08 k * = 0.08 (k * ) 2 -0.006 , whose solution is k * ≈ 3.3265 < 3.6515 ≈ c a . This leads to the optimal number of verifications k * = 3 and T * (s) ≈ 37.3355 with an overhead T ime(T (s),k) kT (s) ≈ 1.4757. Figure 4 plots the overheads for different values of k and T (s) around the optimal pair of solution. Finally, we observe in the example that

k * ≈ c a = λ S (s) λ F (s) + λ S (s) × C V (s)
.

This is a general result, which always holds when λ F (s) and λ S (s) are very small: letting λ = λ F (s) + λ S (s), the left-hand side of Equation ( 7) has order O(λ 1.5 ) while the right-hand side has order O(λ). Hence, the value of k * that zeroes out the right-hand side, namely c a , is a good approximation when λ is small.

ENERGY-VC+V: MINIMIZING ENERGY

PROPOSITION 4.7. For the SINGLESPEED scenario, the ENERGY-VC+V problem can be solved by a dynamic programming algorithm in O(n 3 ) time.

PROOF. The proof is similar to that of the TIME-VC+V problem presented in Section 4.2.1. Here, we replace T ime V C (j, s) with Energy V C (j, s), which is the optimal expected energy to successfully execute the tasks T 1 to T j . Moreover, instead of T ime V (i, j, s), we use Energy V (i, j, s) and replace T SF V (i, j, l c , s) with E SF V (i, j, l c , s). The goal is to find Energy V C (n, s), and the two dynamic programs can be correspondingly formulated as:

Energy V C (j) = min 0≤i<j {Energy V C (i, s) + Energy V (i + 1, j, s)} + E C j , Energy V (i, j, s) = min i-1≤l<j
Energy V (i, l, s) + E SF V (l + 1, j, i -1, s) .

In particular, E SF V (i, j, l c , s) has similar construction as T SF V (i, j, l c , s), and it denotes the expected total energy consumption to successfully execute the tasks from T i to T j , knowing that the last checkpoint is at T lc and there might be additional single verifications between T lc+1 and T i-2 . When accounting for both fail-stop and silent errors, E SF V (i, j, l c , s) can be expressed as:

E SF V (i, j, l c , s) = p F i,j (s) E losti,j (s) + E R lc + Energy V (l c + 1, i -1, s) + E SF V (i, j, l c , s) +(1 -p F i,j (s)) E i,j (s) + E V j (s) + p S i,j (s) E R lc + Energy V (l c + 1, i -1, s) + E SF V (i, j, l c , s) ,
which simplifies to

E SF V (i, j, l c , s) = (P idle + P cpu (s)) e λ S (s)Ti,j (s) e λ F (s)Ti,j (s) -1 λ F (s) + V j (s) + e (λ F (s)+λ S (s))Ti,j (s) -1 E R lc + Energy V (l c + 1, i -1, s) .
Clearly, the complexity is the same as that of the makespan minimization algorithm (in Theorem 4.5).

PROPOSITION 4.8. For a divisible load application subject to both fail-stop and silent errors, a first-order approximation of the optimal verification period to minimize the expected energy consumption is

T energy V CV (s) = 2(V (s) + C e (s)/ k * ) k * λ F (s) + ( k * + 1)λ S (s)
,

where C e (s) = C(P idle +Pio) P idle +Pcpu(s) . Here, k * denotes the optimal number of verifications between two consecutive checkpoints and it is equal to either max(1, k * ) or k * , where k * ∈ (0, c a ) is the unique solution to the following equation:

2d ak * + b + c k * = c (k * ) 2 -a , with a = 2V (s)(λ F (s) + λ S (s)), b = 2C e (s)(λ F (s) + λ S (s)) + 2V (s)λ S (s), c = 2C e (s)λ S (s) and d = V (s)(λ S (s)+λ F (s)) 2 .
PROOF. The proof is similar to that of Proposition 4.6. Let T (s) denote the verification period and k the number of verifications between two consecutive checkpoints. We can rewrite Equation (8) to compute the expected energy consumption instead of the expected execution time for a C-segment by replacing C with C e (s) = C(P idle +Pio) P idle +Pcpu(s) and replacing R with R e (s) = R(P idle +Pio) P idle +Pcpu(s) . Then accounting for P idle and P cpu (s), we can get the following expression:

Energy(T (s), k) = (P idle + P cpu (s)) F (T (s), k) , (12)
where F (T (s), k) can be expressed as

F (T (s), k) = k i=1 q(s) i-1 p F (s) (i -1) • (T (s) + V (s)) + T lost (s) + R e (s) + F (T (s), k) +(1 -p F (s))p S (s) i • (T (s) + V (s)) + R e (s) + F (T (s), k) +q(s) k k • (T (s) + V (s)) + C e (s)
.

Let E(s) = (P idle + P cpu (s)) T (s) denotes the error-free, checkpoint-free and verification-free energy consumption during a verification period T (s). Again, we are interested in the value of T (s) that minimizes the overhead

Energy(T (s), k) kE(s) = F (T (s), k) kT (s) .
Using the same approach as in Proposition 4.6, we can get the following first-order approximation to the overhead:

F (T (s), k) kT (s) = kλ F (s) + (k + 1)λ S (s) 2 T (s) + V (s) + C e (s)/k T (s) +1 + (k + 1)λ S (s) + (k -1)λ F (s) 2 V (s) + (λ F (s) + λ S (s))R e (s) . ( 13
)
Note that Equation ( 13) is very similar to Equation (10). Hence, by differentiating Equation ( 13) with respect to T (s) and k, we can get the optimal verification period T energy V CV (s) and the optimal number k * as claimed in the proposition. The results are analogous to what we have in Proposition 4.6.

REEXECSPEED SCENARIO

In the REEXECSPEED scenario, we are given two CPU speeds s and σ, where s is the regular speed and σ is the adjusted speed. The regular speed s is used for the first execution of the tasks, while σ is used to speed up or to slow down any potential reexecution in order to improve makespan or energy. We always account for both silent and fail-stop errors.

In this scenario, and for both VC-ONLY and VC+V approaches, we need to derive two independent expressions to compute the expected execution time (or energy consumption). The first expression is for the first execution of the tasks with the first speed until the first error is encountered. Once the first error strikes, we recover from the last checkpoint and start re-executing the tasks with the second speed until we reach the next checkpoint. This latter expression for either the time or energy is essentially the same as that in the SINGLESPEED scenario, but with speed σ.

VC-ONLY: Using verified checkpoints only

In this approach, we aim at finding the best positions of verified checkpoints in order to minimize the makespan (TIME-VC-ONLY) or the total energy consumption (ENERGY-VC-ONLY). PROOF. The proof extends that of Theorem 4.1 in Section 4.1.1. To account for the two speeds, we replace T ime C (j, s) with T ime Cre (j, s, σ), which denotes the optimal expected time to successfully execute the tasks T 1 to T j , where T j has a verified checkpoint. Similarly, we replace T C (i, j, s) with T Cre (i, j, s, σ) as the expected time to successfully execute the tasks T i to T j , where both T i-1 and T j are verified and checkpointed. The goal is to find T ime Cre (n, s, σ), and the dynamic program is formulated as:

T ime Cre (j, s, σ) = min 0≤i<j {T ime Cre (i, s, σ) + T Cre (i + 1, j, s, σ)} + C j .
Note that the checkpointing cost after T j is included in T ime Cre (j, s, σ) but not in T Cre (i, j, s, σ). We initialize the dynamic program with T ime Cre (0, s, σ) = 0.

To compute T Cre (i, j, s, σ) for each (i, j) pair with i ≤ j, we need to distinguish the first execution (before the first error) and all the potential re-executions (after at least one error). Let T SF C f irst (i, j, s) denote the expected time to execute the tasks T i to T j for the very first time, before the first error is encountered, and let T SF C (i, j, σ) denote the expected time to successfully execute the tasks T i to T j in the re-executions but using speed σ. While T SF C (i, j, σ) can be computed in the same way as in Section 4.1.1, T SF C f irst (i, j, s) is computed by considering two possible scenarios: either a fail-stop error has occurred during the execution from T i to T j , and we lose T losti,j (s) time as given in Equation ( 2), or there was no fail-stop error and we check whether a silent error has occurred. Note that in both cases we do not account for the re-executions, as they are handled by T SF C separately (with the second speed). Therefore,

T SF C f irst (i, j, s) = (1 -p F i,j (s))(T i,j (s) + V j (s)) + p F i,j (s) 1 λ F (s) - T i,j (s) e λ F (s)Ti,j (s) -1 .
Let p Err i,j (s) denote the probability that at least one error is detected in the first execution of the tasks from T i to T j at speed s. Note that we account for both silent and fail-stop errors, and we can only detect silent errors if no fail-stop error has occurred, thus p Err i,j (s) = p F i,j (s) + (1 -p F i,j (s))p S i,j (s). If no error strikes during the first execution, i.e., p Err i,j (s) = 0, then the time to execute from T i to T j is exactly T SF C f irst (i, j, s), which means that all the tasks have been executed successfully with the first speed. If at least one error occurs with probability p Err i,j (s) > 0, then T SF C f irst (i, j, s) is the time lost trying to execute the tasks with the first speed. In this case, we need to recover from the last checkpoint and use T SF C (i, j, σ) to re-execute all the tasks from T i to T j with the second speed until we pass the next checkpoint. Therefore,

T Cre (i, j, s, σ) = T SF C f irst (i, j, s) + p Err i,j (s) R i-1 + T SF C (i, j, σ) . ( 14
)
Despite the two steps needed to compute T Cre (i, j, s, σ), the complexity remains the same as in the SINGLESPEED scenario (Theorem 4.1). This concludes the proof.

ENERGY-VC-ONLY: MINIMIZING ENERGY

PROPOSITION 5.2. For the REEXECSPEED scenario, the ENERGY-VC-ONLY problem can be solved by a dynamic programming algorithm in O(n 2 ) time.

PROOF. The proof is similar to that of the TIME-VC-ONLY problem presented in Section 5.1.1. We replace T ime Cre (j, s, σ) with Energy Cre (j, s, σ) while accounting for both speeds. The goal is to find Energy Cre (n, s, σ), and the dynamic program is formulated as:

Energy Cre (j, s, σ) = min 0≤i<j {Energy Cre (i, s, σ) + E Cre (i + 1, j, s, σ)} + E C j .
Similarly to T Cre (i, j, s, σ), we introduce E Cre (i, j, s, σ), which is also composed of two parts: one for the first execution with the first speed s and the other for all potential re-executions with the second speed σ. Again, the first part only includes the energy spent on executing the tasks until the first error is encountered and it does not account for any recovery cost. As a result, the associated energy cost is only contributed by the CPU and is directly proportional to the time T SF C f irst (i, j, s) spent on executing the tasks in the first execution. We can express E Cre (i, j, s, σ) as:

E Cre (i, j, s, σ) = (P idle + P cpu (s)) T SF C f irst (i, j, s) + p Err i,j (s) E R i-1 + E SF C (i, j, σ) , ( 15
)
where E SF C (i, j, σ) can be computed in the same way as in Section 4.1.2. Clearly, the complexity is the same as that of the makespan minimization algorithm (in Theorem 5.1).

VC+V: Using verified checkpoints and single verifications

In the VC+V approach, we can place single verifications between two verified checkpoints to achieve early detection of silent errors. As two speeds are used in this scenario, we will place two sets of single verifications. The first set is used during the first execution of the tasks until the first error is encountered, in which case we recover from the last checkpoint and start re-executing the tasks using the second set of verifications with the second speed. The problem is to find the best positions for the verified checkpoints as well as the best positions for the two sets of single verifications in order to minimize the total execution time (TIME-VC+V) or the total energy consumption (ENERGY-VC+V).

Because two sets of single verifications need to be placed, we formulate two independent dynamic programs to determine their respective optimal positions. The overall complexity, however, remains the same as that of the SINGLESPEED scenario.

TIME-VC+V: MINIMIZING MAKESPAN

THEOREM 5.3. For the REEXECSPEED scenario, the TIME-VC+V problem can be solved by a dynamic programming algorithm in O(n 3 ) time.

PROOF. The VC+V approach follows the same reasoning as the VC-ONLY approach (see Section 5.1.1). Here, we replace T ime Cre (j, s, σ) with T ime V Cre (j, s, σ), and replace T Cre (i, j, s, σ) with T V Cre (i, j, s, σ). Note that both expressions follow the new reexecution model and account for both sets of single verifications. The goal is to find T ime V Cre (n, s, σ), and the dynamic program is formulated as:

T ime V Cre (j, s, σ) = min 0≤i<j {T ime V Cre (i, s, σ) + T V Cre (i + 1, j, s, σ)} + C j .
Note that the checkpointing cost after T j is included in T ime V Cre (j, s, σ) but not in T V Cre (i, j, s, σ). We initialize the dynamic program with T ime V Cre (0, s, σ) = 0.

To compute T V Cre (i, j, s, σ), where both T i-1 and T j are verified and checkpointed, we again distinguish two parts: the optimal expected time T ime V f irst (i, j, s) to execute the tasks T i to T j in the first execution using the first set of single verifications with speed s, and the optimal expected time T ime V (i, j, σ) to successfully execute the tasks T i to T j in all subsequent re-executions using the second set of single verifications with speed σ. Similarly to the proof of the TIME-VC-ONLY problem in Section 5.1.1, T V Cre (i, j, s, σ) always includes the cost T ime V f irst (i, j, s) regardless of whether a error strikes during the first execution. Let p Err i,j (s) denote the probability that at least one error is detected in the first execution, and it is again given by p Err i,j (s) = p F i,j (s) + (1 -p F i,j (s))p S i,j (s). If an error indeed strikes during the first execution, then we need to recover from the last checkpoint and use T ime V (i, j, σ) to re-execute all the tasks from T i to T j with the second speed until we pass the next checkpoint. Therefore,

T V Cre (i, j, s, σ) = T ime V f irst (i, j, s) + p Err i,j (s) (R i-1 + T ime V (i, j, σ)) . (16)
Here, T ime V (i, j, σ) follows the same dynamic programming formulation as in Section 4.2.1 but using speed σ. T ime V f irst (i, j, s), on the other hand, denotes the optimal expected time to execute the tasks T i to T j at speed s until the first error strikes. Hence, it should not include the recovery cost nor the re-executions. The following describes a dynamic programming formulation to compute T ime V f irst (i, j, s):

T ime V f irst (i, j, s) = min i-1≤l<j T ime V f irst (i, l, s) + (1 -p Err i,l (s))(T SF V f irst (l + 1, j, s)) ,
where p Err i,l (s) = p F i,l (s) + (1 -p F i,l (s))p S i,l (s) is the probability that at least one error is detected when executing the tasks T i to T l , and T SF V f irst (i, j, s) denotes the expected time to execute the tasks T i to T j with both T i-1 and T j verified. In this formulation, we include the second term only when no error has happened during the first term, otherwise we have to recover and re-execute the tasks with the second speed, which is handled by T ime V (i, j, σ).

To compute T SF V f irst (i, j, s), we consider two possible scenarios: either a fail-stop error has occurred and we lose T losti,j (s) time, or there was no fail-stop error and we have to check whether a silent error has occurred. Recall that we do not account for the re-executions. Therefore,

T SF V f irst (i, j, s) = (1 -p F i,j (s)) (T i,j (s) + V j (s)) + p F i,j (s) 1 λ F (s) - T i,j (s) e λ F (s)Ti,j (s) -1 .
Finally, we initialize this dynamic program with

T ime V f irst (i, i -1, s) = 0 for all i = 1, • • • , n.
The complexity is dominated by the computation of T ime V (i, j, s) and T ime V f irst (i, j, s), both of which take O(n 3 ) time. Therefore, the overall complexity remains the same as in the SINGLESPEED scenario (Theorem 4.5).

ENERGY-VC+V: MINIMIZING ENERGY

PROPOSITION 5.4. For the REEXECSPEED scenario, the ENERGY-VC+V problem can be solved by a dynamic programming algorithm in O(n 3 ) time.

PROOF. The proof is similar to that of the TIME-VC+V problem in Section 5.2.1. We replace T ime V Cre (j, s, σ) with Energy V Cre (j, s, σ), and replace T V Cre (i, j, s, σ) with E V Cre (i, j, s, σ). Note that both expressions account for the two sets of single verifications with the corresponding speed for each set, as it was done for the makespan problem. The goal is to find Energy V Cre (n, s, σ), and the dynamic program is formulated as:

Energy V Cre (j, s, σ) = min 0≤i<j {Energy V Cre (i, s, σ) + E V Cre (i + 1, j, s, σ)} + E C j .
As with the minimization of the makespan, we compute E V Cre (i, j, s, σ) by breaking it into two parts: the optimal expected energy Energy V f irst (i, j, s) to execute the tasks in the first execution and the optimal expected energy Energy V (i, j, σ) to successfully execute the tasks in the re-executions. Hence, analogous to Equation ( 16), E V Cre (i, j, s, σ) can be expressed as

E V Cre (i, j, s, σ) = Energy V f irst (i, j, s) + p Err i,j (s) E R i-1 + Energy V (i, j, σ) . (17)
Since the first execution does not include for any recovery cost, the optimal energy Energy V f irst (i, j, s) spent during this time comes only from CPU and it is directly proportional to the optimal time T ime V f irst (i, j, s). Hence, we can express:

Energy V f irst (i, j, s) = (P idle + P cpu (s))T ime V f irst (i, j, s) .
For the re-executions, the optimal energy Energy V (i, j, σ) can be obtained by following the same dynamic programming formulation as in Section 4.2.2 but using speed σ.

Clearly, the complexity is the same as that of the makespan minimization algorithm (in Theorem 5.3).

MULTISPEED SCENARIO

In this section, we investigate the most flexible scenario, MULTISPEED, which is built upon the REEXECSPEED scenario, to get even more control over the execution time and the energy consumption, but at the cost of a higher complexity. Instead of having two fixed speeds, we are given a set

S = {s 1 , s 2 , • • • , s K } of K discrete speeds.
We call a sequence of tasks between two checkpoints a segment of the chain, and we allow each segment to use one speed for the first execution, and a second speed for all potential re-executions, where both speeds belong to S. The two speeds can well be different for different segments.

VC-ONLY: Using verified checkpoints only

In this approach, we aim at finding the best positions for the checkpoints, as well as the best speed pair for each segment, in order to minimize the expected makespan (TIME-VC-ONLY) or the total energy consumption (ENERGY-VC-ONLY).

6.1.1. TIME-VC-ONLY: MINIMIZING MAKESPAN THEOREM 6.1. For the MULTISPEED scenario, the TIME-VC-ONLY problem can be solved by a dynamic programming algorithm in O(n 2 K 2 ) time.

PROOF. The proof is built upon that of Theorem 5.1 in Section 5.1.1. Here, we use T ime C mul (j) to denote the optimal expected time to successfully execute tasks T 1 to T j , where T j has a verified checkpoint and there are possibly other verified checkpoints in between. Also, we use T C mul (i, j) to denote the optimal expected time to successfully execute the tasks T i to T j , where both T i-1 and T j are verified and checkpointed. In both expressions, the two execution speeds for each segment can be arbitrarily chosen from the discrete set S. The goal is to find T ime C mul (n), and the dynamic program can be formulated as:

T ime C mul (j) = min 0≤i<j {T ime C mul (i) + T C mul (i + 1, j)} + C j ,
which is initialized with T ime C mul (0) = 0. Recall that T Cre (i, j, s, σ) from the REEXEC-SPEED scenario (see Equation ( 14)) already accounts for two speeds that are fixed. We can use it to compute T C mul (i, j) by trying all possible speed pairs:

T C mul (i, j) = min s,σ∈S T Cre (i, j, s, σ) .
The complexity is now dominated by the computation of T C mul (i, j) for all (i, j) pairs with i ≤ j, and it takes O(n 2 K 2 ) time. After T C mul (i, j) is computed, the dynamic programming table can then be filled in O(n 2 ) time.

6.1.2. ENERGY-VC-ONLY: MINIMIZING ENERGY PROPOSITION 6.2. For the MULTISPEED scenario, the ENERGY-VC-ONLY problem can be solved by a dynamic programming algorithm in O(n 2 K 2 ) time.

PROOF. The proof is similar to that of the TIME-VC-ONLY problem in Section 6.1.1. We replace T ime C mul (j) with Energy C mul (j) and replace T C mul (i, j) with E C mul (i, j). The goal is to find Energy C mul (n) and the dynamic program is formulated as:

Energy C mul (j) = min 0≤i<j {Energy C mul (i) + E C mul (i + 1, j)} + E C j .
Similarly, E C mul (i, j) can be computed from E Cre (i, j, s, σ) (see Equation ( 15)) by trying all possible speed pairs :

E C mul (i, j) = min s,σ∈S E Cre (i, j, s, σ) .
Clearly, the complexity is the same as that of the makespan minimization algorithm (in Theorem 6.1).

VC+V: Using verified checkpoints and single verifications

In this approach, we aim at finding the best positions for the checkpoints and verifications, as well as the best speed pair for each segment, in order to minimize the expected makespan (TIME-VC-ONLY) or the total energy consumption (ENERGY-VC-ONLY).

6.2.1. TIME-VC+V: MINIMIZING MAKESPAN THEOREM 6.3. For the MULTISPEED scenario, the TIME-VC+V problem can be solved by a dynamic programming algorithm in O(n 3 K 2 ) time.

PROOF. The proof is similar to that of the TIME-VC-ONLY problem in Theorem 6.1. Here, we replace T ime C mul (j) with T ime V C mul (j) and replace T C mul (i, j) with T V C mul (i, j). Again, the two expressions denote the optimal execution times with the best speed pair chosen from S for each segment. The goal is to find T ime V C mul (n), and the dynamic program is formulated as:

T ime V C mul (j) = min 0≤i<j {T ime V C mul (i) + T V C mul (i + 1, j)} + C j ,
which is initialized with T ime V C mul (0) = 0. We can compute T V C mul (i, j) from T V Cre (i, j, s, σ) (see Equation ( 16)) by trying all possible speed pairs:

T V C mul (i, j) = min s,σ∈S T V Cre (i, j, s, σ) .
The complexity is still dominated by the computation of T V C mul (i, j), which amounts to computing T V Cre (i, j, s, σ) for all (i, j) pairs and for K 2 possible pairs of speeds (see Theorem 5.3). Therefore, the overall complexity is O(n 3 K 2 ).

6.2.2. ENERGY-VC+V: MINIMIZING ENERGY PROPOSITION 6.4. For the MULTISPEED scenario, the ENERGY-VC+V problem can be solved by a dynamic programming algorithm in O(n 3 K 2 ) time.

PROOF. The proof follows that of the TIME-VC+V problem in Section 6.2.1. We replace T ime V C mul (j) with Energy V C mul (j) and replace T V C mul (i, j) with E V C mul (i, j). The goal is to find Energy V C mul (n), and the dynamic program is formulated as:

Energy V C mul (j) = min 0≤i<j {Energy V C mul (i) + E V C mul (i + 1, j)} + E C j ,
where E V C mul (i, j) is computed from E V Cre (i, j, s, σ) (see Equation ( 17)) by trying all possible speed pairs:

E V C mul (i, j) = min s,σ∈S E V Cre (i, j, s, σ) .
Clearly, the complexity is the same as that of the makespan minimization algorithm (in Theorem 6.3).

EXPERIMENTS

We conduct simulations to evaluate the performance of the dynamic programming algorithms under different execution scenarios and parameter settings. We instantiate the model parameters with realistic values taken from the literature, and we point out that the code for all algorithms and simulations is publicly available at http://graal.ens-lyon.fr/ ∼ yrobert/failstop-silent, so that interested readers can build relevant scenarios of their choice.

Simulation settings

We generate linear chains with different number n of tasks while keeping the total computational cost at W = 5 × 10 4 seconds ≈ 14 hours. The total amount of computation is distributed among the tasks in three different patterns: (1) Uniform, all tasks share the same cost W n , as in matrix multiplication or in some iterative stencil kernels; (2) Decrease, task T i has cost α•(n+1-i) 2 , where α ≈ 3W n 3 . This quadratically decreasing function resembles some dense matrix solvers, e.g., by using LU or QR factorization.

(3) HighLow, a set of identical tasks with large cost is followed by tasks with small cost. This distribution is created to distinguish the performance of different execution scenarios. In the default setting, we assume that 10% of the tasks are large and they contain 60% of the total computational cost. We will also vary these parameters to evaluate their impacts on the performance.

We adopt the set of speeds from the Intel Xscale processor. Following [START_REF] Babaii Rizvandi | Multiple Frequency Selection in DVFS-Enabled Processors to Minimize Energy Consumption[END_REF], the normalized speeds are {0.15, 0.4, 0.6, 0.8, 1} and the fitted power function is given by P (s) = 1550s 3 + 60. From the discussion in Section 2.3, we assume the following model for the average error rate of fail-stop errors:

λ F (s) = λ F ref • 10 d•|s ref -s| smax-s min , (18)
where s ref ∈ [s min , s max ] denotes the reference speed with the lowest error rate λ F ref among all possible speeds in the range. The above equation allows us to account for higher fail-stop error rates when the CPU speed is either too low or too high. In the simulations, the reference speed is set to be s ref = 0.6 with an error rate of λ F ref = 10 -5 for fail-stop errors, and the sensitivity parameter is set to be d = 3. These parameters represent realistic settings reported in the literature [START_REF] Assayad | Tradeoff exploration between reliability, power consumption, and execution time for embedded systems[END_REF][START_REF] Aupy | Energy-aware scheduling under reliability and makespan constraints[END_REF][START_REF] Zhao | Reliability-Aware Dynamic Voltage Scaling for Energy-Constrained Real-Time Embedded Systems[END_REF], and they correspond to 0.83 ∼ 129 errors over the entire chain of computation depending on the processing speed chosen.

For silent errors, we assume that its error rate is related to that of the fail-stop errors as λ S (s) = η•λ F (s), where η > 0 is the relative parameter. To achieve realistic scenarios, we try to vary η to assess the impact of both error sources on the performance. However, we point out that our approach is completely independent of the evolution of the error rates as a function of the speed. In a practical setting, we are given a set of discrete speeds and two error rates for each speed, one for fail-stop errors and one for silent errors. This is enough to instantiate our model.

In addition, we define cr to be the ratio between the checkpointing/recovery cost and the computational cost for the tasks, and define vr to be the ratio between the verification cost and the computational cost. By default, we execute the tasks using the reference speed s ref , and we set η = 1, cr = 1 and vr = 0.01. This setting corresponds to the case where fail-stop and silent errors have similar probabilities to strike the system. Moreover, the tasks have costly checkpoints (same order of magnitude as the computational costs) and lightweight verifications (average cost 1% of computational costs); examples of such tasks are data-oriented kernels processing large files and checksumming for verification. We will also vary these parameters to study their impacts.

Results

7.

2.1. SINGLESPEED scenario for makespan. The first set of experiments is devoted to the evaluation of the time-optimal algorithms in the SINGLESPEED scenario.

Impact of number of tasks and cost distribution. Figure 5(a) shows the expected makespan (normalized by the error-free execution time at the reference speed, i.e., W s ref ) with different number n of tasks and different cost distributions. The results show that having more tasks reduces the expected makespan (for a fixed total computation), since it enables the algorithms to place more checkpoints and verifications, as can be seen in Figure 5(b). The distribution that renders a larger variation in the costs of the tasks create more difficulty in the placement of checkpoints/verfications, thus resulting in worse makespan. Figure 5(c) shows, for n = 100 tasks, that the checkpoints and verifications are placed evenly within the task chain for the Uniform distribution, while for Decrease and HighLow distributions, they are placed more densely at the beginning, where large tasks need to be checkpointed and/or verified for better resilience. The figure also compares the performance of the TIME-VC-ONLY algorithm with that of TIME-VC+V. The latter algorithm, being more flexible, naturally leads to improved makespan under all cost distributions. Because of the additionally placed verifications, it also reduces the number of checkpoints in the optimal solution.

In the rest of this section, we will mainly focus on the evaluation of the TIME-VC+V algorithm.

Impact of error mode and relative ratio. Figure 6(a) compares the performance of the TIME-VC+V algorithm under different error modes, namely, fail-stop (F) only, silent (S) only, and fail-stop plus silent with different values of η. As silent errors are harder to detect and hence to deal with, the S-only case leads to larger makespan than the F-only case. In the presence of both types of errors, the makespan becomes worse with larger η, i.e., with increased rate for silent errors, despite the algorithm's effort to place more checkpoints and more verifications as shown in Figure 6(b). Similar results (not shown) are also observed for the other cost distributions.

In the subsequent experiments, we will concentrate on n = 100 tasks in the presence of both fail-stop and silent errors with η = 1. Impact of checkpointing and verification ratios. Figure 7(a) presents the impact of checkpointing/recovery ratio (cr) and verification ratio (vr) on the performance of the TIME-VC+V algorithm under different CPU speeds. For a given speed, small cr (or vr) enables the algorithm to place more checkpoints (or verifications), which leads to better makespan. Moreover, the performance degrades significantly as the CPU speed is set below the reference speed s ref for the error rate increases exponentially. A higher CPU speed also increases the error rate, but it improves the makespan, at least for small cr, by executing the tasks faster with more checkpoints. Finally, if checkpointing cost is on par with verification cost (e.g., cr = 0.1), reducing the verification cost can additionally increase the number of checkpoints (e.g., at s = 0.6), since each checkpoint also has a verification cost associated with it. For high checkpointing cost, however, reducing the verification cost no longer influences the algorithm's checkpointing decisions. Comparison with divisible load application. Figure 8(a) compares the makespan of the TIME-VC+V algorithm with that of the periodic checkpointing and verification algorithm for a divisible load application. Figure 8(b) also shows the number of checkpoints and verifications placed for the two cases. Note that, in the divisible load application, the total computational cost, the checkpointing cost and the verification cost are set to be the same as the corresponding costs of a discrete task under the Uniform distribution. We see that the makespan for uniform tasks is almost identical to that of the divisible load under all CPU speeds, while the performance degrades significantly for the other two distributions with larger variations in the costs of the tasks. Similar results (not shown) are also observed when comparing the TIME-VC-ONLY algorithm with the periodic checkpointing algorithm for divisible load. Moreover, because divisible load does not impose restrictions in the checkpointing and verification positions, there tends to be more verifications (or checkpoints in the case of periodic checkpointing algorithm) than for discrete tasks, especially when the CPU speed is further away from the reference speed and hence the error rate is high.

In view of these results, we could imagine the following greedy algorithm as an alternative to the TIME-VC-ONLY and TIME-VC+V algorithms for a linear chain of tasks with Uniform cost: position the next checkpoint or verification as soon as the time spent on computing since the last checkpoint or verification exceeds the optimal periods given by Propositions 4.2 and 4.6. The results here suggest that this lineartime algorithm (with complexity O(n)) would give a good approximation to the optimal solution (returned by the TIME-VC-ONLY algorithm with complexity O(n 2 ) or the TIME-VC+V algorithm with complexity O(n 3 )).

Performance with independent checkpointing cost. We now consider the case where the checkpointing costs are independent of the tasks' computational costs. To assess the impact, we generate different patterns by varying the checkpointing costs linearly within the task chain while keeping the sum a constant. Specifically, we use the following function to generate the checkpointing cost

C i = C 1 + δ n (i -n 2 )
for each task T i , where 1 ≤ i ≤ n and C = W n denotes the average checkpointing cost. Here, δ represents the gradient of the linear function: δ = 0 means all tasks have the same checkpointing cost, δ > 0 increases the checkpointing cost as more tasks are processed, and δ < 0 decreases the checkpointing cost.

Figure 9 shows the performance of the TIME-VC+V algorithm for different values of δ under the reference speed s ref = 0.6. When δ increases, the makespan for tasks with Uniform computational cost is barely affected, while significant improvements are observed for the other two distributions. The reason is because the algorithm for the Decrease and the HighLow distributions places more checkpoints at the beginning of the task chain, where the large tasks are located. Therefore, reducing the checkpointing costs for these tasks decreases the execution overhead and hence the overall makespan.

7.2.2. SINGLESPEED scenario for energy. This set of experiments evaluates the energyoptimal algorithms in the SINGLESPEED scenario. The default power parameters are set to be P idle = 60 and P cpu (s) = 1550s 3 according to [START_REF] Babaii Rizvandi | Multiple Frequency Selection in DVFS-Enabled Processors to Minimize Energy Consumption[END_REF]]. The dynamic power consumption P io due to I/O is equal to the dynamic power of the CPU at the lowest discrete speed 0.15. We will vary these parameters to study their impacts.

Impact of number of tasks and cost distribution. degrades at speed s = 1 under the default setting (see Figure 8(a)), this diminishes its makespan advantage at the highest discrete speed. Figure 12 indicates that the TIME-VC+V algorithm running at speed s = 0.8 offers a good energy-makespan tradeoff: compared to the ENERGY-VC+V algorithm, it provides more than 25% improvement in makespan with about 10% degradation in energy under the default settings.

Impact of P idle and P io . Figures 13(a) and 13(b) show the relative performance of TIME-VC+V and ENERGY-VC+V by varying P idle and P io separately according to the dynamic power function 1550s 3 , while keeping the other one at the smallest CPU power, i.e., 1550 • 0.15 3 . The CPU speed is fixed at s = 0.6. Figure 13(c) further shows the number of checkpoints placed by the ENERGY-VC+V algorithm at different P idle and P io values. (The TIME-VC+V algorithm is not affected by these two parameters and always places 11 checkpoints in this experiment.) First, setting the smallest value for both parameters creates a big gap between the CPU and I/O power consumptions. This leads to a large number of checkpoints placed by the ENERGY-VC+V algorithm. Increasing P idle closes this gap and hence reduces the number of checkpoints, which leads to the performance convergence of the two algorithms. While increasing P io has the same effect, a larger value than P cpu = 1550 • 0.6 3 further reduces the number of checkpoints below 11, since checkpointing is now less energy-efficient. This again gives the ENERGY-VC+V algorithm advantage in terms of energy. 7.2.3. REEXECSPEED and MULTISPEED scenarios. This set of experiments evaluates the REEXECSPEED and MULTISPEED scenarios for makespan and energy. To distinguish them from the SINGLESPEED scenario, we consider the HighLow distribution, which yields a larger variance among the computational costs of the tasks. In the simulation, we again focus on the VC+V algorithms for n = 100 tasks, and vary the cost ratio γ, 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 tion objectives, by up to 100% in makespan and even more in energy consumption. Increasing the cost ratio creates more computationally demanding tasks, which need to be executed at speed 0.6 for both makespan and energy efficiency as it incurs fewer errors. This closes the performance gap of the two algorithms as well as the number of checkpoints placed by them. For both algorithms, the number of checkpoints reduces with the cost ratio, because the total computational cost in the small tasks shrinks, thus fewer checkpoints are needed among them.

flexible VC+V and MULTISPEED scenario provide the best overall performance, which in practice translates to shorter makespan or lower energy consumption.

For tasks with similar computational cost as in the Uniform distribution, the SIN-GLESPEED algorithm, or the greedy approximation in the context of divisible load application, could provide comparable solutions with lower computational complexity. The REEXECSPEED algorithms provide marginal benefit compared to SINGLESPEED, but clear performance gains are observed from the MULTISPEED algorithms, especially for tasks with very different costs. The results also show that the optimal solutions are often achieved by processing around the reference speed that yields the least number of failures.

Finally, for the complexity of computing the optimal solutions, we point out that application workflows rarely exceed a few tens of tasks. In such practical contexts, even the most advanced algorithms have a very fast execution time, of a few seconds. To give a number, VC+V in the MULTISPEED scenario requires less than one second for 100 tasks, using a 3.7Ghz single-core. Hence all our algorithms can be applied to determine the optimal checkpointing and verification locations with almost negligible cost.

CONCLUSION

In this paper, we have presented a general-purpose solution that combines checkpointing and verification mechanisms to cope with both fail-stop errors and silent data corruptions. By using dynamic programming, we have devised polynomial-time algorithms that decide the optimal checkpointing and verification positions for a linear chain of tasks. The algorithms can be applied to several execution scenarios to minimize the expected execution time (makespan) or energy consumption. Moveover, we have extended the classical bound of Young/Daly for a divisible load application to handle both fail-stop and silent errors, and to include both checkpoints and verifications. The results are supported by a set of extensive simulations, which demonstrate the quality and tradeoff of our optimal algorithms under a wide range of parameter settings. One future direction is to extend our study from linear chains to other application workflows, such as tree graphs, fork-join graphs, series-parallel graphs, or even general directed acyclic graphs (DAGs).

  4.1.1. TIME-VC-ONLY: MINIMIZING MAKESPAN THEOREM 4.1. For the SINGLESPEED scenario, the TIME-VC-ONLY problem can be solved by a dynamic programming algorithm in O(n 2 ) time.

Fig. 1 .

 1 Fig. 1. Illustration of the dynamic programming formulation for T ime C (j, s).

  s) minimizes the overhead, which extends Young/Daly's formula to include ACM Transactions on Parallel Computing, Vol. 1, No. 1, Article 1, Publication date: January 2014.

  4.1.2. ENERGY-VC-ONLY: MINIMIZING ENERGY PROPOSITION 4.3. For the SINGLESPEED scenario, the ENERGY-VC-ONLY problem can be solved by a dynamic programming algorithm in O(n 2 ) time.

Fig. 2 .

 2 Fig. 2. Illustration of the dynamic programming formulation for T ime V C (j, s).

Fig. 4 .

 4 Fig.4. The overheads for different values of (k, T (s)) around the optimal pair(3, 37.3355) for the setting with λ F (s) = 0.001, λ S (s) = 0.002, C = R = 20 and V (s) = 1.

  5.1.1. TIME-VC-ONLY: MINIMIZING MAKESPAN THEOREM 5.1. For the REEXECSPEED scenario, the TIME-VC-ONLY problem can be solved by a dynamic programming algorithm in O(n 2 ) time.

Fig. 5 .

 5 Fig. 5. Impact of n and cost distribution on the performance of the TIME-VC-ONLY and TIME-VC+V algorithms. In (b), the thick bars represent the number of verified checkpoints and the yellow thin bars represent the total number of verifications. In (c), the number of tasks is fixed at n = 100. The long vertical bars mark the positions of the verified checkpoints within the task chain, whereas the short vertical bars mark the positions of the additional verifications.

Fig. 6 .

 6 Fig.6. Impact of η on the performance. F denotes fail-stop error only and S denotes silent error only.

Fig. 7 .

 7 Fig. 7. Impact of cr and vr on the performance with different CPU speeds. Speed s = 0.15 yields extremely large makespan, which is omitted in the figure.

Fig. 8 .

 8 Fig. 8. Performance comparison of the TIME-VC+V algorithm and the periodic checkpointing and verification algorithm for divisible load application.

Fig. 11 .Fig. 12 .

 1112 Fig. 11. Performance comparison of the ENERGY-VC+V algorithm and the periodic checkpointing and verification algorithm for divisible load application.

Fig. 14 .Fig. 15 .

 1415 Fig. 14. Performance comparison of the TIME-VC+V algorithms in MULTISPEED, REEXECSPEED and SIN-GLESPEED scenarios for n = 100 tasks under HighLow cost distribution. In (b), the cost ratio is fixed at γ = 0.6, and the yellow part at the bottom of each bar represents the expected execution time for the large tasks.

Fig. 16 .

 16 Fig. 16. Impact of cost ratio on the relative performance of the ENERGY-VC+V and TIME-VC+V algorithms under the MULTISPEED scenario.

Table I .

 I List of main notations.

		Tasks
	{T 1 , T 2 , . . . , Tn}	Set of n tasks
	w i	Computational cost of task T i
		Speeds
	s	Regular speed
	σ	Re-execution speed
	{s 1 , s 2 , . . . , s K }	Set of K discrete computing speeds (DVFS)
		Time
	T i,j (s)	Time needed to execute tasks T i to T j at speed s
	V i (s)	Time needed to verify task T i at speed s
	C i	Time needed to checkpoint task T i
	R i	Time needed to recover from task T i
		Resilience
	λ F (s)	Fail-stop error rate for a given speed s
	λ S (s)	Silent error rate for a given speed s
	p F i,j (s)	Probability that a fail-stop error strikes between tasks T i and T j
	p S i,j (s)	Probability that a silent error strikes between tasks T i and T j
		Energy
	P idle	Static/idle power dissipated when the platform is switched on
	Pcpu(s)	Dynamic power spent by operating the CPU at speed s
	P io	Dynamic power spent by I/O transfers (checkpoints and recoveries)
	E i,j (s)	Energy needed to execute tasks T i to T j at speed s
	E V i (s) E C i E R i	Energy needed to verify task T i at speed s Energy needed to checkpoint task T i

ACM Transactions on Parallel Computing, Vol. 1, No. 1, Article 1, Publication date: January 2014.

7.2.4. Summary. We have evaluated and compared various algorithms under different execution scenarios and parameter settings. In general, the algorithms under the most ACM Transactions on Parallel Computing, Vol. 1, No. 1, Article 1, Publication date: January 2014.

the performance, while a larger variation in the tasks' costs worsens the performance. Unlike the makespan case, the performance difference between ENERGY-VC-ONLY and ENERGY-VC+V is less evident. The reason is because the checkpointing cost is much smaller in terms of energy consumption, so more checkpoints are placed (compare Figures 10(b) and 5(b)), and this reduces the number of additional verifications required and hence their benefits.

Comparison with divisible load application. Figure 11 compares the performance of the ENERGY-VC+V algorithm with that of the periodic checkpointing and verification algorithm for a divisible load application when executing n = 100 tasks. Similarly to the makespan case (see Figure 8), the energy consumed for tasks with Uniform distribution is very close to that for the divisible load, which admits more verifications and/or checkpoints due to the flexible task model. In addition, the optimal energy is achieved by setting the CPU speed below the reference, i.e, at s = 0.4. This is in contrast to the TIME-VC+V algorithm, which achieves the optimal makespan at s = 0.8, a higher speed than the reference.

Energy-makespan tradeoff. We now study the energy-makespan tradeoff exhibited by the ENERGY-VC+V and TIME-VC+V algorithms. Figure 12 compares their relative performance for makespan and energy when executing n = 100 tasks. At speed s = 0.15, the power consumed by the CPU is identical to that by I/O. This yields the same number of checkpoints placed by the two algorithms, which in turn leads to the same performance for makespan and energy. As the speed s increases, the I/O power becomes relatively cheaper, so ENERGY-VC+V tends to place more checkpoints to improve the energy at the expense of makespan. Since the makespan of TIME-VC+V which is the percentage of the large tasks' computational cost in the total computational cost.

Comparing different execution scenarios. Figure 14(a) compares the makespan of the TIME-VC+V algorithms under the three execution scenarios. For the SINGLESPEED and REEXECSPEED scenarios, only s = 0.6 and s = 0.8 are drawn, since the other speeds lead to much larger makespan. For small cost ratios, no task has a very large computational cost, so the distribution is close to Uniform. In this case, the faster speed s = 0.8 offers the best performance despite its higher error rate, as we have seen in Figure 8(a). When the cost ratio increases, tasks with larger cost start to emerge. At the high error rate of s = 0.8, these tasks will experience much more errors and re-executions, so their execution time will dominate the overall makespan. Therefore, for large cost ratios, s = 0.6 becomes the best speed due to its smaller error rate, which was also observed in Figure 8(a) under the HighLow distribution.

In the REEXECSPEED scenario, we observe that the best re-execution speed σ, regardless of the initial speed s, is also determined by the computational costs of the tasks, which are in turn decided by the cost ratio. Figure 14(b) shows, for cost ratio γ = 0.6, that setting σ = 0.6 improves the execution of the big tasks but degrades the performance of the small tasks. On the other hand, setting σ = 0.8 helps the small tasks but hurts the big tasks. These experiments suggest that, despite the ability to select a more appropriate speed for the reexecutions, the REEXECSPEED scenario presents only limited benefits compared to the best performance achievable in the SIN-GLESPEED scenario. The MULTISPEED scenario, with its flexibility to choose different speeds depending on the costs of the tasks, offers clear performance gains. The advantage is especially evident at medium cost ratio, where a good mix of large and small tasks coexist -a situation that is very hard to cope with by using fixed speed(s).

Similar results can also be observed for the ENERGY-VC+V algorithms under the three scenarios, which are shown in Figure 15. Note that, in terms of energy consumption, speed s = 0.4 is more suitable for small tasks due to its better power efficiency, while speed s = 0.6 is more suitable for big tasks due to its lower error rate. Again, the most flexible MULTISPEED scenario is able to choose between the two speeds depending on the costs of the tasks, and hence it offers the best overall performance.

Energy-makespan tradeoff under MULTISPEED scenario. Figure 16 shows the relative performance of the ENERGY-VC+V and TIME-VC+V algorithms under the MUL-TISPEED scenario. As small cost ratios favor speed s = 0.4 for energy and s = 0.8 for makespan, it distinguishes the two algorithms in terms of their respective optimiza-