Li Han
email: li.han@ens-lyon.fr

Valentin Le Fèvre

Louis-Claude Canon

Yves Robert

Frédéric Vivien

A Generic Approach to Scheduling and Checkpointing Workflows *

Keywords: workflow, checkpoint, fail-stop error, resilience

This work deals with scheduling and checkpointing strategies to execute scientific workflows on failure-prone largescale platforms. To the best of our knowledge, this work is the first to target fail-stop errors for arbitrary workflows. Most previous work addresses soft errors, which corrupt the task being executed by a processor but do not cause the entire memory of that processor to be lost, contrarily to fail-stop errors. We revisit classical mapping heuristics such as HEFT and MINMIN and complement them with several checkpointing strategies. The objective is to derive an efficient trade-off between checkpointing every task (CKPTALL), which is an overkill when failures are rare events, and checkpointing no task (CKPTNONE), which induces dramatic re-execution overhead even when only a few failures strike during execution. Contrarily to previous work, our approach applies to arbitrary workflows, not just special classes of dependence graphs such as M-SPGS (Minimal Series-Parallel Graphs). Extensive experiments report significant gain over both CKPTALL and CKPTNONE, for a wide variety of workflows.

Introduction

This work deals with scheduling techniques to deploy scientific workflows on large parallel or distributed platforms. Scientific workflows are the archetype of HPC (High Performance Computing) applications, which are naturally partitioned into tasks that represent computational kernels. The tasks are partially ordered because the output of some tasks may be needed as input to some other tasks. Altogether, the application is structured as a DAG (Directed Acyclic Graph) whose nodes are the tasks and whose edges enforce the dependences. Nodes are weighted by the computational requirements (in flops) while edges are weighted by the size of communicated data (in bytes). Given a workflow and a platform, the problem of mapping the tasks onto the processors and to schedule them so as to minimize the total execution time, or makespan, has received considerable attention. This classical mapping and scheduling problem has recently been revisited to account for the fact that errors and failures can strike during execution. Indeed, platform sizes have become so large that errors and failures are likely to strike at a high rate during application execution [START_REF] Cappello | Toward exascale resilience: 2014 update[END_REF]). More precisely, the MTBF (Mean Time Between Failures) µ P of the platform decreases linearly with the number of processors P , since µ P = µind P , where µ ind is the MTBF of each individual component (see Proposition 1.2 in (Hérault and Robert (2015))). Take µ ind = 10 years as an example. If P = 10 5 then µ P ≈ 50 minutes and if P = 10 6 then µ P ≈ 5 minutes: from the point of view of faulttolerance, scale is the enemy.

Several approaches (see Section 6 for a review) have been proposed to mitigate the simplest instance of the problem, that of soft and silent errors. Soft errors cause a task execution to fail but without completely losing the data present in the processor memory. Local checkpointing (or more precisely making a copy of all task input/output data), and task replication, are the most widely used technique to address soft errors. Silent errors represent a different challenge than soft errors, in that they do not interrupt the execution of the task but corrupt its output data. However, their net effect is the same, since a task must be re-executed whenever a silent error is detected. A silent error detector is applied at the end of a task's execution, and the task must be re-executed from scratch in case of an error. Again, local checkpointing (making copies of input/output data) or replicating tasks and comparing outputs, are two common techniques to mitigate the impact of silent errors.

Fail-stop errors, or failures, are much more difficult to deal with. In the case of a fail-stop error (e.g., a crash due to a power loss or some other hardware problem) the execution of the processor stops, all the content of its memory is lost, and the computations have to be restarted from scratch, either on the same processor once it reboots or on a spare. The defacto approach to handle such failures is Checkpoint/Restart (C/R), by which application state is saved to stable storage, such as a shared file system, throughout execution. The common strategy used in practice is checkpoint everything, or CKPTALL: all output data of each task is saved onto stable

P 1 P 2 T 1 T 2 T 3 T 4 T 5 T 6 T 7 T 8 T 9
Figure 1. Schedule of a workflow with 9 tasks on 2 processors (each edge corresponds to a file dependence between tasks). storage (in which case we say "the task is checkpointed").

For instance, in production Workflow Management Systems (WMSs) [START_REF] Deelman | Pegasus, a workflow management system for science automation[END_REF]; [START_REF] Fahringer | Askalon: A development and grid computing environment for scientific workflows[END_REF]; [START_REF] Wilde | Swift: A language for distributed parallel scripting[END_REF]; [START_REF] Wolstencroft | The taverna workflow suite: designing and executing workflows of web services on the desktop, web or in the cloud[END_REF]; [START_REF] Altintas | Kepler: an extensible system for design and execution of scientific workflows[END_REF]; [START_REF] Albrecht | Makeflow: A portable abstraction for data intensive computing on clusters, clouds, and grids[END_REF]), the default behavior is that all output data is saved to files and all input data is read from files, which is exactly the CKPTALL strategy. While this strategy leads to fast restarts in case of failures, its downside is that it maximizes checkpointing overhead.

At the other end of the spectrum would be a checkpoint nothing strategy, or CKPTNONE, by which all output data is kept in memory (up to memory capacity constraints) and no task is checkpointed. This corresponds to "in-situ" workflow executions, which has been proposed to reduce I/O overhead [START_REF] Zhang | Enabling In-situ Execution of Coupled Scientific Workflow on Multi-core Platform[END_REF]). The downside is that, in case of a failure, a large number of tasks may have to be re-executed, leading to slow restarts. The objective of this work is to achieve a desirable trade-off between these two extremes. To the best of our knowledge, no general solution is available. We build upon our previous work (Han et al. (2018a)) that was restricted to M-SPGS (Minimal Series-Parallel Graphs) [START_REF] Valdes | The recognition of series parallel digraphs[END_REF]). In (Han et al. (2018a)), we took advantage of the recursive structure of M-SPGS and used proportional mapping [START_REF] Pothen | A mapping algorithm for parallel sparse cholesky factorization[END_REF]) for scheduling and checkpointing M-SPG workflows as sets of superchains. For general graphs, we have to resort to classical scheduling heuristics such as HEFT [START_REF] Topcuoglu | Performance-effective and low-complexity task scheduling for heterogeneous computing[END_REF]) and MINMIN [START_REF] Braun | A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems[END_REF]), two reference scheduling algorithms widely used by the community. We provide extensions of HEFT and MINMIN that allow for a smaller subset of tasks to be checkpointed and lead to better makespans than the versions where each task (CKPTALL) or no task (CKPTNONE) is checkpointed.

The main contributions of this paper are the following:

• We deal with arbitrary dependence graphs, and require no graph transformation before applying our scheduling and checkpointing algorithms. • We compare several mapping strategies and combine them with several checkpointing strategies.

• We design an event-based simulator to evaluate the makespan of the proposed solution. Indeed, computing the expected makespan of a solution is a difficult problem (Han et al. (2018a)), and simple Monte-Carlo based simulations cannot be applied to general DAGs unless all tasks are checkpointed: otherwise, sampling the weight distribution for each task independently is not enough to compute the makespan, since a failure may involve re-executing several tasks (as shown in Section 2). • We report extensive experimental evaluation with both real-world and randomly generated workflows to quantify the performance gain achieved by the proposed approach. The rest of the paper is organized as follows. First in Section 2, we work out an example to help understand the difficulty of the problem. Then we introduce the performance model in Section 3. We detail our scheduling and checkpointing algorithms in Section 4. We give experimental results in Section 5. Section 6 surveys the related work. Finally, we provide concluding remarks and directions for future work in Section 7.

Example

In this section, we illustrate the difficulty of deciding where to place checkpoints in a workflow. Consider the example of Figure 1 with 9 tasks, T i , 1 ≤ i ≤ 9, that have been mapped on 2 processors as shown on the figure. Note that this DAG cannot be reduced to an M-SPG and our previous approach (Han et al. (2018a)) cannot be applied for this graph. While most tasks are assigned to processor P 1 , some tasks are assigned to the second processor, P 2 , to exploit the parallelism of the DAG. Any dependence between two tasks represents a file that is required to start the execution of the successor task; hence, T 1 → T 2 represents a file produced by task T 1 that is required for the execution of task T 2 to start. Because T 1 and T 2 are both executed on processor P 1 , this file is kept in the memory of P 1 after T 1 completes. However, for the dependence T 1 → T 3 , because the tasks T 1 and T 3 are executed on different processors, the corresponding file must Prepared using sagej.cls

P 1 P 2 T 1 T 2 T 3 T 4 T 5 T 6 T 7 T 8 T 9 Figure 3.
A purple crossover checkpoint is performed for each file produced by one processor and used by another one.

T 1 13 T 2 T 1 T 2 T 3 34 T 5 13 T 3 T 5 59 be retrieved by P 2 . Such a dependence between two tasks assigned to two different processors is called a crossover dependence.

In a first scenario, let us suppose that no task is checkpointed as showed in Figure 1: then if no failure strikes, the makespan will be the shortest possible, consisting only of the execution time of each task and of retrieving the necessary input files. However, as soon as a failure happens, we may need to restart the whole application from the very beginning. To study such a scenario, we need to explicit the memory management. Let us assume that once a processor has sent a file to another processor, then this file is deleted from the memory of the producing processor. For instance, as soon as P 2 has received from P 1 the file corresponding to the dependence T 1 → T 3 , this file is erased from the memory of P 1 . Remember that a failure wipes out the whole content of the memory of the struck processor. Thus, if a failure strikes during the execution of T 5 , to be able to re-attempt to execute T 5 , T 3 will need to be re-executed before (because the file T 3 → T 5 is no longer available), which requires T 1 to be re-executed first (because the file T 1 → T 3 is no longer available). Hence, a single failure in a part of the graph may require the re-execution of most of the workflow, which is known as the domino effect in fault tolerance protocols and needs to be mitigated. Figure 2 shows an example of execution of the DAG when no task is checkpointed. To execute T 4 , we need both T 2 and T 3 to finish successfully, and that no fault strikes neither P 1 nor P 2 between the completion of these tasks and the start of T 4 . Here, T 2 does not finish so T 1 is re-executed. When P 2 fails, we need to re-execute T 3 , which requires input from T 1 . Luckily (!), P 1 already suffered from a failure, so T 1 has already been re-executed. Otherwise, we would have had to restart the execution of the whole workflow because of the failure of P 2 .

To avoid rolling back to the beginning in case of failures, we can try to place some checkpoints inside the workflow. As commonly assumed in workflow management systems [START_REF] Deelman | Pegasus, a workflow management system for science automation[END_REF]; [START_REF] Fahringer | Askalon: A development and grid computing environment for scientific workflows[END_REF] 2012)), any file produced by one processor and required by another processor is necessarily saved to stable storage. Thus, an error on one processor will not lead to re-execution on another processor. In the second scenario shown in Figure 3, we decide to checkpoint every crossover dependence (from T 1 to T 3 , T 3 to T 4 , and T 5 to T 9 ). An execution of that schedule is shown in Figure 4. Cyan boxes represent checkpoints while yellow boxes represent data being read. We can see that thanks to the crossover checkpoints, T 4 does not need to wait for the completion of the second execution of T 3 anymore, as T 3 output data has already been checkpointed. Moreover, if only a failure on P 2 happened, instead of rolling back to task T 1 to reexecute T 3 as it was the case before, T 3 could have restarted directly (although the entire content of the processor memory is lost, so all inputs of T 3 must be recovered from stable storage after a downtime before the execution of T 3 can restart). Note that we start executing the target task of a crossover dependence after checkpointing, to make sure that all files needed are available in the stable storage in case of failure. The motivation to checkpoint all files involved in crossover dependences is to isolate the processors. Indeed, if all crossover files are checkpointed, a failure on a processor will never lead to the re-execution of a task successfully executed on another processor. Overall, we will lose less time recomputing tasks or waiting for their second completion. However, reading from stable storage and checkpointing also take time. Finding the right trade-off is the main focus of this paper: deciding which tasks should be checkpointed, so that the overhead added by the checkpointing and reading of files is not more expensive than the re-execution of tasks.

We conclude by informally introducing examples of checkpointing strategies that achieve desirable trade-offs (see Section 4.2 for details). Two additional checkpoints, in blue, called induced checkpoints, have been added in Figure 5. Their role is to secure the fast re-execution of tasks that are the target of a crossover dependence, namely T 4 and T 9 . The blue checkpoint after T 2 isolates the execution of the task sequence S 1 = {T 4 , T 6 , T 7 , T 8 } on P 1 . To this purpose, it is necessary to checkpoint all intermediate results that may

P 1 P 2 T 1 T 2 T 3 T 4 T 5 T 6 T 7 T 8 T 9
Figure 5. Blue induced checkpoints are used to isolate task sequences on a processor (labeled in green, such as the sequence T4, T6, T7 and T8 on P1). Finally, additional checkpoints can be added inside an idle-free task sequence through a dynamic programming algorithm: the orange checkpoint corresponds to such an addition.

be used after the execution of T 2 : these are the files generated by previous tasks, namely T 1 → T 7 and T 2 → T 4 , This way, when a failure strikes, previous tasks do not have to be restarted and the computation may be restarted directly from T 4 . This way, tasks in the sequence S 1 may be sequentially executed without idle time. It would not have been possible to include T 1 and T 2 in S 1 because T 4 could have waited for the completion of T 3 leading to idle time in some scenarios.

Similarly, the second blue checkpoint isolates the execution of T 9 . Finally, once the four tasks T 4 , T 6 , T 7 , and T 8 of the sequence S 1 have been "isolated" from other tasks, it is possible to use a dynamic programming algorithm similar to that used in (Han et al. (2018a)) in order to introduce additional checkpoints. In the example of Figure 5, a single additional checkpoint, in orange, is inserted after T 7 .

Model

This section details the execution and fault-tolerance models used to compare scheduling and checkpointing algorithms.

Execution Model

The execution model for a task workflow on a homogeneous system is represented as a Directed Acyclic Graph (DAG), G = (V, E), where V is the set of nodes corresponding to the tasks, and E is the set of edges corresponding to the dependences between tasks. In a DAG, a node without any predecessor is called an entry node, while a node without any successor is an exit node. For a task T in G, pred (T ) and succ(T ) represent the set of its immediate predecessors and successors respectively. We say that a task T is ready if either it does not have any predecessor in the dependence graph, or if all its predecessors have been executed.

In this model, the execution time of a task T i ∈ V is w i , i.e., its execution time in a failure-free execution. Each dependence (T i , T j ) ∈ E is associated with the cost c i,j to store/read the data onto/from stable storage. In some realworld instances from [START_REF] Pegasus | Pegasus workflow generator[END_REF]), a task may generate multiple files for different successors or generate the same file for more than one successor task. Direct communications between processors take place through a communication network which is much faster than writing/reading from the stable storage. Before the execution of T j on processor P k , all input files needed by T j must be present in the local memory of P k . Suppose that T j needs a file from T i executed on processor P l , it will first try to retrieve the file from the local memory of P l . The start time of T j is max{t cij , (t avail k + t c )}, where t cij is the finish time of checkpointing the file transferred from T i to T j , t avail k donates the available time on processor P k , and t c is the communication time. We start executing the task after checkpointing the crossover dependence, to make sure that all files needed are available in the stable storage in case of failure. If the file is absent from local memory of P l , then it must be read from the stable storage.

Fault-Tolerance Model

In this work, each processor is a processing element that is subject to its own individual failures. Failures can strike a processor at any time, during either task execution or waiting time. Failure inter-arrival times are assumed to be Exponentially distributed. These failure-prone processors stop their execution once a failure strikes, i.e., we have failstop errors. When a fail-stop error strikes a processor, the whole content of its memory is lost and the computation it was performing must be restarted, either on the same processor after a reboot, or on a spare processor (e.g., taken from a pool of spare processors either specifically requested by the job submitter, or maintained by the resource management infrastructure).

Consider a single task T , with weight w, scheduled on such a processor, and whose input is stored on stable storage. The total execution time W of T is a random variable, because several execution attempts may be needed before the task succeeds. We assume that failures are i.i.d. (independent and identically distributed) across the processors and that the failure inter-arrival times at each processor is Exponentially distributed with Mean Time Between Failures (MTBF) µ = 1/λ. Let λ 1 be the Exponential failure rate of the processor. With probability e -λw , no failure occurs, and W is equal to w. With probability (1 -e -λw ), a failure occurs. For Exponentially distributed failures, the expected time to failure, knowing that a failure occurs during the task execution (i.e., in the next w seconds), is 1/λw (e λw -1) (Hérault and Robert (2015)). After this failure, there is a downtime d, which is (an upper bound of) the time needed to reboot the processor or migrate to a spare. Then we start the execution again, first with the recovery r, the time to read data from stable storage, and then the work w. With a general model where an unbounded number of failures can occur during recovery and work, the expected time W to execute task T is given by W = 1 λ + d e λr e λw -1 (Hérault and Robert ( 2015)). Now if the output data of task T is checkpointed, with a time c to write all of its output files onto stable storage, the total time Prepared using sagej.cls becomes:

W = 1 λ + d e λr e λ(w+c) -1 . (1)
Equation ( 1) assumes that failures can also occur during checkpoints, which is the most general model for failures.

We also assume that failures may strike during the idle time (i.e., waiting time) of the processor (e.g., the power supply may fail). In the case of a sequence of non-checkpointed tasks to be executed on a processor P , the output data of each task resides in the memory of P for use by subsequent tasks. When a failure strikes P , the entire memory content is lost and the whole task sequence must be re-executed from scratch.

Problem Formulation

Given a DAG and a set of processors on which fail-stop failures strike with Exponentially distributed inter-arrival times, the objective is to schedule the task executions and potential checkpoints such that the expected completion time (or makespan) is minimized. Due to delays resulting from the faults, the schedule of the tasks consists of an assignment to processors and of a task ordering. Each processor executes tasks as soon as possible and resumes their processing when a failure strikes. Finally, the schedule of the checkpoints is the (possibly empty) list of files that must be checkpointed after each task execution.

Scheduling and checkpointing algorithms

In this section, we first present heuristics to map tasks to processors. Then we propose three different checkpointing strategies that can be used simultaneously.

Scheduling heuristics

We map tasks to processors and schedule them using two classical scheduling heuristics, HEFT [START_REF] Topcuoglu | Performance-effective and low-complexity task scheduling for heterogeneous computing[END_REF]) † and MINMIN [START_REF] Braun | A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems[END_REF]). We run these heuristics as if the platforms were not subject to failures, that is, without considering checkpoints. Therefore, we decide first on which processor a task will be executed, and the order in which a processor will execute tasks, before deciding when and what to checkpoint (see Section 4.2). However, we present variants of HEFT and MINMIN, named HEFTC and MINMINC, that are specifically designed for our failureprone framework.

Heterogeneous Earliest Finish Time first (HEFT) is presented as the HEFTC variant in Algorithm 1. The original HEFT algorithm comprises two phases. In a first task prioritizing phase, the bottom-level of all tasks is computed and tasks are ordered by non-increasing bottom-levels. The bottom-level of a task is the maximum length of any path starting at the task and ending in an exit task, considering that all communications take place [START_REF] Darte | Scheduling and automatic parallelization[END_REF]). In the second processor selection phase, the first unscheduled task is scheduled as early as possible on a processor that minimizes its completion time. In all cases, ties are broken arbitrarily. To these original two phases, we add a third one, the chain mapping phase (lines 7 and 8 of Algorithm 1).

If the newly mapped task T is the head of a chain in the task graph, which means T only has one successor whose only predecessor is T , then this whole chain is mapped on the same processor as T , and the tasks will be executed consecutively. Ensuring that entire chain of tasks are scheduled on the same processor decreases the number of crossover dependences and thus, the time to checkpoint them. HEFTC has a complexity of O(n 2 ) for a workflow with n tasks. During the processor selection phase, the earliest finish time of a task is computed in HEFTC while assuming that the newly mapped task must start after all tasks previously scheduled on that processor have completed. On the contrary, the original HEFT heuristic is allowed to perform backfilling following a classical insertion-based policy, as long as the completion time of no task is delayed. Allowing backfilling is more expensive at scheduling time but should lower the execution time (the complexity of HEFT with backfilling is also O(n 2 ) with homogeneous processors). We do not allow backfilling for HEFTC because it could be antagonistic to the chain mapping phase if it led to backfill the head of the chain, but not the whole chain. The MINMIN scheduling algorithm is presented in the MINMINC variant in Algorithm 2. The original MINMIN algorithm is a simple loop which, at each step, schedules the task that can finish the earliest among unscheduled tasks. Therefore, at each step it considers all ready tasks and, for each of them, all the processors. We (try to) improve this heuristic by adding a chain mapping phase exactly as previously (lines 5 and 6 of Algorithm 2). MINMINC has a complexity of O(n 2 p) for a workflow with n tasks and p processors.

Checkpointing strategies

While the previous scheduling algorithms provide mappings of tasks to processors, it remains to decide which files must be checkpointed and when. This section introduces finer strategies than the two extremes solutions that consist of checkpointing no task or all tasks. These two extreme solutions, CKPTNONE and CKPTALL, are denoted with the suffixes NONE and ALL, respectively. The minimum strategy that is required to isolate processors consists in checkpointing all files that must be transferred between any pair of processors, i.e., exactly the files corresponding to crossover dependences. In this case, any failure on a processor will not require any re-execution on other processors. The strategy is denoted with a "C" in the checkpoint suffix.

For the next two additional strategies, we introduce a new type of checkpoints: task checkpoints. While a simple file checkpoint consists of writing to stable storage a file that corresponds to a dependence between two tasks, a task checkpoint consists of writing all files that (i) reside in memory on a processor; (ii) will be used later by tasks assigned to the same processor; and (iii) have not already been checkpointed. In the example in Section 2, for each crossover dependence we did a simple file checkpoint rather than a full task checkpoint. A task checkpoint after task T 3 would have also checkpointed the file corresponding to the dependence T 3 → T 5 . A non-trivial task checkpoint for the example of Section 2 would be a task checkpoint for task T 2 . This checkpoint would require checkpointing the files corresponding to the dependences T 2 → T 4 and T 1 → T 7 .

When a task checkpoint is performed after the execution of a task, multiple files may be checkpointed "at the same time" (either newly created files or previously created ones that will later be used). If several files are checkpointed, they are all checkpointed after the task completion, one after the other (in any order). When absent from memory (following a failure), input files are read from stable storage as late as possible, just before the execution of the task that needs them.

Checkpointing crossover dependences enable to isolate processors, in that there is no re-execution propagation from a processor to another. However, when a task is the target of a crossover dependence, its starting time is the maximum of the availability times of all its input files, and these files come from different processors. Therefore, its starting time may be delayed by failures occurring on other processors. Because failures can strike during idle time, it may be beneficial to try to use the potential waiting time by performing a task checkpoint of the task preceding the target task. This way, the whole content of the memory will be preserved, the cost of the checkpoint may be offset by some waiting time, and if a failure strikes during the remaining waiting time all input files remain available. Therefore, we propose a new checkpointing strategy denoted with "I" in the checkpoint suffix. This strategy consists of checkpointing all induced dependences. A dependence T i → T j is an induced dependence if T i and T j are scheduled on the same processor P and there exists a crossover dependence T k → T l such that T l is scheduled on P after T i and before T j (or T l = T j ). Checkpointing these induced dependences is done by performing a task checkpoint of the task preceding T l on P . In the example of Section 2, the dependences T 2 → T 4 and T 1 → T 7 are both induced dependences because of the crossover dependence T 3 → T 4 . As a side note, we point out that our induced checkpoints are not related to those introduced in [START_REF] Baldoni | A communication-induced checkpointing protocol that ensures rollback-dependency trackability[END_REF]) to track consistency among execution traces of general applications: we deal with simple task graphs and can easily regenerate missing data by following the dependences.

So far, we have only introduced checkpoints to isolate processors, either to avoid failure propagation or to try to minimize the impact of processors having to wait from each other. We further consider checkpoints that more directly optimize expected total execution time. We present an additional strategy, denoted by the suffix "DP", which adds additional checkpoints through a O(n 2 ) dynamic programming algorithm, which is a transposition of that of (Han et al. (2018a)). This dynamic program considers a maximal sequence of consecutive tasks that are all assigned to the same processor, and that are isolated from other tasks: the sequence contains no checkpoint and none of its tasks is the target of a crossover dependence, except for its first task. Let T 1 , ..., T k be such a sequence of tasks. By definition, all input data produced by some previous tasks have been checkpointed. Then, the optimal expected time to execute this sequence is given by Time(k) where Time is defined as follows:

Time(j) = min T (1, j), min 1≤i<j Time(i) + T (i + 1, j)
where T (i, j) is the expected time to execute tasks T i to T j provided that two task checkpoints are performed: one right before task T i and one right after task T j . Using the same reasoning as in Section 3.2, we can provide an upper bound on T (i, j) as follows:

T (i, j) = 1 λ + d e λ(R j i +W j i +C j i ) -1
where R j i (resp. W j i and C j i ) is the sum of the recovery (resp. execution and checkpointing) costs of tasks T i to T j . The recovery costs concern all input files of these tasks that are on the stable storage, while the checkpointing costs concern all files that will be checkpointed when a task checkpoint is done after T j . This is an upper bound, because when no failure strikes, some input files of tasks T i to T j may already be present in memory and will not be read from stable storage. Because we have no simple mean to know whether some failures had previously struck, we have to resort to this upper bound. This is a necessary condition to be able to reuse, in some way, the dynamic programming approach of (Han et al. (2018a)). This algorithm requires, by construction, that induced dependences be checkpointed. However, we heuristically use it even when this condition is not satisfied. In this case, we take a maximal sequence while allowing tasks to be the target of crossover dependences, and behave as if these crossover dependences were not existing: we discard any potential waiting time that may be due to these crossover dependences (because we have no means to estimate them).

Experiments

In this section, we describe the experiments conducted to assess the efficiency of the checkpointing strategies.

In Subsection 5.1, we describe the parameters and applications used during our experimental campaign, then in Subsection 5.2 we present the simulator used to run the applications and simulate the behavior of large-scale platforms. Finally, we present our results in Subsection 5.3.

Experimental methodology

We consider workflows from real-world applications, namely representative workflow applications generated by the Pegasus Workflow Generator (PWG) [START_REF] Da Silva | Community resources for enabling research in distributed scientific workflows[END_REF]; [START_REF] Bharathi | Characterization of scientific workflows[END_REF]; [START_REF] Juve | Characterizing and profiling scientific workflows[END_REF]), as well as the three most classical matrix decomposition algorithms (LU, QR, and Cholesky) [START_REF] Choi | Design and implementation of the scalapack lu, qr, and cholesky factorization routines[END_REF]), and randomly generated DAGs from the Standard Task Graph Set (STG) [START_REF] Tobita | A standard task graph set for fair evaluation of multiprocessor scheduling algorithms[END_REF]).

Pegasus workflows. PWG uses the information gathered from actual executions of scientific workflows as well as domain-specific knowledge of these workflows to generate representative and realistic synthetic workflows (the parameters of which, e.g., the total number of tasks, can be chosen). We consider all of the five workflows [START_REF] Pegasus | Pegasus workflow generator[END_REF]) generated by PWG, including three M-SPGS (GENOME, LIGO, and MONTAGE) that are used to compare our new general approach with PROPCKPT, the strategy for M-SPGS proposed in (Han et al. (2018a)).

• MONTAGE: The NASA/IPAC Montage application stitches together multiple input images to create custom mosaics of the sky. The average weight of a MONTAGE task is 10s. Structurally, MONTAGE is a three-level graph [START_REF] Deelman | Pegasus: A framework for mapping complex scientific workflows onto distributed systems[END_REF]). The first level (reprojection of input image) consists of a bipartite directed graph. The second level (background rectification) is a bottleneck that consists of a join followed by a fork. Then, the third level (co-addition to form the final mosaic) is simply a join. Structurally, the CYBERSHAKE workflow starts with several forks. Then each of the forked tasks has two dependences: one to a single task (join) and one to a specific task for each of the tasks. Finally, all these new tasks are joined without another dependence this time.

• SIPHT: The SIPHT workflow, from the bioinformatics project at Harvard, is used to automate the search for untranslated RNAs (sRNAs) for bacterial replicons in the NCBI database. The average weight of a SIPHT task is 190s. Structurally, the SIPHT workflow is composed of two different parts that are joined at the end: the first one is a series of join/fork/join, while the other is made of a giant join. We generate these workflows with 50, 300, and 700 tasks (these are the number of tasks given to the generator, the actual number of tasks in the generated workflows depend on the workflow shape). The task weights and file sizes are generated by PWG. In some instances, a single file may be used by more than one task and a dependence may represent multiple files to transfer between two tasks. In the first case, whenever a file is common to multiple dependences, the file is only saved once. In the second case, files are aggregated into a single one.

Matrix factorizations. We consider the three most classical factorizations of a k × k tiled matrix: LU, QR, and Cholesky factorizations.

• The LU decomposition is the factorization of any matrix into a product of one lower-triangular (L) and one upper-triangular (U) matrices. Structurally, the DAG is made of k steps, with at step i, one task having two sets of k -i -1 children, and each pair of tasks between the two sets having another child. • The QR decomposition is the decomposition of a matrix into a product of an orthogonal matrix (Q) and upper-triangular matrix (R), i.e., A = QR with QQ T = Id. Structurally, the QR decomposition looks like the LU decomposition but it has more complex dependences between the k -i -1 children at step i. • Cholesky is a factorization of a positive and definite matrix into the product of a triangular matrix and its transpose, i.e., A = BB T where B is lowertriangular and has non-zero values of the diagonal. The Cholesky decomposition DAG is the representation of a panel algorithm and can be constructed recursively by removing the first row and the first column of submatrices, to keep factorizing the trailing matrix. For each factorization, we perform experiments with k = 6, 10, and 15, for a total of 3 × 3 = 9 DAGs with up to 1240 tasks. The number of vertices in the DAG depends on k as follows: the Cholesky DAG has 1 3 k 3 + O(k 2 ) tasks, while the LU and QR DAGs have 2 3 k 3 + O(k 2 ) tasks. There are 4 types of tasks in LU, QR, and Cholesky, which are labeled by the corresponding BLAS kernels [START_REF] Choi | Design and implementation of the scalapack lu, qr, and cholesky factorization routines[END_REF]), and their weights are based on actual kernel execution times as reported in [START_REF] Augonnet | Starpu: a unified platform for task scheduling on heterogeneous multicore architectures[END_REF]) for an execution on Nvidia Tesla M2070 GPUs with tiles of size b = 960.

Random graphs. The STG benchmark [START_REF] Tobita | A standard task graph set for fair evaluation of multiprocessor scheduling algorithms[END_REF]) includes 180 instances for each size of DAGs (from 50 to 5 000). This set is often used in the literature to compare the performance of scheduling strategies. Instead of choosing part of the instances for each size, we did experiments on all instances of size 300 and 750. For each instance, one of the four DAG generators specifies the structure of the dependences (e.g., layer-by-layer) and one of the six cost generators provides the distribution of the processing times (e.g., uniform).

Failure distribution. In the experiments, we consider different exponential processor failure rates. To allow for consistent comparisons of results across different DAGs (with different numbers of tasks and different task weights), we simply fix the probability that a task fails, which we denote as p fail , and then simulate the corresponding failure rate. Formally, for a given DAG G = (V, E) and a given p fail value, we compute the average task weight as w = i∈V w i /|V |, where w i is the weight of the i-th task in V . We then pick the failure rate λ such that p fail = 1 -e -λ w. We conduct experiments for three p fail values: 0.01, 0.001, and 0.0001.

Checkpointing costs. An important factor that influences the performance of checkpointing strategies, and more precisely of the checkpointing and recovery overheads, is the data-intensiveness of the application. We define the Communication-to-Computation Ratio (CCR) as the time needed to store all the files handled by a workflow (input, output, and intermediate files) divided by the time needed to perform all the computations of that workflow on a single processor. For Pegasus workflows, LU, QR, and Cholesky, we vary the CCR by scaling file sizes by a factor. As STG only provides task weights, we compute the average communication cost as c = w × CCR. Communication costs are generated with a lognormal distribution with parameters µ = log(c) -2 and σ = 2 to ensure an expected value of c. This distribution with parameter σ = 2 has been advocated to model file sizes [START_REF] Downey | The structural cause of file size distributions[END_REF]). This allows considering and quantifying the data-intensiveness of all workflows in a coherent manner across experiments and workflow classes and configurations.

Reference strategies. In the experiments, we compare our strategies to the two extreme approaches CKPTALL and CKPTNONE. We use the simulator described in Subsection 5.2. For each parameter setting of each workflow, we run 10,000 random simulations and approximate the makespan by the observed average makespan.

Simulator

In order to evaluate the performance of our strategies, we implemented a discrete event simulator. The C++ code for the simulator is available at http://github.com/ vlefevre/task-graph-simulation. To simulate the execution of applications on large-scale platforms, we operate in three steps:

1. We first read an input file describing the task-graph and the scheduling/mapping strategy; 2. Then we generate a set of fail-stop error times for each processor during a time horizon (that is set by the user); 3. Finally, we execute ready tasks by mapping them to a processor and we keep doing this until all tasks are executed. The first part is basically reading a file that describes the following important elements for the simulation:

• For each task, its ID, its weight (i.e., duration), the ID of the processor it has been mapped to,

several booleans indicating whether the task has to be checkpointed or not, one for each checkpointing strategy. • For each dependence between two tasks, the ID of the parent, the ID of the child, the list of files with their time to be loaded/written that creates the dependence (i.e., there are some of the output files of the parent and some of the input files of the child). • For each processor, its schedule: a list of tasks that have been mapped to it and that respects the causal order of the task-graph.

The second part is done by using the inversion sampling method: we generate error times according to a random variable that follows an exponential distribution, and this exponential distribution is generated from an (assumed) uniform distribution between 0 and 1 obtained by calling the C function rand(), and dividing its result by the C constant RAND_MAX. In our case, if U is a random variable following a uniform distribution between 0 and 1, then -log U λ follows an exponential distribution of parameter λ. We generate errors on each processor, until the time of one error is greater than the horizon parameter. In the experiments, it was set to at least 2 times the expected makespan we have with the CKPTALL strategy, which we computed using the Monte-Carlo method. In practice, most of the simulations were done before the horizon was reached except for NONE with large p fail .

For the last step, we keep a global time t on all the processors, and we generate events happening on each processor (either a failure or the successful completion of a task). Each processor holds the time of its last event in a variable t i . At each moment of the simulation, we have t i ≥ t, ∀i. The algorithm repeats these steps until all tasks are marked executed:

• For each processor p i , we look at the next task to be executed on p i (following the list scheduling given as input) if the current task is finished at time t; if it is ready, we compute its full execution time by computing the time of reading the necessary input files, the weight of the task (given as input) and potentially some writing (in case of crossover dependences or if the checkpoint strategy requires this task to be checkpointed); we look at the next error happening after time t:

if it is before the end of the task then we set t i to be the time of that failure, otherwise t i is set to the time when the task ends and the task is marked executed.

• We set t = min i t i .
There are two more things to detail: the computation of reading times and how we rollback when there is a failure. For the first problem, we keep a set of all files loaded on each processor. Before reading an input file, we check if it is already loaded (i.e., belongs to that set). If it is already loaded, we count a cost of 0, otherwise we add the communication/reading time for that file that is given as input. Files are added to the set whenever they are loaded or written (not necessarily a checkpoint). The set is cleared whenever a fail-stop error strikes on the processor.

When there is a failure, the rollback is easy because we always checkpoint crossover dependences. This implies that a failure on a processor p i will only impact the tasks that have been executed on p i since the last checkpointed task that was mapped to p i . To rollback we explore the list of tasks backward from the current task to the last checkpointed one (we keep two pointers on these two tasks at each time to access them instantaneously), we mark each task unexecuted, we clear the set of loaded files and we can start simulating again from the last checkpointed task as if nothing happened. In the case of CKPTNONE, the simulation is rolled back from the first task anytime an execution or communication is interrupted.

Finally, the simulator computes the following measures: the number of file checkpoints taken, the number of task checkpoints taken, the number of failures, the total time spent checkpointing data and the execution time of the application.

Results

In this section, we first compare the expected makespan of our proposed checkpointing strategies (CDP and CIDP) over two baseline strategies (ALL and NONE) with the same task mapping and scheduling strategy. Remind that "C", "I" and "DP" stands for checkpointing crossover dependences, checkpointing induced dependences and dynamic programming respectively. Then, we compare the solutions (different task mapping and scheduling heuristics combined with several checkpointing strategies) from this work with the method PROPCKPT proposed in (Han et al. (2018a)) for M-SPGS.

In Figures 6-10, we compare the four considered task mapping and scheduling strategies: HEFT and MINMIN, with their chain-mapping variants HEFTC and MINMINC using boxplots ‡ . On these figures, the lower the better and the baseline at 1 is the performance of HEFT. The chainmapping variants have the same performance or improve that of their basic counterparts, especially when communications are expensive (rightmost parts of the graphs). The other conclusion is that MINMIN (resp. MINMINC) almost always achieves same or worse performance than HEFT (resp. HEFTC). This is easily explained by the fact that HEFT and HEFTC take into account the critical path of workflows. These trends are representative of the trends that can be observed for all considered graphs and workflows, but suffer from some exceptions. The chain-mapping variants can be superceded by their basic counterparts for workflows that do not include any chains (like LU in Figure 7), because the basic variants can use backfilling. However, backfilling sometimes backfires, even in the absence of chains, like for SIPHT in Figure 9 where HEFTC can decrease the expected makespan by more than 30% with respect to HEFT. Overall, of the four considered task mapping and scheduling heuristics, HEFTC never achieves significantly bad performance, and most of the time achieves the best performance. This is the reason why we focus on it in the remainder of this section.

Figures 11 through 18 present the expected makespans achieved by CDP, CIDP and NONE divided by that of ALL when the Communication-to-Computation Ratio increases.

Therefore, the lower the better and data points below the y = 1 line denote cases in which these strategies outperform the competitor ALL (i.e., achieve a lower expected makespan). Each figure shows results for workflows with different number of tasks, ranging from 50 to 1240 tasks (each line of subfigure is for a different size, the number of tasks being reported on the rightmost column), for various number of processors P (different line styles), and for the three p fail values (0.0001, 0.001, 0.01). We report on these figures the average number of failures that occur for the 10,000 random trials for each setting. These numbers are reported in black above the horizontal axis in each figure. The other two lines of numbers are the number of checkpointed tasks for the CDP and CIDP strategies, each number is printed with the same color as the curve of the corresponding strategy.

A clear observation is that CIDP never achieves worse performance than ALL: either it achieves a similar performance or it outperforms ALL, especially when communications, and thus checkpoints, are expensive (in the rightmost parts of graphs). It should be noted that when checkpoints come for free (leftmost parts of graphs), ALL and CIDP have the same performance as they do the same thing: they checkpoint all tasks. When the number of failures rises, the optimal solution is to checkpoint more tasks, potentially all of them, and the gain of CIDP with respect to ALL therefore decreases. This can be seen, for instance, on Figure 12 when p fail = 0.01, n = 385 and there are 385 tasks checkpointed.

In the majority of cases, CDP also achieves similar or better performance than ALL. As we explained in Section 4, the dynamic programming algorithm is well-defined for CIDP, which checkpoints all induced dependences. However, CDP tries to save some checkpointing overhead by not systematically checkpointing induced dependences. As a consequence, the dynamic programming algorithm estimations of expected execution times may be inaccurate, which explains the sometimes bad performance of CDP. There are only a couple of CCR values for CYBERSHAKE for which CDP achieves a significantly worse performance than ALL. On the contrary, CDP often has better performance than CIDP when checkpointing cost is high. In all scenarios, CDP checkpoints less or the same number of tasks than CIDP. Depending on the checkpointing cost and failure rate, CDP can lead to significant improvement over ALL. For workflows as dense as LU, we save more than 10% when CCR = 1 for both strategies, and CDP even achieves 35% saving for SIPHT. As the CCR decreases, the ratio converges to 1. As already pointed out, this is because both strategies decide to checkpoint most, if not all, tasks, when checkpointing becomes cheaper.

CDP and CIDP achieve better results than NONE except when (i) checkpoints are expensive (high CCR) and/or (ii) failures are rare (low p fail ). In these cases, checkpointing is a losing proposition, and yet our strategies, by design, always checkpoints some files (they checkpoint all crossover files and even induced dependences for CIDP). In practice, in such cases, the optimal approach is to bet that no failure will happen and to restart the whole workflow execution from scratch upon the very rare occurrence of a failure. NONE becomes worse whenever there are more failing tasks, i.e., when the failure rate increases (going from the leftmost column to the rightmost one in the figures), and/or when the number of tasks increases (going from the topmost row to the bottom one in the figures). When the failure rate is high and the workflows are large (the bottom right corner of the figures), the relative expected makespan of NONE is so high that it does not appear in the plots. The above results, and our experimental methodology in general, make it possible to identify these cases so as to select which approach to use in practical situations. We summarize the major observations in Table 1:

Figure 19 presents the aggregated results for the 180 STG random DAGs with boxplots. The trends on these graphs are the same as already reported. This confirms the generality of our conclusions.

Finally, we compare our new general approach with PROPCKPT, the approach specific to M-SPGS that we proposed in (Han et al. (2018a)). Figures 202122present this comparison for Montage, Ligo and Genome, which are the three M-SPGS presented in (Han et al. (2018a)). Overall, the new approaches perform better than PROPCKPT.

Related work

Checkpointing workflows has received considerable attention in the recent years, but no satisfactory solution has yet been proposed for fail-stop failures and general DAGs.

Many authors [START_REF] Cao | Design for a soft error resilient dynamic task-based runtime[END_REF]; [START_REF] Jin | Performance Under Failures of DAG-based Parallel Computing[END_REF]; [START_REF] Kail | A novel adaptive checkpointing method based on information obtained from workflow structure[END_REF]) have considered soft errors, by which a task execution fails but does not lead to completely losing the data present in the processor memory. Fail-stop errors have far more drastic consequences than soft errors as they induce the loss of all data present in memory. Therefore they require different solutions. As discussed in Section 1, silent errors represent do not interrupt the execution of the task but corrupt its output data. Their net effect is the same, since a task must be re-executed whenever a silent error is detected. Their detection requires the use of some silent error detectors at the end of a task's execution. Two well-known examples of fault detectors are Algorithm-Based Fault Tolerance (ABFT) [START_REF] Huang | Algorithm-based fault tolerance for matrix operations[END_REF]; [START_REF] Bosilca | Algorithmbased fault tolerance applied to high performance computing[END_REF]; [START_REF] Shantharam | Fault tolerant preconditioned conjugate gradient for sparse linear system solution[END_REF]) and silent error detectors based on domain-specific data analytics [START_REF] Berrocal | Lightweight silent data corruption detection based on runtime data analysis for HPC applications[END_REF]; Bautista Gomez andCappello (2014, 2015)). As we only consider fail-stop errors we do not need to use fault detectors.

Relatively few published works have studied fail-stop failures, rather than soft and silent errors, in the context of workflow applications. In (Zhu et al. (2016)), Zhu et al. proposed an automatic checkpoint algorithm on Spark to solve the long lineage problem. Because of the lazy feature of transformation operation, one could get the logical graph (lineage) before an action (submitting a job). Their solution is just tracing back the lineage, find and keep all the RDDs which are created in the job with direct parents in the previous job so they could recompute from these RDDs to get all the RDDs in this job. This method is based on specific domain knowledge. In [START_REF] Lin | On improving fault tolerance for heterogeneous hadoop mapreduce clusters[END_REF]), they designed a checkpointing mechanism specifically for Map tasks, which creates a checkpoint at a specific percentage of a task in progress. Checkpoints are created when the progress reaches 0.5 or 0.25 by calculation progress rate and estimated task execution time. When the workflow consists of a linear chain of tasks, the problem of finding the optimal checkpoint strategy, i.e., determining which tasks to checkpoint, has been solved by [START_REF] Toueg | On the optimum checkpoint selection problem[END_REF]) using a dynamic programming algorithm. The algorithm of [START_REF] Toueg | On the optimum checkpoint selection problem[END_REF]) was later extended in [START_REF] Benoit | Assessing general-purpose algorithms to cope with fail-stop and silent errors[END_REF]) to cope with both fail-stop and silent errors simultaneously. When the workflow is general but comprised of parallel tasks that each executes on the whole platform, the problem of placing checkpoints is NP-complete for simple join graphs [START_REF] Aupy | Scheduling computational workflows on failure-prone platforms[END_REF]) (this is because the original workflow is not a chain but must be linearized). In the most general case, tasks of a workflow do not necessarily span the whole platform when executing. Existing work in this most general context diverges from ours as follows: either there is a limit to the number of failures that an execution can cope with [START_REF] Wang | Replicationbased fault-tolerance for large-scale graph processing[END_REF]), or the optimization objective is reliability [START_REF] Assayad | A bi-criteria scheduling heuristic for distributed embedded systems under reliability and real-time constraints[END_REF]), meaning that the application execution can fail altogether.

The only exception that we are aware of is our previous work (Han et al. (2018a)). The limitation of that work was different: the proposed solution could only deal with workflows whose structure was a Minimal Series-Parallel Graph (a generalization of Series-Parallel Graph). To the best of our knowledge, this work is the first approach (beyond application-specific solutions) that (i) does not resort to linearizing the entire workflow as a chain of (parallel) tasks; (ii) can be applied to any workflow; (iii) can cope with an arbitrary number of failures; (iv) always guarantees a successful application execution; and (v) minimizes the (expectation of) the application execution time. As a result, we propose the first DAG scheduling/checkpointing algorithm that allows arbitrary workflows to execute concurrently on multiple failure-prone processors in standard task-parallel fashion.

Conclusion

This work tackles the challenging problem of executing arbitrary workflows on homogeneous processors, with reasonable performance in presence of failures but without incurring a prohibitive cost when no failure strikes. While CKPTALL meets the first objective by expensively checkpointing every task and CKPTNONE meets the second one by avoiding any checkpoint at all, we propose new strategies that provide different trade-offs between these two extremes. First, all crossover dependences, corresponding to file transfers between processors, are checkpointed, which prevents re-execution propagation between processors in case of failure. Then, a DP (Dynamic Programming) solution is used to insert additional checkpoints to minimize the expected completion time. Additional (induced) checkpoints may be added prior to the DP execution to provide it with more accurate information. Moreover, different mapping strategies that extend classical ones to reduce the number of checkpoints were also proposed. To the best of our knowledge, these new strategies are the first to be tuned to minimize the need for checkpointing while mapping tasks. Extensive experiments with a discrete event simulator, conducted for both synthetic and realistic instances, show that our approaches significantly outperform CKPTALL and CKPTNONE in most scenarios. Future work will aim at extending our approach to workflows with parallel moldable tasks [START_REF] Drozdowski | Scheduling for Parallel Processing[END_REF]). Such an extension raises yet another significant challenge: now the number of processors assigned to each task becomes a parameter to the proposed solutions, with a dramatic impact on both performance and resilience. Zhu W, Chen H and Hu F (2016)

T 1 T 1 P 2 Figure 2 .

 1122 Figure 2. Sample execution of the workflow in Figure 1 without any checkpoint, with two failures striking during the execution of T2 on P1 and during that of T5 on P2.

34 T 4 1 P 2 Figure 4 .

 4124 Figure 4. Sample execution of the application in Figure 3 with two failures striking during the execution of T2 on P1 and that of T5 on P2, with crossover checkpoints. Label ij indicates the file from Ti to Tj. Now T4 can start before the re-execution of T3 since its output was checkpointed.

  ; Wilde et al. (2011); Wolstencroft et al. (2013); Altintas et al. (2004); Albrecht et al. (

1

  Compute the bottom-level of all tasks by traversing the graph from the exit tasks 2 Sort the tasks by non-increasing values of their bottom-levels 3 while there are unscheduled tasks do 4 Select the first task T i 5 k ← arg min 1≤k≤p EarliestFinishTime(T i , P k ) 6 Schedule task T i on processor P k 7 if T i is the head of a chain of tasks then 8 Schedule the whole chain continuously on P k

  Algorithm 2: MINMINC 1 ReadyTasks ← entry tasks 2 while there are unscheduled tasks do 3 Pick a task T ∈ ReadyTasks and a processor P such that the completion time of T on P is minimum among the Earliest Finish Times of all ready tasks 4 Schedule task T on processor P 5 if T is the head of a chain of tasks then 6 Schedule the whole chain continuously on P 7 Update ReadyTasks

Figure 6 .Figure 7 .Figure 8 .Figure 9 .Figure 10 .

 678910 Figure 6. Relative performance of the four task mapping and scheduling strategies for Cholesky.

Figure 14 .

 14 Figure 14. Performance of the different checkpointing strategies for Montage using HEFTC for task mapping and scheduling.

Figure 18 .

 18 Figure18. Performance of the different checkpointing strategies for CyberShake using HEFTC for task mapping and scheduling.

Figure 19 .Figure 20 .Figure 21 .Figure 22 .

 19202122 Figure19. Average performance of the different checkpointing strategies for the STG task graphs using HEFTC for task mapping and scheduling.

Table 1 .

 1 Identify suitable cases to apply each approach

	Strategy Description
	ALL	when checkpoints are free and/or extremely high p fail
	CIDP	always achieves a similar performance or outperforms ALL
	CDP	better than CIDP when checkpointing cost is high
	NONE	when checkpoints are expensive and/or extremely low p fail

  Performance of the different checkpointing strategies for Cholesky using HEFTC for task mapping and scheduling. Performance of the different checkpointing strategies for LU using HEFTC for task mapping and scheduling.

					pfail=0.0001						pfail=0.001							pfail=0.01
		1.00
		0.75																									strategy
		0.50																									56	CIDP
		0.25	50 28	50 25	50 23	50 23	50 23	50 23	50 21	50 17	51 51	50 37	50 28	50 25	50 23	50 23	50 21	50 17	56 56	56 56	51 51	50 37	50 29	50 26	50 26	50 24	CDP
		0.00	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	2	NONE
	Ratio to ALL	0.25 0.50 0.75 1.00 0.00 1.00	210 154 1	210 210 150 150 1 1	210 210 150 150 1 1	210 210 151 152 1 1	210 149 1	211 211 1	210 210 164 154 1 1	210 210 150 150 1 1	210 210 151 152 1 1	210 149 1	220 220 2	220 211 220 211 2 2	210 210 164 158 2 2	210 210 154 154 3 5	211 160 10	220	#proc 5 10 30
		0.75																									60
		0.50																									680	100
		0.25	665 552	665 665 548 547	665 665 547 547	665 665 547 547	665 547	666 666	665 665 573 552	665 665 548 547	665 665 547 547	665 548	680 680	680 666 680 666	665 665 574 571	665 665 557 563	666 570	200
		0.00	1	1	1	1	1	1	1	1	1	1	1	1	1	1	2	4	6	6	6	6	7	9	14	32
						0.01				1.00				0.01				1.00				0.01				1.00
										Communication-to-Computation Ratio
	0.50 0.75 1.00 Figure 11. 85 57 0.25	85 49	pfail=0.0001 85 85 85 85 44 44 44 43	85 42	85 32	86 86	85 73	85 58	pfail=0.001 85 85 50 44	85 43	85 42	85 40	91 91	91 91	86 86	pfail=0.01 85 85 75 68	85 55	85 54	85 57	91	strategy CIDP CDP
		0.00	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	2	3	NONE
	Ratio to ALL	0.25 0.50 0.75 1.00 0.00 1.00	375 287 1	375 375 277 261 1 1	375 375 261 263 1 1	375 375 264 244 1 1	375 244 1	376 368 1	375 375 307 287 1 1	375 375 277 271 1 1	375 375 266 244 1 1	375 247 2	385 385 4	385 376 385 376 4 4	375 375 312 293 4 4	375 375 286 263 5 8	376 272 17	385	#proc 5 10 30
		0.75																									60
		0.50 0.25	1225 1225 1225 1225 1225 1225 1225 1225 1045 1026 1026 1021 1024 1024 921 924	1225 1225 1225 1225 1225 1225 1225 1225 1207 1092 1046 1026 1027 1024 924 928	1240 1240 1226 1225 1225 1225 1226 1226 1240 1240 1220 1092 1056 1040 937 953	1240	100 200
		0.00	1	1	1	1	1	1	1	1	2	2	2	2	2	2	3	6	11	11	11	12	13	17	26	58
						0.01				1.00				0.01				1.00				0.01				1.00
										Communication-to-Computation Ratio
	Figure 12.

  Performance of the different checkpointing strategies for QR using HEFTC for task mapping and scheduling.

					pfail=0.0001						pfail=0.001							pfail=0.01
		1.00
		0.75																									strategy
		0.50																									91	CIDP
		0.25	81 49	81 38	81 34	81 32	81 30	82 34	83 31	82 30	86 86	82 68	81 50	81 44	81 34	82 36	83 32	82 34	91 91	91 91	86 86	82 70	82 57	82 50	83 48	82 49	CDP
		0.00	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	2	3	NONE
	Ratio to ALL	0.25 0.50 0.75 1.00 0.00 1.00	370 268 1	370 370 251 245 1 1	372 372 238 229 1 1	372 372 225 237 1 1	373 248 1	376 367 1	371 370 301 274 1 1	372 372 248 235 1 1	372 372 226 238 1 1	373 256 2	385 385 4	385 376 385 376 4 4	372 372 307 283 4 5	372 372 259 264 6 8	376 310 18	385	#proc 5 10 30
		0.75																									60
		0.50 0.25	1222 1220 1219 1219 1219 1219 1220 1219 1011 985 966 949 963 978 979 917	1224 1220 1219 1219 1219 1219 1220 1219 1134 1083 1018 971 975 990 982 959	1240 1240 1226 1220 1219 1220 1222 1225 1240 1240 1213 1080 1061 1047 1039 1056	1240	100 200
		0.00	1	1	1	1	1	1	1	1	2	2	2	2	2	2	3	6	13	13	13	13	14	17	26	60
						0.01				1.00				0.01				1.00				0.01				1.00
										Communication-to-Computation Ratio
	30 Figure 13. 48 0.25 0.50 1.00 0.75	48 16	47 13 pfail=0.0001 47 47 47 14 15 14	47 12	47 14	48 47	48 38	48 32	48 18 pfail=0.001 48 15	47 15	47 13	47 15	49 49	48 47	48 47	48 38 pfail=0.01 48 29	48 27	48 23	48 28	50	#proc
		0.00	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
	Ratio to ALL	0.00 0.25 0.50 0.75 1.00	298 244 1	298 298 216 185 1 1	298 298 179 186 1 1	297 297 194 188 1 1	296 185 1	298 298 1	298 298 270 248 1 1	298 298 208 189 1 1	298 298 195 188 1 1	297 194 1	300 300 2	299 298 299 298 2 2	298 298 272 257 2 3	298 298 242 232 3 5	298 254 11	300
		1.00
		0.75
		0.50																									700
		0.25	698 629	698 698 579 553	698 698 538 551	698 698 540 538	698 505	699 699	699 698 649 630	698 698 588 554	698 698 544 543	698 518	700 700	699 699 699 699	699 698 652 626	698 698 610 618	698 617
		0.00	1	1	1	1	1	1	1	1	1	1	1	1	1	1	2	3	5	5	5	5	6	7	11	28
						0.01				1.00				0.01				1.00				0.01				1.00
										Communication-to-Computation Ratio
	Prepared using sagej.cls

  Performance of the different checkpointing strategies for Genome using HEFTC for task mapping and scheduling. Performance of the different checkpointing strategies for Ligo using HEFTC for task mapping and scheduling.

					pfail=0.0001						pfail=0.001							pfail=0.01
		1.00
		0.75																										#proc
		0.50																									47	5
		0.25	13 11	13 11	13 11	13 10	14 10	13 9	12 9	12 9	14 12	13 11	13 11	13 11	14 11	13 10	12 10	12 9	24 23	19 18	15 13	15 13	15 12	15 13	14 12	14 13		10
		0.00	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	2		30
	Ratio to ALL	0.25 0.50 0.75 1.00 0.00 1.00	78 71 1	78 71 1	78 70 1	79 70 1	78 68 1	81 71 1	82 73 1	84 73 1	85 78 1	79 72 1	79 72 1	80 73 1	79 72 1	82 74 1	83 74 1	84 73 1	126 125 4	90 87 4	85 82 4	85 80 4	85 80 4	85 80 4	85 81 5	86 85 7	297	60 70 140 strategy
		0.75																										CIDP
		0.50																									699	CDP
		0.25	183 171	183 182 171 170	182 187 168 173	189 190 173 178	190 177	193 182	192 189 180 177	187 190 175 178	191 191 176 180	191 180	339 338	234 199 232 194	196 197 188 190	197 197 191 195	198 197		NONE
		0.00	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	2	8	8	8	8	8	9	10	17
						0.01				1.00				0.01				1.00				0.01				1.00
										Communication-to-Computation Ratio
	0.50 0.75 1.00 Figure 15. 25 23 0.25	25 22	pfail=0.0001 25 25 25 25 21 19 18 18	25 18	25 17	36 35	26 24	26 23	pfail=0.001 26 26 22 21	26 19	25 19	26 18	40 39	37 36	37 36	pfail=0.01 27 26 25 23	26 22	26 22	26 22	50	strategy CIDP CDP
		0.00	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	2		NONE
	Ratio to ALL	0.25 0.50 0.75 1.00 0.00 1.00	151 146 1	151 150 145 144 1 1	150 150 127 126 1 1	150 150 122 126 1 1	149 122 1	222 216 1	157 152 151 146 1 1	152 152 145 144 1 1	152 152 130 128 1 1	151 124 1	249 248 4	226 223 224 218 3 4	161 153 155 148 4 4	153 153 147 148 4 5	153 145 7	300	#proc 5 10 30
		0.75																										60
		0.50 0.25	506 480	502 502 479 478	503 502 459 454	502 505 454 458	504 460	729 702	541 515 503 481	512 512 479 477	511 513 472 468	512 470	837 826	747 731 727 707	549 521 512 482	521 521 483 484	521 487	1000	100 200
		0.00	1	1	1	1	1	1	1	1	1	1	1	2	2	2	2	3	10	10	11	11	11	12	14	23
						0.01				1.00				0.01				1.00				0.01				1.00
										Communication-to-Computation Ratio
	Figure 16.

  Performance of the different checkpointing strategies for Sipht using HEFTC for task mapping and scheduling.

					pfail=0.0001						pfail=0.001							pfail=0.01
		1.00
		0.75																									#proc
		0.50																									48	5
		0.25	47 15	47 18	47 16	47 17	46 12	44 17	32 12	32 12	48 18	47 20	47 16	47 17	46 14	46 19	34 12	34 12	48 21	48 24	48 21	47 21	46 17	46 20	34 15	34 15	10
		0.00	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	2	30
	Ratio to ALL	0.25 0.50 0.75 1.00 0.00 1.00	288 178 1	288 288 183 171 1 1	288 288 168 170 1 1	278 278 165 188 1 1	277 135 1	288 187 1	288 288 192 178 1 1	288 288 169 179 1 1	288 288 174 190 1 1	287 136 1	290 225 3	289 288 209 195 3 3	288 288 188 198 4 4	288 288 190 209 4 5	287 156 7	290	60 70 140 strategy
		0.75																									CIDP
		0.50																									677	CDP
		0.25	671 493	671 671 442 455	671 671 472 450	658 648 430 441	648 365	671 520	671 671 464 475	671 671 476 462	672 671 452 450	671 368	677 562	674 671 504 511	671 671 519 504	672 671 492 496	671 414	NONE
		0.00	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	2	7	7	8	8	8	8	10	17
						0.01				1.00				0.01				1.00				0.01				1.00
										Communication-to-Computation Ratio
	Figure 17. 47	45	45	46	45	45	45	41
			38	35	33	32	29	27	32	29
			1	1	1	1	1	1	1	1
			299	296 297	297 294	267 266	268
			235	215 214

  Asc: Improving spark driver performance with automatic spark checkpoint. In: 2016 18th International Conference on Advanced Communication Technology (ICACT). IEEE, pp. 607-611.

East China Normal University, China

Univ Lyon, EnsL, UCBL, CNRS, Inria, LIP, F-69342, LYON Cedex 07,

Prepared using sagej.cls

215 203 191

Acknowledgements

We would like to thank the anonymous reviewers for their valuable comments and suggestions, which helped improve the quality of this paper. A shorter version of this work has been published in the proceedings of ICPP'18 (Han et al. (2018b)). This work is partially supported by a JORISS grant from ENS Lyon and ECNU.

Notes * . A preliminary version of this work appeared in the proceedings

of ACM ICPP 2018. †. In fact, because we have homogeneous processors, we use MCP (Modified Critical Path) (Wu and Gajski (1990)) with backfilling, which is exactly HEFT in this context. ‡. Each boxplot consists of a bold line for the median, a box for the quartiles, whiskers that extend at most to 1.5 times the interquartile range from the box and additional points for outliers.


A Study of the Rotating Stall in a Vaneless Diffuser of Radial Flow Pump

Keywords: Experimental research, Diffuser performance, Radial pump, Rotating stall, Spectrum analysis, Vaneless diffuser

Rotating stall in a vaneless diffuser of radial flow pump is studied. The measurements have consisted of: i/ unsteady pressure measurements delivered by two microphones, ii/ 9 steady pressure taps mounted in one radial line to measure the pressure recovery in the vaneless diffuser. Spectrum analysis was used to identify and characterize rotating stall. An assumption was made to estimate the losses in the vaneless diffuser to evaluate the effect of the instability development on its performance. The result has shown that the arising of rotating stall has a positive effect on the diffuser performance. Two possible reasons are proposed: 1. A blockage in the diffuser due to the unstable cells which shortens the streamlines and decreased the friction losses along the vaneless diffuser. 2. The topology of rotating stall cells results in the convection of fluid coming from outside part of the pump model to the vaneless diffuser.

Introduction

Pumps are widely used in many fields, like irrigation, water supply, cooling system, pumping station, etc [START_REF] Mahdi | Optimal design and operation of irrigation pumping stations using mathematical programming and genetic algorithm (GA)[END_REF]. One important limit in the operating range of pumps is the occurrence of unstable phenomena in their internal flows. One of them is the rotating stall which is occurring in diffusers of radial flow pumps operating at partial flow rates [START_REF] Dazin | Rotating instability in the vaneless diffuser of a radial flow pump[END_REF](Dazin et al., , 2011)). Several negative effects are also associated with rotating stall, such as noise, vibration, mechanical damage and especially performance reduction. Therefore, characterizing, understanding and even predicting this phenomenon is important and necessary. A lot of studies of rotating stall have thus been carried out and the research methods could be summarized as follows:

(1) Theoretical analysis, which includes three dimensional analysis [START_REF] Jansen | Rotating stall in a radial vaneless diffuser[END_REF][START_REF] Senoo | Asymmetric flow in vaneless diffusers of centrifugal blowers[END_REF]Senoo & Kinoshita, 1977; Fringe & Van den Braembussche, 1985; [START_REF] Dou | Analysis of the flow in vaneless diffusers with large width-to-radius ratios[END_REF] and two dimensional analysis [START_REF] Tsujimoto | Study of vaneless diffuser rotating stall based on two dimensional inviscid flow analysis[END_REF][START_REF] Moore | Weak rotating flow disturbances in a centrifugal compressor with a vaneless diffuser[END_REF][START_REF] Abdelhamid | Analysis of Rotating Stall in Vaneless Diffusers of Centrifugal Compressors[END_REF]. For two dimensional analysis, it is generally admitted that the effect of boundary layer can be ignored in wide vaneless diffuser, for which the existence of a 2D core flow is assumed, as shown in Fig. 1. On the other hand, the effect of three-dimensional boundary layer instability was suggested to be responsible for the occurrence of rotating stall in the narrow vaneless diffuser. i. The effect of flow conditions and geometries of impeller/diffuser on the rotating stall, such as diffuser width (Senoo & Kinoshita, 1977;[START_REF] Abdelhamid | Distinction between two types of self-excited gas oscillations in vaneless radial diffusers[END_REF][START_REF] Ötügen | Diffuser stall and rotating zones of separated boundary layer[END_REF][START_REF] Ljevar | Rotating stall in wide vaneless diffusers[END_REF][START_REF] Ferrara | Rotating stall in centrifugal compressor vaneless diffuser: experimental analysis of geometrical parameters influence on phenomenon evolution[END_REF][START_REF] Abidogun | Effects of vaneless diffuser geometries on rotating stall[END_REF][START_REF] Nishida | A study on the rotating stall of centrifugal compressors (1st report, effect of vaneless diffuser width on rotating stall)[END_REF], coupling between impeller and diffuser [START_REF] Abdelhamid | Analysis of Rotating Stall in Vaneless Diffusers of Centrifugal Compressors[END_REF][START_REF] Ferrara | Rotating stall in centrifugal compressor vaneless diffuser: experimental analysis of geometrical parameters influence on phenomenon evolution[END_REF][START_REF] Kobayshi | A study on the rotating stall of centrifugal compressors (2nd report, effect of vaneless diffuser inlet shape on rotating stall)[END_REF], diffuser diffusion ratios [START_REF] Ferrara | Rotating stall in centrifugal compressor vaneless diffuser: experimental analysis of geometrical parameters influence on phenomenon evolution[END_REF], Mach number (Senoo & Kinoshita, 1977;[START_REF] Ferrara | Rotating stall in centrifugal compressor vaneless diffuser: experimental analysis of geometrical parameters influence on phenomenon evolution[END_REF], Reynolds number (Senoo & Kinoshita, 1977;[START_REF] Abidogun | Effects of vaneless diffuser geometries on rotating stall[END_REF], radius ratios of diffuser (Senoo & Kinoshita, 1977;[START_REF] Abdelhamid | Distinction between two types of self-excited gas oscillations in vaneless radial diffusers[END_REF][START_REF] Abdelhamid | Effects of vaneless diffuser geometry on flow instability in centrifugal compressor systems[END_REF][START_REF] Ljevar | Two-dimensional rotating stall analysis in a wide vaneless diffuser[END_REF][START_REF] Ljevar | Rotating stall in wide vaneless diffusers[END_REF][START_REF] Abidogun | Effects of vaneless diffuser geometries on rotating stall[END_REF], impeller [START_REF] Ljevar | Two-dimensional rotating stall analysis in a wide vaneless diffuser[END_REF][START_REF] Ljevar | Rotating stall in wide vaneless diffusers[END_REF][START_REF] Abidogun | Effects of vaneless diffuser geometries on rotating stall[END_REF]. Figure 1 The flow structure in wide vaneless diffuser [START_REF] Ljevar | Rotating stall in wide vaneless diffusers[END_REF] Although rotating stall was studied in many aspects listed above, some of the mechanisms and effects of the instability are still unclear. Therefore, the present work reports studies managed with the support of an experimental test rig which was used to observe the rotating stall in the vaneless diffuser. 22 flow rates were tested for two rotating speed: 1200 and 1800 RPM. A dedicated spectrum analysis was applied to spectrally identify and characterize the rotating modes which were observed in the vaneless diffuser: number of cells, amplitude and propagation velocity of the stall. At last, an analysis of the pressure losses in the diffuser operating in stable or unstable conditions is proposed to study the effect of rotating stall on the performance of such a wide vaneless diffuser.

Experiment Apparatus

The experimental test rig (Fig. 2) includes a radial impeller which was coupled with a vaneless diffuser. Inlet conditions are obtained using a long suction pipe. In order to ensure axisymmetric outlet boundary conditions, no volute was set downstream to the vaneless diffuser. The configuration was equipped with 9 steady pressure taps which were flush mounted on the diffuser wall in one radial line (equally spaced from R = 264 mm to 384 mm).

Therefore, the diffuser performance is determinable based on the pressure recovery from diffuser inlet to outlet. The uncertainty of these measurements was ±2 Pa. To ensure the stability of the inlet flow, a tank, equipped with a honeycomb flow straightener, was set before the suction pipe. A set of changeable diaphragms (with different inlet diameters) is available to be installed at the tank inlet to adjust the flow rate.

Two Brüel & Kjaer condenser microphones (Type 4135) were used to get the unsteady pressure fluctuation. They were flush mounted at the same radius (R = 320 mm) on the diffuser wall but with an angular difference of = 75°, then the instabilities which occurred in the vaneless diffuser are detectable and analyzable. The measurement uncertainty for these measurements was less than 1%. The data were acquired by LMS. Test Xpress with the sampling time 600 seconds and sampling frequency 4096 Hz. The experiment was made in air, and the main parameters of radial impeller and vaneless diffuser are given in Table 1. In this experiment, 22 flow rates (Q/Q d =0.261.53) were performed for two rotating speeds: 1200 RPM and 1800 RPM. The pump (impeller + diffuser) and the diffuser performances (in terms of static pressure rise) are plotted in Fig. 3.

More details of this experimental test rig can be found in previous studies presented by [START_REF] Dazin | Rotating instability in the vaneless diffuser of a radial flow pump[END_REF][START_REF] Dazin | High-speed stereoscopic PIV study of rotating instabilities in a radial vaneless diffuser[END_REF] with the same configuration. The spectrum information which was acquired by two microphones allows to detect the development of rotating stall in the vaneless diffuser and also to analyze its characteristics, as shown in Fig. 4, where ψ was defined as:

2 2 P U    (1)
Where P is the microphone pressure signal.

RPM

According to the spectrum analysis, rotating stall was identified at the five partial flow rates: Q/Q d =0.26, 0.36, 0.47, 0.56, 0.58, and cannot be observed when the flow rate ratio is higher than 0.6. For a given flow rate, rotating stall characteristics are similar for the two rotating speeds investigated.

When the flow rate ratio is higher than 0.6, the dominant frequency was the blade passing frequency (a typical example is proposed Fig. 5a), and the impeller frequency and its harmonics are also significant. On the contrary, for the five lower partial flow rates, the spectra are dominated by several low frequency peaks due to rotating stall, as shown in Fig. 5b, c, d, e andf

Q/Q d =0.58; (c) Q/Q d =0.56; (d) Q/Q d =0.47; (e) Q/Q d =0.36; (f) Q/Q d =0.26
At one flow condition, some peaks may correspond to different modes of rotating stall, but others to harmonics or nonlinear interaction of fundamental phenomena. Therefore, a dedicated spectrum analysis was applied to identify the different modes of rotating stall.

Considering the amplitude of each frequency from high to low, an example for flow rate 5f) is given in Table 2. As the pressure fluctuation signal associated with one stall mode n is assumed to be ̃ ( ) ( ( )). The determination of number of stall cells n depends on the measured phase difference between the two microphones △phase and the angular difference △θ between them, that is: n = △phase/△θ. Frequency(Hz) Amplitude(Pa 2 ) Mode

Q/Q d =0.26 (Fig.
f 1 =16.5 f 2 =13 f 3 =20 f 4 =29.5 f 5 =33
Harmonic(=2f 1 )
As it can be seen from Table 2, two frequencies corresponding to different rotating stall modes can be identified. It has been shown in a previous study [START_REF] Pavesi | Experimental and numerical investigation of unforced unsteadiness in a vaneless radial diffuser[END_REF]) that for a given operating point, two stall modes can coexist intermittently. A synthesis of the unstable modes that can be evidenced for each flow rates is proposed in Table 3, in which n is the number of rotating cells that could be identified through the analysis of the phase difference of the pressure signals of the two microphones.

Then the amplitude and dimensionless circumferential velocity of stall cells versus flow rate are drawn in Fig. 6. Concerning the amplitude, the general tendency is an increase of the intensity of the unstable flow with the flow rate decrease. It can be seen that the circumferential velocity of stall cells is increasing with the decrease of flow rate. This can be linked with the increase of the circumferential velocity of the main flow with the decrease of flow rate according to the shape of the velocity triangle at impeller outlet (diffuser inlet), then the circumferential velocity of rotating stall which is involved in the diffuser flow is then increased. This tendency can also be found in a theoretical work presented by Tsujimoto, Yoshida, & Mori (1996).

(a)

(b)

Figure 6 The amplitude (a) and circumferential velocity (b) of stall cells for 1200 RPM

Effect of rotating stall on the diffuser performance

Since the presence of rotating stall in the vaneless diffuser is confirmed and characterized, it is possible to determine the effect of rotating stall on the diffuser performance. Using the measured values of the 9 wall static pressure taps along the diffuser wall, the mean pressure evolution from diffuser inlet to outlet can be obtained. Figure 7 gives the pressure recovery in the vaneless diffuser, scaled by the kinetic energy at the diffuser inlet. The absolute velocity at diffuser inlet has been evaluated by the determination of the velocity triangle at impeller outlet.

Figure 7 Diffuser static pressure recovery versus flow rate ratio

In stable conditions (with no rotating stall), it can be seen that the diffuser performance is decreased with the flow rate, but is increased at the onset of rotating stall and then decreased again when rotating stall is fully developed. One can note that the performance increase is also obvious on the performance curve of the diffuser (Fig. 3), around Q/Q d = 0.6.

To study more accurately the effect of rotating stall on the diffuser performance, an analysis of the losses in the diffuser is proposed: the isentropic increase of pressure due to the velocity decrease in the diffuser has been calculated and compared to the experimental pressure recovery (Fig. 8): more precisely, at the diffuser outlet, the pressure difference between the isentropic theoretical estimation and the experimental result is then defined as experimental losses, and an experimental loss coefficient can be defined as:

2 3 / ( ) 2 V Losses    (3)
Figure 8 Pressure recovery curve at design flow rate Q d

The losses in vaneless diffuser, in stable operations, are usually divided into three terms: i/ losses due to friction that can be modeled by a friction factor derived from the ones obtained in duct flows. ii/ Additional losses due to the adverse pressure gradient. These losses are commonly called 'diffusion losses'. iii/ Losses due to the mixing of the jet wake pattern coming out from the impeller.

The present study is neglecting the two last losses sources because:

ii/ the diffusion losses could be neglected if the streamline in the diffuser is sufficiently long [START_REF] Aungier | Aerodynamic Design and Analysis of Vaneless Diffusers and Return Channels[END_REF][START_REF] Dou | Investigation of the Prediction of Losses in Radial Vaneless Diffusers[END_REF]. [START_REF] Dou | Investigation of the Prediction of Losses in Radial Vaneless Diffusers[END_REF] showed that the diffusion losses could be neglected for diffuser width of the same order of magnitude compared to the one used in the present study (B 3 /D 2 = 0.075) if the absolute flow angle at diffuser inlet is lower than 25°. In the present study, the diffuser inlet flow angle varies from 2.3° to 24.6°, depending on the flow rate studied.

iii/ The mixing losses are concentrated in the region close to the impeller outlet (1.00< D/D 2 < 1.06) [START_REF] Dou | Investigation of the Prediction of Losses in Radial Vaneless Diffusers[END_REF]. In the present paper, the first pressure tap is located at

D/D 2 = 1.
09 and the effect of the mixing losses in the performance of the diffuser has not to be taken into account in the analysis of the pressure recovery curves presented.

Consequently, if the vaneless diffuser is on stable operation, the losses are supposed to be mainly due to friction losses along the length L of a streamline:

2 3 H 2 V Losses L D    (4)
Where D H is the hydraulic diameter,  is the friction factor, and in the present vaneless diffuser,

4 H S D C  ( 5
)
Where S is the cross sectional area which is equal to The diffuser loss coefficient in stable conditions is:

2 3 / ( ) 2 H S V Losses L D       (6)
Which is depending only on the length of streamline L, and the streamline in the vaneless diffuser is known as a logarithmic spiral (Fig. 9) (from the continuity equation and moment of momentum equation, and assuming that the flow is 2D, axisymmetric). The length of streamline L can be estimated by equation [START_REF] Cellai | Experimental investigation and characterization of therotating stall in a high pressure centrifugal compressor, part IV: impeller influence on diffuser stability[END_REF]. It is depending only on the value of the absolute flow angle α at diffuser inlet and is thus increasing with the flow rate decrease, as shown in Fig. 10. The diffuser inlet flow angle was estimated from the calculation of the velocity triangle at impeller outlet, using Stodola slip factor. The evolution of the diffuser loss coefficient versus the length of streamline was drawn in Fig. 11. It can be seen that the losses increase linearly with the streamline length for small value of L, that is, for operating conditions without rotating stall (stable conditions). Moreover, it is noticeable that the experimental slope (≈ 0.32) is close to the theoretical one [START_REF] Senoo | Influence of inlet flow conditions and geometries of centrifugal vaneless diffusers on critical flow angle for reverse flow[END_REF], with a value of the friction factor extracted from the Moody diagram), as it was assumed in equation [START_REF] Aungier | Aerodynamic Design and Analysis of Vaneless Diffusers and Return Channels[END_REF]. What is particularly notable in Fig. 11 is that the arising of rotating stall is corresponding to a clear drop of the losses. This is confirmed again in Fig. 12, presenting the evolution of the loss coefficient as a function of the flow rate. In this figure, the loss coefficient drops at the arising of rotating stall is also obvious. After this drop, the losses are increasing again with the decreasing of flow rate, but this time with a clear much smaller slope than the one ( S  ) calculated based on the length of logarithmic spiral which represents the conditions without rotating stall. Figure 13 gives the diffuser experimental/theoretical losses coefficient versus the static pressure recovery coefficient. The experimental loss coefficient is a straight line. This is due to the definition of the experimental losses which are defined as the difference between the isentropic pressure recovery and the experimental pressure recovery. Consequently, the experimental loss coefficient is:

H D /  (=0.
4 3 4 3 2 3 ( ) ( ) 0.5 is P P P P V       (8)
That is:

2 3 4 3 22 43 () (1 ) 0.5

R P P RV

      (9)
The theoretical loss coefficient is calculated based on equation ( 6) which assumes that the diffuser flow is stable (without rotating stall). It can be seen that the experimental loss coefficient agrees well with the theoretical one while the diffuser flow is stable. However, with the presence of rotating stall (Q/Q d < 0.58), the experimental loss coefficient is not as large as the theoretical prediction, which confirmed the effect of rotating stall on the diffuser performance.

As a conclusion, it seems that the arising of the instability could be a way, for the flow, to reduce its losses when the flow angle is very low at diffuser inlet. The losses reduced means the diffuser performance with rotating stall is higher than the one without rotating stall because of the choice of the isentropic pressure curve that has been taken as a fixed theoretical value, as illustrated in Fig. 14. To estimate the streamline, previous PIV results were used to estimate the blockage induced by the rotating cells. Then, the vaneless diffuser can be divided into two parts, as shown in Fig. 16:

(1) Part 1: Before the streamline reaches to the boundary of cells, it can be assumed that the streamline is not affected by the presence of rotating stall.

(2) Part 2: After the streamline reaches to the stall zone, the effect of blockage due to stall cells should be taken into account. One can nevertheless notice that the corrected losses are a little bit higher than the experimental losses. Therefore, a second explanation has also to be considered: pressure which is measured at the diffuser outlet is a time averaged value and considering the topology of cells, it can be seen that they are characterized by regions of inward radial velocity.

Consequently, some high pressure flow coming from downstream of the diffuser (the ambient air at atmospheric pressure) is convected in the diffuser (Fig. 19), then the measured time averaged pressure is actually increased. Eventually, this effect results in the decrease of experimental losses again.

Figure 19 Convection at the diffuser outlet

The rotating stall in a vaneless diffuser was experimentally observed and characterized by a dedicated spectrum analysis. Moreover, the pressure recovery in the vaneless diffuser was calculated experimentally and theoretically. By a theoretical assumption, the effect of rotating stall on the diffuser performance was then determined and analyzed. Several conclusions were drawn as follows:

(1) 22 flow rates were tested in experiment, and rotating stall was observed at 5 partial flow rates lower than Q/Q d = 0.58. It was found that the dominant stall mode was characterized by 4 cells at Q/Q d =0.47, 0.56, 0.58, 2 cells at Q/Q d =0.36 and 3 cells at [START_REF] Suzuki | Noise characteristics in partial discharge of centrifugal fans: 1st report, low-frequency noise due to the rotating stall[END_REF]. Moreover, the experimental result shows that the occurrence and characteristics of rotating stalls are the same for the two rotating speed investigated.

Q/Q d =0.
(2) In some cases, several competitive stall modes could co-exist intermittently. In this situation, it seems that the mode with fewer cells propagates faster than the mode with more cells.

(3) The effect of rotating stall on the vaneless diffuser performance was analyzed. The result shows that, for operating points with no rotating stall, the losses increase linearly with the length of the streamline in the diffuser. But, it has also been observed that the development of rotating stall is corresponding to an increase of the pressure recovery in the diffuser and to a decrease of the losses compared to a case without rotating stall. The arising of instability has thus a positive effect on the diffuser performance. Two possible reasons were offered: 1. the shorter length of streamline, due to the blockage induced by the stall cells decreased the friction losses;

2. The convection of some high pressure flow coming from downstream of the vaneless diffuser.

( 2 )

 2 Experimental researches (for example: PIV study-Wuibaut, Dupont, Bois, Caignaert, & Stanislas, 2002; Krause, Zähringer, & Pap, 2005; Pavesi et al., 2011; Dazin et al., 2008, 2011) and numerical analyses are quite numerous in open literature. The main research contents of rotating stall were focused on several aspects:

  ii. The prediction, detection and control of the inception of rotating stall (Tsurusaki, Imaichi, & Miyake, 1987; Tsurusaki & Kinoshita, 2000; Kurokawa, Saha, Matsui, & Kitahora, 1999). iii. Analysis of the characteristics of rotating stall itself: such as the critical flow angle, propagation velocity, frequency and number of stall cells (Cellai, Ferrara, Ferrari, Mengoni, & Baldassarre, 2003; Dazin et al., 2008, 2011; Pavesi et al., 2011; Suzuki, Ugai, & Harada, 1977; Caignaert, Desmet, & Stevenaert, 1982; Abdelhamid, Colwill, & Barrows, 1979).

Figure 2

 2 Figure 2 Experimental test rig

Figure 3

 3 Figure 3 Pump and diffuser performance curves. (Static pressure rise)

Figure 4

 4 Figure 4 Crosspower spectra at two impeller angular velocities: (a) 1200 RPM and (b) 1800

Figure 5

 5 Figure 5 Crosspower spectra at design flow rate (a) and the flow rates with rotating stall: (b)

3 2 *

 2 rB  , and C is the perimeter of the cross-section which is equal to 4 r  .

Figure 9 Figure 10

 910 Figure 9 Streamline in the vaneless diffuser

Figure 11

 11 Figure 11 Diffuser loss coefficient at diffuser outlet versus length of streamline

Figure 14

 14 Figure 14 Diffuser pressure recovery Two possible reasons may explain why the pressure recovery is increased in presence of rotating stall: First, Figure 15, from previous experimental study with the same configuration (Dazin et al., 2011), gives the PIV result of the radial velocity in the vaneless diffuser (at Q/Q d = 0.26). Three rotating cells can be identified and each cell is composed of two cores with inward and outward radial velocity. Therefore, one can consider the rotating cells generate a blockage region due to the inward radial velocity near the diffuser outlet. Consequently, the flow in the regions outside of rotating cells is characterized by higher radial velocities than what we would have without rotating cells. Therefore, the real streamline could become shorter than the one we would have if the flow without rotating stall, and then the shorter streamline leads to smaller friction losses.

Figure 15

 15 Figure 15 Radial velocity in the vaneless diffuser at Q/Q d =0.26[START_REF] Dazin | High-speed stereoscopic PIV study of rotating instabilities in a radial vaneless diffuser[END_REF]

Figure 16

 16 Figure 16 Two assumed spaces in the vaneless diffuser Therefore, in Fig. 17, the length of streamline 1 has been calculated as before (without rotating stall). For the streamline 2, the new radial velocity has been calculated taking into account the blockage area identified from the PIV result. Then, a new flow angle and a new length of streamline 2 have been estimated. Finally, the new estimation of friction losses based on the new length of streamline has been calculated (with the same value of / H D  used before) and compared with experimental results, as shown in Fig. 18.

Figure 17

 17 Figure 17 Assumption of the real streamline

Table 1

 1 Main parameters of impeller and vaneless diffuser

	Impeller
	D 1	Inlet Diameter	282.2 (mm)
	D 2	Outlet Diameter	513.2 (mm)
	B 2	Impeller Outlet Width	38.5 (mm)
	Z	Number of Blades
	β 2	Outlet Blade Angle
	Q d	Design Flow Rate (N=1200 RPM)

Table 2

 2 Rotating stalls, harmonics and nonlinear interaction at flow rate Q/Q d =0.[START_REF] Suzuki | Noise characteristics in partial discharge of centrifugal fans: 1st report, low-frequency noise due to the rotating stall[END_REF]

Table 3

 3 Different modes of rotating stallIt can be seen that with the flow rate decrease, the dominant stall mode starts from 4 cells mode (Q/Q d =0.47, 0.56, 0.58), then becomes 2 cells mode (Q/Q d =0.36), and changes to 3 cells mode (Q/Q d =0.26) at last. This trend agrees well with previous study on the same experimental configuration[START_REF] Dazin | Rotating instability in the vaneless diffuser of a radial flow pump[END_REF]. Based on the rotating stall frequency, the circumferential velocity of the stall cells ω, can be estimated as follow:

	Q/Q d	Dominant	Second	Third	Fourth
	0.26	n=3	n=2	no	no
	0.36	n=2	n=3	no	no
	0.47	n=4	n=2	n=3	no
	0.56	n=4	no	no	no
	0.58	n=4	no	no	no
				2/ rs fn  

Acknowledgement

The authors acknowledge the cooperation with the projects: National Natural Science Foundation of China (No. 51509108) and Natural Science Foundation of Jiangsu Province (Grant No. BK20150506). The authors would also like to thank Professor Gerard Bois for the interesting discussions on this topic.

Funding

The authors wish to thank the financial support by CSC (China Scholarship Council).

Notation