Loris Marchal

Oliver Sinnen

Scheduling tree-shaped task graphs to minimize memory and makespan

Keywords: Scheduling, Memory-aware, Trees, Bi-objective optimization

This paper investigates the execution of tree-shaped task graphs using multiple processors. Each edge of such a tree represents a large IO file. A task can only be executed if all input and output files fit into memory, and a file can only be removed from memory after it has been consumed. Such trees arise, for instance, in the multifrontal method of sparse matrix factorization. The maximum amount of memory needed depends on the execution order of the tasks. With one processor the objective of the tree traversal is to minimize the required memory. This problem was well studied and optimal polynomial algorithms were proposed. Here, we extend the problem by considering multiple processors, which is of obvious interest in the application area of matrix factorization. With the multiple processors comes the additional objective to minimize the time needed to traverse the tree, i.e., to minimize the makespan. Not surprisingly, this problem proves to be much harder than the sequential one. We study the computational complexity of this problem and provide an inapproximability result even for unit weight trees. Several heuristics are proposed, each with a different optimization focus, and they are analyzed in an extensive experimental evaluation using realistic trees.

Ordonnancement d'arbres de tâches pour minimiser mémoire et temps d'exécution

Résumé : Dans ce rapport, nous nous intéressons au traitement d'arbres de tâches par plusieurs processeurs. Chaque arête d'un tel arbre représente un gros fichier d'entrée/sortie. Une tâche peut être traitée seulement si l'ensemble de ses fichiers d'entrée et de sortie peut résider en mémoire, et un fichier ne peut être retiré de la mémoire que lorsqu'il a été traité. De tels arbres surviennent, par exemple, lors de la factorisation de matrices creuses par des méthodes multifrontales. La quantité de mémoire nécessaire dépend de l'ordre de traitement des tâches. Avec un seul processeur, l'objectif est naturellement de minimiser la quantité de mémoire requise. Ce problème a déjà été étudié et des algorithmes polynomiaux ont été proposés. Nous étendons ce problème en considérant plusieurs processeurs, ce qui est d'un intérêt évident pour le problème de la factorisation de grandes matrices. Avec plusieurs processeurs se pose également le problème de la minimisation du temps nécessaire pour traiter l'arbre. Nous montrons que comme attendu, ce problème est bien plus compliqué que dans le cas séquentiel. Nous étudions la complexité de ce problème et nous fournissons des résultats d'inaproximabilité, même dans le cas de poids unitaires. Nous proposons plusieurs heuristiques pour obtenir un ordonnancement, qui se concentrent chacune sur un objectif différent. Nous analysons leurs performances par une large campagne de simulations utilisant des arbres réalistes.

Mots-clés : Ordonnancement, Contrainte Mémoire, Arbres, Optimisation bi-critère

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, as the size of the data to be processed is increasing, the memory footprint of the application must be optimized as it can have a dramatic impact on the algorithm execution time. 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 out-of-core techniques. There are very few existing studies on the minimization of the memory footprint when scheduling task graphs, and even fewer of them targeting parallel systems.

We consider the following memory-aware parallel scheduling problem for rooted trees. The nodes of the 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 takes as input several large files, one for each of its children, and it produces a single large file, and the different files may have different sizes. Furthermore, the execution of any node requires its execution file to be present; the execution file can be seen as the program of the task. We are to execute such a set of tasks on a parallel system made of p identical processing resources sharing the same memory. The execution scheme corresponds to a schedule of the tree where processing a node of the tree translates into reading the associated input files and producing the output file. How can the tree be scheduled so as to optimize the memory usage?

Modern computing platforms exhibit a complex memory hierarchy ranging from caches to RAM and disks and even sometimes tape storage, with the classical property that the smaller the memory, the quicker. Thus, to avoid large running times, one usually wants to avoid the use of memory devices whose IO bandwidth is below a given threshold: even if out-of-core execution (when large data are unloaded to disks) is possible, this requires special care when programming the application and one usually wants to stay in the main memory (RAM). This is why in this paper, we are interested in the question of minimizing the amount of main memory needed to completely process an application.

Throughout the paper, we consider in-trees where a task can be executed only if all its children have already been executed. (This is absolutely equivalent to considering out-trees as a solution for an in-tree can be transformed into a solution for the corresponding out-tree by just reversing the arrow of time, as outlined in [START_REF] Jacquelin | On optimal tree traversals for sparse matrix factorization[END_REF].) A task can be processed only if all its files (input, output, and execution) fit in currently available memory. At a given time, many files may be stored in the memory, and at most p tasks may be processed by the p processors. This is obviously possible only if all tasks and execution files fit in memory. When a task finishes, the memory needed for its execution file and its input files is released. Clearly, the schedule which determines the processing times of each task plays a key role in determining which amount of main memory is needed for a successful execution of the whole tree.

The first motivation for this work comes from numerical linear algebra. Tree workflows (assembly or elimination trees) arise during the factorization of sparse matrices, and the huge size of the files involved makes it absolutely necessary to reduce the memory requirement of the factorization. The sequential version of this problem (i.e., with p = 1 processor) has already been studied. Liu [START_REF] Joseph | On the storage requirement in the out-of-core multifrontal method for sparse factorization[END_REF] discusses how to find a memory-minimizing traversal when the traversal is required to correspond to a postorder traversal of the tree. In the follow-up study [START_REF] Joseph | An application of generalized tree pebbling to sparse matrix factorization[END_REF], an exact algorithm is shown to solve the problem, without the postorder constraint on the traversal. Recently, some of us [START_REF] Jacquelin | On optimal tree traversals for sparse matrix factorization[END_REF] proposed another algorithm to find a memory-optimal traversal, which proved to be faster on existing elimination trees, although being of the same worst-case complexity (O(n 2 )).

The parallel version of this problem is a natural continuation of these studies: when processing large elimination trees, it is very meaningful to take advantage of parallel processing resources. However, to the best of our knowledge, there exist no theoretical studies for this problem. The key contributions of this work are:

• The proof that the parallel variant of the pebble game problem is NP-complete. This shows that the introduction of memory constraints, in the simplest cases, suffices to make the problem NP-hard. • The proof that no algorithm can simultaneously deliver a constant-ratio approximation for the memory minimization and for the makespan minimization. • A set of heuristics having different optimizing focus.

• An exhaustive set of simulations using realistic tree shaped task graphs to assess the relative and absolute performance of these heuristics. The rest of this paper is organized as follows. Section 2 reviews related studies. The notation and formalization of the problem are introduced in Section 3. Complexity results are presented in Section 4 while Section 5 proposes different heuristics to solve the problem, which are evaluated in Section 6.

2 Background and Related Work

Sparse matrix factorization

As mentioned above, 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] Joseph | On the storage requirement in the out-of-core multifrontal method for sparse factorization[END_REF][START_REF] Joseph | An application of generalized tree pebbling to sparse matrix factorization[END_REF] on memory minimization for postorder or general tree traversals presented in the previous section. Memory minimization is still a concern in modern multifrontal solvers when dealing with large matrices. Among other, 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 dataintensiveworkflows 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] Joseph | 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 our problem when 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].

To the best of our knowledge, there have been no attempts to extend these results to parallel machines, with the objective of minimizing both memory and total execution time. We present such an extension in Section 4.

Model and objectives

Application model

We consider in this paper a tree-shaped task-graph T composed of n nodes, or tasks, numbered from 1 to n. Nodes in the tree have an output file, an execution file (or program), and several input files (one per child). More precisely:

• Each node i in the tree has an execution file of size n i and its processing on a processor takes time w i .

• Each node i has an output file of size f i . If i is not the root, its output file is used as input by its parent parent(i); if i is the root, its output file can be of size zero, or contain outputs to the outside world.

• Each non-leaf node i in the tree has one input file per child. We denote by Children(i) the set of the children of i. For each child j ∈ Children(i), task j produces a file of size f j for i.

If i is a leaf-node, then Children(i) = ∅ and i has no input file: we consider that the initial data of the task either reside in its execution file or are read from disk (or received from the outside word) during the execution of the task.

During the processing of a task i, the memory must contain its input files, the execution file, and the output file. The memory needed for this processing is thus:

  j∈Children(i) f j   + n i + f i
After i has been processed, its input files and program are discarded, while its output file is kept in memory until the processing of its parent.

Platform model and objectives

In this paper, our goal is to design the simpler platform model which allows to study memory minimization on a parallel platform. We thus consider p identical processors which share a single memory. We do not consider here a hard constraint on the memory, but we rather include memory in the objectives. We thus consider multi-criteria optimization with the following two objectives:

• Makespan. Our first objective is the classical makespan, or total execution time, which corresponds to the times-span between the beginning of the execution of the first leaf task and the end of the processing of the root task.

• Memory. Our second objective is the amount of memory needed for the computation. At each time step, some files are stored in the memory and some task computations occur, which induces a memory usage. The peak memory is the maximum usage of the memory over the whole schedule, which we aim at minimizing.

Complexity results in the Pebble Game model

Since there are two objectives, the decision version of our problem can be stated as follows.

root

N 1 L 1 1 L 1 2 . . . L 1 3m×a1 N 2 L 2 1 L 2 2 . . . L 2 3m×a2 . . . N 3m L 3m 1 L 3m 2 . . . L 3m 3m×a3m
Figure 1: Tree used for the NP-completeness proof Definition 1 (BiObjectiveParallelTreeScheduling). Given a tree-shaped task graph T provided with memory weights and task durations, p processors, and two bounds B Cmax and B mem , is there a schedule of the task graph on the processors whose makespan is not larger than B Cmax and whose peak memory is not larger than B mem ?

This problem is obviously NP-complete. Indeed, when there are no memory constraints (B mem = ∞) and when the task tree does not contain any inner node, that is, when all tasks are either leaves or the root, then our problem is equivalent to scheduling independent tasks on a parallel platform which is an NP-complete problem as soon as tasks have different execution times [START_REF] Lenstra | Complexity of machine scheduling problems[END_REF]. On the contrary minimizing the makespan for a tree of same-size tasks can be solve in polynomial-time when there are no memory constraints [START_REF] Hu | Parallel sequencing and assembly line problems[END_REF]. In this section, we consider the simplest variant of the problem. We assume that all input files have the same size (∀i, f i = 1) and no extra memory is needed for computation (∀i, n i = 0). Furthermore, we assume that the processing of each node takes a unit time: ∀i, w i = 1. We call this variant of the problem the Pebble Game model since it perfectly corresponds to pebble game problems introduced above: the weight f i = 1 corresponds to the pebble put on one node once it has been processed and its results

is not yet discarded. Processing a node requires to put an extra pebble on this node and is done in unit time.

In this section, we first show that even in this simple variant, the introduction of memory constraints (a limited number of pebbles) makes the problem NP-hard (Section 4.1). Then, we show that when trying to minimize both memory and makespan, it is not possible to get a solution with a constant approximation ratio for both objectives (Section 4.2).

NP-completeness

Theorem 1. The BiObjectiveParallelTreeScheduling problem is NP-complete in the Pebble Game model (i.e., with ∀i,

f i = w i = 1, n i = 0).
Proof. First, it is straightforward to check that the problem is in NP: given a schedule, it is easy to compute its peak memory and makespan.

To prove the problem NP-completeness, we perform a reduction from 3-Partition, which is known to be NP-complete in the strong sense [START_REF] Garey | Computers and Intractability, A Guide to the Theory of NP-Completeness[END_REF]. We consider the following instance I 1 of the 3-Partition problem: let a i be 3m integers and B an integer such that a i = mB. We consider the variant of the problem, also NP-complete, where ∀i, B/4 < a i < B/2. To solve I 1 , we need to solve the following question: does there exist a partition of the a i 's in m subsets S 1 , . . . , S m , each containing exactly 3 elements, such that, for each S k , i∈S k a i = B. We build the following instance I 2 of our problem, illustrated on Figure 1. The tree contains a root r with 3m children, the N i 's, each one corresponding to a value a i . Each node N i has 3m × a i children, which are leaf nodes. The question is to find a schedule of this tree on p = 3mB processors, whose peak memory is not larger than B mem = 3m × B + 3m and whose makespan is not larger than B Cmax = 2m + 1.

Assume first that there exists a solution to I 1 , i.e., that there are m subsets S k of 3 elements with i∈S k a i = B. In this case, we build the following schedule:

• At step 1, we process all the nodes L i1

x , L j1 y , and L k1 z with S 1 = {a i1 , a j1 , a k1 }. There are 3mB = p such nodes, and the amount of memory needed is also 3mB.

• At step 2, we process the nodes N i1 , N j1 , N k1 . The memory needed is 3mB + 3.

• At step 2n + 1, with 1 ≤ n ≤ m -1, we process the 3mB = p nodes L in x , L jn y , L kn z with S n = {a in , a jn , a kn }. The amount of memory needed is 3mB + 3n (counting the memory for the output files of the N t nodes previously processed).

• At step 2n + 2, with 1 ≤ n ≤ m -1, we process the nodes N in , N jn , N kn . The memory needed for this step is 3mB + 3(n + 1).

• At step 2m + 1, we process the root node and the memory needed is 3m + 1.

Thus, the peak memory of this schedule is B mem and its makespan B Cmax .

On the contrary, assume that there exists a solution to problem I 2 , that is, that there exists a schedule of makespan at most B Cmax = 2m + 1. Without loss of generality, we assume that the makespan is exactly 2m + 1. We start by proving that at any step of the algorithm there are at most three of the N i nodes that are processed. By contradiction, assume that four (or more) such nodes N i1 , N i2 , N i3 , N i4 are processed during a certain step. We recall that a i > B/4 so that a i1 + a i2 + a i3 + a i4 > B and thus a i1 + a i2 + a i3 + a i4 ≥ B + 1. The memory needed at this step is thus at least (B + 1)3m for the children of the nodes N i1 , N i2 , N i3 , and N i4 and 4 for the nodes themselves, hence a total of at least (B + 1)3m + 4, which is more than the prescribed bound B mem . Thus, at most three of N i nodes are processed at any step. In the considered schedule, the root node is processed at step 2m + 1. Then, at step 2m, some of the N i nodes are processed, and at most three of them from what precedes. The a i 's corresponding to those nodes make the first subset S 1 . Then all the nodes L j

x such that a j ∈ S 1 must have been processed at the latest at step 2m -1, and they occupy a memory footprint of 3m aj ∈S1 a j at steps 2m -1 and steps 2m. Let us assume that a node N k is processed at step 2m -1. For the memory bound B mem not to be satisfied we must have a k + aj ∈S1 a j ≤ B. (Otherwise, we would need a memory of at least 3m(B + 1) for the involved L j

x nodes plus 1 for the node N k ). Therefore, node N k could have been processed at step 2m. We then modify the schedule so as to schedule N k at step 2m and thus we add k to S 1 . We can therefore assume, without loss of generality, that no N i node is processed at step 2m -1. Then, at step 2m -1 only children of the N j nodes with a j ∈ S 1 are processed, and all of them are. So, none of them have any memory footprint before step 2m -1. We then generalize this analysis: at step 2i, for 1 ≤ i ≤ m -1, only some N j nodes are processed and they define a subset S i ; at step 2i -1, for 1 ≤ i ≤ m -1, are processed exactly the nodes L k x that are children of the nodes N j such that a j ∈ S i .

Because of the memory constraint, each of the m subsets of a i 's built above sum to at most B. Since they contain all a i 's, their sum is mB. Thus, each subset S k sums to B and we have built a solution for I 1 .

Joint minimization of both objectives

As our problem is NP-complete, it is natural to wonder whether there exist approximation algorithms. Here, we prove that there does not exist schedules which approximates both the minimum makespan and the minimum memory with constant factors1 . Theorem 2. There is no algorithm that is both an α-approximation for makespan minimization and a β-approximation for memory peak minimization when scheduling in-tree task graphs. 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 input tree T in a time not greater than α times the optimal execution time while using a peak memory that is not greater than β times the optimal peak memory.

The tree. Figure 2 presents the tree used to derive a contradiction. This tree is made of n identical subtrees whose roots are the children of the tree root. The values of n and δ will be fixed later on. Optimal execution time. The optimal execution time is equal to the length of the critical path, as we have made no hypothesis on the number of available processors. The critical path has a length of δ + 2, which is the length of the path from the root to any b i δ+1 , a i,δ-1

root cp 1 1 d 1 1 a 1,1 δ a 1,1 δ-1 ... a 1,1 2 a 1,1 1 cp 1 2 d 1 2 a 1,2 δ-1 ... a 1,2 2 a 1,2 1 cp 1 δ-1 d 1 δ-1 a 1,δ-1 2 a 1,δ-1 1 b 1 δ b 1 δ+1 cp 2 1 d 2 1 a 2,1 δ a 2,1 δ-1 ... a 2,1 2 a 2,1 1 cp 2 2 d 2 2 a 2,2 δ-1 ... a 2,2 2 a 2,2 1 cp 2 δ-1 d 2 δ-1 a 2,δ-1 2 a 2,δ-1 1 b 2 δ b 2 δ+1 . . . cp n 1 d n 1 a n,1 δ a n,1 δ-1 ... a n,1 2 a n,1 1 cp n 2 d n 2 a n,2 δ-1 ... a n,2 2 a n,2 1 cp n δ-1 d n δ-1 a n,δ-1 2 a n,δ-1 1 b n δ b n δ+1
1 , or a i,δ-1 2 node, with 1 ≤ i ≤ n.
Optimal peak memory. Let us consider any sequential execution that is optimal with regard to the peak memory usage. Under this execution, let d i 1 be the last processed node among the d j 1 nodes, 1 ≤ j ≤ n. We consider the step at which node d i 1 is processed. As, by hypothesis, all the d j 1 nodes, 1 ≤ j ≤ n and j = i, have already been processed, there are in memory at that step at least n -1 results. The processing of d i 1 requires δ + 1 memory units as this node has δ children. Hence, a total memory usage of at least (n -1) + (δ + 1) = δ + n for the processing of d i 1 . This is obviously a lower bound on the optimal peak memory usage. We now show that this bound can be reached.

We consider the following schedule:

• Completely process first the subtree rooted at cp 1 1 , then the subtree rooted at cp 2 1 , and so on.

• The subtree rooted at cp i 1 is processed as follows: for j going from 1 to δ -1, process the δ -j + 1 children of node d j i , then node d j i ; then process nodes b i δ+1 , b i δ , and nodes cp i δ-1 to cp i 1 . When the subtree rooted at cp i 1 is processed there are in memory exactly i -1 results coming from the processing of the first i -1 subtrees. These are exactly the results of the processing of the nodes cp 1 1 , ..., cp i-1 1 . The processing of node d i j requires a memory of δ -j + 2, for 1 ≤ j ≤ δ -1: this node has δ -j + 1 inputs and one output. When node d i j is processed the memory contains j -1 results due to the processing of the subtree rooted at cp 1 i : the results of the processing of nodes d i 1 to d i j-1 . Hence, the total memory usage when node d i j is processed is (i -1) + (δ -j + 2) + (j -1) = i + δ. Accordingly when b i δ+1 is processed the memory usage is (i -1) + (δ -1) + 1 = i + δ -1, and when b i δ+1 is processed it is (i -1) + (δ -1) + 2 = i + δ. Later on, when node cp i j is processed, for 1 ≤ j ≤ δ -1, the memory usage is (i -1) + j + 2 = i + j + 1 ≤ i + δ. Indeed, at that time, the only data in memory relative to the processing of the subtree rooted at cp i 1 are 1) the results of the nodes d i 1 through d i j , 2) the result of cp i j+1 if j < δ -1 or of b i δ otherwise, and 3) the result of the processing of node cp i j . Under this schedule, the peak memory usage during the processing of the subtree rooted at cp i 1 is i + δ. The overall peak memory usage of the studied schedule is then n + δ which is thus the optimal peak memory usage.

Lower bound on the peak memory usage of A. The peak memory usage is not smaller than the average memory usage. We derive the desired contradiction by using the average memory usage of algorithm A as a lower bound to its peak memory usage.

By hypothesis, algorithm A is α competitive with regard to makespan minimization. Therefore the processing of the tree by algorithm A should complete at the latest at time α(δ + 2). To ensure that, the n cp i 1 nodes, 1 ≤ i ≤ n, must all be executed at the latest at time α(δ + 2) -1. Therefore, all the descendants of these nodes must be executed between time 0 and time α(δ + 2) -2. We now evaluate the number of these descendants and their memory footprints.

The descendants of node cp i 1 includes the two nodes b i δ and b i δ+1 , the δ -

2 nodes cp i 2 to cp i δ-1 , the δ -1 nodes d i 1 through d i δ-1
, and, finally, the descendants of the d i j nodes, for 1 ≤ j ≤ δ -1. As node d i j has δ -j + 1 descendants, the number of descendants of node cp i 1 is:

2 + (δ -2) + (δ -1) + δ-1 j=1 (δ -j + 1) = 2δ -1 +     δ j=1 j   -1   = δ 2 + 5δ -4 2
All together, the nodes

cp i 1 , for 1 ≤ i ≤ n have n δ 2 +5δ-4 2
descendants. We consider the memory footprint of each of these nodes between time step 0 and time step α(δ + 2) -2. The result of the processing of each of theses nodes must be in memory for at least two steps in this interval, the step at which the node is processed and the step at which its parent node is processed, except for the nodes d 1 j , 1 ≤ j ≤ n, and cp k 2 , for 1 ≤ k ≤ n, whose parents need not have been processed in that interval and thus need only to be present in memory during one time step. The overall memory footprint between time 0 and α(δ + 2) -2 is then:

n δ 2 + 5δ -4 2 -2 × 2 + 2 × 1 = n δ 2 + 5δ -6 .
The average memory usage during that period is thus:

n δ 2 + 5δ -6 α(δ + 2) -2 .
This is obviously a lower bound on the overall peak memory usage. This bound enables us to derive a lower bound lb on the approximation ratio ρ of algorithm A with regard to memory usage:

ρ ≥ lb = n(δ 2 +5δ-6) α(δ+2)-2 n + δ = n δ 2 + 5δ -6 (α(δ + 2) -2)(n + δ) .
We then let δ = n 2 . Therefore,

lb = n n 4 + 5n 2 -6 (α(n 2 + 2) -2)(n + n 2 )
.

Then, lb tends to +∞ when n tends to infinity. There is thus a value n 0 such that, for any value n ≥ n 0 , the right-hand side is greater than 2β. We let n = n 0 and we obtain:

lb = n 0 n 4 0 + 5n 2 0 -6 (α(n 2 0 + 2) -2)(n 0 + n 2 0 ) ≥ 2β,
which contradicts the definition of β.

Heuristics

Given the complexity of optimizing the makespan and memory at the same time, we have investigated heuristics and propose three algorithms: ParSubtrees, ParInnerFirst, and ParDeep-estFirst. The intention is that the proposed algorithms cover a range of use cases, where the optimization focus wanders between the makespan and the required memory. ParSubtrees employs a memory-optimizing sequential algorithm for it subtrees, hence its focus is more on the memory side. In contrast, ParInnerFirst and ParSubtrees are list scheduling based algorithms, which should be stronger in the makespan objective. Nevertheless, ParInnerFirst tries to approximate a postorder in parallel, which is good for memory in sequential. ParDeepest-First's focus is fully on the makespan. The minimal memory requirement M is achieved by using the optimal sequential algorithm [9], i.e., using p = 1 processor. Employing more processors cannot reduce the amount of memory required, yet the sequential algorithm is of course only a p-approximation of the optimal parallel makespan C * max .

Heuristic ParSubtrees

The most natural idea to process a tree T in parallel is arguably its splitting into subtrees and their subsequent parallel processing, each using the sequentially memory-optimal algorithms [START_REF] Jacquelin | On optimal tree traversals for sparse matrix factorization[END_REF][START_REF] Joseph | An application of generalized tree pebbling to sparse matrix factorization[END_REF]. An underlying idea is to give each processor a whole subtree in order to enable a lot of parallelism while also limiting the increase of the peak memory usage that can be observed when several processors work on the same subtree. Algorithm 1 outlines such an algorithm, together with the routine for splitting T into subtrees given in Algorithm 2. The makespan obtained using ParSubtrees is denoted by C ParSubtrees max .

Algorithm 1: ParSubtrees (T , p)

1 Split tree T into q subtrees (q ≤ p) and remaining set of nodes, using SplitSubtrees (T , p). 2 Concurrently process the q subtrees, each using memory minimizing algorithm, e.g. [START_REF] Jacquelin | On optimal tree traversals for sparse matrix factorization[END_REF]. 3 Sequentially process remaining set of nodes, using memory minimizing algorithm.

In this approach, q subtrees of T , q ≤ p, are processed in parallel. Each of these subtrees is a maximal subtree of T . In other words, each of these subtrees include all the descendants (in T ) of its root. The nodes not belonging to the q subtrees are processed sequentially. These are the nodes where the q subtrees merge, the nodes included in subtrees that where produced in excess (if more than p subtrees where created), and the ancestors of these nodes. An alternative approach, as discussed below, is to process all subtrees in parallel, assigning more than one subtree to each processor, but Algorithm 1 allows us to find a makespan-optimal splitting into subtrees, established shortly in Lemma 1.

As w i is the computation weight of node i, W i denotes the total computation weight (i.e., sum of weights) of all nodes in the subtree rooted in i, including i. SplitSubtrees uses a node priority queue P Q in which the nodes are sorted by non-increasing W i , and ties are broken according to non-increasing w i . head(P Q) returns the first node of P Q, while popHead(P Q) also removes it. P Q[i] denotes the i-th element in the queue.

SplitSubtrees starts with the root and continues splitting the largest subtree (in terms of W) until this subtree is a leaf node (W head(P Q) = w head(P Q) ). The execution time of Step 2 of ParSubtrees is that of the largest of the q subtrees, hence W head(P Q) of the splitting. Splitting subtrees that are smaller than the largest leaf (W j < max i∈T w i ) cannot decrease the parallel time, but only increase the sequential time. More generally, given any splitting s of T into subtrees, the best execution time for s with ParSubtrees is achieved by choosing the p largest subtrees for the parallel Step 2. This can be easily derived, as swapping a large tree included in the sequential part with a smaller tree included in the parallel part cannot increase the total execution time.

Lemma 1. SplitSubtrees returns a splitting of T into subtrees that results in the makespanoptimal processing of T with ParSubtrees.

Proof. The proof is by contradiction. Let S be the splitting into subtrees selected by SplitSubtrees. Assume now that there is a different splitting S opt which results in a shorter processing Algorithm 2: SplitSubtrees (T , p)

1 Compute weights W i , ∀i ∈ T 2 P Q ← root 3 seqSet ← ∅ 4 Cost(0) = W root 5 s ← 1 /* splitting rank */ 6 while W head(P Q) > w head(P Q) do 7 node ← popHead(P Q) 8 seqSet ← seqSet ∪ node 9 P Q ← Children(node) 10 C ParSubtrees max (s) = W head(P Q) + i∈seqSet w i + |P Q| i=P Q[p+1] W i 11 s ← s + 1 12 Select splitting x with C ParSubtrees max (x) = min s-1 t=0 C ParSubtrees max (t)
with ParSubtrees.

Let r be the root node of a heaviest subtree in S opt . Let t be the first step in SplitSubtrees where a node, say r t , of weight W r is the head of P Q at the end of the step (r t is not necessarily equal to r, as there can be more than one subtree of weight W r ). There is always such a step t, because all subtrees are split by SplitSubtrees until at least one of the largest trees is a leaf node. By definition of r, there cannot be any leaf node heavier than W r . The cost of the solution of step t is C ParSubtrees max (t) = W r + Seq(t), hence parallel time plus sequential time, denoted by Seq(t). Seq(t) is the total weight of the sequential set seqSet plus the total weight of the surplus subtrees (that is, of all the subtrees except the p ones of largest weights). The cost of S opt is C * max = W r + Seq(S opt ), given that r is the root of a heaviest subtree of S opt by definition. The splitting at step t (and any other splitting considered by SplitSubtrees) cannot be identical to S opt , otherwise SplitSubtrees would have selected that splitting. All subtrees that were split in SplitSubtrees before step t were strictly heavier than W r . Thus, there cannot exist any subtree in S opt , whose subtrees are part of the splitting at step t. Hence for every subtree T j in the splitting at step t the following property holds: either T j is part of S opt or a splitting of T j into subtrees is part of S opt . It directly follows that Seq(t) ≤ Seq(S opt ), because every splitting of a tree into subtrees increases the sequential time by at least the root's weight. As the parallel time is identical for t and S opt , namely W r , it follows that C ParSubtrees max (t) ≤ C * max , which is a contradiction to S opt 's shorter processing time. ), e.g., [START_REF] Jacquelin | On optimal tree traversals for sparse matrix factorization[END_REF][START_REF] Joseph | An application of generalized tree pebbling to sparse matrix factorization[END_REF], or O(n log(n)) if the optimal postorder suffices. Thus the total complexity of ParSubtrees is O(n 2 ) or O(n log(n)), depending on the chosen sequential algorithm.

Complexity

ParSubtrees has the following guarantees for the memory requirement and makespan.

Memory ParSubtrees is a (p + 1)-approximation algorithm for peak memory minimization.

During the parallel part of ParSubtrees the total memory used is less than p times the memory for the complete sequential execution (M seq ), M p ≤ p • M seq . This is because each of the p processors executes a maximal subtree and that the processing of any subtree uses, obviously, less memory (if done optimally) than the processing of the whole tree. During the sequential part of ParSubtrees the memory is bounded by M s ≤ M seq + p • max i∈T f i ≤ (p + 1)M seq , where the second term is for the output files produced by the up to p subtrees processed in parallel. Hence, in total: Makespan ParSubtrees delivers a p-approximation algorithm for makespan minimization. In other words, the makespan achieved by ParSubtrees can be up to p times worse than the optimal makespan and thus may be not faster than the sequential execution. This can be derived readily with a tree of height 1 and p • k leaves (a fork) and

M ≤ (p + 1)M seq root 1 2 ... p • k -1 p • k
w i = 1, ∀i ∈ T ,
where k is a large integer (this tree is depicted on Figure 3). The optimal makespan for such a tree is

C * max = kp/p + 1 = k + 1. With ParSubtrees the makespan is C max = 1 + (1 + pk -p) = p(k -1) + 2.
When k tends to +∞ the ratio between the makespans tends to p.

Given the just observed worst case for the makespan, a makespan optimization for ParSubtrees is to allocate all produced subtrees to the p processors instead of only p. This can be done by ordering the subtrees by non-increasing total weight and allocating each subtree in turn to the processor with the lowest total weight. Each of the parallel processors executes its subtrees sequentially. This optimized form of the algorithm shall be named ParSubtreesOptim. Note that this optimization should improve the makespan, but it will likely worsen the peak memory usage.

Heuristic ParInnerFirst

ParSubtrees is a high level algorithm employing sequential memory-optimized algorithms. An alternative is to design algorithms that directly work on the tree in parallel and we present two such algorithms. From the sequential case it is known that a postorder traversal, while not optimal for all instances, provides good results [START_REF] Jacquelin | On optimal tree traversals for sparse matrix factorization[END_REF]. Our intention is to extend the principle of postorder traversal to the parallel processing. To do so we establish the following rules. Parallel Postorder:

1. If an inner node (i.e., a non-leaf node) is ready to be processed (i.e., its input files are all in memory) then execute it.

2. Otherwise, select and process the leaf node that is closest (in terms of edges to be traversed) to the previously selected leaf.

These rules do not correspond to the usual formulation of postorder but, when applied using a single processor, they give rise to a postorder traversal of the tree. Due to the concurrent processing of nodes with p processors, the resulting order will not be a perfect postorder, but hopefully a close approximation.

With the careful formulation of the parallel postorder we are able to base the heuristic on an event-based list scheduling algorithm [START_REF] Hwang | Scheduling precedence graphs in systems with interprocessor communication times[END_REF]. Algorithm 3 outlines a generic list scheduling, driven by node finish time events. At each event at least one node has finished so at least one processor is available for processing nodes. Each available processor is given the respective head node of the priority queue.

The order in which nodes are processed in Algorithm 3 is determined by two aspects: i) the node order O given as input; and ii) the ordering established by the priority queue P Q.

For our proposed parallel postorder algorithm, called ParInnerFirst, the priority queue uses the following ordering: 1) inner nodes, ordered by non-increasing depth; 2) leaf nodes as ordered in the input order O. To achieve a parallel postorder, the node ordering O needs to be a sequential postorder. It makes heuristic sense that this postorder is an optimal sequential postorder, so that memory consumption can be minimized [START_REF] Joseph | On the storage requirement in the out-of-core multifrontal method for sparse factorization[END_REF]. f inishT ime(node) Complexity The complexity of ParInnerFirst is that of determining the input order O and that of the list scheduling. Computing the optimal sequential postorder is O(n log n) [START_REF] Joseph | On the storage requirement in the out-of-core multifrontal method for sparse factorization[END_REF]. In the list scheduling algorithm there are O(n) events and n nodes are inserted and retrieved from P Q. An insertion into P Q is O(log n), so the list scheduling complexity is O(n log n). Hence, the total complexity is also O(n log n).

1 1 • • • • • • p -1 • • • • • • k -1 1 • • • • • • p -1 k 2k
In the following we study the memory requirement and makespan of ParInnerFirst.

Memory There is no limit on the required memory compared to the optimal sequential memory M seq . This is derived considering the tree in Figure 4. All output files have size 1 and the execution files have size 0 (f i = 1, n i = 0 for any node i of T ). When optimally processing with p = 1, we process the leaves in a deepest first order. The resulting optimal memory requirement is M seq = p + 1, reached when processing a join node.With p processors all leaves have been processed at the time the first join node (k -1) can be executed. (The longest chain has length 2k.) At that time there are (k -1) • (p -1) + 1 files in memory. When k tends to +∞ the ratio between the memory requirements also tends to +∞.

Makespan ParInnerFirst schedule is a (2 -1 p )-approximation algorithm for makespan minimization because ParInnerFirst is a list scheduling algorithm [START_REF] Graham | Bounds for certain multiprocessing anomalies[END_REF].

Heuristic ParDeepestFirst

The previous heuristic ParInnerFirst is motivated by good memory results for sequential postorder. Going the opposite direction, a heuristic objective can be the minimization of the makespan. For trees, all inner nodes depend on the leaf nodes, so it makes heuristic sense to try to process the deepest nodes first to reduce any possible waiting time. For the parallel processing of the tree, the most meaningful definition of the depth of a node i is the w-weighted length of the path from i to the root of the tree. This path length includes the w i . The deepest node is the first node of the critical path of the tree.

ParDeepestFirst is our proposed algorithm that does this. Due to the general nature of the list scheduling presented in Algorithm 3, we can implement ParDeepestFirst with it. To achieve the deepest first processing the priority queue P Q orders the nodes as follows: 1) deepest nodes first (in terms of w-weighted path length to root); 2) inner nodes before leaf nodes; 3) leaf nodes are ordered in the input order O. Note that the leaf order is only relevant for leaves of the same depth. This order should nevertheless be "reasonable", i.e., it should not alternate between leaves from different parents, which would be bad for the memory consumption. Such an order is again easily achieved when O is a sequential postorder.

Complexity

The complexity is the same as for ParInnerFirst, namely O(n log n). See ParIn-nerFirst's complexity analysis. Now we study the memory requirement and the makespan of ParDeepestFirst.

Memory The required memory of ParDeepestFirst is unbounded compared to the optimal sequential memory M seq . Consider the tree in Figure 5 with many long chains, assuming the Pebble Game model (i.e., f i = 1, n i = 0, and w i = 1 for any node i of T ). The optimal sequential memory requirement is 3.The memory usage of ParDeepestFirst will be proportional to the number of leaves, because they are all at the same depth, the deepest one. As we can build a tree like the one of Figure 5 for any predefined number of chains, the ratio between the memory required by ParDeepestFirst and the optimal one is unbounded.

Makespan ParDeepestFirst schedule is a (2 -1 p )-approximation algorithm for makespan minimization because ParDeepestFirst is, like ParInnerFirst, a list scheduling algorithm [START_REF] Graham | Bounds for certain multiprocessing anomalies[END_REF].

Experimental validation

In this section, we experimentally compare the heuristics proposed in the previous section, and we compare their performance to lower bounds.

Setup

All heuristics have been implemented in C. Special care has been devoted to the implementation to avoid complexity issues. Especially, priority queues have been implemented using binary heap to allow for O(log n) insertion and minimum extraction 2 . Instead of implementing an intricate algorithm with O(n 2 ) complexity such as Liu's algorithm [START_REF] Joseph | An application of generalized tree pebbling to sparse matrix factorization[END_REF] to obtain minimum sequential memory, we have chosen to estimate this minimum memory using the optimal post-order traversal. We have shown in [START_REF] Jacquelin | On optimal tree traversals for sparse matrix factorization[END_REF] that this traversal was optimal in 95.8% of the tested cases, with an average increase of 1% with respect to the optimal. This justifies this choice. Since the reference sequential task-graph traversal serves as a basis for ordering nodes in a number of our heuristics, a large complexity would be prohibitive for this first step.

Data set

The data set contains assembly trees of 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 nonzeros per row at least equal to 2.5, and a number of nonzeros per row at most equal to 5,000,000; and each chosen matrix has the largest number of nonzeros 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 × 10 5 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 nonzeros 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). The memory weights f i of edges are computed as (µ -1) 2 .

The resulting 608 trees contains from 2,000 to 1,000,000 nodes. Their depth ranges from 12 to 70,000 and their maximum degree ranges from 2 to 175,000. Each heuristic is tested on each tree using p = 2, 4, 8, 16, and 32 processors. Then the memory and makespan of the resulting schedules are evaluated by simulating a parallel execution. The comparison of the heuristics is summarized in Table 1. It shows that ParSubtrees and ParSubtreesOptim are the best heuristics for memory minimization. On average they use less than 2.5 times the amount of memory required by the best sequential postorder (whose memory usage is very close to the optimal sequential memory as noted above), when ParInnerFirst and ParDeepestFirst need respectively 3.7 and 5.2 times this amount of memory. ParInnerFirst and ParDeepestFirst perform best for makespan minimization, having makespans very close on average to the best achieved ones. As the scheduling problem, without memory constraints, is already NP-hard, we do not know what the optimal makespan is. We have seen however that ParInnerFirst and ParDeepestFirst are 2-approximation algorithms for the makespan. Furthermore, given the critical path oriented node ordering, we can expect that ParDeepestFirst's makespan is close to optimal. ParInnerFirst outperforms ParInnerFirst for makespan minimization, at the cost of a noticeable increase in memory. ParSubtrees and ParSubtreesOptim may be better trade-offs, since their average deviation from best makespan is under 35%. 7, and 8 provide complete results of the simulations. In each figure, a point represent one scenario (one heuristic on one tree with a given number of processors). To better visualize the distribution, we also plot a "cross" for each heuristic: the center of this cross is the average performance, while the branches represent the scope of each objective between the 10th and the 90th percentile of the distribution.

Results

Heuristic

On Figure 6, we plot the results of all simulations compared to some estimations of the lower bounds. The lower bound for memory minimization is the memory usage of the best sequential postorder, which is known to be very close to the optimal sequential traversal. The lower bound for the makespan is the maximum between the total processing time of the tree divided by the number of processors, and the maximum weighted critical path. This figure exhibits the same trends for average values as noted in Table 1. When the maximum deviation from the lower bound on the makespan is around 4, the ratio of the parallel memory usage to the optimal sequential one can be far larger, as it is larger than 100 for the extreme cases.

In the following figures, the results of the heuristics is normalized by the results of Par-Subtrees (Figure 7) or ParInnerFirst (Figure 8). As expected, ParSubtreesOptim gives results close to those of ParSubtrees, with better makespans but slightly worse memory usage. ParDeepestFirst always use more memory than ParInnerFirst, while having comparable makespans. In most cases, ParInnerFirst gives slightly better makespan than ParSubtrees, but uses more memory.

Conclusion

In this study we have shown that the parallel version of the pebble game on trees is NP-complete, hence stressing the negative impact of the memory constraints on the complexity of the problem. More importantly, we have shown that there does not exist any algorithm that is simultaneously an approximation algorithm for both makespan minimization and peak memory usage minimization when scheduling tree-shaped task graphs. We have thus designed heuristics for this problem. We have assess their performance using real task graphs arising from sparse matrices computation. These simulations showed that two of the heuristics, ParSubtrees and ParSubtreesOptim, only needed, for their parallel executions, and on average, 2.5 times the sequential memory, while achieving makespans that were less than 35% larger than best achieved ones. These heuristics appear thus to deliver interesting trade-offs between memory usage and execution times. In the future work, we will consider designing scheduling algorithms that take as input a cap on the memory usage.

Figure 2 :

 2 Figure 2: Tree used for establishing Theorem 2.

  We first analyse the complexity of SplitSubtrees. Computing the weights W i costs O(n). Each insertion into P Q costs O(log(n)) and calculating C ParSubtrees max (s) in each step costs O(p). Given that there are O(n) steps, SplitSubtrees's complexity is O(n(log(n)+p)). The complexity of the sequential traversal algorithms used in Steps 2 and 3 of ParSubtrees cost at most O(n 2

Figure 3 :

 3 Figure 3: ParSubtrees is at best a p-approximation for the makespan.

Algorithm 3 :1 4 popHead(eventSet) 5 6 P a ← available processors 7 while 9 Assign node to proc 10 eventSet

 34567910 List scheduling(T , p, O) Insert leaves in P Q, ordered as in O 2 eventSet ← {0} /* ascending order */ 3 while eventSet = ∅ do /* event:node finishes */ Insert new ready nodes in P Q /* available parents of nodes completed at event */ P a = ∅ and P Q = ∅ do 8 proc ← popHead(P a ); node ← popHead(P Q) ← eventSet ∪

Figure 4 :

 4 Figure 4: No memory bound for ParInnerFirst.

Figure 5 :

 5 Figure 5: Tree with long chains.

Figure 6 :

 6 Figure 6: Comparison to lower bounds.

Figure 7 :

 7 Figure 7: Comparison to ParSubtrees.

Figures 6 ,

 6 Figures 6,[START_REF] Hu | Parallel sequencing and assembly line problems[END_REF], and 8 provide complete results of the simulations. In each figure, a point represent one scenario (one heuristic on one tree with a given number of processors). To better visualize the distribution, we also plot a "cross" for each heuristic: the center of this cross is the average performance, while the branches represent the scope of each objective between the 10th and the 90th percentile of the distribution.On Figure6, we plot the results of all simulations compared to some estimations of the lower bounds. The lower bound for memory minimization is the memory usage of the best sequential postorder, which is known to be very close to the optimal sequential traversal. The lower bound for the makespan is the maximum between the total processing time of the tree divided by the number of processors, and the maximum weighted critical path. This figure exhibits the same trends for

Figure 8 :

 8 Figure 8: Comparison to ParInnerFirst.

Table 1 :

 1 Proportions of scenarii when heuristics reach best (or close to best) performance, and average deviations from optimal memory and best achieved makespan.

		Best memory	Within 5% of best memory optimal (seq.) memory Avg. deviation from	Best makespan	Within 5% of best makespan from best makespan Avg. deviation
	ParSubtrees	81.1 %	85.2 %	133.0 %	0.2 %	14.2 %	34.7 %
	ParSubtreesOptim	49.9 %	65.6 %	144.8 %	1.1 %	19.1 %	28.5 %
	ParInnerFirst	19.1 %	26.2 %	276.5 %	37.2 %	82.4 %	2.6 %
	ParDeepestFirst	3.0 %	9.6 %	325.8 %	95.7 %	99.9 %	0.0 %

RR n°8082

This is equivalent to say that there is no Zenith or simultaneous approximation.RR n°8082

The code and the data sets are available online at http://graal.ens-lyon.fr/ ~lmarchal/scheduling-trees/ RR n°8082

Acknowledgement

We thank Bora Uçar for his help in creating and managing the data set used in the experiments. We gratefully acknowledge that this work is partially supported by the Marsden Fund Council from Government funding, Grant 9073-3624767, administered by the Royal Society of New Zealand.

RESEARCH CENTRE GRENOBLE -RHÔNE-ALPES


Kalypso Magklara
email: kalypso.magklara@inria.fr

Dimitrios Zorbas
email: dimitrios.zormpas@inria.fr

Tahiry Razafindralambo
email: tahiry.razafindralambo@inria.fr

Node discovery and replacement using mobile robot

A critical problem of wireless sensor networks is the network lifetime, due to the device's limited battery lifetime. The nodes are randomly deployed in the field and the system has no previous knowledge of their position. To tackle this problem we use a mobile robot, that discovers the nodes around it and replaces the active nodes, whose energy is drained, by fully charged inactive nodes. In this paper we propose two localized algorithms, that can run on the robot and that decide, which nodes to replace. We simulate our algorithms and our findings show that all nodes that fail are replaced in a short period of time.

Introduction

Wireless sensor networks is a collection of a large number of small size, low-cost sensing devices organized into a cooperative network. A sensor network except from the nodes that collect data also consists of a sink (base station). The nodes use their communication range to send the collected data to the base station. This can be succeeded using either a multi-hop architecture or a Connected Dominating Set (CDS) network. The nodes can be deployed in various physical environments to monitor events in the area. Sensor networks can be used in various applications, such as military surveillance, environmental monitoring, health-care and agriculture.

One of the fundamental issues to be addressed in wireless sensor networks is the network lifetime. Due to the device's limited battery lifetime nodes fail, the connectivity is lost and coverage is degraded. This problem can be solved by exploiting the redundant nodes that exist in the terrain. Previous papers have proposed a few strategies that calculate when or if failed nodes should be replaced using mobile nodes or robots [START_REF] Parikh | Node-Replacement Policies to Maintain Threshold-Coverage in Wireless Sensor Networks[END_REF], [START_REF] Zorbas | Wireless Sensor Network Redeployment under the Target Coverage Constraint[END_REF] and some other algorithms that do not move any of the nodes but activate the ones needed to cover the environment in question [START_REF] Sakib | Failed node replacement policies for maximising sensor network lifetime[END_REF]. However, most of them assume complete knowledge of the network or the position of redundant/inactive nodes.

We propose two localized solutions, that do not assume any previous knowledge of the network. This means that in an autonomous network, we need to find out the parameters of the nodes, namely the position of the nodes and their energy consumption, in order to replace them with new nodes. We assume that the robot can learn information on the location of the nodes only if they are within its detection range. The advantages of our solutions are summarized in the following:

1. previous knowledge of the network is not required, namely the position of the nodes or the energy they consume, 2. the robot has the capability to explore the area and detect both active and inactive nodes, 3. both solutions are localized and do not demand a central server to process the network's parameters and 4. we implement a realistic energy consumption model both for the nodes [START_REF]Battery energy storage[END_REF] and the robot, for the later specifically we rely on experimental values based on the wifibot [START_REF]Wifibots[END_REF].

The rest of the paper is organized as follows. In Section 2, we present the related work in the fields of node replacement and sensor network redeployment. In Section 3, we provide a description of our model, while in Section 4 we present our solutions. In Section 5 we evaluate our methods and we compare them. Finally, Section 6 concludes the paper.

Related work

Most of the research literature related to node replacement in wireless sensor networks deal with the problem by assuming they have previous knowledge of the nodes' position or the events' position or even the nodes' energy consumption [START_REF] Parikh | Node-Replacement Policies to Maintain Threshold-Coverage in Wireless Sensor Networks[END_REF], [START_REF] Tong | Node Reclamation and Replacement for Long-Lived Sensor Networks[END_REF], [START_REF] Tong | On-Demand Node Reclamation and Replacement for Guaranteed Area Coverage in Long-Lived Sensor Networks[END_REF], [START_REF] Tong | Towards Reliable Scheduling Schemes for Long-lived Replaceable Sensor Networks[END_REF], [START_REF] Falcon | The one-commodity traveling salesman problem with selective pickup and delivery: An ant colony approach[END_REF], [START_REF] Mei | Sensor replacement using mobile robots[END_REF] and others require mobile sensors [START_REF] Zorbas | Wireless Sensor Network Redeployment under the Target Coverage Constraint[END_REF], [START_REF] Li | Mesh-Based Sensor Relocation for Coverage Maintenance in Mobile Sensor Networks[END_REF].

In [START_REF] Parikh | Node-Replacement Policies to Maintain Threshold-Coverage in Wireless Sensor Networks[END_REF] three policies are proposed, each policy determines the importance of each failed node on the coverage and the lifetime of the network, by assigning a weight to each failed node. If the weight is greater than the policy threshold then the node is replaced, otherwise it is ignored. These policies try to maximize the lifetime and simultaneously minimize the redundant resources. Although to evaluate these weights knowledge of the network is needed and a central server to calculate them. In [START_REF] Tong | Node Reclamation and Replacement for Long-Lived Sensor Networks[END_REF] knowledge of the events is needed and also the redundant nodes position is known since they are stored in the sink. The proposed scheme will schedule both the travels of the robot and the duty cycles of the sensors, the goal is to maintain the coverage while minimizing the traveled distance. However it only considers point coverage, so [START_REF] Tong | On-Demand Node Reclamation and Replacement for Guaranteed Area Coverage in Long-Lived Sensor Networks[END_REF] was proposed, that considers area coverage. The nodes are grouped in sets and a staircase-based scheduling model is implemented, a fixed number of backup nodes are also deployed in sets. In this paper the sets are scheduled so that they will not all be exhausted at the same time, so that different sets can be reclaimed and replaced in different time. Still this scheme works under the assumption that active sensors consume energy at the same rate and there is no sensor failure, therefore in [START_REF] Tong | Towards Reliable Scheduling Schemes for Long-lived Replaceable Sensor Networks[END_REF] an improvement of the staircase-cased scheme was proposed and two other schemes, that minimize the hardware cost and the maintenance labor cost. The recharging time of the nodes is considered non-trivial. In [START_REF] Falcon | The one-commodity traveling salesman problem with selective pickup and delivery: An ant colony approach[END_REF] the novel combinatorial problem is introduced, one-commodity traveling salesman problem with selective pickup and delivery and also solved by applying the ant colony optimization meta-heuristic. The inactive nodes report their location to the base station, while the active ones report any adjacent sensing hole. Periodically a robot replaces the failed nodes are replaced by inactive ones. This algorithm tries to minimize the traveled distance and the visited nodes. In [START_REF] Mei | Sensor replacement using mobile robots[END_REF] a small number of robots to replace failed sensors is proposed, the goal is to minimize the motion and the messaging overhead. Three algorithms are studied, a central and two distributed. Every node knows its own location and needs to know which robot is its manager and the location of the manager.

On the other hand, in [START_REF] Zorbas | Wireless Sensor Network Redeployment under the Target Coverage Constraint[END_REF] a localized solution is proposed, however mobile sensors are required for it to work. This algorithm redeploys nodes from targets that are monitored by a large number of sensors and moves them to other targets that are sparsely covered. The nodes initially know only their own and the targets location. Each node covering a target detects and keeps in its memory other neighboring nodes, that cover only the same target. The nodes covering a target can communicate with the nodes covering 2-hop neighboring targets. A head node in its 2-hop neighbor is selected and that one decides which nodes will be moved towards the most sparsely covered neighboring target. Finally in [START_REF] Li | Mesh-Based Sensor Relocation for Coverage Maintenance in Mobile Sensor Networks[END_REF] another localized algorithm is introduced that relocates sensors in a mobile sensor network. It is based on the Distance-Sensitive Node Discovery algorithm. All active nodes send their location to neighboring active nodes but also to redundant nodes. The last send reports to the closest active neighbor. When an active node fails the active neighbors try to find the nearest delegated redundant node.

System Description

Since the devices used in wireless sensor networks have a relatively short transmission range and the terrain size can be several thousands of m 2 , the nodes are not always close to the sink and they cannot send their messages directly. Therefore, we need to configure the network in a way, so that it will be able to have the messages be relayed through intermediate nodes to reach the destination. Furthermore, using such an approach we also have a way to communicate with the robot even when it is far away from the base station. A multi-hop routing mechanism is required with reduced traffic during communication. Hence, we create a static sensor network and ensure connectivity by using a Connected Dominating Set (CDS).

The main parameters for communication in the energy model of the nodes are the following [START_REF] Younis | Energy-aware management for clusterbased sensor networks[END_REF]:

1. the energy consumed by the transmitter α 11 , 2. the energy consumed by the receiver α 12 , 3. the energy for the power amplifier α 2 , 4. the energy consumed when inactive α idle and 5. the energy consumed when sensing α sense All the values are measured per bit. Assuming a 1/d n path loss, the energy consumed is:

E tx = (α 11 + α 2 d n )r, (1)
E rx = α 12 r, (2)
and

E sensing = α sense r, (3)
where E tx is the energy to send r bits, E rx is the energy consumed to receive r bits, d is the distance between the two devices that communicate with each other and n is the path loss exponent, which depends on the distance. The energy consumed by the robot per time unit can be distinguished in two cases. In the first case, when the robot is not moved, the energy consumption is constant. In the second case, when the robot is moved, the energy cost depends on the traveled distance.

E robot = α idle if υ = 0, α mv dst if υ > 0. ( 4
)
where dst is the distance the robot covered, α mv is a constant value and υ is the speed of the robot. We also assume that there is only one available slot on the robot, so it can only carry one node at any time. We assume that the nodes know their own coordinates and send them to the robot when needed, but even if this information is not accurate enough, according to [START_REF] Sheu | Design and implementation of mobile robot for nodes replacement in wireless sensor networks[END_REF] the robot can navigate towards the nodes, then it can pickup and replace them without any knowledge. The received signal strength is used to determine the direction taken by the mobile robot and it is able to move to the destination, using a hop-by-hop approach.

Node Replacement Algorithms

In this section we present the two localized solutions, the Reactive and the Proactive algorithm. In both solutions the robot decides which sensing node to pickup and which one to replace based on information that it receives dynamically from the nodes. The robot does not have any knowledge of the network, but it can detect both active and inactive nodes within its sensing range. On the other hand the nodes know their own coordinates. The algorithms never end but the network at some point runs out of inactive nodes.

Reactive Algorithm

Briefly, in the Reactive algorithm (see Algorithm 1) the nodes send an alarm when their energy falls below a threshold. If there are more than one pending alarms, the robot prioritizes them and decides which one to serve first. The robot stays idle, unless there is a node to serve. The energy threshold of each node depends on the respective consumption rate and the distance between the node and the base station. The messages that the nodes send to the robot contain the following information:

1. the coordinates of the node,

the remaining time until it fails

In more details, the algorithm works in rounds. Each round starts by updating the nodes energy according to the energy model described in Section 3. If an alarm has been sent by a node in the previous step or in a previous round, then the robot checks the priority of each outstanding alarm and decides which one is the most important. The weight of an alarm is based on three variables. More important are the nodes that have already failed, the more the time that have passed the higher the priority. If there are no failed nodes then it checks the values of the other two variables, namely the remaining uptime and the distance from the robot. In this case, priority is given to the node that is closer to the robot and has the smallest remaining time until it fails. Subsequently, there are three main cases.

In the first case where there is an alarm to be served, the robot checks if it has enough energy to move towards the node in question and then go back from that point to the base station plus the energy to travel the maximum pickup range. If the robot has enough energy then it sets the node as a target and moves towards it, otherwise it sets the base station as a target and moves towards the sink in order to recharge its battery. In the second case, the robot has no alarm to handle but has set the base station as a target, so it moves towards that direction. In the third case, the robot has absolutely no target. Here, as explained before, it will stay at the point where it last stopped at. At this point we can distinguish two sub-cases. Either the robot is at the base station or it is anywhere else in the terrain. If the first it does nothing, if the second then it has to check if it has enough energy to reach the base station.

When the robot is moving, it performs several tasks. It starts by detecting all active nodes and keeping the information it receives in its memory. It, also, detects any inactive node within its sensing range and keeps them in its memory as well. Next, for each detected inactive node, the robot computes the distance between itself and the node. After it finds the one that is closest to its current coordinates, if that distance is less than or equal to the predefined maximum pickup range, it sets that node as a temporary target. On the other hand, if the target of the robot is the base station, it is moving towards it. Otherwise if it is already there, it starts recharging. However, if there is a temporary target then it moves towards that direction, but if it is already there it picks up the inactive node. Finally, if an alarm was set as a target then the robot moves towards that node, but again if it is there it will try to replace it. The only reason not to succeed in the delivery is when it does not carry any nodes. At this point, it will check one more time the inactive nodes in its memory and set the one closest to itself as a temporary target, without taking into account the pickup range. The robot can have two targets, the main target which is an active node or sensing node that needs replacement and the temporary that is an inactive node, that will be delivered. A temporary target is defined only if the slot on the robot is empty and it is prioritized over the main target, because we need the inactive once we reach the failed node. checks their energy levels and it decides if it needs to take some action.

As in the Reactive algorithm every node has an energy threshold, which depends on the respective consumption rate and the distance between the node and the base station. The information that the nodes send to the robot once they are detected is the following:

1. the coordinates of the node, 2. the remaining time until it fails, 3. the node's current energy, 4. the node's threshold, and 5. the node's maximum consumption rate More thoroughly, this algorithm likewise works in rounds and starts by updating all nodes' energy levels according to the aforementioned energy model. If no specific target exists or previously chosen coordinates, then a random set of coordinates is calculated. The robot checks if it has enough energy to go to its current destination and back to the base station. If yes it moves towards the coordinates, otherwise it sets the base station as its new target and moves on. The main idea behind the Proactive algorithm is to try to avoid failures, so the robot keeps moving and if it finds an inactive node being close to an active one, and having much more energy than the second, then it will swap them.

When the robot is moving, it performs again various tasks. At the beginning of every move, it detects the active nodes within its range and stores them in its memory. At the same time, it detects the inactive nodes storing them in a different list. It continues by distinguishing four cases. In the first one, the target is the base station and the robot has to move towards it, unless it has reached the sink, in which case it recharges. In the second case, a temporary target exists. If the robot is already at the inactive node then it will pick it up. If not it will move towards it. The third option corresponds to the target being an active node or sensing node. Once again if it has reached the node's coordinates it will try to deliver. If it is not carrying any nodes then as in the Reactive algorithm, the robot will search within its memory for the closest inactive and will go for it. If none of the previous cases are true, then the robot will check the list of detected active nodes and pick the one with the less remaining energy. It will compare that node's remaining energy against its threshold. If it is less than or equal, then the active node will be set as target. After this, it will search in the list of all inactive nodes for the one closest to the robot and will set it as a temporary target. However, if the energy of the active node is greater than its threshold and the robot is not carrying any inactive nodes, then it will search in the list of all inactive nodes but this time it will compare the energy between the chosen active and every detected inactive that is within its pickup range. If the energy of an inactive node is greater or equal to k times the energy of the active node, where k is a static integer, then it will set the active as main target and the inactive in question as temporary target.

written in Python for the two algorithms. The total number of nodes is 200 and we use two different terrain sizes, 20K m 2 and 40K m 2 respectively. We assess the algorithms using six scenarios, by running 30 instances per scenario with random node deployment for each terrain. While the total number of nodes is kept constant, the percentage of the nodes that act as sensing nodes is changed in each scenario and the values used are 20, 40, 60 and 80%. This means that in the first scenario (i.e. 20%) there are 40 sensing nodes out of the 200 nodes and from the remaining 160 some are inactive and some are active. The last ones constitute the CDS, while the sensing nodes constitute the leafs. In the second scenario (i.e. 40%) there are 80 sensing nodes and the remaining 120 are active and inactive and so on. In Figure 1 is depicted an example of a scenario, with 200 nodes in total, while 20 of them are sensing nodes. The base station is plotted as a big square, the sensing nodes as small circles, while the rest of the active nodes are drown as big circles and the inactive nodes as dots. The lines connecting the nodes represent the links between active and/or sensing nodes. The big circle with the base station in its center represents the communication range of the nodes.

The communication range of the nodes is 50m and their sensing range is 10m. The battery of the nodes is initially equal to 20kJ (this is a typical energy capacity of one C-type or two AA-type batteries [START_REF]Battery energy storage[END_REF]). The values for the sensing node's energy model are α 11 = 50nJ/bit when transmitting, α 12 = 100nJ/bit when receiving, α 2 = 100pJ/bit for the power amplifier, α idle = 10nJ/bit when idle and α sense = 100nJ/bit when sensing. Regarding the path loss exponent n, its value ranges between 2 and 4, depending on the distance d. The robot on the other hand, when fully recharged has 388.8kJ and it needs 14400 seconds to fully recharge. The values used are α mv = 24.836J/sec when it moves with υ = 0.9m/sec and α idle = 8.568J/sec1 . Finally, the sensing range of the robot is 50m and the maximum pickup range is 100m.

Simulation Results

In the above mentioned scenarios we assess the percentage of the average time of disconnection. For example in the first scenario, we calculate the average time during which the 40 sensing nodes can not send their data to the base station and then we measure the percentage of that time in the total simulation time. The disconnection can either be caused because the sensing node itself failed or because of the failure of an active node on the path between the sink and that sensing node. We also assess the average time needed by the robot to replace the nodes after they have failed, meaning that after we computed the time that passed from the second an active node or a sensing node failed until the second the robot replaced the given node. After that we calculate the average of all nodes and sensing nodes together and then again the percentage of that time in the total simulation time. Finally, another metric that we evaluate is the energy consumption of the robot during the simulation.

The results that are presented in Table 1 refer to the first set of simulations using the smaller terrain of 20K m 2 . They show that concerning the time each point of interest in the terrain is not covered, the Reactive algorithm delivered better results than the Proactive. The Reactive algorithm takes advantage of the fact that the nodes are close to each other, since the network density is high, and reacts fast in occurring alarms. Therefore, it needs less time to replace a node. The Proactive algorithm performs well in the scenarios where there are few sensing nodes. In this case, the energy consumption in the network is low, and thus the robot has enough time to travel around the terrain and detect many inactive nodes before the nodes start to fail. Moreover, when the number of sensing nodes is too high, both approaches cannot perform as well as before, because there are less inactive nodes available for the replacements and the robot runs fast out of available nodes.

The results that are presented in Table 2 refer to the second set of simulations using the terrain of 40K m 2 . In this case, the network density is low and the distance between the nodes higher, forcing Reactive to travel longer distances when a new alarm appears and, thus, achieving a worse performance. Proactive starts moving from the first second and thus has already discovered a few inactive nodes for the first replacements. In this case, it seems that the trade off between the energy consumption of the robot and the reaction time in In conclusion, we could say that in both terrains -dense and sparse -both algorithms are able to replace all the failed nodes in the field. The Reactive algorithm performs better than the Proactive when the density is low, while Proactive closes the gap in large terrain sizes. We need to stress that Proactive suffers from the long recharging period that occurs more frequently than in Reactive. A representative example is shown in Figure 2. In reference to the robot's energy in the Reactive algorithm the consumption is far slower than that in the Proactive, since in the first case the robot does not need to travel constantly during the simulation and by staying idle it conserves energy.

Conclusion and future work

In this paper we dealt with node replacement in wireless sensor networks in order to prolong the network's lifetime, while trying to minimize the time a sensing node's data is not able to reach the base station, the time it takes for the robot to replace an active node and the energy of the robot. The nodes are randomly deployed and we do not assume any previous knowledge of the network. To tackle this problem we presented two localized algorithms. In both of them the robot mainly receives information from the nodes that are within its range and uses that to it decides if and which node it should serve. The evaluation results showed that the Reactive algorithm performs better in highdensity scenarios, while Proactive closes the gap when the density is low despite the fact that it has to recharge its battery more often. Our future work includes the implementation of a combination of the two algorithms, where the robot evaluates the possible alarm and traveled distance. Moreover, we investigate the use of more than one robot in the field and the use of robots with variable capacity in terms of how many nodes they can carry at the same time.

  If 0 <= d < 10 then n = 2, if 10 <= d < 20 then n = 2.5, if 20 <= d < 30 then n = 3, if 30 <= d < 40 then n = 3.5 and if 40 <= d < 50 then n = 4.

Figure 1 :

 1 Figure 1: Terrain with 200 nodes from which the 10% are sensing nodes

Figure 2 :

 2 Figure 2: Robot Energy Consumption for second set (40K m 2 ), first scenario (20% of sensing nodes)

Table 1 :

 1 Average Disconnection and Replacement Time for the 4 Scenarios with Terrain 20K m 2

	No. of		Reactive			Proactive
	sensing	% of	avg %	avg % of	% of	avg %	avg % of
	nodes	successful	disconnect	replace	successful	disconnect	replace
	40	replacements 100	time 15.5	time 3.45	replacements 100	time 18.55	time 14.05
	80	100	26.31	2.77	100	19.46	11.18
	120	100	11.46	2.89	100	36.01	6.05
	160	100	54.4	11.77	100	69.26	15.89

Table 2 :

 2 Average Disconnection and Replacement Time for the 4 Scenarios with Terrain 40K m 2

	No. of		Reactive			Proactive
	sensing	% of	avg %	avg % of	% of	avg %	avg % of
	nodes	successful	disconnect	replace	successful	disconnect	replace
	40	replacements 100	time 27.93	time 4.20	replacements 100	time 28.81	time 12.33
	80	100	36.41	4.24	100	36.19	6.68
	120	100	57.83	11.88	100	55.17	9.92
	160	100	81.63	41.60	100	85.06	39.37
	case of a failure is better in Proactive algorithm.

These values were experimentally calculated in our lab

5 Evaluation and discussion of the results

In this section, we start by presenting the main parameters of the simulations, we then simulate the proposed algorithms and finally we compute the robot's energy and the sensing nodes' down time. We assume there are no obstacles in the terrain. The base station is located in the middle of the left side of the terrain and it is the starting and recharging point of the robot. We use two programs written in Perl to create the terrain and produce 2-dimensional pictures of the network respectively and we have implemented our own simulation environment