Guillaume Aupy

Ana Gainaru

Valentin Le Fèvre

Periodic I/O scheduling for super-computers

Keywords: Scheduling, models, I/O, HPC, bandwidth, congestion Ordonnancement, modèles, entrées-sorties, HPC, bande passante, congestion

With the ever-growing need of data in HPC applications, the congestion at the I/O level becomes critical in super-computers. Architectural enhancement such as burst-buffers and pre-fetching are added to machines, but are not sufficient to prevent congestion. Recent online I/O scheduling strategies have been put in place, but they add an additional congestion point and overheads in the computation of applications. In this work, we show how to take advantage of the periodic nature of HPC applications in order to develop efficient periodic scheduling strategies for their I/O transfers. Our strategy computes once during the job scheduling phase a pattern where it defines the I/O behavior for each application, after which the applications run independently, transferring their I/O at the specified times. Our strategy limits the amount of I/O congestion at the I/O node level and can be easily integrated into current job schedulers. We validate this model through extensive simulations and experiments by comparing it to state-of-the-art online solutions, showing that not only our scheduler has the advantage of being de-centralized and thus overcoming the overhead of online schedulers, but also that it performs better than these solutions, improving the application dilation up to 13% and the maximum system efficiency up to 18%.

Introduction

In the race to larger supercomputers, the most commonly used metric is is the computational power. However supercomputers are not simply computers with billions of processors. One of the reason why Sunway TaihuLight (the world fastest supercomputer as of Nov 2016 [START_REF]top supercomputer list[END_REF]), reaches 93 PetaFlops on HPL (a performance benchmark based on dense linear algebra), but struggles to reach 0.37 PetaFlop on HPCG, a recent benchmark based on actual HPC applications [START_REF] Dongarra | Toward a new metric for ranking high performance computing systems[END_REF] is data movement. Nowadays, a supercomputing application creates or has to deal with TeraBytes of data. This is true in all fields, from medical research (Brain initiatives), to astrophysics (HACC [START_REF] Habib | The universe at extreme scale: multi-petaflop sky simulation on the BG/Q[END_REF], Enzo [START_REF] Bryan | An adaptive mesh refinement code for astrophysics[END_REF], HOMME [START_REF] Nair | Petascale atmospheric general circulation models[END_REF]), including meteorology (CM1 [START_REF] Bryan | A benchmark simulation for moist nonhydrostatic numerical models[END_REF]) and fusion plasma (GTC [START_REF] Ethier | Petascale parallelization of the gyrokinetic toroidal code[END_REF]). In 2013, Argonne upgraded its house supercomputer: moving from Intrepid (peak performance: 0.56 PFlops; peak I/O throughput: 88 GB/s) to Mira (peak performance: 10 PFlops; peak I/O throughput: 240 GB/s). While both criteria seem to have improved considerably, the reality behind is that for a given application, its I/O throughput scales linearly (or worse) with its performance, and hence, what should be noticed is a downgrade from 160 GB/PFlop to 24 GB/PFlop! On Intrepid, it was shown that I/O congestion could cause up to a 70% decrease to the I/O throughput [START_REF] Gainaru | Scheduling the i/o of hpc applications under congestion[END_REF].

To help with the ever growing amount of data created, architectural improvement such as burst buffers [START_REF] Liu | On the role of burst buffers in leadership-class storage systems[END_REF] have been added to the system. Work is being done to transform the data before sending it to the disks in the hope of reducing the I/O sent [START_REF] Dorier | Calciom: Mitigating I/O interference in HPC systems through cross-application coordination[END_REF]. However, even with the current I/O footprint burst buffers are not able to completely hide congestion. Moreover, the data used is always expected to grow. Recent works [START_REF] Gainaru | Scheduling the i/o of hpc applications under congestion[END_REF] have started working on novel online, centralized I/O scheduling strategies at the I/O node level. However one of the risk noted on these strategies is the scalability issue caused by potentially high overheads (between 1 and 5% depending on the number of nodes used in the experiments) [START_REF] Gainaru | Scheduling the i/o of hpc applications under congestion[END_REF]. Moreover, it is expected this overhead to increase at larger scale since it need centralized information about all applications running in the system.

In this paper, we present a decentralized I/O scheduling strategy for supercomputers. We show how to take known HPC application behaviors (namely their periodicity) into account to derive novel static algorithms. The periodicity of HPC applications has been well observed and documented [START_REF] Carns | 24/7 characterization of petascale I/O workloads[END_REF][START_REF] Gainaru | Scheduling the i/o of hpc applications under congestion[END_REF][START_REF] Dorier | Omnisc'io: a grammarbased approach to spatial and temporal i/o patterns prediction[END_REF]: HPC applications alternate between computation and I/O transfer, this pattern being repeated over-time. Furthermore, fault-tolerance technique (such as periodic checkpointing [START_REF] Daly | A higher order estimate of the optimum checkpoint interval for restart dumps[END_REF]) also add to this periodic behavior. Using this periodicity property, we compute a static periodic scheduling strategy, which provides a way for each applications to know when they should start transferring their I/O (i) hence reducing potential bottlenecks either due to I/O congestion, and (ii) without having to consult with I/O nodes every time I/O should be done and hence adding an extra overhead. The main contributions of this paper are:

• A novel light-weight I/O algorithm that looks at optimizing both applicationoriented (dilation or fairness) and platform-oriented (maximum system RR n°9037 efficiency) objectives; • A set of extensive simulations and experiments that show that this algorithm performs as well or better than current state of the art heavy-weight online algorithms. Note that the algorithm presented here is done as a proof of concept to show the efficiency of this kind of light-weight techniques. We believe our scheduler can be implemented naturally into a job scheduler and we provide experimental results backing this claim. However, this integration is beyond the scope of this paper.

The rest of the paper is organized as follows: in Section 2 we present the application model and optimization problem. In Section 3 we present our novel algorithm technique as well as a brief proof of concept for a future implementation. In Section 4 we present extensive simulations based on the model to show the performance of our algorithm compared to state of the art. We then confirm the performance on a super-computer to validate the model. We give some background and related work in Section 5. We provide concluding remarks and ideas for future research directions in Section 6.

Model

In this section we use the model introduced in our previous work [START_REF] Gainaru | Scheduling the i/o of hpc applications under congestion[END_REF] that has been verified experimentally to be consistent with the behavior of Intrepid and Mira, super-computers at Argonne.

We consider scientific applications running at the same time on a parallel platform. The applications consist of series of computations followed by I/O operations. On a super-computer, the computations are done independently because each application uses its own nodes. However, the applications are concurrently sending and receiving data during their I/O phase on a dedicated I/O network. The consequence of this I/O concurrency is congestion between an I/O node of the platform and the file storage.

Parameters

We assume that we have a parallel platform made up of N identical unit-speed nodes, composed of the same number of identical processors, each equipped with an I/O card of bandwidth b (expressed in bytes per second). We further assume a centralized I/O system with a total bandwidth B (also expressed in bytes per second). This means that the total bandwidth between the computation nodes and an I/O node is N • b while the bandwidth between an I/O node and the file storage is B, with usually N • b B. We have instantiated this model for the Intrepid platform on Figure 1.

We have K applications, all assigned to independent and dedicated computational resources, but competing for I/O. For each application App (k) we define:

• Its size: App (k) executes with β (k) dedicated processors; • Its pattern: App (k) obeys a pattern that repeats over time. There are n (k) tot instances of App (k) that are executed one after the other. Each instance consists of two disjoint phases: computations that takes a time w (k) , followed by I/O transfers for a total volume vol (k) io . The next instance cannot start before I/O operations for the current instance is terminated. We further denote by r k the time when App (k) is released on the platform and d k the time when the last instance is completed. Finally, we denote by γ (k) (t), the bandwidth used by a node on which application App (k) is running, at instant t.

Execution Model

As the computation resources are dedicated, we can always assume w.l.o.g that the next computation chunk starts right away after completion of the previous I/O transfers, and is executed at full (unit) speed. On the contrary, all applications compete for I/O, and congestion will likely occur. The simplest case is that of a single periodic application App (k) using the I/O system in dedicated mode during a time-interval of duration D. In that case, let γ be the I/O bandwidth used by each processor of App (k) during that time-interval. We derive the condition β (k) γD = vol (k) io to express that the entire I/O data volume is transferred. We must also enforce the constraints that (i) γ ≤ b (output capacity of each processor); and (ii) β (k) γ ≤ B (total capacity of I/O system). Therefore, the minimum time to perform the I/O transfers for an instance of App (k) is time

(k) io = vol (k) io min(β (k) b,B)
. However, in general many applications will use the I/O system simultaneously, whose bandwidth capacity B will be shared among all these applications (see Figure 2). This model is very flexible, and the only assumption is that at any instant, all processors assigned to a given application are assigned the same bandwidth.

RR n°9037

App (1) w (1) w (1) w ( 1) This assumption is transparent for the I/O system and simplifies the problem statement without being restrictive. Again, in the end, the total volume of I/O transfers for an instance of App (k) must be vol

App (2) w (2) w (2) w (2) App (3) w (3) w (3) w (3)

Bandwidth

(k)
io , and at any instant, the rules of the game are simple: never exceed the individual bandwidth b of each processor (γ (k) (t) ≤ b for any k and t), and never exceed the total bandwidth

B of the I/O system ( K k=1 β (k) γ (k) (t) ≤ B for any t).

Objectives

We now focus on the optimization objectives at hand here. We use the objectives introduced in [START_REF] Gainaru | Scheduling the i/o of hpc applications under congestion[END_REF].

First, the application efficiency achieved for each application App (k) at time t is defined as

ρ(k) (t) = i≤n (k) (t) w (k,i) t -r k , where n (k) (t) ≤ n (k)
tot is the number of instances of application App (k) that have been executed at time t, since the release of App (k) at time r k . Because we execute w (k,i) units of computation followed by vol

(k,i) io units of I/O operations on instance I (k) i of App (k) , we have t -r k ≥ i≤n (k) (t) w (k,i) + time (k,i) io
. Due to I/O congestion, ρ(k) never exceeds the optimal efficiency that can be achieved for App (k) , namely

ρ (k) = w (k) w (k) + time (k) io
The two key optimization objectives, together with a rationale for each of them, are:

• SysEfficiency: where we maximize the peak performance of the platform, namely maximizing the amount of operations per time unit:

maximize 1 N K k=1 β (k) ρ(k) (d k ). (1)
• Dilation: where we minimize the largest slowdown imposed to each application (hence optimizing fairness across applications): minimize max

k=1..K ρ (k) ρ(k) (d k ) . (2)
Note that it is known that both problems are NP-complete, even in an (easier) offline setting [START_REF] Gainaru | Scheduling the i/o of hpc applications under congestion[END_REF].

Periodic scheduling strategy

In general, for an application App (k) , n (k) tot the number of instances of App (k) is very large and not polynomial in the size of the problem. For this reason, online schedule have been preferred until now. The key novelty of this paper is to introduce periodic schedules for the K applications. Intuitively, we are looking for a computation and I/O pattern of duration T that will be repeated over time (except for initialization and clean up phases), as shown on Figure 3a. In this section, we start by introducing the notion of periodic schedules and a way to compute the application efficiency differently. We then provide the algorithms that are at the core of this work.

Because there is no competition on computation (no shared resources), we can consider that a chunk of computation directly follows the end of the transfer of I/O, hence we need only to represent I/O transfers in this pattern. The bandwidth used by each application during the I/O operations is represented over time, as shown in Figure 3b. We can see that an operation can overlap with the one of the previous pattern or the next pattern, but overall, the pattern will just repeat.

To describe a pattern, we use the following notations:

• n (k)
per : the number of instances of App (k) during a pattern.

• I (k) i : the i-th instance of App (k) during a pattern. • initW (k) i : the time of the beginning of I (k) i . So, I (k) i has a computation interval going from initW (k) i to endW (k) i = initW (k) i + w (k) mod T . • initIO (k)
i : the time when the I/O transfer from the i-th instance of App (k) starts (between endW

(k) i and initIO (k) i , App (k) is idle). Therefore, we have initW (k) (i+1)%n (k) per initIO (k) i β (k) γ (k) (t)dt = vol (k) io .
Globally, if we consider the two dates per instance initW (k) per distinct dates, that are called the events of the pattern. We define the periodic efficiency of a pattern of size T :

ρ(k) per = n (k) per w (k) T . (3)

RR n°9037

Bw Time Init For periodic schedules, we use it to approximate the actual efficiency achieved for each application. The rationale behind this can be seen on Figure 3. If App (k) is released at time r k , and the first pattern starts at time r k + c, that is after an initialization phase, then the main pattern is repeated n times (until time n•T +r k +c), and finally App (k) ends its execution after a clean-up phase at time d k = r k +c+n•T +c . If we assume that n•T c+c , then d k -r k ≈ n•T . Then the value of the ρ(k) (d k ) for App (k) is:

ρ(k) (d k ) = n • n (k) per + δ w (k) d k -r k = n • n (k) per + δ w (k) c + n • T + c ≈ n (k) per w (k) T = ρ(k)
per where δ can be 1 or 0 depending whether App (k) was executed or not during the clean-up or init phase.

PerSched: a periodic scheduling algorithm

For details in the implementation, we refer the interested reader to the source code available at https: // github. com/ vlefevre/ IO-scheduling-simu .

The difficulties of finding an efficient periodic schedule are three-fold:

• The first one is that the right pattern size has to be determined;

• The second one is that for a given pattern size, the number of instances of each application that should be included in this pattern need to be determined;

• Finally, the time constraint between two consecutive I/O transfers of a given application, due to the computation in-between makes naive scheduling strategies harder to implement.

Finding the right pattern size A solution is to find schedules with different pattern sizes between a minimum pattern size T min and a maximum pattern size T max .

Because we want a pattern to have at least one instance of each application, we can trivially set up T min = max k (w (k) + time (k) io ). Intuitively, the larger T max is, the more possibilities we can have to find a good solution. However this also increases the complexity of the algorithm. We want to limit the number of instances of all applications in a schedule. For this reason we chose to have

T max = O(max k (w (k) + time (k) io )
). We discuss this hypothesis in Section 4, where we give better experimental intuition on finding the right value for T max . Experimentally we observe (Section 4, Figure 7) that T max = 10T min seems to be sufficient.

We then decided on an iterative search where the pattern size increases exponentially at each iteration from T min to T max . In particular, we use a precision ε as input and we iteratively increase the pattern size from T min to T max by a factor (1 + ε). This allows us to have a polynomial number of iterations. The rationale behind the exponential increase is that when the pattern size gets large, we expect performance to converge to an optimal value, hence needing less the precision of a precise pattern size. Furthermore while we could try only large pattern size, it seems important to find a good small pattern size as it would simplify the scheduling step. Hence a more precise search for smaller pattern sizes. Finally, we expect the best performance to cycle with the pattern size. We verify these statements experimentally in Section 4 (Figure 6).

Determining the number of instances of each application By choosing

T max = O(max k (w (k) + time (k) io
)), we guarantee the maximum number of instances of each application that fit into a pattern is

O max k (w (k) +time (k) io ) min k (w (k) +time (k) io )
.

Instance scheduling Finally, our last item is, given a pattern of size T , how to schedule instances of applications into a periodic schedule.

To do this, we decided on a strategy where we insert instances of applications in a pattern, without modifying dates and bandwidth of already scheduled instances. Formally, we call an application schedulable: Definition 1 (Schedulable). Given an existing pattern

P = ∪ K k=1 n (k) per , ∪ n (k) per i=1 {initW (k) i , initIO (k) i , γ (k) ()} , RR n°9037
we say that an application App (k) is schedulable if there exists 1

≤ i ≤ n (k)
per , such that:

initIO (k) i -w (k) initW (k) i +w (k) min β (k) b, B - l β (l) γ (l) (t) dt ≥ vol (k) io (4) Bw Time 0 0 B vol (1) io vol (1) io vol (2) io vol (2) io vol (2) io vol (3) io initW (2) 2 +w (2) initIO (2) 2 -w (2)
Figure 4: Description of what schedulable means: if we want to insert an instance of App (2) , we need to check that the blue area is greater than vol [START_REF] Behzad | Taming parallel I/O complexity with auto-tuning[END_REF] io , while the red area is reserved for the computation of w (2) .

To understand the integral in Equation ( 4): we are checking that during the end of the computation of the i th instance (initW

(k) i + w (k)
), and the beginning of the computation of the i + 1 th instance (initIO

(k) i -w (k)
), there is enough bandwidth to perform at least a volume of I/O of vol (k) io . We represent it graphically on Figure 4.

With Definition 1, we can now explain the core idea of the instance scheduling part of our algorithm. Starting from an existing pattern, while there exist applications that are schedulable:

• Amongst the applications that are schedulable, we choose the application that has the worse Dilation. The rationale is that even though we want to increase SysEfficiency, we do it in a way that ensures that all applications are treated fairly; • We insert the instance into an existing scheduling using a procedure Insert-

In-Pattern such that (i) the first instance of each application is inserted using procedure Insert-First-Instance which minimizes the time of the I/O transfer of this new instance, (ii) the other instances are inserted just after the last inserted one. Note that Insert-First-Instance is implemented using a water-filling algorithm [START_REF] Gallager | Information theory and reliable communication[END_REF] and Insert-In-Pattern is implemented as described in Algorithm 1. We use a different function for the first instance of each application because we do not have any previous instance to use the Insert-In-Pattern function. Thus, the basic idea would be to put them at the beginning of the pattern, but it will be more likely to create congestion if all applications are "synchronized" (for example if all the applications are the same, they will all start their I/O phase at the same time). By using Insert-First-Instance, every first instance will be at a place where the congestion for it is minimized. This creates a starting point for the subsequent instances. The function addInstance updates the pattern with the new instance, given a list of the intervals (E l , E l , b l ) during which App (k) transfers I/O between E l and E l using a bandwidth b l .

Correcting the period size In Algorithm 2, the pattern sizes under trial are determined by T min and ε. There is no reason why this would be the right pattern size, and one might be interested in reducing it to fit precisely the instances that are included in the solutions that we found.

In order to do so, once a periodic pattern has been computed, we try to improve the best pattern size we found in the first loop of the algorithm, by trying new pattern sizes, close to the previous best one, let us say T opt . To do this, we add a second loop which now tries 1/ε uniformly distributed pattern sizes from T opt to T opt /(1 + ε).

With all of this in mind, we can now write PerSched (Algorithm 2), our algorithm to construct a periodic pattern. For all pattern sizes tried between T min and T max , we return the pattern with maximal SysEfficiency.

RR n°9037

Algorithm 2: Periodic Scheduling heuristic:

PerSched procedure PerSched(K , ε, {App (k) } 1≤k≤K ) begin Tmin ← max k (w (k) + time (k) io ); Tmax ← K • Tmin; T = Tmin; SE ← 0; Topt ← 0; Popt ← {}; while T ≤ Tmax do P = {};
while exists a schedulable application do while exists a schedulable application do

A = {App (k) |App (k) is schedulable}; Let App (k) be the element of A minimal with respect to the lexicographic order ρ (k) ρ(k) per , w (k)
A = {App (k) |App (k) is schedulable}; Let App (k) be the element of A minimal with respect to the lexicographic order ρ (k) ρ(k) per , w (k) time (k) io ; P ←Insert-In-Pattern(P, App (k) ); if SysEfficiency(P) = T opt T • SE then Popt ← P; T ← T -(Topt - T opt 1+ε )/ 1/ε else return Popt
We estimate SysEfficiency of a periodic pattern, by replacing ρ(k) (d k ) by ρ(k) per in Equation (1) RR n°9037

Complexity analysis

Finally, in this section we show that our algorithm runs in reasonnable execution time. We detail theoretical results that allowed us to reduce the complexity. We want to show the following result:

Theorem 1. Let n max = max k (w (k) +time (k) io ) min k (w (k) +time (k) io ) , PerSched(K , ε, {App (k) } 1≤k≤K ) runs in O 1 ε + log K log(1 + ε) • K 2 (n max + log K ) .
Some of the complexity results are straightforward. The key results to show are:

• The complexity of the tests "while exists a schedulable application" on lines 11 and 23

• The complexity of computing A and finding its minimum element on line 13 and 25.

• The complexity of Insert-In-Pattern

To reduce the execution time, we proceed as follows: instead of implementing the set A, we implement a heap à that could be summarized as (k) is not yet known to not be schedulable} sorted following the lexicographic order:

{App (k) |App
ρ (k) ρ(k) per , w (k) time (k) io
. Hence, we replace the while loops on lines 11 and 23 by the algorithm snippet described in Algorithm 3. The idea is to avoid calling Insert-In-Pattern after each new inserted instance to know which applications are schedulable.

Algorithm 3: Schedulability snippet 11 à = ∪ k {App (k) } (sorted by ρ (k) ρ(k) per , w (k) time (k) io ); 12 while à = ∅ do 13
Let App (k) be the minimum element of Ã;

;

We then need to show that they are equivalent, that is:

RR n°9037
• At all time, the minimum element of à is minimal amongst the schedulable applications with respect to the order ρ (k)

ρ(k) per , w (k) time (k) io
(shown in Lemma 4);

• If à = ∅ then there are no more schedulable applications (shown in Corollary 2).

To show this, it is sufficient to show that (i) at all time, A ⊂ Ã, and (ii) Ã is always sorted according to

ρ (k) ρ(k) per , w (k) time (k) io
.

Definition 2 (Compact pattern). We say that a pattern

P = ∪ K k=1 n (k) per , ∪ n (k) per i=1 {initW (k) i , initIO (k) i , γ (k) ()} is compact if for all 1 ≤ i < n (k)
per , either initW

(k) i + w (k) = initIO (k) i , or for all t ∈ [initW (k) i , initIO (k) i ], l β (l) γ (l) (t) = B.
Intuitively, this means that we can only schedule a new instance for all application App (k) between I Proof. For each application, either we use Insert-First-Instance to insert the first instance (so P is compact as there is only one instance of an application at this step), either we use Insert-In-Pattern which inserts an instance just after the last inserted one, which is the definition of being compact. Hence, P is compact at any time during PerSched.

Lemma 2. Insert-In-Pattern(P, App (k) ) returns P, if and only if App (k) is not schedulable.

Proof. One can easily check that Insert-In-Pattern checks the schedulability of App (k) only between the last inserted instance of App (k) and the first instance of App (k) . Furthermore, because of the compacity of P (Lemma 1), this is sufficient to test the overall schedulability.

Then the test is provided by the last condition Dataleft > 0.

• If the condition is false, then the algorithm actually inserts a new instance, so it means that one more instance of App (k) is schedulable. • If the condition is true, it means that we cannot insert a new instance after the last inserted one. Because P is compact, we cannot insert an instance at another place. So if the condition is true, we cannot add one more instance of App (k) in the pattern.

Corollary 1. In Algorithm 3, an application App (k) is removed from à if and only if it is not schedulable.

Lemma 3. If an application is not schedulable at some step, it will not be either in the future.

Proof. Let us suppose that App (k) is not schedulable at some step. In the future, new instances of other applications can be added, thus possibly increasing the total bandwidth used at each instant. The total I/O load is non-decreasing during the execution of the algorithm. Thus if for all i, we had

initIO (k) i -w (k) initW (k) i +w (k) min β (k) b, B - l β (l) γ (l) (t) dt < vol (k) io ,
then in the future, with new bandwidths used γ (l) (t) > γ (l) (t), we will still have that for all i,

initIO (k) i -w (k) initW (k) i +w (k) min β (k) b, B - l β (l) γ (l) (t) dt < vol (k) io .
Corollary 2. At all time,

A = {App (k) |App (k) is schedulable} ⊂ Ã.
This is a direct corollary of Corollary 1 and Lemma 3 Lemma 4. At all time, the minimum element of à is minimal amongst the schedulable applications with respect to the order ρ (k)

ρ(k) per , w (k) time (k) io
(but not necessarily schedulable).

Proof. First see that {App (k) |App (k) is schedulable} ⊂ Ã. Furthermore, initially the minimality property is true. Then the set à is modified only when a new instance of an application is added to the pattern. More specifically, only the application that was modified has its position in à modified. One can easily verify that for all other applications, their order with

respect to ρ (k) ρ(k) per , w (k) time (k) io
has not changed, hence the set is still sorted. This concludes the proof that the snippet is equivalent to the while loops. With all this we are now able to show timing results for the version of Algorithm 2 that uses Algorithm 3.

Lemma 5. The loop on line 23 of Algorithm 2 terminates in at most 1/ε steps.

Proof. The stopping criteria on line 27 checks that the number of instances did not change when reducing the pattern size. Indeed, by definition for a pattern P,

SysEfficiency(P) = k β (k) ρ(k) per = k β (k) n (k) per w (k) T .
Denote SE the SysEfficiency reached in T opt at the end of the while loop on line 11 of Algorithm 2. Let SysEfficiency(P) be the SysEfficiency obtained in T opt /(1 + ε). By definition, SysEfficiency(P) < SE and T opt 1 + ε SysEfficiency(P) < T opt SE.

Necessarily, after at most 1/ε iterations, Algorithm 2 exits the loop on line 23.

Proof of Theorem 1.

There are m pattern sizes tried where T min • (1 + ε) m = T max in the main "while" loop (line 9), that is

m = log T max -log T min log(1 + ε) = log K log(1 + ε)
.

Furthermore, we have seen (Lemma 5) that there are a maximum of 1/ε pattern sizes tried of the second loop (line 21).

For each pattern size tried, the cost is dominated by the complexity of Algorithm 3. Let us compute this complexity.

• The construction of à is done in O(K log K).

• In sum, each application can be inserted a maximum of n max times in à (maximum number of instances in any pattern), that is the total of all insertions has a complexity of O(K log Kn max ).

We are now interested by the complexity of the different calls to Insert-In-Pattern.

First one can see that we only call Insert-First-Instance K times, and in particular they correspond to the first K calls of Insert-In-Pattern. Indeed, we always choose to insert a new instance of the application that has the largest current slowdown. The slowdown is infinite for all applications at the beginning, until their first instance is inserted (or they are removed from Ã) when it becomes finite, meaning that the K first insertions will be the first instance of all applications.

During the k-th call, for 1 ≤ k ≤ K, there will be n = 2(k-1)+2 events (2 for each previously inserted instances and the two bounds on the pattern), meaning that the complexity of Insert-First-Instance will be O(n log n) (because of the sorting of the bandwidths available by non-increasing order to choose the intervals to use). So overall, the K first calls have a complexity of O(K 2 log K).

Furthermore, to understand the complexity of the remaining calls to Insert-In-Pattern we are going to look at the end result. In the end there is a maximum of n max instance of each applications, that is a maximum of 2n max K events. For all application App (k) , for all instance

I (k) i k, 1 < i ≤ n (k)
, the only events considered in Insert-In-Pattern when scheduling I (k) i k were the ones between the end of initW

(i) k + w (k) and initW (i)
k+1 . Indeed, since the schedule has been able to schedule vol (k) io , Insert-In-Pattern will exit the while loop on line 13. Finally, one can see that the events considered for all instances of an application partition the pattern without overlapping. Furthermore, Insert-In-Pattern has a linear complexity in the number of events considered. Hence a total complexity by application of O(n max K). Finally, we have K applications, the overall time spent in Insert-In-Pattern for inserting new instances is O(K 2 n max ).

Hence, with the number of different pattern tried, we obtain a complexity of

O m + 1 ε K 2 log K + K 2 n max .
Note that in practice, both K and K are small (≈ 10), and ε is close to 0, hence making the complexity O nmax ε .

High-level implementation, proof of concept

We envision the implementation of this periodic scheduler to take place at two levels:

1) The job scheduler would know the applications profile (using solutions such as Omnisc'IO [START_REF] Dorier | Omnisc'io: a grammarbased approach to spatial and temporal i/o patterns prediction[END_REF]). Using profiles it would be in charge of computing a periodic pattern every time an application enters or leaves the system.

2) Application-side I/O management strategies (such as [START_REF] Zhang | Opportunistic data-driven execution of parallel programs for efficient I/O services[END_REF][START_REF] Lofstead | Managing variability in the IO performance of petascale storage systems[END_REF][START_REF] Tessier | Topologyaware data aggregation for intensive i/o on large-scale supercomputers[END_REF]) then would be responsible to ensure the correct transfer of I/O at the right time by limiting the bandwidth used by nodes that transfer I/O. The start and end time for each I/O as well as the used bandwidth are described in input files.

Evaluation and model validation

Note that the data used for this section and the scripts to generate the figures are available at https: // github. com/ vlefevre/ IO-scheduling-simu .

In this section, we (i) assess the efficiency of our algorithm by comparing it to a recent dynamic framework [START_REF] Gainaru | Scheduling the i/o of hpc applications under congestion[END_REF], and (ii) validate our model by comparing theoretical performance (as obtained by the simulations) to actual performance on a real system.

We perform the evaluation in three steps: first we simulate behavior of applications and input them into our model to estimate both Dilation and SysEfficiency of our algorithm (Section 4.4) and evaluate these cases on an actual machine to confirm the validity of our model. Finally, in Section 4.5 we confirm the intuitions introduced in Section 3 to determine the parameters used by PerSched.

Experimental Setup

The platform available for experimentation is Jupiter at Mellanox, Inc. To be able to verify our model, we use it to instantiate our platform model. Jupiter is a Dell PowerEdge R720xd/R720 32-node cluster using Intel Sandy Bridge CPUs. Each node has dual Intel Xeon 10-core CPUs running at 2.80 GHz, 25 MB of L3, 256 KB unified L2 and a separate L1 cache for data and instructions, each 32 KB in size. The system has a total of 64GB DDR3 RDIMMs running at 1.6 GHz per node. Jupiter uses Mellanox ConnectX-3 FDR 56Gb/s InfiniBand and Ethernet VPI adapters and Mellanox SwitchX SX6036 36-Port 56Gb/s FDR VPI InfiniBand switches.

We measured the different bandwidths of the machine and obtained b = 0.01GB/s and B = 3GB/s. Therefore, when 300 cores transfer at full speed (less than half of the 640 available cores), congestion occurs.

Implementation of scheduler on Jupiter

We simulate the existence of such a scheduler by computing beforehand the I/O pattern for each application and feeding it as input files. The experiments require a way to control the exact moment when all applications perform I/O, use the CPU or stay idle waiting to start their I/O. For this purpose, we modified the IOR benchmark [START_REF] Shan | Using IOR to analyze the I/O performance for HPC platforms[END_REF] to read the input files that provide the start and end time for each I/O transfer as well as the bandwidth used. Our scheduler generates one such file for each application. Each IOR instance represents one application whose I/O pattern is described in one of the generated scheduling files. The IOR benchmark is split in different sets of processes running independently on different nodes, where each set represents a different application. One separate process acts as the scheduler and receives I/O requests for all groups in IOR. Since we are interested in modeling the I/O delays due to congestion or scheduler imposed delays, the modified IOR benchmarks do not use inter-processor communications.

We made experiments on our IOR benchmark and compared the results between periodic and online schedulers as well as with the performance of the original IOR benchmark without any extra scheduler.

Applications and scenarios

In the literature, there are many examples of periodic applications. Carns et al. [START_REF] Carns | 24/7 characterization of petascale I/O workloads[END_REF] observed with Darshan the periodicity of four different applications (MADBench2 [START_REF] Carter | Performance characteristics of a cosmology package on leading HPC architectures[END_REF], Chombo I/O benchmark [START_REF] Colella | Chombo infrastructure for adaptive mesh refinement[END_REF], S3D IO [START_REF] Sankaran | Direct numerical simulations of turbulent lean premixed combustion[END_REF] and HOMME [START_REF] Nair | Petascale atmospheric general circulation models[END_REF]). Furthermore, in our previous work [START_REF] Gainaru | Scheduling the i/o of hpc applications under congestion[END_REF] we were able to verify the periodicity App (k) w (k) (s) vol of gyrokinetic toroidal code (GTC) [START_REF] Ethier | Petascale parallelization of the gyrokinetic toroidal code[END_REF], Enzo [START_REF] Bryan | An adaptive mesh refinement code for astrophysics[END_REF], HACC application [START_REF] Habib | The universe at extreme scale: multi-petaflop sky simulation on the BG/Q[END_REF] and CM1 [START_REF] Bryan | A benchmark simulation for moist nonhydrostatic numerical models[END_REF]. Unfortunately, few documents give the actual values for w (k) , vol

(k) io (GB) β (k) Turbulence1 (
io and β (k) . Liu et al. [START_REF] Liu | On the role of burst buffers in leadership-class storage systems[END_REF] provide different periodic patterns of four scientific applications: PlasmaPhysics, Turbulence1, Astrophysics and Turbulence2. They were also the top four write-intensive jobs run on Intrepid in 2011. We chose the most I/O intensive patterns for all applications (as they are the most likely to create I/O congestion). We present these results in Table 1. Note that to scale those values to our system, we divided the number of processors β (k) by 64, hence increasing w (k) by 64. The I/O volume stays constant.

To compare our strategy, we tried all possible combinations of those applications such that the number of nodes used equals 640. That is a total of ten different scenarios that we report in Table 2.

Baseline and evaluation of existing degradation

We ran all scenarios on Jupiter without any additional scheduler. In all tested scenarios congestion occurred and decreased the visible bandwidth used by each applications as well as significantly increased the total execution time. We present in Table 3 Depending on the IO transfers per computation ratio of each application as well as how the transfers of multiple applications overlap, the slowdown in the perceived bandwidth ranges between 25% to 65%. Interestingly, set 1 presents the worst degradation. This scenario is running concurrently ten times the same application, which means that the I/O for all applications are executed almost at the same time (depending on the small differences in CPU execution time between nodes). This scenario could correspond to coordinated checkpoints for an application running on the entire system. The degradation in the perceived bandwidth can be as high as 65% which considerably increases the time to save a checkpoint. The use of I/O schedulers can decrease this cost, making the entire process more efficient.

Comparison to online algorithms

In this subsection, we present the results obtained by running PerSched and the online heuristics from our previous work [START_REF] Gainaru | Scheduling the i/o of hpc applications under congestion[END_REF]. Because in [START_REF] Gainaru | Scheduling the i/o of hpc applications under congestion[END_REF] we had different heuristics to optimize either Dilation or SysEfficiency, in this work, the Dilation and SysEfficiency presented are the best reached by any of those heuristics. This means that there are no online solution able to reach them both at the same time! We show that even in this scenario, our algorithm outperforms these heuristics for both optimization problems! PerSched takes as input a list of applications, as well as the parameters, presented in Section 3, K = Tmax Tmin , ε. All scenarios were tested with K = 10 and ε = 0.01.

Simulation results

We present in Table 4 all evaluation results. The results obtained by running Algorithm 2 are called PerSched. To go further in our evaluation, we also look for the best Dilation obtainable with our pattern (we do so by changing line 15 of PerSched). We call this result min Dilation in Table 4. This allows us to estimate how far the Dilation that we obtain is from what we can do. Furthermore, we can compute an upper bound to SysEfficiency by replacing ρ(k) by ρ (k) in Equation ( 1): The first noticeable result is that PerSched almost always outperfoms (when it does not, matches) both the Dilation and SysEfficiency attainable by the online scheduling algorithms! This is particularly impressive as these objectives are not obtained by the same online algorithms (hence conjointly), contrarily to the PerSched result.

Upper bound = 1 N K k=1 β (k) w (k) w (k) + time (k) io . (5)
While the gain is minimal (from 0 to 3%, except SysEfficiency increased by 7% for case 4) when little congestion occurs (cases 4 to 10), the gain is between 9% and 16% for Dilation and between 7% and 18% for SysEfficiency when congestion occurs (cases 1, 2, 3)!

The value of ε has been chosen so that the computation stays short. It seems to be a good compromise as the results are good and the execution times vary from 4 ms (case 10) to 1.8s (case 5) using a Intel Core I7-6700Q. Note that the algorithm is easily parallelizable, as each iteration of the loop is independent. Thus it may be worth considering a smaller value of ε, but there will be no big improvement on the results.

Model validation through experimental evaluation We used the modified IOR benchmark to reproduce the behavior of applications running on HPC systems and analyze the benefits of I/O schedulers. We made experiments on the 640 cores of the Jupiter system. Additionally to the results from both periodic and online heuristics, we present the performance of the system with no additional I/O scheduler. The performance estimated by our model is accurate within 3.8% for periodic schedules and 2.3% for online schedules.

Figure 5 shows the SysEfficiency (normalized using the upper bound in Table 4) and Dilation when using the periodic scheduler in comparison with the online scheduler. For the system efficiency the upper limit and the results when applications are running without any scheduler are also shown. As observed in the previous section, the periodic scheduler gives better or similar results to the best solutions that can be returned by the online ones, in some cases increasing the system performance by 18% and the dilation by 13%. When we compare to the current strategy on Jupiter, the SysEfficiency reach 48%! In addition, the periodic scheduler has the benefit of not requiring a global view of the execution of the applications at every moment of time (by opposition to the online scheduler).

Finally, a key information from those results is the precision of our model introduced in Section 2. The theoretical results (based on the model) are within 3% of the experimental results! This observation is key in launching more thorough evaluation via extensive simulations and is critical in the experimentation of novel periodic scheduling strategies.

Discussion on finding the best pattern size

The core of our algorithm is a search of the best pattern size via an exponential growth of the pattern size until T max . As stated in Section 3, the intuition of the exponential growth is that the larger the pattern size, the less needed the precision for the pattern size as it might be easier to fit many instances of each We verify this experimentally and plot on Figure 6 the SysEfficiency and Dilation found by our algorithm as a function of the pattern size T .

Finally, the last information to determine to tweak PerSched is the value of T max . Remember that we denote K = T max /T min .

To be able to get an estimate of the pattern size returned by PerSched, we provide in Table 5 (i) the maximum number of instances n inst of any application, and (ii) the ratio

n max = max k w (k) +time (k) io min k w (k) +time (k) io
. Together along with the fact that the Dilation (Table 4) is always below 2 they give a rough idea of K (≈ ninst nmax ). It is sometimes close to 1, meaning that a small value of K can be sufficient, but choosing K ≈ 10 is necessary in the general case.

We then want to verify the cost of under-estimating T max . For this evaluation all runs were done up to K = 100 with ε = 0.01. Denote SysEfficiency(K ) (resp. Dilation(K )) the maximum SysEfficiency (resp. corresponding Di-lation) obtained when running PerSched with K . We plot their normalized version that is: fast: when K = 3, the average SysEfficiency is within 0.3% of SysEfficiency(100), but the corresponding average Dilation is 5% higher than Dilation(100). If we go to K = 10 then we have a SysEfficiency of 0.1% of SysEfficiency(100) and a Dilation within 1% of Dilation(100)! Hence validating that choosing K = 10 is sufficient.

SysEfficiency(K ) SysEfficiency(

Related Work

Performance variability due to resource sharing can significantly detract from the suitability of a given architecture for a workload as well as from the overall performance realized by parallel workloads [START_REF] Skinner | Understanding the causes of performance variability in HPC workloads[END_REF]. Over the last decade there have been studies to analyze the sources of performance degradation and several solutions have been proposed. In this section, we first detail some of the existing work that copes with I/O congestion and then we present some of the theoretical literature that is similar to our Periodic problem. The storage I/O stack of current HPC systems has been increasingly identified as a performance bottleneck. Significant improvements in both hardware and software need to be addressed to overcome oncoming scalability challenges. The study in [START_REF] Isaila | Making the case for data staging coordination and control for parallel applications[END_REF] argues for making data staging coordination driven by generic cross-layer mechanisms that enable global optimizations by enforcing local decisions at node granularity at individual stack layers.

While many other studies suggest that I/O congestion is one of the main problems for future scale platforms [START_REF] Biswas | Petascale computing: Impact on future NASA missions[END_REF][START_REF] Lofstead | Insights for exascale IO APIs from building a petascale IO API[END_REF], few papers focus on finding a solution at the platform level. Some paper consider application-side I/O management and transformation (using aggregate nodes, compression etc) [START_REF] Zhang | Opportunistic data-driven execution of parallel programs for efficient I/O services[END_REF][START_REF] Lofstead | Managing variability in the IO performance of petascale storage systems[END_REF][START_REF] Tessier | Topologyaware data aggregation for intensive i/o on large-scale supercomputers[END_REF]. We consider those work to be orthogonal to our work and able to work jointly. Recently, numerous works focus on using machine learning for auto tuning and performance studies [START_REF] Behzad | Taming parallel I/O complexity with auto-tuning[END_REF][START_REF] Kumar | Characterization and modeling of pidx parallel I/O for performance optimization[END_REF]. However these solution also work at the application level for IO-scheduling and do not have a global view of the I/O requirements of the system and they need to be supported by a platform level I/O management for better results. Some paper consider the use of burst buffers to reduce I/O congestion by delaying accesses to the file storage, as they found that congestion occurs on a short period of time and the bandwidth to the storage system is often underutilized [START_REF] Liu | On the role of burst buffers in leadership-class storage systems[END_REF]. However, the computation power tends to increase faster than the I/O bandwidth, which may cause the bandwidth to be saturated more often and thus decreasing the efficiency of burst buffers. [START_REF] Kougkas | Leveraging Burst Buffer Coordination to Prevent I/O Interference[END_REF] presents a dynamic I/O scheduling at the application level using burst buffers to stage I/O and to allow computations to continue uninterrupted. They design different strategies to mitigate I/O interference, including partitioning the PFS, which reduces the effective bandwidth non-linearly. However, the strategies are basically designed for only 2 applications and their heuristics does not take into account the characteristics of the applications to better optimize the scheduling.

The study from [START_REF] Seelam | Virtual i/o scheduler: A scheduler of schedulers for performance virtualization[END_REF] offers ways of isolating the performance experienced by applications of one operating system from variations in the I/O request stream characteristics of applications of other operating systems. While their solution cannot be applied to HPC systems, the study offers a way of controlling the coarse grain allocation of disk time to the different operating system instances as well as determining the fine-grain interleaving of requests from the corresponding operating systems to the storage system.

Closer to this work, online schedulers for HPC systems were developed such as our previous work [START_REF] Gainaru | Scheduling the i/o of hpc applications under congestion[END_REF], the study by Zhou et al [START_REF] Zhou | I/oaware batch scheduling for petascale computing systems[END_REF], and a solution proposed by Dorier et al [START_REF] Dorier | Calciom: Mitigating I/O interference in HPC systems through cross-application coordination[END_REF]. In [START_REF] Dorier | Calciom: Mitigating I/O interference in HPC systems through cross-application coordination[END_REF], the authors investigate the interference of two applications and analyze the benefits of interrupting or delaying either one in order to avoid congestion. Unfortunately their approach cannot be used for more than two applications. Another main difference with our previous work is the light-weight approach of this study where the computation is only done once.

Our previous study [START_REF] Gainaru | Scheduling the i/o of hpc applications under congestion[END_REF] is more general by offering a range of options to schedule each I/O performed by an application. Similarly, the work from [START_REF] Zhou | I/oaware batch scheduling for petascale computing systems[END_REF] also utilizes a global job scheduler to mitigate I/O congestion by monitoring and controlling jobs' I/O operations on the fly. Unlike online solutions, this paper focuses on a decentralized approach where the scheduler is integrated into the job scheduler and computes ahead of time, thus overcoming the need to monitor the I/O traffic of each application at every moment of time.

As a scheduling problem, our problem is somewhat close to the cyclic scheduling problem (we refer to Hanen and Munier [START_REF] Hanen | Cyclic scheduling on parallel processors: an overview[END_REF] for a survey), namely there are given a set of activities with time dependency between consecutive tasks stored in a DAG that should be executed on p processors. The main difference is that in cyclic scheduling there is no consideration of a constant time between the end of the previous instance and the next instance.

Conclusion

Performance variation due to resource sharing in HPC systems is a reality and I/O congestion is currently one of the main causes of degradation. Current storage systems are unable to keep up with the amount of data handled by all applications running on an HPC system, either during their computation or when taking checkpoints. In this document we have presented a novel I/O scheduling technique that offers a decentralized solution for minimizing the congestion due to application interference. Our method takes advantage of the periodic nature of HPC applications by allowing the job scheduler to pre-define each application's I/O behavior for their entire execution. Recent studies [START_REF] Dorier | Omnisc'io: a grammarbased approach to spatial and temporal i/o patterns prediction[END_REF] have shown that HPC applications have predictable I/O patterns even when they are not completely periodic, thus we believe our solution is general enough to easily include the large majority of HPC applications.

We conducted simulations for different scenarios and made experiments to validate our results. Decentralized solutions are able to improve both total system efficiency and application dilation compared to dynamic state-of-theart schedulers. Moreover, they do not require a constant daemon capable of monitoring the state of all applications, nor do they require a change in the current I/O stack. One particularly interesting result is for scenario 1 with 10 identical periodic behaviors (such as what can be observed with periodic checkpointing for fault-tolerance). In this case the periodic scheduler shows a 30% improvement in SysEfficiency. Thus, system wide applications taking global checkpoints could benefit from such a strategy.

Future work: we believe this work is the initialization of a new set of techniques to deal with the I/O requirements of HPC system. In particular, by showing the efficiency of the periodic technique on simple pattern, we expect to open a door to multiple extensions. We give here some examples that we will consider in the future. The next natural directions is to take more complicated periodic shapes for applications (an instance could be composed of sub-instances) as well as different point of entry inside the job scheduler (multiple IO nodes). This would be modifying the Insert-In-Pattern procedure and we expect that this should work well as well. Another future step would be to study how variability in the compute or I/O volumes impact a periodic schedule or the impact of non periodic applications. Finally we plan to model burst buffers and to show how to use them conjointly with periodic schedules.

Our method is used for minimizing the congestion caused by concurrent I/O accesses. However, the methodology and concepts are general and can be applied to any resource sharing problem. We will continue to investigate the causes for performance degradation in HPC applications and adapt our findings to each case.

Figure 1 :

 1 Figure 1: Model instantiation for the Intrepid platform [14].

Figure 2 :

 2 Figure 2: Scheduling the I/O of three periodic applications (top: computation, bottom: I/O).

  change between computation and I/O phases, we have a total of S ≤ K k=1 2n

Figure 3 :

 3 Figure 3: A schedule (above), and the detail of one of its regular pattern (below), where (w (1) = 3.5; vol (1) io = 240; n (1) per = 3), (w (2) = 27.5; vol (2) io = 288; n (2) per = 3), (w (3) = 90; vol

Algorithm 1 : 3 if 9 13 while 22 return

 1391322 Insert-In-Pattern 1 procedure Insert-In-Pattern(P, App (k) ) 2 begin App (k) has 0 instance then 4 return Insert-First-Instance (P,App (k) ); the last inserted instance of App (k) ; 8 Let E0, E1, • • • , Ej i the times of the events between the end of I {i} k + w (k) and the beginning of I {(i+1) mod l T (k)} k ; For l = 0 • • • ji -1, let B l be the minimum between β (k) b and the available bandwidth during [E l , E l+1 ]; DataLeft > 0 and l < ji do 14 if B l > 0 then 15 TimeAdded = min(E l+1 -E l , DataLeft/B l ); 16 DataLeft -= TimeAdded•B l ; 17 sol = [(E l , E l + T imeAdded, B l )] + sol; P.addInstance(App (k) ,sol)

  In-Pattern(P, App (k) ); if SE < SysEfficiency(P) then SE ← SysEfficiency(P); Topt ← T ; Popt ← P T ← T • (1 + ε); T ← Topt; while true do P = {};

14 Ã 16 if P = P then 17 P ← P ; 18 Insert

 14161718 ← à \ {App (k) }; 15 Let P =Insert-In-Pattern(P, App (k) ); App (k) in à following ρ (k)

Lemma 1 .

 1 At any time during PerSched, P is compact.

Figure 5 :

 5 Figure5: Performance for both experimental evaluation and theoretical (simulated) results. The performance estimated by our model is accurate within 3.8% for periodic schedules and 2.3% for online schedules.

Figure 6 :

 6 Figure 6: Evolution of SysEfficiency and Dilation when the pattern size increases.

Figure 7 :

 7 Figure 7: Normalized system efficiency and dilation obtained by Algorithm 2 averaged on all 10 sets as a function of K (with Standard Error bars).

Table 1 :

 1 Details of each application.

		T1)		70		128.2 32,768
	Turbulence2	(T2)		1.2		235.8	4,096
	AstroPhysics	(AP)		240		423.4	8,192
	PlasmaPhysics (PP)		7554		34304 32,768
		Set # T1 T2 AP PP
		1	0	10	0	0
		2	0	8	1	0
		3	0	6	2	0
		4	0	4	3	0
		5	0	2	0	1
		6	0	2	4	0
		7	1	2	0	0
		8	0	0	1	1
		9	0	0	5	0
		10	1	0	1	0

Table 2 :

 2 Number of applications of each type launched at the same time for each experiment scenario.

Table 3 :

 3 the average I/O bandwidth slowdown due to congestion for Bandwidth slowdown, performance and application slowdown for each set of experiments the most representative scenarios together with the corresponding values for SysEfficiency.

	Set #	Application	BW slowdown SysEfficiency
	1	Turbulence 2	65.72%	0.064561
	2	Turbulence 2	63.93%	0.250105
		AstroPhysics	38.12%
	3	Turbulence 2	56.92%	0.439038
		AstroPhysics	30.21%
	4	Turbulence 2	34.9%	0.610826
		AstroPhysics	24.92%
	6	Turbulence 2	34.67%	0.621977
		AstroPhysics	52.06%
	10	Turbulence 1	11.79%	0.98547
		AstroPhysics	21.08%

Table 4 :

 4 Best Dilation and SysEfficiency for our periodic heuristic and online heuristics.

	Set	Min Dilation	Upper bound SysEff	PerSched Dilation SysEff Dilation SysEff Online
	1	1.777	0.172	1.896	0.0973	2.091	0.0825
	2	1.422	0.334	1.429	0.290	1.658	0.271
	3	1.079	0.495	1.087	0.480	1.291	0.442
	4	1.014	0.656	1.014	0.647	1.029	0.640
	5	1.010	0.816	1.024	0.815	1.039	0.810
	6	1.005	0.818	1.005	0.814	1.035	0.761
	7	1.007	0.827	1.007	0.824	1.012	0.818
	8	1.005	0.977	1.005	0.976	1.005	0.976
	9	1.000	0.979	1.000	0.979	1.004	0.978
	10	1.009	0.988	1.009	0.986	1.015	0.985

Table 5 :

 5 Maximum number of instances (n inst ) per application, ratio between longest and shortest application (n max ) in the solution returned by PerSched.application. On the contrary, we expect that for small pattern sizes finding the right one might be a precision job.

	RR n°9037

RR n°9037

Acknowledgement

Part of this work was done when Guillaume Aupy and Valentin Le Fèvre were at Vanderbilt University. The authors would like to thank Anne Benoit and Yves Robert for helpful discussions.


J Audouard

A Määttänen

C Listowski

F Forget

A Spiga

E Millour

CO2 ICE CLOUDS SCHEME FOR CLIMATE MODELS -J. Audouard et al. A COMPLETE CO 2 ICE CLOUDS MODEL FOR GCMs AND MESOSCALE MODELS

Introduction:

Since the first claimed detection of Martian CO2 clouds [START_REF] Herr | Evidence for Solid Carbon Dioxide in the Upper Atmosphere of Mars[END_REF], numerous observations (e.g. [START_REF] Clancy | CO2 ice clouds in the upper atmosphere of Mars[END_REF][START_REF] Montmessin | Subvisible CO 2 ice clouds detected in the mesosphere of Mars[END_REF][START_REF] Montmessin | Hyperspectral imaging of convective CO2 ice clouds in the equatorial mesosphere of Mars[END_REF][START_REF] Määttänen | Mapping the mesospheric CO 2 clouds on Mars: MEx/OMEGA and MEx/HRSC observations and challenges for atmospheric models[END_REF][START_REF] Vincendon | New near-IR observations of mesospheric CO2 and H2O clouds on Mars[END_REF], theoretical advances and modeling works [START_REF] Määttänen | Nucleation studies in the Martian atmosphere[END_REF][START_REF] Määttänen | Two-component heterogeneous nucleation kinetics and an application to Mars[END_REF][START_REF] Colaprete | CO 2 clouds, CAPE and convection on Mars: Observations and general circulation modeling[END_REF][START_REF] Spiga | Gravity waves, cold pockets and CO2 clouds in the Martian mesosphere[END_REF][START_REF] Listowski | Near-pure vapor condensation in the Martian atmosphere: CO2 ice crystal growth[END_REF][START_REF] Listowski | Modeling the microphysics of CO2 ice clouds within wave-induced cold pockets in the martian mesosphere[END_REF] have improved our understanding of CO2 cloud formation and dynamics on Mars. These clouds, less frequently observed than the water ice clouds, form in the troposphere at the poles during winter and at equatorial latitudes in the mesosphere (60 -110 km).

Atmospheric CO2 condensation requires extremely low temperatures to produce supersaturation. Such low temperatures are reached during the polar night and have been observed at low latitudes in the mesosphere (Schofield et al., 1997 ;[START_REF] Montmessin | Subvisible CO 2 ice clouds detected in the mesosphere of Mars[END_REF][START_REF] Forget | Density and temperatures of the upper Martian atmosphere measured by stellar occultations with Mars Express SPICAM[END_REF]. These cold pockets are most likely produced by gravity waves propagating to the upper atmosphere [START_REF] Spiga | Gravity waves, cold pockets and CO2 clouds in the Martian mesosphere[END_REF], at the altitudes of the temperature minima caused by the thermal tides.

Moreover, aerosol particles must be present for the CO2 to condense on them by the mean of heterogeneous nucleation. At high mesospheric altitudes and such low pressures (typically 0.01 Pa), it is unknown whether dust lifted from the surface or particles coming from above (such as meteoritic dust) prevail. CO2 clouds are short-lived and do not last long after the favorable conditions vanish (about a dozen of minutes, [START_REF] Listowski | Modeling the microphysics of CO2 ice clouds within wave-induced cold pockets in the martian mesosphere[END_REF].

Towards understanding Martian CO2 cloud formation, abundance and features, including their formation and evolution in a Global Climate Model (GCM) is necessary. Their precise radiative impact on the climate throughout the history of the planet is especially of prime importance due to the backscattering of the infrared photons by the CO2 ice crystals that might have contributed to a greenhouse effect.

The purpose of this work is to include a complete and validated CO2 cloud scheme (developped by [START_REF] Listowski | Near-pure vapor condensation in the Martian atmosphere: CO2 ice crystal growth[END_REF][START_REF] Listowski | Modeling the microphysics of CO2 ice clouds within wave-induced cold pockets in the martian mesosphere[END_REF] in the GCM of the Laboratoire de Météorologie Dynamique (LMD) [START_REF] Forget | Improved general circulation models of the Martian atmosphere from the surface to above 80 km[END_REF]. We hereafter present the key steps of this coupling and the first results.

CO2 clouds microphysics:

Martian mesospheric CO2 clouds have the specificity to form from the main atmospheric component, at very low pressures (~0.01 Pa) and temperatures.

Aerosol particles must be present to trigger the CO2 condensation in a supersaturated environment Fig. 1 : Atmospheric temperature profiles with gravity-wave induced cold pockets simulated by the LMD Mesoscale model [START_REF] Spiga | A new model to simulate the Martian mesoscale and microscale atmospheric circulation: Validation and first results[END_REF][START_REF] Spiga | Gravity waves, cold pockets and CO2 clouds in the Martian mesosphere[END_REF]. The red dotted line is the CO2 saturation curve. From [START_REF] Listowski | Modeling the microphysics of CO2 ice clouds within wave-induced cold pockets in the martian mesosphere[END_REF] such as S > 1, where S is the saturation ratio defined as the CO2 partial pressure over the CO2 saturation vapor pressure. Following the work on nucleation of [START_REF] Määttänen | Nucleation studies in the Martian atmosphere[END_REF]2007) and the water ice cloud model of [START_REF] Montmessin | New insights into Martian dust distribution and water-ice cloud microphysics[END_REF], a specific bin microphysics scheme has been developped by [START_REF] Listowski | Near-pure vapor condensation in the Martian atmosphere: CO2 ice crystal growth[END_REF][START_REF] Listowski | Modeling the microphysics of CO2 ice clouds within wave-induced cold pockets in the martian mesosphere[END_REF]. It uses heterogeneous nucleation with a contact parameter m=0.952 and then computes at each time step the growth rate (condensation or sublimation) of the activated CO2 ice particle.

Global Climate Model:

We want to implement the CO2 cloud microphysics scheme of Listowki et al. (2013Listowki et al. ( , 2014) ) into the LMD-GCM presented in [START_REF] Forget | Improved general circulation models of the Martian atmosphere from the surface to above 80 km[END_REF].

As it is, the GCM does not include a realistic gravity wave parametrization and hence can not produce mesospheric temperatures low enough to trigger CO2 cloud formation.

In order to validate our implementation, we therefore use the 1-D version of the GCM. The physic implied is shared with the 3-D global and mesoscale versions but the 1-D version allow us to control more freely the different inputs to produce ideal scenari for CO2 cloud formation, such as the temperature and dust profiles in the atmosphere.

The CO2 microphysics scheme is implemented in the code inside a microphysical time loop equal to 1/30th of the physical time step (i.e. ~ 30s). At each microphysical time step, we compute the saturation ratio, the nucleation probability and growth rate of the particles and thus the evolution of three specific tracers : the CO2 ice mass ratio, the activated condensation nuclei concentration and mass ratio. The latent heat released by the CO2 condensation is taken into account. In contrast with [START_REF] Listowski | Modeling the microphysics of CO2 ice clouds within wave-induced cold pockets in the martian mesosphere[END_REF]'s bin model, our model is a two-moment bulk parameterisation scheme that predicts the total mass and number density of CO2 ice crystals.

In our implementation of CO2 cloud microphysics, the dust population is discretized in 40 different bin sizes ranging from 1 nm to 50 µm. Each bin is populated with regards to the current atmospheric profiles of the dust concentration and mass.

The gravitational sedimentation of the CO2 ice particles and activated condensation nuclei is performed inside the microphysical sub-time loop.

Mesosphere cold pockets:

Wind blowing on the surface topography propagates a short-lived temperature wave (or gravity wave) to the upper atmosphere. When it reaches the mesosphere, the resulting cold pockets can be below the CO2 saturation curve (function of P and T). A mesospheric model such as [START_REF] Spiga | A new model to simulate the Martian mesoscale and microscale atmospheric circulation: Validation and first results[END_REF] can simulate these gravity waves and produce atmospheric temperature profiles presented in Fig. 1. These gravity wave-induced mesospheric cold pockets provide a good environment for CO2 cloud for-mation and growth, provided enough condensation nuclei are present. They also account for the large scale atmospheric state (including the thermal tides).

In order to validate our CO2 microphysic implementation in the LMD-GCM, we use the temperature profiles of Fig. 1 as input to our 1-D runs, hence producing ideal conditions for CO2 clouds formation in the mesosphere.

Moreover, in order to explore the sensitivity of the CO2 microphysics scheme to the saturation ratio, we can subtract or add a few Kelvins to the temperature profiles presented in Fig. 1.

First simulations:

As input to our 1-D simulations using the LMD-GCM, we choose the atmospheric dust profiles (concentration and mass ratio) in order to explore a plausible range of aerosols available for CO2 condensation in the mesosphere. Our chosen dust size profiles decreases with altitude by the mean of an exponential law.

Elapsed time (hours)

Our test simulations last less than 1 sol, and at a given time, we use the gravity wave-perturbed atmospheric temperature profiles of Fig. 1 as input. These profiles evolve for 3.6 hours and are forced from a given time, as can be seen in Fig. 2a. This setup produces cold pockets in the mesosphere, below the CO2 saturation curve and thus supersaturation (Fig. 2b). When the condition S > 1 is reached, the CO2 microphysics scheme is called by the model and a cloud can form and evolve. The cloud rapidly decays when the super-saturation disappears (Fig 2c).

With this method reproducing ideal conditions for CO2 cloud formation, we are able to produce realistic cloud properties (altitude, radius, dynamics) with regards to the observations (e.g. [START_REF] Määttänen | Mapping the mesospheric CO 2 clouds on Mars: MEx/OMEGA and MEx/HRSC observations and challenges for atmospheric models[END_REF]. We observe a strong dependency of the resulting cloud properties on the input parameters, especially the saturation ratio (i.e. the amplitude of the cold pocket) and the dust abundance and particle size in the mesosphere.

We then investigate the sensitivity of simulated CO2 clouds to super-saturation and dust size and abundance in the mesosphere.

We perform the same kind of idealized simulations with different values for the dust size and the saturation ratio for a fixed dust content. We report the mean and maximum values of the obtained CO2 clouds particle size and concentration in Fig. 3. The CO2 ice particles radius are at most a few µm, in agreement with retrievals from observations [START_REF] Määttänen | Mapping the mesospheric CO 2 clouds on Mars: MEx/OMEGA and MEx/HRSC observations and challenges for atmospheric models[END_REF] and simulation decoupled from a GCM using the same CO2 microphysics scheme and temperature profiles in a radius bin model [START_REF] Listowski | Modeling the microphysics of CO2 ice clouds within wave-induced cold pockets in the martian mesosphere[END_REF]. Here also, the behaviour depicted is expected : large aerosol particles imply less but bigger CO2 ice particles, and more as the saturation increases.

Conclusions and prospects :

We have implemented a specific two moments CO2 ice clouds microphysics scheme in the LMD-GCM.

First results using the 1-D version of the LMD-GCM and idealized conditions produce clouds with realistic properties and behaviour.

The produced clouds are very sensitive to especially the aerosol abundance and radius in the mesosphere on which the CO2 condenses.

We now have a tool for simulating CO2 clouds coupled to the LMD-GCM. We look forward to simulating clouds with the mesoscale version of the LMD-GCM. This will allow to reproduce the real Martian mesospheric conditions accurately, and hence to study where, when and why we have or should be able to observe clouds in the Martian mesosphere.

We also plan to study the polar tropospheric CO2 clouds in the future and we will report on our advancement at the conference.

Aknowledgment:

This work is funded by the excellence laboratory Exploration Spatiale des Environnements Planétaires, Labex ESEP N 2011-LABX-030. J. A. acknowledges the support of the French government and the ANR within the Investissements d'avenir programme through the excellence initiative PSL*(ANR-10-IDEX-0001-02).

Fig. 2 :

 2 Fig. 2 : Ideal conditions simulation of CO2 clouds. (a) The atmospheric temperature is imposed from fig. 1 (Gravity-wave induced cold pockets) at 7.2 local time and last ~3.6 hours ; (b) corresponding saturation ratio S ; (c) produced cloud, indicated by the CO2 ice particles radi.

Fig

  Fig 3a show the mean CO2 ice particle size (inside the cloud) as a function of the aerosol size in the mesosphere and the saturation. Fig 3b represent the same simulation set, with the max CO2 ice particle size as a function of saturation and aerosol size. These two diagrams show an expected behaviour: the cloud particles are larger as the saturation increases and as the aerosols available for heterogeneous nucleation are larger.

Fig

  Fig 3cshows the variations of the CO2 ice particle concentration as a function of the saturation ratio and aerosol size. Here also, the behaviour depicted is expected : large aerosol particles imply less but bigger CO2 ice particles, and more as the saturation increases.

Fig. 3 :

 3 Fig. 3 : Variations of the CO2 ice particle mean (a), maximum (b) radius and maximum concentration (c) as a function of saturation ratio S and aerosol particle size in the mesosphere.