Meriem Halimi

Gilles Millérioux

An LPV framework for chaos synchronization in communication

An LPV framework for chaos synchronization in communication

Introduction

Most of chaos-based cryptosystems proposed since the 90's require synchronization of complex sequences. Indeed, following the principle of symmetric ciphers [START_REF] Knuth | The Art of Computer Programming[END_REF], they consist in scrambling an information with a chaotic digital sequence. The most popular techniques proposed so far are additive masking, parameter modulation, chaotic switching, two-channel transmission, message-embedding. An overview of the different methods can be found in the survey papers [START_REF] Ogorzalek | [END_REF][3][START_REF] Yang | Int. J. of Computational Cognition[END_REF][START_REF] Millérioux | [END_REF] or in the book [START_REF] Banerjee | Chaos Synchronization and Cryptography for Secure Communications: Applications for Encryption[END_REF]. In the year 1997, it has been shown that chaos synchronization can be formulated as a state reconstruction problem (see the pioneering works [START_REF] Nijmeijer | [END_REF][8] [9] [10]). Since then, many classes of observers have been proposed to tackle the synchronization problem. The point lies in that the structure and the design of the observers depend on the nonlinearities involved in the chaotic model. A case-by-case study must be carried out. The aim of this paper is to show that a unified and efficient framework can be proposed to achieve chaos synchronization for a large class of discrete-time chaotic systems. In particular, the classes of chaotic systems involving polynomial nonlinearities (Duffing map, Henon map, Burger map,. . . ) and piecewise linear maps (Lozi map, Zigzag map, Tent map, Baker map, Cat map, . . . ) can be addressed within a same framework, called LPV framework. Linear Parameter Varying (LPV) systems are linear models whose state representation depends on a parameter vector which can vary in time. A special attention has been paid on LPV systems for years because they are very handy for control purposes [11] [START_REF] Packard | Theory and application of linear parameter-varying control techniques[END_REF] [13] [14] [15] [16] and observation or filtering purposes [17] [18] [19] [START_REF] Sato | [END_REF]. In the special context of chaos synchronization, the problem of observers synthesis is particularly important. Indeed, the observers play the role of the receivers. It will be shown that, under some specific conditions, a chaotic system can be rewritten in the form of a polytopic LPV model. A polytopic LPV system is an LPV system such that the time-varying parameter admits a convex description. It turns out that, in such a case, the corresponding observer a gilles.millerioux@univ-lorraine.fr admits a simple Luenberger-like description called polytopic observer. The gains of the polytopic observer are simply derived from the solution of a convex optimization problem which is expressed in terms of Linear Matrix Inequalities (LMI) [21]. And yet, very efficient numerical tools are available to solve LMI (see [START_REF] Oliveira | LMI solver[END_REF] or the Yalmip Matlab toolbox). Besides, if we are not only concerned with stability but also with performances like robustness with respect to mismatched parameters or with respect to noise, the structure of the observer is kept unchanged. The gains are still derived from LMI but they are adapted to meet the required performances (see [START_REF] Halimi | Robust Control and Linear Parameter Varying Approaches[END_REF] for details). Thus, the simplicity of the observers design, that is of the receiver, is preserved. All those considerations highlight the interest of the LPV framework. The outline of the paper is the following. In Section 2, background on LPV systems and state reconstruction related problems are recalled. Then, the LPV framework is particularized to chaotic systems and it is shown how the issue of chaos synchronization can be addressed with such a framework. Section 3 is devoted to applications of the LPV framework. Several examples, from basic to advanced ones, are proposed in a tutorial-like form to clarify the main points. An example involving a chaos-based cryptosystem illustrates the use of the LPV framework in communication.

2 Chaotic systems and LPV framework 2.1 Background on polytopic LPV systems LPV systems are classes of systems obeying the following state space equations

x k+1 = A(ρ k )x k + Bu k y k = Cx k + Du k (1)
where x k ∈ R n is the state vector, u k ∈ R m is the control input, y k ∈ R p is the output vector, A ∈ R n×n is the dynamical matrix depending on the possibly time varying parameter vector

ρ k = ρ (1) k , ρ (2)
k , ..., ρ

(Lρ) k ∈ R Lρ , B ∈ R n×m is the input matrix,
C ∈ R p×n is the output matrix and D ∈ R p×m is the direct transfer matrix. The parameter ρ k is assumed to be available at every times k.

Remark 1 Let us note that (1) can be extended to affine systems and the timevarying parameter can be involved in all the state space matrices. In such a case, the following state space equations must be considered

x k+1 = A(ρ k )x k + B(ρ k )u k + E(ρ k ) y k = C(ρ k )x k + D(ρ k )u k (2)
In the sequel, we will focus on (1) for simplicity but the results can be extended in a straightforward way to [START_REF] Ogorzalek | [END_REF]. The dependence of A(ρ k ) with respect to ρ k can take many forms, in particular, polytopic. The polytopic decomposition refers to a dependence on ρ k of A(ρ k ) which reads

A(ρ k ) = N i=1 ξ (i) k (ρ k )A i (3)
where ξ k belongs to the compact set

Φ Φ = µ k ∈ R N , µ k = µ (1) k , . . . , µ (N ) k , µ (i) k ≥ 0 ∀ i and N i=1 µ (i) k = 1
Owing to the convexity of Φ, the set of matrices {A 1 , . . . , A N } defines a polytope denoted D A and the matrices A i correspond to the vertices of D A . Hereafter, for the sake of simplicity and whenever possible, the parameter dependency on ρ k of ξ (i)

k will be omitted, that is the notation ξ (i) k will be used instead of ξ

(i) k (ρ k ).
The conditions under which a polytopic decomposition can apply are now explained. If the components ρ (i)

k (i = 1, . . . , L ρ ) of ρ k belong to a bounded range [ρ (i) min , ρ (i) max ],
thus ρ k belongs to a bounded set Ω ρ ⊂ R Lρ . And then, Ω ρ can always be embedded in a polytope D ρ with vertices {ρ oi , . . . , ρ o N } ∈ R Lρ . It holds that

ρ k = N i=1 ξ (i) k ρ oi , ξ k ∈ Φ (4)
Furthermore, we can notice that A(ρ k ) in (1) can always be written as

A(ρ k ) = Ā(0) + Lρ j=1 ρ (j) k Ā(j) (5)
where Ā(0) and Ā(j) are constant matrices obtained from A(ρ k ). Ā(0) is the matrix derived from A(ρ k ) by keeping its constant entries and setting to zero its time varying entries. Ā(j) is the matrix derived from A(ρ k ) by setting to zero its constant entries and to unity the one corresponding to the location of ρ

(j) k in A(ρ k ).
Finally, after substituting (4) into (5), the vertices A i of (3) can be expressed as

A i = Ā(0) + Lρ j=1 ρ (j) oi Ā(j) (6)

Polytopic LPV description of chaotic systems

Let us consider the general nonlinear dynamical system assumed to exhibit a chaotic dynamics

x k+1 = g(x k , u k ) y k = Cx k + Du k (7)
where

x k ∈ X ⊆ R n is the state vector, u k ∈ R m is the input, y k ∈ R p is the measured signal.
The aim is to give some conditions under which (7) can be rewritten as [START_REF] Knuth | The Art of Computer Programming[END_REF].

The following proposition applies

Proposition 1 If the following conditions are fulfilled

-i) there exists a function ρ : R n → R Lρ such that A(ρ(x k ))x k + Bu k = g(x k , u k ) -ii) ρ(x k ) depends only on measured signals -iii) ρ(x k ) lies in a bounded set Ω ρ when x k lies in the admissible set X ⊆ R n
then the nonlinear system (7) admits an LPV form (1) with ρ k = ρ(x k ) and with polytopic description (3).

Proof 1

The key point is that, for a chaotic system, x k belongs to a chaotic attractor Ω and thus X = Ω. If Condition iii) is satisfied, Ω ρ is bounded and thus can always be embedded in a polytope D ρ . Furthermore, if Condition ii) is satisfied, ρ k is available at every times k. Finally, Condition i) is explicit for obtaining an LPV form.

Two problems must be handled. First, it is worth pointing out that, most often, the LPV description is not unique and multiple functions ρ can be candidates. Such a consideration will be clarified and illustrated in Example 1 of Section 3. Example 1 will also highlight the fact that chaotic systems involving polynomial nonlinearities admit a polytopic LPV description. Secondly, it may happen that obtaining analytically the polytope D ρ is either a hard task or is not possible at all. Moreover, we should be concerned, for the sake of conservatism, to get a minimal polytope. Let us assume that we can get, by simulation or experimentally, a sufficient number of vectors ρ k , collected in a finite set Γ ρ of cardinality N ρ , to describe the set Ω ρ with proper accuracy. The minimal polytope D * ρ wherein Ω ρ is embedded can thereby be considered as the convex hull of the set of points Γ ρ . We recall that an element of a finite set of points is an extreme point if it is not a convex combination of other points in this set. Hence, finding D * ρ amounts to finding the extreme points of Γ ρ . It turns out that the computation can be performed by standard methods. For instance, the built-in function convhull of Matlab can be used to that purpose. Such a point will be illustrated in Example 2 of Section 3.

Finally, it is clear that switched linear and switched affine systems also admit a description as (1) (or ( 2)) with a polytopic dependence (3) of the parameter. The only distinction lies in that the set Ω ρ is not a continuum but a finite set. Hence, the set Φ still holds with µ (i) k taking only extreme values 0 or 1. Such a point will be clarified and illustrated in Example 3 of Section 3.

Chaos synchronization with polytopic observers

Recalling that chaos synchronization can be formulated as a state reconstruction issue and so as an observer synthesis, we propose below an observer, called polytopic observer. The interest of such an observer is that it is suited for polytopic LPV models and so, for all the chaotic maps admitting such models. The synthesis principle is detailed in the simplest situation but enhancements can be proposed to handle the problems related to mismatch parameters, noisy context, performances guarantees (speed of convergence, . . . ) [START_REF] Halimi | Robust Control and Linear Parameter Varying Approaches[END_REF]. Let us assume that Proposition 1 holds. Hence, the matrix A(ρ k ) in (1) can be rewritten in the polytopic form (3). A polytopic observer for (1) obeys the following state space description

xk+1 = A(ρ k )x k + Bu k + L(ρ k )(y k -ŷk ) ŷk = C xk + Du k (8)
where xk ∈ R n , ŷk ∈ R p and L is a time-varying gain matrix depending on ρ k which reads

L(ρ k ) = N i=1 ξ (i) k (ρ k )L i , ξ k ∈ Φ (9)
and where the ξ 9) coincide, for every discrete times k, with the ones involved in the polytopic decomposition (3) of A(ρ k ). Let us point out that, such a requirement can always be satisfied whenever Condition ii) of Proposition 1 holds. Indeed, if ρ k is available, the vertices of the polytope D ρ being known, the polytopic decomposition (4) can be performed on-line. Then, it's a simple matter to see that, from (1) and ( 8), the reconstruction error e k = x k -xk is governed by the dynamics

(i) k (ρ k ) in (
e k+1 = (A(ρ k ) -L(ρ k )C) e k ( 10
)
The dynamics of the state reconstruction is nonlinear since A and L depend on ρ k . However, (10) can be viewed as an autonomous LPV polytopic system with state vector e k ∈ R n . Indeed, from (3), ( 9) and (10), and taking into account the coincidence between the ξ

(i)
k involved in (3) and ( 9), we get that

e k+1 = N i=1 ξ (i) k (ρ k )(A i -L i C)e k , ξ k ∈ Φ (11)
Global Asymptotical Stability (GAS) around the equilibrium point e * = 0 can be ensured by a suitable choice of the gains L i (i = 1, . . . , N ). To this end, the following standard theorem involving Linear Matrix Inequalities [21] is recalled.

Theorem 1 [START_REF] Halimi | Robust Control and Linear Parameter Varying Approaches[END_REF] If there exist symmetric matrices P i , matrices G i and matrices F i fulfilling, ∀ (i, j) ∈ {1...N } × {1...N }, the Linear Matrix Inequalities

P i (•) T G i A i -F i C G T i + G i -P j > 0 ( 12
)
then the polytopic observer (8) with gain

L(ρ k ) = N i=1 ξ (i) k (ρ k )L i and L i = G -1
i F i ensures that the system (10) is GAS.

Actually, [START_REF] Packard | Theory and application of linear parameter-varying control techniques[END_REF] ensures the existence of a Lyapunov function

V : R n × R L → R + defined by V (e k , ρ k ) = e T k P (ρ k )e k with P (ρ k ) = N i=1 ξ (i) k (ρ k )P i and ξ k ∈ Φ, called poly-quadratic Lyapunov function, fulfilling for all e k ∈ R n , for all ξ k ∈ Φ V (e k+1 , ρ k+1 ) -V (e k , ρ k ) < 0 (13)
which is sufficient for Global Asymptotical Stability. Such an observer can be useful for chaos-based communication purposes as it will be illustrated in Example 4 of Section 3.

Applications

Example 1

This example aims at clarifying the problem of the selection of good candidate functions ρ which fulfill conditions of Proposition 1.

Let us consider the chaotic system derived from the Duffing map and involving polynomial nonlinearities

         x (1) k+1 = x (2) k x (2) k+1 = -2 x (1) k 3 + 2 x (1) k + 0.3 x (1) k x (2) k y k = x (1) k (14)
The corresponding attractor Ω is depicted in Figure 1 (a). Let ρ k be the time-varying parameter vector defined as

ρ (1) k = -2 x (1) k 2 + 2 ρ (2) k = 0.3 x (1) k
Then, the map ( 14) can be rewritten as an LPV system (1) with

A(ρ k ) = 0 1 ρ (1) k ρ (2) k , B = 0, C = [1 0] and D = 0
The parameter ρ k is available from the output y k . Indeed, ρ k is not available from measured signals.

Example 2

This example aims at illustrating the method to get the minimal polytope D * ρ . Let us consider the following system derived from the "Tinkerbell map" given in [START_REF] Nusse | Dynamics: Numerical Explorations[END_REF] [24]

                       x (1) k+1 = x (1) k 2 -x (2) k 2 + ax (1) k + bx (2) k x (2) k+1 = 2x (1) k x (2) k + cx (1) k + dx (2) k x (3) k+1 = 0.1bx (2) k -0.1 x (2) k 2 + 0.1x (3) k x (4) k+1 = 0.5x (1) k + 0.1x (2) k + 0.3x (4) k y (1) k = x (1) k y (2) k = x (2) k (15)
with a = 0.9, b = -0.6013, c = 2 and d = 0.5. For such a setting, the system exhibits a chaotic behavior. The objective is to rewrite (15) in the LPV form (1) with polytopic dependence (3) and to find the minimal polytope D * ρ . To this end, let us define

θ (1) k = a + x (1) k θ (2) k = b -x (2) k (16)
Then, ( 15) can be rewritten as ( 1) with the time-varying parameter vector ρ k such as

A(ρ k ) =     ρ (1) k ρ (2) k 0 0 c ρ (3) k 0 0 0 ρ (4) k 0.1 0 0.5 0.1 0 0.3     where          ρ (1) k = θ (1) k ρ (2) k = θ (2) k ρ (3) k = d + 2(θ (1) k -a) ρ (4) k = 0.1θ (2) k and C = 1 0 0 0 0 1 0 0
The matrices B and D are zero since the system ( 15) is autonomous. The parameter ρ k is available from the output y k and ρ(x k ) is bounded. Indeed, θ

= a + y

k , ρ (2)
k ) subspace are depicted in Figure 2 (a). Another polytope D ρ , that is non minimal in such a case, can be defined as depicted in Figure 2 (b). The number of vertices reduces to 5 but the stability conditions ( 12) would be more conservative. To conclude, such a choice for ρ k fulfills the conditions of Proposition 1.

Example 3

This example aims at illustrating that a switched linear systems also admits an LPV form like (1) with polytopic description (3). Let us consider the following map derived from the "Lozi map" given in [START_REF] Peitgen | Chaos and fractals: new frontiers of science[END_REF] after replacing the affine part "1" by a new variable x

(3) k              x (1) k+1 = -1.7 x (1) k + x (2) k + x (3) k x (2) k+1 = 0.5 x (1) k x (3) k+1 = x (3) k y k = 2 x (1) k (17)
Define ρ k as the one-dimensional time-varying parameter such as

ρ k = ρ (1) k with ρ (1) k = -1.7 if x (1) k ≥ 0 1.7 if x (1) k < 0
Then, ( 17) can be rewritten in the form (1) with

A(ρ k ) =   ρ (1) k 1 1 0.5 0 0 0 0 1   , B = 0, C = [2 0] and D = 0
The vector ρ k only takes two specific values ρ min = -1.7 and ρ max = 1.7. Hence, Ω ρ = {ρ min , ρ max } is not a continuum but reduces to a finite set of two elements. The vertices of the polytope D ρ coincide with Ω ρ . The vertices are ρ o1 = ρ min = -1.7 and ρ o2 = ρ max = 1.7. Such a choice for ρ k fulfills all the conditions of Proposition 1. In particular, ρ k is available from the output y k . Indeed, ρ

= -1.7 if y k ≥ 0 1.7 if y k < 0 (1) k
Besides, ρ(x k ) is clearly bounded. To conclude, such a choice for ρ k fulfills the conditions of Proposition 1.

Example 4

This example aims at illustrating the use of polytopic observers to ensure chaos synchronization for a chaos-based switching cryptosystem.

The general principle is recalled on Figure 3. The transmitters 1 and 2 are de- scribed by Υ 1 and Υ 2 respectively. Let us denote with x j k the state vector of the system Υ j and with x (i,j) k the ith component of x j k for the system Υ j .

Υ 1                x (1,1) k+1 = -1.4 x (1,1) k 2 + x (2,1) k + x (3,1) k x
(2,1)

k+1 = 0.3 x (1,1) k x (3,1) k+1 = x (3,1) k y 1 k =0.4 x (1,1) k (18)
and

Υ 2                  x (1,2) k+1 = -0.825x (1,2) k -0.296 x (1,2) k 2 -x (2,2) k + 1.04 x (1,2) k 2 x (2,2) k -1.04 x (1,2) k 4 x (2,2) k x (2,2) k+1 = 1.127 x (1,2) k y 2 k = 0.5 x (1,2) k (19)
The information m k is binary and then, only takes two values m 1 = 0 or m 2 = 1.

According to the current value of the information at time k, the output y 1 k of Υ 1 or y 2 k of Υ 2 is conveyed through the channel, that is

y k = y 1 k if m k = m 1 y 2 k if m k = m 2 (20)
The objective is to design the receivers assigned to each system in order to recover m k . To this end, two polytopic observers are well suited. We detail below the off-line step (design) and the on-line step (deciphering).

Off-line step Υ 1 and Υ 2 admit an LPV polytopic description (1) as shown below.

-System Υ 1 (18) The time-varying parameter for System Υ 1 (18) is denoted ρ 1 k . It is defined as a one-dimensional vector such as

ρ 1 k = ρ (1,1) k with ρ (1,1) k = -1.4 x (1,1) k (21)
Then, (18) can be rewritten in the LPV form (1) with polytopic dependence (3) where

A(ρ 1 k ) =   ρ (1,1) k 1 1 0.3 0 0 0 0 1   , C = 0.4 0 0
The matrices B and D are zero since (18) is autonomous. The parameter ρ 1 k is available from the output y 1 k since ρ

(1,1) k = -3.5y 1 k . Furthermore, the vector ρ 1 k belongs to the range min(ρ

(1,1) k ) max(ρ (1,1) k
) . As a result, the minimal polytope D * ρ 1 is obtained in a straightforward way. It involves 2 vertices ρ 1 o1 = min(-1.4 x

(1,1) k

) and

ρ 1 o2 = max(-1.4 x (1,1) k
) (N = 2) and the vertices A i of (3) can be directly derived with [START_REF] Banerjee | Chaos Synchronization and Cryptography for Secure Communications: Applications for Encryption[END_REF]. As a conclusion, the definition of ρ 1 k fulfills the conditions of Proposition 1.

-System Υ 2 [START_REF] Toth | proceeding of: Proceedings of the European Control Conference[END_REF] The time-varying parameter of System Υ 2 (19) is denoted ρ 2 k and is two-dimensional. It is defined as

ρ (1,2) k = -0.825 -0.296 x (1,2) k ρ (2,2) k = -1 + 1.04 x (1,2) k 2 -1.04 x (1,2) k 4 (22)
Then, ( 19) can be rewritten in the LPV form (1) with polytopic dependence (3) where The receivers 1 and 2 are chosen to take the form of polytopic observers (8) for the respective systems ( 18) and ( 19) following the principle as depicted in Figure 3. To this end, the toolbox Y almip of Matlab is used to solve the LMI [START_REF] Packard | Theory and application of linear parameter-varying control techniques[END_REF] from which the gains L 1 and L 2 are derived for each system Υ 1 and Υ 2 . It turns out that the LMI (12) are feasible and the gains L 1 and L 2 can be performed from by G -1 i F i according to Theorem 1.

A(ρ 2 k ) = ρ (1,2) k ρ ( 2

On-line step a) state reconstruction

The on-line state reconstruction, and so the chaos synchronization, is performed online by the polytopic observers (8) for each system Υ 1 and Υ 2 . The results are depicted in Figures 5 and6. Figure 5 highlights the time evolution of the state reconstruction errors x

(1,1) k - x(1,1) k , x (

Conclusion

This paper has presented a unified framework to achieve chaos synchronization of both classes of chaotic discrete-time systems, namely maps involving polynomial nonlinearities and piecewise linear maps which encompass a very large class of chaotic systems. It has been derived conditions under which those chaotic systems can be rewritten as polytopic Linear Parameter Varying (LPV) models. The outcome of the LPV framework lies in that, the observers, which play the role of the receivers, admit a simple Luenberger-like description for all those chaotic systems. Hence, such a framework gives a systematic approach for the design of the receivers. The gains of the polytopic observers are derived from the solution of a close set of Linear Matrix Inequalities for which standard solvers exist. The use of the LPV framework has been illustrated for the chaotic switching cryptosystem but the same methodology applies for all the well-known chaotic cryptosystems, namely, the parameter modulation, the two-channel transmission, the message embedding. Finally, the LPV framework is flexible enough to cope with mismatched parameters or noisy contexts. Indeed, the structure of the observer is kept unchanged. Only the gains must be adapted but it turns out that they are still derived from LMI and so, the ease of design is preserved.

k

  = 0.3 y k . Furthermore, ρ k belongs to a set Ω ρ as depicted in Figure1(b) which clearly highlights the fact that Ω ρ is bounded and can be embedded in a polytope D ρ . As a conclusion, such a definition for ρ k fulfills all the conditions of Proposition 1.

Fig. 1 .

 1 Fig. 1. (a) Chaotic attractor Ω (b) Set Ωρ

  k . By iterating (15), 2000 vectors ρ k are collected and gathered in the set Γ ρ which is bounded. The function convhull of Matlab is used to find the minimal polytope D * ρ of D ρ . It succeeds in giving 108 vertices ρ oi . Both the set Ω ρ and the minimal polytope D * ρ in the (ρ(1)

Fig. 2 .

 2 Fig. 2. (a) Set Ωρ and polytope D * ρ (b) Polytope Dρ with 5 vertices

Fig. 3 .

 3 Fig. 3. Secure communication setup

y 2 k 4 .

 24 The matrices B and D are zero since[START_REF] Toth | proceeding of: Proceedings of the European Control Conference[END_REF] is autonomous. The parameter ρ 2 k is available from the output y 2 k since ρ After iterating (19), 500 vectors ρ 2 k are collected and gathered in Γ ρ 2 which is bounded. The function convhull of Matlab is used to find the minimal polytope D * ρ 2 of D ρ 2 . It succeeds in giving 121 vertices ρ 2 oi . The set Ω ρ 2 and the minimal polytope D * ρ 2 are depicted in Figure4. The vertices A i of (3) can be directly derived with[START_REF] Banerjee | Chaos Synchronization and Cryptography for Secure Communications: Applications for Encryption[END_REF]. As a conclusion, the definition of ρ 2 k fulfills the conditions of Proposition 1.

Fig. 4 .

 4 Fig. 4. Set Ω ρ 2 and polytope D * ρ 2 of Υ2

Fig. 5 .Fig. 6 .

 56 Fig. 5. State reconstruction error for Υ1

Fig. 7 .

 7 Fig. 7. Recovered information mk


R Castro-Beltran

N Huby

G Loas

H Lhermite

D Pluchon

B Bêche

Improvement of efficient coupling and optical resonances by using taper-waveguides coupled to cascade of UV210 polymer micro-resonators

In this paper, we report the overall design, fabrication and optical characterization of single and multiple resonant micro-structures patterned on the UV210 polymer and shaped by adequate deep-UV lithography procedures. Various families of ring and racetrack forms are investigated with different geometrical dimensions linked to the micro-resonators and the specific taper-waveguides and gaps allowing the optimized coupling. Well defined photonic structures families in the sub-micrometer range obtained by this deep UV-light process are clearly confirmed through scanning electron microscopy. In order to evaluate and quantify the efficiency of the submicrometer coupling, the recirculation of the light and the quality of the optical resonance aspects, a global study including top view intensity imaging, spectral measurements and Fast Fourier Transform analysis is performed for all these devices based on single and multiple family resonators. The experimental TE-mode resonance transmissions reveal a complete agreement with the period of the theoretically expected resonances. A maximum value of the quality factor Q = 3.5 x 10 3 at 1035 nm with a 3.2 times higher resonance contrast is assessed for cascade of triple micro-resonators respect to the photonic devices based on only one micro-resonator. In addition, these UV210 circuits made of specific tapers coupling to cascade loops act directly on the improvement of the evanescent coupling and resonances in terms of quality factor and extinction rate, by selecting successively and more precisely the optical mode resonance. All these designs and low cost technological reproducible steps, and furthermore the devices and protocol measurements are markedly suitable for mass fabrication and metrology applications. Figure 1. Schematic representation and structural details of (a) single micro-Ring and (b) single micro-RaceTrack. Parameters R, L c and gap represent respectively the radius, the coupling length and the distance between the rib waveguides and the micro-resonators.

Introduction

Developing new photonic devices through simple, low cost and parallel fabrication steps has been over the last decade extremely important for biosensing and telecom applications [1][2][3][START_REF] Flueckiger | Proc. of SPIE 7929 79290I[END_REF][START_REF] Beck | [END_REF]. In particular, the ability to fabricate systems with nanoscale features requires critical procedures that range from direct laser writing to photoresist-based patterning [6][START_REF] Sheng | 6th IEEE Int. Conf[END_REF][START_REF] Sahoo | [END_REF][9][10]. Because of the resolution limits on the patterning techniques, not all the lithography systems can generate photonic devices in the submicrometer scale. Two routes can be followed: the first one refers to a modification on the lithography systems by decreasing the exposure wavelength. Changing the presentation of the filters, as was done in the deep ultraviolet (DUV) lithography system, allows a reduction in the optical lithographic wavelength from 365 nm i-line to 248 nm [START_REF] Sahoo | [END_REF]. The second route refers to the photonic circuit design strategies. Thus, in the case of microresonators, it consists in a vertical coupling between the bus waveguide and the resonant structure. Multilayer stack and submicrometer gap are then controlled by reactive ion etching process [START_REF] Luan | Proc. of ECTC '07 2035[END_REF][START_REF] Delezoide | [END_REF].

To fabricate our photonic devices, we opted for DUV lithography using the chemically amplified (CA) UV210 photoresist as polymer [13]. This positive photoresist is now used for submicrometer photonic patterns [14,15]. The evolution and capacity of this polymer to act as more classical photonic structures have been demonstrated. Single-mode rib waveguides have shown off optical losses about few dB/cm whereas lateral coupling zones of few hundred nanometers have proven the possibility of developing first photonic structures [16,17].

The capacity of emerging photoresist to be used for the development of photonic circuits, mainly constituted by resonant structure, demonstrated the capability for photonic miniaturization. Such resonators have proven to be useful on-chip integration for a large number of applications ranging from environment monitoring to wavelength filtering. For such applications, the shape of the resonances must present appropriate optical properties that are strongly connected to the fabrication process. Recently, serial of multiple micro-resonators on another material have found promising functionality as an optical element by providing more uniform resonance responses [START_REF] Tobing | Proc. of SPIE[END_REF][START_REF] Chao | [END_REF][START_REF] Timotijevic | [END_REF][21]. Cascade of multiple resonators, distributed with identical cavities, can enhance the optical transmission features without influence on the free spectral range (FSR). An improvement in the full width at half maximum (FWHM) through sharper roll-off resonances, results in an enhancement in the finesse and in the quality (Q) factor of the photonic devices [START_REF] Timotijevic | [END_REF]22].

The aim of this paper is to investigate the capability of the UV210 polymer to support tapers coupled to different cascade of multiple Ring and RaceTrack micro-resonators by low cost and reproducible deep UV (DUV) lithography procedures. Section 2 reports all the global geometrical parameters of these family microstructures, describes the DUV lithography fabrication processes and the scanning electron microscopy (SEM) images highlighting the quality and reproducible aspects of such micro-and nanoscale integration systems. Moreover, the entire platform devoted to the measurements and the specific protocol is described. The overall optical characterization of the family structures using micro beam profile (MBP) system and optical spectral analyzer (OSA) coupled with fast Fourier transform (FFT) analysis are presented in Sections 3. The discussions presented in Section 4 emphasize the advantages of such integrated configurations on the improvement of optical resonances.

Design, fabrication and integration technologies of the tapers/micro-resonators structures

The details of two circuits shaped as tapers coupled to single micro-resonators under test are illustrated in figure 1.

Figures 1(a) and 1(b) describe the geometrical parameters for the two different families defined as single Ring and single RaceTrack MRs respectively. As illustrated in figure 1, the resonators are coupled by two straight slowly tapered waveguides of 2µm width, assuring both single-mode optical propagation, an exaltation of the field in the taper and coupling zone, plus an efficient evanescent power-coupling into the MR [START_REF] Beck | [END_REF]. The features and presentations on all the design of the devices under test, such as devices with one (Single), two (Double) and three (Triple) consecutive cavities, with Ring and RaceTrack shapes, with radius of R = 25 µm and R = 50 µm, allow us to classify them as presented in table 1. Since many different devices are tested, a nomenclature has been introduced for more simplicity: as an example SSR means Single Small Ring, DLRT means Double Large RaceTrack, whereas TSR means Triple Small Ring. In addition, it is noteworthy that for devices with Double and Triple cavities, the micro-resonators keep their dimensions unchanged and the distance between two consecutive MRs has been chosen long enough in order to avoid direct interaction between two independent resonators.

Deep UV lithography processes on the micro-and nano-scale

The fabrication procedure of Single and cascade of Ring and RaceTrack MRs is schematically represented in figure 2. Devices are fabricated by DUV lithography and the whole process is performed in a class 100 cleanroom. The starting point of the micro-fabrication and engineering processes consists of a (1 0 0) silicon substrate covered with a 1.5 µm-thick thermal SiO 2 layer acting as an optical lower cladding with n = 1.45 at 980 nm. A 1 µm-thick layer of the UV210 polymer is spin-coated on the SiO 2 /Si substrate. In order to evaporate the remaining solvent in the deposited layer, a softbake procedure is done before exposure. Single and cascade of multiple MRs patterns are transferred onto such UV210 polymer layer by using only one deep UV lithography exposure through quartz mask. Light exposure is performed using a UV lamp (HBO 1000 W/D, mercury short arc lamp from OSRAM) combined to a bandpass filter to obtain a 248nm insolation-wavelength. This is immediately followed by the post exposure bake (PEB) procedure which consists in putting the substrate on a hot plate to allow the UV210 polymer to complete the crosslinking. Before developing the serial of optical circuits on the chip, 10 minutes of cooling down allow the surface of the layer to capture oxygen which helps in the quality of the patterning of the devices. After this, the sample is immersed in the developer solution to remove insolated zones and reveal the micro and sub-micrometer patterns as the gap or coupling zones tapers/MRs. Finally, the last step consists in fully cross-linking the polymer layer by curing process also referring as hard bake step. This process is realized in an oven with temperatures ranging from 100 °C-150 °C during 24 hours.

Scanning electron microscopy and quality of circuits

Scattering losses from interfaces imperfections associated with fabrication procedures are fundamental aspects for efficient miniaturization of photonic circuits [START_REF] Chao | [END_REF]23]. It is particularly important to follow the structural qualities like shape and surface conditions of the photonic devices before all the specific optical characterizations. SEM images have been taken systematically on each device and some of the results are gathered on figure 3.

Figure 3(a) and figure 3(b) present respectively the top-view perspectives of the SLR and SLRT. Both photonic devices are well defined presenting a radius of R = 50 µm, a width of W = 5 µm and for SLRT a coupling length L c = 60 µm. Figure 3(c) shows the tilted top-view of the TLR device confirming constancy on the properties of the cascade of the three Ring microresonators. Figure 3(d) presents the most important aspect on this kind of configuration: coupling zone and quality of manufacture on the sidewalls of the photonic devices. The measurement of the gap width by SEM image treatment leads to mean value of 531 nm for the ring and 500 nm for the racetrack. The standard deviation calculated for several measurements along the coupling length for these structures are 14 nm and 23 nm respectively, showing the high accuracy of the DUV lithography method.

Experimental protocol, optical injection and coupling

The experimental platform is presented in the schematic diagram of figure 4. Two optical broadband sources are used to characterize the photonic circuits patterned as tapers/MRs. The first one is centered at 845 nm with a FWHM of 30 nm of and the second one at 1025 nm with a FWHM of 45 nm. The outputs of both sources are connected to single mode fibers and coupled to a x20 objective to collimate the optical beams. The transverse electric TE polarization is controlled with a polarizer. The beam is then focused and coupled to the devices under test through one of the inputs of the rib waveguides with a x20 objective. The device and the objective for light injection are positioned on piezo electric nano-positioners. The beam at the output of the device is collected and collimated by a x20 objective and simultaneously monitored with a IR camera and an optical powermeter. Once the maximum of power is obtained, the optical powermeter is replaced by an optical spectra analyzer (OSA Ando AQ-6315E) for resonances detection analysis.

A Micro Beam Profiler (Newport-MBP) is used to corroborate the light propagation along the rib waveguides and the loop of the resonant structures. It is positioned on top of the devices with the aim of collecting their scattered light. Figure 5 presents the recorded image for TLR device. Figure 5(a) highlights the light propagation along the three loops of the Ring micro-resonators. It also displays the coupling light along the add port through the three coupling regions belonging to each micro cavity thus confirming the evanescent coupling between rib waveguides and serial of MRs.

The corresponding cross-sectional intensity measurements are presented on figure 5(b). This intensity profile allows an estimation of the geometrical dimensions such as the diameter of the Rings (100 µm) and the width between the two sidewalls that form the cavity (5 µm). These measurements reproduce well the dimensions obtained by SEM which demonstrates the accuracy of this method to estimate geometrical conditions of one photonic structure.

Optical characterizations and resonances, spectral analysis, results and discussions

Referring to the experimental setup of figure 4, we characterized all the families and series of microresonators by using two different large bandwidth sources. After having optimized the intensity of the light emerging from the waveguide, this signal is coupled to the OSA to observe the multiple resonances corresponding to each kind of MR. A complementary optical characterization over one tapered waveguide under the same geometrical conditions allowed us to confirm that the modal propagation properties remain free of conversion and of internal interferences, which means a completely adiabatic process into the tapered waveguide and between the micro-resonators [START_REF] Beck | [END_REF]. As an example, figure 6 shows the comparison between the normalized intensities at the transmitted ports of the SLR and TLR devices by using the broadband source centered at 845 nm. Deeper resonances are clearly observed for cascaded MRs compared to single MR. Indeed, 2.5 times higher contrast is calculated for those resonances obtained for the TLR device in comparison with its corresponding registered for the SLR device. We can also notice on figure 6(a) a slight wavelength shift between their corresponding resonances transmissions. This is not surprising since both devices are from two independent photonic chips and are optically characterized under different OSA alignment and thermal conditions. The most important optical parameters that describe the response and behavior of a microresonator are the free spectral range (FSR), the FWHM, the quality factor Q and the finesse F [17]. All these features hinge on the losses and the coupling coefficients describing each MR. Regarding resonance of the cascade of TLR in figure 6, taking into account the geometrical conditions and the refractive index n UV210 of 1.553 at 850 nm, FSR-values ranging from 1.41 nm to 1.52 nm are theoretically expected between λ = 830 nm and λ = 860 nm wavelengths respectively. Possible slight difference between the theoretically and experimentally obtained FSR-values can be explained by considering the effective group index (n g ) which is inherent to any optical large bandwidth source.

The normalized FFT responses, presented in figure 6(b), reveal the good agreement of the theoretical FSR-value with the experimental one. Through Lorentzian fitting, values of 0.6 nm of FWHM at λ = 848.21 nm, Q-factor of 1.4×10 3 and F of 2.6 are calculated. Those values are improved compared to SLR showing calculated values of 0.9 nm of FWHM at λ = 848.03 nm, Q-factor of 0.95×10 3 and F of 1.6. We chose to not present in figure 6 the resonance spectrum of the DLR device for more clarity, it is nevertheless clear that cascaded micro-resonators improve greatly the photonic circuit properties. DLR device presents values of 2 times higher contrast in the depth of the resonances, in comparison with the SLR device. Moreover, we characterized in parallel all the serial of MRs by using a large bandwidth source centered at 1025 nm. As an example, figure 7 shows the resonance spectra of the SSRT and of the TSRT devices. As previously demonstrated, for the SLR and TLR resonance transmissions, the multiple loops corresponding to multiple RaceTrack MRs also improve the optical properties since the resonance peaks are deeper and with higher extinction ratio. For this case, 3.2 times of higher contrast is calculated for the resonances registered for the TSRT device in comparison with those obtained for the SSRT device. The resonance spectrum of the DSRT device (not shown here) presents values of 1.4 times higher contrast in comparison with the SSRT device.

Under these geometrical and experimental conditions, we expect theoretical FSR-values ranging from 2.3 nm to 2.7 nm between λ = 1000 nm and λ = 1060 nm wavelengths respectively. The FFT analysis, presented in the figure 7, highlights a main contribution at 2.9 nm for TSRT unlike SSRT that present a wider range in the period of the resonances which are disseminated around 2.8 nm. This is due to the cascade of multiple loops, which besides improving the properties of the resonance frequencies, can act as modal filters by selecting successively and then more precisely the optical mode resonance. When multiple frequencies are traveling along the resonator, this works as a very dispersive photonic structure and slight deficiencies on the quality of fabrication enhance the delaying process. Nevertheless, cascade of resonators restrict this delayed condition by limit the bandwidth of the frequencies that can be delayed. Here, resonators in multistage configuration act as high order optical filters based on the same principle used in electronics [22]. Possible slight difference between the theoretically and experimentally obtained FSR-values can be explained by considering the dispersion of the effective group index (n g ) inherent to the use of optical large bandwidth source.

In order to analyze further the role of geometry and number of devices as well as light source on the resonators behavior, figure 8 summarizes the obtained results on the evolutions of the Q-values for the series of micro-resonators under test. The graphs present an evolution of their Q-values according to several parameters of all familydevices such as the shape, the dimension, the number of resonant structures and the wavelength excitation sources. A clear enhancement is observed on the Q-factor magnitudes as the number of loops in the photonic devices increases. Moreover, the two groups of devices (Ring and RaceTrack) present also a positive evolution on their Q-values when MRs with longer geometrical dimensions are analyzed. This is mainly because the Q-factor presents a linear dependence with the length of the MR.

The Q-values obtained through these configurations represent an enhancement respect to our previous publication on which maximum Q-values of 850 for disks and of 630 for stadium were obtained at 850 nm of excitation wavelength [17]. These results were obtained for filled structures and have to be compared with their corresponding empty structure investigated here, e.g., single Ring and single RaceTrack. Through empty resonant structures, an improvement in the resonance transmission properties and Q-factor is expected since these are known to better confine the light and to promote the single mode operation. Nevertheless, the enhancement on the Q-values is temperate, less than one order of magnitude, which can be explained in terms of roughness. Indeed, the losses are mainly dominated by the sidewalls roughness that is doubled in empty structures. In addition, a longer extension of the coupling zone can contribute to both a strong coupling strength and with added light scattering too [START_REF] Chao | [END_REF]23].

Another interesting aspect appearing on figure 8 is related to the selection of the wavelength excitation source. We can note that, all the photonic devices enhanced their responses under the broadband source center at 1025 nm which is in good agreement with Ref. [23]. Apparently, the coupling strength, mainly due to elongating the gap zone and, the losses, basically dominated by the two sidewalls of the photonic devices, present a different behavior when the two broadband sources were used. This behavior can be explained as following: backward reflections due to sidewall roughness in the photonic devices limit their resonance properties. At shorter excitation wavelength the scattering of the propagating light is stronger which can cause back-scattering into a counter-propagating mode which makes that the Q-value decreases.

Finally the evolution presented in figure 8 demonstrates an enhancement on the Q-values as the number of loops involved in the photonic circuit increases. No saturation effect in the Q-values suggests that improvement on the optical response is still feasible and will be subject of further study. Indeed, different routes may be tested. On the one hand post-deposition treatment (thermal or plasma) can improve the roughness of the side walls and optical losses directly connected to the Q factor. On the other hand, a different approach will be to pattern the submicronic gap by e-beam lithography.

Conclusion

The high capacity of the chemically amplified UV210 polymer to support cascade of various families of micro-resonators (MRs) with different geometries and dimensions is presented in this work. The adequate quality of the fabrication process by deep UV lithography is validated by SEM images and confirmed by micro beam profiles (MBP) imaging. In particular, the sub-micrometer gap remains constant along the coupling zones for cascade of multiple MRs showing a gap along the coupling zone of 531 +/-14 nm and 500+/-23nm for ring and racetrack respectively. In addition, MBP demonstrates the efficient evanescence coupling between the taper-waveguides and the resonant cavities of the devices due to the adequate exaltation of the optical field. Through spectral analyses and protocol measurements, we verified the excellent agreement of the theoretical and experimental FSR-values of all the series of families of MRs under test. A systematical study on single and cascade of Ring and RaceTrack MRs is presented in order to correlate geometrical aspects and cavity efficiencies. The improvement on the resonance properties is due to the structural organization of the multiple loops presented in cascade of MRs. Cascade of three RaceTrack microresonators show the best optical response, presented values of Q = 3.5 × 10 3 and 3.2 times higher resonance contrast respect its corresponding single devices. In addition, the FFT-anlyses of the optical responses of cascade of multiple cavities demonstrate to have a very high capacity to discriminate between modal propagation that does not correspond to the opto-geometrical conditions of the resonator. The ability of new organics, as the CA UV210 polymer, to undergo integrated optics transformations that contribute to the trend of photonic circuit miniaturization is demonstrated through the design of various associations tapers/MRs which are suitable for different purposes like filters or thermal sensors.

Figure 2 .

 2 Figure 2. Scheme of global fabrication steps of a chip using DUV lithography procedures on quartz-mask. (a) Transfer of waveguide patterns into the UV210 polymer. (b) Cross section representation of one of the Single devices after having developed and cured the sample.

Figure 3 .

 3 Figure 3. Visualization of the structural details through SEM images of the devices: (a) SLR, (b) SLRT, (c) tilted views of TLR and (d) a zoom on the coupling zone of the Ring micro-resonators forming the device.

Figure 4 .

 4 Figure 4. Experimental setup. Two broadband sources are used to characterize the different microresonators. XYZ nanometer displacement mounts are used to control the alignment of the incident NIR objectives (x20) and of the device position. An optimized control of the light injection, propagation and detection is achieved through IR camera, optical powermeter and MBP system. Microresonators resonances are finally analyzed with an Optical Spectrum analyzer. SMF: Single mode fiber.

Figure 5 .

 5 Figure 5. Field intensity pattern of the TLR. (a) Confirmation of the light propagation through the rib waveguides and recirculation into the loops. (b) Intensity profiles of the cross-sectional line visible on the figure 5(a).

Figure 6 .

 6 Figure 6. (a) Resonances transmissions spectra for SLR and cascade of TLR. (b) Corresponding normalized fast Fourier transform (FFT) for both devices.

Figure 7 .

 7 Figure 7. (a) Experimental normalized responses of the SSRT and TSRT and (b) their corresponding normalized FFT signals.

Figure 8 .

 8 Figure 8. Evolution of the Q-factor values as a function of the multi-stage configuration: single (line-square), double (line-circle) and triple (line-triangle). Q-values obtained by using the broadband source (a) centered at 845 nm and (b) centered at 1025 nm.

Table 1 .

 1 Global classification and abbreviation of all the families of micro-resonators under test

	Cavities	Size	Shape	Nomenclature
	Single: S	Small (S)	Ring (R)	SSR, SLR
		Large (L)	RaceTrack (RT)	SSRT, SLRT
	Double: D	Small (S)	Ring (R)	DSR, DLR
		Large (L)	RaceTrack (RT)	DSRT, DLRT
	Triple: T	Small (S)	Ring (R)	TSR, TLR
		Large (L)	RaceTrack (RT)	TSRT, TLRT

Acknowledgments

This work was supported by Région Bretagne (SAD program).The authors are grateful to the assistance of F. Gouttefangeas and L. Joanny from the CMEBA in University Rennes 1 for SEM work.


André Seznec

TAGE-SC-L Branch Predictors *

Keywords: Global, local, skeleton histories

Outline

The TAGE predictor [START_REF] Seznec | A case for (partially)-tagged geometric history length predictors[END_REF] is considered as one of the most storage effective global branch/path history predictors. It has been shown that associated with small adjunct predictors like a statistical corrector (SC for short) and/or a loop predictor (L for short) [START_REF] Seznec | A new case for the tage branch predictor[END_REF][START_REF] Seznec | A 64 kbytes ISL-TAGE branch predictor[END_REF], TAGE can even be more effective. In this study, we explore the performance limits of these TAGE-SC-L predictors for respectively 32Kbits storage budget, 256 Kbits storage budget and quasi-unlimited (< 2 Gbits) storage budget.

With a 32Kbits storage budget, only a very limited storage budget can be invested in the adjunct predictors. Then our submitted predictor used most of its storage budget on the TAGE predictor and features only a small loop predictor LP and a simple corrector filter CF. The submitted 32Kbits predictor achieves 3.315 MPKI on the CBP-4 traces.

With a larger storage budget, one can invest more significant storage budget in the adjunct predictors. The submitted 256Kbits TAGE-SC-L predictor features a TAGE predictor, a loop predictor LP and a quite complex (≈ 45 Kbits) statistical corrector SC that exploits local history, global branch history and return-associated branch history. The 256Kbits TAGE-SC-L predictor achieves 2.365 MPKI on the CBP-4 traces.

The no-limit budget allows to use a statistical corrector build with many components exploiting global branch and path histories, local histories and some form of skeleton histories. The submitted predictor achieves 1.782 MPKI on the CBP-4 traces.

General view of the TAGE-SC-L predictor

The TAGE-SC-L predictor consists of three components: a TAGE predictor, a statistical corrector predictor and a loop predictor (Figure 1).

The TAGE predictor provides the main prediction. Then this prediction is used by the statistical corrector predictor which role consists in confirming (general case) or reverting the prediction. The statistical predictor reverts the prediction when it appears that, in similar circumstances (prediction, branch histories, branch confidence, ..) TAGE statistically mispredicted. The loop predictor is useful to predict regular loops with long loop bodies.

The TAGE conditional branch predictor

The TAGE predictor was described in [START_REF] Seznec | A case for (partially)-tagged geometric history length predictors[END_REF] and [START_REF] Seznec | The L-TAGE branch predictor[END_REF]. Only marginal modifications are introduced in this study.

Figure 2 illustrates a TAGE predictor. The TAGE predictor features a base predictor T0 in charge of providing a basic prediction and a set of (partially) tagged predictor components Ti. These tagged predictor components Ti, 1 ≤ i ≤ M are indexed using different history lengths that form a geometric series [START_REF] Seznec | Analysis of the O-GEHL branch predictor[END_REF], i.e, L(i) = (int)(α i-1 * L(1) + 0.5).

In practice, the set of history lengths used in the submitted predictors were obtained, first through exploring the use of a geometric series, then through refinements. These refinements led to limited benefits (< 0.5% ) on accuracy.

Throughout this paper, the base predictor will be a sim- ple PC-indexed 2-bit counter bimodal table; in order to save storage space, the hysteresis bit is shared among several counters as in [START_REF] Seznec | Design tradeoffs for the ev8 branch predictor[END_REF] for the limited size predictor. An entry in a tagged component consists in a signed counter ctr which sign provides the prediction, a (partial) tag and an unsigned useful counter u. In our study, u is a 2-bit counter and ctr is a 3-bit counter for the limited size predictors, and a 5-bit counter for the no-limit predictor.

A few definitions and notations The provider component is the matching component with the longest history. The alternate prediction altpred is the prediction that would have occurred if there had been a miss on the provider component.

If there is no hitting component then altpred is the default prediction.

Prediction computation

The prediction selection algorithm is exactly the same as described [START_REF] Seznec | A case for (partially)-tagged geometric history length predictors[END_REF] or [START_REF] Seznec | The L-TAGE branch predictor[END_REF].

At prediction time, the base predictor and the tagged components are accessed simultaneously. The prediction is provided by the hitting tagged predictor component that uses the longest history. In case of no matching on tagged predictor component, the default prediction is used.

However we remarked that when the confidence counter of the matching entry is null, on some traces, the alternate prediction altpred is sometimes more accurate than the "normal" prediction. This property is global to the application and can be dynamically monitored through 4-bit coun-ters ( USE ALT ON NA in the simulator). For this submission, we use a small array of USE ALT ON NA counters indexed by the program counter (< 0.5% reduction of the misprediction rate).

Prediction computation summary Therefore the prediction computation algorithm is as follows:

1. Find the longest matching component and the alternate component 2. if (the confidence counter is not weak or USE ALT ON NA is negative) then the provider component provides the prediction else the prediction is provided by the alternate component

Updating the TAGE predictor

Update on a correct prediction by the longest marching entry The prediction counter of the provider component is updated. When the prediction is low confidence, the alternate provider is also updated.

Update on a misprediction by the longest matching entry First we update the provider component prediction counter.

As a second step, if the provider component Ti is not the component using the longest history (i.e., i < M ) , we try to allocate entries on predictor, components Tk using a longer history than Ti (i.e., i < k < M ).

For the limited size predictor, for a medium to large number of TAGE tables, allocating two entries on a misprediction is slightly better than allocating a single entry (due to faster warming of the predictor). However, for a 32Kbits predictor, we also found that when the misprediction ratio is high, one should avoid to allocate many entries (avoiding pollution). Therefore we dynamically decide on the number of entries (one or two) to allocate on a misprediction.

For the no-limit predictor, systematically allocating many entries on a misprediction allows to reduce the warmup time of the predictor.

The M-i-1 u j useful bits are read from predictor components Tj, i < j < M . The allocation algorithm chose entries for which the useful bits are null, moreover we guarantee that the entries are not allocated in consecutive tables. When an entry is allocated, its prediction counter is set in weak mode and its useful bit is set to null.

Updating the useful counter u The useful counter u of the provider component is incremented whenever the actual prediction is correct and the alternate prediction altpred is incorrect.

In order to avoid the useful bits to stay forever set, we have to implement a reset policy.

In this Championship, we have used a new variation of the reset policy on the small predictor. On allocation of new entries, we dynamically monitor the number of successes and fails when trying to allocate new entries after a misprediction. This monitoring is performed through a single counter called TICK in the simulator. On a failure, the u counter of the associated entry is probabilistically decremented, the decrement probability increases with the TICK counter value.

For the 256Kbits predictor, we implement the smooth resetting all the u counters proposed in [START_REF] Seznec | A 64 kbytes ISL-TAGE branch predictor[END_REF].

For the no-limit predictor, the replacement policy is not a real issue.

Tag width tradeoff Using a large tag width leads to waste part of the storage while using a too small tag width leads to false tag match detections [START_REF] Seznec | A case for (partially)-tagged geometric history length predictors[END_REF]. Systematic experiments confirmed that using narrower tags on the tables with smaller history lengths leads to the best storage tradeoff.

For the submitted limited size predictors, increasing the tag width by 1 bit on all tables would result in unsignificant accuracy benefit, while decreasing this width results in about 1% misprediction rate increase.

For the no-limit predictor, we set the tag width to 16 for all tables; experiments with larger width did not lead to higher accuracy.

The global history vector For the limited size predictors, the usual combination of the global branch history vector and a short path history (limited to 1 bit per branch) was found to be slightly outperformed by a global history vector introducing much more information for unconditional branches (4 bits per unconditional branch). Using 7 bits per branch would be better, but consumes storage bits. This is used for the no-limit predictor.

The loop predictor component

The loop predictor simply tries to identify regular loops with constant number of iterations.

The implemented loop predictor provides the global prediction when a loop has successively been executed 7 times with the same number of iterations. The loop predictor used in the submission features only 64 entries and is 4-way skewed associative.

Each entry consists of a past iteration count on 10 bits, a retire iteration count on 10 bits each , a partial tag on 10 bits, a confidence counter on 4 bits, an age counter on 4 bits and 1 direction bit i.e. 39 bits per entry. The loop predictor features only a limited number of entries 16 for the 32Kbits predictor and 32 for the 256Kbits predictor.

Replacement policy is based on the age. An entry can be replaced only if its age counter is null. On allocation, age is first set to 7. Age is decremented whenever the entry was a possible replacement target and incremented when the entry is used and has provided a valid prediction. Age is reset to zero whenever the branch is determined as not being a regular loop.

The loop predictor reduces the misprediction rate by approximately 1% for the 256Kbits predictor and 1.2 % for the 32Kbits predictor and only 0.4 % on the no-limit predictor.

Statistical Corrector Predictor

The TAGE predictor is very efficient at predicting very correlated branches even when the correlation is with very remote branches. However TAGE fails at predicting statistically biased branches e.g. branches that have only a small bias towards a direction, but are not strongly correlated with the history path. On some of these branches, the TAGE predictor performs sometimes worse than a simple PC-indexed table of wide counters.

In [START_REF] Seznec | A 64 kbytes ISL-TAGE branch predictor[END_REF][START_REF] Seznec | A new case for the tage branch predictor[END_REF], we introduced the Statistical Corrector predictor to better predict this class of statistically biased branches, The correction aims at detecting the unlikely predictions and to revert them: the prediction flowing from TAGE as well as information on the branch (address, global history, global path, local history) are presented to Statistical Corrector predictor which decides whether or not to invert the prediction. Since in most cases the prediction provided by the TAGE predictor is correct, the Statistical Corrector predictor can be quite small.

32Kbits predictor: The Corrector Filter

For the 32Kbits predictor, only a small storage can be devoted to the statistical corrector, since the benefit of increasing the TAGE predictor size is important. The Corrector Filter is an associative table used to monitor the mispredictions from TAGE. The mispredictions (PC and predicted direction) are stored in the Corrector Filter with a low probability. On a hit on the Corrector Filter, the prediction is inverted if the entry indicates to revert the prediction with a high confidence. Replacement policy favors the replacement of entries with low confidence or which indicate not to invert the prediction.

A 64-entry 2-way skewed associative Corrector Filter is used with a 13-bits entry (6-bit counter + 7-bit tag). As an optimization, high confidence branches flowing from TAGE are not inverted by the Corrector Filter.

The Corrector Filter reduces the overall misprediction rate by about 1.5%.

256Kbits: Multi-GEHL Statistical Corrector Predictor

For the 256 Kbits predictor, we use an enhanced version of the statical corrector predictor introduced in [START_REF] Seznec | A 64 kbytes ISL-TAGE branch predictor[END_REF] and in [START_REF] Seznec | A new case for the tage branch predictor[END_REF].

The Multi-GEHL Statistical Corrector, MGSC, used in the submitted predictor is composed of 6 different components:

• The Bias component: indexed through the PC and the TAGE predicted direction. The Bias component is made of two tables indexed with distinct hashing functions to limit entry conflict impact. The return stack associated branch history work as follows.

History is stored in the same return stack as calls. On a call, the top of the stack is copied on the newly allocated entry in the stack, after the associated return, the branch history reflects the branches that were executed before the call. This allows to capture some correlations that could be lost during the execution of the called function. The benefit of the associated GEHL component is only of 0.7 %. Investing its storage budget in doubling the global history GEHL component would bring back about half of this benefit. The use of two distinct local histories was introduced by [START_REF] Ishii | Revisiting local history for improving fused two-level branch predictor[END_REF]. The benefit of the 2nd local history is marginal (about 0.5 % misprediction reduction). However adding a 3rd local history table with also 16 history entries, with a different hashing function on the local history table induces an extra accuracy benefit in the same range.

All tables are 5 or 6 bit counters. The Bias tables as well the tables with the shorter history of each GEHL component are 6 bits wide, the other tables are 5 bits wide. The prediction is computed as the sign of the sum of the (centered) predictions read on all the Statistical Corrector tables, moreover we integrate the result of the TAGE prediction through adding twice the number of multi-GEHL tables multiplied by the direction (+1,-1).

The MGSC predictor tables are updated using a dynamic threshold policy as suggested for the GEHL predictor [START_REF] Seznec | Analysis of the O-GEHL branch predictor[END_REF]. As suggested in [START_REF] Daniel | Oh-snap: Optimized hybrid scaled neural analog predictor[END_REF], a PC-indexed table of dynamic threshold is used (32 entries), enabling marginal benefit (0.1% misprediction decrease).

The role of the Bias component indexed with the PC and the TAGE output is fundamental. Most branches are correctly predicted in most cases by the TAGE predictor. The associated Bias tables entries tend to saturate on these branches. This allows to use relatively small other components in the MGSC.

The output of MGSC is generally more accurate than the output of the TAGE predictor. However when the output of TAGE is high confidence (see [?]) and the output of MGSC is low confidence (i.e. |sum| < threshold), TAGE is generally a little bit more accurate. Then, in the general case we select the MGSC output, apart when TAGE output is high confidence and MGSC output is low confidence then the prediction is chosen based on 3 counters respectively monitoring the behavior of very low MGSC confidence (|sum| < threshold/3), medium low MGSC confidence(threshold/3 < |sum| < 2 * threshold/3), and high low MGSC confidence (2 * threshold/3 < |sum| < threshold). This simple policy enables about 0.7% misprediction reduction.

In practice, the MGSC used in the submitted 256Kbits predictor features less than a total of approximately 46 Kbits storage bits. It reduces the total misprediction rate by about 6.8%.

Statistical Corrector for the no-limit predictor

For the no-limit predictor, we use a perceptron-inspired [START_REF] Jimenéz | Neural methods for dynamic branch prediction[END_REF] Statistical Corrector, that combines multiple components:

• the Bias component: indexed through the PC and the TAGE predicted direction.

• 4 LGEHL components, 3 using a 16-entry history table, and one using 64K-entry history table. Each one features 15 tables.

• 4 perceptron-derived local history components using similar history tables. In these perceptron-derived components, we use the MAC representation of the counters [START_REF] Seznec | Revisiting the perceptron predictor[END_REF]; a counter is associated with 6 consecutive bits of history. Each of these components features 10 tables.

• 2 perceptron-derived using respectively global history and global path history: 10 tables each.

• a global history GEHL component: 209 tables. The 5 shortest history components are indexed using the TAGE output in the index (¡0.1% gain through this trick).

• a global history component inspired from the MAC-RHSP predictor [START_REF] Seznec | Revisiting the perceptron predictor[END_REF]; a counter is associated with 6 consecutive bits of history and part of the global branch history (1/3) is hashed with the PC: 80 tables.

• Two path skeleton history GEHL components. The first path skeleton are the taken branches which targets are not too close to the branch source. By too close, we mean 16 bytes for backward branches and 128 bytes for forward branches. The second path skeleton registers the branch in the path only if it was not among the last 8 encountered branches. Each of these components features 15 tables.

• Two path skeleton history perceptron-derived components: 10 tables each.

All tables are 8 bit counters, wider counters do not bring any significant benefit (less than 0.1 %). The prediction is computed as the sign of the sum of the (centered) predictions read on all the Statistical Corrector tables: a total of 460 counters are summed.

In practice, we tried every combination of information from the control flow that we expected to have a possible correlation with the direction output; some brought extra accuracy and were retained, others only polluted the prediction and were rejected.

As for 256Kbits, the Statistical Corrector predictor tables are updated using a dynamic threshold policy. [START_REF] Seznec | Analysis of the O-GEHL branch predictor[END_REF] and a PC-indexed table of dynamic threshold [START_REF] Daniel | Oh-snap: Optimized hybrid scaled neural analog predictor[END_REF] is used enabling marginal benefit.

Choosing between TAGE and statistical corrector outputs

The prediction flowing out from the statistical corrector is generally more accurate than the TAGE prediction. However using a chooser results in a slightly better accuracy than just using the statistical corrector output.

The best chooser we have experimented uses a GEHL + LGEHL structure with limited number of tables (i.e. short histories). It is indexed with the PC, the TAGE prediction, the confidence (high or not) of the TAGE prediction, the confidence (high or not ) of the SC prediction.

This chooser marginally outperforms the chooser described for the 256 Kbits predictor (0.005 misp/KI). [START_REF] Seznec | Revisiting the perceptron predictor[END_REF] The submitted limited size predictors

32Kbits TAGE-SC-L predictor

The TAGE component consists in a (4Kbits prediction, 1Kbits hysteresis), 10 tagged tables with respective histories {4, 9, 13, 24, 37, 53, 91, 145, 226, 359}, {256, 256, 256, 256, 128, 256, 128, 64, 64} entries and {7, 7, 7, 8, 9, 10, 10, 11, 13, 13} tag widths and 32 entries USE ON ALT NA and a few counters for a total of 31639 bits.

The loop predictor features 16 39-bits entries, i.e 624 bits.

The corrector filter features 64 13-bits entries, i.e 832 bits.

Including the 359 bits of global branch history, the 27bit global path history, the submitted TAGE-SC-L predictor features a total of 33,465 storage bits.

The 256Kbits TAGE-SC-L predictor

The The loop predictor features 32 39-bits entries, i.e 1,248 bits.

The MGSC features a Bias component with two tables(128 entries each) a global conditional branch history GEHL (2 256-entries + 2 512-entries tables), a return-stackassociated history GEHL (2 256-entries + 1 512-entries tables, a 16-entry history stack), a 256-entries local history GEHL ( 2 512-entries + 1 1024-entries table ) and two 16entry local history GEHL (2 256-entries + 2 512-entries tables). All tables are 5 or 6 bit counters as mentioned in the previous section. It also features a 32 entries dynamic threshold table. Including local history tables, and the three selection counters, the MGSC features a total of 46,809 storage bits.

The submitted 256Kbits TAGE-SC-L predictor features a total of 262,433 storage bits.

Performance analysis of the statistical corrector As already mentioned, the statistical corrector reduces the misprediction rate of the TAGE-L predictor by 6.8% (2.538 MPKI).

If one considers only the three local components (about 30 Kbits total) then the misprediction rate is increased by about by 1.5 % (2.401 MPKI).

If one considers only the global history component and the return-stack associated history (about 15 Kbits total) then the misprediction rate increase by 3.6 % (2.452 MPKI).

If one doubles the size of all the GEHL components in the statistical corrector (i.e. adds about extra 40 Kbits) then the global misprediction rate is decreased by only 1.2 % (2.338 MPKI).

A more realistic 256 Kbits TAGE-SC-L predictor Through uncommenting "#define REALISTIC" on the first line of the predictor.h file of the submission , one gets a more realistic configuration of the TAGE-SC-L predictor with statistical corrector featuring a global branch GEHL (4 tables) and one local history GEHL (4 tables), a TAGE predictor with 12 equal size tagged tables, achieving only 2.7 % extra mispredictions (2.430 MPKI).

In practice, benefits associated with using three local history GEHL components instead of one and the return-stack associated history GEHL component are not worth: less than 1 % of extra mispredictions if one invest the freed storage budget in the remaining components of the statistical corrector.

6 Accuracy analysis of the no-limit TAGE-SC-L predictor

The submitted predictor features many components. We analyze here the benefits of the components in terms of extra mispredictions over the submitted predictor when the component is removed.

Exploring the best configuration

We systematically explored several parameters for finding the best possible configuration. Most tables were dimensioned with 1 million or 1 2 million entries, and we varied the number of tables and the history lengths to find the best configuration. Through this process, we reduce the misprediction rate by only 0.7 %.

The simulator footprint does not exceed 500 Mbytes, tests with larger tables did not result in any visible accuracy benefit.

The TAGE predictor

The TAGE component presented in the submission would observe 23.5 % more mispredictions than the complete predictor. In [START_REF] Seznec | The idealistic gtl predictor[END_REF], we mentioned that the TAGE predictor accuracy saturates around 18-20 tagged components. We verify the same behavior on the distributed traces. The TAGE predictor with only 20 tagged tables observes only 19.5 % extra mispredictions, but the complete predictor with only 20 tagged tables would encounter 0.4 % more mispredictions than the submitted predictor.

However the extra mispredictions due to extra tagged components are essentially captured by the statistical corrector.

Removing the TAGE predictor

If one removes the TAGE predictor from our submission then the predictor becomes a perceptron-inspired predictor exploiting local and global branch/history. This predictor achieves 4.7 % more mispredictions than the submitted predictor.

The loop predictor

Without the loop predictor, the misprediction rate is increased by 0.4 %.

The chooser

Systematically using the SC prediction instead of choosing through our chooser between SC output and TAGE output would result in an accuracy loss of 3.2 %.

The Bias component

The bias component tends to record the statistical bias of the output of TAGE on branch B and a predicted direction D. That is when branch B is predicted in a direction D and it has been observed that in most similar cases, B was mispredicted then the bias component will indicate to revert the prediction.

Removing the use of the TAGE output in the index of the bias component would change our submission in a more classical hybrid predictor, it would also result in an increase of 1.6 % more mispredictions: this is the most influent single table in the set of 460 tables of the statistical corrector.

Local history components

Ignoring local history in the statistical corrector would result in a 3.9% increase of the total misprediction rate. Further eliminating the use of local history from the chooser has no significant impact (4.1%).

Using several local histories Using several local history tables is beneficial. Using a single local history with 32Kentry history table would result in an accuracy loss of 1.7 %. The use of several distinct local histories was introduced by [START_REF] Ishii | Revisiting local history for improving fused two-level branch predictor[END_REF]. In practice, 3 16-entry local history table sizes indexed with different hashing functions, we divide the con flow sttsome correlation between branches that would map on a single entry of 16-entry history table.

Perceptron-derived local history components Removing the perceptron-derived local history components would result in a 0.4 % increase of the misprediction rate.

Local history GEHL components Removing the local history GEHL components would result in a 1.3 % increase of the misprediction rates.

The global history/path components

Several global history components are used in the SC predictor. Globally removing these components results in an accuracy loss of 3.7%.

However, removing only one of them has small impact on accuracy as listed below, that is these components are essentially capturing the same kind of correlation.

The long history components Removing only the global history GEHL component from our submitted predictor would result in 0.3 % more mispredictions. Removing the MAC-RHSP derived component would result in an increase of 0.25 % of the misprediction rate. Removing both components results in an increase of 1.8 % of the mispredictions, that is the MAC-RHSP component and the GEHL component are essentially capturing similar correlation on branch outputs.

The perceptron-derived global history and global path components Removing these two components results in an insignificant increase of 0.1 % of the misprediction rate.

Skeleton path history components

Removing only the skeleton path history components would result in a marginal 0.4 % increase of the misprediction rate.

However, if we remove all the global branch/path history components and the skeleton path history components then a 5.1 % misprediction rate increase is encountered. This shows that the skeleton path history components essentially capture correlations that are also captured by the global history components.

Comparison with the GTL predictor

The GTL predictor [START_REF] Seznec | The idealistic gtl predictor[END_REF] was the most accurate published "unlimited storage size" predictor so far. The TAGE-SC-L significantly outperforms it due to several reasons: 1) use of alternate forms of global history components (MAC-RHSP component, perceptron-inspired components), 2) introduction of local history components 3) use of the Bias component.

However TAGE-SC-L achieves about 5% more mispredictions than the poTAGE-SC predictor submitted to same championship [START_REF] Michaud | Pushing the branch predictability limits with the multi-potage+sc predictor[END_REF].

Conclusion

The TAGE-SC-L predictor can be adapted to various predictor storage budgets.

For small storage budgets (e.g. 32Kbits), large accuracy benefits is obtained through increasing the number or the sizes of the TAGE tagged tables, therefore only very small loop predictors and statistical correctors can be used.

For larger storage budgets, the adjunct predictors can implement more complex schemes as illustrated by the multi-GEHL statistical corrector used for the 256 Kbits predictor.

The submitted predictors were optimized to achieve the ultimate accuracy at the fixed storage budgets of the championship. This leads to use unrealistic number of tables, different predictor table sizes, tag widths and different schemes in the multi-GEHL statistical corrector. However, simpler designs with storage budgets in the same range, but using much smaller number of tables would achieve prediction accuracy in the same range (less than 3 % extra mispredictions).

Using the TAGE-SC-L scheme with a quasi unlimited budget allows to reach substantially better accuracy than the one of the 256Kbits predictor (more than 20 % less mispredictions). However this is achieved through using a particularly unrealistic number of components in the predictor and trying to exploit all forms of branch and path history that we could imagine.

Figure 1 .

 1 Figure 1. The TAGE-SC-L predictor: a TAGE predictor backed with a Statistical Corrector predictor and a loop predictor

Figure 2 .

 2 Figure 2. The TAGE predictor synopsis: a base predictor is backed with several tagged predictor components indexed with increasing history lengths

  -bit USE ON ALT NA counters and a few counters. This leads to a total of 214,376 bits including the 1347 bits of global branch history, and the 27-bit global path history.

		TAGE	component	consists	in	a
	(16Kbits	prediction,	4Kbits	hysteresis),	15
	tagged tables with respective history lengths
	{6, 10, 18, 25, 35, 55, 69, 105, 155, 230, 354, 479, 642, 1012,
	1347}, with {1K, 1K, 1K, 2K, 1K, 1K, 1K, 1K, 1K, 512,
	512, 512, 256, 128, 128}		entries	and
	{7, 9, 9, 9, 10, 11, 11, 12, 12, 12, 13, 14, 15, 15, 15}	tag
	widths and 2x256 entries 5

* This work was partially supported by the European Research Council Advanced Grant DAL No 267175 (Main) TAGE Predictor Stat.

Cor.