N Bachelard

C Garay

J Arlandis

R Touzani

P Sebbah

Coalescence of Anderson-localized modes at an exceptional point in 2D random media

Keywords: numbers: 42.25.Bs, 71.23.An, 71.70.Gm

In non-hermitian systems, the particular position at which two eigenstates coalesce under a variation of a parameter in the complex plane is called an exceptional point. A non-perturbative theory is proposed which describes the evolution of modes in 2D open dielectric systems when permittivity distribution is modified. We successfully test this theory in a 2D disordered system to predict the position in the parameter space of the exceptional point between two Anderson-localized states. We observe that the accuracy of the prediction depends on the number of localized states accounted for. Such an exceptional point is experimentally accessible in practically relevant disordered photonic systems.

Losses are inherent to most physical systems, either because of dissipation or as a result of openness. These systems are described mathematically by a non-hermitian Hamiltonian, where eigenvalues are complex and eigenstates form a nonorthogonal set. In such systems, interaction between pairs of eigenstates when a set of external parameters is varied is essentially driven by the existence of exceptional points (EP). At an EP, eigenstates coalesce: Complex eigenvalues degenerate and spatial distributions become collinear. In its vicinity, eigenvalues display a singular topology [1] and encircling the EP in the parameter space leads to a residual geometrical phase [2,3]. Since their introduction by Kato in 1966 [START_REF] Kato | Perturbation Theory for Linear Operators[END_REF], EPs have turned to be involved in a rich variety of physical effects: Level repulsion [START_REF] Heiss | [END_REF], mode hybridization [6], quantum phase transition [7], lasing mode switching [8], PT symmetry breaking [9,10] or even strong coupling [11]. They have been observed experimentally in different systems such as microwave billiards [12], chaotic optical microcavities [13] or two level atoms in high-Q cavities [11]. Open random media are a particular class of nonhermitian systems. Here, modal confinement may be solely driven by the degree of scattering. For sufficiently strong scattering, the spatial extension of the modes becomes smaller than the system size, resulting in transport inhibition and Anderson localization [14]. Disorderedinduced localized states have raised increasing interest. They provide with natural optical cavities in random lasers [15,16]. They recently appeared to be good candidate for cavity QED [17,18], with the main advantage of being inherently disorder-robust. These modes can be manipulated by a local change of the disorder and can be coupled to form necklace states [19][20][21], which open channels in a nominally localized system [22,23]. These necklace states are foreseen as a key mechanism in the transition from localization to diffusive regime [24]. PT symmetry has been studied in the context of disordered media and Anderson localization [25][26][27] but so far EPs between localized modes have not been investigated.

In this letter, coalescence at an EP between two Anderson-localized optical modes is demonstrated in a two dimensional (2D) dielectric random system. To bring the system in the vicinity of an EP, the dielectric permittivity is varied at two different locations in the random system. We first propose a general theory to follow the spectral and spatial evolution of modes in 2D dielectric open media. This theory is applied to the specific case of Anderson-localized modes to identify the position of an EP in the parameter space. This prediction is confirmed by Finite Element Method (FEM) simulations. We show that this is a highly complex problem of multiple mode interaction where a large number of modes are involved. We believe that our theory opens the way to a controlled local manipulation of the permittivity and the possibility to engineer the modes. Furthermore, we think this approach can be easily extended to others kinds of networks e.g. coupled arrays of cavities [28,29].

We first consider the general case of a finite-size dielectric medium in 2D space, with inhomogeneous dielectric constant distribution, ǫ(r). In the frequency domain, the electromagnetic field follows the Helmholtz equation:

∆E(r, ω) + ǫ(r)ω 2 E(r, ω) = 0 (1)
where E(r, ω) stands for the electrical field and the speed of light, c = 1. Eigensolutions of eq. ( 1), define the modes or eigenstates of the problem:

(Ω i , |Ψ i ) i∈N | ∆|Ψ i + ǫ(r)Ω 2 i |Ψ i = 0 (2)
Because of its openness, the system has inherent losses, thus is described by a non-hermitian Hamiltonian.

For non-hermitian systems, modes are a priori nonorthogonal, complex and their completeness is not ensured. Here, we consider open systems with finite range permittivity ǫ(r) and where a discontinuity in the permittivity provides a natural demarcation of the problem. For problems fulfilling these two conditions, Leung et al. [30][31][32] demonstrated the completeness of the set of eigenstates. As a result, the electrical field can be expanded along the modes:

E(r, ω) = i a i (ω)|Ψ i (3)
where a i (ω) stand for expansion coefficients along the basis. Moreover, if the eigenstates are not degenerated a biorthogonal product between modes can be defined [START_REF] Morse | Methods of theoretical physics[END_REF][START_REF] Moiseyev | [END_REF]:

Ψ * p |ǫ(r)|Ψ q = δ pq (4)
Now, we consider two locations R 1 and R 2 where the permittivity is varied

ǫ(r) = ǫ(r) + ∆ǫ 1 (r)p 1 (r) + ∆ǫ 2 (r)p 2 (r) (5)
where

{p i (r ∈ R i ) = 1|p i (r / ∈ R i ) = 0} i∈[1,2]
is the location and {∆ǫ i (r)} i∈ [1,2] the shape of the variation of permittivity. Eq. ( 1) becomes:

[∆ + ω 2 (ǫ(r) + ∆ǫ 1 (r)p 1 (r) + ∆ǫ 2 (r)p 2 (r))]E(r, ω) = 0 (6)
The permittivity distribution ǫ(r), describes a new disordered system with new modes ( Ωi , | Ψi ) i∈N . Nevertheless, we can still use the basis of the original random system, (Ω i , |Ψ i ) i∈N , to expand the electric field as follows:

E(r, ω) = i b i (ω)|Ψ i ( 7
)
where b i (ω) are the new expansion coefficients. Inserting eq. ( 7) into eq. ( 6):

i bi(ω) ∆ + ω 2 (ǫ(r) + ∆ǫ1(r)p1(r) + ∆ǫ2(r)p2(r)) |Ψi = 0 (8)
Projecting eq. ( 8) on Ψ * j |, using eq. ( 2) and the biorthogonal product (4) leads to:

∀ i b i (ω) Ω 2 i -ω 2 = ω 2 j b j (ω)C ij (9)
where

C ij = Ψ * j |∆ǫ 1 (r)p 1 (r)|Ψ i + Ψ * j |∆ǫ 2 (r)p 2 (r)|Ψ i (10)
If we consider a finite set of N modes, the generalized eigenvalue problem of eq. ( 9) can be written conveniently in a matrix form:

   Ω 2 1 ... 0 . . . . . . . . . 0 ... Ω 2 N    -ω 2    1 + C 11 ... C 1N . . . . . . . . . C N 1 ... 1 + C N N    = 0 (11)
The eigensolutions of eq. ( 11), ( Ωi , | Ψi ) i∈ [1,N ] , are the eigensolutions of eq. ( 1) for the permittivity distribution ǫ(r). In eq. ( 11), the coupling coefficients, C ij , between original modes i and j depend on the variation of the permittivity and the spatial overlap of the modes at the location of the permittivity modification. Noteworthily, the coupling integral not only depends on the spatial overlap of the mode intensity profiles but also on the overlap of their spatial distributions. Remarkably, when reduced to two modes, the system is the analog of two inductance/capacitor oscillators coupled via an inductance L c , in which charges of both capacitors satisfy

   1 √ L1C1 2 0 0 1 √ L2C2 2    -ω 2 1 + LC L1 Lc L1 Lc L2 1 + Lc L2 = 0 (12)
Eq. ( 11) extends this result to any number of interacting modes N > 2. The modes act as a network of linearly coupled oscillators. Our theory is now applied to a particular system. We consider a 2D random collection of 896 circular dielectric scatterers (radius 60 nm) with dielectric permittivity, ǫ = 4, embedded in a host material of index ǫ mat = 1.0, with a filling fraction of 40% (Fig. 1(a)). The system dimensions are L × L = 5.3 µm × 5.3 µm. In the spectral range considered in the following, the localization length is estimated around ξ ≈ 1 µm ≪ L and the modes are localized. The two circular regions of diameter 340 nm, R 1 and R 2 , are shown in Fig. 1(a). The dielectric permittivity of the scatterers within these regions is varied from ǫ to ǫ + ∆ǫ 1 and ǫ + ∆ǫ 2 , respectively. This can be achieved experimentally by shining 2 laser beams to induce a local change of the permittivity through nonlinear Kerr effect.

The initial modes (Ω i , |Ψ i ) i∈[1,N ] , which are the only input requested by eq. ( 11) are computed using a Finite Element Method (FEM) [START_REF] Touzani | OFELI, An Object Oriented Finite Element Librar[END_REF][START_REF] Hernandez | [END_REF] with absorbing boundary conditions. Numerical boundary conditions are placed 0.4 µm away from each side of the system. A large number of modes (N = 90) are computed for the initial system (Fig. 1(b)) in a narrow spectral range and we check that no modes are degenerated. We choose among them two localized states |Ψ 1 and |Ψ 2 respectively at Ω 1 and Ω 2 , spectrally close (Fig. 1(b)) but spatially distinct (Fig. 1(c),(d)). We define in the complex plane the spectral distance of mode i to mode 1 as

d(1, i) = |Ω 1 -Ω i |.
This distance, color-coded in Fig. 1(b) is a measure of the spectral overlap between mode i and mode 1. Here, mode 2 is most likely to couple to mode 1 but we will see that the influence of other nearby modes cannot be neglected in the modal interaction.

The biorthogonal product defined in eq. ( 4) corresponds to an integration over the whole space, R 2

Φ * q |ǫ(r)|Φ p = R 2 ǫ(r)Φ q (r)Φ p (r)dr (13)
Since the initial modes are obtained via FEM computation, thus they are spatially defined in a finite spatial domain V = [-0.1 µm, 5.7 µm] 2 . However, the biorthogonal product can be split into an integral over V and a second term at the boundary of V which replaces outside propagation [37]. Because the modes are localized they have very weak amplitude along the boundary of V . Neglecting the edge term in the biorthogonal product leads to an inaccuracy of 0.8% in the position of EP. Therefore, we can approximate the biorthogonal product by its restriction to V . The parameter space, (∆ǫ 1 , ∆ǫ 2 ), is sampled and eq. ( 11) is solved for each value of (∆ǫ 1 , ∆ǫ 2 ) and for N = 60 interacting modes to compute the new eigenstates, ( Ωi , | Ψi ) i∈ [1,N ] . The evolution of spectral distance between new modes 1 and 2, d(1, 2) = | Ω1 -Ω2 |, in the small range of parameter space is shown in Fig. 2(a). It sharply drops to zero at (∆ǫ 1 , ∆ǫ 2 ) @EP = (0.939, 0.90). The existence of an EP at this position is confirmed by plotting in the parameter space the real and imaginary parts of the eigenvalues, Ωi∈ [1,2] (Fig. 2(c),(d)). The intricate topology of intersecting Riemann's sheets around the singular point (∆ǫ 1 , ∆ǫ 2 ) @EP , is the hallmark of an EP. We now focus on the corresponding eigenfunctions, Ψ1 | Ψ2 , in the vicinity of the EP. We compute the inner product of these two eigenstates and plot the function 1/(1 -| Ψ1 | Ψ2 |), as shown in Fig. 2(b). At the exact position where | d(1, 2)| vanishes, the two eigenvectors become collinear confirming the coalescence of the two eigenstates. The evolution of the modes in the vicinity of an EP is investigated in Fig. 2(e), where we plot the curves Im( Ω1 ) = Im( Ω2 ) and Re( Ω1 ) = Re( Ω2 ) in the parameter space. As expected these two curves end at the exact position of the EP, where both the real and imaginary parts of the eigenvalues are equal, and they form a continuous trajectory. Our calculations allows to go further and check that | Ψ1 = ±i| Ψ2 on either sides of the EP [38]. Indeed, we confirm that both eigenvectors are collinear with a phase shift of ±π/2 [38]. Finally, the theoretical prediction is confronted with an numerical computation of the EP position: FEM simulations are used this time to compute systematically the new modes | Ψi∈ [1,2] for each set of (∆ǫ 1 , ∆ǫ 2 ) in a range enclosing our theoretical prediction (∆ǫ 1 , ∆ǫ 2 ) @EP . The sampling is set to 0.04 along ∆ǫ 1 and ∆ǫ 2 . The numerically-computed eigenvalues merge at position (∆ǫ 1 , ∆ǫ 2 ) = (0.92, 0.88) ± (0.04, 0.04) which is within the error bar of the predicted value obtained from eq. ( 11). The collinearity of the eigenvectors is also satisfied and confirms the existence of an EP at this specific position.

In order to understand the coalescence mechanism, the common amplitude of mode 1 and 2 at EP, | Ψ1/2,@EP , is shown in the inset of Fig. 3(a). It forms a beaded chain which connects both ends of the system and is similar to necklace states studied in [19]. To investigate the influence of the nearby modes in the coalescing of modes 1 and 2 at EP, we measure in Fig. 3(a) the norm of the biorthogonal projection of eigenstate | Ψ1/2,@EP along the different initial modes, | Ψ i∈[1,N ] | Ψ1/2,@EP |. Remarkably enough, it demonstrates the vanishing, though non negligible, influence of nearby modes, i > 2. If projection norms for initial modes 1 and 2 are close to 0.6, others modes (for instance 4 and 5) contribute up to 0.25. Their influence is also highlighted in Fig. 3(b), where the position of the EP, (∆ǫ 1 , ∆ǫ 2 ) @EP , is obtained from eq. ( 11) for different number of modes, N , ranging from 2 to 60. The position of the EP in the parameter space fluctuates significantly for small N and converges for values larger than 55. Therefore, the EP cannot be explained by a two-mode interaction and results from a collective effect between multiple modes.

In conclusion, we proposed a general theory to study the evolution of modes in open media when the permittivity is varied. This approach, which relies on the linearity in ǫ(r) in Helmhotz equation, is non-perturbative: For any ∆ǫ i∈ [1,2] , eq. ( 11) gives the new modes from the knowledge of the initial system. Our theory describes the system by an infinite set of modes acting as oscillators coupled via the modification of the permittivity. We considered the specific case of random media in the localization regime and show that our theory can be used to investigate the mode coupling and hybridization resulting from a local perturbation. In particular, by changing the local index at two different locations, two modes are brought to an EP where they coalesce. Remarkably, the accuracy of the theoretical prediction is shown to strongly depend on the number of modes considered. A large number of modes is required, which shows that the evolution of modes is dictated by multiple-mode interactions. In term of experimental realization, such a disorder manipulation can be easily implemented on exist- ing setups [16,39,40]. Permittivity landscape can be shaped reversibly using e.g. laser illumination and nonlinear Kerr effect to engineer the modes. For instance, EP can be reached by following the crossing line of Fig. 2(e). EPs can be calculated for any pair of modes and even generalized to three or more eigenstates coupling, which opens the way to the control of light-matter interaction in random media. For instance, the random system can be designed to force the hybridization of modes and the opening of channels in opaque systems. This is in contrast to earlier works where such a necklace state was obtained using a try-and-fail method. Alternatively, using mode repulsion in the vicinity of EP, the disorder can be engineered to increase the spatial confinement of the modes and consequently their Q-factor. Finally, we believe this approach can be extended to others types of cavity networks e.g. photonic crystal cavity arrays used for quantum simulation [28,29,41], where fabrication inaccuracy could be compensated a posteriori by such an external control. We acknowledge S. Rotter for fruitfull discussions. PS is thankful to the Agence Nationale de la Recherche for its support under grant ANR PLATON (No. 12-BS09-003-01), the LABEX WIFI (Laboratory of Excellence within the French Program 'Investments for the Future') under reference ANR-10-IDEX-0001-02 PSL* and the Groupement de Recherche 3219 MesoImage.

Figure 1 .

 1 Figure 1. (a) 2D random medium: 896 scatterers of dielectric permittivity ǫ = 4 are embedded in vacuum ǫmat = 1.0. The system is open at its boundaries. The permittivity is modified in two regions of diameter 340 nm (respectively R1 = red circle and R2 = green circle). (b) Initial eigenvalues (Ωi) i∈[1,90] computed by FEM and sorted in the complex plane according the distance d(1, i). An insert points out eigenvalues of interest (namely Ω1 and Ω2). (c) and (d) Amplitudes of initial eigenvectors |Ψ1 and |Ψ2 , respectively.

Figure 2 .

 2 Figure 2. (a) Eigenvalue difference d(1, 2) dB = | Ω1 -Ω2|dB (arbitrary units), canceling out at position (∆ǫ1, ∆ǫ2) @EP in the parameter space. (b) The function 1/(1 -| Ψ1| Ψ2 |) in the parameter space. At position (∆ǫ1, ∆ǫ2) @EP , it exhibits a clear maximum meaning the two modes become collinear. (c) and (d) Real and imaginary parts of eigenvalues Ω1 and Ω2. The eigenvalue surfaces display the typical structure of intersecting Riemann sheets centered around (∆ǫ1, ∆ǫ2) @EP . (e) Trajectories Im( Ω1) = Im( Ω2) and Re( Ω1) = Re( Ω2) marked by red and blue dots, respectively: Both curves join continuously at EP. In inset, spatial distributions surrounded by a blue (red) frame show real and imaginary parts of mode 1 (2) at EP: Modes becomes collinear and satisfy Ψ1 = ±i Ψ2.

Figure 3 .

 3 Figure 3. (a) Norm of the biorthogonal projection of modes 1 and 2 at EP along the 45 first initial modes: | Ψ i∈[1,N] | Ψ1/2,@EP |. The amplitude of | Ψ1/2,@EP is shown in inset. The four aligned spatial distributions correspond to initial modes 1, 2, 4 and 5, respectively. Black arrows point to their respective biorthogonal projection coefficients. (b) Prediction of EP position in the parameter space (∆ǫ 1@EP red curve and ∆ǫ 2@EP blue curve) for a number of initial modes N ranging from 2 to 60. Prediction only converges for N ≥ 55. The two error bars point out the position of the EP obtained by FEM computation.


Claire C Hanen
email: claire.hanen@lip6.fr

Alix Munier-Kordon

Cyclic DataFlows in computers and embedded systems

Introduction

This chapter addresses cyclic scheduling problems issued from the control of data flows in computers, embedded systems or sensor networks. Although in various context, parts and data may induce the same theoretical scheduling problems, we focus here on specific models and constraints. We point out analogies with production scheduling as well as differences and show the main basic results of the field, following the introduction on cyclic scheduling given in [START_REF] Robert | Introduction to Scheduling[END_REF], chapters 5, 6 and 8.

Dealing with data flows instead of manufacturing process means that tasks/jobs represent computation and/or data transmission. Precedence constraints are here induced by data dependencies: a job can be processed only when its input data, produced or carried by another task, is available. Notice that in a manufacturing process, a part is usually transformed, assembled, but remains in the system, although a computation task may create or delete data. Precedence constraints may also be defined when a limited memory constraint is considered. Indeed, a job J i that has to write a data in a full memory or buffer has to wait that another one, say J i , frees place, inducing then a precedence relation from executions of J i to J j . These constraints are frequently considered in embedded systems for which the overall available memory is limited.

Computations are done by physical components that, from a scheduling point of view are similar to usual processors or machines in production process though parallel processors or more complex resources from RCPSP problems are usually used [START_REF] Ayala | The resource-constrained modulo scheduling problem: an experimental study[END_REF]. However, energy saving may induce unusual constraints on the scheduling process, in particular grouping of tasks processed by the same component, in order to avoid too many on/off. We consider in this chapter a finite set of jobs J = {J i , 1 ≤ i ≤ n} which communicate data following a Synchronous DataFlow Graph formalism. Synchronous DataFlow Graph (SDF in short) is a simple model of computation introduced by Lee and Messerschmitt [START_REF] Lee | Synchronous data flow[END_REF] for the description of Digital Signal Processing Applications. In this context, SDF or extensions were considered to model H263 Encoder [START_REF] Benazouz | A new method for minimizing buffer sizes for cyclo-static dataflow graphs[END_REF], an MP3 playback [START_REF] Oh | Efficient code synthesis from extended dataflow graphs for multimedia applications[END_REF] or a Reed-Solomon decoder [START_REF] Bekooij | Efficient computation of buffer capacities for cyclo-static real-time systems with back-pressure[END_REF]. The SDF obtained do not exceed here more that height actors. SDF associated to an application may also be generated automatically using a DataFlow language [START_REF] Thies | StreamIt: A compiler for streaming applications[END_REF][START_REF] Goubier | Σc: A programming model and language for embedded manycores[END_REF]. The number of actors for real-life applications ranges up to 600. The size of the instances encountered in this new generation of embedded systems is significantly larger than before as they express increasingly higher levels of concurrency.

Each jobs of a fixed SDF has to be executed repeated infinitely. Thus, checking the feasibility of a SDF or evaluating its maximum throughput can be seen has a cyclic scheduling problem. One of the aim of this chapter is to investigate the relationship between cyclic scheduling problems and Dataflow problems. The main questions that these two communities have explored are the following:

• Schedulability: does a feasible infinite schedule exist?

• Evaluation of the maximum throughput: what is the structure and the performance of a schedule that maximizes the throughput? • Performance of a periodic schedule: what is the optimal cycle time of a schedule with a specific periodic structure? • Memory optimization: what is the minimum amount of memory to reach feasibility? or a given cycle time?

We propose in next sections, a panorama of theoretical results developed for dataflow models in connection with cyclic scheduling problems. Section 1.2 is dedicated to the presentation of the SDF model. Basic results about the precedence constraints and the normalization are recalled, leading to the definition of a feasible schedule and its normalized average cycle time. Two small examples, namely a loop parallelization problem and the modelling of periodic data transfer for a real-time system are presented in Section 1.3. Section 1.4 presents some basic results and optimization problems for the special case of uniform precedence graph, which is particular important class of SDFs. Section 1.5 is dedicated to the presentation of basic mathematical properties on SDF and two important optimization problems. Section 1.6 is our conclusion.

Synchronous dataFlow graphs

This section presents some basic definitions and results on Synchronous Dataflow Graphs. Subsection 1.2 introduces the general model and the repetition vector. Next subsection recalls that a SDF models an infinite set of precedence relations between the successive executions of the jobs. Subsection 1.2.3 presents the normalization of a SDF. This transformation will be useful to study the schedulability and the determination of a periodic schedule in section 1.5. We lastly presents some common criteria and scheduling policies.

General Model

Let us consider a set of n jobs J = {J 1 , . . . , J n } with processing times {p 1 , . . . , p n } to be repeated many times. For J i ∈ J , <J i , k> denotes the k th occurrence of J i . Jobs are usually supposed to be totally or partially non-reentrant, i.e. two successive executions of a job may not overlap or for all n > 0, <J i , n + 1> starts at least one time unit after <J i , n> starts.

Jobs can exchange data using FIFO (First-In First Out) queues. Each FIFO has exactly one input job J i and one output job J j and is thus modelled by an arc a = (J i , J j ). Arcs are usually bi-valued by two strictly positive integers u(a) and v(a) with the assumptions that:

1. u(a) data (or tokens) are stored in the FIFO at the completion of each execution of J i ; 2. v(a) data are removed from the FIFO before each execution of J j . If there is not enough data, the job cannot be executed and must wait for them.

Let A be the set or arcs. M 0 (a) for each arc a ∈ A is a non negative integer corresponding to the initial number of data in the associated buffer. These values can be fixed at the beginning, or may be variable for some optimization problems. A Synchronous DataFlow Graph (in short SDF) is then a tri-valued multi-graph G = (J , A, u, v, M 0 ). Let C (G) denotes the set of circuit of G.

A schedule is a function s : J × N → R + such that s(J i , k) is the starting time of <J i , k>. A schedule is feasible if at any instant the number of tokens in any FIFO is non negative.

Consider for example the SDF of n = 4 jobs J = {J 1 , J 2 , J 3 , J 4 } depicted by Figure 1.1. We also suppose that p 1 = 1, p 2 = 2, p 3 = 1 and p 4 = 2. Figure 1 v(a) . Note that, if W (c) > 1, the number of data items stored in the FIFO will increase as far as the jobs are executed. In the contrary, if W (c) < 1, this numbers tends to 0, leading to a deadlock. These situations correspond to design flaws and such graphs can be dismissed. Thus, all studies are restrained to unitary graphs for which the weight of every circuit

c is 1, i. e, ∀c ∈ C (G), W (c) = 1.
Suppose that, at time instant t, J i was executed n i times, with n i > 0 and that J j was executed n j times with n j > 0. Then, the total number tokens at t stored in the buffer associated to arc a equals M 0 (a) + u(a)n iv(a)n j . Thus, we observe that if n i = k × v(a) and n j = k × u(a), the number of tokens in the queue equals M 0 (a). More formally, the following theorem is proved in [START_REF] Lee | Synchronous data flow[END_REF]:

J 1 J 2 J 3 J 4 1 3 2 1 2 3 3 2 3 2 1 1 a ∈ A u(a) v(a) M 0 (a) a 1 = (J 1 , J 3 ) 1 3 0 a 2 = (J 3 , J 2 ) 2 1 1 a 3 = (J 1 , J 2 ) 2 3 1 a 4 = (J 2 , J 1 ) 3 2 3 a 5 = (J 4 , J 1 ) 3 2 5 a 6 = (J 2 , J 4 ) 1 1 0 Fig. 1.1: A Synchronous Data Flow Graph G J 4 J 3 J 2 J 1 1 2 3 4 5 6 1 2 3 4 1 2 1 2 3
Fig. 1.2: First executions of the earliest schedule of the SDF pictured by Figure 1.1

Theorem 1.1 (Repetition vector). Suppose that G is a unitary SDF. Then, there exists an integer vector N ≥ 1 n such that or for every arc a = (J i , J j ) ∈ A, the equality u(a) × N i = v(a) × N j holds. Then, the graph is feasible iff each job J i ∈ J can be executed at least N i times. Moreover, once each job is executed exactly N i times (if it is possible), the systems returns in its initial state, ı.e the current marking of the buffers equals its initial value.

We can check that our example pictured by Figure 1.1 is unitary. The equations verified by the repetition vectors are N 1 = 3N 3 , 2N 3 = N 2 , 2N 1 = 3N 2 , N 2 = N 4 and 3N 4 = 2N 1 . The smallest integer solution is then

N 1 = 3, N 2 = 2, N 3 = 1 and N 4 = 2.

Precedence constraints associated to a SDF and useful tokens

A precedence constraint between executions <J i , n i > and <J j , n j > with (n i , n j ) ∈ N 2 expresses that <J j , n j > cannot be executed before the completion of <J i , n i >. Munier [START_REF] Munier | Régime asymptotique optimal d'un graphe d'événements temporisé généralisé: application à un problème d'assemblage[END_REF] proved that each arc a = (J i , J j ) is equivalent to an infinite set of precedence relations between the successive executions of J i and J j defined the following theorem. A proof can also be found in [START_REF] Marchetti | Cyclic scheduling for the synthesis of embedded systems[END_REF].

Theorem 1.2 (Precedence constraints associated with a FIFO queue). Let J i and J j be two re-entrant jobs. A FIFO queue a = (J i , J j ) ∈ A with initially M 0 (a) tokens models a precedence relation between the n i th execution of J i and the n j th execution of J j iff u(a) > M 0 (a) + u(a)

• n i -v(a) • n j ≥ max{u(a) -v(a), 0}.
For example, let us consider the arc a = (J 1 , J 2 ) with u(a) = 2, v(a) = 3 and M 0 (a) = 1. The inequality of Theorem 1.2 becomes

2 > 1 + 2 • n i -3 • n j ≥ 0.
The couples of indexes (n 1 , n 2 ) such that there exists a precedence relation due to a are then {(1 + 3k, 1 + 2k), k ∈ N} and {(3 + 3k, 2 + 2k), k ∈ N}. A useful initial marking is such that, for any arc a = (J i , J j ), M 0 (a) is a multiple of gcd(u(a), v(a)). A corollary of Theorem 1.2 is that useful initial markings are dominant [START_REF] Marchetti | A sufficient condition for the liveness of weighted event graphs[END_REF][START_REF] Marchetti | Cyclic scheduling for the synthesis of embedded systems[END_REF]. Moreover the initial marking M 0 (a) of a may be replaced by

M 0 (a)
gcd(u(a),v(a)) × gcd(u(a), v(a)) without any influence on the precedence constraints associated to a. Thus, we only consider useful initial markings.

Normalization

Let us assume that a SDF G = (J , A, u, v, M 0 ) is a unitary graph. A SDF is said to be normalized if there exists a positive integer vector Z = (Z 1 , • • • , Z n ) such that, for any arc a = (J i , J j ) ∈ A, u(a) = Z i and v(a) = Z i . Marchetti and Munier [START_REF] Marchetti | A sufficient condition for the liveness of weighted event graphs[END_REF][START_REF] Marchetti | Cyclic scheduling for the synthesis of embedded systems[END_REF] proved the following theorem: Theorem 1.3 (Normalization). If G is a unitary SDF then, there exists an integer vector Z ≥ 1 n such that, for any arc a = (J i , J j ), Z i × v(a) = Z j × u(a). It follows that the normalized SDF G built from G by setting, for any arc a = (J i , J j ), u (a) = Z i , v (a) = Z j and M 0 (a) = M 0 (a) × Z i u(a) generates the same set of precedence constraints as G.

Theorem 1.3 can be seen as a corollary of Theorem 1.1. Indeed, if the repetition vector N is given, we can get the normalization vector by setting M = lcm(N 1 , • • • , N n ) and for any job J i , Z i = M N i . In the following we only consider normalized SDF.

For example, Figure 1.4 presents the normalized SDF G associated with the SDF G shows by Figure 1.1 and its initial marking. We get M = lcm(2, 3) = 6 and thus

Z 1 = M 3 = 2, Z 2 = M 2 = 3, Z 3 = M = 6 and Z 4 = M 2 = 3. J 1 J 2 J 3 J 4 2 6 6 3 2 3 3 2 3 2 3 3 a ∈ A M 0 (a) a 1 = (J 1 , J 3 ) 0 a 2 = (J 3 , J 2 ) 3 a 3 = (J 1 , J 2 ) 1 a 4 = (J 2 , J 1 ) 3 a 5 = (J 4 , J 1 ) 5 a 6 = (J 2 , J 4 ) 0

Uniform precedence graphs

A SDF G is said to be uniform if for any arc a = (J i , J j ), u(a) = v(a) = 1. The corresponding inequality of Theorem 1.2 becomes 1 > M 0 (p) + n in j ≥ 0, and thus n jn i = M 0 (a). In this case, the corresponding set of precedence constraints between executions of J i and J j verifies :

∀n > 0 s(J i , n) + p i ≤ s(J j , n + M 0 (a)) .
Observe that in this case, p i > 0 and M 0 (a) ≥ 0. However, uniform precedence graphs can be defined more generally as in [START_REF] Munier-Kordon | A graph-based analysis of the cyclic scheduling problem with time constraints: schedulability and periodicity of the earliest schedule[END_REF]. Indeed, in the more general case, the two integer values associated to any arc a = (J i , J j ) may be negative. A uniform precedence graph is then defined as a bi-valued oriented graph G = (J , A, , h). The length and the height of an arc are respectively function defined as : A → Z and h : A → Z. The precedence relations associated to any arc a = (J i , J j ) are then defined by:

∀n ≥ max(1, 1 -h(a)), s(J i , n) + (a) ≤ s(J j , n + h(a)).
Several authors [START_REF] Marchetti | A sufficient condition for the liveness of weighted event graphs[END_REF][START_REF] Marchetti | Cyclic scheduling for the synthesis of embedded systems[END_REF] have observed that the precedence relations induced by any unitary SDF can be expressed using a uniform precedence graph for which each job J i is duplicated N i times. This transformation, called the expansion of the graph, allows to consider all the algorithmic tools developed for uniform precedence graphs to SDF, and thus was extensively used.

Its main drawback is that the size of the expanded graph is not polynomial and may be huge for real-life applications. Indeed, its total number of vertices equals

J 1 1 J 2 1 J 3 1 J 1 2 J 2 2 (1, 0) (1, 0) (1, 1)
(2, 0)

(2, 1) ∑ n i=1 N i and its number of arcs is around ∑ a=(J i ,J j )∈A min(N i , N j ). The consequence is that the methods developed for uniform precedence graphs are not efficient for these instances. However, as we will see in subsection 1.5.1, partial expansions may be considered to develop efficient exact algorithms for the throughput evaluation.

(1, 0) (1, 0)

Criteria

Several criteria may be considered to evaluate a feasible schedule s. The most common one is the average cycle time of s, which is the inverse of the throughput. More formally, the average cycle time of job J i for a schedule s is the mean time interval between two executions of J i :

λ s i = lim k→ +∞ s(J i , k) k .
The normalized average cycle time of s can be defined then as

λ s = max J i ∈J λ s i Z i .
Another common criteria of a schedule is the latency L s . Roughly speaking, the latency is the maximum delay between a stimulation and the answer of the system. The SDF G must be without circuits. The latency of the entire system is the maximum time gap from a data input of a system to a connected outcome. This criteria is particularly important for real-time systems to measure the worst-case reaction time of a system.

Scheduling policies

A schedule s is said to be K-periodic if there exists for any job J i a period w i and an integer K i such that, for n sufficiently large, s(J i , n

+ K i ) = s(J i , n) + w i . K i is the of J i , while w i is its period. Note that λ s i = w i K i .
Moreover, if G is strongly connected, the normalized average cycle time is

λ s = w i K i Z i .
The most common scheduling policy consists on executing the actors as as soon as possible (asap in short) which maximizes the throughput. An asap schedule always consists of two stages [START_REF] Munier | Régime asymptotique optimal d'un graphe d'événements temporisé généralisé: application à un problème d'assemblage[END_REF]. The first one is an initialization phase which is necessarily finite and possibly null. A K-periodic steady state phase follows. The periodicity factor of job

J i verifies K i = α × N i with α ∈ N .
The earliest schedule depicted by Figure The main drawback of the asap schedule is that its description is not of polynomial size. Indeed, values of the repetition vector are not polynomial and may be huge. Many authors (see as example [START_REF] Marchetti | Complexity results for weighted timed event graphs[END_REF][START_REF] Benazouz | A new approach for minimizing buffer capacities with throughput constraint for embedded system design[END_REF]) restrict their study to periodic schedules in order to get efficient algorithms. The structure of periodic schedules of a SDF is presented in Section 1.5.2

Modelling Examples

Two usual applications for which SDF and uniform graphs are particularly suitable are presented in this section. The first one concerns a loop parallelization. It has been studied since the early 90's [START_REF] Gasperoni | Generating close to optimum loop schedules on parallel processors[END_REF][START_REF] Rau | Iterative modulo scheduling: an algorithm for software pipelining loops[END_REF][START_REF] Calland | Circuit retiming applied to decomposed software pipelining[END_REF][START_REF] Eichenberger | Efficient formulation for optimal modulo schedulers[END_REF] and the introduction of parallel computers. Most of computation time is indeed spent in loops, so that the good use of parallelism allowed by the architecture is crucial. Our second example shows that communications between real-time periodic jobs following Liu and Layland model [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF] can be expressed using a particular normalized SDF. This modelling can be used to evaluate the whole latency of the system.

Loop parallelization

Let us describe on an example how a task system associated to the execution of a loop on a specific architecture can be modeled by a uniform task system, provided that enough resources are available.

Assume that arrays a, b are stored in the memory of a computer, and consider the C loop depicted in figure 1.6. We describe the jobs associated with assembly instructions. We assume that all instructions are processed by pipelined units, that can start a new instruction at each time unit, while the execution time till the end of an operation is 2 for additions, 6 for multiplication, and 4 for memory operations (load and store).

for (i = 3; i < n; i ++){ b[i] = a[i -3] + c; a[i] += b[i] • d; } J 1 J 2 J 3 J 4 J 5 J 6 J 7 J 8 J 9 address a[i] address b[i] load a[i-3] add c store b[i] mult d load a[i] add a[i] store a[i]
Fig. 1.6: A C loop and its associated jobs Figure 1.7 shows the uniform constraints induced by the loop semantic as well as the architecture (assuming here unlimited number of functional units). The partial reentrance is modelled by the loops around each job with label (1, 1). Although interleaving the iterations is allowed, the storage of a[i] in the memory at iteration i, i.e job <J 9 , i>, must precede the load of a[i] at iteration i + 3 (Job <J 3 , i + 3>). Thus the arc (J 9 , J 3 ) has = 4 and h = 3. Uniform constraints can also model the use of a limited number of buffers. For example, we can assume here that the successive address of a[i] are stored in a buffer of size 3, so that at most three executions of J 3 can start without starting J 1 and J 1 can start only if a register is free, i.e. if J 3 started. This is modeled by the arcs (J 1 , J 3 ) and (J 3 , J 1 ) with values (2, 3) and (0, 0). When dealing with loop execution on parallel architectures, it is necessary to build a compact schedule, that can be easily described by a finite set of instructions. Hence in this field most authors considered strictly periodic schedules, where all jobs have Let us consider a set of jobs based on the model of Liu and Layland [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF]. Each job J i is characterized by a period T i , a processing time C i , a deadline D i , and a release date r i . The nth occurrence of J i can be processed if and only if its execution start date s(t i , n) is superior or equal to its release date

J 1 J 3 J 4 J 5 J 7 J 9 J 2 J 8 J 6 (1,1) (1,1) (1,1) (1,1) (1,1) (1,1) (1,1) (1,1) (1,1) (2,3) (0,0) (4,0) (4,0) (6,0) (2,0) (2,0) (2,0) (4,3) (2,0) (0,2) (2,0)
J 3 J 4 J 3 J 4 J 3 J 4 J 3 J 2 J 5 J 2 J 5 J 2 J 5 J 1 J 7 J 1 J 7 J 1 J 6 J 6 J 6 J 8 J 9 J 8 core with λ = 6
r i + (n -1)T i ≤ s(J i , n).
and its execution end date cannot exceed its deadline

s(J i , n) +C i ≤ r i + (n -1)T i + D i .
Suppose for example that job J i needs data from job J i . We consider that the nth execution of J i writes a unique data at time r i + (n -1)T i + D i and that the nth execution of J j reads a unique data at time r j + (n -1)T j . The data are not stored in a FIFO queue, but in a unique memory. Thus, task J j may read several time the same data if its period T j < T i .

For example, consider 3 jobs J 1 , J 2 and J 3 which parameters are shown in Table 1.2. We assume that J 1 sends data to J 2 and that J 2 sends data to J 3 . Figure 1.9 presents the relations between jobs. For example, <J 2 , 2> is reading a data from <J 1 , 1>, while <J 2 , 4> is reading a data from <J 1 , 2>. The data considered by <J 2 , 3> comes from <J 1 , 1>, the arcs is omitted by transitivity, since <J 2 , 2> precedes <J 2 , 3>. Table 1.2: Parameters of jobs J 1 , J 2 and J 3 The question is to compute efficiently the latency of the system. The first problem is then to characterized couples of integers (n i , n j ) ∈ N 2 such that <J j , n j > reads a data from <J i , n i >.

J i r i T i C i D i
By studying the lifetime of the data, Khatib et al. [START_REF] Khatib | Computing latency of a real-time system modeled by synchronous dataflow graph[END_REF] observed that the relations between the executions of communicating jobs corresponds to precedence relations of a unitary SDG built following Theorem 1.4: Theorem 1.4. Let J i and J j be two periodic jobs such that J i communicates with J j . The set of communicating instances of jobs J i and J i corresponds to prece-dence relations of an arc a = (J i , J j ) of a normalized SDF with Z i = T i , Z j = T j and M 0 (a) = T j + α -T a with T a = gcd(T i , T j ) and α =

r i -r j +C i T a × T a .
Thus, the corresponding SDF is composed by two arcs a 1 = (J 1 , J 2 ) and a 2 = (J 2 , J 3 ) with Z 1 = 30, Z 2 = 20, Z 3 = 40 and the initial markings M 0 (a 1 ) = 10 and M 0 (a 2 ) = 40. Note that the latency of the graph equals 60. It corresponds to the path <J 1 , 3>, <J 2 , 5>, <J 2 , 6> and <J 3 , 4>. Section 1.5.4 is dedicated to the evaluation of the latency of the SDF extracted from a real-time system.

Uniform precedence graphs

Some fundamental basic results on uniform precedence graphs are firstly recalled. We then introduce a generic technique, called decomposed software pipelining, that was used by several authors to solve periodic scheduling problems with resource constraints and to get approximation results. We finally present constraints recently introduced to handle energy saving in sensor networks and we mention some complexity results.

Basic results

Let consider that G = (J , A, , h) is a uniform precedence graph G. If no additional resource constraint is considered, the schedulability, the evaluation of the maximum throughput and the performance of a periodic schedule are polynomially solvable.

These questions were initially considered for non-negative uniform case [START_REF] Carlier | Problèmes d'ordonnancement : modèlisation, complexité, algorithmes[END_REF], i.e, for any arc a, (a) > 0 and h(a) ≥ 0. These results were extended in [START_REF] Munier-Kordon | A graph-based analysis of the cyclic scheduling problem with time constraints: schedulability and periodicity of the earliest schedule[END_REF] for any integer values. For the sake of simplicity, we mention here the main results for the case where G is strongly connected. General case can be found in [START_REF] Munier-Kordon | A graph-based analysis of the cyclic scheduling problem with time constraints: schedulability and periodicity of the earliest schedule[END_REF][START_REF] Claire | Cyclic scheduling[END_REF].

Let C + (G) (Resp. C -(G)) be the set of circuits c of G with h(c) > 0 (Resp. h(c) < 0). For any circuit µ ∈ C (G), let L(µ) = Σ a∈c (a) and H(µ) = Σ a∈c h(a).
Let also define the two ratios:

λ + (G) = max µ∈C + (G) L(µ) H(µ) λ -(G) =    min µ∈C -(G) L(µ) H(µ) if C -(G) = / 0 + ∞ otherwise A circuit µ ∈ C + (G) is critical if L(µ) H(µ) = λ + (G).
The critical circuit of the graph depicted in Figure 1.7 is the circuit µ = (J 3 , J 4 , J 6 , J 8 , J 9 , J 3 ) and its value equals

L(µ) H(µ) = λ + (G) = 18 3 = 6.
A schedule s is said to be strictly periodic if there is a constant λ such that ∀J i ∈ J ∀k > 0 s(J i , k) = s i + (k -1)λ . λ is the average cycle time of s, also called its period. First point of Theorem 1.5 deals with the schedulability. Second point concerns the the evaluation of the maximum throughput while the third point is about the performance of a periodic schedule: Theorem 1.5 ([39, 35]). Let G be a uniform strongly connected task system.

1. G is feasible if and only λ + (G) ≤ λ -(G) and there is no circuit µ in C (G) with H(µ) = 0 and L(µ) > 0. 2. If G is feasible, its minimum average cycle time is λ + (G) and the asap schedule is K-periodic. 3. If G is feasible, there exists an optimal strictly periodic schedule s with λ s = λ + (G) 4. Checking feasibility, computing the optimal cycle time and the optimal strictly periodic schedule can be done in polynomial time according to graph algorithms.

Dasdan et al. [START_REF] Dasdan | Efficient algorithms for optimum cycle mean and optimum cost to time ratio problems[END_REF] have experimentally tested several algorithms to compute the maximum cost to time ratio, which is exactly our problem here. Notice that a fixed value λ ∈ [λ + (G), λ -(G)] iff there is no valued positive cycles in the graph G valued by V λ (a) = (a)λ .h(a) for any arc a. Checking for a positive cycle in a graph Dot? can be done in polynomial time using Bellman-Ford algorithm [START_REF] Cormen | Introduction to Algorithms[END_REF]. Howard's algorithm, which is supposed to be the most efficient for the problem, although pseudopolynomial in the worst case, increases a lower bound b of λ + (G) until the critical circuit is reached or an infeasibility is detected. Another efficient and polynomial approach is a parametric path algorithm with complexity O(n 4 ) [START_REF] Alacaide | Cyclic multiple robot scheduling with time-window constraints using a critical path approach[END_REF][START_REF] Kats | Cyclic routing algorithms in graphs: Performance analysis and applications to robot scheduling[END_REF]. Figure 1.10 shows the graph of Figure 1.7 valued by V λ for λ = 6. First execution times s i ∈ J of a feasible strictly periodic schedule of period 6 are also reported.

J 1 J 3 J 4 J 5 J 7 J 9 J 2 J 8 J 6 6

Decomposed software pipelining and resource constrained problems

As seen in section 1.3.1, loop parallelization induces a uniform task system. The architecture on which the loop is executed induces additional resource constraints.

From the simple case of parallel processors [START_REF] Hanen | Cyclic scheduling on parallel processors: An overview[END_REF][START_REF] Hanen | A study of the cyclic scheduling problem on parallel processors[END_REF] to the more complex case of RCMSP (resource-constrained modulo scheduling problem), two main approaches have been investigated, in order to find an optimal strictly periodic schedule. Although it can be easily proved that periodic schedules are not dominating schedules, their simple formulation make them very easy to implement and thus often used in loop parallelization context. Firstly the ILP formulations, for example in [START_REF] Ayala | The resource-constrained modulo scheduling problem: an experimental study[END_REF][START_REF] Eichenberger | Efficient formulation for optimal modulo schedulers[END_REF][START_REF] Dupont De Dinechin | Resource-constrained moulo scheduling[END_REF] combining classical ILP formulations of resource constraints (either time-indexed or not), and linear expression of uniform constraints. In [START_REF] Ayala | The resource-constrained modulo scheduling problem: an experimental study[END_REF], several models are described and experimentally compared. The second approach, known as decomposed software pipelining (DSP) is based on the decomposition of the cyclic scheduling problem into two phases, retiming and compaction, the first one is related to the uniform task system, and the second to non cyclic resource constrained scheduling. In particular, several approximation algorithms have been proposed, based on this ideas [START_REF] Gasperoni | Generating close to optimum loop schedules on parallel processors[END_REF][START_REF] Blachot | SCAN: A Heuristic for Near-Optimal Software Pipelining[END_REF][START_REF] Calland | Circuit retiming applied to decomposed software pipelining[END_REF][START_REF] Benabid | Worst case analysis of decomposed software pipelining for cyclic unitary RCPSP with precedence delays[END_REF]. Finally, in [START_REF] Ayala | The resource-constrained modulo scheduling problem: an experimental study[END_REF], a hybrid approach combining shifting and ILP has been investigated.

In this section we describe the decomposed software pipelining technique and summarize the approximation results.

DSP relies on the notion of retiming. The main interest of this technique is to transform a set of uniform constraints into a set of usual precedence constraints, so that the remaining problem is an acyclic scheduling problem with resource constraints.

The intuition behind retiming is that while dealing with periodic schedules, the real iteration number of a job occurrence is not so important. Consider an occurrence <J i , k>, which corresponds to the (k) th execution of the first instance of J i . It can also be interpreted as the (k + r i ) th execution of J i (r i ) whose first occurrence is <J i , -r i >. The height of precedence relations are then changed: if there is a uniform constraint a = (J i , J j ) labelled by ( (a), h(a)), then s(J i (r i ), k) + (a) ≤ s(J j (r j ), k + r j + h(a)r i ). So the value r j + h(a)r i is the height of a new uniform precedence relation between J i (r i ) and J j (r j ). Definition 1.1. A legal retiming associates to each job J i an integer value r i so that: r : J → Z, ∀a = (J i , J j ) ∈ A r j + h(a)r i ≥ 0

Now considering a legal retiming, if r j + h(a)r i = 0 then <J i (r i ), k> precedes <J j (r j ), k> for enough large integer k. So that the precedence relations induced by the uniform constraint is now within an iteration of the shifted jobs. Otherwise, <J i (r i ), k> precedes an occurrence <J j (r j ), k > with k > k which belongs to a next iteration. Hence for these new generic operations (J i (r i )) 1≤i≤n , the first iteration fulfills the non cyclic precedence relations given by a graph called G r computed from G by keeping only the arcs a = (J i , J j ) for which r j + h(a)r i = 0. to get a feasible retiming r so that G r has no arcs. Thus at the compaction step, only independent jobs have to be considered. Hence if the underlying non cyclic scheduling problem is easily solvable for independent tasks then the DSP approach provides an optimal periodic schedule. This occurs for example in cyclic shop-like problems (open shop, job-shop) if, unlike in [START_REF] Pempera | Open shop cyclic scheduling[END_REF], no limitation on the completion time of an iteration, or on the interleaving between iterations is given.

List scheduling algorithms are the most used heuristics for scheduling with precedence and resource constraints. Efficiency of these algorithms in practice is well known. Moreover usually a worst case performance guarantee can be determined in most resource context, from the parallel processors to RCPSP settings where a job may require several units of different resources during its execution.

Using such algorithms at the compaction step leads to a worst case ratio on the periodic schedule. This has been considered for parallel processors [START_REF] Gasperoni | Generating close to optimum loop schedules on parallel processors[END_REF][START_REF] Darte | Loop shifting for loop compaction[END_REF] and extended to RCPSP in [START_REF] Benabid | Worst case analysis of decomposed software pipelining for cyclic unitary RCPSP with precedence delays[END_REF].

Energy saving or other resource dependent constraints

In this section we consider problems issued from sensor networks, and in particular the scheduling problems induced by the IEEE 802.15.4/ZigBee network. Here the jobs represents data communications. Now, in real networks, while dealing with periodic schedules, the period is quite long with respect to the processing times of jobs. Moreover, the resources involved in the communication must be awaken to perform the jobs during each period. To avoid energy loss due to many in and out of the resources, it can be interesting to group jobs using the same resource as much as possible, so that the resource is awaken during a short interval once per period. In the context of periodic schedules, this will induce constraints on the core of the schedule, regardless the occurrence number of the concerned jobs.

Let us now present a model of data-flows inspired by the ZigBee norm, introducing grouping constraints. This work is issued from [START_REF] Hanen | Grouping tasks to save energy in a cyclic scheduling problem: a complexity study[END_REF][START_REF] Ahmad | An energy efficient schedule for IEEE 802.15.4/zigbee cluster tree WSN with multiple collision domains and period crossing constraint[END_REF]. We consider a tree T , whose nodes represent the clusters and whose edges represent the logical links between them. We then consider a collection of flows. Each flow f is defined by a copy of a subtree of T , oriented as an in-tree, and represents the communication of data along the communication links of T from source nodes of the flow to the unique sink. For flow f , if node i belongs to the sub-tree of f , then we denote, by J i f , the communication task associated to node i in flow f . Figure 1.12 shows an example of a tree consisting of seven clusters and two flows.

An iteration of each flow will start at each period. Moreover, the energy constraints of the ZigBee standard consider that each cluster should be active once in each period. So tasks J i f for all flows f passing through node i belong to group i, which should be grouped in the period.

Of course, if we do not limit the time of delivery for each flow, then the periodic scheduling problem can be handled in polynomial time by considering a retiming that lead to independent jobs. However, if we wish to achieve a good response time,

J 7 2 J 2 2 J 3 2 J 4 2 J 5 2 J 1 1 J 2 1 J 3 1 J 4 1 J 6 1 (1,0) (1,2) (1,0) (1,0) (1,0) (1,0) (1,0) (1,0) (1,0) (1,2)
Fig. 1.12: An example of the tree T and two flows, and the associated uniform graph we need to fix some time limits. We assume here that for each flow f the number of periods crossed by f from a source until its delivery should be less than a given integer p f . The experiments with a scheduling tool [START_REF] Ahmad | An energy efficient schedule for IEEE 802.15.4/zigbee cluster tree WSN with multiple collision domains and period crossing constraint[END_REF], which enables system designers to configure all the required parameters of the IEEE 802.15.4/ZigBee cluster-tree WSNs, illustrate the efficiency of the model. Moreover, this model induces for each flow a representation of the constraints induced by the data flow by a uniform graph:

1. The nodes of G are for each flow the tasks J i f . 2. If there is a communication link J i f → J j f in the underlying sub-tree, then (J i f , J j f ) is an arc of G with h value 0.

If J i

f is the sink of the flow f and J j f is a source, there is an arc from J i f to J j f with h(J i f , J j f ) = p f + 1. Figure 1.12 depicts the graph associated to the two flows, considering p 1 = p 2 = 1.

Consider now a uniform task system G, and assume that each job has a group label k i ∈ {1, . . . , K}. A periodic schedule is said to be grouped if the tasks of the same group are executed close to each other in the core. This notion can be expressed by different means, but we can choose the simplest way here, where each group is to be scheduled as a single super-task in the core schedule. In the context we consider here, the period is usually large with respect to the processing times so we can consider that the complexity induced by the schedule of the jobs inside a super-task is not worth. As we consider here feasibility questions, we assume in the following that the super-task has a unit processing time, but the same results can be obtained by considering sum or max of the processing times of the grouped jobs.

Though the ZibBee feasibility question turns out in the following question: Given a uniform precedence graph G and group labels of the tasks, does a grouped periodic schedule of G exist? We call the UGF (Uniform Grouped Feasibility), this decision problem.

One can easily see that for some instances no grouped periodic schedule exists. If we consider our example assuming p 1 = p 2 = 0 this means that the first execution of all jobs have to be scheduled during the first period. As <J 2 1 , 1> precedes <J 3 1 , 1> for the execution of the first flow, and <J 3 2 , 1> precedes <J 2 2 , 1> for the second flow, and as J 2 1 , J 2 2 (resp. J 3 1 , J 3 2 ) belong to the group of node 2 of the tree (resp. node 3), we get a contradiction.Figure 1.13 shows a core of a grouped schedule for the example of figure 1.12. We prove in [START_REF] Hanen | Grouping tasks to save energy in a cyclic scheduling problem: a complexity study[END_REF] that the general UGF problem is

J 1 1 J 2 1 J 3 1 J 2 2 J 3 2 J 5 2 J 4 2 J 6 1 J 4 1 J 7 2
Fig. 1.13: A core of a grouped periodic schedule -grouped jobs are shown by colors NP-Complete, but the specificity of the tree underlying communication path for the ZigBee problem lead to a polynomial algorithm, based on the use of decomposed software pipelining, which proves its efficiency in practice in [START_REF] Ahmad | An energy efficient schedule for IEEE 802.15.4/zigbee cluster tree WSN with multiple collision domains and period crossing constraint[END_REF].

In [START_REF] Hanzálek | The impact of core precedences in a cyclic RCPSP with precedence delays[END_REF] the authors explore a weaker way of considering grouping in a uniform task system by introducing precedence constraints with arbitrary latencies on the core schedule, called core constraints. Unfortunately, they prove that even if no additional resource constraints is assumed, and if unit processing times are considered, deciding the existence of a periodic schedule is also NP-complete.

Synchronous data flows

This section aims to present several important theoretical results on normalized SDF. The feasibility and the evaluation of the minimum normalized average cycle time are two challenging problems for which the complexity is unknown. Subsection 1.5.1 presents some algorithms to answer these two questions. Subsection 1.5.2 is dedicated to characterization of a periodic feasible schedule of minimum period, leading to a polynomial time algorithm to compute it. This characterization is considered to optimize the total buffers capacity under a minimum period constraint in subsection 1.5.3. Lastly, subsection 1.5.4 is dedicated to the computation of the latency for a real-time application which communications between tasks are modelled using a SDF.

Feasibility and evaluation of the minimum normalized average cycle time

Let us suppose that G = (J , A, u, v, M 0 ) is a normalized SDF. G is feasible (or live) if there exists an infinite feasible schedule. Following Theorem 1.1, the simplest way to test the feasibility is to execute the jobs as soon as possible until each job J i is executed at least N i times. If it is possible, G is live.

The main drawback of this method is that values N i are not polynomial and may be quite huge for real-life systems. From a theoretical point of view, the complexity of checking the feasibility of a SDF remains unknown. However, a simple sufficient condition of feasibility was proved by Marchetti ans Munier [START_REF] Marchetti | A sufficient condition for the liveness of weighted event graphs[END_REF][START_REF] Marchetti | Cyclic scheduling for the synthesis of embedded systems[END_REF].

Theorem 1.7 (Sufficient condition of feasibilty of a SDF). Let G be a normalized SDF. If, for any circuit c ∈ C (G), the inequality

∑ a∈c M 0 (a) > ∑ a=(J i ,J j )∈c Z j -gcd(Z i , Z j ) is true, then G is feasible.
Checking this condition requires to label each arc of a = (J i , J j ) of the SDF by V (a) = Z jgcd(Z i , Z j ) -M 0 (a) and testing that the sum of the labels of each circuit remains strictly negative. As example, Figure 1.14 pictures the SDF from Figure 1.1 with arcs a = (J i , J j ) valued by V (a). This graph has nos positive or null valued circuits, thus G is feasible.

Checking the existence of positive circuits can be done using a two steps polynomial time algorithm: the first step consists on checking the non existence of positive or null valued circuits using Bellmann-Ford algorithm [START_REF] Cormen | Introduction to Algorithms[END_REF]. A depth-first search algorithm applied only to critical arcs allows to check the non existence of null-valued circuits.

= (J i , J j ) valued by V (a) = Z j - gcd(Z i , Z j ) -M 0 (a)
Munier [START_REF] Munier | Régime asymptotique optimal d'un graphe d'événements temporisé généralisé: application à un problème d'assemblage[END_REF] proved that the earliest schedule of a SDF is K-periodic. Thus, the simplest way to evaluate the minimum normalized average cycle time is to compute the earliest schedule until the convergence of the normalized average cycle time. Another way is to compute the expansion of the graph, and determine its average cycle time. The main drawback of these two methods is that they are not polynomial, and thus not efficient whenever Σ n i=1 N i is important. Bodin et al. [START_REF] Bodin | K-periodic schedules for evaluating the maximum throughput of a synchronous dataflow graph[END_REF] have proved that, for any integer vector of n components X ≥ 1 n an expansion G X (which is a uniform precedence graph) of G can be defined. For any arc a = (J i , J j ), arcs of G X between the duplicates of J i and J j models a superset of precedence constraints between J i and J j . They also show that dominant values for the computation of the minimum normalized average cycle can be achieved for the vector set {X ∈ N n : ∀i ∈ {1, • • • , n} (X i divides N i )}. These expansions can be used to get upper-bounds of the minimum normalized average cycle.

Algorithm 1 was also developed by Bodin et al. [START_REF] Bodin | Optimal and fast throughput evaluation of CSDF[END_REF] to compute the minimum normalized average cycle time by expanding only jobs of the successive critical circuits. Although non polynomial, this algorithm allows to evaluate quickly this value for industrial instances of large size.

Algorithm 1: Computation of the minimum normalized average cycle time

Require: A normalized SDF G = (J , A, u, v, M 0 ). Ensure : Normalized minimum average cycle time λ (G) of G.

1 Set M = (Z 1 , • • • , Z n ), ∀i ∈ {1, • • • , n} (N i = M Z i ); 2 Set X = 1 n
, G X the corresponding expanded graph and c a critical circuit of G X ; 3 while every job J i of c is not expanded N i times do 4 Set X i = N i for every job J i of c; 5 Update G X and a critical circuit c of G X ;

6 Let λ (c) be the average cycle time of G X ; λ (G) = λ (c) X 1 ;

Existence and Computation of a periodic schedule of minimum average cycle time

We show in this section that the determination of a feasible periodic schedule of minimum period is a polynomial problem for a normalized SDF. A schedule s is periodic if for any job J i , there exists w i ∈ Q + with ∀n > 1 s(J i , n) = s(J 1 , 1) + (n -1)w i . Benabid et al. [START_REF] Benabid-Najjar | Periodic schedules for bounded timed weighted event graphs[END_REF] have proved Theorem 1.8 that characterizes periodic schedules.

Theorem 1.8. Let G be a normalized strongly connected SDF. For any periodic schedule s, there exists a rational λ s ∈ Q + such that for any job J i , w i Z i = λ s . Moreover, the precedence relations associated with any place a = (J i , J j ) are fulfilled by s iff s(J j , 1)s(J i , 1) ≥ p i + λ s (Z j -M 0 (a)gcd(Z i , Z j )).

λ s is then the average cycle time of s.

Since length p i > 0 for any job J i , there exists a periodic schedule for G iff for any circuit c ∈ C (G), the inequality ∑ a=(J i ,J j )∈c (Z j -M 0 (a)gcd(Z i , Z j )) < 0 holds, which is exactly the condition of feasibility of Theorem1.7. If this condition is true, the minimum average cycle time λ s can then be computed by finding critical circuits of the graph G 1 with the same structure of G and for which each arc a = (J i , J j ) is bi-valued by (p i , M 0 (a) + gcd(Z i , Z j ) -Z j ).

Consider for example the bi-valued graph G 1 pictured by Figure 1.15 and associated with the graph G of Figure 1

.1. The critical circuit of G 1 is c = (J 1 , J 3 , J 2 , J 1 ) with ratio λ (c) = 1+2+2 -4+3+2 = 5.
Thus the minimum normalized average period of a periodic schedule is λ s = 5.

J 1 J 2 J 3 J 4 (1, -4) (2, 3) (1, -1) (2, 2) (1, 4)
(2, 0) Fig. 1.15: SDF G from Figure 1.1 with arcs a = (J i , J j ) bi-valued by (p i , M 0 (a) + gcd(Z i , Z j ) -Z j )

Optimization of the total buffers capacity under a minimum period constraint

SDF can be considered to model data exchanges [START_REF] Lee | Synchronous data flow[END_REF] for streaming applications.

Jobs correspond here to programs that are repeatedly executed. Arcs are associated to buffers. The total amount of memory needed to execute an application is an important criteria for the designers due to the cost of the memories. Thus, the minimization of the total buffers capacity under a minimum period constraint is an important bi-criteria optimization problem. The capacity F(a) of an arc a is the maximum number of tokens that can be stored simultaneously in the buffer corresponding to a. First at all, Marchetti and Munier proved in [START_REF] Marchetti | Complexity results for weighted timed event graphs[END_REF] that the capacity of a buffer may be modelled using a back-ward arc as follows by studying the precedence relations induced by this capacity constraints.

Theorem 1.9. Any arc a = (J i , J j ) initially marked by M 0 (a) with a capacity limited by F(a) ≥ M 0 (a) may be replaced by a couple of arcs (with no limited capacity) a 1 = (J i , J j ) and a 2 = (J j , J i ) with M 0 (a 1 ) = M 0 (a) and M 0 (a 2 ) = F(a) -M 0 (a) (see Figure 1 Let G s = (J , A s , u, v, M 0 ) be the SDF associated to G for which each arc a with a limited capacity is replaced by a couple of arcs (a 1 , a 2 ). For any arc a, we denote by θ (a) > 0 the size needed to store one unique data in a. The size of a is then F(a) × θ (a) and the total size is thus

.16). J i J j J i J j Z i Z j Z i Z j Z j Z i a = (J i , J i ) with bounded capacity F(a) M 0 (a) ≤ F(a) a 1 = (J i , J i ) and a 2 = (J j , J i ) M 0 (a 1 ) = M 0 (a) and M 0 (a 2 ) = F(a) -M 0 (a)
F = ∑ a∈A θ (a)F(a) = ∑ a∈A s θ (a)M 0 (a)
The optimization problem addressed here is to find an initial marking M 0 (a), a ∈ A s such that the total size of the memories ∑ a∈A s θ (a)M 0 (a) is minimum, while there exists a schedule with a normalized average cycle time at most equal to K.

Since there is no polynomial algorithm to compute the feasibility and the minimum average cycle time of a SDF, we do not know if this problem belong to N P. Several authors limit their study to periodic schedules in order to get around this problem. In this case, the optimization problem can be expressed easily using the following Integer Linear Program Π (K):

minimize ∑ a∈A s θ (a)M 0 (a) subject to        ∀a = (J i , J j ) ∈ A s s(J j , 1) -s(J i , 1) ≥ p i -K(M 0 (a) + gcd(Z i , Z j ) -Z j ) ∀a = (J i , J j ) ∈ A s M 0 (a) = k i, j • gcd(Z i , Z j ) ∀a = (t i ,t j ) ∈ A s k i, j ∈ N ∀J i ∈ J s(J i , 1) ≥ 0
If the initial marking is not fixed, Marchetti and Munier proved in [START_REF] Marchetti | Complexity results for weighted timed event graphs[END_REF] that this problem is N P-complete even if G is a uniform precedence graph with F(a) = 1 for every arc. Benazouz et al. [START_REF] Benazouz | A new approach for minimizing buffer capacities with throughput constraint for embedded system design[END_REF] developed a 2-approximation ratio algorithm for the general case. The idea of this algorithm is first to solve the associated relaxed linear program. An approximated solution is then built using a classical rounding technique.

Evaluation of the latency for real-time systems

Consider a normalized SDF G without circuits issued from a set of real-time Jobs which are communicating as described in section 1.3.2. The problem is to evaluate efficiently the latency of the system. Latency is a measure of the response time of the system, it is thus fundamental for real-time systems.

Let us define the maximum (Resp. minimum) latency L max (Resp. L min ) between two connected jobs J i and J j as the maximum (Resp. minimum) duration between the end of an execution of <J i , n i > and the start of an execution of <J j , n J > such that there is a precedence relation from <J i , n i > to <J j , n J >. Theorem 1.10 proved by Khatib et al. [START_REF] Khatib | Computing latency of a real-time system modeled by synchronous dataflow graph[END_REF], expresses the minimum and the maximum latency between two periodic communicating jobs: Theorem 1.10. The maximum and the minimum latencies between a couple of periodic jobs (J i , J j ) such that J i communicates data to J j are L min (J i , J j ) = r jr i + α -C i and L max (J i , J j ) = r jr i -max{0, T i -T j } + α -T a + T i -C i with T a = gcd(T i , T j ) and α = r i -r j +C i T a × T a .

Consider for example the two communicating jobs J 1 and J 2 from Figure 1.9. We get α = 10, T a = 10, L min (J 1 , J 2 ) = 0 and L max (J 1 , J 2 ) = 10. The delay between the end of <J 1 , 1> and the beginning of <J 2 , 1> equals 0 and corresponds to L min (J 1 , J 2 ).

The delay between the end of <J 1 , 2> and the beginning of <J 2 , 1> equals 10 and corresponds to L max (J 1 , J 2 ).

The latency of the entire system is a time gap from a data input of a system to a connected outcome. The worst-case latency is then the longest time gap between the input Job executions and output Job executions of a system.

The exact evaluation of the latency can be obtained by computing an expanded valued graph [START_REF] Khatib | Computing latency of a real-time system modeled by synchronous dataflow graph[END_REF]. Each vertex J i is duplicated N i times. Arcs correspond to relations between executions and are valued by the exact latency between the corresponding executions following Theorem 1.10. This method is clearly not polynomial and is not efficient for large repetition vectors. Now, let G max = (J ∪ {s, d}, A m , w) be the graph built from the SDF G as follows.

• Let a = (J i , J j ) be an arc of G with T a = gcd(T i , T j ). An arc e = (J i , J j ) is built for G max with

w(e) =    C i T a T a + T i -T a if T i ≤ T j C i T a
T a + T i T j T j -T a otherwise

• For any job J i without predecessor, add the arc e = (s, J i ) with w(e) = 0; for any job J i without successor, add the arc e = (J i , p) with w(e) = D i .

Khatib et al. [START_REF] Khatib | Computing latency of a real-time system modeled by synchronous dataflow graph[END_REF] proved that an upper bound of the maximum latency can be computed by evaluating the longest paths of G max . On the same way, a lower bound of the maximum latency can be computed by evaluating the longest paths of G min = (J ∪ {s, d}, A m , w ) defined as follows :

• For any arc e ∈ A m corresponding to an arc a = (J i , J j ) ∈ A, w (e) = C i T a T a .

• For any job J i without predecessor, add the arc e = (s, J i ) with w (e) = 0; For any job J i without successor, add the arc e = (J i , p) with w (e) = D i They also experimentally show that the gap between the exact value and the upper (resp. lower) bound varies between 10 and 15% (resp. 20 and 30%).

Let us consider the real-time system of section 1.3.2 adding a communication from J 1 to J 3 . Corresponding graphs G min and G max are pictured by Figure 1.17. The value of longest paths of these two graphs are respectively equal to 90 and 60.

G min

Fig. 1.17: G min and G max for the real-time system of section 1.3.2

Conclusion

Cyclic scheduling problems arise in many crucial applications of computing and real time systems. Data transfers and data dependences induce specific precedence constraints, that have been analyzed and sometimes combined with resource constraints. In this chapter we proposed an insight on the main theoretical tools and

  .2 presents the first executions of the earliest schedule of the SDF of Figure 1.1. Let us define the weight of any circuit c of G by W (c) = Π a∈c u(a)

Fig. 1 . 3 :

 13 Fig.1.3: Precedence relations between first executions of J 1 and J 2 and the arc a = (J 1 , J 2 ) with u(a) = 2, v(a) = 3 and M 0 (a) = 1. Jobs J 1 and J 2 are supposed to be re-entrant.

Fig. 1 . 4 :

 14 Fig. 1.4: Normalized graph G associated with G

Fig. 1 . 5 :

 15 Fig. 1.5: Expansion of the graph composed by two non re-reentrant jobs J 1 and J 2 and the arc a = (J 1 , J 2 ) with u(a) = 2, v(a) = 3 and M 0 (a) = 1

Fig. 1 .

 1 Fig. 1.7: A uniform graph modeling a loop. Arcs are labelled with ( , h)

Fig. 1 . 8 :

 18 Fig. 1.8: An optimal periodic schedule

J 1 Fig. 1 . 9 :

 119 Fig.1.9: Communications between successive executions of jobs J 1 , J 2 and J 3

2 Fig. 1 . 10 :

 2110 Fig. 1.10: Graph of Figure 1.7 valued by V λ for λ = 6. First execution times s i ∈ J of a feasible periodic schedule of period 6 are reported in the squares.

Fig. 1 .

 1 Fig. 1.14: SDF G from Figure 1.1 with arcs a= (J i , J j ) valued by V (a) = Z jgcd(Z i , Z j ) -M 0 (a)

Fig. 1 .

 1 Fig. 1.16: Transformation of an arc e with a capacity bounded by F(a) into a coupe of arcs with no capacity constraint

Cyclic DataFlows in computers and embedded systems

Several ideas have been investigated to find a legal retiming for nonnegative uniform task systems. Notice first that a retiming can always be found from any strict periodic schedule s fulfilling the uniform constraints.

Let s be a strict periodic schedule with period λ . For any job J i , s i can be uniquely decomposed with respect to the period: s i = t i + λ .q i , with 0 ≤ t i < λ and q i is an integer. (t i ) {J i ∈J } is called the core of the periodic schedule, and (q i ) {J i ∈J } is the shift of the periodic schedule.

The shift (q i ) {J i ∈J } is a feasible retiming. This property was used by Gasperoni and Schwiegelsohn [START_REF] Gasperoni | Generating close to optimum loop schedules on parallel processors[END_REF] by finding the shift of an optimal periodic schedule assuming unlimited resources. Figure 1.11 shows the graph G r considering the retiming associated with the shift of the optimal schedule depicted in figure 1.8.

In [START_REF] Calland | Circuit retiming applied to decomposed software pipelining[END_REF], where using retiming for loop shifting is formalized, the authors consider two optimizations, with polynomial graph algorithms:

• the length of the longest path in G r minimization • the number of arcs in G r minimization, so as to reduce the number of precedence constraints for loop compaction.

core with λ = 8 The idea behind DSP approach is to choose a particular retiming r, and then use an algorithm to get a schedule (t i ) {J i ∈J } of G r , fulfilling the resource constraints to get a periodic schedule of the original problem.

This relies on the following result:

Theorem 1.6. If r is a feasible retiming, and (t i ) {J i ∈J } is a schedule fulfilling the non cyclic precedence constraints of G r and the resource constraints, then there exists a periodic schedule s whose core is (t i ) {J i ∈J } and whose shift is (r i ) {J i ∈J } .

Figure 1.11 shows a construction of a core for our example, assuming that arithmetic operations are performed on one of the two available ALU's, while memory jobs (load and store) use one ALU and one memory controller at the same time. The makespan of the schedule (t i ) {J i ∈J } , combined with the observation of precedence constraints crossing the core lead to the computation of a period λ in polynomial time [START_REF] Ayala | The resource-constrained modulo scheduling problem: an experimental study[END_REF]. For our example λ = 8.

From this an interesting special case can be noted: if G has no circuit (except the ones due to the non-reentrance hypothesis for jobs), then it is always possible algorithms of the field, and gave the flavor of the most recent questions and results.

Several questions remain open, from complexity to algorithmic issues. We hope that the readers will further contribute to their solutions.


est destinée au dépôt

  Effect of early postextubation high-flow nasal cannula vs conventional oxygen therapy on hypoxaemia in patients after major abdominal surgery: a French multicentre randomised controlled trial (OPERA) Emmanuel Futier, Catherine Paugam-Burtz, Thomas Godet, Linda Khoy-Ear, Sacha Rozencwajg, Jean-Marc Delay, Daniel Verzilli, Jeremie Dupuis, Gerald Chanques, Jean-Etienne Bazin, et al. To cite this version: Emmanuel Futier, Catherine Paugam-Burtz, Thomas Godet, Linda Khoy-Ear, Sacha Rozencwajg, et al.. Effect of early postextubation high-flow nasal cannula vs conventional oxygen therapy on hypoxaemia in patients after major abdominal surgery: a French multicentre randomised controlled trial (OPERA). Intensive Care Medicine, 2016, 42 (12), pp.1888 -1898. 10.1007/s00134-016-4594-y. hal-01781339