Anne Benoit

Valentin Le Fèvre

Padma Raghavan

Yves Robert

Hongyang Sun

Design and Comparison of Resilient Scheduling Heuristics for Parallel Jobs

This paper focuses on the resilient scheduling of parallel jobs on high-performance computing (HPC) platforms to minimize the overall completion time, or makespan. We revisit the classical problem while assuming that jobs are subject to transient or silent errors, and hence may need to be re-executed each time they fail to complete successfully. This work generalizes the classical framework where jobs are known offline and do not fail: in the classical framework, list scheduling that gives priority to longest jobs is known to be a 3-approximation when imposing to use shelves, and a 2-approximation without this restriction. We show that when jobs can fail, using shelves can be arbitrarily bad, but unrestricted list scheduling remains a 2-approximation. The paper focuses on the design of several heuristics, some list-based and some shelf-based, along with different priority rules and backfilling strategies. We assess and compare their performance through an extensive set of simulations, using both synthetic jobs and log traces from the Mira supercomputer.

Introduction

One of the main challenges faced by today's HPC platforms is resilience, since such platforms are confronted with many failures or errors due to their large scale [START_REF] Snir | Addressing failures in exascale computing[END_REF]. Indeed, the number of failures is known to grow proportionally with the number of nodes on a platform [START_REF] Herault | Fault-Tolerance Techniques for High-Performance Computing, Computer Communications and Networks[END_REF], and the largest supercomputers today experience several failures per day. There are two main classes of errors that can cause failures in an application's execution, namely, fail-stop and silent errors. While fail-stop errors cause the execution to terminate (e.g., due to hardware fault), large-scale platforms are also confronted with silent errors, or silent data corruptions (SDCs). Such errors are caused by cosmic radiation or packaging pollution, striking either the cache or memory units (bit flips), or the CPU operations [START_REF] O'gorman | The effect of cosmic rays on the soft error rate of a DRAM at ground level[END_REF][START_REF] Ziegler | Cosmic ray soft error rates of 16-Mb DRAM memory chips[END_REF]. Even though any bit can be corrupted, the execution continues (unlike fail-stop errors), hence the error is transient, but it may dramatically impact the result of a running application. Many silent errors can be accurately detected by verifying the data using dedicated, lightweight detectors (e.g., [START_REF] Chen | LADR: Low-cost application-level detector for reducing silent output corruptions[END_REF][START_REF] Chen | Online-ABFT: An online algorithm based fault tolerance scheme for soft error detection in iterative methods[END_REF][START_REF] Guhur | Lightweight and accurate silent data corruption detection in ordinary differential equation solvers[END_REF][START_REF] Wu | Fault tolerant matrix-matrix multiplication: Correcting soft errors online[END_REF]). In this work, we focus on job failures caused by silent errors, and we aim to design resilient scheduling heuristics while assuming the availability of ad-hoc detectors to detect such errors.

The problem of scheduling a set of independent jobs on parallel platforms with the goal of minimizing the total completion time, or makespan, has been extensively studied (see Section 2). Jobs may be parallel and should be executed on a given number of processors for a certain duration; both the processor requirement and the execution time of each job are known at the beginning. Such jobs are called rigid jobs, contrarily to moldable or malleable jobs, whose processor allocations can vary at launch time or during execution [START_REF] Feitelson | Theory and practice in parallel job scheduling[END_REF]. While moldable or malleable jobs offer more flexibility in the execution, rigid jobs remain the most prevalent form of parallel jobs submitted on today's HPC systems, and we focus on rigid jobs in this paper.

Unlike the classical scheduling problem without job failures, we consider failure-prone platforms subject to silent errors. Hence, at the end of each job's execution, an SDC detector will flag if a silent error has occurred during its execution. In this case, the job must be re-executed until it has been successfully completed without errors. For a set of jobs, each execution may lead to a different failure scenario, depending upon the jobs that have experienced failures as well as the number of such failures. The objective is to minimize the makespan under any failure scenario, as well as the expected makespan, averaged over all possible failure scenarios, where each scenario is weighted by a probability that governs its occurrence under certain failure assumptions. Since a failure scenario is unknown a priori, the scheduling decisions must be made dynamically on-the-fly, whenever an error has been detected. As a result, even for the same set of jobs, different schedules may be produced, depending on the failure scenario that occurred in a particular execution.

Building upon the existing framework for scheduling parallel jobs without failures, we propose two scheduling strategies, namely, a list-based strategy and a shelf-based strategy. While list-based schedules have no restrictions on the starting times of the jobs, shelf-based schedules group all jobs into subsets of jobs having the same starting time (called shelves); a shelf of jobs can start its execution once the longest job from the previous shelf has completed. For list-based scheduling, practical systems also employ a combination of reservation and backfilling strategies with different job priority rules to increase the system utilization. On platforms with no failures, variants for all of these strategies exist that could achieve constant approximations for the makespan (see Section 2 for details). The main focus of this paper is to extend these existing heuristics to execution scenarios with job failures, and to experimentally compare their performance using a variety of job and platform configurations.

Our main contributions are the following:

• We propose a formal model for the problem of resilient scheduling of parallel jobs on failure-prone platforms. The model formulates the performance of an algorithm under both worst-case and expected executions. • We design a resilient list-based strategy, and prove that its greedy variant achieves (2 -1 P )-approximation, and its reservation variant is (3 -4 P +1 )-approximation, where P is the total number of processors. These results apply to both worst-case and expected makespans.

• We design a resilient shelf-based strategy, but we show that, under some failure scenarios, any shelf-based algorithm has an unbounded approximation ratio, thus having a makespan that is arbitrarily higher than the optimal makespan in the worst case. • We conduct an extensive set of simulations to evaluate and compare different variants of these heuristics using both synthetic jobs and log traces from the Mira supercomputer. The results show that the performance of these resilient scheduling heuristics is close to the optimal in practice, even when confronted with failures. The rest of this paper is organized as follows: Section 2 describes the background of parallel job scheduling and presents some related work. The formal models and the problem statement are presented in Section 3. The key contributions of the paper are presented in Section 4, where we describe both list-based and shelf-based strategies, and analyze their performance. Section 5 presents an extensive set of simulation results and highlights the main findings. Finally, Section 6 concludes the paper and discusses future directions.

2 Background and Related Work

This section describes the background of scheduling rigid parallel jobs and reviews some related work.

Different scheduling flavors and strategies

Historically, scheduling parallel jobs comes in two flavors: if a job requests p processors, either any subset of p processors can be assigned, or only subsets of p contiguous processors can be chosen. In the latter case, processors are organized as a linear array and labeled from 1 to P , where P is the total number of processors; then only neighboring processors (whose labels differ by one) can be assigned to a job. The contiguous variant is equivalent to the rectangle strip packing problem, where rectangles are to be stacked (without rotation) within a strip of width P : rectangle widths represent processor numbers, and rectangle heights represent execution times.

Most scheduling strategies also come in two flavors: either the schedule is restricted to building shelves (also referred to as levels in some literature), or it is unrestricted, in which case the jobs are often scheduled based on an ordered list. Shelves are subsets of jobs with the same starting time, and for which each of the P processors is used at most once: the height of a shelf is the length of its longest job; when the shorter jobs complete, their processors become idle, but these processors are not reassigned to other jobs until the completion of the longest job of the shelf. Thus, a shelf resembles a bookshelf, hence the name. Shelf-based schedules play an important role in HPC, because they correspond to batched execution scenarios, where jobs are grouped into batches that are scheduled one after another. Note that for shelf-based algorithms, the contiguous and non-contiguous variants collapse.

Offline scheduling of rigid jobs

To minimize the makespan for a set of rigid jobs that are known statically and available initially (i.e., offline), the problem is obviously NP-complete, as it generalizes the problem of scheduling independent jobs on two processors, a variant of the 2-PARTITION problem [START_REF] Garey | Computers and Intractability, a Guide to the Theory of NP-Completeness[END_REF]. Coffman et al. [START_REF] Coffman | Performance bounds for level-oriented two-dimensional packing algorithms[END_REF] showed that the Next-Fit Decreasing Height (NFDH) algorithm is 3-approximation, and the First-Fit Decreasing-Height (FFDH) algorithm is 2.7-approximation. Both algorithms are shelf-based. See the survey by Lodi et al. [START_REF] Lodi | Two-dimensional packing problems: A survey[END_REF] for more results and lower bounds on the best possible approximation ratio for shelf-based algorithms, and see Han et al. [START_REF] Han | Strip packing vs. bin packing[END_REF] for the intricate relationship between strip packing and bin packing.

For list-based scheduling, Baker et al. [START_REF] Baker | Orthogonal packings in two dimensions[END_REF] showed that the Bottom-up Left-justified (BL) heuristic while ordering the jobs in decreasing processor requirement achieves 3-approximation. Turek et al. [START_REF] Turek | Approximate algorithms scheduling parallelizable tasks[END_REF] showed that ordering jobs in decreasing execution time is also 3-approximation. Moreover, both algorithms guarantee contiguous processor allocations for all jobs. Without the contiguous processor constraint, several works [START_REF] Feldmann | Dynamic scheduling on parallel machines[END_REF][START_REF] Garey | Bounds for multiprocessor scheduling with resource constraints[END_REF][START_REF] Turek | Approximate algorithms scheduling parallelizable tasks[END_REF] showed that the greedy list-scheduling heuristic achieves 2-approximation. Finally, Jansen [START_REF] Jansen | A (3/2+ ) approximation algorithm for scheduling moldable and non-moldable parallel tasks[END_REF] presented a (3/2+ )-approximation algorithm for any fixed > 0. This is the best result possible, since a lower bound on the approximation ratio is 3/2, which holds even when considering asymptotic performance [START_REF] Johannes | Scheduling parallel jobs to minimize the makespan[END_REF].

Online scheduling of rigid jobs

In the online problem, a set of rigid jobs arrive dynamically over time and information of a job is not known until the job has arrived. In this case, the list-based greedy algorithm maintains a competitive ratio of 2 [START_REF] Johannes | Scheduling parallel jobs to minimize the makespan[END_REF][START_REF] Naroska | On an on-line scheduling problem for parallel jobs[END_REF]. Chen and Vestjens [START_REF] Chen | Scheduling on identical machines: How good is LPT in an on-line setting[END_REF] showed a 1.3473 lower bound on the competitive ratio of any deterministic online algorithm even when all jobs are sequential. Shmoys et al. [START_REF] Shmoys | Scheduling parallel machines on-line[END_REF] showed that by collecting all jobs that arrive during a batch and then scheduling them together in the next batch, one can transform any capproximation offline algorithm into a 2c-competitive online algorithm. We point out that this technique, however, does not apply to the model considered in this paper, because it relies on jobs having fixed, although unknown, release times, whereas the "new job arrivals" in our model (corresponding to failed jobs restarting) depend on the decisions made on-the-fly by the schedulers.

Batch schedulers in practical systems

In practical systems, parallel jobs are often scheduled by batch schedulers [START_REF] Jackson | Core Algorithms of the Maui Scheduler[END_REF][START_REF] Staples | TORQUE resource manager[END_REF][START_REF] Yoo | SLURM: Simple Linux Utility for Resource Management[END_REF] that use a combination of reservation and backfilling strategies: while high-priority jobs are scheduled by reserving processors in advance, low-priority ones are used to fill in the "holes" to improve system utilization. Two popular backfilling strategies are conservative [START_REF] Mu | Utilization, Predictability, Workloads, and User Runtime Estimates in Scheduling the IBM SP2 with Backfilling[END_REF] and aggressive (a.k.a. EASY ) [START_REF] Lifka | The ANL/IBM SP Scheduling System[END_REF][START_REF] Skovira | The EASY -LoadLeveler API Project[END_REF]. The former gives a reservation for every job in the queue, and a lower-priority job is moved forward as long as it does not delay the reservation for any higher-priority job. The latter only gives reservation to the job at the head of the queue (i.e., the one with the highest priority), and backfilling is allowed without delaying this highest-priority job. As jobs arrive over time, most practical schedulers use First-Come First-Serve (FCFS) in conjunction with these strategies to prevent job starvation, but no worst-case performance guarantee is known. Various priority rules have been empirically evaluated to characterize and tune their performance for different metrics (e.g., [START_REF] Gaussier | Online tuning of EASY-backfilling using queue reordering policies[END_REF][START_REF] Srinivasan | Characterization of backfilling strategies for parallel job scheduling[END_REF][START_REF] Wong | Evaluating the EASY-backfill job scheduling of static workloads on clusters[END_REF]).

Models

In this section, we formally present the models, the problem statement, and the main assumptions we make in the paper.

Job model

We consider a set J = {J 1 , J 2 , . . . , J n } of n parallel jobs to be executed on a platform consisting of P identical processors. All jobs are released at the same time, corresponding to the batch scheduling scenario in an HPC environment. We focus on rigid jobs, which must be executed with a fixed number of processors set by the user when the job is submitted1 . For each job J j ∈ J , let p j ∈ {1, 2, . . . , P } denote its fixed (integral) processor allocation, and let t j denote its error-free execution time. The area of the job is defined as a j = p j × t j .

Error model

We consider failures that manifest as silent errors or silent data corruptions (SDCs) [START_REF] Snir | Addressing failures in exascale computing[END_REF] that could corrupt a job during execution. A silent error detector is assumed to be available for each job, which is triggered at the end of the job's execution. If an error is detected, the job needs to be re-executed, followed by another error detection. This process repeats until the job completes successfully without errors. Current state-of-the-art SDC detectors are typically lightweighted (e.g., ABFT for matrix computations [START_REF] Chen | Online-ABFT: An online algorithm based fault tolerance scheme for soft error detection in iterative methods[END_REF][START_REF] Wu | Fault tolerant matrix-matrix multiplication: Correcting soft errors online[END_REF], data analytics for scientific applications [START_REF] Chen | LADR: Low-cost application-level detector for reducing silent output corruptions[END_REF][START_REF] Guhur | Lightweight and accurate silent data corruption detection in ordinary differential equation solvers[END_REF]), and hence incur a negligible cost compared to the job's overall execution time.

All the list-based and shelf-based scheduling heuristics introduced and compared in this paper are agnostic of the probability of each job to fail any given number of times. Specifically, for a job J j , consider a particular run where it fails f j times before succeeding on the (f j + 1)-th execution. The probability that this happens is denoted as q j (f j ). Let f = (f 1 , f 2 , . . . , f n ) denote a failure scenario, i.e., a vector of the number of failed execution attempts for all jobs, during a particular run. Assuming that errors occur independently for different jobs, the probability that this combined failure scenario happens can be computed as Q(f ) = j=1...n q j (f j ). The failure scenario f , as well as the associated probabilities q j (f j ) and Q(f ) may be unknown to the scheduler.

Problem statement

We study the following resilient scheduling problem: Given a set J of parallel jobs, find a schedule for J on P identical processors under any failure scenario f = (f 1 , f 2 , . . . , f n ). Here, a schedule for f is defined by a collection s = ( s 1 , s 2 , . . . , s n ) of starting time vectors for all jobs, where vector s j = (s

(1) j , s (2) j , . . . , s (f j +1) j
) specifies the starting times for job J j at different execution attempts until success.

The objective is to minimize the overall completion time of all jobs, or the makespan. Suppose an algorithm Alg makes scheduling decision s during a failure scenario f , then the makespan of the algorithm for this scenario is defined as:

T Alg (f , s) = max j=1...n s (f j +1) j + t j . (1)
All scheduling decisions should be made while satisfying the following two constraints:

1. Processor constraint: The number of processors used at any time t by the set J t of running jobs should not exceed the total number P of available processors on the platform, i.e., J j ∈Jt p j ≤ P, ∀t.

Re-execution constraint:

A job cannot be re-executed if its previous execution attempt has not yet been completed, i.e., s

(i+1) j ≥ s (i) j + t j , ∀j = 1 . . . n, ∀i ≥ 1.
This scheduling problem, encompassing the failure-free problem as a special case, is clearly NP-hard. A scheduling algorithm Alg is said to be c-approximation if its makespan is at most c times that of an optimal scheduler for all possible sets of jobs under all possible failure scenarios, i.e.,

T Alg (f , s) ≤ c • T Opt (f , s * ) , (2)
where T Opt (f , s * ) denotes the optimal makespan with scheduling decision s * under failure scenario f . Clearly, this optimal makespan admits the following two lower bounds:

T Opt (f , s * ) ≥ t max (f ) , (3)
T Opt (f , s * ) ≥ A(f ) P , (4)
where t max (f ) = max j=1...n (f j + 1) • t j is the maximum cumulative execution time of any job under f , and

A(f ) = n j=1 (f j + 1)
• a j is the total cumulative area.

In Section 4, we establish several approximation results, which are valid for any failure scenario regardless of its individual probability. This is the strongest result that can be obtained from a theoretical perspective. However, from a practical perspective, given a set of jobs, it is not easy to assess the performance of a scheduling heuristic if the probability Q(f ) = j=1...n q j (f j ) of each failure scenario f is not known. Thus, for the experiments in Section 5, we report the expected makespan of each heuristic under the standard exponential probability distribution, as explained below.

Expected makespan

Suppose the occurrence of silent errors striking the jobs follows an exponential probability distribution, and that the mean time between error (MTBE) of an individual processor is µ, so the error rate of the processor is given by λ = 1/µ. For a job J j executed on p j processors, the probability that the job is struck by a silent error during execution is then given by q j = 1 -e -λp j •t j = 1 -e -λa j [START_REF] Herault | Fault-Tolerance Techniques for High-Performance Computing, Computer Communications and Networks[END_REF]. Then, the probability for job J i to fail f j times before succeeding on the (f j + 1)-th execution is q j (f j ) = q f j j (1 -q j ). Given a set J of jobs, we can now define the expected makespan of an algorithm Alg, taken over all possible failure scenarios weighted by their probabilities, as:

E(T Alg ) = f Q(f ) • T Alg (f , s) . (5)
In this case, an algorithm is a c-approximation if we have:

E(T Alg ) ≤ c • E(T Opt ) , (6)
for all possible sets of jobs, where E(T Opt ) denotes the optimal expected makespan. This is because the inequality is true for each failure scenario, hence for the weighted sum. Obviously, the converse is not true: an algorithm could satisfy Equation ( 6) (thus achieving c-approximation in expectation) but be arbitrarily worse than the optimal on some (low probability) failure scenarios. Still, expected makespan provides a synthetic indicator on the performance of an algorithm under study, enabling easy and quantitative comparisons. Thus, we use it for the experimental evaluations in Section 5.

Static vs. dynamic scheduling

As all the information regarding the set of jobs (except the failure scenario f ) is available, one approach would be to make all scheduling decisions (i.e., starting times s) statically at the beginning, and then execute the jobs according to this static schedule. While this approach works for failure-free executions, it is problematic when jobs can fail and re-execute. In particular, a static schedule needs to pre-compute a (possibly infinite) sequence of starting times for all jobs to account for every possible failure scenario, while ensuring the satisfaction of the constraints. Pre-computing such a static schedule would be computationally intractable, especially when there turn out to be only a few failures in a run. In contrast, another more flexible approach is to make scheduling decisions dynamically depending on the particular failure scenario that is unveiled from an execution. For example, a scheduling algorithm may decide the starting time for the next execution attempt of a job depending on the failure scenario and schedule so far. As a result, even for the same set of jobs, the algorithm may produce different schedules in response to the different failure scenarios that could arise at runtime. In this paper, we adopt this dynamic approach.

Resilient Scheduling Heuristics

In this section, we present a resilient list-based heuristic (R-List) and a resilient shelf-based heuristic (R-Shelf) for scheduling rigid parallel jobs that could fail due to silent errors. We show that the greedy variant of R-List without reservation is 2-approximation, and a variant with reservations is 3-approximation. For R-Shelf, even though it achieves 3-approximation in the failure-free case, we show through an example that any resilient shelfbased algorithm may have an approximation ratio of Ω(ln P ) compared to the optimal in some failure scenario.

R-List scheduling heuristic

We first present a resilient list-based scheduling heuristic, called R-List, that schedules any set of jobs with the capability to handle failures. Al-gorithm 1 shows the pseudocode of R-List. It extends the classical batch scheduler that combines reservation and backfilling strategies. The algorithm first organizes all jobs in a list (or a queue) based on some priority rule. Then, whenever an existing job J k completes and hence releases processors (at time 0, a virtual job J 0 can be considered to complete), the algorithm schedules the remaining jobs in the queue. First, it checks if job J k completes with error. If so, the job will be inserted back into the queue, based on its priority, to be rescheduled later. All jobs in the queue are divided into two groups: the first m jobs with the highest priorities are each given a reservation at the earliest possible time, provided that any reservation made should not delay the starting times of the higher-priority jobs; the subsequent jobs in the queue (if any) are then examined one by one and backfilled to start at the current time, again if such backfilling does not affect any reservations for the higher-priority jobs. 2The R-List heuristic takes a parameter m, and depending on the value of m chosen, it resembles several scheduling strategies known in theory and practice:

• m = |Q| (Conservative backfilling [START_REF] Mu | Utilization, Predictability, Workloads, and User Runtime Estimates in Scheduling the IBM SP2 with Backfilling[END_REF]): this strategy makes reservations for all pending jobs in the queue; • m = 1 (Aggressive or EASY backfilling [START_REF] Lifka | The ANL/IBM SP Scheduling System[END_REF][START_REF] Skovira | The EASY -LoadLeveler API Project[END_REF]): this strategy makes a reservation only for the job at the head of the queue, and uses backfilling to schedule all remaining jobs in the queue; • m = 0 (Greedy scheduler [START_REF] Feldmann | Dynamic scheduling on parallel machines[END_REF][START_REF] Garey | Bounds for multiprocessor scheduling with resource constraints[END_REF][START_REF] Turek | Approximate algorithms scheduling parallelizable tasks[END_REF]): this strategy does not make any reservation, and uses backfilling to schedule all jobs in the queue. Note that, when m > 0 and when a job J k with high priority fails, it may be re-inserted back into the first part of the queue (i.e., among the top m jobs). This may require recomputing the existing reservations (made previously) for some jobs that have lower priority than J k . From an analysis point of view, we can think of each job completion as a trigger, which deletes all previous reservations and makes a fresh round of reservation and backfilling decisions based on the updated queue.

In the following, we denote by Reservation this variant of R-List with reservations (m > 0), and by Greedy the variant with m = 0.

Approximation ratios of R-List

We show that, under any failure scenario, Reservation with a particular priority rule is a (3-4 P +1 )-approximation, and that Greedy with any prior-Algorithm 1: R-List

Input: a set J = {J1, J2, • • • , Jn} of rigid jobs, with processor allocation pj and error-free execution time tj for each job Jj ∈ J , a platform with P identical processors, parameter m; Output: a list schedule with starting times for all jobs in J till they complete successfully. begin Insert all jobs into a queue Q according to some priority rule; whenever an existing job J k completes do if error detected for J k then Q.insert with priority(J k ); end // schedule high-priority jobs using reservation for j = 1, 2 . . . , min(m, |Q|) do Jj ← Q(j); Give job Jj an earliest possible reservation without delaying the reservation of job J j , ∀j = 1, . . . , j -1; end // schedule low-priority jobs using backfilling for j = m + 1, . . . , |Q| do Jj ← Q(j); if Job Jj can be scheduled at the current time without delaying the reservation of job J j , ∀j = 1 . . . m then execute job Jj at the current time; end end end end ity rule is a (2 -1 P )-approximation. According to Equation ( 6), these results directly imply the same approximation ratios for the respective heuristic variants in terms of the expected makespan.

Result for Reservation

We first consider the Reservation variant, while applying a priority rule that favors large jobs and uses any priority for small jobs. We call this rule Large Job First (LJF). Specifically, a job is said to be large if its processor allocation is at least P +1 2 , and small otherwise. The LJF rule specifies that: (1) all large jobs have higher priority than all small jobs; (2) the priorities for large jobs are based on decreasing processor allocation; and (3) the priorities for small jobs are defined arbitrarily.

The following proposition shows the performance of Reservation in any failure scenario using the above LJF rule. The result matches the 3approximation ratio [START_REF] Baker | Orthogonal packings in two dimensions[END_REF][START_REF] Turek | Approximate algorithms scheduling parallelizable tasks[END_REF] known for failure-free jobs.

Proposition 1. For any set of rigid parallel jobs under any failure scenario f , the makespan of Reservation with the LJF priority rule satisfies:

T R (f , s) ≤ (3 - 4 P + 1 ) • T Opt (f , s * ) . (7)
Proof Sketch. Due to the lack of space, we only sketch the proof here; the complete proof can be found in [START_REF] Benoit | Design and comparison of resilient scheduling heuristics for parallel jobs[END_REF]. Since R-List only allocates and de-allocates processors upon job completions (the starting time of a reservation is necessarily at a future job completion time as well), the entire schedule can be divided into a set of consecutive and non-overlapping intervals I = {I 1 , I 2 , . . . , I v }, where jobs only start (or complete) at the beginning (or end) of an interval. Let J j be a last successfully completed job in the schedule. We can divide I into two disjoint subsets I 1 and I 2 , where I 1 contains the intervals in which job J j is executing (including all of its execution attempts), and

I 2 = I\I 1 .
We show that the cumulative length T 1 of all intervals in I 1 satisfies T 1 ≤ t max (f ), and the number of utilized processors p(I) in any interval I ∈ I 2 satisfies p(I) ≥ P +1

2 . This gives rise to a makespan at most (3 -4 P +1 ) times the optimal.

Result for Greedy

We now consider the Greedy variant. The following proposition shows the performance of Greedy in any failure scenario regardless of the priority rule. The result generalizes the 2-approximation ratio [START_REF] Feldmann | Dynamic scheduling on parallel machines[END_REF][START_REF] Garey | Bounds for multiprocessor scheduling with resource constraints[END_REF][START_REF] Turek | Approximate algorithms scheduling parallelizable tasks[END_REF] known for failure-free jobs.

Proposition 2. For any set of rigid parallel jobs under any failure scenario f , the makespan of Greedy regardless of the priority rule satisfies:

T G (f , s) ≤ (2 - 1 P ) • T Opt (f , s * ) . (8)
Proof Sketch. The proof is similar to that of Proposition 1. Let I min denote the last-executed interval that has the minimum processor utilization p min = min p(I ) among all intervals in I. Consider a job J j that is running during interval I min . We now define I 1 to be the subset of intervals in which job J j is executing (including all of its execution attempts), and I 2 = I\I 1 . We show that the cumulative length T 1 of all intervals in I 1 satisfies T 1 ≤ t max (f ), and the number of utilized processors p(I) in any interval I ∈ I 2 satisfies p(I) ≥ P -p min + 1. This leads to a makespan at most (2 -1 P ) times the optimal. The complete proof can again be found in [START_REF] Benoit | Design and comparison of resilient scheduling heuristics for parallel jobs[END_REF].

R-Shelf scheduling heuristic

We now present a shelf-based scheduling heuristic, called R-Shelf, that schedules any set of parallel jobs onto a series of shelves while handling job failures.

Heuristic description Algorithm 2 shows the pseudocode of R-Shelf. As in R-List, the algorithm starts by organizing all jobs in a queue based on some priority rule. Whenever the jobs in the preceding shelf all complete (at time 0, a virtual shelf S 0 with no job in it can be considered to complete), the algorithm builds a new shelf and adds the remaining jobs to it. First, any job in the preceding shelf that completes with error will be inserted back into the queue based on its priority. Then, the algorithm scans the queue and adds a job to the new shelf if the job can fit in without violating the processor constraint. R-Shelf takes a binary parameter b that determines if backfilling is used in the process:

• b = 0 (No backfilling): the heuristic closes the new shelf upon encountering the first job in the queue that does not fit in the shelf. This resembles the Next-Fit (NF) strategy for bin-packing. • b = 1 (Backfilling): the heuristic scans all the jobs in the queue until no more job can be added to the new shelf. This resembles the First-Fit (FF) strategy for bin-packing. Once the jobs in the new shelf have been selected, they will simultaneously start their executions.

Inapproximability result For failure-free jobs, the variant of R-Shelf without backfilling and considering jobs in the non-increasing execution time order is equivalent to the Next-Fit Decreasing Height (NFDH) [START_REF] Coffman | Performance bounds for level-oriented two-dimensional packing algorithms[END_REF] algorithm for strip packing. The algorithm starts with the longest job J 1 , which is put on the first shelf, whose height is t 1 . Then, the next job J 2 is put on the same shelf if it fits in, meaning that p 1 + p 2 ≤ P , otherwise a new shelf is started for J 2 , whose height is t 2 . The algorithm proceeds like this, either putting the next job on the last shelf if it fits in, or creating a new shelf otherwise. Despite its simplicity, the algorithm is shown to be a 3-approximation for failure-free jobs [START_REF] Coffman | Performance bounds for level-oriented two-dimensional packing algorithms[END_REF][START_REF] Turek | Approximate algorithms scheduling parallelizable tasks[END_REF]. Now, when jobs can fail, we show that there exists a job instance J and a failure scenario f such that any shelf-based algorithm has a makespan T S (f , s) that is arbitrarily higher than the optimal makespan T Opt (f , s * ) regardless of the job priority used. This is in clear contrast with the 3approximation result for the failure-free case. Note that T Opt (f , s * ) is not Furthermore, since the P jobs have decreasing execution time and increasing number of failures, any shelf-based algorithm will have at least one shelf of height t j , for all 1 ≤ j ≤ P , thus having a makespan that is at least T S (f , s). Therefore, the same ratio applies to any shelf-based algorithm.

We conclude this section with an open problem. Instead of a single scenario, consider an exponential probability distribution and the expected makespan as defined in Section 3.4. Will R-Shelf or any shelf-based algorithm admit a constant approximation ratio in expectation? To answer this question seems difficult, because computing the expected makespan seems out of reach analytically. Given P = 10 in the above example, we find numerically (using a computer program) that the expected makespan ratio of R-Shelf is 1.00005 for λ = 10 -7 and 1.07 for λ = 10 -3 . We have not been able to build an example where this ratio (computed numerically) is greater than 3.

Performance Evaluation

We now evaluate and compare the performance of all heuristics presented in Section 4, using different job priority rules and backfilling strategies. The evaluation is performed by simulation using both synthetic jobs and jobs extracted from the log traces of the Mira supercomputer.

Simulation setup

We compare five different heuristics combined with seven different priority rules. The five heuristics are:

• For each of these five heuristics, we consider seven different job priority rules:

• Lpt/Spt (Longest/Shortest Processing Time): a job with a longer/shorter processing time will have higher priority; • Hpa/Lpa (Highest/Lowest Processor Allocation): a job with a higher/lower number of requested processors will have higher priority; • La/Sa (Largest/Smallest Area): a job with a larger/smaller area will have higher priority; • Random (Random): the priorities are determined randomly for all jobs.

We simulate two different settings, one using synthetic jobs and the other using real job traces from the Mira logs.

• Synthetic jobs: We generate 30 different job sets, each containing 100 jobs. For each job, the processor allocation is generated uniformly at random between 50 and 2000, while the execution time is generated uniformly at random between 100 and 20000 seconds. The total number of processors is set to be P = 10000. In the experiments, we also vary P to study its impact. • Jobs from Mira logs: We generate jobs by extracting from the log traces [START_REF]Mira log traces[END_REF] (of June 2019) of the Mira supercomputer, which has P = 49152 compute nodes. There were 4699 jobs submitted in June 2019, and we group the ones submitted each day as a set to form 30 sets of jobs. Figure 1(a) plots the number of jobs in each day of the month, varying between 66 and 277. The processor allocations of the jobs vary between 512 and 49152, and the execution times vary between 37 and 86494 seconds. Figure 1(b) plots these two parameters for all jobs in the month (with each point representing a job).

In both settings, silent errors are injected to the jobs based on the exponential distribution as described in Section 3.4. To study the impact of error rate, we further define the average failure probability for a set of jobs to be q = 1-e -λā , where ā = n j=1 a j /n is the average area of all jobs in the set. Intuitively, q represents the probability that a job with the average area over all jobs would fail due to silent errors. For a given value of q, we can compute the error rate as λ = -ln(1 -q)/ā, and hence the failure probability of any job J j with area a j to be q j = 1-e -λa j = 1-(1-q) a j /ā . Based on this q, we then randomly generate 1000 failure scenarios for the set of jobs following the probabilities. For each failure scenario f , we evaluate the makespans of the heuristics, normalized by the lower bound L(f ) = max(t max (f ), A(f )/P ) as defined in Equations ( 3) and ( 4). The normalized makespans are then averaged over the 1000 failure scenarios for comparison.

The simulation code for all experiments is publicly available at http: //www.github.com/vlefevre/job-scheduling.

Results for synthetic jobs

We first compare the performance of different heuristics using synthetic jobs. Here, we focus on assessing the impact of two parameters: the average failure probability q, and the total number of processors P . The results are averaged over the 30 different sets of jobs.

Figure 2 shows the performance of different heuristics when q varies from 0 to 0.9. First, we can see that, for all list-based heuristics, the normalized makespans first increase with q and then decrease. Indeed, a higher failure probability will result in a larger number of errors, thus increasing the difficulty of scheduling and hence the makespan. However, when the probability is too high, an excessive number of errors will occur, making the optimal scheduler perform equally worse and thus reducing the makespan ratios for the heuristics. For the shelf-based heuristics, the performance appears to be independent of the failure probability. Here, tasks that fail need to wait for the completion of the current shelf to be re-executed, so the number of shelves is mainly determined by the number of re-executions, which influences both the makespan and an optimal scheduler. The normalized makespan is thus mainly decided by the efficiency of the heuristic to fill one shelf, which does not depend on the failure probabilities. Second, the Lpt and La priorities lead to the best performance for all list-based heuristics, with Lpt performing better when q is low for R-List-1 and R-List-Q, and La performing better for R-List-0 under any q. For the shelf-based heuristics, Lpt and Spt are the two best priorities, which is not surprising as the performance of these algorithms is mainly determined by the duration of each shelf.

Figure 4(a) further compares the performance of the five heuristics using some of the best priorities. While most list-based heuristics behave similarly when there is no failure (i.e., q = 0), R-List-0 clearly outperforms the rest when jobs can fail. This corroborates the theoretical result that R-List-0 (i.e., Greedy) has the lowest approximation ratio regardless of the priority Normalized makespan

R-List-0 / Lpt R-List-0 / La R-List-1 / Lpt R-List-1 / La R-List-Q / Lpt R-List-Q / La R-Shelf-B / Lpt R-Shelf-NB / Lpt (a) 5000 10000 15000 20000 P 1.0 1.2 1.4 1.6 Normalized makespan R-List-0 / Lpt R-List-0 / La R-List-1 / Lpt R-List-1 / La R-List-Q / Lpt R-List-Q / La R-Shelf-B / Lpt R-Shelf-NB / Lpt (b)
Figure 4: Comparison of different heuristics with the best priority rules Lpt and/or La when: (a) q varies between 0 and 0.9, and P = 10000; and (b) P varies between 5000 and 20000, and q = 0.3. rule and failure scenario. Moreover, R-List-0 is also the heuristic that is least affected by job failures, with an increase in normalized makespan by less than 10% compared to the case of q = 0, while the other heuristics experience 20-30% increase in normalized makespan. Finally, R-Shelf-NB appears to be the worst heuristic for small and high probabilities of failure with a makespan that is up to 15% higher than that of R-List-0 (when q = 0.9), while R-List-Q is the worst for medium probabilities (e.g., 26% higher than that of R-List-0 for q = 0.5). The results are likely due to: (i) the restriction of R-Shelf-NB for building shelves in a schedule, which leads to poor performance for some failure scenarios (such as the one discussed in Section 4.3), and hence an increase in the expected makespan, and (ii) the fact that R-List-Q is more affected by the increasing failure probability.

Figure 3 shows the performance of different heuristics when the number of processors P varies from 5000 to 20000 while the failure probability is fixed at q = 0.3. Again, we can see that La and Lpt are the two best priority rules for all heuristics, with La performing better for R-List-0 and R-List-1, and Lpt performing better for other heuristics under all P . Also, the normalized makespans of the heuristics first increase with the number of processors and then tend to decrease. This is because when P is either too small (i.e., total resource is constrained) or too big (i.e., total resource is almost unconstrained), the optimal scheduler tends to have very similar performance as the heuristics.

We further compare the performance of the five heuristics using some of the best priorities in Figure 4(b). As in the previous experiment, the best heuristic is R-List-0 with the La priority, which is the least impacted by the total number of processors (with < 10% variations in normalized makespan). Also, R-List-Q gives the worst performance (with a 23% increase in makespan compared to R-List-0 with La when P = 15000) and has the largest variation (∼20%) in normalized makespan as the number of processors changes.

From these experiments, we can see that job failures and processor variations do have an impact on the relative performance of different heuristics. Nevertheless, the makespans of all the heuristics (with good priorities) are never more than 40% worse than the theoretical lower bound, which can be much less than the optimal makespan. The results suggest the robustness of these heuristics, and that they should actually perform really well in practice, even with job failures.

Results for jobs from Mira

We now evaluate the performance of different heuristics using real jobs from the Mira trace logs. Figures 5 and6 show the normalized makespans of all heuristics and priority rules under all 30 days (sets) of jobs with and without failures. We observe that the Lpt and La priorities again offer the best performance, with Lpt performing better this time for most job sets. This holds for every heuristic on average, especially when there is no failure (i.e., q = 0). As the failure probability increases, both Lpt and La (and even Hpa) give similar performance. The reason is that the processor allocations and execution times of the jobs in Mira are more skewed than those of the synthetic ones. Here, some jobs use a very large number of processors and have long execution times, which make them fail more often even with small values of q. As a result, the makespan lower bound is largely determined by the total execution times of these jobs, thus any priority rule that favors these jobs will achieve similar performance. Comparing different heuristics, we can see that R-List-0 again performs the best and R-Shelf-B the worse, especially with higher failure probability (q = 0.1). This is consistent with the previous findings and corroborates the analysis.

Table 1 summarizes the results of the five heuristics using the Lpt priority (which is overall the best one) over 30 days (sets) of jobs, which have an average of 157.63 jobs per day (set). As q increases to 0.05 and 0.1, the average number of failures rises to around 15 and 254, respectively. All list-based heuristics have good average makespan ratios that are very close to 1 (with low standard deviations), as well as good maximum makespan ratios that are lower than 1.5, while the two shelf-based heuristics have worse performance in comparison, even when failures are not present. The maxi-

(i) R-List-Q (with q = 0.1)
Figure 5: Performance of list-based heuristics for 30 job sets using the Mira trace logs (June 2019) with and without failures. Each row represents a different heuristic (R-List-0, R-List-1 and R-List-Q), and each column represents a different failure probability (q = 0, q = 0.05 and q = 0.1). The average number of failures for each job set is indicated on top of each plot. (f) R-Shelf-NB (with q = 0.1)

Figure 6: Performance of shelf-based heuristics for 30 job sets using the Mira trace logs (June 2019) with and without failures. Each row represents a different heuristic (R-Shelf-B and R-Shelf-NB), and each column represents a different failure probability (q = 0, q = 0.05 and q = 0.1). The average number of failures for each job set is indicated on top of each plot. Overall, these results confirm the efficacy and robustness of the resilient scheduling heuristics, not only for synthetic jobs, but also for real sets of jobs. In particular, both theory and practice have suggested that R-List-0 is the best heuristic when silent errors are present, and Lpt and La are the two best priorities for most cases. In all experiments we have conducted, this heuristic achieves a makespan that is within a few percent of the lower bound on average, and never more than 50% in the worst case.

Conclusion

In this paper, we have investigated the problem of scheduling rigid jobs onto a parallel platform subject to silent errors. We have revisited the classical scheduling algorithms in this new framework, where jobs that have been struck by errors must be re-executed (possibly many times) until success. We designed resilient list-based and shelf-based scheduling heuristics, along with different priority rules and backfilling strategies. On the theoretical side, we proved that variants of the list-based heuristic achieve a constant approximation ratio (2 or 3 depending whether reservation is used or not). We also showed that any shelf-based heuristic is no longer a constant-factor approximation, while a failure-free variant was known to be a 3-approximation. Extensive simulations conducted using both synthetic jobs and real traces from the Mira supercomputer demonstrate that these heuristics are quite robust, and achieve makespans close to the optimal. As highlighted by the theoretical analysis, the best strategy remains the unrestricted greedy list-based scheduling with no reservations, and good results are obtained in practice when job priorities are assigned by processing times (favoring jobs with long execution times) or by areas (favoring jobs with many processors and/or long execution times).

Some problems remain open, in particular for the study of shelf-based algorithms, whose expected makespan under the exponential probability dis-tribution is not known to be bounded by a constant factor of the optimal or not. A natural extension of this work would be to consider moldable jobs, whose processor allocations can be decided at launch time. However, for jobs with nonlinear speedup curves, changing the number of processors assigned to a job also changes its error probability under the exponential probability distribution, thereby severely complicating the problem, and thus calling for the design of novel heuristics.

  R-List-0: The list-based algorithm with m = 0; • R-List-1: The list-based algorithm with m = 1; • R-List-Q: The list-based algorithm with m = |Q|; • R-Shelf-B: The shelf-based algorithm with b = 1. • R-Shelf-NB: The shelf-based algorithm with b = 0.

Figure 1 :

 1 Figure 1: Data from the trace logs of the Mira supercomputer.

Figure 2 :Figure 3 :

 23 Figure2: Normalized makespans of different heuristics and priority rules over 30 sets of jobs when q varies between 0 and 0.9, and P = 10000.

  (c) R-List-0 (with q = 0.1)

22

 22

  13 .1 55 59 .2 94 24 .5 04 11 .3 92 22 .4 81 16 .6 99 12 .2 28 Normalized makespan 11 .0 78 11 .5 46 11 .8 55 60 .5 98 22 .9 73 30 1. 05 14 .7 83 55 .1 43 11 .8 55 58 .5 54 66 .2 53 64 .1 26 0. 04 22 .6 29 11 8. 37 6 14 4. 57 3 14 .7 34 38 .3 2 75 .6 87 44 .8 72 20 10 .4 6 29 .3 93 24 .6 75 73 .0 06 33 74 .8 4 29 6. 64 9 78 .0 65 25 3. 00 9 52 .7 82 31 .6 89

	4. 75 1 4. 46 9 4. 88 9 14 .0 02 5. 71 9 22 .8 97 4. 59 4 8. 42 9 4. 88 9 13 .3 61 12 .6 61 11 .8 52 21 .1 79 9. 10 5 18 .0 14 21 .7 72 6. 25 4 11 .2 28 15 .6 04 16 .1 88 47 .5 46 9. 33 7 10 .2 47 Lpt La Hpa Spt Sa Lpa	Random	2.25	La Lpt	Spt Hpa		Lpa Sa	Random
			2.00
			1.75
			1.50
			1.25
			1.00
				5	10	15	20	25	30
						Set
	(e) R-Shelf-NB (with q = 0.05)

Table 1 :

 1 Performance of different heuristics using Lpt priority for all 30 days (sets) of jobs from June 2019 on the Mira supercomputer. .051 1.051 1.407 1.441 8.78 × 10 -2 8.19 × 10 -2 8.23 × 10 -2 1.29 × 10 -1 1.45 × 10 -1 1.425 1.425 1.425 1.633 1.760 0.05 15.2913 1.031 1.049 1.061 1.129 1.141 6.72 × 10 -2 6.87 × 10 -2 7.76 × 10 -2 1.30 × 10 -1 1.40 × 10 -1 1.278 1.292 1.292 1.489 1.510 0.1 254.453 1.016 1.025 1.028 1.071 1.073 4.66 × 10 -2 4.54 × 10 -2 4.97 × 10 -2 1.03 × 10 -1 1.06 × 10 -1 1.249 1.224 1.245 1.398 1.413 mum makespans, however, are never more than 80% of the theoretical lower bound. This again corroborates the results in Section 5.2.

	q	Average #failures	0	Average makespan ratio R-List R-Shelf 1 Q B NB	0	R-List 1	Standard deviation Q	B	R-Shelf	NB	0	Maximum makespan ratio R-List R-Shelf 1 Q B NB
	0	0	1.067 1

Other parallel job models include moldable and malleable models, which allow the processor allocation of a job to vary at launch time or during execution[START_REF] Feitelson | Theory and practice in parallel job scheduling[END_REF]. Considering alternative job models will be part of our future work.

For practical schedulers, this is typically implemented using two separate job queues, one for reservation and one for backfilling.

Acknowledgement: The data from Mira logs was generated from resources of the Argonne Leadership Computing Facility, which is a DOE Office of Science User Facility supported under Contract DE-AC02-06CH11357.

Algorithm 2: R-Shelf

Input: a set J = {J1, J2, • • • , Jn} of rigid jobs, with processor allocation pj and error-free execution time tj for each job Jj ∈ J , a platform with P identical processors, parameter b; Output: a shelf schedule with starting times for all jobs in J till they complete successfully. begin Insert all jobs into a queue Q according to some priority rule; i ← 0, Si ← ∅; whenever all jobs in Si complete do if error detected for J k ∈ Si then Q.insert with priority(J k );

break ; // no backfilling end end execute all jobs in Si at the current time; end end necessarily the optimal makespan of a shelf-based schedule. Proposition 3. There exists a job instance and a failure scenario such that any shelf-based algorithm has an approximation ratio of Ω(ln P ).

Proof. Consider a set J = {J 1 , . . . , J P } of P uniprocessor jobs, where t j = P/j and p j = 1 for 1 ≤ j ≤ P . For the failure scenario f , we let f j = j -1 for 1 ≤ j ≤ P ; hence job J 1 does not fail, job J 2 fails once before success, and job J P fails f P = P -1 times before success.

We first consider the R-Shelf algorithm. Because the problem instance above has only P uniprocessor jobs, R-Shelf has no freedom at all: it schedules the first execution of all P jobs in the first shelf of height t 1 , then the second execution of jobs J 2 to J P in the second shelf of height t 2 , and so on until the last shelf of height t P , which includes only the P -th execution of job J P . Therefore, the makespan of R-Shelf is T S (f , s) = P + P 2 + • • • + 1 = P P j=1 1 j , while the optimal algorithm schedules the different executions of all jobs right after each other, thus having a makespan of T Opt (f , s * ) = P . The ratio T S (f ,s) T Opt (f ,s * ) tends to ln(P ) when P tends to infinity, hence it is not bounded.