George Bosilca

Aurélien Bouteiller

Elisabeth Brunet

Franck Cappello

Jack Dongarra

Amina Guermouche

Thomas Herault

Yves Robert

Dounia Zaidouni

Unified Model for Assessing Checkpointing Protocols at Extreme-Scale

Keywords: Fault-tolerance, checkpointing, coordinated, hierarchical, model, exascale

In this article, we present a unified model for several well-known checkpoint/restart protocols. The proposed model is generic enough to encompass both extremes of the checkpoint/restart space, from coordinated approaches to a variety of uncoordinated checkpoint strategies (with message logging). We identify a set of crucial parameters, instantiate them and compare the expected efficiency of the fault tolerant protocols, for a given application/platform pair. We then propose a detailed analysis of several scenarios, including some of the most powerful currently available HPC platforms, as well as anticipated Exascale designs. The results of this analytical comparison are corroborated by a comprehensive set of simulations. Altogether, they outline comparative behaviors of checkpoint strategies at very large scale, thereby providing insight that is hardly accessible to direct experimentation.

Un modèle unifié pour l'évaluation des protocoles de checkpoint à très large échelle

Résumé :

Nous présentons ici un modèle unifié de plusieurs protocoles de sauvegarde de points de reprise (checkpoints) et de redémarrage. Le modèle proposé est suffisamment générique pour contenir les deux extrêmes des techniques de checkpoint/restart, d'une approche coordonnée à toute une famille de stratégies non-coordonnées (avec enregistrement de messages).

Nous identifions un ensemble de paramètres cruciaux, les instancions et comparons l'espérance de l'efficacité des protocoles de tolérance aux pannes, pour un couple donné application/plate-forme. Nous proposons une analyse détaillée de plusieurs scénarios, incluant certaines des plates-formes de calcul existantes les plus puissantes, ainsi que des anticipations sur les futures plates-formes exascale. Les résultats de cette analyse sont corroborés par un ensemble de simulations. Ensemble, ces résultats illustrent le comportement relatif des différentes stratégies à large échelle, fournissant des enseignements qu'il serait très difficile, voire impossible, d'obtenir par l'expérimentation directe.

Mots-clés : Tolérance aux pannes, checkpoint, modèle, coordonné, hiérarchique, exascale

Introduction

A significant research effort is focusing on the outline, characteristics, features, and challenges of High Performance Computing (HPC) systems capable of reaching the Exaflop performance mark [START_REF] Dongarra | The international exascale software project: a call to cooperative action by the global high-performance community[END_REF][START_REF] Eesi | The European Exascale Software Initiative[END_REF][START_REF] Sarkar | Exascale software study: Software challenges in extreme scale systems[END_REF][START_REF] Ashby | The opportunities and challenges of exascale computing[END_REF]. The portrayed Exascale systems will necessitate, billion way parallelism, resulting in a massive increase in the number of processing units (cores), but also in terms of computing nodes. Considering the relative slopes describing the evolution of the reliability of individual components on one side, and the evolution of the number of components on the other side, the reliability of the entire platform is expected to decrease, due to probabilistic amplification. Executions of large parallel HPC applications on these systems will have to tolerate a higher degree of errors and failures than in current systems. Preparation studies forecast that standard fault tolerance approaches (e.g., coordinated checkpointing on parallel file system) will lead to unacceptable overheads at Exascale. Thus, it is not surprising that improving fault tolerance techniques is one of the main recommendations isolated by these studies.

In this paper we focus on techniques for tolerating the ultimate effect of detected and uncorrectable hard and soft errors: the crash of processes (undetected errors, also known as silent errors, are out-of-scope of this analysis). There are two main ways of tolerating process crashes, without undergoing significant application code refactoring: replication and rollback recovery. An analysis of replication feasibility for Exascale systems was presented in [START_REF] Ferreira | Evaluating the Viability of Process Replication Reliability for Exascale Systems[END_REF]. In this paper we focus on rollback recovery, and more precisely on the comparison of checkpointing protocols.

There are three main families of checkpointing protocols: (i) coordinated checkpointing; (ii) uncoordinated checkpointing with message logging; and (iii) hierarchical protocols mixing coordinated checkpointing and message logging. The key principle in all these checkpointing protocols is that all data and states necessary to restart the execution are regularly saved in process checkpoints. Depending on the protocol, theses checkpoints are or are not guaranteed to form consistent recovery lines. When a failure occurs, appropriate processes rollback to their last checkpoints and resume execution.

Each protocol family has serious drawbacks. Coordinated checkpointing and hierarchical protocols suffer a waste of computing resources when living processes have to rollback and recover from a checkpoint, to help tolerate failures. These protocols may also lead to I/O congestion when too many processes are checkpointing at the same time. Message logging increases the memory consumption, the checkpointing time, and slows-down the failure-free execution when messages are logged. Our objective is to identify which protocol delivers the best performance for a given application on a given platform. While several criteria could be considered to make such a selection, we focus on the most widely used metric, namely, the expectation of the total parallel execution time.

Fault-tolerant protocols have different overheads in fault-free and recovery situations. These overheads depend on many factors (type of protocols, application characteristics, system features, etc.) that introduce complexity and limit the scope of experimental comparisons as they have been done several times in the past [START_REF] Bouteiller | MPICH-V: a multiprotocol fault tolerant MPI[END_REF][START_REF] Rao | Egida: An extensible toolkit for low-overhead fault-tolerance[END_REF]. In this paper, we approach the fault tolerant protocol comparison from an analytical perspective. Our objective is to provide a valid performance model covering the most suitable rollback recovery protocols for HPC executions. Our model captures many optimizations proposed in the literature, and can be used to explore the effects of novel optimizations, and highlight the critical parameters to be considered when evaluating a protocol. The main contributions of this paper are:

1. to provide a comprehensive model that captures many consistent rollback recovery protocols, including coordinated checkpoint, uncoordinated checkpoint, and the composite hierarchical hybrids; 2. to provide a closed-form formula for the waste of platform computing resources incurred by each checkpointing protocol. This formula is the key to assessing existing and new protocols, and constitutes the first tool that can help the community to compare protocols at very large scale, and to guide design decisions for given application/platform pairs; 3. to instantiate the model on several realistic scenarios involving state-ofthe-art platforms, and future Exascale ones, thereby providing practical insight and guidance. The rest of this paper is organized as follows. Section 2 details the characteristics of available rollback recovery approaches, and the tradeoff they impose on failure-free execution and recovery. We also briefly discuss related work in this section. In Section 3, we describe our model that partially unifies coordinated rollback recovery approaches, and effectively captures coordinated, partially and totally uncoordinated approaches as well as many of their optimizations. We then use the model to analytically assess the performance of rollback recovery protocols. We instantiate the model with realistic scenarios in Section 4, and we present case-study results in Section 6, before concluding and presenting perspectives.

Rollback Recovery Strategies

Rollback recovery addresses permanent (fail-stop) process failures, in the sense that a process reached a state where either it cannot continue for physical reasons or it detected that the current state has been corrupted and further continuation of the current computation is worthless. In order to mitigate the cost of such failures, processes save their state on persistent memory (remote node, disk, ...) by taking periodic checkpoints. When the state of a process is altered by a failure, a replacement resource is allocated, and a previous state of the process can be restored from a checkpoint. Clearly, to minimize the amount of lost computation, the checkpoint must be as close as possible to the failure point.

In a distributed system, many inter-dependent processes participate in the computation, and a consistent global state of the application not only captures the state of each individual process, but also captures the dependencies between these states carried by messages [START_REF] Chandy | Distributed snapshots : Determining global states of distributed systems[END_REF]. In the context of checkpoint-based rollback recovery, the state of processes after some have reloaded from a checkpoint forms the recovery line. Any message altering the deterministic behavior of the application, and crossing a recovery line, must be available for restarted processes, in order to maintain a consistent global state. Protocols taking checkpoints without a guarantee of consistency are subject to the domino effect, and may lead to a restart of the execution from the beginning. Such protocols are excluded from this study.

Ensuring a consistent recovery can be achieved by two approaches, whose key difference is the level of coordination imposed on the recovery procedure. On one extreme, coordinating checkpoints, where after a failure, the entire application rolls back to a known consistent global state. On the opposite extreme, only the failed process rolls back to a checkpoint, in which case the recovery line must be augmented with additional information in order to avoid inconsistent dependencies during the re-execution phase, a method known as message logging [START_REF] Rao | The cost of recovery in message logging protocols[END_REF]. Recent advances in message logging [START_REF] Bouteiller | Correlated set coordination in fault tolerant message logging protocols[END_REF][START_REF] Guermouche | HydEE: Failure Containment without Event Logging for Large Scale Send-Deterministic MPI Applications[END_REF][START_REF] Esteban Meneses | Team-based message logging: Preliminary results[END_REF] have led to composite algorithms, called hierarchical checkpointing, capable of partial coordination of checkpoints while retaining message logging capabilities to remove the need for a global restart.

The goal of the model presented in this paper, is to capture the largest possible spectrum of checkpointing techniques, in order to propose a holistic description of all viable approaches. Based on this unified model, an assessment between the different classical techniques can be made, allowing for a deeper understanding of the advantages and drawbacks of each particular approach.

Coordinated Checkpointing

Several algorithms have been proposed to coordinate checkpoints, the most commonly used being the Chandy-Lamport algorithm [START_REF] Chandy | Distributed snapshots : Determining global states of distributed systems[END_REF]. The main requirement to form a globally consistent recovery line, characterized by the absence of intransit messages at the checkpoint line, is often implemented by completely silencing the network during checkpoint phases [START_REF] Plank | Efficient Checkpointing on MIMD Architectures[END_REF]. Coordinated algorithms possess the advantage of having almost no overhead outside of checkpointing periods, but require that every process, even if unaffected by failures, rolls back to its last checkpoint, as only this recovery line is guaranteed to be consistent. Arguably, the checkpoint and the recovery are costly operations, increasing the strain on the I/O subsystem.

Message Logging

Message Logging is a family of algorithms that provide a consistent recovery strategy from checkpoints taken at independent dates and without rolling back the surviving processes, a feature expected to increase resilience to adverse failure patterns [START_REF] Bouteiller | MPICH-V: a multiprotocol fault tolerant MPI[END_REF]. As the recovery line includes the arbitrary state of processes that do not rollback to a checkpoint, the restarted processes must undergo a directed replay, in order to reach a state that is part of a consistent global state. Such a replay requires two supplementary bits of information, not captured by the traditional process checkpoint: 1) the Event log, which contains the outcome of all nondeterministic events that happened during the lost computation; and 2) the Payload log, which enables replaying reception of messages sent to restarted processes before the recovery line.

Payload copy can be highly optimized; in particular, the sender-based approach [START_REF] Rao | The cost of recovery in message logging protocols[END_REF] permits the payload copy operation to be completely overlapped with the send operation itself. However, this extra data becomes part of the process checkpoint, and hence the amount of data to be stored on stable storage directly depends on the communication intensity of the application. On the other side, the fact that the recovery is a directed replay, rather than a complete coordinated restart, conveys two potential benefits. During the replay, message receptions are immediately available from the log and emissions are mostly discarded, hence the communication overhead is greatly reduced. As a result the replay of processes restarted from checkpoint may progress faster than the original execution [START_REF] Bouteiller | MPICH-V: a multiprotocol fault tolerant MPI[END_REF]. Second, as the failure recovery is constrained to processes directly impacted, other processes may continue to progress concurrently with the recovery, until they need to interact with one of the replaying processes. However, it can be argued that for tightly coupled applications, very little computation is completed before depending (transitively) on a replaying process.

Hierarchical Checkpointing

Hierarchical checkpointing protocols are a recent refinement of fault tolerant protocols, gathering advantages from both coordinated checkpointing and message logging while minimizing the drawbacks. They are designed to avoid the global restart associated with coordinated checkpointing while drastically limiting the volume of message to log compared to message logging protocols [START_REF] Bouteiller | Correlated set coordination in fault tolerant message logging protocols[END_REF][START_REF] Esteban Meneses | Team-based message logging: Preliminary results[END_REF][START_REF] Guermouche | HydEE: Failure Containment without Event Logging for Large Scale Send-Deterministic MPI Applications[END_REF]. These hierarchical schemes partition the processes of the application in groups, based on heuristics such as network proximity or communication intensity. Each group checkpoints independently, but processes belonging to the same group coordinate their checkpoints (and recovery), in order to spare some of the payload log. Communications between groups continue to incur payload logging. However, because processes belonging to a same group follow a coordinated checkpointing protocol, the payload of messages exchanged between processes of the same group is not needed during replay.

The optimizations driving the choice of the size and shape of groups are varied. A simple heuristic is to checkpoint as many processes as possible, simultaneously, without exceeding the capacity of the I/O system. In this case, groups do not checkpoint in parallel. Groups can also be formed according to hardware proximity and communication patterns. In such approaches, there may be opportunity for several groups to checkpoint concurrently. Without loss of generality, we consider that all groups of the application enter their checkpoint phase in turn, thus making the whole execution appear as a parallel work phase, followed by a checkpointing phase made of a sequence of checkpoints. The model we propose captures the intricacies of these grouping strategies, and we instantiate a variety of meaningful scenarios in Section 4.

Related work

The study of the optimal period of checkpoint for sequential jobs (or parallel jobs checkpointed in a coordinated way) has seen many studies presenting different order of estimates: see [START_REF] Young | A first order approximation to the optimum checkpoint interval[END_REF][START_REF] Daly | A higher order estimate of the optimum checkpoint interval for restart dumps[END_REF], and [START_REF] Ling | A variational calculus approach to optimal checkpoint placement[END_REF][START_REF] Ozaki | Distribution-free checkpoint placement algorithms based on min-max principle[END_REF] that consider weibull distributions, or [START_REF] Bougeret | Checkpointing strategies for parallel jobs[END_REF] that considers parallel jobs. The selection of the optimal checkpointing interval is critical to extract the best performance of any rollback-recovery protocol. However, although we use the same approach to find the optimal checkpoint interval, we focus our study on the comparison of different protocols that were not captured by the models these works considered.

The literature proposes different works as [START_REF] Plank | Processor allocation and checkpoint interval selection in cluster computing systems[END_REF][START_REF] Jin | Optimizing HPC Fault-Tolerant Environment: An Analytical Approach[END_REF][START_REF] Wang | Modeling Coordinated Checkpointing for Large-Scale Supercomputers[END_REF][START_REF] Oldfield | Modeling the impact of checkpoints on next-generation systems[END_REF][START_REF] Zheng | Reliability-aware scalability models for high performance computing[END_REF] on the modeling of coordinated checkpointing protocols. [START_REF] Bouguerra | Complexity Analysis of Checkpoint Scheduling with Variable Costs[END_REF] focus on refining failures prediction; [START_REF] Jin | Optimizing HPC Fault-Tolerant Environment: An Analytical Approach[END_REF], and [START_REF] Plank | Processor allocation and checkpoint interval selection in cluster computing systems[END_REF] focus on the optimized uses of the available resources: some may be kept in backup in order to replace the down ones and others may be even shutdown in order to decrease the failure risk or to prevent storage consumption by saving less checkpoints snapshots. [START_REF] Zheng | Reliability-aware scalability models for high performance computing[END_REF] proposes a scalability model where they compare the impact of failures on application performance with and without coordinated checkpointing. The major difference with these works lays in the unified model for coordinated and hierarchical protocols, and the inclusion of more parameters (like recovery of the checkpoint transfer cost with overlapping computation), refinning the model.

More scare papers present the modeling of uncoordinated or hierarchical checkpointing. [START_REF] Wu | Performance under failures of high-end computing[END_REF] models a periodic checkpointing on fault-aware parallel tasks that do not communicate. From our point of view, this specificity does not match the uncoordinated checkpointing with message logging we consider. In this paper, the three families of checkpointing protocols are targeted : the coordinated, the uncoordinated and the hierarchical ones. To the best of our knowledge, it is the first attempt at providing a unified model for this large spectrum of protocols.

Model and Analytical Assessment

In this section, we formally state the unified model, together with the closedform formula for the waste optimization problem. We start with the description of the abstract model (Section 3.1). Processors are partitioned into G groups, where each group checkpoints independently and periodically. To help follow the technical derivation of the waste, we start with one group (Section 3.2) before tackling the general problem with G ≥ 1 groups (Section 3.3). We even deal with a simplified model with G ≥ 1 before tackling the fully general model, which requires three additional parameters (pay-load overhead, faster execution replay after a failure, and increase in checkpoint size due to message logging). We end up with a complicated formula that characterizes the waste of resources due to checkpointing. This formula can be instantiated to account for all the checkpoint protocols described in Section 2, see Section 4 for examples. Note that in all scenarios, we model the behavior of tightly coupled applications, meaning that no computation can progress on the entire platform as long as the recovery phase of a group with a failing processor is not completed.

Abstract model

In this section, we detail the main parameters of the model. We consider an application that executes on p total processors subject to failures.

Units-To avoid introducing several conversion parameters, we instantiate all the parameters of the model in seconds. The failure inter-arrival times, the durations of a downtime, checkpoint, or recovery are all expressed in seconds. Furthermore, we assume (without loss of generality) that one work unit is executed in one second, when all processors are computing at full rate. One work-unit may correspond to any relevant application-specific quantity. When a processor is slowed-down by another activity related to fault-tolerance (writing checkpoints to stable storage, logging messages, etc.), one work-unit takes longer than a second to complete.

Failures and MTBF-The platform consists of p total identical processors. We use the term "processor" to indicate any individually scheduled compute resource (a core, a socket, a cluster node, etc) so that our work is agnostic to the granularity of the platform. These processors are subject to failures. Exponential failures are widely used for theoretical studies, while Weibull or log-normal failures are representative of the behavior of real-world platforms [START_REF] Heath | Improving cluster availability using workstation validation[END_REF][START_REF] Schroeder | A large-scale study of failures in highperformance computing systems[END_REF][START_REF] Liu | An optimal checkpoint/restart model for a large scale high performance computing system[END_REF][START_REF] Heien | Modeling and tolerating heterogeneous failures in large parallel systems[END_REF]. The mean time between failures of a given processor is a random variable with mean (MTBF ) µ (expressed in seconds). Given the MTBF of one processor, it is difficult to compute, or even approximate, the failure distribution of a platform with p total processors, because it is the superposition of p total independent and identically distributed distributions (with a single processor). However, there is an easy formula for the MTBF of that distribution, namely µ p = µ p total . In our theoretical analysis, we do not assume to know the failure distribution of the platform, except for its mean value (the MTBF). Nevertheless, consider any time-interval I = [t, t + T ] of length T and assume that a failure strikes during this interval. We can safely state that the probability for the failure to strike during any sub-interval [t , t + X] ⊂ I of length X is X T . Similarly, we state that the expectation of the time m at which the failure strikes is

m = t + T 2 .
Neither of these statements rely on some specific property of the failure distribution, but instead are a direct consequence of averaging over all possible interval starting points, that will correspond to the beginning of checkpointing periods, and that are independent of failure dates.

Tightly-coupled application-We consider a tightly-coupled application executing on the p total processors. Inter-processor messages are exchanged throughout the computation, which can only progress if all processors are available. When a failure strikes some processor, the application is missing one resource for a certain period of time, the downtime. Then, the application recovers from the last checkpoint (recovery time) before it re-executes the work done since that checkpoint and up to the failure. Under a hierarchical scenario, the useful work resumes only when the faulty group catches up with the overall state of the application at failure time. Many scientific applications obey to the previous scheme. Typically, the tightly-coupled application will be an iterative application with a global synchronization point at the end of each iteration. However, the fact that inter-processor information is exchanged continuously or at given synchronization steps (as in BSP-like models [START_REF] Valiant | A bridging model for parallel computation[END_REF]) is irrelevant: in steady-state mode, all processors must be available concurrently for the execution to actually progress. While the tightly-coupled assumption may seem very constraining, it captures the fact that processes in the application depend on each other, and progress can be guaranteed only if all processes are present to participate to the computation.

Blocking or non-blocking checkpoint-There are various scenarios to model the cost of checkpointing, so we use a very flexible model, with several parameters to instantiate. The first question is whether checkpoints are blocking or not. In some architectures, we may have to stop executing the application before writing to the stable storage where checkpoint data is saved; in that case checkpoint is fully blocking. In other architectures, checkpoint data can be saved on the fly into a local memory before the checkpoint is sent to the resilient disk,while computation can resume progress; in that case, checkpoints can be fully overlapped with computations. To deal with all situations, we introduce a slow-down factor α: during a checkpoint of duration C, the work that is performed is αC work units, instead of C work-units if only computation takes place. In other words, (1 -α)C work-units are wasted due to checkpoint jitter perturbing the progress of computation. Here, 0 ≤ α ≤ 1 is an arbitrary parameter. The case α = 0 corresponds to a fully blocking checkpoint, while α = 1 corresponds to a fully overlapped checkpoint, and all intermediate situations can be represented.

Periodic checkpointing strategies-For the sake of clarity and tractability, we focus on periodic scheduling strategies where checkpoints are taken at regular intervals, after some fixed amount of work-units have been performed. This corresponds to an infinite-length execution partitioned into periods of duration T . We partition T into T = W + C, where W is the amount of time where only computations take place, while C corresponds to the amount of time where checkpoints are taken. The total amount of work units that are executed during a period of length T is thus Work = W + αC (recall that there is a slow-down due to the overlap). In a failure-free environment, the waste of computing resources due to checkpointing is (see Figure 1):

Waste = T -Work T = (1 -α)C T (1)
As expected, if α = 1 there is no overhead, but if α < 1 (actual slowdown, or even blocking if α = 0), checkpointing comes with a price in terms of performance degradation.

For the time being, we do not further quantify the length of a checkpoint, which is a function of several parameters. Instead, we proceed with the abstract model. We envision several scenarios in Section 4, only after setting up the formula for the waste in a general context.

Processor groups-As described above, we assume that the platform is partitioned into G groups of same size. Each group contains q processors (hence p total = Gq). For the sake of the presentation, we first compute the waste when G = 1 before discussing the case where G ≥ 1. When G = 1, we speak of a coordinated scenario, and we simply write C, D and R for the duration of a checkpoint, downtime and recovery. When G ≥ 1, we speak of a hierarchical scenario. Each group includes q processors and checkpoints independently and sequentially in time C(q). Similarly, we use D(q) and R(q) for the durations of the downtime and recovery. Of course, if we let G = 1 in the (more general) hierarchical scenario, we retrieve the value of the waste for the coordinated scenario. As already mentioned, we derive a general expression for the waste for both scenarios, before further specifying the values of C(q), D(q), and R(q) as a function of q and the various architectural parameters under study.

Waste for the coordinated scenario (G = 1)

The goal of this section is to compute a formula for the expected waste in the coordinated scenario where G = 1. Recall that the waste is the fraction of time that the processors do not compute at full rate, either because they are checkpointing, or because they recover from a failure. Recall too that we write C, D, and R for the checkpoint, downtime, and recovery using a single group of p total processors. We obtain the following equation for the waste, which we explain below, and illustrate with Figures 2 and3:

Waste coord = (1 -α)C T (2) + 1 µ p T -C T R + D + αC + T -C 2 (3) + 1 µ p C T R + D + αC + T -C + C 2 (4)
• (2) is the portion of the execution lost in checkpointing, even during a fault-free execution, see Equation (1).

• (3) is the overhead of the execution time due to a failure during a work interval (see Figure 2). D+R is the duration of the downtime and recovery.

We add the time needed to re-execute the work that had already completed during the period, and that has been lost due to the failure. First, we need to re-execute the work done in parallel with the last checkpoint (of duration C). This takes a time αC since no checkpoint activity is taking place during that replay. Then we re-execute the work done in the workonly area, which had a duration of T lost . On average, the failure happens in the middle of the interval of length T -C, hence the term T lost has expected value

T lost = T -C 2 .
The previous quantity is weighted by its probability: when a fault occurs, it occurs during the work period with probability (T -C)/T . Finally, this execution overhead occurs each time a fault occurs, that is, on average, once every µ p .

• (4) is the overhead due to a failure during a checkpoint (see Figure 3).

The reasoning is similar. Just as before, we re-execute the work done in parallel with the previous checkpoint (of duration αC), then the work done in the work-only area (of duration T -C), and finally the work done during the checkpoint (of duration T lost as it is re-executed while checkpoints are taken). In expectation, T lost = C/2. We weight with the probability of the event, now equal to C/T .

After simplification of Equations ( 2) to (4), we get:

Waste coord = (1 -α)C T + 1 µ p D + R + T 2 + αC (5)
We point out that Equation ( 5) is valid only when T µ p : indeed, we made a first-order approximation when implicitly assuming that we do not have more than one failure during the same period. In fact, the number of failures during a period of length T can be modeled as a Poisson process of parameter T µp ; the probability of having k ≥ 0 failures is

1 k! ( T µp ) k e -T
µp . Hence the probability of having two or more failures is π

= 1 -(1 + T µp )e -T
µp . Enforcing the constraint T ≤ 0.1µ p leads to π ≤ 0.005, hence a valid approximation when bounding the period range accordingly.

In addition to the previous constraint, we must enforce the condition C ≤ T , by construction of the periodic checkpointing policy. Without the constraint C ≤ T ≤ 0.1µ p , the optimal checkpointing period T * that minimizes the expected waste in Equation ( 5) is T * = 2µ p C(1 -α). However, this expression for T * (which is known as Young's approximation [START_REF] Young | A first order approximation to the optimum checkpoint interval[END_REF] when α = 0) may well be out of the admissible range. Finally, note that the optimal waste may never exceed 1, since it represents the fraction of time that is "wasted". In this latter case, the application no longer makes progress.

Waste for the hierarchical scenario (G ≥ 1)

In this section, we compute the expected waste for the hierarchical scenario. We have G groups of q processors, and we let C(q), D(q), and R(q) be the duration of the checkpoint, downtime, and recovery for each group. We assume that the checkpoints of the G groups take place in sequence within a period (see Figure 4). We start by generalizing the formula obtained for the coordinated scenario before introducing several new parameters to the model.

Generalizing previous scenario with G ≥ 1

We obtain the following intricate formula for the waste, which we explain term by term below, and illustrate with Figures 4 to 7:

Waste hierarch = T -Work T + 1 µ p D(q) + R(q) + Re-Exec (6)
Work = T -(1 -α)GC(q) (7) Re-Exec = T -GC(q) T 1 G G g=1 (G-g+1)αC(q) + T -GC(q) 2 (8) + GC(q) T 1 G 2 G g=1 (9) g-2 s=0
(G -g + s + 2)αC(q) + T -GC(q) (10)

+ GαC(q) + T -GC(q) + C(q) 2 (11) + G-g s=1 (s + 1)αC(q) ( 12
)
• The first term in Equation ( 6) represents the overhead due to checkpointing during a fault-free execution (same reasoning as in Equation ( 1)), and the second term the overhead incurred in case of failure. Failures strike every µ p seconds on average; each of them induces a downtime of duration D(q), a recovery of duration R(q), and the re-execution of some amount of work, which is captured in the term Re-Exec.

• (7) provides the amount of work units executed within a period of length T , namely T -GC(q) at full speed, and αGC(q) during the G checkpoints.

RR n°7950

Note that when given a group checkpoints, all groups endure the same slowdown, because the application is tightly-coupled and can only progress at the pace of the slowest resource.

• (8) represents the time needed for re-executing the work when the failure happens in a work-only area, i.e., during the first T -GC(q) seconds of the period. Thanks to message-logging, only the failing group must rollback and re-execute some work. The re-execution time depends upon the group which is hit by the failure, and we average over all groups: see Figure 4. If the failure hits group g, where 1 ≤ g ≤ G, then we need to re-execute the work done in parallel with the last checkpoint of all groups following g, including itself. There are G -g + 1 such groups, hence the term (G -g + 1)αC(q). Just as for the coordinated approach, note that the work that has been executed in time (G -g + 1)C(q) is now re-executed faster, since no checkpoint activity is taking place during that replay. Then, on average, the failure happens in the middle of the interval of length T -GC(q), hence the term T lost has expected value

T lost = T -GC(q) 2
. The total time needed for re-execution is then weighted by the probability for the failure to happen during the work-only area, namely T-GC(q) T .

• (9) deals with the case where the fault happens during a checkpoint, i.e.

during the last GC(q) seconds of the period (hence the first term that represents the probability of this event). There are G 2 cases to average upon. Indeed, assume that the failure hits group g, where 1 ≤ g ≤ G.

The failure took place while one of the G groups was checkpointing. We distinguish three cases, depending upon whether the latter group is a group preceding g, group g itself, or a group following g.

- [START_REF] Bouteiller | Correlated set coordination in fault tolerant message logging protocols[END_REF] is for the case when the fault happens before the checkpoint of group g. More precisely, see Figure 5: there are s groups that have completed their checkpoints, and the failure took place during the checkpoint of group s + 1, where 0 ≤ s ≤ g -2. The amount of wasted time is ∆-T , with the notations of the figure, and is explained as follows: (i) the work done in parallel with the last checkpoint of all groups following g, including g itself, which amounts to (G -g + 1)αC(q), just as before; (ii) the work done during the first T -GC(q) seconds of the period; and (iii) the work done while the s + 1 first groups were checkpointing, re-executed faster, namely in time (s + 1)αC(q). Note that we do not need to take the expected value of the term T lost (which is C(q) 2 ), because terms cancel in the equation, as shown in the figure. Note also that we assume that the downtime of the struck group starts after the end of the current checkpoint (by group s + 1), while some (short) overlap might be possible in theory.

- [START_REF] Guermouche | HydEE: Failure Containment without Event Logging for Large Scale Send-Deterministic MPI Applications[END_REF] is for the case when the fault happens during the checkpoint of group g, see Figure 6. This case is quite similar to the previous case, and we retrieve the quantity (G -g + 1)αC(q) + (T -GC(q)) + (s + 1)αC(q), with s = g -1. As outlined in the figure, in contrast with the previous case, the faulty group is the one that is currently checkpointing: instead of re-executing the corresponding work at a faster rate, we have lost half of the checkpoint duration: the expectation of [START_REF] Esteban Meneses | Team-based message logging: Preliminary results[END_REF] is the case when the fault happens after the checkpoint of group g, during the checkpoint of group g + s, where g + 1 ≤ g + s ≤ G. See Figure 7: in this last case, the incurred overhead is much smaller.

T lost is C(q) 2 . - (
Because the failure took place after the checkpoint of group g, we only re-execute, at a faster rate, the work that was done during the checkpoints of groups g to g + s, which amounts to a time ((g + s)g + 1)αC(q). Note that we made the same simplification as for case [START_REF] Bouteiller | Correlated set coordination in fault tolerant message logging protocols[END_REF], assuming no overlap between the downtime and the end of the current checkpoint.

T α(G-g+1)C D R G.C T -G.C -T lost T lost T lost G 2 G 4 G g G 1
α(s.C + T lost ) R (G-s-1)C α(C -T lost ) T -G.C (G-g+1)C α(G-g+1)C D C -T lost T lost s.C T -G.C G 2 G g G 3 G 1
α(g -1)C (G-g)C C -T lost T lost T -G.C α(G-g+1)C R D T lost (g -1)C (G-g+1)C T -G.C G 2 G g G 3 G 1 G 5
Re-executing slowed-down work Recovery time Downtime After simplification (using a computer algebra software), we obtain:

∆ (g -1)C (G -s -g)C α(C -T lost ) α(s.C + T lost ) R D C -T lost s.C T lost T -G.C G g G 4 G 3 G 1
Waste hierarch = 1 2µ p T ×     T 2 +GC(q) (1 -α)(2µ p -T ) + (2α -1)C(q) +T 2(D(q) + R(q)) + (α + 1)C(q) +(1 -2α)C(q) 2     (13)
Of course this expression reduces to Equation ( 5) when G = 1. Just as for the coordinated scenario, we enforce the constraint

GC(q) ≤ T ≤ 0.1µ p (14)
The first condition is by construction of the periodic checkpointing policy, and the second is to enforce the validity of the first-order approximation, assuming at most one failure per period.

Refining the model

We introduce three new parameters to refine the model when the processors have been partitioned into several groups. These parameters are related to the impact of message logging on execution, re-execution, and checkpoint image size, respectively.

Impact of message logging on execution and re-execution-With several groups, inter-group messages need to be stored in local memory as the execution progresses, and event logs must be stored in a reliable storage, so that the recovery of a given group, after a failure, can be done independently of the other groups. This induces an overhead, which we express as a slowdown of the execution rate: instead of executing one work-unit per second, the application executes only λ work-units, where 0 < λ < 1. Typical values for λ are said to be λ ≈ 0.98, meaning that the overhead due to payload messages is only a small percentage [START_REF] Bouteiller | Redesigning the message logging model for high performance[END_REF][START_REF] Guermouche | HydEE: Failure Containment without Event Logging for Large Scale Send-Deterministic MPI Applications[END_REF]. On the contrary, message logging has a positive effect on re-execution after a failure, because inter-group messages are stored in memory and directly accessible after the recovery (as explained in Section 2.2). Our model accounts for this by introducing a speed-up factor ρ during the re-execution. Typical values for ρ lie in the interval [1..2], meaning that re-execution time can be reduced up to by half for some applications [START_REF] Bouteiller | MPICH-V: a multiprotocol fault tolerant MPI[END_REF].

Fortunately, the introduction of λ and ρ is not difficult to account for in the expression of the expected waste: in Equation ( 6), we replace Work by λWork and Re-Exec by Re-Exec ρ and obtain

Waste hierarch = T -λWork T + 1 µ p D(q) + R(q) + Re-Exec ρ ( 15
)
where the values of Work and Re-Exec are unchanged, and given by Equations [START_REF] Rao | Egida: An extensible toolkit for low-overhead fault-tolerance[END_REF] and (8 -12) respectively.

Impact of message logging on checkpoint size-Message logging has an impact on the execution and re-execution rates, but also on the size of the checkpoint. Because inter-group messages are logged continuously, the size of the checkpoint increases with the amount of work that is executed before a checkpoint. Consider the hierarchical scenario with G of q processors. Without message logging, the checkpoint time of each group is C 0 (q), and to account for the increase in checkpoint size due to message logging, we write the equation

C(q) = C 0 (q)(1 + βλWork) ⇔ β = C(q) -C 0 (q) C 0 (q)λWork (16)
As before, λWork = λ(T -(1 -α)GC(q)) (see Equation ( 7)) is the number of work units, or application iterations, completed during the period of duration T , and the parameter β quantifies the increase in the checkpoint image size per work unit, as a proportion of the application footprint. Typical values of β are given in the examples of Section 4. Combining with Equation ( 16), we derive the value of C(q) as

C(q) = C 0 (q)(1 + βλT ) 1 + GC 0 (q)βλ(1 -α) (17)
The first constraint in Equation ( 14), namely GC(q) ≤ T , now translates into GC 0 (q)(1 + βλT ) 1 + GC 0 (q)βλ(1 -α) ≤ T which leads to GC 0 (q)βλα ≤ 1 and T ≥ GC 0 (q) 1 -GC 0 (q)βλα (18)

Case Studies

In this section, we instantiate the previous model to evaluate different case studies. We propose three generic scenarios for the checkpoint protocols, three application examples that provide different values for the parameter β, and four platform instances.

Checkpointing algorithm scenarios

Coord-IO-The first scenario considers a coordinated approach, where the duration of a checkpoint is the time needed for the p total processors to write the memory footprint of the application onto stable storage. Let Mem denote this memory, and b io represents the available I/O bandwidth. Then we have C = C Mem , where C Mem = Mem bio . In most cases we have equal write and read speed access to stable storage, and we let R = C = C Mem , but in some cases we have different values, for example with the K-Computer (see Table 1). As for the downtime, the value D is the expectation of the duration of the downtime. With a single processor, the downtime has a constant value, but with several processors, the duration of the downtime is very difficult to compute: a processor can fail while another one is down, thereby leading to cascading downtimes. The exact value of the downtime with several processors is unknown, even for failures distributed according to an exponential law, but an upper bound can be provided (see [START_REF] Bougeret | Using group replication for resilience on exascale systems[END_REF] for details). In most practical cases, the lower bound of the downtime of a single processor is expected to be very accurate, and we use a constant value for D in our case studies.

Hierarch-IO-The second scenario uses a number of relatively large groups. Typically, these groups are composed so as to take advantage of the application communication pattern [START_REF] Guermouche | HydEE: Failure Containment without Event Logging for Large Scale Send-Deterministic MPI Applications[END_REF][START_REF] Esteban Meneses | Team-based message logging: Preliminary results[END_REF]. For instance, if the application executes on a 2D-grid of processors, a natural way to create processor groups is to have one group per row (or column) of the grid. If all processors of a given row belong to the same group, horizontal communications are intra-group communications and need not to be logged. Only vertical communications are inter-group communications and, as such, need to be logged.

With large groups, there are enough processors within each group to saturate the available I/O bandwidth, and the G groups checkpoint sequentially. Hence the total checkpoint time without message logging, namely GC 0 (q), is equal to that of the coordinated approach. This leads to the simple equation

C 0 (q) = C Mem G = Mem Gb io (19)
where Mem denotes the memory footprint of the application, and b io the available I/O bandwidth. Similarly as before, we let R(q) for the recovery (either equal to C(q) or not), and use a constant value D(q) = D for the downtime.

Hierarch-Port-The third scenario investigates the possibility of having a large number of very small groups, a strategy proposed to take advantage of hardware proximity and failure probability correlations [START_REF] Bouteiller | Correlated set coordination in fault tolerant message logging protocols[END_REF]. However, if groups are reduced to a single processor, a single checkpointing group is not sufficient to saturate the available I/O bandwidth. In this strategy, multiple groups of q processors are allowed to checkpoint simultaneously in order to saturate the I/O bandwidth. We define q min as the smallest value such that

q min b port ≥ b io (20)
Here b port is the network bandwidth of a single processor. In other words, q min is the minimal size of groups so that Equation ( 19) holds. Small groups typically imply logging more messages (hence a larger growth factor of the checkpoint per work unit β, and possibly a larger impact on computation speed λ). Coming back to an application executing on a 2D-grid of processors, twice as many communications will be logged (assuming a symmetrical communication pattern along each grid direction). However, let us ompare recovery times in the Hierarch-Port and Hierarch-IO strategies; assume that R 0 (q) = C 0 (q) for simplicity. In both cases Equation [START_REF] Plank | Processor allocation and checkpoint interval selection in cluster computing systems[END_REF] holds, but the number of groups is significantly larger for Hierarch-Port, thereby ensuring a much shorter recovery time.

Application examples

We study the increase in checkpoint size due to message logging by detailing three application examples: 2D-and 3D-stencil computations, and linear algebra kernels such as matrix product. These examples are typical scientific applications that execute on 2D-or 3D-processor grids, but they exhibit a different increase rate parameter β, as shown below.

2D-Stencil-We first consider a 2D-stencil computation: a real matrix of size n × n is partitioned across a p × p processor grid, where p 2 = p total . At each iteration, each matrix element is averaged with its 8 closest neighbors, which requires rows and columns that lie at the boundary of the partition to be exchanged (it is easy to generalize to larger update masks). Each processor holds a matrix block of size b = n/p, and sends four messages of size b (one in each grid direction) at each iteration. Then each element is updated, at the cost of 9 double floating-point operations. The (parallel) work for one iteration is thus Work = 9b 2 sp , where s p is the speed of one processor. With the Coord-IO scenario, C = C Mem = Mem bio . Here Mem = 8n 2 (in bytes), since there is a single (double real) matrix to store. As already mentioned, a natural (application-aware) group partition is with one group per row (or column) of the grid, which leads to G = q = p. Such large groups correspond to the Hierarch-IO scenario, with C 0 (q) = CMem G . At each iteration, vertical (inter-group) communications are logged, but horizontal (intra-group) communications are not logged. The size of logged messages is thus 2pb = 2n for each group. If we checkpoint after each iteration, C(q)-C 0 (q) = 2n bio , and we derive from Equation ( 16) that β = 2npsp n 2 9b 2 = 2sp 9b 3 . We stress that the value of β is unchanged if groups checkpoint every k iterations, because both C(q) -C 0 (q) and Work are multiplied by a factor k. Finally, if we use small groups of size q min , we have the Hierarch-Port scenario. We still have C 0 (q) = CMem G , but now the value of β has doubled since we log twice as many communications.

Matrix-Product-Consider now a typical linear-algebra kernel involving several matrix products. For each matrix-product, there are three matrices involved, so Mem = 24n 2 (in bytes) and C = C Mem = Mem bio for the Coord-IO scenario. Just as before, each matrix is partitioned along a 2D-grid of size p × p, but now each processor holds three matrix blocks of size b = n/p. Consider Cannon's algorithm [START_REF] Cannon | A cellular computer to implement the Kalman filter algorithm[END_REF] which has p steps to compute a product. At each step, each processor shifts one block vertically and one block horizontally, and the work is Work = 2b 3 sp . In the Hierarch-IO scenario with one group per grid row, only vertical messages ar logged, so that C(q) -C 0 (q) = b 2 bio . We derive that β = sp 6b 3 . Again, β is unchanged if groups checkpoint every k steps, or every matrix product (k = p). In the Coord-Port scenario with groups of size q min , the value of β is doubled. In both scenarios, we have C 0 (q) = CMem G (but many more groups in the latter).

3D-Stencil-This application is similar to 2D-Stencil, but exhibits larger values of β. We have a 3D matrix of size n partitioned across a 3D-grid of size p, where 8n 3 = Mem and p 3 = p total . Each processor holds a cube of size b = n/p. At each iteration, each pixel is averaged with its 27 closest neighbors, so that Work = 27b 3 sp . Each processor sends the six faces of its cube, one in each direction. In addition to the Coord-IO scenario, there are now three hierarchical scenarios: A) Hierarch-IO-Plane where groups are horizontal planes, of size p 2 . Only vertical communications are logged, which represents Table 2: Parameters G, q min , C, R, C(q), R(q) and β for all platform/scenario combinations with 2D-Stencil and Matrix-Product. The equation C 0 (q) = C/G always hold.

two faces per processor. We derive β = 2sp 27b 3 ; B) Hierarch-IO-Line where groups are lines, of size p. Twice as many communications are logged, which represents four faces per processor. We derive β = 4sp 27b 3 ; C) Hierarch-Port with groups of size q min . All communications are logged, which represents six faces per processor. We derive β = 6sp 27b 3 . Note that the order of magnitude of b is the cubic root of the memory per processor for 3D-Stencil, while it was its square root for 2D-Stencil and Matrix-Product, so β will be larger for 3D-Stencil than for the other two applications.

Platforms

We consider multiple platforms, existing or envisioned, that represent state-ofthe-art targets for HPC applications. Table 1 presents the basic characteristics of the platforms we consider. The machine named Titan represents the fifth phase of the Jaguar supercomputer, as presented by the Oak Ridge Leadership Computing Facility1 . The cumulated bandwidth of the I/O network is targeted to top out at 1 MB/s/core, resulting in 300GB/s for the whole system. We consider that all existing machines are limited for a single node output by the bus capacity, at approximately 20GB/s. The K-Computer machine, hosted by Riken in Japan, is the fastest supercomputer of the Top 500 list at the time of writing. Its I/O characteristics are those presented during the Lustre File System User's Group meeting, in April, 2011 [START_REF] Sumimoto | An Overview of Fujitsu's Lustre Based File System[END_REF], with the same bus limitation for a single node maximal bandwidth. The two exa-scale machines represent the two most likely scenarios envisioned by the International Exascale Software Project community [START_REF] Dongarra | The international exascale software project: a call to cooperative action by the global high-performance community[END_REF], the largest variation being on the number of cores a single node should host. For all platforms, we let the speed of one core be 1 Gigaflops, and we derive the speed of one processor s p by multiplying by the number of cores.

Parameters

Tables 2 and3 summarize key parameters for all platform/scenario combinations. In all instances, we use the following default values: ρ = 1.5, λ = 0.98 and α = 0.3. It turns out that these latter parameters have very little impact on the results. 3: Parameters G and β for all platform/scenario combinations with 3D-Stencil. The equation C 0 (q) = C/G always hold (see Table 2 for values of C).

Results from the model

This section covers the results of our unified model on the previously described scenarios (one for coordinated checkpointing and two for hierarchical checkpointing) applied to four platforms, two that reflect existing top entries of Top500, and two on envisioned Exascale machines. In order to allow fellow researchers access to the model, results and scenarios proposed in this paper, we made our computation spreadsheet publicly available. https://www.dropbox.com/ s/m7b2q6vu4y1b2wc/Maple.tar.gz.

We start with some words of caution. First, the applications used for this evaluation exhibit properties that makes them a difficult case for hierarchical checkpoint/restart techniques. These applications are communication intensive, which leads to a noticeable impact on performance (due to message logging). In addition, their communication patterns create logical barriers that make them tightly-coupled, giving a relative advantage to all coordinated checkpointing methods (due to the lack of independent progress). However, these applications are more representative of typical HPC applications than loosely-coupled (or even independent) jobs, and their communication-to-computation ratio tends to zero with the problem size (full weak scalability). Next, we point out that the theoretical values used in the model instances are overly optimistic, based on the values released by the constructors and not on measured values. Finally, we stress that the horizontal axis of all figures is the processor MTBF µ, which ranges from 1 year to 100 years, a choice consistent with the usual representation in the community. In the following discussion, we often refer to the platform MTBF µ p , (see Section 3.1).

Due to the large time required to dump the total memory of the K-Computer or of the Exascale platforms, we assume that a checkpoint incurs a transfer of only a fraction of the total memory (1% for the K-Computer, 1% and 0.1% for Exascale). Otherwise the waste is almost equal to 1 for all scenarios with these machines. While checkpointing only a small fraction of the memory is possible only in some circumstances (employing incremental or application-based checkpointing), here it is mandatory to ensure any application progress -a first (negative) result of our model.

On platforms exhibiting characteristics similar to today's top entries in the Top500, namely Titan and K-Computer, we encounter a quite familiar environment (Figure 8(a)). Clearly, the key factors impacting the balance between coordinated and hierarchical protocols are the communication intensity of the applications (2D-Stencil, Matrix-Product, and 3D-Stencil), and the I/O capabilities of the system. On both platforms, the coordinated protocol has a slow startup, preventing the application from progressing when the platform MTBF µ p is under a system limit directly proportional to the time required to save the coordinated checkpoint. Hierarchical protocols have a quicker startup. However, the cost of logging the messages and the extra checkpoint data is detrimental to the hierarchical protocols when there are fewer failures (even considering the most promising approaches). The vertical segments on the graphs correspond to cut-off values where we enforce the condition T ≤ 0.1µ p (see Equation ( 14)). Values of µ for which no waste is reported correspond to configurations for which no period can satisfy Equation [START_REF] Young | A first order approximation to the optimum checkpoint interval[END_REF].

The Exascale platforms exhibit a similar behavior. In order to evaluate the impact of the checkpoint size, here we provide results with a checkpointing size of 1% and 0.1% of the total memory (Figure 8(b) and 8(c)). As expected, by reducing the checkpoint size, the applications start progressing earlier for both protocols. In most cases hierarchical protocols seem more suitable for such a type of platforms. While they struggle when the communication intensity increases (the case of the 3D-Stencil), they provide limited waste for all the other cases. Overall, Exascale-Fat leads to a smaller waste (or better resource usage) than Exascale-Slim, because it has 10 times fewer processors of same MTBF.

Validation of the model

The simulation engine generates a random trace of errors (parameterized by an Exponential failure distribution or a Weibull one with a shape parameter of 0.7 or 0.5). On this error trace, we simulate the behavior of fault tolerance protocols. In the simulator, there is no assumption on when errors can happen: an error can strike a processor while another or the same processor is already subject to a failure and a recovery phase.

We arbitrarily set the duration of an application failure-free execution to 4 days on each process. We measure the actual execution time of each application on each platform and on each error trace using a time-out of one year: if an execution does not complete before the one year deadline, we consider it never completes and do not report any result for this particular platform/application setting. From the simulated execution times, we compute the actual average waste.

Figure 15 reports the waste for various application/platform scenarios for a Weibull failure distribution with k = 0.7. Results for an Exponential failure distribution and for a Weibull with k = 0.5, are provided in Figures 16 and17 . Each point on the graphs is an average over 20 randomly generated instances.

Overall, Figures 15, 16 and 17 present similar trends and conclusions as 8. The main differences are seen for low MTBFs, in the vicinity of cut-offs values for Figure 8. There, either the first-order assumption could no longer be satisfied, or coordinated protocols were assessed not to allow for any application progress. Simulations show that, in these extreme settings, our analytical study was pessimistic: coordinated protocols have indeed very bad performance, but often applications still make progress (albeit at an unrealistic pace); coordinated protocols have an advantage over hierarchical protocols for slightly lower MTBFs than predicted. However, the simulations validate the relative performance of the different protocols.

For each scenario and each protocol, we plot (in solid line) the average waste for the checkpointing period computed with our model (the one minimizing Equation ( 15)). In Figures 15,16 and 17 we also plot (in dotted line) the average waste obtained for the best checkpointing period (BestPer), numerically found by generating, and evaluating through simulations, a set of 480 periods representative of a very large neighborhood of the period computed with our model. The very good matching between solid and dotted lines show that our model enables to compute near-optimal checkpointing periods.

The comparison between Figures 15, 16 and 17 shows some differences. First, Figure 16 shows better results compared to 15 and 17. This is because, for the same MTBF value, the probability of failure for an exponential distribution is smaller than the one for a Weibull distribution with the two values of k. This is also the reason why the coordinated checkpointing protocol outperforms the hierarchical one for a smaller MTBF value in Figure 16 than in Figures 15 and17. The same remarks can be done if we compare Figures 15 and17 since the probability of failure is smaller when k = 0.7.

Conclusion

Despite the increasing importance of fault tolerance in achieving sustained, predictable performance, the lack of models and predictive tools has restricted the analysis of fault tolerant protocols to experimental comparisons only, which are painfully difficult to realize in a consistent and repeated manner. This paper introduces a comprehensive model of rollback recovery protocols that encompasses a wide range of checkpoint/restart protocols, including coordinated checkpoint and an assortment of uncoordinated checkpoint protocols (based on message logging). This model provides the first tool for a quantitative assessment of all these protocols. Instantiation on future platforms enables the investigation and understanding of the behavior of fault tolerant protocols at scales currently inaccessible. The results presented in Section 5, and corroborated by Section 6, highlight the following tendencies:

• Hardware properties will have tremendous impact on the efficiency of future platforms. Under the early assumptions of the projected Exascale systems, rollback recovery protocols are mostly ineffective. In particular, significant efforts are required in terms of I/O bandwidth to enable any type of rollback recovery to be competitive. With the appropriate provision in I/O (or the presence of distributed storage on nodes), rollback recovery can be competitive and significantly outperform full-scale replication [START_REF] Ferreira | Evaluating the Viability of Process Replication Reliability for Exascale Systems[END_REF] (which by definition cannot reach more than 50% efficiency).

• Under the assumption that I/O network provision is sufficient, the reliability of individual processors has a minor impact on rollback recovery efficiency. This suggests that most research efforts, funding and hardware provisions should be directed to I/O performance rather than improving component reliability in order to increase the scientific throughout of Exascale platforms.

• The model outlines some realistic ranges where hierarchical checkpointing outperforms coordinated checkpointing, thanks to its faster recovery from individual failures. This early result had already been outlined experimentally at smaller scales, but it was difficult to project at future scales. Our study provides a theoretical foundation and a quantitative evaluation of the drawbacks of checkpoint/restart protocols at Exascale; it can be used as a first building block to drive the research field forward, and to design platforms with specific resilience requirements.

Finally, as we are far from a comprehensive understanding of future Exascale applications and platform characteristics, we hope that the community will be interested in instantiating our publicly available model with other scenarios and case-studies.

RR n°7950

Figure 1 :Figure 2 :

 12 Figure 1: Illustrating the waste due to checkpointing in a failure-free environment: there is a slowdown of duration C at the end of every period of length T = W + C. The total work that is executed during such a period is Work = W + αC work units.

Figure 3 :

 3 Figure 3: Coordinated checkpoint: illustrating the waste when a failure occurs during the checkpoint phase.

Figure 4 :

 4 Figure 4: Hierarchical checkpoint: illustrating the waste when a failure occurs during the work phase.

∆

Figure 5 :

 5 Figure 5: Hierarchical checkpoint: illustrating the waste when a failure occurs during the checkpoint phase, and before the checkpoint of the failing group.

∆

Figure 6 :

 6 Figure 6: Hierarchical checkpoint: illustrating the waste when a failure occurs during the checkpoint phase, and during the checkpoint of the failing group.

Figure 7 :

 7 Figure 7: Hierarchical checkpoint: illustrating the waste when a failure occurs during the checkpoint phase, and after the checkpoint of the failing group.

Figure 9 :

 9 Figure 9: Impact of the parameters ρ, λ, and α on the relative gain of the hierarchical protocols with respect to the coordinated one on the Titan platform.

Figure 10 :

 10 Figure 10: Impact of the parameters ρ, λ, and α on the relative gain of the hierarchical protocols with respect to the coordinated one on the K-computer platform.

Figure 11 :

 11 Figure 11: Impact of the parameters ρ, λ, and α on the relative gain of the hierarchical protocols with respect to the coordinated one on the Exascale-Slim platform with C Mem = C Mem /100.

Figure 12 :

 12 Figure 12: Impact of parameters ρ, λ, and α on the relative gain of the hierarchical protocols with respect to the coordinated one on the Exascale-Fat platform with C Mem = C Mem /100.

Figure 13 :

 13 Figure 13: Impact of the parameters ρ, λ, and α on the relative gain of the hierarchical protocols with respect to the coordinated one on the Exascale-Slim platform (with C Mem = C Mem /1000).

Figure 14 :

 14 Figure 14: Impact of parameters ρ, λ, and α on the relative gain of the hierarchical protocols with respect to the coordinated one on the Exascale-Fat platform (with C Mem = 1000).

Figure 15 :Figure 16 :Figure 17 :

 151617 Figure 15: Simulations: waste as a function MTBF µ (years per processor), for a Weibull failure distribution with shape parameter k = 0.7.

Table 1 :

 1 Basic characteristics of platforms used to feed the model.

	Name	Number of	Number of	Number of cores	Memory	I/O Network Bandwidth (bio) I/O Bandwidth per processor (bport)
		cores	processors ptotal	per processor	per processor		Write	Read	Write	Read
	Titan	299,008	18,688	16	32GB	300GB/s	300GB/s	20GB/s	20GB/s
	K-Computer	705,024	88,128	8	16GB	96GB/s	150GB/s	20GB/s	20GB/s
	Exascale Slim 1,000,000,000	1,000,000	1,000	64GB		1TB/s	1TB/s	200GB/s	200GB/s
	Exascale Fat 1,000,000,000	100,000	10,000	640GB		1TB/s	1TB/s	400GB/s	400GB/s
	Name	Scenario	G	Checkpoint	Checkpoint	β for	β for
				(q min if app.)	Saving Time Loading Time 2D-Stencil Matrix-Product
		Coord-IO	1	2,048s		2,048s	/	/
	Titan	Hierarch-IO	136	15s		15s		0.0001098	0.0004280
		Hierarch-Port 1,246 (q min = 15)	1.6s		1.6s		0.0002196	0.0008561
		Coord-IO	1	14,688s		9,400s	/	/
	K-Computer	Hierarch-IO	296	50s		32s		0.0002858	0.001113
		Hierarch-Port 17,626 (q min = 5)	0.83s		0.53s	0.0005716	0.002227
		Coord-IO	1	64,000s		64,000	/	/
	Exascale-Slim	Hierarch-IO	1,000	64s		64s		0.0002599	0.001013
		Hierarch-Port 200,000 (q min = 5)	0.32s		0.32s	0.0005199	0.002026
		Coord-IO	1	64,000s		64,000	/	/
	Exascale-Fat	Hierarch-IO	316	217s		217s	0.00008220	0.0003203
		Hierarch-Port 33,333 (q min = 3)	1.92s		1.92s	0.00016440	0.0006407

  The impact of the different parameters are shown in figures 9, 10, 11, 12, 13, 14.

	Name	Scenario	G	β for 3D-Stencil
		Coord-IO	1	/
	Titan	Hierarch-IO-Plane	26	0.001476
		Hierarch-IO-Line	658	0.002952
		Hierarch-Port	1,246	0.004428
		Coord-IO	1	/
	K-Computer Hierarch-IO-Plane	45	0.003422
		Hierarch-IO-Line	1,980	0.006844
		Hierarch-Port	17,626	0.010266
		Coord-IO	1	/
	Exascale-Slim Hierarch-IO-Plane	100	0.003952
		Hierarch-IO-Line	10,000	0.007904
		Hierarch-Port	200,000	0.011856
		Coord-IO	1	/
	Exascale-Fat Hierarch-IO-Plane	47	0.001834
		Hierarch-IO-Line	2,154	0.003668
		Hierarch-Port	33,333	0.005502
	Table

RR n°7950

http://www.olcf.ornl.gov/computing-resources/titan/ RR n°7950


Brieuc Guillerm

Sophie Monge

Vincent Lapinte
email: vincent.lapinte@univ-montp2.fr

Jean-Jacques Robin

How to modulate chemical structure of polyoxazolines by appropriate functionalization

Keywords: cationic polymerization, functionalization of polymers, oligomers, ring-opening polymerization

Polyoxazolines (POx) are increasingly studied as polymeric building blocks due to the possibility of affording tunable properties. Additionally, as it was proved that biocompatibility and stealth behavior of POx are similar to that of poly(ethylene glycol) (PEG), it became challenging to develop polyoxazoline-based (co)polymers. Even if POx have a lot of advantages, they also show an important drawback as it is to date impossible to prepare high molecular weight polyoxazolines, with low polydispersity indexes. So, it appears important to judiciously functionalize them. This review covers the multiple ways of functionalization of polyoxazolines.

The use of functional initiators, functional terminating agents, and 2-R-2-oxazolines with R functional side group is detailed. In conclusion, some perspectives on POxfunctionalizations are also reported, with functions permitting selective "click" reactions.

Introduction

Polyoxazolines (POx) represents nowadays a valuable type of macromolecules for many reasons.

For instance, they are considered as bio-inspired polymers as they are structural isomers of both polyacrylamides, with a pendant amide function, and polypeptides, bearing amide function in the main chain. [1] To date, they were mainly investigated toward biomedical applications [2,3] due to their biocompatibility, biodistribution, blood clearance and protein adsorption. [4][5][6][7][8] Based on their low toxicity, poly(2-oxazolines) are anticipated to be suitable to build antimicrobial materials, when associated with quaternary ammonium salts. They are also employed as drug carriers, for instance. For all these reasons, POx are considered as similar to poly(ethylene glycol) (PEG). It is also important to notice that the latter showed important drawbacks. [9,10] Indeed, it was notably shown that PEG leads to adverse side effects in the body, caused by the polymer itself or by side products which are toxic. Unexpected pharmacokinetic behavior can also occur with PEG-based carriers. These non negligibleproblems led to the development of polyoxazoline derivatives which are today considered as avaluable alternative to PEG.Other important characteristic of POx-based materials is their thermosensitivity as some of them have a lower critical solution temperature (LCST), depending on the R group of the pendant chain. [11] Thermoresponsiveness is often used to build drug carriers, [12] and until now the most studied thermosensitive polymer in the literature is poly(N-isopropylacrylamide) (PNiPAM) as its LCST (around 32 °C) is relatively independent of environmental conditions. AsPNiPAM is not proved to be biocompatible,POxmay replace it and,additionally, the LCST value of such polymers can be modulated from 5 to 90 °C as a function of the R group of the pendant chain, which is a great advantage.

Well-defined POxsareeasily prepared by cationic ring-opening polymerization (CROP) of cyclic 2-R-2-oxazolines and various properties are obtained as a function of the nature of the R pendant alkyl chain (Me, Et, Pr, etc.). Several teams demonstrated the effect of the R side group on the properties in solution such as solubility in the common solventsand/or water, and the presence of a lower critical solution temperature (LCST).The influenceof the R groupswas also examined in solid state with the determination of mechanical [13,14] and thermal [15][16][17][18] properties.Whereas POxsare very promising materials, one of their drawbacks appears to be very restrictive. Indeed, whatever the nature of 2-oxazoline monomer and the initiator, the molecular weight of welldefined POx with low polydispersity index, usable for smart applications, is only limited to about 40 kg.mol -1 (Table 1). Low molecular weight is an important limitation for the spread development of polyoxazolines in comparison with poly(ethylene glycol) (PEG) competitor (notably in terms of biocompatibility and stealth behavior) which can be prepared with very high molar masses. For this reason, functionalization appears to be the key parameter to overcome this problem. One of the benefits of POx is the possible functionalization of the lateral chain, which is impossible in the case of PEG. Additionally, POx has also the great advantage of being easily converted to polyamines by treatment in acidic medium.In the case of 2-oxazoline bearing alkyl chains, no relation between the nature of the side group and the maximum molecular weight was found. A lot of studies mention transfer reactions as explanation of limited molecular weight but only a few of them investigatesin detailsthis side reaction. Lévy andLitt [19] as well as Kourti, [20] in the particular case of initiator based on metallocene,proposed a monomer transfer reaction based on the abstraction of the -proton of monomer and its transfer on the terminal oxazolinium species of the propagating polymer chain.Schubert et al. illustrated the transfer reaction in the case of 2-ethyl-2-oxazoline using matrix assisted laser desorption/ionization-time of flight (MALDI-Tof) experiments. [21] INSERT TABLE 1 In order to increase the molecular weight and decrease the reaction time, the polymerization of various 2-R-2-oxazolines was achieved by Schubert et al. [22,23] usingmicrowaves. The latter, combined with an increase of the reaction temperature, allowed decreasing the reaction timebut did not lead to higher molecular weights. [24] Indeed, the synthesis of longer well-defined polymer chains in a living way fails as the average molecular weight distributions broaden for polymerization degrees higher than 300.As a consequence, to extend the properties of low molecular weight polyoxazolines, the only solution is to functionalize them with appropriate reactive groups in order to further extend their molar mass by combination with other polymers [25] or to add specific molecules to change some of their properties. For instance, it was proved that antimicrobial activity and hemocompatibilityof telechelicpoly(2-methyloxazoline) is greatly influenced by the nature of the end groups. [26] Functionalization of thePOx chainendsis obtainedby usingfunctional initiators [27] or terminating agents [28] or viathe use of 2-R-2-oxazolines where R represents a functional pendant group [29] (Figure 1). It is also important to notice that functional groups of initiator or monomer interfere in some caseswith the cationic ring-opening polymerization of 2-R-2-oxazoline. [30] This usually detrimentally affectsyields and the control of molecular weight and such problems are minimized by using appropriate protecting groups on initiator (P' for protecting group in Figure 1), terminating agent or R pendant group(Pfor protecting group in Figure 1). This protection strategy notably reduces or removes the nucleophilicity and basicity of the reactive sites by steric hindrance and / or electronic effects. Indeed,the cationic character of the polymerization processis influenced by all nucleophilic reagents in the reaction medium coming from impurities like water, by-product of the initiator or competingnucleophilic site.

INSERT FIGURE 1

To develop smart applications, it is important to prepare well-defined polyoxazolines with controlled functionality and molecular weight, and the appropriate functional groups at the chain ends or along the backbone. [31] In this review, we describe functionalized polyoxazolinessuitable for the preparation of well-defined polyoxazoline-based (co)polymers.

Functionalizedpolyoxazolinescan be obtained using appropriate functional initiators, terminating agents and pendant chains of 2-R-2-oxazolines. These different molecules are listed and the choice in the functional groups is discussed knowing that some protecting groups are able topush back the limits of incompatibility between functional reactants and CROP process.The functionalization reactions are essentialas it will allow the development of innovative materials based on polyoxazolines. Even if lots of examples are reported in the literature, some interesting perspectives can also be envisaged and will bediscussed at the end of this contribution.

Initiator-based functionalization

To date, the cationic ring-opening polymerization of 2-oxazolines has been accomplished using many initiators including Lewis acids such as boron trifluoride (BF 3 -OEt 2 ) (IIIa column of periodic table, Figure 2) [32] zirconiun/tris(pentafluorophenyl)borate, [20] trihalogenobismuthine, [33] and alkyl esters such as tosylates, triflates (VIa column of periodic table, Figure 2) and halides (VIIa column of periodic table, Figure 2). The alkyl halide initiators range from chloride, [34] bromide [35] to iodide [36,37] as well as acetyl halide. [38] The alkyl iodide initiators are mostly converted in situ from chloride [39,40] or bromide [41] analogues using NaI or KI reactants. The simplest iodine initiator is the molecular iodinefor which the mechanism of polymerization has recently been elucidated. [42] Aoi et al.have extensively studied the influence of the nature of the initiator on the mechanism of polymerization which can be ionic and/or covalent. Chemical structure of the initiator also influences the control of the molecular weight. Indeed it was shown that a lack of controlwith the persistence of residual initiator until the end of the polymerization as well as sometimes a latency period at the beginning of the polymerizationis observed with some of the initiators,as demonstrated in the case of 4-(p-toluenesulfonate)methyl-1,3-dioxolan-2-one, [43] 3-butynyl tosylate, [34] tosylate and triflate initiators based on sugar, [44] and macroinitiators such as methoxy--4-toluene-sulfonate poly(ethylene oxide). [45] An alternative approach to overcome a slow initiation consists in preparing first the propagating species composed of the initiator after reaction with one oxazoline monomer unit. It was widely shown that this oxazolinium compound favors the control of the polymerization related to the precursor initiator. [46] -Functionalized POxwerealso developed. Either the functional group carried by the initiator does not react during the polymerization or it provokes transfer reactions. In the latter case, a protecting step is first required. [30] INSERT FIGURE 2 The cationic ring-opening polymerization process is compatible with a lot of functionsbased on atoms ofIVa column of the periodic table including carbon and silicon (Figure 2). The most studied initiators have gotalkyl chains of various lengths [22,36,37,[47][48][49] as well as perfluorinated chains. [28,50] The compatibility also exists with unsaturated aliphatic initiators with double [51][52][53] or triple bonds [34,54,55] even if transfer reactions appeared above 50% conversion in the latter case.

These unsaturated groups have an interest because they can be involved in two types of "click" reaction:thiol-ene coupling (TEC) andcopper catalyzed azide-alkyne cycloaddition (CuAAC) named Huisgen'scycloaddition. These reactions allow the modification of polyoxazolinechain ends [1] and the synthesis ofamphiphilic block copolymers by polymer-polymer coupling. [54] Initiators bearing acetal, oxirane, [56] cyclocarbonate, [43] ester [41,57] and silane [58,[START_REF] Pielichowski | Polyhedral Oligomeric Silsesquioxanes (POSS)-Containing Nanohybrid Polymers[END_REF] derivatives also leadto the CROP of oxazolines without any side reactions (Figure 3). Macroinitiators deriving fromcholesteryl [56] and vegetable oils as castor oil, [57] diacylglycerol, [56] 1,2-o-diooctadecyl-snglyceryl [48] are employed in the synthesis of amphiphiliccopolymers.The CROP of 2-oxazoline is also compatible with bis-initiators bearing unsaturations like acetylenic groups [55,[START_REF] Einzmann | [END_REF] and double bonds. [52,61,62] Multi-functional initiators based on alkyl chains, [61,63,64] aromaticrings with two reactive sites in ortho, meta or para positions [52] or sixreactive sites [65] are used in the elaboration of more complex structures. Other multi-initiators are described such as tetrachloro or iodoinitiators from porphyrine. [66] INSERT FIGURE 3 Otherwise, some functional initiators need the protection of their competitive reactive sites such as alcohol, thiol, oramine groups (Figure 4) whichcan interfere during the CROP process. These functions are based on heteroatoms belonging to Va and VIa columns of the periodic table (Figure 2). In initiator structure, the amine function is converted into urethane, [49] quaternary ammonium salt [26] whereas thiolis transformed into thioether. Alcoholgroupsareconverted into ester groups includingadamantyl which leads to supramolecular network by interactions, [67] or intoacetal or cyclocarbonate groups. Another protecting group of alcohol function is thesilyl ethers like thetert-butyldiphenylsilyl ether. [30] Alcohol groups are also protected into acetate groups in the synthesis of glyco-initiator. [44] Finally, some initiators bearpolymerizable groups such as vinyl [68] andstyrenic [69] groupsin order to further elaborate graft copolymers.

INSERT FIGURE 4

Terminating agent-based functionalization

The cationic nature of the oxazoline polymerization and the persistence of the oxazoliniumpropagating species in terminal position of the polymer chain requirea nucleophilic reagent as terminating agent to stop the propagation. Several reactants based on sulfur, oxygen and nitrogen chemistries were already described as illustrated in Figure 5. The terminating agents belong to Va and VIa columns of the periodic table (Figure 2). The most widely used terminating agent is water [47,70,71] or above all its activated corresponding ion: hydroxyl ion in methanolicsodium hydroxide solution [72] or sodium hydrogen carbonate. [73] In this particular case, whatever the activated species, a hydroxy-terminated polyoxazoline is obtained but the mechanism of the terminating stage is not the same. Indeed, in the presence of sodium hydrogen carbonate, attack on the 2-position of the oxazolinium ring occurs while attack of nucleophilic reagent takes place on the 5-position of the oxazolinium specie. [START_REF] Dubois | Handbook of Ring-Opening Polymerization[END_REF] The other main family deals withamines whichhave an adequate nucleophiliccharacter(pKa>10) to react with oxazolinium species. The basic nitrogen derivative, ammonia, is successfully used as terminating agent [START_REF] Park | [END_REF] while the primary amines are the most important group, ranging from aliphatic compounds with long chain to obtain amphiphilic copolymers, [76] aniline [51] to various functional primary amines. [69,77] Secondary cyclic amines as terminating agents are represented bypiperidine, [78] piperazine derivatives [39,79] or morpholine [80] and by bis-functional acyclic amines. [81,82] Even if the tertiary amines such as pyridine, [56] pyrrole [35] and linear amine with long alkyl chain are less reactive than those less substituted, they react as terminating agents for biocide applications. [83] Ainteresting nitrogen terminating agent issodium azide (NaN 3 ) which further leadsto Huisgen'scycloaddition to generate amphiphilic copolymers by click reaction. [63,84] Another approach consists in the use of bis-terminating agent like ethylenediaminein excess to avoid the coupling between two polyoxazoline chains. [26] Functional amine with alcohol group in -position is also employed to obtain hydroxy-terminal polyoxazoline without using potassium hydroxide, preventing from the hydrolysis of the ester group of the initiator structure. [67] Another class of terminating agents isbased on sulfur derivatives like sodiumthiolates, [85][86][87][88] notably allowing the introduction of carboxylic acids, [88] for instance, or on carboxylic acids and corresponding carboxylate salts such as acrylic acid, [87,89] methacrylic acid, [90][91][92] maleic acid, [93] glutaric acid, [94] cinnamic acid [95] and terephtalic acid. [90] As explained in the case of functional initiators, functional terminating agents are employed to transformpolyoxazolines in macromonomersfor the further elaboration of grafted copolymers.

The polyoxazolinemacromonomers belong to styrenic, [39,96] acrylate [89,97] and methacrylate families. [77,91,92] The last class of terminating agents gathersdifunctionalreagents whichpermitthe increase of the polyoxazolinemolecular weight by a double reaction with central unsaturation coming from the agent. [90,93,94] INSERT FIGURE 5 4

. Functionalized monomers

The third method of polyoxazolinefunctionalization corresponds to the use of 2-R-2-oxazoline monomer bearing R functional pendant group (Figure 6). This possibility of functionalization is a majorbenefit related to poly(ethylene glycol)and offersa supplementary scope of properties in comparison withthe latter.In this purpose,Hoogenboomet al. investigated the feasibility of the preparation of various 2-substituted 2-oxazolines as well as their polymerization. [98] Whatever the R group, the side chain of the monomer may not react during the CROP process. Consequently, a protecting grouphas to beused when necessary to avoid any side-reaction of R group with the propagating species. The R pendant groups based on carbon and silicon (IVa column of periodic table, Figure 2) doesnot requiremasking groups. A lot of 2-oxazolines bearing hydrocarbonated pendant groups were developed while few 2-oxazolines with silane pendant chains were synthesized. [99,100] The most studied2-oxazoline monomers bearlinear alkyl chain with various lengthsranging from methyl to undecyl groups. [19,71,[START_REF] Park | [END_REF]99,[101][102][103][104][105] Additionally, the alkyl chain can also be substituted, withiso-propyl, [START_REF] Park | [END_REF] iso-butyl, [103] ter-butyl, [106] neopentyl, [107] ethylheptyl [102] andethylpentyl groups. [108] The influence of R alkyl group on the polymer solubility, mechanical(Young modulus) and thermal properties(glass transition temperature value)

properties of the final material has widely been described in the literature. Poly(2-methyl-2oxazoline) and poly(2-ethyl-2-oxazoline) are hydrophilic [16] whereas longer R groups or aromatic group lead to hydrophobic character, [107] reflecting the importance of R pendant chain on the solubility.Glass transition temperatures range from 15 to 105°C as a function of the R chain length. [15][16][17][18] Otherwise, the Young modulus is only influenced by R groups containing less than four carbons. [13,14] The impact of the alkyl chain on the behavior of polyoxazoline in solution is also illustrated by the existence of a LCST between 5 and 90 °C [15, 18, 109] which is observed for most POx, except for 2-methyl-2-oxazoline.

2-Oxazoline monomers bearing unsaturation are described with single (internal or terminal) [98,103,110] or several double bonds such as 2-isopropenyl-2-oxazoline [92] which polymerizes under free, [111] controlled (RAFT) radical processes, [112] anionic and cationic polymerizations. [113] 2-(9-Decenyl)-2-oxazoline was modified by thiol-ene coupling in the presence of 2-mercaptoethanol giving polyols for polyurethane formulations. [110] The unsaturationsof soy-based 2-oxazoline monomer were employed to crosslink the core of micelles under UV-irradiation. [114,115] The same strategy is used with tetrathiol in order to elaborate novel photoresist. [116] Alkyne-based oxazolines with one or two unsaturationsare also describedand employed for Huisgen'sCuAACcycloaddition. [79] For instance, Schlaadet al.investigated the crosslinking of block copolymer micelles by thiol-yne reaction. [117] Several 2-oxazolinesbearing cycloaliphatic R side chains were described with strained cycle, [118] bicycle or tricycle. [98] 2-Oxazolines with aromatic R side groups were also synthesized [19] with various substituents [29,98,105,119] including perfluorogroup. [103,120] Other aromatic systems were investigated with furanyl [103,121] and carbazoyl cycles.

As illustrated in Figure 2, the mono-halogenated derivatives based on the elements of the VIIa column of the periodic table cannot be considered as pendant chain due to their high reactivity as initiator whichcanmake them react, thus building branched polyoxazolines. Moreover no protecting group exists with easy deprotection protocol for such compounds. From the Va column, only few examples of pendant chain bearing nitrogen or phosphorus atoms are detailed in the literature because of their high reactivity requiring a protecting step with tertbutyloxycarbonyl (Boc) group [98,119] and into phosphoric ester, respectively. [98] Several examples of pendant chains bearing nitrogenated cycle aredescribed with azetidinyl, azepanyl, piperidine, 1-azocanyl, 1-morpholine, 1-pyrrolidinyl [122] and pyrrolidonylethyl. [123] After the hydrocarbonated R side groups, the oxygenated ones are the most numerous examples in the literature whereasthosebased on sulfurare rare [103] (VIa column of periodic table, Figure 2). Alcohol end group [104] on the pendant chain was investigated even if a protecting group was usually used such as ester [104] or acetal group, [98,123] sometimes cyclic. [124] An interesting example is the glycooxazolineon which each alcohol group is protected into acetate groups.The last class of R side groups in 2-oxazoline is represented by polymer chains like polystyrene, [15][16][17] poly(ethylene oxyde) [123] and poly(-caprolactone). [125] These 2-oxazolines are employed as macromonomers in the synthesis of graft copolymers.

INSERT FIGURE 6

Conclusion and Perspectives

In this review, we described the different ways of functionalization of polyoxazolines using appropriate initiator, terminating agent or viathe R group of the pendant chain of the 2-R-2 oxazoline monomer. It was shown that initiators can bear polyhedral oligomericsilsesquioxane, saccharide, steroid, vegetable oil derivatives, for instance. Terminating agents can notably allow the introduction of a polymerizable groups or sol-gel precursors at the chain end. The wide number of functionalizations of polyoxazolines also comes from R functional pendant groups in the 2-R-2-oxazoline monomers notably with glucose units, aromatic or fluorescent groups. All these possibilities permit the easy synthesis of very different polyoxazolines with lots of different properties which can be adapted to the targeted application, often in the biomedical field due to the biocompatibility and stealth behavior of POx. Easy functionalization explains the interest brought to polyoxazolines by the researchers who noticed a great contribution of these materials compared to poly(ethylene glycol) which proved these last years to generate some problems for biomedical applications as explained in the introduction of this review. Additionally, in the case of PEG, functional groups cannot be introduced so easily. On the reverse,functionalizations of POx lead to further reactivity and permit the building of more complex macromolecular architectures by polymer-polymer coupling or by using polyoxazoline derivatives as macroinitiators.

Among all possibilities of functionalization of POx, selective and orthogonal reactions named "click" reactions appear to be of interest and were already successfully employed in macromolecular chemistry. [126] More precisely, POxfunctionalizations have already been described in the literature usingthiol-ene [127] andthiol-yne [117] reactions, and the Huisgen'scycloaddition catalyzed by copper (CuAAC) reaction. [79,128] In such cases, polyoxazolinesbear double, triple bonds, or azido groups (Figure 7).

INSERT FIGURE 7

Another example involving POx deals with a multifunctional copoly(2-oxazoline) containing anthracene and ω-azide termini as well as pendant alkene group in the side chain (Figure 8). [128] In that case, three different "click" reactionsare achieved: (i) azide-alkyne cycloadditon, (ii) Diels-Alder reaction, and finally (iii) thiol-ene reaction. This example is very interesting as it

shows that multi functional polyoxazolines can be prepared leading to complex chemical structures with a very good control over the molecular weight of the polymer.

INSERT FIGURE 8

From works already described in the literature, some perspectives for the development of new functionalized polyoxazolines can be considered, based on "click" reactions (Figure 9). Indeed, from multi-functional POx just described, it is obvious that Diels-Alder "click" must be studied, taking into account previous work reported by Saegusa [129] and Stevens. [130] The great interest of the Diels-Alder reaction is that it is reversible as a function of the temperature.

So,thermoreversible Diels-Alder reaction could lead to the release ofpolyoxazoline bearing unsaturation in terminal or pendant groups. [131] Thus, new polyoxazolines bearing diene have to be prepared to react with a dienophile. On the other hand,POxdienophile has already been synthesized and could react with diene. Another possibility consists in developing "pentafluoro" clicking, as already mentioned in the literature for other kinds of polymers. [132] This reaction corresponds to the "clicking" of thiol with pentafluoro groups, the latter being introduced via the initiator of in the pendant chain of the oxazoline monomer (Figure 9).

INSERT FIGURE 9

These perspectives demonstrate that the synthesis of various polyoxazoline-based (co)polymers is still possible, by using already prepared polyoxazolines or new ones with useful functionalities.

These new structures might lead to innovative materials that could be employed for smart applications, notably for the biomedical field which requires a good control over the molar mass and the molecular weight distribution, and also appropriate functionalities.

Table 1. Limited molecular weights of polymer chains for various oxazoline monomers allowing the obtaining of well-defined polyoxazolines with low polydispersity indexes. and azide-alkyne cycloaddition. [128] Figure 9. Perspectives concerning the synthesis of functionalized polyoxazolines from precursors bearing appropriate functionality.

Table 1. Limited molecular weightsof polymer chainsfor various oxazoline monomers allowing the obtaining of well-defined polyoxazolines with low polydispersity indexes.

R DP n,exp

M n,max (g.mol -1 )

Ð

Me [83] 149 13000 1.04

Et [38,133] 404 40000 1.20

Pr [134] 106 12000 1.04 iPr [START_REF] Park | [END_REF] 86 10000 1.02 Bu 100 [14]

Figure 1 .

 1 Figure 1. General synthetic considerations for the synthesis of functionalized polyoxazolines

Figure 2 .

 2 Figure 2.The terminating agents and the pendant chainsof oxazolinesbearing various elements of

Figure 3 .

 3 Figure 3. Functionalized initiators for the cationic ring-opening polymerization of 2-R-2-

Figure 4 .

 4 Figure 4. Initiators bearing additional protected and unprotected groups.

Figure 5 .

 5 Figure 5. Terminating agents for the cationic ring-opening polymerization of 2-R-2-oxazolines.

Figure 6 .

 6 Figure 6.R side groups of 2-R-2-oxazoline allowing the functionalization of POx pendant chains.

Figure 7 .

 7 Figure 7.Polyoxazolines bearing functional groups allowing "click chemistry" reactions (All

Figure 8 .

 8 Figure 8. Chemical structure of multi-functionalized poly(2-oxazoline) allowing the

Figure1.

  Figure1.General synthetic considerations for the synthesis of functionalizedpolyoxazolines (Ini:

Figure 2 .

 2 Figure 2.The terminating agents and the pendant chainsof oxazolinesbearing various elements of

Figure 3 .

 3 Figure 3. Functionalized initiators for the cationic ring-opening polymerization 2-R-2-

Figure4.

  Figure4.Initiatorsbearing additional protected and unprotected groups.

Figure 5 .

 5 Figure 5. Terminating agents for the cationic ring-opening polymerization of 2-R-2-oxazolines.

Figure 6 .

 6 Figure 6.R sidegroups of2-R-2-oxazoline allowing the functionalization of POx pendant chains.

Figure 7 .

 7 Figure 7.Polyoxazolines bearing functional groups allowing "click chemistry" reactions (All

Figure 8 .

 8 Figure 8.Chemical structure of multi-functionalized poly(2-oxazoline) allowing the incorporation

Table of Contents How to modulate chemical structure of polyoxazolines by appropriate functionalization

  Brieuc Guillerm, Sophie Monge, Vincent Lapinte,* Jean-Jacques Robin Poly(2-oxazoline)s are widely employed as polymeric building block for the obtaining of well defined macromolecular architecturesfor smart applications. As a consequence, the functionalization of such derivatives is of great interest. The versatility and the diversity of the latterusing functional initiators, terminating agents and R pendant chains of the monomersare highlighted in this review.