Bertrand Simon
email: bertrand.simon@ens-lyon.fr

Loris Marchal
email: loris.marchal@ens-lyon.fr

Frédéric Vivien
email: frederic.vivien@inria.fr

Scheduling malleable task trees

Keywords: Scheduling, Malleable tasks, Task trees, Makespan Minimization, Memory minimization Ordonnancement, Tâches malléables, Arbre de tâches, Minimisation du makespan, Minimisation de la mémoire

 in order to study tree workflow schedules under two contradictory objectives: makespan minimization and memory minization. First, we give a simpler proof of the result of [8] which allows to compute a makespan-optimal schedule for tree workflows. Then, we study a more realistic speedup function and show that the previous schedules are not optimal in this context. Finally, we give complexity results concerning the objective of minimizing both makespan and memory.

Introduction

Solving sparse linear systems requires fast sparse matrix factorizations, which then require execution of tree workflows on a platform of processors. A tree workflow is a rooted tree where each node represents a task to be executed, and in which a node cannot be executed before its children. There are two sources of parallelism in the processing of these workflows: the tree parallelism which allows tasks independent from each other (such as siblings) to be processed concurrently, and the task parallelism which allows a task to be processed on several processors. This study aims at improving the execution of such tree workflows, by theoretical studies. Formally, the purpose is to investigate the problem of scheduling a tree-shaped task graph of malleable tasks.

A malleable task is a task that can be parallelized (the more processors we allocate to it, the faster it will be completed) and the share of processors allocated to it can vary over time. As each node of the tree represents a parallelizable task, the problem consists not only in computing an order of execution between the various tasks of the graph, but also in computing the share of processors that is allocated to each task.

The computing platform studied is composed, unless otherwise specified, of homogeneous processors, and no communication or memory issues between different processors are treated. In other words, it can be seen as a processing power that can be divided between several tasks in any way. Moreover, we allow the allocation of real non-negative shares of processors (e.g., 3.5 processors) to each task. In Section 5, we will add memory constraints, assuming that there exists a unique shared memory capacity that cannot be exceeded.

As said above, the main motivation of this problem comes from scientific computing, and more precisely from tree workflows that arise during LU or Cholesky factorization of sparse matrices. An example of such a tree workflow is the elimination tree, which represents the computational dependencies and storage requirements in those factorizations, see [START_REF] Jacquelin | On optimal tree traversals for sparse matrix factorization[END_REF] for details. Authorising noninteger processor allocation is motivated by actual runtime techniques, because time-sharing can indeed be used to process several tasks on one processor [START_REF] Beaumont | Task scheduling for parallel multifrontal methods[END_REF][START_REF] Prasanna | The optimal control approach to generalized multiprocessor scheduling[END_REF].

One difficulty resides in the fact that the parallelization is not ideal and thus if too much processors are given to a task, losses of work and then of makespan will occur. The speedup of a task is a factor represented by a function f depending on a number of processors p. It is defined as the time necessary to complete the task with p processors divided by the time to complete it with 1 processor. In the ideal case, f (p) would be equal to p, but it is actually smaller because of imperfect parallelizations (communication costs or inner scheduling issues). We assume in this work that the speedup function is the same for all tasks and its expression is known. Unless otherwise specified, we will assume f (p) = p α , with α ∈ ]0, 1[. This model has been inferred from actual behaviors of matrix operations when p > 1 [START_REF] Prasanna | The optimal control approach to generalized multiprocessor scheduling[END_REF]. We do not study the general case of an unknown speedup function.

Both extreme cases of α ∈ {0, 1} are not studied neither here. If α = 1, this is the perfect case where no losses occur in parallelization and then any schedule that uses all the processors at any time is makespan-minimizing: it suffices to schedule a node after its children. On the other hand, if α = 0, no parallelization is beneficial, and it is then natural to impose that at least one processor must be allocated to execute a task. This comes back to the sequential case, as studied in [START_REF] Marchal | Scheduling tree-shaped task graphs to minimize memory and makespan[END_REF].

The remainder of this report is organized as follows. We first deal in Section 4 with the problem of computing makespan-minimizing schedules under two models of the speedup function. The first one is the one described above, and the second one is a modification of this model when p < 1 that is closer to reality but more difficult to study. Then, we present some complexity results for the problem combining makespan and memory minimization, assuming the speedup is equal to p α .

Related work

The first problem that we study is to compute the makespan-minimizing schedule of a tree of malleable tasks with the same given speedup function. The concept of malleable tasks is a classical formalism to model parallel computations, see a survey in [START_REF] Drozdowski | Scheduling parallel tasks -algorithms and complexity[END_REF]. A similar problem problem with arbitrary speedup functions has already been studied in [START_REF] Lepère | Approximation algorithms for scheduling malleable tasks under precedence constraints[END_REF], but only dealing with integer shares of processors. In this context, the authors achieve to design a polynomial 2.6-approximation for series-parallel graphs and 5.2 for arbitrary precedence constraints. Concerning non-integer shares, this problem has been examined by Prasanna and Musicus for series-parallel graphs in [START_REF] Prasanna | The optimal control approach to generalized multiprocessor scheduling[END_REF][START_REF] Prasanna | Generalized multiprocessor scheduling and applications to matrix computations[END_REF]. Their work uses optimal control theory to derive general theorems for any strictly increasing speedup function. For the particular case of the speedup equal to p α , they proved properties characterizing exactly the unique optimal schedule, and allowing to compute it efficiently. In this report, we prove the same properties on this latter case but using only pure-scheduling arguments. Moreover, we study afterwards an other model of the speedup function that is more realistic.

The second problem studied, that deals with both makespan and memory minimization, has already been studied in [START_REF] Marchal | Scheduling tree-shaped task graphs to minimize memory and makespan[END_REF], but without allowing task parallelization. For a complete review of related work on this subject, we refer the interested reader to the related work section of [START_REF] Marchal | Scheduling tree-shaped task graphs to minimize memory and makespan[END_REF]. We prove here similar results concerning NP-completeness and inapproximations for malleable tasks in a more constraint model close to the pebble game model used in [START_REF] Marchal | Scheduling tree-shaped task graphs to minimize memory and makespan[END_REF]. These results are then, by extension, also valid for the general model.

Model and notations

The most elementary structure used in this report is a malleable task, as presented is Section 1. Concerning notations, such a task will be indexed by T , I is a set of indices such that the set of tasks is T i | i ∈ I and L i is the length of task T i . The length of a task is the amount of work that is needed to complete this task.

The tasks are structured in a precedence rooted in-tree G, which means that the processing of a task cannot begin before all its children are completed. Therefore, at the outset, only leaves can be processed until an internal node has all its children completed, and at the end, only the root is processed. The set of children of T i is denoted by Children (T i ) and its parent by parent (T i ).

The total amount of processors available at time t is defined by the step function p(t ) ∈ R + R + , called the processor profile. In order to define the time needed to complete a task knowing how many processors are allocated to it, the speedup function has to be defined. It depends on a non-negative real number p, which is the share of processors allocated to a task, is denoted by f (p) and, unless otherwise specified, will be equal to p α with α ∈]0, 1[ being a fixed parameter.

A solution schedule S is defined by a time limit τ and a set of non-negative piecewise continuous functions p i (t ) | i ∈ I defined on [0, τ]. We can suppose that τ is tight, i.e., ∃i ∈ I | p i (τ) > 0. The function p i (t ) represents the share allocated to task i and because the tasks are malleable, it can vary over time. Its signification is that during a time interval ∆, the task T i performs an amount of work equal to ∆ p i (t ) α dt . Then, T i is completed when the total work it has received since the outset is equal to its length L i . We define w i (t ) as the ratio of work of the task T i that is done during the time interval [0, t ]:

w i (t ) = t 0 p i (x) α dx L i .
The ratio of processors given to a task is p i (t )/p(t ). This quantity is relevant as it will be proved constant under certain conditions. We call a clean interval with regard to S an interval during which no task is completed.

A schedule is a valid solution if and only if it does not use more processors than available, completes all the tasks and respects the precedence constraints. More formally it is valid if and only if it respects the following constraints:

• ∀t ∈ [0, τ], i ∈I p i (t ) ≤ p(t ) • ∀i ∈ I , w i (τ) = 1 • For all i ∈ I and t ∈ [0, τ], if p i (t ) > 0 then, for all j ∈ I such that T j is a child of T i in G, w j (t ) = 1
The makespan of a graph G following S is τ, and the optimal makespan of G is the minimum makespan among every valid schedule.

In the first section, we will actually not study rooted trees but a more general structure that is series-parallel graphs (or SP graphs). A SP graph is recursively defined by being a single task, a series composition of two SP graphs, or a parallel composition of two SP graphs. The two subgraphs forming a parallel composition are called branches. Series composition are ordered so that it is clear which subgraph should be executed first. Then, we can naturally define the parents and children of nodes as direct successors and predecessors. Similarly, if two nodes have the same set of parents, they are called siblings. A tree can be easily transformed into an SP graph by joining the leaves according to its structure (see Figure 1), the resulting graph is then called a pseudo-tree. We will use (i ∥ j ) to represent the parallel composition of tasks T i and T j and (i ; j ) to represent the series composition. Then, the SP graph of Figure 1 can be represented as ((4 ∥ 5) ∥ 6) ; 2 ∥ 3 ; 1 . Therefore, trees can be considered as a subset of SP graphs, so we will study in Section 4 SP graphs as they are more general and more convenient for this purpose, but the results will stay valid for trees, which is the main objective of this study.

Makespan-minimizing schedules at a fixed speedup

In this section, we do not focus on memory consumption but only on makespan minimization. Therefore, optimal should be understood here as minimizing the makespan.

As explained above, the speedup is fixed in this section, which means that we design algorithms to a specific speedup, and we do not study the scheduling problem for generic speedup functions, as it was done in [START_REF] Prasanna | Generalized multiprocessor scheduling and applications to matrix computations[END_REF]. We will first study the model where f (p) = p α , as motivated in [START_REF] Prasanna | Generalized multiprocessor scheduling and applications to matrix computations[END_REF], before designing a more realistic model for the special case where p < 1.

The speedup is equal to f (p) = p α

The purpose of this section is to prove that any SP graph G is equivalent to a single task T G of easily computable length: for any processor profile p(t ), graphs G and T G have the same makespan.

Moreover, we prove that in an optimal schedule, all siblings terminate at the same time. In addition, the ratio of processors allocated to each task T i , defined by r i (t ) = p i (t )/p(t ), is constant and equal to r i from the moment at which T i is initiated to the moment at which it is terminated. Similarly, for each branch of a parallel composition, the total ratio of processors allocated to the set of tasks composing this branch is constant.

These properties imply that the optimal schedule is unique and obeys to a flow conservation property: on a tree, ratios of processors are given to the leaves at the beginning of the schedule. Then, all the children of a node T i terminate at the same time, and its ratio r i becomes the sum of its children ratios.

In [START_REF] Prasanna | Generalized multiprocessor scheduling and applications to matrix computations[END_REF], the authors used optimal control theory to achieve a similar result when p(t ) is constant. We generalize here this result when p(t ) is a step function and give a proof using pure-scheduling arguments. This generalization is motivated by modifications of the processing power available.

We first need to define the length L G associated to a graph G, which will be proved to be the length of the task T G . Then, we state a few lemmas before proving the theorem. Definition 1. We recursively define the length L G depending on a SP graph G:

• L T i = L i • L G 1 ;G 2 = L G 1 + L G 2 • L G 1 ∥G 2 = L 1/α G 1 + L 1/α G 2 α
Lemma 1. An allocation minimizing the makespan uses at any time all the processors.

Proof. If a schedule does not use some processors during a certain time interval ∆, it is possible to increase the work performed during ∆ for all the tasks being executed during ∆ by allocating these processors equitably among those tasks. Then, the work performed during ∆ is achieved in a smaller interval because the speedup is a strictly increasing function. It now suffices to remove the processors possibly allocated in surplus (if too much work is done for certain tasks) and move backward the later part of the schedule to reduce the makespan.

Lemma 2. We have to process n tasks in parallel with a constant number of processors p. A schedule that does not allocate a constant number of processors per task on clean intervals is not optimal.

Proof. By contradiction, we consider an optimal schedule P with makespan M , and we suppose that one task j does not have a constant number of processors allocated to it on a clean interval

∆ = [t 1 , t 2 ]
. By definition of a clean interval, no task completes during ∆. By abuse of notations, we will also use ∆ to represent the length of this interval. From now on, the index j will refer to this particular task and the index i will refer to any task. Let p i (t ) denote the share of processors allocated to task T i at time t ∈ ∆.

The purpose is to build a valid schedule R with a makespan smaller than M . To achieve it, we will define three intermediate and not necessarily valid schedules Q {1,2,3} , which will nevertheless respect the resource constraint (no more than p(t ) processors are used at time t ). These schedules will be equal to P except on ∆ where successive modifications will eventually allow to do the same work as P before t 2 , and then lead to the schedule R.

The constant share of processors allocated to task T i on ∆ in Q 1 is defined by q i = 1 ∆ ∆ p i (t )d t . For all t , we have i ∈I p i (t ) = p. We get i ∈I q i = p. So Q 1 respects the resource constraint.

Let

W ∆ i (P ) (resp. W ∆ i (Q 1 )
) denote the work on T i during ∆ under schedule P (resp. Q 1 ).

We have

W ∆ i (P ) = ∆ p i (t ) α d t = ∆ [0,1] p i (t ∆) α d t and W ∆ i (Q 1 ) = ∆ 1 ∆ ∆ p i (t )d t α d x = ∆ [0,1] p i (t ∆)d t α
As α < 1, the function x → x α is strictly concave and then, by Jensen inequality,

W ∆ i (P ) ≤ W ∆ i (Q 1 )
. Moreover, again by Jensen inequality, as p j (t ) is not constant, we have W ∆ j (P ) < W ∆ j (Q 1 ). We will now partition a part the surplus of processors allocated to task j (as

W ∆ j (P ) < W ∆ j (Q 1 )
) to the other tasks so that each one completes its work before t 2 . Then, we will stop the schedule just before t 2 and so perform at least as much work in a smaller makespan.

As W ∆ j (P ) < W ∆ j (Q 1 ), there exists ε > 0 such that with a constant share of processors equal to q j -(n -1)ε (with n = |I |) allocated to T j during ∆, the work on T j is still strictly larger than the work on T j under P . We create the schedule Q 2 based on Q 1 : the modification is that on ∆, task j is allocated a share of q j -(n-1)ε processors, and any task i = j is allocated a share of q i +ε processors. This still respects the resource constraint as the sum of the shares has not been modified.

Then, the work of each task during ∆ is strictly larger under Q 2 than under P .

Therefore, there exists t 2 < t 2 such that for all i ,

W [t 1 ,t 2 ] i (P ) < W [t 1 ,t 2 ] i (Q 2 ). We note d = t 2 -t 2 and we create another schedule Q 3 from Q 2 .
The modification is that the share of processors allocated to task i drops to 0 at the time

t i < t 2 where W [t 1 ,t 2 ] i (P ) = W [t 1 ,t i ] i (Q 2 ). We construct a last schedule R defined on [0, M -d ]. R is equal to P on [0, t 1 ] and to Q 3 on [t 1 , t 2 ]. On [t 2 , M -d ], R(t ) is equal to P (t + d ).
For each task, the work performed with R is equal to the work performed with P . So R is a valid schedule and completes every task with a smaller makespan. Therefore, P is not optimal. Lemma 3. Let G be the parallel-composition of tasks T 1 and T 2 . Let r 1 (t ) = p 1 (t )/p(t ) (resp. r 2 (t )) be the ratio of processors allocated to T 1 (resp. T 2 ) in a RR n°8587 schedule. If p(t ) is a step function, in every optimal schedule until the graph is terminated, r 1 (t ) is constant and equal to

π 1 = 1 1 + (L 2 /L 1 ) 1/α = L 1/α 1 L 1/α 1 ∥2 .
Proof. First, we prove that r 1 (t ) is constant on any optimal schedule. Therefore, as by Lemma 1 we have r 2 (t ) = 1r 1 (t ), r 2 (t ) will also be proved constant. This results implies in particular that both tasks terminate simultaneously as the ratios never get null until the graph is terminated.

We consider an optimal schedule S , and two consecutive time intervals A and B such that p(t ) is constant and equal to p on A and q on B , and the graph is not terminated. By abuse of notations, we will also use A and B to represent the lengths of these intervals. By Lemma 2, the ratio of processors r 1 (t ) allocated to T 1 in S has a constant value r A 1 on A and r B 1 on B (these values can potentially be 0 or 1 if one task is terminated). We want to prove that r A 1 = r B 1 . Suppose by contradiction that r A 1 = r B 1 . We can assume without loss of generality that r A 1 < r B 1 . We want to prove that S is not optimal, and so that we can do the same work than S on A ∪ B in a smaller makespan.

We can assume without loss of generality that Ap α = B q α (otherwise, we can truncate one interval to decrease A or B ). We set

r 1 = r A 1 + r B 1
2 and we define the schedule S equal to S except on A ∪ B where the rate allocated to The work of task T 1 under S and under S during A ∪ B are

T 1 is r 1 , see Figure 2. S T 2 T 1 T 1 T 2 r A 1 r B 1 1 0 A B =⇒ T 2 T 1 T 1 T 2 r 1 1 0 S A B
W 1 = Ap α r A 1 α + B q α r B 1 α W 1 = r α 1 Ap α + B q α
By concavity, we have:

r B 1 α -(r 1 ) α r B 1 -r 1 < (r 1 ) α -r A 1 α r 1 -r A 1 =⇒ B q α r B 1 α -(r 1 ) α < Ap α (r 1 ) α -r A 1 α =⇒ Ap α r A 1 α + B q α r B 1 α < r α 1 Ap α + B q α =⇒ W 1 < W 1
We have the same properties for T 2 as the hypotheses are symmetric between T 1 and T 2 .

Therefore, S does strictly more work for both tasks during A ∪B , and so can be modified as in Lemma 2 to do the same work in a smaller makespan. Then, S is not optimal. Now, we want to prove that in an optimal schedule S , r 1 (t ) must be equal to π 1 and hence that the optimal schedule is unique. As p(t ) is a step function, we define the sequences (A i ) i >0 and p i i >0 such that A i is the duration of the i -th step of the function p(t ) and p(t ) = p i > 0 on A i . Therefore, the sum of A i 's is the makespan of S .

Then, as S completes both T 1 and T 2 with constant rates, if we note V = i A i p α i and r 1 the value of r 1 (t ), we have:

L 1 = i A i r α 1 p α i = r α 1 V and L 2 = i A i (1 -r 1 ) α p α i = (1 -r 1 ) α V Then, L 2 = (1 -r 1 ) α L 1 r α 1 thus r 1 = 1 1 + L 2 L 1 1/α = π 1
So the lemma is proved.

Lemma 4.

Let G be the parallel-composition of tasks T 1 and T 2 , with p(t ) a step function, and S be an optimal schedule. Then, the makespan of G under S is equal to the makespan of the task T G of length

L G = L 1 ∥2 .
Proof. We characterize p(t ) by the sequences (A i ) i >0 and (p i ) i >0 as in the proof of Lemma 3. Let ∆ be the domain of definition of S , so that ∆ = [0, τ]. As defined in Section 3, we define the functions w i (t ) representing the ratio of work done during [0, t ]:

w i (t ) = t 0 p i (x) α dx L i , such that w 1 (0) = 0 and w 1 (τ) = 1. For RR n°8587
t ∈ ∆, let k(t ) be the index such that p(t ) is in its k(t )-th step, and so p(t ) = p k(t ) . And let t be the difference between t and the starting time of the k(t )-th step. By Lemma 3, we know that the ratio of processors allocated to T 1 is constant over ∆ and equal to:

r 1 = L 1/α 1 L 1/α 1 + L 1/α 2 = L 1 /L 1 ∥2 1/α
Then, we have:

w 1 (t ) = t p k(t ) r 1 α + i <k(t ) A i p i r 1 α L 1 = t p α k(t ) + i <k(t ) A i p α i L 1 ∥2
Similarly, for T 2 , we have:

w 2 (t ) = t p k(t ) (1 -r 1 ) α + i <k(t ) A i p i (1 -r 1 ) α L 2 = t p α k(t ) + i <k(t ) A i p α i L 1 ∥2
We define w(t ) as the ratio of work that is done for the equivalent task T G of length L 1 ∥2 under the processor profile p(t ), until the task is terminated.

We have:

w(t ) = t p α k(t ) + i <k(t ) A i p α i L 1 ∥2 = w 1 (t ) = w 2 (t )
The three ratios are identical, so they all reach 1 at time τ. Then, G and T G have the same optimal makespan under any step-function p(t ).

Theorem 1. For every graph G, if p(t ) is a step function, G has the same optimal makespan than the equivalent task T G of length L G . Moreover, there is a unique optimal schedule, and it can be computed in polynomial time.

Proof. In this proof, we only consider optimal schedules. Therefore, when the makespan of a graph is considered, it is implicitly the optimal makespan. First, we have to remark that in any optimal schedule, as p(t ) is a step function and because of Lemma 2, only step functions are used to allocate processors to tasks, and so Lemma 4 can be applied on any subgraph of G without checking that the processor profile is also a step function for this subgraph.

We prove the result by induction.

• G is a single task. The result is immediate, as by Lemma 1, all the processors have to be used.

• G is the series composition of G 1 and G 2 . By induction, G 1 (resp. G 2 ) has the same makespan than task T 1 (resp. T 2 ) of length L 1 (resp. L 2 ) under any processor profile. Therefore, the makespan of the series composition of T 1 and T 2 is equal to the makespan of G. Then, it is equal to the makespan of the task of length

L G = L 1 ;2 = L 1 + L 2 .

RR n°8587

By induction, the unique optimal schedules of G 1 and G 2 under p(t ) processors can be computed, so there is a unique optimal schedule of G under p(t ) processors: the concatenation of these two schedules.

• G is the parallel composition of G 1 and G 2 . By induction, G 1 (resp. G 2 ) has the same makespan than task T 1 (resp. T 2 ) of length L 1 (resp. L 2 ) under any processor profile.

Consider an optimal schedule S of G and let p 1 (t ) be the processor profile allocated to G 1 . Let S be the schedule of (T 1 ∥ T 2 ) that allocates p 1 (t ) processors to T 1 . S is optimal and gives the same makespan as S for G because T 1 and G 1 (resp. T 2 and G 2 ) have the same makespan under any processor profile. Then, by Lemma 4, S (so S ) gives the makespan equal to the optimal makespan of

L 1 ∥2 = L G .
Moreover, by Lemma 3 applied on (T 1 ∥ T 2 ), we have p 1 (t ) = π 1 p(t ). By induction, the unique optimal schedules of G 1 and G 2 under respectively p 1 (t ) and (p(t )p 1 (t )) processors can be computed. Therefore, there is a unique optimal schedule of G under p(t ) processor: the parallel composition of these two schedules.

Therefore, in order to determine the optimal schedule of a graph G, it suffices to inductively build the equivalent task of each parallel branch and use the rate π 1 described in the proof to compute the processing power that should be given to each branch.

This makespan-minimizing problem is then solved as the optimal schedule can be computed efficiently. A critic, however, can be made on the validity of the speedup value when p < 1. Indeed, the speedup should be linear in this domain as no parallelization issue occurs and so the model overestimates it. Moreover, because of the strict concavity of the function, more work is done by a processor when it is split between several tasks, which is unrealistic. This motivated the following modification of the model, for applications where less than one processor can be used on a task.

The speedup is equal to f (p) = p when p < 1 and f (p) = p α otherwise

As motivated above, we modify in this section the speedup function when p < 1, so that f (p) = p when p < 1 and f (p) = p α otherwise. See Figure 3 for an illustration. We only study here the case where p(t ) is constant and equal to p. This modification complicates the model as optimal schedules do no longer necessarily obey the structure depicted in the previous section, as proved in Property 2. Therefore, a heuristic has been designed to approach the optimal makespan, but no performance guarantee has been proved yet.

In order to clarify the results, we define two classes of schedules, which can also be called processor allocations, as they are completely defined by the share

1 1 speed-up processors f (p) = p f (p) = p α new model
Figure 3: Speed-up in function of the processing power in different models of processors allocated to each task and the precedence constraints, and not by temporal parameters. First, the PM allocation (for Prasanna-Musicus allocation) of a graph is the allocation that associates to each task the share computed by the formulas of the previous section. Then, a PFC allocation (Processor Flow Conservation) is an allocation that associates a constant ratio of processors to each branch at every parallel node. By definition, PM allocations are necessarily PFC allocations. The motivation of the latter class is to preserve a simple structure while allowing other shares of processors than the ones defined in Subsection 4.1. Indeed, they seem general enough to offer better solutions than the PM allocation, and behaved well in our simulations. We will focus here on schedules belonging to this class, as they are easier to manipulate.

The first result, which is proved in Appendix A, shows that:

Property 1.
There exists a unique PFC allocation of minimum makespan, the one in which every siblings terminate simultaneously.

However, Property 2 states that this schedule is not always optimal among all possible schedules. Property 2. The best PFC allocation is not always the optimal schedule. This statement is still valid on pseudo-trees and for moldable tasks (tasks whose share of processor cannot vary until termination).

Proof. We present an example in which no PFC schedule is optimal, which proves the proposition. The goal is to parallelize the tree-shaped graph G of Figure 4 with p = 4 processors. One possible allocation is to allocate one processor to each of the four tasks of length 1, and then two processors to both remaining tasks. The makespan is then M = 2, and the schedule is not PFC.

In an optimal PFC schedule, a certain share 0 < x < 4 is dedicated to subgraph G 2 . We have x < 3 because with

x = 3, G 2 is completed before G 1 . The makespan of G 1 is M 1 (x) = 1+2 α (4-x)
α and is increasing with x. Each of the b 1,i tasks must receive equal shares of x 3 < 1 processors so the makespan of G 2 is M 2 (x) = 3

x + 2

x α and is decreasing with x. Then, suppose that such a schedule is makespan-optimal. There exists x e such that M 1 (x e ) = M 2 (x e ) < M . Then, for the value x 1 such that M 1 (x 1 ) = M , we must

RR n°8587 0 1 1 1 1 2 α 2 α 0 G 1 G 2 b 1,1 b 1,2 b 1,3 b 2 a 1 a 2
Figure 4: Series-parallel graph of the counter example.

have M 2 (x 1 ) < M , as x 1 > x e by the increasing of M 1 and M 2 is decreasing. But in this case, we have:

x 1 = 4 - 1 + 2 α 2 1/α
Then, we numerically verified that M 2 > M for any 0 < α < 1. So no PFC schedule is optimal.

The following result shows that PM allocations are not relevant approximations for the makespan, and so motivates the choice to study PFC allocations, which are more general.

Property 3. The PM allocation is not a constant ratio approximation for the makespan (proof: Appendix C).

Indeed, the PFC-optimal allocation seems more promising. For indication, the worst ratio observed between the makespan of the PFC-optimal allocation and another allocation is around 1.09 (see Appendix C). Therefore, in spite of the lack of established approximation ratio, this schedule seems to be a relevant approximation.

However, this schedule is again difficult to compute. We can nevertheless characterize it by a quantity ∆ P associated to a graph G and a PFC allocation P which represents the largest difference of makespan between two parallel branches and is inductively defined on G with respects to P :

• ∆ P (T ) = 0 • ∆ P (G 1 ;G 2 ) = max (∆ P (G 1 ) , ∆ P (G 2 )) • ∆ P (G 1 ∥ G 2 ) = max (∆ P (G 1 ) , ∆ P (G 2 ) , |M P (G 1 ) -M P (G 2 )|) where M P (G i
) is the makespan of G i under schedule P . The characterization is the following.

Property 4. A PFC allocation P is optimal if and only if ∆ P = 0 (Proof: Appendix A).

RR n°8587

A way to compute this schedule is to start from the PM allocation, which underestimates the makespan of tasks to whom less than 1 processor has been allocated. Then, the idea is to rebalance the allocation of the deepest parallel connections whose branches have different makespans. However, this strategy needs to predict the makespan of a subgraph for a given processor power, in order to balance large branches, which cannot be done efficiently.

Therefore, we design the heuristic depicted in Algorithm 1. The idea is, instead of rebalancing the allocation, to artificially modify the length of underestimated tasks in order to counterbalance the errors made by the PM allocation.

If L i is the length of an underestimated task and p i < 1 the share allocated to it, the updated length L should verify L/p α i = L i /p i so that both makespans are equal: the one expected by the PM allocation, L/p α i and the real one, L i /p i . Therefore, we have L = L i p α-1 i . However, in the updated allocation, p i will likely take a different value, either larger or smaller. That's why the heuristic needs to iterate this step, until convergence.

The principle is to permanently mark at each step tasks with p i < 1, and update their length before computing the new PM allocation. If some p i become greater than 1, the length should then be decreased as the PM allocation now overestimates this makespan, hence the if-then statement.

Input: a graph G with the length L 0 i of each task i , the parameter α and a processing power p Output: A PFC processor allocation of G compute the PM allocation into the p 0 i 1 j ← 0

j -1 i < 1 then 7 L j i ← L 0 i • p j -1 i α-1 8 else 9 L j i ← 1/2 L 0 i + L j -1 i 10
compute the PM allocation and save it in the p j i 's 11 Algorithm 1: Heuristic to approach the optimal PFC allocation The heuristic has been implemented and tested on a large variety of SP graphs, either designed manually or generated randomly among SP graphs including a thousand tasks. This allows to have a good intuition of the relevance of this heuristic. However, it is does not prove its correctness as the tested graphs RR n°8587 do not represent a significant part of this family and so critical cases may not have been scanned. Nevertheless, on every studied example, the heuristic converged towards the optimal PFC allocation whenever α > 1/2. The convergence can indeed be verified by computing the value ∆ P , which tends towards 0 if and only if the heuristic converges towards the expected schedule.

A conjecture derived from these observations is the following.

Conjecture 1. For α > 1/2, during the execution of the algorithm, both sequences ∆ 2 j P j and ∆

2 j +1 P j decrease, and so have a limit. These limits are both equal to 0 and thus the algorithm converges to the optimal PFC schedule.

The difficulty for proving this conjecture is that the whole allocation vary at each step, and the property links step j with step j + 2, independently from step j + 1. It has been proven for the particular case the parallel composition of two tasks (see Appendix B), but the proof seems difficult to generalize.

For α < 1/2, the heuristic does not converge on various examples, which can be explained by a too large error made by the PM allocation. However, in practice, we should have α > 1/2 so this is not a critical issue.

Makespan and memory minimizing schedules

In this section, we take into account the memory needed to execute a task tree. If the memory bound is not a crucial constraint on standard computers, it can become very restraining on platforms housing many processors. Indeed, some algorithms of sparse matrix factorizations, such as multifrontal methods, have high memory costs. Therefore, we need not only to minimize the makespan, but also to prevent an execution from exceeding a memory bound.

As explained in Section 2, we show here negative complexity results in a model similar to the one studied in [START_REF] Marchal | Scheduling tree-shaped task graphs to minimize memory and makespan[END_REF] without task parallelization, but we do not achieve to use a fully homogeneous model as in that paper. Therefore, the theorems proved here are slightly weaker than their analogues from [START_REF] Marchal | Scheduling tree-shaped task graphs to minimize memory and makespan[END_REF], because more flexibility in the input is necessary to achieve the complexity results. This difference is due to the freedom induced by the task parallelization which allows less control on optimal schedule behaviors with the same constraints.

Description of the model and preliminary lemma

In this section, the objective is to schedule a tree G under a fixed processor profile p(t ) = p. Each node T i has a length L i and an output file of size f i that is used as input by its parent if T i is not the tree root. Actually, nodes can also have execution files n i but these can be supposed null, as explained below. The speedup is equal to f (p) = p α , even when p < 1.

We have here an additional constraint when compared to the model without memory. During the execution of T i , the memory must contain its execu-tion, output and its input files (the output files of its children), which leads to a memory occupation for task T i of:

Mem ex i = j ∈Children(T i ) f j + n i + f i
Moreover, the output file of a node must be kept in memory: it cannot be released until the termination of its parent. With this definition, n i can indeed be set to 0 and simulated by an additional child of null length and output file equal to n i . Therefore, we now assume that all n i 's are equal to 0. The objective is to minimize the makespan, which has already been defined, and the memory peak Mem peak . This latter quantity is the maximum amount of memory needed among all time steps. The memory needed at a time t , Mem t , is equal to the sum of all the Mem ex i of the tasks T i that are being executed at time t , plus all the output files that must remain in memory because a node has been processed but the processing parent is not initiated yet. More formally, we have:

Mem t =   i | 0<w i (t )<1 Mem ex i   +    i w parent(T i ) (t )=0 and w i (t )=1 f i   
In order to work with schedules obeying to such memory constraints, we first need the following general lemma which gives us a characterisation of makespan-optimal schedules when a bound on the maximum parallelization is imposed.

Lemma 5. For all x, n ∈ N × and for all p > n, if we have xn independant tasks of length 1 to process in parallel with xp processors and we cannot execute more than x nodes at any time, a schedule is makespan-optimal if and only if it processes at any time x nodes in parallel using equal maximal shares of processors.

Proof. Let S be a schedule with makespan M . We know by Lemma 2 that the shares follow step functions: on clean intervals, optimal schedules allocate constant ratios of processors to each task. Indeed, the constraint on the maximal number of nodes to process in parallel does not contradict the hypotheses of the lemma. Similarly, we know by Lemma 1 that makespan-optimal schedules use all processors at any time, so we only consider such schedules here. Therefore, when a schedule allocates equal shares to x processors, it allocates p/x processors to each task.

The purpose is to show that either S always processes x nodes in parallel with equal shares and has the same makespan than any other such schedule, or its makespan is larger than such a schedule. We first show an analogous property on a small interval where all the shares are constant before generalizing the result.

Let A be a time interval in which all the shares are constant. By abuse of notations, we will also use A to represent the length of this interval. Suppose the distribution of the x involved tasks among the processors is represented by the shares (a i ) 1≤i ≤x (we can potentially have some of them equal to 0). Then, the total work performed during A is W A = A x i =1 a α i . Suppose that we have i , j such that a i < a j . Let ã = 1 2 (a i + a j ) and d a = 1 2 (a ja i ). Let S be the schedule defined on A that is equal to S on A except that it associates a share ã to both tasks i and j , and let W A be the total work performed during A by S . As the function t → t α is strictly concave, we have:

W A -W A A = 2 ãα -a α i -a α j = d a ãα -a α i ã -a i - a α j -ãα a j -ã > 0
Then, S has a total work larger than S during A. Therefore, the unique schedule (up to a permutation of processors) that maximizes the total work performed during A, with the x involved tasks fixed, is the one that allocates the same share to all x tasks. Let S eq be a schedule that finishes every task and allocates equal shares to x tasks at any time. Let M eq be its makespan and M n be the minimum of M and M eq . We can partition the interval of time ∆ n = [0, M n ] in time intervals {A i } such that both S and S eq are constant on each A i .

On A i , if S allocates equal shares to the x tasks involved, the total work of S and S eq is equal. Otherwise, we have shown that the total work of S eq is larger than the total work of S on A i . We then have two cases:

• if for all A i , S allocates equal shares to the x tasks involved, then the total works of S and S eq are equal on ∆ n . Therefore, M = M eq . • otherwise, let A i be an interval that contradicts the previous statement.

Let W eq ∆ n and W ∆ n be the total work of both schedules during ∆ n . We have

W eq ∆ n -W ∆ n = W eq A i -W A i + j =i (W eq A j -W A j ) ≥ W eq A i -W A i > 0
Then, S is not terminated at time M n so M eq < M and S is not makespanoptimal. To conclude, S eq is makespan-optimal so S is makespan-optimal if and only if it processes at any time x nodes in parallel at equal maximal shares of processors.

NP-completeness of the bi-objective problem

We now state the decision problem combining minimisation of both makespan and memory: Definition 2 (BiObjectiveParallelTreeScheduling). Given a task tree G provided with memory weights and task durations, p processors, and two bounds B C and B Mem , is there a schedule of the task tree on the processors whose makespan is not larger than B C and whose memory peak is not larger than B Mem ?

This problem allows any parameters f i and L i . Actually, in order to show the NP-completeness of this problem, we can restrict ourselves to the case where all the output files f i have the same size, 1, and the lengths L i either have the same value, 1, or are null. Without task parallelisation, in [START_REF] Marchal | Scheduling tree-shaped task graphs to minimize memory and makespan[END_REF], the difference is that the L i can be restricted to have the same value, 1.

Theorem 2. The BiObjectiveParallelTreeScheduling problem is NP-Complete in the following model: ∀i

f i = 1, n i = 0, L i ∈ {0, 1}.
Proof. First, the problem clearly belongs to NP.

Then, we reduce the problem from 3-PARTITION which is unary NP-Complete [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF]. Let I 1 be the following instance of 3-PARTITION: let B be an integer and a 1 , . . . , a 3m be 3m integers such that i a i = mB and for all i , B /4 < a i < B /2. The problem is to find whether there exists a partition of the a i 's in m subsets S 1 , . . . , S m each of cardinal 3, such that for all k, i ∈S k a i = B .

Consider the instance I 2 illustrated on Figure 5. The tree T contains a root r with 3m children N 1 , . . . , N 3m , each corresponding to a value a i . Each node N i has 3m × a i children T i x , which are leaf nodes. The execution time of the leaves and the root are 0 and the execution time of the other nodes are 1. The question is to find a schedule of this tree on p > 3 processors, whose memory peak is not larger than B Mem = 3mB + 3m and whose makespan is not larger than

B C = m(3/p) α . r N 1 T 1 1 T 1 2 T 1 3ma1 N 2 T 2 1 T 2 2 T 2 3ma2 N 3m T 3m 1 T 3m 2 T 3m 3ma3m 0 0 0 0 0 0 0 0 0 0 1 1 1
Figure 5: Tree T used for establishing Theorem 2, with execution times written in red.

Assume first that there exists a solution S 1 , . . . , S m to I 1 . We build the schedule Opt({S n }) for I 2 , assuming that S n = {a i n , a j n , a k n }:

• step 1: process the nodes T i 1 x , T j 1 y , T k 1 z for 1 ≤ x, y, z ≤ 3ma i 1 in
time 0 and using 3mB units of memory.

• step 2: process the nodes N i 1 , N j 1 , N k 1 in time (3/p) α and using memory 3mB + 3

• step 2n+1 with 1 ≤ n ≤ m -1: process the nodes T i n x , T j n y , T k n
z in time 0 and using 3mB + 3n units of memory.

• step 2n+2 with 1 ≤ n ≤ m-1: process the nodes N i 1 , N j 1 , N k 1 in time (3/p) α
and using memory 3mB + 3(n + 1) ≤ B Mem • step 2m+1: process the root node in time 0 and using memory 3m + 1.

RR n°8587

Thus, the memory peak is B Mem and the makespan is B C so I 2 is solvable. Now, assume there exists a solution to I 2 . We will show that I 1 is solvable. Consider a makespan-optimal schedule of I 2 with a memory peak not larger than B Mem .

First, there exists a schedule with the same makespan and a not larger memory peak that processes for any i ∈ [1; 3m] all T i

x leaves with x ∈ [1; 3m × a i ] right before N i . Indeed, the execution file and the execution time of each leaf T i

x is null so postponing the execution of such a node until the execution of its parent does not modify the makespan and cannot increase the memory peak. We now consider this schedule S .

As for any i , a i > B /4, we can never process in parallel 4 nodes N i at the same time, because the sum of the corresponding a i 's will not be smaller than B + 1 and the memory peak would be at least 3m × (B + 1) + 4 > B Mem . So, at any time, at most 3 of the N i nodes are processed. We will refer to this memory constraint as CST 3N i .

By Lemma 5, a schedule Opt({S n }) with an arbitrary partition of the a i 's into m triples S 1 , . . . , S m is makespan-optimal among the schedules that respect CST 3N i (regardless of other memory constraints). Indeed, by Lemma 5, a makespan-optimal schedule of the nodes N 1 . . . N 3m that respects CST 3N i processes the N i nodes in groups of 3, and has then a makespan equal to B C , which is the makespan of Opt({S n }). So the makespan of S is not smaller than B C and it is furthermore equal to B C as S is a solution of I 2 . Then, S is makespanoptimal among the schedules that respect CST 3N i so, by Lemma 5, it processes at any time 3 nodes N i in parallel using equal shares of processors.

Because of CST 3N i , there cannot be any preemption (i.e., begin the processing of a task, idle it and continue it later) because this would mean at least 4 of the N i nodes running in parallel (with one being allocated a processor share of 0 during a time interval) as the memory footprint is conserved during the preemption. Therefore, S executes consecutively groups of three tasks, allocating p/3 processors to each one. So there exists a partition {S n } 1≤n≤m such that S = Opt({S n }). Then, because of memory constraints, for all n, a i ∈S n a i ≤ B and so I 1 is solvable.

Inapproximation results

As the bi-objective problem is NP-complete in this restrained model, the next step is to study the existence of approximation algorithms in the same model. Theorem 3 states that no approximation exists with constant factors for both makespan and memory peak, that is, with ratios that are independent of the number p of available processors. Theorem 3. There is no algorithm A that is both a β-approximation for makespan minimization and a γ-approximation for memory peak minimiza-tion when scheduling in-tree task graphs in the model: for all i , f i = 1, n i = 0, L i ∈ {0, 1}.

Proof. Suppose that A is such an algorithm. Without loss of generality, we suppose that β and γ are integers.

We consider the tree of Figure 6 to be scheduled with p = δn processors. The root has n children N 1 . . . N n which each have δ children T i 1 . . . T i δ . Only the T i x leaves have a non null execution time, which is equal to 1. The values δ and n will be fixed later.

r Optimal makespan. We have only δn tasks of non null execution time, so by Lemma 5, the optimal makespan is equal to Opt C = (nδ/p) α = 1.

N 1 T 1 1 T 1 2 T 1 δ N 2 T 2 1 T 2 2 T 2 δ N n T n 1 T n 2 T n δ 0 1 1 1 1 1 1 1 1 1 0 0 0
Optimal memory peak. The optimal memory peak is δ + n, by completing the subtrees one after the other.

Contradiction with A . We set δ = γn 2 and we let n be a multiple of (γ + 1). By definition of A , its memory peak is not larger than

Mem = γ(δ + n) = δ(γ + nγ/δ) = δ(γ + 1/n) < δ(γ + 1)
Then, we cannot process more than ∆ = δ(γ + 1) leaves at any time. We will refer to this constraint as CST ∆ .

The makespan of A is not smaller than the makespan of a makespanoptimal schedule B that processes the δn leaves under constraint CST ∆ .

By Lemma 5, as ∆ divides δn, B processes ∆ tasks at any time, allocating p/∆ = δn/∆ processors per task. There are δn tasks in total, so δn/∆ groups of ∆ tasks. The makespan of B is then equal to:

M B = δn ∆ ∆ δn α = n γ + 1 1-α
Therefore, there exists n, multiple of (γ + 1), such that M B > β and so the makespan of A is larger than βOpt C which is a contradiction with the definition of A .

In this theorem, we restrained ourselves to constant ratio approximations. We now give a lower bound in Theorem 4 on approximation ratios that can depend on p. Theorem 4. When scheduling in-tree task graphs with p processors, there is no algorithm A that is both a β(p)-approximation for makespan minimization and a γ(p)-approximation for memory peak minimization in the model: for all i , f i = 1, n i = 0, L i ∈ {0, 1} with β(p) and γ(p) verifying:

γ(p)β(p) 1-α ≤ p log p + 1 1-α
Proof. Suppose that A is such an algorithm.

We consider the tree of Figure 7 to be scheduled with p = 2 p processors. The tree is binary and complete over a depth of n = p . There are then N = 2 n = p leaves. Only the leaves have a non null execution time, which is equal to 1. Optimal makespan. By Lemma 5, a makespan-optimal schedule executes the N leaves in parallel, with 1 processor per task, and takes a time Opt C = 1.

Optimal memory peak. By completing the tasks following a postorder search, we get a memory peak of Opt M = n +1, which is optimal as any schedule reaches at least this peak during the execution of the last leaf. For indication, an example of a postorder is the order the tasks of a tree G are visited by the recursive algorithm postorder(G): 1) call postorder on the left subtree -2) call postorder on the right subtree -3) visit the root.

C ≥ N Opt M β(p) Opt M β(p) p α ≥ p Opt M β(p) 1-α ≥ p Opt M β(p) 1-α
Then, the makespan of A is larger than C as it must obey stricter memory constraints, because of the memory consumed by non-leaf tasks. Thus,

γ(p)β(p) 1-α > C Opt C β(p) 1-α ≥ p Opt M 1-α = p log p + 1 1-α
Hence the bound.

When disabling task parallelization, in [START_REF] Marchal | Scheduling tree-shaped task graphs to minimize memory and makespan[END_REF], which is in this proof equivalent to state α = 0, the bound proved on the factors of approximation was:

γ(p)β(p) > 2p log p + 2
With α = 0, the bound proved in this report is:

γ(p)β(p) > p log p + 1
Therefore, this bound is approximately two times smaller than the one of [START_REF] Marchal | Scheduling tree-shaped task graphs to minimize memory and makespan[END_REF] on similar cases, so it is not tight. The gap is explained by the difficulty to find a more precise characterization of makespan-optimal schedules than the one of Lemma 5, whereas without task parallelisation, their structure is easier to study.

Conclusion

In this report, we have re-established the results of [START_REF] Prasanna | Generalized multiprocessor scheduling and applications to matrix computations[END_REF] for minimizing the makespan with a speedup of p α with pure scheduling techniques. This work is relevant as optimal control theory was used in that paper to achieve the same results, which requires too much formalism and artefacts such as approximations of step functions into continuous functions which are actually not necessary to establish in this theorem. Its proof is now decomposed in lemmas which can be proved step by step by pure scheduling techniques and gives an overview on the foundations of the theorem. We have also proposed a refinement of the model, which is more realistic for applications allocating less than one processor to some tasks, but complicates the computation of the optimal schedule. An algorithm has been proposed to find an approximation of this schedule when α > 1/2, but if it behaves satisfactorily on every example tested, no formal proof has been obtained.

Then, we presented the first study that combines makespan and memory constraints together with parallelizable tasks. We achieved to reproduce theorems analogous to state-of-the-art results without task parallelization, which state the complexity of the problem.

In short term future work, it remains to prove the convergence and the approximate ratio of the algorithm of Section 4. In the long term, it would be interesting to develop a heuristic allowing a compromise between minimizing the makespan and the memory peak, for example with a guaranteed bound on the memory peak. Finally, an experimental validation of the proposed heuristics would be very desirable, and we have reasonable hope that at least some of them will be tested in the context of the SOLHAR project. This way, in the optimal schedule we have p A < 1 < pB , with p A (resp. pB ) being the share of processors allocated to A (resp. B ). Indeed, suppose p A = 1. Then, as A < B , we have A/1 = B /(p -1) α , so B /A = (p -1) α . Therefore, p A < 1 is implied by B /A > (p -1) α . Then, similarly, to ensure pB > 1, we need A/B < (p -1).

During the execution of the algorithm, for all α ≥ 0.5 and for all j , we will consecutively prove that we have:

1. if p 0 A ≤ p j A < 1, then p j +1 A < 1 2. p 2 j A < p 2 j +2 A < p 2 j +3 A < p 2 j +1 A 3. p j A converges towards p A Claim 1. if p 0 A ≤ p j A < 1, then p j +1 A < 1.
Proof. First, we compute q such that if we replace A by A • qα-1 and compute the PM schedule, we will obtain p A = 1. Then, if p j A > q, we will obtain p j +1

A < 1. We have:

A qα-1 1 = B (p -1) α q = (p -1) α A B 1/(1-α) < 1
We have p for j = 0. Suppose the result true for all k < j . Results involving negative indices are supposed true by convention, so the result is true for all k < 0.

We will show that p ) α . In order to simplify the formulas, we denote q j . = p j A and we replace 2 j by j . Because of Claim 1, as we know that q j > q 0 , we know that q j +1 < 1. By definition of A j +1 and q j +1 , we have RR n°8587

A j +1 = A 0 q α-1 j > A 0 A j +1 q α j +1 = B
pq j +1 α A 0 q j q j q j +1 α = B pq j +1 α A 0 q j +1 = B pq j +1 α q j q j +1 1-α Let's show that q j +1 > q j . We have

A 0 q j < B p -q j α A 0 q j = B
pq j +1 α q j +1 q j α then q α j pq j α > q α j +1

pq j +1 α Therefore, q j +1 > q j and so A 0 q j +1 < B (p-qj+1) α . Then, by Claim 1, q j +2 < 1. At the next step, A j +2 = A 0 q α-1 j +1 . So, A 0 < A j +2 < A j +1 . By similar formulas, we show that A 0 q j +2 < B (p-qj+2) α . If j = 0, we have A j < A j +2 . Otherwise, we know by induction that q j +1 < q j -1 . Therefore, we also have the result q j < q j +2 < q j +1 . At the following step, A j +3 = A 0 q α-1 j +2 . So A j +1 > A j +3 > A j +2 .

Claim 3. p j

A converges towards p A .

Proof. We know that A 2 j and A 2 j +1 both converge, to A e and A o .

We have

A e = Aq α-1 o A o = Aq α-1 e B (p -q o ) α = B (p -q e ) α q e q o α q o q e (1-α) q 2α-1 o (p -q o ) α = q 2α-1 e (p -q e ) α
As α ≥ 1/2, by monotonicity, we must have q o = q e and then A j converges towards a value A x . In the PM schedule S PM , 3n/2 processors are dedicated to each subgraph. So the nodes a i 's and b i , j 's have a makespan of M P M a = 2(B + 1)/3. Indeed, the n nodes b 1, j 's are equivalent to a task of length n α so they are allocate a fraction 1/(B + 1) of the available processors, which is 3n/(2B + 2). Therfore, the ratio M P M a /M S grows to the infinity as B increases, and so S PM is not a constant ratio approximation of S .

In the optimal PFC schedule S , 3n/2 processors are allocated to each branch as they are equivalent. Then, as for S , replacing 2 by 3/2, we get that the share x allocate to each b i , j is x = 1+6B -1

2B

. So the makespan for nodes a i 's and b i , j 's is M a = 1.0159. When looking for the worse approximation ratio between of a PFC allocation, we have designed a recursive structure G x to increase the error made by PFC allocations. This structure is basically describe by the following process: G 0 equals G where B = 1 and n = 2, and G x is similar to G 0 where nodes a i and c i are replaced by G x-1 and the lengths of b i , j 's are changed. In simulation, the approximation ratio between the best PFC schedule (computed by the heuristic, and certified by the value of ∆) and a schedule similar to S has raised to approximately 1.09, which is the largest PFC approximation ratio observed.

RR n°8587

RESEARCH CENTRE GRENOBLE -RHÔNE-ALPES

Figure 1 :

 1 Figure 1: Example of a tree completed in an SP graph.

Figure 2 :

 2 Figure 2: Schedules S and S on A ∪ B . The abscissae represent the time and the ordinates the ratio of processing power.

2 while not converging do 3 j ← j + 1 4mark

 231

Figure 6 :

 6 Figure 6: Tree used for establishing Theorem 3, with execution times written in red.

Figure 7 :

 7 Figure 7: Tree used for establishing Theorem 4 for n = 3, with execution times written in red.

1 Claim 2 .

 12 For all j , p We prove the result by induction on j . We have A p

1 2B. 1 .

 11 M a = (B n) α /(2nnx) α = (B /(2x)) 1/2 . Then, we have 1/x 2 = B /(2x) and so x = 1+8B -So we have M a = M b = 2B 1+8B -We set L = M a n α . Then, the makespan of S is M S = 2M a = 4B 1+8B -1.

2B 1+6B - 1 . 1 .

 11 And the makespan of ci 's is M c = For B = 1, we obtain (M c + M a )/M S =

  Inovallée 655 avenue de l'Europe Montbonnot 38334 Saint Ismier Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr

  Contradiction with A . By definition, the memory of A is not larger than M =

	Opt M β(p). We can assume that β(p) ≤ p/Opt M because as γ(p) ≥ 1, the aimed
	bound would be verified otherwise.
	By Lemma 5, under this memory bound, a makespan-optimal algo-
	rithm handling only the leaves executes the leaves by parallelizing groups of p Opt M β(p) tasks. The makespan of the execution of one group is Opt M β(p) α
	and there are at least

N

Opt M β(p) groups. The overall makespan is then RR n°8587

RR n°8587

Appendix A: Proof of Properties 1 and 4

We prove here that there is a unique PFC-optimal allocation, which is the unique PFC allocation that respects ∆ P = 0.

Proof. In this proof, we need a partial order on the parallel nodes of the graph G. We define the order : b a if the node b belongs to the subtree rooted in a.

First, we show that for any PFC-optimal schedule P , we necessarily have ∆ P = 0. Suppose the contrary. Let P be a PFC-optimal schedule that has a difference of makespan at one parallel node, such that no PFC-optimal schedule has a difference of makespan at a strictly smaller parallel node (according to the order ).

Then, by rebalancing the processors among the two branches of this node, we can achieve a smaller makespan in this subgraph with the same share of processors. We now have two cases. First, there is no parallel composition above this node, and the new schedule has then a smaller makespan. Otherwise, there is a parallel composition above this node, and the new schedule has the optimal PFC makespan, and has a difference of makespan in a smaller parallel composition than P , which violates the hypothesis. We have a contradiction, and so ∆ P = 0. Now, we prove that there is exactly one schedule P using all the processors with ∆ P = 0. This implies by Lemma 1 that the PFC-optimal makespan is unique.

This statement is proven by induction on the structure of G, with the hypothesis: for all G, there is a unique schedule using all the processors with ∆ P = 0 for any value of p, and the makespan decreases in function of p. Then, at a parallel composition, there is only one point of equilibrium between the makespans of the two branches and so the induction is validated.

Appendix B: Convergence of the heuristic in the case of two parallel tasks

We prove here the convergence of the heuristic presented in Algorithm 1 towards the optimal PFC schedule, for the parallel composition of two tasks T A and T B of respective lengths A and B (with A < B ) in the most difficult case, when A/B < (p -1) α < B /A. Indeed, in other cases, either both tasks need more than one processor in the optimal schedule, or they both need less than one. In the first case, the heuristic returns the optimal PM schedule. In the second case, its behavior can be proved by arguments similar to the following ones.

We study two parallel tasks T A and T B , to be scheduled with p > 1 processors such that:

A/B < (p -1) and (p -1) α < B /A Therefore,

Appendix C: Approximate ratios of PM and PFC schedules

The goal here is to prove that with α = 1/2, the PM allocation is not a constant ratio approximation for the makespan and no PFC allocation is a 1.09approximation for the makespan. To achieve this goal, we consider the graph G of Figure 8 to schedule with 3n processors. n and B are parameters of the problem, with n > 0 and B > 1. The lengths of c 1 and c 2 , equal to L, will be defined later.

Consider the schedule S , allocating 2n processors to each group of a i , b i , j 's and n to each c i (the length L will be set such that all the nodes have the same makespan and so this exchange of processors between the branches is possible without loss of makespan). We want the a i 's and b i , j 's to have the same makespan. Let x < 1 be the share of processors allocated to each b i , j . Then, the makespan of each b i , j is M b = 1/x and the makespan of each a i is