Julien Herrmann

Loris Marchal

Yves Robert

Tree traversals with task-memory affinities

Keywords: Scheduling, Memory-aware, Sparse matrix factorization, Multifrontal method, Tree traversal, Bi-objective optimization

We study the complexity of traversing tree-shaped workflows whose tasks require large I/O files. We target a heterogeneous architecture with two resource types, each with a different memory, such as a multicore node equipped with a dedicated accelerator (FPGA or GPU). The tasks in the workflow are colored according to their type and can be processed if all their input and output files can be stored in the corresponding memory. The amount of used memory of each type at a given execution step strongly depends upon the ordering in which the tasks are executed, and upon when communications between both memories are scheduled. The objective is to determine an efficient traversal that minimizes the maximum amount of memory of each type needed to traverse the whole tree. In this paper, we establish the complexity of this two-memory scheduling problem, and provide inapproximability results. In addition, we design several heuristics, based on both post-order and general traversals, and we evaluate them on a comprehensive set of tree graphs, including random trees as well as assembly trees arising in the context of sparse matrix factorizations.

Ordonnancement d'arbres de tâches avec affinité mémoire

Résumé :

Dans ce rapport, nous nous intéressons à la complexité du traitement d'arbres de tâches utilisant de gros fichiers d'entrée et de sortie. Nous nous focalisons sur une architecture hétérogène avec deux types de ressources, utilisant chacune une mémoire spécifique, comme par exemple un noeud multicore équipé d'un accélérateur (FPGA ou GPU). Les tâches de l'arbre sont colorées suivant leur type et peuvent être exécutées si tous leurs fichiers d'entrée et de sortie peuvent être stockés dans la mémoire correspondante. La quantité de mémoire de chaque type utilisée à une étape donnée de l'exécution dépend fortement de l'ordre dans lequel les tâches sont exécutées et du moment où sont effectuées les communications entre les deux mémoires. L'objectif est de déterminer un ordonnancement efficace qui minimise la quantité de mémoire de chaque type nécessaire pour traiter l'arbre entier. Dans ce rapport, nous établissons la complexité de ce problème d'ordonnancement à deux mémoires et nous fournissons des résultats d'inapproximabilité. De plus, nous proposons plusieurs heuristiques, fondées à la fois sur des traversées d'arbres en profondeur et des traversées générales, que nous évaluons sur un ensemble complet d'arbres, comprenant des arbres aléatoires ainsi que des arbres rencontrés dans le domaine de la factorisation de matrices creuses.

Mots-clés : Ordonnancement, Contrainte Mémoire, Factorisation de matrices creuses, Méthode multifrontale, Traversée d'arbres, Optimisation bi-critère

Introduction

Modern computing platforms are heterogeneous: a typical node is composed of a multi-core processor equipped with a dedicated accelerator, such as a FPGA or a GPU. Our goal is to study the execution of a computational workflow tree onto such a platform. The nodes of the workflow tree correspond to tasks, and the edges correspond to the dependencies among the tasks. The dependencies are in the form of input and output files: each node accepts a (potentially large) file as input, and produces a set of files, each of them to be accepted by a different child node. Each task in the workflow is best suited to a given resource type (say a core or a GPU), and is colored accordingly. To execute a task of a given color, all the input files and the output file of the task must fit within the corresponding memory. As the workflow tree is traversed, tasks of different colors are processed, and capacity constraints on both memory types must be met. In addition, when a child of a task has a different color than its parent, a communication from the parent's memory to the child's memory must be executed before the child can be processed (and again, the input file and all output files of this child must fit within the child's memory). All these constraints require to carefully orchestrate the scheduling of the tasks, as well as the communications between memories, in order to minimize the maximum amount of each memory that is needed throughout the tree traversal.

Memory-aware scheduling in an important problem that has been the focus of many papers (see Section 2 for related work). This work mainly builds upon the pioneering work of Liu, who has studied tree traversals that minimize the peak amount of memory used on a single machine, hence with a single memory type. Liu first restricted to depth-first traversals in [START_REF] Liu | On the storage requirement in the out-of-core multifrontal method for sparse factorization[END_REF], before dealing with an optimal algorithm for arbitrary traversals in [START_REF] Liu | On the storage requirement in the out-of-core multifrontal method for sparse factorization[END_REF]. In many situations, the optimal traversal is a depth-first traversal, but this is not always the case. An assessment of the relative performance of depth-first traversals versus optimal traversals is proposed by [START_REF] Jacquelin | On optimal tree traversals for sparse matrix factorization[END_REF]. The main objective of this paper is to extend these results to colored trees with two memory types, and tasks belonging to a given type. Clearly, the traversal, i.e., the order chosen to execute the tasks, and to perform the communications, plays a key role in determining which amount of each memory is needed for a successful execution of the whole tree. The interplay between both memories dramatically complicates the scheduling: it is no surprise that the complexity of the problem, that was polynomial with a unique memory, now becomes NP-complete.

In this paper, we concentrate on memory usage, but we are fully aware that performance aspects are important too, and that even more difficult trade-offs are to be found between parallel performance and memory consumption. One could envision a fully general framework, where tasks have different execution-times for each resource type (instead of being tied to a given resource as in this paper), and where concurrent execution of several tasks on each resource type is possible (instead of the fully sequential processing of the task graph that is assumed in this paper). Altogether, this study is only a first step towards the design of memory-aware schedules on modern heterogeneous platforms with two memory types. However, despite the apparent simplicity of the model, our results show that we already face a difficult bi-criteria optimization problem when dealing with two different memory types. We firmly believe that the results presented in this paper will help to lay the foundations for memory-aware scheduling algorithms on modern heterogeneous platforms such as those equipped with multicores and GPUs.

One major contribution of the paper is the derivation of several complexity results: NPcompleteness of the problem, and inapproximability within a constant (α, β) factor pair of both absolute minimum memory amounts. Here the absolute minimum memory of a given type is computed when assuming an infinite amount of memory of the other type.

Another major contribution is the study of depth-first traversals and related variants. We show how to extend Liu's algorithm to compute the best depth-first traversal, which simultaneously minimizes both memory usages. However, while depth-first traversals were natural algorithms with a single memory, they severely constrain the activation of communication nodes with two memories. We show that the optimization problem is still NP-complete when relaxing the firing of communication nodes in depth-first traversal, which leads us to go beyond depth-first traversals and to introduce general heuristics. These heuristics extends Liu's optimal algorithm along various (greedy) decision criteria to trade-off the usage of both memory types.

Finally, the third major contribution is a comprehensive assessment of all these heuristics using both randomly generated tress, and actual elimination trees that arise from the multifrontal factorization of sparse linear systems.

The rest of the paper is organized as follows: We start with an overview of related work in Section 2. Then we detail the framework in Section 3. The next four sections constitute the heart of the paper. We deal with complexity results in Section 4. Section 5 is devoted to the study of depth-first traversals, a first class of (widely-used) heuristics. Then we introduce additional heuristics in Section 6. The experimental evaluation of all the heuristics is conducted in Section 7. Finally we provide some concluding remarks and hints for future work in Section 8.

Related Work

The work presented in this paper builds upon previous results related to memory-aware scheduling, but its applications are relevant to the field of sparse matrix factorization and of hybrid computing. In this section, we present related work for each domain.

Sparse matrix factorization

Determining a memory-efficient tree traversal is very important in sparse numerical linear algebra. The elimination tree is a graph theoretical model that represents the storage requirements, and computational dependencies and requirements, in the Cholesky and LU factorization of sparse matrices. In a previous study, we have described how such trees are built, and how the multifrontal method organizes the computations along the tree [START_REF] Jacquelin | On optimal tree traversals for sparse matrix factorization[END_REF]. This is the context of the founding studies of Liu [START_REF] Liu | On the storage requirement in the out-of-core multifrontal method for sparse factorization[END_REF][START_REF] Liu | An application of generalized tree pebbling to sparse matrix factorization[END_REF] on memory minimization for postorder or general tree traversals mentioned in Section 1. Memory minimization is still a concern in modern multifrontal solvers when dealing with large matrices. In particular, efforts have been made to design dynamic schedulers that takes into account dynamic pivoting (which impacts the weights of edges and nodes) when scheduling elimination trees with strong memory constraints [START_REF] Guermouche | Memory-based scheduling for a parallel multifrontal solver[END_REF], or to consider both task and tree parallelism with memory constraints [START_REF] Agullo | Robust memory-aware mappings for parallel multifrontal factorizations[END_REF]. While these studies try to optimize memory management in existing parallel solvers, we aim at designing a simple model to study the fundamental underlying scheduling problem.

Scientific workflows

The problem of scheduling a task graph under memory 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 or geophysical simulations. The problem of task graphs handling large data has been identified in [START_REF] Ramakrishnan | Scheduling data-intensiveworkflows onto storage-constrained distributed resources[END_REF] which proposes some simple heuristic solutions. Surprisingly, in the context of quantum chemistry computations, Lam et al. [START_REF] Lam | Memory-optimal evaluation of expression trees involving large objects[END_REF] have recently rediscovered the algorithm published in 1987 in [START_REF] Liu | An application of generalized tree pebbling to sparse matrix factorization[END_REF].

Pebble game and its variants

On the more theoretical side, this work builds upon the many papers that have addressed the pebble game and its variants. Scheduling a graph on one processor with the minimal amount of memory amounts to revisiting the I/O pebble game with pebbles of arbitrary sizes that must be loaded into main memory before firing (executing) the task. The pioneering work of Sethi and Ullman [START_REF] Sethi | The generation of optimal code for arithmetic expressions[END_REF] deals with a variant of the pebble game that translates into the simplest instance of the problem with a unique memory and where all input/output files have weight 1 and all execution files have weight 0. The concern in [START_REF] Sethi | The generation of optimal code for arithmetic expressions[END_REF] was to minimize the number of registers that are needed to compute an arithmetic expression. The problem of determining whether a general DAG can be executed with a given number of pebbles has been shown NP-hard by Sethi [START_REF] Sethi | Complete register allocation problems[END_REF] if no vertex is pebbled more than once (the general problem allowing recomputation, that is, re-pebbling a vertex which have been pebbled before, has been proven Pspace complete [START_REF] Gilbert | The pebbling problem is complete in polynomial space[END_REF]). However, this problem has a polynomial complexity for tree-shaped graphs [START_REF] Sethi | The generation of optimal code for arithmetic expressions[END_REF]. Recently, still in the contact of a single memory type, an extension of these results to parallel machines base been proposed in [START_REF] Marchal | Scheduling tree-shaped task graphs to minimize memory and makespan[END_REF].

Hybrid computing

Hybrid computing consists in the simultaneous use of CPUs and GPUs to optimize performance for high performance computing. Since CPUs and GPUs are powerful for specific and different tasks, its is natural to schedule tasks on their "favorite" resource, that is, the resource where there execution time is minimal. This has been done successfully to increase performance in linear algebra libraries [START_REF] Tomov | MAGMA version User's guide[END_REF][START_REF] Horton | A class of hybrid lapack algorithms for multicore and gpu architectures[END_REF]. There also exist software tools that schedule an application composed of tasks with both CPU and GPU implementations on hybrid platforms: for instance, StarPU [START_REF] Augonnet | Starpu: a unified platform for task scheduling on heterogeneous multicore architectures[END_REF] optimizes the execution time of an application by scheduling its tasks on multiple kinds of resources, based on predictions of execution and data transfer times.

Framework

As stated above, we deal with tree traversals on a two-memory system where each task belongs to a specific memory. Dependencies are in the form of input and output files: each task accepts a file as input from its parent node in the tree, and produces a set of files to be consumed by each child node. We start this section by formally writing all the constraints that need to be satisfied during a traversal: for the convenience of the reader, we briefly review the constraints for uncolored trees (single memory) in Section 3.1, before dealing with those for bi-colored trees (two memories) in Section 3.2. Also, we work out a small example in Section 3.3. Finally, we state the target optimization problems in Section 3.4.

Uncolored trees

The tree work-flow T is composed of n nodes, or tasks, numbered from 1 to n where Children(i) denotes the set of the children of i and parent(i) denotes its parent. We consider here out-trees, where a parent node has to be processed before its children nodes. Each task (or node) i in the tree is characterized by the size f i of its input file (data needed before the execution and received from its parent), and by the size n i of its execution file. A valid traversal σ of the tree T is an ordered list of the nodes of T such that all precedence constraints in T are enforced by the schedule. Since the nodes of T are numbered from 1 to n, σ can be seen as a permutation of 1, n , where ∀i ∈ 1, n and ∀j ∈ Children(i), σ(i) < σ(j).

Each node i in the tree has an input files of size f i . If i is not the root, its input file is produced by its parent parent(i); if i is the root, its input file may be of size zero, or it may contain input from the outside world.

Each node i in the tree has an execution file of size n i . This execution file can be modeled by adding an extra child to the node, as depicted in Figure 1. Thus, from now on, we will assume w.l.o.g. that every node i has an execution file of size n i = 0.

Each non-leaf node i in the tree, when executed, produces a file of size f j for each j ∈ Children(i). If i is a leaf-node, then Children(i) = ∅ and i produces a file of null size (we consider that terminal data produced by leaves are directly sent to the outside world).

During the processing of a task i, the memory must contain its input file, and all its output files (including the execution file of the additional child whenever needed). The amount of memory

A A A ′ f i f i f j1 f jp f j1 f jp n i n i 0 0 ... ...

GGGGGA

Figure 1: Modeling a node with an execution file of size n i = 0

MemReq(i) that is needed for this processing is thus:

MemReq(i) =   j∈Children(i) f j   + f i
After task i has been processed, the input file is discarded, while its output files are kept in memory until the processing of its children. Thus, for a traversal σ of T , the actual amount of memory used to process the node i is:

MemUsed(σ, i) =   j∈Children(i) f j   + f i + j∈S\{i} f j
where S denotes the set of files stored in the memory when the scheduler decides to execute task i. Note that S must contain the input file of task i. After the processing of node i, we have:

S ← (S\{i}) ∪ Children(i)
Initially, S contains the input file of the root.

Bi-colored trees

When two memories are considered, each task (or node) i in the tree is now characterized by its color, which represents the specific memory where the task has to be executed, in addition to the size f i of its input file (as before). We let color(i) ∈ {red, blue} represent the memory type of task i. If color(i) = red, then i is a computational node which operates in the red memory, which it uses to load its input file, execute its program and produce the set of output files for its children. Similarly, if color(i) = blue, then i is a computational node which operates in the blue memory. Each communication from one memory to the other is achieved through a communication node, which is uncolored. Hence, there are two types of nodes in the tree, red or blue computational nodes (or tasks), and uncolored communication nodes. Each time there is a data dependence between two tasks assigned to different memories, the output file of the source task has to be loaded from one memory into the other, using a communication node. Thus, in the model, the tree T does not contain direct edges between blue and red nodes; memory loads from one memory to the other occur only when processing a communication node. A valid traversal σ of the tree T is an ordered list of the nodes of T (including communication nodes) such that all node dependences in T are enforced by the schedule.

Here are further details on the processing of each node type:

Computational nodes: they represent a task executed on a specific memory. During the processing of a computational task i, the associated memory must contain the input file and its output files. Assuming that i is a blue task, the amounts of memory BlueMemReq(i) and RedMemReq(i) that are needed for this processing are thus:

BlueMemReq(i) =   j∈Children(i) f j   + f i RedMemReq(i) = 0
After task i has been processed, the input file is discarded, while its output files are kept in memory until the processing of its children. Thus, for a traversal σ of T , the actual amounts of memory used to process the blue node i are:

BlueMemUsed(σ, i) =   j∈Children(i) f j   + f i + j∈S blue \{i} f j RedMemUsed(σ, i) = j∈S red f j
where S blue (respectively S red ) denotes the set of files stored in the blue (respectively red) memory when the scheduler decides to execute task i. Note that S blue must contain the input file of task i. After processing the blue node i, we have:

S blue ← (S blue \{i}) ∪ Children(i) S red ← S red
Initially, S blue contains the input file of the root and S red = ∅ if the root is a blue node, and conversely if the root is a red node.

Communication nodes represent communications between one memory and the other. Each communication node i has an input file of size f i and an output file of the same size. It loads f i units of memory from one memory to the other. During the processing of a communication task i from the blue memory to the red memory, both memories must contain the file of size f i . Thus, the blue and the red memory needed for this processing is f i :

BlueMemReq(i) = f i RedMemReq(i) = f i
After i has been processed, the input file from the blue memory is discarded, while the output file is kept in the red memory until the processing of its child. Thus, for a traversal σ of T , the actual amounts of memory used to process the communication node i are:

BlueMemUsed(σ, i) = f i + j∈S blue \{i} f j RedMemUsed(σ, i) = f i + j∈S red f j
Note that S blue must contain the input file of task i. Letting j denote the unique child of communication node i, we have after the execution of i that:

S blue ← S blue \{i} S red ← S red ∪ {j}
It is important to stress that a communication node need not be processed right after the execution of its parent. The only constraint is that its processing must precede the execution of its unique child. This flexibility in the schedule severely complicates the search for efficient traversals.

σ ex (i) Fired Node BlueMemReq(i) RedMemReq(i) BlueMemUsed(σ, i) RedMemUsed(σ, i) j∈S blue fj j∈S red fj 1 B 1 4 0 4 0 0 → 4 0 2 C 1 1 1 4 1 4 → 3 0 → 1 3 B 2 7 0 7 1 3 → 4 1 4 B 3 2 0 4 1 4 → 2 1 5 B 4 1 0 2 1 2 → 1 1 6 B 5 4 0 4 1 1 → 3 1 7 C 3 3 3 3 4 3 → 0 1 → 4 8 R 5 0 3 0 4 0 4 → 1 9 R 1 0 5 0 5 0 1 → 4 10 C 2 2 2 2 4 0 → 2 4 → 2 11 B 6 5 0 5 2 2 → 3 2 12 B 7 1 0 3 2 3 → 2 2 13 B 8 2 0 2 2 2 → 0 2 14 R 2 0 8 0 8 0 2 → 6 15 R 3 0 4 0 6 0 6 → 2 16 R 4 0 2 0 2 0 2 → 0 Table 1: Description of the traversal σ ex in Section 3.3.
Top-down vs. bottom-up traversals. We conclude this section with a remark on a variant of the model. There is a complete equivalence with top-down traversals of out-trees (the problem addressed in this paper) and bottom-up traversals of in-trees. In a nutshell, one only needs to reverse the direction of the edges, and to execute the schedule backwards, to move form one variant to another1 . In fact, the literature deals with both variants. The seminal paper of Liu [START_REF] Liu | On the storage requirement in the out-of-core multifrontal method for sparse factorization[END_REF] originally deals with post-order bottom-up traversals for in-trees, while we speak of depth-first top-down traversals for out-trees in this paper, but there is no actual difference.

Example

Let consider the bi-colored tree T depicted in Figure 2. Any traversal of T has to start with the execution of the root B 1 . After it has been processed, 4 units of the blue memory are occupied and the red memory is empty. We now have two choices:

Either we process the right blue children B 2 first. This would use BlueMemUsed(σ, B 2 ) = 8 units of the blue memory since the file of size 1 created by the root would still reside in the blue memory. Then, the sum of the file sizes stored in the blue memory after B 2 has been processed would be equal to j∈S blue f j = 5, and the red memory would be empty.

Or we can process the communication node C 1 to load the file of size 1 from the blue memory to the red one. After that, if the left blue children B 2 is now processed, its execution would use BlueMemUsed(σ, B 2 ) = 7 units of the blue memory instead of 8 in the previous case, but the red memory would contain a file of size 1 wich will matter for a further execution of a red node.

A complete traversal σ ex of T is described in Table 1, with the ordered list of the execution of tall nodes in T , the amount of both memories required for each task, and the evolution of both memory usages after each execution. The maximum memory usage for the traversal σ ex described in Table 1 is 7 units for the blue memory and 8 units for the red memory. As one can see, the ordered list of the execution of the computation and communication nodes of T will be the result of a trade-off between the usage of each memory. In fact, the memory-aware traversal problem for bi-colored rooted trees can naturally be cast into a two-criteria optimization problem.

B 1 B 2 B 3 B 4 B 5 B 6 B 7 B 8 R 1 R 2 R 3 R 4 R 5 C 1 C 2 C 3 1 3 1 2 1 1 2 2 3 4 2 2 3 1 2
Figure 2: Bi-colored tree T for the example.

RR n°8226

Objectives

As stated above, we face a multi-criteria optimization problem: how to minimize the amount of both memories needed for the tree traversal? The peak memory is the maximum usage of each memory over the whole schedule σ of the tree T , and is defined for the blue and the red memory by:

M σ blue (T ) = max i BlueMemUsed(σ, i) M σ red (T ) = max i RedMemUsed(σ, i)
Thus, we define the optimal peak for each memory needed to process a tree T as:

M opt blue (T ) = min σ M σ blue (T ) M opt red (T ) = min σ M σ red (T )
We point out that M opt blue (T ) can be seen as the minimum amount of blue memory required to traverse the tree when there is an unbounded amount of red memory available: a schedule which reaches M σ blue (T ) = M opt blue (T ) can use an arbitrary amount of red memory. Intuitively, one may ask what are trade-offs between the blue and red memory requirements of feasible schedules. One major objective of this paper is to provide quantitative answers to this question.

Complexity results

This section presents several important complexity results. We start with the NP-completeness of the two-memory minimization problem in Section 4.1. Then we show in Section 4.2 that the problem reduces to traversing uncolored trees when one memory is unbounded. Finally, we prove in Section 4.3 that it is impossible to approximate both minimum memories within arbitrary constant factors.

Hardness of the problem

Definition 1 (TwoMemoryTraversal). Given a tree T with n nodes, and two fixed memory amounts M red and M blue , does there exist a traversal σ of the tree such that M σ blue (T ) ≤ M blue and M σ red (T ) ≤ M red ? Theorem 1. The TwoMemoryTraversal problem is NP-complete.

Proof. The problem clearly belongs to NP, and the certificate is the ordered list of tasks (of both colors and including uncolored communication nodes) executed by the schedule; it is easy to maintain the amount of each memory required by the schedule, and to check that neither M red nor M blue is exceeded.

To establish the completeness, we use a reduction from the 2-Partition problem [START_REF] Garey | Computers and Intractability, A Guide to the Theory of NP-Completeness[END_REF]. Consider an instance Inst 1 of the 2-Partition problem, with n integers {a 1 , a 2 , ..., a n n i=1 a i = S}. Consider an instance Inst 2 of the TwoMemoryTraversal, consisting in the tree depicted on Figure 3. We set the bounds M red = 3S for the red memory and M blue = 2S for the blue memory. The construction of Inst 2 is polynomial in the size of Inst 1 .

Assume first that Inst 2 has a solution. Any traversal must start with the root B root . After it has been processed, 2S units of the blue memory are occupied, which means that it is full. Without loss of generality (by symmetry), assume that C is the next node to be executed. Then, we observe that if C (2) was the third executed node, we could never process R root nor R [START_REF] Augonnet | Starpu: a unified platform for task scheduling on heterogeneous multicore architectures[END_REF] root without violating the M red bound for the red memory. Thus, the third executed node has to be R root .

We observe that the red tasks R big and R f ree , and each communication task C i , all have to be processed before R root require 3S units of memory, it would violate the M red bound for the red memory. Besides, since we can not execute R

(2) root before R big , if C (2) were processed before R big , there would be at least S units of memory in the red memory and the execution of R big (which requires 5 2 S units of the red memory) would violate the M red bound. Thus, the node R big has to be processed before C (2) .

Besides, let i 0 be the index of the first processed task B i in the traversal. Its execution requires a i0 + 3 2 S units of the blue memory, which implies that it can not be processed before C (2) without violating the M blue bound for the blue memory. Thus, the node R big has to be processed before B i0 .

According to the previous arguments, the only tasks that can be processed right after R root and before R big are the communication tasks C i . Let I be the set of the indices of the tasks C i executed after R root and before R big .

→ After the execution of R root , there are 2S units occupied in the red memory and S units in the blue memory. Thus, to execute R big without violating the M red bound, the amount of red memory to free is at least S 2 . This means that i∈I

a i ≥ S 2 . → Besides, if i∈I a i > S
2 , the execution of B i0 (which requires at least i∈I a i + 3 2 S units of the blue memory) will violate the M blue bound. Thus, i∈I a i = S 2 , which implies that Inst 1 has a solution. Suppose now that Inst 1 has a solution I. According to the previous reasoning, the sequence of nodes B root ; C; R root ; ∀i ∈ I C i ; R big and R f ree can be executed without violating the bounds on memories. After this sequence, there are 3 2 S units occupied in the blue memory and the red one is empty. The node C (2) can be processed to load S units from the blue memory to the red one. Now, one of the blue node B i0 with i 0 ∈ I can be executed without violating the M blue bound, followed by B ′ i0 . Moreover, we can process every B i and B ′ i for all i ∈ I to free the blue memory. Then, it is possible to execute every branch of C i down to B ′ i for all i / ∈ I. From this point on, we can process the sub-tree rooted at the node R

(2) root using the same pattern, which means that Inst 2 has a solution and concludes the proof.

When one memory is unbounded

In this section, we focus on the computation of M opt red (T ) (or M opt blue (T )) which represents the minimal peak memory reachable when there is no constraint on the other memory. We show that the computation of M opt red (T ) and M opt blue (T ) for a bi-colored tree T reduces to the computation of the minimal peak memory for an uncolored tree.

Definition 2. Given a bi-colored tree T , we construct the corresponding uncolored (or for convenience, single-colored) tree T blue by turning every communication node and red node into a blue node, and by turning every red edge of size f i into a blue edge of size 0, as depicted in Figure 4. We construct the single-colored tree T red in a similar way. We let M ∞ blue denote the minimal amount of memory needed to process T blue (and similarly, M ∞ red for T red ).

Theorem 2. For any bi-colored tree T , we have M ∞ red = M opt red (T ) and M ∞ blue = M opt blue (T ). Proof. Given a bi-colored tree T with n nodes, consider T blue and M ∞ blue as in Definition 2. We show here that M ∞ blue = M opt blue (T ). The proof for M ∞ red = M opt red (T ) is similar. First, T and T blue have the same shape. The only differences between T and T blue are some edge values and the color of some vertices and edges. Thus, to any feasible traversal σ of T ,

C 1 C 2 C n B ′ 1 B ′ 2 B ′ n R root R big R f ree B 1 B 2 B n C (2) 1 C (2) 2 C (2) n B ′(2) 1 B ′(2) 2 B ′(2) n R (2) root R (2) big R (2) f ree B (2) 1 B (2) 2 B (2) n B root C C (2) a 1 a 2 a n 3 2 S 3 2 S 3 2 S 3 2 S a 1 a 2 a n S a 1 a 2 a n 3 2 S 3 2 S 3 2 S 3 2 S a 1 a 2 a n S S S S S • • • • • • ... • • • • • • ...

RR n°8226

we can associate the corresponding feasible traversal σ blue of T blue , and reciprocally. For any node i ∈ 1, n of T , its corresponding node in T blue will be referred at as i blue ∈ 1, n , thus σ(i) = σ blue (i blue ). Moreover we show that BlueMemUsed(σ, i) = MemUsed(σ blue , i blue ) for each node i ∈ 1, n ,:

If color(i) = blue, node i is not changed in T blue as described in Definition 2. Thus, BlueMemReq(i) = MemReq(i blue ) and the size of the files stored in the memory after i blue has been processed is the same that the files stored in the blue memory after i has been processed.

If color(i) = red, then BlueMemReq(i) = 0 and no file is stored in the blue memory after i has been processed. Besides, for the corresponding node i blue in T blue , we have f i blue = 0 and f j = 0 for each j ∈ Children(i blue ),. Thus MemReq(i blue ) = 0 and no file is stored in the memory after i blue has been processed.

If i is uncolored (communication node), then BlueMemReq(i) = f i . There are two sub-cases:

-If i is a communication node from a blue node to a red node, its processing will store no file in the blue memory. According to the Definition 2, if j blue denotes the child of i blue , we have f i blue = f i and f j blue = 0. Thus, MemReq(i blue ) = f i and no file is stored in the memory after i blue has been processed. -If i is a communication node from a red node to a blue node, its processing will store a file of size f i in the blue memory. According to the Definition 2, if j blue denotes the child of i blue , we have f i blue = 0 and f j blue = f i . Thus, MemReq(i blue ) = f i and a file of size f i is stored in the memory after i blue has been processed.

During the whole process BlueMemReq(σ, i) = MemReq(σ blue , i blue ). Besides, the size of the files stored in the blue memory after i has been processed and the size of the files stored in the memory after i blue has been processed are equal. Thus BlueMemUsed(σ, i) = MemUsed(σ blue , i blue ) and M opt blue (T ) = M ∞ blue .

Joint minimization of both objectives

Since the traversal problem is NP-complete, it is natural to wonder whether there exist approximation algorithms. In this section, we prove that there does not exist schedules that approximates both minimum memories M opt blue (T ) and M opt red (T ) within arbitrary constant factors for any bi-colored tree T . Since the (usually unfeasible) point of the Pareto diagram with coordinates (M opt blue (T ),M opt red (T )) is sometimes called the Zenith, this result amounts to proving that there exists no Zenith-approximation. Definition 3. Given a bi-colored tree T , we can construct the corresponding uncolored tree T unco by turning every colored node of T into an uncolored node, as depicted in Figure 5. We let M opt unco (T unco ) be the minimal amount of memory needed to process T unco .

Lemma 1. Given a bi-colored tree T with n nodes, consider an arbitrary traversal σ of T that requires an amount of red memory equal to M σ red (T ) and an amount of blue memory equal to M σ blue (T ). Then necessarily: M σ red (T ) + M σ blue (T ) ≥ M opt unco (T unco ) Proof. Let T unco be the uncolored tree corresponding to T as described in Definition 3. We observe that T and T unco have the same tasks, hence to any feasible traversal σ of T , we can associate the corresponding feasible traversal σ u of T unco , and reciprocally. For any node i ∈ 1, n of T , its corresponding node in T unco will be referred to as i u ∈ 1, n , thus σ(i) = σ u (i u ).

We will show that

∀i ∈ 1, n , BlueMemUsed(σ, i) + RedMemUsed(σ, i) = MemUsed(σ u , i u )
We proceed along the following case analysis:

1 3 1 2 1 1 2 2 3 4 1 2 3 1 2 GGGGGA 1 3 1 2 1 1 2 2 3 4 1 2 3 1 2
Figure 5: A bi-colored tree T and its corresponding uncolored tree T unco in Definition 3.

If color(i) = blue, then BlueMemReq(i) = MemReq(i u ) and RedMemReq(i) = 0. Besides, no file is stored in the red memory after i has been processed; also, the size of the files stored in the blue memory after i has been processed is the same as that of the files stored in the memory after i u has been processed.

If color(i) = red, then RedMemReq(i) = MemReq(i u ) and BlueMemReq(i) = 0. Besides, no file is stored in the blue memory after i has been processed; also, the size of the files stored in the red memory after i has been processed is the same as that the files stored in the memory after i u has been processed.

If i is uncolored (communication node), then BlueMemReq(i) + RedMemReq(i) = 2 × f i = MemReq(i u ).
Besides, a file of size f i will be stored in one of the two memories after i has been processed, and a file of size f i will be stored in the memory after i u has been processed.

During the whole traversal, we thus have BlueMemReq(σ, i)+RedMemReq(σ, i) = MemReq(σ u , i u ).

The sum of the size of the files stored in the blue memory and of the size of the files stored in the red memory after i has been processed is always equal to the size of the files stored in the memory after i u has been processed. Thus BlueMemUsed(σ, i) + RedMemUsed(σ, i) = MemUsed(σ u , i u ). This means that:

M opt unco (T unco ) ≤ M σu unco (T unco ) = max i MemUsed(σ u , i) = max i {BlueMemUsed(σ, i) + RedMemUsed(σ, i)} ≤ max i {BlueMemUsed(σ, i)} + max i {RedMemUsed(σ, i)} = M σ red (T ) + M σ blue (T )
which concludes the proof.

Theorem 3. There exists no algorithm that is both an α-approximation for blue memory peak minimization and a β-approximation for red memory peak minimization, when scheduling bicolored trees.

Proof. To establish this result, we proceed by contradiction. We therefore assume that there is an integer α, an integer β, and an algorithm A that processes any bi-colored tree T using a blue peak memory that is not greater than α times the optimal blue peak memory M opt blue (T ) and using a red peak memory that is not greater than β times the optimal red peak memory M opt red (T ). To derive the contradiction, we use the family of tree (T n ) n∈N depicted on Figure 6. T n is defined recursively using T n-1 . To help the reader to visualize T n , Figure 7 is processed recursively.

At each step of this process, the traversal σ blue does not use more than 3 units of blue memory. Since BlueMemReq(B n-1 ) = 3, this proves that M opt blue (T n ) = 3.

∀n ≥ 1, M opt red (T n ) = 2 Consider the traversal σ red that processes T n as follows. At step k:

-If k = 0, σ red processes the node B 0 -If k > 0, σ red processes the nodes B k . Then T (lef t) k-1 is processed recursively. Nodes C k , R k and C ′ k follow. And finally T (right) k-1
is processed recursively.

At each step of this process, the traversal σ red does not use more than 2 units of red memory. Since RedMemReq(R n ) = 2, this proves that M opt red (T n ) = 2. Let T unco n be the uncolored tree corresponding to T n as describe in Definition 3 and M opt unco (T unco n ) the minimum amount of memory required to execute it. T unco 2 is depicted in Figure 7. We now prove by induction that M opt unco (T unco n ) = n + 2 for n ≥ 2. As show in [START_REF] Liu | An application of generalized tree pebbling to sparse matrix factorization[END_REF], postorder traversals are optimal for peak memory minimization of uncolored trees with unit costs. Besides, all post-order traversals of T unco n require the same amount of memory. Thus

M opt unco (T unco n ) = M opt unco (T unco n-1 ) + 1 for n ≥ 2. Since M opt unco (T unco 1
) = 2, we have the result.

By hypothesis, algorithm A can process any T n with M

A blue (T n ) ≤ α.M opt blue (T n ) = 3α and M A red (T n ) ≤ β.M opt red (T n ) = 2β.
Let n 0 = ⌈3α + 2β⌉, we have:

M A blue (T n0 ) + M A red (T n0 ) ≤ 3α + 2β < ⌈3α + 2β⌉ + 2 = M opt unco (T unco n0 )
This contradicts Lemma 1, which means that such an algorithm A cannot exist.

Depth-first traversals

In this section, we study depth-first traversals, which are the equivalent of post-order traversals for in-trees. In the context of single-memory trees, depth-first traversals are known to be suboptimal [START_REF] Liu | An application of generalized tree pebbling to sparse matrix factorization[END_REF]: worse, their memory usage can be arbitrarily high as compared to that of the optimal solution [START_REF] Jacquelin | On optimal tree traversals for sparse matrix factorization[END_REF]. Clearly, these negative results remain true in a two-memory framework (simply assume that one memory is infinite). Still, depth-first traversals are a natural heuristic for traversing tree graphs, and they enjoy a simple implementation and memory management. As such, they are the most commonly used traversals in actual sparse solvers.

B 1 B (lef t) 0 C 1 R 1 C ′ 1 B (right) 0 Bn Cn Rn C ′ n 1 1 1 1 1 1 1 1 1 1 T (lef t) n-1 T (right) n-1
T 1 :

T n :

RR n°8226

We show how to compute the optimal depth-first traversal in Section 5.1. It turns out that this traversal is optimal for both memory usages (among all depth-first traversals). However, depthfirst traversals give no freedom on scheduling communication nodes. If we allow a communication node to be processed not immediately before its sub-tree, the ordering of the processing of the sub-trees and of the communication nodes will create a trade-off between both memory usages and will allow to decrease them. This leads us to define sloppy depth-first traversals, which we study in Section 5.2.

Strict depth-first traversals

Definition 4. A depth-first traversal is a feasible traversal that processes all nodes of a tree T by processing the root and, then, recursively processing all sub-trees. Hence, in a post-order traversal, after processing a node i, the whole sub-tree rooted at i is completely processed before any other node that does not belong to this sub-tree. Formally, a feasible traversal σ of the tree T with n nodes is a depth-first traversal if and only if for each node r ∈ T , with two children i ∈ Children(r) and j ∈ Children(r), we have:

σ(i) < σ(j) ⇒ (∀u ∈ T i , σ(u) < σ(j))
where T i is the sub-tree rooted at the node i.

Algorithm 1: BestDepthFirstTraversal(T ) root ← the root of T ; S ← 0; (σ, M blue , M red ) ← ([root] , 0, 0); for i ∈ Children(root) do (σ i , M blue i , M red i ) ← BestDepthFirstTraversal(T i ); S ← S + f i if color(root) = blue then for i ∈ Children(root) in the increasing order of M blue i -f i do σ ← [σ; σ i ]; S ← S -f i ; M blue ← max(M blue , S + M blue i ); M red ← max i∈Children(root) M red i ; if color(root) = red then for i ∈ Children(root) in the increasing order of M red i -f i do σ ← [σ; σ i ]; S ← S -f i ; M red ← max(M red , S + M red i ); M blue ← max i∈Children(root) M blue i ; if color(root) = black then i ← the unique child of root; σ ← [σ; σ i ]; if color(i) = blue then M blue ← M blue i ; M red ← max(f i , M red i ); if color(i) = red then M red ← M red i ; M blue ← max(f i , M blue i );
return (σ, M blue , M red ); Theorem 4. Algorithm 1 returns the best depth-first traversal σ of T for both the blue and the red memories and the amount of memory M blue and M red used by σ.

Proof. Finding the best depth-first traversal of T amounts to find the best ordering to process every sub-tree. We prove that the order of the recursive processes at each step in Algorithm 1 is the best for both memories.

At a given step, if the root of the sub-tree is a communication node, we have no choice, and we recursively process the sub-tree rooted at its unique child.

At a given step, if the root r of the sub-tree is blue, then, the amount of red memory used to process this sub-tree will not depend on the order of the recursive processes to complete the sub-tree. Indeed, for each i ∈ Children(r), after the recursive process of T i , S blue ← S blue \{i} and S red is unchanged. Then, independently of the order of the recursive processes of every T i , the amount of red memory required to process T with a depth-first traversal will be RedMemReq(T ) = max i∈Children(root) RedMemReq(T i ). Thus, at this step, we can only optimize the amount of blue memory. To do so, we use the optimal post-order traversal for uncolored trees provided by Liu [11]. This post-order traversal leads the best depth-first traversal for the blue memory at this step, and, thus, to the best depth-first traversal for both memories.

At a given step, if the root of the sub-tree is red, the proof is similar.

Sloppy depth-first traversals

As explained in the previous section, the order of the sub-trees processed in a strict depth-first traversal does not influence the maximum usage of red memory for a tree rooted at a blue node, and vice versa. Thus, in a strict depth-first traversal, both memory usages are independent. This comes from the fact that strict depth-first traversals give no freedom on communications. If we allow a communication node to be processed not immediately before its sub-tree, the ordering of the processing of the sub-trees and of the communication nodes will create a trade-off between both memory usages. This leads us to define sloppy depth-first traversals. Definition 5. A sloppy depth-first traversal is a feasible traversal similar to a depth-first traversal except that, after processing a communication node i, the whole sub-tree rooted at i is not necessarily processed immediately. We define SloppyChildren(i) as being the set of thc red and blue children of i, together with the children of the uncolored children (these represent the set of the computational children of i). Formally, a feasible traversal σ of the tree T with n nodes is a sloppy depth-first traversal if and only if for each node r ∈ T , and for any two nodes i ∈ Children(r) and j ∈ SloppyChildren(r) ∪ Children(r), we have:

σ(i) < σ(j) ⇒ (∀u ∈ T i , σ(u) < σ(j))
where T i is the sub-tree rooted at the node i. Definition 6 (TwoMemorySloppyDepthFirstTraversal). Given a tree T with n nodes, and two fixed amount of memory M red and M blue , is there a sloppy depth-first traversal of the tree that need an amount of red memory inferior to M red and an amount of blue memory inferior to M blue ? Theorem 5. The TwoMemorySloppyDepthFirstTraversal problem is NP-complete.

Proof. The problem clearly belongs to NP, and the certificate is the ordered list of tasks (of both colors, and including communication nodes) executed by the schedule.

To establish the completeness, we use a reduction to the 2-Partition problem [START_REF] Garey | Computers and Intractability, A Guide to the Theory of NP-Completeness[END_REF]. Consider an instance Inst 1 of the 2-Partition problem, with n integers {a 1 , a 2 , ..., a n i a i = S}. Consider an instance Inst 2 of the decision problem, consisting in the tree depicted on Figure 8. We set M red = 2S for the red tasks and M blue = 2S for the blue tasks. The construction of Inst 2 is polynomial in the size of Inst 1 . Assume first that Inst 2 has a solution. Any sloppy depth-first traversal must start with the root B root . After it has been processed, 2S units of the blue memory are occupied, which means that this memory is full. Let i 0 be the index of the first red task R i to be executed. We observe that B big and B f ree have to be processed before R i0 , otherwise the process of C ′ i0 (which occurs right after the process of R i0 in a sloppy depth-first traversal) would violate the M blue bound on the blue memory. Thus, the only tasks that can be processed right after B root and before B big are the communication tasks C i . Let I be the set of the indices of the tasks C i executed before B big .

C 1 C 2 C n C ′ 1 C ′ 2 C ′ n B root B big B f ree B 1 B 2 B n R 1 R 2 R n a 1 a 2 a n 1 2 S 3 2 S 3 2 S 3 2 S 3 2 S 3 2 S 3 2 S a 1 a 2 a n S • • • • • •

If

i∈I a i < S 2 , when the scheduler decides to execute B big , the blue memory would be filled with i / ∈I a i + S units. Thus the process of B big will use BlueMemUsed(B big ) = i / ∈I a i + S + 3 2 S > 2S units of blue memory, which violates the M blue bound.

If i∈I a i > S 2 , when the scheduler decides to execute R i0 , the red memory would be filled with at least i∈I a i > S 2 units. Thus the process of R i0 will use at least RedMemUsed(R i0 ) ≥ i∈I a i + 3 2 S > 2S units of red memory, which violates the M red bound.

Thus, i∈I a i = S 2 , which implies that Inst 1 has a solution. Suppose now that Inst 1 has a solution I. According to the previous reasoning, the sequence of nodes B root ; ∀i ∈ I, C i ; B big and B f ree can be executed without violating the bounds on memories. After this sequence, there are S 2 units occupied in the blue memory and in the red one. Now, one of the red node R i0 with i 0 ∈ I can be executed without violating the M red bound, followed by C ′ i0 and B i0 . Moreover, we can process every R i , C ′ i and B i ∀i ∈ I. Then, one is able to execute every branch of C i down to B i for all i / ∈ I, which means that Inst 2 has a sloppy depth-first solution and concludes our proof.

Heuristics

In addition to depth-first traversals, in this section we present three traversal heuristics which aim at minimizing both the blue and red memories. We start with the simplest heuristic and then proceed to more elaborate ones.

Working with the uncolored tree: LiuUncolored We have shown that the problem TwoM-emoryTraversal of finding a tree-traversal that minimizes both memory is NP-complete. However, when a single memory is considered, the problem becomes polynomial. It is thus natural to adapt the optimal algorithm for the single memory problem proposed by Liu [START_REF] Liu | An application of generalized tree pebbling to sparse matrix factorization[END_REF], to bi-colored trees. The simplest adaptation amounts to considering the tree as uncolored, that is, as if all tasks were processed on the same computing unit with a single memory. On this uncolored tree, illustrated on Figure 4, we apply Liu's optimal algorithm. This heuristic computes an optimal traversal for the sum of the blue and the red memories. The intuition is that minimizing the sum of both memories will lead to a good memory usage for each of them. This heuristic is referred to as LiuUncolored in the following.

Refining the sum with weights: LiuWeightedSum One problem with the previous heuristic is that both memories may not be equivalent. For example, it may well be the case that (input and output) files used by red tasks are much larger that those used by blue tasks. In such a case, minimizing the sum may lead to a much larger amount of blue memory that would be needed, for example, in an optimal traversal for the blue memory. This behavior is not desirable, and we can slightly change the heuristic to (try to) avoid this. We first compute the optimal amount of blue (respectively red) memory that is needed to traverse the tree, as described in Section 4.2, and we denote this amount by M ∞ blue (resp. M ∞ red ). Then, we normalize the memory weight of edges as follows: the memory weight f i of the input edge of node i becomes f i /M ∞ blue if this edge is blue, and f i /M ∞ red if it is red. Then, the corresponding uncolored tree is considered and Liu's optimal algorithm is applied, as in the previous heuristic. This heuristic is called LiuWeightedSum in the following.

LiuWeightedMax In the previous heuristics, when applying Liu's algorithm to modified trees, we minimize the sum (or the weighted sum) of both memory amounts. However, to get closer to the Zenith point, we would like to minimize the maximum, or rather the weighted maximum of both memories. It is possible to modify Liu's algorithm for this new goal. Of course, the resulting algorithm is not optimal anymore (which is coherent with the NP-completeness of the TwoMemoryTraversal problem), but it can be used as a heuristic. Liu's algorithm is a recursive algorithm which, at each node r, combines optimal traversals for the subtrees rooted at the children of r into an optimal traversal for the whole tree rooted in r. The combination relies on the definition of "hill-valley" segments: segments are defined by splitting a subtree schedule at different local minima (the "valley"). These segments are then sorted by non-increasing "hill" minus "valley" values (hill being the local peak memory of the segment). Liu [START_REF] Liu | An application of generalized tree pebbling to sparse matrix factorization[END_REF] proves that such a combination of optimal subtree schedules leads to a global optimal schedule. In this heuristic, we replace the memory criterion used to define of the schedule by the maximum weighted memory: max( BlueMemUsed(σ,i)

M opt blue (T )
, RedMemUsed(σ,i)

M opt red (T )

); we keep the same algorithm for combining subtree schedules. Of course, the proof of optimality does not hold for this new metric. This heuristic is called LiuWeightedMax in the following.

Experiments

In this section, we experimentally compare the memory usage of the heuristics proposed in the previous sections for TwoMemoryTraversal. For each heuristic among BestDepthFirst, LiuUncolored, LiuWeightedSum and LiuWeightedMax, we compute the amount of blue and red memory needed by the traversal. These values are compared to the minimum amount of blue (respectively red) memory needed when the red (resp. blue) memory is unbounded, as described in Section 4.2.

All heuristics have been implemented in C. The optimal value traversal for a single memory is computed using Liu's algorithm [START_REF] Liu | An application of generalized tree pebbling to sparse matrix factorization[END_REF] written as a recursive code. Source code for all the algorithms, heuristics and experiments is publicly available at http://perso.ens-lyon.fr/julien. herrmann/.

Data Sets

We use four different sets of trees, ranging from actual trees arising in sparse matrix computations to random trees. We first describe the data set of uncolored trees which serves as a basis for our realistic colored trees.

Real uncolored trees for Cholesky factorization. The UncoloredRealTrees data set contains assembly trees for a set of sparse matrices obtained from the University of Florida Sparse Matrix Collection (http://www.cise.ufl.edu/research/sparse/matrices/). The chosen matrices satisfy the following assertions: not binary, not corresponding to a graph, square, having a symmetric pattern, a number of rows between 20,000 and 2,000,000, a number of non-zeros per row at least equal to 2.5, and a total number of non-zeros at most equal to 5,000,000; and each chosen matrix has the largest number of non-zeros among the matrices in its group satisfying the previous assertions. At the time of testing, there were 76 matrices satisfying these properties. We first order the matrices using MeTiS [START_REF] Karypis | MeTiS: A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes, and Computing Fill-Reducing Orderings of Sparse Matrices Version 4[END_REF] (through the MeshPart toolbox [START_REF] Gilbert | Geometric mesh partitioning: Implementation and experiments[END_REF]) and amd (available in Matlab), and then build the corresponding elimination trees using the symbfact routine of Matlab. We also perform a relaxed node amalgamation on these elimination trees to create assembly trees. We have created a large set of instances by allowing 1, 2, 4, and 16 (if more than 1.6 × 105 nodes) relaxed amalgamations per node. At the end we compute memory weights and processing times to accurately simulate the matrix factorization: we compute the memory weight n i of a node as η 2 + 2η(µ -1), where η is the number of nodes amalgamated, and µ is the number of non-zeros in the column of the Cholesky factor of the matrix which is associated with the highest node (in the starting elimination tree); the processing cost w i of a node is defined as 2/3η 3 +η 2 (µ-1)+η(µ-1) 2 (these terms corresponds to one Gaussian elimination, two multiplications of a triangular η × η matrix with a η × (µ -1) matrix, and one multiplication of a (µ -1) × η matrix with a η × (µ -1) matrix). Edge weights f i are computed as (µ -1) 2 .

The resulting 644 trees contains from 2, 000 to 1, 000, 000 uncolored nodes. Their depth ranges from 12 to 70, 000, and their maximum degree ranges from 2 to 175, 000.

Real colored trees for Cholesky factorization. The RealTrees data set is obtained by coloring every tree in UncoloredRealTrees in a meaningful way. Every tree node in Uncol-oredRealTrees represents a step of a (η + µ -1) × (η + µ -1) matrix factorization, with a panel of size η. In practice, at each step of the factorization, we aim at processing the GEMM routine (which corresponds to the multiplication of the (µ -1) × η matrix with the η × (µ -1) matrix) on the GPU. Indeed, GEMMs can reach up to 99% of the GPU's theoretical peak performance. Thus, we split every node into two tasks: a red one corresponding to the GEMM routine, and a blue one corresponding to the rest of the factorization.

Real trees with random colors. The RandomColoredRealTrees data set is obtained by randomly coloring every node of every tree in UncoloredRealTrees with an equiprobable choice in the set {red, blue}. Then, communication nodes are added between nodes of different colors.

Real trees with random weights and colors. The RandomWeightedRealTrees data set is obtained by randomly coloring every node of every tree in UncoloredRealTrees with an equiprobable choice in the set {red, blue} and by randomly changing the nodes and edges weight. Every n i is set to a random integer value in 1, N 500 where N is the size of the tree, and every f i is set to a random integer value in 1, N . Then, communication nodes are added between nodes of different colors.

Random trees

The RandomTrees data set is a set of 500 trees with random structure, random weights and random colors. Each tree has been generated as follows: the tree size N is randomly chosen in 1, 32767 . Then, for each node i ∈ 1, N , its parent is randomly chosen in 1, i -1 . The values of its n i and f i are uniformly chosen in 1, 3276 , and its color is randomly chosen between red and blue. Then, communication nodes are added between nodes of different colors.

Results

In this section, we evaluate the performance of the four heuristics introduced above in terms of memory requirement. For every tree T in the data sets, and for every traversal σ returned by the heuristics, we compute the maximum relative overhead of each memory compared to the optimal value: MaxRelativeOverhead(σ, T ) = max(

M σ blue (T )-M opt blue (T ) M opt blue (T ) , M σ red (T )-M opt red (T ) M opt red (T )
). As explained in Section 3, the optimal for both memories (also called Zenith) is a theoretical bound that may be not reachable. Thus, for a tree T , there does not necessarily exist a traversal σ such that MaxRelativeOverhead(σ, T ) = 0. Detailed statistics for the four heuristics are given in Table 2.

We make the following observations:

For the RealTrees data set, BestDepthFirst statistically gives the best results, with an average relative overhead equal to 6.3%,; it reaches the Zenith for 55.6% of the trees. This comes from the particular structure of the assembly trees. Indeed, most nodes in these assembly trees have an input file smaller than the sum of their output files:

f i ≤ j∈Children(i) f j .
This means that when we execute a node, it is more likely to be profitable to execute the whole subtree straightaway. This is why BestDepthFirst turns out to be the best heuristic for the RealTrees and the RandomColoredRealTrees data sets. Besides, LiuUncolored is very close to the BestDepthFirst performances on the RealTrees data set, with an average relative overhead equal to 6.6%. On the contrary, LiuWeightedMax appears to be not well-designed for the structure of the assembly trees in RealTrees, with an average relative overhead equal to 8.4%; it can require up to 2.16 times the optimal memory for some trees.

The structure of the trees in the RandomColoredRealTrees data set is close to the trees in RealTrees, and the results are similar. BestDepthFirst statistically gives the best results with an average relative overhead equal to 3.8%, and LiuUncolored provides the second best results with relative overhead equal to 5.2%.

For the RandomWeightedRealTrees data set, file sizes are randomized, and Best-DepthFirst is no longer adapted to such trees; it provides an average relative overhead equal to 20.9%. Much worse, LiuUncolored can require up to 5.13 times the optimal memory for some trees in RandomWeightedRealTrees. On the contrary, LiuWeight-edMax appears to be well-designed for the trees in RandomWeightedRealTrees, with an average relative overhead two times lower than that of BestDepthFirst.

The results for the RandomTrees data confirm that LiuWeightedMax is the best of the four heuristics when dealing with trees with random structure. It gives the best results with an average relative overhead equal to 3.4%, and exhibits a relative overhead inferior to 10% for 92% of the random trees.

Figures 10, 11 and 12 provide complete results of the simulations. In each figure, a point represents one scenario (one heuristic executed on one tree of the data set). To better visualize the distribution, we also plot a "cross" for each heuristic: the center of this cross is the average result, while the branches represent the scope of each objective between the 10th and 90th percentile of the distribution. For the RealTrees data set, as explained above, we colored in red the nodes corresponding to the GEMM routine, and in blue the others nodes. Thus, every red nodes appears to have a communication node as father, and an unique communication node as child. With this structure, all of our heuristics gives the optimal memory usage for the red memory. This specification fits well with practice, where one aims at not overloading the GPU memory. Figure 9 provides the detailed distribution of the blue memory usage for the heuristics.

These figures exhibit the same trends for average values as observed in Table 2. For the RandomColoredRealTrees data set in Figure 10, and for the RandomTrees data set in Figure 12, we see that many traversals returned by the heuristics are optimal for at least one of the two memories, whereas for the RandomWeightedRealTrees data set in Figure 11, many more of the returned traversals are non-optimal for either memory. We also observe that LiuUncolored can require around 5 times the optimal red memory in two scenarios. These results show that the performance of the heuristics are strongly related to the structure of the trees. While BestDepthFirst achieves nice results for the realistic assembly trees, LiuWeightedMax appears to be a better solution when dealing with more random structures.

Conclusion

In this paper, we have studied the bi-criteria memory minimization problem that arises when traversing a task tree for a system composed of two different computing units with their own memory. After relating this problem to the well-studied one-memory problem, we have proved that the search for an optimal solution, as well as the design of approximation algorithms guaranteed for both memories are NP-complete problems. We have then proposed several heuristics, among which is the optimal depth-first traversal.

Admittedly, the platform model used in this paper is a simplified one, but this was the key to derive complexity results in this initial study. In future work, the model should be refined in several directions, so as to more accurately account for all the characteristics of hybrid platforms (using both CPUs and GPUs); however, this is not expected to change the NP-completeness results. A first step towards a more realistic model would be to include computation times for the tasks, and to try to minimize both the processing time of the total tree, and the amount of blue and red memories needed. A second step would consist in providing each task with two different running times rather than a color, and to give the ability for the scheduler to choose the computing unit for each task based on running time and memory. Given the complexity of the problem in the simple RR n°8226

( 2 )

 2 root , otherwise, since the execution of R[START_REF] Augonnet | Starpu: a unified platform for task scheduling on heterogeneous multicore architectures[END_REF]

Figure 3 :Figure 4 :

 34 Figure 3: Tree corresponding to Inst 2 in the proof of Theorem 1

represents T 2 .

 2 ∀n ≥ 2, M opt blue (T n ) = 3 Consider the traversal σ blue that processes T n as follows: -If n = 0, σ blue processes the node B 0 -If n > 0, σ blue processes the nodes B n and C n . Then T (lef t) n-1 is processed recursively. Nodes R n and C ′ n follow. And finally T (right) n-1

Figure 6 :Figure 7 :

 67 Figure 6: Recursive definition of T n in the proof of Theorem 3

Figure 8 :

 8 Figure 8: Tree corresponding to Inst 2 in the proof of Theorem 5

Figure 9 :

 9 Figure 9: Percentage distribution of the blue memory usage for the RealTrees data set.

Figure 10 :Figure 11 :

 1011 Figure 10: Distribution of each memory usage for the RandomColoredRealTrees data set.

Figure 12 :

 12 Figure 12: Distribution of each memory usage for the RandomTrees data set.

Table 2 :

 2 Statistics on the maximum relative overhead for each memory required by the four heuristics (comparison with the Zenith). Frac. of Opt. (respectively Frac ≤ 10%) counts the fractions of cases when the heuristics achieve the Zenith (resp. has a degradation not larger than 10%).

RR n°8226

This equivalence has been formally proven in[START_REF] Jacquelin | On optimal tree traversals for sparse matrix factorization[END_REF] for single-memory platforms, and it is straightforward to extend the proof for two-memory systems.

case, we do not expect to find approximation algorithms, but rather to design simple heuristics (as BestDepthFirst) that may be optimal under restrictive conditions, either on the traversal type or on the tree structure.

RESEARCH CENTRE GRENOBLE -RHÔNE-ALPES


Ingrid Girardeau

Soil environmental assessments on schools built on or in the vicinity of past industrial facilities

The selection of schools was performed by crossing the schools database with the past industrial activities inventory (BASIAS). Around 2000 establishments on the entire country were identified. Although the BASIAS inventory provides information on past industrial activities, it does not enable to know the current soil quality.

For this purpose, soil assessments must be done on the selected schools. The French State funded a five-year budget of about 50 million euros for this task.

In order to ensure the homogeneity of the action and costs control at the national level, BRGM was put in charge of the technical organisation of the assessments.

Assessments were designed to control if pollution that may be present in the soil, does not deteriorate the air inside the buildings, playground areas for young children, soil and drinking water. Taking into account the uses of schools facilities and contamination that may be found in soils and groundwater, assessments are made on the relevant media of exposure:

• if non-volatile pollution are involved, surface soils controls are carried out in establishments accommodating children under 7 years if accessible bare soils are identified,

• if volatile pollution are involved, controls of soil gas and air in underfloor spaces, if any, are made. They are followed by controls of indoor air quality in case of trouble.

• if necessary drinking water quality in the distribution network is controlled.

Three categories of post-assessment situations are defined.

• Category A: the soil under the establishment poses no problem • Category B: the current layout and uses of the establishment allow to protect people from exposure to potential or proven pollutants.

However information management procedures must be set up to explain what must be done if the facilities or uses of the school deteriorate or are modified.

• Category C: results reveal the presence of contamination that requires the implementation of technical management or even health protection measures.

Assessments results and ranking of establishments are examined by a national working group composed of representatives of all involved ministries and their technical support.

The assessments campaign started in summer 2010 on a first list of 900 establishments. Eventually, it will run on the entire country over a period of five years to involve a total of some 2000 establishments.