Guillaume Aupy

Clément Brasseur

Loris Marchal

Dynamic memory-aware task-tree scheduling

Keywords: scheduling, memory, trees ordonnancement, mémoire, arbres. 15

Factorizing sparse matrices using direct multifrontal methods generates directed treeshaped task graphs, where edges represent data dependency between tasks. This paper revisits the execution of tree-shaped task graphs using multiple processors that share a bounded memory. A task can only be executed if all its input and output data can fit into the memory. The key difficulty is to manage the order of the task executions so that we can achieve high parallelism while staying below the memory bound. In particular, because input data of unprocessed tasks must be kept in memory, a bad scheduling strategy might compromise the termination of the algorithm. In the single processor case, solutions that are guaranteed to be below a memory bound are known. The multi-processor case (when one tries to minimize the total completion time) has been shown to be NP-complete. We present in this paper a novel heuristic solution that has a low complexity and is guaranteed to complete the tree within a given memory bound. We compare our algorithm to state of the art strategies, and observe that on both actual execution trees and synthetic trees, we always perform better than these solutions, with average speedups between 1.25 and 1.45 on actual assembly trees. Moreover, we show that the overhead of our algorithm is negligible even on deep trees (10 5 ), and would allow its runtime execution.

Introduction

Parallel workloads are often modeled as task graphs, where nodes represent tasks and edges represent the dependencies between tasks. There is an abundant literature on task graph scheduling when the objective is to minimize the total completion time, or makespan. However, with the increase of the size of the data to be processed, the memory footprint of the application can have a dramatic impact on the algorithm execution time, and thus needs to be optimized. This is best exemplified with an application which, depending on the way it is scheduled, will either fit in the memory, or will require the use of swap mechanisms or outof-core. There are very few existing studies that take into account the memory footprint when scheduling task graphs, and even fewer of them targeting parallel systems.

In the present paper, we consider the parallel scheduling of rooted in-trees. The vertices of the trees represent computational tasks, and its edges represent the dependencies between these tasks, which are in the form of input and output data: each task requests for its processing all the data produced by its children tasks to be available in memory, and outputs a new data for its parent. We want to process the resulting task tree on a parallel system made of p computing units, also named processors, sharing a global memory of limited size M . At any time, the size of all the data currently produced but not yet consumed cannot exceed M . Our objective is to minimize the makespan, that is, the total time needed to process the whole task tree, under the memory constraint.

The motivation for this work comes from numerical linear algebra, and especially the factorization of sparse matrices using direct multifrontal methods [START_REF] Davis | Direct Methods for Sparse Linear Systems. Fundamentals of Algorithms[END_REF]. During the factorization, the computations are organized as a tree workflow called the elimination tree, and the huge size of the data involved makes it absolutely necessary to reduce the memory requirement of the factorization. Note that we consider here that no numerical pivoting is performed during the factorization, and thus that the structure of the tree, as well as the size of the data are known before the computation really happens.

In this paper, we mainly build on two previous results. On the theoretical side, we have previously studied the complexity of the bi-criteria problem which considers both makespan minimization and peak memory minimization [START_REF] Eyraud-Dubois | Parallel Scheduling of Task Trees with Limited Memory[END_REF], and we have proposed a few heuristic strategies to schedule task trees under hard memory constraints. However, these strategies requires strong reduction properties on the tree. An arbitrary tree can be turned into a reduction tree, but this increases its memory footprint, which limits the performance of the scheduler under memory constraint. On the practical side, Agullo et al. [START_REF] Agullo | Multifrontal QR Factorization for Multicore Architectures over Runtime Systems[END_REF] uses a simple activation strategy to ensure the correct termination of a multifrontal QR factorization, whose task graph is an in-tree. Both approaches have drawbacks: the first one artificially increases the peak memory of the tree, and the second one overestimates the memory booked to process a subtree. Our objective is to take inspiration from both to design a better scheduling algorithm.

Note that we are looking for a dynamic scheduling algorithm, that is, a strategy that dynamically reacts to task terminations to activate and schedule new nodes. We suppose that only the tree structure and the data sizes are known before the execution, not the task processing times, so that one cannot rely on them to build a perfect static schedule. Finally, the scheduling complexity should be kept as low as possible, since scheduling decision need to be taken during the computation without delaying the task executions.

Our contributions are as follows:

• We provide a novel heuristic along with a proof of its termination for memory bounds.

• We provide data-structure optimizations to improve its computational complexity.

• We provide a thorough experimental study, both on actual and synthetic trees to show its dominance over state of the art algorithms.

• We propose a new makespan lower bound for memory-constrained parallel platforms.

The rest of the paper is organized as follows. We first present the problem, its notation and formalize our objective in Section 2. We then review related work and the two existing approaches listed above in Section 3. Next, we present our new scheduling algorithms, as well as the proof of its correctness in Section 4. Then, we propose a memory-aware makespan lower bound in Section 6. Finally, we present a set of comprehensive simulations to assess the benefit of the new algorithm 7, before presenting concluding remarks in Section 8 2 Model and objectives

Application model

Let T be a rooted in-tree (dependencies point toward the root) composed of n nodes, the tasks, denoted by their index 1, . . . , n. A node i is characterized by its input data (one per child), its execution data (of size n i ), and its output data (of size f i ). When processing node i, all input, execution and output data must be allocated in memory. At the termination of node i, input and execution data are deallocated, and only the output data stays in memory. We denote by Children(i) the set of children of node i, which is empty is i as a leaf. The memory needed for the processing of node i, illustrated on Figure 1, is given by:

MemNeeded i =   j∈Children(i) f j   + n i + f i .
(1)

Platform model

We consider a shared-memory parallel platform, composed of p homogeneous processors onto which each task can be computed. Those processors share a limited memory of size M .

Objectives

Our objective here is to minimize the makespan, that is the total execution time, while keeping the size of the data stored in memory below the bound M . This problem is a variant of the bi-criteria problem which aims at minimizing both the makespan and the peak memory. Note that those two objective are antagonist: the best way to minimize the makespan is to parallelize as much as possible without regard to the memory used, while the best way to minimize the peak memory used is to execute the whole schedule on a single processor which would give the worse makespan. In a previous study [START_REF] Eyraud-Dubois | Parallel Scheduling of Task Trees with Limited Memory[END_REF], we have proven that this bi-criteria problem was NP-complete and inapproximable within constants factors of both the optimal memory and the optimal makespan. Our variant clearly inherits this complexity and in this study, we are mainly looking for heuristic solutions.

Note that the algorithms under considerations are natural candidates to replace the simple activation scheme of [START_REF] Agullo | Multifrontal QR Factorization for Multicore Architectures over Runtime Systems[END_REF]. Thus, their runtime complexity is critical, as we want to take scheduling decisions very fast. While a notable, say quadratic, complexity is acceptable in the initial preprocessing phase, we are looking for O(1) complexity at each task termination, or eventually logarithmic.

Related work and existing algorithms

Memory and storage have always been a limited parameter for large computations, as outlined by the pioneering work of Sethi and Ullman [START_REF] Sethi | The Generation of Optimal Code for Arithmetic Expressions[END_REF] on register allocation for task graphs. In the realm of sparse direct solvers, the problem of scheduling a tree so as to minimize peak memory has first been investigated by Liu [START_REF] Joseph | On the storage requirement in the out-of-core multifrontal method for sparse factorization[END_REF] in the sequential case: he proposed an algorithm to find a peakmemory minimizing traversal of a task tree when the traversal is required to correspond to a postorder traversal of the tree. A follow-up study [START_REF] Joseph | An application of generalized tree pebbling to sparse matrix factorization[END_REF] presents an optimal algorithm to solve the general problem, without the postorder constraint on the traversal. Postorder traversals are known to be arbitrarily worse than optimal traversals for memory minimization [START_REF] Jacquelin | On Optimal Tree Traversals for Sparse Matrix Factorization[END_REF]. However, they are very natural and straightforward solutions to this problem, as they allow to fully process one subtree before starting a new one. Therefore, they are widely used in sparse matrix software like MUMPS [START_REF] Amestoy | A fully asynchronous multifrontal solver using distributed dynamic scheduling[END_REF][START_REF] Amestoy | Hybrid scheduling for the parallel solution of linear systems[END_REF], and achieve good performance on actual elimination trees [START_REF] Jacquelin | On Optimal Tree Traversals for Sparse Matrix Factorization[END_REF].

The problem of scheduling a task graph under memory or storage constraints also appears in the processing of scientific workflows whose tasks require large I/O files. Such workflows arise in many scientific fields, such as image processing, genomics, and geophysical simulations. The problem of task graphs handling large data has been identified by Ramakrishnan et al. [START_REF] Ramakrishnan | Scheduling Data-IntensiveWorkflows onto Storage-Constrained Distributed Resources[END_REF] who propose some simple heuristics. In the context of quantum chemistry computations, Lam et al. [START_REF] Lam | Memory-optimal evaluation of expression trees involving large objects[END_REF] also consider task trees with data of large size.

Note that peak memory minimization is still a crucial question for direct solvers, as highlighted by Agullo et al. [START_REF] Agullo | Robust Memory-Aware Mappings for Parallel Multifrontal Factorizations[END_REF], who study the effect of processor mapping on memory consumption for multifrontal methods.

We now review the two scheduling strategies from the literature that target our problem.

Simple activation heuristic

Agullo et al. [START_REF] Agullo | Multifrontal QR Factorization for Multicore Architectures over Runtime Systems[END_REF] use a simple activation strategy to ensure that a parallel traversal of a task tree will process the whole tree without running out of memory. The first step is to compute a postorder traversal, such as the memory-minimizing traversal of [START_REF] Joseph | On the storage requirement in the out-of-core multifrontal method for sparse factorization[END_REF]. This postorder traversal, denoted by AO, will serve as an order to activate tasks. This solution requires that the available memory M is not smaller than the peak memory M AO of the activation order. The strategy is summarized in Algorithm 1. The activation of a task i consists in allocating all the memory needed for this tasks. Then, only tasks that are both activated and whose dependency constraints are satisfied (i.e., all predecessors in the tree are already processed) are available for execution. Another scheduling heuristic may be used to choose which tasks the among available ones are executed: we denote by EO the order giving the priority of the tasks for execution. Note that available nodes are nodes whose children have been completed.

This simple procedure is efficient to schedule task trees without exceeding the available memory. However, it may book too much memory, and thus limit the available parallelism in the tree. Consider for example a chain of tasks T 1 → T 2 → T 3 . Algorithm 1 will first book n 1 + f 1 for task T 1 , then n 2 + f 2 for T 2 and finally n 3 + f 3 for T 3 (assuming all this memory is available). However, no two tasks of this chain can be scheduled simultaneously because of their precedence order. Thus, it is not necessary to book n 1 , n 2 and n 3 at the same time, nor is it necessary to book memory for f 1 and f 3 : the memory used for T 1 can be later reused for the processing of T 2 and T 3 . By booking memory in a very conservative way, this heuristic may prevent nodes from other branches to be available for computation, and thus delay the processing of these nodes.

i ← pop(AO) 9 if M Booked + ni + fi ≤ M then 10 M Booked ← M Booked + ni + fi

Booking strategy for reduction trees

In a previous publication [START_REF] Eyraud-Dubois | Parallel Scheduling of Task Trees with Limited Memory[END_REF], we have proposed a novel activation policy based on a refined memory booking strategy. However, our strategy is limited to special trees, also called reduction trees, who exhibit the following two properties:

• There is no execution data, i.e., n i = 0 for each node i;

• The size of the output of each node is smaller than the size of its inputs, that is,

f i ≤ j∈Children(i) f j .
Using these two properties, we are able to prove that the memory has been successfully booked for all the leaves of a subtree, all nodes in this subtree can be processed without additional memory. Moreover, we know how to compute the amount of booked memory that each completing node has to transmit to its parent. Contrarily to the previous algorithm, this complex strategy allows to correctly predict the amount of memory that needs to be booked for a given subtree. However, it only applies to special trees, namely reduction trees. General trees may be transform into reduction trees by adding fictitious edges. However this increases the overall peak memory needed for any traversal, which limits its interest -we have indeed noticed that it does not give better performance than Algorithm 1 on general trees-. Furthermore, in some cases it makes it a key limitation for general trees with limited memory as it does not always allow for the completion of those trees.

A dynamic fast algorithm

In this section, we propose a novel algorithm, named MemBooking to schedule trees under limited memory, that overcomes the limitations of the previous two strategies. Similarly as in Algorithm 1, we rely on the activation of nodes, following an activation AO which is guaranteed to complete the whole tree within the prescribed memory in the case of a linear execution. However, activating a node does not correspond here to booking the exact memory n i + f i needed for this node: some of this memory will be transfered by some of its descendant in the tree, and if needed, we only book what is absolutely needed. The core idea of the algorithm is the following: when a node completes its execution, we want (i) to reuse the memory that is freed on one of its ancestors and (ii) perform these transfers of booked memory in an As Late As Possible (ALAP) fashion. More precisely, the memory freed by a completed node j will only be transfered to one of its ancestors i if (a) all the descendants of i have enough memory to be executed (that is, they are activated), and (b) if this memory is necessary and cannot be obtained from another descendent of i that will complete its execution later. Finally, an execution order EO states which of the activated and available nodes should be processed whenever a processor is available.

In order to keep track of all nodes, we use five states to descrive them (a node can only be in one state), which we present in reverse order of their use for a given node:

1. Finished (FN ): This corresponds to nodes which have completed their execution.

Running (RUN ):

This corresponds to nodes being executed.

3. Activated (ACT ): This corresponds to nodes for which we have booked enough memory (some of this memory might be booked by some descendant in the subtree).

4. Candidate for activation (CAND): This corresponds to nodes which are the next to be activated, that is, all their descendant have been activated but they are not activated yet. This is the initial state for all leaves. We now present the MemBooking algorithm (Algorithm 2), as well as its proof of correctness. Some optimizations and data-structures used to reduce the RR n°8966 time complexity will be presented later (the full algorithm with optimizations is available in Appendix B).

Algorithm 2: MemBooking(T, p, AO, EO, M ) // initialization of the memory 1. Memory re-allocation: DispatchMemory (Algorithm 3) reallocates the memory used by a node that just finished its execution. We present this algorithm in Section 4.1.

1 foreach node i do 2 Booked[i] ← 0 3 BookedBySubtree[i] ← -1 4 M Booked ← 0 5 UN ← T \ Leaves(T ) 6 CAND ← Leaves(T ) 7 ACT ← ∅ //
2. Node activation: UpdateCAND-ACT (Algorithm 4) allocates the available memory following the activation order AO. We present this algorithm in Section 4.2.

3. Node scheduling: the schedule is done following the execution order EO amongst the nodes that are both activated and ready to be executed.

Note that while AO is a topological order, we do not have any constraint on EO.

To be able to keep track of the memory allocated to each node, we use two arrays of data that are updated during the computation, namely:

• Booked[1.

.n], which contains the memory that is currently booked in order to process nodes 1 to n. We further call M Booked = i Booked[i]; • BookedBySubtree [1..n], which sums the memory that is currently booked by the subtree rooted in i ∈ {1, . . . , n}.

Memory re-allocation

When a node finishes its computation, the memory that was used during its computation can be allocated to other nodes. Our memory allocation works in two steps:

1. First we free the memory that was used by the node that has just finished its execution. Note that we cannot free all the memory: if the node that finished is not the root of the tree, then its output needs to be saved. In that case we allocate this memory to its parent.

2. Then we allocate the memory freed to its ancestors in ACT following an As Late As Possible strategy (meaning that if there is already enough memory booked in the unfinished part of the subtree, we do not allocate it to the root of the subtree but keep it for later use). We thus compute the contribution C i,j of a terminated node j to its parent i as the difference between what is needed by node i and what can be provided later by its subtree.

Algorithm 3: DispatchMemory(j)

/* First we free the memory used by j */

1 B = Booked[j] 2      Booked[j] ← 0 M Booked ← M Booked -B BookedBySubtree[j] ← BookedBySubtree[j] -B 3 i ← parent(j) 4 if i = N U LL then 5      Booked[i] ← Booked[i] + fj M Booked ← M Booked + fj BookedBySubtree[i] ← BookedBySubtree[i] + fj 6 B = B -fj
/* Then we dispatch the memory used by j between its ancestors which are in ACT , if it is neccessary */

7 while i = N U LL and i ∈ ACT ∪ RUN and B = 0 do 8 Cj,i = max(0, MemNeeded i -(BookedBySubtree[i] -B)) 9      Booked[i] ← Booked[i] + Cj,i M Booked ← M Booked + Cj,i BookedBySubtree[i] ← BookedBySubtree[i] -(B -Cj,i) 10 B = B -Cj,i 11 i ← parent(i) RR n°8966

Node activation

Our second algorithm, UpdateCAND-ACT , updates both ACT and CAND.

The key point of this sub-algorithm is that it is conceived such that nodes are activated following the AO order. We formally show this result in Section 5 (Lemma 1).

Algorithm 4: UpdateCAND-ACT (CAND, ACT )

1 WaitForMoreMem ← false 2 while !(WaitForMoreMem) and CAND = ∅ do 3

Let i be the node of CAND with maximal priority in AO

4 MissingMem i = max 0, MemNeeded i -Booked[i] + j∈Children(i) BookedBySubtree[j] 5 if M Booked + MissingMem i ≤ M then 6      Booked[i] ← Booked[i] + MissingMem i M Booked ← M Booked + MissingMem i BookedBySubtree[i] ← Booked[i] + j∈Children(i) BookedBySubtree[j] 7 remove(i, CAND); insert(i, ACT ) 8 if ∀j ∈ Children(parent(i)), j / ∈ UN ∪ CAND then 9 remove(parent(i), UN ); insert(parent(i), CAND) 10 else 11
WaitForMoreMem ← true

Proof of correctness

In this section, we want to show the following result:

Theorem 1. If T can be executed with a memory bound of M using the sequential schedule AO, then MemBooking(T, p, AO, EO, M ) processes T entirely.

To prove this theorem, we need to verify that the following conditions are respected:

1. The memory used never exceed the memory limit M ; 2. Each running task has enough memory to run; 3. No data is lost, that is, a result that was computed will not be overwritten until it has been used; 4. All tasks are executed.

A necessary condition to prove items 1, 2 and 3 using the Booked[1.

.n] introduced earlier is to prove the following results:

1. At all time, i Booked[i] ≤ M ; 2. If i ∈ RUN , then Booked[i] = MemNeeded i ;
3. For all i / ∈ FN , we cannot decrease the value of Booked[i]; finally, when i is moved to FN , its output f i should be moved from Booked[i] to its parent's memory usage: Booked[parent(i)].

In the proofs, we decompose time according to the different events (Algorithm 2, line 9): t 0 = 0 and when each task finishes. We know that to execute the tree T of n tasks, there are at most n + 1 events (each task can finish only once) that we denote t 0 = 0 ≤ t 1 ≤ • • • ≤ t n (in case a node is never executed, we may write t i = +∞).

As our algorithm updates its variables describing the tasks' state and the amount of booked memory for each node after each event, we consider timeintervals ]t i , t i+1 ]: this corresponds to the status of the algorithm after the modification of event t i .

We start by proving that nodes are activated in the right order.

Lemma 1. The nodes are moved from CAND to ACT following the AO order.

Proof. First, we notice that nodes are inserted in ACT only in Algorithm 4, on line 7. Then one can verify that at all time, the element extracted from CAND is the first one with respect to the AO ordering, ensuring that the elements contained in CAND are extracted following AO.

To show that elements are inserted in ACT following AO, we then only need to prove that at all time, the next element according to AO is available in CAND. That is, for all i ∈ {1, • • • , n}, if for all j < i, AO(j) has been extracted from CAND to ACT , then either AO(i) has been extracted from CAND to ACT , or AO(i) ∈ CAND. We prove this by induction.

Because AO is a topological order, then AO(1) is necessarily a leaf. Furthermore, CAND initially contains all leaves, hence AO(1) ∈ CAND.

Let i > 1. Assume that for all j < i, AO(j) has been extracted from CAND to ACT . If AO(i) has been extracted from CAND to ACT then the property is true. Otherwise, either AO(i) is a leaf or an interior node. If it is a leaf, then AO(i) ∈ CAND because leaves were inserted initially and they can only be removed from CAND when they are extracted to ACT . If AO(i) is an interior node, let AO(i 1 ), • • • , AO(i m ) be its children, because AO is a topological order, then for j ≤ m, i j < i. In particular, assume w.l.o.g that i 1 < • • • < i m , then when AO(i m ) was extracted from CAND to ACT , then AO(i) was added to CAND, hence showing the result.

Then, we prove that until a node is activated, the only memory booked for this node are for the results of its completed children. Lemma 2. At any time t, if i ∈ UN ∪ CAND, then

Booked[i] = j∈Children(i)∩FN f j

RR n°8966

Proof. If i ∈ UN ∪ CAND, this means that until that time, i has always been either in UN or in CAND, and hence the only time when Booked[i] could have been modified is by a call of DispatchMemory (Algorithm 3), more specifically on line 5. This happens only when a child of i completes, and hence is moved to FN , which proves the result. Lemma 3. At any time t, if i ∈ ACT ∪ RUN , then [START_REF] Agullo | Multifrontal QR Factorization for Multicore Architectures over Runtime Systems[END_REF] j∈Children(i)∩FN f j ≤ Booked[i];

(2

) MemNeeded i ≤ BookedBySubtree[i] (3) BookedBySubtree[i] = Booked[i] + j∈Children(i)∩(ACT ∪RUN ∪FN ) BookedBySubtree[j].
Proof. First one can notice that for i ∈ ACT ∪ RUN , j∈Children(i)∩FN f j ≤ Booked[i]: indeed, every time a child j of i finished its execution, Dispatch-Memory (Algorithm 3) added f j to Booked[i]. Furthermore, until i is moved to FN , the algorithm never subtracts anything from Booked[i].

Similarly, we have at all time MemNeeded i ≤ BookedBySubtree[i]: it is the case when i is moved from CAND to ACT , and all further transformations of BookedBySubtree[i] preserve this result.

To show the third result, we proceed by induction on time. For simplicity, let us denote by

BBS(i) = Booked[i] + j∈Children(i)∩(ACT ∪RUN ∪FN ) BookedBySubtree[j]
Clearly the result is true at time t 0 = 0 since ACT ∪ RUN = ∅. Assume the induction hypothesis: for all time t ≤ t i0 , if i ∈ ACT ∪ RUN , BookedBySubtree[i] = BBS(i). We now prove that the result holds during the interval ]t i0 , t i0+1 ] using a second induction on the tree structure, starting from leaves.

We first assume that i ∈ ACT ∪ RUN is a leaf. When i was moved from CAND to ACT (using UpdateCAND-ACT ), then the algorithm made sure that the property was respected, then we notice that neither Booked[i] nor BookedBySubtree[i] is modified for a leaf until that leaf is moved to FN , so the result still holds.

We now consider an interior node i c ∈ ACT ∪ RUN such that the result holds for all its descendants until t i0+1 and the result holds for that node until t i0 (first induction hypothesis).

If i c was moved to ACT at time t i0 , then one can verify by looking at algorithm UpdateCAND-ACT that the result holds. Furthermore, if no descendant of i c finished at t i0 , then DispatchMemory has not modified the status of i c , hence by induction hypothesis the result holds. Let us assume now that a descendant of i c has finished its execution at t i0 , let us call j c the children of i c on the path to that descendant.

If j c ∈ FN (meaning j c is the descendant that finished at t i0 ), then one can see that B was subtracted from BBS(i c ). (DispatchMemory, line 2), then f jc was added (DispatchMemory, line 5), then C jc,ic was added (DispatchMemory, line 9). Similarly, f jc was added to BookedBySubtree[i] (DispatchMemory, line 5), then B -C jc,ic was subtracted (DispatchMemory, line 9) which keeps the value identical, showing the result. Finally, one can notice that at the end of the while iteration (line 11), the value B is now what was removed from BookedBySubtree[i] compared to the beginning of the iteration.

Otherwise, j c ∈ ACT ∪RUN In that case, BBS(i c ) and BookedBySubtree[i c ] can only be modified by the "while" loop of Algorithm DispatchMemory. More specifically, only BookedBySubtree[j c ] and Booked[i c ] will be modified. At the beginning of the iteration of the while-loop such that the index i = i c , then B is exactly equal to what was subtracted from BookedBySubtree[j c ]. Furthermore, C j,ic is added to Booked[i c ], and then B -Booked[i c ] is subtracted from BookedBySubtree[i c ] which shows the result. Finally, we notice again that at the end of the iteration, B is exactly equal to what was subtracted from

BookedBySubtree[i c ].
This proves the result for i c , hence proving the wanted result.

Lemma 4. At any time t, if i ∈ ACT ∪ RUN , then

Booked[i] ≤ MemNeeded i - j∈Children(i)∩(ACT ∪RUN ) f j .
Proof. We prove this result by induction on time. At t 0 = 0, ACT ∪ RUN is empty, hence showing the result. Let us assume the result true for all node i ∈ ACT ∪RUN at any time t ≤ t i0 and let us that it also holds for t ∈]t i0 , t i0+1 ]. We first start by the case where i ∈ UN ∪ CAND at t i0 , and i ∈ ACT ∪ RUN in ]t i0 , t i0+1 ]. This means that node i was activated (moved to ACT ) by Algorithm UpdateCAND-ACT at time t i0 . Let us consider the missing memory as defined in UpdateCAND-ACT :

MissingMem i = max   0, MemNeeded i -   Booked[i] + j∈Children(i) BookedBySubtree[j]     ,
Since i was in CAND right before being activated, we had Booked[i] = j∈Children(i)∩FN f i (Lemma 2). Moreover, for all j ∈ Children(i), BookedBySubtree[j] does not change later when i is moved to ACT , hence according to Lemma 3 (we use item (3) on i RR n°8966 then item (2) on the set Children(i) ∩ (ACT ∪ RUN )),

j∈Children(i) BookedBySubtree[j] = j∈Children(i)∩(ACT ∪RUN ∪FN ) BookedBySubtree[j] ≥ j∈Children(i)∩(ACT ∪RUN ) BookedBySubtree[j] ≥ j∈Children(i)∩(ACT ∪RUN ) MemNeeded j ≥ j∈Children(i)∩(ACT ∪RUN ) f j
Hence we verify that:

• If MissingMem i = 0, then when i is moved to ACT , Booked[i] = j∈Children(i)∩FN f j ≤ MemNeeded i - j∈Children(i) BookedBySubtree[j] ≤ MemNeeded i - j∈Children(i)∩(ACT ∪RUN ) f j ;
• If MissingMem i = 0, then when i is moved to ACT ,

Booked[i] = MemNeeded i - j∈Children(i) BookedBySubtree[j] ≤ MemNeeded i - j∈Children(i)∩(ACT ∪RUN ) f j .
Let us now assume that i was already in ACT ∪ RUN at t i0 . Let A i0 be the value of Booked[i] at t i0 , and B i0 = MemNeeded i -j∈Children(i)∩(ACT ∪RUN ) f j at t i0 . We have A i0 ≤ B i0 by induction hypothesis.

• If i is not an ancestor of the node that just finished, then during ]t i0 , t i0+1 ],

Booked[i] = A i0 and MemNeeded i -j∈Children(i)∩(ACT ∪RUN ) f j = B i0 , hence the property holds.

• If i is the parent of the node j c that just finished, then during ]t i0 , t i0+1 ],

MemNeeded i -j∈Children(i)∩(ACT ∪RUN ) f j = B i0 -f jc . Furthermore, DispatchMemory performs the operation Booked[i] ← A i0 + f jc + C i,jc
, where either C i,jc = 0 in which case we can verify that the property holds, or C i,jc = 0, and in this case we have BookedBySubtree[i] = MemNeeded i , then by Lemma 3, we have:

MemNeeded i = BookedBySubtree[i] = Booked[i] + j∈Children(i)∩(ACT ∪RUN ) BookedBySubtree[j] ≥ Booked[i] + j∈Children(i)∩(ACT ∪RUN ) f j
hence showing the result.

• If i is another ancestor of the node j c that just finished, then during ]t i0 , t i0+1 ], MemNeeded i -j∈Children(i)∩(ACT ∪RUN ) f j = B i0 . Furthermore, DispatchMemory does:

Booked[i] ← A i0 + C i,jc
, where either C i,jc = 0 in which case we can verify that the property holds, or C i,jc = 0, and with an indentical argument that above we obtain the result.

This concludes the proof.

Lemma 5. If i ∈ RUN , then Booked[i] = MemNeeded i , if i ∈ FN , then BookedBySubtree[i] = 0.
Proof. We show this result by showing a stronger result: if i ∈ RUN , then

Booked[i] = MemNeeded i = BookedBySubtree[i].
Then, if i ∈ FN , we have BookedBySubtree[i] = 0 (this is a consequence of algorithm DispatchMemory).

The proof is an induction on the tree structure, starting from leaves. If i is a leaf, then by Lemma 3 and 4 we have:

Booked[i] ≤ MemNeeded i ≤ BookedBySubtree[i] = Booked[i],
hence showing the result.

Let us now consider an interior node i and assume that the result is true for its descendants in the tree. When i is moved to RUN , then all its children are in FN , hence Lemma 3 (items (2) and ( 3)) and Lemma 4 can be written as:

MemNeeded i ≤ BookedBySubtree[i] BookedBySubtree[i] = Booked[i] + j∈Children(i)∩FN BookedBySubtree[j] Booked[i] ≤ MemNeeded i
By induction hypothesis, j ∈ Children(i) ∩ FN , BookedBySubtree[j] = 0, which shows the desired result.

We are now ready to show the final result:

Proof of Theorem 1. Let us remind what needs to be proven to show this result:

RR n°8966 1. At all time, i Booked[i] ≤ M ; 2. If i ∈ RUN , then Booked[i] = MemNeeded i ; 3. For all i /
∈ FN , we cannot decrease the value of Booked[i]; finally, when i is moved to FN , its output f i should be moved from Booked[i] to its parent's memory usage: Booked[parent(i)].

All tasks are executed.

We prove the item by checking how the three algorithms modify M Booked . First, we notice that we ensure that at all time, M Booked =

i Booked[i]). DispatchMemory never increases M Booked ; in UpdateCAND-ACT , when modified, M Booked stays below M ; M Booked is not directly modified in Mem-Booking.

The second item is proven by Lemma 5. For the third item, we check that we never modify Booked[i] for i ∈ FN and that DispatchMemory correctly transfers f j to the parent of j at its termination.

For the fourth and last item, we proved by contradiction: suppose that at some time t, all tasks are not processed and no more events happen. If not task termination happens, this means than no tasks are running (RUN = ∅). Let us call t i0 the last event (we write t i0+1 = +∞).

• Consider the case where ACT = ∅. We know that all descendants of nodes in ACT are in ACT ∪ RUN ∪ FN , hence in particular there exists a node i in ACT such that all its descendants are in FN (or it has no descendants). Then, by Lemma 3, 4 and 5 we have during ]t i0 , t i0+1 ]: Booked[i] = MemNeeded i , hence i should have been moved to RUN in the execution of MemBooking at time t i0 which contradicts RUN = ∅.

• Consider the case where ACT = ∅. According to Lemma 1, the i 0 nodes that were inserted in ACT are the i 0 first elements AO. Let k be the i 0 + 1th node in AO. We have also seen in the proof of Lemma 1 that at t i0 , k is the next node to be considered in CAND for activation. Hence the only reason why it was not moved to ACT by UpdateCAND-ACT

is because M Booked + MissingMem j > M .
Because all tasks are either in FN or in UN ∪ CAND, using Lemma 2 we can compute M Booked :

M Booked = i∈FN Booked[i] + i∈UN ∪CAND Booked[i] = i∈FN 0 + i∈UN ∪CAND j∈Children(i)∩FN f j = i,AO[i]>AO[k] j∈Children(i)∩FN f j

RR n°8966

We now evaluate the missing memory:

MissingMem k = MemNeeded k -   Booked[k] + j∈Children(k) BookedBySubtree[j]   = MemNeeded k -Booked[k] thanks to Lemma 5 = MemNeeded k - j∈Children(k)∩FN f j thanks to Lemma 2.
In the end, we have

M Booked +MissingMem k = MemNeeded k + i,AO[i]>AO[k] j∈Children(i)∩FN f j
which is exactly the memory used by the sequential schedule AO when processing k and hence is smaller than M , contradicting the previous hypothesis.

In the end, we were able to show that if RUN = ∅, then ACT ∪UN ∪CAND = ∅, hence showing that FN = T and the whole tree was processed.

Complexity analysis

In this section we give a complexity analysis of the algorithm presented in the previous section. We have chosen to separate the idea of the main algorithm from the optimizations used to lower the execution cost so that the proof of Theorem 1 is more understandable. In this section we now detail those optimizations. A complete version of the Algorithm is available in Appendix B.

Theorem 2. Let T a tree with n nodes, and H be its height, AO an activation order, EO an execution order, M a memory bound and p processors, then MemBooking(T, p, AO, EO, M ) runs in O (n(H + log n)).

Proof. First let us define some data structures that we use and update during the execution but that we did not disclose in the presentation of the algorithm to simplify its proof of correctness. First we introduce some informative arrays:

• We keep an array of size n, ChNotAct, such that at all time:

∀i, ChNotAct[i] = |{j ∈ Children(i)|j ∈ UN ∪ CAND}|.
This array keeps track of the number of children of each nodes that are still in UN or CAND. At the beginning of the execution, this array is initiated for all nodes with their number of children. Then it is updated in constant time by UpdateCAND-ACT when a node i is moved from

CAND to ACT (line 7): ChNotAct[parent(i)] ← ChNotAct[parent(i)] -1.
Hence the time complexity of updating this table throughout execution is O(n).

• We keep an array of size n, ChNotFin, such that at all time:

∀i, ChNotFin[i] = |{j ∈ Children(i)|j / ∈ FN }|.
This array keeps track of the number of children of each nodes that are not finished. At the beginning of the execution, this array is initiated for all nodes with their number of children. Then it is updated in constant time by MemBooking when a node i finishes (line 10):

ChNotFin[parent(i)] ← ChNotFin[parent(i)] -1.
Hence the time complexity of updating this table throughout execution is O(n).

• We keep an array of size n, NotUnCand, such that at all time:

NotUnCand[i] ⇔ i / ∈ UN ∪ CAND
At the beginning of execution, this array is initiated to false. It is then updated in constant time by UpdateCAND-ACT when a node i is moved from CAND to ACT (line 7):

NotUnCand[i] ← true. Hence the time complexity of updating this table throughout execution is O(n).
Now we introduce the main structures used in the computation:

• We implement CAND as a heap whose elements are sorted according to the activation order (AO). All elements are inserted and removed (with complexity O(log n)) at most once from CAND, hence a time complexity of O(n log n). Furthermore, in UpdateCAND-ACT , extracting i from CAND (on line 3) is done in constant time.

• In practice belonging to ACT can be verified by checking if MemNeeded i ≤ BookedBySubtree[i] (Lemma 3, item 2). Hence we do not need a data structure for ACT .

• Nevertheless, we use a data structure to remember the elements of ACT whose children have all finished their execution. Hence instead of implementing ACT , we use:

ACTf = ACT ∩ {i|ChNotFin[i] = 0}.
This is implemented as a heap whose elements are sorted according to the activation order (EO). In order to keep this property at all time, in UpdateCAND-ACT when a node i is moved from CAND to ACT (line 7), we check if ChNotFin[i] = 0, in which case i is inserted in ACTf . Similarly, in MemBooking when a node i finishes (line 10), if ChNotFin[parent(i)] is set to 0, then we insert parent(i) in ACTf in O(log n). Note that all elements are inserted and removed at most once from ACTf , hence the time complexity of elements going through ACTf is O(n log n). Finally, in MemBooking, extracting i from ACTf (line 14) is done in constant time.

If we detail all operations contained in MemBooking:

RR n°8966

• DispatchMemory is called exactly once per node (every time a node finishes). For a given node j of depth h j , it does at most O(h j ) operations (note that the test i ∈ ACT ∪ RUN on line 7 can be done in constant time by checking if NotUnCand[i] = true), which gives a total cumulative time complexity of O(nH).

• UpdateCAND-ACT is called for each event. Note that we have already accounted for removing or inserting all elements from the different sets.

Finding the element to remove from CAND on line 3 is done in constant time because CAND is a heap sorted according to AO. Similarly, the test on line 8 can be done in constant time by simply testing whether ChNotAct[parent(i)] = 0.

The most time consuming event is the computation of MissingMem i on line 4 which could be computed up to O(n) times for a given node if the condition on M Booked and M on line 5 is not satisfied (hence giving a time complexity of O(n 2 )). To avoid this case, we will extend the property (3) proven in Lemma 3 to a node i of CAND such that BookedBySubtree[i] has already been computed once. To do this, we first initialized BookedBySubtree[j] to -1, and replace line 4 in UpdateCAND-ACT by:

If BookedBySubtree[i] = -1, then BookedBySubtree[i] ← Booked[i] + j∈Children(i) BookedBySubtree[j] MissingMem i ← max(0, MemNeeded i -BookedBySubtree[i])
We also extend the "while" loop in DispatchMemory (line 7

) from i ∈ ACT ∪ RUN to i ∈ {i|BookedBySubtree[i] = -1}.
• Finally, the last "while" loop of MemBooking (line 13) is entered once per element contained in ACT , that is exactly n times. Furthermore, because ACTf is a heap sorted according to EO, removing one element is done in O(log n), which gives a cumulative complexity of O(n log n) for this last loop.

Finally accounting for all operations, the total time complexity of this optimized algorithm is O(n(log(n) + H)).

A new makespan lower bound

It is usual in scheduling problems to compare the makespan of proposed algorithms to lower bounds, as the optimal makespan is usually out of reach (NP-complete). The classical lower bound for scheduling task graphs considers the maximum between the average workload (total computation time divided by the number of processors) and the longest path in the graph. In a memoryconstrained environnement, the memory bound itself may prevent the simultaneous execution of too many tasks. We propose here a new lower bound that takes this into account.

Theorem 3. Let C max be the makespan of any correct schedule of a tree whose peak memory is at most the memory bound M , and t i the processing time of task i. Then

C max ≥ 1 M i MemNeeded i × t i .
Proof. Consider a task i as described in the model of Section 2: its processing requires a memory of MemNeeded i (see Equation ( 1)). As stated in the theorem, we denote by t i its processing time. Consider the total memory usage of a schedule, that is, the sum over all time instants t of the memory used by this schedule. Then, task i contributes to at least MemNeeded i × t i to this total memory usage. For a schedule of makespan C max , the total memory usage cannot be larger than C max × M , where M is the memory bound. Thus,

i MemNeeded i × t i ≤ C max × M which concludes the proof.
We have noticed in the simulations described in the next section that with eight processors, this new lower bound improved the classical lower bound in 22% of the case for on actual assembly trees, and in these cases the average increase in the bound was 46%. For the simulations on synthetic trees, it has improved the lower bound in 33% of the cases, with an average improvement of 37%. Contrarily to the previous lower bound, this new lower bound does not depend on the number of processors, hence the improvement is even greater with more processors.

It is important to understand that the more precise the lower bound, the more information is available for a possible improvement of the considered heuristics.

Simulations

We report here the results of the simulations that we performed to compare our new booking strategy (MemBooking) to the two other scheduling heuristics presented above: the basic Activation policy [START_REF] Agullo | Multifrontal QR Factorization for Multicore Architectures over Runtime Systems[END_REF] presented in Section 3.1 and the booking strategy [START_REF] Eyraud-Dubois | Parallel Scheduling of Task Trees with Limited Memory[END_REF] for reduction trees, denoted MemBookingRedTree, from Section 3.2. In the latter, the tree is first transformed into a "reduction tree" [START_REF] Eyraud-Dubois | Parallel Scheduling of Task Trees with Limited Memory[END_REF] by adding some fictitious nodes and edges before the scheduling strategy can be applied.

Data sets

The trees used for the simulations come from two data sets, which we briefly describe below.

The first data set, also called assembly trees are trees corresponding to the multifrontal direct factorization of a set of sparse matrices obtained from the University of Florida Sparse Matrix Collection (http://www.cise.ufl.edu/ research/sparse/matrices/). This data sets is taken from [START_REF] Eyraud-Dubois | Parallel Scheduling of Task Trees with Limited Memory[END_REF], where more information can be found on multifrontal factorization and on how the trees are constructed. This data sets consists in 608 trees which contains from 2,000 to 1,000,000 nodes. Their height ranges from 12 to 70,000 and their maximum degree ranges from 2 to 175,000.

The second data set is synthetic. The node degree is taken randomly in [1; 5], with a higher probability for small values to avoid very large and short trees, on which we already observed with the previous data set that our algorithm outperforms other strategies. The following table gives the precise node degree probabilities:

X P r(δ = X) 1 0.58 2 0.17 3,4,5 0.08
Edges weights follow a truncated exponential distribution of parameter 1. More precisely, we first generate a random number from an exponential distribution of parameter 1, which is multiplied it by 100 and then truncated to fit in the interval [10; 10.000]. The processing size of a node is 10% of its outgoing edge weight and it processing time is proportional to its outgoing edge degree. We generated 50 synthetic trees of 1.000, 10.000 and 100.000 nodes, which results in trees of respective average height of 63, 95 and 131.

Simulation setup

All three strategies were implemented in C, with special care to avoid complexity issues. These strategies have been applied to the two tree families described above, with the following parameters:

• We tested 5 different number of processors [START_REF] Agullo | Robust Memory-Aware Mappings for Parallel Multifrontal Factorizations[END_REF][START_REF] Amestoy | Hybrid scheduling for the parallel solution of linear systems[END_REF][START_REF] Jacquelin | On Optimal Tree Traversals for Sparse Matrix Factorization[END_REF]16,32). The results were quite similar, expect for the extreme case (too large or too small parallelism). We mainly report the results for 8 processors but also mention results for other number of processors.

• For each tree, we first computed the postorder traversal that minimizes the peak memory. This gives the minimum amount of memory needed for both Activation and MemBooking (MemBookingRedTree is likely to use more memory as it works on a transformed tree). The heuristics are then tested with a factor of this minimal memory, which we call below normalized memory bound. We only plot an average result when a given strategy was able to schedule at least 95% of the trees within the memory bound.

• The previous postorder was used as input for both the activation order AO and the execution order EO for Activation and MemBooking in general. We also tested other orders for activation and execution, such as other postorders, critical path ordering, or even optimal (non-postorder) ordering for peak memory [START_REF] Joseph | An application of generalized tree pebbling to sparse matrix factorization[END_REF]. As seen later, this only results in slightly noticeable change in performance.

During the simulations of the parallel executions, we reported the makespan (total completion time), which is normalized by the maximum of the classical lower bound and our new memory related lower bound (see Section 6). We also reported the peak memory of the resulting schedules, as well as the time needed to compute the schedule. This scheduling time does not include the computation of the activation or execution order, which may be done beforehand. Figure 2 plots the average normalized makespan of all strategies on various memory constraints, whileFigure 3 shows the speedup of MemBooking over Activation. We notice that for a memory bound twice the minimum memory, MemBooking is 1.4 faster than Activation on average. However, even this particular speedup spans a wide interval (between 1 and 6) due to the large heterogeneity of the assembly trees. Note that the two heuristics from the literature give very similar results: this is explained by the fact that Mem-BookingRedTree first transforms the trees before applying a smart booking strategy: on these trees, adding fictitious edges has the same effect than booking to much memory (as Activation does) and hinders the benefit of the booking strategy. We also note that MemBooking is able to take advantage of very scarce memory conditions: as soon as the available memory increases from its minimum value, its makespan drops and reaches only 10% above the lower bound for 3x the minimum memory, leaving very little room to hope for better algorithms. This is also illustrated by Figure 4, which plots the real use of the memory by the heuristics: while Activation and MemBookingRedTree are very conservative, MemBooking is able to use larger fraction of the available memory when it is limited.

Results on the assembly trees

Discussion on execution time: From the complexity analysis (Section 5.1) we expect our algorithm to add significant overhead when trees are very deep (nH term of the worst-case complexity). We first study the cumulative running time in Figure 5 of the various strategy as a function of the number of nodes in the trees. All strategies have similar running times, except on a subset of trees for which our heuristic is much slower (≈ 10s). We verify that those running times indeed depend on the height of the tree in Figure 6. Another noticeable fact from this figure is that overall the average overhead for each node remains negligible (below 1ms per node with height H = 10 5 !).

As future work, it may be interesting to get rid of this height factor in the complexity of the algorithm especially for cases when H = O(n).

To give some hindsight on the importance of this factor, we decided to study the speedup of MemBooking compared to that of Activation as a function of the tree height. In particular, one can see from the correlations between Figures 5 and6 that the trees of large height are trees where H = O(n). We report these results in Figure 7 where we show the relation between achievable speedup and tree height: very deep trees usually correspond to thin ones and Normalized memory bound Fraction of available memory used Figure 4: Fraction of memory used by all heuristics on assembly trees (same legend as Figure 2) q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q 0.01

1.00 1e+04 1e+05 1e+06
Tree size (number of nodes, log. scale) Scheduling time (seconds, log. scale) Figure 5: Running times of the heuristics on assembly trees (same legend as Figure 2) RR n°8966 q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q 1e-06 1e-05 1e-04

1e+02 1e+03 1e+04 1e+05
Tree height (log. scale) Average scheduling time per node (s., log. scale)

RR n°8966

do not provide big opportunities for increasing the parallelism. This is why our strategy achieves best speedups on shallow trees. With this in mind, an interesting study would be to derive a good measure on trees which may hint whether the use of a sophisticated strategy such as MemBooking is needed. Finding such a good measure would need a particular research effort and is out of scope of this paper.

Changing the activation or execution order

On Figure 8, we present the average makespan of the Activation heuristic for various activation and execution order. This figure is similar to Figure 2 for the other scheduling heuristics. The activation and execution order used are the following:

• memPO (memory PostOrder): the sequential postorder traversal that minimizes the peak memory (NB: this is the order chosen activation and execution order of both Activation and MemBooking in all other plots of this section); • CP (Critical Path): nodes orders by decreasing bottom-level;

• OptSeq (Optimal Sequential): the sequential (non postorder) traversal that minimizes the peak memory, computed as in [START_REF] Joseph | An application of generalized tree pebbling to sparse matrix factorization[END_REF]; • perfPO (performance PostOrder): another postorder traversal, designed for parallel performance (subtrees with larger critical path are scheduled first, which, in a parallel execution, is supposed to give higher priority to nodes with large critical path). We notice that the results of using different orders for activation and/or execution slightly change the results: using CP as an execution order always gives a small but noticeable improvement over the other strategies. On the contrary, the choice of the activation order has little effect on the final makespan. The same effects can be seen on Activation (when changing the activation/execution orders) and MemBooking (when changing its priority order). However, the gap between the performance of different orders is much smaller than the gap of using different scheduling strategy: changing the activation/execution order does not change the ranking of the scheduling policies

Results on other numbers of processors

Figure 9 depicts the makespan of all strategies for increasing number of processors. We notice that the gain of the proposed MemBooking strategy increases with the number of available processors, as it also increased the potential parallelism in the tree.

Results on the synthetic trees

The simulations on synthetic trees show the same general trends as what we notices on assembly trees, and thus we only review briefly their results.

Figure 10 and 11 shows that MemBooking is once again able to schedule trees faster in a memory-constrained environnement. Synthetic trees are more regular and homogeneous that assembly trees, so that the speedup of Mem-Booking over Activation is more regular. It reaches an average 1.3 when the memory is twice the bound.

Finally, the scheduling time of all strategies is always below 0.1 seconds due to the smaller height of the trees. Note that MemBookingRedTree is not able to schedule most trees in a very constrained memory environment: when the memory bound is smaller that 1.4 times the minimum memory peak of a sequential postorder processing, MemBookingRedTree is unable to schedule 33% of the trees (or more) and thus is not included in the plot. Normalized memory bound Fraction of available memory used Figure 12: Fraction of memory used by all heuristics on synthetic trees (same legend as Figure 10) q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q 0.001 0.010 0.100 1e+04 1e+05

RR n°8966

Tree size (number of nodes, log. scale) Scheduling time (seconds, log. scale) Once again, we notice that an improvement when using CP (Critical Path) as an execution order, and that the improvement is small enough to keep the ranking of the different scheduling policies.

Results on other numbers of processors

Figure 15 depicts the makespan of all strategies for increasing number of processors for synthetic trees. Once again, we notice that the gain of the proposed MemBooking strategy increases with the number of available processors: it is hardly noticeable for 2 or 4 processors, but becomes important for 8,16 and 32 processors.

Conclusion

In this paper, we have proposed a novel algorithm for scheduling task trees on computing platforms with bounded shared memory. The proposed algorithm carefully allocates memory to activated nodes, and accurately predicts how much memory can be recycled from the processing of a node's ancestors. We have shown that it is always able to schedule a tree under an admissible memory bound, and that its complexity is sufficiently small to allow its implementation is actual runtime schedulers. By performing simulations on both actual assembly trees of sparse direct multifrontal solvers and on a broader class of synthetic trees, we have proved that it outperforms its two competitors from the literature, especially when memory is a scarce resource. Incidentally, we have proposed a new makespan lower bound that takes into account a bound on the shared memory, which, to the best of our knowledge, is the first of its kind.

This study is the first step in the design of realistic schedulers for task trees handling large data, such as assembly trees. One major extension would be to consider parallel tasks rather than only sequential ones. To this goal, one would need to make several adaptations to cope with the extra memory needed for a parallel processing, and to solve the unavoidable trade-off between allocating many processors to big tasks (and losing on tree parallelism) and allocating many tasks in parallel (and threatening the memory bound). Nevertheless, we are confident that the algorithm presented in this paper (or its adaptation) would still provide an improvement over the classical Activation algorithm. Another necessary extension would be to consider distributed memories, of even a mix of distributed/shared memory (as in clusters of cores sharing a dedicated memory). A Sequential post-order minimizing average memory

We define the average memory of a schedule as follows:

AvgMem = 1 C max Cmax t=0 mem(t)dt,
where mem(t) is the memory used by the schedule at time t and C max is the makespan.

Theorem 4. A post-order traversal that minimizes the average memory is obtained by processing subtrees by non-increasing T i /f i value, where T i is the total time needed to process the subtree rooted in i.

Proof. Let us consider a tree rooted at node r, with k children c 1 , . . . , c k . If the subtrees are processed in this order, the average memory of the processing of the whole subtree is:

AvgMem(r) = 1 T r        k i=1     i-1 j=1 f j   + AvgMem(c i )   • T ci processing of ci +   k j=1 f j   t r processing of r       
Let us now rewrite this expression:

T r •AvgMem(r) =   k j=1 f j   t r + k i=1 AvgMem(c i )T ci + k i=1   i j=1 f j   T ci - k i=1 f i T ci
The only term that depends on the subtree ordering is the third and penultimate one, namely k i=1 i j=1 f j ×T ci . As this term does not depend on the average memory of the subtrees, it is easy to see that an optimal post-order for a tree can be obtained by optimizing the average memory of its subtrees (to minimize the second term) and carefully ordering them (to minimize the third term).

We then rewrite the third term using T ci = w i and f i = p i and obtain k i=1 w i i j=1 p j which we identify as the weighted sum flow of independant tasks on a single processor (problem 1|| w i C i using Graham's notation). Following the classical Smith's rule [START_REF] Smith | Various optimizers for single-stage production[END_REF], we know that an ordering with minimal RR n°8966 sum flow is obtained by processing the tasks by non-increasing w i /p i . Thus, an optimal ordering of the subtrees for the average memory is obtained by processing them by non-increasing T ci /f i .

B Complete and optimized algorithm

Figure 1 :

 1 Figure 1: Input, execution and output data of a node i with children j 1 , . . . j p and parent k.

Algorithm 1 : 1 M

 11 Activation(T, p, AO, EO, M ) Booked ← 0 2 ACT ← ∅ 3 while the whole tree is not processed do 4 Wait for an event (task finishes or t = 0) // Free the memory booked by j 5 foreach just finished node j do M Booked ← M Booked -nj -j∈Children(i) fj 6 continueActivation ← true 7 while continueActivation do // Activate the first node i of AO if possible

8

 8

main loop 8 10 foreach just finished node j do 11 DispatchMemory(j) 12 UpdateCAND

 8101112 while the whole tree is not processed do 9 Wait for an event (task finishes or t = 0) -ACT (CAND, ACT )13while there is an available processor Pu and ACT = ∅ do 14 Let i be the available node in ACT with maximal priority in EO: Remove(i, ACT )

Figure 2 :

 2 Figure 2: Makespan of assembly trees with all heuristics depending on the memory bound

Figure 3 :

 3 Figure 3: Speedup of MemBooking compared to Activation on assembly trees. Plain lines represent the average speedup, dotted lines connect the median speedup while the ribbon depicts the results between the first and ninth decile (the maximum speedup always lies between 5 and 6).

Figure 6 : 2 Figure 7 :

 627 Figure 6: Running times of the heuristics on assembly trees (same legend as Figure 2)

Figure 8 :

 8 Figure 8: Makespan of assembly trees for the proposed MemBooking strategy using different activation and execution order. The bottom plot corresponds to a zoom on the part where the memory is less limited.

Figure 9 :Figure 10 :Figure 11 :

 91011 Figure 9: Makespan of assembly trees for all strategies on various number of processors.

Figure 13 :Figure 14 :

 1314 Figure 13: Running times of the heuristics on synthetic trees (same legend as Figure 10)

Figure 15 :

 15 Figure15: Makespan of all strategies for synthetic trees on various number of processors.

Algorithm 5 : 2 M 12 B = B -fj 13 while 1 28if

 5212131 Init(T, AO, EO)// Initialization of the data structures 1CAND← AO-sorted heap (init: Leaves(T); fun: AO-insert, AO-remove, AO-min) ACTf ← EO-sorted heap (init: empty; fun: EO-insert, EO-remove, EO-min)ChNotAct[1..n] ← array of size n (init: ∀i, ChNotAct[i] ← |Children(i)|) ChNotFin[1..n] ← array of size n (init: ∀i, ChNotFin[i] ← |Children(i)|) NotUnCand[1..n] ← array of size n (init: ∀i, NotUnCand[i] = false) Booked[1..n] ← array of size n (init: ∀i, Booked[i] = 0) BookedBySubtree[1..n] ← array of size n (init: ∀i, BookedBySubtree[i] = -1) Booked ← 0 RR n°8966 Booked[i] ← Booked[i] + fj M Booked ← M Booked + fj i = N U LL and BookedBySubtree[i] = -1 and B = 0 do 14 Cj,i = min(B, max(0, MemNeeded i -(BookedBySubtree[i] -B))) ← Booked[i] + Cj,i M Booked ← M Booked + Cj,i BookedBySubtree[i] ← BookedBySubtree[i] -(B -Cj,i) 16 B = B -Cj,i 17 i ← parent(i) 18 WaitForMoreMem ← false 19 while !(WaitForMoreMem) and CAND = ∅ do 20 i ← AO-min(CAND) 21 if BookedBySubtree[i] = -1 then 22 BookedBySubtree[i] ← Booked[i] + j∈Children(i) BookedBySubtree[j] 23 MissingMem i = max (0, MemNeeded i -BookedBySubtree[i]) 24 if M Booked + MissingMem i ≤ M then ← Booked[i] + MissingMem i M Booked ← M Booked + MissingMem i BookedBySubtree[i] ← Booked[i] + j∈Children(i) BookedBySubtree[j] 26 AO-remove(i, CAND); if ChNotFin[i] = 0 then EO-insert(i, ACTf ) 27 ChNotAct[parent(i)] ← ChNotAct[parent(i)] -ChNotAct[parent(i)] = 0 then AO-insert(parent(i),CAND) 29 else 30 WaitForMoreMem ← true 31 while there is an available processor Pu and ACTf = ∅ do 32 i ← EO-min(ACTf ); EO-remove(i, ACTf ) 33 Make Pu process i

RR n°8966

Acknowledgments

This work was supported by the ANR SOLHAR project funded by the French National Research Agency.

Algorithm 6: MemBooking(T, p, AO, EO, M )

1 Init(T, AO, EO) 2 while the whole tree is not processed do 3 Wait for an event (task finishes or t = 0)