A Nouisri

O Allix

O Dorival

Towards a non intrusive method for solving coupled direct retrograde problem in transient dynamics

Keywords: waveform relaxation, intrusives methods, dynamics, identification, time direct-retrograde problem

The objective of this work is to solve within a standard finite element software, the direct-retrograde coupled time hyperbolic problems that arise when dealing with the identification of material parameters in dynamic in presence of corrupted measurements by means of the adjoint state approach. This question has given rise among others to Riccati methods and shooting methods. Those methods have several drawbacks, namely their numerical complexity and the fact that their implementation in a commercial software would require to entirely re-design the implementation, which is nearly impossible. Therefore we are seeking an iterative method which could be easily implemented. The proposed method solves alternatively a direct problem and a retrograde one. In order to ensure its convergence a relaxation scheme is applied and optimized. Comparisons between the proposed approach and Riccati and shooting methods in terms of complexity, numerical cost and robustness are given in the case of an elastic bar.

Résumé :

L'objectif de ce travail est de résoudre, par la méthode des éléments finis, un problème temporel hyperbolique direct-rétrograde qui se pose lorsqu'il s'agit d'identifier des paramètres matériaux en dynamique en présence de mesures corrompues par l'approche de l'état adjoint. Cette question a donné lieu entre autres à des méthodes de Riccati et aux méthodes de tirs. Ces méthodes présentent plusieurs inconvénients, notamment leurs complexités numériques et le fait que leur mise en oeuvre dans un logiciel commercial exige de reconcevoir totalement l'implémentation, ce qui est impossible. C'est pourquoi nous recherchons une méthode itérative qui pourrait être facilement implémentée. La méthode proposée permet de résoudre alternativement un problème direct et un problème rétrograde. Afin de garantir la convergence, un schéma de relaxation est appliqué et optimisé. Des comparaisons de la méthode proposée avec les méthodes de Riccati et les méthodes de tirs en termes de complexité, de coût de calcul et de robustesse sont présentées sur le cas d'une barre élastique.

Introduction

The identification of physical structural parameters is a difficult task especially in the context of transient dynamics. Therefore this domain has given rise to a lot of proposals and dedicated methods [START_REF] Andrieux | Reciprocity principle and crack identification[END_REF][START_REF] Aughan | A negative exponential solution for the matrix Riccati equation[END_REF][START_REF] Bui | Introduction aux problèmes inverses en mécanique des matériaux[END_REF][START_REF] Corigliano | Parameter identification in explicit structural dynamics : performance of the extended kalman filter[END_REF][START_REF] Roberts | Continuation in shooting methods for two-point boundary value problems[END_REF][START_REF] Rota | An inverse approach for identification of dynamic constitutive equations[END_REF]. A difficulty is that those methods often need to design new specialized softwares. This is also the case of the method we proposed in order to deal with the identification of the dynamic behavior of laminated composites up to failure [START_REF] Allix | Identification strategy in the presence of corrupted measurements[END_REF][START_REF] Bui | Introduction aux problèmes inverses en mécanique des matériaux[END_REF][START_REF] Ladevèze | Nonlinear Computational Structural Mechanics -New Approaches and Non-Incremental Methods of Calculation[END_REF][START_REF] Sundararajan | An algorithm for response and stability of large order nonlinear systems -application to rotor systems[END_REF]. We are thus seeking a method which could be used in a standard finite element code with as few implementation as possible. This paper is a first step in that direction.

The type of inverse problem we are focused on concerns the identification of material parameters in dynamics in the case of corrupted measurements. The identification strategy used is based on the concept of the modified error in the constitutive relation [START_REF] Deraemaeker | Reduced bases for model updating in structural dynamics based on constitutive relation error[END_REF].

The minimization of the functional under constrains associated to the formulation leads to coupled direct-retrograde wave propagation problems which exhibit exponential solutions, thus making the problem highly ill-conditioned. This problem has previously been solved by combining two technics : the resolution of an algebraic equation of Riccati [START_REF] Aughan | A negative exponential solution for the matrix Riccati equation[END_REF][START_REF] William | A new fundamental solution for differential Riccati equations arising in control[END_REF], which in the non-linear case was adressed using the LATIN method to solve iteratively the problem globally on the whole time interval [START_REF] Allix | Identification strategy in the presence of corrupted measurements[END_REF][START_REF] Ladevèze | Nonlinear Computational Structural Mechanics -New Approaches and Non-Incremental Methods of Calculation[END_REF][START_REF] Sundararajan | An algorithm for response and stability of large order nonlinear systems -application to rotor systems[END_REF]. The implantation of those two methods within a commercial software is beyond what can be done in a research team.

The basic idea of the proposed method is to solve alternatively, starting from an initial guess, a sequence of direct and retrograde differential equations. A waveform relaxation is needed to improve the convergence especially for wide time range. A numerical example shows the feasibility of the method and comparisons with Riccati and shooting methods are given.

Description of the problem 2.1 The reference model

In this paper we have restricted the application of the method to a homogeneous isotropic linear elastodynamic structure whose characteristics (Young's modulus E ref , Poisson's ratio ν ref and density ρ ref ) are known. However the method can be applied to more complicated cases. Nevertheless this simplified development of the strategy based on the concept of the modified error in the constitutive relation in presence of corrupted measurements in transient dynamics [START_REF] Deraemaeker | Reduced bases for model updating in structural dynamics based on constitutive relation error[END_REF] here allows to test the capabilities of the method. Moreover, work to extend the method to the nonlinear case is in progress. The reference model consists in an elastic bar of length L (see Fig. 1) that satisfies the following boundary conditions : -on the border x = 0, the structure is embedded ; -on the border x = L, a half-sine chap load F exp (t) t∈[0, T ] is applied.

E ref , ν ref , ρ ref ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ E F ext (t) O t F ext (t)
Figure 1 -The reference problem

Experimental data

Direct calculation is obtained by means of an implicit θ-method ; experimental displacement u and experimental load σ are then obtained by solving the following problem : equilibrium equation : The resolution of the direct problem provides the boundary conditions in displacements and forces on the given finite-time interval [0, T ]. Perturbations such as white noise are then added in order to simulate real measures :

ρ ref ∂ 2 u ∂t 2 (x, t) - ∂σ ∂x (x, t) = 0 (1a) constitutive relation : σ(x, t) = E ref ∂u ∂x (x, t) (1b)
-measured displacements : ũd at x = 0 and x = L ; -measured forces : fd at x = 0 and x = L.

The inverse problem 3.1 Formulation of the inverse problem

Our aim is to find the suitable space-time fields u and σ depending on the Young's modulus E that at the same time satisfies the constitutive relation and minimizes the distance to experimental datas ũd and fd . The question is about finding a compromise between these equations considered as uncertain under the constrains of reliable ones (i.e. : equilibrium and time initial conditions). The inverse problem associated to the identification strategy based on the modified error in the constitutive relation [START_REF] Deraemaeker | Reduced bases for model updating in structural dynamics based on constitutive relation error[END_REF][START_REF] Feissel | Modified constitutive relation error identification strategy for transient dynamics with corrupted data : The elastic case[END_REF] can then be written as follows : Find the fields u, σ, u d , f d minimizing (2) :

J (u, σ, u d , f d ) = T 0 1 2 L 0 E -1 (σ -Eε) 2 dx + α 2 f d -fd 2 L 0 + β 2 (u d -ũd ) 2 L 0 dt (2)
Under the constrains :

-ρ ref ü + div(σ) = 0 and u(x, 0) = u 0 and u(x, 0) = v 0 (3)

Adjoint problem and derivation

The inverse problem involves the minimization of the cost function (2) under constrains [START_REF] Aughan | A negative exponential solution for the matrix Riccati equation[END_REF]. The searched fields would be the ones for which the saddle point of the Lagrangian ( 4) is reached :

L E (u, σ, u d , f d , u * , λ, µ) = J E (u, σ, u d , f d ) - T 0 L 0 (ρ ref ü -div (σ)) u * dx dt - T 0 |(u -u d ) λ| L 0 dt - T 0 |(σ.n -f d ) µ| L 0 dt (4)
-u * is the Lagrange's mutliplier associated to the model error ; -λ is the Lagrange's mutliplier for relaxation of the displacements boundary conditions ; -µ is the Lagrange's mutliplier for relaxation of the efforts boundary conditions. This leads to the system (5) which is given in the strong form over ]0, L[ by :

   σ (x, t) = E. u ,x (x, t) + u * ,x (x, t) ρ ref ü (x, t) -E.u ,xx (x, t) -E.u * ,xx (x, t) = 0 ρ ref ü * (x, t) -E.u * (x, t) ,xx (x, t) = 0 (5)
The solution must satisfy the time initial and final conditions and the space boundary conditions (6) :

u (x, 0) = u 0 , u (x, 0) = u0 u * (x, T ) = 0, u * (x, T ) = 0          E u ,x (0, t) + u * ,x (0, t) = 1 β u * (0, t) + f 0 d (t) E u ,x (L, t) + u * ,x (L, t) = -1 β u * (L, t) + f L d (t) Eu * ,x (0, t) = -α u(0, t) -ũ0 d (t) Eu * ,x (L, t) = α u(L, t) -ũL d (t) (6)
The system ( 5) is then projected into a classical finite element space. This leads to the differential equations [START_REF] Deraemaeker | Reduced bases for model updating in structural dynamics based on constitutive relation error[END_REF] in which the searched direct and retrograde fields are respectively the unknown nodal vectors U and U * :

   M Ü (t) + K U (t) = K -K U * (t) + F (t) M Ü * (t) + K U * (t) = -K U (t) + F (t) (7)
U and U * must also satisfy the following initial and final conditions in time [START_REF] Feissel | Modified constitutive relation error identification strategy for transient dynamics with corrupted data : The elastic case[END_REF] :

U (0) = U 0 , U (0) = U0 U * (T ) = 0, U * (T ) = 0 (8)
-M et K are respectively the mass and the stiffness matrices ;

-K =        -1 α 0 . . . 0 0 0 0 . . . 0 0 . . . . . . . . . . . . . . . 0 0 . . . 0 0 0 0 . . . 0 -1 α        , F (t) =        -f 0 d (t) 0 . . . 0 f L d (t)        , K =        β 0 . . . 0 0 0 0 . . . 0 0 . . . . . . . . . . . . . . . 0 0 . . . 0 0 0 0 . . . 0 β        and F (t) =        -β ũ0 d (t) 0 . . . 0 -β ũL d (t)       
Classical incremental methods can not be applied due to the presence of coupling between the forward and backward equations in the system (7-8). Various methods have been proposed in the literature [START_REF] Andrieux | Reciprocity principle and crack identification[END_REF][START_REF] Aughan | A negative exponential solution for the matrix Riccati equation[END_REF][START_REF] Bui | Introduction aux problèmes inverses en mécanique des matériaux[END_REF][START_REF] Corigliano | Parameter identification in explicit structural dynamics : performance of the extended kalman filter[END_REF][START_REF] Sundararajan | An algorithm for response and stability of large order nonlinear systems -application to rotor systems[END_REF] to address this type of system.

4 Resolution of the inverse problem using a waveform relaxation method 4.1 Towards a non intrusive method One can transform the systems (7 and 8) into the first-order state-space system (9) :

Ẏ (t) = QY (t) + G(t), Y (0) = U0 , U 0 = Y 0 Ż(t) = QZ(t) + H(t), Z(T ) = 0 (9)
with :

-

Y (t) = U (t), U (t) , Z(t) = U * (t), U * (t)
being the state vectors ;

-P = 0 M -1 K -K 0 0 , Q = 0 M -1 K -I 0 and R = 0 M -1 K 0 0 being constant ma-
trices of dimension 2n (n is the number of degrees of freedom (d.o.f.)) ;

-

G(t) = M -1 F , 0 , H(t) = M -1 F, 0
being the input vectors.

The application of the method of successive approximations [START_REF] Burrage | Preconditioning Waveform Relaxation Iterations For Differential Systems[END_REF][START_REF] Raffort | Convergence of relaxation methods for two-point boundary-value linear problems[END_REF][START_REF] Wendi | Two stage waveform relaxation method for the initial value problems of differential-algebraic equations[END_REF] to the system (9) leads to the following process [START_REF] Ladevèze | Nonlinear Computational Structural Mechanics -New Approaches and Non-Incremental Methods of Calculation[END_REF] :

Ẏ (k) (t) = QY (k) (t) + P Z (k) (t) + G(t), Y (k) (0) = Y 0 Ż(k+1) (t) = QZ (k+1) (t) + RY (k) (t) + H(t), Z (k+1) (T ) = 0 (10)
This iterative procedure consists in solving alternatively the subsystem with initial time values forward from t = 0 to t = T , then the other subsystem with final time values backward from t = T to t = 0. Starting with a given initial guess field Z 0 , the calculation procedure is continued until convergence.

During the resolution of a subsystem, the coupled fields are considered as data, obtained from the previous calculation over the range [0, T ]. However, the redundancy of the boundary conditions and the instability due to the presence of an exponentiel phenomena in the solutions of the homogenous equation associated to the reference problem [START_REF] Raffort | Convergence of relaxation methods for two-point boundary-value linear problems[END_REF] are the main reasons why no convergence arises from such an iterative scheme.

Relaxation method

To help the convergence, the idea of the previous scheme is maintained, but a relaxation scheme is applied. The evaluation of the forward field Y (t) t∈[0, T ] at the (k + 1) th iteration is obtained from a weighted sum of the fields Z(t) t∈[0, T ] calculated at the (k + 1) th iteration and that calculated at the k th iteration.Following this line, equation ( 10) becomes a recurrence process : 1. Initialization is performed by an initial guess Z (0) of the retrograde field, followed by an initial evaluation Y (0) of the direct field by solving :

Ẏ (0) = QY (0) + P Z (0) + G with Y (k) (0) = Y 0 2.
At step k, the direct and retrograde fields Y (k) and Z (k) are known. Then the fields Z (k+1) and Y (k+1) are determined respectively by means of (a) the retordrade equation and its final condition in time and (b) the direct equation and its initial condition in time (a) Ż(k+1

) (t) = QZ (k+1) (t) + RY (k+1) (t) + H(t), with Z (k+1) (T ) = 0 (b) Ẏ (k+1) (t) = QY (k+1) (t) + P ωZ (k+1) + (1 -ω) Z k (t) + G(t), with Y (k+1) (0) = Y 0

Numerical tests

In our experiments, the basic solver used is the implicit θ-method with θ = 1 2 (trapezoidal rule) and the time-step is 0.36 µs for a given finite time interval [0, 0.63 ms]. The direct calculation is used to create measurements on a bar (Fig. 1) of section S = 1cm 2 , length L = 1m and material parameters

E ref = 200GP a, ν ref = 0.3 and ρ ref = 800kg.m -3
. White noise perturbations are then added in order to simulate real measures.

To deal with the relaxation scheme, the initial guess field is set to zero and the error tolerance is 10 -4 . The error used here is the holy norm of the differential equations [START_REF] William | A new fundamental solution for differential Riccati equations arising in control[END_REF]. Plots in Fig. 2-a gives an idea of the effect of noise on the convergence of the method. Although there is a wide choice of relaxation coefficients for which a few relaxation-iterations are spent until convergence, the nearest values to 1 are considered the best ones ; otherwise we do not have a real relaxation. We report on the right side (see Fig. 2-b) errors versus the number of the relaxation iterations arising from the costless values of the relaxation coefficients obtained from the left side one. Algorithm complexities of the proposed relaxation method, the Riccati method and the shooting method are evaluated by calculating the number of Multiply-And-Accumulate (MAC) operations needed to solve the above coupled problem (see Tab.1). According to this numerical test, the relaxation method looks more suitable than other ones : indeed its complexity is O(42kmn 2 ) while the Riccati method is O(mn 4 ) and the shooting method is O(320mn 1 -MAC operations for the proposed method, the Riccati method and the shooting method An evaluation of the algorithm complexity for various number of d.o.f. is given in Fig. 3-a. It confirms not only the efficiency of the relaxation method but also its reliability compared to the other methods. Robustness of the method to noise is also guaranteed : according to Fig. 3-b, Young's modulus were properly identified even for an SNR value up to 2.5.

Conclusions

For a system of time coupled direct-retrograde second order differential equations here derived in the case of an elastic bar, we proposed an iterative method that requires a reduced implementation time, and for which convergence is guaranteed by a relaxation approach. Numerical tests presented here tend to show the better efficiency and robustness of the proposed method compared to Riccati or shooting methods.

Although only the one dimensional elastic problem has been studied here, the same approach can directly be used for other linear two-point boundary value problems. The case of nonlinear materials is now under consideration.

= 10 S N R = 5 S N R = 10 3 S N R = 2 . 5 (Figure 2 -

 1053252 Figure 2 -Convergence of the relaxation method for a coupled system with various SNR ratios

  Algorithm complexity of the relaxation method.

Figure 3 -

 3 Figure 3 -Robustness of the relaxation method compared to the Riccati and the shooting methods.


Simon Urli
email: urli@i3s.unice.fr

Mireille Blay-Fornarino

Philippe Collet
email: collet@i3s.unice.fr

Handling Complex Configurations in Software Product Lines: a Tooled Approach

Keywords: D.2.10 [Software Engineering]: Design-Methodologies, Representation; D.2.13 [Software Engineering]: Reusable Software-Domain engineering, Reuse models Configuration, Software Product Line

As Software Product Lines (SPLs) are now more widely applied in new application fields such as IT or Web systems, complex and large-scale configurations have to be handled. In these fields, the strong domain orientation leads to the need to manage interrelated SPLs and multiple instances of configured sub-products, resulting in complex configurations that cannot be easily represented by simple sets of features.

In this paper we propose a tooled approach to manage such SPLs through a domain model that interrelates several feature models in a consistent way. The approach thus shifts part of the domain knowledge to the problem space and supports the derivation of complex configurations with multiple instantiations and associations of sub-products. We also report on the application of our approach to an industrialstrength software development in the field of digital signage.

INTRODUCTION

Software Product Line (SPL) engineering is concerned with systematically reusing development assets in an application domain [START_REF] Clements | Software Product Lines : Practices and Patterns[END_REF][START_REF] Pohl | Software Product Line Engineering: Foundations, Principles and Techniques[END_REF]. It is similar to mass customization in traditional industry, aiming to develop and evolve software systems as quality products, with reduced development effort and time-to-market. Planned and systematic reuse is facilitated within a family of systems by encapsulating the common and variable aspects into reusable software artifacts. SPL development starts with a first phase of domain engineering, which analyses the domain to identify variability and usually capture it in a model, such as a Feature Model (FM). Features are domain abstractions relevant to stakeholders, typically increments in program functionality [START_REF] Apel | An overview of feature-oriented software development[END_REF], while a FM is an AND-OR graph with propositional constraints that define features and their valid combinations in configurations [START_REF] Czarnecki | Feature diagrams and logics: There and back again[END_REF][START_REF] Schobbens | Generic semantics of feature diagrams[END_REF]. The second phase of SPL development, application engineering, ideally relies on generative techniques to produce a tailored software product from a configuration. With their increasing usage in many application domains and especially in software-intensive systems, many factors contribute to the amplified size and complexity of SPLs. In our work, we are focusing on the variability models expressed in FMs, which are used in these SPLs and increase in the same way.

Variability modeling is now used in different contexts, life cycle stages and parts of software systems. As new application fields in which SPL techniques are gaining attention appear, i.e., information systems and Web infrastructures, the SPL community needs to tackle new challenges to improve the expressiveness of variability models and to manage their overwhelming complexity. These domains indeed face an increasing complexity in managing the diversity of enduser profiles and devices [START_REF] Machado | Low-level variability support for web-based software product lines[END_REF]. But customization of products and even composition of customized sub-products are also strong demands from end-users. Some companies are moving towards the development of systems-of-systems [START_REF] Botterweck | Variability and evolution in systems of systems[END_REF] or software ecosystems [START_REF] Bosch | From software product lines to software ecosystems[END_REF]. In all these contexts, there is a need to support a process to handle complex configurations at the end-user level.In our experience in building and maintaining a complete SPL of Web-based digital signage systems, we have also clearly identified this issue [START_REF] Urli | How to exploit domain knowledge in multiple software product lines?[END_REF]. Tackling it implies to deal with the domain model itself, i.e., the concepts and relationships as they inherently are found in the targeted domain.

A complex configuration would then be a composition of domain element instances linked according to relationships defined by the domain representation.

The contribution of this paper is thus to describe a toolsupported approach, called SpineFM, allowing to design SPLs that handle complex configurations that are made explicit as a representation of the product domain model. The approach relies on a domain model that represents the concepts of the software family, their multiplicities and relationships, some FMs associated to each concept, and constraints between these FMs. This organization allows for representing a form of composite configuration as an instance of the domain model in which all elements refer to consistent FM configurations. Configuration is then driven by a staged [START_REF] Czarnecki | Staged configuration through specialization and multilevel configuration of feature models[END_REF] and order-free process. It relies on a propagation algorithm that ensures, at each configuration step, the consistency of the built configuration through the automated propagation of configuration actions. We also report on the application of the approach on an industrial-strength case study and on some experiments to evaluate its performance and scalabil-ity.

The remainder of the paper is organized as follows. We discuss in the next section some related works, introduce a running example and give an overview of the approach. Section 3 describes the organization of the domain model and its associated feature models. We detail the configuration process and the way the user is guided in Section 4. Section 5 describes the propagation algorithm that ensures the overall consistency during configuration. We evaluate the implementation of our approach in Section 6, detailing propagation time and memory usage on different complex configurations. Section 7 concludes the paper and briefly discusses future work.

HANDLING COMPLEX CONFIGURATIONS 2.1 Related Work

As feature modeling [START_REF] Kang | Feature-oriented domain analysis (foda) feasibility study[END_REF] is widely used to describe the variability of a domain, different extensions or techniques have been proposed to enhance the scalability of their usage [START_REF] Reiser | Multi-level feature trees: A pragmatic approach to managing highly complex product families[END_REF].

Several extensions to the original formalism have been proposed to allow cardinality in feature models, or references between distinct feature models [START_REF] Czarnecki | Staged configuration through specialization and multilevel configuration of feature models[END_REF][START_REF] Hartmann | Supplier independent feature modelling[END_REF]. We can cite in particular the work of Czarnecki et al. who define both a formalism for FM with cardinality and references, and a process to realize multi-staged configurations [START_REF] Czarnecki | Staged configuration through specialization and multilevel configuration of feature models[END_REF]. This improves the expressiveness of FMs but still, the need for organizing the captured information from the domain in a class model has been also identified and proposals have been made [START_REF] Czarnecki | Feature and meta-models in clafer: mixed, specialized, and coupled[END_REF][START_REF] Rosenmüller | Automating the configuration of multi software product lines[END_REF][START_REF] Acher | Composing multiple variability artifacts to assemble coherent workflows[END_REF].

On the other hand, support for composing FMs (foundations and tools) has been proposed [START_REF] Acher | Separation of Concerns in Feature Modeling: Support and Applications[END_REF]. It focuses on a sound semantics for FM merging, but does not address the configuration process. Moreover in some of their applications, different ad hoc DSLs realized the dynamic composition of FMs according to user choices, not making explicit the domain model and its relationships [START_REF] Acher | Composing multiple variability artifacts to assemble coherent workflows[END_REF].

As creating and maintaining a single FM is not desirable for large systems [START_REF] Dhungana | Structuring the modeling space and supporting evolution in software product line engineering[END_REF][START_REF] Hartmann | Using feature diagrams with context variability to model multiple product lines for software supply chains[END_REF][START_REF] Dhungana | Configuration of multi product lines by bridging heterogeneous variability modeling approaches[END_REF], approaches for separating FMs according to different concerns [START_REF] Acher | Separation of Concerns in Feature Modeling: Support and Applications[END_REF] or views [START_REF] Hubaux | Supporting multiple perspectives in feature-based configuration[END_REF] have been proposed and tooled. This can help in solving simple relationships between different FMs, e.g., when FMs are layered [START_REF] Kang | Form: A feature-oriented reuse method with domain-specific reference architectures[END_REF], when external and internal variabilities are distinguished [START_REF] Pohl | Software Product Line Engineering: Foundations, Principles and Techniques[END_REF][START_REF] Metzger | Disambiguating the documentation of variability in software product lines: A separation of concerns, formalization and automated analysis[END_REF], or when a view is explicitly tailored to simplify the configuration process for a specific usage [START_REF] Hubaux | Supporting multiple perspectives in feature-based configuration[END_REF]. Another complexity factor is the multiple nature of certain SPL usages, e.g., when independent suppliers describe the variability of their different products [START_REF] Czarnecki | Staged configuration through specialization and multilevel configuration of feature models[END_REF][START_REF] Hartmann | Supplier independent feature modelling[END_REF], when several SPLs should be integrated to form a multiple SPL [START_REF] Hartmann | Using feature diagrams with context variability to model multiple product lines for software supply chains[END_REF][START_REF] Dhungana | Structuring the modeling space and supporting evolution in software product line engineering[END_REF][START_REF] Holl | A systematic review and an expert survey on capabilities supporting multi product lines[END_REF], or when subsystems are modular variable entities that need to be put together in a consistent way [START_REF] Bosch | From integration to composition: On the impact of software product lines, global development and ecosystems[END_REF][START_REF] Acher | Composing multiple variability artifacts to assemble coherent workflows[END_REF].

Multiple software product lines have been proposed in various works, and under different terms, as another solution to tame the growing complexity of SPLs. Holl et al. realized an interesting survey that gives the following definition of multi product lines: "a set of several self-contained but still interdependent product lines that together represent a large-scale or ultra-large-scale system" [START_REF] Holl | A systematic review and an expert survey on capabilities supporting multi product lines[END_REF]. They identify several capabilities in actual multi product lines, proposing more advanced features like dynamic checking or collaborative configuration support. Dhungana et al. propose with Invar to manage the heterogeneity of SPLs integrating the different variability modeling approaches in order to define and use the multi product line as a whole [START_REF] Dhungana | Configuration of multi product lines by bridging heterogeneous variability modeling approaches[END_REF]. In particular, they define a way to express dependencies between variability models which inspires our own approach.

However most of the proposed solutions strongly bound the problem space and the solution space, assuming that stakeholders designing the SPL and configuring it have the same domain knowledge. For example, the approach proposed by B ֒ ak et al. with Clafer allows to realize a unique model mapping directly the variability of the problem space, generally represented as a feature model, to the solution space, represented as a class-based metamodel [START_REF] Czarnecki | Feature and meta-models in clafer: mixed, specialized, and coupled[END_REF]. However, combining the domain knowledge inside a unique Clafer model imposes to learn another paradigm of modeling, which can be error prone as many notions are mixed.

In our approach we propose to keep the modeling paradigms (class models and feature models) separated while using them in combination. This is similar to the work of Rosenmüller et al. as they use a class model to represent the different instances of the SPLs which occur in the final configuration [START_REF] Rosenmüller | Automating the configuration of multi software product lines[END_REF]. The configuration then consists in realizing the different instances by selecting the features for each SPL instance. We consider our approach as an extension to this work, as we show in this paper how to provide more flexibility in the creation of the first model representing the SPL instances, and how to ensure the consistency of the whole configuration product in a dynamic way, during the user configuration process.

Running Example

Our approach has been used to develop a complete SPL that will be described in Section 7 for evaluation purpose. In the rest of the paper, we will use the following running example inspired from the Home Automation System [START_REF] Pohl | Software Product Line Engineering: Foundations, Principles and Techniques[END_REF]. The objective is to configure a software system to control the different sensors and actuators of a house. The House itself has at least one opening. In our scenario, these concepts will be kept in the configuration space as classes and each of them supports some variability represented by a FM. Figure 2 depicts these FMs. The House can have a central computer to manage globally temperature, luminosity and security. Openings can be Doors or Windows, the windows can be a smart tinted glass and have roller stores. We also can put a lock on each opening and a sensor can be put to give the opening state. Each room can have sensors and actuators to manage temperature, presence or lightning. Moreover the FM expresses some internal constraints such as "Temperature implies Thermostat".

Constraints between these FMs must also be considered (cf. red arrows in Figure 2). For example, each time a room is configured with a Locking actuator, a Lock on each opening of this local room must also be created. Looking globally at the house, a central security system could oblige, for example, to have a lock on each opening, to have presence sensors, opened state sensors, roller store actuators and locking actuators. of an House instance that conforms to these specifications. Figure 3 gives two examples of such valid configurations. The first configuration, at the top, is a minimal valid configuration respecting both the domain model and the feature models. The second configuration is a bit more complex, but it also respects all given constraints.

Consequently we want to be able to create configurations

Overview of the Approach

Our approach is summarized on Figure 4. The SpineFM toolchain allows to design SPLs so to create composite configurations. In SpineFM, a SPL is defined by (i) a domain model that represents, at the end-user level, the concepts of the software family, their multiplicities, and how these concepts are interrelated; (ii) FMs that capture the commonalities and variabilities of each concept, also at end-user level; and (iii) constraints between these FMs.

For example, in our running example, the SPL is defined by the domain and FMs respectively depicted in Figure 1 and 2. These concepts are defined in a dedicated metamodel presented in section 3. Our solution supports end-user definitions of complex configurations, i.e., an instance of the domain model, whose elements refer to FM configurations. The configurations introduced in the previous section and depicted in Figure 3 are representations of our composite configurations for the running example.

The part of the metamodel formalizing composite configurations and concepts underlying the derivation process are described in section 4. These composite configurations serve as inputs for a dedicated generation tool that builds concrete products, but in this paper, we only focus on its definition and the configuration stages. The derivation process is based on a propagation algorithm that continuously ensures the consistency of the partial composite configuration by automatically triggering configuration actions with respect to model instances and previous actions. The algorithm and its properties are described in section 5.

A DOMAIN MODEL WITH INTERRE-LATED FMS

The domain model and its related FMs serve both to design the SPL and to drive the user through the derivation process.

Figure 5 shows an excerpt of the metamodel that defines the concepts supported in a domain model. These concepts are organized in three packages: DomainMetamodel gathers concepts for the domain elements, associations and multiplicities, FMModel contains all concepts to represent and manipulate FMs, and finally RFModel consists of concepts managing constraints between FMs.

Concepts, Associations and Multiplicities

In the domain model, concepts are Domain Elements (DE) and associations between them are DEAssociation. Each DE is related to a FM representing its specific variability. Associations are not oriented and two domain elements are only related by a unique association. This enables to focus on a unique association when relating their FMs. Each DE supports its own multiplicity to allow its multiple instantiation in configurations. Associations extremities (DEAssociatio-nEnd in the metamodel) also express multiplicities to control the number of associated instances of DE. Unbounded multiplicities are supported and bounded multiplicities are limited to 0 or 1. The different restrictions on the domain model enables to simplify the interrelations between FMs, but in our experience, this is expressive enough to capture and represent complex configurations.

Figure 1 shows a domain model using all these concepts: House, Room and Opening are domain elements; the three relations (the two contains and the hasGateways) are DE-Associations; we only represent the multiplicities on associations extremities on this figure.

Representation of Feature Models

Each domain element is an abstraction of a configuration space, i.e., a FM capturing some variability. The package FMModel provides concepts to represent and manipulate such FMs1 . A FeatureModel is a set of Features and Constraints. Each Feature, except the root, is a part of a Group which has an attribute specifying its state between Mandatory, Optional, Or, Alternative-Or and Mutex.

SpineFM supports different FM formalisms (e.g., SPLOT, FeatureIDE, TVL and FML) by delegating operations on FMs to an external reasoning engine. For example, the three FMs in Figure 2 could have been represented using indifferently SPLOT, FeatureIDE and TVL, at the same time 2 . From now on, we use the term "sub-configuration" to qualify indifferently an instance of a DE or a configuration of a FM: we formalize this notion in section 4.1.1.

Restriction Functions

Associations between DEs also aims at managing the relations between configuration spaces. As different sub-configurations are not necessarily compatible, constraints between FMs must be expressed and enforced. For example, in section 2.2 we expressed that a House with a "SecurityManager" imposes to have a "Lock" and an "OpenedState" sensor for each Opening, as well as a "Presence" sensor and "Locking" actuator for each Room. In SpineFM these relations will be expressed as constraints or rules such as if I select Se-curityManager in House, the feature Lock is automatically selected in my future sub-configuration of Opening.

The package RFModel provides concepts to express such rules. These rules are grouped in a RestrictionFunction that complements DEAssociations. A restriction function is oriented from a source FM to a target one, and contains several Rules. A rule is defined as a trigger from an instance of the source and an action to be performed on an instance of the target. The trigger is a ConfigurationState, it represents a specific state of a FM configuration (the sets of selected features and the set of deselected ones). SpineFM supports different actions on FMs (ActionOnFM concept): select or deselect on a feature, and addConstraint to add a new crosstree constraint in the FM.

Finally, as associations are not oriented and restriction functions are, they must be implemented in both ways of the associations. In order to ease the design of the SPL, the inverse restriction functions and rules are automatically computed and maintained by SpineFM.

DERIVING A COMPOSITE CONFIGU-RATION

The domain model and related FMs are also used to derive composite configurations in a consistent way.

Composite Configurations

The configuration of a SpineFM SPL is defined by a Com-positeConfiguration, which is a composition of linked Sub-Configurations. A SubConfiguration is itself a FM configuration related to a domain element instance. The Compos-iteConfiguration contains Links that connect a source subconfiguration to a target one. It is important to note that a Link refers to a related DEAssociation as it can be seen as an instance of this association.

Figure 3 depicts two examples of such composite configurations containing respectively 3 and 6 sub-configurations for the different domain elements House, Room and Opening. In the first composite configuration, the link between the sub-configurations "fromDoor" and "home" corresponds to the association "hasGateways" defined in Figure 1 that relates House and Opening.

Properties

A SubConfiguration is a configuration of a FM as defined by Benavides et al. : "Given a FM with a set of features F , a configuration is a 2-tuple of the form (S, R) such that S, R ⊆ F being S the set of features to be selected and R the set of features to be removed such that S ∩ R = ∅." [START_REF] Benavides | Automated analysis of feature models 20 years later: A literature review[END_REF].

A configuration is defined as a ConfigurationState in which each feature of the FM belongs either to the set of selected or deselected features w.r.t. to the FM semantics (i.e., crosstree constraints and feature groups are respected). A composite configuration is valid and complete w.r.t. to a domain model if (i) multiplicities of associations are respected, (ii) multiplicities of concepts are respected, and (iii) subconfigurations are valid and compatible. The composite configuration then conforms to the domain model.

Both composite configurations presented in Figure 3 are conforms to the domain model presented in Figure 1 following this definition. Multiplicities of associations are respected: the House is connected to a unique Opening in both composite configurations, each House has at least one Room and each Room one Opening. Assuming we can only instantiate a unique House per composite configuration, and as many Rooms and Openings as desired, multiplicities of concepts are respected too. Finally each sub-configuration is valid w.r.t. its FM and linked sub-configurations are compatible. For example, the "entrance" sub-configuration (second composite configuration on Figure 3) contains a "Locking" feature, so it is linked to Opening sub-configurations with "Lock" feature as expressed by red arrows in Figure 2.

Moreover we define the consistency of the SPL as the realizability of each sub-configurations of the SPL [START_REF] Metzger | Disambiguating the documentation of variability in software product lines: A separation of concerns, formalization and automated analysis[END_REF]. This means that for all valid sub-configuration of each domain element, it exists a minimal composite configuration conforming to the domain model that contains it. In other words, the SPL does not contain any "dead" sub-configurations, by analogy with the dead features definition in feature modeling.

Derivation Process

SpineFM must ensure that the derivation of a composite configuration is an order free process. The user is thus only authorized to do specific actions, which are based on her previously done actions. SpineFM then manages different contexts of configuration, so to support a staged composite configuration process, enabling partial configurations without following any predefined configuration workflow.

We distinguish two kinds of actions in our system: user actions (package UserActionModel ), and system actions (package SystemActionModel ). User actions provide a high level of abstraction to realize coarse-grained actions such as selecting a feature or linking two sub-configurations. Moreover these actions create and orchestrate the system actions, which manipulate the different concepts of the metamodel. Different kinds of system and user actions exist, e.g., , to create a configuration, a link, or rename elements, but we only deal here with actions on FMs, corresponding to selection/deselection of features, and creation of cross-tree constraints inside FMs.

The different actions realized on FMs can have impacts (i.e., se-lection or deselection) on the other ones, following the restriction functions. For example, we explain in Section 2.2 that if a feature "Security Manager" is selected in the House sub-configuration, then some features must be selected in all sub-configurations of Room and Opening. The key idea is that realizing this sub-configuration of the House will globally impact all the other sub-configurations of Room and Opening. We use here the term "global" to insist on the fact that all further sub-configurations will be impacted. On the other hand, if we select in a specific Room sub-configuration a "Locking" actuator, then only the associated (but all of them) Opening sub-configurations should have a "Lock" feature. This means that realizing a sub-configuration of the Room will locally impact the sub-configurations of Opening. The term "local" expresses here that impacts are only localized on few sub-configurations.

To manage these impacts and their We illustrate the notion of context with the following scenario: A user starts the derivation by selecting the feature "Sensors" in a Room. Now if she continues by selecting the feature "SecurityManager" in the DE House, the CPS of House in the global context is impacted, as the House can only be present once in a composite configuration. As some rules are associated to this feature (see red arrows on Figure 2), the CPS of Room in the global context is also impacted to select "Presence", "RollerStore" and "Locking" once for all: all the further Rooms she could create need to have these features selected. But at this moment, these 3 features are not selected in the CPS of Room in the first local context, and that could lead to inconsistent user actions (e.g., deselecting "RollerStore"). That is why the same impacts are also applied in the CPS of Room in the first local context, selecting the 3 features 'Presence", "RollerStore" and "Locking".

Consequently the ContextManager can be seen as the wizard of the derivation process. It contains all the contexts of the system and manages the different operations to create new contexts and to propagate actions through them.

PROPAGATION

In order to propagate the actions triggered by restriction functions through the different contexts of the system, SpineFM relies on a propagation algorithm. The propagation is triggered from a CPS that belongs to a context. Each time a user does an action like selecting or deselecting a feature, the propagation is triggered from the impacted CPS. A strong hypothesis to use this propagation algorithm is that the SPL must be consistent (see section 4.1.1).

We thus check the SPL consistency each time a new subconfiguration is added into the SPL. This checking process uses our propagation algorithm to verify the compatibility of a sub-configuration with the others. However we can reduce the complexity of the process by considering the domain model as a graph and restricting propagations to the biconnected domain elements. Considering the SPL as consistent, adding a new sub-configuration only requires to check few connected components to ensure the realizability of the new part.

Description of the Algorithm

The algorithm is recursive and comprises four main steps: (i) it computes the actions to be triggered in the different CPSs of the same context, following the associations; (ii) it applies the actions on the targeted CPS; (iii) for each impacted CPS that belongs to the global context, it applies the same impacts to all CPS related to the same domain element in local contexts; and finally (iv) it triggers back the propagation from each newly impacted CPS.

We now describe the main functions of the propagation algorithm. We consider that the GlobalContext (noted GC) and the set of LocalContexts (noted SetOfLocalContexts) are global variables accessible from everywhere. We also use a dot notation similar to the Java implementation. setOfActionsToDo := getActions(asso, cps)

12:
for all action in setOfActionsToDo do 13:

if cpsTarget.getActionsDone() ∩ action = ∅ then 14:

result.add(cpsTarget)

15:
action.setCPS(cpsTarget)

16:
action.apply() 17: return result Function 2 computes and applies actions to be triggered on CPSs that belong to the same context as the original action. It takes as inputs the CPS that is responsible for the propagation and its associated context. To ease reading in the following, we call this context the propagation context. The function iterates on associations to which the DE belongs (lines 4 to 16). For each association, the target DE is the one referenced by the other association end (line 5).

Then the CPS to target is selected w.r.t. to the multiplicity of the target DE (lines 7 to 10): if the DE has a upper multiplicity of 1, then the CPS must be retrieved from the global context, otherwise it is taken from the propagation context. The function retrieves the list of actions to trigger on targeted CPS (line 11, this function is detailed below). Finally it iterates on each action (line 12), verifies that the action has not been yet applied on the targeted CPS (line 13) and if not, it adds the targeted CPS to the resulting list of impacted CPSs (line 14) and applies the action (lines 15-16). result.add(rule.getAction()) 8: return result Function 3 compares a list of rules with a configuration state and selects which actions to apply on a CPS. It takes as inputs an association and the CPS triggering the actions. To compute the actions to apply, the function starts by getting the ConfigurationState (CS) corresponding to the CPS (line 2). Then it iterates on each rule of each restriction functions of the association (lines 3-4) and checks whether a CS of a rule matches with the CS returned from the CPS (line 6): a match means that a rule can be fired. The matching part consists in computing the intersection between two CS, which directly corresponds to the intersection of their respective sets of selected and deselected features. propagate(cps, cont) Function 4 then performs the propagation recursively. It takes as inputs the set of CPS which has been impacted by restrictions (Function 2) and the propagation context. The function iterates on each CPS handling two possibilities. The first one is the case where the CPS refers to a DE with a upper multiplicity higher than 1 and the context given as input is local, then the propagation is triggered with this CPS (line 11). If one of the previous conditions is not met, i.e., the CPS refers to a DE with a upper multiplicity of 1 or the context corresponds to the global context (line 4), the propagation is applied on the global context (line 5). However, if a CPS with a upper multiplicity higher than 1 is impacted in the global context (line 6), then all CPSs referring to the same DE in local contexts must reflect the same impacts (line 7). This is exactly the case at the end of the last example of section 4.2. Actually the function mergeWithCPS, which takes a CPS as input, looks in the context to retrieve a CPS with the same referring DE and apply in this last CPS all actions applied in the CPS given in argument. Finally, as all local contexts can have new impacts, the propagation is also triggered from them.

Termination of the Algorithm

The propagation algorithm is based on actions triggered by a user action on a CPS. A CPS cannot be modified twice by the same action because of the idempotence of all supported actions. In Function 2 we check if an action has already been done (line 13) to reduce the algorithm complexity and to know exactly which CPSs have been impacted. Moreover, the system actions associated to restriction functions (and triggered by the propagation) are only FM actions to select or deselect features, or to add a constraint.

Consequently the configuration space associated to CPS is always decreasing, each step of the propagation reducing the number of allowed actions. This shows that the algorithm always terminates and a propagation results in the application of all the rules once on each context, in the worst case.

EVALUATION

In this section, we elaborate on the implementation and the evaluation of our approach based on a real-world case study. We evaluate our approach by tracing the derivation process while creating configurations. We want to verify the relevance of the approach w.r.t. (i) the need for complex configurations (see Section 6.4.1), (ii) the variability of the SPL (see Section 6.4.2), and (iii) impacts of the algorithm on propagation time (see Section 6.4.3) and memory usage (see Section 6.4.4). We also discuss the threats to validity regarding our evaluation.

Implementation

The solution described in this paper has been entirely implemented in Java 6 the Eclipse Modeling Framework (EMF) for the metamodeling part3 SpineFM is constituted by more than 90 KLOC and around half of them are generated using EMF. It can be used through a REST API which allows to create any of the user actions. SpineFM is connected to the FAMILIAR DSL, which provides a language and API facilities to manipulate and reason on different feature model formalisms [START_REF] Acher | Familiar: A domain-specific language for large scale management of feature models[END_REF].

A generic user interface is also provided to support the derivation process. The interface is not dedicated to a specific domain model but uses meta-data associated to feature models and domain models [START_REF] Urli | Towards Flexible Configuration User Interfaces (in french) / Vers des interfaces graphiques flexibles de configurations[END_REF]. The implementation of the interface uses the Javascript framework AngularJS and is around 7 KLOC. Finally a generation tool for YourCast products (YourCast is described more in details in the next section) has also been created using Java 6 and EMF, representing more than 95 KLOC. The tool relies on different EMF transformations, taking as input the composite configuration and the domain model, and transforming them to an architectural model of the solution. Then other transformations are applied to create specific component models until a final model-to-code transformation that uses templating facilities from the Velocity engine.

YourCast

YourCast4 is a project initiated in 2011 which aims at creating an industrial-strength SPL for Digital Signage Systems (DSS) [START_REF] Urli | Managing a Software Ecosystem Using a Multiple Software Product Line: a Case Study on Digital Signage Systems[END_REF]. A DSS broadcasts dynamic information, mainly from the Web, typically targeting both public institutions and private companies. This project involved during two and half years around 30 contributors realizing more than 470 KLOC for the assets of the SPL and two software architects for the design of the SPL.

Several products have been generated using the complete toolchain mentioned above, including SpineFM as reasoning engine, the user interface to create the configuration and the generation part to create the concrete product. Some of the generated products have been notably deployed on several university campuses, on our laboratory, during conferences, or for big events like the "Choralies" an event which involves more than 4000 of participants in the south of France. We discuss in the following paragraphs the realization of some of these products and use them as starting points to evaluate different aspects of the proposed approach.

Evaluation Setup

Using SpineFM, a DSS is captured at the domain level by 5 concepts: the Sources of information to display, the Renderer components to display information, the Transition components to move from a piece of information to another, the Zone where to put information on the screen and the Layout to organize the different zones and design the display. Figure 7 gives an overview of the YourCast domain model. We represent inside each domain element box the multiplicity associated to the concept (e.g., a DSS contains one layout and many sources). The domain model also contains 2 restriction functions by associations (one for each orientation of the association) and 174 rules, including the automatically computed inverse ones. The rules express constraints between component like type compatibility between Sources information and rendering components, and style compatibility between zones, renderers, layout, and transitions. The table 1 gives some figures about feature models used in the YourCast project. Our feature models have small size in terms of features but are highly constrained, as they are actually automatically built by merging feature models describing individual products by using a logical operator defined in the FAMILIAR tool [START_REF] Acher | Separation of Concerns in Feature Modeling: Support and Applications[END_REF]. This operation allows us to manage the evolution of our feature models, however it imposes to create a lot of constraints inside feature models [START_REF] Urli | Using composite feature models to support agile software product line evolution[END_REF]. This gives some first insights on the configuration process.

Layout Zone Renderer

First, the number of sub-configurations and links seems to be always related, which is consistent as the composite configurations conforms to the domain model described in Figure 7.

The number of contexts is also directly proportional to the number of configurations being built by the user.

The theoretical number of contexts is indeed bounded by the number of configurations: it corresponds to at least one context (the global one) and at most twice the number of configurations being built by the user, these extra contexts handling unbounded multiplicities (i.e., 1..*). We can notice that the average number of contexts is significantly lower than the upper bound of this theoretical number.

As for actions, we split the measure into four categories: we distinguish user actions and system actions as explained in 4.2. Then system actions are divided into two categories: the automatic actions, triggered by restriction functions, and the FM actions. These are implicit actions realized by FAMILIAR back-end solvers (SAT or BDD depending on the operations), when configuring the FM, so that it remains valid, e.g., selecting automatically a parent feature or applying a constraint. We observe that the number of user actions is very low in comparison with the total number of system actions, emphasizing the need for an automatic derivation process to create complex products. Moreover as the system actions are only feature model actions, it gives an interesting insight on the size a unique feature model would have to capture equivalent configurations (e.g., more than 4000 feature in case A). Finally we also observe that feature model actions are far more frequent than automatic actions.

Though our figures obviously depend on the design of our feature models, this shows that our approach can support a configuration process with automatic propagation while relying on feature models and usual solvers.

Number of configurations

As the variability captured in an SPL is related to the number of configurations it represents, we determine how to compute a potential number of composite configurations given the domain model and the number of feature model configurations.

In YourCast, let CL, CZ , CR, CS and CT be the respective number of configurations for Layout, Zone, Renderer, Source, and Transition elements (all figures are available in Table 1). We define Z as the total number of zones in a composite configuration, as a layout can be associated with many zones, and we define R as the total number of renderers associated to a zone (assuming that each zone has the same number of renderers), as a zone can have many renderers. Then we can compute N , the number of potential composite configurations depending on Z and R, following this formula:

N = C Z ! (C Z -Z)! × C R ! (C R -(R×Z))! × C S ! (C S -(R×Z))! × C T ! (C T -Z)! × CL
However N is an upper bound of configurations, as it does not take into account the compatibility and restriction between products.

The average number of zones in the considered products is around 3 and the average number of renderers per zone is around 4. Then given Z = 3 and R = 4, we obtain N = 2.28 × 10 52 potential complex configurations. Even if Z = 1 and R = 1, this leads to a composite configuration with only one instance of each concept, the number of available configurations being N = 26.493.480. The very high number of possible combinations emphasizes the high variability and the great complexity of the SPLs one can manage with the proposed approach.

Propagation time

In our approach the propagation algorithm is key to the configuration process. Therefore it is essential that propagation time remains short enough to keep the user focus on her configuration task. During the 5 configurations described in Table 2, 266 propagations occured (propagations are part of user actions). We also gathered metrics on them, presented in Table 3, classifying them by the length of the propagation path. We define a propagation path as the number of CPS impacted during the propagation. The second column gives the number of occurrences of propagation of a given path length. The three last columns give respectively the average duration of the propagation in milliseconds, the average number of system actions and the average number of impacted contexts. The last line shows the total number of propagation occurences, duration time, number of system actions and number of impacted contexts.

First we can notice that the 266 propagations on the 5 configurations involved more than 7000 system actions. A high percentage of these propagations only impact a single context, making the propagation very fast. It is interesting to note that propagations with a path length greater than 7 are very rare (only one occurence of each). Actually this number of 7 seems to be strongly related to the considered domain model. In our YourCast model, a propagation may impact 4 concepts simultaneously in the same context, but We think it might also be related to the usual habit to finish a sub-configuration before shifting to another: finished configurations cannot be impacted anymore, which limits the impacted contexts.

We also observe that, as expected, in average the longer is the path, the longer is the duration and the more there are system actions. The high duration number obtained for a path length of 3 is not absolutely clear for us, but it can partially be explained by the fact that most propagations of this length have been obtained during the last configuration (configuration E in Table 2), which involved a lot of artifacts. This has obliged the FAMILIAR reasoning engine to use the garbage collector, slowing down the whole execution. Finally we observe that the average number of impacted contexts is very low. Most of the impacts are very local, thus showing the good scalability of the propagation algorithm.

Memory usage

The propagation algorithm relies on the contexts, which are composite entities. Each new context contains as many CPS as concepts in the domain model. Each CPS is associated with a FM configuration through the FAMILIAR DSL. Thus we measured the memory footprint of SpineFM when augmenting artificially the number of contexts.

We show in Table 4 the result of the memory usage obtained with the bash command free -m. The first measure is taken after the Tomcat server launch, all services being ready: the reported memory usage is the footprint memory usage of the machine. For the second measure, we initialized SpineFM with YourCast information: the global context is automatically created. Then all other measures are taken after having activated some Cre-ateContext user actions through the SpineFM API. Table 4 shows that from 1 to 1000 contexts, the consumed memory increases gradually, a thousand of contexts taking around 170 Mb of memory. This experiment points out that our tool easily supports configurations with thousands of subconfigurations for a SPL of the size of YourCast.

However we can also notice that the initialization of a first configuration of YourCast took 163 Mb of memory, which is significant. This amount of memory can be explained by the usage of FAMILIAR to manage our FMs: the first initialization of SpineFM with a domain model imposes to load the associated FMs in FAMILIAR, which is memory consuming. Moreover, in YourCast, FMs are defined as the result of a merging operation in FAMILIAR, which is also known to be memory consuming [START_REF] Acher | Separation of Concerns in Feature Modeling: Support and Applications[END_REF].

To emphasize the memory consumption related to SPL configurations (and not only due to context management), we measured the memory consumption during the realization of the 5 products given in Table 2. The measures, also obtained with the command free -m, are shown on Table 5.

Here the memory consumption for the first configuration was around 175 Mb of memory: it corresponds to the first initialization of the system, as explained above. Afterwards, each configuration took less than 20 Mb of memory, which seems reasonable.

Threats to Validity

A first internal threat to validity concerns the termination of our algorithms. Even if we demonstrated in section 5.2 that our propagation algorithm terminates, bugs in the implementation could occur. The SpineFM implemented is thus completed by unit tests and some coverage of different scenarii in order to minimize such a risk. Moreover we are currently formalizing the whole approach, which will allow us to formally verify our set of algorithms. Another internal threat concerns our memory measures. Actually as SpineFM embeds the FAMILIAR toolkit, it is hard to distinguish what is really used by SpineFM or by FAMIL-IAR. A more complete evaluation based on the number of instantiated objects in SpineFM during a high number of configurations should give us more confidence in the first results presented here.

The main external threat to validity is related to the low number of experiments we currently conducted. We only applied our approach in one real case study with the Your-Cast project. Nevertheless the approach shows its usability during the project, and experiments on another real case study have already been scheduled to complement our results [START_REF] Urli | How to exploit domain knowledge in multiple software product lines?[END_REF].

Another external threat to validity concerns the users involved in our evaluation as they already knew the YourCast system and the configuration interface. However we estimate that the obtained metrics are not strongly related to the user behaviors. Moreover we are actually conducting user experiments with ergonomists to evaluate the config-uration process on the SpineFM user interface supporting undo actions. This should help us to improve both the configuration process and the interfaces for further evaluations.

CONCLUSION

In this paper, we described SpineFM, a tooled approach that allows to handle complex configurations in SPL. The SPL is then organized around a domain model and interrelated feature models. The approach enables users to create complex configurations in an order-free process, while being guided thanks to a consistent propagation of actions. We also reported on the application of the approach on the development of industrial-strength family of digital signage systems, showing its good performance on a medium-scale SPL.

At short term we are going to apply our approach to another real SPL of cyber-physical systems, aiming to refine and validate our proposals. A formalization of the whole set of algorithms will complement this validation. As future work, we plan to extend the SpineFM variability model to support attributed feature models and decision models, and to study more thoroughly the expressiveness of domain models w.r.t. UML model, so to extend its capabilities. As the order free configuration process is at the heart of our solution, we also plan to implement our algorithms inside a collaborative configuration environment.

Figure 1 :

 1 Figure 1: Domain model of the example Figure1gives a very high point of view of a House: it is an aggregation of Rooms, each Room containing at least one Opening. The House itself has at least one opening. In our scenario, these concepts will be kept in the configuration space as classes and each of them supports some variability represented by a FM. Figure2depicts these FMs. The House can have a central computer to manage globally temperature, luminosity and security. Openings can be Doors or Windows, the windows can be a smart tinted glass and have roller stores. We also can put a lock on each opening and a sensor can be put to give the opening state. Each room can have sensors and actuators to manage temperature, presence or lightning. Moreover the FM expresses some internal constraints such as "Temperature implies Thermostat".

Figure 2 :

 2 Figure 2: Feature models and excerpt of relations home:House {House}

Figure 3 :

 3 Figure 3: Example of two valid configurations

Figure 4 :

 4 Figure 4: Overview of the approach

Figure 5 :

 5 Figure 5: Domain model and interrelated FMs (metamodel excerpt)

Figure 6 :

 6 Figure 6: Composite configuration (metamodel excerpt)

Function 1 Function 2

 12 propagate(cps:CPS, cont:Context):void 1: setOfCPS := restriction(cps, cont) 2: recursePropagation(setOfCPS, cont) Function 1 is the entry point of the propagation. It takes as inputs a CPS impacted by an action and its related context. This function first computes and applies actions on CPSs of the same context. Then the list of resulting impacted CPSs is used to trigger the propagation recursively and apply global impacts in local contexts. restriction(cps:CPS, cont:Context):Set 1: result := ∅ 2: deSrc := cps.getDE() 3: assoSrc := deSrc.getAssociation() 4: for all asso ∈ assoSrc do 5:deTarget := assoSrc.getOtherEnd(deSrc)

Function 3 6 :

 36 getActions(asso:DEAssociation, cps:CPS):Set 1: result := ∅ 2: CS := cps.getState() 3: for all rf ∈ asso.getRestrictionFunctions() do 4: for all rule ∈ rf.getRules() do 5: ruleCS = rule.getState() if ruleCS ∩ CS = ruleCS then 7:

1 :

 1 for all cps ∈ setOfCPS do 2: deTarget := cps.getDE() 3: multTgt := deTarget.getMultiplicity() 4:if (multTgt.upperBound() = 1) or (cont = GC) then

Figure 7 :

 7 Figure 7: YourCast Domain Model

  propagation, we define the notion of Context. A unique Global Context manages all the global impacts and many Local Contexts are used for the local ones. More precisely, information about the impacts are contained in the concept of ConfigurationPro-cessStep (CPS), which represents a FM being configured. A CPS contains (i) a reference to the domain element it rep-

resents; (ii) references to the actions done on the FM; and (iii) the current configuration state of the associated FM (see section 3.3).

A context only contains a unique CPS for each DE. Moreover, contexts are closely related to the multiplicity of the DEs. If a DE can be instantiated only once (upper multiplicity is 1) in a composite configuration, then there is no need to keep another CPS for this DE on each context. We only need a unique CPS contained in the global context to represent the state of this DE. However if a DE can be instantiated many times, it does not mean its CPS will only exist in a local context. In fact, each context (local and global) of the system will contain a CPS for these DEs.

Table 1 :

 1 YourCast feature modelsOur experimental setup consists in configuring different Your-Cast products to gather different kinds of metrics. All con-figurations have been realized on a virtual machine exploiting a Linux Debian 6.0.8 system with 4096 Mb of RAM and 4 CPUs at 2.4 Ghz. The toolchain was running on a Tomcat 6 application server limited to 512 Mb of memory. The Java version used was 1.6.0 build 26.

	Concept	# Features # Constraints # Config.
	Sources	81	154	68
	Renderers	76	347	74
	Transitions	33	45	15
	Zones	49	160	27
	Layouts	51	59	13
	Average	58	149	39
	Total	290	765	-

Table 2 :

 2 Metrics on YourCast Configurations

Table 3 :

 3 Propagation metrics by number of steps if the Layout is involved, the global context impacts is then replicated in few local contexts.

Table 4 :

 4 SpineFM memory evolution by contexts

Table 5 :

 5 SpineFM memory evolution by config.

This FM metamodel is partially extracted from the project http://www.eclipse.org/featuremodel/ focusing on elements used by the propagation algorithm.

[START_REF] Acher | Separation of Concerns in Feature Modeling: Support and Applications[END_REF] However SpineFM is currently limited to propositional FMs.

More information about SpineFM will be soon available at http://www.yourcast.fr/en:spinefm.

http://www.yourcast.fr

Acknowledgments

The work reported in this paper is partly funded by the ANR YourCast project under contract ANR-2011-EMMA-013-01.


Karim Jerbi

Etienne Combrisson

Sarang S Dalal

Juan R Vidal

Carlos M Hamame

Olivier Bertrand

Alain Berthoz

Philippe Kahane

Jean-Philippe Lachaux

Carlos M Hamamé

Decoding cognitive states and motor intentions from intracranial EEG: How promising is high-frequency brain activity for brain-machine interfaces?

Keywords: Brain-computer Interfaces, intracranial electroencephalography, electrocorticography, High frequency activity, gamma band, real-time electrophysiology, intention decoding, cognitive BCI

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

Whether the future of Brain-Computer Interface (BCI) technology will be predominantly based on non-invasive recordings of brain signals or, on the contrary, on invasive electrophysiological recordings is still a matter of debate. Yet, it is conceivable that the nature of the optimal recordings that are needed will depend on the application and the context. For example, while intracranial EEG (iEEG) might turn out to be irreplaceable with scalp EEG in the case of certain specific clinical or therapeutic BCI applications (e.g., restoring skilled motor behavior to tetraplegic patients), other applications such as neurofeedback-based cognitive remediation or enhancement strategies will most probably continue to rely on noninvasive brain recordings. In addition, it is a safe bet that the BCI-oriented video gaming industry is unlikely to require in the future that its customers undergo surgery to be able to play their games. We contend therefore that research into invasive and non-invasive methods for BCI research will remain complementary and, most importantly, will serve different purposes.

In humans, reports of invasive BCI systems are less numerous than in non-human primates and signal selection for optimal control is still in its early days [START_REF] Andersen | Selecting the signals for a brain-machine interface[END_REF]). Furthermore, most reports of invasive BCI studies have relied on electrocorticography (ECoG) subdural grids and strips; however, insights on the putative utility of stereotactic-EEG (SEEG) recordings for BCI applications are scarce [START_REF] Lachaux | A blueprint for real-time functional mapping via human intracranial recordings[END_REF]Jerbi, Freyermuth et al. 2009;[START_REF] Hamame | Reading the mind's eye: online detection of visuo-spatial working memory and visual imagery in the inferior temporal lobe[END_REF].

We performed a series of studies to evaluate the possible utility of intracerebral recordings obtained via SEEG depth electrodes for the development of novel Brain-Computer Interfaces. In particular, we set out to investigate the efficiency of local broadband high-gamma (approx. 50-150 Hz) neuronal activity as a reliable BCI feature. This hypothesis stems from accumulating evidence across both human and animal studies indicating that broadband highgamma activity is a reliable marker of local neuronal processing [START_REF] Logothetis | Neurophysiological investigation of the basis of the fMRI signal[END_REF][START_REF] Mukamel | Coupling between neuronal firing, field potentials, and FMRI in human auditory cortex[END_REF][START_REF] Crone | Highfrequency gamma oscillations and human brain mapping with electrocorticography[END_REF][START_REF] Lachaux | Relationship between task-related gamma oscillations and BOLD signal: new insights from combined fMRI and intracranial EEG[END_REF]).

To test the ability of patients to control various parameters of their intracranial recordings in real-time we used the Brain TV set-up, a custom-design online signal analysis system that computes and displays the ongoing power variations at various frequencies, including the high-gamma band [START_REF] Lachaux | A blueprint for real-time functional mapping via human intracranial recordings[END_REF]). Combining the findings of task-related power modulations observed with this system with that of classical offline analysis paves the way for the development of novel strategies for BCI and real-time functional mapping. In addition, we used offline analysis of SEEG data acquired during various delayed motor tasks (hand and eye movements) that directly address the question of whether motor intentions can be decoded in the brain, not only at execution but prior to execution during the planning phase.

Our results suggest that BCI performance may be improved by using signals recorded from various neuronal systems such as the oscillatory activity recorded in the motor and oculomotor systems as well as higher cognitive processes including attention and mental calculation networks (Jerbi, Freyermuth et al. 2009). We also found that gamma-and alpha-band activity play a key role in motor intention decoding, providing high decoding accuracy even during the delay period preceding movements. Of further interest to invasive BCI applications, is our finding that gamma-band power modulations in prefrontal cortex are differentially modulated by positive and negative feedback on one's performance [START_REF] Jung | Brain responses to success and failure: Direct recordings from human cerebral cortex[END_REF]. Moreover, we recently found using SEEG data that goaldirected behavior is associated with transient suppressions of broad-band gamma power in neuronal structures that closely match the so-called default-mode network [START_REF] Jerbi | Exploring the electrophysiological correlates of the default-mode network with intracerebral EEG[END_REF][START_REF] Ossandon | Transient suppression of broadband gamma power in the default-mode network is correlated with task complexity and subject performance[END_REF].

Beyond advancing our knowledge of the electrophysiological underpinnings of resting-state networks observed with fMRI, these recent results suggest that real-time monitoring of gamma power fluctuations in the resting state might be key to assessing a subject's attention state, and possibly also for tracking pathological alteration of fine-grained spatio-temporal network dynamics in patients with epilepsy.

In conclusion, our SEEG findings suggest that local modulations of gamma-band activity can be reliably used to infer the subject's intentions or cognitive states provided that the electrodes are implanted in the involved sites. A small methodological note of caution has to be raised, however, because of the vulnerability of SEEG to eyemovement artifacts. This previously unsuspected phenomenon consists of gamma-range contamination of the SEEG signal caused by the activity of extra-ocular eye muscles during saccade executions. Several techniques (such as bipolar rereferencing) can be applied to minimize or rule out the contribution of such artifacts (Jerbi, Freyermuth et al. 2009;[START_REF] Worrell | Recording and analysis techniques for high-frequency oscillations[END_REF].

Taken together, our findings suggest that SEEG depth recordings of high-gamma activity provide an extremely promising feature to decode motor intentions and cognitive states and that non-invasive techniques such as electroencephalography and magnetoencephalography (MEG) might also need to improve their ability to target such high-frequency modulations in order to improve their decoding power. High-gamma activity has been reported with MEG (e.g., [START_REF] Dalal | Simultaneous MEG and intracranial EEG recordings during attentive reading[END_REF])) but its sensitivity can be improved by adequate task design [START_REF] Jerbi | Taskrelated gamma-band dynamics from an intracerebral perspective: review and implications for surface EEG and MEG[END_REF]) and putatively by improved source modeling approaches (e.g., [START_REF] Cottereau | Multiresolution imaging of MEG cortical sources using an explicit piecewise model[END_REF][START_REF] Dalal | Five-dimensional neuroimaging: localization of the time-frequency dynamics of cortical activity[END_REF]). Finally, while we have focused here on the utility of gammaband activity for future BCI application, we contend that lower-frequency oscillations (e.g., in the alpha and beta range) will continue to be very useful features for decoding, both separately and in combination with high-gamma activity.

Acknowledgments

This research was supported in part by the Fondation pour la Recherche Médicale (FRM).