Chams Lahlou
email: chams.lahlou@lip6.fr

Approximation Algorithms for Scheduling with a Limited Number of Communications

We consider the case of a UET tree and an unlimited number of processors. We give a 2-approximation algorithm for minimizing the total number of communications, when there are no communication delays. This algorithm allows us to design a 6-approximation algorithm for the makespan minimization problem when there are unit length communication delays and the processors are interconnected by a simgle bus. Finally, we compare our 6-approximation algorithm with other algorithms by simulations. We show that its mean performance is regular (around 1.25) and we explain, for certain cases, the performance of these algorithms by considering some parameters of the problem.

Introduction

In a multiprocessor system there are usually interprocessor communications during the execution of a parallel program because of data transfers between tasks. It is therefore important to consider scheduling models with realistic communication constraints if one wants to apply results from scheduling theory to practical parallel computation problems. For instance, in order to take into account the duration of a data transfer between two tasks scheduled by different processors, Rayward-Smith [START_REF] Rayward-Smith | UET scheduling with interprocessor communication delays[END_REF] proposed in 1987 a basic model with unit execution time and unit communication delays (UET-UCT for short). Since then, scheduling problems with communication delays have been studied and important results have been obtained (the reader is referred to [START_REF] Ph | Scheduling theory and its applications[END_REF] for a survey on the subject). However, in most of these problems it is supposed that there is no communication contention. Whereas this assumption seems reasonable for some multiprocessor systems (if processors are fully connected for instance), it is not realistic if the communication resources are strongly limited as it is the case for a single bus machine.

In this paper we consider two scheduling models where the communication contention is modelled by a limitation of the number of communications. The parallel program is represented by a precedence graph which is a directed acyclic graph whose vertices represent tasks and arcs represent data dependencies among tasks. If two dependent tasks are not scheduled by the same processor there is an interprocessor communication between their execution for the data transfer. The first model (UET-bound) has been proposed by Afrati, Papadimitriou and Papageorgiou [START_REF] Afrati | Scheduling dags to minimize time and communication[END_REF] on the one hand, and Prastein [START_REF] Prastein | Precedence-constrained scheduling with minimum time and communication[END_REF] on the other hand: Tasks have unit execution time, there are no communication delays and the total number of communications is limited. More recently, Finta and Liu [START_REF] Finta | Complexity of Task graph Scheduling with Fixed Communication Capacity[END_REF] have considered the case of a single bus machine with the UET-UCT assumption. In their model, called UET-UCT-bus, they study the special case where the bus capacity is one, that is there can be at most one communication per unit of time (a similar model for the particular case with two processors has been also proposed by Norman, Pelagatti and Thanish [START_REF] Norman | On the complexity of scheduling with communication delay and contention[END_REF]). They also define two data semantics, that is the kind of data dependencies among the tasks. For the case of independent-data semantics, all data sent by a task are different and hence if a task has to communicate to k tasks there are exactly k communications. On the contrary, for the case of common-data semantics all data sent by a task are identical. So if a task has to send data to k tasks scheduled by a set of k ′ processors only k ′ communications are needed. In [START_REF] Afrati | Scheduling dags to minimize time and communication[END_REF] the independent data semantics is considered and in [START_REF] Prastein | Precedence-constrained scheduling with minimum time and communication[END_REF] the common data semantics. In both cases, it is shown that scheduling a UET tree on an unlimited number of identical processors in at most T unit of time and with at most C communications is an NP-complete problem. In [START_REF] Finta | Complexity of Task graph Scheduling with Fixed Communication Capacity[END_REF] the authors are concerned with the two semantics. They show that finding a minimum length schedule (i.e., with a minimum makespan) of a UET-UCT precedence graph on a single bus machine with capacity one is NP-hard for several cases, particularly if the task graph is a binary tree and the number of processors is infinite.

The purpose of our work is to show that it is possible to design approximation algorithms for the makespan minimization problem in the UET-UCT-bus model by using approximation algorithms for the communications minimization problem in the UET-bound model. Our paper is organized as follows. In Section 2, we establish the connection between the two models from the approximation point of view. In Section 3, we present an algorithm for the problem of minimizing the total number of communications in the UET-bound model, for the special case of a tree and an unlimited number of processors. We then prove that its relative performance is bounded by 2. In Section 4, we first show that under restrictive assumptions it is possible to find in a polynomial time a schedule of an arbitrary precedence graph on a single bus machine. Then we give a 6-approximation algorithm for the makespan minimization problem in the UET-UCT-bus model, again for the special case of a tree and an unlimited number of processors. In Section 5, we compare the previous algorithm with some heuristics by the use of simulations, and Section 6 concludes the paper.

The Connection between UET-bound and UET-UCT-bus

A schedule for a precedence graph G = (V, E), in the model UET-bound, assigns a starting time t i and a unique processor π i to each task i of V such that (1) for every couple of tasks (i, j), if π i = π j then t i = t j (a processor schedules at most one task at at each unit of time), and (2) for each precedence constraint (i, j) ∈ E, t j ≥ t i + 1.

In the model UET-UCT-bus, a schedule for a precedence graph G = (V, E), with the independent-data semantics, on a single bus machine with capacity B assigns a starting time t i and a processor π i to each task i of V such that (1) for every couple of tasks (i, j), if π i = π j then t i = t j , (2) for each precedence constraint (i, j) ∈ E, if π i = π j then t j ≥ t i + 1 else there is a communication task m ij such that t m ij ≥ t i + 1 and t j ≥ t m ij + 1, and (3) at each time t, |{m ij : t m ij = t}| ≤ B (there can be no more than B communications per unit of time). If the common-data semantics is considered, all data sent by a task i are identical, so we have to add the following constraint : (4) if m ij and m ij ′ are two communication tasks such that π i = π j and

π j = π j ′ then m ij = m ij ′ else m ij = m i ′ j ′ .
Let us now consider two optimization problems, MINCOM-BOUND for the UET-bound model and MINTIME-BUS for the UET-UCT-bus model. In the MINCOM-BOUND problem we are asked to find a schedule with makespan at most T units of time (that is max i∈V {t i + 1} ≤ T ) such that the total number of communications is minimum (the definition of communication depends on the choice of the data semantics). Notice that we have l ≤ T < n (where l is the length of a longest path in G, and n = |V | is the number of tasks) since there exists no schedule with makespan less than l, and since, if T ≥ n, we can get an optimum solution by scheduling all tasks on a single processor. Moreover, since l ≤ T , it is always possible to find a solution. In the MINTIME-BUS problem we are asked to find a schedule with minimum makespan.

We now show how the two problems are related. Let Algo 1 be an approximation algorithm for MINCOM-BOUND, c(t) the total number of communications in a solution provided by Algo 1 when the makespan is limited to t, and c * (t) the total number of communications in an optimum solution. Consider the following algorithm Algo 2 for MINTIME-BUS :

1. Let l be the length of a longest path in the precedence graph (in number of tasks). We set t = l ; While c(t) > (t -1)B we set t=t+1;

2. (creation of communication delays) the schedule provided at the end of the previous step is scanned from left to right, and each communication (i, j) at time t is replaced by a communication of one unit length : so task j and all its successors are shifted to the right by one unit of time.

3. (scheduling of communications) the schedule obtained at the end of the previous step is again scanned from left to right. If at a time t there are more than B communications, the extra communications are delayed by one unit of time.

We then have the following result.

Theorem 1 If Algo 1 is an α-approximation algorithm then Algo 2 is a 3αapproximation algorithms.

Proof -Let T * denotes the makespan of an optimum schedule for MINTIME-BUS. We show that Algo 2 provides a schedule with makespan at most 3αT * . Let T 1 , T 2 and T 3 be the makespan of the schedules we get by steps 1, 2 and 3 respectively. Since T 1 may be increased (during step 2) by one time unit at each time t where there are communications, and because there are at most T 1 -1 such instants: T 2 ≤ 2T 1 -1. Again, T 2 may be increased (during step 3) by one time unit each time there are more than B communications. Since there are at most (T 1 -1)B communications (by step 1), T 2 is increased at most T 1 -2 times. Hence we get

T 3 ≤ T 2 + T 1 -2 = 3(T 1 -1).
Let T * 1 be the minimum makespan of an optimum schedule such that c * (T * 1 ) ≤ (T * 1 -1)B. Since c * (T * 1 ) ≤ (T * 1 -1)B, the associated schedule is a valid solution for a relaxed version of MINTIME-BUS (more precisely, when only the total number of communications is limited). Thus we have T * 1 ≤ T * . So we consider two cases:

1. If T 1 = T * 1 : T 1 ≤ T * and T 3 ≤ 3T * . 2. If T 1 > T * 1 : by step 1, (T 1 -2)B < c(T 1 -1) and (by definition of Algo 1 ) c(T 1 -1) ≤ αc * (T 1 -1). If t ≥ t ′ we have c * (t) ≤ c * (t ′ ), so c * (T 1 -1) ≤ c * (T * 1 ). Hence, (T 1 -2)B < αc * (T * 1 ) and, since c * (T * 1 ) ≤ (T * 1 -1)B, we have T 1 ≤ αT * 1 ≤ αT * .
Finally, T 3 ≤ 3T 1 ≤ 3αT * and the theorem is proved.

2

Note that this result does not depend neither on the bus capacity, nor on the data semantics.

Approximation in the UET-bound Model

We are concerned in this Section with the problem MINCOM-BOUND when the precedence graph is a tree (an out-tree, more precisely) and the number of processors is unlimited. This problem is NP-hard for both data semantics since the associated decision problems are NP-complete (see [START_REF] Afrati | Scheduling dags to minimize time and communication[END_REF] and [START_REF] Prastein | Precedence-constrained scheduling with minimum time and communication[END_REF]).

Let A be a tree of height h with n unit execution tasks, and T the makespan limitation (h ≤ T < n). We consider the independent-data semantics, so the cost (the total number of communications) of a schedule is the number of arcs (i, j) such that i and j are not scheduled by the same processor. Since T < n, there is at least one communication in every schedule, and it is possible to define the performance ratio c c * where c * is the cost of a an optimum schedule and c the cost of an approximation algorithm.

We now present an algorithm which approximates the optimum within a ratio of 2 ( c c * ≤ 2).

Presentation of the Algorithm

We first introduce some notations. Let i be a task of A. We denote by A(i) the subtree with root i, by Γ + (i) the set of immediate successors of i, and r i the rank of i in A, that is the length in number of arcs of the path from the root of A to i. The schedule of A provided by the algorithm is denoted by σ and an optimum schedule is denoted by σ * . For a task i of A, π i is the processor that schedules i in σ, t i the starting time of i, and S(i) the set of tasks of A(i) that are scheduled by π i . We define in the same way π * i , t * i and S * (i) for an optimum schedule σ * .

The cost c(i) of a task i in σ is equal to the number of immediate successors of i that are not scheduled by π i . The cost of a subtree A(i), denoted by c(A(i)), is equal to j∈A(i) c(j). The costs c * (i) and c * (A(i)) in σ * are defined in the same way.

It is hard to characterize the structure of an optimum solution, but there are however two easy cases. If A(i) is a subtree of A we have:

1. If r i + |A(i)| ≤ T , A(i) can be scheduled optimally int T -r i unit of
time by executing all tasks of A(i) by the same processor.

2. If all immediate successors j of i are such that each subtree A(j) can be scheduled by only one processor, we get an optimum schedule of A(i) with makespan at most Tr i by scheduling as many subtrees A(j) as possible by the processor π i .

Our algorithm is based on these two special cases:

1. for every i in A :

(a) S(i) = {i}. (b) if r i + |A(i)| ≤ T then xi = 0.
(c) else xi = 1 and t i = r i .

2. The schedule σ i of A(i) is built recursively (starting from the leaves) as follows:

(a) if xi = 0 then we set S(i) = A(i) and all tasks of S(i) are scheduled since time r i by a new processor π i .

(b) else i. if i has no immediate successor j such that xj = 0 then let k be the immediate successor of i such that |S(k)| is minimal ; we set S(i) = S(i) S(k) and π i = π k . ii. else let S 0 = {j : j ∈ Γ + (i) and xj = 0} and l be the list of elements j of S 0 sorted according to the non-decreasing values |S(j)|. Let j ′ be the first element in l.

while r i + |S(i)| + |S(j ′ )| ≤ T do S(i) = S(i) S(j ′ ) and l = l\{j ′ }. Then let S 1 = {j : j ∈ Γ + (i) and xj = 1}. If S 1 = ∅, let k ∈ S 1 a task such that |S(k)| is minimum. If r i + |S(i)| + |S(k)| ≤ T we set S(i) = S(i) S(k).
Finally, we choose a new processor for π i . iii. Tasks of S(i) are then scheduled by π i : if k has to be scheduled by π i , the schedule σ k start at time t i + 1 = r k (t i = r i by step 1.(b)) ; schedules σ j , for j ∈ S 0 and π j = π i , are then scheduled by π i one after the other.

An example of execution for the tree of Figure 1 is represented on Figure 2.

The Performance Guarantee

The proof of the guarantee is based on a classification of the tree nodes. To each i of A is associated a variable x i whose value is defined recursively (starting from the leaves) by: We say that the type of a node i is 0, 1, 2, 3 or 4, according to the value of x i . In the same way, we say that the type of a subtree A(i) is the type of its root i. This classification leads to the following decomposition of the tree: if we delete, in A, all arcs of type (3, 0), (3, 1) and (3, 2) we get a set of subtrees A = {A 0 , . . . , A K }. Since arcs of type [START_REF] Ph | A polynomial algorithm to optimally schedule tasks on a virtual distributed system under tree-like precedence constraints[END_REF][START_REF] Ph | A polynomial algorithm to optimally schedule tasks on a virtual distributed system under tree-like precedence constraints[END_REF], [START_REF] Ph | A polynomial algorithm to optimally schedule tasks on a virtual distributed system under tree-like precedence constraints[END_REF][START_REF] Ph | Scheduling theory and its applications[END_REF], [START_REF] Ph | Scheduling theory and its applications[END_REF][START_REF] Ph | Scheduling theory and its applications[END_REF] and [START_REF] Ph | Scheduling theory and its applications[END_REF][START_REF] Ph | A polynomial algorithm to optimally schedule tasks on a virtual distributed system under tree-like precedence constraints[END_REF] are not deleted, all nodes of type 3 and 4 belong to the same subtree. An example of decomposition is shown on Figure 1.

x i =              0 if r i + |A(i)| ≤ T 1 if r i + |A(i)| > T and ∀j ∈ Γ + (i) : x j = 0 2 if r i + |A(i)| > T and ∀j ∈ Γ + (i) : x j ∈ {1, 2} 3 if r i + |A(i)| > T and ∃ (j, j ′ ) ∈ Γ + (i) × Γ + (i) : x j = 0 and x j ′ = 0 4 else.

General Properties

Let i be a node of A, we denote:

• by Γ + 0 (i) the set of 0-type immediate successors of i.

• by Γ + 0 (i) the set of all other immediate successors of i.

• by S 0 (i) the set of tasks in Γ + 0 (i) scheduled by π i .

• by S * 0 (i) the set of tasks in Γ + 0 (i) scheduled by π * i .

• by s max (i) the maximum number of subtrees A(j), j ∈ Γ + 0 (i), that can be entirely scheduled by π i , that is s max (i) = max S⊆Γ + 0 (i) |{S :

r i + 1 + j∈S |A(j)| ≤ T }. • by b(i) = |Γ + 0 (i)| -|S 0 (i)
| the number of 0-type nodes not scheduled by π i .

A schedule built by the algorithm has the following properties:

Lemma 1 For every i in A : 1. |S 0 (i)| = s max (i). 2. c(i) ≤ b(i) + |Γ + 0 (i)|. 3. c(i) ≥ b(i) + |Γ + 0 (i)| -1.
Proof -1. The algorithm allocates all tasks of a 0-type subtree to the same processor. Since at the end of the step where i is considered, a maximum number of 0-type immediate successors of i are allocated to π i since time r i , the property is true.

2. At the end of the step where i is considered, at least |S 0 (i)| immediate successors of i are allocated to π i , so c(i)

≤ |Γ + (i)|-|S 0 (i)| = |Γ + 0 (i)|+ |Γ + 0 (i)| -|S 0 (i)| = |Γ + 0 (i)| + b(i).
3. If i has at least one non 0-type immediate successor, at most one non 0-type immediate successor of i can be allocated to π i (by step 2.(b).ii). So c(i) is at least equal to

|Γ + 0 (i)| + b(i) -1.
2

We shall use the following bound for the proof of the performance guarantee:

Lemma 2 For i ∈ A : b(i) ≤ c * (i) + j∈Γ + 0 (i) c * (A(j))
Proof -Let k 0 and k ′ 0 be the number of elements in S * 0 (i) such that S * (j) = A(j) and S * (j) = A(j), respectively. Let k 1 be the number of elements in Γ + 0 (i) allocated to

π * i . By definition, c * (i) = |Γ + (i)| -k 0 -k ′ 0 -k 1 . Since each of the k ′ 0 0-type subtrees creates at least one communication, we have j∈Γ + 0 (i) c * (A(j)) ≥ k ′ 0 . So we get c * (i) + j∈Γ + 0 (i) c * (A(j)) ≥ |Γ + (i)| -k 0 -k 1 . Since k 0 ≤ s max (i) = |S 0 (i)| (case 1 of property 1), c * (i)+ j∈Γ + 0 (i) c * (A(j)) ≥ |Γ + (i)|-|S 0 (i)|-k 1 = |Γ + 0 (i)|-|S 0 (i)|+|Γ + 0 (i)|- k 1 . But b(i) = |Γ + 0 (i)| -|S 0 (i)| and k 1 ≤ |Γ + 0 (i)|. It is then true that c * (i) + j∈Γ + 0 (i) c * (A(j)) ≥ b(i). 2
To make easier the understanding of the performance guarantee proof, we first give a proof for a simple case:

Theorem 2 If A is a 2-type tree then c ≤ 2c * .
Proof -Let N 1 and N 2 be the 1-type and 2-type nodes of A, respectively. By definition of the algorithm, the cost of a 0-type subtree is 0 in σ, so c = i∈N 1 ∪N 2 c(i). Since each 2-type node i has exactly one immediate successor allocated to

π i (see step 2.(b).i), i∈N 2 c(i) = i∈N 2 (|Γ + (i)|-1) = (|N 2 |+|N 1 |-1)-N 2 . All immediate successors of a 1-type node i are 0-type nodes, so c(i) = |Γ + 0 (i)| -|S 0 (i)| = b(i), again by definition of the algorithm. Thus we have c = i∈N 1 b(i) + |N 1 | -1, and since 1 ≤ c(i) for i ∈ N 1 we get c = i∈N 1 b(i) + i∈N 1 c(i) -1 ≤ 2 i∈N 1 b(i) -1. Finally, by lemma 2 we have c ≤ 2c * .

2

We use the same idea for the general proof: the total cost c is decomposed according to the type of the nodes of A. However, the proof is much more difficult because some nodes can have a zero cost in σ * but not in σ: for instance, if i is a 3-type node with only one 1-type immediate successor, it is possible that all immediate successors of i are allocated to π * i but there is no proof that they are also allocated to π i . Therefore it is not possible to bound c(i) by an expression with c * (i). For i in N 4 (the set of 4-type For this purpose, we shall prove that in fact for some 3-type node with a zero cost in σ * but not in σ, there exists one successor j (not necessarily immediate) such that: either c * (A(j)) ≥ 1, or c * (j) + k∈Γ + 0 (j)c * (A(k)) ≥ 1, or c * (j) ≥ 1. By this way, it is possible to associate to each 3-type node with a zero cost in σ * but not in σ a successor with a non zero cost.

nodes of A) c(i) = |Γ + (i)| -1,

Properties of 3-type Nodes

We study 3-type nodes according to their cost in σ and σ * . We also consider 4-type nodes because such a node can be an immediate successor or predecessor of a 3-type node.

Let N 3 and N 4 be the sets of 3-type and 4-type nodes of A, respectively. Consider the following partition of N 3 :

• N 1 3 = {i : c * (i) + j∈Γ + 0 (i) c * (A(j)) = 0, c(i) = |Γ + 0 (i)
| and i has at least one 3-type successor}

• N 2 3 = {i : c * (i) + j∈Γ + 0 (i) c * (A(j)) = 0, c(i) = |Γ + 0 (i)
| and i has no 3-type successor}

• N 3 3 = {i : c * (i) + j∈Γ + 0 (i) c * (A(j)) = 0 and c(i) = |Γ + 0 (i)| -1} • N 4 3 = {i : c * (i) + j∈Γ + 0 (i) c * (A(j)) = 1 and c(i) = |Γ + 0 (i)| + 1} • N 5 3 = {i : c * (i) + j∈Γ + 0 (i) c * (A(j)) = 1 and c(i) ≤ |Γ + 0 (i)|} • N 6 3 = {i : c * (i) + j∈Γ + 0 (i) c * (A(j)) ≥ 2}
and the following partition of N 4 : For nodes in N 1 3 ∪ N 2 3 ∪ N 3 3 we have :

• N 1 4 = {i : c * (i) = 0} • N 2 4 = {i : c * (i) ≥ 1} It is indeed a partition: if i ∈ N 1 3 ∪ N 2 3 ∪ N 3 3 then b(i) = 0,
Lemma 3 If i is in an element of N 1 3 ∪ N 2 3 ∪ N 3 3 then : 1. b(i) = c * (i) + j∈Γ + 0 (i) c * (A(j)) 2. j∈S * 0 (i) |S * (j)| = j∈S 0 (i) |S(j)| Proof - 1. It is obvious by lemma 2. 2. Since c * (i) = 0 we have S * 0 (i) = Γ + 0 (i), and since j∈Γ + 0 (i) c * (A(j)) = 0, each of the subtrees A(j) (j ∈ Γ + 0 (i)) is entirely scheduled by π * i . Because b(i) = 0 we have |S 0 (i)| = |Γ + 0 (i)| (see definition of b(i)), that is S 0 (i) = Γ + 0 (i), so S 0 (i) = S * 0 (i). hence j∈S * 0 (i) |S * (j)| = j∈S 0 (i) |S * (j)| = j∈S 0 (i) |S(j)|.

2

To give an analogous result for nodes in N 4 3 we need the following lemma.

Lemma 4 Let i ∈ A and S ′ ⊆ Γ + 0 (i). If |S ′ | ≥ |S 0 (i)| then : j∈S ′ |A(j)| ≥ j∈S 0 (i)

|S(j)|

Proof -Tasks of 0-type subtree A(j) are allocated to the same processor by the algorithm, so |S(j)| = |A(j)|. Since nodes j in S 0 (i) are chosen one after the other according to the non-decreasing values |S(j)|, the lemma is true.

2

Then we have the following.

Lemma 5 If i is an element of N 4 3 then :

1. b(i) = c * (i) + j∈Γ + 0 (i) c * (A(j)) 2. j∈S * 0 (i) |S * (j)| ≥ j∈S 0 (i) |S(j)|
(i) + j∈Γ + 0 (i) c * (A(j)) = 1 the property is true. 2. Since b(i) = 1, s max (i) = |Γ + 0 (i)| -1, that is |S 0 (i)| = |Γ + 0 (i)
| -1 by lemma 1; so there exists a subtree with root in Γ + 0 (i) that is not scheduled by π i . We consider two cases:

(a) if j∈Γ + 0 (i) c * (A(j)) = 0, each of the subtreesA(j), j ∈ Γ + 0 (i),
(i) |A(j)| ≥ j∈S 0 (i) |S(j)|. (b) If j∈Γ + 0 (i) c * (A(j)) = 1
, each of the subtrees A(j), j ∈ Γ + 0 (i), is entirely scheduled by π * j , except one. Let S * ′ 0 (i) be the set of roots of these subtrees. Since c * (i) = 0, all these roots are allocated to

π * i . So we have j∈S * 0 (i) |S * (j)| ≥ j∈S * ′ 0 (i) |S * (j)| = j∈S * ′ 0 (i) |A(j)|. Since |S * ′ 0 (i)| = |S 0 (i)|
we just have to use lemma 4 to prove the result.

3. We have seen that task i has a 0-type immediate successor that is not allocated to π * i . Since either c * (i) = 0 or c * (i) = 1 the lemma is proved.

Characterization of some Successors of 3-type Nodes

We now prove that for some 3-type nodes with cost zero in σ * but not in σ, there exists a successor j such that one of the following inequality is true: We first establish a central property that allows us to bound (in certain cases) the total number of successors of a task i that are allocated to π i .

1. c * (A(j)) ≥ 1 2. c * (j) + k∈Γ + 0 (j)c * (A(k)) ≥ 1 3. c * (j) ≥ 1
Lemma 6 Let l = (j 1 , . . . , j q ) be a path in A without nodes in N 2 ∪ N 3 3 ∪ N 4 3 ∪ N 4 . If i is an immediate successor of j q then:

|S(j 1 )| ≤ r i -r j 1 + |S(i)| + k∈l j∈S 0 (k)

|S(j)|

Proof -Let L be the set of nodes in l ∩ (N 3 3 ∪ N 4 3 ). We study two cases, according to the value α = |L| :

1. α = 0 : (case 1 of Figure 3) the type of nodes in l is 2 or 4. Moreover, these nodes cannot have 0-type immediate successor by definition, so a node i in l has only one immediate successor allocated to π i . We have then |S(j 1 )| ≤ |S(j 2 )| + 1 (if it is not the case, there exists an immediate successor j of j 1 allocated to π j 1 such that |S(j)| > |S(j 2 )|; so j 2 is executed by π j 1 and j is not, which is impossible). By repeating this reasoning we have |S(j

1 )| ≤ |S(i)|+r i -(r i +1). Since k∈l j∈S 0 (k) |S(j)| = 0, we get |S(j 1 )| ≤ r i -r j 1 + |S(i)| + k∈l j∈S 0 (k) |S(j)|.
2. α ≥ 1 : (case 2 of Figure 3) we prove the inequality pby induction. Let j p be the first node of the path l that is in L. By definition of the algorithm, j p has at most one non 0-type imediate successor not allocated to π jp .

If there is one such immediate successor, either j p+1 is allocated to π jp , or there exists j ′ ∈ Γ + (j p ) such that |S(j ′ (a) α = 1 : the type of a node in the path from j p+1 to j q is 4, so

|S(j p+1 )| ≤ r i -r j p+1 + |S(i)|. Thus we have |S(j p )| ≤ 1 + r i - r j p+1 +|S(i)|+ j∈S 0 (jp) |S(j)| = r i -r jp +|S(i)|+ j∈S 0 (jp) |S(j)|.
If j p = j 1 the inequality is proved; else the type of a node in l from j 1 toj p , different from

j p , is 4. So |S(j 1 )| ≤ r jp -r j 1 + |S(j p )| and we get |S(j 1 )| ≤ r i -r j 1 + |S(i)| + j∈S 0 (jp) |S(j)|.
(b) α ≥ 2 : suppose the inequality is true for |L| = α and consider the case |L| = α+1. Let j p ′ be the second node of the path l that is in L, and let L ′ = L\{j p }. By the hypothesis of induction, we have

|S(j p ′ )| ≤ r i -r j p ′ + |S(i)| + k∈L ′ j∈S 0 (k) |S(j)|.
The type of a node in l from j p+1 to j p ′ , different from j p ′ , is 4, so |S(j p+1 )| ≤ r j p ′ -r j p+1 +|S(j p ′ )|. Again, by the hypothesis of induction we get

|S(j p+1 )| ≤ r j p ′ -r j p+1 + r i -r j p ′ + |S(i)| + k∈L ′ j∈S 0 (k) |S(j)|, that is |S(j p+1 )| ≤ r i -r j p+1 + |S(i)| + k∈L ′ j∈S 0 (k) |S(j)|. We have proved that |S(j p )| ≤ 1 + |S(j p+1 )| + j∈S 0 (jp) |S(j)|, so |S(j p )| ≤ 1 + r i -r j p+1 + |S(i)| + k∈L ′ j∈S 0 (k) |S(j)| + j∈S 0 (jp) |S(j)| = r i -r jp + |S(i)| + k∈L j∈S 0 (k) |S(j)|. If j p = j 1 the inequality is true. Else, the type of a node in l from j 1 to j p , different from j p , is 4, so |S(j 1 )| ≤ |S(j p )| + r jp -r j 1 . Finally, we have |S(j 1 )| ≤ r i -r j 1 + |S(i)| + k∈L j∈S 0 (k) |S(j)|.
The lemma is then true since the inequality is true in all cases.

2

To prove that some successors j are such that c * (A(j)) ≥ 1 we need an intermediate result.

Lemma 7 If, for a 0-type or 1-type node

i, |S * (i)| < |S(i)| then c * (A(i)) ≥ b(i) + 1.
Proof -if the type of i is 0 then the lemma is obviously true. If the type of i is 1, suppose we have |S * (i)| < |S(i)|. Let k 0 be the number of immediate successor of i scheduled by π i . Let k * 0 and k * 1 be the number of immediate successors j of i scheduled by π * i such that S(j) = A(j) and S(j) = A(j), respectively. By definition we have c

* (i) = |Γ + (i)| -k * 0 -k * 1 , and because the type of i is 1 we get c * (i) = |Γ + 0 (i)| -k * 0 -k * 1 . Each of the k * 1 subtrees create at least one communication, so c * (A(i)) ≥ c * (i) + k * 1 = |Γ + 0 (i)| -k * 0 . But k * 0 ≤ s max (i) -1 = |S 0 (i)| -1, by the case 1 of property 1 (we have |S * (i)| ≥ |S(i)| if it is not the case, which is impossible). Hence, we conclude that c * (A(i)) ≥ |Γ + 0 (i)| -|S 0 (i)| + 1 = b(i) + 1. 2
So by this result and lemma 6 we obtain:

Lemma 8 Let i be in N 1 3 ∪ N 2 3 . If i has no successor in N 1 3 ∪ N 2 3 ∪ N 5 3 ∪ N 6 3 , there exists a 1-type node i ′ ∈ A(i) such that c * (A(i ′ )) ≥ b(i ′ ) + 1.
Proof -Since i has no successor in N 1 3 ∪N 2 3 ∪N 5 3 ∪N 6 3 , non 0-type and non 1-type successors of i are in N 2 ∪ N 3 3 ∪ N 4 3 ∪ N 4 : each of these successors has at least one of its non 0-type immediate successor scheduled by its processor, in σ and in σ * , by definition of the partition and by lemma 5. So there exists a 1-type successor i ′ of i allocated to π * i . Let l = (i, j 1 , . . . , j q , i ′ ) the path from i to i ′ in A, and let l ′ = (j 1 , . . . , j q ). We have then

|S * (j 1 )| ≥ r i ′ -r j 1 + |S * (i ′ )| + k∈l ′ j∈S * 0 (k) |S * (j)| Since i ∈ N 1 3 ∪ N 2
3 , i has no immediate successor (with type different from 0) allocated to π i , but all of its immediate successors (with type different from 0) are allocated to π * i . So π j 1 = π i and π * j 1 = π * i . In the same way, since i ∈ N 1 3 ∪ N 2 3 we can use case 2 of lemma 3 and we get j∈S * 0

(i) |S * (j)| = j∈S 0 (i) |S(j)|. If |S(j 1 )| ≤ |S * (j 1 )|, we have t j 1 + 1 + |S(j 1 )| + j∈S 0 (i) |S(j)| = r j 1 + 1 + |S(j 1 )| + j∈S * 0 (i) |S * (j)| ≤ t * j 1 + 1 + |S * (j 1 )| + j∈S * 0 (i) |S * (j)| ≤ T
1. π i ′ = π j 1 : we have |S(j 1 )| = r i ′ -r j 1 + |S(i ′ )| + j∈S 0 (j 1 ) |S(j)|. Since |S(j 1 )| > |S * (j 1 )|, we get |S(i ′ )| > |S * (i ′ )| + k∈l ′ j∈S * 0 (k) |S * (j)| - j∈S 0 (j 1 ) |S(j)|, so |S(i ′ )| > |S * (i ′ )|+ j∈S * 0 (j 1 ) |S * (j)|-j∈S 0 (j 1 ) |S(j)|. If j 1 ∈ N 2 ∪ N 4 , j 1 has no 0-type immediate successor, so |S(i ′ )| > |S * (i ′ )|. Else, j ∈ N 3 3 ∪ N 4
3 so we can use lemmas 3 and 5 (case 2) and get

|S(i ′ )| > |S * (i ′ )|.
Then, by lemma 7, the result is proved.

2. π i ′ = π j 1 : if we use lemma 6 with the path l ′ = (j 1 , . . . , j q ), we get

|S(j 1 )| ≤ r i ′ -r j 1 + |S(i ′ )| + k∈l ′ j∈S 0 (k) |S(j)|.
Again, by lemmas 3 and 5, we have

|S(i ′ )| > |S * (i ′ )|.
So the lemma is true. Now, we prove the existence of the other kind of successors. We say that j is an immediate descendant of i, if j ∈ N 1 3 ∪ N 2 3 and there exists no other node that belongs to N 1 3 ∪ N 3 2 in the path from i to j.

Lemma 9 Let i an element of N 1 3 . If i ′ is an immediate descendant of i then there exists a node in the path l from i to i ′ that belongs to N 5 3 ∪N 6 3 ∪N 2 4 .

Proof -Since i ∈ N 1 3 we have c(i) = |Γ + 0 (i)| and b(i) = 0. So S 0 (i) = Γ + 0 (i) and there exists no immediate successor of i (with type different from 0) allocated to π i . Hence,

|S(i)| = 1 + j∈S 0 (i) |S(j)|. Because b(i ′ ) = 0 and c(i ′ ) = |Γ + 0 (i ′ )
| we can use the same reasoning for node i ′ . Thus we get:

|S(i)| + |S(i ′ )| = 2 + j∈S 0 (i) |S(j)| + j∈S 0 (i ′ ) |S(j)| (1) If i ′ is an immediate successor of i then π * i ′ = π * i (since i ∈ N 1 3 , we have c * (i) + j∈Γ + 0 (i) c * (A(j)) = 0). So |S * (i)| ≥ 2 + j∈S * 0 (i) |S * (j)| + j∈S * 0 (i ′ ) |S * (j)|. Because i ′ ∈ N 1 3 ∪ N 2 3
, we can use case 2 of lemma 3 and get |S * (i)| ≥ 2 + j∈S 0 (i) |S(j)| + j∈S 0 (i ′ ) |S(j)|. By (1) we have

|S(i)| + |S(i ′ )| ≤ |S * (i)
| and i ′ should have been scheduled by π i : so there exists a node in the path from i to i ′ different from i and from i ′ .

If l = (i, j 1 , . . . , j q , i ′ ), let l ′ = (j 1 , . . . , j q ). We prove by contradiction that not all nodes in l ′ belong to N 3 3 ∪ N 4 3 ∪ N 1 4 . Suppose that all nodes in l ′ belong to à N 3 3 ∪ N 4 3 ∪ N 1 4 (see figure 4). We have two cases:

1. π * i = π * i ′ : Let j be a node in l. If j belongs to N 1 3 ∪ N 2 3 ∪ N 3 3 ∪ N 1 4
then c * (j) = 0 (by definition) and all immediate successors of j are allocated to π * j . Else j belongs to N 4 3 , and by lemma 5, all immediate successors of j (with type different from 0) are scheduled by π * j . So we have π *

j 1 = π * j 2 = • • • = π * jq = π * i ′ , and since c * (i) = 0 we get π * i = π * j 1 : this case is not possible. 2. π * i = π * i ′ : all nodes in l are scheduled by π * i , so |S * (i)| ≥ 1 + r i ′ -r i + j∈S * 0 (i) |S * (j)| + j∈S * 0 (i ′ ) |S * (j)| + k∈l ′ j∈S * 0 (k) |S * (j)|.
By case 2 of lemmas 3 and 5 we get :

|S * (i)| ≥ 1+r i ′ -r i + j∈S 0 (i) |S(j)|+ j∈S 0 (i ′ ) |S(j)|+ k∈l ′ j∈S 0 (k) |S(j)| (2)
Since all nodes in l ′ belong to à N 3 3 ∪N 4 3 ∪N 1 4 , we can use lemma 6 with the path l ′ and get |S(j

1 )| ≤ r i ′ -r j 1 + |S(i ′ )| + k∈l ′ j∈S 0 (k) |S(j)|. Then, |S(i)| + |S(j 1 )| ≤ 1 + j∈S 0 (i) |S(j)| + r i ′ -r j 1 + |S(i ′ )| + k∈l ′ j∈S 0 (k) |S(j)|. Because r j 1 = r i + 1 we have |S(i)| + |S(j 1 )| ≤ r i ′ -r i + j∈S 0 (i) |S(j)|+|S(i ′ )|+ k∈l ′ j∈S 0 (k) |S(j)|. Since |S(i ′ )| = 1+ j∈S 0 (i ′ ) |S(j)|, we get |S(i)|+|S(j 1 )| ≤ 1+r i ′ -r i + j∈S 0 (i) |S(j)|+ j∈S 0 (i ′ ) |S(j)|+ k∈l ′ j∈S 0 (k) |S(j)|, that is |S(i)|+ |S(j 1 )| ≤ |S * (i)| by inequality 2.
We have then

t i + |S(i)| + |S(j 1 )| = r i + |S(i)| + |S(j 1 )| ≤ t * i + |S(i)| + |S(j 1 )| ≤ t * i + |S * (i)| ≤ T ,
so j 1 should have been scheduled by π i : this case is not possible.

In the two cases, there is a contradiction with the hypothesis that all nodes in l ′ belong to N 3 3 ∪ N 4 3 ∪ N 1 4 : the lemma is then true.

2

Since by definition we have c * (j) ≥ 1 for j ∈ N 2 4 and c * (j)+ k∈Γ + 0 (j) c * (A(k)) ≥ 1 for j ∈ N 5 3 ∪ N 6 3 , the existence of the successors is proved and we can now establish the main result.

Theorem 3

The performance guarantee of the algorithm is 2.

c ≤ 2 i∈N 1 c * (A(i)) + i∈N 2 4 c * (i) + 2 i∈N 4 3 ∪N 5 3 ∪N 6 3 {c * (i) + j∈Γ + 0 (i) c * (A(j))} that is c ≤ 2c * 2 3.2.4
The Tightness of the Bound We show that the bound is asymptotically tight. Suppose we have the 2-type subtree of Figure 5: in a schedule built by the algorithm none of th subtrees with root 1, 2, ..., k can be scheduled by only one processor. Hence we have k -1 communications from the main root and k communications from the roots of the k subtrees, that is c = 2k -1. In an optimum schedule, there are only k communications. So we have c c * → 2 when k tends to the infinity.

T = 1+k(k+1)/2 T-2 T-3 k T-k-1 0 1 2 k 0 1 2 3 k

Approximation and Polynomial Results in the UET-UCT-bus Model

In this Section we are concerned with the case of a single machine bus.

Contrary to the previous model, we have now communications delays.

A Polynomial Case

In [START_REF] Afrati | Scheduling dags to minimize time and communication[END_REF] Afrati, Papadimitriou and Papageorgiou have proposed a polynomial algorithm that schedules a precedence graph with unit execution time on m processors in at most T unit of time and at most C communications, if C is fixed.

We slightly modify their algorithm to solve the following problem.

m-MINTIME-BUS-B-T:

Instance: a UET-UCT precedence graph G with n tasks, single machine bus R with m processors and a capacity B, and an integer T .

Goal: Schedule G on R such that the makespan is at most T .

Theorem 4

The problem m-MINTIME-BUS-B-T can be solved in time

O(D D+1 n 2D+1 log n) where D = B(T -2).
Proof -When T is fixed there are at most B(T -2) communications. So we can use the enumerative method described in [START_REF] Afrati | Scheduling dags to minimize time and communication[END_REF]. Let V be the set of n nodes in G, and E the set of arcs of G. The maximum number of B(T -2)-tuples is bounded by |E| B(T -2) . If we delete each of these B(T -2)-tuples we get at most c = B(T -2) + 1 weakly connected components. Since each of theses components has to be assigned to a single processor, there are min(m, c) possible assignments. Then, each component must be scheduled after the communications of its inner arcs and before its outer arcs, so these arcs define release times and deadlines. It is then possible to schedule each component by solving a single-processor scheduling problem in time O(n log n) (see [START_REF] Lawler | Optimal sequencing of a single machine subject to precedence constraints[END_REF]). Since the total number of these arcs is at most

B c (T -2) c ,

An Approximation Algorithm

Now, we consider the problem MINTIME-BUS in which we are asked to find a minimum makespan schedule of a UET-UCT tree on an infinite number of processors. We suppose that the capacity B is arbitrary. First, we show that a list algorithm can have a very bad performance. We consider the instance shown on Figure 6. Suppose B = 1 and k is even: an optimum schedule if of length 2k + 1. 2 . So the performance ratio is not bounded and can be as bad as we want. Now, if we use the algorithm presented in Section 3 and then algorithm Algo 2 (see page 3) we can get a solution of MINTIME-BUS, and we have the following approximation theorem.

1,1 1,k 2,1 3,1 3,k 2,3 k,1 k,k 1,k 1,1 k,1 k,k 0 1 k k
k 0 1 2 3 k Bus 0 1 2 3 k k+1 k Bus com. of 0 com. of 1 com. of 2 com. of k 1,1 1,k 2,1 2,2 2,k k,2 k,k 1,2 k/2 k/2 k/2

Theorem 5 MINTIME-BUS can be approximated within a ratio of 6.

Proof -this a consequence of theorems 1 and 3.

5 Simulations

We have proposed an approximation algorithm (from now we call it MIN-COM) for the problem MINTIME-BUS and we have analyzed its worst-case to get a performance guarantee. In order to analyze the performance in case of a random instance, we did some simulations on a computer.

The Method

To get an idea of the quality of the performance we compared our algorithm with four heuristics.

The first one is based on solving a relaxed problem. Indeed, if we do not consider the limitation constraint we get the model UET-UCT and the problem is polynomial (see Chrétienne [START_REF] Ph | A polynomial algorithm to optimally schedule tasks on a virtual distributed system under tree-like precedence constraints[END_REF]). So, to get a solution for MINTIME-BUS, we just have to use step 3 of the algorithm Algo 2 to schedule the communications.

The three others are list algorithms. We tested several priority list but three ones seem to have a better performance than the others: (1) nodes sorted according to the non increasing height, (2) nodes sorted according to the non increasing width (the number of leaf of a subtree), and (3) nodes sorted according to the non increasing ratio width/height.

To compare these five algorithms, we computed the ratio ω(H) ω -, where ω(H) is the makespan of a heuristic H and ω -the makespan of a solution by the algorithm of Chrétienne. Since this algorithm solves a relaxed problem, ω -is a lower bound of an optimum makespan ω * for MINTIME-BUS. Hence, we have ω(M ) ω * ≤ ω(M ) ωand, by this way, we approximate the real performance ratio.

To generate the trees we used the algorithm described in [START_REF] Alonso | Random generation of trees[END_REF]. The interesting point of this method is that the trees are randomly and uniformly generated. We considered 20 sizes for the trees (from 10 to 485, with a step equal to 25), and for each size we generated 100 trees (results are stable from this value). To each tree we associated 3 values of the capacity (1, 5 and 10), that is we considered 6000 instances of the problem. We used a 200 MHz Pentium and it took about 2 hours and a half for the tests to be done.

The Results

The aim of the tests was not only to compare our algorithm MINCOM with others, but also to study the correlation between the performance ratio and some parameters of the trees: the number of nodes, the height, the width and the ratio width/height. In the following we present two kind of plots:

(1) the mean performance ratio and (2) the scatter plot (the individual performance ratios) as a function of one of the parameters. By analyzing the scatter plots we can get an idea of a possible correlation and of its significance. Indeed, if the mean performance varies with a parameter (the number of nodes for instance) and if the variability does not depend on the parameter, it is almost sure that there exists a correlation (if the sample has a sufficient number of items, obviously) (see [START_REF] Vessereau | La statistique, Presses Universitaires de France, collection "Que sais-je ?[END_REF] for instance or an other introductory book to statistics).

The Mean Performance as a Function of the Number of Nodes

We first observe that the mean performance ratio of our algorithm does not depend on the bus capacity, and is equal to around 1.25. The mean performance ratio of the four other algorithms degrades with the increase of the number of nodes, except for the case of a capacity 10 where it is hard to conclude. However the performance of these algorithm gets better with the increase of the bus capacity. Finally, we can note that the method based on Chrétienne's algorithm is very efficient for the case of a capacity 10 (the optimum seems to be reached many times). This is not a surprise since if the capacity is great the model UET-UCT-bus is close to the model UET-UCT, in a sense. We only give the results for the width/height parameter because they are the most significants. We can make the same observation as previously, except maybe for the case of a capacity 10 where the performance of all algorithms seems to deteriorate. However, as we shall see in the following, the last performance values are not significant because they are associated to few data. Now, we study the correlation between the performance ratio and the number of nodes of the trees. Only the case of a capacity 1 is presented, since it is the most significant. We first observe that the performance of MINCOM does not depend on the number of nodes. On the contrary, there exists a correlation for the other algorithms, but we can not assert that this correlation is important or that the performance depends only on the size of the trees (the variability is not independent from this parameter).

Scatter Plot as a Function of the Ratio Width/Height

We are now concerned with the correlation between the performance ratio and the parameter width/height. We can make the following observations:

1. The performance of MINCOM does not seem to depend on the ratio width/height.

2. If capacity is 1, the correlation is linear and important for the four other algorithms.

3. If the capacity is 5, there exists a threshold from which there is a correlation. This correlation is important, except for the list algorithm according to the height.

4. If the capacity is 10, it seems that there is no correlation, except may be for the list algorithm according to the width. Now, we compare the heuristics according to the number of processors they use. First, we have to mention that this number does not depend on the capacity when the method based on Chrétienne's algorithm is used. Indeed, the number of processors required in that case is exactly the one found by Chrétienne's algorithm since we only schedule the communications of the relaxed solution to get a feasible solution (remember that the allocation of tasks to the processors remains the same during that step). The first observation to make is that this number increase with the number of nodes, whatever the heuristic we consider. Next, whereas the method based on Chrétienne's algorithm requires from 2 or 3 processors (for a tree with 10 nodes) to around 210 (for a tree with 485 nodes) whatever the capacity is, our algorithm never uses more than around 25 processors and the three list algorithm never use more than around 5, 15 and 20 processors in case of a capacity equal to 1, 5 and 10 respectively. We have shown that it is possible to design approximation algorithms with performance guarantee for two problems where the number of communications is limited. Moreover, We have proved that the two problem are related from the approximation point of view. In this way, we have used the approximation of a the former problem to approximate the latter.

For the first problem (MINCOM-BOUND) we have proposed a 2-approximation algorithm. This algorithm has been proved for the case of an outtree with the independent-data semantics, but is still valid for an in-tree (the two semantics are in this case the same) and for an in-tree with the independent-data semantics, since a node has at most only one immediate successor. However, in case of an out-tree with the common-data semantics, the algorithm is no longer valid, and the approximation seems harder. For instance, if we consider a 1-type tree with several 0-type subtrees the problem of minimizing the number of communications reduces to the BINPACKING problem, which is NP-hard (recall that the same problem is polynomial in case of the independent-data semantics).

For the second problem (MINTIME-BUS) we have proposed a 6-approximation algorithm. We do not know, contrary to the previous algorithm, if the bound is tight. However we have compared its performance with that of other possible heuristics, by randomly generating an important number of instances. These tests show that the performance ratio of our algorithm is stable around the value 1.25 while the worst case ratio is at most equal to 6. They also show that 1) our algorithm is the most efficient if the capacity is small, 2) list algorithms are the most interesting if we want to use a number of processors as small as possible and 3) the method based on Chrétienne's algorithm is the most efficient if the capacity is great, but it requires a great number of processors.

The approximation of more general problems (arbitrary precedence graph, arbitrary number of processors, ...) seems to be much harder. However, we could test some heuristics. For example, it would be interesting to compare list algorithm with a heuristic based on the relaxation of the problem, as we have done. For the case of scheduling an arbitrary precedence graph on an unlimited number of processors, it is possible to use the 4 3 -approximation of König and Munier [START_REF] König | A heuristic for a scheduling problem with communication delays[END_REF] for the relaxed problem in the model UET-UCT.

To conclude, we think that the model of Afrati, Papadimitriou, Papageorgiou and Prastein could be a basic model for scheduling problems with a limited number of communications. Despite the difficulty of proving performance guarantee for general problems, we think that their model could be useful for designing good heuristics.

Figure 1 :

 1 Figure 1: Decomposition of a tree

Figure 2 :

 2 Figure 2: An example of execution

  by definition of the algorithm. The value |N 4 | can be suppressed in the expression of c, as it is the case for the value |N 2 | in the proof of the previous theorem. On the contrary, for a task i in N 3 (the set of 3-type nodes of A) we can not use this trick, and the bound of the cost c looks like |N 3 | + • • • . If we want to get a guarantee we have to bound the value |N 3 |.

  and thus either c(i) = |Γ + 0 (i)| or c(i) = |Γ + 0 (i)| -1 (by cases 2 and 3 of lemma 1); if i ∈ N 4 3 ∪ N 5 3 then b(i) ≤ 1, and we have either c(i) = |Γ + 0 (i)| + 1 or c(i) ≤ |Γ + 0 (i)| (by the same lemma). We now express more precisely the value of the bound b(i) of lemma 2 for certain nodes in N 3 .

3 . 1 .

 31 All non 0-type immediate successors of i are scheduled by π * i . unlimited -If b(i) = 0 then c(i) ≤ |Γ + 0 (i)| by case 2 of lemma 1, which is impossible. So we have b(i) ≥ 1, and since c *

2

 2

Figure 3 :

 3 Figure 3: Case 1 and 2 of lemma 6

  )| ≤ |S(j p+1 )|. So we get, in the former case |S(j p )| = 1 + |S(j p+1 )| + j∈S 0 (jp) |S(j)| and in the latter case |S(j p )| = 1 + |S(j ′ )| + j∈S 0 (jp) |S(j)| ≤ 1 + |S(j p+1 )| + j∈S 0 (jp) |S(j)|. If there is no such immediate successor, |S(j p )| = 1+ j∈S 0 (jp) |S(j)| ≤ 1 + |S(j p+1 )| + j∈S 0 (jp) |S(j)|. In all cases we have |S(j p )| ≤ 1 + |S(j p+1 )| + j∈S 0 (jp) |S(j)|.

and j 1

 1 should have been allocated to π i (by definition of the algorithm). So we have |S(j 1 )| > |S * (j 1 )| Consider now the two following cases:

  ........... 0 0 .......... 0 0 ........ 0 must be on the same processor must be on the same processor must be on the same processor must be on the same processor

Figure 4 :

 4 Figure 4: a contradictory argument for lemma 9

Figure 5 :

 5 Figure 5: An instance for which the bound is tight

  we can examine all possible solution in time O(|E| B(T -2) min(m, c)B c (T -2) c n log n). By bounding |E| by n 2 , and min(m, c + 1) by n, we get a time O(B(T -2) B(T -2)+1 n 2B(T -2)+1 log n).

2

 2

Figure 6 :

 6 Figure 6: A bad instance for a list algorithm

  Figure 7: Capacity 1

Figure 9 : 10 5. 2 . 2

 91022 Figure 9: Capacity 10

Figure 12: Capacity 10 5. 2 . 3

 1023 Figure 12: Capacity 10

Figure

  Figure 13: MINCOM (capacity 1)

Figure 14 :

 14 Figure 14: Heuristic based on Chrétienne's algorithm (capacity 1)

Figure 15 :

 15 Figure 15: List algorithm according to the ratio width height of the tree (capacity 1)

Figure 16 :

 16 Figure 16: List Algorithm according to the width of the tree (capacity 1)

Figure 17 :

 17 Figure 17: List algorithm according to the height of the tree (capacity 1)

Figure

  Figure 18: MINCOM (capacity 1)

Figure

  Figure 19: MINCOM (capacity 5)

FigureFigure 21 :Figure 22 :Figure 23 :Figure 24 :Figure 25 :Figure 26 :Figure 27 :Figure 28 :Figure 29 :Figure 30 :Figure 31 :Figure 32 :

 212223242526272829303132 Figure 20: MINCOM (capacity 10)

  Figure 33: Capacity 1

  If all of these subtrees are scheduled by π * i we get s max (i) = |Γ + 0 (i)|, which is impossible. So there exists at least one of them that is not allocated to π *

	is
	entirely scheduled by π * j .
	So we have j∈S * 0 (i) |S

* (j)| = j∈S * 0 (i) |A(j)|. i , and since c * (i) = 1, exactly one of them is not scheduled by π * i . Now, because |S * 0 (i)| = |S 0 (i)| we can use lemma 4 and get j∈S * 0

Acknowledgment

I wish to express my sincere thanks to Prof. Claire Hanen for her careful review and for many improvements in the proof of theorem 3.

Proof -Let N be the set of nodes in A. We denote by N i , i ∈ {0, 1, 2, 3, 4} the set of i-type nodes, by R 1 and R 2 (respectively) the sets of roots of 1-type and 2-type subtrees.

We have:

By definition of the partition of N 3 :

, we have:

Now, let us consider an immediate successor j of a node in N 3 ∪ N 4 . By definition of the classification, either j belongs to N 3 ∪ N 4 , or is the root of a 1-type (or 2-type) subtree (see Figure 1). So we have :

Consider now the nodes in N 1 3 . Let N 1 ′ 3 be the set of nodes in N 1 3 that have, either an immediate descendant, or no immediate descendant but one successor in N 5 3

3 ) we get

| and by (3) we have

For a node i in

By definition, nodes in N 1 ′′ 3 have neither immediate descendant, nor successor in N 5 3 ∪ N 6 3 . In other words, no successor of a node in

3 . So we can use lemma 8. It also true for nodes in N 2 3 since the have no successor in N 3 by definition. So it is possible to associate to each node in

cannot have, by definition, a successor that belongs to N 1 ′′ 3 ∪ N 2 3 , all these subtrees are different and we get

The type of an immediate successor of a 2-type node is 1 or 2, by definition of the classification. so it cannot belong to R 1 or R 2 (the immediate predecessor of a node in R 1 ∪ R 2 is either a 3-type node or a 4-type node). Hence we have

(5) Since the cost of a 0-type node is 0 in σ, we have c = i∈N 1 ∪N 2 c(i) + i∈N 3 ∪N 4 c(i), that is by adding (4) to ( 5)

By definition, we have:

3 . Thus we have:


J P Colombier

P Combis

F Bonneau

R Le Harzic

E Audouard

Hydrodynamic simulations of metal ablation by femtosecond laser irradiation

Keywords: numbers: 61.80.Az, 72.15.Cz, 79.20.Ap

Ablation of Cu and Al targets has been performed with 170 fs laser pulses in the intensity range of 10 12 -10 14 W/cm 2 . We compare the measured removal depth with 1D hydrodynamic simulations. The electron-ion temperature decoupling is taken into account using the standard two-temperature model. The influence of the early heat transfer by electronic thermal conduction on hydrodynamic material expansion and mechanical behavior is investigated. A good agreement between experimental and numerical matter ablation rates shows the importance of including solid-to-vapor evolution of the metal in the current modeling of the laser matter interaction.

I. INTRODUCTION

Ultrafast phenomena driven by subpicosecond laser pulses have been the subject of thorough investigation for many years in order to explain the ablation of solid materials 1,2,3,4 . As opposed to the laser-dielectric interaction where thermal and athermal ablation regimes probably takes place 5,6,7 , the laser-metal interaction is mainly governed by the thermal ablation one 6,8 . The laser energy is absorbed by the free electrons first. The pulse duration being shorter than the electron-phonon relaxation time (τ e-ph ∼ 10 -12 s), electrons and ions subsystems must be considered separately. The "two-temperature model" (TTM) describes the thermal transport of energy by the electrons and the energy transfer from the electrons to the lattice 9 .

Numerous theoretical and experimental previous works have been devoted to the study of the matter ablation with a single laser pulse. Experimental irradiation conditions in current applications are largely investigated to optimize the ablation rate: pulse duration 10 , fluence 11 and background gas 12,13 . However, a complete view including all the relevant physical mechanisms is still lacking. To get a better understanding of the ablation process and to extend the results into situations not covered by the experiments, two kinds of investigations are put at work : (i) a complete identification of the various physical mechanisms responsible for the material removal from the surface, (ii) an evaluation of the impact of these various processes on the amount of ablated matter. In the works previously addressed, few calculations are able to provide a direct comparison with experiments. Most of them are focused on thermal transport and a more detailed description of the physical processes occuring in the material has to be incorporated to really describe the whole ablation process. Among these, works based on hydrodynamic modeling 1,2,14,[START_REF] Afanasiev | Conference on Contr. Fusion and Plasma Phys. Funchal, ECA[END_REF] have been recently associated to the TTM to describe ablation process. To overcome the drawbacks of a material fluid treatment, a mechanical extension of the TTM has been proposed to model the ultrafast thermomelasticity behavior of a metal film [START_REF] Chen | [END_REF] . Works based on molecular dynamics allow to access to the influence of the ultrafast energy deposition on the thermal and mechanical evolution properties of the material 17,18 . With a different approach, other authors have performed a microscopic analysis of the mechanisms of ultrashort pulse laser melting by means of a hybrid molecular-dynamic and fluid modelisation 3,4 .

From all these investigations, it appears that none of these effects may be neglegted to reproduce the features of the damage resulting from an ultrashort laser irradiation. Moreover, there is a lack of investigations which combine experimental and theoretical results so that current models are still questionnable. In the present simulations, the TTM provides energy deposition in an expanding material intimately correlated with the processes governing the ablation in the ultrashort pulse case, which is a specificity of our hydrodynamic approach. Simulation results give useful insight into the presented experiment data.

Transport properties of electrons are not very well understood in nonequilibrium electron-ion systems. However, the comprehension of these phenomena in the context of ultrafast interaction is essential not only for fundamental purposes but also for micromachining applications. A precise description of the effect of the electronic temperature on the absorption seems to be still unsettled 19,20,21 , and it has not been taken into account in the presented calculations. Nevertheless, the model employed in this work uses a large set of current available data.

Obviously, numerical calculations are always requiring additional information such as electron-phonon or electron-electron relaxation times, which may be extracted, from experimental data 22,23 . Reciprocally, comparison between simulations and experiments allows to validate physical data introduced into the theoretical models. For instance, we shall see in the following that the measure of the pressure variation with time inside the material would be very informative. These data, however, are difficult to measure with a high accuracy. By contrast, experimental measure of laser ablation rate seems to be easier to be obtained and compared with numerical simulations.

In this article, numerical and experimental results on ablated matter are reported. For this purpose, the TTM is inserted into a hydrodynamic code in order to describe the material removal. First we detail the physical processes which are taken into account in our computations within the framework of hydrodynamical modeling. Then, the effects caused by relaxation processes on the evolution of shock waves are examined. We next present the experiments which have been performed to obtain ablation depth measurements as a function of the laser fluence. Finally, our discussions are based on results of numerical simulations on Cu and Al samples compared with specific experimental measurements.

II. THEORETICAL MODEL

To represent numerically the interaction between the laser and the metallic target, we used a 1D Lagrangian hydrodynamic code 24 . Solving the Helmholtz wave equation permitted us to determine the electromagnetic field through the region illuminated by the laser. The deposited energy is then deduced using the Joule-Lenz law. A precise result for the absorption from an arbitrary medium can be obtained from the direct solution of the equation for the electromagnetic field. Let us consider a planar wave propagating along z axis. We write the following Helmholtz equation for the complex amplitude of the electric field E z with frequency ω :

∆E z -∇∇E z + 1 + i 4π ω σ (T, ρ) ω 2 c 2 E z = 0 (1)
where σ(T, ρ) is the complex conductivity and c is the light speed. The function σ is calculated as a function of the density ρ(z) and the temperature T (z). The relative permittivity of the medium is supposed to be equal to the unity in the case of a metal target. These simulations need accurate data such as transport coefficients in solids, liquids, vapors and dense or diluted plasmas, specially refractive indices [START_REF] Palik | Handbook of Optical Constants of Solids[END_REF] , electric and thermal conductivities [START_REF] Ebeling | Polishchuk: Thermophysical Properties of Hot Dense Plasmas[END_REF] , and mechanical properties such as material strength. The evolution of the irradiated target is governed by the fluid hydrodynamic and heat diffusion equations connected with a multi-phase equation of state (EOS). Thermodynamic functions that realistically describe characteristics of metal properties in various parts of phase diagram are needed. A such set of different metal EOS is generated by means of a numerical tool developped by the authors of the reference [START_REF] Bushman | [END_REF] . As an illustration of the EOS used, Fig. 1 displays isobars in the phase diagram temperature-specific energy of the copper for a wide range of pressure. Such data reveal the dependence on the thermodynamic properties of the melting and vaporisation processes.

The mechanical propagation of shock waves and fracture are also simulated. Elastoplasticity is described by a strain rate independent model (relevant to high strain rate conditions at high pressure, typically beyond 10 GPa) which accounts for pressure, temperature and strain dependent yield strength and shear modulus 28 . Laser induced stresses are the combination of the hydrostatic pressure and the response to the shearing deformation. In the temperature range of interest here, the effect of radiative energy transport on the hydrodynamic motion is negligible. Hence we ignore energy transport by radiation when solving the hydrodynamic equations. Ultrashort laser irradiation and the associated ionic and electronic temperature decoupling require to introduce specific electronic parameters. We assume that free electrons form a thermal distribution during the interaction and use the Fermi-Dirac distribution to determine the electron properties (energy, pressure and heat capacity) as a function of the density and the temperature [START_REF] Ashcroft | Solid State Physics[END_REF] . The evanescent electromagnetic wave is absorbed by the electrons. In our range of intensity, they are quickly heated at a temperature of few eV. During and after the pulse, the energy diffuses among the electrons and is then transferred to the lattice. Classical heat diffusion plays a significant role as soon as a thermal gradient occurs in the material. Diffusion processes are described by the following equations :

ρ C e ∂T e ∂t = ∇ (K e ∇T e ) -γ(T e -T i ) + S (2)
ρ C i ∂T i ∂t = ∇ (K i ∇T i ) + γ(T e -T i ) (3)
where T , C and K are the temperature, the specific heat and the thermal conductivity respectively. Indices "e" and "i" stand for electron and ion species. ρ is the mass density. γ characterizes the rate of energy exchange between the two subsystems and S is the space and time dependent laser source term determined by the Joule-Lenz law. Introduction of the TTM in a hydro-code allows us to take into account the density dependence of both specific heats and conductivities. C e (T e , ρ) is calculated with the Fermi model using ρ dependent chemical potentials [START_REF] Ashcroft | Solid State Physics[END_REF] . The electron thermal conductivity K e is commonly expressed in the form [START_REF] Anisimov | Proc. SPIE[END_REF] :

K e = α (θ 2 e + 0.16) 5/4 (θ 2 e + 0.44) (θ 2 e + 0.092) 1/2 (θ 2 e + βθ i ) θ e (4)
where θ e and θ i are electron and ion temperature normalized to the Fermi temperature (θ e = T e /T F , θ i = T i /T F ) and α, β are material dependent parameters 3,[START_REF] Wang | [END_REF] . The linear variation of coupling term with (T e -T i ) is classic in TTM : we have taken γ = γ 0 as 3 × 10 16 WK -1 m -3 for copper 22 , and 3 × 10 17 WK -1 m -3 for aluminum 20 . It must be noticed that the values of K e and γ are subject to considerable uncertainty in literature 3 . To accurately describe the ultrafast response, we incorporate electronic pressure into the set of hydrodynamic equations. The system of equations for electron and ion subsystems can be written in the Lagrangian form :

       ∂ε e ∂t = -p e ∂V ∂t , ∂ε i ∂t = -p i ∂V ∂t ∂u ∂t = - ∂ ∂m (p e + p i ), ∂V ∂t = ∂u ∂m ( 5
)
where u is the fluid velocity, m the mass and V the specific volume. p e , ε e , p i , ε i are the pressure and the specific energy of electrons and ions. Equations ( 2) to ( 5) connected with a multiphase equation of state (EOS) [START_REF] Bushman | [END_REF] constitute a self-consistent description of the matter evolution. However, the pressure p(T e = T i ) provided by this EOS is the sum of the electronic and ionic pressure at the equilibrium and has to be replaced by the sum of these two contributions out of equilibrium. The electronic pressure is independently determined by means of the standard fermion gas model. As a consequence, the total pressure used in the above calculations is determined as p(T e = T i ) = p e (T e ) -p e (T i ) + p i (T i ).

III. SIMULATIONS AND ANALYSIS

To start with, the interaction of a 10 J/cm 2 , 170 fs FWHM gaussian pulse at 800 nm wavelength with a copper target is investigated. Fig. 2 shows the space-time evolution of the induced stress. The metal surface is heated to a maximum of 2950 K, 30 ps after the irradiation. At this time, the free surface expands in a liquid state with a velocity of 400 ms -1 . Due to the electron heating, an electronic compression wave appears at the end of the laser pulse. The electron-ion energy exchange results in a significant increase in the ionic pressure, which propagates inside the metal. Behind the shock, tensile stress occurs associated with very high strain rate around 10 9 s -1 .

In order to study the sensitivity of the above results with respect to the physical parameters, we compare in Fig. 3 the time variation of the computed stress at 1 µm depth under standard conditions (γ = γ 0 and K e = K eo ) with those obtained with an increased coupling factor or electronic conductivity. In the first hundred picoseconds, the stress growth is directly related to the heating depth. The increased coupling factor leads to a steeper thermal gradient and a lower temperature at 1 µm depth compared to the other situations. The resulting stress is therefore lower in this case. The peak of the shock wave, propagating from the surface, reaches the 1 µm depth at 200 ps. Increasing the coupling factor accelerates the energy transfer from the electrons to the lattice and results in higher compression. Inversely, an enhanced electronic conductivity spreads the energy spatial profile and yields reduced stresses. It must be noticed that in the three cases, the compression is followed by a high tensile stress greater than the characteristic tensile strength of the material. Nevertheless, the loading in tension is not long enough (150 ps) to induce a fracture in the medium 32,33 . The shock duration and intensity provide a good signature of the balance between the electronic diffusion and the electron-ion coupling. Further improvements will be discussed in the following.

To obtain local information on the energy transfer induced by a femtosecond laser irradiation, a highresolution time measurement of the stress reaching the rear side of a thin sample could be achieved 34,35 . Such experimental records could be directly compared with our simulations which would led us to refine the (γ, K e ) physical values accordingly. To validate the computation, we performed ablation measurements and compared them to the current simulations using standard values of (γ, K e ) for aluminum and copper samples.

IV. EXPERIMENT DETAILS

Ultrashort laser pulses are generated by an amplified all solid-state Ti:Saphire laser chain. Low energy pulses are extracted from a mode-locked oscillator (1.6 nJ/pulse, 80 MHz, 800 nm, 120 fs). The pulses are then injected into an amplifying chain including : an optical pulse stretcher, a regenerative amplifier associated with a two-pass amplifier using a 20 W Nd:YLF laser as pumping source, and a pulse compressor. Linearly polarized pulses with wavelength centered around 800 nm, an energy of 1.5 mJ at 1 kHz repetition rate and typical duration of 170 fs were delivered. The samples are mounted on a three-motorized-axes system with 0.5 µm accuracy. Experiments are performed in the image plane of an aperture placed before the objective. The resulting spatial laser profile on sample is "top hat" so that borders and spurious conical drilling effects are reduced. Focusing objectives of 25 mm or 10 mm focal lengths to obtain fluences in a range of 0.5 to 35 J/cm 2 with the same beam size, 16 µm in diameter, in the image plane.

For ablation depth measurements, grooves are machined by moving the sample 36 . The sample speed is adapted such that each point on the groove axis undergoes 8 consecutive irradiations at each target pass. The number of times the sample passes in front of the fixed beam can be adjusted. Fig. 4 shows a scanning electron microscopy (SEM) picture of the machined grooves on copper for 2, 4, 6, 8 and 10 passes. The groove depth FIG. 4: SEM picture of machined-groove profiles, from 2 to 10 passes, on a copper sample.

is measured using an optical profilometer with a 10 nm depth resolution. The ablation rates for each groove are deduced taking into account the sample speed, the repetition rate of the laser, the beam size and the number of passes. For each energy density, an averaged ablation rate is determined and the number of passes has been chosen to obtain reproducible results. From these experiments on copper and aluminum targets, we evaluate, for different fluences, an ablation depth averaged over a few tens of laser shots. The theoretical ablation depth is deduced from 1D numerical simulations using a criterion discussed hereafter.

V. RESULTS AND DISCUSSION

At moderate fluence, the propagation of the shock wave induced by the energy deposition on the lattice causes the surface expansion at very high speed and significant non-uniform strain rates. Simultaneously, the surface of the target is melted or vaporized as soon as the conditions of temperature and density required are fulfilled. High strain rates can turn the liquid region into an ensemble of droplets and ablation follows. This process is called the homogeneous nucleation 37 . Unfortunately, quantitative values on the formation and ejection of liquid droplets are difficult to access because the interfacial solid-liquid microscopic properties of the nucleation centers are not accurately known. Nevertheless, in our simulation we can consider that the liquid layer accelerated outside the target corresponds to the ablated matter. Large values of strain rates (10 9 s -1 ) indeed signal that droplet formation may occur and are sufficient to produce ablation. At higher fluence, the surface is strongly vaporized. The gas expands near the free surface and compresses the internal matter. The vaporized part of the target added to the fraction of the above-defined liquid layer constitute the calculated ablated matter. Experimental results on ablation of copper and aluminum are compared with the numerical estimates in Fig. 5 and6.

Sharp numerical ablation thresholds are visible at 3 and 0.5 J/cm 2 for Cu and Al targets respectively. At high fluence, the ablation saturates for both materials. This saturation occurs mainly for two reasons. Vaporization and subsequent gas expansion consume energy that does not contribute to the ablation process. Moreover, the liquid layer confinement increases as far as the gas expands and limits the liquid removal.

As defined by Feit et al 7 , a specific removal depth, i.e., depth removed per unit incident fluence could be a relevant parameter to estimate the ablation efficiency at a fixed pulse duration. Calculations of this quantity is carried out as a function of the laser fluence. Dashed curve presented in Fig. 6 indicate a maximum value of 0.5 J/cm 2 in the aluminum case. The curve is smoother for copper in Fig. 5 and the maximum specific removal depth is reached at a fluence around 5 J/cm 2 . This point corresponds to the occurence of a critical behavior which confirms a change in the hydrodynamic behavior. While the thickness of the liquid layer grows with the incident energy, the specific removal depth rises. Afterwards, when the gas expansion starts, a growing part of the laser energy is transformed in kinetic energy and the specific removal depth drops. This suggests that an optimum material removal exists and refers to the situation when the surface vaporisation is limited. It appears that this quantity is relevant for material processing which can be optimized by operating at this optimal fluence. At low fluence, a noticeable discrepancy arises between the experimental and numerical results. The calculated ablated matter for a copper target is below the experimental results, while for an aluminum target, numerical results are above. We suspect that electron transport properties should be further improved. It has been shown that a significant decrease in the electrical conduc-tivity may take place as a result of the electronic temperature increase 19 , which our model discards. However, the experimental measurements and the theoretical calculations come to a reasonable agreement at higher fluence.

As it has been shown by Fisher et al 20 , in the vicinity of a 800 nm wavelength, the interband absorption occuring in an aluminum target decreases with increasing temperature. The authors show that, with 50 fs laser pulses, the absorbtion coefficient presents a minimum near ablation threshold, at 5 × 10 13 W/cm 2 laser intensity. The evolution of interband absorption with the temperature is not taken into account in our calculations. Consequently, we may overestimate the energy absorbed in this intensity region.

For copper, the simulation overestimates the ablation threshold. This can be due to a deficit of physical process comprehension or to the inaccuracy of the parameters introduced in the model. No single value of γ or K e can perfectly fit the sets of data shown in Fig. 5 and6. As for the discussion of pressure presented above, one can think that a change in γ or K e has a similar effect on the threshold fluence F T h . Therefore, it is interesting to investigate the fluence threshold dependence on γ and K e . A parametric analysis has been performed for a copper target. Fig. 7 displays the threshold fluence which has been obtained for different parameter couples (γ, K e = K e0 ) and (γ = γ 0 , K e ). The deposited energy with lower thermal conductivity or higher coupling factor can penetrate deeper into the material. As a consequence, F T h is lowered with respect to that of the reference case (γ 0 , K e0 ) and would be comparable with experimental data in the vicinity of the threshold. However, simulations performed in these conditions have shown a higher disagreement with experimental data at higher fluence due to an earlier expanded vapor. On the contrary, for a reduced γ or an enhanced K e value, F T h increased and the ablation depth at high fluence is overestimated.

Results obtained with one-temperature simulations evidence the importance of the TTM to reproduce the experimental results. The good agreement obtained between experimental data and simulations underlines the need of coupling the TTM model with a hydrodynamic code for ablation simulations in metals. Numerical results presented in this paper give an overall description of processes occuring during ultrashort laser ablation experiments.

VI. CONCLUSION

In this paper, we have reported new results on the interaction of femtosecond laser pulses with metal targets at intensities up to 10 14 W/cm 2 . Numerical computations were carried out by means of a 1D hydrodynamic code describing the laser field absorption and the subsequent phase transitions of matter. Simulations were compared to original ablation experiments performed on aluminum and copper samples. The behavior of the ab- lation depth as a function of laser fluence confirms the importance of the use of specific two-temperature equa-tion of state and hydrodynamics. An optimum condition for laser fluence has been identified and could provide a precious information for efficient material processing. We have highlighted that ablation process is not only governed by electronic diffusion but also by the high shock formation and propagation. The differences between experimental and numerical results remain, however, more pronounced for low laser fluences. We took a great care to extend the metal properties to the nonequilibrium case. Nevertheless, inclusion of realistic material parameters, such as sophisticated band structure of metals or various scattering mechanisms, would allow calculations with more accuracy. Also, a full nonequilibrium treatment should take into account the conductivity dependence with both electron-electron and electron-phonon collisions. This work is in progress and implies an elaborate optical absorption model more suitable for ultrashort laser pulse.

Simulations suggest that the in-depth stresses induced by an ultrashort laser pulse provide information of the matter dynamics in time, with which experimental pressure measurements could be compared. In particular, because it develops over temporal scales larger than the energy deposition one, the characteristic shape of the delayed shock conveys information about interaction physics and it should thus supply a promising way for exploring matter distortions upon picosecond time scales.

FIG. 1 :

 1 FIG. 1: Representation of isobars in a phase diagram of the copper EOS in the region of phase transitions.

FIG. 2 :

 2 FIG.2: Contour plots of the stress resulting from the irradiation of a copper target by a 170 fs, 10 J/cm 2 laser pulse.

FIG. 3 :

 3 FIG.3: Time evolution of the stress in copper at 1 µm depth resulting from a 170 fs, 10 J/cm 2 laser pulse. Standard conditions : γ = γ0 and Ke = Ke 0 (solid line), γ =5 γ0 (dashed line), Ke = 10 Ke 0 (dotted line).

FIG. 5 :

 5 FIG.5: Experimental and numerical (solid line) ablation depth as a function of the laser fluence on a copper target obtained with a 170 fs laser pulse. The dashed line shows evolution of the specific removal rate.

FIG. 6 :

 6 FIG.6: Experimental and numerical (solid line) ablation depth as a function of the laser fluence on an aluminum target obtained with a 170 fs laser pulse. The dashed line shows evolution of the specific removal rate.

FIG. 7 :

 7 FIG.7: Calculation of the threshold fluence dependence on the coupling parameter γ and the electronic conductivity Ke for copper. Simulations are performed for different ratio of the standard value of one parameter remaining the second one constant. Consequently, the intersection of curves coincide with the value used in the calculation of ablation rate presented in Fig.5.