domain: math phys

text:
Grégoire Sergeant-Perthuis
email: gregoireserper@gmail.com

Characterization of extreme Gibbs measures for a Categorical Approach to Statistical Mechanics

Keywords: Statistical mechanics, category theory, Extreme Gibbs measures, Zero-one laws MSC: 18D99, 60F20, 60A99

In recent work we proposed to follow a categorical approach to Statistical Mechanics. In this paper we continue in this direction and give a categorical formulation of the decomposition of Gibbs measures by extending the characterization of extreme Gibbs measures to the categorical setting.

Introduction

Statistical Mechanics is the field interested in the statistical study of interacting particles (X i ∈ E i , i ∈ N). A landmark rigorous formulation of Statistical Mechanics can be found in Georgii's Gibbs Measures and Phase Transition [START_REF] Georgii | Gibbs Measures and Phase Transitions[END_REF]. Such a framework is needed to define phases or, more generally, Gibbs measures of statistical systems. Phases only exist for infinitely many interacting particles and do not exist for finite-size systems. The main constructions of such a framework rely on the necessity to have a universe, denoted Ω, that encompasses all possible configurations of the system, i.e., all the possible joint configurations of the particles Ω := i∈N E i . Not referring to a global space is problematic as exhibited by Giry's seminal work on A Categorical Approach to Probability Theory [START_REF] Giry | A categorical approach to probability theory[END_REF] and can be summarized by the fact that the Giry monad, P, does not commute to limits. We are interested in describing statistical systems for which it is not possible to have complete knowledge of the states of the particles at the same time; we want to forget about the 'Ω' and we want to study statistical systems 'locally'.

In [START_REF] Sergeant-Perthuis | A categorical approach to statistical mechanics[END_REF][START_REF] Sergeant-Perthuis | Intersection property, interaction decomposition, regionalized optimization and applications[END_REF], we proposed to reformulate Statistical Mechanics and Gibbs measures introducing an appropriate category. Among others, in [START_REF] Sergeant-Perthuis | Interaction decomposition for presheaves[END_REF], we gave a characterization of independent variables in terms of projective objects in this category and an easy-to-verify condition that characterizes such objects (for the injective case see [START_REF] Sergeant-Perthuis | Bayesian/graphoid intersection property for factorisation spaces[END_REF][START_REF] Sergeant-Perthuis | Intersection property and interaction decomposition[END_REF][START_REF] Sergeant-Perthuis | Interaction decomposition for hilbert spaces[END_REF][START_REF] Bennequin | Extra-fine sheaves and interaction decompositions[END_REF]). In [START_REF] Sergeant-Perthuis | Regionalized optimization[END_REF], we proposed an Entropy functional for the categorical version of statistical systems. In this article, we show how the characterization of extreme Gibbs measures (Theorem 7.7 [START_REF] Georgii | Gibbs Measures and Phase Transitions[END_REF]), one of the steps for proving a zero-one law for the extreme Gibbs measures, transfers in the categorical setting. In the classical theory of rigorous statistical mechanics, the tail σ-algebra generates the observables for which a 'generalized' law of large numbers (zero-one law) holds. In this article, we give a candidate for such a σ-algebra in the categorical setting and show the associated extreme Gibbs measures decomposition. We will discuss in a follow-up paper the generalization of the zero-one law of specifications to A -specifications.

A -specifications and their Gibbs measures

In classical theory, a statistical system is defined by a specification (Definition 1.23 [START_REF] Georgii | Gibbs Measures and Phase Transitions[END_REF]). We proposed in [START_REF] Sergeant-Perthuis | A categorical approach to statistical mechanics[END_REF][START_REF] Sergeant-Perthuis | Intersection property, interaction decomposition, regionalized optimization and applications[END_REF] to reformulate such constructions as a couple of a presheaf and a functor over a poset, denoted as A ; we call such a couple an A -specification. Let us recall their definition. Let us denote Mes the category that has as objects measurable spaces and as morphisms measurable maps, and Kern the category that has as objects measurable spaces and as morphisms Markov kernels. Definition 2.1 (A -specifications (Definition 7 [START_REF] Sergeant-Perthuis | A categorical approach to statistical mechanics[END_REF])). Let A be a poset. An A -specification is a couple (G, F ) of a presheaf and a functor G : A op → Mes and F : A → Kern such that for any a, b

∈ A with b ≤ a, G a b • F b a = id (1)
We denote α • β simply as αβ in what follows.

Let us now recall the categorical generalization of the classical Gibbs measures (Definition 1.23 [START_REF] Georgii | Gibbs Measures and Phase Transitions[END_REF]) that we propose. Definition 2.2 (Gibbs measure for A -specifications Definition 8 [START_REF] Sergeant-Perthuis | A categorical approach to statistical mechanics[END_REF]). Let γ := (G, F ) be an A -specification,

G (γ) := {(p a ∈ P(G(a)), a ∈ A )|∀b ≤ a, F b a p b = p a } (2)
with P(G(a)) the (measurable) space of probability measures over G(a).

Categorical Version of the Tail σ-Algebra

Measurable maps are particular Markov kernels. Let F : E b → E a be a Markov kernel; let us denote it also as F (ω a |ω b ), where ω b ∈ E b and ω a ∈ E a .

One associates to a Markov kernel F :

E b → E a a linear map π : L ∞ (E a ) → L ∞ (E b ) defined as follows: for any f ∈ L ∞ (E a ), ∀ω b ∈ E b , π(f )(ω b ) = f (ω a )F (dω a |ω b ) (3)
This association is 'functorial', we may denote the underlying functor L ∞ : Kern op → Vect which is presheaf from the category of Markov kernels to the category of vector spaces. It is the presheaf that associates spaces to their space of observables. Let us denote

L ∞ • G : A → Vect as i and L ∞ • F : A op → Vect as π. In these notation one has that for any a, b ∈ A such that b ≤ a then π a b • i b a = id.
Let us recall the definition of the tail σ-algebra in the classical formulation. Let Ω = i∈N E i , where E i are measurable spaces; let us denote F ≥k as the σ-algebra generated by the cylinders n≥k E k . The tail σ-algebra is defined as k∈N F ≥k . A more general definition holds when I is any set and F ⊇a is indexed by a subset a ⊆ I that is co-finite, i.e., which has a finite complement. For a functor from A to Mes, let us denote σ(G(a)) as the sigma algebra of the measurable space G(a), where a ∈ A , and σ(G) as the underlying functor defined as

σ(G) b a A b := G a b -1 A b , with b ≤ a.
We propose that one candidate that plays the role of the tail σ-algebra for a given specification γ = (G, F ) is lim σ(G) defined as,

lim σ(G) := {(A a ∈ σ(G(a)), a ∈ A )|∀a, b ∈ A , A a = G a b -1 A b } (4)
Let us denote 1 A : E → {0, 1} the indicator function over the set A that sends ω ∈ A to 1 and ω ∈ A to 0. Let us remark that

1 A b • G a b = 1[G a b (ω a ) ∈ A b ] = 1 G a b -1 A b . Remark that A ∈ lim σ(G) is equivalent to 1 A ∈ lim i; in other words, lim σ(G) is the restriction of lim i to indicator functions of the form 1 Aa , a ∈ A .
Finally, we also need to recall that for any f ∈ L ∞ (E) and µ ∈ P(E), one can define a measure f

• µ as f • µ(dω) = f (ω)dω.
The key proposition of this document is Proposition 3.1; the proof of that proposition is given for G(a), a ∈ A finite measurable sets. Therefore, we assume in what follows that the measurable sets are finite. However, there is no finiteness constraint on A . We will say that F > 0 when for any

a, b ∈ A , such that b ≤ a, F (ω a |ω b ) > 0 for any ω b such that G a b (ω a ) = ω b ; G • F = id requires that F (ω a |ω b ) = 0 when G a b (ω a ) = ω b .
The following lemma is an extension of the classical result that states that conditioning over a σ-subalgebra F 1 ⊆ F defines a morphism of modules when finer (F measurable) observables are seen as modules over the coarser (F 1 measurable observables). Lemma 3.1. Let E 1 , E 2 be two measurable spaces, let g : E 2 → E 1 be a measurable map and f : E 1 → E 2 be a Markov kernel so that, f • g = id. Let us denote respectively i and π the induced linear maps on

L ∞ (E 1 ), L ∞ (E 2 ). Let h ∈ L ∞ (E 2 ) and k ∈ L ∞ (E 1 ), then, π(h).k = π(h.i(k)) (5)
Proof. Let us first prove the result in the particular case when

h = 1 B with B ∈ σ(E 2 ) and k = 1 A with A ∈ σ(E 1 ). Let us denote A the complement of A, then 1 A + 1 A = 1 and 1 A .1 A = 0. Furthermore i(1 A ) = g -1 A π(1 B ) = π(1 B .1 g -1 A ) + π(1 B .1 g -1 A ) (6)
and

π(1 B .1 g -1 A ) ≤π(1 g -1 A ) = π • i(1 A ) = 1 A (7) π(1 B .1 g -1 A ) ≤π(1 g -1 A ) = 1 A (8)
Therefore,

π(1 B )1 A = π(1 B .1 g -1 A )1 A + π(1 B .1 g -1 A )1 A (9) But, π(1 B .1 g -1 A )1 A ≤ 1 A .1 A = 0 so, π(1 B )1 A = π(1 B .1 g -1 A )1 A . Fur- thermore, π(1 B .1 g -1 A ) = π(1 B .1 g -1 A )1 A + π(1 B .1 g -1 A )1 A therefore, π(1 B .1 g -1 A )1 A ≤ π(i(1 A )).1 A = 0 (10)
We just showed that,

π(1 B .1 g -1 A ) = π(1 B .1 g -1 A )1 A (11) So π(1 B ).1 A = π(1 B .i(1 A )).
The result then extends by linearity directly to h = k≤n 1 B k and k = k≤n 1 1 An , which ends the proof.

Let us remark that if

A ∈ lim σ(G) then A := (A a , a ∈ A ) is also in lim i. Proposition 3.1. Let γ = (G, F ) be a specification, let G(a) be finite sets for any a ∈ A , let F > 0. Let µ ∈ G (γ), for any f ∈ a∈A L ∞ (G(a)), such that ∀a ∈ A , µ a (f a ) = 1, f.µ ∈ G (γ) ⇐⇒ ∃ f ∈ lim i, s.t. f.µ = f .µ (12)
Proof. Let us assume that f.µ ∈ G (γ), then for any a, b ∈ A such that b ≤ a, and for any g a ∈ L ∞ (G(a)), by hypothesis, (f.µ) b π a b (g a ) = (f.µ) a (g a ); it can be rewritten as,

µ b (π a b (g a ).f b ) = µ a (f a .g a ) (13) By Lemma 3.1, π a b (g a ).f b = π a b (g a .i b a f b ); therefore, µ b π a b (g a .i b a f b ) = µ a (f a .g a ) (14)
Therefore f a = i b a f b µ a -almost surely. We will now show that there is f ∈ lim i such that f .µ = f.µ. It is in this part of the proof that we assume that G(a) are finite sets and that F > 0. Let's call S a := suppµ a , the support of µ a , i.e., the set suppµ a := {ω a ∈ G(a)|µ a (ω a ) > 0}. Let us denote N a := S a its complement and M a = 1 Na . We will now show that (N a , a ∈ A ) ∈ lim σ(G).

For any b, a

∈ A such that b ≤ a, µ a i b a = µ b ; therefore, as µ b (M b ) = 0, one has that µ a i b a (M b ) = 0. Recall that i b a (M b ) is the indicator function of the set G a b -1 N b ; the previous remark implies that i b a (M b ) ≤ M a . Furthermore, µ b π a b (M a ) = µ a (M a ) = 0; therefore, π a b (M a ) ≤ M b . Hence, as π a b (i b a M b ) = M b and i b a M b ≤ M a , then by applying π a b on both sides, M b ≤ π a b (M a ). And so π a b (M a ) = M b . Recall that we showed that π a b (M a ) = M b and i b a (M b ) ≤ M a . In partic- ular, M a -i b a (M b ) ≥ 0; furthermore, π a b (M a -i b a (M b )) = 0 so M a = i b a (M b ). To be more explicit: ∀ω b ∈ G(b), π a b (M a -i b a (M b ))(ω b ) = ωa∈G(a) F (ω a |ω b )[M a -i b a (M b )](ω a ) (15)
As F (ω a |ω b ) > 0 by hypothesis, then M a = i b a (M b ). This implies that M ∈ lim i and N ∈ lim σ(G). This also implies that S ∈ lim σ(G).

Let f = f 1 S . Then f 1 S ∈ lim F and for any a ∈ A , f a = fa µ a -a.s., which ends the proof.

One remarks that lim i is a subset of lim π: for any f ∈ lim i, by definition for any a, b

∈ A such that b ≤ a, i b a f b = f a and so π a b i b a f b = π a b f a so f b = π a b f a . Let us also remark that for any b ≤ a ∈ A , µ a (A a ) = µ b (A b ) for µ ∈ G (γ), A ∈ lim G.
Theorem 3.1 (Extreme measure characterisation (Generalisation of Theorem 7.7 [START_REF] Georgii | Gibbs Measures and Phase Transitions[END_REF]) ). Let γ = (G, F ) be a specification, let G(a) be finite sets for any a ∈ A , let F > 0. G(γ) is a convex set. Each µ ∈ G (γ) is uniquely determined by it's restriction to lim σ(G). Furthermore µ is extreme in G (γ) if and only if for any A ∈ lim σ(G), ∀a ∈ A , µ a (A a ) = 0 or 1.

Proof. Let us denote π * the functor from A to Vect for which for any b ≤ a, π * b a : (L ∞ F (b)) * → (L ∞ F (a)) * is the dual of π a b that send linear forms to linear forms. Then G (γ) is a subspace of the vector space lim F * and furthermore for any a ∈ A and p ∈ [0, 1], pµ a + (1p)ν a ∈ P(G(a)) whenever µ a , ν a ∈ P(G(a)). Therefore G (γ) is a convex set. Proposition 3.1, allows us to apply a similar proof, when done with caution, to the one found of Theorem 7.7 in [START_REF] Georgii | Gibbs Measures and Phase Transitions[END_REF]. Let us recall the proof. Let µ, ν ∈ G(γ) such that µ | lim i = ν | lim i . Let µ = µ+ν 2 , then µ ∈ G (γ). But µ and ν are absolutely continuous with respect to µ therefore for any a ∈ A there is f a , g a ∈ L ∞ (G(a)) such that µ a = f a µ a and ν a = g a µ a . By Proposition 3.1, f, g ∈ lim i. By hypothesis, for any h

∈ lim i µ a (h a ) = µ a (h a ) = ν a (h a ). Im- portantly i b a is a ring morphism of L ∞ (G(b)), i.e. i b a (k b .h b ) = i b a (k b ).i b a (h b ). Therefore for any h, k ∈ lim i, k.h ∈ lim i; as f -g ∈ lim i, then it is also the case that (f -g) 2 ∈ lim i; but for any a ∈ A , µ a [(f a -g a ) 2 ] = 0 (16) so f a = g a µ a -a.s. Therefore f µ = gµ and µ = ν. Showing that µ ∈ G (γ) is extreme is equivalent to µ being trivial on lim i is a direct generalization of Corollary 7.4 [1] thanks to Proposition 3.1. Let µ ∈ G (γ) be not trivial on lim σ(G) then there is A = (A a , a ∈ A ) ∈ lim σ(G) such that, ∀a ∈ A , 0 < µ a (A a ) < 1 (17)
Therefore for any a ∈ A ,

µ a = µ a (A a ) 1 Aa .µ a µ a (A a ) + µ a (A a ) 1 Aa .µ a µ a (A a ) (18)
Furthermore, for any b ≤ a,

i b a 1 A b µ a (A b ) = 1 Aa µ a (A b ) = 1 Aa µ a (A a ) (19)
Therefore 1 Aa µa(Aa) , a ∈ A is in lim i and so by Lemma 3.1, 1 Aa .µa µa(Aa) , a ∈ A ∈ G (γ). Similarly 1 A a .µa µa(Aa) , a ∈ A ∈ G (γ). In particular there is 0 < p < 1 so that µ = pν + (1p)ν 1 with ν, ν 1 ∈ G (γ). Therefore µ is not an extreme measure.

Assume now that µ ∈ G (γ) is such that for any A ∈ lim σ(A), and any a ∈ A , µ a (A a ) = 0 or 1. Suppose that there is 0 < p < 1 such that µ = pν + (1p)ν 1 with ν, ν 1 ∈ G (γ). Then for any a ∈ A , ν a , ν 1a is absolutely continuous with respect to µ a . Therefore, there are (f a ≥ 0, a ∈ A ), (g a ≥ 0, a ∈ A ) both in a∈A L ∞ (G(a)) such that ν = f µ and ν 1 = gµ. As ν, ν 1 ∈ G (γ), then by Lemma 3.1, f, g ∈ lim i. Therefore, for all a ∈ A , µ a (f a ) = 0 or for all a ∈ A , µ a (g a ) = 0. So, µ = ν or µ = ν 1 and µ is extreme in G (γ).

  Let us remark that if A has only one connected component, then forA ∈ lim σ(G), satisfying ∀a ∈ A , µ a (A a ) = 0 or 1 is equivalent to ∃a ∈ A , µ a (A a ) = 0 or 1. Indeed, ifa, b are in the same connected component, i.e., a ≤ b or b ≤ a, then µ a (A a ) = µ b (A b ).


Pablo De Oliveira Castro
email: pablo.de-oliveira-castro@cea.fr

St Éphane Louise
email: stephane.louise@cea.fr

Denis Barthou
email: denis.barthou@inria.fr

Design-Space Exploration of Stream Programs through Semantic-Preserving Transformations

Stream languages explicitly describe fork-join parallelism and pipelines, offering a powerful programming model for many-core Multi-Processor Systems on Chip (MPSoC). In an embedded resource-constrained system, adapting stream programs to fit memory requirements is particularly important.

In this paper we present a design-space exploration technique to reduce the minimal memory required when running stream programs on MPSoC; this allows to target memory constrained systems and in some cases obtain better performance. Using a set of semantically preserving transformations, we explore a large number of equivalent program variants; we select the variant that minimizes a buffer evaluation metric. To cope efficiently with large program instances we propose and evaluate an heuristic for this method.

We demonstrate the interest of our method on a panel of ten significant benchmarks. As an illustration, we measure the minimal memory required using a multi-core modulo scheduling. Our approach lowers considerably the minimal memory required for seven of the ten benchmarks.

INTRODUCTION

The recent low-consumption Multi-Processors Systems on Chip (MPSoC) enable new computationintensive embedded applications. Yet the development of these applications is impeded by the difficulty of efficiently programming parallel applications. To alleviate this difficulty, two issues have to be tackled: how to express concurrency and parallelism adapted to the architecture and how to adapt parallelism to constraints such as buffer sizes and throughput requirements.

Stream programming languages [START_REF] Gordon | A stream compiler for communication-exposed architectures[END_REF][2] [START_REF] Aussaguès | Using multi-core architectures to execute high performance-oriented real-time applications[END_REF] are particularly adapted to describe parallel programs. Fork-join parallelism and pipelines are explicitly described by the stream graph, and the underlying data-flow formalism enables powerful optimization strategies.

As an example, the StreamIt [START_REF] Gordon | A stream compiler for communication-exposed architectures[END_REF] framework defines transformations of dataflow programs enhancing parallelism through fission/fusion operations. These transformations are guided by greedy heuristics. However, to our knowledge, there is no method for the systematic exploration of the design space based on the different expressions of parallelism and communication patterns. The main difficulty comes from the definition of a space of semantically equivalent parallel programs and the complexity of such exploration.

In this paper we propose a design space exploration technique that generates, from an initial program, a set of semantically equivalent parallel programs, but with different buffer, communication and throughput costs. Using an appropriate metric, we are able to select, among all the variants, the one that best fits our requirements. We believe that our approach is applicable to buffer, communication and throughput requirements, yet in this paper we only consider memory requirements. Study of the other requirements will be the object of future works.

The buffer requirements of stream programs depend not only on the different rates of its actors but also on the chosen mapping and scheduling. We demonstrate the memory reduction achieved by our technique using the modulo scheduling execution model. Kudlur and Mahlke [START_REF] Kudlur | Orchestrating the execution of stream programs on multicore platforms[END_REF] use modulo scheduling to minimize the throughput when mapping stream programs on a multi-core processor. Choi et al [START_REF] Choi | Stream compilation for real-time embedded multicore systems[END_REF] extend this method to cope with memory and latency constraints. They introduce the Memory-constrained Processor Assignment for minimizing Initialization Interval(MPA-ii) problem which we review on section 5. As an illustration we show that combining our exploration method with S J c2 p2 c1 p1 Fig. 1. The split node S alternatively outputs p1 then p2 elements on the two edges, while the join node J takes alternatively c1 and c2 elements from its incoming edges.

MPA-ii achieves memory reductions as high as 80%. Yet our exploration method could also be applied to other scheduling and mapping techniques, it is not particularly tied to MPA-ii.

The contributions of this paper are:

• a theoretical framework to check if a stream program transformation is valid;

• a general set of valid stream transformations;

• a terminating exhaustive search algorithm for the implementation space generated by the above transformation set;

• an heuristic based on graph partitioning to explore very large program instances;

• a design space exploration that minimizes memory requirements on a large set of programs. Section 2 presents the data-flow formalism used. The transformations modifying the granularity of the elements of our program and producing semantically equivalent variants are described in Section 3. Section 4 presents the exploration algorithm built upon these transformations and the algorithm termination proof. Section 5 reviews the MPA-ii problem [START_REF] Choi | Stream compilation for real-time embedded multicore systems[END_REF] that we use to illustrate the benefits of our exploration method and section 6 presents a buffer size metric evaluation. In Section 7 we present our experimental methodology and our results. Finally, Section 8 presents related works.

FORMALISM

In our approach a program is described using a cyclo-static data flow (CSDF) graph where edges represent communications and nodes are either data reorganization operations or computation filters.

Nodes represent the CSDF actors, the node label indicates the node kind (sometimes followed by a number to allow easy referencing); edges denote inputs and outputs. When necessary, the node productions or consumptions are indicated on their associated edges. As an example consider figure 1: a split node with productions (p 1 , p 2 ) is connected to a join node with consumptions (c 1 , c 2 ).

Our stream formalism is very close to Streamit [START_REF] Gordon | A stream compiler for communication-exposed architectures[END_REF]; we consider the following set of nodes:

Input and Output nodes

Source I(l): a source models a program input. It has an associated size l. The source node is fired only once and writes l elements to its single output. If all the elements in the source are the same, the source is constant and denoted by the node C(l).

Sink O: a sink models a program output. It consumes all elements on its single input. If we never observe the consumed elements, we say the sink is trash and we write the node T.

Splitter and Joiner nodes

Splitter and joiners correspond to the expression of data parallelism and communication patterns. Join round-robin J(c 1 . . . c n ) : a join round-robin has n inputs and one output. We associate to each input i a consumption rate c i ∈ N ⋆ . The node fires periodically. In its k th firing the node takes c u , where u = (k mod n) + 1, elements on its u th input and writes them on its output. As in a classic CSDF model, nodes only fire when there are enough elements on their input. When the node has consumed elements on all its inputs, it has completed a cycle and starts all over again. Split round-robin S(p 1 . . . p m ) : a split round-robin has m outputs and one input. We associate to each output j a production rate p j ∈ N ⋆ . In its k th firing the node takes p v , where v = (k mod m)+1, elements on its input, and writes them to the v th output. Duplicate D(m) has one input and m outputs. Each time this node is fired, it takes one element on the input and writes it to every output, duplicating its input m times.

Filters

A filter node F(c 1 . . . c n , p 1 . . . p m ) has n inputs and m outputs. To each input i is associated a consumption rate c i , and to each output j a production rate p j . The node is associated to a pure function f computing from n inputs m outputs. The node fires when for each input i there is at least c i available elements.

Schedulability

We can schedule a CSDF graph in bounded memory if it has no deadlocks (it is live) and if it admits a steady state schedule (it is consistent) [6][7].

A graph is live when no deadlocks can occur. A graph deadlocks if the number of elements received by any sink remains bounded no matter how much we increase the size of the sources.

A graph is consistent if it admits a steady state schedule, that is to say a schedule during which the amount of buffered elements between any two nodes remains bounded. A consistent CSDF graph G with N G nodes admits a positive repetition vector q G = [q 1 , q 2 , . . . , q N G ] where q i represents the number of cycles executed by node i in its steady state schedule. Given two nodes u, v connected by edge e. We note β(e) the elements exchanged on edge e during a steady state schedule execution. If node u produces prod(e) elements per cycle on edge e and node v consumes cons(e) elements per cycle on edge e, β(e) = prod(e) × q u = cons(e) × q v (1)

SEARCH SPACE

In this section we present the transformations that are used to generate semantically preserving variants of the input program. In sec. 3.1 we define what is a semantically preserving (or admissible) transformation. In sec.3.2 we present a set of useful and admissible transformations.

The graph transformation framework presented here follows the formulation given in [START_REF] Andries | Graph transformation for specification and programming[END_REF]. A transformation T (fig. 2) applied on a graph G and generating a graph

G ′ is denoted G T -→ G ′ .
It is defined by a matching subgraph L ⊆ G, a replacement graph R ⊆ G ′ and a glue relation g that binds the frontier edges of L (edges between nodes in L and nodes in G\L) to the frontier edges of R.

The graph transformation works by deleting the match subgraph L from G thus obtaining G\L. After this deletion, all the edges between G\L and L are left dangling. We then use the glue relation to paste R into G\L obtaining G ′ .

A sequence of transformations applied to a graph define a derivation: Definition 1: A derivation of a graph G 0 is a chain of transformations that can be applied successively to G 0 : G 0 T0 -→ G 1 . . . Tn --→ . . ..

Admissible transformations

In this section we define formally the properties that a transformation must possess to preserve the semantic of a program. In lemma 1, we also give a sufficient condition for a transformation to be semantically preserving. We suppose without loss of generality that our stream graphs are connex.

The ordered stream of tokens for a given edge e defines the trace of the edge, denoted t(e). We consider a prefix order ≤ on traces:

x ≤ y ⇒ (x infinite ∧ x = y) ∨ (x = y[0 .. x -1]). We also extend ≤ for tuples: u ≤ v ⇒ ∀k, u[k] ≤ v[k].
Sink and Source nodes have a single edge, thus with no ambiguity, we will consider that the trace of a Source or Sink node is the trace of its unique edge. The input traces and output traces are defined respectively as

I(G) = [t(i) : i ∈ Sources] and O(G) = [t(o) : o ∈ Sinks].
I(G) = I(G ′ ) ⇒ O(G) ≤ O(G ′ ) (2) G is consistent ⇒ G ′ is consistent (3) G is live ⇒ G ′ is live (4)
I(G) = {a, b, c, d, e} O(G) = {a, b, c, d} ≤ O(G ′ ) = {a, b, c, d, e} i1 o1 S J 2 2 2 2 ⇒ i ′ 1 o ′ 1 Fig. 3.
Example of a transformation that is only possible under the weak condition of eq.2

In other words, T preserves the semantics of G if T preserves consistency, liveness and if for the same inputs, the graph generated by T , G ′ , produces at least the same outputs as G. We show in lemma 1 proof, that (2) ⇒ (4). This weak definition of semantics preservation defines a large class of admissible transformations. If we had enforced a strict preservation of the output (O(G) = O(G ′ )), some of the transformations presented in section 3.2 would not be possible. Indeed these transformations relax the communication rates to achieve simplifications. Take for example the transformation in figure 3, the split and join nodes seem useless since they do not change the order of the elements, yet they impose that elements are always consumed in pairs. If we simplify this pattern, this property is no longer true: the input will not be truncated to an even size; nevertheless except for the last element the output of G and G ′ will be the same. This transformation is not possible with the strict condition (O(G) = O(G ′ )) but accepted with our weak condition (cf. eq. ( 2)). If the residual elements are not wanted, each output of the graph can be truncated (since the size of the original output is statically computable in the CSDF model), therefore restoring the strict condition.

We would like to determine if a transformation is admissible examining only local properties of the transformation, that is to say looking only at the match L and replacement R subgraphs, not at G\L. For this we propose the following lemma.

Lemma 1 (Local admissibility):

If a transformation G T -→ G ′ verifies ∃b ∈ N, ∀I(L) = I(R) ⇒ O(L) ≤ O(R) (5)
⇒ max(O(R) -O(L)) ≤ b (6) L is consistent ⇒ R is consistent (7)
then the transformation is admissible. Proof:

(5) ⇒ (2): Using a result from [START_REF] Panangaden | The expressive power of indeterminate dataflow primitives[END_REF] we prove that the graphs in our model are monotonic, that is to say given two sets of input traces for a same graph I 1 (G), I 2 (G) and their associated output

traces O 1 (G), O 2 (G), I 1 (G) ≤ I 2 (G) ⇒ O 1 (G) ≤ O 2 (G).
Using the monotonicity of L,R,G\L and G ′ \R, we prove (5) ⇒ (2).

( 3) is true. We suppose thus that L, R and G are consistent, we'll prove that G ′ is consistent. If there is no cycle between the outputs of R and the inputs of R (through F ≡ G ′ \R), the consistency of G ′ is trivial to prove. Without loss of generality, we will thus suppose that L and R have exactly one input edge and one output edge, which are connected through

)(6)(7) ⇒ (3): If L is not consistent, then G is not consistent and ( 5
F ≡ G\L ≡ G ′ \R, as in figure below. L F ⇒ R F
We will note l(x) the length of the output trace produced by subgraph L for an input trace of length x. We define in the same way r(x) for subgraph R and f (x) for subgraph F .

Let note c L and p L the consumptions and productions for L during an execution of a steady state, which exists because L is consistent. This is also true of R and F .

We thus have:

∀k, l(k.c L ) = k.p L (8) ∀k, r(k.c R ) = k.p R (9) ∀k, f (k.p L ) = k.c L (10)
If we execute p L times the steady state schedule of subgraph R, we'll get an output sequence of length

O(R) = r(p L .c R ) = p L .p R . The output of R is the input of F in G ′ , thus O(F ) = f (O(R)) = f (p L .p R ) = p R .c L .
We notice that in this scenario, both F and R consume a multiple of their steady state consumption, thus they observe a steady state schedule.

To prove that this scenario is indeed possible, and thus that G ′ admits a steady state schedule, we must show that:

O(F ) = I(R) ⇔ p L .c R = p R .c L (11)
We derive:

(8) ⇒ l(c L .c R ) = p L .c R (12) (9) ⇒ r(c L .c R ) = c L .p R ( 13
) (5) ⇒ ∃n 1 , r(c L .c R ) = l(c L .c R ) + n 1 = p L .c R + n 1 ( 14
) (5) ⇒ ∀k, ∃n k , r(k.c L .c R ) = k.p L .c R + n k (15) (6) ⇒ ∀k, n k ≤ b (16)
Because both k.c L .c R and c L .c R are multiples of the steady state consumptions of R we can write: 16)

∀k, k.r(c L .c R ) = r(k.c L .c R ) ∀k, k.(p L .c R + n 1 ) = k.p L .c R + n k by (14)(15) ∀k, k.n 1 = n k ∀k, k.n 1 ≤ b by (
n 1 = 0 and ∀k, n k = 0 (17)
Thus, (17)(14)(13) ⇒ (11), and the result follows.

(2) ⇒ (4): If G is not live (4) is true. We suppose G live, thus increasing the length of I(G) we can produce an O(G) as long as we want.

Suppose that

G ′ deadlocks. If G ′ deadlocks its output trace O(G ′ ) is bounded: ∃c, ∀I(G ′ ), O(G ′ ) ≤ c. By (2), we get: ∀I(G), O(G) ≤ O(G ′ ) ≤ c.
This contradicts the G liveness hypothesis, therefore (2) ⇒ (4).

Because we have proved in a), that (5) ⇒ (2), by transitivity (5) ⇒ (4).

In the following we will describe a set of transformations preserving graph semantics. The match and replacement graphs are given for each transformation in figure 4. The input and output edges are denoted i x and o y in both graphs. The natural correspondence between the i x (resp. o y ) of L and R gives the glue relation. All these transformations are admissible since they satisfy the sufficient conditions stated in lemma 1.

We separate our transformations into two families: transformations and simplifying transformations.

Transformations

These transformations split or reorder the streams of data and modify the expression of concurrency.

SplitF(fig. 4(b))

This transformation splits a filter on its input. SplitF introduces simple split-join parallelism in the programs. This is legal because filters are pure: we can compute each input block on a different node. The SplitF transformation is parametric in the arity of the split (number of filter nodes used). As splitting a filter once with an arity of 4 or splitting twice with an arity of 2 achieves the same result, splitting is only applied once for any given filter. An already split filter is marked unsplitable. InvertJS(fig. 4(a)) This transformation inverts join and split nodes. To achieve this it creates as many split nodes as inputs and as many join nodes as outputs. It then connects together the new split and join stages as shown in the figure. Intuitively, this transformation works by "unrolling" the original nodes (examining consecutive executions of the nodes) so that a common period between the join and split stage emerges. The transformation make explicit the communication pattern in this common period, enabling to invert the join and split stage.

The transformation is admissible in two cases: 1-Each p j is a multiple of C = i c i , the transformation is admissible choosing p ij = c i .p j /C, c ji = c i . 2-Each c i is a multiple of P = j p j , the transformation is admissible choosing p ij = p j , c ji = p j .c i /P .

Because this transformation exposes the underlying unrolled communication pattern between two computation stages, it may often trigger some simplifying transformations, making the communication pattern simpler or breaking it into independent patterns.

A similar transformation is possible when ∀i, j p i = c j , that is when there is a shuffle between n input channels and m output channels. We choose not to describe this as a single transformation since it can be achieved using SplitS and SplitJ followed by a RemoveJS.

SplitS / SplitJ(fig. 4(e)) SplitS (resp. SplitJ) creates a hierarchy of split (resp. join) nodes. In the following we will only discuss SplitS. The transformation is parametric in the split arity f . This arity must divide the number of outputs, m = k.f . In the figure, we have chosen f = 2. We forbid the trivial cases (k = 1 or f = 1) where the transformation is the identity. As shown in figure 4(e), the transformation works by rewriting the original split using two separate stages: odd and even elements are separated then odd (resp. even) elements are redirected to the correct outputs.

SplitS and SplitJ can be used together with RemoveJS to break some synchronization points.

InvertDN(fig. 4(c))

This transformation inverts a duplicate node and its children, if they are identical. It is simple to see why this is legitimate. All nodes are pure, their outputs depend only on their inputs; thus applying a process k times to the same input is equivalent to applying the process once making k copies of the output. This transformation eliminates redundant computations in a program.

Simplifying Transformations

These transformations, remove nodes with either no effect or non-observed computations, and separate split-join structures into independent ones. SimplifySS / SimplifyJJ(fig. 4(i)) SimplifySS compacts a hierarchy of split nodes. SimplifyJJ is similar for join nodes. We will in the following discuss the SimplifySS transformation. This transformation is only possible when the lower split productions sum is equal to the production on the edge connecting the lower and upper splits.

This transformation is useful to put cascades of split nodes in a normal form so that other transformations can operate on them. It should be noted that this transformation is not the inverse of SplitS (breaking the arity of splits instead of the productions sizes).

SimplifyJS(fig. 4(h))

This transformation is possible when the sum of the join consumptions is equal to the sum of the split productions: x c x = y p y . The idea behind this transformation is to find a partition of the join consumptions and a partition of the split production so that their sum is equal: x≤j c x = y≤k p k . In that case we can split the Join-Split in two smaller Join-Split.

BreakJS(fig. 4(g))

This transformation is very similar to SimplifyJS. It is triggered when x c x = y p y but no partition of the productions/consumptions can be found. In that case the transformation breaks the edge with the largest consumptions (resp. productions), so that a partition can be found.

Both SimplifyJS and BreakJS work on join-splits of the same size. Join-splits of the same size correspond to a periodic shuffle of values. The idea behind these transformations is to make explicit the communications that occur during this shuffle, and separate this communication pattern into independent join-splits when possible.

SimplifyDD SimplifyDD is similar to SimplifySS, it compacts a hierarchy of duplicate nodes.

BreakC(fig. 4(f)) When a constant source is split, we can eliminate the split duplicating the constant source.

BreakT(fig. 4(d))

A node for which all outputs go to a Trash can be replaced by a Trash itself without affecting the semantics. This transformation eliminates subgraphs whose outputs are never observed, it is a kind of dead-code elimination.

RemoveJS / RemoveSJ / RemoveD These transformations are very simple and remove nodes whose composed effect is the identity:

• A join node followed by a split node can be removed if the join productions are the same as the split consumptions. • A split node followed by a join node for which the split i th output is connected to the join i th input, both nodes having equal consumptions and productions, can be removed. • A Duplicate, Join or Split node with only one output branch can be safely removed.

EXPLORATION ALGORITHM

The exploration is an exhaustive search of all the derivations of the input graph using our transformations. We use a branching algorithm with backtracking, as described recursively in algorithm 1. Optimized exploration and exploring a smaller search space are described in Section 4.2.

For this algorithm to terminate we must prove that for every initial graph, once a large enough recursion depth is reached, no transformations will satisfy the for all condition in statement 6. This follows from the fact that the transformations considered cannot produce infinite derivations. This is guaranteed by lemma 2 proved in the next section.

Algorithm 1 EXPLORE(G)

Termination

First we define a weight function σ on nodes, then we extend this weight to graphs using a τ function. Finally we introduce a well-founded ordering on the image of τ which we use to prove that no infinite derivation can be generated.

Let us define a weight function σ : Node → N on nodes as:

σ(N ) =        n k=1 c k if N = J(c 1 . . . c n ) m k=1 p k if N = S(p 1 . . . p m ) 1 if N = F splitable 0 otherwise
Let τ be a function defined on (Graphs) → (M(N), ≻) as τ (G) = {σ(n) : n ∈ G N odes }. We note M(N) the set of all finite multisets of N. Since the canonical order on N is well-founded, we can define a well-founded partial multiset ordering ≻ on M(N) [START_REF] Dershowitz | Proving termination with multiset orderings[END_REF]. The multiset ordering is defined as follows: ∀M, N ∈ M(N), M ≻ N if for some multisets X, Y ∈ M(N), where X = {} and X ⊆ M , N = (M -X) ∪ Y and ∀(x, y) ∈ (X, Y ), x > y That is to say, a multiset is reduced by removing at least one of its elements, and adding any number of smaller elements.

Definition 3: A transformation T is monotone iff G T -→ G ′ ⇒ τ (G) ≻ τ (G ′ ).
In words, a transformation is monotone if all the weights of added nodes are strictly inferior to the weights of the removed nodes, or if it only removes nodes. Using the well-foundness of the multiset ordering it is easy to prove the following lemma:

Lemma 2 (Finite derivations): All derivations of a graph G that only make use of monotone transformations are finite.

Computing the weight function for each left-hand side and right-hand side of the graph rewriting transformation shows that all of these transformations are monotone, and termination of algorithm 1 follows.

Optimizing Exploration

Because the search space is potentially exponential, we have introduced some modifications to the naive exploration presented before.

Dominance rules

Generated graphs G are often obtained through application of transformations operating on distinct part of the graph. In that case, applications of these transformations commute; meaning that the order in which they are applied does not change the resulting graph. Since the order is of no importance, it is more efficient to only explore one of the possible permutations of the application order, and cut the other confluent branches.

To select only one of the possible permutations during our exploration, we introduce an arbitrary ordering (⊏) on our transformations, we say that T 1 dominates T 2 if T 1 ⊏ T 2 . A new transformation is applied only if it dominates all the earlier transformations that commute with it.

A sufficient condition for an early transformation T 1 to commute with a later transformation T 2 is that the nodes that are matched by L 2 where already present before applying T 1 . This condition can be easily checked if nodes are tagged with a creation date during exploration.

Sandbox exploration

Some data reorganization patterns, like a matrix transposition or a copy of elements, may be modeled with high arity nodes. This is not a problem per se since the complexity of our algorithm is tied to the number of nodes, and not to the number of edges. Yet for some transformations (e.g. InvertJS, InvertND), the number of nodes created is equal to the arity of the original nodes in the matching subgraph. If such transformations are applied to high arity nodes, the complexity explodes. To alleviate this problem, configurations leading to this potential issue are identified.

A node has high arity when it has more than H in or out edges. H can be chosen arbitrarily, H = 30 in our experiments. A graph is compact when all its high arity nodes have a number of distinct children or parents which is less than H. The complexity explosion is caused by transformations that turn a compact graph into a non-compact one. A straightforward approach is to forbid such transformations. Yet this eliminates valuable branches where the graph is compacted shortly after by another transformation.

We would like to forbid the derivations that produce non-compact graphs, yet keeping the derivations in which the graph is compacted shortly after. To achieve this we implement sandbox exploration. The idea of sandbox exploration is to extract high arity nodes along with their close neighborhood. Explore all the derivations of this neighborhood, eliminate all the non compact derivations and keep the compact ones. This optimization eliminates some possible derivations of the search space, making the algorithm non exhaustive. Yet in the applications we have studied, there was little gain in the non-compact derivations that have been removed.

Partitioning heuristic

Algorithm 1 exhaustive search may take too much time on very large graph instances. The optimizations presented in the previous section, mitigate the problem; nervertheless for really large graphs like Bitonic (370 nodes) or DES (423 nodes) in section 7, the exploration still takes too much time. To deal with very large graph instances we have implemented an heuristic combining our exploration with a graph partitioning of the initial program.

We show that reducing the initial program size, reduces the exploration maximal size. Our heuristic, based on this result works by partitioning the initial program.

For this to work, the metrics we optimize must be composable: there must exist a function f that verifies for every partition G 1 , G 2 of G, metric(G) = f (metric(G 1 ), metric(G 2 )). We will see in section 6 that the metrics we use to reduce the memory required in a modulo scheduling are indeed composable.

If the metric we try to optimize is composable it is legit to explore each partition separately, selecting the best candidate (which maximizes f ) for each partition, and assemble them back together as detailed in algorithm 2.To partition the graphs we use the freely available Metis [START_REF] Karypis | A fast and high quality multilevel scheme for partitioning irregular graphs[END_REF] graph partitioning tool, trying to reduce the number of edges between partitions.

The downside of this heuristic is that we loose the transformations involving nodes of different partitions. Yet our benchmarks in section 7 show that the degradation of the final solution is acceptable (except for very small partitions).

Algorithm 2 PARTITIONING(G, P SIZE)

1: n = countN odes(G) 2: p = n/P SIZE 3: partition G in p balanced partitions G 1 , . . . , G p 4: for all G i do 5:
EXPLORE(G i ) finds a best candidate B i 6: end for 7: assemble together the B i

REVIEW OF MODULO SCHEDULING

To evaluate our exploration method we have chosen a stream modulo scheduling execution model. We are going to review modulo scheduling in this section, particularly the problem MPA-ii, Memoryconstrained Processor Assignment for minimizing Initiation Interval, introduced in [START_REF] Choi | Stream compilation for real-time embedded multicore systems[END_REF].

Mapping and scheduling

In a modulo scheduling each task is assigned a stage. Stages are activated successively, forming a software pipeline. The problem MPA-ii consists in finding a scheduling that reduces the throughput on multiple P E under memory constraints. The solution proposed in [START_REF] Choi | Stream compilation for real-time embedded multicore systems[END_REF] uses two separate phases, first they map each node in the graph to a processor, then they assign to each node a pipeline stage.

Let N G be the number of nodes and P the number of PE. For each node i we consider:

• a ij equal to 1 when node i is assigned to processor j.

• w(i), the work cost of one steady-state execution of the node.

• b(i), the buffer size needed by one steady-state execution of the node. This buffer size depends of the stage assigned to i which itself depends on the PE mapping. Every node must be assigned to exactly one processor,

P j=1 a ij = 1, ∀i = 1, . . . , N G (18)
To optimize the throughput, we balance the cumulated cost in each processor,

N G i=1 w(i).a ij ≤ II, ∀j = 1, . . . , P (19)
minimize II (20)

Finally we consider the memory constraint imposed by the available local memory in each PE mem (in this paper we consider that all the PE have the same available memory),

N G i=1 b(i).a ij ≤ mem, ∀j = 1, . . . , P (21)
Because the b(i) depends on the mapping the program is not linear. To compute a solution efficiently, the authors in [START_REF] Choi | Stream compilation for real-time embedded multicore systems[END_REF] propose the following algorithm:

• Stage1, Make the conservative assumption that all the nodes are assigned to different PE.

• Stage2, Assign the earliest possible stages base on the previous assumption.

Buffer size

When computing the buffer size needed for implementing the communications over an edge e between node u and node v, the authors in [START_REF] Choi | Stream compilation for real-time embedded multicore systems[END_REF] consider two kind of situations:

• u and v are on the same PE, the output buffer of u can be reused by v.

• u and v are on different PE, buffers may not be shared, since a DMA operation d is needed to transfer the data. The stage in which d is scheduled is noted stage d . The number of elements produced by u and consumed by v on edge e during a steady-state execution is called β(e) and given by eq. ( 1). Furthermore, since multiple executions of the streams may be on flight in the pipeline at the same time, buffers must be duplicated to preserve data coherency. The number of buffer copies needed depends on the stage difference between the producer u and the consumer v:

δ(u, v) = stage v -stage u + 1 (22)
The output buffer requirements for all the nodes but Duplicate are,

out buf s(i) = ∀e∈outputs(i) δ(u, v) * β(e) (23)
For Duplicate nodes, since the output is the same on all the edges, we can share the buffers among all the recipients,

out buf s(i) = max ∀e∈outputs(i) δ(u, v) * β(e) (24)
iff i ≡ D

The input buffer requirements are,

in buf s(i) = ∀e∈dma inputs(i) δ(v, d) * β(e) (25)
Combining (23)(24)(25) we obtain the total requirements for a node,

b(i) = out buf s(i) + in buf s(i) (26)

METRICS

In this section we propose a metric that selects candidates which improve the minimal memory required for the modulo scheduling described in the previous review.

From equations (26)(23)(24)(25) we observe that to reduce the b(i) we can either reduce the stage difference between producers and consumers, δ(u, v), or we can reduce the elements exchanged during a steady state execution, β(e).

The authors of [START_REF] Choi | Stream compilation for real-time embedded multicore systems[END_REF] already optimize the δ(u, v) when possible in Stage5. We attempt to reduce b(i) by reducing β(e). To reduce the influence of the β(e) in the buffer cost we search the candidate that minimizes,

maxbuf (G) = max ∀e∈G β(e) (27)
if we have a tie between multiple candidates, we chose the one that minimizes,

totbuf (G) = ∀e∈G β(e) (28)
We note that these metrics are composable, as required by the partitioning heuristic described in section 4.3. Indeed given a partition

G 1 , G 2 of G, we have maxbuf (G) = max(maxbuf (G 1 ), maxbuf (G 2 )) and totbuf (G) = totbuf (G 1 ) + totbuf (G 2 ).

RESULTS

We demonstrate the interest of our method in reducing the minimal memory requirements in a modulo-scheduling stream execution model.

Experimental protocol

We consider a representative set of programs from the StreamIt benchmarks [START_REF]Streamit benchmarks[END_REF]: Matrix Multiplication, Bitonic sort, FFT, DCT, FMradio, Channel Vocoder. We also consider three benchmarks of our own: Hough filter and fine grained Matrix Multiplication (which both contain cycles in the stream graph), and Sobel filter (with high-arity nodes). We first compute for each benchmark the minimal memory requirements per core for which an MPA-ii mapping is possible (of course we take into account the optimizations proposed by [START_REF] Choi | Stream compilation for real-time embedded multicore systems[END_REF] in Stage5). We will use this first measure, MPAii mem, as our baseline. We then use our exploration method on each benchmark, and select the best candidate according to the metrics described in section 6. We compute the MPA-ii minimal memory per core requirements for the best candidate: Exploration MPAii mem.

Finally we compute the memory requirements reduction using the following formula:

(MPAii mem -Exploration MPAii mem) MPAii mem In [START_REF] Kudlur | Orchestrating the execution of stream programs on multicore platforms[END_REF] the authors consider different function splitting variants while solving the ILP of modulo scheduling, yet unlike [START_REF] Choi | Stream compilation for real-time embedded multicore systems[END_REF], they do not try to minimize the buffer memory cost. Nevertheless we believe it would be possible to integrate the function split selection described in [START_REF] Kudlur | Orchestrating the execution of stream programs on multicore platforms[END_REF] with the memory constraints of [START_REF] Choi | Stream compilation for real-time embedded multicore systems[END_REF]. Thus, to make the comparison fair, we have considered the same function splitting variants when measuring MPAii mem and Exploration MPAii mem. This means that in the results below we do not measure the memory reduction achieved by splitting function blocks (SplitF), we only take into account the memory reduction achieved by the rest of the transformations.

Memory reduction

The experimental results obtained are summarized in figure 6. The exhaustive search was used when exploring the variants for all the benchmarks except DES and Bitonic for which we used the partitioning heuristic (with PSIZE=60). We achieve a significant memory reduction in seven out of the ten benchmarks. This means in these seven cases we are able to execute the application using significantly less memory than using the approach in [START_REF] Choi | Stream compilation for real-time embedded multicore systems[END_REF], therefore we are able to target system with a smaller memory footprint. In terms of throughput, our method does not degrade the performance since we obtain similar II (initialization interval) values than bare MPA-ii.

We can distinguish three categories among the benchmarks:

No effect: DCT, FM, Channel In this first group of benchmarks, we do not observe any improvement. Indeed these programs make little use of split, join and duplicate nodes. They are almost function only programs. Because our transformations work on data reorganisation nodes, they have no effect on these examples. The very small improvement in Channel is due to a single SimplifyDD that compacts a serie of duplicate nodes.

Loop splitting: MM Fine, Hough These two benchmarks contain cycles. Using our set of transformations we are able to split the cycles, as we demonstrate in figure 5 for the Hough benchmark. This is particularly interesting in the context of modulo scheduling where cycles are fused [START_REF] Kudlur | Orchestrating the execution of stream programs on multicore platforms[END_REF]. As you see in the Hough selected variant, the cycle has been broken in three smaller cycles. Thus after fusion, it has more fine-grained filters, and achieves smaller memory requirements.

Dependencies breaking, and communication reorganisation simplifying: MM coarse, MM fine, FFT, Bitonic, Sobel, DES The rest of the benchmarks show varying memory reductions. They are due to a better expression of communication patterns. Either non needed dependencies between nodes have been exposed, allowing for a better balancing among the cores, or groups of split, join and dup have been simplified in a less memory consumming pattern.

Variation when changing number of PE

In this section we study the memory reduction variance depending on the number of cores in the target architecture. We can identify two categories:

Plateau, graphs in this category, Bitonic, FFT, DES, show little change over the number of PE. We observe in table 1 that for these graphs maxbuf has variated little, but totbuf has decreased. Increasing, graphs in this category, MM Fine, MM Coarse, Sobel, Hough, show a better memory improvement the more PEs are used. In table 1 we see that these graphs increase both totbuf and maxbuf .

Graph in category Increasing, break the biggest memory consumer nodes in less greedy nodes. Thus when increasing the number of PE, the mapping algorithm is able to better balance the memory cost since it can split the biggest consumer(s) among multiple processors. This explains that these benches show better results as we increase the PE number. Once we add enough processors to distribute all the new nodes created after the split of the biggest consumer, this increase should stop (we can observe this effect on Hough and MM Fine). In the other hand, the reduction in graphs of category Plateau, is more uniform, and thus the gain does not depend on the number of PE.

Exploration cost and Heuristic evaluation

We measure the exploration time of our method for each of the benchmarks. The measures were taken using a Intel Pentium 4 3.8GHz computer with 4Gb of RAM. The exploration algorithms were written in Python and executed using Python 2.5.4 interpreter running on Linux. The results are reported on table 2.

If we do an exhaustive search, exploration times are fast (under 1min) for six of the benchmarks. Sobel and Hough, which possess multiple high-arity nodes, show moderate exploration times (under 10min). Finally, without the heuristic, exploration for DES and Bitonic (the largest benchmarks in our suite) is too long (5 hours for DES; more than 6 hours for Bitonic, we stopped the exploration after that point).

Using the heuristic, with PSIZE=60, the exploration of DES and Bitonic is very fast (under 2min). The partitioning heuristic effectively reduces the running time of these very large graphs, but in the process discards valid transformations. To evaluate the effect of the heuristic on the solution quality, we have compared the memory reduction achieved by the exhaustive exploration to the memory reduction achieved after partitioning the initial graph in 2,3,4 and 6 subgraphs. We have used smaller versions of DES (with 8 mixing stages instead of 16) and Bitonic (with 8 bit strings instead of 32) to evaluate the heuristic (using the original version was impractical because of the very long search time). The results are summarized in figure 7.

The solutions for Bitonic8, Des8 and FFT are quite good even with 6 partitions, they are at most 25% worst than the exhaustive solution.

MM coarse, MM fine, Hough and Sobel, on the other hand, are quickly degraded, and for more than two division do not improve the original program. The extreme degradation of these benchmarks is explained by their small size. Having less than 20 nodes, the partitioning process leaves very small partitions where no transformations are found. The heuristic should be evaluated on larger programs, nevertheless we provide the results for completeness.

RELATED WORKS

Dataflow programming models have been studied for a long time, and many variants have been proposed. Our graphs are defined upon the cyclo-static dataflow model [START_REF] Bilsen | Cycle-static dataflow[END_REF] a special case of Kahn process networks [START_REF] Kahn | The semantics of a simple language for parallel programming[END_REF]. The authors of [START_REF] Kudlur | Orchestrating the execution of stream programs on multicore platforms[END_REF] were the first to apply Modulo Scheduling to stream graphs, evaluating their technique on the Cell BE. In [START_REF] Choi | Stream compilation for real-time embedded multicore systems[END_REF] their work was extended considering an embedded target with memory and number of PE constraints, MPA-ii is introduced. The authors of [START_REF] Udupa | Software pipelined execution of stream programs on gpus[END_REF] successfully used Modulo Scheduling to compile stream graphs on GPU.

The StreamIt project [START_REF] Thies | StreamIt: A Language for Streaming Applications[END_REF], proposes both a stream language, which is very similar to the formalism of our paper, and an optimizing compiler for the Raw [START_REF] Gordon | A stream compiler for communication-exposed architectures[END_REF] architecture. As in our approach, StreamIt adapts the granularity and communications patterns of programs through graph transformation, which it separates in three classes:

• Fusion transformations cluster adjacent filters, coarsening their granularity.

• Fission transformations parallelize stateless filters decreasing their granularity.

• Reordering transformations operate on splits and joins to facilitate Fission and Fusion transformations. The order in which to apply the transformation is decided using a greedy algorithm. We implement Fission transformations on stateless filters using the SplitF transformation. In our approach, Fusion transformations should be delegated to a later clustering phase, since in our case early coarsening would reduce the number of explored variants. Thus we do not use StreamIt fusion transformations during our exploration. Instead, we have concentrated on proposing new Reordering transformations that explore alternate communication patterns. We implement StreamIt filter hoisting on duplicate nodes with InvertND. We propose, through RemoveJS and RemoveSJ, StreamIt synchronization removal, which eliminates neighbor split-joins with matching weights. We go further tackling split-join junctions of different weights with InvertJS and BreakJS, eliminating dead-code with BreakT and removing unnecessary synchronization on constant sources using BreakC. To the best of our knowledge StreamIt does not consider reordering transformations on feedback loops. The BreakT transformations which eliminates dead-code was already described in [START_REF] Parks | A comparison of synchronous and cycle-static dataflow[END_REF].

Array-OL also proposes data transformations in its multi-dimensional dataflow model for signal processing. In Array-OL, the elements that are consumed by a task are defined by successively translating a selection pattern over a multidimensional array. In [17][18] the authors show that in some cases it is possible to share the patterns for two succesive tasks. We achieve a similar effect on our model using InvertDN, indeed if two function nodes work on similar patterns there is a chance that our transformations exposes the common pattern as a number of common subgraphs under a Duplicate node; using InvertDN we are able to hoist the common pattern over the duplicate node.

Dataflow transformations approaches have been proposed to optimize circuit design [START_REF] Chandrakasan | An approach for power minimization using transformations[END_REF][20], but they usually target a much smaller granularity of nodes than our filters.

Many methods for optimizing CSDF multiprocessor schedules have already been proposed, some concentrate on maximizing the throughput [START_REF] Bilsen | Cycle-static dataflow[END_REF][21], other on minimizing the memory requirements [START_REF] Wiggers | Efficient computation of buffer capacities for cyclo-static dataflow graphs[END_REF] and some search best pareto configurations for both criteria [START_REF] Stuijk | Throughput-buffering trade-off exploration for cyclo-static and synchronous dataflow graphs[END_REF]. Our approach does not act at the schedule level but at the implementation level, it is therefore complementary to these approaches which operate on the schedule.

CONCLUSION

We propose a design space exploration to reduce memory requirements of stream programs under modulo scheduling. Memory reduction is achieved through succesive semantically preserving transformations, that break cycles, break dependencies and simplify communication patterns in the stream graph.

We propose an efficient heuristic to explore the different transformations combinations based on graph partitioning. We demonstrate the interest of the approach on a significant panel of benchmarks.

We think that this approach is flexible and could also be used with a different metric to adapt stream programs to other constraints as communication bus capacities, maximum latencies, memory hierarchies. We plan to investigate this in the future.

Fig. 2 .

 2 Fig. 2. An abstract CSDF transformation.

2 :

 2 Furthermore, for a subgraph H ⊆ G we define I(H) as the traces on the input edges of H and O(H) as the traces on the output edges of H. The tuple of the lengths of each sink trace is noted O(G) = [t(o) : o ∈ Sinks]. Definition Given a CSDF graph G, a transformation G T -→ G ′ is admissible iff

  . n . . . N o11 . . .o 1m on1 . . .o nm ⇒ i1 N D . . . m . . . D o11 . . .o n1 o1m. . .o nm (c) InvertDN in0 . . . inn

  i1 . . . ij ij+1 . . . in o1 . . . o k o k+1 . . .o m . ij ij+1 . . . in o1 . . . o k o k+1 . . .o m

Fig. 4 .

 4 Fig. 4. Set of transformations considered. Each transformation is defined by a graph rewriting rule. Node N denotes a wildcard for any arity compatible node.

1 :

 1 Simp ← {SimplifySS, SimplifyJJ, BreakC ...} 2: Tran ← {SplitF, InvertJS, BreakJS, ...} 3: while ∃N ∈ G ∃S ∈ Simp such that S applicable at N do 4: G ← S N (G) 5: end while 6: for all N ∈ G and T ∈ Tran such that T applicable at N do end for 10: G ← RESTORE(G)

•,

  Stage3Compute the b(i) using Stage1 and Stage2. • Stage4, Solve the ILP problem ((2)+(3)+(4)) using the conservative b(.) of Stage3. • Stage5, Optimize stage assignment based on the PE assignment in Stage4.

1 )

 1 InvertJS on J6 and S15 2) InvertJS on J16 and S7 3) InvertJS on J8 and S19 4) BreakC on IH 5) RemoveJS on J26 6) InvertJS on J4 and S17 7) InvertDN on D2 (c) The derivation that generated the best candidate, some transformations involve transient nodes that do neither appear in the original graph nor in the best candidate.

Fig. 5 .

 5 Fig. 5. Using our transformations to split cycles on the Hough benchmark.

Fig. 6 .

 6 Fig.6. Minimal required memory reductions achieved by our proposed method: the results are expressed as a reduction percentage over the minimal required memory per PE obtained by MPA-ii in[START_REF] Choi | Stream compilation for real-time embedded multicore systems[END_REF]

Fig. 7 .

 7 Fig. 7. Evaluation of the partitioning heuristic on 8 PE: for each benchmark, we show the memory reduction achieved when changing N G P SIZE (the number of partitions used), exhaustive search is conducted independently in each partition.

TABLE 1

 1 Metrics variations between the original graph and the best selected candidate (values represent a number of elements)

TABLE 2

 2

	Measured exploration costs


Amal Ghazi

Vincent Le Cam

Jean-Marie Marie Caussignac

Professor Alfredo Güemes
email: aguemes@dmpa.upm.es

Metrological approach of new sensors used in structural health monitoring

ABSTRACT

The rise of new technologies and the use of new sensors in structural health monitoring rise from a need increasing for knowledge and sounding in real time of constructions in the civil engineering. Safety requires the reliability of the results and the answers given by the sensors. In this context it is essential to carry out thorough metrological studies making it possible to extract uncertainty associated with the result according to the need and the context of use, in order to better evaluate the degree of confidence according to the requirements one fixed.

The metrological studies can be done with various methods according to the situation and to the nature of measurements. Indeed currently the international reference for the calculation of uncertainties is the famous GUM "Guides to the expression of uncertainty in measurement" published in 1993 which proposes a procedure of evaluation and expression of uncertainty called analytical approach. It is currently the most traditional method of reference. But as uncertainty touches now with all the measurable sizes and that the processes of measurement are increasingly complex and the settings in equations of all the components of uncertainty become difficult even impossible, in order to stage with this problem several laboratories have worked for a few years on a classification of four methods, the first is the traditional method based on the GUM, the second approach consists in composing the uncertainties estimated starting from the characteristics of the method. The third method consists in using the values of fidelity of a method published in the exit of interlaboratories comparison and finally the last uses theses intercomparisons to determine the performance of a laboratory. The two first approaches are applied inhouse in only one laboratory whereas the two last are applied when several laboratories intervene.

INTRODUCTION

Metrology and tests are closely bound [1], indeed we can establish that if we make measurements without carrying out tests, we seldom carry out tests without measurements.

The components of a test are subjected to the concepts, operations and requirements of metrology, would be only by the means of the operations of checking or calibration of the used measurement materials. A process of relevant test must thus take account of the whole of this information, of metrological nature.

In addition, a process of test and a process of measurement face the same requirements as regards quality of produced information. We wish in particular to have uncertainty associated with the measurement or test [START_REF] Allisy | Assessment of uncertainty in measurement[END_REF][START_REF] Nf | Normes fondamentales-Guide pour l'expression de l'incertitude de mesure[END_REF]. This narrow overlap between the two worlds forces to call upon identical concepts, or at least coherent, when we must answer questions of comparable nature.

After some metrological definitions, we will propose the study carried out on a new acoustic system developed at the LCPC and whose first objective is to detect and to locate the wire ruptures which intervene in the cables of the bridges [START_REF] Cam | A wireless sensor network for damage detection and health monitoring of cables[END_REF][START_REF] Cam | A wireless acoustic sensor network for damage detection and health monitoring of cables[END_REF].

The system allows the detection of the new ruptures once installed but not the ruptures which could have intervened before installation. A first operational generation of this system designed by the LCPC, was industrialized and equipped several bridges in France [START_REF] Cam | A wireless acoustic sensor network for damage detection and health monitoring of cables[END_REF].

The new system aims are recording and exploitation of the acoustic signals for better ruptures localization and new criteria of diction. We want also to perform the acoustic system in its sensor-network topology and the real-time monitoring of cables.

INTRODUCTION TO THE METROLOGICAL STUDY

Any operation of measurement is ineluctably sullied with errors [7]. Theses errors originate in the measurement system and the quantity itself.

The measurement system

The system of measurement is never perfect. It can be sensitive to the environment (effects of the temperature, of the hygroscopy...), it is certainly not faithful (since when the observations are repeated, we observe a dispersion of the values).

The bad definition of the quantity to measure is itself a source of errors

It should be considered that it would be necessary to provide many details to define in an exhaustive way the quantity object of measurement.

MEASURMENT PROCESS ANALYSIS

The correct analysis of the measurement process is doubtless the most difficult and most delicate task to estimate the uncertainty. This analysis require technical skills and analysis feeling. It can be practiced only by someone who control the measurement technique. The development of the "better" mathematical model requires to have finely analyzed the measurement process so as to identify the factors of possible influence, which will be identified like "causes of errors". We will take guard so that the term usually used of "causes of errors" indicates an influence quantity on the measurement result which can exploit at the same time on the error and on the uncertainty.

There is a technique, based on Ishikawa diagram also called the fishbone diagram which allows starting from a brainstorming and a very good knowledge of the measurement process to imagine and to count all the causes.

We analyze successively, the contribution of the means, the measurement method, the surrounding medium, the operator and the measured object (mesurand). Figure 1 shows a general fishbone diagram.

Figure 1 .

 1 Figure 1. Ishikawa diagram

RUPTURE DETECTION: PRINCIPLE

When a rupture occurred in a cable, an acoustic wave is generated and detected by the sensors physically placed along the cable. An accelerometer is the sensitive element of each sensor. Each sensor embed a processor that permanently digitizes signal from the accelerometer and compare its amplitude to a predefined threshold. If the signal amplitude exceeds the threshold, this value is recorded and precisely dated. Then, those two datas (amplitude and time detection) are sent to supervisor [START_REF] Cam | A wireless acoustic sensor network for damage detection and health monitoring of cables[END_REF].

The supervisor communicates with sensors and "knows" sensor relative locations (L12, L23,…) and is so able to locate the point of rupture X. The supervisor identifies sensors 1,2 and 3. sensors 1 and 2 are the two sensors that received the wave first. That means that the break thus occurred between those two sensors. Sensor 3 and sensor 1 enable one to compute the speed "V" of the wave. From these datas it determines the localization "X" as follows [START_REF] Cam | A wireless acoustic sensor network for damage detection and health monitoring of cables[END_REF].

V=L31/t31

(1)

Where tij denotes the delay in event detection between sensor i and sensor j.

SYSTEM CARACTERISATION

We can divide our acoustic system into two blocks; the first is the input data block constituted by: -The sensors placed along the cable ( 3 at least) and which measure permanently the acceleration. -

The GPS information provided to each sensor by the satellites. The second is the output data block constituted by the information given by the supervisor: -

The waves recorded by the sensors. -

The detected and located ruptures on the cable. -

The system events.

Influence factors

The place of installation of the sensor on the cable is full of consequence: if (as recommended) the sensor is fixed directly on the cable, the measured wave is closer to the real phenomenon, whereas if for practical reasons (access, cost of installation, …) the sensor is fixed differently then the measurements are strongly influenced by "the medium" surrounding the cable.

There is a strong dependence of the sensor response to its fixing. Indeed if the sensor is strongly fixed or not, the wave could be completely undetected by the system. The fixation system have a big influence on the result.

The sensor is sensitive to : accelerometers drift and limits, the analogicalnumeric converter quality and limits (this element permit the conversion of the accelerometer signal on a 16 bits samples), the electromagnetic compatibility which could, if its raised, influence the behavior of the electronic components, and at least the good GPS cover (sometimes a satellite cover can provide erroneous information.

There is no losses on-line, all transmitted octets are received. Each sensor has a synchronization mechanism based on recovery of the absolute hour transmitted by the GPS. The sensors have a resynchronized base of time all the 1s by the P.P.P signal of the GPS. A counter of 1/100 of a µs is reset at each P.P.S top. The precision of the P.P.S being of 200ns and the interruption of the reset is 1 µs. All the sensors receiving the satellite are synchronous on the basis of universal time with +/-1µs.

The threshold are fixed by "training" of the cable. We try to pace the sensors thresholds "right at the top of noise" but as low as possible. Generally around 1 to 4g.

CONCLUSION

This article is the beginning of the metrological study of the acoustic system. Nerveless the results obtained at this time are very promising , we hope at end to have a relative uncertainty around 10%.

When the system is in optimal conditions, the detection is assumed at 100%. The crucial point at time is to find the better solution to resolve fixation problems which are the probably most important part in the uncertainty.


Alessio Tornese
email: alessio.tornese@cea.fr

Christophe Delaveaud
email: christophe.delaveaud@cea.fr

Maximum Gain of an Electrically Small Cosines-Dipole-Based End-Fire Array

Keywords: antenna arrays, electrically small antenna, superdirectivity, high efficiency, antenna gain optimization

Electrically Small Antennas (ESAs) are of high interest in applications where a compact size wants to be preserved. With the objective of the realization of a highly efficient and superdirective array within a very compact space, a new radiating element and array design is proposed, optimized for maximum attainable gain. A cosines-dipole printed antenna is designed by adjusting the amplitude and periodicity of the cosine microstrip, to resonate at the desired frequency of 916 MHz. Then, to achieve high gain two elements are closely spaced, mirrored to their excitation point, one fed and the other parasitic. An analytical method for gain optimization based on the Spherical Wave Expansion (SWE) theory is used to maximize the array gain. Two different array geometries are compared by looking at the power distribution of the spherical modes, and the configuration that returns the highest gain is chosen. A realized gain of 6.5 dBi is achieved in simulation, for a total size included in a radiansphere of ka=1, with the advantage of having a printed antenna, thus planar, easy to integrate, and low cost. The proposed antenna solution presents in theory an excellent trade-off between electrical size and realized gain.

I. INTRODUCTION

Electrically Small Antennas (ESAs) have proven to be of particular interest due to their small size (relative to the wavelength of interest) and yet good performance. However, the difficulty in their implementation has always been a matter of debate, given the fundamental limitations that bound gain and bandwidth to the antenna's physical size [START_REF] Koziol | A four-year program to tackle a fundamental antenna challenge -IEEE Spectrum[END_REF]. The milestone works of Chu [START_REF] Chu | Physical Limitations of Omni-Directional Antennas[END_REF] and Harrington [START_REF] Harrington | Effect of antenna size on gain, bandwidth, and efficiency[END_REF] set the limits to antenna directivity as ( ) ( )

m a x ² 2 D k r k r = +
, with k the wavenumber, r the radius of the smallest sphere enclosing the antenna, and kr the size of the "radiansphere". To agree with realizations of antennas presenting higher directivity values, Kildal and Best [START_REF] Kildal | Further investigations of fundamental directivity limitations of small antennas with and without ground planes[END_REF] proposed a heuristic formula that re-computes this limit as ( ) m ax ² 3 D kr = + . For a vanishing kr, this limit converges to 3 (or 4.77 dBi) agreeing with the directivity of an infinitesimal Huygens source. More recently, in [START_REF] Pigeon | Analysis of Harrington limit for electrically small antenna directivity[END_REF] a new effective radiansphere of size kr+1 that allows the efficient propagation of the fundamental mode, even for a vanishing kr, is considered. This results in the re-calculation of the limit as ( ) ( )

m a x D = k r + 1 2 π ² + 2 k r + 1 2 π       
 . On the other hand, already in 1946 Uzkov [START_REF] Uzkov | An approach to the problem of optimum directive antenna design[END_REF] observed for end-fire arrays of P isotropic sources an increasing directivity up to P² when tending to a near-zero inter-element distance. Hence, the size of a radiating source is not the only parameter determining its potential directivity. Any source whose directivity exceeds these limits is considered "superdirective". Superdirective sources that are also efficient are referred to as "supergain".

It is generally known that end-fire arrays present high values of gain, but when their inter-element spacing is reduced (< 0.2 ) [START_REF] Uzkov | An approach to the problem of optimum directive antenna design[END_REF]. The compact dimensions lead to strong levels of mutual-coupling and current magnitudes on the elements, and high power dissipation in the resistive part of the antennas.

The synthesis of supergain arrays can be mathematically seen as a relaxation of the optimum problem when directivity is optimized. In practice, all the available modes, in the given volume and radiating in the desired direction, should be correctly excited with the additional constraint of keeping the radiation efficiency high.

While the literature on superdirectivity is quite large, only few works deal with the synthesis of supergain end-fire arrays. In [START_REF] Debard | Three-element end-fire linear arrays (super) directivity and gain optimization[END_REF], the array factor theory is used to optimize a three-element end-fire array presenting 8.6 dBi of gain with a kr=1.4; in [START_REF] Georgiadis | A convex optimization approach for the design of supergain electrically small antenna and rectenna arrays comprising parasitic reactively loaded elements[END_REF] a convex optimization problem is developed and theoretical results are presented for two-and three-dipole end-fire arrays; and finally in [START_REF] Tornese | A new method for endfire array gain optimization using spherical wave expansion[END_REF] a method for gain optimization based on Spherical Wave Expansions (SWE) theory is presented. Recently, in [START_REF] Shi | Multipolebased electrically small unidirectional antenna with exceptionally high realized gain[END_REF] another approach to the design and optimization of high-gain antennas is presented based on the multipole excitations in a very compact space. An antenna within a radiansphere of kr=0.98 is realized and a realized gain of 6.3 dBi is measured.

This paper aims to present a new cosines-dipole antenna geometry, the design of a new two-element compact array geometry with a total kr<1, and the use of the SWE method [START_REF] Tornese | A new method for endfire array gain optimization using spherical wave expansion[END_REF] to investigate the best array geometry and maximize the gain.

II. DIRECTIVITY AND GAIN OPTIMIZATION

Directivity limits for end-fire arrays of P elements, when their spacing vanishes, are known from the literature in the case of isotropic sources, according to Uzkov's observation [START_REF] Uzkov | An approach to the problem of optimum directive antenna design[END_REF] as P², and for electrical dipoles and Huygens sources as P²+P-1/2 and P²+2P respectively, according to [START_REF] Debard | On the maximum end-fire directivity of compact antenna arrays based on electrical dipoles and Huygens sources[END_REF]. In the latter, it is also pointed out that when directivity tends to its maximum, according to the efficiency, a drop in the gain is observed. The gap between directivity and gain depends on the efficiency values of the array elements.

When P=2 half-wave electrical dipoles are considered, their maximum directivity is 7.3 dBi, while for the gain not the same limit can be stated. However, despite losses severely impacting the array performance when compact sizes are targeted, gain optimization can be a solution. As reported in [START_REF] Tornese | A new method for endfire array gain optimization using spherical wave expansion[END_REF] by taking into account the radiation efficiency of the elements the optimization can be modified and target maximum gain rather than directivity. Based on the SWE theory, this optimization searches for a trade-off between the highest possible number of radiating modes and their efficiency. In the case of directivity, one may observe higher order modes excited and a consequent high directivity, but an actual very low gain. Such higher-order modes can be excited in the structure, but they are mainly dissipative and cannot radiate energy. The gain optimization cuts away that portion of modes that are not efficient. In practice, it reduces the directivity and increases the gain. By employing the method presented in [START_REF] Tornese | A new method for endfire array gain optimization using spherical wave expansion[END_REF], one can find the optimal excitation, i.e. the complex coefficient ap, necessary to excite the best combination of spherical mode for maximum gain, as detailed in the following paragraph.

A. Synthesis of Supergain End-Fire Arrays

According to the SWE theory, outside of the radiansphere of radius kr, the electric field radiated by P radiating sources can be expressed with a combination of spherical far-field functions ( ) ,( ,) 1

,
smn co smn p p smn smn p n p p smn Q K i G Q θ φ θ ϕ δ ⋅ = ⋅ +     uur r (2)
is the total gain of the array. The , expressing the losses of each spherical mode of n-th degree radiated by the p-th element. In [START_REF] Tornese | A new method for endfire array gain optimization using spherical wave expansion[END_REF], [START_REF] Hansen | Spherical Near-Field Antenna Measurements[END_REF] it is demonstrated that the maximum of ( 2) is achieved whit the set of spherical wave coefficients ( )

* * max 0 0 , 1 smn co smn n K Q c i θ φ δ   = ⋅ ⋅     +   uur r (3)
with c an arbitrary constant. Then, the desired coefficients ap are the solution of the matrix problem where the initial conditions are expressed by a matrix containing all the SWE coefficients ,1 , ,..., 2), calcu- lated for the P elements. The coefficients of the optimal modal distribution are known by (3) as

initial Q smn smn P Q Q   =   of equation (
max optimal Q smn Q   =   cal-
culated with the same number of spherical modes Nmax. Then, a matrix inversion of these two quantities

-1 in itial op tim al a Q × Q = (4)
is the solution to the problem. The vector a in our case would contain two complex numbers a1 and a2, proportional to the optimal elements feed for gain maximization.

B. Parasitic array

The complex coefficients ap solution for maximum gain represents the excitations of the array elements. The amplitude and phase of the ap are proportional to the magnitude and phase of the currents that must be excited. Setting such a specific current on each element with a fully driven configuration leads to the optimal result. However, it is often preferred, for a matter of complexity, or realization feasibility, to seek an alternative solution. Parasitic loading demonstrated an excellent agreement with full-driven excitation for superdirective arrays [START_REF] O'donnell | Electrically small superdirective arrays using parasitic elements[END_REF]. The amplitude and phase shift needed among the array elements are synthesized by loading with equivalent complex loads each element. In this way, the real and imaginary parts of the element's impedance can be tuned to build the desired current. The initial ap complex coefficients is transformed then in a set of impedances Zp.

In our case of a two-element array, parasitic loading is quite straightforward, as only one load must be calculated. First, the two complex values a1 and a2 are normalized to the value a1 because represent the fed element. We are interested in the amplitude and phase shift of the second element compared with the first. Then the complex value a2,norm and the scattering matrix S are used to calculate the load Z2. This impedance is connected in series with the second element and provides the same effect of the full-drive excitation of a1 and a2 as separate excitations.

III. SINGLE SOURCE AND ARRAY DESIGN METHOD

The objective is the design of the highest possible gain antenna in a limited space of kr<1. End-fire arrays present compact dimensions and high gain. As revealed in the SotA of superdirectivity, dipolar-type radiators are preferred considering that they can be flexibly miniaturized without compromising radiation efficiency. Moreover, the results must be cheap and easy to fabricate, and for these reasons, a printed type of antenna is investigated. The design of a miniaturized electrical dipole, based on a co-sinusoidal bend of the two arms, and printed on a dielectric substrate is reported. Then, two configurations of two-element end-fire arrays of this new proposed element are investigated. By using the SWE analysis on the radiated field and the array optimization, the best configuration for maximum gain is chosen.

A. The cosine dipole

Dipole miniaturization can be done by bending the dipole's arms. This is equivalent as an increase in the electrical path of the current which allows to match the desired frequency. The employee of a cosine line geometry presents a smoother current path, and even for a 40% of total length reduction a radiation efficiency higher than 99% is observed. The cosine dipole is defined by three parameters, corresponding to the dimensions of the cosine function, assuming it written as cos( ) A b y ⋅ . One has that • the larger the value of b, the smaller the period and the distance between two maxima or minima are;

• the larger the value of A, the greater the amplitude of the cosine line;

• y is the direction where the line is shaped, and it varies from ymin to ymax, defining the vertical dipole length.

To match the interested frequency of 916 MHz the parameters A and b must be tuned. At first, for a fixed amplitude 16 ⁄ the effect of the parameter b is investigated. One can observe that the lower is b, the closer is the cosine to a straight line, and the return loss improve as the resonance frequency increase (Fig. 2). The choice of b affects the resonance and the length of the line, but not the overall length of the dipole, which is defined by ymax -ymin. The amplitude A scale up or down the line according to its value, and has also an effect on the resonance of the antenna (Fig. 2). Finally, the parameters are set as ymax -ymin = 0.3 (10 cm), A= 22 ⁄ (14.9 cm), and b=0.107. The substrate chosen is the Roger 5880 ( 2.2 r ε = ) with thickness 0.7 mm. The printed line is made of copper ( ) with a width of 2 mm and thickness 0.07 mm. The final geometry is presented in Fig. 1.

B. Two-elements array

The single element is none other than a dipole, as described in the previous section. The advantageous low profile permits the design of a two elements array within the radiansphere of an electrically small antenna (kr<1). The curved shape takes advantage of the available surface of the sphere, even if just on its central section (circle of radius 1 2 ⁄ ). It has been highlighted in Sections I and II that high gain is possible only when radiation efficiency is high, and element spacing is critical when lower than a certain threshold [START_REF] Tornese | A new method for endfire array gain optimization using spherical wave expansion[END_REF]. Therefore, two different array configurations, as illustrated in Fig. 3, have been investigated and compared. The first case favors the length of cosines-bended dipole's arm, but the two elements are very close to fit into the fixed sphere. The second case considers more distant elements, and a further length reduction of the arms to fit in the same sphere.

C. Gain optimization and simulated results

In the first case, the two elements have a central axe-tocentral axe distance of 0.06 . The overall length of the dipoles is reduced by 38%. The configuration is illustrated in Fig. 3 with green lines. The structure is symmetric and the spherical modes can be more evenly excited. When the gain optimization method of Section II is applied, the SWE of the total array field is depicted in Fig. 3. One can distinguish the 4. Geometry of the two elements cosine-dipoles mirrored to the feeding point. The zooms highlight the feeding port of the active elements and the parasitic loading of the second one.

TE and TM components of n=1 fully excited, and the excitation of the TM mode of n=2. The power distribution is the one of two dipoles closely spaced, as demonstrated in [START_REF] Debard | On the maximum end-fire directivity of compact antenna arrays based on electrical dipoles and Huygens sources[END_REF]. All the modes are evenly excited, which means that the energy shared between the excited modes and it results in stable radiation. The simulated patterns of the realized gain the Eand H-planes are illustrated in Fig. 5. In this case, a directivity of 7.1 dBi and a gain of 6.5 dBi are observed. The second case considers, in the same radiansphere, a more distant element disposition. The central axe-to-central axe distance is of 0.17 . To make the dipoles fit in the sphere, the cosines-line miniaturization is increased by up to a 46% reduction of the total dipole length, as illustrated in Fig. 3 (red lines). The efficiency observed is still close to the unity, but this configuration presents a different modal distribution when the gain is optimized (Fig. 3). The excited modes are the same, but the power is not evenly distributed compared to the first case. In particular, for n=1 the TM mode has the 19% of power, and the TE mode the 45% of power. This unbalance is the result of the increased element-spacing. Considering a dipole centered in the origin of the coordinate system and oriented along the y direction, it is known from its SWE that by shifting along the z direction TE modes components appear. Then, the resulting modal distribution differs from the optimal one which sees the TE and TM modes of n=1 equally excited (Huygens source). The dipole miniaturization is also responsible, since the total length is decreased, and the cosine-line miniaturization squeezes the arms over each other and makes the line closer to a loop, further enhancing the TE mode excitation. The radiation patterns in E-and H-planes of the realized gain is illustrated in Fig. 5. The directivity observed is 5.4 dBi and the gain of 5.3 dBi. In the latter case, directivity and gain are very close, telling us that the problem is not related to efficiency, but to the way it possible to excite the modes in the radiating structure.

IV. DISCUSSION AND CONCLUSIONS In this paper, the process of synthesis of a supergain endfire arrays is discussed, highlighting the difference with the optimization of directivity. Then, the design process of a compact and high-gain array is described. Firstly, a new printed cosine-dipole antenna is shown. Then, two different configurations of two-element arrays are analyzed, representing the compromise between single-element size and interelement spacing, at a fixed radiansphere of kr=1. With the help of SWE, it was possible to maximize the gain and show the different power distribution of the radiated modes in the two cases, determining the causes of the difference in performances. It is noted that a homogeneous power distribution returns a higher gain. Moreover, the result obtained for the directivity is close to the limits found in [START_REF] Debard | On the maximum end-fire directivity of compact antenna arrays based on electrical dipoles and Huygens sources[END_REF] for dipole-based end-fire arrays, but with a surprisingly high level of realized gain. One can then again verify Uzkov's assertion, with directivity being more important the closer the elements are together. What is remarkable here is that this can be equally valid for gain, if certain design conditions occur. In particular, the first case with a reduced element spacing and 36% of dipole miniaturization shows a realized gain in simulations of 6.5 dBi, making this compact array of kr=1 a supergain planar antenna. This value surpasses the Chu-Harrington limit that this size is set to 4.77 dBi, and the Kildal-Best limit set to 6 dBi.

  η0 being the complex impedance of the vacuum and , sm n p Q the spherical wave coefficients for each of the p=1,…,P elements. The term smn  denotes the triple sum over the indexes s,m,n. The degree n can be truncated to a Nmax normally proportional to the size of the sphere, while the order m is limited by m n≤ . The index s=1,2 indicates TEor TM-modes, respectively. According to[START_REF] Tornese | A new method for endfire array gain optimization using spherical wave expansion[END_REF]

r

  is the unit vector in the polarization direction, and the term ,

Fig. 1 .

 1 Fig. 1. Geometry illustration of the cosines-dipole printed antenna.

Fig. 2 .

 2 Fig. 2. Parametric results of the S11 modifying the parameter (top figure) and b (bottom figure) of the cosine microstrip line.

Fig. 3 .

 3 Fig. 3. Two possible element geometry and disposition fitting in the radiansphere of kr=1. On the right the power distribution of the SWE for Cases 1 and 2 when the gain is optimized. TE modes are shown in red bars (first line) and TM modes in blue bars (second line).

Fig. 5 .

 5 Fig. 5. Simulated (CST Microwave Studio) radiation patterns in E-and Hplanes at 916 MHz for the two cases. Cosine-dipoles are closely spaced in Case 1 and farther apart in Case 2.

Fig. 6 .

 6 Fig. 6. Analytical reconstruction in MATLAB of the 3D Gain radiation pattern from the SWE coefficients for the two cases.

ACKNOWLEDGMENT

The authors would like to thank Dr. HDR P. Pouliguen and Dr. P. Potier for their useful comments on the work presented in this manuscript. This work is partially supported by the DGA (Direction générale de l'armement) and by the French National Research Agency through the project "COMET5G" under the grant ANR-19-CE24-0010-01.