Jean-François Pineau
email: jean-francois.pineau@ens-lyon.fr

Yves Robert
email: yves.robert@ens-lyon.fr

Frédéric Vivien
email: frederic.vivien@ens-lyon.fr

The impact of heterogeneity on master-slave on-line scheduling

In this paper, we assess the impact of heterogeneity for scheduling independent tasks on master-slave platforms. We assume a realistic one-port model where the master can communicate with a single slave at any time-step. We target on-line scheduling problems, and we focus on simpler instances where all tasks have the same size. While such problems can be solved in polynomial time on homogeneous platforms, we show that there does not exist any optimal deterministic algorithm for heterogeneous platforms. Whether the source of heterogeneity comes from computation speeds, or from communication bandwidths, or from both, we establish lower bounds on the competitive ratio of any deterministic algorithm. We provide such bounds for the most important objective functions: the minimization of the makespan (or total execution time), the minimization of the maximum response time (difference between completion time and release time), and the minimization of the sum of all response times. Altogether, we obtain nine theorems which nicely assess the impact of heterogeneity on on-line scheduling.

These theoretical contributions are complemented on the practical side by the implementation of several heuristics on a small but fully heterogeneous MPI platform. Our (preliminary) results show the superiority of those heuristics which fully take into account the relative capacity of the communication links.

Introduction

The main objective of this paper is to assess the impact of heterogeneity for scheduling independent tasks on masterslave platforms. We make two important assumptions that render our approach very significant in practice. First we assume that the target platform is operated under the oneport model, where the master can communicate with a single slave at any time-step. This model is much more real-istic than the standard model from the literature, where the number of simultaneous messages involving a processor is not bounded. Second we consider on-line scheduling problems, i.e., problems where release times and sizes of incoming tasks are not known in advance. Such dynamic scheduling problems are more difficult to deal with than their static counterparts (for which all task characteristics are available before the execution begins) but they encompass a broader spectrum of applications.

We endorse the somewhat restrictive hypothesis that all tasks are identical, i.e., that all tasks are equally demanding in terms of communications (volume of data sent by the master to the slave which the task is assigned to) and of computations (number of flops required for the execution). We point out that many important scheduling problems involve large collections, or bags, of identical tasks [START_REF] Casanova | Grid Computing: Making The Global Infrastructure a Reality, chapter Parameter Sweeps on the Grid with APST[END_REF][START_REF] Adler | Optimal sharing of bags of tasks in heterogeneous clusters[END_REF].

Without the hypothesis of having same-size tasks, the impact of heterogeneity is harder to be studied Indeed, scheduling different-size tasks on a homogeneous platform reduced to a master and two identical slaves, without paying any cost for the communications from the master, and without any release time, is already an NP-hard problem [START_REF] Garey | Computers and Intractability, a Guide to the Theory of NP-Completeness[END_REF]. In other words, the simplest (off-line) version is NP-hard on the simplest (two-slave) platform.

On the contrary, scheduling same-size tasks is easy on fully homogeneous platforms. Consider a master-slave platform with m slaves, all with the same communication and computation capacity; consider a set of identical tasks, whose release times are not known in advance. An optimal approach to solve this on-line scheduling problem is the following list-scheduling strategy: process tasks in a FIFO order, according to their release times; send the first unscheduled task to the processor whose ready-time is minimum. Here, the ready-time of a processor is the time at which it has completed the execution of all the tasks that have already been assigned to it. It is striking that this simple strategy is optimal for many classical objective functions, including the minimization of the makespan (or total execu-tion time), the minimization of the maximum response time (difference between completion time and release time), and the minimization of the sum of the response times.

On-line scheduling of same-size tasks on heterogeneous platforms is much more difficult. In this paper, we study the impact of heterogeneity from two sources. First we consider a communication-homogeneous platform, i.e., where communication links are identical: the heterogeneity comes solely from the computations (we assume that the slaves have different speeds). On such platforms, we show that there does not exist any optimal deterministic algorithm for on-line scheduling. This holds true for the previous three objective functions (makespan, maximum response time, sum of response times). We even establish lower bounds on the competitive ratio of any deterministic algorithm. For example, we prove that there exist problem instances where the makespan of any deterministic algorithm is at least 1.25 times larger than that of the optimal schedule. This means that the competitive ratio of any deterministic algorithm is at least 1.25. We prove similar results for the other objective functions.

The second source of heterogeneity is studied with computation-homogeneous platforms, i.e., where computation speeds are identical: the heterogeneity comes solely from the different-speed communication links. In this context, we prove similar results, but with different competitive ratios.

Not surprisingly, when both sources of heterogeneity add up, the complexity goes beyond the worst scenario with a single source. In other words, for fully heterogeneous platforms, we derive competitive ratios that are higher than the maximum of the ratios with a single source of heterogeneity.

The main contributions of this paper are mostly theoretical. However, on the practical side, we have implemented several heuristics on a small but fully heterogeneous MPI platform. Our (preliminary) results show the superiority of those heuristics which fully take into account the relative capacity of the communication links.

The rest of the paper is organized as follows. In Section 2, we state some notations for the scheduling problems under consideration. Section 3 is devoted to the theoretical results. We start in Section 3.1 with a global overview of the approach and a summary of all results: three platform types and three objective functions lead to nine theorems! We study communication-homogeneous platforms in Section 3.2, computation-homogeneous platforms in Section 3.3, and fully heterogeneous platforms in Section 3.4. We provide an experimental comparison of several scheduling heuristics in Section 4. Section 5 is devoted to an overview of related work. Finally, we state some concluding remarks in Section 6.

Framework

Assume that the platform is composed of a master and m slaves P 1 , P 2 , . . . , P m . Let c j be the time needed by the master to send a task to P j , and let p j be the time needed by P j to execute a task. As for the tasks, we simply number them 1, 2, . . . , i, . . . We let r i be the release time of task i, i.e., the time at which task i becomes available on the master. In on-line scheduling problems, the r i 's are not known in advance. Finally, we let C i denote the end of the execution of task i under the target schedule.

To be consistent with the literature [START_REF] Lenstra | Optimization and approximation in deterministic sequencing and scheduling: a survey[END_REF][START_REF] Blazewicz | Scheduling subject to resource constraints[END_REF], we describe our scheduling problems using the notation α | β | γ where: α: the platform-As in the standard, we use P for platforms with identical processors, and Q for platforms with different-speed processors. As we only target sets of same-size tasks, we always fall within the model of uniform processors: the execution time of a task on a processor only depends on the processor running it and not on the task itself. We add MS to this field to indicate that we work with master-slave platforms.

β: the constraints-We write on-line for on-line problems. We also write c j = c for communication-homogeneous platforms, and p j = p for computation-homogeneous platforms.

γ: the objective-We deal with three objective functions:

• the makespan or total execution time max C i ;

• the maximum flow max-flow or maximum response time max (C i -r i ): indeed, C i -r i is the time spent by task i in the system;

• the sum of response times (C i -r i ) or sumflow, which is equivalent to the sum of completion times C i (because r i is a constant independent of the scheduling).

Theoretical results

Overview and summary

Given a platform (say, with homogeneous communication links) and an objective function (say, makespan minimization), how can we establish a bound on the competitive ratio on the performance of any deterministic scheduling algorithm? Intuitively, the approach is the following. We assume a scheduling algorithm, and we run it against a scenario elaborated by an adversary. The adversary analyzes the decisions taken by the algorithm, and reacts against them. For instance if the algorithm has scheduled a given task T on P 1 then the adversary will send two more tasks, while if the algorithm schedules T on P 3 then the adversary terminates the instance. In the end, we compute the performance ratio: we divide the makespan achieved by the algorithm by the makespan of the optimal solution, which we determine off-line, i.e., with a complete knowledge of the problem instance (all tasks and their release dates). In one execution (task T on P 1 ) this performance ratio will be, say, 1.1 while in another one (task T on P 3 ) it will be, say, 1.2. Clearly, the minimum of the performance ratios over all execution scenarios is the desired bound on the competitive ratio of the algorithm: no algorithm can do better than this bound! Because we have three platform types (communicationhomogeneous, computation-homogeneous, fully heterogeneous) and three objective functions (makespan, max-flow, sum-flow), we have nine bounds to establish. Table 1 summarizes the results, and shows the influence on the platform type on the difficulty of the problem. As expected, mixing both sources of heterogeneity (i.e., having both heterogeneous computations and communications) renders the problem the most difficult.

Objective function Platform type

Makespan

Max-flow Sum-flow Communication homogeneous

5 4 = 1.250 5- √ 7 2 ≈1.177 2+4 √ 2 7

≈1.093

Computation homogeneous

Heterogeneous

1+ √ 3 2 ≈1.366 √ 2 ≈1.414 √ 13-1 2

≈1.302

Table 1. Lower bounds on the competitive ratio of on-line algorithms, depending on the platform type and on the objective function.

Communication-homogeneous platforms

In this section, we have c j = c but different-speed processors. We order them so that P 1 is the fastest processor (p 1 is the smallest computing time p i ), while P m is the slowest processor.

Theorem 1. There is no scheduling algorithm for the problem Q, MS | online, r i , p j , c j = c | max C i with a competitive ratio less than 5 4 .

Proof. Suppose the existence of an on-line algorithm A with a competitive ratio ρ = 5 4 -, with > 0. We will build a platform and study the behavior of A opposed to our adversary. The platform consists of two processors, where p 1 = 3, p 2 = 7, and c = 1.

Initially, the adversary sends a single task i at time 0. A sends the task i either on P 1 , achieving a makespan at least (Nothing forces A to send the task i as soon as possible) equal to c + p 1 = 4, or on P 2 , with a makespan at least equal to c + p 2 = 8. At time t 1 = c, we check whether A made a decision concerning the scheduling of i, and the adversary reacts consequently:

1. If A did not begin the sending of the task i, the adversary does not send other tasks. The best makespan is then t 1 + c + p 1 = 5. As the optimal makespan is 4, we have a competitive ratio of 5 4 > ρ. This refutes the assumption on ρ. Thus algorithm A must have scheduled the task i at time c.

If

A scheduled the task i on P 2 the adversary does not send other tasks. The best possible makespan is then equal to c + p 2 = 8, which is even worse than the previous case. Consequently, algorithm A does not have another choice than to schedule the task i on P 1 in order to be able to respect its competitive ratio.

At time t 1 = c, the adversary sends another task, j. In this case, we look, at time t 2 = 2c, at the assignment A made for j:

1. If j is sent on P 2 , the adversary does not send any more task. The best achievable makespan is then max{c + p 1 , 2c+p 2 } = max{1+3, 2+7} = 9, whereas the optimal is to send the two tasks to P 1 for a makespan of max{c + 2p .

Proof. Suppose the existence of an on-line algorithm A with a competitive ratio ρ = 2+4 √ 2 7

-, with > 0. We will build a platform and study the behavior of A opposed to our adversary. The platform consists of two processors, where p 1 = 2, p 2 = 4 √ 2 -2, and c = 1. Initially, the adversary sends a single task i at time 0. A sends the task i either on P 1 , achieving a sum-flow at least equal to c + p 1 = 3, or on P 2 , with a sum-flow at least equal to c + p 2 = 4 √ 2 -1. At time t 1 = c, we check whether A made a decision concerning the scheduling of i, and the adversary reacts consequently:

1. If A did not begin the sending of the task i, the adversary does not send other tasks. The best sum-flow is then t 1 + c + p 1 = 4. As the optimal sum-flow is 3, we have a competitive ratio of 4 3 > ρ. This refutes the assumption on ρ. Thus algorithm A must have scheduled the task i at time c.

If

A scheduled the task i on P 2 the adversary does not send other tasks. The best possible sum-flow is then equal to c + p 2 = 4 √ 2 -1, which is even worse than the previous case. Consequently, algorithm A does not have another choice than to schedule the task i on P 1 in order to be able to respect its competitive ratio.

At time t 1 = c, the adversary sends another task, j. In this case, we look, at time t 2 = 2c, at the assignment A made for j:

1. If j is sent on P 2 , the adversary does not send any more task. The best achievable sum-flow is then

(c + p 1 ) + ((2c + p 2 ) -t 1 ) = 2 + 4 √ 2,
whereas the optimal is to send the two tasks to P 1 for a sum-flow of

(c+p 1 )+(max{2c+p 1 , c+2p 1 }-t 1 ) = 7. The com- petitive ratio is then 2+4 √ 2 7 > ρ.
2. If j is sent on P 1 the adversary sends a last task at time t 2 = 2c. Then the schedule has the choice to execute the last task either on P 1 for a sum-flow of

(c + p 1 ) + (max{c + 2p 1 , 2c + p 1 } -t 1 ) + (max{3c + p 1 , c + 3p 1 } -t 2 ) = 12, or on P 2 for a sum-flow of (c + p 1 ) + (max{c + 2p 1 , 2c + p 1 } -t 1 ) + ((3c + p 2 ) -t 2 ) = 6 + 4 √ 2.
The best achievable sum-flow is then 6 + 4 √ 2. However, scheduling the second task on P 2 and the two others on P 1 leads to a sum-flow

of (c + p 1 ) + ((2c + p 2 ) -t 1 ) + (max{3c + p 1 , c + 2p 1 } -t 2 ) = 5 + 4 √ 2.
The competitive ratio is therefore at least equal to 6+4

√ 2 5+4 √ 2 = 2+4 √ 2 7 > ρ.
3. If j is not send yet, then the adversary sends a last task k at time t 2 = 2c. Then the schedule has the choice to execute j either on P 1 , and achieving a sum-flow worse than the previous case, or on P 2 . Then, it can choose to execute the last task either on P 2 for a sumflow of (c

+ p 1 ) + (t 2 + c + p 2 -t 1 ) + (t 2 + c + p 2 + max{c, p 2 } -t 2 ) = 12 √ 2 + 2, or on P 1 for a sum- flow of (c + p 1 ) + (t 2 + c + p 2 -t 1 ) + (max{t 2 + c + p 1 , c + 2p 1 } -t 2 ) = 7 + 4 √ 2.
The best achievable sum-flow is then 7 + 4 √ 2 which is even worse than the previous case. Hence the desired contradiction.

Theorem 3. There is no scheduling algorithm for the problem

Q, MS | online, r i , p j , c j = c | max (C i -r i ) with a competitive ratio less than 5- √ 7
2 . Proof. Suppose the existence of an on-line algorithm A with a competitive ratio ρ = 5-

√ 7 2
-, with > 0. We will build a platform and study the behavior of A opposed to our adversary. The platform consists of two processors, where

p 1 = 2+ √ 7 3 , p 2 = 1+2 √ 7 3
, and c = 1. Initially, the adversary sends a single task i at time 0. A sends the task i either on P 1 , achieving a max-flow at least equal to c + p 1 = 5+ √ 7

3 , or on P 2 , with a max-flow at least equal to c

+ p 2 = 4+2 √ 7 3 . At time τ = 4- √ 7
3 , we check whether A made a decision concerning the scheduling of i, and the adversary reacts consequently:

1. If A did not begin the sending of the task i, the adversary does not send other tasks. The best possible max-flow is then τ + c + p 1 = 3. As the optimal max-flow is 5+ √ 7

3 , we have a competitive ratio of

9 5+ √ 7 = 5- √ 7 2
> ρ. This refutes the assumption on ρ. Thus algorithm A must have scheduled the task i at time τ .

If

A scheduled the task i on P 2 the adversary does not send other tasks. The best possible max-flow is then equal to

4+2 √ 7 3
, which is even worse than the previous case. Consequently, algorithm A does not have another choice than to schedule the task i on P 1 in order to be able to respect its competitive ratio.

At time τ = 4- √ 7
3 , the adversary sends another task, j. The best schedule would have been to send the first task on P 2 and the second on P 1 achieving a max-flow of max{c +

p 2 , 2c + p 1 -τ } = max{ 4+2 √ 7 3 , 4+2 √ 7 3 } = 4+2 √ 7 3
. We look at the assignment A made for j:

1. If j is sent on P 2 , the best achievable max-flow is then

max{c + p 1 , 2c + p 2 -τ } = max{ 5+ √ 7 3 , 1 + √ 7} = 1 + √ 7, whereas the optimal is 4+2 √ 7 3
. The competitive ratio is then 5-

√ 7 2 > ρ.
2. If j is sent on P 1 , the best possible max-flow is

then max{c + p 1 , max{c + 2p 1 , 2c + p 1 } -τ } = max{ 5+ √ 7 3 , 1 + √ 7} = 1 + √ 7.
The competitive ratio is therefore once again equal to 5-

√ 7 2
> ρ.

Computation-homogeneous platforms

In this section, we have p j = p but processor links with different capacities. We order them, so that P 1 is the fastest communicating processor (c 1 is the smallest computing time c i ). Just as in Section 3.2, we can bound the competitive ratio of any deterministic algorithm: Theorem 4. There is no scheduling algorithm for the problem P, MS | online, r i , p j = p, c j | max C i whose competitive ratio ρ is strictly lower than 6 5 .

Proof. Assume that there exists a deterministic on-line algorithm A whose competitive ratio is ρ = 6 5 -, with > 0. We will build a platform and an adversary to derive a contradiction. The platform is made up with two processors P 1 and P 2 such that p 1 = p 2 = p = max{5, 12 25 }, c 1 = 1 and c 2 = p 2 . Initially, the adversary sends a single task i at time 0. A executes the task i, either on P 1 with a makespan at least equal to 1 + p, or on P 2 with a makespan at least equal to 3p 2 .

At time-step p 2 , we check whether A made a decision concerning the scheduling of i, and which one:

1. If A scheduled the task i on P 2 the adversary does not send other tasks. The best possible makespan is then 3p 2 . The optimal scheduling being of makespan 1 + p, we have a competitive ratio of

ρ ≥ 3p 2 1 + p = 3 2 - 3 2(p + 1) > 6 5
because p ≥ 5 by assumption. This contradicts the hypothesis on ρ. Thus algorithm A cannot schedule task i on P 2 .

2. If A did not begin to send the task i, the adversary does not send other tasks. The best makespan that can be achieved is then equal to p 2 + (1 + p) = 1 + 3p 2 , which is even worse than the previous case. Consequently, algorithm A does not have any other choice than to schedule task i on P 1 .

At time-step p 2 , the adversary sends three tasks, j, k and l. No schedule which executes three of the four tasks on the same processor can have a makespan lower than 1 + 3p (minimum duration of a communication and execution without delay of the three tasks). We now consider the schedules which compute two tasks on each processor. Since i is computed on P 1 , we have three cases to study, depending upon which other task (j, k, or l) is computed on P 1 :

1. If j is computed on P 1 , at best we have:

(a) Task i is sent to P 1 during the interval [0, 1] and is computed during the interval [1, 1 + p]. (b) Task j is sent to P 1 during the interval [ p 2 , 1 + p 2 ] and is computed during the interval [1 + p, 1 + 2p]. (c) Task k is sent to P 2 during the interval [1+ p 2 , 1+ p] and is computed during the interval [1 + p, 1 + 2p]. (d) Task l is sent to P 2 during the interval [1 + p, 1 + 3p 2 ]
and is computed during the interval

[1 + 2p, 1 + 3p].
The makespan of this schedule is then 1 + 3p.

(d) Task l is sent to P 1 during the interval [ 3p 2 , 1+ 3p 2 ] and is computed during the interval [1 + 3p 2 , 1 + 5p 2 ]
. The makespan of this schedule is then 3p.

Consequently, the last two schedules are equivalent and are better than the first. Altogether, the best achievable makespan is 3p. But a better schedule is obtained when computing i on P 2 , then j on P 1 , then k on P 2 , and finally l on P 1 . The makespan of the latter schedule is equal to 1 + 5p 2 . The competitive ratio of algorithm A is necessarily larger than the ratio of the best reachable makespan (namely 3p) and the optimal makespan, which is not larger than 1 + 5p 2 . Consequently:

ρ ≥ 3p 1 + 5p 2 = 6 5 - 6 5(5p + 2) > 6 5 - 6 25p ≥ 6 5 - 2
which contradicts the assumption ρ = 6 5with > 0.

Theorem 5. There is no scheduling algorithm for the problem P, MS | online, r i , p j = p, c j | max (C i -r i ) whose competitive ratio ρ is strictly lower than 5 4 . Proof. Assume that there exists a deterministic on-line algorithm A whose competitive ratio is ρ = 5 4 -, with > 0. We will build a platform and an adversary to derive a contradiction. The platform is made up with two processors P 1 and P 2 , such that p 1 = p 2 = p = 2c 2 -c 1 , and c 1 = , c 2 = 1. Initially, the adversary sends a single task i at time 0. A executes the task i either on P 1 , with a max-flow at least equal to c 1 + p, or on P 2 with a max-flow at least equal to c 2 + p.

At time step τ = c 2 -c 1 , we check whether A made a decision concerning the scheduling of i, and which one:

1. If A scheduled the task i on P 2 the adversary send no more task. The best possible max-flow is then c 2 + p = 3 -. The optimal scheduling being of max-flow c 1 + p = 2, we have a competitive ratio of

ρ ≥ c 2 + p c 1 + p = 3 2 - 2 > 5 4 -
Thus algorithm A cannot schedule the task i on P 2 .

2. If A did not begin to send the task i, the adversary does not send other tasks. The best max-flow that can be achieved is then equal to τ +c1+p c1+p = 3- 2 , which is the same than the previous case. Consequently, algorithm A does not have any choice but to schedule the task i on P 1 .

At time-step τ , the adversary sends three tasks, j, k and l. No schedule which executes three of the four tasks on the same processor can have a max-flow lower than max(c 1 +3p-τ, max(c 1 , τ )+c 1 +p+max{c 1 , p}-τ ) = 6 -2 . We now consider the schedules which compute two tasks on each processor. Since i is computed on P 1 , we have three cases to study, depending upon which other task (j, k, or l) is computed on P 1 :

1. If j is computed on P 1 :

(a) Task i is sent to P 1 and achieved a flow of c 1 + p = 2.

(b) Task j is sent to P 1 and achieved a flow of

max{c 1 + 2p -τ, max{τ, c 1 } + c 1 + p -τ } = 3. (c)
} + c 2 + 2p, max{τ, c 1 } + 2c 2 + c 1 + p} -τ = 5 -2 . The max-flow of this scheduling is then max{max{τ, c 1 } + c 2 + 2p, max{τ, c 1 } + 2c 2 + c 1 + p} -τ = 5 -2 .
, c 1 } + c 2 + 2p, max{τ, c 1 } + 2c 2 + p} = 5 -2 .
Consequently, the last two schedules are equivalent and are better than the first. Altogether, the best achievable maxflow is 5 -2 . But a better schedule is obtained when computing i on P 2 , then j on P 1 , then k on P 2 , and finally l on P 1 . The max-flow of the latter schedule is equal to

max{c 2 + p, max{τ, c 2 } + c 1 + p -τ, max{max{τ, c 2 } + c 1 + c 2 + p, c 2 + 2p} -τ, max{max{τ, c 2 } + 2c 1 + c 2 + p, max{τ, c 2 } + c 1 + 2p} -τ } = 4.
The competitive ratio of algorithm A is necessarily larger than the ratio of the best reachable max-flow (namely 5 -2 ) and the optimal max-flow, which is not larger than 4. Consequently:

ρ ≥ 5 -2 4 = 5 4 - 2
which contradicts the assumption ρ = 5 4with > 0.

Theorem 6. There is no scheduling algorithm for the problem P, MS | online, r i , p j = p, c j | (C i -r i ) whose competitive ratio ρ is strictly lower than 23/22.

Proof. Assume that there exists a deterministic on-line algorithm A whose competitive ratio is ρ = 23/22 -, with > 0. We will build a platform and an adversary to derive a contradiction. The platform is made up with two processors P 1 and P 2 , such that p 1 = p 2 = p = 3, and c 1 = 1, c 2 = 2. Initially, the adversary sends a single task i at time 0. A executes the task i either on P 1 , with a max-flow at least equal to c 1 + p, or on P 2 with a max-flow at least equal to c 2 + p.

At time step τ = c 2 , we check whether A made a decision concerning the scheduling of i, and which one:

1. If A scheduled the task i on P 2 the adversary sends no more task. The best possible sum-flow is then c 2 + p = 5. The optimal scheduling being of sum-flow c 1 + p = 4, we have a competitive ratio of

ρ ≥ c 2 + p c 1 + p = 5 4 > 23 22
.

Thus algorithm A cannot schedule the task i on P 2 .

2. If A did not begin to send the task i, the adversary does not send other tasks. The best sum-flow that can be achieved is then equal to τ +c1+p c1+p = 6 4 , which is even worse than the previous case. Consequently, algorithm A does not have any choice but to schedule the task i on P 1 .

At time-step τ , the adversary sends three tasks, j, k, and l. We look at all the possible schedules, with i computed on P 1 :

1. If all tasks are executed on P 1 the sum-flow is (c

1 + p) + (max{c 1 + 2p, max{τ, c 1 } + c 1 + p -τ ) + (max{c 1 +3p, max{τ, c 1 }+c 1 +p+max{c 1 , p}-τ )+ (max{c 1 + 4p, max{τ, c 1 } + c 1 + p + 2 max{c 1 , p} - τ ) = 28.
2. If j is the only task executed on P 2 the sum-flow is

(c 1 + p) + (max{τ, c 1 } + c 2 + p -τ ) + (max{c 1 + 2p, max{τ, c 1 } + c 2 + c 1 + p} -τ ) + (max{c 1 + 3p, max{τ, c 1 }+c 2 +c 1 +p+max{c 1 , p}}-τ ) = 24.
3. If k is the only task executed on P 2 the sum-flow is

(c 1 + p) + (max{c 1 + 2p, max{τ, c 1 } + c 1 + p - τ ) + (max{τ, c 1 } + c 1 + c 2 + p -τ ) + (max{c 1 + 3p, max{τ, c 1 } + c 2 + 2c 1 + p} -τ ) = 23.
4. If l is the only task executed on P 2 the sum-flow is

(c 1 + p) + (max{c 1 + 2p, max{τ, c 1 } + c 1 + p -τ ) + (max{c 1 + 3p, max{τ, c 1 } + c 1 + p + max{c 1 , p} - τ ) + (max{τ, c 1 } + 2c 1 + c 2 + p -τ ) = 24.
5. If j,k,l are executed on P 2 the sum-flow is (c

1 + p) + (max{τ, c 1 } + c 2 + p -τ ) + (max{τ, c 1 } + c 2 + p + max{c 2 , p} -τ ) + (max{τ, c 1 } + c 2 + p + 2 max{c 2 , p} -τ ) = 28.
We now consider the schedules which compute two tasks on each processor. Since i is computed on P 1 , we have three cases to study, depending upon which other task (j, k, or l) is computed on P 1 :

1. If j is computed on P 1 the sum-flow is:

(c 1 + p) + (max{c 1 + 2p, max{τ, c 1 } + c 1 + p -τ ) + (max{τ, c 1 } + c 1 + c 2 + p -τ ) + (max{τ, c 1 } + c 1 + c 2 + p + max{c 2 , p} -τ ) = 24.
2. If k is computed on

P 1 : (c 1 + p) + (max{τ, c 1 } + c 2 + p -τ ) + (max{c 1 + 2p, max{τ, c 1 } + c 2 + c 1 + p} - τ ) + (max{τ, c 1 } + c 2 + p + max{c 1 + c 2 , p} -τ ) = 23.
3. If l is computed on

P 1 : (c 1 + p) + (max{τ, c 1 } + c 2 + p -τ ) + (max{τ, c 1 } + c 2 + p + max{c 2 , p} -τ ) + (max{c 1 + 2p, max{τ, c 1 } + 2c 2 + c 1 + p} -τ ) = 25.
Consequently, the best achievable sum-flow is 23. But a better schedule is obtained when computing i on P 2 , then j on P 1 , then k on P 2 , and finally l on P 1 . The sum-flow of the latter schedule is equal to

(c 2 + p) + (max{τ, c 2 } + c 1 + p -τ ) + (max{max{τ, c 2 } + c 1 + c 2 + p, c 2 + 2p} -τ + max{max{τ, c 2 } + 2c 1 + c 2 + p, max{τ, c 2 } + c 1 + 2p} - τ } = 22.
The competitive ratio of algorithm A is necessarily larger than the ratio of the best reachable sum-flow (namely 23) and the optimal sum-flow, which is not larger than 22. Consequently:

ρ ≥ 23 22
which contradicts the assumption ρ = 23 22 with > 0.

Fully heterogeneous platforms

Just as in the previous two sections, we can bound the competitive ratio of any deterministic algorithm. As expected, having both heterogeneous computations and communications increases the difficulty of the problem. Theorem 7. There is no scheduling algorithm with at least three processors for the problem Q, MS | online, r i , p j , c j | max C i whose competitive ratio ρ is strictly lower than

1+ √ 3
2 . Proof. Assume that there exists a deterministic on-line algorithm A whose competitive ratio is ρ = 1+ √ 3 2 -, with > 0. We will build a platform and an adversary to derive a contradiction. The platform is made up with three processors P 1 , P 2 , and

P 3 such that p 1 = , p 2 = p 3 = 1 + √ 3, c 1 = 1 + √ 3 and c 2 = c 3 = 1.
Initially, the adversary sends a single task i at time 0. A executes the task i, either on P 1 with a makespan at least equal to c 1 + p 1 = 1 + √ 3 + , or on P 2 or P 3 , with a makespan at least equal to c 2 + p 2 = c 3 + p 3 = 2 + √ 3.

At time-step 1, we check whether A made a decision concerning the scheduling of i, and which one:

1. If A scheduled the task i on P 2 or P 3 , the adversary does not send any other task. The best possible makespan is then c 2 + p 2 = c 3 + p 3 = 2 + √ 3. The optimal scheduling being of makespan c 1 + p 1 = 1 + √ 3 + , we have a competitive ratio of:

ρ ≥ 2 + √ 3 1 + √ 3 + > 1 + √ 3 2 -,
because > 0 by assumption. This contradicts the hypothesis on ρ. Thus algorithm A cannot schedule task i on P 2 or P 3 .

2. If A did not begin to send the task i, the adversary does not send any other task. The best makespan that can be achieved is then equal to 1 + c 1 + p 1 = 2 + √ 3 + , which is even worse than the previous case. Consequently, algorithm A does not have any other choice than to schedule task i on P 1 .

Then, at time-step τ = 1, the adversary sends two tasks, j and k. We consider all the scheduling possibilities:

• j and k are scheduled on P 1 . Then the best achievable makespan is:

max{c 1 +3p 1 , max{c 1 , τ }+c 1 +p 1 +max{c 1 , p 1 }} = 3(1 + √ 3) + , as < 1+ √ 3
2 . • The first of the two jobs, j and k, to be scheduled is scheduled on P 2 (or P 3 ) and the other one on P 1 . Then, the best achievable makespan is:

max{c 1 + p 1 , max{c 1 , τ } + c 2 + p 2 , max{c 1 + 2p 1 , max{c 1 , τ } + c 2 + c 1 + p 1 }} = max{1 + √ 3 + , 3 + 2 √ 3, max{1 + √ 3 + 2 , 3 + 2 √ 3 + } = 3 + 2 √ 3 + .
• The first of the two jobs j and k to be scheduled is scheduled on P 1 and the other one on P 2 (or P 3 ). Then, the best achievable makespan is:

max{c 1 +p 1 , max{max{c 1 , τ }+c 1 +p 1 , c 1 +2p 1 }, max{c 1 , τ } + c 1 + c 2 + p 2 } = max{1 + √ 3 + , max{2 + 2 √ 3 + , 1 + √ 3 + 2 }, 4 + 3 √ 3} = 4 + 3 √ 3.
• One of the jobs j and k is scheduled on P 2 and the other one on P 3 .

max{c 1 + p 1 , max{c 1 , τ } + c 2 + p 2 , max{c 1 , τ } + c 2 + c 3 + p 3 } = max{1 + √ 3 + , 3 + 2 √ 3, 4 + 2 √ 3} = 4 + 2 √ 3.
• The case where j and k are both executed on P 2 , or both on P 3 , leads to an even worse makespan than the previous case. Therefore, we do not need to study it.

Therefore, the best achievable makespan for A is: 3+2 √ 3+ (as < 1). However, we could have scheduled i on P 2 , j on P 3 , and then k on P 1 , thus achieving a makespan of:

max{c 2 + p 2 , max{c 2 , τ } + c 3 + p 3 , max{c 2 , τ } + c 3 + c 1 + p 1 } = max{2+ √ 3, max{1, 1}+2+ √ 3, max{1, 1}+2+ √ 3+ , } = 3 + √ 3 + .
Therefore, we have a competitive ratio of:

ρ ≥ 3 + 2 √ 3 + 3 + √ 3 + > 1 + √ 3 2 -.
This contradicts the hypothesis on ρ.

Theorem 8. There is no scheduling algorithm with at least three processors for the problem Q, MS | online, r i , p j , c j | (C i -r i ) whose competitive ratio ρ is strictly lower than

√ 13-1 2
.

Proof. Assume that there exists a deterministic on-line algorithm A whose competitive ratio is ρ = √ 13-1 2

-, with > 0. We will build a platform and an adversary to derive a contradiction. The platform is made up of three processors P 1 , P 2 , and

P 3 such that p 1 = , p 2 = p 3 = τ + c 1 -1, c 2 = c 3 = 1, and τ = √ 52c 2 1 +12c1+1-(6c1+1) 4
. Note that τ < c 1 and that:

lim c1→+∞ τ c 1 = √ 13 -3 2
Therefore the exists a value N 0 such that:

c 1 ≥ N 0 ⇒ c 1 > and τ > .
The value of c 1 will be defined later on. For now, we just assume that c 1 ≥ N 0 . Initially, the adversary sends a single task i at time 0. A executes the task i, either on P 1 with a sum-flow at least equal to c 1 + p 1 , or on P 2 or P 3 , with a sum-flow at least equal to c 2 + p 2 = c 3 + p 3 = τ + c 1 .

At time-step τ , we check whether A made a decision concerning the scheduling of i, and which one:

1. If A scheduled the task i on P 2 or P 3 , the adversary does not send any other task. The best possible sumflow is then c 2 + p 2 = c 3 + p 3 = τ + c 1 . The optimal scheduling being of sum-flow c 1 + p 1 = c 1 + , we have a competitive ratio of:

ρ ≥ τ + c 1 c 1 + .
However,

lim c1→+∞ τ + c 1 c 1 + = √ 13-3 2 c 1 + c 1 c 1 = √ 13 -1 2 .
Therefore, there exists a value N 1 such that:

c 1 ≥ N 1 ⇒ τ + c 1 c 1 + > √ 13 -1 2 - 2 ,
which contradicts the hypothesis on ρ. We will now suppose that c 1 ≥ max{N 0 , N 1 }. Then algorithm A cannot schedule task i on P 2 or P 3 .

2. If A did not begin to send the task i, the adversary does not send any other task. The best sum-flow that can be achieved is then equal to τ + c 1 + p 1 = τ + c 1 + , which is even worse than the previous case. Consequently, algorithm A does not have any other choice than to schedule task i on P 1 .

Then, at time-step τ , the adversary sends two tasks, j and k. We consider all the scheduling possibilities:

• Tasks j and k are scheduled on P 1 . Then the best achievable sum-flow is:

(c 1 + p 1 )+ (max{max{c 1 , τ } + c 1 + p 1 , c 1 + 2p 1 } -τ )+ (max{max{c 1 , τ } + c 1 + p 1 + max{c 1 , p 1 }, c 1 + 3p 1 } -τ ) = 6c 1 + 3p 1 -2τ = 6c 1 -2τ + 3 as p 1 < c 1 .
• The first of the two jobs, j and k, to be scheduled is scheduled on P 2 (or P 3 ) and the other one on P 1 . Then, the best achievable sum-flow is:

(c 1 + p 1 ) + ((max{c 1 , τ } + c 2 + p 2 ) -τ ) + (max{max{c 1 , τ } + c 2 + c 1 + p 1 , c 1 + 2p 1 } -τ ) = 4c 1 + 2 + 2p 1 + p 2 -2τ = 5c 1 -τ + 1 + 2
• The first of the two jobs j and k to be scheduled is scheduled on P 1 and the other one on P 2 (or P 3 ). Then, the best achievable sum-flow is:

(c 1 +p 1 )+(max{max{c 1 , τ }+c 1 +p 1 , c 1 +2p 1 }-τ ) + ((max{c 1 , τ } + c 1 + c 2 + p 2 ) -τ ) = 5c 1 + c 2 + 2p 1 + p 2 -2τ = 6c 1 -τ + 2
• One of the jobs j and k is scheduled on P 2 and the other one on P 3 .

(c 1 + p 1 ) + ((max{c 1 , τ } + c 2 + p 2 ) -τ ) + ((max{c 1 , τ } + c 2 + c 3 + p 3 ) -τ ) = 3c 1 + 3c 2 + p 1 + 2p 2 -2τ = 5c 1 + 1 +
• The case where j and k are both executed on P 2 , or both on P 3 , leads to an even worse sum-flow than the previous case. Therefore, we do not need to study it.

Therefore, the best achievable sum-flow for A is: 5c 1 -τ + 1+2 (as c 1 > τ > ). However, we could have scheduled i on P 2 , j on P 3 , and then k on P 1 , thus achieving a sum-flow of:

(c 2 + p 2 ) + ((max{c 2 , τ } + c 3 + p 3 ) -τ ) + ((max{c 2 , τ } + c 3 + c 1 + p 1 ) -τ ) = c 1 + 3c 2 + p 1 + 2p 2 = 3c 1 + 2τ + 1 + .
Therefore, we have a competitive ratio of:

ρ ≥ 5c 1 -τ + 1 + 2 3c 1 + 2τ + 1 + However, lim c1→+∞ 5c 1 -τ + 1 + 2 3c 1 + 2τ + 1 + = lim c1→+∞ 5c 1 - √ 13-3 2 c 1 3c 1 + 2 √ 13-3 2 c 1 = √ 13 -1 2
Therefore, there exists a value N 2 such that:

c 1 ≥ N 2 ⇒ 5c 1 -τ + 1 + 2 3c 1 + 2τ + 1 + > √ 13 -1 2 - 2 ,
which contradicts the hypothesis on ρ. Therefore, if we initially choose c 1 greater than max{N 0 , N 1 , N 2 }, we obtain the desired contradiction.

Theorem 9. There is no scheduling algorithm with at least three processors for the problem

Q, MS | online, r i , p j , c j | max(C i -r i ) whose competitive ratio ρ is strictly lower than √ 2.
Proof. Assume that there exists a deterministic on-line algorithm A whose competitive ratio is ρ = √ 2 -, with > 0. We will build a platform and an adversary to derive a contradiction. The platform is made up of three processors P 1 , P 2 , and

P 3 such that p 1 = , p 2 = p 3 = √ 2c 1 -1, c 1 = 2(1 + √ 2), c 2 = c 3 = 1, and τ = ( √ 2 -1)c 1 . Note that τ < c 1 , and that c 1 + p 1 < p 2 .
Initially, the adversary sends a single task i at time 0. A executes the task i, either on P 1 with a max-flow at least equal to c 1 + p 1 = c 1 + , or on P 2 or P 3 , with a max-flow at least equal to c 2 + p 2 = c 3 + p 3 = √ 2c 1 . At time-step τ , we check whether A made a decision concerning the scheduling of i, and which one:

1. If A scheduled the task i on P 2 or P 3 , the adversary does not send any other task. The best possible maxflow is then

c 2 + p 2 = c 3 + p 3 = √ 2c 1 .
The optimal scheduling being of max-flow c 1 + p 1 = c 1 + , we have a competitive ratio of:

ρ ≥ c 2 + p 2 c 1 + p 1 = √ 2c 1 c 1 + > √ 2 -, as c 1 > √ 2.
This contradicts the hypothesis on ρ. Thus algorithm A cannot schedule task i on P 2 or P 3 .

2. If A did not begin to send the task i, the adversary does not send any other task. The best max-flow that can be achieved is then equal to τ + c 1 + p 1 = √ 2c 1 + , which is even worse than the previous case. Consequently, algorithm A does not have any other choice than to schedule task i on P 1 .

Then, at time-step τ , the adversary sends two tasks, j and k. We consider all the scheduling possibilities:

• j and k are scheduled on P 1 . Then the best achievable max-flow is:

max{c 1 + p 1 , max{max{c 1 , τ } + c 1 + p 1 , c 1 + 2p 1 } -τ, max{max{c 1 , τ } + c 1 + p 1 + max{c 1 , p 1 }, c 1 + 3p 1 } -τ } = 3c 1 + p 1 -τ = (4 - √ 2)c 1 + as p 1 < c 1 .
• The first of the two jobs, j and k, to be scheduled is scheduled on P 2 (or P 3 ) and the other one on P 1 . Then, the best achievable max-flow is:

max{c 1 + p 1 , (max{c 1 , τ } + c 2 + p 2 ) -τ, max{max{c 1 , τ } + c 2 + c 1 + p 1 , c 1 + 2p 1 } -τ } = c 1 + c 2 -τ + max{p 2 , c 1 + p 1 } = 2c 1
• The first of the two jobs j and k to be scheduled is scheduled on P 1 and the other one on P 2 (or P 3 ). Then, the best achievable max-flow is:

max{c 1 + p 1 , max{max{c 1 , τ } + c 1 + p 1 , c 1 + 2p 1 } -τ, (max{c 1 , τ } + c 1 + c 2 + p 2 ) -τ } = 2c 1 -τ + max{p 1 , c 2 + p 2 } = 3c 1
• One of the jobs j and k is scheduled on P 2 and the other one on P 3 .

max{c 1 + p 1 , (max{c 1 , τ } + c 2 + p 2 ) -τ, (max{c 1 , τ } + c 2 + c 3 + p 3 ) -τ } = c 1 + 2c 2 + p 2 -τ = 2c 1 + 1
• The case where j and k are both executed on P 2 , or both on P 3 , leads to an even worse max-flow than the previous case. Therefore, we do not need to study it.

Therefore, the best achievable max-flow for A is: 2c 1 . However, we could have scheduled i on P 2 , j on P 3 , and then k on P 1 , thus achieving a max-flow of:

max{c 2 + p 2 , (max{c 2 , τ } + c 3 + p 3 ) -τ, (max{c 2 , τ } + c 3 + c 1 + p 1 ) -τ } = max{c 2 , τ } + c 2 + max{p 2 , c 1 + p 1 } -τ = √ 2c 1
Therefore, we have a competitive ratio of:

ρ ≥ 2c 1 √ 2 = √ 2,
which contradicts the hypothesis on ρ.

MPI experiments

To complement the previous theoretical results, we looked at some efficients on-line algorithms, and we compared them experimentally on different kind of platforms. In particular, we include in the comparison the two new heuristics of [START_REF] Pineau | Off-line and on-line scheduling on heterogeneous masterslave platforms[END_REF], which were specifically designed to work well on communication-homogeneous and on computation-homogeneous platforms respectively. We then study the impact of heterogeneity on the performance of some scheduling algorithms.

The algorithms

We describe here the different algorithms used in the practical tests:

1. SRPT: Shortest Remaining Processing Time is a well known algorithm on a platform where preemption is allowed, or with task of different size. But in our case, with identical tasks and no preemption, its behavior is the following: it sends a task to the fastest free slave; if no slave is currently free, it waits for the first slave to finish its task, and then sends it a new one.

2. LS: List Scheduling can be viewed as the static version of SRPT. It uses its knowledge of the system and sends a task as soon as possible to the slave that would finish it first, according to the current load estimation (the number of tasks already waiting for execution on the slave).

3. RR : Round Robin is the simplest algorithm. It simply sends a task to each slave one by one, according to a prescribed ordering. This ordering first choose the slave with the smallest p i + c i , then the slave with the second smallest value, etc.

4. RRC has the same behavior than RR, but uses a different ordering: it sends the tasks starting from the slave with the smallest c i up to the slave with the largest one.

5. RRP has the same behavior than RR, but uses yet another ordering: it sends the tasks starting from the slave with the smallest p i up to the slave with the largest one.

6. SLJF : Scheduling the Last Job First is one of the two algorithms we built. We proved in [START_REF] Pineau | Off-line and on-line scheduling on heterogeneous masterslave platforms[END_REF] that this algorithm is optimal to minimize the makespan on a communication-homogeneous platform, as soon as it knows the total number of tasks, even with releasedates. As it name says, it calculates, before scheduling the first task, the assignment of all tasks, starting with the last one.

7. SLJFWC : Scheduling the Last Job First With Communication is a variant of SLJF conceived to work on processor-homogeneous platforms. See [START_REF] Pineau | Off-line and on-line scheduling on heterogeneous masterslave platforms[END_REF] for a detailed description.

The last two algorithms were initially built to work with off-line models, because they need to know the total number of tasks to perform at their best. So we transform them for on-line execution as follows: at the beginning, we start to compute the assignment of a certain number of tasks (the greater this number, the better the final assignment), and start to send the first tasks to their assigned processors. Once the last assignment is done, we continue to send the remaining tasks, each task being sent to the processor that would finish it the earliest. In other words, the last tasks are assigned using a list scheduling policy.

The experimental platform

We build a small heterogeneous master-slave platform with five different computers, connected to each other by a fast Ethernet switch (100 Mbit/s). The five machines are all different, both in terms of CPU speed and in the amount of available memory. The heterogeneity of the communication links is mainly due to the differences between the network cards. Each task will be a matrix, and each slave will have to calculate the determinant of the matrices that it will receive. Whenever needed, we play with matrix sizes so as to achieve more heterogeneity or on the contrary some homogeneity in the CPU speeds or communication bandwidths. We proceed as follows: in a first step, we send one single matrix to each slave one after a other, and we calculate the time needed to send this matrix and to calculate its determinant on each slave. Thus, we obtain an estimation of c i and p i , according to the matrix size. Then we determine the number of times this matrix should be sent (n ci ) and the number of times its determinant should be calculated (n pi ) on each slave in order to modify the platform characteristics so as to reach the desired level of heterogeneity. Then, a task (matrix) assigned on P i will actually be sent n ci times to P i (so that c i ← n ci .c i ), and its determinant will actually be calculated n pi times by P i (so that p i ← n pi .p i ).

The experiments are as follows: for each diagram, we create ten random platforms, possibly with one prescribed property (such as homogeneous links or processors) and we execute the different algorithms on it. Our platforms are composed with five machines P i with c i between 0.01 s and 1 s, and p i between 0.1 s and 8 s.

Once the platform is created, we send one thousand tasks on it, and we calculate the makespan, sum-flow, and maxflow obtained by each algorithm. After having executed all algorithms on the ten platforms, we calculate the average makespan, sum-flow, and max-flow. The following section shows the different results that have been obtained.

Results

In the following figures, we compare the seven algorithms: SRPT, List Scheduling, the three Round-Robin variants, SLJF, and SLJFWC. For each algorithm we plot its normalized makespan, sum-flow, and max-flow, which are represented in this order, from left to right. We normalize everything to the performance of SRPT, whose makespan, max-flow and sum-flow are therefore set equal to 1.

First of all, we consider fully homogeneous platforms. Figure 1(a) shows that all static algorithms perform equally well on such platforms, and exhibit better performance than the dynamic heuristic SRPT. On communication-homogeneous platforms (Figure 1(b)), we see that RRC, which does not take processor heterogeneity into account, performs significantly worse than the others; we also observe that SLJF is the best approach for makespan minimization. On computationhomogeneous platforms (Figure 1(c)), we see that RRP and SLJF, which do not take communication heterogeneity into account, perform significantly worse than the others; we also observe that SLJFWC is the best approach for makespan minimization. Finally, on fully heterogeneous platforms (Figure 1(d)), the best algorithms are LS and SLJFWC. Moreover, we see that algorithms taking communication delays into account actually perform better.

In another experiment, we try to test the robustness of the algorithms. We randomly change the size of the matrix sent by the master at each round, by a factor of up to 10%. Figure 2 represents the average makespan (respectively sumflow and max-flow) compared to the one obtained on the same platform, but with identical size tasks. Thus, we see that our algorithms are quite robust for makespan minimization problems, but not as much for sum-flow or max-flow problems.

Related work

We classify several related papers along the following four main lines:

Models for heterogeneous platforms

In the literature, one-port models come in two variants. In the unidirectional variant, a processor cannot be involved in more than one communication at a given time-step, either a send or a receive. In the bidirectional model, a processor can send and receive in parallel, but at most from a given neighbor in each direction. In both variants, if P u sends a message to P v , both P u and P v are blocked throughout the communication.

The bidirectional one-port model is used by Bhat et al [START_REF] Bhat | Efficient collective communication in distributed heterogeneous systems[END_REF][START_REF] Bhat | Efficient collective communication in distributed heterogeneous systems[END_REF] for fixed-size messages. They advocate its use because "current hardware and software do not easily enable multiple messages to be transmitted simultaneously". Even if non-blocking multi-threaded communication libraries allow for initiating multiple send and receive operations, they claim that all these operations "are eventually serialized by the single hardware port to the network". Experimental evidence of this fact has recently been reported by Saif and Parashar [START_REF] Saif | Understanding the behavior and performance of non-blocking communications in MPI[END_REF], who report that asynchronous MPI sends get serialized as soon as message sizes exceed a few megabytes. Their results hold for two popular MPI implementations, MPICH on Linux clusters and IBM MPI on the SP2.

The one-port model fully accounts for the heterogeneity of the platform, as each link has a different bandwidth. It generalizes a simpler model studied by Banikazemi et al. [START_REF] Banikazemi | Efficient collective communication on heterogeneous networks of workstations[END_REF], Liu [START_REF] Liu | Broadcast scheduling optimization for heterogeneous cluster systems[END_REF], and Khuller and Kim [START_REF] Khuller | On broadcasting in heterogenous networks[END_REF]. In this simpler model, the communication time only depends on the sender, not on the receiver: in other words, the communication speed from a processor to all its neighbors is the same.

Finally, we note that some papers [START_REF] Banikazemi | Communication modeling of heterogeneous networks of workstations for performance characterization of collective operations[END_REF][START_REF] Bar-Noy | Message multicasting in heterogeneous networks[END_REF] depart from the one-port model as they allow a sending processor to initiate another communication while a previous one is still on-going on the network. However, such models insist that there is an overhead time to pay before being engaged in another operation, so there are not allowing for fully simultaneous communications.

Task graph scheduling

Task graph scheduling is usually studied using the socalled macro-dataflow model [START_REF] Norman | Models of machines and computation for mapping in multicomputers[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][START_REF] El-Rewini | Task scheduling in multiprocessing systems[END_REF], whose major flaw is that communication resources are not limited. In this model, a processor can send (or receive) any number of messages in parallel, hence an unlimited number of communication ports is assumed (this explains the name macro-dataflow for the model). Also, the number of messages that can simultaneously circulate between processors is not bounded, hence an unlimited number of communications can simultaneously occur on a given link. In other words, the communication network is assumed to be contention-free, which of course is not realistic as soon as the processor number exceeds a few units. More recent papers [START_REF] Tan | Minimizing the aplication execution time through scheduling of subtasks and communication traffic in a heterogeneous computing system[END_REF][START_REF] Orduna | A new task mapping technique for communication-aware scheduling strategies[END_REF][START_REF] Roig | Improving static scheduling using inter-task concurrency measures[END_REF][START_REF] Beaumont | A realistic model and an efficient heuristic for scheduling with heterogeneous processors[END_REF][START_REF] Beaumont | A polynomial-time algorithm for allocating independent tasks on heterogeneous fork-graphs[END_REF][START_REF] Sinnen | Communication contention in task scheduling[END_REF] take communication resources into account.

Hollermann et al. [START_REF] Hollermann | Scheduling problems in a practical allocation model[END_REF] and Hsu et al. [START_REF] Hsu | Task allocation on a network of processors[END_REF] introduce the following model for task graph scheduling: each processor can either send or receive a message at a given time-step (bidirectional communication is not possible); also, there is a fixed latency between the initiation of the communication by the sender and the beginning of the reception by the receiver. Still, the model is rather close to the one-port model discussed in this paper.

On-line scheduling

A good survey of on-line scheduling can be found in [START_REF] Sgall | On line scheduling-a survey[END_REF][START_REF] Pruhs | On-line scheduling[END_REF]. Two papers focus on the problem of on-line scheduling for master-slaves platforms. In [START_REF] Joseph | Minimizing total completion time in master-slave systems[END_REF], Leung and Zhao proposed several competitive algorithms minimizing the total completion time on a master-slave platform, with or without pre-and post-processing. In [START_REF] Joseph | Minimizing mean flowtime and makespan on master-slave systems[END_REF], the same authors studied the complexity of minimizing the makespan or the total response time, and proposed some heuristics. However, none of these works take into consideration communication costs. To the best of our knowledge, the only previously known results for on-line problems with communication costs are those reported in our former work [START_REF] Pineau | Off-line and on-line scheduling on heterogeneous masterslave platforms[END_REF]; in the current paper, we have dramatically improved several of the competitive ratios given in [START_REF] Pineau | Off-line and on-line scheduling on heterogeneous masterslave platforms[END_REF] and we have added new ones.

Conclusion

In this paper, we have dealt with the problem of on-line scheduling independent, same-size tasks on master-slave platforms. We enforce the one-port model, and we study the impact of heterogeneity on the performance of scheduling algorithms. The major contribution of this paper lies on the theoretical side, and is well summarized by Table 1. We have provided a comprehensive set of lower bounds for the competitive ratio of any deterministic scheduling algorithm, for each source of heterogeneity and for each target objective function. An important direction for future work would be to see which of these bounds can be met, if any, and to design the corresponding approximation algorithms.

On the practical side, we have to widen the scope of the MPI experiments. A detailed comparison of all the heuristics that we have implemented needs to be conducted on significantly larger platforms (with several tens of slaves). Such a comparison would, we believe, further demonstrate the superiority of those heuristics which fully take into account the relative capacity of the communication links.

Jean-François Pineau was born in 1982 in Montpellier. He is currently a PhD student in the Computer Science Laboratory LIP at ENS Lyon. He is mainly interested in the design of parallel algorithms for heterogeneous platform and in scheduling techniques.

Yves Robert received the PhD degree from Institut National Polytechnique de Grenoble in 1986. He is currently a full professor in the Computer Science Laboratory LIP at ENS Lyon. He is the author of four books, 95 papers published in international journals, and 120 papers published in international conferences. His main research interests are scheduling techniques and parallel algorithms for clusters and grids. He is a Fellow of the IEEE.

Frédéric Vivien was born in 1971 in Saint-Brieuc, France. He received the Ph.D. degree from École normale supérieure de Lyon in 1997. From 1998 to 2002, he had been an associate professor at Louis Pasteur University of Strasbourg. He spent the year 2000 working in the Computer Architecture Group of the MIT Laboratory for Computer Science. He is currently a full researcher from INRIA. His main research interests are scheduling techniques, parallel algorithms for clusters and grids, and automatic compilation/parallelization techniques.

2 .

 2 If k is computed on P 1 : (a) Task i is sent to P 1 during the interval [0, 1] and is computed during the interval [1, 1 + p]. (b) Task j is sent to P 2 during the interval [ p 2 , p] and is computed during the interval [p, 2p]. (c) Task k is sent to P 1 during the interval [p, 1 + p] and is computed during the interval [1 + p, 1 + 2p]. (d) Task l is sent to P 2 during the interval [1 + p, 1 + 3p 2 ] and is computed during the interval [2p, 3p]. The makespan of this scheduling is then 3p. 3. If l is computed on P 1 : (a) Task i is sent to P 1 during the interval [0, 1] and is computed during the interval [1, 1 + p]. (b) Task j is sent to P 2 during the interval [ p 2 , p] and is computed during the interval [p, 2p]. (c) Task k is sent to P 2 during the interval [p, 3p 2 ] and is computed during the interval [2p, 3p].

  Task k is sent to P 2 and achieved a flow of max{τ, c 1 } + c 1 + c 2 + p -τ = 3 (d) Task l is sent to P 2 and achieved a flow of max{τ, c 1 }+c 1 +c 2 +p+max{c 2 , p}-τ = 5-. The max-flow of this schedule is then max{τ, c 1 } + c 1 + c 2 + p + max{c 2 , p} -τ = 5 -. 2. If k is computed on P 1 : (a) Task i is sent to P 1 and achieved a flow of c 1 + p = 2. (b) Task j is sent to P 2 and achieved a flow of max{τ, c 1 } + c 2 + p -τ = 3 -. (c) Task k is sent to P 1 and achieved a flow of max{c 1 +2p, max{τ, c 1 }+c 2 +c 1 +p}-τ = 3. (d) Task l is sent to P 2 and achieved a flow of max{max{τ, c 1

3 .

 3 If l is computed on P 1 : (a) Task i is sent to P 1 and achieved a flow of c 1 + p = 2. (b) task j is sent to P 2 and achieved a flow of max{τ, c 1 ) + c 2 + p} = 3 -. (c) Task k is sent to P 2 and achieved a flow of max{max{τ, c 1 } + c 2 + 2p, max{τ, c 1 } + 2c 2 + p} = 5 -2 . (d) Task l is sent to P 1 and achieved a flow of max{c 1 +2p, max{τ, c 1 }+2c 2 +c 1 +p}-τ = 4. The max-flow of this schedule is then max{max{τ

Figure 1 .

 1 Figure 1. Comparison of the seven algorithms on different platforms.

Figure 2 .

 2 Figure 2. Assessing the robustness of the algorithms.

  = c 2 . A has the choice to execute j on P 1 , and to achieve a makespan worse than the previous case, or on P 2 . And it has then the choice to send k either on P 2 for a makespan of max{c + p 1 , t 2 + c + p 2 + max{c, p 2 }} = max{4, 17} = 17, or on P 1 for a makespan of max{c+2p 1 , t 2 +c+p 2 , t 2 +2c+p 1 } =

	1 , 2c + p 1 } = 7. The competitive ratio is 4 > ρ. 7 > 5 then 9 2. If j is sent on P 1 the adversary sends a last task at time t 2 = 2c. Then the schedule has the choice to execute the last task either on P 1 for a makespan of max{c + 3p 1 , 2c + 2p 1 , 3c + p 1 } = max{10, 6} = 10, or on P 2 for a makepsan of max{c + 2p 1 , 3c + p 2 } = max{6, 5, 10} = 10. The best achievable makespan is then 10. However, scheduling the first task on P 2 and the two others on P 1 leads to a makespan of max{c + p 2 , 2c + 2p 1 , 3c + p 1 } = max{8, 8, 6} = 8. The competitive ratio is therefore at least equal to 10 8 = 5 4 > ρ. 3. If j is not sent yet, then the adversary sends a last task at time t 2 max{7, 10, 7} = 10. The best achievable makespan is then 10. The competitive ratio is therefore at least equal to 10 8 = 5 4 > ρ. Hence the desired contradic-tion. Theorem 2. There is no scheduling algorithm for the prob-lem Q, MS | online, r i , p j , c j = c | (C i -r i ) with a √ 2 competitive ratio less than 2+4 7