Anne Benoit

Loïc Pottier

Yves Robert

Resilient application co-scheduling with processor redistribution

Keywords: Resilience, co-scheduling, redistribution, complexity results, heuristics, simulations

Recently, the benefits of co-scheduling several applications have been demonstrated in a faultfree context, both in terms of performance and energy savings. However, large-scale computer systems are confronted to frequent failures, and resilience techniques must be employed to ensure the completion of large applications. Indeed, failures may create severe imbalance between applications, and significantly degrade performance. In this paper, we propose to redistribute the resources assigned to each application upon the striking of failures, in order to minimize the expected completion time of a set of co-scheduled applications. First, we introduce a formal model and establish complexity results. When no redistribution is allowed, we can minimize the expected completion time in polynomial time, while the problem becomes NP-complete with redistributions, even in a faultfree context. Therefore, we design polynomial-time heuristics that perform redistributions and account for processor failures. A fault simulator is used to perform extensive simulations that demonstrate the usefulness of redistribution and the performance of the proposed heuristics.

I. Introduction

With the advent of multicore platforms, HPC applications can be e ciently parallelized on a flexible number of processors. Usually, a speedup profile determines the performance of the application for a given number of processors. For instance, the applications in [START_REF] Heroux | Improving Performance via Mini-applications[END_REF] were executed on a platform with up to 256 cores, and the corresponding execution times were reported. A perfectly parallel application has an execution time t seq /p, where t seq is the sequential execution time, and p is the number of processors. In practice, because of the overhead due to communications and to the inherently sequential fraction of the application, the parallel execution time is larger than t seq /p. The speedup profile of the application is assumed to be known (or estimated) before execution, through benchmarking campaigns.

A simple scheduling strategy on HPC platforms is to execute each application in dedicated mode, assigning all resources to each application throughout its execution. However, it was shown recently that rather than using the whole platform to run one single application, both the platform and the users may benefit from co-scheduling several applications, hence minimizing the loss due to the fact that applications are not perfectly parallel. Sharing the platform between two applications leads to significant performance and energy savings [START_REF] Shantharam | Speedup-aware co-schedules for e cient workload management[END_REF], that are even more important when co-scheduling more than two applications simultaneously [START_REF] Aupy | Co-scheduling algorithms for high-throughput workload execution[END_REF].

To the best of our knowledge, co-scheduling has been investigated so far only in the context of fault-free platforms. However, large-scale platforms are prone to failures. Indeed, for a platform with p processors, even if each node has an individual MTBF (Mean Time Between Failures) of 120 years, we expect a failure to strike every 120/p years, for instance every hour for a platform with p = 10 6 nodes. Failures are likely to destroy the load-balancing achieved by co-scheduling algorithms: if all applications were assigned resources by the co-scheduler so as to complete their execution approximately at the same time, the occurrence of a failure will significantly delay the completion time of the corresponding application. In turn, several failures may well create severe imbalance among the applications, thereby significantly degrading performance.

To cope with failures, the de-facto general-purpose error recovery technique in HPC is checkpoint and rollback recovery [START_REF] Elnozahy | A survey of rollback-recovery protocols in message-passing systems[END_REF]. The idea consists in periodically saving the state of the application, so that when an error strikes, the application can be restored into one of its former states. The most widely used protocol is coordinated checkpointing, where all processes periodically stop computing and synchronize to write critical application data onto stable storage. The frequency at which checkpoints are taken should be carefully tuned, so that the overhead in a faultfree execution is not too important, but also so that the price to pay in case of failure remains reasonable. Young and Daly provide good approximations of the optimal checkpointing interval [START_REF] Young | A first order approximation to the optimum checkpoint interval[END_REF], [START_REF] Daly | A higher order estimate of the optimum checkpoint interval for restart dumps[END_REF].

This paper investigates co-scheduling on failure-prone platforms. Checkpointing helps to mitigate the impact of a failure on a given application, but it must be complemented by redistributions to re-balance the load among applications. Co-scheduling usually involves partitioning the applications into packs, and then scheduling each pack in sequence, as e ciently as possible. We focus on the second step, namely co-scheduling a given pack of applications that execute in parallel, and leave the partitioning for further work. This is because scheduling a given pack becomes a di cult endeavor with failures (and redistributions), while it was of linear complexity without failures. Given a pack, i.e., a set of parallel tasks that start execution simultaneously, there are two main opportunities for redistributing processors. First, when a task completes, the applications that are still running can claim its processors. Second, when a failure strikes a task, that task is slowed down. By adding more resources to it, we hope to reduce the overall completion time. However, we have to be careful, because each redistribution has a cost, which depends on the volume of data that is exchanged, and on the number of processors involved in redistribution. In addition, adding processors to a task increases its probability to fail, so there is a trade-o to achieve in order to minimize the expected completion time of the pack.

The major contributions of this work are the following:

• the design of a detailed and comprehensive model for scheduling a pack of tasks on a failure-prone platform; • the NP-completeness proof for the problem with redistributions; • the design and assessment of several polynomial-time heuristics to deal with the general problem with failures and redistribution costs. This work provides an important extension to our previous work on co-schedules [START_REF] Aupy | Co-scheduling algorithms for high-throughput workload execution[END_REF], which already demonstrated that sharing the platform between two or more applications can lead to significant performance and energy savings [START_REF] Shantharam | Speedup-aware co-schedules for e cient workload management[END_REF]. To the best of our knowledge, it is the first work to consider co-schedules and failures, and hence to use malleable applications [START_REF] Blazewicz | Approximation algorithms for scheduling independent malleable tasks[END_REF], [START_REF] Frigo | The Implementation of the Cilk-5 Multithreaded Language[END_REF] to allow redistributions of processors between applications. More related work on models for parallel applications and resilience are discussed in the companion research report [START_REF] Benoit | Resilient application co-scheduling with processor redistribution[END_REF].

We point out that co-scheduling with packs can be seen as the static counterpart of batch scheduling techniques, where jobs are dynamically partitioned into batches as they are submitted to the system (see [START_REF] Muthuvelu | Batch resizing policies and techniques for fine-grain grid tasks: The nuts and bolts[END_REF] and the references therein). Batch scheduling is a complex online problem, where jobs have release times and deadlines, and where only partial information on the whole workload is known when taking scheduling decisions. On the contrary, co-scheduling applies to a set of applications that are all ready for execution. In this paper, as already mentioned, we restrict to a single pack, because scheduling already becomes di cult for a single pack with failures and redistributions.

The rest of the paper is organized as follows. The model and the optimization problem are formally defined in Section II. In Section III, we expose the complexity results. We introduce some polynomial-time heuristics in Section IV, which are assessed through simulations using a fault generator in Section V. Finally, we conclude and provide directions for future work in Section VI.

II. Framework

We consider a pack of n independent malleable applications {T 1 , . . . , T n }, and an execution platform with p identical processors subject to failures. We assume n AE p in failure-free problems and 2n AE p when accounting for failures, due to the use of the double checkpointing model. The objective is to minimize the expected completion time of the last application. First, we define the fault model in Section II-A. Then, we show how to compute the execution time of an application in Section II-B, assuming that no redistribution has occurred. The redistribution mechanism and its associated cost are discussed in Section II-C, and the objective function is detailed in Section II-D.

A. Fault model

We consider fail-stop errors, which are detected instantaneously. To model the rate at which faults occur on one processor, we use an exponential probability law of parameter ⁄. The mean (or MTBF) of this law is µ = 1 ⁄ . The MTBF of an application depends upon the number of processors it is using, hence changes whenever a redistribution occurs. Specifically, if application T i is (currently) executed on j processors, its MTBF is µ i,j = µ j (see [START_REF] Herault | Fault-Tolerance Techniques for High-Performance Computing[END_REF]Proposition 1.2] for a proof).

To recover from fail-stop errors, we use a light-weight checkpointing protocol called the double checkpointing algorithm, or buddy algorithm [START_REF] Ni | Hiding Checkpoint Overhead in HPC Applications with a Semi-Blocking Algorithm[END_REF], [START_REF] Dongarra | Performance and reliability trade-o s for the double checkpointing algorithm[END_REF]. This is an inmemory checkpointing protocol, which avoids the high overhead of disk checkpoints. Processors are paired: each processor has an associated processor called its buddy processor. When a processor stores its checkpoint file in its own memory, it also sends this file to its buddy, and the buddy does the same. Therefore, each processor stores two checkpoints, its own and that of its buddy. When a failure occurs, the faulty processor looses these two checkpoint files, and the buddy must re-send both checkpoints to the faulty node. If a second failure hits the buddy during this recovery period (which happens with very low probability), we have a fatal failure and the system cannot be recovered. Note that the number of processors assigned to each application must be even.

We enforce periodic checkpointing for each application. Formally, if application T i is executed on j processors, there is a checkpoint every period of length • i,j , with a cost C i,j . We now explain how to compute the cost C i,j of a checkpoint when application T i executes with j processors. Let m i be the memory footprint (total data size) of application T i . Each of the j processors holds mi j data, which it must send to its buddy processor. The time to communicate a message of size s is -+ s • , whereis a start-up latency and • the link bandwidth. We derive that C i,j = mi j• + -. As for the checkpointing period • i,j , we use Young's formula [START_REF] Young | A first order approximation to the optimum checkpoint interval[END_REF] and let

• i,j =  2µ i,j C i,j + C i,j . (1)
Because • i,j is a first order approximation, the formula is valid only if C i,j π µ i,j . When a fault strikes, there is first a downtime of duration D, and then a recovery period of duration R i,j . We assume that R i,j = C i,j , while the downtime value D is platform-dependent and not application-dependent.

B. Execution time without redistribution

To compute the expected execution time of a schedule, we first have to compute the expected execution time of an application T i executed on j processors subject to failures. We first consider the case without redistribution (but taking failures into account). Let t i,j be the execution time of application T i on j processors in a fault-free scenario. Let t R i,j (-) be the expected time required to compute a fractionof the total work for application T i on j processors, with 0 AE -AE 1. We need to consider such a partial execution of T i on j processors to prepare for the case with redistributions.

Recall that the execution of application T i is periodic, and that the period • i,j depends only on the number of processors, but not on the remaining execution time (see Equation ( 1)). After a work of duration • i,j ≠ C i,j , there is a checkpoint of duration C i,j . In a fault-free execution, the time required to execute the fraction of workis -t i,j , hence a total number of checkpoints of

N i,j (-) = 7 -t i,j • i,j ≠ C i,j 8 . ( 2
)
Next, we have to estimate the expected execution time for each period of work between checkpoints. We are able to calculate the expectation of one period of work according to an MTBF value and a number of processors. The expected time to execute successfully during T units of time with j processors (there are T ≠ C units of work and C units of checkpoint, where T is the period) is equal to

1 1 ⁄j + D 2
(e ⁄jT ≠ 1) [START_REF] Herault | Fault-Tolerance Techniques for High-Performance Computing[END_REF]. Therefore, in order to compute t R i,j (-), we compute the sum of the expected time for each period, plus the expected time for the last (possibly incomplete) period. This last period is denoted as • last and defined as:

• last = -t i,j ≠ N i,j (-)(• i,j ≠ C i,j ). (3)
Note that • last is depending onbecause • last represents the incomplete fraction of • i,j ≠ C i,j at the end of the application. The first N i,j (-) periods are equal (of length • i,j ), hence have the same expected time. Finally, we obtain:

t R i,j (-) = e ⁄jR i,j 3 1 ⁄j +D 4 ! N i,j (-)(e ⁄j• i,j ≠1)+(e ⁄j• last ≠1) " . ( 4
)
In a fault-free environment, it is natural to assume that the execution time is non-increasing with the number of processors. Here, this assumption would translate into the condition:

t R i,j+1 (-) AE t R i,j (-) for 1 AE i AE n, 1 AE j < p, 0 AE -AE 1. (5)
However, when we allocate more processors to an application, even though the work is further parallelized, the probability of failures increases, and the corresponding waste increases as well. Therefore, adding resources to an application is useful up to a threshold. After this threshold, we have t R i,j+1 Ø t R i,j . In order to satisfy Equation ( 5), we restrict the number of processors assigned to each application, and never assign more processors than the previous threshold. In other words, if T i is already assigned j processors, we consider assigning more processors to it only if t R i,j+1 AE t R i,j . Formally, this defines a maximum number of processors, j max (i), for each application T i :

j max (i) = min 1AEjAEp {j such that t R i,k Ø t R i,j for all k > j}, ( 6
) and we assume that t R i,j+1 AE t R i,j for all j < j max (i). Another common assumption for malleable applications is that the work is non-decreasing when the number of processors increases [START_REF] Blazewicz | Approximation algorithms for scheduling independent malleable tasks[END_REF]: this amounts to say that no superlinear speed-up is possible. Hence, we assume here that for

1 AE i AE n, 1 AE j < p and 0 AE -AE 1, (j + 1) ◊ t R i,j+1 (-) Ø j ◊ t R i,j (-).
For convenience, we denote by t U i the current expected finish time of application T i at any point of the execution. Initially, if application T i is allocated to j processors, we have

t U i = t R i,j (1)

. C. Redistributing processors

There are two major cases for which it may be useful to redistribute processors: (1) in a fault-free scenario, when an application ends, it releases processors that can be used to accelerate other applications, and (2) when an error strikes, we may want to force the release of processors, so that we can assign more processors to the application that has been slowed down by the error.

1) Fault-free scenario: We first consider a simplified scenario without checkpoint (nor failure), in order to explain how redistribution works. Consider for instance that q processors are released when application T 2 ends. We can allocate q 1 new processors to application T 1 , and q 3 new processors to application T 3 , where q 1 + q 3 = q. This redistribution will take some time (redistribution cost RC i , detailed below), after which T 1 and T 3 will resume execution, and we first need to compute the new expected completion time for their remaining fraction of work.

Consider that a redistribution is conducted at time t e (the end time of an application), and that application T i , initially with j processors, now has k = j + q > j processors. What will be the new finish time of T i ? The fraction of work already executed for T i is te ti,j , because the application was supposed to finish at time t i,j (see Figure 1). The remaining fraction of work is -= 1 ≠ te ti,j , and the time required to complete this work with k processors is t Õ , where

t Õ t i,k = -, hence t Õ = -t i,k = 3 1 ≠ t e t i,j 4 t i,k
. Furthermore, we need to add a redistribution cost: when moving from j to k = j + q processors, the application T i must redistribute its m i data across the processors. The application keeps its initial j processors, which now hold too much data, and enrolls q = k ≠ j new processors, which have no data yet. Each of the original j processors initially holds mi j data and will keep only mi k after the redistribution; it sends mi jk data to each of the newly enrolled q processors, thereby keeping mi j ≠(k≠j) mi jk = mi k data. In turn, each new processor receives mi jk data from j processors and duly gets mi k data in the end. What is the best schedule for such a redistribution, and what time does it require? We first account for a constant start-up overhead S, paid for initiating the redistribution call. Then we adopt a realistic one-port communication model [START_REF] Bhat | Efficient collective communication in distributed heterogeneous systems[END_REF] where a processor can send and receive at most one message at any time-step. Independent communications, involving distinct sender/receiver pairs, can take place in parallel; however, two messages sent by the same processor will be serialized. Recall that the time to communicate a message of size s is -+ s • . To schedule the redistribution, we build a bipartite graph G with j nodes on the left and q nodes on the right, and we count the number of rounds required to schedule the redistribution. Thanks to Konig's theorem [START_REF] Bondy | Graph theory with applications[END_REF], we obtain a number of rounds equal to max(j, k ≠ j) (see [START_REF] Benoit | Resilient application co-scheduling with processor redistribution[END_REF] for details), and the redistribution cost is

W done = te t i,j W todo = - j k t Õ time 0 te te + t Õ t i,j
RC jaek i = S + max(j, k ≠ j) ◊ 3 m i jk• + - 4 . ( 7
)
Needless to say, we would perform a redistribution if the cost of redistribution is lower than the benefit of allocating new processors to the application, i.e., if

t i,j ≠ (t e + t Õ ) > RC jaek i .
2) Accounting for failures: When struck by a fault, an application needs to recover from the failure and to reexecute some work. While the application loads were wellbalanced initially in order to minimize total execution time, now the faulty application is likely to exceed its expected execution time. If it becomes the longest application of the schedule, we try to assign it more processors so as to reduce its completion time, hence redistributing processors.

Because we use the double checkpointing algorithm as resilience model, we consider processors by pairs. We aim at redistributing pairs of processors either when an application is finished, at time t e (as in the fault-free scenario discussed in Section II-C1), or when a failure occurs, say at time t f . In each case, we need to compute the remaining work, and the new expected completion time of the applications that have been a ected by the event. Given an application T i , we keep track of the time when the last redistribution or failure occurred for this application, denoted as t lastRi . At time t (corresponding to the end of an application or to a failure), we know exactly how many checkpoints have been taken by application T i executed on j processors since t lastRi , and we let this number be N i,j :

N i,j = 7 t ≠ t lastRi • i,j 8 . ( 8
)
We begin with the case of an application completion: consider that an application finishes its execution at time t e , hence releasing some processors. We consider assigning some of these processors to an application T i currently running on j processors. The fraction of work executed by T i since the last redistribution is

te≠t lastR i ≠Ni,j Ci,j ti,j
, because we have to remove the cost of the checkpoints, during which the application did not execute useful work.

We apply the same reasoning for the second case, when a fault occurs. In this case, we need to consider the application T i where the failure stroke, and other applications T i Õ from which we would remove some processors (in order to give them to T i ). • Consider that application T i is running on j processors and subject to a failure at time t f . Therefore, T i needs to recover from its last valid checkpoint, and the fraction of work executed by T i corresponds to the number of entire periods completed since the last failure or redistribution t lastRi , each followed by a checkpoint. We can express it as Ni,j ◊(•i,j ≠Ci,j ) ti,j . • At time t f , consider application T i Õ , on which we perform a redistribution, moving from j Õ to j Õ ≠ q processors, with q > 0. The fraction of work executed by T i Õ can be computed as in the application ending case scenario: it is

t f ≠t lastR i Õ ≠N i Õ ,j Õ C i Õ ,j Õ t i Õ ,j Õ
. Finally, for any application subject to a redistribution or a failure, leti be the remaining fraction of work to be executed by T i , that is 1 minus the sum of the fraction of work executed before t lastRi and the fraction of work expressed above (computed between t lastRi and t). Similarly to the fault-free scenario, RC jaek i denotes the redistribution cost for application T i when moving from j to k processors. Redistribution can now add (k > j) or remove (k < j) processors to application T i , and the cost is expressed as:

RC jaek i = S + max(min(j, k), |k ≠ j|) ◊ 3 m i kj• + - 4 . ( 9
)
We are now ready to compute the new values of t lastRi for all applications subject to a failure or a redistribution, and we illustrate the di erent scenarios in Figure 2. Let t be the time of the event (end of application t = t e , or failure t = t f ), and consider that a redistribution is done either for a faulty application T i or for another time i Õ is performing a redistribution but it was not struck by a failure, it can start the redistribution at time t: either it is getting new processors that are available following the end of an application, or is is using less processors and can perform its redistribution. In all cases, we have

t lastR i ÕÕ = 0 processors C i,j C i,j Fault t D R i,j RC jaej+q i C i,j+q t lastR i T i C i Õ ,j Õ C i Õ ,j Õ RC j Õ aej Õ ≠q i Õ C i Õ ,j Õ ≠q T i Õ t lastR i Õ C i ÕÕ ,j ÕÕ C i ÕÕ ,j ÕÕ T i ÕÕ
t lastR i Õ = t + RC j Õ aek Õ i Õ + C i Õ
,k Õ . Note that we can have processors involved simultaneously in two redistributions, as they will only receive data from the other processors of the faulty application T i , and send data to the other processors of the non-faulty application T i Õ . We assume that sends and receives can be done in parallel without slowdown.

Finally, the expected finish time of an application T i for which we have updated

t lastRi becomes t U i = t lastRi + t R i,k (- i ),
where k is the new number of processors on which T i is executed, andi the remaining fraction of work. Similarly to the fault-free scenario, we give extra processors to an application only if the new expected finish time t U i is lower than the one with no redistribution. Note that we consider that we cannot enroll processors that have not yet finished the current redistribution, i.e., if an event happens between t and t lastR i Õ in Figure 2, the processors involved in T i and T i Õ cannot be considered for a new redistribution.

D. Objective function

We can now state the objective function: Definition 1 (CoSched). Given n malleable applications {T 1 , . . . , T n }, their speedup profiles, and an execution platform with p identical processors subject to failures with individual rate ⁄, minimize the maximum of the expected completion times of the applications. Redistributions are allowed only when an application completes execution or is struck by a failure (with a cost specified in Section II-C).

III. Complexity results

We first consider the CoSched problem without redistributions in Section III-A and provide an optimal polynomial-time algorithm. Then, we prove that the problem becomes NP-complete with redistributions, even in a fault-free scenario (Section III-B).

A. Without redistributions

Aupy et al. [START_REF] Aupy | Co-scheduling algorithms for high-throughput workload execution[END_REF] designed a greedy algorithm to solve the problem with no redistribution, in a faultfree scenario. Their algorithm (called Optimal-1-packschedule) therefore works with t i,j values instead of t R i,j , and minimizes the execution time of the applications. As a minor detail, it does not take into account the fact that the number of processors assigned to an application must always be even in our setting, because we use the double checkpointing algorithm. It is not di cult to extend this algorithm to solve the problem with failures, but still without redistributions: Theorem 1. The CoSched problem without redistributions can be solved in polynomial time O(n), where n is the number of applications.

Proof. We define a function ‡ such that

n q i=1 ‡(i) AE p,
where ‡(i) is the number of processors assigned to T i . A schedule with no redistribution corresponds to a unique function ‡, because the number of processors remains identical throughout the whole execution.

The fraction of work that each application must compute is -= 1, and we use the notation [START_REF] Heroux | Improving Performance via Mini-applications[END_REF]. Then, Algorithm 1 returns in polynomial time a schedule that minimizes the expected execution time. It greedily allocates processors to the longest application while its expected execution time can be decreased. If we cannot decrease the expected execution time of the longest application, then we cannot decrease the overall expected execution time, which is the maximum of the expected execution times of all applications.

T i 4 R ‡ T j if t R i, ‡(i) (1) AE t R j, ‡(j)
The proof that this algorithm returns an optimal cost schedule is similar to the proof in [START_REF] Aupy | Co-scheduling algorithms for high-throughput workload execution[END_REF]. We replace t i,j by t R i,j [START_REF] Heroux | Improving Performance via Mini-applications[END_REF], and instead of adding processors one-by-one, we add them two-by-two. Consequently, there are at most (p≠ 2n)/2 iterations. The complexity of Algorithm 1 is O(p ◊ log(n)).

Note that we added a test in Line 8 to check whether there is hope to decrease the expected execution time of the longest application. If T i ı has reached its maximum enrollment with ‡(i ı ) processors (according to the threshold j max (i ı ) defined with Equation ( 6)), then we cannot decrease its expected execution time. In the following, Algorithm 1: Optimal schedule with no redistribution. in such situations, we aim at making good use of extra processors through redistributions.

B. With redistributions

We can easily build examples to show the di culty of CoSched when redistributions are allowed, even when there are no failures: (i) Algorithm 1 is no longer optimal because it may give processors to an application with a poor speedup profile (i.e., it does not gain much from the additional processors); and (ii) the greedy variant where remaining processors are allocated to the application with the best speedup profile can also lead to nonoptimal schedules (see the companion research report [START_REF] Benoit | Resilient application co-scheduling with processor redistribution[END_REF] for details). Intuitively, these little examples show that CoSched seems to be of combinatorial nature when redistributions are taken into account, even with zero cost.

To establish the complexity of the problem with redistributions, we consider the simple case with no failures. Therefore, redistributions only at the end of an application, and any application changes at most n times its number of processors, where n is the total number of applications. We further consider that the redistribution cost is a constant equal to S, i.e., we let -= 0 and • = +OE in Equation [START_REF] Benoit | Resilient application co-scheduling with processor redistribution[END_REF]. Even in this simplified scenario, the problem is NP-complete:

Theorem 2. With constant redistribution costs and without failures, CoSched is NP-complete (in the strong sense).

Proof. We consider the associated decision problem: given a bound on the execution time D, is there a schedule whose expected execution time does not exceed D? The problem is obviously in NP: with n applications, there are at most n ≠ 1 redistributions, hence n intervals during which processor assignment remains constant for all applications. Given a schedule and the list of resources assigned to each application within these n intervals, it is easy to check in polynomial time that it is valid and that its execution time does not exceed the bound D. To establish the completeness, we use a reduction from 3-partition [START_REF] Garey | Computers and Intractability, A Guide to the Theory of NP-Completeness[END_REF] with distinct integers (which remains strongly NP-complete [START_REF] Hulett | Multigraph realizations of degree sequences: Maximization is easy, minimization is hard[END_REF]Corollary 7]). We consider an instance I 1 of 3-partition: given an integer B and 3m distinct positive integers a 1 , a 2 , . . . , a 3m such that for all i oe {1, . . . , 3m}, B/4 < a i < B/2 and with q 3m i=1 a i = mB, does there exist a partition I 1 , . . . , I m of {1, . . . , 3m} such that for all j oe {1, . . . , m}, |I j | = 3 and q ioeIj a i = B? Letting M = max 1AEiAE3m (a i ), we can assume w.lo.g. that B AE 3M , otherwise there is no solution to I 1 .

a 1 a 2 • • • a Õ 1,k S T 3m+k S S • • • a Õ 2,k S T 3m+k • • • a Õ 3,k T 3m+k S S • • • a 3m • • • S S S T 3m+k • • •
We build an instance I 2 of our problem, with n = 4m applications and p = n processors. We let D = 3M + 2 be the bound on the execution time. For each redistribution, each application whose processor number changes, simply pays the constant overhead S = 1 9m < 1 (communication costs are set to zero). For 1 AE i AE 3m, we have the following execution times: t i,1 = a i , and t i,j = 3ai 4 for j > 1 (these are small applications, and the work is strictly larger when using more than one processor). The last m applications are identical, with the following execution times: for 3m + 1 AE i AE 4m, t i,j = 4D≠B≠9S j for 1 AE j AE 4, and t i,j = 2 9 (4D ≠ B ≠ 9S) for j > 4 (these are large applications with a total work equal to 4D ≠ B ≠ 9S for 1 AE j AE 4, and a strictly larger work when using more than four processors). It is easy to check that the execution times are non-increasing with j, and that the work j ◊ t i,j is non-decreasing with j for all applications. Note that 4D ≠ B ≠ 9S > D. Clearly, the size of I 2 is polynomial in the size of I 1 . We now show that instance I 1 has a solution if and only if instance I 2 does.

Suppose first that I 1 has a solution. Let

I k = {a Õ 1,k , a Õ 2,k , a Õ 3,k }, for k oe {1, . . . , m}.
We build the following schedule for I 2 : initially, each application has a single processor. When an application T i finishes its execution (at time a i ), with 1 AE i AE 3m, its processor is redistributed to application T 3m+k , given that a i oe I k . Both the single processor of T i and each currently enrolled processor of T 3m+k pay a time overhead S for this redistribution, see Figure 3 for an illustration. Because the a i 's are all distinct, the successive redistributions occur at di erent time-steps, and the redistribution intervals of size S do not overlap. Each application T 3m+k starts with 1 processor and proceeds first with 2 processors (then paying an overhead S for its single processor before the redistribution), then with 3 processors (then paying an overhead S for each of its two processors before the redistribution), and finally with 4 processors (then paying an overhead S for each of its three processors before the redistribution) for some time in the end of its execution, because M + S < D. The total overhead due to the redistributions involving the three small tasks giving resources to T 3m+k is therefore 9S. Now, each application T 3m+k always executes with an optimal work profile, and actually completes its execution in time D. Indeed, the 4 processors finally assigned to T 3m+k have to complete a total work of a

Õ 1,k + a Õ 2,k + a Õ 3,k + 4D ≠ B ≠ 9S = 4D ≠ 9S
, and there are exactly 3(D ≠ S) + D ≠ 6S = 4D ≠ 9S time slots available for computations. Again, because M + S < D, all small applications also complete before the deadline, and we have a solution to I 2 .

Suppose now that I 2 has a solution. Initially, we have one processor per application, because there are exactly n processors and n applications. We first show that each small application T i terminates before the end of the schedule, and that its processor must be redistributed. Indeed, a i AE M < D, and if we do not redistribute the processor assigned to T i when it completes, then this processor stays idle for D ≠ a i > D ≠ M time steps. But the total work to execute is at least Because the a i 's are distinct, the 3m redistributions at the end of the 3m small tasks do not overlap. The first m redistributions involve at least another application running on one processor, which also looses S time-steps. The next m redistributions involve at least another application running on two processors, which costs 2S work units, and finally the last m redistributions involve at least another application running on three processors, hence costing 3S work units. Altogether, we have at least 9mS work units for redistribution costs. But the total work is at least nD ≠ 9mS, and the area of the computing window is nD. This means that we pay exactly 9mS for redistributions, and that all the work is perfectly parallel. We now draw two consequences:

q 3m i=1 a i + m ◊ (4D ≠ B ≠ 9S) = m(4D≠9S),
• When a small task completes, the redistribution of its processor involves a single other application (otherwise we would end with strictly more than 9mS redistribution overhead). • This processor is redistributed to a large application, because all the work is perfectly parallel. There are 3m processors to redistribute to m large applications, and none of them can receive more than 3 processors, again because all the work is perfectly parallel.

Hence, each large application is assigned exactly 3 new processors throughout its execution. Formally, for 1 AE k AE m, the large application T 3m+k receives processors from 3 small applications T i with i oe

I k = {a Õ 1,k , a Õ 2,k , a Õ 3,k }, for k oe {1, . . . , m}. The total work of these four processors is 4D ≠ B ≠ 9S + a Õ 1,k + a Õ 2,k + a Õ 3
,k and there are 4D ≠ 9S available time-steps for them. Hence a Õ 1,k +a Õ 2,k +a Õ 3,k AE B. This is true for all triplets of small applications, and because q 3m i=1 a i = mB, we must have an equality for each triplet, hence the solution to I 1 .

Remark. We conjecture that CoSched remains NPcomplete with zero redistribution cost. This is because of the combinatorial exploration suggested by the examples.

But this remains an open problem!

IV. Heuristics

In this section, we introduce polynomial-time heuristics to solve the general CoSched problem with both failures and redistributions. Before performing any redistribution, we need to choose an initial allocation of the p processors to the n applications. We use the optimal algorithm without redistribution discussed in Section III-A (Algorithm 1).

We first discuss the general structure of the heuristics in Section IV-A. Then, we explain how to redistribute available processors in Section IV-B, and the two strategies to redistribute when failures occur in Section IV-C. The pseudo-codes for all algorithms are available in the companion research report [START_REF] Benoit | Resilient application co-scheduling with processor redistribution[END_REF].

A. General structure

All heuristics share the same skeleton: we iterate over each event (either a failure or an application termination) until total remaining work is equal to zero. If some applications are still working for a previous redistribution, (i.e., the current time t is smaller than t lastRi for these applications), then we exclude them for the next redistribution, and add them back into the list of applications after the current redistribution is completed. If an application ends, we redistribute available processors as will be discussed in Section IV-B. Then, if there is a failure, we calculate the new expected execution time of the faulty application. Also, we remove from the list the applications that end before t lastR f , and we release their processors. Afterwards, we have to choose between trying to redistribute or do nothing. If the faulty application is not the longest application, the total execution time has not changed since the last redistribution. Therefore, because it is the best execution time that we could reach, there is no need to try to improve it. However, if the faulty application is the longest application, we apply a heuristic to redistribute processors (see Section IV-C).

B. Redistribution when an application ends

When an application ends, the idea is to redistribute the processors that it releases in order to decrease the expected execution time. The easiest way to proceed consists in adding processors greedily to the application with the longest execution time, as was done in Algorithm 1 to compute an optimal schedule. This time, we further account for the redistribution cost, and update the values ofi , t lastRi and t U i for each application i that encountered a redistribution. Therefore, this heuristic, called EndLocal, returns a new distribution of processors.

Rather than using only local decisions to redistribute available processors at time t, it is possible to recompute an entirely new schedule, using the greedy algorithm Algorithm 1 again, but further accounting for the cost of redistributions. This heuristic is called EndGreedy. Now, we need to compute the remaining fraction of work for each application, and we obtain an estimation of the expected finish time when each application is mapped on two processors. Similarly to Algorithm 1, we then add two processors to the longest application while we can improve it, accounting for redistribution costs.

Note that we e ectively update the values ofi and t lastRi for application T i only if a redistribution was conducted for this application. It may happen that the algorithm assigns the same number of processors as was used before. Therefore, we keep the updated value of the fraction of work in a temporary variablet i and update it whenever needed at the end of the procedure.

C. Redistribution when there is a failure

Similarly to the case of an application ending, we propose two heuristics to redistribute in case of failures. The first one, ShortestapplicationsFirst, takes only local decisions. First, we allocate the k available processors (if any) to the faulty application if that application is improvable. Then, if the faulty application is still improvable, we try to take processors from shortest applications (denoted T s ) in the schedule, and give these processors to the faulty application, until the faulty application is no longer improvable, or there are no more processors to take from other applications. We take processors from an application only if its new execution time is smaller than the execution time of the faulty application.

The second heuristic, IteratedGreedy, uses a modified version of the greedy algorithm that initializes the schedule (Algorithm 1) each time there is a failure, while accounting for the cost of redistributions. This is done similarly to the redistribution of EndGreedy explained in Section IV-B, except that we need to handle the faulty application di erently to update the values off and t lastR f .

V. Simulations

To assess the e ciency of the heuristics defined in Section IV, we have performed extensive simulations. The simulation settings are discussed in Section V-A, and results are presented in Section V-B. Note that the code is publicly available at http://graal.ens-lyon.fr/~abenoit/ code/redistrib, so that interested readers can experiment with their own parameters.

A. Simulation settings

To evaluate the quality of the heuristics, we conduct several simulations, using realistic parameters. The first step is to generate a fault distribution: we use an existing fault simulator developed in [START_REF] Bougeret | Checkpointing strategies for parallel jobs[END_REF], [START_REF] Bosilca | Unified model for assessing checkpointing protocols at extreme-scale[END_REF]. In our case, we use this simulator with an exponential law of parameter ⁄. The second step is to generate a fault-free execution time for each application (the t i,j value). We use a synthetic model to generate the execution profiles in order to represent a large set of scientific applications. The application model that we use is a classical one, similar to the one used in [START_REF] Aupy | Co-scheduling algorithms for high-throughput workload execution[END_REF]. For a problem of size m, we define the sequential time: t(m, 1) = 2 ◊ m ◊ log 2 (m). Then we can define the parallel execution time on q processors:

t(m, q) = f ◊ t(m, 1) + (1 ≠ f ) t(m, 1) q + m q log 2 (m). ( 10
)
The parameter f is the sequential fraction of time, we fix it to f = 0.08. So 92% of time is considered as parallel. The factor m q log 2 (m) represents the overhead due to communications and synchronizations. Finally, we have t i,j (m i ) = t(m i , j) where t i,j (m i ) is the execution time for application T i with a problem of size m i on j identical processors.

Finally, we assign to each application T i a random value for the number of data m i such that: m inf AE m i AE m sup . We set m inf = 1, 500, 000 and m sup = 2, 500, 000 to have execution times long enough so that several failures are likely to strike during execution. With such a value for m sup , the longest execution time in a fault-free execution is around 100 days. We also consider two di erent data distribution cases, (i) very heterogeneous with m inf = 1, 500, and (ii) homogeneous with m inf = 2, 499, 000, and detailed results for these distributions are available in [START_REF] Benoit | Resilient application co-scheduling with processor redistribution[END_REF].

The cost of checkpoints for an application T i with j processors is C i,j = C i /j, where C i is proportional to the memory footprint of the application. We have C i = m i ◊c, where c is the time needed to checkpoint one data unit of m i . The default value is c = 1, unless stated otherwise. The synchronisation cost value S is fixed to S = 0 for all following experiments. Finally, the MTBF of a single processor is fixed to 100 years, unless stated otherwise.

Note that we assume that a failure can strike during checkpoints but not during downtime, recovery and while the processor is performing some redistribution.

B. Results

To evaluate the heuristics, we execute each heuristic 50 times and we compute the average makespan, i.e., the longest execution time in the pack. We compare the makespan obtained by the heuristics to the makespan (i) in a faulty context without any redistribution (worst case), and (ii) in a fault-free context with redistributions (best case). We normalize the results by the makespan obtained in a faulty context without any redistribution, which is expected to be the worst case. The execution in a faultfree setting provides us an optimistic value of the execution of the application in the ideal case where no failures occur.

We consider all four possible combinations of EndLocal or EndGreedy with ShortestapplicationsFirst or IteratedGreedy.

a) Performance in a fault-free context: Figure 4 shows the impact of redistribution in a fault-free context with 1000 applications, where we vary the number of processors from 2000 to 10000. In this case, we compare EndLocal with EndGreedy (see Section IV-B). The two heuristics have a very similar behavior, leading to a gain of more than 20% with less than 4000 processors, and a slightly better gain for the EndGreedy global heuristic. When the number of processors increases, the e ciency of both heuristics decreases to converge to the performance without redistribution. Indeed, there are then enough processors so that each application does not make use of the extra processors released by ending applications.

In the heterogeneous context (with m inf = 1500), the gain due to redistribution is even larger (see [START_REF] Benoit | Resilient application co-scheduling with processor redistribution[END_REF]).

b) Impact of n: Figure 5 shows the impact of the number of applications n when the number of processors is fixed to 5000. The results show that having more applications increases the e ciency of both heuristics.

With n = 1000, we obtain a gain of more than 40% due to redistributions. The reason is that when n increases, the number of processors assigned to each application decreases, then heuristics have more flexibility to redistribute.

Note that, as expected, IteratedGreedy is better than ShortestapplicationsFirst, because it recomputes a complete new schedule at each fault, instead of just allocating available processors from shortest applications to the faulty application. Using EndGreedy with IteratedGreedy does not improve the performance, while EndGreedy is useful with Shortestapplica-tionsFirst, hence showing that complete redistributions are useful, even when only performed at the end of an application. Similar results can be observed in the homogeneous and heterogeneous cases, and similar conclusions are drawn when varying p for a fixed value of n (see [START_REF] Benoit | Resilient application co-scheduling with processor redistribution[END_REF]). c) Impact of MTBF: Figure 6 shows the impact of the MTBF on the performance of redistributions. We vary the MTBF of a single processor between 5 years and 125 years. When the MTBF decreases, the number of failures increases, consequently the performance of both heuristics decreases. The performance of IteratedGreedy is closely linked to the MTBF value. Indeed, it tends to favor a heterogeneous distribution of processors (i.e., applications with many processors and applications with few processors). If an application is executed on many processors, its MTBF becomes very small and this application will be hit by more failures, hence it becomes even worse than without redistribution! d) Impact of checkpointing cost: Figure 7 shows the impact of the checkpointing cost on a platform with 100 applications and 1000 processors. To do so, we multiply the checkpointing cost by c in Figure 7 (recall that c is the time needed to checkpoint one data unit). When c decreases, the performance of the heuristics increases and the gap between the execution time in a fault-free context and a fault context becomes small. Indeed, if checkpoints are cheap, a lot of checkpoints can be taken, and the average time lost due to failures decreases. Additionally, we show in [START_REF] Benoit | Resilient application co-scheduling with processor redistribution[END_REF] that the sequential fraction of time f of the applications also has an impact on performance: as expected, when applications are more parallel, the redistribution is more e cient.

e) Summary: Altogether, we observe that Iterated-Greedy achieves better performance than Shortestap- plicationsFirst, mainly because it rebuilds a complete schedule at each fault, which is very e cient but also costly. Nevertheless, when the MTBF is low (around 10 years or less), ShortestapplicationsFirst becomes better than IteratedGreedy. In a faulty context, we gain flexibility from the failures and we can achieve a better load balance. We observe that the ratio between the number of applications and the number of processors plays an important role, because having too many processors for few applications leads to a deterioration of performance. We also show that the cost of checkpointing and the fraction of sequential time have a significant impact on performance.

Finally, we point out that all four heuristics run within a few seconds, while the total execution time of the application takes several days, hence even the more costly combination IteratedGreedy-EndGreedy incurs a negligible overhead.

VI. Conclusion

In this paper, we have designed a detailed and comprehensive model for scheduling a pack of applications on a failure-prone platform, with processor redistributions. We have introduced a greedy polynomial-time algorithm that returns the optimal solution when there are failures but no processor redistribution is allowed. We have shown that the problem of finding a schedule that minimizes the execution time when accounting for redistributions is NP-complete in the strong sense, even with constant redistribution costs and no failures. Finally, we have provided several polynomial-time heuristics to redistribute e ciently processors at each failure or when an application ends its execution and releases processors. The heuristics are tested through extensive simulations, and the results demonstrate their usefulness: a significant improvement of the execution time can be achieved thanks to the redistributions.

Further work will consider partitioning the applications into several consecutive packs (rather than one) and conduct additional simulations in this context. We also plan to investigate the complexity of the online redistribution algorithms in terms of competitiveness. It would also be interesting to deal not only with fail-stop errors, but also with silent errors. This would require adding verification mechanisms to detect such errors.

Figure 1 :

 1 Figure 1: Work representation for application T i at time t e .

Figure

  Figure 2: Example of redistribution when a fault strikes application Ti . The colored rectangles correspond to useful work done by T i and T i Õ before the failure. T i ÕÕ is not a ected by the failure, since it does not perform a redistribution.

3m small apps m large apps DFigure 3 :

 apps3 Figure 3: Illustration for the proof of Theorem 2.

  assuming perfect parallelism. If the remaining n ≠ 1 processors work all the time, they contribute for (n ≠ 1)D. If the processor assigned to T i works at most M time-steps, we must have m(4D ≠ 9S) AE (n ≠ 1)D + M , or equivalently 9mS Ø D ≠M . But D ≠M > 2, and 9mS AE 1 by definition of S, a contradiction.

Figure 5 :

 5 Figure 5: Impact of n with p = 5000 processors.

Figure 6 :

 6 Figure 6: Impact of MTBF with n = 100 and p = 5000.

  Fault-free context with ReDistrib (EndLocal)

Figure 7 :

 7 Figure 7: Impact of checkpointing cost.

  2: Example of redistribution when a fault strikes application T i . The colored rectangles correspond to useful work done by T i and T i Õ before the failure. T i ÕÕ is not a ected by the failure, since it does not perform a redistribution. application T i Õ . After a redistribution, we always start by taking a checkpoint before computing with the new period. Therefore, if a fault occurs, we do not have to redistribute again.For the faulty application T

i , the new value of t lastRi hence becomes t lastRi = t + D + R i,j + RC jaek i + C i,k (we need to account for the downtime and recovery). However, if T