PHAN TH ÀNH Mathieu Lewin
email: mathieu.lewin@math.cnrs.fr

Nicolas Rougerie
email: nicolas.rougerie@grenoble.cnrs.fr

BOSE GASES AT POSITIVE TEMPERATURE AND NON-LINEAR GIBBS MEASURES

We summarize recent results on positive temperature equilibrium states of large bosonic systems. The emphasis will be on the connection between bosonic grandcanonical thermal states and the (semi-) classical Gibbs measures on one-body quantum states built using the corresponding mean-field energy functionals. An illustrative comparison with the case of "distinguishable" particles (boltzons) is provided.

Contents

1. Bose Einstein condensation in trapped atomic gases 1 2. From bosonic grand-canonical Gibbs states to non-linear Gibbs measures 2 2.1. Setting 2 2.2. Non-linear Gibbs measures 4 2.3. Mean-field/large temperature limit 5 3. The case of boltzons: derivation of a mean-field free energy functional 6 Appendix A. Boltzons at positive temperature, proof of Theorem 3.1 8 References 10

1. Bose Einstein condensation in trapped atomic gases

. Twenty years after this achievement, many important questions raised by the experiments remain unresolved, in particular as regards the rigorous derivation of BEC from the first principles of quantum mechanics, i.e. the many-body Schrödinger equation.

Full Bose-Einstein condensation is the phenomenon that, below a certain critical temperature T c , (almost) all particles of a bosonic system must reside in a single quantum state of low energy. Ideally one would like to prove the existence of such a temperature and provide an estimate thereof. For an interacting gas this has so far remained out of reach. In particular, for the homogeneous Bose gas, there is still no proof of Bose-Einstein condensation in the thermodynamic limit, even in the ground state. However, this might not be the main question of interest for the description of cold atoms experiments. Indeed, those are performed in magneto-optic traps, which set a fixed length scale to the problem.

The gases in which BEC is observed are thus not homogeneous, and the thermodynamic limit is not the most physically relevant regime in this context.

A lot of progress has been achieved in recent years by considering different scaling regimes, more adapted to the case of inhomogeneous systems, e.g. the mean-field and the Gross-Pitaevskii limits. For trapped systems, BEC in the ground state and its propagation by the many-body Schrödinger equation is now fairly well understood (see [START_REF] Benedikter | Effective Evolution Equations from Quantum Dynamics[END_REF][START_REF] Golse | On the Dynamics of Large Particle Systems in the Mean Field Limit[END_REF][START_REF] Lewin | Mean-Field limit of Bose systems: rigorous results[END_REF][START_REF] Lieb | The mathematics of the Bose gas and its condensation[END_REF][START_REF] Rougerie | De Finetti theorems, mean-field limits and Bose-Einstein condensation[END_REF][START_REF] De De Finetti | limites de champ moyen et condensation de Bose-Einstein[END_REF][START_REF] Schlein | Derivation of effective evolution equations from microscopic quantum dynamics[END_REF][START_REF] Seiringer | Hot topics in cold gases[END_REF] for reviews). Even in these somewhat more wieldy regimes, very little is known about positive temperature equilibrium states. In particular, an estimate of the critical temperature (or, more generally, temperature regime) is lacking.

In this note, we discuss some of our recent results [START_REF] Lewin | Derivation of nonlinear Gibbs measures from many-body quantum mechanics[END_REF], in the perspective of the previously mentioned issues. The main idea is to relate, in a certain limit, Gibbs states of large bosonic systems to non-linear Gibbs measures built on the associated mean-field functionals. This is a semi-classical method, where the BEC phenomenon can be recast in the context of a classical field theory. Although, as far as the study of BEC is concerned, our results are rather partial, it is our hope that our methods might in the future help to shed some light on the physics we just discussed. We shall compare the new results to what can be proved in the case of "boltzons", i.e. particles with no imposed symmetry, in order to illustrate the crucial importance of Bose statistics in this problem.

We refer to [START_REF]From bosonic grand-canonical ensembles to nonlinear Gibbs measures[END_REF] for another look at the main results of [START_REF] Lewin | Derivation of nonlinear Gibbs measures from many-body quantum mechanics[END_REF], with an emphasis on their relation to constructive quantum field theory [START_REF] Dereziński | Mathematics of Quantization and Quantum Fields[END_REF][START_REF] Glimm | Quantum Physics: A Functional Integral Point of View[END_REF][START_REF] Lörinczi | Feynman-Kac-Type Theorems and Gibbs Measures on Path Space: With Applications to Rigorous Quantum Field Theory[END_REF][START_REF] Simon | The P (ϕ)2 Euclidean (quantum) field theory[END_REF][START_REF] Summers | A Perspective on Constructive Quantum Field Theory[END_REF][START_REF]Constructive quantum field theory: The 1973 Ettore Majorana international school of mathematical physics[END_REF] and the use of invariant measures in the study of non-linear dispersive partial differential equations [START_REF] Lebowitz | Statistical mechanics of the nonlinear Schrödinger equation[END_REF][START_REF] Bourgain | Periodic nonlinear Schrödinger equation and invariant measures[END_REF][START_REF]Invariant measures for the 2d-defocusing nonlinear Schrödinger equation[END_REF][START_REF]Invariant measures for the Gross-Pitaevskii equation[END_REF][START_REF] Tzvetkov | Invariant measures for the defocusing nonlinear Schrödinger equation[END_REF][START_REF] Burq | Random data Cauchy theory for supercritical wave equations. I. Local theory[END_REF][START_REF] Burq | Long time dynamics for the one dimensional non linear Schrödinger equation[END_REF][START_REF] Thomann | Gibbs measure for the periodic derivative nonlinear Schrödinger equation[END_REF][START_REF] Cacciafesta | Invariant measure for the Schrödinger equation on the real line[END_REF].

2.

From bosonic grand-canonical Gibbs states to non-linear Gibbs measures 2.1. Setting. We consider N bosons living in R d and work in the grand-canonical ensemble. Let thus H = L 2 (R d ),

H N = N sym H ≃ L 2 sym (R N d )
be the symmetric N -fold tensor product appropriate for bosons and

F = C ⊕ H ⊕ H 2 ⊕ . . . ⊕ H N ⊕ . . . F = C ⊕ L 2 (R d ) ⊕ L 2 s (R 2d ) ⊕ . . . ⊕ L 2 s (R N d ) ⊕ .
. . be the bosonic Fock space. We are interested in the positive temperature equilibrium states of the second-quantized Hamiltonian H λ defined as

H λ = H 0 + λW = ∞ n=1 H n,λ , with H 0 = ∞ n=1   n j=1 h j   = ∞ n=1   n j=1 -∆ j + V (x j ) -ν   W = ∞ n=2   1 i<j n w ij   .
Here ν is a chemical potential, V is a trapping potential, i.e.

V (x) → +∞ when |x| → ∞ and w is a positive, symmetric, self-adjoint operator on H 2 . The methods of [START_REF] Lewin | Derivation of nonlinear Gibbs measures from many-body quantum mechanics[END_REF] are limited to rather smooth repulsive interactions, thus w will in general not be a multiplication operator. We shall comment on this issue below but, for the time being, think of a finiterank w with smooth eigenvectors, corresponding to a regularization of a physical interaction.

We are interested in the asymptotic behavior of the grand-canonical Gibbs state at temperature T

Γ λ,T = 1 Z λ (T ) exp - 1 T H λ . (2.1)
The partition function Z λ (T ) fixes the trace equal to 1 and satisfies

-T log Z λ (T ) = F λ (T ) (2.2)
where F λ (T ) is the infimum of the free energy functional

F λ [Γ] = Tr F [H λ Γ] + T Tr F [Γ log Γ] (2.3)
over all grand-canonical states (trace-class self-adjoint operators on F with trace 1). It turns out that an interesting limiting behavior emerges in the regime

T → ∞, λ = 1 T , ν fixed, (2.4)
provided one makes the following assumptions:

Assumptions 2.1 (One-body hamiltonian). We assume that, as an operator on H = L 2 (R d ),

h := -∆ + V -ν > 0
and that there exists p > 0 such that

Tr H h -p < ∞. (2.5)
Note that one can always find a p such that (2.5) holds. The easiest case, for which our results are the most satisfying, is that where one can take p = 1 (refered to as the trace-class case). This happens only in 1D and if the trapping potential grows sufficiently fast at infinity, i.e.

h = - d 2 dx 2 + |x| a -ν (2.6)
with ν small enough and a > 2.

Assumptions 2.2 (Interaction term).

We pick w a positive self-adjoint operator on H 2 and distinguish two cases:

• either one can take p = 1 in (2.5) and then we assume

Tr H 2 w h -1 ⊗ h -1 < ∞ (2.7)
• or p > 1 in (2.5) and we make the stronger assumption that

0 w h 1-p ′ ⊗ h 1-p ′ (2.8)
for some p ′ > p.

In essence, these (rather restrictive) asumptions correspond to asking that the noninteracting Gibbs state has a well-controled interaction energy. Indeed, one can compute that its two-body density matrix behaves as T 2 h -1 ⊗ h -1 in the limit T → ∞. In the 1D case (2.6) where p = 1, we can take for example w a multiplication operator, e.g. by a bounded function w(x -y). The assumption we make when p > 1 does not cover such operators.

2.2. Non-linear Gibbs measures. The natural limiting object in the setting we just described turns out to be the non-linear Gibbs measure on one-body quantum states given formally by

dµ(u) = 1 Z e -E[u] du, (2.9)
where Z is a partition function and E[u] is the mean-field energy functional

E[u] := u| -∆ + V -ν|u H + 1 2 u ⊗ u|w|u ⊗ u H 2 .
(2.10)

The rigorous meaning of (2.9) is given by the two following standard lemmas/definitions:

Lemma 2.3 (Free Gibbs measure). Write h = -∆ + V -ν = ∞ j=1 λ j |u j u j |
and define the asociated scale of Sobolev-like spaces

H s := D(h s/2 ) = u = j 1 α j u j : u 2 H s := j 1 λ s j |α j | 2 < ∞ . (2.

11)

Define a finite dimensional measure on span(u 1 , . . . , u K ) by setting

dµ K 0 (u) := K j=1 λ j π exp -λ j | u, u j | 2 d u, u j
where d u, u j = da j db j and a j , b j are the real and imaginary parts of the scalar product. Let p > 0 be such that (2.5) holds. Then there exists a unique measure µ 0 over the space H 1-p such that, for all K > 0, the above finite dimensional measure µ 0,K is the cylindrical projection of µ 0 on span(u 1 , . . . , u K ). Moreover

γ (k) 0 := H 1-p |u ⊗k u ⊗k | dµ 0 (u) = k! (h -1 ) ⊗k (2.12)
where this is seen as an operator acting on k sym H. Note that the free Gibbs measure never lives on the energy space H 1 . It lives on the original Hilbert space H 0 = H if and only if (2.5) holds with p = 1. We can now define the interacting Gibbs measure as being absolutely continuous with respect to the free Gibbs measure:

Lemma 2.4 (Interacting Gibbs measure). Let F NL [u] := 1 2 u ⊗ u|w|u ⊗ u H 2 . If Assumptions 2.2 hold we have that u → F NL [u] is in L 1 (H 1-p , dµ 0 ). In particular µ(du) = 1 Z r exp (-F NL [u]) µ 0 (du) (2.13)
makes sense as a probability measure over H 1-p . That is, the relative partition function satisfies

Z r = exp (-F NL [u]) µ 0 (du) > 0.
Equation (2.13) is the correct interpretation of the formal definition (2.9). It is this object that we derive from the bosonic grand-canonical Gibbs state.

2.3. Mean-field/large temperature limit. Our main result in [START_REF] Lewin | Derivation of nonlinear Gibbs measures from many-body quantum mechanics[END_REF] relates, in the limit (2.4), the grand-canonical Gibbs state (2.1) to the classical Gibbs measure on one-body state defined in Lemma 2.4: Theorem 2.5 (Derivation of nonlinear Gibbs measures). Under Assumptions 2.1 and 2.2 we have

F λ (T ) -F 0 (T ) T -→ T →∞ -log Z r
where F λ (T ) is the infimum of the free-energy functional (2.3) and Z r the relative partition function defined in Lemma 2.4. Let furthermore Γ (k) λ,T be the reduced k-body density matrix of Γ λ,T . We have,

Γ (1) λ,T T -→ T →∞ H 1-p |u u| dµ(u) (2.14)
strongly in the Schatten space S p (H). In case p = 1 in (2.5) we also have, for any k 2,

k! T k Γ (k) λ,T -→ T →∞ H |u ⊗k u ⊗k | dµ(u) (2.15)
strongly in the trace-class.

An obvious caveat of our approach is the case p > 1 where the result is not as strong as one would hope. We conjecture that (2.15) continues to hold strongly in the Schatten space S p (H) also for k > 1, but this remains an open problem. More importantly, it would be highly desirable to go beyond the stringent assumption (2.8). There are however wellknown obstructions to the construction of the Gibbs measure µ in this case. A minima, a Wick renormalization [START_REF] Glimm | Quantum Physics: A Functional Integral Point of View[END_REF][START_REF] Simon | The P (ϕ)2 Euclidean (quantum) field theory[END_REF] must be performed in order to make sense of the measure when w = w(x -y) is a multiplication operator. The derivation from many-body quantum mechanics of the so-defined measure is the subject of ongoing work by the authors.

We refer to [START_REF] Lewin | Derivation of nonlinear Gibbs measures from many-body quantum mechanics[END_REF][START_REF]From bosonic grand-canonical ensembles to nonlinear Gibbs measures[END_REF] for additional comments. Here, let us only discuss the relevance of this result to the BEC phenomenon:

• First, this theorem seems to be the first giving detailed information on the limit of the thermal states of a Bose system at relatively large temperature. The result (2.14) clearly shows the absence of full BEC in the regime we consider. For finite dimensional bosons, things simplify a lot and versions of Theorem 2.5 were known before, see [START_REF] Gottlieb | Examples of bosonic de Finetti states over finite dimensional Hilbert spaces[END_REF] and [START_REF] Rougerie | De Finetti theorems, mean-field limits and Bose-Einstein condensation[END_REF]Appendix B].

• The asymptotic regime (2.4) should be thought of as a mean-field limit. In fact, when p = 1, (2.14) indicates that the expected particle number behaves as O(T ), so that taking λ = T -1 corresponds to the usual mean-field scaling where the coupling constant scales as the inverse of the particle number. Roughly speaking we are thus dealing with the regime

N → ∞, λ = 1 N , T ∼ N.
• Still in the case p = 1, one should expect from a natural extrapolation of this theorem that full BEC does occur in the regime

N → ∞, λ = 1 N , T ≪ N
which would indicate that the critical temperature scales in this case as the particle number. A natural idea would be to confirm this by studying the concentration of the non-linear Gibbs measure µ on the mean-field minimizer when the chemical potential is varied.

The case of boltzons: derivation of a mean-field free energy functional

We now change gears and consider, for comparison, the situation where the quantum statistics of the particles is ignored. In this case, we can work in the canonical ensemble, and this is what we shall do here. Let thus H = L 2 (R d ) and

H N = N L 2 (R d ) ≃ L 2 (R dN )
be the N -body Hilbert space for N distinguishable particles. We consider the N -body free-energy functional at temperature T

F N,T [Γ N ] := Tr H N [H N Γ N ] + T Tr H N [Γ N log Γ N ] (3.1)
where, to fix ideas, we take

H N := N j=1 (-∆ j + V (x j )) + λ N -1 1 i<j N w ij . (3.2)
We make standard asssumptions ensuring that this can be realized as a self-adjoint operator, e.g. that w = w(x -y) is a multiplication operator by a radial function decaying at infinity

w ∈ L p + L ∞ with max(1, d/2) < p < ∞.
We consider the case of a (say smooth) trapping potential V (x) → ∞ when |x| → ∞, so that -∆ + V has compact resolvent. In (3.1) Γ N is a N -body state, that is a trace-class self-adjoint operator on H N with trace 1. For a Hamiltonian such as (3.2) it is well-known [START_REF] Lieb | The Stability of Matter in Quantum Mechanics[END_REF]Chapter 3] that the minimizer at T = 0 is bosonic, i.e.

U σ Γ N = Γ N U σ = Γ N (3.3)
for any permutation σ of N indices, where U σ is the associated unitary operator on H N :

(U σ Ψ N ) (x 1 , . . . , x N ) = Ψ N (x σ(1) , . . . , x σ(N ) ).
This is no longer true at positive temperature, and in fact we are going to see that in this case, unrestricted minimizers are not bosonic.

Due to the symetry of H N , the minimizer of (3.1), i.e. the Gibbs state

Γ N,T = exp -T -1 H N Tr H N [exp (-T -1 H N )] (3.4) satisfies however U σ Γ N U * σ = Γ N (3.
5) for any permutation, and we shall make use of this fact.

Since we do not impose any stronger symmetry, a state of the form Γ N = γ ⊗N is admissible for any one-body state γ. Taking such an ansatz leads to a mean-field free energy functional

F mf [γ] = Tr H [(-∆ + V )γ] + λ 2 Tr H 2 w γ ⊗2 + T Tr H [γ log γ] . (3.6)
Note that the state γ ⊗N always satisfies (3.5), but not (3.3) (see e.g. [START_REF] Hudson | Locally normal symmetric states and an analogue of de Finetti's theorem[END_REF]Proposition 3]) unless γ = |ψ ψ| is pure. For the bosonic problem, the entropy term in the mean-field functional would thus be 0 for any admissible trial state. We denote F mf the infimum of F mf over one-body mixed states and γ mf the minimizer:

F mf := inf F mf [γ], γ ∈ S 1 (H), γ = γ * , γ 0, Tr H γ = 1 = F mf [γ mf ]. (3.7)
Note that γ mf is unique by strict convexity of the functional, and that for T = 0 one can easily realize that it must be mixed, i.e not a projector, so that

Tr H [γ mf log γ mf ] < 0.
One can in fact show that the above mean-field functional correctly describes particles with no symmetry in a mean-field limit, with fixed temperature T :

Theorem 3.1 (Mean-field limit for boltzons at finite temperature).

Let Γ N,T be the unrestricted Gibbs state minimizing (3.6) and

F N,T = -T log Tr H N exp -T -1 H N
the associated free-energy. Define, via a partial trace 1 , Γ

N,T = Tr k+1→N Γ N,T the k-body density matrix of Γ N,T . Then, for any fixed λ and T we have

F N,T N -→ N →∞ F mf (3.8)
and

Γ (k) N,T -→ N →∞ γ ⊗k mf (3.9)
strongly in the trace-class.

Results in this spirit can be found in [START_REF] Fannes | Equilibrium states for mean field models[END_REF][START_REF] Petz | Asymptotics of Varadhan-type and the Gibbs variational principle[END_REF][START_REF] Raggio | Quantum statistical mechanics of general mean field systems[END_REF][START_REF] Werner | Large deviations and mean-field quantum systems[END_REF]. A proof is presented in Appendix A for completeness. As far as BEC is concerned, the above theorem is mainly interesting in as much as it helps emphasizing the role of Bose statistics at positive temperature 2 :

1 Remark the normalization: Γ (k) N,T has trace 1. 2 In much the same way as the study of "bosonic atoms" illustrates the role of the Pauli principle in true atoms [START_REF] Benguria | Proof of the Stability of Highly Negative Ions in the Absence of the Pauli Principle[END_REF].

• First, the above theorem indicates that the emergence of the non-linear Gibbs measure discussed previously truly requires Bose statistics. • Since at fixed T = 0, the minimizer of (3.6) is mixed, full BEC does not occur for a trapped boltzonic system in the mean-field limit N → ∞, T fixed. In the same regime, bosons do show BEC [START_REF] Sütő | Thermodynamic limit and proof of condensation for trapped bosons[END_REF] and the temperature has in fact no effect at leading order [21, Section 3.2]. • Thus, for trapped boltzons, we see that the critical temperature scales as O(1) when N → ∞ in the mean-field regime. Only when T → 0 at the same time as N → ∞ does full BEC occur in the Gibbs state. • The occurence of BEC for boltzons in this limit is in fact a trivial question of (free) energy balance, very different from the statistical effect that leads to BEC for bosons. • As a consequence, one should expect that the critical temperature is much higher for bosons than for boltzons. This can be seen from comparing the above theorem and [38, 21, Section 3.2]: T boltzons c ∼ 1 in the mean-field limit whereas T bosons c ≫ 1. • In fact, from the results of [START_REF] Lewin | Derivation of nonlinear Gibbs measures from many-body quantum mechanics[END_REF] we previously discussed, we see that in some situations the critical temperature for bosons could be as high as O(N ), much larger as that one obtains by neglecting statistics.

where C T,λ,k does not depend on N . Since -∆ + V has compact resolvent we deduce that in fact Γ

N,T → γ (k) strongly in the trace-class, and thus

Tr H k γ (k) = 1 Tr k+1 γ (k+1) = γ (k) (A.3)
where Tr k+1 denotes a partial trace with respect to one variable. One may thus apply the quantum de Finetti theorem of Størmer-Hudson-Moody [START_REF] Størmer | Symmetric states of infinite tensor products of C * -algebras[END_REF][START_REF] Hudson | Locally normal symmetric states and an analogue of de Finetti's theorem[END_REF] (see also [START_REF] Rougerie | De Finetti theorems, mean-field limits and Bose-Einstein condensation[END_REF]Section 3.4] and [START_REF] Lewin | Derivation of Hartree's theory for generic mean-field Bose gases[END_REF]Remark 5.3]). This yields a unique Borel probability measure µ over the set

S(H) = γ ∈ S 1 (H), γ = γ * , Tr γ = 1
of one-body mixed states such that, for any k 0,

γ (k) = S γ ⊗k dµ(γ). (A.4)
One can easily pass to the liminf in the energy terms of (3.6), following [21, Section 3], and obtain lim inf

N →∞ N -1 Tr H N [H N Γ N,T ] lim inf N →∞ Tr H (-∆ + V )Γ (1)
N,T + λ 2 Tr H 2 w Γ (2) N,T Tr H (-∆ + V )γ (1) + λ 2 Tr H 2 w γ (2) = S Tr H [(-∆ + V )γ] + λ 2 Tr H 2 w γ ⊗2 dµ(γ). (A.5)
For the entropy term, we first use subadditivity of the entropy to write, for any k 0

Tr H N [Γ N,T log Γ N,T ] N k Tr H k Γ (k) N,T log Γ (k) N,T + Tr H m Γ (m) N,T log Γ (m) N,T (A.6)
where (Euclidean division)

N = k N k + m with m < k.
Next, setting γ 0 = c 0 exp(-∆ + V ) with c 0 a normalization constant we use the positivity of the relative entropy to get

Tr H m Γ (m) N,T log Γ (m) N,T = Tr H m Γ (m) N,T log Γ (m) N,T -γ ⊗m 0 + Tr H m Γ (m) N,T log γ ⊗m 0 Tr H m Γ (m) N,T log γ ⊗m 0 .
Using (A.2) we find that this is bounded below independently of N . Thus, returning to (A.6), one can pass first to the liminf in N and then to the sup in k to get lim inf

N →∞ N -1 Tr H N [Γ N,T log Γ N,T ] sup k∈N 1 k Tr H k γ (k) log γ (k) . (A.7)
We then invoke a quantum analogue of a result of [START_REF] Robinson | Mean entropy of states in classical statistical mechanics[END_REF]:

Lemma A.1 (The mean entropy is affine). Let γ (k) k∈N be a sequence of k-body states satisfying (A.3). Then the mean entropy defined by

-sup k∈N 1 k Tr H k γ (k) log γ (k) = -lim k→∞ 1 k Tr H k γ (k) log γ (k)
is an affine function of γ (k) k∈N . Proof. That the limit exists and coïncides with the sup is a consequence of subadditivity of the entropy. Take now two sequences γ

(k) 1 k∈N , γ (k) 2 k∈N
and define

γ (k) = 1 2 γ (k) 1 + 1 2 γ (k)
2 . We clearly have, by concavity of the entropy

Tr H k γ (k) log γ (k) 1 2 Tr H k γ (k) 1 log γ (k) 1 + 1 2 Tr H k γ (k) 2 log γ (k) 2
.

On the other hand, the log being operator monotone, we get -log 2.

Tr H k γ (k) log γ (k) = 1 2 Tr H k γ (k) 1 1/2 log γ (k) γ (k) 1 1/2 + 1 2 Tr H k γ (k) 2 1/2 log γ (k) γ (k) 2 1/2
Dividing the previous inequalities by k and passing to the limit gives upper and lower bounds establishing that the limit functional is affine.

Combining (A.5), (A.7), inserting the de Finetti representation (A.4) and using the above lemma we get lim inf

N →∞ N -1 F N,T [Γ N,T ] S F mf [γ]dµ(γ) F mf
because µ is a probability measure. This is the desired lower bound and thus (3.8) is proved. The convergence of states (3.9) follows by combining with (A.1): the measure µ must be concentrated on the unique minimizer of F mf .

Acknowledgment. The research summarized here has received funding from the European Research Council (ERC Grant Agreement MNIQS 258023), the People Programme / Marie Curie Actions (REA Grant Agreement 291734) and from the ANR (Projects NoNAP ANR-10-BLAN-0101 & Mathostaq ANR-13-JS01-0005-01).

Appendix A. Boltzons at positive temperature, proof of Theorem 3.1

Here we briefly sketch a proof of Theorem 3.1 inspired by the method introduced in [START_REF] Messer | Statistical mechanics of the isothermal Lane-Emden equation[END_REF] for classical mean-field limits. We denote

the von Neumann entropy. We shall use some of its well-known properties for which we refer to [START_REF] Carlen | Trace inequalities and quantum entropy: an introductory course[END_REF][START_REF] Ohya | Quantum entropy and its use[END_REF]. As noted in the main text, γ ⊗N is an admissible trial state, and since

we clearly get the inequality

by the variational principle. We turn to the proof of a matching free energy lower bound. Passing to a diagonal subsequence we may assume that as N → ∞ and for any k 0,

in the trace-class. It is easy to obtain the a priori bound


Loris Marchal
email: loris.marchal@ens-lyon.fr

Bertrand Simon
email: bertrand.simon@ens-lyon.fr

Oliver Sinnen
email: o.sinnen@auckland.ac.nz

Frédéric Vivien
email: frederic.vivien@inria.fr

‡ Oliver Sinnen

Malleable task-graph scheduling with a practical speed-up model

Keywords: Scheduling, Task graph, Malleable tasks, Approximation algorithms Ordonnancement, Graphe de tâches, Tâche malléable, Algorithmes d'approximation

Scientific workloads are often described by Directed Acyclic task Graphs. Indeed, DAGs represent both a model frequently studied in theoretical literature and the structure employed by dynamic runtime schedulers to handle HPC applications. A natural problem is then to compute a makespan-minimizing schedule of a given graph. In this paper, we are motivated by task graphs arising from multifrontal factorizations of sparse matrices and therefore work under the following practical model. We focus on malleable tasks (i.e., a single task can be allotted a time-varying number of processors) and specifically on a simple yet realistic speedup model: each task can be perfectly parallelized, but only up to a limited number of processors. We first prove that the associated decision problem of minimizing the makespan is NP-Complete. Then, we study a widely used algorithm, Prop-Scheduling, under this practical model and propose a new strategy GreedyFilling. Even though both strategies are 2-approximations, experiments on real and synthetic data sets show that GreedyFilling achieves significantly lower makespans.

Ordonnancement de Graphes de Tâches Malléables avec un modèle pragmatique

Résumé :

Les applications de calcul scientifique sont souvent décrites comme des graphes de tâches dirigés et acycliques. En effet, ces graphes représentent à la fois un modèle étudié fréquemment dans la littérature théorique ainsi qu'une structure employée par les ordonnanceurs dynamiques de runtime pour traiter des applications HPC. Un problème naturel consiste donc à calculer un ordonnancement d'un graphe donné minimisant le temps d'exécution. Dans ce rapport, nous nous concentrons sur des graphes de tâches provenant de factorisations multifrontales de matrices creuses et travaillons donc dans le modèle pragmatique suivant. Nous étudions les tâches malléables (i.e., une tâche peut être allouée à un nombre variant de processeurs) et plus précisément un modèle d'accélération simple mais réaliste: chaque tâche peut être parallélisée parfaitement, mais seulement jusqu'à un nombre limite de processeurs. Nous commenons par prouver que le problème de décision associé à la minimisation du makespan est NP-complet. Ensuite, nous étudions sous notre modèle un algorithme largement répandu, PropScheduling, et proposons une nouvelle stratégie, GreedyFilling. Même si ces deux stratégies sont des 2-approximations, des expériences sur des bases de données réelles et artificielles montrent que GreedyFilling atteint des makespans significativement plus courts.

Introduction

Complex computations are often described as Directed Acyclic Graphs (DAGs), where nodes represent computational tasks and edges represent dependences between these tasks. This formalism is both very common in the theoretical scheduling literature [START_REF] Drozdowski | Scheduling parallel tasks -algorithms and complexity[END_REF] and sees an increasing interest in High Performance Computing: to cope with the complexity and heterogeneity in modern computer design, many HPC applications are now expressed as task graphs and rely on dynamic runtime schedulers such as StarPU [START_REF] Augonnet | StarPU: a unified platform for task scheduling on heterogeneous multicore architectures[END_REF], KAAPI [START_REF] Gautier | KAAPI: A thread scheduling runtime system for data flow computations on cluster of multi-processors[END_REF], StarSS [START_REF] Planas | Hierarchical taskbased programming with StarSs[END_REF], and PaRSEC [START_REF] Bosilca | PaRSEC: Exploiting heterogeneity for enhancing scalability[END_REF]. Even the OpenMP standard now includes DAG scheduling constructs [START_REF]OpenMP Architecture Review Board: OpenMP application program interface[END_REF].

Task graphs are helpful to express the structure of applications and to take advantage of the potential parallelism they express, sometimes called inter-task parallelism. However, tasks are often coarse grain and each task can be executed in parallel on several processing cores. To achieve good performance, we also want to take into account this intra-task parallelism.

There have been a number of studies to mix both sources of parallelism when scheduling task graphs, such as [START_REF] Radulescu | CPR: mixed task and data parallel scheduling for distributed systems[END_REF][START_REF] Dutot | Scheduling parallel task graphs on (almost) homogeneous multicluster platforms[END_REF]. The main difficulty in this context is to come up with an expressive and yet tractable model for tasks. Task characteristics are summarized through a speed-up function that relates the task execution time to the number of processors it is allocated to. In the present paper, we focus on a simple model where the speedup function is perfect -that is, equal to the number of processor-until it reaches a given threshold, after which it stalls and stays constant. This speedup function models well the performance of linear algebra kernels which are our present concern, and it has been studied both in theoretical scheduling [START_REF] Drozdowski | Scheduling parallel tasks with sequential heads and tails[END_REF] and for practical schedulers [START_REF] Nagarajan | Flowflex: Malleable scheduling for flows of mapreduce jobs[END_REF][START_REF] Sbîrlea | Elastic tasks: Unifying task parallelism and SPMD parallelism with an adaptive runtime[END_REF]. Contrarily to most existing studies, we also assume that tasks are preemptible (a task may be interrupted and resumed later), malleable (the number of processors allocated to a task can vary over time) and we allow fractional allocation of processors. We claim that this model is reasonable firstly because changing allocation of processors is easily achieved using the time sharing facilities of operating system schedulers or hypervisors: actual runtime schedulers are able to dynamically change the allocation of a task [START_REF] Hugo | Composing multiple StarPU applications over heterogeneous machines: A supervised approach[END_REF]. Secondly, given preemption and malleability, it is possible to transform any schedule with rational allocation to a schedule with integral allocation using McNaughton's wrap-around rule [START_REF] Mcnaughton | Scheduling with deadlines and loss functions[END_REF]. Hence, we can consider rational allocations that are simple to design and analyze, and then transform them into integral ones when needed.

The here presented study is motivated and driven by task graphs coming from sparse linear algebra, and especially from the factorization of sparse matrices using the multifrontal method. Liu [START_REF] Liu | The role of elimination trees in sparse factorization[END_REF] explains that the computational dependencies and requirements in Cholesky and LU factorization of sparse matrices using the multifrontal method can be modeled as a task tree, called the assembly tree. Our target are therefore such trees and the experimental evaluation will focus on them. Having that said, the proposed algorithms in this paper are not limited to trees, but apply to series-parallel graphs (SP-graphs) or general DAGs. We will describe and analyse them correspondingly for the sake of generality.

The contributions of this paper are the following. We apply the perfect but limited speedup model to scheduling graphs with malleable tasks. We first show that this problem is NP-complete. We analyse an allocation scheme called Proportional Mapping which is commonly used by runtime schedulers and show that it is a 2-approximation algorithm with tight ratio. We propose and analyse a simple greedy scheduler, called Greedy-Filling, and prove that it also is a 2-approximation algorithm. We perform simulations both on synthetic series-parallel graphs and on real task trees and show that the Greedy-Filling heuristic usually performs better than Proportional Mapping.

Related Work

In this section, we thoroughly review the related work on malleable task graph scheduling for models of tasks that are close or similar to our model. We also present some basic resuts on series-parallel graphs.

Models of parallel tasks. The literature contain numerous models for "parallel tasks"; names and notations are varying and their usage is not always consistent. The most simple model for parallel tasks is the model of rigid tasks, sometimes simply called parallel tasks [START_REF] Günther | Scheduling and packing malleable and parallel tasks with precedence constraints of bounded width[END_REF]. A rigid task must always be executed on the same number of processors (that must be simultaneously available). In the model of moldable tasks, the scheduler has the freedom to chose on which number of processors to run a task, but this number cannot change during the execution. This model is sometimes called multiprocessor tasks [START_REF] Drozdowski | Scheduling multiprocessor tasks -an overview[END_REF]. The most general model is that of malleable tasks: the number of processors executing a task can change in any way at any time throughout the task execution. However, numerous articles use the name malleable to denote moldable tasks like, for instance, [START_REF] Günther | Scheduling and packing malleable and parallel tasks with precedence constraints of bounded width[END_REF][START_REF] Lepère | Approximation algorithms for scheduling malleable tasks under precedence constraints[END_REF][START_REF] Jansen | An approximation algorithm for scheduling malleable tasks under general precedence constraints[END_REF]. Depending on the variants, moldable and malleable tasks can run on any number of processors, from 1 to p, or each task T i may have a maximum parallelism which is often denoted by δ i [START_REF] Drozdowski | Scheduling multiprocessor tasks -an overview[END_REF][START_REF] Beaumont | Minimizing weighted mean completion time for malleable tasks scheduling[END_REF].Furthermore, depending on the assumptions, tasks may be preempted to be restarted later on the same set of processors, or on a potentially different ones (preemption+migration). It should be noted that the model of malleable tasks is a generalization of the model of moldable tasks with preemption and migration.

An important feature of the models for moldable and malleable tasks is the task speed-up functions that relate a task execution time to the number of processors it uses. Some authors, like Hunold [START_REF] Hunold | One step toward bridging the gap between theory and practice in moldable task scheduling with precedence constraints[END_REF], do not make any assumptions on the speed-up functions. More generally, people assume the task execution time is a non-increasing function of the number of processors [START_REF] Hunold | One step toward bridging the gap between theory and practice in moldable task scheduling with precedence constraints[END_REF][START_REF] Lepère | Approximation algorithms for scheduling malleable tasks under precedence constraints[END_REF][START_REF] Makarychev | Precedence-constrained scheduling of malleable jobs with preemption[END_REF][START_REF] Fan | An effective approximation algorithm for the malleable parallel task scheduling problem[END_REF]. Another classical assumption is that the work is a non-decreasing function [START_REF] Hunold | One step toward bridging the gap between theory and practice in moldable task scheduling with precedence constraints[END_REF][START_REF] Lepère | Approximation algorithms for scheduling malleable tasks under precedence constraints[END_REF][START_REF] Fan | An effective approximation algorithm for the malleable parallel task scheduling problem[END_REF] -the work is the product of the execution time and of the number of processor used-which defines the model sometimes called monotonous penalty assumptions. Some other work consider that the speed-up function is a concave function [START_REF] Makarychev | Precedence-constrained scheduling of malleable jobs with preemption[END_REF]. Several of the models considered in the literature satisfy all above assumptions: nondecreasing concave speed-up function and non-decreasing work. This is for instance the case of the model studied by Prasanna and Musicus [START_REF] Prasanna | Generalized multiprocessor scheduling and applications to matrix computations[END_REF][START_REF] Prasanna | The optimal control approach to generalized multiprocessor scheduling[END_REF] where p i (k) = p 1 (1) k α where α is a task-independent constant between 0 and 1 [START_REF] Prasanna | Generalized multiprocessor scheduling and applications to matrix computations[END_REF][START_REF] Prasanna | The optimal control approach to generalized multiprocessor scheduling[END_REF][START_REF] Guermouche | Scheduling trees of malleable tasks for sparse linear algebra[END_REF]. Another instance is the model we use in this work, that is, the linear model [START_REF] Beaumont | Minimizing weighted mean completion time for malleable tasks scheduling[END_REF][START_REF] Wang | A heuristic of scheduling parallel tasks and its analysis[END_REF][START_REF] Drozdowski | Scheduling parallel tasks with sequential heads and tails[END_REF][START_REF] Nagarajan | Flowflex: Malleable scheduling for flows of mapreduce jobs[END_REF][START_REF] Zinder | Scheduling flexible multiprocessor tasks on parallel machines[END_REF]:

p i (k) = p i
k . Kell and Havill [START_REF] Kell | Improved upper bounds for online malleable job scheduling[END_REF] added to that model an overhead affine in the number of processors used:

p i (k) = p i k + (k -1)c.
This model is also closely related to the Amdahl's law where

p i (k) = p (p) i k + p (s)
i . This law is considered the experimental evaluation of [START_REF] Fan | An effective approximation algorithm for the malleable parallel task scheduling problem[END_REF].

Finally, the number of processors alloted to a task can, depending on the assumptions, either only take integer values, or can also take rational ones [START_REF] Prasanna | Generalized multiprocessor scheduling and applications to matrix computations[END_REF][START_REF] Prasanna | The optimal control approach to generalized multiprocessor scheduling[END_REF][START_REF] Guermouche | Scheduling trees of malleable tasks for sparse linear algebra[END_REF][START_REF] Makarychev | Precedence-constrained scheduling of malleable jobs with preemption[END_REF].

Results for moldable tasks. Du and Leung [START_REF] Du | Complexity of scheduling parallel task systems[END_REF] have shown that the problem of scheduling moldable tasks with preemption and arbitrary speedup functions is NP-complete.

In the scope of the monotonous penalty model, Lepère, Trystram, and Woeginger [START_REF] Lepère | Approximation algorithms for scheduling malleable tasks under precedence constraints[END_REF] presented a 3 + √ 5 ≈ 5.23606 approximation algorithm for general DAGs, and a 3+ √ 5 2 + ≈ 2.61803 + approximation algorithm for series-parallel graphs and DAGs of bounded width.

Wang and Cheng presented [START_REF] Wang | A heuristic of scheduling parallel tasks and its analysis[END_REF] a 3-2 p -approximation algorithm to minimize the makespan while scheduling moldable task graphs with linear speedup and maximum parallelism δ j (problem P |prec, any, spdp-lin, δ j |C max ).

Results for malleable tasks. The problem of scheduling independent malleable tasks with linear speedups, maximum parallelism per task, and with integer allotments, that is P |var , spdp-lin, δ j |C max , can be solved in polynomial time [START_REF] Vizing | Minimization of the maximum delay in servicing systems with interruption[END_REF][START_REF] Drozdowski | Scheduling parallel tasks with sequential heads and tails[END_REF] using a generalization of McNaughton's wrap-around rule [START_REF] Mcnaughton | Scheduling with deadlines and loss functions[END_REF]. Drozdowski and Kubiak showed in [START_REF] Drozdowski | Scheduling parallel tasks with sequential heads and tails[END_REF] that this problem becomes NP-hard when dependences are introduced: P |prec, var , spdp-lin, δ j |C max is NP-hard. Balmin et al. [START_REF] Nagarajan | Flowflex: Malleable scheduling for flows of mapreduce jobs[END_REF] present a 2-approximation algorithm for this problem. Their algorithm builds integral allotments by first scheduling the DAG on an infinite number of processors and then using the optimal algorithm for independent tasks to build an integral-allotment schedule for each interval of the previous schedule during which a constant number of processors greater than p was used. According to Theorem 5 of the present paper, this algorithm is also a 2 -δ min p approximation for makespan minimization with fractional allotments.

Makarychev and Panigrahi [START_REF] Makarychev | Precedence-constrained scheduling of malleable jobs with preemption[END_REF] consider the problem P |prec, var |C max under the monotonous penalty assumption and when allotments are rational. They provide a (2 + )-approximation algorithm, of unspecified complexity (their algorithm relies on the resolution of a rational linear program; this linear program is not explicitly given). Furthermore, they prove that there is no "online algorithm with sub-polynomial competitive ratio" (an online algorithm is an algorithm that considers tasks one after the other, as in our greedy algorithms).

Series-parallel graphs. Series-parallel graphs can be recognized and decomposed into a tree of series and parallel combination in linear time [START_REF] Valdes | The recognition of series parallel digraphs[END_REF]. It is well-known that that series-parallel graphs capture the structure of many real-world scientific workflows [START_REF] Bharathi | Characterization of scientific workflows[END_REF], A possible way to extend algorithms designed for series-parallel graphs to general graphs is to first transform a graph into a series-parallel graph, using a process sometimes called SPization [START_REF] González-Escribano | Mapping unstructured applications into nested parallelism[END_REF][START_REF] Mitchell | Creating minimal vertex series parallel graphs from directed acyclic graphs[END_REF] before applying a specialized algorithm for SP-graphs. This was for example done in [START_REF] Cordasco | Assessing the computational benefits of area-oriented dag-scheduling[END_REF]. However, note that no SPization algorithm guarantees that the length of the critical path is increased by only a constant ratio.

Application model

We consider a workflow of tasks whose precedence constraints are represented by a task graph G = (V, E, w, δ) of n nodes, or tasks: a task can only be executed after the termination of all its predecessors. We assume that G is a series-parallel graph. Such graphs are built recursively as series or parallel composition of two or more smaller SP-graphs, and the base case is a single task. Trees can be seen as a special-case of series-parallel graphs. A tree can be turned into an SP-graph by simply adding one dummy task without computation cost, that has an edge with every leaf of the tree.

Each task T i ∈ V is associated with a weight w i that corresponds to the work that needs to be done to complete the task. By extension, the weight of a subgraph of G is the sum of the weights of the tasks it is composed of. The start time t i of a task T i is defined as the time when the processing of its work starts for the first time. We denote by p the total number of identical processors available to schedule G. Tasks are assumed to be preemptible, malleable, with linear speed-up, and maximum parallelism per task. That is, each task T i may be allocated a fractional, time-varying amount p i (t) of processors at time t. Moreover, task T i is associated with a threshold δ i in the number of processors, which limits the speed-up of the task. For p i (t) ≤ δ i , the task is perfectly parallel, and for p i (t) > δ i , the speed-up is equal to the threshold. The completion or finish time of task T i is thus defined as the smallest value f i such that

f i 0 min(p i (t), δ i )dt = w i .
The objective is to minimize the makespan of the application, that is the latest task finish time. Using Graham's notation, this problem corresponds to P |prec, var , frac, spdp-lin, δ j |C max , where frac denotes fractional allocations. As mentioned in the introduction, it is possible to remove the assumption of fractional allocation without degrading the makespan thanks to malleability: from any fractional schedule, we consider each interval when tasks get a constant fractional number of processors, and we transform it into an integer allocation using McNaughton's wrap-around rule [START_REF] Mcnaughton | Scheduling with deadlines and loss functions[END_REF]. This may only add a number of preemptions proportional to the number of tasks for each interval.

In the following, we will often use the length of the critical path of a task T i , which is defined as the minimum time needed to complete all the tasks on any path from this task to any output task of the graph, provided that an unlimited number of processors is available. This corresponds to the classical notion of bottom-level [START_REF] Sinnen | Task Scheduling for Parallel Systems[END_REF], when the duration of each task is set to w i /δ i . By extension, the critical path of the entire graph G is the longest critical path of all its tasks. Some of the algorithms presented in this paper also apply to some restricted variants of the problem. A notable one is the case of moldable tasks, which prohibit any variation in the set of processors used by a task: in this case, p i (t) must be constant on one time interval, and null elsewhere.

Complexity

Task malleability and perfect speed-up make this problem much easier than most scheduling problems. However, quite surprisingly, adding thresholds to limit the possible parallelism is sufficient to make it NP-complete1 .

Theorem 1. The problem of minimizing the makespan is NP-complete.

Proof. We start by proving that this problem belongs to NP. Without loss of generality, we restrict to schedules which allocate a constant share of processors to each task between any two task completions. Note that from a schedule that does not respect this condition, we can construct a schedule with the same completion times simply by allocating the average share of processors to each task in each such interval. Given a schedule that respects this restriction, it is easy to check that it is valid in time polynomial in the number of tasks.

To prove completeness, we perform a reduction from the 3SAT problem which is known to be NP-complete [START_REF] Garey | Computers and Intractability, a Guide to the Theory of NP-Completeness[END_REF]. An instance I of this problem consists of a boolean formula, namely a conjunction of m disjonctive clauses, C 1 , . . . , C m , of 3 literals each. A literal may either be one of the n variables x 1 . . . x n or the negation of a variable. We are looking for an assignment of the variables which leads to a True evaluation of the formula.

Instance definition. From I, we construct an instance J of our problem. This instance is made of 2n+1 chains of tasks and p = 3 processors. The first 2n chains corresponds to all possible literals of instance I; they are denoted L x i or L x i and called literal chains. The last chain is intended to mimic a variable "processor profile", that is a varying number of available processors over time for the other chains, and is denoted by L pro .

Our objective is that for every pair of literal chains (L x i and L x i ), one of them starts at some time t i = 2(i -1) and the other at time t i + 1. The one starting at time t i + 1 will have the meaning of True. We will construct the chains such that (i) no two chains of the same pair can start both at time t i + 1 and (ii) at least one chain L x i or L x i corresponding to one of the three literals of any given clause starts at time t i + 1.

For any chain, we consider its critical path length, that is, the minimum time needed to process it provided that enough processors are available. The makespan bound M of instance J is equal to the critical path length of the last chain L pro , and will be specified later. Thus, to reach M , all tasks of L pro must be allocated their threshold, and no idle time may be inserted between them.

In constructing the chains, we only use tasks whose weight is equal to their threshold, so that their minimum computing time is one. Then, a chain is defined by a list of numbers [a 1 , a 2 , . . .]: the i-th task of the chain has a threshold and a weight a i . As a result, the critical path length of a chain is exactly the number of tasks it contains. We define ε = 1/4n and present the general shape of a literal chain L a , where a is either x i or x i :

L a = [1, ε, ε, . . . , ε 2(n-i) , SelectClause(a) 2m tasks , ε, . . . , ε 2(n-i) , 1]
The leftmost and rightmost parts of the chain are dedicated to ensuring that in each pair of literal chains, one of them starts at time t i = 2(i -1) and the other at time t i + 1. The central part of the chain is devoted to clauses, and ensures that for each clause, at least one chain corresponding to a literal of time processor usage the clause starts at time t i + 1:

L pro L x1 L x1 L x2 L x2 t 1 = 0 t 2 M -t 2 M -t 1
SelectClause(a) = [InClause(C 1 , a), ε, . . . , InClause(C m , a), ε]
where

InClause(C k , a) = [1 -2 3 nε] if a appears in C k [ε] otherwise
In total, the chain L a includes 4n + 2m -4i + 3 tasks. Finally, the profile chain is defined as follows: where

L pro = [2, 2 -ε, . . . , 2
L 10 = [1 -( 2 3 n -2)ε, 3ε].
The critical path length of L pro defines M = 2m + 4n. Figure 1 presents a valid schedule for the instance corresponding to the formula (x 1 ∨ x 2 ∨ x 2 ), which corresponds to the assignment {x 1 = 0, x 2 = 0}.

From a truth assignment to a valid schedule. We assume here that we are given a truth assignment of the variables of I: let v i denote the value of variable x i in this assignment. We construct the following schedule for J : for all chains, each task is allocated a number of processors equal to its threshold and no idle time is inserted between any two consecutive tasks. Chain L pro starts at time 0 while chain L x i (respectively L x i ) starts at time t i + 1 if v i is True (resp. False), otherwise it starts at time t i . It is straightforward to check that this schedule is valid. Here, we only concentrate on the most critical part, namely the central part which corresponds to the clauses. We count the number of processors used during on time interval [2n + 2(k -1), 2n + 2k] which corresponds to clause C k :

• In the first half of this interval, at most 2 literal chains can have a task of size 1 -2 3 nε since at least one in the tree literals of the clause is true.

Together with the other literal chains and the profile, the maximum processor occupancy is at most:

2 1 - 2 3 nε False literal chains + (2n -2)ε other literal chains + 1 - 2 3 n -2 ε Lpro = 3.
(Remark that because ε = 1/4n, 1 -2 3 nε > ε.) • In the second half of this interval, at most 3 literal chains can have a task of size (1 -2 3 nε), which may result in a maximum number of busy processors of:

3 1 - 2 3 nε True literal chains + (2n -3)ε other literal chains + 3ε Lpro = 3.
The resulting schedule has a makespan of M and is thus a solution to J .

From a valid schedule to a truth assignment. We now assume that instance J has a valid schedule S and we aim at reconstructing a solution for I. We first prove some properties on the starting times of chains through the following lemma. The proof is done by induction on i, by carefully checking when the first and last tasks of chains L x i , L x i may be scheduled, given the resources which are not used by the previous chains and by L pro .

Lemma 2. In any valid schedule S for J , i. each pair of chains L x i , L x i is completely processed during time interval

[t i , M -t i ],
ii. one of them is started at time t i and the other one at time t i+1 , iii. all tasks of both chains are allocated their threshold, iv. there is no idle time between any two consecutive tasks of each chain.

Proof. We prove the lemma by induction on i. It is obviously true for i = 0 (as no chain L x 0 exists). We assume the lemma true for i < n and consider chains L x i , L x i . We first notice that given the induction properties, no processor is available before t i and after M -t i , which proves (i). The time span available for the remaining chains is thus M -2t i = 4n + 2m -4i + 4 while the critical path of chains L x i and L x i is 4n + 2m -4i + 3: these chains cannot be started after t i + 1 to be completed within the time span.

We consider the first task of chain L x i and the first task of chain L x i . Both tasks have weight 1. Let A denote the first of these two tasks to complete (at a time t A ) and let B be the other one (which completes at time t B ). Given the 2(i -1) chains already scheduled, the number of processors available during interval [t i , t i + 1] is 1 and during interval [t i + 1, t i + 2] is 1+ε. A and B both complete at or after time t i +1. We note t A = t i +1+∆ 1 and t B = t i + 1 + ∆ 1 + ∆ 2 (∆ 1 ≥ 0 and ∆ 2 ≥ 0). Note that because of the critical path length of the remaining tasks of both chains and the limited time span, ∆ 1 ≤ 1 and ∆ 1 + ∆ 2 ≤ 1. The following figure illustrates the previous notations and the amount of processors available for tasks A and B (note that after time t A , B may use only δ B = 1 processor).

t p 1 ∆ 1 ∆ 2 1 1 + ε t A t B
Since w A + w B = 2 work units have to be performed before time t B , we have

1 + ∆ 1 (1 + ε) + ∆ 2 ≥ 2 and thus ∆ 2 ≥ 1 -∆ 1 (1 + ε) and t B ≥ t i + 2 -∆ 1 ε.
We symmetrically apply the same reasoning to the last tasks C and D of these two chains, and their starting times t C and t D , assuming that C is started before D. By setting t D = M -t i -1 -∆ 1 , we get t C ≤ M -t i -2 + ∆ 1 ε. We distinguish between two cases, depending on the chains to which A, B, C, and D belong to:

• In the first case, we assume that A and D belong to the same chain.

We consider the other chain, containing B and C. Because exactly 4(n -i) + 2m + 1 tasks need to be processed between these two tasks, we have

t C ≥ t B + 4(n -i) + 2m + 1 which gives ∆ 1 ε ≥ 1 -∆ 1 ε
We have ∆ 1 ≤ 1 and similarly, ∆ 1 ≤ 1. Together with the previous inequality, this gives ε ≥ 1/2 which is not possible since ε = 1/4n. Hence B and C cannot belong to the same chain.

• In the second case, we consider that A and C belongs to the same chain. Because exactly 4(n -i) + 2m + 1 tasks need to be processed

RR n°8856

between A and C (and between B and D), we have

t C ≥ t A + 4(n -i) + 2m + 1 and t D ≥ t B + 4(n -i) + 2m + 1.
This gives

2m + 4n -t i -2 + ∆ 1 ε ≥ t i + 1 + ∆ 1 + 4(n -i) + 2m + 1 and 2m + 4n -t i -1 -∆ 1 ≥ t i + 2 -∆ 1 ε + 4(n -i) + 2m + 1,
which are simplified (using

t i = 2(i -1)) into ∆ 1 ε ≥ ∆ 1 and ∆ 1 ≤ ∆ 1 ε. This leads to ∆ 1 ≤ ∆ 1 ε 2 . As 0 < ε < 1, we have ∆ 1 = 0, so t A = t i +1.
Then, no processor can be allocated to B during [t i , t i+1 ].

In other words, one task among the first task of L x i and the first task of L x i is fully processed during interval [t i , t i + 1] and the other one is not processed before t i + 1. Because of its critical path length, the chain starting second must be processed at full speed (each task being allocated a number of processors equal to its threshold) and without idle time in the interval

[t i + 1, M -t i ],
which in particular proves (ii). The last task of the chain starting at time t i must then be completed at time M -t i -1, and thus this chain must also be processed at full speed and without idle time. This proves (iii) and (iv).

For each literal chain which starts at time t i + 1, we associate the value True in an assignment of the variables of I, and we associate the value False to all other literals. Thanks to the previous lemma, we know that exactly one literal in the pair (x i , x i ) is assigned to True. Furthermore, not three tasks of size 1 -2 3 nε can be scheduled at time 2n + 2(k -1) because of the profile chain, as this would lead to a number of occupied processors of:

3 1 - 2 3 nε 3 False literal chains + (2n -3) ε other literal chains + 1 - 2 3 n -3 ε Lpro = 4- 2 3 nε = 4- 1 6 > 3 = p.
Thus, at least one literal of each clause is set to True in our assignment. This proves that it is a solution to I.

Proportional Mapping

The first algorithm to be studied is the widely used "proportional mapping" [START_REF] Pothen | A mapping algorithm for parallel sparse cholesky factorization[END_REF]. In this approach, a sub-graph is allocated a number of processors that is proportional to the ratio of its weight to the sum of the weights of all sub-graphs under consideration. Based on the composition of the considered SP-graph G, Algorithm 1 allocates a share of processors to each sub-graph and eventually each task. A given graph G (with SP-graph characteristics) can be decomposed into its series and parallel components using an algorithm from [START_REF] Valdes | The recognition of series parallel digraphs[END_REF]. Observe that the threshold δ i is not considered in this proportional mapping.

The schedule corresponding to this proportional mapping is simply to start every task as early as possible (i.e. after predecessors have completed) with min {δ i , p i } processors, as given in Algorithm 2.

Algorithm 2: PropScheduling (G = (V, E, w, δ), p)

1 Call ProportionalMapping (G, p) to determine p i for each task

T i ∈ G 2 Order tasks of G in topological order list L 3 foreach T i ∈ L do 4
Start T i with min {δ i , p i } processors as early as possible, i.e. after all predecessors completed Given the proportional mapping, there are always enough processors available to do that. It is worth noting that the created schedule is compatible with the moldable model; tasks use the same number of processors during their entire execution. As such, Algorithm 2 can also be used for the moldable model.

In the case of perfect parallelism (i.e., δ i ≥ p, ∀T i ∈ G), there is no idle time as all tasks of a parallel composition terminate at exactly the same time (due to the proportional mapping). Hence, this schedule achieves the optimal makespan M ∞ = i∈G w i p . For the general case the following theorem holds. Theorem 3. PropScheduling is a 2-approximation algorithmfor makespan minimization.

Proof. We first note that the optimal makespan without thresholds, M ∞ , is a lower bound on the makespan M with thresholds. With M OPT being the optimal schedule length, we have M ∞ ≤ M OPT ≤ M and we want to show M ≤ 2M OPT .

The critical path cp of G, as defined in Section 3, is a longest path in G, where length is defined as the sum of the work of each task on the path divided by its threshold, len(cp) = i∈cp w i δ i . Naturally, the critical path length is another lower bound on the optimal makespan, len(cp) ≤ M OPT .

Consider the schedule produced by PropScheduling. There is at least one path Φ in G from the entry task to the exit task, with no idle time between consecutive tasks. In other words, the next task starts execution when the previous one finishes.This follows from the fact that we start tasks as early as possible, so this is always true between the tasks of every serial composition of the SP-graph G, and it is true for at least one task in every parallel composition. The execution length of this path is the makespan M , because it includes no idle time and that it goes from entry to exit task. It is given by M = i∈Φ w i min {δ i , p i } Let us divide the tasks of Φ into two sets: the set A of tasks that are executed with their threshold processors δ i and the set B of tasks that are executed with the allocated number of processors p i < δ i , with A ∪ B = Φ. We then have

M = i∈A w i δ i + i∈B w i p i
The first term is per definition less than or equal to the length of the critical path len(cp). The second term consists only of tasks that are executed with their proportionally allocated processors, so it is less than or equal to the optimal length without threshold M ∞ . We then get the desired inequality:

M = i∈A w i δ i + i∈B w i p i ≤ len(cp) + M ∞ ≤ 2M OPT
So PropScheduling is a 2-approximation algorithm and the factor is asymptotically tight, as shown in the following corollary.

Corollary 4. The approximation factor 2 for PropScheduling is asymptotically tight.

RR n°8856

Proof. Consider the tree of Figure 2, where k chains of two tasks each are connected to the root. The tasks are of two different types. The ones closer to the root (depicted as narrow and long) are called type S and have a threshold of δ S = and a size which is a multiple of , between 1 and k. The leaves are called type P (depicted as rectangular), have no threshold, i.e. δ P ≥ p, and a computation size as given in the figure. The number of processors is p = W . Let be very small in comparison to W and k, and k be small in comparison to W .

With PropScheduling each chain is allocated p/k processors. Hence all chains are processed in parallel and the makespan is determined by the rightmost chain. In that chain, the S task takes k time units (due to δ S = ) plus the execution of the P task with all processors p/k:

M pro = k + W p k
In an optimal schedule, the processors are not all allocated statically, but first allocated to the rightmost chain to complete its P task, then to the one left to it (minus processors) and so on. The resulting makespan is:

M opt = k + W p + O( )
The ratio of those makespans is then:

M pro M opt = kp + kW kp + W + O(1/ )
and with p = W we get

M pro M opt = 2pk p(k + 1) + O(1/ )
When k and p tend to infinity, the ratio tends to 2.

PropScheduling has the following complexity. The recursive processing of sub-graphs in

Greedy-filling

The proportional mapping studied in the previous section might be a common approach, but it does not make use of the malleability of tasks and

RR n°8856 root δ = δ = δ = δ = δ = 2 3 (k -1) k W + (k -1) W + (k -2) W + (k -3) W + W Figure 2:
Tree for proof of tightness of approximation factor of Propor-tionalMapping is restricted to SP-graphs. In this section we study an algorithm, called GreedyFilling, that does not have these limitations. It considers one task at a time and greedily "fills" the possible empty spaces in the schedule. An essential part in this heuristic is to keep track of how many processors are available at each time. For this, we propose to use a sorted set of pairs τ k , p k , called availP rocs. Each pair represents the time τ k from which on p k processors are available until the time τ k+1 of the next pair τ k+1 , p k+1 . The sorted set property means that times are distinct and in ascending order. Also, for any two consecutive pairs, the numbers of processors are different (otherwise the later of the two pairs is not meaningful). All additions to, and modifications of, availP rocs keep these properties intact. In particular, if the numbers of processors of two consecutive pairs become identical, then the later pair is removed.Figure 3a illustrates this data structure with six pairs, τ k , p k , k ∈ {1, . . . , 6}, depicting the available processors at the six times (note that p 6 = p).

Using the availP rocs data structure, the GreedyFilling algorithm is proposed in Algorithm 3. The principle of the algorithm is simple. First, each task is given a distinct priority. Then, the algorithm successively schedules the tasks, always choosing a free task T s with highest priority. A task T is free when all of its parents have already been completely scheduled. When a task is scheduled, it is "poured" into empty spaces of the schedule. This means it starts as early as it can, which is at the earliest processor availability time from availP rocs that is at or after T s 's ready time ready(s). A task T's ready time is the highest finish time of its parents or zero if T has no parent (i.e., is a source task). The task T s greedily uses as many processors as it can, which is the smaller of its threshold δ s and the number of processors available at the time. Given that processor availability changes over time, we must determine the number of processors that can be used during each interval of availability times of availP rocs until T s is completely scheduled. Figure 3b illustrates the adding of task T s to the schedule. Its ready time, and hence it earliest start time, is τ 3 at which time it starts. During the interval [τ 3 , τ 4 ] the processors it can use is limited by its threshold δ s . After τ 4 it uses all available processors p k and completes at time f s . This time becomes a new time-processors pair to be added to availP rocs. The resulting availability profile after T s has been added is given in Figure 3c.

It is interesting to note that if the total number of processors p and all thresholds are integers (δ i ∈ N, ∀T i ∈ V ) then also all allocated processors p i will be integers too.

Theorem 5. GreedyFilling is a 2 -δ min p approximation for makespan minimization,with δ min = min T i ∈V δ i .

Proof. This proof is a transposition of the classical proof by Graham [START_REF] Graham | Bounds for certain multiprocessing anomalies[END_REF]. In any schedule produced by GreedyFilling, let T 1 be a task whose completion time is equal to the completion time of the processing of the whole task graph. We consider the last time t 1 prior to the start of the execution of T 1 at which not all processors were fully used. If the execution of T 1 did not start at time t 1 this is only because at least one ancestor T 2 of T 1 was executed at time t 1 . Then, by induction we build a dependence path Φ = T k → . . . → T 2 → T 1 such that all processors are fully used during the execution of the entire schedule except, at least partially, during the execution of the tasks of Φ.

We consider the execution of any task T i of Φ. At any time during the execution interval(s) of T i (due to malleability it might be executed in disconnected intervals), either all processors are fully used, or some processors are (partially) idle and then, because of Step 10, δ i processors are allocated F reeT asks ← F reeT asks \ {T s } ∪ free children of T s to T i . Therefore, during the execution of T i , the total time during which not all processors are fully used is at most equal to w i δ i and there are at most p -δ i idle processors. Let Idle denote the sum of the idle areas, i.e., idle periods multiplied by idle processors, in the schedule. Then we have:

w ∆ ← w s //
Idle ≤ k i=1 w i δ i × (p -δ i ) ≤ (p -δ min ) × k i=1 w i δ i ≤ (p -δ min )M OPT .
The last inequality comes from the fact that k i=1 w i δ i is a lower bound on the execution time of the path Φ, and thus a lower bound on the optimal makespan.

Let Used denote the sum of the busy areas in the schedule. Then Used = i w i and thus Used ≤ p×M OPT . Let M be the makespan of the considered schedule. Then we have:

p × M = Idle + Used ≤ (2p -δ min )M OPT .
Note that the above proof makes little reference to how the schedule of G DAG has been constructed. The only important characteristic is that the algorithm never leaves a processor deliberately idle if there are tasks that could be scheduled. Hence, the above approximation factor will also apply to other algorithms which adhere to that characteristic.

GreedyFilling has the following complexity. Assigning a priority to each task and always selecting the free task with the highest priority has a total complexity of O(|V | log |V |), for example by using a heap based priority queue for F reeT asks. Checking for newly freed tasks in the last line amortises to O(|E|) for all tasks, as every edge is only checked once. For every task at most O(|V |) processor availability intervals are checked, as the bounds of the intervals are finishing times of tasks of which there are at most O(|V |). As this is done for each task, the complexity of this step is O(|V | 2 ), which is also the total complexity of GreedyFilling as it dominates the other components.

Simulations

In this section, we compare the proposed GreedyFilling algorithm to two existing algorithms: PropScheduling, described earlier, and a 2approximation, FlowFlex, proposed in [START_REF] Nagarajan | Flowflex: Malleable scheduling for flows of mapreduce jobs[END_REF] to solve a more general problem with multiple applications. In summary, FlowFlex first runs an algorithm similar to GreedyFilling on an infinite number of processors and then divide the obtained schedule into time intervals with constants allocations. On each such interval, if the total number of used processors exceed their actual number, the allocation is proportionally scaled down to fit the limit and the duration of this interval is increased. Note that PropScheduling does not take advantage of task malleability, while both GreedyFilling and FlowFlex do.

The following simulations are performed on two different datasets:

• First, we consider synthetic random SP-graphs of 5000 nodes, whose generation is detailed below. In order to compute a random SP-graph of x > 1 nodes, we obey the following recursive strategy: toss k uniformly in [1, x-1]; with a probability of 1/2, build a series composition of two random SP-graphs of respectively k and x -k nodes, and otherwise, build a parallel composition of these graphs. Then, in order to compute a random task (i.e., a random graph of x = 1 node), we choose its weight uniformly in [1; 1000], and we choose its threshold to be proportional to its weight (with a factor of f = 0.01). This dataset has two variants, one where the threshold and the weight of a task are proportional (δ i = α × w i , with α = 0.01), denoted by Synth-Prop, and one where some randomness is introduced in this relation (α ∈ [0.001, 0.1] with log uniform distribution), denoted by Synth-Rand. • Second, we consider the assembly trees of a set of actual sparse matri-ces, which corresponds to the task graphs of the factorization of these matrices using multifrontal methods. In total, we consider more than 600 trees which may have a very large number of nodes, so we aggregate nodes such that at most 1000 nodes remain and their weight is larger than a given threshold (100 kFLOP). Here, the threshold of tasks is also proportional to their weight This dataset is denoted by Trees. The last dataset D rl consists of assembly trees of a set of sparse matrices obtained from the University of Florida Sparse Matrix Collection (http://www.cise.ufl.edu/research/sparse/matrices/). The details concerning the computation of the data set can be found in [START_REF] Eyraud-Dubois | Parallel scheduling of task trees with limited memory[END_REF]. The data set consists of more than 600 trees each containing between 2, 000 and 1, 000, 000 nodes with a depth ranging from 12 to 75, 000. In order to simplify the dataset, we aggregated the trees by merging the smallest tasks to their parent, i.e., adding their weight, so that each tree now consists of 1, 000 nodes. Then, we set the threshold of each node being proportional to its weight. In Figure 4, we present the makespan of PropScheduling, FlowFlex and GreedyFilling normalized by the classical lower bound on makespan: the maximum of the critical path and of the total work divided by the number of processors. Since all graphs do not have the same intrinsic parallelism, they exhibit different behaviors for the same number of processors. Thus, we first estimate the inter-task parallelism in a given graph using the following formula: para = makespan with all thresholds at 1 and infinite resources (p = ∞) makespan with all thresholds at 1 and (p = 1)

Then, the number of processors is normalized using this quantity: p norm = p/para. We run the simulations on similar values of the normalized number of processors in order to better illustrate the behavior of the algorithms. In Figure 4, linked dots depict the average over all trees and the ribbon shows the 80% of the results that are between the first and ninth decile. We first notice that PropScheduling and FlowFlex always give longer schedules. For very small or very large numbers of processors, the problem is simplified and all algorithms reach the same makespan: with very few processors, the thresholds do not influence the solution, and with an abundance of processors, there is no need to share the resources. Thus, the maximum gain of the proposed GreedyFilling is reached for an intermediate number of processors which depends on the algorithm and the intrinsic parallelism of the task graph. One may note that a threshold not proportional to the weight (as in Synth-Rand) leads to a larger maximum gap between the algorithms, which appears for fewer processors. Quantitatively, one can expect a maximum gain of 27% on a random graph, by switching from PropScheduling to GreedyFilling, and 24% when switching from FlowFlex to GreedyFilling. On the Trees dataset, GreedyFilling outperforms PropScheduling and FlowFlex in respectively 33% and 25% of the cases, and is outperformed by any of both in only 3% of the cases. For each tree, the algorithms exhibit the same behavior than the one outlined on Figure 4. However, the position and height of this characteristic shape widely vary among families (trees obtained from the same matrix using different ordering and amalgamation parameters). The maximum expected gain is smaller (around 15%). On Figure 5, we present the makespans achieved by the three algorithms normalized by the same lower bound as before on the 8 trees of a single family of Trees. The linked dots depict the average over this family and the ribbon shows the minimum and maximum makespans. The interested reader can find all results listed in Appendix A, each graph corresponding to a single family of Trees.

To explain the good behavior of GreedyFilling compared to its com-petitors, we remark that it takes advantage of task malleability, contrarily to PropScheduling. Moreover, FlowFlex may produce gaps during its first phase, that is, time intervals with low processor utilization, which cannot be filled later; it only uses task malleability to cope with resource limitation.

Conclusion

In this paper, we have studied how to schedule graphs of malleable tasks with a perfect but bounded parallelism. We first proved the NP-completeness of the makespan minimization problem. Then, we show that the existing PropScheduling scheduling heuristic is a 2-approximation algorithm.

Then we introduced GreedyFilling, a simple greedy policy that we also proved to be a 2-approximation algorithm. Using extensive simulations, we compare these two heuristics together and also against FlowFlex, another 2-approximation proposed in [START_REF] Nagarajan | Flowflex: Malleable scheduling for flows of mapreduce jobs[END_REF]. GreedyFilling gives the smallest makespan in most configurations and achieves noticeably lower makespans, both on synthetic and realistic graphs. For instance, on random graphs, for the maximum expected gain in makespan is around 25%. This work could be extended by focusing on the more constrained moldable model in which the processing power alloted to a task cannot vary during its execution. Both theoretical and practical directions could be considered. First, it would be interesting to quantify the theoretical gain of allowing malleability and, then, to design certified and efficient heuristics for the moldable model.

A Extensive simulation results

We list in this appendix the results presented in Section 7.

Algorithm

GreedyFilling PropScheduling FlowFlex

Figure 1 :

 1 Figure 1: Example of a possible schedule for the instance J associated to the formula x 1 ∨ x 2 ∨ x2 .

  -(2n -1)ε 2n tasks , L 10 , L 10 , . . . , L 10 2m tasks , 2 -(2n -1)ε, . . . , 2 -ε, 2 2n tasks ]

Algorithm 1 : 2 Allocate p k = p processors to each subgraph 3 else

 123 ProportionalMapping (G = (V, E, w, δ), p)1 ifThe top-level composition is the series composition of K sub-graphsthen The top-level composition is the parallel composition of K sub-graphs4Allocate the ratio of processorsp k = W k K W j p to subgraph k, 1 ≤ k ≤ K,where W k is the weight of sub-graph k 5 Call ProportionalMapping (sub-graph k, p k ) for each sub-graph k

  ProportionalMapping is O(|V |). A topological order for a directed acyclic graph is created in O(|V | + |E|). Scheduling each task as early as possible is also O(|V |+|E|), because each predecessor relationship corresponds to one edge which is only checked once. So the total complexity of PropScheduling is O(|V | + |E|), which is O(|V |) for the addressed SP-graphs (as O(|E|) = O(|V |)).

  After Ts was added

Figure 3 :

 3 Figure 3: Processor availability behavior with GreedyFilling.

Figure 4 :

 4 Figure 4: Normalized makespan of PropScheduling and GreedyFilling on Synth-Prop (left) and Synth-Rand (right).

Figure 5 :

 5 Figure 5: Normalized makespan of PropScheduling and GreedyFilling on a single family of Trees.

Figure 6 :

 6 Figure 6: Legend common to all graphs of Appendix A.

  Initialize work to be done6 foreach τ k , p k ∈ availP rocs in order with τ k ≥ ready(s), skip if p k = 0 do 7 if τ k , p k is last pair in availP rocs then interval ← ∞

8 else interval ← τ k+1 -τ k 9 10 usedP rocs ← min{δ s , p k } 11 Replace τ k , p k by τ k , p k -usedP rocs in availP rocs 12 if w ∆ = w s then t s ← τ k // first part, set start time 13 if w ∆ /usedP rocs > interval then w ∆ ← w ∆ -interval • usedP rocs 14 else // rest of task fits in interval 15 f s = τ k + w ∆ /usedP rocs // set finish time 16 availP rocs ← availP rocs ∪ f s , p k 17 break // break out foreach loop 18

RR n°8856

A similar result already appeared in[START_REF] Drozdowski | Scheduling parallel tasks with sequential heads and tails[END_REF], however its proof is more complex and not totally specified, which makes it difficult to check.RR n°8856

Algorithm 3: GreedyFilling (G DAG = (V, E, w, δ), p)

1 Assign distinct priority priority(i) to each task T i ∈ G DAG 2 F reeT asks ← source tasks; availP rocs ← 0, p 3 while F reeT asks = ∅ do 4 T s ← arg max T j ∈F reeT asks {priority(j)} // select task