Keywords: Plate-forme maître-esclave hétérogène, ordonnancement en-ligne, applications concurrentes

Ordonnancement hors-ligne et en-ligne d'applications concurrentes de types sacs de tâches¡ sur plates-formes hétérogènes

Résumé : Les problèmes liés à l'ordonnancement de tâches sont déjà difficiles sur des machines traditionnelles. Ils deviennent encore plus inextricables sur des machines hétérogènes, même lorsque les applications considérées sont facilement parallélisables (de type tâches indépendantes). Nous nous intéressons ici à l'ordonnancement d'applications multiples, sous forme de collections de tâches indépendantes et identiques, sur une plate-forme maître-esclave hétérogène. Les requêtes de calcul surviennent au cours du temps, ce qui signifie que nous ne disposons pas de connaissance sur la charge de travail au tout début de l'exécution. Notre objectif est de minimiser l'étirement (stretch) maximum des applications, c'est-à-dire le rapport entre le temps que l'application passe dans le système avant d'être terminée et le temps qu'elle y aurait passé si elle disposait de la plate-forme pour elle seule. D'un point de vue théorique, nous concevons un algorithme optimal pour le cas hors-ligne (offline), lorsque toutes les dates d'arrivée et les caractéristiques des applications sont connues à l'avance. Nous proposons également plusieurs méthodes heuristiques pour le cas en-ligne (online), sans connaissance sur l'arrivée future des applications. D'un point vue expérimental, nous avons mené des expérimentations approfondies sous la forme de simulations avec SimGrid mais aussi dans un environment parallèle réel, en utilisant MPI. Ces expérimentations montrent que nous sommes capables d'ordonnancer des problèmes de grande taille en quelques secondes. Enfin, la solution que nous proposons surpasse les méthodes heuristiques classiques, ce qui démontre l'intérêt de notre démarche.

Introduction

Scheduling problems are already difficult on traditional parallel machines. They become extremely challenging on heterogeneous clusters, even when embarrassingly parallel applications are considered. For instance, consider a bag-of-tasks [START_REF] Adler | Optimal sharing of bags of tasks in heterogeneous clusters[END_REF], i.e., an application made of a collection of independent and identical tasks, to be scheduled on a master-worker platform. Although simple, this kind of framework is typical of a large class of problems, including parameter sweep applications [START_REF] Casanova | Grid'[END_REF] and BOINC-like computations [START_REF]Berkeley Open Infrastructure for Network Computing[END_REF]. If the master-worker platform is homogeneous, i.e., if all workers have identical CPUs and same communication bandwidths to/from the master, then elementary greedy strategies, such as purely demanddriven approaches, will achieve an optimal throughput. On the contrary, if the platform gathers heterogeneous processors, connected to the master via different-speed links, then the previous strategies are likely to fail dramatically. This is because it is crucial to select which resources to enroll before initiating the computation [START_REF] Banino | Scheduling strategies for master-slave tasking on heterogeneous processor platforms[END_REF][START_REF] Pineau | Matrix product on heterogeneous master-worker platforms[END_REF].

In this paper, we still target fully parallel applications, but we introduce a much more complex (and more realistic) framework than scheduling a single application. We envision a situation where users, or clients, submit several bags-of-tasks to a heterogeneous masterworker platform, using a classical client-server model. Applications are submitted online, which means that there is no a priori (static) knowledge of the workload distribution at the beginning of the execution. When several applications are executed simultaneously, they compete for hardware (network and CPU) resources.

What is the scheduling objective in such a framework? A greedy approach would execute the applications sequentially in the order of their arrival, thereby optimizing the execution of each application onto the target platform. Such a simple approach is not likely to be satisfactory for the clients. For example, the greedy approach may delay the execution of the second application for a very long time, while it might have taken only a small fraction of the resources and few time-steps to execute it concurrently with the first one. More strikingly, both applications might have used completely different platform resources (being assigned to different workers) and would have run concurrently at the same speed as in exclusive mode on the platform. Sharing resources to execute several applications concurrently has two key advantages: (i) from the clients' point of view, the average response time (the delay between the arrival of an application and the completion of its last task) is expected to be much smaller; (ii) from the resource usage perspective, different applications will have different characteristics, and are likely to be assigned different resources by the scheduler. Overall, the global utilization of the platform will increase. The traditional measure to quantify the benefits of concurrent scheduling on shared resources is the maximum stretch. The stretch of an application is defined as the ratio of its response time under the concurrent scheduling policy over its response time in dedicated mode, i.e., when it is the only application executed on the platform. The objective is then to minimize the maximum stretch of any application, thereby enforcing a fair trade-off between all applications.

The aim of this paper is to provide a scheduling strategy which minimizes the maximum stretch of several concurrent bags-of-tasks which are submitted online. Our scheduling algorithm relies on complicated mathematical tools but can be computed in time polynomial to the problem size. On the theoretical side, we prove that our strategy is optimal for the offline version of the problem (when all release dates and application characteristics are known beforehand). We also introduce several heuristics for the general case of online applications. On the practical side, we have conducted extensive simulations and MPI experiments, showing that we are able to deal with very large problem instances in a few seconds. Also, the solution that we compute totally outperforms classical heuristics from the literature, thereby fully assessing the usefulness of our approach.

The rest of the paper is organized as follows. Section 2 describes the platform and application models. Section 3 is devoted to the derivation of the optimal solution in the offline case, and to the presentation of heuristics for online applications. In Section 4 we report an extensive set of simulations and MPI experiments, and we compare the optimal solution against several classical heuristics from the literature. Section 5 is devoted to an overview of related work. Finally, we state some concluding remarks in Section 6.

Framework

In this section, we outline the model for the target platforms, as well as the characteristics of the applicative framework. Next we survey steady-state scheduling techniques and we introduce the objective function, namely the maximum stretch of the applications.

Platform Model

We target a heterogeneous master-worker platform (see Figure 1), also called star network or single-level tree in the literature.

The master P master is located at the root of the tree, and there are p workers P u (1 ≤ u ≤ p). The link between P master and P u has a bandwidth b u . We assume a linear cost model, hence it takes X/b u time-units to send (resp. receive) a message of size X to (resp. from) P u . The computational speed of worker P u is s u , meaning that it takes X/s u time-units to execute X floating point operations. Without any loss of generality, we assume that the master has no processing capability. Otherwise, we can simulate the computations of the master by adding an extra worker paying no communication cost.

Communication models

Traditional scheduling models enforce the rule that computations cannot progress faster than processor speeds would allow: limitations of computation resources are well taken into account. Curiously, these models do not make similar assumptions for communications: in the literature, an arbitrary number of communications may take place at any time-step [START_REF] Yang | DSC: Scheduling parallel tasks on an unbounded number of processors[END_REF][START_REF] Brucker | Scheduling Algorithms[END_REF]. In particular, a given processor can send an unlimited number of messages in parallel, and each of these messages is routed as if was alone in the system (no sharing of resources). Obviously, these models are not realistic, and we need to better take communication resources into account. To this purpose, we present two different models, which cover a wide range of practical situations.

Under the bounded multiport communication model [START_REF] Hong | Distributed adaptive task allocation in heterogeneous computing environments to maximize throughput[END_REF], the master can send/receive data to/from all workers at a given time-step. However, there is a limit on the amount of data that the master can send per time-unit, denoted as BW. In other words, the total amount of data sent by the master to all workers each time-unit cannot exceed BW. Intuitively, the bound BW corresponds to the bandwidth capacity of the master's network card; the flow of data out of the card can be either directed to a single link or split among several links indifferently, hence the multiport hypothesis. The bounded multiport model fully accounts for the heterogeneity of the platform, as each link has a different bandwidth. Simultaneous sends and receives are allowed (all links are assumed bi-directional, or full-duplex).

Another, more restricted model, is the one-port model [START_REF] Bhat | Efficient collective communication in distributed heterogeneous systems[END_REF][START_REF] Bhat | Efficient collective communication in distributed heterogeneous systems[END_REF]. In this model the master can send data to a single worker at a given time, so that the sending operations have to be serialized. Suppose for example that the master has a message of size X to send to worker P u . We recall that the bandwidth of the communication link between both processors is b u . If the transfer starts at time t, then the master cannot start another sending operation before time t + X/b u . Usually, a processor is supposed to be able to perform one send and one receive operation at the same time. However, this hypothesis will not be useful in our study, as the master processor is the only one to send data.

The one-port model seems to fit the performance of some current MPI implementations, which serialize asynchronous MPI sends as soon as message sizes exceed a few hundreds of kilobytes [START_REF] Saif | Understanding the behavior and performance of non-blocking communications in MPI[END_REF]. However, recent multi-threaded communication libraries such as MPICH [START_REF] Gropp | A high-performance, portable implementation of the MPI message passing interface standard[END_REF][START_REF] Karonis | Mpich-g2: A grid-enabled implementation of the message passing interface[END_REF] allow for initiating multiple concurrent send and receive operations, thereby providing practical realizations of the multiport model.

Finally, for both the bounded multiport and the one-port models, we assume that computation can be overlapped by independent communication, without any interference.

Computation models

We propose two models for the computation. Under the fluid computation model, we assume that several tasks can be executed at the same time on a given worker, with a time-sharing mechanism. Furthermore, we assume that we totally control the computation rate for each task. For example, suppose that two tasks A and B are executed on the same worker at respective rates α and β. During a time period ∆t, α • ∆t units of work of task A and β • ∆t units of work of task B are completed. These computation rates may be changed at any time during the computation of a task.

Our second computation model, the atomic computation model, assumes that only a single task can be computed on a worker at any given time, and this execution cannot be stopped before its completion (no preemption).

Under both computation models, a worker can only start computing a task once it has completely received the message containing the task. However, for the ease of proofs, we add a variant to the fluid computation model, called synchronous start computation: in this model, the computation on a worker can start at the same time as the reception of the task starts, provided that the computation rate is smaller than, or equal to, the communication rate (the communication must complete before the computation). This models the fact that, in several applications, only the first bytes of data are needed to start executing a task. In addition, the theoretical results of this paper are more easily expressed under this model, which provides an upper bound on the achievable performance.

Proposed platform model taxonomy

We summarize here the various platform and application models under study:

Bounded Multiport with Fluid Computation and Synchronous Start (BMP-FC-SS).

This is the uttermost simple model: communication and computation start at the same time, communication and computation rates can vary over time within the limits of link and processor capabilities. We include this model in our study because it provides a good and intuitive framework to understand the results presented here. This model also provides an upper bound on the achievable performance, which we use as a reference for other models.

Bounded Multiport with Fluid Computation (BMP-FC). This model is a step closer to reality, as it allows computation and communication rates to vary over time, but it imposes that a task input data is completely received before its execution can start.

Bounded Multiport with Atomic Computation (BMP-AC). In this model, two tasks cannot be computed concurrently on a worker. This model takes into account the fact that controlling precisely the computing rate of two concurrent applications is practically challenging, and that it is sometimes impossible to run simultaneously two applications because of memory constraints.

One-Port Model with Atomic Computation (OP-AC). This is the same model as the BMP-AC, but with one-port communication constraint on the master. It represents systems where concurrent sends are not allowed.

In the following, we mainly focus on the variants of the bounded multiport model. We explain the results obtained with the one-port model in Section 3.

3.4.

INRIA

There is a hierarchy among all the multiport models: intuitively, in terms of hardness, BMP-FC-SS < BMP-FC < BMP-AC Formally, a valid schedule for BMP-AC is valid for BMP-FC and a valid schedule for BMP-FC is valid for BMP-FC-SS. This is why studying BMP-FC-SS is useful for deriving upper bounds for all other models.

Application model

We consider n bags-of-tasks A k , 1 ≤ k ≤ n. The master P master holds the input data of each application A k upon its release time. Application A k is composed of a set of Π (k) independent, same-size tasks. In order to completely execute an application, all its constitutive tasks must be computed (in any order).

We let w (k) be the amount of computations (expressed in flops) required to process a task of A k . The speed of a worker P u may well be different for each application, depending upon the characteristics of the processor and upon the type of computations needed by each application. To take this into account, we refine the platform model and add an extra parameter, using s (k) u instead of s u in the following. In other words, we move from the uniform machine model to the unrelated machine model of scheduling theory [START_REF] Brucker | Scheduling Algorithms[END_REF]. The time required to process one task of A k on processor P u is thus w (k) /s (k) u . Each task of A k has a size δ (k) (expressed in bytes), which means that it takes a time δ (k) /b u to send a task of A k to processor P u (when there are no other ongoing transfers). For simplicity we do not consider any return message: either we assume that the results of the tasks are stored on the workers, or we merge the return message of the current task with the input message of the next one (and update the communication volume accordingly).

Steady-state scheduling

Assume for a while that a unique bag-of-tasks A k is executed on the platform. If Π (k) , the number of independent tasks composing the application, is large (otherwise, why would we deploy A k on a parallel platform?), we can relax the problem of minimizing the total execution time. Instead, we aim at maximizing the throughput, i.e., the average (fractional) number of tasks executed per time-unit. We design a cyclic schedule, that reproduces the same schedule every period, except possibly for the very first (initialization) and last (clean-up) periods. It is shown in [START_REF] Beaumont | Bandwidth-centric allocation of independent tasks on heterogeneous platforms[END_REF][START_REF] Banino | Scheduling strategies for master-slave tasking on heterogeneous processor platforms[END_REF] how to derive an optimal schedule for throughput maximization. The idea is to characterize the optimal throughput as the solution of a linear program over rational numbers, which is a problem with polynomial time complexity.

Throughout the paper, we denote by ρ

(k)
u the throughput of worker P u for application A k , i.e., the average number of tasks of A k that P u executes each time-unit. In the special case where application A k is executed alone in the platform, we denote by ρ * (k) u the value of this throughput in the solution which maximizes the total throughput:

ρ * (k) = p u=1 ρ * (k) u .
We write the following linear program (see Equation ( 1)), which enables us to compute an asymptotically optimal schedule. The maximization of the throughput is bounded by three types of constraints:

The first set of constraints state that the processing capacity of P u is not exceeded.

The second set of constraints states that the bandwidth of the link from P master to P u is not exceeded.

The last constraint states that the total outgoing capacity of the master is not exceeded.

(1)

                       Maximize ρ * (k) = p u=1 ρ * (k) u subject to ∀1 ≤ u ≤ p, ρ * (k) u w (k) s (k) u ≤ 1 ∀1 ≤ u ≤ p, ρ * (k) u δ (k) bu ≤ 1 p u=1 ρ * (k) u δ (k) BW ≤ 1
The formulation in terms of a linear program is simple when considering a single application. In this case, a closed-form expression can be derived. First, the first two sets of constraints can be transformed into:

∀1 ≤ u ≤ p ρ * (k) u ≤ min s (k) u w (k) , b u δ (k) .
Then, the last constraint can be rewritten:

p u=1 ρ * (k) u ≤ BW δ (k) .
So that the optimal throughput is

ρ * (k) = min BW δ (k) , p u=1 min s (k) u w (k) , b u δ (k) .
It can be shown [START_REF] Beaumont | Bandwidth-centric allocation of independent tasks on heterogeneous platforms[END_REF][START_REF] Banino | Scheduling strategies for master-slave tasking on heterogeneous processor platforms[END_REF] that any feasible schedule under one of the multiport model has to enforce the previous constraints. Hence the optimal value ρ * (k) is an upper bound of the achievable throughput. Moreover, we can construct an actual schedule, based on an optimal solution of the linear program and which approaches the optimal throughput. The reconstruction is particularly easy. For example the following procedure builds an asymptotic optimal schedule for the BMP-AC model (bounded multiport communication with atomic computation). As this is the most constrained multiport model, this schedule is feasible in any multiport model:

INRIA

While there are tasks to process on the master, send tasks to processor P u with rate ρ * (k) u .

As soon as processor P u starts receiving a task it processes at the rate ρ * (k)

u .

Due to the constraints of the linear program, this schedule is always feasible and it is asymptotically optimal, not only among periodic schedules, but more generally among any possible schedules. More precisely, its execution time differs from the minimum execution time by a constant factor, independent of the total number of tasks Π (k) to process [START_REF] Banino | Scheduling strategies for master-slave tasking on heterogeneous processor platforms[END_REF]. This allows us to accurately approximate the total execution time, also called makespan, as:

M S * (k) = Π (k) ρ * (k) .
We often use M S * (k) as a comparison basis to approximate the makespan of an application when it is alone on the computing platform. If M S (k) opt is the optimal makespan for this single application, then we have

M S (k) opt -M k ≤ M S * (k) ≤ M S (k) opt
where M k is a fixed constant, independent of Π (k) .

Stretch

We come back to the original scenario, where several applications are executed concurrently. Because they compete for resources, their throughput will be lower. Equivalently, their execution rate will be slowed down. Informally, the stretch [START_REF] Bender | Flow and stretch metrics for scheduling continuous job streams[END_REF] of an application is the slowdown factor.

Let r (k) be the release date of application A k on the platform. Its execution will terminate at time C (k) ≡ r (k) +M S (k) , where M S (k) is the time to execute all Π (k) tasks of A k . Because there might be other applications running concurrently to A k during part or whole of its execution, we expect that M S (k) ≥ M S * (k) . We define the average throughput ρ (k) achieved by A k during its (concurrent) execution using the same equation as before:

M S (k) = Π (k) ρ (k) .
In order to process all applications fairly, we would like to ensure that their actual (concurrent) execution is as close as possible to their execution in dedicated mode. The stretch of application A k is its slowdown factor

S k = M S (k) M S * (k) = ρ * (k) ρ (k)
Our objective function is defined as the max-stretch S, which is the maximum of the stretches of all applications:

S = max 1≤k≤n S k
Minimizing the max-stretch S ensures that the slowdown factor is kept as low as possible for each application, and that none of them is unduly favored by the scheduler.

Theoretical study

The main contribution of this paper is a polynomial algorithm to schedule several bag-of-task applications arriving online, while minimizing the maximum stretch. We start this section with the presentation of an asymptotically optimal algorithm for the offline setting, when application release dates and characteristics are known in advance. Then we present our solution for the online framework.

Offline setting for the fluid model

Defining the set of possible solutions

In this section, we assume that all characteristics of the n applications A k , 1 ≤ k ≤ n are known in advance.

The scheduling algorithm is the following. Given a candidate value for the max-stretch, we have a procedure to determine whether there exists a solution that can achieve this value. The optimal value will then be found using a binary search on possible values.

Consider a candidate value S l for the max-stretch. If this objective is feasible, all applications will have a max-stretch smaller than S l , hence:

∀ 1 ≤ k ≤ n, M S (k) M S * (k) ≤ S l ⇐⇒ ∀1 ≤ k ≤ n, C (k) = r (k) + M S (k) ≤ r (k) + S l × M S * (k)
Thus, given a candidate value S l , we have a deadline:

(2)

d (k) = r (k) + S l × M S * (k)
for each application A k , 1 ≤ k ≤ n. This means that the application must complete before this deadline in order to ensure the expected max-stretch. If this is not possible, no solution is found, and a larger max-stretch should be tried by the binary search. Once a candidate stretch value S has been chosen, we divide the total execution time into time-intervals whose bounds are epochal times, that is, applications' release dates or deadlines. Epochal times are denoted t j ∈ {r (1) , ..., r (n) } ∪ {d (1) , . . . , d (n) }, such that t j ≤ t j+1 , 1 ≤ j ≤ 2n-1. Our algorithm consists in running each application A k during its whole execution window [r (k) , d (k) ], but with a different throughput on each time-interval [t j , t j+1 ] such that r (k) ≤ t j and t j+1 ≤ d (k) . Some release dates and deadlines may be equal, leading INRIA to empty time-intervals, for example if there exists j such that t j = t j+1 . We do not try to remove these empty time-intervals so as to keep simple indices.

Note that contrarily to the steady-state operation with only one application, in the different time-intervals, the communication throughput may differ from the computation throughput: when the communication rate is larger than the computation rate, extra tasks are stored in a buffer. On the contrary, when the computation rate is larger, tasks are extracted from the buffer and processed. We introduce new notations to take both rates, as well as buffer sizes, into account:

ρ (k)
M →u (t j , t j+1 ) denotes the communication throughput from the master to the worker P u during time-interval [t j , t j+1 ] for application A k , i.e., the average number of tasks of A k sent to P u per time-units.

ρ (k)
u (t j , t j+1 ) denotes the computation throughput of worker P u during time-interval [t j , t j+1 ] for application A k , i.e., the average number of tasks of A k computed by P u per time-units.

B (k)

u (t j ) denotes the (fractional) number of tasks of application A k stored in a buffer on P u at time t j .

We write the linear constraints that must be satisfied by the previous variables. Our aim is to find a schedule with minimum stretch satisfying those constraints. Later, based on rates satisfying these constraints, we show how to construct a schedule achieving the corresponding stretch.

All tasks sent by the master. The first set of constraints ensures that all the tasks of a given application A k are actually sent by the master:

(3) ∀ 1 ≤ k ≤ n, 1≤j≤2n-1 tj ≥ r (k) tj+1 ≤ d (k) p u=1 ρ (k) M →u (t j , t j+1 ) × (t j+1 -t j ) = Π (k) .
Non-negative buffers. Each buffer should always have a non-negative size:

(4) ∀ 1 ≤ k ≤ n, ∀1 ≤ u ≤ p, ∀1 ≤ j ≤ 2n, B (k) u (t j ) ≥ 0.
Buffer initialization. At the beginning of the computation of application A k , all corresponding buffers are empty:

(5)

∀ 1 ≤ k ≤ n, ∀1 ≤ u ≤ p, B (k) u (r (k) ) = 0.
Emptying Buffer. After the deadline of application A k , no tasks of this application should remain on any node:

(6) ∀ 1 ≤ k ≤ n, ∀1 ≤ u ≤ p, B (k) u (d (k) ) = 0.
Task conservation. During time-interval [t j , t j+1 ], some tasks of application A k are received and some are consumed (computed), which impacts the size of the buffer:

(7) ∀ 1 ≤ k ≤ n, ∀1 ≤ j ≤ 2n -1, ∀1 ≤ u ≤ p, B (k) u (t j+1 ) = B (k) u (t j ) + ρ (k) M →u (t j , t j+1 ) -ρ (k) u (t j , t j+1 ) × t j+1 -t j
Bounded computing capacity. The computing capacity of a node should not be exceeded on any time-interval:

(8) ∀1 ≤ j ≤ 2n -1, ∀1 ≤ u ≤ p, n k=1 ρ (k) u (t j , t j+1 ) w (k) s (k) u ≤ 1.
Bounded link capacity. The bandwidth of each link should not be exceeded:

(9) ∀1 ≤ j ≤ 2n -1, ∀1 ≤ u ≤ p, n k=1 ρ (k) M →u (t j , t j+1 ) δ (k) b u ≤ 1.
Limited sending capacity of master. The total outgoing bandwidth of the master should not be exceeded:

(10) ∀1 ≤ j ≤ 2n -1, p u=1 n k=1 ρ (k) M →u (t j , t j+1 ) δ (k) BW ≤ 1.
Non-negative throughputs.

(11) ∀1 ≤ u ≤ p, ∀1 ≤ k ≤ n, ∀1 ≤ j ≤ 2n -1, ρ (k)
M →u (t j , t j+1 ) ≥ 0 and ρ (k) u (t j , t j+1 ) ≥ 0.

We obtain a convex polyhedron (K) defined by the previous constraints. The problem turns now into checking whether the polyhedron is empty and, if not, into finding a point in the polyhedron. 7), ( 5), ( 6), ( 4), ( 8), ( 9), ( 10) and (11)

(K) ρ (k) M →u (t j , t j+1 ), ρ (k) u (t j , t j+1 ), ∀k, u, j such that 1 ≤ k ≤ n, 1 ≤ u ≤ p, 1 ≤ j ≤ 2n -1 under the constraints (3), (

Number of tasks processed

At first sight, it may seem surprising that in this set of linear constraints, we do not have an equation establishing that all tasks of a given application are eventually processed. Indeed, such a constraint can be derived from the constraints related to the number of tasks sent from the master and the size of buffers. Consider the constraints on task conservation INRIA (Equation ( 7)) on a given processor P u , and for a given application A k ; these equations can be written:

∀1 ≤ j ≤ 2n -1, B (k) u (t j+1 ) -B (k) u (t j ) = ρ (k) M →u (t j , t j+1 ) -ρ (k) u (t j , t j+1 ) × t j+1 -t j .
If we sum all these constraints for all time-interval bounds between t start = r (k) and t stop = d (k) , we obtain:

B (k) u (t stop )-B (k) u (t start ) = [tj , tj+1] tj ≥ r (k) tj+1 ≤ d (k) ρ (k) M →u (t j , t j+1 )× t j+1 -t j - [tj , tj+1] tj ≥ r (k) tj+1 ≤ d (k) ρ (k) u (t j , t j+1 )× t j+1 -t j
Thanks to constraints ( 5) and ( 6), we know that

B (k) u (t start ) = 0 and B (k)
u (t stop ) = 0. So the overall number of tasks sent to a processor P u is equal to the total number of tasks computed:

[tj , tj+1] tj ≥ r (k) tj+1 ≤ d (k) ρ (k) M →u (t j , t j+1 ) × t j+1 -t j = [tj , tj+1] tj ≥ r (k) tj+1 ≤ d (k) ρ (k) u (t j , t j+1 ) × t j+1 -t j
This is true for all processors, and constraints (3) tells us that the total number of tasks sent for application A k is Π (k) , so:

p u=1 [tj , tj+1] tj ≥ r (k) tj+1 ≤ d (k) ρ (k) u (t j , t j+1 ) × t j+1 -t j = Π (k)
Therefore in any solution in Polyhedron (K), all tasks of each application are processed.

Bounding the buffer size

The size of the buffers could also be bounded by adding constraints:

∀1 ≤ u ≤ p, ∀1 ≤ j ≤ 2n, n k=1 B (k) u (t j )δ (k) ≤ M u
where M u is the size of the memory available on node P u . We bound the needed memory only at time-interval bounds, but the above argument can be used to prove that the buffer size on P u never exceeds M u . We choose not to include this constraint in our basic set of constraints, as this buffer size limitation only applies to the fluid model. Indeed, we have earlier proven that limiting the buffer size for independent tasks scheduling leads to NP-complete problems [START_REF] Beaumont | Independent and divisible tasks scheduling on heterogeneous star-schaped platforms with limited memory[END_REF].

Equivalence between non-emptiness of Polyhedron (K) and achievable stretch

Finding a point in Polyhedron (K) allows to determine whether the candidate value for the stretch is feasible. Depending on whether Polyhedron (K) is empty, the binary search will be continued with a larger or smaller stretch value:

If the polyhedron is not empty, then there exists a schedule achieving stretch S. S becomes the upper bound of the binary search interval and the search proceeds.

On the contrary, if the polyhedron is empty, then it is not possible to achieve S. S becomes the lower bound of the binary search.

This binary search and its proof are described below. For now, we concentrate on proving that the polyhedron is not empty if and only if the stretch S is achievable.

Note that the previous study assumes a fluid framework, with flexible computing and communicating rates. This is particularly convenient for the totally fluid model (BMP-FC-SS) and we prove below that the algorithm computes the optimal stretch under this model. The strength of our method is that this study is also valid for the other models. The results are slightly different, leading to asymptotic optimality results and the proofs detailed below are slightly more involved. However, this technique allows to approach optimality. Theorem 1. Under the totally fluid model, Polyhedron (K) is not empty if and only if there exists a schedule with stretch S.

In practice, to know if the polyhedron is empty or to obtain a point in (K), we can use classical tools for linear programs, just by adding a fictitious linear objective function to our set of constraints. Some solvers allow the user to limit the number of refinement steps once a point is found in the polyhedron; this could be helpful to reduce the running time of the scheduler.

Proof. ⇒ Assume that the polyhedron is not empty, and consider a point in (K), given by the values of the ρ (k) M →u (t j , t j+1 ) and ρ (k) u (t j , t j+1 ). We construct a schedule which obeys exactly these values. During time-interval [t j , t j+1 ], the master sends tasks of application A k to processor P u with rate ρ (k) M →u (t j , t j+1 ), and this processor computes these tasks at a rate ρ (k) u (t j , t j+1 ). To prove that this schedule is valid under the fluid model, and that it has the expected stretch, we define ρ (k) M →u (t) as the instantaneous communication rate, and ρ (k) u (t) as the instantaneous computation rate. Then the (fractional) number of tasks of

A k sent to P u in interval [0, T ] is T 0 ρ (k) M →u (t)dt
With the same argument as in the previous remark, applied on interval [0, T ], we have

B (k) u (T ) = T 0 ρ (k) M →u (t)dt - T 0 ρ (k) u (t)dt INRIA
Since the buffer size is positive for all t j and evolves linearly in each interval [t j , t j+1 ], it is not possible that a buffer has a negative size, so

T 0 ρ (k) u (t)dt ≤ T 0 ρ (k) M →u (t)dt
Hence data is always received before being processed.

With the constraints of Polyhedron (K), it is easy to check that no processor or no link is over-utilized and the outgoing capacity of the master is never exceeded. All the deadlines computed for stretch S are satisfied by construction, so this schedule achieves stretch S.

⇐ Now we prove that if there exists a schedule S 1 with stretch S, Polyhedron (K) is not empty. We consider such a schedule, and we call ρ

(k) M →u (t) (and ρ (k) u (t)
) the communication (and computation) rate in this schedule for tasks of application A k on processor P u at time t. We compute as follows the average values for communication and computation rates during time interval [t j , t j+1 ]:

ρ (k) M →u (t j , t j+1 ) = tj+1 tj ρ (k) M →u (t)dt t j+1 -t j and ρ (k) u (t j , t j+1 ) = tj+1 tj ρ (k) u (t)dt t j+1 -t j .
In this schedule, all tasks of application A k are sent by the master, so

d (k) r (k) ρ (k) M →u (t)dt = Π (k) .
With the previous definitions, Equation ( 3) is satisfied. Along the same line, we can prove that the task conservation constraints (Equation ( 7)) are satisfied. Constraints on buffers (Equations 5, 6 and 4) are necessarily satisfied by the size of the buffer in schedule S 1 since it is feasible. Similarly, we can check that the constraints on capacities are verified.

Binary search

To find the optimal stretch, we perform a binary search using the emptiness of Polyhedron (K) to determine whether it is possible to achieve the current stretch.

The initial upper bound for this binary search is computed using a naive schedule where all applications are computed sequentially. For the sake of simplicity, we consider that all applications are released at time 0 and terminate simultaneously. This is clearly a worst case scenario. We recall that the throughput for a single application on the whole platform can be computed as:

ρ * (k) = min BW δ (k) , p u=1 min s (k) u w (k) , b u δ (k)
Then the execution time for application A k is simply Π (k) /ρ * (k) . We consider that all applications terminate at time k Π (k) /ρ * (k) , so that the worst stretch is

S max = max k Π (k) /ρ * (k) k Π (k) /ρ * (k) .
The lower bound on the achievable stretch is 1. Determining the termination criterion of the binary search, that is the minimum gap between two possible stretches, is quite involved, and not very useful in practice. We focus here on the case where this precision is given by the user. Please refer to Section 3.4 for a low-complexity technique (a binary search among stretch-intervals) to compute the optimal maximum stretch.

Algorithm 1: Binary search begin S inf ← 1 S sup ← S max while S sup -S inf > do S ← (S sup + S inf )/2 if Polyhedron (K) is empty then S inf ← S else S sup ← S
return S sup end Suppose that we are given > 0. The binary search is conducted using Algorithm 1. This algorithm allows us to approach the optimal stretch, as stated by the following theorem.

Theorem 2. For any > 0, Algorithm 1 computes a stretch S such that there exists a schedule achieving S and S ≤ S opt + , where S opt is the optimal stretch. The complexity of Algorithm 1 is O(log Smax ).

Proof. We prove that at each step, the optimal stretch is contained in the interval [S inf , S sup ] and S sup is achievable. This is obvious at the beginning. At each step, we consider the set of constraints for a stretch S in the interval. If the corresponding polyhedron is empty, Theorem 1 tells us that stretch S is not achievable, so the optimal stretch is greater than S. If the polyhedron is not empty, there exists a schedule achieving this stretch, thus the optimal stretch is smaller than S.

The size of the work interval is divided by 2 at each step, and we stop when this size is smaller than . Thus the number of steps is O(log Smax ). At the end, S opt ∈ [S inf , S sup ] with S sup -S inf ≤ , so that S sup ≤ S opt + , and S sup is achievable.

INRIA

Property of the one-dimensional load-balancing schedule

Before showing how to extend the previous result to more complex platform models, we introduce a tool that will prove helpful for the proofs: the one-dimensional load-balancing schedule and its properties.

A significant part of this paper is devoted to comparing results under different models. One of the major differences between these models is whether they allow -or not-preemption and time-sharing. On the one hand, we study "fluid" models, where a resource (processor or communication link) can be simultaneously used by several tasks, provided that the total utilization rate is below one. On the other hand, we also study "atomic" models, where a resource can be devoted to only one task, which cannot be preempted: once a task is started on a given resource, this resource cannot perform other tasks before the first one is completed. In this section, we show how to construct a schedule without preemption from fluid schedules, in a way that keeps the interesting properties of the original schedule. Namely, we aim at constructing atomic-model schedules in which tasks terminate not later, or start not earlier, than in the original fluid schedule.

We consider a general case of n applications A 1 , . . . , A n to be scheduled on the same resource, typically a given processor, and we denote by t k the time needed to process one task of application A k at full speed. We start from a fluid schedule S fluid where each application A k is processed at a rate of α k tasks per time-units, such that @ "@ @ "@ @ "@ @ "@ @ "@ @ "@ @ "@ A "A From S fluid , we build an atomic-model schedule S 1D using a one-dimensional loadbalancing algorithm [START_REF] Boulet | Static tiling for heterogeneous computing platforms[END_REF][START_REF] Beaumont | A proposal for a heterogeneous cluster ScaLAPACK (dense linear solvers)[END_REF]: at any time step, if n k is the number of tasks of application A k that have already been scheduled, the next task to be scheduled is the one which minimizes the quantity (n k +1)×t k α k . Figure 2(b) illustrates the schedule obtained. We now prove that this schedule has the nice property that a task is not processed later in S 1D than in S fluid . Lemma 1. In the schedule S 1D , a task T does not terminate later than in S fluid .

n k=1 α k ≤ 1. Figure 2(a) illustrates such a schedule. ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ ¡¢ £ ¡£ ¡£ ¡£ ¡£ ¡£ £ ¡£ ¡£ ¡£ ¡£ ¡£ £ ¡£ ¡£ ¡£ ¡£ ¡£ £ ¡£ ¡£ ¡£ ¡£ ¡£ ¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¤ ¡¤ ¡¤ ¡¤ ¡¤ ¡¤ ¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¡¥ ¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ ¡¦ § ¡ § ¡ § ¡ § ¡ § ¡ § § ¡ § ¡ § ¡ § ¡ § ¡ § § ¡ § ¡ § ¡ § ¡ § ¡ § § ¡ § ¡ § ¡ § ¡ § ¡ § ¡¡¡¡¡¡ ¡¡¡¡¡ ¡¡¡¡¡ ¡¡¡¡¨© ¡© ¡© ¡© ¡© ¡© © ¡© ¡© ¡© ¡© ¡© © ¡© ¡© ¡© ¡© ¡© © ¡© ¡© ¡© ¡© ¡© ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ! "! "! "! ! "! "! "! # "# "# "# # "# "# "# $ "$ "$ "$ $ "$ "$ "$ % "% "% "% % "% "% "% & "& "& "& & "& "& "& ' "' "' "' ' "' "' "' ( "( "( "( ( "( "( "( ) ") ") ") ) ") ") ") 0 "0 "0 "0 0 "0 "0 "0 1 "1 "1 "1 1 "1 "1 "1 time T i (a) fluid schedule S fluid 2 "2 "2 2 "2 "2 2 "2 "2 2 "2 "2 2 "2 "2 2 "2 "2 2 "2 "2 3 "3 3 "3 3 "3 3 "3 3 "3 3 "3 3 "3 4 ¡4 ¡4 4 ¡4 ¡4 4 ¡4 ¡4 4 ¡4 ¡4 4 ¡4 ¡4 4 ¡4 ¡4 4 ¡4 ¡4 4 ¡4 ¡4 4 ¡4 ¡4 4 ¡4 ¡4 4 ¡4 ¡4 4 ¡4 ¡4 4 ¡4 ¡4 5 ¡5 ¡5 5 ¡5 ¡5 5 ¡5 ¡5 5 ¡5 ¡5 5 ¡5 ¡5 5 ¡5 ¡5 5 ¡5 ¡5 5 ¡5 ¡5 5 ¡5 ¡5 5 ¡5 ¡5 5 ¡5 ¡5 5 ¡5 ¡5 5 ¡5 ¡5 6 ¡6 ¡6 ¡6 6 ¡6 ¡6 ¡6 6 ¡6 ¡6 ¡6 6 ¡6 ¡6 ¡6 6 ¡6 ¡6 ¡6 6 ¡6 ¡6 ¡6 6 ¡6 ¡6 ¡6 7 ¡7 ¡7 ¡7 7 ¡7 ¡7 ¡7 7 ¡7 ¡7 ¡7 7 ¡7 ¡7 ¡7 7 ¡7 ¡7 ¡7 7 ¡7 ¡7 ¡7
A "A A "A A "A A "A A "A A "A B ¡B ¡B B ¡B ¡B B ¡B ¡B B ¡B ¡B B ¡B ¡B B ¡B ¡B B ¡B ¡B B ¡B ¡B B ¡B ¡B B ¡B ¡B B ¡B ¡B B ¡B ¡B B ¡B ¡B C ¡C C ¡C C ¡C C ¡C C ¡C C ¡C C ¡C C ¡C C ¡C C ¡C C ¡C C ¡C C ¡C D ¡D ¡D ¡D ¡D D ¡D ¡D ¡D ¡D D ¡D ¡D ¡D ¡D D ¡D ¡D ¡D ¡D D ¡D ¡D ¡D ¡D D ¡D ¡D ¡D ¡D D ¡D ¡D ¡D ¡D E ¡E ¡E ¡E E ¡E ¡E ¡E E ¡E ¡E ¡E E ¡E ¡E ¡E E ¡E ¡E ¡E E ¡E ¡E ¡E E ¡E ¡E ¡E F ¡F ¡F F ¡F ¡F F ¡F ¡F F ¡F ¡F F ¡F ¡F F ¡F ¡F F ¡F ¡F F ¡F ¡F F ¡F ¡F F ¡F ¡F F ¡F ¡F F ¡F ¡F F ¡F ¡F G ¡G G ¡G G ¡G G ¡G G ¡G G ¡G G ¡G G ¡G G ¡G G ¡G G ¡G G ¡G G ¡G H "H "H H "H "H H "H "H H "H "H H "H "H H "H "H H "H
¡P P ¡P Q ¡Q Q ¡Q Q ¡Q Q ¡Q Q ¡Q Q ¡Q Q ¡Q Q ¡Q Q ¡Q Q ¡Q Q ¡Q Q ¡Q Q ¡Q R "R R "R R "R R "R R "R R "R R "R S "S S "S S "S S "S S "S S "S S "S T ¡T ¡T T ¡T ¡T T ¡T ¡T T ¡T ¡T T ¡T ¡T T ¡T ¡T T ¡T ¡T T ¡T ¡T T ¡T ¡T T ¡T ¡T T ¡T ¡T T ¡T ¡T T ¡T ¡T U ¡U U ¡U U ¡U U ¡U U ¡U U ¡U U ¡U U ¡U U ¡U U ¡U U ¡U U ¡U U ¡U V "V "V V "V "V V "V "V V "V "V V "V "V V "V "V V "V "V W "W "W W "W "W W "W "W W "W "W W "W "W W "W "W W "W "W X ¡X ¡X ¡X ¡X X ¡X ¡X ¡X ¡X X ¡X ¡X ¡X ¡X X ¡X ¡X ¡X ¡X X ¡X ¡X ¡X ¡X X ¡X ¡X ¡X ¡X X ¡X ¡X ¡X ¡X Y ¡Y ¡Y ¡Y Y ¡Y ¡Y ¡Y Y ¡Y ¡Y ¡Y Y ¡Y ¡Y ¡Y Y ¡Y ¡Y ¡Y Y ¡Y ¡Y ¡Y Y ¡Y
Proof. First, we point out that t k /α k is the time needed to process one task of application

A k in S fluid (with rate α k ). So n k ×t k α k
is the time needed to process the first n k tasks of application A k . The scheduling decision which chooses the application minimizing (n k +1)×t k α k RR nb 6401 consists in choosing the task which is not yet scheduled and which terminates first in S fluid . Thus, in S 1D , the tasks are executed in the order of their termination date in S fluid . Note that if several tasks terminate at the very same time in S fluid , then these tasks can be executed in any order in S 1D , and the partial order of their termination date is still observed in S 1D .

T other d fluid T before t ki T before d 1D t ki
Then, consider a task T i of a given application A ki , its termination date d fluid in S fluid , and its termination date d 1D in S 1D . We call S before the set of tasks which are executed before T i in S 1D . Because S 1D executes the tasks in the order of their termination date in S fluid , S before is made of tasks which are completed before T i in S fluid , and possibly some tasks completed at the same time as T i (at time d fluid ). We denote by T before the time needed to process the tasks in S before .

In S 1D , we have d 1D = T before + t ki whereas in S fluid , we have d fluid = T before + t ki + T other where T other is the time spent processing tasks from other application than A k and which are not completed at time d fluid , or tasks completing at time d fluid and scheduled later than

T i in S 1D . Since T other ≥ 0, we have d 1D ≤ d fluid .
The previous property is useful when we want to construct an atomic-model schedule, that is a schedule without preemption, in which task results are available no later than in a fluid schedule. On the contrary, it can be useful to ensure that no task will start earlier in an atomic-model schedule than in the original fluid schedule. Here is a procedure to construct a schedule with the latter property.

1. We start again from a fluid schedule S fluid , of makespan M . We transform this schedule into a schedule S -1 fluid by reversing the time: a task starting at time d and finishing at time f in S fluid is scheduled to start at time M -f and to terminate at M -d in S -1 fluid , and is processed at the same rate as in S fluid . Note that this is possible since we have no precedence constraints between tasks.

2. Then, we apply the previous one-dimensional load-balancing algorithm on S -1 fluid , leading to the schedule S -1 1D . Thanks to the previous result, we know that a task T does not terminate later in S -1

1D than in S -1 fluid .

3. Finally, we transform S -1 1D by reverting the time one last time: we obtain the schedule S -2 1D . A task starting at time d and finishing at time f in S -1 1D starts at time M -f and finishes at time M -d in S -2

1D . Note that S -1 1D may have a makespan smaller that M (if the resource was not totally used in the original schedule S fluid ). In this case, our INRIA method automatically introduces idle time in the one-dimensional schedule, to avoid that a task is started too early. Lemma 2. A task does not start sooner in S -2 1D than in S fluid . Proof. Consider a task T , call f 1 its termination date in S -1 fluid , and f 2 its termination date in S -1

1D . Thanks to Lemma 1, we know that f 2 ≤ f 1 . By construction of the reverted schedules, the starting date of task T in S fluid is M -f 1 . Similarly, its starting date in S -2 1D is M -f 2 and we have M -f 2 ≥ M -f 1 .

Quasi-optimality for more realistic models

In this section, we explain how the previous optimality result can be adapted to the other models presented in Section 2.1.3. As expected, the more realistic the model, the less tight the optimality guaranty. Fortunately, we are always able to reach asymptotic optimality: our schedules get closer to the optimal as the number of tasks per application increases.

We describe the delay induced by each model in comparison to the fluid model: starting from a schedule optimal under the fluid model (BMP-FC-SS), we try to build a schedule with comparable performance under a more constrained scenario.

In the following, we consider a schedule S 1 , with stretch S, valid under the totally fluid model (BMP-FC-SS). For the sake of simplicity, we consider that this schedule has been built from a point in Polyhedron (K) as explained in the previous section: the computation and communication rates (ρ

(k) u (t j , t j+1 ) and ρ (k)
M →u (t j , t j+1 )) are constant during each interval, and are defined by the coordinates of the point in Polyhedron (K).

We assess the delay induced by each model. Given the stretch S, we can compute a deadline d (k) for each application A k . By moving to more constrained models, we will not be able to ensure that the finishing time M S (k) is smaller than d (k) . We call lateness for application A k the quantity max{0, M S (k) -d (k) }, that is the time between the due date of an application and its real termination. Once we have computed the maximum lateness for each model, we show how to obtain asymptotic optimality in Section 3.3.3.

Without simultaneous start: the BMP-FC model

We consider here the BMP-FC model, which differs from the previous model only by the fact that a task cannot start before it has been totally received by a processor. Theorem 3. From schedule S 1 , we can build a schedule S 2 obeying the BMP-FC model where the maximum lateness for each application is max

1≤u≤p n k=1 w (k) s (k) u .
Proof. From the schedule S 1 , valid under the fluid model (BMP-FC-SS), we aim at building S 2 with a similar stretch where the execution of a task cannot start before the end of the corresponding communication. We first build a schedule as follows, for each processor P u (1 ≤ u ≤ p):

1. Communications to P u are the same as in S 1 ; 2. By comparison to S 1 , the computations on P u are shifted for each application A k : the computation of the first task of A k is not really performed (P u is kept idle instead of computing this task), and we replace the computation of task i by the computation of task i -1. Because of the shift of the computations, the last task of application A k is not executed in this schedule at time d (k) . We complete the construction of S 2 by adding some delay after deadline d (k) to process this last task of application A k at full speed, which takes a time

w (k) s (k) u
. All the following computations on processor P u (in the next time-intervals) are shifted by this delay.

The lateness for any application A k on processor P u is at most the sum of the delays for all applications on this processor,

n k=1 w (k) s (k) u
, and the total lateness of A k is bounded by the maximum lateness between all processors:

lateness (k) ≤ max 1≤u≤p n k=1 w (k) s (k) u
An example of such a schedule S 2 is shown on Figure 3 (on a single processor).

Atomic execution of tasks: the BMP-AC model

We now move to the BMP-AC model, where a given processor cannot compute several tasks in parallel, and the execution of a task cannot be preempted: a started task must be completed before any other task can be processed.

INRIA

Theorem 4. From schedule S 1 , we can build a schedule S 3 obeying the BMP-AC model where the maximum lateness for each application is

max 1≤u≤p 2n × n k=1 w (k) s (k) u .
Proof. Starting from a schedule S 1 valid under the fluid model (BMP-FC-SS), we want to build S 3 , valid in BMP-AC. We take here advantage of the properties described in Section 3.2 of one-dimensional load-balancing schedules, and especially of S -2 1D . Schedule S 3 is built as follows:

1. Communications are kept unchanged; 2. We consider the computations taking place in S 1 on processor P u during time-interval [t j , t j+1 ]. A rational number of tasks of each application may be involved in the fluid schedule. We first compute the integer number of tasks of application A k to be computed in S 3 :

n u,j,k = ρ (k) u (t j , t j+1 ) × (t j+1 -t j )
. The first n u,j,k tasks of A k scheduled in time-interval [t j , t j+1 ] on P u are organized using the transformation to build S -2

1D in Section 3.2. 3. Then, the computations are shifted as for S 2 : for each application A k , the computation of the first task of A k is not really performed (the processor is kept idle instead of computing this task), and we replace the computation of task i by the computation of task i -1. Lemma 2 proves that, during time-interval [t j , t j+1 ], on processor P u , a computation does not start earlier in S 3 than in S 1 . As S 1 obeys the totally fluid model (BMP-FC-SS), a computation of S 1 does not start earlier than the corresponding communication, so a computation of task i of application A k in S 1 does not start earlier than the finish time of the communication for task i -1 of A k . Together with the shifting of the computations, this proves that in S 3 , the computation of a task does not start earlier than the end of the corresponding communication, on each processor.

Because of the rounding down to the closest integer, on each processor P u , at each timeinterval, S 3 computes at most one task less than S 1 of application A k . Moreover, one more task computation of application A k is not performed in S 3 due to the computation shift. On the whole, as there are at most 2n -1 time-intervals, at most 2n tasks of A k remain to be computed on P u at time d (k) . The delay for application A k is:

lateness (k) ≤ max 1≤u≤p 2n × n k=1 × w (k) s (k) u
. This is obviously not the most efficient way to construct a schedule for the BMP-AC model: in particular, each processor is idle during each interval (because of the rounding down). It would certainly be more efficient to sometimes start a task even if it cannot be terminated before the end of the interval. This is why for our experiments, we implemented on each worker a greedy schedule with Earliest Deadline First Policy instead of this complex construction. However, we can easily prove that this construction has an asymptotic optimal stretch, unlike other greedy strategies.

Asymptotic optimality

In this section, we show that the previous schedules are close to the optimal, when applications are composed of a large number of tasks. To establish such an asymptotic optimality, we have to prove that the gap computed above gets smaller when the number of tasks gets larger. At first sight, we would have to study the limit of the application stretch when Π (k) is large for each application. However, if we simply increase the number of tasks in each application without changing the release dates and the tasks characteristics, then the problem will look totally different: any schedule will run for a very long time, and the time separating the release dates will be negligible in front of the whole duration of the schedule. This behavior is not meaningful for our study.

To study the asymptotic behavior of the system, we rather change the granularity of the tasks: we show that when applications are composed of a large number of small-size tasks, then the maximal stretch is close to the optimal one obtained with the fluid model. To take into account the application characteristics, we introduce the granularity g, and we redefine the application characteristics with this new variable:

Π (k) g = Π (k) g , w (k) g = g × w (k) and δ (k) g = g × δ (k) .
When g = 1, we get back to the previous case. When g < 1, there are more tasks but they have smaller communication and computation size. For any g, the total communication and computation amount per application is kept the same, thus it is meaningful to consider the original release dates.

Our goal is to study the case g → 0. Note that under the totally fluid model (BMP-FC-SS), the granularity has no impact on the performance (or the stretch). Indeed, the fluid model can be seen as the extreme case where g = 0. The optimal stretch under the BMP-FC-SS S opt does not depend on g. Theorem 5. When the granularity is small, the schedule constructed above for the BMP-FC (respectively BMP-AC) model is asymptotically optimal for the maximum stretch, that is

lim g→0 S = S opt
where S is the stretch of the BMP-FC (resp. BMP-AC) schedule, and S opt the stretch of the optimal fluid schedule.

Proof. The lateness of the applications computed in Section 3.3.1 for the BMP-FC model, and in Section 3.3.2 for the BMP-AC model, becomes smaller when the granularity increase:

INRIA

for the BMP-FC model, we have

lateness (k) ≤ max 1≤u≤p n k=1 w (k) g s (k) u ----→ g→0 0.
Similarly, for the BMP-AC model,

lateness (k) ≤ max 1≤u≤p 2n × n k=1 w (k) g s (k) u ----→ g→0 0.
Thus, when g gets close to 0, the stretch obtained by these schedules is close to S opt .

One-port model

In this section, we explain how to modify the previous study to cope with the one-port model. We cannot simply extend the result obtained for the fluid model to the one-port model (as we have done for the other models) since the parameters for modeling communications are not the same. Actually, the one-port model limits the time spent by a processor (here the master) to send data whereas the multiport model limits its bandwidth capacity. Thus, we have to modify the corresponding constraints. Constraint ( 10) is replaced by the following one.

(10-b) ∀1 ≤ j ≤ 2n -1, p u=1 n k=1 ρ (k) M →u (t j , t j+1 ) δ (k) b u ≤ 1
Note that the only difference with Constraint (10) is that, now, we bound the time needed by the master to send all data instead of the volume of the data itself. The set of constraints corresponding to the scheduling problem under the one-port model, for a maximum stretch S, are gathered by the definition of Polyhedron (K 1 ):

(K 1 ) ρ (k)
M →u (t j , t j+1 ), ρ (k) u (t j , t j+1 ), ∀k, u, j such that 1 ≤ k ≤ n, 1 ≤ u ≤ p, 1 ≤ j ≤ 2n -1 under the constraints (3), ( 7), ( 5), ( 6), ( 4), ( 8), ( 9), (10-b), and [START_REF] Beaumont | Steady-state scheduling on heterogeneous clusters[END_REF] As previously, the existence of a point in the polyhedron is linked to the existence of a schedule with stretch S. However, we have no fluid model which could perfectly follow the behavior of the linear constraints. Thus we only target asymptotic optimality. Proof. (a) To prove the first part of the theorem, we prove that for any schedule with stretch S 1 , we can construct a point in Polyhedron (K 1 ). Given such a schedule, we denote by A

M →u (t j , t j+1 ) the total number of tasks of application A k sent by the master to processor P u during interval [t j , t j+1 ]. Note that this may be a rational number if there are ongoing transfers at times t j and/or t j+1 . Similarly, we denote by A (k) u (t j , t j+1 ) the total (rational) number of tasks of A k processed by P u during interval [t j , t j+1 ]. Then we compute:

ρ (k) M →u (t j , t j+1 ) = A (k) M →u (t j , t j+1 ) t j+1 -t j and ρ (k) u (t j , t j+1 ) = A (k) u (t j , t j+1 ) t j+1 -t j .
As in the fluid case, we can also compute the state of the buffers based on these quantities:

B (k) u (t j ) = ti+1≤tj A (k) M →u (t i , t i+1 ) -A (k) u (t i , t i+1 )
We can easily check that all constraints (3),( 4), ( 5), ( 6), ( 7), ( 8), [START_REF] Beaumont | Bandwidth-centric allocation of independent tasks on heterogeneous platforms[END_REF], and (10-b) are satisfied. Variables

B (k) u (t j ), ρ (k)
M →u (t j , t j+1 ), and ρ (b) From a point in Polyhedron (K 1 ), we build a schedule which is asymptotically optimal, as defined in Section 3.3.3. During each interval [t j , t j+1 ], for each worker P u , we proceed as follows.

1. We first consider a fluid-model schedule S f following exactly the rates defined by the point in the polyhedron: the tasks of application A k are sent with rate ρ

(k)

M →u (t j , t j+1 ) and processed at rate ρ (k) u (t j , t j+1 ). 2. We transform both the communication schedule and the computation schedule using one-dimensional load-balancing algorithms. We first compute the integer number of tasks that can be sent in the one-port schedule:

n comm u,j,k = ρ (k)
M →u (t j , t j+1 ) × (t j+1 -t j ) . The number of tasks that can be computed on P u in this time-interval is bounded both by the number of tasks processed in the fluid-model schedule, and by the number of tasks received during this time-interval plus the number of remaining tasks:

n comp u,j,k = min ρ (k) u (t j , t j+1 ) × (t j+1 -t j ) , n comm u,j,k + j-1 i=1 n comm u,i,k -n comp u,i,k

INRIA

The first n comm u,j,k tasks sent in schedule S f are organized with the one-dimensional load-balancing algorithm into S 1D , while the last n comp u,j,k tasks executed in schedule S f are organized with the inverse one-dimensional load-balancing algorithm S -2 1D (see Section 3.2). 3. Then, the computations are shifted: for each application A k , the computation of the first task of A k is not really performed (the processor is kept idle instead of computing this task), and we replace the computation of task i by the computation of task i -1.

The proof of the validity of the obtained schedule is very similar to the proof of Theorem 4 for the BMP-AC model: we use the fact that a task does not start earlier in S -2 1D than in S f , and no later in S 1D than in S f to prove that the data needed for the execution of a given task are received in time.

At time d (k) , some tasks of application A k are still not processed, and some may even not be received yet. Let us denote by L k the number of time-intervals between r (k) and d (k) , that is time-intervals where tasks of application A k may be processed (L k ≤ 2n -1). Because of the rounding of the numbers of tasks sent, at most one task is not transmitted in each interval, for each application. At time d (k) , we thus have at most L k tasks of application A k to be sent to each processor P u . We have to serialize the sending operations, which takes a time at most

n u=1 L k × δ (k) b u
Then, the number of tasks remaining to be processed on processor P u is upper bounded by 2L k + 1: at most L k are received late because of the rounding of the number of tasks received, at most L k tasks are received but not computed because we also round the number of tasks processed, and one more task may also remain because of the computation shift. The computation (at full speed) of all these tasks takes at most a time (2L k + 1) w (k) s (k) u on processor P u . Overall, the delay induced on all processors for finishing application A k can be bounded by:

n u=1 L k × δ (k) b u + max 1≤u≤p (2L k + 1) × w (k) s (k) u .
As L k ≤ 2n -1, the lateness of any application A k is thus:

lateness (k) ≤ k n u=1 (2n -1) × δ (k) b u + max 1≤u≤p (4n -1) × w (k) s (k) u .
As in the proof of Theorem 5, when the granularity becomes small, the stretch of the obtained schedule becomes as close to S 2 as we want.

Binary search with stretch-intervals

In this section, we present another method to compute the optimal stretch in the offline case. This method is based on a linear program built from the constraints of the convex polyhedron (K) with the minimization of the stretch as objective. To do this, we need that other parameters (especially the deadlines) are functions of the stretch. We recall that the deadlines of the applications are computed from their release date and the targeted stretch S: When S is such a critical value, some release dates and deadlines have the same values; When S varies between two such critical values, i.e., when S a < S < S a+1 , then the ordering of the release dates and the deadlines is preserved.

d (k) = r (k) + S × M S * (k) . d 1 d 3 t r 3 r 2 r 1 S d 2 S4 S3 S2 S1 = 1 S5
To simplify our notations, we add two artificial critical values corresponding to the natural bound of the stretch: S 1 = 1 and S m = ∞.

Our goal is to find the optimal stretch by slicing the stretch space into a number of intervals. Within each interval defined by the critical values, the deadlines are linear functions of the stretch. We first show how to find the best stretch within a given interval using a single linear program, and then how to explore the set of intervals with a binary search, so as to find the one containing the optimal stretch.

Within a stretch-interval

In the following, we work on one stretch-interval, called [S a , S b ]. For all values of S in this interval, the release dates r (k) and deadlines d (k) are in a given order, independent of the value of S. As previously, we note {t j } j=1...2n = {r (k) , d (k) }, with t j ≤ t j+1 . As the values of the t j may change when S varies, we write t j = α j S + β j . This notation is general enough for all r (k) and d (k) : If t j = r (k) , then α j = 0 and β j = r (k) .

If t j = d (k) , then α j = M S * (k) and β j = r (k) .

Note that like previously, some t j might be equal, and especially when the stretch reaches a bound of the stretch-interval (S = S a or S = S b ), that is a critical value. For the sake of simplicity, we do not try to discard the empty time-intervals, to avoid the renumbering of the epochal times.

When we rewrite the constraints defining the convex polyhedron (K) with these new notations, we obtain quadratic constraints instead of linear constraints. To avoid this, we introduce new notations. Instead of considering the instantaneous communication and computation rates, we use the total amount of tasks sent or computed during a given timeinterval. Formally we define A (k) M →u (t j , t j+1 ) to be the fractional number of tasks of application A k sent by the master to processor P u during the time-interval [t j , t j+1 ]. Similarly, we denote by A (k) u (t j , t j+1 ) the fractional number of tasks of application A k computed by processor P u during the time-interval [t j , t j+1 ]. Of course, these quantities are linked to our previous variables. Indeed, we have:

A (k) M →u (t j , t j+1 ) = ρ (k) M →u (t j , t j+1 ) × (t j+1 -t j ) A (k) u (t j , t j+1 ) = ρ (k) u (t j , t j+1 ) × (t j+1 -t j )
with t j+1 -t j = (α j+1 -α j )S + (β j+1 -β j ). We rewrite the set of constraints with these new notations:

Total number of tasks We make sure that all tasks of application A k are sent by the master:

(12) ∀ 1 ≤ k ≤ n, 1≤j≤2n-1 tj ≥ r (k) tj+1 ≤ d (k) p u=1 A (k) M →u (t j , t j+1 ) = Π (k)
Non-negative buffer Each buffer should always have a non-negative size:

(13) ∀ 1 ≤ k ≤ n, ∀1 ≤ u ≤ p, ∀1 ≤ j ≤ 2n, B (k) u (t j ) ≥ 0
Buffer initialization At the beginning of the computation of application A k , all corresponding buffers are empty:

(14) ∀ 1 ≤ k ≤ n, ∀1 ≤ u ≤ p, for t j = r (k) , B (k) u (t j ) = 0
Emptying Buffer After the deadline of application A k , no tasks of this application should remain on any node:

(15) ∀ 1 ≤ k ≤ n, ∀1 ≤ u ≤ p, for t j = d (k) , B (k) u (t j ) = 0
Task conservation During time-interval [t j , t j+1 ], some tasks of application A k are received and some are consumed (computed), which impacts the size of the buffer: ( 16)

∀ 1 ≤ k ≤ n, ∀1 ≤ j ≤ 2n-1, ∀1 ≤ u ≤ p, B (k) u (t j+1 ) = B (k) u (t j )+A (k) M →u (t j , t j+1 )-A (k) u (t j , t j+1 )
Bounded computing capacity The computing capacity of a node should not be exceeded on any time-interval:

(17) ∀1 ≤ j ≤ 2n-1, ∀1 ≤ u ≤ p, n k=1 A (k) u (t j , t j+1 ) w (k) s (k) u ≤ (α j+1 -α j )S +(β j+1 -β j )
Bounded link capacity The bandwidth of each link should not be exceeded: ( 18)

∀1 ≤ j ≤ 2n -1, ∀1 ≤ u ≤ p, n k=1 A (k) M →u (t j , t j+1 ) δ (k) b u ≤ (α j+1 -α j )S + (β j+1 -β j )
Limited sending capacity of master The total outgoing bandwidth of the master should not be exceeded:

(19) ∀1 ≤ j ≤ 2n-1, p u=1 n k=1 A (k) M →u (t j , t j+1 )δ (k) ≤ BW× (α j+1 -α j )S +(β j+1 -β j )
We also add a constraint to bound the objective stretch to be in the targeted stretchinterval:

(20) S a ≤ S ≤ S b
Even if the bounds of the sum on the time-intervals in Equation ( 12) seem to depend on S, the set of intervals involved in the sum does not vary as the order of the t j values is fixed for S a ≤ S ≤ S b . With the objective of minimizing the stretch, we get the following linear program.

INRIA (LP)

Minimize S, under the constraints (12), ( 13), ( 14), ( 15), ( 16), ( 17), ( 18), ( 19), [START_REF] Brucker | Scheduling Algorithms[END_REF] Solving this linear program allows to find the minimum possible stretch in the stretchinterval [S a , S b ]. If the minimum stretch computed by the linear program is S opt > S a , this means that there is not better possible stretch in [S a , S b ], and thus there is no better stretch for all possible values. On the contrary, if S opt = S a , we cannot conclude: S a may be the optimal stretch, or the optimal stretch is smaller than S a . In this case, the binary search is continued with smaller stretch values. At last, if there is no solution to the linear program, then there exists no possible stretch smaller or equal to S b , and the binary search is continued with larger stretch values. This binary search and its proof are described below.

When S a < S opt ≤ S b , we can prove that S opt is the optimal stretch.

Theorem 7. The linear program (LP) finds the optimal stretch provided that the optimal stretch is in ]S a , S b ].

Proof. The proof highly depends on Theorem 1. First, consider an optimal solution of the linear program (LP). We compute

ρ (k) M →u (t j , t j+1 ) = A (k) M →u (t j , t j+1 ) (α j+1 -α j )S + (β j+1 -β j ) and ρ (k) u (t j , t j+1 ) = A (k) u (t j , t j+1 ) (α j+1 -α j )S + (β j+1 -β j )
.

These variables constitute a valid solution of the set of constraints of Theorem 1 for S = S opt . Therefore there exists a schedule achieving stretch S opt . Assume now that there exists a schedule with stretch S such that S a < S < S b . Due to Theorem 1, there exists values for ρ (k) M →u (t j , t j+1 ) and ρ (k) u (t j , t j+1 ) satisfying the corresponding set of constraints for S. Then we compute

A (k) M →u (t j , t j+1 ) = ρ (k) M →u (t j , t j+1 ) × (α j+1 -α j )S + (β j+1 -β j ) A (k) u (t j , t j+1 ) = ρ (k) u (t j , t j+1 ) × (α j+1 -α j )S + (β j+1 -β j ) A (k)
M →u (t j , t j+1 ) and A (k) u (t j , t j+1 ) constitute a solution of the linear program (LP) with objective value S. As the objective value S opt found by the linear program is minimal among all possible solutions, we have S opt ≤ S.

Binary search among stretch intervals

We assume that we have computed the bounds of the stretch intervals: S 1 , . . . , S m . The binary search to reach the optimal stretch works as follows: Theorem 8. Algorithm 2 finds the optimal stretch value in a polynomial number of steps. Proof. This algorithm performs a binary search among the m stretch-intervals. Thus, the number of steps of this search is O(log m) and each step consists in solving a linear program, which can be done in polynomial time.

We prove that the optimal stretch is always contained in the interval [S L , S U ]. This is obviously true in the beginning. On a stretch-interval [S M , S M +1 ], the minimum possible stretch S opt is computed. If S opt > S M , thanks to Theorem 7, we know that S opt is the optimal stretch. If there is no solution, no stretch values in the stretch-interval [S M , S M +1 ] is feasible, so the optimal stretch is in [S M +1 , S U ]. If S opt = S M , then the optimal stretch smaller or equal than S M . Thus, the optimal stretch is still contained in [S M , S M +1 ] after one iteration. If we exit while loop without having return the optimal stretch, then U = L+1 and the optimal stretch is contained in the stretch-interval [S L , S U ]. We compute this value with the linear program and return it.

Online setting

We now move to the study of the online setting. Because we target an online framework, the scheduling policy needs to be modified upon the completion of an application, or upon the arrival of a new one. Resources will be re-assigned to the various applications in order to optimize the objective function. The scheduler is making best use of its partial knowledge of the whole process (we know neither the release date, nor the number of tasks, nor the characteristics of the next application to arrive into the system). The idea is to make use of our study of the offline case. When a new application is released, we recompute the achievable max-stretch using the binary search described in the offline case. However, we INRIA cannot pretend to optimality any longer as we now have only limited information on the applications.

When a new application A knew arrives at time T new = r (knew) , we consider the applications A 0 , . . . , A knew-1 , released before T new .

We call Π

rem the (fractional) number of tasks of application A k remaining at the master at time T new . For the sake of simplicity, we do not consider the applications that are totally processed, and we thus have Π (k) rem = 0 for all applications. For the new application, we have Π (knew) rem = Π (knew) . We also consider as parameters the state B (k) u (t knew ) of the buffers at time T new . We also have B (knew) u (t knew ) = 0 As previously, we compute the optimal max-stretch using Algorithm 1. For a given objective S, we have a convex polyhedron defined by the linear constraints, which is non empty if and only if stretch S is achievable. The constraints are slightly modified in order to fit the online context. First, we recompute the deadlines of the applications: k) . Note that now, all release dates are smaller than T new , and all deadlines are larger than T new .

d (k) = r (k) + S × M S * (
We sort the deadlines by increasing order, and denote by t j the set of orderer deadlines: {t j } = {d (k) }∪{T new } such that t j ≤ t j+1 . The constraints are the same as the ones used for Polyhedron (K), except the constraint on the number of task processed, which is updated to account for the remaining number of tasks to be processed.

As described for the offline setting, a binary search allows to find the optimal max-stretch. Note that this "optimality" concerns only the time interval [T new , +∞], assuming that no other application will be released after T new . This assumption will not hold true in general, hence our schedule will be suboptimal (which is the price to pay without information about future released applications). The stretch achieved for the whole application set is bounded by the maximum of the stretches obtained by the binary search each time a new application is released.

MPI experiments and SimGrid simulations

We have conducted several experiments in order to compare different scheduling strategies, and to show the benefits of the algorithms presented in this work. We first present the heuristics. Then we detail the platforms and applications used for the experiments. Finally, we expose and comment the numerical results.

The code and the experimental results can be downloaded from: http://graal.ens-lyon.fr/~lmarchal/cbs3m/.

Heuristics

In this section, we present strategies that are able to schedule multi-applications in an online setting. Most of these strategies are simple and wait for an application to terminate before scheduling another application. Although far from the optimal in a number of cases, such strategies are representative of existing Grid schedulers.

We compare sixteen algorithms in the experiments. First we outline policies for selecting the set of applications to be executed: FIFO (First In First Out): applications are computed in the order of their release dates.

SPT (Shortest Processing Time): released applications are sorted by non-decreasing processing time (which is approximated by M S * , see Section 2.3). The first application must be completed before we determine the next one to be executed.

SRPT (Shortest Remaining Processing Time): at each release date, released applications are sorted by non-decreasing processing time, according to the tasks that remains to be scheduled, and the applications are fully executed one after the other in this order until a new release date occurs.

SWRPT (Shortest Weighted Remaining Processing Time): it is very similar to SRPT, but the remaining processing time of the released applications are weighted with M S * . In practice, it gives small applications a priority against large applications which are almost finished, which is better in order to minimize the stretch.

The importance and relevance of the above heuristics are outlined in the related work section (Section 5). Next we outline policies for resource selection:

RR (Round-Robin): all workers are selected in a cyclic way.

MCT (Minimum Completion Time): given a task of an application, it selects the worker which will finish this task first, given the current load of the platform.

DD (Demand-Driven): workers are themselves asking for a task to compute as soon as they become idle.

The four application selection policies and the three resource selection rules lead to twelve different greedy algorithms. We also test a more sophisticated algorithm: MWMA (Master Worker Multi-Applications): this algorithm computes on each time interval a steady-state strategy to schedule the available applications, as presented in [START_REF] Beaumont | Centralized versus distributed schedulers for multiple bag-of-task applications[END_REF][START_REF] Beaumont | Centralized versus distributed schedulers for multiple bag-of-task applications[END_REF]. All available applications are running at the same time, and each application is given a different fraction of the platform according to its weight. This weight can be derived from:

the remaining number of tasks of the applications (variant called NBT); the remaining time of computation of the applications (variant called MS).

Both variants are compared in the experiments.

INRIA

Finally, there is the strategy presented in this paper, called CBS3M (Clever Burst Steady-State Stretch Minimization). We test it with two variants, both a FIFO or EDF policy for the workers to choose the next task to compute among those they have received. Both the CBS3M and the MWMA strategies make use of linear programs to compute their schedule. These linear programs are solved using glpk, the Gnu Linear Programming Kit [START_REF]GLPK: GNU Linear Programming Kit[END_REF].

Platforms

In this section, we conduct experiments on a real platform, in order to have an insight of the behavior of the algorithms. We also run multiple simulations, in order to get more results about their performance. For the sake of simplicity, we suppose in this section that the processors are related, which means that the computation time of a task of each set will only depends on the size of the task and of the computation speed of the worker, and not on the applications.

Because our MPI library serializes communications, we use the one-port model for all experiments and simulations: the linear program used for CBS3M is the one adapted for the one-port model (see Section 3.3.4), and we serialize communications both in the MPI program and in the simulations.

Experimental settings

Experiments were conducted on a cluster composed of nine processors. The master is a SuperMicro server 6013PI, with a P4 Xeon 2.4 GHz processor, and the workers are all Su-perMicro servers 5013-GM, with P4 2.4 GHz processors. All nodes have 1 GB of memory and are running Linux. They are connected with a switched 10 Mbps Fast Ethernet network. As this platform may not be as heterogeneous as we would like, we sometimes artificially enhance its heterogeneity by slowing down some communications and/or some computations. In order to artificially slow down a communication link, we send several times the same message to one worker. The same idea works for processor speeds: we ask a worker to compute a given matrix-product several times in order to slow down its computation capability. The experiments are performed using the MPICH-2 communication library [START_REF] Gropp | Mpich2: A new start for mpi implementations[END_REF].

We create ten different fully heterogeneous platforms. The communication and computation slowdowns were uniformly chosen between 1 to 10.

Simulations

An extensive set of simulations is performed using SimGrid [START_REF] Legrand | Scheduling Distributed Applications: The SimGrid Simulation Framework[END_REF]. The parameters of the simulated platforms were kept as close as possible to the actual experimental framework so that simulations can be considered a direct complement of the experimental MPI setting. In a first step, we run the exact same experiments (with the same platform configuration and application scenario) to make sure that our simulation behaves similarly to the MPI experiments. Then, we conducted an extensive set of simulations with larger applications.

Applications

A bag-of-tasks is described by its release date, its number of tasks, and the communication and computation sizes of one task. For our experiments and simulations, we randomly generated the applications, with the following constraints in order to be realistic:

1. the release dates of the applications follow a log-normal distribution as suggested in [START_REF] Feitelson | Workload Characterization and Modeling Book[END_REF]; 2. the total amount of communications and computations for an application is randomly chosen with a log-normal distribution between realistic bounds, and then split into tasks. The parameters used in the generation of the applications for the experiments and the simulations are described in Tables 1 and2 The number of tasks for one application is bounded above by the minimum amount of communication and computation allowed for one task.

Results

In this section we describe the results obtained on all different platforms, experimental or simulated.

Experimental results

We express the performance of any given algorithm on one problem instance as the ratio of the max-stretch obtained by the algorithm on this instance over the theoretical optimal max-stretch obtained by linear programming.

The results of the experiments are shown in Table 3. Figure 5 summarizes the experiments for the best four algorithms, CBS3M using EDF policy, in both the offline and online versions, MWMA NBT and SWRPT. We can see in Table 3 that the four versions of CBS3M achieve a better relative maxstretch than most other strategies. In fact, they all achieve far better performance than any other strategy in all but two experiments. We also see that resource selection is important on heterogeneous platforms, as the algorithms which have the worst relative max-stretch are the ones using round-robin or demand-driven policies. The MWMA algorithms lie in between our algorithms and the greedy strategies, but sometimes they achieve a very bad relative max-stretch (up to 2.98).

On Figure 5, one can clearly see that our algorithms outperform the other algorithms. Surprisingly, the offline version is not always better than the online version. The offline version knows the future and thus should achieve better performance. However, it suffers from discrepancies between the actual characteristics of the platform and those of the platform model. The online version is able to circumvent this problem as it takes into account the work effectively processed to recompute the schedule at each new application arrival. This gain of reactivity compensates for the loss due to the lack of knowledge of the future.

Simulations on experimental platforms

We have run exactly the same experiments with simulations, using the same platform configurations and application scenarios. We compare the difference between the relative maxstretch in both cases. As a result, we found that the average difference on the relative Figure 5: Relative max-stretch of best four heuristics. max-stretch (that is the ratio between the max-stretch obtain by any heuristic and the optimal max-stretch computed by the linear program) is around 21%, with a standard deviation of 57%. These results show that our simulations are generally close to those obtained on a real platform. Indeed, only one scenario has very different executions in the MPI experiment and in the simulation, with a 566% difference. In this case, the slowdown of the processors is not correctly achieved, leading for the SPT scheduler to take a totally different decision. If we discard this execution, the average difference drops down to 16%, with a standard deviation of 14% (and a maximum of 72%).

Simulation results

In this section, we detail the results of the simulations. We run 1000 experiments based on the parameters described in Table 2. Table 4 presents the results of all heuristics for the max-stretch metric, whereas Figure 6 shows the evolution of some heuristics (the best ones) over the load of the scenario. Here the load is characterized with the optimal achievable max-stretch: we consider that a scenario where the optimal max-stretch is 6 is twice as loaded as a scenario with an optimal max-stretch of 3.

The CBS3M heuristics perform very well for the max-stretch: CBS3M EDF ONLINE achieves the optimal max-stretch in 65.2% of the experiments. This heuristic achieves great performance, with an average max-stretch of 1.16 times the optimal max-stretch, and a worst case of 1.93.

INRIA

More surprisingly, CBS3M also gives the best average results for the makespan and the max-flow objectives. With respect to sum-flow, CBS3M gives the best results for lightloaded scenarios, whereas SRPT and SWRPT give better results for high-loaded scenarios. Finally, CBS3M is outperformed by SRPT and SWRPT for sum-stretch.

The good results of the CBS3M heuristics can be explained by the fact that they make very good use of the platform, by scheduling simultaneously several applications when it is possible, for example when the communication medium has still some free bandwidth after scheduling the most critical application. All other heuristics (except MWMA) are limited to scheduling only one application at a time, leading to an overall bad utilization of the computing platform.

Another comment is the relative bad result of the involved strategies MWMA (MWMA NBT and MWMA MS): although they schedule several applications concurrently on the platforms, they use a somewhat wrong computation of the priorities, leading to poor results.

Bags-of-Tasks

Bags-of-tasks are parallel applications whose tasks are all independent. Their study is motivated by problems that are addressed by collaborative computing efforts such as SETI@home [46], factoring large numbers [START_REF] Cowie | A world wide number field sieve factoring record: on to 512 bits[END_REF], the Mersenne prime search [START_REF] Prime | [END_REF], and those distributed computing problems organized by companies such as Entropia [START_REF]Entropia[END_REF]. Bags-of-tasks are well suited for computational grids, because communication can easily become a bottleneck for tightly-coupled parallel applications.

Condor [START_REF] Litzkow | Condor -A hunter of idle workstations[END_REF] and APST [START_REF] Berman | Adaptive computing on the grid using AppLeS[END_REF][START_REF] Casanova | Grid'[END_REF] are among the first projects providing specific support for such applications. Condor was initially conceived for campus-wide networks [START_REF] Litzkow | Condor -A hunter of idle workstations[END_REF], but has been extended to run on grids [START_REF] Frey | Condor-G: A Computation Management Agent for Multi-Institutional Grids[END_REF]. While APST is user-centric and does not handle multiple-applications, Condor is system-centric. Those two projects are designed for standard grids but more recent and active projects like OurGrid [START_REF] Cirne | Running Bag-of-Tasks Applications on Computational Grids: The MyGrid Approach[END_REF] or BOINC [START_REF]Berkeley Open Infrastructure for Network Computing[END_REF] target more distributed architectures like desktop grids. BOINC [START_REF]Berkeley Open Infrastructure for Network Computing[END_REF] is a centralized scheduler that distributes tasks for participating applications, such as SETI@home, ClimatePrediction.NET, and Einstein@Home. The set of resources is thus very large while the set of applications is small and very controlled. OurGrid is a Brazilian project that encourages people to donate their computing resources while maintaining the symmetry between consumers and providers. All these projects generally focus on designing and providing a working infrastructure, and they do not provide any analysis of scheduling techniques suited to such environments.

Steady-State Scheduling

Minimizing the makespan, i.e., the total execution time, is a NP-hard problem in most practical situations [START_REF] Garey | Computers and Intractability, a Guide to the Theory of NP-Completeness[END_REF][START_REF] Shirazi | Scheduling and load balancing in parallel and distributed systems[END_REF][START_REF] Chrétienne | Scheduling Theory and its Applications[END_REF], while it turns out that the optimal steady-state schedule can often be characterized very efficiently, with low-degree polynomial complexity.

The steady-state approach has been pioneered by Bertsimas and Gamarnik [START_REF] Bertsimas | Asymptotically optimal algorithms for job shop scheduling and packet routing[END_REF]. It has been used successfully in many situations [START_REF] Beaumont | Steady-state scheduling on heterogeneous clusters[END_REF]. In particular, steady-state scheduling has been used to schedule independent tasks on heterogeneous tree-overlay networks [START_REF] Beaumont | Bandwidth-centric allocation of independent tasks on heterogeneous platforms[END_REF][START_REF] Banino | Scheduling strategies for master-slave tasking on heterogeneous processor platforms[END_REF]. Bandwidth-centric scheduling is introduced in [START_REF] Beaumont | Bandwidth-centric allocation of independent tasks on heterogeneous platforms[END_REF], and extensive experiments are reported in [START_REF] Kreaseck | Dynamic autonomous scheduling on Heterogeneous Systems[END_REF]. The steady-state approach has also been used by Hong et al. [START_REF] Hong | Distributed adaptive task allocation in heterogeneous computing environments to maximize throughput[END_REF] who extend the work of [START_REF] Beaumont | Bandwidth-centric allocation of independent tasks on heterogeneous platforms[END_REF] to deploy a divisible workload on a heterogeneous platform. However, and to the best of our knowledge, the only reference dealing with steady-state scheduling for several applications is [START_REF] Beaumont | Centralized versus distributed schedulers for multiple bag-of-task applications[END_REF].

Flow-type objective functions and online scheduling

The flow of a task is the time it spends in the system, that is the time elapsed between its release date and its completion time. The stretch of a task is therefore a weighted form of its flow time, where the weight is the inverse of the task running time, if it were alone on the platform. Most of the existing work on stretch minimization deals with the mono-processor case. In fact, there has been a lot of work on the performance of simple list scheduling heuristics for the optimization of flow-like metrics with preemption. We will therefore first consider this work.

Flow optimization. On a single processor, the max-flow is optimized by First-Come First-Serve (FCFS) (see Bender et al. [START_REF] Bender | Flow and stretch metrics for scheduling continuous job streams[END_REF] for example), and the sum-flow is optimized by shortest remaining processing time first (SRPT) [START_REF] Baker | Introduction to Sequencing and Scheduling[END_REF].

Things are more difficult for stretch minimization. First, any online algorithm which has a better competitive ratio for sum-stretch minimization than FCFS is subject to starvation, and is thus not a competitive algorithm for max-stretch minimization [START_REF] Legrand | Minimizing the stretch when scheduling flows of divisible requests[END_REF]. In other words, the two objective functions cannot be optimized simultaneously to obtain a non trivial competitive factor (FCFS is not taking into account the weight of tasks in the objective).

Sum-stretch minimization. The complexity of the offline minimization of the sumstretch with preemption is still an open problem. At the very least, this is a hint at the difficulty of this problem. Bender, Muthukrishnan, and Rajaraman [START_REF] Bender | Approximation algorithms for average stretch scheduling[END_REF] designed a Polynomial Time Approximation Scheme (PTAS) for minimizing the sum-stretch with preemption. Chekuri and Khanna [START_REF] Chekuri | Approximation schemes for preemptive weighted flow time[END_REF] proposed an approximation scheme for the more general sum weighted flow minimization problem. On the online side, no online algorithm has a competitive ratio less than or equal to 1.19484 for the minimization of sum-stretch [START_REF] Legrand | Minimizing the stretch when scheduling flows of biological requests[END_REF][START_REF] Legrand | Minimizing the stretch when scheduling flows of divisible requests[END_REF].

As we recalled, on one processor, SRPT is optimal for minimizing the sum-flow. When SRPT takes a scheduling decision, it only considers the remaining processing time of a task, and not its original processing time, i.e., the weight of the task in the objective function. Nevertheless, Muthukrishnan, Rajaraman, Shaheen, and Gehrke have shown [START_REF] Muthukrishnan | Online scheduling to minimize average stretch[END_REF] that SRPT is 2-competitive for sum-stretch. Another well studied algorithm is the Smith's ratio rule [START_REF] Smith | Various optimizers for single-stage production[END_REF] also known as shortest weighted processing time (SWPT). Whatever the weights, SWPT is 2-competitive [START_REF] Schulz | The power of α-points in preemptive single machine scheduling[END_REF] for the minimization of the sum of weighted completion times. However, SWPT is not an approximation algorithm for minimizing the sum-stretch. Indeed, both SPT (shortest processing time) and SWPT are not competitive algorithms for minimizing the sum-stretch [START_REF] Legrand | Minimizing the stretch when scheduling flows of biological requests[END_REF][START_REF] Legrand | Minimizing the stretch when scheduling flows of divisible requests[END_REF]. To address the weaknesses of both SRPT and SWPT, one might consider a heuristic that takes into account both the original and the remaining processing times of the jobs, which leads to the shortest weighted remaining processing time heuristic (SWRPT). Muthukrishnan, Rajaraman, Shaheen, and Gehrke [START_REF] Muthukrishnan | Online scheduling to minimize average stretch[END_REF] proved that SWRPT is actually optimal when there are only two job sizes. However, in the general case, the worst case for SWRPT for sum-stretch minimization is at least 2, and thus is no better than that of SRPT [START_REF] Legrand | Minimizing the stretch when scheduling flows of biological requests[END_REF][START_REF] Legrand | Minimizing the stretch when scheduling flows of divisible requests[END_REF].

INRIA

Max-stretch minimization. Max-stretch can be optimally minimized in the offline case [START_REF] Legrand | Minimizing the stretch when scheduling flows of biological requests[END_REF][START_REF] Legrand | Minimizing the stretch when scheduling flows of divisible requests[END_REF], even on unrelated machines (either with preemption or in the divisible load framework). The online case is far more difficult. With only two task sizes, SWRPT is optimal, as we have already recalled. However, as soon as there are at least three task sizes, no algorithm as a competitive ration lower than 1 2 ∆ √ 2-1 , where ∆ is the ratio of the largest to the smallest size of tasks [START_REF] Legrand | Minimizing the stretch when scheduling flows of biological requests[END_REF][START_REF] Legrand | Minimizing the stretch when scheduling flows of divisible requests[END_REF].

In fact, this latter work is the only one targeting max stretch minimization in a multiprocessor environment. This work is done in the divisible load framework, meaning that applications can be arbitrarily divided in sub-tasks when, in the context of the current paper, the granularity of the tasks of each application is fixed independently of the scheduler. Furthermore, communications can be neglected for the applications targeted in [START_REF] Legrand | Minimizing the stretch when scheduling flows of biological requests[END_REF][START_REF] Legrand | Minimizing the stretch when scheduling flows of divisible requests[END_REF], when they play a major role in our case.

General online scheduling. More generally, we refer the reader to surveys on online scheduling algorithms [START_REF] Pruhs | Handbook of Scheduling: Algorithms, Models, and Performance Analysis, chapter Online Scheduling[END_REF], on randomized online scheduling algorithms [START_REF] Albers | On randomized online scheduling[END_REF], or even more generally on online algorithms [START_REF] Albers | Online algorithms: a survey[END_REF].

Conclusion

In this paper, we have studied the problem of scheduling multiple applications, made of collections of independent and identical tasks, on a heterogeneous master-worker platform. Applications have different release dates. We aimed at minimizing the maximum stretch, or equivalently at minimizing the largest relative slowdown of each application due to their concurrent execution. We derived an optimal algorithm for the off-line setting (when all application sizes and release dates are known beforehand). We have adapted this algorithm to an online scenario, so that it can react when new applications are released.

We have compared our new algorithms against classical greedy heuristics, and also against some involved static multi-applications strategies. Experiments were run both on a real cluster, using MPI, and through extensive simulations, conducted with SimGrid. Both experimental comparisons show a great improvement when using our CBS3M strategy, which achieves an averaged worse max-stretch only 16% greater than the off-line optimal max-stretch. To the best of our knowledge, this work is the first attempt to provide efficient scheduling techniques for multiple bags-of-tasks in an online scenario.

Future work includes extending the approach to other communication models (such as the one-port model of [START_REF] Sinnen | Communication contention in task scheduling[END_REF]) and to more general platforms (such as multi-level trees). It would also be very interesting to deal with more complex application types, such as pipeline or even general DAGs.

Figure 1 :

 1 Figure 1: A star network.

INRIA

Figure 2 :

 2 Figure 2: Gantt charts for the proof illustrating the one-dimensional load-balancing algorithm.

Figure 3 :

 3 Figure 3: Example of the construction of a schedule S 2 for BMP-FC model from a schedule S 1 for BMP-FC-SS model. We plot only the computing rate. Each box corresponds to the execution of one task.

Theorem 6 .g

 6 (a) If there exists a schedule valid under the one-port model with stretch S 1 , then Polyhedron (K 1 ) is not empty for S 1 .(b) Conversely, if Polyhedron (K 1 ) is not empty for the stretch objective S 2 , then there exists a schedule valid for the problem under the one-port model with parameters Π , as defined in Section 3.3.3, whose stretch S is such that lim g→0 S = S 2 .

u

  (t j , t j+1 ) define a point in Polyhedron (K 1 ).

Figure 4 :

 4 Figure 4: Relation between stretch and deadlines Figure 4 represents the evolution of the deadlines d (k) over the targeted stretch S: each deadline is an affine function in S. For the sake of readability, the time is represented on the x axis, and the stretch on the y axis. Special values of stretches S 1 , S 2 , . . . , S m are represented on the figure. These critical values of the stretch are points where the ordering of the release dates and deadlines of the applications is modified:

INRIA

RR n 6401 Algorithm 2 :

 64012 Binary search among stretch-intervals begin L ← 1 and U ← max while U -L > 1 do M ← L + U 2 Solve the linear program (LP) for interval [S M , S M +1 ] if there is a solution with objective value S opt then if S opt > S M then return S opt else U ← M else L ← M Solve the linear program (LP) for interval [S L , S U ] return the objective value S opt of the solution end

INRIA

Figure 10 :

 10 Figure 10: Evolution of the sum-flow of best heuristics in the simulations under different load conditions.

Table 1 :

 1 . general number of workers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 number of applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 arrival dates mean of the distribution in the log space . . . . . . . . . . . 4.0 standard deviation in the log space . . . . . . . . . . . . . . . . . 1.2 computations maximum amount of work application . . . . . . . . . . . . . . 76.8 Gflops minimum amount of work per task . . . . . . . . . . . . . . . . . 3.1 Gflops communications maximum amount of communication per application 800 MB minimum amount of communication per task . . . . . . . 40 MB number of tasks minimum number of tasks per application . . . . . . . . . . 10 Parameters for the MPI experiments general number of workers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 number of applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 arrival dates mean of the distribution in the log space . . . . . . . . . . . 4.0 standard deviation in the log space . . . . . . . . . . . . . . . . . 1.2 computations maximum amount of work application . . . . . . . . . . . . . . 409 Gflops minimum amount of work per task . . . . . . . . . . . . . . . . . 3.1 Gflops communications maximum amount of communication per application 6 GB minimum amount of communication per task . . . . . . . 40 MB number of tasks minimum number of tasks per application . . . . . . . . . . 10

Table 2 :

 2 Parameters for the SimGrid simulations

Table 3 :

 3 Results of the experiments.

Table 4 :

 4 Max-stretch of all heuristics in the simulations. Evolution of the relative max-stretch of best heuristics in the simulations under different load conditions.

		4
									SRPT_MCT
								SWRPT_MCT
								MWMA_NBT
								CBS3M_EDF_OFFLINE
		3.5						CBS3M_EDF_ONLINE
	average max_stretch / optimal max_stretch	2 2.5 3
		1.5
		1
		4	5	6	7	8	9	10	11	12
					load (optimal stretch)
	Figure 6: INRIA

Table 5 :

 5 Sum-stretch of all heuristics in the simulations. Evolution of the sum-stretch of best heuristics in the simulations under different load conditions.

		2.2
									SRPT_MCT
								SWRPT_MCT
								MWMA_NBT
		2						CBS3M_EDF_OFFLINE CBS3M_EDF_ONLINE
	average sum_stretch / best sum_stretch	1.2 1.4 1.6 1.8
		1
		0.8
		4	5	6	7	8	9	10	11	12
					load (optimal stretch)
	Figure 7:

Table 6 :

 6 Makespan of all heuristics in the simulations. Evolution of the makespan of best heuristics in the simulations under different load conditions.

		1.4
									SRPT_MCT
								SWRPT_MCT
								MWMA_NBT
		1.35					CBS3M_EDF_OFFLINE
								CBS3M_EDF_ONLINE
	average makespan / best makespan	1.1 1.15 1.2 1.25 1.3
		1.05
		1
		4	5	6	7	8	9	10	11	12
					load (optimal stretch)
	Figure 8: INRIA

Table 7 :

 7 Max-flow of all heuristics in the simulations. Evolution of the max-flow of best heuristics in the simulations under different load conditions.

		1.9
									SRPT_MCT
								SWRPT_MCT
		1.8						MWMA_NBT CBS3M_EDF_OFFLINE
								CBS3M_EDF_ONLINE
		1.7
	average max_flow / best max_flow	1.3 1.4 1.5 1.6
		1.2
		1.1
		1
		4	5	6	7	8	9	10	11	12
					load (optimal stretch)
	Figure 9:

Table 8 :

 8 Sum-flow of all heuristics in the simulations.

		1.5
									SRPT_MCT
								SWRPT_MCT
		1.45					MWMA_NBT CBS3M_EDF_OFFLINE
								CBS3M_EDF_ONLINE
		1.4
	average sum_flow / best sum_flow	1.15 1.2 1.25 1.3 1.35
		1.1
		1.05
		1
		4	5	6	7	8	9	10	11	12
					load (optimal stretch)

RR n 6401