Anne Benoit

Louis-Claude Canon

Redouane Elghazi

Pierre-Cyrille Héam

Update on the Asymptotic Optimality of LPT

Keywords: Longest Processing Time (LPT) heuristic, Asymptotic performance, Empirical evaluation, Cost distributions. Résultats Heuristique LPT (Longest Processing Time), performance asymptotique, évaluation empirique, distribution de coûts

When independent tasks are to be scheduled onto identical processors, the typical goal is to minimize the makespan. A simple and efficient heuristic consists in scheduling first the task with the longest processing time (LPT heuristic), and to plan its execution as soon as possible. While the performance of LPT has already been largely studied, in particular its asymptotic performance, we revisit results and propose a novel analysis for the case of tasks generated through uniform integer compositions. Also, we perform extensive simulations to empirically assess the asymptotic performance of LPT. Results demonstrate that the absolute error rapidly tends to zero for several distributions of task costs, including ones studied by theoretical models, and realistic distributions coming from benchmarks.

Introduction

We revisit the classical problem of scheduling n independent tasks with costs p 1 , . . . , p n onto m identical processors. The goal is to minimize the total execution time, or makespan, usually denoted by C max . This problem, denoted P ||C max in Graham's notation [START_REF] Graham | Optimization and approximation in deterministic sequencing and scheduling: a survey[END_REF], has been extensively studied in the literature, and greedy heuristics turn out to have theoretical guarantees and to perform well in practice. In particular, we focus on the Longest Processing Time (LPT) heuristic, where the longest task will be scheduled first, on the processor where it can start the earliest. This heuristic is very simple and has a low complexity, while exhibiting good worst-case performance [START_REF] Graham | Bounds on multiprocessing timing anomalies[END_REF], and excellent empirical one. With a large number of tasks, LPT appears to be almost optimal.

Since the worst-case performance exhibits cases where LPT is further from the optimal, many different approaches have tried to fill the gap between this worst-case performance and the excellent practical performance. The goal is to provide performance guarantees of different kinds, for instance by studying the average-case complexity, some generic-case complexity, or convergence results.

Hence, many convergence results have been proposed in the literature. They state that LPT ends up providing an optimal solution when the number of tasks grows towards infinity. Some of these results even provide asymptotic rates that quantify the speed with which LPT tends to optimally. These results depend on assumptions on the probability distribution of the costs of the tasks, and on the definition of distance to optimality. However, the literature lacks a definitive answer on the convergence to optimality and its rate when faced with difficult cost distributions. In particular, this work is the first to consider dependent random costs with a constraint on the minimum cost.

First, Section 2 synthesizes the existing contributions and their limitations. Then, we revisit LPT and propose an update to these asymptotic optimality results, both from a theoretical perspective and from an empirical one. We also consider related heuristics, in particular a novel strategy recently proposed in [START_REF] Della Croce | The longest processing time rule for identical parallel machines revisited[END_REF]. Our contribution is twofold:

1. We derive a new convergence (in probability) result when the distribution of task costs is generated using uniform integer compositions, hence leading to a novel probabilistic analysis of the heuristics for this problem (Section 3);

2. We perform a thorough empirical analysis of these heuristics, with an extended range of settings to study particular distributions but also distributions coming from real applications (Section 4).

Related Work

Theoretical studies.

There are several theoretical works studying the rate of convergence of LPT. Coffman et al. [START_REF] Coffman | Probabilistic analysis of the LPT processor scheduling heuristic[END_REF] analyze the average performance of LPT under the assumption that costs are uniformly distributed in the interval (0, 1]. They show that the ratio between the expected makespan obtained with LPT and the expected optimal one with preemption is bounded by O(1

+ m 2 n 2 )
, where m is the number of processors and n is the number of tasks.

Frenk and Rinnooy Kan [START_REF] Frenk | The rate of convergence to optimality of the LPT rule[END_REF] bound the absolute error (i.e., the difference between the achieved makespan and the optimal one) of LPT using order statistics of the processing times when the cost distribution has a cumulative distribution function of the form F (x) = x a with 0 < a < ∞. The results also stand when this constraint is relaxed into F (x) = Θ(x a ). They prove that the absolute error goes to 0 with speed

O ( log log(n) n ) 1 a
as the number of tasks n grows. For higher moments, of order q, a similar technique gives a speed of

O ( 1 n ) a q .
Frenk and Rinnooy Kan [START_REF] Frenk | The asymptotic optimality of the LPT rule[END_REF] also study uniform machines (Q||C max ) in the more general case where costs follow a distribution with finite moment and the cumulative distribution function is strictly increasing in a neighbourhood of 0. They show that LPT is asymptotically optimal almost surely in terms of absolute error. When it is the second moment that is finite instead, they show that LPT is asymptotically optimal in expectation. For the more specific cases where the costs follow either a uniform distribution or a negative exponential distribution, they provide additional convergence rates.

Another theoretical study is done by Loulou [START_REF] Loulou | Tight bounds and probabilistic analysis of two heuristics for parallel processor scheduling[END_REF], providing a comparison between LPT and a less sophisticated heuristic, RLP (Random List Processing), also called LS (List Scheduling) in this paper. This heuristic is simpler than LPT because the jobs are considered in an arbitrary order instead of a sorted order. These algorithms are studied under the assumption that the costs are independent and identically distributed (i.i.d.) random variables with finite first moment. Under this assumption, the absolute error of RLP with at least three processors and LPT are both stochastically bounded by a finite random variable. The author also proves that the absolute error of LPT converges in distribution to optimality with rate O(1/n 1-).

Coffman et al. [START_REF] Coffman | Asymptotic methods in the probabilistic analysis of sequencing and packing heuristics[END_REF] list various results and techniques that are useful for the study of the problems of scheduling and bin packing. They consider both theoretical optimal results, and heuristic algorithm results. LPT is one of the algorithms they study, in terms of both relative error (LPT/OPT) and absolute error (LPT -OPT). They also reuse the specific probability distribution used by Frenk and Rinnooy Kan [START_REF] Frenk | The rate of convergence to optimality of the LPT rule[END_REF] of the form F (x) = x a , with 0 < a < ∞. They present a heuristic adapted from a set-partitioning problem with a better convergence on this distribution.

Piersma and Romeijn [START_REF] Piersma | Parallel machine scheduling: A probabilistic analysis[END_REF] have considered the R||C max problem (with unrelated machines), and they propose an LP relaxation of the problem, followed Inria Table 1: For each main result, the problem may consider uniform processors (P ) or processors with speeds (Q or R). A result on the absolute difference is stronger than on the ratio. OPT is the optimal makespan, whereas OPT * is the optimal makespan with preemption.

Problem

Distribution Studied quantity Convergence/rate

[2] P ||C max U(0, 1) E[LPT]/E[OPT * ] 1 + O(m 2 /n 2 ) [12] P ||C max F (x) = x a , 0 < a < ∞ LPT -OPT O((log log(n)/n) 1 a
) almost surely (a.s.) [START_REF] Frenk | The rate of convergence to optimality of the LPT rule[END_REF]

P ||C max as above E[(LPT -OPT) q ] O((1/n) a q ) [11] Q||C max finite 1st moment LPT -OPT a.s. [11] Q||C max finite 2nd moment LPT -OPT in expectation [11] Q||C max U(0, 1) or Exp(λ) LPT -OPT O(log n/n) a.s. [11] Q||C max U(0, 1) E[LPT] -E[OPT] O(m 2 /n) [18] P ||C max finite 1st moment LPT -OPT bounding finite RV [18] P ||C max U(0, 1) LPT -OPT O(1/n 1-) in dist. [4] P ||C max U(0, 1) E[LPT -OPT] O(m/(n + 1)) [20] R||C max U(0, 1) OPT nθ a.s.
by a Lagrange relaxation. Assuming that the processing times are i.i.d. random vectors of [0, 1] m , they prove that 1 n OPT converges almost surely to a value θ that they give (it depends on the Lagrange relaxation). Using a previous convergence result [START_REF] Frenk | The rate of convergence to optimality of the LPT rule[END_REF], they infer that the makespan of LPT also converges a.s. to nθ.

Dempster et al. [START_REF] Dempster | Analysis of heuristics for stochastic programming: results for hierarchical scheduling problems[END_REF] consider an objective function also depending on the machine cost, and they propose a heuristic in two steps, where they first choose the machines to be bought with knowledge of the distribution of the jobs, and then schedule the jobs on the machines that were bought in the first step. For identical machines, assuming that the processing times are i.i.d. random variables with finite second moment, they prove that the relative error of their heuristic converges to 0 in expectation and probability when the number of jobs goes to infinity. For uniform machines, they need more assumptions to reach results.

Summary.

Table 1 summarizes the main results that are known about LPT.

Beyond LPT.

Even though LPT has interesting properties in terms of convergence, other heuristics have been designed for the multiprocessor scheduling problem. For independent tasks and makespan minimization, the problem is actually close to a bin-packing problem, where one would like to create m bins of same size.

Hence, the MULTIFIT heuristic [START_REF] Coffman | An application of bin-packing to multi-processor scheduling[END_REF] builds on techniques used in bin-packing, and it provides an improved worst-case bound.

Then, a COMBINE heuristic was proposed [START_REF] Lee | Multiprocessor scheduling: combining LPT and MULTIFIT[END_REF], combining MULTIFIT and LPT to get the best of these two heuristics. Another alternative, LISTFIT, was proposed in [START_REF] Gupta | A LISTFIT heuristic for minimizing makespan on identical parallel machines[END_REF], still with the goal to minimize the makespan on identical machines.

Building on the Largest Differencing Method of Karmarkar and Karp [START_REF] Michiels | Performance Ratios for the Karmarkar-Karp Differencing Method[END_REF], a novel heuristic was proposed, outperforming LPT and MULTIFIT from an average-case perspective.

More recently, Della Croce and Scatamacchia [START_REF] Della Croce | The longest processing time rule for identical parallel machines revisited[END_REF] revisit LPT to propose yet another heuristic, SLACK, by splitting the sorted tasks in tuples of m consecutive tasks (recall that m is the number of processors), and then sorting tuples by non-increasing order of the difference between the largest and smallest task in the tuple. A list-scheduling strategy is then applied with tasks sorted in this order. Moreover, LPT last step is enhanced to reach a better worst-case approximation ratio.

Empirical studies.

An empirical comparison of LISTFIT with MULTIFIT, COMBINE and LPT is proposed in [START_REF] Gupta | A LISTFIT heuristic for minimizing makespan on identical parallel machines[END_REF]. Several parameters are varied, in particular the number of machines, number of jobs, and the minimum and maximum values of a uniform distribution for processing times. No other distribution is considered. LIST-FIT turns out to be robust and returns better makespan values than previous heuristics.

Behera and Laha [START_REF] Behera | Comparison of heuristics for identical parallel machine scheduling[END_REF] consider the three heuristics MULTIFIT, COMBINE and LISTFIT, and propose a comprehensive performance evaluation. While LISTFIT outperforms the two other heuristics, this comes at a price of an increased time complexity. They do not consider instances with more than 300 tasks, and no comparison with LPT is done.

An empirical evaluation of LPT was proposed in [START_REF] Laha | A comprehensive review and evaluation of LPT, MULTIFIT, COMBINE and LISTFIT for scheduling identical parallel machines[END_REF], showing that LPT consumes less computational time than the competitors (MULTIFIT, COMBINE, LISTFIT), but returns schedules with higher makespan values. However, here again, there is no study of the convergence, and no comparison of LPT with other simpler algorithms.

Finally, an evaluation of SLACK is done in [START_REF] Della Croce | The longest processing time rule for identical parallel machines revisited[END_REF]: this variant of LPT turns out to be much better than LPT on benchmark literature instances, and it remains competitive with the COMBINE heuristic that is more costly and more difficult to implement.

Beyond independent tasks.

While we have been focusing so far on independent tasks, there have also been some empirical analysis of list scheduling for general directed acyclic graphs (DAGs), i.e., with dependencies. For instance, Cooper et al. [START_REF] Cooper | An Experimental Evaluation of List Scheduling[END_REF] evaluate various list schedulers on benchmark codes, pointing out cases where a basic list Inria scheduling algorithm works well, and where more sophisticated approaches are helpful. In this paper, we focus on independent tasks to study the convergence of LPT and other heuristics.

Convergence Results for Integer Compositions

In this section, we derive new convergence results for four heuristics that are first described in Section 3.1. These results apply when the distribution of task costs is generated following an integer composition method. In contrast to related work where the number of tasks n is known beforehand, this consists in considering that the total amount of work W is fixed (costs are thus dependent random variables). We detail how tasks are generated among possible decompositions of this work (Section 3.2). We finally perform the probabilistic analysis in two different settings, depending whether the minimum cost of tasks is one (Section 3.3) or greater (Section 3.4).

The proofs of the results in this section are mainly based on combinatorics techniques. The reader is referred to [START_REF] Flajolet | Analytic Combinatorics[END_REF] for more information.

Algorithms

We consider four different list scheduling algorithms: they order the tasks in some way, and then successively assign tasks in a greedy manner, to the processor that has the lowest current finishing time (or makespan). Hence, tasks are always started as soon as possible, and for independent tasks, there is no idle time in the schedule.

The four algorithms differ in the way they first order the tasks:

• LS: List Scheduling is the basic list scheduling algorithm that does not order the tasks, but rather considers them in an arbitrary order. The time complexity of LS is O(n log m).

• LPT: Largest Processing Time orders the tasks from the largest to the smallest. The time complexity of LPT is O(n log n).

• MD: Median Discriminated is an attempt to find a intermediate solution between LPT and LS. The tasks are not completely sorted, but the median of the execution times is computed so that the first n 2 processed tasks are larger than the median, while the next n 2 are smaller. The time complexity of MD is O(n log m).

• SLACK: as defined by Della Croce and Scatamacchia in [START_REF] Della Croce | The longest processing time rule for identical parallel machines revisited[END_REF], it makes packs of m tasks and defines for each of these packs the slack, which is the difference between the largest and the smallest task of the pack. The packs are then sorted from the largest to the smallest slack and the tasks are ordered in the order incurred by the order of the packs. The time complexity of SLACK is O(n log n).

Tasks Random Generation

A W -composition is a finite sequence p 1 , . . . , p n of strictly positive integers such that p 1 + . . . + p n = W . Let D W be the uniform distribution over W -compositions and D W,pmin the uniform distribution over W -compositions satisfying for each i, p i ≥ p min . In particular, D W,1 = D W . For instance, D 4 is the uniform distribution over the eight elements (1, 1, 1, 1), (1, 1, 2), (1, 2, 1), (1, 3), (2, 1, 1), (2, 2), (3, 1), (4); D 4,2 is the uniform distribution over (2, 2) and ( 4). Note that for D 4 , the probability that p 1 = 1 is 1/2 and the probability that

p 1 = 3 is 1/8.
In practice, random generation is performed using the recursive method [START_REF] Flajolet | A calculus for the random generation of labelled combinatorial structures[END_REF].

For a list L of task costs, we denote by LPT(L, m) the makespan C max returned by LPT on m machines. We define as well LS(L, m), MD(L, m) and SLACK(L, m) for the other heuristics. The optimal (minimum) C max that can be obtained by any algorithm is similarly denoted OPT(L, m).

Probabilistic Analysis of List-Scheduling Heuristics for D W

Ratio for D W .

In this setting, we know the total workload W , but the number of tasks n is not fixed and there is no minimum task cost. Let L[W ] = (p 1 , . . . , p n ) be a sequence of positive integers such that n i=1 p i = W , hence a W -composition. According to [START_REF] Graham | Bounds on multiprocessing timing anomalies[END_REF],

LS(L[W ], m) OPT(L[W ], m) ≤ 1 + (m -1) p max n i=1 p i = 1 + (m -1) p max W ,
where p max = max{p i }.

Following [9, page 310], for D W and for any y,

P (p max ≥ 2 log 2 W + y) = O e -2y W . ( 1
)
Since by definition of OPT, OPT(

L[W ], m) ≤ LS(L[W ], m), for any fixed m, P LS(D W , m) OPT(D W , m) ≤ 1 + 2(m -1) log 2 (W ) W -→ W →+∞ 1. (2)
It is also known, see [9, Proposition V.I.], that for the distribution D W , E[p max ] ∼ log 2 W . By linearity of expectations, the following result holds:

E LS(D W , m) OPT(D W , m) -→ W →+∞ 1.
The results also hold for LPT, MD and SLACK, which are particular listscheduling heuristics. The absolute error of a heuristic is the difference between its result and the optimal result. A first obvious upper bound is that LS(L, m) -OP T (L, m) ≤ p max (for any set of tasks L), and previous results on p max can be used to bound the error (but not proving it tends to 0). Furthermore, we prove the following theorem:

Theorem 1. Algorithms LPT and SLACK are optimal for D W , with probability 1 -O 1 W . For any fixed m, for L generated according to D W ,

P(LPT(L, m) = OPT(L, m)) = 1 -O 1 W
, and

P(SLACK(L, m) = OPT(L, m)) = 1 -O 1 W
, and

P(MD(L, m) ≤ OPT(L, m) + 1) = 1 -O 1 W .
To prove this theorem, let us first prove two lemmas. Let α W be the random variable counting the number of p i 's equal to 1 in D W . Proof. There are 2 W -1 compositions of W . The expected number of parts n is W +1 2 . The number of 1-parts in a composition of W is given by the ordinary generating function C(z, u) =

1 1-( z 1-z +(u-1)z) = 1-z 1-2z-z(1-z)(u-1) (see [9, page 168]).
Moreover, we have [9, Proposition III.2]:

E[α W ] = [z W ]∂ u C(z, u) |u=1 [z W ]C(z, 1) = [z W ]∂ u C(z, u) |u=1 2 W -1 , (3)
and

E[α 2 W ] = [z W ]∂ 2 u C(z, u) |u=1 [z W ]C(z, 1) + [z W ]∂ u C(z, u) |u=1 [z W ]C(z, 1) . ( 4
) Also, ∂ u C(z, u) = z(1-z) 2 (1-2z-(u-1)z(1-z)) 2 . Therefore ∂ u C(z, u) |u=1 = z(1-z) 2 (1-2z) 2 = z 4 -1 4 + 1 8(1-2z) + 1 8(2z-1) 2 . Using Equation (3), we obtain for W ≥ 2, E[α W ] = W + 2 4 . Now, ∂ 2 u C(z, u) = 2z 2 (1-z) 3 (1-2z-z(1-z)(u-1)) 3 and ∂ 2 u C(z, u) |u=1 = 2z 2 (1-z) 3 (1-2z) 3 = z 2 4 - 3z 8 - 1 8(1-2z) + 1 16(1-2z) 2 + 1 16(1-2z) 3 .

RR n°9397

It follows that for W ≥ 3,

E[α 2 W ] = W (W + 1) 16 + W + 1 8 - 1 4 + W + 2 4 . It follows that Var[α W ] = E[α 2 W ] -E[α W ] 2 = 5 16 (W + 1).
Lemma 2. Let A W be the event α W > W 8 and B W be the event p max ≤ 2 log 2 W . For D W , we have:

P(A W ∩ B W ) = 1 -O 1 W .
Proof. We have:

P α W ≤ W 8 = P α W ≤ W + 2 4 - W + 4 8
≤ P α W ≤ W + 2 4 - W + 4 8 + P α W ≥ W + 2 4 + W + 4 8 = P α W - W + 2 4 ≥ W + 4 8 .
Now, using Lemma 1 and Chebyshev's inequality, we obtain:

P α W ≤ W 8 ≤ 5 16
W + 1 ( W +4 8 ) 2 = 20 W + 1 (W + 4) 2 = O( 1 W ).
It follows that P(A W ) = O( 1 W ). Furthermore, according to Equation (1),

P(B W ) = O( 1 W ). Finally, P(A W ∩ B W ) = 1 -P(A W ∪ B W ) ≤ 1 -P(A W ) -P(B W ) = 1 -O 1 W ,
which concludes the proof.

We are now ready to prove Theorem 1.

Proof. By Lemma 2, one has with probability 1

-O( 1 W ), |{i | p i = 1}| < W 8
and p max ≤ 2 log 2 W . Assume that L[W ] satisfies these two properties, and let δ be the maximum difference of loads between two processors when there remains W 8 tasks to scheduled (scheduling with LPT). One has δ ≤ p max ≤ 2 log 2 W . Now, the remaining tasks to be scheduled are unitary. Since the function mapping x to x -16(m -1) log 2 x is strictly increasing for x ≥ 1 and tends to infinity when x → +∞, there exists an integer W 0 such that, for every

W ≥ W 0 , W 8 ≥ 16(m -1) log 2 W .
Consequently, the remaining unitary tasks will be optimally scheduled, proving the theorem for LPT.

Inria

For the SLACK algorithm, the proof is quite similar. By Lemma 2, one has with probability 1 -O( 1W ), α W < W 8 and p max ≤ 2 log 2 W . In this case, there are at least W 8(m+1) m-tuples appearing in the SLACK algorithm with a null slack and composed of tasks of cost 1. Moreover each m-tuple has a maximal 2 log 2 W -1 slack (when the tuple contains a maximal and a minimal p i ). Therefore, for W large enough, the scheduling of the W 8(m+1) tuples of unitary tasks fulfills any difference between the current processing times of the machines. Note that we may still have some non-unitary tasks to schedule, but since tuples are sorted by non-increasing slack, they would also be organized in m-tuples with null stack.

It remains to prove a similar result for MD but up to 1 to the optimal. Let ρ W = |{i | p i = 2}|. The bivariate generating function associate to ρ W is and p max ≤ 2 log 2 W . Assume for the rest of the proof that this is the case.

G(z, u) = 1 -z 1 -2z + (u -1)(1 -z)z 2 . Since ∂ u G(z, u) |u=1 = (1-z) 2 z 2 (1-2z) 2 =, z∂ u A(z, u) |u=1 , we have, [z W ]∂ u G(z, u) |u=1 = [z W -1 ]∂ u A(z, u) |u=1 . It follows that, for W ≥ 2, E[ρ W ] = W +1 8 . Similarly ∂ 2 u G(z, u) |u=1 = z 2 ∂ 2 u A(z, u), providing that, for W ≥ 3, E[ρ 2 W ] = (W -2)(W -1) 64 + W -1 32 -1 4 + W +1 8 .
Let n be the number of tasks. There are n-α W -ρ W that are of cost greater than or equal to 3. Therefore,

n -α W -ρ W ≤ W -α W -2ρ W 3 . Consequently n -2α W -2ρ W ≤ W -4α W -5ρ W 3 ≤ W 3 (1 -11 16 -5 16 ) ≤ 0. Since α W + ρ W ≥ n 2
, the task of medium value has either cost 1 or 2. If it is 1, then MD is optimal (with the same arguments as for LPT). Otherwise, MD is up to 1 to the optimal. Theorem 1 can be reformulated in a convergence in probability result:

P(|MD(L, m) -OPT(L, m)| ≥ 1 + ε) = 0. Proof. P(|LPT(L, m) -OPT(L, m)| ≥ ε) = P(LPT(L, m) -OPT(L, m) ≥ ε) ≤ P(LPT(L, m) -OPT(L, m) > 0) = 1 -P(LPT(L, m) -OPT(L, m) = 0) = O 1
W . The proof is similar for SLACK and MD.

Analysis for D W,p min

Let min{p i } = p min ≥ 2. Let α W,pmin be the number of p i 's equal to p min in a decomposition (p 1 , . . . , p k ) satisfying p i = W and for every i, p i ≥ p min . The random variable α W,pmin is studied for the D W,pmin distribution. Let also γ pmin,k be the number of p i 's greater than or equal to k (with k ≥ p min ).

P(|SLACK(L, m) -OPT(L, m)| ≤ p min ) -→ W →+∞ 1 .
The proof is based on two lemmas.

Lemma 3. There exists a constant

β > 0 such that E[α W,pmin ] ∼ W →+∞ β(n+1). Moreover, Var[α W,pmin ] = o(W 2 ).
Proof. The ordinary generating function for compositions (p 1 , . . . , p k ) satisfying p i = W and for every i, p i ≥ p min is:

A(z) = 1 1 -z p min 1-z = 1 -z 1 -z -z pmin . Let Q(z) = 1 -z -z p min .
The polynomial Q is strictly decreasing on R + and Q(0) = 1 and Q(1) = 1. Therefore, Q has a unique real root σ satisfying 0 < σ < 1. Consequently, there exists a polynomial P with real coefficients such that Q(z) = (σ -z)P (z). Moreover, since lim z→σ -Q(z) = 0 + and since Q has no multiple roots, P (σ) > 0.

It follows that A(z) ∼ z→σ 1-σ (σ-z)P (σ) . Using transfer results [9, Corollary VI.I], we obtain:

[z W ] A(z) ∼ W →+∞ 1 -σ σP (σ) σ -W . ( 5
)
The bivariate ordinary generating function for the number decompositions (p 1 , . . . , p k ) satisfying p i = W and for every i, p i ≥ p min , and counting the number of p i 's equal to p min is

A(z, u) = 1 1 -( z p min 1-z -(u -1)z pmin ) = 1 -z 1 -z -z pmin + (1 -z)(u -1)z pmin . It follows that ∂ u A(z, u) = (1-z) 2 z p min (1-z-z p min +(1-z)(u-1)z p min ) 2 and ∂ u A(z, u) |u=1 = (1 -z) 2 z pmin (1 -z -z pmin ) 2 = (1 -z) 2 z pmin (σ -z) 2 P (z) 2 ∼ z→σ (1 -σ) 2 σ p min (σ -z) 2 P (σ) 2 .
Therefore, using [9, Corollary VI.I] again,

[z W ] ∂ u A(z, u) |u=1 ∼ W →+∞ (1 -σ) 2 σ p min σ 2 P (σ) 2 σ -W (W + 1). ( 6
)

Inria

Consequently, using [9, Proposition III.2] and Equations ( 5) and ( 6),

E[α W,pmin ] ∼ W →+∞ (1 -σ) 2 σ p min σ 2 P (σ) 2 σP (σ) 1 -σ (W + 1) = (1 -σ)σ pmin-1 P (σ) (W + 1) = β(W + 1), with β = (1-σ)σ p min -1 P (σ)
. It remains to prove the result for the variance. One has

∂ 2 u A(z, u) |u=1 = 2(1 -z) 3 z 2r (σ -z) 3 P (z) 3 ∼ z→σ 2(1 -σ) 3 σ 2r (σ -z) 3 P (σ) 3 .
Consequently,

[z W ] ∂ 2 u A(z, u) |u=1 ∼ W →+∞ 2(1 -σ) 3 σ 2r σ 3 P (σ) 3 (W + 1)(W + 2) 2 σ -W . ( 7
)
According to [9, Proposition III.2] and using Equation ( 5),

E[α 2 W,pmin ] ∼ W →+∞ 2(1 -σ) 3 σ 2r σ 3 P (σ) 3 σP (σ) 1 -σ (W + 1)(W + 2) 2 + β(W + 1) ∼ W →+∞ β 2 (W + 1)(W + 2).
We have proved that

E[α W,p min ] W -→ W →+∞
β and

E[α 2 W,p min ] W 2 -→ W →+∞ β 2 . It follows that Var[α W,pmin ] W 2 = E[α 2 W,pmin ] -E[α W,pmin ] 2 W 2 -→ W →+∞ 0,
which concludes the proof.

Lemma 4. One has, for the D W,pmin distribution,

P(p max ≥ log 2 1/σ (W )) -→ W →+∞ 0,
where σ is the unique real root of 1 -z -z k = 0 (0 < σ < 1).

Proof. Let B(z, u) be the bivariate ordinary generating function of D W,pmin , with parameter the number γ pmin,k . One has B(z, u) =

1 1-( z p min 1-z +(u-1) z k 1-z ) = 1-z 1-z-z p min +(u-1)z k .
The proof lies on Markov inequality. We will point out an upper bound of E[γ pmin,k ]. One has

E[γ pmin,k ] = [z W ] ∂ u B(z, u) |u=1 [z W ]B(z, 1) . ( 8
) Now, ∂ u B(z, u) |u=1 = (1-z)z k (1-z-z p min ) 2 . Since 1-z (1-z-z p min ) 2 ∼ σ 1-σ (z-σ) 2 P (σ) 2 , using [9, Corollary VI.I] one has [z W ] 1-z (1-z-z p min ) 2 ∼ W →+∞ 1-σ σ 2 P (σ) 2 σ -W (W + 1), that can be reformulated into [z W ] 1-z (1-z-z p min ) 2 = 1-σ σ 2 P (σ) 2 σ -W (W + 1)(1 + ε(W ))
, with ε(W ) → 0 when W → +∞. Note too that ε(W ) depends on p min but not on k. It provides

[z W ] ∂ u B(z, u) |u=1 = [z W -k ] 1 -z (1 -z -z pmin ) 2 (9) = 1 -σ σ 2 P (σ) 2 σ -W +k (W -k + 1)(1 + ε(W -k)). ( 10
) Similarly, [z W ] B(z, 1) |u=1 = [z W ] 1-z (1-z-z p min ) 2 = 1-σ σP (σ) σ -W (1 + ε (W ))
, with ε (W ) → 0 when W → +∞. Note that ε (W ) depends on p min but not on k. Therefore, and combining ( 8) and ( 10), one obtains

E[γ pmin,k ] = σ k (W + 1 -k) σP (σ) 1 + ε(W -k) 1 + ε (W ) . ( 11
)
With k = log 2 1/σ W , Equation ( 11) becomes

E[γ pmin,k ] = σ log 2 1/σ W (W + 1 -log 2 1/σ W ) σP (σ) 1 + ε(W -log 2 1/σ W ) 1 + ε (W ) ≤ W 1-log 1/σ W σP (σ) 1 + ε(W -log 2 1/σ W ) 1 + ε (W ) . Since 0 < σ < 1, W 1-log 1/σ W -→ 0 W →+∞ .
To finish, using Markov inequality,

P(p max ≥ log 2 1/σ (W ))) = P(γ pmin,log 2 1/σ (W ) ≥ 1) ≤ E[γ pmin,log 2 1/σ (W ) ],
proving the lemma.

One can now prove Theorem 2.

Proof. We only provide a sketch of the proof, which is similar to the one of Theorem 1. Using Lemma 3 and Lemma 4, almost surely there is a linear number (relatively to W ) of tasks of cost p min and the maximum cost of a task is bounded by log 2 1/σ . Therefore, applying LPT will provide a maximum load C such that C -W/m ≤ p min . The inequality OPT ≥ W/m concludes the proof. The proof for SLACK follows as for Theorem 1.

We do not have yet any theoretical results for MD for D W,pmin , but experimental results explored in Section 4 are encouraging.

As for Theorem 1 one can deduce the following corollary from Theorem 2 (with a similar proof).

Empirical Study

The objective of this section is threefold: first, evaluate the tightness of the convergence rate proposed in [START_REF] Frenk | The rate of convergence to optimality of the LPT rule[END_REF] (Section 4.2); then, assess the performance of the four heuristics when generating costs with the integer composition approach (Section 4.3); finally, quantifying the convergence for realistic instance (Section 4.4). We first detail the experimental setting in Section 4.1. All the algorithms were implemented in Python 3, and the code is available on figshare1 .

Experimental Setting

Synthetic Instances.

We consider two kinds of synthetic instances: (1) i.i.d. execution times with cumulative distribution function F (x) = x a for some a > 0. This distribution has an expected value of a a+1 and a variance of a (a+1) 2 •(a+2) . These values can be seen as a function of a in Fig. 1. Note that for a = 1, this is a uniform distribution U(0, 1). (2) The integer composition distribution considered in Section 3, that is to say a uniform distribution on all possible ways to decompose a total amount of work into integer values. Execution time (log)

Figure 2: Empirical cumulative distributions and histograms of task costs for the KIT ForHLR II and NASA Ames iPSC/860 instances.

Realistic Instances.

We also compare the four algorithms of Section 3.1 using real logs from the Parallel Workloads Archive, described in [START_REF] Feitelson | Experience with using the parallel workloads archive[END_REF] and available at https://www. cs.huji.ac.il/labs/parallel/workload/. More specifically, we took the instances called KIT ForHLR II2 with 114 355 tasks and NASA Ames iPSC/8603 with 18 239 tasks. The profiles of the task costs in these instances are presented in Fig. 2.

In order to also get instances for which the number of tasks n could change, we build new instances from these two instances. In the new instances, the tasks are i.i.d. random variables with an empirical cumulative distribution function that is computed from the distribution of the two original instances.

Optimality Transform.

When studying the absolute error of an algorithm, we consider the difference of its makespan to the optimal one to measure the convergence when the number of tasks n goes to infinity. The optimal makespan is computationally hard to get, so as a first approach, we can take a lower bound instead of the actual optimal value. However, there is a risk of actually measuring the quality of the lower bound instead of the quality of the algorithm.

To address this problem, we transform the instances so that we know the optimal makespan. This transformation is described as follows:

• we take an instance with n tasks;

• we perform a random List Scheduling on this instance;

• from this schedule, we add a total of at most m -1 tasks so that all of the processors finish at the same time;

• we randomize the order of the tasks to avoid adding a bias to the heuristics;

• we end up with an instance with at most n + m -1 tasks such that the optimal makespan equals the sum of the execution times divided by the number of processors (OPT = W m ).

As we are interested in the asymptotic behavior of the algorithms, m is small compared to n, and we expect this transformation to alter the task distribution only marginally. However, studying the precise distribution of the added tasks is left to future work.

Rate Tightness

We experimentally verify the bound given in [START_REF] Frenk | The rate of convergence to optimality of the LPT rule[END_REF]: if the tasks are independent and have cumulative distribution function F = x a with a > 0, then the absolute error is a O(( log log(n) We can see that the bound seems to be rather tight for LPT, which confirms that the convergence rate of [START_REF] Frenk | The rate of convergence to optimality of the LPT rule[END_REF] is strong. Also, we can see that the absolute error of SLACK seems to converge to 0 at a similar rate than LPT, but with a lower multiplicative constant. On the other side, the absolute errors of LS and MD do not seem to converge to 0 at all, but MD performs significantly better than LS.

Uniform Integer Compositions

Some experiments have been performed for the distributions described in Section 3: a total workload W is fixed as well as a fixed number m of machines. Then, the list of task costs is uniformly picked among all the possible lists for the distribution D W ; and among all the possible lists with a minimum cost p min for the distribution D W,pmin .

For D W , an instance has been generated for all W from 10 to 9999, for m = 10, m = 30, and m = 100. Instances are not transformed to avoid changing the total work W . Thus, we compare the makespan obtained by the heuristics to the lower bound on the optimal value OPT: max( W m , p max ). In all cases (about 30 000), LPT and SLACK always reach this bound, which indicates that they are both optimal and the bound is tight with these instances. Results for LS and MD are reported in Table 2. The average absolute error for MD is 0.35 for this experiment with a standard deviation of 0.6. Moreover MD is optimal 3). We now focus on the difference δ between C max and the lower bound. In each case, the maximal value of δ is reported, as well as its average and standard deviation. Note that for each sample, both SLACK and LPT ensure that δ < p min , and MD ensures it in 99% of cases. The LS heuristic is less effective since for p min = 3, only 41% of the samples satisfy δ < p min ; 49% for p min = 5, 53% for p min = 7 and 58% for p min = 10. Results for the SLACK and LPT heuristics are very close. Over the about 120 000 samples, SLACK is strictly better than LPT only 55 times, when LPT is strictly better than SLACK only 54 times. Each time, the difference is either 1 or 2. On these distributions, SLACK and LPT seem to compete equally.

Realistic Workloads

In Fig. 4, we present experiments similar to those with synthetic instances in Section 4.2, but with the realistic instances.

As we can see when comparing LS and MD, treating the n 2 largest tasks first Inria only marginally decreases the makespan of LS. We can also see that when n grows, the absolute error of LPT seems to be on par with the one of SLACK.

In [START_REF] Della Croce | The longest processing time rule for identical parallel machines revisited[END_REF], SLACK was found to perform generally better than LPT for some synthetic instances, which differs from the results we get with more realistic instances. Finally, LPT seems to converge even faster to the optimal with these instances than with the synthetic ones, as the absolute error quickly becomes close to 0.

Conclusion

Given various probability distributions, we have evaluated the performance of four heuristics, among which the classical LPT heuristic and the more recent SLACK one. The literature already contains important theoretical results either in the form of different kinds of stochastic convergence to optimality or with a convergence rate. To the best of our knowledge, this paper is the first to empirically assess the tightness of a theoretical convergence rate for LPT. Furthermore, we focus on a novel definition of uniformity for the cost distribution: for a given total work, any integer composition can be drawn with the same probability, which leads to dependent random costs. This distribution is further enhanced by considering a subset of the decompositions that constrains the minimum cost. This paper proves the convergence in probability of LPT and similar heuristics with these distributions as well. Finally, we empirically analyze the convergence with realistic distributions obtained through traces. All these results contribute to understand the excellent performance of LPT in practice. Future work will consist in obtaining stronger convergence theoretical results. For instance, existing results only consider that the number of tasks n tends to infinity. The impact of a varying number of processors m could be explored. Also, this work is the first attempt to consider dependent cost distributions, but many such distributions exist and could be explored. For instance, the same application consisting of a given set of tasks can be executed with different input size. The tasks could thus often have the same profile to a given multiplying factor. Finally, the novel distribution in this paper presents a minimum cost. Existing convergence results for independent distributions could probably be extended to consider costs with a similar minimum value. For instance, the worst-case ratio for LPT is achieved with costs 1 3 and 1 2 . The uniform distribution U( 13 , 1 2 ) could thus present some challenges.

Inria

3. 3 . 2

 32 Absolute error for D W .

Lemma 1 .

 1 For W ≥ 3,

Corollary 1 .

 1 For every ε > 0, for the distributions D W , lim W →+∞ P(|LPT(L, m) -OPT(L, m)| ≥ ε) = 0, and lim W →+∞ P(|SLACK(L, m) -OPT(L, m)| ≥ ε) = 0, and lim W →+∞

Theorem 2 .

 2 Let m be a fixed number of machines. One has, for L generated according to D W,pmin , P(|LPT(L, m) -OPT(L, m)| ≤ p min ) -→ W →+∞ 1 and

Figure 1 :Corollary 2 .

 12 Figure 1: Expected value and standard deviation of a random variable with cumulative distribution function F (x) = x a as a function of a with 0 < a < ∞.

  n

) 1 a 1 a

 11 ) almost surely. Fig.3depicts the absolute error of LPT and related heuristics (LS, MD and SLACK) for different values of n. The instance contains n-m+1 costs generated with the considered distribution and is then completed with the optimality transform. Moreover, we plot C • ( log log(n) n ) , where C is the lowest constant such that all of LPT values are under the bound.

Figure 3 :

 3 Figure3: Absolute error with a distribution of the form F (x) = x a with a > 0 (instances are transformed to obtain OPT). Smoothed lines are obtained by using a rolling median with 45 values (each value is set to the median of the 22 values on the left, the 22 on the right and the current one).

Figure 4 :

 4 Figure4: Absolute error with costs derived from the KIT ForHLR II and NASA Ames iPSC/860 instances (after optimality transformation). Smoothed lines are obtained by using a rolling median with 45 values (each value is set to the median of the 22 values on the left, the 22 on the right and the current one). The ribbons represent the rolling 0.1-and 0.9-quantiles.

Table 2 :

 2 Distribution of the absolute errors observed for LS and MD with W from 10 to 9999 and m ∈ {10, 30, 100}.

	abs. err.	LS	MD	abs. err.	LS	MD
	0	3.3	67.6	6	8.9	0.04
	1	10.8	30.5	7	5.0	0.02
	2	17.0	0.88	8	2.7	0.01
	3	18.4	0.56	9	1.2	0.01
	4	17.4	0.23	10	0.6	< 0.01
	5	14.0	0.09	> 10	0.7	< 0.01

Table 3 :

 3 Results on the difference between the C max computed by the heuristics and a lower bound of the optimal makespan OPT. Each line is related to different D W,pmin . The first number is the maximum difference observed for all the samples, the second one is the average difference, and the last one is the standard deviation of this difference. Each value is obtained with W from 10 to 9999 and for m ∈ {10, 30, 100}. 6% of the samples and up to 1 from the optimum in 98% of the samples. LS is optimal in 3.3% of the cases and the average error is 3.75 (s.d. 2.15).Similar tests have been done for D W,pmin with W ∈ {10, . . . , 9999}, p min ∈ {3, 5, 7, 10} and m ∈ {10, 30, 100} (see Table

	p min	LPT	LS	MD	SLACK
	3	2 -0.92 -0.71 16 -2.53 -0.92 10 -1.47 -0.58 2 -0.92 -0.71
	5	4 -1.82 -1.23 24 -4.28 -1.51 10 -2.66 -0.90 4 -1.82 -1.23
	7	6 -2.69 -1.81 26 -5.95 -2.15 12 -3.63 -1.20 6 -2.69 -1.81
	10	9 -3.92 -2.67 38 -8.32 -3.22 15 -5.17 -1.86 9 -3.92 -2.67
	in 67.

RR n°9397

https://doi.org/10.6084/m9.figshare.14067839 RR n°9397

https://www.cs.huji.ac.il/labs/parallel/workload/l_kit_fh2/index.html

https://www.cs.huji.ac.il/labs/parallel/workload/l_nasa_ipsc/index.html Inria


Delphine Neff
email: neff@drecam.cea.fr

Solenn Reguer
email: reguer@drecam.cea.fr

Ludovic Bellot-Gurlet
email: bellot-gurlet@glvt-cnrs.fr

Philippe Dillmann
email: dillman@drecam.cea.fr

Régis Bertholon
email: regis.bertholon@univ-paris1.fr

Structural characterisation of corrosion products on archaeological iron. An integrated analytical approach to establish corrosion forms

Keywords: Raman micro-spectroscopy, synchrotron X-Rays micro-diffraction, iron oxides and oxy-hydroxides, archaeological artefact, corrosion typologies

The description and identification of corrosion products formed on archaeological iron artefacts needs various approaches at different observation scales. For this study, samples of five different sites were prepared using two techniques. The first one consists in cutting cross sections perpendicular to corrosion layers. This allows local observations and analysis of the corrosion layer stratigraphy at different levels. The second one consists in performing manual grinding or abrading of the corrosion layers starting from the current surface of the excavated artefact to the metal core. It allows the description of the successive layers and is well adapted for the analysis on a larger scale. In addition to these two observation scales, the identification of the iron oxides formed needs the coupling of several complementary techniques. Elementary compositions were determined by SEM-EDX and Electron Micro-Probe Analysis (EMPA). Structural identification was performed by X-ray micro Diffraction under synchrotron radiation (μXRD) and micro Raman spectroscopy. These analyses were performed on the same samples both with X-ray diffraction and Raman spectroscopy in order to ensure a reliable characterisation. In some cases there are some ambiguities or overlapping between signatures of different phases by micro X-rays diffraction (as maghemite/magnetite) or Raman spectroscopy (as goethite/magnetite) which can be raised by the association of the two methods. The final aim is to set up an analytical methodology that will be the best for the study of ancient iron corrosion products. It is the first step of the study of long term mechanisms of iron in soil.

INTRODUCTION

Archaeological iron artefacts undergo corrosion phenomenon during their burial period and also after excavation. These degradations can lead to a dramatic state of certain objects and in consequence information about their function or forging treatments could be lost. Though it is important to increase the knowledge on long term corrosion mechanisms in order to restore the excavated objects and prevent their further deterioration. The aim of this paper is to present a global study dedicated to the determination of corrosion forms on five different archaeological sites. This paper will focus on the presentation of the Raman microspectroscopy analytical contribution to point out its complementarity with other techniques also employed in this study to give structural information at the microscopic scale.

Corrosion of archaeological artefacts

Up to now, the corrosion of this kind of artefacts in soil has been studied for different purposes and some of them are reviewed here. On one hand some authors [START_REF]ctes du colloque "Journées de 3. nd native 4. 5. metals 6. s conservation[END_REF][START_REF] Miller | [END_REF][3][4] consider archaeological artefacts as analogues for the estimation of iron corrosion behaviour in soil, particularly for obtaining average corrosion rates. Unfortunately, these studies rarely give detailed analysis of the corrosion products. On the other hand other kind of studies provides information for preventing degradation after excavation and ensuring reliable restoration. These recent ones aimed at the understanding of the corrosion phenomenon in the field of conservation of archaeological artefacts. Soerensen et al. 5 underline the difficulty of this kind of work. Soil is in fact a complex environment and different parameters as geological factors (soil types, pH and electrical resistivity), hydrological factors (water flow through ground layers) and soil chemical composition play a role in the corrosion process. Gerwin et al. 6 worked on iron nails and measured the degree of corrosion by comparing the size of the metal core remaining with that of the object before corrosion estimated from Xray photograph. This method is not very precise because of the difficulty in determining the original size. Nevertheless the obtained results show general tendencies about the influence of soil composition on iron corrosion rates. For example, phosphates and specially carbonates lead to the formation of a protective layer on the metal that slows down the corrosion process, but the phases constituting this layer were not specified in this study. Conversely, a high sulphates or chlorides content in soil water ensures the destruction of layers covering the metallic substrate that would have been protective. To estimate corrosion rates, two simulation studies have been carried out on steel buried in soil. Angelini et al. [START_REF]als conservation, Draguignan-8. tals conservation, 9. i , Université de 10. es System[END_REF] studied a soil with a high content of organic matter and carbonates. These authors showed that the sample corrosion rate decreases with burial time (from 0.035 g/dm²/day after 30 days to 0.028 g/dm²/day after 120 days). To complete these observations X-ray Diffraction (XRD) and Fourier Transform Infrared Spectroscopy (FT-IR) data were collected in order to identify the corrosion layers. They report the presence of goethite (α-FeOOH), akaganeite (β-FeOOH) an oxyhydroxide containing chloride, magnetite (Fe3O4) and siderite (FeCO3) in the corrosion products. Fell et al. 8 analysed archaeological artefacts excavated from a waterlogged deposit. This particular environment leads to the formation of aggregates of sulphides, identified by XRD. These phases are formed principally through biological activity. On some samples the major corrosion product was siderite: it is assumed that this phase is often associated with sulphides. Some studies were specifically dedicated to the understanding of the long term corrosion behaviour of archaeological iron artefacts in clay soils. Pons et al. 9,10 performed Raman microspectroscopy analyses on cross sections of about ten corroded archaeological iron artefacts dated from the beginning of the XX th century and coming from the same site. These analyses reveal the presence of goethite and magnetite as main corrosion products. Moreover, some electrochemical measurements on these artefacts show that the internal zone of the corrosion products seems to be less porous than the external one.

The limit of the original surface

To find the original shape of archaeological artefacts, Bertholon 11,12 worked on the concept of original surface (OS). The author defined the original surface as the artefactʹs surface at the time of its burial or abandonment, that means before the beginning of the corrosion process. When the artefact has corroded, its surface has changed but it is still possible to locate the limit of the original surface (also named limitos) within the present corroded materials. The limitos is the limit between different materials that constituted the object (metal, mineral and organic parts) and the surrounding soils at the time of the abandonment. Then it is expected to find special features in the artefactʹs corrosion layers regarding their position to the limit of the original surface. Corrosion layers located under the limitos are recognisable because they contain "inner markers" coming out from the metallic substrate (slag inclusions for example), and those located above the limitos by the presence of "outer markers", such as soil minerals (quartz grains…). The limit of the original surface does not always coincide with the level of the original surface of the object because it can move during the formation of oxide scales.

When examining the artefact prior to treatment, conservators carefully abrade the corrosion layers under binoculars by manual mechanical means (scalpels, needles, micro-grinding wheels, microsandblasting, etc.). This limited drilling allows conservators to distinguish the main corrosion strata according to their nature (corrosion products, soil, deposit, metal, etc.) and physical characters (colour, hardness, compactness, porosity, etc.). Other strata characters such as shape, direction are described according to a new descriptive method of corrosion being currently perfected [START_REF] Masson | es de conservation[END_REF]12 .

Aim of the study

Considering this short review, all the studies on archaeological artefacts cited here are very dissimilar. It appears that literature data alone are not sufficient to provide a complete and statistical overview. Moreover, the fine and local determination of the corrosion products structure was rarely undertaken and it is important to obtain such data to understand the corrosion mechanisms. Two methods that allow the identification of the structure at micrometric scale are the synchrotron X-ray micro diffraction (μXRD) and the Raman microspectroscopy (μRaman): they were employed to study the iron corrosion during long period. The aim was to collect information on the corrosion phenomenon by analysing a large number of corroded artefacts. To this purpose, the corrosion products of about forty archaeological artefacts were analysed. First, Neff et al. 13 proceed to a local characterisation of the corrosion products of 9 artefacts coming from 3 different sites aged of 500, 600 and 800 years by micro X Ray diffraction (μXRD) 14 . In this study, the analytical approach, including composition and structure analysis by Raman micro spectroscopy, was specially established to study statistically significant series. Moreover, two complementary preparation techniques of the samples were tested on the artefacts: on one hand analyses on cross sections and on the other hand, stratigraphic probes by mechanical abrasion were performed. This conducts to propose an analytical methodology for corrosion product analyses on iron archaeological artefacts, using different characterisation techniques.

EXPERIMENTAL PROCEDURE Instrumentation

First, the optical microscope was used to study the metallographic structure of the iron core and to observe the morphology of the corrosion products. Then, composition analyses were performed on the samples by Energy Dispersive Spectroscopy (EDS) coupled to a Scanning Electron Microscope (SEM). The analyses were done under an accelerating voltage of 15 kV. The Si(Li) detector used was equipped with a thin beryllium window that allows to detect and quantify oxygen with a good accuracy (about 1% relative error on iron oxides standards). The EDS analyses performed here can not quantify light elements as carbon and gives only relative analyses. In the case of the presence of carbonates, composition analyses were done by Electron Probe MicroAnalysis (EPMA) which provides absolute composition data. EPMA was performed with a 2x2 μm² beam accelerated under 15 kV.

The local structure was determined by μXRD. These experiments were performed on the D15 beamline at the Laboratoire pour l'Utilisation du Rayonnement Synchrotron (LURE) at Orsay (France). The set-up was described elsewhere 12,15,16 . A microbeam of 20x20 μm² (λ = 0.08857 nm) was focused on thin films made from the cross sections. The advantage of this method is the disposability of reference spectra which are collected in the JCPDF databank. Meanwhile the access to the beamline is not easy and the sample preparation in thin sections (~ 30 μm) is delicate.

The μRaman was employed because it ensures a great facility of use. Measurements were performed at Laboratoire de Dynamique Interaction et Réactivité (LADIR) with a Notch-based spectrometer LabRam Infinity (Jobin Yvon-Horiba) using the radiation at 532 nm of a frequency-doubled Nd:YAG laser. Samples were observed under an Olympus microscope with Leitz objectives 10x, and long-focus 50x and 100x. With the 100x objective the diameter of the analysed area is about 3 μm. A Peltier-based cooled CCD records spectrum and the resolution given by the spectrometer setting is around 2 cm -1 . As some iron oxides, particularly magnetite, are highly sensitive to laser irradiation we use a set of six density filters to modulate the laser power on the sample from 5.2 mW to 5 μW. Acquisition and basic treatment of spectra are made with the LabSpec (Jobin Yvon-Horiba) software. The sample table is motorised which allows to collect profile and spectral cartography in automatic acquisition mode.

Methodology

Five French excavation sites were chosen because of their differences of dating and soil. From these sites about forty archaeological artefacts were studied (Table 1). In order to analyse the entire system constituted by the iron core and the burial environment, artefacts were collected with adhering soil. Samples were dried in an oven to withdraw the water and were mounted in epoxy resin.

As said before, two different preparation techniques were tested on the samples: Cross sections analyses Cross sections were cut into each of them. After polishing the samples with diamond paste (3 et 1 μm), all the techniques (especially μRaman) were used to locally determine the morphology, the composition and the structure of the corrosion products on the cross section. For each artefacts, the same cross section was used for all the techniques except for the X-ray microdiffraction which required a specific preparation: a cross section is cut in the artefact and polished until having a thickness of maximum 50 μm because the acquisitions are done in transmission mode.

Stratigraphic probe

This investigation method is applied to non-cut artefacts. Locally on the object, a mechanical abrasion is used to make a stratigraphic probing. It is then possible to collect μRaman spectra from these different zones.

Raman characterisation of iron oxides and oxyhydroxides

Various reference spectra are available in literature dealing with corrosion or mineralogy, for instance concerning iron oxides and oxy-hydroxides 17-28 and for carbonate 9,[29][30][31][32][START_REF] Bernard | Progress in Organic Coati 34[END_REF] . But, as no certified database of Raman spectra exists, we also acquire with our experimental set-up some spectra collected on commercial products or laboratory synthesised samples. A powder of goethite (α-FeOOH) has been synthesised by us following the instructions given by Schwertmann 34 and was controlled by X-Ray Diffraction by us. After synthesis, the composition analysis show that a low amount of K (several thousand ppm) remains in the FeOOH structure. This element, initially present in a product used for the synthesis (KOH solution), could be in insertion in the lattice. Nevertheless it have no detectable influence on the XRD spectra compared to the JCPDF reference. The μRaman spectrum is shown on Figure 1a. The main peak is localised at 388 cm -1 and other major peaks appear at 301, 416 and 685 cm -1 . This last one is larger than the peak generally mentioned on reference spectra in a previous paper [START_REF] Faria | Journal of Raman Spectroscopy 26[END_REF] . This could be due to the presence of potassium. The main peak has a Raman shift of 669 cm -1 . Two other peaks are located respectively at 308 and 542 cm -1 . Some laser power stability tests have been performed on magnetite which leads to the formation of haematite above a laser power threshold as shown in Figure 2. According to literature [START_REF] Faria | Journal of Raman Spectroscopy 26[END_REF] , magnetite can transform under heating conditions, first into maghemite at about 200°C and then haematite around 400°C. Thus, a moderate laser power must be routinely used for iron corrosion product analysis and when a maghemite (or haematite) spectrum is obtained, a checking experiment with lowest power and a longer acquisition time at a different location in the same phase must be performed to ensure whether the maghemite is real obtained rbitrary Units A Intensity / igure 2. Two spectra of the same magnetite reference F powder, a) 0.42 mW, b) 0.06 mW, cquisitions of 30 s Meanwhile, in some case it was not easy to discriminate the structure of some phases. For example, in this work the various carbonates were difficult to distinguish by μRaman. Indeed, in corrosion products, especially when iron and calcium are present it is sometimes impossible to attribute the main Raman shift of carbonate to siderite (FeCO3), calcite (CaCO3) or a mix of these two phases. The main peak for these phases is assigned respectively to 1084 cm -1 and 1088 cm -1 for siderite and calcite [START_REF] Bernard | Progress in Organic Coati 34[END_REF] . In fact the bending modes (minor peaks) are more sensitive than the ν1 symmetric mode to discriminate these two phase but, in our samples the relatively low phase crystallinity does not allow the observation of these peaks. Moreover solid solutions of these carbonates are not well documented. For example, a profile was collected on a zone where only siderite was identified by μXRD (it is important to note that, by this method, FeCO3 and CaCO3 can easily be discriminated). EDS analyses in the same zone show that this siderite can contain various amounts of Ca (from 1.5 to 2.3 mass%). Figure 3 shows the shift of the siderite main peak from 1084 to 1088 cm -1 on different spectra collected at several points of this zone. This illustrates the necessity, when e th detailed interpretation of Raman spectra is difficult, to use other complementary analytical techniques.

The last point to take into account when collecting Raman spectra, is the peak overlap. In the case of rrosion products, this phenomenon co p 1084 1088

Raman shift / cm

G

Figure 4 shows the difference of signal intensity for spectra collected in the same conditions on reference powders of these two phases. Peaks around 700 cm -1 are very close for these two phases. Moreover it is the main for magnetite. Thus, it can be difficult to clearly identify low quantity of magnetite in goethite. It is the same in the case of a small amount of magnetite in maghemite. These restrictions can be overcome by crossed use of complementary methods as μXRD.

As said before, μXRD was used to determine the structure of the corrosion products on archaeological samples. But, because this method is not so versatile, to increase the number of studied samples μRaman proved to be the easiest to use technique. The advantage of μXRD is the reference spectra that are available. But μRaman is eas to utili e, though it allows p samples.

RESULTS

Cross section analyses

Cross-sections made on archaeological artefacts can be described as follow from the metal to the soil (Figure 5 of minor elements and also slag inclusions coming from reduction stage 15,35 .

-A layer of corrosion products made of iron oxides, oxyhydroxides and/or carbonates. These phases are generally well crystallised and relatively compact. Thus this layer will be named "Dense Product Layer" (DPL). This DPL can contain internal markers (IM) as slag inclusions coming from the metallic substrate.

-A transition zone between the DPL and the non altered soil, containing both corrosion products and markers from the soil as quartz grain, considered as external markers. This zone will be called "transformed medium" (TM). The surface between the DPL and the TM corresponds to the old original surface (OS) of the object that has probably moved during the corrosion.

-The soil (S), where no corrosion products can be found.

the following, these abbreviatio In to describe the corrosion system.

Fe O / -Fe O mix It has first been observed that all the iron cores are hypoeutectoid steels 13 . Carbon excepted, the main minor element detected is phosphorous, that can be present until 0.5mass%. Carbon and phosphorous are in the most case heterogeneously distributed. The iron substrate contain also slag inclusions composed mainly of iron silicates and oxides. These slag inclusions are numerous in most of the substrate and contribute to the struct ral heterogeneity of the metal. Metallic substrates are comparable from one site to another.

The investigations realised on the corrosion products concern mainly the DPL i.e., the scales that appear relatively dense and homogeneous directly in contact with the metal and do not contain any quartz grain. Considering the DPL, the 38 analysed objects coming from five different sites can be ssified in two different types of corrosion forms.

The first one concerns the objects coming from the Cabaret, Avrilly and Montbaron sites and is schematised 5. It is the main corrosion form that is identifi d the objects f the corpus. The DPL are constituted by a phase that appears light dark under optical microscope. This phase is marbled by a fine light grey phase, which appears under the form of filaments. These filaments are numerous and constituted of magnetite and sometimes maghemite. The dark phase is identified as goethite. As an example, Figure 6 shows some Raman spectra of these different phases. Frequently some strips containing calcium are observed in the DPL. These phase The second type of corrosion form was only observed on the objects of the site of Glinet. As shown on the microphotograph of Figure 7, a layer composed of Ca-containing siderite is directly in contact with the metal. In these layers two types of fine strips appear regularly. The first one is grey light and is made of magnetite. The second type is composed of oxygen, iron, but also sulphur (until 17 mass%). Because of its very small size, the structure of this strip could not b d F igure 7. Typology F optical micrography and a Raman spectrum of the magnetite strip It is interesting to note that weather by μXRD or by μRaman it is more difficult to determine the structure of the phases constituting the TM. In this zone the only identified phases are goethite and haematite, but spectra show weak broad peaks contrary to the DPL where peaks are well defined linked to a different DPL.

Stratigraphic probe

A nail from the Glinet site, previously analysed by the cross section approach was studied by stratigraphic probe. As for the previous anal siderite, magnetite and calcite were detected by μRaman: it is a similar corrosion form than those who was established on the cross sections.

A second object coming from the medieval site of Saint-Denis was studied by this approach. Figure 8 described the corrosion system that was found on this object, following the terminology developed by Bertholon 11,12 to designate the different strata. Magnetite (or maghemite) were identified in strata CP2.CP1e and CP3.CP1i on both sides of the limit of the original surface. Goethite (α-FeOOH) was also identified in stratum CP3.CP2i which is now the core material due to the complete alteration of the metallic iron. μRaman analysis shows that the white material in CP3.D1i is a (Fe-Ca) carbonate which could have precipitated in previously formed cracks. As shown on the artefacts from Cabaret, Montbaron or Avrilly, it becomes more difficult to collect Raman spectra in the zone containing soil minerals, which seems to be less crystallised. The

DISCUSSION

On the objects of Glinet, it seems that the presence of siderite on one hand and of sulphur-containing phases on the other hand indicates that microbial corrosion has occurred. This hypothesis is reinforced by the fact that the zone where the objects were sampled is a waterlogged soil containing wood peaces that can provide organic matter. Meanwhile the presence of the magnetite strip in the siderite could be u d e to a change in the potential-pH conditions during the burial period.

The other corrosion form is the most common one characterised in this study. The presence of goethite in contact with the metal indicates that the burial conditions were always oxidant in the sites where such corrosion forms were found (Cabaret, Montbaron, Avrilly and Saint Denis). The presence of calcium-containing phases in the DPL of some of these objects shows that ions coming from the nearby environment can migrate into the corrosion products. This result is in agreement with the conclusion of Pons 9 who has shown that the layer in contact with the metal is relatively porous. Considering the TM, analyses indicate that iron precipitates mainly as oxyhydroxides. Moreover the fact that theses phases are not well crystallised could indicate that the crystal grains have no sufficient time to grow. It could be due to the presence of the water solution of the soil which could render soluble the iron corrosion products, transport the iron species by diffusion or convection. These last could precipitate again in a more oxidant zone farther from the iron core. This is a hypothesis to explain the iron migration from the object into the environment.

It seems that the same typology is identified on the Saint Denis artefact on which only stratigraphic probing was performed. This result shows the possibility of appraising corroded objects with a non destructive analytical method when a previous corrosion form is established. Thi lead u to a general methodology, that could be used in conservation to stu y and understand the corrosion forms and conduct to identify S1e CP1e CP2.CP1e

CP3.D1i

(Figure 9): 1. Stratigraphic probing of a statistical number of artefacts using μRaman to characterise the phases of the TM and DPL 2. If the identified corrosion form corresponds to classified corrosion form, a diagnostic is possibl leading to the delimitation of the corrosion system and particularly of the original surface limit. 3. If the identified corrosion form does not correspon to a classified one then it is necessary to perform complete characterisation of the system on cros sections and by using other methods as EDS, EPM and μXRD. This complete characterisation will lead to a new corrosion form and typology.

CP3.CP1i

CP3.CP2i

Figure 9. Analytical methodology to an co

CONCLUSION

The coupling between the results obtained by μRaman and μXRD allows us to ensure the identification of the corrosion products formed on about forty archaeological iron artefacts. It seems that the most frequent corrosion form observed on iron archaeological artefacts of the analysed corpus is forme mainly by goethite enclosing magnetite/maghemite strips. This form has been identified on objects coming from four sites with different soils composition. On these objects the migration of iron in the environment has been observed. An explanation of this phenomenon could be successive dissolution/precipitation transported by the solution of the soil.

Furthermore, it has been tested that when the corrosion typology is well establish, it will be possible to recognise corrosion forms on another artefacts only by performing a the stratigraphic approach, with the help of μRaman It ill be then easier to locate the original surface on these artefacts and ensure a reliable restoration of them. This lead us o propose a methodology for further studies a

Figure 1 .

 1 Figure 1. a) Goethite spectrum, long focus x100, laser power 0.21 mW, 600s x 2accumulations; b) Magnetit pectrum, long focus x100, laser power 0.06 mW, 1 h e

Figure 3 .

 3 Figure 3. Raman shift of the siderite versus the distance to the interface metal/corrosion products (Cacontain increasing from Raman shift / cm -1

Figure 4 .

 4 Figure 4. Comparison of the intensity of the spectra of e goethite and the magneti th 1800 s x 2 ac

  Figure 5. Main corros o

  characterisation. inally, some calcite aggregates were also identified. of the DPL of the objects of Glinet, and on the spectra. This fact could be formation mechanism than in the ysis on cross sections, corrosion products on this sample shows a form that is very similar to the first described in the previous part

Figure 6 .

 6 Figure 6. Morphology of the DPL with marbled aspect, optical micrography and Ra g thite, calcite magnetite (M) with magh mite (Mh), sample Mont4, Montbaron site

Figure 8 .

 8 Figure 8. Corrosion form observed on the Saint Denis rtefact after stratigraphic a μRaman analyse

  supported by ANDRA (French National Agency for Nuclear Waste Management) and the GDR 2114 of CNRS "Physico-Chimie M

Table 1 .

 1 Archaeological French sites where samples were taken

	Site	Dating	Location	Number of studied artefacts	Analytical approach
	Cabaret 12-13 th c. AD	Around Carcassonne (Aude)	15	Cross section
	Montbaron 12-13 th c. AD	Around Chateauroux (Indre et Loire)	6	Cross section
	Avrilly	15 th c. AD	Around Chartres (Eure)	8	Cross section
	Glinet	16 th c. AD	Around Rouen	8	Cross section
			(Seine Maritime)		Stratigraphic
					probing
	Saint-Denis	10-11 th c. AD	Around Paris	1	Stratigraphic probing

Acknowledgements

The authors would like to thank the archaeologists to allow them to work and sample the objects that they entrust to us: Marie-Elise Gardel (Cabaret), Armelle Querrien (Montbaron), Bérengère Lecain (Avrilly), anielle Arribet (Glinet). des atériaux du Patrimoine Culturel" (CHIMART)