Anne Benoit

Aurelien Cavelan

Florina Ciorba

Valentin Le Fèvre

Yves Robert

Combining Checkpointing and Replication for Reliable Execution of Linear Workflows with Fail-Stop and Silent Errors

Keywords: checkpoint, replication, HPC, fail-stop error, silent error, linear workflow

Large-scale platforms currently experience errors from two different sources, namely fail-stop errors (which interrupt the execution) and silent errors (which strike unnoticed and corrupt data). This work combines checkpointing and replication for the reliable execution of linear workflows on platforms subject to these two error types. While checkpointing and replication have been studied separately, their combination has not yet been investigated despite its promising potential to minimize the execution time of linear workflows in error-prone environments. Moreover, combined checkpointing and replication has not yet been studied in the presence of both fail-stop and silent errors. The combination raises new problems: for each task, we have to decide whether to checkpoint and/or replicate it to ensure its reliable execution. 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.

Combinaison des techniques de checkpoint et de réplication pour l'exécution efficace de chaînes de tâches avec erreurs fatales et silencieuses

Résumé : Les plateformes à grande échelle subissent des erreurs de deux sources différentes, à savoir les erreurs fatales (qui interrompent l'exécution de l'application) et les erreurs silencieuses (qui ne sont pas détectées lorsqu'elles arrivent et corrompent les données). Ce rapport étudie la combinaison des techniques de checkpoint et de réplication pour l'exécution efficace et sûre de chaînes de tâches sur des plates-formes à grande échelle en présence d'erreurs fatales. . Ces deux techniques ont été étudiées séparément mais leur combinaison ouvre de nouvelles perspectives pour la minimisation du temps d'exécution dans des environnements sujets aux fautes. De plus, la combinaison des checkpoints et de la réplication n'a jamais été étudiée avec la présence de fautes fatales et silencieuses à la fois. Pour chaque tâche, on doit décider s'il faut la checkpointer et /ou s'il faut la répliquer. Nous proposons un algorithme de programmation dynamique de complexité quadratique en le nombre de tâches pour résoudre le problème, et montrons expérimentalement, via un jeu complet de simulations, dans quelles conditions les deux techniques, prises séparément ou combinées, peuvent améliorer les performances.

Mots-clés : checkpoint, réplication, HPC, erreur fatale, erreur silencieuse, chaîne de tâches

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 entire 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 considering linear workflows is to ensure their 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 errors [START_REF] Cappello | Toward Exascale Resilience[END_REF][START_REF] Cappello | Toward Exascale Resilience: 2014 update[END_REF]. Scale is the enemy here: even if each computing resource is very reliable, with, say, a Mean Time Between Errors (MTBE) of ten years, meaning that each resource will experience an error only every 10 years on average, a platform composed of 100, 000 of such resources will experience an error every fifty 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 errors are required to ensure a correct and uninterrupted execution of the application [START_REF] Lucas | Top ten exascale research challenges[END_REF]. To further complicate matters, several types of errors need to be considered when computing at scale. In addition to the classical fail-stop errors (such as hardware failures or crashes), silent errors (also known as silent data corruptions) constitute another threat that can no longer be ignored [START_REF] O'gorman | The effect of cosmic rays on the soft error rate of a DRAM at ground level[END_REF][START_REF] Ziegler | IBM experiments in soft fails in computer electronics[END_REF][START_REF] Ziegler | Accelerated testing for cosmic soft-error rate[END_REF][START_REF] Ziegler | Cosmic ray soft error rates of 16-Mb DRAM memory chips[END_REF][START_REF] Moody | Design, Modeling, and Evaluation of a Scalable Multi-level Checkpointing System[END_REF]. There are several causes of silent errors, such as cosmic radiation, packaging pollution, among others. Silent errors can strike the cache and memory (bit flips) components as well as the CPU operations; in the latter case they resemble floating-point errors due to improper rounding, but have a dramatically larger impact because any bit of the result, not only low-order mantissa bits, can be corrupted.

The standard approach to cope with fail-stop errors is checkpoint with 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 correctly executed. A checkpoint is simply a file including all intermediate results and associated data that is saved on a storage medium resilient to errors; 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 an error later 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 recomputing 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 an error strikes, there is a lot of re-execution involved, which calls for more frequent checkpoints. However, checkpointing incurs a significant overhead, and is a mere waste of resources if no error strikes. Altogether, there is a trade-off to be found, and one may want to checkpoint only carefully selected tasks.

While checkpoint/restart [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][START_REF] Elnozahy | A survey of rollbackrecovery protocols in message-passing systems[END_REF] is the de-facto recovery technique for addressing fail-stop errors, there is no widely adopted general-purpose technique to cope with silent errors. The challenge 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 address the problem of silent errors, many application-specific detectors, or verification mechanisms, have been proposed. We apply such a verification mechanism after each task in this paper. Our approach is agnostic of the nature of the verification mechanism (checksum, error correcting code, coherence test, etc.). In this context, if the verification succeeds, then the output of the task is correct, and one can safely either proceed to the next task directly, or save the result beforehand by taking a checkpoint. Otherwise, if verification fails we have to rollback to the last saved checkpoint and re-execute the work since that point on. However, and contrarily to fail-stop errors, silent errors do not cause the loss of the entire memory content of the affected processor. To account for this difference, we use a two-level checkpointing scheme: the checkpoint file is saved in the main memory of the processor before being transferred to some storage (disk) that is resilient to fail-stop errors. This allows for recovering faster after a silent error than after a fail-stop error.

Replication is a well-known, but costly, method to deal with both, fail-stop errors [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][START_REF] Casanova | On the impact of process replication on executions of large-scale parallel applications with coordinated checkpointing[END_REF][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] Elliott | Combining partial redundancy and checkpointing for HPC[END_REF][START_REF] Stearley | Does partial replication pay off?[END_REF] and silent errors [START_REF] Ni | ACR: Automatic Checkpoint/Restart for Soft and Hard Error Protection[END_REF][START_REF] Benoit | Identifying the right replication level to detect and correct silent errors at scale[END_REF]. While both checkpointing and replication have been extensively studied separately, their combination has not yet been investigated in the context of linear workflows, despite its promising potential to minimize the execution time in error-prone environments. 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 with a two-level checkpoint/recovery mechanism whose cost depends both on the number of processors executing the task, and on whether the task is replicated or not. • We address both fail-stop and silent errors. We perform a verification after each task to detect silent errors and recover from the last in-memory checkpoint after detecting one. We recover from the last disk checkpoint after a fail-stop error. If a task is replicated, we do not need to roll back and we can directly proceed to the next task, unless both replicas have been affected (by either error type). • 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 and silent 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 2 details the model and formalizes the objective function and the optimization problem. Section 3 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 proposed optimal dynamic programming algorithm is outlined in Section 4. The experimental validation is provided in Section 5. Finally, related work is discussed in Section 6, and the work is concluded in Section 7.

Model and objective

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

Application model

We target applications whose workflows represent linear chains of parallel tasks. More precisely, for one application, consider 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, w i , consists of a sequential fraction α i w i , 0 ≤ α i ≤ 1, and the remaining fraction (1α i )w i perfectly parallel. The (error-free) execution time, T i , using q i processors is thus

w i α i + 1-α i q i
. Without loss of generality, we assume that processors execute the tasks at unit speed, and we use 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 from a few minutes up to tens of minutes. In such frameworks, it may be worthwhile to replicate or to checkpoint tasks to mitigate the impact of errors.

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 and silent errors whose inter-arrival times follow an Exponential distribution. More precisely, let λ F ind be the fail-stop 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 ) = 1 -e -λ F ind T .
Similarly, let λ S ind be the silent error rate of each individual processor P i : the probability of having a silent error striking P i within T time-units is

P(Y ≤ T ) = 1 -e -λ S
ind T . Then, a computation on q ≤ p processors has an error rate qλ F ind for fail-stop errors, and qλ S ind for silent errors. The probability of having a fail-stop error within T time-units and with q processors becomes 1e -qλ F ind T (and 1e -qλ S ind T for a silent error) [START_REF] Hérault | Fault-Tolerance Techniques for High-Performance Computing, Computer Communications and Networks[END_REF].

Verification

To detect silent errors, we add a verification mechanism at the end of each task. This ensures that the error will be detected as soon as possible. The verification following task T i has a cost V i . We assume that the verification mechanism has a perfect recall (it detects all errors). This guarantees that all taken checkpoints are correct, because they are always preceded by a verification. Similarly, we assume that no silent error can strike during the verification.

The cost V i depends upon the detector and can thereby take a wide range of values. In this work, we adopt a quite general formula and use

V i (q i ) = u i + v i q i (1)
to model the cost of verifying task T i when executed with q i processors, where u i and v i denote the sequential and parallel cost of the verification, respectively. In the experiments (Section 5.2), we instantiate the model with two cases:

• We use u i = βw i and v i = 0, where β is a small parameter (around 1%). This means that the cost of the verification is proportional to the sequential cost w i of T i . It corresponds to the case of data-oriented kernels processing large files and checksumming for verification in a centralized location (hence sequentially) [START_REF] Benoit | Assessing general-purpose algorithms to cope with fail-stop and silent errors[END_REF].

• We use u i = 0 and v i = βw i . This means that the cost of the verification is proportional to the parallel fraction of T i . It corresponds to the same scenario as above, but where checksumming is performed in parallel on all enrolled processors.

Checkpointing

The output of each task T i can be checkpointed in time C i . We use a two-level checkpoint protocol where the checkpoint is first saved locally (memory checkpoint) before being transferred to a slower but reliable storage like a filesystem (disk checkpoint). The memory checkpoint will be lost when a fail-stop error strikes a processor (and its local data), whereas the disk checkpoint will always remain available to restart the application. When a fail-stop error strikes during the execution of T i , 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 D j+1 , which amounts to reading the disk checkpoint of task T j . When a silent error is detected at the end of T i by the verification mechanism, we also roll back to the last checkpointed task T j , but (i) we do not pay the downtime D; and (ii) the recovery cost is R M j+1 , which amounts to reading the memory checkpoint of task T j (hence at a much smaller cost than for a fail-stop error).

The checkpoint cost C i , and both recovery costs R D j+1 and R M j+1 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 (2)
to model the time to save a checkpoint after T i executed with q i processors. Here, a i + b i q i represents the I/O overhead to write the task output file M i to the storage medium. For in-memory checkpointing [START_REF] Zheng | FTC-Charm++: an in-memory checkpointbased fault tolerant runtime for Charm++ and MPI[END_REF], a i + b i q i is the communication time, in which a i denotes the latency to access the storage system; then we have b i q i = M i τnetq i , where τ net is the network bandwidth (each processor stores M i q i data items). For coordinated checkpointing to stable storage, there are two cases: if the I/O bottleneck is the storage system's bandwidth, then a i = β + M i τ io and b i = 0, where β is a start-up time and τ io is the I/O bandwidth; otherwise, if the I/O bottleneck is the network latency, 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 (from memory or from disk), we assume similar formulas:

R M i (q i ) = a M i + b M i q i + c M i q i ; R D i (q i ) = a D i + b D i q i + c D i q i . (3)
The coefficients depend on the type of recovery: again, a memory recovery is much faster than a disk recovery. If we further assume that reading and writing from/to the same storage medium (memory or disk) have same cost, we have

C i (q i ) = R D i+1 (q i ) + R M i+1 (q i )
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 D 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 ).

Replication

When executing a task, we envision two possibilities: either the task is not replicated, or it is replicated. To explain the impact of replication, we momentarily assume that we consider fail-stop errors only. Then we return to the scenario with both fail-stop and silent errors.

With fail-stop errors only, 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 an error strikes, and re-execute the entire 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 entire platform, hence with q i = p processors. Then we let E norep (i) denote the expected execution time of T i when accounting for errors. We attempt a first execution, which takes

T norep i = w i α i + 1-α i p if
no fail-stop error strikes. But if a fail-stop error does strike, we must account for the time that has been lost (between the beginning of the execution and the fail-stop error), then perform a downtime D, a recovery R i (p) (since we use the entire 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 3.

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

T rep i = w i α i + 1-α i p 2
, since each copy uses p 2 processors. If a fail-stop error strikes one copy, we proceed as before, account for the downtime D, recover (in time R i ( p 2 ) now), and restart execution with that copy. Then there are two cases: (i) if the second copy successfully completes its first execution, the fail-stop error has no impact and the execution time remains the same as the error-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 fail-stop error, the cost would be R i ( p 2 ). However, in the unlikely event where both copies are struck by a fail-stop error 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 5.1. 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 Drep i or R M rep i for the recovery costs (disk or memory) when T i is replicated, and R Dnorep i or R M 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

RR n°9235

Combining Checkpointing and Replication for Linear Workflows with Fail-Stop and Silent Errors8 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 3). We let E rep (i) denote the expected execution time of T i with replication and when accounting for fail-stop errors, when T i-1 is checkpointed. The derivation of E rep (i) is significantly more complicated than for E norep (i) and represents a new contribution of this work, detailed in Section 3.2.

We now detail the impact of replication when both fail-stop and silent errors can strike. First, we have to state how the verification cost V i of task T i depends upon whether T i is replicated or not. For the analysis, we keep a general model and let V rep i be the cost when T i is replicated, and V norep i when it is not. However, as explained later in the experimental evaluation (Section 5.2), we use two different instantiations of Equation ( 1), which directly give the two (possibly different) values of V rep i and V norep i as a function of parameter β. Next, consider again a task T i , and still assume for simplicity that the predecessor T i-1 of T i has been checkpointed. The impact of fail-stop errors is the same as before, and depends upon how many replicas of T i are executed. The only difference is that the failstop error can now strike either during the execution of a replica or during its verification. But if no fail-stop error strikes, we still have to perform the verification to detect a possible silent error, whose probability depends upon the error-free execution time of that replica. Recall that no silent error can strike during the verification (but a fail-stop can strike). If a silent error is detected, we have to re-execute the task, in which case we recover from the memory checkpoint instead of from the disk checkpoint.

Finally, we extend the definition of E norep (i) and E rep (i) to account for both fail-stop and silent errors, when T i-1 is checkpointed. We explain how to compute both quantities in Section 3.2.

Optimization problem

The objective of this work is to minimize the expected makespan of the linear workflow in the presence of fail-stop and silent errors. For each task, we have four choices: either we replicate the task or not, and either we checkpoint it or not. More formally, for each task T i we need to decide: (i) if it is checkpointed or not; and (ii) if it is replicated or not, (meaning that there are 4 n combinations for the whole workflow) with the objective to minimize the total execution time of the workflow. 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, for the scenario with fail-stop errors only (see Section 6 on related work for further references). Adding replication significantly 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 4.

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 an error strikes. We explain how to deal with the general case of re-executing a segment of tasks, some of them replicated, in Section 4. Here, 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][START_REF] Benoit | Assessing general-purpose algorithms to cope with fail-stop and silent errors[END_REF], but we present this case to help the reader follow the derivation in Section 3.2 for the case where T i is replicated, which is new and much more involved.

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 a fail-stop error strikes during the execution of the task and its verification (lasting

T norep i + V norep i
), and in this case we lose some work and need to re-execute the task, recovering from a disk checkpoint;

• Either there is no fail-stop error, and in this case the verification indicates whether there has been a silent error or not:

-If a silent error is detected, we need to re-execute the task right after the verification, recovering from a memory checkpoint;

-Otherwise the execution has been successful.

This leads to the following recursive formula:

E norep (i) = P(X p ≤ T norep i + V norep i ) T norep lost (T norep i + V norep i ) + D + R Dnorep i + E norep (i) + (1 -P(X p ≤ T norep i + V norep i )) T norep i + V norep i (4) + P(X p ≤ T norep i )(D + R M norep i + E norep (i)) ,
where P(X p ≤ t) is the probability of having a fail-stop error on one of the p processors before time t, i.e., P(X p ≤ t) = 1e -λ F ind pt , and P(X p ≤ t) is the probability of having a silent error on one of the p processors before time t, i.e., P(X p ≤ t) = 1e -λ S ind pt . The time lost when an error strikes is the expectation of the random variable X p , knowing that the error stroke before the end of the task and its verification. We compute it as follows:

RR n°9235

Combining Checkpointing and Replication for Linear Workflows with Fail-Stop and Silent Errors10

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

T norep lost (T norep i + V norep i ) = 1 λ F ind p - T norep i + V norep i e λ F ind p(T norep i +V norep i ) -1 . (5)
Replacing the left hand side term of Equation ( 5) in Equation ( 4) and solving, we derive:

E norep (i) = 1 λ F ind p + D + R Dnorep i e p((λ F ind +λ S ind )T norep i +λ F ind V norep i ) (6)
-

1 λ F ind p + (R Dnorep i -R M norep i ) e λ S ind pT norep i -(D + R M norep i ).
Recall that

T norep i = w i α i + 1-α i p
in Equation [START_REF] Benoit | Assessing general-purpose algorithms to cope with fail-stop and silent errors[END_REF]. Finally, if we decide to checkpoint T i , we simply add

C norep i to E norep (i).

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 a case analysis similar to that of Section 3.1:

• Either two fail-stop errors strike before the end of the task and its verification (lasting

T rep i + V rep i
), with one fail-stop error striking each copy. Then we have lost some work and need to re-execute the task from a disk checkpoint;

• Or at least one copy is not hit by any fail-stop error. Then we need to account for two different cases in the analysis:

-Both copies have survived: then we need to re-execute the task (recovering from a memory checkpoint) only if both copies are hit by a silent error.

-Only one replica survived: then we need to re-execute the task if this replica is hit by a silent error.

RR n°9235

Combining Checkpointing and Replication for Linear Workflows with Fail-Stop and Silent Errors11

This leads to the following formula:

E rep (i) = P(Y p ≤ T rep i + V rep i ) 2 T rep lost (T rep i + V rep i ) + D + R Drep i + E rep (i) + (1 -P(Y p ≤ T rep i + V rep i ) 2 )(T rep i + V rep i ) (7) + 2(1 -P(Y p ≤ T rep i + V rep i ))P(Y p ≤ T rep i + V rep i )P(Y p ≤ T rep i ) + (1 -P(Y p ≤ T rep i + V rep i )) 2 P(Y p ≤ T rep i ) 2 (D + R M rep i + E rep (i)),
where P(Y p ≤ t) is the probability of having an error on one replica of p 2 processors before time t, i.e., P(Y p ≤ t) = 1e -λ F ind p 2 t , and P(Y p ≤ t) is the probability of having a silent error on one replica of p 2 processors before time t, i.e., P(Y

p ≤ t) = 1 -e -λ S
ind p 2 t . The first line of Equation ( 7) corresponds to the case where both replicas are hit by a fail-stop error, the second line accounts for the time spent in case at least one replica survives. The last two lines correspond to the two cases when we need to re-execute the task after the detection of a silent error (one replica alive for line 3, two replicas alive for line 4 of Equation ( 7)).

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 + V rep i ) T rep i +V 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 + V rep i ) = (-2λ F ind p(T rep i +V rep i )-4)e - λ F ind p(T rep i +V rep i ) 2 +(λ F ind p(T rep i +V rep i )+1)e -λ F ind p(T rep i +V rep i ) +3 (e - λ F ind p(T rep i +V rep i ) 2 -1) 2 λ F ind p
.

(8) Replacing the left hand side term of Equation [START_REF] Bosilca | Unified model for assessing checkpointing protocols at extreme-scale[END_REF] in Equation ( 7) and solving, we get:

E rep (i) = - (4 + 2λ F ind p(R Drep i -R M rep i ))e p( λ F ind (T rep i +V rep i ) 2 +λ S ind T rep i ) (2e p λ F ind (T rep i +V rep i )+λ S ind T rep i 2 -1) • λ F ind p (9)
+ (1 + λ F ind p(R Drep i -R M rep i ))e λ S ind pT rep i (2e p λ F ind (T rep i +V rep i )+λ S ind T rep i 2 -1) • λ F ind p + (3 + λ F ind p(D + R Drep i ))e p(λ F ind (T rep i +V rep i )+λ S ind T rep i ) (2e p λ F ind (T rep i +V rep i )+λ S ind T rep i 2 -1) • λ F ind p -(D + R M rep i ) Recall that T rep i = w i α i + 1-α i p 2
in Equation [START_REF] Buneci | Qualitative Performance Analysis for Large-Scale Scientific Workflows[END_REF]. Finally, if we decide to checkpoint T i , we simply add

C rep i to E rep (i).

Optimal dynamic programming algorithm

In this section, we provide an optimal dynamic programming (DP) 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 Chains-RepCkpt will be given by min

T rep opt (n) + C rep n , T norep opt (n) + C norep n . ( 10
)
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 Drep 1 + T rep,rep N C (1, j), R Dnorep 1 + T norep,rep N C (1, j)                  (11)
In Equation [START_REF] Cappello | Toward Exascale Resilience: 2014 update[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 between T 1 and T j 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 ( 11) 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 ( 11), 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 ( 11), 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 experiencing an error.

Lines 3 and 4 apply to the case where T i is not replicated, with similar notation 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 ( 11): we include the cost to read the initial input, which depends whether T 1 is replicated (in line 5) or not (in line 6) of Equation [START_REF] Cappello | Toward Exascale Resilience: 2014 update[END_REF].

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

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 Drep 1 + T rep,norep N C (1, j), R Dnorep 1 + T norep,norep N C (1, j)                  (12)
To synthesize the notation, 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 an error 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 an error 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 an error during T j depends whether T j is replicated or not, and we need to restart from T i in case of error, 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 an error (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 -λ F ind p(T norep j +V norep j ) T norep lost (T norep j + V norep j ) + D + R D 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 -λ F ind p(T norep j +V norep j ) T norep j + V norep j + 1 -e -λ S ind pT norep j (D + R M A i + min T A,rep N C (i, j -1), T A,norep N C (i, j -1) + T A,norep (j | i))
.

The term in e - we pay a downtime and a memory 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)) from last checkpoint. When a fail-stop error strikes, we account for

T norep lost (T norep j + V norep j
), the time lost within T j , and whose value is given by Equation ( 5). Then we pay a downtime and a disk recovery (with a cost depending on A). Finally, we re-execute all the tasks from last checkpoint and that is similar to the previous case.

The formula is similar with replication of T j , where the probability of error accounts for the fact that we need to recover only if both replicas fail for the fail-stop errors and accounts for the number of living replicas in the case where a silent error is detected (see Section 3.2 for the details):

T A,rep (j | i) = 1 -e - λ F ind p(T rep j +V rep j ) 2 2 T rep lost (T rep j + V rep j ) + D + R D 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 - λ F ind p(T rep j +V rep j ) 2 2   T rep j + V rep j + (1 -e - λ F ind p(T rep j +V rep j )
2

)e - λ F ind p(T rep j +V rep j ) 2 (1 -e - λ S ind pT rep j 2 ) +e -λ F ind p(T rep j +V rep j ) (1 -e - λ S ind pT rep j 2 ) 2 D + R M A i + min T A,rep N C (i, j -1), T A,norep N C (i, j -1) + T A,rep (j | i) .
Note that the value of T rep lost (T rep j ) is given by Equation [START_REF] Bosilca | Unified model for assessing checkpointing protocols at extreme-scale[END_REF]. Overall, we need to compute the O(n 2 ) 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 ).

Experiments

In this section, we evaluate the advantages of adding replication to checkpointing in the presence of both, fail-stop and silent errors. We point out that the simulator that implements the proposed DP algorithm 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. The code is written in-house in C++ and does not use any library other than the STL.

We start by assessing scenarios with fail-stop errors only in Section 5.1. We first describe the evaluation framework in Section 5.1.1, then we compare checkpoint with replication to checkpoint only in Section 5.1.2. In Section 5.1.3, we assess the impact of the different model parameters on the performance of the optimal strategy. Finally, Section 5.1.4 compares the performance of the optimal solution to alternative sub-optimal solutions.

Then we assess scenarios with both fail-stop and silent errors in Section 5.2. We first describe the few modifications of the evaluation framework in Section 5.2.1, then we compare checkpoint with replication to checkpoint only in Section 5.2.2. Finally, Section 5.2.3 assesses the impact of the different model parameters on the performance of the optimal strategy.

Scenarios with fail-stop errors only

Experimental setup

We fix the total work in the chain to W = 10, 000 seconds. The choice of this value is less important than the duration of the tasks compared to the error rate. For this reason, we rely on five different work distributions, where all tasks are fully parallel (α i = 0):

• Uniform: every task i is of length w i = W n , i.e., identical tasks. • Increasing: the length of the tasks constantly increases, i.e., task T i has length

w i = i 2W n(n+1) .
• Decreasing: the length of the tasks constantly decreases, i.e., task T i has length w i = (ni + 1) 2W n(n+1) . • HighLow: the chain is formed by long tasks followed by short tasks. The long tasks represent 60% of the total work and there are n 10 such tasks. Short tasks represent the remaining 40% of the total work and consequently there are n -n 10 small tasks. • Random: task lengths are uniformly chosen 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 Dnorep , where 1 ≤ α ≤ 2, and we assess the impact of parameter α in Section 5.2.3. 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.

Comparison to checkpoint only

We start with an analysis of the solutions obtained by running the optimal dynamic programming (DP) algorithm ChainsRepCkpt on chains of 20 tasks for the five different work distributions described in Section 5.1.1. 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 fail-stop error rate λ F ind p from 10 -8 to 10 -2 . Note that when λ F 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 RR n°9235
Combining Checkpointing and Replication for Linear Workflows with Fail-Stop and Silent Errors16 task (hence b i = c i = 0) and varies from 10 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. As the optimal solution may or may not contain checkpoints and replicas, we distinguish 4 cases: 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, except when the error rate becomes very high. 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 fails-stop error rate λ F 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 low error rates and low checkpointing costs, only checkpoints are used, because their cost is lower than the average re-execution time in case of error. 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 fail-stop error rate λ F ind p to 10 -3 , which corresponds to the case highlighted by the red box in Figure 1. Figure 2 presents the optimal solutions obtained with the ChainsCkpt and ChainsRepCkpt algorithms for the Uniform, 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 in 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 instead taken every three tasks, 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 longest tasks are also checkpointed. A general rule of thumb is that replication only is preferred for short tasks while checkpointing and replication is reserved for longer tasks, where the probability of error 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 longer 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 shorter tasks by replicating them. In this scenario (high error rate and high checkpoint cost), this is clearly a winning strategy. The normalized expected makespan decreases with increasing n, as the corresponding number of tasks that are replicated increases almost linearly. The Chains-RepCkpt 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 an error, 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 long (60% of the total work), which greatly increases the probability of error and the associated re-execution cost.

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 fail-stop error rate λ F ind p on the performance. The ChainsRepCkpt algorithm improves the ChainsCkpt strategy for large values of λ F ind p: replication starts to be used for λ F ind p > 2.6 × 10 -4 and it reduces the makespan by ≈ 16% for λ F ind p = 10 -3 and by up to ≈ 40% when λ F 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 low 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

RR n°9235

Combining Checkpointing and Replication for Linear Workflows with Fail-Stop and Silent Errors19 cost is between 0.9 and 1.6 times the cost of one task, ChainsRepCkpt 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 non-replicated tasks α and we present the results for α = 1

(C rep i = R Drep i = C norep i = R Dnorep i ), α = 1.5 (C rep i = R Drep i = 1.5C norep i = 1.5R Dnorep i ) and α = 2 (C rep i = R Drep i = 2C norep i = 2R Dnorep 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 (shorter) 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, λ F 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 error rate values. However, when the term c i p becomes large in front of b i p , we see that ChainsRepCkpt is much better than ChainsCkpt, as the checkpointing costs tend to

RR n°9235

Combining Checkpointing and Replication for Linear Workflows with Fail-Stop and Silent Errors20 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).

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 fail-stop error rates λ F ind p under the Uniform work distribution. We show that the optimal solution with ChainsRep-Ckpt (highlighted by the green box) 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.

Scenarios with both fail-stop and silent errors

In this section we evaluate the power of replication in addition to checkpointing on platforms subject to both fail-stop and silent errors.

Experimental setup

All the model parameters are instantiated as before, with the following changes to account for the presence of silent errors. Unless stated otherwise, the fail-stop error rate has been set to 1.28e-3s -1 and the silent error rate has been set to 5.48e-3s -1 . The silent error rate has been computed from real measures [START_REF] Bautista-Gomez | Unprotected computing: A large-scale study of dram raw error rate on a supercomputer[END_REF]: we derived a non-corrected silent error rate per core of 5.48e-9s -1 . Similarly, the fail-stop error rate per core considered was 1.28e-9s -1 , which corresponds to a core lifetime of 25 years. Finally, we considered a platform of 1 million cores which tends to be the trend for current Top500 machines [42].

As for other parameters, we considered a verification cost of 1% of the corresponding task length. The cost of memory recovery was set to 5% of that of a disk recovery, considering an average between different measured values from [START_REF] Moody | Design, Modeling, and Evaluation of a Scalable Multi-level Checkpointing System[END_REF].

For simplicity, we assume that checkpointing costs are equal to the sum of the corresponding recovery costs, assuming that read and write operations take approximately the same amount of time, i.e., R

Dnorep i+1 + R M norep i+1 = C norep i .
For replicated tasks, we set RR n°9235

C rep i = αC norep i , R Drep i = αR Dnorep i and R M rep i = αR M norep i
, where 1 ≤ α ≤ 2, and we assess the impact of parameter α in Section 5.2.3. As in the previous section, 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.

Comparison to checkpoint only

We start with an analysis of the solutions obtained by running the optimal dynamic programming (DP) algorithm ChainsRepCkpt on chains with 20 tasks for the five different work distributions described in Section 5.1.1. 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 fail-stop error rate λ F ind p from 10 -8 to 10 -2 , without changing the silent error rate λ S ind . The disk checkpoint/recovery cost is constant per task and varies from 10 . In another experiment, we also make the silent error rate λ S ind p vary from 10 -8 to 10 -2 without changing the fail-stop error rate of 1.28e-3, with the same range for the checkpoint cost. s Figure 7 presents the results of these experiments for the Uniform distribution. The colors are the same as in Figure 1, with Checkpointing Only meaning that some tasks are checkpointed but no task is replicated and Checkpointing+Replication meaning that some tasks are checkpointed and some tasks are replicated. The left figure presents the results when the silent error rate is fixed but the fail-stop error rate varies. The right figure presents the results of the other experiment with a fixed fail-stop error rate and different silent error rates.

First, we observe that with silent errors, checkpointing becomes mandatory. Too many failures can strike during the execution, and checkpointing helps reducing the time spent on rollbacks and re-executions. However, as soon as the cost of a checkpoint exceeds the length of a task, replication becomes useful and this remains true even for low error rates. This holds for both fail-stop errors (left) and silent errors (right). There is one exception: when the fail-stop error rate is lower than 10 -5 and the checkpointing cost is less than twice the length of a task, checkpoints are sufficient and is replication is not needed. Replication is overall not needed under good conditions, however for our real setup, indicated by the red box, using both checkpointing and replication is a better solution. 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
), keeping λ F ind p = 1.28e-3 and λ S ind p = 5.48e-3, for the fail-stop and silent error rates, respectively, which corresponds to the case highlighted by the red box in Figure 7. Figure 8 presents the optimal solutions obtained with the ChainsCkpt and ChainsRep-Ckpt algorithms for the Uniform, Increasing, Decreasing, HighLow and Random work distributions, respectively. With two sources of errors, the solution is straightforward: almost every task must be checkpointed, with the exception of one (short) task for the Decreasing and Increasing distributions. However almost every task is also replicated

RR n°9235

Combining Checkpointing and Replication for Linear Workflows with Fail-Stop and Silent Errors24 (20 tasks out of 20 for the Uniform distribution compared to only 13 in the experiments of Section 5.1.2), showing once more that replication grants better protection to failures even if it increases the failure-free execution time. Checkpoints are being taken the same way as in our previous experiments: long tasks are systematically checkpointed while shorter tasks are either unprotected or replicated, as can be seen with the first tasks of the Increasing distribution and the last task of the Decreasing distributions. Figure 9 compares the performance of ChainsRepCkpt to the checkpoint-only strategy ChainsCkpt with fail-stop and silent errors. First, we observe that long tasks, being more likely to fail than shorter tasks, introduce a high overhead. As a consequence, with 20 tasks, the normalized makespan is too high and the execution of such applications is not possible, independently of the work distribution and the chosen checkpointing strategy. With more tasks however, the ChainsRepCkpt strategy always yield a shorter makespan compared to the ChainsCkpt strategy. For example, with 100 tasks, the normalized makespan obtained with the ChainsRepCkpt strategy is as high as ≈ 8.5 (and much more for the HighLow distribution), compared to ≈ 13 for ChainsCkpt. Indeed, with such high error rates, all tasks are replicated under the ChainsRepCkpt strategy, as can be seen on the right plot, but fewer tasks need to be be checkpointed (up to 50% fewer checkpoints with 100 tasks and the Uniform distribution).

The improvement is comparable to the 35% improvement observed with only fail-stop errors. Once again, replicated tasks tend to decrease the global probability of having an error, thus slightly reducing the number of checkpoints needed, while reducing the reexecution costs that can be very important with late-detected silent errors. Regarding the HighLow work distribution, we again observe a higher optimal expected makespan for both the ChainsCkpt and the ChainsRepCkpt strategies. Indeed, in this scenario, the first tasks are very long (60% of the total work), which greatly increases the error probability and the associated re-execution cost. Overall, for such applications on platforms subject to both, fail-stop and silent errors, replication appears to be mandatory and allows a reduction of the makespan of at least 30% if tasks are not too large (i.e. the probability of completing the task is not close to 1).

RR n°9235

Combining Checkpointing and Replication for Linear Workflows with Fail-Stop and Silent Errors25

Impact of error rate and checkpoint cost on the performance

Figure 10 shows the impact of four of the model parameters on the optimal expected normalized makespan of both ChainsCkpt and ChainsRepCkpt, using the Uniform distribution. First, we show the impact of the fail-stop error rate λ F ind p on the performance. The ChainsRepCkpt strategy always yields shorter makespans compared to the Chains-Ckpt strategy. All tasks are always replicated, reducing the probability of having an error for each task, and each task is also checkpointed. The normalized makespan for Chains-Ckpt is 19.5 for λ F ind p = 10 -5 , compared to 19.2 for ChainsRepCkpt, i.e. a reduction of only 1.7%, but this goes up to 50.3 for λ F ind p = 1.14e-3 compared to 35.2 when using replication, i.e. a reduction of 30%. The results are similar when we vary the silent error rate: when λ S ind p = 10 -5 , ChainsRepCkpt results in a normalized makespan of 4.60 compared to 5.55 with ChainsCkpt, i.e. a reduction of 17%, and this goes up to more than 30% when λ S ind p > 5 × 10 -3 . Then, we investigate the impact of the checkpointing cost with respect to the task length. The results are slightly different now that we have silent errors: ChainsCkpt and ChainsRepCkpt behave similarly only for small values of checkpoint cost. Chains-RepCkpt becomes better than ChainsCkpt for C ≥ 0.525, thus reducing the makespan obtained using only checkpoints. Both strategies yield a makespan that increases linearly with the checkpointing cost, however the ChainsRepCkpt strategy needs less checkpoints, and the makespan increases slower. This means that the costlier the checkpoints the better the improvement thanks to replication. Overall, the execution under the ChainsRepCkpt strategy is 1.17 times faster than ChainsCkpt for a checkpointing cost of 1.05T norep i , 1.66 times faster for a checkpoint cost of 3.15T norep i , and this goes up to 1.95 times faster when the checkpointing cost is 5.25T norep i . We now investigate the impact of the ratio α between the checkpointing and recovery cost for replicated tasks and non-replicated tasks and we present the results for α = 1, α = 1.5 and α = 2. 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 (shorter) tasks increases. As shown previously, when tasks are smaller, ChainsRepCkpt favors replication over checkpointing, especially when the checkpointing cost is high, which means fewer 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, λ F ind = 1.28 × 10 -9 , λ S ind = 5.48 × 10 -9 and we make p vary from 1000 to 2,000,000 (i.e., the error rates vary between 10 -6 and 10 -2 approximately). Figure 11 presents the results of the experiment using three different sets of values for a i , b i and c i . The trend is the same as previously with fail-stop errors: when b i increases and c i decreases, the advantage of using replication becomes less clear. However, on every plot, ChainsCkpt and ChainsRepCkpt grants the same makespan only when using a few cores. Every plot shows that, with the increasing number of cores on nowadays platforms, ChainsRepCkpt will behave better and better compared to ChainsCkpt. In particular, the improvement for each set of parameters (from left to right) is 69%, 30% and 0% for p = 500000, and is 76%, 60% and 16% for p = 1500000.

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 and silent errors.

Checkpointing

The de-facto general-purpose recovery technique in high-performance 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 rollbackrecovery 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 linear workflows, such as considered in the present work, the problem of finding the optimal checkpointing strategy, i.e., of determining which tasks to checkpoint, 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 error 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 twolevel 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 error using a local checkpoint stored on a partner node. If more than one error 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 errors 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.

Replication

As mentioned earlier, this work only considers task 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 error 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, Ferreira et al. [START_REF] Ferreira | Evaluating the viability of process replication reliability for exascale systems[END_REF] 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 error detection, consistent message ordering among replicas, etc.), and a set of experimental and simulation results. Thread-level replication has also been investigated [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 thread-level 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 and silent errors and minimize makespan.

Partial redundancy was also studied (in combination with coordinated checkpointing) to decrease the overhead of full replication [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 | Programmer-directed partial redundancy for resilient HPC[END_REF]. 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. In the present work, 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 only consider perfectly parallel applications while we investigate herein 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 with both, fail-stop and silent errors. In contrast, the present 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 combined 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.

Conclusion

In this work, we studied the combination of checkpointing and replication to minimize the execution time of linear workflows in environments prone to both fail-stop and silent errors. We introduced a sophisticated dynamic programming algorithm that solves the combined 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 was 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 checkpointing is costly and error rates are 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.

i

  and C norep i can be instantiated from Equation (2) and those of R Drep i , R Dnorep i , R M rep i and R M norep i can be instantiated from Equation (

  λ F ind p(T norep j +V norep j ) represents the case without fail-stop error, where the execution time is simply T norep j + V norep j . If a silent error is detected after the verification, RR n°9235

i+1 = C norep i .

 i For replicated tasks, we set C rep i = αC norep i and R Drep i = αR Dnorep i

  -3 T norep i to 10 3 T norep i . For replicated tasks, we set α = 1 in this experiment, i.e., C rep i

1

  .0 e -0 3 4 .0 e -0 3 1 .6 e -0 2 6 .4 e -0 2 2 .6 e -0 1 1 .0 e + 0 0 4 .1 e + 0 0 1 .6 e + 0 1 6 .6 e + 0 1 2 .6 e + 0 2 1 .0 e + 0 3 Checkpoint/Recovery cost over task length ratio 1

Figure 1 :

 1 Figure 1: Impact of checkpoint/recovery cost and error rate 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). Each color shows the presence of checkpoints and/or replicas in the optimal solution. Results corresponding to the case highlighted with a red square are presented in Figure 2.

T 2 T 4 T 6 T 8 T 20 CHAINSREPCKPT

 246820 10 T 12 T 14 T 16 T 18 T 20 CHAINSCKPT (Checkpointing Only) T 2 T 4 T 6 T 8 T 10 T 12 T 14 T 16 T 18 T 20 CHAINSREPCKPT (Checkpointing and Replication) (a) Uniform T 2 T 4 T 6 T 8 T 10 T 12 T 14 T 16 T 18 T 20 CHAINSCKPT (Checkpointing Only) T 2 T 4 T 6 T 8 T 10 T 12 T 14 T 16 T 18 T 20 CHAINSREPCKPT (Checkpointing and Replication) (b) Increasing T 2 T 4 T 6 T 8 T 10 T 12 T 14 T 16 T 18 T 20 CHAINSCKPT (Checkpointing Only) T 2 T 4 T 6 T 8 T 10 T 12 T 14 T 16 T 18 T 20 CHAINSREPCKPT (Checkpointing and Replication) (c) Decreasing T 2 T 4 T 6 T 8 T 10 T 12 T 14 T 16 T 18 T 20 CHAINSCKPT (Checkpointing Only) T 2 T 4 T 6 T 8 T 10 T 12 T 14 T 16 T 18 T 20 CHAINSREPCKPT (Checkpointing and Replication) (d) HighLow T 2 T 4 T 6 T 8 T 10 T 12 T 14 T 16 T 18 T 20 CHAINSCKPT (Checkpointing Only) T 2 T 4 T 6 T 8 T 10 T 12 T 14 T 16 T 18 T

Figure 2 :

 2 Figure 2: Optimal solutions obtained with the ChainsCkpt algorithm (top) and the ChainsRepCkpt algorithm (bottom) for the five work distributions.

  , 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 a fail-stop error rate of λ F 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 model 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 fail-stop error rates of λ F ind = 10 -4 (top), λ = 10 -3 (middle) and λ = 10 -2 (bottom) and for checkpointing costs of 0.5×T norep i

-3 T norep i to 10 3

 3 T norep i (hence, the memory checkpoint/recovery cost varies from 5 × 10 -5 T norep i to 50T norep i ). Overall, all checkpoints have a cost from 1.05 × 10 -3 T norep i to 1.05 × 10 3 T norep i as we always perform both types of checkpoints. For replicated tasks, we set α = 1 in RR n°9235 Combining Checkpointing and Replication for Linear Workflows with Fail-Stop and Silent Errors22 this experiment, i.e., C rep i

Figure 7 :

 7 Figure 7: Impact of checkpoint/recovery cost and error rates on the usage of checkpointing and replication. Total sequential work is fixed to 10, 000s and is distributed uniformly among n = 20 tasks (i.e., T 1 = T 2 = • • • = T 20 = 500s). Each color shows the presence of checkpoints and/or replicas in the optimal solution.

20 CHAINSREPCKPT

 20 CHAINSCKPT (Checkpointing Only)T 2 T 4 T 6 T 8 T 10 T 12 T 14 T 16 T 18 T 20 CHAINSREPCKPT (Checkpointing and Replication) (a) Uniform T 2 T 4 T 6 T 8 T 10 T 12 T 14 T 16 T 18 T 20 CHAINSCKPT (Checkpointing Only) T 2 T 4 T 6 T 8 T 10 T 12 T 14 T 16 T 18 T 20 CHAINSREPCKPT (Checkpointing and Replication) (b) Increasing T 2 T 4 T 6 T 8 T 10 T 12 T 14 T 16 T 18 T 20 CHAINSCKPT (Checkpointing Only) T 2 T 4 T 6 T 8 T 10 T 12 T 14 T 16 T 18 T 20 CHAINSREPCKPT (Checkpointing and Replication) (c) Decreasing T 2 T 4 T 6 T 8 T 10 T 12 T 14 T 16 T 18 T 20 CHAINSCKPT (Checkpointing Only) T 2 T 4 T 6 T 8 T 10 T 12 T 14 T 16 T 18 T 20 CHAINSREPCKPT (Checkpointing and Replication) (d) HighLow T 2 T 4 T 6 T 8 T 10 T 12 T 14 T 16 T 18 T 20 CHAINSCKPT (Checkpointing Only) T 2 T 4 T 6 T 8 T 10 T 12 T 14 T 16 T 18 T

Figure 8 :

 8 Figure 8: Optimal solutions obtained with the ChainsCkpt algorithm (top) and the ChainsRepCkpt algorithm (bottom) for the five work distributions.

  Uniform, Increasing, Decreasing, HighLow, Random distributions

Figure 9 :

 9 Figure 9: 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 a fail-stop error rate of λ F ind p = 1.28e-3, a silent error rate of λ S ind p = 5.48e-3 and a constant chekpointing/recovery cost C norep i

Figure 10 :

 10 Figure 10: Impact of fail-stop error rate λ F ind p (left), checkpoint cost (middle) and ratio α between the checkpointing cost for replicated task C rep i over non-replicated tasks C norep i

Figure 11 :

 11 Figure 11: Comparison of the ChainsCkpt and ChainsRepCkpt strategies for different numbers of processors, with different model parameter values for the checkpointing cost (a i , b i , c i ).

RR n°9235

Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

Acknowledgement

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


G Seniutinas

E Brasselet

A Bal Cytis

C David

S Juodkazis

Diamond: a gem for micro-optics

Seniutinas, G. (gediminas.seniutinas@psi.ch) Photonics have developed greatly over the last several decades and brought about a variety of new concepts in communica tions, sensing, solar energy and many other fields. With the emerging applications of quantum technologies and all optical data processing, the impact of photonics on technology is unde niable, as evidenced through the International Year of Light and Light based Technologies in 2015.

One of the key issues in the field is miniaturization and inte gration of photonic components, to enable light control at the microscale. Advancements in various fabrication techniques facilitate downscaling of optical elements; however, their design concepts need to be elaborated to keep the performance at the microscale. Metasurfaces and form birefringence structures have proved to be highly efficient for engineering arbitrary light fields [1,2]. Even though optical functionalities in these cases can be endowed by structuring materials on the subwavelength scale, the performance of components still highly depends on their material properties. Low absorption, high refractive index, high threshold of radiation damage, thermal stability, and high ther mal conductivity are greatly desired material features to reduce losses and assure stable performance over a broad range of oper ation conditions. All these properties are well combined in a material that has been admired for centuries diamond. Being extraordinarily hard and chemically inert, it withstands harsh environments and aging. The large bandgap makes diamond appear crystal clear and highly transparent from the UV to the far infrared bands. In addition, high refractive index at visible wavelengths and ultimate thermal conductivity set diamond apart from other available materials and make it compelling for optics and photonics [3,4]. Nonetheless, diamond is naturally an almost isotropic material, thus birefringence and optical func tionality must be created by shaping the material at the subwave length scale.

Diamond optical elements based on form birefringence have been successfully demonstrated for the infrared band, where microscale patterning resolution is sufficient to accommodate longer wavelengths. High efficiency annular groove phase masks for infrared light attenuation in a vortex coronagraph were pro duced using nanoimprinting and reactive ion etching techniques [START_REF] Forsberg | Proc. SPIE[END_REF]. Similar fabrication approaches were used making phase plates to control polarization in high power CO 2 lasers [START_REF] Forsberg | [END_REF]. Also, diamond optics has been developed to manipulate high inten sity X ray beams. It has been shown that diffractive elements made out of diamond can survive and keep their performance at high intensities even when used in a full beam of X ray free electron lasers [7]. Despite many advantages, however, the use of diamond for micro optics in the visible domain remained lim ited mainly because of the challenging fabrication. State of the art electron beam lithography offers sufficient patterning resolu tion of resist masks. Still, high resolution pattern transfer into diamond is complicated due to high aspect ratio structures required to induce necessary phase shift between different polar ization states of the incident light. Nonetheless, a robust nanofabrication process involving electron beam lithography and oxygen plasma etching has been recently developed to make X ray diffraction gratings [8]. We use a similar process to make subwavelength structures and establish micro optical elements operating throughout the entire visible spectrum. We also inves tigated direct focused ion beam writing to mill desired patterns directly into the diamond. Both techniques allow for production of diamond micro optics.

Due to the high refractive index of diamond, optical elements can be just a few micrometers in thickness, thus in our demon stration we used 5 mm thick chemical vapor deposition grown diamond membranes. Illustration of beam shaping capabilities of subwavelength structured diamond micro optical elements is made in the context of the generation of light beams carrying an arbitrary amount of orbital angular momentum per photon, so called vortex beams. Such beams find a variety of applications, for instance in optomechanics, optical communications, optical imaging, and quantum optics. These optical components rely on imprinting an azimuthal phase profile to an incident light beam via the geometrical features of space variant subwavelength grat ings. We used discrete set of domains that act as microscale bire fringent half wave plates for the considered wavelength, whose individual optical axis is prescribed by the grating orientation. The domains were arranged by following design rules described in Ref. [9]. The design exploits the coupling between the polar ization and spatial degrees of freedom of light, which refers to the spin orbit interaction of light. In practice, an incident circu larly polarized Gaussian beam is converted into a vortex beam carrying an orbital angular momentum defined by the structure of the micro optical element and the handedness of the incident polarization state. An example of such an element designed to operate at 1 mm wavelength is featured on the cover of this issue of Materials Today. The image shows scanning electron micro graph of a component enabling the generation of optical vortex beams with topological charge of 10 (i.e., the phase is exploring 20p over one full turn). The extension to any other wavelength is readily achieved by design, adapting the grating pitch, depth, and filling factor to the need. Our current diamond nanopattern ing processes enable fabrication of high aspect ratio gratings down to sub 100 nm period and opens up practical implementa tions of diamond micro optics in a variety of applications.

Acknowledgments

GS and CD acknowledge funding from the EU H2020 Research and Innova tion Program under Grant Agreement No. 654360 NFFA Europe. This work was performed in part at the Melbourne Centre for Nanofabrication (MCN) in the Victorian Node of the Australian National Fabrication Facility (ANFF) and partly supported by the Australian Research Council DP130101205 grant.

Further reading