Carole Delporte-Gallet

Hugues Fauconnier

Eli Gafni

Sergio Rajsbaum
email: rajsbaum@math.unam.mx

Sergio Rajsbaum Linear

Linear Space Boostrap Communication Scheme

Keywords: shared memory, read/write registers, distributed algorithms, wait-free, space complexity, renaming

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

In many distributed algorithms it is assumed that the processes, p 1 , . . . , p n , communicate using Single-Writer Multi-Reader (SWMR) registers, R 1 , . . . , R n , so p i knows it is the i-th process, and can write exclusively to R i . However, often processes do not know their indexes, they know only their ids, and the number of possible ids N , is much bigger than the number of processes, n. In this situation, preallocating a register for each identifier would lead to a distributed algorithm with a very large space complexity. One would like the processes to run a renaming algorithm as a preprocessing stage, to obtain new ids from a smaller range, M (n), that depends only on n, and then use these ids to index only M (n) SWMR registers. Several waitfree renaming algorithms e.g. [START_REF] Attiya | Renaming in an asynchronous environment[END_REF][START_REF] Borowsky | Immediate atomic snapshots and fast renaming[END_REF] are known that reduce the name space to M (n) = 2n -1 (and this is the best than can be done, except for some exceptional values of n [START_REF] Castañeda | New combinatorial topology bounds for renaming: the lower bound[END_REF]). However, if the system did not allocate N SWMR register to start with, how do the processes communicate to run the renaming algorithm? Such a question has been considered in the context of adaptive computation [START_REF] Attiya | Polynominal and adaptive long-lived (2k-1)-renaming[END_REF][START_REF] Attiya | Adaptive and efficient algorithms for lattice agreement and renaming[END_REF][START_REF] Moir | Fast, long-lived renaming improved and simplified[END_REF][START_REF] Afek | Efficient adaptive collect algorithms[END_REF][START_REF] Aguilera | A pleasant stroll through the land of infinitely many creatures[END_REF]. In these papers, n is unknown, and moreover processes "arrive" and "depart." When first solving adaptive renaming to allocate MWMR registers to processes, they obtain Θ(n 2 ) space complex-ity. The first basic question we address here is: In the most favorable situation, when n is known and we want to solve is a task, how much space do we need? Is solving renaming first unavoidable?

Recall that a task e.g. [START_REF] Herlihy | The topological structure of asynchronous computability[END_REF] is a one shot problem, where processes start with inputs and after communicating with each other, must decide on outputs that satisfy the task's specification. Famous examples of tasks are consensus and set agreement.

We show that indeed it is possible to solve any read-write wait-free solvable task with n MWMR registers. To obtain this result, the paper shows how the processes can non-blocking emulate a system of n SWMR registers on top of n MWMR registers. Moreover, as we explain, it is not hard to prove that no such emulation exists on less than n MWMR registers.

An application of the non-blocking emulation is that one can run any SWMR wait-free algorithm that solves a task on n MWMR registers. In particular, one can run directly a SWMR (2n -1)-renaming algorithm such as the one of [START_REF] Borowsky | Immediate atomic snapshots and fast renaming[END_REF] on top of n MWMR registers. This is a significant improvement over the previous adaptive Θ(n 2 ) space renaming algorithm, when that algorithm is instantiated to our context. Admittedly, the previous renaming algorithm will actually use fewer than n 2 registers but nevertheless since it is apriori unknown how the algorithm will evolve a preallocation of Θ(n 2 ) registers is necessary. Notice that as the simulation is non-blocking, a SWMR algorithm that solves a task on top of the n MWMR registers may incur some cost in time: a process may not be able to produce an output value, until another process finishes the algorithm and exits the emulation.

As said, with n registers we can solve (2n -1)renaming, using these new names, with additional 2n -1 registers each process can obtain a dedicated register, and from there on emulate a simulated write operation in a wait freemanner. Are 3n -1 MWMR necessary to have a wait-free emulation of a write operation in a non-terminating environment? We show that a total of just 2n -1 MWMR registers is sufficient, describing how the processes can wait-free emulate a system of n SWMR registers on top of 2n -1 MWMR registers. We conjecture that 2n -1 registers are the minimum possible for wait-free emulation. The wait-free emulation allows to solve a sequence of tasks (potentially infinite) that are sequentially dependent (processes need the previous task's outputs in order to proceed to the next task). A non-blocking emulation might starve a process forever. By doubling the space complexity, using 2n -1 rather than just n registers, the computation is wait-free rather than non-blocking.

The paper also describes an algorithm to broadcast the value of one of the processes, using n/2 MWMR registers. The algorithm, which seems interesting in itself, illustrates the way information propagates in our emulations. It is simple, but the proof is subtle.

At the end of the paper we briefly discuss why we believe our techniques will be useful for dynamic systems of bounded concurrency n e.g. [START_REF] Aguilera | A pleasant stroll through the land of infinitely many creatures[END_REF]. In such a system, any number of processes arrive compute and depart, yet, at any point in time the number of arrivals exceeds the number of departures by at most n.

We stress that our interest is in space complexity, our emulations are not particularly efficient in terms of step complexity. Also, there are various previous papers dealing with a similar problem, but in the adaptive setting. In [START_REF] Attiya | An adaptive collect algorithm with applications[END_REF] there is a definition similar to our emulation problem, as "store-collect" of a (key,value) problem. Another definition of store-collect, by equivalence to an array (hence more like our problem specification) appears in [START_REF] Afek | Long-lived adaptive collect with applications[END_REF]. Similarly, solutions without explicitly solving renaming first appear in [START_REF] Attiya | Algorithms adapting to point contention[END_REF], although not very space efficient.

There is a long history of space complexity results, starting with the mutual exclusion lower bound of [START_REF] Burns | Bounds on shared memory for mutual exclusion[END_REF] and even before there was interest in this (see references herein). In this context, [START_REF] Styer | Tight bounds for shared memory symmetric mutual exclusion problems[END_REF] considers renaming with the same motivation that we do, and shows that 2 logn + 1 registers are sufficient to solve it, and a corresponding lower bound within a constant factor, but their model is easier than ours. There are various algorithms and lower bounds on the number of registers needed to solve specific problems e.g. [START_REF] Fatourou | Space-optimal multi-writer snapshot objects are slow[END_REF][START_REF] Fatourou | Time-space tradeoffs for implementations of snapshots[END_REF][START_REF] Helmi | The space complexity of long-lived and one-shot timestamp implementations[END_REF][START_REF] Moir | Fast, long-lived renaming improved and simplified[END_REF], but we are not aware of general emulations. In [START_REF] Jayanti | Time and space lower bounds for nonblocking implementations[END_REF] there is a lower bound for non-blocking implementations, but it is n -1 registers. In special cases it can be beaten [START_REF] Aspnes | Polylogarithmic concurrent data structures from monotone circuits[END_REF]. In [START_REF] Fich | On the space complexity of randomized synchronization[END_REF] a Ω( √ n) space complexity lower bound for a randomized nonblocking implementation of consensus is presented.

Model

We assume a standard asynchronous sharedmemory model of computation with n processes communicating by reading and writing to a fixed set of shared registers [START_REF] Attiya | Distributed Computing. Fundamentals, Simulations, and Advanced Topics[END_REF][START_REF] Herlihy | The Art of Multiprocessor Programming[END_REF]. The processes have unique ids in {1, . . . , N }, with N >> n. Processes may take a finite or an infinite number of steps but we assume that at least one process takes an infinite number of steps.

The shared memory consists of a set of atomic Multi-Writer Multi-Readers (MWMR) registers. We assume that processes can read and write any MWMR register and these operations are atomic [START_REF] Herlihy | Wait-free synchronization[END_REF]. For short, we usually omit the term atomic. If r is such a MWMR register, a process can write x on r using write(r, x), and read on r using read(r). A process executes its code taking three types of atomic steps: the read of a register, the write of a register, and the modification of its local state.

We consider also more powerful operations to read the registers. A collect is an iterative read of all registers. A scan returns a snapshot, an instantaneous view of the registers. In [START_REF] Afek | Atomic snapshots of shared memory[END_REF], there are non blocking and wait free linearizable implementations of the scan. A non-blocking implementation of scan (N BScan) can be obtained repeating Collect operations until two of them return the same values. A scan wait-free implementation (Scan) is more involved, and has to embed a snapshot with the write. So in this case we call the write, update (update(r, v) updates the register r with the value v).

Two progress conditions that have received much attention are non-blocking and wait-free. The non-blocking progress condition states that when there are concurrent operations at least one process terminates its operations. The wait-free [START_REF] Herlihy | Wait-free synchronization[END_REF] progress condition states that each process terminates its operations in a bounded number of its own steps.

We consider also a model in which each process has its own atomic Single-Writer Multi-Reader register (SWMR). Process p can write a value x in its SWMR register with the operation write(p, x) and all the processes may read the value in the SWMR register of p with read(p).

We say that we have a non-blocking (resp. wait-free) emulation of the n process SWMR model using m MWMR registers if we implement write and read in terms of write and read such that the implementation is linearizable [START_REF] Herlihy | Linearizability: A correctness condition for concurrent objects[END_REF] and the progress condition is non-blocking (resp. wait free).

A regular SWMR register [START_REF] Lamport | On interprocess communication; part I and II[END_REF], is a weaker type of register. A SWMR register is regular if when no write is concurrent with a read operation, the read returns the current value in the register. Otherwise the read returns any value written by a concurrent write operation or the last value in the register before the concurrent writes. With regular SWMR registers it is possible to wait-free free implement atomic SWMR register [START_REF] Herlihy | The Art of Multiprocessor Programming[END_REF][START_REF] Lamport | On interprocess communication; part I and II[END_REF]. So to emulate non-blocking (resp. wait-free) the n process SWMR register model using m MWMR registers it is enough to emulate non-blocking (resp. wait-free) n process model with regular SWMR register model.

Preliminaries

We consider algorithms that have the same structure as algorithm in Figure 1. Processes share a set R of MWMR registers. Each process maintains a variable V iew. Each process repeatedly reads all registers (function Collect()) and updates its variable V iew by adding all it has just read in V iew together with some other values in variable input, and then writes it in some registers.

For each R ∈ R, R τ denotes the value of register R at time τ . Similarly, V iew τ p denotes the value of variable V iew of p at time τ .

We say that v is eventually forever in R if there is a time τ such that for all time τ > τ , v ∈ R τ .

function Collect():

1 V = ∅ 2 for all R in R 3 V = V ∪ read(R) 4 return V main loop: repeat forever 5 V iew = Collect() ∪ V iew ∪ input 6
Let (deterministically) Reg be some register in R We have directly from the algorithm:

Observation 1 For all processes p and for all times τ and τ , if τ < τ then V iew τ p ⊆ V iew τ p Following [START_REF] Burns | Bounds on shared memory for mutual exclusion[END_REF], we say that register R is covered by process p at some time τ if the next register that p writes after time τ is R: more precisely p covers R at time τ if, at time τ , the next writing of p (Line 7) is on register R and p has begun the Collect in Line 5. Note that if p does not cover R, before writing R, p reads the value of R (by Collect in Line 5) and then it will write in R at least this value.

If some register is covered the value of this register may be lost. So, by extension, we say that R is V -covered at time τ if all processes covering R at time τ are going to write sets containing V in register R. If R is V -covered at time τ , next writings contains V (by processes covering R) or contains R τ (by processes not covering R that read R before writing). We have:

Lemma 2 If, at some time τ , register R is V - covered at time τ then for all τ ≥ τ , (R τ ∩ V ) ⊆ R τ .
Proof. By induction on the number k of writings of R made after time τ , we prove that R contains R τ ∩ V . For k = 0 it is clear. Consider any writing of R after time τ and assume this writing is made, say, by process q. Consider the two cases:

• either q does not cover R at time τ and then q makes a Collect before writing R. This

Collect occurs after time τ and by induction hypothesis it returns a value containing R τ ∩ V . Then process q writes a superset of R τ ∩ V in register R.

• or q covers R at time τ and V ⊆ V iew p then q writes a superset of R τ ∩ V in R.

If no process covers R at time τ , then by definition R is V -covered for any set V , then by the previous Lemma after time τ , R contains forever R τ . In particular: Lemma 3 If R is not covered at time τ and v ∈ R τ then v will be eventually forever in R.

Let R ∞ be the set of registers infinitely often written:

Lemma 4 If v is eventually forever in R then v is eventually forever in all registers in R ∞ .
Proof. There is a time τ after which v is forever in R, after this time all Collect contains v and then all next writing will contain v. Hence all registers infinity often written will contain v.

Lemma 5 If at time τ , card{R ∈ R|v ∈ R τ } ≥ n, then v will be forever in all registers in R ∞ Proof. Let X be the set of at least n registers containing v and p be the last process that wrote before time τ in any register in X. Just after this writing p does not cover any register. As we have n processes, by the pigeon hole principle at least one register in X is not cover. Then by Lemma 3, v will be forever in some register and by Lemma 4, v will be forever in all R ∞ .

Broadcast

We give here a very weak definition of broadcast. Essentially this definition ensures that the value of some process will be known by all processes making an infinity of steps. More precisely, we assume that each process p has a value v p to broadcast, the broadcast is defined by way of a primitive deliver operation returning a set of values. The broadcast ensures:

• (integrity) if v belongs to the set of values returned by some deliver then v = v p for some process p,

• (convergence) there is a value v and a time τ after which every set returned by any deliver contains v. The algorithm of Figure 2 is a simple application of the generic algorithm of Figure 1. But here in, the main loop, we use a non-blocking scan N BScan instead of Collect. N BScan() returns V , a snapshot of the registers, such that there is a time

1 variable: set of Values V = ∅ 2 for i from 1 to m do 3 V = V ∪ read(R[i])
τ such that R[i] τ = V [i].
N BScan() is only assumed to be non-blocking. Implementation of such non-blocking snapshot is easy [START_REF] Afek | Atomic snapshots of shared memory[END_REF]. As N BScan is a particular form of Collect all previous Lemmata from Section 3 apply. For a snapshot V , V [i] is the value returned for register R[i] and abusing notation, V may denote

∪ 1≤i≤m V [i].
A Deliver reads all the registers and returns the union of the values read in the registers. Note, using Collect() that Deliver always terminate. We prove the main property:

Theorem 6 Algorithm of Figure 2 implements broadcast if m > n 2
The proof is rather subtle, it is in Appendix A.

Non-Blocking emulation of SWMR registers

We first describe the emulation, and then the lower bound, in Section 5.2.

The algorithm

The algorithm in Figure 3 is a non-blocking emulation of regular SWMR registers for n processes using an array R of m MWMR registers, if m ≥ n.

In the following to distinguish between the writings of MWMR registers and the emulation of SWMR writings, we denote the first ones using lower case and the second ones with upper case. To make its k-write, a process p adds the value to write (in fact the value, its identity and its timestamp k) to its variable V iew. The write ends when the value to be written is in all the m registers. A read of value written by process q collects the values present in registers and returns the value from q with a maximal timestamp among all the values from q.

As in the generic algorithm of Figure 1, each process p maintains a variable V iew containing all the information it knows. Iteratively, each process reads all the m registers by a nonblocking scan and accordingly updates its variable V iew before writing it in the next register in cyclic order. The write of v terminates as soon as v is in n registers. Here instead of Collect, we use N BScan, a non blocking Scan, as described in Section 2. //N BScan returns a snapshot of the shared memory write(p, x): The main point here is that as we have n processes and at least n registers then at least one register will not be covered and then all the values contained in this register will eventually be present in all registers and will remain forever in all registers. Hence as soon as a value is present in all registers the write is terminated because afterwards the Collect of every read will contain this value.

1 v = (x, p, k) 2 next = 0 3 V iew = V iew ∪ {v} 4 do 5 Snap = N BScan() 6 V iew = Snap ∪ V iew 7 write(R[next], V iew) 8 next = (next + 1) mod m 9 until (card{r|v in Snap[r]} ≥ n) 10 k = k + 1 read(q): 11 V iew = Collect() 12 return x such that (x, q, u) ∈ V iew with maximal u
First we prove the safety properties of the implementation of regular register.

We say that the write of v succeeds at time τ if there is some register such that after time τ , v is forever in this register. By extension, we say that the write of v succeeds if there is a time at which the write of v succeeds or equivalently if v is eventually forever in R. Directly from the algorithm we get the following lemmas:

Lemma 7 Let v = (x, p, k) and v = (y, p, k ) such that k ≥ k , if v succeeds at time τ , then v succeeds at time τ too.
By Lemma 4 and the code of the algorithm: Lemma 8 If the write of v succeeds at time τ , after this time v is returned by every Collect.

Lemma 9 Let S be the set of all values (x, p, k) that succeed at time τ and K the maximal k over all (x, p, k) in S, then read of p returns the value v = (x, p, k) ∈ S with k ≥ K maximal.

From Lemma 5:

Lemma 10 If at some time τ , v is in n registers, then the write of v succeeds at time τ .

Lemma 11 (safety) Any read(p) returns the last value x such that write(p, x) terminates before the beginning of the read, or a value x such that write(p, x) is concurrent with the read.

Proof. Assume x is the kth write of p, let v be (x, p, k). Consider any read(p) and let E be the set of values returned by the Collect made for this read. By Lemma 8 all values for which the write has succeeded are in E. write(p, x) returns when, for a N BScan (Line 5), v belongs to n registers (Line 9) at some time. Then by Lemma 10, v succeeds by the time of the N BScan and E contains all values for which the write has terminated. Lemma 9 proves that the value returned by the read(p) is either the last value for which the write by p has terminated or a value for which the write is concurrent. Now we prove that the algorithm is nonblocking. First as Collect is wait-free, any read is wait-free too:

Lemma 12 Any read made by a process that takes an infinite number of steps terminates.

By Lemma 4, and the fact that the write ends when the value is in all registers: Lemma 13 Assume the registers are written infinitely often, if the write of v succeeds then v will eventually be forever in all registers and if the process that writes v takes an infinite number of steps, the write terminates. Lemma 14 If the registers are written infinitely often then an infinity of write terminate.

Proof. By contradiction assume the contrary: there is a time τ after which no write terminates. When a process has terminated all its writes it stops writing the registers, then there is at least one process that takes an infinite number of steps and does not terminate the write of some v. By Lemma 13, there is time at which all registers will contain values for which the write is not terminated. By pigeon hole principle one of these registers is not covered and contains a value for which the write is not terminated, by Lemma 3 the write of this value succeeds, and by Lemma 13, the write of this value terminates -a contradiction.

If after some time there is no writing of the registers, being non-blocking any N BScan returns:

Lemma 15 If some process that takes an infinite number of steps is stuck forever on a N BScan then the registers are written infinitely often.

Lemma 16 (non-blocking) If m ≥ n, and the write of v by a process p that takes an infinite number of steps does not terminate, then infinitely often some writes terminate.

Proof.

By contradiction, assume that the write of some process p that takes an infinite number of steps does not terminate and only a finite number of writes occurs. Then by Lemma 14, there is a time after which no registers are written and by Lemma 15, p may not be stuck on a N BScan and hence p makes progress in its code and hence writes registers infinitely often. By Lemma 14 an infinity of write terminates -a contradiction Lemmas 11 and 16 prove that the algorithm in Figure 3 is a non blocking emulation of regular SWMR registers for n processes from n MWM-Rregisters. We now use the classical wait free transformation [START_REF] Herlihy | The Art of Multiprocessor Programming[END_REF][START_REF] Lamport | On interprocess communication; part I and II[END_REF] from regular to atomic registers to conclude: Theorem 17 There is a non blocking emulation of SWMR registers for n processes from n MWMR registers.

Lower bound

We prove in this section that we cannot emulate SWMR registers for n processes with less than n MWMR registers.

Lemma 18 SWMR registers for n processes cannot be emulated with n -1 MWMR registers.

Proof.

Consider a set of n processes p 1 , . . . , p n . By contradiction, assume we can emulate the SWMR system with (n -1)-MWMR atomic registers. We construct inductively a run e where this assumption is not satisfied. For this we construct by induction on k a partial run e k and a set R k of k registers each being covered by processes p 1 , . . . , p k .

(k = 1) : In e 1 only process p 1 takes steps and its code is write(p 1 , p 1 ). Claim: p 1 has to write in some register. Proof. By contradiction assume p 1 does not write in any register and assume the code of p n is read(p 1 ). Once p 1 ends its write, p n takes steps and does not find any value written by p 1 , contradicting the semantics of a register.

In e 1 , only p 1 takes steps and stops just before its first writing of a register, say R 1 . Then p 1 covers R 1 and R 1 = {R}.

(k < n -1) : By induction let e k be such that {p 1 , • • • , p k } covers each register in the set of k registers R k . Run e k+1 extends partial run e k for the process p k+1 that executes the code write(p k+1 , p k+1 ). Claim: p k+1 has to write in some register not in R k . Proof. By contradiction assume p k+1 does not write any register not in R k and assume the code of p n is read(p k+1 ). p k+1 ends its write and has only written registers in R k , then each process in {p 1 , . . . , p k } executes one step and overrides each register in R k . Then p n executes the code for read(p k+1 ). But this execution is indistinguishable (for all processes different from p k+1 ) from one in which p k+1 does not make any write and the read may not return the value written by p k+1 .

In e k+1 , p k+1 takes steps and stops before writing a register that is not in R k , say R k+1 . Then

p k+1 covers R k+1 . Define R k+1 = R k ∪ R k+1 .
When k = n-1, R n-1 contains all the MWMR registers. Now, consider process p n and assume it runs the code write(p n , p n ). Run e n is an extension of e n -1 in which p n takes steps until it ends its write and takes no other steps. Each process executes one step and overrides each register in R n-1 . At this point the value written by p n is not in the local memory of any process (except p n ) and in particular it is not in the local memory of p 1 . Then p 1 ends its write(p 1 , p 1 ), at the end of this write, the value written by p n is not in any MWMR registers and the run is indistinguishable (for all processes different from p n ) from the same run in which p n does not take any write. Now if p 1 runs read(p n ), p 1 cannot get the value written by p n .

Wait-free emulation of SWMR registers

The previous emulation is only non-blocking. Using 3n -1 MWMR registers with help of the simulation of n non-blocking SWMR registers it is easy to simulate n wait-free SWMR registers. For this, the 3n -1 registers are partitioned into a set W of n registers and a set P R of 2n-1 registers. The n MWMR registers of W are used to (non-blocking) simulate n SWMR register with the algorithm of Figure 3. With these n SWMR registers we can run a renaming algorithm [START_REF] Attiya | Renaming in an asynchronous environment[END_REF][START_REF] Borowsky | Immediate atomic snapshots and fast renaming[END_REF]. In fact as such an algorithm always terminates in a finite number of steps it is easy to verify that the non-blocking simulation is enough to ensure that the renaming terminates. Hence each process p of the n processes gets an unique identity id(p) in the set {1, • • • , 2n -1}. To write a value v, p will write in the id(p)th register of P R. As p is the unique writer the simulation is wait-free. But it is possible to reduce the number of MWMR registers to 2n -1. In the algorithm we propose we eventually get an unique identity in the set {1, . . . , n}.

Shared variable :

array of n -1 MWMR-register : W array of n + 1 MWMR-register : PR Local variable: set of Values V iew = ∅ //V iew.proc: set of processes in V iew ordered by names //U pdate, Scan: wait-free snapshot Code for process p init k=0; write(p, x): We present first an algorithm with 2n MWMR registers. The algorithm of Figure 4 has a structure similar to the previous algorithms. Each process maintains a variable V iew containing all information it knows. Here the processes access shared variables using wait free snapshot by means of primitives U pdate and Scan. Implementations of such primitives are described for example in [START_REF] Afek | Atomic snapshots of shared memory[END_REF].

1 v = (x, p, k) 2 next = 0 3 nextReg = W [next] 4 V iew = V iew ∪ {v} 5 N ame = index of p in V iew.proc 6 do 7 Snap = Scan() /*of W and P R*/ 8 V iew = Snap ∪ V iew 9 if (Snap[card(V iew.proc)] = ⊥) then 10 N ame = index of p in V iew.proc 11 U pdate(P R[card(V iew.proc)], V iew)
For a set V of values V.proc denotes the list of all processes occurring in V (process q occurs in V if there is any v = (x, q, s) in V ). For conve-nience all the lists of processes are ordered by process identities. The index of process p in an ordered list of processes is the rank of p in the list. Indexes begins on 0, for example, for 1, 3, 8, 15 the index of 1 is 0 and index of 3 is 1.

In the algorithm the processes share an array W (Working registers) of n -1 MWMRregisters (W [0], . . . , W [n -2]) and an array PR (Personal Registers) of n + 1 MWMR-registers (P R[0], . . . , P R[n]).

Personal registers play a double part: they give the supposed number of participants and give a personal register for each participant. For this, the last cell different from ⊥ gives the supposed number and list of participants: if P R[a] is this last cell then the supposed number of participants is a and the list of participants is P R[a].proc. In the ordered list of assumed participants process p determines its index (variable N ame) and will consider P R[N ame] as its personal register (Lines 5 and 10).

As usual to write a value x (assuming it is the kth), a process adds v = (x, p, k) to its V iew and successively writes (by U pdate and after updating its V iew by Scan in Line 8) to the n -1 registers W (Line 14) and in its personal register P R[N ame](Line 13). But it has to check that its N ame is correct. After each Scan a process will verify that the number of participants corresponds to the contents of P R registers (Line 9): if the number of participants is a then P R[a] must be the last cell different from ⊥. If it is the case, its N ame is up to date and it writes the next register (Line 13 and 14). If it not the case, the index of the last non ⊥ cell in P R is less than the number of participants that p has seen, then p writes in the correct cell of P R (P R[a] if a is the number of participants seen by p) (Line 11) and determine its new index N ame in its list (Line 10).

As before the write terminates when v is in at least n registers (condition in Line 16): when v is in n registers at least one of these registers is not covered. Roughly speaking, write is wait-free because eventually the last cell distinct of ⊥ will correspond to the actual number of participants, and the list of participants in this cell will be the actual list of all participants, hence processes will have a personal register in which it will be alone to write.

The same arguments proving the safety properties of the non-blocking algorithm of Figure 3 apply here (essentially the write of v terminates when v is in at least n registers by a non covering argument then v will be returned by all Scan). Then we restrict ourselves to prove the wait-freedom.

For each register r, r.proc is the list of all processes occurring in r.

Lemma 19 There is a time after which each register r of P R[0], ..., P R[n -1] is written by at most one process.

Proof. Let max be the greatest i such that P R[i] = ⊥. By definition of the index, max may not be the N ame of any register, then P R[max] may only be written by processes in Line 11 for which for the previous Scan P R [max] was ⊥. Hence this register is written only a finite number of time. Consider time τ after which only processes that make an infinite number of Scan/U pdate take steps and after which P R[max] is no more written. Claim There are a set P articipant of size max and a time σ > τ after which: (1) P R[max].proc = P articipant and (2) for every process p that makes an infinite number of Scan/U pdate, V iew p .proc = P articipant.

Proof.

Let P articipant be the value of P R[max].proc a time τ .

Let p be a process that makes an infinite number of Scan/U pdate, p will make some Scan after time τ getting P R[max]. Then there is a time τ p after which P R[max].proc ⊆ V iew p .proc. Then P R[max].proc = V iew p .proc is equivalent to max = card(V iew p .proc). If P articipant = P R[max].proc = V iew p .proc then max < card(V iew p .proc) and p will write in P R[card(V iew p .proc)] contradicting the definition of P R[max]. Let time σ be max of τ p for all p making an infinite number of Scan/U pdate, after time σ conditions (1) and (2) of the claim are satisfied.

Let i such that 0 ≤ i ≤ n and assume that P R[i] is written after time σ, then by definition of max, we can assume that 0 ≤ i < max. If, after time σ > τ , some q writes P R[i], by definition of τ , this process makes an infinite number of Scan/U pdate. By the claim, V iew q .proc = P articipant, and if q writes in P R[i] that means that the index of q in P articipant is i and as each process making an infinity of Scan/U pdate has an unique index in P articipant, q is the only writer of P R[i].

Lemma 20 The algorithm in Figure 4 emulates wait-free n SWMR registers with 2n MWMR registers for n processes.

Proof. We prove only the wait-freedom. Assume a process p that takes an infinite number of steps tries to write v = (x, p, k) in its register and does not succeed. Then (v, p, k) in inserted in V iew p and by Lemma 1, (v, p, k) remains forever in V iew p By the algorithm, p executes an infinite number of Scan/U pdate and writes V iew p an infinite number of times in at least one register of P R. By Lemma 19, there is a register P R[i] and a time τ after which p writes infinitely often in P R[i] and p is the only writer of P R[i]. Then v will be forever in P R[i]. After time τ , every process q that executes Scan/U pdate reads P R[i] and includes it in its V iew q . Then all processes that write after time τ in some register will write v in this register too. As we assume that the write of p does not terminate, at least p writes in each register of W . Therefore, there is a time after which v will be forever in all the n -1 registers W and in register P R[i], then for any Scan v will be in at least n registers and the write of v ends.

Notice that the information in P R[n] can be easily integrated to P R[n-1]. So we can use only 2n -1 MWMR registers. The shared MWMR registers array W is of size n -1 and array P R is of size n.

Finally, we replace Line 9 to Line 11 from algorithm in Figure 4 with Lines in Figure 5 :

Theorem 21 The algorithm in Figure 5 emulates wait-free n SWMR registers with 2n -1 MWMR-registers for n processes.

Concluding remarks

We have seen how n processes emulate SWMR non-blocking using n-registers and wait-free using 2n -1 MWMR registers. What if we have M processes M >> n (M possibly infinite) but we have the notion of arrivals and departures of processes? Processes have to solve the task only under the condition that the number of processes that invoked the task (arrived) minus the number of processes that obtain an output (departed) is at any point of time less or equal to n. Suppose that we know that a task T is read-write non-blocking (resp. wait-free) solvable in the SWMR model under the assumption of n-concurrency. Can we solve T with just n (resp. 2n -1) MWMR registers, without indefinite postponement, i.e. the step complexity of a process until it gets an output will be, like in the SWMR model, a function of n rather than M ? We observe that the non-blocking simulation is in fact n-concurrent. Thus, for the non-blocking case, the answer is positive. Concerning the wait-free simulation it is more tricky, but we conjecture that the answer is positive too. i

Figure 1 :

 1 Figure 1: Generic algorithm.

6 for i = 1 to m 7 V 9 foreverFigure 2 :

 6792 Figure 2: Broadcast with m MWMR registers

  Shared variable :array of m MWMR-register : R // To ensure non-blocking we assume m ≥ n Local variable: set of Values V iew = ∅ Code for process p init k=0;

Figure 3 :

 3 Figure 3: Non blocking implementation of regular SWMR registers for n processes.

12 else 13 if

 1213 next = n then update(P R[N ame], V iew) 14 else update(W [next], V iew) 15 next = (next + 1) mod (n + 1) 16 until (card{r|v in Snap[r]} ≥ n) 17 k = k + 1 read(q): 18 V iew = Collect()19 return x such that (x, q, u) ∈ V iew with maximal u

Figure 4 :

 4 Figure 4: Wait-free emulation with 2n MWMR registers for n processes.

9. 1 2 NifFigure 5 :

 125 Figure 5: Wait-free emulation with 2n -1 MWMR registers for n processes.

iii A Broadcast: Proof of Theorem 6

If a process takes an infinity number of steps then its Delivers terminate, and the Integrity property is trivial. We now prove the convergence.

Recall that we assume that there is at least one process that takes an infinite number of steps.

Lemma 22 At least one process makes an infinite number of N BScan and all registers are written infinitely often.

Henceforth R ∞ is here the set of all registers.

If all registers contain some set of values V , if the number of processes covering registers with values W such that V ⊆ W is less than m, the number of registers, then V will be forever contained in all registers.

Moreover there is a time after which for all processes p that take an infinite number of steps V ⊆ V iew p .

Proof. If card(Q) < m then by pigeon hole principle at least one register, say R[j], is Vcovered then by Lemma 2, V = V ∩ R[j] τ will be forever in this register. By Lemma 4, eventually V will be in all registers. Then if p takes an infinite number of steps it eventually makes a N BScan that returns a superset of V and by Lemma 1 there is a time after which V is forever in V iew p . Now consider some properties on sets written in registers. From Lemma 1 and the fact that V iew is a subset of the set of initial values and this set is finite we get:

Lemma 24 For all processes p, there is a set V of values such that there is a time after which forever V iew p = V .

A set of values E is said to be stable if E is written infinitely often in some register. By Lemma 22 and the fact that there is a finite set of values, there is at least one stable set.

Then, directly from the definition:

Lemma 25 E is stable if and only if there is a process p that takes an infinite number of steps and a time τ after which we have forever E = V iew p .

As a process writes always some values, a stable set is not the empty set.

Hence, let τ 0 the time after which only stable sets are written in registers.

Stable sets may be ordered by inclusion, for this order a stable set E is minimal if and only if for all stable sets E if E ⊆ E then E = E. As the set of stable sets being finite, minimal stable sets always exist.

Consider a minimal stable set M , and assume a time τ ≥ τ 0 . Let M be the set of processes that take an infinite number of steps that eventually write M in registers. By Lemma 25 at least one process p M that takes an infinite number of steps writes M forever in all registers. Before writing M in some register, p M makes a N BSscan of all registers returning snapshot V . By stability V = M and by minimality of M , for each i we have V [i] = M . Then there is a time σ ≥ τ such that for each i,

Assume by contradiction that there is some stable set X such that X ∩ M = ∅. Let X be the set of such sets, and P be the set of processes that take an infinite number of steps and eventually write in the registers any X ∈ X . From Lemma 23, if card(P) < m, M will be forever in all registers but then card(P) = 0 contradicting the hypothesis. Then we have card(P) ≥ m.

Consider any minimal stable set N in X , by a symmetric argument we prove that if Q is the set of processes that take an infinite number of steps and eventually write stable sets Y such that Y ∩ N = ∅ then card(Q) ≥ m.

As card(Q) ≥ m, card(P) ≥ m, P and Q are disjoint and n < 2m, we get a contradiction.

Hence if n < 2m all stable sets contain M , proving that all Deliver eventually return sets iv all containing M . Moreover, by Lemma 26, there is a value in M , proving the convergence property.


C Albea

S Lesecq

D Puschini

Optimal and Robust Saturated Control for a Clock Generator

Optimal and Robust Saturated Control for a Clock Generator

Carolina Albea-Sanchez, Suzanne Lesecq, Diego Puschini

I. Introduction

The continuous increase in clock frequency together with technology scaling has made the distribution of a single global clock over a digital chip tremendously difficult. Globally Asynchronous Locally Synchronous (GALS) design alleviates the problem of clock distribution by having multiple clocks, each one being distributed on a small area of the chip. An architecture with different clock frequency domains appears as a natural enabler for fine-grain power-aware architectures. Actually, power consumption is a limiting factor in Very Large Scale Integration (VLSI), especially for mobile applications. Voltage-Frequency Islands (VFI) [START_REF] Choudhary | Hardware based frequency/voltage control of voltage frequency island systems[END_REF] have proven to be highly effective to reduce the power consumption of the chip while meeting the performance requirements [START_REF] Horowitz | Low-power digital design[END_REF].

The key idea behind local DVFS is to control at fine grain the supply voltage and the frequency of an island at runtime to minimize its power consumption of the island considered while satisfying the computation/throughput constraints [START_REF] Choi | Fine-grained dynamic voltage and frequency scaling for precise energy and performance tradeoff based on the ratio of off-chip access to on-chip computation times[END_REF].

DVFS techniques mainly rely on two 'actuators'. These actuators need to be dynamically controlled in order to reduce the power consumption while maintaining the required performance. More precisely, the control policy {suzanne.lesecq, diego.puschini}@cea.fr must be carefully designed in order to achieve high power efficiency at low area cost. The voltage actuator fixes the supply voltage of the VFI. It can be a classical buck converter [START_REF] Liu | A dynamic buck converter with ultra fast response and low voltage ripples designed for DVS systems[END_REF] or a discrete Vdd-hopping converter [START_REF] Albea | Control and stability analysis for the Vdd-hopping mechanism[END_REF], [START_REF] Miermont | A power supply selector for energy-and area-efficient local dynamic voltage scaling[END_REF]. The frequency actuator is supposed to be a Clock Generator.

An important issue of technology scaling is the in-die and die-to-die process variability (P-variability). As a consequence, each VFI performance and optimal functional frequency will strongly differ from place to place within the chip. These changes are also induced by Voltage and Temperature variations (VT-variability) over time. Therefore, the optimum functional and energetic point of the whole circuit can be found if VFI number i has its functioning frequency in the range [F min,i , F max,i ] [START_REF] Tretz | An all digital frequencylocked loop immune to hysteresis effects for power management of multicore processors[END_REF]. If the clock is generated for the whole circuit, and distributed in each VFI, the maximum acceptable frequency (i.e. that will ensure no timing fault for any VFI) will be F max,i = min{F max,i , ∀i}, leading to a suboptimal circuit functioning. Therefore, the clock is locally generated and controlled by a Clock Generator according to Process, Voltage and Temperature (PVT) variations.

The main objective of this paper is to design a control law for the Clock Generator (see Fig. 1) taking into account the next objectives:

• robustness with respect to PVT variations; • low cost implementation;

• saturation; • delay consideration and • exogenous disturbance rejection. Therefore, the designed controller must not only guarantee the set-point stabilization, but also other criterions.

An optimal and robust saturated control law for the Clock Generator is proposed in discrete time. The system is rewritten into a suitable state-space representation to formulate a robust H ∞ control problem that can be solved using Lyapunov-Krasovskii theory [START_REF] Fridman | Delay-dependent H inf control of uncertain discrete delay systems[END_REF]. In this process, the saturation in the actuator input is considered [START_REF] Cao | Stability analysis of linear timedelay systems subject to input saturation[END_REF]. The designed controller guarantees asymptotic stability, disturbance rejection as well as robustness of the system with respect to delays and uncertain parameters. The problem is expressed in terms of Linear Matrix Inequalities (LMIs). Likewise, an attraction domain is estimated in such a way that a regional stabilization for the saturated control is guaranteed. The robustness properties of the closed-loop system are confirmed by simulations.

The rest of this paper is organized as follows: in Section II, the error equation of the circuit model is derived as well as its properties. The robustness problem statements are presented in Section III. Likewise, in Section IV, the stabilization of the time-delay system is performed. This result is extended for a robust control design in Section V. An optimization procedure is proposed in Section VI. The control gains are computed in Section VII, being confirmed by simulations in Section VIII. The paper closes with a section of conclusion.

Notation. For a given x ∈ R,

sat M m (x) M if x > M x if m ≤ x ≤ M m if x < m.
} with x k 2 2 ∞ k=0 x T k x k < ∞.

II. Error equation of the Clock Generator

The main blocks of the Clock Generator considered in this paper are a digital to analog converter (DAC), a Voltage Controlled Oscillator (VCO) that provides at its output a frequency f (t), a sensor to measure this frequency and a controller that contains a frequency comparator between the targeted frequency, f r , and the output frequency and some 'intelligent controller'. Note that this structure is similar to the one of a Digital Frequency-Locked Loop. Figure 1 shows a sketch of the Clock Generator.

Controller VCO Sensor e k-h u k-h f (t) f r f k-h K s f k K V CO , b, K 1 , K 2 + - z -h K s DAC DCO B w + + d(t) K DCO R, C Fig. 1: Clock Generator block diagram.
The main blocks of this Clock Generator are modeled through design considerations and accurate simulations. The VCO can be modeled as a RC circuit [START_REF] Bui | Design of a high-speed differential frequency-to-voltage converter and its application in a 5-GHz frequency-locked loop[END_REF]. Indeed, it can be approximately modeled as

ḟ (t) = - f (t) RC +KV CO u(t-τ )+b+Bwd(t), τ = h(t k+1 -t k )
where f ∈ R 1 is the analog frequency output, u is a control signal, d is a L 2 disturbance and K V CO and B w are constant. R and C represent the resistive and capacitive components, respectively, of the circuit, and b is an offset.

This model is approximately discretized, in such a way that the whole Digitally-Controlled Oscillator (DCO) is modeled by :

f k+1 = (1 -ρTs)f k + KDCOTsu k-h + bTs + BwTsd k
where T s is the sampling period, K DCO is the gain of the whole DCO and ρ 1 RC . Defining e k f rf k , where f r is the reference signal, the error equation is

e k+1 = (1-ρT s )e k -K DCO T s u k-h +ρT s f r -bT s -B w T s d k .
(1) A controller proposed for this system is given by

u k-h = sat ūM ūm {u k-h-1 + Kx k-h } , ( 2
)
where h is the size of the constant delay introduced by the sensor,

x k-h [e k-h e k-h-1 ] T and K [K 1 K 2 ].
Note that the controller proposed presents a simple enough structure to be implemented in hardware. This property is very important in SoCs [START_REF] Micheli | Nanosystems[END_REF].

III. Problem statement

The problem statement is formulated. The closed-loop system (1) is rewritten in a state-space form taking into account the delay, saturation, uncertain parameters and any exogenous disturbance.

Parameters R, C, T s and K DCO can be considered uncertain. Their corresponding uncertainty intervals are

• R ∈ [R m , R M ], • C ∈ [C m , C M ], • T s ∈ [T m s , T M s ], • K DCO ∈ [K m DCO , K M DCO ]
. Consequently, the main objective is to find the optimal gain K, in such a way that, Control (2) is robust with respect to delays as well as parameter uncertainties. Likewise, this optimal K must guarantee asymptotic stability and disturbance rejection for the known constant delay h.

A. Alternative representation for the saturated control (2) and the error equation [START_REF] Choudhary | Hardware based frequency/voltage control of voltage frequency island systems[END_REF] Firstly, some lemmas are given to rewrite the saturated control (2) in an alternative form.

Define χ u k-1-h1 x k-h . Note, from Eq.(1), u k-1-h1 directly depends on x k = [e k , e k-1 ]. Lemma 1: [12], let K, G ∈ R 1×2 be given. For all, χ k-h ∈ R 1×3 , if χ k-h ∈ {χ k-h ∈ R 1×3 : [1 G]χ k-h ∈ [1 N ]}, then sat N 1 {[1 G]χ k-h } ∈ Co {[1 K]χ k-h , [1 G]χ k-h } .
Lemma 2: Assume that there exists G ∈ R 1×2 , c > 0 and Ψ diag{ρ, P 1 }, where

P 1 † > 0 ∈ R 2 , ρ > 0 ∈ R 1 such that for any χ k-h ∈ X, where X = χ k-h : χ T k-h Ψχ k-h ≤ c -1 , (3)
† P 1 is a positive matrix defined to guarantee system stability.

then, 1 < u k-1-h1 +Gx k-h < N , and Control (2) admits the following representation

u k-h1 = [α k (u k-1-h1 + Kx k-h ) +(1 -α k )(u k-1-h1 + Gx k-h )] = [u k-1-h1 + α k Kx k-h + (1 -α k )Gx k-h )] = [u k-1-h1 + ūk-h ] ,
where ūk-h (

α k K + (1 -α k )G)x k-h with α k ∈ [0, 1],
for all k > 0. Then, Eq. ( 1) can be rewritten as

e k+1 = (1 -ρT s )e k -bT s + ρT s f r -B w T s d k -K DCO T s (u k-1-h1 + ūk-h ) (4)

B. State-space representation

The saturated control law and error equation, as redefined above, allow system (1) rewrite it in a state-space form. From Eq. ( 1),

u k-h = -e k+1 + (1 -ρT s )e k + ρT s f r -bT s -B w T s d k K DCO T s ,
and, therefore

u k-h-1 = -e k + (1 -ρTs)e k-1 + ρTsfr -bTs -BwTsd k-1 KDCOTs
which substituted in ( 4) gives

e k+1 = (2 -ρT s )e k + (ρT s -1)e k-1 -K DCO T s ūk-h + T s B w (d k -d k-1 ) (5)
From Lemma 1 and 2, Eq. ( 5) can be rewritten in the following matrix form:

x k+1 = Ax k + B ūk-h + Bw w k (6)
where

w k [d k d k-1 ] T , A 2 -ρT s ρT s -1 1 0 , B -K DCO T s 0 , Bw T s b w -T s b w 0 0 .

C. Stability and disturbance rejection problem

Equation ( 6) can be rewritten in the following explicit closed-loop form, in such a way that a H ∞ problem can be formulated.

x k+1 = Ax k + B(α k K + (1 -α k )G)x k-h + Bw w k , (7) x l = φ l , ∀l ∈ [-h, 0] (8)
z k = I 2 x k , (9)
where x k , z k , w k ∈ R 2 are the state vector, controlled output and exogenous disturbance input, respectively. φ l is the initial condition and h ≥ 0 ∈ R is a fixed and known delay.

Problem 1: The problem is to find X(P 1 , c), vector G and K, such that a) Lemma 2 holds and, hence, the closed-loop system (7), and b) there exists a Lyapunov-Krasovskii functional V k > 0 such that V k+1 -V k along the solution of ( 7) fulfills

V k+1 -V k < 0, (10)
when the system is not perturbed, and for any disturbance input, there exists a minimum disturbance attenuation, γ * ≥ 0, such that, for all γ ≥ γ * the L 2 gain between the disturbance vector w k and the output vector z k is less or equal to γ. i.e.

z k 2 2 -γ 2 w k 2 2 < 0, ∀w k ∈ L 2 for φ l = 0, -h ≤ l ≤ 0. ( 11
)
The solution to this problem guarantees the asymptotic convergence, system stability as well as the disturbance rejection for the time-delay system ( 7)- [START_REF] Cao | Stability analysis of linear timedelay systems subject to input saturation[END_REF].

IV. H ∞ control design

In order to cope with Problem 1 a mathematical manipulation of Eq. ( 7) is performed via a descriptor model transformation [START_REF] Fridman | A Descriptor System Approach to H∞ Control of Linear Time-Delay Systems[END_REF]. The descriptor approach is a variable change, which makes easier to work with Lyapunov-Krasovskii functional [START_REF] Fridman | Delay-dependent H inf control of uncertain discrete delay systems[END_REF].

A. Descriptor model transformation

Equation ( 7) is manipulated in order to achieve the previous objectives. A descriptor model transformation is applied.

Considering

y k x k+1 -x k , ψ k k-1
i=k-h y i , Eq. ( 7) is rewritten in the descriptor form [START_REF] Fridman | A Descriptor System Approach to H∞ Control of Linear Time-Delay Systems[END_REF]:

x k+1 0 = y k + x k -y k + Ax k -x k + B(α k K + (1 -α k )G)x k-h + Bwwk.
From x k-h = x kψ k , this system can be compactly written as:

E xk+1 = Āx k - 0 B(α k K + (1 -α k )G) ψ k + 0 Bw w k , (12) where
Ā I 2 I 2 A + B(α k K + (1 -α k )G) -I 2 -I 2 E diag{I 2 , 0 2 }, xk
x k y k .

B. Condition for state-space representation

Condition a) of Problem 1 is satisfied, if

1 < u k-1-h1 + Gx k-h < N, ∀χ k-h ∈ X (13)
given in (3) is guaranteed. Subtracting N +1 2 in inequality [START_REF] Fridman | A Descriptor System Approach to H∞ Control of Linear Time-Delay Systems[END_REF] and from [START_REF] Fridman | Regional stabilization and H∞ control of time-delay systems with saturating actuators[END_REF], it is seen that, it is necessary satisfy

2N -2 > N (1 + cx T k-h P 1 x k-h + cu T k-1-h ρu k-1-h ) -2 > 4u k-1-h + 4Gx k-h -2(N + 1) (14)
From Lemma 2, relationships ( 14) correspond to

  1 u k-1-h 1 x T k-h   T   3N -2 -2G -2 cN ρ 0 -2G T 0 cN P1     1 u k-1-h 1 x k-h   > 0 ( 15
)
This inequality is satisfied if

  c -2 -2Y -2 ρ3N 2 0 -2Y T 0 3N 2 P1   > 0 (16)
Note that this LMI is equivalent to ( 15) by means of employing the Schur's complement, defining Y GQ 1 with Q 1 ∈ R 2 which is Hermitian, applying P1 = Q 1 P 1 Q 1 and pre-and post-multiplying by diag{1, 1, Q 1 }.

C. Control design

Now, condition b) of Problem 1 can be formulated in terms of Linear Matrix Inequalities (LMIs) [START_REF] Fridman | Delay-dependent H inf control of uncertain discrete delay systems[END_REF]. Fulfillment of conditions ( 10) and ( 11) is looked for.

Assumption 1: There exists a Lyapunov function V k , with condition (10) and a γ, such that,

V k+1 -V k + z T k+1 z k+1 -γ 2 (w T k w k ) ≤ ζ T Γζ < 0. (17) where ζ [x k ψ k w k ]
T is an augmented state vector and Γ ∈ R 4×4 is a symmetric matrix.

Define P P 1 P 2 P 2 0 , being P 2 Hermitian.

The function Γ is obtained defining the next Lyapunov-Krasovskii candidate

V k = V 1,k + V 2,k + V 3,k , ( 18
) being V 1,k = xT k EP E xk (19) V 2,k = h n=1 k-1 i=k-n y T i Ry i , R > 0 (20) V 3,k = k-1 i=k-h x T i Sx i , S > 0, ( 21
)
where V 1,k guarantees asymptotic stability of system (12) without delays. Delay-dependent as well as delayindependent criteria are considered in V 2,k and V 3,k , respectively [START_REF] Fridman | Delay-dependent H inf control of uncertain discrete delay systems[END_REF], [START_REF] Gu | Stability Analysis of Time-Delay Systems: A Lyapunov Approach[END_REF]. Next, a sufficient condition for asymptotic stability and disturbance rejection is derived.

Theorem 1: Consider system ( 7)-( 9) with energybounded w k and control law ūk

-h = α k Kx k-h + (1 - α k )Gx k-h where h > 0 ∈ R is a known constant delay and K, G ∈ R 1×2 . If there exist S, R ∈ R 2×2 such that P 1 > 0, ( 22
) Γ k < 0 (23)
LMIs [START_REF] Gu | Stability of time-delay systems[END_REF] where Γ k is defined in (24) found at the top of next page, then the equilibrium of the closed-loop system ( 7)-( 9) is asymptotically stable and there is a value γ * such that for γ < γ * condition ( 11) is fulfilled.

Proof: The goal is to satisfy

V k+1 -V k + z T k z k - γ 2 w k
T w k < 0 for both disturbance rejection and asymptotic stability of the equilibrium for system [START_REF] Hu | Control systems with actuator saturation: analysis and design[END_REF].

Lyapunov-Krasovskii method yields:

V 1,k+1 -V 1,k = xT k+1 EP E xk+1 -xT k EP E xk = xT k ĀT -ψ T k [0 α k K T B T + (1 -α k )G T B T ]+ + w k [0 BT w ] P Āx k - 0 α k BK + (1 -α k )BG ψ k + 0 Bw w k -xT k EP E xk = xT k [ ĀT P Ā -EP E]x k -xT k ĀT P 0 α k BK + (1 -α k )BG ψ k -ψ T k [0 α k K T B T + (1 -α k )G T B T ]P Āx k -xT k ĀT P 0 Bw w k + w k [0 BT w ]P Āx k .
From (20) and Jensen Inequality [START_REF] Gu | Stability of time-delay systems[END_REF]:

V 2,k+1 -V 2,k = hy T k Ry k - h n=1 y T k-n Ry k-n ≤ xT k 0 0 0 hR xk - 1 h ψ T k Rψ k Finally, V 3,k+1 -V 3,k = x T k Sx k -x T k-h Sx k-h = x T k Sψ k + ψ T k Sx k -ψ T k Sψ k
These developed expressions are applied to inequality [START_REF] Millan | An optimal control L 2 -gain disturbance rejection design for networked control systems[END_REF], in such a way that the LMIs (23) are obtained.

V. Robust control

The uncertain parameters given in Section III are now taken into account, at the same time that stability as well as disturbance rejection for the time-delay Vddhopping system are ensured. For this reason, Theorem 1 is extended in the case of polytopic uncertainties.

Denote Ω [A B α k ] and assume that Ω ∈ Co{Ω j , j = 1, ..., 16}, namely

Ω = n j=1 λ j Ω j , 0 ≤ λ j ≤ 1, n j=1 λ j = 1
and being the vertices of the polytope described by Ω j = [A (j) B (j) α (j) k ] for j = 1, ..., 16. Pre-and post-multiplying LMI (23

) by Q = diag{Q 1 , Q 1 , Q 1 , I 2 } and taking Q 1 = P -1 2 > 0 and P1 = Q 1 P 1 Q 1 , R = Q 1 RQ 1 , S = Q 1 SQ 1 , the following sufficient condition is achieved.
Theorem 2: Consider system ( 7)-( 9) with energybounded w k and control law ūk

-h = α k Kx k-h + (1 - α k )Gx k-h for α k ∈ [0, 1], where h ≥ 0 ∈ R is a known constant delay and K, G ∈ R 1×n . If there exist T, Y ∈ Γ k     ĀT P Ā -EP E + diag{I 2 , hR} -ĀT P 0 Bα k K + (1 -α k )G + S 0 ĀT P 0 Bw * -1 h R -S 0 * * -γ 2 I 2     (24) R n×1 and Q 1 ∈ R n×n with K = T Q -1 1 , G = Y Q -1
1 and R, S > 0 ∈ R n×n for j = 1, ..., 16 such that

P1 > 0 (25) Γ(j) < 0 j = 1, ...., 16, (26)
LMIs [START_REF] Gu | Stability of time-delay systems[END_REF] being Γ(j) defined in (27) found at the top of next page, are satisfied. Then, in the vertices i and j, the equilibrium is asymptotically stable as well as the disturbances are rejected in the entire polytope.

Proof: This is an extension of Theorem 1 for polytopic uncertainties with some mathematical manipulations. Therefore, this theorem proof follows Theorem 1 proof.

Remark 1: This robust control tuning method is conservative due to the definition of matrix P , as well as, the attraction domain, X.

Corollary 1: Gain K, obtained from T and Q 1 in Theorem 2, fulfills Theorem 1 and consequently guarantees both robust stability and robust disturbance rejection for a fixed delay.

VI. Optimal and Robust control

In order to obtain a maximum attraction domain, i.e. minimum c, and for the disturbances to be effectively rejected (i.e. minimum γ), an optimal control problem is formulated.

Assumption 2: There exists a functional cost

J x k+1 P 1 x k+1 + z k+1 2 2 -γ 2 w k 2 2
The first term on the right side quantifies the size of the attraction domain and the other terms the disturbance attenuation.

Lemma 3: Suppose that Assumptions 1 and 2 are fulfilled, Then the optimal controller gain K for Problem 1 can be found by: Minimize -J subject to:

Γ(j) < 0 P1 > 0.
LMIs (j) (16) j = 1, ..., 16. Proof: The optimal Problem 1 is solved by Lemma 1 if condition [START_REF] Micheli | Nanosystems[END_REF] is fulfilled [START_REF] Millan | An optimal control L 2 -gain disturbance rejection design for networked control systems[END_REF].

For w k = 0 and under zero initial conditions

V k+1 -V k ≤ -z T k+1 z k+1 + γ 2 w T k w k .
The summation of both side is

V k+1 -V 0 ≤ - k+1 k=0 z T k+1 z k+1 + γ 2 k k=0 w T k w k .
For k → ∞, under the zero initial condition V 0 = 0 and the positive definitiveness of the Lyapunov function, it is proved that

∞ k=0 z T k+1 z k+1 ≤ γ 2 ∞ k=0 w T k w k ⇒ z k+1 2 2 ≤ γ 2 w k 2 2 .
Corollary 2: The optimal gain K, obtained applying Lemma 3 guarantees both robust stability and robust disturbance rejection and provides a maximum attraction domain.

VII. Optimal and robust control result

In this section, the robust control gains for Control (2) are computed. For the control signal ūm = 0.6V and ūM = 1.1V , b = -26M Hz and h = 1. b w = 10 was taken, for any exogenous disturbance. The uncertain parameters take the following ranges:

• C ∈ [2, 4]nF , • R ∈ [5, 10]Ω, • K DCO ∈ [10, 1000]M Hz/LSB, • T s ∈ [20, 30]ns. From Lemma 3, it comes that K 1 = 0.8 K 2 = -0.8.
Likewise γ = 0.025, c = 0.9, G = 0.0747 -0.0732

and P 1 = 0.0062 -0.0062 -0.0062 0.0062 .

Note that even if the control constant tuning is conservative, there is a feasible solution.

VIII. Simulation Results.

In this section, some simulations show the robustness of the optimal and robust saturated control law proposed for the Clock Generator. For these simulations, the data given above are taken.

Figure 2 shows some simulation results when the system parameters are changed: 'syst 1', 'syst 3' and 'syst 4' are superposed. Note that the four systems converge to the set-point, showing the system robustness. Finally, note in Fig. 3 that the control law rejects an added exogenous disturbance, as expected. Γ(j)

     Γ(j) 1 Γ(j) 2 -α (j) k B (j) T -(1 -α (j) k )B (j) Y + S Bw Q 1 * P1 -2Q 1 + h R -α (j) k B (j) T -(1 -α (j) k )B (j) Y Bw Q 1 * * -R h -S 0 * * * -γ 2 Q 1      , j = 1, ..., 16. (27)
where Γ(j)

1 Q 1 A (j) T + A (j) Q 1 -2Q 1 + α (j) k T T B (j) T + (1 -α (j)
k )Y T B (j) T + αB

IX. Conclusions

In this paper an optimal and robust saturated controller was designed for a time-delay Clock Generator. The system is rewritten in a suited state-space representation, such that an optimal and robust H ∞ problem can be formulated to tune the control gains. This problem is dealt with Lyapunov-Krasovskii theory, which provides some stability conditions through Linear Matrix Inequalities (LMIs). Consequently, robust equilibrium stability as well as robust disturbance rejection under parameter uncertainties are ensured for the time-delay system. The method also takes into account the control saturation estimating a maximum attraction domain. The closed-loop system robustness is exemplified by means of simulations.

syst 1 :

 1 K DCO = 0.04 GHz LSB , R = 5Ω, C = 2 • 10 -9 F , Ts = 20ns, syst 2: K DCO = 0.14 GHz LSB , R = 5Ω, C = 2 • 10 -9 F , Ts = 20ns, syst 3: K DCO = 0.04 GHz LSB , R = 10Ω, C = 410 -9 F , Ts = 20ns, syst 4: K DCO = 0.04 GHz LSB , R = 5Ω, C = 2 • 10 -9 F , Ts = 30ns.

2 Γ(j) 2 P1 + Q 1 AFig. 2 :

 2212 Fig. 2: Evolution of the output frequency for four different systems.

Fig. 3 :

 3 Fig. 3: Exogenous disturbance added to 'syst 1'.

  and round(x) is the nearest integer to x. For a given set S, Co(S) denotes the convex hull of set S. ∆ζ ζ + -ζ -, where ζ + and ζ -are respectively ζ(k + 1) and ζ(k), i.e., the value of ζ in two consecutive sampling times. Finally, L 2 is the space of {x k


Younès Chandarli

Yasmina Abdeddaïm

Damien Masson

The Fixed Priority Scheduling Problem for Energy Harvesting Real-Time Systems

Energy harvesting is the process of generating electrical energy from environmental sources such as solar panels. In recent years, this term has been frequently applied in the context of small autonomous devices such as wireless sensor nodes. The classical scheduling theory is insufficient for this kind of systems and new scheduling problems arise in this context. Until now, the research on this area focused in trying to improve the efficiency of existing algorithms. Our approach is to complete these efforts by a feasibility theory allowing us to understand why classical optimal algorithms are not efficient anymore with energy constraints.

In this paper, we try to establish a schedulability test for a fixed priority real-time scheduling problem with energy constraints. We first introduce the problem and describe the model. Then, to illustrate the difficulty of the problem, we focus on a preemptive fixed priority scheduling policy where all the executions are postponed as long as possible. This policy lets the harvester the maximal amount of time to refill the battery. We call this policy P F PALAP for As Late As Possible. We try to define sufficient and/or necessary schedulability conditions and discuss its potential optimality under some additional assumptions. Then, through simple counter examples, we show that intuitive assumptions are wrong for this scheduling problem, making it very interesting to study.

I. INTRODUCTION AND RELATED WORK

The first work addressing the scheduling problem for energy harvesting systems was the one of Mossé [START_REF] Allavena | Scheduling for frame-based embedded systems with rechargeable batteries[END_REF]. The problem was solved under a very restrictive task model: the frame based model where all the tasks have exactly the same period and implicit deadline. Then Moser et al. studied a very similar problem [START_REF] Moser | Lazy scheduling for energy harvesting sensor nodes[END_REF]. They proposed an optimal algorithm called LSA but in their hypotheses, the CPU frequency can be changed to adjust the Worst Case Execution Time (WCET) of the tasks depending on their energy consumption. Then the results of this work rely on a strong hypothesis: tasks energy consumption is directly linked to their WCET. Recent work shows that this hypothesis is not realistic [START_REF] Jayaseelan | Estimating the worst-case energy consumption of embedded software[END_REF]. Finally, the problem was addressed by Chetto et al. in [START_REF] Chetto | A real-time scheduling framework for embedded systems with environmental energy harvesting[END_REF], [START_REF] Chetto | Fixed priority scheduling strategies for ambient energy-harvesting embedded systems[END_REF]. A clairvoyant algorithm and several non clairvoyant heuristics was proposed. This clairvoyant algorithm relies on a meta policy: as long as the system can perform without energy failure, a standard policy such as EDF is used. Then, as soon as a future energy issue is detected, i.e E < 0, the system is paused as long as possible or until the energy storage unit is full. The notion of slack time [START_REF] Lehoczky | An optimal algorithm for scheduling soft-aperiodic tasks fixed priority preemptive systems[END_REF] is extended to the notion of slack energy. An algorithm to compute slack energy under EDF is provided. However, as most embedded systems only use fixed priority, we are interested in extending and completing existing works for fixed priority scheduling.

The remaining of the paper is organized as follow, we present the model in Section II, then we describe the P F P ALAP algorithm and we discuss about its worst case scenario, its study period and we try to build a schedulability condition based on P F P ALAP in Section III. Section IV presents the problem of finding the minimal battery size that permits to schedule a system. Finally we conclude in Section V.

II. MODEL

A. Target application description

We consider an embedded system connected to an energy harvesting device. An energy harvesting device is a system that collects energy from its environment. The energy is stored in an energy storage unit. We suppose that we can know or bound the energy quantity that arrives in the storage unit, and for each task the energy that it consumes in the worst case. Figure 1 illustrates this description.

B. Formal description

We consider a real-time system in a renewable energy environment defined by a set of n periodic and independent tasks. Each task τ i is characterized by its priority P i , its worst case execution time C i , its period T i , its deadline D i and its worst case energy consumption E i . The execution time C i and the energy consumption E i of a task are fully independent. A task τ i releases an infinite number of jobs separated by T i time unit and each job must execute during C i and consume E i energy unit. Deadlines are constrained or implicit. The system is powered by a battery or a capacitor recharged from a renewable energy source like a solar panel. The energy is replenished continuously even during the execution of tasks and the energy level of the battery fluctuate between two thresholds E max and E min . We note P r(t) the charging function and for the sake of simplicity we consider that P r (t) is a linear function. We define the processor utilization of τ i as U i = C i /T i and its energy utilization as

U ei = C i t+Ti t P r(t) dt
The total utilization of the system is the sum of all the tasks utilization; i.e U = n

1 U i and U e = n 1 U ei . III. PFP ALAP SCHEDULING ALGORITHM
PFP ALAP is a fixed-priority scheduling policy that delays the jobs executions as long as possible, i.e, as long as the slack time remains positive. We are interested in studying this policy since this algorithm is simple and seems optimal when E max is not bounded. It lets the maximal time interval for the battery replenishment before the execution of a task. If this algorithm is proved to be optimal it can be used to build a feasibility test. Unfortunately, we will show a counter example that invalidates this claim. To do that, we must first find the worst case scenario that the task set can suffer, then we have to calculate the length of the study period necessary to decide the task set feasibility. In the following sections, we present without proof an intuitive worst case scenario, a study period and a feasibility condition based on P F P ALAP .

A. PFP ALAP worst case scenario

For the classical work conserving fixed priority algorithm, which we denote P F P ASAP by opposition to P F P ALAP , the worst case activation scenario corresponds to the synchronous activation of all tasks [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF]. In this situation the processor gets a maximum of workload that takes a maximum time to execute. So, the resulting busy period is the longest possible one. The lowest priority tasks suffer their longest delay in this situation, this is why it is said the worst case scenario. In the same scenario, PFP ALAP undergoes the same workload and behaves the same way as PFP ASAP but further delays jobs as long as slack-time is available. So without energy constraints, the worst case scenario of this algorithm is the same as PFP ASAP . By combining E 0 = E min with this scenario we get a scenario which can be the worst one for PFP ALAP . Indeed, at this moment the CPU load and energy demand are maximized and the battery level is minimized. A different situation is necessarily not as worse because in the case of an asynchronous activation, we should have more slack-time to recharge and less CPU workload and if more energy than E min is available, the system is less energy constrained. These arguments are persuasive but not conclusive and we do not have any formal proof until now.

B. PFP ALAP Study period

Without energy constraints, the study period of a task set with constrained or implicit deadlines is the processor busy period in the worst case scenario. For PFP ASAP scheduling, this period is the response time of the first job of the lowest priority task [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF]. Following the same logic, the study period of PFP ALAP algorithm is defined as the period when there is pending work. It starts from the critical instant (synchronous activation) and ends when all CPU demand is processed, that is later than the effective deadline of the lowest priority task. The first instance may be sufficient to study the schedulability of a system because firstly, all tasks have constrained or implicit deadlines, i.e there is no interference between two successive tasks. Secondly, the next activation period is at least equal or better than a synchronous activation and energy level is E ≥ E min . This seems reasonable but it is wrong as illustrated in Figure 2. In this counter-example we can see that despite the system described in Table I successes during the lower priority task's response time (time 32), it fails one instance later when the energy level is insufficient to satisfy the energy demand at time 70. To be sure that we will encounter all possible scenarios we must study a longer period bounded by the hyper period. This gives us the possibility to study all possible scenarios. So, the problem of finding a shorter study period is still open.

C. Optimality ?

The aim of our work is to build an energy-aware schedulability test for PFP ALAP that can decide if a given task set is timely and energetically feasible or not, i.e to check if all tasks respect their deadlines while the battery level remains between E max and E min . We begin with setting an assumption for simplicity: we consider initially the battery to be infinite and not bounded, i.e E max = ∞, then we relax this hypothesis by fixing a bound for the smallest battery capacity necessary to keep the system feasible.

A schedulability test is the study of tasks execution according to a scheduling policy during a study period that starts at the critical instant in the worst case energy scenario. In this period we have to test if there is no deadline miss nor energy constraints violation. In our case, the algorithm is PFP ALAP , the study period is the hyper period and the worst case scenario is the simultaneous activation at the lowest possible battery level i.e the initial energy level E 0 = E min as previously mentioned. Now it remains to check if all jobs meet their deadlines during the study period, and if the energy recharged during an idle-period is sufficient to meet the energy demand of the busy-period that follows. If the execution satisfies these conditions along the study period, the system is feasible because the periods that follow are at least better or equal to the starting one and the system can execute continuously without constraints violation. To make such verification, we must first calculate the start dates and the length of idle and busy periods and the energy demand of each one.

When the battery reaches its maximum level E max before the end of an idle period, we cannot continue to charge and Figure 2. Lowest priority task response time is not the real study period for P F P ALAP we lose the energy that could be recharged between that moment and the next execution begin. This leads to wast energy if nothing is done to avoid that. In our case this cannot happen because we suppose that E max is infinite. Since P F P ALAP postpones jobs executions to charge battery as much as possible before executing, our intuition is to say that such scheduling policy is optimal. We know that all schedulable task sets with P F P ASAP are schedulable with P F P ALAP so no timing problems can occur and we know also that in P F P ALAP idle-periods are as longer as possible which seems better for energy level. These simple intuitions may appear convincing but when we tried to build a formal proof we found a counter-example which invalidates the optimality of P F P ALAP . Figures 3 and2 illustrate a counter example where the task set described in Table I is not schedulable with P F P ALAP while it exists a feasible schedule. Indeed, we simulated this system with YARTISS [START_REF] Chandarli | Yartiss: A tool to visualize, test, compare and evaluate real-time scheduling algorithms[END_REF]; and this simulation shows that it is feasible until the hyper period. We can see that P F P ALAP postpones executions as late as possible which leads in this example to a very long busy period which has a big energy demand and the energy charged during the previous idle period is not sufficient, thus the system failed energetically. When we schedule the same task set with P F P ASAP by introducing charging periods as much as necessary when the battery is empty, jobs are scheduled as soon as possible then we avoid some very long busy periods and all jobs meet their deadline and idle periods are always sufficient.

-

C i E i T i D i P i τ 1 4 216

IV. BATTERY CAPACITY

The design of a system with E max = ∞ assumption is not realistic and schedulability test based on such assumption is not very useful, so finding the lowest E max value is necessary. The exact capacity of the battery is difficult to compute because it depends on tasks characteristics and we cannot predict the lowest necessary capacity to satisfy energy demand continuously before executing tasks. So to prevent this, we can solve the problem partially by bounding E max value.

First, knowing that tasks have implicit or constrained deadlines we can limit the study period to the hyper period. Second, the CPU utilization U gives us the proportion of time where CPU is busy, the remaining time the processor is idle and the system is only charging energy. So the highest level of energy that can be reached during a cycle starting from the worst case This is because we suppose for all tasks that it consumes more energy than we can charge during its execution time, i.e E i > Ci 0 P r(t) dt. This bound is very pessimistic but gives us a sufficient condition. If a task set is schedulable with P F P ALAP with E max = ∞ and the given E max is greater than or equal to Bound max , then it is feasible. By combining the previous test with a battery capacity bound, we have a sufficient condition for the feasibility of a task set.

V. CONCLUSION AND FUTURE WORKS

In this paper we presented some intuitive ideas to solve the problem of the energy harvesting scheduling. Then we showed that simple solutions are not always the best choices despite their obviousness. We invalidated the optimality of P F P ALAP and showed that the classical study period is no more valid. We also presented a sufficient schedulability test based on P F P ALAP algorithm and proposed a bound for the lowest necessary battery capacity. It is not an optimal algorithm, so a such schedulability test may be very pessimistic. For this reason we will continue our research on this way by exploring other scheduling policies and heuristics and try to provide more optimistic feasibility conditions. We will study carefully P F P ASAP and other clairvoyant algorithms and try to establish more optimistic or optimal feasibility conditions.

Figure 3 .

 3 Figure 3. P F P ALAP is not optimal