Anne Benoit

Aurelien Cavelan

Florina M Ciorba

Valentin Le Fèvre

Yves Robert

Combining Checkpointing and Replication for Reliable Execution of Linear Workflows

This paper combines checkpointing and replication for the reliable execution of linear workflows. While both methods have been studied separately, their combination has not yet been investigated despite its promising potential to minimize the execution time of linear workflows in failure-prone environments. The combination raises new problems: for each task, we have to decide whether to checkpoint and/or replicate it. We provide an optimal dynamic programming algorithm of quadratic complexity to solve both problems. This dynamic programming algorithm has been validated through extensive simulations that reveal the conditions in which checkpointing only, replication only, or the combination of both techniques lead to improved performance.

I. INTRODUCTION

Several high-performance computing (HPC) applications are designed as a succession of (typically large) tightly-coupled computational kernels, or tasks, that should be executed in sequence [START_REF] Buneci | Qualitative Performance Analysis for Large-Scale Scientific Workflows[END_REF], [START_REF] Cuevas-Vicenttín | Scientific workflows and provenance: Introduction and research opportunities[END_REF], [START_REF] Kandaswamy | Fault tolerance and recovery of scientific workflows on computational grids[END_REF]. These parallel tasks are executed on the whole platform, and they exchange data at the end of their execution. 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. Such linear chains of tasks also appear in image processing applications [START_REF] Mehta | Meta-Algorithms for Scheduling a Chain of Coarse-Grained Tasks on an Array of Reconfigurable FPGAs[END_REF], and are usually called linear workflows [START_REF] Talia | Workflow Systems for Science: Concepts and Tools[END_REF].

The first objective when dealing with linear workflows is to ensure an efficient execution, which amounts to minimizing the total parallel execution time, or makespan. However, a reliable execution is also critical to performance. Indeed, large-scale platforms are increasingly subject to failures. Scale is the enemy here: even if each computing resource is very reliable, with, say, a Mean Time Between Failures (MTBF) of 10 years, meaning that each resource will experience a failure only every 10 years on average, a platform composed of one million of such resources will experience a failure every five minutes [START_REF] Hérault | Fault-Tolerance Techniques for High-Performance Computing, Computer Communications and Networks[END_REF]. Hence, fault-tolerance techniques to mitigate the impact of failures are required to ensure a correct execution of the application [START_REF] Lucas | Top ten exascale research challenges[END_REF]. The standard approach is checkpoint, rollback and recovery [START_REF] Chandy | Distributed snapshots: Determining global states of distributed systems[END_REF], [START_REF] Elnozahy | Checkpointing for peta-scale systems: a look into the future of practical rollback-recovery[END_REF]: in the context of linear workflow applications, each task can decide to take a checkpoint after it has been correctly executed. A checkpoint is simply a file including all intermediate results and associated data that is saved on a storage medium resilient to failures; it can be either the memory of another processor, a local disk or a remote disk. This file can be recovered if a successor task experiences a failure later on in the execution. If there is an error while some task is executing, the application has to roll back to the last checkpointed task (or to start again from scratch if no checkpoint was taken). Then the checkpoint is read from the storage medium (recovery phase), and execution resumes from that task onward. If the checkpoint was taken many tasks before a failure strikes, there is a lot of re-execution involved, which calls for frequent checkpoints. However, checkpointing incurs a significant overhead, and is a mere waste of resources if no failure strikes. Altogether, there is a trade-off to be found, and one may want to checkpoint only carefully selected tasks.

Another approach to address failures consists in replicating the work: we can for instance execute a task twice, in parallel, using only half of the platform for each replica, in order to maximize the chance of success. Indeed, if one of the executions succeeds without failure, we can keep going to the next task. Even though this approach has a high cost in terms of computing resources (half of the platform is wasted if no failure strikes), several authors have recently advocated the use of replication in HPC in the recent years [START_REF] Schroeder | Understanding Failures in Petascale Computers[END_REF], [START_REF] Zheng | Reliability-aware scalability models for high performance computing[END_REF], [START_REF] Engelmann | The case for modular redundancy in large-scale high performance computing systems[END_REF], [START_REF] Ferreira | Evaluating the viability of process replication reliability for exascale systems[END_REF]. Indeed, if there are too many failures, an application using only checkpointing may experience too many recoveries and reexecution delays in order to progress efficiently. Furthermore, parallel tasks are often following Amdahl's law [START_REF] Amdahl | The validity of the single processor approach to achieving large scale computing capabilities[END_REF], i.e., they include a sequential part that will take the same time, whatever the number of processors allocated to the task. Hence, using twice more processors to execute a task does not mean that the execution will be twice faster. Coupling a better failure-free efficiency with a better resilience to failures makes duplication worth investigating for linear workflows 1 .

While both checkpointing and replication have been extensively studied separately, their combination has not yet been investigated despite its promising potential to minimize the execution time in failure-prone environments, in particular in the context of linear workflows. The contributions of this work are the following:

• We provide a detailed model for the reliable execution of linear workflows, where each task can be replicated or not, and where the checkpoint cost depends both on the number of processors executing the task, and on whether the task is replicated or not; • We design an optimal dynamic programming algorithm that minimizes the makespan of a linear workflow with n tasks, with a quadratic complexity, in the presence of fail-stop errors; • We conduct extensive experiments to evaluate the impact of using both replication and checkpointing during execution, and compare them to an execution without replication; • We provide guidelines about when it is beneficial to employ checkpointing only, replication only, or to combine both techniques together. The paper is organized as follows. Section II details the model and formalizes the objective function and the optimization problem. Section III presents a preliminary result for the dynamic programming algorithm: we explain how to compute the expected time needed to execute a single task (replicated or not), assuming that its predecessor has been checkpointed. The dynamic programming algorithm is outlined in Section IV and the experimental validation is provided in Section V. Finally, related work is discussed in Section VI, and we conclude in Section VII.

II. MODEL AND OBJECTIVE

This section details the framework of this study. We start with the application and platform models, then detail checkpointing and replication, and finally state the optimization problem.

A. Application model

We target applications whose workflow represents a linear chain of parallel tasks. More precisely, we have a chain

T 1 → T 2 → • • • → T n of n parallel tasks T i , 1 ≤ i ≤ n.
Hence, T 1 must be completed before executing T 2 , and so on.

Here, each T i is a parallel task whose speedup profile obeys Amdahl's law [START_REF] Amdahl | The validity of the single processor approach to achieving large scale computing capabilities[END_REF]: the total work is w i , with a sequential fraction α i w i and the remaining fraction (1α i )w i perfectly parallel. The (failure-free) execution time of T i using q i processors is thus w i α i + 1-αi qi . Without loss of generality, we assume that processors execute the tasks at unit speed, and we speak of time units and work units interchangeably. While our study is agnostic of task granularity, it applies primarily to frameworks where tasks represent large computational entities whose execution takes, say, from a few minutes up to tens of minutes. In such frameworks, it may be worthwhile to replicate or checkpoint the task to mitigate the impact of failures.

B. Execution platform

We target a homogeneous platform with p processors P i , 1 ≤ i ≤ p. We assume that the platform is subject to fail-stop errors whose inter-arrival times follow an Exponential distribution. More precisely, let λ ind be the error rate of each individual processor P i : the probability of having a fail-stop error striking P i within T time-units is P(X ≤ T ) = 1e -λ ind T . Then, a computation on q ≤ p processors has an error rate qλ ind , and the probability of having a fail-stop error within T time-units becomes 1e -qλ ind T [START_REF] Hérault | Fault-Tolerance Techniques for High-Performance Computing, Computer Communications and Networks[END_REF].

C. Checkpointing

The output of each task T i can be checkpointed in time C i . When an error strikes, we first incur a downtime D, and then we must start the execution from the task following the last checkpoint. Hence, if T j is the last checkpointed task, the execution starts again at task T j+1 , and the recovery cost is R j+1 , which amounts to reading the checkpoint of task T j . The checkpoint cost C i and recovery cost R i clearly depend upon the checkpoint protocol and storage medium, as well as upon the number q i of enrolled processors. In this work, we adopt a quite general formula for checkpoint times and use

C i (q i ) = a i + b i q i + c i q i (1)
to model the time to save a checkpoint after T i executed with q i processors. Here, a i + bi qi represents the I/O overhead to write the task output file M i to the storage medium. For inmemory checkpointing [START_REF] Zheng | FTC-Charm++: an in-memory checkpoint-based fault tolerant runtime for Charm++ and MPI[END_REF], a i + bi qi is the communication time with latency a i ; then we have bi qi = Mi τnetqi , where τ net is the network bandwidth (each processor stores Mi qi data items). For coordinated checkpointing to stable storage, there are two cases: if the storage system's bandwidth is the I/O bottleneck, then a i = β + Mi τio and b i = 0, where β is a start-up time and τ io is the I/O bandwidth; otherwise, if the network is the I/O bottleneck, we retrieve the same formula as for in-memory checkpointing. Finally, c i q i represents the message passing overhead that grows linearly with the number of processors, in order for all processors to reach a global consistent state [START_REF] Elnozahy | Checkpointing for peta-scale systems: a look into the future of practical rollback-recovery[END_REF], [START_REF] Zheng | Reliability-aware speedup models for parallel applications with coordinated checkpointing/restart[END_REF].

For the cost of recovery, we assume a similar formula:

R i (q i ) = a i + b i q i + c i q i . (2)
If we further assume that reading and writing from/to the storage medium have same cost, we have R i+1 (q i ) = C i (q i ) for 1 ≤ i ≤ n -1, since recovering for task T i+1 amounts to reading the checkpoint from task T i .

Finally, we assume that there is a fictitious task T 0 of zero weight (w 0 = 0) that is always checkpointed, so that R 1 (q 1 ) represents the time for I/O input from the external world. Similarly, we systematically checkpoint the last task T n , in order to account for the I/O output time C n (q n ).

D. Replication

When executing a task, we envision two possibilities: either the task is not replicated, or it is replicated. Consider a task T i , and assume for simplicity that the predecessor T i-1 of T i has been checkpointed. If it is not the case, i.e., if the predecessor T i-1 of T i is not checkpointed, we have to roll back to the last checkpointed task, say T k where k < i -1, whenever a failure strikes, and re-execute the whole segment from T k+1 to T i instead of just T i .

Without replication, a single copy of T i is executed on the whole platform, hence with q i = p processors. Then we let E norep (i) denote the expected execution time of T i when accounting for failures. We attempt a first execution, which takes w i α i + 1-αi p if no failure strikes. But if some failure does strike, we must account for the time that has been lost (between the beginning of the execution and the failure), then perform a downtime D, a recovery R i (p) (since we use the whole platform for T i ), and then re-execute T i from scratch. Similarly, if we decide to checkpoint after T i , we need C i (p) time units. We explain how to compute E norep (i) in Section III.

With replication, two copies of T i are executed in parallel, each with q i = p 2 processors. If no failure strikes, both copies finish execution in time

w i α i + 1-αi p 2
, since each copy uses p 2 processors. If a failure strikes one copy, we proceed as before, account for the downtime D, recover (in time R i ( p 2 ) now), and restart execution of that copy. Then there are two cases: (i) if the second copy successfully completes its first execution, the failure has no impact and the execution time remains the same as the failure-free execution time; (ii) however, if the second copy also fails to execute, we resume its execution, and iterate until one copy successfully completes. Of course, case (ii) is less likely to happen than case (i), which explains why replication can be useful. Finally, if we decide to checkpoint after T i , the first successful copy will take the checkpoint in time C i ( p 2 ). Replication raises several complications in terms of checkpoint and recovery costs. When a replicated task T i is checkpointed, we can enforce that only one copy (the first one to complete execution) would write the output data onto the storage medium, hence with a cost C i ( p 2 ), as stated above. Similarly, when a single copy of a replicated task T i performs a recovery after a failure, the cost would be R i ( p 2 ). However, in the unlikely event where both copies are struck by a failure at close time instances, their recoveries would overlap, and the cost can vary anywhere between R i ( p 2 ) and 2R i ( p 2 ), depending upon the amount of contention, the length of the overlap and where the I/O bottleneck lies. We will experimentally evaluate the impact of the recovery cost with replication in Section V. For simplicity, in the rest of the paper, we use C rep i for the checkpoint cost of T i when it is replicated, and C norep i when it is not. Similarly, we use R rep i for the recovery cost when T i is replicated, and R norep i when it is not. Note that the recovery cost of T i depends upon whether it is replicated or not, but does not depend upon whether the checkpointed task T i-1 was replicated or not, since we need to read the same file from the storage medium in both cases. The values of C rep 2). Finally, we let E rep (i) denote the expected execution time of T i with replication and when accounting for failures, when T i-1 is checkpointed. The derivation of E rep (i) is much more complicated than for E norep (i) and represents a new contribution of this work. We explain how to compute E rep (i) in Section III-B.

E. Optimization problem

The objective is to minimize the expected makespan of the workflow in the presence of fail-stop errors. For each task, we have four choices: either we replicate the task or not, and either we checkpoint it or not. We point out that none of these decisions can be made locally. Instead, we need to account for previous decisions and optimize globally. Our major contribution of this work is to provide an optimal dynamic programming algorithm to solve this problem, which we denote as CHAINSREPCKPT.

We point out that CHAINSCKPT, the simpler problem without replication, i.e., optimally placing checkpoints for a chain of tasks, has been extensively studied. The first dynamic programming algorithm to solve CHAINSCKPT appears in the pioneering paper of Toueg and Babaoglu [START_REF] Toueg | On the optimum checkpoint selection problem[END_REF] back in 1984 (see Section VI on related work for further references). Adding replication dramatically complicates the solution. Here is an intuitive explanation: When the algorithm recursively considers a segment of tasks from T i to T j , where T i-1 and T j are both checkpointed and no intermediate task T k , i ≤ k < j is checkpointed, there are many cases to consider to account for possible different values in: (i) execution time, since some tasks in the segment may be replicated; (ii) checkpoint, whose cost depends upon whether T j is replicated or not; and (iii) recovery, whose cost depends upon whether T i is replicated or not. We provide all details in Section IV.

III. COMPUTING E norep (i) AND E rep (i)

This section details how to compute the expected time needed to execute a task T i , assuming that the predecessor of T i has been checkpointed. Hence, we need to re-execute only T i when a failure strikes. We explain how to deal with the general case of re-executing a segment of tasks, some of them replicated, in Section IV. We start with the case where T i is not replicated. It is already known how to compute E norep (i) [START_REF] Hérault | Fault-Tolerance Techniques for High-Performance Computing, Computer Communications and Networks[END_REF], but we present this case to help the reader follow the derivation in Section III-B for the case where T i is replicated, which is new and much more involved.

A. Computing E norep (i)

To compute E norep (i), the average execution time of T i with p processors without replication, we conduct a case analysis:

• Either an error strikes during the execution, and in this case we lose some work and then need to re-execute the task; • Either there is no error, and in this case we only need the failure-free execution time

T norep i = w i α i + 1-αi p
. This leads to the following recursive formula:

E norep (i) = P(X p ≤ T norep i ) T norep lost (T norep i ) + D + R norep i + E norep (i) (3)
+ (1 -P(X p ≤ T norep i ))T norep i ,
where P(X p ≤ t) is the probability of having a failure on one of the p processors before time t, i.e., P(X p ≤ t) = 1-e -λ ind pt . The time lost when a failure strikes is the expectation of the random variable X p , knowing that the error stroke before the end of the task. We compute it as follows:

T norep lost (T norep i ) = +∞ 0 xP(Xp = x|Xp ≤ T norep i )dx = 1 P(Xp ≤ T norep i ) T norep i 0 xP(Xp = x)dx = 1 P(Xp ≤ T norep i ) T norep i 0 x dP(Xp ≤ x) dx dx
After integration, we get the formula:

T norep lost (T norep i ) = 1 λ ind p - t e λ ind pT norep i -1 . (4)
Replacing the terms in Equation ( 3) and solving, we derive:

E norep (i) = (e λ ind pT norep i -1)( 1 λ ind p + D + R norep i ). (5)
Recall that 5). Finally, if we decide to checkpoint T i , we simply add

T norep i = w i α i + 1-αi p in Equation (
C norep i to E norep (i). B. Computing E rep (i)
We now discuss the case where T i is replicated; each copy executes with p 2 processors. To compute E rep (i), the expected execution time of T i with replication, we conduct the same case analysis:

• Either two failures strike before the end of the task, with one failure striking each copy, and we have lost some work and need to re-execute the task; • Either (at least) one copy is not hit by any failure, and in this case we only need the failure-free execution time

T rep i = w i α i + 1-αi p 2
. This leads to the following formula:

E rep (i) = P(Y p ≤ T rep i ) T rep lost (T rep i ) + D + R rep i + E rep (i) +(1 -P(Y p ≤ T rep i ))T rep i (6)
where P(Y p ≤ t) is the probability of having a failure on both replicas of p 2 processors before time t, i.e., P(Y p ≤ t) = (1e -λ ind p 2 t ) 2 . The time lost when both copies fail can be computed in a similar way as before:

T rep lost (T rep i ) = 1 P(Y p ≤ T rep i ) T rep i 0 x dP(Y p ≤ x) dx dx.
After computation and verification using a Maple sheet, we obtain the following result:

T rep lost (T rep i ) = (-2λ ind pT rep i -4)e - λ ind pT rep i 2 +(λ ind pT rep i +1)e -λ ind pT rep i +3 (e - λ ind pT rep i 2 -1) 2 λ ind p . (7)
Replacing the terms in Equation ( 6) and solving, we get:

E rep (i) = 3e λ ind pT rep i -4e λ ind p 2 T rep i + 1 2e λ ind p 2 T rep i -1 1 λ ind p + ( e λ ind pT rep i 2e λ ind p 2 T rep i -1 -1)(D + R rep i ). (8)
Recall that

T rep i = w i α i + 1-αi p 2
in Equation [START_REF] Casanova | On the impact of process replication on executions of large-scale parallel applications with coordinated checkpointing[END_REF]. Finally, if we decide to checkpoint T i , we simply add C rep i to E rep (i).

IV. OPTIMAL DP ALGORITHM

In this section, we provide a dynamic programming algorithm to solve the CHAINSREPCKPT problem for a linear chain of n tasks.

Theorem 1. The optimal solution to the CHAINSREPCKPT problem can be obtained using a dynamic programming algorithm in O(n 2 ) time, where n is the number of tasks in the chain.

Proof. The algorithm recursively computes the expectation of the optimal time required to execute tasks T 1 to T i and then checkpoint T i . As already mentioned, we need to distinguish two cases, according to whether T i is replicated or not, because the cost of the final checkpoint depends upon this decision. Hence, we recursively compute two different functions:

• T rep opt (i), the expectation of the optimal time required to execute tasks T 1 to T i , knowing that T i is replicated; • T norep opt (i), the expectation of the optimal time required to execute tasks T 1 to T i , knowing that T i is not replicated. Note that checkpoint time is not included in T rep opt (i) nor T norep opt (i). The solution to CHAINSREPCKPT will be given by

min T rep opt (n) + C rep n , T norep opt (n) + C norep n . (9)
We start with the computation of T rep opt (j) for 1 ≤ j ≤ n, hence assuming that the last task T j is replicated. We express T rep opt (j) recursively as follows:

T rep opt (j) = min 1≤i<j                T rep opt (i) + C rep i + T rep,rep N C (i + 1, j), T rep opt (i) + C rep i + T norep,rep N C (i + 1, j), T norep opt (i) + C norep i + T rep,rep N C (i + 1, j), T norep opt (i)+C norep i +T norep,rep N C (i + 1, j), R rep 1 + T rep,rep N C (1, j), R norep 1 + T norep,rep N C (1, j)                (10)
In Equation [START_REF] Crago | Programming models and development software for a space-based many-core processor[END_REF], T i corresponds to the last checkpointed task before T j , and we try all possible locations T i for taking a checkpoint before T j . The first four lines correspond to the case where there is indeed an intermediate task T i that is checkpointed, while the last two lines correspond to the case where no checkpoint at all is taken until after T j .

The first two lines of Equation ( 10) apply to the case where T i is replicated. Line 1 is for the case when T i+1 is replicated, and line 2 when it is not. In the first line of Equation ( 10), T rep,rep N C (i+1, j) denotes the optimal time to execute tasks T i+1 to T j without any intermediate checkpoint, knowing that T i is checkpointed, and both T i+1 and T j are replicated. If T i+1 is not replicated, we use the second line of Equation [START_REF] Crago | Programming models and development software for a space-based many-core processor[END_REF], where

T norep,rep N C (i + 1, j) is the counterpart of T rep,rep N C
(i + 1, j), except that it assumes that T i+1 is not replicated. This information on T i+1 (replicated or not) is needed to compute the recovery cost when executing tasks T i+1 to T j and experimenting a failure.

Lines 3 and 4 apply to the case where T i is not replicated, with similar notations as before. In the first four lines, no task between T i+1 and T j-1 is checkpointed, hence the notation NC for no checkpoint.

If no checkpoint at all is taken before T j (this corresponds to the case i = 0), we use the last two lines of Equation ( 10): we include the cost to read the initial input, which depends whether T 1 is replicated (in line 5) or not (in line 6).

We have a very similar equation to express T norep opt (j) recursively, with obvious notations:

T norep opt (j) = min 1≤i<j          T rep opt (i) + C rep i + T rep,norep N C (i + 1, j), T rep opt (i) + C rep i + T norep,norep N C (i + 1, j), T norep opt (i) + C norep i + T rep,norep N C (i + 1, j), T norep opt (i)+C norep i +T norep,norep N C (i + 1, j), R rep 1 + T rep,norep N C (1, j), R norep 1 + T norep,norep N C (1, j)          (11)
To synthesize notations, we have defined T A,B N C (i+1, j), with A, B ∈ {rep, norep}, as the optimal time to execute tasks T i+1 to T j without any intermediate checkpoint, knowing that T i is checkpointed, T i+1 is replicated if and only if A = rep, and T j is replicated if and only if B = rep. In a nutshell, we have to account for the possible replication of the first task T i+1 after the last checkpoint, and of the last task T j , hence the four cases.

There remains to compute T A,B N C (i, j) for all 1 ≤ i, j ≤ n and A, B ∈ {rep, norep}. This is still not easy, because there remains to decide which intermediate tasks should be replicated. In addition to the status of T j (replicated or not, according to the value of B), the only thing we know so far is that the only checkpoint that we can recover from while executing tasks T i to T j is the checkpoint taken after task T i-1 , hence we need to re-execute from T i whenever a failure strikes. Furthermore, T i is replicated if and only if A = rep, hence we know the corresponding cost for recovery, R A i . Letting T A,B N C (i, j) = 0 whenever i > j, we can express T A,B N C (i, j) for 1 ≤ i ≤ j ≤ n as follows:

T A,B N C (i, j) = min T A,rep N C (i, j -1), T A,norep N C (i, j -1) + T A,B (j | i).
Here the new (and final) notation T A,B (j | i) is simply the time needed to execute task T j , knowing that a failure during T j implies to recover from T i . Indeed, to execute tasks T i to T j , we account recursively for the time to execute T i to T j-1 ; T i-1 is still checkpointed; T i is replicated if and only if A = rep, T j is replicated if and only if B = rep, and we consider both cases whether T j-1 is replicated or not. The time lost in case of a failure during T j depends whether T j is replicated or not, and we need to restart from T i in case of failure, hence the notation T A,B (j | i), representing the expected execution time for task T j with or without replication (depending on B), given that we need to restart from T i if there is a failure (and T i is replicated if and only if A = rep).

The last step is hence to express these execution times. We start with the case where T j is not replicated:

T A,norep (j | i) = 1 -e -λT norep j T norep lost (T norep j ) + D + R A i + min T A,rep N C (i, j -1), T A,norep N C (i, j -1) + T A,norep (j | i) +e -λT norep j T norep j .
The term in e -λT norep j represents the case without failure, where the execution time is simply T norep j . When a failure strikes, we account for T norep lost (T norep j ), the time lost within T j , and whose value is given by Equation ( 4). Then we pay a downtime and a recovery (with a cost depending on A). Next, we need to re-execute all the tasks since the last checkpoint (T i to T j-1 ) and take the minimal value obtained out of the execution where T j-1 is replicated or not; finally we execute T j again (with a time T A,norep (j | i)).

The formula is similar with replication, where the probability of failure accounts for the fact that we need to recover only if both replicas fail:

T A,rep (j | i) = 1 -e - λT rep j 2 2 T rep lost (T rep j ) + D + R A i + min T A,rep N C (i, j -1), T A,norep N C (i, j -1) + T A,rep (j | i) +   1 -1 -e - λT rep j 2 2   T rep j .
Note that the value of T rep lost (T rep j ) is given by Equation ( 7). Overall, we need to compute the O(n2 ) intermediate values T A,B (j | i) and T A,B N C (i, j) for 1 ≤ i, j ≤ n and A, B ∈ {rep, norep}, and each of these take constant time. There are O(n) values T A opt (i), for 1 ≤ i ≤ n and A ∈ {rep, norep}, and these perform a minimum over at most 6n elements, hence they can be computed in O(n). The overall complexity is therefore O(n 2 ).

V. EXPERIMENTS In this section, we evaluate the advantages of adding replication to checkpointing. We first describe the evaluation framework in Section V-A, then we compare checkpoint with replication to checkpoint only in Section V-B. In Section V-C, we assess the impact of the different model parameters on the performance of the optimal strategy. Finally, Section V-D compares the performance of the optimal solution to alternative sub-optimal solutions 2 .

A. Experimental setup

We fix the total work in the chain to W = 10, 000 seconds, and we rely on five different work distributions, where all tasks are fully parallel (α i = 0):

• UNIFORM: every task is of length W n , i.e., identical tasks. • INCREASING: the length of the tasks constantly increases, i.e., task T i has length i 2W n(n+1) . • DECREASING: the length of the tasks constantly decreases, i.e., task T i has length (ni + 1) 2W n(n+1) . • HIGHLOW: the chain is formed by big tasks followed by small tasks. The large tasks represent 60% of the total work and there are n 10 such tasks. Small tasks represent the remaining 40% of the total work and consequently there are n -n 10 small tasks. • RANDOM: task lengths are chosen uniformly at random between W 2n and 3W 2n . If the total work of the first i tasks reaches W , the weight of each task is multiplied by i n so that we can continue adding the remaining tasks. Experiments with increasing sequential part (α i ) for the tasks are available in the companion research report [START_REF] Benoit | Combining checkpointing and replication for reliable execution of linear workflows[END_REF]. Setting α i = 0 amounts to being in the worse possible case for replication, since the tasks will fully benefit of having twice as much processors when not replicated.

For simplicity, we assume that checkpointing costs are equal to the corresponding recovery costs, assuming that read and write operations take approximately the same amount of time, i.e., R norep , where 1 ≤ α ≤ 2, and we assess the impact of parameter α in Section V-C. In the following experiments, we measure the performance of a solution by evaluating the associated normalized expected makespan, i.e., the expected execution time needed to compute all the tasks in the chain, with respect to the execution time without errors, checkpoints, or replicas.

B. Comparison to checkpoint only

We start with an analysis of the solutions obtained by running the optimal dynamic programming (DP) algorithm CHAINS-REPCKPT on chains of 20 tasks for the five different work distributions described in Section V-A. We also run a variant of CHAINSREPCKPT that does not perform any replication, hence using a simplified DP algorithm, that is called CHAINSCKPT.

We vary the error rate λ ind p from 10 -8 to 10 -2 . Note that when λ ind p = 10 -3 , we expect an average of 10 errors per execution of the entire chain (neglecting potential errors during checkpoints and recoveries). The checkpoint cost

C norep i = a i is constant per task (hence b i = c i = 0) and varies from 10 -3 T norep i to 10 3 T norep i . For replicated tasks, we set α = 1 in this experiment, i.e., C rep i = C norep i and R rep i = R norep i .
Figure 1 presents the results of these experiments for the UNIFORM distribution. We are interested in the number of checkpoints and replicas in the optimal solution: None means that no task is checkpointed nor replicated, Checkpointing Only means that some tasks are checkpointed but no task is replicated, Replication Only means that some tasks are replicated, but no task is checkpointed, and Checkpointing+Replication means that some tasks are checkpointed and some tasks are replicated. First, we observe that when the checkpointing cost is less than or equal to the length of a task (on the left of the black line), the optimal solution does not use replication. However, if the checkpointing cost exceeds the length of one task (on the right of the black vertical bar), replication proves useful in some cases. In particular, when the error rate λ ind p is medium to high (i.e., 10 -6 to 10 -4 ), we note that only replication is used, meaning that no checkpoint is taken and that replication alone is a better strategy to prevent any error from stopping the application. When the error rate is the highest (i.e., 10 -4 or higher), replication is added to the checkpointing strategy to ensure maximum reliability. It may seem unusual to use replication alone when checkpointing costs increase. This is because the recovery cost has to be taken into account as well, in addition to re-executing the tasks that have failed. Replication is added to reduce this risk: if successful, there is no recovery cost to pay for, nor any task to re-execute. Finally, note that for small error rates and checkpointing costs, only checkpoints are used, because their cost is smaller than the average re-execution time in case of failure. We point out that similar results are obtained when using other work distributions (see the extended version [START_REF] Benoit | Combining checkpointing and replication for reliable execution of linear workflows[END_REF]).

In the next experiment, we focus on scenarios where both checkpointing and replication are useful, i.e., we set the checkpointing cost to be twice the length of a task (i.e.,

C norep i = a i = 2T norep i
), and we set the error rate λ ind p to 10 -3 , which corresponds to the case highlighted in red in Figure 1. Figure 2 presents the optimal solutions obtained with the CHAINSCKPT and CHAINSREPCKPT algorithms for the UNI-FORM, INCREASING, DECREASING, HIGHLOW and RANDOM work distributions, respectively. First, for the UNIFORM work distribution, it is clear that the CHAINSREPCKPT strategy leads to a decrease of the number of checkpoints compared to the CHAINSCKPT strategy. Under the CHAINSCKPT strategy, a checkpoint is taken every two tasks, while under the CHAINS-REPCKPT strategy, a checkpoint is taken every three tasks instead, while two out of three tasks are also replicated. Then, for the INCREASING and DECREASING work distributions, the results show that most tasks should be replicated, while only the largest tasks are also checkpointed. A general rule of thumb is that replication only is preferred for small tasks while checkpointing and replication is reserved for larger tasks, where the probability of failure and the re-execution cost are the highest. Finally, we observe a similar trend for the HIGHLOW work distribution, where two of the first four large tasks are checkpointed and replicated.

Figure 3 compares the performance of CHAINSREPCKPT to the checkpoint-only strategy CHAINSCKPT. First, we observe that the expected normalized makespan of CHAINSCKPT remains almost constant at ≈ 4.5 for any number of tasks and for any work distribution. Indeed, in our scenario, checkpoints are expensive and the number of checkpoints that can be used is limited to ≈ 17 in the optimal solution, as shown in the middle plot. However, the CHAINSREPCKPT strategy can take advantage of the increasing number of smaller tasks by replicating them. In this scenario (high error rate and high checkpoint cost), this is clearly a winning strategy. The normalized expected makespan keeps decreasing as n increases, as the corresponding number of tasks that are replicated increases almost linearly. The CHAINSREPCKPT strategy reaches a normalized makespan of ≈ 2.6 for n = 100, i.e., a reduction of 35% compared to the normalized expected makespan of the CHAINSCKPT strategy. This is because replicated tasks tend to decrease the global probability of having a failure, thus reducing even more the number of checkpoints needed as seen previously. Regarding the HIGHLOW work distribution, we observe a higher optimal expected makespan for both the CHAINSCKPT and the CHAINSREPCKPT strategies. Indeed, in this scenario, the first tasks are very large (60% of the total work), which greatly increases the probability of failure and the associated re-execution cost.

C. Impact of error rate and checkpoint cost on the performance

Figure 4 shows the impact of three of the model parameters on the optimal expected normalized makespan of both CHAINSCKPT and CHAINSREPCKPT. First, we show the impact of the error rate λ ind p on the performance. The CHAINS-REPCKPT algorithm improves the CHAINSCKPT strategy for large values of λ ind p: replication starts to be used for λ ind p > 2.6 × 10 -4 and it reduces the makespan by ≈ 16% for λ ind p = 10 -3 and by up to ≈ 40% when λ ind p = 10 -2 , where all tasks are checkpointed and replicated.

Then, we investigate the impact of the checkpointing cost with respect to the task length. As shown in Figure 1, replication is not needed for small checkpointing costs, i.e., when the checkpointing cost is between 0 and 0.8 times the cost of one task: in this scenario, all tasks are checkpointed and both strategies lead to the same makespan. When the checkpointing cost is between 0.9 and 1.6 times the cost of one task, CHAINSREP-CKPT checkpoints and replicates half of the tasks. Overall, the CHAINSREPCKPT strategy improves the optimal normalized expected makespan by ≈ 11% for a checkpointing cost ratio of 1.6, and by as much as ≈ 36% when the checkpointing cost is five times the length of one task.

We now investigate the impact of the ratio between the checkpointing and recovery cost for replicated tasks and nonreplicated tasks α and we present the results for α = 1

(C rep i = R rep i = C norep i = R norep i ), α = 1.5 (C rep i = R rep i = 1.5C norep i = 1.5R norep i ) and α = 2 (C rep i = R rep i = 2C norep i = 2R norep i ).
As expected, the makespan increases with α, but it is interesting to note that the makespan converges towards a same lower-bound as the number of (smaller) tasks increases. As shown previously, when tasks are smaller, CHAINSREPCKPT favors replication over checkpointing, especially when the checkpointing cost is high, which means less checkpoints, recoveries and re-executions.

Finally, we evaluate the efficiency of both strategies when the number of processors increases. For this experiment, we instantiate the model using variable checkpointing costs, i.e., we do not use b i = c i = 0 anymore, so that the checkpointing/recovery cost depends on the number of processors. We set n = 50, λ ind = 10 -7 and we make p vary from 10 to 10,000 (i.e., the global error rate varies between 10 -6 and 10 -3 ). Figure 5 presents the results of the experiment using three different sets of values for a i , b i and c i . We see that when b i increases while c i decreases, the replication becomes useless, even for the larger failure rate values. However, when the term c i p becomes large in front of bi p , we see that CHAINSREPCKPT is much better than CHAINSCKPT, as the checkpointing costs tend to decrease, in addition to all the other advantages investigated in the previous sections. With p = 10, 000, the three different experiments show an improvement of 80.5%, 40.7% and 0% (from left to right, respectively).

D. Impact of the number of checkpoints and replicas

Figure 6 shows the impact of the number of checkpoints and replicas on the normalized expected makespan for different checkpointing costs and error rates λ ind p under the UNIFORM work distribution. We show that the optimal solution with CHAINSREPCKPT (highlighted in green) always matches the minimum value obtained in the simulations, i.e., the optimal number of checkpoints, number of replicas, and expected execution times are consistent. In addition, we show that in scenarios where both the checkpointing cost and the error rate are high, even a small deviation from the optimal solution can quickly lead to a large overhead.

VI. RELATED WORK

In this section, we discuss the work related to checkpointing and replication. Each of these mechanisms has been studied for coping with fail-stop errors and/or with silent errors. The present work combines checkpointing and replication for linear workflows in the presence of fail-stop errors.

A. Checkpointing

The de-facto general-purpose recovery technique in highperformance computing is checkpointing and rollback recovery [START_REF] Chandy | Distributed snapshots: Determining global states of distributed systems[END_REF], [START_REF] Elnozahy | A survey of rollback-recovery protocols in message-passing systems[END_REF]. Checkpointing policies have been widely studied and we refer to [START_REF] Hérault | Fault-Tolerance Techniques for High-Performance Computing, Computer Communications and Networks[END_REF] for a survey of various protocols. For divisible load applications where checkpoints can be inserted at any point in the execution for a nominal cost C, there exist well-known formulas proposed by Young [START_REF] Young | A first order approximation to the optimum checkpoint interval[END_REF] and Daly [START_REF] Daly | A higher order estimate of the optimum checkpoint interval for restart dumps[END_REF] to determine the optimal checkpointing period. For applications expressed as a linear workflow, as considered in the present work, the problem of finding the optimal checkpointing strategy, i.e., of determining which tasks to checkpoint, in order to minimize the expected execution time, has been solved by Toueg and Babaoglu [START_REF] Toueg | On the optimum checkpoint selection problem[END_REF].

Single-level checkpointing schemes suffer from the intrinsic limitation that the cost of checkpointing and recovery grows with the failure probability, and becomes unsustainable at large scale [START_REF] Ferreira | Evaluating the viability of process replication reliability for exascale systems[END_REF], [START_REF] Bosilca | Unified model for assessing checkpointing protocols at extreme-scale[END_REF] (even with diskless or incremental checkpointing [START_REF] Plank | Diskless checkpointing[END_REF]). Recent advances in decreasing the cost of checkpointing include multi-level checkpointing approaches, or the use of SSD or NVRAM as secondary storage [START_REF] Cappello | Toward Exascale Resilience: 2014 update[END_REF]. To reduce the I/O overhead, various two-level checkpointing protocols have been studied. Vaidya [START_REF] Vaidya | A case for two-level distributed recovery schemes[END_REF] proposed a two-level recovery scheme that tolerates a single node failure using a local checkpoint stored on a partner node. If more than one failure occurs during any local checkpointing interval, the scheme resorts to the global checkpoint. Silva and Silva [START_REF] Silva | Using two-level stable storage for efficient checkpointing[END_REF] advocated for a similar scheme by using memory protected by XOR encoding to store local checkpoints. Di et al. [START_REF] Di | Toward an optimal online checkpoint solution under a two-level HPC checkpoint model[END_REF] analyzed a two-level computational pattern, and proved that equal-length checkpointing segments constitute the optimal solution. Benoit et al. [START_REF] Benoit | Optimal resilience patterns to cope with fail-stop and silent errors[END_REF] relied on disk checkpoints to cope with fail-stop failures and used memory checkpoints coupled with error detectors to handle silent data corruptions. They derived first-order approximation formulas for the optimal pattern length as well as the number of memory checkpoints between two disk checkpoints. The present work employs single-level checkpointing (in memory or on stable storage) for individual tasks in linear workflows.

B. Replication

As mentioned earlier, this work only considers duplication. Triplication [START_REF] Lyons | The use of triple-modular redundancy to improve computer reliability[END_REF] (three replicas per task) is also possible yet only useful with extremely high failure rates, which are unlikely in HPC systems. The use of redundant MPI processes is analyzed in [START_REF] Casanova | On the impact of process replication on executions of large-scale parallel applications with coordinated checkpointing[END_REF], [START_REF] Engelmann | Redundant execution of HPC applications with MR-MPI[END_REF], [START_REF] Ferreira | Evaluating the viability of process replication reliability for exascale systems[END_REF]. In particular, the work by Ferreira et al. [START_REF] Ferreira | Evaluating the viability of process replication reliability for exascale systems[END_REF] has studied the use of process replication for MPI applications, using two replicas per MPI process. They provide a theoretical analysis of parallel efficiency, an MPI implementation that supports transparent process replication (including failure detection, consistent message ordering among replicas, etc.), and a set of experimental and simulation results. Threadlevel replication has been investigated in [START_REF] Yu | Thread-level redundancy fault tolerant CMP based on relaxed input replication[END_REF], [START_REF] Crago | Programming models and development software for a space-based many-core processor[END_REF], [START_REF] Rashid | Supporting highly-decoupled threadlevel redundancy for parallel programs[END_REF]. The present work targets selective task replication as opposed to full task replication in conjunction with selective task checkpointing to cope with fail-stop errors and minimize makespan.

Partial redundancy is studied in [START_REF] Elliott | Combining partial redundancy and checkpointing for HPC[END_REF], [START_REF] Stearley | Does partial replication pay off?[END_REF], [START_REF] Subasi | Programmerdirected partial redundancy for resilient HPC[END_REF] (in combination with coordinated checkpointing) to decrease the overhead of full replication. Adaptive redundancy is introduced in [START_REF] George | ADFT: An adaptive framework for fault tolerance on large scale systems using application malleability[END_REF], where a subset of processes is dynamically selected for replication. Earlier work [START_REF] Benoit | Identifying the right replication level to detect and correct silent errors at scale[END_REF] considered replication in the context of divisible load applications. Herein, task replication (including work and data) is studied in the context of linear workflows, which represent a harder case than that of divisible load applications as tasks cannot arbitrarily be divided and are executed non-preemptively.

Ni et al. [START_REF] Ni | ACR: Automatic Checkpoint/Restart for Soft and Hard Error Protection[END_REF] introduce process duplication to cope both with fail-stop and silent errors. Their pioneering paper contains many interesting results. It differs from this work in that they limit themselves to perfectly parallel applications while we investigate per task speedup profiles that obey Amdahl's law. More recently, Subasi et al. [START_REF] Subasi | Designing and Modelling Selective Replication for Fault-Tolerant HPC Applications[END_REF] proposed a software-based selective replication of task-parallel applications used for both fail-stop and silent errors. In contrast, this work (i) considers dependent tasks such as found in applications consisting of linear workflows; and (ii) proposes an optimal dynamic programming algorithm to solve the selective replication and checkpointing problem. Combining replication with checkpointing has also been proposed in [START_REF] Schroeder | Understanding Failures in Petascale Computers[END_REF], [START_REF] Zheng | Reliability-aware scalability models for high performance computing[END_REF], [START_REF] Engelmann | The case for modular redundancy in large-scale high performance computing systems[END_REF] for HPC platforms, and in [START_REF] Leblanc | VolpexMPI: An MPI Library for Execution of Parallel Applications on Volatile Nodes[END_REF], [START_REF] Yi | Using replication and checkpointing for reliable task management in computational grids[END_REF] for grid computing.

VII. CONCLUSION

In this paper, we have studied the combination of checkpointing and replication to minimize the execution time of linear workflows in a failure-prone environment. We have introduced a sophisticated dynamic programming algorithm that solves the problem optimally, by determining which tasks to checkpoint and which tasks to replicate in order to minimize the total execution time. This dynamic programming algorithm has been validated through extensive simulations that reveal the conditions in which checkpointing, replication, or both lead to improved performance. We have observed that the gain over the checkpoint-only approach is quite significant, in particular when checkpoint is costly and error rate is high. Future work will address workflows whose dependence graphs are more complex than linear chains of tasks. Although an optimal solution seems hard to reach, the design of efficient heuristics that decide where to locate checkpoints and when to use replication would prove highly beneficial for the efficient and reliable execution of HPC applications on current and future large-scale platforms. We also plan to run some experiments on real applications in the near future. Finally, extending the approach to cope with both fail-stop and silent errors would be interesting, since both error sources are massively and simultaneously present on large-scale platforms.

i

  and C norep i can be instantiated from Equation (1) and those of R rep i and R norep i can be instantiated from Equation (

Figure 1 :Figure 2 :

 12 Figure 1: Impact of checkpoint/recovery cost and error on the usage of checkpointing and replication. Total work is fixed to 10, 000s and is distributed uniformly among n = 20 tasks (i.e., T 1 = T 2 = • • • = T 20 = 500s).

  UNIFORM, INCREASING, DECREASING, HIGHLOW, RANDOM distributions

Figure 3 :Figure 4 :

 34 Figure 3: Comparison of the CHAINSCKPT and CHAINSREPCKPT strategies for different numbers of tasks: impact on the makespan (left), number of checkpoints (middle) and number of replicas (right) with an error rate of λ ind p = 10 -3 and a constant chekpointing/recovery cost C norep i

Figure 5 :

 5 Figure 5: Comparison of the CHAINSCKPT and CHAINSREPCKPT strategies for different numbers of processors, with different parameter values for the checkpointing cost (a i , b i , c i ).

Figure 6 :

 6 Figure 6: Impact of the number of checkpoints and replicas on the normalized expected makespan for λ = 10 -4 (top), λ = 10 -3 (middle) and λ = 10 -2 (bottom) and for checkpointing costs equal to 0.5 × T norep i

We only consider duplication in this work. Having three replicas (triplication) is possible but useful only with extremely high failure rates that cannot be mitigated via duplication, which are unlikely in HPC systems[START_REF] Ferreira | Evaluating the viability of process replication reliability for exascale systems[END_REF].

The simulator is publicly available at http://graal.ens-lyon.fr/ ∼ yrobert/ chainsrep.zip so that interested readers can instantiate their preferred scenarios and repeat the same simulations for reproducibility purpose.

Acknowledgements: This work has been partially supported by the Swiss Platform for Advanced Scientific Computing (PASC) project SPH-EXA.


Based Image Analysis (OBIA) for Urban Mapping

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

УДК 550.8 P.Lemenkova, pauline.lemenkova@gmail.com Univerzita Karlova v Praze, Prirodovedecka fakulta

GEO-INFORMATION TECHNOLOGIES OF OBJECT BASED IMAGE ANALYSIS (OBIA) FOR URBAN MAPPING

Current work is aimed at the deriving of information from the remote sensed VHR data using a priori knowledge in the Object Based Image Analysis (OBIA) approach. OBIA technology is new and effective tool for urban mapping, as it enables dealing with raster images for detailed and precise cartography. Specific focus of this study is selected urban areas of the city of Brussels, Belgium. The study is performed using panchromatic very high resolution (VHR) image processed in the eCognition software.

Application of the a priori knowledge in the OBIA approach towards classification of the satellite imagery for solving problem of the land cover studies is the target aim of this research. Some attempts of utilizing knowledge in the classifying map objects are performed [START_REF] Lesbegueries | A Platform for Spatial Data Labeling in an Urban Context[END_REF] describing techniques of the labelling objects in urban environment. The authors developed an open source framework to study urban evolutions using vector based topographic databases as a part of the open GeOpenSim project. Using visualization of the geospatial objects from the database and expert knowledge labelling of the objects and generated the data set has been performed. It included continuous and discontinuous urban fabric, individual houses, high and low density mixed housing surface, hydrographical and communication network (canals, rivers), as well as specific urban surface (industrial wasteland and buildings), etc.

Among earlier works, a review of the existing knowledge based approaches and examples in geospatial modelling is presented [START_REF] Cross | Knowledge-based interpretation of remotely sensed images[END_REF], where current development of this research branch is demonstrated. As it is noticed, the external knowledge that can be used for image interpretation may exist in a the form of models of the imaging process knowledge and models of the types of structure that can be on the image, as well as in view of other data sets, e.g., previous interpretations or map data by the user, and the user's own expertise and experience. Example of application of knowledge based expert image processing is given [START_REF] Baatz | eCognition User Guide[END_REF], where meaningful area-wide spatial information for city planning and management from IKONOS imagery is derived. The authors applied expert knowledge for image classification and mapping homogeneous zones of urban environment for detection of spatial distribution of the built-up densities within the city. The classification based on shape and neighbourhood enabled image to be segmented by object extraction using region-growing rule.

The methodology of current work considered existing works and includes processing and classification of the remote sensing data (satellite very high resolution images) using eCognition software. The operation "Multi-resolution Segmentation" was chosen for image processing, as this is one of the most important image processing tools. During segmentation the image was divided up into large homogeneous regions and isolated shapes into the separate polygons within the study area. This procedure was performed at a different scale factors to adjust local conditions, such as urban structures, contrast factors, topology, etc. The four first layers in the layers legend represent multispectral image, while the fifth layer belongs to the panchromatic image. These two images were processed, in order to benefit from the high spatial and spectral resolution of the images which have different properties. Besides, processing of both of them gave various results: the panchromatic VHR image enabled to achieve very detailed segmentation of the image. However, for the current research aim (mapping urban environment and detecting separate buildings), the level of such scale was too detailed. The nearest neighbour classifies subdivide image into objects based on the image sample using mean spectral signature values of the objects [START_REF] Walter | Object-based classification of remote sensing data for change detection[END_REF].

The results are presented by accurate geographic classification of the raster image. The objects are grouped into the separated classes connected with each other according to the hierarchical values of their features. The target objects are detected using existing knowledge which helped to find out what information exists in the objects based on training test areas (TTA). The classification is done using nearest neighbour principle after the manual defining of the number of sample objects [START_REF] Walter | Object-based classification of remote sensing data for change detection[END_REF]. Alike to the standard pixel-based classification, all spectral bands are also used as input channels in OBIA approach, so that the difference consists not in the data but rather in their methodological processing [5]: while pixel-based classification is based on the classification of each pixel separately, the object-based classification treats together all pixels that belong to one object, which is embedded in eCognition. The method of the multiresolution segmentation procedure using OBIA approach was applied to the image in eCognition software and the image was processed (Fig. 2). The classification is based on the segmentation of the whole image into meaningful polygons, according to the fuzzy logic approach and nearest neighbour classifier which is similar to the supervised classification in usual image analysis software. The work proved effectiveness of the object based image analysis approach for satellite data processing in urban mapping.

ig.1. Image classification and objects recognition in eCognition software

ig.2. Fragment of classification: objects classified as 'vegetation' class (red coloured). Initial image: left.

Acknowledgment

The financial support of this research has been provided by the Wallonie-Bruxelles-International (WBI) Scholarship Committee of Belgium.