Catherine Donati-Martin

Bernard Roynette
email: roynette@iecn.u-nancy.frvallois@iecn.u-nancy.fr

Pierre P Vallois

Marc Yor

On constants related to the choice of the local time at 0, and the corresponding Itô measure for Bessel processes with dimension d = 2(1 -α) , 0 < α < 1

Keywords: Bessel processes, excursion theory, local time AMS Classification : 60G44, 60G52, 60J25, 60J35, 60J55, 60J60, 60J65

HAL is a

Introduction

1.1 Nowadays, it is no longer necessary to emphasize how powerful excursion theory for, say, the study of linear Brownian motion, is. This is due, in particular, to the several fundamental descriptions of Itô's characteristic measure of (Brownian) excursions, n 1/2 , which are mainly due to D. Williams ([17], §II.67).

The following compensation formula holds :

E   γ∈G H(γ, e γ ) 1 (δ-γ>0)   = E ∞ 0 dL s Ωexc n 1/2 (dε)H(s, ε) (1.1)
where :

• H : R + × Ω × Ω exc → R + is P ⊗ E measurable, P denoting the predictable σ-field associated to the Brownian motion (B u , u ≥ 0), and (Ω exc , E) denoting the measurable space of generic excursions .

• {e γ , γ ∈ G} denotes the family of Brownian excursions, labelled with their starting time γ, and where δ denotes the ending time of the same excursion, i.e : e γ (u) = B γ+u 1 (u≤δ-γ)

• G is the set of left extremities of maximal intervals ]γ, δ[ which constitute the complement of the random set Z w = {s : B s (w) = 0}; e γ (u) = B γ+u 1 (u≤δ-γ) denotes the excursion on ]γ, δ[.

• (L s , s ≥ 0) is the standard local time at 0 of (B s , s ≥ 0), i.e. : it satisfies

{|B s | -L s , s ≥ 0} is again a Brownian motion. (1.2)
Formula (1.1) is a key formula from which many consequences may be derived. See, e.g, [ [START_REF] Revuz | Continuous martingales and Brownian motion, volume 293 of Grundlehren der Mathematischen Wissenschaften[END_REF] : Chap XII]. Note that on the RHS of (1.1), it is the product :

dL s n 1/2 (dε) (1.3)
which appears, but since most authors take (1.2) as a definition of (L s ), then, as (1.3) is intrinsic, there is no ambiguity about the choice of n 1/2 .

1.2 This clear cut Brownian situation is no longer so unambiguous when one considers the excursion theory for other diffusions, and also Lévy processes. The aim of the present note is to give an easy access to pairs (L, n α ) related to the d-dimensional Bessel process (R t , t ≥ 0), starting from 0, with dimension d = 2(1 -α) with 0 < d < 2 or equivalently, with index

-α = d 2 -1 (0 < α < 1)
. To be precise, this process, which we shall denote sometimes as BES(-α), is an R + -valued Feller diffusion whose infinitesimal generator L is defined by :

Lf (r) = 1 2 d 2 f dr 2 (r) + 1 -2α 2r df dr (r)
on the domain :

D = f : R + → R ; Lf ∈ C b (R + ) , lim r→0 r 1-2α f (r) = 0 .
From now on, this dimension d will be fixed, hence so will α.

Inspired by the Brownian case, and formula (1.2), we shall take as a definition of (L t , t ≥ 0) the unique continuous increasing process such that :

R 2α t -L t := N t , t ≥ 0 , is a martingale. (1.4)
In the Brownian case, we have d = 1, α = 1/2. Then we recover (1.2). Thus, the corresponding Itô characteristic measure n α is, in fact, determined, and we shall give some descriptions of it below. We shall denote by (L (c) t , t ≥ 0) the choice :

L (c) t = cL t ,
for some c > 0.

(1.5)

Thus, the corresponding Itô measure n (c) α satisfies :

n (c) α = 1 c n α , (1.6)
since, by (1.1), which also holds of course for all the Bessel diffusions, with 0 < d < 2, the product :

dL (c)
t n (c) α (dε) does not depend on c. One of our tasks in this Note is to present, in Section 5, the various constants c found in the literature, which, we hope, may be helpful in order to avoid trivial, but annoying, mistakes... But, first, in Section 2, we give an elementary stochastic calculus approach to formula (1.4); then, in Section 3, we examine some consequences of our choice for L.

1.3

Although the present work can hardly be considered as a research paper, but merely as a user's friendly note, we think its publication may be justified as the computations of the constants related to various choices of local times for BES (-α) often play a crucial role, if one deals simultaneously with several BES processes, e.g : relating one to another one by time changes, as in Biane-Yor [START_REF] Ph | Valeurs principales associées aux temps locaux browniens[END_REF], or trying to pass to the limit as, say, α ↓ 0, as in Donati-Martin-Yor [START_REF] Donati-Martin | Some explicit Krein representations of certain subordinators, including the Gamma process[END_REF].

A stochastic calculus approach

We now derive formula (1.4), and a number of properties of (L t , t ≥ 0) by relying upon the definition of squares of Bessel processes, via the stochastic differential equation :

R 2 t = 2 t 0 R s dβ s + δt, t ≥ 0, (2.1)
where δ ≥ 0 is given, and (R s , s ≥ 0) is assumed to be an R + -valued process. It is by now well known that the equation (2.1), where (β s , s ≥ 0) is a driving Brownian motion, admits a unique solution, which is strong (see, e.g. [START_REF] Revuz | Continuous martingales and Brownian motion, volume 293 of Grundlehren der Mathematischen Wissenschaften[END_REF], Chap. IX).

Using stochastic calculus, we show the following

Theorem 2.1 For δ = 2(1 -α), 0 < α < 1, the process (R 2α t , t ≥ 0) is a submartingale, whose Doob-Meyer decomposition is R 2α t = N t + L t , t ≥ 0, (2.2)
with (L t , t ≥ 0) a continuous increasing process, carried by the zeros of (R t , t ≥ 0), and (N t , t ≥ 0) a martingale which may be written :

N t = 2α t 0 R 2α-1 s dβ s , t ≥ 0. (2.3)
Proof. Let ε > 0. We apply Itô's formula to the semimartingale : ε + R 2 t α , t ≥ 0 ; thus we obtain :

ε + R 2 t α = ε α + 2α t 0 ε + R 2 s α-1 R s dβ s + 2α(1 -α)ε t 0 ds ε + R 2 s 2-α , t ≥ 0. (2.4)
It is not difficult to show, using dominated convergence that both the martingale part, and the increasing process part in (2.4) converge, in L 2 (Ω), as ε → 0. Moreover, concerning the Riemann integral, it is clear that, for any η > 0 :

ε t 0 1 {Rs≥η} ds ε + R 2 s 2-α → 0, as ε → 0.
Thus, from (2.4), we deduce that, by letting ε → 0 :

R 2α t = 2α t 0 R 2α-1 s dβ s + L t , t ≥ 0,
where (L t , t ≥ 0) is a continuous increasing process such that :

1 {Rt =0} dL t = 0.
Corollary 2.2 Let (R t ) as in Theorem 2.1. There exists a reflecting Brownian motion (ρ s , s ≥ 0) such that :

R 2α t = ρ At , where A t =< N > t = 4α 2 t 0 R 2(2α-1) s ds. (2.5)
Proof. Define θ u = inf{t ≥ 0; A t ≥ u}. Then, from (2.2), we deduce :

ρ u def = R 2α θu = -γ u + L θu , u ≥ 0, (2.6)
where, from (2.3) and the Dubins-Schwarz theorem, (γ u , u ≥ 0) is a one dimensional Brownian motion. Since the increasing process L θu , u ≥ 0 is supported on the set of the zeros of (ρ u , u ≥ 0), the identity (2.6) may be considered as a particular case of Skorokhod's reflection equation. Hence, L θu = sup 0≤v≤u γ v and therefore (ρ u , u ≥ 0) is a reflecting Brownian motion.

3 Some useful formulae related to the choice (1.4) of L Proposition 3.1 There exists a jointly continuous family (L x t ; x ≥ 0, t ≥ 0) of local times such that :

1. L 0 t = L t ;
2. the occupation formula :

t 0 h(R s )ds = 1 α ∞ 0 h(x)L x t x 1-2α dx (3.1)
holds for every Borel function h : R + → R + .

Proof. From the general theory of diffusion local times, we know that (3.1) holds with a certain constant C, on the RHS, instead of 1 α and our task is to show that C = 1 α . But, taking expectations on both sides of (3.1) (with C on the RHS, instead of 1/α), we get :

t 0 ds r s (x) = Cx 1-2α E[L x t ]
where r s (x) is the density of R s .

Recall that (see for instance [START_REF] Revuz | Continuous martingales and Brownian motion, volume 293 of Grundlehren der Mathematischen Wissenschaften[END_REF] Chap. XI, p446) :

r s (x) = 2 α s α-1 Γ(1 -α) x 1-2α exp - x 2 2s , s > 0, x ∈ R. (3.2)
Hence, from our choice (1.4), we get :

Cx 1-2α E[R 2α t ] ∼ x→0 t 0 ds r s (x). (3.3) But, since R 2 u (d) = 2uγ d/2
, where γ k denotes a standard Gamma variable with parameter k, it easily follows from (3.3) that : C = 1 α .

Denote by τ ≡ inf {t : L t > } , ≥ 0 the right continuous inverse of (L t , t ≥ 0).

Proposition 3.2

The process (τ , ≥ 0) is a stable (α) subordinator, such that :

E [exp(-λτ )] = exp - Γ(1 -α) Γ(1 + α) 2 -α λ α . (3.4)
Moreover its Lévy measure ν(dt) is equal to

1 2 α Γ(α) dt t α+1 1 {t>0} , i.e. E [exp(-λτ )] = exp - ∞ 0 1 -e -λt 1 2 α Γ(α) dt t α+1 . (3.5)
Proof. 1) As in the previous proof, we know a priori that there exists a constant C such that :

E [exp(-λτ )] = exp -C λ α (3.6)
and we wish to prove :

C = Γ(1 -α) 2 α Γ(1 + α) . (3.7)
However, by integration of both sides of (3.6) with respect to (d ), we obtain :

E ∞ 0 dL t exp(-λt) = 1 C λ α . (3.8)
Again, from (1.4) the LHS is equal to :

E ∞ 0 dR 2α t exp(-λt) = E R 2α 1 ∞ 0 α t α-1 dt exp(-λt) = 2 α 1 Γ(1 -α) αΓ(α) 1 λ α ,
which yields (3.4).

2) An easy scaling argument shows that the Lévy measure ν of (τ ) is of the form :

ν(dt) = C ν dt t α+1 1 {t>0}
, where C ν is a positive constant. Integrating by parts, we have :

∞ 0 1 -e -λt dt t α+1 = λ α ∞ 0 e -λt dt t α = λ α α Γ(1 -α).
Consequently

C ν λ α α Γ(1 -α) = Γ(1 -α) Γ(1 + α) 2 -α λ α .
This implies that C ν = 1 2 α Γ(α) .

Furthermore, by scaling, there is the relation :

for fixed , τ (d)
= ( /L 1 ) 1/α . (

If we denote by (θ (t), t ≥ 0) the density of τ , then :

θ (t) = 1 πt ∞ k=1 (-1) k+1 Γ(αk + 1) k! γ t α k sin(kπα) (t ≥ 0)
with :

γ := Γ(1 -α) Γ(1 + α) 2 -α
(see [START_REF] Lukacs | Characteristic functions[END_REF], p. 142).

In particular :

θ (t) ∼ t→∞ γ Γ(α + 1) πt α+1 sin πα = Γ(α) 2 -α t α+1 , (3.10) because Γ(α)Γ(1 -α) = π sin πα
, (cf [START_REF] Lebedev | Special functions and their applications[END_REF], p. 3).

We now discuss similar properties for the density (p t ( ), ≥ 0) of L t . The scaling property yields :

L t (d) = t α L 1 . (3.11) Proposition 3.3
The following relation between θ (t) and p t ( ) holds :

θ (t) = α t α+1 p 1 t α .
Moreover :

p 1 (0) = 2 -α Γ(1 + α) . (3.12)
Proof. The relation between θ (t) and p t ( ) follows directly from (3.9). Taking the limit of

p 1 t α = t α+1 α θ (t),
as t → ∞, and using (3.10), we obtain :

lim t→∞ p 1 t α = lim t→∞ t α+1 α Γ(α) 2 -α t α+1 = 2 -α Γ(1 + α)
.

This shows (3.12).

The positive moments of L

= (τ 1 ) -α have a nice expression.

Proposition 3.4 Let m be a positive real. Then

E [(L 1 ) m ] = Γ(1 + m) Γ(1 + αm) 2 α Γ(1 + α) Γ(1 -α) m . ( 3

.13)

Proof. 1) It easily follows from the usual computation of negative moments of a R + -valued r.v. that :

E 1 (τ 1 ) αm = 1 Γ(αm) ∞ 0 du u αm-1 E e -uτ 1
and it now remains to use (3.4).

2) An alternative proof of (3.13) consists in using the fact that, for S a standard exp [START_REF] Barlow | Une extension multidimensionnelle de la loi de l'arc sinus[END_REF] distributed variable, independent of (L t , t ≥ 0), one has L S (d) = S α L 1 , and L S is distributed as an exp(C ) variable, with C given by (3.7).

3) For m an integer, the referee suggested another proof based on Kac's recursive moment formula :

E [(L t ) m ] = mE t 0 E (L t-s ) m-1 dL s . (3.14)
Assuming (3.14) for a moment, one recovers (3.13) by recurrence, from the scaling property of (L t , t ≥ 0).

We now give a proof of formula (3.14). This identity may be proved using the two first formulae of [START_REF] Gradinaru | Abel transform and integrals of Bessel local times[END_REF], p533, with ϕ(x) = 1. It seems interesting to give a direct proof of (3.14) in a more general setting than Bessel processes. Suppose that (L t , t ≥ 0) is the local time process at 0 of a diffusion started at 0, such that L ∞ = ∞ a.s. We claim that :

E[G(L t )] = E t 0 E[g(L t-s )]dL s , (3.15)
where g : R + → R + is Borel and

G(x) = x 0 g(t)dt, x ≥ 0.
Obviously, (3.15) is an extension of (3.14) since taking g(x) = mx m-1 in (3.15) we recover (3.14).

To prove (3.15), we introduce the two following positive measures on R + :

µ 1 (t; A) = E t 0 1 A (L s )dL s , µ 2 (t; A) = E t 0 P (L t-s ∈ A)dL s , t ≥ 0,
where

A is a generic Borel set included in R + . It is clear that µ 1 (t; •) = µ 2 (t; •) if and only if (3.15) holds. Therefore (3.15) is equivalent to : θ 1 (λ, a) = θ 2 (λ, a)
, for any λ, a > 0, where

θ i (λ, a) = ∞ 0 e -λt µ i (t; e -a• )dt.
Let (τ u ) be the right-inverse of (L t ) (i.e. τ u = inf{s ≥ 0; L s > u}) and ψ be the Lévy exponent of (τ u ) :

E e -λτu = e -uψ(λ) , u, λ > 0.

(3.16)

We first compute θ 1 (λ, a) :

θ 1 (λ, a) = ∞ 0 dte -λt E t 0 e -aLs dL s = 1 λ E ∞ 0
e -aLs-λs dL s .

Setting u = L s and using (3.16), we obtain :

θ 1 (λ, a) = 1 λ E ∞ 0 e -au-λτu du = 1 λ ∞ 0 e -u(a+ψ(λ)) du = 1 λ(ψ(λ) + a)
.

Similarly, we express θ 2 (λ, a) in terms of ψ(λ) :

θ 2 (λ, a) = ∞ 0 dte -λt E t 0 E[e -aL t-s ]dL s .
Using Fubini's theorem we get :

θ 2 (λ, a) = E ∞ 0 e -λs dL s ] E ∞ 0 e -aLu-λu du . Since E ∞ 0 e -λs dL s ] = E ∞ 0 e -λτu
du], then (3.16) implies that :

θ 2 (λ, a) = 1 ψ(λ) E ∞ 0 e -aLu-λu du .
Using excursions theory, we obtain :

θ 2 (λ, a) = 1 ψ(λ) E l>0 τ l τ l- e -aLu-λu du = 1 ψ(λ) E l>0 e -al-λτ l-1 -e -λ(τ l -τ l-) λ = 1 λψ(λ) ∞ 0 e -al E[e -λτ l ]dl ψ(λ).
Using (3.16) and (3.5), we have :

θ 2 (λ, a) = 1 λψ(λ) ∞ 0 e -l(a+ψ(λ)) dl ψ(λ) = 1 λ(a + ψ(λ))
.

This proves that θ 1 (λ, a) = θ 2 (λ, a). Hence, formula (3.15) has been proved. Likewise, the moments of l 1 , the local time of the standard Bessel bridge, with dimension 2(1 -α) may be computed explicitly as the following proposition shows.

Proposition 3.5 For m, any positive real, we have :

E [(l 1 ) m ] = Γ(1 + m)Γ(α) Γ α(1 + m) 2 α Γ(1 + α) Γ(1 -α) m . (3.17)
The main difference with (3.13) is that in the denominator of (3.17), we find Γ α(1 + m) , whereas in that of (3.13), we have Γ (1 + α)m .

Proof of Proposition 3.5 Let g = sup{t < 1, R t = 0}. We have :

L 1 = L g = g α l 1 ,
by scaling, using the fact that 1 √ g R ug , 0 ≤ u ≤ 1 is a standard Bessel bridge independent of g.

Next, we use the fact that g

(d)
= β(α, 1 -α). Consequently :

E [(L 1 ) m ] = E g αm E [(l 1 ) m ] = Γ α(1 + m) Γ(1 + αm)Γ(α) E [(l 1 ) m ] .
Comparing this formula with (3.13), we obtain (3.17).

Descriptions of n α

Traditionally, following D. Williams' descriptions of Itô's measure for Brownian motion, (see e.g : Williams [START_REF] Williams | Diffusions, Markov processes, and martingales[END_REF] and Rogers [START_REF] Rogers | Williams' characterisation of the Brownian excursion law: proof and applications[END_REF]), there are two descriptions for n α , which are obtained by disintegrating n α with respect to M = sup u≤v(ε) ε(u) or with respect to V (ε) = inf{t > 0; ε(t) = 0}, where ε denotes the generic excursion and V (ε) its lifetime. These descriptions are (see [START_REF] Ph | Valeurs principales associées aux temps locaux browniens[END_REF], and [START_REF] Pitman | Decomposition at the maximum for excursions and bridges of onedimensional diffusions[END_REF]) : 4.2 Disintegration with respect to

V (i) n α (V ∈ dv) = dv 2 α Γ(α)v α+1 ; (4.2) (ii) Conditionally on V = v, the process (ε(u), u ≤ v) is distributed as a standard BES (α) bridge, with length v.
In fact, a simple look at either (4.1) (i), or (4.2)(i), as well as the corresponding formulae in Biane-Yor [START_REF] Ph | Valeurs principales associées aux temps locaux browniens[END_REF], shows that : n α = nα , where nα is the notation for Itô measures chosen in [START_REF] Ph | Valeurs principales associées aux temps locaux browniens[END_REF]. Thus, it suffices to show (4.1) (i) : on one hand, from excursion theory, one has :

P max u≤τ R u < a = exp {-n α (M ≥ a)} . (4.3)
On the other hand, trivially,

P max u≤τ R u < a = P {τ < T a } = P {L Ta > } . (4.4)
However, L Ta is exponentially distributed, with mean E[L Ta ] = a 2α , from our choice of L. Comparing (4.3) and (4.4), we obtain (4.1)(i).

Remark 4.1 We take this opportunity to correct an annoying mistake in (3.h) [START_REF] Ph | Valeurs principales associées aux temps locaux browniens[END_REF], where the constant 1 4µ(1-µ) should be changed in 1 2µ(1-µ) (see also a similar remark before paragraph (3.3) in [START_REF] Donati-Martin | Some explicit Krein representations of certain subordinators, including the Gamma process[END_REF]).

The different choices of c in the literature

As we scanned the literature about excursion theory and/or choice of local times for BES (-α), we have come across the following papers :

1. Pitman-Yor ( [START_REF] Pitman | Random Brownian scaling identities and splicing of Bessel processes[END_REF], [START_REF] Pitman | On the distribution of ranked heights of excursions of a Brownian bridge[END_REF], [START_REF] Pitman | Laplace transforms related to excursions of a one-dimensional diffusion[END_REF]) : in these three papers, the results do not depend on the local time normalization; In most of these papers from 2. to 9., the authors use a particular density of occupation formula :

t 0 h(R s )ds = γ ∞ 0 h(x)L
x(c) t

x β dx , which, when compared with (3.1) yields : (in many cases, β = 1 -2α, so that : L

x(c) t

= 1 αγ L x t ).
We now present a table for the formulae (5.1) obtained from the papers 2. to 9.

[7] L

x(c) t

4. 1

 1 Disintegration with respect to M (i) n α (M ≥ a) = a -2α ; (4.1) (ii) Conditionally on M = a, {ε(u), u ≤ V (ε)} may be obtained by putting two independent BES (α) processes back to back, up to their first hitting times of a, where BES(α) denotes the Bessel process started at level 0, with positive index α, or dimension d = 2(1 + α) > 2.

2 .

 2 Gradinaru-Roynette-Vallois-Yor ([7]; p.538); 3. Borodin-Salminen ([3], p.80); 4. Chaumont-Yor : Exercises in Probability ([4]), Exercise 4.19, p.114; 5. Barlow-Pitman-Yor ([1], p.299); 6. Biane-Yor ([2], p.44, (3.f)); 7. Pitman-Yor ([11], p.300); 8. Donati-Martin-Yor ([5]) 9. Molchanov-Ostrovskii ([10])

t = 2

 2 -α Γ(1 + α)L t

Acknowledgement : We thank the referee for his constructive suggestions which helped to improve our paper.


A Benabid
email: abir.benabid@lip6.fr

C Hanen

Worst case analysis on modulo scheduling for specialized processors systems

Keywords: Cyclic scheduling, Specialized processors, Performance bound

The problem of cyclic scheduling for specialized processors systems is presented and a worst case analysis of a heuristic scheduling algorithm is studied. A resource constrained cyclic scheduling problem is characterized by k, the number of types of functional units employed, mx the maximal number of processors of the same type and δ the maximal precedence delay. The main problem is to cope with both precedence and resource constraints which make the problem N P-complete in general. A guaranteed approach, called decomposed software pipelining, has been proposed by Gasperoni and Schwiegelshohn, followed by the retiming method by Calland, Darte and Robert to solve the problem for parallel processors. We present, in this paper, an extension of this approach to resource-constrained cyclic scheduling problems with precedence delays and we provide an approximation algorithm. Let λ and λ opt be respectively the period given by the algorithm and the optimal period. We establish the bound:

Mots-Clefs.

Introduction

Cyclic scheduling problems have numerous practical application in production systems [START_REF] Proth | Modlisation, analyse et optimisation des systmes fonctionnement cyclique[END_REF] as well as in embeded systems [START_REF] Hanen | Cyclic scheduling on parallel processors: An overview[END_REF]. Our research in this field is partically motivated by the advances in hardware technology, but our results still available for mass production systems.

Embedded architectures used for devices such as mobile, automotive and consumer electronics need high performance, low silicon implementation costs, low power consumption and rapid development to ensure minimum time-to-market. Most of todays heigh performance applications uses instruction level parallel processors such as VLIW processors [START_REF]Proceedings of the 26th Annual International Symposium on Microarchitecture[END_REF].

VLIW architectures are mainly used for media processing in embedded devices, and instruction schedules produced by the compiler is a performance critical optimization that has a direct impact on the overall system cost and energy consumption. High-quality instruction schedules enable to reduce the operating frequency given real-time processing requirements. Most of the parallelism present in these systems is expressed in the form of loops.

In this paper, we consider a loop composed of many unit processing tasks that are to be executed a large number of times. Instruction scheduling for inner loops is also known as software pipelining [START_REF] Allan | Software pipelining[END_REF] and can be modelised by a cyclic scheduling problem. Among the different cyclic scheduling frameworks, modulo scheduling [START_REF] Rau | Iterative modulo scheduling: an algorithm for software pipelining loops[END_REF] is the most successful in production compilers. The modulo scheduling focuses on finding a periodic schedule with the minimal period λ.

The classical results of modulo scheduling apply to problems that are too limited to be of practical use in instruction scheduling in modern processors as well as in mass production problems. For example, these results assume simple precedence constraints on tasks in a schedule, instead of precedences with delays like those in pipelined processors, and focus on machine models where each operation uses one of m identical processors for its execution.

In order to model the software pipelining problem, [START_REF] Artigues | Resource-Constrained Project Scheduling: Models, Algorithms, Extensions and Applications[END_REF] proposes an extension of the classic modulo scheduling problem to resource-constrained modulo scheduling problems with precedence delays where the resources are adapted from the renewable resource of the resourceconstrained scheduling problem [START_REF] Brucker | Resourceconstrained project scheduling: Notation, classification, models, and methods[END_REF].

We define, in this paper, a special case of this problem where the processing times as well as the resource demand is unitary, and we present a guaranteed algorithm for these problems.

Problem formulation

An instance of a resource-constrained cyclic scheduling problem can be defined by:

-An architecture model defined by

P = {P (i,j) \1 ≤ i ≤ k, 1 ≤ j ≤ m i },
where k denotes the number of different types of processors and m i denotes the number of type i processors.

Let

m x = max 1≤r≤k m r .
-Precedence graph G(V, E) where:

• V is a set of n tasks V = {T i } 1≤i≤n with unit processing time. To each task T i is associated a binary vector {b i r } 1≤r≤k over the resource types, such that T i uses b i r units of resource of type r during its execution.

• E is a set of edges defining uniform dependence relations denoted by T i lij ,hij -→ T j , where the delay l ij and the height h ij are positive integers. l ij and h ij model the fact that the task T j at iteration q has to be issued at least l ij time units after the start of task i in iteration q -h ij . We denote by δ = max

(Ti,Tj )∈E l ij .
Notice that this model generalize the classical parallel processors statements (in which k = 1 -i.e. there is a unique type of processors) as well as typed tasks systems where each binary vector {b i r } 1≤r≤k has only one positive component. Let us illustrate the notions of tasks, iterations, latencies and heights with the following example. We will work on this example throughout the paper.

The loop has n = 7 tasks, each one is executed N times. N is a given parameter representing the number of iterations and can be very large. The associated precedence graph G(V, E) is given in Figure 1. Values of l ij and h ij are displayed next to the corresponding arc. The resource request {b i 1 , b i 2 } of each task T i is highlighted next to the corresponding node.

for 1 ≤ i ≤ N do (T 1 ) : t 1 (i) = t 3 (i) (T2) : t2(i) = t3(i) (T 3 ) : t 3 (i) = t 2 (i -3) (T4) : t4(i) = t2(i -1) (T 5 ) : t 5 (i) = t 4 (i -2) + t 2 (i -1) + t 7 (i) (T 6 ) : t 6 (i) = t 5 (i -1) (T 7 ) : t 7 (i) = t 6 (i -1)
Fig.

1

. An example of precedence graph G(V, E).

A resource-constrained cyclic scheduling problem is to find a schedule σ that assigns an issue time σ(T i , q) for each task occurence (T i , q) such that for all r ∈ {1, • • • , k} the number of tasks issued on processors of the same type r is at most equal to m r , and

T i l ij ,h ij -→ T j ⇒ σ(T i , q) + l ij ≤ σ(T j , q + h ij ) ∀q ∈ N
The modulo scheduling focuses on finding a periodic schedule with the minimal period λ such that:

∀i ∈ {1, • • • , n}, ∀q ∈ N : σ(T i , q) = σ(T i , 0) + q • λ
Periodic schedules are of high interest from a practical point of view, because their representation is compact so that they can be easily implemented in real systems.

Decomposed software pipelining

Generating an optimal resource constrained cyclic scheduling with minimal period is known to be N P-hard. To overcome this N P-hardness, we used the decomposed software pipelining approach introduced simultaneously by Gasperoni and Schwiegelsohn [START_REF] Gasperoni | Generating close to optimum loop schedules on parallel processors[END_REF], and by Wang, Eisenbeis, Jourdan and Su [START_REF] Wang | Decomposed software pipelining: a new perspective and a new approach[END_REF]. The main idea is to decouple the problem into dependence constraints and resource constraints so as to decompose the problem into two subproblems: a cyclic scheduling problem ignoring resource constraints, and a standard acyclic graph for which efficient techniques are known.

Gasperoni and Schwiegelshohn give an upper bound to the period λ for the problem with m identical processors and precedences without latencies. Let λ opt be the optimal (smallest) period. For unit execution tasks, this bound is given by the following inequality:

λ ≤ (2 - 1 m
)λ opt [START_REF] Calland | Circuit retiming applied to decomposed software pipelining[END_REF] presents a heuristic based on circuit retiming algorithms to generalize the efficiency bound given for Gasperoni-Schwiegelshohn algorithm. The main idea is to use a retiming R to decide which edges to cut in G(V, E) so as to make it acyclic.

R : V → Z, ∀(i, j) ∈ E, R(j) + h ij -R(i) ≥ 0 A legal retiming for G of Figure 1 is given in Table 1 Table 1. A retiming R of G. Tasks T1 T2 T3 T4 T5 T6 T7 R 0 1 0 2 2 0 1
Then, we define the acyclic graph G R by keeping only the arcs of G for which R(j) + h ij -R(i) = 0. We add two pseudo-tasks with null processing times and no resource use Start and Stop:

-Start is a predecessor of each task with l Start,i = 0, ∀i ∈ E.

-Stop is a successor of each task with l i,Stop = max

j∈Succ(i) l ij , ∀i ∈ E.
Let π R be any (non cyclic) schedule of G R that fulfills the resource constraints as well as the precedences induced by G R then, setting λ R = π R Stop and for any task

T i , σ R (T i , q) = π R i + (q + R(T i ))λ R
, we get the following result:

Lemma 1. σ R is a feasible periodic schedule of G with period λ R .
Proof. Now, the idea, previously used by [START_REF] Gasperoni | Generating close to optimum loop schedules on parallel processors[END_REF] and [START_REF] Calland | Circuit retiming applied to decomposed software pipelining[END_REF] is to choose a particular retiming and use a guaranteed algorithm to get a schedule π R of G R , and then to extend the guarantee to the induced periodic schedule.

List scheduling algorithms are the most used heuristics for scheduling with precedence and resource constraints. Chou, in [?] proves that for specialized processors with precedence delays these algorithm have the following worst case performance:

C max ≤ (k + 1 - 1 m x (δ) )C opt max
We thus propose the following generic algorithm 1 to solve our problem, by using a list algorithm to produce π R . Figures 2 and3 illustrate the algorithm on our example. The acyclic graph provided by the retiming R is given by Figure 2 and its corresponding list scheduling allocation is presented in Figure 3. The makespan of this pattern is λ R = 8 and it gives the period of the modulo scheduling of G. The different steps of this heuristic are illustrated by the following algorithm.

Worst case analysis

In this section we analyze the worst case performance of algorithm 1 in general, making use of the proof of Chou [?] for list scheduling. Then, we show that using some particular retiming, that can be computed in polynomial time, we can get an overall guarantee for the Extended DSP algorithm.

Minimal length of pattern

Consider a dependence graph G. An acyclic graph G R is obtained by a retiming R. Then, we schedule G R by a list algorithm and generate a pattern π R . We note φ R the length (sum of the delays) of the longest path in G R . Let λ opt be the optimal period of G.

Algorithm 1: Extended DSP 1. Find a legal retiming R for G; 2. for (T i , T j ) ∈ E do if R(T j ) -R(T i ) + h ij = 0 then keep (T i , T j ) in G R ;
R = Cmax(G R ) = π R Stop ; 4. Define the cyclic schedule σ R by: for 1 ≤ q ≤ N do for T i ∈ V do σ R (T i , q) = π R i + λ R (q + R(T i )) ;
We consider two type of bounds obtained from resource and precedence constraints.

Resource bound :

Lemma 2. For each type i, let u i and m i be respectively the number of tasks using resource type i and the number of machines of type i. Then,

λ opt ≥ max 1≤i≤k u i m i .
Proof. The shortest time required to complete the tasks of type i is u i m i . Furthermore, the length of the optimal period λ opt is not shorter than the time required to schedule any type of tasks. Hence, λ opt ≥ max 1≤i≤k u i m i .

P recedence bounds on schedule π R : Let π R be a schedule induced by a list algorithm on G R . In order to reveal the dependencies among tasks, we classify the time slots into three kinds:

1. A full slot t f is a time slot in which at least all the processors of a certain type are executing tasks. 2. A partial slot t p is a time slot in which at least one processor of each type is idle. 3. A delay slot t d is a time slot in which all processors are idle.

We note:

-p: the number of partial slots in π R .

-d: the number of delay slots in π R .

Lemma 3. The partial-slots lemma:

If π R contains p partial slots and d delay slots, then φ R ≥ p + d.

Proof. We prove this lemma by finding a chain h =< T j1 , • • • , T jc > in π R such that the length of h is at least equal to p + d.

Let T jc = Stop and assume that we already have a chain

< T ji+1 , • • • , T vc >. Consider, if it exists, the predecessor T vi of T ji+1 such that π R ji + l ji,ji+1
is maximum.

The construction of h leads to the following observation: All the slots before π R j 1 or between π R ji + l ji,ji+1 and π R ji+1 (if they exist) are full slots and in which there is no available processor in a type of resource used by T ji+1 . Otherwise, T ji+1 would have been scheduled earlier by the list algorithm.

Therefore, all the p partial slots and d delay slots are covered by the intervals [π R v i , π R j i + l j i ,j i+1 ), so that the length of h not less than p + d. Thus, φ R ≥ p + d. Lemma 4. The delay-slots lemma:

If π R contains d delay slots, then φ R ≥ d + d δ -1 .
Proof. The schedule is computed by a list algorithm, then the number of any consecutive delay slots is not greater than δ -1. Consider the chain h defined in the previous lemma.

All the delay slots are included in

∪ 1≤i≤c-1 [π R j i + 1, π R j i + l j i ,j i+1 ), since at time π R j i , T j i is performed. Now the length of each interval [π R j i + 1, π R j i + l j i ,j i+1 ) is less than δ -1. So that c(δ -1) ≥ d.
The length of h is thus not less than d plus the number of the chained tasks c,

which is greater than d δ -1 . Thus, φ R ≥ d + d δ -1 .

Performance bound

Here we define the notations to be used below:

M = 1≤i≤k m i .
u i : the number of tasks using resources of type i. v i : the number of tasks using resources of type i which are scheduled in partial slots in π R . V = ∪ 1≤i≤k v i : the set of tasks which are scheduled in partial slots in π R .

Consider the pattern π R :

M λ R = number of non-idle cycles + number of idle cycles.

where the second term on the right hand side is composed of the number of idle cycles associated with t f , those associated with t d and those associated with t p .

1. The number of idle cycles per processor associated with t d is equal to M d.

2. The number of idle cycles per processor associated with t p is at most equal to M p -|V |.

3. Using Lemma 2, the number of idle cycles associated with t f is bounded by the following value:

≤ 1≤i≤k (M -m i ) u i -v i m i ≤ 1≤i≤k (M -m i ) u i m i - 1≤i≤k (M -m i ) v i m i ≤ 1≤i≤k (M -m i ) max 1≤i≤k u i m i -(M -m x ) |V | m x ≤ (kM -M )λ opt -(M -m x ) |V | m x
Then,

M λ R ≤ M λ opt + (kM -M )λ opt -(M -m x ) |V | m x + M p -|V | + M d ≤ kM λ opt -(M -m x ) |V | m x + M p -|V | + M d ≤ kM λ opt -M |V | m x + M p + M d
|V | is the number of tasks scheduled in the partial slots, since each partial slot contains at least one task, |V | ≥ p. Thus,

λ σ ≤ kλ opt - p m x + p + d ≤ kλ opt + (1 - 1 m x )(p + d) + 1 m x d ≤ kλ opt + (1 - 1 m x )(p + d) + 1 m x δ -1 δ δ δ -1 d ≤ kλ opt + (1 - 1 m x )(p + d) + 1 m x δ -1 δ (d + d δ -1 )
From Lemmas 3 and 4, we have φ

R ≥ p + d and φ R ≥ d + d δ -1 . Then, λ R ≤ kλ opt + (1 - 1 m x )φ R + 1 m x δ -1 δ φ R ≤ kλ opt + (1 - 1 m x δ )φ R Theorem 1 Consider a dependence graph G. Let R be a legal retiming R on G and φ R the length of the longest path in G R . Then, λ R λ opt ≤ k + (1 - 1 m x δ ) φ R λ opt .

Choosing a good retiming

In order to improve the performance bound, it seems important to minimize the ratio between φ R and λ opt . So if we have a good lower bound LB of λ opt , using theorem 7 in [START_REF] Leiserson | Retiming synchronous circuitry[END_REF], we can verify the existence of a legal retiming R such that φ R ≤ LB ≤ λ opt . If such retiming exists, we have a performance guarantee of:

λ R λ opt ≤ k + 1 - 1 m x δ .
An another approach consist on minimizing the length of the longest path in the pattern. There are well-known retiming algorithms [START_REF] Leiserson | Retiming synchronous circuitry[END_REF] to minimize φ R . Let R opt a retiming for which the length of the longest path in the acyclic graph G R opt is minimal. We note it φ opt . We also denote by σ ∞ an optimal periodic schedule for unlimited resources (with period λ ∞ ).

Lemma 5.

λ

∞ + δ -1 ≥ φ opt .
Proof. Consider an optimal cyclic schedule σ ∞ for unlimited resources. Let us define r :

V → [0, λ ∞ -1] and R : V → Z such that: σ ∞ (i, q) = r(i) + λ ∞ (q + R(i)), ∀i ∈ V, ∀q ∈ N
Then, the precedence constraint for each edge (i, j) ∈ E is: σ ∞ (i, q) + l ij ≤ σ ∞ (j, q + h ij ) r(i) + λ ∞ (q + R(i)) + l ij ≤ r(j) + λ ∞ (q + h ij + R(j)) r(i) + l ij ≤ r(j) + λ ∞ (h ij + R(j) -R(i)) [START_REF] Calland | Circuit retiming applied to decomposed software pipelining[END_REF] proved that R defines a valid retiming for G. Furthermore, G R is obtained by keeping the edges of G for which R(j) + h ij -R(i) = 0. Thus ,

r(i) + l ij ≤ r(j), ∀(i, j) ∈ E Let h =< T j1 , • • • , T jc , Stop > be a chain in G R .
l j c k φ R -max k∈Succ(Tj c ) l j c k ≤ r(j c ) φ R -δ ≤ λ ∞ -1
Hence, φ R -δ ≤ λ ∞ -1 and since φ opt ≤ φ R , we have the desired result.

Finally, using theorem 1 applied to R opt , we have

λ Ropt ≤ kλ opt + (1 - 1 m x δ )φ opt ≤ kλ opt + (1 - 1 m x δ )(λ ∞ + δ -1) ≤ kλ opt + (1 - 1 m x δ )(λ opt + δ -1) ≤ (k + 1 - 1 m x δ )λ opt + (1 - 1 m x δ )(δ -1)
Theorem 2

λ Ropt ≤ (k + 1 - 1 m x (δ + 1) )λ opt + (1 - 1 m x (δ + 1)
)(δ -1).

3 Conclusion

Fig. 2 .

 2 Fig. 2. The acyclic graph given by the retiming R.

Fig. 3 .

 3 Fig. 3. A pattern generated by a list scheduling of G R : λ R = 8.

  r(j i ) + l ji,ji+1 ≤ r(j i+1 ), ∀i ∈ {1, • • • , c -1},By summing up these c -1 inequalities, we haver(j 1 ) + c-1 i=1 l ji,ji+1 = r(j c ) Thus, r(j 1 ) c-1 i=1 l j i ,j i+1 ≤ r(j c ) c-1 i=1 l j i ,j i+1 ≤ r(j c )This inequality is true for any chain of G R in particular for the longest path in G R . Hence, c-1 i=1 l j i ,j i+1 + max k∈Succ(Tj c )

  add nodes Start and Stop; 3. Perform a list scheduling on G R coping with both precedence and resource constraints.Compute π R i the start time of task Ti in this schedule and λ


Claire Hanen
email: claire.hanen@lip6.fr

Alix Munier-Kordon

Equivalence of two classical list scheduling algorithms for dependent tasks with release dates and due dates on parallel processors

Keywords: scheduling, release dates, due dates, list scheduling 1 Introduction

HAL is a

i.e, the modified due dates produced by one of the algorithm are consistent with respect to the other algorithm. The consequence is that all the results obtained in the literature for one of these algorithm are also valid for the other one for this basic problem.

Problem definition and notations

The scheduling problem tackled by this talk is the optimization problem P |prec, p i = 1, r i , d i | L max and its corresponding decision problem P |prec, p i = 1, r i , d i | . The set of tasks is noted T and n = |T |. With each task i are given a release time r i , a due date d i , and its unit processing time p i = 1.

The cyclic precedence graph is noted G = (T , E). We denote i → j if there is a path from i to j in G. j ∈ Indep(i) if neither i → j nor j → i. A schedule defines for each task i a completion time C i . We assume without loss of generality that release times are consistent with precedence constraints, i.e, if i → j then r i < r j .

The question addressed by the decision problem is: "is there a schedule on m parallel processors satisfying the precedence constraints such that ∀i ∈ T , r i < C i ≤ d i ? ". The optimization problem can be stated as follows : "construct a schedule on m parallel processors satisfying the precedence constraints such that ∀i ∈ T , r i < C i and minimizing the maximum lateness

L max = max i∈T C i -d i ".
3 The GJ and the LPP consistency GJ and LPP algorithms modify due dates until a fixed point

D = (D 1 , • • • , D n ) ≤ (d 1 , . . . d n ) is reached,
expressing in both cases necessary conditions for the existence of a feasible schedule. This fixed point rely on two notions of consistency of due dates described in the following.

GJ consistency

Let consider, for each task i ∈ T and each tuple (s, d) such that r i ≤ s ≤ D i ≤ d, the set S(i, s, d) = {j ∈ T , j = i, D j ≤ d, and (r j ≥ s or i → j)}.

Obviously, all tasks from S(i, s, d) should end before d. Now, let suppose that task i ends exactly at its due date D i . If D i = s, all tasks from S(i, s, d) have to be performed in the time interval [s, d). Otherwise, D i > s and S(i, s, d) ∪ {i} have to be performed in the time interval [s, d).

The notion of GJ consistency derives from this intuition. The due dates

D 1 , • • • , D n are GJ-consistent if ∀i ∈ T , r i < D i and either |S(i, s, d)| < m(d -s) or |S(i, s, d)| = m(d -s) and s = D i .

LPP consistency

Let i ∈ T and T i = Indep(i) ∪ {j ∈ T , i → j}. Let also release and due dates vectors r and d and a value t ∈ {r i + 1, • • • , d i }. Then, Existence i (t, r, d) defined as follows is a necessary condition for the existence of a feasible schedule such that i ends at time t.

Existence i (t, r, d): is there a schedule on m processors of T i ∪ {i} considered as independent tasks meeting release dates r and due dates d defined as follows:

1. d i = t and ∀j ∈ T i , d j = d j 2. r i = t -1; ∀j ∈ Indep(i), r j = r j 3. ∀j ∈ T with i → j, r j = max(r j , t + 1).
Let us denote by BS i (r, d) the maximal integer t ≤ d i for which the answer for Existence

i (t, r, d) is yes. The due dates D = (D 1 , • • • , D n ) are LPP-consistent if for any task i ∈ T , BS i (r, D) = D i .
Notice that list scheduling can be used to decide wether Existence i (t, r, d) is satisfiable.

Lemma 1 The problem Existence i (t, rd) can be decided by fixing the starting time of i to be t -1 and then scheduling the tasks of T i as if they were independent with their modified due-dates and release times using a list scheduling algorithm based on the priorities of the due-dates in increasing order.

Equivalence of due dates consistency and consequences

Our main theorem establishing the equivalence between GJ and LPP consistencies is first presented. Its consequences are then detailed from both an algorithmic and a theoretical point of view.

Equivalence between GJ and LPP consistencies

The next theorem establishes the equivalence between the two due dates consistencies and constitutes the central result of our talk. The main idea of its proof is to show that any vector D verifying one property also fulfills the other.

Theorem 1 Let consider an instance of the problem P |prec, p i = 1, r i , d i | and let a vector

D i ≤ d i , ∀i ∈ T . D is GJ-consistent if and only if D is LPP-consistent.
To prove this theorem, we proceed step by step, by first showing that any LPP-consistent due dates are GJ-consistent.

Lemma 2 Let D be a vector of LPP-consistent due-dates. Then D is GJ-consistent.

Proof. Let us assume that D is not GJ-consistent. Then, there exists a task i, and two integers s, d with r i ≤ s ≤ D i ≤ d, such that the set S(i, s, d) is two large. Assume first that s < D i . then |S(i, s, d)| ≥ m(D i -s). Now, let us notice that S(i, s, d) ⊂ T i . Moreover, if we consider the modified due dates and release times for checking Existence i (D i , r, D) (whose answer is yes), all successors j of i have a modified release time r j = D i > s. Hence, in the schedule build to check Existence i (D i , r, D), all tasks from S(i, s, d) are scheduled in the interval [s, d]. Moreover, i ∈ S(i, s, d) is also scheduled during [s, d]. As there are at least m(d -s) + 1 such tasks, we get a contradiction.

Lemma 3 Let D be a vector of GJ-consistent due-dates. Then D is LPP-consistent.

Proof.

Both GJ and LPP consistencies are sufficient to obtain optimization and approximation results. Thus, a simple outcome of Theorem 1 is that any result obtained for one of these priority list is still valid for the other one. They are listed in the following.

Complexity of GJ and LPP list scheduling algorithms for solving a decision problem or minimizing the maximum lateness

From a complexity point of view, LPP algorithm is slightly better than GJ one. Indeed, it computes consistent modified due dates in a time complexity O(n 2 lognα(n) + ne) where e is the number of edges of G and α(n) functional inverse of the Ackermann function. GJ algorithm computes consistent modified due dates in O(n 3 logn).

Concerning the optimization problem, several authors (Leung et. al. 2001, Hanen and[START_REF] Hanen | The worst-case analysis of the Garey-Johnson Algorithm[END_REF]) observed that a polynomial-time algorithm minimizing the maximum lateness can be obtained using a due date modification and a list scheduling algorithm as follows:

step 1: Compute by binary search the minimum ∆ such that a set of consistent due dates D can be computed from due dates d + ∆;

step 2: Perform a list schedule of the graph G according to the priorities given by the due dates D.

According to Theorem 1, GJ or LPP consistencies may be considered without influence on the quality of the solution obtained. Now, LPP should be preferred for implementations issues as noted before.

Theoretical consequences of Theorem 1

GJ consistency was exploited by several authors to obtain approximation algorithms for minimizing the maximum lateness, using the scheme described previously. Theorem 2 was proved by [START_REF] Hanen | The worst-case analysis of the Garey-Johnson Algorithm[END_REF] and is true for the two optimization algorithms by Theorem 1.

Theorem 2 An upper-bound of the maximum lateness L max of the solution obtained using a LPP or GJ consistency-based algorithm for the problem P |prec,

p i = 1, r i , d i | L max is L max ≤ (2 - 2 u(m) )L max (σ ) + (1 - 2 u(m) ) max i∈N d i -(1 - 2 u(m) )
where L max (σ ) is an optimum schedule and

u(m) = m if m is even, m + 1 if m is odd.
Notice that as L max (σ ) may be null; the performance guarantee of an algorithm always involves an additive term depending on the maximum due date.

On the other hand, LPP algorithm was considered to get polynomial-time algorithms minimizing the maximum lateness or the makespan. Theorem 3 is a consequence of [START_REF] Leung | Scheduling time-constrained instructions on pipelined processors[END_REF] who proved that the LPP list scheduling algorithm can be used to solve optimally various sub cases of P |prec, p i = 1, r i , d i | L max and of Theorem 1.

Theorem 3 Scheduling problems P |p i = 1, interval -order, r i |L max , P |p i = 1, intervalorder, r i |C max , P 1|p i = 1, prec, r i |L max , P |p i = 1, intree|L max and P |p i = 1, outtree, r i |C max are solved polynomially using a GJ or a LPP consistency-based list scheduling algorithm.

Conclusion and further approach

We show that the structural equivalence between the two consistencies leads to a unification of the results proved for each of them. First consequences are a more efficient approximation algorithm with the same worst case performance guarantee to minimize the maximum lateness on parallel processors and some new optimality results for the GJ list scheduling algorithm.

This equivalence should be further investigated for variants of the initial problem: precedence delays, communication delays, typed tasks systems, and preemptive tasks. If, as we conjecture, the equivalence can be proved also in such contexts, other optimality and approximation results will be derived for both algorithms.

We also hope that a careful investigation of the two algorithms may lead to a more efficient algorithm taking the best of both.

One can also think that the due date modification algorithm could be used reversely to modify release times on the reverse graph, and iterate until a fixed point is reached. The question is then to evaluate if a better worst case performance ratio may be achieved.


Claire Hanen

Grouping tasks to save energy in a cyclic scheduling

problem: a complexity study

Grouping tasks to save energy in a cyclic scheduling problem: a complexity study

Claire Hanen 1 , 2 and Zdenek Hanzalek 3

1 University Paris-Ouest Nanterre, 92000 Nanterre (France) 2 LIP6 UPMC, 5 place jussieu, 75252 Paris Cedex 05 (France) claire.hanen@lip6.fr 3 Czech Technical University in Prague, Faculty of Electrical Engineering hanzalek@fel.cvut.cz

Mots-clés : cyclic scheduling, energy saving 1 Motivation

In order to improve the functionality and efficiency of industrial monitoring and control systems, the industries are looking toward Wireless Sensor Networks (WSNs), especially in environments where electricity is not available. So, saving energy is an important tradeoff in such systems. The IEEE 802.15.4/ZigBee [START_REF]Part 15.4 : wireless medium access control (MAC) and physical layer (PHY) specifications for low-rate wireless personal area networks (LR-WPANs)[END_REF][6] standards are leading technologies for low-cost, low-power and low-rate WSNs.

In the beacon-enabled variant, a network of clusters in a tree-shape is considered, which leaves are sensors. The communications between sensors are given by a set of data flows through the network. The data flows repeat periodically, but as clusters cannot tranfer more than one data at the same time, two independent flows may induce a collision in a cluster and one of them should be delayed. Thus, the key problem is to find a periodic schedule which specifies when the clusters are active and transfer data while avoiding possible inter-cluster collisions and meeting all flows end-to-end deadlines, expressed by a bound on the number of periods needed to acheive the data flow.

But we need to consider the energy efficiency. The Zigbee standard [6] specifies that each cluster is active only once during the period, so that during a period, all tasks of the data-flows passing through a cluster are grouped. Consequently not every instance has a fasible solution meeting all the requirements.

This motivating problem led us to address the more general problem setting where a cyclic dependence graph with uniform constraints is to be scheduled so that some tasks are grouped in order to save energy. Notice that the grouping constraints apply to the core of the periodic schedule, i.e. that they may involve tasks of different iterations. We consider the feasibility of such a system, and we prove that even if no resource constraints are considered, this problem is N P -complete. We then investigate the ZigBee special case.

Problem setting

We are given a graph G of uniform constraints with unit length and nonnegative heights : each arc (i, j) of G is characterized by an integer height h ij , that indicates that for any integer k the k th occurrence of i precedes the k +h th ij occurrence of j. Each task i has a type k i ∈ 1, . . . , K and a unit processing time. A periodic schedule of period λ assigns to each task i a starting time s i so that

∀(i, j) ∈ G, s j -s i ≥ 1 -λh ij (1)
A periodic schedule can also be described by its core σ and its retiming α as follows [3][7] :

α(i) is the largest integer such that s i = σ(i) + λα(i), with σ(i) ∈ [0, λ).
A periodic schedule is said to be grouped if the tasks of the same type are executed close to each other in the core : each group is to be scheduled as a single task in the core schedule. So a grouped schedule associates a starting time t r to each group r in the core. The task i of type r is scheduled at time σ(i) = t r in the core.

We can now state the feasibility problem called U GF : Given a uniform graph and the tasks groups, Does it exist a grouped periodic schedule of G ?

U GF complexity

Grouping constraints might be considered as a special case of core precedence (see [START_REF] Hanzalek | Impact of core precedences in a cyclic rcpsp with temporal constraints[END_REF]) So, they can be easily embedded in an ILP formulation, even with additional resource constraints. However, this formulation does not give an insight on the complexity of the problem U GF , although it can provide solutions for small size problems [START_REF] Dupont De Dinechin | Resource constrained modulo scheduling[END_REF].

But the structure of U GF allows us to formulate it as a graph problem : For a given retiming α, we define G α the sub-graph of G composed with all arcs (i, j) such that h ij + α(j) -α(i) = 0. It is well known [START_REF] Calland | Circuit retiming applied to decomposed software pipelining[END_REF][1] that G α is an acyclic graph.

Let R α be the graph obtained from G α by merging the nodes of the same group. An arc (i, j) of G α results in R α in an arc (k i , k j ).

Notice that even if G α is acyclic, by merging nodes, R α may contain circuits, and in this case, no feasible schedule can be found for this retiming.

So the feasibility problem is to find a retiming vector α such that the resulting grouped graph R α is acyclic.

This property is used to state our main result :

Theorem 1 U GF is NP-Complete

We prove this theorem by an origninal reduction from 3 -SAT . In the last section, we investigate the Zigbee special case, wher there is a special underlying structure for groups and for uniform constraints. We prove some properties of the structure of grouped schedules and provide a polynomial subcase. However, the complexity of this special case is still unknown.


Abir Benabid
email: abir.benabid@lip6.fr

Claire Hanen
email: claire.hanen@lip6.fr

Decomposed software

published or not. The documents may come

Introduction

Cyclic scheduling problems have numerous practical application in production systems [START_REF] Hanen | Modélisation, analyse et optimisation des systèmes à fonctionnement cyclique[END_REF] as well as in embeded systems [START_REF] Hanen | Cyclic scheduling on parallel processors: An overview[END_REF]. Our research in this field is partically motivated by the advances in hardware technology, but our results still available for mass production systems.

⋆ ORCYAE project supported by awards from DIGITEO, a research park in Ile-de-France dedicated to information science and technology.

Embedded architectures used for devices such as mobile, automotive and consumer electronics need high performance, low silicon implementation costs, low power consumption and rapid development to ensure minimum time-to-market. Most of todays high performance applications uses instruction level parallel processors such as VLIW processors [START_REF] Rau | Dynamically scheduled vliw processors[END_REF].

VLIW architectures are mainly used for media processing in embedded devices, and instruction schedules produced by the compiler are a performance critical optimization that has a direct impact on the overall system cost and energy consumption. Highquality instruction schedules enable to reduce the operating frequency given real-time processing requirements. Most of the parallelism present in these systems is expressed in the form of loops.

In this paper, we consider a loop composed of many tasks that are to be executed a large number of times. Instruction scheduling for inner loops is also known as software pipelining [START_REF] Allan | Software pipelining[END_REF] and can be modelised by a cyclic scheduling problem. Among the different cyclic scheduling frameworks, modulo scheduling [START_REF] Rau | Iterative modulo scheduling: an algorithm for software pipelining loops[END_REF] is the most successful in production compilers. The modulo scheduling focuses on finding a periodic schedule with the minimal period λ.

The classical results of modulo scheduling apply to problems that are too limited to be of practical use in instruction scheduling in modern processors as well as in mass production problems. For example, these results assume simple precedence constraints on tasks in a schedule, instead of precedences with delays like those in pipelined processors, and focus on machine models where each operation uses one of m identical processors for its execution.

In order to model the software pipelining problem, [START_REF] Artigues | Resource-Constrained Project Scheduling: Models, Algorithms, Extensions and Applications[END_REF] proposes an extension of the classic modulo scheduling problem to resource-constrained modulo scheduling problems with precedence delays where the resources are adapted from the renewable resource of the resource-constrained scheduling problem [START_REF] Brucker | Resource-constrained project scheduling: Notation, classification, models, and methods[END_REF].

We define, in this paper, a special case of this problem where the resource demands are unitary, and we present a guaranteed algorithm for these problems.

Problem formulation

An instance of a unitary resource-constrained cyclic scheduling problem can be defined by:

-An architecture model defined by

P = {P (i,j) \1 ≤ i ≤ k, 1 ≤ j ≤ m i },
where k denotes the number of different types of processors and m i denotes the number of type i processors. Let mx = max 1≤r≤k mr.

-A set of n tasks V = {T i } 1≤i≤n with integer processing time {p i } 1≤i≤n . To each task T i is associated a binary vector {b i r } 1≤r≤k over the resource types, such that T i uses b i r units of resource of type r during its execution. Notice that a task might use several processors but of different types.

-Each task T i must be performed an infinite number of times. We call T i at iteration q the q-th execution of T i . -Precedence graph G(V, E) where:

-E is a set of edges defining uniform dependence relations denoted by T i lij ,hij -→ T j , where the delay l ij and the height h ij are nonnegative integers. l ij and h ij model the fact that the task T j at iteration q has to be issued at least l ij time units after the end of task i in iteration qh ij .

-We denote ρ = lmax p min where lmax = max (Ti,Tj )∈E l ij and p min = min

1≤i≤n p i .
Notice that this model generalize the classical parallel processors statements (in which k = 1 -i.e. there is a unique type of processors) as well as typed tasks systems where each binary vector {b i r } 1≤r≤k has only one positive component. Let us illustrate the notions of tasks, iterations, delays and heights with the following example. We will work on this example throughout the paper.

F or 1 ≤ i ≤ N (T 1 ) : t 1 (i) = t 3 (i) (T 2 ) : t 2 (i) = t 3 (i) (T 3 ) : t 3 (i) = t 2 (i -3) (T 4 ) : t 4 (i) = t 2 (i -1) (T 5 ) : t 5 (i) = t 4 (i -2) +t 2 (i -1) + t 7 (i) (T 6 ) : t 6 (i) = t 5 (i -1) (T 7 ) : t 7 (i) = t 6 (i -1) Tasks T 1 T 2 T 3 T 4 T 5 T 6 T 7 p i 2 2 3 3 1 1 1 {b i 1 , b i 2 } 1,1 1,1 1,0 1,0 1,1 0,1 1,1
The loop has n = 7 tasks, each one is executed N times. N is a given parameter representing the number of iterations and can be very large, and thus is assumed infinite. The associated precedence graph G(V, E) is given in Figure 1. Values of l ij and h ij are displayed next to the corresponding arc. The resource request {b i 1 , b i 2 } of each task T i is highlighted next to the corresponding node. A resource-constrained cyclic scheduling problem is to find a schedule σ that assigns a starting time σ(T i , q) for each task occurence (T i , q) such that for all r ∈ {1, • • • , k} and for each time s, the number of tasks using processors of type r at time s is at most equal to mr, and

" T i lij ,hij -→ T j « ⇒ σ(T i , q) + p i + l ij ≤ σ(T j , q + h ij ) ∀q ∈ N
The modulo scheduling focuses on finding a periodic schedule with the minimal period λ such that:

∀i ∈ {1, • • • , n}, ∀q ∈ N : σ(T i , q) = σ(T i , 0) + q • λ
Periodic schedules are of high interest from a practical point of view, because their representation is compact so that they can be easily implemented in real systems.

Decomposed software pipelining

Generating an optimal resource constrained cyclic scheduling with minimal period is known to be N P-hard. To overcome this N P-hardness, we used the decomposed software pipelining approach introduced simultaneously by Gasperoni and Schwiegelsohn [START_REF] Gasperoni | Generating close to optimum loop schedules on parallel processors[END_REF], and by Wang, Eisenbeis, Jourdan and Su [START_REF] Wang | Decomposed software pipelining: a new perspective and a new approach[END_REF]. The main idea is to decouple the problem into dependence constraints and resource constraints so as to decompose the problem into two subproblems: a cyclic scheduling problem ignoring resource constraints, and a standard acyclic graph for which efficient techniques are known.

Gasperoni and Schwiegelshohn give an efficiency bound to the period λ for the problem with m identical processors and precedences without delays. Let λ opt be the optimal (smallest) period, this bound is given by the following inequality:

λ ≤ " 2 - 1 m « λ opt + " 1 - 1 m « ( max 1≤i≤n p i -1)
Darte et al. [START_REF] Calland | Circuit retiming applied to decomposed software pipelining[END_REF] presents a heuristic based on circuit retiming algorithms to generalize the efficiency bound given for Gasperoni-Schwiegelshohn algorithm. The main idea is to use a retiming R to decide which edges to cut in G(V, E) so as to make it acyclic. Then, the acyclic makespan minimization problem is solved using any approximated algorithm, that provides a pattern (schedule of a period) for a feasible periodic schedule.

In this paper, we generalize this approach for our problem. Several new elements have to be taken into account: extended resource constraints and arbitrary precedence delays.

We first use the definition of [START_REF] Calland | Circuit retiming applied to decomposed software pipelining[END_REF] for a legal retiming:

R : V → Z, ∀(T i , T j ) ∈ E, R(T j ) + h ij -R(T i ) ≥ 0
A legal retiming for G of Figure 1 is given in Table 1.

Table 1 A retiming R of G.
Tasks

T 1 T 2 T 3 T 4 T 5 T 6 T 7 R(T i ) 0 1 0 2 2 1 1
Then, we define the acyclic graph G R by keeping only the arcs of G for which R(T j )+h ij -R(T i ) = 0. We add two dummy tasks Start and Stop with null processing times and no resource use. For each task T i , we add arcs (Start, T i ) and (T i , Stop) and we define valuations of these new arcs such that:

∀(T i , T j ) ∈ G\G R , l i,Stop + l Start,j ≥ l ij . (1)
Notice that such valuations can be defined as follows for each task T i :

-l Start,i = 0 -l i,Stop = max (Ti,Tj )∈G\G R l ij .
Let π R be any (non cyclic) schedule of G R that fulfills the resource constraints as well as the precedences induced by G R . We note π R i the start time of task T i in this schedule. Then, setting λ R = π R Stop and for any task

T i , σ R (T i , q) = π R i + (q + R(T i )) λ R
we get the following result:

Lemma 1 σ R is a feasible periodic schedule of G with period λ R .
Proof. First, we prove that, at any time slot t, the tasks scheduled at t in σ R meet the resource constraints. We note F t the set of tasks for which one of occurence is scheduled at t. Let T i and T j be two tasks in F t . We note q and q ′ their corresponding

occurences such that σ R (T i , q) ≤ t < σ R (T i , q) + p i , σ R (T j , q ′ ) ≤ t < σ R (T j , q ′ ) + p j . Hence, t = σ R (T i , q) + s = σ R (T j , q ′ ) + s ′ π R i + (q + R(T i )) λ R + s = π R j + `q′ + R(T j ) ´λR + s ′ π R i -π R j + s -s ′ -`R(T j ) -R(T i ) + q ′ -q ´λR = 0. ( 2
) Since π R i + s < π R i + p i ≤ π R Stop = λ R and similarly π R i + s ′ < λ R , -λ R < π R i + s -π R i -s ′ < λ R .
Hence, the equality (2) gives:

π R i + s = π R j + s ′ and R(T i ) + q = R(T j ) + q ′
Hence, T i and T j are performed on the same time slot π R i +s in the acyclic schedule π R . Thus, T j ∈ F π R i +s and then

F t ⊆ F s+π R i Since π R fullfills the resource constraints induced by G R , F π R i
(and then F t ) meets the resource constraints.

For precedence constraints, we need to prove that, ∀(T i , T j ) ∈ E, ∀q ∈ N:

σ R (T i , q) + p i + l ij ≤ σ R (T j , q + h ij ) ⇔ π R i + (q + R(T i )) λ R + p i + l ij ≤ π R j + `q + R(T j ) + h ij ´λR
Hence, we have to verify that inequality (3) is satisfied for each (T i , T j ) in E and for any q

∈ N π R i -π R j + p i + l ij ≤ `R(T j ) -R(T i ) + h ij ´λR . ( 3
) Case 1 : (T i , T j ) ∈ G R Then, R(T j )-R(T i )+h ij = 0. Since π R fullfills the precedence constraints induced by G R , π R i + p i + l ij ≤ π R j . Hence, inequality 3 is satisfied. Case 2 : (T i , T j ) / ∈ G R Thus, R(T j ) -R(T i ) + h ij > 0. And then, using 1 π R i -π R j + p i + l ij ≤ π R i + p i + l i,Stop + l j,Start -π R j As π R j ≥ l j,Start and π R i + p i + l i,Stop ≤ π R Stop , we get: π R i -π R j + p i + l ij ≤ π R Stop ≤ λ R ≤ λ R (R(T j ) -R(T i ) + h ij )
which achieves the proof. Now, the idea, previously used by [START_REF] Gasperoni | Generating close to optimum loop schedules on parallel processors[END_REF] and [START_REF] Calland | Circuit retiming applied to decomposed software pipelining[END_REF] is to choose a particular retiming and use a guaranteed algorithm to get a schedule π R of G R , and then to extend the guarantee to the induced periodic schedule.

List scheduling algorithms are the most used heuristics for scheduling with precedence and resource constraints. Alix et al. [START_REF] Munier | Approximation bounds for a general class of precedence constrained parallel machine scheduling problems[END_REF] prove that such algorithms have the following worst case performance in the case of m identical processors in presence of precedence delays:

Cmax ≤ " 2 - 1 m(ρ + 1) « C opt max
where ρ = lmax p min . For systems with unit execution time tasks and typed processors, Chou and Chung [START_REF] Chou | Upper bound analysis of scheduling arbitrary delay instruction on typed pipelined processors[END_REF] give the following bound:

Cmax ≤ " k + 1 - 1 mx(lmax + 1) « C opt max
We thus propose the following generic algorithm 1 to solve our problem, by using a list algorithm to produce π R .

Algorithm 1: Extended DSP 1. Find a legal retiming R for G; 2. for (T i , T j ) ∈ E do if R(T j ) -R(T i ) + h ij = 0 then keep (T i , T j ) in G R ;
R = Cmax(G R ) = π R Stop ; 4. Define the cyclic schedule σ R by: for 1 ≤ q ≤ N do for T i ∈ V do σ R (T i , q) = π R i + λ R (q + R(T i )) ;
The acyclic graph provided by the retiming R is given by Figure 2 and its corresponding list scheduling allocation is presented in Figure 3. The makespan of this pattern is λ R = 9 and it gives the period of the modulo scheduling of G. The different steps of this heuristic are illustrated by algorithm 1.

Worst case analysis

In this section we analyze the worst case performance of algorithm 1 in general, making use of the proof of Chou and Chung [START_REF] Chou | Upper bound analysis of scheduling arbitrary delay instruction on typed pipelined processors[END_REF] for list scheduling. Then, we show that using some particular retiming, that can be computed in polynomial time, we can get an overall guarantee for the Extended DSP algorithm.

Minimal length of pattern

Consider a dependence graph G. An acyclic graph G R is obtained by a retiming R. Then, we schedule G R by a list algorithm and generate a pattern π R . We note φ R the length (sum of the delays and processing times) of the longest path in G R . Let λ opt be the optimal period of G.

We consider two types of bounds obtained from resource and precedence constraints.

Resource bound

Lemma 2 For each type r, let mr be the number of machines of type r. Then,

λ opt ≥ max 1≤r≤k P n i=1 b i r • p i mr .
Proof. The shortest time required to complete the tasks using resources of type r on a single machine is

n X i=1 b i r • p i .
Hence, on mr parrallel processors, the shortest time required is

P n i=1 b i r • p i mr
. Furthermore, the length of the optimal period λ opt is not shorter than the time required to schedule these tasks once.

P recedence bounds

Let π R be a schedule induced by a list algorithm on G R . In order to reveal the dependencies among tasks, we classify the time slots into three kinds:

1. A full slot t f is a time slot in which at least all the processors of a certain type are executing tasks. 2. A partial slot tp is a time slot in which at least one processor of each type is idle and this slot contains at least one non-idle processor. 3. A delay slot t d is a time slot in which all processors are idle.

We note:

p: the number of partial slots in π R .

d: the number of delay slots in π R .

Lemma 3 The partial-slots lemma:

If π R contains p partial slots and d delay slots, then φ R ≥ p + d.

Proof. We prove this lemma by finding a chain h =< T j1 , • • • , T jc > in π R such that the length of h is at least equal to p + d.

Let T jc = Stop and assume that we already have a chain < T ji+1 , • • • , T jc >. Consider, if it exists, the predecessor T ji of T ji+1 such that π R ji + p ji + l ji,ji+1 is maximum.

The construction of h leads to the following observation: All the slots before π R j1 or between π R ji + p ji + l ji,ji+1 and π R ji+1 (if they exist) are full slots and in which there is no available processor in a type of resource used by T ji+1 . Otherwise, T ji+1 would have been scheduled earlier by the list algorithm.

Therefore, all the p partial slots and d delay slots are covered by the intervals

[π R ji , π R ji + p ji + l ji,ji+1
), so that the length of h is not less than p + d. Thus, φ R ≥ p + d.

Lemma 4

The delay-slots lemma:

If π R contains d delay slots, then φ R ≥ d + ‰ d lmax ı p min .
Proof. The schedule is computed by a list algorithm, then the number of any consecutive delay slots is not greater than lmax. Consider the chain h defined in the previous lemma. All the delay slots are included in

∪ 1≤i≤c-1 [π R ji + p ji , π R ji + p ji + l ji,ji+1 ), since during interval [π R ji , π R ji + p ji ), T ji is performed. Now the length of each interval [π R ji + p ji , π R ji + p ji + l ji,ji+1
) is less than lmax. So it holds that c • lmax ≥ d. The length of h is thus not less than d plus the length of the chained tasks, which is greater than

c • p min ≥ ‰ d lmax ı p min . Thus, φ R ≥ d + ‰ d lmax ı p min .

Performance bound

Here we define the notations to be used below:

M = X 1≤r≤k mr.
ur: the number of non-idle cycles on processors of type r.

vr: the number of non-idle cycles on processors of type r in partial slots in π R . V = X 1≤r≤k vr: the number of non-idle cycles in partial slots in π R .

We now prove a first bound ont the algorithm performance based on the length of the longest path in G R .

Theorem 1 Consider a dependence graph G. Let R be a legal retiming R on G and φ R the length of the longest path in G R . Then,

λ R λ opt ≤ k + " 1 - 1 mx(ρ + 1) « φ R λ opt .
Proof. Consider the pattern π R :

M λ R = number of non-idle cycles + number of idle cycles.

where the second term on the right hand side can be decomposed as the number of idle cycles occurring during delay, partial and full slots.

P 1≤r≤k v i mx ≤ (kM -M )λ opt -(M -mx) V mx Then, M λ R ≤ M λ opt + (kM -M )λ opt -(M -mx) V mx + M p -V + M d ≤ kM λ opt -(M -mx) V mx + M p -V + M d ≤ kM λ opt -M V mx + M p + M d
V is the number of non-idle cycles in partial slots, since a partial slot contains at least one non-idle cycle, V ≥ p. Thus,

λ σ ≤ kλ opt - p mx + p + d ≤ kλ opt + (1 - 1 mx )(p + d) + 1 mx d ≤ kλ opt + (1 - 1 mx )(p + d) + 1 mx d " 1 + p min lmax « 1 1 + pmin lmax ! ≤ kλ opt + (1 - 1 mx )(p + d) + 1 mx " d + ‰ d lmax ı p min « " ρ ρ + 1 « From Lemmas 3 and 4, we have φ R ≥ p + d and φ R ≥ d + ‰ d lmax ı p min . Then, λ R ≤ kλ opt + (1 - 1 mx )φ R + 1 mx ρ ρ + 1 φ R ≤ kλ opt + (1 - 1 mx(ρ + 1)
)φ R

Choosing a good retiming

In order to improve the performance bound, it seems important to minimize the ratio between φ R and λ opt . So if we have a good lower bound LB of λ opt , using theorem 7 in [START_REF] Leiserson | Retiming synchronous circuitry[END_REF], we can verify the existence of a legal retiming R ′ such that φ R ′ ≤ LB ≤ λ opt . If such retiming exists, we have a performance guarantee of:

λ R ′ λ opt ≤ k + 1 - 1 mx(ρ + 1)
.

An another approach consists on minimizing the length of the longest path in the pattern. There are well-known retiming algorithms [START_REF] Leiserson | Retiming synchronous circuitry[END_REF] to minimize φ R . Let R opt be a retiming for which the length of the longest path in the acyclic graph G Ropt is minimal. We note it φ opt . We also denote by σ∞ an optimal periodic schedule for unlimited resources (with period λ∞). Proof. Consider an optimal cyclic schedule σ∞ for unlimited resources. Let us define r : V → [0, λ∞ -1] and R : V → Z such that:

σ∞(T i , q) = r(T i ) + λ∞ (q + R(T i )) , ∀T i ∈ V, ∀q ∈ N
Then, the precedence constraint for each edge (T i , T j ) ∈ E is:

σ∞(T i , q) + p i + l ij ≤ σ∞(T j , q + h ij ) r(T i ) + λ∞ (q + R(T i )) + p i + l ij ≤ r(T j ) + λ∞ `q + h ij + R(T j ) ŕ(T i ) + p i + l ij ≤ r(T j ) + λ∞ `hij + R(T j ) -R(T i ) [10]
proved that R defines a valid retiming for G. Furthermore, G R is obtained by keeping the edges of G for which R(T Hence, φ Rδ ≤ λ∞ -1 and since φ opt ≤ φ R , we have the desired result.

j ) + h ij -R(T i ) = 0. Thus , r(T i ) + p i + l ij ≤ r(T j ), ∀(T i , T j ) ∈ E Let h =< T j1 , • • • , T jc , Stop > be a chain in G R .
Finally, from lemma5, we deduce our last performance ratio.

Theorem 2 Consider a dependence graph G. Let R opt be a retiming on G that minimize the length of the longest path in R . Then,

λ Ropt ≤ " k + 1 - 1 mx(ρ + 1) « λ opt + " 1 - 1 mx(ρ + 1)

«

(δ -1).

Proof. Using theorem 1 applied to R opt , we get:

λ Ropt ≤ kλ opt + (1 - 1 mx(ρ + 1)
)φ opt ≤ kλ opt + (1 -1 mx(ρ + 1)

)(λ ∞ + δ -1)

≤ kλ opt + (1 -1 mx(ρ + 1)

)(λ opt + δ -1)

≤ (k + 1 - 1 mx(ρ + 1)
)λ opt + (1 -1 mx(ρ + 1)

)(δ -1)

Conclusion

Instruction scheduling, which takes place when compiling applications for modern processors, affects critically the performance of the the overall system cost and energy consumption.

In this paper, we presented a generalized model of instruction scheduling but our results are still available for applications in production systems problems.

We have built upon results of [START_REF] Gasperoni | Generating close to optimum loop schedules on parallel processors[END_REF][START_REF] Calland | Circuit retiming applied to decomposed software pipelining[END_REF][START_REF] Chou | Upper bound analysis of scheduling arbitrary delay instruction on typed pipelined processors[END_REF] and extended them to propose a guaranteed heuristic for unitary resource-constrained modulo scheduling problems. A worst case analysis of this heuristic is explored and a performance bound is established. It is the first guarantee derived for cyclic scheduling problems in the case of many different resources.

Fig. 1

 1 Fig. 1 An example of precedence graph G(V, E).

Fig. 2

 2 Fig.2The acyclic graph given by the retiming R.

Fig. 3 A

 3 Fig. 3 A pattern generated by a list scheduling of G R : λ R = 9.

Lemma 5

 5 Let δ = max (Ti,Tj )∈E (p i + l ij ) be the maximum scope in G. Then, λ∞ + δ -1 ≥ φ opt .

-

  r(T ji ) + p ji + l ji,ji+1 ≤ r(t ji+1 ), ∀i ∈ {1, • • • , c -1},By summing up these c -1 inequalities, we haver(T j1 ) + c-1 X i=1 (p ji + l ji,ji+1 ) ≤ r(T jc ) Thus, c-1 X i=1 (p ji + l ji,ji+1) ≤ r(T jc ). This inequality is true for any chain of G R in particular for the longest path in G R . Hence, c-1 X i=1 (p ji + l ji,ji+1 ) + (p jc + l jc,Stop ) (p jc + l jc,Stop )

  1. The number of idle cycles per processor occurring during delay slots is equal to M d. 2. The number of idle cycles per processor occurring during partial slots is at most equal to M p -V . 3. Using Lemma 2, we now give a bound on the number of idle cycles occurring during full slots.Notice that for a resource type r, there are at most urvr mr full slots in which resource r is full. Thus the number of idle cycles in these slots is at most (M -

	mr) ≤ ≤ ≤	ur -vr mr X (M -mr) . Hence we get: ur -vr mr 1≤r≤k X 1≤r≤k (M -mr) ur mr -1≤r≤k X X 1≤r≤k (M -mr) max 1≤r≤k P n i=1 b i (M -mr) r • p i mr -(M -mx) vr mr

We point out that it would be interesting to derive algorithms more sophisticated than list scheduling to improve this performance bound.

Finally, it would be worth to study the importance of choosing a good retiming and its impact on the performance guarantee. Good lower bounds for the optimal period would give a better guarantee.