Ana Gainaru

Brice Goglin

Valentin Honoré

Aupy Guillaume Pallez

Padma Raghavan

Yves Robert

Hongyang Sun

Reservation and Checkpointing Strategies for Stochastic Jobs

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

In this paper, we revisit our recent work on reservation strategies for stochastic jobs [START_REF] Aupy | Reservation Strategies for Stochastic Jobs[END_REF]. Stochastic jobs originate from Big Data or Machine Learning workloads, whose performance is widely dependent on characteristics of input data. Figure 1 shows an example of a Neuroscience job. Reservation strategies provide a sequence of fixed length reservations to execute a stochastic job. If the reservation is too short for the job, it is restarted in a longer reservation. We extend the approach to include the possibility of checkpointing at the end of some (well-chosen) reservations. The idea of checkpointing is very natural and widely used in practice, in particular for long jobs lasting several hours, but it dramatically complicates the design of scheduling strategies. To the best of our knowledge, existing approaches either checkpoint at the end of all reservations, or never. For large-scale applications, checkpointing to save intermediate results at the end of each reservation is the de facto standard approach. We use an example to help understand the challenges of the problem under study. Consider the jobs depicted in Figure 1. We model their execution time with D, a truncated LogNormal probability distribution on the domain [a, b] = [0, 80h] (mean µ = 21h, standard deviation σ = 20h). The exact execution time X of the next job to be scheduled is not known until that job has successfully completed, but instead is randomly and uniformly sampled from the target probability distribution D. We want to minimize the expected cost of scheduling this job. To do so, we have to derive a sequence of reservations. Then we compute the cost of the job given that sequence, and aim at minimizing the expected value. To determine the cost of a reservation, we use the generic model from our previous work [START_REF] Aupy | Reservation Strategies for Stochastic Jobs[END_REF]. This model has been shown to encompass a variety of scenarios, ranging from the Reserved Instances of Cloud Computing where one pays (for a cheaper cost) only the reserved time [START_REF]AWS pricing information[END_REF], to High-Performance Computing (HPC) platforms where one pays the total execution time (wait time and runtime).

Specifically, for a reservation of length W 1 and an actual execution duration of length X, the cost is expressed as:

αW 1 + β min(W 1 , X) + γ (1)
where α, β and γ are constant parameters that depend on the platform and the cost model. The first component αW 1 is proportional to the reservation length (pay for what you ask). The second component β min(W 1 , X) is proportional to the actual execution time (pay for what you use). Finally, the third and last component is a start-up time possibly associated with the first and/or second components.

To illustrate the contribution of this work, we use α = 1, β = γ = 0 in the example, and we divide execution costs by a factor 60 for simplicity, so that [a, b] = [0, 80] minutes. In Figure 2 , we depict three strategies, and their expected costs: (i) S 1 (Standard), which reserves the upper bound of D, W 1 = b = 80; (ii) S 2 (No Checkpoint), which introduces a first reservation of size W 1 = 20 before the second reservation W 2 = 80; (iii) S 3 (With Checkpoint), which introduces a first checkpointed reservation of size W 1 = 20 + 7 ( cover jobs shorter than 20, and 7 (red box) is the cost to checkpoint), then a second non-checkpointed reservation of size W 2 = 7 + 20 (7 (green box) is the cost to restart, 20 to cover jobs larger than 20 and smaller than 40), and a third reservation of size W 3 = 7 + 60 (7 is the cost to restart, 60 to cover jobs of size up to b). Here are the expected costs of these strategies: Note that S3 , the variant of S 3 where the second reservation is also checkpointed, would have a larger expected cost due to this second checkpoint: E( S3 ) = 27 × 0.66 + 61 × 0.26 + 128 × 0.08 = 43.92. Similarly one can verify that not performing the second reservation at all would have also increased the expected cost. This example shows that checkpointing does help for some scenarios but has too much overhead for others, and suggests that finding the best trade-off is difficult.

Indeed, in the general case, one has to decide which reservations should be checkpointed, depending on application profile and platform parameters. Moreover, determining the expected cost of a given reservation sequence together with scheduling decisions gets quite complicated. Section 2 gives a detailed formula for the expected cost, and Theorem 1 in Section 3.1 provides a simplified version. In our previous work without checkpoints [START_REF] Aupy | Reservation Strategies for Stochastic Jobs[END_REF], we have been able to analytically characterize the optimal sequence of reservations for any smooth probability distribution (except the length of the first reservation which had to be found numerically). The problem with checkpoints is dramatically more difficult, but we provide a holistic approach: we show how to compute the optimal solution for any discrete probability distribution, using a sophisticated dynamic programming algorithm. Then we show how to approximate the opti-mal solution for any continuous probability distribution with bounded support, by providing a reservation sequence (and its checkpointing decisions) whose expected cost is arbitrarily close to the optimal one. In practice, the restriction to bounded support is not a limitation. Given, say, a LogNormal or Weibull probability distribution defined on [a, ∞), it is very natural to truncate it on a bounded interval [a, b] where b corresponds to the quantile Q(1 -ε) for a small value of ε. This amount to discarding job execution times that are unreasonably too long, and never encountered in practice.

The main contributions of this work are the following:

• The characterization of an optimal reservation sequence, together with its checkpointing decisions, for any discrete probability distribution, using a sophisticated dynamic programming algorithm. • An approximation of the optimal solution for any continuous probability distribution with bounded support, by providing an algorithm to compute a reservation sequence (and its checkpointing decisions) whose expected cost is arbitrarily close to the optimal one. • An extensive set of simulation results as well as experiments on a multicore platform, using nine probability distributions and neuroscience application traces, showing the efficiency of our strategies in a HPC environment. The rest of the paper is organized as follows. Section 2 introduces the framework and main notations, and provides a detailed formula for the expected cost of a reservation sequence and its checkpointing decisions. Section 3 describes our key algorithmic contributions. Section 4 is devoted to experimental evaluation and comparison with existing approaches. Section 5 evaluates the actual performance of the approach for a neuroscience application on an HPC platform. Section 6 presents related work. Finally, we provide concluding remarks and hints for future work in Section 7.

Framework

In this section, we introduce some notations and formally define the optimization problem under study.

Stochastic jobs

We consider stochastic jobs whose execution times are unknown but (i) deterministic with respect to input data, so that two successive executions of the same job will have the same duration; and (ii) randomly and uniformly sampled from a given probability distribution law D, whose density function (PDF) is f and cumulative distribution function (CDF) is F . The probability distribution is assumed to be nonnegative, since we model execution times, and it is defined either on a finite support [a, b], where 0 ≤ a < b, or on an infinite support [a, ∞) where a ≥ 0. Hence, the execution time of a job is a random variable X, and P(X ≤ T ) = F (T ) = T a f (t)dt. For notational convenience, we sometimes extend the domain of f outside the support of D by letting f (t) = 0 for Elapsed Time

T1 = t1 C W1 R T2 = t2 -t1 W2 R T3 = t3 -t1 C W3 R T4 = t4 -t3 W4
t ∈ [0, a] ∪ [b, ∞).
In addition, we assume that we can interrupt the jobs at any time (divisible load application) to take a checkpoint: this will save the current progress of the execution, and enable to restart from that point on. Divisible load applications can be found, for example, in biological computations, image and video processing [START_REF] Ismail | Implementation and performance evaluation of a scheduling algorithm for divisible load parallel applications in a cloud computing environment[END_REF]. We assume that the cost of checkpoint and of recovery is constant throughout the execution: let C be the cost to checkpoint the data at the end of an execution, and R the cost to read the data to restart a computation.

Cost model

We use the cost model motivated in our previous work [START_REF] Aupy | Reservation Strategies for Stochastic Jobs[END_REF]. For a reservation of length W and an actual execution duration w for the job, the cost is αW + β min(W, w) + γ, where α > 0, β ≥ 0 and γ ≥ 0. If the job does not complete within W seconds, then another reservation should be paid for.

However, we take checkpoints into account in this work. If the job did not complete its execution during the last reservation, but was checkpointed during the last C seconds of that reservation, then in the current reservation, the job can restart from that checkpoint during the first R seconds, and then continue execution from its saved state. On the contrary, if no checkpoint was taken during the last reservation, the work done during that reservation is lost, and the execution must restart from the last checkpoint (or from the very beginning if no checkpoint was taken yet).

Altogether, the user needs to schedule a (possibly infinite) sequence of reservations W = (W 1 , W 2 , . . . , W i , W i+1 , . . . ) to execute any job whose execution time follows the distribution D, and to launch these reservations one after the other, until the job successfully terminates within the duration of some reservation. In addition, the user should decide whether to take a checkpoint or not at the end of each reservation.

Definition 1 (Reservation sequence for D). Given a probability distribution D, a reservation sequence S = {(W 1 , δ 1 ), (W 2 , δ 2 ), . . . }, is defined as a sequence of reservation lengths W k and a sequence of checkpointing decisions δ k ∈ {0, 1}: δ k = 1 means the k th reservation ends with a checkpoint, and δ k = 0 means it does not.

Then, the k th reservation can be decomposed into:

W k = R k + T k + C k (2)
Size of job where R k is the time spent for restart, T k for actual job execution, and C k for checkpoint. We have C k = δ k C by definition. There is a restart if and only if there has been a checkpoint at some point before, hence

0 t 1 t 2 t 3 t 4 T 1 T 2 T 3 T 4
R k = (1 - k-1 i=1 (1 - δ i ))R (assuming R 1 =
0 for the first reservation). But it is hard to keep track of actual job progress when using only the (W k , δ k ) values. Consider for instance the following sequence S = {(W 1 , 1), (W 2 , 0), (W 3 , 1), (W 4 , 0)}, which is depicted in Figure 3. If the actual job duration is X = t, during which reservation will the job complete its execution? We introduce another view of the reservation sequence S by introducing the milestones {t k } as shown in Figure 4. A milestone t k represents the amount of work that has been actually executed at the end of the k th reservation. Then, the last reservation for the job of length t is W k , where t k-1 ≤ t ≤ t k . Of course, we need that t ≤ t 4 for all values of D (equivalently, the upper bound of the support of D is b ≤ t 4 ) for all jobs to complete successfully with the four reservations of S.

The relationship between the milestone t k (actual work progress) and the value of T k (time spent computing during reservation

W k ; see Equation (2)) is t k = T k + k-1
i=1 δ i T i : Indeed, the work actually progresses only from the last checkpoint, while the work executed during the previous non-checkpointed reservations is lost whenever these non-checkpointed reservations do not allow for the full completion of the job. Another way to express the relationship between t k and T k is the following:

t k = T k + max{t i | 1 ≤ i ≤ k -1 and δ i = 1} (3)
Equation ( 3) gives a recursive way to compute t k from its definition. We recapitulate the relations between all notations introduced in Figures 3 and4:

W k = R k + T k + C k ; R k = (1 -Π i<k (1 -δ i ))R; T k = t k -i<k δ i T i ; C k = δ k C. (4)
In the following, we use milestones t k rather than reservation lengths W k to characterize a reservation sequence, and we write S = {(t 1 , δ 1 ), (t 2 , δ 2 ), . . . } instead of S = {(W 1 , δ 1 ), (W 2 , δ 2 ), . . . }, because it is easier to use milestones when computing the expected cost of a sequence, as shown below. For notational convenience, we define t 0 = 0 as the first milestone of each sequence S. Note also that we can restrict to sequences where t k-1 < t k , because otherwise (if t k-1 = t k ), the execution does not progress during the k th reservation.

Expected cost

Given a reservation sequence S = ((t i , δ i )) i and a job with execution time t such that t k-1 < t ≤ t k , the cost of the sequence for that job is given by:

C S (k, t) = k-1 i=1 (αW i + βW i + γ) + αW k + β(R k + t -(t k -T k )) + γ (5)
where the first part is the total cost from the k -1 first reservations that did not allow the job to complete, and the second part is the cost of the k th reservation. The actual execution time during the k th reservation is t -(t k -T k ), because t k -T k is the amount of work done up to the beginning of that reservation; we add the restart time (R k ) but do not need to checkpoint (if δ k = 1) because the job successfully completes before it is taken.

We let k(t) = k for a job of length t such that t k-1 < t ≤ t k . Now, given a random variable X following a distribution D, the expected cost of the reservation sequence S is

E(S(X)) = ∞ 0 C S (k(t), t)f (t)dt = ∞ k=1 t k t k-1 C S (k, t)f (t)dt (6)

Optimization problem

We are now ready to state the optimization problem:

Definition 2 (Stochastic). Given a random variable X (with PDF f and CDF F ) for the execution times of a stochastic job, and a cost function in Equation ( 5) (with parameters α > 0 and β, γ ≥ 0), find a reservation strategy S with minimal expected cost E(S(X)) as given in Equation ( 6).

We further define ReservationOnly to be the instance of Stochastic where the cost is a linear function of the reservation length only, i.e., when β = γ = 0. For ReservationOnly, we can further consider α = 1 without loss of generality. For instance, such costs are incurred when making reservations of resources to schedule jobs on some cloud platforms, with hourly or daily rates. Throughout the paper, we focus on the usual probability distributions, hence we assume that the density function f and the CDF F of D are smooth (infinitely differentiable), and that D has finite expectation.

Algorithms

In this section, we establish some key properties of an optimal solution in the general setting.

Expected cost

We start by establishing a simpler expression for the expected cost function of Stochastic in the following theorem. The proof is omitted due to space constraint but can be found in the companion report [START_REF] Gainaru | Reservation and Checkpointing Strategies for Stochastic Jobs (Extended Version)[END_REF].

Theorem 1. Given a random variable (RV) X and a reservation sequence S = ((t 1 , δ 1 ), (t 2 , δ 2 ), . . . ), the expected cost E(S(X)) of a strategy S given by Equation ( 6), with parameters α, β and γ, can be rewritten as

E(S(X)) = β • E[X]+α t1 + δ1C + γ + ∞ i=2 αWi +β Ri +(1-δi-1)Ti-1 +Ci-1 + γ • P(X > ti-1) (7)
For ease of reading, when there is no ambiguity on the RV X, we write E(S(X)) = E(S).

Dynamic programming for discrete distributions

We study the problem for a finite discrete distribution:

Y ∼ (v i , f i ) 1≤i≤n , where v i < v i+1 for all 1 ≤ i ≤ n -1 and f i = P(Y = v i ). We assume that f n = 0 and n i=1 f i = 1. Consider a strategy S = {(t 1 , δ 1 ), (t 2 , δ 2 ), . . . , (t |S| , δ |S| )}, where t i = v π(i) and t i < t i+1 for all 1 ≤ i ≤ |S| -1.
Also, the last reservation is necessarily t |S| = v n to ensure that the expected cost of the strategy is finite. By convention, we let t 0 = v 0 = a, hence P (Y > t 0 ) = 1. Note that we can safely restrict to strategies where each milestone t i is equal to some threshold v j of the discrete distribution: otherwise, replacing t i by the largest v j such that v j ≤ t i leads to a smaller cost.

Rewriting Equation ( 7) with W i = R i + T i + C i , and since W 0 = 0, the expected cost of strategy S can be expressed as:

E(S) = β • E[Y ] + |S| i=1 α (Ri + Ti + Ci) + βRi + γ • P(Y > ti-1) + |S|-1 i=1 β (1 -δi)Ti + Ci • P(Y > ti) (8)
Based on Equation (8), and using Equations ( 4), we construct a dynamic programming algorithm to compute the optimal reservation sequence:

Theorem 2. For a discrete distribution Y ∼ (v i , f i ) 1≤i≤n
, the optimal expected cost is returned by E ckpt (0, 0), where, for

0 ≤ i c ≤ i l ≤ n, E ckpt (i c , i l ) is: =β • E[Y ], if i l = n = min i l +1≤j≤n, ∆ j ∈{0,1} E ckpt ∆jj, j + α vj + ∆jC +γ • n k=i l +1 f k +β (1-∆j)vj +∆jC • n k=j+1 f k , if ic = 0 = min i l +1≤j≤n, ∆ j ∈{0,1} E ckpt (1 -∆j)ic + ∆jj, j + α R+(vj -vi c )+∆jC +βR+γ • n k=i l +1 f k +β (1-∆j)(vj -vi c )+∆jC • n k=j+1 f k , otherwise
The optimal solution can be computed in O(n 3 ) time.

Intuitively, i c denotes the index of the last checkpointed value, while i l denotes the index of the last value that was tried before we try the next one with index j. Here, ∆ j indicates whether the value v j will be checkpointed or not. The optimality is proven by induction on the index of the last checkpointed reservation. The proof is again omitted but available in the companion report [START_REF] Gainaru | Reservation and Checkpointing Strategies for Stochastic Jobs (Extended Version)[END_REF].

Approximation algorithm for continuous distributions

In this section, we provide an approximation algorithm of the optimal strategy for continuous distributions with bounded support [a, b], where a ≥ 0 and b is finite. Because we model job execution times, it is natural to truncate continuous distributions whose support is [0, ∞[ such as an Exponential or LogNormal distribution, say, to a bounded support [a, b].

The result for continuous distribution is particularly important: we have shown in recent work [START_REF] Gainaru | Making speculative scheduling robust to incomplete data[END_REF] that continuous distributions gave strategies that allowed using small data samples to find an efficient strategy. Here, it returns an arbitrarily good quality solution with low complexity.

More precisely, let X be a continuous random variable defined on [a, b] modeling the probability distribution D, where 0 ≤ a < b, with CDF F and PDF f . Theorem 3 shows that Algorithm 1 computes a close-to-optimal strategy for Stochastic. Before stating Theorem 3, we start with a lemma: Lemma 1. Given a random variable X and a strategy S = {(t 1 , δ 1 ), . . . ,

(t |S| , δ |S| )}, if there exists an index i 0 > 1 such that t 1 < • • • < t i0-1 ≤ min(R, εE[X]) < t i0 < • • • < t |S| , then the strategy S = {(min(R, εE[X]), 0), (t i0 , δ i0 ), . . . , (t |S| , δ |S| )} satisfies: E( S(X)) ≤ (1 + ε) • E(S(X))
Algorithm 1 Dyn-Prog-Count(X, ε)

1: Let [a, b] be the domain of X, with 0 ≤ a < b 2: c 0 = 3(b -a) min 1 min(max(a,εE[X]/3),R,C) , α+β γ 3: n ← c 0 /ε 4: Define the discrete distribution Yn ∼ (v i , f i ) i=1...n s.t. v i = a + i • b-a n for 0 ≤ i ≤ n f i = P(Yn = v i ) = P(v i-1 < X ≤ v i ) for 1 ≤ i ≤ n (9)
5: S dp n ← Optimal strategy for Yn (Theorem 2) 6: return S dp n Intuitively, this lemma states that restricting to strategies whose first reservation length is at least min(R, εE[X]), increases the cost by at most a factor of 1 + ε.

Proof. Consider a strategy S = {(t 1 , δ 1 ), . . . , (t |S| , δ |S| )} for a random variable X, such that there exists an index i 0 > 1 with

t 1 < • • • < t i0-1 ≤ min(R, εE[X]) < t i0 < • • • < t |S| . Let ã = min(R, εE[X]), and define strategy S = {(ã, 0), (t i0 , δ i0 ), . . . , (t |S| , δ |S| )}. From Equation (7), we have E(S(X)) ≥ βE[X] + α(t1 + C1) + γ+ (αWi 0 + β Ri 0 + (1 -δi 0 -1)Ti 0 -1 + Ci 0 -1 + γ • P(X > ti 0 -1) + |S| i=i 0 +1 αWi + β Ri + (1 -δi-1)Ti-1 + Ci-1 + γ • P(X > ti-1), while E( S(X)) = βE[X] + (αã + γ) + (α Wi 0 + βã + γ) • P(X > ã) + |S| i=i 0 +1 α Wi + β Ri + (1 -δi-1) Ti-1 + Ci-1 + γ • P(X > ti-1).
We obviously have C i = Ci , ∀i ≥ i 0 . We now show that ∀i ≥ i 0 , W i ≥ Wi . We consider two cases: (i) the last checkpoint before t i was done during t j with j ≥ i 0 or there was no checkpoint before t i . In this case, W i = Wi ; (ii) the last checkpoint before t i was done during t j with j < i 0 in S, and there was no checkpoint done in S before t i . In this case, we have

W i = R + (t i -t j ) + δ i C and Wi = t i + δ i C. Since t j ≤ t i0-1 ≤ R, we get W i ≥ Wi . Similarly, we can show that, ∀i ≥ i 0 , R i ≥ Ri . Further, since P(X > ã) ≤ P(X > t i0-1 ) ≤ 1, we have E( S(X)) -E(S(X)) ≤ α(ã -t 1 -C 1 ) + β(ã -R i0 -(1 -δ i0-1 )T i0-1 -C i0-1 ) • P(X > t i0-1 ) ≤ (α + β)ã ≤ ε(α + β)E[X].
Finally, E(S(X)) ≥ (α+β)E[X]+γ, because this is the cost of an omniscient strategy that makes a single reservation of exactly the right size for each job. Therefore, we obtain E( S(X)) -E(S(X)) ≤ ε • E(S(X)).

Theorem 3. Given a continuous random variable X on the domain [a, b], where 0 ≤ a < b, and given a constant ε > 0, Dyn-Prog-Count(X, ε) is a 1 + εapproximation algorithm for Stochastic and executes in time O 1 ε 3 . Proof. Given a continuous random variable X of support [a, b], we define the discrete random variable Y n ∼ (v i , f i ) i=1...n as stated in Equation ( 9) of Algo-rithm 1: Let S opt = {( to i , δo i )} 1≤i≤|S opt | denote the optimal solution for X, and let S dp n the optimal solution for Y n returned by Theorem 2. We want to show that E(S dp n (X)) ≤ (1 + ε) • E(S opt (X)). In order to do so, we construct two intermediate strategies S opt ε/3 and S algo as follows. First, S opt ε/3 = ((

t o i , δ o i )) i is constructed in such a way that if to 1 ≥ min(R, εE[X]
3 ), then S opt ε/3 = S opt , otherwise we construct S opt ε/3 from S opt by Lemma 1 below, with the value ε 3 . Then, according to Lemma 1, we have:

E(S opt ε/3 (X)) ≤ 1 + ε 3 • E(S opt (X)) (10)
Second,

S algo = ((t a i , δ a i )) 1≤i≤|S opt ε/3 | (hence |S algo | = |S opt ε/3 |), is such that for 1 ≤ i ≤ |S opt ε/3 |, we let (t a i , δ a i ) = (v π o (i) , δ o i ).
Here, we use the sequence (v i ) i=0...n from Equation ( 9), and the function π o defined by

v π o (i)-1 < t o i ≤ v π o (i) .
In other words, for each reservation, S algo chooses the first discrete value larger than or equal to the corresponding one chosen by S opt ε/3 , and makes the same checkpointing decision.

Lemma 2. E(S algo (X)) ≤ (1 + ε 3 ) • E(S opt ε/3 (X)).
Proof. We use the notations

T o i , R o i , C o i , W o i
for the parameters of S opt ε/3 , and

T a i , R a i , C a i , W a i
for the parameters of S algo . From Equation ( 4), we see that, for

1 ≤ i ≤ |S opt ε/3 |, we have δ o i = δ a i ; R o i = R a i ; C o i = C a i ; and W a i -W o i = T a i -T o i . In addition, if σ o (i) (resp. σ a (i))
is the index of the last checkpoint before t o i (resp. t a i ), then σ o (i) = σ a (i), and,

|T a i -T o i | = t a i -t a σ a (i) -t o i -t o σ o (i) = v π o (i) -v π o (σ o (i)) -t o i -t o σ o (i) = v π o (i) -t o i -v π(σ o (i)) -t o σ o (i) ≤ max v π o (i) -t o i , v π o (σ o (i)) -t o σ o (i) ≤ b -a n
From Equation ( 7) we have:

E(S opt ε/3 (X)) = βE[X]+ |S opt ε/3 | i=1 αW o i +β R o i +(1- δ o i-1 )T o i-1 +C o i-1 +γ •P X > t o i-1 while E(S algo (X)) = βE[X]+ |S opt ε/3 | i=1 αW a i + β R a i + (1 -δ a i-1 )T a i-1 + C a i-1 + γ • P X > t a i-1 . We first observe that P X > t a i-1 ≤ P X > t o i-1 because t a i-1 ≥ t o i-1 . We can derive that E(S algo (X)) -E(S opt ε/3 (X)) ≤ |S opt ε/3 | i=1 α|T a i -T o i | + β(1 - δ o i-1 )|T a i-1 -T o i-1 | • P X > t o i-1 ≤ α b-a n + |S opt ε/3 |-1 i=1 α + β(1 -δ o i ) b-a n • P(X > t o i ) ≤ b-a n α + (α + β) |S opt ε/3 |-1 i=1 P(X > t o i ) .
We also observe that:

E(S opt ε/3 (X)) ≥ γ + |S opt ε/3 |-1 i=1 γ • P(X > t o i ) . Furthermore, for 1 ≤ i ≤ |S opt ε/3 |, we have W o i ≥ R o i + T o i ≥ min(R, ã)
, where ã = max(a, min(R, εE[X]/3)). This is because either T o i ≥ ã according to Lemma 1 (when there was no checkpoint before t o i ), or R o i = R (when there was a checkpoint before t o i ). Therefore:

E(S opt ε/3 (X)) ≥ min(max(a, εE[X]/3), R, C) α + (α + β) |S opt ε/3 |-1 i=1 P(X > t o i ) . One can observe that: min(R, max(a, min(R, ε E[X] 3 ))) = min(max(a, ε E[X] 3 ), R).
Using c 0 (line 2, Algorithm 1), we obtain:

E(S algo (X)) -E(S opt ε/3 (X)) ≤ c0 n • E(S opt ε/3 (X)) ≤ ε 3 • E(S opt ε/3 (X)).
Lemma 3. E(S dp n (X)) ≤ E(S algo (X)) Proof. Given any reservation strategy S = {(t i , δ i )} 1≤i≤|S| such that ∀i, t i ∈ {v 1 , . . . , v n }, we show that:

E(S(Y n )) -E(S(X)) = β (E[Y n ] -E[X])
Indeed, for the two distributions Y n and X, the only differences in the cost function are: (i) the expectations E[Y n ] and E[X]; and (ii) the probability values P(Y n > t i ) and P(X > t i ) , ∀i. But if t i ∈ {v 1 , . . . , v n }, we have:

P(Y n > t i ) = P(Y n > v k ) = P Y n ∈ ∪ n j=k+1 {v j } = n j=k+1 P(Y n = v j ) = n j=k+1 P(X ∈]v j-1 , v j ]) = P(X ∈]v k , v n ]) = P(X > v k ) = P(X > t i )
We obtain that:

E(S(Y n )) -E(S(X)) = β (E[Y n ] -E[X])
We apply this result to both S dp n and S algo and derive that:

E(S dp n (Y n )) -E(S dp n (X)) = E(S algo (Y n )) -E(S algo (X)) or equivalently, E(S dp n (Y n )) -E(S algo (Y n )) = E(S dp n (X)) -E(S algo (X)) S dp n is optimal for Y n , hence E(S dp n (Y n )) -E(S algo (Y n )) ≤ 0.
And finally, the result E(S dp n (X)) -E(S algo (X)) ≤ 0.

Combining Lemma 2, Lemma 3 and Equation ( 10), we get:

E(S dp n (X)) ≤ E(S algo (X)) ≤ 1 + ε 3 • E(S opt ε/3 (X)) ≤ 1 + ε 3 1 + ε 3 • E(S opt (X)) ≤ (1 + ε) • E(S opt (X))
which concludes the proof of Theorem 3.

Extensions

All the results presented in Sections 3.1 to 3.3, namely the cost model (Theorem 1), the optimal algorithm for discrete distributions (Theorem 2), and the approximation algorithm for continuous distributions with bounded support (Theorem 3), can be extended to some variants of the problem where the checkpoint strategy is determined a priori. Indeed, there are two important and natural variants to consider: strategies where no reservation is checkpointed, and strategies where all reservations are checkpointed. The former variant (called No-Ckpt) was studied in our previous work [START_REF] Aupy | Reservation Strategies for Stochastic Jobs[END_REF], where we derived an optimal algorithm for discrete distributions with reduced time complexity O(n 2 ) instead of O(n 3 ) as in Theorem 2. The latter variant (called All-Ckpt) also admits an optimal dynamic programming algorithm of reduced time complexity O(n 2 ) that can be found in the companion report [START_REF] Gainaru | Reservation and Checkpointing Strategies for Stochastic Jobs (Extended Version)[END_REF].

Performance evaluation

In this section, we evaluate the performance of the different algorithms in simulation. In the following, performance stands for the expected cost of each algorithm under various job execution time distributions, C/R overheads and cost functions. We use jobs that follow a wide range of usual probability distributions as well as a distribution obtained from traces of a real neuroscience application. The code for this section is publicly available on https: //gitlab.inria.fr/vhonore/ckpt-for-stochastic-scheduling.

Evaluated algorithms

In addition to the algorithms presented in Section 3, we propose a periodic heuristic for the case of bounded distributions. This strategy, described in Algorithm 2, is a natural policy, where successive reservations differ in length by a constant amount of time T , called the period. A checkpoint is performed at the end of each period. Hence, the value of W i associated with each t i is constant in this strategy. The algorithm specifies the number of chunks τ in the domain [a, b] of the bounded distribution, thus the period can be computed as Algorithm 2 All-Ckpt-Per(X, τ )

1: Let [a, b] be the domain of X, and let T = b-a τ 2: (t i , δ i ) = (a + i • T, 1) for i = 1, 2, . . . , τ -1 (b, 0) for i = τ 3: return S period τ ← ((t i , δ i )) 1≤i≤τ
Table 1: Probability distributions and parameter instantiations.

Distribution PDF f (t) Instantiation Support (in hours) Distributions with infinite support Exponential (λ) λe -λt λ = 1.0h -1 t ∈ [0, ∞) Weibull(λ, κ) κ λ t λ κ-1 e -( t λ ) κ λ = 1.0h κ = 0.5 t ∈ [0, ∞) Gamma(α, β) β α Γ(α) t α-1 e -βt α = 2.0 β = 2.0h -1 t ∈ [0, ∞)
LogNormal (ν, κ)

1 tκ √ 2π e -(ln t-ν) 2 2κ 2 ν = 3.0h κ = 0.5 t ∈ (0, ∞) Pareto(ν, α) αν α t α+1 ν = 1.5h α = 3.0 t ∈ [ν, ∞)
Distributions with finite support Truncated Normal(ν, κ 2 , a, b)

1 κ 2 π • e -1 2 ( t-ν κ ) 2 1-erf a-ν κ √ 2 ν = 8.0h κ 2 = 2.0h 2 a = 1.0h b = 20.0h t ∈ [a, b] Uniform(a, b) 1 b-a a = 1.0h b = 20.0h t ∈ [a, b]
Beta(α, β)

t α-1 •(1-t) β-1 B(α,β) α = 2.0 β = 2.0 t ∈ [0, 1]
Bounded Pareto(L, H, α)

αL α t -α-1 1-L H α L = 1.0h H = 20.0h α = 2.1 t ∈ [L, H] T = b-a τ .
Note that for this policy, one can derive optimal strategies for some distributions (such as uniform distributions [START_REF] Gainaru | Reservation and Checkpointing Strategies for Stochastic Jobs (Extended Version)[END_REF]).

Overall, we evaluate five different algorithms from the following two sets of strategies:

• Dyn-Prog-Count: This set includes Algorithm 1, and its All-Ckpt and No-Ckpt variants described in Section 3.4.

• All-Ckpt-Per: This set includes Algorithm 2, and its No-Ckpt-Per counterpart where checkpointing is not allowed (i.e., δ i = 0, ∀i).

Evaluation methodology

We evaluate the performance using two scenarios, both based on the Reserved Instance pricing scheme in AWS [START_REF]AWS pricing information[END_REF], where the user pays exactly what is requested. In the evaluation, we set α = 1, β = γ = 0: • Scenario 1 (Section 4.3): We consider nine usual probability distributions, five of which have infinite support (Exponential, Weibull, Gamma, LogNormal, Pareto) and four have finite support (Truncated Normal, Uniform, Beta, Bounded Pareto). Table 1 lists all distributions used in simulation with the instantiations of their parameters for evaluation. The first five distributions are truncated and fed as input to Algorithm 1. To do so, we set the upper bound of the infinite support to b = Q(1 -υ), where Q(x) = inf{t|F (t) ≥ x} is the quantile function and υ is a small constant. In our simulation, we set υ = 10 -7 . During the discretization procedure in Algorithm 1, we then normalize the probabilities of all discrete values so that they sum to 1. We set C = R = 360 seconds (0.1 hour). This checkpointing cost is extracted from [START_REF] Hussain | Partial redundancy in hpc systems with non-uniform node reliabilities[END_REF] and corresponds to an average checkpointing duration, where an optimistic one is 60 seconds and a pessimistic one is 600 seconds. We further discuss the impact of the checkpointing cost on the performance.

• Scenario 2 (Section 4.4): In this scenario, we consider execution traces of a real neuroscience application, and fit a LogNormal distribution to its execution times. To further evaluate the robustness of the algorithms, we perturb the parameters of the fitted distribution by varying its mean and standard deviation, and show the impact on the performance.

Additional simulations with different cost models where β = 0 are available in [START_REF] Gainaru | Reservation and Checkpointing Strategies for Stochastic Jobs (Extended Version)[END_REF], with similar trends as the results presented below.

Results for Scenario 1

We first evaluate the performance of Dyn-Prog-Count compared to the other strategies, as a function of the values of R and C. Figure 5a presents the performance of these strategies normalized to that of Dyn-Prog-Count (black line for y = 1.0) for the Exponential distribution (Figure 5a) and Bounded Pareto distribution (Figure 5b). The results are similar for other distributions [START_REF] Gainaru | Reservation and Checkpointing Strategies for Stochastic Jobs (Extended Version)[END_REF]. We use ε = 0.1 for Dyn-Prog-Count and its variants. Regarding periodic strategies, we choose the best value for the number of chunks τ in [START_REF] Afanasyev | Service provider competition: Delay cost structure, segmentation, and cost advantage[END_REF]1000]. Not surprisingly, we can observe that when C and R are small, the best result is to use the All-Ckpt strategy while when they are large, one should use the No-Ckpt strategy. There exist thresholds on the sizes of C and R where Dyn-Prog-Count uses a mix of checkpointed and not checkpointed reservations. In that case, the gain of using Dyn-Prog-Count can be up to 10% compared with its variants. An interesting future research direction is to find properties on those thresholds as a function of the probability distribution. Finally, one should observe that the gain achieved with Dyn-Prog-Count compared to the best periodic solution is in general even larger than 10%. The exception is for the Exponential distribution, where one can show [START_REF] Gainaru | Reservation and Checkpointing Strategies for Stochastic Jobs (Extended Version)[END_REF] that All-Ckpt and its periodic counterpart are identical. This is due to the memoryless property of the Exponential distribution.

We then study the impact of ε on the performance of Dyn-Prog-Count (DPC) when R = C = 360s. The idea is that when ε = 1, this theoretically guarantees that the performance is at most twice (= 1 + ε) that of the optimal, but in practice it can be a lot better. In Figure 6, we study the performance of Dyn-Prog-Count for various values of ε for distributions of Table 1. All performance are normalized by Dyn-Prog-Count for ε = 0.1. We see that in practice, the convergence to the lower bound in performance is fast. Indeed, for ε = 1, almost all distributions already reach convergence, except for Weibull and Pareto (which have a much larger domain of definition and specific properties1 ). For those distributions, we see that they converged for ε = 0.1. For this experiment, the number of chunks n in Dyn-Prog-Count varies between 50 to 1000 depending on the distribution and value of ε, showing the practicality of Dyn-Prog-Count for the target distributions.

Our final evaluation for this scenario is a study of the impact of the period size. So far, we have always chosen the period minimizing the objective functions. Table 2 shows the performance of both variants of the periodic algorithms, All-Ckpt-Per and No-Ckpt-Per, normalized by that of Dyn-Prog-Count (ε = 0.1), when C = R = 360s. For each distribution, the second column shows the best period found when τ varies from 1 to 1000 (with its associated cost normalized by that of Dyn-Prog-Count), and the other columns present results for specific values of τ in that interval. As observed before, All-Ckpt-Per is in general not able to match Dyn-Prog-Count (except for some distributions). In addition, we see that No-Ckpt-Per performs even worse than All-Ckpt-Per. The reason is that the checkpointing cost is relatively low in this setup, so it is preferable to checkpoint more often than never. Finally another observation is that a wrong period size can significantly deteriorate the performance of the periodic algorithms.

Results for Scenario 2

We now present the simulation results for a probability distribution fitted to the execution times from the traces of a real neuroscience application (a code for structural identification of orbital anatomy) extracted from the Vanderbilt's medical imaging database [START_REF] Harrigan | Vanderbilt university institute of imaging science center for computational imaging XNAT: A multimodal data archive and processing environment[END_REF]. Figure 1 shows the execution traces of the application and its fitted LogNormal distribution. Figure 7 presents the performance of different algorithms for this fitted distribution. To evaluate the robustness of algorithms, we also vary the original mean µ o (Figure 7a) or standard deviation σ o (Figure 7b) of the distribution from their original values. For readability, all axis are in logscale. We fix the checkpointing cost to C = R = 600 seconds and ε = 1.0. For periodic strategies, we use similar brute-force procedure as Scenario 1 to find the period that performs best. The expected costs of the algorithms are normalized by that of an omniscient scheduler (blue dashed line), which knows the execution time t of a job a priori, and thus would pay the minimum possible cost by making a single reservation of length t 1 = t. We observe that Dyn-Prog-Count always gives the best performance. As previously seen, the checkpointing cost influences the performance of No-Ckpt and All-Ckpt with regard to Dyn-Prog-Count. In this setup, since C = R = 600 seconds is a value low enough to allow for checkpointing all reservations, the performance of Dyn-Prog-Count and All-Ckpt are the same and outperforms No-Ckpt by a wide margin. Simulation with other C/R values can be found in [START_REF] Gainaru | Reservation and Checkpointing Strategies for Stochastic Jobs (Extended Version)[END_REF] and show similar trends. As for the periodic algorithms, All-Ckpt-Per has better performance than No-Ckpt-Per. However, both algorithms have worse per- formance than Dyn-Prog-Count. The results demonstrate the robustness of Dyn-Prog-Count for a practical application with different distribution parameters.

Finally, when the ratio µ/σ is large (either by increasing the mean (µ/µ o large), or decreasing the standard deviation (σ/σ 0 small)), the solutions converge to the omniscient scheduler. This could be expected, since in this case the variability becomes negligible and the job behaves similarly to a deterministic job.

Experiments

In this section, we conduct real experiments on an HPC platform by using three stochastic neuroscience applications. The focus is to study the performance of different reservation and checkpointing strategies when scheduling multiple jobs in a shared HPC execution environment.

Experimental setup

The chosen neuroscience applications are described in Table 3 along with their execution characteristics, which are extracted from the Vanderbilt's medical imaging database [START_REF] Harrigan | Vanderbilt university institute of imaging science center for computational imaging XNAT: A multimodal data archive and processing environment[END_REF]. In particular, the walltime distributions are obtained by fitting traces of execution times, while the checkpointing/restart costs are obtained by analyzing and averaging memory footprints. Note that, for these applications, restart costs (R) differ from checkpointing costs (C) and depend upon the time-steps at which they are taken. We focus on the evaluation of the following two different sets of strategies:

• An HPC-for-neuroscience strategy (called HPC in Section 5.2), which uses the average of the last 5 runs as the initial reservation length and then increases it by 50% for each subsequent reservation. This strategy is currently used by the MASI group [START_REF] Landman | Medical-image Analysis and Statistical Interpretation (MASI) Lab[END_REF] at Vanderbilt to handle stochastic neuroscience applications.

• Our proposed Dyn-Prog-Count strategy and its All-Ckpt variant.

We ran the experiments on a 256-thread Intel Processor (Xeon Phi 7230, 1.30GHz) while submitting jobs through the Slurm scheduler. All three neuroscience applications are sequential (i.e., use a single hardware thread) and perform some medical imaging analysis. The variation in execution time is due to the different characteristics of the input data. However, as we do not have access to the raw input images, we used the information in the logs to simulate the characteristics of the input data, thereby forcing a job to run for a certain walltime and saving a specific amount of data for the checkpoints. The platform under study obeys the ReservationOnly cost model, with α = 1, β = γ = 0. In each experiment, we submitted 500 total jobs, and recorded the completion time of each of them. We use the average job stretch (defined as the ratio between the total execution time of a job and its actual walltime) to show the individual job performance, and use the utilization (defined as the ratio between the sum of all job walltimes and the total time required to execute them) to show the performance of the system for the whole job set. By experimenting on a real system, we investigate the robustness of our strategy: 1) when multiple applications of the same type are running concurrently (and read/write times vary due to congestion while accessing I/O and/or due to application interference); 2) when the C/R costs vary depending upon which time-steps get a checkpoint/restart (i.e., different values for different reservations); and 3) when running multiple job types concurrently.

Experimental results

Figure 8 shows the performance of the three strategies when submitting 500 jobs from each application to the Slurm scheduler. In this experiment, we manually force the C/R costs to be the same (as in Table 3) for each strategy, in order to study the impact of application interference and runtime system's performance variability on our model. The findings consistent with the simulation results (in Section 4), showing that Dyn-Prog-Count performs better than its All-Ckpt variant in terms of both system utilization and average job stretch using all three applications. Moreover, both algorithms outperform the simple HPC strategy.

Depending on when the checkpoint is being taken, the checkpoint size and thus the time to save and restore the application can vary. Figure 9 shows the results when the C/R costs could vary for different reservations. Based on the log traces of these three applications, we noticed that their memory footprints can vary by as much as 30% depending on when the checkpoint is taken (e.g., the checkpoint time can vary between 80 and 110 seconds for Qball).

Our experiment generates random checkpoint sizes using a uniform distribution with the mean given by the average checkpoint size from the traces, and forces the application to read/write the corresponding amount at the beginning/end of the execution. In this experiment, we assume that the checkpointing time is included in the request time and is never responsible for applications exceeding their allocated time. While the Dyn-Prog-Count solution is computed using the average C/R costs presented in Table 3, the experimental results show that its performance is robust up to 15-20% variability in the C/R costs. Moreover, the average job stretch appears to be even more stable than the utilization, suggesting that most of the submitted jobs are not impacted by the fluctuation in the C/R costs.

If application-level checkpoint is used, the application is usually aware of the checkpoint size, thus the checkpointing process can start before the reservation is over. The subsequent submissions can easily adapt to this deviation with the first checkpoints that are smaller than the one used to compute the sequence (this is the case for Figure 9). For system-level checkpoint, the application footprint usually remains similar throughout the execution of the application. In case the checkpointing time is causing the application to exceed the reserved time, the submission will fail and subsequent submissions can take this into account by adding the wasted time. The limitation of our method is visible for applications with large variability in checkpointing size, which can be due to multiple factors, either within the application that presents different memory footprints throughout its execution, or by system-level causes, such as I/O congestion or failures. Such large variability in checkpointing size compared to what is used to compute the reservation sequence can result in worse performance when using our method, and the classic HPC model would be preferred in this case. We are currently investigating methods to incorporate variation of checkpointing size into the computation of the optimal reservation sequence, by either using historic information or adapting the subsequent request times based on the sizes of previous checkpoints. We plan to further analyze variable C/R times in the future.

Reservation-based scheduling Batch schedulers are widely adopted by many resource managers in HPC systems, such as Slurm, Torque and Moab. Most batch schedulers use resource reservation in combination with backfilling [START_REF] Lifka | The ANL/IBM SP Scheduling System[END_REF][START_REF] Mu | Utilization, Predictability, Workloads, and User Runtime Estimates in Scheduling the IBM SP2 with Backfilling[END_REF][START_REF] Skovira | The EASY -LoadLeveler API Project[END_REF], and rely on users to provide accurate estimates for the walltimes of the submitted jobs. While this works for applications with deterministic resource needs, it can cause resource over-estimation or under-estimation for stochastic jobs with large variations in the walltime, thus degrading system and/or application performance [START_REF] Gainaru | On-the-fly scheduling versus reservation-based scheduling for unpredictable workflows[END_REF][START_REF] Weidner | Rethinking high performance computing platforms: Challenges, opportunities and recommendations[END_REF].

Clusters of commodity servers that use big-data frameworks such as MapReduce [START_REF] Dean | MapReduce: Simplified data processing on large clusters[END_REF] and Dryad [START_REF] Isard | Dryad: Distributed data-parallel programs from sequential building blocks[END_REF] offer alternative solutions to running HPC workloads. Schedulers for these frameworks such as YARN [START_REF] Vavilapalli | Apache hadoop yarn: Yet another resource negotiator[END_REF] and Mesos [START_REF] Hindman | Mesos: A platform for fine-grained resource sharing in the data center[END_REF] offer distinct features (e.g., fairness, resource negotiation) to manage the workloads, but they generally also require accurate information regarding the applications' resource demands.

Cloud computing platforms such as Amazon AWS [START_REF]AWS pricing information[END_REF] and Google GCP [START_REF]GCP pricing information[END_REF] have emerged as another option for executing HPC applications, with a variety of pricing and reservation schemes. Both on-demand and reservation models are available with the latter typically offering a lower price. Several works [START_REF] Afanasyev | Service provider competition: Delay cost structure, segmentation, and cost advantage[END_REF][START_REF] Chen | Pricing schemes in cloud computing: Utilization-based versus reservation-based[END_REF][START_REF] Dierks | Cloud pricing: the spot market strikes back[END_REF][START_REF] Xu | Dynamic cloud pricing for revenue maximization[END_REF] have studied the pricing strategies for platform providers, as well as delay modeling and cost evaluation for the users.

Stochastic scheduling and checkpointing Many prior works have considered stochastic scheduling for jobs with execution time uncertainty. Most research in this paradigm (e.g., [START_REF] Bruno | Sequencing tasks with exponential service times to minimize the expected flow time or makespan[END_REF][START_REF] Goel | Stochastic load balancing and related problems[END_REF][START_REF] Kleinberg | Allocating bandwidth for bursty connections[END_REF][START_REF] Möhring | Approximation in stochastic scheduling: The power of LP-based priority policies[END_REF][START_REF] Mora | Stochastic scheduling. Encyclopedia of Optimization[END_REF]) assumes that the execution time of a job follows a known probability distribution and aims to optimize the expected response time or makespan for a set of jobs under various distributions. Most of them, however, do not consider the problem in the context of reservation-based scheduling. In our prior work [START_REF] Aupy | Reservation Strategies for Stochastic Jobs[END_REF], we have proposed near-optimal reservation strategies for a single job in both HPC and cloud systems. The work was later extended to scheduling a set of stochastic jobs, both sequential and parallel, using backfilling in a reservation-based environment [START_REF] Gainaru | Speculative scheduling for stochastic HPC applications[END_REF][START_REF] Gainaru | On-the-fly scheduling versus reservation-based scheduling for unpredictable workflows[END_REF].

Another approach to coping with stochastic applications and/or platform unavailability is through checkpoint-restart [START_REF]Fault-Tolerance Techniques for High-Performance Computing[END_REF][START_REF] Wolter | Stochastic Models for Fault Tolerance, Restart, Rejuvenation, and Checkpointing[END_REF]. To ensure the robustness of the execution, the application's state is periodically checkpointed and in case of interrupt (due to either insufficient reservation or platform failure), the application can be recovered from the last saved checkpoint. In the context of fault tolerance, a lot of work (e.g., [START_REF] Daly | A higher order estimate of the optimum checkpoint interval for restart dumps[END_REF][START_REF]Fault-Tolerance Techniques for High-Performance Computing[END_REF][START_REF] Young | A first order approximation to the optimum checkpoint interval[END_REF]) has been devoted to deriving the optimal checkpointing interval that minimizes the checkpointing overhead or resource waste.

In this paper, we present strategies that combine reservation and checkpointing for stochastic jobs with known execution time distributions. To the best of our knowledge, this is the first result to provide performance guarantee on the expected execution time while leveraging checkpointing in reservation-based scheduling environment.

22

We have studied the problem of scheduling stochastic jobs running on a reservationbased platform. We presented a model and optimization framework which combine a sequence of reservations with associated checkpointing decisions. We provided an optimal solution via a dynamic programming algorithm in the case of discrete distributions. We also provided approximation scheme for bounded continuous distributions that are arbitrarily close to the optimal. We used both standard distributions and traces from real neuroscience applications to conduct an extensive set of simulations and actual experiments. Altogether, we have demonstrated the effectiveness of these new solutions in comparison with classic strategies. Hopefully, these results should help to convince HPC users and system administrators that significant improvements, in terms of both system and application performance, can be achieved by using a well-chosen reservation sequence rather than a unique reservation of maximum length (the current standard policy).

For future work, we are interested in analytically quantifying the critical checkpointing cost, below (or above) which the best strategy is to always (or never) checkpoint the reservations. This will help to fully characterize the optimal solution for a given application profile. Another interesting direction is to incorporate non-constant checkpointing costs into the optimization problem, in order to design new reservation strategies that will be more robust than our current solutions. This would alleviate the limitation of our approach when checkpointing costs exhibit a large variability.

Figure 1 :

 1 Figure 1: Execution times from 2017 for a Structural identification of orbital anatomy application, and its fitted distribution (in red).

Figure 2 :

 2 Figure 2: Illustration of different reservation strategies. The checkpoint (red) and restart (green) costs are equal to 7.

E(S 1

 1 ) = 80 E(S 2 ) = 20•P(X ≤ 20)+100•P(20 < X ≤ 80) = 20 × 0.66 + 100 × 0.34 = 47.2 E(S 3 ) = 27•P(X ≤ 20)+54•P(20 < X ≤ 40)+121•P(40 < X) = 27 × 0.66 + 54 × 0.26 + 121 × 0.08 = 41.54

Figure 3 :

 3 Figure 3: Illustration of the elapsed time for the reservation sequence S = {(W1, 1), (W2, 0), (W3, 1), (W4, 0)}.

Figure 4 :

 4 Figure 4: Illustration of job progress (and showing t k versus T k ) for the reservation sequence S = {(W1, 1), (W2, 0), (W3, 1), (W4, 0)}.

Figure 5 :Figure 6 :

 56 Figure 5: Expected costs of the different strategies normalized to that of Dyn-Prog-Count(X, 0.1) when C = R vary, for Exponential and Bounded Pareto distributions.

Table 2 :

 2 Expected cost of All-Ckpt-Per and No-Ckpt-Per, normalized by Dyn-Prog-Count(X, 0.1). C = R = 360s. Distribution All-Ckpt-Per No-Ckpt-Per Best τ τ = 1 τ = 200 τ = 400 τ = 600 τ = 800 τ = 1000 Best τ τ = 1 τ = 200 τ = 400 τ = 600 τ = 800 τ = 1000 Exponential 23 (1.

  (a) Variation of µ, σ = = 19.7h Variation of σ, µ = = 21.4h

Figure 7 :

 7 Figure 7: Normalized performance of algorithms with omniscient scheduler when µ or σ vary. Basis is the LogNormal distribution in Fig. 1 (µo = 21.4h, σ0 = 19.7h). C = R = 600s, ε = 1. Black (Dyn-Prog-Count) and yellow (All-Ckpt) lines overlap.

  Diffusion model fitting (Qball) Gamma (k = 1.18, θ = 34, [a, b] = [146s, 407s]) 90s 40s Diffusion model fitting (SD) Weibull (k = 1043811, λ = 1174322466, [a, b] = [46min, 2.3h]) 25min 10min Functional connectivity analysis (FCA) Gamma (k = 3.6, θ = 72, [a, b] = [165s, 1003s]) 150s 100s

Figure 8 :

 8 Figure 8: Utilization (higher is better) and average job stretch (lower is better) for Dyn-Prog-Count, All-Ckpt and the HPC strategies.

Table 3 :

 3 Characteristics of the chosen neuroscience applications.

For instance, Pareto is a long-tail distribution, meaning that it has a large number of occurrences that are far from the beginning and central part of its support. Formally, it means that 1-F (x+y) 1-F (x) → 1 when x → ∞, ∀y > 0.

Acknowledgments We thank the anonymous reviewers for their comments and suggestions. This research was supported in part by the Vanderbilt Institutional Fund. Some of the simulations presented in this paper were carried out using the PlaFRIM experimental testbed, supported by Inria, CNRS (LABRI and IMB), Université de Bordeaux, Bordeaux INP and Conseil Régional d'Aquitaine (see https://www.plafrim.fr/en/home/). The remaining simulation resources were provided by the computing facilities MCIA (Mésocentre de Calcul Intensif Aquitain) of the Université de Bordeaux and of the Université de Pau et des Pays de l'Adour.

Finally, we conduct experiments in a more realistic scenario by running all three applications simultaneously, and investigating the impact on the different strategies. Specifically, we submitted a total of 500 jobs (100 from Qball, and 200 each from SD and FCA), and kept the C/R costs constant across different reservations to study the sole impact of having several application types executing concurrently. We recorded the utilization and average job stretch when using Dyn-Prog-Count compared to the HPC strategy for 10 different runs choosing different instances from the traces each time. The results are presented in Table 4. We see that Dyn-Prog-Count improves both utilization and average job stretch by 10% on average, and by up to 20% depending on the instances submitted. Overall, these results again illustrate the robustness of our algorithm and confirm its benefit for scheduling stochastic applications on reservation-based platforms, as long as checkpoint costs remain constant for each application.

Related Work

We review some related work on reservation-based scheduling and checkpointing in HPC and cloud systems, as well as some prior work on dealing with stochastic applications.