Mirko Fiacchini
email: mirko.fiacchini@gipsa-lab.fr

Irinel-Constantin Morȃrescu
email: constantin.morarescu@univ-lorraine.fr

Convex conditions on decentralized control for graph topology preservation

Keywords: Interconnected systems, set-theory, consensus, decentralized control

The paper focuses on the preservation of a given graph topology which is usually chosen to ensure its connectivity. This is an essential ingredient allowing interconnected systems to accomplish tasks by using decentralized control strategies. We consider a networked system with discrete-time dynamics in which the subsystems are able to communicate if an algebraic relation between their states is satisfied. Each subsystem is called agent and the connected subsystems are called neighbors. The agents update their state in a decentralized manner by taking into account the neighbors' states. The characterization of the local control feedback gains ensuring topology preservation is provided. The results are based on invariance and set-theory and yield to conditions in Linear Matrix Inequality (LMI) form. The conditions for topology preservation are applied to an illustrative example concerning partial state consensus of agents with double integrator dynamics.

I. INTRODUCTION

Multi-agent systems have been used in the last decade to model different dynamics occurring in a large panel of applications going from biology and medicine to transportation, communication and sociology. It has also been emphasized that controlling interconnected systems in a decentralized manner [START_REF] Jadbabaie | Coordination of groups of mobile autonomous agents using nearest neighbor rules[END_REF], [START_REF] Olfati-Saber | Consensus problems in networks of agents with switching topology and time-delays[END_REF], [START_REF] Ren | Consensus seeking in multiagent systems under dynamically changing interaction topologies[END_REF] has advantages related to the computation and communication cost reduction. On the other hand the changes of the network topology may hamper the global coordination goal. To avoid this, recent works have been oriented towards the connectivity preservation of the interconnection graph of mobile networks [START_REF] Bullo | Distributed Control of Robotic Networks[END_REF], [START_REF] Zavlanos | Distributed connectivity control of mobile networks[END_REF]. In [START_REF] Martin | Sufficent conditions for flocking via graph robustness analysis[END_REF] the authors compute a robust connected spanning subgraph which allows the highest degree of freedom for the agents position and find the initial states (position and velocities) assuring the graph preservation. Starting from this idea, in this paper we present conditions for network topology preservation. Note that the procedure may be designed for dynamic graph topologies with the intersection given by the core graph to be preserved.

The main contribution of this paper is the characterization of the control laws preserving a given graph. As in [START_REF] Zavlanos | Distributed connectivity control of mobile networks[END_REF], the primary aim of our method is not a given global coordination objective. However, the controllers that pursue secondary global objectives, as flocking or rendez-vous, can be selected among those ensuring the graph topology preservation.

We consider a networked system with discrete dynamics and a given interconnection topology. The subsystems are able to communicate if an algebraic relation, defined in the next section, between their states is satisfied. The connected subsystems are called neighbors. The subsystems update their state in a decentralized manner by taking into account their neighbors states. Each connection is preserved as far as the algebraic relation is verified. Our aim is to characterize the decentralized control laws that ensure the satisfaction of the algebraic constraint. The design of the decentralized controllers satisfying the algebraic constraint can be done either by minimizing a cost function [START_REF] Fiacchini | Set theory based condition in LMI form for network topology preservation for decentralized control[END_REF], or by negociations through the network at each step [START_REF] Ferrari-Trecate | Model predictive control schemes for consensus in multi-agent systems with single-and double-integrator dynamics[END_REF]. Our approach use invariance based techniques (see [START_REF] Basile | Controlled and Conditioned Invariants in Linear system Theory[END_REF]- [START_REF] Blanchini | Set-Theoretic Methods in Control[END_REF] for the use of invariance in control theory) to characterize the conditions assuring that the algebraic constraint holds. The resulting topology preservation conditions rewrites as a convex constraint that may be posed in LMI form. Thus, we not only propose a new tool for decentralized control but also an easy implementable one.

Notation

The set of positive integers smaller than or equal to the integer n ∈ N is denoted as N n , i.e. N n = {x ∈ N : 1 ≤ x ≤ n}. Given the finite set A ⊆ N n , |A | is its cardinality. Given a symmetric matrix P ∈ R n×n , notation P > 0 (P ≥ 0) means that P is positive (semi-)definite. By A † we denote the left pseudoinverse of the matrix A. Given the matrix T ∈ R n×m and N ∈ N, diag N (T ) ∈ R nN×mN is the blockdiagonal matrix whose N block-diagonal elements are given by T , while diag(A, B, ..., Z) is the block-diagonal matrix, of adequate dimension, whose block-diagonal elements are the matrices A, B, ..., Z. Given a set of N matrices A k with k ∈ N N , denote by {A k } k∈N N the matrix obtained concatenating A k in column. Given a square matrix A, λ max (A) denote the maximal eigenvalue of A.

II. PROBLEM STATEMENT

Throughout the paper we consider a system consisting of V ≥ 2 interconnected subsystems assumed identical, whose states have dimension n ∈ N. Each subsystem is referred to as agent. Let us suppose that the initial interconnection topology is given by the graph G = (V , E ) where the vertex set is V = N V and the connecting edge set E ⊆ V × V represents the set of pairs of agents that satisfy a distance-like condition. Precisely, for given r > 0, d ∈ N, d ≤ n and T ∈ R d×n with T T ⊤ invertible, the initial edge set is given by

E = {(i, j) ∈ N V × N V | T (x i (0) -x j (0)) 2 < r},
where x i and x j are the states of the i-th and j-th agents, respectively. Since T is a matrix, i.e. a linear application, the graph G is undirected, which means that (i, j) ∈ E ⇔ ( j, i) ∈ E .

In the sequel we denote by N ⊆ E the set of edges that must be preserved. Hence, it is sufficient to suppose that every agent i knows the state of the j-th one if (i, j) ∈ N . Definition 1: For all i ∈ V we define the set of connected neighbors of the i-th agent as

N i = { j ∈ N V : (i, j) ∈ N }.
The dynamics of each agent is given by

x + i = Ax i + Bu i , (1)
for all i ∈ N V , with A ∈ R n×n , B ∈ R n×m and where x i ∈ R n is the state and u i ∈ R m is the control input of the i-th agent. As usual in multi-agent systems, the interconnection appears in the control input u i which is designed by taking into account not only the state x i but also the states x j , for all j ∈ N i .

In order to clarify the concepts let us consider a network of mobile agents moving in a two dimensional space which are able to select the variation of their velocity. Modelling the input as a velocity variation or, equivalently, the variations along the two Cartesian axis, the dynamics of the i-th agent, with i ∈ N V , along the x axis is given by

p x i (k + 1) = p x i (k) + tv x i (k), v x i (k + 1) = v x i (k) + u x i (k), (2)
where p x i is the position, v x i the velocity, u x i the control input and t the sampling time. So, the overall dynamics of the i-th agent along the x axis is given by a linear system with matrices

Ā = 1 t 0 1 , B = 0 1 .
The dynamics along the y axis are clearly analogous. Then the full dynamics of the i-th agent is given by (1) with

A = Ā 0 0 Ā , B = B 0 0 B , where the state is x i (k) = [p x i (k), v x i (k), p y i (k), v y i (k)] ⊤ and the input u i = [u x i , u y i ] ⊤ .
Supposing that the agents can communicate only if the euclidean distance between them is smaller than r, is equivalent to define T as the projection T x i (k) = [p x i (k), p y i (k)] ⊤ . Given the set of connections N , the objective is to design a decentralized control law ensuring that none of these connections is lost. Thus, the objective can be posed in terms of the error dynamics between connected neighbors:

e + i, j = x + i -x + j = A(x i -x j ) + B(u i -u j ), (3)
for all (i, j) ∈ N . In the sequel, the i-th input is defined by

u i = ∑ j∈N i K i, j (x i -x j ) = ∑ j∈N i K i, j e i, j , (4)
with the controller gains K i, j depending on the current states and chosen such that the link (i, j) is preserved. Thus, the design of each u i is reduced to the design of the controller gains associated to each i, j system:

e + i, j = (A+ BK i, j + BK j,i )e i, j + k = j ∑ k∈N i BK i,k e i,k - k =i ∑ k∈N j BK j,k e j,k , (5)
for all (i, j) ∈ N . Remark 1: Our objective is to characterize the feedback gains involved in ( 5) such that the link (i, j) is preserved. Since such a characterization must be shared by the i and the j agents to be useful in the decentralized context, only the information common to both of them should be involved. Such information consists in the states of the i and j agents and of those of the common neighbors. The shared information on the non-common neighbors reduces to their number (and implicitly a bound on their position). Such knowledge is used for determining a bound on the effect of the non-common neighbors on the i, j system, as shown in the following.

The dynamics of the i, j system is given by the matrix A + BK i, j + BK j,i if no interaction with the other agents is present. The perturbation on the i, j system induced by such an interaction can be bounded within a set depending on the radius r and on the knowledge of common neighbors of the i-th and j-th agents. Consider the sets

N i, j = N i ∩ N j , Ni, j = N i \ (N i, j ∪ { j}), N j,i = N j \ (N i, j ∪ {i}), (6)
then, N i, j denotes the common neighbors of the i-th and the j-th agents and Ni, j the neighbors of the i-th one which are neither j nor one of its neighbors, analogously for N j,i . The elements of Ni, j ∪ N j,i are referred to as the non-common neighbors of the i, j system. The dynamics of the i, j system, perturbed by the non-common neighbors, is

e + i, j = (A + BK i, j + BK j,i )e i, j + ∑ k∈N i, j (BK i,k e i,k -BK j,k e j,k ) + w i, j , (7)
with the bounded perturbation described by

w i, j = ∑ k∈ N i, j (BK i,k e i,k ) -∑ l∈ N j,i (BK j,l e j,l ). (8)
For all the neighbors of the j-th and the i-th agents, the following relations hold

Te i,k 2 ≤ r, if k ∈ N i, j , Te j,k 2 ≤ r, if k ∈ N j,i . (9)
The problem addressed in this paper can be stated as follows.

Problem 1: Design a procedure to find at each step a condition on the decentralized control gains K l,k , with l, k ∈ N V in ( 7) and ( 8) such that the following algebraic relation is satisfied

Te + i, j 2 < r, ∀(i, j) ∈ N . (10)

III. CONVEX CONDITIONS FOR TOPOLOGY PRESERVATION

In the following, we restrict the study to the generic i, j system with (i, j) ∈ N . In this way, Problem 1 reduces to a set of simpler problems as explained below.

Problem 2: Given the i, j system ( 7) and ( 8) with (i, j) ∈ N , pose a condition on the gains K i,k , with k ∈ N i , and K j,l , with l ∈ N j , such that the following algebraic relation is satisfied

Te + i, j 2 < r, ( 11
)
if Te i,k 2 ≤ r, Te j,l 2 ≤ r for all e i,k , k ∈ N i and e j,l , l ∈ N j . Let us consider the 2|N |-uples of gains K i, j , (i, j) ∈ N ordered lexicographically. We suppose that the Problem 2 is solved for the link (i, j) and the solution is given by Sol i j , the set of all tuples of gains satisfying its conditions. A solution of Problem 1 is then obtained by applying the following decentralized algorithm:

Algorithm 1 Solving Problem 1 Input: value r, distance matrix T , the set N , the set V 1: initialize x 2: for i ∈ V do 3:
for j ∈ N i do end if 8: end for Remark 2: It is important to recall that in this paper we provide only necessary conditions and sufficient ones for the existence of controllers preserving the graph topology. Due to local knowledge it is clear that agent i can only find conditions to preserve its own links. The design of the controllers preserving the whole topology can be done by minimizing cost functions that may be also related to a secondary agreement goal (see Section IV).

Definition 2: Given ( 6), ( 7) and ( 8), define

N = 2|N i, j | + 1, N = | Ni, j | + | N j,i |, E i, j = {e i,k } k∈N i, j , E j,i = {e j,k } k∈N i, j , E = [e ⊤ i, j , E ⊤ i, j , E ⊤ j,i ] ⊤ ∈ R nN , Z = diag N (T ) E ∈ R dN , Ǩi, j = [{K ⊤ i,k } k∈N i, j ] ⊤ , Ǩj,i = [{-K ⊤ j,k } k∈N i, j ] ⊤ , ∆ = T [A + B(K i, j + K j,i ), B Ǩi, j , B Ǩj,i ] diag N (T ) † ∈ R d×dN , Ēi, j = {e i,k } k∈ N i, j , Ē j,i = {e j,k } k∈ N j,i , Ē = [ Ē⊤ i, j , Ē⊤ j,i ] ⊤ ∈ R n N , Z = diag N (T ) Ē ∈ R d N , Ki, j = [{K ⊤ i,k } k∈ N i, j ] ⊤ , Kj,i = [{-K ⊤ j,k } k∈ N j,i ] ⊤ , Γ = T [B Ki, j , B Kj,i ] diag N (T ) † ∈ R d×d N .
(12) Notice that E, Z and ∆ are two vectors and a matrix which are functions of the states and the gains of the i, j system and its common neighbors; Ē, Z and Γ concern the states and gains of the non-common neighbors of the i, j system. The dependence of N, N, E, Z, ∆, Ē, Z and Γ on the indices i, j is omitted to simplify the notation. Using Definition 2, we have that Te + i, j = ∆Z + Γ Z and then the algebraic constraint ( 11) is equivalent to

[∆ Z + Γ Z] ⊤ [∆ Z + Γ Z] < r 2 , ( 13
)
and the uncertainties bounds are given, in the terms of Z, by

Z⊤ D k Z ≤ r 2 , ∀k ∈ N N , (14)
from ( 9), for all k ∈ N N , with

D k = diag(0 d , . . . , 0 d , I d , 0 d , . . . , 0 d ) ∈ R d N×d N ,
where I d ∈ R d×d is the identity, 0 d ∈ R d×d is the zero matrix and k indicates that I d is the k-th block of D k . Remark 3: We have shown that Problem 2 is equivalent to: (13) is satisfied for every Z ∈ R d N fulfilling (14).

A. Necessary condition for network preservation

In this section we derive some bounds on the gains associated to the non-common neighbors that are necessary for the feasibility of Problem 2. In other words, we look for constraints on the matrix Γ that hampers the existence of admissible realizations of the uncertainty Z which lead to the break of the (i, j) link.

Consider the matrix Γ ⊤ Γ which is real, symmetric, positive semidefinite and block diagonal, i.e. there are M k ∈ R d×d , with k ∈ N N , real, symmetric and positive semidefinite such that Γ ⊤ Γ = diag(M 1 , . . . , M N ). Then there exist G k ∈ R d×d diagonal and H k ∈ R d×d unitary, for all k ∈ N N , such that

Γ ⊤ Γ = diag(M 1 , . . . , M N ) = diag(H ⊤ 1 G 1 H 1 , . . . , H ⊤ N G N H N ) = H ⊤ GH, ( 15
)
with

G = diag(G 1 , . . . , G N ) and H = diag(H 1 , . . . , H N ) such that HH ⊤ = I d N .
[∆ Z + Γ Z] ⊤ [∆ Z + Γ Z] ≥ r 2 , (16)
for all Z ∈ R dN and ∆.

Proof: Given Γ ⊤ Γ as in (15), denote with λ k the maximal eigenvalue of M k , i.e. λ k = λ max (M k ), and suppose with no loss of generality that λ k is the first element of the diagonal of G k , for every k ∈ N N . Defining with h k ∈ R d an eigenvector of norm one related to λ k we have H k h k = [1, 0, . . . , 0] ⊤ , for all k ∈ N N .

Suppose that

∑ k∈N Nλ k ≥ 1 and choose Z = r{h k } k∈N N ∈ R d N . We have that Z⊤ D k Z = r 2 h ⊤ k h k = r 2 , (17)
for all k ∈ N N , thus Z fulfills (14). Moreover

Z⊤ Γ ⊤ Γ Z = Z⊤ H ⊤ G H Z = r 2 ∑ k∈N N [1, 0, . . . , 0]G k [1, 0, . . . , 0] ⊤ = r 2 ∑ k∈N N λ k ≥ r 2 . (18)
Notice that (17) and (18) do not depend on the sign of Z. Thus, for all Z and ∆ there exists an adequate selection of the sign of Z such that

Z ⊤ ∆ ⊤ ∆ Z + 2 Z⊤ Γ ⊤ ∆ Z + Z⊤ Γ ⊤ Γ Z ≥ Z⊤ Γ ⊤ Γ Z. ( 19
)
Actually, the first term in (19) is always nonnegative and the second term in (19) becomes nonnegative by appropriately choosing the sign of Z. From (18) and (19) we have ( 16). An alternative necessary condition for the Problem 2 to have a solution, inspired by the comments of an anonymous reviewer, follows from the lemma below. This condition is employed in the next section to provide sufficient conditions for Problem 2 to admit solutions.

∑ k∈N Nλ k = ∑ k∈N Nλ max (M k ) + 0.5ε < ∑ k∈N Nλ max (M k ) + ε = 1.
For the sufficiency, suppose the existence of Λ that satifies (20) with ∑ k∈N Nλ k < 1. From the particular structure of Γ, (20) implies M k < λ k I d which yields λ max (M k ) < λ k , for all k ∈ N N . From this and ∑ k∈N Nλ k < 1, Assumption 1 follows. Remark 4: Given Λ as in Lemma 1, the quantity δ = ∑ k∈N Nλ k may be geometrically interpreted as a bound on the uncertainty. In fact, from Definition 2, condition (20) leads to

Tw i, j 2 2 = Z⊤ Γ ⊤ Γ Z < Z⊤ Λ Z = ∑ k∈N Nλ k Z⊤ D k Z ≤ ∑ k∈N Nλ k r 2 ,
for all e i,k , with k ∈ N i, j , and e j,k with k ∈ N j,i such that (9) holds. Precisely, the effect of the non-common neighbors can be modelled as a perturbation on the i, j system bounded by an ellipsoid determined by T ⊤ T and of radius √ δ r. Therefore the condition Γ ⊤ Γ < Λ results in a bound on the gains related to the non-common neighbors of the i-th and j-th agents. It can be interpreted as a joint limitation on the control efforts of the agents i and j aimed at regulating and preserving their other connections. Using the interpretation above, Proposition 1 may be reformulated as an intuitive result saying that: it is not possible to guarantee the "distance" constraint as far as the uncertainties are too large, i.e. Tw i, j 2 ≥ r.

B. Sufficient condition for network preservation

This section provides conditions on the gains Γ and Λ for guaranteeing the existence of solutions for Problem 2. In order to derive the sufficient condition we use the S-procedure (see [START_REF] Boyd | Linear Matrix Inequalities in system and control theory[END_REF] for further details). This commonly used procedure gives sufficient conditions in terms of LMI. An important contribution of this paper, namely the sufficient condition for the constraint [START_REF] Ren | Consensus seeking in multiagent systems under dynamically changing interaction topologies[END_REF] to hold, is stated in the following theorem.

Theorem 1 (Sufficient condition): Problem 2 admits solutions (i.e. condition [START_REF] Zavlanos | Distributed connectivity control of mobile networks[END_REF]

is satisfied for every Z ∈ R d N fulfilling (14) ) if there exists Λ = diag(λ 1 I d , . . . , λ N I d ) with λ k ≥ 0, for all k ∈ N N such that   r 2 -r 2 δ 0 Z ⊤ ∆ ⊤ 0 Λ Γ ⊤ ∆ Z Γ I d   > 0, (21)
with δ = ∑ k∈N Nλ k . Furthermore, any (∆, Γ) satisfying (21) defines admissible controller gains for the Problem 2.

Proof: First notice that every solution of (21) satisfies also

∑ k∈N Nλ k < 1, Γ ⊤ Γ -Λ < 0, ( 22
)
as the principal minors of a positive definite matrix are positive definite. Since ( 22) is a necessary condition for the Problem 2 to admit a solution, see Section III-A, there is no loss of generality in assuming it satisfied. Condition ( 13) is equivalent to

[Z ⊤ , Z⊤ ] ∆ ⊤ ∆ ∆ ⊤ Γ Γ ⊤ ∆ Γ ⊤ Γ Z Z < r 2 . ( 23
)
This condition must be satisfied for every Z such that (14) holds. Applying the S-procedure, a sufficient condition for [START_REF] Zavlanos | Distributed connectivity control of mobile networks[END_REF] to hold for every Z ∈ R d N satisfying ( 14) is the existence of λ k ≥ 0, for all k ∈ N N , such that

Z ⊤ ∆ ⊤ ∆ Z + 2 Z⊤ Γ ⊤ ∆ Z + Z⊤ [Γ ⊤ Γ -Λ] Z < r 2 -r 2 δ , ( 24
)
for every Z ∈ R d N . From ( 22) and Z being known, the lefthand side of ( 24) is a concave function in Z whose maximum is attained at

Z = -(Γ ⊤ Γ -Λ) -1 Γ ⊤ ∆ Z. ( 25
)
Hence condition (24) holds for every Z ∈ R d N if and only if it is satisfied for the maximum of the function at left-hand side, that is if and only if

Z ⊤ ∆ ⊤ ∆ Z -Z ⊤ ∆ ⊤ Γ(Γ ⊤ Γ -Λ) -1 Γ ⊤ ∆ Z < r 2 -r 2 δ , (26)
which is given by ( 24) at (25). Hence every Λ, ∆ and Γ satisfying conditions ( 22) and ( 26) ensure the satisfaction of Te + i, j 2 < r for all Z such that (14) holds. The condition (26) is equivalent to

Z ⊤ ∆ ⊤ ∆ Z -r 2 + r 2 δ Z ⊤ ∆ ⊤ Γ Γ ⊤ ∆ Z Γ ⊤ Γ -Λ < 0 ⇔ Z ⊤ ∆ ⊤ ∆ Z Z ⊤ ∆ ⊤ Γ Γ ⊤ ∆ Z Γ ⊤ Γ < r 2 -r 2 δ 0 0 Λ ⇔ Z ⊤ ∆ ⊤ Γ ⊤ ∆ Z Γ < r 2 -r 2 δ 0 0 Λ ⇔   r 2 -r 2 δ 0 Z ⊤ ∆ ⊤ 0 Λ Γ ⊤ ∆ Z Γ I d   > 0.
Thus ( 21) is equivalent to (24), sufficient condition for (13) to hold.

C. Guaranteed network preservation: common feedback gains

The condition presented in the previous subsection ensures that the algebraic constraint related to the i, j system is satisfied at the successive time instant. No insurance on its satisfaction along the evolution of the overall system can be guaranteed, unless proper choices of K i, j are done. In case the feedback gains are assumed to be the same for every agent and every i, j system, a sufficient condition for guaranteeing the network topology preservation at every future time instant can be posed.

Assumption 2: Given the system (1) with control (4), assume that K i, j = K for all (i, j) ∈ N .

The objective is to characterize the set of common feedback gains such that, if applied to control the multi-agent system, they ensure the non-increasing of the values Te i, j 2 for all (i, j) ∈ N . If the connection condition is satisfied by the initial condition, i.e. Te i, j (0) 2 ≤ r for all (i, j) ∈ N , the network topology preservation is iteratively guaranteed at every successive instant. Given the sets as in [START_REF] Ferrari-Trecate | Model predictive control schemes for consensus in multi-agent systems with single-and double-integrator dynamics[END_REF], define

N M = max (i, j)∈N {|N i | + |N j | -2}.
Then, for all (i, j) ∈ N , N M ∈ N is an upper bound of the number of agents different from i and j affecting the i, j system.

Proposition 2: Let Assumption 2 hold. If there exists λ ∈

[0, 1] such that λ T ⊤ T (A + 2B K) ⊤ T ⊤ T (A + 2B K) λ I d ≥ 0, (1 -λ )T ⊤ T N M K⊤ B ⊤ T ⊤ N M T B K (1 -λ )I d ≥ 0, (27)
then the systems given by ( 7) and ( 8) are such that Te + i, j 2 ≤ r for all (i, j) ∈ N if Te l,k 2 ≤ r for all (l, k) ∈ N .

Proof: Define the set B T = {e ∈ R n : Te 2 ≤ r}, then e ∈ B T if and only if e ⊤ T ⊤ Te ≤ r 2 . The first condition in ( 27) is equivalent to

(A + 2B K) ⊤ T ⊤ T (A + 2B K) ≤ λ 2 T ⊤ T , which implies that (A + 2B K)B T ⊆ λ B T .
From Assumption 2 one have that K i, j = K j,i = K, which means that A + 2B K is the dynamics of any i, j system in the absence of the perturbation of the neighbors. Then the set B T is mapped in λ B T if no perturbation is present, that is (A + BK i, j + BK j,i )e i, j ∈ λ B T , for all e i, j ∈ B T . Analogously, the second condition in ( 27) is equivalent to

N 2 M K⊤ B ⊤ T ⊤ T B K ≤ (1 -λ ) 2 T ⊤ T , which leads to ∑ k∈N N M B KB T = N M B KB T ⊆ (1 -λ )B T .
This means that if e i,k ∈ B T for all k ∈ N i \ { j} and e k, j ∈ B T for all k ∈ N j \ {i}, as implicitly assumed, then

∑ k∈N i, j (B Ke i,k -B Ke j,k )+ ∑ k∈ N i, j (B Ke i,k )-∑ l∈ N j,i (B Ke j,l )∈(1-λ )B T ,
for all (i, j) ∈ N . From properties of the Minkowski set addition, see [START_REF] Rockafellar | Convex Analysis[END_REF], we have e + i, j ∈ λ B T + (1 -λ )B T = B T , if e l,k ∈ B T for all (l, k) ∈ N , which ends the proof.

Proposition 2 characterizes the common gains that ensure the network topology preservation along the whole trajectories. An analogous sufficient condition for convergence follows.

Corollary 1: Let Assumption 2 hold. If there exist λ ∈ [0, 1] and λ > 0 such that

(λ -λ )T ⊤ T (A + 2B K) ⊤ T ⊤ T (A + 2B K) (λ -λ )I d ≥ 0, (1 -λ )T ⊤ T N M K⊤ B ⊤ T ⊤ N M T B K (1 -λ )I d ≥ 0,
then the systems given by ( 7) and ( 8) are such that

Te + i, j 2 ≤ (1 -λ ) Te i, j 2 , for all (i, j) ∈ N if e l,k ∈ R n satisfies Te l,k 2 ≤ r for all (l, k) ∈ N .
Hence the corollary provides a sufficient condition for the exponential convergence of the i, j system to the set Te 2 = 0, for all (i, j) ∈ N , if Te l,k (0) 2 ≤ r for every (l, k) ∈ N . Notice that this would imply Te + i, j 2 < r, strictly, as required in Problem 2.

Proposition 2 and Corollary 1 provide sufficient conditions on the local feedback gains for the recursive satisfaction of the algebraic constraints and for convergence, respectively. On the other hand, the price to pay for the recursive guarantee of constraints satisfaction (or of convergence) is a certain degree of conservativeness of the results in comparison with those of Theorem 1.

IV. APPLICATION TO DECENTRALIZED CONTROL OF MULTI-AGENT SYSTEMS

Let us consider the problem of flocking for a set of agents with the dynamics along the x axis given by ( 2) and similar one along y axis. We consider an interaction graph in which the euclidean distance between two neighbors is smaller than or equal to r. The matrix T defining the algebraic constraint to be preserved is

T = 1 t 0 0 0 0 1 t . (28)
Thus, denoting

∆p i, j = (p x i (k) -p x j (k)) 2 + (p y i (k) -p y j (k)) 2 1 2
we suppose ∆p i, j (k + 1) ≤ r and we determine the controllers ensuring ∆p i, j (k + 2) ≤ r. Among all these controllers we chose the one that minimize the difference between neighbors speeds, i.e. the value ∆v

i, j = (v x i (k) -v x j (k)) 2 + (v y i (k) - v y j (k)) 2 1 2 .
Let us consider the six interconnected agents with the initial conditions given in [START_REF] Martin | Sufficent conditions for flocking via graph robustness analysis[END_REF] and connected by the minimal robust graph computed in the same work. That is: N = {(1, 2), (2, 3), (3, 4), (4, 5), (5, 6)}, r = 3.2 and initial conditions:

x 1 (0) = [-4 -v 0 3 0] ⊤ , x 6 (0) = [4 v 0 3 0] ⊤ , x 2 (0) = [-2 -v 0 2 0] ⊤ , x 5 (0) = [2 v 0 2 0] ⊤ , x 3 (0) = [-1 -v 0 0 0] ⊤ , x 4 (0) = [1 v 0 0 0] ⊤ ,
where v 0 is used as a parameter to analyze the maximal initial speed that can be dealt with by different control strategies. It is noteworthy that, as shown in [START_REF] Martin | Sufficent conditions for flocking via graph robustness analysis[END_REF], for the classical consensus algorithm the preservation of the minimal robust graph is guaranteed for a critical speed value v c ≃ 0.23. Nevertheless, it is numerically shown that the sufficient condition is conservative since for v 0 = 1.5v c (generating approximately a 4 times higher global velocity disagreement) the robust graph is not broken. We also note that the classical consensus algorithm is not able to preserve the connectivity when the global disagreement is 5 times superior to the one guaranteeing the consensus (i.e. v 0 > 2.1v c ).

In the sequel, we use Theorem 1 to compute the sets of gains ensuring the topology preservation. The choice of the controllers gain within these sets is done heuristically by minimizing a cost function that expresses the velocity disagreement and penalizes the links break. This strategy has admissible solutions for v 0 = 19v c (see Figures 1,2) and the connection between the third and the fourth agent is lost for v 0 = 20v c . It is worth noting that the control acts like springs between agents' velocities (compare the Figures 1 and2, noticing that the system 1, 2 has the same evolution as the 5, 6 and the 2, 3 the same as 4, 5, by symmetry). First, the control cancels the speed difference between neighbors with opposite velocities creating a speed disagreement in both symmetric branches of the graph. Next, it cancel the disagreement between 2-nd and the 3-rd agent and between the 4-th and 5-th one, mimicking a gossiping procedure where the choice of active communication link is given by the error between neighbors speeds. Doing so, either the flocking is reached before the connectivity is lost, or the graph splits into two groups that will independently agree to two different velocity values.

V. CONCLUSION AND FURTHER WORKS

In this paper we have provided necessary conditions and sufficient ones in terms of controller gains for the preservation of a given graph topology. These conditions are written as a convex constraint that may be posed in LMI form allowing an easy implementation of the controller design. An illustrative example shows how the procedure can be applied to achieve both the topology preservation and an additional global objective which is in this case the partial state consensus. In this example our controller allows to solve the coordination problem for a set of initial conditions that is larger than the one existing in the literature.

Lemma 1 :

 1 The matrix Γ satisfies Assumption 1 if and only if there exists Λ = diag(λ 1 I d , . . . , λ N I d ) with λ k ≥ 0 and∑ k∈N Nλ k < 1 such that Γ ⊤ Γ < Λ.(20) Proof: For the necessity, suppose that Assumption 1 holds. Denote ε = 1 -∑ k∈N Nλ max (M k ) > 0 and define Λ with λ k = λ max (M k ) + 0.5ε/ N. Clearly (20) holds and

Fig. 1 .

 1 Fig. 1. Trajectories (top) and errors of the systems 1,2 and 5,6, (bottom).

Fig. 2 .

 2 Fig. 2. Errors of the systems 2,3 and 4,5 (top) and the 3,4 one (bottom).

  The diagonal entries of G k (resp. of G) are the eigenvalues of M k (resp. of Γ ⊤ Γ) and the columns of H ⊤ The matrix Γ is such that ∑ k∈N Nλ max (M k ) < 1. The necessity of Assumption 1 is proved below.Proposition 1 (Necessary condition): If Assumption 1 does not hold, then there is Z ∈ R d N such that (14) holds and

k

(resp. of H ⊤ ) are the related eigenvectors, for all k ∈ N N . All the eigenvalues are nonnegative.

Assumption 1:

This work has been partially founded by the Lorraine region's grant: "Analyse et conception de lois de commande pour des systèmes interconnectés".


Tetsuya Odajima

Taisuke Boku

Mitsuhisa Sato

Toshihiro Hanawa

Yuetsu Kodama

Raymond Namyst

Samuel Thibault

Olivier Aumage

Adaptive Task Size Control on High Level Programming for GPU/CPU Work Sharing

établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

While GPU clusters with high performance GPUs provide cost effective HPC environment, still there is a serious problem on programming for users who are forced to describe complicated codes with mixed paradigm on parallel processing and GPU computing. Recent programming codes on a modern PC cluster commonly described in a hybrid manner to combine MPI and OpenMP to exploit the parallelism of resources effectively. In addition on GPU clusters, the programmers additionally have to describe GPU manipulation. As a result, large scale parallel GPU programming on GPU clusters becomes the toughest work on parallel processing which easily causes numerous coding errors and reduces code productivity.

We have been developing a language named XcalableMP (hereinafter called XMP for short) [2], which is a directive-based PGAS (Partitioned Global Address Space) language for parallel systems with distributed memory architecture. In addition to the original XMP specification, we also proposed an extension of XMP for accelerating device programming environments such as CUDA or OpenCL, named XcalableMP-dev [START_REF] Lee | An Extension of Xcal-ableMP PGAS Lanaguage for Multi-node GPU Clusters[END_REF] (hereinafter called XMP-dev for short), which employs the concept of XMP by supporting a feature to off-load the computation of a specified section (loop) to the target accelerating devices.

In our previous work [START_REF] Odajima | GPU/CPU Work Sharing with Parallel Language XcalableMP-dev for Parallelized Accelerated Computing[END_REF], we utilized both GPU and CPU resources on each node for work sharing of the loop execution within the context of the XMP-dev language. For this purpose, we apply StarPU [START_REF] Starpu | [END_REF] for sub-task management and scheduling where a loop execution is divided into a number of sub-tasks for multiple GPUs and CPU cores on each computation node. Based on this concept, we implemented XcalableMP-dev/StarPU (hereinafter called XMP-dev/StarPU for short) which enables the loop-level work sharing among CPU cores and GPU on each computation node while the framework of XMP. In some cases, we confirmed that this new feature improves the performance of GPU clusters with additional power by CPU cores rather than using GPU only, with very simple and easy programming for high productivity. In many cases, however, the performance gain with GPU/CPU work sharing is not enough as estimated. The basic problem is how to decide the task size to be assigned to CPU cores and GPUs which has different characteristics on the performance.

In this paper, to solve this problem, we propose a new framework to control the task size to be dispatched to heterogeneous devices (CPU cores and GPUs) individually and dynamically. In this method, we can keep the execution time on each device as almost the same by dispatching different size of tasks to them even with a limited but moderate number of tasks according to the problem size.

2 XcalableMP, XcalableMP-dev and StarPU

Overview of XcalableMP (XMP)

XMP [START_REF] Lee | Implementation and Performance Evaluation of XcalableMP: A Parallel Programming Language for Distributed Memory Systems[END_REF] is a PGAS language for describing large-scale scientific code on parallel systems with distributed memory architecture. For simplification for easy understanding, XMP is a directive-based parallelizing language with grammar similar to that of OpenMP. And its concept came from HPF [START_REF]High Performance Fortran Version 2.0[END_REF] for global array distribution and work sharing on loop construction. It is possible to parallelize the target code with just a few changes on the original serial code, thus the programming effort can be significantly reduced compared with many additional lines in MPI programming.

XcalableMP-dev (XMP-dev)

In addition to XMP directives (please refer [START_REF] Lee | Implementation and Performance Evaluation of XcalableMP: A Parallel Programming Language for Distributed Memory Systems[END_REF] in detail) which enable data/task parallelization between nodes in a distributed memory system, XMP-dev directives (please refer [START_REF] Lee | An Extension of Xcal-ableMP PGAS Lanaguage for Multi-node GPU Clusters[END_REF] in detail) enable further data/task parallelization between one or more acceleration devices on each node under the concept of off-loading the computation to them. Figure 1 shows an example of XMP-dev code. When a code is written in XMP-dev, XMP directives describe the distribution of data among. On each Fig. 1. An example code segment of XMP-dev node, with XMP-dev directives (starting with "#pragma xmp device"), the user can specify the data to be allocated on GPU device, data movement between CPU and GPU, and computation offloading to GPU an shown in Figure 1. This is a large advantage for highly productive coding compared with complicated orthogonal programming with MPI and CUDA mixture, and an incremental code enhancement is possible for users as like as OpenMP.

StarPU

In this subsection, we briefly describe the concept and features of StarPU. For more details of the StarPU system, please refer [START_REF] Starpu | [END_REF]. StarPU is a run-time system that allocates and dispatches a collection of computations as a task to any computation resource and schedules the task execution dynamically. The target computation resources include multicore CPUs and GPUs, where each task is dispatched to a core of the multicore CPUs or to GPU device(s).

Although StarPU manages the task execution on both CPU cores and GPUs simultaneously, it is a critical issue how to decide the task size for GPUs and CPU cores to achieve high performance. The performance of recent CPUs has been increased to several hundreds of GFLOPS. However, there is still a big difference in the factor of ten between the performance of single CPU core and GPU. When there is a large number of tasks generated from a large scale data, tens or more times of tasks can be allocated to GPU device while CPU cores are processing small number of them. However, it is impossible to keep the load of them when the number of tasks is limited for a small size problem, and it causes a serious situation where even the additional CPU cores become the bottleneck in total execution time.

StarPU is equipped with a feature to anneal the task size automatically when the task size (the data size associated with the task) is tuned step-by-step during the code execution in the iteration of time step simulation. However, this feature works only for cases with simple iterations of code, and it is difficult to apply this feature to a complicated execution phase of general codes. It is especially difficult when a computation node is equipped with multiple GPU devices and the performance gap between the CPU part and the GPU part is really large.

Dynamic Load Balancing on XMP-dev/StarPU

Our previous implementation without dynamic load balancing feature among GPUs and CPU cores are described in [START_REF] Odajima | GPU/CPU Work Sharing with Parallel Language XcalableMP-dev for Parallelized Accelerated Computing[END_REF] in detail. In this section, we describe the essence of the work to understand our new feature, then introduce a dynamic load balancing feature on XMP-dev/StarPU.

Previous Implementation Strategy and Its Performance

To implement the feature of work sharing among GPUs and CPU cores for loop execution, we modified the XMP-dev compiler and the run-time system to utilize StarPU as the task scheduler and execution engine. Since the original XMP-dev/CUDA compiler is ready for data distribution and parallel execution management of basic XMP features for GPU clusters, we run StarPU on each node in the single node mode for simplicity. The XMP-dev/CUDA compiler generates a code with CUDA functions on each node, and the data distribution and synchronization among multiple nodes are performed by MPI. Local array and Replicated array accordingly in XMP-dev syntax.

In [START_REF] Odajima | GPU/CPU Work Sharing with Parallel Language XcalableMP-dev for Parallelized Accelerated Computing[END_REF], we observed that the relative performance gain by XMP-dev/StarPU to XMP-dev/CUDA is very low in many cases, at a performance with just around 45% of original XMP-dev/CUDA. This is because the task size is always constant where Replicated array on the node is always divided equally over all tasks. But the performance gap among GPU and CPU core is so large. Therefore, much larger number of tasks should be assigned to GPU than CPU core to keep the execution time balance among all computation resources. In many cases, however, there is a limit of the number of total tasks because too small size of tasks cannot be effectively executed by GPU to hide the task invocation cost including data movement between CPU and GPU. As a result, we cannot create an appropriate number of tasks to keep a good load balance between these heterogeneous resources and the efficiency of GPU execution, in a moderate size of problem. Thus, we concluded the essential problem of low performance in this work is the task size control on GPUs and CPU cores.

Improvement of XMP-dev/StarPU with Dynamic Load

Balancing Feature

Previous XMP-dev/StarPU divides Replicated arrays with fixed task size whereas the performance gain by additional CPU cores to GPUs is not enough due to performance imbalance on different type of resources. We found the problem in [START_REF] Odajima | GPU/CPU Work Sharing with Parallel Language XcalableMP-dev for Parallelized Accelerated Computing[END_REF] and performed a preliminary study to observe the performance behavior when the task size to be assigned CPU cores and GPUs differ to keep a good load balance. According to this study, we propose and implement a new feature for dynamic load balancing in this paper.

The key of task size control is the performance gap between CPU and GPU. In heterogeneous hybrid work sharing, CPU and GPU execution time for each task should be close or in the same order at least. On the other hand, it is required to allocate a large size of task to GPU since it has to tolerate a data transfer overhead and have a large degree of parallelism to utilize a number of cores inside the device. The best solution for this problem is to assign well balanced task size for all GPU and CPU cores in each of Replicated array to be processed in a loop.

As the answer to this problem, we introduce a parameter to decide the balance of working set size for GPU and CPU on loop work sharing, named "CPU Weight". To simplify the control of load balance on resources, we decided to apply this value to divide a Replicated array into two parts which are processed by GPUs and CPU cores before StarPU run-time system makes further subdivision of each part of array. Figure 2(b) shows the image of dividing a Replicated array where the blue part is a relatively small portion for CPU cores while the red part is a large portion for GPUs, for the total number of array elements N. This array corresponds to the Replicated array in Figure 2(a). These two parts are further divided by StarPU to smaller size of tasks. By making the data structure appropriately to bind the task data portion and computing resource in StarPU framework, we can control the task dispatch for sub-divided data portion in each side (blue or red) so as to be correctly assigned to CPU core or GPU, respectively. In Figure 2(b) for example, StarPU divides each array into three parts. In this way, we can allocate different size of tasks to heterogeneous resources to keep the load balance controlled by CPU Weight.

Since it is difficult to set the value of CPU Weight automatically by the system, we design the system where this value is decided and set by the user explicitly in the program code. It is described by new pragma "reset weight" as "#pragma xmp device reset weight (cpu weight)". Here, cpu weight provides the CPU Weight to be applied after this point until it is reset again. The user can reset CPU Weight anywhere before entering a loop construction. There are several use cases of this feature. A user may decide to set the CPU Weight statically according to his knowledge on program behavior, or he can adaptively apply it based on the program execution behavior with any hint. Since the CPU Weight is applied to divide a Replicated array linearly into just two parts for GPU and CPU as shown in Figure 2(b), it is still difficult to find the best value of it to keep perfect load balance. One of the effective ways is to find it based on dynamic profiling of execution time by GPU and CPU. Actually, it is possible to anneal the CPU Weight during multiple time steps for most of simulation codes with time development scheme.

There is an idea to imply such an adaptive optimization of CPU Weight into the run-time system to hide it from user's view, however, we think it is very sensitive parameter to role the entire load balance and it is better to pass its control to users for various applications. For example, the user can even keep several set of CPU Weight according to different loop body, and switch them to describe the "reset weight" pragma before entering to the different loop.

Performance Evaluation

We use a massively GPU cluster HA-PACS in University of Tsukuba for performance evaluation. The node specification is shown below. The CPU is Intel Xeon E5-2670 2.6 GHz (8 cores * 2 sockets) with Sandy Bridge architecture, and the GPU is NVIDIA Tesla M2090 (4 GPUs/node) with Fermi architecture. All nodes are connected with dual rails of InfiniBand QDR x4 by Fat-Tree topology with full-bisection bandwidth. In this evaluation, we use just two nodes because our purpose is to observe the behavior of adaptive load balance on each node for parallel execution. Although each node has 16 CPU cores per node, the management of each GPU consumes one thread on a CPU core in StarPU. So the number of CPU cores is "16 -(Number of used GPUs)" per node.

We evaluate two benchmark codes: N-Body and MM (Matrix-Matrix Multiplication). Since the program runs on just two nodes, the communication time on MPI which is automatically generated by XMP-dev/StarPU compiler is negligible (under 1%) for both benchmarks. Thus, we evaluate the computation time on each node including data transfer overhead between CPU and GPUs, without caring MPI communication overhead.

The purpose of this evaluation is to confirm the function of dynamic load balancing based on CPU Weight works correctly and to show the potential of any dynamic load balancing algorithm by the user. Therefore, we introduce a very simple annealing algorithm to modify CPU Weight dynamically in the time step development of the simulation. In all case of evaluation, CPU Weight is changed according to the computation time of each CPU core and GPU for the outer-most loop iteration. For N-Body, the outer-most loop corresponds to the time step of physics simulation. For MM benchmark, we assume that some size of matrix-matrix multiplication such as DGEMM routine in BLAS (Gotoblas [7] for CPU kernel and MAGMA blas [START_REF]PGI Accelerator Compiler[END_REF] for GPU) is executed repeatedly for larger computation. Therefore, the same size of matrix-matrix multiplication is repeated in MM and the computation time of one outer-most iteration is examined.

Based on rough estimation on sustained performance of up to four GPUs and 12 CPU cores in each node, we set the initial value of CPU Weight as 0.2. The policy to decide CPU Weight in the next time step is as follows. ratio = T CP U / (T CP U + T GP U ); if (ratio > 0.5) cpu weight -= 0.01; else cpu weight += 0.01; Here, T CP U and T GP U are the task execution time by CPU and GPU in last task execution, respectively. Those values can be directly extracted by our API function. This policy shows a very simple annealing algorithm to modify CPU Weight in step by step manner. Of course, the user can describe more sophisticated algorithm in any style.

Figures 3(a Finally, we show the total performance gain by GPU/CPU work sharing driven by our new system compared with the performance by GPU-only. Figures 4(a) and 4(b) show the relative performance to the execution with GPUonly for various cases, on N-Body and MM benchmarks, respectively. In N-Body, GPU/CPU work sharing constantly improves the performance although the ratio of gain differs in the cases. The largest gain with up to 20% is achieved for the smallest size of problem. Basically, the performance gain is reduced when the number of GPUs increases where the usable CPU cores are decreased as mentioned before. N-body benchmark is suitable for GPU computing where the sustained performance gap between GPU and CPU is large and the effect of additional CPU cores is relatively small for larger problem size. On the other hand for MM benchmark, the performance gain by GPU/CPU work sharing increases according to the problem size where the maximum gain with approximately 40% is achieved for the largest problem size using single GPU. In MM, the task ex-ecution time for the matrix size is shorter than N-Body, and the overhead of fine task control cannot be covered by the performance of additional CPU cores. When enough size of problem is provided, the contribution of CPU cores is great to raise the total performance of computation node.

Since current implementation of XMP-dev/StarPU compiler can handle just single dimension decomposition for multi-dimension arrays, the memory utilization and data movement efficiency is low. We think that this is one of the major factors for performance limitation. We are now developing multi-dimensional array decomposition to achieve higher performance in our system.

Related Works

There are several compilers for GPU accelerators, for example PGI Accelerator Compile [START_REF]PGI Accelerator Compiler[END_REF] and HMPP Workbench [START_REF]HMPP Workbench[END_REF]. These compilers provide a directivebased language for some accelerator including GPU. HMPP Workbench use CUDA or OpenCL for backend compiler. So, it is possible to program a hybrid work sharing with GPU and CPU, by inserting some directive in user code. However, the user has to describe additional MPI code with this complicated work sharing because the compiler just cares on a single node computation. Our XMP-dev/StarPU provides a sophisticated PGAS model programming for distributed memory system. Also, there is a work [START_REF] Agullo | Faster, Cheaper, Better a Hybridization Methodology to Develop Linear Algebra Software for GPUs[END_REF] that applies StarPU to BLAS (Basic Liner Algebra Subprograms) library designed for NVIDIA GPU. This work performs work sharing with GPU and CPU on library level. In the performance aspect, this work can obtain about four times performance enhancement compared with only single GPU at Cholesky decomposition by using Intel Nehalem X5560 6 cores and 3 NVIDIA FX5800. In the XMP-dev/StarPU framework, users can write a work sharing program code more flexibly, as for the problem can be written in loop distribution basically, not just with a limited function of such a library-based approach. We need to compare the performance of our approach with native implementation of MAGMA in the same class of libraries.

As the original work by StarPU research team, the load balance issue was studied [START_REF] Augonnet | StarPU: a Runtime System for Scheduling Tasks over Accelerator-Based Multicore Machines[END_REF]. From user's view point, it is difficult to describe a code directly with StarPU for GPU/CPU work sharing. Our approach is based on high-level PGAS language (XMP-dev) using StarPU as underlying supporting system. We have not modified StarPU itself to apply to our system, and our system can work as user friendly interface for StarPU feature.

Concluding Remarks

In this paper, we proposed and implemented a programming environment to enable GPU/CPU work sharing on our PGAS language XMP-dev compiler and run-time system to be applied to multi-GPU equipped PC clusters. The proposed system allows users to keep the load balance among GPUs and CPU cores on each node for adaptive tuning of work sharing performance. We confirmed the effectiveness of this approach through several HPC benchmarks and achieved up to 40% of performance gain compared with original GPU-only solution. To exploit this performance gain utilizing full computation resources on each node, the user just has to add several key directives to his original serial code to describe data distribution, loop distribution, GPU/CPU data movement and synchronization, without complicated combined paradigm of MPI and CUDA.

Our future work includes applying this system for wider variety of applications and larger systems, and also improves the performance based on multidimensional array dividing on global array handling.

Fig. 2 .

 2 Fig. 2. Implementation of XMP-dev/StarPU

Figure 2

 2 Figure 2(a) shows the execution flow of XMP-dev/StarPU. The basic strategy for implementation of XMP-dev/StarPU is as follows. -XMP-dev compiler aligns the distributed Global array to Local array for each node. -Runtime system replicates Local array as another one named Replicated array. Local array is for communication with MPI in the context of XMP, and Replicated array is a target of task assignment and management by StarPU. -Replicated array is allocated to StarPU's data pool and divided to a number of tasks which has the same size. Then, tasks are allocated to each device by the StarPU scheduler. -The programmer explicitly describes the synchronization on data between Local array and Replicated array accordingly in XMP-dev syntax.

Fig. 3 .Fig. 4 .

 34 Fig. 3. Transitions of CPU Weight

#pragma xmp nodes p(4) #pragma xmp template t(0:N-1) #pragma xmp distribute t(BLOCK) onto p #pragma xmp align [i] with t(i) :: x, y

	1	int x[N], y[N];
	2
	3
	4
	5
	6
	7
	8	int main() {
	9	int i;
	10
	11	#pragma xmp loop on t(i)
	12	for (i = 0; i < N; i++) {
	13	x[i] = func(i);
	14	y[i] = func(i);
	15	}
	16
	17	#
	18
	19
	20
	21
	22
	23
	24
	25
	26
	27
	28
	29
	30

pragma xmp device replicate (x, y) { #pragma xmp device replicate_sync in (x, y) #pragma xmp device loop on t(i) for

		ExecuƟon
		on Host
		Data
		AllocaƟon
		Data Copy
		Host to
		Device
	(i = 0; i < N; i++) y[i] += x[i];	ExecuƟon on Device
		Data Copy
	#pragma xmp device replicate_sync out (y)	Device to
	}	Host
	}

Acknowledgment

This work is partially supported by a JST-ANR Joint Project entitled "Framework and Programming for Post Petascale Computing (FP3C)" and JST/CREST program entitled "Research and Development on Unified Environment of Accelerated Computing and Interconnection for Post-Petascale Era", in the research area of "Development of System Software Technologies for post-Peta Scale High Performance Computing".


Kenza El

Kenza

A metric to

come

empirical work. The hypotheses are tested on a three different sectors. The paper concludes with a summary; avenues for future research and managerial implications.

1. Major innovations sequences: Literature review and research questions Several scholars suggested that major innovations are rare. Even during periods in which overall rates of change are high, there will be relatively few radical or major innovations. Major innovations usually occur independently of other major innovations. In other words, literatures suggest that there is no relationship between major innovations within a given sector.

1.1 Frequency of major innovations: Several research works have suggested that major innovations are rare. According to [START_REF] Rothwell | Re--Innovation and Robust Design: Producer and user Benefits[END_REF], major innovation introduces a new type of product on the market, e.g. the jet engine versus piston engine or the personal microcomputer versus mainframe computer, then, this major innovation will be followed by a series of minor modifications (incremental innovations) until the introduction of other new type of product. Indeed, if we consider a new type of product as a reference to measure major innovations during time, the authors estimated that only 10% of all new innovations fall into the category of radical or major innovations and incremental innovations cover 90% of the remaining cases. That means that major innovations are rare. The punctuated equilibrium model of change confirms that long periods of small incremental change are disconnected by brief periods of discontinuous, major, radical change (Abernathy and Utterback 78; Tushman and Anderson 86; Rosenkopf and Tushman 95). Like a Darwinian theory, which discuss the notion of punctuated equilibrium, which means that such long periods of gradual change were interrupted periodically by massive discontinuities. In addition, Foster's works give a tool that can aid in the identification of radical innovations' behavior. This tool is the technology S--Curve introduced by him in 1986 (Figure .1). The S--curve has been used to describe the origin and evolution of technologically radical innovations (Utterback and Abernathy, 1996;[START_REF] Utterback | Mastering the dynamics of innovation[END_REF]. This theory suggests that technological changes moves along an S--curve until technical limitations cause research effort, time, and/or resource inefficiencies to result in diminishing returns. New innovations replace the old technology and a new S--Curve is initiated (see Figure .1). In addition to the management and marketing literature concerning the scarcity of major innovations, economists were also interested in it. Lancaster (1966a) was aware of innovation and dedicated an important part of his work on this issue. He introduced the idea that goods are consumed for the characteristics that they possess, and he describes goods not merely as goods but takes them as an input to the consumption function, which gives in characteristics of goods as outputs; According to him, new goods could be regarded solely as a combination of existing characteristics in new proportions or as an improvement in the performance of certain characteristics. Lancaster's model encompasses innovations, which are due to combinations of characteristics or to a performance improvement in the characteristics, and excludes the innovations, which could be due to the addition of characteristics that are not possessed by any existing good. According to Lancaster there is no revolutionary good that integrates characteristics, which are not possessed by any existing good (Lancaster, 1966a). That means that major changes are really rare. These different viewpoints suggested that major innovations are rare and not frequent (Table .1 summarizes different viewpoints concerning the frequency of major innovations).

Radical innovation

Extremely rare This literature review allows us to construct the following hypothesis: Hypothesis 1 (H1): Major innovations are rare and not frequent. This first hypothesis is clearly confirmed by Lancaster's approach, which suggests that each new good is solely a combination of existing characteristics. The punctuated equilibrium model also confirms the first hypothesis, because it suggests that long periods of small incremental change are disconnected by brief periods of major or radical change. This article will test this hypothesis (H1), to answer the question: Are major innovations really rare? Before doing our empirical tests, we noted that some scholars suggested that firms could implement special structures and organizations in order to increase the frequency of major innovations. This viewpoint considers that many firms compete by changing continuously, for example Intel, 3M, Apple; their ability to change is not limited. The technological discontinuities, and the continuous changes affect the firms' organizational environment and require certain types of organizations structures. Many scholars showed that organizations structures which grouped different actors of the innovation process and which facilitate the communication between them could be particularly promising to follow the continuous change and to have repeated major innovations (Clark and Wheelwright, 1992). [START_REF] Brown | The Art of Continuous Change: Linking Complexity Theory and Time--paced Evolution in Relentlessly Shifting Organizations[END_REF] describe organizations in which change is frequent, rapid and even endemic to the firm, this perspective contrasts with many paradigms in organizational and strategic thinking, such as transaction cost economics, agency theory, and organization ecology, in which organizations are assumed to be static or nearly so. According to [START_REF] Godoe | Innovation Regimes, R&D and Radical Innovations in Telecommunications[END_REF], evidence from analysis of innovation in the telecom sector suggests that innovation regimes have provided a capability of coordination, direction and leadership in the creation of many of the radical technological innovations that have emerged in the sector. That means that major innovations could be coordinated. According to this point of view, we can think that major innovations could be organized and can be scheduled to be a part of the firms' strategy. That means that major innovations could be frequent and not rare.

Interdependency and chain reaction effect between major innovations:

Beyond the debate around the frequency of major innovations, the purpose of this article is to delineate the interdependency between major innovations; in other terms the relationship between new and past major innovations. In contemporary innovation theory, the creation of incremental innovations is variously explained in terms of rational responses to markets, dynamics of technological regimes, radical innovations in contrast are explained in terms of serendipity, chance or haphazard scientific discoveries without any interdependency between them. However, building on the resource-based view of the firm, past research has emphasized leveraging firm competences to create successful products. That means that interdependency exists between past and future major innovations. The idea is to capitalize on what the firm does well. Lansiti and Clark 1994 found that building on past knowledge for current projects was related to successful product generations in the mainframe computer and auto industries. So building on the past is key to successful multiple new product innovation. Lansiti and Clark confirmed the fact that future innovations could benefit from the past innovations and the past knowledge. In the other hand, economists as [START_REF] Aghion | A Model of Growth through Creative Destruction[END_REF] were interested in the interdependency of innovations during the technological progress. According to them, Research firms are motivated by the prospect of monopoly rents that can be captured when a successful innovation is patented. But those rents in turn will be destroyed by the next innovation, which will render obsolete the existing intermediate good. This means that there is no interdependency between major changes and that new innovations destroy systematically the existing technology or goods. This viewpoint is contrary to the idea that interdependency between major innovations could exist and that old innovations could influence the appearance of a set of others new major innovations. We have two different points of view concerning the interdependency between innovations. One viewpoint rejects the interdependency between major changes, because new innovations destroy the old ones, and the other point of view supports the idea that building new innovations on the past could be a key to successful innovations. So, is there any relationship between major innovations?

In order to answer this question, we should test the following hypothesis: Hypothesis 2 (H2): There is interdependency between major innovations. These major innovations create a chain reaction effect between them. This article focuses on the frequency and interdependency between major innovations and in order to reject or confirm the previous hypotheses, we need an adequate method to measure major innovations. The next part will debate the measurement of major innovations. innovations with the sport shoes or with the sport bags we are not sure to measure major innovations of the whole sport sector.

Different methods to measure the major innovations:

The measurement of innovations remains very complicated and requires really complex tools. Several scholars measure innovations on different levels: Product or technology measures; financial or market measures; Patent or intellectual property measures [START_REF] Griliches | Patent Statistics as Economic Indicators: A Survey[END_REF][START_REF] Sanderson | Managing product families: The case of the Sony Walkman[END_REF]García--Morales et al 2008;[START_REF] Salomo | What about Design Newness? Investigating the Relevance of a Neglected Dimension of Product Innovativeness[END_REF]. The financial (Ratio of sales of new products to total sales, R&D spending), the organizational (Innovation activities), or patent measures (Number of patents, patents fees) are useful to measure the performance of innovations or the way in which teams can be organized to be innovative, or the performance of R&D activities. As seen before, we are interested on the measuring of major innovations through new characteristics. Indeed, financial or organizational measures couldn't capture these major innovations aspect. We can think that patent measures could capture major innovations, but patents reflect new technologies, we are not sure that they could be transformed to new characteristics with an economic effect on the market (new characteristics which help consumer to choose between different new products). These measures are not adequate to measure major innovations in terms of new characteristics, which integrate a product reference. There are researches, which used quantitative measurement to capture the major innovations on a given market. However there are only few researchers how try to construct quantitative measures to capture innovations. We will treat two examples: 1) Measurement of major innovation with specific magazines and groups of experts. 2) Measurement of major innovation with manufacturers' sales brochures. The first methodology used by [START_REF] Salomo | What about Design Newness? Investigating the Relevance of a Neglected Dimension of Product Innovativeness[END_REF], who measured innovation by capturing the major car's innovations (ABS, Daylight or rain sensors, aluminum chassis etc.); he used industry publications that target end consumers in the Automobile industry. His method is the use of Automobile magazines, which offer available data on new product launched over time. According to Salomo these conditions allow him to build a data set, which capture major innovations in the Automobile industry. These innovations are important to end consumers; they have an economic effect because these innovations have an influence on sales performance. Salomo's methodology requires the intervention of a number of experts who should verify and complete the list of innovations. The second methodology was the one used by [START_REF] Sanderson | Managing product families: The case of the Sony Walkman[END_REF] to capture variety and new features on personal portable stereos. They used manufacturer's sales brochures to obtain information on the design, new features and specifications of the whole market personal stereos models. The measurement of variety is interesting with this method. These two methods are used to capture major innovations and variety (new products' characteristics and features). They are properly constructed, but they are not easily to duplicate. The intervention of experts to verify the major innovations' list can influence the objectivity of information, may be major innovations for a group of experts are not the same for an other group (what is new for one expert is not new for the others). In addition, Salomo chose a set of brands and set of categories of cars (small, medium) and then he captured major innovations of these cars. The problem with this methodology is the choice of the adequate product references. How can be sure that with this set of cars we can capture major innovation on the automobile sector?

The second method captures manufacturer's viewpoint of new products' features. These characteristics could may be not have an economic effect on marketplace (consumers), it excludes the value for the end consumers. The measurement of major innovations sequences requires a new method, which can capture new characteristics with an economic effect (consumption function); which can be easy to duplicate;

New tool of measuring major innovation:

The quantitative measurement of major innovations remains complicated. However this article try to bridge the gap by using a new tool of measuring the sequences of major innovations by following the Lancaster's viewpoint.

Research approach:

In his seminal work, Lancaster (1966b) introduced the idea that goods are consumed for the characteristics that they possess, and he describes goods not merely as goods but takes them as an input to the consumption function which gives in characteristics of goods as outputs; According to him, goods contain many properties, but he defines characteristics as properties that are relevant to consumers' choices (economic effect). As seen before, our method will follow this viewpoint to measure major innovations through the measurement of new characteristics. As explained by Lancaster, the evaluation of the product characteristics is regularly made by consumer guides, which regularly make a synthesis of all existing products and compare them along well--identified characteristics that are considered to be critical in the consumer choice. In this perspective a major innovation can be identified by looking at the emergence of new characteristics used to evaluate the product on the market. Measurement of innovation in this case considers what the customer really wants to use or to consume; this methodology enables us to study only innovations that pass the "Market test" (Hayek, 1978) and that have economic values. This paper used consumer guides, following the advice from Lancaster (1966a): "Organizations such as the consumers Union exist to provide more objective information on characteristics than is easily available elsewhere". Consumers union's missions are to test products, to inform the public, and to protect consumers. In fact, we based our empirical work on the test results from the tests that are carried out on consumer goods by the French Consumers Union, Union Fédérale des consommateurs. These results have been published periodically in Que Choisir? --The French equivalent of the American magazine Consumer Reports--since 1961. In these reports, attributes of goods are tested and they are tabulated with their technical values. A consumer would be more interested in the evolution of these technical values but we are interested in the evolution of the characteristics that are being tabulated. Therefore, for our research, characteristics that are given in a test report constitute our material.

Specification of the basic methodology: Strengths and weaknesses:

Our New tool of the measurement of major innovations has both strengths and weaknesses. Methodology's Strengths The quantitative method of measuring major innovations using consumer guides, capture the characteristics with an economic value. Consumer guides are responsible for the selection of the right sample of products, which correspond to consumers needs on different market (TV, Mobile phone, Iron, Washing Machine etc.). They do different test and give consumers the right devices concerning the consumer goods and give a detailed list of characteristics of products, which help consumers' choice. The consumer guides are independent organizations; they are not advertising for brands; in contrast they do tests on different brands to compare them. With consumer guides we don't need to contact experts who can verify the list of characteristics. Consumer guides are a reachable source of information; give a detailed list of products' characteristics; every year we find products' tests (products from different brand); they give information, which correspond to consumers' need (economic value). Methodology's Weaknesses This method captures new product's characteristics not at the right time, because consumer guides do tests on the existing products (they are already on the market), indeed characteristics can be overdue. In addition, this method could not capture all new characteristics. For example, in the case of mobile phone, we capture 83 new characteristics during the period from 1996 to 2010, and may be in the reality there are more than 83 characteristics, but our objective with this method is to capture major innovations to show the sequences of them. So, in spite the fact that we capture lower bound of characteristics number we can reject our first hypothesis, and we can show that major innovations are frequent. This methodology is strong and can measure the major innovations solely if we have what we call a product reference. For example on the market of mobile phone the product reference is mobile phone and we can measure the major innovations integrated each time to this product reference. However, this methodology becomes weak when we have a market with several product references like sport sector. We have several products reference because this sector is a universe of different uses. If we capture major innovations of shoes or bags sport we are not sure to capture major innovations of a whole sport sector. This method becomes weak also with a complex product like a car. In the consumer guides concerning car the list of characteristics is not tabulated like a mobile phone. So the measurement of major innovations in this case cannot use detailed characteristics. We will see in the following parts how we can extend this methodology to capture major innovations on car market. This article focuses on a quantitative methodology, which allows us to characterize major innovation sequences and its application in three industrial sectors. In the next part, this article analysis and exposes the main results concerning mobile phone and Iron. In these cases the list of characteristics is known and explicit within the consumer guides.

Data Analysis and Main results: Case n°1 -The list of characteristics is known and reachable.

Data collection:

In order to obtain empirical evidence to test our hypothesis, we needed a characteristics database. First, we selected two types of products: Mobile Phone and Iron. At the beginning of our work, our aim was to study goods that were very volatile in terms of innovation and others that have been on the market for a long time and that are stable in terms of innovation. Second and after the choice of the reference products (Mobile phone and Iron), we based our empirical work on the test results from tests that are carried out on consumer goods by the French consumers Union, " Union Fédérale des consommateurs ". The results have been published periodically in " Que choisir? ". And finally, it is important to note that our aim is to show the sequences of major innovations, elsewhere the relationship between these innovations for a long time. That is the reason why, we should build characteristics database on the longest time period; from 1996 to 2010 for mobile phone and from 1962 to 2010 for Iron. We take the longest periods (over almost 50 years) to gain insight into the long--term dynamics of innovation discontinuities. To follow the evolution of characteristics on time we use the archives of "Que choisir?". We capture major innovations by measuring the number of new added line in the list of products' characteristics each year. The characteristics are reachable because consumer guides provide the detailed list of products' characteristics. Basically the work shows that the method enables to characterize a sequence of major innovations: there are reliable data and reliable ways to analyze them.

Major innovations are frequent and not rare:

Our empirical findings (Table .2) show that there are major innovations sequences. If we took Mobile Phone, since the first report in 1996 on mobile phones, the cumulative number of new characteristics has reached 83. The mobile phone cumulate new characteristics from "Display", "Camera", "Music" to "Bluetooth", "GPS", and "internet", with this set of new characteristics, we can have more dynamic view of mobile phone. Mobile phone is not only the object which allows us to call people without being at home, but it becomes also camera, TV, personal computer… etc. We could think that mobile phone is very recent and volatile product, and this could be the main reason for the appearance of these new characteristics (83 since 1996 to 2010). However, we observe the same symptom concerning Iron. This product exists for a long time on marketplace and we thought that it is stable. Our database for irons contains information about 19 periods of product tests over almost 50 years. According to the database, cumulative number of characteristics of irons is 73 new characteristics. Iron cumulated new characteristics from "Safety", "Teflon sole" to "Steam", Comfort", and "Cordless", these major innovations show that iron is not solely an object for ironing clothes, but becomes an object, that take care of clothes. 2,3 Over almost 50 years and in the two markets, these are usually newly added characteristics, this expansion in the characteristics space show the existence of major innovations on the marketplace. As seen before, many scholars noted that major innovations are rare. However, our results rejected the hypothesis 1 which suggests that major innovations are rare and we confirmed that major innovations are frequent. Major innovations are not rare; the frequency of major innovations (sequences of new characteristics. See Table .2) reaches until 6 new characteristics per year for mobile phone during 14 years (1996--2010) and 2.3 new characteristics per year for Iron during the whole given period (1962--2010). Figure .2 shows the total number of new characteristics that are added to mobile phone from May 1996 to September 2010. The new characteristics added to product reference (6 new characteristics per year) are significantly high. We can see in that curve the number of characteristics, which are added to product reference (mobile phone) all over time. We noted that the first 14 new characteristics started on May 1996 are the first characteristics tabulated for mobile phone; they represent the starting point; there are no predecessor characteristics before these 14 mobile phone's characteristics. The first consumer guide's test on mobile phone was on May 1996. The appearance of new characteristics is frequent; we can see that every year new characteristics were added to the mobile phone. With these results, we can reject the first hypothesis. Major innovations are not rare. The frequency of changes is relatively high. We can see in that curve the number of characteristics, which starts on December 1962, sets of characteristics were usually added to the mobile phone all this given period. There is a continuous change. We noted that the first set of twelve characteristics is a starting point; then, this starting point is followed by the other sets of new characteristics. These empirical results reject the first hypothesis (H1). According to our results major innovations are repeated all over time, they are not rare and major innovations' sequences are frequent. The dominant design is revisited by the addition of a set of new characteristics on products. If we take the example of mobile phone, during the time the mobile phone become music, pictures, videos and Internet support. The product reference, which is mobile phone, has now different uses than before.

Chain reaction effect and Interdependency between major innovations:

Our empirical studies show that major innovations are interdependent. We identify chain reaction processes that link certain newly emerging characteristics over time. That means that our results can confirm the second hypothesis (H2), which said that major innovations are interdependent. We use the term "Chain reaction" because old characteristics influence the appearance of new ones, like chain reaction in chemistry and physics fields. A chain reaction is a sequence of reactions where a reactive product or by--product causes additional reactions to take place. The interdependency can be represented as a network of characteristics (Figure . 5). There is more than one type of relationship between major innovations. The interdependency can take a lot of time to be observed; also the interdependency can be build by chaining new characteristics. Figure .5 summarizes the relationships between different major innovations all over time. Our results show that some new characteristics give, in fact, other new ones. The initial characteristics influence the appearance of a set of other characteristics. For example, here characteristic "B" influences the appearance of "F" and this one gives other new characteristic "O". That shows the interdependency and the chain reaction effect in the same time. In other hand, a set of characteristics could generate one new characteristic - "G", "H" and "I" influence the appearance of "K". However, one new characteristic can take a long time to generate other new one or a set of new characteristics (example: "A" and "J"). We can find also, the situation, when new characteristic doesn't generate other. It appears and stops like "E". Characteristics follow different patterns and rhythm, but still confirming the interdependency between them all over time. The chain reaction effect can have different aspect and it depends on: the speed of appearance of new characteristics; the number of intermediate characteristics, which build the chain of characteristics. Multi band characteristic is about the frequency bands that mobile phones support. This characteristic is important when traveling. If a mobile phone supports a wide variety of frequency bands then the consumer can use his phone for roaming purposes. When the characteristic dual--band first added, it was new to the market but then it generated other new characteristics as tri--band technology.

Internet: After the appearance of GPRS and UMTS on the list of characteristics, there has not been an immediate effect. Then these were followed by another characteristics Wi--Fi, which was in turn, was followed after a few years by other characteristics that are internet--related.

Picture: Camera was appeared on a list of characteristics, that is followed by many characteristics that all consumers notice and know how to use. Music: When music player was first introduced to mobile phones, right after it was added MP3 sound quality and music transfer characteristics. Data characteristics: Many data characteristics were added on the lists of mobile phone characteristics, and other new ones followed them. Data transfer --Mini USB, Memory Card -Size, Type. Our basic methodology with the known and the reachable list of characteristics, allows us to reject the hypothesis 1 (H1), and to confirm the idea that major innovations are not rare. Also to confirm the second hypothesis (H2) with the interdependency between the old and the new set of major innovations. 4. Basic methodology's extension: Data Analysis and Main results case n°2 -The list of characteristics is unknown and not reachable (Automobile) Some methodology's weaknesses encourage us to extend our basic methodology in order to test our hypothesis in the case of complex product when the list of characteristics is unknown and aren't tabulated in the consumer guides.

Methodology's extension and Data collection:

As seen before, with complex product like car, consumer guides don't give the list of new characteristics like mobile phone or Iron. Automobile is a complicated product with a huge number of sets of characteristics, which are integrated within different types of car (Small, medium, big etc.). With Lancaster viewpoint it was interesting to capture a set of characteristics, but it is no easy to do that with complex product, like an automobile. Indeed, we extent our basic methodology from set of characteristics to an other type of reference product. We measure major innovations by capturing the appearance of new car's models or classes and capture the appearance of car's trends.

The models of car (Sedans, Breaks, Roadster, Family cars etc.) integrated a huge set of characteristics, so when new category appears, it suggests that a new set of characteristics appears too. Major innovations are integrated within cars' models. In the addition to that, and in order to complete our method, cars trends are measured too. Cars trends represent the new way or the new use of cars (Family, Sporty, Urban, fashion etc.). We noted that new trend influence the appearance of new models (Underlying the appearance of new set of characteristics). We measure major innovations in this case, by extending our basic methodology from characteristics of products to other reference level of product. We measure the appearance of new models or classes of cars and trends. Consumers chose their car by regarding models and also by regarding sector trends. In order to obtain empirical evidence to test our hypothesis in this case, we needed a categories and trends database concerning the Automobile. We used one of the most French known Automobile consumer guides, which is "L'Auto--journal", we use specially "Le guide de l'acheteur" (Consumer guide) to measure the appearance of new cars' models. We used the archives of this magazine from 1959 to 2011.

Major innovations are not rare:

Our database contains information about 15 periods of product guide surveys over almost 50 years; the cumulated new characteristics of Automobile are 20 new trends and 40 new categories (Table .3). These variables have an economic value for the consumers (as seen before). Automobile is no longer solely a means of transport, but becomes a living space, a communication object, and a fashion. Concerning the sequences of major innovations, we have found that during the given period, 1 new class or model appears each year, and in terms of trends, 1 new trend per two year appears during the same given period. Figure .8 shows the sequences of major new trends (Low--cost, Eco--responsibility, sporty, Fashion, Family etc.) that are added to Automobile from 1959 to 2011. We can see in that curve the number of new trends of car added to the universe of trends; sets of characteristics were usually added to the Automobile all this given period. We noted that the first 8 trends are the starting point. There is a continuous change and major innovations represented by trends are frequent all over the time. That means that we can reject the first hypothesis (H1) in order to suggest that major innovations are not rare.

Interdependency between major innovations

The results of our basic methodology's extension show that the characteristics concerning the automobile have two levels of interdependency. Trends of cars influence the appearance of new models. And new models influence the generation of others (see figure.10). Our results show that major innovations could be expressed by the major changes in usefulness of cars (Low--cost, Eco--responsibility, sporty, Fashion, Family etc.) and models (Sedans, Breaks, Roadster, Family cars etc.).

Our results confirm the second hypothesis; Major innovations are interdependent. In the case of Automobile there are two levels of interdependency. The first level is between car's trends and car's models (see Figure .9.). The appearance of a set of new trends influences the appearance of new set of car's categories. SUV: SUV car evolves to be conducted on extreme condition land. This characteristics evolves all over time in order to generate other new characteristics like luxury, Leisure and urban. These characteristics were be mixed to SUV. Major changes were related to this category of car's uses.

Eco responsibility: New characteristic was related to car, it is eco responsibility. That means that this kind of characteristic let cars contain new technologies and innovations in order to respect the environment and to be eco responsible. These results support the second hypothesis, and show the chain reaction effect and the interdependency between major innovations within a complex product. We could capture major innovations by measure the really new trends and models cars. The extension of our basic methodology allows us to reject the first hypothesis and to confirm the second one. Major innovations are not rare and they are interdependent; Old innovations can influence the generation of a set of new characteristics.

Conclusion and Future Research

This study contributes to innovation research --specially the measurement of major innovations--by providing a new tool to measuring major innovations sequences by regarding new characteristics, which are integrated to the product reference (Mobile phone, Iron, Automobile) on long time period (1959--2011). It studied innovation from the perspective to show that new characteristics were coming and expanding the characteristics space of different product, even if the most stable and old product on the marketplace as Iron or Automobile. In other words, this article suggests that major innovations are not rare all over time. This article shows also, contrary to several viewpoints, that major innovations could follow a chain reaction effect, because of the relationship between the succeeding major innovations (Old innovations influence the generation of new ones). This article opens the debate around the dominant design of mobile phone, Iron or Automobile. The accumulation of major innovations within the products reference revisited the dominant design of the products; for example, mobile phone became not solely a simple tool of communication, but also personal computer, agenda, Camera etc. This article use database concerning three different products (Mobile Phone, Automobile and Iron), may be further research should duplicate our methodology on other different products or sector, first in order to reinforce and extend our methodology, second to study the frequency of the major innovations in multitude sectors and finally to study the different degree and types of interdependency. This article analysis the appearance of new characteristics and the dynamic of different markets via major innovations; however it didn't treat the situation with markets without major innovations or really less innovations. Further research may try to answer the following question: Are sectors without major innovations dynamic? Do they have a continuum growth? Implications for Management: These phenomena -frequency and chain reaction effect --suggest analyzing the adequacy of the organizational forms in the sector companies with the sequence of innovations in the sector. It helps to diagnose some inadequacies and to suggest some organizational changes. The tool would also allow monitoring the current dynamic of innovations in a given industrial sector and, occasionally, the shifts in these dynamics (changes in innovation regime).

Figure. 1 .

 1 Figure.1. Technology/Marketing S--Curve Phenomena (Adapted from Foster 1986)

Figure

  Figure.2: Total Number of new Characteristics for Mobile Phone

Figure. 3 :

 3 Figure.3: Total Number of new Characteristics for Iron

Figure. 4 :

 4 Figure.4: Total Number of cumulated characteristics -Mobile Phone and Iron

Figure. 5 :

 5 Figure.5: Interdependency between major innovations and the chain reaction effect

Figure. 6 :

 6 Figure.6: Interdependency between major innovations and the chain reaction effect -Mobile Phone

Figure. 7 :

 7 Figure.7: Interdependency between major innovations and the chain reaction effect -Iron

Figure. 8 :

 8 Figure.8: Total Number of new cars Trends

Figure. 9 :

 9 Figure.9: Total Number of new cars classes or categories

Figure. 9 :

 9 Figure.9: Interdependency between major trends and models -Automobile

Figure. 10 :

 10 Figure.10: Interdependency between cars trends -Automobile

Table . 1

 . Major/Radical innovations and different viewpoints:

	Authors	Innovations	Frequency
	Lancaster 1966	Revolutionary	Rare
	Tushman and Anderson 1986	Discontinuous innovation	Not frequent
	Foster 1986	Radical innovation	Not frequent
	Tushman and Anderson 1986	Discontinuous/Radical	Rare
	Rothwell and Gardiner	Major innovations	Rare
	Garcia and Calantone 2002

Table . 2

 . Number of consumer tests and total number of new characteristics by products

		Mobile Phone	Iron
	Period of time	1996 --2010	1962 --2010
	Number of consumer guide surveys	15	19
	Total number of new characteristics	83	73
	Major innovations frequency (New characteristics	6
	per year)

Table . 3

 . Number of consumer tests and total number of new characteristics by type of the observable

		Automobile
	Types of the observable	Models/ Classes	Trends
	Period of time	1959 --2011	1959 --2011
	Number of consumer guide surveys	13	15
	Total number of new characteristics	40	20
	Major innovations frequency	1	0,5

Jan--62 Jan--63 Jan--64 Jan--65 Jan--66 Jan--67 Jan--68 Jan--69 Jan--70 Jan--71 Jan--72 Jan--73 Jan--74 Jan--75 Jan--76 Jan--77 Jan--78 Jan--79 Jan--80 Jan--81 Jan--82 Jan--83 Jan--84 Jan--85 Jan--86 Jan--87 Jan--88 Jan--89 Jan--90 Jan--91 Jan--92 Jan--93 Jan--94 Jan--95 Jan--96 Jan--97 Jan--98 Jan--99 Jan--00 Jan--01 Jan--02 Jan--03 Jan--04 Jan--05 Jan--06 Jan--07 Jan--08 Jan--09 Jan--10 Iron